[科普中国]-迭代循环

基本概念

迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。1

步骤利用迭代算法解决问题，需要做好以下三个方面的工作：

一、确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

迭代求根注意事项具体使用迭代法求根时应注意以下两种可能发生的情况：

(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时间。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比较，循环迭代算法在时间效率方面具有明显优势。