使用递归方程的程序的时间复杂度

Question

我想用递推方程找出程序的时间复杂度.那是 ..

int f(int x)
{
if(x<1) return 1;
 else  return f(x-1)+g(x); 
}
int g(int x)
{
if(x<2) return 1;
 else return f(x-1)+g(x/2);
}

我写了它的递推方程并尝试解决它,但它继续变得复杂

T(n) =T(n-1)+g(n)+c
         =T(n-2)+g(n-1)+g(n)+c+c
         =T(n-3)+g(n-2)+g(n-1)+g(n)+c+c+c
         =T(n-4)+g(n-3)+g(n-2)+g(n-1)+g(n)+c+c+c+c
         ……………………….
        ……………………..
        Kth time …..
        =kc+g(n)+g(n-1)+g(n-3)+g(n-4).. .. . … +T(n-k)

Let at kth time input become 1
Then n-k=1
         K=n-1
Now i end up with this..
T(n)= (n-1)c+g(n)+g(n-1)+g(n-2)+g(n-3)+….. .. g(1)

我无法进一步解决它.如果我们计算这个程序中函数调用的数量,可以很容易地看出时间复杂度是指数级的,但我想用重复证明它.怎么做到呢 ？

在Anwer 1中的解释,看起来正确,我做过类似的工作.

这段代码中最困难的任务是写出它的递归方程.我已经绘制了另一个图,我确定了一些模式,我认为我们可以从这个图中得到一些帮助,可能是可能的递归方程.

And I came up with this equation , not sure if it is right ??? Please help.

T(n) = 2*T(n-1) + c * logn

Answer 1

设 f(0)=0 且 g(0)=0

从我们拥有的函数来看，

f(x) = f(x - 1) + g(x) 
g(x) = f(x - 1) + g(x/2)

将 g(x) 代入 f(x) 我们得到，

f(x) = f(x-1) + f(x -1) + g(x/2)

∴f(x) = 2f(x-1) + g(x/2)

扩展这个我们得到，

f(x) = 2f(x-1)+f(x/2-1)+f(x/4-1)+ ... + f(1)

令 s(x) 为定义如下的函数，

s(x) = 2s(x-1)

现在显然 f(x)=Ω(s(x))。

s(x) 的复杂度为 O(2 ^x )。

因此函数 f(x)=Ω(2 ^x )。