用於快速選擇的非遞歸實現算法——循環疊代算法，與遞歸算法以及V c++標準庫函式nth_element進行了比較，表明該算法比傳統的遞歸算法具有較高的效率和可靠性； 與標準庫函式nth_ element比較，在時間效率方面具有明顯優勢。
基本介紹
- 中文名：疊代循環
- 外文名：Iterative loop
- 適用範圍：數學計算，程式編寫
- 區別：遞歸算法，nth_element
- 套用軟體：matlab，excel，python
- 套用算法：EM算法
基本概念,步驟,疊代求根注意事項,與遞歸對比,定義：,階段：,注意：,三種算法CPU時間對比,
基本概念
疊代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重複性操作的特點，讓計算機對一組指令(或一定步驟)進行重複執行，在每次執行這組指令(或這些步驟)時，都從變數的原值推出它的一個新值。
步驟
利用疊代算法解決問題，需要做好以下三個方面的工作：
一、確定疊代變數。在可以用疊代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變數，這個變數就是疊代變數。
二、建立疊代關係式。所謂疊代關係式，指如何從變數的前一個值推出其下一個值的公式(或關係)。疊代關係式的建立是解決疊代問題的關鍵，通常可以使用遞推或倒推的方法來完成。
三、對疊代過程進行控制。
疊代求根注意事項
具體使用疊代法求根時應注意以下兩種可能發生的情況：
(1) 如果方程無解，算法求出的近似根序列就不會收斂，疊代過程會變成死循環，因此在使用疊代算法前應先考察方程是否有解，並在程式中對疊代的次數給予限制;
(2) 方程雖然有解，但疊代公式選擇不當，或疊代的初始近似根選擇不合理，也會導致疊代失敗。
與遞歸對比
定義：
遞歸是設計和描述算法的一種有力的工具，由於它在複雜算法的描述中被經常採用，為此在進一步介紹其他算法設計方法之前先討論它。
程式調用自身的編程技巧稱為遞歸( recursion)。
階段：
一個過程或函式在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程式就可描述出解題過程所需要的多次重複計算，大大地減少了程式的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。用遞歸思想寫出的程式往往十分簡潔易懂。
一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進;當邊界條件滿足時，遞歸返回。
由於遞歸引起一系列的函式調用，並且可能會有一系列的重複計算，遞歸算法的執行效率相對較低。當某個遞歸算法能較方便地轉換成遞推算法時，通常按遞推算法編寫程式。
注意：
1) 遞歸就是在過程或函數裡調用自身；
2) 在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
三種算法CPU時間對比
利用隨機數生成算法產生了六組整型數據， 採用等間距選取k值， 統計 l 0次第k最小量選擇的時間耗費。測試環境為LENOVOB560，CPU Intel Core i3 M380@ 2.53GH z，4GB記憶體， Windows7 Ultimate 32 bit。算法編譯環境為VisualC ++ 2010。測試結果見表1。表中列出了循環疊代算法、遞歸算法和Visual c ++ 2010標準庫(ST L )中的第k最小數選擇函式nth_element的CPU時間。
數組大小 （*106） | CPU時間/ms | ||
循環疊代算法 | 遞歸算法 | nth_element | |
1 | 95 | 97 | 1344 |
2 | 173 | 186 | 2764 |
4 | 416 | 422 | 5283 |
8 | 745 | 749 | 9763 |
16 | 1456 | 1473 | 21629 |
32 | 2797 | 2834 | 43468 |
由表1可以看出， 循環疊代算法與遞歸算法之間在時問耗費上相差不大， 但總體上循環疊代算法高於遞歸算法，而且，隨輸入數組大小的增加有擴大的趨勢。與標準庫函式nth_element比較，本文算法的時間效率明顯較高。nth_element是 STL 庫中的套用非常廣泛的第k最順序量選擇函式。Visual c++ 2010標準庫(STL )函式nth_element在快速選擇算法的基礎上，主要在兩個方面進行 了最佳化：一是採用三元素取中算法確定劃分主元； 二是當子數組元素數小於32時， 則採用插入排序算法進行全排序，再取出第k順序統計量 ，只有當子數組元素數大於或等於 32時，才會採用快速選擇算法進行處理。然而，由於 STL 庫函式nth_element採用疊代器(i t er at or)來進行數組元素訪問，降低了運行效率，因而整體運行效率較低。本文算法與遞歸算法之間時間耗費相差不大的原因，主要在於測試數據是隨機生成的，選取主元時沒有出現極端情況，算法運行時遞歸深度不大，不會造成系統堆疊溢出。為了測試極端情況下的算法運行情況，先對輸入數組進行排序，並直接以每次劃分輸入子數組的起始元素作為主元進行測試，當數組大小超過4500時，遞歸算法會出現堆疊溢出，而循環疊代算法則仍能正常運行 。
因而，與遞歸算法比較 ， 循環疊代算法雖然在時間效率方面優勢不太明顯 ，但其可靠性較高；與標準庫函式nth_element比較，循環疊代算法在時間效率方面具有明顯優勢。
