¿Existen algoritmos del mundo real que superen en gran medida a la clase siguiente? [cerrado]

Búsquedas en tablas de datos fijas muy pequeñas. Una tabla hash optimizada puede ser O (1) y, sin embargo, más lenta que una búsqueda binaria o incluso una búsqueda lineal debido al costo del cálculo de hash.

Un ejemplo simple es la diferencia entre varios algoritmos de clasificación. Mergesort, Heapsort y algunos otros son O (n log n) . Quicksort es O (n ^ 2) en el peor de los casos. Pero, a menudo, Quicksort es más rápido y, de hecho, funciona en promedio como O (n log n) . Más información .

Otro ejemplo es la generación de un solo número de Fibonacci. El algoritmo iterativo es O (n) , mientras que el algoritmo basado en matrices es O (log n) . Aún así, para el primer par de miles de números de Fibonacci, el algoritmo iterativo es probablemente más rápido. ¡Esto también depende de la implementación del curso!

Los algoritmos con un mejor rendimiento asintótico pueden contener operaciones costosas que no son necesarias con un algoritmo con peor rendimiento pero operaciones más simples. Al final, la notación O solo nos dice algo sobre el rendimiento cuando el argumento sobre el que opera aumenta dramáticamente (se acerca al infinito).

Multiplicación de matrices. El ingenuo algoritmo O (n ^ 3) se usa a menudo en la práctica más rápido que el O (n ^ 2.8) de Strassen para matrices pequeñas; y Strassen's se usa en lugar del algoritmo O (n ^ 2.3) Coppersmith-Winograd para matrices más grandes.

Nota: Por favor, lea los comentarios de @ back2dos a continuación y otros gurús, ya que de hecho son más útiles que lo que he escrito: gracias a todos los colaboradores.

Creo que de la tabla a continuación (tomada de: Big O notation , busque "La naturaleza pesimista de los algoritmos:"), puede ver que O (log n) no es siempre mejor que decir, O (n). Entonces, supongo que tu argumento es válido.

Para valores prácticos de n , sí. Esto surge mucho en la teoría CS. A menudo hay un algoritmo complicado que técnicamente tiene mejor rendimiento de gran Oh, pero los factores constantes son tan grandes que lo hacen poco práctico.

Una vez, mi profesor de geometría computacional describió un algoritmo para triangular un polígono en tiempo lineal, pero terminó con "muy complicado. No creo que nadie lo haya implementado realmente" (!!).

Además, los montones de Fibonacci tienen mejores características que los montones normales, pero no son muy populares porque no funcionan tan bien como en la práctica como montones regulares. Esto puede pasar a otros algoritmos que utilizan montones; por ejemplo, las rutas más cortas de Dijkstra son matemáticamente más rápidas con un montón de fibonacci, pero generalmente no en la práctica.

Compare la inserción en una lista vinculada y la inserción en una matriz de tamaño variable.

La cantidad de datos debe ser bastante grande para que la inserción de la lista vinculada O (1) valga la pena.

Una lista vinculada tiene una sobrecarga adicional para los siguientes punteros y desreferencias. Una matriz de tamaño variable tiene que copiar los datos alrededor. Esa copia es O (n), pero en la práctica es muy rápida.

La notación Big-Oh se usa para describir la tasa de crecimiento de una función, por lo que es posible que un algoritmo O (1) sea más rápido, pero solo hasta cierto punto (el factor constante).

Notaciones comunes:

O (1): el número de iteraciones (a veces puede referirse a esto como tiempo de uso de la función) no depende del tamaño de la entrada y, de hecho, es constante.

O (n): el número de iteraciones aumenta en una lineal proporcional al tamaño de la entrada. Significado: si el algoritmo se itera a través de cualquier entrada N, 2 * N veces, aún se considera O (n).

O (n ^ 2) (cuadrático): el número de iteraciones es el tamaño de entrada al cuadrado.

Las bibliotecas Regex generalmente se implementan para realizar un seguimiento que tiene el peor tiempo exponencial del caso en lugar de la generación de DFA que tiene una complejidad de O(nm) .

El backtracking ingenuo puede tener un mejor desempeño cuando la entrada permanece en la ruta rápida o falla sin la necesidad de retroceder excesivamente.

(Aunque esta decisión no solo se basa en el rendimiento, también permite referencias posteriores).

Clasificación:

La clasificación de inserción es O (n ^ 2) pero supera a los otros O (n * log (n)) algoritmos de clasificación para una pequeña cantidad de elementos.

Esta es la razón por la que la mayoría de las implementaciones de ordenación usan una combinación de dos algoritmos. P.ej. use la ordenación de combinación para dividir las matrices grandes hasta que alcancen un tamaño determinado, luego use la ordenación por inserción para ordenar las unidades más pequeñas y fusionarlas nuevamente con la ordenación de combinación.

Vea Timsort la implementación predeterminada actual de Python y Java 7 que utilizan esta técnica.

El algoritmo de unification utilizado en la práctica es exponencial en el peor de los casos, para algunas entradas patológicas.

Hay un algoritmo de unificación polinómica , pero es demasiado lento. práctica.

Un algoritmo O(1) :

def constant_time_algorithm
  one_million = 1000 * 1000
  sleep(one_million) # seconds
end

Un algoritmo O(n) :

def linear_time_algorithm(n)
  sleep(n) # seconds
end

Claramente, para cualquier valor de n donde n < one_million , el algoritmo O(n) dado en el ejemplo será más rápido que el algoritmo O(1) .

Aunque este ejemplo es un poco complicado, es equivalente en espíritu al siguiente ejemplo:

def constant_time_algorithm
  do_a_truckload_of_work_that_takes_forever_and_a_day
end

def linear_time_algorithm(n)
  i = 0
  while i < n
    i += 1
    do_a_minute_amount_of_work_that_takes_nanoseconds
  end
end

Usted debe conocer las constantes y los coeficientes en su expresión O , y debe conocer el rango esperado de n , para determinar a priori qué algoritmo terminará siendo más rápido.

De lo contrario, debe evaluar los dos algoritmos con valores de n en el rango esperado para determinar a posteriori qué algoritmo terminó siendo más rápido.

Bubblesort en la memoria puede superar a Quicksort cuando el programa se está cambiando a disco o necesita leer todos los elementos del disco cuando se compara.

Este debería ser un ejemplo con el que pueda relacionarse.

A menudo, los algoritmos más avanzados suponen una cierta cantidad de configuración (costosa). Si solo necesita ejecutarlo una vez, puede que esté mejor con el método de fuerza bruta.

Por ejemplo: la búsqueda binaria y la búsqueda de tabla hash son mucho más rápidas por búsqueda que una búsqueda lineal, pero requieren que ordene la lista o cree la tabla hash, respectivamente.

El orden le costará N log (N) y la tabla hash costará al menos N. Ahora, si va a hacer cientos o miles de búsquedas, eso sigue siendo un ahorro amortizado. Pero si solo necesita hacer una o dos búsquedas, podría tener sentido simplemente hacer una búsqueda lineal y ahorrar el costo de inicio.

El descifrado es a menudo 0 (1). Por ejemplo, el espacio clave para DES es 2 ^ 56, por lo que el descifrado de cualquier mensaje es una operación de tiempo constante. Es solo que tienes un factor de 2 ^ 56 ahí, así que es una constante realmente grande.

Diferentes implementaciones de conjuntos vienen a mi mente. Uno de los más ingenuos es implementarlo sobre un vector, lo que significa remove así como contains y por lo tanto también add toma O (N). Una alternativa es implementarlo sobre un hash de propósito general, que asigna hashes de entrada a valores de entrada. Dicha implementación de conjunto se realiza con O (1) para add , contains y remove .

Si asumimos que N es aproximadamente 10, la primera implementación probablemente sea más rápida. Todo lo que tiene que hacer para encontrar un elemento es comparar 10 valores con uno.
La otra implementación tendrá que iniciar todo tipo de transformaciones inteligentes, que pueden ser mucho más caras, que hacer 10 comparaciones. Con toda la sobrecarga, puede que incluso tengas errores de caché y entonces realmente no importa qué tan rápida sea tu solución en teoría.

Esto no significa que la peor implementación que puedas imaginar superará a una decente, si N es lo suficientemente pequeña. Simplemente significa para una N suficientemente pequeña, que una implementación ingenua, con una huella y gastos generales reducidos en realidad puede requerir menos instrucciones y ocasionar menos fallas de caché que una implementación que pone en primer lugar la capacidad de ampliación, y por lo tanto será más rápida.

Realmente no puedes saber qué tan rápido es algo en un escenario del mundo real, hasta que lo pones en uno y simplemente lo mides. A menudo los resultados son sorprendentes (al menos para mí).

Sí, para una N adecuadamente pequeña. Siempre habrá una N, sobre la cual siempre tendrá el pedido O (1) < O (lg N) < O (N) < O (N log N) < O (N ^ c) < O (c ^ N) (donde O (1) < O (lg N) significa que en un algoritmo O (1) tomará menos operaciones cuando N es adecuadamente grande y c es una constante fija que es mayor que 1) .

Supongamos que un algoritmo O (1) particular toma exactamente f (N) = 10 ^ 100 (a googol) y un algoritmo O (N) toma exactamente g (N) = 2 N + 5 operaciones. El algoritmo O (N) dará un mayor rendimiento hasta que N sea más o menos un googol (en realidad, cuando N > (10 ^ 100 - 5) / 2), por lo que si solo espera que N esté en el rango de 1000 a mil millones sufrirías una penalización mayor con el algoritmo O (1).

O para una comparación realista, digamos que están multiplicando números de n dígitos. El algoritmo de Karatsuba es como máximo 3 n ^ (lg 3) operaciones (que es aproximadamente O (n ^ 1.585)) mientras el Schönhage – Strassen algorithm es O (N log N log log N) es un pedido más rápido , pero para citar wikipedia:

  

En la práctica, el algoritmo de Schönhage-Strassen comienza a superar   Métodos más antiguos, como Karatsuba y Toom-Cook, multiplicación para   números más allá de 2 ^ 2 ^ 15 a 2 ^ 2 ^ 17 (10,000 a 40,000 decimales   dígitos). [4] [5] [6]

Entonces, si estás multiplicando números de 500 dígitos, no tiene sentido usar el algoritmo que es "más rápido" por los grandes argumentos de O.

EDITAR: puede encontrar determinar f (N) en comparación con g (N), tomando el límite N- > infinito de f (N) / g (N). Si el límite es 0, entonces f (N) < g (N), si el límite es infinito, entonces f (N) > g (N), y si el límite es alguna otra constante, entonces f (N) ~ g (N) en términos de notación O grande.

El método símplex para programación lineal puede ser exponencial en el peor de los casos, mientras que los algoritmos de puntos interiores relativamente nuevos pueden ser polinomiales .

Sin embargo, en la práctica, el peor caso exponencial para el método símplex no aparece: el método símplex es rápido y confiable, mientras que los primeros algoritmos de puntos interiores eran demasiado lentos para ser competitivos. (Ahora hay algoritmos de puntos interiores más modernos que son competitivos, pero el método símplex también es ...)

El algoritmo de Ukkonen para crear intentos de sufijo es O (n log n). Tiene la ventaja de estar "en línea", es decir, puede agregar más texto de manera incremental.

Recientemente, otros algoritmos más complejos han afirmado ser más rápidos en la práctica, en gran parte porque su acceso a la memoria tiene una mayor ubicación, lo que mejora la utilización de la memoria caché del procesador y evita las paradas de la CPU. Ver, por ejemplo, this encuesta , que afirma que el 70-80% del tiempo de procesamiento se invierte en esperar por la memoria, y este documento que describe el algoritmo" wotd ".

Los intentos de sufijo son importantes en genética (para secuencias genéticas coincidentes) y, algo menos importante, en la implementación de los diccionarios de Scrabble.

Siempre hay el algoritmo más rápido y más corto para cualquier problema bien definido . Sin embargo, solo es teóricamente el algoritmo (asintóticamente) más rápido.

Dada cualquier descripción de un problema P y una instancia de ese problema I , enumera todos los algoritmos posibles A y las pruebas Pr , verificando para cada uno de esos pares si Pr es una prueba válida de que A es el algoritmo asintóticamente más rápido para P . Si encuentra tal prueba, ejecuta A en I .

La búsqueda de este par a prueba de problemas tiene una complejidad O (1) (para un problema corregido P ), por lo que siempre usa el algoritmo asintóticamente más rápido para el problema. Sin embargo, dado que esta constante es tan indeciblemente enorme en casi todos los casos, este método es completamente inútil en la práctica.

Muchos lenguajes / marcos de trabajo utilizan una combinación de patrones ingenua para unir cadenas en lugar de KMP . Buscamos cuerdas como Tom, Nueva York, en lugar de ababaabababababababababababab.