从第一原则对快速排序进行复杂性分析

Question

我正在尝试从第一原理学习复杂性分析以及如何执行它。以 QuickSort 为例，我希望能够为该算法的平均大小写复杂度导出一个 O 表示法表达式。

我知道 QuickSort 是 O（nlog（n）），我明白为什么，它必须在每次迭代时传递 n 个元素，并且递归深度是 log n。但我不知道你会如何用第一原理来证明这一点，即计算原始操作。

Answer 1

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