¿En qué partes de CLRS no debería centrarse un programador competitivo? Realmente no entiendo la importancia de saber cómo calcular la complejidad de un algoritmo o demostrar la exactitud de un algoritmo. ¿Debería omitir esta parte?

Hay partes de CLRS que quizás desee omitir, pero las partes que menciona en los detalles de la pregunta son definitivamente, definitivamente, no las partes que debe omitir. Se encuentran entre los contenidos más importantes.

Probar que sus programas son correctos es una habilidad esencial para cualquier buen programador. Es posible que no escriba pruebas formales, pero cada vez que escribe un código, siempre debe discutir por qué es correcto en su cabeza. Al hacerlo, puede descubrir que su lógica es incorrecta o no tiene en cuenta algunos casos de esquina. Alternativamente, puede descubrir que no es fácil determinar si es correcto o no, en cuyo caso volvería a escribir el código para que su corrección sea más obvia, lo que podría evitarle cometer un error. El principio es escribir programas que sean fácilmente verificables.

En la programación competitiva, un razonamiento muy preciso sobre la corrección del programa es en realidad aún más importante que en la programación típica porque hay un tiempo muy limitado para las pruebas. A menudo, debe estar bastante convencido de que sus programas funcionan en todos los casos después de hacer solo algunas pruebas rápidas en pequeños ejemplos (para descartar errores tontos). Un caso de esquina perdido a veces puede resultar en la falla de un problema completo.

En una nota relacionada, un error común de principiante es no comprender que la carga de la prueba está en probar la corrección y no en refutarla. No puede confiar en que un programa sea correcto a menos que pueda dar un argumento convincente de por qué es así. He visto (muy) malos programadores competitivos dar una respuesta a un problema, y ​​luego, cuando me preguntaron por qué esperaban que su solución fuera correcta, dijeron “bueno, ¿por qué no sería así? No puedo pensar en ningún caso para que falla “. Esa es una muy mala forma de abordar los problemas, y estas personas generalmente no llegan lejos. Ni siquiera pueden arreglar su código correctamente una vez que saben que no está funcionando, porque es muy probable que lo cambien a otra cosa que esté mal.

En resumen, ser capaz de razonar cuidadosamente sobre por qué su algoritmo es correcto es fundamental si desea ser consistentemente correcto.

Calcular la complejidad también es extremadamente importante: le da una idea de qué tan rápido se ejecutará su algoritmo, lo que le permite ver si es probable que su plan de acción supere las restricciones del problema antes de invertir tiempo en codificarlo. Un análisis de complejidad responde a la pregunta “¿mi idea actual es lo suficientemente buena o necesito buscar una idea mejor?” Hay muy poco que sea más importante que eso.

Hay ciertas partes de CLRS que puedes omitir si solo te interesan las competiciones. Cosas como montones binomiales, montones de Fibonacci, árboles vEB y redes de clasificación son principalmente de interés teórico y es poco probable que sean útiles en un concurso. Los árboles B y el subprocesamiento múltiple son importantes en la práctica, pero generalmente no son relevantes para los concursos de codificación. La mayoría de los otros temas se vuelven importantes en algún nivel de competencia. A medida que avanza en el nivel de habilidad, enfrentará problemas que involucran más y más conceptos.

¡Tipo! si no puede quedarse sin nada para terminar un libro de Algoritmo que se considera la Biblia del campo y se sigue en la mayoría de las principales instituciones de todo el mundo, ¿cómo puede esperar tener un buen desempeño en la programación competitiva?

La programación competitiva no es como un examen universitario que se puede hacer en una noche, salteando algunos capítulos. Es solo el comienzo donde está ahora (si planea lograr algo significativo), tiene un largo camino por recorrer, sea paciente, concéntrese en el aprendizaje, no tome atajos. ¡Y divertirse!