誰かがこの再発を解決する方法を知っていますか？
マスター定理はここでは機能しません。
1728 次
2 に答える
4
以来、O（1）で明らかなようです
T(n) = T(n - sqrt(n)) = T(m) with 0 < m < n
誘導により、イプシロンが0に近いT（n）= T（イプシロン）が得られます。
T（n）= T（n-sqrt（n））+ mの場合、質問はより感覚的になります
于 2011-03-22T16:14:07.747 に答える
0
マスターの定理がここでは適用されないのは正しいです。よく見ると、再帰のコストがゼロであることがわかります（右側に空き要素はありません：T(n) = T(m) + f(n)。
これは、再帰を実行するのにまったく費用がかからないことを意味します（1回の操作でも）。nしたがって、反復で減少する限り（そして、それが原因でn > n - sqrt(n)）、再帰は実際には無料です。
したがって、答えはO(1)です。PS再帰のコストとして少なくともO（1）を実行するため、これを実際に使用することはできません。
于 2015-12-13T10:16:26.913 に答える