在考虑时间复杂度时，什么是三次算法？

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)是三次图，但对于密度较大的图，它的行为更像四次算法。