数据结构初阶：时间与空间复杂度解析
数据结构的重要性不言而喻，无论是面试还是实际工作，面对海量数据或复杂逻辑关系时，巧妙运用数据结构能梳理问题脉络，找到简洁的解题思路。
什么是数据结构与算法？
数据结构指相互之间存在一种或多种特定关系的数据元素的集合。简单来说，就是组织和存储数据的方式，让数据能被高效地访问、修改、增删。就好比把杂乱的物品用不同的收纳工具和方法归置整齐。
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。它接收特定的输入，经过有限个步骤的处理，产生对应的输出。打个比方，算法就像是一份精准的菜谱，食材是输入，按照菜谱上的步骤烹饪后得出的菜肴就是输出。
如何学好算法和数据结构？
数据结构偏向于底层逻辑，学习重要的不是学了很多，而是对于每个数据的代码，都知道为什么这么写。
- 时常问问自己为什么这里的代码这样写
- 多画图梳理逻辑
- 多写几遍代码
- 和不会的问题死磕到底，钻研不出来就问人
算法效率评估
如何判断一个算法的好坏，主要从时间和空间来考量。算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，存储容量很小，所以对空间复杂度很是在乎。如今存储容量已很高，我们通常更关注时间复杂度，但空间复杂度依然重要。
时间复杂度详解
概念
在计算机科学中，算法的时间复杂度是一个函数，定量描述了该算法的运行时间。理论上无法直接算出程序运行的确切时间，只有上机测试才知道。但这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
举个例子，计算 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^2$ 次，接着一次循环执行 $2N$，最后执行 10 次。
大 O 的渐进表示法
确定基本操作：找出其中最核心、执行次数最多，且对整体运行时间起关键影响的基本操作。例如在排序算法里，元素比较、交换的操作；在搜索算法中，是数据元素的查看操作。
分析操作执行次数：设输入规模为 $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)$。
常见复杂度的对比
一些和时间复杂度有关的练习：
掌握这些基础概念，有助于我们在编码时做出更优的选择。建议结合代码多动手实践，加深理解。