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)、 as 、それ自体が(極限のwolfram alpha link)H(x) = Theta(2^x)という事実から続くことを意味します。H(x)/2^x -> sqrt(e) as x-> infinity

今（警告：より重い数学、おそらく cs.stackexchange または math.stackexchange の方が適しています）

wolfram alphaによると(リンクをクリックして x = 無限大付近の級数展開を参照)、

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

また、ウルフラム アルファ(リンク (上記とは異なります) をクリックし、x = 無限大の級数展開を参照) によると、次のようになります。

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 = f(2L))Kのみに依存する) がいくつかあります。L

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)

Answer 2

memoisationを使用すると、両方の関数を O(n) 時間で簡単に計算できます。しかし、プログラムは少なくとも O(2^n) 時間かかるため、非常に効率の悪い計算方法ですf(n)。g(n)

0 より大きい任意のイプシロンに対して、プログラムが最大でO(2+イプシロン)^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) -> 十分に大きな n の場合は 0
• したがって、H(n) < (2 + イプシロン) * H(n-1) すべてのイプシロン > 0 および十分に大きな n
• したがって、任意のイプシロン > 0 の O((2 + イプシロン)^n) の H
• (編集: 当初、上限は O(2^n) であるとここで結論付けました。 nhahtdh が指摘したように、これは正しくありませんが、以下を参照してください)
• これは私が証明できる最高のものです.... G < F < H であるため、それらは O((2 + epsilon)^n) にあるため、任意のイプシロン > 0 に対して

---

追記 (Knoothes 氏の解決策を見た後): 優れた数学的証明は、多くの式ではなく洞察を与えてくれるので、将来のすべての世代のために SO が存在するためです (こんにちは!):

多くのアルゴリズムでは、f(n+1) の計算には、f(n) の作業量の 2 倍 (3 倍、..) に加えて、さらに何かが必要です。これが n の増加に伴って相対的に小さくなる場合 (これはよくあることです)、上記のように固定イプシロンを使用することは最適ではありません。上記のイプシロンを n の減少関数 ε(n) で置き換えると、多くの場合 (ε が十分に速く減少する場合、ε(n)=1/n とします) 上限 O((2 + ε(n))^ が得られます。 n ) = O(2^n)

Answer 3

f(n) > h(n) = 2h(n-1) = 2 n であるため、 f(n) > 2 n であること^は明らかだと思います。

ここで、すべての n に対して、次のようなεがあると主張します: f(n) < (2+ε) ⁿ。 = 1、 f(n) <= 3 ⁿを表示するには、それを拡張します。

強い帰納法を使用します。すべての 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 ⁿ ) の証明が完了します。

^{しかし、これを (2+ε) n}の形式に拡張したい場合は、単に1を使用して不等式を置き換えると、次のようになります。

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

また、[3]によって、すべての n に対して、 f(n) < (2+ε) ⁿとなるような ε が存在すると言うことができます。実際には、n > n ₀に対して f(n)∈O(( 2+ε) ⁿ )。[4]

これで、@Knoothe のように wolfarmalphaを使用できます。ε =1/n を設定すると、次のようになります。

f(n) < (2+1/n) ⁿ結果は f(n) < e*2 ⁿとなり、開始時の単純な下限により、f(n)∈ Θ(2^n) .[ 5]

PS: イプシロンを正確に計算したわけではありませんが、ペンと紙で簡単に計算できます。このイプシロンは正しくないと思いますが、簡単に見つけることができます。難しい場合は難しいと教えてください。それ。

Answer 4

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 ) です。