वृद्धि की दर, नहीं अभिन्न लागत
बिग ओ: मापता है कि किस प्रकार लागत की वृद्धि होती है
बिग ओ नोटेशन लागत की वृद्धि की दर को मापता है - नहीं अभिन्न लागत।
बिग ओ का प्रश्न है: जब इनपुट का आकार N दोगुना होता है, तो काम दोगुना होता है, चार गुणा होता है, या स्थिर रहता है?
दशमलव का 'O' खड़ा है 'order of magnitude.' पैरेंथीसिस के अंदर लिखी गई अभिव्यक्ति वृद्धि की ग्राफ़ की आकृति को निर्दिष्ट करती है।
![बिग ओ वृद्धि तालिका: N=10, 100, और 1,000 के लिए O(1), O(N), और O(N²) के लिए संचालन] (/static/diagrams/cs_algo_big_o_table.svg)
मुख्य जटिलता वर्ग:
- O(1) — स्थिर: लागत नहीं बढ़ती। उदाहरण: एक सरणी में एक मान द्वारा खोज। चाहे सरणी में 10 वस्तुएँ हों या 10 लाख, एक खोज एक खोज बनी रहती है।
- O(N) — लाइनीय: लागत इनपुट के साथ बढ़ती है। उदाहरण: एक सूची में एक बार प्रत्येक वस्तु को पढ़ना। दोगुना करें, दोगुना करें।
- O(N²) — वर्गीय: लागत इनपुट के वर्ग के रूप में बढ़ती है। उदाहरण: प्रत्येक वस्तु को प्रत्येक अन्य वस्तु के साथ तुलना करें। डबल करें, चार गुणा करें।
वृद्धि तुलना तालिका:
| N | O(1) | O(N) | O(N²) |
|---|------|------|-------|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
N=10 पर अंतर छोटा दिखता है। N=1,000 पर फासला बहुत बड़ा हो जाता है।
O(N) को O(N²) से तुलना करें
ऊपर दी गई वृद्धि तुलना तालिका का उपयोग करें।
N=1,000 पर: O(N) के लिए 1,000 संचालन। O(N²) के लिए 1,000,000 संचालन।
कोड की संरचना जो जटिलता का पता चलती है।
कोड से बिग ओ की पहचान कैसे करें
बिग ओ कोड की आकृति में छिपा होता है। चार पैटर्न अधिकांश मामलों को कवर करते हैं:
N आइटम पर एकल लूप: ओ(एन)
# ओ(एन): सूची के एक पास
for item in list_of_n_items:
process(item)N² आइटम पर नेस्टेड लूप: ओ(एन²)
# ओ(एन²): हर आइटम को हर अन्य आइटम के साथ जोड़ा जाता है।
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)स्थिर समय लुकअप: ओ(1)
मैट्रिक्स इंडेक्स एक्सेस, हैश टेबल लुकअप - साइज से परे किसी भी चीज के लिए एक कदम।
प्रश्न (प्रॉब्लम को हर चरण में आधा काटें): ओ(लोग एन)
बाइनरी सर्च: प्रत्येक जाँच लोकप्रिय वस्तुओं को आधा करती है।
---
ओ(एन²): एक लूप के भीतर सूची
# यह ओ(एन) जैसा दिखता है लेकिन वास्तव में ओ(एन²) है।
visited = []
for item in list_of_n_items:
if item not in visited: # स्कैन करता है: ओ(एन)
visited.append(item) # पूरे लूप: ओ(एन²)if item not in visited लाइन हर प्रतिक्रिया में visited के प्रत्येक तत्व को स्कैन करती है। एक सूची स्कैन का लागत ओ(एन) है। एक लूप जो एन बार चलता है, प्रत्येक ओ(एन) काम करता है: ओ(एन) × ओ(एन) = ओ(एन²)।
यह पैटर्न 1,000+ ओपन-सोर्स परियोजनाओं में प्रकट होता है। सहारा ले लें: visited = [] को visited = set() से बदलें। सेट सदस्य परीक्षण की लागत ओ(1) नहीं है ओ(एन)। एक बदलाव। समान परिणाम। एन=1,000 पर 1,000× तेजी से।
इस कोड को वर्गीकृत करें और ठीक करें
इस कोड को पढ़ें:
result = []
for name in student_names:
if name not in result:
result.append(name)नظرियाँ मिलती हैं पрак्षेत्र में
Big O वाइल्ड में
Big O सिर्फ सिद्धांत नहीं है। यह उसी काम पर 17 मिनट से 2 सेकंड तक प्रोग्राम बना देता है।
वास्तविक उदाहरण: निर्भरता चक्र की खोज निर्माण प्रणाली में।
जब आप सॉफ्टवेयर इंस्टॉल करते हैं, तो आपका कंप्यूटर एक ग्राफ़ की गिनती करता है: पैकेज ए को बी की आवश्यकता है, बी को सी की आवश्यकता है, और इसी तरह। एक निर्माण प्रणाली इस ग्राफ़ को चक्रों की जाँच करती है।
ओ(एन²) चक्र-खोज एल्गोरिदम एन=100 पैकेज पर ठीक काम करता है। एन=50,000 पैकेज (एक वास्तविक परियोजना) पर: यह 17 मिनट लेता है। ओ(एन) की सुधार: 10 सेकंड।
यह exact मान्या दोष गह्स (हस्केल कंपाइलर) में, पाइप (पाइथन पैकेज मैनेजर) में, मेवन (जावा निर्माण प्रणाली) में, कार्गो (रस्ट पैकेज मैनेजर) में, और 1000 से अधिक अन्य परियोजनाओं में मौजूद है।
क्योंकि उनके लेखक सावधान नहीं थे। visited = [] लिखा गया था जब N छोटा था। कोड कैल्सिफाइड हुआ। N बढ़ा। कोई भी 30 मिनट के निर्माण के समय तक नहीं देख सका।
Big O वह शब्दावली है जो आपको इसे नाम देने की अनुमति देती है - और ठीक करती है।
---
और अधिक जानने के लिए चाहें तो? हमारा unhamming पाठ्यक्रम एक पूरा अध्याय Big O पर शामिल करता है, MOAD-0001 (एक वास्तविक ओ(एन²) दोष जो 1000 से अधिक खुले स्रोत परियोजनाओं में पाया गया है), और नामांकित पैटर्न को ढूंढने की अनुमति देता है। देखें [Algorithmic Complexity: The Missing Chapter](/en/un/unhamming_algorithmic_complexity).
निर्माण समय का अनुमान
निर्माण प्रणाली ओ(एन²) चक्र-खोज का उपयोग करती है।
मापा निर्माण समय:
- एन=100 पैकेज: 0.01 सेकंड
- एन=1,000 पैकेज: 1 सेकंड
ओ(एन²) के लिए समय (N_new / N_old)² के अनुपात में स्केल करता है।
ओ(एन) के लिए समय (N_new / N_old) के अनुपात में स्केल करता है।