Complexidade de loop aninhado

Question

Estou trabalhando por meio do MIT 6.006 OpenCourseWare conforme ensinado no outono de 2011 . O Problema 1.2c pede a complexidade de tempo de um algoritmo ¹ que encontra um elemento de pico (ou seja, todos os vizinhos são menores ou iguais) de uma matriz M x N. Minha análise de complexidade não corresponde à deles e parece depender da complexidade de um loop aninhado.

O algoritmo cria uma cruz que divide a matriz em quatro "subproblemas". Ele encontra o máximo na cruz, verifica os vizinhos e recorre conforme necessário:

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)

O instrutor fornece a complexidade para getMaximumas O (len (locais)), getBetterNeighbore getLocationInSelfas O (1), getSubproblemContainingas O (len (boundList)), e todas as chamadas de rastreamento como O (1). O crossProducté calculado como:

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

A solução afirma: "uma única chamada da função (sem contar a chamada recursiva) funciona proporcionalmente a m + n." Eu não entendo isso.

Não é crossProductO (mn)?

Meu raciocínio é que, para uma matriz M x N, getMaximumdeve-se percorrer a cruz divisória (uma linha, uma coluna) que contribui com O (m + n). O getSubproblemContainingcontribui com algo linear, O (m) ou O (n). Todo o resto além crossProducté O (1), a complexidade de crossProductnão ser fornecido, de modo que a relação de recorrência é

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)

A recorrência reduz através da série geométrica para O (m + n),

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

que produz T (n, n) = O (n ^ 2). A solução fornecida é O (n). O crossProducttermo parece ser a discrepância.

---

¹ O algoritmo / implementação do código é escrito pelo instrutor. Todos os erros de estilo pitônico são deles (e provavelmente cometidos por razões pedagógicas).

Answer 1

Não se esqueça do que ne mrealmente são.

Quando você diz que esta função:

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

leva tempo O (mn), o que são me n? Bem, m é o tamanho de lista1 e n é o tamanho de lista2 (ou vice-versa).

Quando você diz que o algoritmo3 leva tempo O (mn), o que são m e n? Bem, m é o número de linhas en é o número de colunas (ou vice-versa).

Espere! Não são a mesma coisa! Devemos usar nomes diferentes para variáveis ​​diferentes. Seria mais fácil se disséssemos que crossProduct tem complexidade O (ab) onde a é o tamanho da lista1 e b é o tamanho da lista2 (ou vice-versa). Você não pode dar a duas coisas diferentes o mesmo nome de variável e então simplesmente assumir que são a mesma coisa.

Então, o que são aeb?

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

Ok, então chamamos uma vez com a = 1 e b = n, e chamamos novamente com a = me b = 1. Portanto, essas duas chamadas juntas têm complexidade O (1n + m1) = O (n + m).