T (n)= T (n-sqrt (n))

Question

이 재발을 해결하는 방법을 아는 사람이 있습니까?

마스터 정리는 여기서 작동하지 않습니다.

Answer 1

O (1)에서 분명해 보입니다. 라코 디스

유도법으로 엡실론이 0에 가까운 T (n)= T (엡실론)을 얻습니다.

이 질문이 T (n)= T (n-sqrt (n)) + m이면 더 감각을 돋 웁니다

Answer 2

여기에 석사 정리가 적용되지 않는다는 것이 맞습니다.자세히 살펴보면 재귀 비용이 0이라는 것을 알 수 있습니다 (오른쪽에 무료 요소가 없습니다 : T(n) = T(m) + f(n). ).

즉, 재귀를 실행하는 데 비용이 전혀 들지 않습니다 (한 번의 작업도 아님).따라서 n가 반복을 통해 감소하는 한 (n > n - sqrt(n) 때문에 그렇습니다) 재귀는 실제로 무료입니다.

답은 O(1)입니다.추신재귀 비용으로 O (1) 이상을 수행 할 것이기 때문에 실제 생활에서는 이것을 가질 수 없습니다.