algorithm - sheet - big o rapper

¿Hay algún caso en el que prefiera un algoritmo de complejidad de tiempo Big-O más alto que el más bajo? (22)

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

¿Tienes algún ejemplo?

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 de entender el O (1) alg. Entonces no tendría que usar el algoritmo O (1)
cuando O (1) necesita mucha memoria que no puede suministrar, mientras que puede aceptarse el tiempo de O (lgN).

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.

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

Este suele ser el caso de las aplicaciones de seguridad en las 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ña 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 se reduzcan intencionalmente para evitar que alguien sin la clave privada descifre el cifrado. Los algoritmos están diseñados para ser descifrados en un O(2^n) momento con suerte donde n está 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.

Agregando a 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 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 el tiempo Big-O estos son O (1) vs O (logN).

Los índices de hash actualmente no se recomiendan en postgres ya que en una situación de la vida real, particularmente en los sistemas de bases de datos, lograr el hash sin colisión es muy difícil (puede conducir a una O (N) peor caso de complejidad) 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.

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

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 a 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 tiempo de acceso O(log n) 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 esta: 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 está optimizando 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 algoritmo para optimizar otra cosa.

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

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:

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

El acceso al bitset tendrá acceso constante garantizado. 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 cuanto a memoria.

E incluso si no se desarrolla para un sistema embebido 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 aproximadamente 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.

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 .

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.

Hay un buen caso de uso para usar un algoritmo O (log (n)) en lugar de un algoritmo O (1) que las numerosas otras 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 árbol 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 mantener 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.

La gente ya ha respondido su pregunta exacta, por lo que abordaré una pregunta ligeramente diferente en la que la gente puede estar realmente 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 pueden funcionar peor en promedio.
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.

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 pueda paralelizarse 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.

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 ² <6 n ² ) . 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 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 búsqueda 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]), seguirá superando 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.

Mi respuesta aquí La selección ponderada aleatoria rápida en todas las filas de una matriz estocástica es un ejemplo en el que un algoritmo con complejidad O (m) es más rápido que uno con complejidad O (log (m)), cuando m no es demasiado grande.

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

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 menor 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 en 10^5 es mejor 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 n el 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 necesita ordenar una matriz de tres números, realmente importa poco si usa el algoritmo O(n*log(n)) u O(n^2) .
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 proporciona una complejidad de tiempo O(log log N) para encontrar un elemento, pero también hay un árbol binario que encuentra lo mismo en O(log n) . Incluso para grandes cantidades de n = 10^20 la diferencia es insignificante.
La complejidad del tiempo no lo es todo. Imagine un algoritmo que se ejecuta en O(n^2) y requiere memoria O(n^2) . Podría ser preferible sobre O(n^3) tiempo y 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), una 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 utilizar 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 temporal 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 más otros algoritmos solo pueden operar eficientemente en una lista completa de valores.

Sí.

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_map con un hash que muestrea como máximo 10 veces a lo largo de la cadena (nuestras claves 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 bastante frecuencia el O (n) supera al 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 lineales 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á limitado 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 de hash) pueden tener fácilmente un factor constante similar o mayor.

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.

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 :

Permuta la matriz al azar usando un proceso cuántico,

Si la matriz no está ordenada, destruya el universo.

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 tanto en NP como en 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, 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 "queda como un ejercicio para el lector".

Una pregunta más general es si hay situaciones en las que uno preferiría un algoritmo O(f(n)) a un algoritmo O(g(n)) aunque g(n) << f(n) como n tiende al infinito. Como otros ya han mencionado, la respuesta es claramente "sí" en el caso donde f(n) = log(n) g(n) = 1 . A veces es sí, incluso en el caso de que f(n) sea polinomial pero g(n) sea 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, se descubrieron algoritmos de tiempo polinomiales (como 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 (excepto para 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).

En cualquier momento 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 pueden compararse 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