4.3—代入法求解递归式

4.3—代入法求解递归式对于代入法求解递归式 有以下自己的感触 1 中间的证明过程用到了数学归纳法的思想 1 首先证明初始条件是不是满足的 例如 T n O nlgn 首先得验证当 n 1 的时候是不是满足条件 这里还 牵扯到一个边界条件不成立的问题 这可以让我们重新选取一个边界 毕竟这个大 O 记号是一种牵扯到达恩的想 法 所以边界的选取只要是一个有限的数字就可以了 2 接下来就是最重要的证明

大家好,我是讯享网,很高兴认识大家。

对于代入法求解递归式,有以下自己的感触:

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表示基本就求解出来了。

小讯
上一篇 2025-03-01 23:05
下一篇 2025-04-08 09:29

相关推荐

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