설명과 함께 다음 코드의 시간 복잡성?

이 알고리즘의 복잡도는 얼마이며 그 이유는 무엇입니까?설명과 함께 다음 코드의 시간 복잡성?

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

정답은 O (n)이지만 O (nlogn)를 얻습니다. 아무도 왜 O (n)인지 말해 줄 수 있습니까?

시도한 적이 있습니까? 어디서 갇혀 있고 왜 그런지 설명해주십시오. 이것은 숙제 서비스가 아닙니다. – 4castle

네, 그랬습니다. 문제는 외부 루프가 O (logn)를 실행하고 내부 루프가 외부 루프까지 실행된다는 것입니다. 그래서, 그것은 O (nlogn)이어야합니다. 하지만 O (n)으로 줄일 수있을 것 같습니다. 그래서 저는 수학적으로 어떻게 알고 싶습니까? –

예, O (nlogn) 여야합니다. 하지만 대답은 O (n)입니다. 그래서, 어때요? –

첫 번째 반복에서 내부 루프는 N 번을 실행 한 다음 N/2 번을 실행 한 다음 N/4 번 등을 실행합니다. 이것은 무한 합으로 표현 될 수 있습니다 : 각 용어의 N을 고려하면

N + N/2 + N/4 + N/8 + N/16 + N/32 + ...

, 당신은 얻을 :

괄호 안의 무한 순서 2 (더 많은 정보에 값에 수렴

N * (1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ...)

Wikipedia). 따라서, 동작 횟수가 단순화 될 수있다 : 큰-O의 관점에서

N * 2

, 점근 값 이내 :

가

O(N)

넌 관찰하여이를 확인할 수있는 출력 관계 N과 count 사이의 값은 선형입니다 : Ideone Demo

2017-03-23 22:01:05 4castle

답변