Problem 1 (教材习题 4.1-4)
假定修改最大子数组问题的定义,允许结果为空数组,其和为 0 。你应该如何修改现有算法,使它们能允许空数组为最终结果?
Solution
算法描述如下:
Problem 2 (教材习题 4.1-5)
使用如下思想为最大子数组问题设计一个非递归的、线性时间的算法。从数组的左边界开始,由左至右处理,记录到目前为止已经处理过的最大子数组。若已知 A[1..j] 的最大子数组,基于如下性质将解扩展为 A[1..j+1] 的最大子数组: A[1..j+1] 的最大子数组要么是 A[1..j] 的最大子数组,要么是某个子数组 A[i..j+1](1≤i≤j+1) 。在已知 A[1..j] 的最大子数组的情况下,可以在线性时间内找出形如 A[i..j+1] 的最大子数组。
Solution
算法伪代码如下:
从第 5 到 15 行的 for 循环不难看出,该算法的运行时间为 Θ(n) ,这是一个线性时间的算法。
下面使用 循环不变式 来证明该算法的正确性,第 5 到 15 行的 for 循环的不变式为:每次循环开始前, A[p..q] 是 A[1..j−1] 的最大子数组, A[i..j−1] 是 A[1..j−1] 的最大后缀子数组。
初始化:在第一次迭代开始前,p=q=i=1,j=2 ,A[1] 显然是 A[1] 的最大子数组和最大后缀子数组,不变式显然成立。
保持:若迭代开始前,A[p..q] 是 A[1..j−1] 的最大子数组, A[i..j−1] 是 A[1..j−1] 的最大后缀子数组,
于是,下一次迭代开始前,A[p..q] 是 A[1..j] 的最大子数组, A[i..j] 是 A[1..j] 的最大后缀子数组。循环保持了不变式。
终止:最后一次迭代结束后, j=n+1 ,根据循环不变式, A[p,q] 是 A[1..n+1−1]=A[1..n] 的最大子数组。因此,算法 1 是正确的。
补充本题的洛谷模版题链接,读者可以自行编程并提交评测。
Problem 3 (教材习题 4.2-2)
为 Strassen 算法编写伪代码。
Solution
Problem 4 (教材习题 4.2-6)
用 Strassen 算法作为子过程来进行一个 kn×n 矩阵和一个 n×kn 矩阵的乘法,最快需要花费多长时间? 对于两个输入矩阵规模互换的情况,回答相同的问题。
Solution
考虑分块矩阵的乘法。记
A=⎣⎢⎢⎢⎢⎡A1A2⋮Ak⎦⎥⎥⎥⎥⎤,B=[B1B2…Bk]
其中, Ai 和 Bj 都是 n×n 的矩阵。
A⋅B=⎣⎢⎢⎢⎢⎡A1B1A2B1⋮AkB1A1B2A2B2⋮AkB2……⋱…A1BkA2Bk⋮AkBk⎦⎥⎥⎥⎥⎤,B⋅A=[i=1∑kAiBi]
其中,每次乘法需要 Θ(nlog7) (Strassen 算法),每次加法需要 Θ(n2) (平凡算法)。
所以不难看出 A⋅B 的运行时间为 Θ(k2nlog7) ,B⋅A 的时间为 Θ(knlog7) 。
Problem 5 (教材习题 4.2-7)
设计算法,仅使用三次实数乘法即可完成复数 a+bi 和 c+di 相乘。算法需接收 a,b,c,d 作为输入,分别生成实部 ac−bd 和虚部 ad+bc 。
Solution
考虑如下两个等式:
ac−bd=ac+bc−bc−bd=(a+b)c−b(c+d)ad+bc=ad−bd+bd+bc=(a−b)d+b(c+d)
我们只需要计算三次乘积 P1=(a+b)c,P2=b(c+d),P3=(a−b)d 即可分别生成实部 ac−bd=P1−P2 和虚部 ad+bc=P2+P3 。