知识卡片
期望比较次数是调和和
在元素互异的前提下,对每对元素设置是否比较的指示变量;每对至多比较一次。用概率 2/(j−i+1) 与期望线性性求和,得 O(n log n) 期望比较次数,进而得随机快排 O(n log n) 期望时间;同值键需另分析。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第7章 快速排序 · 查看原书依据
The expected running time of RANDOMIZED-QUICKSORT on an input of n distinct elements is O(n lg n).
参考来源
- 位置:《算法导论(第4版)》第 7 章定理 7.4(`OEBPS/chapter007.xhtml`,文本字符 [28600, 30500);Art_P315–P321)。
- 结论依据:原文用指示变量、期望线性性、调和级数上界和引理 7.1 完成推导。
- 原始内容:The expected running time of R ANDOMIZED -Q UICKSORT on an input of n distinct elements is O ( n lg n ).