我如何证明快速排序的主定理

Question

我对算法，快速排序有疑问。有人可以解释一下我如何得出结果（证明）2T（n / 2）+？（n）吗？结果意味着：T（n-1）+？（n）。

感谢所有答案。

Answer 1

大师定理指出，

对于任何 ，

1. 如果 对于一些常数 ， 然后 。
2. 如果 ， 然后 。
3. 如果 ，对于一些常数 ， 而如果 对于一些常数 而且都足够大 ， 然后

至于你的
，

这里，
（第二个条件）
因此复杂度将为：

关于第二个问题，请了解此功能 ，您需要了解分而治之的方法。在快速排序中，对于n个项目，如果您将最后一个值作为轴，则项目数将减少1，这将使项目数减少到（n-1），现在，如果您递归调用以最后一个值作为轴，每次减少一项。因此，复杂度将是，当您将中间值作为枢轴时，情况并非如此。