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

  • Z时代
  • 2024-01-10
  • 分类：问答

我知道的“直觉”如何计算它n，n^2，n!等等，但是我完全失去了关于如何计算它是算法 等等。

我的意思是，我知道快速排序是n log n（平均）..但是， 呢？合并/梳理等也是一样

谁能以一种不太数学的方式向我解释你如何计算这个？

主要原因是Im即将接受一次大采访，我很确定他们会要求这种东西。我研究了几天，似乎每个人都对气泡排序为什么是n ^

2的解释或维基百科上对我来说不可读的解释

回答：

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

许多算法需要大步数的对数，但是每个大步幅都需要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）。

以上是 如何为更复杂的算法（例如快速排序）计算订单（大O） 的全部内容， 来源链接： utcz.com/qa/400367.html

回到顶部