>> [संगीत खेल]
>> डेविड जे मालन: सब ठीक है.
तो वापस स्वागत करते हैं.
इस CS50 है, और सप्ताह के अंत में तीन.
>> तो, पिछले कई हफ्तों में याद हम की काफी थोड़ा खर्च किया गया है
सी पर, प्रोग्रामिंग पर, वाक्यविन्यास पर समय.
आप अभी भी कर रहे हैं और अगर यह काफी सामान्य है हो सकता है, समस्या सेट 2 के साथ संघर्ष
दीवार के खिलाफ अपना सिर पीटने.
यह गुप्त दिखने त्रुटि संदेश है और कीड़े कि आप
काफी नीचे का पीछा नहीं कर सकते हैं.
, बाकी का आश्वासन दिया, क्योंकि उस में सिर्फ एक कुछ सप्ताह का समय आप पीठ पर देख लेंगे
सीज़र, और [की तरह बातें? वि genair,?] शायद यह भी दरार, और
तुम आ गए अभी कितनी दूर एहसास समय की एक छोटी अवधि में.
तो यह है कि किसी भी सांत्वना है, अब के लिए वहाँ में लटका.
>> आज, हालांकि, हम संक्रमण के लिए शुरू बातें उच्च स्तर पर.
और हम के लिए दी लेने के लिए शुरू कि तुम लोग कैसे प्रोग्राम पता है, या कम से
के कम से कम शुरुआत उस सुविधा के स्तर.
और हम पर विचार करना शुरू करेंगे हम कैसे कर सकते हैं अधिक कार्यक्रमों को डिजाइन करने के बारे में जाना
प्रभावी ढंग से.
हम अनुकूलन के बारे में कैसे जा सकते हैं हमारे एल्गोरिदम की क्षमता है, और
आम तौर पर अधिक सुलझाने दिलचस्प समस्याओं.
और उस के लिए दी लेने के लिए शुरू, हम चाहते थे, हम किसी भी कोड सकता
उदाहरण के हम मन में है.
तो आज, हम कीबोर्ड पर नहीं टिकते कोड के किसी भी रूप के लिए.
यह बहुत उच्च स्तर होगा, और अंत में, के बारे में समस्या को सुलझाने.
>> तो उस बात पर आते हैं, मुझे का प्रस्ताव करते हैं जो निम्न सात
आयतों के पीछे, सात दरवाजों का प्रतिनिधित्व की एक पूरी गुच्छा रहे हैं जो
संख्या 50 है, जो बीच में संख्या,.
मुझे इस पर इस परियोजना के चलो साथ ही यहाँ स्क्रीन.
और हम एक स्वयंसेवक की जरूरत है कि प्रस्ताव मेरे सामने एक नंबर मिल मदद
देखने के लिये यहां इंटरनेट.
गुलाबी में, ऊपर आओ.
ठीक है.
तुम्हारा नाम क्या है?
>> जेनिफर [सुनाई]
>> डेविड जे मालन: क्षमा करें?
>> जेनिफर: जेनिफर.
>> डेविड जे मालन: जेनिफर.
सब ठीक है, जेनिफर.
आपसे मिलकर अच्छा लगा.
ऊपर आओ.
यहाँ तो इन सात दरवाजे हैं, और क्या मैं, आप यहाँ हमारे लिए क्या करना चाहते हैं
अपने सहपाठियों के सभी के सामने, हमें संख्या, 50 पाते है.
एक नंबर मिल जाए, आप के पीछे झांकना कर सकते हैं बस दोहन से इन दरवाजों के किसी भी
दरवाजों में से एक है, और उस पर इसकी संख्या खोलेगा.
और यह कैसे जल्दी से आप देखते हैं हमें संख्या, 50 को पा सकते हैं.
>> 15.
16.
50.
अच्छी तरह से किया.
ठीक है.
जेनिफर लिए प्रशंसा का दौर.
>> [वाहवाही]
>> ठीक है.
तो के लिए आपकी रणनीति क्या थी संख्या, 50 ढूँढने?
>> जेनिफर: उम, मैं शायद सोचा कि अगर -
[सुनाई]
>> डेविड जे मालन: ओह.
यह एक दूसरी दे.
ऐसा करने के लिए अपनी रणनीति थी संख्या, 50 ढूँढने?
>> जेनिफर: तो मैं बस अभी शुरू क्या पहले नंबर देखने के लिए शुरुआत
था, और फिर मैं शायद अगर सोचा, वे हल कर रहे हैं, मैं सिर्फ रखेंगे
उच्च ऊपर दोहन?
>> डेविड जे मालन: ठीक है.
और हम मिल गया है लगता कि मामला हो.
हालांकि, की परतों वापस छील जाने बस थोड़ा सा, और आप जाना चाहते हैं
आगे और दूसरे दरवाजे से पता चलता है आप चुन सकते थे?
>> जेनिफर: ओह, प्यारे.
>> डेविड जे मालन: आह.
>> जेनिफर: तो मैं सिर्फ भाग्यशाली है.
>> डेविड जे मालन: तो आप भाग्यशाली है.
ठीक है.
इतना बुरा नहीं.
लेकिन यह है कि एक दिलचस्प है अंतर्दृष्टि, सही?
, आप मान लिया, और आपको मिला हैं वास्तव में, वहाँ भाग्यशाली एक सा है.
लेकिन आप संख्याओं थे मान लिया है कि अगर हल, आप और अधिक सटीक हो सकते हैं
कि प्रभावित के रूप में कैसे अपने व्यवहार?
>> जेनिफर: वे हल किया गया तो, तो मैं सबसे बड़ा करने के लिए शायद सबसे छोटी सोचा.
>> डेविड जे मालन: ठीक है.
>> जेनिफर: या यह समाप्त हो गया, तो जा रहा है वास्तव में बड़ा है, तो सबसे बड़ी छोटी करने के लिए.
>> डेविड जे मालन: ठीक है.
तो सबसे बड़ी छोटी, या करने के लिए सबसे बड़ा करने के लिए छोटी से छोटी.
लेकिन मुझे का प्रस्ताव करते हैं, आप के लिए किया था लगता है अशुभ हो गया, और लगता है कि वे
वास्तव में, हल, कितने, नहीं थे उन दरवाजों आप झांकना था हो सकता है
कि सबसे खराब स्थिति में पीछे?
>> जेनिफर: वे सब के सब.
>> डेविड जे मालन: वे सब के सब.
तो चलो एन के रूप में है कि सामान्यीकरण करते हैं.
वहाँ 7 में होने वाला है, लेकिन अधिक चलो आम तौर पर पता दरवाजे कहते हैं कि वहाँ
यहाँ स्क्रीन.
तो सबसे खराब स्थिति में, आप होगा 7 दरवाजे, या एन दरवाजों के पीछे देखने के लिए.
और हां यह सच है, इसके बारे में एक सा है भाग्य आज, लेकिन यह वास्तव में एक रेखीय है
एक तरह की एल्गोरिथ्म, यहां तक ​​कि आप हालांकि एक तरह से चारों ओर लंघन थे.
यह ठीक है?
>> जेनिफर: हाँ.
>> डेविड जे मालन: ठीक है, मुझे देखते हैं अगर आपके मैं करने के लिए हमें ले जाते हैं तो रणनीति में परिवर्तन
यहाँ के साथ हमारे दूसरे उदाहरण 7 अलग दरवाजे.
एक ही नंबर है, लेकिन इस समय वे हल कर रहे हैं.
होने जा रहा यहाँ अपनी रणनीति क्या है, अपने दिमाग से बाहर डालने की कोशिश कर क्या
दूसरे नंबर थे -
>> जेनिफर: ठीक है.
>> डेविड जे मालन: - पहले?
>> जेनिफर: चलो शुरू करते हैं पहली बार एक साथ.
>> डेविड जे मालन: सब ठीक है.
पहली बार एक साथ शुरू करो.
4.
अब तुम जाने के लिए जा रहा है, और यही कारण है कहाँ?
>> जेनिफर: 4 वास्तव में छोटा है.
इसलिए वे की तरह हो सकता है कि छोटी से छोटी हो अगर सबसे बड़ा करने के लिए, यह होना चाहिए
- दो बार, और हो.
>> डेविड जे मालन: ठीक है.
आपको लगता है कि जो, चलो देखते हैं?
>> जेनिफर: पिछले एक कोशिश करें.
नाइस.
>> डेविड जे मालन: बहुत अच्छी तरह से किया.
ठीक है.
>> [वाहवाही]
>> डेविड जे मालन: ठीक है.
तो आप वास्तव में यह कर रहे हैं बुरी तरह, आप कर रहे हैं, क्योंकि
यह बहुत अच्छी तरह से कर रही.
असमर्थ करने के लिए हमें जो पत्ते कुछ बिंदुओं बनाते हैं.
तो चलो यहाँ वापस रोल करने की कोशिश करते हैं.
>> जेनिफर: ठीक है.
>> डेविड जे मालन: बहुत अच्छी तरह से बहरहाल, किया.
तो अगर आप शुरुआत में शुरू आप यह आप तब, 4 था कि देखा
अंत में ले जाया गया.
लेकिन तुम भाग्यशाली नहीं मिला लगता है वहाँ, और अनुमान है 50
कहीं और था.
अपने तीसरे चरण के लिए क्या किया गया है?
>> जेनिफर: शुरुआत के लिए वापस जाओ.
>> डेविड जे मालन: वापस जाएँ शुरुआत करने के लिए.
ठीक है, तो आप को छुआ गया होता 8 था जो इस दरवाजे,.
ठीक है.
तो यह है कि 50 नहीं है.
तुम कहाँ अगले देखा होगा?
>> जेनिफर: अगर मैं नहीं था वे क्रमबद्ध पता है.
>> डेविड जे मालन: सही है.
खैर, अगर तुम किया था पता वे हल किया गया -
>> जेनिफर: ओह, हाँ, क्या पता था.
>> डेविड जे मालन: - लेकिन तुम नहीं किया 50 अभी तक था, जहां पता है?
>> जेनिफर: बस जाते रहते हैं.
>> डेविड जे मालन: सब ठीक है.
ठीक है.
चलते रहो.
ठीक है, मैं के साथ काम कर सकते हैं.
>> जेनिफर: ठीक है.
>> डेविड जे मालन: अब, आप अभी कर रहे हैं जा रहा रखने के लिए जा रहा है, क्या आपका है
एल्गोरिथ्म devolving में समर्थन किया.
>> जेनिफर: रैखिक -.
>> डेविड जे मालन: यह रेखीय की तरह है.
लेकिन, मुझे का प्रस्ताव करते हैं मुझे मौके पर ही डाल दिया.
मुझे पेज को रीफ्रेश करते हैं.
एक ही नंबर है, वही व्यवस्था, एक ही दरवाजे.
लेकिन में वापस कि पहले दिन के लिए लगता है वर्ग जब हम में एक फोन पुस्तक फाड़े
आधा है, की तरह, और क्या था वहाँ हमारी रणनीति?
>> जेनिफर: मध्य में शुरू करो.
>> डेविड जे मालन: ठीक है.
इसलिए मध्य में शुरू करो.
तो चलो आगे जाना है और अनुकरण करते हैं.
द्वारा मध्य में शुरू करो उस दरवाजे खुलासा.
तो 16 नंबर.
तो मजबूत आदमी क्या किया होता, जो आधे में फोन पुस्तक फाड़े
अगले अनुमान को प्राप्त करने के लिए?
>> जेनिफर: इस छमाही में जाओ.
>> डेविड जे मालन: और क्यों सही करने के लिए?
>> जेनिफर: वे की तरह सबसे छोटे थे तो सबसे बड़ा करने के लिए, तो 50 होना चाहिए
कि अंत में.
>> डेविड जे मालन: अच्छा.
पूरी तरह से उचित है.
तो एक फोन की किताब की तरह, आप के लिए जाना यहां बाईं ओर का विरोध किया, लेकिन सही रूप
कुंजी takeaway है.
अब आप दूर फेंक, या बंद कर सकते हैं आंसू इस समस्या का आधा, आप नहीं छोड़ने
7 दरवाजे के साथ, लेकिन वास्तव में सिर्फ 3 के साथ.
का लगभग आधा है जो समस्या के आकार.
ठीक है.
तो अब आप क्या होगा आप सही जाने के बाद किया?
>> जेनिफर: तो 16 अभी भी बहुत छोटा है, 50 के सापेक्ष, तो शायद मैं कोशिश करता हूँ,
जैसे, यह एक.
>> डेविड जे मालन: सब ठीक है.
42.
ठीक है, तो अब क्या आपकी है आपको बता रहा वृत्ति?
>> जेनिफर: मैं दूर फेंक कर सकते हैं इस और फिर बस -
>> डेविड जे मालन: ठीक है.
अच्छा, आप दूर फेंक कर सकते हैं वहाँ बाईं आधा.
>> जेनिफर: - यह एक चुनना.
>> डेविड जे मालन: और सही.
>> जेनिफर: हाँ.
>> डेविड जे मालन: तो यह मुश्किल है, भले ही केवल जब वहाँ, शायद देखने के लिए
7 दरवाजे,, अब, के बारे में सोचना की स्थिरता
आप अभी लागू एल्गोरिथ्म.
पिछले मामले में, तुमने किया महान था, जो भाग्यशाली हो.
लेकिन अगर आप एक अनुमानी का उपयोग किया था, मैं कहूँगा.
आप अपने सहज ज्ञान के आधार पर क्रमबद्ध प्रयोग किया जाता है, और यह सुंदर है अगर यह हल जानने के
शुरुआत में छोटे, स्पष्ट रूप से, हम है सही करने के लिए अधिक जाना है.
लेकिन कुछ समझ में, आप भाग्यशाली है, शायद यह संख्या 100 थी, क्योंकि
और शायद 50 के बीच में अधिक था.
शायद 50 भी यहां खत्म हो गया था.
>> लेकिन यदि आप एक छोटे से अलग क्या किया इस समय आप एक ही काम किया था,
बार - बार.
और मैं तर्क होता है कि क्या आप बस , हालांकि फोन से प्रभावित था
किताब उदाहरण है, बहुत कुछ है अधिक एल्गोरिथम, और भी बहुत कुछ
कम विशेष मामलों.
बहुत कम सहज.
तो दिन के अंत में, कैसे होगा आप की दक्षता का वर्णन
तुम चले गए, जहां पहले एल्गोरिथ्म, बनाम, सही करने के लिए छोड़ दिया
यहां दूसरे एल्गोरिथ्म?
>> जेनिफर: यह एक तरह होना चाहिए, शायद हाँ, यहाँ तक कि अधिक समय आधा करना, या.
>> डेविड जे मालन: ठीक है, शायद उससे भी ज्यादा.
उस पर थोड़ा जोर से धक्का करते हैं.
सच क्या है, हम यह जारी है तर्क, हम निश्चित रूप से आधी
इस दूसरे एल्गोरिथ्म के साथ समय चल रहा है के आधे से दूर फेंकने से
संख्या है, लेकिन हम अगले पर क्या किया जेनिफर पता चला जब चलना,
दूसरे नंबर?
>> हम फिर से दरवाजे की संख्या आधी हो गई.
और फिर अगर हम, उसके बाद क्या किया साथ खेलने के लिए और अधिक दरवाजे थे?
हम उन्हें आधा करना, और फिर, होगा और फिर, और फिर से.
और यह सब सिर्फ आप लोगों की तरह था के पहले सप्ताह में खड़े
वर्ग, आप नीचे बैठने का आधा, आधा क्या आप का, आधा नीचे बैठे
एक अकेला, जब तक नीचे बैठे आत्मा खड़ा था.
और हम ने कहा कि का समय चल रहा है कि, इसे ले लिया चरणों की संख्या थी
क्या के आदेश पर?
>> स्पीकर 1 [सुनाई]
>> डेविड जे मालन: तो n के आधार 2, लॉग या अभी और अधिक बस, एन के प्रवेश करें.
तो लघुगणक कुछ.
और ग्राफ एक सीधी रेखा में नहीं था कि अभी भी बदतर और बदतर हो गया, यह था
नहीं था कि यह दिलचस्प वक्र समय के साथ इतना बुरा हो.
तो चलो इस विचार पर पकड़.
की जेनिफर धन्यवाद करते हैं.
बहुत बहुत धन्यवाद ऊपर पर आने के लिए.
और, एक सेकंड.
कोई डेस्क आज दीपक, लेकिन हम CS50 तनाव की गेंद है.
>> जेनिफर: याय.
>> डेविड जे मालन: यहां सब ठीक है,.
वसूल करने के लिए धन्यवाद यहाँ तनाव.
ठीक है.
तो अब हम नहीं कर सकते, तो चलो देखते हैं थोड़ा और अधिक इस सजाना.
तो फिर, क्या हम सिर्फ किया था जैसा कि हमने किया अनिवार्य रूप से एक ही बात
कि पहले हफ्ते में.
लेकिन बजाय सिर्फ एक रेखीय के साथ समाप्त हम दर्शाया जो एल्गोरिथ्म,
पहले यह सीधी रेखा के रूप में, जिससे, हम पर एक और दरवाजा डाल
स्क्रीन, तब जेनिफर होगा संभवतः, देखने के लिए पड़ा है,
एक और दरवाजे के पीछे.
हम दो और दरवाजे डाल, तो वह हो सकता है दो और दरवाजों के पीछे देखने के लिए.
>> और हां, इस रैखिक वहां गया था के आकार के बीच संबंध
X-अक्ष, कहते हैं, पर समस्या है, और समय की राशि है कि यह करने के लिए ले जाता है
Y पर हल.
लेकिन मैं की ओर इशारा करते रहा था तस्वीर पहले इस ग्रीन लाइन थी.
ग्रीन जान - बूझकर, क्योंकि यह सिर्फ बेहतर महसूस किया.
सिद्धांत रूप में, हम ऐसा किया था जब एल्गोरिथ्म, हमने कर दिया जब फोन की किताब, के साथ
साथ आप एक दूसरे को भरोसा कर लोग, और दूसरे मामले में, जब जेनिफर बस
यहाँ यह किया था, यह की तरह था की मौलिक बेहतर.
यह सिर्फ दो बार के रूप में तेजी नहीं थी.
यह भी चार बार के रूप में तेजी से नहीं था.
इस पर पूरी तरह से निर्भर था क्या इनपुट के आकार के रूप में था, कितने
कदम यह अंततः लिया.
>> और हम सब ले लिया है, ताकि इस सरल विचार फोन की किताब के साथ प्रदान के लिए,
इसी प्रकार लागू किया जा सकता है इस तरह से कुछ करने के लिए.
और यह अधिक लापरवाही से हो सकता है आप कर सकते हैं, के रूप में जाना
, विभाजन और जीत की कल्पना.
नहीं हम क्या किया विपरीत, ज़ाहिर है, फोन की किताब के साथ.
>> लेकिन pseudocode, याद है, यह था.
तो हम फिर से ऐसा करते हैं, लेकिन याद नहीं होगा कि पहले हफ्ते, हम सब उठ खड़ा हुआ
और फिर आप के आधे आधे से बैठ गए, आप नीचे बैठे थे, आप में से आधे बैठ गए.
एल्गोरिथ्म है कि एक में लागू किया गया था एक धोखा दे रास्ते से बिट, कि में, यह
मुझे गिनती का सिर्फ एक नहीं था, मूलरूप में, और अधिक कुशलता से.
उस मामले में, मैं का लाभ दिया गया था एक माध्यमिक संसाधन.
सॉर्ट की, कई CPUs, कई दिमाग, में कई चालाक लोग
कमरा मुझे कुछ से मिल मदद कर रहे थे कुछ करने के लिए रैखिक
कुछ से, लघुगणक कुछ हरे रंग के लिए लाल.
>> लेकिन इस मामले में, अकेले जेनिफर कर सकते हैं मौलिक पर सुधार
द्वारा अपने पहले एल्गोरिथ्म के प्रदर्शन, फिर, बस थोड़ा कठिन सोच.
और अब, जब इसे लागू करने के लिए समय आता है इन बातों को पता लगाना
आप लिख सकते हैं कोड की क्या लाइनों आप उन्हें फिर से दोहराने, और कर सकते हैं कि
फिर से, और फिर, की तरह एक पाशन फैशन में.
आपके पास करने के लिए नहीं जा रहे हैं क्योंकि जेनिफर की तरह विलासिता, करने के लिए, पहली बार में किया
बस, आईएफएस की एक पूरी गुच्छा है और कहते हैं हम्म, यह पहली संख्या 4 है, तो
मुझे अंत तक सभी तरह कूद करते हैं.
ओह, कि संख्या बहुत बड़ी है, तो मुझे वापस मनमाने ढंग से चलते हैं
दूसरा तत्व है.
आप इसे एक बहुत होने जा रहा है कि मिल जाएगा क्या हम मनुष्यों को औपचारिक रूप से कठिन
बहुत ही उचित रूप में लेने के लिए दी heuristics, लेकिन एक कंप्यूटर ही है
आप यह करना बता क्या क्या करने जा रहा.
>> अब यह बहुत दिलचस्प है निहितार्थ.
यह ग्राफ की तरह की तरह करने के लिए है नेत्रहीन भी हिला, लेकिन नोटिस जहां
इस ग्राफ में सीधी रेखा है?
कहां रेखीय ग्राफ है हम n है कि कॉल?
खैर, यह की तरह नीचे की ओर है इस तस्वीर की, है ना?
तो हम किया है सभी हम की तरह लिया है X-अक्ष और बाहर तेजी से बढ़ी
की भावना लाने के लिए प्रयास करने के लिए Y-अक्ष क्या घटता के अन्य प्रकार की तरह लग रहे.
>> और गणितीय की बारीकियों अभिव्यक्ति आज तो कोई बात नहीं होगी
ज्यादा है, लेकिन का एक बहुत कुछ है कि नोटिस दूर से भी बदतर हैं कि एल्गोरिदम
रैखिक है कि कुछ और.
दरअसल, एन cubed बहुत बुरा लग रहा है.
N करने के लिए 2 बहुत बुरा लग रहा है. n चुकता बहुत बुरा लग रहा है.
और हम देखेंगे उन का क्या कुछ वास्तविकता में आज हो सकता है.
और लॉग एन के रूप में बुरा महसूस नहीं करता है, लेकिन n से बेहतर n के लॉग आधार 2 है.
लेकिन तुम जानते हो, यह हो गया होता भी , अधिक जेनिफर अगर अद्भुत, या हम अगर
कि पहले हफ्ते के साथ आया था n के प्रवेश का प्रवेश है कि कुछ और.
>> तो दूसरे शब्दों में, इस पूरे नहीं है करने के लिए संभव समाधान की सीमा
समस्याओं, लेकिन यहाँ भी, नोटिस क्या होने जा रहा है.
इन घटता की मैं बाहर ज़ूम करते हैं, जो निरपेक्ष साबित हो जा रहा है
अब स्क्रीन पर लोगों का सबसे बुरा?
तो पता cubed सुंदर लग रहा है इस समय बुरा.
लेकिन हम बाहर ज़ूम और अधिक देखते हैं एक्स और वाई अक्ष, जो हो रहा है
अंततः हावी?
तो यह वास्तव में पता चला है कि करने के लिए 2 एन, और आप अभी से यह पता लगा सकते हैं
कुछ तेजी से बड़ी में plugging संख्या, और आप देखेंगे कि 2 को
एन, वास्तव में, बहुत तेजी से बड़ा हो जाता है.
हम वास्तव में बाहर ज़ूम, एक 2 n एल्गोरिथ्म बिल्कुल बेकार है.
मेरा मतलब यह नहीं ले रहा है के लिए समय की बहुत थोड़ी
के माध्यम से मंथन करने के लिए कंप्यूटर.
>> लेकिन आप विशेष रूप से, समय के साथ देखेंगे भविष्य समस्या सेट के साथ और भी
अंतिम परियोजनाओं, आपके डेटा है सेट, सभी अधिकार बड़ा हो जाता है?
यहां तक ​​कि फेसबुक के पहले संस्करण में, मित्रों की संख्या, और के रूप में
पंजीकृत उपयोगकर्ताओं की संख्या, बड़े मिला आप में फोन की तरह कर सकते हैं
रैखिक खोज के साथ कुछ को लागू करने, या एक बहुत ही सरल छँटाई
हम आज देखेंगे एल्गोरिथ्म.
आप कठिन सोचना शुरू किया है और इन समस्याओं के बारे में कठिन.
और समस्याओं के प्रकार जैसे स्थानों फेसबुक, और गूगल और माइक्रोसॉफ्ट,
और दूसरों है पर काम बिल्कुल इन सवालों की तरह के बड़े डेटा के आधार पर क्रमबद्ध
तेजी से इन दिनों.
>> ठीक है.
इसलिए कि दूसरे में जेनिफर की सफलता एल्गोरिथ्म, सच में, वह आश्चर्यजनक किया
अच्छी तरह से पहली बार, लेकिन चलो भाग्य के रूप में यह लिखने के लिए इतना है कि हम
इस बिंदु बना सकते हैं.
दूसरे मामले में, वह leveraged एक फिर से दोहराया और कहा कि एल्गोरिथ्म
फिर, लेकिन वह दी एक के लिए ले लिया हम अनुमति दी है कि निश्चित धारणा
उसे, लेकिन वह कुछ विस्तार शोषण वह नहीं था कि दूसरी बार
पहली बार.
क्या जो था?
>> सूची हल किया गया था.
इसलिए जैसे ही सूची हल किया गया था के रूप में, हम जेनिफर हो पा रहा था कि दावा
मौलिक बेहतर.
7 दरवाजे, हाँ, यह दिलचस्प नहीं है, लेकिन वह हो 7 लाख दरवाजे हम मान लें.
N के प्रवेश निश्चित रूप से जा रहा है बहुत, बहुत प्रदर्शन करने के लिए
लंबे समय में तेजी से.
लेकिन वह है था उसके हल के लिए दरवाजे.
अब, मुझे लगता है कि कर की स्वतंत्रता लिया कंप्यूटर स्क्रीन पर अग्रिम में
यहाँ, लेकिन लगता है कि जेनिफर खुद को ऐसा करने के लिए था?
मान लीजिए कि प्रश्न में दरवाजे प्रतिनिधित्व एक डेटाबेस में डेटा, या
मित्रों फेसबुक के लिए पंजीकृत है, या इंटरनेट पर किसी भी वेब पृष्ठों है कि
विभिन्न वेबसाइटों आवश्यकता हो सकती है सूचकांक में या उस पर खोज करते हैं.
>> आप सिर्फ एक कच्चे डेटा था कि मान लीजिए सेट और यह आप के लिए, या करने के लिए छोड़ दिया गया था
जेनिफर कि छँटाई करने के लिए?
यही है, बल्कि, हम जवाब देने की आवश्यकता है कि सवाल है, ठीक है, कितना समय
, जेनिफर लिया, या यहाँ तक कि मुझे दिया होता अग्रिम में उन लोगों की संख्या के आधार पर सॉर्ट करने के लिए इतना
वह उस का लाभ ले सकता है?
है ना?
निहितार्थ यह है, ज़ाहिर है, क्योंकि यह सॉर्ट करने के लिए मुझे कुछ समय लेता है
हो तुम कि कौन परवाह करता है संख्या, इतनी तेजी से 50 की तरह एक नंबर मिल सकता है,
जेनिफर के मामले के रूप में, अगर हम अधिक से अधिक कुल समय की राशि अभिभूत
यह पहले से बातें छँटाई द्वारा लिया?
>> तो हम नहीं कर सकते, तो चलो देखते हैं यहाँ तस्वीर रंग.
मैं एक पूरी गुच्छा अधिक तनाव है गेंदों, कि अगर मदद मिलती है
यहां बर्फ तोड़ने.
और तुम बुरा नहीं होता, तो हम सात स्वयंसेवक की जरूरत है -
ठीक है, पर.
वाह.
इसलिए हम खर्च करने की जरूरत नहीं है टेबल लैंप पर, ऐसा लगता है.
ठीक है.
तो आप कैसे सामने दो के बारे में.
तुम कैसे वापस में दो लोगों के बारे में.
इसलिए कि चार है.
कैसे आप के बारे में सामने पांच, छह और सात.
वहीं पर.
आपके मित्र का तुम बाहर ओर इशारा करते हुए, तो आप पुरस्कार मिलेगा.
>> ठीक है.
ऊपर आओ.
और यही कारण है कि हम आप के लिए नहीं है लोग यहाँ पर आते हैं.
मैं तुम्हें हर एक नंबर देने के लिए जा रहा हूँ.
और आगे जाना है और अपने आप को व्यवस्था हूबहू क्या है
स्क्रीन पर दिखाया गया.
>> [INTERPOSING आवाज़ें]
>> डेविड जे मालन: Oop, माफ करना.
बग.
ठीक है.
ठीक है, यहाँ हम चले.
पांच नंबर.
छठे नंबर.
एक, दो, तीन, चार, पांच, छह, सात.
ओह, यह अजीब है.
>> अध्यक्ष 2: मैं सिर्फ एक मिल जाएगा -.
>> डेविड जे मालन: अच्छा सौदा है.
ठीक है.
भाग लेने के लिए धन्यवाद.
>> [वाहवाही]
>> ठीक है.
ठीक है.
तो हमारे पास चार, दो, छह, एक, तीन, सात, पांच.
बिल्कुल सही है तो हम सात स्वयंसेवकों यहां तक ​​चौड़ाई में बराबर हैं, जो
हम खेल रहे हैं कि सरणी पहले साथ.
और मैं कारणों के लिए सात चुना कि बस हो जाएगा
एक छोटा सा में सुविधाजनक.
और मैं पहली बार है कि प्रस्ताव करने जा रहा हूँ हम इन सात स्वयंसेवकों को सॉर्ट.
यदि आप चाहें तो, सबसे पहले, हालांकि नमस्ते कहने के लिए.
यह एक होने जा रहा है के बाद से अजीब कई मिनट.
अपने आप को परिचय.
>> अनुग्रह: हाय, मैं अनुग्रह हूँ.
मैं Leverett हाउस में एक sophomore हूँ.
>> ब्रैनसन: हाय.
मैं ब्रैनसन हूँ.
मैं वेल्ड में एक नए हूँ.
>> Gabe: हाय.
मैं Gabe कर रहा हूँ.
मैं Cabot में एक जूनियर हूँ.
>> नील: मैं नील हूँ.
मैं मैथ्यू में एक नए हूँ.
>> जेसन: मैं जेसन हूँ.
मैं Greenough में एक नए हूँ.
>> माइक: मैं माइक हूँ.
मैं Grays में एक नए हूँ.
>> जेस: मैं जेस हूँ.
मैं Leverett में एक sophomore हूँ.
>> डेविड जे मालन: उत्कृष्ट.
ठीक है.
खैर, हमारे सब के लिए धन्यवाद इस प्रकार अब तक यहां स्वयंसेवकों.
और अब हाथ में चुनौती रहा है फिर इन लोगों की तरह करने के लिए किया है, लेकिन करने के लिए
हम एक छोटे से सोचने के लिए किया जा रहे हैं कैसे कुशलतापूर्वक हम वास्तव में मुश्किल के बारे में
उन्हें हल किया.
तो चलिए पहले यह कोशिश करते हैं.
तुम लोग एक दूसरे की संख्या देख सकते हैं बस चारों कोनों रखकर.
आगे बढ़ो और कुछ ही सेकंड ले, और पर छोटी से अपने आप को सॉर्ट
सही पर सबसे बड़ा करने के लिए छोड़ दिया है.
जाओ.
>> ठीक है.
अच्छा.
यह वास्तव में रफ़ू तेज थी.
अब यहाँ कोई, कलन विधि क्या था इन लोगों को लागू किया है?
>> स्पीकर 1: सबसे बड़ा करने के लिए कम से कम.
>> डेविड जे मालन: ठीक है.
कम से कम सबसे बड़ा करने के लिए वास्तव में एक तरह से है उद्देश्य है, लेकिन मुझे लगता है कि यकीन नहीं कर रहा हूँ
वास्तव में एक एल्गोरिथ्म.
कम से कम नहीं बताता है सबसे बड़ा करने के लिए मुझे कदम दर कदम क्या करना है.
हाँ?
>> स्पीकर 1 [सुनाई]
>> डेविड जे मालन: ठीक है.
तो आप से एक व्यक्ति छोटे देखते हैं आपका नंबर है, तो करने के लिए कदम
उनमें से सही.
तो, अब है कि अधिक अर्थपूर्ण हो रही है अधिक एक एल्गोरिथ्म की तरह, तुम क्योंकि
, इस, तो कह सकते हैं कि.
तो हम किसी तरह का है सशर्त निर्माण.
और इन लोगों को ऐसा लग रहा था कि कुछ कई बार, आप में से कुछ एक सा ले जाया गया क्योंकि
एक दूरी से.
इसलिए किसी तरह का संभवतः वहां गया था पाशन उनके दिमाग में चल रहा है.
>> लेकिन चलो कि औपचारिक रूप देने की कोशिश करते हैं.
तुम लोगों को वापस रीसेट कर सकता है इस व्यवस्था के लिए.
हम इस एक शकल नहीं कर सकते, तो चलो देखते हैं बिट, और फिर बस, सवाल पूछना
यह कैसे कुशल है?
बेशक, हम और अधिक धीरे धीरे इस करते हैं, यह के रूप में अच्छा महसूस हो रहा है
एक एल्गोरिथ्म, लेकिन हम कर सकते हैं, तो चलो देखते हैं सटीक कदम पर हमारे उंगलियों डाल दिया.
>> तो अगर आप दो लोगों को चार और दो हैं.
या फिर आप को सही या गलत आदेश?
जाहिर है गलत.
इसलिए हम बदली.
अब मैं एक तरफ स्थानांतरित करने के लिए जा रहा हूँ यहाँ और कहते हैं 05:56.
आप सही है या गलत कर रहे हैं?
>> Gabe: सही है.
>> डेविड जे मालन: सही है.
छह और एक?
नहींं.
स्वैप.
तो यह है कि दो स्वैप है.
छह और तीन?
नहींं.
स्वैप.
छह और सात?
अच्छा लग रहा है.
सात और पांच?
>> जेस: [सुनाई]
>> डेविड जे मालन: ठीक है, स्वैप.
और हल.
ठीक है.
तो जाहिर है, सही नहीं है?
इसलिए अधिक चल रहा था.
लेकिन, वास्तव में, इन लोगों को भी बस सहज.
घूमता रहा.
वे सिर्फ बंद नहीं किया था एक बार वे एक समस्या को सही.
तो.
दरअसल, मैं जा रहा हूँ एक ही बात करने के लिए.
मैं एक तरह से वापस उल्टा करने के लिए किया जा रहा हूँ इस समस्या की शुरुआत करने के लिए,
या के इस सरणी की शुरुआत लोग, उन्हें बुला शुरू करते हैं.
>> और अब क्या करना चाहिए मेरे एल्गोरिथ्म दूसरा पास पर हो?
>> स्पीकर 1: एक ही बात.
>> डेविड जे मालन: एक ही बात.
और यह, मैं सही, पसंद करने के लिए शुरू कर रहा हूँ?
जैसे ही आप अपने आप कर मिल सकता है एक ही बात बार बार, कि
अधिक, एक एल्गोरिथ्म की तरह होता जा रहा है और कम मानव वृत्ति.
>> तो अब, यहाँ हम फिर जाओ.
दो और चार?
नहीं.
चार और एक?
आह, कुछ वास्तव में वहां गया था कुछ किया जाना अभी भी काम करते हैं.
के लिए और तीन?
अच्छा.
चार और छह?
छह और पाँच?
छह और सात?
ठीक है, अब, किया.
ठीक है, नहीं.
मैं वापस जाने के लिए है.
>> तो अब, फिर से, हम यह कर रहे हैं एक छोटे से अधिक जान - बूझकर.
और अब, सिर्फ एक मस्तिष्क वहाँ इस कलन विधि को क्रियान्वित.
एक सीपीयू, अगर तुम जाएगा.
और सच में, कि केवल संसाधन है हम करने के लिए उपयोग करने के लिए जा रहे हैं.
और हम एक कुंजीपटल करने के लिए वापस जाना है एक बार और हमारे पर सी की तरह कुछ है
निपटान, हम केवल एक प्रोग्राम लिख रहे हैं कि एक समय में एक ही काम कर सकते हैं.
एक पल पहले इन लोगों को, जबकि हम उनके सामूहिक brainpower leveraged
जैसे तुम लोग सप्ताह शून्य में किया था.
तो चलो यह कर रखते हैं.
>> दो और एक.
दो और तीन.
तीन और चार.
चार और पांच.
पांच और छह.
छह और सात.
हो गया?
तो मैं कर रहा हूँ, लेकिन मुझे खेलते हैं शैतान के अधिवक्ता.
मैं, कंप्यूटर की तरह है जो सिर्फ इस श्रृंखला के माध्यम से एक पास बनाया
लोग, मैं कर रहा हूँ पता है?
>> स्पीकर 1: नहीं
>> डेविड जे मालन: तो क्यों?
के क्रम में मुझे क्या करना होगा निर्णायक मैं कर रहा हूँ कि निष्कर्ष है?
शायद एक और पास.
है ना?
क्योंकि मुझे लगता है कि पिछले से सभी जानते है पास मैं एक गलती को सही करता है.
और इसका मतलब है, शायद वहाँ अभी भी एक और गलती
मैं सही करने की जरूरत है.
इसलिए मैं केवल rewinding द्वारा सुनिश्चित किया जा सकता है, और फिर दो, दो, एक जाँच और
तीन, तीन और चार, चार और पांच, पांच और छह, छह और सात.
ठीक है, अब मैं कोई काम नहीं किया.
>> मैं निश्चित रूप से मैं नहीं किया था कि याद कर सकते हैं एक चर की तरह कुछ के साथ काम करते हैं,
एक पूर्णांक की तरह.
स्वैप को बुलाओ, और स्वैप 0 है, तो एक बार मैं यहां मिलता है, और यह तो ठीक है, 0 पर शुरू कर दिया
मैं बस जा रहा रखने के लिए पागल हो जाएगा आगे पीछे, फिर जाँच, और
फिर से, और फिर, सही?
आप कुछ में अटक जाते हैं क्योंकि अनंत लूप की तरह.
इसलिए जैसे ही 0 स्वैप वहाँ के रूप में, हम दावा कर सकते हैं कि इस
एल्गोरिथ्म वास्तव में पूरा हो गया है.
>> अब, हम इस पर एक नाम डाल दिया.
मैं बस हम प्रस्ताव है कि एल्गोरिथ्म है कार्यान्वित बुलबुला बुलाया कुछ
सॉर्ट, अर्थ में इस तरह के रूप में जाना जाता है कि बड़ा प्रकार के हैं कि संख्या
बुलबुला उनके शीर्ष करने के लिए जिस तरह से ऊपर, या संख्याओं की सरणी के अंत करने के लिए.
लेकिन इस एल्गोरिथ्म कैसे कुशल था?
मैं शारीरिक रूप से करने के लिए कितने कदम था इन प्रकार के लिए, उदाहरण के लिए, ले
सात मनुष्यों?
>> चार से पांच?
ठीक है, बहुत सारे अंततः है जवाब होने जा रहा.
लेकिन फिर भी, विशिष्ट संख्या इतना रोचक नहीं है.
के एन के रूप में यह सामान्यीकरण करते हैं.
मैं यहाँ n लोग ऊपर था, और यदि ऐसा है तो वे एक तरह से, कम से यादृच्छिक क्रम में थे,
कि मूल आदेश में, शुरुआत.
खैर, कितने कदम मेरे पास था पहले पारित पर लेने के लिए?
यह एक, दो, तीन, चार, पाँच था छह, और वे सात लोगों को है, इसलिए कर रहे हैं
कि n है तो, - कि सात, छह है शून्य से एक पहली बार कदम.
>> अब, कितने कदम मेरे पास था मैं rewound जब लेने के लिए?
ठीक है, हम वास्तव में दोहरा सकता है कि अगर हम वास्तव में चाहते थे, लेकिन अब के लिए, मैं कर रहा हूँ
सिर्फ कहने के लिए जा रहा है, ठीक है, एक और एन शून्य से 1.
तो एन शून्य से 1 प्राप्त करने के लिए जा रहा है कष्टप्रद का ट्रैक रखने, तो ऐसा करने के
बस थोड़ा दौर.
तो 2N कदम.
तो 14 कदम, दे या ले.
>> मैं कितनी बार ले गए थे एक अगली बार कदम?
खैर, यह 3n है.
वास्तव में.
और अब, सबसे खराब स्थिति में, के लिए उदाहरण के लिए, कितनी बार मैं होता
आगे पीछे, आगे पीछे चला गया है, गमागमन, इस कलन विधि को क्रियान्वित
प्रत्येक पर लोगों को मोटे तौर पर, पास?
यह वास्तव में पता है, सही चुकता है?
>> सबसे खराब स्थिति में, आप की तरह कर सकते हैं क्योंकि की, intuitively इस बारे में सोचते हैं
यह एक छोटा सा लग सकता है, भले ही अंदर सिंक करने के लिए समय का एक सा
सबसे खराब स्थिति में, क्या होगा इन सात लोगों में, की तरह देखा है
व्यवस्था की शर्तें उनकी संख्या का?
पूरी तरह से पीछे की ओर, सही?
और सिर्फ इतना है कि अनुकरण करने के लिए, आपका नाम फिर क्या था?
>> माइक: माइक.
>> डेविड जे मालन: माइक?
ठीक है, माइक, तुम सिर्फ मुझ पर शामिल हो सकते हैं यहां सिर्फ एक दूसरे के लिए?
दरअसल, नहीं.
क्षमा माइक, का उल्टा करते हैं.
आपका नाम फिर क्या है?
>> नील: नील.
>> डेविड जे मालन: नील.
ठीक है, नील, आप के साथ आते हैं मुझे, तुम बुरा नहीं है.
तो मैं बस के लिए, प्रस्ताव करने जा रहा हूँ नील में अब है कि सादगी, उसकी
सबसे ज्यादा संभव मामले.
लेकिन मैं कार्यान्वित कैसे याद मेरे एल्गोरिथ्म.
मैं तुलना, तुलना, तुलना कर रहा हूँ, , की तुलना की तुलना, ओह.
अब इन लोगों को बाहर कर रहे हैं आदेश की, तो मैं तय कर लो.
तो तुम लोग स्वैप.
लेकिन अब विचार करना है, कितना आगे नील जाने के लिए है?
यह मोटे तौर पर पता है.
तुम्हें पता है, यह वास्तव में पता नहीं है.
यह तरह एन शून्य से 1 है, लेकिन मैं कर रहा हूँ छोटे से नाराज रखते हुए ट्रैक
संख्या है, तो हम सिर्फ n कहते हैं.
>> तो नील ज़्यादा से ज़्यादा हर एक कदम चलता है अगर समय, और नील एक कदम स्थानांतरित करने के लिए,
मैं यह वास्तव में कठिन पारित करने के लिए है आगे पीछे, यह मोटे तौर पर है
यह कर, एन कदम, एन बार की कुल, यह मुझे ले जा रहा है क्योंकि
कि सभी नील पाने के लिए कई कदम वह कहाँ के लिए रास्ता.
अकेले जाने बाकी सब अगर तुम लोग सभी के रूप में अच्छी तरह से गलत आदेश दिए थे.
>> तो चलो चुकता सॉर्ट n बुलबुला कहते हैं.
इस एल्गोरिथ्म के समय चल रहा है, इस एल्गोरिथ्म के प्रदर्शन,
इस एल्गोरिथ्म की दक्षता, हम सिर्फ अधिक का वर्णन होगा
आम तौर पर के रूप में n चुकता.
मैं क्या कर सकता है, क्योंकि जो अच्छा है आठ लोग, नौ के साथ एक ही उदाहरण
लोगों को, एक लाख लोगों को, और उस जवाब बदलने नहीं जा रहा है.
>> तुम लोगों को बुरा नहीं होता तो, अगर चलो तुम कहाँ शुरू करने के लिए आप रीसेट.
और दो अन्य तरीकों की कोशिश करते हैं और हम मौलिक नहीं कर सकते हैं देखें
इस से भी बेहतर.
तो इस बार, मैं प्रस्ताव करने के लिए जा रहा हूँ अलग एल्गोरिथ्म का एक तरह से.
आखिरी बार है कि हम में से बहुत चालाक था, और तुम लोग सही थे
बस की तरह सही प्रवृत्ति जोड़ो गमागमन.
लेकिन मैं वास्तव में इस दृष्टिकोण के लिए चाहता था बस, और अपने लक्ष्य को स्थानांतरित करने के लिए है
छोटी संख्या को इस तरह के सभी, और बड़ी संख्या के सभी धक्का
जिस तरह से, मैं अभी क्यों नहीं करते कि में सबसे अनुभवहीन संभव तरीके से और देखो अगर मैं
एक क्या था की तुलना में बेहतर कर सकते हैं काफी जटिल एल्गोरिथ्म?
>> तो चलो देखते हैं.
चार एक बहुत छोटी संख्या है, तो मैं कर रहा हूँ तुम वहाँ पल छोड़ने के लिए जा रहा है.
ओह, नंबर दो और भी बेहतर है.
तो तुम सिर्फ आगे कदम कर सकते हैं एक पल के लिए?
यह वर्तमान में मेरे सबसे छोटी गिने है उम्मीदवार, और मैं याद करने के लिए जा रहा हूँ
कि एक चर, जैसे, के साथ.
लेकिन मैं जाँच रखने के लिए जा रहा हूँ.
जिसका कोई है संख्या छोटी है?
छह, नहीं.
ओह, फिर नील नहीं है.
>> तो मैं तुम्हें वापस पुश करने के लिए जा रहा हूँ तरह की धारणा.
नील को आगे आना होगा.
और अब, मैं करने के लिए उपयोग कर रहा हूँ कि चर छोटी से छोटी है जो का ट्रैक रखने के
संख्या को रोकने के लिए अद्यतन किया जाता है नील का स्थान.
खैर, चलो देखते हैं.
तीन, सात, पांच.
ठीक है, मैं जानता हूँ कि नील सबसे छोटा था.
सरल बात क्या है मुझे अब क्या करना है?
मैं बस से अपना समय बर्बाद करने के लिए नहीं जा रहा हूँ बाईं ओर नील एक स्थान बुदबुदाती.
क्यों मैं सिर्फ नील डाल नहीं है जहां वह जहां पाठ्यक्रम की है, जो अंतर्गत आता है?
>> शुरुआत में सभी तरह.
तो नील, मेरे साथ आओ.
और अपना नाम फिर क्या था?
>> अनुग्रह: अनुग्रह.
>> डेविड जे मालन: अनुग्रह.
ठीक है.
तो ग्रेस, दुर्भाग्य से, आप कर रहे हैं तरह के रास्ते में.
तो कैसे हम इस समस्या को हल करने के लिए?
है ना?
यह एक सरणी है, तो वहाँ केवल सात स्थानों.
रॉब के साथ, याद है कि, हम के बारे में बात की थी उम्र घोषित करने, और हम केवल था एक
उम्र के परिमित संख्या?
यहां एक ही विचार है.
हम केवल ints की एक निश्चित संख्या है.
ग्रेस में एक तरह से है हमारे जिस तरह से है, तो हम कैसे तय करते हैं?
>> सबसे सरल तरीका है, की तरह है ग्रेस, माफ करना.
आप पर जाने के लिए करने जा रहे हैं इसलिए हम जगह नहीं कर सकते हैं.
अब, आप हो सकता है, इस बारे में सोचते हैं हम सिर्फ समस्या बदतर बना दिया.
और शायद हम, क्या किया, क्योंकि अगर अनुग्रह सही जगह में थे?
लेकिन हम वह नहीं है क्योंकि मुझे पता है अन्यथा, वह हो गया होता
आगे खड़े बजाय इस समय नील, है ना?
हम पहले से ही उसकी संख्या की जाँच की.
>> ठीक है.
तो अब, नील सही जगह में, और मैं एक मामूली अनुकूलन कर सकते हैं.
अगले मिनट के लिए, मैं अनदेखा करने के लिए जा रहा हूँ एक साथ नील सब, नहीं तो के रूप में
गलती से उसका समय बर्बाद, या गलत जगह पर उसे स्वैप.
तो अब, कैसे मैं अगले पता करूँ छोटी से छोटी है कि तत्व?
दो.
यही है, अगर एक बहुत अच्छा नंबर आप आगे कदम करना चाहते हैं और
मैं आपको याद होगा.
छह, अच्छा नहीं.
चार, तीन, सात, पांच, अच्छा नहीं.
इसलिए मेरे लिए तुम चलो अपने सही जगह है.
और हम सिर्फ भाग्यशाली इस बार मिला है.
>> अब, मैं इन पर ध्यान न दें करने के लिए जा रहा हूँ अब दो लोग, और एक अधिक करना
इस के माध्यम से गुजरती हैं.
छह, एक बहुत छोटी संख्या है.
आगे चलो.
ओह, माफ करना.
अनुग्रह की संख्या बेहतर है, इतना आगे पर कदम.
चार.
क्षमा करें, अनुग्रह.
फिर वापस जाओ.
तीन नंबर बेहतर है.
सात.
पांच.
और अब अपना नाम फिर क्या है?
>> जेसन: जेसन.
>> डेविड जे मालन: जेसन.
तो जेसन अब छोटी से छोटी है तत्व मैं का चयन किया है.
वह कहाँ जा रहा है?
तो छह है.
और अपना नाम फिर से है?
>> Gabe: Gabe.
>> डेविड जे मालन: Gabe.
Gabe रास्ते में है.
आसान बात क्या है?
इन दो लोगों को स्वैप और जारी है.
तो अब चलो देखते हैं.
कौन सबसे छोटी है?
चार.
मुझे बस की तरह धोखा करते हैं.
पांच सबसे छोटी होने जा रहा है.
आप कदम चाहते हैं, अगर मैं अगले पाते आगे, क्या मैं के साथ क्या करना है
Gabe के साथ इन लोगों को?
फिर स्वैप.
तो अब, अभी भी थोड़ा आदेश से बाहर.
मैं तो, Gabe छोटी से छोटी हो पाया मैं उसे बाहर पॉप से ​​अधिक तुम लोग ले जाते हैं.
और हो गया.
>> तो जवाब एक ही है.
अंतिम परिणाम एक ही है.
इन दो एल्गोरिदम का कौन सा बेहतर है?
दूसरा एक, मैंने सुना.
क्यों?
>> स्पीकर 3: यह [सुनाई] n कदम है.
>> डेविड जे मालन: यह सबसे कम n कदम है.
दिलचस्प है.
तो यह यद्यपि है?
तो मैं कैसे पता चला छोटी तत्व?
कितने कदम मैं लेने के लिए किया है छोटी तत्व को खोजने?
मैं एक बार देख सभी तरह था अंत में, सही?
वजह यह है कि सबसे खराब स्थिति में, क्या नील यहाँ पर थे?
तो सिर्फ छोटी तत्व खोजने या एन शून्य से 1, मुझे पता कदम उठा लेता है.
लेकिन, ठीक है.
तो नील को ठीक.
कि, तो पहले एक मिनट या याद रखें.
>> लेकिन कैसे मैं अगले मिला छोटी तत्व?
यह वास्तव में एन शून्य से 1, या एन शून्य से 2 है चरणों की संख्या से.
तो ठीक है.
तो मैंने किया था एन शून्य से 2.
ठीक है.
तो यह है कि एक छोटे से बेहतर लगता है.
ठीक है.
कितने कदम अगली बार तीन नंबर खोजने के लिए?
तो एन शून्य से 4.
तो यह एक कम, कम है प्रत्येक यात्रा पर कदम.
तो यह ठीक है, बेहतर लग रहा है?
पिछली बार तो यह मोटे तौर पर एन बार पता था इस समय यह n शून्य से 1 है, प्लस n घटा
2, प्लस n शून्य से 3, प्लस n शून्य से 4, डॉट, दूरसंचार विभाग, दूरसंचार विभाग.
लेकिन अगर आप अपने उच्च विद्यालय से याद करते हैं पाठ्यपुस्तकों, थोड़ा धोखा
फ़ार्मुलों है कि पीठ पर चादर, अगर आप संख्या की इस श्रृंखला के लिए जोड़,
चरणों की कुल संख्या क्या है मैं यहाँ ले कि होने जा रहा?
>> यह उन में से एक, जैसे, एन शून्य से है 2 से विभाजित 1, टाइम्स एन,.
तो मैं खींच सकते हैं देखें बस एक पल के लिए यह ऊपर.
और फिर, मैं एक तरह से कुछ गोलाई हूँ सिर्फ साधारण हमारे जीवन रखने के लिए संख्या है,
मुझे याद है लेकिन, यह अगर ऐसा कुछ है मैं 1 बातें करते n घटा, फिर n घटा
2, फिर n शून्य से 3, यह मोटे तौर पर है 2 से अधिक कुछ इस तरह है, और अगर मैं
इस बाहर गुणा, कि वास्तव में एन स्क्वायर.
वह भी अच्छा महसूस नहीं है. n माइनस 2 n से अधिक.
>> लेकिन यहाँ बात है.
कंप्यूटर विज्ञान, समस्याओं जब में जब n है दिलचस्प मिल शुरू
वास्तव में बड़ा हो जाता है.
और एन, जिनमें से वास्तव में बड़ा हो जाता है जब इन मूल्यों को सब पर हावी हो रहा है
दूसरों का?
यह सही है, की तरह n चुकता है?
हाँ, 2 से विभाजित बहुत अच्छा है.
लेकिन आप अरबों के बारे में बात कर रहे हैं डेटा के टुकड़े, या अरबों की की
डेटा के टुकड़े, ठीक है, तो आप दो बार के रूप में तेजी से कर रहे हैं.
लेकिन जो वास्तव में है कि बड़ी संख्या परवाह करता है अगर इस पहलू क्या हो जाता है अगर
बड़ा और बड़ा.
और निश्चित रूप से, यह बनाता है के अधिक इस आदमी की तुलना में एक फर्क है.
तुम लोग सही हैं तो फिर भी, दूसरी एल्गोरिथ्म, हम यह फोन करता हूँ
चयन के आधार पर क्रमबद्ध, असली दुनिया में, एक मैं कर रहा हूँ, क्योंकि तेजी से संभावित काटा
लेने के लिए कम और कम हर बार दोहराएँ.
>> यह वास्तव में मौलिक रूप से तेजी से नहीं है.
क्योंकि हम वास्तव में इस के लिए बाहर खेलने अगर अंत में एन के बड़े मान,
दिन, बड़ा पर्याप्त n के लिए, यह अभी भी है बहुत धीमी गति से महसूस करने के लिए जा रहा है.
खैर, मुझे एक ले जाने उस पर पिछले पास.
यही तो मैं क्या कहेंगे है चयन के आधार पर क्रमबद्ध.
तुम लोग अपने आप को रीसेट कर सकते हैं एक आखिरी बार?
और यह पिछले मामले में, मैं जा रहा हूँ कुछ प्रस्ताव करने के लिए
सम्मिलन सॉर्ट बुलाया.
निवेशन प्रकार किया जा रहा, धारणा, थोड़ा अलग.
>> बल्कि आगे और पीछे जाने से और छोटी तत्व का चयन, मैं हूँ
सिर्फ इनमें से प्रत्येक के साथ सौदा करने के लिए जा रहा मैं उन्हें मुठभेड़, और सम्मिलित रूप लड़के
उनकी सही जगह में उन्हें.
तो मैं बस, ग्रेस के साथ शुरू करने जा रहा हूँ और मुझे लगता है वह संख्या चार है कि देखते हैं.
चार नंबर कहां का है?
मैं कुछ भी छँटाई शुरू नहीं किया है, इतना अनुग्रह सही वहाँ रहने के लिए हो जाता है.
अगर तुम सकता है और अब मैं दावा करने के लिए जा रहा हूँ अपने सही, इस के लिए एक कदम उठाना
मेरे क्रमबद्ध सूची, यह मेरा है unsorted शेष सूची.
तो अब मैं, आगे आगे बढ़ने के लिए जा रहा हूँ और अपना नाम फिर क्या है?
>> ब्रैनसन: ब्रैनसन.
>> डेविड जे मालन: ब्रैनसन.
तो ब्रैनसन संख्या दो है.
तो मैं तुम्हें लेने के लिए जा रहा हूँ एक पल के लिए बाहर.
और अब, आप जहां संबंधित है इस सरणी में?
ग्रेस के अधिकार के लिए तो.
तो फिर, हम एक तरह से कर रहे हैं अनुग्रह यहां बहुत काम करते हैं.
हम आपको कहां रखा है?
तो हम करने के लिए आप स्लाइड करने के लिए जा रहे हैं छोड़ दिया है, और वहाँ ब्रैनसन डालें.
लेकिन अब मैं दावा है कि तुम लोग कर रहे हैं.
लेकिन सूचना, मैं अतिरिक्त स्थान का उपयोग नहीं कर रहा हूँ.
यह अभी भी 2 तत्व है यहाँ, 5 यहाँ पर.
कुल सरणी आकार 7 है, तो मैं कर रहा हूँ सभी अधिकार धोखा नहीं?
>> तो अब हम यहाँ Gabe के साथ है, नंबर छह, तुम कहाँ हो?
आप फिर से भाग्यशाली है.
तो तुम सही वहाँ रहने के लिए मिलता है.
बस सही करने के लिए एक मामूली कदम उठाने बस आप हल कर रहे हैं कि स्पष्ट करने के लिए.
और अब हम फिर से नंबर नील है एक, जहां आप जाते हो?
हम देखते हैं कि शुरू करेंगे जहां और अब है इस एल्गोरिथ्म, यद्यपि पर पहले
नज़र, बहुत चालाक लगता है, देखो होने वाला है क्या.
आप आगे कदम सकता है.
>> हम नील डाल दिया, जहां चाहते हैं?
तो जाहिर है, यहाँ तो कैसे हम वहाँ नील मिलता है?
के इस कदम दर कदम करते हैं.
Gabe, तुम जाने के लिए जहां जरूरत है?
हां, तो एक बड़ा कदम उठाने, बनाने के लिए या दो आधे कदम
वहाँ पर एक कदम है.
तुम कहाँ जाना ग्रेस,?
अच्छा.
तो एक और कदम.
और अंत में, ब्रैनसन?
एक और कदम.
और अब हम जगह में नील डाल सकता है.
>> तो अब, इस तर्क जारी है.
हम नील स्थानांतरण नहीं कर रहे हैं, भले ही से अधिक, और अधिक, और अधिक, उसे डाल करने के लिए
वह सबसे खराब स्थिति में, कहाँ जाता है, हम मुठभेड़ हो सकता है अगले संख्या सका
संख्या, कहते हैं, एक नंबर वहाँ था होना शून्य, तो हम सभी को शिफ्ट करने के लिए जा रहे हैं
इन लोगों को.
नकारात्मक एक संख्या है, कि मान लीजिए एक है, तो हम बदलाव किया है
इन लोगों का सब.
इसलिए हम वास्तव में बस की तरह flipping रहे हैं चारों ओर समस्या है, हम कर रहे हैं कि इस तरह के
से खर्च स्थानांतरित चयन प्रक्रिया इतनी प्रविष्टि
तुम लोग सिर्फ था कि इस तरह की प्रक्रिया, मोटे तौर पर एन शून्य से कुछ को स्थानांतरित करने के लिए
चरणों की संख्या.
और कदम की कि संख्या ही जा रहा है मैं अधिक संख्या को चुनने के रूप में वृद्धि,
मैं तुम लोगों को मार रखने के लिए है अगर वापस, और वापस, और वापस.
>> तो दुखद बात अब इन सभी का है एल्गोरिदम n चुकता कर रहे हैं.
चलो आगे चलते हैं और इन करने के लिए धन्यवाद दोस्तों, और ये एक बिट कल्पना
अलग ढंग से.
बहुत अच्छी तरह से किया.
>> [वाहवाही]
>> ठीक है.
वहाँ तुम जाओ.
के लिए धन्यवाद -
>> ब्रैनसन [सुनाई] संख्या में रहते हैं.
>> डेविड जे मालन: नहीं, आप कर सकते हैं साथ ही नंबर रखने.
ठीक है.
अच्छी तरह से किया.
ठीक है.
तो क्या अब हम संक्षेप में प्रस्तुत नहीं कर सकते, तो चलो देखते हैं और अधिक तेजी से, और अधिक नेत्रहीन,
बस वास्तव में क्या हुआ यहाँ के रूप में इस प्रकार है.
मैं आगे जाने के लिए जा रहा हूँ और Firefox अपने आप को रोकना.
हम इस प्रदर्शन को लिंक करना होगा पाठ्यक्रम की वेबसाइट पर.
जावा काम कर पाने के लिए एक सा गुस्सा आ रहा है कुछ ब्राउज़रों में इन दिनों.
तो तुम घर पर इस के साथ खेलते हैं, तो यदि आप Firefox का उपयोग करने की आवश्यकता हो सकती एहसास
यह काम करने के लिए.
और क्या मैं इस के साथ क्या करने जा रहा हूँ प्रदर्शन के बाद है.
>> तल में, मैं एक पूरी गुच्छा की है एक शुरुआत है और एक सहित मेनू विकल्पों,
बटन बंद करो.
इसके अलावा, एक अलग रूप में, एक नहीं हो रहा है इन कार्यक्रमों में बग, जिससे आप
वास्तव में शुरू देखना या नहीं रोक सकता आप पकड़ बटन जब तक आदेश या ऑल्ट
प्लस और में ज़ूम, जो मजे की बात है आप अधिक बटन दिखाता है.
तो बस FYI आप खेलते हैं इस घर में साथ.
अब मैं प्रारंभ क्लिक करने के लिए जा रहा हूँ, बस एक पल, की देरी निर्दिष्ट करने के बाद,
जैसे, 200 मिसे यहाँ, बस इसलिए हम देखते हैं क्या होता कर सकते हैं.
>> इसलिए मैं इस एक दृश्य है कि दावा पहले एल्गोरिथ्म के
इन लोगों को किया था, बुलबुला तरह, जिससे हम जोड़ी के लिहाज से लोगों बदली.
इस दृश्य के लिए महत्वपूर्ण जानकारी है कि सलाखों के ऊंचाई
संख्या के आकार का प्रतिनिधित्व करता है.
तो लम्बे बार, बड़ी संख्या.
छोटा बार, छोटी संख्या.
अगर तुम नोटिस और, हम के माध्यम से जा रहे हैं इस एल्गोरिथ्म की पहली यात्रा,
बड़े और छोटे संख्या गमागमन, इतना है कि छोटी संख्या पहले आता है और
बड़ी संख्या सही करने के लिए चला जाता है.
>> और जैसे ही हम सरणी के अंत के रूप में सात तुलना में बहुत अधिक संख्या में, हम कर रहे हैं
शुरुआत में वापस जाने के लिए जा रहा है.
और यह आशा.
अब तक छोड़ दिया पर, कि छोटे आदमी चल रहा है ओर करने के लिए स्वैप, और यह करने के लिए
प्रक्रिया को दोहराता है.
अब इस दृश्य को जल्दी हो जाता है बोरिंग, तो मुझे आगे जाना है और बंद करो
यह बहुत देरी कुछ परिवर्तन तेजी से बस, अब के लिए एक महसूस पाने के लिए
इस एल्गोरिथ्म.
>> इसलिए मैं इसे ऊपर निकल गया है, भले ही यह है खरीदने, अपने प्रोसेसर उन्नयन की तरह
एक नए कंप्यूटर.
मैं मौलिक नहीं बदला है मेरी एल्गोरिथ्म, लेकिन आप वास्तव में अधिक देख सकते हैं
स्पष्ट रूप से मनुष्यों के साथ तुलना में, कि बड़े संख्या ऊपर तक बुदबुदाती हैं,
और कम संख्या बुदबुदाती रहे हैं नीचे करने के लिए नीचे.
और अब यहाँ इस बात को हल.
और एक अलग रूप में, चौराहों में, वहाँ वहाँ सिर्फ कुछ बहीखाता के लिए
आप कितने तुलना गिनती मदद, या कितने स्वैप है
वास्तव में किया गया.
>> ठीक है, चलो की एक कोशिश करते हैं दूसरों हमने देखा.
मुझे सॉर्ट यहां बुलबुला पर क्लिक करते हैं, और इस पूरे वेब पेज मुझे चुनने दें, और
एक छोटी सी छोटी गाड़ी है.
के जोखिम को स्वीकार करते हैं और फिर इसे चलाते हैं.
हम वहाँ जाते हैं.
तो चलो चयन के आधार पर क्रमबद्ध करते हैं.
मैं क्यों मेनू में पता नहीं है वहाँ पर दिखाई देता है.
आइए उसे ठीक करने में ज़ूम बग, 50 के लिए यह परिवर्तन.
आह, वास्तव में करते हैं कि बहुत तेजी से.
पांच मिसे या तो है, और शुरू.
>> तो इस चयन के आधार पर क्रमबद्ध है.
तो फिर, क्या हम के बारे में सोचना यहाँ मनुष्यों के साथ किया था.
हम सरणी के माध्यम से चला गया और चयनित फिर छोटी तत्व,
और फिर, और फिर से.
अब मुझे लगता है कि अभी भी बहुत बुरा था दावा करते हैं.
यह अभी भी था पता दे या ले, चुकता लेकिन यह एक सा है, असली दुनिया में, था
मैं वास्तव में ले जा रहा था, क्योंकि तेजी थोड़ा कम कदम हर बार.
लेकिन हम केवल क्या बात कर रहे हैं?
यहाँ शायद 40 या तो सलाखों?
हम 40 लाख में बात नहीं कर रहे हैं.
इसलिए मेरे लिए पूरी तरह से स्पष्ट नहीं है कि वास्तव में एक महत्वपूर्ण लाभ था.
>> मुझे अब वापस जाने के लिए बदल लेते हैं हमारे का चयन किया गया था जिसमें तीसरी एल्गोरिथ्म,
सम्मिलन तरह.
और अब यह वास्तव में छोटी गाड़ी है क्योंकि मेनू वास्तव में नीचे नहीं होना चाहिए.
तो अब हम यहाँ वापस स्क्रॉल करेंगे और इस एल्गोरिथ्म शुरू करते हैं.
ललकार, शुरू और बंद.
तो यह एक तरह का एक सुंदर स्वरूप है हम फिर से कर रहे हैं यह करने के लिए, जिससे
मनुष्य डालने, या में इस मामले में सलाखों
उनके उचित स्थान.
और यह पहले से ही से पहले किया जाता है मैं घूमा.
लेकिन यह एक है, भी, सिद्धांत में, अभी भी पता चुकता है.
>> इसलिए हम संक्षेप में प्रस्तुत नहीं कर सकते, तो चलो देखते हैं इन प्रकार के रूप में.
मैं आगे जाने के लिए जा रहा हूँ और बस देने के लिए बात कर के हमें की तरह एक आम तरीका
इन चीजों के बारे में, मुझे परिचय यहाँ अंकन के बस थोड़ा सा.
तुम बड़े बुलाया कुछ देख रहे हैं के बारे यह सचमुच एक बड़ा है हे, क्योंकि
ओ और यह एक तरह से है कि एक कंप्यूटर वैज्ञानिक या एक गणितज्ञ भी उपयोग करता है
समय चल रहा है वर्णन करने के लिए कुछ एल्गोरिथ्म की.
कितने कदम यह वास्तव में ले करता है?
>> अब मैं के साथ अपने आप को नीचा दिखाने के लिए जा रहा हूँ यहां सिर्फ एक पल में मेरी लिखावट.
लेकिन मुझे आगे जाना है और कहते हैं कि इस यहाँ पर बड़ी हे हो जाएगा.
और मुझे अन्य एक परिचय प्रतीक, एक राजधानी ओमेगा.
ओमेगा विपरीत होने जा रहा है, अनिवार्य रूप से, बड़ा ओ की जबकि बड़ी हे
इसका मतलब है, सबसे खराब स्थिति में, कितना समय कुछ एल्गोरिथ्म में, लग सकता है
n के मामले, ओमेगा जा रहा है कितना समय यह हो सकता है
सबसे अच्छी स्थिति में ले.
और हम से क्या मतलब देखेंगे बस एक पल में सबसे अच्छा मामले.
>> तो चलो कुछ सरल शुरू करते हैं.
मुझे एक रेखीय खोज के साथ शुरू करते हैं.
तो छँटाई नहीं.
हम इस रैखिक खोज फोन करता हूँ.
और अब, एक छोटे से बना इस से बाहर मेज.
और अब, रैखिक खोज के मामले में, सबसे खराब स्थिति में, कितने कदम है
इसे खोजने के लिए मुझे लेने के लिए जा रहा एक मनमाने ढंग से चुनाव की संख्या?
और कुल दरवाजे वहाँ n है या N कुल संख्या.
सबसे बुरी स्थिति.
कितने कदम मैं करने के लिए जा रहा हूँ एक सरणी में संख्या 50 मिल लेना
n दरवाजे की?
और क्यों?
यह सब हो सकता है क्योंकि रास्ते पर अंत पर.
जेनिफर का सामना करना पड़ा इतना पसंद, संख्या 50 सभी तरह से खत्म हो गया था, इसलिए में
सबसे खराब स्थिति रैखिक खोज n की बड़ी हे है, हम कह देंगे.
>> सबसे अच्छा मामले के बारे में क्या, क्या तुम सच में भाग्यशाली हो तो क्या होगा?
यह सिर्फ एक कदम ले जा रहा है, या कदम की एक निरंतर संख्या.
तो हम 1 के रूप में उस का वर्णन करेंगे.
तो यह बहुत अच्छा है.
हम कुछ किया अब क्या अगर द्विआधारी खोज की तरह?
तो द्विआधारी खोज, सबसे खराब में मामला है, कितना समय लगा?
>> [INTERPOSING आवाज़ें]
>> डेविड जे मालन: तो वास्तव में, मैं एक जोड़े स्थानों में यह सुना.
तो यह वास्तव में, लॉग एन देना या लेना है क्योंकि हम छमाही में सूची में विभाजित के रूप में
फिर से, और फिर, और फिर, हम सक्षम हैं लगता है, अंत में, मूल्य,
यह वहाँ है, लेकिन वहाँ एक पकड़ है.
हम करने के लिए है कि इस धारणा क्या है द्विआधारी खोज के लिए दी ले?
इसे हल किया जाना है.
इसे हल नहीं है, आप बात को विभाजित कर सकते हैं छमाही में फिर से और फिर से, और आप
बाईं जा सकते हैं, और आप सही जा सकते हैं, और आप छोड़ दिया और सही जा सकते हैं, लेकिन आप कर रहे हैं
तत्व को खोजने के लिए नहीं जा रहा है अगर सूची, हल नहीं है क्योंकि
आप यह याद कर सकते हैं.
क्योंकि छोड़ा जाने के लिए अपने अनुमानी, या सही यह है कि अगर त्रुटिपूर्ण होने जा रहा है
वास्तव में हल नहीं.
तो एक तरह से एक छिपा हुआ शुल्क नहीं है इस तरह से कुछ का उपयोग करने के लिए.
>> अब, हमारे छँटाई में जाने एल्गोरिदम खोज नहीं -
ओह, वास्तव में यह रिक्त में चलते हैं.
सबसे अच्छा मामले में द्विआधारी खोज?
यह सिर्फ होना होता है अगर यह भी 1 है सरणी, या के बहुत बीच में
फोन की किताब के बीच.
अब चलो बुलबुला तरह करते हैं.
तो फिर, अब हम प्रवेश कर रहे हैं प्रकार, नहीं खोज करता है.
>> सबसे खराब स्थिति में, कितने कदम हमने किया दावा बुलबुला तरह ले जा रहा है?
n चुकता.
इसलिए मुझे लगता है कि आकर्षित करने के लिए जा रहा हूँ.
ओह, मेरी लिखावट भी बुरा लग रहा है यह है कि बड़े अनुमान है जब.
ठीक है.
इसलिए कि n चुकता है.
और बुलबुला तरह का सबसे अच्छा मामले में, कितने कदम इसे ले जा रहा है?
1, मैंने सुना.
>> स्पीकर 1: एन.
>> डेविड जे मालन: एन, मैंने सुना.
>> स्पीकर 1: 2.
>> डेविड जे मालन: 2, मैंने सुना.
मैं 3 सुन रहे हो?
ठीक है.
तो मैं 1 के बारे में सुना, एन, 2, लेकिन नियमित छोड़ दिया अलग कम से कम उन लोगों की पहले
सुझाव, 1.
यह एक बुरा वृत्ति नहीं है यह क्योंकि एक तरह से यहां एक पैटर्न प्रकार है.
लेकिन यह केवल 1 कदम, कैसे में लेता है दुनिया मैं दावा कर सकती है कि सूची
, हल है मैं केवल अनुमति हूँ क्योंकि अगर 1 कदम उठाने के लिए, कितने तत्वों
मैं वास्तव में यह सुनिश्चित करने की जाँच कर सकता है?
खैर, अभी 1, जिसका अर्थ है वहाँ n है से बाहर हो सकता है कि शून्य से 1 तत्वों
आदेश, और मैं बस के बाद विश्वास पर जा रहा हूँ 1 तत्व को देख कि
बात सॉर्ट किया जाता है.
तो 1 के यहां सही नहीं.
तो न्यूनतम, कितने मैं देखने के लिए क्या करना है?
>> [INTERPOSING आवाज़ें]
>> डेविड जे मालन: एन शून्य से 1, या वास्तव में, N, मैं हर देखने की जरूरत है क्योंकि
यह सुनिश्चित करने के तत्व यह आदेश से बाहर नहीं है.
लेकिन फिर, हम की तरह लहर करेंगे हमारी छोटे संख्या में हाथों और
n बड़े हो जाता है, वे कर रहे हैं, मानते हैं कि वैसे भी रसहीन.
इसलिए कि बुलबुला तरह है.
और अब, इन पिछले दो करते हैं.
चयन छंटाई, और फिर हम हूँ सम्मिलन तरह करते हैं.
और फिर हम उड़ा देगा आपकी बहुत कुछ के साथ मन
इन सभी की तुलना में बेहतर है.
ठीक है.
>> चल सबसे खराब स्थिति क्या है चयन की तरह समय?
>> अध्यक्ष 4: R चुकता.
>> डेविड जे मालन: N वर्ग, मैं सुन रहा हूँ.
लेकिन क्यों एन intuitively, चुकता?
>> अध्यक्ष 4: हम सिर्फ यह किया है.
>> डेविड जे मालन: हम सिर्फ यह किया है.
ठीक है.
अच्छा जवाब.
लेकिन intuitively, क्यों चयन है सॉर्ट n चुकता?
हम क्या करने की ज़रूरत थी बार - बार?
हम कर रहे हैं, के माध्यम से स्कैनिंग रखने के लिए किया था आप छोटी से छोटी है, तो आप कर रहे हैं
छोटी से छोटी है, तो आप छोटी से छोटी हैं.
और दी, हम n ले पा रहे थे कदम है, तो एन शून्य से 1, फिर n शून्य से 2.
लेकिन आप की तरह उन सभी को जोड़ने के लिए, या मैं जोड़ दिया है कि आस्था पर ले
उन्हें अग्रिम में, हम मोटे तौर पर पता मिल कुछ छोटी संख्या शून्य से चुकता.
इसलिए मैं चुकता इस n कॉल करने के लिए जा रहा हूँ.
लेकिन सबसे अच्छा में चयन के आधार पर क्रमबद्ध साथ मामला है, यह कितने कदम है
मुझे लेने के लिए जा रहे हैं?
>> स्पीकर 5 [सुनाई]
>> डेविड जे मालन: यह दुर्भाग्य है अभी भी पता है, सही चुकता?
क्योंकि मैं सबसे छोटी चयन कर रहा हूँ अगर तत्व, और हम यहां सात लोगों की थी
मैं बहुत करने के लिए एक बार मैं ही जानता हूँ, मैं सबसे छोटी पाया है कि अंत,
संख्या, जहाँ भी वह या वह हो सकता है.
लेकिन कैसे मैं अगले पता करूँ सबसे छोटी संख्या?
मैं एक और पारित करना होगा.
तो सबसे अच्छा मामले में, क्या है चयन के आधार पर क्रमबद्ध करने के लिए निवेश?
यह एक पहले से ही सॉर्ट सूची, नंबर एक है नंबर दो, तीन नंबर, चार नंबर.
लेकिन मैं एक कंप्यूटर हूँ.
मैं केवल एक पर देख सकते हैं एक बार में बात.
मैं एक तरह से एक कदम नहीं ले सकते वापस, एक मानव की तरह हैं और कहते हैं
ओह, यह सही लगता है.
>> मैं केवल में शुद्धता निर्णय कर सकते हैं चयन करके चयन के आधार पर क्रमबद्ध
सबसे छोटी संख्या.
लेकिन जब मैं पहली बार नंबर एक मिल जाए, मैं के बारे में सब कुछ पता नहीं है अगर
मैं नहीं, सब मुझे क्या करना है, जो दूसरे नंबर, मैं एक सरणी सौंप दिया गया है कि पता
या दरवाजे का एक सेट है, जो पीछे हैं संख्या, मुझे लगता है कि किसी को पता ही रास्ता
सबसे छोटा था?
मैं सभी तरह से यहाँ मिलता है और एहसास है, अरे नहीं, एक वास्तव में सबसे छोटा था.
>> लेकिन कैसे मैं फिर तय करते हैं कि दो छोटी अगले है?
एक ही अक्षमता ऐसा करके बार - बार.
तो अंत में, प्रविष्टि प्रकार के साथ, कैसे, सबसे खराब स्थिति में,
हम यह प्रदर्शन कहा?
यह भी पता चुकता है.
और कैसे सबसे अच्छा मामले के साथ के बारे में?
हम एक cliffhanger के रूप में छोड़ दूँगा.
हम चाहते हैं कि रिक्त अगली बार में भर देंगे, लेकिन पहली बार मुझे लगता है कि हम प्रस्ताव करते हैं
मूलरूप से बेहतर कर इन सब, ठीक है?
>> तो अपने आप के लिए क्या लगता है कि प्रविष्टि सॉर्ट होने जा रहा है.
खैर, कि, बहुत नाटकीय नहीं था मैं केवल एक हूँ क्योंकि
कि परिवर्तन देखा.
वाह.
ठीक है.
तो यहाँ हम एक हद तक है अलग प्रदर्शन.
मैं यहाँ में ज़ूम, तो आप उस पर देखेंगे हम में, बुलबुला तरह छोड़ दिया
मध्य हम पर चयन प्रकार का है, और अभी तक ठीक है, हम कुछ है हम
अभी तक देखा नहीं है मर्ज सॉर्ट बुलाया.
लेकिन हम किया गया है क्या विचार आज इस प्रकार अब तक यहाँ क्या कर रहा.
जेनिफर पहले चरण पर आया था, जब हम नंबर की सरणी के माध्यम से चला गया
फिर से, और फिर, रैखिक खोज के साथ, और हम रैखिक समय चल रहा है, बड़ी हे मिला
के एन, तो बात करो.
>> अब हम पहले सप्ताह की जब विचार वर्ग, हम विभाजन और जीत थी,
और हम, फोन बुक फाड़ था और जेनिफर, और हम सामूहिक रूप
leveraged कि करने के लिए किया गया था जिसमें महत्वपूर्ण जानकारी, द्वारा बार - बार अपने आप को दोहराने
किसी भी तरह, दूर फेंक, दूर फेंक दूर फेंक, समस्या का आधा, या
आम तौर पर, आधे में एक समस्या का विभाजन और फिर छोटे टुकड़े का इलाज
धारणात्मक समकक्ष के रूप में समस्या अन्य के लिए, हम किसी भी तरह से किया था
मौलिक बेहतर.
लेकिन चयन के साथ बुलबुला तरह, के साथ सॉर्ट, प्रविष्टि प्रकार के साथ, हम है हो सकता है
जेनिफर किया था कि ऐसी कोई अंतर्दृष्टि.
हम बहुत ज्यादा सिर्फ वापस चला गया और आगे एक पूरी टाइम्स का गुच्छा, और हम
गमागमन, चीजें एक छोटा सा tweaked इस क्रम में, हो सकता है
डालने या चयन.
लेकिन दिन के अंत में, मैं एक बहुत कुछ किया अजीब आगे पीछे चल रहा है.
हम वास्तव में कुछ लाभ उठाने नहीं था जेनिफर की तरह स्मार्ट विभाजित पसंद नहीं आया
और जीतने.
>> तो इसके विपरीत, की तरह विलय, जो हम अगले सप्ताह तक नहीं देखेंगे, यह हो रहा है
विभाजित करके कि मुख्य विचार का लाभ उठाने के लिए इनपुट, और उसके बाद तो संयोग है, और
संयोग, और फिर संयोग.
और कहा कि पाश के प्रत्येक चलना पर, बाईं आधा, और सही छँटाई
आधा, फिर बाईं आधे के बाईं आधा, और बाईं के ठीक आधे, तो
छोड़ा ठीक आधे का आधा है, और ठीक आधे के ठीक आधे.
और बार - बार दोहरा.
>> तो आप नेत्रहीन यह देखते हैं, लेकिन यह करूँगा अगले हफ्ते हमें इंतजार कर रहा है.
और सामान्य में, हमें लगता है कि जब एक छोटे से ऐसे किसी भी समस्या पर कठिन सा.
हम n बाईं तरफ चुकता, n है बीच में चुकता, और n
सही पर लॉग एन.
तो अपने असली cliffhanger नहीं है.
हम सोमवार को आप देखेंगे.
>> [वाहवाही]