n！实现以n^100为log N

Question

我正在读的SO这个帖子不同的排列：p-versus-np

见到了这个：

"The creation of all permutations for a given range with the length n is not bounded, as you have n! different permutations. This means that the problem could be solved in n^(100) log n, which will take a very long time, but this is still considered fast."

有人能解释一下N！可在n ^（100）log中求解n

Answer 1

我仔细阅读了来自我长期解释的声明。我认为，正确的写法应该是：

“这意味着一个问题可能在N 100日志N，其中将需要很长的时间来解决，但这仍然被认为是快速另一方。第一个用于TSP的算法之一是O（n！），另一个是O（n2 2n）。与多项式函数相比，这些算法真的非常快速。

通知字的 “一个”，而不是 “的”

Answer 2

正确的近似值是Stirling's formula。

这扼杀了家伙写的东西。老实说，我不知道他的意思是什么......