作者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