¿El concepto de complejidad computacional es importante para los desarrolladores de software? [cerrado]

Tenía la impresión de que los conceptos de tiempo y complejidad de la memoria son imprescindibles para los graduados de los cursos de compsci, pero después de haber estudiado ingeniería no tengo conocimiento si ese es el caso. Recientemente me ha sorprendido entrevistar a algunos graduados de una universidad local que ni siquiera conocen el concepto. Supongo que mi pregunta es:

¿El concepto de complejidad computacional es importante para los desarrolladores de software? ¿Y debería enseñarse en cursos de pregrado?

En la mayoría de las universidades, supongo (¡espero!) Que la complejidad del tiempo y la memoria es definitivamente parte de sus cursos.

Ahora, estas "complejidades" son un tema muy elástico. Si las personas realmente deberían conocer toda la teoría como "ZPP es la clase de complejidad de los problemas de decisión que se pueden resolver con cero errores en una máquina de Turing probabilística en tiempo polinómico". y ese tipo de cosas es cuestionable. Personalmente considero que estas teorías avanzadas son irrelevantes para el desarrollo de software.

Por el contrario, considero que cada desarrollador debe ser consciente de la complejidad de tiempo / espacio de las estructuras de datos y algoritmos que utilizan.

Muchos principiantes sufren de obsesión por la microoptimización. Aprendizaje comp. La complejidad conduce a los estudiantes hacia una forma mucho más práctica de estimar el rendimiento y la escalabilidad, en mi experiencia.

Por lo que he visto, parece que la notación Big-O y la complejidad del tiempo y la memoria se enfatizan mucho en la educación formal en informática ... sin embargo, siendo autodidacta, esta percepción se basa en escuchar y leer lo que las personas con tales educaciones decir y escribir.

Aunque creo que las ideas y conceptos generales son importantes, no creo que la formalización de la misma (como la notación big-O y la terminología variada) sea tan importante, excepto para los fines de la comunicación. El hecho de que alguien no esté familiarizado con la notación formal y la terminología no significa que no puedan ver cómo y por qué un algoritmo sería más rápido que otro en un caso particular. Las personas pueden ver que el tiempo necesario para buscar un árbol binario equilibrado se relaciona con el logaritmo de base 2 del número de nodos sin primero aprender sobre la teoría de la complejidad en ningún sentido formal, si entienden cómo funciona el árbol y tienen una comprensión razonable de la alta matemáticas de la escuela Sin embargo, es importante saber cuándo prestar atención a la complejidad y el uso de la memoria, y considerar los casos típicos y peores ... pero algunas personas no lo hacen.

La notación y la terminología se vuelven importantes para la comunicación. Ofrecen una buena manera de transmitir una cuantificación del rendimiento de un algoritmo a otra persona. Debido a que aparece en documentos y explicaciones con frecuencia, es útil tener al menos una comprensión vaga para que sean más fáciles de seguir.

Entonces sí, los conceptos son importantes (aunque menos cuando los recursos y el tiempo son amplios pero los datos no lo son). Pero aunque los conceptos son importantes, la formalización de ellos a menudo no es tan importante, y uno debe recordar que la notación y la terminología no son las mismas que los conceptos mismos.

Editar:

No diría que entiendo los conceptos con tanto detalle como alguien que ha estudiado formalmente, pero muchas de las ideas generales simplemente tienen sentido. Creo que hay valor en estudiar esto formalmente, pero parte de ese valor todavía puede existir sin él.

En cuanto a la introducción de los conceptos (fuera del estudio formal), creo que un buen comienzo es alentar a las personas a pensar sobre la cantidad de memoria que tienen las estructuras de datos, qué pasos involucran los algoritmos y cómo cambian estas cosas con diferentes datos.

También ayuda a considerar situaciones y cambios hipotéticos, como considerar qué sucede si un árbol está equilibrado versus qué sucede si está tan desequilibrado como sea posible, o cuántos niveles en el árbol estarían la mayoría de los nodos, o cuántos nodos más puede sostenga si la profundidad aumenta un nivel. Esta forma de pensar es generalmente útil para los programadores de todos modos, no solo cuando se mira la complejidad; y si se aplica a pensar sobre cómo funcionan los algoritmos y las estructuras de datos en diferentes circunstancias, naturalmente apunta en la misma dirección que lo haría un examen más formal de la complejidad.

si

Comprender los conceptos básicos de la complejidad es importante y debe ser algo que aprendas como estudiante. De hecho, creo que generalmente se menciona en cualquier clase que le enseñe sobre estructuras de datos. Puedo entender a los graduados que no entienden o no recuerdan, pero no puedo ver que no se les hayan enseñado los conceptos básicos de la complejidad.

Actualización: ¿Por qué es importante?

Estaba en una migración de base de datos en un trabajo en particular. Teníamos una fecha límite para cuándo debía realizarse la migración. La persona que escribió el guión no tenía ninguna base en la complejidad. Desafortunadamente, nadie más miró de cerca la lógica que utilizó en el guión. No recuerdo los detalles, aparte de que usó un bucle doblemente anidado en lugar de una tabla hash. Después de una semana de ejecución continua del script, observamos la lógica y nos dimos cuenta del problema. Tomó algo así como 5 horas para completar después del cambio. Casi perdimos la fecha límite para completar la migración como resultado de que alguien no comprende la complejidad.

El punto es que es fácil hacer accidentalmente algo que es de órdenes de magnitud más lento, o siempre se quedará sin memoria antes de que se complete el trabajo. Si bien las máquinas más rápidas con más memoria pueden mitigar pequeños errores, a menudo no pueden mitigar los problemas de complejidad.

Encuentro que preguntar si es "importante o no" es bastante vago.

Encontrarás a muchas personas evangelizando sobre cómo se requiere estrictamente el más mínimo conocimiento en este mundo en su opinión. Pero eso es un poco inútil, porque uno nunca puede saberlo todo, y no se debe esperar que lo haga a menos que le ayude a cumplir con los requisitos que plantea su trabajo. Prefiero adoptar un enfoque más pragmático de los requisitos educativos previos, en general, a menos que sea una afición o una preferencia personal arbitraria.

¿Es importante para los programadores que se espera que escriban código extremadamente eficiente o algoritmos de infraestructura innovadores? Si.

¿Es importante para los programadores que desarrollan aplicaciones web convencionales? Pueden administrar sin él u obtener implementaciones eficientes en el mundo de código abierto.

¿Es importante para los programadores que desarrollan GUI para aplicaciones? Probablemente no, porque los marcos de GUI exitosos abstraen todos esos pequeños detalles.

Siempre es bueno saberlo, como cualquier cosa, pero no impide que muchos (o incluso la mayoría) de los programadores simplemente hagan su trabajo para satisfacción de sus empleadores.

Por otro lado, si uno se inscribe en estudios superiores, en busca de educación fundamental y teórica, se debe esperar que aprenda materias que, por definición, son más teóricas que prácticas. En mi opinión, es esencial que CompSci. los estudiantes aprenden sobre la complejidad, así como es importante que aprendan sobre el cálculo

Pero de todos modos, desde cuándo CompSci. Qué programas enseñan a las personas a ser buenos programadores? Para eso, tiene programas de capacitación especializados y experiencia práctica (ya sea la suya o la de otros programadores que pueden compartir la suya con usted).