Q
大O分析指數函數
0
A
回答
2
如果我們假設所有的算術運算都是在O(1)中完成的,那麼: 當我們看到每個函數調用時,我們將exp分解爲2,當exp達到零時 - 我們完成了。 我們可以多少次分割兩次而不是零?這是日誌exp。所以log exp函數調用* O(1)給出了log(exp)的複雜性。等比數列的 查找和你找到答案了另一個問題:多少個節點,其中n完全(所有的兄弟姐妹有)樹葉: 設N = 4:
1' |_1'' |_1''' |_2''' |_2'' |_3''' |_4'''
你發現節點的數量在這樣的樹
1
你讓你的數學開始是說,你在函數調用Exp(n)
花「N」時的假設,「N/2」 Exp(n/2)
時間,「N/4」 Exp(n/4)
等時間在...
但是,實際上,你只花費不變每個函數調用中的時間爲O(1)
。那麼,你有恆定時間的函數調用。嘗試用這個開始的假設運行你的數學的其餘部分,看看你得到了什麼。
相關問題
- 1. 指數大O等效
- 2. 作業 - 大O分析
- 3. 函數的大O計算
- 4. 大O和函數統治
- 5. 大O符號Python函數
- 6. 大O,大歐米茄,大theta函數
- 7. 具有多個參數的方法的大O分析
- 8. Python數據結構的大O分析列表
- 9. 算法分析:大O /最壞情況
- 10. 分析運行時間,大O
- 11. 大O問題 - 算法分析II
- 12. 大O問題 - 算法分析
- 13. 算法分析大O符號
- 14. 大O符號 - 遞歸函數
- 15. 計算遞歸函數的大O
- 16. 記錄函數的大O表示
- 17. 確定函數的大O複雜度
- 18. 大O操作數
- 19. XML分析大量數據
- 20. 動態函數分析
- 21. 遞歸函數分析
- 22. 在MATLAB大爭論的指數函數
- 23. C函數指針分配
- 24. 對於遞減函數的操作數大O 0
- 25. 分組在大數據,而指數
- 26. C++數據結構大O
- 27. 指數函數沒有分配給鴨
- 28. 分頁與笨,沒有指數函數
- 29. YUI數據表和大型數據集W/O分頁
- 30. 在構造函數和析構函數中讀取會話變量的I/O
關於你的'這是正確的部分':不。 – Blender
這看起來像是http://en.wikipedia.org/wiki/Exponentiation_by_squaring(Square-And-Multiply)複雜性必然會導致exp,它將每個「step」減半。當你看到每步減少一個常數因子時,它通常是對數複雜度。 – sleeplessnerd