이 의사 코드의 시간 복잡도는 얼마입니까?

Question

이것은 의사 코드입니다. 나는 this answer으로이 함수의 시간 복잡도를 계산하려고 시도했다.

n + n/3 + n/9 + ... 

아마 시간 복잡도는 것 같아요 O(nlog(n)) 같은 것이있다 : 것처럼해야 하는가? 또는 log(n)은 log(n)3이어야합니다.? 누군가는 시간 복잡도가 O (n)이라고 말하면서는 전혀 받아 들일 수 없습니다.

j = n 
while j >= 1 { 
    for i = 1 to j { 
     x += 1 
    } 
    j /= 3 
} 

Answer 1

알고리즘을 실행할에서 :

N + N/3 + N/9 + ... = series = O ~ (3/2 * 않음) = O (n)이

3/2가 상수 인이기 때문에. 여기에서 k 번째 루프는 n/3 ^k 단계로 실행됩니다.

---

외부 루프가 n 번 실행 링크 된 질문에서 중요한 차이를 발견하고는 고정하십시오.