재발의 시간 복잡성?

Question

재발의 시간 복잡도 (Big Oh Bound)를 확인하십시오 T(n) = T(⌊n⌋) + T(⌈n⌉) + 1.

이 시간 복잡도는 어떻게 발생합니까? O(n) ??

Answer 1

T(n)=T(⌊n/2⌋)+ T(⌈n/2⌉) + 1입니다.

T(n)의 처음 몇 값을 계산합니다.

T(1) = 1 
T(2) = 3 
T(3) = 5 
T(4) = 7 

우리는 T(n) = 2 * n - 1을 추측 할 수 있습니다.

가 mathematical induction

기초

T(1) = 1 
T(2) = 3 
T(3) = 5 
T(4) = 7 

기초하여 유도 단계 모두 입증 되었기 때문에 유도 단계

T(2*n) = T(⌊2*n/2⌋)+ T(⌈2*n/2⌉) + 1 
    = T(⌊n⌋)+ T(⌈n⌉) + 1 
    = (2*n - 1) + (2*n - 1) + 1 
    = 4*n - 1 
    = 2 * (2*n) - 1 

T(2*n+1) = T(⌊(2*n+1)/2⌋)+ T(⌈(2*n+1)/2⌉) + 1 
    = T(n)+ T(n+1) + 1 
    = (2*n - 1) + (2*(n+1) - 1) + 1 = 
    = 4*n + 1 = 
    = (2*n+1)*2 - 1 

하여 증명할하자, 그것은 이제 수학적 귀납법에 의해 증명 된 그 T (n)은 모든 자연적인 2 * n - 1에 대해 유지된다.

T(n) = 2*n - 1 = O(n)

Answer 2

현재 귀하가 이해하지 못하는 것은 무엇입니까? n은 보통 자연 숫자로 간주되기 때문에 n=⌊n⌋=⌈n⌉입니다. 그런 다음 재발은 다음과 같습니다 : 크기 n의 문제를 크기가 n 인 두 가지 문제로 분해하여 1 시간을 보냅니다. 방금 만든 두 가지 새로운 문제가 차례로 나뉘어지며, 모두 당신이하는 일은 스스로 더 많은 일을 만들어내는 것입니다.