算法图解 - 大 O 表示法

大 O 表示法

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

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

  1. $O(log_2 n)$ 也叫对数时间

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

  3. $O(n * log_2 n)$

  4. $O(n^2)$

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

旅行商算法（n!）

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

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

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

小结

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

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

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

  • $O(log_2 n)$ 比 $O(n)$ 快，当需要搜索的元素越多时，前者比后者快的越多。