如何计算更复杂算法(如快速排序)的顺序(大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(log n)的大步骤o(n)工作每个意味着合并排序是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/something)和(n-n/something)的片段上完成,就可以了。如果它把它分成(k)和(n-k),那么树的高度将是o(n),而不是o(log n)。

对于算法,您通常可以声明log n,它在每次运行时将空间/时间减半。这方面的一个好例子是任何二进制算法(例如二进制搜索)。选择左或右,然后将搜索的空间分成两半。重复做一半的模式是log n。

对于某些算法来说,通过直觉获得运行时间的严格限制几乎是不可能的(我认为我永远都无法凭直觉 O(n log log n) 例如,运行时间,我怀疑是否有人会期望你这样做)。如果你能把手放在 CLRS Introduction to Algorithms text ,你会发现一个非常彻底的渐近符号的处理,这是适当的严格,而不是完全不透明。

如果该算法是递归的,则导出边界的一个简单方法是写出一个递归,然后开始迭代或使用 Master Theorem 或者其他方式。例如,如果您不想对它过于严格,获得Quicksort运行时间的最简单方法是通过主定理——Quicksort需要将数组分成两个相对相等的子数组(这应该是相当直观的 O(n) ,然后在这两个子数组上递归调用quicksort。如果我们让 T(n) 表示运行时间,我们有 T(n) = 2T(n/2) + O(n) ,按master方法 O(n log n) .

查看此处给出的“电话簿”示例: What is a plain English explanation of "Big O" notation?

记住,大O是 规模 :随着数据集的增长,此算法还需要多少操作?

O(log n) 通常意味着您可以在每次迭代中将数据集减半(例如二进制搜索)

O(n log n) 表示正在执行O(log n)操作 对于每一个 数据集中的项

我很确定‘O(n日志n)’没有任何意义。或者,如果是这样,它将简化为O(n log n)。

我将尝试做一个直观的分析为什么MergeSort是n Log n,如果你能给我一个n Log Log n算法的例子,我也可以通过它来工作。

mergesort是一个排序示例,它通过重复拆分元素列表,直到只存在元素,然后将这些列表合并在一起。每个合并中的主要操作是比较,每个合并最多需要n个比较,其中n是两个列表组合的长度。从这个例子中,你可以得到循环,并很容易地解决它,但是我们将避免这种方法。

相反,考虑一下mergesort的行为方式,我们将获取一个列表并将其拆分,然后将这些部分再拆分,直到有n个长度为1的分区为止。我希望可以很容易地看到,在将列表拆分为n个分区之前,这种递归只会深入日志(n)。

既然我们有了这些n个分区中的每一个都需要合并,那么一旦合并了这些分区,下一个级别就需要合并,直到我们有一个长度为n的列表。有关此过程的简单示例,请参阅维基百科的图形。 http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg .

现在考虑这个过程将花费的时间,我们将有日志(n)级别,在每个级别上,我们将不得不合并所有列表。事实证明,合并每个级别需要n个时间,因为我们每次都要合并总共n个元素。然后,您可以很容易地看到,如果将比较操作作为最重要的操作,则使用mergesort对数组进行排序需要n个日志(n)时间。

如果有什么不清楚或我跳过了某个地方,请告诉我,我可以尽量更详细。

编辑第二个解释:

让我想想,如果我能更好地解释这一点。

这个问题被分解成一组较小的列表,然后对较小的列表进行排序和合并,直到您返回到现在已排序的原始列表。

当你分解问题时,你有几个不同的大小级别,首先你有两个大小列表:N/2,N/2,然后在下一个级别你有四个大小列表:N/4,N/4,N/4,N/4,在下一个级别你有N/8,N/8,N/8,N/8,N/8,N/8,N/8,N/8,N/8,N/8,N/8,这会一直持续到N/2^K等于1(每个分区的长度除以P2的幂,并不是所有的长度都可以被4整除,所以它不会很漂亮)。这是两次的重复除法,最多可以继续执行log 2(n)次,因为2^(log 2(n))=n,所以再除以2将产生一个大小为零的列表。

现在要注意的重要一点是,在每一个级别上,我们都有n个元素,所以对于每一个级别,合并需要n个时间,因为合并是一个线性操作。如果有递归的日志(n)级别,那么我们将执行这个线性操作日志(n)次,因此我们的运行时间将是n日志(n)。

对不起,如果这也没用的话。

当应用一种分治算法,将问题分割成若干个子问题,直到问题简单到微不足道时,如果分割顺利,则每个子问题的大小大约为n/2。这通常是 log(n) 出现在大O复杂性中: O(log(n)) 是分区正常时所需的递归调用数。