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

Question

有誰知道如何解決這個問題？

主定理在這裏不起作用。

Answer 1

這似乎爲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

Answer 2

你是對的，碩士定理不適用於此。如果你仔細觀察，你會發現遞歸的代價爲零（右邊沒有空閒元素：T(n) = T(m) + f(n)。

這意味着它完全不需要運行遞歸（甚至不需要1次操作）。所以，只要你的n降低了迭代（它確實是因爲n > n - sqrt(n)）你的遞歸實際上是免費的。

因此，答案是O(1) PS。這是不可能有這個在現實生活中，因爲你會做最少O（1）作爲遞歸的代價