Скрытые константы в сложности алгоритмов

Для многих задач алгоритм с наилучшей асимптотической сложностью имеет очень большой постоянный коэффициент, который скрыт большими обозначениями O. Это происходит в матричном умножении, целочисленном умножении (в частности, недавнем алгоритме умножения целых чисел O (n log n) Харви и Ван-дер-Хувена), в сетях с малой глубиной сортировки и нахождении второстепенных графов. Такие алгоритмы иногда называют галактическими алгоритмами.

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

Какие исследования были проведены при отделении первых алгоритмов от последних с теоретической точки зрения?

Мне известно, что скрытые константы часто опускаются, чтобы скрыть различия между различными моделями вычислений. Однако я уверен, что при большом разнообразии моделей эти галактические алгоритмы будут работать медленнее, чем асимптотически худшие алгоритмы, например, для входных данных размером один миллиард. Различие не является тонким, в некоторых случаях. Это было сделано строго?

Например, можно изобрести очень простую модель вычислений, такую как машина фон Неймана с очень простым ISA, а затем реализовать алгоритмы и связать их время выполнения с явными константами. Было ли это сделано для различных алгоритмов?

cc.complexity-theory ds.algorithms time-complexity isaacg
источник

Алгоритмы быстрого целочисленного умножения не являются галактическими. Они на самом деле обычно используются на практике.

Эмиль Йержабек

@ EmilJeřábek Может быть, ОП говорит о недавнем прорыве Дэвида Харви и Йориса ван дер Хувена, «Целочисленное умножение за время », которое является галактическим (см. Эту запись в блоге Липтона, например: rjlipton .wordpress.com / 2019/03/29 /… )

O (n \log n)

$O(n \log n)$

Ламин

Поскольку авторы пишут сами (и упоминается в блоге Липтона), статья для простоты не пытается оптимизировать константы, но их, скорее всего, можно сделать практичными.

Эмиль Йержабек

@ EmilJeřábek Эта газета действительно была той, о которой я говорил. В статье описываются улучшения, которые могут быть сделаны, но крайне сомнительно, что алгоритм как таковой когда-либо будет практическим улучшением по сравнению с текущими алгоритмами O (n log n log log n), которые используются на практике, учитывая, как мало log log n для практического вклада.

Исаак

@ EmilJeřábek В частности, алгоритм, представленный в статье, относится к более простому алгоритму для базового случая, когда число имеет менее битов, где в настоящее время они принимают . Оптимизация, которую они описывают, может позволить им вместо этого использовать , но битов по-прежнему превышает число частиц во вселенной, поэтому практичность по-прежнему не обсуждается. Смотрите раздел 5.4 их статьи.

2^{d^{12}}

$2^{d^{12}}$

d = 1729

$d=1729$

d = 9

$d=9$

2^{9^{12}}

$2^{9^{12}}$

Исаак

Ответы:

В аналитической комбинаторике одним из интересных мест, где к этому подходу интересно подходят некоторые классы алгоритмов и комбинаторные задачи . Описанный основной подход аналогичен тому, что вы предлагаете: вы начинаете с какой-то конкретной реализации алгоритма и идентифицируете некоторые повторяющиеся операции (обычно наиболее тяжелые), которые вы будете использовать, чтобы связать явно исчисляемую сложность для выполнения ввода заданного значения. размер $N$ в виде числа $C_N$ что выбранная операция выполнена.

Методология не требует исправления какой-либо конкретной модели вычислений, хотя это может быть полезно, конечно. Также обратите внимание, что вы можете попытаться вычислить поведение наихудшего случая или ожидаемое поведение, или еще что-то еще.

Важнейшим компонентом этой методологии является анализ производящих функций этих значений. Иногда вы можете получить очень точные асимптотические приближения, используя методы комплексного анализа.

Простой пример, который рассматривается в книге, это быстрая сортировка. Это имеет квадратичное время выполнения в худшем случае, но на практике превосходит большинство $\mathcal O(n\log n)$ алгоритмы. Делая точный анализ ожидаемой стоимости быстрой сортировки и сравнивая ее с сортировкой слиянием, вы видите, что ожидается, что она превзойдет последнюю с размером около 10, если я правильно помню. Чтобы иметь возможность вычислять такие вещи, вы, конечно, не можете игнорировать скрытые константы.

Фактически, в быстрой сортировке вы сортируете список путем рекурсивной сортировки подсписков, так что вы получите улучшение для всех размеров, если вы используете mergesort для списков, меньших, чем 10. Интересное примечание в книге упоминает, что в некоторой библиотеке Microsoft с открытым исходным кодом, универсальный алгоритм сортировки реализован как быстрая сортировка, пока вы не достигнете размера 10, после чего используется сортировка слиянием. В комментариях к коду упоминается, что тесты производительности показали, что это значение является оптимальным.

doetoe
источник