第一章 1. 算法分析题 算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5 是，n^2 < 2 ^n 所以，当n >= 1 时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1) 因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2) 因为：log(n) < √n ; f(n) = 2log(n); g(n)= √n 所以：f(n) = O(g(n)) (3) 因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4) 因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5) 因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6) 因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7) 因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8) 因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答： 因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题 2-3 设a[0:n-1]是已经排好序的数组。请改写二分搜索算法，似的当搜索元素 x在数组中时，返回小于 x 的最大元素位置 i 和大于 x 的最小元素位置 j。当搜索元素在数组中时， i 和 j 相同，均为 x 的位置。 分许与解答： 改写二分搜索算法如下： typedef int TYPE_t; /* * Function name: BinarySearch * Parameters: * iIndex 代表 i 的位置，即最大元素位置; * jIndex 代表 j 的位置，即最小元素位置; * aArr[]: 代表数组a[],且有序 * xVar:代表元素 x; * aLen: 代表数组元素个数; * Return value: * 0: 执行成功，最大元素位置和最小元素位置不等 * 1: 执行成功，最大元素位置和最小元素位置相等 */ static int BinarySearch(TYPE_t aArr[], int nLen, TYPE_t xVar, int *iIndex, int *jIndex) { ...
