문제가 있습니다. 해결을 위해 노력하고 있으며 도움을 많이 주셔서 감사합니다! 어떤 시간 복잡도는 ...점근 분석에 로그 추가
외부 for 루프는 n 번 실행됩니다. 내부 루프에서 k+= log n을 처리하는 방법을 잘 모르겠습니다. 내 생각은 그것이 O (n^2)입니다. log (n)을 k에 추가하는 것은 추가 n 개의 루프를 얻는 것은 아니지만 O (n * log n)보다 작을 것이라고 생각합니다. 분명히, 그것은 단지 추측이며, 수학적으로 그것을 보여주는 법을 이해하는데 도움이된다면 크게 도움이 될 것입니다!
여기서 log(n)을 상수로 사용할 수 있습니다.
루프를 반복 할 때마다 일정한 작업량 (sum+=...; k+=...)이 n/log(n)과 같은 횟수만큼 수행됩니다. 반복의 n 반복이 있습니다. 총 작업은 따라서 n^2/log(n)입니다.
당신과 같이 작업의 무리를 볼 때마다 :
---------------------b-------------------------
|O(blah) + O(blah) + O(blah) + O(blah) + O(blah)
|O(blah) + O(blah) + O(blah) + O(blah) .
a|O(blah) + O(blah) + O(blah) .
|O(blah) + O(blah) .
|O(blah) . . . .
그것은 a*b * O(blah)입니다 - 단지 광장 상상 (필자는 .들 넣어). 이것은 2D 직사각형의 일정한 부분 (사각형의 절반)이므로 O(a*b)입니다. 위의 경우
n, A =
n/log(n) 및 O 넌 아주 쉽게 "그냥 섬프"수
감사합니다. 하나의 후속 조치. 그래서 n/log (n) - 당신은 단지 그것을 보았을 때 도착했습니다. 그렇습니까? n/log (n)을 식별 할 수있는 다른 트릭이나 제안이 있습니까? 내 문제는 항상 코드를 수학 방정식으로 변환하는 방법을 알아내는 것이고, 나는 종종 그 사실에 관해 온라인이 얼마나 도움이되는지에 대해 놀란다. – chrismanderson
루프와 관련하여 상수였습니다 (즉, 그렇게 생각하고 싶다면 합계에서 빼낼 수 있습니다). 'log (n)'이 아니라'log (j)'와 같은 것이면 (이상한 이유로), 더 어려울 것입니다. 나는 일의 양을 용어로 적어서 패턴을 보려고 노력할 것입니다. 당신은 또한 그것을 묶기 위해 그것을 시뮬레이션 할 수 있습니다 ("오, n과 n^2 사이 어딘가에 ..."). 재귀 적으로 다시 작성하고 http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method를 사용할 수 있습니다. – ninjagecko
(내부 루프)에서 (ㅋ) = O(1) :
외부 루프는 n 걸음을했다. 내부 루프는 (k-j)/log n 단계를가집니다. (대략)의
:
n
---
\ (n-j) n*n
/ -------- = ... = ---------
___ (log n) 2*log(n)
j=1
을 그래서, 그것은 총 O((n^2)/log(n))입니다.
당신은 다음과 같이 공식적으로 진행할 수 :
내부 루프는 몇 번을 실행 하는가? 'ceil ((n-j)/log (n))'이다. 거기서 일해라. –