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

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

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

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

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

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

Не забывайте, что прежнему растет в геометрической прогрессии (в log ( n ) ) быстрее, чем log ( log n ) !$\log n$$\log(n)$$\log(\log n)$

В самом деле, если вы посмотрите на отношения и log ( log ( n ) ) , не так уж много впечатляющего:$\log(n)$$\log(\log(n))$

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

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

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

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

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

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

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

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

Тесты выполняют 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$