这个for循环的大O分析

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

Answer 1

我会说它的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

Answer 2

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

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

^{全尺寸图片}

请注意，这是一个对数标度，并且所有函数都被缩放到大致相同的范围内。

猜猜是什么，avergae执行时间t(n)除以n^5不断减少，而t(n)/n^3不断增长。 当接近无穷大时，只有t(n)/n^4稳定，这certificate平均执行时间实际上是O(n^4) 。

Answer 3

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