知识卡片

普通读书笔记卡 · 3596.b

归并排序递归树每层成本相同

理解等级:中级

归并排序满足 T(n)=2T(n/2)+Θ(n)。在二的幂规模下,递归树每往下一层,节点数翻倍、各节点处理量减半,整层仍耗 Θ(n);约有 lg n 层,总时间 Θ(n lg n)。

非二的幂规模须核对取整项。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 2 章 2.3.2 节“Analysis of merge sort”(`OEBPS/chapter002.xhtml`,式 2.3、2.4 与图 2.5)。 - 结论依据:原文把分解与归并代价写为递推式,并用递归树逐层求和;相关公式和图已核对。 - 原始内容:Each level has twice as many nodes as the level above, but each node contributes only half the cost of a node from the level above.