पुस्तक "परफेक्ट अल्गोरिथम। मूल बातें

हाय, हब्रोज़ितेली! यह पुस्तक ऑनलाइन एल्गोरिथम पाठ्यक्रमों पर आधारित है जो टिम राफगार्डन कोर्टेरा और स्टैनफोर्ड लागुनिटा पर ले जाती है, और ये पाठ्यक्रम स्टैनफोर्ड विश्वविद्यालय में कई वर्षों से छात्रों को दे रहे व्याख्यान के लिए धन्यवाद के बारे में आए हैं।

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

* 6.3। DSelect एल्गोरिथ्म

RSelect एल्गोरिथ्म को प्रत्येक इनपुट के लिए रैखिक समय में निष्पादित किया जाता है, जिसमें गणितीय अपेक्षा एल्गोरिदम द्वारा निष्पादित यादृच्छिक विकल्पों से जुड़ी होती है। क्या रैखिक चयन के लिए यादृच्छिककरण आवश्यक है? इस खंड में और आगे, इस समस्या को पसंद समस्या के लिए एक निर्धारक रैखिक एल्गोरिथ्म का उपयोग करके हल किया जाता है।

सॉर्टिंग कार्य के लिए, ओ (एन लॉग एन) रैंडमाइज्ड क्विकॉर्ट एल्गोरिथम का औसत रनटाइम नियतांक मर्जसॉर्ट एल्गोरिथ्म के समान है, और दोनों एल्गोरिदम क्विकॉर्ट और मर्जसॉर्ट व्यावहारिक उपयोग के लिए उपयोगी एल्गोरिदम हैं। दूसरी ओर, हालांकि इस खंड में वर्णित नियतात्मक रैखिक चयन एल्गोरिथ्म अभ्यास में ठीक काम करता है, यह RSelect एल्गोरिथ्म के साथ प्रतिस्पर्धा नहीं करता है। यह दो कारणों से होता है: DSelect एल्गोरिथ्म के संचालन समय में बड़े स्थिर कारकों और अतिरिक्त RAM के आवंटन और प्रबंधन से जुड़े एल्गोरिथम द्वारा किए गए कार्यों के कारण। फिर भी, एल्गोरिथ्म में विचार इतने अच्छे हैं कि मैं आपको उनके बारे में बताने में मदद नहीं कर सकता।

6.3.1। शानदार विचार: मंझले लोगों का ध्यान

RSelect एल्गोरिथ्म तेज है, क्योंकि एक उच्च संभावना है कि यादृच्छिक समर्थन तत्व काफी अच्छे होंगे, पृथक्करण के बाद इनपुट सरणी के लगभग संतुलित विभाजन प्रदान करते हैं, इसके अलावा, बहुत अच्छे सहायक तत्व तेजी से प्रगति करते हैं। यदि हमें यादृच्छिककरण का उपयोग करने की अनुमति नहीं है, तो हम बहुत अधिक काम किए बिना एक बहुत अच्छे संदर्भ तत्व की गणना कैसे कर सकते हैं?

एक नियतात्मक रैखिक विकल्प में सरल विचार "मंझले लोगों के मध्यिका" का उपयोग करना है, जो सच्चे मध्यस्थ के लिए एक प्रॉक्सी के रूप में है। एल्गोरिथ्म इनपुट सरणी के तत्वों को खेल टीमों के रूप में मानता है और दो राउंड में नॉकआउट टूर्नामेंट आयोजित करता है, जिसमें से चैंपियन सहायक तत्व है; अंजीर भी देखें। 6.1।


पहला राउंड एक समूह स्टेज है जिसमें पहले समूह के रूप में इनपुट ऐरे के 1-5 स्थान होते हैं, दूसरे समूह के रूप में 6-10 की स्थिति में तत्व, और इसी तरह। पांच तत्वों के समूह के पहले दौर के विजेता को तत्व के मध्य (यानी तीसरे सबसे छोटे) के रूप में परिभाषित किया गया है। चूंकि वहाँ है पांच तत्वों के समूह हैं पहले विजेता। (हमेशा की तरह, हम सादगी के लिए भिन्नता की उपेक्षा करते हैं।) एक टूर्नामेंट चैंपियन को पहले दौर के विजेताओं के मध्य के रूप में परिभाषित किया गया है।

6.3.2। DSelect एल्गोरिथ्म के लिए स्यूडोकोड

वास्तव में मध्ययुगीनों की गणना कैसे करें? उन्मूलन टूर्नामेंट के पहले चरण का कार्यान्वयन सरल है, क्योंकि मध्यिका की प्रत्येक गणना में केवल पांच तत्व शामिल हैं। उदाहरण के लिए, प्रत्येक ऐसी गणना को क्रूर बल द्वारा किया जा सकता है (प्रत्येक पांच संभावनाओं के लिए, विस्तार से जांचें कि क्या यह एक मध्य तत्व है) या सॉर्टिंग समस्या पर हमारी जानकारी का उपयोग कर (खंड 6.1.2)। दूसरे चरण को लागू करने के लिए, हम माध्यिका की गणना करते हैं पहले दौर के विजेता पुनरावर्ती हैं।


1-2 और 6–13 की लाइनें RSelect एल्गोरिथ्म के समान हैं। रेखाएँ 3-5 एल्गोरिथम का एकमात्र नया भाग हैं; वे इनपुट सरणी के माध्यिका की गणना करते हैं, RSelect एल्गोरिथ्म में लाइन की जगह लेते हैं, जो संदर्भ को यादृच्छिक रूप से चुनता है।

लाइन्स 3 और 4 एलिमिनेशन टूर्नामेंट के पहले राउंड के विजेताओं की गणना करते हैं, जहां पांच तत्वों के प्रत्येक समूह के मध्य तत्व की गणना ब्रूट फोर्स विधि या सॉर्टिंग एल्गोरिथ्म का उपयोग करके की जाती है, और इन विजेताओं को नए एरे सी में कॉपी किया जाता है। लाइन 5 टूर्नामेंट के चैंपियन की गणना करता है, जो पुन: सरणी के सी के मध्य की गणना करके टूर्नामेंट के चैंपियन की गणना करता है; चूँकि C की लंबाई है (अस्थायी रूप से) सरणी C. का क्रमिक आँकड़े। एल्गोरिथ्म के किसी भी चरण में कोई यादृच्छिकता का उपयोग नहीं किया जाता है।

6.3.3। DSelect एल्गोरिथ्म को समझना

संदर्भ तत्व की गणना करते समय DSelect एल्गोरिथ्म के लिए एक पुनरावर्ती कॉल खतरनाक चक्रीय लग सकता है। यह समझने के लिए कि क्या चल रहा है, चलिए सबसे पहले पुनरावर्ती कॉलों की कुल संख्या को निर्दिष्ट करते हैं।


सही उत्तर है: (c)। आधार मामले और खुशहाल मामले को संदर्भित करते हुए जिसमें संदर्भ तत्व आवश्यक आदेश आँकड़े हैं, DSelect एल्गोरिथ्म दो पुनरावर्ती कॉल करता है। यह समझने के लिए कि क्यों, इसे ज़्यादा मत करो; बस लाइन द्वारा DSelect एल्गोरिथ्म छद्म कोड लाइन की जाँच करें। लाइन 5 में एक पुनरावर्ती कॉल है और लाइन 11 या 13 पर एक अन्य है।

इन दो पुनरावर्ती कॉलों के बारे में दो भ्रामक सामान्य प्रश्न हैं। सबसे पहले, यह एक तथ्य नहीं है कि RSelect एल्गोरिथ्म सिर्फ एक पुनरावर्ती कॉल करता है, यही कारण है कि यह हमारे सॉर्ट एल्गोरिदम की तुलना में तेजी से काम करता है? क्या DSelect ने दो पुनरावर्ती कॉल करके इस सुधार को नहीं छोड़ा है? खंड 6.4 से पता चलता है कि लाइन 5 पर अतिरिक्त पुनरावर्ती कॉल के बाद से केवल एक अपेक्षाकृत छोटे उपशीर्षक (मूल सरणी में 20% तत्वों के साथ) को हल करना चाहिए, हम अभी भी रैखिक विश्लेषण बचा सकते हैं।

दूसरे, दो पुनरावर्ती कॉल मूलभूत रूप से भिन्न भूमिका निभाते हैं। लाइन 5 पर पुनरावर्ती कॉल का उद्देश्य वर्तमान पुनरावर्ती कॉल के लिए एक अच्छा संदर्भ तत्व निर्धारित करना है। लाइन 11 या 13 पर पुनरावर्ती कॉल का लक्ष्य सामान्य है - वर्तमान पुनरावर्ती कॉल द्वारा छोड़े गए शेष शेष कार्य को पुन: हल करना। फिर भी, DSelect एल्गोरिथ्म में पुनरावर्ती संरचना पूरी तरह से अन्य सभी विभाजनों और विजेता एल्गोरिदम की परंपरा का पालन करती है जो हमने अध्ययन किया था: प्रत्येक पुनरावर्ती कॉल सख्ती से महीन उपशीर्षक के साथ बाद के पुनरावर्ती कॉलों की एक छोटी संख्या बनाता है और उनके अतिरिक्त काम करता है। अगर हम इस बात से चिंतित नहीं थे कि मर्जेसॉर्ट या क्विकसॉर्ट जैसे एल्गोरिदम हमेशा के लिए चलेंगे, तो हमें DSlector एल्गोरिदम की चिंता नहीं करनी चाहिए।

6.3.4। DSelect एल्गोरिथ्म रनटाइम

DSelect एल्गोरिथ्म केवल एक स्पष्ट रूप से व्यक्त कार्यक्रम नहीं है जो सीमित समय में पूरा होता है - यह रैखिक समय में चलता है, इनपुट डेटा को पढ़ने के लिए केवल एक निरंतर कारक पर अधिक काम करना आवश्यक है।

प्रमेय 6.6 (DSelect एल्गोरिथ्म के ऑपरेटिंग समय)। लंबाई n, 1 के प्रत्येक इनपुट सरणी के लिए, DSelect एल्गोरिथ्म का रन समय O (n) है।

RSelect एल्गोरिथ्म के रन समय के विपरीत, जो सिद्धांत रूप में n (n2) से अधिक नहीं हो सकता है, DSelect एल्गोरिथ्म का रन समय हमेशा O (n) के बराबर होता है। फिर भी, व्यवहार में, आपको RSelect to DSelect एल्गोरिथम को प्राथमिकता देनी चाहिए, क्योंकि पहले एक ही स्थान पर काम करता है, और Theorem 6.1 में औसत ऑपरेटिंग समय "O (n)" में छिपा हुआ निरंतर, Theorem 6.6 में छिपे हुए निरंतरता से छोटा है।

»पुस्तक की अधिक जानकारी प्रकाशक की वेबसाइट पर पाई जा सकती है
» सामग्री
» अंश

ख़ारोज़ज़ाइटी के लिए कूपन पर 20% की छूट - एलगोरिदम

पुस्तक के पेपर संस्करण के भुगतान पर, पुस्तक का एक इलेक्ट्रॉनिक संस्करण ई-मेल द्वारा भेजा जाता है।

पुनश्च: पुस्तक की लागत का 7% नई कंप्यूटर पुस्तकों के अनुवाद में जाएगा, छपाई घर को सौंपी गई पुस्तकों की सूची यहां है ।