遞歸指數運算器的輸出和複雜度

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爲偶數，它將exceute（B％2）2 ==灣如果b爲奇數，它會exceute一個 EXP3（A，B-1）。我的程序沒有問題。如果b爲4，（4％2）* 2 = 0，和0是不等於b。所以我無法理解如何計算偶數時的b值。

問題2：

我想calucate在程序步數。所以根據我的教科書，我可以得到如下的形式。 B還送噸（B）= 6 + T（B/2） b奇數T（B）= 6 + T（B-1） 爲什麼是第一數目6？我怎樣才能在開始時得到數字3？

Answer 1

你(b%2)*2 == b測試是不正確的。我想你想b % 2 == 0測試是否b是偶數。該代碼仍然得到正確的答案，因爲另一個遞歸案例（僅適用於奇數b值）也適用於偶數（這只是效率較低）。

至於你的其他問題，我不知道那裏的6無論從未來。這很大程度上取決於你計算的「步驟」。通常，根據「大O」值而不是具體數字來討論性能是非常有用的。