Algoritmos en pocas palabras, 2ª edición

Apéndice A. Evaluación comparativa

Cada algoritmo de este libro va acompañado de datos sobre su rendimiento. Como es importante utilizar los puntos de referencia adecuados para obtener un rendimiento preciso, en este apéndice presentamos nuestra infraestructura para evaluar el rendimiento de los algoritmos. Esto también debería ayudarte a resolver cualquier pregunta o duda que puedas tener sobre la validez de nuestro enfoque. Intentamos explicar los medios precisos por los que se calculan los datos empíricos, para permitirte tanto verificar que los resultados son precisos como comprender en qué casos las suposiciones son adecuadas dado el contexto en el que se pretende utilizar el algoritmo.

Existen numerosas formas de analizar los algoritmos. El Capítulo 2 presentó un tratamiento teórico y formal, introduciendo los conceptos de análisis del peor caso y del caso medio. Estos resultados teóricos pueden evaluarse empíricamente en algunos casos, pero no en todos. Por ejemplo, considera la evaluación del rendimiento de un algoritmo para ordenar 20 números. Hay 2,^43*1018 permutaciones de estos 20 números, y no podemos evaluar exhaustivamente cada una de estas permutaciones para calcular el caso medio. Además, no podemos calcular la media midiendo el tiempo necesario para ordenar todas estas permutaciones. Debemos basarnos en medidas estadísticas para asegurarnos de que hemos calculado correctamente el tiempo de rendimiento esperado del algoritmo.

Fundación Estadística

Este capítulo ...