Análisis de Algoritmos: Notación Asintótica y Recurrencias

Y 0 flashcards y 3 preguntas más en el documento.

Texto del documento

APUNTES PRÁCTICAS DE PROGRAMACIÓN Grado en Ingeniería Informática Universitat Oberta de Catalunya AprenAI 2026-2027 Guía completa de análisis de algoritmos: notación asintótica O, cálculo de complejidad en bucles y condicionales, y resolución de ecuaciones de recurrencia.

APREN.AI Índice 1 Fundamentos de eficiencia y notación asintótica La función de tiempo de ejecución y la cota superior Reglas algebraicas de composición 2 Análisis de estructuras de control iterativas y secuenciales Asignaciones y secuencias de instrucciones Sentencia condicional Sentencia iterativa (bucles) 3 Análisis de algoritmos recursivos mediante relaciones de recurrencia Definición de ecuaciones de recurrencia Método de sustitución reiterada Análisis de algoritmos recursivos sobre estructuras 4 Formulario Propiedades y reglas de la notación asintótica Estructuras de control estructuradas Análisis de recurrencias Errores típicos Soluciones de las preguntas de repaso Estos apuntes pueden contener errores u omisiones.

Son un material de apoyo y no sustituyen al temario oficial ni al profesorado: contrasta la información importante. Análisis de Algoritmos: Notación Asintótica y Recurrencias 1 1 Fundamentos de eficiencia y notación asintótica AL ACABAR SABRÁS Identificar la notación asintótica O como cota superior del crecimiento del tiempo de ejecución. Aplicar las reglas de la suma y del producto para simplificar expresiones temporales compuestas. Reconocer las relaciones de crecimiento relativo entre las funciones de complejidad más comunes. PIÉNSALO ANTES DE LEER 1 ¿Por qué al comparar dos algoritmos prescindimos del tiempo exacto en segundos y usamos órdenes matemáticos?

Al diseñar soluciones computacionales, suele existir más de un método válido para resolver un mismo problema. Para seleccionar la alternativa más adecuada se analiza la eficiencia, tomando como referencia principal el tiempo de ejecución computacional y su ritmo de crecimiento al aumentar el volumen de datos de entrada. La función de tiempo de ejecución y la cota superior El comportamiento temporal de un algoritmo se modela mediante una función matemática , en la que la variable cuantifica el tamaño de la entrada. Para caracterizar la velocidad con la que crece este tiempo sin depender de la máquina o del compilador, se utiliza la notación asintótica mediante el orden de cota superior .

DEFINICIÓN Se afirma formalmente que T(n) es O(f(n)) si la función se encuentra acotada superiormente por un múltiplo de . De este modo, reúne el conjunto de funciones cuya tasa de crecimiento es a lo sumo tan rápida como la de . En el estudio asintótico se aplican dos propiedades algebraicas esenciales: Supresión de factores constantes: para cualquier constante positiva multiplicativa , el conjunto coincide con . Por ejemplo, una expresión como pertenece al orden . Desprecio de términos de orden inferior: si una función crece más despacio que , entonces .

En un polinomio como , el término cúbico domina asintóticamente sobre los términos cuadrático y lineal, concluyendo que la expresión resultante es de orden O(n^3). T(n) n O(f(n)) T(n) f(n) O(f(n)) g(n) f(n) c O(c × f(n)) O(f(n)) 20n3 O(n ) 3 g(n) f(n) O(f(n) + g(n)) = O(f(n)) 20n + 3 40n + 2 80n Análisis de Algoritmos: Notación Asintótica y Recurrencias 2 COMPRUEBA 2 ¿Por qué la complejidad de una función temporal definida por 20n³ + 40n² + 80n se reduce simplemente a O(n³)? Reglas algebraicas de composición Cuando un algoritmo enlaza varias subtareas o instrucciones consecutivas, su comportamiento se rige por la regla de la suma y la regla del producto.

Operación Hipótesis de tiempos Tiempo resultante Complejidad asintótica Regla de la suma (ejecución secuencial) y Regla del producto (ejecución anidada) y A partir de la combinación de ambas propiedades operativas se derivan las siguientes deducciones básicas: Si una función temporal toma un valor puramente invariable , su orden es (tiempo constante). Al sumar una constante aditiva a una función, , la cota resultante sigue siendo . Al multiplicar una función por una constante, , la cota resultante se conserva como .

La siguiente gráfica ilustra las diferencias en la tasa de crecimiento de las clases asintóticas más comunes conforme se incrementa el tamaño de la entrada : T (n) = 1 O(f(n)) T (n) = 2 O(g(n)) T (n) + 1 T (n) 2 O(max(f(n), g(n))) T (n) = 1 O(f(n)) T (n) = 2 O(g(n)) T (n) × 1 T (n) 2 O(f(n) × g(n)) T(n) = c O(1) T(n) = c + f(n) O(f(n)) T(n) = c × f(n) O(f(n)) n Análisis de Algoritmos: Notación Asintótica y Recurrencias 3 Gráfica de curvas de crecimiento para distintas complejidades asintóticas habituales.

ERROR FRECUENTE Al aplicar la regla de la suma sobre varios bloques de instrucciones, un fallo habitual es acumular las funciones sumando sus órdenes dentro del operador (por ejemplo, expresar incorrectamente ). La regla establece que la suma queda dominada por el término de mayor tasa de crecimiento, debiendo simplificarse a . IDEAS CLAVE La función modela el tiempo de ejecución de un programa frente al tamaño de la entrada. La notación delimita formalmente una cota asintótica superior para la velocidad de crecimiento del tiempo. Las constantes multiplicativas y los sumandos de menor orden se ignoran en el análisis asintótico.

La regla de la suma selecciona el orden máximo de las componentes secuenciales: . La regla del producto multiplica los órdenes cuando se ejecutan tareas anidadas: . O(n + 2 n) O(max(f(n), g(n))) T(n) O(f(n)) O(max(f(n), g(n))) O(f(n) × g(n)) Análisis de Algoritmos: Notación Asintótica y Recurrencias 4 COMPRUEBA LO QUE HAS APRENDIDO 3. ¿Cuál es la complejidad asintótica de un fragmento de código con tiempo según las reglas asintóticas? 4. Si un programa realiza dos operaciones consecutivas e independientes con órdenes y , ¿qué cota describe el conjunto? Test Rodea la respuesta correcta. Las soluciones están al final. 5. ¿Qué representa la expresión T(n) = O(f(n)) en el análisis de algoritmos?

6. ¿Cuál es el orden de complejidad resultante para T(n) = 20n³ + 40n² + 80n? 7. ¿Qué orden asintótico corresponde a la ejecución consecutiva de dos etapas O(f(n)) y O(g(n))? 8. Si una operación elemental tiene un tiempo invariable T(n) = c, ¿cuál es su orden de complejidad? 2 Análisis de estructuras de control iterativas y secuenciales AL ACABAR SABRÁS Calcular la complejidad temporal de asignaciones, secuencias y estructuras condicionales. Formular la función de tiempo de ejecución de un bucle iterativo considerando las comprobaciones de condición. Deducir el orden asintótico global de fragmentos de código iterativo combinados.

T(n) = 5n + 12 O(n) O(n ) 2 El consumo de memoria máximo del ordenador. a) Una cota superior asintótica del tiempo de ejecución. b) El tiempo exacto en microsegundos de un algoritmo. c) El número mínimo estricto de pasos del algoritmo. d) O(n) a) O(n²) b) O(n³) c) O(20n³) d) O(max(f(n), g(n))) a) O(min(f(n), g(n))) b) O(f(n) / g(n)) c) O(f(n) · g(n)) d) O(c) a) O(1) b) O(0) c) O(n) d) Análisis de Algoritmos: Notación Asintótica y Recurrencias 5 PIÉNSALO ANTES DE LEER 9 ¿Por qué un bucle que se repite n veces no consume exactamente n operaciones de comprobación?

El análisis formal de un algoritmo estructurado se aborda descomponiendo el código en sus instrucciones individuales, deduciendo el coste temporal de cada bloque elemental y agregándolos según su mecanismo de control. Asignaciones y secuencias de instrucciones Las sentencias de asignación y las operaciones aritméticas elementales (como sumas, divisiones o restos) demandan un número invariable de ciclos elementales que no dependen del tamaño de entrada . Por consiguiente, su tiempo de cálculo es O(1). EJEMPLO Consideremos las siguientes tres operaciones sucesivas: 1. a := 100; 2. a := a + 1; 3. a := (b div 4) mod 8 + 1000; Cada una de estas líneas consume un tiempo fijo de orden constante .

Cuando se analiza una secuencia de instrucciones cuyos tiempos respectivos están acotados por , el tiempo total es la suma de los tiempos individuales.

Aplicando la regla de la suma de forma reiterada, se deduce la expresión global: Sentencia condicional Para determinar el coste de una bifurcación selectiva, se debe considerar el peor caso posible entre las ramas computacionales: n O(1) P , P , ..., P 1 2 k T (n) = i O(f (n)) i T (n) = O(max(f (n), f (n), ..., f (n))) i=1 k i 1 2 k Estructura condicional simple ( if <condicion> then <instrucciones> end if ): el tiempo global es la suma del tiempo de evaluar la condición y el tiempo de ejecutar el bloque de instrucciones en el peor de los casos. Su complejidad corresponde a .

1 T(n) T (n) = 1 O(f(n)) T (n) = 2 O(g(n)) O(max(f(n), g(n))) Estructura condicional alternativa ( if <condicion> then <instrucciones1> else <instrucciones2> end if ): al evaluar la expresión lógica se invierte un tiempo . Los bloques then y else conllevan respectivamente y . El tiempo total en el peor escenario es , por lo que la complejidad asintótica se simplifica en O(max(f(n), g(n), h(n))).

2 T (n) = 1 O(f(n)) T (n) = 2 O(g(n)) T (n) = 3 O(h(n)) T (n) + 1 max(T (n), T (n)) 2 3 Análisis de Algoritmos: Notación Asintótica y Recurrencias 6 Si la condición y ambas ramas constan de instrucciones elementales de tiempo acotado ( ), el tiempo resultante adopta la forma constante , perteneciente al orden . COMPRUEBA 10 ¿Cómo se calcula el orden de complejidad en el peor caso de una instrucción if-then-else cuyas ramas no tardan lo mismo? Sentencia iterativa (bucles) En un bucle interactivo de la forma while <condicion> do <instrucciones> end while , la condición lógica de parada debe comprobarse k + 1 veces para completar con éxito un total de k iteraciones del cuerpo interno.

PROCESO Evaluación temporal en el bucle iterativo 1 Evaluación de con dición Consume tiempo T1(n); se repite k+1 veces en total. 2 Cuerpo del bucle Consume tiempo T2(n); se repite exactamente k veces. 3 Comprobación final Resulta falsa e interrumpe la ite ración del bloque.

Siendo el tiempo invertido en evaluar la condición y el tiempo consumido en una iteración del cuerpo del bucle, el tiempo total queda expresado por la fórmula de acumulación: k , k , k 1 2 4 T(n) = k + 1 max(k , k ) = 2 4 k O(1) T (n) 1 T (n) 2 T(n) = T (n) + (T (n) + T (n)) = T (n) + k × (T (n) + T (n)) 1 i=1 k 1 2 1 1 2 Análisis de Algoritmos: Notación Asintótica y Recurrencias 7 EJEMPLO Analicemos el siguiente algoritmo de recorrido secuencial con un bucle iterativo: 1 i := 1; 2 count := 0; 3 while (i # n) do 4 if (v[i] = x) then 5 count := count + 1; 6 end if; 7 i := i + 1; 8 end while Para calcular la complejidad total: 1.

Las instrucciones de inicialización (líneas 1 y 2) toman tiempos constantes y . 2. Dentro del cuerpo del bucle, la condición condicional (líneas 4 a 6) invierte en el peor caso , mientras que el incremento del índice (línea 7) consume . Todas son de orden constante. 3. La condición del bucle (línea 3) requiere un tiempo y se evalúa para un total de repeticiones completas. 4. El tiempo de las líneas 3 a 8 equivale a . 5. Sumando las inicializaciones: , lo que demuestra un crecimiento de orden O(n) (lineal). ERROR FRECUENTE Un error muy extendido al evaluar bucles while consiste en multiplicar el coste de la condición únicamente por el número de iteraciones .

Debe tenerse siempre en cuenta la comprobación final fallida que provoca la salida del bucle, sumando exactamente comprobaciones en total. IDEAS CLAVE Las asignaciones y operaciones aritméticas elementales tienen complejidad constante . Una secuencia sucesiva de instrucciones queda delimitada por el tiempo de la sentencia más costosa: . En una sentencia condicional alternativa se evalúa el peor caso tomando el tiempo de la condición más el máximo de las dos ramas. En una estructura iterativa que da vueltas, la condición se examina formalmente veces. Un recorrido de un bucle de pasos con operaciones internas constantes genera una función de tiempo lineal .

T (n) = 1 k 1 T (n) = 2 k 2 k + 4 k5 k 7 k 3 n T (n) = 3-8 k + 3 n × (k + 3 k + 4 k + 5 k ) 7 T(n) = k + 1 k + 2 k + 3 n × (k + 3 k + 4 k + 5 k ) = 7 k + n × K k k + 1 O(1) O(max(f (n))) i k k + 1 n O(n) Análisis de Algoritmos: Notación Asintótica y Recurrencias 8 COMPRUEBA LO QUE HAS APRENDIDO 11. ¿Cuántas veces se ejecuta la comprobación booleana de un bucle while que itera exactamente 10 veces? 12. ¿Cuál es la complejidad temporal de una estructura if-then-else si la condición toma tiempo , la rama then tarda y la rama else ? Test Rodea la respuesta correcta. Las soluciones están al final. 13. ¿Cuál es la complejidad temporal de una asignación como a := (b div 4) mod 8 + 1000? 14.

En un bucle while que realiza k iteraciones, ¿cuántas veces se evalúa la condición de parada? 15. ¿Qué expresión representa el coste global de un bloque if c then A else B end if? 16. Si un bucle realiza n iteraciones con un cuerpo interno de coste constante, ¿cuál es su orden? 3 Análisis de algoritmos recursivos mediante relaciones de recurrencia AL ACABAR SABRÁS Plantear formalmente las ecuaciones de recurrencia divididas en caso base y caso recursivo. Aplicar el método de sustitución iterada hasta hallar la expresión cerrada independiente de recurrencias. Calcular la complejidad asintótica de algoritmos recursivos que contienen operaciones internas de orden no constante.

O(1) O(n) O(1) O(1) a) O(n²) b) O(log n) c) O(n) d) k - 1 veces a) 2k veces b) k + 1 veces c) k veces d) T(c) + max(T(A), T(B)) a) max(T(c), T(A) + T(B)) b) T(c) + T(A) · T(B) c) T(c) · max(T(A), T(B)) d) O(1) a) O(n²) b) O(n) c) O(log n) d) Análisis de Algoritmos: Notación Asintótica y Recurrencias 9 PIÉNSALO ANTES DE LEER 17 ¿Por qué no se puede aplicar directamente la regla de la suma para acotar una función recursiva? El análisis asintótico de las subrutinas recursivas se fundamenta en los mismos principios que el de las sentencias iterativas: se modela en primer lugar la función de tiempo de ejecución y, a continuación, se deduce su orden de complejidad asintótica.

Definición de ecuaciones de recurrencia Dado que un algoritmo recursivo se invoca a sí mismo sobre instancias de menor tamaño, su función temporal queda expresada en términos del coste de sus propias llamadas internas. Esta función se compone de dos elementos estructurales: Caso base: describe el coste computacional directo cuando no se realizan más llamadas recursivas (generalmente cuando el parámetro alcanza un valor umbral, como ). Corresponde habitualmente a operaciones elementales constantes . Caso recursivo: cuantifica la suma de las operaciones propias realizadas en la llamada en curso más el tiempo demandado por las nuevas invocaciones dependientes de un tamaño reducido, como .

Método de sustitución reiterada Resolver una relación de recurrencia consiste en encontrar una forma cerrada para T(n) que no dependa recursivamente de la propia función, sino exclusivamente del valor de . El procedimiento general por sustitución reiterada sigue estos pasos: T(n) T(n) n = 0 T(0) = c 1 T(n 1) + c 2 n Expansión algebraica inicial: se sustituye la llamada recursiva aplicando repetidamente la propia definición matemática para , y pasos subsiguientes. 1 n 1 n 2 Generalización para la etapa : se detecta el patrón inductivo y se expresa la función en términos de un parámetro genérico de paso .

2 i i Identificación del valor umbral: se calcula qué valor debe adoptar para que el argumento alcance la condición del caso base no recursivo. 3 i Sustitución final y obtención de la forma cerrada: se reemplaza el valor de en la expresión generalizada para calcular la función final y determinar su orden asintótico en notación . 4 i O Análisis de Algoritmos: Notación Asintótica y Recurrencias 10 EJEMPLO Resolvamos paso a paso la relación de recurrencia elemental: 1. Desarrollamos las sustituciones sucesivas: 2. Deducimos el término para un número de expansiones: 3. Igualamos el argumento al caso base: . 4.

Evaluamos la expresión en el caso base sabiendo que : La solución cerrada es T(n) = 2n + 1, con complejidad lineal O(n). COMPRUEBA 18 ¿Cuál es el objetivo principal del método de sustitución sucesiva al resolver una recurrencia? Análisis de algoritmos recursivos sobre estructuras Al procesar vectores o listas, los parámetros que controlan el avance de la recursión definen la variable de tamaño en la función temporal. 1.

Sustitución de caracteres en vector (acción replace ) action replace(inout v: vector[MAX] of char, in a: char, in b: char, in size: integer, out count: integer) if size = 0 then count := 0; else replace(v, a, b, size-1, count); if v[size] = a then v[size] := b; count := count + 1; end if; end if; end action El parámetro size disminuye en 1 en cada llamada hasta llegar a 0. Definiendo : Si : se realizan comprobaciones y asignaciones elementales de coste constante .

T(n) = { 1 T(n 1) + 2 si n = 0 si n > 0 T(n) = T(n 1) + 2 = (T(n 2) + 2) + 2 = T(n 2) + 4 = (T(n 3) + 2) + 4 = T(n 3) + 6 i T(n) = T(n i) + 2i n i = 0 i = n T(0) = 1 T(n) = T(n n) + 2n = T(0) + 2n = 2n + 1 n n = size n = 0 T(0) = c 1 Análisis de Algoritmos: Notación Asintótica y Recurrencias 11 Si : se ejecuta una llamada sobre sumada a un conjunto de operaciones elementales constantes , resultando en . Desplegando la recurrencia para niveles: Tomando para alcanzar el caso base ( ): Por tanto, el procedimiento posee complejidad lineal O(n). 2.

Conteo combinado sobre estructuras anidadas (función sumCount ) function sumCount(v: vector[N] of list(integer); nelem: integer): integer var sum: integer; end var sum := 0; if nelem = 0 then sum := 0; else sum := countNeg(v[nelem]) + sumCount(v, nelem-1); end if; return sum; end function Sea el número de elementos restantes del vector principal. En cada etapa recursiva se invoca a la función auxiliar countNeg , cuyo tiempo en el peor caso es lineal respecto al tamaño de la lista analizada: .

Planteando la ecuación temporal para sumCount : Desarrollando la recurrencia mediante sustitución reiterada: Aplicando el caso base al sustituir (con ): Si el número de elementos de cada lista en el peor caso alcanza el tamaño del vector ( ) y sustituyendo la definición lineal de : n = 0 n 1 c 2 T(n) = T(n 1) + c 2 i T(n) = T(n i) + i × c 2 i = n n i = 0 T(n) = T(0) + n × c = c + n × c = O(n) 2 1 2 m = nelem n T (n) = c k + 1 n × k 2 T (m) = s { k 3 k + T (n) + T (m 1) 4 c s si m = 0 si m > 0 T (m) s = k + T (n) + T (m 1) 4 c s = 2k + 2T (n) + T (m 2) 4 c s = i × k + i × T (n) + T (m i) 4 c s i = m T (0) = s k 3 T (m) = m × k + m × T (n) + k s 4 c 3 m = n T (n) c T (n) s = n × k + n × (k + n × k ) + k 4 1 2 3 = k + n × (k + k ) + n × k = O(n ) 3 1 4 2 2 2 Análisis de Algoritmos: Notación Asintótica y Recurrencias 12 La combinación del decrecimiento recursivo del vector junto al recorrido de la lista lineal en cada llamada da como resultado una complejidad cuadrática O(n^2).

ERROR FRECUENTE Al formular la recurrencia de una rutina que invoca una función auxiliar dentro del caso recursivo, se suele cometer el error de modelar el coste adicional como una simple constante . Si la función subordinada recorre una colección dependiente de (como ocurría con countNeg ), su coste temporal completo debe integrarse explícitamente en cada llamada recursiva. PROCESO Método de sustitución sucesiva 1 Expansión recursiva Desplegar T(n-1), T(n- 2)... hasta visualizar la regla de evolución. 2 Generali zación en paso i Formular la expresión genérica en función del índice i. 3 Aplicación del caso base Calcular i para alcan zar la base (n - i = 0 => i = n).

4 Forma ce rrada Sustituir T(0) y deri var la cota asintótica O resultante. IDEAS CLAVE El tiempo de un algoritmo recursivo se formula mediante ecuaciones de recurrencia compuestas de caso base y caso recursivo. El método de sustitución sucesiva expande el término recursivo hasta identificar una regla de evolución dependiente del paso . El valor del parámetro genérico se despeja forzando la condición que activa el caso base. Cuando cada nivel recursivo realiza un trabajo de orden constante y el problema decrece en una unidad, la complejidad resultante es lineal .

Si cada paso recursivo ejecuta una rutina interna de orden lineal , la acumulación sucesiva genera una complejidad global cuadrática . COMPRUEBA LO QUE HAS APRENDIDO 19. ¿Qué complejidad posee la recurrencia con caso base ? 20. En la función sumCount, ¿por qué la complejidad asintótica se eleva a en lugar de permanecer en ? c n i i O(1) O(n) O(n) O(n ) 2 T(n) = T(n 1) + c T(0) = k O(n ) 2 O(n) Análisis de Algoritmos: Notación Asintótica y Recurrencias 13 Test Rodea la respuesta correcta. Las soluciones están al final. 21. ¿Cuáles son las dos componentes fundamentales de una ecuación de recurrencia en algoritmos recursivos? 22.

¿Qué forma cerrada se obtiene al resolver T(n) = T(n-1) + 2 con T(0) = 1? 23. Si una acción recursiva reduce su tamaño n en una unidad y ejecuta trabajo lineal O(n) por llamada, ¿cuál es su complejidad? 24. ¿Cuál es la complejidad del procedimiento replace si procesa recursivamente un vector de longitud n? 4 Formulario Propiedades y reglas de la notación asintótica Fórmula o procedimiento Significado de los símbolos Cuándo se usa : constante multiplicativa; : tamaño de la entrada Para suprimir factores constantes en el cálculo asintótico. si : término dominante; : término de menor orden Para despreciar sumandos de menor crecimiento relativo.

, : tiempos de cada bloque Regla de la suma: ejecución secuencial o ramificada de algoritmos. : tiempos de instrucciones anidadas o multiplicadas Regla del producto: sentencias o bucles anidados. Condición lógica y cuerpo iterativo. a) Regla de la suma y regla del producto. b) Caso base y caso recursivo. c) Término cuadrático y constante multiplicativa.

d) T(n) = n² + 1 a) T(n) = n + 2 b) T(n) = 2n + 1 c) T(n) = 2 d) O(2 ) a) O(log n) b) O(n²) c) O(n) d) O(n log n) a) O(n) b) O(n²) c) O(1) d) O(c f(n)) = O(f(n)) c n O(f(n) + g(n)) = O(f(n)) g(n) O(f(n)) f(n) g(n) T (n) + 1 T (n) = 2 O(max(f(n), g(n))) T (n) = 1 O(f(n)) T (n) = 2 O(g(n)) T (n) 1 T (n) = 2 O(f(n) g(n)) T , T 1 2 Análisis de Algoritmos: Notación Asintótica y Recurrencias 14 Estructuras de control estructuradas Fórmula o procedimiento Significado de los símbolos Cuándo se usa : tiempo elemental constante Asignaciones directas y operaciones aritméticas elementales. : número de sentencias; : orden de la sentencia Secuencia sucesiva de instrucciones independientes.

: coste condición; : costes de ramas then y else Sentencias condicionales (peor caso). : iteraciones realizadas; : condición evaluada veces; : cuerpo ejecutado veces Sentencias iterativas (bucle while). Análisis de recurrencias Fórmula o procedimiento Significado de los símbolos Cuándo se usa Expandir sucesivamente Generalizar para el paso Determinar para alcanzar el caso base ( ) Reemplazar y resolver forma cerrada Expresar en notación : nivel de profundidad recursiva; : parámetro de recursión Método de resolución de recurrencias por sustitución reiterada. : coste caso base ; : trabajo constante por nivel Llamada recursiva con decremento unitario y trabajo constante.

: llamada a función interna dependiente del tamaño Llamada recursiva combinada con un recorrido lineal subordinado. Errores típicos Condición en bucles iterativos: contabilizar la condición únicamente veces en lugar de (incluyendo la comprobación final de salida falsa). Regla de la suma: mantener sumandos inferiores dentro de la notación asintótica (por ejemplo, escribir en lugar de simplificar a ). Rutinas subordinadas en recursión: tratar funciones auxiliares como de coste constante cuando su coste temporal real depende de la entrada . T(n) = k O(1) k T (n) = i=1 k i O(max(f (n), …

, f (n))) 1 k k f (n) i i T(n) = T (n) + 1 max(T (n), T (n)) = 2 3 O(max(f(n), g(n), h(n))) T 1 T , T 2 3 T(n) = T (n) + 1 k (T (n) + 1 T (n)) 2 k T 1 k + 1 T 2 k T(n 1), T(n 2) i i n i = 0 i = n O i n T(n) = T(n 1) + c 2 T(n) = c + 1 n c = 2 O(n) c 1 T(0) c 2 T(n) = T(n 1) + O(n) T(n) = O(n ) 2 O(n) n k k + 1 O(n + 2 n) O(n ) 2 O(1) n Análisis de Algoritmos: Notación Asintótica y Recurrencias 15 Soluciones de las preguntas de repaso 1. Porque el tiempo en segundos depende del procesador y del entorno, mientras que el orden asintótico refleja objetivamente cómo escala la solución con datos masivos. 2.

Porque en el análisis asintótico las constantes multiplicativas se descartan y los términos con menor tasa de crecimiento resultan despreciables frente al término dominante n³. 3. Es , ya que la constante aditiva 12 se desestima por la regla de la suma y la constante multiplicativa 5 se elimina por la regla del producto. 4. Describe una cota , puesto que la regla de la suma determina la complejidad a partir del máximo entre ambos órdenes. 5. b) Una cota superior asintótica del tiempo de ejecución.. La notación O mayúscula describe formalmente una cota superior en el ritmo de crecimiento temporal. 6. c) O(n³).

Se desprecian los factores constantes y los términos cuadrático y lineal al dominar el término de grado 3. 7. a) O(max(f(n), g(n))). La regla de la suma estipula que la complejidad combinada equivale al término con mayor crecimiento: O(max(f(n), g(n))). 8. b) O(1). Cualquier tiempo fijo independiente del tamaño de entrada posee una complejidad asintótica constante O(1). 9. Porque requiere una evaluación adicional al final con resultado falso para poder detener el ciclo. 10. Se suma el tiempo de evaluación de la condición al máximo temporal entre las ramas then y else, resultando en O(max(f(n), g(n), h(n))). 11.

Se ejecuta 11 veces: 10 comprobaciones verdaderas para ingresar al bucle y 1 comprobación final falsa que determina la salida. 12. La complejidad en el peor caso es , al regirse por el máximo entre las componentes según la regla de la suma. 13. a) O(1). Las operaciones aritméticas elementales y las asignaciones directas tienen un tiempo fijo de orden constante O(1). 14. c) k + 1 veces. La condición se comprueba en cada una de las k iteraciones ejecutadas y una última vez para salir. 15. a) T(c) + max(T(A), T(B)). En el peor caso, al tiempo de la condición se le añade el tiempo de la rama más costosa. 16. c) O(n). Sumar n veces una constante da una función polinomial lineal de orden O(n). 17.

Porque el número de llamadas depende del parámetro de entrada, requiriendo plantear y resolver primero una ecuación de recurrencia. 18. Obtener una expresión matemática cerrada para T(n) que dependa únicamente de n y de constantes, sin referencias a la propia función recursiva. 19. Posee complejidad lineal , pues tras sustituciones la forma cerrada resultante es . 20. Porque en cada una de las llamadas recursivas se ejecuta la función auxiliar countNeg, que consume tiempo lineal , provocando que el término dominante sea cuadrático. O(n) O(n ) 2 O(n) O(n) n T(n) = k + n × c n O(n) Análisis de Algoritmos: Notación Asintótica y Recurrencias 16 21. c) Caso base y caso recursivo..

Toda recurrencia algorítmica se define mediante la combinación de un caso base directo y un caso recursivo. 22. c) T(n) = 2n + 1. Al expandir i veces se obtiene T(n-i) + 2i; haciendo i = n y sumando T(0)=1 resulta 2n + 1. 23. c) O(n²). Al sumar n veces un trabajo proporcional a n se genera un polinomio de segundo grado con complejidad O(n²). 24. b) O(n). Realiza n llamadas con un trabajo constante en cada nivel, lo que determina una complejidad lineal O(n). Análisis de Algoritmos: Notación Asintótica y Recurrencias 17