Полиномиальное время и экспоненциальное время

Может ли кто-нибудь объяснить разницу между алгоритмами полиномиального времени, неполиномиального времени и экспоненциального времени?

Например, если алгоритм занимает O (n ^ 2) времени, то в какую категорию он входит?

Ответы

Ответ 1

Проверьте это.

Экспоненциальный хуже, чем полиномиальный.

O (n ^ 2) попадает в квадратичную категорию, которая является типом полинома (частный случай экспоненты равен 2) и лучше, чем экспоненциальный.

Экспоненциальный намного хуже, чем полиномиальный. Посмотрите, как растут функции

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

k^n  = k^10  |   k^100   |    k^1000

k ^ 1000 исключительно велико, если k не меньше, чем что-то вроде 1.1. Например, что-то вроде каждой частицы во Вселенной должно было бы выполнять 100 миллиардов миллиардов миллиардов операций в секунду в течение триллионов миллиардов миллиардов лет, чтобы это сделать.

Я не рассчитал это, но ЕГО ЭТО БОЛЬШОЕ.

Ответ 2

Ниже приведены некоторые общие функции Big-O при анализе алгоритмов.

  • O (1) - постоянное время
  • O (log (n)) - логарифмическое время
  • O ((log (n)) c) - полилогарифмическое время
  • O (n) - линейное время
  • O (n 2) - квадратичное время
  • O (n c) - полиномиальное время
  • O (c n) - экспоненциальное время
  • O (n!) - факториальное время

(n = размер ввода, c = некоторая константа)

Вот граф модели, представляющий сложность Big-O некоторых функций

graph model

ура :-)

График кредитов http://bigocheatsheet.com/

Ответ 3

O (n ^ 2) - полиномиальное время. Многочлен f (n) = n ^ 2. С другой стороны, O (2 ^ n) - экспоненциальное время, где подразумевается экспоненциальная функция f (n) = 2 ^ n. Разница заключается в том, является ли функция n местом n в базе возведения в степень или в самом экспоненте.

Любая экспоненциальная функция роста будет расти значительно быстрее (в долгосрочной перспективе), чем любая полиномиальная функция, поэтому различие имеет отношение к эффективности алгоритма, особенно при больших значениях n.

Ответ 4

Полиномиальное время

Полином - это сумма терминов, которые выглядят как Constant * x^k Экспоненциальный означает что-то вроде Constant * k^x

(в обоих случаях k является константой, а x является переменной).

Время выполнения экспоненциальных алгоритмов растет намного быстрее, чем полиномиальных.

Ответ 5

Экспоненциальный (у вас есть экспоненциальная функция, если MINIMAL ONE EXPONENT зависит от параметра):

  • например. f (x) = constant ^ x

Полином (у вас есть полиномиальная функция, если NO EXPONENT зависит от некоторых параметров функции):

  • например. f (x) = x ^ constant

Ответ 6

полиномиальное время O (n) ^ k означает количество операций пропорционально мощности k размера ввода

экспоненциальное время O (k) ^ n означает Количество операций пропорционально показателю размера ввода

Ответ 7

o (n sequre) - полиномиальная временная сложность, а o (2 ^ n) - экспоненциальная временная сложность если p = np в лучшем случае, в худшем случае p = np не является равным, поскольку размер входного файла n растет так долго или увеличивается размер входного sizer, поэтому он доходит до наихудшего случая и обрабатывает таким образом увеличение скорости роста сложности и зависит от n размера ввода когда вход мал, он является полиномиальным, если размер ввода большой и большой, поэтому p = np не равно ему означает, что скорость роста зависит от размера ввода "N". оптимизация, сит, клика и независимый набор также встречались в экспоненциальном значении до значения по умолчанию.