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