algorithm - 发现 n! 之间的区别!和一个 2^n 算法

Question

我最近看到一些有趣的讨论，讨论给定的(“困难”)问题是否至多是 2^n 或 n!已知的解决方案。

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

相关讨论:

• 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 ) 算法，它还调用了两次递归调用。

编辑:例如:
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()