Logarítmica vs doble complejidad de tiempo logarítmica

Question

En las aplicaciones del mundo real es que hay un beneficio concreto cuando se usa $ \ mathcal {O} (\ log (\ log (n)) $ en lugar de $ \ mathcal {O} (\ log (n)) $ algoritmos

Este es el caso cuando uno de los usos para los árboles van ejemplo Emde Boas en lugar de implementaciones árbol binario de búsqueda más convencionales. Pero por ejemplo, si tomamos $ n <10 ^ 6 $ a continuación, en el mejor de los casos el algoritmo de doble logarítmica supera el logarítmica de (aproximadamente) un factor de $ 5 $. Y también, en general, la aplicación es más difícil y compleja.

Dado que yo personalmente prefiero BST más de VEB-árboles, ¿qué te parece?

Uno podría fácilmente demostrar que:

$ \ qquad \ displaystyle \ forall n <10 ^ 6. \ \ Frac {\ log n} {\ log (\ log (n))} <5,26146 $

Answer 1

No se olvide que $ \ log n $ todavía crece exponencialmente (en $ \ log (n) $) más rápido que $ \ log (\ log n) $!

De hecho, si nos fijamos en el cociente de $ \ log (n) $ y $ \ log (\ log (n)) $, no hay mucho impresionante ver:

^{[ fuente ]}

Pero aún así, se obtiene un factor de cinco y cincuenta y cinco minutos para tamaños de hasta $ 100000 $. Tenga en cuenta que los tamaños más grandes no son infrecuentes en la práctica, y una aceleración por ese factor es impresionante ! Se puede hacer la diferencia entre tener resultados después del almuerzo o únicamente mañana. Tenga en cuenta que parte del aumento de velocidad puede ser devorado por las constantes más altos de la implementación del árbol; que tendría que trama (o analizar) $ c \ cdot \ log (n) $ y $ d \ cdot \ log (\ log (n)) $ con $ c, d $ las constantes de tiempo de ejecución reales para obtener una imagen real.

Además, menciona lo que Dave es importante: si la operación se aceleró thusly se ejecuta, por ejemplo, a menudo de forma lineal, aceleraciones constantes se convierten en aceleraciones lineales, es decir, es posible que disminuya la constante principal de toda su algoritmo! Como he dicho anteriormente, es impresionante. Basta con mirar lo que ocurre si se ejecuta la operación de $ n $ veces:

^{[ fuente ]}

Ahora bien, si eso no es vale la pena, no sé qué.

Answer 2

Uno podría imaginar que la diferencia en la complejidad realmente no importa mucho, y que el tiempo de ejecución real es más importante. Pero si el algoritmo está en el núcleo de otro algoritmo, entonces esta diferencia puede ser importante.

Desde un propósito puramente teórico, la diferencia, por supuesto, es importante, especialmente si el algoritmo es una parte de otro. Se puede poner el algoritmo de mayor complejidad en una clase diferente.

Answer 3

he hecho como punto de referencia la furgoneta Emde-Boas árbol de mi mismo una vez. He comparado con un árbol de AA, un HashMap y una matriz de bits.

Las pruebas realizar inserciones size con números aleatorios en el [0, bound] intervalo, entonces búsquedas size, a continuación, elimina size y luego de nuevo búsquedas size. Eliminaciones se realizan en los números al azar, así, por lo que primero tiene que averiguar si se encuentran en la estructura del todo.

Estos son los resultados (size = 2.000.000, bound = 10000000) en segundos:

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

Como se puede ver, los árboles van Emde-Boas son aproximadamente dos veces más lento como mapas de patata, diez veces tan lento como matrices de bits, y 5 veces más rápido que los árboles binarios de búsqueda.

Por supuesto, la necesidades por encima de un descargo de responsabilidad:. Las pruebas son artificiales, posiblemente pueda mejorar el código o utiliza un lenguaje diferente con un compilador cuya salida es más rápido, y así sucesivamente y así sucesivamente

Esta exención de responsabilidad está en el corazón de la razón por la que utilizamos análisis asintótico en los algoritmos de diseño: como no tienes idea de lo que las constantes son y como las constantes puede cambiar dependiendo de factores ambientales, lo mejor que podemos hacer es un análisis asintótico.

Ahora, en el caso de $ \ log n $ contra $ \ log \ log n $: en el ejemplo anterior, mi árbol de Van Emde-Boas es capaz de contener $ 2 ^ {32} $ elementos. $ \ Log ^ {2} 32 = 32 $ y $ \ log 32 = 5 $, que es una mejora del factor de 6, que es un poco en la práctica. Además, los árboles van Emde-Boas tienen buenas factores constantes (es todo acerca de los factores constantes en la práctica de esta pequeña diferencia) ya que no se necesitan para mantener el equilibrio.