Transcript for:
समय जटिलता का महत्व और समझ

Hi everyone, आज के इस lecture के अंदर हम सीखने वाले हैं time complexity के बारे में और कैसे time complexity के concepts को हम practical problem solving के अंदर use कर सकते हैं अब आज का जो हमारे lecture है उसमें बिल्कुल फरक नहीं पड़ता बिल्कुल भी language specific हमारे lecture नहीं होने वाला इसके अंदर सारी की सारी discussion हैं वो हम conceptually करेंगे जो हर language के उपर apply करते हैं अब time complexity DSA के अंदर एक ऐसा concept है जो हमें बहुत जादा confuse करता है क्यूं? क्योंकि इसके अंदर हम बहुत सारी theoretical चीजें पढ़ लेते हैं, पर जब हम actually problems को solve करने जाते हैं, तो हमें समझ में नहीं आता कि कैसे वो सारी theory, हमारी problem solving के अंदर fit in करती है, तो वही चीज अच्छली आज के session के अंदर हम सीखने वाले हैं, तो first part के अंदर पहले हम time complexity का एक तरीके से revision करेंगे, तो अगर आपको already time complexity के बारे में आता है, अगर आपने आज तक time complexity के बारे में नहीं सीखा है, तो भी इस revision को हम देख सकते हैं ताकि हम जान सके कि time complexity actually work कैसे करती है जब भी हम algorithms की बात करते हैं and फिर second section के अंदर हम जान रहे होंगे कि कैसे जो हमारी TC की knowledge है वो हमें help करती है जब हम problems को solve करने जाते हैं क्योंकि कई बार जब हमें कोई question दिया जाता है solve करने के लिए तो उसके अंदर constraints को देख कर हम actually guess कर सकते हैं कि इस question की expected time complexity या इस question का expected solution क्या होने वाला है तो सबसे पहले start करते हैं अपने revision के साथ हम बात करेंगे कि time complexity exactly होती क्या है, अब time complexity के अंदर time word आता है, तो कई बार students यहाँ पे guess करते हैं, कि क्या पता जो हम code लिखते हैं, जो हम algorithm लिखते हैं, क्या पता यह उसका run time है, time complexity का मतलब, but यह actually बहुत गलत guess है, time complexity, I can write it here, time complexity is not equal to the actual time taken by the algorithm, यानि हो सकता है कि आपने कोई simple सा code है, वो कोई for loop भी हो सकता है, वो कुछ भी हो सकता है वही simple सा code, अगर आप lead code के ऊपर submit करेंगे और वही code जाकर आप code forces के ऊपर submit करेंगे या किसी और platform के ऊपर submit करेंगे तो same algorithm के लिए, same code के लिए आपको different execution time मिल सकता है इसके अलावा, हो सकता है कि same code आप किसी Mac machine के अंदर run करें और same code किसी Windows machine के अंदर run करें और same code को किसी Linux machine के अंदर run करें तब भी हो सकता है उस same code and same algorithm के लिए आपको different run time मिले, तो कहने का मतलब यह है कि जब भी हम time complexity की बात करते हैं, हम actual time taken की बात नहीं करते हैं, यानि हम यह बात नहीं करते हैं कि एक second लगेगा, या 100 milliseconds लगेगे, या 400 milliseconds लगेगे, या 500 milliseconds लगेगे, हम एक relation की बात करते हैं, हम एक behavior पर सबसे पहले तो एक clarity होनी चाहिए कि हो सकता है आपके और आपके दोस्त ने same code लिखा हो पर different machines पर run करें या different platforms के उपर जाके run करें तो आपका code different time में execute बिलकुल हो सकता है क्योंकि जो actual run time होता है वो बहुत सारे factors के उपर depend करता है वो इस पर भी depend करता है कि आपके system के क्या वो इस पर भी डिपेंड करता है कि Leetcode ने अलग server configurations रख रखें, Codeforces के अलग configurations हैं और किसी और coding platforms के different configuration हैं, तो हमें different time taken मिल सकता है, तो time complexity exactly है क्या, time complexity एक behavior है, या इसको कह सकते हैं एक function है, basically time complexity हमें बताता है कि कोई भी code है, उसके अंदर जो भी input आ रहा है, मतलब अगर हमने कोई भी simple सा algorithm लिखा हुआ है for example this is my simple algorithm यह एक for loop भी हो सकता है इसके अंदर कोई न कोई input तो आ रहा होगा कोई input हमारा एक array भी हो सकता है यह input हो सकता है कोई map हो यह input हो सकता है कोई string हो यह एक कुछ और input भी हो सकता है जो भी input है उसका size vary कर सकता है यानि अगर हम एक simple array का example लें तो array तो एक single element का भी हो सकता है array पांच elements का भी हो सकता है array दस million elements का भी हो सकता है तो यह जो array का size है, या जो input का size है, वो कैसे इस code के number of operations को बढ़ाएगा, decrease करेगा, कैसे number of operations change होंगे, based upon this input size, so this is the behavior, this is the function, जो हमारे algorithm से निकल के आएगा, कई सारी books के अंदर explanation के लिए इसे ऐसे भी बताया जाता है, कि कैसे input size के बढ़ने पर, हमारे algorithm कितना time लेगी, उसे हम अपनी time complexity कहते हैं, इसके लिए बहुत simple size example लेते हैं, For example, मैंने लिखा एक for loop अपने किसी array के लिए, for loop के अंदर, let's suppose we are starting from the index 0, index 0 से हम अपने array के size n तक जा रहे हैं, और हर बार i++ कर रहे हैं, और हर बार हम क्या print करवाने की कोशिश कर रहे हैं, हम print करवाने की कोशिश कर रहे हैं अपने array का i-th element, यह मैंने simple सा एक for loop लिखा है, अ तो उस time पर मेरे कितने number of operations होंगे, क्योंकि मेरा loop run ही नहीं करेगा, तो number of operations भी नहीं होंगे, तो यहाँ पे 0 by 0 का एक मुझे point मिलेगा, कि जब मेरा input size 0 है, तब मेरे number of operations भी 0 हो सकते हैं किसी एक particular code के अंदर, या 0 नहीं, तो हो सकता है किसी case में हमारे पास simple एक ही operation perform हो, दो ह तो overall मेरा ये loop कितनी बार run करेगा, मेरा loop भी करीबन 100 बार run करेगा, तो क्या मैं assume कर सकती हूँ, around 100 operations को हम perform कर रहे होंगे, तो यहाँ पे जब मेरा input size, let's suppose यहाँ पे 100 आता है, तो यहाँ पे करीबन 100 operations को हम perform करेंगे, तो मेरा next जो point आएगा, वो मेरे graph में कुछ यहाँ पे द तो हो सकता है मेरा 10,000 कुछ यहाँ पर lie करता हो, अब यह बिल्कुल scale वाला graph नहीं है, बहुत assumption के साथ चीज़ें चल रही हैं, तो यहीं पर करीबन मेरा 10,000 वाला point lie करेगा, और यह meet कहाँ पर होंगे ग्राफ के अंदर, यह कुछ यहाँ पर meet हो रहे होंगे, उसके बाद हो स तो ये क्या है, ये points क्या है, ये points behavior को represent करते हैं, और जब इन सारे points को मिला के हम एक straight line ले कर जाते हैं, तो ये क्या होता है, this behavior, this function is actually my time complexity, this is a representation of my time complexity, कि कैसे input size increase हुआ, तो मेरे इस particular code के number of operations किस proportion में increase हुए, किस behavior के साथ increase हुए, और ये जो behavior है, यह मेरा एक linear behavior कहलाता है, यह एक particular time complexity है, जिसको हम linear time complexity कहते हैं, और इसको हम generally represent करते हैं big of n के साथ, तो कई बार आपने big of n के time complexity देखी होगी, उसी time complexity का अगर graph बनाया जाए, तो इस तरीके की एक straight line उपर की तरफ जाती हुई हमें दिखाई देती है, और यह जो graph है, mathematically, this is a graph of तो यहाँ से हमारा concept निकल के आता है time complexity का, कि कैसे input size के बढ़ने के साथ हमारे number of operations increase होते हैं, अब जब भी हम time complexity को लिखना चाहते हैं, यहाँ पे जैसे मैंने big O लिखा, तो time complexity को लिखने के अलग-अलग तरीके होते हैं, इन सारे तरीकों को हम notations कहते हैं, if I write it here, हमारे पास different हमारे लिए यह important नहीं है, practically सबसे ज़ादा जो important notation होती है, that is called big O, because it's literally a big O, big O notation बताता है कि हमारा worst case क्या होगा, मतलब हमारी worst case time complexity क्या होने वादी है, अब यहाँ पे सबसे पहला सवाल दिमाग में आ सकते है कि notation क्या होती है, notation is basically a symbol, किसी चीज़ को दिखाने का तरीका, मैं क मैं कैसे दिखाऊं कि मेरे पास एक रुपी है, तो मैं क्या करूँगी, रुपी notation को use करूँगी, तो notation कुछ नहीं होता, notation बस एक symbol होता है, चीज को दिखाने का तरीका होता है, और ऐसे ही time complexity के लिए, हमारे पास different different notations है, अब इसमें सबसे important notation हमारे पास big O आ गई है, और big O notation is important क्यूं, क्यूंकि हमारे लिए worst case scenario, यानि सबसे बड़ी value ही सबसे important होती है, मैं एक तरफ आपको दू 10 रुपी, आपके लिए रख दिये 10 करोड रुपे, तो कौन सी value सबसे ज़ादा important हो जाएगी, obviously जो value size में बड़ी है, वो सबसे ज़ादा important हो जाएगी हमारे लिए, इस point of discussion के लिए, तो वैसे ही जब भी हम worst case time complexity की बात करते हैं, तो big O notation सबसे बड़ी value हमें देता है, एक website है, जिसके उपर 10 users आते हैं, एक बिल्यन यूजर जाते हैं या टेन मिलियन यूजर जाते हैं तो कौन सी वेबसाइट ज्यादा स्टेबल होगी ऑफिस यह सेकंड वाली वेबसाइट ज्यादा स्टेबल होगी क्योंकि ज्यादा लोड ले सकती है इससे ज्यादा स्केलिबल बनाया गया है ज्यादा यूज हम हमेशा इस तरीके से अपने systems को बनाते हैं कि हमारे पास 10 million users आएंगे, हमारे पास 1 billion users आएंगे, वो actually strong systems होते हैं, तो यहाँ पे time complexity role ऐसे play करता है कि जिन भी algorithms को हम use करें, वो ठीक है best case scenario में तो work कर जाएंगी, average में भी work कर जाएंगी, पर क्या वो worst case scenario को withstand कर पाएंगी, तो तो हमसे generally big O time complexity पूछी जाती है और जब भी हमें अपनी algorithm की time complexity calculate करनी होती है हम किसी coding test के अंदर बैठे हैं तब भी हम big O को ही calculate करते हैं because practically this is used the most तो हम इसी को लेकर, मतलब big O को ही base बनाके अपने आगे के सारे discussions कर रहे होंगे अब अभी हमने जाना कि हमारा जो input and operation के बीच का function है जो relation है, उसी को हम अपनी time complexity कहते हैं तो basically time complexity can be any mathematical function math के अंदर function कोई भी value ले सकते हैं math के अगर बात करें तो math के अंदर हम generally देखते थे fx is equal to अगर मैंने n square लिख दिया ये क्या है ये एक function है अगर मैंने लिख दिया fx is equal to 5n cube plus 2 to the power n ये क्या है ये एक function है तो math का कोई भी function time complexity बन सकता है पर generally अगर हमारे पास बहुत सारे expressions आ जाते हैं तो हम इन में से हमेशा सबसे बड़ा expression लेते हैं, तो यही reason है कि जब भी time complexity measure की जाती है, हम constants को ignore कर देते हैं, और सबसे worst value को हम लेके आते हैं, क्यों? क्योंकि हमें हमेशा worst case scenario को ध्यान में रखना है, तो उसमें for example, अगर मुझे एक time complexity दी जाती है, मेरे पास एक time complexity है, big of n cube, या इसे 5 n cube plus 2 n square plus 52, इस तरीके कि अगर मुझे time complexity दी जाती है, तो सबसे पहले तो हम क्या करेंगे, constants को अटाएंगे, क्योंकि जब हम 1 billion, 10 million, इतनी बड़ी values के बारे में सोच रहे हैं, तो ये छोटे-छोटे constants, हमारी overall time complexity पे कोई change नहीं लाने वाले, इसलिए हम हमेशा constants को ignore कर देते हैं, हमारे पास जितनी भी different-different values हैं, हम उनमें से worst value निकालते हैं, अब n cube, practically हमेशा n square से बड़ा होगा और n square हमेशा इस value से बड़ा होगा तो क्या मैं कह सकती हूँ इस n square को और इस चीज़ को हम completely ignore कर सकते हैं हमारी जो overall time complexity आएगी that is going to be big of n cube तो जब भी हमें time complexity का इस तरीके का सवाल दिया जाता है उसके अंदर constants को ignore करना है छोटी values को ignore करना है और हमेशा बड़ी value के उपर focus करना है क्योंकि वही हमारी overall time complexity है उनके दिमाग में doubt आता है कि जब भी हम time complexity को सीखते हैं, हमें ऐसे से काफी सारे formula दिखाई जाते हैं, तो क्या मुझे भी अपने code के लिए ऐसे formula लिखने होंगे, तो इसका जवाब है बिलकुल भी नहीं, यानि अगर आपने DSA के 50 to 70 questions कर लिए और आपको already time complexity की knowledge है, तो एक मुझे कोई calculation नहीं करनी पड़ रही, कोई operations नहीं करने पड़ रहे, देखने के लिए, कि मेरा यह जो loop है, यह big of n का है, क्योंकि n times run करेगा, तो जब हम enough number of questions solve कर लेते हैं, तो आपके लिए भी एक point ऐसा आएगा, जब आप literally अपने code को देखकर बता पाएंगे, कि इसकी running time complexity क हम इस तरीके की equations को देख रहे हों, इस तरीके की equations को solve कर रहे हों, पर practically interviews के अंदर बैठ कर कोई इतनी बड़ी-बड़ी equations को solve नहीं कर रहा होता, generally हम एक अंदाजा लगा के अपनी time complexity को solve कर सकते हैं, but वो phase हमारा तब आएगा जब हम enough number of questions को solve कर लेंगे, अब अपने पुराने discussion पे आ जाते हैं, हमने बात कर ली कि time complexity is basically a function, अब math के अंदर तो function कुछ भी हो सकते हैं, इसका मतलब time complexity भी कुछ भी हो सकती है, infinite number of values हैं जो time complexity के लिए आ सकती हैं, पर practically कुछ particular values हैं, जो हमें जादा देखने को मिलती हैं time complexity के अंदर, तो हम एक-एक करके उन particular values को और detail में समझने वाले हैं, अब हमने बात की थी कि time complexity is actually a function, तो function की तो कोई भी values हो सकती हैं, infinite number of values हो सकती हैं, जो एक math वाले function की हो सकती हैं, वैसे ही time complexity की भी infinite number of values हो सकती हैं, depending upon कि हमने क्या algorithm लिखा हुआ है, but practically जब हम DSA के सवाल solve करने जाते हैं, कुछ particular values ऐसी होती हैं, जैसे big of 1 हो गया, big of n हो गया, big of log n हो गया, जो हमें बार-बार-बार-बार देखने को मिलती हैं, तो अगर इन time complexities की values को हम अच्छे से समझ जाते हैं, तो हमारे लिए बाकी algorithms की complexity values को calculate करना बहुत असान हो जाता है, तो हम क्या करेंगे, इन ही values को एक-एक करके detail में समझेंगे, तो common complexities काफी common complexity मिलती है, which is constant time complexity, अब हमने पहली बात की थी कि constants को हम ignore करते हैं, पर एक constant, अकेला constant ऐसा, जिसे हम ignore नहीं करते, that is big of 1, यानि ये 1 वाला constant, constant time complexity कहने का मतलब है कि आपका input size चाहे कुछ भी हो, आपके number of operations algorithm में उतने ही लगेंगे, जिसे for example आपने कोई function बना दिया, इस function के अंदर हम कोई array है जिसको input ले रहे हैं, और code के अंदर, यानि function के अं अब यहाँ पर चाहे हमारे array का size 10 हो, चाहे हमारे array का size 10 million हो, क्या हमारे number of operations बढ़ेंगे, बिल्कुल नहीं बढ़ेंगे, क्योंकि हर बार function को क्या करना है, एक ए operation perform करना है, which is to print hello world, तो यह क्या हो गई, यह constant time complexity हो गई, कि आपके array के size के उपर, आपके number of operations depend नहीं करते, number of operations constant रहेंगे, constant time complexity का, जब भी हम generally graph plot करने जाते हैं, तो उसका graph एक straight line होता है, यानि इस तरीके का graph is constant time complexity, this is bigger of 1, यह थोड़ा सा vertically उपर भी हो सकता है, नीचे भी हो सकता है, depending upon what are the number of constant operations, but generally जब भी आपको straight line दिखे, that is a constant time complexity, अब practically constant time complexity हमें कहां देखने को मिलती है, जब भी हम किसी array की बात करें, अगर मुझे array के अंदर पता है, कि मुझे किसी particular index पे जाके value को access करना है, तो मुझे already index पता है, मुझे already array का नाम पता है, तो क्या मैं कह सकती हूँ, यह constant यानि big of 1 का operation है, क्योंकि सारी चीज़ें already पता है, बस उस address पे जाना है और value को लेके आना है, तो चाहे array का size 10 हो, चाहे array का size 10 million हो, अगर मैं 0th index या first index पे जाके value को access करना चाहिए हूँ, तो that is a Second time complexity, जिसको हम already देख चुके हैं, that is big O of n. Big O of n का graph हम already draw करके देख चुके हैं, कि इस तरीके की, अगर straight line निकलती है, तो इसे हम big O of n कह देते हैं. जहांपे जैसे-जैसे हमारा input size increase हो रहा है, वैसे-वैसे हमारे number of operations increase हो रहे हैं. अब linear time complexity हमें कहां देखने को मिलती है, जैसे हमने एक example देखा, जैसे हम सारे के सारे area elements को print करने के लिए, string के सारे characters को print करने के लिए एक loop लगाते हैं. तो जैसे जैसे string का size बढ़ेगा या array का size बढ़ेगा वैसे वैसे मेरे number of operations भी increase होगे तो ये हमारा linear time complexity होगी linear time complexity हमें linear search के अंदर भी देखने को मिलती है जैसे अगर मेरे पास एक array है और array के अंदर मुझे किसी particular index पे जाके for example I have some values और मुझे किसी value 3 को जाके ढूनना है तो मेरी जो final time complexity आएगी that will be linear time complexity क्योंकि अगर मैं सारे index पे जा रही हूँ तो worst case में मैं पूरे के पूरे array को traverse कर रही हूँ और अगर मेरे array का size यहाँ पर 5 के equal है तो अगर 5 size का input है तो मतलब मैंने 5 operations लगाए अगर 1 million मेरे array का size होगा तो मतलब मैं 1 million operations लगा रही हूँगी और इनका graph कैसा दिखेगा इनका graph generally एक straight line मुझे दिखाई देगा so this is called linear time complexity अब अगर मेरे पास कोई भी ऐसा code होता है जिसमें एक तो मैंने loop लगा रखा है एक जगे मैंने big of n का loop लगा रखा है और दूसरी जगे मैं कोई constant operation perform कर रही हूँ कुछ भी normal value print करने का तो क्या मैं कह सकती हूँ कि मेरे लिए यहाँ पर मैं इस constant value को ignore कर दूँगी जब भी मैं final time complexity क्योंकि हमारे लिए worst case क्या है worst case यह है कि यह loop बड़ा होगा constant तो हमेशा constant ही रहेगा तो जब हमारे पास multiple time complexities होती हैं एक single code के अंदर तब हम छोटी complexities को ignore कर दें हैं, और हमेशा सबसे बड़ी वाली complexity को लेते हैं, और दोनों cases में हमें कैसे पता चलेगा, बड़े वाली complexity कौन सी है, हम n के लिए value assume कर लेते हैं, बहुत बड़ी, यानि कोई बड़ी सी value assume कर लो, 10 to the power 6, 10 to the power 7, काफी 10 million, 1 billion, इस तरीके की बड़ी value assume कर लो, हम n को कभी भी छोटा assume नहीं करते, n is equal to 1, n is equal to 5, ऐसे करके time complexity कभी calculate नहीं करनी, n को हमेशा बड़ा imagine करना है, तो यहाँ पे n जब बड़ा होगा, तो मतलब यहाँ पे तो 1 billion हो जाएगा n, और 1 हमेशा 1 ही रहेगा, तो मतलब यह वाली time complexity बड़ी है, as compared to this time complexity, और जैसे time complexity बड़ी होती जाती है, वैसे time complexity खराब होती जाती है, क्योंकि जितनी भी बड़ी time complexity है, मतलब बड़े input size के लिए code जादा time लेगा, जितना जादा time लेगा code, उतना जादा वो कम efficient है, तो बड़ी time complexity का मतलब होता है, खराब time complexity, किसी भी case में big of 1 वाला code हमेशा better होगा big of n वाले code से, इसके बाद next आ जाते हैं अपनी big of n square वाली time complexity पर, big of n square को generally हम quadratic time complexity कहते हैं big of n square generally हमें nested loops के अंदर मिलता है, मतलब मैंने एक for loop लगा दिया और for loop के अंदर मैंने एक और for loop nesting के अंदर generally दो बार loop run करता है और दोनों बार अगर n time run कर रहा है तो हमारे पास n square time complexity आ जाती है या फिर अगर हम किसी matrix का भी example लें, मुझे अगर कोई 2D array दिया हुआ है, जिसके अंदर इस तरीके से, मेरा size है, let's suppose I have created an array of n by n, तो अगर इस 2D array को, या इस matrix को, मुझे पूरा traverse करना है, तो पहले n time करेंगे, फिर दुबारा n time करेंगे, फिर यहाँ पर भी n time, यहाँ पर तो जब भी किसी matrix को मुझे पूरा का पूरा travel करना होता है, तो वहाँ पर complexity आती है big of n square के equal, या फिर nested loops के अंदर आती है complexity big of n square के equal, अब मेरी जो big of n square वाली time complexity है, generally उसे represent करने के लिए हम कुछ इस तरीके का graph बना सकते हैं, this is big of n square, तो जैसे जैसे graph में हम उपर की तरफ जाते जाते हैं, हमारी time complexity खराब होती जाती है, linear है, मतलब थोड़ा सा कम अच्छा है, और n square है, मतलब हम खराब complexity की तरफ जाते जा रहे हैं, fourth common time complexity, जो हमें कई बार देखने को मिलती है, that is log n, अब log n देखके बहुत सारे students घबरा जाते हैं, कि log क्या आ गया, हमने तो math के अंदर पढ़ा था, logarithm, हम तो coding करने आये थे, but if I tell you genuinely, log n is your friend, क्योंकि log n बहुत अच्छी time complexity होती है, जब भी हम practically algorithms लिखने जाते हैं, लॉग इन वाली time complexity बहुत अच्छी होती है as compared to linear time complexity इसलिए जब भी आपके code में हमें login की time complexity दिखे या अगर हम n से login में convert कर पा रहे हैं तो मतलब हमारा code बहुत सुन्दर होता जा रहा है अब login का exactly मतलब क्या होता है time complexity की terms में अब login वाली time complexity generally हमें देखने को मिलती है binary search के अंदर जब भी हम binary search कर रहे होते हैं, for example, we have created this array, और इस array के अंदर बहुत सारे different different number of elements हैं, और मुझे binary search करके 5 को find out करना है, तो binary search कैसे काम करता है, हम अपने sorted array के अंदर पहले mid निकाल लेंगे, फिर देखेंगे जिस भी target को मुझे find out करना है, क्या ये मेरे mid से बड़ा है, या छोट तो एक ही iteration में मेरा input size half हो गया, तो इस पूरे array को अब हम ignore कर सकते हैं, अब second half में आ जाते हैं, second half में mid निकालेंगे, let's suppose हमारा mid 4 आता है, अब दुबारा से 4 को 5 से compare करेंगे, तो मुझे पता चलेगा कि मेरे 4 से बड़ा है मेरा target, तो यहाँ पर भी इस array के अंदर हम left part को completely हटा देंगे, तो दुबारा से मेरा input size half हो गया, और finally इसे अगर हमने हटा दिया, तो हम इस last array से जब हम अपने target को compare करेंगे, और यहाँ पर हमारा binary search complete हो गया, तो binary search कैसे काम करता है कि हर एक iteration के अंदर हम अपने input size को half करते चले जाते हैं, it basically means कि अगर हमने एक array के साथ start किया और array के अंदर अभी array का size है 100 के equal, तो next iteration में array का size होगा वो 50 हो जाएगा, उससे अगले iteration में array का size 25 हो जाएगा, उससे अगले iteration में n का size 12 हो जाएगा और इस तर तो इस तरीके से हमारे जो input size है हर बार half होता चला जाता है, अब यहां से log का क्या connection है, binary search के अंदर log time complexity समझने के लिए हमें थोड़ा सा यहां पे math करना पड़ता है, math के अंदर basically हम नीचे की तरफ जाने की बजाए उपर की तरफ सोचते हैं, उपर की तरफ सोचते हैं मतलब, तो basically वन को क्या कर रहे हैं हम हर बार double कर रहे हैं, वन को double किया तो 2 आ गया, 2 को double किया तो next time हमारे पास क्या आ जाएगा, 4 आ जाएगा, 4 को double करेंगे 8 आ जाएगा, 8 को double करेंगे 16 आ जाएगा, तो binary search में वैसे तो half होता था, पर क्योंकि हम नीचे से उपर की तरफ जा रहे है let's suppose हमने इसे x times 2 से multiply किया, x times 2 से multiply करने का मतलब होता है कि 2 to the power x हम ले आएं, तो जब 1 को 2 to the power x से हम multiply करेंगे, तो final result क्या आना चाहिए, final result हमारे पास 100 आना चाहिए, तो यहां से हमारे पास relation निकल के आता है, 2 to the power x is equal to 100, और x की value अगर हमें निकालनी है, तो math के अंदर हम log और यहाँ पे यह hundred क्या था, यहाँ पे यह hundred मेरे array का size था, यानि n था, तो basically हम कह सकते हैं x is equal to log n, यहाँ पे base को ignore कर देते हैं, x is equal to log n, और x क्या था, x मेरे number of operations थे, जो मुझे सारे operations अपने binary search के अंदर लगाने पड़ेंगे, तो basically number of operations क्या निकल के आते हैं, x क्या है, x is equal to तो binary search में जब हम log n लिखते हैं, उसका मतलब यह होता है कि हर बार जब हमारा array का size half होता चला जाएगा, तो उस case में क्या worst case time complexity आएगी, worst case time complexity will be log n, मतलब worst case में log n number of operations को हम perform कर रहे होंगे, अब वैसे time complexity करने के लिए इससे ज़्यादा हमें log का math सीखने की ज़रूरत नहीं है, तो थोड़ा सा हम rewind करके lecture का ये part देख सकते हैं बाकि ये जो calculation है ये generally interview में आपसे नहीं पूछी जाएगी आपसे final time complexity ही पूछी जाती है तो हम चाहें तो यहाँ पर याद भी रख सकते हैं कि हमारी binary search की time complexity हमेशा login होती है in fact अगर हम balanced BSTs की भी बात करते हैं जब हमारे पास कोई balanced BST होता है जब हम उनके अंदर भी search की time complexity निकालते हैं तो वो भी हमारे पास login के equal निकल के आती है अब graphs के अंदर log n वाली time complexity कहां आती है graph के अंदर generally log n वाली time complexity कुछ यहां निकल के आती है मतलब this is big of log n और अगर हम compare करें linear से बहुत ज़्यादा better है हमारी log n time complexity काफी करीब होती है हमारी constant time complexity के लिए तो इसलिए log n वाला code बहुत अच्छा होता है as compared to a linear code यानि अगर मैं लिखूं कि मेरे code की time complexity log n के equal है, this is much much better than, ये greater than greater than का sign नहीं है, ये better का sign है, this is much better than big of n, और वैसे ही अगर मैं लिखूं कि मेरे code की time complexity n log n के equal है, this is much better than having a complexity which is n square, तो ये वाला code बहुत better होगा, and ये वाला code भी बहुत better होगा, as compared to these codes, अब next जो common time complexity हमें देखने को मिलती है, that is n login, n login generally कहां दिखती है, generally हमें sorting के अंदर दिखती है, maximum cases में, जहां भी sorting हो रही होती है, वहां n login की ही time complexity हो रही होती है, चाहे आप inbuilt sort को use करो, c++ के अंदर, हमारे पास sorting के already inbuilt functions होते हैं, उनकी भी time complexity हमें यही assume करनी होती है, या अगर हम खुद से merge sort लिखें तो भी हमारे पास time complexity यही निकल कर आएगी उसके बाद एक और common जो time complexity हमें देखने को मिलती है that is exponential time complexity exponential time complexity का मतलब है कि यहां किसी ना किसी तरीके से generally यह कहां देखने को मिलती है generally यह recursion में देखने को मिलती है जहां पे भी recursion हो रहा है और हमारे एक decision tree बनता है जब भी recursion होता है एक decision tree बनता है कि हम अभी यहां पे कड़े थे recursion में हमारे पास दो choices हैं यह समझने के लिए हमें already recursion आना चाहिए coding के अंदर तो हमारे पास recursion है, recursion में let's suppose हम दो direction में जा सकते हैं, अब यहां से भी हम क्या कर सकते हैं, यहां से भी हम दो direction में जा सकते हैं, यहां से भी हम दो direction में जा सकते हैं, यहां से भी हम दो direction में जा सकते हैं, तो recursion के अंदर एक node से जितनी number of branches निकलती हैं, वो तो हमारी exponential time complexity का base हो मतलब ये generally brute force होती है, तो अगर इसे मैं graph पे दिखाओं, तो graph पे generally exponential time complexity कुछ यहाँ पर आईगी, मतलब big of 2 to the power n कुछ यहाँ पर आईगा, which is way worse than n square, मतलब n cube कुछ यहाँ पर आईगा, n to the power 4 यहाँ पर आईगा, और 2 to the power n काफी खराब time complexity होती है, अब क्योंकि brute force recursion की time complexity exponential होती है, तो इसी लिए हम generally dynamic, programming को use करते हैं इस time complexity को better करने के लिए तो हम memoization का use करते हैं हम tabulation का use करते हैं वो सब क्यों use किया जाते हैं वो सारी जो techniques है dynamic programming अपने आप में जो एक technique है वो इसलिए use की जाती है ताकि इस खराब time complexity को हम सुधार सकें और उसे और जादा better कर सकें इसलिए tabulation में कई बार time complexity हम n square तक लाने की कोशिश करते हैं या कुछ-कुछ cases में हम linear तक 2 to the power n हो गया पर अगर कहीं पर आपको दिखाई दे 3 to the power n, 4 to the power n ये सारी की सारी exponential time complexities की ही category के अंदर आती हैं तो जहां पर भी हम इस तरीके की values देखें this is my exponential time complexity अच्छा इसके अलावा एक और special time complexity होती है जो हमें उतना जादा देखने को नहीं मिलती which is n factorial now n factorial is the worst of them all मतलब n factorial ग्राफ में कुछ यहाँ पर मुझे दिखाई देगी ये exponential से भी खराब होती है कैसे पता चले, exponential से भी खराब होती है, उसके लिए हम एक example ले लेते हैं, let's remove all of it, let's suppose एक है हमारे part time complexity 2 to the power n, इसमें हम n is equal to 4 ले लेते हैं, तो यह क्या होगा, यह होगा 2 into 2 into 2 into 2, मतलब 2 to the power 4, और दूसरी time complexity है n factorial, इसमें n को 4 ले लेते हैं, तो यह क्या हो जाएगा, यह हो यह जो value है, यह छोटी होगी as compared to this value, क्योंकि इसके अंदर 4, 3, 2, मतलब काफी बड़े numbers हैं जो multiply हो रहे हैं, तो इसलिए n factorial, जब हम बड़े n के लिए consider करते हैं, तो एक worst time complexity होती है as compared to an exponential time complexity, अब n factorial time complexity कहां देखने को मिलती है, generally अगर आप permutation calculate कर रहे हैं, अगर आप brute force method से सारे possible permutation calculate करेंगे, तो उस case में हमें n factorial लग सकता है, तो वहां n factorial, मतलब एक काफी खराब time complexity हमारे पास आती है, तो अगर हमारे पास, इन 5-6 time complexities की, अगर एक ठीक understanding है, तो most of the practical cases के अंदर, हमारे लिए time complexity calculate करना easy हो जाएगा, और एक graph देख लेते हैं, इन सारी चीज़ों को summarize करते हुए, तो ये मेरा input size है, यहाँ पे number of computations है, computations यानि number of operations, तो basically यहाँ पे मेरी constant time complexity आती है, फिर मेरी logarithmic time complexity आती है, फिर हमारे पास linear आती है, फिर n login आ जाती है, n square आ जाती है फिर जो n cube होती है या n to the power 4 होती है generally n to the power 4 या n to the power 5 ऐसी time complexities हमें practically उतना देखने को नहीं मिलती पर ये सारी ग्राफ के अंदर यहाँ पर plot होती है उसके बाद exponential में हम कुछ यहाँ पर आ जाते है और फिर worse जो होती है which is n factorial वो हमें हाँ इससे भी खराब हो सकते है time complexities पर वो practical cases में हमें उतना जाता देखने को नहीं मिलती है अब ये तो हो गई हमारी सारी time complexity की knowledge, मतलब time complexity के हमने concepts को बढ़ लिया, कैसे calculate करते हैं, वो सारी चीज़ें कर लिये, पर इस knowledge को कैसे हम practically questions को solve करते time use कर सकते हैं, मतलब अगर मैं lead code पे questions को solve करने जा रही हूँ, या मैं code forces पे questions को solve करने जा रही हूँ, तो कैसे इस knowledge को हम problem solving की time उसके बारे में हम बात करने वाले हैं, अब problem solving की अगर हम बात करें, तो generally हमारे पास different different platforms होते हैं, आप में से कोई student हो सकता है, hacker earth के उपर जाके code कर रहा हो, कोई student हो सकता है, lead code पे code कर रहा हो, कोई student हो सकता है, code forces, code chef के उपर जाके code कर रहा हो, पर generally for most of the platforms हम assume करते हैं कि एक second के अंदर generally around 10 to the power 8 operations perform हो सकते हैं, यह हमें assumption लेके चलनी होती है, कि 10 to the power 8 operations होने में generally एक second का time लगता है, और हमें assume करके चलना होता है, कि हमारी जो generally time limit दी जाती है, the time limit that is given to us, that is around one second, कि एक सवाल को हमारे जो run time लगना चाहिए, हमारे code को, that should be equal to one second in the worst case scenario, इसका मतलब है, कोई भी code अगर हम लिखेंगे, तो उसमें at most, worst case scenario में, हमारा जो code है, उसके अंदर कितने operations perform हो सकते हैं, उसके अंदर 10 to the power 8 operations perform हो सकते हैं, क्यों, क्योंकि हमें 1 secondy allowed है, यह हमें assume करके चलना होता है, and maximum platforms के उपर आप देखोगे, कि यह चीज़ completely hold करती है, अब मुझे पता चल गया, मेरा जो code है, या मेरी जो algorithm है, जिसे मैं लिखने वाली हूँ, चाहे वो easy level question हो, medium level question हो, hard level question हो, मेरा जो code है, worst case scenario में, उसमें 10 to the power 8 operations perform होने चाहिए, तो generally हर question के नीचे, कुछ-कुछ constraints दिये जाते हैं, इसका एक हम example ले लेते हैं, अब let's suppose हम lead code पर गए, और यह greedy का एक काफी classical question है, इसको हमने खोल लिया, तो यहाँ पर इस question के अंदर मुझे तीन arrays दिये हुए हैं, start time, end time and profit, अब तीनो arrays के लिए last में, generally हर बार questions के last में हमें कुछ constraints दिये जाते हैं, और अगर interview में आपको directly constraints नह तो यहाँ पे array के जो constraints हैं, उसमें दिया हुआ है कि maximum size array का जा सकता है 5 into 10 to the power 4, तो basically यहाँ ये मेरे n की largest value हो सकती है, तो कैसे इस n की largest value से हम थोड़ा थोड़ा assumption ले सकते हैं कि हमारे final code की time complexity क्या हो सकती है, तो अपने concepts को एक बार revise करते हैं, हमें already पर रहा है कि हमारे solution में हम तो क्या मैं कह सकती हूँ, अगर मेरे पास एक array है, जिसमें 10 to the power 8 से जादा number of elements है, तो एक-एक करके, मैं अगर इस array को traverse करती हूँ, तो तो क्या होगी, मेरे पास linear time complexity आएगी, पर क्या मेरे code के अंदर linear time complexity हो सकती है, मेरे code के अंदर ये linear time complexity बिलकुल नहीं हो सक तो इसलिए जब भी ये constraint दिया जाता है, मेरी final time complexity should be better than linear, यानि वो यातो log n हो सकती है, या फिर constant time complexity में भी हम जा सकते हैं, basically linear से better होनी चाहिए, depending upon कि कितनी बड़ी n की value हमें दी जा रही है, उसके बाद अगर हमें कभी भी बोला जाता है, कि n की value less than equal to 10 to the power 8 हो दी चाहिए, तो उस case में हम assume कर सकते हैं, कि मेरी worst case time complexity should be linear, हाँ, linear से better हो सकती है, हम चाहें तो constant time complexity में भी अपने सवाल को solve कर सकते हैं, पर linear से खराब में solve नहीं कर सकते हैं, मतलब ये मेरी constraint है, और मैं n square का code लिख दूँ, जिसमें कोई nested loop use हो रहा है, तो उस case मेरा code गलत हो जाएगा, और हमारे पास TLE आ जाएगा, time limit exceeded तभी आता है, तो उस case में हम assume कर सकते हैं कि हमारा जो final code होगा वो n login का हो सकता है, और ऐसे cases में एक और hint हमें मिल जाता है, एक और hint यह मिलता है कि क्योंकि n login allowed है, तो इसका मतलब sorting भी allowed होगी, मतलब अगर मेरे सवाल के अंदर कहीं पर array यूज़ हो रहा है, तो इसका मतलब है हम इस array को sort करक कि अगर मेरे पास कोई array है, और कुछ sorting से related solution है, तो मेरे solution के अंदर sorting बिल्कुल around होगी, और generally ये चीज मुझे greedy problems के अंदर देखने को मिलती है, और जिस problem को अभी हमने discuss किया, that is also a greedy problem, यहाँ पे हम end time के basis पे sort करते हैं, job scheduling का जो problem है, it is a very classical problem, और इसमें भी अगर हम constraints को ध्यान से देखे, n less than equal to, 5 into 10 to the power 4 दिया हुआ है, अब यहाँ पे different different values को fit करके देख लेते हैं, यहाँ पे fit करके देखते हैं, क्या यहाँ पे n square allowed होगा, n square का solution, उसके लिए मुझे क्या करना है, simply इस largest value को, worst case scenario के लिए largest value को square करके देख लो, 5 का square क्या हो जाएगा, 25 हो जाएगा, and this is going to be 10 to the power 8, तो 25 into 10 to the power 8 तो क्या है, 10 to the power 8 से बड़ा है, मतलब ये solution बिलकुल भी accept नहीं होगा, ये गलत solution हो जाएगा, पर वहीं दूसरी तरफ, if I take n login, तो ये मेरा acceptable solution है, और जब भी n login आ रहा है, हम एक बार sorting के बारे में सोच सकते हैं, एक question greedy का है, तो यहाँ पे n login का कोई solution है, हाँ obviously, अगर किसी question में, हम, linear तक भी जा पा रहे हैं, constant solution भी कर पा रहे हैं, तो तो बहुत ही बढ़िया है, फिर हमें वो चीज करनी है, पर worst case को हमने protect कर लिया, कि n square वाला solution यहाँ पे नहीं चलेगा, maximum हम n login की limit को touch कर सकते हैं, तो इस तरीके से time complexity की knowledge हमें कई बार help कर देती है, अपना possible solution guess करने के लिए, उसके अलावा n less than equal to 10 to the power 4 है, तो यहाँ पे n square का solution चल जाएगा, कि n square के solution के लिए क्या होगा, 10 to the power 4 into 2, this is going to be 10 to the power 8, मतलब n square acceptable होगा, पर अगर 10 to the power 4 से कोई भी बड़ा constraint है, जैसे यहाँ पर 10 to the power 4 से एक बड़ा constraint था, तो वहाँ पर n square acceptable नहीं होगा, वहाँ हमें n log in की direction में देखना पड़ेगा, तो अगर आपको कभी भी यह भी दिखता है, n less than 10 to the power 5, तो यहाँ पर भी हम n log in के बारे में सोचेंगे, n less than equal to 500, मतलब जितनी चोटी हमारी n की value जा रही है, उतना बड़ा expected time complexity हम assume कर सकते हैं काफी cases के अंदर, तो n less than equal to 500 के लिए generally n cube वाली type complexity expected हो सकती है, n less than equal to 25 के लिए, यहाँ पे exponential time complexity generally हम expect कर सकते हैं, वो 2 to the power n भी हो सकती है, वो 3 to the power n भी हो सकती है, पर basic यह है exponential time complexity है, और जहाँ भी exponential time complexity expected हो, वहां हम सोच सकते हैं it might be a brute force recursion solution, क्योंकि recursion के अंदर generally exponential हम यह देखने को मिलती है, और ऐसे cases में हम यह सोच सकते हैं कि हमें ज़ादा कुछ optimizations करने की ज़रूरत नहीं है, क्योंकि generally इस सवाल को solve करने के लिए, जो first approach हमारे दिमाग में hit कर रही है, ज़रूरत नहीं है, तो ऐसी जो constraints होते हैं, उस case में brute force solution generally accept हो जाता है, यह हमेशा याद रखना है यह सारी assumptions हैं यह हर एक single case में apply नहीं करेंगी पर यह काफी जगह अपलाई कर जाएंगी और वहाँ पर हमें help मिल रही होगी इसके अलावा एक n less than equal to 12 वाली time complexity होती है इस case में हम assume कर सकते हैं कि n factorial की हमसे assumption है कि कुछ ना कुछ n factorial type time complexity होगी क्योंकि generally n is equal to 12 के लिए n factorial 10 to the power 8 को exceed करता है तो 12 से कम values के लिए n factorial एक valid number of operations हमें करके देगा तो इस तरीके से हम जब भी किसी भी problem को देखें, हम एक उसकी expected time complexity को पहले अपने दिमाग में सोच सकते हैं, उसके बाद expected time complexity से हम एक direction ले सकते हैं, कि कौन-कौन से data structures हैं, जिनको यहाँ पर use किया जा सकता है, कौन-कौन से algorithms हैं, जिनको यहाँ पर use किया जा सकता है, जब भी तो login जब भी हम सोचते हैं, हम एक बार binary search के बारे में ज़रूर सोचेंगे, या अगर हम constant सोच रहे हैं, तो constant के case में हम यह सोच सकते हैं, कि क्या पता यह जो पूरा का पूरा मुझे question दिया हुआ है, इसका solution किसी trick के अंदर छुपा हो, और बिल्कुल एक constant time के अंदर मैं पूरा solution calculate करके निकालूँ, तो इस तरीके से काफी-काफी different जो ideas और different जो thoughts होते हैं, वो हमारे emerge होकर आते हैं, प्लस जब हमारी time complexity की knowledge strong होगी, तो time complexity सिर्फ एक बहुत theoretical चीज नहीं है, जब DSA के सवाल practically हम solve करने जाते हैं, जब CP के सवाल जब हम practically solve करने जाते हैं, तब time complexity की knowledge हमारे बहुत काम आ रही होती है, practical problem solving करते हैं time, तो I hope कि आज का यह session है, इसने time complexity से related कुछ नए concepts आपको सिखाए होंगे, जिनने हम practically जाके अब एक better software engineer हमें बनाने में help करते हैं, तो उस चीज़ को अमेशा याद रखना है, एक learning perspective रखना है, जब भी हम चीज़ों को सीख रहे हैं, सारी चीज़ें theoretical नहीं होती, कहीं ना कहीं उनका practical application जरूर होता है, हो सकता है उस practical application से अभी तक हम नहीं टकराए हूँ, पर वो चीज़ कह