[問題] 挑數字問題

[flere (人間失格)]

想問一下

給定N個數字 ( 10<=N<=10^6, 數字範圍0~10^8)

假定數字皆不重複



現在要從這N個數字裡面,挑出10個數字

再把這10個數字分成兩堆 (一堆5個

使的兩堆的數字相差要最小



請問這是NP-complete問題嗎?? (不太會分QQ

有什麼快速的做法嗎??


謝謝: )

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.203.24
推 AstralBrain:不是NP-complete, 就算用最笨的窮舉也只要O(n^10)
推 singlovesong:窮舉不是n^10
窮舉我想應該是(N取10的組合數) * (分兩堆的時間)

所以這應該是P問題

但是時間複雜度非常的大

這樣理解是對的吧??
※ 編輯: flere           來自: 123.195.203.24       (01/06 17:10)
推 eieio:限制數字範圍 0~10^8 且數字不重複從理論上來看就是 O(1) 了
→ eieio:Big-O 必須 n 能往無限大走
推 eieio:anyway, (N 取 10) * (10 取 5) 應該是對的，時間 O(N^10)