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

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

दर्शक: मैरी बेथ. अध्यक्ष: मैरी बेथ, ऊपर की ओर आते हैं. मुझे आप के लिए यहाँ माइक्रोफोन मिलता है. आपसे मिलकर अच्छा लगा. 

दर्शक: आपसे मिलकर अच्छा लगा. अध्यक्ष: ठीक है, तो मेरे पास है यहां नीला किताबें A से Z के माध्यम से, और मुझे लगता है कि नाटक करने के लिए जा रहा हूँ मैं, छात्रों में से एक है और वे कुछ हद तक अनियमित रूप से आ रहे हैं एक तीन घंटे की परीक्षा ब्लॉक के अंत में, इसलिए वे कुछ में समाप्त कर रहे हैं इस तरह अर्द्ध यादृच्छिक क्रम. अब बस एक पल में अपने काम के लिए जा रहा है यह है कि वे कैसे वास्तव में है be-- को के अंत में में बदल गया वर्ग, सबसे अधिक संभावना है. अपनी नौकरी के लिए अब काफी, होने जा रहा है बस, हमारे लिए इन नीले किताबें सॉर्ट करने के लिए एक से जेड के माध्यम से 

दर्शक: ओह, यह है हमेशा के लिए ले जा रहा है. 

अध्यक्ष: और हम देखेंगे आप इस करते हैं, कोई दबाव नहीं. दर्शक: नहीं, कोई दबाव नहीं है या कुछ भी. 

अध्यक्ष: और मनोरंजन के लिए, चलो एक टाइमर ऊपर डाल दिया. 

दर्शक: तो बहुत मज़ा, इतना मजा आया. 

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

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

दर्शक: हाँ. 

जेड सभी के माध्यम से सब ठीक है, एक: अध्यक्ष ठीक है, बधाई हो, तुम ऐसा किया था. आप अपनी पसंद है. ब्लू? सब ठीक है, उसके लिए धन्यवाद. तो मैरी बेथ का प्रस्ताव किया क्या उसके दृष्टिकोण था, लेकिन एक और दृष्टिकोण क्या है कैसे आप इन बातों छँटाई के बारे में जाना हो सकता है? आप क्या किया होता? हरा करने के लिए रिकॉर्ड किया गया होता एक मिनट और 50 या तो सेकंड, प्लस मैं भूल वाले गिनती के लिए. आप क्या किया होता? हाँ? दर्शकों को ढेर ले लो. शुरू से शुरू. अपने कागजात की जाँच करें. और ऊपर से एक अधिक है से, हो सकता है, वे कर रहे हैं, नीचे एक है जितना अधिक होगा, तो उन्हें स्विच. 

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

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

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

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

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

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

अब डॉट, डॉट, लहरों की डॉट तरह यह है juicier विवरण में से कुछ पर हाथ, लेकिन चलो बस आगे बढ़ो और आसान बनाने चलो. आप उच्च से याद करते हैं आप के स्कूल, स्पष्ट रूप से, एक बहुत था कि था गणित की किताबें एक छोटे से धोखा शीट सामने कवर या पर आप पता चला कि पीछे के कवर जैसे क्या श्रृंखला summations यह अंततः करने के लिए कहा. सामान्य स्थिति में, यदि आपके पास एक n की तरह चर, और वास्तव में यह एक है, तुम को देखा तो अपने पुराने स्कूल गणित की किताब, आप यह वास्तव में देखना होगा कि , यहां इस राशि को कहते हैं n बार n शून्य से 1 सभी 2 से विभाजित. तो अब के लिए मुझे सिर्फ निर्धारित करते हैं यह तो विश्वास की छलांग पर, सच है कि इस रकम क्या है अप करने के लिए, और हम कर सकते थे एक अधिक सामान्य मामले में साबित होता है कि. लेकिन अब इस बाहर का विस्तार करते हैं. तो चलो इस बाहर गुणा करते हैं, तो वह है n चुकता शून्य से एन, सभी 2 से विभाजित. यही है, वास्तव में n चुकता है शून्य से 2 n खत्म, 2 से विभाजित, इसलिए कि सब अच्छा है और दिलचस्प है. लेकिन क्या हम अगर ऐसा होता है अब प्लग में एक मूल्य है? मैं आठ नहीं था मान लीजिए लोगों, लेकिन एक लाख का कहना है. और एक लाख सिर्फ इसलिए यह एक बहुत बड़ी संख्या है उस में प्लग और देखते हैं क्या होता. मुझे लगता है कि सूत्र में एक लाख प्लग तो अगर मैं, एक लाख चुकता पाने के लिए जा रहा हूँ 2 से विभाजित, शून्य से एक लाख, 2 से विभाजित. अब क्या है कि बराबर करने के लिए हो रहा है? तो 500 अरब, शून्य से 500,000. और मैं वास्तव में करते हैं कि गणित बाहर मतलब है कि, कि एक लाख छँटाई बुलबुला प्रकार के साथ लोग मुझे 499999500000 ले सकता है अंत में कदम या तुलना, हम सिर्फ extrapolating रहे हैं. 

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

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

-Senator, तुम यहाँ हो गूगल पर, और मुझे पसंद राष्ट्रपति पद के बारे में सोचना एक नौकरी के साक्षात्कार के रूप में. अब, इसे पाने के लिए मुश्किल है राष्ट्रपति के रूप में एक नौकरी, और तुम अब कठोरता के माध्यम से जा रहे हैं. यह गूगल पर एक नौकरी पाने के लिए भी मुश्किल है. हम प्रश्न हैं, और हम हमारे उम्मीदवारों सवाल पूछने, और यह एक लैरी श्विमर से है. क्या-- तुम लोगों को मैं हूँ मजाक कर रहे हैं, यह ठीक है यहाँ है. सबसे कारगर तरीका क्या है एक लाख 32 बिट पूर्णांकों तरह? 

-Well-- 

खेद; -मैं, maybe-- 

नहीं, नहीं, नहीं. मैं बुलबुला तरह लगता है गलत रास्ता तय करना होगा. 

आओ पर, जो उसे यह बताया? मैं कंप्यूटर नहीं देखा अपनी पृष्ठभूमि में विज्ञान. 

-We've वहाँ में हमारे जासूस मिला. 

ठीक है, चलो एक अलग पूछना साक्षात्कार प्रश्न. 

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

अध्यक्ष: तो के बारे में बात हालांकि विशिष्ट संख्या है, कि सभी उपयोगी होने वाला नहीं है. यह एक जीवन सबक है कि बुलबुला नहीं है क्रमबद्ध, एक लाख आदानों दिया, के रूप में कई 500,000,000,000 के रूप में कदम उठाने के लिए हो सकता है. आप वास्तव में सामान्यीकरण नहीं कर सकते बहुत प्रभावी ढंग से उस से और अच्छे डिजाइन निर्णय लेने कार्यक्रमों जब लेखन. तो चलो कैसे पर यद्यपि ध्यान केंद्रित हम इस परिणाम को आसान बनाने में हो सकता है. 

इसलिए मैं यहां पीले रंग में प्रकाश डाला है n के परिणाम, 2 से विभाजित चुकता तो एक लाख चुकता 2 से विभाजित है, और फिर मैं प्रकाश डाला है क्या अंतिम जवाब था हम बंद घटाया एक बार 2 n से विभाजित. और अब मैं करने जा रहा हूँ दावा है, आप बंद घटाना अगर जो बिल्ली परवाह 2 एक छोटे से अधिक पुराने n जब पहले इस सूत्र का हिस्सा इतना बड़ा है? यह अन्य हावी अवधि, एन 2 से विभाजित चुकता के रूप में, स्पष्ट रूप से, इतना बड़ा है एन, एक लाख की तरह बड़ा हो जाता है कि वास्तव में एक बड़ा अंतर है 500 अरब के बीच दिन के अंत और 499999500000? ज़रूरी नहीं. और तो क्या हम करने जा रहे हैं कंप्यूटर वैज्ञानिकों के रूप में करते हैं उन निचले क्रम शर्तें उपेक्षा और इस और सच की तरह कुछ ले अभी तक यह आसान बनाने में बात करने के लिए जा रहा है कि अवधि. बड़ा हमारे डेटा सेट, बड़ा हो हमारे डाटाबेस, और अधिक वेब पृष्ठों मिल हम अधिक से खोज करने के लिए दोस्तों आप फेसबुक पर है. 

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

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

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

क्या मैं बजाय बदलते हैं कहानी, नहीं बुलबुला तरह के बारे में होना लेकिन यह ऊपरी बाध्य बारे में. आप एक एल्गोरिथ्म के बारे में सोच सकते हैं हम पहले से ही देखा है कि जिसका ऊपरी ही, अधिकतम समय या संचालन के उपाय, घिरा होने के लिए कहा जा होगा n द्वारा एक रैखिक समारोह, नहीं घुमावदार है कि एक वर्ग एक? एक एल्गोरिथ्म क्या है कि हमेशा अधिक नहीं लेता है n कदम, या तरह से 2N कदम, या 3N कदम? हाँ? 

दर्शक: ढूँढना एक सूची में सबसे बड़ी संख्या? 

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

तो बजाय अगर मुझे लगता है कि प्रस्तावित क्या इस दुनिया में एल्गोरिदम रहे हैं कि है कि एक समय चल रहा है लॉग n की बड़ी हे से घिरा, लॉग एन? हम कहाँ से पहले यह देखा है? हाँ? 

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

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

अब इस एक की, बड़ी हे क्या मतलब हो सकता है? यह अपने एल्गोरिथ्म मतलब नहीं है कि , एक और केवल एक कदम लेता है यह सिर्फ एक लेता मतलब चरणों की लगातार संख्या. शायद यह हो सकता है यह है, 1 है 10, हो सकता है यह 1000 के, लेकिन इसके बारे में स्वतंत्र है समस्या का आकार. चाहे कितना बड़ा n है, एक निरंतर समय एल्गोरिथ्म हमेशा चरणों की एक ही नंबर लेता है. तो क्या एक एल्गोरिथ्म हो सकता है हम के बारे में या सिर्फ बात की है intuitively कि कि तुम्हारे पास आता है हमेशा तथाकथित लगातार समय में चलाता है? हाँ? 

दर्शक: दो नंबर जोड़ें. अध्यक्ष:, दो नंबर जोड़ें 2 प्लस 2 किया, 4 के बराबर होती है. तो यह है कि काम हो सकता है, और क्या? कैसे और अधिक वास्तविक दुनिया के बारे में, हाँ? 

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

तो यह है कि लगातार समय है, लेकिन दूसरा पहलू क्या है? कि ऊपरी था सीमा, हम क्या चाहते हैं कम सीमा का वर्णन करने के लिए हमारे एल्गोरिदम का समय चल रहा है? लगभग एक सबसे अच्छा मामले संभवतः, अगर तुम जाएगा, इन शब्दों का सबसे अच्छा करने के लिए आवेदन कर सकता है, हालांकि मामलों, सबसे खराब मामलों, औसत मामलों अधिक आम तौर पर, लेकिन सिर्फ ध्यान केंद्रित निचले सीमा पर अधिक आम तौर पर. क्या है कि एक एल्गोरिथ्म है एक कम, एन चरणों के लिए बाध्य या 2N कदम, या 3N कदम? N चरणों में से कुछ कारक, कि इसकी कम ही है. हाँ? 

दर्शक: बुलबुला तरह? 

अध्यक्ष: बुलबुला तरह लेता है आप न्यूनतम n कदम, क्यों? ऐसा क्यों? क्यों कि शुरू तुम्हारे पास आना चाहिए Intuitively, यह करता है, भले ही नहीं बस अभी तक? हाँ? 

दर्शक: [अश्राव्य]. अध्यक्ष: बिल्कुल है. का सबसे अच्छा संभव परिदृश्य में बुलबुला तरह, और एल्गोरिदम का एक बहुत, मैं आप आठ लोग हाथ जो पहले से ही हल कर रहे हैं, यह मूर्खता होगी आप के लिए, एल्गोरिथ्म, आगे और पीछे जाने के लिए एक बार से अधिक, है ना? जैसे ही आप के रूप में, क्योंकि एक बार सूची के माध्यम से चलना, आप का एहसास ओह चाहिए, मैंने बनाया कोई स्वैप, इस सूची से बाहर निकलें हल है. लेकिन यह है कि आप n कदम उठाने जा रहा है. 

और इसके विपरीत, क्या एक और है इसके बारे में सोचने का तरीका? बुलबुला तरह एक ओमेगा है, इसलिए n का, बात करने के लिए, अगर तुम देखो, क्योंकि कम से n तत्वों, क्या मौलिक मुद्दा है? इसे हल है तो आप सही पता नहीं है. हम आठ में पराक्रम नज़र मनुष्य लोगों और,, ओह, यह हल हो कि मुझे पता कदम उठाने नहीं था, लेकिन ऐसा किया था. तुम्हारी आँखें, भी तरह आप हालांकि का, दृष्टि का एक बड़ा क्षेत्र है आप आठ तत्वों को देखा, तुम, आठ लोगों को देखा कि प्रभावी ढंग से आठ कदम है. और मैं पूरे के माध्यम से चलना ही अगर सूची मैं हाँ, हल, महसूस करते हैं. मैं रोक तो आधे रास्ते सब सोच ठीक है, यह बहुत अब तक हल है, इसे हल नहीं है क्या हालात हैं? यह सही नहीं होने जा रहा एल्गोरिदम. तेजी से, लेकिन गलत हो सकता है. 

तो अब हम एक तरह का है एक निचली सीमा का वर्णन, और लगातार समय के बारे में क्या? क्या एक कम है कि एक एल्गोरिथ्म है एक के अपने समय चलने पर बाध्य? चरण 1, 2 चरणों, 10 चरणों, लेकिन , निरंतर n के स्वतंत्र, इनपुट के आकार? हाँ, पीठ में. 

दर्शक: printf? अध्यक्ष: वह क्या है? दर्शक: printf? अध्यक्ष: printf. यकीन है, ठीक है. इसलिए यह कदम की एक निश्चित संख्या लेता है. और मैं अब उस now-- चाहिए हम सी कोड के बारे में बात कर रहे हैं और नहीं स्क्रैच, कुछ कहते हैं, printf साथ, हम सावधान पाने के लिए शुरू कर देना चाहिए. Printf ले करता है क्योंकि इनपुट, यह एक स्ट्रिंग है, और तार तकनीकी रूप से लंबाई है. हम अब लेने के लिए चाहते हैं, तो आप पर, आप मन नहीं है, तकनीकी रूप से हम उस printf तर्क दे सकते हैं एक चर लंबाई इनपुट ले करता है, और निश्चित रूप से यह अधिक लग सकता है समय, यह लंबे समय से एक स्ट्रिंग मुद्रित करने के लिए इस लंबे से. 

तो हम बस क्या विचार छंटाई और उदाहरण खोज? फोन में माइक स्मिथ के बारे में क्या पुस्तक, या अधिक आम तौर पर द्विआधारी खोज? सबसे अच्छा मामले में, क्या हो सकता है? मैं, बेम, फोन की किताब खोलने और माइक स्मिथ की संख्या है. मैं अभी उसे फोन कर सकते हैं. 

शायद दो कदम एक कदम ले लिया, लेकिन कदम की एक निरंतर संख्या मैं भाग्यशाली हूं. और सच कहूँ तो, हम पर देखा सोमवार को अपनी सहपाठी एक पंक्ति में दो बार काफी भाग्यशाली हो. और कहा कि वास्तव में स्थिर था एक कम सीमा में समय प्रश्न में एल्गोरिथ्म पर खोजने के लिए उन बंद के पीछे संख्या 50 दरवाजे. 

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

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

यह करने के लिए मुझे ले करता कितने कदम दूसरा सबसे छोटा तत्व पाते? n शून्य से 2, मैं कर रहा हूँ क्योंकि गूंगा जा रहा है मैं एक ही लोगों को देख रही है अगर फिर मैं पहले से ही उसे चुना है, तो या उसे और उनकी जगह में डाल दिया. और तीसरा कदम, एन शून्य से 3, तो n शून्य से 4. हम इस पैटर्न देखा है इससे पहले, और वास्तव में चयन क्रमबद्ध इसी प्रकार बाउंड एक ऊपरी है के एन हम चाहते हैं कि योग करते अगर चुकता. इसकी कम बाध्य, चयन क्रमबद्ध क्या है? न्यूनतम रूप से, कितना समय चाहिए चयन हम सोमवार को यह परिभाषित के रूप में क्रमबद्ध, ले? दो विकल्पों का प्रस्ताव. शायद यह पहले की तरह, एन. शायद यह है कि यह रूप में चुकता एन ऊपरी बाध्य रूप में अब है. 

दर्शक: n चुकता. अध्यक्ष: चुकता एन. क्यों? 

दर्शक: क्योंकि तुम [अश्राव्य] को परिभाषित करने के लिए. 

अध्यक्ष: बिल्कुल है. मैं चयन क्रमबद्ध परिभाषित कम से कम के रूप में यह बहुत भोली थी, चलते रहो, छोटी तत्व हैं. छोटी तत्व मिल जाए, फिर जाओ. छोटी तत्व मिल जाए, फिर जाओ. का कोई प्रकार है वहाँ उस में अनुकूलन मेरे बाद गर्भपात चलो शायद बस एन या तो कदम. तो वास्तव में, चयन क्रमबद्ध, एन के ओमेगा चुकता. 

मैं लिया जहां सम्मिलन सॉर्ट, के बारे में क्या मैं दिया गया था, और फिर मैं उसे plopped जो या उसे सही जगह में? तब मैं दूसरे व्यक्ति के लिए रवाना सही जगह में उसे या उसके plopped. फिर अगले व्यक्ति, plopped उसे या उसके सही जगह में. यह बहुत ही है कि नोटिस रेखीय, तो बात करने के लिए. मुझे लगता है मैं कर रहा हूँ, एक सीधी रेखा हूँ आगे और पीछे नहीं जा रहा, मैं वास्तव में कभी नहीं वापस देख रहे हैं, लेकिन मैं उसे सम्मिलित करते क्या हो रहा है की शुरुआत में उसके या सूची हम सोमवार को किया था? क्या हो रहा है? हाँ? दर्शक: [अश्राव्य]. अध्यक्ष: हाँ, यह ठीक है, पकड़ थी? आप से याद हो सकता है अपने सहपाठियों, वे अगर किसी भी आंदोलन के साथ बना रहे थे उनके पैर, कि एक ऑपरेशन था. तो अगर वहाँ तीन लोग यहाँ थे और नया व्यक्ति, वहाँ रास्ते पर थे इस तरह से एक लंबे समय से मंच पर, यकीन है, वह या वह सिर्फ बहुत अंत तक जा सकता है. लेकिन हम एक के बारे में सोच रहे हैं कंप्यूटर और स्मृति की एक सरणी, इन लोगों को जा रहे हैं अधिक फेरबदल करने के लिए है उस व्यक्ति के लिए जगह बनाने के लिए. और इसलिए कि n शून्य से 1 shufflings, n शून्य से 2 shufflings, एन शून्य से 3 shufflings बस की तरह है नहीं मेरे सामने, मेरे पीछे हो रहा पहले के रूप में, कुछ समझ में. अब एक अलग रूप में, और के रूप में आप ऑनलाइन देखा होगा आप के बारे में आसपास poking शुरू प्रकार, इतने सारे अलग अलग लोगों को वहाँ उनमें से बाहर वहाँ, कुछ दूसरों की तुलना में बेहतर है. दरअसल, bogosort एक है कि देखो मज़ा की तरह है. Bogosort का एक सेट लेता है नंबर या कार्ड के डेक का कहना है, बेतरतीब ढंग से उन्हें shuffles, और चेकों वे क्रमबद्ध रहे हैं. और अगर नहीं, फिर से करता है. और अगर नहीं, फिर से करता है. यदि नहीं, तो फिर से करता है. अविश्वसनीय बेवकूफ. 

और वास्तव में, यदि आप पढ़ने विकिपीडिया लेख की तरह, अपने उपनाम बेवकूफ तरह है. यह अंत में काम करेंगे, उम्मीद है, पर्याप्त समय दिया, लेकिन समय की है कि राशि काफी कुछ समय लग सकता है. मैं, चलो सकता है अगर गति चीजें इतनी पहले मैरी बेथ के उदाहरण से ऊपर, कुछ और तत्व होने से, लेकिन दो और प्रोसेसर. दो लोग, आप अगर मुझे शामिल होने मन होता नहीं. कैसे के बारे में 1 यहाँ पर, और वहाँ पर कोई नहीं go-- जाने? वहाँ पर कोई नहीं? ठीक. ब्लैक के साथ आप शर्ट, हाँ, नीचे आओ. सब ठीक है, आपका नाम क्या है? 

दर्शक: पीटर. 

अध्यक्ष: वह क्या है? 

दर्शक: पीटर. अध्यक्ष: पीटर, डेविड, आपसे मिलकर अच्छा लगा. ठीक है, हम यहाँ पीटर है आप अगर यहाँ पर मेज पर आना चाहते हैं. और तुम्हारा नाम क्या है? 

दर्शक: ऐलेना. अध्यक्ष: ऐलेना. ठीक है, आपसे मिलकर अच्छा लगा. ऐलेना पीटर से मिलने. पीटर, ऐलेना. और हम एंड्रयू की आवश्यकता होगी यहाँ के रूप में अच्छी तरह से, कृपया. और अपनी चुनौती रहा है ताश के पत्तों की एक डेक सॉर्ट करने के लिए किया जाना है. और अपरिचित हैं, डेक ताश के पत्तों की चाहिए अंततः जैसे एक छोटे से कुछ हल किया यह है कि हम तो, क्लब करूँगा जहां हुकुम, तो दिल और एक एक के रूप में इक्का से हीरे,, राजा को सभी तरह. 

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

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

दर्शक: [अश्राव्य] अध्यक्ष: वह क्या है? दर्शक: सूट द्वारा. अध्यक्ष: सूट द्वारा. तो पहले वे क्लस्टरिंग कर रहे हैं हीरे के सभी एक साथ यह सभी के लिए लगता है एक साथ ऐसा लगता है दिल, और बहुत आगे है, सम्मान के बिना कार्ड पर संख्या के लिए. और अब वे उदाहरण के लिए, प्रकट, संख्या से उन्हें छँटाई करने के लिए. बहुत अच्छा. 

सब ठीक है, इतना करने के लिए क्या हो रहा है तो यहाँ अंतिम कदम हो सकता है? हम चार हल सूट, एक बार क्या हम चार ढेर करने के लिए क्या करने की आवश्यकता है एक को प्राप्त करने के क्रम में काफी बस, डेक क्रमबद्ध? इसलिए हम उन्हें फिर से विलय करने की जरूरत है. 

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

[वाहवाही] 

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

लेकिन मैं एक तरह से मैं फोन करता हूँ क्या इस्तेमाल किया यहाँ एक बहुत ही चलने का दृष्टिकोण, विशेष नोटिस में 8 लाइन और लाइन 11. उन चलने के सबूत हैं दृष्टिकोण, एक पाशन दृष्टिकोण, कि ठीक है क्योंकि वे प्रेरित व्यवहार. उन दोनों लाइनों के लिए जाना कहना लाइन तीन, और आप कर सकते हैं प्रकार की में उस के बारे में सोच अपने एक पाश होने के रूप में मन की आंखों. यह कदम अप करने के लिए वापस जाने के लिए कह रहा है तीन और दोहराने, फिर, और फिर, और फिर. 

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

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

तो यह महसूस करना चाहिए, भले ही एक चक्रीय परिभाषा की एक बिट की तरह जहां आप किसी के जवाब दे रहे हैं बस की तरह पूछकर सवाल फिर वही सवाल, जैसे क्यों, क्यों, क्यों? हम कड़ी मेहनत से कोडित है क्योंकि वास्तविकता है विशेष लाइनों की एक जोड़ी, चरण 4, एक, अगर, और 12 कदम है जो जो प्रभावी ढंग से एक और शाखा है हम उन डिप्टी उपाय है क्योंकि, इस एल्गोरिथ्म समाप्त होगा अगर हम माइक पाते हैं, या अगर हम नहीं. लेकिन अब चरण 7 और 10 में, हम हैं क्या हम एक पुनरावर्ती एल्गोरिथ्म फोन करता हूँ. और recursion वास्तव में एक शक्तिशाली विचार है कि, पहली बार में झुकने एक छोटे से मन है हम इस प्रकार अब लागू कर सकते हैं. 

पिछले क्रमबद्ध किया जाएगा क्रमबद्ध मर्ज कि हम औपचारिक रूप से कम से कम वर्ग में, पर दिखेगा. और यह मौलिक अलग है निश्चित रूप से वे पिछले तीन, और से पिछले चार हम bogosort शामिल हैं. यहाँ मर्ज प्रकार के लिए pseudocode है. N तत्वों के इनपुट पर, इतना दिया जब आकार n के एक सरणी, एन, कम से कम 2 है वापसी. तो क्यों मुझे लगता है कि क्या करना है विवेक पहले की जाँच करें? मैं आप हाथ अगर निहितार्थ क्या है जिसकी लंबाई N एक सरणी 2 से कम है? यह पहले से ही सही, स्पष्ट रूप से, हल है? सूची या तो है क्योंकि तुच्छता है जो एक तत्व, यह इसलिए है क्योंकि क्रमबद्ध वहाँ केवल एक चीज है. या, यह मतलब है जो आकार शून्य की है सॉर्ट करने के लिए कुछ भी नहीं स्वभाव से तो, वहाँ यह हल है. गलत वहाँ अभी कुछ भी नहीं है. इसलिए कि हमारे तथाकथित आधार मामला है. 

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

लेकिन यहाँ विश्वास की छलांग, नहीं तो, अब है , तत्वों के बाईं आधा छांटने तो सही तरह तत्वों का आधा, और फिर क्रमबद्ध आधा मर्ज. ऐसा लगता है, जहां और यहाँ है जैसे हम बाहर copping रहे हैं. मैं सॉर्ट करने के लिए आप से पूछा है n तत्वों, और मैं कर रहा हूँ छँटाई द्वारा, ठीक है, यह कह बाएँ और दाएँ छँटाई. लेकिन मैं एक कह रहा हूँ दूसरी बात, और इस ऐसा लगता है कुंजी विषय है इस प्रकार अब तक अंतर्ज्ञान में, विलय का यह तीसरा कदम है. जो भी यह हालांकि , भावना में तो गूंगा लगता है जैसे सिर्फ बातें विलय एक साथ, ऐसा लगता है की ओर एक महत्वपूर्ण कदम हो दो समस्याओं का दुबारा जोड़ना कि आधे में अंततः विभाजित किया गया. 

तो आप करेंगे, चलो यह करते हैं, की तरह मर्ज एक और प्रदर्शन के साथ हास्य मुझे,, सिर्फ इतना है कि हम कुछ है संख्या के साथ काम करने के लिए. मैं आठ तनाव विनिमय कर सकते हैं आठ लोगों के लिए गेंदों? सब ठीक है, कैसे चार तुम, तीन आप के बारे में इस अनुभाग, पांच, छह, और चलो में 7, 8, ऊपर की ओर आते हैं. ठीक है, हाँ, ठीक है. माइनस 8, हम वहाँ जाते हैं, प्लस 1. बहुत बढ़िया. सभी सही पर आते हैं, चलो जल्दी आप नंबर दे. नंबर दो, तीन नंबर, चार नंबर, नंबर पांच, छह, सात और आठ. मैं सही ढंग से इस समय आठ से किया था. 

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

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

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

दर्शक: डैरेन. 

अध्यक्ष: दान. दान के लिए आगे कदम रखा है. 

दर्शक: डैरेन. अध्यक्ष: डैरेन, किया. आप डैरेन या दान कहा? 

दर्शक: डैरेन. 

अध्यक्ष: डैरेन. ठीक है, डैरेन कदम रखा है आगे और वह अब हल है. और यह लगभग एक है बेहूदा दावा, है ना? मैं वास्तव में प्राप्त करने जा नहीं लगती कुछ भी है, लेकिन हम आगे बढ़ना. अब मुझे सही तरह अवगत तत्वों का आधा. आपका नाम क्या है? 

दर्शक: ल्यूक. 

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

तो लगभग की तरह लगता है एक बुलबुला तरह प्रभाव, लेकिन मेरे मौलिक एल्गोरिथ्म, इस समय बहुत अलग. चीजें एक मिलता है लेकिन अब है थोड़ा कष्टप्रद आप क्योंकि मानसिक रूप से उल्टा करने के लिए मैं जहां बंद छोड़ दिया. मैं अभी हल आधा विलय कर दिया गया है, जो मैं अपने एल्गोरिथ्म में जहां हूँ मतलब है? मैं सही, सही आधा सॉर्ट करने के लिए है? 

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

दर्शक: Adriano. 

अध्यक्ष: Adriano. Adriano अब हल है. और तुम्हारा नाम क्या है? 

दर्शक: एलेक्स. 

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

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

दर्शक: उमर. 

अध्यक्ष: उमर किया, आगे कदम. वाम आधा हल है. और तुम्हारा नाम क्या है? 

दर्शक: क्रिस. 

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

दर्शक: मरीना. 

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

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

लेकिन मेरे बाएं हाथ अब जा रहा है डैरेन पर बात करने के लिए incremented किया, और यहाँ कुंजी के साथ भाग लेने के लिए है विलय, मैं यह कर रखने के लिए जा रहा हूँ, जाहिर है, आप अगर तरह के तर्क का पालन करें. लेकिन मेरे हाथ कभी नहीं रहे पीछे की ओर जाने के लिए जा रहा है, जो मैं सिर्फ कभी के लिए आगे बढ़ रहा हूँ मतलब मेरे विलय प्रक्रिया के साथ छोड़ दिया, और उस की कुंजी होने जा रहा है बस एक पल में हमारे विश्लेषण. 

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

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

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

दर्शक: लॉग एन. 

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

तो यह न्यूनतम लॉग n कदम है, लेकिन है इस कुंजी विलय कदम के बारे में क्या मैं विलय कर दिया, जहां मेरी बाईं आधा और सही आधा और मंच के पार चला गया? कि विलय करने के लिए कितने कदम है? यह पता है, लेकिन मैं अभी नहीं किया अंतिम समय विलय. प्रत्येक पर उन नेस्ट कॉल में से प्रत्येक पर उन नेस्ट विलीन हो जाती है, मैं अभी भी हल. मैं तो इन दो इन दो दोस्तों, विलय कर दिया दोस्तों, तो इन दो लोग और बहुत आगे है. 

तो मैं फिर से, और फिर से विलय किया था. कितनी बार? तो हर बार मैं विभाजित सूची छमाही में, मैं एक मर्ज किया. एक मर्ज करना, आधे में सूची में विभाजित. सूची विभाजित तो अगर लॉग n बार किया जा सकता है, और विलय अंततः n लेता है कदम, क्या अब ऊपरी हो सकता है चल रहा है पर बाध्य हमारे एल्गोरिथ्म के समय? n लॉग. 

और वास्तव में, कि क्या हो रहा है हम यहाँ हासिल कर लिया है. तो आप नेत्रहीन जब देख लगता है कि उन तीन बातों की ओर से कंधा मिलाकर चलने एन के खिलाफ चुकता है लॉग एन एन खिलाफ चुकता. हम देखेंगे मौलिक कौन सा, आज, लेकिन भविष्य में न केवल, बहुत, बहुत तेजी से होता है. इन लोगों के लिए प्रशंसा का एक दौर, मैं तनाव गेंदों के साथ उन्हें पुरस्कृत करेंगे. चलो आज यहाँ स्थगित करते हैं, और हम सोमवार को आप देखेंगे.