算法导论阅读笔记2-分治算法

2018-09-20 本文已影响10人二进制研究员

分治算法的三个主要步骤：

分：将问题划分为数个子问题，每个子问题是该问题的更小实例。
治：通过递归迭代处理子问题。然而，如果子问题的规模足够小，直接处理子问题。
组合：组合子问题的解构成原始问题的解。

求解递归表达式（如T(n) = 2T(n/2) + θ(n)）的三种方法：

替代法：猜测表达式的界，并使用数学归纳法证明猜测的准确性；
递归树方法
主方法：给出如下格式的递归表达式的界T(n) = aT(n/b) + f(n)，其中a≥1, b>1, 且f(n)为给定函数。

最大子数组问题（maximum subarray problem）

最大子数组问题只有在数组中存在负值时才有意义。否则，整个数组是最大子数组。

问题描述

给定数组A，寻找A的和最大的非空连续子数组。

解决方法

假定我们要寻找子数组A[low..high]的最大子数组。使用分治技术意味着将子数组划分为两个规模尽量相等的子数组，即找到数组的中心位置，比如mid。然后，考虑求解两个子数组A[low..mid]和A[mid + 1..high]。如图所示，A[low..high]的任何连续子数组A[i..j]所处的位置必然是以下三种情形之一。

完全位于子数组A[low..mid]中，因此low≤i≤j≤mid。
完全位于子数组A[mid+1..high]中，因此mid+1≤i≤j≤high。
跨越中心点，因此low≤i≤mid≤j≤high。

子数组的可能位置

因此，我们可以递归的求解A[low..mid]和A[mid + 1..high]的最大子数组。剩下的问题是寻找跨越中心点位置的最大子数组。然后，选取三种情况中的和最大者。

任何跨越中心点的子数组都由两个子数组A[i..mid]和A[mid+1..j]组成。因此，我们只需找出A[i..mid]和A[mid+1..j]的最大子数组，然后将其合并即可。

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = -INF
sum = 0
for i = mid downto low
  sum = sum + A[i]
  if sum > left-sum
    left-sum = sum
    max-left = i
right-sum = -INF
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])
else mid = (low+high)/2
  (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
  (right-low, rigth-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)
  elseif right-sum >= left-sum and right-sum >= cross-sum
    return (right-low, right-high, right-sum)
  else
    return (cross-low, cross-high, cross-sum)

c代码

struct result {
  int left;
  int right;
  int sum;
};
struct result find_max_crossing_subarray(int *a, int low, int mid, int high) {
  int left_sum = INT_MIN;
  int sum = 0
  int max_left = -1;
  for(int i = mid; i >= low; i--) {
    sum = sum + a[i];
    if (sum > left-sum) {
      left_sum = sum;
      max_left = i;
    }
  }
  int right_sum = INT_MIN
  sum = 0
  int int max_right = -1;
  for (int j = mid + 1; j <= high; j++) {
    sum = sum + a[j];
    if (sum > right_sum) {
      right_sum = sum;
      max_right = j;
    }
  }
  struct result res;
  res.left = max_left;
  res.rigth = max_right;
  res.sum = left_sum + right_sum;
  return res;
}

struct result find_maximum_subarray(int *a, int low, int high) {
  struct result res;
  if (high == low) {
    res.left = low;
    res.right = high;
    res.sum = a[low];
    return res;
  }
  else {
    int mid = (low+high)/2
    struct result res1 = find_maximum_subarray(a, low, mid);
    struct result res2 = find_maximum_subarray(a, mid+1, high);
    struct result res3 = find_max_crossing_subarray(a, low, mid, high);
    if (res1.sum >= res2.sum && res1.sum >= res3.sum) {
      return res1;
    }
    elseif (res2.sum >= res1.sum && res2.sum >= res3.sum) {
      return res2;
    }
    else
      return res3;
  }
}

算法特性

时间复杂度为θ(nlgn)。

矩阵乘法的Strassen算法

按照矩阵乘定义进行计算

SQUARE-MATRIX-MULTIPLY(A, B)
n = A.row
let C be a new n*n matrix
for i = 1 to n
  for j = 1 to n
    cij = 0
    for k = 1 to n
      cij = cij + aij * bij
return C

时间复杂度为θ(n³)。

直观分块算法

矩阵分块

矩阵分块乘法

矩阵分块乘法计算公式

伪代码

SQUARE-MATRIX-MULTIPLY-RECURSIVE(A,B)
n = A.rows
let C be a new n*n matrix
if n == 1
  c11 = a11*b11
else partition A, B, and C
  C11 = SQUARE-MATRIX-MULTIPLY_RECURSIVE(A11, B11)
      + SQUARE-MATRIX-MULTIPLY_RECURSIVE(A12, B21)
  C12 = SQUARE-MATRIX-MULTIPLY_RECURSIVE(A11, B12)
      + SQUARE-MATRIX-MULTIPLY_RECURSIVE(A12, B22)
  C21 = SQUARE-MATRIX-MULTIPLY_RECURSIVE(A21, B11)
      + SQUARE-MATRIX-MULTIPLY_RECURSIVE(A22, B21)
  C22 = SQUARE-MATRIX-MULTIPLY_RECURSIVE(A21, B12)
      + SQUARE-MATRIX-MULTIPLY_RECURSIVE(A22, B22)
return C

T(n) = 8T(n/2) + θ(n²)
时间复杂度为θ(n³)

Strassen算法

核心思想是令递归树稍微不那么浓密，即只递归7次而不是8次n/2xn/2矩阵的乘法。减少一次矩阵乘法带来的代价可能是额外几次n/2xn/2矩阵的加法，但只是常数次。
该算法包含4个步骤：

将输入矩阵A、B和输出矩阵C分解为n/2xn/2的子矩阵。此步骤花费θ(1)时间，与SQUARE-MATRIX-MULTIPLY-RECURSIVE相同。
创建10个n/2xn/2的矩阵S₁, S₂, ..., S₁₀，每个矩阵保存步骤1中创建的两个子矩阵的和或差。花费时间为θ(n²)。
用步骤1中创建的子矩阵和步骤2中创建的10个矩阵，递归地计算7个矩阵积P₁, P₂, ..., P₇。每个矩阵P_i都是n/2xn/2的。
通过P_i矩阵的不同组合进行加减运算，计算出结果矩阵C的子矩阵C₁₁, C₁₂, C₂₁, C₂₂。花费时间θ(n²)。
递归式：T(n) = 7T(n/2) + θ(n²)。
时间复杂度: T(n) = θ(n^lg7)（笔者注：O(n^2.81))

算法步骤

在步骤2中，创建如下10个矩阵
S₁ = B₁₂ - B₂₂
S₂ = A₁₁ + A₁₂
S₃ = A₂₁ + A₂₂
S₄ = B₂₁ - B₁₁
S₅ = A₁₁ + A₂₂
S₆ = B₁₁ + B₂₂
S₇ = A₁₂ - A₂₂
S₈ = B₂₁ + B₂₂
S₉ = A₁₁ - A₂₁
S₁₀ = B₁₁ + B₁₂

在步骤3中，递归地计算7次n/2xn/2矩阵的乘法，如下所示：
P₁ = A₁₁xS₁
P₂ = S₂xB₂₂
P₃ = S₃xB₁₁
P₄ = A₂₂xS₄
P₅ = S₅xS₆
P₆ = S₇xS₈
P₇ = S₉xS₁₀

步骤4：
C₁₁ = P₅ + P₄ - P₂ + P₆
C₁₂ = P₁ + P₂
C₂₁ = P₃ + P₄
C₂₂ = P₅ + P₁ - P₃ - P₇

主定理

令a≥1和b>1是常数，f(n)是一个函数，T(n)是定义在非负整数上的递归式：T(n) = aT(n/b) + f(n)
其中我们将n/b解释为 $\lfloor{n/b}\rfloor$ 或 $\lceil{n/b}\rceil$ 。那么，T(n)有如下渐进界:

若对某个常数 $\epsilon>0$ 有 $f(n)=O(n^{log_{b}a-\epsilon})$ ，那么 $T(n) = \Theta(n^{log_{b}a})$ 。
若 $f(n)=O(n^{log_{b}a})$ ，那么 $T(n) = \Theta(n^{log_{b}a}lgn)$ 。
若对某个常数 $\epsilon>0$ 有 $f(n)=\Omega(n^{log_{b}a+\epsilon})$ ，且对某个常数 $c<1$ 和所有足够大的n有 $af(n/b) \le cf(n)$ ，则 $T(n) = \Theta(f(n))$ 。