PDF de programación - Tema 1 - Análisis de la eficiencia

Imágen de pdf Tema 1 - Análisis de la eficiencia

Tema 1 - Análisis de la eficienciagráfica de visualizaciones

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
  • Links de descarga
http://lwp-l.com/pdf14609

Comentarios de: Tema 1 - Análisis de la eficiencia (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad