내가 루프 <pre><code>for(int i = 2; i <= n/2; i++){ for(int j = 2 * i; j <= n; j++){ } } </code></pre> <p>그들의 시간 복잡도는 무엇입니까</p> 두 가지를 가지고 루프

에 대한 이들의 시간 복잡도는 무엇입니까? 내 생각에 반복 횟수는 (n-4) + (n-6) + (n-8) + ... + 4 + 2 + 1이 될 것입니다. 엔)? 고마워요내가 루프 <pre><code>for(int i = 2; i <= n/2; i++){ for(int j = 2 * i; j <= n; j++){ } } </code></pre> <p>그들의 시간 복잡도는 무엇입니까</p> 두 가지를 가지고 루프

j ++를 j + = i로 변경하면 어떻게 될까요? 반복 횟수를 계산하는 방법은 무엇입니까?

출처

2016-10-23 codemonkey

아니, 그것은 O (n 개의 * n을)로 단순화를 N 마이너스 일정 단순화 ~ n) 내부 루프. 이 유형의 질문은 StackOverflow에 적합하지 않으며 http://cs.stackexchange.com/ – Slai

과 같은 다른 StackExchange 사이트에 더 적합합니다. n을 상수로 곱한 값이 n으로 단순화되기 때문에 Still O (n * n) ('j + = i'는 내부 루프에서 상수 임). n의 일부 값에 대한 루프 수를 계산하고 x-y 축으로 그릴 경우 시각화하는 것이 더 쉬울 수도 있습니다. https://en.wikipedia.org/wiki/Time_complexity – Slai

Thanks Slai. 나는 아직도 약간 혼란 스럽다. 내 생각은 반복은 n/2 + (n-3)/3 + (n-4)/4 + (n-5)/5 + ... + (n - (n-1))/(n - 1), O (n * n)이 될 것입니까? 나는 그것이 O (n)일지도 모른다라고 생각했다. – codemonkey