侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 292 篇文章
  • 累计创建 132 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

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

孔子说JAVA
2019-11-03 / 0 评论 / 0 点赞 / 86 阅读 / 3,034 字 / 正在检测是否收录...

1、算法复杂度表示方法

描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度, 它们代表的含义:  这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。大O加上()的形式,里面其实包裹的是一个函f(),O(f()),指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。

  • 注: logn -对数函数n=log(a)(b),反向表示an=b。如果ax=N(a>0,且a≠1),那么数x叫做以a为底N的对数,记作x=logaN,读作以a为底N的对数,其中a叫做对数的底数,N叫做真数。上下文中的logn默认以2为底数。

image-1649579389044

  1. 比如时间复杂度为O(n),就代表数据量增大几倍,耗时也增大几倍。比如常见的遍历算法。
  2. 时间复杂度O(n2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度。比如冒泡排序,就是典型的O(n2)的算法,对n个数排序,需要扫描n×n次。
  3. O(logn),当数据增大n倍时,耗时增大logn倍(这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度)。二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。
  4. O(nlogn)同理,就是n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。
  5. O(1)就是最低的时空复杂度了,也就是耗时/耗空间与输入数据大小无关,无论输入数据增大多少倍,耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标(不考虑冲突的话)

2、常用排序算法时空复杂度

排序法 时间复杂度(最坏) 时间复杂度(最好) 时间复杂度(平均) 稳定性 空间复杂度
冒泡排序 O(n^2) O(n) O(n^2) 稳定 O(1)
快速排序 O(n^2) O(nlogn) O(nlogn) 不稳定 O(nlogn)~O(n)
选择排序 O(n^2) O(n^2) O(n^2) 不稳定 O(1)
二叉树排序 O(n^2) O(nlogn) O(nlogn) 不稳定 O(n)
插入排序 O(n^2) O(n) O(n^2) 稳定 O(1)
堆排序 O(nlogn) O(nlogn) O(nlogn) 不稳定 O(1)
希尔排序 O(n^2) O(n) O(nlogn) 不稳定 O(1)
归并排序 O(nlogn) O(nlogn) O(nlogn) 稳定 O(n)
计数排序 O(n+k) O(n+k) O(n+k) 稳定 O(n+k)
桶排序 O(n^2) O(n) O(n+k) 稳定 O(n+k)
基数排序 O(n*k) O(n*k) O(n*k) 稳定 O(n+k)

3、常用数据结构增删查复杂度

3.1 时间复杂度

(1)时间频度

一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

(2)时间复杂度

在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

(3)渐进时间复杂度评价算法时间性能

主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

  • 在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n^2)。 按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(logn),线性阶O(n), 线性对数阶O(nlogn),平方阶O(n2),立方阶O(n3),…, k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
// 对数阶
void aFunc(int n) {    
    for (int i = 2; i < n; i++) {
        i *= 2;
    }
}

解释: 假设循环次数为 t,则循环条件满足 2^t < n。可以得出,执行次数t = log(2)(n),即 T(n) = log(2)(n),可见时间复杂度为 O(log(2)(n)),即 O(log n)。

//指数阶
long aFunc(int n) {    
    if (n <= 1) {        
        return 1;
    } else {        
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

解释: 显然运行次数,T(0) = T(1) = 1,同时 T(n) = T(n - 1) + T(n - 2) + 1,这里的 1 是其中的加法算一次执行。显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列,通过归纳证明法可以证明,当 n >= 1 时 T(n) < (5/3)^n,同时当 n > 4 时 T(n) >= (3/2)^n。所以该方法的时间复杂度可以表示为 O((5/3)^n),简化后为 O(2^n)。

3.2 空间复杂度

与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量,它也是问题规模n的函数。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。渐近空间复杂度也常常简称为空间复杂度。

  • 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地"进行的,是节省存储的算法;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。

  • 如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

0

评论区