¿Aplicaste la teoría de la complejidad computacional en la vida real?

Question

Estoy tomando un curso sobre complejidad computacional y hasta ahora tengo la impresión de que no será de mucha ayuda para un desarrollador.

Puede que me equivoque, pero si ya has seguido este camino antes, ¿podrías darnos un ejemplo de cómo te ayudó la teoría de la complejidad en tu trabajo?Toneladas de gracias.

Answer 1

O(1):Código simple sin bucles.Simplemente fluye.Las búsquedas en una tabla de búsqueda también son O(1).

O(log(n)):algoritmos optimizados eficientemente.Ejemplo:Algoritmos de árbol binario y búsqueda binaria.Generalmente no duele.Tienes suerte si tienes un algoritmo de este tipo a mano.

En):un solo bucle sobre datos.Duele por n muy grande.

O(n*log(n)):un algoritmo que hace algún tipo de estrategia de divide y vencerás.Duele por n grande.Ejemplo típico:fusionar ordenar

O(n*n):un bucle anidado de algún tipo.Duele incluso con n pequeña.Común con cálculos matriciales ingenuos.Desea evitar este tipo de algoritmo si puede.

O(n^x para x>2):una construcción perversa con múltiples bucles anidados.Duele por n muy pequeño.

O(x^n, n!y peor):algoritmos extraños (y a menudo recursivos) que no desea tener en el código de producción excepto en casos muy controlados, para n muy pequeña y si realmente no hay una mejor alternativa.El tiempo de cálculo puede explotar con n=n+1.

Bajar su algoritmo de una clase de mayor complejidad puede hacer que su algoritmo vuele.Piense en la transformación de Fourier, que tiene un algoritmo O(n*n) que no se podía utilizar con el hardware de los años 60, excepto en casos excepcionales.Luego, Cooley y Tukey hicieron algunas reducciones inteligentes de la complejidad reutilizando valores ya calculados.Esto llevó a la introducción generalizada de FFT en el procesamiento de señales.Y al final también es por eso que Steve Jobs hizo una fortuna con el iPod.

Ejemplo sencillo:Los programadores ingenuos de C escriben este tipo de bucle:

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

Ese es un algoritmo O(n*n) debido a la implementación de strlen().Los bucles anidados conducen a la multiplicación de complejidades dentro de la O grande.O(n) dentro de O(n) da O(n*n).O(n^3) dentro de O(n) da O(n^4).En el ejemplo, calcular previamente la longitud de la cadena convertirá inmediatamente el bucle en O(n). Joel también ha escrito sobre esto.

Sin embargo, la clase de complejidad no lo es todo.Hay que estar atento al tamaño de n.Reelaborar un algoritmo O(n*log(n)) a O(n) no ayudará si el número de instrucciones (ahora lineales) crece enormemente debido a la reelaboración.Y si n es pequeño de todos modos, la optimización tampoco dará mucho resultado.

Answer 2

Si bien es cierto que se puede llegar muy lejos en el desarrollo de software sin la más mínima comprensión de la complejidad algorítmica.Creo que uso mi conocimiento de la complejidad todo el tiempo;aunque, a estas alturas muchas veces es sin darnos cuenta.Las dos cosas que le brinda aprender sobre la complejidad como desarrollador de software son una forma de comparar algoritmos no similares que hacen lo mismo (los algoritmos de clasificación son el ejemplo clásico, pero la mayoría de las personas en realidad no escriben sus propias clasificaciones).Lo más útil que te ofrece es una forma de describir rápidamente un algoritmo.

Por ejemplo, considere SQL.SQL es utilizado todos los días por una gran cantidad de programadores.Si viera la siguiente consulta, su comprensión de la consulta sería muy diferente si hubiera estudiado la complejidad.

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

Si ha estudiado la complejidad, entendería si alguien dijera que es O(n^2) para un determinado DBMS.Sin la teoría de la complejidad, la persona tendría que explicar sobre escaneos de tablas y demás.Si agregamos un índice a la tabla Order

CREATE INDEX ORDER_USERID ON Order(UserId)

Entonces la consulta anterior podría ser O(n log n), lo que haría una gran diferencia para una base de datos grande, pero para una pequeña, no es nada en absoluto.

Se podría argumentar que la teoría de la complejidad no es necesaria para comprender cómo funcionan las bases de datos, y sería correcto, pero la teoría de la complejidad proporciona un lenguaje para pensar y hablar sobre los algoritmos que trabajan con datos.

Answer 3

Para la mayoría de los tipos de trabajos de programación, la parte teórica y las pruebas pueden no ser útiles en sí mismas, pero lo que hacen es tratar de darle la intuición de poder decir inmediatamente "este algoritmo es O(n^2), así que podemos". No lo ejecute en este millón de puntos de datos".Incluso en el procesamiento más elemental de grandes cantidades de datos, se encontrará con esto.

Pensar rápidamente en la teoría de la complejidad ha sido importante para mí en el procesamiento de datos empresariales, SIG, programación de gráficos y comprensión de algoritmos en general.Es una de las lecciones más útiles que puede obtener de los estudios de informática en comparación con lo que normalmente estudiaría por su cuenta.

Answer 4

Las computadoras no son inteligentes, harán lo que usted les indique.Los compiladores pueden optimizar un poco el código, pero no pueden optimizar los algoritmos.El cerebro humano funciona de manera diferente y es por eso que es necesario comprender la Gran O.Considere calcular los números de Fibonacci.Todos sabemos que F(n) = F(n-1) + F(n-2), y comenzando con 1,1 puedes calcular fácilmente los siguientes números sin mucho esfuerzo, en tiempo lineal.Pero si le dices a la computadora que lo calcule con esa fórmula (recursivamente), no sería lineal (al menos, en lenguajes imperativos).De alguna manera, nuestro algoritmo optimizado cerebralmente, pero el compilador no puede hacer esto.Entonces, tienes que trabajar sobre el algoritmo para hacerlo mejor.

Y luego, necesitas entrenamiento, para detectar optimizaciones cerebrales que parecen tan obvias, para ver cuándo el código puede ser ineficaz, para conocer patrones de algoritmos buenos y malos (en términos de complejidad computacional), etc.Básicamente, esos cursos sirven para varias cosas:

• comprender los patrones de ejecución y las estructuras de datos y qué efecto tienen en el tiempo que necesita para finalizar su programa;
• Entrene su mente para detectar posibles problemas en el algoritmo, cuando podría ser ineficiente en grandes conjuntos de datos.O comprender los resultados de la elaboración de perfiles;
• aprender formas conocidas de mejorar los algoritmos reduciendo su complejidad computacional;
• prepárate para pasar una entrevista en una buena compañía :)

Answer 5

Es extremadamente importante.Si no comprende cómo estimar y calcular cuánto tiempo tardarán en ejecutarse sus algoritmos, terminará escribiendo un código bastante lento.Pienso en la complejidad computacional todo el tiempo cuando escribo algoritmos.Es algo que siempre debes tener en cuenta al programar.

Esto es especialmente cierto en muchos casos porque, si bien su aplicación puede funcionar bien en su computadora de escritorio con un pequeño conjunto de datos de prueba, es importante comprender qué tan rápido responderá su aplicación una vez que la implemente, y hay cientos de miles de personas. usándolo.

Answer 6

Sí, frecuentemente uso la notación O grande, o más bien, uso los procesos de pensamiento detrás de ella, no la notación en sí.En gran parte porque muy pocos desarrolladores de las organizaciones que frecuento lo entienden.No quiero ser irrespetuoso con esas personas, pero en mi experiencia, el conocimiento de estas cosas es una de esas cosas que "separa a los hombres de los niños".

Me pregunto si esta es una de esas preguntas que sólo pueden recibir respuestas "sí".Me sorprende que el conjunto de personas que entienden la complejidad computacional es más o menos equivalente al conjunto de personas que piensan que es importante.Por lo tanto, cualquiera que responda que no tal vez no comprenda la pregunta y, por lo tanto, pase a la siguiente pregunta en lugar de hacer una pausa para responder.Solo un pensamiento ;-)

Answer 7

Hay momentos en los que enfrentará problemas que requerirán pensar en ellos.Hay muchos problemas del mundo real que requieren la manipulación de un gran conjunto de datos...

Ejemplos son:

• Aplicación de mapas...como Google Maps: ¿cómo procesarías los datos de las líneas de carreteras en todo el mundo y los dibujarías?¡Y necesitas dibujarlos rápido!
• Aplicación de logística...Piense en un vendedor ambulante con esteroides.
• Procesamiento de datos...todas las grandes empresas requieren uno, ¿cómo extraerías una base de datos que contenga 100 tablas y más de 10 millones de filas y obtendrías resultados útiles antes de que las tendencias queden obsoletas?

Tomar un curso sobre complejidad computacional lo ayudará a analizar y elegir/crear algoritmos que sean eficientes para tales escenarios.

Créame, algo tan simple como reducir un coeficiente, digamos de T(3n) a T(2n), puede generar ENORMES diferencias cuando la "n" se mide en días, si no en meses.

Answer 8

Hay muchos buenos consejos aquí y estoy seguro de que la mayoría de los programadores han utilizado su conocimiento de la complejidad de vez en cuando.

Sin embargo, debo decir que comprender la complejidad computacional es de extrema importancia en el campo de los juegos.Sí, lo escuchaste, esas cosas "inútiles" son el tipo de cosas sobre las que vive la programación de juegos.

Apuesto a que muy pocos profesionales se preocupan tanto por Big-O como los programadores de juegos.

Answer 9

Utilizo cálculos de complejidad con regularidad, en gran parte porque trabajo en el dominio geoespacial con conjuntos de datos muy grandes, p.procesos que involucran millones y ocasionalmente miles de millones de coordenadas cartesianas.Una vez que comienzas a enfrentar problemas multidimensionales, la complejidad puede ser un problema real, ya que los algoritmos codiciosos que serían O(n) en una dimensión de repente saltan a O(n^3) en tres dimensiones y no se necesitan muchos datos para resolverlos. crear un serio cuello de botella.Como mencioné en una publicación similar, también verá que la notación O grande se vuelve engorrosa cuando comienza a trabajar con grupos de objetos complejos de diferentes tamaños.El orden de complejidad también puede depender mucho de los datos, y los casos típicos funcionan mucho mejor que los casos generales para sistemas bien diseñados. ad hoc algoritmos.

También vale la pena probar sus algoritmos con un generador de perfiles para ver si lo que ha diseñado es lo que ha logrado.Creo que la mayoría de los cuellos de botella se resuelven mucho mejor ajustando el algoritmo que mejorando la velocidad del procesador por todas las razones obvias.

Para leer más sobre algoritmos generales y sus complejidades encontré El trabajo de Sedgewick informativo y accesible.Para algoritmos espaciales, O'Rourkes El libro sobre geometría computacional es excelente.

Answer 10

En tu vida normal, no cerca de una computadora, debes aplicar conceptos de complejidad y procesamiento paralelo.Esto le permitirá ser más eficiente.Coherencia de caché.Esa clase de cosas.

Answer 11

Sí, mis conocimientos sobre algoritmos de clasificación me resultaron útiles un día cuando tuve que ordenar una pila de exámenes de estudiantes.Utilicé ordenación por combinación (pero no ordenación rápida ni ordenación en montón).Cuando programo, simplemente empleo cualquier rutina de clasificación que ofrezca la biblioteca.(Aún no he tenido que ordenar una gran cantidad de datos).

Utilizo la teoría de la complejidad en la programación todo el tiempo, principalmente para decidir qué estructuras de datos usar, pero también para decidir si ordenar cosas y cuándo, y para muchas otras decisiones.

Answer 12

'Sí' y 'No'

Sí) Yo uso frecuentemente notación O grande al desarrollar e implementar algoritmos.P.ej.cuando debes manejar 10^3 elementos y la complejidad del primer algoritmo es O(n log(n)) y del segundo O(n^3), simplemente puedes decir que el primer algoritmo es casi en tiempo real mientras que el segundo requiere cálculos considerables.

A veces los conocimientos sobre Clases de complejidades NP puede ser útil.Puede ayudarle a darse cuenta de que puede dejar de pensar en inventar un algoritmo eficiente cuando algún problema NP completo puede reducirse al problema en el que está pensando.

No) Lo que he descrito anteriormente es una pequeña parte de la teoría de las complejidades.Como resultado, es difícil decir que lo uso, uso una parte menor o menor.

Debo admitir que hay muchos proyectos de desarrollo de software que no tocan el desarrollo de algoritmos ni su uso de manera sofisticada.En tales casos, la teoría de la complejidad es inútil.Los usuarios comunes de algoritmos operan frecuentemente usando palabras "rápido" y "lento", "x segundos", etc.

Answer 13

@Martín:¿Puedes explicarnos más detalladamente los procesos de pensamiento detrás de esto?

Puede que no sea tan explícito como sentarse y resolver la notación Big-O para una solución, pero crea conciencia del problema y eso lo orienta a buscar una respuesta más eficiente y a alejarse de los problemas en los enfoques que podría adoptar. .p.ej.O(n*n) versus algo más rápido, p.e.buscar palabras almacenadas en una lista versus almacenadas en un trie (ejemplo artificial)

Considero que hay una diferencia en las estructuras de datos que elegiré usar y en cómo trabajaré con una gran cantidad de registros.

Answer 14

Un buen ejemplo podría ser cuando tu jefe te dice que hagas algún programa y puedes demostrar, utilizando la teoría de la complejidad computacional, que lo que tu jefe te pide que hagas no es posible.