数据结构和算法方面的问题。关于时间复杂度的求法。关于代入法和主定理，谢谢！ 问题可能有点多，

Question

数据结构和算法方面的问题。关于时间复杂度的求法。关于代入法和主定理，谢谢！

问题可能有点多，图片有点长。但是可以不用全部回答，下面几个问题回答1个也可以，有收获留给分。谢谢啦。
（图中有2和3两题，纸条下面的是第二题的部分答案。）
问题如下:
1.第三题用主定理法如何求解。有一步是以5为底6的对数log5（6），如何是主定理的第一种情况如何减去一个常数才能和f（n）“相等”。
2.第二题的代入法如图（纸条下）所示，为什么不是nlgn级别的，把那个n乘进去不是nlgn吗，如何出来lgn的平方？
3.主定理法给了3种情况，确实比较快，但是有点复杂。请问老师们有什么比较快捷的方法迅速判断一个式子应该用哪种情况的法则，而不用试呢？
4.还有什么好方法解决图中题目。

谢谢

Answer 1

在我看来主定理并没什么大的用处, 不仅条件需要仔细验证, 而且三种情况之间还有真空地带, 还不如掌握些常用的解递推的方法更实用.

当然, 从你的叙述来看, 你连主定理都没有理解, 所以你的首要任务是先学会用主定理.

粗略地讲, 主定理的基本思想是对
T(n)=aT(n/b)+f(n)
型的递推, 到底是 aT(n/b) 这项大还是 f(n) 这项大, 所以引出分水岭 g(n)=n^{ln b/ln a}.

对于第三题, 取 ε=ln6/ln5-1>0, 那么 f(n)=n^1=n^{ln6/ln5-ε}, 比 g(n) 低 n^ε, 然后代主定理就得到 T(n)=Θ(n^{ln6/ln5})

对于第二题, f(n)=nln n, g(n)=n, 两者间没有多项式的鸿沟, 就不能直接用主定理. 这也就是我说主定理其实没啥大用的道理.

一般来讲掌握下面的方法就可以解决这一大类递推, 其实主定理也是这样推出来的.

对于第二题, 只考虑 n=2^k 的子列, 换元之后把 T(2^k) 记成 S(k), 那么
S(k) = 2S(k-1) + 2^k * k
S(k-1) = 2S(k-1) + 2^{k-1} * (k-1)
...
S(1) = 2S(0) + 2
把左端为 S(k-j) 的式子乘上 2^j 之后全加起来就消去了所有中间项得到
S(k) = 2^k S(0) + 2^k[k+(k-1)+...+1] = 2^k*O(1) + 2^k*Θ(k^2) = Θ(2^k*k^2)
写成 T(n) 的形式就是 T(n)=Θ(n*(ln n)^2)
由于 T(n) 是单调的, 考虑上述子列足够推出渐进量级了

对于第三题, 同样的方法, 令 n=5^k, S(k) = T(5^k), 那么
S(k) = 6S(k-1) + 5^k
S(k-1) = 6S(k-2) + 5^{k-1}
...
S(1) = 6S(0) + 5
把左端为 S(k-j) 的式子乘上 6^j 之后全加起来就消去了所有中间项得到
S(k) = 6^k S(0) + [5^k + 6*5^{k-1} + ... + 6^{k-1}*5]
= 6^k*Θ(1) + 5*Θ(6^k) = Θ(6^k)
注意后面那堆求和是等比数列求和
换回去就得到 T(n) = Θ(n^{ln6/ln5})

一般方法大致就是这样, 当然你得会选择合适的变量代换, 也得掌握一些基本的求和, 有时候求和不易求可以用积分来代替, 不影响渐进量级

追问

谢谢，解释的很详细。有一个地方还需赐教，这里: S(k) = 2^k S(0) + 2^k[k+(k-1)+...+1] = 2^k*O(1) + 2^k*Θ(k^2) = Θ(2^k*k^2)。第二个和第三个等号是如何化简的，或者说依据什么。谢谢

追答

第二个等号

S(0)=T(1)=O(1)

k+(k-1)+...+1=k(k+1)/2=Θ(k^2), 等差数列求和而已
第三个等号

2^k*O(1) + 2^k*Θ(k^2) = 2^k [O(1)+Θ(k^2)] = 2^kΘ(k^2) = Θ(2^k*k^2)

这些看不出来很不应该

Answer 2

C