java - この for ループの Big O 分析

Question

 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) を見ることができます。私はわかりません。明確にするのを手伝ってください。

EDIT私はランタイムでif(j%i==0). 親ループから入力を受け取るため、代わりに実行をN^2行うことができます(N^2)/cN/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関数で割り、次のようにプロットしました。

^{フルサイズの画像}

これは対数スケールであり、すべての関数が多かれ少なかれ同じ範囲になるようにスケーリングされていることに注意してください。

平均実行時間を でt(n)割った値は、増加し続けn^5ながら、減少し続けていると思いt(n)/n^3ます。平均実行時間が実際t(n)/n^4に.O(n^4)

Answer 3

シグマ表記を使用すると、答えは次のようになると思います。