नेस्टेड लूप जटिलता

Question

मैं एमआईटी 6.006 ओपनकोर्सवेयर के माध्यम से काम कर रहा हूं, जैसा कि 2011 फॉल में पढ़ाया गया था । समस्या 1.2c एक एल्गोरिथ्म ¹ का समय जटिलता के लिए पूछता है जो एक एम एक्स एन मैट्रिक्स का एक चरम तत्व (यानी सभी पड़ोसी कम या बराबर) पाता है। मेरा जटिलता विश्लेषण उनके मेल नहीं खाता है और नेस्टेड लूप की जटिलता पर टिका हुआ प्रतीत होता है।

एल्गोरिथ्म एक क्रॉस बनाता है जो मैट्रिक्स को चार "उपप्रोब्लेम्स" में विभाजित करता है। यह क्रॉस पर अधिकतम पाता है, पड़ोसियों की जांच करता है, और आवश्यकतानुसार पुनरावर्ती करता है:

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)

प्रशिक्षक getMaximumO (len (स्थान)) के रूप में जटिलता प्रदान करता है , getBetterNeighborऔर getLocationInSelfO (1) के getSubproblemContainingरूप में O (len (बाध्यतावादी)), और O (1) के रूप में सभी ट्रेस कॉल करता है। इस crossProductप्रकार गणना की जाती है:

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

समाधान बताता है, "फ़ंक्शन का एक एकल कॉल (पुनरावर्ती कॉल की गिनती नहीं) एम + एन के लिए आनुपातिक काम करता है।" मुझे यह समझ में नहीं आता है।

है नहीं crossProductहे (MN)?

मेरा तर्क यह है कि M x N मैट्रिक्स के लिए, getMaximumविभाजन क्रॉस (एक पंक्ति, एक कॉलम) को पार करना होगा जो O (m + n) का योगदान देता है। getSubproblemContainingयोगदान कुछ रैखिक हे (एम) या हे (एन)। इसके अलावा सब कुछ crossProductO (1) है, crossProductप्रदान नहीं किए जाने की जटिलता , ताकि पुनरावृत्ति संबंध हो

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)

ज्यामिति श्रृंखला के माध्यम से O (m + n) तक पुनरावृत्ति कम हो जाती है,

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

जो पैदावार T (n, n) = O (n ^ 2) है। प्रदान किया गया समाधान O (n) है। यह crossProductशब्द विसंगति प्रतीत होता है।

---

¹ एल्गोरिथ्म / कोड कार्यान्वयन प्रशिक्षक द्वारा लिखा गया है। सभी पाइथोनिक शैली की त्रुटियां उनकी हैं (और संभवतः शैक्षणिक कारणों से बनाई गई हैं)।

Answer 1

क्या nऔर mवास्तव में क्या हैं मत भूलना ।

जब आप कहते हैं कि यह फ़ंक्शन:

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

O (mn) समय लेता है, m और n क्या हैं? खैर, मी list1 का आकार है और n सूची 2 (या इसके विपरीत) का आकार है।

जब आप कहते हैं कि एल्गोरिदम 3 O (mn) समय लेता है, तो m और n क्या हैं? खैर, मी पंक्तियों की संख्या है और n कॉलम (या इसके विपरीत) की संख्या है।

डटे रहो! वे एक ही बात नहीं कर रहे हैं! हमें विभिन्न चर के लिए अलग-अलग नामों का उपयोग करना चाहिए। यह आसान होगा यदि हमने कहा कि क्रॉसप्रोडक्ट में O (ab) जटिलता है जहां a सूची 1 का आकार है और b सूची 2 (या इसके विपरीत) का आकार है। आप दो भिन्न चीजों को एक ही चर नाम नहीं दे सकते हैं और फिर मान सकते हैं कि वे एक ही चीज हैं।

तो एक और बी क्या हैं?

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

ठीक है, इसलिए हम इसे एक बार = 1 और बी = एन के साथ कहते हैं, और हम इसे फिर से एक = एम और बी = 1 के साथ कहते हैं। तो इन दोनों कॉल में O (1n + m1) = O (n + m) जटिलता है।