判断题
偏易
#19749
使用二叉堆优化的Dijkstra最短路算法,在某些特殊情况下时间复杂度不如朴素实现的O(V^2)。
使用二叉堆优化的Dijkstra最短路算法,在某些特殊情况下时间复杂度不如朴素实现的O(V^2)。
答案与解析
正确答案:对
解析
分析图的顶点数V与边数E的数量级关系;考察二叉堆优化Dijkstra中每次边松弛操作引起的堆操作次数与复杂度;计算二叉堆版本总时间复杂度O((V + E) log V);对比稠密图中E接近V^2时该表达式的增长趋势;比较朴素算法在所有情况下均保持O(V^2)的时间复杂度;考虑当E足够大时,(V + E) log V可能超过V^2;识别图结构中边密度对两种实现方式效率的影响机制。