Nunca antes había visto un algoritmo con un registro en el denominador, y me pregunto si hay algún algoritmo realmente útil con este formulario.
Entiendo muchas cosas que podrían hacer que un factor de registro se multiplique en el tiempo de ejecución, por ejemplo, algoritmos de clasificación o basados en árboles, pero ¿qué podría hacer que se divida por un factor de registro?
ds.algorithms
big-list
time-complexity
Mike Izbicki
fuente
fuente
Respuestas:
La respuesta habitual a "¿qué puede hacer que se divida por un registro?" es una combinación de dos cosas:
Creo que hay muchos ejemplos, pero el ejemplo clásico es el Algoritmo de los cuatro rusos para subsecuencias comunes más largas, etc. En realidad termina siendo , porque usa la idea de empaquetamiento de bits pero luego guarda un segundo factor de registro utilizando otra idea: reemplazar bloques de operaciones de bit por una sola búsqueda de tabla.O ( log 2 n )O ( n2/ log2n ) O ( log2n )
fuente
El cubo de Rubik es un ejemplo muy natural (y para mí, inesperado). Un cubo requiere pasos de para resolverlo. (Tenga en cuenta que esta es la notación theta, por lo que es un límite superior e inferior estrecho).n × n × n Θ ( n2/ logn )
Esto se muestra en este documento [1].
Vale la pena mencionar que la complejidad de resolver instancias específicas del cubo de Rubik estáΘ ( n2/ logn )
abierta, pero se conjetura que es NP-hard (discutido aquí por ejemplo)NP hard [2]. El algoritmo garantiza una solución y garantiza que todas las soluciones son asintóticamente óptimas, pero es posible que no resuelva instancias específicas de manera óptima. Su definición de útil puede o no aplicarse aquí, ya que los cubos de Rubik generalmente no se resuelven con este algoritmo ( el algoritmo de Kociemba generalmente se usa para cubos pequeños, ya que proporciona soluciones rápidas y óptimas en la práctica).[1] Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw y Andrew Winslow. Algoritmos para resolver los cubos de Rubik. Actas del 19º Simposio europeo anual sobre algoritmos (ESA 2011), del 5 al 9 de septiembre de 2011, páginas 689–700
[2] Erik D. Demaine, Sarah Eisenstat y Mikhail Rudoy. Resolver el cubo de Rubik de manera óptima es NP-completo. Actas del 35 ° Simposio internacional sobre aspectos teóricos de la informática (STACS 2018), 28 de febrero al 3 de marzo de 2018, páginas 24: 1-24: 13.
fuente
Un ejemplo de que aparece en el denominador sin trucos de empaque de bits es un artículo reciente de Agarwal, Ben Avraham, Kaplan y Sharir sobre el cálculo de la distancia discreta de Fréchet entre dos cadenas poligonales en el tiempo . Si bien no estoy familiarizado con los detalles del algoritmo, un truco general es dividir la entrada en partes relativamente pequeñas y luego combinar las respuestas inteligentemente (por supuesto, esto suena como dividir y conquistar, pero no obtienes el registro n en el denominador con algunos trucos ingeniosos)O ( n 2 log log n / log n )Iniciar sesiónnorte O ( n2Iniciar sesiónIniciar sesiónn / logn )
fuente
No es exactamente lo que solicitó, pero una situación "en la naturaleza" en la que aparece un factor logarítmico en el denominador es el documento " Guijarros y programas de ramificación para la evaluación de árboles " por Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman y Rahul Santhanam.
El problema de evaluación de árbol (TEP) es: dado un árbol de -anotado anotado con valores en en las hojas y funciones en los nodos internos, evalúe el árbol. Aquí cada nodo interno obtiene el valor de su función anotada en los valores de sus hijos. Este es un problema fácil, y el punto es mostrar que no se puede resolver en el espacio logarítmico (cuando la altura del árbol es parte de la entrada). A tal efecto, estamos interesados en el tamaño de los programas de ramificación que resuelven TEP.{ 1 , ... , k } { 1 , ... , k } d → { 1 , ... , k }re { 1 , ... , k } { 1 , ... , k }re→ { 1 , ... , k }
En la Sección 5, se presentan límites estrechos para árboles de altura 3, tanto para TEP como para el problema relacionado BEP, en el que la salida se contrae a de alguna manera arbitraria. Para TEP, el límite es , mientras que para BEP el límite es , es decir, obtiene un ahorro de .Θ ( k 2 d - 1 ) Θ ( k 2 d - 1 / log k ) log k{ 0 , 1 } Θ ( k2 d- 1) Θ ( k2 d- 1/ logk ) Iniciar sesiónk
fuente
Aunque no se trata del tiempo de ejecución, pensé que valía la pena mencionar el resultado clásico de Hopcroft, Paul y Valiant: [1], ya que sigue en el espíritu de "lo que podría hacer que guarde un factor de registro".TIME[t]⊆SPACE[t/logt]
Eso proporciona muchos ejemplos de problemas cuyo límite superior más conocido en la complejidad del espacio tiene un registro en el denominador. (Dependiendo de su punto de vista, creo que esto hace que este ejemplo sea muy interesante, ¡qué teorema increíble! O muy poco interesante, probablemente no sea "realmente útil").
[1] Hopcroft, Paul y Valiant. En el tiempo versus el espacio . J. ACM 24 (2): 332-337, 1977.
fuente
Hay dos problemas con la complejidad de consultas estrictas :Θ(n/logn)
fuente
El algoritmo más conocido para calcular la distancia de edición (también conocida como Levenshtein) entre dos cadenas de longitud toma tiempo:O ( ( n / log n ) 2 )n O((n/logn)2)
William J. Masek, Mike Paterson: una secuencia de cálculo de algoritmo más rápido Editar distancias. J. Comput. Syst. Sci. 20 (1): 18-31 (1980).
fuente
Gregory Valiant y Paul Valiant, El poder de los estimadores lineales, 2011. En el 52º Simposio anual de IEEE sobre los fundamentos de la informática, FOCS 2011.
fuente
Aquí hay otro ejemplo de un apretado límite que tiene un factor log (Este es el teorema 6.17 de la complejidad de la función booleana: avances y fronteras de Stasys Jukna).
La razón por la que el factor log aparece en el denominador es que representar enteros entre 1 y requiere bits en total, ya que cada entero requiere bits Entonces, un límite superior que parece natural en términos de , como , se convierte en cuando se expresa en términos de , donde es el número de bits en la entradam poly(m) n:=O(mlogm) O(logm) m Θ(m2logm) Θ(n2/logn) n n
fuente
Encontrar los factores primos de n por división de prueba cuando la lista de primos ya está dada. Hay primos menores que n, por lo que si se le dan estos primos, entonces la división de prueba de n por cada uno de ellos toma tiempo (suponiendo que la división es una operación de tiempo constante)θ(nlog(n)) θ(nlog(n))
fuente
algo similar a la respuesta de JG y "pensar fuera de la caja", esto parece un resultado negativo relacionado / relevante / a propósito / fundamental . basado en la diagonalización con una TM universal, existe un lenguaje DTIME que no puede ejecutarse en DTIME, debido al teorema de la jerarquía del tiempo . así que esto se aplica a un algoritmo DTIME lineal que existe, , que se ejecuta imposiblemente en DTIME .O ( f ( n )O(f(n)) f(n)=nO(nO(f(n)logf(n)) f(n)=n O(nlogn)
fuente