Estaba pasando por algunas estructuras de datos y noté esto como una complejidad de tiempo: O (log (log (n)))) - competitivo.¿Qué significa O (log (log (n)))) - competitivo?
He leído que constante-competitiva fue la relación del tiempo esperado/tiempo óptimo. Pero, ¿qué significa tener un conjunto competitivo?
Algoritmo en línea es aquel que no conoce sus entradas por adelantado, y debe "reaccionar" (en cierto sentido) a entradas impredecibles. Por el contrario, los algoritmos fuera de línea son aquellos que conocen todas sus entradas por adelantado.
El análisis competitivo compara el rendimiento de un algoritmo en línea óptimo con un algoritmo fuera de línea óptimo. Por lo tanto, k-competitive significa que hay un algoritmo fuera de línea que funciona como mucho k-veces peor que un algoritmo en línea. Entonces, O (lglgn) competitivo significa que el algoritmo fuera de línea óptimo realiza a lo sumo lglgn (veces una constante) veces peor que el algoritmo en línea óptimo.
El término "k-competitive" se puede considerar de la misma manera que el término "k-approximation". Una aproximación k significa que el algoritmo de aproximación realiza a lo sumo k veces más que el algoritmo óptimo.
This puede arrojar algo de luz sobre su pregunta.
Desde el enlace de arriba:
Sea A cualquier algoritmo de BST, definir A (S) como el coste de realizar secuencia S y OPT (S, A) ya que el coste mínimo para realizar la secuencia S. Un algoritmo A es competitivo T si para todas las secuencias posibles S, A (S) < = T * OPT (S, To) + O (m, n).
¿Puedes mejorar la pregunta? –
¿Se puede mejorar al menos O (log (log (N)))? –