Dijkstra 算法的大 O 与 D-Ary 堆
Big-O of Dijkstra's Algorithm with D-Ary Heap
我正在寻找使用 D-Ary 堆实现 Dijkstra 算法运行时的完整演练。
我目前最好的理解是树的深度最多为log_d(n)，所以插入和冒泡的最大时间为log_d(n)。删除节点时冒泡会不会一样？
我只是无法将所有东西拼凑在一起以在此处找到总的 Big-O 运行时。我的理解是它应该是 O(m logm/n n))，但我想通过一种演练来理解为什么会这样。
在 d-ary 堆中，up-heaps（例如，插入，decrease-key 如果您在堆节点移动时跟踪它们）需要时间 O(log_d n)和 down-heaps（例如，delete-min）需要时间 O(d log_d n)，其中 n 是节点数。 down-heaps比较贵的原因是我们要找到最小的child来推广，而up-heaps只是和parent比较。
假设一个连通图，Dijkstra最多使用m - (n - 1) decrease-keys和最多n - 1 inserts/deletes（假设我们从不插入根）。因此，Dijkstra 使用 d-ary 堆作为优先级队列的 运行 时间为 O((m + n d) log_d n)，这对于密集图来说是值得的。
我正在寻找使用 D-Ary 堆实现 Dijkstra 算法运行时的完整演练。
我目前最好的理解是树的深度最多为log_d(n)，所以插入和冒泡的最大时间为log_d(n)。删除节点时冒泡会不会一样？
我只是无法将所有东西拼凑在一起以在此处找到总的 Big-O 运行时。我的理解是它应该是 O(m logm/n n))，但我想通过一种演练来理解为什么会这样。
在 d-ary 堆中，up-heaps（例如，插入，decrease-key 如果您在堆节点移动时跟踪它们）需要时间 O(log_d n)和 down-heaps（例如，delete-min）需要时间 O(d log_d n)，其中 n 是节点数。 down-heaps比较贵的原因是我们要找到最小的child来推广，而up-heaps只是和parent比较。
假设一个连通图，Dijkstra最多使用m - (n - 1) decrease-keys和最多n - 1 inserts/deletes（假设我们从不插入根）。因此，Dijkstra 使用 d-ary 堆作为优先级队列的 运行 时间为 O((m + n d) log_d n)，这对于密集图来说是值得的。