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

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

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

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

एलन एस्ट्राडा: उम। डेविड जे मालन: वस्तुतः आधे में समस्या फाड़। 

एलन एस्ट्राडा: ओह। मिमी। बहुत अच्छा। 

डेविड जे मालन: ठीक है। अच्छा। धन्यवाद। एलन एस्ट्राडा: बहुत अच्छा है। ठीक। 

डेविड जे मालन: और इसलिए अब, आप इसे नीचे whittled किया है समस्या के आधे आकार के लिए। अब, हम एक चौथाई से नीचे रहे हैं। आप की ओर ध्यान दे रहे हैं हम रख रहे हैं जो की ओर? 

[हँस] 

एलन एस्ट्राडा: हाँ, मैं think-- 

डेविड जे मालन: क्या अनुभाग हम में हैं? एलन एस्ट्राडा: मफलर, इसलिए। 

डेविड जे मालन: ठीक है। लेकिन माइक स्मिथ जा रहा है मफलर के बाद किया जाना है। So-- 

[हँस] 

ठीक है। एलन एस्ट्राडा: हम कहाँ देख रहे हो? डेविड जे मालन: माइक स्मिथ। एलन एस्ट्राडा: माइक स्मिथ। डेविड जे मालन: अब, हम शल्य चिकित्सा में हैं। अब, चिकित्सकों। Now-- 

एलन एस्ट्राडा: चलो असली के साथ चलते हैं Let's-। रीयल। 

डेविड जे मालन: रियल। ठीक। आप रियल की जरूरत है। अब, माइक स्मिथ जो रास्ता है? 

एलन एस्ट्राडा: इस तरह। 

डेविड जे मालन: कौन सा तरीका है? एलन एस्ट्राडा: रुको। एम है- सही? हम with-- शुरू कर दिया 

डेविड जे मालन: हाँ। वे छोड़ रहे हैं। आपका अधिकार। 

एलन एस्ट्राडा: हाँ। 

डेविड जे मालन: तो माइक यहाँ में। एलन एस्ट्राडा: क्या? 

[हँस] 

बुरा उदाहरण, दोस्तों। माफ़ कीजिए। डेविड जे मालन: यह सिखाना होगा आप अपनी कुर्सी से बाहर छलांग करने के लिए। 

एलन एस्ट्राडा: ओह। ओह। तुम मुझे मिल गए। तुम मुझे मिल गए। ओह। ओह। यह ठीक है-, मैं तुम्हें मिल गया। यहीं स्मिथ? 

डेविड जे मालन: स्मिथ, धन्यवाद। तो मैं स्मिथ ऊपर देख रखेंगे? 

एलन एस्ट्राडा: ओह, हाँ। नहीं नहीं नहीं। अरे नहीं। यह मेरा है। 

डेविड जे मालन: ओह, आप स्मिथ मिला है। ठीक। 

एलन एस्ट्राडा: हाँ, मैं यहीं स्मिथ मिला है। क्षमा करें दोस्तों। मैं Michael-- सोचा हम माइकल के लिए देख रहे थे। माफ़ कीजिए। 

डेविड जे मालन: यह ठीक है। ठीक है, अब हम कर रहे हैं Paccini और संस में। 

एलन एस्ट्राडा: Paccini और बेटों। डेविड जे मालन: सिर्फ तुम और मैं इस पर कर रहे हैं। ठीक। हमें माइक स्मिथ का पता लगाएं। स्मिथ। 

एलन एस्ट्राडा: स्मिथ। 

डेविड जे मालन: स्मिथ। हम बकवास के लिए आर में कर रहे हैं। एलन एस्ट्राडा: बकवास। ओह। इसमें कुछ समय लग रहा है। 

[हँस] डेविड जे मालन: जूते। हम जूते में हैं। 

एलन एस्ट्राडा: अब हम gonna-- रहे 

डेविड जे मालन: अच्छा। एलन एस्ट्राडा: Which-- [हँस] ओह, यह बहुत अच्छा है। [हँस] 

डेविड जे मालन: यह ठीक है। 

एलन एस्ट्राडा: ओह, यह अच्छा है। मैं मैं करने जा रहा हूँ नहीं लगता इस के बाद PSAT साथी है। डेविड जे मालन: अच्छा। स्पोर्टिंग। एलन एस्ट्राडा: स्पोर्टिंग। उम, एल, एम, एन, ओ, पी डेविड जे मालन: ठीक है। तो चलो छमाही में यह आंसू करते हैं। यह ठीक है। यह वैसे भी खराब समाप्त होता माइक क्योंकि स्मिथ पीले पन्नों में नहीं होगा। 

एलन एस्ट्राडा: ओ। 

डेविड जे मालन: नहीं, यह ठीक है। लेकिन जैसे नाटक वह इस पेज पर है। तो अब, आप नीचे समस्या whittled किया है एक पेज के लिए, और हम माइक स्मिथ पाया। 

[जयकार] ठीक धन्यवाद। ठीक। यही कारण है कि असाधारण था। लेकिन यह अभी भी तेज थी रैखिक खोज से, जिसमें हम पर शुरू किताब की शुरुआत, बाएं से दाएं और हम अपने रास्ते चले जाते हैं, अंत में माइक स्मिथ की तलाश में। और हां, यदि फोन की किताब , शायद 1,000 पृष्ठों की थी हो सकता है यह ले लिया जाएगा हमें 10 या तो पेज आँसू। 

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

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

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

और अगर जॉर्डन वास्तव में कर सकता है मंच पर हमें यहाँ तक शामिल हो। बस एक पल के लिए ऊपर आओ। आपका नाम क्या है? कैरोलीन: कैरोलीन। डेविड जे मालन: कैरोलीन, ऊपर पर आते हैं। और आप में शामिल हो गए हो जाएगा मुझे यहाँ और जॉर्डन के द्वारा। कैरोलीन, धन्यवाद। ठीक है। तो हम यहाँ के लिए क्या किया कैरोलीन 26 ब्लू पुस्तकें है एफएएस प्रशासन के लिए उपयोग करता है कुछ अंतिम परीक्षा। ये खोजने के लिए मुश्किल हो रही है लेकिन हम अग्रिम में क्या किया है हम किसी का नाम रख दिया है वह यह है कि इनमें से प्रत्येक के मोर्चे पर, लेकिन हम ने यह सरल रखा है उसके बाद पूरा नाम बाहर डाल। इसलिए हम नाम के साथ व्यक्ति को रखा जाएगा एल, डी, जम्मू, बी, सभी तरह A से Z के माध्यम से, लेकिन वे यादृच्छिक क्रम में कर रहे हैं। और आप चाहते हैं यदि हां, तो अपनी बात आप के रूप में समस्या के माध्यम से रास्ता यह, तुम आगे नहीं जा सकती है और एक से जेड के लिए, हमारे लिए इन प्रकार 

दर्शकों: ठीक है, तो एल बीच, की तरह है। सी शुरुआत है। बी एल बी से पहले जम्मू, अतारांकित 

डेविड जे मालन: कि पकड़ो एक पल के लिए सोचा। अन्यथा, क्योंकि यह केवल है तुम, मुझे, और जॉर्डन के लिए दिलचस्प है। हम वहाँ चलें। दर्शकों: [अश्राव्य]। आर डेविड जे मालन: ठीक है। आप क्या कर रहे हैं? 

कैरोलीन: एम ओ के बाद आता है 

डेविड जे मालन: ठीक है। 

कैरोलीन: ओ डेविड जे मालन: हे, अच्छा है। 

कैरोलीन: ई 

डेविड जे मालन: ई, एफ हाँ। 

कैरोलीन: टी, यू, वी 

डेविड जे मालन: वी, टी, यू, वी यह तो आप जा रहा रखने making-- रहे हैं की तरह लग रहा है। आप कर रहे हैं ऐसा लगता है एक बड़ा ढेर यहाँ पर, और वहाँ पर एक बड़ा ढेर की तरह। तो वर्णमाला की पहली छमाही, वर्णमाला की दूसरी छमाही। ठीक। अच्छा। एक तरह से दो में समस्या बंटवारे। एम, एन, एक्स हाँ। कैरोलीन: लालकृष्ण डेविड जे मालन: ठीक है। लालकृष्ण तो आप किस तरह का चयन कर रहे हैं उन्हें एक के बाद एक, बाईं या दाईं या तो इसे लगाने, या जेड के फर्श पर जा रहा है। ठीक। 

कैरोलीन: जेड मंजिल पर जा रहा है। 

डेविड जे मालन: ठीक है। वाई मंजिल पर जा रहा है। अब हम एक्स डाल सकते हैं 

कैरोलीन: जी डेविड जे मालन: जी छोड़ दिया जा रहा। यह सही है जा रहा है। ठीक है, एक बाएं सभी रास्ते पर जा रहा है। 

कैरोलीन: ए, बी, सी, डी 

डेविड जे मालन: अब, अच्छा है। हम एक मिल गया है, बी, सी डब्ल्यू वहाँ नीचे जा रहा है। ठीक है, टी 

कैरोलीन: एच, मैं, जे डेविड जे मालन: एच, मैं, जे अच्छा है। कैरोलीन: केंद्र में, मैं gonna-- रहा हूँ डेविड जे मालन: ठीक है। तो अब, हम किस तरह जा रहे हैं के इन विभिन्न ढेर विलय। तो एक सी के माध्यम से, तो मैं डी देखते हैं, और ई, एफ और, और जी, और एच, और मैं अच्छा लगा। जम्मू, कश्मीर और फिर, इस ढेर है उल्टा, लेकिन यह ठीक है। ज़रूर। हम कुछ कोनों में कटौती कर सकते हैं। ठीक। और फिर हम डब्ल्यू, एक्स, वाई, जेड जरूरत 

कैरोलीन: हाँ। 

डेविड जे मालन: बहुत बढ़िया। तो एक बड़ा करने के लिए धन्यवाद इन छंटाई के लिए कैरोलीन। 

[जयकार] 

धन्यवाद। बहुत बहुत धन्यवाद। तो अब हम एक क्षण के लिए विचार करते हैं कैसे कैरोलीन कर रही है कि गया के बारे में, और क्या वास्तव में हम कैसे है-- सक्षम थे हम कि हल करने में सक्षम थे समस्या जब हम सिर्फ थे यादृच्छिक आदानों की एक पूरी गुच्छा दिया। 

खैर, यह वहाँ की तरह लग रहा है वहाँ एक प्रणाली का एक सा हो गया था? ठीक है। पहले पत्र तो वर्णमाला में, वह था बाईं ओर डाल, और वर्णमाला में बाद में पत्र, वह सही में डाल रहा था। और जैसे ही उसने पाया के रूप में कुछ समीपस्थ पत्र, लोगों को कि, एक-दूसरे के ठीक बगल में जाना वह क्रम में उन लोगों को रखा जाएगा। और इसलिए हम एक तरह से इन छोटे था होने वाली सॉर्ट आदानों के ढेर। 

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

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

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

इस one-- क़ौम जा रहे हैं एक तेज और तेज करने के लिए अब। नीचे आए। आपका नाम क्या है? ट्रेवर: ट्रेवर। 

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

तो ट्रेवर, आपसे मिलकर अच्छा लगा। यहाँ तो एक सरणी के लिए इतना है, सात दरवाजे की एक सूची बोलते हैं। आगे बढ़ो और हमें नंबर 50 लगता है। और फिर इस तथ्य के बाद, आप इसे कैसे मिला हमें बताओ। सब ठीक be-- चाहिए। हाँ, यह यहाँ एक है? उह ओह। ठीक। आपको लगता है कि एक क्लिक किया। अच्छा। 

और अच्छा। अब आपको लगता है कि एक क्लिक किया। और मुझे तुम माइक्रोफोन देते हैं, इतना है कि आप बस एक पल में यह है। आगे बढ़ो और क्लिक करें आप का इरादा है कि अगले दरवाजे। हाँ अच्छा। ट्रेवर: मैं एक दरवाजा unclick कर सकते हैं? डेविड जे मालन: नहीं, तुम unclick नहीं कर सकते। ट्रेवर: ठीक है। यह वाला. डेविड जे मालन: आप कहाँ जाना चाहते हो? कौन? 

ट्रेवर: यह एक। 

डेविड जे मालन: नहीं 

ट्रेवर: ठीक है। यह वाला. 

डेविड जे मालन: हाँ। वह अच्छा था। ठीक है। तो अपने एल्गोरिथ्म क्या था या इस ट्रेवर करने के लिए प्रक्रिया? 

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

ट्रेवर: ठीक है। 

डेविड जे मालन: क्या है होने जा रहा अपने एल्गोरिथ्म? 

ट्रेवर: यह ठीक है, यदि हल, यह या तो जा रहा सबसे बड़ी है, तो सबसे बड़ा करने के लिए be-- करने के लिए, उतरते, यह पहली बार एक हो जाएगा या यह विपरीत है, तो यह पिछले एक हो जाएगा। तो मैं सिर्फ इस दरवाजे का दोहन कर देंगे, और उसके बाद अभी पिछले दरवाजे नल। डेविड जे मालन: बहुत बढ़िया। ठीक है। इसलिए हम 50 नंबर मिल गया। इसलिए जैसे ही आप पता था वे हल किया गया है, हम इस धारणा का लाभ उठाने में सक्षम थे। इसलिए वे की तरह बहुत ज्यादा कर रहे हैं फोन की किताब उदाहरण है। जैसे ही आप भी साथ है इस तरह एक छोटी सी समस्या है, आपकी जानकारी के पूर्व हल है, हम कर सकते हैं वास्तव में यकीनन मूल्य मिल अधिक कुशलता से। 

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

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

-इस संख्या 50? 

-इस संख्या 50। और आप क्या कर सकते हैं प्रकट इन दरवाजों से प्रत्येक के पीछे बस एक उंगली से इसे छूने से। लानत है। 

[हँस] 

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

-ठीक। 

आपको यह लगता है कि अगर -और आपको फिल्म रहते हैं। आप यह नहीं मिल रहा है, तो आप इसे वापस दे। 

मैन। 

-ओह! 

- [अश्राव्य] ठीक है। इसलिए मैं समाप्त होता है की जाँच करने के लिए जा रहा हूँ ओह there's--, तो यह निर्धारित करने के लिए पहले। 

[वाहवाही] 

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

[वीडियो प्लेबैक] 

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

[हँस] 

यह एक चाल सवाल नहीं है। एक। 

[हँस] इस बिंदु पर, अपने स्कोर में बहुत नहीं है अच्छा, तो आप के रूप में अच्छी तरह से जा रहा रख सकता है। तीन। 

[हँस] 

जारी रखें। सच कहूँ तो, लेकिन मैं मदद नहीं आश्चर्य कर सकते हैं क्या आप भी so--, के बारे में सोच रहे हैं 

[हँस] केवल शीर्ष पंक्ति है, इसलिए आप तीन छोड़ दिया गया। तो मुझे सात लगता है। 

[हँस] 17। सात. 

[वाहवाही] 

ठीक है। 

[अंत प्लेबैक] 

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

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

तो turquoise-- हरे रंग में से एक यह है? आप प्रतिबद्ध हैं? दो। नीचे आए। ठीक। तीन। चार। , पांच ठीक me-- करते हैं। आप अपने दोस्त द्वारा नामित किया जा रहा हो। छह, सात और आठ। आ जाओ। ठीक है। बहुत बहुत धन्यवाद। आ जाओ। आ जाओ। 

ठीक है। इसलिए हम here-- और इस के लिए क्या किया अधिक अजीब लोगों के बीच में है, इस के बाद आपको लगता है कि हास्य की आवश्यकता होगी समय का सिर्फ एक छोटा सा के लिए मुझे। आप नंबर एक हो जाएगा। आपका नाम क्या है? 

अन्नान: अन्नान। 

डेविड जे मालन: अन्नान। डेविड। आपका नाम क्या है? 

यूसुफ: यूसुफ। 

डेविड जे मालन: यूसुफ, आप नंबर दो हैं। 

सेरेना: सेरेना, तीन नंबर। स्टीफन, चार नंबर। CYNTHIA: सिंथिया। डेविड जे मालन: सिंथिया, पांच नंबर। [अश्राव्य] डेविड जे मालन: [अश्राव्य]। डेविड, छठे नंबर। मैट: मैट। डेविड जे मालन: मैट की सातवें नंबर। और? 

WAVERLY: वेवरली। 

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

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

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

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

ठीक। तो दो और चार, मुझे जाने दो आगे और सिर्फ आप दो स्वैप। आप शारीरिक रूप से स्थानांतरित कर सकते हैं अपने आप को और अपने कागज, मैं मिल गया है लगता एक बेहतर स्थिति में सूची। 

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

ठीक है, स्पष्ट रूप से नहीं। लेकिन यह सही है, एक छोटे से बेहतर है? हुआ नोटिस क्या है। हर बार हम एक स्वैप, प्रदर्शन एक छोटे नंबर एक तरह से उस तरह से percolated, और एक बड़ी संख्या इस तरह से percolated, या हम करेंगे करने के लिए bubbled कह शुरू छोड़ दिया है या सही करने के लिए bubbled। 

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

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

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

मुझे क्या करना है या इस आखिरी पारित नहीं किया? दर्शकों: कोई बदलाव नहीं हुआ। डेविड जे मालन: क्षमा करें? दर्शकों: कोई बदलाव नहीं। डेविड जे मालन: कोई बदलाव नहीं हुआ। इसलिए मुझे यह करने की बेवकूफी होगी फिर एक ही है कि एल्गोरिथ्म करना मैं किसी भी नहीं किया है तो पहली बार बदलता है। और राज्य नहीं बदला है। निश्चित रूप से, मैं बनाने के लिए नहीं जा रहा हूँ किसी भी दूसरी बार बदलता है। और हां, यह अब सुरक्षित है कहने के लिए, सूची हल है। 

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

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

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

बंद गिरने के बिना तो चरण इस साल मैं नंबर हड़पने के लिए जा रहा हूँ one-- और आपका नाम फिर क्या था? 

अन्नान: अन्नान। 

डेविड जे मालन: अन्नान। और तुम मुझ पर शामिल हो सकते हैं सूची की शुरुआत, तुम कहाँ चलो तुम डाल दिया। Unfortunately-- तुम्हारा नाम क्या है? 

STEFAN: स्टीफन। 

डेविड जे मालन: स्टीफन रास्ते में है। स्टीफन इस हल करती है तो इससे पहले कि समस्या यह है कि हमें क्या करना चाहिए? हम स्टीफन के साथ क्या करते हैं? 

दर्शकों: [अश्राव्य]। डेविड जे मालन: ठीक है। तो क्या हम ऐसा कर सकता है। हम की तरह स्टीफन और ले सकता है उसके चार, और सिर्फ एक चर में डाल दिया और के लिए यह करने के लिए पर पकड़ समय के कुछ राशि, जिससे नंबर एक के लिए कमरे में कर रही है। और कहा कि बुरा नहीं है। मैं क्यों नहीं करते हैं, सुझाव सकता है हम बस यहाँ स्टीफन रखा है? क्यों यह एक का उल्लंघन हो सकता है विचारों का हम शुरू पिछले सप्ताह, पिछले समय के बारे में बात कर रही है? हाँ? 

दर्शकों: [अश्राव्य]। 

डेविड जे मालन: इसके लिए कोई सूचकांक है। आप एक के रूप में, वास्तव में, इस के बारे में सोच सरणी, इस नकारात्मक एक की तरह है, तो कोई स्मृति वास्तव में नहीं है यहाँ यह वास्तव में एक सरणी है, जैसे हम व्याख्यान में पिछले सप्ताह घोषणा की। इसलिए हम यह नहीं करना चाहिए। हम एक चर में स्टोर हो सकता है। 

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

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

और अब, मैं करने के लिए क्या जा रहा हूँ नंबर एक के बारे में भूल जाता है स्थायी रूप से, क्योंकि मुझे पता है मेरे पीछे सूची अब हल है। तो मेरी सूची में पहले से आकार आठ था। अब, यह आकार सात वर्ष की है। इसलिए मेरी समस्या हो रही है रैखिक हालांकि, छोटे। तो अब, मैं चयन करने के लिए जा रहा हूँ वर्तमान छोटी तत्व, दो। छह, आठ, चार, तीन, सात, पांच। यही कारण है कि छोटी से छोटी तत्व था। तो क्या मैं with-- करने जा रहा हूँ दोबारा आपका नाम क्या है? 

यूसुफ: यूसुफ। 

डेविड जे मालन: यूसुफ? हम जगह में यूसुफ को छोड़ने के लिए जा रहे हैं। अब, मैं नाटक करने के लिए जा रहा हूँ इन लोगों को अच्छी तरह से are-- कि, मुझे पता है कि इन दो पहले से ही हल कर रहे हैं। चलो अब पर ध्यान केंद्रित करते हैं सूची के शेष। छह वर्तमान में सबसे छोटी है। आठ बड़ा है। चार अब वर्तमान में सबसे छोटी है। तीन अब वर्तमान में सबसे छोटी है। और हां, अब मैं तीन का चयन करने के लिए जा रहा हूँ जो अपने नाम फिर क्या है-? सेरेना: सेरेना। डेविड जे मालन: सेरेना, अगर तुम सकता है अपना नंबर और स्वैप with-- हड़पने KALSANG: Kalsang। डेविड जे मालन: Kalsang। पीठ पर आते हैं, और हम कर रहे हैं उन दो स्वैप करने के लिए जा रहा है। और अब, के ऑटोपायलट पर इस डाल दिया। मुझे जाना है और तुम लोगों के लिए इसे छोड़ने के लिए जा रहा हूँ छोटी अगले तत्वों का चयन करने के लिए। डन डन डन डन। चार नंबर, आप क्या करना चाहिए? बहुत बढ़िया। अब, मैं एक और पारित करने के लिए जा रहा हूँ। डन डन डन डन। मैं पाँच छोटी अगले है देखते हैं। अब, मैं एक और पास ले जा रहा हूँ। डन डन डन डन। छह सबसे छोटी है। अच्छा। सात सबसे छोटी है। कोई परिवर्तन नहीं होता है। आठ सबसे छोटी है। हो गया। 

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

तो यह शायद, और भी आसान है Intuitively, पिछले की तुलना में। के एक पिछले एक कोशिश करते हैं। तुम लोगों को अपने आप को फिर से कायम कर सकता है निम्नलिखित पदों में एक अंतिम समय, चलो देखते हैं, तो हम नहीं कर सकते अब एक अन्य दृष्टिकोण को औपचारिक। वास्तव में, होगा किसी को वहाँ से बाहर का प्रस्ताव करना हम ऐसा करने के बारे में कैसे और जाना हो सकता है? Buzzwords या प्रकार बाहर फेंकना बिना पहले से ही जाना जाता है कि जवाब में से, बस intuitively, हम क्या कर सकता है? 

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

तो मुझे सिर्फ बंधेज जाने कि इस सूची हल है। लेकिन अब मैं इस सूची के बाकी है। तो अब, मैं दो मुठभेड़। जहां स्पष्ट रूप से दो करता है चार के लिए सम्मान के साथ हैं? चार से पहले। तो मैं यहाँ क्या कर सकते हैं? कृपया फिर से अपना नाम बताएं? 

यूसुफ: यूसुफ। 

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

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

अब, मैं एक तरह से मैं undone-- है आगे और फिर एक कदम उठाया एक कदम पीछे, क्योंकि अब यूसुफ आदेश से बाहर किया जाएगा। तो चलो यह करते हैं। आप नंबर एक ले सकता है और बस एक पल के लिए वापस कदम। हम कैसे put-- क्या कर सकते हैं आपका नाम फिर से था? 

अन्नान: अन्नान। 

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

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

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

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

[वाहवाही] 

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

तो यह पता चला है कि एक बुलबुला प्रकार के साथ, ठीक है, कितने कदम मैं पर ले जाना है कि एल्गोरिथ्म के पहले पास? मैं, चलो एक see-- जाने take-- सकता है दो, तीन, चार, पांच, छह, सात। और यहाँ आठ तत्वों नहीं है। तो यह n करने के लिए शून्य से 1 कदम की तरह है सूची की शुरुआत से मिलता है सूची के अंत में। 

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

लेकिन तब मैं की जरूरत नहीं है इस तत्व को देखते रहो, क्योंकि मुझे पता है यह पहले से ही छोटी से छोटी। तो अब, मैं सिर्फ सात पर देख सकते हैं तत्वों, तो छह तत्वों, तो फिर पांच तत्वों, चार तत्वों। और तो गणितीय, n है, तो तत्व या संख्याओं की संख्या हम साथ शुरू कर दिया है, तो आप कल्पना कर सकते हैं इस n शून्य से 1 के रूप में ही है कि, प्लस n शून्य से 2 कदम, प्लस n शून्य से 3 चरणों, प्लस n शून्य से 4 कदम, सब जिस तरह से नीचे सिर्फ एक कदम के लिए। और मैं अपने अंतिम व्यक्ति पर हूँ। 

और आप एक बहुत याद करते हैं कि यदि की किताबें या गणित की किताबें आँकड़े पर उन सूत्रों है वापस हार्डकवर या उनके सामने, यह इस श्रृंखला पता चला है कि अधिक बस व्यक्त किया जा सकता n बार n के रूप में शून्य से 2 पर 1। ऐसा नहीं है और अगर यह ठीक है आपके मन में सबसे आगे। लेकिन यह वास्तव में सच है। यही कारण है कि इसे लिखने का सिर्फ एक सरल तरीका है। और फिर अगर आपको लगता है वापस ग्रेड स्कूल को, तुम सिर्फ गुणा शुरू करने के समय चीजें बाहर, निश्चित रूप से यह, सिर्फ n चुकता शून्य से 2 n से विभाजित है। मैंने किया है सभी का विस्तार है वहाँ भाव। और तो यह फिर से लिखना थोड़ा अलग तरह से। यही कारण है कि 2 n शून्य से एन / 2 से विभाजित चुकता है। 

तो फिर, मैं बस की तरह आवेदन कर रहा हूँ कुछ गणित वहाँ नियम। लेकिन अब नोटिस कि सबसे बड़ी अवधि इस अभिव्यक्ति में, तो बात है, n चुकता है। तो हाँ, यह n चुकता है 2, शून्य से एन / 2 से विभाजित। 

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

इसलिए हम 1 लाख लोगों के लिए किया था लगता है चरण, या 1 लाख चीजों पर हम की तरह करना चाहते हैं। के एक लाख प्लग ठीक है कि सूत्र में यह कुल लगता है कि कितने चरण देखें कहते हैं का उपयोग कर एक लाख तत्वों को सॉर्ट करने, चयन छांटना। 

इसलिए हम पहले की तरह ही सूत्र होगा। मैं इतना है कि मैं एक लाख प्लग होता एक लाख, 2 से विभाजित चुकता शून्य से एक लाख 2 से विभाजित। मैं पहले से है कि गणित करते हैं यहाँ, हम 500 अरब है शून्य से 500,000, जो , 499,999,500,000 हमें देता है जो रफ़ू बड़ा है। 

वास्तव में, आप अब की तुलना 499,000,000,000, 999,000,000, हमारे मूल कीमत के खिलाफ 500,000, 500 अरब, यह तो बहुत करीब है। है ना? 2 n देता से विभाजित चुकता us-- या यों कहें, एन 2 से विभाजित चुकता हमें 500 अरब दे दी है। यह बहुत अरे करीब है 499,999,500,000 के लिए, बंद 500,000 घटाकर जो कहना है, या अधिक आम तौर पर, बंद घटाकर एन वास्तव में नहीं है, एक बड़ा सौदा चुकता। इन बनाता n चुकता संख्या वास्तव में तेजी से बढ़ता है। 

अब, यह केवल महत्वपूर्ण है जहां तक हम के रूप में, कंप्यूटर वैज्ञानिकों के रूप में, आम तौर पर इतना ध्यान नहीं जा रहे हैं इन सूत्रों की बारीकियों के बारे में और वास्तव में क्या सटीक जवाब हैं। हम ही नहीं, आप जानते हैं कि क्या परवाह है? दिन के अंत में, इस सूत्र चुकता n के आदेश पर है। 

हाँ, हम वहाँ में 2 से विभाजित कर रहे हैं। हाँ, हम बंद n शून्य से 2 घटाकर रहे हैं। लेकिन दिन के अंत में, अवधि कि वास्तव में हमें दर्द होता है और हमें लागत कदम की एक बहुत कि वर्ग शब्द है। और तो क्या एक कंप्यूटर वैज्ञानिक आम तौर पर ऐसा करने के लिए जा रहा है उन सभी की अनदेखी कर रहा है छोटे आदेश शर्तों, और सिर्फ एक पर लग रही है कि लागत के लिए सबसे अधिक योगदान देता है। 

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

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

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

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

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

आठ लोगों को पहले ही सुलझा लिया। और मैं प्रविष्टि प्रकार का उपयोग करें। एल्गोरिदम की है कि पिछले। ठीक है, चलो असली तेजी reenact करते हैं। मैं यहाँ शुरू तो, अगर मैं एक देखते हैं। जहां एक हैं करता है? यह ठीक है यहाँ अंतर्गत आता है। मैं दो देखते हैं। जहां दो हैं करता है? यहीं। मैं तीन देखते हैं। जहां तीन हैं करता है? यहीं। 

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

खैर, क्या वास्तव में ऐसा होता है इस संख्या में है तो क्या होगा? और हम सिर्फ उदाहरण के एक जोड़े को क्या करेंगे। क्या नंबर आठ, वास्तव में, यदि यहाँ है, और number-- वूप्स। तो क्या हुआ अगर, वास्तव में, नंबर आठ, यहां पर सभी तरह से है और मैं प्रविष्टि प्रकार का उपयोग कर रहा हूँ? 

ठीक। मैं यह जगह में इस समय दावा करते हैं। लेकिन अब, seven-- जहां सात जाना है? बेशक, यह यहाँ पर चला जाता है। तो मैं एक जगह पर आठ बढ़ना है। अब छह, जहां यह जाना है? तो ठीक है। अब, मैं आठ स्थानांतरित करने के लिए है एक जगह है, और एक जगह पर सात, और फिर मैं छह नीचे खटखटाने। 

तो पहली बार, यह लागत चीजों को ठीक करने के लिए मुझे एक कदम है, तो यह चीजों को ठीक करने के लिए मुझे दो चरणों की लागत। यह कितने कदम है ठीक करने के लिए ले जा रहा सही जगह में पांच डाल करने के लिए बातें? तीन। अब मुझे करना है क्योंकि , एक, दो, तीन चलते हैं। कितने कदम इसे लेने के लिए जा रहा है सही जगह में चार डाल करने के लिए? 4 प्लस 5, प्लस 6, प्लस 7। 

और तो यह करने के लिए गणितीय समान है हम चयन प्रकार के लिए वर्णित है। हम इस श्रृंखला है कि सिर्फ बढ़ती जा रही है। 1 प्लस 2 प्लस 3 प्लस 4, या इसके विपरीत, 7 प्लस 6 प्लस 5 प्लस 4 आज के लिए के लिए कहते हैं n के आदेश पर करने के उद्देश्यों चुकता। 

तो मुझे भी निर्धारित करना है कि चलो बुलबुला तरह एन चुकता में भी है। क्योंकि बुलबुला तरह, प्रत्येक के साथ बार मैं सूची के माध्यम से जाना मैं मोटे तौर पर कितने कदम उठा रहा हूँ? हर बार जब मैं सचमुच वहाँ से वहाँ के लिए चलते हैं? मोटे तौर पर एन कदम। लेकिन कितनी बार मैं हो सकता है सूची के माध्यम से जाने की जरूरत है? 

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

लेकिन बुलबुला तरह से, कितनी दूर एक करता है सूची के माध्यम से अपने पहले पारित पर ले जाते हैं? कितने धब्बे वह प्राप्त करता है सही जगह के करीब? सिर्फ एक। तो इस के माध्यम से आप अगर तरह का कारण इस एल्गोरिथ्म के माध्यम से हर समय, दाऊद के लेने के लिए मोटे तौर पर एन कदम। लेकिन कितने गुजरता सूची में यह है के माध्यम से बुलबुले के लिए एक के लिए ले जा रहा जहां यह है बाईं करने के लिए? 

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

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

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

एक फोन में माइक स्मिथ मिल क्योंकि सबसे खराब स्थिति में n पृष्ठों की पुस्तक, मुझे एन कदम ले सकता है। उपस्थिति लेने के बारे में क्या? एक दो तीन चार पांच छह। इस का समय चल रहा है क्या है उपस्थिति लेने के लिए एल्गोरिथ्म? क्योंकि सिद्धांत में N की बड़ी हे, मैं कमरे में हर किसी के लिए बात करनी है। 

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

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

और वास्तव में, की संख्या कदम डिवाइड प्रदर्शन और जीत के लिए लेता है, या द्विआधारी खोज के रूप में हम शुरू करेंगे फोन की किताब के रूप में, यह फोन लॉग इन करें और कदम के आदेश पर है। और यह एक अजीब से एक का एक सा है। 

एक कदम लेता है क्या, या अधिक विशेष कदम की एक निरंतर संख्या? शायद यह हो सकता है यह तीन है, दो है, लेकिन एक कंप्यूटर वैज्ञानिक सिर्फ 1 के बड़े हे के रूप में इसे सरल, कदम से कुछ निरंतर संख्या। आपको लगता है कि कुछ कर सकता क्या है कदम की एक निरंतर संख्या लेता है? 

ताली बजाने का समय चल रहा है? लगातार समय। है ना? की तरह, का समय चल रहा है सिर्फ एक लेता है कि कुछ भी कर रही है आपरेशन, जैसे एफ नमस्ते विश्व प्रिंट। यही कारण है कि लगातार समय होने के लिए कहा जा सकता है प्रिंट एफ के साथ कम कोने मामला है, जब तक क्या समय चल रहा हो सकता है प्रिंट की एफ वास्तव में हो सकता है? और क्यों? उस मामले में n मापने क्या है? 

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

यही कारण है कि ओमेगा संकेतन है। बड़ी हे, क्या इसका मतलब है जबकि ऊपरी चल रहे अपने समय पर ही? ज़्यादा से ज़्यादा है, कितना समय कुछ समय लग सकता है? Omega-- खेद इस आ रहा रखता है up-- उस के विपरीत है, यह एक कम बाध्य पर है जिससे समय कुछ की राशि ले सकता है। 

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

यह करने के लिए ले करता है कितना समय सबसे अच्छा में क्रमबद्ध n तत्वों बुलबुला प्रकार की तरह कुछ का उपयोग कर मामला? अपनी सूची में पहले से ही हल है मान लीजिए। हम बुलबुला तरह लेता है पर कहा n के आदेश कदम चुकता। लेकिन यह पहले से ही क्या हल है तो क्या होगा? क्या आप के बाद एहसास यदि सरणी के माध्यम से एक पास कि आप कोई स्वैप कर दिया है? आप गुजरता अधिक बनाने रखने की जरूरत है? 

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

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

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

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

और यह भी देने को समाप्त होता है अंतिम परिणाम। अब उन के सभी तीन बहुत तेजी से महसूस किया। और वास्तव में, मैं उन्हें दौड़ा एक बहुत अच्छा क्लिप पर। लेकिन मौलिक रूप से, वे सभी कर रहे हैं बहुत भयानक, ईमानदार हो। इन एल्गोरिदम के सभी प्रकार अब तक n के बड़े हे में है कि रन चुकता का बहुत थोड़ा ले समय अंत में चलाने के लिए। 

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

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

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

[Beeping] 

जिससे आप एक आवृत्ति आवेदन कर रहे हैं बार बार की ऊंचाई पर आधारित है। यह बुलबुला तरह है। 

[विकृत beeping] 

आने वाले है- अगले आ रहा है अगले है- चयन तरह, जहां फिर, हम का चयन कर रहे हैं अगले छोटी तत्व, और हम यह बढ़ रही देख सकते हैं बाएं से दाएं। 

हमारे विजेता इस प्रकार अब तक आज, तरह मिलाएं। यह बातें विभाजित है सूचना कैसे [अश्राव्य] आधा और क्वार्टर में। हम नहीं है जो सूक्ति तरह, के बारे में बात की थी, और नेत्रहीन बनाता है और एक का एक सा audally विभिन्न आकार और ध्वनि। आगे और पीछे जा कर, चीजों को साफ। इसके अलावा heapsort बाहर की जाँच इस आदमी की वेबसाइट पर। 

और यह बात है। हम आपको अगली बार देखेंगे। 

[Whooshing और संगीत]