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.¿Aplicó la teoría de la complejidad computacional en la vida real?
Puedo estar equivocado, pero si usted ha pasado por este camino antes, ¿podría proporcionar un ejemplo de cómo la teoría de la complejidad ayudado en su trabajo? Toneladas de gracias.
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 de datos. Duele por muy grande n.
O (n * log (n)): un algoritmo que hace una especie de estrategia de dividir y conquistar. Duele por grande n. Ejemplo típico: merge sort
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 for 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 mejor alternativa. El tiempo de cálculo puede explotar con n = n + 1.
Al mover su algoritmo hacia abajo desde 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 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 C Naive escribir este tipo de bucle:
for (int cnt=0; cnt < strlen(s) ; cnt++) {
/* some code */
}
Eso es un O (n * n) algoritmo debido a la aplicació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 has also written about this.
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 golpe, también.
Un buen ejemplo podría ser cuando su jefe le dice que haga algún programa y se puede demostrar mediante el uso de la teoría de la complejidad computacional que lo que su jefe está pidiendo que hagas no es posible.
Hay puntos en el tiempo cuando se enfrentan a problemas que requieren pensando en ellos. Hay muchos problemas del mundo real que requieren la manipulación de la gran cantidad de datos ...
ejemplos son:
aplicaciónRealizar 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 hacer una GRAN diferencia cuando la "n" se mide en días si no en meses.
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 que lo usan.
Sí, mi conocimiento de algoritmos de ordenación vino muy bien un día, cuando tenía que ordenar una pila de exámenes de los estudiantes. Usé sort sort (pero no quicksort o heapsort). Cuando programo, solo empleo la rutina de clasificación que ofrece la biblioteca. (no he tenido que ordenar realmente 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 o cuándo y para muchas otras decisiones.
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 intuir que se puede decir "este algoritmo es O (n^2) así que no podemos 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.
pensamiento de la teoría rápidamente complejidad ha sido importante para mí en el procesamiento de datos de la empresa, SIG, la programación de gráficos y la comprensión de los algoritmos 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.
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 usted ha estudiado la complejidad, a continuación, usted entendería si alguien dice que es O (n^2) para una determinada DBMS. Sin la teoría de la complejidad, la persona tendría que explicar sobre los escaneos de tablas y demás. Si añadimos un índice para la tabla Order
CREATE INDEX ORDER_USERID ON Order(UserId)
A continuación, la consulta anterior podría ser O (n log n), lo que haría una gran diferencia para una gran base de datos, pero para una pequeña, entonces no es nada todas.
Se podría argumentar que la teoría de la complejidad no es necesaria para entender cómo funcionan las bases de datos, y serían correctas, pero la teoría de la complejidad proporciona un lenguaje para pensar y hablar de algoritmos que trabajan con datos.
'sí' y 'sin'
sí) Suelo utilizar big O-notation al desarrollar e implementar algoritmos. P. ej. 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 real mientras que el segundo requiere cálculos considerables.
En ocasiones los conocimientos acerca de NP complexities classes 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 anteriormente 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 ni 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 las palabras 'rápido' y 'lento', 'x segundos', etc.
Las computadoras no son inteligentes, harán lo que usted les indique. 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. Por lo tanto, tiene que trabajar en el algoritmo para hacerlo mejor.
Y luego, necesita capacitación, para detectar las optimizaciones cerebrales que parecen 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:
Sí, con frecuencia utilizan la notación Big-O, o más bien, utilizo los procesos de pensamiento detrás de él, no la notación en sí. 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. Es sólo una idea ;-)
Hay un montón de buenos consejos aquí, y estoy seguro que la mayoría de los programadores han utilizado sus conocimientos 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 oíste, esas cosas "inútiles" son el tipo de cosas que la programación de juegos sigue viviendo.
Apuesto que muy pocos profesionales probablemente se preocupan por el Big-O tanto como los programadores de juegos.
@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. enfoques que podría tomar. p.ej. O (n * n) versus algo más rápido, p. buscando palabras almacenadas en una lista versus almacenadas en un trie (ejemplo ideado)
Creo que hace una diferencia con las estructuras de datos que elegiré usar y cómo trabajaré en un gran número de registros.
utilizo regularmente cálculos de complejidad, en gran parte porque trabajo en el dominio geoespacial con grandes bases de datos, 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 a similar post, también verá una gran notación O que se vuelve engorrosa cuando comienza 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 sus algoritmos bajo un generador de perfiles para ver si lo que han diseñado es lo que han 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 más lectura en algoritmos generales y sus complejidades He encontrado Sedgewicks work la vez informativo y accesible. Para algoritmos espaciales, el libro O'Rourkes sobre geometría computacional es excelente.
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.
En resumen, algunas personas escriben código que es basura, pero ni siquiera pueden comprender por qué es basura. La notación Big-O puede ser una ayuda para hacerles saber que junto con la notación que desconocen, es un efecto de ralentización del tiempo de ejecución del mundo real de su código, que depende de la longitud de n en este caso (variable en tiempo de ejecución), que no entienden que el código comienza mal y empeora a medida que crece el tamaño de su conjunto de datos. –