Complejidad de bucle anidado

Question

Estoy trabajando con MIT 6.006 OpenCourseWare como se enseñó en el otoño de 2011 . El problema 1.2c pregunta por la complejidad temporal de un algoritmo ¹ que encuentra un elemento pico (es decir, todos los vecinos son menores o iguales) de una matriz M x N. Mi análisis de complejidad no coincide con el de ellos y parece depender de la complejidad de un ciclo anidado.

El algoritmo crea una cruz que divide la matriz en cuatro "subproblemas". Encuentra el máximo en la cruz, verifica a los vecinos y recurre según sea necesario:

def algorithm3(problem, bestSeen = None, trace = None):
    # if it's empty, we're done 
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    midRow = problem.numRow // 2
    midCol = problem.numCol // 2

    # first, get the list of all subproblems
    subproblems = []

    (subStartR1, subNumR1) = (0, midRow)
    (subStartR2, subNumR2) = (midRow + 1, problem.numRow - (midRow + 1))
    (subStartC1, subNumC1) = (0, midCol)
    (subStartC2, subNumC2) = (midCol + 1, problem.numCol - (midCol + 1))

    subproblems.append((subStartR1, subStartC1, subNumR1, subNumC1))
    subproblems.append((subStartR1, subStartC2, subNumR1, subNumC2))
    subproblems.append((subStartR2, subStartC1, subNumR2, subNumC1))
    subproblems.append((subStartR2, subStartC2, subNumR2, subNumC2))

    # find the best location on the cross (the middle row combined with the
    # middle column)
    cross = []

    cross.extend(crossProduct([midRow], range(problem.numCol)))
    cross.extend(crossProduct(range(problem.numRow), [midCol]))

    crossLoc = problem.getMaximum(cross, trace)
    neighbor = problem.getBetterNeighbor(crossLoc, trace)

    # update the best we've seen so far based on this new maximum
    if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen):
        bestSeen = neighbor
        if not trace is None: trace.setBestSeen(bestSeen)

    # return if we can't see any better neighbors
    if neighbor == crossLoc:
        if not trace is None: trace.foundPeak(crossLoc)
        return crossLoc

    # figure out which subproblem contains the largest number we've seen so
    # far, and recurse
    sub = problem.getSubproblemContaining(subproblems, bestSeen)
    newBest = sub.getLocationInSelf(problem, bestSeen)
    if not trace is None: trace.setProblemDimensions(sub)
    result = algorithm3(sub, newBest, trace)
    return problem.getLocationInSelf(sub, result)

El instructor proporciona la complejidad para getMaximumcomo O (len (ubicaciones)) getBetterNeighbory getLocationInSelfcomo O (1), getSubproblemContainingcomo O (len (boundList)) y todas las llamadas de seguimiento como O (1). El crossProductse calcula como:

def crossProduct(list1, list2):
    answer = []
    for a in list1:
        for b in list2:
            answer.append ((a, b))
    return answer

La solución establece que "una sola llamada de la función (sin contar la llamada recursiva) funciona de forma proporcional a m + n". No entiendo esto.

¿No es crossProductO (mn)?

Mi razonamiento es que para una matriz M x N, getMaximumdebe atravesar la cruz divisoria (una fila, una columna) que aporta O (m + n). El getSubproblemContainingaporta algo lineal, O (m) u O (n). Todo lo demás además crossProductes O (1), la complejidad de crossProductno ser proporcionado, de modo que la relación de recurrencia es

T(m, n) = O(mn) + O(m + n) + cO(n) + T(m/2, n/2)   for some constant c
        = O(mn) + T(m/2, n/2)

La recurrencia se reduce a través de la serie geométrica a O (m + n),

T(m, n) = O(mn) + O(m + n)
        = O(mn) 

lo que da como resultado T (n, n) = O (n ^ 2). La solución proporcionada es O (n). El crossProducttérmino parece ser la discrepancia.

---

¹ El instructor escribe la implementación del algoritmo / código. Todos los errores de estilo Pythonic son suyos (y probablemente se hayan cometido por razones pedagógicas).

Answer 1

No se olvide de lo que ny men realidad son.

Cuando dices que esta función:

def crossProduct(list1, list2):
    answer = []
    for a in list1:
        for b in list2:
            answer.append ((a, b))
    return answer

toma O (mn) tiempo, ¿cuáles son my n? Bueno, m es el tamaño de list1 y n es el tamaño de list2 (o viceversa).

Cuando dice que el algoritmo3 toma O (mn) tiempo, ¿cuáles son my n? Bueno, m es el número de filas y n es el número de columnas (o viceversa).

¡Aférrate! ¡Esos no son lo mismo! Deberíamos usar diferentes nombres para diferentes variables. Sería más fácil si dijéramos que crossProduct tiene una complejidad O (ab) donde a es el tamaño de list1 yb es el tamaño de list2 (o viceversa). No se puede dar el mismo nombre de variable a dos cosas diferentes y luego asumir que son lo mismo.

Entonces, ¿qué son ayb?

cross.extend(crossProduct([midRow], range(problem.numCol)))
cross.extend(crossProduct(range(problem.numRow), [midCol]))

Bien, lo llamamos una vez con a = 1 y b = n, y lo volvemos a llamar con a = my b = 1. Entonces, estas dos llamadas juntas tienen complejidad O (1n + m1) = O (n + m).