9. Хуйня какая-то…

Метод ветвей и границ: состоит в последовательном переборе вариантов, рассмотрении лишь тех из них, которые по определенным признакам оказываются перспективными, и отбрасывании бесперспективных вариантов.

Задача коммивояжёра — задача отыскания самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п.

Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи.

10 Простая сортировка

Метод прямого включения, сложность O(n²): мы шаг за шагом идем по массиву и каждый элемент последовательно вставляем в нужную нам позицию.

Метод прямого обмена (пузырек) , сложность O(n²): меняем местами соседние элементы до полного упорядочивания

Метод прямого выбора, сложность O(n²): выбираем наименьший элемент, меняем местами с первым, и повторяем тоже самое с оставшимися (n-1) элементами, пока не останется 1 элемент.

12 Внешняя сортировка — сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память.

Сортировка простым слиянием: образуем сначала пары, затем четверки, восмерки и т.д. пока не получится исходный упорядоченый массив:

11 Сложные сортировки

Метод Шелла, сложность О(n log n): усовершенствованная сортировка прямого включения. Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на большом расстоянии, затем это расстояние уменьшается и так до тех пор, пока расстояние не станет равно единице.

Метод Хоара (быстрая сортировка), сложность О(n log n): берем средний элемент массива Х. Далее будем просматривать наш массив слева, пока не найдем элемент i > X, затем справа, пока не найдем элемент j < X. Теперь поменяем местами i и j и продолжим процесс просмотра и обмена, пока оба просмотра не встретятся (i=j). В результате массив будет разбит на левую часть с элементами меньше или равными X и правую часть с элементами большими или равными X. Затем применим этот процесс к получившимся двум частям, затем к частям частей. И так до тех пор, пока каждая из частей не будет состоять из одного-единственного элемента.

Сортировка пирамидой, сложность О(n log n): строим сортирующее дерево для которого массив array, где: array[1] – это корень, array[2i] и array[2i+1] – потомки элемента array[i]. Array[i] >= array[2i] и array[2i+1]. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем array[1] и array[n], преобразовываем array[1], … , array[n-1] в сортирующее дерево. Затем переставляем array[1] и array[n-1] и т.д. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент.

13 Поиск

Интерполяционный – дан массив m[], искомый X, гранницы left и right.

while( m[left] <= x && x <= m[right] )

{

y = i + (x - m[left]) / (m[right] - m[left]) * (right - left);

if( m[y] < x ) left = y+1;

if( m[y] > x ) right = y-1;

if( m[y] = x ) return y;

}

if( m[left] = x) return left;

else return NOT FOUND;