分治算法的复杂度

代入法

1:

2:

3:

代入法就是知道结果，然后把结果代入进去 用数学归纳法证明成立就表示假设是正确的。
我们知道分治策略的复杂度是nlgn
公式一是用θ记号表示的复杂度上界
把这个结果带入到公式1中，得到公式2
公式2 因为n/2取下操作 所以公式二小于用n/2替换取下操作的n/2
得到公式3
右边等于 cn * lgn - cn +n = cnlgn-n(c-1)
算法中把lgn当做以2为底的 所以lg2 = 1
只要c>1就会成立

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容