[算法导论][4]分治策略

1. 第4章 分治策略
   1. 4.1 最大子数组问题
      1. 4.1.1 问题描述
      2. 4.1.2 暴力求解方法
      3. 4.1.3 使用分治策略的求解方法
      4. 4.1.4 分治算法的分析

第4章 分治策略

• 在分治策略中，我们递归地求解一个问题，在每层递归中运用如下三个步骤

  1. 分解(Divide)：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小
  2. 解决(Comquer)：递归的求解出子问题，如果子问题的规模足够小，则停止递归，直接求解
  3. 合并(Combine)：将子问题的解组合成原问题的解

• 递归情况和基本情况

  • 当子问题足够大时，需要地柜求解，我们称之为递归情况(recursive case)
  • 当子问题变得足够小，不再需要递归时，我们说递归已经"触底"，进入基本情况(base case)

• 递归式

  • 一个递归式(recurrence)就是一个等式或不等式，它通过更小的输入上的函数值来描述一个函数
  • 例如
    
  • 三种求解递归式的方法
    • 代入法：我们猜测一个界，然后用数学归纳法证明其正确性
    • 递归树法：将递归式转换为一棵树，其节点表示不同层次的递归调用的代价，然后采用边界和技术求解
    • 主方法：可求解形如下式的递归式
      

---

4.1 最大子数组问题

4.1.1 问题描述

• 寻找一个数组的和最大的非空连续子数组，这样的数组我们称为最大子数组(maximum subarray)

• 注意：只有当数组中包含负数时，最大子数组问题才有意义。如果所有数组元素都是非负的，最大子数组问题没有任何难度，因为整个数组的和肯定是最大的

4.1.2 暴力求解方法

• 简单的尝试每对可能的{数组下标,数组上标},寻找最大值

• 时间复杂度:O(n₂),一共有(n-1)*n/2种情况

• 样例

  def find_maximum_subarray(A):
      low = 0
      high = 0
      max_val = float('-inf')
      for i in range(0, len(A)):
          for j in range(i, len(A)):
              sum = 0
              for s in range(i, j + 1):
                  sum += A[s]
              if sum > max_val:
                  max_val = sum
                  low = i
                  high = j
  
      return low, high, max_val
  
  
  if __name__ == '__main__':
      A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
      print(find_maximum_subarray(A))
  
  '''
  (7, 10, 43)
  '''

4.1.3 使用分治策略的求解方法

• 首先我们把数组 A[low..high] 划分为两个规模尽量相等的子数组: A[low..mid] 和 A[mid+1..high]

• A[low..high] 的任何连续子数组A[i..j]所处的位置必然是一下三种情况之一,如下图

  1. 完全位于子数组 A[low..mid] 中，因此 low<=i<=j<=mid
  2. 完全位于子数组 A[mid+1..high] 中，因此 mid<i<=j<=high
  3. 跨越了中点,因此 low<=i<=mid<j<=high
     

• 因此 A[low..high] 的一个最大子数组所处的位置必定是这三种情况之一.我们可以递归的求解 A[low..mid] 和 A[mid+1..high] 的最大子数组，因为这两个子问题仍然是最大子数组问题，只是规模更小.因此，剩下的问题就是寻找跨越中点的最大子数组,然后在三种情况中选取和最大者

• 我们可以很容易地使用线性时间(O(n))内求出跨越中点的最大子数组，算法如下

  def find_max_crossing_subarray(A, low, mid, high):
  """
  求解跨越了中点的最大子数组
  :param A: 数组
  :param low: 数组下标
  :param mid: 数组中点
  :param high: 数组上标
  :return:
  """
  print("find_max_crossing_subarray:", A, low, mid, high)
  
  # 这里需要考虑一种特殊情况,可以忽略但不影响逻辑理解
  if low == mid:
      return find_max_crossing_subarray_base_case(A, low)
  
  left_sum = float("-inf")
  sum = 0
  for i in range(mid, low - 1, -1):
      sum += A[i]
      if sum > left_sum:
          left_sum = sum
          max_left = i
  
  right_sum = float("-inf")
  sum = 0
  for i in range(mid + 1, high + 1):
      sum += A[i]
      if sum > right_sum:
          right_sum = sum
          max_right = i
  
  return max_left, max_right, left_sum + right_sum

• 有了一个线性的find_max_crossing_subarray在手，我们就可以设计求解最大子数组问题的分治算法了

  def find_maximum_subarray(A, low, high):
  """
  通过分治方法递归的求解最大子数组
  :param A: 数组
  :param low: 数组下标
  :param high: 数组上标
  :return:
  """
  print("find_maximum_subarray:", A, low, high)
  if low == high:
      return low, high, A[low]
  
  else:
  
      mid = int((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.4 分治算法的分析

• 接下来我们建立一个递归式来分析分治算法
  

• 最终可以求得时间复杂度为:O(nlgn)

---