algorithm - 化简 log n/3i 之和

Question

我有以下等式：

W(n) = w(n/3) + lg(n)
W(1) = Theta(1)

我想找到它的时间复杂度。主定理无法解决（任何人都可以确认）所以我必须通过“手”来解决

如果我把它想象成一棵树，那将只有一棵，W(1)因为它只是将自己分成一个部分，而不是几个部分。

对于所有其他n != 1，我可以把它们写成总和：

sum_{i=0}^{log3(n)-1}ln\frac{n}{3i}

我现在对这个问题的回答是：

w(n) = sum_{i=0}^{log3(n)-1}ln\frac{n}{3i}

我现在的问题是我不知道如何简化这个总和！

谁能为我解释一下该怎么做？

Answer 1

替代n = 3^k。

W(3^0) = 1
W(3^k) = W(3^(k-1)) + lg(3^k) = W(3^(k-1)) + lg(3)*k,

替代T(k) = W(3^k)。

T(0) = 1
T(k) = T(k-1) + lg(3)*k.

通过归纳验证

T(k) = 1 + lg(3) * sum_{j=1}^k j = 1 + lg(3) * (k+1)*k/2.

撤消替换。

W(n) = 1 + lg(3) * (log3(n)+1)*log3(n)/2 = 1 + (lg(n)/lg(3)+1)*lg(n)/2.

Answer 2

它满足主定理。

让a=1, b=3, and f(n)=lg n, 使案例 2适用于c=0and k=1。因此，w(n)=Theta(lg^2 n)。

您可以分析您的最终金额：

w(n) = sum_{i=1}^{log3(n)-1}ln\frac{n}{3i}
= sum_{i=1}^{log3(n)-1}ln(n/3)-ln i
= (log3(n)-1)ln(n/3)-ln((log3(n)-1)!)
= Theta(ln^2(n))-Theta(ln((log3(n)-1)!)
= Theta(ln^2(n))-Theta((log3(n)-1)ln(log3(n)-1))
= Theta(ln^2(n))-Theta(ln n * ln(ln n))
= Theta(ln^2(n))