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

Análisis de Complejidad

Siguiente ►
►

El análisis de complejidad es una parte fundamental en el estudio de algoritmos, ya que nos permite evaluar la eficiencia de un algoritmo en términos de tiempo y espacio. En esta sección, aprenderemos los conceptos básicos de la complejidad temporal y espacial, cómo se mide y cómo se expresa utilizando la notación Big O.

Conceptos Básicos

Complejidad Temporal

La complejidad temporal se refiere a la cantidad de tiempo que un algoritmo tarda en completarse en función del tamaño de la entrada. Es crucial para determinar la eficiencia de un algoritmo, especialmente cuando se trabaja con grandes conjuntos de datos.

Complejidad Espacial

La complejidad espacial se refiere a la cantidad de memoria que un algoritmo necesita para ejecutarse en función del tamaño de la entrada. Esto incluye tanto la memoria utilizada por las variables como la memoria adicional que el algoritmo pueda requerir.

Notación Big O

La notación Big O es una forma de expresar la complejidad de un algoritmo de manera asintótica, es decir, cómo se comporta el algoritmo cuando el tamaño de la entrada tiende a infinito.

Principales Clases de Complejidad

  1. O(1) - Constante: El tiempo de ejecución no depende del tamaño de la entrada.

    def constante_algo(arr):
    return arr[0]

  2. O(log n) - Logarítmica: El tiempo de ejecución crece logarítmicamente con el tamaño de la entrada.

    import math
def logaritmica_algo(n):
    return math.log(n)

  3. O(n) - Lineal: El tiempo de ejecución crece linealmente con el tamaño de la entrada.

    def lineal_algo(arr):
    for i in arr:
        print(i)

  4. O(n log n) - Linealítmica: El tiempo de ejecución crece en función de n log n.

    def linealitmica_algo(arr):
    arr.sort()

  5. O(n^2) - Cuadrática: El tiempo de ejecución crece cuadráticamente con el tamaño de la entrada.

    def cuadratica_algo(arr):
    for i in arr:
        for j in arr:
            print(i, j)

  6. O(2^n) - Exponencial: El tiempo de ejecución crece exponencialmente con el tamaño de la entrada.

    def exponencial_algo(n):
    if n == 0:
        return 1
    else:
        return exponencial_algo(n-1) + exponencial_algo(n-1)

Ejemplos Prácticos

Ejemplo 1: Búsqueda Lineal vs. Búsqueda Binaria

Búsqueda Lineal (O(n))

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

Búsqueda Binaria (O(log n))

def busqueda_binaria(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Ejemplo 2: Ordenación por Burbuja vs. Ordenación Rápida

Ordenación por Burbuja (O(n^2))

def ordenacion_burbuja(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Ordenación Rápida (O(n log n))

def ordenacion_rapida(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return ordenacion_rapida(left) + middle + ordenacion_rapida(right)

Ejercicios Prácticos

Ejercicio 1: Análisis de Complejidad

Analiza la complejidad temporal de los siguientes fragmentos de código:

def ejercicio_1(arr):
    for i in arr:
        print(i)
def ejercicio_2(arr):
    for i in arr:
        for j in arr:
            print(i, j)

Soluciones

  1. O(n): El bucle for recorre todos los elementos de arr una vez.
  2. O(n^2): El bucle for anidado recorre todos los elementos de arr para cada elemento de arr.

Ejercicio 2: Implementación de Algoritmos

Implementa una función que realice la búsqueda binaria en una lista ordenada y otra que realice la ordenación por burbuja.

Soluciones

  1. Búsqueda Binaria
def busqueda_binaria(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return -1
  1. Ordenación por Burbuja
def ordenacion_burbuja(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Conclusión

En esta sección hemos aprendido los conceptos básicos del análisis de complejidad, incluyendo la complejidad temporal y espacial, y cómo se expresa utilizando la notación Big O. También hemos visto ejemplos prácticos y realizado ejercicios para reforzar estos conceptos. Con esta base, estamos preparados para profundizar en técnicas algorítmicas más avanzadas en los siguientes módulos.

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