理解算法中的时间复杂度与空间复杂度

我们讨论算法时，都讨论其运行时间。一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。
但是如何量化算法有多快呢？以每次运行的时间为基准？随着元素的增多，时间可能会失去参考性。此时我们就需要一种表示法来量化算法的执行效率，这正是大O表示法的用武之地。

大O表示法指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。（记住，大O表示法计算的是操作数。）

举几个常见算法例子

二分法

使用二分法检查长度为n的列表，需要执行log n次操作。使用大O表示法怎么表示呢，O(log n)或者O(log2n)。

简单查找

使用简单查找（也称为线性查找），则按照顺序依次对比，需要执行n次操作（当然也有可能，第一个就是）。使用大O表示法为O(n)。
解释一下，为什么使用简单查找第一次就找到了，仍然为O(n)。

简单查找的运行时间总是为O(n)。查找时，一次就找到了，这是最佳的情形，但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

选择排序

有一个歌单，里面有歌曲和播放次数。现在有一个需求，需要对歌单按照播放次数进行排序。
实现思路，遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。然后继续再次这样做，找出播放次数第二多的乐队，如此循环…

要找出播放次数最多的乐队，必须检查列表中的每个元素。正如你刚才看到的，这需要的时间为O(n)。因此对于这种时间为O(n)的操作，你需要执行n次。

所以这样的“算法”需要的总时间为O(n × n)，即O(n²)。
随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一个。既然如此，运行时间怎么还是O(n2)呢？

你说得没错，并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素数依次为n -1, n -2, …, 2和1。平均每次检查的元素数为1/2 ×n，因此运行时间为O(n×1/2×n)。但大O表示法省略诸如1/2这样的常数，因此简单地写作O(n×n)或O(n²)。

一些常见的大O运行时间

下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。

1. O(log n)，也叫对数时间，这样的算法包括二分查找。
2. O(n)，也叫线性时间，这样的算法包括简单查找。
3. O(n * log n)，这样的算法包括的快速排序一种速度较快的排序算法。
4. O(n²)，这样的算法包括选择排序——一种速度较慢的排序算法。
5. O(n! )，阶乘，一种非常慢的算法。

关于对数

你可能不记得什么是对数了，但很可能记得什么是幂。log10 100相当于问“将多少个10相乘的结果为100”。答案是两个：10 × 10=100。因此，log10 100=2。对数运算是幂运算的逆运算。

为了理解对数，一些示例

一些关于对数的理论知识

log2 8=3 （2的多少次方等于8，答案为3）

有些没有底数的叫常用对数，常用对数 log10(x)，有时写为 log(x)

n log n就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方，归并排序就是O(nlogn)的时间复杂度。

使用大O表示法讨论运行时间时，log指的都是log2。使用简单查找法查找元素时，在最糟情况下需要查看每个元素。因此，如果列表包含8个数字，你最多需要检查8个数字。而使用二分查找时，最多需要检查log n个元素。如果列表包含8个元素，你最多需要检查3个元素，因为log 8=3（2的3次方等于8）。如果列表包含1024个元素，你最多需要检查10个元素，因为log 1024=10（2的十次方等于1024）。

FAQ

0. 算法运行时间并不以秒为单位。
1. 算法的速度指的并非时间，而是操作数的增速。
2. 算法运行时间是从其增速的角度度量的。
3. 算法的运行时间用大O表示法表示。

参考资料：
《算法图解》
算法复杂度和大O表示法
请问怎么计算时间复杂度？