es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Cómo encontrar la permutación peor caso para el algoritmo MergeSort.

12 Jun, 2023 Programación

Estoy obteniendo un error de recursión y cuando reassigno el límite recursivo, obtengo un error de memoria al intentar ejecutar el siguiente código.

def join(A, left, right, l, m, r):
    x = 0
    for x in range(m-l):
        A[x] = left[x]
    for j in range(r-m):
        A[x+j] = right[j]enter code here

def split(A, left, right, l, m, r):
    for i in range(0, m-l, 1):
        left[i] = A[i*2]
    for i in range(0, r-m, 1):
        right[i] = A[i*2+1]

def generateWorstCase(A, l, r):
    if l < r:
        m = int(l + (r-1) / 2)
        left = [0 for i in range(m - l + 1)]
        right = [0 for i in range(r - m)]
        split(A, left, right, l, m, r)
        generateWorstCase(left, l, m)
        generateWorstCase(right, m+1, r)
        join(A, left, right, l, m, r)

arr = [1, 2, 3, 4, 5, 6, 7, 8]
generateWorstCase(arr, 0, len(arr)-1)
print(arr)

Intenté traducir el ejemplo dado de geeksforgeekshttps://www.geeksforgeeks.org/find-a-permutation-that-causes-worst-case-of-merge-sort/, y aún estoy confundido sobre la escritura del código en python. Entiendo los fundamentos de cómo funciona (es decir, hace que el algoritmo de mergeSort compare la cantidad más alta). Aprecio cualquier consejo que pueda ayudar con esto.

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para solucionar el error de recursividad y el error de memoria en este código, puede aumentar el límite de recursividad utilizando sys.setrecursionlimit() antes de llamar a generateWorstCase(). Sin embargo, esta solución no es ideal ya que puede provocar errores de desbordamiento.

    Una solución mejor es modificar la función generateWorstCase() para usar un bucle en lugar de la recursividad. Aquí hay una forma de hacerlo:

    def generateWorstCase(A, l, r):
    stack = [(l, r)]
    while stack:
        l, r = stack.pop()
        if l < r:
            m = l + (r - l) // 2
            left = [0] * (m - l + 1)
            right = [0] * (r - m)
            split(A, left, right, l, m, r)
            stack.append((m + 1, r))
            stack.append((l, m))
            join(A, left, right, l, m, r)

    Este código utiliza una pila para simular las llamadas recursivas en el código original. En lugar de llamar a generateWorstCase() recursivamente, coloca las submatrices izquierda y derecha en la pila para procesarlas más tarde. El bucle continúa hasta que la pila esté vacía, lo que significa que se han procesado todas las submatrices.

    Tenga en cuenta que la fórmula para calcular m se ha cambiado a l + (r - l) // 2 para evitar el desbordamiento de enteros. El operador // realiza una división entera, que siempre devuelve un número entero.

    Con estos cambios, el código debería funcionar sin errores y producir la peor permutación esperada del array de entrada.

Comments are closed.