0
그러한 반복 관계에 대한 꽉 묶인 것을 어떻게 알 수 있습니까? 이것은 hw 질문이고 우리는 m/log (m)이 tight asymptotic bound임을 증명할 것으로 예상됩니다. 유도를 사용하여 시도했지만 아무데도 갈 것 같습니다. 그것은 로그 규칙으로 무언가를 놓치고 있거나 뭔가 더 있습니다.반복 T (n) = T (n - log (n)) + 1
A
답변
1
유도. 모두 k < n에 대해 C의 경우 T(k) <= C k/log k이라고 가정합니다. log(n/2)log(.)와 교체
펴고 재발을 (n/2)/log(n/2)
T(n) 및
log(n) 모두 단조 함수라는 사실을 이용). 즉,
T(n) <= C (n/2)/log(n/2) + (n/2)/log(n/2)
이제 오른쪽에있는 표현식이 C n/log n에 의해 제한되어 있음을 증명해야
T(n) <= T(n/2) + (n/2)/log(n/2)
T(n) <= T(n - log(n/2) * (n/2)/log(n/2)) + (n/2)/log(n/2)
C 연습으로 남아 있습니다.
관련 문제
- 1. : T (N) = T (N - 1) + N
- 2. 반복 관계 : T (n/16) + n log n
- 3. 역 반복 방법으로 T (n) = T (n-1) + 2n을 풀다.
- 4. 찾기 theta : T (n) = T (n^(1/2)) + 1
- 5. t (n) = t (n-2) + (n-2) ²
- 6. T (n) = T (n - sqrt (n))
- 7. T (n-1) + 1/lg (n) recurrence
- 8. T (n) = T (n-1) + n + 2의 반복 방정식은 어떻게 찾을 수 있습니까?
- 9. 해결 재발 T (N) = T (N/2) + Θ (1)
- 10. T (n) = 2T (n/2) + O (n)
- 11. 반복에 대한 명시 적 수식 : T (n) = 2 * T (n - 1) + 4^n + 1
- 12. 반복을 해결하는 방법 T (n) = T (n-1) + ... T (1) +1?
- 13. 재발 관계 : T (N-1)
- 14. 되풀이 관계 : T (n) = 2T (n/4) + T (n/2) + n^2
- 15. A (n) = A (n-1) + n * log (n)?
- 16. "\ n \ t \ t \ t \ tDay of Week \ n \ t \ t \ t"와 같이 \ n, \ t 단어를 제거하는 방법?
- 17. 재귀 적 복잡도를 풀는 방법 T (n) = T (n/4) + t (3n/4) +1?
- 18. 방법이 점화식을 해결 : T (N) = T를 (N-1) * T (N-2)
- 19. 재발 T (N) = T (N-1) + T를 해결하는 방법 (N-3) -T (N-4), N> = 재발 방정식</p> <p>1 해결 방법
- 20. 만약 T (n) = θ (n^2)가 T (n) = 0 (n)이라면?
- 21. 제곱근에 대한 다음과 같은 반복 관계에 대한 해답은 무엇입니까? T (n) = T ([√n]) + logn?
- 22. T (n-1) + sqrt (n)에 대한 재발생율
- 23. Regressive n log (n) 정렬
- 24. log (n!) = O ((log (n))^2)입니까?
- 25. 실행 시간 : T (n) = 2T (n-1) + 3T (n-2) + 1
- 26. std :: type T ** 대 T * [N]
- 27. N + 1 + N + 1 + ... + N + 1 + N + 1에서 N (N + 1)을 어떻게 얻습니까?
- 28. 1/N + 2/N-1 + 3/N-2 + ... N/1
- 29. (log (n))^log (n) 및 n/log (n)은 더 빠릅니까?
- 30. 목록에서 '\\ n \\ t \\ t \\ t'요소를 제거하십시오.
유도를 시작하는 방법을 알려주세요. 어쩌면 누군가가 당신을 도울 수 있습니다. – ShadowMitia