¿En qué curso estudian las especialidades de CS la teoría de la complejidad (encontrar la complejidad de los algoritmos, la notación big-O)?

Es difícil decirle con seguridad si no conocemos su plan de estudios. Sin embargo, para “encontrar complejidad de algoritmos, notación de gran O” es seguro decir que la mayor parte estará en el curso de Algoritmos y Estructuras de datos. Es posible que tenga algunos conceptos básicos anteriores sobre cursos como Introducción a la informática o similares, si los tiene, pero la mayor parte del tema se tratará en ADS; solo cuando aprenda los algoritmos, también aprenderá sus complejidades y cómo determinarlos.

Si su plan de estudios le proporciona el aprendizaje de la teoría de la complejidad (que no es realmente lo mismo), probablemente será un curso separado (probablemente electivo) por su propio nombre. Computación / Teoría de la computabilidad (aunque la teoría de la computabilidad es todavía otra cosa, pero posiblemente se pueden rellenar en un curso). También puede haber partes de la teoría de la complejidad cerca del final de su curso de Teoría de Automatas, Idiomas y Computación. Pero como ve, hay muchas posibilidades, así que tal vez su plan de estudios lo resuelva de alguna otra manera en la que simplemente no he pensado ahora.

En Georgia Tech, hay un curso graduado de “Introducción a los algoritmos” en el que se cubre gran parte de esto. Creo que también está cubierto en un curso de pregrado similar. Busque un curso que requiera que compre una copia de CLRS o de uno de sus competidores.

El diseño y análisis de algoritmos es el curso donde se analizan estudios detallados sobre notaciones asintomáticas. Y como resolver las relaciones de recurrencia.