Почему алгоритмы «разделяй и властвуй» часто работают быстрее, чем грубая сила? Например, чтобы найти ближайшую пару точек. Я знаю, что вы можете показать мне математическое доказательство. Но интуитивно, почему это происходит? Магия?
Теоретически, верно ли, что «разделяй и властвуй всегда лучше, чем грубая сила»? Если нет, то есть ли контрпример?
Что касается вашего первого вопроса, то интуиция, стоящая за принципом «разделяй и властвуй», заключается в том, что во многих задачах объем работы, который необходимо выполнить, основан на некотором комбинаторном свойстве входных данных, которое масштабируется более чем линейно.
Например, в задаче о паре ближайших точек время выполнения прямого перебора ответов определяется тем, что вам нужно просмотреть все O(n2) возможных пар точек.
Если вы возьмете что-то, что растет квадратично, и разрежете его на две части, каждая из которых в два раза меньше, чем раньше, то для решения задачи в каждой половине потребуется четверть начального времени, поэтому решение задачи в обеих половинах займет примерно время половина времени, необходимого для решения грубой силы. Разрезание на четыре части заняло бы одну четвертую часть времени, разрезание на восемь частей — одну восьмую и т. д.
В этом случае рекурсивная версия оказывается быстрее, потому что на каждом шаге мы избегаем большого объема работы с парами элементов, гарантируя, что пар, которые нам действительно нужно проверять, не слишком много. Большинство алгоритмов, использующих принцип «разделяй и властвуй», оказываются быстрее по той же причине.
Что касается вашего второго вопроса, нет, алгоритмы «разделяй и властвуй» не обязательно быстрее, чем алгоритмы грубой силы. Рассмотрим задачу нахождения максимального значения в массиве. Алгоритм грубой силы занимает O (n) времени и использует пространство O (1), поскольку он выполняет линейное сканирование данных. Алгоритм «разделяй и властвуй» приведен здесь:
Это также занимает время O(n), но использует память O(log n) для пространства стека. На самом деле это хуже, чем простой линейный алгоритм.
В качестве другого примера можно привести максимальную прибыль от одной продажи. -conquer, но оптимизированное решение для динамического программирования быстрее и по времени, и по памяти.
Надеюсь это поможет!
Я рекомендую вам прочитать главу 5 книги Algorithm Design, она очень хорошо объясняет принцип разделяй и властвуй.
Интуитивно, для проблемы, если вы можете разделить ее на две подзадачи с тем же шаблоном, что и исходная, а временная сложность объединения результатов двух подзадач в окончательный результат как-то мала, тогда это быстрее чем решить исходную полную проблему грубой силой.
Как сказано в разделе Проектирование алгоритмов, на самом деле вы не можете получить слишком много от метода «разделяй и властвуй» с точки зрения времени. 3) до O(n^2)), но вряд ли от экспоненциального до полиномиального (например, от O(2^n) до O(n^3)).
Я думаю, что максимум, что вы можете получить от принципа «разделяй и властвуй», — это установка на решение проблем. Это всегда хорошая попытка разбить первоначальную большую проблему на более мелкие и простые подзадачи. Даже если у вас не будет лучшего времени выполнения, это все равно поможет вам обдумать проблему.
