PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 時間複雜度疑問

看板Prob_Solve (計算數學 Problem Solving)作者 (...)時間13年前 (2011/09/28 15:27), 編輯推噓4(4推 0噓 9→)
留言13則, 4人參與, 最新討論串1/1
問題一： Polynomial time algorithm 是指 O(n^k) 的演算法， 其中 n 我想應該是指資料的數量多寡，不是指資料的數值大小吧？ 那麼為何 AKS primality test 的 n 是指數值大小呢？ ^^^^^^^^ 修正: 數值(二進位表示)的位數 問題二： 有一些 NP-complete 問題，例如 0/1 Knapsack Problem， 當輸入資料的數值大小範圍有限、又是整數時， 我們可以用 pseudo-polynomial time algorithm 解決問題。 那麼，同樣是 NP-complete 問題的 Hamiltonian path， 也會有 pseudo-polynomial time algorithm 嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.168.20.43
推
09/28 17:08, , 1F
1. 的 n 是指(二進位)位數, 不然傳統怎麼做都是 O(n)
09/28 17:08, 1F
推
09/28 17:12, , 2F
2. 的話, depends, 這也是 weakly/strongly NP-complete
09/28 17:12, 2F
→
09/28 17:13, , 3F
的分野
09/28 17:13, 3F
→
09/29 13:09, , 4F
我把問題一的敘述改好了~
09/29 13:09, 4F
→
09/29 13:10, , 5F
問題二，NP-Complete問題之間不是可以互相轉換嗎? 為何還會有
09/29 13:10, 5F
→
09/29 13:11, , 6F
weakly/strongly的差異呢?
09/29 13:11, 6F
※ 編輯: DJWS 來自: 118.168.20.43 (09/29 13:12)
→
09/29 14:32, , 7F
可是AKS我記得是lg ? 那就不是與長度成指數次方關係了？
09/29 14:32, 7F
推
10/01 11:50, , 8F
N 正確的說法應該是input size
10/01 11:50, 8F
推
10/02 15:33, , 9F
NPC 的性質不變, weakly/strongly 的差別在於如果 input 的
10/02 15:33, 9F
→
10/02 15:34, , 10F
範圍是 bounded, 原本的問題能不能變簡單, 我理解成問題難度
10/02 15:34, 10F
→
10/02 15:34, , 11F
的另一種維度
10/02 15:34, 11F
→
10/02 15:35, , 12F
畢竟 reduction 並沒有保證 input 的 range 會不會仍然保有
10/02 15:35, 12F
→
10/02 15:36, , 13F
bounded 的性質
10/02 15:36, 13F
‣ 更多 DJWS 的文章
文章代碼(AID): #1EWin_nt (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 DJWS 的文章
文章代碼(AID): #1EWin_nt (Prob_Solve)