递推关系 T(n) = T(T(n - 1)) + 1 有解吗？

Question

这个递归关系有什么解决办法吗

T(n) = T( T( n - 1 ) ) + 1

来自类似 C 语法的代码

Algo(int n)
{
    printf("%d ->",n);
    return (n >= 1)?Algo(Algo(n - 1))+1:1;
} 

#include <stdio.h>
int main(void){
    printf("\tEnd: %d",Algo(3));
    return 0;
}

结果：

3->2->1->1->2->1->1 结束：3

如何求这个关系的时间复杂度？

谢谢你

Answer 1

有什么解决办法吗

根据

T(0)

的值，并假设

n = 0,1,2 ...

有一个解决方案：

T(n) = T(0) + n

证明：

n	T(n)	T(n)
0	T(0)=	X
1	T(1) =	T(0)+1 = (X)+1
2	T(2)=	T(1)+1 = (X+1)+1
3	T(3)=	T(2)+1 = (X+1+1)+1
4	T(4) =	T(3)+1 = (X+1+1+1)+1
5	T(5)=	T(4)+1 = (X+1+1+1+1)+1
6	T(6) =	T(5)+1 = (X+1+1+1+1+1)+1
7	T(7) =	T(6)+1 = (X+1+1+1+1+1+1)+1
8	T(8)=	T(7)+1 = (X+1+1+1+1+1+1+1)+1

如果解决方案/假设可以接受，请分享。 (:

Answer 2

我认为你的意思是：“return (n >= 1)?Algo(Algo(n - 1))+1:0” 在这种情况下，递归被精确调用 2^(n + 1) - 1 次，因为在每个阶段递归树都会分裂成 2 个子树。 您还可以放置一个静态计数器并测试不同的 n 值。