알고리즘 시간 복잡도 : i = 2 in 루프

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 (nlogn)가 될 답을 얻었지만 그 답은 분명히 O (n)입니다.알고리즘 시간 복잡도 : i = 2 in 루프

내 논리는 외부 루프가 지수 감소를 나타내며 log_base2_ (N) 회 발생합니다. 내부 루프는 기하학적 합계가 될 때 총 N 회 실행됩니다 (첫 번째 반복은 N/2 번, N/4, N/8 ...). 이 두 개를 합치고 중첩 루프의 결과로 곱하면 O (NlogN)이 생깁니다. 나는 명백한 무엇인가 놓치고 있냐?

출처

2017-09-13 user6142489

외부 루프는 총 log (n) 회 실행됩니다. 이제 당신이 처음은이 시리즈

n(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...)

이의 합이 될 것 (2 * N)하게하므로, 등등의 n 배, 다음/2 회 N를 실행하고 내부 루프를 관찰하면, 즉 O (n)

외부 루프가 O (logn) 회 실행되고 내부 루프가 O (n) 회 실행되므로 시간 복잡도는 O (n)입니다.

하지 않는 내부 루프 보낸 O (nlogn) N 단계마다 아니며, 실제로 촬영 한 모든 단계의 합계 (n)를

출처

2017-09-13 11:03:03 marvel308

이 O 유용하다. 나는 전체 작업 횟수와 실행 시간을 혼동하고 있다고 생각합니다. 내가 정확하게 요점을 이해한다면, 시간 복잡성은이 경우 O (n) 인 두 개의 루프보다 나빠질 것입니다. – user6142489

@ user6142489 일반적으로 두 개의 루프 중에서 최악은 아니지만 가장 안쪽 루프의 총 반복 횟수입니다. 따라서,이 답변에서 지적한 바와 같이, O (n)의 합계를 제공하는 각각의 합계를 수행해야합니다. 그러나 일반적인 절차는 각 루프의 복잡도 (따라서 _max_가 아닌)를 취하는 것이지만, 가장 안쪽 루프의 반복 횟수가 현재 루프의 반복 횟수에 따라 다르므로 너무 느슨한 경계가됩니다. _나는_. – qwertyman

흥미 롭습니다. 고맙습니다. – user6142489

알고리즘 시간 복잡도 : i = 2 in 루프

답변

관련 문제