php网站开发薪资,做信息发布网站要多少钱,广州建设工程交易中心专题片,销售的技巧与口才1 问题 2 解决思路
使用递归树猜想一个上界#xff0c;使用归纳法证明上界也是下界。
2.1 使用递归树#xff08;recursion tree#xff09;猜想结论#xff08;不严谨#xff09;
使用递归树两点#xff1a;1⃣️逐行展开#xff1b;2⃣️逐行相加#xff1b;
逐行…1 问题 2 解决思路
使用递归树猜想一个上界使用归纳法证明上界也是下界。
2.1 使用递归树recursion tree猜想结论不严谨
使用递归树两点1⃣️逐行展开2⃣️逐行相加
逐行展开
本质上是分解问题每个非叶子结点表示分解合并问题所付出的代价叶子结点表示解决边界问题所付出的代价。
逐层求和
这里要注意除去非叶子结点每一层的和呈现出等比数列性质计算整个代价T(n)T(n)T(n)本质上就是分解合并问题付出的代价解决递归边界付出的代价。
Case1:
分解问题的代价 解决递归边界的代价 Θ(nlogba)\Theta(n^{log_ba})Θ(nlogba)。 取多项式最高次项因此T(n)O(nlogba)T(n) O(n^{log_ba})T(n)O(nlogba);
Case2:
分解问题的代价 解决递归边界的代价 Θ(nlogba)\Theta(n^{log_ba})Θ(nlogba)。 取多项式最高次项因此T(n)O(nlogbalogbn)T(n) O(n^{log_ba}log_bn)T(n)O(nlogbalogbn);
Case3:
分解问题的代价 根据假设容易得到 上面的不等号是渐进成立的所以为了保证对每一个nnn都成立对于前有限的nnn要加上每一个都要加上一个足够大的常数因此有下面的式子。 解决递归边界的代价 Θ(nlogba)\Theta(n^{log_ba})Θ(nlogba)。 取多项式最高次项因此T(n)O(f(n))T(n) O(f(n))T(n)O(f(n));
2.2 使用归纳法证明结论严谨
上面的递归树分析只是大概得到了一个上界下面使用数学归纳发证明上届也是下界。
Case1: Case2: Case3: 3 结论
先使用非严谨的形式分析、猜想然后用数学归纳法证明这个思路贯穿整个导论一书主定理由递归树推出很多情形不符合主定理的假设但是递归树归纳法仍然可以解决所以整个过程最有价值的是这套分析、证明方法而非主定理。上面在使用归纳法证明时渐进符号的威力惊艳了我
