算法设计与分析学习笔记3
蛮力法
1、对 f(n)=n, 并且 a=b 的情况，证明递归方程 T(n)=aT(n/b)+f(n) 的解为O(nlogn).
证明：由 f(n)=n, f(n)∈θ(n^d^ ),得 d=1
又 a = b，即要求我们证明 T(n) ∈ θ(n logn )。不失一般性， 假定 n 为 a 的整幂，
即存在正整数 k，使得 n = a^k^ 。同时假定 T(1) 为常数，当 n > 1 时， 则：
T(n)= aT(n/a)+ n
= a(aT(n/a^2^)+n/a)+n
= a^2^T(n/a^2^)+2n
=a^k^T(n/a^k^)+kn
因为 a^k^ = n，所以 k =log(a)n，于是 T(n) = nT(1)+nlog(a)n， 从而 T(n)∈ θ(n logn )。
2、设计求解 n 个数字之和的分治算法，给出伪代码描述并分析算法的计算复杂度（每次分为 2 个子问题）。
解：
算法思想：将 n 个待相加的元素分割成 2 个大致相等的子集合 A、B；对每一个子集合分别递归求和；再将每个子集的和相加。当 n 等于 1 时递归终止，此时所求之和为该元素自身。
算法的形式化描述如下：
Algorithm Sum (A[0 ... n-1])
//输入：n 个数字
//输出：n 个数字的和
if n>1 then
sum = Sum(A[0…⌊n/2⌋-1)+Sum(A[⌊n/2⌋…n-1]);
return sum
else return A[0]时间复杂度分析：设 T(n) 为算法计算 n 个数字之和所花费的基本运算次数。此时的基本运算为加法。显然，当 n=1 时，T(n)=0; n>1 时，不失一般性，假设n=2^k^ ，其中 k 为某个正整数， 则
T(n) = 2T(n/2)+1
= 2[2*T(n/2^2^)+1]+1
= 2^2^ *T(n/2^2^)+2+1
= 2^2^[2*T(n/2^3^ )+1]+2+1
= 2^3^ * T(n/2^3^ )+4+2+1
= …
= 2^k^ *T(1)+...+4+2+1
= 2^k^ -1
=n-1
因此算法的计算复杂度为Θ(n)。
3、假设 R 与 S 分别为具有 r 个与 s 中 个元素的有序表，其中 s ≤ r/log r . 设计一个最坏情况下 O( r) 时间的算法， 将 R 与 S 合并成一个有序表.
解：假设有序表 R 由 a_ 1 , a_ 2 , ..., a_ r 构成，记作 R=(a_ 1 , a_ 2 , ..., a_ r )，其中a_i<=a_i+1 ,0<i<r。
同时假设有序表 S 由 b_ 1 , b_ 2 , ..., b_ s 构成，记作 S=(b_ 1 , b_ 2 , ..., b_ s )，其中b_ j<=b_ j+1，0<j<s。
算法思想如下：
将 b_ 1 , b_ 2 , ..., b_ s 依次插入到有序表 R 中。对于元素 b_ j , 在 R 上使用二分查找
方法，找到b_ j所要插入的位置。假设b_ j插入后的状态为
a_ 1 , a_ 2 , ..., a_ k , b_ j , a_ k+1 , a_ k+2 , ..., a_ r ，
由于b_ j<=b_ j+1，则将b_ j+1插入 R 时的工作可在有序子序列 a_ k+1 , a_ k+2 , ..., a_ r 上进行，从而对 S 中的每个元素在 R 上实施二分查找插入方法的序列长度始终不超过 r。
根据二分查找算法的复杂度为O(log r)，得知归并 R 与 S 的算法复杂度为O(s * log r) 由于 s <= r/log r , 可得算法复杂度为O( r)。
算法形式化描述如下：
令 Binsearch( b_ i , Temp)为一个函数过程，能够在有序表 Temp 上使用二分查找方
法返回b_ i 应该被插入的位置 k ，算法可形式化描述为：
Algorithm Merger (R, S)
Begin
1. Temp := R;
2. for i := 1 to s do
2.1. k := Binsearch(b i , Temp);
2.2. 将 b i 插入到 R 中，并更新 R ;
2.3. Temp := (a_ k+1 , a_ k+2 , ..., a_ r );
end of for;
3. return(R);
end复杂度分析：
算法的基本操作为元素之间的比较。由于 Temp 的长度始终不超过r ，因此步骤 2.1 总能在 O(log r) 时间内完成。由于s<= r/log r ，从而步骤 2 的开销为 slog r <= (r/log r)log r<=r，所以整个算法的复杂度为O( r ) 。
4、给定长度为 n 的表，表中的所有元素已构成 k 个有序段， 设计一个计算复杂度为 O(n log k) 的算法完成对表元素的排序。 给出算法的形式化描述与复杂度分析。
解：假定 k 个有序段依次为 L_ 1 ，L_ 2 ，...，L_ k ，其中每个 L_ i 的长度为 l_ i ，1≤i≤k，则l_ 1 +l_ 2 +...+l_ k = n.
算法思想为：
将这 k 个有序段进行两两合并，生成⌈k/2⌉个有序段；并连续使用这种有序段归并方法，将⌈k/2⌉个有序段归并为⌈k/2^2^⌉个有序段，直到将最后所剩的两个有序段归并成最终的一个有序段。
令 A={L_ 1 ，L_ 2 ，...，L_ k }, merge（B，C，A）为将集合 B 与 C 合并成有序集
合 A 的过程，其复杂度为 O（|B|+|C|)，即以 B 与 C 的所有元素个数为上界。
算法的形式化描述如下：
Algorithm Sort（A）
begin
If k = 1 then return（A）
else begin
1. m = ⌈k/2⌉;
2. B = {L_ 1 ，L_ 2 ，...，L_ m };
3. C :={L_ m+1 ，L_ m+2 ，...，L_ k };
4. Sort(B);
5. Sort(C);
6. Merge(B，C，A);
end;
end.算法复杂度分析：
由于有序段个数为 k，从而递归的深度为 O（log k）。而在每个递归层算法总要完成当前层所有子序列的两两归并，共计花费 O（n）次比较。所以算法的
复杂度为 O（n log k）。
查看23道真题和解析
