1. 空间复杂度
根据摩尔定律，晶体管数量增加导致内存成本降低，但编程时仍需注意空间浪费问题。
空间复杂度是一个数学表达式，用于衡量算法在运行过程中额外临时开辟的空间。它不是程序占用的字节数，而是计算变量的个数。空间复杂度的计算规则与时间复杂度类似，使用大 O 渐进表示法。
函数运行时所需的栈空间（存储参数、局部变量等）在编译期间已确定，因此空间复杂度主要通过函数运行时显式申请的额外空间来确定。
例如冒泡排序代码：
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;
}
}
上述代码中，for 循环定义的局部变量 end、exchange 和 i 都在栈上。虽然不同系统上整型占用空间不同，但依据大 O 阶规则，空间复杂度为 O(1)。
示例：计算阶乘递归 Fac 的空间复杂度
long long Fac(size_t N) {
if (N == 0)
return 1;
return Fac(N - 1) * N;
}
空间复杂度关注函数体是否申请额外空间。Fac(N) 调用会创建函数栈帧，直到 N=0。此过程需要额外的 N 个空间，空间复杂度为 O(N)。在此递归中，空间和时间复杂度表现一致。
2. 常见复杂度对比
随着 n 的增加，logn 的变化趋势最小。变化快慢的排序（从慢到快）为：logn、n、nlogn、n²、2ⁿ、n!。logn 复杂度最优，往后依次递减。
有了复杂度概念，可以在编写程序之前评估性能，并通过题目练习快速计算复杂度。
3. 复杂度算法题
3.1 旋转数组
解法一
暴力循环解法：
