算法复杂性分析 比较两对算法的效率 ............................................................................................ 1 复杂性的计量 ........................................................................................................ 3 复杂性的渐近性态及其阶 .................................................................................... 6 复杂性渐近阶的重要性 ...................................................................................... 1 0 算法复杂性渐近阶的分析 .................................................................................. 1 2 递归方程解的渐近阶的求法 .............................................................................. 1 6 递归方程组解的渐进阶的求法——代入法 ................................................................. 1 6 递归方程组解的渐进阶的求法——迭代法 ................................................................. 1 9 递归方程组解的渐进阶的求法——套用公式法 ......................................................... 2 3 递归方程组解的渐进阶的求法——差分方程法 ......................................................... 2 5 递归方程组解的渐进阶的求法——母函数法 ............................................................. 2 9 比较两对算法的效率 考虑问题1：已知不重复且已经按从小到大排好的m 个整数的数组A[1..m]（为简单起见。还设 m=2 k，k 是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标 i，使得 A[i]=c；若找不到，则返回一个0。 问题1 的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A 的第 i 个分量，经检测满足 A[i]=c；或者扫到A 的最后一个分量，经检测仍不满足 A[i]=c。我们用一个函数Search 来表达这个算法： Function Search (c:integer):integer; Var J:integer; Begin J:=1; {初始化} {在还没有到达 A 的最后一个分量且等于 c 的分量还没有找到时， 查找下一个分量并且进行检测} While (A[i]
