-5
A
回答
1
讓我解釋其中之一,看看你是否可以嘗試其餘的。
f(n) is O(g(n)) "function f of n" is ("big O") **Order** g(n)
if for some n (maybe not f(0) or f(1) or... but eventually for some n)
and for some **constant** (1, 2, 50, 80 million, something)
f(n) <= c * g(n)
So if we say some function f is "O(log n)" than means that starting at
some n that we pass into f(), and some number c then
f(n) <= c * log(n)
讓我們一個非常簡單的例子:
function f (n) {
answer = 0;
for (i = 0; i < n; ++i) { // loops n times
answer += n+3; // 2 ops: add, add
answer /= (7*n); // 2 ops: mult, div
answer ^= 2; // 1 op: xor
} // 2 + 2 + 1 = 5
return answer;
}
所以,我們可以說 'C' 是5,和g(n)是N(我們清楚地循環n次)。
f (n) <= 5 * g(n)
f (n) <= 5 * n
f() is O(n)
基本上這是說什麼,當n變得足夠大時,常數因子根本就不重要。如果f(n)是(5n)或(7n)或(27n),當我們可以將其與其他函數(87log(n))或(0.01n 2)進行比較時,它幾乎沒有區別。
\ n 10 1000 100000
f(n) \-----------------------------
7n | 70 7000 700000 O(n) grows linearly with prob size
87logn | ~200 ~600 ~1000 O(log n) grows slowly [good!]
.01n² | 10 10000 100000000 O(n²) grows fast [bad!]
相關問題
- 1. 大O而不是小O意味着Theta?同樣,大歐米茄和不小歐米加意味着Theta?
- 2. 算法複雜度大O,小O,大歐米茄,小歐米茄,西塔
- 3. 任何人都可以解釋大O與大歐米茄vs Big Theta?
- 4. 大歐米茄分析
- 5. 算法分析(大O和大歐米茄)
- 6. 大O和大歐米茄是相同的,但相反?
- 7. 給大O,大西塔和Big歐米茄功能
- 8. 以下功能的大哦,theta和歐米茄w /說明?
- 9. 算法的計算複雜性在大哦,大歐米茄和Theta
- 10. 大歐米茄符號證明
- 11. 證明大歐米茄功能
- 12. 是大歐米茄分配到加法?
- 13. 幫助大歐米茄證明?
- 14. 算法比較大O,西塔和歐米茄
- 15. 什麼是變量'C'是指大O或歐米茄符號
- 16. 等於歐米茄()在jeet?
- 17. 歐米茄4.x子主題創作
- 18. 主題歐米茄3 - 使用區域
- 19. 歐米茄指南針庫錯誤
- 20. 下界歐米茄表示法
- 21. 整齊/歐米茄網格問題
- 22. clojure庫函數的大O
- 23. 函數的大O計算
- 24. 大O符號Python函數
- 25. 大O和函數統治
- 26. 什麼時候使用大O而不是theta或小o
- 27. 檢查大歐塔,小哦,小歐米加限制?
- 28. 大O
- 29. 指數函數的大O符號
- 30. 大O分析指數函數
現在看起來你只是要求我們爲你做功課。你試過什麼了?你有什麼想法?你有直覺瞭解發生了什麼? – templatetypedef
我不知道,所以我問任何線索。除了Big-o的定義之外,我有點失落了。 –
@KaranSingla - 我的回答是否有任何指導? –