Полиномиальный алгоритм: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Полиномиальный алгоритм''' (''Polinomial algorithm'') - алгоритм, у которого ''временна...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Полиномиальный алгоритм''' (''Polinomial algorithm'') - | '''Полиномиальный алгоритм''' (''[[Polinomial algorithm]]'') - | ||
алгоритм, у которого ''временная сложность'' равна <math>O(p(n))</math>, где | [[алгоритм]], у которого ''[[временная сложность]]'' равна <math>O(p(n))</math>, где | ||
<math>p(n)</math>--- некоторый полином. | <math>p(n)</math>--- некоторый полином. | ||
Другое название --- ''Алгоритм полиномиальной временной сложности.'' | Другое название --- ''[[Алгоритм полиномиальной временной сложности]].'' | ||
См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, | ==См. также ==''[[Задача о вершинном покрытии]], [[Задача о выполнимости]], [[Задача о клике]], [[Задача о неэквивалентности регулярных выражений]], [[Задача о разбиении]], [[Задача о точном покрытии 3-множествами]], [[Задача о трехмерном сочетании]], [[Классы P и NP|Классы <math>\mathcal P</math> и <math>\mathcal NP</math>]], [[Метод локальной замены]], [[Метод построения компонент]], [[Метод сужения задачи]], [[Полиномиальная сводимость (трансформируемость)]], [[NP-Полная задача|<math>\mathcal NP</math>-полная задача]], [[Труднорешаемая задача]].'' | ||
Задача о трехмерном сочетании, Классы <math>\ | |||
==Литература== | ==Литература== | ||
[Ахо-Хопкрофт-Ульман], | [Ахо-Хопкрофт-Ульман], | ||
Версия от 12:19, 21 декабря 2009
Полиномиальный алгоритм (Polinomial algorithm) - алгоритм, у которого временная сложность равна [math]\displaystyle{ O(p(n)) }[/math], где [math]\displaystyle{ p(n) }[/math]--- некоторый полином.
Другое название --- Алгоритм полиномиальной временной сложности.
==См. также ==Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о точном покрытии 3-множествами, Задача о трехмерном сочетании, Классы [math]\displaystyle{ \mathcal P }[/math] и [math]\displaystyle{ \mathcal NP }[/math], Метод локальной замены, Метод построения компонент, Метод сужения задачи, Полиномиальная сводимость (трансформируемость), [math]\displaystyle{ \mathcal NP }[/math]-полная задача, Труднорешаемая задача.
Литература
[Ахо-Хопкрофт-Ульман],
[Касьянов/88],
[Евстигнеев-Касьянов/94],
[Касьянов/95]