eficiencia de algoritmos - vanessa ramirez

ACTIVIDAD 4

ALUMNA:Vanessa Ramírez Corral 1103150016

PROFESOR:Iván González Peyro

MATERIA:Técnicas de Programación

Software 2° AAula 12, UD-2

Enero – Abril 2012

La eficiencia de un programa tiene dos ingredientesfundamentales: espacio y tiempo.

La eficiencia en espacio es una medida de la cantidadde memoria requerida por un programa.

La eficiencia en tiempo se mide en términos de lacantidad de tiempo de ejecución del programa. Ambasdependen del tipo de computador y compilador

Divide y vencerás

Pilas

FIFO

Recursivo

Ramificación

Poda

Precisión es la razón del número de documentos relevantes entre elnúmero total de documentos arrojados por la búsqueda.

Recuperación es la razón de documentos relevantes obtenidos parauna consulta dada entre el total de documentos relevantes en labase de datos; aquí, con excepción de colecciones de pruebarelativamente pequeñas, el denominador es generalmentedesconocido y debe ser estimado mediante muestreo o algún otrométodo.

El análisis A Priori (o teórico)

En el análisis A Posteriori(experimental o empírica)

En lugar de medir el tiempo de ejecución enmicrosegundos o algo por el estilo, nospreocuparemos del número de veces que seejecuta una operación primitiva.

Para estimar la eficiencia de este algoritmo,podemos preguntarnos, "si el argumento es unafrase de N números, ¿cuántas multiplicacionesrealizaremos?"

La respuesta es que hacemos una multiplicaciónpor cada número en el argumento, por lo quehacemos N multiplicaciones. La cantidad de tiempoque se necesitaría para el doble de números seríael doble.

En general, el análisis se realizará sobre ejemplos expresados según el esquema básico de un algoritmo iterativo:

Inicializar; mientras B hacer

Restablecer; Avanzar;

Fmientras

Se ha de tener en cuenta que cada uno de los bloques básicos: (Inicializar, Restablecer, Avanzar, incluso el cálculo de la expresión lógica B) pueden a su vez estar formados por una combinación de cada una de las estructuras fundamentales de un lenguaje imperativo:SECUENCIA: Composición secuencial de instrucciones: S1, S2, ..., SnALTERNATIVA: Instrucciones condicionales del tipo: si B entonces S1 si no S2 fsi, o del tipo más general: caso B1 ® S1 ð caso B2® S2....... caso Bn®Sn fcasoITERACION: Iteración, en sus varias formas: mientras B hacer S fmientras,repetir S hasta B, para i desde E1 hastaE2 hacer S fpara, ...Cualquiera de estas formas es transformable a una expresión del primer tipo (bucle "mientras")

PROCEDURE Factorial (n : CARDINAL) : CARDINAL

BEGIN

VAR Resultado, i: CARDINAL;

Resultado: =1;

FOR i: =1 TO n DO

Resultado: = Resultado*i;

END ;

RETURN Resultado

END Factorial;

Dos implementaciones de un mismo algoritmono diferirán más que en una constantemultiplicativa.

Estrategia para la ordenación:

1.- Considerar el vector dividido en dos zonas:

- elementos que ya están ordenados

- elementos por reubicar.

2.- Se utiliza una variable “i” para marcar el límiteentre ambas zonas.

Peor Caso:

Indica el mayor tiempo obtenido, teniendo en consideración todas las entradas posibles.

En el peor escenario posible (nos permite acotar el tiempo de ejecución).

Mejor Caso:

Indica el menor tiempo obtenido, teniendo en consideración todas las entradas posibles.

En condiciones óptimas (no se usa por ser demasiado optimista).

Media:

Indica el tiempo medio obtenido, considerando todas las entradas posibles.

Caso difícil de caracterizar en la práctica.

Asume una distribución de probabilidad sobre las posibles entradas.

Como no se puede analizar el comportamiento sobre todas las entradas posibles, va aexistir para cada problema particular un análisis en él

Permite medir la dificultad inherente de un problema y evaluar la eficienciade un algoritmo.

El análisis de algoritmos es el proceso que empleamos para determinar lacantidad de recursos (tiempo, espacio, etc.), necesarios para la ejecución deun algoritmo en particular. Siendo el tiempo de ejecución una función deltamaño de entrada, puede ser lineal, cuadrática, cúbica o logarítmica. Elvalor exacto de esta función dependerá de más factores, tales como lavelocidad de la máquina, la calidad del compilador, y en alguno casos lacalidad del programa. Lo que nosotros vamos a tratar de medir es el índicede crecimiento de éstas funciones.

De las funciones que mencionamos, la lineal representa el algoritmo máseficiente. Por esta razón trataremos que nuestros algoritmos según sea elcaso se comporten como una función lineal. Incluso los trucos deprogramación más inteligentes no pueden hacer rápido un algoritmoineficiente.

Por tanto, antes de perder el tiempo intentando optimizar un código,debemos tratar optimizar el algoritmo.

Esta función se puede medir físicamente(ejecutando el programa, reloj en mano) ocalcularse sobre el código contandoinstrucciones a ejecutar y multiplicando porel tiempo requerido por cada instrucción.

Para medir el tiempo de ejecución de un algoritmo existen varios métodos.

Benchmarking

La técnica de benchmark considera una colección de entradas típicas representativas deuna carga de trabajo para un programa.

Profiling

Consiste en asociar a cada instrucción de un programa un número que representa lafracción del tiempo total tomada para ejecutar esa instrucción particular. Una de lastécnicas más conocidas (e informal) es la Regla 90-10, que afirma que el 90% deltiempo de ejecución se invierte en el 10% del código.

Análisis

Consiste en agrupar las entradas de acuerdo a su tamaño, y estimar el tiempo deejecución del programa en entradas de ese tamaño, T(n). Esta es la técnica que seestudiará en el curso. De este modo, el tiempo de ejecución puede ser definido comouna función de la entrada. Denotaremos T(n) como el tiempo de ejecución de unalgoritmo para una entrada de tamaño n.

La complejidad (o costo) de un algoritmo es unamedida de la cantidad de recursos (tiempo,memoria) que el algoritmo necesita.

La complejidad de un algoritmo se expresa enfunción del tamaño (o talla) del problema.

TALLA DE UN PROBLEMA:

Es cualquier parámetro en función del cual se

pueda expresar la complejidad del problema:

Nº de datos de entrada

Nº de datos de salida

Valor de las variables numéricas

Una función de los anteriores

Suele guardar relación con el volumen de los datos

a tratar, y por ello se le suele llamar “tamaño” del

problema.

Si compramos una computadora diez veces másrápida, ¿en qué tiempo podremos ahora ejecutar unalgoritmo?

La respuesta depende del tamaño de la entrada de datos,así como de la razón de crecimiento del algoritmo.

Si la razón de crecimiento es lineal es decir, T(n)=cn)entonces por ejemplo, 100.000 números seránprocesados en la nueva máquina en el mismo tiempo que10.000 números en la antigua computadora.

Clasifica los algoritmos en buenos o malos.

Clasifica los problemas de acuerdo a lacomplejidad inherente de resolverlos.

Complejidad Temporal: tiempo requerido porun algoritmo para encontrar la solución.

Complejidad Espacial: almacenamientorequerido por un algoritmo para encontrar lasolución.

• O(1) orden constante• O(log n) orden logarítmico• O(n) orden lineal• O(n2) orden cuadrático• O(na) orden polinomial (a> 2)• O(an) orden exponencial (a> 2)• O(n!) orden factorial

Si un programa se va a ejecutar muy pocas veces, los costes de codificación ydepuración son los que más importan, relegando la complejidad a un papelsecundario.

Si a un programa se le prevé larga vida, hay que pensar que le tocará mantenerloa otra persona y, por tanto, conviene tener en cuenta su legibilidad, incluso acosta de la complejidad de los algoritmos empleados.

Si podemos garantizar que un programa sólo va a trabajar sobre datos pequeños(valores bajos de N), el orden de complejidad del algoritmo que usemos sueleser irrelevante, pudiendo llegar a ser incluso contraproducente.

El interés principal del análisis de algoritmosradica en saber cómo crece el tiempo deejecución, cuando el tamaño de la entradacrece. Esto es la eficiencia asintótica delalgoritmo.

La notación asintótica se describe por mediode una función cuyo dominio es los númerosnaturales (Ν) estimado a partir de tiempo deejecución o de espacio de memoria dealgoritmos en base a la longitud de la entrada.

La notación O se utiliza para comparar funciones.Resulta particularmente útil cuando se quiereanalizar la complejidad de un algoritmo, en otraspalabras, la cantidad de tiempo que le toma a uncomputador ejecutar un programa.

Decimos que una función T(n) es O(f(n))si existen constantes n0 y ctales que T(n) ≤ cf(n) para todo n ≥ n0:

T(n) es O(f(n)) ⇔∃c∈R, ∃n0∈N, tal que ∀n>n0∈N, T(n) ≤ cf(n)

Para o la desigualdad se mantiene para todas las constantes positivas, mientras que para O la desigualdad se mantiene sólo para algunas constantes positivas

Ω Es el reverso de O.

f (x) =Ω(g(x)) →←g(x) =O(f (x))

Ω Grande dice que asintóticamente f (x) domina a g(x).

Θ Grande dice que ambas funciones se dominan mutuamente, en otras palabras, son asintóticamente equivalentes.

f (x) =Θ(g(x))→←

f (x) =O(g(x))∧f (x) =Ω(g(x))

f =Θ (g): “f es de orden g”

Los enteros positivos:

•f ∈ O (g(x)) ↔ f ≤ g (se dice que f es asintóticamente menor o igual que g)

•f ∈ o (g(x)) ↔ f <g

•f ∈ Θ (g(x)) ↔ f =g

•f ∈ Ω (g(x)) ↔ f ≥g

• f ∈ ω (g(x)) ↔ f >g