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

Question

我最近看到一些有趣的讨论,争论一个给定的("硬")问题是否至少有2 ^ n或n!已知解决方案

我的问题是,除了实际走过算法并看到增长率之外,还有一种启发式方法可以快速发现一个与另一个相比吗？IE浏览器.是否存在一些算法的快速可观察属性,使其显然是一个或另一个？

相关讨论:

• /sf/answers/385593841/
• http://news.ycombinator.com/item?id=3621555

Answer 1

没有算法可以确定程序的复杂性[根本].它是暂停问题的一部分- 您无法确定某个算法是否会停止.[你不能估计它是否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()