对于代入法求解递归式,有以下自己的感触:
1.中间的证明过程用到了数学归纳法的思想:
(1)首先证明初始条件是不是满足的,例如T(n)=O(nlgn),首先得验证当n=1的时候是不是满足条件,这里还牵扯到一个边界条件不成立的问题,这可以让我们重新选取一个边界,毕竟这个大O记号是一种牵扯到达恩的想法,所以边界的选取只要是一个有限的数字就可以了。
(2)接下来就是最重要的证明,假设它对于更小规模的T(n')也是成立的,例如T(n)=2T(n/2)+n,更小的规模就是T(n/2)时成立的,接下来就是证明利用递推关系式怎么得到T(n)也是满足大O不等式的。
(3)有了这两个步骤,对于一个递归式的大O表示基本就求解出来了。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/79384.html