算法复杂度分析

这一部分的内容可以说是最重要但是我最薄弱的一部分了。重要的原因在于每次面试都会碰到，从大陆找互联网实习面试，到目前在HK很惨淡的找technology for finance实习的面试，到大四卓工保研面试。为什么说我很薄弱呢？因为70%我都是算错或者不会算。

算法复杂度分析可以分为时间复杂度分析和空间复杂度分析。所有的讨论都基于通用输入空间/规模(general input space)为n为前提。

算法复杂度分析的是最坏的情况。

算法时间复杂度分析

一个语句的频度是指该语句在算法中被重复执行的次数。

算法中所有语句的频度之和记为$T(n)$，即为算法的时间复杂度。

时间复杂度主要分析$T(n)$的数量级。算法中最深层循环中的语句被称为基本运算。所以我们在计算算法时间复杂度时，只关注最深层循环中的语句执行次数即可。

渐进分析

渐近分析是一种分析算法时间复杂度$T(n)$的方式：忽略$T(n)$的系数和低阶项，仅关注高阶项。

例如，$T(n)=2n^2+3n-4=O(n^2)=\theta (n^2)=\Omega(n^2)$

有三种渐近分析记号：

• $\theta(g(n))$：渐近紧确界，表示所有满足条件的函数$T(n)$的集合。$\theta(g(n))={T(n): \exist \ c_1,c_2,n_0>0,\ such\ that \ c_1 \times g(n) \leq T(n) \leq c_2 \times g(n) \ for \ all \ n \geq n_0}$。
• $O(g(n))$：渐近上界，表示所有满足条件的函数$T(n)$的集合。$O(g(n))={T(n): \exist \ c,n_0>0,\ such\ that \ 0 \leq T(n) \leq c \times g(n) \ for \ all \ n \geq n_0}$。
• $\Omega(g(n))$：渐近下界，表示所有满足条件的函数$T(n)$的集合。$\Omega(g(n))={T(n): \exist \ c,n_0>0,\ such\ that \ T(n) \geq c \times g(n) \ for \ all \ n \geq n_0}$。

上述表示方法中，$g(n)$都是一致的，都是忽略$T(n)$的系数和低阶项，仅关注高阶项。

为什么渐近上界$O(g(n))$更常见？

常见的渐进时间复杂度为（以$ O(g(n)) $为例）：

如何计算时间复杂度？

我认为程序类型可以分为两种：
有循环的程序（例如，$for$循环和$while$循环）和无循环的程序。

第一步：寻找基本操作。

循环程序

我们需要根据循环终止条件和循环变量的操作计算时间复杂度（一般是循环变量的操作次数）。

1
2
3
4
5
6
7
8

int i=0;
for (i=0; i<n; i=i+1) {
    // write your code here
}
i=0;
while(i<n) {
    i = i+1;
}

在上述$for$循环的结构中，循环终止条件判断指的是$i<n$，循环变量的操作指的是$i=i+1$。在$while$循环中，循环终止条件判断指的是$i<n$，循环变量的操作指的是$i=i+1$。

设基本运算的执行次数为$t$（在$for$和$while$循环中，基本运算都是循环变量的操作）。在每次基本操作中，循环变量$i$都$+1$。所以在t次操作之后，循环变量的值变为$i=t1$，我们再看循环终止条件$i<n$，代入可以得到$i=t1<n$，即$t<n$。

所以，$\textbf{T(n)=t=O(n)}$。

再看一个循环变量操作是乘法的例子：

1
2
3
4

int i=0;
while(i<n) {
    i = i*2;
}

无循环程序

这一类问题，我们只需要解决递归(recursion)问题即可。
递归问题一般使用公式进行递推。例如，求解$T(n)$和下一层更小规模的时间复杂度$T(n-1)$之间的关系。

我们以最经典的问题使用递归法求斐波那契数列为例子：

递归问题的原理是逐步缩小输入数据的规模，所以计算递归问题的时间复杂度也可以按照这个思路，计算所有基本语句的执行次数。

假设原始问题（输入规模为$n$）的时间复杂度为T(n)，根据斐波那契数列公式我们可以知道，$T(n)=1+T(n-1)+T(n-2)$，其中的$1$指的是这一层计算的次数，如果有循环的话，执行次数就会转换为$n$了。接下来，进行下一层的推导，$T(n)=O(1)+(O(1)+T(n-1)+T(n-2))+(O(1)+T(n-2)+T(n-3))$。所以，

递归问题时间复杂度求解还有一个很形象的方法就是递归树法。

更多例子

1
2
3
4

int i=5;
while((i+1)(i+1)<n) {
    i = i+1;
}

上述问题是循环程序求解，循环变量是$i$，假设基本语句$i=i+1$的执行次数是$t$，在经历了$t$次运算后，$i=5+t$，根据循环终止条件可获得式子：$(t+6)*(t+6)<n$，所以$t<\sqrt{n}-6=O(\sqrt{n})$。

算法空间复杂度分析

算法空间复杂度$S(n)$定义为该算法所需要的辅助存储空间（默认输入规模为$n$），例如几个与输入数据规模$n$相同的辅助数组的时空间复杂度为$O(n)$、辅助HashMap等。

空间复杂度的计算还是比较容易的，主要是计算最大辅助存储空间即可，例如二维数组$int[n][n]$的空间复杂度$S(n)$为$O(n^2)$。根据渐近分析的定义，我们只选择最高阶项即可。

递归问题的空间复杂度分析

递归问题的算法复杂度分析涉及到程序运行原理，每进行一层的递归，都需要程序运行栈提供$O(1)$的辅助存储位置保存这一层的结果，直到递归程序到达底端，此时程序运行栈中保存的数据数量最多，只要计算这个时候占了多少存储空间即可。在递归树中，空间复杂度为递归树的层高。

参考文献：北航计算机专业《算法设计与分析》课程、王道数据结构、HKU ARIN7001 PartIII

• ← Previous Post
• Next Post →