Algoritmia 3

Complejidad Algoritmica

Existen dos tipos de eficiencia: eficiencia de
tiempo y eficiencia de espacio.
La eficiencia de tiempo, también llamada
complejidad, indica qué tan rápido corre un
algoritmo en cuestión.
La eficiencia de espacio, también llamada
complejidad de espacio, se refiere a la cantidad
de unidades de memoria requeridas por el
algoritmo además del espacio necesitado para suentrada y salida.

Por supuesto, se puede simplemente utilizar
algunas unidades estándar de medición de
tiempo ( un segundo o milisegundo y así
sucesivamente) para medir el tiempo de
ejecución de un programa implementando un
algoritmo. Sin embargo hay inconvenientes
obvios a dicho acercamiento.

Un posible acercamiento es contar el número de
veces que cada una de las operaciones del
algoritmo esejecutada. Este acercamiento es
tanto muy díficil como usualmente innecesario.
Lo que hay que hacer es identificar la operación
más importante del algoritmo, llamada la
operación básica, la operación que más
contribuye al tiempo total de ejecución y computar
el número de veces que dicha operación es
ejecutada.

Como regla, no es dificil identificar la operación
básica de un algoritmo: Usualmente esla
operación que más tiempo consume en el ciclo
más interno del algoritmo.
Por ejemplo, la mayoría de los algoritmos de
ordenamiento trabajan al comparar elementos
(llaves) entre ellos de una lista que está siendo
ordenada; para dichos algoritmos, la operación
básica es la comparación de las llaves.

Por lo tanto, el marco establecido para el análisis
de la complejidad de un algoritmo sugiere quese
mida contando el número de veces que la
operación básica del algoritmo se ejecuta en
entradas de tamaño n.

Ordenes de Crecimiento
El marco de análisis de eficiencia se concentra en
el orden de crecimiento del conteo de
operaciones básicas.
Una diferencia en tiempos de ejecución para
entradas pequeñas no es lo que distingue
algoritmos eficientes de ineficientes. Para valores
grandes de n, elorden de crecimiento de la
función es lo que importa.

Valores de varias funciones importantes para el
análisis de algoritmos.

Eficiencia: Peor Caso, Mejor Caso y Caso Medio
Para entender las nociones de complejidad
(eficiencia) del mejor, peor y caso medio, piensa
en correr un algoritmo sobre todas las
posibles instancias de datos que se le pueden
ingresar.
Para el problema de ordenamiento, elconjunto de
posibles instancias de entrada consiste de todos
los posibles acomodos de n llaves, sobre todos
los posibles valores de n.

Introducción Informal
●

La complejidad del peor caso del algoritmo es la
función definida por el máximo número de pasos
tomados en cualquier instancia de tamaño n.

Introducción Informal
●

La complejidad del mejor caso del algoritmo es
la función definida porel mínimo número de
pasos tomados en cualquier instancia de
tamaño n.

Introducción Informal
●

La complejidad de caso medio del algoritmo es
la función definida por el número promedio de
pasos sobre todas las instancias de tamaño n.

Complejidad del mejor, peor y caso medio

Como se mencionó previamente, el marco de
análisis de eficiencia se concentra en el orden de
crecimiento del conteo de laoperación básica
de un algoritmo como el indicador principal de la
eficiencia del algoritmo.
Para comparar y ordenar dichos ordenes de
crecimiento, se utilizan tres notaciones: Ο (o
grande), Ω (omega grande) y Θ (theta grande).

A partir de este momento, t(n) y g(n) pueden ser
cualquier función no negativa definida sobre los
números naturales. En el contexto que nos
interesa, t(n) será el tiempode ejecución de un
algoritmo (usualmente denotado por el conteo de
su operación básica C(n)), y g(n) será alguna
función simple para comparar con el conteo.
Las notaciónes asintóticas ignoran la diferencia
entre constantes multiplicativas. Las funciones
f(n) = 2n y g(n) = n son idénticas en el análisis
asintótico.

Notación Ο
Una función t (n) se dice que está en Ο(g(n)) ,
denotado con t...