如何计算更复杂算法的顺序(大O)(例如快速排序)

Question

我知道有很多关于大O符号的问题,我已经检查过了:

• 大O的简单英语解释
• 大O,你如何计算/近似它？
• Big O表示法作业 - 代码片段算法分析？

仅举几例.

我知道的"直觉"如何计算它n,n^2,n!等等,但是我完全失去了关于如何计算它是算法log n,n log n,n log log n等等.

我的意思是,我知道Quick Sort n log n(平均)..但是,为什么？合并/梳子等同样的事情

任何人都可以用不太算数的方式解释我,你怎么计算这个？

主要原因是我即将进行大型采访,我很确定他们会要求这种东西.我已经研究了几天了,似乎每个人都有解释为什么冒泡排序是n ^ 2或维基百科上不可读的解释(对我而言)

Answer 1

对数是取幂的逆运算.取幂的一个例子是当你将每一步的项目数加倍时.因此,对数算法通常将每一步的项目数减半.例如,二分搜索属于此类别.

许多算法需要对数个大步骤,但每个大步骤都需要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)工作的大步骤均表示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/something)和(n - n/something)的片段上完成的,那就没关系.如果将其分解为(k)和(nk),则树的高度将为O(n)而不是O(log n).

Answer 2

您通常可以为算法声明log n,每次运行时它会将空间/时间减半.一个很好的例子是任何二进制算法(例如,二进制搜索).你可以向左或向右选择,然后将你正在搜索的空间对齐一半.反复做一半的模式是log n.

Answer 3

对于某些算法来说,通过直觉获得运行时间的紧密限制几乎是不可能的(例如,我不认为我能够直观地计算O(n log log n)运行时间,而且我怀疑任何人都会指望你).如果您能够掌握CLRS算法简介文本,那么您将找到一种非常彻底的渐近符号处理方法,它具有适当的严谨性而不会完全不透明.

如果算法是递归的,那么导出一个边界的一种简单方法是写出一个重复,然后设置解决它,迭代地或使用主定理或其他方式.例如,如果你不想对它过于严格,那么获得QuickSort运行时间的最简单方法是通过Master Theorem - QuickSort需要将数组分成两个相对相等的子阵列(它应该是相当直观的看到它这是O(n)),然后在这两个子数组上递归调用QuickSort.然后,如果我们让T(n)表示运行时间,我们有T(n) = 2T(n/2) + O(n),通过主方法是O(n log n).