This website requires JavaScript.

算法札记

一些常见的大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次操作。执行这些操作需要多少秒呢?

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

算法绘制网格所需的时间

代码

快速排序

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])
0条评论
avatar