㈠ 5. 設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti，1<=i<=n。應如何安排n個顧客的服務次序才能
上面的 思路不錯
最優服務次序問題
一、問題描述：
設有n 個顧客同時等待一項服務。顧客i需要的服務時間為ti, 1≦i ≦n 。共有s處可以提供此服務。應如何安排n個顧客的服務次序才能使平均等待時間達到最小?平均等待時間是n 個顧客等待服務時間的總和除以n。
二、貪心選擇策略
假設原問題為T，而我們已經知道了某個最優服務系列，即最優解為A={t(1)，t(2)，…．t(n)}(其中t(i)為第i個用戶需要的服務時間)，則每個用戶等待時間為：
T(1)=t(1)；T(2)=t(1)+t(2)；...T(n)：t(1)+t(2)+t(3)+……t(n)；
那麼總等待時問，即最優值為：
TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)*t(i)+…2*t(n-1)+t(n)；
由於平均等待時間是n個顧客等待時間的總和除以n，故本題實際上就是求使顧客等待時間的總和最小的服務次序。
本問題採用貪心演算法求解，貪心策略如下：對服務時間最短的顧客先服務的貪心選擇策略。首先對需要服務時間最短的顧客進行服務，即做完第一次選擇後，原問題T變成了需對n-1個顧客服務的新問題T』。新問題和原問題相同，只是問題規模由n減小為n-1。基於此種選擇策略，對新問題T』，選擇n-1顧客中選擇服務時間最短的先進行服務，如此進行下去，直至所有服務都完成為止 。
三、問題的貪心選擇性質
先來證明該問題具有貪心選擇性質，即最優服務A中t(1)滿足條件：t(1)<=t(i)(2<i<n)。
用反證法來證明：假設t(1)不是最小的，不妨設t(1)>t(i)(i>1)。
設另一服務序列B=（t(i)，t(2)，…，t(1)…，t(n)）
那麼TA-TB=n*[t(1)-t(i)]+(n+1-i)[t(i)-t(1)]=(1-i)*[t(i)-t(1)]>0
即TA>TB，這與A是最優服務相矛盾。
故最優服務次序問題滿足貪心選擇性質。
四、問題的最優子結構性質
在進行了貪心選擇後，原問題T就變成了如何安排剩餘的n-1個顧客的服務次序的問題T』，是原問題的子問題。
若A是原問題T的最優解，則A』={t(2)，…t(i)…t(n))是服務次序問題子問題T』的最優解。
證明：假設A』不是子問題T』的最優解，其子問題的最優解為B』，則有TB』<TA』，而根據TA的定義知，TA』十t(1)=TA。因此TB』+t(1)<TA』+t(1)=TA，即存在一個比最優值TA更短的總等待時間，而這與TA為問題T的最優值相矛盾。因此，A』是子問題T』的最優值。
從以上貪心選擇及最優子結構性質的證明，可知對最優服務次序問題用貪心演算法可求得最優解。
根據以上證明，最優服務次序問題可以用最短服務時間優先的貪心選擇可以達到最優解。故只需對所有服務先按服務時間從小到大進行排序，然後按照排序結果依次進行服務即可。平均等待時間即為TA/n。
五、演算法實現
由多處最優服務次序問題具有貪心選擇性質和最優子結構性質，容易證明演算法greedy的正確性。本演算法採用最短服務時間優先的貪心策略。首先將每個顧客所需要的服務時間從小到大排序。然後申請2個數組：st[]是服務數組，st[j]為第j個隊列上的某一個顧客的等待時間；su[]是求和數組，su[j]的值為第j個隊列上所有顧客的等待時間；
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;//循環分配顧客到每一個服務點上
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
六、演算法測試結果
七、演算法復雜性分析
程序主要是花費在對各顧客所需服務時間的排序和貪心演算法，即計算平均服務時間上面。其中，貪心演算法部分只有一重循環影響時間復雜度，其時間復雜度為O(n)：而排序演算法的時間復雜度為O(nlogn)。因此，綜合來看演算法的時間復雜度為O(nlogn)。
八、參考文獻
[1] 王曉東.計算機演算法設計與分析(第3版)[M]．北京：電子工業出版社,2007．
[2] 陳媛.《演算法與數據結構》[M],清華大學出版社, 第1版,2005.4.
[3] 王曉東.演算法設計與實驗題解 [M]．北京：電子工業出版社,2008．
附錄（程序代碼）
#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
using std::vector;
double greedy(vector<int>x,int s)
{
vector<int>st(s+1,0);
vector<int>su(s+1,0);
int n=x.size();
sort(x.begin(),x.end());
int i=0,j=0;
while(i<n){
st[j]+=x[i];
su[j]+=st[j];
i++;
j++;
if(j==s)j=0;
}
double t=0;
for(i=0;i<s;i++) t+=su[i];
t/=n;
return t;
}
void main()
{int n;//等待服務的顧客人數
int s;//服務點的個數
int i;
int a;
int t;//平均服務時間
vector<int>x;
cout<<"please input the num of the customer:"<<endl;
cin>>n;
cout<<"please input the num of the server:"<<endl;
cin>>s;
cout<<"please input the need service time of each customer:"<<endl;
for(i=1;i<=n;i++){
cout<<"No."<<i<<endl;
cin>>a;
x.push_back(a);
}
t=greedy(x, s);
cout<<"the least average waiting time is:"<<t<<endl;
}
㈡ 快速排序演算法在平均情況下的時間復雜度為 求詳解
時間復雜度為O(nlogn) n為元素個數
1. 快速排序的三個步驟：
1.1. 找到序列中用於劃分序列的元素
1.2. 用元素劃分序列
1.3. 對劃分後的兩個序列重復1,2兩個步驟指導序列無法再劃分
所以對於n個元素其排序時間為
T(n) = 2*T(n/2) + n （表示將長度為n的序列劃分為兩個子序列，每個子序列需要T(n/2)
的時間，而劃分序列需要n的時間）
而 T(1) = 1 （表示長度為1的序列無法劃分子序列，只需要1的時間即可）
T(n) = 2^logn + logn * n （n被不斷二分最終只能二分logn次（最優的情況,每次選取
的元素都均分序列））
= n + nlogn
因此T(n) = O(nlogn)
以上是最優情況的推導，因此快速排序在最優情況下其排序時間為O(nlogn),通常平均情況
我們也認為是此值。
在最壞情況下其會退化為冒泡排序，T(n) = T(n - 1) + n (每次選取的元素只能將序列劃分為
一段，即自身是 最小元素或最大元素)
因此T(n) = n * (n-1) / 2 相當於O(n^2)