← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3596.a

归并过程线性扫描两个有序段

理解等级:中级

归并两个有序段时,只比较各段尚未取出的首元素,每次向结果写入一个值;一段耗尽后复制另一段余项。

每个元素恰写回一次,因此归并用 Θ(n) 时间;相等时先取左段,可保持跨段相等元素的原次序。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

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