第四章分治算法 §1.算法基本思想 考虑下面折半搜索算法 程序4-1-1折半搜索 template<class T, int BinarySearch(t al, const T& x, int n W/在数组a[0:n-1]中搜索x,数组中的元素满足a[0]<=a[1] ·<≡a[n-1]。如果找到x,则返回所在位置(数组元素的下标) //否则返回-1 int left=0; int right=n-1 while(left(=right)( int middle=(left+right)/2 if(x==amiddle]) return middle if(x)a middled) left=middle+1 else right=middle -1 return-1;//未找到x while的每次循环(最后一次除外)都将以减半的比例缩小搜索范围,所以, 该循环在最坏的情况下需要执行θ(logn)次。由于每次循环需耗时⊙(1),因此在 最坏情况下,总的时间复杂性为e(logn) 折半搜索算法贯彻一个思想,即分治法。当人们要解决一个输入规模,比 如n,很大的问题时,往往会想到将该问题分解。比如将这n个输入分成k个不 同的子集。如果能得到k个不同的可独立求解的子问题,而且在求出这些子问题 的解之后,还可以找到适当的方法把它们的解合并成整个问题的解,那么复杂的 难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的 方法称为分治法。一般来说,被分解出来的子问题应与原问题具有相同的类型, 这样便于采用递归算法。如果得到的子问题相对来说还较大,则再用分治法,直 到产生出不用再分解就可求解的子问题为止。人们考虑和使用较多的是k=2的情第四章 分 治 算 法 §1. 算法基本思想 考虑下面折半搜索算法 程序 4-1-1 折半搜索 template<class T> int BinarySearch(T a[], const T& x, int n) {// 在 数 组 a[0:n-1] 中 搜 索 x ， 数 组 中 的 元 素 满 足 a[0]<=a[1] //<= ···<=a[n-1]。如果找到 x，则返回所在位置（数组元素的下标）， //否则返回 –1 int left=0; int right=n-1; while(left<=right){ int middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left=middle+1; else right=middle – 1; } return –1; //未找到 x } while 的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以， 该循环在最坏的情况下需要执行Θ(log n)次。由于每次循环需耗时Θ(1) ，因此在 最坏情况下，总的时间复杂性为Θ(log n)。 折半搜索算法贯彻一个思想，即分治法。当人们要解决一个输入规模，比 如 n，很大的问题时，往往会想到将该问题分解。比如将这 n 个输入分成 k 个不 同的子集。如果能得到 k 个不同的可独立求解的子问题，而且在求出这些子问题 的解之后，还可以找到适当的方法把它们的解合并成整个问题的解，那么复杂的 难以解决的问题就可以得到解决。这种将整个问题分解成若干个小问题来处理的 方法称为分治法。一般来说，被分解出来的子问题应与原问题具有相同的类型， 这样便于采用递归算法。如果得到的子问题相对来说还较大，则再用分治法，直 到产生出不用再分解就可求解的子问题为止。人们考虑和使用较多的是 k=2 的情