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

Re: [問題] 0/1背包問題的時間複雜度

看板Prob_Solve (計算數學 Problem Solving)作者stimim (qqaa)時間13年前 (2011/10/27 09:54)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串4/4 (看更多)

: ┌────────────────────────────────────── : │ 實際上，這個問題最大的癥結是： : │ 明明輸入的是變數W，但是為什麼不能和以前一樣輸入n就用n估算，輸入a就用a估算 : │ W好好的沒事還要變成2^logW : │ 才能下去算複雜度... : └────────────────────────────────────── http://en.wikipedia.org/wiki/Pseudo-polynomial_time 在這頁有提到質數檢查的問題，我覺得就是一個好例子：考慮一個數 N ，請問他是不是質數？我們可以給出一個簡單的演算法： for each integer i, 2 <= i <= sqrt(N) if N Mod i = 0 return false return true 這個演算法的複雜度是 O(N^0.5) 是多項式時間可是，對這個問題來說，我們關心的並不是 N 變成兩倍的話，運算量會多多少 (Ex: N ~= 10000 和 N ~= 20000) 我們所關心的是，從 N ~= 2^32 變成 N ~= 2^64 會差多少？我們所謂的 "不同大小的輸入" 指的應該是 N ~= 2^n 中的 n 而不是 N ，當 n 成長時，函數的執行時間會有什麼變化？是 O(2^(n/2)) 或是說加法，在一般的討論下，加法應該是 O(1) ，可是，如果討論加法本身，也就是說，算兩個 n bits 的數字的和要多久？如果今天 n' = 2n ，又要多久？那就不是 O(1) 了，而是 O(n) 。回到 0/1 kp ，大部分我們遇到的 W 都不大，而且變動的大多是 n ，如果，今天的題目是：給兩個數 n, w ，代表的是，有 n 個物品，重量 0<= W <= 2^w ... 的 0/1 KP 問題，那你應該可以想像， w = 10 和 w = 100 所花的時間會差非常非常多。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.49.204