4 
 sum = 0;
 for (i = 1; i <= n; i++) {    //#1
   for (j = 1; j <= i * i; j++) {     //#2
      if (j % i == 0) {    //#3 
          for (k = 1; k <= j; k++) {   //#4
             sum++;
         }
     }
  }

}

以上让我感到困惑

Suppose #1 runs for N times
    #2 runs for N^2 times
    #3 runs for  N/c since for N inputs N/c could be true conditions
    #4 runs for  N times

因此，大致我可以看 O(N^5) 。我不确定。请帮助澄清。

编辑我想知道if(j%i==0). 由于它N^2从其父循环中获取输入，因此它可能正在(N^2)/c执行执行而不是N/c

4

3 回答 3

6

我会说它的 O(N^4) 和它一样。

 for (int i = 1; i <= n; i++)        //#1 O(n ...
   for (int j = i; j <= i * i; j+=i) //#2 ... * n ...
     for (int k = 1; k <= j; k++)    //#4 ... * n^2) as j ~= i^2
         sum++;

或者

public static void main(String... args) {
    int n = 9000;
    System.out.println((double) f(n * 10) / f(n));
}

private static long f(long n) {
    long sum = 0;
    for (long i = 1; i <= n; i++)   //#1
        for (long j = 1; j <= i; j++) //#2
            sum += i * j; // # 4
    return sum;
}

印刷

9996.667534360826

这非常接近 10^4

于 2012-04-09T10:50:45.683 回答
1

@PeterLawrey 做了数学计算，这里是图表上绘制的基准（我的数据集-n与以微秒为单位的执行时间）。

n基本上，我使用不同的输入（X 轴）多次运行有问题的代码。然后我将平均执行时间除以n^5,n^4和n^3函数并绘制：

在此处输入图像描述

全尺寸图片

请注意，这是一个对数刻度，所有函数都被缩放到或多或少在同一范围内。

你猜怎么着，平均执行时间t(n)除以n^5不断减少，同时t(n)/n^3不断增长。只有t(n)/n^4在接近无穷大时才稳定，这证明平均执行时间实际上是O(n^4)。

于 2012-04-09T11:32:44.003 回答
0

我认为使用 Sigma 表示法的答案如下：

在此处输入图像描述

于 2014-03-14T18:58:02.143 回答