D-ary堆實現Dijkstra的算法

Question

正如你可以在這個鏈接看到：http://en.wikipedia.org/wiki/D-ary_heap#Applications 它在維基百科說，最佳的選擇d是d = m/n（它導致總的時間複雜度爲O（米logm/nn））

在我看來，這個猜測是空空如也。有沒有一種簡單的方法來證明（甚至解釋）這確實是最優的d？

在此先感謝

Answer 1

從解釋本身可以抵扣，你有N個刪除分鐘操作的O(log(n)/log(d))每個都需要O(d log(n)/log(d))和M降低優先級的操作。合併後的工作是(m*log(n)+n*d*log(n))/log(d)。

如果填寫建議的d值，則全局行爲如O(m*log(n)/log(d))所述。如果您採用其他任何d，則其中一個條件大於平均值，導致複雜性增加。