>> [संगीत खेल]
डेविड मालन: सब ठीक है.
ठीक है, वापस स्वागत करते हैं.
तो इस सप्ताह 4, शुरुआत है क्या है, पहले से ही.
और तुम पिछले हफ्ते, हम डाल दिया कि याद करेंगे बस एक छोटा सा के लिए अलग कोड
और हम एक छोटे से अधिक बातें करने लगे जैसी चीजों के बारे में उच्च स्तर,
खोज और छँटाई जो यद्यपि कुछ हद तक सरल विचार कर रहे हैं
समस्याओं का एक वर्ग के प्रतिनिधि आप विशेष रूप से हल करने के लिए शुरू हो जाएगा
आप अंतिम के बारे में सोचना शुरू कर के रूप में परियोजनाओं और दिलचस्प समाधान आप
असली दुनिया की समस्याओं के लिए हो सकता है.
अब बुलबुला तरह सरलतम में से एक था ऐसे एल्गोरिदम, और यह
इन कम संख्या होने से काम किया एक सूची में या किसी सरणी प्रकार के में
बुलबुला उनके शीर्ष करने के लिए जिस तरह से ऊपर है, और बड़ी संख्या को नीचे अपने तरीके से स्थानांतरित
उस सूची के अंत.
>> और हम कल्पना कर सकता है कि याद बुलबुला तरह एक छोटे से
कुछ इस तरह.
तो मुझे आगे जाना है और प्रारंभ क्लिक करते हैं.
मैं बुलबुला तरह चुने हुए लिया है.
और यदि आपको याद है कि लम्बे नीला लाइनों छोटे, बड़े संख्या का प्रतिनिधित्व
नीली लाइनों के रूप में, कम संख्या का प्रतिनिधित्व करते हैं हम बार - बार यह माध्यम से जाओ और
फिर, प्रत्येक के लिए अगले दो बार की तुलना लाल रंग में अन्य, हम स्वैप करने के लिए जा रहे हैं
सबसे बड़ी और अगर छोटी से छोटी वे आदेश से बाहर हैं.
>> तो इस पर जाना होगा और पर जाना है और जाना पर, और आप देखेंगे कि बड़ा
तत्वों को अपनी राह बना रहे हैं सही है, और छोटे तत्व हैं
बाईं ओर अपनी राह बना.
लेकिन हम यों के लिए शुरू किया दक्षता,
इस एल्गोरिथ्म की गुणवत्ता.
और जैसा कि हमने कहा है कि सबसे खराब में मामला है, इस एल्गोरिथ्म ले लिया
मोटे तौर पर कितने कदम?
>> तो पता चुकता.
और एन क्या था?
>> दर्शक: तत्वों की संख्या.
>> डेविड मालन: तो पता था तत्वों की संख्या.
और इसलिए हम अक्सर यह करूँगा.
हम आकार के बारे में बात करना चाहते हैं किसी भी समय एक समस्या है या एक के आकार का
इनपुट, या यह लगता है की राशि उत्पादन का उत्पादन करने के लिए, हम सिर्फ हूँ
सामान्यीकृत जो कुछ भी इनपुट एन के रूप में है.
तो वापस वीक 0 में, संख्या पन्ने फोन बुक में पता था.
छात्रों की संख्या कमरे में एन था.
तो यहां भी, हम पालन कर रहे हैं उस पैटर्न.
>> अब पता चुकता विशेष रूप से नहीं है तेजी से, तो हम बेहतर करने की कोशिश की.
और इसलिए हम एक जोड़े की तरफ देखा अन्य एल्गोरिदम, जो बीच में
चयन के आधार पर क्रमबद्ध थे.
इसलिए चयन के आधार पर क्रमबद्ध किया गया था थोड़ा अलग.
यह लगभग आसान था, मैं कहता हूँ की हिम्मत, मैं के शुरू में शुरू कर दिया जिससे
हमारे स्वयंसेवकों की सूची और बस फिर मैं और बार - बार के माध्यम से चला गया
सूची छोटी बाहर तोड़ एक समय पर तत्व और उसे डालने या
सूची की शुरुआत में उसे.
>> लेकिन यह भी, एक बार हम सोचना शुरू कर दिया गणित के माध्यम से और बड़ा
तस्वीर के बारे में सोचा कितनी बार मैं वापस आगे और पीछे जा रहा था
और आगे, हम सबसे ज्यादा मामले में कहा, चयन के आधार पर क्रमबद्ध, भी, क्या था?
n चुकता.
अब असली दुनिया में, यह हो सकता है वास्तव में मामूली तेजी से हो.
फिर, क्योंकि मैं रखने के लिए नहीं था मैं क्रमबद्ध किया था एक बार पीछे हट
छोटी से छोटी तत्वों.
लेकिन हम बहुत बड़ी n के बारे में सोचते हैं, और अगर आप की तरह गणित के रूप में बाहर करते हैं
मैं चुकता एन के साथ, बोर्ड पर किया था शून्य से कुछ है, बाकी सब कुछ
n चुकता इसके अलावा, एक बार n , वास्तव में बड़ा नहीं मिलते
सच के रूप में ज्यादा फर्क.
तो कंप्यूटर वैज्ञानिकों के रूप में, हम की तरह छोटे के लिए एक अंधे आँख बारी
कारकों और केवल कारक में पर फोकस बनाने जा रहा है कि एक अभिव्यक्ति
सबसे बड़ा अंतर है.
>> खैर, अंत में, हम देखा प्रविष्टि के आधार पर क्रमबद्ध पर.
और इस भावना में समान था, लेकिन iteratively के माध्यम से जाने के लिए और के बजाय
एक में सबसे छोटा तत्व किसी एक का चयन समय, मैं बजाय हाथ लिया कि मैं
सभी, निपटा, और मैंने तय कर लिया गया था ठीक है, तुम यहाँ के.
तो मैं अगले तत्व पर चले गए और फैसला किया कि वह या
वह यहाँ था.
और फिर मैं पर और पर ले जाया गया.
और मुझे लगता है, जिस तरह से साथ, करने के लिए हो सकता है के क्रम में इन लोगों बदलाव
उनके लिए जगह बनाने.
इसलिए कि मानसिक पलटने की तरह था चयन की तरह है कि हम
सम्मिलन सॉर्ट बुलाया.
>> इसलिए इन विषयों के लिए होते हैं असली दुनिया में.
बस कुछ साल पहले, जब एक निश्चित सीनेटर, राष्ट्रपति के लिए चल रहा था
समय पर सीईओ एरिक श्मिट, गूगल, वास्तव में अवसर मिला
उसे साक्षात्कार के लिए.
और हम हम इस यूट्यूब हिस्सा था हम बारी सकता है, यहाँ आप के लिए क्लिप
मात्रा.
>> [वीडियो प्लेबैक]
>> अब, सीनेटर, आप यहाँ गूगल पर रहे और मैं राष्ट्रपति पद के बारे में सोचना पसंद
एक नौकरी के साक्षात्कार के रूप में.
>> [हंसी]
>> अब इसे पाने के लिए मुश्किल है अध्यक्ष के रूप में एक काम है.
और आप के माध्यम से जा रहे हैं अब कठोरता.
यह गूगल पर एक नौकरी पाने के लिए भी मुश्किल है.
हम प्रश्न हैं और हम पूछना हमारे उम्मीदवारों सवाल.
और यह एक लैरी श्विमर से है.
>> [हंसी]
तुम लोगों को मैं मजाक कर रहा हूँ?
यह ठीक है यहाँ है.
सबसे कारगर तरीका क्या है एक लाख दो बिट पूर्णांक प्रकार?
>> [हंसी]
>> खैर, उह -
>> -मैं माफी चाहता हूँ.
शायद हम चाहिए -
>> नहीं, नहीं, नहीं, नहीं, नहीं.
>> कि एक नहीं है -
ठीक है.
>> मैं बुलबुला तरह होता लगता है गलत रास्ता तय करना हो.
>> [हंसी]
>> [जयकार और तालियां]
>> जो इस उससे कहा, पर हो रहा है?
ठीक है.
>> [अंत वीडियो प्लेबैक]
>> डेविड मालन: तो वहाँ तुम्हारे पास है.
इसलिए हम इन चल यों के लिए शुरू किया कई बार, तो कुछ के साथ बात करने के लिए
जो कहा जाता उपगामी संकेतन, बस मोड़ के बारे में हमारी तरह करने के लिए चर्चा करते हुए
एक अंधा उन छोटे कारकों के लिए आंख और केवल समय चल रहा है पर देख रहे हैं,
इन एल्गोरिदम का प्रदर्शन, n समय के साथ वास्तव में बड़ा हो जाता है.
और इसलिए हम बड़ा ओ और बड़ी हे पेश हमने सोचा कि कुछ प्रतिनिधित्व
की एक ऊपरी ही रूप में.
और वास्तव में, बैरी, हम कम कर सकते हैं mic से एक छोटा सा?
>> हम इस एक ऊपरी बाध्य है के बारे में सोचा.
N की तो बड़ी हे चुकता मतलब है कि में सबसे खराब स्थिति, जैसे कुछ
चयन के आधार पर क्रमबद्ध ले जाएगा n कदम चुकता.
या सम्मिलन प्रकार की तरह कुछ n कदम चुकता करेंगे.
अब प्रविष्टि की तरह कुछ के लिए सॉर्ट, सबसे खराब स्थिति क्या थी?
एक सरणी को देखते हुए, सबसे बुरा क्या है आपको मिल सकता है कि संभव परिदृश्य
खुद के साथ सामना करना पड़ा?
>> यह ठीक है, पूरी तरह से पीछे की ओर है?
क्योंकि यह पूरी तरह से पीछे की ओर, अगर आप काम की एक पूरी बहुत कुछ करना है.
क्योंकि आप पूरी तरह से पीछे की ओर कर रहे हैं, आप खोजने के लिए जा रहे हैं
यहां सबसे बड़ा तत्व है, भले ही यह वहाँ नीचे के अंतर्गत आता है.
तो आप पर, सभी सही कहने जा रहे हैं समय में इस समय, तुम यहाँ के,
तो आप उसे अकेला छोड़ दें.
>> तो फिर तुम ओह, अरे नहीं, मैं करने के लिए है, एहसास इस थोड़ा छोटा तत्व के लिए कदम
तुम छोड़ दिया.
तब मैं फिर से ऐसा करने के लिए है और फिर और फिर.
और मैं आपको आगे और पीछे चला गया की तरह का प्रदर्शन कैसा महसूस होगा
कि एल्गोरिथ्म, क्योंकि लगातार मैं हूँ में नीचे हर किसी फेरबदल
इसके लिए जगह बनाने के लिए सरणी.
तो यह है कि सबसे खराब स्थिति है.
>> इसके विपरीत करके -
और यह आखिरी बार एक cliffhanger था -
हमने कहा कि सम्मिलन सॉर्ट क्या से एक ओमेगा था?
सर्वश्रेष्ठ मामले चल रहे हैं क्या है प्रविष्टि की तरह समय?
तो यह n वास्तव में है.
यही कारण है कि हम छोड़ दिया कि रिक्त था पिछली बार बोर्ड पर.
>> क्योंकि और यही कारण है कि यह n के ओमेगा है?
खैर, बहुत अच्छा मामले में, क्या हो रहा है सम्मिलन सॉर्ट सौंप दिया जा रहा है?
खैर, पूरी तरह से हल है कि एक सूची ऐसा करने के लिए पहले से ही कम से कम काम करते हैं.
लेकिन क्या प्रविष्टि प्रकार के बारे में साफ है है कि यह यहाँ शुरू होता है और क्योंकि
, ओह, आप संख्या हैं फैसला एक, तुम यहाँ के.
ओह, एक अच्छा भाग्य क्या.
>> आप संख्या दो हो.
तुम भी यहाँ के.
तीन नंबर, और भी बेहतर, तुम यहाँ के.
जैसे ही यह के अंत तक हो जाता है सूची, प्रविष्टि प्रति के आधार पर क्रमबद्ध pseudocode है
हम मौखिक रूप से के माध्यम से चला गया है कि पिछली बार यह हो चुका है.
लेकिन चयन के आधार पर क्रमबद्ध, इसके विपरीत, क्या कर रखा है?
>> सूची के माध्यम से रखा जा रहा है फिर और फिर और फिर.
महत्वपूर्ण जानकारी ही नहीं थी क्योंकि आप सभी तरह से करने के लिए देखा है एक बार
सूची के अंत आप कुछ कर सकते हैं आप चयनित तत्व था कि
वास्तव में वर्तमान में सबसे छोटा तत्व.
इसलिए इन विभिन्न मानसिक मॉडल अंत ऊपर कुछ बहुत ही वास्तविक दुनिया से बेदखल
हमारे लिए मतभेद है, साथ ही इन सैद्धांतिक उपगामी मतभेद.
>> तो बस, फिर, एन की बड़ी हे संक्षिप्त करने के लिए चुकता, हम कुछ इस तरह देखा है
एल्गोरिदम इस प्रकार अब तक.
N की बड़ी हे?
सकता है कि एक एल्गोरिथ्म क्या है n की बड़ी हे होने के लिए कहा जा सकता है?
सबसे खराब स्थिति में, इसे लेता है कदम की एक रेखीय संख्या.
>> ठीक है, रैखिक खोज.
और सबसे खराब स्थिति में, जहां है आप देख रहे हैं तत्व जब
रैखिक खोज को लागू करने?
>> ठीक है, सबसे खराब स्थिति में, यह भी वहाँ नहीं है.
या दूसरा सबसे खराब स्थिति में, यह है अंत में सभी तरह, जो है
प्लस या माइनस एक एक कदम फर्क.
, दिन के अंत में तो हम यह रेखीय कह सकते हैं.
N की बड़ी हे, रैखिक खोज होगा क्योंकि सबसे खराब स्थिति में,
तत्व भी वहाँ नहीं है या यह है अंत में सभी तरह.
>> खैर, एन के प्रवेश की बड़ी हे.
हम इस बारे में बहुत विस्तार से बात नहीं की यही नहीं, लेकिन हम पहले यह देखा है.
क्या लघुगणक तथाकथित में रन सबसे खराब स्थिति में समय,?
>> हाँ, तो द्विआधारी खोज.
और सबसे खराब स्थिति में द्विआधारी खोज कहीं तत्व हो सकता है
कहीं मध्यम, या सरणी के अंदर.
आप लेकिन एक बार आप केवल यह लगता है में, आधे में सूची में विभाजित
आधा आधा में, आधे में.
और फिर देखा, तो वह वहाँ है.
या फिर, सबसे ज्यादा मामले, यह भी वहाँ नहीं है.
लेकिन आप यह नहीं है कि पता नहीं है आप की तरह है कि पिछले पहुँचने तक
संयोग से नीचे सबसे तत्वों और संयोग और संयोग.
>> 1 की बड़ी हे.
इसलिए हम 2 की बड़ी हे, 3 की बड़ी हे सका.
किसी भी समय आप सिर्फ एक निरंतर संख्या चाहते हैं, हम बस की तरह बस को आसान बनाने में
1 के रूप में है कि बड़ी हे.
हालांकि वास्तविक हैं, तो यह लेता है 2 या यहां तक ​​कि 100 कदम, यह एक है अगर
कदम की लगातार संख्या, हम सिर्फ 1 की बड़ी हे कहते हैं.
है कि एक एल्गोरिथ्म क्या है 1 की बड़ी हे में?
>> दर्शक: लंबाई ढूँढना एक चर की.
>> डेविड मालन: ढूँढना एक चर की लंबाई?
>> दर्शक: नहीं, लंबाई यह पहले से ही हल है, तो.
>> डेविड मालन: अच्छा.
ठीक है, तो कुछ की लंबाई को खोजने अगर ऐसा कुछ, की लंबाई
एक सरणी, कुछ चर में संग्रहीत किया जाता है.
आप बस चर पढ़ सकते हैं क्योंकि, या चर मुद्रित, या
सिर्फ आम तौर पर कि चर का उपयोग.
और देखा, कि लगातार समय लगता है.
>> इसके विपरीत, पीठ खरोंच के लिए लगता है.
वापस सी के पहले सप्ताह के लिए सोचो बुला सिर्फ printf और मुद्रण
स्क्रीन पर कुछ यकीनन है लगातार समय, यह सिर्फ लेता है क्योंकि
दिखाने के लिए CPU चक्र की कुछ संख्या स्क्रीन पर उस पाठ.
या इंतज़ार - करता है यह?
कैसे हम मॉडल हो सकता है printf के प्रदर्शन?
किसी असहमत करना चाहेंगे कि हो सकता है यह वास्तव में निरंतर समय नहीं है?
क्या अर्थ हो सकता है printf के चलाने में समय, पर वास्तव में एक स्ट्रिंग मुद्रण
स्क्रीन, कुछ हो निरंतर के अलावा अन्य.
>> दर्शक: [सुनाई].
>> डेविड मालन: हाँ.
तो यह हमारे दृष्टिकोण पर निर्भर करता है.
हम वास्तव में करने के लिए निवेश के बारे में सोच printf स्ट्रिंग जा रहा है, और के रूप में
इसलिए हम उस के आकार के उपाय इसकी लंबाई द्वारा इनपुट - तो चलो कहते हैं
कि लंबाई n के रूप में अच्छी तरह से -
यकीनन, printf n की बड़ी हे ही है यह आप n कदम उठाने जा रहा है क्योंकि
उन n के प्रत्येक बाहर मुद्रित करने के लिए वर्ण, सबसे अधिक संभावना है.
कम से कम हम मान लें कि सीमा तक हो सकता है कि यह एक पाश के लिए इस्तेमाल कर रहा है
हुड के नीचे.
>> लेकिन हम उस पर विचार करना होगा बेहतर यह समझने के लिए कोड.
और वास्तव में, एक बार तुम लोग शुरू अपनी खुद की एल्गोरिदम का विश्लेषण, आप हूँ
सचमुच कि बस.
सॉर्ट के अपने कोड नेत्रगोलक और लगता है के बारे में - ठीक है, मैं इस लूप है
यहाँ या मैं यहाँ एक नेस्टेड छोरों है कि एन हालात एन बार करने जा रहा है,
और आप की तरह अपना रास्ता कारण कर सकते हैं यह कोड के माध्यम से, भले ही
pseudocode और वास्तविक नहीं कोड.
>> तो क्या पता की ओमेगा चुकता के बारे में?
एक एल्गोरिथ्म क्या था कि सबसे अच्छा में मामले, अभी भी कदम चुकता पता लगा?
हाँ?
>> दर्शक: [सुनाई].
>> डेविड मालन: तो चयन के आधार पर क्रमबद्ध.
क्योंकि वास्तव में कम है कि समस्या में फिर से, मैं नहीं जानता कि इस तथ्य को
मैं जब तक वर्तमान के सबसे छोटे पाया है मैं सभी रफ़ू तत्वों की जाँच की है.
तो ओमेगा का, कहना, एन हम सिर्फ एक के साथ आया था.
सम्मिलन सॉर्ट.
सूची हल होना होता है पहले से ही सबसे अच्छा मामले में हम अभी है
इसके माध्यम से एक पास बनाने के लिए, हम सुनिश्चित कर रहे हैं पर जो बात.
और फिर कहा जा सकता है सुनिश्चित करने के लिए, रेखीय हो.
>> क्या 1 के ओमेगा के बारे में?
सबसे अच्छा मामले में, लग सकता है क्या, कदम की एक निरंतर संख्या?
तो रैखिक खोज, तुम सिर्फ भाग्यशाली हो अगर और आप देख रहे हैं तत्व
, सही सूची की शुरुआत में है आप शुरू कर रहे हैं कि जहां अगर आपके
उस सूची के रैखिक चंक्रमण.
>> और यह एक का सच है बातें की संख्या.
उदाहरण के लिए, यहां तक ​​कि बाइनरी खोज 1 की ओमेगा है.
आप वास्तव में रफ़ू मिलता तो क्या वजह लकी और के बीच में एक प्रकार का जहाज़ थपका
अपने सरणी संख्या है आप के लिए देख रहे हैं?
तो आप के रूप में अच्छी तरह से, वहाँ भाग्यशाली हो सकता है.
>> यह एक, अन्त में, लॉग एन एन की ओमेगा.
इसलिए n लॉग एन, हम वास्तव में नहीं था अभी तक के बारे में बात करते हैं, लेकिन -
>> दर्शक: सॉर्ट मर्ज?
>> डेविड मालन: सॉर्ट मर्ज.
आखिरी बार है कि के cliffhanger था, जहां हम प्रस्तावित है, और हम पता चला
नेत्रहीन, एल्गोरिदम है कि वहाँ.
और मर्ज की तरह सिर्फ एक ऐसी मूलरूप में तेजी से होता है कि एल्गोरिथ्म
इन अन्य लोगों की तुलना में कुछ.
वास्तव में, कम मर्ज में ही नहीं है सबसे अच्छा मामले n सबसे खराब में, लॉग एन
मामले लॉग एन एन.
और आप का यह संयोग है जब ओमेगा और बड़ी हे एक ही बात की जा रही है?
हम वास्तव में क्या है कि के रूप में वर्णन कर सकते हैं यह है, हालांकि, थीटा नामक एक
थोड़ा कम आम.
लेकिन वह सिर्फ दो सीमा का मतलब है, इस मामले में, एक ही हैं.
>> तो यह क्या करता है, के आधार पर क्रमबद्ध विलय वास्तव में हमारे लिए करने के लिए नीचे फोड़ा?
खैर, प्रेरणा याद करते हैं.
मुझे एक और एनीमेशन तक खींच लें कि हम पिछले समय में नहीं लग रही थी.
यह एक ही विचार है, लेकिन यह एक छोटे से बड़ा है.
और मुझे आगे जाना है और बाहर बात करने जा रहा हूँ पहला - हम की तरह पर प्रविष्टि है
ऊपर छोड़ दिया, तो चयन के आधार पर क्रमबद्ध, बुलबुला तरह, अन्य प्रकार के एक जोड़े -
जल्दी खोल और - हम बात नहीं की है कि के बारे में, और ढेर और तरह समा जाता है.
>> तो कम से कम अपनी आँखें ध्यान केंद्रित करने की कोशिश ऊपर छोड़ दिया पर तीन और तब
जब मैं क्लिक करें सॉर्ट मर्ज इस हरी तीर.
लेकिन मैं अभी तक, उन सभी को चलाने दूँगा आप की विविधता की भावना दे
दुनिया में मौजूद है कि एल्गोरिदम.
मैं इस दौड़ जाने के लिए जा रहा हूँ बस कुछ सेकंड के लिए.
और तुम अपनी आँखें ध्यान केंद्रित है - एक लेने एल्गोरिथ्म, के लिए उस पर ध्यान सिर्फ एक
सेकंड - आप देखना शुरू कर देंगे इसे लागू करने की है कि पैटर्न.
>> मर्ज सॉर्ट, नोटिस किया जाता है.
ढेर प्रकार, त्वरित सॉर्ट, खोल -
तो यह है कि हम तीन पेश लगता है सबसे खराब एल्गोरिदम पिछले हफ्ते.
लेकिन यह है कि हम करने के लिए आज यहाँ हो यह अच्छी बात है में से एक है जो मर्ज सॉर्ट, पर देखने के लिए
आसान लोगों को भी, पर लग रहा है यह शायद आपके मन झुकेगा हालांकि
बस थोड़ा सा.
यहाँ हम देख सकते हैं कि अभी कितना चयन के आधार पर क्रमबद्ध बेकार है.
>> लेकिन दूसरा पहलू पर, यह है लागू करने के लिए वास्तव में आसान.
और शायद सेट पी 3 के लिए, उस में से एक है आप को लागू करने के लिए चुना है एल्गोरिदम
मानक संस्करण के लिए.
बिल्कुल सही, बिल्कुल ठीक.
>> आप अगर लेकिन फिर, एन के रूप में बड़े हो जाता है एक तेज कलन विधि को लागू करने के लिए चयन
मर्ज प्रकार की तरह, बाधाओं बड़ा में हैं और बड़ा आदानों, अपने कोड अभी है
तेजी से चलाने के लिए जा रहा.
आपकी वेबसाइट को बेहतर काम करने के लिए जा रहा है.
आपकी उपयोगकर्ताओं को खुश होने जा रहे हैं.
और इसलिए इन इफेक्ट होते हैं वास्तव में दे रही है
हमें कुछ गहरा सोचा.
>> तो चलो क्या मर्ज पर एक नज़र सॉर्ट सब के बारे में वास्तव में है.
शांत बात यह है कि मर्ज है तरह सिर्फ यह है.
यह हम बुलाया है क्या, फिर, है pseudocode, pseudocode जा रहा है
अंग्रेजी की तरह वाक्यविन्यास.
और सादगी है एक तरह से आकर्षक.
>> इसलिए n तत्वों के इनपुट पर - इतना है कि यहाँ सिर्फ एक सरणी है, इसका मतलब है.
यह उस में एन चीजें मिल गया है.
यही कारण है कि हम वहाँ कह रहे है.
>> N कम से कम 2 है, तो वापसी.
ताकि बस तुच्छ मामला है.
N कम से कम 2 है, तो जाहिर है यह है 1 या 0, जो मामले में बात
पहले से ही हल या nonexistent है, तो सिर्फ वापसी.
ऐसा करने के लिए कुछ भी नहीं है.
इसलिए कि बंद बांधना एक साधारण मामला है.
>> वरना, हम तीन चरणों का है.
सॉर्ट तत्वों की बाईं आधे को क्रमबद्ध तत्वों की सही आधा,
और तब क्रमबद्ध हिस्सों विलय.
क्या यहां दिलचस्प बात यह है कि मैं एक तरह से सही, punting रहा हूँ?
तरह का एक परिपत्र परिभाषा नहीं है इस एल्गोरिथ्म के लिए.
क्या मायने में इस एल्गोरिथ्म की है परिभाषा परिपत्र?
>> दर्शक: [सुनाई].
>> डेविड मालन: हाँ, मेरे छँटाई एल्गोरिथ्म, अपने कदम के दो "प्रकार हैं
कुछ और. "और इसलिए है कि भीख माँगता सवाल है, ठीक है, मैं क्या उपयोग करने के लिए जा रहा हूँ
बाईं आधा सॉर्ट करने के लिए और सही आधा?
और यहाँ सौंदर्य है कि भले ही फिर, यह है मन झुका
संभावित हिस्सा है, आप एक ही उपयोग कर सकते हैं बाईं आधा सॉर्ट करने के लिए एल्गोरिथ्म.
>> लेकिन एक मिनट रुको.
आप सॉर्ट करने के लिए कहा हो जब बाईं आधा, दो क्या हैं
कदम अगले होने जा रहा?
हम छोड़ दिया आधा सुलझा लेंगे बाईं आधा और सही
बाईं आधे का आधा.
अरे नहीं, मैं कैसे उन दो प्रकार है अब आधा या चौथाई?
>> लेकिन यह ठीक है.
हम यहाँ एक छँटाई कलन विधि है.
और आप में चिंता हो सकती है, भले ही पहले यह एक अनंत की तरह है
पाश, यह कभी नहीं है कि एक चक्र है खत्म हो रहा है - यह जा रहा है
क्या होता है एक बार अंत?
N कम से कम 2 है एक बार.
अंत में होने जा रहा है जो, क्योंकि आप संयोग रखने के लिए और अगर
निश्चित रूप से, इन हिस्सों संयोग में संयोग अंततः आप समाप्त करने के लिए जा रहे हैं
सिर्फ 1 या 0 तत्वों के साथ.
जो बात, इस एल्गोरिथ्म पर आप कर रहे हैं कहते हैं.
>> इस में तो असली जादू एल्गोरिथ्म में किया जा रहा है
कि अंतिम चरण के विलय.
सिर्फ दो विलय यह सरल विचार बातें, कि अंततः क्या हो रहा है
हम में से एक सरणी सॉर्ट करने के लिए अनुमति देने के लिए, के, आठ तत्व कहते हैं.
इसलिए मैं आठ और तनाव गेंदों ऊपर है यहां आठ कागज के टुकड़े, और एक
गूगल ग्लास -
जो मैं रखने के लिए मिलता है.
>> [हंसी]
>> डेविड मालन: हम आठ ले सकता है स्वयंसेवकों, और हम कर सकते हैं, तो चलो देखते हैं
इसलिए, यह बाहर खेलते हैं.
ठीक है, वाह.
कम्प्यूटर साइंस मज़ा हो रही है.
ठीक है.
तो आप कैसे तीन के बारे में, वहाँ सबसे बड़ा हाथ ऊपर.
पीठ में चार.
और हम कैसे के बारे में आप क्या करेंगे इस पंक्ति में तीन?
और सामने चार.
तो आप आठ, ऊपर की ओर आते हैं.
>> [हंसी]
>> डेविड मालन: मैं वास्तव में हूँ यह क्या है यकीन नहीं.
यह तनाव गेंदों है?
डेस्क दीपक?
सामग्री?
इंटरनेट?
>> ठीक है.
तो ऊपर की ओर आते हैं.
कौन चाहते हैं -
ऊपर आते रहते हैं.
चलो देखते हैं.
और इस स्थान में डालता है -
आप स्थान में हो.
ओह, एक मिनट रुको.
1, 2, 3, 4, 5, 6, 7 - ओह, अच्छा.
ठीक है, हम अच्छा कर रहे हैं.
ठीक है, तो हर कोई एक सीट है, लेकिन नहीं गूगल ग्लास पर.
मुझे इन कतार के लिए करते हैं.
तुम्हारा नाम क्या है?
>> MICHELLE: मिशेल.
>> डेविड मालन: मिशेल?
सब ठीक है, आप की तरह लग रहे हो geek, यह ठीक है अगर.
खैर, मैं भी, मुझे लगता है, बस एक पल के लिए.
सब ठीक है, स्टैंडबाय.
हम एक साथ आने की कोशिश कर रहा है गूगल ग्लास के लिए मामले का उपयोग करें, और हम
यह सिर्फ क्या करना मजेदार होगा इस लोगों को जब मंच पर हैं.
हम विश्व रिकॉर्ड होगा उनके नजरिए से.
ठीक है.
शायद गूगल का इरादा नहीं है.
सब ठीक है, तुम बुरा न मानो पहने यह अगले अजीब मिनट के लिए,
उस अद्भुत होगा.
>> ठीक है, तो हम यहां की एक सरणी है तत्वों, और प्रति के रूप में उस सरणी,
इन लोगों में कागज के टुकड़े ' हाथ, वर्तमान unsorted है.
>> MICHELLE: ओह, यह बहुत अजीब है.
>> डेविड मालन: यह बहुत ज्यादा यादृच्छिक है.
और बस एक पल में, हम कोशिश करने जा रहे हैं सॉर्ट साथ विलय को लागू करने के लिए
कि महत्वपूर्ण जानकारी है और कहाँ देखते हैं.
और मर्ज प्रकार के साथ यहाँ चाल है हम अभी तक ग्रहण नहीं किया है कि कुछ और.
हम वास्तव में कुछ की जरूरत अतिरिक्त जगह.
तो क्या विशेष रूप से होने जा रहा है इस बारे में दिलचस्प है कि इन
लोग एक छोटे से चारों ओर ले जाने के लिए जा रहे हैं मैं मान जा रहा हूँ बिट, ऐसा इसलिए है क्योंकि
अंतरिक्ष के एक अतिरिक्त सरणी है, सही उनके पीछे, कहते हैं.
>> वे अपनी कुर्सी के पीछे रहे हैं तो अगर, कि माध्यमिक सरणी है.
वे यहाँ बैठा रहे हैं, वह है, प्राथमिक सरणी.
लेकिन यह है कि हम एक संसाधन है बुलबुले के साथ इस प्रकार अब तक leveraged नहीं
सॉर्ट, चयन प्रकार के साथ, प्रविष्टि प्रकार के साथ.
पिछले सप्ताह याद है, हर कोई बस एक तरह से जगह में फेरबदल.
वे किसी भी अतिरिक्त मेमोरी का उपयोग नहीं किया.
हम से लोगों के लिए कमरा बनाया आसपास के लोगों घूम रहा है.
>> तो यह भी एक महत्वपूर्ण जानकारी है.
इस व्यापार बंद में सामान्य रूप में, वहाँ संसाधनों के कंप्यूटर विज्ञान,.
आप कुछ तेजी लाने के लिए चाहते हैं समय की तरह, आप करने जा रहे हैं
एक मूल्य का भुगतान किया है.
और उन मूल्यों का एक बहुत अक्सर है अंतरिक्ष, स्मृति की मात्रा या मुश्किल
आप उपयोग कर रहे हैं कि डिस्क स्थान.
या, स्पष्ट रूप से, राशि प्रोग्रामर समय की.
यह आपको लगता है कि कितना समय, मानव, वास्तव में कुछ और लागू करने के लिए
जटिल एल्गोरिथ्म.
लेकिन आज के लिए, व्यापार बंद समय और स्थान है.
>> तुम लोग बस को पकड़ सकता है तो अगर आपके संख्या तो हम आप कर रहे हैं देख सकते हैं
वास्तव में 4, 2, 6, 1, 3, 7, 8 मिलान.
बहुत बढ़िया.
इसलिए मैं आर्केस्ट्रा की कोशिश करने जा रहा हूँ बातें, तुम लोग कर सकते हैं, बस
यहाँ मेरे नेतृत्व का पालन करें.
>> तो मुझे लगता है, सबसे पहले, लागू करने के लिए जा रहा हूँ जो pseudocode का पहला कदम
n तत्वों के इनपुट पर, यदि n है 2 से भी कम, फिर लौट आते हैं.
जाहिर है, कि नहीं करता लागू होते हैं, तो हम पर चलते हैं.
इसलिए तत्वों की बाईं आधा सॉर्ट.
तो यह है कि मैं ध्यान केंद्रित करने जा रहा हूँ मतलब है मेरे इन पर बस एक पल के लिए ध्यान
यहां चार लोग.
सब ठीक है, मुझे लगता है कि आगे क्या करना है?
>> दर्शक: बाईं आधा तरह.
>> डेविड मालन: तो अब मैं हल करना होगा इन लोगों के बाईं आधा.
फिर, क्योंकि अपने आप को ग्रहण लक्ष्य बाईं आधा तरह है.
आप यह कैसे करते हो?
अभी भी, निर्देशों का पालन करें हम इसे फिर से कर रहे हैं.
तो बाईं आधा सॉर्ट.
अब मैं इन दो लोगों छँटाई कर रहा हूँ.
आगे क्या आता है?
>> दर्शक: बाईं आधा तरह.
>> डेविड मालन: वाम आधा तरह.
तो अब ये यहाँ इस सीट, 1 आकार की एक सूची है.
और अपना नाम फिर क्या है?
>> राजकुमारी डेज़ी: राजकुमारी डेज़ी.
>> डेविड मालन: राजकुमारी डेज़ी यहाँ है.
और इसलिए वह पहले से ही हल है क्योंकि सूची 1 आकार की है.
मैं आगे क्या करते हैं?
उस सूची का है क्योंकि, ठीक है, लौटने कम से कम 2 है, जो आकार 1,.
तो फिर अगला कदम क्या है?
और अब आप की तरह करने के लिए है आपके मन में पीछे.
>> है, जो सही आधा तरह -
आपका नाम क्या है?
>> लिंडा: लिंडा.
>> डेविड मालन: लिंडा.
और इसलिए अब हमें क्या करना है कि हम आकार 1 की एक सूची है?
>> दर्शक: वापसी.
>> डेविड मालन: सावधान.
हम पहले लौटने के लिए, और अब तीसरे मैं एक तरह से यह द्वारा शब्दों में वर्णन करना और अगर - कदम
मैं अब, अब दो सीटों को गले लगाते इन दोनों तत्वों को मर्ज करने के लिए है.
तो अब दुर्भाग्य से, तत्वों क्रम से बाहर हैं.
लेकिन है कि जहां विलय प्रक्रिया सम्मोहक पाने के लिए शुरू होता है.
>> तुम लोगों को बस के लिए खड़े हो सकते हैं तो अगर एक पल, मैं एक में, आप की जरूरत करने के लिए जा रहा हूँ
पल, अपनी कुर्सी के पीछे करने के लिए कदम.
और लिंडा, 2 है क्योंकि अगर 4, क्यों नहीं की तुलना में छोटे
जब आप पहली बार के आसपास आ गए?
वहाँ रहो.
इसलिए लिंडा, आप पहली बार के आसपास आ गए.
>> अब हकीकत में यह सिर्फ एक सरणी है अगर हम सिर्फ वास्तविक समय में उसे स्थानांतरित कर सकता
इस कुर्सी से इस जगह पर.
तो कुछ निरंतर लिया है कि कल्पना चरणों की संख्या 1.
और अब -
लेकिन हम में तुम डाल करने की आवश्यकता यहां पहला स्थान.
>> और अब आप के आसपास आ सकता है साथ ही, हम करने जा रहे हैं
स्थान दो में हो.
और यह इस तरह का मानना ​​है कि भले ही एक समय लग रहा है, अब अच्छा क्या है
उस की बाईं आधा बाईं आधा अब हल है.
हम तो अब, अगर अगला कदम क्या था कहानी में आगे उल्टा?
>> दर्शक: सही आधा.
>> डेविड मालन: ठीक आधे तरह.
तो तुम लोग ऐसा करने के लिए, के रूप में अच्छी तरह से.
आप खड़े हो सकते तो अगर बस एक पल के लिए?
और तुम्हारा नाम क्या है?
>> जेस: जेस.
>> डेविड मालन: जेस.
ठीक है, तो जेस अब छोड़ दिया है ठीक आधे का आधा.
और इसलिए वह आकार 1 की एक सूची है.
वह स्पष्ट रूप से हल है.
और अपना नाम फिर से?
>> MICHELLE: मिशेल.
>> डेविड मालन: मिशेल जाहिर है 1 आकार की एक सूची.
वह पहले से ही हल है.
तो अब जादू होता है विलय की प्रक्रिया.
तो जो पहले आ रहा है?
जाहिर मिशेल.
तो तुम चारों ओर वापस आ सकता है.
हम उसके लिए अब उपलब्ध है अंतरिक्ष यहीं इस कुर्सी के पीछे है.
और अब आप के रूप में अच्छी तरह से वापस आ सकता है, अब हम स्पष्ट होना, है, दो
आधा आकार 2 से प्रत्येक -
और सिर्फ चित्रण के लिए के लिए, आप अगर एक अंतरिक्ष का एक छोटा सा कर सकता है -
यहां एक बाएं आधा, एक यहाँ सही आधा.
>> कहानी में आगे उल्टा.
क्या कदम अगले है?
>> दर्शक: मर्ज.
>> डेविड मालन: तो अब हम विलय किया है.
तो ठीक है, तो अब, शुक्र है, हम सिर्फ चार कुर्सियों को मुक्त कर दिया.
तो हम दो बार के रूप में ज्यादा मेमोरी प्रयुक्त की है, लेकिन हम दोनों के बीच फ्लिप flopping दे सकते हैं
दो सरणियों.
तो जो नंबर पहले आ रहा है?
तो मिशेल, जाहिर है.
तो चारों ओर आने और ले यहाँ अपनी सीट.
और तब संख्या 2 जाहिर है अगला, तो आप यहां आते हैं.
नंबर 4, 6 नंबर.
और फिर, एक नहीं है, भले ही शामिल चलने का थोड़ा सा,
वास्तव में, इन तुरंत हो सकता है, - एक चलती द्वारा
ठीक है, अच्छी तरह से खेला.
>> [हंसी]
>> डेविड मालन: और अब हम कर रहे हैं बहुत अच्छी हालत में.
पूरे के बाईं आधा इनपुट अब सुलझा लिया गया है.
ठीक है, तो इन लोगों की थी मेरे का लाभ -
कैसे इस पर सभी लड़कियों को खत्म किया बाएँ और दाएँ पर सभी लड़कों?
>> ठीक है, अब लोग 'की बारी है.
इसलिए मैं आप के माध्यम से चलना होगा इन चरणों.
हम फिर से लागू कर सकते हैं, तो हम देखेंगे एक ही pseudocode.
तुम आगे बढ़ो और खड़े होने के लिए चाहते हैं, और तुम लोग, मुझे आप mic देते हैं.
आप क्या नकल नहीं कर सकते हैं देखें हम बस पर यहाँ था
सूची के दूसरे छोर.
जो पहली बात करने की जरूरत है, एल्गोरिथ्म पर आधारित है?
तो इससे पहले कि आप क्या कर रहे हैं समझाने आप किसी भी पैर आंदोलनों.
>> स्पीकर 1: सब ठीक है, ताकि बाद मैं छोड़ दिया आधा हूँ
आधा छोड़ दिया, मैं वापसी.
है ना?
>> डेविड मालन: अच्छा.
>> स्पीकर 1: और फिर -
>> डेविड मालन: कौन करता है mic अगले करने के लिए जाना?
>> स्पीकर 1: अगला नंबर.
>> अध्यक्ष 2: तो मैं सही आधा हूँ के बाईं आधे के
आधा छोड़ दिया है, और मैं वापसी.
>> डेविड मालन: अच्छा.
आप वापसी.
तो अब तुम दोनों के लिए अगले क्या हो रहा है?
>> अध्यक्ष 2: हम छोटे कौन देखना चाहते हैं.
>> डेविड मालन: बिल्कुल.
हम मर्ज करना चाहते हैं.
हम विलय करने के लिए उपयोग करने के लिए जा रहे हैं अंतरिक्ष आप वे कर रहे हैं, भले ही में
जाहिर है पहले से ही हल है, हम जा रहे हैं एक ही कलन विधि का पालन करें.
तो जो पहले वापस में चला जाता है?
तो 3, और फिर 7.
और अब mic चला जाता है इन लोगों के लिए, ठीक है?
>> स्पीकर 3: तो मैं के ठीक आधे हूँ आधा छोड़ दिया, और मेरी मी से कम है
1, तो मैं सिर्फ पारित करने के लिए जा रहा हूँ -
>> डेविड मालन: अच्छा.
>> अध्यक्ष 4: मैं के ठीक आधे हूँ सही सही आधे का आधा है, और मैं कर रहा हूँ
यह भी एक व्यक्ति है, तो मैं कर रहा हूँ वापस जाने के लिए जा रहा है.
तो अब हम विलय.
>> स्पीकर 3: तो हम वापस जाओ.
>> डेविड मालन: तो तुम वापस में चलते हैं.
तो 5 से 8 तो, पहले चला जाता है.
और अब दर्शकों को, जो कदम हम अब उल्टा करने के लिए
वापस हमारे मन में करने के लिए?
>> दर्शक: मर्ज.
>> डेविड मालन: विलय बाईं आधा और सही मूल बाईं आधे का आधा.
तो अब -
और बस, यह स्पष्ट करने के लिए अंतरिक्ष का एक छोटा सा कर
आप दो लोगों के बीच.
तो अब है कि दो सूची है, बाएँ और दाएँ.
तो कैसे हम अब में तुम लोगों को मर्ज करते हैं फिर सीटों की आगे की पंक्ति?
>> 3 पहले चला जाता है.
फिर 5, जाहिर है.
फिर 7, और अब 8.
ठीक है, और अब हम कर रहे हैं?
>> दर्शक: ऐसा नहीं किया.
>> डेविड मालन: ऐसा नहीं किया, क्योंकि जाहिर है, शेष एक कदम नहीं है.
लेकिन फिर, कारण है कि मैं इस का उपयोग कर रहा हूँ जैसे शब्दजाल ", अपने मन में उल्टा"
कि क्योंकि यह सच है क्या हो रहा है.
हम इन सभी चरणों के माध्यम से जा रहे हैं, लेकिन हम एक तरह से एक के लिए रोक रहे हैं
में पल, डाइविंग गहरी एल्गोरिथ्म, एक पल के लिए रोक,
एल्गोरिथ्म में गहरी डाइविंग, और अब हम की तरह में उल्टा करने के लिए हमारे
मन और इन परतों के सभी पूर्ववत हम की तरह ठंडे बस्ते में डाल दिया है.
>> तो अब हम आकार 4 की दो सूची है.
तुम लोगों को एक आखिरी बार खड़े हो सकते हैं और यहाँ अंतरिक्ष का एक सा बना
इस बाएं है कि स्पष्ट करना मूल का आधा,
मूल के ठीक आधे.
कि हम पहले नंबर कौन है पीठ में खींचने की जरूरत है?
मिशेल, बिल्कुल.
>> तो हम यहाँ मिशेल डाल दिया.
और जो नंबर 2 है?
नंबर 2 के रूप में अच्छी तरह से पीठ पर आता है.
नंबर 3?
बहुत बढ़िया.
नंबर 4, संख्या 5, 6 नंबर, संख्या 7, और 8 नंबर.
>> ठीक है, तो यह एक बहुत की तरह महसूस किया कदम से, सुनिश्चित करने के लिए.
लेकिन अब हम इस बात की पुष्टि नहीं कर सकते, तो चलो देखते हैं एक तरह से intuitively कि इस
एल्गोरिथ्म मौलिक, खासकर के रूप में हमने देखा है के रूप में एन, वास्तव में बड़ा हो जाता है
एनिमेशन के साथ है, मूलरूप में तेजी.
इसलिए मैं सबसे खराब में, इस एल्गोरिथ्म का दावा मामला और भी सबसे अच्छा मामले में,
एन बार का बिग हे लॉग एन रहा है.
यानी, इस के कुछ पहलू है n कदम उठा लेता है, लेकिन है कि एल्गोरिथ्म
एक और पहलू में कहीं नहीं है कि चलना, कि पाशन, कि
लॉग n कदम उठा लेता है.
हम क्या उन पर हमारे उंगली रख सकते हैं दो नंबर की बात कर रहे हैं?
खैर, जहां -
mic कहाँ जाना होगा?
>> स्पीकर 1: लॉग n होगा दो में हमें तोड़ने -
अनिवार्य रूप से, दो से विभाजित.
>> डेविड मालन: बिल्कुल.
हम इस प्रकार किसी भी एल्गोरिथ्म में देख किसी भी समय अब तक, इस पद्धति का हो गया है
, विभाजित विभाजित विभाजित.
और यह आमतौर पर कम है है कि कुछ करने के लिए
लघुगणक, 2 आधार लॉग ऑन करें.
लेकिन यह वास्तव में कुछ भी हो सकता है, लेकिन 2 आधार लॉग ऑन करें.
>> अब क्या पता के बारे में?
मुझे लगता है हम एक तरह से आप विभाजित देख सकते हैं कि लड़के - आप, आप विभाजित विभाजित,
, आप विभाजित आप विभाजित.
अंत कहाँ से आया है?
>> इसलिए यह विलय है.
इसके बारे में सोचते हैं.
आप एक साथ आठ लोगों को मर्ज करते हैं, उनमें से आधे से चार का एक सेट कर रहे हैं जिससे
और दूसरे आधे एक और कर रहे हैं चार के सेट, कैसे तुम जाते हो
विलय करने के बारे में?
खैर, तुम लोगों को यह किया काफी intuitively.
>> लेकिन मैं बजाय यह एक छोटे से अधिक किया है विधिपूर्वक, मैं पर बताया कि हो सकता है
मेरे बाएँ से पहले बाएँ तरफ के व्यक्ति हाथ, बाएँ तरफ के व्यक्ति पर बताया
कि मेरे दाहिने हाथ के साथ आधा, और की सिर्फ बाद में के माध्यम से चला गया
सूची, छोटी तत्व तरफ इशारा करते हुए हर बार, पर मेरी उंगली चलती है और
के रूप में सूची में जरूरत से अधिक.
लेकिन क्या इस विलय के बारे में महत्वपूर्ण है प्रक्रिया मैं इन जोड़ों तुलना कर रहा हूँ है
तत्वों की.
ठीक आधे से और बाएं से आधा, मैं एक बार पीछे हट कभी नहीं रहा हूँ.
>> तो मर्ज ही ले जा रहा है कोई और अधिक n से कदम.
और कितनी बार मैंने किया था कि विलय करना है?
अभी हम अच्छी तरह से नहीं n से अधिक, और अंतिम मर्ज के साथ देखा.
आप कुछ करते हैं और इसलिए लेता है कि n चरणों एन बार, या इसके विपरीत, लॉग
यह हमें देने के लिए जा रहा है एन बार लॉग एन.
>> और क्यों यह बेहतर है?
खैर, हम पहले से ही है कि प्रवेश पता है अगर एन की तुलना में बेहतर है - ठीक है?
हम फोन की किताब, द्विआधारी खोज में देखा उदाहरण के लिए, लॉग n निश्चित रूप से किया गया था
रैखिक की तुलना में बेहतर है.
इसलिए कि एन बार पता है लॉग इन करने का मतलब एन बार की तुलना में निश्चित रूप से बेहतर अन्य
एन, उर्फ ​​एन चुकता.
और कहा कि हम अंततः महसूस कर रहा है.
>> इतनी बड़ी प्रशंसा का दौर, अगर हम इन लोगों के लिए, कर सकते थे.
>> [वाहवाही]
>> डेविड मालन: और अपने बिदाई उपहार - आप संख्या रख सकते हैं,
अगर आप चाहते हैं.
और अपने बिदाई उपहार, हमेशा की तरह.
ओह, और हम आपको भेज देंगे फुटेज, मिशेल.
धन्यवाद.
ठीक है.
एक तनाव गेंद को अपने आप को मदद.
>> और मुझे बीच में, ऊपर खींच देना, पेशकश करने के लिए हमारे दोस्त रोब बोडेन
इस पर कुछ अलग परिप्रेक्ष्य, आप इन के बारे में सोच सकते हैं के बाद से
एक हद तक में हो रहा कदम अलग तरह से.
वास्तव में, क्या रोब है के बारे में के लिए सेट अप हमें दिखाने के लिए हम है कि मानता है
पहले से ही की डिवाइडिंग किया आठ छोटे सूचियों में बड़ी कंपनियों की सूची,
आकार 1 में से प्रत्येक.
>> इसलिए हम pseudocode एक बदल रहे हैं बस की तरह पर पाने के लिए थोड़ा सा
विलय कैसे काम करता है के मूल विचार है.
लेकिन समय चल रहा है क्या वह क्या करने के बारे में अभी भी है
एक ही होने जा रहा.
और फिर, यहाँ सेट अप है कि वह है आकार 1 के आठ सूचियों के साथ शुरू हो गया.
तो आप वह हिस्सा है जहां बहुत याद किया वास्तव में लॉग n किया, लॉग एन लॉग एन
इनपुट की डिवाइडिंग.
>> [वीडियो प्लेबैक]
>> -वह एक कदम के लिए है.
बार बार कदम दो, के लिए सूचियों के जोड़े विलय.
>> डेविड मालन: हम्म.
केवल ऑडियो आ रहा है अपने कंप्यूटर के बाहर.
चलो फिर से इस कोशिश करते हैं.
>> बस मनमाने ढंग से जो उठा - अब हम चार सूची है.
पहले जानें.
>> डेविड मालन: हम वहाँ जाते हैं.
>> -विलय 108 और 15, हम अंत सूची में 15, 108 के साथ.
50 और 4 विलय, हम 4, 50 के साथ खत्म होता है.
विलय 8 और 42, हम 8, 42 के साथ खत्म होता है.
और 23 और 16 के विलय, हम 16, 23 के साथ खत्म होता है.
>> अब हमारे सभी सूचियों आकार 2 के हैं.
सूचना है कि के प्रत्येक चार सूचियों हल है.
तो हम विलय शुरू कर सकते हैं फिर सूचियों के जोड़े.
, 15 और 108 और 4 और 50 विलय हम पहले तो, 4, तो 15 ले
50, फिर 108.
8, 42 और 16, 23 मर्ज करना, हम पहले ले 8, फिर 16, फिर 23,
फिर 42.
>> तो अब हम आकार की सिर्फ दो सूची है 4, जिनमें से प्रत्येक का हल है.
तो अब हम इन दो सूचियों विलय.
सबसे पहले, हम 4 लेते हैं, तो हम ले 8, तो हम तो, फिर 15, 16 ले
23, फिर 42, फिर 50, फिर 108.
>> [अंत वीडियो प्लेबैक]
>> डेविड मालन: एक बार फिर, नोटिस, वह कभी नहीं किसी दिए कप एक से अधिक बार छुआ
यह परे आगे बढ़ाने के बाद.
तो वह दोहरा कभी नहीं रहा है.
इसलिए वह हमेशा पक्ष के लिए आगे बढ़ रहा है हम हमारे n मिल गया और है कि जहां.
>> क्यों मुझे एक एनीमेशन ऊपर खींच देना नहीं हमने पहले देखा था, लेकिन यह है कि इस समय
मर्ज प्रकार पर ही केंद्रित थी.
मुझे आगे जाना है और ज़ूम इस यहाँ पर में.
पहले मुझे एक यादृच्छिक इनपुट का चयन करते हैं, इस आवर्धन, और आप की तरह देख सकते हैं
प्रदान के लिए हम क्या ले लिया, इससे पहले, सॉर्ट वास्तव में क्या कर रही है विलय.
>> तो आप इन हिस्सों हो या कि नोटिस इन तिमाहियों या इन eighths
समस्या यह है कि अचानक अच्छा आकार लेना शुरू करते हैं.
और फिर अंत में, तुम पर देख बहुत कि बेम अंत,
सब कुछ एक साथ मिला दिया गया है.
>> तो ये सिर्फ तीन अलग हैं एक ही विचार पर ले जाता है.
लेकिन महत्वपूर्ण अंतर्दृष्टि, बस डिवाइड पसंद और बहुत पहले वर्ग में जीत,
हम किसी भी तरह विभाजित करने का निर्णय लिया गया था कि कुछ बड़ा, में में समस्या
भावना में की तरह समान कुछ, लेकिन छोटे और छोटे और छोटे
और छोटे.
>> एक तरह से सोचने के लिए अब एक और मजेदार तरीका इन के बारे में, भले ही यह नहीं है
आप एक ही सहज देने जा रहा समझ है,
निम्नलिखित एनीमेशन.
तो यह एक वीडियो किसी को एक साथ रखा है विभिन्न कि एसोसिएटेड
के लिए विभिन्न कार्यों के साथ लगता है सम्मिलन सॉर्ट मर्ज प्रकार के लिए, और
दूसरों के एक जोड़े के लिए.
तो एक पल में, मैं खेलने के हिट करने के लिए जा रहा हूँ.
यह लंबे समय से एक मिनट के बारे में है.
और तुम अब भी देख सकते हैं, भले ही पैटर्न हो रहा है, आप कर सकते हैं इस समय
भी इन एल्गोरिदम हैं कैसे सुना अलग तरह से और के साथ प्रदर्शन
कुछ अलग पैटर्न.
>> इस प्रविष्टि प्रकार का होता है.
>> [टन खेलने]
>> डेविड मालन: यह फिर से कोशिश कर रहा है प्रत्येक तत्व सम्मिलित करने के लिए
जहां यह है में.
यह बुलबुला तरह है.
>> [टन खेलने]
>> डेविड मालन: और आप की तरह महसूस कर सकते हैं यह कर रही है कि कैसे अपेक्षाकृत छोटे काम
हर कदम पर.
इस उकताहट कैसा लगता है.
>> [टन खेलने]
>> डेविड मालन: यह चयन प्रकार है हम तत्व का चयन करें जहां हम से चाहते हैं
फिर और फिर और फिर से गुजर रही और शुरुआत में इसे लगाने.
>> [टन खेलने]
>> डेविड मालन: यह है, की तरह मर्ज है जो आप वास्तव में महसूस करना शुरू कर सकते हैं.
>> [टन खेलने]
>> [हंसी]
>> डेविड मालन: कुछ कहा सूक्ति हम पर गौर नहीं किया है जो प्रकार,.
>> [टन खेलने]
>> डेविड मालन: तो मुझे देखते हैं, अब, उम्मीद है आप से कर रहे हैं के रूप में विचलित
संगीत, मैं एक छोटी सी पर्ची कर सकते हैं यहां गणित की सा.
तो हम कर सकते हैं कि एक चौथा रास्ता नहीं है यह इन का मतलब क्या है के बारे में सोचना
कार्यों लोगों की तुलना में तेजी से हो हम पहले देखा है कि.
और तुम से पाठ्यक्रम में आ रहे हैं एक गणित पृष्ठभूमि, आप
वास्तव में पहले से ही शायद जानते हैं आप कि इस तकनीक पर एक शब्द थप्पड़ कर सकते हैं -
अर्थात् प्रत्यावर्तन, एक समारोह कि किसी तरह खुद को कहता है.
>> और फिर, याद सॉर्ट मर्ज कि pseudocode अर्थ में पुनरावर्ती था
उस मर्ज तरह है कदमों में से एक सॉर्ट कॉल करने के लिए गया था -
कि, खुद है.
लेकिन शुक्र है, हम कर रखा है क्योंकि , की तरह बुला, या ऐसा मर्ज
विशेष रूप से, एक और छोटे छोटे पर और छोटी सूची, हम अंततः
हम फोन करता हूँ क्या करने के लिए धन्यवाद बाहर तली एक आधार के मामले, हार्ड कोडित मामले कि
सूची छोटा है, ने कहा कि अगर कम से कम 2 उस मामले में, बस आती हूँ.
हम चाहते हैं कि विशेष मामला नहीं था, एल्गोरिथ्म, बाहर नीचे कभी नहीं होगा
और आप वास्तव में एक में मिल जाएगा वास्तव में हमेशा के लिए अनंत लूप.
>> लेकिन अब हम करना चाहते थे कि लगता है यह, फिर से, का उपयोग n पर कुछ संख्या
इनपुट के आकार के रूप में.
और मैं क्या है, आप से पूछना चाहता था में शामिल कुल समय
सॉर्ट मर्ज चल रहा है?
या अधिक आम तौर पर, क्या है समय में यह की कीमत क्या है?
>> वैसे यह है कि मापने के लिए बहुत आसान है.
N कम से कम 2 है, तो समय शामिल n तत्वों छँटाई में,
2 n है जहां, 0 है.
हम बस वापस जाने की वजह से.
कुछ किया जाना कोई काम नहीं है.
अब यकीनन, शायद यह एक या दो कदम है राशि के लिए बाहर निकालने के लिए कदम
काम, लेकिन यह 0 से काफी करीब है कि मैं अभी कोई काम नहीं है कहने जा रहा हूँ
सूची इतना छोटा है तो आवश्यक शुष्क हो लिए.
>> लेकिन इस मामले में दिलचस्प है.
पुनरावर्ती मामले की शाखा थी किसी और ने कहा कि pseudocode है, की तरह
बाईं आधा, सही तरह आधा, दो हिस्सों विलय.
अब क्यों इस अभिव्यक्ति करता है उस खर्च का प्रतिनिधित्व करते हैं?
खैर, एन टी बस का मतलब n तत्वों सॉर्ट करने के लिए समय है.
और फिर दाहिने बाजू पर वहाँ पर हस्ताक्षर बराबरी, एन टी विभाजित
2 से क्या की लागत की बात कर रहा है?
बाईं आधा छँटाई.
2 से विभाजित n के अन्य T है संभवतः के लिए लागत की चर्चा करते हुए
ठीक आधे सॉर्ट.
>> और फिर प्लस n?
विलय है.
क्योंकि आप दो सूचियों में से एक है अगर आकार पर 2 n और आकार n का एक और
2 पर, आप अनिवार्य रूप से स्पर्श करने के लिए है उन तत्वों में से प्रत्येक के लिए, बस रोब पसंद
कप में से प्रत्येक को छुआ, और बस हम में से प्रत्येक में बताया
मंच पर स्वयंसेवकों.
तो पता विलय की कीमत है.
>> अब दुर्भाग्य से, इस सूत्र खुद पुनरावर्ती भी है.
तो सवाल पूछा, तो पता कहते हैं, अगर, 16, मंच पर 16 लोग अगर वहाँ
या वीडियो में 16 कप, कितने कुल कदम यह उन्हें तरह लेते हैं
मर्ज प्रकार के साथ?
यह वास्तव में एक स्पष्ट जवाब नहीं है, अब आप की तरह है क्योंकि
बारी बारी से इस सूत्र का जवाब.
>> मुझे का प्रस्ताव करते हैं लेकिन क्योंकि यह ठीक है, हम निम्नलिखित कर सकते हैं.
16 लोगों या ऐसा करने के लिए शामिल समय 16 कप प्रतिनिधित्व किया जा रहा है
आम तौर पर 16 से टी के रूप में.
लेकिन उस के अनुसार, के बराबर होती है हमारी पिछले सूत्र, 2 गुना राशि
समय की यह सॉर्ट करने के लिए ले जाता है 8 कप प्लस 16.
और फिर, प्लस 16 मर्ज करने के लिए समय है, और 8 की दो बार टी है
बाईं आधा और सही आधा सॉर्ट करने के लिए समय है.
>> लेकिन फिर, यह पर्याप्त नहीं है.
हम गहरे में गोता लगाने के लिए है.
यह हम जवाब देने के लिए किया है इसका मतलब सवाल, 8 की टी क्या है?
खैर 8 टी सिर्फ 2 है 4 प्लस 8 बार टी.
खैर, 4 की टी क्या है?
4 में से 2 टी प्लस 4 की सिर्फ 2 बार टी है.
खैर, 2 टी क्या है?
2 की 1 टी प्लस 2 की सिर्फ 2 बार टी है.
>> और फिर, हम किस तरह की हो रही है इस चक्र में फँस गया.
लेकिन यह है कि हिट करने के बारे में है आधार के मामले तथाकथित.
1 टी क्या है, हम यह दावा किया?
0.
तो अब अंत में, हम पीछे की ओर काम कर सकते हैं.
>> 1 टी 0 है, तो मैं अब एक को वापस जा सकते हैं यहाँ इस आदमी को लाइन, और मैं कर सकता हूँ
1 के टी के लिए 0 में प्लग.
ताकि, यह 2 बार शून्य के बराबर होती है इसका मतलब अन्यथा 0, प्लस 2 के रूप में जाना जाता है.
और इतना है कि पूरे अभिव्यक्ति 2 है.
>> अब मैं जिसका जवाब 2 का टी, ले 2, मध्य पंक्ति में प्लग है, टी
4 की, कि मुझे 2 बार देता है 2 प्लस 4, इसलिए 8.
मैं तो पिछले करने के लिए 8 में प्लग रेखा, कि मुझे 2 गुना 8, 16 देता है.
और हम तो साथ कि जारी है 24, 16 में उनका कहना है, हम अंत में मिलता है एक
64 की मूल्य.
>> अब है कि तरह की बात करते हैं और खुद की n अंकन करने के लिए कुछ भी नहीं है,
बड़ी हे, हम है कि ओमेगा के बारे में बात कर रहे हैं.
लेकिन यह 64 वास्तव में पता चला है कि 16, इनपुट के आकार,
16 में से 2 आधार लॉग ऑन करें.
और यह सिर्फ एक छोटे से अपरिचित है अगर वापस लगता है, और यह वापस आ गया हूँ
आप के लिए अंततः.
इस प्रवेश 2 आधार है, तो यह 2 की तरह है क्या आप 16 देता करने के लिए उठाया?
ओह, यह 4 है, तो यह 16 गुना 4 है.
>> और फिर, यह एक बड़ा सौदा नहीं है यह अगर तरह का एक धुंधला स्मृति अब है.
लेकिन अब के लिए, विश्वास पर लेना 16 प्रवेश 16 से 64 है.
और तो वास्तव में, यह साधारण विवेक के साथ जाँच, हम पुष्टि की है -
लेकिन औपचारिक रूप से साबित नहीं -
उस मर्ज का समय चल रहा है सॉर्ट n लॉग एन वास्तव में है.
>> इतना बुरा नहीं.
यह निश्चित रूप से बेहतर है एल्गोरिदम हम इस प्रकार अब तक देखा है, और
हम एक leveraged है, क्योंकि यह है प्रत्यावर्तन नामक तकनीक.
लेकिन उस से अधिक दिलचस्प है कि, विभाजन और विजय की धारणा.
फिर, सही मायने में सप्ताह 0 से सामान यहां तक ​​कि अब एक में आवर्ती है
अधिक प्रभावशाली तरीके से.
>> अब एक मजाक सा व्यायाम, आपने अगर यह कभी नहीं किया - और आप शायद
, नहीं होता क्योंकि सामान्य की तरह लोगों को ऐसा करने के लिए नहीं लगता है.
लेकिन मैं google.com पर और अगर जाना है मैं इस बारे में कुछ सीखना चाहते हैं
प्रत्यावर्तन, लिखें.
>> [हंसी]
[अधिक हँसी]
डेविड मालन: बुरा मजाक धीरे धीरे फैल गया.
[हंसी]
डेविड मालन: बस के मामले में, यह वहाँ है.
मैं इसे गलत जादू नहीं था और मजाक नहीं है.
ठीक है.
आप के बगल में लोगों को यह समझा यह काफी बस अभी तक क्लिक नहीं किया है.
लेकिन प्रत्यावर्तन, अधिक आम तौर पर, संदर्भित करता है एक समारोह बुला की प्रक्रिया को
ही है, या अधिक आम तौर पर, एक विभाजित हो सकता है कि कुछ में समस्या
समान हल करके टुकड़ों हल प्रतिनिधि समस्याओं.
>> ठीक है, चलो गियर बदलते हैं बस एक पल के लिए.
हम निश्चित cliffhangers पर समाप्त करना, तो चलो स्थापित करने के लिए शुरू करते हैं
चरण, कई मिनट के लिए, एक बहुत ही सरल विचार पर -
दो तत्वों, सही गमागमन की है कि?
इन एल्गोरिदम के सभी हम किया गया है पिछले कुछ के बारे में बात कर
व्याख्यान कुछ शामिल की तरह गमागमन.
आज यह उन्हें मिल रहा द्वारा कल्पना की गई थी अपनी कुर्सियों से बाहर और
चारों ओर घूमना, लेकिन कोड में, हम करेंगे सिर्फ एक सरणी से एक तत्व ले
और दूसरे में यह खटखटाने.
>> तो कैसे हम यह करने के बारे में जाना है?
खैर, मुझे आगे जाना है और लिखने यहाँ एक त्वरित कार्यक्रम.
मुझे आगे जाना है और क्या करने जा रहा हूँ इस निम्नलिखित के रूप में.
चलो यह कहते हैं -
क्या हम इस एक नाम देना चाहते हैं?
>> दरअसल, नहीं.
मुझे उल्टा करते हैं.
मैं ऐसा नहीं करना चाहता हूँ कि अभी तक cliffhanger.
यह मजा खराब होगा.
के बजाय यह करते हैं.
>> मैं एक छोटे से लिखना चाहते हैं कि मान लीजिए कार्यक्रम और कहा कि अब यह गले लगाती
प्रत्यावर्तन का विचार है.
मैं एक तरह से वहाँ खुद से आगे हो गया.
मैं निम्नलिखित करने के लिए जा रहा हूँ.
>> सबसे पहले, एक त्वरित मानक io.h के शामिल, साथ ही एक cs50.h. के शामिल
और फिर मैं आगे जाने के लिए जा रहा हूँ और int मुख्य शून्य घोषित
हमेशा की तरह.
मैं मैं फ़ाइल misnamed, इसलिए किया है एहसास हुआ मुझे सिर्फ इतना यहाँ एक. सी एक्सटेंशन जोड़ दें
हम इसे ठीक से संकलन कर सकते हैं कि.
इस समारोह में बंद शुरू करो.
>> और मैं चाहता हूँ समारोह काफी, लिखने के लिए बस, पूछता है कि एक है
फिर एक नंबर के लिए उपयोगकर्ता और इजाफा होता है उस बीच सभी नंबरों
संख्या और कहते हैं, 0.
तो पहले मैं आगे जाने के लिए जा रहा हूँ और int n घोषणा.
तब मैं कुछ कोड की नकल है कि हम थोड़ी देर के लिए उपयोग किया है.
कुछ सच है.
मैं एक पल में वापस करने के लिए आया हूँ.
>> मुझे क्या करना चाहते हैं?
मैं सकारात्मक printf कहना चाहता हूँ कृपया पूर्णांक.
और फिर मैं जा रहा हूँ n INT मिल जाता कहना.
तो फिर, कुछ boilerplate कोड हम पहले का उपयोग किया है कि.
और मैं यह करने के लिए जा रहा हूँ एन 1 से कम है, जबकि.
तो यह सुनिश्चित करेंगे कि उपयोगकर्ता मुझे एक सकारात्मक पूर्णांक देता है.
>> और अब मैं निम्नलिखित करने के लिए जा रहा हूँ.
मैं संख्या के सभी को जोड़ने के लिए चाहते हैं 1 और और एन, या 0 और एन के बीच
यों, कुल राशि प्राप्त करने के लिए.
इतनी बड़ी सिग्मा प्रतीक आप याद कर सकते हैं.
तो मैं पहली बार फोन करके यह करने के लिए जा रहा हूँ सिग्मा नामक समारोह,
एन में इसे पारित, और फिर मैं जा रहा हूँ printf का कहना है, इस सवाल का जवाब सही नहीं है.
>> तो संक्षेप में, मैं और उपयोगकर्ता से int.
मैं यह सकारात्मक है सुनिश्चित करते हैं.
मैं एक चर बुलाया जवाब घोषित int प्रकार और उस में वापसी की दुकान
इनपुट के रूप में N गुजर सिग्मा के मूल्य,.
और फिर मुझे लगता है कि जवाब बाहर प्रिंट.
>> दुर्भाग्य से, भले ही सिग्मा आवाज़ में हो सकता है कि कुछ की तरह
math.h फ़ाइल, इसकी घोषणा, यह वास्तव में नहीं है.
तो यह ठीक है.
मैं यह अपने आप लागू कर सकते हैं.
मैं एक समारोह को लागू करने के लिए जा रहा हूँ सिग्मा, और इसे लेने के लिए जा रहा है एक
पैरामीटर -
चलो बस बस, एम कहते हैं इसलिए यह अलग है.
और फिर यहाँ, मैं कहने जा रहा हूँ, एम 1 से कम है, तो ठीक है, - यह एक है
बहुत शुष्क कार्यक्रम.
तो मैं आगे जाने के लिए जा रहा हूँ तुरंत वापसी 0.
यह सिर्फ सभी को जोड़ने के लिए मतलब नहीं है 1 और एम के बीच नंबरों अगर एम
खुद को 0 या नकारात्मक है.
>> और फिर मैं आगे जाने के लिए जा रहा हूँ और बहुत iteratively ऐसा करते हैं.
मैं पुराने स्कूल के इस तरह करने के लिए जा रहा हूँ, और मैं आगे जाने के लिए जा रहा हूँ
और मैं जा रहा हूँ कहना है कि 0 होने के लिए एक राशि की घोषणा.
तो मैं करने जा रहा हूँ int के पाश के लिए एक -
और मुझे यह मैच करते हैं हमारे वितरण कोड है, तो आप एक प्रति है
घर पर. INT मैं करने के लिए ऊपर पर 1 हो जाता है मैं कम से कम या मीटर के बराबर है.
मैं प्लस प्लस.
और फिर पाश के लिए इस के अंदर -
हम लगभग वहाँ रहे हैं -
योग योग प्लस 1 हो जाता है.
और फिर मैं राशि वापस करने के लिए जा रहा हूँ.
>> तो मैं जल्दी से यह किया काफी मानते.
लेकिन फिर, मुख्य समारोह सुंदर है सरल, हम कोड पर लिया है आधारित
इस प्रकार अब तक लिखा.
एक सकारात्मक पाने के लिए दोहरी पाश का उपयोग करता है उपयोगकर्ता से int.
मैं तो एक नया कार्य करने के लिए कि int पारित एन, फिर, यह फोन, सिग्मा बुलाया.
और मैं जवाब वापसी मूल्य की दुकान ब्लैक बॉक्स से वर्तमान
एक चर में, सिग्मा के रूप में जाना जवाब कहा जाता है.
तो मैं इसे मुद्रित.
>> हम अब कहानी जारी है, सिग्मा कैसे कार्यान्वित किया जाता है?
मैं इस प्रकार लागू करने का प्रस्ताव है.
सबसे पहले, त्रुटि जाँच का एक छोटा सा उपयोगकर्ता नहीं है कि बनाना
मेरे साथ खिलवाड़ और में गुजर कुछ नकारात्मक या 0 मूल्य.
तो फिर मैं एक चर घोषित योग और यह 0 पर सेट.
>> और अब मैं बराबरी से जाना शुरू 1 सभी तरह, अप करने के लिए और एम सहित
मैं शामिल करना चाहते हैं, क्योंकि सभी समावेशी एम के माध्यम से एक से नंबर.
और पाश के लिए इस के अंदर, मैं अभी करना योग यह अब जो कुछ भी हो जाता है, के साथ साथ
मैं के लिए मूल्य.
इसके अलावा मैं के लिए मूल्य.
>> एक अलग रूप में, आप यह नहीं देखा है अगर इससे पहले, कुछ वाक्यात्मक चीनी वहाँ
इस लाइन के लिए.
इसके अलावा मैं बराबर होती है, जैसा कि मैं इस फिर से लिखना कर सकते हैं सिर्फ अपने आप को कुछ कीस्ट्रोक्स को बचाने के लिए
और एक सा कूलर देखने के लिए.
लेकिन वह सब है.
यह कार्यात्मक रूप में एक ही बात है.
>> दुर्भाग्य से, इस कोड है अभी तक संकलित करने के लिए नहीं जा रहा.
मैं सिग्मा 0, कैसे हूँ बनाने चलाते हैं मैं पर चिल्लाया प्राप्त करने के लिए जा रहे हैं?
क्या यह पसंद नहीं जा रहा है?
>> दर्शक: [सुनाई].
>> डेविड मालन: हाँ, मैं घोषणा नहीं की थी सही समारोह ऊपर शीर्ष,?
सी कि उस में, बेवकूफ की तरह है ही क्या आप क्या यह बताने के लिए, और करता
इसी क्रम में यह करना होगा.
मैं यहाँ हिट दर्ज करें और अगर ऐसा है, तो मैं करने जा रहा हूँ अंतर्निहित सिग्मा के बारे में एक चेतावनी मिल
घोषणा.
>> ओह, कोई बात नहीं.
मैं शीर्ष तक जा सकते हैं, और मैं कर सकता हूँ कहते हैं, ठीक है, एक मिनट रुको.
सिग्मा कि रिटर्न एक समारोह है एक पूर्णांक और यह उम्मीद है एक
इनपुट, अर्धविराम के रूप में int.
या मैं पूरे समारोह डाल सकता है मुख्य ऊपर है, लेकिन सामान्य रूप में, मैं होता
यह इसलिए है क्योंकि, उस के खिलाफ की सिफारिश हमेशा शीर्ष पर मुख्य है अच्छा तो
आप सही में गोता लगाने और पता कर सकते हैं क्या एक कार्यक्रम के मुख्य पहले पढ़ने से कर रहे हैं.
>> तो अब मुझे स्क्रीन स्पष्ट करते हैं.
सिग्मा 0 रीमेक.
सभी की जाँच करने लगता है.
मुझे सिग्मा 0 चलाते हैं.
सकारात्मक अंतर.
मैं यह नंबर देता हूँ 3 सरल रखने के लिए.
इसलिए कि मुझे देना चाहिए 3 प्लस 2 प्लस 1, ताकि 6.
दर्ज करें, और वास्तव में मैं 6 मिलता है.
>> मैं कुछ बड़ा कर सकते हैं -
50, 12, 75.
बस एक स्पर्श करने के रूप में, मैं क्या करने जा रहा हूँ एक बहुत बड़ा तरह हास्यास्पद कुछ
संख्या, ओह, यह वास्तव में बाहर काम किया -
एह, मुझे लगता है कि सही नहीं लगता है.
चलो देखते हैं.
इसके साथ वास्तव में गड़बड़ करते हैं.
>> यह एक समस्या है.
क्या चल रहा है?
कोड है कि बुरा नहीं है.
यह अभी भी रैखिक है.
सीटी हालांकि, एक अच्छा प्रभाव है.
क्या चल रहा है?
>> इसलिए नहीं कि मैं यह सुना, तो सुनिश्चित करें.
तो यह पता चला है - और यह एक अलग रूप है.
यह करने के लिए कोर नहीं है प्रत्यावर्तन का विचार है.
मैं कोशिश कर रहा हूँ क्योंकि यह पता चला है, इतनी बड़ी संख्या का प्रतिनिधित्व करते हैं, सबसे
संभावना है कि यह गलत व्याख्या की जा रही है एक सकारात्मक नहीं संख्या के रूप में सी द्वारा,
लेकिन नकारात्मक संख्या.
>> हम इस बारे में बात की, लेकिन नहीं है यह नकारात्मक संख्या रहे हैं पता चला है
इसके अलावा में दुनिया में सकारात्मक संख्या के लिए.
और इसका मतलब है कि आप जो कर सकते द्वारा एक नकारात्मक संख्या का प्रतिनिधित्व करते हैं
अनिवार्य रूप से, आप एक का उपयोग इंगित करने के लिए विशेष बिट
नकारात्मक से अधिक सकारात्मक.
यह एक छोटे से अधिक जटिल है कि अधिक से है, लेकिन यह है कि मूल विचार है.
>> तो दुर्भाग्य से, सी भ्रामक एक है के रूप में वास्तव में अर्थ उन बिट्स की,
ओह, यह मेरे पाश, एक नकारात्मक संख्या है यहाँ, उदाहरण के लिए, वास्तव में कभी नहीं है
समाप्त करने जा रही है.
इसलिए मैं वास्तव में कुछ मुद्रण कर रहे थे बार बार, हम करेंगे
एक पूरी बहुत कुछ देखा.
लेकिन फिर, इस बिंदु के अलावा है.
यह सच में सिर्फ एक प्रकार का है हम आया हूँ कि बौद्धिक जिज्ञासा
वापस अंत में करने के लिए.
लेकिन अब के लिए, यह एक सही है हम यह मान कार्यान्वयन कि अगर
उपयोगकर्ता ints प्रदान करेगा ints भीतर कि फिट.
>> लेकिन मैं स्पष्ट रूप से इस कोड का दावा है कि इतना अधिक आसानी से किया जा सकता है.
हाथ में लक्ष्य एक नंबर लेने के लिए है, तो एम की तरह और सभी को जोड़ने
यह और 1, या इसके विपरीत के बीच संख्या 1 के बीच और यह, मैं दावा
मैं मर्ज कि इस विचार उधार ले सकते हैं कि सॉर्ट एक समस्या ले जा रहा था, जो था
इस आकार और विभाजित की कुछ छोटे में.
शायद नहीं आधा है, लेकिन छोटे, लेकिन प्रतीकात्मकता वही.
एक ही विचार है, लेकिन एक छोटे समस्या.
>> इसलिए मैं वास्तव में हूँ - मुझे इस फ़ाइल को बचाने एक अलग संस्करण संख्या के साथ.
हम इस संस्करण फोन करता हूँ 1 के बजाय 0.
और मुझे लगता है कि मैं वास्तव में यह कर सकते हैं दावा इस तरह की में इस reimplement
मन झुका रास्ता.
>> मैं अकेले इसका हिस्सा छोड़ने के लिए जा रहा हूँ.
मीटर कम है तो मैं कहने जा रहा हूँ से या 0 को भी बराबर -
मैं सिर्फ एक छोटे से होने जा रहा हूँ अधिक गुदा इस समय
मेरे त्रुटि जाँच के साथ -
मुझे आगे जाना है और 0 वापसी करने जा रहा हूँ.
यह मनमाना है.
मैं बस यूँ ही तय कर रहा हूँ अगर उपयोगकर्ता मुझे एक नकारात्मक संख्या देता है, मैं कर रहा हूँ
0 लौटने, और वे पढ़ना चाहिए और अधिक बारीकी प्रलेखन.
>> वरना -
मैं क्या करने जा रहा हूँ नोटिस.
वरना मैं एम लौटने से अधिक करने के लिए जा रहा हूँ -
एम के सिग्मा क्या है?
खैर, एम प्लस एम शून्य से 1 की सिग्मा, एम शून्य से 2, प्लस एम ऋण 3 प्लस.
मुझे लगता है कि सभी को बाहर लिखने के लिए नहीं करना चाहती.
क्यों मैं सिर्फ बाज़ी नहीं है?
बारी बारी से एक थोड़ा के साथ खुद को कॉल छोटे समस्या, अर्धविराम,
और इसे एक दिन फोन?
>> है ना?
अब यहां भी, आपको लगता है या चिंता हो सकती है यह मैं हूँ कि एक अनंत लूप है कि
मैं लागू कर रहा हूँ, जिससे उत्प्रेरण सिग्मा फोन करके सिग्मा.
लेकिन वह पूरी तरह से ठीक है क्योंकि मैं आगे एक जोड़ा जो लाइनों में सोचा है?
>> दर्शक: [सुनाई].
>> डेविड मालन: 23 से 26, जो अगर मेरी हालत है.
के बारे में अच्छी बात है क्योंकि क्या यहाँ घटाव, मैं रखना क्योंकि
सौंपने छोटी समस्याओं सिग्मा, छोटे समस्याओं, छोटे - यह नहीं है
आधे आकार.
यह केवल एक बच्चे के कदम के रूप में बड़ा है, लेकिन यह ठीक है.
अंत में, हम काम करेंगे क्योंकि नीचे 1 या 0 के लिए हमारे रास्ते.
हम 0 मारा और एक बार, सिग्मा नहीं है अब और खुद फोन करने वाला.
यह तुरंत 0 वापसी करने जा रहा है.
>> इतना प्रभाव है, तो आप एक तरह से यह हवा अगर अपने मन में, एम प्लस जोड़ने के लिए है
एम शून्य से 1, प्लस एम शून्य से 2, प्लस एम घटा 3, प्लस डॉट, दूरसंचार विभाग, दूरसंचार विभाग, एम घटा
मी, अंततः आप 0 दे रही है, और प्रभाव के सभी जोड़ने के लिए अंततः है
एक साथ इन बातों को.
इसलिए हम recursion के साथ, नहीं है, इस समस्या का हल है कि हम
पहले हल नहीं कर सकता.
दरअसल, इस के संस्करण 0, और हर तिथि करने के लिए समस्या, व्याख्या करने योग्य किया गया है
बस छोरों के लिए उपयोग करने के साथ या जब छोरों या इसी तरह के निर्माणों.
>> लेकिन recursion, मैं हिम्मत करना, हमें देता है के बारे में सोच का एक अलग तरीका
समस्याओं, हम एक ले जा सकते हैं जिससे समस्या यह है कि कुछ से विभाजित
कुछ हद तक कुछ में कुछ बड़े छोटे, मुझे लगता है हम इसे हल कर सकते हैं कि दावा
शायद एक छोटे से अधिक सुंदर ढंग से मामले में डिजाइन के, कम कोड के साथ,
और शायद यह भी कि समस्याओं का समाधान होगा , कठिन हो हम अंत में होगा के रूप में
विशुद्ध रूप से iteratively को सुलझाने, देखें.
>> लेकिन मैंने किया था कि cliffhanger हम पर छोड़ना चाहते हैं यह था.
मुझे आगे जाना है और खोल दो. से एक फाइल ऊपर -
वास्तव में, मुझे जाने दो और असली तेजी से ऐसा करते हैं.
मुझे आगे जाना है और प्रस्ताव दो. निम्नलिखित.
आज के कोड के बीच यहां इस फाइल है.
यहाँ यह एक, noswap.
>> तो यह है कि एक बेवकूफ सा प्रोग्राम है मैं क्या करने का दावा है कि कोसा
निम्नलिखित.
मुख्य रूप से, यह पहले एक वाणी INT एक्स कहा जाता है और यह प्रदान करती है
1 का मूल्य.
तो यह एक int y वाणी और यह मूल्य 2 प्रदान करती है.
तो फिर यह एक्स क्या बाहर प्रिंट और y है.
तो यह, डॉट डॉट डॉट गमागमन, कहते हैं.
>> तो यह एक समारोह बुला होने का दावा एक्स में गुजर, स्वैप बुलाया और
वाई, जिनमें से विचार है कि उम्मीद है कि है एक्स और वाई वापस आ जाएगा
अलग, विपरीत.
तो फिर यह बदली दावा!
एक विस्मयादिबोधक बिंदु के साथ.
तो यह एक्स और वाई बाहर प्रिंट.
>> लेकिन यह पता चला है कि यह बहुत साधारण प्रदर्शन नीचे
यहाँ वास्तव में छोटी गाड़ी है.
मैं एक अस्थायी घोषणा कर रहा हूँ हालांकि चर और अस्थायी रूप से एक में डाल
यह है, तो मैं फिर नियत हूँ एक बी की मूल्य -
मैं किया था, इसलिए उचित लगता है, जो एक में अस्थायी की प्रतिलिपि बचाया.
तब मैं बराबर करने के लिए बी को अद्यतन अस्थायी में जो कुछ भी था.
एक चलती का खोल खेल के इस तरह इस का उपयोग करके एक में में बी और बी
मध्यम आदमी बुलाया अस्थायी लगता है पूरी तरह से उचित.
>> लेकिन मैं दावा है कि मैं इस चलाते समय कोड, मैं अब क्या करेंगे के रूप में -
मुझे आगे जाना है और यहाँ में पेस्ट करते हैं.
मैं इस noswap.c फोन करता हूँ.
नाम का सुझाव है, यह नहीं है एक सही कार्यक्रम होने जा रहा.
Noswap. / कोई स्वैप बनाओ.
एक्स 1 है, y बदली, गमागमन, 2 है.
एक्स 1 है, वाई 2 है.
यह मूल रूप से गलत है, यहां तक ​​कि यह पूरी तरह से लगता है, हालांकि
मेरे लिए उचित.
और वहाँ एक कारण है, लेकिन हम नहीं कर रहे हैं बस अभी तक कारण प्रकट करने जा रहा.
>> मैं चाहता था कि अब दूसरा cliffhanger के लिए साथ छोड़ना, यह है एक
कूपन कोड पर एक तरह की घोषणा.
देर से दिन के साथ हमारे नवाचार इस वर्ष एक गैर तुच्छ संख्या छिड़ गई है
सवालों का, जो था नहीं हमारा इरादा.
इन कूपन कोड का इरादा, जिससे आप समस्या का हिस्सा करते हैं
जिससे एक अतिरिक्त दिन हो रही है, जल्दी सेट, तुम लोगों की मदद करने में मदद करने के लिए वास्तव में था
अपने आप को सॉर्ट, जल्दी शुरू की आप incentivizing द्वारा.
हमें भर में लोड वितरित में मदद करता है कार्यालय समय बेहतर तो यह है कि
यह एक तरह से जीत है.
>> दुर्भाग्य से, मुझे लगता है कि मेरे निर्देश तिथि करने के लिए, बहुत स्पष्ट है, इसलिए नहीं किया गया है
मैं वापस इस सप्ताह के अंत में चला गया और अद्यतन बड़ा, बिंदास पाठ करने में कल्पना
इस तरह की गोलियों की व्याख्या.
और बस से, अधिक सार्वजनिक रूप से यह कहने के लिए Default, समस्या सेट गुरुवार की वजह से कर रहे हैं
दोपहर में, पाठ्यक्रम के अनुरूप.
आप के हिस्से के परिष्करण, जल्दी शुरू करते हैं 12:00 पर बुधवार तक सेट समस्या
PM, एक कूपन से संबंधित हिस्सा कोड, विचार है कि आप का विस्तार कर सकते हैं
के लिए अपनी समय सीमा पी शुक्रवार तक निर्धारित किया है.
वह यह है कि पी के एक छोटे से हिस्से को काटा आम तौर पर क्या है के सापेक्ष सेट
बड़ी समस्या है, और आप खरीद अपने आप को एक अतिरिक्त दिन.
फिर, यह आप के बारे में सोच रही हो जाता है सेट समस्या, करने के लिए आप हो जाता है
जल्दी ही कार्यालय समय.
लेकिन कूपन कोड समस्या अभी भी है आप इसे प्रस्तुत नहीं करते, तो भी जरूरी है.
>> लेकिन अधिक compellingly यह है.
(मंच कानाफूसी) और छोड़ने के लिए उन लोगों को जल्दी यह अफसोस वाला हैं.
के रूप में छज्जे पर लोग कर रहे हैं.
मैं पर लोगों को पहले से माफी माँगता हो जाएगा कि कारणों के लिए बालकनी
बस एक पल में साफ है.
>> तो हम में से एक है भाग्यशाली रहे हैं CS50 के पूर्व प्रमुख शिक्षण साथियों पर
एक कंपनी dropbox.com कहा जाता है.
वे बहुत उदारता से एक दान किया इतना अंतरिक्ष के लिए यहाँ कूपन कोड,
ऊपर से है जो सामान्य 2 गीगाबाइट.
तो मैंने सोचा कि क्या हम इस पर क्या होगा अंतिम ध्यान दें, एक सस्ता के एक सा करना है
बस एक पल में, हम को उजागर करेंगे जिससे विजेता और जो एक कूपन है
आप तब तक जा सकता है कि कोड को अपने वेबसाइट, उस में टाइप करें, और देखा, मिल एक
आपके लिए पूरी बहुत अधिक ड्रॉपबॉक्स अंतरिक्ष उपकरण और अपने व्यक्तिगत फाइल के लिए.
>> और सबसे पहले, जो भाग लेना चाहते हैं इस बैठक में?
ठीक है, अब है कि यह और भी मजेदार बना देता है.
इस 25 गीगाबाइट प्राप्त करने वाले व्यक्ति कूपन कोड - दूर तक है जो
देर से अधिक सम्मोहक अब दिन, शायद -
एक के शीर्ष पर बैठा है, जो एक है सीट कुशन है जो नीचे
कि कूपन कोड.
अब आप नीचे लग सकता है अपनी सीट कुशन.
>> [वीडियो प्लेबैक]
>> एक, दो, तीन.
>> [चिल्ला]
>> तुम एक कार हो!
आप एक कार हो!
>> डेविड मालन: हम देखेंगे बुधवार को आप.
>> तुम एक कार हो!
आप एक कार हो!
>> डेविड मालन: बालकनी लोगों, आओ यहाँ नीचे सामने करने के लिए,
हम एक्स्ट्रा कलाकार है जहां.
>> हर कोई एक कार हो जाता है!
हर कोई एक कार हो जाता है!
>> [अंत वीडियो प्लेबैक]
>> बयान: अगले CS50 पर -
>> स्पीकर 5: हे भगवान हे भगवान हे भगवान भगवान भगवान भगवान भगवान भगवान भगवान भगवान -
>> [हवाई द्वीप का गितार के प्रकार का चार तारो वाला वाद्ययंत्र विशेष निभाता]