题库 信息学奥赛题库 题目列表 对一个 n 个顶点,m 条边的带正权有向...
单选题

对一个 个顶点,条边的带正权有向简单图使用 Dijkstra 算法计算 单源最短路时,如果再使用一个可以在 Θ(log n) 时间复杂度内查询堆内最

小值、在 Θ(𝑛) 时间复杂度内合并两个堆、在 Θ(1) 时间复杂度内将堆内 一个元素变小、在 Θ(log𝑛) 时间复杂度内弹出堆内最小值的堆优化

Dijkstra 算法,则整个 Dijkstra 算法的时间复杂度为 ( )。

A.

Θ(𝑛𝑛 + 𝑚 log 𝑛)

B.

Θ((𝑛 + 𝑚) log 𝑛)

C.

Θ(𝑚+𝑛log𝑛)

D.

Θ(𝑚𝑛 + 𝑛 log 𝑛)

题目信息
选择题 练习 2021年
50%
正确率
0
评论
144
点击