算法设计与分析王晓东

习题2-1 求下列函数的渐进表达式：

3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。 解答：3n^2+10n=O(n^2), n^2/10+2^n=O(2^n), 21+1/n=O(1), logn^3=O(logn), 10log3^n=O(n).

习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。 解答：照渐进阶从高到低的顺序为：n!、 3^n、4n^2 、20n、n^2/3、logn、2 习题2-4

(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？

(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？

(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？

解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6 (2)n1^2=64n^2得到n1=8n

(3)由于T（n)=常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答：n'=100n

n'^2=100n^2得到n'=10n n'^3=100n^3得到n'=4.64n n'!=100n!得到n'

习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。

解答：（1）f(n)=logn^2;g(n)=logn+5. logn^2=θ（logn+5） (2)f(n)=logn^2;g(n)=根号n. logn^2=O(根号n) (3)f(n)=n;g(n)=(logn)^2. n=Ω(（logn）^2) (4)f(n)=nlogn+n;g(n)=logn. nlogn+n=Ω（logn） (5)f(n)=10;g(n)=log10. 10=θ(log10)

(6)f(n)=(logn)^2;g(n)=logn. (logn)^2=Ω（logn） (7)f(n)=2^n;g(n)=100n^2. 2^n=Ω（100n^2） (8)f(n)=2^n;g(n)=3^n. 2^n=O(3^n)

习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为θ（f(n)），则该算法在最坏情况下所需的计算时间为Ω（f(n)）。 证明：Tavg(N)=IeDn∑P(I)T(N,I) ≤IeDn∑P(I)IeDnmaxT(N,I')

=T(N,I*)IeDn∑P(I) =T(N,I*)=Tmax(N)

因此，Tmax(N)=Ω（Tavg(N)）=Ω（θ(f(n))）=Ω（f(n)） 习题2-8 求解下列递归方程： So=0;

Sn=2Sn-1+2^n-1.

解答： 1应用零化子化为齐次方程， 2解此齐次方程的特征方程， 3由特征根构造一般解，

4再由初始条件确定待定系数，得到解为：Sn=(n-1)2^n+1 习题2-9 求解下列递归方程 Ho=2; H1=8;

Hn=4Hn-1-4Hn-2. 解：Hn=2^(n+1)(n+1) 第三章 递归与分治策略

习题3-1 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。 public static int binarySearch1(int []a,int x,int n) {

int left=0; int right =n-1; while (left<=right) {

int middle = ( left + right )/2; if ( x == a[middle]) return middle; if ( x> a[middle]) left = middle; else right = middle; return -1; }

public static int binarySearch2(int []a, int x, int n) {

int left = 0; int right = n-1; while ( left < right-1 ) { int middle = ( left + right )/2; if ( x < a[middle]) right = middle; else left = middle; }

if (x == a[left]) return left; else return -1 }

public static int binarySearch3(int []a, int x, int n) {

int left = 0; int right = n-1; while ( left +1 != right) { int middle = ( left + right)/2; if ( x>= a[middle]) left = middle; else right = middle; }

if ( x == a[left]) return left ; else return -1; }

public static int binarySearch4(int []a, int x, int n) {

if (n>0 && x>= a[0]) { int left = 0; int right = n-1; while (left < right ) { int middle = (left + right )/2; if ( x < a[middle]) right = middle -1 ; else left = middle; }

if ( x == a[left]) return left; } return -1; }

public static int binarySearch5(int []a, int x, int n) {

if ( n>0 && x >= a[0] ) { int left = 0; int right = n-1; while (left < right ) {

int middle = ( left + right +1)/2; if ( x < a[middle]) right = middle -1; else left = middle ; }

if ( x == a[left]) return left; } return -1; }

public static int binarySearch6(int []a, int x, int n) {

if ( n>0 && x>= a[0]) { int left = 0; int right = n-1; while ( left < right) {

int middle = (left + right +1)/2;

if (x < a[middle]) right = middle – 1; else left = middle + 1; }

if ( x == a[left]) return left ; } return -1; }

public static int binarySearch7(int []a, int x, int n) {

if ( n>0 && x>=a[0]) { int left = 0; int right = n-1; while ( left < right) {

int middle = ( left + right + 1)/2; if ( x < a[middle]) right = middle; else left = middle; }

if ( x == a[left]) return left; } return -1; }

分析与解答：

算法binarySearch1数组段左右游标left和right的调整不正确，导致陷入死循环。

算法binarySearch2数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。 算法binarySearch3数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。 算法binarySearch4数组段左右游标left和right的调整不正确，导致陷入死循环。 算法binarySearch5正确，且当数组中有重复元素时，返回满足条件的最右元素。

算法binarySearch6数组段左右游标left和right的调整不正确，导致当x=a[n-1]时返回错误。 算法binarySearch7数组段左右游标left和right的调整不正确，导致当x=a[n-1]时陷入死循环。 习题3-2 设a[0:n-1] 是已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 分析与解答：

改写二分搜索算法如下：

public static boolean binarySearch(int []a, int x, int left, int right, int []ind) {

int middle;

while ( left <= right ) { middle = (left + right)/2;

if (x == a[middle]) { ind[0]=ind[1]=middle; return true;} if (x > a[middle]) left = middle + 1; else right = middle -1; }