Sesión 03_Mg Orleans Gálvez Tapia(1)

Vista previa del material en texto

ANÁLISIS DE ALGORITMOS Y 
ESTRATEGIAS DE PROGRAMACIÓN
Docente: 
Mg. Gálvez Tapia Orleans Moisés
CIP. 171497
UNIDAD 1:
LA COMPLEJIDAD ALGORÍTMICA Y 
PRINCIPALES ESTRATEGIAS DE 
PROGRAMACIÓN
SEMANA 03: Complejidad algorítmica, Notación O grande
¿Qué entiende por 
complejidad 
algorítmica?
SABERES PREVIOS
AGENDA:
1. Matrices en Python (ejercicio pendiente)
2. Propiedades de los algoritmos
3. Tiempo de ejecución de un algoritmos T(n)
4. Operaciones Elementales
5. Cálculo del tiempo de ejecución en estructuras de control 
secuenciales, condicionales y repetitivas.
6. Notación O grande.
7. Ejercicio propuesto
8. Referencias Bibliográficas
LOGRO DE LA SESIÓN
Al término de la clase, el estudiante calcula la complejidad 
de un algoritmo usando el tiempo de ejecución del mismo, 
mostrando dominio técnico del lenguaje Python y una 
lógica coherente.
MATRICES EN PYTHON
Desarrollar un programa en Python que permita:
i. Pedir al usuario que ingrese el número de filas
y columnas.
ii. Crear y poblar una matriz de enteros pidiendo
cada elemento al usuario. Si se trata de una
matriz cuadrada debe almacenar en un
vector los elementos de la diagonal principal
y en otro los elementos de la diagonal
secundaria.
iii. Mostrar los elementos de la matriz y los
elementos de las diagonales
iv. Mostrar el mayor elemento almacenado en la
matriz
Desarrollar un programa en Python que permita:
i. Pedir al usuario que ingrese el número de filas
y columnas.
ii. Crear y poblar una matriz de enteros pidiendo
cada elemento al usuario. Si se trata de una
matriz cuadrada debe almacenar en un
vector los elementos de la diagonal principal
y en otro los elementos de la diagonal
secundaria.
iii. Mostrar los elementos de la matriz y los
elementos de las diagonales
iv. Mostrar el mayor elemento almacenado en la
matriz
[0] [1] [2] [3] [4]
[0] m[0][0] m[0][1] m[0][2] m[0][3] m[0][4]
[1] m[1][0] m[1][1] m[1][2] m[1][3] m[1][4]
[2] m[2][0] m[2][1] m[2][2] m[2][3] m[2][4]
[3] m[3][0] m[3][1] m[3][2] m[3][3] m[3][4]
[4] m[4][0] m[4][1] m[4][2] m[4][3] m[4][4]
m:
Los elementos de la
diagonal principal son
aquellos donde:
i = j
MATRICES EN PYTHON
Desarrollar un programa en Python que permita:
i. Pedir al usuario que ingrese el número de filas
y columnas.
ii. Crear y poblar una matriz de enteros pidiendo
cada elemento al usuario. Si se trata de una
matriz cuadrada debe almacenar en un
vector los elementos de la diagonal principal
y en otro los elementos de la diagonal
secundaria.
iii. Mostrar los elementos de la matriz y los
elementos de las diagonales
iv. Mostrar el mayor elemento almacenado en la
matriz
[0] [1] [2] [3] [4]
[0] m[0][0] m[0][1] m[0][2] m[0][3] m[0][4]
[1] m[1][0] m[1][1] m[1][2] m[1][3] m[1][4]
[2] m[2][0] m[2][1] m[2][2] m[2][3] m[2][4]
[3] m[3][0] m[3][1] m[3][2] m[3][3] m[3][4]
[4] m[4][0] m[4][1] m[4][2] m[4][3] m[4][4]
m:
Los elementos de la
diagonal secundaria
son aquellos donde:
i+j = len(m) - 1
MATRICES EN PYTHON
Salida del programa:
MATRICES EN PYTHON
López et al. (2009) definen algoritmo como “un conjunto de pasos que, ejecutados de la
manera correcta, permiten obtener un resultado (en un tiempo acotado)”.
ALGORITMO
Problema
Métodos y/o
Procedimientos
Figura : Se diseña un algoritmo para resolver un problema
resuelven
(Secuencia finita 
de instrucciones)
o Tiene definidas las entradas que se requieren, así
como las salidas que se deben producir.
o Es preciso
o Es determinista
o Es finito
o Es efectivo
PROPIEDADES DE UN ALGORITMO
ANÁLISIS DE ALGORITMOS
Implementación I
AlgoritmoImplementación II
Implementación III
Figura: Un algoritmo puede tener varias 
implementaciones
Algoritmo I
ProblemaAlgoritmo II
Algoritmo III
Figura: Pueden existir varios algoritmos para 
resolver el mismo problema
“El análisis de algoritmos pretende descubrir si estos son o no eficaces. Establece además una
comparación entre los mismos con el fin de saber cuál es el más eficiente, aunque cada uno de los
algoritmos de estudio sirva para resolver el mismo problema”.
[Villalpando, 2003].
EFICIENCIA DE UN ALGORITMO
Los aspectos a tomar en cuenta para estudiar la eficiencia de un algoritmo son el tiempo que se emplea
en resolver el problema y la cantidad de recursos de memoria que ocupa.
Para saber qué tan eficiente es un algoritmo hacemos las preguntas:
o ¿Cuánto tiempo ocupa?
o ¿Cuánta memoria ocupa?
Nos interesa el tiempo de ejecución de 
un algoritmo.
TIEMPO DE EJECUCIÓN T(n)
Al tiempo que tarda un algoritmo para resolver un problema se le llama T(n), donde n es el tamaño de
los datos de entrada. Es decir, T(n) depende del tamaño de los datos de entrada.
El tamaño de la entrada es el número de componentes sobre los que se va a ejecutar el algoritmo.
Estos pueden ser por ejemplo: el número de elementos de un arreglo que se va a ordenar, o el tamaño de
las matrices que se van a multiplicar.
TIEMPO DE EJECUCIÓN T(n)
Lo que importa es la forma que tiene la función T(n)
para saber cómo cambia la medida del tiempo de
ejecución en función del tamaño del problema, es decir,
con T(n) podemos saber si el tiempo aumenta poco o
aumenta mucho cuando la n crece.
El tiempo de ejecución T(n) de un algoritmo para una
entrada de tamaño n no debe medirse en segundos,
milisegundos, etc., porque T(n) debe ser independiente
del tipo de computadora en el que corre.
OPERACIONES ELEMENTALES
Para medir T(n) usamos el número de operaciones elementales. Una operación
elemental puede ser:
o Operación aritmética.
o Asignación a una variable.
o Llamada a una función.
o Retorno de una función.
o Comparaciones lógicas
o Acceso a una estructura (arreglo, matriz, lista ligada…).
Se le llama tiempo de ejecución, no al tiempo físico, sino al número de operaciones
elementales que se llevan a cabo en el algoritmo.
ANÁLISIS DE OPERACIONES ELEMENTALES
1 OE (asignación)
1 OE (asignación)
1 OE (salida)
1 OE (entrada)
4 OE (1 acceso al vector + 2 comparaciones + 1 AND)
2 OE (incremento + asignación)
2 OE (acceso + comparación)
1 OE (salida)
1 OE (salida)
1 OE (retorno)
CÁLCULO DE T(n) EN EL MEJOR CASO
1 OE (asignación)
1 OE (asignación)
1 OE (salida)
1 OE (entrada)
2 OE (1 acceso al vector + 1 comparación)
2 OE (acceso + comparación)
1 OE (salida)
1 OE (salida)
1 OE (retorno)
T(𝑛)= 𝟒 + 𝟐 + 𝟐 + 𝟐 = 10
Figura: Análisis de operaciones elementales en el mejor caso, es decir, cuando se encuentra inmediatamente el número buscado
buscado = 1
1 OE (asignación)
1 OE (asignación)
1 OE (salida)
1 OE (entrada)
4 OE (1 acceso al vector + 2 comparaciones + 1 AND)
2 OE (incremento + asignación)
2 OE (acceso + comparación)
1 OE (salida)
1 OE (salida)
1 OE (retorno)
T(𝑛)= 𝟒 + 𝒋=𝟎
𝒏−𝟏 𝟒 + 𝟐 + 𝟒 + 𝟐 + 𝟐
Figura: Análisis de operaciones elementales, en el peor caso, es decir, cuando no se encuentra el elemento buscado
CÁLCULO DE T(n) EN EL PEOR CASO
T(𝑛)= 𝟒 + 𝒋=𝟎
𝒏−𝟏 𝟒 + 𝟐 + 𝟒 + 𝟐 +2
T(𝑛)= 𝟒 + 𝒋=𝟏
𝒏 𝟒 + 𝟐 + 𝟒 + 𝟐 + 𝟐
T(𝑛)= 𝟒 + 𝒋=𝟏
𝒏 𝟔 + 𝟒 + 𝟐 + 2
T(𝑛)= 𝟏𝟐 + 𝒋=𝟏
𝒏 𝟔
T(𝑛)= 𝟏𝟐 + 6n
 
𝑗=1
𝑛
𝑘 = 𝑘. 𝑛
El ciclo while se ejecuta n veces, donde n es el tamaño del arreglo, en este caso 9.
Además, una vez que se ejecuta este ciclo 9 veces, se hacen otras 4 operaciones
elementales para verificar que se terminó la búsqueda.
Para n = 9 T(n) es 66.
CÁLCULO DE T(n) EN EL PEOR CASO
Consideraciones importantes:
o Normalmente cuando se calcula el número de OE, se tiene en cuenta el
pero caso.
o Consideramos que el tiempo de una OE es, por definición, de orden 1.
o El tiempo de ejecución de una secuencia consecutiva de instrucciones se
calcula sumando los tiempos de ejecución de cada una de las
instrucciones.
CÁLCULO DE T(n) EN EL PEOR CASO
EQUIVALENCIA ENTRE LOS CICLOS WHILE Y FOR
1 OE 1 OE 2 OE: i=i+1 
4 OE: 
1 asignación + 1 comparación +
2 (incremento y asignación)
# OE de instrucciones
1 OE 
1 OE 
2 OE:i=i+1 
# OE de instrucciones
Forma equivalente del for: 
Tiempo en el peor de los casos:
T(𝑛)= 𝟏 + 𝟏 + 𝒊=𝟎
𝒏−𝟏 #𝑶𝑬 𝒊𝒏𝒔𝒕𝒓𝒖𝒄𝒄𝒊𝒐𝒏𝒆𝒔 + 𝟐 + 𝟏
El primer 1 es el de la asignación, el segundo 1 es el de la última comparación (cuando ya no se
cumple la condición) y al final hay que sumar el resultado de multiplicar n veces el número de OE
de las instrucciones dentro del ciclo más 2 OE del incremento más 1 OE de la comparación, es
decir n( #OE de instrucciones +2+1).
for (int i = 0; i < n; i++){
instrucciones...
}
int i = 0;
while(i < n){
instrucciones...
i = i+1;
}
EJERCICIO 01
Identificar las OE y calcular T(𝑛) del siguiente algoritmo: 
Solución:
T(𝑛)= 𝟑 + 𝟏 + 𝟏 + 𝒊=𝟏
𝒏 𝟑 + 𝟐 + 𝟏 = 𝟓 + 𝟔𝒏
NOTACIÓN O(grande)
Ejemplo 01. Determinar la complejidad de la siguiente función:
Aplicamos las siguientes propiedades: 
a) Dadas dos funciones f(n) y g(n), se dirá que f(n) es mas compleja que g(n) cuando:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= ∞
b) Asimismo, se determinará que f(n) es menos compleja que g(n) cuando:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= 0
c) Por ultimo, se afirmará que f(n) es equivalente a g(n) cuando:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k, siendo k≠0 y k≠∞
𝑓(𝑛) = 100 𝑛2 + 10𝑛 + 1
Ejemplo 01. Determinar la complejidad de la siguiente función: 𝑓(𝑛) = 100 𝑛2 + 10𝑛 + 1
𝑔(𝑛)
Aplicamos la propiedad c:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k, siendo k≠0 y k≠∞
lim
𝑛→∞
100𝑛2+10𝑛 + 1
𝑛2
= lim
𝑛→∞
100 +
10
𝑛
+
1
𝑛2
= 𝟏𝟎𝟎
Podemos concluir que: O(100𝑛2 + 10𝑛 + 1 ) = O(𝑛2)
Es decir:
El orden de la función 𝑓(𝑛) = 100 𝑛2 + 10𝑛 + 1 es 𝒏𝟐
= lim
𝑛→∞
100 + lim
𝑛→∞
10
𝑛
+ lim
𝑛→∞
10
𝑛2
= 100 +
10
∞
+
1
∞2
= 100 + 0 + 0
o El límite de una función constante siempre
da como resultado la propia constante.
o Cualquier número dividido entre ±∞ da
como resultado 0.
o ∞2 = ∞
NOTACIÓN O(grande)
Ejemplo 02. Determinar la complejidad de la siguiente función: 𝑓(𝑛) = 5 𝑛3 + 2𝑛
𝑔(𝑛)
Aplicamos la propiedad c:
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k, siendo k≠0 y k≠∞
lim
𝑛→∞
5𝑛3+2𝑛
𝑛3
= lim
𝑛→∞
5 +
2
𝑛2
= 𝟓
Podemos concluir que: O(5𝑛3 +2𝑛) = O(𝑛3)
Es decir:
El orden de la función 𝑓(𝑛) = 5 𝑛3 +2𝑛 es 𝒏𝟑
= lim
𝑛→∞
5 + lim
𝑛→∞
2
𝑛2
= 5 +
2
∞2
= 5 + 0
o El límite de una función constante siempre
da como resultado la propia constante.
o Cualquier número dividido entre ±∞ da
como resultado 0.
o ∞2 = ∞
NOTACIÓN O(grande)
𝑆𝑖 lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k, dependiendo del valor de k, tenemos:
i. Prueba de Identidad: 
Si k≠0 y k≠∞, entonces O(f) = O(g)
ii. Prueba de inclusión:
Si k=0, entonces O(f) ⊂ O(g)
iii. Prueba de exclusión:
Si k = ±∞, entonces O(f) ⊃ O(g)
Indicar si la siguiente afirmación es cierta: 
Ejemplo 03: O( 𝑛2) ⊂ O( 𝑛3)
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k
lim
𝑛→∞
𝑛2
𝑛3
= lim
𝑛→∞
1
𝑛
= 
1
∞
= 0
Entonces, por la propiedad (ii) la proposición es cierta.
𝑓(𝑛) 𝑔(𝑛)
NOTACIÓN O(grande)
𝑆𝑖 lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k, dependiendo del valor de k, tenemos:
i. Prueba de Identidad: 
Si k≠0 y k≠∞, entonces O(f) = O(g)
ii. Prueba de inclusión:
Si k=0, entonces O(f) ⊂ O(g)
iii. Prueba de exclusión:
Si k = ±∞, entonces O(f) ⊃ O(g)
Ejemplo 04: O( 𝑛3) ⊂ O( 𝑛2)
Indicar si la afirmación anterior es cierta: 
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k
lim
𝑛→∞
𝑛3
𝑛2
= lim
𝑛→∞
𝑛 =∞
Por la propiedad (iii) se tiene que O( 𝑛3) ⊃ O( 𝑛2), 
por lo tanto la proposición original es falsa.
NOTACIÓN O(grande)
𝑆𝑖 lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k, dependiendo del valor de k, tenemos:
i. Prueba de Identidad: 
Si k≠0 y k≠∞, entonces O(f) = O(g)
ii. Prueba de inclusión:
Si k=0, entonces O(f) ⊂ O(g)
iii. Prueba de exclusión:
Si k = ±∞, entonces O(f) ⊃ O(g)
Indicar si la siguiente afirmación es cierta: 
Ejemplo 05: O(2𝑛+1) = O(2𝑛)
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k
lim
𝑛→∞
2𝑛+1
2𝑛
= lim
𝑛→∞
2𝑛.2
2𝑛
=2
Por la propiedad (i) la proposición es cierta.
NOTACIÓN O(grande)
𝑆𝑖 lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k, dependiendo del valor de k, tenemos:
i. Prueba de Identidad: 
Si k≠0 y k≠∞, entonces O(f) = O(g)
ii. Prueba de inclusión:
Si k=0, entonces O(f) ⊂ O(g)
iii. Prueba de exclusión:
Si k = ±∞, entonces O(f) ⊃ O(g)
Indicar si la siguiente afirmación es cierta: 
Ejemplo 06: O( 𝑛 + 1 !) ⊂ O(𝑛!)
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k
lim
𝑛→∞
𝑛+1 !
𝑛!
= lim
𝑛→∞
𝑛+1 𝑛!
𝑛!
= lim
𝑛→∞
(𝑛 + 1) = ∞+1 = ∞
Por la propiedad (iii) se tiene que O( 𝑛 + 1 !) ⊃ O(𝑛!)
por lo tanto la proposición original es falsa.
NOTACIÓN O(grande)
𝑆𝑖 lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k, dependiendo del valor de k, tenemos:
i. Prueba de Identidad: 
Si k≠0 y k≠∞, entonces O(f) = O(g)
ii. Prueba de inclusión:
Si k=0, entonces O(f) ⊂ O(g)
iii. Prueba de exclusión:
Si k = ±∞, entonces O(f) ⊃ O(g)
Indicar si la siguiente afirmación es cierta: 
Ejemplo 07: O(3𝑛) ⊂ O(2𝑛)
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= k
lim
𝑛→∞
3𝑛
2𝑛
= lim
𝑛→∞
(
3
2
)𝑛 = (
3
2
)∞ =∞
Por la propiedad (iii) se tiene que O(3𝑛) ⊃ O(2𝑛), por 
lo tanto la proposición original es falsa.
Aplicamos:
𝑘∞=∞ y 𝑘−∞=0 (si k>1)
𝑘∞=0 y 𝑘−∞=∞ (si 0<k<1)
NOTACIÓN O(grande)
EJERCICIO PROPUESTO
Elaborar un programa en Phyton que permita identificar y mostrar los números primos 
almacenados dentro de una matriz.
REFERENCIAS BIBLIOGRÁFICAS
REFERENCIA ENLACE 
Una introducción a las matemáticas para el 
análisis y diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/35059
Manual de algorítmica: recursividad, complejidad y 
diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/56561
Introducción práctica a la programación con 
Python 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/124259
Criptografía sin secretos con Python https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/106497
ACM UVA Online http://uva.onlinejudge.org/
ACM ICPC Competition https://icpc.global/compete/preparation
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
http://uva.onlinejudge.org/
https://icpc.global/compete/preparation