快速排序时间复杂度 [英] Quick sort time complexity

问题描述

我最近阅读了有关时间复杂度的信息，发现快速排序的平均时间复杂度为 O（nlog（n））。

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

问题1：我不理解时间复杂度方程式中的 log（n）是如何出现的？

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

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

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

推荐答案

如何登录进入了复杂度公式吗？

How did the logn got into the complexity formula?

• 对于每一步，您都在第一和第二步上递归调用算法



• 因此-所需的总步骤数是从 n 开始达到所需的次数如果您将问题按每步2的比例分配给 1 。
  
  所以您实际上是在寻找 k 这样的：

• 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 n to 1 if you devide the problem by 2 each step.
  So you are actually looking for a k such that:

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

但是，请注意，等式实际上是： n / 2 ^ k = 1 。由于 2 ^ logn = n ，我们得到 k = logn 。因此，算法所需的步骤（迭代）数为O（logn），这将使算法 O（nlogn）-因为每次迭代均 O（n）。

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).

注意：在这里并不精确，在极少数情况下，快速排序会衰减到 O（n ^ 2），这取决于数据透视选择。 每步2划分问题是一种简化，但它不会更改算法的平均值分析。

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 average analyzis of the algorithm.

为什么要使用大O符号？

它简单且独立于平台。

op的确切数量（有时甚至是比较）取决于平台。 （如果指令集A比指令集B更丰富，则可能需要更多操作）。

它绝对不是使用的 only 方法。对于现实生活中的应用程序，确切的运行时间（以秒为单位）是非常重要的因素，经常被使用。

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 only method used. For real life applications, the exact run time (in seconds) is very important factor and is often used.

因此，简而言之-大O表示法使我们易于计算-独立于平台的近似算法在渐近（无穷大）处的表现方式，可以将算法的族划分为复杂性的子集，让我们可以轻松地在它们之间进行比较。

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，theta和大/小欧米茄。

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

这篇关于快速排序时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！