当考虑时间复杂性时，什么被认为是三次算法

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