所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，
是指重复“减半”的过程。
例 1.3 设方程 f（x）=0 在区间[a，b]上有实根，且 f（a）与 f（b）异号。
利用二分法求该方程在区间[a，b]上的一个实根。
用二分法求方程实根的减半递推过程如下：
首先取给定区间的中点 c=（a+b）／2。
然后判断 f（c）是否为 0。
若 f（c）=0，则说明 C 即为所求的根，求解过程结束；
如果 f（c）≠0，则根据以下原则将原区间减半：
若 f（a）f（c）<0，则取原区间的前半部分；
若 f（b）f（c）<0，则取原区间的后半部分。
最后判断减半后的区间长度是否已经很小：
若|a-b|<ε，则过程结束，取（a+b）／2 为根的近似值；
若|a-b|≥ε，则重复上述的减半过程。
6．回溯法
通过对问题的分析，找出一个解决问题的线
索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得
到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称
为回溯法。
在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步
骤,并且也不能进行无限的列举。对于这类问题,一种有效的方法是“试”。
三、算法复杂度
主要包括时间复杂度和空间复杂度。
1．算法的时间复杂度
（1）定义
执行算法所需要的计算工作量。
（2）衡量标准
通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
算法所执行的基本运算次数还与问题的规模有关。
综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所
执行的基本运算次数是问题规模的函数，即算法的工作量=f（n）。
（3）存在问题
算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能
将所有可能情况下算法所执行的基本运算次数都列举出来。
