Google到的快排时空复杂度的计算，涉及到很多数学定理，看的不太懂。老师你能从代码的实现中指导下时空复杂度的计算吗？因为我觉得从具体代码分析更易懂
哈哈哈蜜瓜 2017-07-02 22:29:58
源自：3-8 三路快速排序法
liuyubobobo 2017-07-03 02:30:26
首先，我必须指出，复杂算法的复杂度计算本身就是困难的，对数学的要求是高的（下面我会介绍快排为什么在复杂度计算的角度看是“复杂”的）。所以，我个人不是很建议本科水平的学生去理解严谨的复杂度计算。还是应该以算法本身的实现学习为主，对复杂度有一个大致的概念就好。在我的课程《玩转算法面试》（玩转算法面试_互联网公司算法面试真题-慕课网实战）的第二章，我总结了本科水平需要掌握的算法复杂度的大致水平。通常公司的面试达到这一水平即可。我没有听说过任何一家公司，就算是FLAG，面试问题中包含：请严格推导出快速排序的时间复杂度。。。：）
不过，如果对这一部分感兴趣，确实就要把数学学好。有一个专门的领域，就是复杂度的研究。有兴趣可以查看一下相关资料。快排的时间复杂度的严谨计算之所以复杂。是因为当我们使用随机化的方式选择pivot以后，快排的每一次partition的结果是不确定的。其实即使不是随机化的选择pivot，给定的数组不同，第一个数字不同，每一次partition划分的结果也不是确定的。（相较而言，归并排序每次都是平分，不管数组是怎样的，是确定的划分，所以时间复杂度的计算简单很多）在这种情况下，快排变成了一个随机化的算法。此时，我们所求的快排的时间复杂度，实际上是快排所消耗时间的“期望值”。我不确定你现在的年龄和数学水平，是否接触过概率。期望值是概率论中的一个基本概念。你可以简单的理解成是平均情况。
我假设你已经理解了归并排序的时间复杂度是O(nlogn)。在这种情况下，快排虽然每次partition将数组的两部分分的不平均，但是直观理解，在随机情况下，这次左边多一点；下次右边多一点，平均下来，整体上也是平衡的，划分的层数和归并是在一个数量级上的，都是logn这个级别的。所以快排的时间复杂度也是O(nlogn)的。
当然，我上面的介绍太粗糙，里面有太多的细节，确实需要数学基础。如果想深刻理解其中的缘由，数学是逃不掉的。我的课程《玩儿转算法面试》中，也给出了一个“验证”时间复杂度的方法，通过这个方法，你可以大概验证快排平均时间复杂度确实是O(nlogn)级别的。但是具体的证明是另外一回事儿。希望上面的介绍能够让你大概理解快排的时间复杂度是O(nlogn)这样的一个结论。如果希望学习非常严谨的证明，就要啃下数学这块硬骨头：（