वह एल्गोरिदम जो समय पर पूरे हो जाएं: एक Complexity की जांच

आप एक function लिखते हैं, अपने test data पर चलाते हैं, और यह ठीक काम करता है। फिर यह production data — 500 की जगह 500,000 rows — पर जाता है और request timeout हो जाता है। यह लगातार होता है, और यह लगभग हमेशा एक complexity समस्या है जो छोटे scale पर reasonable दिखने वाले code के पीछे छिपी होती है।

आपका laptop आपसे झूठ क्यों बोला

एक O(n²) algorithm 100 items पर चलाने से 10,000 operations होते हैं। यह किसी भी machine पर तुरंत होता है। उसी algorithm को 100,000 items पर चलाएं और आप 10 billion operations पर हैं — milliseconds की जगह मिनट या घंटे। n से n² तक की jump जब तक n बड़ा न हो जाए तब तक खतरनाक नहीं लगती, और यही कारण है कि यह code review और local testing से बच निकलता है।

एक classic उदाहरण: nested loop के साथ duplicates की जांच करना।

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

यह O(n²) है। इसे एक set से बदलें:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

अब यह O(n) है। Set lookups average O(1) हैं, तो पूरा function linearly की जगह quadratically scale नहीं होता। 10,000 items पर यह लगभग 100 million comparisons और 10,000 के बीच का अंतर है।

Optimize करने से पहले measure करें

Guess न करें। timeit को microbenchmarks के लिए use करें:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

बड़े functions के लिए, cProfile के साथ profile करें:

python -m cProfile -s cumulative myscript.py

cumtime column को देखें। अगर एक function 90% runtime खा रहा है, वह आपका target है। ऐसे code को optimize करना जो bottleneck नहीं है आपका समय बर्बाद करता है और कोई gain के बिना complexity जोड़ता है।

सामान्य patterns जो चुपचाप धीमे हो जाते हैं

Repeated list membership checks। if x in my_list एक list के लिए O(n) है लेकिन एक set या dict के लिए average O(1) है। अगर आप एक loop के अंदर membership की जांच कर रहे हैं, तो वह O(n) check एक O(n) loop के अंदर आपको O(n²) देता है। list को एक set से बदलें और आप O(n) पर वापस हैं।

Loop में string concatenation। Python में, result += chunk strings के लिए एक loop के अंदर worst case में O(n²) है क्योंकि strings immutable हैं और हर concatenation पूरी चीज को copy करता है। इसकी जगह ''.join(chunks) use करें — यह string को एक बार बनाता है।

Sorting जब आपको इसकी जरूरत न हो। sorted() O(n log n) है। अगर आप इसे loop के अंदर सिर्फ हर iteration में max या min खोजने के लिए call कर रहे हैं, तो max()/min() (O(n)) use करें या बेहतर है, एक heap (heapq) अगर आपको बार-बार चलने वाली extreme की जरूरत है। heapq.nlargest(k, data) O(n log k) है, जब k छोटा है तो पूरी list को sort करने से बहुत सस्ता है।

Memoization के बिना recursive functions। Naive recursive Fibonacci O(2ⁿ) है क्योंकि यह एक ही subproblems को बार-बार recompute करता है। functools.lru_cache जोड़ें और यह O(n) तक गिरता है:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Real code से Big O को fast पढ़ना

Same input पर nested loops count करें — यह आमतौर पर आपका exponent है। एक single loop O(n) है। एक loop एक loop के अंदर O(n²) है जब तक inner loop का range shrink न हो (जैसे bubble sort के optimized form में, अब भी O(n²) worst case है लेकिन कम comparisons)। Recursive calls जो problem को आधा बाँटते हैं, जैसे binary search या merge sort, O(log n) या O(n log n) की ओर इशारा करते हैं। Recursive calls जो हर level पर कई calls में branch करते हैं, जैसे naive Fibonacci, exponential time की ओर इशारा करते हैं — एक strong signal कि आपको memoization या एक iterative rewrite की जरूरत है।

एक अच्छी habit: इससे पहले कि आप nested loops या recursion लिखें user-facing data के लिए, पूछें कि n production में realistically क्या हो सकता है, आपकी test file में नहीं। अगर n छः अंकों तक hit कर सकता है, तो एक O(n²) solution को ship होने से पहले दूसरा look लेने की जरूरत है।

Complexity analysis, sorting algorithms, और profiling tools पर अधिक जानकारी के लिए, Korra Studio पर Python और Computer Science segments को देखें।