되풀이 관계 숙제 투쟁

다음은 질문입니다.
T (1) = theta (1) 인 경우 T (n)에 대한 theta bound를 구하여 재발생을 해결하십시오. 해결 방법을 시도되풀이 관계 숙제 투쟁

T(n) = n + T(n-3)

: 나는이 솔루션은 재발을 맞는 있는지 확인 두 번 때

T(n) = T(n-6) + (n-3) + n 

= T(n-9) + (n-6) + (n-3) + n 

= T(n-(n-1)) + [(n-n) + (n-(n-3)) + (n-(n-6)) + ... + n] 

= T(1) + [0 + 3 + 6 + ... + n] 

= theta(1) = 3[1 + 2 + 3 + ... + n/3] 

= theta(1) + [(n/3)(n/3 + 1)]/2 

= theta(1) + (n^2+3n)/6

, 그것은 작동하지 않습니다.

출처

2011-01-29 Anonymous

더 나은 장소가 있어야합니다. 다른 모든 '재발 관계'문제는 '주제에서 제외'됩니다. 개새끼, 어떤 생각? – new123456

@ new123456 : 정말요? 나는 단 하나의 [재발 - 관계] 질문 만 볼 수있다 - 그것은 그것들의 거의 전부는 아니다. 그게 내가 주제에 동의하지 않는 경향이 있다고 말했어 - 나에게 수학 같은 냄새가 난다 ... :) @sephy : 아마도 http://math.stackexchange.com/가 더 좋을까요? – Mac

제안을 주셔서 감사합니다. 수학 단원에서 질문 드리겠습니다. –

문제는 당신이 틀린 합계를 얻고 있다는 것이 었습니다. 마지막 T 함수가 T (n - (n-1)) 였으므로 이전에 T (n- (n-4)) 였으므로 0에서 시작하지 않습니다. 따라서 합계는 4에서 시작하여 n까지 올라갑니다.

이 요약을 찾는 방법을 모르는 경우 요약 수식의 몇 가지 교정본을 살펴 보시기 바랍니다. 이것이 바로 솔루션의 모습입니다.

T(n) = T(n-3) + n 

= T(n-6) + (n-3) + n 

= T(n-(n-1)) + [ (n-(n-4)) + (n-(n-7)) + ... + n] 

= T(1) + [4 + 7 + ... + n] 

= theta(1) + (4 + n) * (n - 1)/6

출처

2011-01-29 22:54:57

답변

관련 문제