¿Cómo encontrar la relación de recurrencia y calcular el Teorema Maestro de un código de Ordenamiento Merge?
Estoy tratando de encontrar el Teorema Maestro de este Código de Ordenamiento por Fusión, pero primero necesito encontrar su relación de recurrencia, pero estoy luchando para hacerlo y entender ambos. Ya vi algunas preguntas similares aquí, pero no pude entender las explicaciones, como, ¿primero necesito encontrar cuántas operaciones tiene el código? ¿Alguien podría ayudarme con eso?
Código:
def mergeSort(alist):
print(“Dividiendo”,alist)
if len(alist)>1:
mitad = len(alist)//2
mitad_izq = alist[:mitad]
mitad_der = alist[mitad:]
mergeSort(mitad_izq)
mergeSort(mitad_der)
i=0
j=0
k=0
while i < len(mitad_izq) and j < len(mitad_der):
if mitad_izq[i] < mitad_der[j]:
alist[k]=mitad_izq[i]
i=i+1
else:
alist[k]=mitad_der[j]
j=j+1
k=k+1
while i < len(mitad_izq):
alist[k]=mitad_izq[i]
i=i+1
k=k+1
while j < len(mitad_der):
alist[k]=mitad_der[j]
j=j+1
k=k+1
print("Fusionando",alist)
alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)
davy.ai
Para encontrar la relación de recurrencia de este código de ordenamiento por mezcla, primero debemos entender las operaciones básicas que se realizan en cada iteración del algoritmo.
El código divide primero de forma recursiva la lista de entrada en dos mitades hasta que cada mitad contiene solo un elemento. Luego, compara y fusiona las sub-listas en orden ordenado, resultando en una lista ordenada.
El número de operaciones básicas en el ordenamiento por mezcla se puede calcular de la siguiente manera:
– El paso de división toma tiempo constante y se realiza log n veces (ya que la entrada se divide de manera uniforme)
– El paso de fusión toma tiempo lineal y se realiza log n veces (ya que fusionamos dos listas de tamaño n/2 para formar una lista ordenada de tamaño n)
Por lo tanto, el número total de operaciones básicas se puede representar con la relación de recurrencia:
T(n) = 2T(n/2) + n
(Donde T(n) representa el tiempo necesario para realizar el ordenamiento por mezcla en una entrada de tamaño n)
Ahora, para aplicar el Teorema Maestro a esta relación de recurrencia, necesitamos determinar los valores de a, b y f(n).
En este caso, a = 2 (ya que cada llamada recursiva divide la entrada en dos mitades)
b = 2 (ya que cada sub-problema tiene la mitad del tamaño de la entrada original)
f(n) = n (ya que el paso de fusión toma tiempo lineal)
Según el Teorema Maestro, tenemos:
Si f(n) = O(n^c) para alguna constante c, entonces:
– Si a < b^c, entonces T(n) = O(n^c)
– Si a = b^c, entonces T(n) = O(n^c * log n)
– Si a > b^c, entonces T(n) = O(n^logb a)
En nuestro caso, f(n) = O(n), ya que c = 1. Por lo tanto:
a = 2
b = 2
c = 1
Como a = b^c, podemos aplicar el caso 2 del Teorema Maestro para obtener:
T(n) = O(n log n)
Por lo tanto, la complejidad temporal del ordenamiento por mezcla se puede expresar como O(n log n).