Полиномиальная задержка
При анализе алгоритмов говорят, что алгоритм перечисления (т. е. алгоритм перечисления большого или бесконечного набора структур) имеет полиномиальную задержку , если время между выводом любой одной структуры и следующей ограничено полиномиальной функцией от размер ввода, в худшем случае . [1] Полиномиальная задержка подразумевает, что общее время, используемое алгоритмом, будет полиномиальным для каждого выходного элемента, но это более строгое требование. Это желательное свойство, поскольку оно означает, что любому потребителю потока выходных данных не придется долго ждать бездействия от одного вывода к другому. В частности, алгоритм с полиномиальной задержкой не может иметь фазу запуска, которая занимает экспоненциальное время , прежде чем он выдаст один выходной результат, в отличие от некоторых алгоритмов, которые занимают полиномиальное время на каждый выходной элемент. [2] Кроме того, в отличие от ограничений общего времени, это подходящая форма анализа даже для алгоритмов, которые производят бесконечную последовательность результатов.
Понятие полиномиальной задержки было впервые введено Дэвидом С. Джонсоном , Михалисом Яннакакисом и Христосом Пападимитриу . [2]
Ссылки
[ редактировать ]- ^ Голдберг, Лесли Энн (1991). Эффективные алгоритмы перечисления комбинаторных структур . ed.ac.uk (докторская диссертация). Эдинбургский университет. hdl : 1842/10917 . ISBN 9780521117883 . OCLC 246835963 . EThOS uk.bl.ethos.651566 .
- ^ Jump up to: а б Джонсон, . С .; Яннакакис, М. ; Пападимитриу, CH (1988), «О создании всех максимальных независимых наборов», Information Processing Letters , 27 (3): 119–123, doi : 10.1016/0020-0190(88)90065-8 , MR 0933271 .