Was ist die Laufzeit Komplexität dieser Funktion?

Question

void fn(int n){ 

    int p,q; 
    for(int i=0;i<n;i++){ 
     p=0; 
     for(int j=n;j>1;j=j/2) 
      ++p; 
     for(int k=1;k<p;k=k*2) 
      ++q; 

    } 

} 

1. Ich denke, seine Komplexität
2. Mein Freund sagt, dass seine nlog (logn)

und mir bitte auch sagen nlogn ist - Do inneren Schleifen in dieser Funktion voneinander abhängen?

Answer 1

Es ist eigentlich von undefinierter Komplexität, weil Sie q nicht initialisiert verwenden.

Den kleinen Fehler ignorierend, ist die äußere Schleife offensichtlich O(n). Die erste innere Schleife ist O(log n). Die zweite innere Schleife ist O(log p) und p ist log n so ist es O(log log n) aber es macht nichts, weil es sequentiell nach der ersten inneren Schleife ausgeführt wird und daher die Summe für beide inneren Schleifen ist O(log n) (Wenn Sie zwei Komplexitäten hinzufügen, ist die Gesamtkomplexität der am schnellsten wachsende). So ist Ihre Gesamtkomplexität O(n log n)