数据结构和算法方面的问题。关于时间复杂度的求法。关于代入法和主定理，谢谢！ 问题可能有点多，
发布网友
发布时间：2022-05-24 18:10
共1个回答
热心网友
时间：2023-10-24 13:08
当然, 从你的叙述来看, 你连主定理都没有理解, 所以你的首要任务是先学会用主定理.
粗略地讲, 主定理的基本思想是对
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)
这些看不出来很不应该
