ANALISIS DE ALGORITMOS

52 %
48 %
Information about ANALISIS DE ALGORITMOS
ing

Published on December 11, 2007

Author: evansbv

Source: slideshare.net

Description

ANALISIS DE ALGORITMOS

ANALISIS DE ALGORITMOS UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIA PROFESOR: Ing. Evans Balcazar Veizaga

PROFESOR:

Ing. Evans Balcazar Veizaga

Objetivos El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. A la hora de realizar un análisis teórico de algoritmos es corriente calcular su complejidad en un sentido asintótico, es decir, para una tamaño de entrada suficientemente grande.

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.

A la hora de realizar un análisis teórico de algoritmos es corriente calcular su complejidad en un sentido asintótico, es decir, para una tamaño de entrada suficientemente grande.

Contenido : 3.1 Tiempos de Algoritmos 3.2 Complejidad Algorítmica

3.1 Tiempos de Algoritmos

3.2 Complejidad Algorítmica

Definición del Problema : Se desea comparar 2 algoritmos, A 1 y A 2 respecto a su velocidad, asumiendo que A 1 y A 2 son equivalentes. La velocidad de ejecución es independiente de la plataforma que esta utilizando, por ejemplo: “ Si A 1 se ejecuta en una Pentium VI de 3Ghz y A 2 se ejecuta en una Pentium I de 800Mhz, entonces es muy probable que A 1 se ejecute mucho mas rápido siendo un algoritmo concebido lentamente”

Se desea comparar 2 algoritmos, A 1 y A 2 respecto a su velocidad, asumiendo que A 1 y A 2 son equivalentes.

La velocidad de ejecución es independiente de la plataforma que esta utilizando, por ejemplo:

“ Si A 1 se ejecuta en una Pentium VI de 3Ghz y A 2 se ejecuta en una Pentium I de 800Mhz, entonces es muy probable que A 1 se ejecute mucho mas rápido siendo un algoritmo concebido lentamente”

Tiempos de una Algoritmo : Para hacerlo independiente de la plataforma, se han ideado tiempos enteros a cada sentencia del programa, utilizando una conjunción: Las llamadas a funciones o procedimientos tienen el tiempo que les lleva a ellos ejecutarse. Una asignación simple tarda 1, por ejm: x:=x+1; => 1 y:=2*x-1; => 1 y:=factorial(n); => No es Simple Las comparaciones simples tardan 1, por ejm: if (x=y) then => 1 if (x=3)or (y=5) then => 1 if (factorial(n)==120) then => Compuesta

Para hacerlo independiente de la plataforma, se han ideado tiempos enteros a cada sentencia del programa, utilizando una conjunción:

Las llamadas a funciones o procedimientos tienen el tiempo que les lleva a ellos ejecutarse.

Una asignación simple tarda 1, por ejm:

x:=x+1; => 1

y:=2*x-1; => 1

y:=factorial(n); => No es Simple

Las comparaciones simples tardan 1, por ejm:

if (x=y) then => 1

if (x=3)or (y=5) then => 1

if (factorial(n)==120) then => Compuesta

Tiempos de Algoritmos : Ejm 1: Encontrar el tiempo de ejecución procedure uno(n:integer); begin x:=1; y:=x+1; z:=0; end; Tabla de Conteo Tuno(n)=3 3 Total 1 3 1 2 1 1 Tiempo Línea

Tiempos de Algoritmos : Ejm 2: Encontrar el tiempo de ejecución procedure dos(n:integer); begin x:=3; if(x=3)then t:=x+1; z:=0: end; Tabla de Conteo Tdos(n)=4 1 3 4 Total 1 4 1 2 1 1 Tiempo Línea

Tiempos de Algoritmos : Ejm 3: Encontrar el tiempo de ejecución procedure Tres(n:integer); begin z:=0; if(n mod 2=0)then begin y:=x+1; z:=0; end else z:=z+1: end; Tabla de Conteo Ttres(n)=9 1 1 2 1 1 1 Total 5 4 3 Línea 3 9 1 - - 4 - 3 n mod 2 <> 0 n mod 2 = 0

Tiempos de Algoritmos : For i:=a to b do Begin Cuerpo; End; Ejm 4: Encontrar el tiempo de ejecución procedure cuatro(n:integer); begin z:=3; for i:=5 to n do begin write (i); t:=x+1; end; end; Tabla de Conteo Tcuatro(n)=3n-10 => b-a+2 =>b-a+1 1*(n-4) 3 3n-10 Total 1*(n-4) 4 n-5+2 2 1 1 Tiempo Línea

Tiempos de Algoritmos : Ejm 5: Encontrar el tiempo de ejecución procedure cinco(n:integer); begin for i:=5 to n do begin m:=0; for j:=2 to n-1 do m:=m-1; uno(n); dos(n); end end; Tabla de Conteo Tcinco(n)=2n 2 -2n-23 1* (n-2)*(n-4) 4 (n-1)*(n-4) 3 3*(n-4) 5 2n 2 -2n-23 Total 4*(n-4) 6 1+(n-4) 2 N-5+2 1 Tiempo Línea

Practica 6 : Realizar un programa que Buscar el máximo valor de un arreglo. Realizar el análisis del tiempo de un algoritmo anterior

Realizar un programa que Buscar el máximo valor de un arreglo.

Realizar el análisis del tiempo de un algoritmo anterior

Complejidad Algorítmica : Concepto : Mucho algoritmos, tienen la dificultad de que el tiempo de conteo que ellos presentan es difícil de calcular. Por este motivo se busca una función que sea una cota superior a la función tiempo. Esta función se la consigue usando la O de Lagrange. Definición : Se dice T(n)=O(f(n)) sii Э c,n o >=0 Tal que Vn=>n o T 1 (n) <=c*f(n)

Concepto : Mucho algoritmos, tienen la dificultad de que el tiempo de conteo que ellos presentan es difícil de calcular. Por este motivo se busca una función que sea una cota superior a la función tiempo. Esta función se la consigue usando la O de Lagrange.

Definición :

Se dice T(n)=O(f(n)) sii

Э c,n o >=0 Tal que Vn=>n o T 1 (n) <=c*f(n)

Complejidad Algorítmica : Teorema 1: Si un algoritmo A con tiempo de conteo Ta(n) = O( f(n) ) entonces se dice que A tiene complejidad f(n). Por Ejemplo: T cinco (n)=2n 2 -2n-23=O(n 2 ) Entonces se dice que cinco tiene una complejidad n 2. Teorema 2: Si un algoritmo A con tiempo proporcional a k * f(n) entonces el algoritmo A es proporcional a f(n). Si T A (n)=O(k(f(n))) entonces T A (n)=O(f(n)) (Es decir las constantes no interesan, k>0)

Teorema 1:

Si un algoritmo A con tiempo de conteo Ta(n) = O( f(n) )

entonces se dice que A tiene complejidad f(n).

Por Ejemplo:

T cinco (n)=2n 2 -2n-23=O(n 2 )

Entonces se dice que cinco tiene una complejidad n 2.

Teorema 2:

Si un algoritmo A con tiempo proporcional a k * f(n)

entonces el algoritmo A es proporcional a f(n).

Si T A (n)=O(k(f(n))) entonces T A (n)=O(f(n))

(Es decir las constantes no interesan, k>0)

Complejidad Algorítmica : Demostración : Supongamos que T A (n)=O(k*f(n)) entonces por def. de O, Э c,n o >0 Tal que T A (n)=c*k*f(n) n>=n o Si tomamos c 2 =c*k >0 T A (n)<=c 2 *f(n) T A (n)<=O(f(n)) Corolario: Si T A (n)=k entonces T A (n)=O(1) Por Ejemplo: T uno (n)=3=O(1) T dos (n)=4=O(1) Es decir todo algoritmos con tiempos constante tiene complejidad 1.

Demostración :

Supongamos que T A (n)=O(k*f(n))

entonces por def. de O, Э c,n o >0

Tal que T A (n)=c*k*f(n) n>=n o

Si tomamos c 2 =c*k >0

T A (n)<=c 2 *f(n)

T A (n)<=O(f(n))

Corolario:

Si T A (n)=k entonces T A (n)=O(1)

Por Ejemplo:

T uno (n)=3=O(1)

T dos (n)=4=O(1)

Es decir todo algoritmos con tiempos constante tiene complejidad 1.

Complejidad Algorítmica : Ejm 6: Calcular la Complejidad procedure seis(n:integer); begin for i:=1 to n do begin uno(n); end; end; Tabla de Conteo Tseis(n)=4n+1 Tseis(n)=4n+1=O(4n+1)=O(n) 4n+1 Total 3*(n-1+1) 2 n-1+2 1 Tiempo Línea

Complejidad Algorítmica : Teorema 3: Si T A1 (n) = O( f 1 (n) ) y T A2 (n) = O( f 2 (n) ) entonces se dan las siguientes propiedades: T A1 (n)+T A2 (n)= O( f 1 (n) + f 2 (n) ) T A1 (n)*T A2 (n)= O( f 1 (n) * f 2 (n) ) Teorema 4: Si un algoritmo A tiene 2 sub-algoritmos A 1 y A 2 Supongamos que : T A1 (n) = O( f 1 (n) ) T A2 (n) = O( f 2 (n) ) entonces T A (n) = O( max{ f 1 (n), f 2 (n) ) La herramienta que se presenta a continuación llamada tabla de complejidad esta basada en los tres teoremas anteriores.

Teorema 3:

Si T A1 (n) = O( f 1 (n) ) y T A2 (n) = O( f 2 (n) )

entonces se dan las siguientes propiedades:

T A1 (n)+T A2 (n)= O( f 1 (n) + f 2 (n) )

T A1 (n)*T A2 (n)= O( f 1 (n) * f 2 (n) )

Teorema 4:

Si un algoritmo A tiene 2 sub-algoritmos A 1 y A 2

Supongamos que : T A1 (n) = O( f 1 (n) )

T A2 (n) = O( f 2 (n) )

entonces T A (n) = O( max{ f 1 (n), f 2 (n) )

La herramienta que se presenta a continuación llamada tabla de complejidad esta basada en los tres teoremas anteriores.

Complejidad Algorítmica : Tabla de Complejidad: La siguiente tabla se construye bajo el sustento teórico de los teoremas anteriores. Tabla de Complejidad … … O( max{f 1 (n),… f n (n)}) Total O( f n (n)) n O( f 2 (n)) 2 O( f 1 (n)) 1 Complejidad Línea

Tabla de Complejidad:

La siguiente tabla se construye bajo el sustento teórico de los teoremas anteriores.

Complejidad Algorítmica : ¿Pero cual es la función mayor ? La siguiente tabla se construye bajo el sustento teórico de los teoremas anteriores, por cada línea se calcula su complejidad y la complejidad total es obtenida tomando la función máxima. <=Mayor <=Menor n 1 log n n log n n k (k>=2) a n (a>1)

¿Pero cual es la función mayor ?

La siguiente tabla se construye bajo el sustento teórico de los teoremas anteriores, por cada línea se calcula su complejidad y la complejidad total es obtenida tomando la función máxima.

Complejidad Algorítmica : Ejm 7: Encontrar la complejidad procedure siete(n:integer); begin x:=7; for i:=1 to n do begin k:=k+1; for j:=3 to n do begin k:=k-1; end; end end; Tabla de Complejidad Tsiete(n)=O( n 2 ) (n-1)*n = O( n 2 ) 4 1*n = O( n ) 3 1*(n-2)*n= O( n 2 ) 5 O( n 2 ) Total n-1+2 = O( n ) 2 1 = O( 1 ) 1 Complejidad Línea

Complejidad Algorítmica : Ejm 8: Encontrar la complejidad procedure ocho(v:array;n:integer); begin mayor:=v[1]; for i:=2 to n do begin if(mayor>v[i])then begin Mayor:=v[i]; end; end end; Tabla de Complejidad Tocho(n)=O( n 2 ) 1* O( n ) 4 O( n ) 3 O( n ) Total O( n ) 2 O( 1 ) 1 Complejidad Línea

Complejidad Algorítmica : Teorema 5: T QuickSort (n) = O( n log (n) ) T BusqBinaria (n) = O( n log 2 (n) ) T Hanoi (n) = O( 2 n ) T ShellSort (n) = O( n log (n) ) Teorema 6: Sea Sort(n) un algoritmo de clasificación para un vector V de N elementos, luego: T Sort (n) >= O( n log (n) )

Teorema 5:

T QuickSort (n) = O( n log (n) )

T BusqBinaria (n) = O( n log 2 (n) )

T Hanoi (n) = O( 2 n )

T ShellSort (n) = O( n log (n) )

Teorema 6:

Sea Sort(n) un algoritmo de clasificación para un vector V de N elementos, luego:

T Sort (n) >= O( n log (n) )

Complejidad Algorítmica : Ejm 9: Encontrar la complejidad procedure nueve(n:integer); begin for k:=1 to n do begin for i:=k+1 to n do begin Quicksort(k); end; p:=BusqBinaria(k) end end; Tabla de Complejidad Tnueve(n)= O( n 3 log n ) O( n log 2 n ) 4 O( n 3 log n ) 3 O( n 3 log n ) Total O( n 2 ) 2 O( n ) 1 Complejidad Línea

Practica 7 : Realizar un programa que me permita calcular la suma de la TSD y TSI. Realizar el análisis de complejidad del algoritmo anterior.

Realizar un programa que me permita calcular la suma de la TSD y TSI.

Realizar el análisis de complejidad del algoritmo anterior.

GRACIAS Estructura de Datos

Add a comment

Related presentations

Related pages

Análisis de algoritmos - Wikipedia, la enciclopedia libre

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los ...
Read more

Análisis de Algoritmos: Complejidad

Análisis de Algoritmos: Complejidad José A. Mañas Noviembre, 1997 1. Introducción 2. Tiempo de Ejecución 3. Asintotas 4. Reglas Practicas 5.
Read more

MANUAL ANÁLISIS DE ALGORITMOS

asignatura de “Análisis y Diseño de Algoritmos” del séptimo semestre de la carrera de Ingeniería en Gestión Informática, del Instituto Nacional de
Read more

Análisis de Algoritmos , Complejidad de algoritmos - YouTube

Análisis de Algoritmos , Complejidad de algoritmos (Audio) - Duration: 10:22. ... Analisis de Algoritmos - Ejemplos - 5 - Duration: 10:21.
Read more

Analisi de Algoritmos - YouTube

Video realizado para la asignatura de analisis de algoritmos.
Read more

ALGORITMOS: ANÁLISIS DE ALGORITMOS

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los ...
Read more

SÉPTIMA UNIDAD - ANÁLISIS DE ALGORITMOS | ESTRUCTURA DE ...

En el análisis de algoritmos se considera usualmente el caso peor, si bien a veces conviene analizar igualmente el caso mejor y hacer alguna estimación ...
Read more

01_analisis_algoritmos (1) - Scribd - Read books ...

01_analisis_algoritmos (1) by Pedro López. 4 views. Embed. Download. Description. algoritmos. algoritmos. Categories: Types, Presentations.
Read more

Algoritmo - Wikipedia, la enciclopedia libre

Los algoritmos son el objeto de estudio de la algoritmia. [1] En la vida cotidiana, se emplean algoritmos frecuentemente para resolver problemas.
Read more