Полиномиальный алгоритм

Материал из WikiGrapp
Перейти к:навигация, поиск

Полиномиальный алгоритм (Polinomial algorithm) — алгоритм, у которого временная сложность равна \,O(p(n)), где \,p(n) — некоторый полином.

Другое название — Алгоритм полиномиальной временной сложности.

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.