2

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

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

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

优化这个公式以最小的 O 时间复杂度运行

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

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

在有人尝试解决方案后，我将发布该讨论中的一些信息/链接。

任何语言都可以接受。

4

7 回答 7

6

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

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（k2）

如果重写为使用浮点数，乘法将是原子操作，但我们会损失很多精度。它甚至溢出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
于 2009-06-05T15:46:30.397 回答
5

请注意，WolframAlpha 返回一个“十进制近似值”。如果您不需要绝对精度，您可以通过使用Stirling's Approximation计算阶乘来做同样的事情。

现在，Stirling 的近似需要计算 (n/e)^n，其中 e 是自然对数的底，这将是迄今为止最慢的操作。但这可以使用另一个 stackoverflow 帖子中概述的技术来完成。

如果您使用双精度和重复平方来完成求幂，则操作将是：

  • 对斯特林近似的 3 次评估，每次都需要 O(log n) 次乘法和一次平方根评估。
  • 2 次乘法
  • 1个部门

稍微聪明一点可能会减少操作的数量，但是使用这种方法，总时间复杂度将是 O(log n)。相当易于管理。

编辑：考虑到这种计算的普遍性，肯定会有很多关于这个主题的学术文献。一个好的大学图书馆可以帮助你找到它。

EDIT2：另外，正如在另一个响应中指出的那样，这些值很容易溢出双精度，因此即使是中等大的 k 和 n 值，也需要使用具有非常扩展精度的浮点类型。

于 2009-06-05T16:12:44.523 回答
2

我会在Mathematica中解决它：

Binomial[n, k]

伙计，这很容易...

于 2009-06-05T15:45:15.780 回答
2

Python：O (1)中的近似值？

使用python十进制实现来计算近似值。由于它不使用任何外部循环，并且数量有限，我认为它会在O (1) 中执行。

from decimal import Decimal

ln = lambda z: z.ln()
exp = lambda z: z.exp()
sinh = lambda z: (exp(z) - exp(-z))/2
sqrt = lambda z: z.sqrt()

pi = Decimal('3.1415926535897932384626433832795')
e = Decimal('2.7182818284590452353602874713527')

# Stirling's approximation of the gamma-funciton.
# Simplification by Robert H. Windschitl.
# Source: http://en.wikipedia.org/wiki/Stirling%27s_approximation
gamma = lambda z: sqrt(2*pi/z) * (z/e*sqrt(z*sinh(1/z)+1/(810*z**6)))**z

def choose(n, k):
  n = Decimal(str(n))
  k = Decimal(str(k))
  return gamma(n+1)/gamma(k+1)/gamma(n-k+1)

例子：

>>> choose(20000000,15000000)
Decimal('2.087655025913799812289651991E+4884377')
>>> choose(130202807,65101404)
Decimal('1.867575060806365854276707374E+39194946')

再高一点，就会溢出。指数似乎限制为 40000000。

于 2009-06-09T22:59:50.537 回答
1

给定合理数量的 n 和 K 值，提前计算它们并使用查找表。

它以某种方式回避了这个问题（您正在卸载计算），但如果您必须确定大量值，它是一种有用的技术。

于 2009-06-05T15:53:30.803 回答
1

MATLAB：

  • 作弊者的方式（使用内置函数NCHOOSEK）：13 个字符，O(?)

    nchoosek(N,k)

  • 我的解决方案：36 个字符，O(min(k,Nk))

    a=min(k,N-k);
prod(N-a+1:N)/prod(1:a)
于 2009-06-05T16:22:15.650 回答
1

我知道这是一个非常古老的问题，但我一直在努力解决这个问题，直到我找到了一个用 VB 6 编写的非常简单的问题，并将其移植到 C# 之后，结果如下：

public int NChooseK(int n, int k)
{
    var result = 1;
    for (var i = 1; i <= k; i++)
    {
        result *= n - (k - i);
        result /= i;
    }

    return result;
}

最终的代码非常简单，除非您运行它，否则您不会相信它会起作用。

此外，原始文章对他如何达到最终算法给出了一些很好的解释。

于 2012-03-20T18:58:32.747 回答