Maestría en Ciencias en Ingeniería y Tecnologías Computacionales

Proceso de Admisión 2022

Análisis de Algoritmos
Dr.Miguel Morales Sandoval
 Tema:
1. Análisis y diseño de algoritmos

1.1 Algoritmos
1.2 Análisis de algoritmos
1.3 Complejidad algorítmica
1.4 Notación asintótica
1.5 Ejercicios
1.6 Complejidad de principales algoritmos

1/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

1. ¾Qué es un algoritmo?

2/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

1. ¾Qué es un algoritmo?

• Secuencia de pasos nitos, no ambiguos, ordenados, para

resolver un problema
• Requiere de datos de entrada, los cuales se usan en los pasos
del algoritmo
• Produce una salida o resultado después de la ejecución de
cada uno de los pasos
• En computación, un algoritmo usa recursos de cómputo y de
almacenamiento durante la ejecución de cada paso
• En la teoría, contamos con recursos ilimitados
• En la práctica, un algoritmo podría requerir más recursos de
cómputo o de memoria de los que se disponen
2/56 Programación Básica - Análisis de Algoritmos Junio 2022
 Algoritmos

¾Es el siguiente un algoritmo?

1 1 Input: x an integer number

Output: y a real number

2 i ← 0;
3 y ← 1;
4 while i < x do
5 y ← ∗ = 2;
6 i ← + = 1;
7 end
8 return y
Secuencia de pasos 1: ¾es un algoritmo?

3/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

Características de un buen algoritmo

1. Precisión  los pasos que conforman el algoritmo están

claramente denidos (no ambiguos).

2. Unicidad  el resultado de cada paso en el algoritmo está

únicamente denido por los datos de entrada de ese paso y por

los resultados de los pasos anteriores.

3. Finitidad  el algoritmo termina después de que se han

ejecutado un número nito de pasos.

4. Generalidad  el algoritmo es aplicable a diversos conjuntos

de entrada.
4/56 Programación Básica - Análisis de Algoritmos Junio 2022
 Algoritmos

Ejemplo de algoritmos a distintos niveles de abstracción

5/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

Construcción y validación de un algoritmo

1. Analizar el problema y desarrollar la especicación del mismo (determinar los

datos de entrada, resultados esperados, y restriciones).

6/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

Construcción y validación de un algoritmo

1. Analizar el problema y desarrollar la especicación del mismo (determinar los

datos de entrada, resultados esperados, y restriciones).

2. Diseñar la solución (crea el o los algoritmos requeridos y verica que el diseño es

correcto).

6/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

Construcción y validación de un algoritmo

1. Analizar el problema y desarrollar la especicación del mismo (determinar los

datos de entrada, resultados esperados, y restriciones).

2. Diseñar la solución (crea el o los algoritmos requeridos y verica que el diseño es

correcto).

3. Implementar el algoritmo (crea el programa) y verica que la escritura del

programa es correcta.

6/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

Construcción y validación de un algoritmo

1. Analizar el problema y desarrollar la especicación del mismo (determinar los

datos de entrada, resultados esperados, y restriciones).

2. Diseñar la solución (crea el o los algoritmos requeridos y verica que el diseño es

correcto).

3. Implementar el algoritmo (crea el programa) y verica que la escritura del

programa es correcta.

4. Vericar el programa, mediante depuración y realización de pruebas para

asegurar que el algoritmo es correcto y completo, bajo todos los casos de

prueba.

6/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

Un algoritmo es correcto/válido si resuelve el problema computacio-

nal para el cual fue diseñado. Para cada entrada, produce la salida

deseada (correcta).

7/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

Un algoritmo es correcto/válido si resuelve el problema computacio-

nal para el cual fue diseñado. Para cada entrada, produce la salida

deseada (correcta).

Forma manual de vericar la correctitud de un algoritmo:

1. Seleccionar un conjunto de datos de entrada DE

2. Ejecutar el algoritmo con DE

3. Vericar el resultado R

7/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

¾Cuántos DEs podemos pasarle a un algoritmo?

8/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

¾Cuántos DEs podemos pasarle a un algoritmo?

Cada DE dene una instancia del problema.

8/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Algoritmos

¾Cuántos DEs podemos pasarle a un algoritmo?

Cada DE dene una instancia del problema.

Un algoritmo es completo si garantiza retornar una respuesta correc-

ta para cualquier entrada DE, o si la respuesta no existe, lo informa.

8/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Un algoritmo completo es ecaz, pero podría no poder ejecutarse

en algún dispositivo computacional, ya que podría demandar mas

recursos de cómputo o de memoria de los que se disponen.

9/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Un algoritmo completo es ecaz, pero podría no poder ejecutarse

en algún dispositivo computacional, ya que podría demandar mas

recursos de cómputo o de memoria de los que se disponen.

Un problema puede tener muchos algoritmos que lo resuelven, nos

interesaría aquel que: ¾se ejecuta más rápido?, ¾usa menos recursos

de cómputo (menos instrucciones que ejecutar)?, ¾usa menos recur-

sos de memoria?

9/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Un algoritmo completo es ecaz, pero podría no poder ejecutarse

en algún dispositivo computacional, ya que podría demandar mas

recursos de cómputo o de memoria de los que se disponen.

Un problema puede tener muchos algoritmos que lo resuelven, nos

interesaría aquel que: ¾se ejecuta más rápido?, ¾usa menos recursos

de cómputo (menos instrucciones que ejecutar)?, ¾usa menos recur-

sos de memoria?

Analizar un algoritmo → determinar qué tan bueno es (qué

tan rápido, que tan costoso en instrucciones o memoria)

9/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

El análisis de algoritmos consiste en determinar la complejidad de

la solución propuesta (algoritmo) a un problema dado.

¾Cuántas operaciones básicas requiere el algoritmo? > costo en

tiempo
¾Cuánta memoria requiere el algoritmo? > costo en espacio

10/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. ¾Los algoritmos creados e implementados se pueden ejecutar

en una computadora en tiempo razonable? Complejidad

temporal

2. ¾La cantidad de memoria requerida por los algoritmos creados

está disponible en la computadora donde se ejecutarán los

mismos? Complejidad espacial

11/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. ¾Los algoritmos creados e implementados se pueden ejecutar

en una computadora en tiempo razonable? Complejidad

temporal

2. ¾La cantidad de memoria requerida por los algoritmos creados

está disponible en la computadora donde se ejecutarán los

mismos? Complejidad espacial

La respuesta a estas preguntas, intuitivamente, depende del tamaño

de la entrada o instancia del problema.

11/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. ¾Cómo calculamos la complejidad temporal de un

algoritmo?

12/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. ¾Cómo calculamos la complejidad temporal de un

algoritmo?

1.1 Determinar en el algoritmo el número de pasos

1.2 Determinar en el algoritmo el número de operaciones básicas
1.3 Determinar en el algoritmo el número de ciclos de procesador

12/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. ¾Cómo calculamos la complejidad temporal de un

algoritmo?

1.1 Determinar en el algoritmo el número de pasos

1.2 Determinar en el algoritmo el número de operaciones básicas
1.3 Determinar en el algoritmo el número de ciclos de procesador
2. ¾y la complejidad espacial?

12/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. ¾Cómo calculamos la complejidad temporal de un

algoritmo?

1.1 Determinar en el algoritmo el número de pasos

1.2 Determinar en el algoritmo el número de operaciones básicas
1.3 Determinar en el algoritmo el número de ciclos de procesador
2. ¾y la complejidad espacial?
2.1 Determinar número de variables (arreglos, estructuras, listas)
2.2 Determinar el espacio utilizado por las variables en el algoritmo
2.3 Determinar cantidad de datos almacenados en disco

12/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

La complejidad (espacial y temporal) de un algoritmo se calculan en

función de los datos de entrada (instancia del problema)

13/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Un algoritmo debería ser el mejor posible: se ejecuta más rápido

que otros algoritmos que resuelven el mismo problema o usa

menos recursos de memoria. Es decir, el algoritmo debería tener la

complejidad más baja posible.

¾Cuándo un algoritmo es mejor que otro?, ¾Cómo lo sabe-

mos?

14/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. Complejidad temporal
1.1 En el análisis de algoritmos, no se mide y hace una
comparación de tiempos de ejecución entre algoritmos para
determinar cuál es el mejor.

15/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. Complejidad temporal
1.1 En el análisis de algoritmos, no se mide y hace una
comparación de tiempos de ejecución entre algoritmos para
determinar cuál es el mejor.
1.2 Aunque es un indicativo, el tiempo de ejecución es variable,
depende de muchos factores.

15/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. Complejidad temporal
1.1 En el análisis de algoritmos, no se mide y hace una
comparación de tiempos de ejecución entre algoritmos para
determinar cuál es el mejor.
1.2 Aunque es un indicativo, el tiempo de ejecución es variable,
depende de muchos factores.
1.3 El análisis es más formal, matemático, independiente del
dispositivo donde se ejecute el algoritmo.

15/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. Complejidad temporal
1.1 En el análisis de algoritmos, no se mide y hace una
comparación de tiempos de ejecución entre algoritmos para
determinar cuál es el mejor.
1.2 Aunque es un indicativo, el tiempo de ejecución es variable,
depende de muchos factores.
1.3 El análisis es más formal, matemático, independiente del
dispositivo donde se ejecute el algoritmo.
El análisis de algoritmos se enfoca generalmente en deteminar la

complejidad temporal de los algoritmos. A menos que se exprese

lo contrario, por complejidad de un algoritmo nos referiremos a su

complejidad temporal.
15/56 Programación Básica - Análisis de Algoritmos Junio 2022
 Análisis de algoritmos

Considere el problema de cálculo de una exponenciación: Dado n

un número entero y x un número real, calcular xn . Considere
los siguientes dos algoritmos que resuelven el problema anterior:
Input: n, x Input: n, x
Output: xn Output: xn
1 if n>0 then 1 if n es par then

2 regresar x ∗ xn−1 2 regresar (xn/2 )2

3 end 3 end

4 else 4 else

5 regresar 1 5 regresar x ∗ (xn/2 )2

6 end 6 end

16/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Considere el problema de cálculo de una exponenciación: Dado n

un número entero y x un número real, calcular xn . Considere
los siguientes dos algoritmos que resuelven el problema anterior:
Input: n, x Input: n, x
Output: xn Output: xn
1 if n>0 then 1 if n es par then

2 regresar x ∗ xn−1 2 regresar (xn/2 )2

3 end 3 end

4 else 4 else

5 regresar 1 5 regresar x ∗ (xn/2 )2

6 end 6 end

¾Cuál de los dos algoritmos es mejor? Dependerá de la complejidad

de cada uno

16/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

La Complejidad Algorítmica es una estimación del número de pa-

sos en un algoritmo para realizar un cálculo dado, dependiendo del

tamaño de los datos de entrada.

17/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Análisis de la Complejidad de un Algoritmo

1. Sea n el tamaño de la entrada del algoritmo

2. Considerar las operaciones básicas como una unidad de pasos de
ejecución (asignaciones, cálculos aritméticos, etc). Estas
operaciones, en cualquier arquitectura de cómputo tendrán un costo
aunque variable, nito. Dicha variación debido a la tecnología usada
estará determinada por una constante.
3. Contabilizar el número de operaciones básicas en función de n

18/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Análisis teórico de la Complejidad Temporal: Ejemplo

Considere el siguiente problema. Dado un arreglo A de n elemen-

tos, y un valor v , determinar si v ∈ A.
1. Proponga un algoritmo que resuelva el problema anterior y
contabilice cuántas operaciones requiere, en función de n.

19/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Análisis teórico de la Complejidad Temporal: Ejemplo

Considere el siguiente problema. Dado un arreglo A de n elemen-

tos, y un valor v , determinar si v ∈ A.
1. Proponga un algoritmo que resuelva el problema anterior y
contabilice cuántas operaciones requiere, en función de n.
buscar(A, n, v ){
for each (v1 ∈ A)
if (v1 == v ) return true
return false
}

19/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Análisis teórico de la Complejidad Temporal: Ejemplo

Considere el siguiente problema. Dado un arreglo A de n elemen-

tos, y un valor v , determinar si v ∈ A.
1. Sea T (n) el número de operaciones del algoritmo A, en función del tamaño de

los datos de entrada n.

2. T (n) = n es la complejidad del algoritmo buscar(A, n, v).

3. Si gracamos T (n) para diferentes valores de A, ¾qué tipo de gráca

obtenemos?

20/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Análisis teórico de la Complejidad Temporal: Ejemplo

Considere el siguiente problema. Dado un arreglo A de n elemen-

tos, y un valor v , determinar si v ∈ A.
1. Sea T (n) el número de operaciones del algoritmo A, en función del tamaño de

los datos de entrada n.

2. T (n) = n es la complejidad del algoritmo buscar(A, n, v).

3. Si gracamos T (n) para diferentes valores de A, ¾qué tipo de gráca

obtenemos?

4. La gráca es una LÍNEA con pendiente 45 grados.

5. El comportamiento LINEAL del algoritmo buscar(A, n, v) será el mismo,

independientemente de la velocidad de procesador del equipo donde se ejecute

el algoritmo.

20/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Piense y de un ejemplo de un algoritmo, cuya número de operaciones

T (n) = 1, esto es, independientemente del tamaño de la entrada, el

número de operaciones sea 1.

21/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Piense y de un ejemplo de un algoritmo, cuya número de operaciones

T (n) = 1, esto es, independientemente del tamaño de la entrada, el

número de operaciones sea 1.

encontrarCentro(A, n){
return A[n/2]
}

21/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Piense y de un ejemplo de un algoritmo, cuya número de operaciones

T (n) = 1, esto es, independientemente del tamaño de la entrada, el

número de operaciones sea 1.

encontrarCentro(A, n){
return A[n/2]
}

La complejidad de encontrarCentro(A, n) es T (n) = 1. ¾Cómo se

vería la gráca de T (n) para distintos valores de n?

21/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Piense y de un ejemplo de un algoritmo, cuya número de operaciones

T (n) = 1, esto es, independientemente del tamaño de la entrada, el

número de operaciones sea 1.

encontrarCentro(A, n){
return A[n/2]
}

La complejidad de encontrarCentro(A, n) es T (n) = 1. ¾Cómo se

vería la gráca de T (n) para distintos valores de n?

En este caso que T (n) = 1, decimos que el algoritmo tiene una

complejidad CONSTANTE. Lo mismo pasaría si T (n) = c, para

cualquier otro número de operaciones constante c.

21/56 Programación Básica - Análisis de Algoritmos Junio 2022
 Análisis de algoritmos

Si un algoritmo A realiza TA (n) = c1 y un algoritmo B realiza

TB (n) = c2 , ambos algoritmos tendrán una complejidad CONS-

TANTE, ¾porqué?

22/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Si un algoritmo A realiza TA (n) = c1 y un algoritmo B realiza

TB (n) = c2 , ambos algoritmos tendrán una complejidad CONS-

TANTE, ¾porqué?

Distintos algoritmos pertenecen a la misma familia de acuerdo con

su complejidad, medida por el número de operaciones que realizan.

Una de estas familias es la de complejidad CONSTANTE.

22/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Si un algoritmo A realiza TA (n) = c1 y un algoritmo B realiza

TB (n) = c2 , ambos algoritmos tendrán una complejidad CONS-

TANTE, ¾porqué?

Distintos algoritmos pertenecen a la misma familia de acuerdo con

su complejidad, medida por el número de operaciones que realizan.

Una de estas familias es la de complejidad CONSTANTE.

A parte de la familia de algoritmos con complejidad CONSTANTE,

existen otras, como la complejidad LINEAL.

22/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

Ejemplo:

23/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. arrayMax(A,n) se ejecuta en T (n) = 6n − 1 operaciones

básicas, en el peor caso.

24/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. arrayMax(A,n) se ejecuta en T (n) = 6n − 1 operaciones

básicas, en el peor caso.

1.1 Si gracamos la función T (n) para distintos valores de n,

¾cómo se verá la gráca?.

24/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. arrayMax(A,n) se ejecuta en T (n) = 6n − 1 operaciones

básicas, en el peor caso.

1.1 Si gracamos la función T (n) para distintos valores de n,

¾cómo se verá la gráca?.
1.2 El tasa de crecimiento del tiempo de ejecución dado por T (n)
es una propiedad intrínseca del algoritmo arrayMax(),
independientemente de la computadora donde se ejecute.

24/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Análisis de algoritmos

1. arrayMax(A,n) se ejecuta en T (n) = 6n − 1 operaciones

básicas, en el peor caso.

1.1 Si gracamos la función T (n) para distintos valores de n,

¾cómo se verá la gráca?.
1.2 El tasa de crecimiento del tiempo de ejecución dado por T (n)
es una propiedad intrínseca del algoritmo arrayMax(),
independientemente de la computadora donde se ejecute.
2. ¾La complejidad del algoritmo buscar(A,n,v) es la misma

que la del algoritmo arrayMax(A,n)?

24/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

La Complejidad Algorítmica se mide mediante notación asintó-

tica (cuál es el comportamiento del crecimiento de la función para

diversos valores de n, cuando n tiende a ser muy grande).

25/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

La Complejidad Algorítmica se mide mediante notación asintó-

tica (cuál es el comportamiento del crecimiento de la función para

diversos valores de n, cuando n tiende a ser muy grande).

En otras palabras, la notación asintótica indica qué tan rápido crece

T (n) respecto a n.

25/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

La Complejidad Algorítmica se mide mediante notación asintó-

tica (cuál es el comportamiento del crecimiento de la función para

diversos valores de n, cuando n tiende a ser muy grande).

En otras palabras, la notación asintótica indica qué tan rápido crece

T (n) respecto a n.

Permite agrupar funciones T (n) asociadas a complejidad de algorit-

mos dentro de una misma clase (CONSTANTE, LINEAL, etc) .

25/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

¾Qué función crece más rápido?

a) T (n) = 100n + 300

2
b) T (n) = 6n + 10

26/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

¾Qué función crece más rápido?

27/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

¾Qué función crece más rápido asintóticamente?

28/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

1. La notación asintótica (tambien conocida como notacion

"big-o"), o Big-O , es una notación matemática que permite

caracterizar un algoritmo en términos de una función de

referencia (logarítmica, lineal, cuadrática, polinomial,

exponencial), en términos del tamaño de la entrada.

2. Indica el comportamiento límite de una función.

29/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

1. La notación asintótica (tambien conocida como notacion

"big-o"), o Big-O , es una notación matemática que permite

caracterizar un algoritmo en términos de una función de

referencia (logarítmica, lineal, cuadrática, polinomial,

exponencial), en términos del tamaño de la entrada.

2. Indica el comportamiento límite de una función.

Dada una función g(n), denotamos por O(g(n)) a la familia de fun-

ciones que dieren de g(n) por una constante.

29/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Dada una función g(n), denotamos por O(g(n)) a la familia de fun-

ciones que dieren de g(n) por una constante.

Ejemplo:

1. T1 (n) = 1, T1 (n) = 2, T3 (n) = 10, T4 (n) = 200,...., todas ellas

son funciones que dieren en una constante de la función

g(n) = 1. T1 , T2 , T3 , T4 , todas ellas están en O(1).

30/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Dada una función g(n), denotamos por O(g(n)) a la familia de fun-

ciones que dieren de g(n) por una constante.

Ejemplo:

1. T1 (n) = 1, T1 (n) = 2, T3 (n) = 10, T4 (n) = 200,...., todas ellas

son funciones que dieren en una constante de la función

g(n) = 1. T1 , T2 , T3 , T4 , todas ellas están en O(1).

2. T1 (n) = 20n, T2 (n) = 2n, T3 (n) = 3n, ..., todas ellas son

funciones que dieren en una constante de la función

g(n) = n. Todas ellas están en O(n).

30/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Dada una función g(n), denotamos por O(g(n)) a la familia de fun-

ciones que dieren de g(n) por una constante.

Ejemplo:

1. El número de pasos para ejecutar search(A,n,v) es

T (n) = n en el peor caso. ¾T (n) ∈ O(n)?

31/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Dada una función g(n), denotamos por O(g(n)) a la familia de fun-

ciones que dieren de g(n) por una constante.

Ejemplo:

1. El número de pasos para ejecutar search(A,n,v) es

T (n) = n en el peor caso. ¾T (n) ∈ O(n)?

2. El número de pasos para ejecutar maxArray(A,n) es

T (n) = 6n − 1 en el peor caso. ¾T (n) ∈ O(n)?

31/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Dada una función g(n), denotamos por O(g(n)) a la familia de fun-

ciones que dieren de g(n) por una constante.

Ejemplo:

1. El número de pasos para ejecutar search(A,n,v) es

T (n) = n en el peor caso. ¾T (n) ∈ O(n)?

2. El número de pasos para ejecutar maxArray(A,n) es

T (n) = 6n − 1 en el peor caso. ¾T (n) ∈ O(n)?

¾Tienen search(A,n,v) y maxArray(A,n) la misma complejidad?

31/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Dada T (n) el número de operaciones básicas para ejecutar un algo-

ritmo A, decimos que A tiene complejidad g(n), o que T (n) está en

O(g(n)) si:

Existe una constante positiva c y un entero positivo n0 tal que

T (n) ≤ cg(n), ∀n ≤ n0 .

32/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Existe una constante positiva c y un entero positivo n0 tal que f (n) ≤

cg(n), ∀n ≤ n0 .

Se lee:

1.  T (n) es de orden g(n)

2. T (n) no crece más rápido que g(n)

33/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Suponga que después de diseñar el algoritmo A, se realiza su análisis,

y resulta que el número de operaciones básicas que dicho algoritmo

realiza es T (n) = 2n + 10.

¾Cuál es la complejidad algorítmica de A?, ¾Cómo la determinamos?.

34/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Suponga que después de diseñar el algoritmo A, se realiza su análisis,

y resulta que el número de operaciones básicas que dicho algoritmo

realiza es T (n) = 2n + 10.

¾Cuál es la complejidad algorítmica de A?, ¾Cómo la determinamos?.
R = Encontrar g(n), tal que T (n) ∈ O(g(n)).

34/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Suponga que después de diseñar el algoritmo A, se realiza su análisis,

y resulta que el número de operaciones básicas que dicho algoritmo

realiza es T (n) = 2n + 10.

¾Cuál es la complejidad algorítmica de A?, ¾Cómo la determinamos?.
R = Encontrar g(n), tal que T (n) ∈ O(g(n)).

Por el grado del polinomio, la hipótesis es que T (n) es O(n), es decir

suponemos que g(n) = n. ¾Cómo lo demostramos?

34/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Suponga que después de diseñar el algoritmo A, se realiza su análisis,

y resulta que el número de operaciones básicas que dicho algoritmo

realiza es T (n) = 2n + 10.

¾Cuál es la complejidad algorítmica de A?, ¾Cómo la determinamos?.
R = Encontrar g(n), tal que T (n) ∈ O(g(n)).

Por el grado del polinomio, la hipótesis es que T (n) es O(n), es decir

suponemos que g(n) = n. ¾Cómo lo demostramos?

Debemos encontrar c y n0 tal que (2n + 10) ≤ cn, ∀n ≥ n0

15 minutos para encontrar la respuesta.

34/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

2n + 10 ≤ cn
10 ≤ c(n − 2)
10/(n − 2) ≤ c
Tomamos c = 3, n0 = 10

35/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = n2 . Demuestre que T (n) NO es O(n).

15 minutos para resolverlo.

36/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

n2 ≤ cn
n≤c
No existe una constante que cumpla con la condición anterior. Por

lo tanto, no hay forma en la que n2 no crezca más rápido que n.

37/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = 2n3 + n + 1

2
¾T (n) está en O(n )?

38/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = 2n3 + n + 1

2
¾T (n) está en O(n )?
3
¾T (n) está en O(n )?

Resuelva, determine c y n0

38/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = 2n3 + n + 1

T (n) es O(n3 ). Usa c = 3 y n0 = 2.

39/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

La notación Big O permite denir un límite superior al crecimiento

de una función.

Establece un orden entre familias de funciones.

1 ≤ log n ≤ n ≤ n log n ≤ n2 ≤ n3 ≤ ... ≤ np ≤ an ≤ nn

40/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

La notación Big O establece un orden entre familias de funciones.

1 ≤ log n ≤ n ≤ n log n ≤ n2 ≤ n3 ≤ ... ≤ np ≤ an ≤ nn

41/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

La notación Big O establece un orden entre familias de funciones.

1 ≤ log n ≤ n ≤ n log n ≤ n2 ≤ n3 ≤ ... ≤ np ≤ an ≤ nn

Si T (n) es O(n), T (n) también es O(n2 ) u O(2n ), pero no es O(1)

u O(log n).

42/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

La notación Big O establece un orden entre familias de funciones.

1 ≤ log n ≤ n ≤ n log n ≤ n2 ≤ n3 ≤ ... ≤ np ≤ an ≤ nn

Si T (n) es O(n), T (n) también es O(n2 ) u O(2n ), pero no es O(1)

u O(log n).

Cuando se determina la complejidad algoritmica, se debe determinar

la familia de funciones más pequeña que satisface T (n) ∈ O(g(n)).

42/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = 2n3 + n + 1

¾Cuáles de las siguientes armaciones es correcta y cuál es falsa?

1. T (n) es O(2n )

43/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = 2n3 + n + 1

¾Cuáles de las siguientes armaciones es correcta y cuál es falsa?

1. T (n) es O(2n )
2. T (n) es O(n)

43/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = 2n3 + n + 1

¾Cuáles de las siguientes armaciones es correcta y cuál es falsa?

1. T (n) es O(2n )
2. T (n) es O(n)
3. T (n) es O(n4 )

43/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = 2n3 + n + 1

¾Cuáles de las siguientes armaciones es correcta y cuál es falsa?

1. T (n) es O(2n )
2. T (n) es O(n)
3. T (n) es O(n4 )
¾Cual es la complejidad de T (n)?

43/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = 2n3 + n + 1

¾Cuáles de las siguientes armaciones es correcta y cuál es falsa?

1. T (n) es O(2n )
2. T (n) es O(n)
3. T (n) es O(n4 )
¾Cual es la complejidad de T (n)?
T (n) 3
es O(n ).

Se pueden descartar los términos de grado inferior y las constantes.

43/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

SeaT (n) = 10n3 + 4n2 + 1000

¾Cuál es la complejidad de T (n)?

44/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T (n) = 10n3 + 4n2 + 1000

¾Cuál es la complejidad de T (n)?

T (n) es O(n3 ).

44/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T1 (n) = 10n3 + 4n2 + 1000 el número de pasos del Algoritmo

A para resolver P
3
Sea T2 (n) = 2n + n + 1 el número de pasos del Algoritmo B que

también resuelve P

¾Cuál algoritmo es mejor?

45/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea T1 (n) = 10n3 + 4n2 + 1000 el número de pasos del Algoritmo

A para resolver P
3
Sea T2 (n) = 2n + n + 1 el número de pasos del Algoritmo B que

también resuelve P

¾Cuál algoritmo es mejor?

Ambos T1 (n), T2 (n) son O(n3 ), tienen la misma complejidad.

45/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea A(n) el algoritmo con la siguiente descripción.

A(n){
f1 (n)
f2 (n)
f3 (n)
for (i = 1 to n)
f1 (n)
}

46/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea A(n) el algoritmo con la siguiente descripción.

A(n){
f1 (n)
f2 (n)
f3 (n)
for (i = 1 to n)
f1 (n)
}
Sea T (n) A(n), T (n) en O(g(n)).
el número de pasos para ejecutar
2
Suponga que la complejidad de f1 (n) es O(n ), f2 (n) es O(1), f3 (n)

es O(n).

46/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Sea A(n) el algoritmo con la siguiente descripción.

A(n){
f1 (n)
f2 (n)
f3 (n)
for (i = 1 to n)
f1 (n)
}
Sea T (n) A(n), T (n) en O(g(n)).
el número de pasos para ejecutar
2
Suponga que la complejidad de f1 (n) es O(n ), f2 (n) es O(1), f3 (n)

es O(n).

¾Quién es g(n)?
46/56 Programación Básica - Análisis de Algoritmos Junio 2022
 Complejidad algorítmica

Sea T (n) la estimación de operaciones básicas del Algoritmo A:

47/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad algorítmica

Expectativa del tiempo de ejecución de un algoritmo de acuerdo a

su complejidad:

48/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Ejercicios

¾Cuál es la complejidad del siguiente algoritmo?

1 int findMaxElement ( int [] array ) {

int max = array [0];
3 for ( int i = 0; i < array . length ; i ++) {
if ( array [ i ] > max ) {
5 max = array [ i ];
}
7 }
return max ;
9 }

Listing 1: Algoritmo 1

49/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Ejercicios

¾Cuál es la complejidad del siguiente algoritmo?

long findInversions ( int [] array ) {

3 long inversions = 0;
for ( int i = 0; i < array . length ; i ++)
5 for ( int j = i + 1; j < array . length ; i ++)
if ( array [ i ] > array [ j ])
7 inversions ++;
return inversions ;
9 }

Listing 2: Algoritmo 2

50/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Ejercicios

¾Cuál es la complejidad del siguiente algoritmo?

int sum3 ( int n ) {

3 decimal sum = 0;
for ( int a = 0; a < n ; a ++)
5 for ( int b = 0; b < n ; b ++)
for ( int c = 0; c < n ; c ++)
7 sum += a * b * c ;
return sum ;
9 }

Listing 3: Algoritmo 3

51/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Ejercicios

¾Cuál es la complejidad del siguiente algoritmo?

int calculate ( int n ) {

3 int result = 0;
for ( int i = 0; i < (1 < < n ) ; i ++)
5 result += i ;
return result ;
7 }

Listing 4: Algoritmo 4

52/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Ejercicios

¾Cuál es la complejidad del siguiente algoritmo?

decimal Fibonacci ( int n ) {

3 if ( n == 0)
return 1;
5 else if ( n == 1)
return 1;
7 else
return Fibonacci ( n - 1) + Fibonacci ( n - 2) ;
9 }

Listing 5: Algoritmo 5

53/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Operaciones más comunes en programación sobre colecciones:

Colección Acceso Agregar Encontrar Eliminar

Array (T []) O(1) O(n) O(n) O(n)
List
(LinkedList<T>) O(n) O(1) O(n) O(n)
Map
(HashMap<T>) O(1) O(1) O(1) O(1)
(TreeMap<T>) O(logn) O(logn) O(logn) O(logn)

54/56 Programación Básica - Análisis de Algoritmos Junio 2022

 Complejidad en algoritmos de ordenamiento:

Algoritmo Complejidad Complejidad

en tiempo en espacio
2
Quicksort O(n ) O(log n)
Mergesort O(n log n) O(n)
Timsort O(n log n) O(n)
Heapsort O(n log n) O(1)
Bubble Sort O(n2 ) O(1)
Insertion Sort O(n2 ) O(1)
Selection Sort O(n2 ) O(1)
Tree Sort O(n2 ) O(n)
Shell Sort O(n log n2 ) O(1)
Bucket Sort O(n2 ) O(n)
55/56 Programación Básica - Análisis de Algoritmos Junio 2022
 FIN
DEL
CURSO

56/56 Programación Básica - Análisis de Algoritmos Junio 2022