外部合并排序的时间复杂度/成本

Question

我从一个讨论外部合并排序的链接中得到了这个结果。

从幻灯片6示例:使用5个缓冲区页对108页文件进行排序

• Pass0: 108/5 = 22次排序运行，每次5页(最后一次只运行3页)
• Pass1 22/4 =6次排序运行，每次20页(最后一次只运行8页)
• Pass2: 6/3 =2次排序运行，80页和28页
• 传递3: 2/2 = 108页排序文件

问:我的理解是外部合并排序，在pass 0中创建块，然后对每个块进行排序。在剩下的传球中，您将继续合并它们。因此，将其应用到上面的示例中，因为我们只有5个缓冲区页，所以在传递0时，我们需要22次排序运行，每次运行5页。

1. 现在，我们为什么要为剩余的传球或合并进行排序运行呢？
2. 当我们只有5个缓冲区页时，它为什么会告诉pass 1，6个排序的运行，每个20页？
3. 合并到底发生在哪里？每过一次，即从108次降到22次，从6次降到2次，氮是如何减少的？

Answer 1

当无法将所有数据存储到内存中时，外部合并排序是必要的。您所能做的最好是将数据分解为排序的运行，并在随后的传递中合并运行。运行的长度与可用缓冲区大小相关联。

Pass0：您正在执行相应的操作。因此，您将5页数据加载到缓冲区中，然后使用就地排序算法对其进行排序。这5页将作为运行存储在一起。

通过：您不能再在适当的地方执行操作，因为您合并了许多页面的运行。4页加载到缓冲区，第5页是写缓冲区。合并与合并排序算法相同，但是您将用B-1而不是2的因子进行除法和征服。当写入缓冲区被填充时，它将被写入磁盘并启动下一页。

复杂性：在分析外部合并排序的复杂性时，正在考虑的是I/O的数量。在每一次传递中，您必须读一页并写该页。设N是页数。每次运行将花费2N。读这页，写这一页。

设B是可以容纳缓冲空间的页数，N是页数。

将有ceil(log_B-1(ceil(N/B)通行证。每个通行证将有2N I/O。哦(Nlogn)。

在每次传递中，运行的页面长度都会增加一个B-1倍，而排序运行的次数则会减少一个B-1倍。

Pass0: ceil(108 / 5) = 22，每次运行5页

Pass1: ceil(22 / 4) = 6，每次运行20页

Pass2: ceil(6 /4)=每次运行2，80页

Pass3: ceil(2 /4)=1-已完成，1次运行108页

Answer 2

答:因为它从来没有提到合并，所以我认为(希望)后面的“排序”传递正在进行合并。

B.同样，假设这是合并，您需要一个缓冲区来保存合并的记录，并为正在合并的每个文件使用一个剩余的缓冲区:因此，有4个输入文件，每个w/ 5页: 20页。

C.我想我已经回答过合并是两次了:)