如何计算更复杂的算法（如快速排序）的顺序（大O）
我知道有很多关于大O符号的问题，我已经检查过：
仅举几例。
我通过“直觉”知道如何计算n ， n^2 ， n! 所以，但是我完全失去了如何计算log n ， n log n ， n log log n等算法的结果。
我的意思是，我知道快速排序是n log n （平均）..但是， 为什么 ？ 合并/梳理等相同的东西
有人可以用一种不太数学的方式解释我吗？你如何计算这个数字？
主要原因是我即将进行一次大型采访，而且我非常确定他们会要求这种东西。 我已经研究了几天，每个人似乎都有解释为什么冒泡排序为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（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 /东西）和（n - n /东西）的片断上完成的，没关系。 如果将它分解为（k）和（nk），那么树的高度将是O（n）而不是O（log n）。
您通常可以在每次运行时将空间/时间减半的算法声明log n。 一个很好的例子是任何二进制算法（例如二进制搜索）。 您可以选择左侧或右侧，然后将您正在搜索的空间加入一半。 重复做一半的模式是log n。
对于一些算法来说，通过直觉获得运行时间的一个紧密限制几乎是不可能的（例如，我不认为我会永远能够运行O(n log log n)运行时间，并且我怀疑任何人将永远期望你）。 如果您可以亲身体验CLRS算法简介文本，那么您会发现渐进式符号的相当彻底的处理方式，其适当的严格性而不会完全不透明。
如果算法是递归的，一个简单的派生边界的方法是写出一个递归，然后着手解决它，要么迭代地，要么使用主定理或其他方式。 例如，如果您不想超级严谨，获取QuickSort运行时间的最简单方法是通过主定理 - QuickSort需要将数组划分为两个相对平等的子阵列（应该相当直观地看到这是O(n) ），然后在这两个子阵列上递归地调用QuickSort。 那么如果我们让T(n)表示运行时间，我们有T(n) = 2T(n/2) + O(n) ，这是由主方法为O(n log n) 。
上一篇: How to calculate order (big O) for more complex algorithms (eg quicksort)