阶乘时间算法和P/NP问题

Question

10

很容易看出n！增长得比几乎任何N的幂次方（例如100^N）都要慢，因此，如果一个问题被认为是NP完全的，并且我们找到了一个n！算法来近似解决方案，那么人们会为之欢呼雀跃。

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

当然，这两个问题基于第一段话是正确的；如果我犯了错误，请告诉我。

- Zian Choy

n! 的增长速度比 k^n 快。一旦 n > k，那么 n! 肯定会增长得更快。 - Rafe

我不理解你的评论，因为对于某些大于k的n值，n!是一个单独的数字（例如：如果k = 10，则10！= 3628800）。 - Zian Choy

1

考虑n!和100^n的前100个项。到目前为止，100^n增长速度比n!快（即每个因子在100^n中比n!大--1 vs 100, 2 vs 100，...）。然而，超过这一点后，n!中的每个项都将比100^n中对应的项更大（101 vs 100, 102 vs 100，...）。 - Rafe

2个回答

5

很容易看出阶乘在行为上是（近似）指数级的。

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

因此，如果你找到了任何特定的M，认为Mⁿ是一个好的近似值，那么你（可能）是错误的。269！比100ⁿ还要大，并且由于n!将与大于100的数字相乘，它将继续增长得更快。

- Vatine

1

+1 for Stirling的近似公式。虽然除非你自己推导出来，否则你可能应该提到他的名字。 :-) - Nemo

经过进一步的检查，即使是令人困惑的 WolframAlpha 图表 (http://www.wolframalpha.com/input/?i=x%21+vs.+5%5Ex)，也揭示了 n! 和 5^x 是彼此相对应的翻译版本。 - Zian Choy

@Nemo：嗯，我通常自己使用n^n作为粗略的近似值。 - Vatine

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jerry Coffin · Accepted Answer

不，阶乘时间复杂度不是多项式时间复杂度。多项式时间复杂度通常意味着形如O(N^k)的方程式，其中N为处理的项数，k为某个常数。重要的是指数是一个常数——你正在将N乘以一个固定数量的自身——而不是取决于N本身。阶乘时间复杂度算法意味着乘法的数量并不固定——乘法的数量随着N增长。
在这里你似乎有同样的问题。N²将是多项式时间复杂度。2^N则不是。你的基本前提也是错误的——阶乘时间复杂度算法并不意味着“我们有一个相当快的算法”，至少一般来说不是这样。如果有什么的话，结论恰恰相反：阶乘算法可能在一些特殊情况下实用（即，N非常小）, 但是随着N的增长，它很快变得不实用。

让我们来看看这个问题。二分查找的时间复杂度为O(log N)。线性搜索的时间复杂度为O(N)。在排序中，“慢”算法的时间复杂度为O(N²)，而“先进”的算法则是O(N log N)。阶乘时间复杂度就是（显然）O(N!)。

让我们尝试将其放在一个更具体的背景下。考虑到只处理10个项，每个项大致上应该比1个项需要花费多少倍的时间：

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

这里我稍微作弊了一点，使用了自然对数而不是以2为底的对数，但我们只是在试图提供一个粗略的估计（而且差异在任何情况下都是一个相当小的常数因素）。

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

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

N!的增长速度非常之快，以至于它们几乎保证在涉及的项目数量已知相当小时就会变得不实用。仅仅为了好玩，让我们假设上述过程的基本操作可以在单个机器时钟周期内运行。出于论证的目的（并且为了保持计算简单），让我们假设有一个10 GHz的CPU。那么，处理一个项目需要0.1纳秒。在这种情况下，有20个项目：

O(log N) = 0.3 纳秒
O(N) = 2 纳秒
O(N log N) = 6 纳秒
O(N²) = 40 纳秒
O(N!) = 7.7 年。