Page 19 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 19
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
En el paso uno se decide cómo medir N. Decidimos el recurso que nos interesa:
Tiempo de ejecución = f(n).
A partir de aquí se analizará f(n). Como se verá más adelante, calcular la fórmula analítica exacta que
caracteriza a un algoritmo puede ser bastante laborioso. Habitualmente, no es necesario conocer el
comportamiento exacto, sino que basta con conocer una cota superior, es decir, alguna función que
se comporte “aun peor”. De esta forma, se puede afirmar que el programa práctico nunca superará
una cierta cota.
En el paso dos se decide la complejidad:
Dadas dos funciones f(n) y g(n), se dirá que f(n) es más compleja que g(n) cuando
Asimismo, se determinará que f(n) es menos compleja que g(n) cuando
Por último, se afirmará que f(n) es equivalente a g(n) cuando
Nótese que esta definición permite realizar no solo un análisis algorítmico conociendo la formulación
de la función, sino también un análisis experimental observando los recursos consumidos para va-
lores crecientes de N.
En el paso tres se suelen manejar las siguientes funciones:
13
