4. 分治策略

本着涉及更多的分治法相关的算法，以及分治法运行时间的分析方法。

递归式

递归式可以很自然的刻画分支算法的运行时间。
递归式通过更小的输入上的函数值来藐视一个函数。
下图为归并排序的递归式：

$T(n)=\left\{ \begin{aligned} & \Theta(1) & if \quad n=1, \\ & 2T(n/2) + \Theta(n) & if \quad n>1, \end{aligned} \right.$

求解递归式的方法

• 代入法
  猜测一个界，然后用数学归纳法证明这个界的正确性
• 递归树法
  将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
• 主方法 可求解形式如 $T(n) = aT(n/b) + f(n)$的递归式的界

涉及算法

点击查看实现

• 最大子数组
• 矩阵乘法

练习

4.1-1

1

返回最大的一个数组成的数组

4.1-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

FIND-MAXIMUM-SUBARRAY(A, n)
    low = 1
    high = 1
    sum = A[1]
    for i = 1 to n
        max_sum = A[i]
        tmp_sum = A[i]
        for j = i+1 to n
            tmp_sum += A[j]
            if tmp_sum > max_sum
                max_sum = tmp_sum
                tmp_low = i
                tmp_high = j
        if max_sum > sum
            sum = max_sum
            low = tmp_low
            high = tmp_high
    return (low, high, sum)

4.1-4

1

在比较left-sum, right-sum, cross-sum时，增加对0的比较，当0最大时，返回空数组