BIG-O :이 루프의 시간 복잡성은 왜 o (n)입니까?

Question

다음과 같은 기능이 있습니다.

int fun(int n) 
{ 
  int count = 0; 
  for (int i = n; i > 0; i /= 2) 
     for (int j = 0; j < i; j++) 
        count += 1; 
  return count; 
} 

.

O(N) 시간 복잡성이 있습니다.나는 그것이 O(N LogN)라고 생각했다 (즉, 우리가 얻는 내부 루프를 제거하면)

for (int i = n; i > 0; i /= 2){
...
}

.

O(Log N)는 그렇지 않습니다?그리고 내부 루프는 선형으로 증가하면서 O(N)로 밝혀졌습니다.그래서 나는 그것이 O(Log N * N)가되어야한다고 생각합니다.내 생각에 무엇이 잘못 될 수 있는지

Answer 1

내부 루프가 복용하는 단계 수를 확인하십시오. $ n + \ fRAC {1} {2} n + \ fRAC {1} {4} n + \ cos + ₩ cdots $ .그러나 기하학적 인 시리즈 우리에게 알려줍니다 :

$$ \ SUM_ {k= 0} ^ {\ lceil \ log n \ rceil + c} \ frac {n} {2 ^ k}