Complexity of Algorithm – Efficiency of Algorithm

Complexity of Algorithm – किसी Algorithm की Complexity एक Function होता है जो किसी Input Data के आधार पर Data की Processing में लगने वाला समय या Space या दोनों को दर्शाता है।

यानी किसी Algorithm को Execute होने में कितना समय लगेगा और वह Algorithm Memory में कितना Space लेगा, इन दोनों या दोनों में से किसी एक बात को दर्शाने के लिए हम जिस Function को Use करते हैं, वह Function बताता है कि कोई Algorithm कितना Complex है और कितने समय में किसी Data की Processing करेगा तथा Data की Processing के लिए कितना Space Use करेगा। इन Functions द्वारा हम Mathematically ये जान सकते हैं कि कोई Algorithm किसी अन्‍य Algorithm की तुलना में कितना Efficient है।

Computer Science में Algorithms को Analyze करना एक बहुत ही बडा व जटिल काम है। किन्ही Algorithms की तुलना करने के लिए हमारे पास कुछ Criteria होना बहुत जरूरी होता है, जिससे हम पता लगा सकें कि कोई Algorithm कितना Efficient है।

यदि किसी Data Structure में n Data हों तो Algorithm M के Input Data की Size n होती है। Input Data की Size किसी भी Algorithm का पहला Criteria होता है। हम किसी Algorithm से किस प्रकार के Steps का प्रयोग करके Data Process करते हैं, उन Steps की संख्‍या किसी Algorithm की Efficiency ज्ञात करने का दूसरा Criteria होता है।

यानी कोई Algorithm कितना Efficient है, ये Input Data व Data को Process करने के लिए Use कि, जाने वाले Steps की संख्‍या यानी Comparisons पर निर्भर करता है।

कोई Algorithm किसी समस्या का समाधान प्रदान करने के लिए कितने समय व Space का उपयोग करता है, इन दोनों तथ्यों के आधार पर उस Algorithm की Efficiency का पता चलता है।

मानलो कि M एक Algorithm है और उसके Input Data की Size n है। किसी Searching या Sorting के Algorithm में जितने Operations के बाद Data Process होता है, उन Operations की संख्‍या के आधार पर Algorithm के Time का पता चलता है।

जैसे कि एक File में 1000 Records हैं और उनमें से किसी विशेष नाम के Record को प्राप्त करना है, तो Algorithm को वांछित Record प्राप्त करने के लिए अधिकतम 1000 Comparisons करने पड सकते हैं। इन अधिकतम 1000 Comparisons में लगने वाले समय को Algorithm द्वारा Use किया जाने वाला समय कहते हैं और इन 1000 Comparisons में Algorithm जितनी Memory को Use करता है, वह Memory किसी Algorithm द्वारा Use की जाने वाली Space होती है।

किसी Algorithm M की Complexity ज्ञात करने के लिए एक Function f(n) का प्रयोग किया जाता है। ये Function किसी Algorithm की Complexity प्रदान करता है जहां n Input Data की Size है।

उदाहरण के लिए किसी File में केवल 1 Record है तो उस Record से किसी नाम के Record को Search करने पर Algorithm की Complexity कम होगी जबकि उसी File में यदि 100 Record हों तो Use होने वाले Algorithm की Complexity अधिक होगी। यदि वांछित Record पूरी File में कहीं प्राप्त ना हो तो Algorithm की Complexity अनन्त होगी।

मानलो कि जो Record Search किया जा रहा है वह File में पहले स्थान पर ही उपलब्ध हो तो Algorithm की Complexity बिल्कुल कम होगी और Algorithm को Best Case Algorithm कहा जाएगा। यदि Search किया जाने वाला Record File के मध्‍य में हो तो Algorithm को Average Case Algorithm कहा जाएगा और यदि जो Record Search किया जा रहा है वह Record पूरी File में कहीं ना हो तो ऐसे Algorithm को Worst Case Algorithm कहा जाता है।

किसी Worst Case Algorithm में Record को Search करने के लिए उतनी बार Comparison का Operations करना पडता है, जितने File में Records हैं। मानलो कि File में 100 Record हैं तो Algorithm को 100 बार Comparison करना पड सकता है। इसे हम Mathematically निम्नानुसार प्रदर्शित कर सकते हैं-

C(n) = n

जहां C = Comparisons की संख्‍या है और n = Input Data की Size है। किसी Linear Search Algorithm की Worst Case Complexity में C(n) = n होती है।

Average Case Algorithm में किसी Data के हर Location पर मिलने की सम्भावना 1/n होती है जहां n Data Items की संख्‍या है। यानी यदि किसी Data Structure में n Data Items हों तो Data 1 से लेकर n तक में किसी भी स्थान पर हो सकता है। इसलिए किसी Data Item को किसी List में खोजने के लिए Algorithm को कुल n Comparisons करने पड सकते हैं। इसे हम निम्नानुसार Mathematically दर्शा सकते हैं-

इस Probability Equation से हम देख सकते हैं कि किसी Data के List में मिलने की सम्भावना लगभग n/2 होती है जहां n List के कुल Data Items की संख्‍या है।