主方法 - 与两个 T 的递归关系
斧头
我正在学习数据结构和算法课程（这很艰难）。我们学习了求解基本递推关系的主要方法，当它们的形式为 aT(n/b)+f(n) 时。现在我们已经了解了线性时间选择算法，它的关系不是这种形式，我被要求发现它的最坏情况运行时间是渐近符号。
我发现递归关系为：
在我看来，大师方法并没有考虑到这一点——我很可能是错的。如果不是，那么您如何找到最坏情况下的运行时间？
马特·蒂默曼斯
主定理不适用，但直接证明此递归的紧界并不难。
你知道你不能做得比O(n)更好，因为该术语已经在循环中。你被告知这是一个线性时间算法，根据一些经验，你会猜测子问题的总大小小于 n 的事实，所以你可以做O(n)是一个很好的选择.
剩下的就是证明。
你可以很容易地通过归纳来证明这一点。设 C 是一个（大）常数，使得：
T(n) <= T(n/101 + 1) + T(151n/202 + 101) + C(n+1)/202，对于所有n，（eq 1），和
T(n) <= C(n+1)，对于所有n < 1000 (eq 2)
对于任何n >= 1000，如果（eq 2）适用于所有较小的n，那么我们有
T(n) <= T(n/101 + 1) + T(151n/202 + 101) + C(n+1)/202 (eq 1)
T(n) <= C(n+202)/101 + C(151n+20604)/202 + C(n+1)/202 (subst eq 2)
T(n) <= C(2n+404)/202 + C(151n+20604)/202 + C(n+1)/202
T(n) <= C(156n+20604)/202
T(n) <= C(0.78n + 102) <= C(n - 0.22n + 102) <= C(n - 220 + 102)（因为 n>=1000）
T(n) <= C(n+1)
所以，如果我们像上面一样选择C，那么 (eq 2) 对n < 1000成立的事实意味着它对所有n 成立，并且T(n) 在 O(n) 中
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
约束两个递归多对多关系
- 2
约束两个递归多对多关系
- 3
CTE是处理两个表的递归的正确方法吗？
- 4
基于两个表的正确Laravel获取关系的方法
- 5
无法正确获得两个组合框和主窗口之间的关系
- 6
确定具有两个递归案例的递归方法的Big O？
- 7
带有两个初始语句的 T-SQL 递归
- 8
Scala：通过第三个关系来连接两个DataFrame的更好方法
- 9
不使用主定理的递归关系
- 10
具有多对多关系的两个表的CTE递归查询
- 11
推荐的方法来获取两个节点之间特定类型的单一关系
- 12
Cypher-在两个节点阵列之间创建关系的最佳方法
- 13
在Laravel中使用相同的控制器方法创建两个关系
- 14
两个共享许多方法但不具有“是”关系的Java类
- 15
通过关系连接使用匹配两个值的mysql返回行的方法
- 16
合并两个分支而不是主
- 17
意外的两个主分支Git
- 18
递归减去两个JavaScript对象
- 19
两个函数之间的尾递归
- 20
合并两个列表并递归排序
- 21
两个函数之间的递归调用
- 22
两个类似的递归代码
- 23
C编程-递归的两个for循环
- 24
为什么我需要实现IComparable <T>来比较通用方法中的两个值？
- 25
IEnumerable <T>-如何为两个枚举器使用一种方法
- 26
为什么IEqualityComparer <T> Equals方法采用两个参数？
- 27
Python-在两个类之间创建多对一关系，并创建一个相互引用的方法
- 28
确定两个元素之间的关系
- 29
两个类之间的OOP关系
我来说两句