Zeitkomplexität Analyse von iterativen Programme

Question

was wäre die Zeitkomplexität der folgenden sein des

int i,j,k; 

for(i=n/2 ;i<=n ;i++) 
{ 
    for(j=1;j<=n/2;j*3) 
    { 
     for(k=1;k<=n;k=k*2) 
     { 
      pf('vish'); 
     } 
    } 
} 

Answer 1

Sie können dies lösen, indem Sie eine Reihe von einfachen Regeln anwenden.

1. Wenn Sie Schleifen verschachtelt sind, und die Grenzen und Stufen der inneren Schleifen sind indpendent des Index der äußeren Schleifen, dann die Anzahl der Iterationen durch die innerste Körper ausgeführt ist die Multiplikation der Anzahl der Iterationen jede Schleife.

Hier zum Beispiel zu beachten, dass die inneren Schleifen (auf j und i), zum Beispiel, nicht auf i abhängen.

for(i=n/2 ;i<=n ;i++) 
{ 
    for(j=1;j<=n/2;j*3) 
    { 
     for(k=1;k<=n;k=k*2) 

2. wenn die Grenzen Θ (n) sind, und die Inkremente sind feste Zusätze, die Anzahl von Iterationen ist Θ (n). So zum Beispiel

   for (i = n/2; i < = n; i ++)

durchgeführt wird Θ (n) mal.

3. Wenn die Grenzen Θ (n) sind und die Stufen sind feste Multiplikationen, die Anzahl der Iterationen ist Θ (log (n)). So zum Beispiel

   for (j = 1, j < = n/2; j * 3)

ist Θ (log (n)).

4. eine konstante Funktion ist O (1).

   pf ('vish');

ist O (1).

---

die obigen Regeln kombinierend, haben wir eine O (1)Funktion durchgeführt wird Θ (n) Θ (log (n)) Θ (log (n)) mal. Die Komplexität ist Θ (n log (n)).

Answer 2

Schauen wir uns an, wie oft jede Schleife ausgeführt wird:

for(i=n/2 ;i<=n ;i++)  // executed O(n) times 
{ 
    for(j=1;j<=n/2;j*3)  // executed O(log_3(n)) times 
    { 
     for(k=1;k<=n;k=k*2) // executed O(log_2(n)) times 
     { 
      pf('vish'); 
     } 
    } 
} 

Unter der Annahme, pf ist O(1) (konstante Zeit) ist die Gesamtkomplexität O(n * log(n)^2).