10

很容易看出 n! 增长速度比几乎任何 N 次方都慢（比如 100^N），因此，如果一个问题被认为是 NP 完全的并且发生了一个！近似解决方案的算法，人们会做史努比舞。

我对这种情况有两个问题：

  1. 会不会！算法被认为是多项式时间内的解决方案？阶乘当然不是一个提升到幂的术语。
  2. 如果找到一个！解决方案意味着我们有一个相当快的算法，因为 n! 增长速度超过 2^N，那么这是否意味着某些 NP 完全问题不需要启发式/逼近算法（晦涩的情况除外）？

当然，这两个问题依赖于第一段的真实性；如果我错了，请告诉我。

4

2 回答 2

41

  1. 不，阶乘时间不是多项式时间。多项式时间通常表示 O(N k )形式的方程，其中 N = 正在处理的项目数，k = 某个常数。重要的部分是指数是一个常数——你将 N 乘以它自己，其中一些是固定的——不依赖于 N 本身。阶乘复杂度算法意味着乘法的数量不是固定的——乘法本身的数量随着 N 增长。

  2. 您似乎在这里遇到了同样的问题。N 2将是多项式复杂度。2 N不会。您的基本原则也是错误的——阶乘复杂度算法并不意味着“我们有一个相当快的算法”，至少作为一般规则。如果有的话，结论恰恰相反：阶乘算法在一些特殊情况下可能是实用的（即 N 非常小），但随着 N 的增长很快变得不实用。

让我们试着正确看待这一点。二进制搜索是 O(log N)。线性搜索是 O(N)。在排序中，“慢”算法是 O(N 2 )，“高级”算法是 O(N lg N)。阶乘复杂度（显然足够）O（N！）。

让我们试着给出一些数字，考虑（目前）只有 10 个项目。这些中的每一个将大致是处理 10 个项目而不是 1 个项目的处理时间的多少倍：

O(log N): 2
O(N):10
O(N log N): 23
O(N 2 ): 100
O(N!): 3,628,800

目前我有点作弊，并使用自然对数而不是以 2 为底的对数，但我们只是在这里尝试进行粗略估计（无论如何，差异都是一个相当小的常数因子）。

如您所见，阶乘复杂度算法的增长率比其他任何算法都快得多。如果我们将其扩展到 20 项，差异将变得更加显着：

O(log N): 3
O(n): 20
O(N log N): 60
O(N 2 ): 400
O(N!): 2,432,902,008,176,640,000

N 的增长率！速度如此之快，几乎可以保证它们是不切实际的，除非已知所涉及的项目数量非常少。对于 grins，我们假设上述进程的基本操作都可以在单个机器时钟周期内运行。只是为了争论（并保持计算简单），让我们假设一个 10 GHz CPU。因此，基础是处理一项需要 0.1 ns。在这种情况下，有 20 个项目：

O(log N) = .3 ns
O(N) = 2 ns
O(N log N) = 6 ns
O(N 2 ) = 40 ns
O(N!) = 7.7 年。

于 2011-06-04T06:16:20.270 回答
5

很容易看出阶乘的行为（大约）是指数的。

它可以（非常粗略地）近似为 n n（更具体地说，是 sqrt(2πn)(n/e) n）。

因此，如果您发现任何特定的 M，您认为 M n是一个很好的近似值，那么您（可能）错了。269！大于 100 n并且作为 n! 将乘以大于 100 的数字，它将继续以更快的速度增长。

于 2011-06-04T10:36:59.750 回答