练习

2.1-2

将第5行判断A[ i ] > key –>   A[ i ] < key

2.1-3

Algorithm 1 Linear-Search( A, v )

输入 :数组A = < a1, a2, …, an > 和值 v

输出:使得A[ i ] == v 的下标, 若v不在A内输出 nil 

for i = 1 to n 

　　if A[ i ] == v

　　　　return i

　return nil

循环不变式: A[1, 2, …, i-1 ]中没有值等于v 。 

2.1-4

形式化描述(?) 模拟手算，二进制从低位到高位依次保存(大端(Big-endian)，便于进位)。

Algorithm 2 Binary-Addition(a, b, n)

输入:两个整数 a, b 与它们的二进制位数n

输出:a+b的二进制

let A[ 1…n ], B[ 1…n ] and C[ 1…n+1 ] to be new arrays

for i = 1 to n

　　A[ i ] = a&1

　　B[ i ] = b&1

　　a>>=1

　　b>>=1

for i = 1 to n

　　C[ i+1 ] = (C[ i ] +  A[ i ] + B[ i ] ) / 2 //进位

　　C[ i ]    = ( A[ i ] + B[ i ] ) %2 //当前位

2.2-1

n^3/1000 – 100n^2 – 100n + 3 = O( n^3 ) (暂时用O表示书中的theta 忽略系数，只取最高项)

2.2-2

假设函数Find-Min(A, r, s) 返回数组A下标从r到s的元素最小值的下标, 函数运行时间为O( s- r ) ( r<=s ) 

Algorithm 3 Selection-Sort( A )

输入:数组A

输出:顺序排列的A

for i in 1 to n-1

　　j = Find-Min( A, i, n )

　　A[ i ] <—> A[ j ]  //交换元素A[i]与A[j]

 循环不变式: A[ 1, 2, …, i-1 ] 已经排列完毕并且A数组其余元素都大于等于循环不变式中的元素

因为最后剩下的元素A[ n ] 一定是最大的，所以只需要排列n-1次

时间复杂度: for循环n-1次，Find-Min时间复杂度O( n ) 所以总体时间复杂度为 O(∑i(1<=i<=n)) = O( n^2 ) 这个复杂度同时符合(holds)最好情况和最坏情况

2.2-3

因为每个元素都有可能是要查找的元素，所以查找元素有1/2可能在数组前一半，同时有一半可能在数组后一半，平均下来需要查找一半的元素。

最坏情况即要查找的元素在最后一个，即要查找n次。 最好和最坏情况时间复杂度都为O( n )

2.2-4 

其中一个方法是针对最好情况修改算法，使其有效的处理最好情况。

2.3-4

 递归版本的插入排序:

Algorithm 4 Insertion-Sort( A , n )

输入:数组A

输出:顺序排列的A

if n>1 

　　Insertion-Sort( n-1 )

　　key = A[ n ]

　　i = n-1

　　while i>0 && A[ i ] > key

　　　　A[ i+1 ] = A[ i ]

　　　　i = i-1

　　A[ i+1 ] = key 

T( n ) = T( n-1 ) + O( n ) = O(∑i(1<=i<=n)) = O( n^2 ) 

2.3-5

递归版二分搜索:

Binary-Search( A, l, r, v)

输入 :数组A = < a1, a2, …, an > 和值 v

输出:使得A[ i ] == v 的下标, 若v不在A内输出 nil 

if l<r

　　m = ( l + r ) / 2

　　if A[m] ==v 

　　　　return m

　　if A[m] < v 

　　　　Binary-Search(A, m+1, r, v)

　　else

　　　　Binary-Search(A, l, m-1, v)

return nil

因为长度n最多二分lgn次，所以二分查找最坏情况为O(lgn)

2.3-6

 如果用二分搜索，其目标应该是返回第一个大于v的下标。二分的变形总结https://blog.csdn.net/qq_38742161/article/details/88838496  时间复杂度为O(lgn)

但找到下标后还需要让所有之后的元素后移一个位置，时间复杂度为O(n)，所以最坏运行时间为O(∑i(1<=i<=n-1)) = O( n^2 ) 

2.3-7

思路1:先用时间复杂度<=O( nlgn )的排序算法排序数组S（如归并排序），如果有a+b==x 则 a = x-b , 可以在S中用二分查找是否有值为x-S[ i ] (1<=i<=S.length ) T(n)=O(nlgn)+O(nlgn) = O(nlgn)

思路2:先排序,从两端到中间查找是否有S[ i ] + S[ j ] == x (1<=i<j<=S.length ) T(n) = O(nlgn) + O(n) = O(nlgn)

Algorithm 5 Check-Sum( S, x )

输入:数组S及数值x

输出:若S中有两个元素和为x，返回true , 否则false

Merge-Sort( S )

n  = S.length

for i = 1 to n

　　if Binary-Search( S, 1, n, x-A[ i ])   //参见2.3-2

　　　　return true

return false

Merge-Sort( S )

n  = S.length

i = 1

j = n

while( i<j )

　　if S[ i ] + S[ j ] == x

　　　　return true

　　elseif  S[ i ] + S[ j ]  > x

　　　　j = j – 1

　　else

　　　　i = i + 1

return false

思考题

2.1