分治策略

本文包括

1. 分治的基本概念
2. 二分查找
3. 快速排序
4. 归并排序
5. 找出伪币
6. 棋盘覆盖
7. 最大子数组

源码链接：https://github.com/edisonleolhl/DataStructure-Algorithm/tree/master/Divede-and-conquer

分治的基本概念

• 在排序算法中有种算法叫做归并排序，它采用了分治策略，在策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：

  • 分解(Divide)步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
  • 解决(Conquer)步骤递归地求解出子问题，如果子问题的规模足够小，则停止递归，直接求解。
  • 合并(Combine)步骤将子问题的解组合成原问题的解。

• 当子问题足够大时，需要递归求解，我们称之为递归情况(recursive case)。

• 当子问题足够小，不需要递归求解时，我们称之为“触底”，进入了基本情况(base case)。

• 很多时候，问题看上去并不是一目了然的，能否用分治策略，可以取决于问题是否满足以下四条特征：

  • 该问题的规模缩小到一定的程度就可以容易地解决；
  • 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
  • 利用该问题分解出的子问题的解可以合并为该问题的解；
  • 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

• 递归式（recurrence）就是一个等式或者不等式，比如归并排序的最坏情况运行时间：

         { θ(1)             若 n=1
    T(n)=|
         { 2T(n/2)+θ(n)     若 n>1
  

  求解可得 T(n)=θ(nlogn)

二分查找

• 我们先看个简单的例子，二分查找，假设我们想要查找 x 是否存在于已排序列 a[] 中。

百度百科：如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：比较x和L中任意一个元素L[i]，若x=L[i]，则x在L中的位置就是i；如果x<L[i]，由于L是递增排序的，因此假如x在L中的话，x必然排在L[i]的前面，所以我们只要在L[i]的前面查找x即可；如果x>L[i]，同理我们只要在L[i]的后面查找x即可。无论是在L[i]的前面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。很显然此问题分解出的子问题相互独立，即在L[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。

• 二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较。

  • 如果x=a[n/2],则找到x,算法中止；
  • 如果x<a[n/2],则只需要在 a[] 的左半部分继续搜索 x；
  • 如果x>a[n/2],则只需要在 a[] 的右半部分继续搜索 x。

• 容易理解，时间复杂度无非就是迭代的次数，O(logn)

• 利用 while 循环的伪代码：

    BinarySearch(max,min,des)
        mid-<(max+min)/2
        while(min<=max)
            mid=(min+max)/2
            if mid=des then
                return mid
            elseif mid >des then
                max=mid-1
            else
                min=mid+1
        return
  

• 利用迭代的 Python 代码：

    def binary_search(A, x, low, high):
        if low == high:
            return -1
        mid = (low + high) // 2
        if A[mid] == x:
            return mid
        result_left = binary_search(A, x, low, mid)
        print("left", result_left)
        result_right = binary_search(A, x, mid+1, high)
        print("right", result_right)
        if result_left != -1:
            return result_left
        elif result_right != -1:
            return result_right
        else:
            return -1
  
    A = list(range(10))
    print(binary_search(A, 3, 0, len(A)-1))
  

• 输出

    left -1
    right -1
    left -1
    right -1
    left -1
    right 3
    left 3
    left -1
    right -1
    left -1
    right -1
    left -1
    left -1
    right -1
    right -1
    right -1
    3
  

快速排序

• 快速排序的基本思想是基于分治法的

• 对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：

  • 分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
  • 递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
  • 合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。

• 这个解决流程是符合分治法的基本步骤的，因此，快速排序法是分治法的经典应用实例之一。

• 详情见之前写的排序算法：http://www.jianshu.com/p/7cb29ad6d0f7

归并排序

• 也是分治策略的典型应用，具体见排序算法，文章了链接同上。

x^n

• 输入 x 与 n，求 x^n

• 最朴素的方法就是把 x 连乘 x,这样需要时间复杂度为 Θ(n)

• 但是如果把计算式分解成奇数和偶数的情况，时间复杂度降为 Θ(logn)

    x^n = x^(n/2) × x^(n/2)  当 n 为偶数
          x^(n-1/2) × x^(n-1/2) ×  当 n 为奇数
  

找出伪币

• 给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。

• 可以想到，一个很简单的方法就是暴力枚举法：

  • 比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。

  • 假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并能够找出这一伪币。

• 另外一种方法就是利用分而治之的方法：

  • 假如把16硬币的例子看成一个大的问题。

  • 第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把16个硬币的问题分成两个8硬币的问题来解决。

  • 第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在，此时直接结束算法。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中，然后继续把较轻组的硬币继续划分为两组，放在仪器中比较重量。一直这样迭代下去，直至两枚硬币比较，较轻的那枚就是伪币。

• 当然，如果硬币数量为奇数的话就不能这么简单了，但是这里只是为了体现分治的思想，所以先用偶数说明概念。

棋盘覆盖

• 问题描述：在一个 2^k×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

  

• 分析：

  • 当 k>0 时，将 2^k×2k 棋盘分割为 4 个 2^(k-1)×2(k-1) 的 子棋盘，如下图 a 所示。

  • 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

    

• 实现：每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角（top left coner）方格的行列坐标，然后再与特殊方格坐标进行比较，就可以知道特殊方格是否在该块中。如果特殊方块在里面，这直接递归下去求即可，如果不在，则根据分割的四个方块的不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继续递归。这样我们就按照要求填充了整个棋盘。

最大子数组

• 题目描述：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。设计一种算法求出输入数组的最大子数组以及对应的子数组和是多少。

• 例如输入的数组为

    13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7
  

  那么最大的子数组为

    18,20,-7,12
  

  因此输出该子数组

    43, 7, 10
  

解法一：暴力求解

• 两个 for 循环，时间复杂度 O(n^2)

• 思路：

• 代码：

  def di_cal_wrong(A):
      max_sub_sum = -float('inf')  # init
      for i in range(len(A)):
          for j in range(i+1, len(A)):
              if sum(A[i:j+1]) > max_sub_sum:
                  max_sub_sum = sum(A[i:j+1])
                  low = i
                  high = j
      return(max_sub_sum, low, high)
  
  A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
  print(di_cal(A))
  

• 输出：

  (43, 7, 10)
  

• 思考：上述代码有错吗？

• Python 列表的切片操作，如果放在类似于 Java 、C 之类的语言中，想要实现的话得通过 for 循环然后依次累加，这时岂不是3个 for 循环嵌套了？

• 更正：每当 j 增加1后，令 sum = sum + A[J]，然后再比较 sum 是否小于 max_sub_sum，这样就实现了两次 for 循环嵌套。

• 更正后的代码：

  def di_cal(A):
      sum = A[0]
      max_sub_sum = -float('inf')  # init
      for i in range(len(A)):
          sum = A[i]
          for j in range(i+1, len(A)):
              sum += A[j]
              if sum > max_sub_sum:
                  max_sub_sum = sum
                  low = i
                  high = j
      return(max_sub_sum, low, high)
  

• 利用 timeit 模块测试两个函数的性能

  print(di_cal_wrong(A))
  print(di_cal(A))
  
  t1 = Timer("di_cal([13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7])", "from __main__ import di_cal")
  print("di_cal ", t1.timeit(number=1000), "seconds")
  
  t1 = Timer("di_cal_wrong([13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7])", "from __main__ import di_cal_wrong")
  print("di_cal_wrong ", t1.timeit(number=1000), "seconds")
  

• 输出

  (43, 7, 10)
  (43, 7, 10)
  di_cal  0.017742687098883683 seconds
  di_cal_wrong  0.05528770369116012 seconds
  

• 可以看到，很明显 di_cal_wrong(A) 代码的性能要差于 di_cal(A)，所以实现算法时一定要细心，Python 容易使用，但是不能把集成好的功能当作基本操作来使用。

解法二：分治策略

• 假定我们要寻找 A[low..high] （假设 low<high）的最大子数组，使用分治策略意味着要将这个数组分解为两个规模尽量相等的子数组，即找到中央位置：mid=(low+high)/2。

• 然后分解为两个子数组：A[low..mid]，A[mid+1..high]

• 可以想象，A[low..high] 的最大子数组必然是以下三种情况之一

  • 完全位于左边子数组中 A[low,mid] 中，此时可以解可以表示为：A[i..mid]
  • 完全位于右边子数组中 A[mid,high] 中，此时可以解可以表示为：A[mid+1..high]
  • 跨越了中点，此时解可以表示为 A[i..mid]+A[mid+1..j]

• 这样，在任何情况下，一个问题可以分为3个子问题，我们可以递归地求解 A[i..mid] 与 A[mid+1..high]，因为这两个子问题仍然是最大子数组问题，只是规模缩小了一半而已。

• 因此我们先解决第三种情况：

  • 以 mid 为中心，向左向右依次找最大子数组，这个时候只需要线性时间就可以找到了

  • find_max_crossing_subarray：

    def find_cross_suming_subarray(A, mid, low, high):
        # 最大子数组横跨中点，所以最大子数组的左边是A[i..mid],右边是A[mid+1..j]
        # 求 A[i..mid] 可以直接用暴力求解法，从 mid 开始从左依次相加，判断一下，然后赋值即可，求 A[mid+1..j] 是同样的方法
        left_sum, right_sum = 0, 0
        max_left_sum, max_right_sum = -float('inf'), -float('inf')
        # 注意 range(start,stop,step)，包括start，不包括stop，所以对应的low-1 与 high+1
        for i in range(mid, low-1, -1):
            left_sum += A[i]
            if left_sum > max_left_sum:
                max_left_sum = left_sum
                low = i
        for j in range(mid+1, high+1, 1):
            right_sum += A[j]
            if right_sum > max_right_sum:
                max_right_sum = right_sum
                high = j
        return max_right_sum+max_left_sum, low, high
    

  • 有了第三种情况的处理，接下来可以编写递归的函数了，注意要在开头判断跳出递归的条件：

    def divide_and_conquer(A, low, high):
        if low == high:
            return A[low], low, high
        mid = (low + high) // 2
    
        left_sum, left_low, left_high = divide_and_conquer(A, low, mid)
        print("left:", left_sum, left_low, left_high)
        right_sum, right_low, right_high = divide_and_conquer(A, mid+1, high)
        print("right:", right_sum, right_low, right_high)
        cross_sum, cross_low, cross_high = find_cross_suming_subarray(A, mid, low, high)
        print("cross:", cross_sum, cross_low, cross_high)
    
        if left_sum > right_sum and left_sum > cross_sum:
            return left_sum, left_low, left_high
        elif right_sum > left_sum and right_sum > cross_sum:
            return right_sum, right_low, right_high
        else:
            return cross_sum, cross_low, cross_high
    

  • 注意到递归后每次的结果都输出到控制台上，在处理递归问题时，我发现 log 比 debug 代码要容易理解得多了，有兴趣的朋友可以一步一步看看是怎么样输出的

    left: 13 0 0
    right: -3 1 1
    cross: 10 0 1
    left: 13 0 0
    left: -25 2 2
    right: 20 3 3
    cross: -5 2 3
    right: 20 3 3
    cross: 5 0 3
    left: 20 3 3
    left: -3 4 4
    right: -16 5 5
    cross: -19 4 5
    left: -3 4 4
    left: -23 6 6
    right: 18 7 7
    cross: -5 6 7
    right: 18 7 7
    cross: -21 5 7
    right: 18 7 7
    cross: 17 3 4
    left: 20 3 3
    left: 20 8 8
    right: -7 9 9
    cross: 13 8 9
    left: 20 8 8
    left: 12 10 10
    right: -5 11 11
    cross: 7 10 11
    right: 12 10 10
    cross: 25 8 10
    left: 25 8 10
    left: -22 12 12
    right: 15 13 13
    cross: -7 12 13
    left: 15 13 13
    left: -4 14 14
    right: 7 15 15
    cross: 3 14 15
    right: 7 15 15
    cross: 18 13 15
    right: 18 13 15
    cross: 16 8 15
    right: 25 8 10
    cross: 43 7 10
    (43, 7, 10)
    

解法三：联机算法

• 《算法导论》中的练习4.1-5提供了一种更快速地解决最大子数组的算法

• 从数组的左边界开始，从左往右处理，记录到目前为止已经处理过的最大子数组。

• 假设我们已经知道了 A[1..j] 的最大子数组，那么往右处理时，可以遵从如下性质：

  • 数组 A[1...j+1] 的最大子数组，有两种情况：

    • A[1...j] 的最大子数组

    • A[i...j+1]

• 那么如何求得 A[i...j+1] 呢？

  • 首先不难想通：如果一个数组 a[1..r] 求和得到负值，那么下一次往右处理时，可以直接把之前的记录全部清空，因为下次操作时的 a[r+1]，还不如直接把自己当作解（至少起点要从这里开始），因为 a[1..r]+a[r+1]<a[r+1]。

  • 所以只要某次操作时，求和为负，那么直接把和清0，重新计算最大子数组，并且把起点设置为下一个要操作的序数。

  • 代码：

    def linear_time(A):
        sum, max_sub_sum, low, high, cur = 0, 0, 0, 0, 0
        for i in range(0, len(A)):
            sum += A[i]
            if sum > max_sub_sum:
                max_sub_sum = sum
                # 起点从0开始，从左往右操作
                low = cur
                high = i
            # 每当和小于0时，丢弃之前处理过的所有记录，最大和清0，并且起点从下一位开始
            if sum < 0:
                sum = 0
                cur = i + 1
        return max_sub_sum, low, high
    

• 在网上查阅了许久，上述解法应该属于联机算法，不过挺容易理解的，并且时间复杂度的确是 O(n)，常量空间，不需要辅助空间进行，非常快。

百度百科：联机算法是在任意时刻算法对要操作的数据只读入（扫描）一次，一旦被读入并处理，它就不需要在被记忆了。而在此处理过程中算法能对它已经读入的数据立即给出相应子序列问题的正确答案。

解法四：动态规划

• 这种解法同样可以实现线性时间复杂度

• 假设有一个数组a[1..n]，若记 b[i] 为：以 a[i] 结尾的子数组的最大和，即

    b[i]=max{sum(a[j~k])}, 其中0<=j<=i，j<=k<=i。
  

• 因此对于数组 a[0..n] 的最大子数组的和为

    max{b[0], b[1], b[2], .., b[n]}
  

  即求 b[] 的最大值

• 由 b[i] 的定义可易知

    当 b[i-1]>0 时，b[i]=b[i-1]+a[i]
    否则 b[i]=a[i]。
  

• 故b[i]的动态规划递归式为:

    b[i] = max(b[i-1]+a[i], a[i])，1<=i<=n
  

• 代码如下：

    def dp(A):
        low, high = 0, 0
        B = list(range(len(A)))
        B[0] = A[0]
        max_sub_sum = A[0]
        for i in range(1, len(A)):
            if B[i-1] > 0:
                B[i] = B[i-1] + A[i]
            else:
                B[i] = A[i]
                low = i
            if B[i] > max_sub_sum:
                max_sub_sum = B[i]
                high = i
        return max_sub_sum, low, high
  

感觉解法三、解法四很像，等到时候学习动态规划了，再来好好琢磨琢磨解法四的精髓。

找出数组中最大的两个数

参考视频：http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184_p1+sp/courseware/b64e822fe8bf4fc18e86a560087efebc/e794869faa9844528206ba3e9ab6b640/

我感觉视频中前两种方法有点点问题，把 A[0] 作为 x1， x2 的初值，有些刁钻的测试用例会有错误的输出，所以我把初值都改为了负无穷大，相应的，比较的次数会多一次，但是分析的思想没变。

• 输入：一个数组

• 输出：数组中的最大值 x1 以及次大值 x2

• 如果数组允许重复元素，那么必有 x1 > x2 ； 否则 x1 ≥ x2

  视频中期望的输出是 x1 ≥ x2，这样的要求放宽了限制，把 A[0] 作为 x1， x2 的初值似乎没毛病，但是为了深入思考，我决定严格限制输出，这样对编程思想的提高会有较大帮助。

• 方法一——暴力枚举法：

  • 第一趟循环找出数组的最大值 x1，n 次比较

  • 第二趟循环找出数组开头到最大值序号之间的次大值

  • 第三趟循环找出数组最大值的序号到最后之间的次大值，与上面加起来是 n-1 次比较

  • 大约需要经过 2n-1 次比较

    def max2_force(A):
        x1 = -float('inf')
        x2 = -float('inf')
        for i in range(len(A)):
            if A[i] > x1:
                x1 = A[i]
                j = i
        for i in range(j):
            if A[i] > x2:
                x2 = A[i]
        for i in range(j + 1, len(A)):
            if A[i] > x2:
                x2 = A[i]
        return x1, x2
    

• 方法二——暴力枚举法改进版：

  • 只有一趟循环，每次循环时，先把当前值与次大值比较，再进一步把次大值与最大值比较

  • 最好情况：每次比较都小于次大值，所以比较次数为 n

  • 最坏情况：每次比较都大于次大值，所以比较次数 2n

    def max2_force_improve(A):
        x1 = -float('inf')
        x2 = -float('inf')
        for i in range(len(A)):
            if A[i] > x2:
                x2 = A[i]
                if x2 > x1:
                    x1, x2 = x2, x1
        return x1, x2
    

• 方法三——分治法：

  • 时间复杂度：T(n) = 2*T(n/2) + 2 = 5n/3 - 2

    def max2_divide_and_conquer(A, low, high):
        if low == high:
            return A[low], A[low]
        elif low + 1 == high:
            if A[low] > A[high]:
                return A[low], A[high]
            else:
                return A[high], A[low]
        else:
            mid = (low + high) // 2
            x1_left, x2_left = max2_divide_and_conquer(A, low, mid)
            x1_right, x2_right = max2_divide_and_conquer(A, mid + 1, high)
            if x1_left > x1_right:
                if x2_left > x1_right:
                    return x1_left, x2_left
                else:
                    return x1_left, x1_right
            else:
                if x2_right > x1_left:
                    return x1_right, x2_right
                else:
                    return x1_right, x1_left