[关闭]
@MicroCai 2015-03-16T11:14:08.000000Z 字数 1503 阅读 6075

算法的时间复杂度

计算机基础


「计算机基础」系列用以复习基础之用,文章整理自网络


算法是一个计算的具体步骤。同一个问题使用不同的算法,效率也不尽相同,甚至天差地别,所以寻找一个好的算法有可能大大提高程序性能。

算法复杂度是用来衡量算法优劣的重要标准,包括时间复杂度和空间复杂度。见名知意,时间复杂度是用来衡量算法的执行时间上的效果,空间复杂度用来衡量所占内存空间的情况。这次主要是回顾点算法时间复杂度的基础知识点。

时间复杂度的计算

  1. 找出算法中的基本语句;
    算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。

  2. 计算基本语句的执行次数的数量级;
    只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。

  3. 用大 O 记号(Big-O)表示算法的时间性能。
    将基本语句执行次数的数量级放入大 Ο 记号中。
    如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。

  1. // 算法时间复杂度为 O(n)
  2. for (i=1; i<=n; i++)
  3. {
  4. x++;
  5. }
  6. // 算法时间复杂度为 O(n²)
  7. for (i=1; i<=n; i++)
  8. {
  9.  for (j=1; j<=n; j++)
  10.  {
  11. x++;
  12. }
  13. }

算法中还可能会牵涉 稳定性 这一概念。假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri = rj,且 ri在 rj 之前,而在排序后的序列中,ri 仍在 rj 之前,则称这种排序算法是稳定的;否则称为不稳定的。

常用数据结构和算法的复杂度

下面列举了许多算法和数据结构的时间复杂度表和空间复杂度,可以用来作为速查表 (查看表格来源

搜索算法

图中由上至下依次是:

搜索算法

排序算法

图中由上至下依次是:

排序算法

数据结构

图中由上至下依次是:

数据结构

图中由上至下依次是:

堆

图中由上至下依次是:

图

算法时间复杂度的曲线图

图中 x 轴表示元素个数, y 轴表示基本语句的执行次数次数,右侧函数表示算法时间复杂度。

算法时间复杂度的曲线图

算法的时间复杂度与运行时间有一些常见的比例关系 查看图表来源

复杂度 10 20 50 100 1,000 10,000 100,000
O(1) < 1s < 1s < 1s < 1s < 1s < 1s < 1s
O(log(n)) < 1s < 1s < 1s < 1s < 1s < 1s < 1s
O(n) < 1s < 1s < 1s < 1s < 1s < 1s < 1s
O(n*log(n)) < 1s < 1s < 1s < 1s < 1s < 1s < 1s
O(n²) < 1s < 1s < 1s < 1s < 1s 2 s 3-4 min
O(n³) < 1s < 1s < 1s < 1s 20 s 5 hours 231 days
O(2^n) < 1s < 1s 260 days hangs hangs hangs hangs
O(n!) < 1s hangs hangs hangs hangs hangs hangs
O(n^n) 3-4 min hangs hangs hangs hangs hangs hangs

参考链接

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注