算法图解 - 大 O 表示法

🏷️ 《算法图解》

大 O 表示法

大 O 表示法是一种特殊的表示法，指出了算法的速度有多快。大 O 表示法指出了最糟情况下的运行时间。

一些常见的大 O 运行时间：

1. $O(lo{g}_{2}n)$ 也叫对数时间

2. $O(n)$ 也叫线性时间

3. $O(n\ast lo{g}_{2}n)$

4. $O(n^2)$

5. $O(n!)$ n 的阶乘

旅行商算法（n!）

一位旅行商要前往 5 个城市，同时要确保旅程最短。

$P_5^5$ 也就是 $5!=120$

当扩展到 n 个城市时，就是需要执行 $n!$ 次操作才能计算出结果。

小结

• 算法的速度指的并非时间，而是操作数的增速。

• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

• 算法的运行时间用大 O 表示法表示。

• $O(lo{g}_{2}n)$ 比 $O(n)$ 快，当需要搜索的元素越多时，前者比后者快的越多。