算法K-Way合併。這個解決方案是O（n log k）嗎？

所以問題是將k個已排序列表（假設它們按升序排序）合併爲一個使用min堆的n個元素列表。現在我找到了一個解決方案，但我不確定它是否可以有nlogk的運行時間。這是我的僞代碼，你們怎麼看？算法K-Way合併。這個解決方案是O（n log k）嗎？

Algorithm kWayMerge(S) 
    t ← 0 
    Result ← ∅ 
    while t ≤ n do 
     choosenHeap ← min(S1[1], … Sk[1]) 
     t ← t + 1 
     Result[t] ← DeleteMin(choosenHeap) 
    end loop 
end 

Function DeleteMin(H) 
    Min ← A[1] 
    A[1] ← A[size[H]] 
    size[H] ← size[H] - 1 
    DownHeap(H, 1) 
    return Min 
end 

Function DownHeap(A, t) 
    c ← 2*t 
    if c > size[A] then 
     return 
    if c+1 > size[A] && A[c] > A[c + 1] then 
     c ← c + 1 
    temp ← A[t] 
    A[t] ← A[c] 
    A[c] ← temp 
    DownHeap(A, c) 
end

基本上我的解決方案是搜索k列表並找到具有最小根值的Min Heap並將其放入結果數組中。基本上，由於從給定的k個排序列表中移除所有元素，因此kWayMerge中的外部循環將迭代n次。

來源

2016-11-06 McDoogles

你未定義功能'min'。如果它以線性時間運行，那麼代碼將以_O（k n）_運行。 – kgeorgiy

你的算法被稱爲Ideal Merge technique for k-way merge，並在ö確實運行（N日誌（k））的，假設最小堆與對數數據結構來實現（例如，binary heap。

堆被訪問Θ（n）的倍，因爲每個項目被插入並正好一次萃取。
堆包含，在每個點處，至多ķ元素（請注意，有些列表可能會在其他列表之前「耗盡」）。
所有其他操作每個元素的時間是恆定的。

因此，如果每個訪問堆是O（日誌（K '）），其中K'是在堆元件的數量，則總海岸爲O（n log（k））。

來源

2016-11-06 20:41:15

分了運行時間也和這裏的O（K）

所以它的O（NK穩定常數）

來源

2016-11-19 16:45:58 TheDotter

算法K-Way合併。這個解決方案是O（n log k）嗎？

回答

相關問題