→ Gabino: non-deterministic 01/26 19:14
推 Astar5566: 先google什麼是非確定性演算法吧 01/26 19:21
→ k2shouai: 看p199下面...... 01/26 19:25
推 yorunohoshi: non-deterministic algorithm可以想像成是個囧囧的 01/26 19:30
→ yorunohoshi: 演算法，只要滿足:"Yes instanse"拿去跑至少有一次 01/26 19:30
→ yorunohoshi: 有辦法輸出Yes，所有"No instance"必須輸出No，則這 01/26 19:30
→ yorunohoshi: 個演算法就是個正確的non-deterministic algorithm 01/26 19:30
推 yorunohoshi: 假設S={1,3,5,7} 要問有沒有M=9，你就給他多跑幾次 01/26 19:35
→ yorunohoshi: 可能第10次就猜對了 前面9次都是no也沒差 01/26 19:35
→ yorunohoshi: 但是如果是要問有沒有M=10 所有回答都會是no 01/26 19:36
→ hihihi45: 感謝 我有看到但覺得他很莫名 所以只要有一次ok我就 01/26 19:37
→ hihihi45: 能說他O(n)? 01/26 19:37
推 yorunohoshi: 恩恩 所以才囧囧的 01/26 19:39
→ hihihi45: 感謝 真的好囧的演算法... 01/26 19:40
→ k2shouai: 是指驗證輸入只要O(n)的時間才對吧 01/26 20:11
→ joeboy: Yes instance 輸出 yes ，No instance輸出沒有說是No吧？ 01/26 20:12