我正在阅读算法简介并尝试完成书中的练习。
在练习 4.1-3
4.1-3 在您自己的计算机上实现最大子阵列问题的蛮力和递归算法。什么问题大小 n0 给出了递归算法击败蛮力算法的交叉点？然后，只要问题大小小于 n0，就将递归算法的基本情况更改为使用蛮力算法。这会改变交叉点吗？
我按照书上的伪代码写了这两个算法。但是，我的代码一定有问题，因为第二个代码被设计为 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)：
sub_sum = 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 = 无
sub_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 = 无
sub_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)
# 子函数
# 增长率：应该是 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）
交叉 = 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
打印“比率：”，（time1-time0）/（time2-time1）