使用迭代或替换求解递归方程 T(n) = T(n/3) + O(1)

Question

我意识到用 Master 定理解决这个问题给出了 Big Theta(log n) 的答案。但是，我想了解更多并找到对数的底数。我尝试阅读更多有关 masters theorem 的内容以了解基础，但无法在维基百科 (https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)) 上找到更多信息。

我如何使用递归树或替代方法来解决这个问题？ 您可以假设 n = 2^K 和 T(0) = 0.

Answer 1

不设置 n=2^k 但 n=3^k

因此T(3^k) = T(3^{k-1}) + c

重复变成w_k = w_{k-1} + c

假设T(1) = 1 通用术语：w_k = ck+1 和 w_0 = 1

你得出结论T(n) = clog_3(n) + 1

因此 T(n) = O(log_3(n))

Answer 2

T(n) = T(n/3) + O(1) = T(n/9) + O(1) + O(1) = T(n/27) + O(1) + O(1) + O(1) = …

在 log3(n) 步之后，术语 T 消失并且 T(n) = O(log(n))。