Análisis de la eficiencia de los algoritmos PDF 2024-25

1.- Análisis de la eficiencia de los algoritmos Ignacio Fábregas - [email protected] Fundamentos de Algoritmia (FAL) Grupos E y F Grado en Ingeniería del Software...

1.- Análisis de la eficiencia de los algoritmos Ignacio Fábregas - [email protected] Fundamentos de Algoritmia (FAL) Grupos E y F Grado en Ingeniería del Software Fac. Informática (Transparencias basadas en originales de Clara Segura) Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 1 / 48 Contenidos 1 Introducción 2 Eficiencia 3 Medidas asintóticas de la eficiencia 4 Análisis de eficiencia en algoritmos iterativos 5 Resumen Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 2 / 48  Introducción Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 3 / 48 ¿Por qué tenemos que tener en cuenta la eficiencia? ¿No basta con programar? Buscamos resolver los problemas eficientemente, es decir, consumiendo el mínimo de recursos. En programación nuestros recursos son el tiempo (lo que tarda el programa en producir el resultado) y el espacio (la memoria que usamos). Una mala gestión del algoritmo puede hacer que nuestro programa sea innecesariamente ineficiente. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 4 / 48 ¿Qué es un número grande? Pandemia Durante los primeros meses de la pandemia de covid en 2020, el número de infectados se duplicaba cada 3 días. Si empezamos con un infectado, ¿cuánto tiempo tardará en haber un millón de infectados? ¿Un año? ¿6 meses? ¿1 semana? En 60 días habrá 1,048,576 infectados. 30 días después más de 1,000,000,000. En un año, más de 1,000,000,000,000,000,000,000,000,000,000,000,000. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 5 / 48 ¿Qué es un número grande? Lirios de agua Hay un lirio en un pantano. Cada día dobla su tamaño y en 30 días ocupará el pantano completo matando al resto de plantas y animales en él. Como cada día vemos que crece muy poco decidimos tomar acciones contra la planta cuando ocupe la mitad del pantano... Eso ocurre el día 29. Sólo queda un día para mover el resto de plantas. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 6 / 48 ¿Qué es un número grande? Arroz y ajedrez Cuenta la leyenda que el visir Sissa ben Dahir inventó el ajedrez para el rey Shirham de la India. Ante tan magnífico invento, el rey le dijo a Sissa que podía elegir su propia recompensa. Sissa dió dos opciones al rey: o bien con la cantidad de arroz equivalente a dos años o bien de la siguiente manera: un grano de arroz en la primera casilla del tablero de ajedrez, más dos granos en la segunda, etc. Duplicando el número de granos en cada casilla, hasta llegar a la última. El rey eligió la segunda opción, ¿hizo bien? Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 7 / 48 ¿Qué es un número grande? Arroz y ajedrez En la primera fila hay: 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 = 255 ¡En la primera casilla de la segunda fila habrá 28 = 256! P23 i En las tres primeras filas hay: i=0 2 = 224 − 1 = 16, 777, 216... Son unos 600kg de arroz. En total hay X 63 2i = 264 − 1 = 18, 446, 744, 073, 709, 551, 615 i=0... aproximadamente 10 siglos de cosechas.... Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 8 / 48 ¿Qué es un número grande? Crecimiento exponencial Hemos visto 3 ejemplos de crecimiento exponencial. En todos ellos ocurre lo siguiente: inicialmente crecen lentamente. hay un punto en el que el crecimiento es desmesurado. Eficiencia A la hora de programar es importante ser consciente del coste, los recursos que consume, del programa. Si el número de operaciones que debe hacer un programa es exponencial, seguramente tardará mucho tiempo en calcular el resultado. Normalmente nos centraremos en coste en tiempo. Si conocemos el coste de los algoritmos y somos capaces de compararlo con otros, podemos elegir el algoritmo más eficiente para cada problema. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 9 / 48 ¿Y no podemos esperar? Los procesadores más potentes a nivel usuario computan alrededor de 1 teraFLOPS (≈ 1012 operaciones por segundo). Consolas/GPUs actuales alrededor de 10 teraFLOPS. En 2022 se construyó un ordenador con capacidad de 1 exaFLOPS (≈ 1018 operaciones por segundo). Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 10 / 48  Eficiencia Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 11 / 48 Cálculo de la eficiencia (cálculo explícito) Debemos determinar cómo medir el coste de un algoritmo, de forma que sea posible compararlo con otros que resuelven el mismo problema. Una primera solución (poco práctica) es contar las instrucciones y multiplicar por su coste. Por ejemplo, tenemos estos tiempos por instrucción: ta : tiempo de una asignación tc : tiempo de una comparación ti : tiempo de un incremento/decremento tv : tiempo de un acceso a vector Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 12 / 48 Ejemplo del cálculo de eficiencia (cálculo explícito) Consideremos la siguiente función para buscar si un valor x aparece en un vector v. 1 bool search ( const vector & v, const T & x) { 2 int i = 0; 3 while (i < v.size () && v[i] != x) { 4 ++i; 5 } 6 return i < v.size (); 7 } Obviamente, si el valor aparece en la primera posición del vector, el programa consumirá muy poco tiempo. En cambio, si no aparece se consumirá más tiempo. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 13 / 48 Ejemplo del cálculo de eficiencia (cálculo explícito) Si calculamos la función de coste para el algoritmo anterior tendremos 2 costes diferentes (suponemos que v.size() no consume nada): 1 bool search ( const vector & v, const T & x) { 2 int i = 0; 3 while (i < v.size () && v[i] != x) { 4 ++i; 5 } 6 return i < v.size (); 7 } Caso mejor: el elemento está en la primera posición Tmin (n) = ta + 3tc + tv + tc = ta + 4tc + tv |{z} | {z } |{z} L2 L3 L6 El tiempo es independiente del tamaño del número de elementos a explorar (el tamaño del vector). El coste es, por lo tanto, constante y se denota como O(1). Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 14 / 48 Ejemplo del cálculo de eficiencia (cálculo explícito) 1 bool search (vector const & v, T const & x) { 2 int i = 0; 3 while (i < v.size () && v[i] != x) { 4 ++i; 5 } 6 return i < v.size (); 7 } Caso peor: el elemento no aparece en el vector Tmax (n) = t a + n(3tc + tv ) + nti + tc |{z} | {z } |{z} |{z} L2 L3 L4 L6 = n(3tc + tv + ti ) + tc + ta El coste depende linealmente del número n de elementos a explorar: si tenemos el doble de elementos, tardemos aproximadamente el doble de tiempo. El coste es, por lo tanto, lineal y se denota como O(n). Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 15 / 48 Factores En los costes anteriores podemos ver 3 elementos importantes: El tamaño de los datos de entrada: longitud de un vector, valor de un entero, número de cifras de un número… El contenido de los datos de entrada. Aun considerando vectores de un mismo tamaño n, el coste varía entre Tmin (n) y Tmax (n) dependiendo del contenido concreto del vector. La tecnología, es decir, el código concreto generado por el compilador y la máquina sobre la que se ejecutará el programa. Esto repercute en los valores concretos de ta , tc , ti y tv. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 16 / 48 Factores Buscamos comparar algoritmos y para eso lo sensato es olvidarnos del valor de los datos de entrada. Hay dos técnicas clásicas: 1. Medir el caso peor: la ejecución que tarde más tiempo de todos los ejemplares de un tamaño fijo n. Esto es lo que hacíamos en el segundo ejemplo. Formalmente, si el tiempo que tarda un algoritmo A en procesar una entrada concreta x lo denotamos por tA (x), definimos la complejidad de A en el caso peor como TA (n) = max{tA (x) | x es de tamaño n } 2. Medir el caso promedio: la media de todos los casos de tamaño n Definimos la complejidad de A en el caso promedio como X TMA (n) = p(x)tA (x) x es de tamaño n donde p(x) ∈ [0 · · · 1] es la probabilidad de que la entrada sea x. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 17 / 48 Caso peor Nosotros nos centraremos en el caso peor por dos razones: Establece una cota superior fiable para todos los casos del mismo tamaño. Es más fácil de calcular que el caso promedio, donde necesitamos considerar todas las ejecuciones. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 18 / 48  Medidas asintóticas de la eficiencia Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 19 / 48 Medidas asintóticas de la eficiencia No nos interesa el coste preciso usando una tecnología concreta, sino conocer cómo crece el tiempo usado por el algoritmo conforme aumenta el tamaño de la entrada. Para ello usaremos medidas asintóticas: 1. La eficiencia (coste) es una función que únicamente depende del tamaño de la entrada, p.ej. si el tamaño lo denotamos por n, f(n) = n3. Para cada algoritmo hay que definir qué entendemos por tamaño de la entrada. 2. Las constantes multiplicativas o aditivas no afectan. P. ej. f(n) = n3 y g(n) = 5n3 + 48 son equivalentes. 3. La comparación entre funciones de coste se hace para valores suficientemente grandes de n, así que los costes para tamaños pequeños se consideran irrelevantes. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 20 / 48 Medidas asintóticas de la eficiencia Definición formal Sea una función f : N → R+. El conjunto de las funciones del orden de f(n), llamado O(f(n)), se define como: O(f(n)) = {g : N → R+ | ∃c ∈ R+ , n0 ∈ N. ∀n ≥ n0. g(n) ≤ cf(n)} En otras palabras, es el conjunto de todas las funciones g(n) tales que a partir de un n suficientemente grande son inferiores a f(n). Si g ∈ O(f(n)) diremos que g es del orden de f(n) o que g está en O(f(n)). Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 21 / 48 Intuición f(n) ∈ O(g(n)) indica que la función g es una cota superior de la f. En este caso existe c ∈ R+ y n0 = 5 ∈ N tales que f(n) ≤ cg(n) para todo n ≥ n0 Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 22 / 48 Ejemplos f(n) = 5 f(n) ∈ O(1) [∀n ∈ N, c = 5] f(n) ∈ O(n) [n0 ≥ 5, c = 1] f(n) ∈ O(n2 ) [n0 ≥ 3, c = 1] f(n) ∈ O(5n ) [n0 ≥ 1, c = 1] g(n) = 10n + 5 g(n) ̸∈ O(1) g(n) ∈ O(n) [n0 ≥ 1, c = 20] g(n) ∈ O(n2 ) [n0 ≥ 11, c = 1] g(n) ∈ O(5n ) [n0 ≥ 2, c = 1] Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 23 / 48 Orden de Cota superior Una función tiene varias cotas superiores. Estamos interesados en aquella cota superior más ajustada. Es decir, la menor de las cota superiores. f(n) = 5 ∈ O(1), g(n) = 10n + 5 ∈ O(n). Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 24 / 48 Cota inferior y orden exacto Además de O(f(n)), en el análisis de eficiencia se pueden utilizar otras medidas asintóticas. Análogamente podemos considerar acotar inferiormente a una función. Esto no cambia que el cálculo se haga en el caso peor, sólo que la acotación es por debajo. Cota inferior Ω(f(n)) es el conjunto de funciones para las cuales f(n) es una cota inferior para valores suficientemente grandes de n: Ω(f(n)) = {g : N → R+ | ∃c ∈ R+ , n0 ∈ N. ∀n ≥ n0. g(n) ≥ cf(n)} Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 25 / 48 Cota inferior y orden exacto Orden exacto Si una función f(n) ∈ O(g(n)) y además f(n) ∈ Ω(g(n)), diremos que f(n) está en el orden exacto de g(n): f(n) ∈ Θ(g(n)). Siempre que sea posible su obtención, el orden exacto del coste de un algoritmo es preferible puesto que es más informativo que únicamente una cota inferior o superior. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 26 / 48  Ejemplo (no siempre existe el orden exacto) Consideremos la siguiente función: 1 int fact_par (int n) { 2 int ret = 1; 3 if (n % 2 == 0) { // ' n ' es p a r 4 for (int i = 2; i 1. Si f ∈ O(g) y g ∈ O(h), entonces f ∈ O(h) (transitividad). Regla de la suma: O(f + g) = O(máx(f, g)). Regla del producto: Si g1 ∈ O(f1 ) y g2 ∈ O(f2 ), entonces g1 · g2 ∈ O(f1 · f2 ). Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 30 / 48 Órdenes de complejidad A cada familia O(f(n)) se le denomina clase de complejidad u orden de complejidad. Como hemos visto las constantes multiplicativas o aditivas no afectan, por lo que se elige como representante del orden O(f(n)) a la función más sencilla posible: O(1): constante O(log n): logarítmico O(n): lineal O(n.log n): cuasi-lineal O(n2 ): cuadrático O(nk ): polinomial O(2n ): exponencial O(n!): factorial Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 31 / 48 Teorema del límite Teorema del límite (para O()) f(n) lı́mn→∞ g(n) = m ∈ R+ ⇒ f ∈ O(g) y g ∈ O(f) ⇔ O(f) = O(g) f(n) lı́mn→∞ g(n) =0 ⇒ f ∈ O(g) y g ̸∈ O(f) ⇔ O(f) ⊂ O(g) f(n) lı́mn→∞ g(n) = +∞ ⇒ f ̸∈ O(g) y g ∈ O(f) ⇔ O(f) ⊃ O(g) El teorema del límite se usa para comparar órdenes de complejidad. En los apuntes tienes versiones para Ω y Θ. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 32 / 48 Jerarquía de órdenes de complejidad Los distintos órdenes de complejidad se pueden ordenar por inclusión: O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n.log n) ⊂ O(n2 ) ⊂ O(nk )... ⊂ O(2n ) ⊂ O(3n )... ⊂ O(n!) | {z } | {z } razonables en la práctica intratables | {z } tratables Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 33 / 48 Orden de complejidad de un algoritmo En el siguiente apartado veremos cómo calcular directamente el orden de complejidad de la función de coste de algoritmos iterativos. Como decíamos antes, nos centraremos en el análisis para el caso peor. Diremos que un algoritmo está en O(f(n)) si su función de coste T(n) ∈ O(f(n)). Es decir, para valores suficientemente grandes de su parámetro de entrada n el tiempo consumido por el algoritmo está acotado superiormente por f(n). De manera menos formal usaremos el nombre del orden de complejidad: algoritmo constante, algoritmo lineal, algoritmo cuadrático, … Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 34 / 48  Análisis de eficiencia en algoritmos iterativos Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 35 / 48 Análisis de eficiencia en algoritmos iterativos Como decíamos antes, en la práctica no se hace un cálculo exacto del tiempo por cada instrucción (ta , tc , ti …) Como estamos interesados únicamente en el orden O(f(n)) (o el orden exacto Θ), podemos simplificar el proceso. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 36 / 48 Reglas para el cálculo de la eficiencia 1. Las instrucciones básicas (asignación, entrada/salida, acceso a vectores, operaciones aritméticas, etc.) tendrán un coste en O(1). ¡Ojo! Si la instrucción requiere la evaluación de expresiones complejas (p.ej. una llamada a función) el coste estará en el máximo orden de dichas evaluaciones. Ejemplos: x = 4; ∈ O(1) x > 4; ∈ O(1) x+1 > 4; ∈ O(1) 2. Las llamadas a función tienen un coste del orden de la función aplicado a los argumentos concretos. Ejemplos: fact_par(x); ∈ O(x) fact_par(6); ∈ O(1) search(v, 6); ∈ O(n), siendo n la longitud del vector v Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 37 / 48 Reglas para el cálculo de la eficiencia 3. Una secuencia de instrucciones S1 ; S2 tiene coste en O(max(f1 (n), f2 (n))), donde el coste de S1 está en O(f1 (n)) y el coste de S2 está en O(f2 (n)) Ejemplos: x = 4; x > 4; ∈ O(1) x > 4; a = fact_par(x); ∈ O(x) fact_par(n); fact_par(m); ∈ O(max(n, m)) = O(n + m) Apunte O(max(f1 (n), f2 (n))) = O(f1 (n) + f2 (n)), así que podéis usar max o + para indicar los costes que no se puedan simplificar Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 38 / 48 Reglas para el cálculo de la eficiencia 4. Una instrucción condicional if (B) {S1 } else {S2 } tiene un coste en O(max(fB (n), f1 (n), f2 (n))), donde el coste de B está en O(fB (n)), el de S1 en O(f1 (n)) y el de S2 en O(f2 (n)). Ejemplos: if (x > 4) {a = 5;} else {a = 0;} ∈ O(1) if (x > 4) {a = fact_par(x);} else {a = 0;} ∈ O(x) if (fact_par(x) > 56) {b = true;} ∈ O(x) Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 39 / 48 Reglas para el cálculo de la eficiencia 5. Consideremos un bucle while (B) {S} donde el coste de B; S está en O(fB;S (n)) y el número de iteraciones del bucle es iter(n). El coste del bucle será el sumatorio del coste de cada iteración para cada valor desde 1 hasta iter(n). Ejemplo: int i = 0; while (i < n) { a = a + fact_par (i); i++; } Una iteración (i < n; a = a + fact_par(i); i++;) ∈ O(i) Número de iteraciones: n, desde i = 0 hasta i = n − 1 Coste de todas las iteraciones: X n−1 (n − 1)n i= ∈ O(n2 ) i=0 2 Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 40 / 48 Reglas para el cálculo de la eficiencia El caso de bucles for es igual considerando que for(; ; ) { S } es equivalente a ; while () {S;}. Si en en un bucle el coste de cada iteración es constante, resolver el sumatorio se simplifica. Ejemplo: int i = 0; while (i < n) { a = a + i; i++; } Una iteración: (i < n; a = a + i; i++;) ∈ O(1) Número de iteraciones: n, desde i = 0 hasta i = n − 1 Coste de todas las iteraciones: X n−1 1 = n ∈ O(n) i=0 Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 41 / 48 Propiedades de sumatorios1 “Constantes fuera”: X n X n k · si = k · si i=a i=a Serie aritmética: suma_extremos num_elementos z }| { z }| { X n (a + n) (n − a + 1) i= i=a 2 Serie geométrica: X n 1 − kn+1 ki = i=0 1−k 1 son sólo unos pocos ejemplos, hay muchas más. Ignacio Fábregas - [email protected] 1.- Análisis de la eficiencia de los algoritmos Curso 2024-25 42 / 48 Ejemplo: Producto de matrices cuadradas 1 typedef vector Matriz ; 2 void producto ( const Matriz & A, const Matriz & B, Matriz & C, int n){ 3 for (int i=0; i c3n  c · 2n (para 2 ) ( 3todo n n0. Esto implicaría que ( 32 )n  c para todo para que ( 3 )n > c, es decir )n no se puede acotar superiormente. n n0.2Pero esto es falso porque 2 dado un c cualquiera, bastaría tomar n > log1,5 c ? ? O(f La notación (n)) para que (O(f 3 n 2) > c, esnos (n)) decir ) nocota 3 n da( 2una se puede acotar superior tiempo de ejecución t(n) al superiormente. t(n) de un f (n) ? algoritmo. Normalmente La notación estaremos O(f (n)) nos interesados da una cota entiempo superior al la menor funciónt(n) de ejecución de tal f (n) un que t(n) 2t(n) O(f (n)) 2 O(f (n)). algoritmo. Una forma estaremos Normalmente de realizarinteresados un análisisenmás completo la menor es encontrar función además f (n) tal que la mayor función t(n) 2 O(f g(n) que sea g(n)forma (n)). Una una cota de realizar inferiormás un análisis de completo t(n). Para t(n) ello introducimos es encontrar además la siguiente medida. la mayor función g(n) que sea una cota inferior de t(n). Para ello introducimos la siguiente medida. Definición 1.2 fSea N R! : Nf : ! +R + [ {0}. El conjunto ⌦(f (n)), leído omega de f (n), [ +{0} ⌦(f (n)) f (n) como:1.2 Sea f : N ! R [ {0}. El conjunto ⌦(f (n)), leído omega de f (n), Definición se define se define como: ⌦(f (n)) = {g : N ! R++[ {0} | 9c 2+R++ , n0 2 N. 8n n0. g(n) cf (n)} ⌦(f (n))⌦(f (n)): = = {g : NR ![R{0} N {g!+ [ {0} 2 R, n, 0n022NN.. 8n 9c R | 9c| 2 8n nn00. g(n). g(n) cf (n)} cf (n)} g(n) cf (n) ? ? O(fO(f Es frecuente confundir la medida (n)) (n)) como aplicable al caso peor y la medida Es frecuente ?⌦(f (n)) confundir ⌦(f (n)) como aplicablela medida Estacomo O(f (n)) al caso mejor. aplicable idea es errónea.al Aplicaremos caso peor yambas la medida (n)) comoal aplicable ⌦(f medidas caso peoral(también caso mejor. Esta idea podríamos es ambas aplicar errónea. Aplicaremos al caso promedio, oambas al medidas al caso caso mejor). Si elpeor tiempo t(n)(también t(n) de unpodríamos algoritmo aplicar en el casoambas peor al está caso en O(fpromedio, O(f (n)) o al (n)) y en caso⌦(g(n)), mejor).loSique el estamos tiempo diciendo t(n) de esunque algoritmo en el caso peor está en t(n) no puede valer más que c1cf (n), O(f (n)) y en ni menos ⌦(g(n)) t(n) 1 f (n) que c2lo ⌦(g(n)), quepara g(n), estamos diciendo esapropiadas dos constantes que t(n) noc puede y c y valer más valores de que c f (n), ni menos n suficientemente c2 g(n) grandes. c1 1 c2 2 n 1 que c2 g(n), para dos constantes apropiadas c1 y c2 y valores de n suficientemente ? grandes. Es fácil demostrar (ver ejercicios) el llamado principio de dualidad: g(n) 2 O(f (n)) ? ? si y demostrar Es fácil solo si f (n) (ver 2 ⌦(g(n)). g(n)22O(f ejercicios) el llamado principio de dualidad:g(n) O(f(n)) (n)) si y solo si f2(n) f (n) ⌦(g(n)) 2 ⌦(g(n)). Facultad de Informática - UCM ? ? Sucede con frecuencia que una misma función f (n) es a la vez cota superior e inferior f (n) del tiempo t(n) t(n) (peor, promedio, etc.) de un algoritmo. Para tratar estos casos, introducimos la siguiente medida.  1 ms 10 ms 10 ms 0.1 s 1s 1.02 s 102 2 ms 0.1 s 0.2 s 10 s 16.67 m 4.02⇤1020 sig 3 291 6 10 3 ms 1s 3s 16.67 m 11.57 d Capítulo 1. 3.4⇤10 Análisis desig la eficiencia 104 4 ms 10 s 40 s 1.16 d 31.71 a 6.3 ⇤ 103000 sig ? Sucede con frecuencia que una misma función f (n) es a la vez cota superior e inferior 6 Capítulo 1. Análisis de la eficiencia 5 del tiempo t(n) (peor, promedio, etc.) de un algoritmo. Para tratar estos casos, 10 5 ms 1.67 m 8.33 m 115.74 d 317.1 sig 3.16 ⇤ 1030093 sig introducimos la siguiente medida. Definición 6 6 ms 1.3 Elm conjunto 1.67 hde funciones 31.71 a ⇥(f 097.9leído 317(n)), sig del orden exacto de f (n), 10 16.67 3.1 ⇤ 10301020 sig se define como: Definición 1.3 El conjunto de funciones ⇥(f (n)), leído del orden exacto de f (n), se define como: ⇥(f (n)) = O(f (n)) \ ⌦(f (n)) ⇥(f (n)) = O(f (n)) \ ⌦(f (n)) También se puede definir como: También se puede definir como: ⇥(f (n)) = {g : N ! R++[ {0} | 9c1 , c2 2 R++ , n0 2 N. ⇥(f (n)) = {g : N ! R [ {0} | 9c1 , c2 2 R , n0 2 N. ⇥(f (n)) = {g : N ! R+ [ {0} | 9c18n , c2 2nn0R 8n 0..+c f0(n) g(n) 2N c1,1fn(n).g(n)c2cf2(n)} f (n)} 8n n0. c1 f (n)  g(n)  c2 f (n)} c2 f (n) g(n) c1 f (n) ? ? Siempre que sea posible, daremos el orden exacto del coste de un algoritmo, por ser ? Siempre que sea posible, daremos el orden exacto del coste de un algoritmo, por ser más informativo que dar solo una cota superior. más informativo que dar solo una cota superior. 3. Jerarquía de órdenes de complejidad 3. Jerarquía de órdenes de complejidad ? ? Es importante visualizar las implicaciones prácticas de que el coste de un algoritmo ? pertenezca avisualizar Es importante una u otralas clase de complejidad. implicaciones La Figura prácticas de que1 el muestra el crecimiento coste de un algoritmo de algunas de estas funciones, suponiendo que expresan un tiempo en milisegundos pertenezca a una u otra clase de complejidad. La Figura 1 muestra el crecimiento ms de (ms = milisegundos, = algunas s= de estas s = segundos, funciones, m= m = minutos, suponiendo h h== horas, que expresan etc.). en milisegundos un tiempo (ms = milisegundos, s = segundos, m = minutos, h = horas, etc.). ? ? Se aprecia inmediatamente la extraordinaria eficiencia de los algoritmos de coste en n) O(log O(log n): pasar de un tamaño de n = n = an n== 11000 1010 eficiencia 000 solo hace que el 000 000 ? Se aprecia inmediatamente la extraordinaria de los algoritmos de coste tiempo crezca de 1 milisegundo a 6. La búsqueda binaria en un vector ordenado, y en la O(log n): pasar de un tamaño de n = 10 a n = 1 000 000 solo hace que el búsqueda en ciertas estructuras de datos de este curso, tienen este coste en el caso tiempo peor.crezca de 1 milisegundo a 6. La búsqueda binaria en un vector ordenado, y la búsqueda en ciertas estructuras de datos de este curso, tienen este coste en el caso ? peor. En sentido contrario, los algoritmos de coste O(2 n ) son prácticamente inútiles: ? O(2n ) mientras que un problema de tamaño n = 10 se resuelve en aproximadamente un ? En segundo, sentido contrario, la edad del los algoritmos universo nde(1, conocido =coste 410 ⇥ 10 n ) son 8 siglos) O(2 prácticamente sería inútiles: totalmente insuficiente 1, 4 ⇥ 10 8 para resolver uno de tamaño Algunos algoritmos de vuelta mientras que un problema de tamaño n = 10 se resuelve en aproximadamente un n = 100. atrás que veremos en estelacurso segundo, edadtienen ese n = conocido coste del universo 100 en el caso(1,peor. 4 ⇥ 108 siglos) sería totalmente insuficiente para resolver uno de tamaño n = 100. Algunos algoritmos de vuelta atrás que veremos Esta curso ? en este tabla tienen confirma eselacoste afirmación hechapeor. en el caso al comienzo de este capítulo de que para ciertos algoritmos es inútil esperar a que los computadores sean más rápidos. Es más productivo invertir esfuerzo en diseñar mejores algoritmos para ese problema. ? Esta tabla confirma la afirmación hecha al comienzo de este capítulo de que para ciertos algoritmos Fundamentos es inútil esperar a que los computadores sean más rápidos. Es más de Algoritmia productivo invertir esfuerzo en diseñar mejores algoritmos para ese problema. ? Para mejorar la intuición anterior, hagamos el siguiente experimento: supongamos seis algorimos con los costes anteriores, tales que tardan todos ellos 1 hora en re- 3. Jerarquía de órdenes de complejidad 7 n log10 n n n log10 n n2 n3 2n 10 1 ms 10 ms 10 ms 0.1 s 1s 1.02 s 102 2 ms 0.1 s 0.2 s 10 s 16.67 m 4.02⇤1020 sig 103 3 ms 1s 3s 16.67 m 11.57 d 3.4⇤10291 sig 104 4 ms 10 s 40 s 1.16 d 31.71 a 6.3 ⇤ 103000 sig 105 5 ms 1.67 m 8.33 m 115.74 d 317.1 sig 3.16 ⇤ 1030093 sig 106 6 ms 16.67 m 1.67 h 31.71 a 317 097.9 sig 3.1 ⇤ 10301020 sig Figura 1: Crecimiento de distintas funciones de complejidad ? Para mejorar la intuición anterior, hagamos el siguiente experimento: supongamos seis algorimos con los costes anteriores, tales que tardan todos ellos 1 hora en re- solver un problema de tamaño n = 100. ¿Qué ocurre si duplicamos la velocidad del computador? O lo que es lo mismo, ¿qué ocurre si duplicamos el tiempo disponible? t(n) t = 1h. t = 2h. k1 · log n n = 100 n = 10 000 k2 · n n = 100 n = 200 k3 · n log n n = 100 n = 178 k 4 · n2 n = 100 n = 141 k5 · n3 n = 100 n = 126 k6 · 2n n = 100 n = 101 ? Observamos que mientras el de coste logarítmico es capaz de resolver problemas 100 veces más grandes, el de coste exponencial resuelve un tamaño practicamente igual al anterior. Obsérvese que los de coste O(n) y O(n log n) se comportan de acuerdo a la intuición de un usuario no informático: al duplicar la velocidad del computador (o el tiempo disponible), se duplica aproximadamente el tamaño del problema resuelto. En p los de coste O(nk ), al duplicar la velocidad, el tamaño se multiplica por un factor k 2. ? En la Figura 2 se muestra la jerarquía de órdenes de complejidad. Las inclu- siones estrictas expresan que se trata de clases distintas. Los algoritmos cuyos costes están en la parte izquierda resuelven problemas que se denominan tratables. Estos costes se denominan en su conjunto polinomiales. Hay problemas que solo admiten algoritmos de complejidad exponencial o superior. Se llaman intratables. ? También hay muchos problemas interesantes cuyos mejores algoritmos conocidos son exponenciales en el caso peor, pero no se sabe si existirán para ellos algoritmos polinomiales. Se llaman NP-completos y se verán en el próximo curso. El más conocido de todos es el problema SAT que consiste en determinar si una fórmula de la lógica proposicional es satisfactible. Facultad de Informática - UCM 8 Capítulo 1. Análisis de la eficiencia O(1) ⇢ O(log n) ⇢ O(n) ⇢ O(n log n) ⇢ O(n2 ) ⇢... ⇢ O(nk ) ⇢... ⇢ O(2n ) ⇢ O(n!) | {z } razonables en la práctica | {z } | {z } tratables intratables Figura 2: Jerarquía de órdenes de complejidad 4. Propiedades de los órdenes de complejidad ? O(a · f (n)) = O(f (n)) con a 2 R+. (✓) g 2 O(a · f (n)) , 9c 2 R+ , n0 2 N tal que 8n n0. g(n)  c · a · f (n). Tomando c0 = c · a se cumple que 8n n0. g(n)  c0 · f (n), luego g 2 O(f (n)). (◆) g 2 O(f (n)) , 9c 2 R+ , n0 2 N tal que 8n n0. g(n)  c · f (n). Entonces tomando c0 = ac se cumple que 8n n0. g(n)  c0 · a · f (n), luego g 2 O(a · f (n)). ? La base del logaritmo no importa: O(loga n) = O(logb n), con a, b > 1. La demostra- ción es inmediata sabiendo que: loga n logb n = loga b ? Si f 2 O(g) y g 2 O(h), entonces f 2 O(h). f 2 O(g) ) 9c1 2 R+ , n1 2 N tal que 8n n1. f (n)  c1 · g(n) g 2 O(h) ) 9c2 2 R+ , n2 2 N tal que 8n n2. g(n)  c2 · h(n) Tomando n0 = máx(n1 , n2 ) y c = c1 · c2 , se cumple 8n n0. f (n)  c1 · g(n)  c1 · c2 · h(n) Y por tanto f 2 O(h). ? Regla de la suma: O(f + g) = O(máx(f, g)). (✓) h 2 O(f + g) ) 9c 2 R+ , n0 2 N. 8n n0. h(n)  c · (f (n) + g(n)). Pero f  máx(f, g) y g  máx(f, g), luego: h(n)  c · (máx(f (n), g(n)) + máx(f (n), g(n))) = 2 · c · máx(f (n), g(n)) Tomando c0 = 2 · c se cumple que 8n n0. h(n)  c0 · máx(f (n), g(n)) y por tanto h 2 O(máx(f, g)). (◆) h 2 O(máx(f, g)) ) 9c 2 R+ , n0 2 N. 8n n0. h(n)  c · máx(f (n), g(n)). Pero máx(f, g)  f + g, luego h 2 O(f + g) trivialmente. ? Regla del producto: Si g1 2 O(f1 ) y g2 2 O(f2 ), entonces g1 · g2 2 O(f1 · f2 ). La demostración es similar. Fundamentos de Algoritmia Notas bibliográficas 9 ? Teorema del límite f (n) lı́mn!1 g(n) = m 2 R+ ) f 2 O(g) y g 2 O(f ) , O(f ) = O(g) f (n) lı́mn!1 g(n) =0 ) f 2 O(g) y g 62 O(f ) , O(f ) ⇢ O(g) lı́mn!1 fg(n) (n) = +1 ) f 62 O(g) y g 2 O(f ) , O(f ) O(g) ? Por el principio de dualidad, también tenemos: f (n) lı́mn!1 g(n) = m 2 R+ ) g 2 ⌦(f ) y f 2 ⌦(g) , ⌦(f ) = ⌦(g) f (n) lı́mn!1 g(n) =0 ) g 2 ⌦(f ) y f 62 ⌦(g) , ⌦(f ) ⌦(g) lı́mn!1 fg(n) (n) = +1 ) g 62 ⌦(f ) y f 2 ⌦(g) , ⌦(f ) ⇢ ⌦(g) ? Aplicando la definición de ⇥(f ), también tenemos: f (n) lı́mn!1 g(n) = m 2 R+ ) g 2 ⇥(f ) y f 2 ⇥(g) f (n) lı́mn!1 g(n) =0 ) f 2 O(g) pero f 62 ⇥(g) lı́mn!1 fg(n) (n) = +1 ) g 2 O(f ) pero g 62 ⇥(f ) Notas bibliográficas Se recomienda ampliar el contenido de estas notas estudiando el Capítulo 1 de (Peña, 2005) en el cual se han basado. También la Sección 1.4 de (Rodríguez Artalejo et al., 2011). El Capítulo 3 de (Martí Oliet et al., 2012) contiene material válido para este capítulo y material adicional que será utilizado en los Capítulos 3 y 4. También tiene numerosos ejemplos resueltos. Ejercicios 1. Demostrar el Principio de dualidad, es decir g(n) 2 O(f (n)) , f (n) 2 ⌦(g(n)). 2. Demostrar que todo polinomio am nm + · · · + a1 n + a0 , en n y de grado m, cuyo coeficiente am correspondiente al mayor grado sea positivo, está en O(nm ). 3. Demostrar f (n) lı́m = 0 ) O(f (n)) ⇢ O(g(n)) n!1 g(n) Dar un ejemplo de que la implicación inversa puede no ser cierta. 4. Demostrar f (n) lı́m = k > 0 ) f (n) 2 ⇥(g(n)) n!1 g(n) 5. Usar el teorema del límite para demostrar las siguientes inclusiones estrictas (supo- nemos k > 1): O(1) ⇢ O(log n) ⇢ O(n) ⇢ O(nk ) ⇢ O(2n ) ⇢ O(n!) Facultad de Informática - UCM 10 Capítulo 1. Análisis de la eficiencia 6. Si tenemos dos algoritmos con costes t1 (n) = 3n3 y t2 (n) = 600n2 , ¿cuál es mejor en términos asintóticos? ¿A partir de que umbral el segundo es mejor que el primero? 7. Si el coste de un algoritmo está en O(n2 ) y tarda 1 segundo para un tamaño n = 100, ¿de qué tamaño será el problema que puede resolver en 10 segundos? 8. Demostrar por inducción sobre n 0 las siguientes igualdades: Pn a) i=1 i = n(n + 1)/2. Pn 2 b) i=1 i = n(n + 1)(2n + 1)/6. Pn i c) i=1 2 i = (n 1)2n+1 + 2. P 9. Demostrar que ni=1 ik 2 ⇥(nk+1 ). p p 10. Demostrar que log n 2 O( (n)) pero que (n) 62 O(log n). 11. ¿Verdadero o falso? a) 2n + n99 2 O(n99 ). b) 2n + n99 2 ⌦(n99 ). c) 2n + n99 2 ⇥(n99 ). d ) Si f (n) = n2 , entonces f (n)3 2 O(n5 ). e) Si f (n) 2 O(n2 ) y g(n) 2 O(n), entonces f (n)/g(n) 2 O(n). f ) Si f (n) = n2 , entonces 3f (n) + 2n 2 ⇥(f (n)). g) Si f (n) = n2 y g(n) = n3 , entonces f (n)g(n) 2 O(n6 ). 12. Comparar con respecto a O y ⌦ los siguientes pares de funciones: a) 2n+1 , 2n. b) (n + 1)!, n!. p c) log n, n. d ) Para cualquier a 2 R+ , log n, na. 13. Supongamos que t1 (n) 2 O(f (n)) y t2 (n) 2 O(f (n)). Razonar la verdad o falsedad de las siguientes afirmaciones: a) t1 (n) + t2 (n) 2 O(f (n)). b) t1 (n) · t2 (n) 2 O(f (n2 )). c) t1 (n)/t2 (n) 2 O(1). 14. (Martí Oliet et al. (2012)) Demostrar o refutar cada una de las siguientes afirmacio- nes: a) n2 + n + log n 2 O(n2 ). b) n2 + n + log n 2 ⌦(n). c) n2 + n + log n 2 ⇥(log n). d ) 21n3 + 7n2 + n log n 17n + 8 2 O(n4 ). e) 2n + 3n + n59 2 O(n59 ). f ) 2n + 3n + n59 2 ⌦(2n ). Fundamentos de Algoritmia Ejercicios... 11 g) Si f (n) = n2 , entonces f (n)3 2 ⇥(f (n)3 ). h) ⇥(2n ) = ⇥(2n+2 ) = ⇥(4n ). i) log2 n 2 O(log3 n). 15. (Martí Oliet et al. (2012)) Para cada una de las siguientes funciones f (n), obtener el menor número natural k tal que f (n) 2 O(nk ). a) f (n) = 2n3 + n2 log n. b) f (n) = 3n5 + (log n)4. c) f (n) = (n4 + n2 + 1)/(n3 + 1). d ) f (n) = (n4 + n2 + 1)/(n4 + 1). e) f (n) = (n4 + 5 log n)/(n4 + 1). f ) f (n) = (n3 + 5 log n)/(n4 + 1). 16. (Martí Oliet et al. (2012)) Para cada una de las siguientes funciones f (n), encontrar una función g(n) del menor orden posible tal que f (n) 2 O(g(n)). a) f (n) = (n log n + n2 )(n3 + 2). b) f (n) = (2n + n2 )(n3 + 3n ). c) f (n) = n log(n2 + 1) + n2 log n. n 2 d ) f (n) = n2 + nn. e) f (n) = (n! + 2n )(n3 + log(n2 + 1)). 17. (Martí Oliet et al. (2012)) Comparar con respecto a O y ⌦ los siguientes pares de funciones: a) n2 + 3n + 7, n2 + 10. b) n2 log n, n3. c) n4 + log(3n8 + 7), (n2 + 17n + 3)2. d ) (n3 + n2 + n + 1)4 , (n4 + n3 + n2 + n + 1)3. e) log(n2 + 1), log n. f ) 2n+3 , 2n+7. n 2 g) 22 , 2n. 18. (Martí Oliet et al. (2012)) Indicar cuántas multiplicaciones realizan los siguientes algoritmos para calcular potencias en el caso peor. Indicar también sus ordenes asin- tóticos. 1 int potencia1(int x, int y){ 2 int p = 1; 3 while (y > 0){ 4 p = p*x; 5 y--; 6 } 7 return p; 8 } Facultad de Informática - UCM 12 Capítulo 1. Análisis de la eficiencia 1 int potencia2(int x, int y){ 2 int w = x; int p = 1; 3 while (y > 0){ 4 if (y %2 == 1) p = p*w; 5 y = y/2; 6 w = w*w; 7 } 8 return p; 9 } 19. Sea la siguiente función que implementa el algoritmo de inserción de un elemento en una lista (tLista) ordenada de enteros con posibles repeticiones, representada como una estructura con dos campos, elems, un array de enteros y cont, un entero. Indicar el número de instrucciones que ejecuta esta función y su orden asintótico en los casos mejor y peor. Nota: Para simplificar, se considera una instrucción a una línea de programa distinta de llave o else. 1 bool insertar(tLista& lista, int x){ 2 if (lista.cont == MAX){ 3 return false; 4 } else{ 5 int pos = lista.cont; 6 while (pos > 0 && x < lista.elems[pos-1]) { 7 lista.elems[pos] = lista.elems[pos-1]; 8 pos--; 9 } 10 lista.elems[pos] = x; 11 lista.cont++; 12 return true; 13 } 14 } 20. Sea la siguiente función que implementa el algoritmo de inserción de un elemento en una lista ordenada de enteros sin repeticiones. Indicar el número de instrucciones que ejecuta (ver Ej. 19) en los casos mejor y peor. Indicar también su orden asintótico en los casos mejor y peor en los siguientes dos supuestos: a) buscar es una búsqueda lineal; b) buscar es una búsqueda binaria. 1 bool insertar(tLista& lista, int x) { 2 if (lista.cont == MAX) 3 return false; 4 else { 5 int pos = 0; 6 if (!buscar(lista, x, pos)) {// pos i n d i c a l a p o s i c i ó n en l a 7 for (int i = lista.cont;i > pos;i--); // que debe c o l o c a r s e x 8 lista.elems[i] = lista.elems[i-1]; 9 lista.elems[pos] = x; 10 lista.cont++; 11 return true; 12 } 13 else return false; 14 } 15 } Fundamentos de Algoritmia Ejercicios... 13 21. Dada la siguiente función que implementa el algoritmo de ordenación por inserción directa. Indicar el número de instrucciones que ejecuta (ver Ej. 19) y su orden asin- tótico en los casos mejor y peor. 1 void ordenar(tLista& lista) { 2 int nuevo, pos; 3 for (int i = 1; i < lista.cont; i++) { 4 nuevo = lista.elems[i]; 5 pos = 0; 6 while ((pos < i) && !(lista.elems[pos] > nuevo)) { 7 pos++; 8 } 9 // pos : í n d i c e d e l p r i m e r mayor ; i s i no l o hay 10 for (int j = i; j > pos; j--) { 11 lista.elems[j] = lista.elems[j - 1]; 12 } 13 lista.elems[pos] = nuevo; 14 } 15 } 22. Dada la siguiente función que implementa el algoritmo de ordenación de la burbuja. Indicar el número de instrucciones que ejecuta (ver Ej. 19) y su orden asintótico en los casos mejor y peor. 1 void ordenar(tLista& lista) { 2 bool inter = true; 3 int i = 0; int tmp; 4 while ((i < lista.cont - 1) && inter) { 5 inter = false; 6 for (int j = lista.cont - 1; j > i; j--) 7 if (lista.elems[j] < lista.elems[j - 1]) { 8 tmp = lista.elems[j]; 9 lista.elems[j] = lista.elems[j - 1]; 10 lista.elems[j - 1] = tmp; 11 inter = true; 12 } 13 if (inter) 14 i++; 15 } 16 } Facultad de Informática - UCM