→ polomoss:對了，如果O(n^2)+theta(n)=O(n^2)? 02/10 23:11
→ polomoss:所以如果複雜度相同，bigO跟theta相加會等於theta 02/10 23:12
→ polomoss:Omega跟theta或bigO相加=Omega 02/10 23:12
→ polomoss:如果不同就挑大者~? 這樣的思維有錯嗎~? 02/10 23:12
推 taitin:n^loglogn =(logn)^logn 這兩個都不是 02/10 23:18
→ taitin:Ω(n)+Θ(n)=Θ(n),Ω(n)+Θ(n)=Θ(n),Ο(n)+Θ(n)=Ο(n) 02/10 23:21
→ taitin:原則上都是取最大上限者 02/10 23:22
→ taitin:噗..我怎麼打了兩次一樣，我是要打這個 Ω(n)+Ο(n)=Θ(n) 02/10 23:23
→ polomoss:對歐~我在搞笑~ 02/10 23:24
→ polomoss:不是~我推文問的問題是 02/10 23:25
→ polomoss:複雜度不同時還是一定為Θ嗎? 02/10 23:25
→ taitin:又打錯...這個才對Ο(n)+Θ(n)=Θ(n) 02/10 23:25
→ polomoss:還有Ω(n)+Θ(n)=Ω(n) 才對喔~ 02/10 23:26
→ 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)
→ taitin:Ω(n^2)+Θ(n)=Ω(n^2) Ω(n^2)+O(n)=Ω(n^2) 02/10 23:27
→ polomoss:Ω不用到n^2,同樣是n也是Ω 02/10 23:29
→ taitin:不是吧... 02/10 23:33
→ taitin:至少需要n^2+剛好需要n 等於至少需要n^2阿 02/10 23:35
→ taitin:要想成兩個方程式相加 02/10 23:35
→ taitin:所以這兩個Ω(n)+Θ(n)=Θ(n) Ω(n)+O(n)=Θ(n) 02/10 23:36
→ taitin:把+想做聯集，等號右邊的結果都要符合等號左邊的限制 02/10 23:37
→ taitin:Ο(n^2)+Θ(n)=O(n^2) 02/10 23:38
→ polomoss:不是耶，我手邊的書是Ω 02/10 23:43
推 EntHeEnd:Ω(n)+O(n)=Ω(n)吧...@@ ? 02/10 23:43
→ polomoss:當初也覺得很奇怪，後來想想，相加取大者 02/10 23:44
→ taitin:哪一本 02/10 23:44
→ polomoss:Ω(n)為下限值，後來想成可能為n^2,n^3..... 02/10 23:45
→ polomoss:但是O(n)至多n，所以兩個相加用Ω表示較佳 02/10 23:45
→ polomoss:就補習班筆記，這題考過兩三次了，95東華考過 02/10 23:46
推 EntHeEnd:請問n^loglogn的order 是在多項數和指數之間嗎... ? 02/10 23:47
→ polomoss:我覺得超過指數 02/10 23:47
→ EntHeEnd:好像有一些很難界定說他是什麼的... ? 02/10 23:48
→ polomoss:ㄟ~不對= = 02/10 23:48
→ EntHeEnd: 多項式 02/10 23:48
→ polomoss:應該是多項式和指數間比一般n^k大，但比2^n小 02/10 23:49
→ taitin:喔喔Ω看來是我搞錯了 02/10 23:50
推 EntHeEnd:所以說不算多項式時間 但是還不到指數的程度這樣 ? 02/10 23:50
→ polomoss:問一下 n^n n^logn (logn)^n 算哪個等級~? 02/10 23:51
→ taitin:看到一個例子 Ω(n^2)+Θ(n^3)=Ω(n^3) 02/10 23:51
→ polomoss:恩~ 02/10 23:52
→ EntHeEnd:我對(lglgn)! 比較好奇... 02/10 23:52
→ EntHeEnd:n^n 大於 n! 大於 2^n 這樣吧 02/10 23:53
→ polomoss:我的筆記 n^n 比n!大 02/10 23:53
→ polomoss:那n^logn 跟 (logn)^n 跟2^n 比呢? 02/10 23:53
→ EntHeEnd:n^(lgn)小於 2^n 吧 02/10 23:54
→ polomoss:沒事了~取完log就很明顯^^ 02/10 23:57
→ polomoss:謝謝討論~~休息去 02/10 23:57
推 EntHeEnd:(lglgn)! 是不是小於多項式時間阿 ? 02/10 23:57
→ EntHeEnd:(logn)^n 比 2^n 大吧 02/10 23:59
→ taitin:階乘在外面的話，就不是多項式時間內了 02/11 00:02
推 EntHeEnd:恩....... 02/11 00:06
推 EntHeEnd:感謝指正 發現我實在是誤會大了 orz 02/11 01:02
推 FRAXIS:n^log之類的叫做moderately exponential 02/11 09:31