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

Question

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

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

Answer 1

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

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

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

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

ура: -)

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

Answer 7

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