5

我正在观看有关合并排序的 Coursera Princeton 算法讲座，我了解所有分析，除了合并最多 6 n log n 数组访问。

为什么是6？

4

2 回答 2

2

为了获得 6 次数组访问，一个效率低下的合并过程：

read  - read an element from even run for compare
read  - read an element from odd  run for compare
      - compare
read  - read the lower element again for copy
write - write the lower element to the output array for copy
...   - after merge copy back
read  - read element from output array to copy back
write - write element back to original array to copy back

正常情况是对每个移动的元素进行一次读取和一次写入，但考虑到元素太大而无法放入变量（如字符串）的情况，因此在比较之后，必须再次读取要移动的字符串。

通常可以避免复制回操作，这取决于合并排序的编码方式。

于 2015-10-21T17:55:03.173 回答
0

我也想知道 6。我看了 Tim Roughgarden 的分析（视频 '1 - 7 - Merge Sort- Analysis (9 min).mp4'），他也说 6。每个解释都感觉像是在挥手，但也许是因为它太简单了，他们没有意识到需要解释：

当您复制到辅助数组时，您为每个 n（或 k）访问一个数组两次 aux[k] = a[k]; 然后，在最坏的情况下，您永远不会耗尽一个子数组（您只比较常量），这样您就有四个数组访问 else if (less(aux[j], aux[i])) a[k] = aux[j++];（例如，如果输入是相反的顺序）或每次比较失败并且 else 在比较之后启动（正确的顺序），或者两者的某种组合。没关系，只是根据最坏情况的定义，您无法通过常量（使用if (i > mid)or else (j > hi)）转义数组访问，因此每个 k 都有四个。总数为 6。

（每一行代码都是 Sedgewick 的 - 他的文本的第 p271 页。）

于 2016-02-26T03:49:07.430 回答