我正在阅读算法导论并试图完成书中的练习。

在练习 4.1-3 中



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

def find_maximum_subarray_bf(a): #bf 用于蛮力
p1 = 0
l = 0 # l 为左
r = 0 # r 为右边
最大总和 = 0
对于范围内的 p1(len(a)-1):
子总和 = 0
对于范围内的 p2(p1, len(a)):
sub_sum += a[p2]
如果 sub_sum > max_sum:
max_sum = sub_sum
l = p1
r = p2
返回 l, r, max_sum

def find_maximum_subarray_dc(a): #dc 分而治之

# 子功能
# 给定一个数组和三个可以将数组拆分为 a[l:m] 的索引
# 和 a[m+1:r],找出一个子数组 a[i:j],其中 l\leq i\less m\less j\leq r"。
# 根据上面的定义,目标子数组必须
# 由两个子数组 a[i:m] 和 a[m+1:j] 组合
# 增长率:theta(n)

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

# 左边
# ls_r 和 ls_l 表示左子数组的左右边界。
# l_max_sum 表示左子数组的最大和
# sub_sum 表示当前计算子数组的总和
ls_l = 0
ls_r = m-1
l_max_sum = 无
子总和 = 0
for j in range(m+1)[::-1]: # 从右到左添加元素
sub_sum += a[j]
如果 sub_sum > l_max_sum:
l_max_sum = sub_sum
ls_l = j

# 右边
# rs_r 和 rs_l 表示左子数组的左右边界。
# r_max_sum 表示左子数组的最大和
# sub_sum 表示当前计算子数组的总和
rs_l = m+1
rs_r = 0
r_max_sum = 无
子总和 = 0
对于范围内的 j(m+1,len(a)):
sub_sum += a[j]
如果 sub_sum > r_max_sum:
r_max_sum = sub_sum
rs_r = j

#结合
返回 (ls_l, rs_r, l_max_sum+r_max_sum)

# 子功能
# Growing Rate: 应该是theta(nlgn),但是有一些错误
def recursion(a,l,r): # T(n)
如果 r == l:
返回 (l,r,a[l])
别的:
m = (l+r)//2 # theta(1)
left = recursion(a,l,m) # T(n/2)
右 = 递归(a,m+1,r) # T(n/2)
cross = find_crossing_max(a,l,r,m) # theta(n)

如果 left[2]>=right[2] 和 left[2]>=crossing[2]:
返回左
elif right[2]>=left[2] 和 right[2]>=crossing[2]:
返回权
别的:
回程

#返回主函数
l = 0
r = len(a)-1
返回递归(a,l,r)

如果 __name__ == "__main__":

从时间导入时间

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

时间 0 = 时间()
find_maximum_subarray_bf(a)
时间 1 = 时间()
find_maximum_subarray_dc(a)
时间 2 = 时间()
打印“函数 1:”,time1-time0
打印“函数 2:”,time2-time1
打印 "ratio:", (time1-time0)/(time2-time1)

最佳答案

首先,蛮力中的一个错误:

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)

此外,总和的初始值。最大子数组的索引对于左侧部分是可疑的,对于右侧部分是错误的。

对于左边的部分,我们从一个空和开始,但必须包括 a[m] 。这可以通过最初设置 l_max_sum = None 或通过设置 l_max_sum = a[m] 并让 j 省略索引 m 来完成。无论哪种方式, ls_l 的初始值都不应该是 0 ,而对于 ls_r ,它不应该是 m-1ls_r 必须为 m ,如果 ls_l 的初始值为 m+1 ,则 l_max_sum 应以 None 开头,如果 ml_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^kn/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

关于python - Theta(n**2) 和 Theta(n*lgn) 算法执行不正确,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13789925/

10-12 23:23