【算法导论】第2章 算法基础

举报
1+1=王 发表于 2022/12/08 09:35:43 2022/12/08
【摘要】 【算法导论】第2章 算法基础
  • 2.1-1 说明INSERTION-SORT在数组A=<31,41,59,26,41,58>上的执行过程。

    a. <31,41,59,26,41,58>
    b. <31,41,59,26,41,58>
    c. <31,41,59,26,41,58>
    d. <26,31,41,59,41,58>
    e. <26,31,41,41,59,58>
    f. <26,31,41,41,58,59>

  • 2.1-2 重写过程INSERTION-SORT,使之按非升序排序。

for i=2 to A.length
	key = a[i]
	j = i - 1
	while j>0 and a[j]<key
		A[j+1] = A[j]
		j = j - 1
	A[j+1] = key
  • 2.1-3 考虑以下查找问题:
    输入:n个数的一个序列A=<a1,a2,a3,…,an>和一个值v。
    输出:下标i使得v=A[i]或者当v 不在A中出现时,v为特殊值NIL。
for i=1 to n
	if v = A[i]
		return i;
	return NIL;
证明循环不定式成立:
	初始化:迭代之前,其子数组为空,没有找到继续循环,循环不定式成立。
	保持:如果A[1...i-1]不包含v,我们比较A[i]与v。相等则返回i,不等则进行下一步。
	终止:i>A.length,则A中肯定不包含v,返回NIL。
  • 2.1-4 把两个n为二进制整数加起来,这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按照二进制形式存储在一个(n+1)元数组C中。
ADD_BINARY(A,B):
	C = new integer[A.length + 1]
	temp = 0
	for i=1 to A.length
		C[i] = (A[i] + B[i] + temp) % 2
		temp = (A[i] + B[i] + temp) / 2
	C[i+1] = temp
	return C

@[TOC](2.2 分析算法)

  • 2.2-1 表示函数n^3 / 1000 - 100n^2 -100n + 3。

    n^3 / 1000 - 100n^2 -100n + 3 = O(n^3)

  • 2.2-2 写出选择排序算法的伪代码。该算法维持的循环不定式是什么?为什么只需要对前n-1个元素,而不是对所有n个元素运行?给出选择排序的最好情况和最坏情况运行时间。

SELECT_SORT(A,n):
	for i=0 to n-1
		min = i
		for j=i+1 to n
			if A[j] < A[min]
				min = j
			if min != j
				swap(A[i],A[min])	//交换A[i]和A[min]
证明循环不定式成立:
	初始化:迭代之前,子数组为空,循环不定式成立。
	保持:当迭代至第 i 时,子数组A[1,...,i-1]已按序排列,for循环的下一次迭代增加i将保持循环不定式。
	终止:当i迭代至i=n-1时,A[1-n]都按序排列。

每次迭代都是找出A[i-n]中的最小元素,在经过n-1次后,剩下的最后一个元素一定为A中的最大元素。

最好情况与最坏情况均为O(n^2)

  • 2.2-3 再次考虑现行查找问题(练习2.1-3)。假定要查找的元素等可能的为数组中的任意元素,平均需要检查输入序列的多少元素?最坏元素又如何?

    平均:待查找的元素等概率出现(概率为:1/n):(1 + 2 + 3 + … + n)/ n = (n+1) / 2
    最坏:n
    运行时间均为:O(n)

  • 2.2-4 应如何修改任何一个算法,才能使之具有良好的最好情况运行时间?

    在算法中加入对最好情况的判断。例如:排序时,如果输入序列已经排好序,则直接return,这样最好情况运行时间为O(n)。

@[TOC](2.3 设计算法)

  • 2.3-1 说明并归排序在数组A = < 3,41,52,26,38,57,9,49 >上的操作。
    在这里插入图片描述

  • 2.3-2 重写过程MERGE,使之不使用哨兵,而是一旦数组L或R的所有元素均被复制回A就立刻停止,然后把另一个数组的剩余部分赋值回A。

MERG(A,p,q,r):
	n1 = q-p+1
	n2 = r-q
	for i = 1 to n1
		L[i] = A[p+i-1]
	for j = 1 to n2
		R[j] = A[q+j}
	temp = 1
	for k1 = p to q and k2 = q+1 to r
		if L[k1] <= L[k2]
			A[temp] = L[k1]
			temp = temp + 1
		else
			A[temp] = L[k2]
			temp = temp + 1
	while(k1 <= q)
		A[temp++] = L[k1++]
	while(k2 <= r)
		A[temp++] = R[k2++]
  • 2.3-3使用数学归纳法证明:当n刚好是2的幂时,一下递归式的解是T(n)=nlgn。
    T(n)=2,若n=2
    T(n)=2T(n/2)+n, 若n=2^k,k>1

    在这里插入图片描述

  • 2.3-4 我们可以把插入排序表示为如下的一个递归过程。为了排序A[1…n],我们递归地排序A[1…n-1],然后把A[n]插入已排序的数组A[1…n-1]。为插入排序的这个递归版本的最坏情况运行时间写一个递归式。

在这里插入图片描述

  • 2.3-5 回顾查找问题(参见练习2.1-3),注意到,如果序列A已排好序,就可以将该序列的中点与v进行比较。根据比较的结果,原序列中有一半就可以不用再做进一步的考虑了。二分查找算法重复这个过程,每次都将序列剩余部分的规模减半。为二分查找写出迭代或递归的伪代码。证明:二分查找的最坏情况运行时间为O(lgn)。
BINARY_SEARCH(A,key,p.r):
	if mid >= r and key != A[p]
		return NIL
	j = (r-p) / 2
	if key = A[j]
		return j;
	else
		if key < A[j]
			return BINARY_SEARCH(A,key,p,j)
		else
			return BINARY_SEARCH(A,key,j,r)

//	T(n) = O(lgn)
  • 2.3-6 注意到2.1节中的过程 INSERTION-SORT 的第5~7行的while循环采用一种线性查找来(反向)扫描已排好序的子数组A[1…j-1]。我们可以使用二分查找(参见练习2.3-5)来把插入排序的最坏情况总运行时间改进到O(nlgn)吗?
INSERTION_SORT:
	for i=2 to A.length
		key = A[i]
		low = 1 
		high = i-1
		while low <= high
			mid = (low + high) / 2
			if key = A[mid]
				break
			else if key < A[mid]
				high = mid- 1
			else
				low = mid + 1
		for j = mid to i-1
			A[j+1] = A[j]
		A[mid] = key

在最坏情况下,二分查找的时间复杂度为nlgn,但元素的移动次数未改变,它依赖于待排序表的初始状态,因此总运行时间不能改进到O(nlgn),仍然为O(n^2)。

  • 2.3-7 描述一个运行时间为O(nlgn)的算法,给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个其和刚好为x的元素。

    (1)将集合S排序(并归排序) O(lgn)
    (2)循环折半查找 x-A[i],存在 return true;不存在 return false

CHECK_SUMS(A,x):
	SORT(A)
	for i = 1 to A.length
		if BINARY_SEARCH(A,x-A[i],i,n)
			return true

@TOC

  • 2-1 (在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为O(n lgn),而插人排序的最坏情况运行时间为O(n^2),但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行得更快。因此,在归并排序中当子问题变得足够小时,采用插人排序来使递归的叶变粗是有意义的。考虑对归并排序的一种修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表,这里k是一个待定的值。
    a. 证明:插入排序最坏情况可以在O(nk)时间内排序每个长度为k的n/k个子表。
    b. 表明在最坏情况下如何在O(nlg(n/k))时间内合并这些子表。
    c. 假定修改后的算法的最坏情况运行时间为O(nk十nlg(n/k)),要使修改后的算法与标准的归并排序具有相同的运行时间,作为n的一个函数,借助O记号,k的最大值是什么?
    d. 在实践中,我们应该如何选择k?

    a. 插入排序最坏运行时间为O(n^2),即 ak^2 + bk + c;
    n/k个子表共需:n/k(ak^2 + bk + c) = ank + bn + nc/k = O(nk);

    b. 并归排序时递归树树高为:lg(n/k),每个叶子代价为ck
    合并的总代价为O(ck(n/k)lgn/k) = O(nlgn/k)

    c. O(nk + nlgn/k) = O(nlgn),即k <= lgn,k的最大值为lgn

    d. 选择的k值应使插入排序快于并归排序

  • 2-4 (逆序对)假设A_1…n]是一个有n个不同数的数组。若i<j且Ai>Aj],则对偶(i,j)称为A的一个逆序对(inversion)。
    a. 列出数组(2,3,8,6,1>的5个逆序对。
    b. 由集合{1,2,…,n)中的元素构成的什么数组具有最多的逆序对?它有多少逆序对?
    c. 插人排序的运行时间与输人数组中逆序对的数量之间是什么关系?证明你的回答。

    a. < 2,1 >,< 3,1 >,< 8,1 >,< 6,1 >,< 8,6 >
    b. 当集合降序排列时,具有最多的逆序对,共有n(n-1)/2对。
    c. 逆序对的数量决定while内循环的执行次数。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。