Big-Theta notation Data structures and Algorithms in Hindi

big theta notation किसी भी algorithm की tight bound को दर्शाता है इस notation से हम किसी भी algorithm के बारे में अच्छे से जानकारी प्राप्त कर सकते है लेकिन इसको calculate करना बहुत ही मुश्किल होता है क्युकी यह algorithm की upper और lower दोनों bound को दर्शाता है 

अगर आपको big o notation के बारे में नहीं पता है की किसी भी function के लिए big o को कैसे ज्ञात किया जाता है तो पहले आप निचे दी गयी post को पढ़े क्योकि बिना big o notation के बारे में समझे आपको theta notation के बारे में नहीं समझ में आएगा | 

Big o notation in Hindi

big theta notation एक symmetric notation है इसका मतलब है की अगर कोई function f(x) समय के साथ किसी दर g(x) से बढ़ रहा है तो function g(x) भी f(x) की दर से बढ़ेगा | 

f(x) = Ө(g(x)) <=> g(x) = Ө(f(x)) 

Big theta का Example

माना की हमारे पास एक function है f(n) = 42n^2 + 25n + 4 

जैसे की हम सभी जानते है की big o notation सिर्फ algorithm की upper bound को ही दर्शाता है इसलिए हम कह सकते है की function f(n) O(n^2), O(n^3), और O(n^100) का है जो की function की upper bounds है 

लेकिन theta notation algorithm की सिर्फ tight bound को ही दर्शाता है इसलिए हम कहेगे की function f(n) की tight bound सिर्फ Ө(n^2) है 

Note: किसी भी algorithm की एक ही tight bound होती है और upper bound एक से ज्यादा हो सकती है 

big theta notation की Mathematical परिभाषा 

माना की हमारे पास functions का समूह है जिसे हम Ө(g(x)) से दर्शाते है तो अगर कोई function f(x),  उन functions के समूह Ө(g(x)) में से होगा अगर दो ऐसे positive constants c1, c2 हो की जिनको function g(x) में गुना करने पर function f(x), function (c1*g(x)) से तो बड़ा हो लेकिन c2*g(x) से छोटा हो | 

 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N

इसलिए हम कह सकते है की function f(x) की upper और lower bound दोनों function g(x) ही है | 

जहा 
c1*g(x) = lower bound 
c2*g(x) = upper bound कहलाती है | 

Big theta का graph representation

                                    


एक टिप्पणी भेजें

0 टिप्पणियाँ