確定的遞推關係

Question

我發現在網絡上下面的代碼，我知道這是用b 整數倍，但我在尋找遞推關係或確定的複雜問題，所以你能指導我

public int mystery(int a, int b) { 
if (b == 0) return 0; 
else if (b % 2 == 0) 
    return mystery(a + a, b/2); 
else return mystery(a + a, b/2) + a; 
} 

Answer 1

遞歸關係由函數本身定義。我認爲它不會在數學符號上有很大差異。

複雜度僅取決於b，其指數級地減小直到停止條件。因此複雜度將是O(logb)。