知识卡片

普通读书笔记卡 · 3615.d.1.a.1.a

期望比较次数是调和和

理解等级:高级

在元素互异的前提下,对每对元素设置是否比较的指示变量;每对至多比较一次。用概率 2/(j−i+1) 与期望线性性求和,得 O(n log n) 期望比较次数,进而得随机快排 O(n log n) 期望时间;同值键需另分析。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 ).