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

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

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

好吧，我想我已经能够证明这一点f(x) = Theta(2^x)（注意时间复杂度是一样的）。这也证明了g(x) = Theta(2^x) as f(x) > g(x) > f(x-1).

首先，正如大家所指出的，很容易证明f(x) = Omega(2^x).

现在我们有这样的关系f(x) <= 2 f(x-1) + f(x/2) (since f(x) > g(x))

我们将证明，对于足够大的x，有一些常数K > 0这样

f(x) <= K*H(x), where H(x) = (2 + 1/x)^x

这意味着f(x) = Theta(2^x), as H(x) = Theta(2^x)，这本身就源于以下事实：H(x)/2^x -> sqrt(e) as x-> infinity (阿尔法钨 http://www.wolframalpha.com/input/?i=Limit%20x-%3E%20infinity%20%282%2b1/x%29%5Ex/2%5Ex限制的链接）。

Now (warning:较重的数学，也许 cs.stackexchange 或 math.stackexchange 更适合）

根据阿尔法钨 http://www.wolframalpha.com/input/?i=%282%20%2b%201/x%29%5Ex（单击链接并查看 x = 无穷大附近的级数展开），

H(x) = exp(x ln(2) + 1/2 + O(1/x))

再次，根据阿尔法钨 http://www.wolframalpha.com/input/?i=%282%20%2b%201/x%29%5Ex%20-%202%2a%282%20%2b%201/%28x-1%29%29%5E%28x-1%29（单击链接（与上面不同）并查看 x = 无穷大的级数展开），我们有

H(x) - 2H(x-1) = [1/2x + O(1/x^2)]exp(x ln(2) + 1/2 + O(1/x))

and so

[H(x) - 2H(x-1)]/H(x/2) -> infinity as x -> infinity

因此，对于足够大的x (say x > L）我们有不等式

H(x) >= 2H(x-1) + H(x/2)

现在有一些K（仅取决于L（例如 K = f(2L))）使得

f(x) <= K*H(x) for all x <= 2L

现在我们继续进行（强）归纳（如果您愿意，您可以恢复为自然数）

f(x+1) <= 2f(x) + f((x+1)/2)

通过归纳法，右边是

<= 2*K*H(x) + K*H((x+1)/2)

我们之前证明了

2*H(x) + H((x+1)/2) <= H(x+1)

Thus f(x+1) <= K * H(x+1)