如何为更复杂的算法（例如快速排序）计算订单（大O） [英] How to calculate order (big O) for more complex algorithms (eg quicksort)
问题描述
我知道关于O表示法存在很多问题，我已经检查过：
I know there are quite a bunch of questions about big O notation, I have already checked:
- Plain english explanation of Big O
- Big O, how do you calculate/approximate it?
- Big O Notation Homework--Code Fragment Algorithm Analysis?
仅举几例。
我知道直觉如何针对 n ， n ^ 2 ， n计算它！等等，但是对于 log n ， n log n的算法，如何计算它却一无所知， n log log n 等。
I know by "intuition" how to calculate it for n, n^2, n! and so, however I am completely lost on how to calculate it for algorithms that are log n , n log n, n log log n and so.
我的意思是是，我知道快速排序为 n log n （平均）..但是，为什么？对于合并/梳子等也是同样的事情。
What I mean is, I know that Quick Sort is n log n (on average).. but, why? Same thing for merge/comb, etc.
有人可以用不太数学的方式解释我吗？
Could anybody explain me in a not too math-y way how do you calculate this?
主要原因是我即将接受一次大采访，我很确定他们会要求这种东西。我研究了几天，似乎每个人要么对为什么气泡排序是n ^ 2的解释，要么对维基百科
The main reason is that Im about to have a big interview and I'm pretty sure they'll ask for this kind of stuff. I have researched for a few days now, and everybody seem to have either an explanation of why bubble sort is n^2 or the unreadable explanation (for me) on Wikipedia
推荐答案
对数是求幂的逆运算。取幂的一个示例是在每个步骤中将项目数量加倍。因此，对数算法通常将每个步骤的项目数量减半。例如，二进制搜索属于这一类。
The logarithm is the inverse operation of exponentiation. An example of exponentiation is when you double the number of items at each step. Thus, a logarithmic algorithm often halves the number of items at each step. For example, binary search falls into this category.
许多算法需要对数的大步数，但每个大步数需要O（n）个工作单元。 Mergesort属于此类。
Many algorithms require a logarithmic number of big steps, but each big step requires O(n) units of work. Mergesort falls into this category.
通常，您可以通过将它们可视化为平衡的二叉树来识别这些类型的问题。例如，这里是合并排序：
Usually you can identify these kinds of problems by visualizing them as a balanced binary tree. For example, here's merge sort:
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）。
At the top is the input, as leaves of the tree. The algorithm creates a new node by sorting the two nodes above it. We know the height of a balanced binary tree is O(log n) so there are O(log n) big steps. However, creating each new row takes O(n) work. O(log n) big steps of O(n) work each means that mergesort is O(n log n) overall.
通常，O（log n）算法看起来像下面的功能。他们在每一步都会丢弃一半的数据。
Generally, O(log n) algorithms look like the function below. They get to discard half of the data at each step.
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）算法看起来像下面的函数。他们还将数据分成两半，但是他们需要考虑两个部分。
While O(n log n) algorithms look like the function below. They also split the data in half, but they need to consider both halves.
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）时间。
Where do_simple_case() takes O(1) time and combine() takes no more than O(n) time.
算法不需要将数据精确地分成两半。他们可以将其分为三分之一和三分之二，那很好。对于平均情况下的性能，将其平均拆分为一半就足够了（例如QuickSort）。只要对（n /某物）和（n-n /某物）进行递归，就可以了。如果将其分为（k）和（n-k），则树的高度将为O（n）而不是O（log n）。
The algorithms don't need to split the data exactly in half. They could split it into one-third and two-thirds, and that would be fine. For average-case performance, splitting it in half on average is sufficient (like QuickSort). As long as the recursion is done on pieces of (n/something) and (n - n/something), it's okay. If it's breaking it into (k) and (n-k) then the height of the tree will be O(n) and not O(log n).
这篇关于如何为更复杂的算法（例如快速排序）计算订单（大O）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
