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

У меня есть вопрос о разнице между алгоритмами полиномиального времени, алгоритмами неполиномиального времени и алгоритмами экспоненциального времени, например, если алгоритм займет время O(n^2), то в какой категории он будет?

7 59
algorithm

7 ответов:

зацените

http://en.wikipedia.org/wiki/Big_oh#Orders_of_common_functions

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

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

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

n    = 10    |     100   |      1000

n^2  = 100   |   10000   |   1000000 

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

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

Я не рассчитал его, но он такой большой.

57

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

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

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

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

graph model

ура :-)

кредиты графа http://bigocheatsheet.com/

61

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

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

39

полиномиальное время.

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

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

17

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

  • например, f (x) = константа ^ x

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

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

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

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

2

o (n sequre) - полинимальная временная сложность, а o (2^n) - экспоненциальная временная сложность если п=НП, когда лучшем случае , в худшем случае п=НП не равны, потому что при входе размера n растут так долго или ввода сайзер увеличить так больше его будет в худшем случае и обращение, поэтому сложность темпов роста и зависят от N размер ввода при входе это polynimal когда входной размер большой, а большие так что п=НП не равный это означает, темпы роста зависят от величины входного сигнала "Н". оптимизация, sat, clique и независимое множество также встречалось в экспоненциальном к полинимальному.

0