Complexité des boucles imbriquées

Question

Je travaille avec MIT 6.006 OpenCourseWare comme enseigné à l'automne 2011 . Le problème 1.2c demande la complexité temporelle d'un algorithme ¹ qui trouve un élément de pic (c'est-à-dire que tous les voisins sont inférieurs ou égaux) d'une matrice M x N. Mon analyse de complexité ne correspond pas à la leur et semble dépendre de la complexité d'une boucle imbriquée.

L'algorithme crée une croix qui divise la matrice en quatre "sous-problèmes". Il trouve le maximum sur la croix, vérifie les voisins et se répète au besoin:

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)

L'instructeur fournit la complexité de getMaximumas O (len (locations)), getBetterNeighboret getLocationInSelfas O (1), getSubproblemContainingas O (len (boundList)), et tous les appels de trace comme O (1). Le crossProductest calculé comme:

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

La solution déclare, "un seul appel de la fonction (sans compter l'appel récursif) fonctionne proportionnellement à m + n." Je ne comprends pas ça.

N'est-ce pas crossProductO (mn)?

Mon raisonnement est que pour une matrice M x N, il getMaximumfaut traverser la croix de division (une ligne, une colonne) qui contribue O (m + n). Le getSubproblemContainingapporte quelque chose de linéaire, O (m) ou O (n). Tout le reste crossProductest O (1), la complexité de crossProductne pas être fourni, de sorte que la relation de récurrence est

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 récurrence se réduit via la série géométrique à O (m + n),

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

ce qui donne T (n, n) = O (n ^ 2). La solution fournie est O (n). Le crossProductterme semble être la divergence.

---

¹ L'implémentation de l'algorithme / du code est écrite par l'instructeur. Toutes les erreurs de style pythonique sont les leurs (et probablement commises pour des raisons pédagogiques).

Answer 1

N'oubliez pas ce nque msont et sont réellement.

Quand vous dites que cette fonction:

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

prend O (mn) temps, que sont m et n? Eh bien, m est la taille de list1 et n est la taille de list2 (ou vice versa).

Quand vous dites que l'algorithme3 prend O (mn) temps, que sont m et n? Eh bien, m est le nombre de lignes et n est le nombre de colonnes (ou vice versa).

Attendre! Ce n'est pas la même chose! Nous devrions utiliser des noms différents pour différentes variables. Ce serait plus facile si nous disions que crossProduct a une complexité O (ab) où a est la taille de list1 et b est la taille de list2 (ou vice versa). Vous ne pouvez pas donner à deux choses différentes le même nom de variable et ensuite supposer qu'elles sont la même chose.

Alors, que sont a et b?

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

D'accord, nous l'appelons une fois avec a = 1 et b = n, et nous l'appelons à nouveau avec a = m et b = 1. Donc, ces deux appels ont ensemble une complexité O (1n + m1) = O (n + m).