algorithm - 总和大于给定值的最小子数组的大小

Question

原来的问题是

总和大于给定值的最小子数组给定一个整数数组和一个数字 x，找到总和大于给定值的最小子数组。在http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

但是如果问题只是求最小子数组的大小，是否可以使用分而治之的方法呢？

算法:Size_of_min_subarray(1,n) =

min of { Size_of_min_subarray(1,n/2), Size_of_min_subarray(n/2,n),Size_of_array_containing mid_element(s) }

Size_of_array_containing_mid_element 的计算方式:

取mid element(s)，初始化sum=mid element/sum of mid elements and num_elements=1/2 based on n is odd or even .if sum<=given value, check if number in its right or left更大。将更大的元素添加到总和并增加 num_elements。重复直到 sum> 给定值。

插图:

1,4,45,6,0,19 和阈值=51

min_size=min{ min_size{1,4,45} , min_size{6,0,19} , min_containing_45and6 }

min_containing_45and6:

sum=中间元素/中间元素之和=45+6=51<=51,num_elements=2。由于 4>0 将 4 添加到 sum 中，sum=55 并增加 num_elements。 num_elements=3.

min_size=min{不可能，不可能，3}=3。

这个算法正确吗？我认为它的复杂度是 O(logn)，对吗？

编辑:我意识到我用来查找 Size_of_array_containin_mid_elemnts 的算法是错误的。有人可以建议一种算法来查找这个值吗？

Answer 1

1. 没有亚线性算法可以解决这个问题，因为它必须至少考虑每个数组元素一次(最坏情况)。

2. 您的算法缺少“基本”步骤，即 Size_of_min_subarray(1,n) 用于小 n(无论“小”是什么)。

3. 您的算法的循环是 F(n)=2*F(n/2)+G(n) 其中 F(n) 是对于大小 n 和 G(n)，Size_of_min_subarray 的复杂度是 Size_of_array_containing_mid_element(n) 的复杂度。由于 G(n)~O(n)，您的算法是 O(n)。