Publicado el 19 de Diciembre del 2018
558 visualizaciones desde el 19 de Diciembre del 2018
178,9 KB
21 paginas
Creado hace 16a (18/10/2007)
TEMA 1
ANÁLISIS DE LA EFICIENCIA
1. Complejidad de los algoritmos
2. Medidas asintóticas de la complejidad
3. Ordenes de complejidad
4. Métodos de análisis de la complejidad temporal de los algoritmos
iterativos
Bibliografía:
Fundamentals of Data Structures in C++
E. Horowitz, S. Sahni, D. Mehta
Computer Science Press, 1995
Análisis de la eficiencia
1
1.1 Complejidad de los algoritmos
Legible y
bien documentado
Correcto
programa
ideal
Eficiente
Fácil de mantener
y reutilizar
Un algoritmo será tanto más eficiente cuantos menos recursos consuma: tiem-
po y espacio de memoria necesario para ejecutarlo.
La eficiencia de los algoritmos se cuantifica con las medidas de complejidad:
— Complejidad temporal: tiempo de cómputo de un programa
— Complejidad espacial: memoria que utiliza un programa en su ejecución
En general, es más importante conseguir buenas complejidades temporales
¡¡¡ Seamos generosos con las variables !!!
Análisis de la eficiencia
2
La complejidad de un programa depende de
la máquina y el compilador.
—
— el tamaño de los datos de entrada,
— el valor de los datos de entrada, y
En los estudios teóricos de la complejidad no nos ocupamos de la máquina ni
del compilador.
El “tamaño de los datos” depende del tipo de datos y del algoritmo:
— para un vector, su longitud,
— para un número, su valor o su número de dígitos, …
Para un tamaño de datos dado, hablamos del valor de los datos como pertene-
cientes al caso mejor, al caso peor, o, si tenemos en cuenta todos los valores
posibles y sus probabilidades, al caso promedio. Por ejemplo,
const int N = 10;
int i, j, x;
int v[N];
for ( i = 1; i < N; i++ )
{
x = v[i];
j = i-1;
while ( (j >= 0) && (v[j] > x) )
{
}
}
// ¿qué hace este algoritmo?
v[j+1] = v[j];
j = j-1;
v[j+1] = x;
con tamaño 4: uno = [1,2,5,4], dos = [1,2,3,4] y tres = [4,3,2,1]
— Caso mejor: dos (no se entra nunca en el while)
— Caso peor: tres (se ejecuta (i-1) veces el bucle por cada i)
Análisis de la eficiencia
3
Medida del tiempo de ejecución de un algoritmo
Vamos a medir el tiempo de ejecución del algoritmo de ordenación anterior,
aplicado sobre datos de distinto tamaño
— Convertimos el algoritmo de ordenación en un procedimiento
void ordena ( int v[], int num ) {
int i, j, x;
for ( i = 1; i < num; i++ ) {
x = v[i];
j = i-1;
while ( (j >= 0 ) && (v[j] > x) ) {
v[j+1] = v[j];
j = j-1;
}
v[j+1] = x;
}
}
— Para medir el tiempo utilizamos la función clock( ) que devuelve un valor de
tipo clock_t con el número de ciclos de reloj en ese instante.
const int N = 50;
clock_t t1, t2;
int v[N];
double tiempo;
for ( i = 0; i < N; i++ )
v[i] = rand();
t1 = clock();
ordena(v, N);
t2 = clock();
tiempo = double(t2-t1)/CLOCKS_PER_SEC;
el problema de este método es que la precisión del reloj del sistema suele estar
entorno a los milisegundos, y el tiempo a medir es inferior o de ese orden.
La solución es repetir la ejecución del procedimiento que pretendemos medir
un cierto número de veces hasta que el tiempo medido sea significativo. Como
pretendemos tomar medidas para distintos tamaños de datos, repetiremos
también el proceso para cada valor de N, y utilizaremos un número de repeti-
ciones distinto dependiendo de dicho valor.
Análisis de la eficiencia
4
El programa de toma de tiempos queda entonces
int main( int argc, char* argv[] )
{
const int N = 1000;
const int NumPuntos = 10;
int i, j, k;
int tamanyos[NumPuntos] = { 100, 200, 300, 400, 500, 600,
700, 800, 900, 1000 };
int repeticiones[NumPuntos] = { 5000, 4000, 4000, 3000, 3000, 3000,
2000, 1000, 500, 100 };
double tiempos[NumPuntos];
int u[N], v[N];
clock_t t1, t2;
for ( i = 0; i < N; i++ )
u[i] = rand();
for ( k = 0; k < NumPuntos; k++ ) {
t1 = clock();
for( i = 0; i < repeticiones[k]; i++) {
for ( j = 0; j < tamanyos[k]; j++ )
v[j] = u[j];
ordena(v, tamanyos[k]);
}
t2 = clock();
tiempos[k] = (double(t2-t1)/CLOCKS_PER_SEC) / repeticiones[k];
}
for ( k = 0; k < NumPuntos; k++ )
cout << "N = " << tamanyos[k] << "; t = " << tiempos[k] << endl;
char c;
cin >> c;
return 0;
}
Análisis de la eficiencia
5
Los resultados de la ejecución anterior (en un Pentium III a 650MHz, compi-
lado en C++ Builder 5)
N
100
200
300
400
500
600
700
800
900
1000
t
0,000067
0,000220
0,000544
0,000947
0,001439
0,002063
0,002842
0,003775
0,004662
0,005840
Ordenación
0
200
400
600
800
1000
N
t
0,007
0,006
0,005
0,004
0,003
0,002
0,001
0,000
Análisis de la eficiencia
6
Definición de complejidad temporal
El tiempo que tarda un algoritmo A en procesar una entrada concreta xr lo no-
taremos como
tA(xr )
TA(n)
como la función
remos
TMA(n)
como la función
Definimos la complejidad de un algoritmo A en el caso peor, que notaremos
TA(n) =def max{ tA(xr ) | xr de tamaño n }
Definimos la complejidad de un algoritmo A en el caso promedio, que nota-
TMA(n)=def ∑
de xr
tamaño
n
p(xr ) ⋅ tA(xr )
siendo p(xr ) la función de probabilidad −p(xr ) ∈ [0,1]− de que la entrada sea el
dato xr .
La complejidad en el caso promedio supone el conocimiento de la distribución
de probabilidades de los datos.
La complejidad en el caso peor proporciona una medida pesimista, pero fiable.
Dado que realizamos un estudio teórico, ignorando los detalles de la máquina
y el compilador, y teniendo en cuenta que las diferencias en eficiencia se hacen
significativas para tamaños grandes de los datos, no pretendemos obtener la
forma exacta de la función de complejidad sino que nos limitaremos a estudiar
su comportamiento asintótico.
Análisis de la eficiencia
7
1.2 Medidas asintóticas de la complejidad
Una medida asintótica es un conjunto de funciones que muestran un comporta-
miento similar cuando los argumentos toman valores muy grandes.
Las medidas asintóticas se definen en términos de una función de referencia f.
medidas asintóticas, f, presentan el perfil
Tanto las funciones de complejidad, T, como las funciones de referencia de las
T, f : ℵ → ℜ+
donde ℵ es el dominio del tamaño de los datos y ℜ+ el valor del coste del al-
goritmo.
Definimos la medida asintótica de cota superior f, que notaremos
O( f )
como el conjunto de funciones
{ T | existen c ∈ ℜ+, n0 ∈ ℵ tales que,
para todo n ≥ n0, T(n) ≤ c ⋅ f(n) }
Si T ∈ O( f ) decimos que “T(n) es del orden de f(n)” y que
“f es asintóticamente una cota superior del crecimiento de T”.
Definimos la medida asintótica de cota inferior f, que notaremos
Ω( f )
como el conjunto de funciones
{ T | existen c ∈ℜ+, n0 ∈ ℵ tales que,
para todo n ≥ n0, T(n) ≥ c ⋅ f(n) }
Si T ∈ Ω( f ) podemos decir que “f es asintóticamente una cota inferior del
crecimiento de T”.
Definimos la medida asintótica exacta f, que notaremos
Θ( f )
como el conjunto de funciones
{ T | existen c1, c2 ∈ ℜ+, n0 ∈ ℵ, tales que,
Si T ∈ Θ( f ) decimos que “T(n) es del orden exacto de f(n)”.
para todo n ≥ n0, c1 ⋅ f(n) ≤ T(n) ≤ c2 ⋅ f(n) }
Análisis de la eficiencia
8
Ejemplos
— f ∈ O( f )
(n+1)2 ∈ O(n2), con c=4, n0=1
—
— 3n3+2n2 ∈ O(n3), con c=5, n0=0
— P(n) ∈ O(nk), para todo polinomio P de grado k
— 3n ∉ O(2n). Si lo fuese existirían c ∈ ℜ+, n0 ∈ ℵ tales que
∀ n : n ≥ n0 : 3n ≤ c ⋅ 2n
⇒ ∀ n ≥ n0 : (3/2)n ≤ c
⇔
falso
pues limn→∞(3/2)n = ∞
(n+1)2 ∈ Ω(n2) con c = 1 y n0=1
— f ∈ Ω( f )
— n ∈ Ω(2n) con c = ½, n0=0
—
— P(n) ∈ Ω(nk) para todo polinomio P de grado k
— f ∈ Θ( f )
— 2n ∈ Θ(n) con c1=1, c2=2 y n0=0
—
— P(n) ∈ Θ(nk) para todo polinomio P de grado k
Estas afirmaciones se pueden demostrar por inducción sobre n, una vez fijadas
las constantes c −c1 , c2− y n0.
(n+1)2 ∈ Θ(n2) con c1=1, c2 = 4, n0=1
Se puede demostrar que
Θ( f ) = O( f ) ∩ Ω( f )
o lo que es igual
T ∈ Θ( f ) ⇔ T ∈ O( f ) ∧ T ∈ Ω( f )
Análisis de la eficiencia
9
1.3 Ordenes de complejidad
Nos referiremos a las medidas asintóticas aplicadas a funciones concretas co-
mo órdenes.
Algunos órdenes tienen nombres particulares:
→ orden constante O(n2) → orden cuadrático
O(1)
O(log n) → orden logarítmico O(n3) → orden cúbico
O(n)
O(nk) → orden polinómico
O(n log n) → orden cuasi-lineal O(2n) → orden exponencial
→ orden lineal
Es posible demostrar que se cumplen las siguientes relaciones de inclusión en-
tre los órdenes de complejidad, que permiten definir una jerarquía de órdenes de
complejidad (a saberse):
O(1) ⊂ O(log n) ⊂ O( n ) ⊂ O(n) ⊂ O(n log n) ⊂
O(n2) ⊂ O(n3) ⊂ ... ⊂ O(nk) ⊂ ...
O(2n) ⊂ O(n!)
2n
n3
n2
n log n
n
log n
100
0
20
40
60
80
1,0E+10
1,0E+08
1,0E+06
1,0E+04
1,0E+02
1,0E+00
Análisis de la eficiencia
10
Debemos recordar que los órdenes de complejidad son medidas asintóticas.
Para datos pequeños, y si las constantes multiplicativas son distintas, nos po-
demos encontrar situaciones como ésta
400.000
300.000
200.000
100.000
0
n2
10.000 log n
0
200
400
600
Para determinar con exa
Comentarios de: Tema 1 - Análisis de la eficiencia (0)
No hay comentarios