un

guest
1 / ?
back to lessons

कोर्स ने क्या कवर किया और क्या छोड़ दिया

Hamming के कोर्स में एनालॉग-टू-डिजिटल कन्वर्जन, त्रुटि सुधार, सिमुलेशन, सांख्यिकी, संख्या विश्लेषण, और n-आयामी भूगोल शामिल थे। उन्होंने संगत रूप से - सिग्नल प्रोसेसिंग, कोडिंग थ्योरी, डिजिटल फिल्टर सभी कम्प्यूटेशनल रीजनिंग की आवश्यकता का सोचा।

उन्होंने एल्गोरिदमिक कॉम्प्लेक्सिटी को सिस्टमैटिक रूप से नहीं सिखाया।

Algorithmic Complexity Growth Curves: O(1) flat, O(log N) gentle, O(N) diagonal, O(N²) parabola

क्यों ऐसा खाली था

Hamming की मानसिक मॉडल उस युग में बना जब हार्डवेयर बॉटलनेक्स्ट्स नियंत्रित करते थे। प्रश्न: कितने ट्रांजिस्टर प्रति चिप? एल्गोरिदम हार्डवेयर उपलब्ध पर चला। N=100 पर, एक O(N²) एल्गोरिदम 10,000 ऑपरेशन्स का खर्च आता है। N=1,000 पर, यह 1,000,000 का खर्च आता है। N=10,000 (आज के दिन के विशेषज्ञ ग्राफ, सामाजिक नेटवर्क, और पैकेज मैनेजर्स में नियमित): यह 100,000,000 का खर्च आता है। Hamming के साथ काम करते समय O(N) और O(N²) के बीच का अंतर दिखाई नहीं देता था, और उसके छात्रों के जीवन के स्केल पर यह कैटनास्ट्रोफिक था।

डोनाल्ड क्नوث ने 1968 में The Art of Computer Programming प्रकाशित किया - Hamming के पूर्ण अनुसंधान उत्पादकता के उसी साल। बिग ओ नोटेशन 1970 के और 1980 के दशक में स्टैंडर्ड एल्गोरिदमिक वाक्य पाठ्यक्रम में बन गया। Hamming के कोर्स की तारीख 1995 है, लेकिन उनकी कम्प्यूटेशन मॉडल की मानसिक अवधारणा पहले की गई थी। उन्होंने इस अध्याय को नहीं अपडेट किया।

Hamming के अपने परीक्षण द्वारा एक मौलिक

Hamming का परीक्षण: (1) यह समय के साथ टिका रहता है, (2) क्षेत्र के बाकी हिस्सों को इसका उपयोग करके निर्धारित किया जा सकता है।

बिग ओ दोनों परीक्षणों को पास करता है। वृद्धि दर विश्लेषण ने क्नوث के बाद से टिका रखा है। इसका उपयोग एल्गोरिदम चयन, डेटा संरचना चयन, और प्रदर्शन पूर्वानुमान के लिए किया जाता है - प्रैक्टिकल कम्प्यूटर साइंस का अधिकांश क्षेत्र 'N के रूप में लागत कैसे बढ़ती है?' पूछता है। Hamming ने सबसे टिकाऊ अपने क्षेत्र के मौलिक को अनजाने में छोड़ दिया।

बिग ओ के रूप में एक मौलिक

Hamming ने कहा कि मौलिक समय के साथ टिका रहता है। उन्होंने कलकुलस का उदाहरण दिया: एक बार बनाया गया, यह दूरस्थ विज्ञान, इंजीनियरिंग, अर्थशास्त्र, और जीव विज्ञान के लिए सदियों तक लागू होता है। परिधीय उपकरण आते जाते हैं; मौलिक संपला।

Hamming ने कहा कि मौलिक समय के साथ टिका रहता है। एल्गोरिदमिक कॉम्प्लेक्सिटी को Hamming के अपने परीक्षण के दोनों मानदंडों के अनुसार मौलिक माना जाता है? दोनों कriteria: (1) समय की लंबाई, और (2) इसका उपयोग करके क्षेत्र के बाकी हिस्सों को निर्धारित किया जा सकता है। अपनी स्थिति को संगत रूप से तर्क दें।

लागत का विकास

बिग ओ लागत की वृद्धि को मापता है जब इनपुट बढ़ता है। स्थिरांक कारक को नहीं - दर। N=100 पर 'कुछ मिलीसेकंड' में दो एल्गोरिदम अगर एक O(N) समय में चल रहा हो और दूसरा O(N²) तो N=10,000 पर 10,000 गुणा भिन्न हो सकते हैं।

सामान्य जटिलता वर्ग

O(1) - स्थिर। N के आधार पर समान लागत। उदाहरण: कुंजी द्वारा हैश टेबल खोज, मैट्रिक्सccess द्वारा मैट्रिक्स, स्टैक पुश/पॉप। N को दोगुना करें - कुछ नहीं बदलें।

O(1) वृद्धि की ग्राफ: समतल क्षैतिज रेखा

O(log N) - लघु-अकार। प्रत्येक चरण आधे बचे काम को हलता है। उदाहरण: एक सॉर्टेड मैट्रिक्स में बाइनरी खोज, गेम इंजन में BVH स्पेशियल क्वेरी, संतुलित बाइनरी ट्री संचालन। N=1,000,000 पर: log₂(1,000,000) ≈ 20 चरण।

O(log N) वृद्धि की ग्राफ: तेजी से बढ़ना फिर स्तरण

O(N) - लाइनियर। लागत इनपुट के साथ बढ़ती है। उदाहरण: एक सूची में लाइनियर स्कैन, फ़ाइल पढ़ना, एक संग्रह में वस्तुओं की गिनती। N=10,000 पर: 10,000 संचालन।

O(N) वृद्धि की ग्राफ: सीधी कोणीय रेखा

O(N log N) - लाइनियरिथ्मिक। लगभग लाइनियर, थोड़ा बदतर। उदाहरण: मेर्ज सॉर्ट, कार्यदिवस के लिए सबसे काम के एल्गोरिदम (Dijkstra के साथ ही पूल)। N=10,000 पर: ~133,000 संचालन।

O(N log N) वृद्धि की ग्राफ: थोड़ा सीधी की तुलना में अधिक कोणीय

O(N²) - वर्गीय। लागत विस्फोट करती है। उदाहरण: एक सूची में list.contains() को उसी सूची पर लूप में कॉल किया गया, बबल सॉर्ट, सीधे सभी तुलना। N=1,000 पर: 1,000,000 संचालन। N=10,000 पर: 100,000,000 संचालन।

O(N²) वृद्धि की ग्राफ: परिक्रमा विस्फोट

O(2^N) — Exponential. असंभव है किसी भी अर्थपूर्ण पैमाने पर इसका उपयोग। उदाहरण: ब्रूट फोर्स कॉम्बिनेटरिक्स, सभी उपसमुच्चय खोजना। N=30 पर: 1,000,000,000 संचालन।

O(2^N) वृद्धि ग्राफ: विस्फोटक वृद्धि

पैमाना जो इसे दिखाता है

N=10 संचालन:
  O(N):   10
  O(N²):  100
  अनुपात:  10x

N=1,000 संचालन:
  O(N):   1,000
  O(N²):  1,000,000
  अनुपात:  1,000x

N=10,000 संचालन:
  O(N):   10,000
  O(N²):  100,000,000
  अनुपात:  10,000x

N=10 पर, अंतर केवल थोडा सा दिखता है। N=10,000 पर, O(N²) एल्गोरिदम 10,000 गुना धीमा होता है। यही कारण है कि MOAD-0001 को 1993 में 50 नोड वाले ग्राफ पर चलने के लिए दशकों तक अनदेखा किया गया: 2020 में उसी कोड को 50,000 नोड वाले निर्भरता ग्राफ पर चलाया गया।

तीन संचालनों का वर्गीकरण

इन कॉम्प्लेक्सिटी वर्गों को सीधे संचालन पर लागू करें। प्रत्येक के लिए मुख्य प्रश्न: N बढ़ते हुए, इसे कितने संचालन लेता है?

प्रत्येक संचालन के लिए नीचे दिए गए, बड़ ओ कॉम्प्लेक्सिटी दें और एक वाक्य में इसके कारण की व्याख्या करें: (a) शब्द की खोज एक पेज नंबर द्वारा शब्दकोश में (b) शब्द की खोज शब्दकोश के हर पेज पर (c) कार्डों की एक ढेर को मिश्रित करके हर संभव व्यवस्था का प्रयास करके एक सॉर्ट किया जाए प्रत्येक के लिए एक व्याख्या का एक वाक्य लिखें।

सही कोड, गलत वृद्धि ग्राफ

O(N²) समय में काम करने वाले सही कोड को O(N) कोड के समान परिणाम प्राप्त होते हैं। परीक्षण सफल होते हैं। निर्यात संगत होता है। कोई अपवाद नहीं जलता है। सीमा का दोष छिपा होता है।

यह गुण O(N²) विकृतियों को sedimentary बना देता है: वे काम कर रहे कोड के अंदर कैल्सिफाई होती हैं और जब N का प्रतिच्छेद एक सीमा से अधिक होता है, तब ही स्पष्ट होती हैं। कोड बदला नहीं गया। इसके चारों ओर का विश्व बदल गया।

MOAD-0001: sedimentary विकृति

सबसे व्यापक मामला: visited = [] एक ग्राफ ट्रैवर्सल लूप के अंदर।

visited = []
for node in graph:
    if node not in visited:  # O(N) स्कैन प्रति कॉल
        visited.append(node)
        process(node)

प्रत्येक not in visited कॉल 0 से len(visited)-1 तक के आइटम्स का स्कैन करता है। N कॉल × N/2 औसत स्कैन किए गए आइटम्स = O(N²) कुल। सुधार: एक ही लाइन।

visited = set()  # O(1) सदस्यता परीक्षण
for node in graph:
    if node not in visited:  # O(1) हैश लुकअप
        visited.add(node)
        process(node)

समान व्यवहार। समान आउटपुट। समान परीक्षण सफल। वृद्धि दर O(N) से O(N²) में बदल गई। N=1,000 पर: 1,000 गुणा तेज। N=10,000 पर: 10,000 गुणा तेज।

क्यों हैमिंग के युग ने इसे बोया

प्रारंभिक Java और C में, ArrayList (डाइनेमिक आरे) वैकल्पिक सेक्वेंशियल कंटेनर था। सेट्स मौजूद थे, लेकिन वे निर्माण नहीं थे - विक्रेता वह जानते थे जो सबसे अधिक सामान्य था। 1993 में एक ग्राफ ट्रैवर्सल पर N=50 पर माइक्रोसेकंड में चला। इस कोड को वर्जन नियंत्रण में रखा गया, कॉपी किया गया, लाइब्रेरी में लपेटा गया, पैकेज मैनेजर में भेजा गया। 2020 तक, इसी पैटर्न ने 50,000 नोड वाले निर्भरता ग्राफ्स पर चला।

1993 में कोड सही था। यह 2020 में जब इसके चारों ओर का विश्व बदल गया, तब महंगा बन गया। हैमिंग के युग ने इस प्रकार की विकृति को बोया क्योंकि उन्होंने कभी वृद्धि-दर के सवाल का नाम नहीं दिया।

संकल्प और सुधार

संकल्प का लागू करें: O(N²) पैटर्न का पता लगाएं, सुधार की पहचान करें।

आप इस कोड को प्रोडक्शन कोडबेस में पाते हैं: `if item not in visited_list: visited_list.append(item)` 50,000 आइटमों के लूप के अंदर। पूरे लूप के लिए सदस्यता परीक्षण कितने औसत संचालन करता है, और इसे ठीक करने के लिए `visited_list` को किस चीज से बदला जाना चाहिए?

नाम बदलने के क्या परिवर्तन हुए

बिग ओ को नाम नहीं था, तब प्रोग्रामरों ने 'यह धीरे चल रहा है' पाया। वे प्रोफ़ाइल किये, सुधारे। लेकिन वे इस पैटर्न को सिख नहीं सके - वे केवल उदाहरण पर इशारा कर सके। एक पैटर्न जिसका नाम नहीं होता, वह प्रसारित नहीं हो सकता।

बिग ओ को नाम मिलने के बाद, एक वरिष्ठ इंजीनियर कह सकता था 'यह O(N²) है, इसे सेट के साथ बदल दें' और एक नौसिखिया इंजीनियर इस पैटर्न को समझ सकता था, इसका उपयोग कर सकता था, और इसे सिख भी सकता था। नाम ने पैटर्न को एक स्थानांतरित करने योग्य ज्ञान का एक इकाई बना दिया।

हैमिंग ने इस प्रकार के अन्य क्षेत्रों में इस प्रकार की गतिविधि जानी। उन्होंने 1960s में 'स्पागेटी कोड' का नाम देने का वर्णन किया, जिससे समुदाय को माना गया, चर्चा की और अंत में एक ऐसी विसंगति को पहचान सका, जिसे सभी ने अनुभव किया था, लेकिन किसी ने भी नाम नहीं दिया था। इसी तरह की विसंगतियों को पहचान सकते हैं।

अनहैमिंग को हैमिंग ने युक्तियां छोड़ दी: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N)। ये नाम आपको कोड पढ़ने पर ग्रोथ कुर्व को देखने देते हैं, पैमाने पर प्रदर्शन का अनुमान लगा सकते हैं, और सटीक सुधार संवाद कर सकते हैं। वे हैमिंग के अपने परीक्षण को संतुष्ट करते हैं: स्थायी, और क्षेत्र के बाकी में अधिकांश को जनरेट करने वाले।

संख्या सिद्धांत से कंप्यूटर साइंस तक

बिग ओ नोटेशन कंप्यूटर साइंस में नहीं उत्पन्न हुआ। यह संख्या सिद्धांत में 74 साल पहले डोनाल्ड कंथ के इस्तेमाल से पहले पुरे गणित में उत्पन्न हुआ।

पॉल बाखमैन, 1894

पॉल बाखमैन, एक जर्मन गणितज्ञ, ने 1894 में अपनी किताब डी एनालिटिश ज़ाहलेन्थियोरी (एनालिटिक नंबर थेरी) में ओ नोटेशन को पेश किया। उन्हें एक संक्षिप्त तरीके से एक अन्य की तुलना में फंक्शन की वृद्धि को व्यक्त करने की आवश्यकता थी। लिखना 'f(n) = O(g(n))' का अर्थ था: f को g की तुलना में अधिक तेज़ी से बढ़ना चाहिए। यह संख्या सिद्धांत के अनुमानों के त्रुटि शब्दों को बिना सही स्थिरांक को ट्रैक किए की अनुमति देता था।

बाखमैन ने लूप, डेटा संरचनाओं, या कार्यक्षमता के बारे में सोचा था। उन्होंने प्राइम नंबर के वितरण के बारे में सोचा था, विशेष रूप से प्राइम नंबर सिद्धांत के त्रुटि शब्दों में।

एडमंड लैंडाउ, 1909

एडमंड लैंडाउ, एक अन्य जर्मन गणितज्ञ, ने 1909 में हैंडबुक ऑफ़ द डिस्ट्रीब्यूशन ऑफ़ प्राइम नंबर्स (प्राइम नंबरों की वितरण के हैंडबुक) में इस नोटेशन को लोकप्रिय बनाया। लैंडाउ ने इसी तरह के नोटेशन o (छोटे-o) को भी पेश किया और ओ नोटेशन की परिवार को इतना व्यापक बना दिया कि इसे बाखमैन-लैंडाउ नोटेशन या सिर्फ लैंडाउ नोटेशन के रूप में जाना गया।

छह दशकों तक, ओ नोटेशन ने पूरी तरह से गणित में रहते हुए। किसी भी प्रोग्रामर ने इसके बारे में सोचा नहीं।

डोनाल्ड कνούथ, 1968 & 1976

डोनाल्ड कνούथ ने नोटेशन को कंप्यूटर साइंस में अनुवादित किया। कंप्यूटर साइंस की कला (भाग 1, 1968) में, कνούथ ने एल्गोरिदम के रनिंग टाइम का वर्णन करने के लिए ओ नोटेशन का उपयोग किया - एक सीधा बाचमान का उपकरण अन्य क्षेत्र में प्रत्यक्ष प्रत्यारोपण। वह पहला व्यक्ति था जिसने इसके विशद रूप से एल्गोरिदम विश्लेषण पर लागू किया।

1976 में, कνούथ ने SIGACT न्यूज में एक छोटे से लेख 'बिग ओमाइक्रोन और बिग ओमेगा और बिग थीटा' प्रकाशित किए। उन्होंने नीचे के सीमा के लिए ओमेगा (Omega) और टाइट बाउंड्स के लिए थीटा पेश किया, जो आज कंप्यूटर साइंस उपयोग करते हैं। उन्होंने इन सिम्बल्स के उपयोग के लिए क्षेत्र में स्टैंडर्डाइजेशन का समर्थन किया - एक निर्णय की कार्रवाई जिसने अपनाने में तेजी लाई।

1980 के दशक के अंत तक, बिग ओ हर एल्गोरिदम के पाठ्यक्रम में दिखाई दिया। 1990 के दशक तक, यह मानक साक्षात्कार का वाक्यांश बन गया।

एक 74-वर्षीय यात्रा

1894 — बाखमान ने ओ को संख्या सिद्धांत में पेश किया।
1909 — लैंडाउ ने ओ, o, और पूरी नोटेशन परिवार को लोकप्रिय बनाया।
1953 — हैमिंग बेल लैब्स में अनुसंधान शुरू करते हैं (कभी भी CS टूल के रूप में बिग ओ नहीं सीखते हैं)
1968 — कνούथ ने TAOCP Vol. 1 में एल्गोरिदम विश्लेषण पर ओ को लागू किया।
1976 — कνούथ ने ओमेगा और थीटा जोड़े, और स्टैंडर्डाइजेशन के लिए तर्क दिया।
1980s — बिग ओ सभी CS कार्यक्रमों में प्रवेश करता है।
1993 — MOAD-0001 सेडिमेंट परत का गठन होता है प्रोडक्शन कोड में
1995 — हैमिंग ने अंतिम संस्करण की कक्षा सिखाई; कभी बिग ओ का कवर नहीं किया।
2026 — MOAD-0001 को 1000+ ओपन-सोर्स परियोजनाओं में पाया जाता है।

बाखमान का टूल 74 साल गणित में सिर्फ संख्या सिद्धांत में बिताया। हर गणितज्ञ के लिए दिखाई देता था, लेकिन हर प्रोग्रामर के लिए दिखाई नहीं। कνούथ ने प्रत्यारोपण देखा। हैमिंग - उसी कालखंड में, उसी कंप्यूटिंग समुदाय के साथ - कभी अपने कोर्स में इसका हिस्सा नहीं बना सका।

कुण्ठ की स्टैंडर्डाइजेशन का क्यों महत्व था

कुण्ठ के 1976 के लेख ने ओमेगा और थीटा के पेश करने के अलावा कुछ और किया। उन्होंने तर्क दिया कि क्षेत्र को संगत नोटेशन की आवश्यकता है, और असंगत नोटेशन सक्रिय रूप से हानिकारक था। अलग-अलग पाठ्यक्रमों ने ओ को अलग-अलग चीजों का अर्थ दिया - कभी-कभी एक उच्च सीमा के लिए, कभी-कभी एक अनुमान के लिए, कभी-कभी स्थिरांक की महत्ता के बिना विशेषज्ञता के बिना। कुण्ठ ने इसे साफ कर दिया।

यह हैमिंग के पैटर्न-नेमिंग डायनेमिक को स्वयं नोटेशन पर लागू करता है। क्नوث ने सिम्बल्स को स्टैंडर्ड किया था, तब इंजीनियर्स प्रेसिस्ली कॉम्प्लेक्सिटी क्लेम्स को टेक्स्टबुक्स, पेपर्स, या टीम्स के बीच कॉमन कर नहीं सकते थे। स्टैंडर्डाइजेशन के बाद, 'यह O(N लॉग N) में चल रहा है' किसी के द्वारा भी कहे जाने पर ठीक एक ही मतलब ले आता था।

क्नوث ने अनौपचारिक अनुवाद भी दिया: 'O(f(n)) का अर्थ है कि रनिंग टाइम किसी निश्चित कारक के बारे में f(n) से अधिक होता है, सभी पर्याप्त रूप से बड़े n के लिए।' यह व्याख्या - उच्च सीमा, एक स्थिर कारक के लिए, बड़े इनपुट के लिए - प्रत्येक प्रोग्रामर को सीखने वाली मानक धारणा बन गई।

बाखमान ने 1894 में संख्या सिद्धांत के लिए ओ नोटेशन का आविष्कार किया। कुण्ठ ने 1968 में एल्गोरिदम विश्लेषण के लिए इसे अपनाया। कंप्यूटिंग, पैमाने, या प्रोग्रामर के काम करने के तरीके में क्या बदला - ताकि एक स्वयं गणितज्ञ का टूल सॉफ्टवेयर इंजीनियर्स के लिए आवश्यक वाक्यांश बन जाए? कम से कम दो कारकों को दें।