リカバリーアルゴリズムの時間計算量を計算する

Question

私は再帰アルゴリズムの時間計算量を計算しようとしています。ここで私が見てきた擬似コードです：

long pow(long x, int n) { 
    if (n == 0) 
     return 1; 
    if (n == 1) 
    return x; 
    if(isEven(n)) 
     return pow(x, n/2) * pow(x, n/2); 
    else 
     return x * pow(x * x, n/2); 
} 

ISEVENは単にそれに渡された整数が偶数かではなく、この例のポイントのために、一定の時間で動作しているか否かを判定する。

したがって、n = 0またはn = 1の場合、これは以下のように一定時間動作を行います。 f（n）= C0。 しかし、n> 1の場合、f（n）= f（n-1）+ f（n-1）+ C1となる。 ）+ 1、nが奇数の場合、正しい？または、nが偶数のときf（n）= f（n/2）+ f（n/2）+ C1、nが奇数のときf（n）= f（n/2）

私はたくさんの例を見てきました。 Hereは非常に参考になった1つです。私の問題は、nが偶数であるときに2つの再帰呼び出しがあることに由来します。私はここで何をすべきかを完全には分かっていません。誰かが正しい方向に私を指すことができるなら、私は本当にそれを感謝します。

Answer 1

Master Theoremをご覧ください。これを「分割と征服」アルゴリズムとして扱うことができます。

最終的には、2つの再帰呼び出しを実行すると、最悪の場合のO（n）ランタイムになります。例えば。 pow（x、4）はpow（x、2）を2回、pow（x、1）を4回呼び出します。一般に2の累乗はn * 2-1コールをもたらす。

また、pow（x、n/2）を一度呼び出し、その分岐で結果を二乗することによって、アルゴリズムはO（log n）になります。

Answer 2

f（m）は、サイズmの問題の操作数を与えるものとして定義しましょう。 「問題」はもちろん累乗（pow）で、例えばx^nまたはpow(x,n)です。 long pow(long x, int n) {関数は、xを変更すると多かれ少なかれ作業を行う必要はありません。したがって、問題累乗のサイズはxに依存しません。しかしそれはnに依存する。 2^4のサイズが4で、3^120のサイズが120の場合を考えてみましょう。2^4=2*2*2*2と3^120=3*3*3*3*..*3が表示されていれば理にかなっています。したがって、問題のサイズはnです。もしあなたが望むなら、問題のサイズは2 * log（n）と言うことができますが、それは愚かです。

ここで、f（m）は任意のxに対してpow(x,m)を計算する操作の数です。 pow(x,m)は正確にサイズmの問題です。 したがって、pow(x,y)がある場合、操作の数は、定義により、f(y)となります。たとえば、pow(3,3*m/2)は、f(3*m/2)の操作を持ちます。

は最後に、みんなでそれを取る操作

long pow(long x, int n) { 
    if (n == 0) //1 
     return 1; 
    if (n == 1) //1 
    return x; 
    if(isEven(n)) //1 
     return pow(x, n/2) * //that is f(n/2), y=n/2 
       pow(x, n/2); //also f(n/2) 
    else 
     return x * pow(x * x, n/2); //1+1+f(n/2) 
} 

を数えてみましょう：f(n) = 2*f(n/2) + c1（nは偶数）とf(n) = f(n/2) + c2（nは奇数）。最悪のシナリオにのみ関心がある場合は、奇妙なケースはあまり効果がないことに注意してください。したがって、f（n）は、偶数の場合：f(n) <= 2*f(n/2)+cで上に境界付けられます。