如何计算更复杂算法的阶数（大O）（例如快速排序）

我知道有很多关于大O表示法的问题，我已经检查过了：

• 大O的简单英语解释 https://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o
• 大O，你是如何计算/近似的？ https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it
• 大O记法作业——代码片段算法分析？ https://stackoverflow.com/questions/216796/big-o-notation-homework-code-fragment-algorithm-analysis

仅举几例。

我凭“直觉”知道如何计算n, n^2, n!所以，但是我完全不知道如何计算它的算法log n , n log n, n log log n and so.

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

有人能用不太数学的方式向我解释一下你是如何计算这个的吗？

主要原因是我即将接受一次大型采访，我很确定他们会要求这类东西。我已经研究了几天了，每个人似乎都对为什么冒泡排序是 n^2 有解释，或者对我来说不可读的解释维基百科 http://en.wikipedia.org/wiki/Big_O_notation

对数是指数的逆运算。取幂的一个例子是在每一步将项目数加倍。因此，对数算法通常将每一步的项目数量减半。例如，二分查找就属于这一类。

许多算法需要对数个大步骤，但每个大步骤都需要 O(n) 个工作单元。归并排序就属于这一类。

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

 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) 个大步骤意味着归并排序总体上是 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) 时间，而 merge() 花费不超过 O(n) 时间。

该算法不需要将数据精确地分成两半。可以分成三分之一和三分之二，那就可以了。对于平均情况的性能，将其平均分成两半就足够了（如快速排序）。只要递归是在 (n/something) 和 (n - n/something) 的片段上完成的，就可以了。如果将其分解为 (k) 和 (n-k)，那么树的高度将是 O(n) 而不是 O(log n)。