有关三路快速排序（双支点快速排序），我将如何去寻找大O绑定？谁能告诉我如何获得的呢？

For 3-way Quicksort (dual-pivot quicksort), how would I go about finding the Big-O bound? Could anyone show me how to derive it?

推荐答案

还有查找的算法的复杂度和证明是

There's a subtle difference between finding the complexity of an algorithm and proving it.

要寻找的算法的复杂性，可以作为阿米特在对方回答说，这样做：你知道，在的平均值的，你拆你的尺寸的问题ñ成规模的三个小问题 N / 3 ，所以你会得到，在电子log_3（N）`步骤平均，大小1。问题随着经验的积累，你会开始得到这种方法的感觉，能够推导出的算法的复杂性只是在涉及到的子的角度思考这些问题。

To find the complexity of this algorithm, you can do as amit said in the other answer: you know that in average, you split your problem of size n into three smaller problems of size n/3, so you will get, in è log_3(n)` steps in average, to problems of size 1. With experience, you will start getting the feeling of this approach and be able to deduce the complexity of algorithms just by thinking about them in terms of subproblems involved.

要证明，该算法在运行O（nlogn）在平均情况下，您使用的主定理。要使用它，你必须写的递推公式给花了排序阵列的时间。正如我们所说，分拣大小的数组 N 可以分解为分选尺寸 N / 3 加上三个阵列花费的时间建立他们。这可以写成如下：

To prove that this algorithm runs in O(nlogn) in the average case, you use the Master Theorem. To use it, you have to write the recursion formula giving the time spent sorting your array. As we said, sorting an array of size n can be decomposed into sorting three arrays of sizes n/3 plus the time spent building them. This can be written as follows:

T(n) = 3T(n/3) + f(n)

其中， T（N）是一种功能，给予解决时间大小的输入 N （实际需要的基本操作）的数量，而 F（N）给分割问题划分为若干子所需要的时间。

Where T(n) is a function giving the resolution "time" for an input of size n (actually the number of elementary operations needed), and f(n) gives the "time" needed to split the problem into subproblems.

有关三路快速排序， F（N）= C * N ，因为你去通过阵列，请在哪里放置每个项目，并最终使交换。这使我们处于 法师定理案例2 ，其中指出，如果 F（N）=为O（n ^（log_b（一））登录^ K（N））一些 K＆GT; = 0 （在我们的例子 K = 0 ），那么

For 3-Way quicksort, f(n) = c*n because you go through the array, check where to place each item and eventually make a swap. This places us in Case 2 of the Master Theorem, which states that if f(n) = O(n^(log_b(a)) log^k(n)) for some k >= 0 (in our case k = 0) then

T(n) = O(n^(log_b(a)) log^(k+1)(n)))

由于 A = 3 和 B = 3 （我们把这些从递推关系， T（N）=为（N / B）），这简化了

As a = 3 and b = 3 (we get these from the recurrence relation, T(n) = aT(n/b)), this simplifies to

T(n) = O(n log n)

和这是一个证明