算法复杂度

苏丙榅2024-05-052024-05-12

我们都知道，数据结构和算法本身解决的是 “快” 和 “省” 的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢？这里就要用到本章要讲的内容：时间、空间复杂度分析。

1. 大O表示法

时间复杂度指的就是算法的执行效率，粗略地讲，就是算法代码执行的时间，用时越短效率越高。但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？

先看一段简单的代码：

void func(int n) 
{ 
    int sum = 0; 
    for (int i=1; i <= n; ++i) 
    { 
        sum = sum + i; 
    } 
    printf("sum = %d\n", sum); 
}

从 CPU 的角度来看，执行每行代码的操作都类似，虽然执行时间不尽相同，但是可以假设 CPU 执行每行代码的时间都是一个指令周期，这样就可以轻松算出上面代码的执行时间了：

第 3、8 行，分别需要1个指令周期 -> 2
第 4、6 行，分别需要n个指令周期 -> 2n

所以上面代码评估出的执行总时间是：T(n) = 2n+2

按照这个分析思路，我们再来分析一下这段代码：

void func1(int n) 
{
    int sum = 0;
    for (int i = 1; i <= n; ++i) 
    {
        printf("i = %d\n", i);
        for (int j=1; j <= n; ++j) 
        {
            printf("j = %d\n", j);
            sum = sum + i + j;
        }
    }
    printf("sum = %d\n", sum);
}

第 3、13 行，分别需要1个指令周期 -> 2
第 4、6 行，分别需要n个指令周期 -> 2n
第 7、9、10 行，分别需要n²个指令周期 -> 3n²

所以上面代码评估出的执行总时间是：T(n) = 3n²+2n+2

在数据结构中针对于复杂度的描述有一个表示方法，叫做大 O（欧）表示法，公式如下：

T(n) = O(f(n))

T(n) 表示代码执行的时间；
n 表示数据规模的大小；
f(n) 表示每行代码执行的次数总和；
O 表示代码的执行时间 T(n) 与 f(n) 表达式成正比；

所以上面估算出的代码复杂度用大O表示法可以写成这样：

T(n) = O(2n+2)
T(n) = O(3n²+2n+2)

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫作渐进时间复杂度，简称时间复杂度。

当 n 很大时，你可以把它想象成非常非常非常大的数，此时公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示上面两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n²)。

关于时间复杂度的推导，有以下三条原则可供参考：

只关注一个代码块中循环执行次数最多的一段代码
加法法则：多个代码块的总复杂度等于量级最大的那段代码的复杂度
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

2. 时间复杂度分析

2.1 O(1)

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如下面代码，即便有多行，它的时间复杂度也是 O(1）。

#include <stdio.h>
int findMax(int a, int b) 
{
    return (a > b) ? a : b;
}

int findMin(int a, int b) 
{
    return (a < b) ? a : b;
}

int main() 
{
    int num1 = 10, num2 = 20;    
    printf("最大值是：%d\n", findMax(num1, num2));
    printf("最小值是：%d\n", findMin(num1, num2));
    return 0;
}

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

2.2 O(logn)、O(nlogn)

关于数阶形式的时间复杂度也非常常见，同时也是最难分析的一种时间复杂度。下面举例说明：

#include <stdio.h>
int loopFunction(int n) 
{
    int i = 1;
    int count = 0;    // 用于记录循环执行的次数
    while (i <= n) 
    {
        i = i * 2;
        count++;      // 每次循环执行都增加计数
    }
    return count;
}

int main() 
{
    int n = 100;
    int result = loopFunction(n);
    printf("循环执行了 %d 次\n", result);
    return 0;
}

在这个while循环中，i 的初始值为 1，每次循环 i 都会乘以 2，直到 i 的值超过 n 为止。

分析这段代码的难度在于while并不是循环了n次，循环执行的次数取决于将 1 乘以多少次 2 后会超过 n。所以最后一次循环应该是 2^x>=n，指数x就是循环的次数，求指数x的表达式可以写为： x=log₂n，所以代码的时间复杂度为 O(log₂n)

如果将上面的代码稍作修改:

int loopFunction(int n) 
{
    int i = 1;
    int count = 0;    // 用于记录循环执行的次数
    while (i <= n) 
    {
        i = i * 3;
        count++;      // 每次循环执行都增加计数
    }
    return count;
}

按照刚才的思路其分析，最后一次循环应该是 3^x>=n，因此 x=log₃n ，所以这个函数的时间复杂度为 O(log₃n)

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？下面给大家推导一下：

根据换底公式，将以3为底的对数转换为以2为底的对数

log₃N = log₂N / log₂3

将分母移动到等号左边

log₃N * log₂3 = log₂N

两边同乘 log₃2

log₃N * log₂3 * log₃2 = log₂N * log₃2

因为log₂3 * log₃2 = 1

log₃N = log₂N * log₃2

由于log₃2是常数，根据大O表示法规则，低阶、常量、系数三部分可以忽略，所以 O(log₃N) = O(log₂N)，如果只看第一步 1/log₂3 也是一个常数，将其忽略之后也可以得出 O(log₃N) = O(log₂N)

使用同样的方法进行推导可得到结论：

O(log₃N) = O(log₂N) = O(logN) 【O(log₁₀N) = O(logN)】

这样我们就能彻底明白为什么所有的对数阶都用以10为底的对数来表示了。

如果把上面的main函数修改为下面的样子，程序的时间复杂度就又变了:

int main() 
{
    int n = 100;
    for(int i=0; i<10; ++i)
    {
        int result = loopFunction(n);
        printf("循环执行了 %d 次\n", result);
    }
    return 0;
}

由于loopFunction函数的时间复杂度为O(logn)，又因为该函数需要在一个循环中执行n次，所以该main函数的时间复杂度为O(nlogn)

2.3 O(m+n)、O(m*n)

我们再来讲一种跟前面都不一样的时间复杂度，代码的复杂度由两个数据的规模来决定。先看代码：

int calc(int m, int n) 
{
    int sum1 = 0;
    for (int i=1; i < m; ++i) 
    {
        sum1 = sum1 + i;
    }

    int sum2 = 0;
    for (int j=1; j < n; ++j) 
    {
        sum2 = sum2 + j;
    }
    return sum1 + sum2;
}

从代码中可以看出，m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。

如果将上面的两个并列的for循环写成如下的嵌套的形式，此时时间复杂度就变成了O(m*n)。

int calc(int m, int n) 
{
    int sum1 = 0;
    int sum2 = 0;
    for (int i=1; i < m; ++i) 
    {
        for (int j=1; j < n; ++j) 
        {
            sum2 = sum2 + j;
        }
        sum1 = sum1 + sum2 + i;
    }
    return sum1;
}

2.4 O(n²)

如果有一个嵌套的循环，并且外层和内层的循环次数是相同的，此时这段程序的时间复杂度就是 O(n²)，比如：

void func1(int n) 
{
    int sum = 0;
    for (int i = 1; i <= n; ++i) 
    {
        printf("i = %d\n", i);
        for (int j=1; j <= n; ++j) 
        {
            printf("j = %d\n", j);
            sum = sum + i + j;
        }
    }
    printf("sum = %d\n", sum);
}

但是不是所有嵌套循环内外的循环次数都相等，比如下面这样：

void func2(int n)
{
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        printf("i = %d\n", i);
        for (int j = i; j <= n; ++j)  // 此处是 j=i, 不是 j=0
        {
            printf("j = %d\n", j);
            sum = sum + i + j;
        }
    }
    printf("sum = %d\n", sum);
}

当 i=0 时，内层循环执行了 n 次
当 i=1 时，内层循环执行了 n-1 次
当 i=2 时，内层循环执行了 n-2 次
……
当 i=n 时，内层循环执行了 1 次

所以执行的总次数为：n+(n-1)+(n-2)+…+1 = n(n+1)/2 = n²/2+n/2

根据大O表示法推导规则，去掉系数和低阶之后得到的复杂度为 O(n²)

3. 空间复杂度

空间复杂度是对算法在运行过程中所需存储空间大小的评估。使用大O表示法既可以描述时间复杂度也可以用来描述空间复杂度。

下面拿一段代码举例：

#include <iostream>
int main() 
{
    int size;
    std::cout << "请输入数组大小: ";
    std::cin >> size;
    // 使用 new 运算符为数组动态分配内存
    int *arr = new int[size];
    // 使用分配的内存存储数据
    for (int i = 0; i < size; ++i) {
        arr[i] = i * 2; // 以偶数填充数组
    }
    // 打印数组内容
    std::cout << "数组内容: ";
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    // 记得释放内存
    delete[] arr;
    return 0;
}