T(n) = T(n/2) + T(n/4) 使用迭代法求解这个递归
T(n) = T(n/2) + T(n/4) solve this recurrence using iterative method
如何求解递归方程
T(n) = T(n/2) + T(n/4)
对于基本情况 T(n)=1
我已经检查了 this and this 的线索，但它并没有帮助我使用迭代方法解决它
我只需要得到这个的一般方程式。
我不知道如何使用 "iterative method" 来解决这个问题。
但是你的递归关系和斐波那契数的递推关系有相似之处，可以用来求解。
T(2^k) = T(2^(k-1)) + T(2^(k-2))。所以假设 T(1) = T(2) = 1，T(2^k) = Fib(k)。所以对于 n 的 2 次方，T(n) = Fib(lg(n))。由于 Fib(n) = Theta(phi^n)，T(n) = Theta(phi^(lg n)) = Theta(n ^ lg(phi)) ~= n^0.7
这里Fib(n)是第n个斐波那契数，phi = (1 + sqrt(5))/2.
如何求解递归方程
T(n) = T(n/2) + T(n/4)
对于基本情况 T(n)=1
我已经检查了 this and this 的线索，但它并没有帮助我使用迭代方法解决它
我只需要得到这个的一般方程式。
我不知道如何使用 "iterative method" 来解决这个问题。
但是你的递归关系和斐波那契数的递推关系有相似之处，可以用来求解。
T(2^k) = T(2^(k-1)) + T(2^(k-2))。所以假设 T(1) = T(2) = 1，T(2^k) = Fib(k)。所以对于 n 的 2 次方，T(n) = Fib(lg(n))。由于 Fib(n) = Theta(phi^n)，T(n) = Theta(phi^(lg n)) = Theta(n ^ lg(phi)) ~= n^0.7
这里Fib(n)是第n个斐波那契数，phi = (1 + sqrt(5))/2.