die asymptotische Komplexität im schlimmsten Fall Bestimmung (O (N)) von einer bestimmten Funktion

Question

Ich mag die asymptotische Komplexität im schlimmsten Fall die folgende Funktion bestimmen:

int j; 
float r = 1.0; 
for (int i=1; i<(log n); i++){ 
    j = 1; 
    while (j <= i^2){ 
     r*=2; 
     j++; 
} 
print(r); 

Answer 1

Zunächst werde ich davon ausgehen, Das i^2 in Ihrem Code bedeutet "i auf die Potenz von 2 erhöht", anstatt "i Bitwise-XOR 2", wie letztere mit C++ - Syntax konsistent ist, aber unvorhersehbare Ergebnisse erzeugt.

Zeitkomplexität wird durch die Summe gegeben

Wir müssen die Summen der natürlichen Zahlen in die Potenz von 2 zu bewerten, die auf dieser Webseite mit Informationen: http://www.trans4mind.com/personal_development/mathematics/series/sumGeneralPowersNaturalNumbers.htm.

So ist die Zeitkomplexität ist