algorithm - 从第一原理开始快速排序的复杂性分析

Question

我正在尝试了解复杂性分析以及如何从第一原理中执行它。以 QuickSort 为例，我希望能够推导出该算法的平均情况复杂度的 O-notation 表达式。

我知道 QuickSort 是 O(nlog(n)) 并且我理解为什么，它必须在每次迭代中传递 n 个元素，并且递归深度是 log n。但我不知道你将如何用第一原则来展示这一点，即计算原始操作。

Answer 1

Knuth 在《计算机编程艺术》第 3 卷（排序和搜索）第 5.2.2 节（按交换排序）中详细分析了快速排序的具体实现（当然是在 MIX 中）。他可能是世界上唯一一个愿意手工进行这种分析以供人类消费的人。