algorithm - Floyd Warshall 复杂性

Question

有人可以告诉我这个过程在 for 迭代中的时间复杂度吗？这段代码是FloydWarshall算法的“重构路径”部分。prev[n][n]是最短路径中源节点和目的节点之间的节点矩阵。printAllSP 在迭代中运行 n^2 次，我无法真正弄清楚的是它每次执行的递归调用次数，只知道这取决于 i 值 (max n)、j 值 (max n) 和插入 i 和 j 之间最短路径的 k (???) 节点数，根据我的评估，包括 for 循环，这部分在 On^4 中运行，但总算法复杂度为 On^3。请启发我!

 void PrintAllSP(int i, int j, int prev[n][n]){
if (i == j)
    print i
else  {
    PrintAllSP(i, prev[i][j], prev);
    print j
}
}

//PSEUDOPART OF MAIN
for i = 1 TO n
    for j = 1 TO n
        PrintAllSP(i, j, prev);
    }
}

Answer 1

总共有 n 个节点，这意味着打印了 O(n^2) 个最短路径。每条最短路径最多只能有 n 个节点。因此，只能打印O(n^3) 个节点。由于每个基本递归步骤都会导致打印一个节点，这意味着总共只有 O(n^3) 个基本递归步骤。