Kompleksitas loop bersarang

Question

Saya bekerja melalui MIT 6.006 OpenCourseWare seperti yang diajarkan pada Musim Gugur 2011 . Soal 1.2c menanyakan kompleksitas waktu dari algoritma ¹ yang menemukan elemen puncak (yaitu semua tetangga kurang dari atau sama) dari matriks M x N. Analisis kompleksitas saya tidak sesuai dengan analisis mereka dan tampaknya bergantung pada kompleksitas loop bersarang.

Algoritme membuat persilangan yang membagi matriks menjadi empat "submasalah". Ia menemukan max di salib, memeriksa tetangga, dan berulang sesuai kebutuhan:

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)

Instruktur menyediakan kompleksitas untuk getMaximumsebagai O (len (lokasi)), getBetterNeighbordan getLocationInSelfsebagai O (1), getSubproblemContainingsebagai O (len (boundList)), dan semua panggilan pelacakan sebagai O (1). Ini crossProductdihitung sebagai:

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

Solusinya menyatakan, "satu panggilan fungsi (tidak termasuk panggilan rekursif) bekerja sebanding dengan m + n." Saya tidak mengerti ini.

Bukankah crossProductO (mn)?

Alasan saya adalah bahwa untuk matriks M x N, getMaximumharus melintasi salib pemisah (satu baris, satu kolom) yang memberikan kontribusi O (m + n). The getSubproblemContainingberkontribusi sesuatu linear, O (m) atau O (n). Segala sesuatu yang lain selain crossProductO (1), kompleksitas crossProducttidak tersedia, sehingga relasi perulangannya adalah

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)

Pengulangan berkurang melalui deret geometris menjadi O (m + n),

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

yang menghasilkan T (n, n) = O (n ^ 2). Solusi yang diberikan adalah O (n). The crossProductIstilah tampaknya perbedaan tersebut.

---

¹ Algoritma / implementasi kode ditulis oleh instruktur. Semua kesalahan gaya Pythonic adalah milik mereka (dan kemungkinan besar dibuat karena alasan pedagogis).

Answer 1

Jangan lupa apa ndan msebenarnya.

Ketika Anda mengatakan bahwa fungsi ini:

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

membutuhkan waktu O (mn), apa m dan n? Nah, m adalah ukuran list1 dan n adalah ukuran list2 (atau sebaliknya).

Ketika Anda mengatakan bahwa algoritme3 membutuhkan waktu O (mn), berapakah m dan n? Nah, m adalah jumlah baris dan n adalah jumlah kolom (atau sebaliknya).

Tunggu sebentar! Itu tidak sama! Kita harus menggunakan nama yang berbeda untuk variabel yang berbeda. Akan lebih mudah jika kita mengatakan bahwa crossProduct memiliki kompleksitas O (ab) di mana a adalah ukuran list1 dan b adalah ukuran list2 (atau sebaliknya). Anda tidak dapat memberi dua hal yang berbeda nama variabel yang sama dan kemudian menganggapnya adalah hal yang sama.

Jadi, apa a dan b itu?

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

Oke, jadi kita menyebutnya sekali dengan a = 1 dan b = n, dan kita menyebutnya lagi dengan a = m dan b = 1. Jadi kedua panggilan ini memiliki kompleksitas O (1n + m1) = O (n + m).