问题 问答题

阅读以下说明,根据要求回答下列问题。
[说明]
现需在某城市中选择一个社区建一个大型超市,使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图,其中顶点表示社区,边表示社区间的路线,边上的权重表示该路线的长度。
现设计一个算法来找到该大型超市的最佳位置:即在给定图中选择一个顶点,使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径,即需要计算任意两个顶点之间的最短路径;然后对每个顶点,计算其他各顶点到该顶点的最短路径之和;最后,选择最短路径之和最小的顶点作为建大型超市的最佳位置。

[问题2]
[问题1]中伪代码的时间复杂度为______(用O符号表示)。

答案

参考答案:O(n3)

解析:在[问题1]伪代码中第2行~第8行,用于计算任意两点之间的最短路径,共有三重for循环,故这部分伪代码的时间复杂度为O(n3)。
第9行~第12行的伪代码,用于计算每个点到任意其他点的最短路径之和,共有两重for循环,故这部分伪代码的时间复杂度为O(n2)。
第13行~第18行的伪代码,通过一个for循环在所有点的最短路径之和中找到最小的最短路径之和,故这部分伪代码的时间复杂度为O(n)。
综合以上分析情况,该算法总的时间复杂度为O(n3)。

材料题
单项选择题