Re: [理工] [DS]排序

[mqazz1 (無法顯示)]

※ 引述《jim055006 (jim)》之銘言：
: 問題如下:
: A server has n custoniers to serve. The time required to serve
: customer i is ti. which is known in advance. The waiting time
: of customer i is the total time that customer i has to wail
: until he is served, i.e., it is the sum of the service times of
: all the customers served before i. Our goal is to minimize the
: total waiting time
: T=Σ(waiting time for customer i). (i: 1 to n)
: Given an efficient algorithm for computing the optimal order in which
: to serve the customers. Remember to justify why your algorithm is
: correct. and to analyze its running time.
: 請問這樣的題目可以用quick sort解嗎?
: 還是要用其他的方式解...
: 有請高手們解答....
: 鋼溫!!!

題目已預先知道服務customer i需要的時間是ti

目標是要讓total waiting time最小

應該說這題主要是問OS的排程法

先用comparsion base sort將服務的時間由小排到大

接著使用SJF 讓CPU brust較小的先完成

複雜度是Omega(nlogn)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186
推 jim055006:這樣comparsion-and-swap sort是可以認我選一個來寫嗎?
→ jim055006:因為這題好像是OS的題目....我一開始看到有點愣住...
推 jim055006:還是說照M大你這樣寫就可以當答案了?
我想任何排序法都可以選吧

只是我記得這題我有看過洪逸解的

印象中是寫comparsion sort 因為感覺比較專業

可能再等等看其他高手的意見吧 因為我是憑印象來回答的= ="

這應該是資結跟OS合在一起的考卷吧


※ 編輯: mqazz1          來自: 140.118.110.186      (11/06 00:19)
推 jim055006:這題是95中正的資結跟演算法