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

Question

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

Answer 1

正确答案：(7)O(n³)
(7)O(n³) 解析：问题1：本问题考查算法流程。第(1)空表示主循环，k是循环控制变量，故第(1)空填k=1to n。第(2)和(3)空根据题意和递归式，可分别得到答案为
[*]
和计算了任意两个顶点之问的最短路径之后，对每个顶点，开始统计其到所有其他顶点的最短路径之和，因此第(4)空填SP[i]=SP[i]+dy⁽ⁿ⁾。第13和第14行初始化，假设最小的到所有其他顶点的最短路径之和为第一个顶点的最小路径之和，大型超市的最佳位置为第一个顶点，故第(5)空填rain_v=l。最后要求返回大型超市的最佳位置，即到所有其他顶点的最短路径之和最小的顶点。
问题2：本问题考查[问题1]中的伪代码2—8行，计算任意两点之间的最短路径，有三重循环，故时间复杂度0(n³)。第9～12行，计算任意两点之间的最短路径之和，有两重循环，故时间复杂度为0(n²)。第15—18行，在所有点的最短路径之和中找到最小的最短路径之和，时间复杂度为O(n)。故算法总的时间复杂度为O(n³)。