Может ли кто-нибудь объяснить разницу между алгоритмами полиномиального времени, неполиномиального времени и экспоненциального времени?
Например, если алгоритм занимает O (n ^ 2) времени, то в какую категорию он входит?
Может ли кто-нибудь объяснить разницу между алгоритмами полиномиального времени, неполиномиального времени и экспоненциального времени?
Например, если алгоритм занимает O (n ^ 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 миллиардов миллиардов миллиардов операций в секунду в течение триллионов миллиардов миллиардов лет, чтобы это сделать.
Я не рассчитал это, но ЕГО ЭТО БОЛЬШОЕ.
Ниже приведены некоторые общие функции Big-O при анализе алгоритмов.
(n = размер ввода, c = некоторая константа)
Вот граф модели, представляющий сложность Big-O некоторых функций
ура :-)
График кредитов http://bigocheatsheet.com/
O (n ^ 2) - полиномиальное время. Многочлен f (n) = n ^ 2. С другой стороны, O (2 ^ n) - экспоненциальное время, где подразумевается экспоненциальная функция f (n) = 2 ^ n. Разница заключается в том, является ли функция n местом n в базе возведения в степень или в самом экспоненте.
Любая экспоненциальная функция роста будет расти значительно быстрее (в долгосрочной перспективе), чем любая полиномиальная функция, поэтому различие имеет отношение к эффективности алгоритма, особенно при больших значениях n.
Полиномиальное время
Полином - это сумма терминов, которые выглядят как Constant * x^k
Экспоненциальный означает что-то вроде Constant * k^x
(в обоих случаях k является константой, а x является переменной).
Время выполнения экспоненциальных алгоритмов растет намного быстрее, чем полиномиальных.
Экспоненциальный (у вас есть экспоненциальная функция, если MINIMAL ONE EXPONENT зависит от параметра):
Полином (у вас есть полиномиальная функция, если NO EXPONENT зависит от некоторых параметров функции):
полиномиальное время O (n) ^ k означает количество операций пропорционально мощности k размера ввода
экспоненциальное время O (k) ^ n означает Количество операций пропорционально показателю размера ввода
o (n sequre) - полиномиальная временная сложность, а o (2 ^ n) - экспоненциальная временная сложность если p = np в лучшем случае, в худшем случае p = np не является равным, поскольку размер входного файла n растет так долго или увеличивается размер входного sizer, поэтому он доходит до наихудшего случая и обрабатывает таким образом увеличение скорости роста сложности и зависит от n размера ввода когда вход мал, он является полиномиальным, если размер ввода большой и большой, поэтому p = np не равно ему означает, что скорость роста зависит от размера ввода "N". оптимизация, сит, клика и независимый набор также встречались в экспоненциальном значении до значения по умолчанию.