Algoritmos y

Estructuras de
Datos

2025-1
Ingeniería de Sistemas de Información
Ingeniería de Software
Ciencia de Datos

Recurso didáctico.
2025

Universidad San Ignacio de Loyola - USIL

Docentes del curso

Esta presentación está bajo una licencia Creative Commons (BY-NC-ND 4.0). Al usar este contenido los usuarios aceptan
las condiciones de uso.
Atribución-NoComercial-SinDerivadas 4.0 Internacional
[Link]

Atribución — Debe dar crédito de manera adecuada, brindar un enlace a la licencia, e indicar si se han realizado
cambios. Puede hacerlo en cualquier forma razonable, pero no de forma tal que sugiera que usted o su uso tienen el
apoyo de la licenciante.
NoComercial — No puede hacer uso del material con propósitos comerciales.
SinDerivadas — Si remezcla, transforma o crea a partir del material, no podrá distribuir el material modificado.

Los términos empleados en este recurso y la presentación de los datos no implican toma alguna de posición de parte de
Usil. Las ideas y opiniones expresadas en el recurso son las de los autores, y no reflejan necesariamente el punto de vista
de Usil ni comprometen a la organización.

[Link]
Ingeniería de Sistemas de Información
Ingeniería de Software
Ciencia de Datos

MOMENTOS

Saberes
Innovación
(Skills and
(Innovation)
knowledges)

Utilidad Logros
(Utility) (Accomplishment )
Temas

Desarrollo

Conclusiones
Ingeniería de Sistemas de Información
Ingeniería de Software
Ciencia de Datos

MOMENTOS

Saberes
Innovación
(Skills and
(Innovation)
knowledges)

Utilidad Logros
(Utility) (Accomplishment )
Utility (Utilidad)
 Utility (Utilidad)

[Link]
Aprendizaje esperado.

Al finalizar la sesión, el estudiante aplicará los

conocimientos avanzados de programación para
la implementación de estructura de datos
lineales.
Ingeniería de Sistemas de Información
Ingeniería de Software
Ciencia de Datos

MOMENTOS

Saberes
Innovación
(Skills and
(Innovation)
knowledges)

Utilidad Logros
(Utility) (Accomplishment )
Skills and knowledges (Saberes)
Agenda.

• Conceptos de análisis de complejidad.

• El problema del acceso al disco.

• Formas de la complejidad algorítmica.

• Complejidad temporal.

• La notación BigO.

• Ejemplos de notación BigO.

• Conclusiones.
 Motivación.

"Solo me preguntaba cómo

estaban hechas las cosas."
Claude Shannon
Pensemos.

¿Podemos analizar los algoritmos

y hacerlos eficientes?
 Definiciones del Análisis de Complejidad.

Donald Knuth (2011):

Es el estudio de cuánto tiempo y espacio requiere un programa para hacer
su trabajo.

Jon Bentley (1999):

Es el estudio del tiempo y espacio requeridos por un algoritmo para completar su
tarea, así como su comportamiento asintótico cuando las entradas crecen.
destaca la importancia de comprender el rendimiento de los algoritmos a medida
que las entradas aumentan en tamaño.
Definiciones del Análisis de Complejidad.

Cormen, Leiserson, Rivest y Stein (2022):

Es el proceso de predecir el rendimiento relativo de diferentes algoritmos
para resolver un problema en función del tamaño de la entrada. Este
enfoque incluye tanto el análisis teórico como el experimental para evaluar
el rendimiento de los algoritmos

Richard Johnsonbaugh (2017):

Es el proceso de determinar la cantidad de tiempo y espacio requeridos para
resolver un problema en función del tamaño de la entrada, es esencial para
comprender el rendimiento y tomar decisiones sobre selección y diseño.
 Consolidando el Concepto.

Es el estudio de cuánto tiempo

y espacio requiere un
programa para hacer su
trabajo.

Donald Knuth
El problema del acceso al disco.

El problema del acceso al disco ha sido fundamental en

la evolución de los sistemas operativos, especialmente
en cómo se manejan los recursos de almacenamiento.
Gracias a autores como Tanenbaum, contamos con bases
teóricas sólidas para entender y diseñar soluciones que
optimicen el rendimiento del almacenamiento en los
sistemas modernos.
El problema del acceso al disco.

• La velocidad del procesador es muy superior

a la velocidad del disco.

• Se estima que se puede alcanzar unos 120

accesos al disco por segundo en un HDD a
7200 RPM.

• Esto generó un cuello de botella para el

procesamiento de la información.
El problema del acceso al disco.

Tipo SSD Interfaz Vel. Lectura Vel. Escritura

SATA III SSD SATA 6 Gbps ~500–550 MB/s ~450–520 MB/s

NVMe Gen 3 PCIe 3.0 ~3,000–3,500 MB/s ~2,500–3,000 MB/s

NVMe Gen 4 PCIe 4.0 ~5,000–7,000 MB/s ~4,000–6,000 MB/s

NVMe Gen 5 PCIe 5.0 ~10,000–14,000 MB/s ~10,000–12,000 MB/s

 Formas del Análisis de Complejidad.

Análisis de Complejidad Temporal

Evalúa la eficiencia de un algoritmo en términos de cuánto tiempo tarda en
ejecutarse en función del tamaño de la entrada.

Análisis de Complejidad Espacial

Evalúa la eficiencia de un algoritmo en términos de cuánta
memoria utiliza un algoritmo en función del tamaño de la entrada.
La Complejidad Temporal.

La complejidad temporal es un concepto fundamental en el

análisis de algoritmos que se refiere a la cantidad de tiempo
que un algoritmo tarda en ejecutarse en función del tamaño
de su entrada. Se utiliza para medir cuánto tiempo tardará
un algoritmo en ejecutarse en el peor de los casos o en
promedio, en función del tamaño de la entrada.
 Medición del Tiempo.

Peor de los Casos Mejor de los Casos

Se determina el peor tiempo de ejecución que Se determina el mejor tiempo de ejecución que
podemos tener con un determinado algoritmo. podemos tener con un determinado algoritmo.

Promedio

Caso Promedio
Proporciona una predicción sobre el tiempo de ejecución, a partir de
diferentes entradas de cantidades aleatorias de datos, estableciendo
un valor promedio.
Notación Asintótica.

Notation Big-O
O(g(n)) = {f(n): Existen
constantes positivas c Notation Theta (Ɵ)
y n0 donde
0 <=f(n) <= c*g(n) θ(g(n)) = {f(n): Existen constantes
Para todo n >= n0} positivas c1,c2 y n0
Donde

O 0 <=c1*g(n) <= f(n) <= c2*g(n)

para todo n >= n0}

Notation Omega (Ω) Ɵ

Ω
Ω(g(n)) = {f(n): Existen
constantes positivas c
y n0 donde
0 <= c*g(n) <= f(n)
para todo n >= n0}
 Notación Asintótica.

Notación BigO
Esta notación proporciona el límite superior estricto de la función dada. Generalmente está
representada por la notación f(n) = O(cg(n)).

O(g(n)) = { f(n): Existen constantes positivas c y

n0 donde 0 <= f(n) <= cg(n)
Para todo n >= n0 }
 Ejemplos de Notación Asintótica.

Usando Notación BigO:

Una forma de calcular el valor Big-O en un procedimiento que se ha escrito, es determinar qué línea
de código se ejecuta más veces en su función, dado el tamaño de entrada n .

Ejemplo 1:

En esta función, cada línea se ejecuta

1 exactamente una vez, y por la misma cantidad.
1 El valor mayor entre 1 y 1 es 1. Por lo tanto, la función se
determina como O(1)
Ejemplos de Notación Asintótica.

Usando Notación BigO:

Una forma de calcular el valor Big-O en un procedimiento que se ha escrito, es determinar qué línea
de código se ejecuta más veces en su función, dado el tamaño de entrada n .

Ejemplo 2:

1 En esta función, en la 3era línea ( sum += a[i]; ) se

ejecuta una vez para cada elemento en a , para un
n total de [Link] n veces.

1 Tenemos como tiempos de ejecución n + 2 = n

Por lo tanto, la función Big O es: O(n)
 Ejemplos de Notación Asintótica.

Usando Notación BigO:

Una forma de calcular el valor Big-O en un procedimiento que se ha escrito, es determinar qué línea
de código se ejecuta más veces en su función, dado el tamaño de entrada n .

Ejemplo 3:

n => O(n)
1
 Eficiencia

Una solución es eficiente si resuelve el problema dentro de sus limitaciones de recursos.

❑ Espacio (Estructura de datos)
❑ Tiempo(Algoritmos)
El costo de una solución es la cantidad de recursos que esta consume en tiempo y espacio.
Existen tres tipos generales de análisis de tiempo:
❑ Mejor caso, caso promedio y peor caso.
❑ Existen otros tipos de análisis, a los cuales no prestaremos atención.
Ejemplo

Después de realizar el análisis asintótico de dos algoritmos, h y k, obtuvimos las siguientes

fórmulas de tiempo en base al número de datos n:

n h(n) k(n)
h(n) = n − 12n + 20n + 110
0 110 5
k(n) = n + n + 5n + 5 1 119 12
 De 0 a 3 datos

100
Tiempo(ms)

80

60

40

20

0 0.5 1 1.5 2 2.5 3

Datos(n)
De 0 a 8 datos
De 0 a 100 datos
De 0 a 1000 datos
Notación big 0.

❑ El análisis detallado de tiempo nos permite determinar la diferencia de tiempos entre los algoritmos de
forma inmediata.
❑ Por esta razón surge la notación Big O.
❑ Big O representa el Peor caso.
❑ Nos permite evaluar los términos de upper bounds, es decir proporcional a lo máximo que podría demorar
un algoritmo.
Como realizar el calculo de BIG 0

❑ Borrar términos de orden menor.

❑ Borrar las constantes.

Ejemplos:

•( h(n) = n^3 - 12n^2 + 20n + 110 ) → ( h(n) = O(n^3) )

•( k(n) = n^3 + n^2 + 5n + 5 ) → ( k(n) = O(n^3) )
•( f(n) = 3n^3 + 90n^2 - 5n + 6046 ) → ( f(n) = O(n^3) )
Orden de los algoritmos
Análisis de algoritmos

Asumir que la cantidad de datos a procesar es un número grande.

¿Qué contar?
❑ Operaciones de comparación
❑ Operaciones aritméticas
❑ Copiado de datos
❑ Asignaciones
❑ Tener conocimiento matemático
 Ejemplo de análisis de algoritmos

❑ Hallar el promedio de todos los números en el arreglo A

int sum = 0;
int n = length(A);
for (int i=0; i < n; i++) sum = sum + A[i];
double prom = sum / n;

Tiempo detallado: 4 + 6n + 2 = 6n + 6
Tiempo asintótico: O(n)
Reglas para calcular el tiempo

❑ Regla 1: sentencias secuenciales

❑ Cada operación y asignación tiene peso 1, funciones tienen su propio peso. Luego sumar
todo.

i = x; // --> 1
a = b + 2 * 3; // --> 3, 2 operaciones y una asignación
v[i] = v[0]; // --> 3, 2 accesos a arreglos y una asignación
b = binSearch(v, 10); // --> 1 + log 10, binSearch(v, n): log(n)
cout << b; // --> 1, 1 por cada operador <<

Tiempo detallado: 9 + log 10

Tiempo asintótico: 1 −→ constante!
 Reglas para calcular el tiempo

Regla 2: estructuras repetitivas

Identificar el número de iteraciones y multiplicar por la expresión interior

for (int i = 0; i < n; ++i) { // --> 1 + n(1 + INTERNA + 2)

sum = sum + A[i]; // --> 3
cout << sum; // --> 1
}

La inicialización del for cuenta por 1 (asignación)

el número de iteraciones del for (n en este caso) multiplica al valor obtenido en la parte interna del for y
se le agrega la expresión correspondiente a la condición de finalización (1 en nuestro caso) y la expresión
de incremento (2 en nuestro caso por el operador ++)
Tiempo detallado: 1 + n(1 + 3 + 1 + 2) = 1 + 7n
Tiempo asintótico: O(n) → Lineal
Reglas para calcular el tiempo

❑ Regla 3: repetitivas anidadas

for (int i = 0; i < n; ++i) { // --> 1 + n(1 + ___ + 2)

for (int k = 0; k < n / 2; k += 2) { // --> 1 + (n / 4)(2 + ___ + 2)
cout << i * k; // --> 2
}
}

El for interno solo realiza n/4 iteraciones ya que el límite superior es n/2 y k se incremente de 2 en 2.

Tiempo detallado: 1 + n(1 + 1 + n/4 (2 + 2 + 2) + 2) = 3𝑛2 /2+ 4n + 1

Tiempo asintótico: O(𝑛2 ) → Cuadrático
Reglas para calcular el tiempo

❑ Regla 4: repetitivas consecutivas

for (int i = 0; i < n; i++) { // --> 1 + n(1 + ___ + 2)

cout << i; // --> 1
}

for (int i = 0; i < 10000; ++i) { // --> 1 + 10000(1 + ___ + 2)

for (int k = 1; k < n; k *= 2) { // --> 1 + (log n)(1 + ___ + 2)
cout << i * k; // --> 2
}
}

Tiempo detallado:
1+n(1+1+2)+1+10000(1+1+(log n)(1+2+2)+2) = 4n+50000(log n)+40002
Tiempo asintótico: O(n)
Reglas para calcular el tiempo

Regla 5: if ... else

Escoger el máximo de la expresión verdadera y de la falsa

if (a > b) { // --> 1 + max(INTERNA IF, INTERNA ELSE)

a = binSearch(v, b); // --> 1 + log n
} else {
a = v[b]; // --> 2
}

Tiempo de expresión dentro del IF más el máximo valor entre la expresión obtenida del bloque IF y el
bloque ELSE.
Tiempo detallado: 1 + log n
Tiempo asintótico: O(log n)
Porque medir la eficiencia de un algoritmo

❑ Nos ayuda a entender la escalabilidad.

❑ Nos permite discernir entre lo que es posible y lo imposible.
❑ Es un lenguaje que nos permite predecir el comportamiento de un programa.
❑ La eficiencia es la "moneda" en la computación.
❑ ¡Buscar la rapidez de un programa es divertido! :D
❑ Debemos convertir esto en un hábito.
Programación genérica

Definición
Consiste en elaborar algoritmos en los que uno o más tipos de datos son especificados
posteriormente
Ventajas
En la mayoría de los casos permite disminuir la cantidad de código e incrementa la reusabilidad
de los algoritmos y tipos de datos abstractos. Es una característica presente en los principales
lenguajes de programación tipados.
C++ templates
C++ implementa la programación genérica con los Templates (plantillas en español), las cuales se
aplican a funciones y TDA definidos por el usuario. Los templates son construcciones usadas en
tiempo de compilación para construir familias de funciones, clases, estructuras, etc.
Considere las siguientes funciones

int sumaInt(int a, int b) { return a + b; }

float sumaFloat(float a, float b) { return a + b; }
double sumaDouble(double a, double b) { return a + b; }

int main() {
double x = 10.5, y = 20.75;
printf("Entero: %d\n", sumaInt(x, y));
printf(" Float: %f\n", sumaFloat(x, y));
printf("Double: %lf\n", sumaDouble(x, y));
return 0;
}

Salida:
Entero: 30
Float: 31.250000
Double: 31.250000
Simplificando un poco

double suma(double a, double b) {

return a + b;
}

int main() {
double x = 10.5, y = 20.75;
printf("Entero: %d\n", suma(x, y));
printf(" Float: %f\n", suma(x, y));
printf("Double: %lf\n", suma(x, y));
return 0;
}

Salida: podemos observar que el resultado entero no se muestra correctamente ¿porque?

Entero: 0
Float: 31.250000
Double: 31.250000
Solución con templates

template <typename T>

T suma(T a, T b) {
return a + b;
}

int main() {
double x = 10.5, y = 20.75;
printf("Entero: %d\n", suma<int>(x, y));
printf(" Float: %f\n", suma<float>(x, y));
printf("Double: %lf\n", suma<double>(x, y));
return 0;
}
Actividad 01:

Elaborar el seudocódigo y completar el código anterior en c++

La sintaxis

Los templates se definen anteponiendo la siguiente declaración:

template<typename T> o template<class T>

A continuación viene la declaración de la función, clase o estructura, por ejemplo:

template<typename T>
T sumar(T a, T b) {
return a + b;
}

Para llamar a esta función usamos la siguiente sintaxis:

cout << "La suma es: " << sumar<int>(x, y);

Clases con templates
template <typename T>
class CCuadrado {
T lado;
public:
CCuadrado(T lado);
~CCuadrado();
T Area();
};
template <typename T>
CCuadrado<T>::CCuadrado(T lado) {
this->lado = lado;
}
template <typename T>
CCuadrado<T>::~CCuadrado() {}
template <typename T>
T CCuadrado<T>::Area() {
return lado * lado;
}
Los templates son expandidos a funciones con tipos explícitos en tiempo de compilación cuando son usadas
con un tipo explícito. Por tal razón, para evitar problemas en tiempo de enlace (linking), se recomienda
implementar los métodos de clases template en el mismo archivo .h donde se declarará la clase template.
Actividad 02:

Elaborar el seudocódigo y completar el código anterior en c++

Selección de una estructura de datos

❑ Analizar el tipo de input posible en el problema.

❑ Analizar el problema para determinar las limitaciones de recursos a los que la solución debe
adaptarse.
❑ Determinar las operaciones básicas que deben ser soportadas. Evaluar las limitaciones de recursos
para cada una de estas operaciones.
❑ Seleccionar la estructura de datos que mejor se adecúe a estos requerimientos.
Nota: Generalmente buscamos la solución más simple .
Que debemos preguntarnos

❑ ¿Las inserciones se harán siempre en el primer registro, al final o en base a algún criterio?
❑ ¿Se puede eliminar la información?
❑ ¿Se procesan los datos en algún orden específico o se accede aleatoriamente?.
Estas interrogantes nos ayudan a eliminar algunas posibilidades.
Y las estructuras de datos …

❑ Cada Estructura de datos tiene costos y beneficios.

❑ Raramente una estructura de datos es mejor que otra en todas las circunstancias.
❑ Una estructura de datos requiere:
❑ Espacio para cada registro,
❑ tiempo para ejecutar cada operación básica y esfuerzo de programación .
Complejidad computacional

Según Romero-Riaño&Martinez-Toro(2020) indica que: La complejidad computacional desde

el enfoque de tiempo y espacio ha sido un tema de investigación que ha sido abordado por
diversos investigadores. La creación de mecanismos capaces de resolver problemas en tiempo
razonable y de algoritmos que minimizan el uso de memoria computacional, tema de
discusión relevante para los investigadores en el ámbito de la computación.
Complejidad temporal

Es el tiempo que le toma a un algoritmo resolver ciertos problemas.

A medida que los datos de entrada son más grandes es difícil definir el tiempo de ejecución en
la máquina, ya que dependerá también de los recursos de hardware y la cantidad de datos que
se tengan que procesar.
El coste de comparar dos operaciones de cadenas iguales depende de los recursos de la
máquina que los procesa.

[Link]
Complejidad temporal

❑ Corresponde al tiempo de ejecución de un algoritmo

❑ Variación del tiempo de ejecución dependiendo de los datos de entrada
❑ Es una medida relativa sin cantidad
❑ La complejidad temporal permite tener una idea del costo directo de un programa o
.
aplicación
Complejidad espacial

❑ El espacio de almacenamiento ocupado por el propio algoritmo de almacenamiento.

❑ El espacio de almacenamiento ocupado por los datos de entrada y salida del algoritmo
❑ El espacio de almacenamiento ocupado temporalmente por el algoritmo durante la
operación.
❑ Es la memoria que necesita para su funcionamiento.
❑ La complejidad espacial tiene mucho menos interés , cuando mencionemos
complejidad nos referimos a la complejidad temporal.
Tiempo de ejecución y tasa de crecimiento

❑ El tiempo de ejecución del algoritmo está en términos de la cantidad que deba

procesar , podemos deducir que, si la entrada crece , el tiempo de ejecución también
lo hará, a esto se le denomina como tasa de crecimiento.
❑ La tasa de crecimiento está dada por el número de operaciones que el algoritmo
realiza.
❑ La tasa de crecimiento está dada por el número de operaciones que el algoritmo
realiza.
Como se interpretan las funciones en la complejidad

Función que imprime los valores previos a n, se va a contar el número de operaciones,

pero en términos de n, recordar que una operación es una declaración y para el ciclo hay
que recordar que se toma en cuenta el número de iteraciones que se generan en el ciclo.
Complejidad II

• Función que imprime los valores previos a n, se va a contar el número de

operaciones, pero en términos de n,
• Recordar que una operación es una declaración y para el ciclo hay que recordar que
se toma en cuenta en número de iteraciones que se generan en el ciclo .
Como se obtiene el orden

✓ Cuente el número de operaciones del algoritmo y calcule su tasa de crecimiento

✓ Quédese con el termino de orden mayor , en el caso de existir, elimine:
✓ Los términos de orden menor
✓ Términos constantes
✓ Coeficientes
✓ Bases en caso de logaritmos
✓ Sea el algoritmo x que tiene la siguiente tasa de crecimiento : 3𝑛2 + 𝑛 + 2
✓ Se elimina las constantes, coeficientes y valores menores por tanto quedaría
O(𝑛2 ).
Innovation (Innovación)
 Desarrollo de Laboratorio.

• Ingresa al Canvas de nuestro curso.

• Ve a la sección de Innovation
(Innovación).

• Ingresa a la tarea de la esta semana (S04

– Tarea 4).
• Descarga la Guía de Laboratorio 4
(Innovación).
• Toma nota del desarrollo de los
ejercicios elaborados por el docente.
• Al finalizar sube tus anotaciones al
canvas.

• El desarrollo del Laboratorio es grupal,

solo el responsable del grupo debe
subir las anotaciones al Canvas.
Ingeniería de Sistemas de Información
Ingeniería de Software
Ciencia de Datos

MOMENTOS

Saberes
Innovación
(Skills and
(Innovation)
knowledges)

Utilidad Logros
(Utility) (Accomplishment )
Consultas.
Conclusiones
 Conclusiones.

0
A lo largo de esta sesión, comprendimos que la
complejidad computacional es una herramienta
fundamental para evaluar la eficiencia de los
algoritmos más allá de su funcionalidad. Aprendimos
a diferenciar entre complejidad temporal, que mide
el número de operaciones en función del tamaño de
entrada, y complejidad espacial, que evalúa el uso
de memoria adicional.
Además, exploramos la notación asintótica, en
especial la notación Big O, como un lenguaje
estándar para expresar el comportamiento de los
algoritmos cuando los datos crecen. Este enfoque
nos permite anticipar el rendimiento y tomar
decisiones informadas en el diseño y selección de
soluciones eficientes.
Referencias
 Referencias.

Fuente Capítulo
Malik, D. S. (2013). Estructuras de datos con C++ (2a. ed.). México: Cengage Learning. 1
Muchas gracias
por ser parte de
Este nuevo
capítulo USIL!