【 在 curry.bbs@cis.nctu.edu.tw ( 紅涵連理) 的大作中提到: 】
: ==> 在 daren.bbs@bbs.cs.nccu.edu.tw (藍藍的香蕉皮) 的文章中提到:
: > ※ 引述《mue.bbs@bbs.cs.tku.edu.tw (閒人)》之銘言：
: > : 【 在 Ray.bbs@bbs.ncku.edu.tw (雅閒居士) 的大作中提到: 】
: > : 一個演算法..對資料數n筆所花的時間成本..而估計方法有Big-Oh和Omega和Theta..
: > : 或許這不屬於資料結構的東西~~算是演算法的..在評估演算法的好壞時的一些比較方式..
: > : 在資料結潔構中的一些應用..通常會用這些來說明哪種資料結構配合的演算法所得的時間
: > : 複雜度是如何~~等等..
: > for example:
: > for(int i=0;i<n;i++){
: > .....
: > ...
: > }
: > this is O(n)
: > 也就是說這個Time complexity是隨著n的大小改變的
: > 若for(int i=0;i<n*n;i++)....
: > 則O(n^2)..........就是這樣
: 對阿 ! 大概就是這樣子了
: 不過我覺得很疑惑ㄌㄟ
: 這一種算法真的能夠大概比較出來嗎 ?
: for(i=1;i<n;i++)
: for(j=1;j<n;i++){
: a=+i;
: cout << a;
: }
: for(i=1;i<n;i++)
: for(j=1;j<n;j++){
: a=i*j+a;
: cout << a;
: }
: 這兩種都是O(N^2) , 但是 a+=i; 可是比 a=i*j+a; 簡單的多了
: 如果換成機械碼的話 , 可能為差到兩倍的長度
: 哪如果差的更多的呢 ?
: 這樣能單單只利用 Big-0 比較出來嗎 ?
: 有沒有人為我解一下疑惑囉
: 不然真是想不通
: 要他幹嘛 !
: ^_^ 紅散雲天 藍普霞天
嗯..其實這個也只是估計罷了..而且是在估計做同一件事的兩個演算法..
如排序or搜尋~~甚至是最短路徑的演算法等等..然後也是在n夠大的時候做比較..
有的時候..的確不準確..但若一個演算法..是O(n^3)而另一演算法是O(2^n)就很明顯了
...況且在求出來的big-O是一樣時~~也只說是相近~~而不能說是一樣..畢竟我們只是
做估計..如10*2^n+n與1000*2^n+2n的big-O都是2^n，我們所決定的是....
當2^n*C(乘上一常數)使得這個函式在n夠大的情況下會大於以上的兩式這樣....
也就是在n夠大時其餘的項式就顯得不重要了..我想你這二個程式做的應該不是同件
事..但即使是做同件事..而big-O相同時也不能說兩件事都一樣好~~只是相近罷了..
而我們要用Big-O的原因是~~由於"確實"的較難去估計..所以求個大概..這樣..
--
※ 來源:‧TKU CS BBS bbs.cs.tku.edu.tw‧[FROM: h234.s110.ts30.]