再帰的累乗器の出力と複雑度

Question

def exp3(a,b): 
     if b == 1: 
      return a 
     if (b%2)*2 == b: 
      return exp3(a*a, b/2) 
     else: return a*exp3(a,b-1) 

これは再帰的な累乗プログラムです。

質問1：

bが偶数である場合、それは（B％2）2 == Bをexceuteう。 bが奇数の場合は、 exp3（a、b-1）をエスケープします。私のプログラムに問題はありません。 bが4の場合、（4％2）* 2 = 0となり、0はbと等しくなりません。だから私はそれが偶数のときにbを計算する方法を理解できません。

質問2：

私はプログラムのステップ数をcalucateたいです。私の教科書によれば、私は次のように書式を得ることができます。 b偶数t（b）= 6 + t（b/2） b奇数t（b）= 6 + t（b-1） なぜ最初の番号6ですか？最初に番号3を得るにはどうすればいいですか？

Answer 1

あなたの(b%2)*2 == bテストは決して真です。 bが偶数の場合には、b % 2 == 0をテストしたいと思います。他の再帰的なケース（奇数bの値のみを対象としています）は、偶数の場合でも有効です（効率があまり良くありません）。

あなたの他の質問については、6がどこから来ているのかわかりません。それはあなたが「ステップ」として数えているものに大きく依存します。通常は、特定の数値ではなく「Big-O」の値でパフォーマンスを議論するのが最も便利です。