知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.12 · 生成模型:未记录

归并每层线性且分割层数受控

理解等级:中级

归并每次按位置近似对半分割,达到单元素需O(log n)层;每一层所有子区间合并总计处理n项,固定比较/复制模型下总成本O(n log n)。顺序良好或不好不改变本例按位置递归的分区形状。

02962把[82,70,11,72,25,36,44,10]逐级分开,再合并成[10,11,25,36,44,70,72,82]。02961单次合并的是[11,70,72,82]与[10,25,36,44],并非无需预排序就能一次合成有序结果。

实际merge只在两边递归都返回后分配当前区间缓冲,复制回后即free,因此不必把每层缓冲都假定同时存活;峰值还需计当前缓冲与递归栈。元素宽度、比较成本和分配器仍不自动为常数。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      O(q+p),因为为了产生一个合并的集,必须遍历两个集的每个元素。由于对应每个lg n级的分割,都需要遍历n个元素合并该级的集合,因此归并排序的时间复杂度为O(nlg n)。又因为归并排序需要额外的存储空间,所以必须要有两倍于要排序数据的空间来处理此算法。 示例12-5:归并排序的实现

    参考来源

    - 位置:《算法精解:C语言描述》第12章《归并排序的实现与分析》(spine1346;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1312.html;u214-ch12-013)。 - 结论依据:214完整递归/层数/合并分析与02961–02966图及全函数实读,核对缓冲在回归阶段创建/释放,没有相同层所有缓冲同时保留。 - 原始内容:O(q+p),因为为了产生一个合并的集,必须遍历两个集的每个元素。由于对应每个lg n级的分割,都需要遍历n个元素合并该级的集合,因此归并排序的时间复杂度为O(nlg n)。又因为归并排序需要额外的存储空间,所以必须要有两倍于要排序数据的空间来处理此算法。 示例12-5:归并排序的实现