Разделяй и властвуй: является ли частью эффективности то, что решение подзадач значительно быстрее, чем неразделенная проблема?

Question

Я думаю о QuickSort конкретно: каждая подзадача составляет примерно половину размера основной проблемы - это то, что подзадачи, включая накладные расходы по разделению основной проблемы и затем рекомбинации результатов решенных подзадач, имеют тенденцию быть решено менее чем за половину основной проблемы?

Я понимаю, что параллельное решение подзадач также является способом ускорения алгоритма, но в большинстве обсуждений QuickSort не упоминается параллелизм.

Answer 1

Быстрая сортировка не является хорошим примером «разделяй и властвуй», поскольку ее основная функция упорядочения данных ( pivot) выполняется перед делением. Как только базовый случай с размером раздела == 1 достигнут, все элементы в этой части цепочки вызовов упорядочены.

Типичная сортировка слиянием сверху вниз является лучшим примером, поскольку она ничто иное, как pu sh индексы (или указатели) на стек через рекурсивные вызовы, и объединение не происходит до тех пор, пока не произойдут два экземпляра подмассива размером 1. Затем объединение выполняется, следуя цепочке вызовов вверх и вниз. Однако сортировка по принципу слияния снизу пропускает все рекурсивные генерации индексов и начинается с обработки массива из n элементов как n подмассивов размера 1 и немедленно начинает слияние. Сверху вниз в основном используется в образовательных целях, в то время как большинство библиотек используют гибрид гибридной сортировки слиянием и сортировкой с вставкой.

Answer 2

Не совсем. Если вы проанализируете QuickSort, то обнаружите, что его эффективность на самом деле зависит от качества сводной диаграммы, и всегда есть случаи, когда по случайности или преднамеренному злонамеренному воздействию O (N ^ 2) будет работать.

Но в целом сложность алгоритма D & C обусловлена ​​сочетанием затрат на решение подзадач и слияние решений. Возвращаясь к вашему вопросу, если стоимость объединения решений имеет порядок решения проблемы с наивным алгоритмом, ваш алгоритм D & C никогда не превзойдет наивный.

Вы можете (почти) всегда решить сложность некоторых алгоритмов D & C, используя теорему Мастера:

https://en.wikipedia.org/wiki/Master_theorem_ (analysis_of_algorithms)

D & C - это просто мета-стратегия для разработки алгоритмов, которые могут или не могут лучше решить определенную проблему; нет никакой гарантии «успеха», то есть более низкой сложности, намного менее низкой.

Например, QuickSort работает в рандомизированном логлиническом времени и имеет приемлемую среднюю производительность для сортировки массивов generic c на стандартном оборудовании, но превосходит другие алгоритмы для конкретных c случаев (таких как целочисленные массивы) или аппаратных архитектур (таких как массивно параллельные компьютеры).