루프의 Big-O 복잡도

Question

루프가 처음 실행될 때 n 번째 단계를 실행 한 후 두 번째로 n - 2를 실행하고 다음에 n - 4를 실행 한 루프가있는 알고리즘이있는 경우 마지막 시간까지 반복해서 반복합니다 2 단계를 실행 한 루프,이 루프의 복잡도 측정은 무엇입니까?

실행되지 않는 단계가 2 차적으로 증가하므로 O (n^2) 복잡성을 나타낼 것으로 생각합니다. 나는 루프 자체를 시각화하는 데 어려움을 겪고 있는데, 이는 내 대답에 대해 자신감이 덜 떨어진다.

도움의 모든 종류의

은/다른 의견이 크게 감사합니다 :)

Answer 1

당신은 복잡 Θ (N ²) 것을 정확합니다. 당신이 설명하는 것은 때문 인 arithmetic progression :

(N - 2) + (N - 4) + ... + 2 (또는 끝에 홀수)입니다

(, 분명히, 2 + 4 + 6 + ... + (n - 2) 또는 홀수 시작과 동등한, BTW).

formula for the sum을 사용하면 첫 번째 요소와 마지막 요소의 평균에 요소 수를 곱한 값입니다. 이들 각각의 용어는 Θ (n)이고 제품은 Θ (n)입니다.