Rate of Growth in Data Structure

Rate of Growth in Data Structure – कोई Algorithm Perform होने में कितने समय का उपयोग करेगा ये Analyze करने का कोई साधारण तरीका नहीं है। किसी भी Algorithm के Time Requirement को प्रभावित करने वाली सबसे पहली Complexity तो ये है कि कोई Algorithm किस Computer पर Perform हो रहा है, उस Computer पर ही Algorithm के Perform होने का Time निर्भर होगा।

मानलो यदि हम एक ही Algorithm को Pentium III Processor वाले CPU पर Execute करते हैं और उसी Algorithm को Pentium IV के Processor पर Execute करें, तो दोनों Computer पर Algorithm के Perform होने के समय में अन्तर रहेगा। यानी सबसे पहले तो कोई भी Algorithm कितना समय लेगा ये उस Computer की Speed पर निर्भर करता है जिस पर Algorithm को Use किया जा रहा है।

Algorithm के Perform होने के Time को प्रभावित करने वाली दूसरी Complexity Input Data Items की संख्‍या पर निर्भर करती है।

उदाहरण के लिए यदि किसी Array में 100 Data Elements को जोडना हो तो कम समय लगेगा जबकि यदि Array में 10000 Data Elements हों, तो उन सभी की जोड करने में 100 Data की तुलना में अधिक समय लगेगा। परिणामस्वरूप कोई Algorithm Perform होने में अनुमानत: कितना समय लेगा, इसे Input Data Size के फलन के रूप में Express किया जा सकता है।

उदाहरण के लिए यदि किसी Array में Data Items की संख्‍या n हो तो Algorithm द्वारा n Data की Processing में लगने वाले समय को Time T(n) व Space S(n) के फलन के रूप में Express किया जा सकता है, जहां T व S Input Data n के फलन हैं।

इससे पहले कि हम किसी Algorithm को Analyze करके उसकी Efficiency ज्ञात करें, कुछ Functions को समय ना ठीक रहेगा, जिनका प्रयोग T व S को Express करने के लिए किया जाता है। ये कुछ Standard Functions हैं जो Input Data Item n की Size के आधार पर Algorithm द्वारा लिया जाने वाला समय ज्ञात करने के लिए Use किए जाते हैं।

उदाहरण के लिए मान लो कि किसी Array में 16 Data Items हैं। इन 16 Data Items को अलग-अलग तरह से अलग-अलग कामों के लिए Process करने के लिए अलग-अलग Algorithms की जरूरत होती है। यदि इन 16 Items पर Processing करने के लिए हम f(n) = 2ⁿ फलन का प्रयोग करें तो हमें Array के 16 Elements को Process करने के लिए कम से कम 2¹⁶ Operations करने पडेंगे, यानी हमें कुल 65536 Operations करने होंगे।

यदि इस फलन का Graph बनाया जाए, तो बनने वाला Graph काफी तेजी से बढेगा। यानी इस फलन के बढने की दर सबसे तेज होती है। ये फलन किसी भी Algorithm की Complexity ज्ञात करने का सबसे पहला फलन है जो किसी Algorithm के Perform होने में Algorithm द्वारा लिए जाने वाले सबसे अधिक समय को दर्शाता है।

यदि इस फलन के स्थान पर Algorithm f(n) = n³ फलन का प्रयोग करे, तो कुल Operations की संख्‍या 16³ होगी।

यदि इस फलन का भी ग्राफ बनाया जाए तो ये ग्राफ भी काफी तेजी से बढेगा लेकिन फिर भी ये Graph पहले वाले फलन की तुलना में कम तेजी से बढेगा। किसी Algorithm की Complexity ज्ञात करने के लिए Use किया जाने वाला तीसरा फलन f(n) = n² है।

यदि इसी 16 Element वाले Array के 16 Data को Process करने के लिए यदि n² Operations करने पडे तो, Algorithm को कुल 256 Operation करने होंगे।

यदि इस फलन के Growth का Graph बनाया जाए तो ये Graph भी काफी तेजी से बढेगा लेकिन पहले वाले दोनों फलनों की तुलना में काफी कम तेजी से बढेगा।

यदि Algorithm Perform होने के लिए f(n) = n log₂ n Operations करता है तो इस फलन का Growth Rate पहले बता, गए सभी फलनों से कम होगा। यानी यदि इस फलन का Graph बनाया जाए तो Graph काफी धीमी गति से बढेगा।

यदि 16 Data Element के Array पर Processing के लिए n log₂ n Operations करने पडें तो कुल Operations की संख्‍या 16 X log₂ 16 = 16 X 4 = 64 होगी, जो कि पहले के सभी फलनों की तुलना में काफी कम है।

यदि जो Algorithm Use किया जा रहा है वह Algorithm 16 Elements को Process करने में केवल 16 ही Operations करे, तो Algorithm की Complexity f(n) = n होती है।

यदि इसका Graph बनाया जाए, तो एक Linear Graph बनता है जो कि Data Elements n की संख्‍या बढने के साथ बढता है और घटने के साथ घटता है। किसी Algorithm की Complexity ज्ञात करने का अन्तिम फलन f(n) = log₂ n है जिसमें 16 Item को Process करने में केवल 4 Operations करने होंगे।

यदि इन सभी फलनों का Graph बनाया जाए तो ये Graph क्रम से अधिक Complex Algorithm को दर्शाऐंगे। इस Graph को किसी Algorithm की Complexity का Rate of Growth कहा जाता है।

कोई Algorithm Perform होने के समय किस फलन के अनुसार Operations करता है, इसके आधार पर Algorithm की Complexity निर्भर करती है। एक ही काम को करने के लिए विभिन्न तरीके हो सकते हैं। जो तरीका कम से कम Operations में हमें हमारा Required Result प्रदान कर देता है वह Algorithm कम Complex और अधिक Efficient कहलाता है जबकि इसके विपरीत होने पर Algorithm अधिक Complex व कम Efficient कहलाता है। Algorithm की Growth निम्न क्रम में होती है-

log₂ n        n          n log₂ n     n²        n³        2ⁿ

किसी भी Algorithm को Analyze करके ये पता किया जाता है कि Algorithm की Complexity किस फलन के अनुसार Grow हो रही है। हमें यही कोशिश करनी चाहिए कि किसी भी Algorithm की Complexity Linear क्रम में बढे। ऐसा Algorithm काफी Efficient होता है जिसका Graph Linearly बढता है।