算法——大O表示法

定义：一种特殊的表示法，指出了算法的速度有多快。用于表示运行时间如何随列表增长而增加。

场景：例如，假设列表包含N个元素。简单查找需要检查每个元素，因此需要执行N次操作。使用大O表示法，这个运行时间为O(n)。如果使用二分法的话，需要执行logN，使用大O表示法，就是O(logN).

以下从快到慢列出经常会遇到的5种大O运行时间：

O(logN),也叫对数时间，这样的算法包括二分查找。

O(N),也叫线性时间，这样的算法包括简单查找。

O(n*logN)，快速排序。

O(N*N),选择排序。

O(N!),旅行商问题的解决方案。

Ps:大O表示法指出了最糟糕情况下的运行时间;大O表示法让你能够比较操作数，它指出了算法运行时间的增速;算法的速度指的并非时间，而是操作数的增速;谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加;O(logN)比O(N)快，当需要搜索的元素越多时，前者比后者快得越多。

参考自：算法图解