0 
void mystery2 (int n)
{
 int i;
 for (i = 1; i <= n; i++) {
    double x = i;
    double delta = 1 / (double)i;
    while ( x > 0 )
      x -= delta;
  }
return 0;
}

如何使用像这里的跟踪表http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html#application而不是通过猜测来确定该程序的时间复杂度？

4

2 回答 2

3

对于每次迭代，最初你有x=i，然后每次x递减。1/i所以这将重复i/(1/i)==i^2多次。

因此，对于 的每次迭代for(i=1;i<n;++i)，内部的复杂度为O(i^2)。当i从 1 增长到 n 时，它就像加(1^2+2^2+3^2+...+n^2)，大致是n^3/6。就这样O(n^3)。

    Outer loop(for)          Inner Loop
    I=1                      1
    I=2                      4
    I=3                      9
    ...                      ..
    I=N                      N^2
 TOTAL_                      ~N^3/6
于 2013-02-28T15:50:26.793 回答
2

这相对简单：您需要确定两个嵌套循环中的每一个执行多少次，并同时考虑复杂性。

外层循环是一个平凡的for循环；它执行n时间。

内部循环需要更多注意：它不断减去1/i，i直到它变为零或变为负数。很容易看出，从中减去需要i循环的迭代。由于最初设置为，因此内部循环所花费的总时间为。while1xxii^2

因此，对于和 ，总数是x平方和。x1n

Wolfram Alpha 告诉我们，这个问题的答案是n*(n+1)*(2n+1)/6

这扩展到n^3/3 + n^2/2 +n/6多项式，其复杂度为O(n^3).

于 2013-02-28T15:56:02.203 回答