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))

...