我有一个奇怪的算法,而不是递归调用2次.它的
int alg(int n)
loop body = ?(3n+1)
alg(n-1);
alg(n-2)
不知何故,我需要找到这个算法的复杂性.我试图使用上述方程的特征多项式找到它,但结果系统太难解决所以我想知道是否有任何其他直接方式..
我没有隐瞒这是我作业的一部分,但在发布之前我已经尝试过了.
所以...
我需要证明一个二叉树,节点k的左子节点在2k上,右子节点在2k + 1位置.我用感应证明了这一点.
现在我需要证明一个二叉树,节点k的父节点(floor)(k/2)位置.我拿了两个案子.
也用感应试了一下.对于3个节点的树来说确实如此.
如果对于节点k是真的,我将证明节点k + 1.
我正在尝试制作一般的二叉树,但这些类型不会帮助我使用归纳假设.我想也许我将不得不使用我之前证明的孩子的位置.
有帮助吗？
我有一个递归算法,如:
int alg(int n) {
if (n == 0)
return 2;
for (int i = 0; i<= n-1; ++i)
alg(i);
}
n == 0情况显然是这样的?(1).但是我无法理解它是如何工作的.我的意思是它必须是这样的:
T(n) = T(0) + T(1) + ... + T(n-1).
然后我们必须给予T(1), T(2), .., T(n-1) = xT(0).我可以理解n = 0和n = 1的方式,但是对于更大的n,它会出错.