最长距离以完全二叉树的最短。对于每个二叉比较树,必有n个内顶点与x在A 中的n种可能的情况相对应。如果一棵二叉树的所有内顶点所在的级数小于或等 于级数k,则最多有2k-1个内顶点。因此n≤2*-1,即Find(n)=k2log(n+1)1。 证毕 由定理可见,任何一种以比较为基础的算法,其最坏情况下的所用时间不可 能低于(logm)。因此,也就不可能存在其最坏情况下时间比折半搜索数量级 (阶)还低的算法。事实上,折半搜索所产生的比较树的所有外部顶点都在相邻 的两个级上,而且这样的二叉树使得由根到叶顶点的最长路径减至最小,因此 折半搜索是解决搜索问题在最坏情况下的最优算法, §2关于排序算法 问题:已知n个元素的数组A[1:n],将A中元素按不降顺序排列。 归并排序算法 程序4-2-1向有序数组插入元素 程序4-2-2插入排序 template<class T> template<class T, void Insert (t a[, int& n, const t& x)i void InsertionSort (t a[, int n) /向数组a[0:n-1]中插入元素x W/对a[0:n-1]进行排序 //假定a的大小超过n for (int i=l: i<n: i++I int Tt=alil for(i=n-1;i>=0&&x<a[i];i--) Insert(a a[i+1]=a[i] [i+1]=x; n++;//添加了一个元素 将上述两个算法合并在一起,得到下述插入排序算法 程序4-2-3插入排序算法伪代码 Insert Sort(A,n)//将A[l:n]中的元素按非降次序排列,n≥1 A[0]=-∞//生成一个虚拟值 for j from2 to n do//A[1:j1]已经排序最长距离以完全二叉树的最短。对于每个二叉比较树，必有 n 个内顶点与x在A 中的 n 种可能的情况相对应。如果一棵二叉树的所有内顶点所在的级数小于或等 于级数 k，则最多有2 −1 k 个内顶点。因此 ≤ 2 −1 k n ，即 Find(n)=k≥log(n+1)。 证毕 由定理可见，任何一种以比较为基础的算法，其最坏情况下的所用时间不可 能低于Θ(logn)。因此，也就不可能存在其最坏情况下时间比折半搜索数量级 （阶）还低的算法。事实上，折半搜索所产生的比较树的所有外部顶点都在相邻 的两个级上，而且这样的二叉树使得由根到叶顶点的最长路径减至最小，因此， 折半搜索是解决搜索问题在最坏情况下的最优算法。 §2.关于排序算法 问题：已知 n 个元素的数组 A[1:n]，将 A 中元素按不降顺序排列。 z 归并排序算法 程序 4-2-1 向有序数组插入元素 程序 4-2-2 插入排序 template<class T> template<class T> void Insert(T a[], int& n, const T& x) void InsertionSort(T a[], int n) {//向数组 a[0:n-1]中插入元素 x {//对 a[0:n-1]进行排序 //假定 a 的大小超过 n for(int i=1; i<n; i++) { int i; T t =a[i]; for(i=n-1; i>=0 && x<a[i]; i--) Insert(a, i, t); a[i+1]=a[i]; } a[i+1]=x; } n++; //添加了一个元素 } 将上述两个算法合并在一起，得到下述插入排序算法： 程序 4-2-3 插入排序算法伪代码 InsertSort (A,n) //将 A[1:n]中的元素按非降次序排列，n≥1 A[0]=−∞ //生成一个虚拟值 for j from 2 to n do // A[1:j-1]已经排序