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

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

看板Prob_Solve (計算數學 Problem Solving)作者i78524 (Shulei)時間13年前 (2011/10/25 15:15)推噓0(0推 0噓 0→)

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

謝謝DJWS及各路高手的幫忙與迴響在這裡謝謝大家願意花時間看我這個無聊的小問題 :) 之前我有寄信去問補教老師 (補教老師真的很好心，肯願意理我...) 今天回信了，關於這部份我將老師的解釋轉錄給大家參考 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 這個是最confuse的地方. 複雜度是 a function of input size 我做一表給你對照 input input size ------------------------------------------- A[1..n] n (資料筆數) W logW(其bit數) 如果A是一個有n個元訴的Array, 其input size為n 但是如果你輸入到演算法的是一整數W, 其input size會以要用幾個bit來算因此若要將 O(nW)表示成a function of input size, 他就會變成exponential. 這部份你若不懂不用深究, 因為考試不會考這個複雜度就寫O(nW) , 但要記得, 0/1KP為NP complete. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 我現在的解讀為：如果input是A[1..n] 這一類的話，對電腦來說n確實就是最自然的輸入量 (可能在電腦機器底層count跑一下電腦就能理解n這個數值是什麼，不費功夫 ) (他真的就是n個東西、數字等...INPUT是n很合理) (所以時間複雜度的輸入量就可以很放心的用n去算) 但是如果輸入是一個"整數W"，電腦要先把它換成他能理解的2進位數logW 令 logW=m 0/1 背包的時間複雜度寫成 O(nW)=O(n2^logw)=O(n2^m) 雖然我們輸入的是整數W，但是對電腦而言 "真正" 他看到的 "輸入量" 是2^m... 所以O最後是變成成O(n2^m)，而不是表面上的O(nW) 都寫成O(n2^m)，他理所當然不是"多項是時間"，是exponential time 而且又被稱作偽多項式時間在CORMAN的演算法導論在第2章也有一段話和這個問題相關『對排序問題，最自然的測量量是是輸入項目的數目-例如用來排序的陣列大小n。對許多其他問題來說，例如將兩個整數相乘，輸入量的最佳測量量是將輸入值以二元符號來表示的位元總數。』所以對於輸入量是一個"整數"了話要換成二進位表示的位元數應該是沒有錯之後看了wiki: http://ppt.cc/F0m_ 和DJWS大的想法之後才有這樣的想法 (其實我打到這邊才發現我的想法應該和DJWS大是一樣的) (bubble sort 的那個例子很有趣，還將兩個數化成bit比較時考慮進去，好底層啊) (不過一般來說不需要這樣吧，都直接當作O(1)) ┌────────────────────────────────────── │ 實際上，這個問題最大的癥結是： │ 明明輸入的是變數W，但是為什麼不能和以前一樣輸入n就用n估算，輸入a就用a估算 │ W好好的沒事還要變成2^logW │ 才能下去算複雜度... └────────────────────────────────────── 以上是我的想法，也謝謝大家的幫忙謝謝！ (明明不會考...還花好幾天想這個，看來今年考試應該也會很坎坷..) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 163.21.235.246