gpt4 book ai didi

python - Theta(n**2) 和 Theta(n*lgn) 算法执行不当

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:09:52 28 4
gpt4 key购买 nike

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

练习 4.1-3

4.1-3 Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size n0 gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than n0. Does that change the crossover point?

这两个算法是我按照书上的伪代码写的。但是,我的代码一定有问题,因为第二个代码设计为 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_sumdef 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)

最佳答案

首先,暴力破解中的一个错误:

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-1 . ls_r必须是 m , 和 ls_l应以 m+1 开头如果初始值为 l_max_sumNone , 以及 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 < lrecursion , 并且重复很小,所以我会保留这一点。

因为你总是遍历 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

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

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com