BIG-O :이 루프의 시간 복잡성은 왜 o (n)입니까?
-
29-09-2020 - |
문제
다음과 같은 기능이 있습니다.
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)
가되어야한다고 생각합니다.내 생각에 무엇이 잘못 될 수 있는지
해결책
내부 루프가 복용하는 단계 수를 확인하십시오. $ n + \ fRAC {1} {2} n + \ fRAC {1} {4} n + \ cos + ₩ cdots $ .그러나 기하학적 인 시리즈 우리에게 알려줍니다 :
$$ \ SUM_ {k= 0} ^ {\ lceil \ log n \ rceil + c} \ frac {n} {2 ^ k}
제휴하지 않습니다 cs.stackexchange