대체 방법을 사용하여 다음 반복을 해결하는 방법은 무엇입니까?</p> <pre><code>T(n) = 2T(n/2) + n/log(n) </code></pre> <p>내가 대체 방법의 "추측"부분에 도착 재귀 트리와 반복을 사용하여 <code>T(n)</code>이 <code>O(n*log(log(n)))</code> 것을 알고있다 :

Question

나는 대체 방법을 사용하여 꽉 다음 재발에 바인딩을 증명해야 방법.

Assume T(n/2) <= c*(n/2)log(log(n/2)) 
T(n) = 2T(n/2) + n/log(n) <= 2c*(n/2)log(log(n/2)) + n/log(n) 

Assume T(n/2) => c*(n/2)log(log(n/2)) 
T(n) = 2T(n/2) + n/log(n) => 2c*(n/2)log(log(n/2)) + n/log(n) 

Answer 1

은 그래서 것을 보여주기 위해 충분 그런

T(n/2) <= (n/2) log log (n/2) = (n/2) log (log n - 1). 

T(n) = 2T(n/2) + n/log n 
    <= n log (log n - 1) + n/log n 
    = n log log n - n (log log n - log (log n - 1) + 1/log n), 

가정 :하지만 문제가 모두 큰-O와 오메가의 유도 단계에서 진행하는 방법을 알아내는이 log log n - log (log n - 1) >= 1/log n은 1/x을 x = k - 1에서까지 통합하여 증명 된 일반적인 불평등 log k - log (k - 1) >= 1/k의 인스턴스입니다.및 평균값 정리 적용. (시각, 폭과 높이 11/k의 직사각형 x = k에 x = k - 11/x에서의 곡선 아래 맞는다.)

하한은 유사하다; k >= 2에 대해 log k - log (k - 1) <= 1/(k - 1) <= 2/k이라는 부등식을 사용하십시오.