数据结构初阶：时间复杂度与空间复杂度详解

确定基本操作：找出其中最核心、执行次数最多，且对整体运行时间起关键影响的基本操作。例如在排序算法里，元素比较、交换的操作；在搜索算法中，是数据元素的查看操作。

分析操作执行次数：设输入规模为 $N$，计算基本操作随着 $N$ 的变化，执行了多少次。以简单的线性搜索算法为例，对于一个长度为 $n$ 的数组，最坏的情况目标元素在末尾或不在，需查看 $N$ 个元素；最好的情况在首位，只需查看 1 个元素。平均下来查看 $(N+1)/2$ 个元素。

忽略低阶项与常数系数：根据大 O 记号的规则，只保留最高阶的项，并且省略该项的常数系数。因为当 $N$ 足够大时，低阶项和常数对整体增长趋势的影响微乎其微。在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为 $O(N)$。

常见示例计算

示例 1

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);
}

整个函数中，基本操作执行了 $2N+10$ 次。for 循环的时间复杂度是 $O(N)$，while 循环的时间复杂度是 $O(1)$。在计算总体时间复杂度时，由于 $O(N)$ 的增长速度比 $O(1)$ 快，当 $N$ 趋向于无穷大时，起主导作用的是 $O(N)$ 这一项。所以，Func2 的时间复杂度是 $O(N)$。

示例 2

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);
}

整个函数中，基本操作执行了 $M+N$ 次。两个循环是顺序执行的，总的执行时间是两个循环执行时间之和。由于不知道 $M$ 和 $N$ 的大小关系，根据时间复杂度的加法规则，总体时间复杂度为 $O(M+N)$。

示例 3

void Func4(int N) {
    int count = 0;
    for (int k = 0; k < 100; ++k) {
        ++count;
    }
    printf("%d\n", count);
}

整个函数中，基本操作执行了 10 次。由于该循环执行次数不随输入规模 $N$ 变化，是一个常数级别的操作。所以，Func4 的时间复杂度是 $O(1)$。

示例 4：strchr

const char* strchr(const char* str, int character);

strchr 函数用于在字符串 str 中查找字符，基本操作执行最好 1 次，最坏 $N$ 次。时间复杂度一般看最坏，时间复杂度为 $O(N)$。

二分查找

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;
}

每经过一轮循环，搜索区间的长度就会减半。设经过 $k$ 轮循环后，搜索区间缩小到只剩 1 个元素，此时有等式 $n * (1/2)^k = 1$，求解 $k$ 可得 $k = \log_2 n$。也就是说，在最坏的情况下，最多需要进行 $\log_2 n$ 次比较操作就能确定目标元素是否存在于数组中。所以 BinarySearch 函数的时间复杂度为 $O(\log n)$。

冒泡排序

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;
    }
}

最好情况下，也就是数组原本就是有序的，内层循环第一次遍历就不会有任何元素交换，此时 exchange 变量始终为 0，内层循环只完整执行一轮就会因 break 跳出，整体时间复杂度是 $O(n)$。但通常我们讨论的是算法的最坏情况时间复杂度，所以冒泡排序的时间复杂度为 $O(n^2)$。

递归阶乘

long long Fac(size_t N) {
    if (0 == N) return 1;
    return Fac(N - 1) * N;
}

基本操作递归了 $N$ 次，所以 Fac 函数的时间复杂度为 $O(N)$。

斐波那契数列

long long Fib(size_t N) {
    if (N < 3) return 1;
    return Fib(N - 1) + Fib(N - 2);
}

看成一棵树，从渐近分析的角度，忽略常数系数，只关注输入规模 $N$ 增大时执行次数的增长趋势，Fib 函数的时间复杂度为 $O(2^N)$。

空间复杂度详解

概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大 O 渐进表示法。

值得注意的是：函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

常见示例计算

冒泡排序

除了输入的数组 a 外，只使用了有限个额外变量，像 end、exchange 和 i 这些变量。无论输入数组的规模 n 有多大，这些额外变量所占用的空间都是固定的，不会随着 n 的增长而增加。所以，冒泡排序算法的空间复杂度为 $O(1)$。

斐波那契数列

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;
}

函数内部使用 malloc 分配了一块连续的内存空间，用来存储斐波那契数列的前 $n$ 项，这块内存的大小是 $(n + 1) * sizeof(long long)$。所以动态开辟了 $N$ 个空间，空间复杂度为 $O(N)$。

递归阶乘

在递归调用过程中，每次调用函数 Fac 时，系统会为当前这次调用在栈上分配一定的空间。最深的递归调用层次达到了 $N$ 层。所以，根据空间复杂度的衡量规则，该函数的空间复杂度是 $O(N)$。

常见复杂度的对比

一些和时间复杂度有关的练习：

• 消失的数字 OJ
• 旋转数组 OJ

掌握这些基础概念，有助于我们在编码时做出更优的选择。建议结合代码多动手实践，加深理解。