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

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(x) = Theta(2^x) (注意时间复杂度是一样的)。这也证明g(x) = Theta(2^x)作为f(x) > g(x) > f(x-1) .

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

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

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

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

这意味着 f(x) = Theta(2^x) , 作为 H(x) = Theta(2^x) ，这本身是因为 H(x)/2^x -> sqrt(e) as x-> infinity (限制的wolfram alpha链接)。

现在(警告较重的数学，也许 cs.stackexchange 或 math.stackexchange 更适合)

根据 wolfram alpha (单击链接并查看 x = 无穷大附近的级数展开)，

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

再次，根据 wolfram alpha (单击链接(与上面不同)并查看 x = infinity 的级数展开)，我们有

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

等等

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

因此，对于足够大的 x (比如说 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)

因此 f(x+1) <= K * H(x+1)