知识卡片
归并过程线性扫描两个有序段
归并两个有序段时,只比较各段尚未取出的首元素,每次向结果写入一个值;一段耗尽后复制另一段余项。
每个元素恰写回一次,因此归并用 Θ(n) 时间;相等时先取左段,可保持跨段相等元素的原次序。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第2章 算法入门 · 查看原书依据
each iteration of these loops copies exactly one value from L or R back into A and that every value is copied back into A exactly once.
参考来源
- 位置:《算法导论(第4版)》第 2 章 2.3.1 节 `MERGE` 伪代码及图 2.3(`OEBPS/chapter002.xhtml`)。
- 结论依据:原文给出三个循环和每个元素写回一次的复杂度证明;稳定性由 `L[i] ≤ R[j]` 的分支条件推得。
- 原始内容:each iteration of these loops copies exactly one value from L or R back into A and that every value is copied back into A exactly once.