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

回答