4. Space Complexity
অ্যালগরিদম অ্যানালাইসিসে মেমরি ব্যবহারের হিসেব রাখাই হলো স্পেস কমপ্লেক্সিটি। একটি প্রোগ্রাম রান করার সময় কম্পিউটারের র্যামে (RAM) কতটুকু জায়গা নেবে, তা ইনপুট সাইজের মাধ্যমে প্রকাশ করা হয়।
মেমরি ব্যবহারের বিশ্লেষণ (Memory Usage Analysis)
একটি প্রোগ্রামের মোট মেমরি ব্যবহারকে মূলত দুই ভাগে ভাগ করা যায়:
- Fixed Part: ভেরিয়েবল, কনস্ট্যান্ট এবং ইন্সট্রাকশন সেট যা ইনপুট সাইজের ওপর নির্ভর করে না।
- Variable Part: ডাইনামিক মেমরি অ্যালোকেশন এবং রিকার্সন স্ট্যাক (Recursion Stack) যা ইনপুট সাইজের ওপর নির্ভর করে।
Auxiliary Space vs Space Complexity
অনেকেই এই দুটিকে গুলিয়ে ফেলেন, কিন্তু এদের মধ্যে পার্থক্য আছে:
- Space Complexity: প্রোগ্রামের ব্যবহৃত মোট মেমরি (Input Space + Auxiliary Space)।
- Auxiliary Space: অ্যালগরিদমটি কাজ করার সময় অতিরিক্ত যে মেমরি ব্যবহার করে (ইনপুট বাদ দিয়ে)।
Input Space
অ্যালগরিদমে যে ডেটা আমরা প্রসেস করার জন্য ইনপুট দেই, সেই ডেটা রাখার জন্য যে মেমরি প্রয়োজন হয় তাকে ইনপুট স্পেস বলে।
Stack Space in Recursion
রিকার্সিভ মেথড কল করার সময় প্রতিটি কলের জন্য মেমরি স্ট্যাক তৈরি হয়। যদি কোনো রিকার্সন n বার কল হয়, তবে এর স্ট্যাক স্পেস হবে O(n)। এটি স্পেস কমপ্লেক্সিটি বাড়ানোর একটি প্রধান কারণ।
ইন-প্লেস অ্যালগরিদম (In-place Algorithms)
সবসব অ্যালগরিদম অন্য কোনো মেমরি ব্যবহার না করেই সরাসরি ইনপুট ডেটার মধ্যেই পরিবর্তন আনে, তাদের ইন-প্লেস অ্যালগরিদম বলে। এগুলোর স্পেস কমপ্লেক্সিটি সাধারণত কম হয়।
- উদাহরণ: Insertion Sort, Bubble Sort (Auxiliary Space: O(1))।
Space-Time Trade-offs
কখনো কখনো আমাদের হাতে দুটি অপশন থাকে:
- কোড খুব দ্রুত চালানো কিন্তু বেশি মেমরি ব্যবহার করা (Time Efficient)।
- মেমরি কম ব্যবহার করা কিন্তু কোড ধীর গতির হওয়া (Memory Efficient)।
আধুনিক কম্পিউটিংয়ে মেমরি সস্তা হওয়ায় আমরা অনেক সময় টাইম অপ্টিমাইজড সমাধানের দিকে ঝুঁকে পড়ি। তবে এমবেডেড সিস্টেম বা ছোট ডিভাইসের জন্য স্পেস অপ্টিমাইজড কোড জরুরি।
IMPORTANT
একটি কার্যকর অ্যালগরিদম হলো সেটি, যা কম সময়ে এবং কম মেমরিতে সঠিক আউটপুট দিতে পারে।
TIP
রিকার্সনের পরিবর্তে অনেক সময় ইটারেটিভ (Loop) অ্যাপ্রোচ ব্যবহার করলে স্ট্যাক মেমরি বাঁচানো যায়।