最短路径问题

小白1379

第7题选哪？原因是？

来自Android客户端

liuzuhagn

对于保存最短路径的结构，可能进行的操作有更新元素值并维持属性以及选择最小元素。对于这两种操作，各选项复杂度如下：
A项，无序线性表，分别为O(1)，O(n)
B项，有序线性表，分别为O(n)，O(1)
C项，最小堆，分别为O(㏒n)，O(1)，哇哦～～
D项，二叉搜索树，分别为O(㏒n)，O(㏒n)

综上我会选择C

来自Android客户端

小白1379

liuzuhagn 发表于 2015-12-10 23:20
对于保存最短路径的结构，可能进行的操作有更新元素值并维持属性以及选择最小元素。对于这两种操作，各选项 ...

有人找到出处了 但不知道为啥 是期末考试题

来自Android客户端

liuzuhagn

果然稠密图是坑，我却没当回事……这样的话这题选无序线性表才对哦，然后我说说稠密和稀疏那个问题啵

Dijkstra算法主体是个循环，每次循环干两个事：一是要找到当前还没找到最短路径的节点中，距离源点最近的那个节点，假设复杂度为O(findmin)；二是对上边那个节点进行松弛，这块就有意思了，如果是稠密图，意味着边比较多，一个节点需要松弛的边更接近总节点个数，假设一次松弛操作的O(relaxation)，一个节点的松弛总复杂度为O(V*relaxation)；如果是稀疏图，边就少，需要松弛的边近似于总边数，于是总体松弛复杂度为O(E*relaxation)。
综上，这样算法总体复杂度长这样：
稠密图，O(V*(findmin + V*relaxation))。
稀疏图，O(V*findmin + E*relaxation)。

这样
无序线性表findmin为V，relaxation为1
稠密图：O(V²)
稀疏图：O(V²)
有序线性表findmin为1，relaxation为V
稠密图：O(V∧3)
稀疏图：O(EV)
堆findmin为1，relaxation为㏒V
稠密图：O(V²㏒V)
稀疏图：O(E㏒V)
搜索二叉树findmin为㏒V，relaxation为㏒V
稠密图：O(V²㏒V)
稀疏图：O(E㏒V)

来自Android客户端

小白1379

liuzuhagn 发表于 2015-12-11 20:33
果然稠密图是坑，我却没当回事……这样的话这题选无序线性表才对哦，然后我说说稠密和稀疏那个问题啵

Dijk ...

多谢大神~ 我基础不太好 我再仔细看下你说的

来自Android客户端

暮雨泉林1

你这是什么试卷？

来自Android客户端