不同演算法優劣

⑴ 簡述各種排序演算法的優缺點

一、冒泡排序
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與 a[2]的值，若a[1]大於a[2]則交換 兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比 較a[3]與a[4]，以此 類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對a[1]~a[n- 1]以相同方法 處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理 n-1 輪 後a[1]、a[2]、……a[n]就以升序排列了。
優點：穩定；
缺點：慢，每次只能移動相鄰兩個數據。

二、選擇排序
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數 據元素排完。
選擇排序是不穩定的排序方法。
n 個記錄的文件的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1 趟排序 在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1 個記錄R[1]交換，使R[1..1]和R[2..n]分別變 為記錄個數增加1 個的新有序區和記錄個數減少1 個的新無序區。
③第i 趟排序
第i 趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟 排序從當前無序區中選出關鍵字最 小的記錄 R[k]，將它與無序區的第1 個記錄R 交換，使R[1..i]和R 分別變為記錄個數增加1 個的新有序區和記錄個數減少 1 個的新無序區。
這樣，n 個記錄的文件的直接選擇排序可經過n-1 趟直接選擇排序得到有序結果。
優點：移動數據的次數已知（n-1 次）；
缺點：比較次數多。

三、插入排序
已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、 b[2]、……b[m]，需將二者合並成一個升序數列。 首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值， 若b[1]仍然大於a[2]，則繼續跳過，直 到b[1]小於a 數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來 a[x]的位置這就完成了b[1] 的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1 的數組a）
優點：穩定，快；
缺點：比較次數不一定，比較次數越少，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鏈表可以解決 這個問題。

四、縮小增量排序
由希爾在1959 年提出，又稱希爾排序(shell 排序)。
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n 不大時，插入 排序的效果很好。首先取一增 量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、 a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……="" 列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重復上述操="" 作，直到d="1。"
優點：快，數據移動少；=""
缺點：不穩定，d="" 的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。=""

五、快速排序=""
快速排序是冒泡排序的改進版，是目前已知的最快的排序方法。
="" 已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據a[x]="" 作為基準。比較a[x]與其它數據並="" 排序，使a[x]排在數據的第k="" 位，並且使a[1]~a[k-1]中的每一個數="" 據a[x]，然後采 用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n] 兩組數據進行快速排序。
優點：極快，數據移動少；
缺點：不穩定。

⑵ 比較演算法優缺點：

1.先來先服務先來先服務（FCFS, First Come First Serve）是最簡單的調度演算法，按先後順序進行調度。1. 定義按照作業提交或進程變為就緒狀態的先後次序，分派CPU；當前作業或進程佔用CPU，直到執行完或阻塞，才出讓CPU（非搶占方式）。在作業或進程喚醒後（如I/O完成），並不立即恢復執行，通常等到當前作業或進程出讓CPU。2.適用場景比較有利於長作業，而不利於短作業。有利於CPU繁忙的作業，而不利於I/O繁忙的作業。
2. 輪轉法輪轉法(Round Robin)是讓每個進程在就緒隊列中的等待時間與享受服務的時間成正比例。1. 定義將系統中所有的就緒進程按照FCFS原則，排成一個隊列。每次調度時將CPU分派給隊首進程，讓其執行一個時間片。時間片的長度從幾個ms到幾百ms。在一個時間片結束時，發生時鍾中斷。調度程序據此暫停當前進程的執行，將其送到就緒隊列的末尾，並通過上下文切換執行當前的隊首進程。進程可以未使用完一個時間片，就出讓CPU（如阻塞）。2. 時間片長度的確定時間片長度變化的影響過長－>退化為FCFS演算法，進程在一個時間片內都執行完，響應時間長。過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數增加，響應時間長。對響應時間的要求：T(響應時間)=N(進程數目)*q(時間片)就緒進程的數目：數目越多，時間片越小系統的處理能力：應當使用戶輸入通常在一個時間片內能處理完，否則使響應時間，平均周轉時間和平均帶權周轉時間延長。
3. 多級反饋隊列演算法多級反饋隊列演算法(Round Robin with Multiple Feedback)是輪轉演算法和優先順序演算法的綜合和發展。1. 定義設置多個就緒隊列，分別賦予不同的優先順序，如逐級降低，隊列1的優先順序最高。每個隊列執行時間片的長度也不同，規定優先順序越低則時間片越長，如逐級加倍。新進程進入內存後，先投入隊列1的末尾，按FCFS演算法調度；若按隊列1一個時間片未能執行完，則降低投入到隊列2的末尾，同樣按FCFS演算法調度；如此下去，降低到最後的隊列，則按「時間片輪轉」演算法調度直到完成。僅當較高優先順序的隊列為空，才調度較低優先順序的隊列中的進程執行。如果進程執行時有新進程進入較高優先順序的隊列，則搶先執行新進程，並把被搶先的進程投入原隊列的末尾。2.優點為提高系統吞吐量和縮短平均周轉時間而照顧短進程。為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程。不必估計進程的執行時間，動態調節3. 幾點說明I/O型進程：讓其進入最高優先順序隊列，以及時響應I/O交互。通常執行一個小時間片，要求可處理完一次I/O請求的數據，然後轉入到阻塞隊列。計算型進程：每次都執行完時間片，進入更低級隊列。最終採用最大時間片來執行，減少調度次數。I/O次數不多，而主要是CPU處理的進程。在I/O完成後，放回優先I/O請求時離開的隊列，以免每次都回到最高優先順序隊列後再逐次下降。為適應一個進程在不同時間段的運行特點，I/O完成時，提高優先順序；時間片用完時，降低優先順序。
4. 優先順序法優先順序演算法（Priority Scheling）是多級隊列演算法的改進，平衡各進程對響應時間的要求。適用於作業調度和進程調度，可分成搶先式和非搶先式。1. 靜態優先順序作業調度中的靜態優先順序大多按以下原則確定：由用戶自己根據作業的緊急程度輸入一個適當的優先順序。由系統或操作員根據作業類型指定優先順序。系統根據作業要求資源情況確定優先順序。進程的靜態優先順序的確定原則：按進程的類型給予不同的優先順序。將作業的情態優先順序作為它所屬進程的優先順序。2. 動態優先順序進程的動態優先順序一般根據以下原則確定：根據進程佔用有CPU時間的長短來決定。根據就緒進程等待CPU的時間長短來決定。
5．短作業優先法短作業優先（SJF, Shortest Job First）又稱為「短進程優先」SPN(Shortest Process Next)；這是對FCFS演算法的改進，其目標是減少平均周轉時間。1. 定義對預計執行時間短的作業（進程）優先分派處理機。通常後來的短作業不搶先正在執行的作業。2. SJF的特點(1) 優點：比FCFS改善平均周轉時間和平均帶權周轉時間，縮短作業的等待時間；提高系統的吞吐量；(2) 缺點：對長作業非常不利，可能長時間得不到執行；未能依據作業的緊迫程度來劃分執行的優先順序；難以准確估計作業（進程）的執行時間，從而影響調度性能。3. SJF的變型「最短剩餘時間優先」SRT(Shortest Remaining Time)（允許比當前進程剩餘時間更短的進程來搶占）「最高響應比優先」HRRN(Highest Response Ratio Next)（響應比R = (等待時間 + 要求執行時間) / 要求執行時間，是FCFS和SJF的折衷）6. 最高響應比優先法最高響應比優先法(HRN，Highest Response_ratio Next)是對FCFS方式和SJF方式的一種綜合平衡。FCFS方式只考慮每個作業的等待時間而未考慮執行時間的長短，而SJF方式只考慮執行時間而未考慮等待時間的長短。因此，這兩種調度演算法在某些極端情況下會帶來某些不便。HRN調度策略同時考慮每個作業的等待時間長短和估計需要的執行時間長短，從中選出響應比最高的作業投入執行。響應比R定義如下： R =(W+T)/T = 1+W/T其中T為該作業估計需要的執行時間，W為作業在後備狀態隊列中的等待時間。每當要進行作業調度時，系統計算每個作業的響應比，選擇其中R最大者投入執行。這樣，即使是長作業，隨著它等待時間的增加，W / T也就隨著增加，也就有機會獲得調度執行。這種演算法是介於FCFS和SJF之間的一種折中演算法。由於長作業也有機會投入運行，在同一時間內處理的作業數顯然要少於SJF法，從而採用HRN方式時其吞吐量將小於採用SJF 法時的吞吐量。另外，由於每次調度前要計算響應比，系統開銷也要相應增加。

⑶ 如何判斷演算法優劣

演算法的好壞是看它的運行效率比如遞歸一般來說是比較耗時間的，也就是說效率低當然也看具體情況，有的演算法在基數小的情況是差不多，性能反而還好點

⑷ 如何衡量一個演算法的優劣有哪些標准

如何衡量一個演算法的優劣，見人見智。一個好的演算法首先是要能夠滿足場景的需求，其次是在能夠最大限度的節省資源（最低成本原則），最後是實現邏輯簡單，比較容易理解(本質上也是最低成本原則)。但是，在現實中硬體資源不變，演算法不變情況下，演算法執行的效率提高，相對應往往是資源消耗增加。一個合格的演算法是在一個可以接受的范圍內滿足場景需求，而一個優秀的演算法則是在滿足場景需求的基礎上，最大限度的節省資源，簡化邏輯。

比如我要完成一項計算任務，要求是在5分鍾執行完成。現在有演算法1:需要執行1分鍾，消耗內存8G；演算法2需要執行3分鍾，需要消耗內存256M。那麼，我們應該如何選擇呢？首先，這兩種方案都能滿足我們的需求；其次：演算法1的需要消耗的資源是演算法2的32倍，演算法1的效率是演算法2的3倍。在這種滿足需求的情況下，往往更傾向於選擇演算法2。衡量一個演算法的優劣往往要評估多方因素，結合實踐，綜合比較最終得出結論。

衡量一個演算法的的標准主要有3個： 演算法的執行效率 ， 演算法的內存消耗 和 演算法的穩定性 。

⑸ 深度優先演算法 和 寬度優先演算法 的優缺點

1、深度優先演算法佔內存少但速度較慢，廣度優先演算法佔內存多但速度較快，在距離和深度成正比的情況下能較快地求出最優解。
2、深度優先與廣度優先的控制結構和產生系統很相似，唯一的區別在於對擴展節點選取上。由於其保留了所有的前繼節點，所以在產生後繼節點時可以去掉一部分重復的節點，從而提高了搜索效率。
3、這兩種演算法每次都擴展一個節點的所有子節點，而不同的是，深度優先下一次擴展的是本次擴展出來的子節點中的一個，而廣度優先擴展的則是本次擴展的節點的兄弟點。在具體實現上為了提高效率,所以採用了不同的數據結構。