算法的时间复杂度与空间复杂度

1. 函数的渐进增长

现在来测试算法A和算法B哪种更好。假设两种算法的输入规模都是n，算法A要做2n+3次运算，算法B要做3n+3次运算。它们两个的执行次数谁大谁小？

可以很明显的看出刚开始各种算法的执行次数差不多，但随着输入规模n的扩大，算法A和B得执行次数开始逐渐拉大。A算法执行次数少于B，就说A算法优于B算法。

函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得所有n>N，f(n)总是比g(n)大，那么我们就说f(n)的增长渐进快于g(n)。

当输入规模扩大到一定程度的时候，无论是+3还是+1对算法执行次数造成的影响都是微乎其微的，甚至可以说是没有影响，这个时候就可以忽略掉这些加法常数。

现在来测试算法C和算法D哪种更好。

但随着输入规模n的扩大，算法C和D得执行次数开始逐渐拉大。C算法执行次数少于D，就说C算法优于D算法。去掉加法常数后，再去掉与n相乘的常数后，代码的执行次数也不会发生太大的改变。扩大到一定程度后，甚至是没有改变，那么就说与最高次相乘的常熟并不重要。

再来测试E和F两种算法。

随着输入规模n的扩大，算法E和F的执行次数开始逐渐拉大。并且可以很明显的看出最高次项指数大的，函数随着n的增长，结果也会变得增长的特别快。

这6种不同的算法足以说明，如果要判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注最高阶项的阶数。

某一个算法，随着n不断增大，会越来越优于另一种算法，或者会差于另一种算法。

2. 算法时间复杂度

2.1 什么是时间复杂度

随问题规模n的扩大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。f(n)是问题规模n的某个函数。

使用大写的0()来体现时间复杂度的记法，即大0记法。一般的情况下，随着n的增大，算法的执行次数增长最慢的称为最优算法。

O(1) 叫常数阶，O(n) 叫线性阶，O(n^2) 叫平方阶。

2.2 大O阶方法如何推导

大O阶方法的推导有着自己的公式。

1. 用常熟1取代运行时间中的所有加法常熟。
2. 在修改过后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且系数不是1，则去除与这个项相乘的系数。得到的结果就是大O阶。

即便是有了这个公式，在后面也会遇到特殊的例子，更重要的是结合思想来确定时间复杂度。

2.3 常数阶

来看一段代码

int sum = 0;//执行一次
int n = 10;//执行一次
sum = (1 + n) * n / 2;//执行一次
System.out.println(sum);//执行一次
1
2
3
4

代码一共执行了4次，为什么时间复杂度不是O(4)，而是O(1)呢？

上面代码的运行次数函数是f(n)=3，根据公式第一步就是把3改为1。因为没有最高阶项，所以算法的时间复杂度就是O(1)。

值得注意的是，不论执行多少次，这个常数都会改为1。这种与n的大小无关执行时间恒定的算法，称之为具有O(1)的时间复杂度，又称常数阶。

注意事项：无论这个常数是多少，都只能是O(1)，而不能是O(3)，O(100)，O(1000)等其它任何数字。

2.4 线性阶

 for (int i = 0; i < n; i++) {
     //时间复杂度为O(1)的程序序列
 }
1
2
3

循环的终止条件是小于n，使用循环会执行n次，算法的时间复杂度就是O(n) 随着n的增大，循环的执行次数也会增大，复杂度也会增大。

如果要分析线性阶的时间复杂度，分析出循环的执行次数就可以了。

2.5 对数阶

先看下面代码

int num = 1;
int n = 10;
while (num < n) {
    num = num * 2;
}
1
2
3
4
5

由于每次num乘以3之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循环。由2^x=n得到x=logn（以2为底）。所以 这个循环的时间复杂度为O(logn)。

2.6 平方阶

再来看一段代码

 int m = 10;
 for (int i = 0; i < m; i++) {
     for (int j = 0; j < m; j++) {

     }
 }
1
2
3
4
5
6

内循环执行了m次，外循环执行了m次。它的执行次数是m*m，即时间复杂度是O(m^2)。

当内循环变成n的时候，时间复杂度就变成了O(m*n)。

再来看下面的代码

for (int i = 0; i < m; i++) {
   for (int j = i; j < m; j++) {
   
   }
}
1
2
3
4
5

由于当i=0时，内循环执行了n次，当i=1时，执行了n-1次…当i=n-1次时，执行了1次，所以总的执行次数是：

参照推导大O阶的方法，可以得出时间复杂度为O(n^2)。

2.7 常用的时间复杂度

常用的时间复杂度从小到大依次是：

2.8 最坏与最好情况

假如现在要在一个有n个随机数字的数组中查找一个数字，最好的情况是第一个数字就是要找的数字，只需要查找一次就找到了，算法的时间复杂度是O(1)；最坏的情况就是这个数字在数组的最后一个位置，这个时候就要整个数组遍历一边，算法的时间复杂度就是O(n)。

注意：在没有特别说明的情况下。算法的时间复杂度指的都是最坏的情况。

3. 算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式：S(n)=O(f(n))，其中n为问题的规模，f(n)为语句关于n所占用存储空间的函数。

若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O(1)。