13

I want to find out the time complexity of the program using recurrence equations. That is ..

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);
}

I write its recurrence equation and tried to solve it but it keep on getting complex 

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)

I ‘m not able to solve it further. Any way if we count the number of function calls in this program , it can be easily seen that time complexity is exponential but I want proof it using recurrence . how can it be done ?

enter image description here

Explanation in Anwer 1, looks correct , similar work I did.

The most difficult task in this code is to write its recursion equation. I have drawn another diagram , I identified some patterns , I think we can get some help form this diagram what could be the possible recurrence equation.

For f(2)

For f(3)

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

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

4 回答 4

3

好的，我想我已经能够证明这一点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)（因为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( wolfram alpha link of the limit) 得出的。

现在（警告：更重的数学，也许 cs.stackexchange 或 math.stackexchange 更适合）

根据wolfram alpha（单击链接并查看 x = infinity 附近的级数展开），

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)

于 2013-03-24T22:17:09.827 回答
1

使用memoisation，这两个函数都可以在 O(n) 时间内轻松计算。但是该程序至少需要 O(2^n) 时间，因此是一种非常低效的计算方式，f(n)并且g(n)

为了证明程序对于任何 epsilon > 0最多花费O(2+epsilon)^n 时间：

令 F(n) 和 G(n) 分别是在计算 f(n) 和 g(n) 时进行的函数调用的数量。显然（将添加计为 1 个函数调用）：

F(0) = 1; F(n) = F(n-1) + G(n) + 1
G(1) = 1；G(n) = F(n-1) + G(n/2) + 1

那么可以证明：

  • F 和 G 是单调的
  • F > G
  • 定义 H(1) = 2；H(n) = 2 * H(n-1) + H(n/2) + 1
  • 显然，H > F
  • 对于所有 n，H(n) > 2 * H(n-1)
  • 因此 H(n/2) / H(n-1) -> 0 对于足够大的 n
  • 因此 H(n) < (2 + epsilon) * H(n-1) 对于所有 epsilon > 0 且足够大的 n
  • 因此对于任何 epsilon > 0 的 O((2 + epsilon)^n) 中的 H
  • （编辑：最初我在这里得出的结论是上限是 O(2^n)。这是不正确的，正如 nhahtdh 指出的那样，但见下文）
  • 所以这是我能证明的最好的......因为 G < F < H 对于任何 epsilon > 0，它们也在 O((2 + epsilon)^n) 中

后记（在看到 Knoothes 先生的解决方案之后）：因为恕我直言，一个好的数学证明可以提供洞察力，而不是大量的公式，并且所有这些后代都存在 SO（嗨，女士们！）：

对于许多算法，计算 f(n+1) 涉及两倍（三倍，..）f(n) 的工作量，再加上更多。如果随着 n 的增加（通常是这种情况），使用上面的固定 epsilon 会变得相对较少，这不是最佳的。用 n 的某个递减函数 ε(n) 替换上面的 epsilon 在许多情况下（如果 ε 下降得足够快，比如 ε(n)=1/n）会产生一个上限 O((2 + ε(n))^ n ) = O(2^n)

于 2013-03-24T10:00:22.817 回答
-1

我认为很清楚 f(n) > 2 n，因为 f(n) > h(n) = 2h(n-1) = 2 n。

现在我声称对于每一个 n，都有一个ε满足： f(n) < (2+ε) n，为了看到这一点，让我们通过归纳来做，但首先为了让它更合理，我将使用 ε = 1，显示 f(n) <= 3 n，然后我将扩展它。

我们将使用强归纳法，假设对于每个 m < n, f(m) < 3 m那么我们有：

f(n) = 2[f(n-1) + f(n/2 -1) + f(n/4 -1)+ ... +f(1-1)]

但是对于这一部分：

A = f(n/2 -1) + f(n/4 -1)+ ... +f(1-1)

我们有：

f(n/2) = 2[f(n/2 -1) + f(n/4 -1)+ ... +f(1-1]) ==>

A <= f(n/2)   [1]

所以我们可以重写 f(n)：

f(n) = 2f(n-1) + A < 2f(n-1) +f(n/2),

现在回到我们的主张：

f(n) < 2*3^(n-1) + 2*3^(n/2)==>
f(n) < 2*3^(n-1) + 3^(n-1) ==>
f(n) < 3^n.  [2]

通过[2]，完成了f(n)∈O(3 n )的证明。

但是如果你想把它扩展到 (2+ε) n的格式，只需用1来代替不等式，那么我们将有

对于 ε > 1/(2+ε) n/2-1 → f(n) < (2+ε) n .[3]

同样通过[3]你可以说对于每个 n 都有一个 ε 使得f(n) < (2+ε) n实际上有一个常数 ε 使得对于 n > n 0 , f(n)∈O(( 2+ε) n )。[4]

现在我们可以像@Knoothe 一样使用wolfarmalpha，通过设置 ε=1/n，我们将拥有：

f(n) < (2+1/n) n这导致 f(n) < e*2 n，并且通过我们在开始时的简单下限，我们有：f(n)∈ Θ(2^n)。 [ 5]

PS：我没有准确计算epsilon，但是你可以用笔和纸简单地计算，我认为这个epsilon不正确，但很容易找到它，如果很难告诉我很难，我会​​写它。

于 2013-03-24T15:09:27.527 回答
-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 )。

于 2013-03-24T08:35:20.973 回答