Divide and Conquer (разделяй и властвуй)
Divide and Conquer (разделяй и властвуй) — это популярная техника для решения алгоритмических задач. Мы уже знакомились с некоторыми методами решения подобных задач. Например, жадный алгоритм выбирает оптимальный результат на каждом шаге, а динамическое программирование строит текущее состояние, опираясь на предыдущие. В случае с Divide and Conquer мы разбиваем задачу на более мелкие подзадачи и решаем каждую из них по отдельности, а затем объединяем полученные результаты. Таким образом, мы divide (разделяем) исходную задачу на подзадачи и conquer (преодолеваем) её, комбинируя решения этих подзадач.
Challenge
Представьте, что у вас есть 512 чисел и 512 специализированных компьютеров (очень маленьких и узконаправленных), которые умеют только вычислять максимум из двух чисел.
Нам нужно найти максимальное число среди этих 512 чисел за максимально короткое время.
Каждый компьютер способен взять два числа, а затем за 1 секунду вернуть их максимум (да, они действительно медлительны 🐌). Сможете придумать алгоритм, который позволит найти максимум среди всех данных чисел как можно быстрее?