¿Hay algún caso en el que prefiera un algoritmo de complejidad de tiempo mayor de O gran que el inferior?

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

¿Tienes algún ejemplo?

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

    • la mayor parte del tiempo, la complejidad de la gran O baja es más difícil de lograr y requiere una implementación experta, muchos conocimientos 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 O gran que 1/10^5 * log(n) ( O(1) frente a 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 no (para mi conocimiento) las bibliotecas computacionales lo usan.
    • big-O tiene sentido cuando se calcula sobre algo grande. Si necesita ordenar una matriz de tres números, importa muy poco si usa el algoritmo O(n*log(n)) o 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 un gran número de n = 10^20 la diferencia es insignificante.
    • la complejidad del tiempo no es todo. Imagine un algoritmo que se ejecuta en O(n^2) y requiere memoria O(n^2) . Puede ser preferible sobre el tiempo O(n^3) y el espacio O(1) cuando el n no es realmente grande. El problema es que puedes esperar mucho tiempo, pero tienes muchas dudas de 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 de productos básicos con una complejidad mayor que el uso de una máquina con una complejidad ligeramente superior.
    • en algunos lugares (seguridad) una complejidad puede ser un requisito. Nadie quiere tener un algoritmo hash que pueda hacer hash increíblemente rápido (porque entonces otras personas pueden forzarte brutalmente más rápido)
    • aunque esto no está relacionado con el cambio de complejidad, pero algunas de las funciones de seguridad deben estar escritas de una manera que prevenga el ataque oportuno . Principalmente permanecen en la misma clase de complejidad, pero se modifican de una manera que siempre es peor si se hace 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ás hasta el final para contar las malas noticias.
    • alguien patentó el algoritmo de complejidad más baja y es más económico para una empresa usar una complejidad mayor que para 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 el quicksort o mergesort, 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 otros algoritmos solo pueden operar eficientemente en una lista completa de valores.

    Siempre existe la constante oculta, que puede ser menor 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 hay preocupación por el tiempo del desarrollador: O (log n ) puede ser 1000 veces más fácil de implementar y verificar.

    Me sorprende que nadie haya mencionado las aplicaciones de memoria aún.

    Puede haber un algoritmo que tenga menos operaciones de coma flotante debido a su complejidad (es decir, O (1) < O (log n )) o porque la constante delante de la complejidad es más pequeña (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 inferior está más ligado a la memoria.

    Lo que quiero decir con “límite de memoria” es que a menudo accedes a datos que están constantemente fuera del caché. Para obtener estos datos, debe extraer la memoria de su espacio de memoria en realidad 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 (aunque estas operaciones se realizan en datos que ya están en la memoria caché [y, por lo tanto, no se requiere búsqueda]), aún superará su algoritmo con menos operaciones (que se deben realizar fuera de -caché de datos [y, por lo tanto, requieren una búsqueda]) en términos de pared real.

    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 una mejor resistencia a los ataques de tiempo .

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

    Tienes una lista de 10,000 códigos UPC para lo que vende tu tienda. 10 dígitos UPC, número 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, lo utiliza como una entrada en el conjunto. En el caso más bajo, estás viendo casi un tercio de un terabyte de almacenamiento.

    El enfoque que uses depende de tu hardware. En la mayoría de las configuraciones modernas razonables, vas a utilizar el enfoque log N. Me imagino que el segundo enfoque es la respuesta correcta si, por alguna razón, se está ejecutando en un entorno en el que la memoria RAM es muy corta, pero tiene un montón de 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. (Sin embargo, tenga en cuenta que al agrupar sus claves puede obtener 3 lecturas garantizadas y, en la práctica, almacenaría en caché la primera).

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

    Entonces, dada una aplicación en la que insertemos, eliminemos o busquemos 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, puede 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 realizando una transacción: el rendimiento de nuestra aplicación está más fuertemente influenciado por factores distintos a este. Permitimos que este algoritmo 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 algo más . Todas las otras respuestas son casos especiales de esto. Algunas veces optimizamos el tiempo de ejecución de otras operaciones. A veces optimizamos para la memoria. A veces optimizamos para la seguridad. Algunas veces optimizamos la mantenibilidad. A veces optimizamos para el tiempo de desarrollo. Incluso la constante primordial es lo suficientemente baja como para importar, se está optimizando para 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 estaba 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 para el algoritmo para optimizar algo más.

    Sí.

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

    Usamos std::map , std::unordered_map con un hash que muestra como mucho 10 veces la longitud de la cadena (nuestras teclas tienden a ser guid, por lo que esto es decente), y un hash que prueba cada carácter (en teoría colisiones reducidas), un vector sin clasificar donde hacemos una comparación ==

    Estos algoritmos van desde O(1) (mapa no ordenado) 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 requirieron que nuestra computadora saltara más en la memoria, mientras que los contenedores lineales no lo hicieron.

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

    La diferencia de rendimiento no fue tan grande, y en conjuntos de datos más grandes, la basada en hash tuvo un rendimiento 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) tiene un límite superior de 32 . (lg (2 ^ 32) = 32) (en ciencias de la computación, lg es short hand para log based 2).

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

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

    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 complejidad más alta cuando el algoritmo es más fácil de ejecutar en paralelo.

    Algunos algoritmos no se pueden paralelizar, pero tienen una clase de complejidad muy baja. Considere otro algoritmo que logra el mismo resultado y se puede paralelizar fácilmente, pero tiene una clase de complejidad más alta. 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 se hace cada vez más bajo, mientras que el primer algoritmo no puede acelerar.

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

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

    El acceso al bitsets tendrá acceso constante garantizado. En términos de complejidad de tiempo, es óptimo. Tanto desde un punto de vista teórico como desde un punto de vista 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 la cantidad de enteros en la lista negra sea muy pequeña, ya que será más eficiente en cuanto a la memoria.

    E incluso si no se desarrolla para un sistema integrado donde la memoria es escasa, solo puedo boost el límite arbitrario de 1,000,000 a 1,000,000,000,000 y hacer el mismo argumento. Entonces el conjunto de bits requeriría alrededor de 125G de memoria. Tener una complexidad de peor caso garantizado de O (1) podría no convencer a su jefe de que le proporcione un servidor tan potente.

    Aquí, preferiría una búsqueda binaria (O (log n)) o á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 vencerá a todos en la práctica.

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

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

    Muchos de los algoritmos y estructuras de datos “O (1) time” en realidad solo toman el tiempo O (1) esperado , lo que significa que su tiempo promedio de ejecución es O (1), posiblemente solo bajo ciertas suposiciones.

    Ejemplos comunes: hashtables, expansión de “listas de matrices” (también conocidas como matrices / vectores de tamaño dynamic).

    En dichos escenarios, es posible que prefiera utilizar estructuras de datos o algoritmos cuyo tiempo garantizado está absolutamente limitado logarítmicamente, aunque en promedio tengan un peor rendimiento.
    Por lo tanto, un ejemplo podría ser un árbol de búsqueda binaria equilibrada, cuyo tiempo de ejecución es peor en promedio pero mejor en el peor de los casos.

    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 a infinito. Como otros ya han mencionado, la respuesta es claramente "sí" en el caso donde f(n) = log(n) g(n) = 1 . Algunas veces 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 progtwigción lineal. En la década de 1970 se demostró que era O(2^n) . Por lo tanto, su peor comportamiento de caso es inviable. Pero su comportamiento promedio de casos 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 progtwigción lineal, pero 30 años más tarde el algoritmo simple parece ser el algoritmo de elección (excepto para algunos problemas muy grandes). Esto es por la razón obvia de que el comportamiento promedio es a menudo más importante que el peor caso de comportamiento, pero también por una razón más sutil 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).

    Para poner mis 2 centavos en:

    En ocasiones, se selecciona un algoritmo de complejidad peor en lugar de uno mejor, cuando el algoritmo se ejecuta en un entorno de hardware determinado. Supongamos que nuestro algoritmo O (1) accede de forma no secuencial a cada elemento de una gran matriz 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.

    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) puts 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)) puts y gets, que es asintóticamente más lento. Sin embargo, la inmutabilidad puede ser lo suficientemente valiosa para compensar un peor rendimiento y, en el caso de que se necesiten conservar 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.

    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 más grande con un problema menor de O grande 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, proponiendo un algoritmo de clasificación que se basa en la Interpretación de Múltiples Mundos de la Mecánica Cuántica :

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

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

    Tenga en cuenta que la gran O de este algoritmo es O(n) , que supera cualquier algoritmo de clasificación conocido hasta la fecha en los artículos generics. El coeficiente del paso lineal también es muy bajo (ya que es solo una comparación, no un intercambio, lo 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 polinomial, ya que cada posible solución (o posible prueba de que no hay solución) puede generarse utilizando el proceso cuántico, luego verificada en tiempo polinomial.

    Sin embargo, en la mayoría de los casos, probablemente no queremos correr el riesgo de que Multiple Worlds no sea correcto, sin mencionar que el acto de implementar el paso 2 todavía “se deja como un ejercicio para el lector”.

    En cualquier punto cuando n está limitado y el multiplicador constante del algoritmo O (1) es más alto 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 de n es tal que log n es significativamente menor que el cálculo de hash en cualquier elemento, almacenar en un árbol binario equilibrado puede ser más rápido que almacenar en un hashset.

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

    Agregando a las respuestas ya buenas. Un ejemplo práctico sería Hash indexes vs B-tree indexes en la base de datos postgres.

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

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

    Los índices hash se desaconsejan actualmente en Postgres ya que en una situación de la vida real particularmente en sistemas de bases de datos, lograr hashing sin colisión es muy difícil (puede llevar a una O (N) peor complejidad de caso) y debido a esto, es aún más difícil de hacer se bloquean (se llaman registros de escritura anticipada – WAL en postgres).

    Este intercambio 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 de tiempo realmente no importaría.

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

    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 de conjunto esperado es pequeño-ish. Por ejemplo, es probable que sea más lento calcular códigos hash de 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).
    1. cuando se rediseña un progtwig, se encuentra que un procedimiento se optimiza con O (1) en lugar de O (lgN), pero si no es el cuello de botella de este progtwig, y ​​es difícil entender el O (1) alg. Entonces no tendrías que usar el algoritmo O (1)
    2. cuando O (1) necesita mucha memoria que no puede suministrar, mientras que el tiempo de O (lgN) puede ser aceptado.

    Este es a menudo el caso de las aplicaciones de seguridad que queremos diseñar problemas cuyos algoritmos son lentos a fin de 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 dificultar la adivinación de contraseñas por fuerza bruta. Esta publicación de Seguridad de la información tiene un punto sobre ella (y mucho más).
    • Bit Coin utiliza un problema controlablemente lento para que una red de computadoras lo resuelva con el fin de “minar” las monedas. Esto permite que la moneda sea extraída 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 ralenticen intencionalmente a fin de evitar que otra persona sin la clave privada descifre el cifrado. Los algoritmos están diseñados para ser craqueados con la esperanza de O(2^n) tiempo donde n es la longitud de bit de la clave (esto es fuerza bruta).

    En otras partes de CS, Quick Sort es 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.