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