时间复杂度和空间复杂度

原文连接

评价一个算法的优劣，往往会从时间复杂度和空间复杂度两个维度来评价。执行时间越短，占用空间越小的算法，被视为最优算法。

——《数据结构和算法之美》

• 时间复杂度全称渐进式时间复杂度
• 空间复杂度全称渐进式空间复杂度

为什么需要对算法进行评价呢？一个算法直接执行一遍，它的消耗时间和占用空间就一目了然了。这个策略也可以，它有个专业名称——事后统计法，但是它有着很大局限性：

• 依赖运行环境和机器性能
• 依赖测试数据的规模

因此，需要在算法设计之初，就要对它进行一个大概的评估。当算法开发完成后，可以执行算法，来验证评估。

大 O 复杂度表示法

算法的执行效率，可以简单的描述为执行时间。算法没有运行，如何估计它的运行时间呢？来分析下面一段代码：

var dic = new Dictionary<int, int>();  // 1行
var n = nums.Length;                   // 2行
for (int i = 0; i < n; i++)            // 3行
{                                      // 4行
    res = nums[i];                     // 5行
    dic.Add(nums[i], i);               // 6行
}                                      // 7行

这段代码一看，消耗时间的地方肯定是这个for循环。当 n 很大时，第1,2行代码消耗的时间可以忽略不计了，因此在算法分析过程里，只考虑消耗最大的那段代码。假设第4、5行代码执行所需时间都是一个单位时间(unit_time)，那4、5行代码共需 $2*unitTime$，整个for循环执行完的时间 $T(n)$ 大概是 $n2unitTime$，可以看出，T(n)与n成正比，用一个公式记作 $T(n)=O(f(n))$。这个公式中 T(n) 表示代码执行时间总和，n表示数据规模，$$f(n)$$ 表示每行代码执行时间，$O$ 表示 $T(n)$ 是 $f(n)$ 的一个正比函数。

时间复杂度分析方法

1. 只关注执行次数最多的代码段

例如上面示例中的代码，代码执行次数最多的是for循环这一段。第4、5行代码共执行n次，执行时间$$T(n)=O(f(n))$$，因此时间复杂度记作$$O(n)$$。

1. 加法法则

有下面一段代码

//第一段           
for (int i = 0; i < n; i++)       
{                                      
    res = nums[i];                     
    dic.Add(nums[i], i);               
}    
//第二段
for (int k = 0; i < m; i++)       
{                                      
    res = nums[k];                     
    dic.Add(nums[k], k);               
}  

这段代码有2小段，先看第一段，假设单行代码执行所需时间为 unit_time,那么第一段代码所需时间就是 $n2unitTime$，记作$$T1(n)=O(f(n))$$。同理第二段代码消耗时间为$$T2(n)=O(g(n))$$，整段代码所需全部时间为$$T(n)=T1(n)+T2(n)$$。

根据第一条规则，取时间数量级最大的作为总的时间复杂度，那么$$T(n)=Max((O(f(n))),(O(g(n))))=O(n)$$。

1. 乘法规则

看下面代码：

         
for (int i = 0; i < n; i++)       
{                                      
    for (int k = 0; i < n; i++)       
	{                                      
    	res = nums[k];                     
    	dic.Add(nums[k], k);               
	}            
}    

外层循环的消耗时间为$T1(n)$，内层循环消耗时间为$T2(n)$，总消耗时间为 $T(n) = T1(n)*T2(n)= O(n * n)=O(n^2)$

常见时间复杂度

• 常量阶 $O(1)$
• 线性阶 $O(n)$
• 对数阶 $O(logn)$
• 线性对数阶 $O(nlogn)$
• 指数阶 $O(2^n)$
• 阶乘阶 $O(n!)$
• 平方阶 $O(n^2)$ 立方阶 $O(n^3)$ ……m次方阶 $O(n^m)$

​ $O(1)$

是一种时间复杂度表示方式，并非指执行了一行代码，例如下面的代码，及时它执行了100次，1千次，时间复杂度仍是$O(1)$

int i=0;
int j=i+10;

$O(n)$

这种时间复杂度非常常见，例如for循环

for(int i=0; i<n;i++){
	int k=i;
}

$O(logn)$

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

​ 这段代码的终止条件是 $2^i >= n$ ,那么 $i = log_2 n = log n$ ，因此时间复杂度为$O(logn)$。

最好、最坏、均摊、平均时间复杂度

• 最好情况时间复杂度
• 最坏情况时间复杂度
• 均摊时间复杂度
• 平均情况时间复杂度

最好、最好情况时间复杂度，很好理解，也很常见。例如使用循环在一个数组中找到某个元素，最好的情况是，这个元素是第一个元素，那么就是最好情况复杂度 $O(1)$，如果这个元素是最后一个，那么就需要遍历整个数组，才能找到，其时间复杂度就是 $O(n)$。

空间复杂度

空间复杂度分析比时间复杂度分析要简单很多，例如以下代码:

int i=0;
int[] arr=new int[n];
for (int i = 0; i < n; i++)       
{    
    res = nums[k];           
}  

这段代码中，第1行声明一个变量，它是常量阶 $O(1)$ ，和数据规模无关。第2行声明一个长度为 n 的数组，它占用空间取决于数据规模n，因此它的空间复杂度为 $O(n)$。for循环中只是进行副职，并没有开辟新的空间。因此这段代码空间复杂度为 $O(n)$

在看一段代码：

for (int i = 0; i < n; i++)       
{    
    for (int k = 0; i < n; i++)       
	{                                      
    	int a=i;               
	}            
} 

这段代码 int a=i 是常量阶，但是它处于2层循环内，相当于声明了$n*n=n^2$ 次变量，因此它的空间复杂度为 $O(n^2)$.

最好、最坏时间复杂度是个极端情况，出现的概率不大。为了更好的表示大多数情况下的时间复杂度，引入平均情况时间复杂度概念。

还是假设在一个数组中查找某个元素，这个元素可能在数组中或不在数组中、在与不在概率都是$\frac{1}{2}$ ，这个元素可能出现在索引0~n-1任意位置的概率为 $\frac{1}{n}$ ，根据概率乘法得到综合概率为 $\frac{1}{2n}$ 。那么目标元素出现在索引0位置的时间复杂度为 $1*\frac{1}{2n}$ ，出现在索引1位置的时间复杂度为 $2*\frac{1}{2n}$，以此类推得到如下公式：

$1*\frac{1}{2n} + 2*\frac{1}{2n} + 3*\frac{1}{2n}+……+n*\frac{1}{2n} = \frac{3n+1}{4}$ .

这个值就是概率论中的平均加权值，也称作期望值。在去掉系数、常量、低阶量之后，得到的平均情况时间复杂度为 $O(n)$

均摊时间复杂度。这个概念跟平均时间复杂度容易混淆。有这样一个场景，集合(数组)中的 insert() 方法，待插入的数据可能会插入到任意一个索引位置，且每个索引位置概率都是 $\frac{1}{n+1}$ 。根据平均时间复杂度可得：

$1*\frac{1}{n+1} + 2*\frac{1}{n+1} + 3*\frac{1}{n+1}+……+n*\frac{1}{n+1} = O(1)$ .

由此可看出数组的 insert() 操作时间复杂度为 $O(1)$，而 find() 操作时间复杂度为 $O(n)$。这也是这两个函数的一个不同点。当然也存在特殊情况，当数组满了之后，此时插入数据，数组需要进行扩容，此时时间复杂度为 $O(n)$ (注意，这里的数组是指可变长数组，如果是定长数组，满了之后无法插入) 。当数组扩容后，再次插入数据时，时间复杂度又是$O(1)$，每到数组满了之后插入数据，时间复杂度又变成$O(n)$，如此循环往复。有n-1个$O(1)$，1个$O(n)$，然后接着是$O(1)$，$O(n)$……那么这一个$O(n)$就可以均摊到n-1个$O(1)$上去，最终时间复杂度还是$O(1)$。这块概念比较难理解，可以将均摊时间复杂度理解为特殊的平均情况时间复杂度。不用过度纠结。

​