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

90

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

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

algorithm Абдул Самад
источник

Ответы:

85

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

Экспонента хуже полинома.

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 миллиардов миллиардов миллиардов операций в секунду в течение триллионов миллиардов миллиардов лет, чтобы это сделать.

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

hvgotcodes
источник
29
Мне нравились все твои иллюзии.
Жозефина
7
k ^ 1000 исключительно велико, если k заметно больше 1. Если k = 1, это менее впечатляет, а если k = 1.00069387 ..., это 2.
Жозефина
2
Как насчет п! против k ^ n. Я знаю, что для 2 ^ n (наиболее часто), n! будет дороже, но я считаю, что для общего k ^ n, где k> 2, n! будет дешевле.
Саад
1
Я рада, что вы не сказали «миллиарды и миллиарды». :-)
Том Рассел
@Saad n! всегда будет асимптотически дороже, чем k ^ n для постоянного k. Однако вы правы в том, что это происходит только тогда, когда мы достигаем большого значения n. По приближению Стирлинга факториальное время должно стать более дорогим примерно при n = e * k, где e = 2,71828 ..
inavda
136

Ниже приведены некоторые общие функции 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 некоторых функций

графовая модель

ура :-)

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

Моханрадж Баласубраманиам
источник
12
Плюс один для меньшего количества слов и большей ясности.
user3144836
1 = n ^ 0, поэтому также многочлен
BigChief
46

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

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

Жозефина
источник
Этот ответ имеет авторитетный (хороший) вид, но он отличается от ответа @dheeran, я полагаю, тем, что основание в экспоненциальном случае обязательно равно 2. Или, вероятно, я неправильно понимаю и просто должен стереть пыль со своей алгебры.
Том Рассел
21

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

Многочлен - это сумма членов, которые выглядят как Constant * x^k экспонента, что означает что-то вродеConstant * k^x

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

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

Клеман
источник
18

Экспоненциальная (у вас есть экспоненциальная функция, если МИНИМАЛЬНАЯ ОДНА ЭКСПОНЕНТА зависит от параметра):

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

Полиномиальная (у вас есть полиномиальная функция, если НИКАКАЯ ЭКСПОНЕНТА не зависит от некоторых параметров функции):

  • Например, f (x) = x ^ константа
Эрхард Динхобль
источник
4
Мне не нравится, если из моего исходного ответа ничего не осталось после того, как он был отредактирован пользователем. Это что-то вроде «подобной рыбалки»?
Эрхард Динхобл
2
Я должен согласиться. Изменения смешные.
satya on rails
3

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

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

Студент
источник
0

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

Насир
источник