GESP 八级 · GESP 202503 C++ 八级 第 13 题

下面 Floyd 算法程序的时间复杂度为（ ）。

#include <iostream>
using namespace std;

#define N 21
#define INF 9999999
int map[N][N];
int main() {
    int n, m, t1, t2, t3;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                map[i][j] = 0;
            else
                map[i][j] = INF;
        }
    }

    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        map[t1][t2] = t3;
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (map[i][j] > map[i][k] + map[k][j])
                    ________; // 在此处填入选项

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout.width(4);
            cout << map[i][j];
        }
        cout << endl;
    }
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】Floyd算法三重循环结构｜时间复杂度分析｜嵌套循环计数

1. 🎯 考纲定位

本题考查《GESP 202503 C++ 八级》大纲中"图论算法"模块的核心考点——Floyd算法的时间复杂度。命题人卡在绝大多数考生对"三重循环即O(N³)"的机械记忆上，真正意图是检验你是否理解算法结构而非死记结论。