作者polomoss (小泽)
看板Grad-ProbAsk
标题Re: [理工] [资结]-交大98-资讯联招-DS&algo核对
时间Wed Feb 10 23:09:14 2010
4(2)
直接PO在这讨论
我选了 nlogn,sqrt(logn),log^2n,log(n!),2^sqrt(2logn)
sqrt(2)^logn , 4^logn , n^1/logn
更正8个!
--
◤ ◥ 答
◤ ◥ 拉
◤ ◥ 米
◤ ◥ 哆
Σ ◆ ◆ 蚊
Σ ◆ ◆ 肥
Σ ◆ ◆ 开
Σ ◆ ◆ 啦
︵ 吸
︵ 儿
︵ 喇
︵ 太
◣++++++◢ ◣++++++◢ ◣++++++◢ 鸡
◣++++++◢ 裸
◥▇▆@ ≡ @▆▇◤ Ψ ≡ Ψ ▄ ≡ ▄ 罗
▄▄▄ ≡ ▄▄▄
▅ ▅ ▄/
▅ \
▄ ▅ ＡΓＶＩＳＳ
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.43.131.96
1F：→ polomoss:对了，如果O(n^2)+theta(n)=O(n^2)? 02/10 23:11
2F：→ polomoss:所以如果复杂度相同，bigO跟theta相加会等於theta 02/10 23:12
3F：→ polomoss:Omega跟theta或bigO相加=Omega 02/10 23:12
4F：→ polomoss:如果不同就挑大者~? 这样的思维有错吗~? 02/10 23:12
5F：推 taitin:n^loglogn =(logn)^logn 这两个都不是 02/10 23:18
6F：→ taitin:Ω(n)+Θ(n)=Θ(n),Ω(n)+Θ(n)=Θ(n),Ο(n)+Θ(n)=Ο(n) 02/10 23:21
7F：→ taitin:原则上都是取最大上限者 02/10 23:22
8F：→ taitin:噗..我怎麽打了两次一样，我是要打这个 Ω(n)+Ο(n)=Θ(n) 02/10 23:23
9F：→ polomoss:对欧~我在搞笑~ 02/10 23:24
10F：→ polomoss:不是~我推文问的问题是 02/10 23:25
11F：→ polomoss:复杂度不同时还是一定为Θ吗? 02/10 23:25
12F：→ taitin:又打错...这个才对Ο(n)+Θ(n)=Θ(n) 02/10 23:25
13F：→ polomoss:还有Ω(n)+Θ(n)=Ω(n) 才对喔~ 02/10 23:26
14F：→ polomoss:只要跟Ω扯上关系都是 = Ω 02/10 23:26
一般来说
Ο(n)+Θ(n)=Θ(n) , Ω(n)+Θ(n)=Ω(n) , Ω(n)+O(n)=Ω(n)
我的问题是Ο(n^2)+Θ(n)= ?
※ 编辑: polomoss 来自: 114.43.131.96 (02/10 23:29)
15F：→ taitin:Ω(n^2)+Θ(n)=Ω(n^2) Ω(n^2)+O(n)=Ω(n^2) 02/10 23:27
16F：→ polomoss:Ω不用到n^2,同样是n也是Ω 02/10 23:29
17F：→ taitin:不是吧... 02/10 23:33
18F：→ taitin:至少需要n^2+刚好需要n 等於至少需要n^2阿 02/10 23:35
19F：→ taitin:要想成两个方程式相加 02/10 23:35
20F：→ taitin:所以这两个Ω(n)+Θ(n)=Θ(n) Ω(n)+O(n)=Θ(n) 02/10 23:36
21F：→ taitin:把+想做联集，等号右边的结果都要符合等号左边的限制 02/10 23:37
22F：→ taitin:Ο(n^2)+Θ(n)=O(n^2) 02/10 23:38
23F：→ polomoss:不是耶，我手边的书是Ω 02/10 23:43
24F：推 EntHeEnd:Ω(n)+O(n)=Ω(n)吧...@@ ? 02/10 23:43
25F：→ polomoss:当初也觉得很奇怪，後来想想，相加取大者 02/10 23:44
26F：→ taitin:哪一本 02/10 23:44
27F：→ polomoss:Ω(n)为下限值，後来想成可能为n^2,n^3..... 02/10 23:45
28F：→ polomoss:但是O(n)至多n，所以两个相加用Ω表示较佳 02/10 23:45
29F：→ polomoss:就补习班笔记，这题考过两三次了，95东华考过 02/10 23:46
30F：推 EntHeEnd:请问n^loglogn的order 是在多项数和指数之间吗... ? 02/10 23:47
31F：→ polomoss:我觉得超过指数 02/10 23:47
32F：→ EntHeEnd:好像有一些很难界定说他是什麽的... ? 02/10 23:48
33F：→ polomoss:ㄟ~不对= = 02/10 23:48
34F：→ EntHeEnd: 多项式 02/10 23:48
35F：→ polomoss:应该是多项式和指数间比一般n^k大，但比2^n小 02/10 23:49
36F：→ taitin:喔喔Ω看来是我搞错了 02/10 23:50
37F：推 EntHeEnd:所以说不算多项式时间 但是还不到指数的程度这样 ? 02/10 23:50
38F：→ polomoss:问一下 n^n n^logn (logn)^n 算哪个等级~? 02/10 23:51
39F：→ taitin:看到一个例子 Ω(n^2)+Θ(n^3)=Ω(n^3) 02/10 23:51
40F：→ polomoss:恩~ 02/10 23:52
41F：→ EntHeEnd:我对(lglgn)! 比较好奇... 02/10 23:52
42F：→ EntHeEnd:n^n 大於 n! 大於 2^n 这样吧 02/10 23:53
43F：→ polomoss:我的笔记 n^n 比n!大 02/10 23:53
44F：→ polomoss:那n^logn 跟 (logn)^n 跟2^n 比呢? 02/10 23:53
45F：→ EntHeEnd:n^(lgn)小於 2^n 吧 02/10 23:54
46F：→ polomoss:没事了~取完log就很明显^^ 02/10 23:57
47F：→ polomoss:谢谢讨论~~休息去 02/10 23:57
48F：推 EntHeEnd:(lglgn)! 是不是小於多项式时间阿 ? 02/10 23:57
49F：→ EntHeEnd:(logn)^n 比 2^n 大吧 02/10 23:59
50F：→ taitin:阶乘在外面的话，就不是多项式时间内了 02/11 00:02
51F：推 EntHeEnd:恩....... 02/11 00:06
52F：推 EntHeEnd:感谢指正 发现我实在是误会大了 orz 02/11 01:02
53F：推 FRAXIS:n^log之类的叫做moderately exponential 02/11 09:31