1 00:00:00,000 --> 00:00:05,760 2 00:00:05,760 --> 00:00:08,900 >> डौग लॉयड: तो CS50 में हम के बारे में सीखा छंटाई और खोज की एक किस्म 3 00:00:08,900 --> 00:00:09,442 एल्गोरिदम। 4 00:00:09,442 --> 00:00:11,400 और कभी कभी यह हो सकता है रखने के लिए एक छोटी सी मुश्किल 5 00:00:11,400 --> 00:00:14,161 क्या एल्गोरिथ्म का ट्रैक क्या करता है। 6 00:00:14,161 --> 00:00:15,910 हम वास्तव में ही है , भी सतह स्किम्ड 7 00:00:15,910 --> 00:00:18,740 कई अन्य खोज कर रहे हैं और एल्गोरिदम छँटाई। 8 00:00:18,740 --> 00:00:21,780 तो इस वीडियो में चलो बस कुछ मिनट लग 9 00:00:21,780 --> 00:00:24,980 कोशिश करते हैं और प्रत्येक एल्गोरिथ्म गढ़ने के लिए इसके मूल तत्वों के नीचे 10 00:00:24,980 --> 00:00:27,810 इसलिए आप सबसे अधिक याद कर सकते हैं उनके बारे में महत्वपूर्ण जानकारी 11 00:00:27,810 --> 00:00:31,970 और स्पष्ट करने में सक्षम होना मतभेद, यदि आवश्यक है। 12 00:00:31,970 --> 00:00:34,220 >> पहले चयन तरह है। 13 00:00:34,220 --> 00:00:38,210 चयन प्रकार के पीछे मूल विचार छोटी से छोटी अवर्गीकृत तत्व मिल रहा है 14 00:00:38,210 --> 00:00:42,890 और एक सरणी में साथ यह स्वैप कि सरणी के पहले अवर्गीकृत तत्व। 15 00:00:42,890 --> 00:00:46,620 हम सबसे ज्यादा मामले ने कहा कि इस बात का चलाते समय n चुकता किया गया था। 16 00:00:46,620 --> 00:00:50,060 और तुम क्यों याद करना चाहते हैं, तो ले लो एक चयन तरह वीडियो को देखो। 17 00:00:50,060 --> 00:00:54,560 सबसे अच्छा मामले चलाने के लिए समय भी n चुकता है। 18 00:00:54,560 --> 00:00:58,910 >> बुलबुला तरह, कि पीछे विचार एक आसन्न जोड़े स्वैप करने के लिए है। 19 00:00:58,910 --> 00:01:01,730 तो यह है कि आप में मदद करता है कि कुंजी है यहाँ अंतर याद है। 20 00:01:01,730 --> 00:01:04,920 चयन तरह है, अब तक, smallest-- बुलबुला मिल 21 00:01:04,920 --> 00:01:06,790 तरह है आसन्न जोड़े स्वैप। 22 00:01:06,790 --> 00:01:08,710 हम आसन्न जोड़े स्वैप तत्वों की है कि वे यदि 23 00:01:08,710 --> 00:01:12,530 जो प्रभावी रूप से, क्रम से बाहर हैं सही करने के लिए बड़ा तत्व बुलबुले 24 00:01:12,530 --> 00:01:17,060 और एक ही समय में यह भी शुरू होता है बाईं ओर छोटे तत्वों को स्थानांतरित करने के लिए। 25 00:01:17,060 --> 00:01:20,180 सबसे ज्यादा मामले मामला चलाने के लिए समय बुलबुला तरह के n चुकता है। 26 00:01:20,180 --> 00:01:23,476 सबसे अच्छा मामले चलाने के लिए समय बुलबुले की तरह n है। 27 00:01:23,476 --> 00:01:25,350 क्योंकि उस स्थिति में हम actually-- नहीं है 28 00:01:25,350 --> 00:01:27,141 हम करने की जरूरत नहीं हो सकती है सब पर किसी भी अदला-बदली कर सकते हैं। 29 00:01:27,141 --> 00:01:31,026 हम केवल एक बनाने के लिए है सभी एन तत्वों भर से गुजरती हैं। 30 00:01:31,026 --> 00:01:34,600 >> प्रविष्टि प्रकार में, यहाँ मूल विचार जा रहा है। 31 00:01:34,600 --> 00:01:36,630 यही कारण है कि प्रविष्टि प्रकार के लिए कीवर्ड है। 32 00:01:36,630 --> 00:01:39,630 हम के माध्यम से एक बार कदम करने के लिए जा रहे हैं से सरणी सही करने के लिए छोड़ दिया है। 33 00:01:39,630 --> 00:01:41,670 हम करते हैं और, जैसा कि हम कर रहे हैं तत्वों बदलाव करने जा रहा 34 00:01:41,670 --> 00:01:46,260 हम पहले से ही के लिए जगह बनाने के लिए देखा है कहीं फिट करने की जरूरत है कि छोटे लोगों 35 00:01:46,260 --> 00:01:48,080 पीठ कि छाँटे गए हिस्से में। 36 00:01:48,080 --> 00:01:51,600 इसलिए हम सॉर्ट सरणी का निर्माण एक सही करने के लिए छोड़ दिया है एक समय में तत्व, 37 00:01:51,600 --> 00:01:54,740 और हम जगह बनाने के लिए चीजों को पाली। 38 00:01:54,740 --> 00:01:58,650 के सबसे ज्यादा मामले चलाने के लिए समय प्रविष्टि प्रकार n चुकता है। 39 00:01:58,650 --> 00:02:02,380 सबसे अच्छा मामले चलाने के समय n है। 40 00:02:02,380 --> 00:02:05,380 >> कीवर्ड sort-- मर्ज यहां विभाजित है और विलय है। 41 00:02:05,380 --> 00:02:08,949 हम, चाहे पूरी सरणी विभाजित यह छह तत्वों, आठ तत्वों है, 42 00:02:08,949 --> 00:02:13,790 10,000 elements-- हम इसे विभाजित नीचे आधे से आधे से आधे से, 43 00:02:13,790 --> 00:02:17,720 हम सरणी के तहत जब तक n एक तत्व सरणियों की। 44 00:02:17,720 --> 00:02:19,470 N एक तत्व सरणियों का एक सेट। 45 00:02:19,470 --> 00:02:22,640 इसलिए हम एक साथ शुरू किया 1000-तत्व सरणी, 46 00:02:22,640 --> 00:02:26,550 और हम बात करने के लिए मिलता है, जहां हम 1000 एक तत्व सरणियों है। 47 00:02:26,550 --> 00:02:30,990 तो फिर हम उन उप सरणियों विलय करने के लिए शुरू वापस एक साथ सही क्रम में। 48 00:02:30,990 --> 00:02:34,860 इसलिए हम दोनों एक-तत्व सरणियों ले लो और एक दो तत्व सरणी बनाएँ। 49 00:02:34,860 --> 00:02:38,180 हम दो दो तत्व सरणियों ले लो और एक चार तत्व सरणी बनाने 50 00:02:38,180 --> 00:02:43,900 और इतने पर और इतने पर हम है जब तक फिर एक n तत्व सरणी पुनर्निर्माण किया। 51 00:02:43,900 --> 00:02:48,410 >> के सबसे ज्यादा मामले चलाने के लिए समय तरह है विलय n बार एन लॉग इन करें। 52 00:02:48,410 --> 00:02:52,390 हम n तत्व है, लेकिन इस recombining प्रक्रिया 53 00:02:52,390 --> 00:02:56,960 लॉग इन कर लेता एन कदम पाने के लिए एक पूरी सरणी के लिए वापस। 54 00:02:56,960 --> 00:03:01,160 समय चलाने सबसे अच्छा मामले भी n लॉग है n इस प्रक्रिया को वास्तव में नहीं है क्योंकि 55 00:03:01,160 --> 00:03:04,090 सरणी था कि क्या परवाह हल या नहीं के साथ शुरू करने के लिए। 56 00:03:04,090 --> 00:03:07,590 प्रक्रिया नहीं है, एक ही है शॉर्ट सर्किट बातें करने के लिए कोई रास्ता नहीं है। 57 00:03:07,590 --> 00:03:11,610 इसलिए n सबसे खराब स्थिति में लॉग n, एन सबसे अच्छा मामले में एन लॉग इन करें। 58 00:03:11,610 --> 00:03:13,960 >> हम दो के बारे में बात की थी एल्गोरिदम खोज। 59 00:03:13,960 --> 00:03:16,230 तो रैखिक खोज पुनरावृति के बारे में है। 60 00:03:16,230 --> 00:03:19,500 हम सरणी पार आगे बढ़ना एक बार, बाएं से दाएं, 61 00:03:19,500 --> 00:03:21,950 नंबर खोजने की कोशिश कि हम के लिए देख रहे हैं। 62 00:03:21,950 --> 00:03:24,550 सबसे ज्यादा मामले चलाने के समय n के बड़े हे है। 63 00:03:24,550 --> 00:03:27,610 यह पुनरावृति हमें ले सकता है हर एक तत्व के पार 64 00:03:27,610 --> 00:03:30,660 हम देख रहे हैं तत्व खोजने के लिए के लिए, या तो अंतिम स्थिति में, 65 00:03:30,660 --> 00:03:31,630 या बिल्कुल नहीं। 66 00:03:31,630 --> 00:03:34,720 लेकिन हम जब तक कि इस बात की पुष्टि नहीं कर सकते हम सब कुछ देखा है। 67 00:03:34,720 --> 00:03:36,730 सबसे अच्छा मामले हूँ, हम तुरंत लगता है। 68 00:03:36,730 --> 00:03:41,060 का सबसे अच्छा मामले चलाने के लिए समय रैखिक खोज 1 की ओमेगा है। 69 00:03:41,060 --> 00:03:43,689 >> अन्त में, द्विआधारी खोज, वहाँ था जो मिश्रित सरणी की आवश्यकता है। 70 00:03:43,689 --> 00:03:45,605 कि एक बहुत याद महत्वपूर्ण विचार 71 00:03:45,605 --> 00:03:47,155 द्विआधारी खोज के साथ काम कर रहे हैं। 72 00:03:47,155 --> 00:03:50,180 यह it-- का उपयोग करने के लिए एक शर्त है आप के माध्यम से देख रहे हैं कि सरणी 73 00:03:50,180 --> 00:03:52,160 हल किया जाना चाहिए। 74 00:03:52,160 --> 00:03:54,500 अन्यथा, कीवर्ड फूट डालो और राज है। 75 00:03:54,500 --> 00:03:58,310 आधे में सरणी विभाजित है और तत्वों का आधा खत्म 76 00:03:58,310 --> 00:04:00,780 हर बार जब आप के माध्यम से आगे बढ़ना है। 77 00:04:00,780 --> 00:04:04,330 इस वजह से फूट डालो और राज की और आधे दृष्टिकोण में बंटवारे बातें, 78 00:04:04,330 --> 00:04:07,450 सबसे ज्यादा मामले चलाने के लिए समय के द्विआधारी खोज है 79 00:04:07,450 --> 00:04:11,730 काफी हद तक है, जो लॉग n रैखिक खोज के एन से बेहतर है। 80 00:04:11,730 --> 00:04:13,570 सबसे अच्छा मामले चलाने के लिए अभी भी समय है। 81 00:04:13,570 --> 00:04:17,010 >> हम इसे तुरंत मिल सकता है पहली बार हम एक विभाजन बना है, लेकिन 82 00:04:17,010 --> 00:04:19,339 फिर, याद है कि द्विआधारी खोज है, हालांकि 83 00:04:19,339 --> 00:04:24,030 रैखिक खोज की तुलना में काफी बेहतर लॉग होने के आधार पर एन बनाम, 84 00:04:24,030 --> 00:04:27,110 आप काम के माध्यम से जाने के लिए हो सकता है पहले अपने सरणी छँटाई की जो 85 00:04:27,110 --> 00:04:32,010 निर्भर करता है कि यह कम प्रभावी बना सकता है छाँटे गए पुनरावृति के आकार पर। 86 00:04:32,010 --> 00:04:35,250 >> मैं डौग लॉयड हूँ, इस CS50 है। 87 00:04:35,250 --> 00:04:36,757