Análisis de complejidad

- Contador de inversiones

def mergeSort(arr, n):
   # Se crea un temp_arr para almacenar la matriz ordenada en la función merge
   temp_arr = [0]*n
   return _mergeSort(arr, temp_arr, 0, n - 1)

# Esta función utilizará MergeSort para contar las inversiones
def _mergeSort(arr, temp_arr, left, right):

   # Una variable inv_count se utiliza para almacenar los conteos de inversiones en cada llamada recursiva
   inv_count = 0

   # Realizaremos una llamada recursiva solo si tenemos más de un elemento
   if left < right:

       # Se calcula la posición media (mid) para dividir la matriz en dos submatrices
       # La división entera (floor division) es necesaria en Python
       mid = (left + right)//2

       # Se calcularán los conteos de inversiones en la submatriz izquierda
       inv_count += _mergeSort(arr, temp_arr, left, mid)

       # Se calcularán los conteos de inversiones en la submatriz derecha
       inv_count += _mergeSort(arr, temp_arr, mid + 1, right)

       # Se fusionarán las dos submatrices en una submatriz ordenada
       inv_count += merge(arr, temp_arr, left, mid, right)
   return inv_count

# Esta función fusionará dos submatrices en una sola submatriz ordenada
def merge(arr, temp_arr, left, mid, right):
   # Índice de inicio de la submatriz izquierda
   i = left
   # Índice de inicio de la submatriz derecha
   j = mid + 1
   # Índice de inicio de la submatriz a ordenar
   k = left
   inv_count = 0
   # Se verifican las condiciones para asegurarse de que i y j no excedan los límites de sus submatrices
   while i <= mid and j <= right:
       # No habrá inversión si arr[i] <= arr[j]
       if arr[i] <= arr[j]:
           temp_arr[k] = arr[i]
           k += 1
           i += 1
       else:
           # Ocurrirá una inversión
           temp_arr[k] = arr[j]
           inv_count += (mid - i + 1)
           k += 1
           j += 1

   # Se copian los elementos restantes de la submatriz izquierda en la matriz temporal
   while i <= mid:
       temp_arr[k] = arr[i]
       k += 1
       i += 1
   # Se copian los elementos restantes de la submatriz derecha en la matriz temporal
   while j <= right:
       temp_arr[k] = arr[j]
       k += 1
       j += 1
   # Se copia la submatriz ordenada en la matriz original
   for loop_var in range(left, right + 1):
       arr[loop_var] = temp_arr[loop_var]

   return inv_count

# Código del programa principal

# Matriz dada
arr = [1, 20, 6, 4, 5, 12, 7, 11, 15, 9]
n = len(arr)

# Se llama a mergeSort para contar las inversiones en la matriz
result = mergeSort(arr, n)

# Se imprime el número de inversiones encontradas
print("El número de inversiones es", result)

# Se imprime la matriz ordenada
print(arr)

1. Función mergeSort():

Sea T_mergeSort(n) la complejidad de tiempo de la función mergeSort(), donde n es la longitud de la matriz.

La función mergeSort() realiza las siguientes operaciones en orden:

1. Creación de una matriz temporal de tamaño n: O(n)
2. Llamada recursiva a _mergeSort() para la submatriz izquierda: T_mergeSort(n/2)
3. Llamada recursiva a _mergeSort() para la submatriz derecha: T_mergeSort(n/2)
4. Fusión de las submatrices y algunas operaciones adicionales: O(n)

La complejidad total de mergeSort():

T_mergeSort(n) = O(n) + T_mergeSort(n/2) + T_mergeSort(n/2) + O(n)

Simplificando la ecuación:

T_mergeSort(n) = 2 * T_mergeSort(n/2) + O(n)

1. Función merge():

Sea T_merge(n) la complejidad de tiempo de la función merge(), donde n es el tamaño total de las submatrices que se fusionan.

La función merge() realiza las siguientes operaciones en orden:

1. Inicialización de índices y variables: O(1)
2. Comparación y copia de elementos en la matriz temporal: O(n)
3. Copia de elementos restantes de las submatrices: O(n)
4. Copia de la submatriz ordenada en la matriz original: O(n)

La complejidad total de merge() se puede expresar como:

T_merge(n) = O(1) + O(n) + O(n) + O(n)

Simplificando la ecuación:

T_merge(n) = O(n)

En resumen, el análisis de complejidad es:

1. La función mergeSort() tiene una complejidad de tiempo:

T_mergeSort(n) = 2 * T_mergeSort(n/2) + O(n)

1. La función merge() tiene una complejidad de tiempo:

T_merge(n) = O(n)

Esto significa que el tiempo de ejecución del código aumentará de manera logarítmica con el tamaño de la matriz.

- Mochila:

peso = [2, 5, 3, 6, 1]
benef = [28, 33, 5, 12, 20]


def mochila_d_pd1(p, b, M):
   n = len(p)
   t = [[0 for _ in range(M + 1)] for _ in range(n + 1)]

   for i in range(1, n + 1):
       for m in range(1, M + 1):
           if p[i - 1] <= m and b[i - 1] + t[i - 1][m - p[i - 1]] > t[i - 1][m]:
               t[i][m] = b[i - 1] + t[i - 1][m - p[i - 1]]
           else:
               t[i][m] = t[i - 1][m]

   return t[n][M]


print('Ingrese peso máximo M de soporte de la mochila:')
Maxi = int(input())
print(mochila_d_pd1(peso, benef, Maxi))

Sea n la longitud de las listas de pesos y beneficios, y M el peso máximo de soporte de la mochila.

1. Creación de la matriz t:

• La creación de la matriz t implica inicializar todos los elementos de la matriz.
• El número total de elementos en la matriz es (n + 1) * (M + 1).
• Por lo tanto, la complejidad de esta operación es O((n + 1) * (M + 1)).

1. Rellenar la matriz t:

• Se utilizan dos bucles anidados para recorrer la matriz t.
• El bucle externo se ejecuta n veces y el bucle interno se ejecuta M veces.
• En cada iteración del bucle interno, se realiza una comparación y una asignación, lo cual tiene un tiempo constante.
• Por lo tanto, la complejidad de esta operación es O(n * M).

1. Retorno del valor t[n][M]:

• Devolver el valor almacenado en la posición t[n][M] tiene una complejidad de tiempo constante, O(1).

En resumen, la complejidad de tiempo del algoritmo es

T (n) = O((n + 1) * (M + 1)) + O(n * M) + O(1), que se simplifica a O(n * M) en términos de la complejidad dominante. Esto significa que el tiempo de ejecución del algoritmo crecerá linealmente en función del producto de n y M.

- Cambio de moneda:

monedas_peru = [11, 5, 1]
monedas_mexico = [1000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
monedas_chile = [20000, 10000, 5000, 2000, 1000, 500, 100, 50, 10]
monedas_japon = [10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1]
monedas_alemania = [1000, 500, 200, 100, 50, 20, 10, 5, 2, 1]

...