图解算法—大O表示法

时间复杂度（大O表示法）

我们在运行算法时，仅仅知道算法需要多长时间能运行完还不够，还需要知道运行时间如何随列表增长而增加，这就是大O表示法的用武之地。大O表示法指出了算法有多快。例如，假设列表包含n个元素，简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O（n）。注：大O表示法指的并非以秒为单位的速度，而是在最坏情况下算法需要执行的操作数。

图解大O表示法

假设我们要画一个网格，它包含16个格子

算法1

以每次画一个的方式画16个格子。画一个格子是一次操作，需要画16个格子就需要16步，所以该算法的运行时间为O（n）

算法2

每次将纸对折。对折一次就是一次操作，每折一次，格子数就翻倍，折4次就能得到16个格子。所以该算法的运行时间为O（log n）.

一些常见的大O运行时间

下面按从快到慢的顺序列出了5种大O运行时间
O（log n）,也叫对数时间，这样的算法包括二分查找；
O（n）,也叫线性时间，这样的算法包括简单查找；
O（n*log n）,这样的算法包括快速排序（一种速度较快的排序算法）；
O（n^2）,这样的算法包括选择排序（一种速度较慢的排序算法）；
O（n!）,这样的算法包括旅行商问题（一种非常慢的算法）。

下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间

总结

1）算法的速度指的并非时间，而是操作数的增速；
2）谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加；
3）算法的运行时间用大O表示法表示；
4）O(log n)比O(n)快，当需要搜索的元素原来越多时，前者比后者快得越多