多级图的时间复杂度为O（n ^ 2）或O（v^ 2），但有人说它是O（E）。那么，从o（v^2）到o（e）它们是不是得到了边数为e=v^2的稠密/完全图？
最佳答案
在求解最短路径的多级图算法中，我们将每一条边的代价精确地最小化一次。因此时间复杂度为O(E)。
然而，在最坏的情况下，我们得到一个完整的图，它具有边E = n*(n-1)/2，所以最坏的时间复杂度变为O(E) = O(n^2)。
注意，在这种情况下，每一条边都会被精确地处理一次。
关于algorithm - 基于自底向上动态规划的多级图时间复杂度分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50664168/