最近,我解决了将不同宽度大小的小容器水平均匀分散到巨大宽度大小容器中的问题。有数以百万计的巨大容器和数十亿个小容器。我需要想出一个算法。我将问题简化为以下问题:
让我们使用Process(Number,Parts)
为例:
数字4
可以通过 3 种方式拆分为2
个部分(不包括 0(。Process(4,2)=3
:
1 + 3
3 + 1
2 + 2
同样,数字4
可以通过两种方式分成3
部分,Process(4,3)=2
:
1 + 1 + 2
2 + 1 + 1
1 + 2 + 1
显然Process(4,4)=1
(不包括Process(4,1)=1
,因为它是4+0
,0
不应该被考虑在内(
我想知道是否有任何计算方法
SuperProcess(4)=Process(4,2)+Process(4,3)+Process(4,4)=7
时间复杂度更低?或者换个词,更快!!
特别是当请求是计算时:SuperProcess(1209)
是否有一些数学方法而不是粗略的循环来执行此计算?
SuperProcess(n)
被称为整数的组合数,而不是包含相同加法的总和被视为与排序无关的相同分区数。
正整数正好有2**(n-1)-1
组合,n
排除只有一个加法的总和。
因此,计算SuperProcess(n)
的最佳算法是简单地计算表达式2**(n-1)-1
,这可以Theta(n)
时间内完成。
如果要枚举所有组合,可以使用递归函数来完成此操作,该函数获取总和中当前位置的整数m
的每个值1...n
,然后递归调用自身,n-m
用于下一个位置,停止0
参数。
枚举算法将花费Theta(n 2**n)
时间,这是最佳的,因为这是显式保存/打印所有组合所需的时间。