[संगीत बजाना] 

प्रोफेसर: ठीक है। इस CS50 है और यह है सप्ताह के अंत में तीन। इसलिए हम आज यहाँ हो, नहीं सैंडर्स में बजाय Weidner लाइब्रेरी में थियेटर,। जो के अंदर एक स्टूडियो है हौसर स्टूडियो के रूप में जाना जाता है, या हम स्टूडियो एच कहते हैं, या करेगा करेगा आपको लगता है कि मजाक का आनंद लिया, तो हम say--, यह वास्तव में से है सहपाठी, मार्क, ऑनलाइन, जो ट्विटर के माध्यम के रूप में ज्यादा का सुझाव दिया। अब के बारे में क्या अच्छा है एक स्टूडियो में यहाँ किया जा रहा है मैं इन हरी से घिरा रहा है कि दीवारों, एक हरे रंग की स्क्रीन या chromakey, इसलिए CS50 जिसका अर्थ है कि बात करने के लिए मेरे लिए अनजान उत्पादन टीम, अभी, डाल सकता है मुझे सबसे दुनिया में कहीं भी, बेहतर या बदतर के लिए। 

अब आगे क्या, समस्या सेट निहित है दो, इस सप्ताह के लिए अपने हाथ में है लेकिन समस्या के साथ सेट तीन यह आने वाले सप्ताह, आप के साथ चुनौती दी जाएगी 15 की तथाकथित खेल, एक पुरानी पार्टी के पक्ष कि आप प्राप्त कर याद हो सकता है एक पूरी गुच्छा है कि एक बच्चे के रूप में नीचे, ऊपर स्लाइड कर सकते हैं कि संख्या की, छोड़ दिया और सही, और एक अंतर है पहेली, भीतर जो में आप वास्तव में उन लोगों के लिए पहेली टुकड़े स्लाइड कर सकते हैं। अंततः आप इस प्राप्त कुछ अर्द्ध यादृच्छिक क्रम में पहेली, और लक्ष्य के लिए है नीचे से ऊपर यह तरह, एक से, सही करने के लिए छोड़ दिया 15 के माध्यम से सभी तरह। 

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

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

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

चयन बनाम बुलबुला तरह क्रमबद्ध मर्ज प्रकार बनाम। अब वे सभी में चला रहे हैं, सिद्धांत, एक ही समय में। सीपीयू उसी गति से चल रहा है। लेकिन आप कैसे उबाऊ यह महसूस कर सकते हैं बहुत जल्दी बनने जा रहा है, और बस कितनी तेजी से, हम जब इंजेक्षन सप्ताह शून्य की एल्गोरिदम का एक सा है, हम चीजों को गति कर सकते हैं। 

तो मार्क तरह अद्भुत लग रहा है। हम कैसे क्रम में, यह उत्तोलन कर सकते हैं और अधिक तेजी से संख्या से सुलझाने के लिए। खैर की पीठ में सोचते हैं एक घटक के लिए है कि हम की है कि, सप्ताह शून्य में वापस था एक फोन बुक में किसी के लिए खोज, और याद है कि हम प्रस्तावित कि स्यूडोकोड, जो के माध्यम से हम पा सकते हैं माइक स्मिथ की तरह किसी को, इस तरह एक छोटे से कुछ देखा। 

अब विशेष रूप से एक नज़र रखना लाइन में 7 और 8, और 10 और 11, हम रखा जिससे है, जो कि पाश प्रेरित फिर, और फिर वापस लाइन 3 जा रहा है, और फिर। लेकिन यह हम देख सकते हैं कि पता चला है इस एल्गोरिथ्म, यहां स्यूडोकोड में, अधिक समग्रता एक छोटे से। वास्तव में, मैं क्या देख रहा हूँ यहाँ स्क्रीन पर, के लिए खोज के लिए एक एल्गोरिथ्म है पृष्ठों में से कुछ सेट के बीच में माइक स्मिथ। और वास्तव में, हम इस सरल सकता उन पंक्तियों के 7 और 8 में एल्गोरिथ्म और 10 और 11 बस, यह कहने के लिए जो मैं पीले रंग में यहाँ प्रस्तुत किया है। दूसरे शब्दों में, यदि माइक स्मिथ, पहले की पुस्तक में है हम कदम निर्दिष्ट करने की जरूरत नहीं है कदम से अब कैसे उसे खोजने के लिए जाना। हम निर्दिष्ट करने के लिए नहीं है 3 लाइन करने के लिए वापस जाने के लिए, यही कारण है कि हम सिर्फ बजाय नहीं करते हैं, कहते हैं, आम तौर पर, में माइक के लिए खोज किताब के बाईं आधा। 

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

इसलिए मैं आप की तरह विलय दे। चलो एक नज़र डालते हैं। तो यहाँ स्यूडोकोड साथ है हम छँटाई लागू कर सकता है, जो मर्ज प्रकार नामक इस कलन विधि का उपयोग। और यह काफी बस इस प्रकार है। N तत्वों के इनपुट पर, दूसरे शब्दों में, अगर आप कर रहे दिए गए n तत्वों और संख्या और इनपुट है या जो भी पत्र, आप n तत्वों, यदि दी रहे हैं 2 n से कम नहीं है, बस वापसी। है ना? N कि, 2 की तुलना में कम है क्योंकि अगर इसका मतलब है कि तत्वों की सूची आकार 0 या 1 के दोनों है, और उन तुच्छ मामलों की दोनों में, सूची में पहले से ही हल है। कोई सूची नहीं है, तो यह हल है। और लंबाई की एक सूची है कि अगर वहाँ 1, यह स्पष्ट रूप से हल है। तो एल्गोरिथ्म केवल करने की जरूरत है वास्तव में दिलचस्प कुछ करते हैं, हम दो या दो से अधिक है, तो तत्वों हमें दिया। तो चलो फिर जादू को देखो। वरना तत्वों के बाईं आधे से तरह, तब तत्वों के ठीक आधे से तरह, तो छाँटे गए हिस्सों विलय। और झुकने मन की तरह क्या है यहाँ, मैं वास्तव में नहीं है तुमसे कहा है लगता है बस अभी तक कुछ भी, है ना? सभी मैं, की एक सूची दी गई है कहा है n तत्वों, बाईं आधे से सुलझाने तो ठीक आधे, तो छाँटे गए हिस्सों मर्ज लेकिन जहां वास्तविक गुप्त सॉस है? एल्गोरिथ्म कहां है? वैसे यह उन दो पंक्तियों पता चला है कि पहले तत्वों की तरह छोड़ दिया आधा, और तत्वों की तरह ठीक आधे, पुनरावर्ती कॉल कर रहे हैं, तो बात करो। 

सब के बाद, इस पर समय में बिंदु, मैं क्या है जिसके साथ करने के लिए एक एल्गोरिथ्म तत्वों की एक पूरी गुच्छा तरह? हाँ। यह ठीक यहाँ है। यह स्क्रीन पर यहीं है, और इसलिए मैं इस कदम की है कि एक ही सेट का उपयोग कर सकते हैं बाईं आधे से सुलझाने के लिए, ठीक आधे मैं कर सकता हूँ। और वास्तव में, फिर से, और फिर से। इसलिए किसी भी तरह या अन्य, और हम जल्द ही करेंगे मर्ज की तरह जादू यह देखना कि बहुत फाइनल में अंतर्निहित है लाइन, सॉर्ट हिस्सों विलय। और कहा कि काफी सहज लगता है। तुम्हें पता है, आप दो हिस्सों लेते हैं, और किसी भी तरह, उन्हें एक साथ विलय, और हम इस देखेंगे वस्तुतः एक पल में। 

लेकिन यह एक पूर्ण एल्गोरिथ्म है। और चलो ठीक से क्यों देखते हैं। खैर, हम ये वही दिया हो कि लगता है स्क्रीन पर यहां आठ तत्वों, एक आठ के माध्यम से, लेकिन वे कर रहे हैं मालूम होता है यादृच्छिक क्रम में। और हाथ में लक्ष्य है इन तत्वों को सॉर्ट करने के लिए। वैसे मुझे लगता है के बारे में कैसे जा सकते हैं फिर, का उपयोग करते हुए यह कर रही है, इस स्यूडोकोड के अनुसार, तरह विलय? और फिर, इस जमा हुआ अपने मन, बस एक पल के लिए। पहले मामले में सुंदर है तुच्छ, यह 2 की तुलना में कम है, सिर्फ कुछ किए जाने की कोई काम नहीं है, वापसी। तो सच में सिर्फ तीन है कदम वास्तव में मन में रखने के लिए। फिर, और फिर, मैं कर रहा हूँ के लिए करना चाहते हो जा बाईं आधे से सुलझाने के लिए, ठीक आधे से तरह, और फिर एक बार उनके दो हिस्सों हल कर रहे हैं मैं उन्हें एक साथ मर्ज करना चाहते हैं एक हल सूची में। इसलिए इस बात का ध्यान रखें। 

तो यहाँ मूल सूची है। चलो एक के रूप में इस का इलाज करते हैं सरणी, हम करने के लिए शुरू के रूप में दो सप्ताह में, जो एक है स्मृति से सटे ब्लॉक। इस मामले में, आठ से युक्त नंबर, वापस वापस करने के लिए वापस करने के लिए। और चलो अब मर्ज तरह लागू होते हैं। तो मैं पहले सॉर्ट करना चाहते हैं इस सूची के बाईं आधा, और इसलिए, चलो 4, 8, 6, और 2 पर ध्यान केंद्रित। 

अब मुझे लगता है के बारे में कैसे जाना है आकार 4 की एक सूची छँटाई? वैसे मैं अब विचार करना है बाईं आधे के बाईं छँटाई। फिर, चलो बस एक पल के लिए उल्टा करते। स्यूडोकोड यदि यह है कि, और मैं आठ तत्वों दिया हूँ, 8 स्पष्ट रूप से अधिक है से अधिक या 2 के बराबर। साथ तो पहला मामला लागू नहीं होता। तो आठ तत्वों से तरह, जब मैं पहली बार के लिए तत्वों की बाईं आधे से सुलझाने तो मैं तो मैं मर्ज ठीक आधे से सुलझाने दो सॉर्ट हिस्सों, आकार 4 से प्रत्येक। ठीक। 

तुम सिर्फ मुझे बता दिया है लेकिन, अगर सुलझाने के अब आकार 4 की है जो बाईं आधा, कैसे मैं छोड़ दिया आधे से तरह करते हैं? वैसे मैं एक है, तो चार तत्वों के इनपुट, जब मैं पहली बार बाएं से सुलझाने दो, तो ठीक दो, और फिर मैं उन्हें एक साथ विलय। तो फिर, यह एक सा हो जाता है एक मन की यहाँ खेल झुकने, तुम क्योंकि, एक तरह से करने के लिए है आप कहानी में हैं जहां याद है, लेकिन दिन के अंत में, तत्वों की किसी भी संख्या को देखते हुए जब आप पहली बार सॉर्ट करना चाहते हैं बाईं आधा, तो ठीक आधे, फिर उन्हें एक साथ विलय। ठीक है कि ऐसा करने के लिए शुरू करते हैं। यहाँ आठ तत्वों के इनपुट है। अब हम यहां बाईं आधे पर देख रहे हैं। कैसे मैं चार तत्वों से तरह करते हैं? खैर मैं पहली बार वाम आधा तरह। अब मैं कैसे छोड़ दिया आधे से तरह करते हैं? वैसे मैं दो तत्वों को देखते हुए किया गया है। तो चलो इन दोनों तत्वों को सॉर्ट करते हैं। 2 या उससे अधिक 2 के बराबर, बिल्कुल। तो यह है कि पहले मामले पर लागू नहीं होता। 

इसलिए मैं अब बाएं हल करना होगा इन दोनों तत्वों का आधा। बाईं आधा, ज़ाहिर है, सिर्फ 4 है। तो मैं कैसे एक तत्व की एक सूची तरह करते हैं? खैर, अब है कि विशेष आधार के मामले शीर्ष ऊपर है, तो बात करने के लिए लागू होता है। 1 कम से कम 2 है, और मेरे सूची वास्तव में आकार 1 का है। तो मैं बस वापसी। मैं कुछ भी नहीं है। और वास्तव में, मैं क्या देखो किया, 4 पहले से ही हल है। जैसा कि मैंने पहले ही कर रहा हूँ यहां आंशिक रूप से सफल। 

अब जब कि बेवकूफ की तरह लगती है दावा है, लेकिन यह सच है। 4 आकार 1 की एक सूची है। यह पहले से ही हल है। यही कारण है कि बाएं आधा है। अब मैं ठीक आधे तरह। मेरे इनपुट 8, एक तत्व है इसी तरह, पहले से ही सुलझा लिया। बेवकूफ भी है, लेकिन फिर, इस बुनियादी सिद्धांत हमें अब निर्माण करने की अनुमति देने के लिए जा रहा है इस के शीर्ष पर सफलतापूर्वक। 4 अब, 8 हल है, हल कि अंतिम चरण के लिए क्या था? तो तीसरे और अंतिम चरण के लिए, किसी भी बार जब आप एक सूची, याद छंटाई कर रहे हैं दो हिस्सों विलय करने के लिए था छोड़ दिया और सही। तो चलो ठीक है कि ऐसा ही करे। मेरी बाईं आधा, बेशक, 4 है। मेरे ठीक आधे 8 है। 

तो चलो यह करते हैं। पहले मैं आवंटित करने के लिए जा रहा हूँ कुछ अतिरिक्त स्मृति, , मैं यहाँ का प्रतिनिधित्व करेंगे कि सिर्फ एक माध्यमिक सरणी के रूप में, कि इस फिट करने के लिए काफी बड़ा है। लेकिन अगर आप को विस्तार देने की कल्पना कर सकते कि आयत पूरी लंबाई, हम और अधिक बाद में की जरूरत है। मैं 4 लेने के लिए और 8, और विलय कैसे करते हैं एक साथ आकार 1 की उन दो सूचियों? यहां भी, बहुत आसान है। 4 तो पहले आता है, 8 आता है। मैं सॉर्ट करना चाहते हैं क्योंकि अगर बाईं आधा, तो ठीक आधे, और फिर उन दो हिस्सों विलय एक साथ, सॉर्ट क्रम में, 4 तो पहले आता है, 8 आता है। 

इसलिए हम भी, प्रगति बनाने लगते हैं मैं किसी भी वास्तविक काम नहीं किया है, हालांकि। हम कहानी में हैं जहां लेकिन याद रखना। हम मूल रूप से आठ तत्वों ले लिया। हम 4 है जो बाईं आधा, हल। तो फिर हम बाईं आधा छाँटे गए 2 था जो बाईं आधा, के। और अब हम चले। हम उस कदम के साथ कर रहे हैं। 

हम हल किया है, तो अगर अब हम 2 के आधे छोड़ा 2 के ठीक आधे हल करना होगा। तो 2 के ठीक आधे है यहां इन दोनों के मूल्यों, 6 और 2। तो चलो अब आकार का एक इनपुट ले चलो 2, और फिर बाईं आधा सॉर्ट करें, और ठीक आधे, और फिर उन्हें एक साथ विलय। खैर, मैं कैसे आकार की एक सूची को सॉर्ट करना 1, बस संख्या 6 से युक्त? मैं पहले से ही काम कर रहा हूँ। आकार 1 की उस सूची में हल है। 

मैं की एक और सूची को सॉर्ट कैसे करते हैं आकार 1, तथाकथित सही आधा। वैसे यह भी है, पहले से ही हल है। नंबर 2 अकेली है। तो अब मैं दो हिस्सों है, छोड़ दिया और ठीक है, मैं उन्हें एक साथ विलय करने की जरूरत है। मुझे अपने आप को कुछ अतिरिक्त जगह दे देते हैं। और, वहाँ में 2 डाल फिर 6 वहाँ में, जिससे उस सूची छँटाई, बाएँ और दाएँ और अंत में, यह एक साथ विलय। इसलिए मैं थोड़ा बेहतर स्थिति में हूँ। मैं, किया क्योंकि नहीं कर रहा हूँ स्पष्ट रूप से 4, 8, 2, 6 मैं चाहता हूँ कि अंतिम आदेश नहीं है। लेकिन मैं अब, कि आकार 2 की दो सूचियों है दोनों क्रमशः है, हल किया गया है। तो अब आप अपने मन में उल्टा यदि आंख, जहां कि हमें छोड़ दिया? मैं तो आठ तत्वों के साथ शुरू कर दिया मैं 4 के बाईं आधा करने के लिए नीचे whittled फिर 2 के बाईं आधा, और फिर 2 के ठीक आधे, मैं बाईं छँटाई, इसलिए, समाप्त 2 में से आधे, और 2 के ठीक आधे, इसलिए तीसरे और अंतिम चरण के लिए यहां क्या हो रहा है? मैं एक साथ विलय करने के लिए है आकार 2 की दो सूचियों। तो चलो आगे चलते हैं। और यहाँ स्क्रीन पर, देना मुझे कुछ अतिरिक्त स्मृति, तकनीकी रूप से हालांकि, मैं कि नोटिस खाली स्थान को शीर्ष की एक पूरी गुच्छा मिला क्या आप वहां मौजूद हैं। मैं विशेष रूप से होना चाहते हैं कुशल अंतरिक्ष बुद्धिमान, मैं सिर्फ तत्वों चलती शुरू कर सकता है आगे और पीछे, ऊपर और नीचे। लेकिन सिर्फ दृश्य स्पष्टता के लिए, मैं नीचे इसे नीचे रख करने जा रहा हूँ अच्छा है और चीजों को साफ रखने के लिए। 

तो मैं आकार 2 की दो सूचियां मिल गया है। पहली सूची 4 और 8 है। दूसरी सूची 2 और 6 है। उन विलय एक साथ सॉर्ट क्रम में। 2, ज़ाहिर है, सबसे पहले आता है फिर 4, फिर 6, तो 8। और अब हम हो रही हैं कहीं दिलचस्प। अब मैं हल किया है, आधा सूची, और संयोग से, यह है सब भी संख्या, लेकिन लगता है कि वास्तव में, सिर्फ एक संयोग है। और मैं अब बाएं हल किया है आधा, यह 2, 4, 6, और 8 इतना है कि। कुछ भी नहीं आदेश से बाहर है। यही कारण है कि प्रगति की तरह लगता है। 

मैं अब ऐसा लगता है अब हमेशा के लिए बात कर रहा है, तो क्या हुआ अगर यह देखने की बात है एल्गोरिथ्म वास्तव में, और अधिक कुशल है। लेकिन हम के माध्यम से जा रहे हैं यह सुपर विधिपूर्वक। एक कंप्यूटर, ज़ाहिर है, लगता है कि जैसे यह करना होगा। तो हम कहाँ हैं? हम आठ तत्वों के साथ शुरू कर दिया। मैं 4 के बाईं आधा हल। मुझे लगता है कि के साथ किया जा करने लगते हैं। तो अब अगले कदम के लिए है 4 के ठीक आधे तरह। और इस हिस्से हम जा सकते हैं एक छोटे से अधिक के माध्यम से जल्दी से, आप कर रहे हैं, हालांकि बस, अतीत या थामने के लिए आपका स्वागत है पर यह माध्यम से लगता है अपनी गति है, लेकिन क्या हम अब एक अवसर के लिए है चार पर सटीक एक ही एल्गोरिथ्म करना अलग नंबरों। 

तो चलो आगे चलते हैं, और पर ध्यान केंद्रित हम यहाँ कर रहे हैं जो सही आधा। उस के बाईं आधा सही आधा है, और अब बाएं के बाईं आधा सही है कि आधे से आधे से, और मैं आकार की एक सूची तरह कैसे करते हैं एक बस संख्या 1 से युक्त? यह पहले से हो चुका है। मैं एक सूची के लिए एक ही कैसे करते हो सिर्फ 7 युक्त आकार 1 की? यह पहले से हो चुका है। तो इस आधे के लिए तीन कदम इन दोनों तत्वों को मर्ज करने के लिए है आकार 2, 1 और 7 की एक नई सूची में। सब कुछ किया है ऐसा नहीं लगता है लगता है कि बहुत दिलचस्प काम करते हैं। की अगली देखो क्या होता है। मैं बस के बाईं आधा छाँटे गए अपने मूल इनपुट के ठीक आधे। अब देखते हैं कि सही तरह चलो 5 और 3 होता है जो आधा। चलो फिर से छोड़ दिया पर एक नजर डालते हैं आधा, हल, ठीक आधे, हल, और, एक साथ उन दो विलय कुछ अतिरिक्त अंतरिक्ष में, 3 तब पहले आता है, 5 आता है। और अब तो, हम हल किया है ठीक आधे के बाईं आधा मूल समस्या के कारण, और ठीक आधे के ठीक आधे मूल समस्या की। तीसरे और अंतिम चरण में क्या है? खैर एक साथ उन दो हिस्सों विलय करने के लिए। तो मुझे अपने आप को कुछ मिल जाने फिर अतिरिक्त जगह है, लेकिन, मैं कि खाली स्थान को शीर्ष का उपयोग हो सकता है। लेकिन हम रखने के लिए जा रहे हैं नेत्रहीन यह सरल। मुझे अब 1 में विलय करते हैं, और उसके बाद 3, और फिर 5, और फिर 7। इस प्रकार से अब मुझे छोड़कर मूल समस्या के ठीक आधे कि पूरी तरह से हल है। 

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

विलय से तो, मैं क्या करने की जरूरत है? मैं क्रम में तत्वों लेना चाहते हैं। तो बाईं आधे पर देख रहे हैं, जब मैं पहली बार नंबर 2 है देखते हैं। मैं ठीक आधे को देखो, जब मैं पहली बार नंबर देख तो जाहिर है, जो 1 नंबर, मैं बाहर बांधना चाहते हो और मेरा अंतिम सूची में पहले रखा है? बेशक, 1। अब मुझे लगता है कि एक ही सवाल पूछना चाहता हूँ। बाईं आधे पर, मैं अभी भी 2 नंबर मिला है। ठीक आधे पर, मैं 3 नंबर मिल गया है। जो एक मैं चयन करने के लिए करना चाहते हैं? बेशक, नंबर 2 और अब उम्मीदवारों को नोटिस सही पर छोड़ दिया, 3 पर 4 हैं। की, बेशक, 3 का चयन करते हैं। अब उम्मीदवारों 4 पर हैं सही पर छोड़ दिया, 5। हम, ज़ाहिर है, 4 चुनें। सही पर छोड़ दिया, 5 पर 6। हम, ज़ाहिर है, 5 चुनें। सही पर छोड़ दिया, 7 पर 6। हम 6 चुनते हैं, और फिर हम 7 चुनते हैं, और फिर हम 8 चुनें। देखा। 

शब्द का तो एक बड़ी संख्या बाद में, हम आठ तत्वों की इस सूची में हल किया है आठ के माध्यम से एक की एक सूची में, कि, हर कदम के साथ बढ़ती जा रही है लेकिन कितना समय किया था यह करने के लिए हमें ले। वैसे मैं जानबूझ कर किया है pictorially रखी चीजें बाहर यहाँ, इतना है कि हम कर सकते हैं प्रकार की देखते हैं या विभाजन की सराहना जीतने में है कि क्या हो रहा है। 

तुम्हें जगा पर वापस देखो यदि वास्तव में, मैं इन बिंदीदार लाइनों के सभी छोड़ दिया है जगह धारकों में, आप कर सकते हैं, एक तरह से, रिवर्स क्रम में, देखो, आप की तरह में वापस देखो इतिहास, अब अपने मूल सूची आकार 8 की, ज़ाहिर है, है। और फिर इससे पहले, मैं था आकार 4 की दो सूचियों के साथ व्यवहार, और फिर आकार 2 के चार सूचियों, और फिर आकार 1 के आठ सूचियों। 

तो यह क्या करता है, एक तरह से, की याद दिलाने? खैर, वास्तव में, किसी भी हम है एल्गोरिदम इस प्रकार अब तक देखा जहाँ हम विभाजन, और विभाजन है, और विभाजन है, फिर से बातें कर रखना, और फिर, यह सामान्य विचार में यह परिणाम है। और तो कुछ भी नहीं है लघुगणक यहाँ पर जा रहा। और यह n के काफी लॉग इन करें, नहीं है, लेकिन एक लघुगणक घटक है हम तो बस क्या किया है करने के लिए। 

अब देखते हैं कि वास्तव में कैसे होता है पर विचार करते हैं। तो फिर, एन लॉग था एक महान समय चल रहा है, हम ऐसा कुछ किया जब द्विआधारी खोज, अब हम इसे कहते हैं, फूट डालो और राज रणनीति जो के माध्यम से हम माइक स्मिथ पाया। अब तकनीकी रूप से। यही कारण है कि यहां तक ​​कि, एन लॉग आधार 2 है सबसे गणित वर्ग में हालांकि, 10 आम तौर पर आप को लगता है कि पसंद है। लेकिन कंप्यूटर वैज्ञानिकों लगभग हमेशा और लगता है कि आधार 2 के संदर्भ में बात करते हैं, तो हम आम तौर पर सिर्फ लॉग कहना एन, बजाय एन लॉग आधार 2 की, लेकिन वे वास्तव में एक और हो कंप्यूटर की दुनिया में एक ही विज्ञान, और एक अलग रूप में, एक निरंतर कारक भी नहीं है दोनों के बीच का अंतर है, तो यह है और अधिक औपचारिक कारणों के लिए, वैसे भी मूट। 

लेकिन अब के लिए, हम क्या परवाह इस बारे में उदाहरण है। तो चलो उदाहरण से यह साबित नहीं करते हैं, लेकिन कम से कम से कम संख्या का एक उदाहरण का उपयोग हाथ में एक मानसिक स्वास्थ्य की जांच के रूप में, अगर तुम जाएगा। तो पहले से सूत्र लॉग आधार था N के 2, लेकिन इस मामले में n क्या है। मैं n मूल नंबर था, या 8 मूल संख्या से विशेष रूप से। अब यह एक छोटे से हो गया है जबकि, लेकिन मैं कर रहा हूँ सुंदर सुनिश्चित करें कि लॉग आधार 2 8 3 मूल्य की, और वास्तव में, यह है कि क्या है के बारे में अच्छा है 3 बार है कि के बिल्कुल संख्या है आप एक सूची में विभाजित कर सकते हैं कि फिर, और फिर लंबाई 8 की, और फिर, आप छोड़ रहे हैं जब तक सिर्फ आकार 1 की सूची के साथ। है ना? 8, 4 को जाता है 2 के लिए चला जाता है, 1 के लिए चला जाता है, और वह है वास्तव में इस बात का चिंतनशील तस्वीर हम सिर्फ एक क्षण पहले था। तो एक छोटे से विवेक के रूप में जहाँ जाँच लघुगणक वास्तव में शामिल किया गया है। 

तो अब, और क्या यहाँ शामिल है? एन। इसलिए हर उस नोटिस बार मैं सूची में विभाजित इतिहास में रिवर्स क्रम में यद्यपि यहाँ, मैं अभी भी एन बातें कर रहा था। यही कारण है कि विलय के कदम आवश्यक है कि मैं नंबरों में से हर एक को छूने में स्लाइड करने के लिए इसके उचित स्थान। तो भले ही इस की ऊंचाई आरेख, एन या 3 के आकार लॉग n की है विशेष रूप से, दूसरे शब्दों में, मैं यहाँ तीन प्रभागों किया था। कितना काम मैं क्षैतिज क्या किया इस चार्ट प्रत्येक समय के साथ? 

खैर, मैं के एन कदम था मैं, क्योंकि अगर काम चार तत्वों और चार तत्वों मिला और मैं उन्हें एक साथ विलय करने की जरूरत है। मैं के माध्यम से जाने की जरूरत है इन चार और इन चार, अंततः उन्हें मर्ज करने के लिए वापस आठ तत्वों में। इसके विपरीत अगर मैं आठ उंगलियों मिल गया है मैं नहीं जानता है, जो यहां से अधिक है, और आठ fingers-- sorry-- मैं तो यहाँ पर चार उंगलियों मिला मैं चार उंगलियों करते हैं यहाँ पर, मुझे क्या करना है, जो तो यह है कि एक ही है उदाहरण के रूप में पहले, अगर मैं ऐसा हालांकि आठ उंगलियों मैं एक तरह से, जो कर सकते हैं, कुल। मैं वास्तव में, यहां क्या कर सकते हैं तो मैं निश्चित रूप से कर सकते हैं इन सूचियों के सभी विलय एक साथ आकार 1 की। लेकिन मैं निश्चित रूप से देखने के लिए है प्रत्येक तत्व में वास्तव में एक बार। इसलिए इस प्रक्रिया की ऊंचाई, लॉग n है इस प्रक्रिया की चौड़ाई, तो बात है, तो हम क्या लगता है, n है अंत में, है, के लिए है आकार n समय की एक समय चल रहा लॉग n। 

दूसरे शब्दों में, हम विभाजित सूची, लॉग n बार, लेकिन हम किया है कि हर बार हम था तत्वों में से हर एक को छूने के लिए उन्हें मर्ज करने के लिए सब एक साथ, जो कदम एन, तो हम n बार लॉग n किया गया था, या एक कंप्यूटर वैज्ञानिक रूप में कहते हैं, asymptotically, जो बड़ा शब्द होगा ऊपरी वर्णन करने के लिए एक समय चल रहा है पर बाध्य, हम एक बड़ा ओ में चल रहे हैं लॉग n समय की है, तो बात करने के लिए। 

अब इस वजह से महत्वपूर्ण है, चल रहे थे बार क्या याद बुलबुला तरह, और चयन के साथ प्रकार, और सम्मिलन तरह, और मौजूद है कि यहां तक ​​कि कुछ अन्य लोगों, n हम पर थे जहां था चुकता। और अगर आप एक तरह से, यहाँ यह देख सकते हैं। N चुकता है, तो जाहिर है n बार है एन, लेकिन यहाँ हम n बार लॉग n, और हम पहले से ही हफ्ते से पता शून्य, कि लॉग n, लघुगणक, कुछ रैखिक की तुलना में बेहतर है। सब के बाद, चित्र याद लाल और पीले रंग के साथ हम आकर्षित किया है कि और हरे रंग की लाइनों, हरी लघुगणक लाइन बहुत कम थी। और इसलिए, ज्यादा बेहतर और तेज सीधे पीले और लाल लाइनों की तुलना में, n बार वास्तव में, लॉग n, बेहतर n बार की तुलना में एन, या एन चुकता। 

तो हम करने लगते हैं एक एल्गोरिथ्म मर्ज की पहचान क्रमबद्ध ज्यादा में चलता है कि तेजी से समय, और वास्तव में, यही कारण है कि इससे पहले इस सप्ताह, जब है हम बुलबुले के बीच कि प्रतियोगिता को देखा प्रकार, चयन प्रकार, और विलय तरह, की तरह वास्तव में, वास्तव में जीता विलय। और वास्तव में, हम भी इंतजार नहीं किया बुलबुला तरह और चयन प्रकार के लिए खत्म करने के लिए। 

अब हम एक दूसरे के पास ले चलो इस पर, एक से थोड़ा अधिक से औपचारिक परिप्रेक्ष्य में, बस में मामला है, इस बेहतर प्रतिध्वनित कि उच्च स्तर की चर्चा से। तो यहाँ एल्गोरिथ्म फिर से है। के अपने आप से पूछना, क्या चल रहा है समय इस विभिन्न चरणों एल्गोरिदम का है? की पहली में विभाजित करते हैं मामला है और दूसरा मामला। अगर मामले में अगर और कुछ, 2 n से कम है तो, सिर्फ वापसी। लगातार समय की तरह लगता है। यह दो चरणों की तरह है, एक तरह से है, 2 n से कम नहीं है, तो फिर लौट आते हैं। लेकिन हम सोमवार को कहा था, लगातार समय, या 1 के ओ बड़ा, दो कदम, तीन हो सकता है कदम, यहां तक ​​कि 1000 कदम। क्या मायने रखता है कि यह है कदम की एक निरंतर संख्या। तो पीले स्यूडोकोड पर प्रकाश डाला यहाँ, हम यह कहते हैं, में चलाता है लगातार समय। इसलिए अधिक औपचारिक रूप से, और हम इस है-- जा रहे हैं हद हो जाएगा, जो हम n के टी now-- इस अधिकार को औपचारिक रूप, एक समस्या का समय चल रहा है कि, इनपुट के रूप में एन somethings लेता है , एक की ओ बड़ा बराबर होती है 2 n की तुलना में कम है। तो यह है कि उस पर सशर्त है। N से कम है तो, अगर स्पष्ट होना 2, हम तो एक बहुत संक्षिप्त सूची है n है जहां समय चल रहा है n के, टी, 1 या 0, यह बहुत ही विशेष मामले में, यह सिर्फ लगातार समय होने जा रहा है। यह एक लेने के लिए जा रहा है , जो भी, दो कदम कदम। यह कदम की एक निश्चित संख्या है। 

तो रसदार हिस्सा निश्चित रूप में होना चाहिए स्यूडोकोड में अन्य मामले। और मामले। तत्वों का क्रमबद्ध बाईं आधा है, की तरह सही तत्वों के आधे सॉर्ट हिस्सों विलय। उन कदमों में से प्रत्येक में कितना समय लगेगा? खैर, तो उनका प्रदर्शन n तत्वों को सॉर्ट करने के लिए समय है, के लिए यह बहुत ही फोन करते हैं सामान्य रूप से, टी एन की, फिर बाईं छँटाई तत्वों के आधे है, की तरह, जैसे कह रही, 2 से विभाजित n के टी, और इसी तरह से ठीक आधे छँटाई तत्वों की है, की तरह, जैसे कह रही, N के 2 टी विभाजित है, और फिर छाँटे गए हिस्सों विलय। वैसे मुझे मिल गया है, तो कुछ यहां तत्वों की संख्या, चार, और कुछ नंबर की तरह यहां तत्वों की, चार की तरह, और मुझे लगता है कि इन चार में से प्रत्येक को मर्ज करने के लिए है में, और इन चार में से प्रत्येक से एक में दूसरे के बाद, इतना है कि अंत में मैं आठ तत्व है। ऐसा लगता है कि एन कदम की ओ बड़ा है की तरह लगता है? मैं उंगलियों और के प्रत्येक n मिल गया है उन्हें जगह में विलय हो गया है, कि एक और एन कदम की तरह है। 

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

अब हम एक का एक सा लग जाने उस का सब से सांस, और एक पर एक नज़र रखना कुछ पूर्व सीनेटर, कौन एक छोटे से परिचित लग सकता है, जो गूगल के एरिक के साथ बैठ गया एक साक्षात्कार के लिए कुछ समय पहले श्मिट, मंच पर, एक पूरी गुच्छा के सामने लोगों की है, अंत के बारे में बात कर रही है एक विषय है, सुंदर है कि अब परिचित है। चलो एक नज़र डालते हैं। 

एरिक श्मिट: अब सीनेटर, आप गूगल पर कर रहे हैं यहाँ और मैं के बारे में सोचना पसंद एक नौकरी के साक्षात्कार के रूप में राष्ट्रपति पद के। अब यह राष्ट्रपति के रूप में एक नौकरी पाने के लिए मुश्किल है। राष्ट्रपति ओबामा: ठीक है। एरिक श्मिट: और आप कर रहे हैं अब [सुनाई] क्या करने जा रही है। यह गूगल पर एक नौकरी पाने के लिए भी मुश्किल है। राष्ट्रपति ओबामा: ठीक है। 

एरिक श्मिट: हम प्रश्न हैं, और हम अपने उम्मीदवारों सवाल पूछने, और इस एक लैरी श्विमर से है। 

राष्ट्रपति ओबामा: ठीक है। 

एरिक श्मिट: क्या? तुम लोगों को मैं मजाक कर रहा हूँ लगता है? यह ठीक यहाँ है। सबसे कारगर तरीका क्या है एक लाख 32 बिट पूर्णांक तरह? 

राष्ट्रपति ओबामा: Well-- एरिक श्मिट: कभी कभी, शायद मैं माफी चाहता हूँ, maybe-- राष्ट्रपति ओबामा: नहीं, नहीं, नहीं, नहीं, नहीं, मैं think-- एरिक श्मिट: यह it-- नहीं है राष्ट्रपति ओबामा: मैं लगता है, मैं बुलबुला लगता है क्रमबद्ध जाने के लिए गलत तरीका होगा। एरिक श्मिट: आओ। कौन उसे यह बताया था? ठीक। मैं कंप्यूटर विज्ञान नहीं किया on-- 

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

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

मैं एक आदेश भागा पहले कमांड लाइन। बजना पानी का छींटा राजधानी एस hello.c, और यह एक फ़ाइल बनाया मुझे बुलाया hello.s के लिए, जो के अंदर वास्तव में थे इन सामग्री, और एक छोटे से अधिक ऊपर और अधिक नीचे एक छोटे से, लेकिन मैं juiciest रख दिया है यहाँ स्क्रीन पर जानकारी। तुम करीब से देखो, तो आप देखेंगे कम से कम कुछ परिचित खोजशब्दों। हम शीर्ष पर मुख्य है। हम बीच में नीचे printf है। और हम भी दुनिया नमस्कार है नीचे नीचे उद्धरण में बैकस्लैश एन। 

यहाँ में और बाकी सब कुछ बहुत कम स्तर निर्देश है कंप्यूटर का सीपीयू को समझता है कि। स्मृति कदम है कि सीपीयू निर्देश चारों ओर, स्मृति से है कि लोड तार, और अंत में, प्रिंट स्क्रीन पर बातें। अब क्या करने के बाद हालांकि होता इस विधानसभा कोड उत्पन्न होता है? अंत में, आप वास्तव में, करते हैं, अभी भी वस्तु कोड उत्पन्न करते हैं। लेकिन कदम वास्तव में है कि हुड के नीचे चल रहा इस तरह एक छोटे से अधिक लग रही है। स्रोत कोड, विधानसभा कोड हो जाता है जो तब ऑब्जेक्ट कोड हो जाता है, और यहाँ ऑपरेटिव शब्द हैं, कि आप अपने स्रोत कोड संकलन करते हैं, बाहर तो विधानसभा कोड, और आता है आप अपने विधानसभा कोड को इकट्ठा करते हैं, बाहर ऑब्जेक्ट कोड आता है। 

अब बजना, सुपर परिष्कृत है compilers के एक बहुत पसंद है, और यह इन चरणों के सभी करता है एक साथ, और यह जरूरी नहीं उत्पादन किसी भी मध्यवर्ती आप भी देख सकते हैं कि फ़ाइलों। यह सिर्फ बातें compiles, जो सामान्य शब्द है कि इस पूरी प्रक्रिया का वर्णन करता है। लेकिन क्या आप वास्तव में चाहते हैं विशेष रूप से होना करने के लिए नहीं है, एक बहुत अधिक के रूप में अच्छी तरह से वहाँ चल रहा है। 

लेकिन हम यह भी है कि अब भी विचार करते हैं कि सुपर सरल कार्यक्रम, hello.c, एक समारोह में कहा जाता है। यह printf बुलाया। लेकिन मुझे लगता है, वास्तव में, printf नहीं लिखा था तो यह है कि बात करने के लिए, ग के साथ आता है। ऐसा लगता है कि एक समारोह में याद करते है मानक io.h, में जो घोषणा की एक हेडर फाइल है, जो एक विषय है कि हम वास्तव में जाएगा लंबे समय से पहले और अधिक गहराई में गोता। लेकिन एक हेडर फाइल है आम तौर पर साथ एक कोड फ़ाइल, स्रोत कोड फ़ाइल है, तो द्वारा मानक io.h. वहाँ मौजूद बहुत पसंद है 

कुछ समय पहले, किसी को, या किसी भी लिखा था में, मानक io.c नामक एक फाइल जो वास्तविक परिभाषा, या printf के कार्यान्वयन, और अन्य कार्यों के गुच्छों, वास्तव में लिखा जाता है। हम होने पर विचार करें तो, अगर यह देखते हुए कि यहाँ छोड़ दिया, hello.c पर, जब कि संकलित, भले ही, hello.s हमें देता है बजना एक जगह में बचत परेशान नहीं करता है हम यह देखते हैं, और कहा कि विधानसभा कोड कर सकते हैं hello.o, में इकट्ठे हो जाता है जो वास्तव में, डिफ़ॉल्ट नाम है आप स्रोत संकलन जब भी दी वस्तु कोड में कोड, लेकिन नहीं कर रहे हैं अभी तक इसे लागू करने के लिए पूरी तरह से तैयार, एक और कदम है क्योंकि ऐसा करने के लिए है, और है पिछले कुछ के लिए हो रहा सप्ताह, आप शायद अनजान। 

विशेष रूप से कहीं न कहीं CS50 आईडीई में है, और यह, भी, एक की एक सा हो जाएगा एक पल के लिए अति सरलीकरण, वहाँ है, या एक समय पर था, मानक io.c नामक एक फाइल, किसी में संकलित किया है कि मानक io.s या समकक्ष, किसी को तो इकट्ठे कि मानक io.o में, या यह एक में पता चला है थोड़ा अलग फ़ाइल एक अलग हो सकता है कि प्रारूप कुल मिलाकर फ़ाइल एक्सटेंशन, सिद्धांत और धारणात्मक, वास्तव में, लेकिन उन कदमों किसी न किसी रूप में तो होना ही था। कहते हैं, कि अब के लिए है जो मैं एक कार्यक्रम लिख रहा हूँ, जब hello.c, बस का कहना है कि, दुनिया नमस्ते, और मैं किसी और के कोड का उपयोग कर रहा हूँ एक पर एक बार गया था, जो printf की तरह समय, मानक io.c नामक एक फाइल में, फिर किसी भी तरह मैं अपने लेने के लिए है ऑब्जेक्ट कोड, मेरे शून्य और लोगों, और उस व्यक्ति की वस्तु कोड, या शून्य और लोगों, और किसी भी तरह में उन्हें एक साथ लिंक कि, हैलो कहा जाता है एक अंतिम फ़ाइल, है शून्य के सभी और मेरी मुख्य समारोह से लोगों को, और शून्य के सभी और printf के लिए लोगों को। 

और वास्तव में, कि अंतिम प्रक्रिया है कहा जाता है, अपने उद्देश्य कोड जोड़ने। जिनमें से उत्पादन एक निष्पादन योग्य फ़ाइल है। तो निष्पक्षता में, पर दिन, कुछ भी नहीं के अंत एक सप्ताह के बाद से बदल गया है, जब हम पहले कार्यक्रम के संकलन शुरू कर दिया। दरअसल, यह सब किया गया है हुड के नीचे हो रहा है, लेकिन अब हम एक स्थिति में हैं जहां हम वास्तव में कर सकते हैं इन विभिन्न चरणों के अलावा तंग। और वास्तव में, अंत में दिन की है, हम अब भी कर रहे शून्य और लोगों के साथ छोड़ दिया है जो एक महान segue अब वास्तव में है सी का एक और क्षमता के लिए, कि हम सबसे अधिक संभावना का लाभ उठाने के लिए नहीं किया है आज तक, बिटवाइस ऑपरेटरों के रूप में जाना जाता है। दूसरे शब्दों में, इस प्रकार अब तक, कभी भी हम है सी में सी या चर में डेटा के साथ निपटा, हम की तरह चीजों को मिला है वर्ण और मंगाई और भारतीय नौसेना पोत और चाहता और युगल और पसंद है, लेकिन उन सभी के कम से कम आठ टुकड़े कर रहे हैं। हम अभी तक करने में सक्षम नहीं किया गया है व्यक्तिगत बिट्स हेरफेर, यहां तक ​​कि एक व्यक्ति बिट हालांकि, हम एक 0 और 1 का प्रतिनिधित्व कर सकते हैं। अब यह सी में पता चला है कि, आप व्यक्तिगत बिट्स के लिए उपयोग हो सकता है, आप वाक्य रचना अगर तुम्हें पता है, जो के साथ उन पर पाने के लिए। 

तो चलो एक नजर डालते हैं बिटवाइस ऑपरेटरों पर। तो यहाँ चित्र में कुछ प्रतीक हैं कि हम, की तरह है, की तरह, पहले देखा है। मैं एक खड़ी एक एम्परसेंड देखना बार, और साथ ही कुछ अन्य लोगों, और कहा कि एम्परसेंड एम्परसेंड याद हम पहले देखा है कुछ है। तुम्हारे पास है, जहां तार्किक और ऑपरेटर उनमें से दो को एक साथ, या तार्किक या ऑपरेटर, जहां आप दो खड़ी सलाखों है। बिटवाइस ऑपरेटरों, जो हम करेंगे व्यक्तिगत रूप से बिट्स पर काम देखना सिर्फ एक ही एम्परसेंड का उपयोग करें, एक एकल खड़ी बार, कैरट प्रतीक अगले, छोटी सी बात आती है टिल्ड, और फिर छोड़ दिया ब्रैकेट ब्रैकेट छोड़ दिया है, या सही ब्रैकेट सही ब्रैकेट। इनमें से प्रत्येक अलग अलग अर्थ है। 

वास्तव में, एक नजर डालते हैं। के पुराने स्कूल आज, और उपयोग चलते हैं पहल साल से एक टच स्क्रीन, एक सफेद बोर्ड के रूप में जाना जाता है। और इस सफेद बोर्ड हमें अनुमति देने के लिए जा रहा है कुछ काफी सरल प्रतीकों को व्यक्त करने के लिए, या यों कहें कि कुछ काफी सरल सूत्र, कि हम अंततः तो कर सकते हैं का लाभ उठाने, क्रम में व्यक्तिगत उपयोग करने के लिए एक सी कार्यक्रम के भीतर बिट्स। दूसरे शब्दों में, चलो यह करते हैं। एक के लिए चलो पहले बात एम्परसेंड के बारे में पल, जो बिटवाइस और ऑपरेटर है। दूसरे शब्दों में, यह है अनुमति देता है कि एक ऑपरेटर मुझे एक बाएं हाथ चर राशि के लिए आम तौर पर, और एक दाएँ हाथ चर, या एक व्यक्ति के मूल्य, कि यदि हम और उन्हें एक साथ, मुझे एक अंतिम परिणाम देता है। तो मैं क्या मतलब है? एक कार्यक्रम में, आप एक चर है, तो इन मूल्यों की दुकानों से एक है कि, या सरल रखने के लिए, और सिर्फ दो व्यक्तिगत रूप से शून्य और लोगों को लिखने, एम्परसेंड ऑपरेटर कैसे काम करता है। 0 एम्परसेंड 0 0 बराबर करने के लिए जा रहा है। अब ऐसा क्यों है? 

यह करने के लिए समान है बूलियन अभिव्यक्ति, कि हम इस प्रकार अब तक चर्चा की है। तुम सब के बाद लगता है, 0 है झूठी, 0, झूठी झूठी और गलत है हम चर्चा की है, के रूप में है तार्किक रूप से, यह भी गलत। इसलिए हम के रूप में अच्छी तरह से 0 यहाँ मिलता है। आप 0 एम्परसेंड लेते हैं 1, अच्छा है कि, भी, क्योंकि इस के लिए, 0 होने जा रहा है बाएं हाथ की अभिव्यक्ति, सच है या एक होने के लिए यह सच है और सच करने के लिए की आवश्यकता होगी। लेकिन यहाँ हम झूठे हैं और यह सच है, या 0 और 1। अब फिर से, हम एक एम्परसेंड है तो 0, भी, 0 होने जा रहा है कि, और हम एक एम्परसेंड एक है, अंत में हम एक एक सा है। दूसरे शब्दों में, हम नहीं कर रहे हैं इस ऑपरेटर के साथ कुछ रोचक बस अभी तक, यह एम्परसेंड ऑपरेटर। यह बिटवाइस और संचालक। लेकिन इन तत्व हैं जो के माध्यम से हम क्या कर सकते हैं हम जल्द ही देखेंगे के रूप में दिलचस्प बातें। 

अब हम सिर्फ एक को देखो यहाँ सही पर पर खड़ी बार। मैं एक 0 सा है और अगर मैं या इसके साथ, बिटवाइस या ऑपरेटर, एक और शून्य सा है, कि मुझे 0 देने के लिए जा रहा है। मैं एक 0 बिट और या यह अपने साथ ले तो एक एक सा है, तो मैं एक पाने के लिए जा रहा हूँ। और वास्तव में, बस के लिए स्पष्टता, मुझे वापस जाओ इतना है कि मेरी ऊर्ध्वाधर सलाखों 1 के लिए गलत नहीं कर रहे हैं। मुझे के सभी फिर से लिखना मेरी एक एक छोटे से अधिक है मैं जाहिर है, अगर इतना है कि हम अगले देखते हैं, 1 या 0, कि एक एक होने जा रहा है है, और मैं 1 या 1 है कि एक है, भी, एक एक होने जा रहा है। तो अगर आप तार्किक रूप से देखते हैं कि या जा सकता है ऑपरेटर बहुत अलग ढंग से व्यवहार करता है। , इस 0 मुझे देता है या 0 मुझे 0 देता है, लेकिन हर दूसरे संयोजन मुझे एक देता है। इतने लंबे समय मैं में एक 1 के रूप में सूत्र, परिणाम एक होने जा रहा है। 

और इसी के साथ इसके विपरीत ऑपरेटर, ampersand मैं में दो 1 तभी समीकरण, मैं वास्तव में एक एक बाहर मिलता है। अब कुछ अन्य वहाँ ऑपरेटर के रूप में अच्छी तरह से। उनमें से एक एक छोटे से अधिक शामिल है। तो मुझे आगे जाना है और मिटा दें यह कुछ स्थान खाली करने के लिए। और चलो पर एक नजर डालते हैं बस एक पल के लिए कैरट प्रतीक,। यह आमतौर पर एक है चरित्र आप टाइप कर सकते हैं अपने कीबोर्ड पकड़े शिफ्ट पर और अपने अमेरिका के ऊपर संख्या में फिर से एक कुंजीपटल। 

तो यह विशेष है या ऑपरेटर, अनन्य या। तो हम बस या ऑपरेटर देखा। इस अनन्य या ऑपरेटर है। वास्तव में क्या अंतर है? खैर चलो बस सूत्र को देखो, और अंततः सामग्री के रूप में इस का उपयोग करें। 0 XOR 0। मैं कहने जा रहा हूँ हमेशा 0 है। यही कारण है कि XOR की परिभाषा है। 0 XOR 1 1 होने जा रहा है। 1 XOR 0, 1 होने जा रहा है और एक XOR एक होने जा रहा है? गलत? या सुधारना? मुझे नहीं पता। 0। अब यहाँ क्या हो रहा है? खैर के बारे में सोचते इस ऑपरेटर का नाम। विशेष या, इतनी के रूप में नाम, एक तरह से पता चलता है, जवाब केवल होने जा रहा है एक 1 आदानों विशेष कर रहे हैं, विशेष रूप से अलग है। तो यहाँ निवेश कर रहे हैं एक ही है, इसलिए उत्पादन 0 है। यहां निवेश कर रहे हैं एक ही है, इसलिए उत्पादन 0 है। यहाँ outputs के वे अलग हैं, कर रहे हैं अनन्य हैं, और इसलिए उत्पादन 1 है। तो यह करने के लिए समान है और, यह बहुत समान है या यों कहें कि यह करने के लिए समान है या, लेकिन केवल एक विशेष तरीके से। यह एक, अब एक एक है हम दो एक के लिए है, क्योंकि और विशेष रूप से नहीं है, उनमें से सिर्फ एक। ठीक है। दूसरोँ का क्या? खैर टिल्ड, इस बीच, है वास्तव में अच्छा और सरल है, शुक्र है। और यह एक एकल है जिसका मतलब है कि ऑपरेटर, यह केवल एक इनपुट के लिए आवेदन किया है एक संकार्य, तो बात करो। नहीं, एक को छोड़ दिया और एक सही करने के लिए। दूसरे शब्दों में, आप में से टिल्ड लेते हैं 0, जवाब विपरीत होगा। और तुम 1 के टिल्ड लेते हैं, जवाब विपरीत हो जाएगा। तो टिल्ड ऑपरेटर है एक सा नकार का एक तरीका है, या से थोड़ा flipping 0-1, या 1-0। 

और कहा कि अंत में हमें छोड़ देता है सिर्फ दो अंतिम ऑपरेटरों के साथ, बाएं पारी तथाकथित, और सही बदलाव ऑपरेटर तथाकथित। के कैसे उन काम पर एक नज़र रखना। लिखित छोड़ बदलाव ऑपरेटर, लगता है कि जैसे दो कोण कोष्ठक के साथ, इस प्रकार के रूप में संचालित। तो बाईं ओर अपने इनपुट, या मेरे संकार्य, बदलाव ऑपरेटर काफी बस एक 1 है। और मैं उसके बाद कंप्यूटर को बता 1, सात स्थानों का कहना है कि बदलाव के लिए छोड़ दिया, परिणाम हालांकि मैं के रूप में है कि एक लेते हैं, और इसे स्थानांतरित खत्म करने के लिए सात स्थानों छोड़ दिया, और डिफ़ॉल्ट रूप से, हम मानते हैं कि करने के लिए जा रहे हैं सही करने के लिए अंतरिक्ष शून्य के साथ गद्देदार किया जा रहा है। दूसरे शब्दों में, एक पारी 7 जा रहा है छोड़ा पीछा किया, एक है कि मुझे देने के लिए 1, 2, 3, 4, 5, 6, 7 शून्य। तो एक तरह से, यह करने के लिए आपको अनुमति देता है 1 की तरह एक छोटी संख्या में लेते हैं, और स्पष्ट रूप से ज्यादा यह कर इस तरह से बहुत बड़ा, बहुत, लेकिन हम वास्तव में देखने के लिए जा रहे हैं इसके लिए अधिक चतुर दृष्टिकोण इसके बजाय, के रूप में अच्छी तरह से, 

ठीक है। यही कारण है कि सप्ताह में तीन के लिए है। हम आपको अगली बार देखेंगे। यह CS50 था। 

[संगीत बजाना] 

स्पीकर 1: वह नाश्ते में था एक गर्म हेराफेरी कुचले हुए फल खाने पट्टी। उन्होंने कहा कि उनके चेहरे पर यह सब किया था। उन्होंने कहा कि एक दाढ़ी की तरह है कि चॉकलेट पहने हुए है स्पीकर 2: तुम क्या कर रहे हो? अध्यक्ष 3: हममम? क्या? 

स्पीकर 2: आप बस डबल डुबकी किया था? आप डबल चिप डूबा हुआ है। अध्यक्ष 3: मुझे माफ करना। स्पीकर 2: आप चिप डूबा एक काट लिया, और आप फिर से डूबा हुआ है। अध्यक्ष 3: स्पीकर 2: कि डालने की तरह है तो डुबकी में अपने पूरे मुंह सही। अगली बार जब आप एक चिप लेने के लिए सिर्फ एक बार डुबकी, और यह खत्म होता है। 

अध्यक्ष 3: आप, दान पता है क्या? आप डुबकी करना चाहते हैं कि जिस तरह डुबकी। मैंने सोचा कि मैं डुबकी करना चाहते हैं कि जिस तरह डुबकी करेंगे।