作者flere (人間失格)
站內Prob_Solve
標題[問題] 挑數字問題
時間Sun Jan 6 14:13:21 2013
想問一下
給定N個數字 ( 10<=N<=10^6, 數字範圍0~10^8)
假定數字皆不重複
現在要從這N個數字裡面,挑出10個數字
再把這10個數字分成兩堆 (一堆5個
使的兩堆的數字相差要最小
請問這是NP-complete問題嗎?? (不太會分QQ
有什麼快速的做法嗎??
謝謝: )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.203.24
1F：推 AstralBrain:不是NP-complete, 就算用最笨的窮舉也只要O(n^10) 01/06 15:59
2F：推 singlovesong:窮舉不是n^10 01/06 16:38
窮舉我想應該是(N取10的組合數) * (分兩堆的時間)
所以這應該是P問題
但是時間複雜度非常的大
這樣理解是對的吧??
※ 編輯: flere 來自: 123.195.203.24 (01/06 17:10)
3F：推 eieio:限制數字範圍 0~10^8 且數字不重複從理論上來看就是 O(1) 了 01/07 03:05
4F：→ eieio:Big-O 必須 n 能往無限大走 01/07 03:07
5F：推 eieio:anyway, (N 取 10) * (10 取 5) 應該是對的，時間 O(N^10) 01/07 03:11