कोड की संरचना जटिलता कैसे प्रकट करती है

कोड से Big O की पहचान कैसे करें

Big O आपके कोड के आकार में छुपा होता है। चार पैटर्न अधिकांश मामलों को कवर करते हैं:

N आइटम्स पर एकल लूप: O(N)

# O(N): सूची के माध्यम से एक पास
for item in list_of_n_items:
    process(item)

नेस्टेड लूप्स, प्रत्येक N आइटम्स पर: O(N²)

# O(N²): हर आइटम को हर दूसरे आइटम के साथ जोड़ा गया
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

निरंतर-समय खोज: O(1)

सरणी सूचकांक पहुंच, हैश तालिका खोज — आकार की परवाह किए बिना एक कदम।

विभाजन-विजय (प्रत्येक कदम में समस्या को आधा करें): O(log N)

बाइनरी खोज: प्रत्येक जांच शेष आइटम्स को आधा करती है।

---

छिपा हुआ O(N²): एक लूप के अंदर एक सूची

# यह O(N) दिखता है लेकिन यह वास्तव में O(N²) है
visited = []
for item in list_of_n_items:
    if item not in visited:   # सभी visited को स्कैन करता है: O(N)
        visited.append(item)  # पूरा लूप: O(N²)

if item not in visited पंक्ति प्रत्येक पुनरावृत्ति में visited के हर तत्व को स्कैन करती है। एक सूची स्कैन O(N) की लागत है। एक लूप जो N बार चलता है, प्रत्येक O(N) काम करता है: O(N) × O(N) = O(N²)।

यह पैटर्न 1,000+ ओपन-सोर्स प्रोजेक्ट्स में दिखता है। फिक्स को एक वर्ण की आवश्यकता होती है: visited = [] को visited = set() से बदलें। सेट सदस्यता परीक्षण O(1) लागत है, O(N) नहीं। एक परिवर्तन। समान परिणाम। N=1,000 पर 1,000 गुना तेज़।

इस कोड को वर्गीकृत & ठीक करें

यह कोड पढ़ें:

result = []
for name in student_names:
    if name not in result:
        result.append(name)

सिद्धांत वास्तविकता से मिलता है

वाइल्ड में Big O

Big O केवल सिद्धांत नहीं है। यह उन प्रोग्राम्स को अलग करता है जो सेकंड में समाप्त होते हैं उन प्रोग्राम्स से जो 17 मिनट लेते हैं — बिल्कुल एक ही कार्य पर।

वास्तविक उदाहरण: एक बिल्ड सिस्टम में निर्भरता चक्र पहचान।

जब आप सॉफ़्टवेयर स्थापित करते हैं, तो आपका कंप्यूटर निर्भरता का एक ग्राफ हल करता है: पैकेज A को B की आवश्यकता है, B को C की आवश्यकता है, इत्यादि। एक बिल्ड सिस्टम इस ग्राफ में चक्रों की जांच करता है।

एक O(N²) चक्र-पहचान एल्गोरिदम N=100 पैकेज पर ठीक काम करता है। N=50,000 पैकेज पर (एक वास्तविक प्रोजेक्ट): यह 17 मिनट लेता है। O(N) फिक्स: 10 सेकंड।

यह सटीक दोष GHC (Haskell संकलक), pip (Python पैकेज प्रबंधक), Maven (Java बिल्ड सिस्टम), Cargo (Rust पैकेज प्रबंधक), & 1,000+ अन्य प्रोजेक्ट्स में मौजूद है।

यह नहीं है कि उनके लेखक लापरवाह थे। visited = [] तब लिखा गया था जब N छोटा था। कोड जमा हुआ। N बढ़ा। किसी को नहीं पता जब तक बिल्ड आधे घंटे नहीं लगे।

Big O वह शब्दावली है जो आपको नाम देने देती है कि क्या हुआ — & इसे ठीक करें।

---

और गहराई से जाना चाहते हैं? हमारा unhamming कोर्स Big O पर एक पूरा अध्याय शामिल करता है, MOAD-0001 (1,000+ ओपन-सोर्स प्रोजेक्ट्स में पाया गया एक वास्तविक O(N²) दोष), & एक पैटर्न को नाम देना आपको इसे हर जगह खोजने देता है। देखें The Missing Chapter: Algorithmic Complexity।

बिल्ड बार का पूर्वानुमान लगाएँ

एक बिल्ड सिस्टम O(N²) चक्र पहचान का उपयोग करता है।

मापे गए बिल्ड समय:

- N=100 पैकेज: 0.01 सेकंड

- N=1,000 पैकेज: 1 सेकंड

O(N²) के लिए: समय (N_new / N_old)² के रूप में स्केल करता है।

O(N) के लिए: समय (N_new / N_old) के रूप में स्केल करता है।