我正在尝试找到上限和下限，可能是O（2 ^ n）
我知道一般器官是：
T（n）= T（n / 2 ^（i + 1））+从i = 0到2 ^（n / 2 ^ i）的k的和
从这里我不知道如何进行..
您的符号有问题。一般器官应为：
T(n) = T(n/2^(i+1)) + sum from k=0 to i of 2^(n/2^k)
在此步骤之后，我们让i = log(2, n) - 1，使T(n/2^(i+1)) = T(1)。
因此，T(n) = T(1) + sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k)。
注意sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k)是2^n + 2^(n/2) + 2^(n/4) + ...，这是小于2^n + 2^(n-1) + 2^(n-2) + ...。但是，后者是2^(n+1) - 1。因此，前者是介于2^n和之间的东西2^(n+1)。因此，总和为O(2^n)。
然后T(n) = O(2^n)。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句