El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

Introducción

En este primer tema del curso "Algoritmos Avanzados", abordaremos los conceptos básicos y la notación que utilizaremos a lo largo del curso. Es fundamental tener una comprensión sólida de estos conceptos para poder seguir los temas más avanzados que veremos posteriormente.

Objetivos

Comprender qué es un algoritmo y sus propiedades.
Familiarizarse con la notación asintótica.
Entender los conceptos de complejidad temporal y espacial.
Conocer las estructuras de datos básicas.

¿Qué es un Algoritmo?

Un algoritmo es un conjunto de instrucciones bien definidas y finitas que permiten resolver un problema o realizar una tarea específica. Las propiedades principales de un algoritmo son:

Finitud: Debe terminar después de un número finito de pasos.
Definición: Cada paso debe estar claramente definido y no debe haber ambigüedad.
Entrada: Debe tener cero o más entradas.
Salida: Debe tener una o más salidas.
Efectividad: Cada paso debe ser lo suficientemente básico para ser realizado en un tiempo finito.

Notación Asintótica

La notación asintótica se utiliza para describir el comportamiento de un algoritmo en términos de su complejidad temporal y espacial. Las notaciones más comunes son:

O (Big O): Describe el peor caso.
Ω (Omega): Describe el mejor caso.
Θ (Theta): Describe el caso promedio.

Ejemplos de Notación Asintótica

O(1): Tiempo constante.
O(n): Tiempo lineal.
O(n^2): Tiempo cuadrático.

Tabla de Comparación de Notaciones

Notación	Descripción	Ejemplo de Algoritmo
O(1)	Constante	Acceso a un elemento en un array
O(n)	Lineal	Búsqueda lineal
O(log n)	Logarítmica	Búsqueda binaria
O(n^2)	Cuadrática	Ordenación por burbuja

Complejidad Temporal y Espacial

Complejidad Temporal

La complejidad temporal mide el tiempo que tarda un algoritmo en ejecutarse en función del tamaño de la entrada. Se expresa comúnmente en notación Big O.

Complejidad Espacial

La complejidad espacial mide la cantidad de memoria que un algoritmo necesita en función del tamaño de la entrada.

Ejemplo de Complejidad Temporal y Espacial

Consideremos el siguiente fragmento de código:

def suma_lista(lista):
    suma = 0
    for numero in lista:
        suma += numero
    return suma

Complejidad Temporal: O(n), donde n es el número de elementos en la lista.
Complejidad Espacial: O(1), ya que solo se utilizan variables adicionales constantes.

Estructuras de Datos Básicas

Arrays

Descripción: Colección de elementos del mismo tipo almacenados en ubicaciones contiguas.
Operaciones Comunes: Acceso (O(1)), Inserción (O(n)), Eliminación (O(n)).

Listas Enlazadas

Descripción: Colección de nodos donde cada nodo contiene un valor y un puntero al siguiente nodo.
Operaciones Comunes: Acceso (O(n)), Inserción (O(1)), Eliminación (O(1)).

Pilas y Colas

Pilas: Estructura LIFO (Last In, First Out).
- Operaciones Comunes: Push (O(1)), Pop (O(1)).
Colas: Estructura FIFO (First In, First Out).
- Operaciones Comunes: Enqueue (O(1)), Dequeue (O(1)).

Ejemplo de Uso de una Pila

class Pila:
    def __init__(self):
        self.items = []

    def esta_vacia(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

# Uso de la pila
pila = Pila()
pila.push(1)
pila.push(2)
print(pila.pop())  # Salida: 2

Ejercicios Prácticos

Ejercicio 1: Análisis de Complejidad

Analiza la complejidad temporal y espacial del siguiente algoritmo:

def encontrar_maximo(lista):
    maximo = lista[0]
    for numero in lista:
        if numero > maximo:
            maximo = numero
    return maximo

Solución:

Complejidad Temporal: O(n), donde n es el número de elementos en la lista.
Complejidad Espacial: O(1), ya que solo se utilizan variables adicionales constantes.

Ejercicio 2: Implementación de una Cola

Implementa una cola utilizando una lista en Python y proporciona las operaciones básicas (enqueue y dequeue).

class Cola:
    def __init__(self):
        self.items = []

    def esta_vacia(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

# Uso de la cola
cola = Cola()
cola.enqueue(1)
cola.enqueue(2)
print(cola.dequeue())  # Salida: 1

Conclusión

En esta sección, hemos cubierto los conceptos básicos y la notación que utilizaremos a lo largo del curso. Hemos aprendido qué es un algoritmo, la notación asintótica, la complejidad temporal y espacial, y algunas estructuras de datos básicas. Estos fundamentos son esenciales para entender y aplicar técnicas algorítmicas avanzadas en los módulos siguientes.

Conceptos Básicos y Notación