algorithm - 考虑时间复杂度时，什么被认为是三次算法？

Question

所以我实现了这个算法，在分析了它的时间复杂度之后，我发现它的上限受 O(n^2*m) 的限制，其中 n 是图中的顶点数，m 是边数。我想知道这是否会被视为三次算法？我知道 O(n^3) 是三次方，但由于“m”，我不确定。任何人都可以解释它是立方还是其他类型的复杂性？

Answer 1

图算法提出了关于时间复杂度的特殊情况，从技术上讲，O(n^2*m) 是四次的(O(n^4))，因为 m = O(n^2)。然而，由于许多图算法对边数敏感，我们将复杂性分别报告为顶点和边的函数，以反映这种敏感性。如果图是稀疏的（m = O(n)），那么 O(n^2m) 是三次的，但对于更密集的图，它的行为更像是四次算法。