有冇人識 Big-O notation

提示: 作者被禁止或刪除 內容自動屏蔽

本帖最後由 ntony 於 2011-5-30 09:50 編輯

抱歉,恕刪。

TOP

本帖最後由 kazenorin 於 2011-5-30 22:56 編輯

其實好簡單, 最緊要係唔好張佢複雜化...


for(i = 0; i < n; i++){
...
}

咁樣上述既公式運行次數就係取決於 n 既數值...
n 每高 1, 就要行多 1 次
所以 Big-O 就係 O( n )

for(i = 0; i < n; i++){
  for(j = 0; j < n; j++){...}
}

上述既公式, n每高 1, 就要行多 n 次
所以 Big-O 就係 n既二次方, i.e. O (n^2)

然後如果繼續 loop 中 loop 就會變成 n 既 2, 3, 4 ... 次方...
i.e. O(n^c)
即係 n每增加1, 就要計多 n 既 c 次方咁多次

如果某公式, n 每增加 1, 只係需要多該回計算既一半時間...
咁就係 n log n (base-2/binary log)

如果某公式, 不受 n 數值影響, 咁就係 constant,  O ( 1 )...
如果某公式, n 每增加 1, 就要計多 「n 次方」咁多次, 就會得出超複雜的 O(c ^ n)...
e.g. f(n) = 123 ^ n, Big-O = O(c ^ n)

如為 n?
n 就係決定性的變數...
例如... 要數一間房裡面有幾多人...
唯一既方法就係逐個數...
每多一個人, 就要數多一次...
這公式就係取決於人數, n = 人數
而 Big-O 就係 O(n)... (因為每多一個人, 就要「計」多一次)

另外, Big-O 只係計算複雜程度, 所以只會以公式中最複雜果部份決定
以 f(n) = n^2 + n 為例,
Big-O 會係 O(n^2),
而不是 O(n^2 + 1) <- 這是錯誤的 Big-O...

所以找出數學算式既 Big-O, 只需著眼於增長得最快果個...

增長速度越快, 運算速度越慢, Big-O 越 complex
論增長速度:
c ^ n > n ^ c >  n! > n > n log n > log n > 1
1係冇增長... 所以增長速度最慢, 運算速度最快...
例子: 計算某數字(n)是雙數或單數...
公式: f(n) = n % 2
Big-O: O(1)
因為即使 n 係幾十億, 呢條公式都只係計一次

突然諗唔到 O(c ^ n) 既例子 ...

TOP

提示: 作者被禁止或刪除 內容自動屏蔽

TOP

其實好簡單, 最緊要係唔好張佢複雜化...


for(i = 0; i < n; i++){
...
}

咁樣上述既公式運行次數就係取 ...
kazenorin 發表於 2011-5-30 10:24



    O(n!) == O(n^n) ?

n! = ( n ) ( n - 1 ) ( ... ) = n ^ n + (....)

TOP

O(n!) == O(n^n) ?

n! = ( n ) ( n - 1 ) ( ... ) = n ^ n + (....)
happyhehe 發表於 2011-5-30 14:38



    n!= (n)(n-1)(n-2)....1
       <= (n)(n)(n)........(n)
       =n^n
So n! = O(n^n)

TOP

回復  kazenorin

如果個公式就咁 500, 個 big O notation 係咩?
hkguile 發表於 2011-5-30 14:13



    O(1)

TOP

本帖最後由 laputafish 於 2011-5-30 16:50 編輯
回復  kazenorin

如果個公式就咁 500, 個 big O notation 係咩?
hkguile 發表於 2011-5-30 14:13

       
kazenorin 兄講左, 所有不受n 數值影響, 都係 O(1).

再一個例子:
f(x) = 3x^10 - 2x^3 + 200000

呢個函數由三部份組成, 3x^10, -2x^3, 200000.
當 x 變化, 其中 3x^10 果部份變化最大, 攞 3x^10.
其中個 "3" 係 constant, 可以踼走佢, 剩番 x^10

咁 f(x) = O(x^10)

TOP

本帖最後由 travel 於 2011-5-30 22:17 編輯
...
n > n log n
...
以 f(n) = n^2 + n 為例,
Big-O 會係 O(n)


   

TOP

n!= (n)(n-1)(n-2)....1
tonald 發表於 2011-5-30 14:49



    n! 既 Big-O 係 O(n!)

點會係 O(n^n) 或者係 O(c^n)

O(n^n) 要 f(n) = n^n 先得

O(n!) 只係 f(n) = (n)(n-1)(n-2) ... 1 就得

TOP