算法的时间复杂度

计算机基础

---

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

---

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

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

时间复杂度的计算

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

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

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

// 算法时间复杂度为 O(n)
for (i=1; i<=n; i++)
{
       x++;  
}
// 算法时间复杂度为 O(n²)
for (i=1; i<=n; i++)
{
    　for (j=1; j<=n; j++)
    　{
          x++;
      }
}

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

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

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

搜索算法

图中由上至下依次是：

• 深度优先搜索
• 广度优先搜索
• 二分查找
• 穷举查找
• 最短路径-Dijkstra，用小根堆作为优先队列
• 最短路径-Dijkstra，用无序数组作为优先队列
• 最短路径-Bellman-Ford

排序算法

图中由上至下依次是：

• 快速排序
• 归并排序
• 堆排序
• 冒泡排序
• 插入排序
• 选择排序
• 桶排序
• 基数排序

数据结构

图中由上至下依次是：

• 基本数组
• 动态数组
• 单链表
• 双链表
• 跳表
• 哈希表
• 二叉树搜索
• 笛卡尔树
• B-树
• 红黑树
• 伸展树
• AVL 树

堆

图中由上至下依次是：

• 链表（已排序）
• 链表（未排序）
• 二叉堆
• 二项堆
• 斐波那契堆

图

图中由上至下依次是：

• 邻接表
• 关联表
• 邻接矩阵
• 关联矩阵

算法时间复杂度的曲线图

图中 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

参考链接

• Big-O Cheat Sheet - Know Thy Complexities!
• zolalad - 算法的时间复杂度和空间复杂度
• 维基百科 - 时间复杂度
• Dennis Gao - 算法复杂度分析