Алгоритмы «разделяй и властвуй» - почему бы не разделить их на две части?

В алгоритмах «разделяй и властвуй», таких как быстрая сортировка и сортировка слиянием, ввод обычно (по крайней мере, во вводных текстах) делится на две части , и два меньших набора данных затем обрабатываются рекурсивно. Для меня имеет смысл, что это ускоряет решение проблемы, если две половины занимают меньше половины работы над всем набором данных. Но почему бы не разбить набор данных на три части? Четыре? н ?

Я предполагаю, что работа по разделению данных на множество подмножеств делает это не стоящим, но мне не хватает интуиции, чтобы увидеть, что нужно остановиться на двух подмножествах.

Я также видел много ссылок на трехстороннюю быструю сортировку. Когда это быстрее? Что используется на практике?

Для меня имеет смысл, что это ускоряет решение проблемы, если две половины занимают меньше половины работы над всем набором данных.

Это не суть алгоритмов «разделяй и властвуй». Обычно дело в том, что алгоритмы не могут «иметь дело со всем набором данных» вообще. Вместо этого он разбивается на части, которые тривиально решить (например, сортировка двух чисел), затем они решаются тривиально, а результаты объединяются таким образом, чтобы получить решение для полного набора данных.

Но почему бы не разбить набор данных на три части? Четыре? п?

Главным образом потому, что разбиение его на более чем две части и рекомбинация более двух результатов приводит к более сложной реализации, но не меняет фундаментальную (Big O) характеристику алгоритма - разница является постоянным фактором и может привести к замедлению если деление и рекомбинация более чем двух подмножеств создает дополнительные издержки.

Например, если вы выполняете трехстороннюю сортировку слиянием, то на этапе рекомбинации вы должны найти самый большой из 3 элементов для каждого элемента, который требует 2 сравнений вместо 1, так что вы сделаете в два раза больше сравнений в целом , Взамен вы уменьшаете глубину рекурсии на коэффициент ln (2) / ln (3) == 0,63, поэтому у вас на 37% меньше свопов, но на 2 * 0,63 == 26% больше сравнений (и обращений к памяти). Хорошо это или плохо, зависит от того, какое оборудование дороже.

Я также видел много ссылок на трехстороннюю быструю сортировку. Когда это быстрее?

Очевидно, что вариант быстрой сортировки с двумя опорными точками может потребовать такого же количества сравнений, но в среднем на 20% меньше свопов, так что это чистый выигрыш.

Что используется на практике?

В наши дни почти никто не программирует свои собственные алгоритмы сортировки; они используют один предоставленный библиотекой. Например, API Java 7 на самом деле использует быструю сортировку с двойным поворотом.

Люди, которые на самом деле по какой-то причине программируют собственный алгоритм сортировки, будут склонны придерживаться простого двухстороннего варианта, поскольку меньшая вероятность ошибок в большинстве случаев превышает производительность на 20%. Помните: безусловно самое важное улучшение производительности - это когда код переходит от «не работает» к «работает».

Асимптотически это не имеет значения. Например, бинарный поиск делает приблизительно log ₂  n сравнений, а троичный поиск - приблизительно log ₃  n сравнений. Если вы знаете свои логарифмы, вы знаете, что log _a  x = log _b  x / log _b  a, поэтому бинарный поиск составляет всего около 1 / log ₃ 2 ≈ 1,5 раза больше сравнений, чем троичный поиск. Это также причина, по которой никто никогда не указывает основание логарифма в больших обозначениях Oh: это всегда постоянный фактор, отличный от логарифма в данной базе, независимо от того, что является базовой действительностью. Таким образом, разбиение задачи на большее количество подмножеств не увеличивает временную сложность и практически не позволяет перевесить более сложную логику. Фактически, эта сложность может отрицательно сказаться на практической производительности, увеличивая нагрузку на кэш или делая микрооптимизации менее осуществимыми.

С другой стороны, некоторые древовидные структуры данных действительно используют высокий коэффициент ветвления (намного больше, чем 3, часто 32 или больше), хотя обычно по другим причинам. Это улучшает использование иерархии памяти: структуры данных, хранящиеся в RAM, лучше используют кеш, структуры данных, хранящиеся на диске, требуют меньше операций чтения HDD-> RAM.

Существуют алгоритмы поиска / сортировки, которые делятся не на два, а на N.

Простой пример - поиск по хеш-кодированию, который занимает O (1) времени.

Если хеш-функция сохраняет порядок, ее можно использовать для создания алгоритма сортировки O (N). (Вы можете думать о любом алгоритме сортировки как о том, что просто выполняете N поисков, где число должно идти в результате.)

Фундаментальный вопрос заключается в том, что когда программа проверяет некоторые данные, а затем переходит в несколько следующих состояний, сколько существует следующих состояний и насколько близки к ним вероятности?

Когда компьютер сравнивает два числа, скажем, и затем либо скачет, либо нет, если оба пути одинаково вероятны, счетчик программы «знает» еще один бит информации о каждом пути, поэтому в среднем он «выучил» один немного. Если проблема требует изучения M битов, то при использовании двоичных решений он не может получить ответ в меньшем количестве, чем M решений. Так, например, поиск числа в отсортированной таблице размером 1024 не может быть выполнен при меньшем числе десяти двоичных решений, хотя бы потому, что у любого меньшего числа будет недостаточно результатов, но это, безусловно, можно сделать больше.

Когда компьютер берет одно число и преобразует его в индекс в массив, он «запоминает» до записи в базу 2 количество элементов в массиве и делает это за постоянное время. Например, если существует таблица переходов из 1024 записей, все более или менее одинаково вероятны, то переход через эту таблицу «запоминает» 10 битов. Это основной трюк за хеш-кодированием. Примером сортировки является то, как вы можете сортировать колоду карт. Имейте 52 лотка, по одному на каждую карту. Сложите каждую карту в корзину, а затем выкопайте их все. Подразделение не требуется.

Так как это вопрос общего разделяй и властвуй, а не просто сортировки, я удивлен, что никто не поднял основную теорему

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

Карацуба алгоритм умножения использует 3-полосная разделяй и властвуй , чтобы достигнуть время работы O (3 п ^ log_2 3) , который бьет в O (N ^ 2) для обычного алгоритма умножения (п число цифр в номера).

Из-за своей двоичной природы компьютер очень эффективен при делении вещей на 2, а не на 3 в 3. Вы получаете деление на 3, сначала делив на 2, а затем снова делите одну из частей на 2. Так что если вам нужно разделить на 2, чтобы получить 3 дивизии, вы можете разделить на 2.