前言

所谓算法,其实就是我们用来操作数据、解决程序问题的一组方法。针对同一个问题,我们可以采用不同的算法,然后实现相同的结果。但是针对不同的算法,对于时间和资源的消耗却有不同的差别。而为了分析不同算法的效率,我们常常从 时间空间 两个方面来对比,然后从中挑出最适合我们的解决方案。

本文主要从时间复杂度和空间复杂度的定义说起,然后介绍常见的时间复杂度和空间复杂度,最后则是对常见排序算法进行了总结。

时间复杂度

定义

若存在函数 时间复杂度与空间复杂度 - 图11#card=math&code=f%28n%29&id=iUWor),使得当 时间复杂度与空间复杂度 - 图12 趋向无穷大时,时间复杂度与空间复杂度 - 图13%20%2F%20f(n)#card=math&code=T%28n%29%20%2F%20f%28n%29&id=gsY4r) 的极限值为不等于 0 的常数,则称 时间复杂度与空间复杂度 - 图14#card=math&code=f%28n%29&id=Ayzzl) 是 时间复杂度与空间复杂度 - 图15#card=math&code=T%28n%29&id=Q62Bv) 的同数量级函数,记作 时间复杂度与空间复杂度 - 图16%3DO(f(n))#card=math&code=T%28n%29%3DO%28f%28n%29%29&id=P2XbU),称 时间复杂度与空间复杂度 - 图17)#card=math&code=O%28f%28n%29%29&id=jJJeL) 为算法的 渐进时间复杂度,简称 时间复杂度,用大 O 来表示,称为 大 O 表示法

推导时间复杂度的原则

  1. 若运行时间是常数量级,则用常数 1 表示
  2. 只保留时间函数中最高阶项,如 时间复杂度与空间复杂度 - 图18#card=math&code=O%28n%5E2%20%2B%204n%29&id=ZJ7Em),保留最高阶项后,成为 时间复杂度与空间复杂度 - 图19#card=math&code=O%28n%5E2%29&id=n9CJr);
  3. 若最高阶项存在,则省去最高阶项前的系数,如 时间复杂度与空间复杂度 - 图20#card=math&code=O%284n%5E2%29&id=sE4N9),省去最高阶项的系数后,成为 时间复杂度与空间复杂度 - 图21#card=math&code=O%28n%5E2%29&id=Kc7xt);

分析时间复杂度的方法

总结起来,对于如何分析一段代码的时间复杂度,主要有如下 3 个实用方法:

  1. 只关注循环执行次数最多的一行代码;
  2. 加法原则:总复杂度等于量度最大的那段代码的复杂度;
  3. 乘法原则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见的时间复杂度曲线

时间复杂度与空间复杂度 - 图22

常见时间复杂度

时间复杂度与空间复杂度 - 图23#card=math&code=O%281%29&id=yoypk)

即无论执行多少行,都不会影响到其他区域,此时代码的复杂度就是 时间复杂度与空间复杂度 - 图24#card=math&code=O%281%29&id=wyBo5),如下面的代码中,假设执行每行代码时间都相同切为 时间复杂度与空间复杂度 - 图25,则 2,3 行各需 1 个执行时间,即为 $t + t = 2t。此时执行时间复杂度为常数。

  1. void sayHello(String name){
  2. System.out.prinln("Hello, " + String);
  3. System.out.prinln("欢迎关注我的公众号:【村雨遥】");
  4. }

时间复杂度与空间复杂度 - 图26#card=math&code=O%28log%20n%29&id=NuKGs)

如下列二分查找代码中,通过 while 循环,能够成倍的缩减搜索范围,假设需要 x 次才能跳出循环,则有 num * 2 * 2 * ... = n ,其中 num 是常数,有 n 个 2 相乘,则有 时间复杂度与空间复杂度 - 图27,从而推出 时间复杂度与空间复杂度 - 图28#card=math&code=x%20%3D%20log_2%28n%2Fnum%29&id=HSSaT) ,因此时间复杂度用大 O 表示法表示为 时间复杂度与空间复杂度 - 图29%E3%80%82#card=math&code=O%28log%20n%29%E3%80%82&id=BSUl7)

  1. int binarySearch(int[] arr, int target){
  2. int left = 0;
  3. int right = arr.length - 1;
  4. while(left <= right){
  5. int middle = left + (left - right) / 2;
  6. if(arr[middle] == target){
  7. return middle;
  8. }else if(arr[middle] > target){
  9. right = middle - 1;
  10. }else {
  11. left = middle + 1;
  12. }
  13. }
  14. return -1;
  15. }

时间复杂度与空间复杂度 - 图30#card=math&code=O%28n%29&id=YUson)

如下面这段代码中,for 循环中的代码被执行了 arr.length 次,因此所需要的时间和数组长度成正比的,因此可以用 时间复杂度与空间复杂度 - 图31#card=math&code=O%28n%29&id=fDMRN) 来表示它的时间复杂度。利用上述推到原则和分析的方法,可以知道下面代码中循环次数最多的是 4,5 行,总的执行时间是 时间复杂度与空间复杂度 - 图32#card=math&code=O%282n%29&id=Mrf7a),抛去系数后,得到最终时间复杂度 时间复杂度与空间复杂度 - 图33#card=math&code=O%28n%29&id=aSSLs).

  1. int sum(int[] arr){
  2. int total = 0;
  3. for(int i = 0; i < arr.length; i++){
  4. total += arr[i];
  5. }
  6. return total;
  7. }

时间复杂度与空间复杂度 - 图34#card=math&code=O%28n%20log%20n%29&id=mEb4m)

如果我们将一个复杂度为 时间复杂度与空间复杂度 - 图35#card=math&code=O%28logn%29&id=nrJ5n) 的代码重复执行 时间复杂度与空间复杂度 - 图36 次,那么此时代码的复杂度不就变成 时间复杂度与空间复杂度 - 图37#card=math&code=O%28nlogn%29&id=mk9HK) 了吗。

  1. void hello (int n){
  2. for( int i = 1 ; i < n ; i++){
  3. int m = 1;
  4. while( m < n ){
  5. m *= 2;
  6. }
  7. }
  8. }

时间复杂度与空间复杂度 - 图38#card=math&code=O%28n%5E2%29&id=OlQYf)

假设我们将时间复杂度为 时间复杂度与空间复杂度 - 图39#card=math&code=O%28n%29&id=nGKdG) 的代码重复执行 时间复杂度与空间复杂度 - 图40 次,那么此时的时间复杂度就是 时间复杂度与空间复杂度 - 图41#card=math&code=n%2AO%28n%29&id=aqBth),即可表示为 时间复杂度与空间复杂度 - 图42#card=math&code=O%28n%5E2%29&id=hQPml),表现出来就是双重循环的形式。

  1. void selectionSort(int[] arr, int n){
  2. for(int i = 0; i < n; i++){
  3. int min = i;
  4. for(int j = i + 1; j < n; j++){
  5. if(arr[j] < arr[min]){
  6. int tmp = arr[i];
  7. arr[i] = arr[j];
  8. arr[j] = tmp;
  9. }
  10. }
  11. }
  12. }

时间复杂度与空间复杂度 - 图43#card=math&code=O%28n%5E3%29&id=YdAqC)

时间复杂度与空间复杂度 - 图44#card=math&code=O%28n%5E2%29&id=u8vI2),类似,将时间复杂度为 时间复杂度与空间复杂度 - 图45#card=math&code=O%28n%5E2%29&id=CJEEn) 的代码嵌套循环一次,此时复杂度就变成了 时间复杂度与空间复杂度 - 图46#card=math&code=O%28n%5E3%29&id=wCPqt),表现出来就是三重循环嵌套的形式。

  1. void demo(int n){
  2. for(int i = 0; i < n; i++){
  3. for(int j = 0; j < n; j++){
  4. for(int k = 0; k < n; k++){
  5. System.out.print("Hello, World");
  6. }
  7. System.out.print("------");
  8. }
  9. System.out.print("******");
  10. }
  11. }

时间复杂度与空间复杂度 - 图47#card=math&code=O%28n%21%29&id=Uh0TM)

虽然理论上存在时间复杂度为 时间复杂度与空间复杂度 - 图48#card=math&code=O%28n%21%29&id=bhVNl) 的算法,但实践中基本遇不到,所以这里就不展开了。

空间复杂度

定义

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度(即除开原始序列大小的内存,在算法过程中用到的额外的存储空间),反映的对内存占用的趋势,而不是具体内存,也叫作 渐进空间复杂度表示算法的存储空间与数据规模间的增长关系,用 时间复杂度与空间复杂度 - 图49#card=math&code=S%28n%29&id=j7xu5) 来代替;

常用空间复杂度

时间复杂度与空间复杂度 - 图50#card=math&code=O%281%29&id=xGOs2)

算法执行所需临时空间不随某一变量 n 的大小而变化,则该算法空间复杂度为一个常量,表示为 时间复杂度与空间复杂度 - 图51%20%3D%20O(1)#card=math&code=S%28n%29%20%3D%20O%281%29&id=CJ8pN);

  1. int num1 = 1;
  2. int num2 = 2;
  3. int total = num1 + num2;

时间复杂度与空间复杂度 - 图52#card=math&code=O%28n%29&id=WFvfz)

数组占用内存大小为 n,而且后续未分配新的空间,因此该算法空间复杂度为 时间复杂度与空间复杂度 - 图53%20%3D%20O(n)#card=math&code=S%28n%29%20%3D%20O%28n%29&id=zttub);

  1. int[] arr = new int[n];

时间复杂度与空间复杂度 - 图54#card=math&code=O%28n%5E2%29&id=BfQMx)

二维数组的情况;

  1. int[][] arr = new int[n][n];

常见排序算法的时间复杂度和空间复杂度

对于面试中常见的的排序算法,以下总结给出了其时间复杂度以及空间复杂度,以及算法稳定性。

排序算法 平均时间复杂度 最好时间复杂度 最坏时间复杂度 空间复杂度 稳定性
插入排序 时间复杂度与空间复杂度 - 图55#card=math&code=O%28n%5E2%29&id=y2WkI) 时间复杂度与空间复杂度 - 图56#card=math&code=O%28n%29&id=UF3ol) 时间复杂度与空间复杂度 - 图57#card=math&code=O%28n%5E2%29&id=IozCb) 时间复杂度与空间复杂度 - 图58#card=math&code=O%281%29&id=QjnPM) 稳定
希尔排序 时间复杂度与空间复杂度 - 图59#card=math&code=O%28n%5E%7B1.3%7D%29&id=ostNj) 时间复杂度与空间复杂度 - 图60#card=math&code=O%28n%29&id=HqrhQ) 时间复杂度与空间复杂度 - 图61#card=math&code=O%28n%5E2%29&id=nnl20) 时间复杂度与空间复杂度 - 图62#card=math&code=O%281%29&id=BC0Xq) 不稳定
选择排序 时间复杂度与空间复杂度 - 图63#card=math&code=O%28n%5E2%29&id=BwYht) 时间复杂度与空间复杂度 - 图64#card=math&code=O%28n%5E2%29&id=Am6ka) 时间复杂度与空间复杂度 - 图65#card=math&code=O%28n%5E2%29&id=Sh88O) 时间复杂度与空间复杂度 - 图66#card=math&code=O%281%29&id=s5j8c) 不稳定
堆排序 时间复杂度与空间复杂度 - 图67#card=math&code=O%28nlog_2n%29&id=qOSEV) 时间复杂度与空间复杂度 - 图68#card=math&code=O%28nlog_2n%29&id=MSi3S) 时间复杂度与空间复杂度 - 图69#card=math&code=O%28nlog_2n%29&id=Rhu85) 时间复杂度与空间复杂度 - 图70#card=math&code=O%281%29&id=JOWLx) 不稳定
冒泡排序 时间复杂度与空间复杂度 - 图71#card=math&code=O%28n%5E2%29&id=uAO1g) 时间复杂度与空间复杂度 - 图72#card=math&code=O%28n%29&id=iAmoC) 时间复杂度与空间复杂度 - 图73#card=math&code=O%28n%5E2%29&id=mHENc) 时间复杂度与空间复杂度 - 图74#card=math&code=O%281%29&id=AAaFk) 稳定
快速排序 时间复杂度与空间复杂度 - 图75#card=math&code=O%28nlog_2n%29&id=Xwaph) 时间复杂度与空间复杂度 - 图76#card=math&code=O%28nlog_2n%29&id=q4p2s) 时间复杂度与空间复杂度 - 图77#card=math&code=O%28n%5E2%29&id=lEtVg) 时间复杂度与空间复杂度 - 图78#card=math&code=O%28nlog_2n%29&id=onOnG) 不稳定
归并排序 时间复杂度与空间复杂度 - 图79#card=math&code=O%28nlog_2n%29&id=XXNLc) 时间复杂度与空间复杂度 - 图80#card=math&code=O%28nlog_2n%29&id=b7mwY) 时间复杂度与空间复杂度 - 图81#card=math&code=O%28nlog_2n%29&id=uYR27) 时间复杂度与空间复杂度 - 图82#card=math&code=O%28n%29&id=IYFG1) 稳定
计数排序 时间复杂度与空间复杂度 - 图83#card=math&code=O%28n%2Bk%29&id=U0nX9) 时间复杂度与空间复杂度 - 图84#card=math&code=O%28n%2Bk%29&id=ELTDf) 时间复杂度与空间复杂度 - 图85#card=math&code=O%28n%2Bk%29&id=u404z) 时间复杂度与空间复杂度 - 图86#card=math&code=O%28n%2Bk%29&id=IZXLO) 稳定
桶排序 时间复杂度与空间复杂度 - 图87#card=math&code=O%28n%2Bk%29&id=tckpn) 时间复杂度与空间复杂度 - 图88#card=math&code=O%28n%29&id=i36PT) 时间复杂度与空间复杂度 - 图89#card=math&code=O%28n%5E2%29&id=KSZxt) 时间复杂度与空间复杂度 - 图90#card=math&code=O%28n%2Bk%29&id=JWT6K) 稳定
基数排序 时间复杂度与空间复杂度 - 图91#card=math&code=O%28n%2Ak%29&id=lXAMu) 时间复杂度与空间复杂度 - 图92#card=math&code=O%28n%2Ak%29&id=tS7ae) 时间复杂度与空间复杂度 - 图93#card=math&code=O%28n%2Ak%29&id=S5rjv) 时间复杂度与空间复杂度 - 图94#card=math&code=O%28n%2Bk%29&id=yBxYs) 稳定

总结

好了,以上就是今天文章的内容了。主要介绍了时间复杂度的定义、推导原则以及常见时间复杂度,还对空间复杂度定义以及常见空间复杂度进行了介绍,最后则是总结了常见排序算法的时间复杂度和空间复杂度。如果觉得文章对你有所帮助,那就点个赞再走吧!