このダブルループの時間複雑度

Question

このコードの時間複雑度はどのくらいですか？

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

Answer 1

あなたはこのような何かにループを展開することができます。

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) 

これは、フォームの合計に展開：

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

あなたはHarmonic Seriesように、第2の要因を認識することがあります。次に、以下の結果を使用すると、SO答え：Finding Big O of the Harmonic Seriesあなたのネストされたループのビッグああを取得することができます：BのX BはXのLN（b）のような

O(b * log(b))