自然k路合并算法超时，当它已经是N*LogN时？

Question

我正在做以下作业。我们应该了解c++的基础知识以及一些普通和高级的排序算法：

使用自然 k 路合并模拟外部排序算法。

给定一个包含 N 个元素 x_i的序列、同时合并的游程数 K 以及步骤数 A。

确定每个步骤之后的顺序。如果序列在 A 步骤之前排序，则终止该过程。

输入的限制是：

• 1 <= N <= 10⁶
• 2<= K <= 10
• 1 <= A <= 20
• 1 <= x_i <= 10⁹

我应该在 A 步骤之后打印序列。

测试通过

make

完成。

我的代码在某些输入上超时。默认限制是 2 秒，我尝试了 10 秒，但仍然超时，尤其是使用较大的输入，如 N=10⁶、K=10 和 A=20。

此外，当我尝试将测试用例粘贴到终端时，出现分段错误。

我找不到导致此问题的原因。我很确定该算法也应该是 O(nlogn)。

有些人建议在某处使用优先级队列，但在分配此任务之前我们还没有涵盖它，所以我怀疑是否需要解决此挑战。

我的代码：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// Function to merge k vectors
vector<int> mergeK (vector<vector<int>> vectors, int k) {
    vector<int> merged = vectors[0];
    
    for (int i = 1; i < k; i++) {
        vector<int> temp;
        merge(merged.begin(), merged.end(), vectors[i].begin(), vectors[i].end(), back_inserter(temp));
        merged = temp;
    }
    return merged;
}

int main() {
    
    int N, K, A;
    // We will merge A times, K sequences at once
    cin >> N >> K >> A;
    
    int prev = 0;
    int numRuns = 1;
    vector<vector<int>> runs(1);
    
    if (N == 1) {
        cin >> prev;
        cout << prev << '\n';
        return 0;
    }
    
    cin >> prev;
    runs[0].push_back(prev);

    for (int i = 1; i < N; i++) {
        int x;
        cin >> x;
        if (x >= prev) {
            runs[numRuns - 1].push_back(x);
        } else {
            runs.push_back(vector<int>()); 
            runs[numRuns].push_back(x);
            numRuns++;
        }
        prev = x;
    }

    /*for(int i = 0; i <= numRuns; i++) {
        for (int j = 0; j < runs[i].size(); j++) {
            cout << runs[i][j] << " ";
        }
        cout << "| ";
    }*/

    int numUnmerged = numRuns;
    vector<vector<int>>& merged = runs;
    
    for (int i = 0; i < A; i++) {
        vector<vector<int>> temp;
        
        // Merge K vectors
        while(numUnmerged >= K) {
            temp.push_back(mergeK(merged, K));
            numUnmerged -= K;
            merged.erase(merged.begin(), merged.begin() + K);
        }

        // If the number of runs is not divisible by K, merge the remaining runs
        if(numUnmerged < K && numUnmerged != 0) {
            temp.push_back(mergeK(merged, numUnmerged));
            merged.erase(merged.begin(), merged.begin() + numUnmerged);
        }
        
        // The new number of runs after the i-th merge is equal to the number of vectors in temp, 
        // and we update the merged vector for the next merge step
        numUnmerged = temp.size();
        merged = temp;
        
        // If at any point there is only one vector left in temp/merged, it means the sequence is sorted
        if (numUnmerged == 1) break;
    }

    // Print the sequence
    for(int i = 0; i < merged.size(); i++) {
        for (int j = 0; j < merged[i].size(); j++) {
            cout << merged[i][j] << " ";
        }
    }

    return 0;
}

Answer 1

您的代码的主要问题似乎在于您在 mergeK 函数中执行 K 路合并的方式。您可以通过使用 std::merge 一次顺序合并两个序列来合并 K 个序列，这对于大型序列来说效率低下，并且可能导致每次合并的时间复杂度为 O(N * K)，特别是对于较大的 N 和 K 值。

此外，您正在对向量使用擦除操作，其复杂度为 O(N)，因为它们需要移位元素。在处理大型数据集时，这会显着减慢您的程序速度。

为了提高算法的效率，您应该：

1. 实现高效的 K-Way 合并：使用优先级队列（最小堆） 有效地执行K路合并。通过使用优先级队列， 您可以在每个合并步骤的 O(N log K) 时间内合并 K 个排序序列。 与相比，该方法显着降低了时间复杂度 一次按顺序合并两个序列。

2. 避免昂贵的擦除操作：而不是在向量上使用擦除， 这是一个 O(N) 操作，使用双端队列来存储您的运行。双端队列 允许在两端高效插入和删除（O(1) 时间） pop_front 和 pop_back 操作的复杂性）。修改你的代码 使用双端队列：

   deque<vector<int>> runs;

更新合并循环以使用 pop_front 而不是擦除。

3. 通过引用传递向量：确保传递大向量 通过引用（如果您不打算，最好作为 const 引用 修改它们）以避免不必要的数据复制。修改 mergeK 函数的签名。

希望它能有所帮助。