本文共 5587 字,大约阅读时间需要 18 分钟。
公众号:顾先生的数据挖掘
关注他
16 人赞同了该文章
今天我们来讲一下分治算法,废话不多说了,我们开始吧!~!
在分支策略中,我们对一个问题求以下三步递归:
本文我会从一个求解最大子数组问题出发,进而介绍矩阵乘法的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 &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 = 0for (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]必然又以下三种情况:
第一、第二种情况还好处理,因为它本质上还是一个最大子数组的问题,只是规模更小,我们只需要将其递归求解即可。
关键是求解第三种情况,因为它加入了限制:必须包含中间位置 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)
所以我们得到了一个渐进复杂性优于暴力求解法的算法。
相信大家一定都知道矩阵乘法,我这里主要讲一下著名的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矩阵的乘法。
具体步骤:
这样我们就用常数次的矩阵乘法减少了一次矩阵乘法。
下面我就简单地说一下代入法,递归树法,主方法来求解递归式。
是不是看着很扯,就是靠猜!~!
但这的确是这样的,先猜一个,再证明递归式的上界和下界,最后缩小不确定的范围!~!
在递归树中,每个节点表示一个单一问题的代价,子问题对应某次递归函数的调用,我们将树中每层的代价求和,得到每层代价,然后将所有层数代价求和,得到所有层数调用递归的总代价。
主方法提供了一种“菜谱式”的求解方法:
T(n) = aT(n/b) + f(n)
递归式描述的是这样一种算法运行时间:它将规模为n的问题分解为a个子问题,每个子问题的规模为n/b,其中a和b都是正常数。a个子问题递归的求解,每个问题花费时间T(n/b),函数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
差不多就是这样了,希望本文能帮到你!~!
转载地址:http://xgkii.baihongyu.com/