Полиномиальная задержка - Википедия - Polynomial delay

в анализ алгоритмов, алгоритм перебора (т.е. алгоритм для перечисления большого или бесконечного набора структур), как говорят, имеет полиномиальная задержка если время между выходом любой одной структуры и следующей ограничено полиномиальной функцией размера входа, в худший случай.[1]Полиномиальная задержка подразумевает, что общее время, используемое алгоритмом, будет полиномиальным для каждого выходного элемента, но это более сильное требование. Это желательное свойство, потому что оно означает, что любому потребителю потока выходных данных не придется долго ждать простоя от одного выхода к другому. В частности, алгоритм с полиномиальной задержкой не может иметь фазу запуска, которая занимает экспоненциальное время до того, как он выдаст единичный вывод, в отличие от некоторых алгоритмов, которые занимают полиномиальное время для каждого элемента вывода.[2] Кроме того, в отличие от ограничений на общее время, это подходящая форма анализа даже для алгоритмов, которые производят бесконечную последовательность выходных данных.

Понятие полиномиальной задержки было впервые введено Дэвид С. Джонсон, Михалис Яннакакис и Христос Пападимитриу.[2]

Рекомендации

  1. ^ Голдберг, Лесли Энн (1991). Эффективные алгоритмы перечисления комбинаторных структур. ed.ac.uk (Кандидатская диссертация). Эдинбургский университет. HDL:1842/10917. ISBN  9780521117883. OCLC  246835963. EThOS  uk.bl.ethos.651566.
  2. ^ а б Джонсон,. С.; Яннакакис, М.; Пападимитриу, К. (1988), «О порождении всех максимальных независимых множеств», Письма об обработке информации, 27 (3): 119–123, Дои:10.1016/0020-0190(88)90065-8, МИСТЕР  0933271.