算法设计与分析课后习题

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)

{

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;

#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

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++];

}

/*

*拷贝临时数组序列到原数组中

*/

for (i = 0; i <= (right - left); i++){

arr[left + i] = tmpArr[i];

}

free(tmpArr);

}

void DatasetNatureMerge(type_t arr[], int n){

int *tmpArr;

int i, k = 0;

int s = 1;

int group; /*记录分割组的数目*/

int count = 0;

int left, between, right;

int arrLen = n;

/*

*tmpArr 用来存储数组元素下标分割点

*/

tmpArr = (int*)malloc(n * sizeof(int));

if (!tmpArr){

return;

}

memset(tmpArr, -1, (n * sizeof(int)));

/*

* 存储首分割点

*/

tmpArr[k++] = 0;

for (i = 0; i < arrLen - 1; i++){

if (arr[i] > arr[i+1]){

tmpArr[k] = i;

k++;

}

}

/*

* 存储尾分割点

*/

tmpArr[k] = n - 1;

/*

* k 和 group 分别记录分割数组长度

*/

group = k;

#if DEBUG

printf(\"\\n数组分割点为:\\n\");

printf(\"\\");

for (i = 0; i <= group; i++){

if (i == 10){

printf(\"\\n\\");

}

printf(\"%d \

}

printf(\"\\n\");

#endif

s = 1;

for (group; group != 1; group = ((group % 2 == 0) ? (group / 2) : (group / 2 + 1))){

/*

*合并次数，例如：5组合并需要两次，4组合并也需要两次

*/

count = group / 2;

/*

*进行第一次合并

*/

left = 0;

between = s;

right = 2 * s;

if (right > k){

right = k;

}

DatasetMerge(arr, tmpArr[left], tmpArr[between], tmpArr[right]);

/*

* 进行生下来的合并

*/

for (i = 1; i < count; i++){

left = right;

between = left + s;

right = between + s;

if (right > k){

right = k;

}

DatasetMerge(arr, tmpArr[left + 1], tmpArr[between], tmpArr[right]);

}

s += s;

}

free(tmpArr);

}

(2). 链表实现法：

#if LINK

typedef struct node *link_t;

struct node {

int item;

link_t next;

};

link_t LinkMerge(link_t a, link_t b){

link_t c, head;

c = head = malloc(sizeof(struct node));

while ((a != NULL) && (b != NULL)){

if (a->item < b->item){

c->next = a;

c = a;

a = a->next;

}else{

c->next = b;

c = b;

b = b->next;

}

}

c->next = (a == NULL) ? b : a;

return head->next;

}

link_t LinkNuturalMergesort(link_t t){

link_t a, b;

link_t u, v;

QUEUE Q;

if (t == NULL || t->next == NULL) return t;

for (u = t; t != NULL; t = u){

while (u && u->next && u->item <= u->next->item){

u = u->next;

}

v = u;

u = u->next;

v->next = NULL;

Q.ENQUEUE(t);

}

Q.DEQUEUE(t);

while (!Q.EMPTY()){

Q.ENQUEUE(t);

Q.DEQUEUE(a);

Q.DEQUEUE(b);

t = LinkMerge(a, b);

}

return t;

}

#endif