我意识到用Master定理解决这个问题可以得出Big Theta（log n）的答案。但是，我想了解更多并找到对数的底数。我尝试阅读有关大师定理的更多信息，以了解基础知识，但是找不到有关维基百科（https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)）的更多信息。
我该如何使用递归树或替换方法解决此问题？ 您可以假设n = 2 ^ K且T（0）= 0。
chen870909 回答：使用迭代或替换求解递归方程T（n）= T（n / 3）+ O（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))
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))也消失了。