Логарифмическая и двойная логарифмическая сложность времени

Question

В приложениях в реальном мире есть конкретное преимущество при использовании $ mathcal {o} ( log ( log (n)) $ вместо $ mathcal {o} ( log (n)) $ алгоритмы?

Это тот случай, когда один из них использует, например, деревья Ван Эмде Боас вместо более обычных реализаций дерева бинарного поиска. Но, например, если мы возьмем $ N <10^6 $, то в лучшем случае двойной логарифмический алгоритм превосходит логарифмический, примерно) коэффициентом $ 5 $. А также в целом реализация более сложная и сложная.

Учитывая, что я лично предпочитаю BST, а не Vib-деревья, что вы думаете?

Можно легко продемонстрировать, что:

$ qquad displaystyle forall n <10^6. frac { log n} { log ( log (n))} <5.26146 $

Answer 1

Не забывайте, что $ log n $ по -прежнему растет экспоненциально (в $ log (n) $) быстрее, чем $ log ( log n) $!

Действительно, если вы посмотрите на коэффициент $ log (n) $ и $ log ( log (n)) $, это не так впечатляет: увидеть:

^{[источник]}

Но, тем не менее, вы получаете фактор пять -шесть за размеры до 100000 долларов. Обратите внимание, что большие размеры не редкость на практике, и ускорение этого фактора является Потрясающие! Это может иметь значение между получением результатов после обеда или только завтра. Имейте в виду, что часть ускорения может быть съедена более высокими константами реализации дерева; Вам нужно будет построить (или анализировать) $ c cdot log (n) $ и $ d cdot log ( log (n)) $ с $ c, d $ фактические константы времени выполнения, чтобы получить реальную картину.

Кроме того, то, что Дэйв упоминает, важно: если операция ускорялась, так же, скажем, линейно, постоянные ускорения становятся линейными ускорением, то есть вы можете уменьшить ведущую константу всего вашего алгоритма! Как я уже сказал, это потрясающе. Просто посмотрите, что произойдет, если вы запустите операцию $ n $ times:

^{[источник]}

Теперь, если это не стоит проблем, я не знаю, что.

Answer 2

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

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

Answer 3

Я на самом деле однажды я сравнивал дерево Ван Эмде-Боаса. Я сравнил его с деревом АА, хэшматой и небольшим количеством массива.

Тесты выполняют size вставки со случайными числами в интервале [0, bound], тогда size Поиск, тогда size Удаляет, а затем снова size Поиск. Удаленные также выполняются и на случайных числах, поэтому вам сначала нужно выяснить, находятся ли они в структуре вообще.

Вот результаты (size=2000000, bound= 10000000) в секундах:

AATreeLookup - O(n log n)
Inserting... 3.3652452
Searching... 5.2280724
Deleting...  7.3457427
Searching... 9.1462039
HashLookup - O(n) expected
Inserting... 0.3369505
Searching... 0.6223035
Deleting...  0.9062163
Searching... 1.1718223
VanEmdeBoasTree - O(n log log n)
Inserting... 0.7007531
Searching... 1.1775800
Deleting...  1.7257065
Searching... 2.2147703
ArrayLookup - O(n)
Inserting... 0.0681897
Searching... 0.1720300
Deleting...  0.2387776
Searching... 0.3413800

Как вы можете видеть, деревья Ван Эмде-Боас примерно в два раза медленнее, чем хеш-карты, в десять раз медленнее, чем битовые массивы, и в 5 раз быстрее, чем бинарные поисковые деревья.

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

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

Теперь, в случае $ log n $ против $ log log n $: В приведенном выше примере мое дерево Ван Эмде-Боас может содержать $ 2^{32} $. $ log 2^{32} = 32 $, и $ log 32 = 5 $, что является улучшением фактора 6, которое на практике довольно мало. Кроме того, деревья Ван Эмде-Боас обладают хорошими постоянными факторами (все это касается постоянных факторов на практике для различий в таких маленьких), поскольку им не нужно сбалансировать себя.