迭代循環

迭代算法是用計算機解決問題的一種基本方法。它利用計算機運算速度快、適合做重複性操作的特點，讓計算機對一組指令(或一定步驟)進行重複執行，在每次執行這組指令(或這些步驟)時，都從變量的原值推出它的一個新值。 ^[1] 

利用迭代算法解決問題，需要做好以下三個方面的工作：

一、確定迭代變量。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。

二、建立迭代關係式。所謂迭代關係式，指如何從變量的前一個值推出其下一個值的公式(或關係)。迭代關係式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。

三、對迭代過程進行控制。

具體使用迭代法求根時應注意以下兩種可能發生的情況：

(1) 如果方程無解，算法求出的近似根序列就不會收斂，迭代過程會變成死循環，因此在使用迭代算法前應先考察方程是否有解，並在程序中對迭代的次數給予限制;

(2) 方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。

遞歸是設計和描述算法的一種有力的工具，由於它在複雜算法的描述中被經常採用，為此在進一步介紹其他算法設計方法之前先討論它。

程序調用自身的編程技巧稱為遞歸( recursion)。

遞歸算法的執行過程分遞推和迴歸兩個階段。

一個過程或函數在其定義或説明中又直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重複計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。

一般來説，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進;當邊界條件滿足時，遞歸返回。

在編寫遞歸函數時要注意，函數中的局部變量和參數知識侷限於當前調用層，當遞推進入“簡單問題”層時，原來層次上的參數和局部變量便被隱蔽起來。在一系列“簡單問題”層，它們各有自己的參數和局部變量。

由於遞歸引起一系列的函數調用，並且可能會有一系列的重複計算，遞歸算法的執行效率相對較低。當某個遞歸算法能較方便地轉換成遞推算法時，通常按遞推算法編寫程序。

1) 遞歸就是在過程或函數里調用自身；

2) 在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

利用隨機數生成算法產生了六組整型數據， 採用等間距選取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時間。 ^[2] 

由表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比較，循環迭代算法在時間效率方面具有明顯優勢。