재발 관계 : T (N-1)

Question

은 내가 시작 큰 O.

T(n) = T(n-1) 

에 대한 몇 가지 점화식 문제를 해결하고있어의 비고 해결 : 이제 N과 K를 설정

T(n) = T(n-1) 
T(n-1) = T(n-2) 
.. 
T(n) = T(n-k) 

-1

T(n) = T(1) 

그래서 결과는

입니다

이것이 맞는지 확실하지 않지만 매우 쉽지 않습니다.

Answer 1

기본 케이스가있는 한 그 말이 맞습니다. I의 반복을 가정하고있어

는 = T (N)

T (0) = (일부 정수 (k)의 경우) K 및

T (N + 1)으로 정의된다

그러면 모든 자연수 n에 대해 T (n) = k임을 유도 할 수 있습니다.

• 기본 케이스 : 만약 N = 0이면 T (N) = T (0) = K, 필요에 따라.
• 유도 단계 : T (n) = k라고 가정한다. 그런 다음 필요에 따라 T (n + 1) = T (n) = k.

따라서, T (n) = k = 0 (1).

희망이 도움이됩니다.