# 时间复杂度与空间复杂度 ## 空间复杂度 一个算法的存储量包括形参所占空间和临时变量所占空间，在进行存储空间分析时，只考察临时变量所占空间。 ### 1、静态分析 一个算法静态使用的存储空间，称为静态空间。静态分析的方法比较容易，只要求算法中所使用的所有变量的空间，再折合成多少空间存储单位。 ### 2、动态分析 一个算法执行过程中，必须以动态方式分配的存储空间是指算法执行过程中分配的空间，称为动态空间。动态空间主要是存储中间结果或操作单元所占用空间。 原地工作并非不需要额外空间，只是说额外空间不随数据大小的增长而增长。 例如，以下算法中临时变量 `i`、`maxi` 占用的空间。所以，空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模 $n$ 的函数，以数量级形式给出，记作： $$ S(n)=O(g(n))、\Omega(g(n)) \text{ 或 } \Theta(g(n)) $$ 其中渐进符号的含义与时间复杂度中的含义相同。 ```c int max(int a[],int n) {int i,maxi=0; for (int i=1;ia[maxi]) maxi=i; return a[maxi]; } ``` 函数体内分配的变量空间为临时空间，不计形参占用的空间，这里的仅计 `i`、`maxi` 的空间，空间复杂度为 $O(1)$。 ```c void func(int n) { int i,k=100; while (i<=n) { k++; i+=2;} } ``` 临时分配了 `i`、`k` 两个变量的空间，它与问题规模 $n$ 无关，空间复杂度为 $O(1)$，即该算法为原地工作算法。 有如下递归算法，分析调用 `maxelem(a,0,n-1)` 的空间复杂度： ```c int maxelem(int a[],int i,int j) { int mid(i+j)/2,max 1,max2; if (imax2)?max1:max2; } else return a[i]; } ``` 每次调用只临时分配 3 个整型变量的空间（$O(1)$）。 调用 `maxelem(a,0,n-1)` 的空间为 $S(n)$，有 > $S(n)=O(1)$，当 $n=1$ > > $S(n)=2S(n/2)+O(1)$，当 $n>1$ $$ \begin{aligned} S(n)&=2S(n/2)+1\\ &=2[2S(n/2^2)+1]+1\\ &=2^2S(n/2^2)+1+2^1\\ &=2^3S(n/2^3)+1+2^1+2^2\\ &=\cdots\\ &=2^k S(n/2^k)+1+2^1+\cdots+2^{k-1}\\ &(\text{设 } n=2^k,\ k=\log_2 n)\\ &=n\cdot 1+2^k-1\\ &=2n-1\\ &=O(n) \end{aligned} $$ ## 一些函数 ### 单调性 - 单调递增：$m\le n$ 蕴含 $f(m)\le f(n)$ - 单调递减：$m\le n$ 蕴含 $f(n)\le f(m)$ - 严格递增：$m0$， $$ \lceil\lceil n/a\rceil/b\rceil=\lceil n/ab\rceil $$ $$ \lfloor\lfloor n/a\rfloor/b\rfloor=\lfloor n/ab\rfloor $$ $$ \lceil a/b\rceil\le (a+(b-1))/b $$ $$ \lfloor a/b\rfloor\ge (a-(b-1))/b $$ ### 取模运算 $$ a\bmod n=a-\lfloor a/n\rfloor\cdot n $$ $$ a\bmod n=b\bmod n,\quad a\equiv b\pmod n $$ $$ a\bmod n\ne b\bmod n,\quad a\not\equiv b\pmod n $$ 等价地，$a\equiv b\pmod n$ 当且仅当 $n$ 是 $b-a$ 的一个约数。 ### 多项式 给定一个正整数 $d$，$n$ 的 $d$ 次多项式是具有如下形式的函数 $p(n)$： $$ p(n)=\sum_{i=0}^{d}a_i n^i $$ $$ a_d\ne 0 $$ 一个多项式是渐进正的，当且仅当 $a_d>0$。 对于一个 $d$ 次的渐进多项式 $p(n)$，$p(n)=\Theta(n^d)$。 对于任意实常数 $a\ge 0$，$n^a$ 单调递增。 对于任意实常数 $a\le 0$，$n^a$ 单调递减。 ### 指数式 对于任意实数 $a$ 和 $b$，且 $a>1$。 ### 增长关系 $$ \lim_{x\to a}\frac{n^b}{a^n}=0 $$ 即 $$ n^b=o(a^n) $$ $$ \begin{aligned} &\text{对任意实数 }x\\ &&&e^{x}=1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\cdots=\sum_{i=0}^{\infty}\frac{x^{i}}{i!}\\ &&&\lim_{n\to\infty}\left(1+\frac{x}{n}\right)^{n}=e^{x}\\ &\text{当 }|x|\le 1\\ &&&1+x\le e^{x}\le 1+x+x^{2}\\ &\text{当 }x\to 0\\ &&&e^{x}=1+x+\Theta\left(x^{2}\right) \end{aligned} $$ 约定下列记号： $$ \lg n=\log_2 n $$ $$ \ln n=\log_e n,\quad \lg^k n=(\lg n)^k,\quad \lg\lg n=\lg(\lg n) $$ $|x|<1$： $$ \ln(1+x)=x-\frac{x^{2}}{2}+\frac{x^{3}}{3}-\frac{x^{4}}{4}+\frac{x^{5}}{5}-\cdots $$ 泰勒展开： $$ f(x)=f(0)+f'(0)x+f''(0)\left(\frac{x^2}{2}\right)+\cdots $$ 当 $x>-1$， $$ \frac{x}{x+1}\le \ln(1+x)\le x $$ 对于任意常数 $a>0$， $$ \lim_{n\to\infty}\frac{n^b}{a^n}=0 $$ 当 $(n=\lg n,\ a=2^a)$，$\lg^b n=o(n^a)$。 因此任意正多项式函数都比多项对数函数增长得快。 ### 阶乘 定义 $$ n!=\begin{cases} 1 & n=0\\ n\times (n-1)! & n>0 \end{cases} $$ 斯特林公式 $$ n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1+\Theta\left(\frac{1}{n}\right)\right) $$ 可以证明 $$ n!=o(n^n),\quad n!=\omega(2^n),\quad \lg(n!)=\Theta(n\lg n) $$ 对于任意 $n\ge 1$， $$ n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n e^{a_n}, $$ 其中 $$ \frac{1}{12n+1}0 \end{cases} $$ $$ f(n)=2n,\quad f^{(i)}(n)=2^i n $$ ### 多重对数函数 设 $\lg^{(i)}n$ 如上定义，其中 $f(n)=\lg n$，由于 $\lg^{(i)}n$ 有定义当且仅当 $\lg^{(i-1)}n>0$。 多重对数的定义为： $$ \lg^{*}n=\min\{i\ge 0:\lg^{(i)}n\le 1\} $$ 注意区分 $\lg^{(i)}n$ 和 $\lg^i n$。 多重对数函数是一种增长很慢的函数： $$ \lg^{*}2=1,\quad \lg^*4=2,\quad \lg^*16=3,\quad \lg^*65536=5,\quad \lg^*2^{65536}=6 $$ ### 递归定义 斐波那契数列和黄金分割率及其共轭数有关系，它们有如下关系： $$ F_0=0,\quad F_1=1,\quad F_i=F_{i-1}+F_{i-2} $$ $$ \phi=\frac{1+\sqrt{5}}{2} $$ $$ \hat{\phi}=\frac{1-\sqrt{5}}{2} $$ $$ F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}} $$ 即斐波那契数列以指数形式增长。 ## 算法分析技术 最坏情况和平均情况分析 ### 递归式 递归算法采用一种分而治之的方式，把一个大问题分解为若干个相似的小问题。 关键是根据递归过程建立递推关系式，然后求解这个递推关系式，得到一个表示算法执行时间的表达式，最后用渐进符号来表示这个表达式即得到算法的时间复杂度。 递归式就是一个等式，它通过通常更小的函数参数值来描述一个函数。 递归算法： ```c void mergesort(int a[],int i,int j) { int m; if (i!=j) { m=(i+j)/2; mergesort(a,i,m); mergesort(a,m+1,j); merge(a,i,j,m); } } ``` `mergesort()` 用于数组 `a[0...n-1]`（设 $n=2^k$，这里的 $k$ 为正整数）的归并排序。 调用该函数方式为 `mergesort(a,0,n-1)`。 `merge(a,i,j,m)` 用于两个有序子序列 `a[i...j]` 和 `a[j+1...m]` 的有序合并，是非递归函数，它的时间复杂度为 $O(n)$（$n=j-i+1$）。 设 `mergesort(a,0,n-1)` 的执行时间为 $T(n)$。 由其执行过程得到以下求执行时间的递归关系（递推关系式）： > $T(n)=O(1)$，当 $n=1$ > > $T(n)=2T(n/2)+O(n)$，当 $n>1$ 其中 $O(n)$ 为 `merge()` 所需的时间，设为 $cn$（$c$ 为正常量）。 $$ \begin{aligned} T(n)&=2T(n/2)+cn\\ &=2^2T(n/2^2)+2cn\\ &=2^kT(n/2^k)+kcn\\ &=nO(1)+cn\log_2 n \quad // \text{假设 } n=2^k\\ &=O(n\log_2 n) \end{aligned} $$ ## 一、从代码直接“看”出 $O$（最实用） 拿到一段代码，按这三个步骤走： ### 第 1 步：找“基本操作” 基本操作就是循环最内层里那些**一次就能做完的语句**（比较、赋值、自增等）。它们的单次代价都是 $O(1)$。 ### 第 2 步：数“循环嵌套层数” - 没有循环 → $O(1)$ - 一层循环（循环次数与 $n$ 成正比）→ $O(n)$ - 两层嵌套 → $O(n^2)$ - 三层嵌套 → $O(n^3)$ - $k$ 层嵌套 → $O(n^k)$ 注意：这里的前提是每一层循环的次数都**与 $n$ 成正比**。 ### 第 3 步：看循环变量有没有“减半” 如果每层循环的规模是**除以 2**（比如 `i = 1; i < n; i *= 2`），那循环层数对应的复杂度就不是 $n$ 而是 $\log n$。 ------ ### 举例：直接用眼睛看插入排序 ```text for j = 2 to n // 外层 n 次 key = A[j] i = j - 1 while i > 0 and ... // 内层最多 j 次 A[i+1] = A[i] i = i - 1 ``` - 外层：$n$ 次 - 内层：最多 $n$ 次（因为 $j$ 最大是 $n$，$i$ 从 $j-1$ 递减到 0） - 嵌套层数：2 层 所以整体最坏是 $O(n\times n)=O(n^2)$。 ------ ## 二、从公式直接“化简”到 $O$（数学规则） 如果表格已经给你写出了精确的 $T(n)$ 公式，你只需要执行下面这几条规则： ### 规则 1：去掉所有常数系数 $$ 3n^2\to n^2 $$ $$ \frac{n^2}{2}\to n^2 $$ $$ 7n\to n $$ ### 规则 2：只保留最高阶项 $$ n^2+n+1\to n^2 $$ $$ n^3+100n^2+5\to n^3 $$ ### 规则 3：常数项变成 $O(1)$ $$ 5\to O(1) $$ $$ 100\to O(1) $$ ### 规则 4：如果是 $\Theta$，上下界都要卡住 - $O$：只保留上界，只去掉低阶项和常数系数即可。 - $\Theta$：需要上下界都被最高阶项卡住，所以必须保证最高阶项的系数 $>0$（对于多项式）。 ------ ### 举个例子 假设你算出来： $$ T(n)=3n^2+5n+100 $$ 化简过程： 1. 去掉常数系数：$n^2+n+1$ 2. 只保留最高阶：$n^2$ 3. 加上记号：$\Theta(n^2)$ ------ ## 三、总结成一张“速查表” | 代码结构 | 直接判断的复杂度 | | ---------------------------------------- | ---------------- | | 无循环，几条赋值 | $O(1)$ | | 一层循环，循环 $n$ 次 | $O(n)$ | | 两层嵌套循环，每层 $n$ 次 | $O(n^2)$ | | 三层嵌套循环，每层 $n$ 次 | $O(n^3)$ | | 一层循环，每次规模减半 | $O(\log n)$ | | 一层循环 $n$ 次，里面套一个规模减半的循环 | $O(n\log n)$ | | 两层嵌套，外层 $n$ 次，内层最多 $n$ 次 | $O(n^2)$ | | 公式 | 化简结果 | | ----------------------------- | ---------------------------- | | $an^2+bn+c$（$a>0$） | $\Theta(n^2)$ | | $an+b$（$a>0$） | $\Theta(n)$ | | $a\log n+b$ | $\Theta(\log n)$ | | $c$ | $\Theta(1)$ | | $n\log n+n$ | $\Theta(n\log n)$ | | $2^n+n^{100}$ | $\Theta(2^n)$（指数增长更快） | ------ ## 四、一句话总结 **从表格到 $O$ 的判断逻辑是：** 1. 先数循环嵌套层数，直接猜出“最高阶项的形式”。 2. 再用公式化简规则，把低阶项和常数系数扔掉。 3. 最后套上 $O$ 或 $\Theta$。 掌握了这个，你就不需要每次都把 $T(n)$ 完整展开再算了，看到代码就能直接报出复杂度。