স্পেস কমপ্লিক্সিটি(complexity)

---

কোনো একটা অ্যালগরিদম/প্রোগ্রামে টাইম কমপ্লিক্সিটির(complexity) মতো স্পেস কমপ্লিক্সিটি(complexity)ও গুরুত্বপূর্ণ বিষয় । স্পেস কমপ্লিক্সিটি(complexity) এবং টাইম কমপ্লিক্সিটি(complexity) প্রায়ই একই কারণ তারা একটি অ্যালগরিদমের ইনপুট পরিমাণের সাথে সম্পর্কিত। যেখানে টাইম কমপ্লিক্সিটি(complexity) একটি অ্যালগরিদমে অপারেশনের পরিমাণের সাথে সম্পর্কিত, এবং স্পেস কমপ্লিক্সিটি(complexity) অ্যালগরিদম সম্পন্ন করার জন্য প্রয়োজনীয় মোট জায়গার সাথে সম্পর্কিত।

স্পেস কমপ্লিক্সিটি(complexity) কি ?

সহজভাবে বললে, একটি অ্যালগরিদম বা প্রোগ্রাম সম্পন্ন করার জন্য ঠিক কতটুকু জায়গা বা মেমরি নিলো তাকেই স্পেস কমপ্লিক্সিটি(complexity) বলে। কোনো অ্যালগরিদম বা প্রোগ্রামের জন্য আমাদের নির্দিষ্ট পরিমাণ মেমরি ব্যাবহার করতে হয়। কিন্তু আমরা যদি স্পেস কমপ্লিক্সিটির(complexity) হিসেব-নিকেশ বুঝি তাহলে সহজেই বলে দিতে পারবো যে একটি প্রোগ্রাম কার্যকর করার জন্য ঠিক কতটুকু মেমরি ব্যাবহার করতে হবে।

একটি অ্যালগরিদম/প্রোগ্রামের স্পেস কমপ্লিক্সিটি(complexity) বের করতে প্রোগ্রামে ব্যবহৃত ভেরিয়েবল দ্বারা দখলকৃত স্থান গণনা করা যথেষ্ট।

স্পেস কমপ্লিক্সিটি(complexity) কেন দরকার ?

একটি অ্যালগরিদমে যদি টাইম কমপ্লিক্সিটি(complexity) অনেক বেশিও হয়ে যায় তবুও কিন্তু প্রোগ্রাম দেরিতে হলেও রান হবে বা চলবে । কিন্তু যদি সেই অ্যালগরিদম/প্রোগ্রামের বরাদ্দকৃত মেমরি অতিক্রম করে অর্থাৎ বরাদ্দকৃত মেমরি থেকে বেশি মেমরি ব্যাবহার করা হয়, তাহলে এটি চলবে না। তাই কোনো অ্যালগরিদম রচনা করার সময় আমাদের খেয়াল রাখা দরকার যে ব্যবহৃত মেমরি যাতে বরাদ্দকৃত মেমরির মধ্যে সীমাবদ্ধ থাকে ।

 

এখন কয়েকটি প্রোগ্রাম দেখি এবং স্পেস কমপ্লিক্সিটি(complexity) বের করার চেষ্টা করি ।

উদাহরণ - ০১ :

function Add(n1, n2) {
  const sum = n1 + n2;
  return sum;
}
const result = Add(10,20);
console.log(result);

জাভাস্ক্রিপ্ট প্রোগ্রামিং ভাষাতে, একটি নাম্বার মেমরিতে জায়গা নেয় 64 বিটস(bits) যাকে বাইটে কনভার্ট করলে হয় 8(আট) বাইটস(bytes) । এখন উপরোক্ত Add ফাংশনে লক্ষ্য করলে দেখবেন যে, প্রথমে এটি ২টা নাম্বার প্যাঁরামিটার হিসেবে নিচ্ছে এবং তাদের যোগফলকে sum নামের একটি ভ্যারিয়েবলে স্টোর করতেছে যা একটি নাম্বার ।

এই ফাংশনে মেমরি স্পেস হবে n1,n2,এবং sum তিনটি নাম্বার ভেরিয়েবলের ওপর নির্ভর করে । হিসাব করলে হয় 3*8 = 24 বাইটস(bytes) এখানে n1,n2 এর মান যতই হোক নাহ কেনো প্রত্যেকটার জন্য 8(আট) বাইটস(bytes) করেই মেমরি নিবে এবং তা sum ভেরিয়েবলে স্টোর হবে । তাহলে উপরোক্ত প্রোগ্রামে যেকোনো পরিস্থিতিতে n1,n2,এবং sum তিনটি নাম্বার ভেরিয়েবলের মেমরি খরচ করে ফেলবে যা একটি কন্সটেন্ট(Constant) নাম্বার । এখন বলতে পারি উপরোক্ত প্রোগ্রামের স্পেস কমপ্লিক্সিটি(complexity) অর্ডার অব ওয়ান O(1) ।

অনেকের মনে প্রশ্ন আসতে পারে যে ভাই, আমরা উপরে যে sum কে রিটার্ন এবং ফাংশনকে কল করলাম এগুলোর জন্য কি মেমরি নেয় নাহ ? উত্তর হবে হ্যাঁ নেয় কিন্তু সেগুলো অস্থায়ী(temporary) যা কাউন্ট করা হয় নাহ এসব মেমরিকে বলা হয় অক্সিলারি মেমরি(Auxiliary Space) ।

অক্সিলারি মেমরি(Auxiliary Space) কি ?

অক্সিলারি মেমরি(Auxiliary Space) হলো অতিরিক্ত বা অস্থায়ী(temporary) মেমরি যা প্রোগ্রাম এক্সিকিউশনের(Execution) সময় ব্যাবহার হয় এবং এটিকে ইনপুট মেমরিতে কাউন্ট করা হয় নাহ । উপরোক্ত ফাংশনে n1,n2,এবং sum তিনটি নাম্বার ভেরিয়েবলের মেমরিই হলো ইনপুট মেমরি ।

উদাহরণ - ০২ :

function sum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

এই ফাংশনে মেমরি স্পেস হবে sum এবং i দুইটি নাম্বার ভেরিয়েবলের ওপর নির্ভর করে যাকে আমরা ইনপুট মেমরিও বলতে পারি । তাছাড়াও উপরোক্ত প্রোগ্রামে রিটার্ন স্টেটমেন্ট, ফাংশন কল, এবং ফর লুপ আছে যারা অক্সিলারি মেমরি(Auxiliary Space) এর অন্তর্ভুক্ত । এখন তাহলে এই প্রোগ্রামের স্পেস কমপ্লিক্সিটি(complexity) নির্ণয় করা যাক -

দেখতে পাচ্ছি, ফাংশনটি একটি অ্যারে(Array) প্যাঁরামিটার হিসেবে নিচ্ছে যার নির্দিষ্ট কোনো সাইজ বলে দেওয়া নেই যখন ফাংশনকে কল করা হবে তখন যেকোন সাইজের অ্যারে(Array) প্যাঁরামিটার হিসেবে পাস করতে পারি ।

যদি প্রথমে ৫ সাইজের একটি অ্যারেকে প্যাঁরামিটার হিসেবে পাস করি, তাহলে ফর লুপটি ৫ বার চলবে এবং sum এর সাথে অ্যারে এলিমেন্টের যোগ হবে অর্থাৎ প্রত্যেক এক্সিকিউশনে i এর মান ১ করে বাড়াবে এবং sum কে আপডেট করে ফেলবে । এখানে কিন্তু অ্যারের সবগুলো মান হবে নাম্বার ডাটা-টাইপ যা প্রত্যেকে মেমরিতে ৮ বাইটস করে নেয় -

 মেমরিতে জায়গা নিচ্ছে ৫৬ বাইটস । এখন প্যাঁরামিটারে ৫ এরে পরিবর্তে ১০ সাইজের একটি অ্যারেকে পাঠায় -

 

এখন মেমরিতে জায়গা নিচ্ছে ৯৬ বাইটস । এখানে কিন্তু এই প্রোগ্রামের মেমরি অ্যারের সাইজের উপর নির্ভর করেতেছে যা লিনিয়ার । তাহলে এখন খুব সহজেই বলতে পারি যে, এই প্রোগ্রামের স্পেস কমপ্লিক্সিটি(complexity) অর্ডার অব এন O(n) ।

আজকের পর্ব শেষ করার পূর্বে, চলুন জেনে নেওয়া যাক জাভাস্ক্রিপ্টে কিছু ডাটা-টাইপের স্পেস কমপ্লিক্সিটি(complexity) -

 # space complexity in javascript

# data structure and algorithm in javascript

# javascript space and time complexity