Обнаружение разницы между n! и алгоритм 2 ^ n - PullRequest
Новая
       2

Обнаружение разницы между n! и алгоритм 2 ^ n

4 голосов
/ 23 февраля 2012

Я видел несколько интересных дискуссий, недавно обсуждающих, имеет ли данная («трудная») проблема в лучшем случае 2 ^ n или n!известное решение.

Мой вопрос, помимо того, что вы на самом деле просматриваете алгоритм и видите скорость роста, есть ли эвристика для быстрого обнаружения одного против другого?То есть.Существуют ли определенные быстро наблюдаемые свойства алгоритма, которые делают его явно тем или иным?

Связанные обсуждения:

Ответы [ 2 ]

6 голосов
/ 23 февраля 2012

Не существует алгоритма, который мог бы определить сложность программы [вообще].Это часть проблемы остановки - вы не можете определить, остановится ли определенный алгоритм или нет.[Вы не можете оценить, является ли оно 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()
0 голосов
/ 23 февраля 2012

Как уже упоминалось, теоретически невозможно проверить, является ли алгоритм O (2 ^ n) или O (n!).Однако вы можете использовать следующую эвристику:

  1. Для различных значений n рассчитайте количество шагов, F (n), для решения
  2. График n против журнала (F (n)) / n
  3. Если она выглядит как плоская линия (или выравнивается как плоская линия), то это O (2 ^ n)
  4. Если она выглядит как строго возрастающая функция, тоis является суперэкспоненциальным
  5. Если он выглядит более линейно по сравнению с графиком log (x), то это "вероятно" O (n!)
...