java 快速排序时间复杂度

Quick sort time complexity

提问by Prakhar Mohan Srivastava

I recently read about time complexity and I found out that Quick sort has an average time complexity of O(nlog(n)).

我最近阅读了时间复杂度，我发现快速排序的平均时间复杂度为O(nlog(n))。

Question 1: What I do not understand is how is the log(n)present in the time complexity equation?

问题 1：我不明白的是log(n)是如何出现在时间复杂度方程中的？

Question 2: Why do we always use the big Onotation to find the time complexity of algorithms? Why don't we use other notations?

问题2：为什么我们总是用大O表示法来求算法的时间复杂度？为什么我们不使用其他符号？

回答by amit

How did the logngot into the complexity formula?

是如何logn进入复杂性公式的？

• For each step, you invoke the algorithm recursively on the first and second half.

• Thus - the total number of steps needed, is the number of times it will take to reach from nto 1if you devide the problem by 2 each step.
  So you are actually looking for a ksuch that:

  n / 2 /2 / 2 / ... /2 = 1
          ^
       (k times) 
  

  But, note that the equation is actually: n / 2^k = 1. Since 2^logn = n, we get k = logn. So the number of steps (iterations) the algorithm requires is O(logn), which will make the algorithm O(nlogn)- since each iteration is O(n).

• 对于每一步，您在前半部分和后半部分递归调用算法。

• 因此 - 所需的总步数是如果您将问题每一步除以 2 n，1则到达 from 所需的次数。
  所以你实际上正在寻找k这样的：

  n / 2 /2 / 2 / ... /2 = 1
          ^
       (k times) 
  

  但是，请注意，该等式实际上是：n / 2^k = 1。因为2^logn = n，我们得到k = logn. 所以算法需要的步数（迭代）是 O(logn)，这将使算法O(nlogn)- 因为每次迭代都是O(n).

Note:The complexity in here is not exact, quicksort in rare cases decays to O(n^2), it is depends on the pivot selection. The "devide the problem by 2 each step" is a simplification, but it does not change the averageanalyzis of the algorithm.

注意：这里的复杂度并不准确，快速排序在极少数情况下会衰减到O(n^2)，这取决于枢轴选择。“每一步将问题除以 2”是一种简化，但它不会改变算法的平均分析。

Why use big O notation?
It is simple and platform independent.
The exact number of op (and sometimes even comparisons) is platform dependent. (If instruction set A is richer then instruction set B, it will probably need more ops).
It is definetly not the onlymethod used. For real life applications, the exact run time(in seconds) is very important factor and is often used.

为什么要使用大 O 符号？
它简单且独立于平台。
op（有时甚至是比较）的确切数量取决于平台。（如果指令集 A 比指令集 B 更丰富，它可能需要更多的操作）。
它绝对不是唯一使用的方法。对于现实生活中的应用程序，确切的运行时间（以秒为单位）是非常重要的因素，并且经常使用。

So, in short - big O notation gives us easy to calculate - platform independent approximation on how will the algorithm behave asymptotically (at infinity), which can divide the "family" of algorithm into subsets of their complexity, and let us compare easily between them.

因此，简而言之 - 大 O 符号使我们易于计算 - 平台无关的近似算法将如何渐近（在无穷大），这可以将算法的“家族”划分为其复杂性的子集，并让我们轻松地比较他们。

Also, other notations that are used are small o, theta and big/small omega.

此外，使用的其他符号是small o、theta 和 big/small omega。

回答by adit

Ques 1. Quick sort's worst case time complexity is O(n^2),whereas average case complexity is O(nlogn). logn factor depends upon the pivot, how the algorithm choose it.

问题 1. 快速排序的最坏情况时间复杂度为 O(n^2)，而平均情况复杂度为 O(nlogn)。logn 因子取决于枢轴，算法如何选择它。

Quick sort worst case time complexity occur when pivot produces two regions one of size 1 element and other of size (n-1) elements recursively.Whereas average case occurs when pivot chooses two regions such that both regions produced have a size of n/2.

当枢轴递归地生成大小为 1 的元素和另一个大小为 (n-1) 个元素的两个区域时，会出现快速排序最坏情况时间复杂度。而平均情况发生在枢轴选择两个区域时，生成的两个区域的大小均为 n/2 .

So recursive relation produced is T(n)=2T(n/2)+Θ(n).

所以产生的递归关系是T(n)=2T(n/2)+Θ(n)。

                  f(n)=Θ(n)     
                  h(n)=n^log2(2)=>n 
                  since f(n) = h(n) so
                  T(n)= f(n)logn =>n(logn).

(here we are using Θ notation since worst case complexity(big O) of quick sort is O(n^2) and here we are calculating average case complexity.)

（这里我们使用 Θ 表示法，因为快速排序的最坏情况复杂度（大 O）是 O(n^2)，这里我们计算平均情况复杂度。）

Ques 2. We use big O notation because it gives the idea of worst case time complexity which limits the algorithm even when the arguments tends infinity,that means the algo will atleast run in this time complexity and cannot go beyond it.

问题 2. 我们使用大 O 表示法，因为它给出了最坏情况时间复杂度的想法，即使参数趋于无穷大，这也限制了算法，这意味着算法至少会在这个时间复杂度内运行并且不能超过它。

Whereas there are other notations such small o, theta and big/small omega which are used very often as they have limited applications.

而还有其他符号，例如小 o、theta 和大/小 omega，由于它们的应用有限，因此经常使用。

回答by André Oriani

Please read Introduction to Algorithms by Cormen et al. In the chapter 3 you will find a good explanation about Complexity Analysis of algorithms. You will find that Big O is not the only asymptotic notation that is used.

请阅读Cormen 等人的算法简介。在第 3 章中，您将找到有关算法复杂性分析的很好的解释。您会发现 Big O 并不是唯一使用的渐近符号。

回答by Pyrce

Even though this is more of a question about computer science in general which can be explained more thoroughly by the comments on the question --

尽管这更像是一个关于计算机科学的一般问题，可以通过对该问题的评论进行更彻底的解释——

Question 1: the log(n) is there to denote that the problem scales at a higher rate than a O(n) problem by a factor log(n). The terms smaller than n*log(n) (like n) are omitted because they scale slower than the largest term.

问题 1：log(n) 表示问题的扩展速率比 O(n) 问题高一个因子 log(n)。小于 n*log(n)（如 n）的项被省略，因为它们的缩放比最大项慢。

Question 2: There are other metrics, O (big O) is the worst case rate of problem expansion. See the book links in the comments to see what the others are/mean, as it's better explained there.

问题2：还有其他指标，O（大O）是最坏情况下的问题扩展率。请参阅评论中的书籍链接以了解其他人是/意味着什么，因为那里有更好的解释。