以下の関数の時間複雑度を計算するにはどうすればよいですか？

Question

以下の機能の時間の複雑さはどのくらいですか？

void function(int n){ 
     for(int i=0; i<n; i++){. //n times 
      for(int j=i ; j< i*i; j++){ // n*n times 
       if(j%i == 0){ 
        for(int k=0; k<j; k++){ // j times = n * n times. 
         ++counter; 
        } 
       } 
      } 
     } 
    } 

予約はO(n^5)です。しかし、なぜ本がj%iを考慮しなかったのか理解できませんでした。 kループはそれに基づいて決定します。明確にすることはできますか？

Answer 1

のuが疑問持っているコードの一部を見てみましょう：

for(int j=i ; j< i*i; j++) 
{ 
    if(j%i == 0) 
     { 
       for(int p=0; p<j; p++){ 
       ++counter; 
     } 
     } 

はちょうどこのコードの一部を分析してみましょう。 jが複雑でO(j)である、すなわち

i, 2i, 3i, .... i*i // upto i*i only,since j<i*i 

今、すべてのjのために、内部では、iの倍数である時はいつでも すべてのiについて、j%i==0はtrueになります。

コードのこの部分のためにそう複雑である：

だから

、全体的な複雑= = O(n^4)O(n*n^3)

Answer 2

実際に機能があるため、時間はO（n^4）で実行されif条件は約n回のループごとに1回だけ発生します。正確な分析については以下を参照してください。

void function (int n) { 
    for(int i=0; i<n; i++) { 
     // Runs a total of n times 
     for(int j=i; j< i*i; j++) { 
      // Runs a total of (n^3 - n)/3 = O(n^3) times 
      if(j%i == 0) { 
       // Runs a total of (n^2 - n)/2 = O(n^2) times 
       for(int k=0; k<j; k++) { 
        // Runs a total of (3n^4 - 10n^3 + 9n^2 - 2n)/24 = O(n^4) times 
        ++counter; 
       } 
      } 
     } 
    } 
}