知识卡片
邻接查找成本要按总边数累计
mst外循环最多V轮,每轮扫描V个顶点取最小key,共O(V²)。被选顶点的邻接边合计扫描E次(无向双向表示按实际邻接条目数计),每次再到全局顶点列表线性找状态O(V),共O(EV)。因此该实现的上界为O(V²+EV),不应再额外乘一次V得到正文O(EV²)。
前后初始化/收集O(V),当前list_ins_next尾插不引入另一个线性搜索。若要优化,需要同时改善取最小候选和边端点到状态的定位;只换优先队列而保留每条边线性定位,不能直接宣称已达O(E logV)。
这里是按真实循环结构分析,不是运行基准;浮点比较/列表基本操作视为常数。
299/03087每轮扫描V个顶点选最小,全部O(V²);各邻接边共E次,每条线性扫描V个全局顶点定位,O(EV),合计O(V²+EV)。原文已经说明每边O(V),却错误写成EV²;仅换堆而不改善边端点定位仍保留EV项。
305指出优化Prim需支持定位元素和decrease-key;取堆顶O(1)不等于删除最小值O(1),并且每边端点状态定位也要高效。源码原有上界已按循环修正为O(V²+EV),书中EV²不能作为优化前精确分析。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 邻接查找成本要按总边数累计
- · 最短路径的实现与分析
- · 问与答
原书出处 · 3 处
- · 查看原书依据
O(EV2),其中V为图中顶点的个数,E为边的数目。这个复杂度来自主循环,在主循环中选择顶点,并比较权值和键值。对于每个选定的顶点V,首先遍历邻接表结构链表中的顶点元素,从而判断哪个顶点有最小的键值。这部分的整体运行时间为O(V2)。接下来,对于每个与选定顶点相邻的顶点,我们考虑其在邻接表结构链表中
- · 查看原书依据
O(EV2),其中V为图中顶点的个数,E为边的条数。这个运行时间来自主循环,在主循环中选择顶点和释放边。对于每个选定的顶点V,首先遍历邻接表结构链表中的顶点元素,从而判断哪个顶点有最小的最短路径估计。在主循环中这部分的整体运行时间为O(V2)。接下来,对于每个与选定顶点相邻的顶点,我们考虑其在邻接表
- · 查看原书依据
优先队列(见第10章),可以极大地提高算法的效率。回想一下,从优先队列中获取数值最小的元素的复杂度为O(1),维护优先队列的堆属性的代价为O(lg n),其中n为元素的个数。这就使得Prim算法的整体复杂为O(ElgV)。然而,此优先队列必须支持队列中元素的递减操作和高效定位元素值的操作(这样元素值