我正在解决一个问题,其中我有80GB
需要排序的数据。我只有1GB
主存储器来对数据进行排序。显然,我们将在这里应用外部排序方法。但我的问题是哪种 k-merge 排序会更有效?
- 8路合并后10路合并
- 5路合并后16路合并
K-merge 排序的复杂度是O(nk^2)
,其中 n 是元素的数量。假设我使用这种方法来计算复杂度:
8路合并后10路合并
8 way merge - O(n*8^2) => O(64n)
10 way merge - O(8n*10^2) => O(800n)
Total time complexity => O(64n) + O(800n)
5路合并后16路合并
5 way merge - O(n*5^2) => O(25n)
16 way merge - O(5n*16^2) => O(1280n)
Total time complexity => O(25n) + O(1280n)
查看时间复杂度5 way merge followed by 16 way merge
似乎需要更多时间。你觉得我的流程对吗?我对此不是很有信心。
更新:@rcgldr 既然你说更大的块大小将花费更少的时间来读/写那么你如何看待这个公式:
Time to read/write 1 block = Average Seek time +
Average rotational latency + blocksize/Maximum Transfer Rate
根据这个公式,如果块大小很小,那么整体读/写时间也会更短。你觉得这里有什么问题吗?或者我们需要将块的总数与此相乘才能准确了解所需的总时间。