我正在尝试学习复杂性分析以及如何根据第一性原理进行分析。以QuickSort为例，我希望能够推导出该算法的平均情况复杂度的O符号表达式。
我知道 QuickSort 是 O(nlog(n)) 并且我理解为什么它必须在每次迭代时传递 n 个元素，并且递归深度是 log n。但我不知道你如何用第一原理来证明这一点，即计算原始操作。
最佳答案
Knuth，在计算机编程艺术，第 3 卷(排序和搜索)，第 5.2.2 节(按交换排序)中，详分割析了快速排序的具体实现(在 MIX 中， 当然)。他可能是世界上唯一愿意为人类消费而手动进行此类分析的人。
关于algorithm - 从第一性原理分析 QuickSort 的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10399641/