介绍
CLRS学习第三=四章，分治策略~
4.1 最大子数组问题
- 分治法解最大子数组
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = -INFINITE
sum = 0
for i = mid down to low
sum = sum + A[i]
if sum > left-sum
left-sum = sum
max-left = i
right-sum = -INFINITE
sum = 0
for j = mid + 1 to high
sum = sum + A[j]
if sum > right-sum
right-sum = sum
max-right = j
return (max-left, max-right, left-sum + right-sum)
FIND-MAXIMUM-SUBARRAY(A, low, high)
if high == low
return (low, high, A[low])
mid = (low + high) // 2
(left-low, left-high, left-sum) =
FIND-MAXIMUM-SUBARRAY(A, low, mid)
(right-low, right-high, right-sum) =
FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
(cross-low, cross-high, cross-sum) =
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
if left-sum >= right-sum and left-sum >= cross-sum
return (left-low, left-high, left-sum)
elif right-sum >= left-sum and right-sum >= cross-sum
return (right-low, right-high, right-sum)
else return (cross-low, cross-high, cross-sum)
- 练习4.1-1 当A的所有元素为负数时，FIND-MAXIMUM-SUBARRAY返回什么？
返回1，1，A[1]
- 练习4.1-2 对最大子数组问题编写暴力求解伪代码，时间$\Theta(n^2)$
FIND-MAXIMUM-SUBARRAY-BRUTE-FORCE(A)
max-sum = -INFINITE
max-left = 1
max-right = 1
for i = 1 to length(A)
s = 0
for j = i to length(A)
s = s + A[j]
if s > max-sum
max-sum = s
max-left = i
max-right = j
return (max-left, max-right, max-sum)
- 练习4.1-3 将递归算法n较小时改为暴力算法，性能交叉点会改变吗？
修改后就没有性能交叉点了……永远是递归胜出。
- 练习4.1-4 如何修改现有算法使其能允许空数组作为最终结果。
if max(left-sum, right-sum, cross-sum) <= 0
return (0, 0, 0)
- 练习4.1-5 为最大子数组问题设计非递归线性时间算法。
FIND-MAXIMUM-SUBARRAY-LINEAR(A)
max1 = -INFINITE
max2 = -INFINITE
left1 = 0
right1 = 0
left2 = 0
for i = 1 to length(A)
if max2 <= 0
max2 = A[i]
left2 = i
if max2 > max1
max1 = max2
left1 = left2
right1 = i
return (left1, right1, max1)
4.2 矩阵乘法的Strassen算法
- 暴力解法
SQUARE-MATRIX-MULTIPLY(A, B)
n = A.rows
let C be a new n * n matrix
for i = 1 to n
for j = 1 to n
c[i][j] = 0
for k = 1 to n
c[i][j] += a[i][k] * b[k][j]
return C
- Strassen方法
T(n) = 7T(n/2) + $\Theta(n^2)$
- 练习4.2-1 使用Strassen算法计算如下矩阵乘法: [1,3;7,5] * [6,8;4,2]
下面一题有伪代码
- 练习4.2-2 为Strassen算法编写伪代码
……too easy……
- 练习4.2-3 如何修改strassen算法,使之适应矩阵规模不是2的幂的情况？而且时间复杂度不变。
添加全是0的行列，到规模是2的幂为止。
- 练习4.2-4 如果可以用k次乘法操作（假定乘法的交换律不成立）完成两个3×3矩阵相乘，那么你可以在Θ(n^log7)时间内完成n×n矩阵相乘，满足这一条件的最大的k是多少？此算法的运行时间是怎么样的？
T(n) = kT(n/3) + Θ(n^2)
最大的k是21
- 练习4.2-5 V.Pan发现一种方法，可以用132464次乘法操作完成68x68的矩阵相乘，发现另一种方法，可以用143 640次乘法操作完成70x70的矩阵相乘，还发现一种方法，可以用155 424次乘法操作完成72x72的矩阵相乘。当用于矩阵相乘的分治算法时，上述哪种方法会得到最佳的渐进运行时间？与Strassen算法相比，性能如何？
a = lg(132464)/lg(68) = 2.7951284873613815
b = lg(143640)/lg(70) = 2.795122689748337
c = lg(155424)/lg(72) = 2.795147391093449
lg(7) = 2.807354922057604
第二种最佳，都比Strassen好一点，但可能有其他因素的影响
- 练习4.2-6 用Strassen算法作为子进程来进行一个kn X n矩阵和一个nXkn的矩阵相乘，最快需要花费多长时间？对两个输入矩阵规模互换的情况，回答相同的问题。
先补成kn * kn, 再补成2的幂，规模互换不影响。
- 练习4.2-7 设计算法，仅使用三次实数乘法即可完成复数a+bi和c+di相乘。算法需接受a、b、c和d为输入，分别生成实部ac-bd和虚部ad+bc。
x = (a+b)(c-d) = ac+bc-ad-bd
y = bc
z = ad
ac - bd = x + y + z
ad + bc = y + z
用代入法求解递归式
猜测解的形式 用归纳法证明
-
练习4.3-1 证明：T(n) = T(n-1) + n的解为$O(n^2)$.
猜测$T(n-1) <= cn^2 $
$T(n) <= c(n-1)^2+n$
$ = cn^2 + c + (1-2c)n$
$ < cn^2$
当 $c + (1-2c)n < 0$
$即c>1$时就成立
