1. PTT
  2. Prob_Solve

[问题] 挑数字问题

楼主: flere (人间失格)   2013-01-06 14:13:21
想问一下
给定N个数字 ( 10<=N<=10^6, 数字范围0~10^8)
假定数字皆不重复
现在要从这N个数字里面,挑出10个数字
再把这10个数字分成两堆 (一堆5个
使的两堆的数字相差要最小
请问这是NP-complete问题吗?? (不太会分QQ
有什么快速的做法吗??
谢谢: )
作者: AstralBrain   2013-01-06 15:59:00
不是NP-complete, 就算用最笨的穷举也只要O(n^10)
作者: singlovesong (~"~)   2013-01-06 16:38:00
穷举不是n^10
作者: eieio (好多目标)   2013-01-07 03:05:00
限制数字范围 0~10^8 且数字不重复从理论上来看就是 O(1) 了Big-O 必须 n 能往无限大走anyway, (N 取 10) * (10 取 5) 应该是对的，时间 O(N^10)
继续阅读
[问题] 请教这份大数乘法复杂度EdisonX2个程序的cpu执行比? 3个字组 udp checksum为?stephenth[问题] Suffix Tree 原始论文问题rifizRe: [问题] 面试问到的问题...LeonRe: [问题] 面试问到的问题...LeonRe: [问题] 面试问到的问题...DJWSRe: [问题] 面试问到的问题...LeonRe: [问题] 面试问到的问题...FavoniaRe: [问题] 面试问到的问题...LeonRe: [问题] 面试问到的问题...Favonia

Links booklink

Contact Us: admin [ a t ] ucptt.com