我有以下等式:
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}
我现在的问题是我不知道如何化简这个和!
谁能帮我解释一下怎么做？
最佳答案
代入 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.
关于algorithm - 化简 log n/3i 的总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26189734/