>> ठीक है, तो, कम्प्यूटेशनल जटिलता।
एक चेतावनी का सिर्फ एक बिट हम भी far-- में गोता लगाने से पहले
यह शायद के बीच हो जाएगा सबसे गणित भारी चीजें
हम CS50 में के बारे में बात करते हैं।
उम्मीद है कि यह बहुत भारी नहीं होगा और हम कोशिश करते हैं और आपका मार्गदर्शन करेंगे
प्रक्रिया के माध्यम से, लेकिन एक निष्पक्ष चेतावनी का सिर्फ एक सा है।
एक छोटा सा है गणित के यहां शामिल किया गया।
ठीक है, आदेश में ऐसा करने के लिए हमारे कम्प्यूटेशनल संसाधनों का उपयोग
वास्तविक world-- में यह सच है एल्गोरिदम समझने के लिए महत्वपूर्ण
और कैसे वे डेटा की प्रक्रिया।
अगर हमारे पास है एक सच कुशल एल्गोरिथ्म, हम
संसाधनों की मात्रा को कम कर सकते हैं हम इसके साथ सौदा करने के लिए उपलब्ध है।
हम एक एल्गोरिथ्म है, तो उस काम का एक बहुत ले जा रहा है
वास्तव में एक प्रक्रिया के लिए डेटा के बड़े सेट, यह है
अधिक आवश्यकता होती जा रही अधिक संसाधनों, और जो
सामान का पैसा, रैम, है कि सभी तरह की है।
>> तो, सक्षम होने के एक विश्लेषण करने के लिए एल्गोरिथ्म, इस उपकरण सेट का उपयोग
असल में, question-- पूछता इस एल्गोरिथ्म पैमाने कैसे करता है
हम उस पर अधिक से अधिक डेटा फेंक के रूप में?
CS50 में, हम डेटा की मात्रा हो के साथ काम करने में बहुत छोटा है।
आम तौर पर, हमारे कार्यक्रमों जा रहे हैं एक दूसरे या less-- में चलाने के लिए
शायद बहुत कम विशेष रूप से जल्दी पर।
>> लेकिन यह है कि सौदों एक कंपनी के बारे में सोचते हैं ग्राहकों के लाखों लोगों के सैकड़ों के साथ।
और वे इस प्रक्रिया की जरूरत है कि ग्राहक डेटा।
ग्राहकों की संख्या के रूप में वे है, बड़ा और बड़ा हो जाता है
यह आवश्यकता होती जा रही है अधिक से अधिक संसाधनों।
कितने अधिक संसाधनों?
खैर, उस पर निर्भर करता है हम एल्गोरिथ्म विश्लेषण,
इस उपकरण बॉक्स में उपकरण का उपयोग कर।
हम की जटिलता के बारे में बात करते हैं एक algorithm-- जो कभी कभी आप हूँ
यह समय के रूप में भेजा सुनना जटिलता या अंतरिक्ष जटिलता
लेकिन हम अभी जा रहे हैं complexity-- फोन करने के लिए
हम आम तौर पर के बारे में बात कर रहे हैं सबसे खराब स्थिति।
निरपेक्ष बुरी ढेर को देखते हुए हम उस पर फेंक हो सकता है कि डेटा,
कैसे इस एल्गोरिथ्म के लिए जा रहा है प्रक्रिया या कि डेटा के साथ सौदा?
हम आम तौर पर सबसे ज्यादा मामले फोन एक एल्गोरिथ्म बड़े-ओ का क्रम।
तो एक एल्गोरिथ्म के लिए कहा जा सकता है चुकता n या एन हे हे में चलाते हैं।
के बारे में और अधिक क्या उन एक दूसरे में मतलब है।
>> कभी कभी, हालांकि, हम परवाह करना सबसे अच्छी स्थिति के बारे में।
डेटा सब कुछ है, तो हम चाहते थे यह हो सकता है और यह बिल्कुल सही था
और हम यह सही भेज रहे थे हमारे एल्गोरिथ्म के माध्यम से डेटा का सेट।
कैसे यह उस स्थिति में संभालना होगा?
हम कभी कभी के रूप में है कि करने के लिए देखें बड़े-ओमेगा, बड़े-ओ के साथ इसके विपरीत में तो,
हम बड़ी-ओमेगा है।
सबसे अच्छी स्थिति के लिए बिग-ओमेगा।
सबसे खराब स्थिति के लिए बिग-हे।
आम तौर पर, हम के बारे में जब बात एक एल्गोरिथ्म की जटिलता,
हम के बारे में बात कर रहे हैं सबसे खराब मामले की पृष्ठभूमि।
इसलिए इस बात का ध्यान रखें।
>> और इस वर्ग में, हम आम तौर पर जा रहे हैं एक तरफ कठोर विश्लेषण छोड़ने के लिए।
विज्ञान और क्षेत्रों रहे हैं इस तरह की चीजें करने के लिए समर्पित कर दिया।
हम तर्क के बारे में बात करते हैं एल्गोरिदम के माध्यम से,
हम कई के लिए टुकड़ा-दर-टुकड़े कर देंगे जो एल्गोरिदम हम वर्ग में के बारे में बात करते हैं।
हम वास्तव में बस के बारे में बात कर रहे हैं आम भावना के साथ के माध्यम से यह तर्क,
नहीं सूत्र, या सबूत के साथ, या ऐसा कुछ।
तो चिंता मत करो, हम नहीं होगा एक बड़ा गणित वर्ग में तब्दील हो रही।
>> इसलिए मुझे लगता है कि हम जटिलता के बारे में परवाह कहा यह सवाल, कैसे पूछता है क्योंकि
हमारे एल्गोरिदम बड़ा संभाल करते हो और बड़े डेटा सेट उन पर फेंक दिया जा रहा है।
खैर, एक डेटा सेट क्या है?
मुझे लगता है कि जब मैंने कहा कि क्या मतलब था?
यह सबसे अधिक करता है जो कुछ भी मतलब है संदर्भ में समझ, ईमानदार हो।
हम एक एल्गोरिथ्म है, तो प्रक्रियाओं Strings-- हम शायद रहे हैं
स्ट्रिंग के आकार के बारे में बात कर।
यही कारण है कि डेटा है set-- आकार, संख्या
स्ट्रिंग को बनाने वाले पात्रों की।
हम एक के बारे में बात कर रहे हैं फ़ाइलें प्रक्रियाओं कि एल्गोरिथ्म,
हम कैसे के बारे में बात की जा सकती है कई किलोबाइट उस फ़ाइल को शामिल।
और उस डेटा सेट है।
हम एक एल्गोरिथ्म के बारे में बात कर रहे हैं कि, और अधिक आम तौर पर सरणियों संभालती
ऐसे छँटाई एल्गोरिदम के रूप में या एल्गोरिदम खोज,
हम शायद संख्या के बारे में बात कर रहे हैं एक सरणी शामिल है कि तत्वों की।
>> अब, हम एक उपाय कर सकते हैं algorithm-- विशेष रूप से,
मैं कहना है कि जब हम कर सकते हैं मैं एक एल्गोरिथ्म के उपाय
हम कैसे उपाय कर सकते हैं मतलब कई संसाधनों यह लेता है।
उन संसाधनों रहे हैं, कितने RAM-- के बाइट्स या राम की मेगाबाइट
यह उपयोगकर्ता है।
या कितना समय इसे चलाने के लिए लेता है।
और हम इस कॉल कर सकते हैं n के च, मनमाने ढंग से, को मापने।
जहाँ n की संख्या है डेटा सेट में तत्वों।
और एन के च कितने somethings है।
कितने संसाधनों की इकाइयों करता है यह उस डेटा को संसाधित करने की आवश्यकता है।
>> अब, हम वास्तव में परवाह नहीं है बिल्कुल n के च क्या है के बारे में।
वास्तव में, हम बहुत कम ही will-- निश्चित रूप से कभी नहीं होगा इस class-- मैं में
किसी भी वास्तव में गहरी में गोता च n है क्या का विश्लेषण।
हम बस क्या च के बारे में बात करने जा रहे हैं एन लगभग या क्या यह करने के लिए जाता है।
और एक एल्गोरिथ्म की प्रवृत्ति है अपने उच्चतम आदेश अवधि तय करती।
और हम देख सकते हैं क्या मैं लेने से मतलब
एक एक और अधिक ठोस उदाहरण देखो।
>> तो चलो हम है कि हम कहते हैं तीन अलग अलग एल्गोरिदम।
जिनमें से पहले n लेता है संसाधनों की घन, कुछ इकाइयों
आकार n के एक डेटा सेट की प्रक्रिया करने के लिए।
हम लेता है कि एक दूसरे एल्गोरिथ्म है घन प्लस n चुकता संसाधनों n
आकार n के एक डेटा सेट की प्रक्रिया करने के लिए।
और हम एक-तिहाई है कि in-- चलता है कि एल्गोरिथ्म
ऊपर लेता एन घन घटा 8N चुकता संसाधनों की प्लस 20 एन इकाइयों
एक एल्गोरिथ्म पर कार्रवाई करने के लिए आकार n का सेट डेटा के साथ।
>> अब फिर से, हम वास्तव में नहीं जा रहे हैं विस्तार के इस स्तर में मिलता है।
मैं तो बस इन ऊपर है वास्तव में कर रहा हूँ एक बात यहाँ का एक उदाहरण के रूप में
मैं जा रहा हूँ कि एक दूसरे में कर रही है, जो
हम केवल वास्तव में परवाह है कि चीजों की प्रवृत्ति के बारे में
डेटा सेट बड़ा हो जाता है।
डेटा सेट छोटा है तो, अगर वहाँ है वास्तव में एक बहुत बड़ा अंतर
इन एल्गोरिदम में।
वहाँ तीसरे एल्गोरिथ्म 13 गुना ज्यादा समय लेता है
संसाधनों का 13 गुना राशि पहले एक रिश्तेदार को चलाने के लिए।
>> हमारे डेटा सेट आकार 10 है, तो जो , बड़ा है, लेकिन जरूरी नहीं कि बहुत बड़ा नहीं है
हम देखते है कि देख सकते हैं वास्तव में एक अंतर का एक सा।
तीसरे एल्गोरिथ्म और अधिक कुशल हो जाता है।
यह वास्तव में 40% के बारे में है - या 60% अधिक कुशल है।
यह 40% समय की राशि लेता है।
यह ले जा सकते हैं run-- कर सकते हैं संसाधनों की 400 इकाइयों
आकार 10 के एक डेटा सेट की प्रक्रिया करने के लिए।
पहला जबकि एल्गोरिथ्म, इसके विपरीत,
संसाधनों की 1,000 इकाइयों लेता है आकार 10 के एक डेटा सेट की प्रक्रिया करने के लिए।
लेकिन जैसे देखो क्या होता है हमारी संख्या भी बड़ा हो।
>> अब, अंतर इन एल्गोरिदम के बीच
एक छोटे से कम स्पष्ट बनने के लिए शुरू करते हैं।
देखते हैं कि और तथ्य निचले क्रम terms-- या यों कहें,
कम exponents-- के साथ शब्दों अप्रासंगिक बनने के लिए शुरू करते हैं।
एक डेटा सेट के आकार का है 1000 और पहले एल्गोरिथ्म
एक अरब चरणों में चलाता है।
और दूसरा एल्गोरिथ्म में चलाता है एक अरब डॉलर और एक लाख कदम।
और तीसरा एल्गोरिथ्म चलाता एक अरब कदम की शर्मीली में।
यह बहुत ज्यादा एक अरब कदम है।
उन निचले क्रम के लिहाज से शुरू वास्तव में अप्रासंगिक हो जाते हैं।
और सिर्फ सच करने के लिए घर हथौड़ा point--
डेटा इनपुट आकार एक की है, तो million-- इन तीनों बहुत ज्यादा
एक quintillion-- तो ले मेरी गणित correct-- कदम है
एक डेटा निवेश की प्रक्रिया को आकार एक लाख का।
यही कारण है कि कदम की एक बहुत कुछ है।
और सच तो यह है कि उनमें से एक हो सकता है एक जोड़ी 100,000, या एक जोड़े को ले 100
लाख भी कम जब हम एक संख्या के बारे में बात कर रहे हैं
कि यह एक तरह से अप्रासंगिक है big--।
वे सब ले जाते हैं लगभग एन घन,
और इसलिए हम वास्तव में उल्लेख होगा इन एल्गोरिदम के सभी के लिए
n के आदेश पर किया जा रहा है के रूप में घन या एन घन के बड़े-हे।
>> यहाँ और अधिक से कुछ की एक सूची है आम कम्प्यूटेशनल जटिलता कक्षाएं
हम में मुठभेड़ हूँ कि एल्गोरिदम, आम तौर पर।
और भी विशेष रूप से CS50 में।
इन से आदेश दिए हैं आम तौर पर शीर्ष पर सबसे तेजी से,
निचले भाग में आम तौर पर धीमी करने के लिए।
तो लगातार समय एल्गोरिदम करते हैं की परवाह किए बिना, तेजी से हो
के आकार का डेटा इनपुट आप में से गुजरती हैं।
वे हमेशा एक ऑपरेशन ले या साथ सौदा करने के लिए संसाधनों की एक इकाई।
यह 2 हो सकता है, यह हो सकता है 3 हो सकता है, यह 4 हो सकता है।
लेकिन यह एक निरंतर संख्या है।
यह भिन्न नहीं है।
>> लघुगणक समय एल्गोरिदम थोड़ा बेहतर हैं।
और का एक बहुत अच्छा उदाहरण एक लघुगणक समय एल्गोरिथ्म
आप निश्चित रूप से अब तक देखा है किया है फोन की किताब के अलावा फाड़
फोन की किताब में माइक स्मिथ खोजने के लिए।
हम आधे में समस्या काटा।
और एन बड़ा हो जाता है तो के रूप में और बड़ा और larger--
वास्तव में, हर बार जब आप दोगुना एन, यह केवल एक और कदम लेता है।
कि एक बहुत बेहतर है तो की तुलना में, कहते हैं, रैखिक समय।
आप n दोगुना करता है, तो यह कौन सा है, कदम की संख्या दोगुनी लेता है।
आप n ट्रिपल हैं, तो यह लगता है चरणों की संख्या तीन गुना।
प्रति यूनिट एक कदम है।
>> तब एक छोटी चीजें more-- मिल छोटे से कम महान वहाँ से।
आप कभी-कभी, रैखिक लयबद्ध समय है लॉग रैखिक समय कहा जाता है या सिर्फ n लॉग एन।
और हम एक उदाहरण हूँ एक एल्गोरिथ्म की है कि
अभी भी बेहतर है, जो एन लॉग n, में रन से द्विघात time-- n चुकता।
या बहुपद समय, एन दो दो से अधिक से अधिक किसी भी संख्या।
या घातीय समय, जो यहां तक ​​कि worse-- सी n करने के लिए है।
तो कुछ निरंतर संख्या के लिए उठाया इनपुट के आकार की शक्ति।
तो अगर 1,000-- अगर वहाँ डेटा इनपुट, आकार 1000 की है
यह 1000 में सत्ता में सी लग जाएगा।
यह बहुपद समय की तुलना में बहुत खराब है।
>> भाज्य समय और भी बदतर है।
और वास्तव में, वास्तव में वहां क्या अनंत समय एल्गोरिदम मौजूद हैं,
जिसका ऐसे तथाकथित, के रूप में बेवकूफ sort-- नौकरी के बेतरतीब ढंग से एक सरणी फेरबदल करने के लिए है
और फिर देखने के लिए जाँच कि क्या यह हल है।
और यह बेतरतीब ढंग से, अगर नहीं है फिर सरणी फेरबदल
और यह हल है या नहीं यह देखने के लिए जाँच करें।
और जैसा कि आप शायद imagine-- कर सकते हैं आप एक स्थिति की कल्पना कर सकते हैं
जहां सबसे ज्यादा मामले में, कि इच्छा वास्तव में सरणी के साथ शुरू करते हैं कभी नहीं।
एल्गोरिथ्म है कि हमेशा के लिए चला जाएगा।
और इतना है कि एक होगा अनंत समय एल्गोरिथ्म।
उम्मीद है कि आप लिख नहीं की जाएगी किसी भी भाज्य या अनंत समय
CS50 में एल्गोरिदम।
>> तो, चलो ले चलो एक छोटे से अधिक कुछ सरल पर ठोस नज़र
कम्प्यूटेशनल जटिलता वर्गों।
इसलिए हम एक example-- है या दो उदाहरण here--
लगातार समय एल्गोरिदम के, जो हमेशा के लिए ले
सबसे ज्यादा मामले में एक ही आपरेशन।
पहले example-- तो हम एक समारोह है
आप के लिए 4 कहा जाता है जो आकार 1,000 के एक सरणी लेता है।
लेकिन तब जाहिरा तौर पर वास्तव में नहीं लगती है
it-- वास्तव में क्या परवाह नहीं करता पर , इसके अंदर उस सरणी की।
हमेशा सिर्फ चार रिटर्न।
तो, कि एल्गोरिथ्म, यह है कि इस तथ्य के बावजूद
1,000 तत्व नहीं है लेता है उनके साथ कुछ भी कर।
बस चार रिटर्न।
यह हमेशा एक ही कदम है।
>> वास्तव में, 2 nums-- जो जोड़ने हम के रूप में well-- पहले देखा है
सिर्फ दो पूर्णांकों प्रक्रियाओं।
यह एक भी कदम नहीं है।
यह वास्तव में एक दो कदम है।
आप एक मिलता है, तुम ख मिलता है, तो आप उन्हें जोड़ने एक साथ, और तुम उत्पादन का परिणाम है।
तो यह 84 कदम है।
लेकिन यह हमेशा स्थिर है की परवाह किए बिना एक या बी की।
आप एक पाने के लिए है, ख मिलता है, जोड़ने उन्हें एक साथ, उत्पादन परिणाम।
तो यह है कि एक निरंतर समय एल्गोरिथ्म है।
>> यहाँ एक का एक उदाहरण है रैखिक समय algorithm--
कि लेता gets-- कि एक एल्गोरिथ्म एक अतिरिक्त कदम है, संभवतः,
अपने इनपुट 1 से बढ़ता है।
तो, चलो हम देख रहे हैं हम कहते हैं एक सरणी की संख्या 5 के अंदर।
आप एक स्थिति जहां हो सकता है आप के लिए यह काफी जल्दी मिल सकता है।
लेकिन आप यह भी हो सकता था एक स्थिति जहां यह
सरणी के अंतिम तत्व हो सकता है।
आकार 5 की एक सरणी, यदि में हम नंबर 5 के लिए देख रहे हैं।
यह 5 कदम उठाएगी।
और वास्तव में, यह है कि वहाँ की कल्पना इस सरणी में नहीं 5 कहीं।
हम अभी भी वास्तव में देखने की जरूरत सरणी के हर एक तत्व
निर्धारित करने के लिए या नहीं, 5 है।
>> तो यह है कि जो सबसे ज्यादा मामले में तत्व सरणी में पिछले है
या सब पर मौजूद नहीं है।
हम अभी भी देखने के लिए है n तत्वों के सभी।
और इसलिए इस एल्गोरिथ्म रैखिक समय में चलाता है।
आप से है कि पुष्टि कर सकते हैं कह कर एक छोटा सा Extrapolating,
हम एक 6-तत्व सरणी था और अगर हम नंबर 5 के लिए देख रहे थे
यह 6 कदम ले सकता है।
हम एक 7-तत्व सरणी है और हम नंबर 5 के लिए देख रहे हैं।
यह 7 चरणों में ले सकता है।
हम एक और तत्व को जोड़ने के रूप में हमारे सरणी, यह एक और कदम लेता है।
यही कारण है कि एक रेखीय एल्गोरिथ्म है सबसे खराब स्थिति में।
>> युगल आप के लिए जल्दी सवाल।
क्या runtime-- क्या है सबसे ज्यादा मामले क्रम
कोड के इस विशेष टुकड़ा की?
तो मैं चलता है कि यहां एक 4 पाश जे 0, एम के लिए सभी तरह के बराबर होती है।
और क्या मैं यहाँ देख रहा हूँ, यह है कि लूप के शरीर लगातार समय में चलाता है।
इसलिए शब्दावली प्रयोग है कि हम पहले से ही क्या about-- बात की है
सबसे ज्यादा मामले की जाएगी इस एल्गोरिथ्म के क्रम?
एक दूसरा ले लो।
पाश के भीतरी भाग लगातार समय में चलाता है।
और के बाहरी भाग पाश मीटर बार चलाने के लिए जा रहा है।
तो सबसे ज्यादा मामले क्रम यहां क्या हो रहा है?
आप मीटर के बड़े-ओ लगता था?
तुम सही होगा।
>> कैसे एक दूसरे के बारे में?
हम एक है इस बार एक लूप के अंदर पाश।
हम एक बाहरी पाश है कि शून्य से पी करने के लिए चलाता है।
और हम चलता है कि एक आंतरिक पाश शून्य से पी करने के लिए है, और उस के अंदर,
मैं राज्य शरीर कि पाश निरंतर समय में चलाता है।
तो सबसे ज्यादा मामले क्रम क्या है कोड के इस विशेष टुकड़ा की?
खैर, फिर से, हम एक हैं पी बार चलता है कि बाहरी पाश।
और प्रत्येक time-- चलना कि पाश की, बल्कि।
हम एक आंतरिक पाश यह भी कहा कि पी बार चलाता है।
उस के अंदर और फिर, वहाँ वहाँ लगातार time-- छोटा सा टुकड़ा।
>> हम एक बाहरी पाश है, तो यह है कि जो की है अंदर पी बार चलाता है
एक आंतरिक पाश कि क्या गुना पी चलाता
सबसे ज्यादा मामले क्रम कोड के इस टुकड़ा की?
आप पी के बड़े-ओ चुकता लगता था?
>> मैं डौग लॉयड हूँ।
इस CS50 है।