Análisis de Complejidad Temporal y Algoritmos de Ordenamiento

Este documento explora las complejidades temporales de los algoritmos y profundiza en varios métodos de ordenamiento, con un enfoque en su implementación y análisis de eficiencia.

Análisis de Complejidad Temporal

Complejidad Temporal Promedio (Esperada)

Se refiere a la complejidad promedio de los tiempos de ejecución para todas las posibles entradas de una escala dada, calculada bajo la suposición de entradas aleatorias.

Complejidad Temporal Mejor Caso (Best Case)

Es la complejidad temporal mínima que un algoritmo puede exhibir para una escala de entrada determinada.

Complejidad Temporal Peor Caso (Worst Case)

Es la complejidad temporal máxima que un algoritmo puede exhibir para una escala de entrada determinada.

Análisis Amortizado

El análisis amortizado es una técnica utilizada para analizar el rendimiento de algoritmos y estructuras de datos dinámicas. Evalúa el rendimiento general considerando el costo promedio de una secuencia de operaciones, en lugar de centrarse únicamente en el costo de operaciones individuales. Este análisis no involucra probabilidades y garantiza el tiempo promedio por operación en el peor de los casos, pero no el rendimiento promedio del sistema. En el peor de los casos, el análisis amortizado distribuye el costo de las operaciones de alto costo entre las operaciones de bajo costo para mantener un costo promedio razonable.

Los métodos comunes para el análisis amortizado incluyen análisis agregado, análisis de contabilidad y análisis de potencial.

Análisis Agregado

El análisis agregado calcula el costo total de una secuencia de operaciones y lo divide entre el número de operaciones para obtener la complejidad amortizada por operación.

Consideremos la operación de añadir un elemento al final de un array dinámico con capacidad inicial de \(m=1\):

  • Si el array no está lleno, la inserción cuesta \(O(1)\).
  • Si el array está lleno, se requiere una operación de redimensionamiento (costo \(O(m)\), donde \(m\) es el tamaño actual), seguida de una inserción \(O(1)\).

Para \(n\) inserciones, el costo total se descompone en:

  • Costo de inserción: \(O(n)\) para \(n\) operaciones de \(O(1)\).
  • Costo de redimensionamiento: Si la capacidad se duplica cada vez, los costos de redimensionamiento para \(n\) elementos serían \(1 + 2 + 4 + \dots + 2^k \le n\), que es \(O(n)\).

El costo amortizado total para \(n\) inserciones es \(O(n) + O(n) = O(n)\). Por lo tanto, el costo amortizado por inserción es \(\frac{O(n)}{n} = O(1)\).

Análisis de Contabilidad (Accounting Analysis)

En este método, se asigna un costo amortizado fijo a cada operación. Las operaciones de bajo costo "pagan" por adelantado por las operaciones futuras de alto costo.

Para la inserción en un array dinámico, asignemos un costo amortizado de 3 por inserción:

  • Costo real: 1
  • Ahorro para redimensionamientos futuros: 2

Cuando se produce un redimensionamiento, el costo real es \(O(m)\). Se asume que la mitad de los elementos previamente insertados (aproximadamente \(n/2\)) han pagado un total de \(2 \times (n/2) = n\) unidades, lo que cubre el costo del redimensionamiento.

Análisis de Potencial (Potential Analysis)

Este método utiliza una función de potencial \(\Phi(S)\) que mide la "energía potencial" de una estructura de datos en un estado \(S\). El costo amortizado \(\hat{c}\) de una operación se define como \(\hat{c} = c + \Phi(S') - \Phi(S)\), donde \(c\) es el costo real y \(S'\) es el estado posterior a la operación.

Propiedades de \(\Phi\):

  • El potencial inicial \(\Phi(S_0) = 0\).
  • El potencial siempre es no negativo: \(\Phi(S) \ge 0\).

Para un array dinámico, definamos \(\Phi(S) = 2n - m\), donde \(n\) es el número de elementos y \(m\) es la capacidad.

  • Inserción sin redimensionamiento:

  • Costo real: \(c=1\).

  • Cambio de potencial: \(\Phi(S') - \Phi(S) = (2(n+1) - m) - (2n - m) = 2\).

  • Costo amortizado: \(\hat{c} = 1 + 2 = 3\).

  • Inserción con redimensionamiento (duplicando capacidad):

  • Costo real: \(c = n+1\) (copiar \(n\) elementos y añadir 1).

  • Cambio de potencial: \(\Phi(S') - \Phi(S) = (2(n+1) - 2m) - (2n - m) = 2 - m = 2 - n\) (asumiendo \(n=m\) antes del redimensionamiento).

  • Costo amortizado: \(\hat{c} = (n+1) + (2-n) = 3\).

En ambos casos, el costo amortizado es contsante, \(O(1)\).

Algoritmos de Ordenamiento

Para mejorar la búsqueda de claves en una interfaz de conjunto, se puede utilizar un array ordenado. A continuación, se presentan varios métodos para ordenar un array.

3.2.1 Ordenamiento por Permutación (Permutation Sort)

Este método genera todas las permutaciones posibles de un array y devuelve la primera que está ordenada. Es extremadamente ineficiente.

  • Complejidad temporal:
  • Mejor caso: \(\Theta(n)\) (si la primera permutación generada está ordenada).
  • Peor caso: \(\Theta(n \cdot n!)\) (requiere \(n!\) permutaciones, cada una verificada en \(O(n)\)).

Conceptos Clave: "In-place" y Estabilidad

  • "In-place" (En el lugar): Un algoritmo de ordenamiento es "in-place" si utiliza solo una cantidad constante de espacio de memoria adicional (\(O(1)\)).
  • Estabilidad (Stability): Un algoritmo de ordenamiento es estable si mantiene el orden relativo de elementos iguales. Si \(A[i] == A[j]\) con \(i < j\), después de ordenar, el elemento que originalmente estaba en \(A[i]\) aparecerá antes que el elemento que estaba en \(A[j]\).

3.2.2 Ordenamiento por Selección (Selection Sort)

En cada paso, encuentra el elemento mínimo (o máximo) restante y lo coloca en su posición correcta. La implementación recursiva dada intercambia el máximo del prefijo con el elemento actual.


def selection_sort(arr, i=None):
   if i is None:
       i = len(arr) - 1
   if i > 0:
       max_idx = find_max_index(arr, i)
       arr[i], arr[max_idx] = arr[max_idx], arr[i]
       selection_sort(arr, i - 1)

def find_max_index(arr, i):
   if i > 0:
       prev_max_idx = find_max_index(arr, i - 1)
       if arr[i] < arr[prev_max_idx]:
           return prev_max_idx
   return i

  • Complejidad temporal:

  • Promedio/Peor caso: \(\Theta(n^2)\) (debido a las llamadas recursivas y la búsqueda del máximo).

  • Mejor caso: \(\Theta(n^2)\).

  • Es "in-place".

  • Generalmente no es estable si se implementa con arrays debido a los intercambios.

3.2.3 Ordenamiento por Inserción (Insertion Sort)

Mantiene un subconjunto ordenado y, en cada paso, inserta el siguiente elemento en su posición correcta dentro del subconjunto ordenado.


def insertion_sort(arr, i=None):
   if i is None:
       i = len(arr) - 1
   if i > 0:
       insertion_sort(arr, i - 1)
       insert_element(arr, i)

def insert_element(arr, i):
   if i > 0 and arr[i] < arr[i - 1]:
       arr[i], arr[i - 1] = arr[i - 1], arr[i]
       insert_element(arr, i - 1)

  • Complejidad temporal:

  • Promedio/Peor caso: \(\Theta(n^2)\).

  • Mejor caso: \(\Theta(n)\) (si el array ya está ordenado).

  • Es estable.

  • Es "in-place".

  • Eficiente para arrays casi ordenados o pequeños. La complejidad puede expresarse como \(\Theta(n + K)\), donde \(K\) es el número de pares inversos.

3.2.4 Ordenamiento por Fusión (Merge Sort)

Divide el array en dos mitades, ordena recursivamente cada mitad y luego fusiona las dos mitades ordenadas.


def merge_sort(arr, start=0, end=None):
   if end is None:
       end = len(arr)
   if 1 < end - start:
       mid = (start + end + 1) // 2
       merge_sort(arr, start, mid)
       merge_sort(arr, mid, end)
       left_half, right_half = arr[start:mid], arr[mid:end]
       i = j = 0
       k = start
       while k < end:
           if (j >= len(right_half)) or \
              (i < len(left_half) and left_half[i] < right_half[j]):
               arr[k] = left_half[i]
               i += 1
           else:
               arr[k] = right_half[j]
               j += 1
           k += 1
  • Complejidad temporal: \(\Theta(n \log n)\) en todos los casos (promedio, mejor, peor).
  • Es estable.
  • No es "in-place" en esta implementación (requiere espacio auxiliar \(O(n)\)).

3.2.5 Ordenamiento Shell (Shell Sort)

Es una optimización del ordenamiento por inserción que permite intercambiar elementos que están lejos unos de otros. Utiliza una secuencia de incrementos decrecientes.


def shell_sort(arr, gap=None):
   if gap is None:
       gap = len(arr) // 2
   if gap == 0:
       return
   for i in range(gap, len(arr)):
       temp = arr[i]
       j = i
       while j >= gap and arr[j - gap] > temp:
           arr[j] = arr[j - gap]
           j -= gap
       arr[j] = temp
   shell_sort(arr, gap // 2)
  • Complejidad temporal: Depende de la secuencia de incrementos. Puede variar desde \(\Theta(n^2)\) (con incrementos de \(\frac{n}{2}\)) hasta \(\Theta(n^{\frac{4}{3}})\) (con incrementos de Sedgewick).
  • Es "in-place".
  • No es estable.

3.2.6 Ordenamiento de Burbuja (Bubble Sort)

Compara repetidamente pares de elementos adyacentes y los intercambia si están en el orden incorrecto. Los elementos más grandes "burbujean" hacia el final.


def bubble_sort(arr, n=None):
   if n is None:
       n = len(arr)
   if n == 1:
       return
   swapped = False
   for i in range(n - 1):
       if arr[i] > arr[i + 1]:
           arr[i], arr[i + 1] = arr[i + 1], arr[i]
           swapped = True
   if not swapped:
       return
   bubble_sort(arr, n - 1)

  • Complejidad temporal:

  • Promedio/Peor caso: \(\Theta(n^2)\).

  • Mejor caso: \(\Theta(n)\) (si el array ya está ordenado).

  • Es estable.

  • Es "in-place".

3.2.7 Ordenamiento por Conteo (Counting Sort)

Utiliza un array auxiliar para contar las ocurrencias de cada elemento y luego construye el array ordenado. Es eficiente cuando el rango de los elementos (\(W\)) no es excesivamente grande en comparación con el número de elementos (\(n\)).


def counting_sort(arr):
   max_val = max(arr)
   min_val = min(arr)
   range_of_elements = max_val - min_val + 1
   count_arr = [0] * range_of_elements
   result_arr = [0] * len(arr)

   # Contar ocurrencias
   for num in arr:
       count_arr[num - min_val] += 1

   # Calcular sumas acumulativas (para estabilidad)
   for i in range(1, len(count_arr)):
       count_arr[i] += count_arr[i - 1]

   # Construir el array resultante
   for num in reversed(arr):
       result_arr[count_arr[num - min_val] - 1] = num
       count_arr[num - min_val] -= 1

   return result_arr
  • Complejidad temporal: \(\Theta(n + W)\) en todos los casos.
  • Es estable (con la modificación de sumas acumulativas).
  • No es "in-place" (requiere espacio \(O(n + W)\)).
  • Es un algoritmo de ordenamiento no comparativo.

3.2.8 Ordenamiento por Radix (Radix Sort)

Ordena los números procesando dígitos individuales. Los números se ordenan primero por el dígito menos significativo y luego por los dígitos subsiguientes.

3.2.9 Ordenamiento por Cola de Prioridad (Priority Queue Sort)

Utiliza una estructura de Cola de Prioridad (PQ) para insertar todos los elementos y luego extraerlos en orden.


# Asumiendo una implementación de cola de prioridad 'PriorityQueue'
# con métodos add(element) y delete_max()

def heap_sort(PQ, arr):
   pq = PQ()
   for element in arr:
       pq.add(element)
   sorted_arr = []
   for _ in range(len(arr)):
       sorted_arr.append(pq.delete_max())
   return sorted_arr[::-1] # Invertir para orden ascendente si delete_max extrae el máximo
  • La eficiencia depende de la implementación de la PQ.
  • Usando un Heap Binario para la PQ:
  • Construcción: \(O(n)\).
  • Inserción: \(O(\log n)\).
  • Extracción de máximo: \(O(\log n)\).
  • Complejidad total del sort: \(O(n \log n)\).
  • Es "in-place".

3.2.10 Ordenamiento Rápido (Quick Sort)

Un algoritmo de tipo "divide y vencerás". Selecciona un elemento como pivote y particiona el array en dos sub-arrays (elementos menores que el pivote y elementos mayores que el pivote), luego ordena recursivamente los sub-arrays.

  • Análisis de tiempo de ejecución:

  • Mejor caso: \(\Theta(n \log n)\) (si el pivote es consistentemente la mediana).

  • Peor caso: \(\Theta(n^2)\) (si el pivote es consistentemente el mínimo o máximo).

  • Caso promedio: \(\Theta(n \log n)\).

  • Para evitar el peor caso:

  • Selección aleatoria del pivote.

  • Uso de algoritmos como BFPRT (Median of Medians) para encontrar un pivote que garantice particiones más equilibradas en tiempo lineal (\(O(n)\)).

  • Generalmente más rápido en la práctica que Merge Sort debido a menores constantes ocultas y mejor localidad de caché.

Etiquetas: análisis de complejidad Complejidad Temporal análisis amortizado ordenamiento selección

Publicado el 7-25 18:15

Etiquetas populares

©2026 Friki Work