Theta(n**2)和Theta(n*lgn)算法执行不正确

Question

我正在阅读算法导论,并尝试完成本书中的练习.

在练习4.1-3中

4.1-3在您自己的计算机上实现最大子阵列问题的强力算法和递归算法.问题大小n0给出了递归算法胜过强力算法的交叉点？然后,每当问题大小小于n0时,更改递归算法的基本情况以使用强力算法.这会改变交叉点吗？

我根据本书的伪代码编写了两种算法.但是,我的代码肯定有问题,因为第二个,设计为Theta(n*lgn)并且应该运行得更快,总是比第一个Theta(n**2)运行得慢.我的代码如下所示.

def find_maximum_subarray_bf(a):        #bf for brute force
    p1 = 0
    l = 0           # l for left
    r = 0           # r for right
    max_sum = 0
    for p1 in range(len(a)-1):
        sub_sum = 0
        for p2 in range(p1, len(a)):
            sub_sum += a[p2]
            if sub_sum > max_sum:
                max_sum  = sub_sum
                l = p1
                r = p2
    return l, r, max_sum

def find_maximum_subarray_dc(a):        #dc for divide and conquer

    # subfunction
    # given an arrary and three indics which can split the array into a[l:m]
    # and a[m+1:r], find out a subarray a[i:j] where l \leq i \less m \less j \leq r".
    # according to the definition above, the target subarray must
    # be combined by two subarray, a[i:m] and a[m+1:j]
    # Growing Rate: theta(n)

    def find_crossing_max(a, l, r, m):

        # left side
        # ls_r and ls_l indicate the right and left bound of the left subarray.
        # l_max_sum indicates the max sum of the left subarray
        # sub_sum indicates the sum of the current computing subarray      
        ls_l = 0
        ls_r = m-1
        l_max_sum = None
        sub_sum = 0
        for j in range(m+1)[::-1]:      # adding elements from right to left
            sub_sum += a[j]
            if sub_sum > l_max_sum:
                l_max_sum = sub_sum
                ls_l = j

        # right side
        # rs_r and rs_l indicate the right and left bound of the left subarray.
        # r_max_sum indicates the max sum of the left subarray
        # sub_sum indicates the sum of the current computing subarray                
        rs_l = m+1
        rs_r = 0
        r_max_sum = None
        sub_sum = 0
        for j in range(m+1,len(a)):
            sub_sum += a[j]
            if sub_sum > r_max_sum:
                r_max_sum = sub_sum
                rs_r = j

        #combine
        return (ls_l, rs_r, l_max_sum+r_max_sum)

    # subfunction
    # Growing Rate: should be theta(nlgn), but there is something wrong
    def recursion(a,l,r):           # T(n)
        if r == l:
            return (l,r,a[l])
        else:
            m = (l+r)//2                    # theta(1)
            left = recursion(a,l,m)         # T(n/2)
            right = recursion(a,m+1,r)      # T(n/2)
            crossing = find_crossing_max(a,l,r,m)   # theta(n)

            if left[2]>=right[2] and left[2]>=crossing[2]:
                return left
            elif right[2]>=left[2] and right[2]>=crossing[2]:
                return right
            else:
                return crossing

    #back to master function
    l = 0
    r = len(a)-1
    return recursion(a,l,r)

if __name__ == "__main__":

    from time import time

    a = [100,-10,1,2,-1,4,-6,2,5]
    a *= 2**10

    time0 = time()
    find_maximum_subarray_bf(a)
    time1 = time()
    find_maximum_subarray_dc(a)
    time2 = time()
    print "function 1:", time1-time0
    print "function 2:", time2-time1 
    print "ratio:", (time1-time0)/(time2-time1)

Answer 1

首先,蛮力的错误:

for p1 in range(len(a)-1):

应该是range(len(a))[或xrange],因为它不会找到最大的子阵列[-12,10].

现在,递归:

def find_crossing_max(a, l, r, m):

    # left side
    # ls_r and ls_l indicate the right and left bound of the left subarray.
    # l_max_sum indicates the max sum of the left subarray
    # sub_sum indicates the sum of the current computing subarray      
    ls_l = 0
    ls_r = m-1
    l_max_sum = None
    sub_sum = 0
    for j in range(m+1)[::-1]:      # adding elements from right to left

您正在检查所有索引为0,但您应该只检查索引l.使用,而不是构建range列表并将其反转xrange(m,l-1,-1)

        sub_sum += a[j]
        if sub_sum > l_max_sum:
            l_max_sum = sub_sum
            ls_l = j

对于右边的总和,模拟成立,你应该只检查索引r,所以xrange(m+1,r+1).

此外,您的总和的初始值resp.最大子阵列的索引对于左侧部分是可疑的,而对于右侧则是错误的.

对于左边部分,我们从一个空的开头开始,但必须包括a[m].这可以通过l_max_sum = None最初设置,或通过设置l_max_sum = a[m]和j省略索引来完成m.无论哪种方式,初始值ls_l不应该是0,并且ls_r不应该是m-1.ls_r必须m和ls_l应该开始为m+1因为如果初始值l_max_sum是None,并且m如果l_max_sum开始的a[m].

对于正确的部分,r_max_sum必须从0开始,并且rs_r应该更好地开始m(虽然这不是很重要,它只会给你错误的索引).如果右边的总和都不是非负的,那么正确的总和应该是0而不是最大的负数.

在recursion,我们有一些重复

left = recursion(a,l,m)         # T(n/2)

包括a[m]已经处理或主要的金额find_crossing_max,所以可能

left = recursion(a,l,m-1)

不过这样人们就不得不也可治疗的可能性r < l中recursion,和重复小,所以我就让那个立场.

由于你总是遍历整个列表find_crossing_max,这就是所谓的O(n)时间,你的分而治之的实现实际上O(n²)也是如此.

如果选中的范围find_crossing_max被限制[l,r],因为它应该是,你有(大约)2^k对长度的范围要求n/2^k,0 <= k <= log_2 n为的总成本O(n*log n).

通过这些更改(以及一些随机数组生成),

def find_maximum_subarray_bf(a):        #bf for brute force
    p1 = 0
    l = 0           # l for left
    r = 0           # r for right
    max_sum = 0
    for p1 in xrange(len(a)):
        sub_sum = 0
        for p2 in xrange(p1, len(a)):
            sub_sum += a[p2]
            if sub_sum > max_sum:
                max_sum  = sub_sum
                l = p1
                r = p2
    return l, r, max_sum

def find_maximum_subarray_dc(a):        #dc for divide and conquer

    # subfunction
    # given an arrary and three indices which can split the array into a[l:m]
    # and a[m+1:r], find out a subarray a[i:j] where l \leq i \less m \less j \leq r".
    # according to the definition above, the target subarray must
    # be combined by two subarray, a[i:m] and a[m+1:j]
    # Growing Rate: theta(n)

    def find_crossing_max(a, l, r, m):

        # left side
        # ls_r and ls_l indicate the right and left bound of the left subarray.
        # l_max_sum indicates the max sum of the left subarray
        # sub_sum indicates the sum of the current computing subarray      
        ls_l = m+1
        ls_r = m
        l_max_sum = None
        sub_sum = 0
        for j in xrange(m,l-1,-1):      # adding elements from right to left
            sub_sum += a[j]
            if sub_sum > l_max_sum:
                l_max_sum = sub_sum
                ls_l = j

        # right side
        # rs_r and rs_l indicate the right and left bound of the left subarray.
        # r_max_sum indicates the max sum of the left subarray
        # sub_sum indicates the sum of the current computing subarray                
        rs_l = m+1
        rs_r = m
        r_max_sum = 0
        sub_sum = 0
        for j in range(m+1,r+1):
            sub_sum += a[j]
            if sub_sum > r_max_sum:
                r_max_sum = sub_sum
                rs_r = j

        #combine
        return (ls_l, rs_r, l_max_sum+r_max_sum)

    # subfunction
    # Growing Rate:  theta(nlgn)
    def recursion(a,l,r):           # T(n)
        if r == l:
            return (l,r,a[l])
        else:
            m = (l+r)//2                    # theta(1)
            left = recursion(a,l,m)         # T(n/2)
            right = recursion(a,m+1,r)      # T(n/2)
            crossing = find_crossing_max(a,l,r,m)   # theta(r-l+1)

            if left[2]>=right[2] and left[2]>=crossing[2]:
                return left
            elif right[2]>=left[2] and right[2]>=crossing[2]:
                return right
            else:
                return crossing

    #back to master function
    l = 0
    r = len(a)-1
    return recursion(a,l,r)

if __name__ == "__main__":

    from time import time
    from sys import argv
    from random import randint
    alen = 100
    if len(argv) > 1:
        alen = int(argv[1])
    a = [randint(-100,100) for i in xrange(alen)]

    time0 = time()
    print find_maximum_subarray_bf(a)
    time1 = time()
    print find_maximum_subarray_dc(a)
    time2 = time()
    print "function 1:", time1-time0
    print "function 2:", time2-time1 
    print "ratio:", (time1-time0)/(time2-time1)

我们得到了我们应该期待的东西:

$ python subarrays.py 50
(3, 48, 1131)
(3, 48, 1131)
function 1: 0.000184059143066
function 2: 0.00020382
ratio: 0.902923976608
$ python subarrays.py 100
(29, 61, 429)
(29, 61, 429)
function 1: 0.000745058059692
function 2: 0.000561952590942
ratio: 1.32583792957
$ python subarrays.py 500
(35, 350, 3049)
(35, 350, 3049)
function 1: 0.0115859508514
function 2: 0.00170588493347
ratio: 6.79175401817
$ python subarrays.py 1000
(313, 572, 3585)
(313, 572, 3585)
function 1: 0.0537149906158
function 2: 0.00334000587463
ratio: 16.082304233
$ python osubarrays.py 10000
(901, 2055, 4441)
(901, 2055, 4441)
function 1: 4.20316505432
function 2: 0.0381460189819
ratio: 110.186204655