complexity-theory - 使用 d-ary 堆实现 Dijkstra 算法

Question

正如您在此链接中看到的那样：http ://en.wikipedia.org/wiki/D-ary_heap#Applications 它在维基百科中说 d 的最佳选择是 d=m/n （它导致总时间复杂度为O(m logm/nn) )

在我看来，这个猜测是凭空捏造的。有没有一种简单的方法可以证明（甚至解释）这确实是最优的 d ？

提前致谢

Answer 1

从解释本身中，您可以推断出您有 n 个删除 min 操作O(d log(n)/log(d))，每个操作都需要 m 个减少优先级操作O(log(n)/log(d))。那么合并的工作就是(m*log(n)+n*d*log(n))/log(d)。

如果填写建议的 d 值，则全局行为如所述O(m*log(n)/log(d))。如果您取任何其他 d，则其中一项大于平均值，从而导致复杂性增加。