大O分析指數函數

Question

對於下面的功能，

我做

但我一定是做錯了什麼？答案應該是O(log n)。我對大O很糟糕... ...還沒有完全理解尚未在學校教授的大師定理。他們只教了遞歸樹

Answer 1

如果我們假設所有的算術運算都是在O（1）中完成的，那麼： 當我們看到每個函數調用時，我們將exp分解爲2，當exp達到零時 - 我們完成了。 我們可以多少次分割兩次而不是零？這是日誌exp。所以log exp函數調用* O（1）給出了log（exp）的複雜性。等比數列的 查找和你找到答案了另一個問題：多少個節點，其中n完全（所有的兄弟姐妹有）樹葉： 設N = 4：

 
1' 
|_1'' 
    |_1''' 
    |_2''' 
|_2'' 
    |_3''' 
    |_4''' 

你發現節點的數量在這樣的樹

Answer 2

你讓你的數學開始是說，你在函數調用Exp(n)花「N」時的假設，「N/2」 Exp(n/2)時間，「N/4」 Exp(n/4)等時間在...

但是，實際上，你只花費不變每個函數調用中的時間爲O(1)。那麼，你有恆定時間的函數調用。嘗試用這個開始的假設運行你的數學的其餘部分，看看你得到了什麼。