t（n）= t（n -sqrt（n））

Question

誰かがこの再発を解決する方法を知っていますか？

マスター定理はここでは機能しません。

Answer 1

それ以来、O（1）では明らかなようです

T(n) = T(n - sqrt(n)) = T(m) with 0 < m < n

誘導により、Epsilonが0に近いT（N）= T（Epsilon）が得られます。

質問は、t（n）= t（n -sqrt（n）） + mであるかどうかをより多く感知します

Answer 2

マスターズ定理がここに適用されないことは正しいです。よく見ると、再帰のコストがゼロであることがわかります（右側に自由要素はありません。 T(n) = T(m) + f(n).

これは、再帰を実行するのに絶対にコストがかかることを意味します（1つの操作でさえありません）。だからあなたの限り n 反復よりも減少します（そして、それはそうです n > n - sqrt(n)）あなたの再帰は実際には無料です。

答えはそうです O(1). 。 PSは、少なくともo（1）を再帰のコストとして行うため、実生活でこれを持つことはできません。