C语言数据结构 —— 复杂度

1. 算法效率

1.1 如何衡量一个算法的好坏

如果衡量一个算法的好坏呢？比如我们有一段关于斐波那契数列的代码：

long long Fib(int N) {
    if (N < 3)
        return 1;

    return Fib(N - 1) + Fib(N - 2);
}

递归实现方式代码是非常简洁的，但是简洁并不代表高效率。因为其中包含了太多重复运算，大家可以自己图解这个算法，这里不再赘述。

1.2 算法的复杂度

算法再编写成可执行程序后，运行时需要耗费时间资源河空间资源。因此衡量一个算法的好坏，一般时从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小，所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经大道了很高的高度，所以我们如今已经不需要再特别关注一个算法的空间复杂度了。

2. 时间复杂度

2.1 时间复杂度的概念

时间复杂度的定义：再计算机科学中，算法的时间发杂度是一个函数(数学函数)，它定量描述了该算法的运行时间。

但是这个运行时间并不是我们主观意识的时间，因为在不同的机器上，同一段代码的运行时间是不一样的。比如我的处理器可以吊打银河系，而你的处理器打开 WPS 都费劲，那么同一段代码在分别在这两台机器上跑的时间肯定是不一样的。所以，算法中的基本操作的执行次数，为算法的时间复杂度。

那么如何找到算法的时间复杂度？即找到某校基本语句与问题规模 N 之间的数学表达式。例如说我们有以下代码：

// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N) 
{
    int count = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j)
        {
            ++count;
        }
    }

    for (int k = 0; k < 2 * N; ++k) {
        ++count;
    }
    int M = 10;
    while (M--) {
        ++count;
    }
    printf("%d\n", count);
}

我们可以看到，Func1 函数的基本操作次数为 F(N)=N^2+2*N+10 ，并且有：

• N=10 F(N)=130
• N=100 F(N)=10210
• N=1000 F(n)=1002010

但是在实际中计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要计算大概执行次数，那么这里我们使用大 O 的渐进表示法。

2.2 大 O 的渐进表示法

大O 符号：描述函数渐进行为的数学符号。

推导大 O 阶方法：

1. 用常数 1 取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是 1 ，则出去这个项目相乘的常数

使用大 O 的渐进表示法以后，Func1 的时间复杂度为：O(N^2)

• N=10 F(N)=100
• N=100 F(N)=10000
• N=1000 F(N)=1000000

通过上面我们会发现大 O 的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏的情况：

• 最坏情况：任意输入规模的最大运行次数
• 平均情况：任意输入规模的期望运行次数
• 最好情况：任意输入规模的最小运行次数

例如说：在一个长度为 N 的有序数组中查找一个元素 x

最好情况：1 次找到

最坏情况：N 次找到

平均情况： N/2 次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中查找元素的时间复杂度为 O(N) 。

2.3 常见时间复杂度计算举例

实例1：

// 计算Func2的时间复杂度？
void Func2(int N) {
    int count = 0;
    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
    printf("%d\n", count);
}

对于 Func2 ，我们可以计算的大概执行次数为 2*N+10 ，但是我们用大 O 的渐进表示法，可以省略掉一些项，那么最终的时间复杂度为 O(N) 。

实例2：

// 计算Func3的时间复杂度？
void Func3(int N, int M) {
    int count = 0;
    for (int k = 0; k < M; ++k)
    {
        ++count;
    }
    for (int k = 0; k < N; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}

对于 Func3 ，可以计算大概的基本执行次数为 M+N ，两项都不能被忽略，所以用大 O 的渐进表示法，可以得出时间复杂度为 O(M+N) 。

实例3：

// 计算Func4的时间复杂度？
void Func4(int N) {
    int count = 0;
    for (int k = 0; k < 100; ++k)
    {
        ++count;
    }
    printf("%d\n", count);
}

对于 Func4 ，可以计算基本执行次数为 100 ，是一个常数，所以用大 O 的渐进表示法为 O(1) 。

实例4：

// 计算strchr的时间复杂度？
const char* strchr(const char* str, int character);

以前我们介绍过 strstr 这个函数，那么对于 strchr 来说，也是一样的道理，即在字符串中查找某个字符。也就类似于前文说的数组例子。那么时间复杂度为 O(N) 。

实例5：

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n) {
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

这是一个冒泡排序算法。我们需要注意，计算时间复杂度时不能只看循环，这种做法是肤浅的、错误的。我们应该关注算法的内核。就拿这个冒泡算法来说，我们通过图解来表达清楚冒泡排序的核心：

可以看到，最好的情况就是执行 N 次(不是 1 次原因是即使不进行元素交换，此算法也会对数组遍历检查)。最差的情况就是计算 1、2、3……N-2、N-1 这个等差数列之和，即 (N-1)*N/2 ，那么要表示时间复杂度，就要用大 O 的渐进表示法，即去除影响不大的项，O(N^2) 。

实例6：

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x) {
    assert(a);
    int begin = 0;
    int end = n - 1;
    // [begin, end]：begin和end是左闭右闭区间，因此有=号
    while (begin <= end)
    {
        int mid = begin + ((end - begin) >> 1);
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid - 1;
        else
            return mid;
    }
    return -1;
}

这是一个二分查找的算法，我们来具体分析一下此算法的时间复杂度。我们通过最坏的角度去分析：

所以这个二分查找的算法的时间复杂度为 O(logN) 。

实例7：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N) {
    if (0 == N)
        return 1;

    return Fac(N - 1) * N;
}

对于函数递归，我们只需要关心函数被调用几次即可。那么对于求阶乘的递归算法来说，函数被调用了 N 次，所以时间复杂度为 O(N) 。

实例8：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N) {
    if (N < 3)
        return 1;

    return Fib(N - 1) + Fib(N - 2);
}

现在我们来分析文章开头提到的斐波那契数列的递归算法。此算法的时间复杂度为 O(2^N) 。

那么大家看到这个算法的时间复杂度是非常高的，这就证明了这个算法的效率非常低。例如说我们要求斐波那契数列的第 40 个数字，那么它的计算量为 2^40 ，可想而知，效率非常低下。

3. 空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时(额外)占用存储空间大小的量度。

空间复杂度不是程序占用了多少字节空间，而是变量(空间)的个数。即使想要计算程序占用了多大空间也没有意义。

空间复杂度计算规则与时间复杂度一样，都使用大 O 渐进表示法。

实例1：

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n) {
        assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

我们要注意，计算空间复杂度是要计算变量(空间)的个数。因为所占空间数为常数，所以空间复杂度为 O(1) 。

实例2：

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n) {
    if (n == 0)
        return NULL;

    long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }
    return fibArray;
}

这个算法就非常简单了。占用的空间与参数 n 有关，所以空间复杂度为 O(N) 。

实例3：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N) {
    if (N == 0)
        return 1;

    return Fac(N - 1) * N;
}

可以明确的看到，Fac 函数被调用 N+1 次，每次调用都开辟一个栈帧，而这个栈帧又是常数。但是调用几次又参数 N 决定，所以空间复杂度为 O(N) 。

补充：

在刚才的计算中，可以发现我们并没有把形参的所占空间给算进去。这里需要注意的是，函数的形参是完成算法的条件，并不是额外开辟的一个临时空间。

4. 复杂度的 oj 练习

消失的数字

题解：

int missingNumber(int* nums, int numsSize)
{
    int sum=0;
    for(int i=0;i<=numsSize;i++)
    {
        sum+=i;//求出 0~n 范围的和
    }
    int tmp=0;
    for(int i=0;i<numsSize;i++)
    {
        tmp+=nums[i];//求出数组和
    }
    return sum-tmp;
}

轮转数组

题解1，以空间换时间：

void rotate(int* nums, int numsSize, int k)
{
   int* arr=(int*)calloc(numsSize,sizeof(int));
   int size=k%numsSize;
   memcpy(arr,nums+numsSize-size,size*sizeof(int));
   memcpy(arr+size,nums,(numsSize-size)*sizeof(int));
   memcpy(nums,arr,numsSize*sizeof(int));
   free(arr);
   arr=NULL;
}

题解2，三步翻转法：

//三步翻转
void reverse(int* nums, int left, int right)
{
    while (left < right)
    {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    if (k >= numsSize)
        k %= numsSize;
    reverse(nums, 0, numsSize - k - 1);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
}