Time Space Tradeoff in Data Structure. Really interesting concept applies everywhere.

किसी समस्या के समाधान को प्राप्त करने के लिए विभिन्न Steps की एक Well Defined List को Algorithm कहते हैं।

Data को Efficiently Process करने के लिए एक Efficient Algorithm की आवश्‍यकता होती है। कोई Algorithm कितना Efficient है, यानी किसी समस्या के समाधान के लिए Algorithm किस तरह लिखा गया है और Algorithm में लिखे गए Steps कितनी Efficiently Data की Processing करते हैं, इसे दो तथ्यों Time व Space के आधार पर तय किया जाता है।

हर Algorithm में Data पर विभिन्न तरीके से Processing की जाती है। इसलिए हम हमेंशा Data को Process करने के लिए सबसे Efficient Algorithm को Use नहीं कर सकते। कोई Algorithm कितना Efficiently Data पर Processing करेगा ये बात कुछ अन्य तथ्यों पर भी निर्भर करती है। जैसेकि हम किस प्रकार के Data पर Processing कर रहे हैं और Data पर विभिन्न Operations करने के लिए कितने Steps लेने पडते हैं।

Time – Space Tradeoff Use किए जा रहे Data Structure पर निर्भर करता है।

यानी यदि हम Data को Store करने के लिए Space बढा दें तो Data की Processing में लगने वाला समय कम हो जाता है और यदि Data को Store करने के लिए Use होने वाले Space को कम कर दें, तो Data की Processing में लगने वाला समय बढ जाता है। इसी प्रक्रिया को Time – Space Tradeoff कहते हैं। इसे समझने के लिए हम एक उदाहरण लेते हैं।

मानलो कि एक File में विभिन्न Students की Information हैं। File को Name Wise Sort करके और Binary Searching Algorithm को Use करके हम बहुत Efficient तरीके से इस File में से किसी विशेष नाम के Record को प्राप्त सकते हैं। लेकिन यदि हमें किसी Student का Serial Number दिया गया हो और हमें उस Serial Number वाले Student के Record को Search करना हो तो हम Binary Searching तरीके को Use करके Record को नहीं खोज सकते हैं।

क्योंकि Binary Searching Algorithm को Use करने के लिए हमें Sorted Records की जरूरत होती है और किसी File के विभिन्न Records को या तो Name Wise Sort करके रख सकते हैं या Serial Number के अनुसार। हम Name व SR_No दोनों को एक साथ Sort करके नहीं रख सकते। इसलिए यदि हमें SR_No के अनुसार किसी Record को खोजना हो तो हमें File के हर Record को किसी अमुक SR_No के लिए Check करना होगा।

यदि Search की जाने वाली File में काफी अधिक Records हों तो इस तरह की Searching में बहुत Time लगेगा। इस समस्या का एक समाधान ये हो सकता है कि हम एक और File बनाए और उसे Serial Number Wise Sort करके रखें। लेकिन ऐसा करने पर समान प्रकार के Data की दो File बन जाएंगी जिससे Memory में दुगुना Space Use होगा। इसलिए इस तरीके को भी एक Efficient तरीका नहीं कहा जा सकता।

इस समस्या के समाधान के रूप में हम एक तरीका और अपना सकते हैं। हम Main File को SR_No Number के अनुसार Sort कर देते हैं और एक और Array लेते हैं और उसमें केवल दो Columns एक नाम के लिए व दूसरा Pointer के लिए लेते हैं।इस Array को Name Wise Sort कर लेते हैं। इस Array के हर SR_No का एक Pointer Main File के किसी Record को Point करता है। इस तरीके में हालांकि दूसरे Array के लिए Extra Space Use हो रहा है लेकिन फिर भी इस Array में केवल दो Fields हैं, इसलिए इस तरीके में कम से कम Space Use होगा। इस तरीके के Algorithm को हम एक Efficient Algorithm कह सकते हैं। (Time Space Tradeoff in Data Structure)