问从第一性原理分析QuickSort的复杂性
EN

Stack Overflow用户

提问于 2012-05-01 23:05:02

回答 1查看 857关注 0票数 2

我正在尝试学习复杂性分析，以及如何从基本原则开始执行它。以QuickSort为例，我希望能够推导出该算法的平均情况复杂度的O符号表达式。

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

回答已采纳

发布于 2012-05-02 22:03:21

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

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/10399641

复制

相似问题

问从第一性原理分析QuickSort的复杂性EN