Владстон Феррейра Фило - Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]

2. Повторять, пока все поселки не будут подключены.

Рис. 3.10.Решение задачи об электрической сети с «жадными» вариантами выбора

На каждом шаге мы выбираем для соединения пару поселков, которая на текущий момент выглядит самой лучшей. Несмотря на то что мы не анализируем, как этот вариант влияет на будущие возможности выбора, присоединение самого близкого поселка без электричества — всегда правильный выбор. Здесь нам повезло: структура задачи идеально подходит для решения «жадным» алгоритмом. В следующем разделе мы увидим структуры задач, для решения которых нужна стратегия великих полководцев.

Когда силы врага раздроблены на небольшие группы, его проще победить. Цезарь и Наполеон управляли Европой, разделяя и завоевывая своих врагов. При помощи той же стратегии вы можете решать задачи — в особенности задачи с оптимальной подструктурой , то есть такие, которые легко делятся на подобные, но меньшие подзадачи. Их можно дробить снова и снова, пока подзадачи не станут простыми. Затем их решения объединяются — так вы получаете решение исходной задачи.

Если у нас есть большой список, который нужно отсортировать, мы можем разделить его пополам: каждая половина становится подзадачей сортировки. Затем решения подзадач (то есть отсортированные половины списка) можно объединить в конечное решение при помощи алгоритма слияния [37] Это самый первый алгоритм, который вы увидели в главе 3. . Но как отсортировать эти две половины? Их тоже можно разбить на подзадачи, отсортировать и объединить.

Новые подзадачи будут также разбиты, отсортированы и объединены. Процесс разделения продолжаем, пока не достигнем базового случая: списка из одного элемента. Такой список уже отсортирован!

Этот изящный рекурсивный алгоритм называется сортировкой слиянием . Как и для последовательности Фибоначчи (см. раздел «Рекурсия»), дерево рекурсивных вызовов помогает увидеть, сколько раз функция merge_sort вызывает саму себя (рис. 3.11).

function merge_sort(list)

····if list.length = 1

········return list

····left ← list.first_half

····right ← list.last_half

····return merge(merge_sort(left),

·················merge_sort(right))

Теперь давайте найдем временную сложность сортировки слиянием. Для этого сначала подсчитаем операции, выполняемые на каждом отдельном шаге разбиения, а затем — общее количество шагов.

Подсчет операций.Допустим, у нас есть большой список размером n. При вызове функция merge_sort выполняет следующие операции:

• разбивает список на половины, что не зависит от размера списка O (1);

• вызывает функцию merge (из раздела «Итерация» мы знаем, что merge имеет сложность O ( n );

• делает два рекурсивных вызова merge_sort, которые не учитываются [38] Операции, которые выполняются рекурсивными вызовами, подсчитываются на следующем шаге разбиения. .

Поскольку мы оставляем только доминирующий член и не учитываем рекурсивные вызовы, временная сложность функции составляет O ( n ). Теперь подсчитаем временную сложность каждого шага разбиения.

Шаг разбиения 1.Функция merge_sort вызывается для списка из n элементов. Временная сложность этого шага составляет O ( n ).

Рис. 3.11.Демонстрация сортировки слиянием. Прямоугольники показывают отдельные вызовы merge_sort, при этом входные данные находятся вверху, а выходные — внизу

Шаг разбиения 2.Функция merge_sort вызывается дважды, каждый раз для элементов. Мы получаем .

Шаг разбиения 3.Функция merge_sort вызывается четыре раза, каждый раз для элементов: .