知识卡片
归并排序将局部有序合成整体
递归把数组分成更小子数组,单个元素可以直接视为有序,再将两个有序子序列逐层合并,得到全体有序结果。这里合并必须保留全部元素及重复次数,只拼接两个有序序列并不能保证整体有序。它说明分解后的局部成果需要符合原问题要求的整合操作。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
分治算法主要包含3个步骤:分、治、并。 “分”是递归地将原问题分解成小问题;“治”是在解决了各个小问题之后(各个击破之后)合并小问题的解,从而得到整个问题的解;“并”是按原问题的要求,将子问题的解逐层合并,构成原问题的解。 以归并排序为例,该算法在1945年由冯·诺伊曼
参考来源
- 位置:《程序员的底层思维》第7章《分治思维》(来源项目book-sources,`extracted/程序员的底层思维/_epub-src/Cheng Xu Yuan De Di Ceng Si Wei_split_011.html`)。
- 结论依据:原文从“分治算法主要包含3个步骤:分、治、并。 “分”是递归地将原问题分”展开,与本卡的“递归把数组分成更小子数组,单个元素可以直接视为有序,再将两个有序子序列逐层合并,得到全体有序结果”对应;正文额外解释的限制、反例或外部校正均不冒充原书保证。
- 原始内容:分治算法主要包含3个步骤:分、治、并。 “分”是递归地将原问题分解成小问题;“治”是在解决了各个小问题之后(各个击破之后)合并小问题的解,从而得到整个问题的解;“并”是按原问题的要求,将子问题的解逐层合并,构成原问题的解。 以归并排序为例,该算法在1945年由冯·诺伊曼