blocks|key|1302784|text|我认为它是一种合并算法，确切的文件IO是实现细节。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1302785|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Merge_algorithm^0|5|6|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

I'd say it's <a href="https://en.wikipedia.org/wiki/Merge_algorithm" rel="nofollow noreferrer">a merge algorithm</a>, exact file IO is an implementation detail.

blocks|key|2596440|text|这是一本教科书外部合并排序时间复杂度O(n+log+)|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2596441|这是维基百科的条目(链接在上面)：|2596442|外部排序的一个例子是外部合并排序算法，它将每个块都放入RAM中进行排序，然后将已排序的块合并在一起。例如，为了仅使用100兆内存对900兆字节的数据进行排序：
用一些传统的方法读取主存和排序中100+MB的数据，比如快速排序。
将已排序的数据写入磁盘。
重复步骤1和步骤2，直到所有数据都被排序为100+MB块(有900+MB/100+MB=9块)，现在需要合并到一个输出文件中。
将每个排序块的前10+MB+(=+100+MB+/(9个块%2B+1))读入主内存中的输入缓冲区，并为输出缓冲区分配剩余的10+MB。(在实践中，它可能提供更好的性能，使输出缓冲区更大，而输入缓冲区稍微更小。)
执行9路合并，并将结果存储在输出缓冲区中.每当输出缓冲区填充时，将其写入最终排序文件并将其清空。每当这9个输入缓冲区中的任何一个清空时，使用其关联的100+MB排序块中的下一个10+MB填充，直到没有更多来自该块的数据可用为止。这是使外部合并排序在外部工作的关键步骤--因为合并算法只对每个块进行一次顺序遍历，每个块不必完全加载；相反，可以根据需要加载块的顺序部分。从历史上看，有时使用替代选择算法来执行初始分布，从而平均产生两倍长度的输出块。|blockquote|2596443|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/External_sorting#External_merge_sort^0|7|6|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|6|7|U|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|V|8|@]|9|@]|C|$]]|$1|I|3|-4|5|6|7|W|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

This is a textbook <a href="https://en.wikipedia.org/wiki/External_sorting#External_merge_sort" rel="nofollow noreferrer">external merge sort</a> Time complexity O(n log n)

Here's Wikipedia's entry on it (linked above):

<blockquote>
 One example of external sorting is the external merge sort algorithm,
 which sorts chunks that each fit in RAM, then merges the sorted chunks
 together. For example, for sorting 900 megabytes of data using
 only 100 megabytes of RAM: &nbsp;&nbsp;&nbsp; 1) Read 100 MB of the data in main memory and
 sort by some conventional method, like quicksort. &nbsp;&nbsp;&nbsp; 2) Write the sorted
 data to disk. &nbsp;&nbsp;&nbsp; 3) Repeat steps 1 and 2 until all of the data is in sorted
 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to
 be merged into one single output file. &nbsp;&nbsp;&nbsp; 4) Read the first 10 MB (= 100MB /
 (9 chunks + 1)) of each sorted chunk into input buffers in main memory
 and allocate the remaining 10 MB for an output buffer. (In practice,
 it might provide better performance to make the output buffer larger
 and the input buffers slightly smaller.) &nbsp;&nbsp;&nbsp; 5) Perform a 9-way merge and
 store the result in the output buffer. Whenever the output buffer
 fills, write it to the final sorted file and empty it. Whenever any of
 the 9 input buffers empties, fill it with the next 10 MB of its
 associated 100 MB sorted chunk until no more data from the chunk is
 available. This is the key step that makes external merge sort work
 externally -- because the merge algorithm only makes one pass
 sequentially through each of the chunks, each chunk does not have to
 be loaded completely; rather, sequential parts of the chunk can be
 loaded as needed. Historically, instead of a sort, sometimes a
 replacement-selection algorithm was used to perform the initial
 distribution, to produce on average half as many output chunks of
 double the length.
</blockquote>

Let's call the amount of RAM available R.

We have an unsorted file of 10 gigs with one column of keys (duplicates allowed).

You split the file into k files, each of which have size R.
You sort each file and write the file to disk.

You read (10 / R) gigs from each file into input buffers. You perform a k-way merge where you read the first key from the first file and compare to every other key in your input buffers to find the minimum. You add this to your output buffer which should also hold (10 / R) gigs of data.

Once the output buffer is full, write it to disk to a final sorted file.

Repeat this process until all k files have been fully read. If an input buffer is empty, fill it with the next (10 / R) gigs of its corresponding file until the file has been entirely read. We can do this buffer refilling in parallel.

What is the official name for this algorithm? Is it a K - Way Merge sort?

The first part, where we split into K files is O((n / k) log (n / k))
The second part, where we merge is O(nk)?

If I am wrong, can I have an explanation? If this is external merge sort, how do we optimize this further?

What is this algorithm called and what is the time complexity?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

让我们调用可用内存的数量R。我们有一个10的未排序文件与一列键(允许重复)。您将文件拆分为k个文件，每个文件的大小为R。您对每个文件进行排序并将文件写入磁盘。您将(10 / R)从每个文件中读取到输入缓冲区中。执行k路合并，从第一个文件中读取第一个键，并将其与输入缓冲区中的每个其他键进行比较，以找到最小值。您可以将其添...

问这个算法叫什么?时间复杂度是多少？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问这个算法叫什么?时间复杂度是多少？EN