大O表示法

大O表示法指出了算法有多块

image-20210829095256434

  1. 大 O 表示法指出了最糟情况下的运行时间（算法执行步数）
    • 除最糟情况下的运行时间外，还应考虑平均情况的运行时间

一些常见的大 O 运行时间

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

image-20210829095521599

最后总结：

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

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

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

大O表示法省略诸如1/2这样的常数