Big O Notation Data structures and algorithms in Hindi

Big O notation एक ऐसा tool है जो की किसी algorithm की efficiency को ज्ञात करने के लिए काम में लिया जाता है जैसे की कोई algorithm run होने में कितना समय लेगा यह किसी भी algorithm की upper bound को ज्ञात करने के लिए इस्तेमाल किया जाता है

यह किसी भी function के asymptotic behavior को दर्शाता है और बताता है की एक function f(n) पर उसमे देने वाले input n की size को बढ़ाने पर कितना प्रभाव पड़ता है 

Big O Notation in Algorithms in Hindi

Big O notation की Definition in Hindi 

एक function f(n) है जो की g(n) order का होगा अगर उस function में 2 ऐसे constants c और n0 हो जिससे की constant c का गुणा function g(n) में करने पर function f(n) का मान , function g(n) से छोटा या उसके बराबर रहे | 

function f(n) <= c*g(n) जहाँ पर n की value nसे बड़ी है 

Big O Notation in Algorithms in Hindi

Note: यहाँ पर g(n) function f(n) की upper bound कहलाती है | 

एक example की मदद से इसे समझते है | 

मान लीजिये की एक function f(n) = 5n + 4 है और हमें इस function का big o notation को ज्ञात करना है | 

f(n) = 5n + 4

अब हमें सबसे पहले function f(n) की upper bound को ज्ञात करना पड़ेगा मान लेते है की g(n) = n है जो की function f(n) की upper bound है | 

big o की definition के अनुसार हमें 2 ऐसे constants c और n0 को find करना है की जिससे की हमारी निचे दी गयी condition true हो जाये | 

अब हम function को big o की definition के अनुसार इस प्रकार लिख सकते है | 

f(n) <= c*g(n)
5n + 4 <= c*n जहाँ n >= n0

मान लीजिये की c = 6 और n0 = 4 है अब हम इन values को function f(n) में देते है तो 

5n + 4 <= 6n जहाँ n >= 4 

यहाँ पर n की value 4 या उससे बड़ी होने पर ऊपर दी गयी condition true होगी 

इसलिए function f(n) = 5n + 4, n order का है और इसे हम mathematical term में 5n+4 is O(n)
ऐसे लिखते है | 

एक दूसरा example लेते है 

f(n) = 3n+ 4n + 7

माना g(n) = n2

अब माना की c = 5 और n0 = 6 है इनके मान function f(n) में रखने पर 

3n2 + 4n + 7 <= 5n2 जहाँ n >= 6 

n की value 6 और उससे बड़ी होने पर condition true होगी इसलिए function f(n) = 3n2 + 4n + 7 order nका होगा 
3n2 + 4n + 7 is O(n2)

अब बात आती है की इन constants की values को find करना इतना आसान नहीं होता है तो इसलिए हम किसी function के लिए big o की find करने के लिए हम कुछ rules का इस्तेमाल करते है जिससे की हम आसानी से big o को find कर सकते है | 


Big O notation को find करने के लिए method Hindi में

Rule First:

fastest-growing term के अलावा बाकि सभी lower terms और constants को हटा दे 

जैसे example, एक function f(n) = 3n2 + 4n + 2 है तो इसमें fastest-growing term 3n2 है तो हम सिर्फ 3n2 को रखेंगे और बाकी सारी lower terms 4n और constant 2 को function f(n) से हटा देंगे | 


Rule Second:

जितने भी coefficients है उनको equation से हटा देंगे | 

जैसे example, हमारे पास function f(n) = 3n2 है तो हम coefficients 3 को equation 3n2 से हटा देंगे | 


Rule third

अगर function f(n) एक constant function है तब  f(n) order 1 का होगा | 

जैसे example हमारे पास  function f(n) = 4 है जो की एक constant function है इसलिए यह order 1 का function है | 


Rule Fourth

किसी भी equation में logarithm के base को हम consider नहीं करेंगे | 


logan = logbn / logba

log a और b दोनों constants है इसलिए हम इनके base को consider नहीं करते है | 

जैसे example अगर एक function f(n) = 8log2n है तो हम कहेगे की function f(n) log n order का है न की हम कहेगे की function base 2 logn order का है | 

एक example से हम समझते है की हम कैसे इन rules का इस्तेमाल करके Big O को किसी function के लिए find करते है |

Example 1:

f(n) = 45
यहाँ पर function f(n) एक constant function है इसलिए यह order 1 का function है | 
f(n) is O(n)

Example 2:

f(n) = 6n3 + 27log2n + 2n

यहाँ पर हम rules को apply करेंगे | 

सबसे पहले , हम lower terms और constants को हटायेंगे 

f(n) = 6n3

दूसरा, coefficients को हटाएंगे

f(n) = n3 

इसलिए function f(n) order n3 का है 
f(n) is O(n3)



टिप्पणी पोस्ट करें

0 टिप्पणियां