Re: [理工] [資結]-交大98-資訊聯招-DS&algo核對

看板Grad-ProbAsk作者 (小澤)時間16年前 (2010/02/10 23:09), 編輯推噓8(8推 0噓 46→)
留言54則, 4人參與, 最新討論串5/9 (看更多)
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
→
02/10 23:11, , 1F
對了，如果O(n^2)+theta(n)=O(n^2)?
02/10 23:11, 1F
→
02/10 23:12, , 2F
所以如果複雜度相同，bigO跟theta相加會等於theta
02/10 23:12, 2F
→
02/10 23:12, , 3F
Omega跟theta或bigO相加=Omega
02/10 23:12, 3F
→
02/10 23:12, , 4F
如果不同就挑大者~? 這樣的思維有錯嗎~?
02/10 23:12, 4F
推
02/10 23:18, , 5F
n^loglogn =(logn)^logn 這兩個都不是
02/10 23:18, 5F
→
02/10 23:21, , 6F
Ω(n)+Θ(n)=Θ(n),Ω(n)+Θ(n)=Θ(n),Ο(n)+Θ(n)=Ο(n)
02/10 23:21, 6F
→
02/10 23:22, , 7F
原則上都是取最大上限者
02/10 23:22, 7F
→
02/10 23:23, , 8F
噗..我怎麼打了兩次一樣，我是要打這個 Ω(n)+Ο(n)=Θ(n)
02/10 23:23, 8F
→
02/10 23:24, , 9F
對歐~我在搞笑~
02/10 23:24, 9F
→
02/10 23:25, , 10F
不是~我推文問的問題是
02/10 23:25, 10F
→
02/10 23:25, , 11F
複雜度不同時還是一定為Θ嗎?
02/10 23:25, 11F
→
02/10 23:25, , 12F
又打錯...這個才對Ο(n)+Θ(n)=Θ(n)
02/10 23:25, 12F
→
02/10 23:26, , 13F
還有Ω(n)+Θ(n)=Ω(n) 才對喔~
02/10 23:26, 13F
→
02/10 23:26, , 14F
只要跟Ω扯上關係都是 = Ω
02/10 23:26, 14F
一般來說 Ο(n)+Θ(n)=Θ(n) , Ω(n)+Θ(n)=Ω(n) , Ω(n)+O(n)=Ω(n) 我的問題是Ο(n^2)+Θ(n)= ? ※ 編輯: polomoss 來自: 114.43.131.96 (02/10 23:29)
→
02/10 23:27, , 15F
Ω(n^2)+Θ(n)=Ω(n^2) Ω(n^2)+O(n)=Ω(n^2)
02/10 23:27, 15F
→
02/10 23:29, , 16F
Ω不用到n^2,同樣是n也是Ω
02/10 23:29, 16F
→
02/10 23:33, , 17F
不是吧...
02/10 23:33, 17F
→
02/10 23:35, , 18F
至少需要n^2+剛好需要n 等於至少需要n^2阿
02/10 23:35, 18F
→
02/10 23:35, , 19F
要想成兩個方程式相加
02/10 23:35, 19F
→
02/10 23:36, , 20F
所以這兩個Ω(n)+Θ(n)=Θ(n) Ω(n)+O(n)=Θ(n)
02/10 23:36, 20F
→
02/10 23:37, , 21F
把+想做聯集，等號右邊的結果都要符合等號左邊的限制
02/10 23:37, 21F
→
02/10 23:38, , 22F
Ο(n^2)+Θ(n)=O(n^2)
02/10 23:38, 22F
→
02/10 23:43, , 23F
不是耶，我手邊的書是Ω
02/10 23:43, 23F
推
02/10 23:43, , 24F
Ω(n)+O(n)=Ω(n)吧...@@ ?
02/10 23:43, 24F
→
02/10 23:44, , 25F
當初也覺得很奇怪，後來想想，相加取大者
02/10 23:44, 25F
→
02/10 23:44, , 26F
哪一本
02/10 23:44, 26F
→
02/10 23:45, , 27F
Ω(n)為下限值，後來想成可能為n^2,n^3.....
02/10 23:45, 27F
→
02/10 23:45, , 28F
但是O(n)至多n，所以兩個相加用Ω表示較佳
02/10 23:45, 28F
→
02/10 23:46, , 29F
就補習班筆記，這題考過兩三次了，95東華考過
02/10 23:46, 29F
推
02/10 23:47, , 30F
請問n^loglogn的order 是在多項數和指數之間嗎... ?
02/10 23:47, 30F
→
02/10 23:47, , 31F
我覺得超過指數
02/10 23:47, 31F
→
02/10 23:48, , 32F
好像有一些很難界定說他是什麼的... ?
02/10 23:48, 32F
→
02/10 23:48, , 33F
ㄟ~不對= =
02/10 23:48, 33F
→
02/10 23:48, , 34F
多項式
02/10 23:48, 34F
→
02/10 23:49, , 35F
應該是多項式和指數間比一般n^k大，但比2^n小
02/10 23:49, 35F
→
02/10 23:50, , 36F
喔喔Ω看來是我搞錯了
02/10 23:50, 36F
推
02/10 23:50, , 37F
所以說不算多項式時間 但是還不到指數的程度這樣 ?
02/10 23:50, 37F
→
02/10 23:51, , 38F
問一下 n^n n^logn (logn)^n 算哪個等級~?
02/10 23:51, 38F
→
02/10 23:51, , 39F
看到一個例子 Ω(n^2)+Θ(n^3)=Ω(n^3)
02/10 23:51, 39F
→
02/10 23:52, , 40F
恩~
02/10 23:52, 40F
→
02/10 23:52, , 41F
我對(lglgn)! 比較好奇...
02/10 23:52, 41F
→
02/10 23:53, , 42F
n^n 大於 n! 大於 2^n 這樣吧
02/10 23:53, 42F
→
02/10 23:53, , 43F
我的筆記 n^n 比n!大
02/10 23:53, 43F
→
02/10 23:53, , 44F
那n^logn 跟 (logn)^n 跟2^n 比呢?
02/10 23:53, 44F
→
02/10 23:54, , 45F
n^(lgn)小於 2^n 吧
02/10 23:54, 45F
→
02/10 23:57, , 46F
沒事了~取完log就很明顯^^
02/10 23:57, 46F
→
02/10 23:57, , 47F
謝謝討論~~休息去
02/10 23:57, 47F
推
02/10 23:57, , 48F
(lglgn)! 是不是小於多項式時間阿 ?
02/10 23:57, 48F
→
02/10 23:59, , 49F
(logn)^n 比 2^n 大吧
02/10 23:59, 49F
→
02/11 00:02, , 50F
階乘在外面的話，就不是多項式時間內了
02/11 00:02, 50F
推
02/11 00:06, , 51F
恩.......
02/11 00:06, 51F
推
02/11 01:02, , 52F
感謝指正 發現我實在是誤會大了 orz
02/11 01:02, 52F
推
02/11 09:31, , 53F
n^log之類的叫做moderately exponential
02/11 09:31, 53F
→
02/11 09:32, , 54F
02/11 09:32, 54F
‣ 更多 polomoss 的文章
文章代碼(AID): #1BSimTTJ (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 5 之 9 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共9篇)
‣ 更多 polomoss 的文章
文章代碼(AID): #1BSimTTJ (Grad-ProbAsk)