3

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

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

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

4

2 回答 2

2

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

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

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 符号的一个很好的解释在这里:什么是“Big O”符号的简单英文解释?

于 2013-11-06T19:51:28.733 回答
1

您具体想了解什么?如果您想知道计算代码需要多长时间,并将其分解为特定循环和嵌套循环,那么我建议您查看秒表类:

http://msdn.microsoft.com/en-us/library/system.diagnostics.stopwatch(v=vs.110).aspx

您也可以通过将秒表的经过时间写入标签然后调用来观看实时使用的时间me.update()

于 2013-11-06T19:39:30.333 回答