Re: [問題] 找出最小的10個值

[kingofsdtw (不能閒下來!!)]

※ 引述《harristime (瀚宇)》之銘言：
: 開發平台(Platform): Linux
: 問題(Question): 一個執行500次的while loop,
:                      每跑一次會得到一個值a,
:                      如何在這500個"a"內找出最小的10個值呢?
:                      謝謝

a[100]={......}  100個元素

取出前10個到B[10]  (a[0]~a[9]  ->b[10] )

Case1: b[10]不排序

      if a[10] < b[0] 那b[0]被取代下來，但卻不保證原來b[0]比b[1]~b[9]小

Case2: b[10]排序

      a[11]~a[99]共90元素都向b[]比較
      if a[11]>b[0]  a[11]<b[1]則只要比較2次
      (運氣差最多比較完全b[]  10個元素)

      最差整體速度a[N] b[B]:
        複製進b[B]速度+Bubllesort        +  比較次數+   複製+bubblesort速度
             B         +   (B-1+1)*(B-1)/2+  (N-B)*B +   (N-B)+0
             B         +   (B-1+1)*(B-1)/2+  (N-B)   +   (N-5)+(N-B)*B

case:
a[N]={9,8,7,6,5,4,3,2,1,15,14,13,12,11,10}
=      10+             (9+1)*9/2+ (N-10)*10+   ( N-10)+N-10

a[N]={16,15,14,13,12,11,10,9,8,7,6,5,4,3,2}
=      10+             (9+1)*9/2+  (N-10)  +   (N-10)*(9)+N-10


http://codepad.org/7RaaOm7O


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.117.8.99
→ kingofsdtw:ps.當 B=1 相當於找最小值    O(N)
→ kingofsdtw: http://codepad.org/kfcsUeG8  不需要開始sort(b)
→ kingofsdtw:  B+ (N-B)*(B)+(N-B)*B+(N-B)
※ 編輯: kingofsdtw      來自: 122.117.8.99         (05/11 02:56)
→ blackwindy:set or priority_queue, C++ STL containers
→ blackwindy:複雜度要比較一下