1

除了正常的递归函数和循环方法之外，找到数字的阶乘的有效方法是什么？由于普通方法产生输出所需的时间太长，有什么方法可以比递归和循环方法降低时间复杂度？如果没有，为什么？

4

6 回答 6

7

从79开始！是 1.711E98 你只需要一个包含 79 个数字的列表就可以使用查找表。阶乘以整数格式列于： http ://www.tsm-resources.com/alists/fact.html 或以科学格式列于http://home.ccil.org/~remlaps/javascript/jstest1.html，所以它只是“剪切和粘贴”

于 2013-08-21T12:02:12.483 回答
2

由于您的一条评论说您想找到 100000！，因此此答案涵盖了巨大的阶乘。

如果您不需要确切的答案，您可以使用斯特林近似

如果您想要一个准确的答案，您需要使用任意精度数学包，如 GMP 任意精度数学包

于 2013-08-21T12:12:02.460 回答
2

如果要计算许多阶乘值，则可以选择在进行时缓存这些值。

如果你只是一个单一的计算factorial(n)，那么循环可能是你能得到的最好的。您可以通过一些循环展开（一次计算两个或四个乘法）从处理器中获得更多收益，但它不太可能适用于非常大的阶乘，因为乘法本身就变成了一系列冗长的指令。

据我所知，没有什么“神奇”的数学可以12 * 13 * 14 * 15比将它们相乘更快地计算出一个或类似的序列。

于 2013-08-21T12:04:19.293 回答
2

您可以使用斯特林近似来评估一个大的阶乘。

于 2013-08-21T12:07:06.870 回答
0

计算非常大的因子的最简单方法是使用 gamma 函数。另一方面：它不会像查表那样快（正如其他人所建议的那样）；如果您使用的是内置类型，则需要以下表格：

for 32 bits: 12 entries
for 64 bits: 20 entries
for float:   34 entries
for double: 170 entries

（上表中可能存在一个错误。我编写了代码以非常快速地计算它们。）

对于double，并且可能float，通常的循环方法可能会引入太多的舍入错误。如果您不想使用表格，并且您有 C++11， exp( lgamma( i + 1 ) )那么应该这样做。（如果你没有 C++11，你可能有这个lgamma函数。它在 C99 中。）

如果您正在处理某种扩展范围类型，则可能必须为您的类型实现lgamma(and exp)。

于 2013-08-21T14:14:08.017 回答
0

不，不是。如果您担心运行时成本，可以使用查找表（这要求您使用预先计算的值）来减少它。

存储每个阶乘可能需要太多内存，所以让我们存储每个 k:th 阶乘。这将要求程序在运行时执行多达 k 次乘法。

假设您的运行时性能要求将每个阶乘限制为 1000 次乘法。然后你需要预先计算并存储 1000!, 2000!, 3000! 依此类推，直到您要支持的上限（可用内存会限制您）。

由于阶乘很快变得比本机数据类型大，因此您需要一个可以处理大量数字的类。我假设存在这样一个类并且它被称为BigInteger.

BigInteger preCalculatedValues[] = { new BigInteger("1"), new BigInteger("<value of 1000!>"), and so on... }

BigInteger factorial(int n) {
  int pre = n/1000;
  int i;
  if (pre > LARGEST_VALUE_HANDLED) { 
    // Either throw an exception or let it take longer. I choose to let it take longer.
    pre = LARGEST_VALUE_HANDLED;
  }
  BigInteger result = preCalculatedValues[pre];
  for (i = pre * 1000 + 1; i <= n; i++) {
     result.multiplyWith(i);  // This operation is probably overloaded on the * operator
  }
}
于 2013-08-21T12:30:07.803 回答