如何为更复杂的算法（例如快速排序）计算订单（大O）

如何为更复杂的算法（例如快速排序）计算订单（大O）

对数是求幂的逆运算。取幂的一个示例是在每个步骤中将项目数量加倍。因此，对数算法通常将每个步骤的项目数量减半。例如，二进制搜索属于该类别。

许多算法需要大步数的对数，但是每个大步幅都需要O（n）个工作单元。Mergesort属于这一类。

通常，您可以通过将它们可视化为平衡的二叉树来识别这些类型的问题。例如，这是合并排序：

 6   2    0   4    1   3     7   5  2 6      0 4      1 3       5 7    0 2 4 6 1 3 5 7         0 1 2 3 4 5 6 7

输入的最上方是树的叶子。该算法通过对上面的两个节点进行排序来创建一个新节点。我们知道平衡二叉树的高度为O（log n），所以有O（log
n）个大步。但是，创建每个新行需要O（n）的工作。O（n）的O（log n）大步骤每个都意味着mergesort总体上为O（n log n）。

通常，O（log n）算法看起来像下面的函数。他们在每一步都会丢弃一半的数据。

def function(data, n):    if n <= constant:       return do_simple_case(data, n)    if some_condition():       function(data[:n/2], n / 2) # Recurse on first half of data    else:       function(data[n/2:], n - n / 2) # Recurse on second half of data

O（n log n）算法看起来像下面的函数。他们还将数据分成两半，但需要同时考虑这两个部分。

def function(data, n):    if n <= constant:       return do_simple_case(data, n)    part1 = function(data[n/2:], n / 2)      # Recurse on first half of data    part2 = function(data[:n/2], n - n / 2)  # Recurse on second half of data    return combine(part1, part2)

其中do_simple_case（）花费O（1）的时间，而Combine（）花费不超过O（n）的时间。

该算法不需要将数据精确地分成两半。他们可以将其分为三分之一和三分之二，那很好。对于平均情况下的性能，将其平均拆分为一半就足够了（例如QuickSort）。只要对（n/某物）和（n-n /某物）进行递归，就可以了。如果将其分解为（k）和（nk），则树的高度将为O（n）而不是O（log n）。