Algoritmos en pocas palabras, 2ª edición

Capítulo 2. Las matemáticas de los algoritmos

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

Uno de los factores más importantes para elegir un algoritmo es la velocidad con la que es probable que se complete. Caracterizar el tiempo de cálculo previsto de un algoritmo es inherentemente un proceso matemático. Este capítulo presenta las herramientas matemáticas que hay detrás de esta predicción del tiempo. Después de leer el capítulo, deberías entender los diversos términos matemáticos utilizados a lo largo de este libro -y en el resto de la literatura que describe algoritmos.

Tamaño de una instancia del problema

Una instancia de un problema es un conjunto concreto de datos de entrada dados a un programa. En la mayoría de los problemas, el tiempo de ejecución de un programa aumenta con el tamaño de este conjunto de datos. Al mismo tiempo, las representaciones demasiado compactas (posiblemente mediante técnicas de compresión) pueden ralentizar innecesariamente la ejecución de un programa. Resulta sorprendentemente difícil definir la forma óptima de codificar una instancia, porque los problemas ocurren en el mundo real y deben traducirse a una representación adecuada para ser resueltos por un programa.

Al evaluar un algoritmo, queremos asumir en la medida de lo posible que la codificación de la instancia del problema no es el factor determinante para saber si el algoritmo puede implementarse de forma eficiente. ...