T（n）= T（n - sqrt（n））

主定理在这里不起作用。

2011-03-22 Markus

不，我正在为明天的考试学习 - 至少有一些提示？ – Markus 2011-03-22 15:58:05

是否有基础案例？这一切是否重现？没有常量？ – 2011-03-22 16:24:48

这似乎为O明显（1）自

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

通过感应，你会得到T（N）= T（ε）与小量接近，如果为0

的问题做出更SENS它是T（n）= T（n - sqrt（n））+ m

2011-03-22 16:14:07

你是对的，硕士定理不适用于此。如果你仔细观察，你会发现递归的代价为零（右边没有空闲元素：T(n) = T(m) + f(n)。

这意味着它完全不需要运行递归（甚至不需要1次操作）。所以，只要你的n降低了迭代（它确实是因为n > n - sqrt(n)）你的递归实际上是免费的。

因此，答案是O(1) PS。这是不可能有这个在现实生活中，因为你会做最少O（1）作为递归的代价

2015-12-13 10:16:26

回答