performance - 这段代码的时间复杂度

Question

我正在做一些家庭作业，所以我不能发布任何代码。我正在编写一些代码，此时我有这样的东西(而不是我编写时间复杂度的函数):

while(O(n^2)) {
    O(n^4);
    O(n^2);
}

我根据函数中的嵌套 for 循环估计了 O。我的问题是这整个事情的实际时间复杂度是多少？我也不介意简短的解释。谢谢!

Answer 1

编辑:我之前的回答是错误的，因为我犯了一个错误。

现在我明白了，您的代码可以重构为

while(run == true)
{
    run = O(n^2);
    O(n^4);
    O(n^2);
}

所以每次迭代都有 O(n^4) 复杂度，因为我们有一个多项式 n^4 + 2*(n^2) 并且我们放弃了较低的次数。现在你必须将它乘以迭代次数。例如，如果你得到 n 次迭代，你最终得到 O(n^5)。如果你总是有 1000000000 次迭代，你仍然有 O(n^4)。

Big-O 符号的一个很好的解释在这里:What is a plain English explanation of "Big O" notation?