[理工] 103 中央 資工 資演7

看板Grad-ProbAsk作者 (路過的slowpoke)時間7年前 (2017/01/26 19:08), 編輯推噓4(4推 0噓 12→)
留言16則, 6人參與, 最新討論串1/1
求各位大大幫助QQ http://i.imgur.com/cg1qhpn.jpg
我怎樣樣都想不通為什麼是O(n)... 可能出現的subset不是有2^n個嗎？ 這樣慢慢試不是很久？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.26.74.133 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485428898.A.3A5.html
→
01/26 19:14, , 1F
non-deterministic
01/26 19:14, 1F
推
01/26 19:21, , 2F
先google什麼是非確定性演算法吧
01/26 19:21, 2F
→
01/26 19:25, , 3F
看p199下面......
01/26 19:25, 3F
推
01/26 19:30, , 4F
non-deterministic algorithm可以想像成是個囧囧的
01/26 19:30, 4F
→
01/26 19:30, , 5F
演算法，只要滿足:"Yes instanse"拿去跑至少有一次
01/26 19:30, 5F
→
01/26 19:30, , 6F
有辦法輸出Yes，所有"No instance"必須輸出No，則這
01/26 19:30, 6F
→
01/26 19:30, , 7F
個演算法就是個正確的non-deterministic algorithm
01/26 19:30, 7F
推
01/26 19:35, , 8F
假設S={1,3,5,7} 要問有沒有M=9，你就給他多跑幾次
01/26 19:35, 8F
→
01/26 19:35, , 9F
可能第10次就猜對了 前面9次都是no也沒差
01/26 19:35, 9F
→
01/26 19:36, , 10F
但是如果是要問有沒有M=10 所有回答都會是no
01/26 19:36, 10F
→
01/26 19:37, , 11F
感謝 我有看到但覺得他很莫名 所以只要有一次ok我就
01/26 19:37, 11F
→
01/26 19:37, , 12F
能說他O(n)?
01/26 19:37, 12F
推
01/26 19:39, , 13F
恩恩 所以才囧囧的
01/26 19:39, 13F
→
01/26 19:40, , 14F
感謝 真的好囧的演算法...
01/26 19:40, 14F
→
01/26 20:11, , 15F
是指驗證輸入只要O(n)的時間才對吧
01/26 20:11, 15F
→
01/26 20:12, , 16F
Yes instance 輸出 yes ，No instance輸出沒有說是No吧？
01/26 20:12, 16F
‣ 更多 hihihi45 的文章
文章代碼(AID): #1OYTYYEb (Grad-ProbAsk)