最大子数组问题

给定一个数组A,求数组A中和最大的子数组:
image.png

如果使用暴力方法解这个问题需要检查\left( \begin{array} { c } { n - 1 } \\ { 2 } \end{array} \right) = \Theta \left( n ^ { 2 } \right)个子数组.

我们来思考如何使用分治法来解决这个问题,假设我们要寻找数组A [ \text {low} . . \text { high } ]的最大子数组,分治法要将这个问题简化成两个小问题,即分割成两个数组A [ \text {low.. mid} ]A [ \text {mid+1.. high } ],则A [ \text {low} . . \text { high } ]的最大子数组A [ i . . j ]必然是下列三种情况之一:

  • 位于A [ \text {low.. mid} ]
  • 位于A [ \text {mid+1.. high } ]
  • 跨越了中点

前两种情况可以递归求解,第三种情况只需遍历一次数组即可以线性时间求解.

def find_max_crossing_subarray(A,low,mid,high):
    # 找左边最大数组
    left_sum = -float('inf')
    sum = 0
    for i in range(low,mid+1)[::-1]:
        sum = 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 = 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):
    if high == low:
        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)
A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
find_maximum_subarray(A,0,len(A)-1)
# (7, 10, 43)

主定理

主定理可以轻松的计算出分治算法的时间复杂度.

a \geqslant 1b > 1是常数,f(n)是一个函数,T(n)是定义在非负整数上的递归式:

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

其中我们将n/b解释为\lfloor n / b \rfloor\lceil n / b \rceil.那么T(n)有如下渐近界:

  1. 若对某个整数\varepsilon > 0f ( n ) = O \left( n ^ { \log _ { b } a - \epsilon } \right),则T ( n ) = \Theta \left( n ^ { \log _ { b } a } \right).
  2. f ( n ) = \Theta \left( n ^ { \log _ { b } a } \right),则T ( n ) = \Theta \left( n ^ { \log _ { b } a } \lg n \right).
  3. 若对某个常数\varepsilon > 0f ( n ) = \Omega \left( n ^ { \log _ { b } a + \epsilon } \right),且对某个常数c<1和所有足够大的naf(n/b)\leq cf(n),则T ( n ) = \Theta ( f ( n ) ).

对于主定理的证明比较麻烦,这里就不介绍了,我们直接用就好了.需要注意的是并不是所有情况都可以用主方法求解.下面来用几个例子熟悉主定理:

第一个例子:

T ( n ) = 9 T ( n / 3 ) + n

这个例子中O(n^{\log_b a})=O(n^{\log_3 9})=O(n^2),属于第一种条件,所以T(n) = \Theta(n^2)

第二个例子:

T ( n ) = T ( 2 n / 3 ) + 1

这个例子中O(n^{\log_b a})=O(n^{\log_{3/2} 1})=O(n^0) = 1,属于第二种条件,所以T(n) = \Theta(\lg n)

第三个例子:

T ( n ) = 3 T ( n / 4 ) + n \lg n

这个例子中O(n^{\log_b a})=O(n^{\log_{4} 3})=O(n^{0.793}),当n足够大时n \lg n始终小于n^{0.793},所以f ( n ) = \Omega \left( n ^ { \log _ { b } a + \epsilon } \right),对于c = 3 / 4,a f ( n / b ) =3 ( n / 4 ) \lg ( n / 4 ) \leqslant ( 3 / 4 ) n \lg n = c f ( n ),所以属于第三种情况,T(n) = \Theta(n \lg n)

第四个例子:

T ( n ) = 2 T ( n / 2 ) + n \lg n

这个例子中f(n) = n \lg n渐近大于n ^ { \log _ { b } a } = n,问题在于这不是多项式意义上的大于,比值( n \lg n ) / n = \lg n都渐近小于n^\epsilon,因此此种情况不能用主方法求解.

下面有更多的例子可供练习:

T ( n ) = 2 T ( n / 2 ) + \Theta ( n )

T ( n ) = 8 T ( n / 2 ) + \Theta \left( n ^ { 2 } \right)

T ( n ) = 7 T ( n / 2 ) + \Theta \left( n ^ { 2 } \right)

T ( n ) = 2 T ( n / 4 ) + 1

T ( n ) = 2 T ( n / 4 ) + \sqrt { n }

T ( n ) = 2 T ( n / 4 ) + n

T ( n ) = 2 T ( n / 4 ) + n ^ { 2 }

posted @ 2019-02-04 15:06:47
评论加载中...

发表评论