Zeitkomplexität von Verschachtelte For-Schleife mit Wenn

Question

void f(int n) 
{ 
    for(int i =1; i<=n; i++){ 
    if(i % (int)sqrt(n)==0){ 
     for(int k=0; k< pow(i,3); k++){ 
     //do something 
     } 
    } 
    } 
} 

Mein Denkprozess: Anzahl der Male ausführen if-Anweisung: Summe i = 1 bis n (theta (1)).

Anzahl von Malen auszuführen Dinge im Innern, wenn: Summe i = 1 bis sqrt (n) (für loop)

Anzahl von Malen zum Schleifen auszuführen: sum k = 0 bis i^3 (theta) (1) = i^3

Das gibt mir: Theta (n) + Summe i = 0 bis sqrt (n) (Theta (i^3)) = theta (n) + theta (n^2)

die mich Theta (n^2)

Die gab er Antwort Schlüssel gibt, ist Theta (n^3,5)

Ich frage mich nur, ob ich einen Fehler in meinem Denkprozess gemacht habe. Ich habe meinen Professor zweimal nach dieser Frage gefragt. Ich will nur sehen, ob es etwas gibt, das ich nicht gesehen habe, bevor ich ihn wieder belästige. Danke!

Answer 1

Mit der Sigma-Notation kam ich auf die exakte geschlossene Form.

Außerdem geht die folgende Formel davon aus, dass der Prozess, der die Bedingung, die die innerste Schleife ausführt, nicht verifiziert, vernachlässigbar ist.

Es liegt an Ihnen fest, um Wachstumsgrenzen zu bestimmen, da der Bodenbelag Funktion und Quadratwurzel usw.

Weitere Informationen hier: https://math.stackexchange.com/questions/1840414/summation-with-floor-and-square-root-functions-tight-bounds

Answer 2

void f(int n) { 
    for(int i =1; i<=n; i++){  //--- n times 
    if(i % (int)sqrt(n)==0){ // --- 2 times (constant) 
     for(int k=0; k< pow(i,3); k++){ // sqrt(n)^3 and n^3 times 
     //do something 
     } 
    } 
    } 
} 

die höchstwertigen Begriff Einnahme sollte es Theta sein (n^3)

etwas tun Unter der Annahme konstant

c = do Somrthing + plus die laufenden Kosten der einzelnen Iteration der inneren loop

a = runnning Kosten der einzelnen Iteration der äußeren Schleife laufen die meisten

b = laufend Kosten Wenn Block mehr darüber nachzudenken c n^3/2 + c n^3 + a * n + b * 2)

Unter der höchsten Ordnung Begriff Theta (n^3) oder da c ist derselbe Koeffizient für sowohl die n^3 und n^3/2 können wir reduzieren es

= cn^3 + cn^3/2

= cn^3 (n^1/2 + 1)

~ cn^3 * n^1/2

= cn^3.5