algorithm - 外部排序阶段的组合复杂度

Question

外部排序复杂性已得到很好的描述 here .在第 2 页和第 3 页上，它很好地描述了 phase1 和 phase2。我了解每个步骤中描述的复杂性。我的问题是 总结阶段 1 和阶段 2 的成本，我们得到总运行时间
Θ(n log2
(n/m)) 在第 4 页提到。在伪代码之后。

据我了解 - 第一阶段的复杂性是:O(MlogM) 对主内存缓冲区中的所有记录进行排序。因此，我们有效地填充缓冲区 N/M 次 O(N/M * M log M)，即 O(NlogM)。

如何:

阶段 1:O(NlogM)。

和

阶段 2:Θ(n log m/n)

组合结果为 Θ(n log2(n/m)) ??

Answer 1

在评估外部算法的性能时，我们通常只计算执行算法所需的磁盘操作数。论文定义了n = N/B和m = M/B。

阶段 1 实际上只需要 Θ(n) 磁盘操作，因为我们只读取和写入每个 block 一次。现在很明显 Θ(n) + Θ(n log n/m) = Θ(n log n/m)