name keywords google algorithm time-complexity

algorithm - keywords - meta tags seo 2018



Peor es mejor Hay un ejemplo? (23)

"Worse is Better" se puede ver también en idiomas, por ejemplo las ideas detrás de Perl, Python, Ruby, Php incluso C # o Java, o cualquier lenguaje que no sea ensamblador o C (C ++ podría caber aquí o no).

Básicamente siempre hay una solución "perfecta", pero muchas veces es mejor usar una herramienta / algoritmo / lenguaje "peor" para obtener resultados más rápidos y con menos dolor. Es por eso que las personas usan estos lenguajes de alto nivel, aunque son "peores" desde el punto de vista del lenguaje informático ideal, y en cambio están más orientados a los humanos.

¿Existe un algoritmo ampliamente utilizado que tenga una complejidad de tiempo peor que la de otro algoritmo conocido, pero es una mejor opción en todas las situaciones prácticas ( peor complejidad pero mejor de lo contrario)?

Una respuesta aceptable puede estar en una forma:

Hay algoritmos A y B que tienen O(N**2) y O(N) complejidad de tiempo correspondientemente, pero B tiene una gran constante que no tiene ventajas sobre A para entradas menos que un número de átomos en el Universo.

Ejemplos destacados de las respuestas:

  • Algoritmo Simplex - el peor caso es el tiempo exponencial - frente a algoritmos de tiempo polinomial conocidos para problemas de optimización convexa.

  • Una ingenua mediana del algoritmo de las medianas - el peor de los casos O (N ** 2) vs. conocido algoritmo O (N).

  • Motores regex de retroceso - motores exponenciales en el peor de los casos frente a O (N) Thompson NFA.

Todos estos ejemplos aprovechan el peor de los casos frente a los escenarios promedio.

¿Hay ejemplos que no dependen de la diferencia entre el peor de los casos frente al escenario medio?

Relacionado:

  • El aumento de `` Peor es mejor '''' . (A los fines de esta pregunta, la frase "Peor es mejor" se usa en un sentido más restringido (a saber, la complejidad del tiempo algorítmico) que en el artículo)

  • Filosofía de diseño de Python :

    El grupo ABC se esforzó por la perfección. Por ejemplo, usaron algoritmos de estructura de datos basados ​​en árboles que resultaron ser óptimos para colecciones asintóticamente grandes (pero no tan buenas para colecciones pequeñas).

    Este ejemplo sería la respuesta si no hubiera computadoras capaces de almacenar estas grandes colecciones (en otras palabras, lo grande no es lo suficientemente grande en este caso).

  • El algoritmo de Coppersmith-Winograd para la multiplicación de la matriz cuadrada es un buen ejemplo (es el más rápido (2008) pero es de algoritmos inferiores a peores). ¿Cualquier otro? Del artículo de la wikipedia: "No se usa en la práctica porque solo proporciona una ventaja para matrices tan grandes que no pueden ser procesadas por hardware moderno (Robinson 2005)".

El género Radix tiene O (n) de complejidad de tiempo para las entradas de longitud fija, pero el quicksort se usa con mayor frecuencia, a pesar del peor tiempo de ejecución asympotic, porque la sobrecarga por elemento en el ordenamiento de Radix suele ser mucho mayor.

Esta declaración se puede aplicar a casi cualquier algoritmo paralelo . La razón por la que no se investigaron mucho en los primeros días de la informática es porque, para un único hilo de ejecución (piense en uniprocesador), son de hecho más lentos que sus contrapartidas secuenciales conocidas en términos de complejidad asintótica, factores constantes para n pequeña, o ambos. Sin embargo, en el contexto de las plataformas informáticas actuales y futuras, un algoritmo que pueda utilizar algunos elementos de procesamiento (piense en varios núcleos), unos cientos (piense en GPU) o unos pocos miles (piense en un superordenador) superará los valores de la versión secuencial en la hora del reloj de pared, incluso si el tiempo total / energía consumida por todos los procesadores es mucho mayor para la versión paralela.

Las clases, los algoritmos de gráficos y las técnicas de álgebra lineal por igual se pueden acelerar en términos de tiempo de reloj de pared al soportar el costo de un poco más de contabilidad, comunicación y sobrecarga de tiempo de ejecución para poder paralelizar.

Hay un algoritmo O (n) para seleccionar el k-ésimo elemento más grande de un conjunto no ordenado, pero rara vez se utiliza en lugar de ordenar, que es, por supuesto, O (n logn).

Siempre he entendido que el término "peor es mejor" se relaciona con problemas con soluciones correctas que son muy complejas donde existe una solución aproximada (o lo suficientemente buena) que es relativamente más fácil de comprender.

Esto facilita el diseño, la producción y el mantenimiento.

La integración de Monte Carlo es un método probabilístico de cálculo de integrales definidas que no tiene garantía de devolver la respuesta correcta. Sin embargo, en situaciones del mundo real, devuelve una respuesta precisa mucho más rápido que los métodos provablemente correctos.

quick-sort tiene la peor complejidad de tiempo de caso de O (N ^ 2) pero generalmente se considera mejor que otros algoritmos de clasificación que tienen complejidad de tiempo O (N log n) en el peor de los casos.

Este ejemplo sería la respuesta si no hubiera computadoras capaces de almacenar estas grandes colecciones.

Es de suponer que el tamaño de la colección fue 641K.

Cuando trabajábamos en el grupo de informática técnica para BAE SYSTEMS, que cuidaba el código estructural y aerodinámico de varias aeronaves, teníamos una base de código que se remontaba al menos a 25 años (y un tercio del personal había estado allí durante tanto tiempo).

Muchos de los algoritmos fueron optimizados para el rendimiento en un mainframe de 16 bits, en lugar de para la escalabilidad. Estas optimizaciones fueron totalmente apropiadas para el hardware de la década de 1970, pero funcionaron mal en conjuntos de datos más grandes en los sistemas de 32 y 64 bits que lo reemplazaron. Si elige algo con peor escalabilidad que funcione mejor en el hardware en el que está trabajando actualmente, tenga en cuenta que se trata de una optimización, y puede que no se aplique en el futuro. En el momento en que se escribieron esas rutinas de los años setenta, el tamaño de los datos que incluimos en los años 2000 no era práctico. Desafortunadamente, tratar de extraer un algoritmo claro de esos códigos que luego podrían implementarse para adaptarse al hardware moderno no fue trivial.

Aparte de hervir los océanos, lo que cuenta como ''todas las situaciones prácticas'' a menudo es una variable dependiente del tiempo.

Bien, considere resolver el problema del vendedor ambulante. La ÚNICA solución perfecta es probar todas las rutas posibles. Sin embargo, eso se vuelve imposible con nuestro hardware y los límites de tiempo a medida que N aumenta. Entonces, hemos pensado en muchas heurísticas.

Lo que nos lleva a la respuesta de tu pregunta. La heurística (peor) es mejor que la fuerza bruta para los problemas NP-completos. Esto describe la situación en la que "Peor es mejor" siempre es cierto.

Mergesort versus Quicksort

La ordenación rápida tiene una complejidad de tiempo promedio de O ( n log n ). Puede ordenar matrices en su lugar, es decir, una complejidad espacial de O (1).

Merge sort también tiene una complejidad de tiempo promedio de O ( n log n ), sin embargo, su complejidad de espacio es mucho peor : Θ ( n ). (hay un caso especial para listas enlazadas)

Debido al peor de los casos, la complejidad de ordenación rápida es Θ (n ^ 2) (es decir, todos los elementos caen en el mismo lado de cada pivote) y el peor caso de mergesort es O ( n log n ), mergesort es la opción predeterminada para la biblioteca implementadores.

En este caso, creo que la previsibilidad de la peor complejidad de tiempo de casos de mergesort supera a los quicksorts con requisitos de memoria mucho menores.

Dado que es posible reducir enormemente la probabilidad del peor caso de complejidad de tiempo de la solución rápida (por ejemplo, mediante la selección aleatoria del pivote), creo que podría argumentarse que el mergesort es peor en todos menos en el caso patológico de la oferta rápida.

Al calcular la mediana de un grupo de números, puede usar un algoritmo muy similar a quicksort. Se divide alrededor de un número, y todos los más grandes van hacia un lado, y todos los más pequeños van hacia el otro lado. Luego tiras un lado y calcula recursivamente la mediana del lado más grande. Esto toma O (n ^ 2) en el peor de los casos, pero es bastante rápido (O (n) con una constante baja) en el caso promedio.

Puede obtener el rendimiento O (n) en el peor de los casos, con una constante de alrededor de 40. Esto se conoce como el algoritmo de la mediana de las medianas . En la práctica, nunca usarías esto.

El ordenamiento por inserción a pesar de tener una complejidad O (n 2 ) es más rápido para colecciones pequeñas (n <10) que cualquier otro algoritmo de clasificación. Eso es porque el ciclo anidado es pequeño y se ejecuta rápidamente. Muchas bibliotecas (incluyendo STL) que tienen la implementación del método de clasificación realmente lo utilizan para pequeños subconjuntos de datos para acelerar las cosas.

Si entiendo la pregunta, estás pidiendo algoritmos teóricamente mejores pero prácticamente peores en todas las situaciones. Por lo tanto, uno no esperaría que se usen realmente a menos que por error.

Un posible ejemplo es la memoria universal. Teóricamente, todas las llamadas a funciones determinísticas deben ser memorizadas para todas las entradas posibles. De esta forma, los cálculos complejos podrían reemplazarse por simples búsquedas de tablas. Para una amplia gama de problemas, esta técnica comercializa de manera productiva el espacio de almacenamiento. Pero supongamos que hubiera un repositorio central de los resultados de todas las entradas posibles para todas las posibles funciones utilizadas por todas las computadoras de la humanidad. La primera vez que alguien en algún lugar hiciera un cálculo sería la última vez. Todos los intentos posteriores darían lugar a una búsqueda de tablas.

Pero hay varias razones por las que puedo pensar para no hacer esto:

  1. El espacio de memoria requerido para almacenar todos los resultados probablemente sea increíblemente grande. Parece probable que el número de bits necesarios exceda el número de partículas en el universo. (Pero incluso la tarea de estimar ese número es desalentadora).

  2. Sería difícil construir un algoritmo eficiente para hacer la memorización de ese enorme espacio problemático.

  3. El costo de la comunicación con el repositorio central probablemente excederá el beneficio a medida que aumente el número de clientes.

Estoy seguro de que puedes pensar en otros problemas.

De hecho, este tipo de intercambio de tiempo / espacio es increíblemente común en la práctica. Idealmente, todos los datos se almacenarían en la memoria caché L1, pero debido a las limitaciones de tamaño, siempre es necesario colocar algunos datos en el disco o (¡horrores!) Cinta. El avance de la tecnología reduce parte del dolor de estas compensaciones, pero como sugerí anteriormente, existen límites.

En respuesta al comentario de JF Sebastian:

Supongamos que en lugar de un repositorio universal de memorización, consideramos un repositorio factorial. Y no contendrá los resultados para todas las entradas posibles. ¡Más bien estará limitado a los resultados de 1 a N! Ahora es fácil ver que cualquier computadora que tenga factoriales se beneficiaría de buscar el resultado en lugar de hacer el cálculo. ¡Incluso para calcular (N+1)! la búsqueda sería una gran ganancia ya que ese cálculo se reduciría a N!(N+1) .

Ahora, para empeorar este algoritmo "mejor", podríamos aumentar N o aumentar la cantidad de computadoras que usan el repositorio.

Pero probablemente no entiendo la sutileza de la pregunta. De la manera en que pienso en ello, sigo aportando ejemplos que escalan bien hasta que no lo hacen.

Ya se sugirió la integración de Monte carlo, pero un ejemplo más específico es la fijación de precios de Monte Carlo en las finanzas también es una sugerencia. Aquí el método es mucho más fácil de codificar y puede hacer más cosas que otros, PERO es mucho más lento que, por ejemplo, la diferencia finita.

no es práctico hacer algoritmos de diferencias finitas de 20 dimensiones, pero una ejecución de precios en 20 dimensiones es fácil de configurar.

Algoritmo de Coppersmith-Winograd para la multiplicación de la matriz cuadrada. Su complejidad temporal es O (n 2,376 ) vs. O (n 3 ) de un algoritmo de multiplicación ingenuo o vs. O (n 2,807 ) para el algoritmo Strassen .

Del artículo de wikipedia:

Sin embargo, a diferencia del algoritmo Strassen, no se usa en la práctica porque solo proporciona una ventaja para matrices tan grandes que no pueden ser procesadas por hardware moderno (Robinson 2005).

El tipo de Spaghetti es mejor que cualquier otro algoritmo de clasificación en que es O (n) para configurar, O (1) para ejecutar y O (n) para extraer los datos ordenados. Logra todo esto en O (n) complejidad espacial. (Rendimiento general: O (n) en tiempo y espacio ambos). Sin embargo, por alguna razón extraña (obvia), nadie lo usa para nada, prefiriendo los algoritmos O (nlogn) muy inferiores y su tipo.

Profundización iterativa

Cuando se compara con una búsqueda trivial de profundidad-profundidad aumentada con poda alfa-beta, una búsqueda de profundización iterativa usada junto con una heurística de ordenamiento de ramificación pobre (o inexistente) daría como resultado que se escaneen muchos más nodos. Sin embargo, cuando se utiliza una buena heurística de ordenación de ramificación, se elimina una parte importante del árbol debido al efecto mejorado de la poda alfa-beta. Una segunda ventaja no relacionada con la complejidad del tiempo o el espacio es que una conjetura de la solución sobre el dominio del problema se establece temprano y esa conjetura se refina a medida que avanza la búsqueda. Es esta segunda ventaja la que lo hace tan atractivo en muchos dominios problemáticos.

Un ejemplo es de geometría computacional. La triangulación de polígonos tiene el peor algoritmo de O (N) debido a Chazelle , pero casi nunca se implementa en la práctica debido a la dureza de la implementación y la gran constante.

No del todo acertada, pero las expresiones regulares basadas en retroceso tienen un peor caso exponencial frente a O (N) para las expresiones regulares basadas en DFA, sin embargo, las expresiones regulares basadas en retroceso casi siempre se usan en lugar de las basadas en DFA.

EDITAR: (JFS)

La coincidencia de expresión regular puede ser simple y rápida (pero es lenta en Java, Perl, PHP, Python, Ruby, ...) :

El poder que las referencias posteriores añaden tiene un gran costo: en el peor de los casos, las implementaciones más conocidas requieren algoritmos de búsqueda exponenciales.

Motores de expresión regular :

Este método (DFA) es realmente más eficiente, e incluso se puede adaptar para permitir la captura y el emparejamiento no codicioso , pero también tiene importantes inconvenientes:

  • Las miradas son imposibles
  • Las referencias posteriores también son imposibles
  • La precompilación de Regex es más larga y requiere más memoria

Del lado positivo, además de evitar los tiempos de ejecución exponenciales en el peor de los casos, los enfoques de DFA evitan el uso de pila en el peor de los casos, que es lineal en el tamaño de los datos de entrada.

[3]:

Existe un algoritmo de tiempo polinomial para determinar la primalidad, pero en la práctica, siempre es más rápido usar un algoritmo de tiempo exponencial o realizar suficientes cálculos probabilísticos para tener la certeza suficiente.

Simplex es un algoritmo que tiene una complejidad de tiempo exponencial en el peor de los casos, pero para cualquier caso real es polinomio. Probablemente existen algoritmos polinomiales para la programación lineal, pero son muy complicados y suelen tener grandes constantes.

Quick-sort has worst case time complexity of O(N^2)! It is considered better than other sorting algorithms like mergesort heapsort etc. which have O(N log n) time complexity in the worst case. The reason may be the 1.in place sorting 2.stability, 3.very less amount of code involved.