阶乘时间算法和P / NP

         否。阶乘时间不是多项式时间。多项式时间通常表示O（Nk）形式的方程，其中N =要处理的项目数，k =某个常数。重要的是，指数是一个常数-您要用N乘以固定数量的N而不是依赖于N本身。阶乘复杂度算法意味着乘法的数量不固定-乘法的数量本身随N增加。 您似乎在这里有同样的问题。 N2将是多项式复杂度。 2N不会。您的基本信条也是错误的-至少一般而言，阶乘复杂度算法并不意味着“我们有一个相当快的算法”。如果有的话，得出的结论则相反：因数算法在一些特殊情况下（即N极小）可能是实用的，但随着N的增长很快变得不切实际。 让我们尝试将其视为透视。二进制搜索为O（log N）。线性搜索为O（N）。在排序中，“慢”算法为O（N2），而“高级”算法为O（N lg N）。阶乘复杂度是（显然足够）O（N！）。 让我们尝试添加一些数字，目前仅考虑10个项目。这些中的每一个将大约是10项而不是1项需要更长的处理时间： O（log N）：2 O（N）：10 O（N log N）：23 O（N2）：100 O（N！）：3,628,800 目前，我已经作弊了一点，并使用自然对数代替以2为底的对数，但是我们在这里仅尝试进行估算（无论如何，差异都是一个很小的常数因子）。 如您所见，阶乘复杂度算法的增长率比其他任何算法都快得多。如果我们将其扩展到20个项目，差异将变得更加明显： O（log N）：3 O（n）：20 O（N对数N）：60 O（N2）：400 O（N！）：2,432,902,008,176,640,000 N的增长率！速度如此之快，几乎可以保证它们是不切实际的，除非已知所涉及的项数很小。对于咧咧的笑容，我们假设上述进程的基本操作可以在单个机器时钟周期内运行。只是为了论证（并保持计算简单），我们假设一个10 GHz CPU。因此，基础是处理一项需要0.1 ns。在这种情况下，有20个项目： O（log N）= 0.3 ns O（N）= 2毫微秒 O（N log N）= 6 ns O（N2）= 40毫微秒 O（N！）= 7.7年。     

        很容易看出阶乘在行为上（大约）是指数的。 它可以（非常粗略）近似为nn（更具体地说，sqrt（2πn）（n / e）n）。 因此，如果您发现任何特定的M都认为Mn是一个很好的近似值，那么您（可能）是错误的。 269！大于100n并等于n！将被乘以大于100的数字，它将继续以更快的速度增长。