このアルゴリズムの実行時の複雑さは？

Question

与えられたaとbは、O（b）よりも速いランタイムでa^bを計算するように求められます。私はついた：

if(b == 1) return a; 
if(b % 2 == 0) 
    return findExp(a,b/2) * findExp(a,b/2); 
else 
    return findExp(a,(b/2)+1) * findExp(a,b/2); 

私の質問は、このアルゴリズムの対数時間または多項式時間の実行時の複雑さですか？

Answer 1

あなたのアルゴリズムはO（b）対数ではありません。

コードのこの部分では、return findExp(a,b/2) * findExp(a,b/2);は同じ値を2回返す同じ関数を呼び出しています。基本的には、2回目のコールに冗長な時間を費やしています。

数学的に、T（b）があなたのアルゴリズムに従って^ bに必要な時間を表すならば、各項は各呼に対応するT(b) = T(b/2) + T(b/2)です。 T(b) = 2.T(b/2)。この再発を解くと、bの順にT（b）が得られます。

対数型にするには、値を変数に格納してその冗長な呼び出しを防ぐだけです。

編集したコード：

if(b == 1) return a; 
if(b % 2 == 0) 
    int x = findExp(a,b/2); 
    return x*x; 
else 
    int x = findExp(a,b/2); 
    return a*x*x; 

今T(b) = T(b/2)あなたがfindExpを呼び出しているので、（、/ 2 b）は、一度だけ（どちらかifの一部またはelse一部）。あなたたいテストそれは、あなたのコードといくつかの大規模なBのために私が言及したものを実行する場合

これはあなたにO(log(b))アルゴリズムを与える

、私たちはB = 1000000000を言わせて、撮影した時間を対比。

Answer 2

これはO（log（b））なので、対数です。