Алгоритмы на языке «разделяй и властвуй». Понятие о классах r и np, np-полных задачах

3. Проблемы с приложением
Рекурсия
Рекурсияговорят, что он конструирует так, что функция вызывает сама себя. Различают прямую и относительную рекурсию. Функция правильно называется рекурсивной, если ее тело содержит ссылку на себя. Когда функция вызывает другую функцию, а эта функция, в свою очередь, вызывает первую функцию, такая функция называется относительной рекурсией.

Quiksort — алгоритм быстрой сортировки.является ярким примером принципа «разделяй и властвуй». Этот алгоритм является рекурсивным и сортирует в среднем N*log2N сравнений. Алгоритм делит данный массив на 2, чтобы отсортировать его. Выбрав произвольный элемент для разбиения, он делится на 2 части.
Но лучше выбрать элемент посередине и разделить его на 2 из равной половины массива. Сравнивается каждый элемент слева и справа от выбранного ключевого элемента. От ключевого элемента мелкие переносятся влево, а крупные — вправо. Теперь повторите вышеуказанные шаги с обеих сторон массива. То есть в качестве ключей берутся элементы между этими интервалами и т.д.

Куча
Реализация стека может быть выполнена двумя различными способами. Цепочка (связанная) и массив.
Цепочка или связанный стек.Каждый элемент в стеке связан с элементом после него, и мы можем определить «верхний» элемент в стеке, используя эту последовательность. Временная сложность стека, созданного этим методом, указана в таблице ниже.

Амаль	Сложность
Нажмите (значение T)	\(О(1)\)
поп()	\(О(1)\)
заглянуть()	\(О(1)\)