El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Ejercicios de Complejidad Temporal y Espacial

Siguiente ►
►

En esta sección, vamos a poner en práctica los conceptos aprendidos sobre la complejidad temporal y espacial de los algoritmos. A través de una serie de ejercicios, analizaremos y compararemos diferentes algoritmos para entender mejor cómo afectan la eficiencia del código.

Ejercicio 1: Análisis de Complejidad Temporal

Problema

Dado el siguiente fragmento de código, determina su complejidad temporal en términos de la notación Big-O.

def example_function(n):
    total = 0
    for i in range(n):
        for j in range(n):
            total += i * j
    return total

Solución

  1. Identificación de Bucles: El código tiene dos bucles anidados, cada uno de los cuales itera n veces.
  2. Cálculo de Iteraciones: El bucle externo se ejecuta n veces y por cada iteración del bucle externo, el bucle interno también se ejecuta n veces.
  3. Complejidad Temporal: La complejidad temporal es O(n) * O(n) = O(n^2).

Respuesta

La complejidad temporal del código es O(n^2).

Ejercicio 2: Análisis de Complejidad Espacial

Problema

Dado el siguiente fragmento de código, determina su complejidad espacial en términos de la notación Big-O.

def create_matrix(n):
    matrix = []
    for i in range(n):
        row = []
        for j in range(n):
            row.append(i * j)
        matrix.append(row)
    return matrix

Solución

  1. Identificación de Estructuras de Datos: El código crea una matriz de tamaño n x n.
  2. Cálculo de Espacio Utilizado: La matriz contiene n filas y cada fila contiene n elementos.
  3. Complejidad Espacial: La complejidad espacial es O(n) * O(n) = O(n^2).

Respuesta

La complejidad espacial del código es O(n^2).

Ejercicio 3: Comparación de Algoritmos

Problema

Compara la complejidad temporal de los siguientes dos algoritmos que calculan la suma de los primeros n números naturales.

Algoritmo A

def sum_natural_numbers_a(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

Algoritmo B

def sum_natural_numbers_b(n):
    return n * (n + 1) // 2

Solución

  1. Algoritmo A:

    • Identificación de Bucles: El bucle se ejecuta n veces.
    • Complejidad Temporal: La complejidad temporal es O(n).

  2. Algoritmo B:

    • Operaciones Constantes: El cálculo se realiza en una sola operación aritmética.
    • Complejidad Temporal: La complejidad temporal es O(1).

Respuesta

  • Algoritmo A tiene una complejidad temporal de O(n).
  • Algoritmo B tiene una complejidad temporal de O(1).

Conclusión

El Algoritmo B es más eficiente en términos de tiempo que el Algoritmo A.

Ejercicio 4: Análisis de Complejidad en Casos Diferentes

Problema

Analiza la complejidad temporal en los mejores, peores y casos promedio del siguiente algoritmo de búsqueda lineal.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Solución

  1. Mejor Caso:

    • Descripción: El mejor caso ocurre cuando el target es el primer elemento del arreglo.
    • Complejidad Temporal: O(1).

  2. Peor Caso:

    • Descripción: El peor caso ocurre cuando el target no está en el arreglo o es el último elemento.
    • Complejidad Temporal: O(n).

  3. Caso Promedio:

    • Descripción: En promedio, el target se encuentra en la mitad del arreglo.
    • Complejidad Temporal: O(n/2), que se simplifica a O(n).

Respuesta

  • Mejor Caso: O(1)
  • Peor Caso: O(n)
  • Caso Promedio: O(n)

Ejercicio 5: Análisis de Complejidad de un Algoritmo Recursivo

Problema

Dado el siguiente algoritmo recursivo, determina su complejidad temporal.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Solución

  1. Identificación de Llamadas Recursivas: La función factorial se llama a sí misma n veces.
  2. Complejidad Temporal: Cada llamada recursiva realiza una multiplicación y una llamada a sí misma hasta llegar a n = 0.
  3. Complejidad Temporal: La complejidad temporal es O(n).

Respuesta

La complejidad temporal del algoritmo es O(n).

Conclusión

En esta sección, hemos practicado el análisis de la complejidad temporal y espacial de varios algoritmos. Hemos aprendido a identificar bucles, estructuras de datos y llamadas recursivas para determinar la eficiencia de un algoritmo. Estos ejercicios nos preparan para diseñar y optimizar algoritmos de manera más efectiva en el futuro.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados