Page 20 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 20
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
¿Por qué estas y no otras? Simplemente porque son sencillas y porque la experiencia ha demostra-
do que aparecen con mayor frecuencia, de ahí que sea poco habitual que se requieran otras.
En el paso cuatro (orden de complejidad), a un conjunto de funciones que comparten un mismo
comportamiento asintótico se le denominará orden de complejidad. A estos conjuntos regularmente
se les llama O (gran O), y existe una infinidad de ellos; aun así, solo nos centraremos en algunos de
uso frecuente. Para cada uno de estos conjuntos se suele identificar un miembro f(n) que se utiliza
como representante de la clase (tabla 1.2).
Tabla 1.2. Conjuntos u órdenes de complejidad
La definición matemática de estos conjuntos debe ser muy cuidadosa para involucrar los dos aspec-
tos antes comentados:
• identificación de una familia y
• posible utilización como cota superior de otras funciones menos malas.
14
