作者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一下...
--
人走了 ， 心也空了
看著你留下的每一份記憶
我卻感覺不到那曾經每一夜的愛情
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.246.171
1F：→ polaristin:推最後一句 XD 推140.112.249.208 11/01
2F：→ starshine:完全不知道你在講什麼 XD 推 218.166.105.95 11/01
3F：→ springgod:最後一個不等式是不是怪怪的~~@@ 推140.112.251.218 11/01
4F：→ YCTai:資料結構的樣子...看不懂... 推 61.222.126.236 11/01
5F：→ HudsonE:O(2^n)> O(n^2) 推218.167.195.248 11/01
6F：→ lfst:當n=4帶入的數值排大小 應該沒錯 推140.112.246.171 11/01
7F：→ lfst:聽說...資料結構會用到 推140.112.246.171 11/01
8F：→ timrau:通常不是要考慮n趨近無限大？ 推 210.85.10.126 11/01
9F：→ timrau:所以O(2^n)>O(n^3)>O(n^2)>..... 推 210.85.10.126 11/01
10F：→ lfst:n要當何數 看情況吧 推140.112.246.171 11/01
11F：→ ZenKou:這是演算法...賞個m 推 140.112.240.16 11/01
12F：→ leeaa:推8,9樓的強者:) 推 61.224.2.223 11/01
13F：→ ZenKou:樓上的強者....解釋一下吧 推 140.112.240.16 11/01
14F：→ lfst:樓上的都是強者..XD (lfst例外 ) 推140.112.246.171 11/02