知识卡片
归并每层线性且分割层数受控
归并每次按位置近似对半分割,达到单元素需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:归并排序的实现