用数学归纳法证明递推系统
用数学归纳法证明递推系统
提问于 2011-04-08 10:45:18
有fnc的：
bool ISINTREE( int x, BinTree<int> t)
{
bool b = false
if (!t.isEmpty())
{
if (x == t.getRoot())
{ b = true }
else
{
if (ISINTREE(x,t.leftTree()))
{ b = true }
if (ISINTREE(x,t.rightTree()))
{ b = true }
}
}
return b
} 如何证明(用数学归纳法) T(n)= 11×2^n−7是该fnc递推系统的解。
编辑的
设F(n) =11*2^n-7
现在,
对于k>0
T(k-1) = F(k-1) = 11*2^(k-1)-7
T(k) = 7+2*(T(k-1))
=7 +2* (11*2^(k-1) -7)
= 11*2^k -7
回答 1
Stack Overflow用户
发布于 2011-04-11 15:27:23
n在这里是什么？树中元素的数量？如果是这样的话，我们肯定可以说，最坏的情况下，这个算法访问树中的每个节点，所以运行时是，最坏的情况下，T(n) = n，在这种情况下，前提(这是T(n) = 11 . 2^n - 7)是无效的。
更新
为了满足这种怀疑，让我们来看看最坏的情况(要查找的项不在树中)。在不失去通用性的情况下，让我们假设我们看到的是一棵完全平衡的树，即每个子树都有(n-1)/2元素。因此，在这些假设下，重复出现的关系是：
T(n) = 2.T((n-1)/2) + 7(我想说这里实际上只有4个可执行操作，但为了简单起见，我们把它称为7)。
显然，T(n) = 11 . 2^n - 7不是这种关系的解决方案。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5593962
复制相关文章
相似问题
腾讯云开发者
