这个算法叫什么?时间复杂度是多少？
让我们调用可用内存的数量R。
我们有一个10的未排序文件与一列键(允许重复)。
您将文件拆分为k个文件，每个文件的大小为R。您对每个文件进行排序并将文件写入磁盘。
您将(10 / R)从每个文件中读取到输入缓冲区中。执行k路合并，从第一个文件中读取第一个键，并将其与输入缓冲区中的每个其他键进行比较，以找到最小值。您可以将其添加到输出缓冲区中，该缓冲区还应该保存(10 / R)的数据。
输出缓冲区满后，将其写入磁盘到最终排序文件。
重复此过程，直到完全读取所有k文件为止。如果输入缓冲区为空，则使用相应文件的下一个(10 / R)内存填充，直到文件被完全读取为止。我们可以并行地进行缓冲区填充。
这个算法的正式名称是什么？这是一种K路合并类型吗？
第一部分，我们分裂成K文件的部分是O((n / k) log (n / k))第二部分，其中合并的是O(nk)？
如果我错了，我能解释一下吗？如果这是外部合并排序，我们如何进一步优化它？
回答 2
Stack Overflow用户
发布于 2017-08-18 19:00:37
这是一本教科书外部合并排序时间复杂度O(n log )
这是维基百科的条目(链接在上面)：
外部排序的一个例子是外部合并排序算法，它将每个块都放入RAM中进行排序，然后将已排序的块合并在一起。例如，为了仅使用100兆内存对900兆字节的数据进行排序： 用一些传统的方法读取主存和排序中100 MB的数据，比如快速排序。 将已排序的数据写入磁盘。 重复步骤1和步骤2，直到所有数据都被排序为100 MB块(有900 MB/100 MB=9块)，现在需要合并到一个输出文件中。 将每个排序块的前10 MB (= 100 MB /(9个块+ 1))读入主内存中的输入缓冲区，并为输出缓冲区分配剩余的10 MB。(在实践中，它可能提供更好的性能，使输出缓冲区更大，而输入缓冲区稍微更小。) 执行9路合并，并将结果存储在输出缓冲区中.每当输出缓冲区填充时，将其写入最终排序文件并将其清空。每当这9个输入缓冲区中的任何一个清空时，使用其关联的100 MB排序块中的下一个10 MB填充，直到没有更多来自该块的数据可用为止。这是使外部合并排序在外部工作的关键步骤--因为合并算法只对每个块进行一次顺序遍历，每个块不必完全加载；相反，可以根据需要加载块的顺序部分。从历史上看，有时使用替代选择算法来执行初始分布，从而平均产生两倍长度的输出块。
Stack Overflow用户
发布于 2017-08-18 18:48:19
我认为它是一种合并算法，确切的文件IO是实现细节。
https://stackoverflow.com/questions/45763105
复制相似问题
腾讯云开发者
