Порядковые статистики

Задача нахождения k-ой порядковой статистики: дан список из n записей и целое число k, необходимо найти ключ записи, которая стоит в отсортированном списке в k-ой позиции.

Специальные случаи этой задачи возникают при k=0 – нахождение минимального элемента,

k=n-1 – нахождение максимального элемента

и, если n нечетно, k=(n+1)/2 – нахождение медианы (если n четно, то существует две медианы k=n/2 и k=n/2+1).

В некоторых случаях решение задачи вычисления порядковых статистик находится за линейное время.

Например, нахождение максимального и минимального элементов требует времени порядка О(n).

Для нахождения k-ой порядковой статистики при и можно использовать пирамидальную сортировку, которая дает в этом случае время порядка О(n).

Методы разработки алгоритмов. Типы алгоритмов

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

Следует, однако, подчеркнуть, что существуют задачи, например NP-полные задачи, для которых эти и любые другие известные методы не обеспечивают эффективных решений. Когда встречается подобная задача, нередко бывает полезно определить, о5ладают ли входные данные для этой задачи какими-либо особыми характеристиками, которыми можно воспользоваться при попытках найти требуемое решение, и можно ли воспользоваться каким-либо приближенным решением (если такое решение легко получить) вместо точного решения, получить которое бывает очень трудно.

Алгоритмы «разделяй и властвуй» (метод декомпозиции)

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

Чтобы проиллюстрировать этот метод, рассмотрим хорошо известную головоломку "Ханойские башни". Имеются три стержня А, В и С. Вначале на стержень А нанизаны несколько дисков: диск наибольшего диаметра находится внизу, а выше – диски последовательно уменьшающегося диаметра, как показано на рис.

Цель головоломки – перемещать диски (по одному) со стержня на стержень так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра и чтобы в конце концов все диски оказались нанизанными на стержень В.

Стержень С можно использовать для временного хранения дисков.

Для решения этой головоломки подходит следующий простой алгоритм.

Представьте, что стержни являются вершинами треугольника. Пронумеруем все перемещения дисков.

Тогда при перемещениях с нечетными номерами наименьший диск, нужно перемещать в треугольнике на соседний стержень по часовой стрелке.

При перемещениях с четными номерами выполняются другие допустимые перемещения, не связанные с наименьшим диском.

Исходное положение в головоломке "Ханойские башни"

Описанный выше алгоритм, конечно, правильный и, к тому же, весьма лаконичный, правда, нелегко понять, почему он "работает", да и вряд ли такой алгоритм быстро придет вам в голову.

Попробуем вместо этого применить метод декомпозиции.

Задачу перемещения n наименьших дисков со стержня А на стержень В можно представить себе состоящей из двух подзадач размера n – 1. Сначала нужно переместить n – 1 наименьших дисков со стержня А на стержень С, оставив на стержне А n-й наибольший диск. Затем этот диск нужно переместить с А на В. Потом следует переместить n-1 дисков со стержня С на стержень В. Это перемещение n-1 дисков выполняется путем рекурсивного применения указанного метода. Чтобы прояснить идею алгоритма, опишем еще один шаг решения головоломки. После того как n – 1 дисков перемещены на стержень С, а наибольший диск помещен на стержень В, n – 2 наименьших диска со стержня С перемещаются на стержень А и (n – 1)-й диск переносится на диск В. Далее решается задача с n – 2 дисками, находящимися на диске А. Поскольку диски, участвующие в перемещениях, по размеру меньше тех, которые в перемещении не участвуют, не нужно задумываться над тем, что находится под перемещаемыми дисками на стержнях А, В или С. Хотя фактическое перемещение отдельных дисков не столь очевидно, а моделирование вручную выполнить непросто из-за образования стеков рекурсивных вызовов, с концептуальной точки зрения этот алгоритм все же довольно прост для понимания и доказательства его правильности (а если говорить о быстроте разработки, то ему вообще нет равных). Именно легкость разработки алгоритмов по методу декомпозиции обусловила огромную популярность этого метода; к тому же, во многих случаях эти алгоритмы оказываются более эффективными, чем алгоритмы, разработанные традиционными методами. В случае "Ханойских башен" алгоритм декомпозиции на самом деле ничем не отличается от того алгоритма, который был описан вначале.