数据结构与算法分析问题

Question

我正在寻找这个问题的答案，这个问题来自于一个关于数据结构和算法的类。我了解了合并排序，但不记得集群和缓冲区。我不太明白这个问题。有人能帮忙解释或回答吗？

一个大小为100万个集群的文件将使用一个集群大小的128个输入缓冲区进行排序。有一个集群大小的输出缓冲区。如果使用平衡k路合并排序(一种多步合并)算法，那么需要多少磁盘I/O？

。

Answer 1

它询问磁盘操作的总数，这里的集群可以是任意大小的。

您需要知道平衡k路合并排序的迭代需要多少磁盘IOs。(提示:每次合并传递都需要从磁盘读取和写入数组中的每个值一次)

然后计算出必须执行多少次迭代才能读取数据。

然后可以计算磁盘IOs的总数。