Cómo saber qué algoritmo usar y cuándo

La pregunta no puede ser respondida lo suficientemente breve. Sin embargo, hay algunos pasos.

Me centro en los “algoritmos” en el sentido de las funciones matemáticas: la misma entrada produce siempre la misma salida; sin efectos secundarios. (Especialmente no quiero explicar cómo lidiar con los algoritmos / problemas en línea)

  1. Comprende el problema :
    ¿Qué es lo que hay que hacer? ¿Cómo se ven sus datos de entrada? ¿Cuál debería ser tu salida?
  2. Fuerza bruta : ¿Cómo resolverías el problema para una pequeña instancia? ¿Cómo lo resolverías con lápiz y papel?
    Si puede responder a esta pregunta, tendrá su primera solución. Es muy probable que sea extremadamente malo y eventualmente inutilizable incluso para casos de problemas de tamaño modesto, pero eventualmente puede crear casos de prueba de los cuales está seguro de conocer la entrada correcta y la salida correcta.
  3. ¿Puedes dividir el problema en 2 o más problemas más simples?
  4. Complejidad espacio / tiempo : ¿en qué clase es su mejor algoritmo actualmente? ¿Qué pasos necesitas hacer?
    Muy a menudo, no podrá determinar la clase de complejidad del problema, porque esto es básicamente O (n) (porque tiene que leer su entrada al menos una vez) u O (n log n) (porque tiene que ordenar).
  5. Conozca muchos algoritmos : consulte la Lista de algoritmos y la Categoría: Algoritmos
  6. Conozca muchas estructuras de datos : Lista de estructuras de datos y Categoría: Estructuras de datos
  7. Piensa en tus datos de entrada / salida . ¿Puede darle más estructura eligiendo una estructura de datos particular? ¿Puedes mejorar tu tiempo de acceso? ¿Qué acciones necesita tomar para llegar a la solución (leer / almacenar valores intermedios / construido)? Esto podría conducir a una estructura de datos que debe construir a partir de los datos.
  8. Clasificación : la mayoría de las veces solo le interesa “ajustar” su solución si es mucho más compleja que O (n log n). Entonces, desde un punto de vista teórico, la clasificación es gratuita. Por lo tanto, vale la pena pensarlo: ¿hay orden en mis datos? ¿Tiene algún uso ordenar?
  9. Conozca sus limitaciones : cuando tiene una solución, a menudo tiene que tomar una decisión cuando quiere mejorarla: ¿Quiere pasar más memoria y menos tiempo o viceversa? Deberías saber qué

Sin embargo, realmente dudo que esto te ayude. Como participas en Top Coder, supongo que ya eres bastante bueno.

Entonces podría ayudarte a aprender más sobre tu lenguaje de programación. Y practica. Mucho.

Para los concursos de programación, normalmente el tiempo de ejecución es un indicador de la bondad de su elección . Los jueces tienden a no preferir soluciones de fuerza bruta y les dan puntajes más bajos. Las soluciones de fuerza bruta normalmente están determinadas por sus tiempos de ejecución más largos. Entonces, los concursantes con soluciones más elegantes con los algoritmos apropiados tienden a tener tiempos de ejecución más cortos.

El diseño del algoritmo no es fácil, pero tampoco es tan difícil. Hay muchos algoritmos estándar a los que la mayoría de los problemas se asignan directamente. Estos problemas de diseño solo pueden resolverse mediante la práctica. Resuelva problemas en algún libro estándar de algo y luego intente problemas competitivos.