数据结构、算法与应用-C++描述2.ppt

* * 搜索过程从x 与数组[left:right]中间元素的比较开始。 如果x等于中间元素，则查找过程结束。 如果x小于中间元素，则仅需要查找数组的左半部分，所以right 被修改为middle - 1。 如果x大于中间元素，则仅需要在数组的右半部分进行查找，left 将被修改为middle + 1。 折半搜索 * * [05 13 19 21 37 56 64 75 80 88 92] [05 13 19 21 37] 56 64 75 80 88 92 05 13 19 [21 37] 56 64 75 80 88 92 查找K=21的过程（查找成功） * * [05 13 19 21 37 56 64 75 80 88 92] 05 13 19 21 37 56 [64 75 80 88 92] 05 13 19 21 37 56 64 75 80 [88 92] 查找K=85的过程（查找失败） 05 13 19 21 37 56 64 75 80] [88 92 * * templateclass T int BinarySearch(T a[], const T x, int n) {// 在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的每次循环(最后一次除外)都将以减半的比例缩小搜索的范围，所以该循环在最坏情况下需执行Θ(logn)次。 由于每次循环需耗时Θ(1)，因此在最坏情况下，总的时间复杂性为Θ(logn)。 折半搜索性能 * * 可以利用复杂性函数对两个执行相同任务的程序P和Q进行比较。 假定程序P具有复杂性Θ(n)，程序Q具有复杂性Θ(n2)，可以断定，对于“足够大”的n，程序P比程序Q快。 2.5 Practical Complexities * * 函数的值 * * 函数曲线 * * 建议 从图中可以看出，随着n的增长，2n的增长极快。事实上，如果程序需要2n执行步，那么当n=40时，执行步数将大约为1.1*1012。在一台每秒执行1000000000步的计算机中，该程序大约需要执行18.3分钟；如果n=50，同样的程序在该台机器上将需要执行13天，当n=60时，需要执行310.56年；当n=100时，则需要执行4*1013年。因此可以认定，具有指数复杂性的程序仅适合于小的n(典型地取n≤40)。 * * 建议 具有高次多项式复杂性的函数也必须限制使用。 例如，如果程序需要n10执行步，那么当n=10时，每秒执行1000000000步的计算机需要10秒钟；当n=100时，需要3171年；n=1000时，将需要3.17*1013年。 如果程序的复杂性是n3，则当n=1000时，需要执行1秒；n=10000时，需要110.67分钟；n=100000时，需要11.57天。 * * 性能测量主要关注得到一个程序实际需要的空间和时间。 2.6 Performance Measurement * * 设计测试数据 对于许多程序，可以手工或用计算机来产生能导致最好和最坏复杂性的测试数据。 然而，对于平均的复杂性，通常很难设计相应的数据。 当不能给出能产生预期的复杂性的测试数据时，可以根据一些随机产生的测试数据所测量出的最小（最大，平均）时间来估计程序的最坏（最好，平均）复杂性。 * * 算法的后期测试 在算法中的某些部位插装时间函数 time ( ) 测定算法完成某一功能所花费时间 * * templateclass T int SequentialSearch(T a[], const T x, int n) {//在未排序的数组a[0:n-1]中搜索x，如果找到，则返回所在位置，否则返回- 1 int i; for (i = 0; i n a[i] != x; i++); if (i == n) return -1 ;