Input – Output Properties of “O” Notation

Input – Output Properties of “O” Notation in Data Structure – Constant Time के Algorithms परिभाषा के रूप में सभी Input Data पर Processing के लिए समान समय लेते हैं। लेकिन ज्यादातर Algorithms Constant Time नहीं होते हैं। यानी सभी Data की Processing में समान समय नहीं लेते हैं। इस स्थिति में हम एक निश्चित अंक के रूप में किसी Algorithm की Efficiency को परिभाषित नहीं कर सकते हैं। इसलिए हमें Algorithm की Efficiency को Input Data की Size n के फलन के रूप में ही परिभाषित करना पडता है।

पहली समस्या का समाधान ये है कि हमें Algorithm की Efficiency को Analytically Measure करना चाहिए ना कि Experimentally, क्योंकि दो अलग Computer पर समान Algorithm भी अलग Time में Perform होगा।

अन्‍य शब्दों में कहें तो हमें Algorithm को उसकी Efficiency व उस Algorithm को प्रभावित करने वाले तत्वों के आधार पर परिभाषित करना होता है। सामान्‍यतया हम किसी Algorithm की Efficiency ज्ञात करने के लिए निम्न में से किसी एक को Measure करते हैं-

• Numerical Algorithms के लिए हम कुल Addition, Subtraction, Multiplication आदि की संख्‍या ज्ञात करते हैं।
• Searching या Sorting के Algorithm में हम कुल Comparisons की संख्‍या ज्ञात करते हैं।
• Assignment Statements व Parameters के आधार पर Data Movement की कुल संख्‍या को ज्ञात करते हैं।
• किसी Algorithm के लिए Required कुल Memory Space की Limit को ज्ञात करते हैं।

दूसरी समस्या के समाधान के लिए हम N Data Items के लिए Algorithm की Efficiency दर्शाने वाला एक फलन ज्ञात करते हैं जिससे किसी Algorithm की Efficiency या Complexity को Represent किया जाता है।

किसी Algorithm की Complexity या Efficiency को ज्ञात करते समय हमें सबसे पहले ये तय करना होता है कि हम Input की किस Property को Measure करने जा रहे हैं।

किसी Algorithm की सबसे अच्छी Property वह होती है जो Algorithm के Efficiency Factor को प्रभावित करती हो।

हम यहां पर Algorithm की Key Property के रूप में Input Size शब्द को Use करके Algorithm को Analyze करेंगे और Input Size को Variable N से Represent करेंगे। फिर भी ये जरूरी नहीं है कि हम केवल एक ही Property का प्रयोग करें। हम किसी Algorithm की Efficiency को कई Properties के आधार पर एक फलन के रूप में Express कर सकते हैं।

लेकिन केवल एक ही Property के आधार पर किसी Algorithm की Efficiency को Express करना काफी सरल तरीका होता है तथा एक ही Property को सभी Properties के रूप में Represent किया जा सकता है। इसी तरीके को सबसे ज्यादा Use किया जाता है।

उदाहरण के लिए किसी List के विभिन्न Elements को Sort करने के लिए जितना समय Use होता है उसे List की Length के एक फलन के रूप में लिखा जा सकता है। Sorting के लिए हम जिस Algorithm का प्रयोग करते हैं वह Typically एक Quadratic Function होता है। यानी

TIME(n) = n * n

MergeSort व QuickSort के Algorithm अधिक तेज होते हैं। उनको फलन के रूप में निम्नानुसार लिखा जा सकता है-

TIME(n) = n * log (n)

इस Algorithm की Length Quadratic से कम लेकिन Linear से अधिक होती है।

ये तरीका अभी भी दूसरी समस्या का जवाब प्रदान नहीं कर रहा है।

मानलो एक Algorithm किसी List में से किसी Required मान को Search कर रहा है। हम ये मान लेते हैं कि जो भी मान Search किया जा रहा है वह हमेंशा List में उपलब्ध होता है। ऐसा कोई मान Search नहीं किया जाता जो कि List में उपलब्ध ही ना हो। इस स्थिति में Algorithm हमेंशा Successful होता है।

अब इस Algorithm की Speed को प्रभावित करने वाला Factor वह स्थान है जहां पर Search किया जाने वाला मान प्राप्त होता है। यदि Algorithm वहां से शुरू होता है जहां पर Search किया जाने वाला मान उपलब्ध है तो Algorithm बहुत ही जल्दी समाप्त हो जाएगा।

जबकि यदि Search किया जाने वाला मान List में कहीं अन्‍य स्थान पर है, तो Algorithm को अन्‍य स्थानों पर भी Search किए जाने वाले मान को खोजना होगा। इस स्थिति में हम जो फलन यहां पर प्राप्त करना चाहते हैं वह पूरा नहीं है। ये फलन Input Size n पर निर्भर है।

यदि Search किया जाने वाला Data तुरन्त प्राप्त हो जाता है तो ये Best Case स्थिति है लेकिन यदि Search किया जाने वाला Data काफी Comparisons के बाद प्राप्त होता है, तो इसे Worst Case स्थिति कहेंगे।

हमारे इस Algorithm में Best Case = Constant Time होगा जबकि Worst Case = Length of List या N-1 होगा। Average Case में Search किया जाने वाला Data List में प्रथम व अन्तिम स्थान के अलावा कहीं भी प्राप्त हो सकता है।

अब जब हम दो Algorithms को Compare करते हैं तो हमें दो Algorithms के फलनों को Compare करना पडता है। इस Analysis में हमें हमेंशा सावधान रहना होता है क्योंकि ये फलन कई स्थानों पर एक दूसरे को Cross कर सकते हैं।

यानी किसी एक Input के लिए पहला Algorithm उपयुक्त लगता है जबकि किसी दूसरे Input के लिए पहले के स्थान पर दूसरा Algorithm अधिक उपयुक्त लगता है। यदि ऐसा होता है तो इसका मतलब है कि दोनों ही Algorithm सभी Inputs के लिए एक दूसरे से अधिक उपयुक्त या Efficient नहीं हैं।

दो Algorithms की वास्तव में उचित Comparing करने के लिए जरूरी है कि हमारे पास दोनों Algorithms के उचित फलन हों और हम ये पता कर सकें कि दोनों Algorithm किस Input के लिए एक दूसरे को Cross करते हैं।

प्रायोगिक रूप से ये पता करना बहुत ही मुशिकल काम है। इसलिए हम दोनों Algorithm के Input का लगभग मान प्राप्त करते हैं जहां पर दोनों Algorithms एक दूसरे को Cross करते हैं। इस प्रक्रिया को “Ballpark Estimate” कहा जाता है।

“Ballpark Estimate” किसी Algorithm का लगभग Complexion होता है जिसे Asymptotic Complexity कहा जाता है। Asymptotic Complexity किसी Algorithm का मुख्‍य Term होता है जिससे किसी Algorithm के फलन की Limit का पता चलता है। उदाहरण के लिए मानलो कि हमारे पास दो Algorithms हैं-

• A1 – Efficiency(n) = 29 [ Constant Time ]
• A2 – Efficiency(n) = 3 + n/2 [ Linear Time ]

जब तक n = 52 होता है तब तक A1(n) > A2(n) होता है। यानी जब n का मान 52 होता है तब दोनों Algorithm की Complexity समान होती है। इस Limit पर दोनों Algorithm एक – दूसरे को Cross करते हैं। हालांकि एक बहुत ही छोटी List के लिए A2 Algorithm काफी Efficient है लेकिन यदि List बडी हो तो A1 Algorithm A2 Algorithm की तुलना में अधिक Efficient रहता है। Asymptotic Complexity के पीछे यही Idea है।

मानलो कि एक Array में 52 Items के साथ 29 Operations करने पर Required काम हो जाता है। इस स्थिति में दोनों ही Algorithms को एक दूसरे के स्थान पर Use किया जा सकता है। लेकिन यदि Data Items की संख्‍या 52 से कम हो तो पहला Algorithm अधिक Efficient होगा जबकि यदि Data Items की संख्‍या 52 से अधिक हो तो दूसरा Algorithm पहले की तुलना में अधिक Efficient होगा।

Asymptotic Complexity में फलन के सभी Lower Order Terms व Constant Multipliers को Ignore कर दिया जाता है, इसलिए सभी Linear फलनों को “O” Notation में O(n) लिखा जाता है और सभी Constant Time फलन को “O” Notation में O(1) लिखा जाता है।

यानी A1 की Asymptotic Complexity O(1) है जबकि A2 की Asymptotic Complexity O(n) है। स्पष्‍ट रूप से हम कह सकते हैं कि Asymptotic Complexity तभी उपयुक्त है जब हमें बहुत बडे Input के साथ प्रक्रिया करनी हो। किसी Application Program में हमें तब अधिक सटीकता से Analysis करना पडता है जब हम कम Input Data के साथ प्रक्रिया कर रहे होते हैं।

हमने अभी तक विभिन्न प्रकार के फलनों को देखा है। इन सभी फलनों द्वारा हम किसी Algorithm को Analyze करते हैं और Algorithm की Efficiency या Complexity ज्ञात करते हैं। Efficiency या Complexity को प्रदर्शित करने के लिए हम Capital Letter “O” का प्रयोग करते हैं। विभिन्न प्रकार के फलनों को Represent करने के लिए हम “O” Notation का प्रयोग करते हैं। इस “O” Notation को Use करके किसी फलन की Efficiency या Complexity को Represent करने की प्रक्रिया को Big – O Notation कहा जाता है।

जब हम Big – O Notation द्वारा किसी Algorithm की Complexity के फलन को Represent करते हैं तब फलन के विभिन्न Low – Order Terms, Dominant Terms व Constants Coefficients को Ignore कर देते हैं व केवल Highest Power या Highest Value Represent करने वाले Notation को ही Big – O Notation के रूप में व्‍यक्त करते हैं। जैसे Efficiency(n) को यदि Big – O Notation के रूप में व्‍यक्त करना हो तो हम इसे केवल O(n) लिखते हैं।