Big-O और जटिलता

वृद्धि, स्टॉपवॉच नहीं

Big-O स्थिरांक और मशीन गति को अनदेखा करके पूछता है: यदि इनपुट दोगुना हो, तो काम का क्या होगा? O(1) अपरिवर्तित, O(log n) एक चरण बढ़ता है, O(n) दोगुना, O(n log n) दोगुने से थोड़ा अधिक, O(n^2) चौगुना।

लूप से जटिलता पढ़ना

n वस्तुओं पर एक बार गुज़रना O(n) है। एक ही डेटा पर लूप के अंदर लूप O(n^2) है। हर चरण में सीमा आधी करना O(log n) है।

for x in arr:            # O(n)
    print(x)

for i in arr:            # O(n^2)
    for j in arr:
        print(i, j)

lo, hi = 0, len(arr) - 1 # O(log n)
while lo <= hi:
    mid = (lo + hi) // 2
    ...

समय बनाम स्थान

स्थान जटिलता इनपुट से परे अतिरिक्त मेमोरी गिनती है — कुछ वेरिएबल O(1), array की प्रति O(n), n गहराई की recursion O(n) स्टैक स्थान। इंटरव्यूअर अक्सर एक को दूसरे से बदलने को कहते हैं।

त्वरित जाँच: इनपुट 1,000 से 1,000,000 हो जाता है। O(log n) चरण गणना लगभग...

• तीन गुना
• ~10 चरण बढ़ती है
• 1000 गुना बढ़ती है