数据结构与算法-时间复杂度

这篇文章会讲到时间频度，时间复杂度，一些排序算法的平均时间复杂度与最坏时间复杂度

1.度量一个程序（算法）的两种方法

1）事后统计法

2）事前估算法

2.时间频度

1.基本介绍

算法1：

算法2：

3.算法的时间复杂度引入

1.举例说明：忽略常数项

2.举例说明：忽略低次项

3.举例说明：忽略系数

4.算法的时间复杂度介绍

1.时间复杂度

2.常见的时间复杂度

分类：

顺序：

3.具体介绍常见的时间复杂度

1.常数阶O(1)

2.对数阶O(log2n)

3.线性阶O(n)

4.线性对数阶O(Nlogn)

5.平方阶O(n^2)

6.立方阶O(n^3)、k次方阶O(n^k)

5.算法的平均时间复杂度和最坏时间复杂度

1.介绍：

2.我们以排序算法为例：

6.算法的空间复杂度简介

7.提炼一下

1.度量一个程序（算法）的两种方法

1）事后统计法

这种方法就是运行一段程序，运行后看花了多少时间。然后再运行另外一段程序，看程序运行花了多少时间，把这时间进行比较。

但是事后统计法有两个问题：

一是要评测设计的算法的运行性能，就需要实际运行该程序，每次要比较就要亲自运行一遍未免太麻烦了，更别说如果这个程序运行完就要10分钟，一直等着那太痛苦了；

二是所得的时间的统计量依赖于计算机的硬件、软件等环境因素，比如你的计算机硬件环境比较好，运行起来嘎嘎快，那同样的程序运行的时间都不一样，更别说不同的程序了，不好比较的，这样就需要在同一台计算机相同的状态下运行才能比较哪个算法速度更快。

2）事前估算法

通过分析某个算法的时间复杂度来判断哪个算法更优。

2.时间频度

1.基本介绍

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中语句的执行次数称为语句频度或者时间频度，记为T(n)。

举例：

计算1-100所有数字之和，可以设计两种算法：

算法1：

int total=0;int end=100;for(int i=1;i<=end;i++){total+=i;}

那么上面这个算法时间频度就是T(n)=n+1;

解释：

因为虽然循环中执行total+=i是执行了1到end也就是100次，但是在for循环的条件中还有个i<=end，然后i=101的时候是判断了，然后不满足条件所以退出，多了一次，所以它就是101次。

算法2：

int total=0;
int end=100;
total=(1+end)*end/2;

那么上面这个算法的时间频度就是T(n)=1

3.算法的时间复杂度引入

我们看到上面的时间频度n+1中带有常数1，次数不是100而是101，太细致了吧。对于常数项，我们还可以看一看，如果没有像1这样的常数项，和带常数项的相比会有多大差别呢？

1.举例说明：忽略常数项

这里可以通过一个表格来看一下：

从n为1到n为300，可以发现这个常数项的影响变小了很多。再看看图：

有常数项的和没有常数项的曲线是不是到n比较大的时候就很接近了！要是n到了1000，那差距是不是看着更小了。

可以得出结论：

1.2n+20和2n随着n变大，执行曲线无限接近，20可以忽略

2.3n+10和3n随着n变大，执行曲线无限接近，10可以忽略

那么对于时间频度而言，常数项可以忽略

2.举例说明：忽略低次项

下面的T(2n^2+3n+10)应该是T(n)= 2n^2+3n+10

可以看到前面两项随着n增大，数值看着比较接近了。后面两项也是，不再是一开始的相差几十倍了。再看图：

有低次项的和没有低次项的曲线是不是到n比较大的时候就很接近了！都要重合了。

可以得出结论：

1.2n^2+3n+10和2n^2随着n变大，执行曲线无限接近，3n+10可以忽略

2.n^2+5n+20和n^2随着n变大，执行曲线无限接近，5n+20可以忽略

那么对于时间频度而言，低次项可以忽略

3.举例说明：忽略系数

下面的T(3n^2+2n)应该是T(n)= 3n^2+2n

在三次方参与的情况下，n=100时这两个二次方的都是与1000000相差很多，在图上看着是很接近的。

可以得出结论：

1.随着n变大，5n^2+7n和3n^2+2n，执行曲线无限接近，在这种情况下作为系数的5和3可以忽略，反正都是二次方的。

2.n^3+5n和6n^3+4n随着n变大，执行曲线分离，但是次方是不能忽略的。二次方和三次方差异巨大啊。不过这里呢n^3+5n和6n^3+4n求导发现大概是6，1000000与6000000。我觉得吧忽略系数这种还是对于一次方二次方的比较适用，对于三次方可能就感觉差距还是挺大的，不太好忽略。

4.算法的时间复杂度介绍

1.时间复杂度

一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示（就是前面时间频度的那个T(n)）。若有某个辅助函数f(n)使得当n趋于无穷大时T(n)/f(n)的极限值为不等于0的常数，就称f(n)是T(n)的同量级函数，记为T(n)=O(f(n))，O(f(n))为算法的渐进时间复杂度，简称为时间复杂度。比如T(n)=n+1，这时有个辅助函数f(n)=n，那么T(n)/f(n)就是(n+1)/n，在n无穷大时这个结果就是1.我们就可以吧T(n)=O(f(n))=O(n)，这个O(n)就是前面算法的时间复杂度。
T(n)不同但是时间复杂度可能相同，比如T(n)=n^2+7n+6与T(n)=3n^2+2n+2，这两个T(n)不一样，但是有个f(n)为n^2，当n无穷大时就趋于一个常数项，所以两个T(n)时间复杂度相同，都是O(n^2)。
计算时间复杂度的方法：
- 用常数1代替运算时间中的所有加分常数。比如T(n)=3n^2+7n+6变成T(n)=3n^2+7n+1
- 修改后的运算次数函数中只保留最高阶项，比如T(n)=3n^2+7n+1变成T(n)=3n^2
- 去除最高阶项的系数，比如T(n)=3n^2变成T(n)=n^2，推出来时间复杂度O(n^2)

2.常见的时间复杂度

顺序：

以上算法的时间复杂度从小到大依次为：

O(1)< O(log2n)< O(n)< O(nlog2n)< O(n^2)< O(n^3)< O(n^k)< O(2^n)

随着问题规模n不断增大，上面算法的时间复杂度不断增大。算法的时间复杂度越大，算法的执行效率越低。

从图中我们可以看到，指数阶的算法在n=10的时候就飙上去了，我们应该尽量避免使用指数阶的算法。其实还有个阶乘阶O(n!)，是时间复杂度最大的，比O(2^n)还大。

3.具体介绍常见的时间复杂度

1.常数阶O(1)

无论代码执行多少行，只要没有循环之类的复杂结构，代码的时间复杂度就是O(1)

举例：

int i=1;int j=2;++i;j++;int m=i+1;

如果i=100000，j=200000，程序执行消耗的时间也不会变，它不会因为变量的增长使消耗的时间变长，就算几千行几万行，都可以用O(1)来表示它的时间复杂度。

2.对数阶O(log2n)

对数阶不一定是以2为底的，也可以log3n，log4n，log10n等等。

在数学中，如果N=a^x(a>0,a≠1)，也就是a的x次方等于N，那么x就是以a为底N的对数，x=logaN。a就是对数的底数，x就是以a为底N的对数。

下面的例子是以2为底的对数阶。

举例：

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

解释：在while循环中，每次将i乘以2，成倍变化，那么总有一个时候不满足条件i<n，也就是i=n或者i>n的时候循环结束。假设循环x次之后，i就大于2了，那么循环就退出了，也就是2的x次方等于n，x=log2n，循环log2n次之后代码就结束了，所以这段代码时间复杂度为O(log2n)。假设n为1024，那么那么x就是10，那么循环10次后代码就结束了。

如果while循环里面i=i*3，那么时间复杂度就是O(log3n)。

那么就记住，这样的循环里面是i=i*k，循环条件是i<n，代码的时间复杂度就是O(logkn)

3.线性阶O(n)

比如单纯的for循环，要循环n次的。

举例：

for(int i=1;i<=n;++i){j=i;j++;}

上面代码中for循环里的代码会执行n遍，时间频度是T(n+1)，它消耗的时间也随n变化而变化，时间复杂度为O(n)。如果n为10，那么时间复杂度就是O(10)

4.线性对数阶O(Nlogn)

其实将时间复杂度为O(logn)的代码循环N遍的时间复杂度就是O(Nlogn)，因为O(N*f(n))=O(N*logn)。

举例：

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

可以看到外面的循环条件m<n，里面的循环时间复杂度logn（其实是log2n简写为logn），那么总的时间复杂度就是O(nlogn)。

5.平方阶O(n^2)

双层for循环，外面循环n次，里面循环n次就达到了n^2次，时间复杂度就是O(n*n)=O(n^2)。

举例：

for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){{System.out.println(“i=”+i+“,j=”+j);}}

上面代码中输出i的值和j的值，i循环n次，j循环n次，那么内层循环中代码就执行了n^2次。比如n=10，输出的就有100行。

如果把其中一层循环的n改成m，那么时间复杂度就是O(m*n)，比如m=8，n=10，i<=m,j<=n，那么内层循环中的输出语句就执行8*10=80次。

6.立方阶O(n^3)、k次方阶O(n^k)

参考上面的O(n^2)理解，O(n^3)相当于三层循环，k次方阶相当于k层循环。

5.算法的平均时间复杂度和最坏时间复杂度

1.介绍：

平均时间复杂度指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

最坏时间复杂度是最坏情况下的时间复杂度。一般讨论的时间复杂度都是最坏情况下的时间复杂度。因为最坏时间复杂度是算法在任何输入实例上运行时间的界限，保证运行时间不会比最坏情况下更长。拿最坏时间复杂度当保底，再差也不会比保底差。
平均时间复杂度和最坏时间复杂度是否一致呢？得看具体算法。

2.我们以排序算法为例：

排序算法	平均时间	最坏情况	稳定度	额外空间	备注
冒泡	O(n^2)	O(n^2)	稳定	O(1)	n小用
交换	O(n^2)	O(n^2)	不稳定	O(1)	n小用
选择	O(n^2)	O(n^2)	不稳定	O(1)	n小用
插入	O(n^2)	O(n^2)	稳定	O(1)	大部分已排序用
基数	O(logRB)	O(logRB)	稳定	O(n)	B为真数(0-9) R为基数(个十百)
希尔	O(nlogn)	O(n^s) 1<s<2	不稳定	O(1)	s为所选分组
快速	O(nlogn)	O(n^2)	不稳定	O(nlogn)	n大用
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大用
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大用

6.算法的空间复杂度简介

算法的空间复杂度定义为该算法所耗费的存储空间，也是关于问题规模n的函数。它是对一个算法在运行过程中临时占用的存储空间大小的度量。有的算法需要占用的临时工作单元数与解决问题的规模n有关，随n增大而增大，当n较大时占用的存储单元就多，比如快速排序和归并排序算法。

注意，我们在做算法分析时，主要讨论的是时间复杂度，从用户角度看，更看重程序执行的速度，要是程序执行很慢用户肯定不乐意了，用户体验就不好了。一些缓存产品比如redis和memcache还有算法比如基数排序，就是用空间换时间。而且一些程序的算法优化就是用空间换时间，设置二级缓存三级缓存，会占用额外空间但是时间上加载时就会更快。