¿Hay algún caso en el que preferiría un algoritmo de complejidad de tiempo Big-O superior al inferior?

242

¿Hay algún caso en el que prefiera la O(log n)complejidad del O(1)tiempo a la complejidad del tiempo? O O(n)para O(log n)?

¿Tienes algún ejemplo?

V.Leymarie
fuente
67
Preferiría un O(log n)algoritmo a un O(1)algoritmo si entendiera el primero, pero no el último ...
Codor
14
Hay toneladas de estructuras de datos poco prácticas con operaciones O (1) de la informática teórica. Un ejemplo sería select () en bitvectors, que puede admitirse en o (n) espacio adicional y O (1) por operación, utilizando 5 capas de indirección. La búsqueda binaria simple combinada con O (1) rank () resulta ser más rápida en la práctica según el autor de la Succinct Data Structure Library
Niklas B.
17
Una menor complejidad asintótica no garantiza tiempos de ejecución más rápidos. Investigue la multiplicación de matrices para un ejemplo concreto.
Connor Clark
54
Además ... cualquier algoritmo se puede convertir a O (1), dada una búsqueda de tabla suficientemente grande;)
Connor Clark
19
@Hoten - ¡Asumiendo que la búsqueda de la tabla es O (1), lo cual no es un hecho para el tamaño de las tablas de las que estás hablando! :)
Jander

Respuestas:

267

Puede haber muchas razones para preferir un algoritmo con mayor complejidad de tiempo de O grande sobre el inferior:

  • La mayoría de las veces, la complejidad de Big-O más baja es más difícil de lograr y requiere una implementación calificada, mucho conocimiento y muchas pruebas.
  • big-O oculta los detalles sobre una constante : el algoritmo que funciona 10^5mejor desde el punto de vista de big-O que 1/10^5 * log(n)( O(1)vs O(log(n)), pero para el más razonable, nel primero funcionará mejor. Por ejemplo, la mejor complejidad para la multiplicación de matrices es O(n^2.373)pero la constante es tan alta que ninguna biblioteca computacional (que yo sepa) la use.
  • big-O tiene sentido cuando calculas sobre algo grande. Si usted necesita para ordenar serie de tres números, importa muy poco si se utiliza O(n*log(n))o O(n^2)algoritmo.
  • a veces la ventaja de la complejidad del tiempo en minúsculas puede ser realmente insignificante. Por ejemplo, hay un árbol de tango de estructura de datos que da una O(log log N)complejidad de tiempo para encontrar un artículo, pero también hay un árbol binario que encuentra lo mismo en él O(log n). Incluso para un gran número de n = 10^20la diferencia es insignificante.
  • La complejidad del tiempo no lo es todo. Imagine un algoritmo que se ejecuta O(n^2)y requiere O(n^2)memoria. Puede ser preferible con el O(n^3)tiempo y el O(1)espacio cuando la n no es realmente grande. El problema es que puedes esperar mucho tiempo, pero dudo mucho que puedas encontrar una RAM lo suficientemente grande como para usarla con tu algoritmo
  • La paralelización es una buena característica en nuestro mundo distribuido. Hay algoritmos que son fácilmente paralelizables, y hay algunos que no se paralelizan en absoluto. A veces tiene sentido ejecutar un algoritmo en 1000 máquinas básicas con una mayor complejidad que usar una máquina con una complejidad ligeramente mejor.
  • En algunos lugares (seguridad), la complejidad puede ser un requisito. Nadie quiere tener un algoritmo de hash que pueda hacer hash de manera increíblemente rápida (porque entonces otras personas pueden imponerle una fuerza bruta más rápido)
  • aunque esto no está relacionado con el cambio de complejidad, pero algunas de las funciones de seguridad deben escribirse de una manera para evitar ataques de tiempo . En su mayoría permanecen en la misma clase de complejidad, pero se modifican de una manera que siempre se necesita peor para hacer algo. Un ejemplo es comparar que las cadenas son iguales. En la mayoría de las aplicaciones, tiene sentido romper rápido si los primeros bytes son diferentes, pero en seguridad aún esperará hasta el final para contar las malas noticias.
  • alguien patentó el algoritmo de menor complejidad y es más económico para una empresa usar una mayor complejidad que pagar dinero.
  • Algunos algoritmos se adaptan bien a situaciones particulares. La ordenación por inserción, por ejemplo, tiene una complejidad de tiempo promedio de O(n^2), peor que la ordenación rápida o la fusión, pero como algoritmo en línea puede ordenar eficientemente una lista de valores a medida que se reciben (como entrada del usuario) donde la mayoría de los otros algoritmos solo pueden operar eficientemente en una lista completa de valores.
Salvador Dalí
fuente
66
Además, he visto algunas veces que las personas se centraron en el gran O de su algoritmo central, pero ignorando los costos de configuración. Crear una tabla hash, por ejemplo, puede ser más costoso que pasar por una matriz linealmente si no necesita hacerlo una y otra vez. De hecho, debido a la forma en que se construyen las CPU modernas, incluso algo como la búsqueda binaria puede ser tan rápido en arreglos ordenados como una búsqueda lineal: la creación de perfiles es una necesidad.
Luaan
@Luaan "De hecho, debido a la forma en que se construyen las CPU modernas, incluso algo como la búsqueda binaria puede ser tan rápido en matrices ordenadas como una búsqueda lineal: la creación de perfiles es una necesidad". ¡Interesante! ¿Puede explicar cómo la búsqueda binaria y la búsqueda lineal podrían tomar la misma cantidad de tiempo en una CPU moderna?
DJG
3
@Luaan - No importa, encontré esto: schani.wordpress.com/2010/04/30/linear-vs-binary-search
DJG
2
@DenisdeBernardy: No, en realidad no es así. Podrían ser algoritmos en P. E incluso si no lo fueran, bajo definiciones razonables de lo que significa paralelizar, eso tampoco implicaría P! = NP. Recuerde también que la búsqueda del espacio de posibles ejecuciones de una máquina de turing no determinista es bastante paralelizable.
einpoklum
228

Siempre existe la constante oculta, que puede ser inferior en el algoritmo O (log n ). Por lo tanto, puede funcionar más rápido en la práctica para datos de la vida real.

También hay problemas de espacio (por ejemplo, correr en una tostadora).

También existe una preocupación por el tiempo del desarrollador: O (log n ) puede ser 1000 veces más fácil de implementar y verificar.

Alistra
fuente
Bien gracias. Estaba pensando que también podría valer la pena considerar un algoritmo O (logn) para garantizar la estabilidad del programa (por ejemplo, en árboles binarios
autobalanceados
16
Un ejemplo que se me ocurre: para una matriz ordenada pequeña, sería más fácil y compacto para el programador implementar una función de búsqueda binaria que escribir una implementación completa de mapa hash y usarla en su lugar.
Coronel Treinta y Dos
55
Un ejemplo de complejidad: encontrar la mediana de una lista sin ordenar es fácil de hacer en O (n * log n) pero difícil de hacer en O (n).
Paul Draper
1
-1, no pongas troncos en tu tostadora ... Bromas aparte, esto es perfecto. lg nes tan, tan, tan kgrande nque la mayoría de las operaciones nunca notarían la diferencia.
corsiKa
3
También está el hecho de que las complejidades algorítmicas con las que la mayoría de las personas están familiarizadas no tienen en cuenta los efectos de caché. Buscar algo en un árbol binario es O (log2 (n)) según la mayoría de las personas, pero en realidad es mucho peor porque los árboles binarios tienen una mala localidad.
Doval
57

Me sorprende que nadie haya mencionado las aplicaciones vinculadas a la memoria todavía.

Puede haber un algoritmo que tenga menos operaciones de coma flotante, ya sea debido a su complejidad (es decir, O (1) < O (log n )) o porque la constante frente a la complejidad es menor (es decir, 2 n 2 <6 n 2 ) . De todos modos, aún puede preferir el algoritmo con más FLOP si el algoritmo FLOP más bajo está más ligado a la memoria.

Lo que quiero decir con "enlazado a memoria" es que a menudo está accediendo a datos que están constantemente fuera de la memoria caché. Para obtener estos datos, debe extraer la memoria de su espacio de memoria real en su caché antes de poder realizar su operación en ella. Este paso de recuperación suele ser bastante lento, mucho más lento que su propia operación.

Por lo tanto, si su algoritmo requiere más operaciones (sin embargo, estas operaciones se realizan en datos que ya están en caché [y, por lo tanto, no se requiere recuperación]), aún superará a su algoritmo con menos operaciones (que deben realizarse fuera de -cach datos [y por lo tanto requieren una búsqueda]) en términos de tiempo de pared real.

NoseKnowsAll
fuente
1
Alistra abordó esto indirectamente cuando habló de "preocupaciones espaciales"
Zach Saucier
2
La gran cantidad de errores de caché solo multiplica la ejecución final por un valor constante (que no es mayor que 8 para CPU de 4 núcleos a 3,2 GHz con ram de 1,6 GHz, generalmente es mucho menor), por lo que se cuenta como una constante fija en el gran -O notación. Por lo tanto, lo único que la memoria caché pierde es mover el umbral de n donde esa solución O (n) comienza a ser más lenta que la solución O (1).
Marian Spanik
1
@MarianSpanik Por supuesto, tienes razón. Pero esta pregunta pedía una situación en la que preferiríamos O(logn)más O(1). Podrías imaginar fácilmente una situación en la que, para todo lo que sea posible n, la aplicación menos vinculada a la memoria se ejecutaría en un tiempo de pared más rápido, incluso a una mayor complejidad.
NoseKnowsTodo el
@MarianSpanik ¿no se pierde un caché de hasta 300 ciclos de reloj? ¿De dónde viene el 8?
HopefulHelpful
43

En contextos donde la seguridad de los datos es una preocupación, un algoritmo más complejo puede ser preferible a un algoritmo menos complejo si el algoritmo más complejo tiene mejor resistencia a los ataques de sincronización .

Kevin K
fuente
66
Si bien lo que dijo es cierto, en ese caso, un algoritmo que se ejecuta en O (1) es, por definición, invulnerable a los ataques de tiempo.
Justin Lessard
17
@JustinLessard: Ser O (1) significa que hay un tamaño de entrada después del cual el tiempo de ejecución del algoritmo está limitado por una constante. Lo que sucede por debajo de este umbral es desconocido. Además, es posible que ni siquiera se alcance el umbral para el uso real del algoritmo. El algoritmo puede ser lineal y, por lo tanto, filtrar información sobre la longitud de la entrada, por ejemplo.
Jörg W Mittag
12
El tiempo de ejecución también puede fluctuar de diferentes maneras, sin dejar de ser limitado. Si el tiempo de ejecución es proporcional (n mod 5) + 1, todavía lo es O(1), pero revela información sobre n. Por lo tanto, un algoritmo más complejo con un tiempo de ejecución más suave puede ser preferible, incluso si puede ser asintóticamente (y posiblemente incluso en la práctica) más lento.
Christian Semrau
Esto es básicamente por qué bcrypt se considera bueno; hace las cosas más lentas
David dice que reinstale a Mónica el
@DavidGrinberg Esa es la razón por la cual se usa bcrypt, y se ajusta a la pregunta. Pero eso no está relacionado con esta respuesta, que habla sobre ataques de tiempo.
Christian Semrau
37

Alistra lo logró, pero no proporcionó ningún ejemplo, así que lo haré.

Tiene una lista de 10,000 códigos UPC para lo que vende su tienda. UPC de 10 dígitos, entero para el precio (precio en centavos) y 30 caracteres de descripción para el recibo.

Enfoque O (log N): tiene una lista ordenada. 44 bytes si es ASCII, 84 si es Unicode. Alternativamente, trate el UPC como un int64 y obtendrá 42 y 72 bytes. 10,000 registros: en el caso más alto, está viendo un poco menos de un megabyte de almacenamiento.

Enfoque O (1): no almacene el UPC, en su lugar, úselo como una entrada en la matriz. En el caso más bajo, estás viendo casi un tercio de un terabyte de almacenamiento.

El enfoque que use depende de su hardware. En la mayoría de las configuraciones modernas razonables, utilizará el enfoque log N. Puedo imaginar que el segundo enfoque es la respuesta correcta si, por alguna razón, está ejecutando en un entorno donde la RAM es críticamente corta pero tiene mucho almacenamiento masivo. Un tercio de un terabyte en un disco no es gran cosa, obtener sus datos en una sonda del disco vale algo. El enfoque binario simple toma 13 en promedio. (Tenga en cuenta, sin embargo, que al agrupar sus claves puede reducir esto a 3 lecturas garantizadas y, en la práctica, almacenará en caché la primera).

Loren Pechtel
fuente
2
Estoy un poco confundido aquí. ¿Estás hablando de crear una matriz de 10 mil millones de entradas (la mayoría de las cuales será indefinida) y tratar el UPC como un índice en esa matriz?
David Z
77
@DavidZ Sí. Si usa una matriz dispersa, es posible que no obtenga O (1) pero solo usará 1 MB de memoria. Si usa una matriz real, tiene garantizado el acceso O (1) pero usará 1/3 TB de memoria.
Navin
En un sistema moderno, utilizará 1/3 TB de espacio de direcciones, pero eso no significa que se acerque a esa memoria de respaldo asignada. La mayoría de los sistemas operativos modernos no comprometen el almacenamiento para asignaciones hasta que lo necesitan. Al hacer esto, esencialmente está ocultando una estructura de búsqueda asociativa para sus datos dentro del sistema de memoria virtual del sistema operativo / hardware.
Phil Miller
@Novelocrat True, pero si lo está haciendo a velocidades de RAM, el tiempo de búsqueda no importará, no hay razón para usar 40mb en lugar de 1mb. La versión de matriz solo tiene sentido cuando el acceso al almacenamiento es costoso: se va al disco.
Loren Pechtel
1
O cuando esta no es una operación de rendimiento crítico, y el tiempo del desarrollador es costoso: decir malloc(search_space_size)y suscribirse a lo que devuelve es tan fácil como parece.
Phil Miller
36

Considere un árbol rojo-negro. Tiene acceso, búsqueda, inserción y eliminación de O(log n). Compare con una matriz, que tiene acceso O(1)y el resto de las operaciones son O(n).

Entonces, dada una aplicación en la que insertamos, eliminamos o buscamos con más frecuencia de la que accedemos y una elección entre solo estas dos estructuras, preferiríamos el árbol rojo-negro. En este caso, podría decir que preferimos el O(log n)tiempo de acceso más engorroso del árbol rojo-negro .

¿Por qué? Porque el acceso no es nuestra principal preocupación. Estamos haciendo una compensación: el rendimiento de nuestra aplicación está más influenciado por factores distintos a este. Permitimos que este algoritmo en particular sufra rendimiento porque hacemos grandes ganancias al optimizar otros algoritmos.

Entonces, la respuesta a su pregunta es simplemente esto: cuando la tasa de crecimiento del algoritmo no es lo que queremos optimizar , cuando queremos optimizar otra cosa. Todas las otras respuestas son casos especiales de esto. A veces optimizamos el tiempo de ejecución de otras operaciones. A veces optimizamos para la memoria. A veces optimizamos para la seguridad. A veces optimizamos la mantenibilidad. A veces optimizamos para el tiempo de desarrollo. Incluso la constante primordial que es lo suficientemente baja como para importar es optimizar el tiempo de ejecución cuando se sabe que la tasa de crecimiento del algoritmo no es el mayor impacto en el tiempo de ejecución. (Si su conjunto de datos estuviera fuera de este rango, optimizaría la tasa de crecimiento del algoritmo porque eventualmente dominaría la constante). Todo tiene un costo y, en muchos casos, cambiamos el costo de una tasa de crecimiento más alta por el algoritmo para optimizar otra cosa.

jpmc26
fuente
No estoy seguro de cómo las operaciones que le permiten usar la matriz con O (1) búsqueda y actualizaciones O (n) corresponden al árbol rojo-negro, la gente solía pensar (al menos yo). La mayoría de las veces, primero pensaría en la búsqueda basada en claves para el árbol rojo-negro. Pero para que coincida con la matriz, debe ser una estructura un poco diferente que mantenga la cantidad de subnodos en los nodos superiores para proporcionar una búsqueda basada en índices y volver a indexar en la inserción. Aunque estoy de acuerdo en que el rojo y el negro pueden usarse para mantener el equilibrio, puede usar el árbol equilibrado si desea ser impreciso sobre los detalles de las operaciones correspondientes.
ony
@ony Se puede usar un árbol rojo-negro para definir una estructura de tipo de mapa / diccionario, pero no es necesario. Los nodos pueden ser solo elementos, esencialmente implementando una lista ordenada.
jpmc26
La lista ordenada y la matriz que define el orden de los elementos tienen una cantidad diferente de información. Uno se basa en el orden entre los elementos y el conjunto y el otro define una secuencia arbitraria que no necesariamente define el orden entre los elementos. Otra cosa es ¿qué es "acceso" y "búsqueda" que declaras ser O(log n)de "árbol rojo-negro"? Inserte de 5en la posición 2 de la matriz [1, 2, 1, 4]resultará en [1, 2, 5, 1 4](elemento 4conseguirá índice actualizada de 3 a 4). ¿Cómo va a obtener este comportamiento en O(log n)el "árbol rojo-negro" al que hace referencia como "lista ordenada"?
ony
@ony "la lista ordenada y la matriz que define el orden de los elementos tienen una cantidad diferente de información". Sí, y eso es parte de por qué tienen diferentes características de rendimiento. Te estás perdiendo el punto. Uno no es una caída en reemplazo del otro en todas las situaciones. Se optimizan las cosas diferentes y hacen diferentes soluciones de compromiso , y el punto es que los desarrolladores están tomando decisiones acerca de esas compensaciones constantemente.
jpmc26
@ony Acceso, búsqueda, inserción y eliminación tienen significados específicos en el contexto del rendimiento del algoritmo. Access es buscar un elemento por posición. La búsqueda consiste en localizar un elemento por valor (que solo tiene una aplicación práctica como verificación de contención para una estructura que no sea de mapa). Sin embargo, insertar y eliminar debe ser sencillo. Ejemplo de uso se puede ver aquí .
jpmc26
23

Si.

En un caso real, realizamos algunas pruebas para realizar búsquedas de tablas con teclas de cadena cortas y largas.

Utilizamos un std::map, un std::unordered_maphash que muestrea como máximo 10 veces a lo largo de la cadena (nuestras teclas tienden a ser de tipo guid, por lo que esto es decente), y un hash que muestrea cada carácter (en teoría, colisiones reducidas), un vector sin clasificar donde hacemos una ==comparación, y (si no recuerdo mal) un vector sin clasificar donde también almacenamos un hash, primero compara el hash, luego compara los caracteres.

Estos algoritmos van desde O(1)(unordered_map) a O(n)(búsqueda lineal).

Para N de tamaño modesto, con frecuencia la O (n) supera a la O (1). Sospechamos que esto se debe a que los contenedores basados ​​en nodos requieren que nuestra computadora salte más en la memoria, mientras que los contenedores basados ​​en lineal no.

O(lg n)existe entre los dos. No recuerdo cómo fue.

La diferencia de rendimiento no fue tan grande, y en conjuntos de datos más grandes, el basado en hash funcionó mucho mejor. Así que nos quedamos con el mapa desordenado basado en hash.

En la práctica, para un tamaño razonable n, O(lg n)es O(1). Si su computadora solo tiene espacio para 4 mil millones de entradas en su tabla, entonces O(lg n)está limitada por 32. (lg (2 ^ 32) = 32) (en informática, lg es la abreviatura de log basado en 2).

En la práctica, los algoritmos lg (n) son más lentos que los algoritmos O (1) no por el factor de crecimiento logarítmico, sino porque la porción lg (n) generalmente significa que hay un cierto nivel de complejidad en el algoritmo, y esa complejidad agrega un factor constante mayor que cualquiera de los "crecimiento" del término lg (n).

Sin embargo, los algoritmos complejos de O (1) (como el mapeo hash) pueden tener fácilmente un factor constante similar o mayor.

Yakk - Adam Nevraumont
fuente
21

La posibilidad de ejecutar un algoritmo en paralelo.

No sé si hay un ejemplo para las clases O(log n)y O(1), pero para algunos problemas, eliges un algoritmo con una clase de mayor complejidad cuando el algoritmo es más fácil de ejecutar en paralelo.

Algunos algoritmos no pueden ser paralelizados pero tienen una clase de complejidad tan baja. Considere otro algoritmo que logre el mismo resultado y se pueda paralelizar fácilmente, pero que tenga una clase de mayor complejidad. Cuando se ejecuta en una máquina, el segundo algoritmo es más lento, pero cuando se ejecuta en varias máquinas, el tiempo de ejecución real disminuye y el primer algoritmo no puede acelerarse.

Simulante
fuente
Pero todo lo que hace la paralelización es reducir el factor constante del que otros han hablado, ¿verdad?
gengkev
1
Sí, pero un algoritmo paralelo puede dividir el factor constante entre 2 cada vez que duplica el número de máquinas en ejecución. Otro algoritmo de subproceso único puede reducir el factor constante solo una vez de manera constante. Entonces, con un algoritmo paralelo, puede reaccionar dinámicamente al tamaño de ny ser más rápido en el tiempo de ejecución del reloj de pared.
Simulante
15

Digamos que está implementando una lista negra en un sistema integrado, donde los números entre 0 y 1,000,000 pueden estar en la lista negra. Eso te deja dos opciones posibles:

  1. Use un conjunto de bits de 1,000,000 de bits
  2. Use una matriz ordenada de enteros en la lista negra y use una búsqueda binaria para acceder a ellos

El acceso al bitset habrá garantizado un acceso constante. En términos de complejidad temporal, es óptimo. Tanto desde un punto de vista teórico como práctico (es O (1) con una sobrecarga constante extremadamente baja).

Aún así, es posible que desee preferir la segunda solución. Especialmente si espera que el número de enteros en la lista negra sea muy pequeño, ya que será más eficiente en la memoria.

E incluso si no se desarrolla para un sistema incrustado donde la memoria es escasa, solo puedo aumentar el límite arbitrario de 1,000,000 a 1,000,000,000,000 y hacer el mismo argumento. Entonces el bitset requeriría alrededor de 125G de memoria. Tener una complejidad garantizada en el peor de los casos de O (1) podría no convencer a su jefe de proporcionarle un servidor tan poderoso.

Aquí, preferiría una búsqueda binaria (O (log n)) o un árbol binario (O (log n)) sobre el conjunto de bits O (1). Y probablemente, una tabla hash con su peor complejidad de O (n) los superará a todos en la práctica.

Philipp Claßen
fuente
12

La gente ya ha respondido su pregunta exacta, por lo que abordaré una pregunta ligeramente diferente en la que la gente podría estar pensando cuando venga aquí.

Muchos de los algoritmos de "O (1) tiempo" y las estructuras de datos en realidad solo toman el tiempo esperado de O (1), lo que significa que su tiempo de ejecución promedio es O (1), posiblemente solo bajo ciertos supuestos.

Ejemplos comunes: tablas hash, expansión de "listas de matrices" (también conocidas como matrices / vectores de tamaño dinámico).

En tales escenarios, es posible que prefiera utilizar estructuras de datos o algoritmos cuyo tiempo se garantice absolutamente limitado logarítmicamente, a pesar de que su rendimiento promedio sea peor.
Por lo tanto, un ejemplo podría ser un árbol de búsqueda binario equilibrado, cuyo tiempo de ejecución es peor en promedio pero mejor en el peor de los casos.

usuario541686
fuente
11

Una pregunta más general es si hay situaciones en las que uno preferiría un O(f(n))algoritmo a un O(g(n))algoritmo a pesar de g(n) << f(n)que ntiende al infinito. Como otros ya han mencionado, la respuesta es claramente "sí" en el caso donde f(n) = log(n)y g(n) = 1. A veces es sí, incluso en el caso de que f(n)sea ​​polinomial pero g(n)exponencial. Un ejemplo famoso e importante es el del Algoritmo Simplex para resolver problemas de programación lineal. En la década de 1970 se demostró que era O(2^n). Por lo tanto, su peor comportamiento es inviable. Pero su comportamiento promedio es extremadamente bueno, incluso para problemas prácticos con decenas de miles de variables y restricciones. En la década de 1980, los algoritmos de tiempo polinomiales (comoSe descubrió el algoritmo de punto interior de Karmarkar ) para la programación lineal, pero 30 años después, el algoritmo simplex todavía parece ser el algoritmo de elección (a excepción de ciertos problemas muy grandes). Esto es por la razón obvia de que el comportamiento de caso promedio es a menudo más importante que el comportamiento de caso peor, pero también por una razón más sutil de que el algoritmo simplex es en cierto sentido más informativo (por ejemplo, la información de sensibilidad es más fácil de extraer).

John Coleman
fuente
10

Para poner mis 2 centavos en:

A veces, se selecciona un algoritmo de peor complejidad en lugar de uno mejor, cuando el algoritmo se ejecuta en un determinado entorno de hardware. Supongamos que nuestro algoritmo O (1) accede de manera no secuencial a cada elemento de una matriz muy grande de tamaño fijo para resolver nuestro problema. Luego coloque esa matriz en un disco duro mecánico o una cinta magnética.

En ese caso, el algoritmo O (logn) (supongamos que accede al disco secuencialmente), se vuelve más favorable.

uylmz
fuente
Podría agregar aquí que en la unidad o cinta de acceso secuencial, el algoritmo O (1) se convierte en O (n), por lo que la solución secuencial se vuelve más favorable. Muchas operaciones O (1) dependen de que la búsqueda agregada e indexada sea un algoritmo de tiempo constante, que no está en un espacio de acceso secuencial.
TheHansinator
9

Hay un buen caso de uso para usar un algoritmo O (log (n)) en lugar de un algoritmo O (1) que las otras numerosas respuestas han ignorado: la inmutabilidad. Los mapas hash tienen O (1) put y gets, suponiendo una buena distribución de los valores hash, pero requieren un estado mutable. Los mapas de árboles inmutables tienen O (log (n)) put y gets, que es asintóticamente más lento. Sin embargo, la inmutabilidad puede ser lo suficientemente valiosa como para compensar el peor rendimiento y, en el caso de que se deban retener varias versiones del mapa, la inmutabilidad le permite evitar tener que copiar el mapa, que es O (n), y por lo tanto puede mejorar actuación.

Reinstalar a Mónica
fuente
9

Simplemente: porque el coeficiente, los costos asociados con la configuración, el almacenamiento y el tiempo de ejecución de ese paso, puede ser mucho, mucho mayor con un problema de Big-O más pequeño que con uno más grande. Big-O es solo una medida de la escalabilidad de los algoritmos .

Considere el siguiente ejemplo del Hacker's Dictionary, que propone un algoritmo de clasificación basado en la Interpretación de la mecánica cuántica de mundos múltiples :

  1. Permuta la matriz al azar usando un proceso cuántico,
  2. Si la matriz no está ordenada, destruya el universo.
  3. Todos los universos restantes ahora están ordenados [incluido el que está en].

(Fuente: http://catb.org/~esr/jargon/html/B/bogo-sort.html )

Observe que el big-O de este algoritmo es O(n), que supera a cualquier algoritmo de clasificación conocido hasta la fecha en elementos genéricos. El coeficiente del paso lineal también es muy bajo (ya que es solo una comparación, no un intercambio, que se hace linealmente). De hecho, se podría usar un algoritmo similar para resolver cualquier problema en NP y co-NP en tiempo polinómico, ya que cada posible solución (o posible prueba de que no hay solución) se puede generar utilizando el proceso cuántico, y luego se verifica en tiempo polinomial.

Sin embargo, en la mayoría de los casos, probablemente no queremos correr el riesgo de que Múltiples mundos no sean correctos, sin mencionar que el acto de implementar el paso 2 todavía "se deja como un ejercicio para el lector".

TheHansinator
fuente
7

En cualquier punto cuando n está acotado y el multiplicador constante del algoritmo O (1) es mayor que el límite en log (n). Por ejemplo, almacenar valores en un hashset es O (1), pero puede requerir un cálculo costoso de una función hash. Si los elementos de datos se pueden comparar trivialmente (con respecto a algún orden) y el límite en n es tal que log n es significativamente menor que el cálculo de hash en cualquier elemento, entonces el almacenamiento en un árbol binario equilibrado puede ser más rápido que el almacenamiento en un hashset

Dmitry Rubanovich
fuente
6

En una situación en tiempo real en la que necesita un límite superior firme, seleccionaría, por ejemplo, un montón en lugar de un Quicksort, porque el comportamiento promedio del montón también es el peor de los casos.

Marqués de Lorne
fuente
6

Además de las respuestas ya buenas, un ejemplo práctico sería los índices Hash frente a los índices del árbol B en la base de datos de Postgres.

Los índices hash forman un índice de tabla hash para acceder a los datos en el disco, mientras que btree, como su nombre indica, utiliza una estructura de datos Btree.

En Big-O, estos son O (1) vs O (logN).

Los índices de hash actualmente se desaconsejan en postgres ya que en una situación de la vida real, particularmente en sistemas de bases de datos, lograr el hash sin colisión es muy difícil (puede conducir a una complejidad O (N) en el peor de los casos) y debido a esto, es aún más difícil de hacer ellos se bloquean a salvo (llamado registro de escritura anticipada - WAL en postgres).

Esta compensación se realiza en esta situación ya que O (logN) es lo suficientemente bueno para los índices y la implementación de O (1) es bastante difícil y la diferencia horaria realmente no importaría.

Madusudanan
fuente
4

Cuando nes pequeño, y O(1)es constantemente lento.

HoboBen
fuente
3
  1. Cuando la unidad de trabajo "1" en O (1) es muy alta en relación con la unidad de trabajo en O (log n) y el tamaño del conjunto esperado es pequeño. Por ejemplo, probablemente sea más lento calcular los códigos hash del Diccionario que iterar una matriz si solo hay dos o tres elementos.

o

  1. Cuando la memoria u otros requisitos de recursos que no son de tiempo en el algoritmo O (1) son excepcionalmente grandes en relación con el algoritmo O (log n).
Joel Coehoorn
fuente
3
  1. al rediseñar un programa, se encuentra que un procedimiento está optimizado con O (1) en lugar de O (lgN), pero si no es el cuello de botella de este programa, y ​​es difícil entender el O (1) alg. Entonces no tendría que usar el algoritmo O (1)
  2. cuando O (1) necesita mucha memoria que no puede suministrar, mientras que se puede aceptar el tiempo de O (lgN).
Yanghaogn
fuente
1

Este suele ser el caso de las aplicaciones de seguridad que queremos diseñar problemas cuyos algoritmos son lentos a propósito para evitar que alguien obtenga una respuesta a un problema demasiado rápido.

Aquí hay un par de ejemplos fuera de mi cabeza.

  • El hash de contraseñas a veces se hace arbitrariamente lento para que sea más difícil adivinar las contraseñas por fuerza bruta. Esta publicación de seguridad de la información tiene una viñeta al respecto (y mucho más).
  • Bit Coin utiliza un problema controlablemente lento que una red de computadoras debe resolver para "extraer" monedas. Esto permite que la moneda se extraiga a una tasa controlada por el sistema colectivo.
  • Los cifrados asimétricos (como RSA ) están diseñados para descifrar sin que las claves sean lentas intencionalmente para evitar que alguien sin la clave privada descifre el cifrado. Los algoritmos están diseñados para descifrar en un O(2^n)momento con suerte, donde nestá la longitud de la clave (esto es fuerza bruta).

En otras partes de CS, Quick Sort está O(n^2)en el peor de los casos, pero en el caso general es O(n*log(n)). Por esta razón, el análisis "Big O" a veces no es lo único que le importa al analizar la eficiencia del algoritmo.

Frank Bryce
fuente