外部合并排序的复杂性是什么？

Question

在wikipedia中，外部排序的时间复杂度如下

（N / B）.log _{（M / B）}（N / B）

其中N是数据的总大小，M是存储器的大小，B是存储器中的块数。在对RAM中的每个块进行排序时，我可以理解日志部分，但是我无法理解日志的基础为M / B。

任何帮助将不胜感激！

Answer 1

在排序阶段之后，合并阶段过程m并行运行，因此您获得了基础m = M/B。

来源：wikipedia.org/wiki/External_memory_algorithm

Answer 2

M是内存大小，...

混乱是由于：

B是内存中的块数。

在Wiki文章中，B是每个块的块大小，因此内存中的块数= M / B。 Wiki的时间复杂度忽略了以下事实：其中一个块用于合并输出，并且该算法使用k方式合并，其中k =（M / B）-1。