时间复杂度

1. 含义

1. 算法在特定输入下的运行时间：指执行的基本操作数或步数
2. 时间复杂度是定性描述该算法运行时间的函数，可以用来估计该算法的运行时间
3. 当输入规模足够大的时候，这个函数的低阶项和最高阶项的常数项对函数值的影响相较于最高阶项指数对函数值的影响来说可以忽略不计，也就是说只对运行时间的次数做描述

2. 渐进记号

渐进记号描述函数的增长趋势。五个渐进记号如下：

2.1. 定义

1. $\mathrm{\Theta }(g(n))=\{f(n)|\mathrm{\exists }{c}_1,c_2,n_0>0,\mathrm{\forall }n\ge n_0,0\le c_{1}g(n)\le f(n)\le c_{2}g(n)\}$
2. $O(g(n))=\{f(n)|\mathrm{\exists }c,n_0>0,\mathrm{\forall }n\ge n_0,0\le f(n)\le cg(n)\}$
3. $\mathrm{\Omega }(g(n))=\{f(n)|\mathrm{\exists }c,n_0>0,\mathrm{\forall }n\ge n_0,0\le cg(n)\le f(n)\}$
4. $o(g(n))=\{f(n)|\mathrm{\forall }c>0,\mathrm{\exists }{n}_0>0,\mathrm{\forall }n\ge n_0,0\le f(n)<cg(n)\}$
5. $\omega (g(n))=\{f(n)|\mathrm{\forall }c>0,\mathrm{\exists }{n}_0>0,\mathrm{\forall }n\ge n_0,0\le cg(n)<f(n)\}$

等号代替属于

为了方便，当 $f(n)\in O(g(n))$ 时，记作 $f(n)=O(g(n))$。

可以更快速地用极限定义：

1. $$f(n)\in \mathrm{\Theta }(g(n))\iff \underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=C$$
2. $$f(n)\in O(g(n))\iff \underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=0\mathrm{或}C$$
3. $$f(n)\in \mathrm{\Omega }(g(n))\iff \underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=\mathrm{\infty }\mathrm{或}C$$
4. $$f(n)\in o(g(n))\iff \underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=0$$
5. $$f(n)\in \omega (g(n))\iff \underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=\mathrm{\infty }$$

其中 $C$ 是一个正常数。

2.2. 性质

2.2.1. 传递性

1. $f(n)=\mathrm{\Theta }(g(n))\wedge g(n)=\mathrm{\Theta }(h(n))\Rightarrow f(n)=\mathrm{\Theta }(h(n))$
2. $f(n)=O(g(n))\wedge g(n)=O(h(n))\Rightarrow f(n)=O(h(n))$
3. $f(n)=\mathrm{\Omega }(g(n))\wedge g(n)=\mathrm{\Omega }(h(n))\Rightarrow f(n)=\mathrm{\Omega }(h(n))$
4. $f(n)=o(g(n))\wedge g(n)=o(h(n))\Rightarrow f(n)=o(h(n))$
5. $f(n)=\omega (g(n))\wedge g(n)=\omega (h(n))\Rightarrow f(n)=\omega (h(n))$

2.2.2. 自反性

1. $f(n)=\mathrm{\Theta }(f(n))$
2. $f(n)=O(f(n))$
3. $f(n)=\mathrm{\Omega }(f(n))$

2.2.3. 对称性和转置对称性

1. $f(n)=\mathrm{\Theta }(g(n))\iff g(n)=\mathrm{\Theta }(f(n))$
2. $f(n)=O(g(n))\iff g(n)=\mathrm{\Omega }(f(n))$
3. $f(n)=o(g(n))\iff g(n)=\omega (f(n))$

2.3 渐进记号的运算规则

2.3.1 加法规则

如果 $f_1(n)=O(g_1(n))$ 且 $f_2(n)=O(g_2(n))$，则：

$$f_1(n)+f_2(n)=O(max\{g_1(n),g_2(n)\})$$

例子：$3n^2+5n+1=O(n^2)+O(n)+O(1)=O(n^2)$

2.3.2 乘法规则

如果 $f_1(n)=O(g_1(n))$ 且 $f_2(n)=O(g_2(n))$，则：

$$f_1(n)\cdot f_2(n)=O(g_1(n)\cdot g_2(n))$$

例子：$n\log n\cdot n=O(n\log n)\cdot O(n)=O(n^2\log n)$

2.3.3 幂次规则

如果 $f(n)=O(g(n))$ 且 $k>0$，则：

$$[f(n){]}^k=O([g(n){]}^k)$$

3. 时间复杂度的表示

1. 时间复杂度可以用渐进记号表示，最常用的是大 O 记号。
2. 大多数情况下，我们只关注算法的最坏情况运行时间：
   1. 对大部分算法来说，最坏情况经常出现；
   2. 平均情况运行时间很可能等于最坏情况运行时间；
   3. 有例外，比如快速排序。

4. 例子

1. 常数时间复杂度：$\mathrm{\Theta }(1)$。

   如果一个算法的执行时间不随输入规模 $n$ 的变化而变化，那么该算法的时间复杂度为 $\mathrm{\Theta }(1)$。例如，访问数组中的单个元素 A[i]，或者执行一次加法运算。

   常数时间复杂度 $\mathrm{\Theta }(1)$ 也可写成 $\mathrm{\Theta }(n^0)$。（为什么？）

2. 线性时间复杂度：$\mathrm{\Theta }(n)$。

   如果一个算法需要遍历一次输入数据，其时间复杂度通常是线性的。例如，在一个大小为 $n$ 的数组中查找最大值：

   int findMax(int arr[], int n) {
       int max_val = arr[0];
       for (int i = 1; i < n; i++) {
           if (arr[i] > max_val) {
               max_val = arr[i];
           }
       }
       return max_val;
   }

   在这个例子中，for 循环执行了 $n-1$ 次。循环体内的操作（比较和可能的赋值）都是常数时间的。因此，总的运行时间与 $n$ 成正比，记为 $\mathrm{\Theta }(n)$。

3. 二次时间复杂度：$\mathrm{\Theta }(n^2)$。

   一个典型的例子是简单的排序算法，如冒泡排序，它包含嵌套循环。

   void bubbleSort(int arr[], int n) {
       for (int i = 0; i < n - 1; i++) {
           for (int j = 0; j < n - i - 1; j++) {
               if (arr[j] > arr[j + 1]) {
                   swap(arr[j], arr[j + 1]);
               }
           }
       }
   }

   外层循环执行 $n-1$ 次，内层循环的执行次数依赖于外层循环的迭代变量 $i$。在最坏情况下（数组完全逆序），总的比较和交换次数约为 $\frac{(n-1)n}{2}$，这是一个关于 $n$ 的二次多项式 $a{n}^2+bn+c$。根据时间复杂度的定义，我们忽略低阶项和常数系数，因此时间复杂度为 $\mathrm{\Theta }(n^2)$。

4. 函数的增长不一定能比较：

   考虑 $f(n)=n$ 和 $g(n)=n^{1+\sin n}$。为什么此时 $f(n)=O(g(n))$ 和 $f(n)=\mathrm{\Omega }(g(n))$ 不成立？

   因为函数 $\sin n$ 的值在 $[-1,1]$ 之间周期性震荡：

   • 当 $\sin n\to 1$ 时（例如 $n\approx 2k\pi +\frac{\pi }{2}$），$g(n)\approx n^2$。在这种情况下，$g(n)$ 的增长速度远于 $f(n)$
   • 当 $\sin n\to -1$ 时（例如 $n\approx 2k\pi +\frac{3\pi }{2}$），$g(n)\approx n^0=1$。在这种情况下，$g(n)$ 增长速度远慢于 $f(n)$。

   因为 $f(n)$ 和 $g(n)$ 的增长速度关系不断变化，无法找到一个从 $n_0$ 开始一直成立的上下界关系，所以两者无法用 $O$ 或 $\mathrm{\Omega }$ 号进行比较。

5. 阶乘的对数：$\lg (n!)=\mathrm{\Theta }(n\lg n)$

   • 上界证明: 由 斯特林公式，$\lg (n!)\approx \lg (\sqrt{2\pi n}(\frac{n}{e}{)}^n)=\lg (\sqrt{2\pi n})+n\lg (n)–n\lg (e)$。又因为 $\lg (\sqrt{2\pi n})$ 和 $-n\lg (e)$ 均可视为较 $n\lg (n)$ 小的项，所以 $\lg (n!)=O(n\lg n)$。

   • 下界证明:

     在阶乘的展开式 $n!=1\times 2\times \cdots \times n$ 中，后一半的项（从 $\lceil \frac{n}{2}\rceil$ 到 $n$）共有 $n-\lceil \frac{n}{2}\rceil +1\ge \frac{n}{2}$ 项，并且每一项都大于等于 $\frac{n}{2}$。因此，它们的乘积 $n!\ge (\frac{n}{2}{)}^{\frac{n}{2}}$。

     两边取对数，得 $\lg (n!)\ge \frac{n}{2}\lg (\frac{n}{2})=\frac{n}{2}(\lg n-\lg 2)=\frac{1}{2}n\lg n-\frac{n}{2}$。

     根据定义，存在常数 $c$ (例如 $c=\frac{1}{4}$），当 $n$ 足够大时，有 $\frac{1}{2}n\lg n-\frac{n}{2}\ge c\cdot n\lg n$。

     因此，$\lg n!=\mathrm{\Omega }(n\lg n)$。

   • 结论：由上界和下界证明可得，$\lg n!=\mathrm{\Theta }(n\lg n)$。

$\ln$ 的底数呢？

经常有人疑惑 $\mathrm{\Theta }(n)=\lg n$ 中 lg 的底数是多少；
对数的底数是几无关紧要，因为：根据换底公式，不同底数的对数之间只差一个常数，而计算时间复杂度的时候不考虑常数。

5. 空间复杂度

5.1 定义

算法的空间复杂度指该算法执行过程中所需要消耗的存储空间资源（不要把输入数据所占的存储空间包括在内）。

5.2 表示方法

与时间复杂度表示方法相同。

习题

1. 20301 [3.3M] 根据增长速度排序以下函数。

   $$1$$$$n$$$$n^2$$$$n^3$$$$n!$$$$(\lg n)!$$$${\lg }^{2}n$$$$\lg (n!)$$$$2^{2^n}$$$$n^{\frac{1}{\lg n}}$$$$\lg \lg n$$$$n^{\lg \lg n}$$$$\lg n$$$$2^{\lg n}$$$$(\lg n{)}^{\lg n}$$$$\sqrt{\lg n}$$$$2^{\sqrt{\lg n}}$$$$2^n$$$$n\lg n$$

2. 20302 [1.1] 秦九韶算法是一种求解多项式的值的方法。

   对于系数 $a_0,a_1,a_2,\dots ,a_n$，多项式 $P(x)=a_0+a_{1}x+a_2{x}^2+\cdots +a_n{x}^n$ 的值可以如下计算：

   $$P(x)=((a_{n}x+a_{n-1})x+\cdots +a_1)x+a_0$$

   (1) 写出秦九韶算法的时间复杂度。 (2) 如果依次计算多项式的每一项，最后求和，写出时间复杂度。