※ 引述《ReinInPtt ( 敗與沒輸的差異)》之銘言：
: 誰能用比較日常的方式解釋大O
: 阿...?
給定一g(n)
O(g(n))為一個函數集合f(n)
這些f皆符合0<=f(n)<=c*g(n)
其中c為常數
基本上就是找上限
--
其實嚴謹一點要加n0的
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.16
> -------------------------------------------------------------------------- <
作者: lfst (計概國文計程普物) 看板: b92902xxx
標題: Re: big-O新解
時間: Sat Nov 1 22:58:24 2003
說點正經的..big O
Big-O函數通常稱為程式或演算法的時間複雜度（time complexity）
頻率計數 時間複雜度
15 O(1)
3n+3 O(n)
5n2+2n+3 O(n2)
(n2(n-1))/2 O(n3)
4logn+5 O(logn)即指O(log2n)
3*2n+2*n3+7 O(2n)
時間複雜度
T(n)：程式執行時所需的時間。
n：資料量的大小。
時間複雜度：輸入量夠大時，演算法的最大執行時間。
O(n)：演算法執行的次數。（以次數來衡量時間複雜度較客觀）
常見的時間複雜度
O(1)
O(n)
O(n2)
O(n3)
O(2n)
O(log2n)
O(nlog2n)
當n = 4
O(1) = 1
O(n2) = 16
O(n3) = 64
O(2n) = 16
O(log2n) = 2
O(nlog2n) = 8
時間複雜度
O(n3) > O(n2) = O(2n) > O(nlog2n) > O(n) > O(log2n) > O(1)
雖然我看不懂...可是還是po一下...
> -------------------------------------------------------------------------- <
作者: flyhermit (Love Just Ain't EnoughＩ 看板: b92902xxx
標題: Re: big-O新解
時間: Sat Nov 1 23:45:13 2003
※ 引述《euphrate (*暴走狂愛.至死不渝~)》之銘言：
: → polaristin:推最後一句 XD 推140.112.249.208 11/01
: → starshine:完全不知道你在講什麼 XD 推 218.166.105.95 11/01
: → springgod:最後一個不等式是不是怪怪的~~@@ 推140.112.251.218 11/01
: → YCTai:資料結構的樣子...看不懂... 推 61.222.126.236 11/01
: → HudsonE:O(2^n)> O(n^2) 推218.167.195.248 11/01
: Big-O()應該是推算演算法執行的最壞時間 感覺有點像degree(x^3+100x^2+3) = 3
看黑皮上寫的
if and only if f(n) = O(g(n))
=> exists c,n0 > 0 s.t for all n>=n0, f(n0)<=cg(n)
> -------------------------------------------------------------------------- <
作者: Lwms (學生至上(智障)) 看板: b92902xxx
標題: Re: big-O新解
時間: Sat Nov 1 23:51:51 2003
※ 引述《flyhermit (Love Just Ain't EnoughＩ》之銘言：
: : → HudsonE:O(2^n)> O(n^2) 推218.167.195.248 11/01
: : Big-O()應該是推算演算法執行的最壞時間 感覺有點像degree(x^3+100x^2+3) = 3
: 看黑皮上寫的
: if and only if f(n) = O(g(n))
: => exists c,n0 > 0 s.t for all n>=n0, f(n0)<=cg(n)
Ο( g(n) ) = { f(n) : there exist positive constants c and n_0
such that 0 ≦ f(n) ≦ cg(n) for all n ≧ n_0 }
所以 Ο( g(n) ) 為一個集合
在不會造成模糊的情況之下 我們把 f(n) 屬於 Ο( g(n) )
記成 f(n) = Ο( g(n) )
所以 Ο( g(n) ) 跟 n 是多大沒有關係
> -------------------------------------------------------------------------- <
作者: Lwms (學生至上(智障)) 看板: b92902xxx
標題: Re: big-O新解
時間: Sun Nov 2 00:53:25 2003
※ 引述《lfst (計概國文計程普物)》之銘言：
: 說點正經的..big O
: Big-O函數通常稱為程式或演算法的時間複雜度（time complexity）
未必， Big-O 只是一個表示法 ( notation ) , 用來表示某些函數的集合
不僅僅可以用來度量 時間 也可以用來度量 空間
: 時間複雜度
: T(n)：程式執行時所需的時間。
: n：資料量的大小。
: 時間複雜度：輸入量夠大時，演算法的最大執行時間。
: O(n)：演算法執行的次數。（以次數來衡量時間複雜度較客觀）
用來度量時間的時候 在某些適當的假設之下
一般常見的是 RAM model random-access machine
裡面有個是假設機器提供了某些 instructions
而執行這些 instructions 都需要某個常數時間
計算某個程式，某種演算法會執行多久 耗費多少時間
我們可以計算他會執行多少個 instructions
把他通通加起來 通常記成 T(n) , n : input size
T(n) 是一個跟 n 有關的函數 , n 為自變數
(不過有時候對於 fix n 執行的 instructions 數也不一定固定)
對於空間亦然
不過我們有興趣的不是 T(n) , 而是 T(n) 的 order
或許 T(n) = n^3 + 1 和 T(n) = n^3 + 2 對你來講這是沒有分別的
或是 我們想知道隨著 n 增加的時候 T(n) 會增加的多快
大概跟哪個函數成正比 可以用那個函數來大概表示
這時候 Big-O notation 就發揮了他的作用
除了 Big-O ( Ο( g(n) ) ) 還有其他幾種
θ( g(n) ) , Ω( g(n) ), ω( g(n) ), ο( g(n) )
: 當n = 4
: O(1) = 1
: O(n2) = 16
: O(n3) = 64
: O(2n) = 16
: O(log2n) = 2
: O(nlog2n) = 8
不 ... 不能這樣寫
> -------------------------------------------------------------------------- <
作者: dh3014 (禁忌的實驗) 看板: b92902xxx
標題: Re: big-O新解
時間: Sun Nov 2 01:38:15 2003
※ 引述《flyhermit (Love Just Ain't EnoughＩ》之銘言：
: ※ 引述《euphrate (*暴走狂愛.至死不渝~)》之銘言：
: : → polaristin:推最後一句 XD 推140.112.249.208 11/01
: : → starshine:完全不知道你在講什麼 XD 推 218.166.105.95 11/01
: : → springgod:最後一個不等式是不是怪怪的~~@@ 推140.112.251.218 11/01
: : → YCTai:資料結構的樣子...看不懂... 推 61.222.126.236 11/01
: : → HudsonE:O(2^n)> O(n^2) 推218.167.195.248 11/01
: : Big-O()應該是推算演算法執行的最壞時間 感覺有點像degree(x^3+100x^2+3) = 3
: 看黑皮上寫的
: if and only if f(n) = O(g(n))
: => exists c,n0 > 0 s.t for all n>=n0, f(n0)<=cg(n)
^^^^^
wrong.
it is: f(n) <= cg(n)
for ex: we define T(n) = 2n^2 + 4n
let g(n) = n^2
we can find that c = 3, n0 = 2 is a sufficient solution for c ans n0
So we can write T(n) = O(g(n)) = O(n^2)
means T(n) is an element of set O(n^2).
In practice, we say this is an UPPER-BOUND GROWTH RATE for function T(n)
It is an important notation in complexity. Not only for algorithms.
But it plays an important role on algorithms.
That's see another example about the following code:
for (i = 0; i < n; ++i)
a[i] = i;
It's very easy to understand the code. Assume that n in a variable.
If you want to know the EFFECIENCY of the code, how could we analyze it?
One way (and the most used method) is by the big-O notation (or theta notation)
we assume
i = 0 needs c1 cycle on machine
i < n needs c2 cycle and ++i needs c3
a[i] = i needs c4 cycle.
Note that thus c1, c2, c3, c4 will not always be equal to each other.
(ex: c1 could be just one instruction MOV, but i < n needs more)
So let T(n) be the time-complexity function of the above code.
We can find that T(n) = c1 + (n + 1) (c2 + c3) + n * c4
= c1 + n (c2 + c3 + c4) + c2 + c3
How could we show that T(n) = O (n) ?
by looing for c = c2 + c4 + c4 + 1 and n0 = c1 + c2 + c3
thus it satisfied the definition for big-O, which implies T(n) = O(n)
Then we say, the above code is an algorithm with linear time complexity.