Полиномиальные и экспоненциальные алгоритмы. Примеры алгоритмов решения задач?

Question

[ChastIOtvaga]

Не могли бы дать статью по Полиномиальные и экспоненциальные алгоритмы. Примеры алгоритмов решения задач и оценка их трудоемкости. Не могу найти что нужно для конспекта преподу ещё нужно сcылка на статью

Comments

[mayton2019]

Сортировка методом Шелла - это полином. Только не квадрат и не куб а дробная степень.
Что то вроде n в степени 1.2.

[dmshar]

mayton2019, N в степени 3/2 при последовательности Хиббарда и в степени 4/3 при последовательности Седжвика.

[mayton2019]

dmshar, я не возражаю. Автор просил полиномиальный пример. Вот ему пример. Докиньте еще ему что-то экспоненциальное.

[dmshar]

Перебор всех подмножеств из N элементов. Сложность такого решения O(2**N).

[ChastIOtvaga]

ребят я просил статью на словах я это понимаю а мне надо статью преподу показать откуда я брал)

[dmshar]

ChastIOtvaga, Очень странный у вас препод. Чему он не поверит? Что такие алгоритмы есть? Что они используются? Или тому, что вы такие статьи сами нашли?