फॉलो भीजिए हमारे फेजबुक पेज को और सब्सक्राइब कीजिए यूटूब चैनल को टेकनिकल सबजेक्ट और टेक न्यूज के वीडियो सबसे पहले पाने के लिए नमस्कार दोस्तों आपका हमारे आना लेक्शर सीरीज में एक बार फिर से बहुत-बहुत स्वागत है आज हम अपने अलगोर्थम के लेक्शर सीरीज में बात करेंगे ग्रोथ आफ फंक्शन एंड एसम्प्रिटिक नोटेशन की अगर एसम्प्रिटिक नोटेशन देखें त जिसका हम use time complexity as well as space complexity को represent करने के लिए हम use कर सकते हैं तो उसी को हम detail out देखेंगे SM2 notation से पहले हम बात करेंगे growth half function की growth half function आप ही हमने previous lecture में हमने देखा कि कई सारे algorithm का time complexity calculate किया तो कुछ का time complexity 1 आया होगा कुछ का n आया होगा आगे हम चलेंगे तो आगे कुछ का complexity n log n आएगा किसी का n square आएगा minimum जो function होगा 1 होगा means या तो space वो या time at least कितना लेगा 1 लेगा 1 से कम means 0 कभी भी नहीं होता ना तो 0 time लेगा ना तो 0 space लेगा किसी भी problem को solve करने के लिए तो सबसे smallest कौन सा है 1 अगर इससे हम आगे चलें तो log n उससे greater होगा root n उससे greater होगा n उसके बाद उससे greater होगा n log n, n से greater होगा n square, n cube ऐसे n power 4, n power 5 ऐसे बढ़ता जाएगा 2 power n, then 2 power n से बढ़ा 3 power n up to 4 power n up to n power n. तो यह जो growth rate है इसी को हम कहते है growth of function और एक एक जो यहाँ पे resultant लिखा हुआ जैसे log n, n, n, log n इसको हम कहते है functions तो function का growth इस तरह से है अब इस function का growth हम use कहां करेंगे वो ज़्यादा बेटर समझ में आएगा जब हम asymptotic notation करेंगे दिन क्योंकि इसका जो growth है वो इसी के carding हम यहाँ पे big O वहां से आएगा कि कहां पर हम फंक्शन का यूज कर रहे हैं एसमी नोटेशन पर आते हैं एसमी नोटेशन क्या है एसमी नोटेशन आर मैथमेटिकल टूल टू रिप्रेजेंट कंप्लेक्सिटी इन द टर्म आफ टाइम एंड स्पेस सिंपली जैसा मैंने कहा कि किसी भी अलगोर्थम को टाइम और स्पेस कंप्लेक्सिटी अगर रिप्रेजेंट करना है डिनोट करना है तो हम इसी एमप्रेटिक टोटेशन से यूज करते हैं टोटल पांच कम ए नोटेशन है हमारे पास सबसे पहला विद्धों जिसको हम कैपिटल वो सिर्फ टेंट करते हैं बिग ओमेगा जिसको हम उनका सिंबल से थीटा थ सिंबल से इसके बाद दो और होते हैं इसमाल वह और इसमाल होंगा हलांकि जो इंपोर्टेंट होते हैं वह इंपोर्टेंट यहीं तीन है इन तरफ जरूरी बहुत कम यूज होता है इसको हम जरूरी रिपरेंट करते तो आपका जितने भी प्रॉब्लम होंगे आगे इस पेस्ट टाइम कंप्यूटी को रिप्रेंट करने के लिए वह सारे इसी तीन से प्रेजेंट होते हैं तो इन तीन को हम डिटेल देखेंगे साथ में इसको भी हम देखेंगे थोड़ा सा कि इसको कैसे हम यूज करते हैं तो इसे अब upper bound क्या होगा, इसी growth function में भी मैं आपको समझाऊंगा, big omega, big omega को हम क्या रिप्रेंट करते हैं, lower bound, एंड थीटा आपका क्या होता है एवरेज बाउंड सपोस्ट कीजिए कि कोई आपका फंक्शन एन है कोई आपका समझ कीजिए फंक्शन एन है तो आप बांड क्या होगा इस केस में इससे ग्रेटर जितने भी फंक्शन है वह सारे क्या हो जाएंगे जैसे इससे ग्रेटर इसको लेकर भी यह से लेकर यहां से लेकर यह सारे जितने फंक्शन है यह सारे हो जाएंगे अपर बांड बिग ओमेगा, ओमेगा क्या होगा, लोवर बाउंड, मतलब अगर आपका function n है, तो इससे including इसको लेके जितने फंक्शन होंगे, ये सारे क्या होंगे, लोवर बाउंड, टाइट बाउंड क्या होगा, एक्जैक्टली, अगर एक्जैक्टली function fn है, तो एक्जैक्टली के लि बाउंड तो डिटेल में चलते हैं बिगो बिगो नोटेशन को बिगो नोटेशन इस साइड आप देख सकते हैं द फंक्शन एफ एन इसको बिगो आप जी जी एन इफ देर इक्जिस्ट पॉजिटिव कंस्टेंट सी एंड एन नोट सच देख एफ एन लेस दन इसको टो सी डॉट जी आफ एन फार ऑल एन वेर एन इस गेटर दन इसको टो एन नोट एंड सीज गेटर दिन जीरो आपको करना क्या है कि किसी फंक्शन का अगर बीगो निकालना है बीगो नोटेशन फाइंड आउट करना है इस कंडीशन को सैटिसफाइड करना होगा वहीं आपका जो जीएन आएगा वह लोग अ बीगो बीगो जीएन जो आएगा यहां पर यही आपका फंक्शन होगा बीगो के साथ में तो कैसे हम करेंगे इसको पहले डायग्राम बनेते हैं सपोस कीजिए कि आपका एक प्रॉब्लम साइज है जिसका एंड एंड साइज प्रॉब्लम साइज और इस रिस्टेक्ट टाइम चलना है टाइम के साथ वह टाइम कंप्रेस्टी की बात कर रहे हैं हम अगर आपको कोई फंक्शन एफ एन है जो कि अगर n की size बढ़ रही है तो time इस तरह से बढ़ रहा है जो आपे fn function compute हो रहा है अगर हम कोई function gn लें जो कि इस direction चला means अगर n की size बढ़ रही है तो t की size इस तरह से बढ़ रही है तो यहाँ पे जो intersection point है यह जो intersection point है यही आपका होता है n not हो अब यह नौक्षित मतलब है समझिए कि इस पॉइंट के बाद हम देखें इस point से पहले तो यहाँ पर Fn वाई line यहाँ जा रही है Gn वाली यहाँ है लेकिन अगर इसके बाद देखें तो Gn हमेशा क्या है greater than Fn है किस value पे N0 यहाँ पे जो N0 intersect किया है यहाँ पे तो इसको represent करने के लिए हम कह सकते हैं Fn is less than is equal to C dot Gn C means कोई constant होगा सब्सक्राइब कोई constant कोई है जिस constant को लेके चल रहा है where C is greater than 0, N is greater than N0, N is greater than N0 means NMSI N0 से greater होगा या equal भी हो सकता है और ये न नॉट जिस गेटर देन जीरो ये न नॉट की वैल्यूज होगी हमेशा जीरो से ग्रेटर होगी तो अगर इस कंडीशन सटिस्फाई करता है तो हम कर सकते हैं ये फ एन इक्कॉल टू बीगो आफ जी एन एक्जाम्पल समझते हैं और इजी हो जाएगा सपोस कोई फ of function भी कर सकते हैं तो हम assume करके चलेंगे g n, g n क्या होगा assume करके चलेंगे, ध्यान दीजिए, assume करने का simple सो तरीका है, कि अगर आपको कोई f n में दिया है, जैसे यहाँ पे 3 n दिया है, तो यहाँ पे अगर order आपको order देखें, इसका कौन सा order है, n का यह order चला है, तो हम g n यहाँ पे n लेके चलेंगे लेस्ट इन इसको टू सी डॉट जी एन फार्मला आपका था अगर हम यहां पर सेट करें इस वैल्यू को तो क्या हो जाएगा थ्री एन प्लस टू लेस्ट इन इसको टू सी डॉट जी एन अब इसकी क्वालिटी फाउंडर के लिए आपको दो चीज आपको आप फाइंड क्या करना है एक तो सी की वैल्यू जैसा आप दिया हुआ सी और एन नॉट दो वैल्यू फाउंड आउट करना है कि जिसके लिए ए हमेशा आपका क्या हो वैल्यू ट्रू करें हमेशा कंडीशन ट्रू हो तो suppose हम c के लिए पहले देखते हैं अगर हम यहाँ पे g n की value एपूट कर लें g n की value क्या है n अगर हम c का देखें c की value 1 रखते हैं तो c की value 1 रखते हैं क्या हो जाएगा 3n plus 2 less than is equal to n c की value 1 हो जाएगा तो केवल n होगा ऐसा possible है condition fail कर जाएगा अगर c की value हम 2 रखें c की value अगर हम 2 रखते हैं यहाँ पे तो 3n प्लस 2 लेस्ट देन 2n कभी नहीं होगा, अगर हम 3 रखते हैं, तो 3n प्लस 2 लेस्ट देन इसकोल टू 3n कभी नहीं होगा, क्योंकि 3n 3n एक्कोल है यहाँ प्लस 2 हो रहा है अधिकनल, तो condition satisfied नहीं होगा, लेकिन अगर हम c की value 4 रखते हैं, c की value 4 रखते हैं, तो maybe condition true कर हो रहा है तब हम जी निकालेंगे n 0 n 0 की value means इस n की value जो n की value put up करना है उसी को n 0 लेकर चलेंगे अगर इसकी value हम starting करें 1 से अगर put कर देते हैं 1 तो condition satisfy होगा अगर हम 1 put करते हैं तो 3n, means 3 plus 2, 5, less than or equal to 4, condition fail, लेकिन अगर हम इसको 2 रखते हैं, 2 रखते हैं, then 3 multiply by 2, 6 plus 2, 8, लेस्ट इसकोल टू फॉर्ड मुल्टिप्लाई बाइट 28 एक तो निशन प्रू है अब थ्री के के लिए भी देख सकते हैं थ्री के लिए चेक करें तो थ्री में भी आपका सटिस्फाइड होगा थ्री थ्री नाइन नाइन थ्री मुल्टिप्लाई बाइट 39 प्लस टू 11 लेस्ट इसकोल टू फॉर्ड मुल्टिप्लाई बाइट रीमेंस टू आपका कंडीशन ट्रू हो जाएगा ऐसे यदि फॉर्ड थ्री फॉर्ड पर रखे पाइप र के लिए condition true हो रहा है, लेकिन जो condition true start होना होगा, closest, closest कौन सी value थी n की, closest value थी आपकी 2, तो हम यहाँ से कह सकते हैं कि, यहाँ से हम कह सकते हैं कि जो यहाँ पे n है, a g of n होगा हमारा, means यहाँ से हम इस तरह से कह सकते हैं कि f n is equal to big O of Big O of n for all c is equal to 4 and n is greater than is equal to 2. कि यह आपका टू हो जाएगा अब इसको यहां भी समझिए थोड़ा रिलेट करेंगे हम कि देखिए यहां पर जो हमने लिया वैलू फॉर एन लिया किस तरह सी और सी के विशाब फाइंड आउट कर लिया अगर हम सपोज यहां पर टेन लिख देते हैं तो टेन पर भी ट्रू करेगा कंडीशन ट्रेन पर देखिए तो यहां पर इनकी वैलू वन पेशाइज टू कर जाए अ ठीक है, 1, 2, 3 सभी के लिए true कर जाए, अगर हम यहाँ पे value 12 लग दें, तो उसके लिए true कर जाए, अगर suppose कीज़े कि इसका order हम n square कर दें यहाँ पे, जैसे मैंने यह बिजूम करके चला था यहन यहाँ पे, अगर हम इसको n square कर लें, यह n square के लिए भी true कर जाएगा, n cube के लिए true कर जाएगा, means, जो function आपका था n, इसके upper bound, upper bound मतलब इसके उपर जितने भी function है, अगर यहाँ पे हम कोई value function बनाते हैं, तो सब के लिए true हो जाएगा, लेकिन, big O क्या करता है, closure 1 find out करने के लिए, जो यहाँ पे n था, यह पे ही हमारा condition satisfied हो जा रहा है, इसको हम big O n ही कहेंगे. तो hopefully समझ में आ गया होगा आपको next हम बात करते हैं big omega की तो big omega को अगर हम देखें तो big omega को हम lower bound भी कहके चलते हैं अब lower bound ऐसे समझेगा जैसे function आएगा तो अभी हमने upper bound भी देखा था तो इस तरह से इसको भी relate हम करेंगे big omega में the function fn is equal to omega of g of n if there exist positive constant c and n not such that fn इस गेटर देन इक्कॉल टू सीड और जी आफ एन फॉर ऑल एन एन इस गेटर देन इसको टू एन नॉट एंड सीज गेटर दिन जीरो अब इसे पॉइंट डाइग्राम फॉर में भी समझ सकते हैं सपोज कोई आपका फंक्शन दिया हुआ है यह आफ एन जो कि अगर हम देखें तो यह निकली करते हैं टाइम कुछ इस पर से इंक्रीज कर रही है अ लेकिन अब मुझे अगर एक find of function हम लेले gn, gn, c.gn जो कि किसी particular point के बाद जो आपका n not होगा, अगर हमें हाफ़ देखें तो हमेशा कहीं न कहीं आगे जो है जी अन यफ यन से हमेशा लोवर ही है उससे उपर कहीं पे भी या इक्वल कहीं भी उपर नहीं जा रहा है तो हम इस तरह से function define कर सकते हैं यफ यन is greater than is equal to c.g of n for इस गेटर देन जीरो एन इस गेटर एन एन एट गेटर देन एन नॉट या इक्वल टू भी आ सकता है यहां पर एन नॉट इस गेटर देन जीरो अगर इस कंडीशन सर्टिस्फाई करता है देन हम कह सकते हैं कि यह फ्रेंड इसको ऑमेगा ऑफ जी आफ एन झाल अब इसको हम condition satisfy कराके देखते हैं कि example में, suppose same example हम लेते हैं, अगर आपको दिया हुआ है fn is equal to 3n plus 2, तो हम gn, gn assume कर लेंगे, gn हमेशा assume करें चलेंगे वही, जो आपका, हाईस्ट कोफिसियंट के वैल्यू हो जैसे यहां पर कितना है एन है तो हम यहां पर एजूम कर लेंगे जी आफ एन इसको टू एन हमने एजूम कर लिया अब इसको हम फार्मलेंट पूट अप करते हैं जो यहां पर दिया हुआ है यह फैन इस गेटर इन इसकोल टो सी ऑफ डीडा टेन सी डॉट जी ऑफ एन फार ऑल सी इस गेटर देन जी रोफ एन ए एन एन नॉट इज गेटर देन जीव वेल्यू पूट अप कर देते हैं यह फिर की वेल्यू क्या जाएगी थ्री एन प्लस टू अजय को अजय को अजय को 3n plus 2 greater than is equal to gn की value हमने assume क्या रखा है n और c यहाँ पर हमने लिया c.n अब यहाँ से आपको c की value find out करनी है, c की value कौन से value में आप put up कर ले, जैसे c की value 1 रखते हैं, तो c की value 1 रखते ही क्या यहाँ पर कभी condition satisfied होगा, satisfied हो जाएगा, c की value 2 पे, c की value 2 रखें, तो 2 पे भी satisfied कर जा लेकिन अगर हम सीखें करते ही क्या हो जाएगा, fail कर जाएगा, 6 करते ही fail कर जाएगा, तो जो closest one मिला, जहां से fail करना start किया यहाँ पे, तो closest one कौन से मिल गया, c is equal to 3, तो हम यहाँ put up कर लेंगे 3, अब n की value देख लिजे, जिसको हम यहाँ पे n not लेके चलना है, यह क्या पूट करने अगर यह की वेल्यू हम पूट करके देखिए तो कंडीशन सटिस्टिफाइड हो रहा है 3 प्लस 25 ग्रेटर इचकल फाइड फ्री गुड अगर हम टू टू वेल्यू पूट अप करें तो टू पर सटिस्टिफाइड करेगा आगे देखने 34 ऐसे आ� करके देख लेना कहीं हो सकता है कभी mismatch हो जाता है तो फिर हम n की value वहाँ से assume करके चलेंगे तो अगर देखें तो n की value 1, 2, 3 सभी सभी सभी satisfied हो रहा है तो हम कह सकते है n is greater than 1 greater than equal to 1 के लिए हमेशा condition satisfied है तो यहाँ से आप कह सकते है f n is equal to omega of n for प्राप्ता कि सीज को टू थ्री एंड एंड इस गेटर दन इसकोल टू एंड अब यहां पर एक चीज और समझने की बात है देखिए अगर उन बीगोमेगा बात करें तो लोग बांड की बात करना लोग बांड यहां पर थ्री थ्री पर सैटिसफाइड हो रहा है थ्री थ्री एंड पर सैटिसफाइड हो रहा है इस पर सैटिसफाइड हो है तो इसके lower के लिए, lower के लिए मतलब अगर हम यहाँ पे 1 लिख दें तो भी condition true है, log n लिख दें तो भी true है, root n लिख दें तो भी true है, और n लिखे तो true तो high है, तो लेकिन हम इसका upper bound यहाँ पे नहीं लिख सकते हैं, तो यहां पर यहां पर यहा आएगा जो कि इस function के closest one में आ रहा है तो इस तरह से हम big omega भी कर सकते हैं next बात करते हैं हम theta की तो चले theta notation देखते हैं theta notation को represent करते हैं theta से the function definition क्या करा है the function f of n is equal to theta of g of n if there exist positive constant c1 c2 and n not such that c1 dot g n less than is equal to f n and less than is equal to c2 dot जी एंड फॉर ऑल एन एन एन फंक्शन ले रहे हैं जो इस तरह से चल रहा है C G of N और एक हमने यहां से लिया C G of N अगर हम इसको C1 ले लें इसको C2 ले लें तो ध्यान दीजेगा C1 Gn always less than is equal to Fn यहां से डाइग्राम में भी देख सकते हैं इस वन है और C2 जो जगह इंटरसेक्ट कर रहा है तो जब जब जगह इंटरसेक्ट कर रहा था जो हाइएर वन होगा उसी को न लेकर चले करेंगे इसको एक्जांपल से समझ सकते हैं सेम एक्जांपल लेगर हम यह फ्रेंड इसको टू थ्री एन प्लस टू देने जी एन इसका क्या जुन कर लेंगे हम हाई एस्ट आडर हाई एस्ट कोफिसिएंट की वैल्यू कितनी एन तो इसको आप जी लिए अब इसको इसको फार्मुल में पूट कर लेते हैं सपोस्ट हमें ले लिया सीवन जी एन की वैल्यू कितनी आ जाएगी एन इस फार्मुल में वैल्यू पूट अप कर दिये लेस्ट देने स्कूल टू एफिक वैल्यू थ्री एन प्लस टू लेस्ट देने स्कूल टू सी टू जी एन की वेलू एंड अगर हम यहां पर देखें तो एक चीज़ आपको क्लियर होगा कि अभी जो हमने पीछे बिग ओमेगा और बिग ओ देखा ओ दोनों का यहां पर कंसेप्ट आ रहा है मतलब कि अगर हम इस वाले केस को देखें यह वाला केस जी टू जी एन शीघ्र जी एन इस गेटर देने इसको टू यह मतलब अगर इस केस को देखिए यहां से यहां तक का तो यह आपका किस में आ रहा है यह आपका बीगो टाइप में आ रहा है और अगर हम इसको देखते हैं इसको तेकिस केस में आएगा कि ओमेगा वहां पर आ जाएगा तो इन दोनों का कंबिनेशन हो रहा है और मैंने फाइंड आउट कर लिया था अगर हम दिए इस एक्जांपल देखिए इस केस के लिए मैं सीटू को वेल्यू अगर वहां समय करें तो सीट� C2, जो वहाँ पे as a C calculate किया हुआ था, और N की value हमने found out किया था, greater than or equal to 2, और omega आप case में देखें, तो हमने वहाँ पे क्या found out किया था, C1 की value 3 find out किया था, और, n की value find out किया था greater than or equal to 1 अगर हम यहाँ पे omega find out करना है तो हमने जैसे कहा है यहाँ पे n not की कौन से value find out करेंगे n not की जो largest value होगी n not means n जो n growth कर रहा है यहाँ पे तो n not की largest value कितनी है 2 तो हम यहाँ पे लिख सकते हैं कि function f n theta of n जो order था n for all कि सीवन इसको टू थ्री सीटू इसको टू फोर एंड यह निश्चित इसको लेंगे क्योंकि मेरे दोनों में मैक्सिमल कौन सा है इन टू इसको लेकर चलेंगे तो आपका आज आएगा ध्यान दीजिए कि यहां पर जब हम टाइट बाउंड की बात करते यहां पर यह नहीं केवल रखेंगे न तो हम इससे लेस्ट की कोई वैलू यहां पर लिख सकते हैं ना तो इससे अपर की वैलू रख सकते हैं जैसे अपर बाउन की केस में बीगो की केस में क्या था अपर की कोई वैलू हम रख सकते थे और ओमिगा केस में लोग की कोई वै सकते थे वहां पर वह फंक्शन नहीं पूट अप करेंगे यहां पर क्योंकि लोग में सब्सक्राइब बाउंड आएगा यह नहीं होगा तो आपको तीनों क्लियर हो चुका होगा इसमाल इसमाल इंपॉर्टेंट नहीं है आपके केस में तो इसको अभी करते हैं आगे फर्थ देखेंगे अगर जरूरत पड़ेगी तो इसको भी हम कंप्लीट करेंगे तो होप सो कंसेप्ट तीनों के के लिए तीनों का क्लियर हो च