大O表示法 是一种特殊的表示法，指出了算法的速度有多快。
大O表示法指出了算法有多快。例如，假设列表包含n 个元素。简单查
找需要检查每个元素，因此需要执行n 次操作。使用大O表示法，这个
运行时间为O (n )。单位秒呢？没有——大O表示法指的并非以秒为单位
的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的
增速 。再来看一个例子。为检查长度为n 的列表，二分查找需要执行log n 次操
作。使用大O表示法，这个运行时间怎么表示呢？O (log n )。这指出了算法需要执行的操作数。之所以称为大O表示法，是因为操作
数前有个大O。这听起来像笑话，但事实如此！
O (log n )，也叫对数时间 ，这样的算法包括二分查找。
O (n )，也叫线性时间 ，这样的算法包括简单查找。
O (n * log n )，快速排序：一种速度较快的排序算法。
O (n^2)，选择排序：一种速度较慢的排序算法。
O (n！)，一种非常慢的算法。
O (1)被称为常量时间 。你以前没有见过常量时间，它并不意味着马上，而是说不管
散列表多大，所需的时间都相同。例如，你知道的，简单查找的运行时
间为线性时间。
image.png
网友评论