Принцип “разделяй и властвуй”

Решение задачи методом “разделяй и властвуй” состоит из двух шагов:

1. Определяем базовый случай, это должен быть простейший случай из всех возможных

2. Задача делится или сокращается до тех пор, пока не будет сведена к базовому случаю.

👾 “Разделяй и властвуй” — не просто алгоритм, который можно применить для решения задачи! Скорее это подход к решению.

📍 Пример: чтобы отсортировать список из n натуральных чисел, необходимо разбить его на два списка примерно из n/2 чисел каждый, отсортировать каждый из них по очереди и скомпоновать оба результата соответствующим образом, чтобы получить отсортированную версию данного списка (алгоритм сортировки слиянием).