.
第一章
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)). 分析与解答：
Word 文档
.
因此，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: 执行成功，最大元素位置和最小元素位置相等 */
Word 文档
.
static int
BinarySearch(TYPE_t aArr[], int nLen, TYPE_t xVar, int *iIndex, int *jIndex) {
int left = 0;
int right = nLen - 1;
int middle = (left + right) / 2;
while (left <= right){
if (xVar == aArr[middle]){
*iIndex = *jIndex = middle; return 1; }
if (xVar > aArr[middle]){ left = middle + 1; }else{
right = middle - 1; }
middle = (left + right) / 2; }
*iIndex = right; *jIndex = left;
return 0; }
算法分析题2 – 6 对任何非零偶数n，总可以找到奇数m和正整数k，使得n = m * 2^k.为了求出2个n阶矩阵的乘积，可以把一个n阶矩阵划分成m×m个子矩阵，每个子矩阵2^k×2^k个元素。当需要求2^k×2^k的子矩阵的积时，使用Strassen算法。设计一个传统方法与Strasssen算法相结合的矩阵相乘算法，对于任何偶数n，都可以求出2个n阶矩阵的乘积。并分析算法的计算时间复杂度。 分析与解答：
将n阶矩阵分块为m×m的矩阵。用传统方法求2个m阶矩阵的乘积需要计算O(m^3)次2个2^k×2^k矩阵的乘积。用Strassen矩阵乘法计算2个2^k×2^k的矩阵的乘积需要的计算时间为O(7^k), 因此算法的计算时间为O(7^k*m^3).
算法分析题2 - 9 设T[0, n-1]是n个元素的数组。对任一元素x，设S(x) = {i | T[i] = x }. 当 |S(x) | > n/2时，称x为T的主元素。设计一个线性时间算法，确定T[0:n-1]是否有一个主元素。
分析与解答： 如果T有一个主元素x，则x是T的中位数。 反之，如果T的中位数不是T的主元素，则T没有主元素。 下面算法设计为在一个线性时间中找中位数：
typedef int T;
Word 文档
.
#define YES_MIDDLE_ELEMENT 1 #define NO_MIDDLE_ELEMENT 0 /*
* Function name:
* IsExistMiddleElement * Parameters:
* aArr[]: 表示数组T[0:n-1] * n: 表示数组长度
* x: 表示要判断的数x，是否主元素 * *keyIndex: 表示主元素在数组中的下标 * * Return:
* YES_MIDDLE_ELEMENT: 表示找到 * NO_MIDDLE_ELEMENT: 表示没有找到 */ static int
IsExistMiddleElement(T aArr[], int n, T x, int *keyIndex) {
int middleKey = n / 2; int i = 0;
for (i = 0; i < n; i++){
if ((aArr[i] == x) && ((i + 1) > middleKey)){ *keyIndex = i;
return YES_MIDDLE_ELEMENT; } }
*keyIndex = -1;
return NO_MIDDLE_ELEMENT; }
算法分析题2-14 对所给元素存储于数组中和存储于链表中2中情形，写出自然合并排序算法。
分析与解答：
自然合并排序是合并排序算法的一种改进。自然合并排序，对于初始给定的数组，通常存在多个长度大于1的已自然排好序的子数组段。例如，若数组a中元素为{4,8,7,1,5,6,2},则自然排好序的子数组段有{4,8}, {3, 7}, {1,5,6}, {2}.用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段。然后将相邻的排好序的子数组段两两合并，构成更大的排好序的子数组段{3,4,7,8}, {1, 2,5,6}.继续合并相邻排好序的子数组段，直至整个数组已经排好序。 算法设计及代码实现： (1). 数组实现法： #define DEBUG 1 typedef int type_t; static void
Word 文档
.
DatasetMerge(type_t *arr, int left, int between, int right) {
int i, k;
int begin1, end1, begin2, end2; type_t *tmpArr;
begin1 = left; /*第一个排好序的初始位置*/ end1 = between; /*第一个排好序的结束位置*/
begin2 = between + 1; /*第二个排好序的初始位置*/ end2 = right; /*第二个排好序的结束位置*/
tmpArr = malloc(sizeof(type_t) * (right - left + 1)); if (!tmpArr){ return; }
k = 0; /*
* 比较两个指针指向的元素，选择相对小的元素放入合并空间 * 并移动指针到下一个位置 */
while ((begin1 <= end1) && (begin2 <= end2)){ if (arr[begin1] < arr[begin2]){ tmpArr[k] = arr[begin1]; begin1++; }else{
tmpArr[k] = arr[begin2]; begin2++; } k++; } /*
×如果第一个序列有剩余，直接拷贝到合并数组的序列中 */
while (begin1 <= end1){
tmpArr[k++] = arr[begin1++]; } /*
*如果第二个序列有剩余，直接拷贝到合并数组的序列中 */
while(begin2 <= end2){
tmpArr[k++] = arr[begin2++]; } /*
*拷贝临时数组序列到原数组中
Word 文档
算法设计与分析课后习题
