Wie berechnet man die Zeitkomplexität für die untere Funktion?

Question

Was ist die zeitliche Komplexität für die folgende Funktion?

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; 
        } 
       } 
      } 
     } 
    } 

Buch sagt O(n^5). Aber ich konnte nicht verstehen, warum Buch j%i nicht berücksichtigt hat. Die k Schleife bestimmt auf dieser Grundlage. Könntest Du das erläutern?

Answer 1

Lasst uns den Teil des Codes betrachten, in dem u Zweifel haben:

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

Lassen Sie uns diesen Teil des Codes nur analysieren. Für jeden i wird j%i==0 wahr sein, wenn j ein Vielfaches von i ist, das heißt

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

nun für jeden j, Innen Komplexität O(j) ist.

So Komplexität für diesen Teil des Codes ist:

So Gesamtkomplexität = O(n*n^3) = O(n^4)

Answer 2

Tatsächlich ist die Funktion in der Zeit O läuft (n^4), da die if Bedingung passiert nur einmal alle ungefähr n Schleifen. Siehe unten für genaue Analyse.

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; 
       } 
      } 
     } 
    } 
}