INSTITUTO POLITÉCNICO NACIONAL

Escuela Superior de Ingeniería Mecánica y Eléctrica

Unidad Culhuacán

“Exámen Práctico”

Grupo:

5CV13

Materia:

Análisis de Algoritmos

Alumno:

Sánchez Chávez Oswaldo

Profesor:

Pilar Resendiz Colin

1
1.- Análisis de Código

Código para analizar:

Identificación de Operaciones Básicas

1. Inicialización de total: O(1)

2. Iteración sobre el arreglo arr: La operación for num in arr es una iteración
que recorrerá cada elemento del arreglo. Si el tamaño de arr es n, esta
operación se ejecutará n veces.

3. Suma: La operación total += num también se ejecuta nnn veces, ya que

se realiza en cada iteración.

Paso 2: Contar el Número de Operaciones

• La inicialización de total se cuenta como O(1).

• La iteración a través del arreglo y la suma totalizan:

o Iteración: O(n)

o Suma: O(n)

Paso 3: Complejidad Temporal

Sumando todas las operaciones, tenemos:

• La complejidad total es:

T(n)=O(1)+O(n)+O(n)=O(n)

2
Por lo tanto, la complejidad temporal del algoritmo suma_arreglo es O(n).

Suposiciones Adicionales

• Se asume que la operación de suma es O(1) y que el arreglo no es

extremadamente grande, lo que podría afectar el rendimiento por
limitaciones de memoria.

• Se asume que arr es un arreglo que contiene nnn elementos.

3
2.- Algoritmo 1: Búsqueda Lineal

La búsqueda lineal es un enfoque simple que consiste en recorrer el arreglo de

manera secuencial.

Análisis de Complejidad

• Complejidad Temporal:

o En el peor caso, el elemento buscado está al final del arreglo o no

está presente.

o Se necesitan n comparaciones, donde n es el tamaño del arreglo.

o Complejidad: O(n)

4
Algoritmo 2: Búsqueda Binaria

La búsqueda binaria es un enfoque más eficiente, pero requiere que el arreglo

esté ordenado. Divide el arreglo en mitades para reducir el espacio de
búsqueda.

5
Análisis de Complejidad

• Complejidad Temporal:

o Cada iteración reduce el tamaño del problema a la mitad.

o Se realizan logaritmos en base 2 de n comparaciones hasta

encontrar el elemento o agotar las posibilidades.

o Complejidad: O(log(n))

Escenarios de Eficiencia

1. Tamaño Pequeño del Arreglo:

o Si el arreglo es pequeño (por ejemplo, menos de 10 elementos), la

diferencia de tiempo entre ambos algoritmos es mínima. La
búsqueda lineal puede ser más rápida debido a su simplicidad.

2. Arreglos Grandes:

6
 o Para arreglos grandes, la búsqueda binaria es mucho más
eficiente. Con el crecimiento del tamaño del arreglo, el número de
comparaciones en búsqueda binaria crece lentamente en
comparación con la búsqueda lineal.

3. Arreglo No Ordenado:

o Si el arreglo no está ordenado, solo se puede utilizar la búsqueda

lineal, lo que lleva a un tiempo de ejecución de O(n)O(n)O(n).

4. Frecuencia de Búsquedas:

o Si se requieren múltiples búsquedas en el mismo arreglo, primero

ordenar el arreglo (si no está ordenado) y luego utilizar la
búsqueda binaria para cada búsqueda será más eficiente a largo
plazo.

Ejemplo de Algoritmo Ineficiente:

Análisis de Complejidad

• Complejidad Temporal:

o El algoritmo tiene dos bucles anidados, cada uno iterando sobre el

arreglo.

o En el peor caso, se realizan O(n2) comparaciones, donde nnn es el

tamaño del arreglo.

7
Propuesta de Optimización:

Análisis de Complejidad de la Versión Optimizada

• Complejidad Temporal:

o El algoritmo recorre el arreglo una sola vez, lo que da como

resultado O(n).

o Las operaciones de inserción y búsqueda en un conjunto (hash

set) tienen, en promedio, O(1)

Análisis de recursividad:

Dada una función recursiva, dibuja el árbol de recursión correspondiente y utiliza

este árbol para

determinar la complejidad temporal de la función..

8
Análisis de Recursividad

Paso 1: Dibujo del Árbol de Recursión

Para calcular factorial, el árbol de recursión sería el siguiente:

Este árbol se puede visualizar como sigue:

9
 • En la raíz, se inicia con factorial(4)factorial.

• Cada nodo representa una llamada recursiva y su cálculo.

• La hoja más baja, factorial(0), es el caso base que retorna 1.

Paso 2: Contar el Número de Llamadas

1. Profundidad del árbol: Cada llamada recursiva disminuye el valor de n en

1. Por lo tanto, para factorial(n)factorial(n)factorial(n), el árbol tendrá n+1
niveles (desde n hasta 000).

2. Número de nodos: Cada nivel genera un nodo. Por ejemplo, para n=4:

o Llamadas:
factorial(0)factorial(4)→factorial(3)→factorial(2)→factorial(1)→fact
orial(0)

o Esto produce un total de n+1n nodos.

Paso 3: Complejidad Temporal

• Coste por Llamada: Cada llamada a la función realiza una multiplicación

y una comparación, lo que se considera O(1).

• Número Total de Llamadas: Para factorial(n)factorial(n)factorial(n), hay

n+1n llamadas.

La complejidad temporal total es:

T(n)=O(1)⋅(n+1)=O(n)

Comparción de algoritmos:

Se te presentan varios algoritmos que resuelven el mismo problema. Compara

su complejidad

temporal y discute las ventajas y desventajas de cada uno en diferentes

situaciones.

10
Vamos a comparar tres algoritmos diferentes para resolver el mismo problema:
la búsqueda de un elemento en un arreglo. Los algoritmos que consideraremos
son:

1. Búsqueda Lineal

2. Búsqueda Binaria

3. Búsqueda mediante Hashing

1. Búsqueda Lineal

Descripción

La búsqueda lineal recorre cada elemento del arreglo uno a uno hasta
encontrar el objetivo o llegar al final.

Complejidad Temporal

• Peor caso: O(n), donde nnn es el tamaño del arreglo.

• Mejor caso: O(1) (si el elemento está en la primera posición).

Ventajas

• Simple de implementar y entender.

• No requiere que el arreglo esté ordenado.

Desventajas

• Ineficiente para arreglos grandes.

• No aprovecha ninguna estructura de datos adicional.

2. Búsqueda Binaria

Descripción

La búsqueda binaria se aplica a arreglos ordenados. Divide el arreglo a la mitad

en cada iteración y descarta la mitad donde no puede estar el elemento.

Complejidad Temporal

• Peor caso: O(\log n).

• Mejor caso: O(1) (si el elemento está en la mitad).

11
Ventajas

• Mucho más eficiente que la búsqueda lineal en arreglos grandes.

• El tiempo de búsqueda disminuye significativamente con el tamaño del

arreglo.

Desventajas

• Solo se puede aplicar a arreglos ordenados. Si el arreglo no está

ordenado, primero hay que ordenarlo, lo que tiene una complejidad de
O(nlogn).

• Más complejo de implementar que la búsqueda lineal.

3. Búsqueda mediante Hashing

Descripción

Utiliza una tabla hash para almacenar elementos. Busca el elemento en la tabla
hash, donde la búsqueda y la inserción son operaciones rápidas.

Complejidad Temporal

• Peor caso: O(n) (en caso de colisiones, aunque se espera que sea O(1).

• Mejor caso: O(1).

Ventajas

• Búsquedas extremadamente rápidas en el caso promedio.

• Ideal para aplicaciones donde se requieren muchas búsquedas o

inserciones.

Desventajas

• Requiere espacio adicional para almacenar la tabla hash.

• La complejidad de la implementación es mayor.

• La gestión de colisiones puede complicar el rendimiento.

Implementación y medición: Implementa un algoritmo en un lenguaje de

programación y mide su tiempo de ejecución para diferentes tamaños de

12
entrada. Compara los resultados obtenidos con el análisis teórico de la
complejidad.

13
Análisis de la Implementación

1. Función de Búsqueda Binaria: Implementa el algoritmo que busca un

elemento en un arreglo ordenado.

2. Medición del Tiempo: Utiliza la biblioteca <chrono> para medir el tiempo

que tarda en ejecutarse la búsqueda.

3. Arreglo de Prueba: Se crea un arreglo ordenado de enteros desde 0 hasta

taman~o−1.

Problemas abiertos: Investiga un problema algorítmico sin una solución

conocida y discute las posibles estrategias para abordarlo. ¿Cuál crees que
sería la complejidad temporal óptima para este problema?

Problema Abierto: El Problema del Viajante (Traveling Salesman Problem, TSP)

Descripción del Problema

El problema del viajante consiste en encontrar la ruta más corta que permite a
un vendedor visitar un conjunto de ciudades, pasando por cada una
exactamente una vez y regresando a la ciudad de origen. Este problema es un
clásico en la teoría de la computación y la optimización combinatoria.

14
Complejidad del Problema

TSP es conocido por ser un problema NP-duro. Esto significa que no se conoce
un algoritmo eficiente que resuelva todos los casos en tiempo polinómico. La
complejidad temporal del enfoque más simple, que utiliza fuerza bruta, es O(n!),
donde nnn es el número de ciudades, ya que se deben considerar todas las
permutaciones posibles de las ciudades.

Estrategias para Abordar el Problema

1. Fuerza Bruta

o Enumerar todas las permutaciones de ciudades y calcular la

distancia total para cada una.

o Complejidad: O(n!).

o Ventajas: Sencillo de implementar.

o Desventajas: Inviable para grandes valores de n.

2. Programación Dinámica

o Utilizar la técnica de programación dinámica para almacenar

resultados de subproblemas.

o El algoritmo de Held-Karp es un enfoque clásico que reduce la

complejidad a O(n2⋅2n).

o Ventajas: Significativamente más eficiente que la fuerza bruta.

o Desventajas: Aún ineficiente para valores grandes de n (por

ejemplo, más de 20-30 ciudades).

3. Algoritmos Aproximados

o Utilizar heurísticas como el algoritmo del vecino más cercano, la

búsqueda tabú o algoritmos genéticos para encontrar soluciones
"suficientemente buenas" en un tiempo razonable.

o Ventajas: Práctico para instancias grandes, puede encontrar

soluciones rápidamente.

o Desventajas: No garantiza encontrar la solución óptima.

15
 4. Métodos de Optimización

o Emplear algoritmos de optimización, como Simulated Annealing o

Particle Swarm Optimization, para buscar soluciones cercanas a la
óptima.

o Ventajas: Puede funcionar bien en la práctica y es flexible.

o Desventajas: Requiere ajustes de parámetros y puede ser difícil de

implementar.

5. Búsqueda Local

o Aplicar técnicas de búsqueda local como el "2-opt" o "3-opt", que

mejoran una solución inicial intercambiando rutas.

o Ventajas: Simple y puede ser muy efectivo.

o Desventajas: Puede quedar atrapado en óptimos locales.

Complejidad Temporal Óptima

La complejidad temporal óptima teórica para resolver TSP en todos los casos es
aún desconocida, pero cualquier algoritmo que garantice encontrar la solución
óptima tendrá al menos O(n!) en el peor caso, dado que se necesita explorar
todas las permutaciones.

En la práctica, se busca una combinación de enfoques que permita soluciones

rápidas y efectivas, aceptando que no siempre se alcanzará la solución óptima,
especialmente para grandes instancias del problema.

Análisis amortizado: Analiza la complejidad amortizada de una operación en

una estructura de datos dinámica (por ejemplo, un arreglo dinámico).

Un arreglo dinámico es una estructura de datos que permite el

almacenamiento de elementos de forma que su tamaño puede crecer y
decrecer según sea necesario. En lenguajes como C++ y Java, los arreglos

16
dinámicos son utilizados comúnmente, y su implementación puede incluir
operaciones como inserciones, eliminaciones y redimensionamiento.

Operación: Inserción en un Arreglo Dinámico

La operación principal a analizar es la inserción de un elemento en un arreglo

dinámico.

Proceso de Inserción

1. Caso Normal:

o Si hay suficiente espacio en el arreglo (es decir, el tamaño actual

es menor que la capacidad del arreglo), simplemente se inserta el
nuevo elemento. Este es un tiempo constante, O(1).

2. Caso de Redimensionamiento:

o Si el arreglo está lleno, se necesita redimensionarlo. Generalmente,

se duplica la capacidad del arreglo. Esto implica:

▪ Crear un nuevo arreglo con el doble de capacidad.

▪ Copiar todos los elementos del arreglo original al nuevo.

▪ Insertar el nuevo elemento.

Este proceso de redimensionamiento tiene una complejidad de O(n), donde nnn

es el número de elementos en el arreglo original.

Análisis Amortizado

Para analizar la complejidad amortizada de las inserciones en un arreglo

dinámico, utilizamos el método de cuentas (también conocido como método
de potencial).

1. Costos de Inserción:

o Inserciones que no requieren redimensionamiento: O(1).

o Inserciones que requieren redimensionamiento: O(n).

2. Contabilidad:

o Supongamos que inicialmente el arreglo tiene una capacidad deC.

17
 o La primera vez que se llena el arreglo y se realiza una redimensión,
el costo es O(C) para copiar los elementos, además de la inserción.

o Sin embargo, cada elemento insertado también paga un pequeño

costo adicional para el futuro. Cuando un nuevo espacio se crea al
duplicar el tamaño, podemos considerar que el costo se
"distribuye" entre todas las inserciones.

3. Costo Amortizado:

o Cada elemento nuevo en el arreglo paga un costo de 111 por la

inserción directa, y un costo adicional cuando se necesita
redimensionar.

o En el largo plazo, se puede demostrar que el costo amortizado de

cada inserción es O(1).

Complejidad espacial: Además de la complejidad temporal, analiza la

complejidad espacial de los algoritmos anteriores. ¿Cómo afecta el uso de la
memoria al rendimiento del algoritmo?

La complejidad espacial se refiere a la cantidad de memoria que un algoritmo

utiliza en función del tamaño de su entrada. Es importante considerar la
complejidad espacial junto con la complejidad temporal, ya que el uso de
memoria puede afectar el rendimiento general del algoritmo.

Análisis del Arreglo Dinámico

1. Estructura de Datos:

o Un arreglo dinámico almacena sus elementos en un bloque de

memoria contigua. Al inicializar, se reserva una capacidad inicial C.

o Complejidad espacial inicial: O(C), donde C es la capacidad del

arreglo.

2. Redimensionamiento:

o Cuando se inserta un nuevo elemento y el arreglo está lleno, se

redimensiona. Este proceso implica:

18
 ▪ Crear un nuevo arreglo con el doble de la capacidad
anterior, 2C.

▪ Copiar los elementos del arreglo antiguo al nuevo.

o Complejidad espacial durante el redimensionamiento: O(2C)

temporalmente, ya que se necesita espacio para ambos arreglos
(el original y el nuevo).

3. Espacio Desperdiciado:

o A menudo, un arreglo dinámico tiene espacio extra que no se

utiliza. Esto se traduce en un factor de carga, que puede afectar la
eficiencia del uso de memoria.

o Un factor de carga bajo puede llevar a un uso ineficiente de la

memoria, mientras que un factor de carga alto puede aumentar la
probabilidad de redimensionamientos frecuentes.

Impacto del Uso de Memoria en el Rendimiento

1. Acceso a Memoria:

o Los arreglos permiten un acceso constante O(1) a sus elementos, lo

que es eficiente en términos de tiempo. Sin embargo, un mayor uso
de memoria puede causar más fallos de caché si el tamaño del
arreglo supera la memoria caché del sistema.

o Si un algoritmo requiere una gran cantidad de memoria, puede ser

más lento debido a estos fallos, a pesar de que la complejidad
temporal teórica sea favorable.

2. Uso de Espacio Adicional:

o Si un algoritmo utiliza estructuras adicionales (como arreglos

temporales durante la redimensión o copias), su complejidad
espacial se incrementa. Esto puede ser crítico en sistemas con
recursos limitados.

o Para aplicaciones en tiempo real o embebidas, un uso de memoria

excesivo puede llevar a problemas de rendimiento.

3. Balance entre Tiempo y Espacio:

19
 o A menudo, hay un trade-off entre el tiempo y el espacio. Algoritmos
que utilizan más memoria pueden tener una complejidad temporal
mejorada, y viceversa.

o Por ejemplo, un algoritmo que utiliza memoria adicional para

almacenar resultados intermedios (como la programación
dinámica) puede mejorar la velocidad a expensas de usar más
espacio.

Problemas del mundo real:

Identifica un problema del mundo real que pueda ser modelado y resuelto
utilizando algoritmos.

Propón un algoritmo eficiente para resolver este problema y analiza su

complejidad.

Descripción del Problema

En la logística y la distribución, las empresas deben optimizar las rutas de

entrega para minimizar costos de combustible, tiempo y recursos. Esto implica
encontrar la ruta más corta o más eficiente que un conjunto de vehículos debe
tomar para entregar paquetes a múltiples destinos. Este problema se puede
modelar como el Problema del Viajante (TSP), que busca la ruta más corta que
visita cada destino exactamente una vez y regresa al punto de partida.

Propuesta de Algoritmo: Algoritmo de Búsqueda Local (2-opt)

El algoritmo de 2-opt es un método heurístico que mejora una solución existente

para el TSP al eliminar cruces en la ruta. Funciona de la siguiente manera:

1. Inicio: Comienza con una solución inicial (ruta de entrega).

2. Intercambio: Para cada par de ciudades en la ruta, intercambia los

segmentos entre las dos ciudades.

3. Evaluación: Calcula el nuevo costo de la ruta. Si la nueva ruta es más

corta, se acepta el cambio.

4. Iteración: Repite el proceso hasta que no se pueden hacer más mejoras.

Complejidad del Algoritmo

20
 1. Construcción de la Ruta Inicial:

o La construcción de una ruta inicial puede ser O(n), donde n es el

número de destinos.

2. Mejoras con 2-opt:

o El algoritmo requiere O(n2) iteraciones para evaluar cada par de

ciudades.

o En cada iteración, el costo de la ruta se recalcula, lo que también

puede tomar O(n).

o Por lo tanto, el costo total del algoritmo de 2-opt es O(n3).

3. Complejidad Amortizada:

o Aunque el costo en el peor caso es O(n3), la naturaleza heurística

del algoritmo significa que, en la práctica, las mejoras se producen
rápidamente, y muchas instancias convergen a una solución
buena en menos iteraciones.

Análisis de Complejidad

• Complejidad Temporal: O(n3) para la implementación básica de 2-opt.

• Complejidad Espacial: O(n) para almacenar la ruta y los costos

asociados.

21
22
Guía para Resolver el Examen

Análisis de complejidad del algoritmo recursivo para calcular el factorial de un

número n:

Identificación de Operaciones Básicas

1. Comparaciones: if n == 0

2. Multiplicaciones: n * factorial(n-1)

3. Llamadas recursivas: factorial(n-1)

Conteo de Operaciones

• Comparaciones: Se realiza una comparación por cada llamada recursiva.

En total, hay n+1n + 1n+1 comparaciones (una por cada n y una más
cuando se llega a 0).

• Multiplicaciones: Hay n multiplicaciones, ya que se realiza una

multiplicación por cada llamada recursiva hasta llegar a 0.

• Llamadas recursivas: Se realizan n llamadas recursivas antes de alcanzar

el caso base.

Complejidad Temporal

Sumando todas las operaciones, tenemos:

• Comparaciones: O(n)

• Multiplicaciones: O(n)

• Llamadas recursivas: O(n)

Por lo tanto, la complejidad temporal total del algoritmo es O(n).

Diseño de Algoritmos

23
1. Enfoque Fuerza Bruta

La implementación de factorial que hemos visto es una fuerza bruta. Calcula el

factorial de nnn de manera directa y recursiva. Su complejidad es O(n)O(n)O(n).

2. Enfoque Iterativo

Podemos implementar el factorial de manera iterativa:

Complejidad Temporal: O(n) (un ciclo que se ejecuta n veces).

Comparación de Enfoques

• Fuerza Bruta (Recursiva):

o Ventajas: Código más limpio y fácil de entender.

o Desventajas: Mayor uso de memoria por las llamadas recursivas, lo

que puede llevar a un desbordamiento de pila para valores
grandes de n.

• Iterativa:

o Ventajas: Menor uso de memoria, ya que no hay pila de llamadas.

o Desventajas: Puede ser menos intuitivo para algunos problemas

más complejos.

Ambos enfoques tienen la misma complejidad temporal, pero el enfoque

iterativo es más eficiente en términos de memoria.

Optimización de Código

1. Evitar la Recursión: La versión iterativa evita problemas de

desbordamiento de pila y es más eficiente en memoria.

24
 2. Uso de Tablas: Para cálculos más grandes, se puede almacenar
resultados intermedios (programación dinámica).

Análisis de Recursividad

Para el factorial recursivo, el árbol de recursión se vería así:

Cada nivel del árbol tiene una profundidad de nnn, y hay nnn llamadas. Así que
el número total de nodos es nnn.

Complejidad Espacial

• Recursiva: O(n) debido a las llamadas en la pila.

• Iterativa: O(1) ya que solo utilizamos variables auxiliares.

25