이 이중 루프의 시간 복잡도

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로 두 번째 요소를 인식 할 수 있습니다. 그런 다음에서 결과를 사용하여 다음 SO 답 : Finding Big O of the Harmonic Series 당신이 당신의 중첩 루프의 큰 아를 얻을 수 있습니다 : B의 ​​X B의 X 에선 같은

O(b * log(b))