theory - problemas - teoría polinomial no determinístico

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

Es extremadamente importante. Si no comprende cómo estimar y calcular cuánto tardarán en ejecutarse los algoritmos, terminará escribiendo un código bastante lento. Pienso en la complejidad de la comprativa todo el tiempo al escribir algoritmos. Es algo que siempre deberías tener en cuenta cuando programes.

Esto es especialmente cierto en muchos casos porque aunque su aplicación funcione 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 se conecte con ella, y hay cientos de miles de personas usándolo

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

Podría estar equivocado, pero si ha seguido este camino antes, ¿podría darnos un ejemplo de cómo la teoría de la complejidad lo ayudó en su trabajo? Toneladas de gracias.

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

Los ejemplos son:

Aplicación de mapas ... como Google Maps: ¿cómo procesarías los datos de la línea de carretera en todo el mundo y los dibujarías? ¡y necesitas dibujarlos rápido!
La aplicación de logística ... piensa en el hombre de ventas que viaja con esteroides
Minería de datos ... todas las grandes empresas lo necesitan, ¿cómo explotarías una base de datos que contiene 100 tablas y 10m + filas y obtendrás resultados útiles antes de que las tendencias se desactualicen?

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

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

Las computadoras no son inteligentes, harán lo que les indiques hacer. Los compiladores pueden optimizar un poco el código para usted, pero no pueden optimizar los algoritmos. El cerebro humano funciona de manera diferente y es por eso que necesita comprender la Gran O. Considere calcular los números de Fibonacci. Todos conocemos 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 los idiomas imperativos). De alguna manera, nuestro algoritmo optimizado para el cerebro, pero el compilador no puede hacer esto. Entonces, tienes que trabajar en el algoritmo para hacerlo mejor.

Y luego, necesita capacitación, para detectar las optimizaciones cerebrales que se ven tan obvias, para ver cuándo el código puede ser ineficaz, para conocer los patrones de los algoritmos malos y buenos (en términos de complejidad computacional), y así sucesivamente. Básicamente, esos cursos sirven varias cosas:

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

Para la mayoría de los tipos de trabajo de programación, la parte teórica y las pruebas pueden no ser útiles en sí mismas, pero lo que están haciendo es intentar darte la intuición de poder decir inmediatamente "este algoritmo es O (n ^ 2) para que podamos '' t ejecutarlo en estos un 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 la teoría de la complejidad ha sido importante para mí en el procesamiento de datos comerciales, GIS, programación de gráficos y algoritmos de comprensión en general. Es una de las lecciones más útiles que puede obtener de los estudios de CS en comparación con lo que, en general, usted mismo autoaprendería.

Sí, mi conocimiento de los algoritmos de clasificación me fue útil algún día cuando tuve que ordenar una pila de exámenes de estudiantes. Usé sort sort (pero no quicksort o heapsort). Cuando programo, solo empleo la rutina de clasificación que ofrece la biblioteca. (Todavía no ha tenido que ordenar una gran cantidad de datos).

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

'' sí '' y '' no ''

sí ) Con frecuencia uso una notación O grande al desarrollar e implementar algoritmos. Por ejemplo, cuando debe manejar 10 ^ 3 elementos y la complejidad del primer algoritmo es O (n log (n)) y del segundo O (n ^ 3), simplemente puede decir que el primer algoritmo es casi en tiempo real mientras que el segundo requiere cálculos considerables.

A veces, los conocimientos sobre las clases de complejidad NP pueden ser útiles. Puede ayudarte a darte cuenta de que puedes dejar de pensar en inventar algoritmos eficientes cuando algún problema NP-complete puede reducirse al problema que estás pensando.

no ) Lo que he descrito arriba es una pequeña parte de la teoría de las complejidades. Como resultado, es difícil decir que lo uso, utilizo una parte minoritaria menor.

Debo admitir que hay muchos proyectos de desarrollo de software que no afectan el desarrollo de algoritmos o el uso de ellos de manera sofisticada. En tales casos, la teoría de la complejidad es inútil. Los usuarios habituales de algoritmos operan con frecuencia usando palabras ''rápido'' y ''lento'', ''x segundos'', etc.

@Martin: ¿Pueden explicar los procesos de pensamiento detrás de esto?

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

Encuentro que hace una diferencia con las estructuras de datos que elegiré usar y cómo trabajaré en un gran número de registros.

Aquí hay muchos buenos consejos, y estoy seguro de que la mayoría de los programadores han usado sus conocimientos de complejidad de vez en cuando.

Sin embargo, ¡debería decir que comprender la complejidad computacional es de extrema importancia en el campo de los Juegos! Sí, lo oíste, esas cosas "inútiles" son el tipo de cosas que la programación de juegos sigue viviendo.

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

Sí, uso con frecuencia la notación Big-O, o más bien, utilizo los procesos de pensamiento detrás de ella, no la notación en sí misma. En gran parte porque muy pocos desarrolladores en la (s) organización (es) lo comprendo frecuentemente. No quiero ser irrespetuoso con esas personas, pero en mi experiencia, el conocimiento de estas cosas es una de esas cosas que "clasifica a los hombres de los niños".

Me pregunto si esta es una de esas preguntas que solo 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 pueda responder no quizás no entienda la pregunta y, por lo tanto, salte a la siguiente pregunta en lugar de detenerse para responder. Solo un pensamiento ;-)

Un buen ejemplo podría ser cuando su jefe le dice que haga algún programa y puede demostrar usando la teoría de la complejidad computacional que lo que su jefe le está pidiendo que haga no es posible.

Si bien es cierto que uno puede llegar muy lejos en el desarrollo de software sin la más mínima comprensión de la complejidad algorítmica. Me parece que uso mi conocimiento de la complejidad todo el tiempo; sin embargo, en este punto a menudo es sin darse cuenta. Las dos cosas que el aprendizaje de la complejidad le proporciona 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 no escriben sus propios géneros). Lo más útil que te da 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 tuviera que ver la siguiente consulta, su comprensión de la consulta es muy diferente si ha estudiado la complejidad.

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

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

CREATE INDEX ORDER_USERID ON Order(UserId)

Entonces, la consulta anterior podría ser O (n log n), lo que supondría una gran diferencia para una gran base de datos, 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 que serían correctas, pero la teoría de la complejidad proporciona un lenguaje para pensar y hablar de algoritmos que trabajan con datos.

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 de manera eficiente. Ejemplo: algoritmos de árbol binario y búsqueda binaria. Usualmente no duele Tienes suerte si tienes ese algoritmo a mano.

O (n): un solo bucle sobre los datos. Duele por muy grande n.

O (n * log (n)): un algoritmo que hace algún tipo de estrategia de dividir y conquistar. Duele por grande n. Ejemplo típico: tipo de fusión

O (n * n): un bucle anidado de algún tipo. Duele incluso con pequeñas n. Común con cálculos de matriz ingenua. 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 muy pequeño n.

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

Mover su algoritmo de una clase de complejidad más alta puede hacer que su algoritmo vuele. Piense en la transformación de Fourier que tiene un algoritmo O (n * n) que no se puede usar con el hardware de los años 60 excepto en casos excepcionales. Luego Cooley y Tukey hicieron algunas reducciones inteligentes de complejidad al reutilizar los valores ya calculados. Eso condujo a la introducción generalizada de FFT en el procesamiento de señales. Y al final también es la razón por la cual Steve Jobs hizo una fortuna con el iPod.

Ejemplo simple: los programadores de Naive 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 de anidación conducen a la multiplicación de complejidades dentro de la gran O. O (n) dentro de O (n) da O (n * n). O (n ^ 3) dentro de O (n) da O (n ^ 4). En el ejemplo, el precalculo de la longitud de la cuerda convertirá inmediatamente el ciclo en O (n). Joel también ha escrito sobre esto.

Sin embargo, la clase de complejidad no es todo. Tienes que vigilar el tamaño de n. Volver a trabajar un algoritmo O (n * log (n)) a O (n) no ayudará si el número de instrucciones (ahora lineales) crece masivamente debido a la reelaboración. Y si n es pequeño de todos modos, la optimización no dará mucho, también.

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

Utilizo cálculos de complejidad regularmente, en gran parte porque trabajo en el dominio geoespacial con conjuntos de datos muy grandes, por ejemplo, procesos que involucran millones y en ocasiones miles de millones de coordenadas cartesianas. Una vez que comienzas a atacar problemas multidimensionales, la complejidad puede ser un problema real, ya que los algoritmos codiciosos que serían O (n) en una dimensión repentinamente saltan a O (n ^ 3) en tres dimensiones y no se necesitan demasiados datos para crear un serio cuello de botella. Como mencioné en una publicación similar , también ves una gran notación O volviéndose engorrosa cuando comienzas a tratar con grupos de objetos complejos de diferentes tamaños. El orden de la complejidad también puede ser muy dependiente de los datos, con casos típicos que funcionan mucho mejor que los casos generales para algoritmos ad hoc bien diseñados.

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

Para obtener más información sobre los algoritmos generales y sus complejidades, encontré que Sedgewicks funciona de manera informativa y accesible. Para los algoritmos espaciales, el libro de O''Rourkes sobre geometría computacional es excelente.