¿Hay algún problema cuyo algoritmo más conocido tenga tiempo de ejecución

18

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?

Mike Izbicki
fuente
24
Mergesort, con . f(n)=nlog2n
Jeff
12
@ Jɛ ff E snarky Mcsnarkster
Suresh Venkat
55
Radix sort - realmente es . Lo que está sucediendo es que debido al acceso aleatorio, puedes guardar un factor de registro ...O(nlogn/logn)
Sariel Har-Peled
Me pregunto si el teorema de la jerarquía DTIME puede usarse como argumento hacia la existencia de tales algoritmos, dado que se puede hacer un truco similar para ahorrar espacio en el modelo RAM.
chazisop

Respuestas:

41

La respuesta habitual a "¿qué puede hacer que se divida por un registro?" es una combinación de dos cosas:

  1. un modelo de cómputo en el que se permiten operaciones aritméticas de tiempo constante en enteros del tamaño de una palabra, pero en el que desea ser conservador acerca de cuánto duran las palabras, por lo que asume bits por palabra (porque menos de eso y ni siquiera podría abordar toda la memoria, y también porque los algoritmos que usan búsquedas de tablas tomarían demasiado tiempo para configurar las tablas si las palabras fueran más largas), yO(logn)
  2. un algoritmo que comprime los datos al empaquetar bits en palabras y luego opera en las palabras.

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)

David Eppstein
fuente
35

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á 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).Θ(n2/logn)

[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.

SamM
fuente
16

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 )lognO(n2loglogn/logn)

Suresh Venkat
fuente
55
Esta es una instancia más compleja de la técnica "Cuatro rusos" descrita en la respuesta de David.
Jeff
13

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 }d{1,,k}{1,,k}d{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}Θ(k2d1)Θ(k2d1/logk)logk

Yuval Filmus
fuente
12

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.

Joshua Grochow
fuente
8

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 )nO((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).

MCH
fuente
44
Nuevamente, creo que esta es una variación del algoritmo de los Cuatro Rusos.
David Eppstein
7

Θ(n/logn) aparece como el límite correcto para un problema considerado por Greg y Paul Valiant (sin conexión con trucos de bits):

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.

Jelani Nelson
fuente
7

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).

El tamaño de la fórmula (sobre la base binaria completa o la base de De Morgan) del problema de distinción de elementos es , donde es el número de bits en la entrada.Θ(n2/logn)n

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 entradampoly(m)n:=O(mlogm)O(logm)mΘ(m2logm)Θ(n2/logn)nn

Robin Kothari
fuente
2

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))

dspyz
fuente
3
De hecho, es suficiente mirar los aproximadamente primos debajo de . Pero hay algoritmos mucho mejores por ahí. 2n/lognn
Yuval Filmus
-2

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)=nO(nlogn)

vzn
fuente
2
en una TM, es trivial ya que no permite que la máquina lea toda la entrada. Además, la notación DTIME hace innecesaria la notación big-oh. DTIME(n/logn)
Sasho Nikolov
?? todavía hay teoría para algoritmos de tiempo sublineales ...
vzn
3
Algoritmos sublineales tienen sentido en Oracle y modelos de acceso aleatorio. DTIME se define de forma estándar wrt multitape TM, y esa es la definición utilizada en el teorema de la jerarquía para DTIME.
Sasho Nikolov
1
DTIME(n/logn)n/lgnn/lgn
55
n/lgnO(n/logn)nnf(n)<nDTIME(f(n))kk