问题描述
我知道有一大群约大O符号的问题，我已经检查的的纯英文解释，大O，怎么你计算/近似它？和<一href="http://stackoverflow.com/questions/216796/big-o-notation-homework-$c$c-fragment-algorithm-analysis">Big O符号家庭作业 - code片段算法分析，仅举几例
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?, and Big O Notation Homework--Code Fragment Algorithm Analysis?, to name a few.
我知道的直觉如何计算它 N ， N ^ 2 ， N！等等，但我完全就如何计算它的算法，它们的 日志N ，<$ C丢失$ C> N日志ñ， N日志日志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日志ñ（平均）..但是，为什么？同样的事情合并/梳子等。
What I mean is, I know that Quick Sort is n log n (on average).. but, why? Same thing for merge/comb, etc.
可能有人解释我在一个不太数学-Y方式如何计算的？
Could anybody explain me in a not too math-y way how do you calculate this?
主要的原因是我将要产生大的面试，我是pretty的肯定，他们会问这种东西。我研究，现在几天，大家似乎都为什么冒泡排序为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 (for me) unreadable explanation a la 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）的工作单位。归并属于这一类。
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）时间，并结合（）将不超过O（n）的时间更多。
Where do_simple_case() takes O(1) time and combine() takes no more than O(n) time.
的算法不需要拆分恰好一半的数据。他们可以将其分为三分之一和三分之二，这将是罚款。为平均情况下的性能，平均分裂成两半是足够（如快速排序）。只要递归上的（N /某事）件和完成的（N - N /某事），也没关系。如果它分解成（k）和（NK），那么树的高度将是为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）为更复杂的算法（例如快速排序）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！