计算n的值选择k
Nik*_*nka 32 language-agnostic algorithm combinations
评估n选择k值的最有效方法是什么？我认为蛮力方式是找到n阶乘/ k阶乘/(nk)阶乘.
更好的策略可能是根据这个递归公式使用dp .有没有其他更好的方法来评估n选择k？
use*_*810 42
这是我的版本,纯粹用整数运算(除以k总是产生一个整数商),并且在O(k)处快速:
function choose(n, k)
if k == 0 return 1
return (n * choose(n - 1, k - 1)) / k
我是递归写的,因为它非常简单漂亮,但如果你愿意的话,你可以把它变成一个迭代的解决方案.
- @icepack:不,它没有.分子范围从n到n-k + 1.分母的范围从k到1.因此,选择(9,4)=(9*8*7*6)/(4*3*2*1)= 126,这是正确的.相比之下,9!/ 4!= 362880/24 = 15120. (5认同)
- 正确,但迂腐.上述函数进行O(k)乘法和除法.我忽略了操作本身的位复杂性. (4认同)
- 这是递归形式的乘法方法。它确实是 O(k)，并且是最快的，除非估计 k！使用斯特林近似就足够了（http://en.wikipedia.org/wiki/Stirling%27s_approximation）。有一个分而治之的阶乘版本，*可能*也有帮助（http://gmplib.org/manual/Factorial-Algorithm.html） (3认同)
- 这不是 O(*k*)；*k* 严格小于 *n*，因此不能忽略 *n* 对运行时的贡献。最好的情况下，您可以说它是 O(*k* M(*n*))，其中 M(*n*) 是乘法算法的速度。 (2认同)
Ped*_*rom 29
你可以使用Multiplicative公式:
http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
- 当nk <k时,我们可以通过计算(n选择nk)而不是(n选择k)来加速它. (16认同)
- 只要考虑到`(n - (ki))/ i`可能不是整数 (3认同)
- 稍微更新的公式：https://wikimedia.org/api/rest_v1/media/math/render/svg/652661edd20c8121e58a2b26844ce46c24180f0f (2认同)
如果您要计算许多这样的组合，计算帕斯卡三角形肯定是最佳选择。由于您已经知道递归公式，我想我可以在这里传递一些代码：
MAX_N = 100
MAX_K = 100
C = [[1] + [0]*MAX_K for i in range(MAX_N+1)]
for i in range(1, MAX_N+1):
for j in range(1, MAX_K+1):
C[i][j] = C[i-1][j-1] + C[i-1][j];
print C[10][2]
print C[10][8]
print C[10][3]