您将如何以最紧凑的方式为大型组合编写此算法？

Question

k可以从N项目检索的项目组合的数量由以下公式描述.

             N! 
c =  ___________________ 
       (k! * (N - k)!)

一个例子是6 Balls可以从48 Balls彩票抽奖的鼓中抽取多少组合.

优化此公式以使用最小的O时间复杂度运行

这个问题的灵感来自新的WolframAlpha数学引擎,以及它可以非常快速地计算出非常大的组合.例如,随后在另一个论坛上讨论该主题.

http://www97.wolframalpha.com/input/?i=20000000+Choose+15000000

在一些人对解决方案进行了尝试之后,我会发布一些来自该讨论的信息/链接.

任何语言都可以接受.

Answer 1

Python: O(min [ k,n - k ] ²)

def choose(n,k):
    k = min(k,n-k)
    p = q = 1
    for i in xrange(k):
        p *= n - i
        q *= 1 + i
    return p/q

分析:

• 的大小p和q将内环路线性增加,如果n-i和1+i可被认为具有一定的大小.
• 然后,每次乘法的成本也会线性增加.
• 所有迭代的总和成为算术系列k.

我的结论:O(k²)

如果重写为使用浮点数,则乘法将是原子操作,但是我们将失去很多精度.它甚至溢出choose(20000000, 15000000).(不是很大的惊喜,因为结果大约是0.2119620413×10 ^4884378.)

def choose(n,k):
    k = min(k,n-k)
    result = 1.0
    for i in xrange(k):
        result *= 1.0 * (n - i) / (1 + i)
    return result

Answer 2

请注意,WolframAlpha返回"十进制逼近".如果您不需要绝对精度,您可以通过使用斯特林近似计算阶乘来做同样的事情.

现在,斯特林的近似需要评估(n/e)^ n,其中e是自然对数的基础,这将是迄今为止最慢的运算.但是这可以使用另一个stackoverflow帖子中概述的技术来完成.

如果使用双精度和重复平方来完成取幂,则操作将为:

• 3个斯特林近似的评估,每个评估需要O(log n)乘法和一个平方根评估.
• 2次乘法
• 1个师

操作次数可能会稍微有点聪明,但使用这种方法总时间复杂度将为O(log n).非常易于管理.

编辑:考虑到这个计算的常见程度,这个主题也必定有很多学术文献.一个好的大学图书馆可以帮助你追踪它.

EDIT2:另外,正如在另一个响应中指出的那样,这些值很容易溢出一个double,因此即使是适度大的k和n值,也需要使用具有非常高精度的浮点类型.