风轻袖影翻

公众号：顾先生的数据挖掘

​关注他

16 人赞同了该文章

今天我们来讲一下分治算法，废话不多说了，我们开始吧！~！

 

在分支策略中，我们对一个问题求以下三步递归：

1. 分解：将问题分解为一些子问题，子问题和原问题形式一样，只是规模更小。
2. 解决：递归地求解子问题，如果子问题规模足够小，则停止递归，直接求解。
3. 合并：将子问题的解合并成原问题的解。

 

本文我会从一个求解最大子数组问题出发，进而介绍矩阵乘法的Strassen算法，最后再介绍三种求解递归的方式：代入法，递归树法，主方法。

最大子数组问题

我发现这个问题和leetcode的一道题目很像，我们就按照那题来作为例子吧！

 

121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

 

示例 1:

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

 

示例 2:

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

 

我们很容易得出一个暴力求解的方法来解决本问题：简单地尝试买入和卖出的时间组合，只要卖出在买入之前即可。所以运行时间也就是所有的日期组合，即O(n^2)。具体代码如下：

 

void MaxSubArraySum_Force(int arr[], vector<int> &subarr, int len)
{
if (len == 0):
return;
int nMax = INT_MIN;
int low = 0, high = 0;
for (int i = 0 , i <= len , i ++){
int nsum = 0
for (int j = i , j <= len , j ++){
nmax += arr[j]
if (nSum > nMax) {
                   nMax = nSum;
                   low = i;
                  high = j;
              }
          }
       }
       for (int i = low; i <= high; i ++) {
           subarr.push_back(arr[i]);
      }
   }

 

很明显，这样做有悖于我们的原则，那么我们可不可以把问题转个方向看待呢？

 

我们的目的是寻找一段日期，使得第一天到最后一天的净增变值最大。我们可以把第i天的数据改为第i-1天和第i天的价格差。如果将这一行新的数据看作数组A，那么问题就可以转换成寻找A和最大非空连续子数组。我们称这样的最大非空连续子数组为最大子数组。

 

那我我们得到了什么优化呢？

 

我们可以重新组织计算方式，利用之前计算出的子数组的和来计算出当前子数组的和，此时每一个子数组的和的时间复杂度为O(1)，而暴力求解的时间复杂度为O(n^2)。

 

然后我们用分治的策略来思考这个问题，使用分治思想意味着我们需要将数组尽可能地分成两个相同的数组。也就是说，求出数组的中央位置mid，然后考虑[low，mid]，[mid+1，high]两种情况。

 

显然，[low，high]的连续子数组[i……j]必然又以下三种情况：

1. 处于[low，mid]。
2. 处于[mid+1，high]。
3. 跨越了中点，所以low<=i<=mid<=j<=high。

 

第一、第二种情况还好处理，因为它本质上还是一个最大子数组的问题，只是规模更小，我们只需要将其递归求解即可。

 

关键是求解第三种情况，因为它加入了限制：必须包含中间位置 mid。因此，我们只需要找出[low，mid]，[mid+1，high]的最大子数组，然后将它们合并即可，条件是两个最大子数组都必须包含mid。我们直接上代码吧！~！

 

int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high)
 {
     const int infinite = -9999;
     int left_sum = infinite;
     int right_sum = infinite;
 
     int max_left = -1, max_right = -1;
 
     int sum = 0; //from mid to left;
     for (int i = mid; i >= low; i --) {
         sum += arr[i];
         if (sum > left_sum) {
             left_sum = sum;
             max_left = i;        
         }
     }
     sum = 0;  //from mid to right
     for (int j = mid + 1; j <= high; j ++) {
         sum += arr[j];
         if (sum > right_sum) {
             right_sum = sum;
             max_right = j;
         }
     }
     return (left_sum + right_sum);
 }
 
 int Find_Maximum_Subarray(int arr[], int low, int high)
 {
     if (high == low) //only one element;
         return arr[low];
     else {
         int mid = (low + high)/2;
         int leftSum = Find_Maximum_Subarray(arr, low, mid);
         int rightSum = Find_Maximum_Subarray(arr, mid+1, high);
         int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high);
 
         if (leftSum >= rightSum && leftSum >= crossSum)
             return leftSum;
         else if (rightSum >= leftSum && rightSum >= crossSum)
             return rightSum;
         else 
             return crossSum;
     }
   }

 

我们来看下时间复杂度吧，两个子问题的时间复杂度为2T(n/2)，而最后调用Find_Maximum_Subarray需要用到O(n)，所以得到运行时间为：

T(n) = O(1)（若 n = 1）；2T(n/2) + O(n) （若 n > 1）

 

所以我们得到了一个渐进复杂性优于暴力求解法的算法。

 

矩阵乘法的Strassen算法

相信大家一定都知道矩阵乘法，我这里主要讲一下著名的n*n矩阵相乘的递归算法。简单起见，我们先想一下用分治思想来计算矩阵乘积C=A*B。

 

我们先把n*n的矩阵划分成4个n/2*n/2的矩阵，所以A=[A11,A12,A21,A22],B=[B11,B12,B21,B22],C=[C11,C12,C21,C22]，由此可得：

 

C11 = A11*B11 + A12*B21

C12 = A11*B12 + A12*B22

C21 = A21*B11 + A21*B22

C22 = A21*B12 + A22*B22

 

讲到这，相信大家已经都差不多了，代码就不打了，大家都懂。

 

递归情况的总时间由分解时间，递归调用以及矩阵加法时间组成：

 

T(N) = T(n/2) + O(n^2)

 

这是分治思想的结果，而Strassen思想的核心是令递归树稍微不那么茂盛一点，即只递归进行7而非8次n/2*n/2矩阵的乘法。

 

具体步骤：

1. 将输入矩阵A、B和输出矩阵C分解为n/2 * n/2 的子矩阵。采用下标计算方法，此步骤花费Θ(1)Θ(1)时间，与SQUARE-MATRIX-MULTIPLY-RECURSIVE相同。
2. 创建10个n/2 * n/2的矩阵 S1,S2,...,S10S1,S2,...,S10每个矩阵保存步骤 1 中创建的两个矩阵的和或差。花费时间为Θ(n2)Θ(n2) 。
3. 用步骤1中创建的子矩阵和步骤2中创建的10个矩阵，递归的计算7个矩阵积P1,P2,..P7P1,P2,..P7。每个矩阵PiPi都是n/2 * n/2 的。
4. 通过PiPi矩阵的不同组合进行加减运算，计算出结果矩阵C的子矩阵C11,C12,C21,C22C11,C12,C21,C22.花费时间Θ(n2)Θ(n2)。

这样我们就用常数次的矩阵乘法减少了一次矩阵乘法。

 

下面我就简单地说一下代入法，递归树法，主方法来求解递归式。

 

用代入法求解递归式

1. 猜测解的形式。
2. 用数学归纳法求出解中的常数，并证明解是正确的。

 

是不是看着很扯，就是靠猜！~！

 

但这的确是这样的，先猜一个，再证明递归式的上界和下界，最后缩小不确定的范围！~！

 

用递归树方法求解递归树

在递归树中，每个节点表示一个单一问题的代价，子问题对应某次递归函数的调用，我们将树中每层的代价求和，得到每层代价，然后将所有层数代价求和，得到所有层数调用递归的总代价。

 

用主方法求解递归式

主方法提供了一种“菜谱式”的求解方法：

 

T(n) = aT(n/b) + f(n)

 

递归式描述的是这样一种算法运行时间：它将规模为n的问题分解为a个子问题，每个子问题的规模为n/b，其中a和b都是正常数。a个子问题递归的求解，每个问题花费时间T(n/b)，函数f(n)包含了问题分解和子问题解合并的代价。

 

1. 若对某个常数 ε>0 有 f(n) = O(nlogba-ε)，则 T(n) = Θ(nlogba) 。
2. 若 f(n) = Θ(nlogba)，则 T(n) = Θ(nlogba lgn) 。
3. 若对某个常数 ε>0 有 f(n) = Ω(nlogba+ε)，且对某个常数 c<1 和所有足够大的 n 有 af(n/b) ≤ cf(n)，则 T(n) = Θ(f(n)) 。

 

对于三种情况，我们都将函数 f(n) 与函数 nlogba 进行比较。直觉上，递归式的解取决于两个函数中的较大者。如情况一是 nlogba 较大，情况3是 f(n) 较大。而情况2是两者一样大，这种情况需要乘上一个对数因子。

 

不知不觉，写了这么多，刚开始开这个系列本意是想以刷题为主的，没想到到现在是算法介绍为主了，这当然也有自己想做点输出来巩固记忆。

 

好吧，下面是真题时间！~！

 

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

 

暴力求解

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # for i in range(n):
        #     arr[i] = arr[i] - arr[i-1]
        max_sum = nums[0]
        sum = 0
        for num in nums:
            sum += num
            if max_sum < sum:
                max_sum = sum
            if sum < 0:
                sum = 0
        return max_sum

 

动态规划

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return null
        res = nums[0]
        n_num = -1
        for num in nums:
            n_num = max(num,n_num + num)
            res = max(n_num,res)
        return res

 

差不多就是这样了，希望本文能帮到你！~！