1. 相关概念
算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源，所以其指标也分为时间复杂度和空间复杂度。
评估一个算法的复杂度，又有三种情况下的指标，分别为最好情况、最坏情况、平均情况。我们通常只关心最坏情况下的复杂度。因为
- 一个系统好坏往往只取决于最坏的情况。最好情况代表系统的上限，但往往没有多大的参考意义。而最坏情况是一种保证指标，代表系统的下限，参考意义较大。
- 平均情况是一种期望指标，这个指标有时候并不能很直接的给出来。
- 在一个复杂的集合中，数据往往都趋向于最坏情况，而平均情况往往也会趋同于最坏情况。
时间频度记为 \(T(n)\) ，空间频度记为 \(S(n)\) ，这里面的n表示问题的规模情况，对于规模足够大的算法，我们只关心其位阶的情况，于是使用大O表示法，统一记为 \(O(f(n))\) 。这种计数法的特点是，忽略每一项的常数系数，如果存在多个位阶的未知项时，只保留最大位阶的那一项。
\(O(f(n))\) 表示一个函数的渐进上界，即存在正常量 \(c\) 和 \(n_0\) ，对所有的 \(n \ge n_0\) ，都有 \(0 \le O(f(n)) \le cf(n_0)\)
另外还有 \(\Omega\) 表示渐进下界， \(O\) 表示非渐进明确的上界，\(\omega\) 表示非渐进明确的下界，但这些符号用的比较少，这里就不详细提及了。
对于一个算法的时间和空间的资源消耗的影响包括软硬件差别和代码执行次数，而软硬件的消耗基本是一个固定值，可以当做一个常量，所以大O表示法只与代码执行次数有关。
一般的，常见的复杂度的大小比较如下：
\(O(1)\) 常数阶 < \(O(\log_2 n)\) 对数阶 < \(O(n)\) 线性阶 < \(O(n\log_2 n)\) 线性对数阶 < \(O(n^2)\) 平方阶 < $ O(n^3)$ 立方阶 < \(O(2^n)\) 指数阶
2. 时间复杂度
一般算法的设计，对于时间复杂度的研究比较困难和复杂，所以，一般都只关注时间复杂度，也一般把时间复杂度简写为复杂度。
2.1. 循环
循环结构的时间复杂度都是下面几个常见的固定值中的一个，一般都可以直接从循环体中判断出来。
循环体常见的时间复杂度的一般格式如下：
2.1.1. \(O(1)\)
没有任何循环体或只循环一次的代码的时间复杂度就是 \(O(1)\)
def func():
operate()2.1.2. \(O(n)\)
一层循环嵌套且增长条件为加法增加的代码的时间复杂度都是 \(O(n)\)
def func(low, high, step):
for i in range(low, high, step):
operate()这里，step 可以为任意值。
设 \(step = 2\) ，其执行循环体总次数为 \(s = \frac{1}{2} n\) ，系数项可以忽略，所以其时间复杂度仍然为 \(O(n)\)
2.1.3. \(O(\log n)\)
一层循环嵌套且增长条件为乘法增加的代码的时间复杂度都是 \(O(\log n)\)
def func(n, start, factor):
i = start
while i < n:
operate()
i *= factor这里，虽然 \(O(\log n)\) 中的 \(\log n\) 是以2为底的对数的简写，但实际上 factor 是可以为任意值的。
设 \(\text{factor}=3\) ，其执行循环体总次数为 \(s = \log_3 n = \log_2 3 \cdot \log_2 n\) ，系数项可以忽略，所以其时间复杂度仍然为 \(O(\log_2 n)\)
2.1.4. \(O(n^2)\)
两层循环嵌套且增长条件为加法增加的代码的时间复杂度都是 \(O(n^2)\)
def func(low, high, step):
for i in range(low, high, step):
for j in range(low, high, step):
operate()这里，两层循环的次数是可以不相等的。
设两层循环的次数分别为 \(n_1\) 、\(n_2\)，其执行循环体总次数为 \(s = n_1 n_2 = n_1 (n_1 + C) = n_1 ^2 + Cn_1\) ，只取位阶最大的部分，所以其时间复杂度仍然为 \(O(n^2)\)
另外，下面循环形式的代码的时间复杂度也为 \(O(n^2)\)
def func(n):
for i in range(n):
for j in range(i, n):
operate()其执行循环体总次数为 \(n + (n-1) + (n - 2) + ... + 1\)，这其实就是一个等差数列，所以其时间复杂度仍然为 \(O(n^2)\)
特别地，我们可以推广至一般情形： x 个时间复杂度为 \(O(n)\) 的代码嵌套，其时间复杂度为 \(O(n^x)\)；时间复杂度为 \(O(n)\) 和 \(O(\log n)\) 的代码嵌套，其时间复杂度为 \(O(n \log n)\)
2.2. 递归
对于递归表达式 \[ F(n)= f(n)+G(n) \] 可以得到其时间复杂度关系式 \[ T(n) = O(f(n))+T(G(n)) \] 可以用以下方法算出上面关系式的时间复杂度
2.2.1. 直接法
针对 \(f(n)=0\) ，直接使用下面公式 \[ T(n) = \text{递归体的次数} * \text{每次递归体执行的次数} \]
2.2.2. 代入法
按照自身的经验，对这个问题的时间复杂度做出预测，然后将预测带入原来的递归方程，如果没有出现矛盾，则是可能的解，最后用数学归纳法证明。
举例说明
对于递归问题 \(T(n) = 4T(\frac{n}{2}) + O(n)\) ，猜测 \(T(n) = kn^2\) ，k为任意常数，则有 \[ 左 = T(n)=kn^2 \\ 右 = 4T(\frac{n}{2}) + O(n) = 4k(\frac{n}{2})^2 + O(n) = kn^2 + O(n) \] 由于右边 \(O(n)\) 的阶比 \(n^2\) 的阶小，所以可以去掉，所以左右两边是相等的，后面再用数学归纳法验证即可。
2.2.3. 迭代法
针对具有初始条件 \(F(n_0)\) 的任意递归关系式，对递归关系式进行展开，直至展开到其初始条件，然后进行化简合并计算，最后只剩关于n的函数式，从而得到 \(O(f(n))\) ，但这种方法虽然是万金油，但比较笨重，不一定可以找到规律，所以并不是很推荐。
举例说明
现在有一递归关系式为 \[ T(n) = 2T(\frac{n}{2}) + n^2 \] 其中初始状态为 \(T(0) = 1\)
推导过程如下 \[ \begin{aligned} T(n) &= n^2 + 2T(\frac{n}{2}) \\ &= n^2 + 2((\frac{n}{2})^2+2T(\frac{n}{4})) \\ &= n^2 + 2((\frac{n}{2})^2+ \dots + 2((\frac{n}{2^i})^2+T(\frac{n}{2^{i+1} }))) \\ &= \sum_{i=0}^{\log n} 2^{i} \cdot \frac{n^2}{ {2i}^2} \\ &= n^2 \sum_{i=0}^{\log n} {\frac{1}{2^i} } \end{aligned} \] 故时间复杂符为 \(O(n^2)\)
2.2.4. 公式法
针对递归关系式为 \[ T(n) = aT(\frac{n}{b}) + O(f(n)) \] 我们有如下规律求其时间复杂度 \[ T(n) = \left \{ \begin{array}{ll} O(n^{\log_b a}) &O(n^{\log_b a}) > O(f(n)) \\ O(f(n) \cdot \log n) &O(n^{\log_b a}) = O(f(n)) \\ O(f(n)) &O(n^{\log_b a}) < O(f(n)) \end{array} \right . \] 上述公式实际上是比较\(n^{\log_b a}\)和\(f(n)\)的阶，如果他们不等，那么\(T(n)\)取他们中的较大者，如果他们的阶相等，那么我们就将他们的任意一个乘以\(\log n\)就可以了。
特别地，当 \(f(n) = 0\) 时，有如下规律 \[ T(n) = \left \{ \begin{array}{ll} O(n^{\log_b a}) & a \neq 1 \\ O(\log n) & a = 1 \end{array} \right . \]
另外，严格来说，上述公式还得加一个限制条件才能生效，即当 \(O(n^{\log_b a})\) 大于/小于 $O(f(n)) $ 且 \(n^{\log_b a}\) 大于/小于 \(f(n)\) 时，公式才生效。但实际应用中，复杂度指标往往只会用于规模较大的算法，所以后面的限制条件可以忽略。
2.2.5. 差分法
针对递归关系式为 \[ T(n) = \sum_{i=1}^{k} a_i T(n-i) + f(n) \] 其中， \(a_i(1 \le i \le k)\) 为常数，初始状态 \([T(0), T(1), \dots , T(n-k)] = [b_0, b_1, \dots , b_{n-k}]\)
上式是一个典型的非齐次差分方程，直接求解差分方程即可求出递归形式的时间复杂度。
为了表述方便，将上式转换为 \[ \sum_{i=0}^{k} a_i T(n-i) = f(n) \] 下面不加证明地给出古典法求解差分方程的过程
另外还有Z变换求解差分方程，感兴趣的可自行查找相关资料。
通解
上式对应的齐次方程为 \[ \sum_{i=0}^{k} a_i T(n-i) = 0 \] 对应的特征方程为 \[ \sum_{i=0}^{k} a_i r^{k-i} = 0 \] 求得特征根解系 \(\vec{r}=[r_1, r_2, \dots , r_k]\)
若无重根，即 \(r_1 \ne r_2 \ne \dots \ne r_k\) ，则通解为 \[ h(n) = \sum_{i=1}^k c_i(r_i)^n \] 否则通解为 \[ h(n) = \sum_{i=1}^k c_i \cdot n^{i-1} \cdot (r_i)^n \] 其中， \(c_i\) 为未知变量
特解
特解 \(t(n)\) 通过查表形式获得，又因为在这里我们不关心复数和三角函数情况，所以下面去掉了复数和三角函数的部分。
\(f(n)\) 的形式 特解 \(t(n)\) 的形式 \(A\) \(d\) \(n^k\) \(\sum_{i=0}^k d_i n^i\) \(r^n\) \(d \cdot r^n\) \(r^n(r与特征根重)\) \(d_1 n r^n + d_2 r^n\) 将对应的特解代入原方程 \(T(n)\) 中即可求出未知变量 \(d\)，继而求得特解 \(t(n)\)
全解 \[ T(n) = h(n) + t(n) \] 代入初始状态，求解其中的未知变量 \(c_i\) ，即可得出其全解。
举例说明
现在有一递归关系式为 \[ T(n) = T(n-1) + T(n-2) + 8 \] 其中初始状态为 \([T(0), T(1)] = [2, 3]\)
通解
对应的其次方程为 \[ r^2-r-1=0 \] 求得非重根 \([r_1, r_2 ] = [\frac{1-\sqrt{5}}{2}, \frac{1+\sqrt{5}}{2}]\)，故其通解为 \[ h(n) = c_1(\frac{1-\sqrt{5}}{2})^n + c_2(\frac{1+\sqrt{5}}{2})^n \]
特解
\(f(n)\) 为常量，查表可得，特解形式为 \(d\)，代入原递归式中可得 \[ d = d+d+8 \] 解得 \(t(n) = d=-8\)
全解 \[ T(n) = c_1(\frac{1-\sqrt{5}}{2})^n + c_2(\frac{1+\sqrt{5}}{2})^n -8 \] 代入初始条件 \([T(0), T(1)] = [2, 3]\) ，求解得到 \([c_1, c_2] = [\frac{5-6\sqrt{5}}{5},\frac{5+6\sqrt{5}}{5}]\)
其实这里有个偷懒的小技巧，复杂度只关心最大的一项，所以只要我们能保证最大那一项的系数不为0，求解未知系数这一步可以略过~
故这个递归关系式的时间复杂度为 \(O((\frac{1+\sqrt{5}}{2})^n )\)
注：
如果是使用递归树方法计算，算出来的时间复杂度是 \(O(2^n)\)，但两者都是正确的。因为大O表示法只是表示一个渐进上界，只是 \(O(2^n)\) 这个上界比 \(O((\frac{1+\sqrt{5}}{2})^n )\) 更加宽松罢了
2.2.6. 母函数法
针对递归关系式为 \[ T(n) =F(n, n-1, n-2, ... , n-k) + f(n) \] 其中，初始状态 \([T(0), T(1), \dots , T(n-k)] = [b_0, b_1, \dots , b_{n-k}]\)
下面不加证明的给出使用母函数求解复杂度的推导过程
上式对应的母函数为 \[ G(x) = \sum_{i=0}^n T(i)x^i \] 代入初始条件和递归关系式，求解得到 \(G(x) = g(x)\)，然后，我们对 \(g(x)\) 进行泰勒展开成一个多项式，合并化简运算后，\(x^n\)对应的系数项就是 \(T(n)\) 的表达式。
这个方法的难点在于，你没有一个通用的公式，你只能靠自身的经验化简得到一个易于泰勒展开的函数式，所以并不一定所有情况下都能奏效。
附：一些常见的泰勒展开式如下 \[ \begin{aligned} e^x &= \sum_{i=0}^n \frac{x^i}{i!} \\ \ln(1+x) &= -\sum_{i=1}^n \frac{(-x)^i}{i} \\ \sin x &= \sum_{i=0}^n \frac{(-1)^i x^{2i+1}}{(2i+1)!} \\ \cos x &= \sum_{i=0}^n \frac{(-1)^i x^{2i}}{(2i)!}\\ \arcsin x &= x + \sum_{i=1}^n \frac{\prod_{j=1}^{i} (2j-1)}{\prod_{j=1}^{i} 2j} \frac{x^{2i+1}}{2i+1} \\ \frac{1}{1-x} &= \sum_{i=0}^n x^i \\ (1+x)^a &= 1 + \sum_{i=1}^n \frac{\prod_{j=0}^{i-1} a-j}{i!} x^i \end{aligned} \] 举例说明
现有一递归关系式 \[ T(n) = T(n-1)+T(n-2) \] 其中，初始条件为 \([T(0), T(1)] = [0, 1]\)
其母函数为 \[ G(x) = \sum_{i=0}^n T(i)x^i \] 代入初始条件和递归关系式运算，有 \[ \begin{aligned} G(x) &= 0+1 \cdot x + \sum_{i=2}^{n} [T(i-1) + T(i-2)]x^{i} \\ &= x + (x^2 + x)G(x) \end{aligned} \] 可得 \[ \begin{aligned} G(x) &= \frac{x}{1-x-x^2} \\ &= \left(-\frac{1-\sqrt{5}}{2\sqrt 5} \cdot \frac{1}{1-\frac{1-\sqrt{5}}{2}x} + \frac{1+\sqrt{5}}{2\sqrt 5} \cdot \frac{1}{1-\frac{1+\sqrt{5}}{2}x}\right)x \\ &= \left[-\frac{1-\sqrt{5}}{2\sqrt 5} \cdot \sum_{i=0}^n (\frac{1-\sqrt{5}}{2}x)^i + \frac{1+\sqrt{5}}{2\sqrt 5} \cdot \sum_{i=0}^n (\frac{1+\sqrt{5}}{2}x)^i\right]x \\ &= \frac{1}{\sqrt{5}}\sum_{i=1}^{n+1} \left[(\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i\right]x^i \end{aligned} \] 可得 \[ T(n) = \frac{1}{\sqrt{5}} [(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n] \] 故该递归关系式的时间复杂度为 \(O((\frac{1+\sqrt{5}}{2})^n )\)
附：一些常见递归的时间复杂度如下
时间复杂度关系式 时间复杂度 举例 \(T(n) = O(1) + T(\frac{n}{2})\) \(T(n)=O(\log n)\) 二分查找、欧几里得GCD \(T(n)=O(1)+T(n-1)\) \(T(n)=O(n)\) 线性查找 \(T(n)=O(1)+2T(\frac{n}{2})\) \(T(n)=O(n)\) \(T(n) = O(n)+2T(\frac{n}{2})\) \(T(n)=O(n\log n)\) 归并排序、快速排序 \(T(n)=O(n\log n) + 2T(\frac{n}{2})\) \(T(n)=O(n \log ^ 2 n)\) \(T(n)=O(n^2) + 2T(\frac{n}{2})\) \(T(n)=O(n^2)\) \(T(n)=O(n)+T(n-1)\) \(T(n)=O(n^2)\) 选择排序、插入排序 \(T(n)=O(1)+2T(n-1)\) \(T(n)=O(2^n)\) 汉诺塔 \(T(n)=O(1)+T(n-1)+T(n-2)\) \(T(n)=O((\frac{1+\sqrt{5}}{2})^n )或 O(2^n)\) 斐波那契数列
3. 空间复杂度
对于一个合格的算法，其空间复杂度应小于 \(O(n^2)\) ，因为不同于时间，内存空间是有限，不可能成一个大倍数增长。
一个算法，如果创建了一个 \(n \times n\) 的矩阵，那么其空间复杂度为 \(O(n^2)\) ；如果创建了常数个集合，那么其空间复杂度为 \(O(n)\)；如果使用了树形结构，则大部分情况下是 \(O(\log n)\)；其他的，基本就是 \(O(1)\) 了。
因为空间复杂度实际应用得比较少，而且大多是一些概念性的东西，我也暂时没想到要补充些什么内容，所以这部分的内容就到这里了。
4. reference
https://www.itdaan.com/blog/2011/12/09/dfdf81588ef1fdcf9f89dbbac08c4ac7.html
Have a nice day~
