折中演算法

Ⅰ 比較兩個演算法的不同

l=l+0/s的位置不一樣，第公式是o和s的值發生了變化。第二個公式，os的值還沒發生變化。

Ⅱ 數據結構 折中查找演算法/選擇排序 起泡排序演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜索演算法也不是一件簡單的事。第一個二分搜索演算法早在1946年就出現了，但是第一個完全正確的二分搜索演算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索演算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的，我們可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函數BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個演算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。
選擇排序
基本思想是：每次選出第i小的記錄，放在第i個位置（i的起點是0，按此說法，第0小的記錄實際上就是最小的，有點別扭，不管這么多了）。當i＝N－1時就排完了。

直接選擇排序
直選排序簡單的再現了選擇排序的基本思想，第一次尋找最小元素的代價是O(n)，如果不做某種特殊處理，每次都使用最簡單的尋找方法，自然的整個排序的時間復雜度就是O(n2)了。

冒泡法
為了在a[1]中得到最大值，我們將a[1]與它後面的元素a[2]，a[3]，...，a[10]進行比較。首先比較a[1]與a[2]，如果a[1]<a[2]，則將a[1]與a[2]交換，否則不交換。這樣在a[1]中得到的是a[1]與a[2]中的大數。然後將a[1]與a[3]比較，如果a[1]<a[3]，則將a[1]與a[3]交換，否則不交換。這樣在a[1]中得到的是a[1]，a[2]，a[3]中的最大值，...。如此繼續，最後a[1]與a[10]比較，如果a[1]<a[10]，則將a[1]與a[10]交換，否則不交換。這樣在a[1]中得到的數就是數組a的最大值（一共進行了9次比較）。

為了在a[2]中得到次大值，應將a[2]與它後面的元素a[3]，a[4]，...，a[10]進行比較。這樣經過8次比較，在a[2]是將得到次大值。

如此繼續，直到最後a[9]與a[10]比較，將大數放於a[9]，小數放於a[10]，全部排序到此結束。
從上面可以看出，對於10個數，需進行9趟比較，每一趟的比較次數是不一樣的。第一趟需比較9次，第二趟比較8次，...，最後一趟比較1次。

以上數組元素的排序，用二重循環實現，外循環變數設為i，內循環變數設為j。外循環重復9次，內循環依次重復9，8，...，1次。每次進行比較的兩個元素，第一個元素與外循環i有關的，用a[i]標識，第二個元素是與內循環j有關的，用a[j]標識，i的值依次為1,2,...,9，對於每一個i, j的值依次為i+1,i+2,...。

Ⅲ 進程調度演算法

演算法原理： 就是誰先來誰就先執行

演算法優點 ：易於理解且實現簡單，只需要一個隊列，公平
演算法缺點 ：有利於長進程，不利於短進程，有利於CPU 繁忙的進程，不利於I/O 繁忙的進程

演算法原理： 對預計執行時間短的進程優先執行。
演算法優點 ：相比FCFS 演算法，該演算法可改善平均周轉時間和平均帶權周轉時間，縮短進程的等待時間，提高系統的吞吐量。
演算法缺點： 對長進程不利，可能長時間得不到執行產生飢餓，不能判斷執行的優先順序。

演算法原理： 同時考慮每個作業的等待時間長短和估計需要的執行時間長短，從中選出響應比最高的作業投入執行。響應比R定義： R =(W+T)/T = 1+W/T
T為該作業估計需要的執行時間，W為作業在後備狀態隊列中的等待時間。執行之前系統計算每個作業的響應比，選擇其中R最大者執行。這種演算法是介於前面兩種之間的一種折中演算法。
演算法優點： 長作業也有機會投入運行，避免了飢餓。
演算法缺點： 每次調度前要計算響應比，增加系統開銷。

演算法原理： 設置一個時間片，每個進程輪流使用時間片，若一個時間片內進程還沒結束，也會被其他的進程搶占時間片而退出執行，進入等待隊列。
演算法優點： 簡單易行、平均響應時間短。
演算法缺點： 不利於處理緊急作業。時間片的大小的設置對系統性能的影響很大，因此時間片的大小應選擇恰當

演算法原理： 根據優先順序的來判斷執行哪個進程。可以分為靜態優先順序和動態優先順序，即優先順序可以根據情況改變。比如如果一個進程等了很久，我們就可以把他的優先順序適當的提高。

演算法優點 ：可以優先處理緊急事件，適用於實時操作系統。

演算法缺點 ：可能導致那些優先順序低的進程飢餓。

UNIX操作系統採取的便是這種調度演算法。
演算法原理 ：

實現先說明執行隊列優先順序Q1>Q2>Q3.......>Qn，分配的時間片Qn>Qn-1>...Q1.

進程在進入待調度的隊列等待時，首先進入優先順序最高的隊列Q1等待。若在Q1隊列裡面還沒執行完，則下放到Q2裡面，等Q1裡面的進程都執行完了之後再執行Q2。以此類推。
若在低優先順序的隊列中的進程在運行時，又有新到達的作業，那麼在運行完這個時間片後，CPU馬上分配給新到達的作業（搶占式）。
在多級反饋隊列調度演算法中，規定第一個隊列的時間片略大於多數人機交互所需之處理時間時，能夠較好的滿足各種類型用戶的需要。