Constantes ocultas en la complejidad de los algoritmos

9

Para muchos problemas, el algoritmo con la mejor complejidad asintótica tiene un factor constante muy grande que está oculto por la notación O grande. Esto ocurre en la multiplicación de matrices, la multiplicación de enteros (específicamente, el reciente algoritmo de multiplicación de enteros O (n log n) de Harvey y van der Hoeven), las redes de clasificación de baja profundidad y la búsqueda de gráficos menores, para hacer algunos. Tales algoritmos a veces se llaman algoritmos galácticos.

Tenga en cuenta que para otros algoritmos, como la clasificación general y la suma de enteros, los algoritmos se conocen con una complejidad asintótica óptima y pequeños factores constantes.

¿Qué investigación se ha hecho para separar los algoritmos anteriores de los últimos algoritmos, desde una perspectiva teórica?

Soy consciente de que las constantes ocultas a menudo se omiten para ocultar la distinción entre diferentes modelos de cálculo. Sin embargo, estoy seguro de que, bajo una amplia variedad de modelos diferentes, estos algoritmos galácticos serán más lentos que los algoritmos asintóticamente peores para entradas de un tamaño de mil millones, por ejemplo. La distinción no es sutil, en algunos casos. ¿Se ha hecho riguroso?

Por ejemplo, uno podría inventar un modelo de cómputo muy simple, como una máquina von Neumann con un ISA muy simple, y luego implementar los algoritmos y vincular sus tiempos de ejecución con constantes explícitas. ¿Se ha hecho esto para una variedad de algoritmos?

isaacg
fuente
1
Los algoritmos de multiplicación de enteros rápidos no son galácticos. En realidad, se usan comúnmente en la práctica.
Emil Jeřábek
2
@ EmilJeřábek Puede que el OP esté hablando sobre el reciente avance de David Harvey y Joris van der Hoeven, "Multiplicación de enteros en el tiempo ", que es galáctico (vea esta entrada del blog de Lipton por ejemplo: rjlipton .wordpress.com / 2019/03/29 / ... )O(norteIniciar sesiónnorte)
Lamine
1
A medida que los autores se escriben a sí mismos (y se menciona en el blog de Lipton), el documento por simplicidad no intenta optimizar las constantes, pero es muy probable que puedan hacerse prácticas.
Emil Jeřábek
@ EmilJeřábek Ese documento fue de hecho del que estaba hablando. El documento describe las mejoras que podrían hacerse, pero es extremadamente dudoso que el algoritmo como sea sea una mejora práctica sobre los algoritmos actuales O (n log n log log n) que se usan en la práctica, dado lo pequeño que es log log n es para insumos prácticos.
isaacg
44
@ EmilJeřábek Específicamente, el algoritmo presentado en el documento difiere a un algoritmo más simple para un caso base siempre que el número tenga menos de bits, donde actualmente toman . Las optimizaciones que describen podrían permitirles usar lugar, pero bits aún exceden el número de partículas en el universo, por lo que la practicidad aún está fuera de discusión. Ver la Sección 5.4 de su trabajo. d = 1729 d = 9 2 9 122re12re=1729re=9 929 912
isaacg

Respuestas:

2

Un lugar donde se aborda esto de una manera interesante para una determinada clase de algoritmos y problemas combinatorios es en la combinatoria analítica . El enfoque principal descrito es similar a lo que sugiere: comienza con una implementación concreta de un algoritmo e identifica alguna operación repetida (generalmente la más pesada) que usará para asociar una complejidad explícitamente contable para la ejecución de la entrada de un determinado tamaño en la forma del número que se realiza la operación elegida.norteCnorte

La metodología no requiere arreglar ningún modelo específico de computación, aunque eso podría ser útil, por supuesto. También tenga en cuenta que puede intentar calcular el comportamiento del peor de los casos o el comportamiento esperado, o aún algo más.

El ingrediente más importante en esta metodología es el análisis de las funciones generadoras de estos valores. A veces puede obtener aproximaciones asintóticas muy precisas utilizando métodos de análisis complejo.

Un ejemplo simple que se trata en el libro es quicksort. Esto tiene un tiempo de ejecución cuadrático en el peor de los casos, pero en la práctica supera a la mayoría de los algoritmos . Al hacer un análisis preciso del costo esperado de quicksort y lo compara con mergesort, ve que se espera que supere a este último de un tamaño de alrededor de 10, si no recuerdo mal. Para poder calcular este tipo de cosas, por supuesto, no puede ignorar las constantes ocultas.O(norteIniciar sesiónnorte)

De hecho, en la clasificación rápida, ordena una lista ordenando recursivamente las sublistas, de modo que obtendrá una mejora para todos los tamaños si usa mergesort en listas más pequeñas que el tamaño 10. Una nota interesante en el libro menciona que en alguna biblioteca de Microsoft de código abierto, el algoritmo de ordenación genérico se implementa como ordenación rápida hasta que se reduce a un tamaño de 10, después de lo cual se usa mergesort. En los comentarios del código se menciona que las pruebas de rendimiento mostraron que este valor era óptimo.

doetoe
fuente