知识卡片
归并排序递归树每层成本相同
归并排序满足 T(n)=2T(n/2)+Θ(n)。在二的幂规模下,递归树每往下一层,节点数翻倍、各节点处理量减半,整层仍耗 Θ(n);约有 lg n 层,总时间 Θ(n lg n)。
非二的幂规模须核对取整项。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第2章 算法入门 · 查看原书依据
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.
参考来源
- 位置:《算法导论(第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.