二叉堆密集图上的 Dijkstra 线性运行时间

发布于 2025-01-08 14:44:04 字数 572 浏览 0 评论 0原文

第一：Dijkstras 最短路径算法的一般运行时间为

Dijkstra Generalrunning time

其中 m 是边数和 n 顶点数

第二：预期的减少键操作数如下

expected running time

第三：带有二进制堆的 dijkstra 的预期运行时间，允许在 log(n) 时间内执行所有操作

expected binary heap

但是，如果我们考虑一个图稠密的话，为什么稠密图上的运行时间是线性的 dense graph

有人可以帮助这里的 O 表示法和日志计算吗？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

抱着落日 2025-01-15 14:44:04

首先，不难证明如果m是n log(n) log(log(n))的大欧米伽，那么log(n)< /code> 是 log(m) 的大欧米伽。因此，您可以证明 m 是 n log(m) log(log(m)) 的大欧米伽。

由此可以看出，n 是 m / (log(m) log(log(m))) 的大欧米伽。

将其代入第三点中的表达式，我们得到预期的运行时间为：

O(m + n log(m/n) log(n))

                   m                                                 m
    = O(m + (------------------) log(log(m) log(log(m))) log(------------------)
             log(m) log(log(m))                              log(m) log(log(m))

从这里您可以将所有乘积日志展开为日志总和。你会得到很多条款。然后这只是一个证明每个人都是O(m)或o(m)的问题。这很简单，但很乏味。

First it isn't hard to show that if m is big omega of n log(n) log(log(n)) then log(n) is big omega of log(m). Therefore you can show that m is big omega of n log(m) log(log(m)).

From this you can show that n is big omega of m / (log(m) log(log(m))).

Substitute this back into the expression you have in the third point and we get that the expected running time is:

O(m + n log(m/n) log(n))

                   m                                                 m
    = O(m + (------------------) log(log(m) log(log(m))) log(------------------)
             log(m) log(log(m))                              log(m) log(log(m))

From here you can expand all of the logs of products into sums of logs. You'll get a lot of terms. And then it is just a question of demonstrating that every one is O(m) or o(m). Which is straightforward, though tedious.

回复收藏 0 原文