Zeit Komplexität dieser Doppelschleife

Question

Was wird die zeitliche Komplexität dieses Codes sein?

for(int i = 1 ; i <= b ; ++i) 
    for(int j = i ; j <= b ; j += i) 

Answer 1

Sie können die Schleifen in etwa so erweitern:

i = 1 ——> 1,2,3,…,b  b 
i = 2 ——> 1,3,5,…,b  (b/2) 
i = 3 ——> 1,4,7,…,b  (b/3) 
i = 4 ——> 1,5,9,…,b  (b/4) 
    … 
i = b ——> 1, b   (b/b = 1) 

Dies erweitert in eine Summe der Form:

b + b/2 + b/3 + … + b/b = b * (1 + 1/2 + 1/3 + … + 1/b) 

Sie könnten den zweiten Faktor als Harmonic Series erkennen. Dann wird unter Verwendung des Ergebnisses aus dem folgenden SO beantworten: Finding Big O of the Harmonic Series können Sie die Big Oh Ihre verschachtelten Schleifen erhalten:

O(b * log(b))