Unidad 3 - emilioone05/Analisis_Algoritmos_utpl GitHub Wiki
🔍 Unidad 3: Evaluación de la Eficiencia de Algoritmos
misterioso(n)
✳️ Análisis del Procedimiento El propósito de este procedimiento es analizar el crecimiento del número de instrucciones ejecutadas con respecto al tamaño de la entrada n
. A continuación se estudia el comportamiento del algoritmo utilizando principios de análisis de complejidad computacional.
🧩 Algoritmo Propuesto
procedure misterioso(n: integer)
var
contador, i, j, k : integer
begin
contador := 0
for i := 1 to n - 1 do
for j := i + 1 to n do
for k := 1 to j do
contador := contador + 1
end
📚 Descripción Detallada
El algoritmo cuenta cuántas veces se ejecuta una instrucción elemental: contador := contador + 1
. A primera vista, parece un algoritmo cúbico por la presencia de tres bucles anidados. No obstante, un análisis más profundo permite calcular con mayor precisión la cantidad total de iteraciones.
- El ciclo externo (
i
) se ejecuta desde1
hastan - 1
, es decir,(n - 1)
veces. - El ciclo medio (
j
) recorre desdei + 1
hastan
, que varía dinámicamente según el valor dei
. - El ciclo interno (
k
) se ejecuta desde1
hastaj
, que también varía dinámicamente.
🧮 Cálculo Teórico del Número de Operaciones
La cantidad total de veces que se incrementa contador
se puede modelar como:
[ T(n) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \sum_{k=1}^{j} 1 = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} j ]
Esta suma no se puede simplificar directamente, pero se puede acotar asintóticamente. El valor máximo de j
es n
, y i
va desde 1
hasta n-1
. Por lo tanto:
[ T(n) \in \Theta(n^3) ]
🧪 Ejecución Manual (Prueba de Escritorio para n = 5)
i |
j |
Rango de k |
Iteraciones | Contador Total |
---|---|---|---|---|
1 | 2 | 1 → 2 | 2 | 2 |
1 | 3 | 1 → 3 | 3 | 5 |
1 | 4 | 1 → 4 | 4 | 9 |
1 | 5 | 1 → 5 | 5 | 14 |
2 | 3 | 1 → 3 | 3 | 17 |
2 | 4 | 1 → 4 | 4 | 21 |
2 | 5 | 1 → 5 | 5 | 26 |
3 | 4 | 1 → 4 | 4 | 30 |
3 | 5 | 1 → 5 | 5 | 35 |
4 | 5 | 1 → 5 | 5 | 40 |
🔚 Total acumulado de iteraciones: 40
🧠 Conclusión del Análisis
Este procedimiento tiene una complejidad cúbica en función del tamaño de entrada n
. Aunque la lógica parece simple, el comportamiento del tercer bucle en función del segundo lo convierte en un excelente ejemplo de algoritmo con crecimiento polinomial elevado.
prod_mat
)
🧮 Análisis del Procedimiento de Multiplicación de Matrices (La multiplicación de matrices es una operación fundamental en áreas como el álgebra lineal, inteligencia artificial y simulaciones científicas. A continuación se describe un procedimiento clásico para multiplicar dos matrices cuadradas de tamaño n × n
.
🧾 Algoritmo de Multiplicación
procedure prod_mat(n: integer)
var
i, j, k: integer
begin
for i := 1 to n do
for j := 1 to n do begin
C[i, j] := 0
for k := 1 to n do
C[i, j] := C[i, j] + A[i, k] * B[k, j]
end
end
🔍 Análisis del Comportamiento
Este algoritmo ejecuta tres bucles anidados, cada uno con un rango de 1
a n
. El número total de operaciones básicas (multiplicaciones
y sumas
) está dado por:
[ T(n) = n \cdot n \cdot n = n^3 ]
🔁 Complejidad temporal: O(n³)
📦 Complejidad espacial: O(n²) (matriz resultante)
📌 Conclusiones Generales
Procedimiento | Tipo de Operación | Complejidad Temporal |
---|---|---|
misterioso(n) |
Conteo condicional triple | O(n³) |
prod_mat(n) |
Multiplicación de matrices | O(n³) |
Ambos algoritmos, aunque diferentes en naturaleza, comparten una estructura cúbica. Sin embargo, en contextos reales, su comportamiento puede diferir significativamente debido al tipo de operaciones internas (sumas vs multiplicaciones).