算法札记

一些常见的大O运行时间

  • O($log^n$),也叫对数时间,这样的算法包括二分查找。
  • O(n),也叫线性时间,这样的算法包括简单查找。
  • O(n * $log^n$),一种速度较快的排序算法,这样的算法包括快速排序。
  • O($n^2$),一种速度较慢的排序算法,这样的算法包括选择排序。
  • O(n!),一种非常慢的算法。

假设你要绘制一个包含16格的网格,且有5种不同的算法可供选择,这些算法的运行时间如上所示。如果你选择第一种算法,绘制该网格所需的操作数将为4(log 16 = 4)。假设你每秒可执行10次操作,那么绘制该网格需要0.4秒。如果要绘制一个包含1024格的网格呢?这需要执行10(log 1024 = 10)次操作,换言之,绘制这样的网格需要1秒。这是使用第一种算法的情况。

第二种算法更慢,其运行时间为O(n)。即要绘制16个格子,需要执行16次操作;要绘制1024个格子,需要执行1024次操作。执行这些操作需要多少秒呢?

下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间:

算法绘制网格所需的时间

代码

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
def quicksort(array):
if len(array) < 2:
return array ←------基线条件:为空或只包含一个元素的数组是“有序”的
else:
pivot = array[0] ←------递归条件
less = [i for i in array[1:] if i <= pivot] ←------由所有小于等于基准值的元素组成的子数组

greater = [i for i in array[1:] if i > pivot] ←------由所有大于基准值的元素组成的子数组

return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])
打赏支持:如果你觉得我的文章对你有所帮助,可以打赏我哟。