作者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