求解该式的意图谬见

来源：蜘蛛抓取(WebSpider) 时间：2020-01-29 03:01 标签： 什么意图
求解递归式即找出解的渐进界┅般有3种方法：

代换法只能用于解那种很容易猜的情形，它可用来确定一个递归式的“O”和“Ω”界。

1.1 先猜测有某个界存在


由于这个递归式与合并排序的计算时间复杂度的递归式很相似所以我们猜测其解为 T(n) = O( n*log(n) )

1.2 然后用数学归纳法证明该猜测的正确性

先假设这个界对└n/2┘成立，即 T(└n/2┘) =

接下来应用数学归纳法证明对边界条件也成立


注意对于此递归式要将n=1的特殊情况，与n=23 ...等普遍情况分开。

2.1 将递归式转换为树形结構树中的节点代表在不同递归层次中付出的代价

2.2 再利用对和式限界的技术来解出递归式

3.2 这种方法要记忆三种情况，做到了这点就可以佷容易地确定很多简单的递归式的界了

0

我要回帖

更多关于 什么意图 的文章

 

随机推荐