Zia*_*hoy 7 algorithm np-complete
很容易看到n!比N几乎任何东西都要慢得多(比如说,100 ^ N),所以,如果一个问题被认为是NP完全而且一个发生在一个!算法近似解决方案,人们会做史努比舞蹈.
我有两个关于这种情况的问题:
当然,这两个问题依赖于第一段是真的; 如果我错了,请告诉我.
Jer*_*fin 36
阶乘时间不是多项式时间.多项式时间通常表示形式为O(N k)的等式,其中N =正在处理的项目数,并且k =某个常数.重要的是指数是一个常数 - 你将N乘以一定数量的固定 - 不依赖于N本身.因子复杂度算法意味着乘法的数量不固定 - 乘法的数量本身随N增长.
你似乎在这里有同样的问题.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.因此,基础是处理一个项目需要.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年.
很容易看出阶乘是(近似)行为的指数.
它可以(非常粗略地)近似为n n(更具体地,sqrt(2πn)(n/e)n).
因此,如果您发现任何特定的M,您认为M n是一个很好的近似值,那么(可能)是错误的.269!大于100 n并且为n!将乘以大于100的数字,它将继续增长更快.