注意到n之间的差别！和2^n算法

Question

最近我看到了一些有趣的讨论，争论一个给定的(“硬”)问题是最多有2^n还是n！已知的解决方案。

我的问题是，除了实际遍历算法并查看增长速度之外，是否有一种启发式方法可以快速发现其中一种与另一种？即。一个算法是否有某些快速可观察的特性，使其明显地成为一个或另一个？

相关讨论：

• https://stackoverflow.com/a/5508483/26624
• http://news.ycombinator.com/item?id=3621555

Answer 1

根本没有算法可以确定程序的复杂性。它是Halting Problem的一部分--您无法确定某个算法是否会停止。您无法估计它是否是Theta(infinity)或低于它的任何东西。

作为经验法则，通常是 O(n!)算法在循环中调用递归调用，而O(2^n)算法则在每个调用中调用两次递归调用。

注意到：并不是所有调用递归调用两次的算法都是O(2^n) --快速排序是O(nlogn)算法的一个很好的例子，O(nlogn)算法也会调用两次递归调用。

编辑:例如：

SAT蛮力解决方案O(2^n)

SAT(formula,vars,i):
  if i == vars.length:
      return formula.isSatisfied(vars)
  vars[i] = true
  temp = SAT(formula,vars,i+1)  //first recursive call
  if (temp == true) return true
  vars[i] = false
  return SAT(formula,vars,i+1)  //second recursive call

查找所有排列：O(n!)

permutations(source,sol):
  if (source.length == 0): 
      print sol
      return
  for each e in source: 
      sol.append(e)
      source.remove(e)
      permutations(source,sol) //recursive call in a loop
      source.add(e)
      sol.removeLast()

Answer 2

正如amit所提到的，理论上不可能检查算法是O(2^n)还是O(n!)。但是，您可以使用以下启发式方法：

1. 对于n的不同值计算步骤数，F(n)，如果它看起来像一条平行线(或平行线)，则它是O(2^n)
2. ，如果它看起来像一个严格增加的函数，则是超级指数

H19如果它看起来更多行x vs日志(X)图，那么它就是“可能”O(n！)<代码>H 210G 211