> For the complete documentation index, see [llms.txt](https://data-structure-and-algorithm.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://data-structure-and-algorithm.gitbook.io/project/daobiao-shi-fa.md).

# 大O表示法

每次介绍算法时，我都将讨论其运行时间。一般而言，应选择效率最高的算 法，以最大限度地减少运行时间或占用空间。

大O表示法是一种特殊的表示法，指出了算法的速度有多快。

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

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

O(n)时间意味着查看列表中 的每个元素一次。例如，对乐队列表进行简单查找时，意味着每个乐队都要查看一次。

对数：

![](https://3953159057-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_oS8XWzoA34pjHOQZS%2F-LbadYdmw392x3dlKIRI%2F-LbahUSt805SdL23XLOY%2Fimage.png?alt=media\&token=b7f3ad2a-e811-4bbc-b01d-476ab72e21b5)

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

1. O(log n)，也叫对数时间，这样的算法包括二分查找。 
2. O(n)，也叫线性时间，这样的算法包括简单查找。 
3. O(n \* log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。 
4. O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。 
5. O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

![](https://3953159057-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_oS8XWzoA34pjHOQZS%2F-Lbak382zWADMyPuPVai%2F-LbakGDebYQVEZooduRA%2Fimage.png?alt=media\&token=00792c4d-0ba1-4564-86b8-5a4773ab3e3d)

![](https://3953159057-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_oS8XWzoA34pjHOQZS%2F-Lbak382zWADMyPuPVai%2F-LbakXwHM2dZRtYpn4aS%2Fimage.png?alt=media\&token=e776f377-1b51-4ae7-836d-be68749bb94d)

![](https://3953159057-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_oS8XWzoA34pjHOQZS%2F-LbbB4mgLaTFNrDwn_xf%2F-LbbCelmRwzLko9pxZqb%2Fimage.png?alt=media\&token=d5f063ca-31a9-4b40-bef0-291ae42c1d4e)

小结：

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