Complexity - Data Structure & Algorithm

প্রোগ্রামিং এ কমেপ্লেক্সিটি ২ ধরনের

• টাইম কমেপ্লেক্সিটি ( Time Complexity )
• স্পেস কমেপ্লেক্সিটি ( Sapce Complexity )

টাইম কমেপ্লেক্সিটি ( Time Complexity )

প্রোগ্রাম বা কোড লেখার পর তা রান করতে কিছুটা সময় লাগে । ওই কোড রান হতে কতটা সময় লাগবে তা নির্ভর করে ওই কোড টা কিভাবে লেখা হয়েছে তার ওপর। এক্ষেত্রে একই কোড ভিন্ন ভিন্ন ইনপুট এর জন্য ভিন্ন ভিন্ন সময় লাগতে পারে। মুলত এইটাকে টাইম কমেপ্লেক্সিটি ( Time Complexity ) বলে।

সাধারন ভাবে বললে, একটি প্রোগ্রাম রান করতে কতখানি সময় নেয় তাকেই টাইম কমেপ্লেক্সিটি বলে। কিন্তু এই উক্তিটা টা সম্পূর্ন ভাবে সত্যি না। কিন্তু কেন?

আমরা সাধারন ভাবে টাইম কমেপ্লেক্সিটি বলতে সময়কে বুঝিয়ে থাকি। কিন্তু একবার ভেবে দেখুন তো, একই কোড একটা সাধারন কম্পিউটারে রান হতে কম সময় লাগবে নাকি সুপার কম্পিউটারে রান হতে কম সময় লাগবে?

উত্তর টা খুবই সহজ। সুপার কম্পিউটারে। তাহলে কি হল এখানে? টাইম কমেপ্লেক্সিটির সংজ্ঞা তো মিলছে না। তাহলে সংজ্ঞা টা কি ভুল ? না।

টাইম কমেপ্লেক্সিটি বলতে মুলত বোঝায় একটা প্রোগ্রাম রান হতে কত ইউনিট পরিমান সময় লাগবে। এখানে মনে রাখতে হবে এই সময় বলতে কিন্তু প্রোগ্রাম রান হওয়ার সম্পূর্ন সময় কে বোঝায় না। বিষয় টা একটু গোলমেলে মনে হচ্ছে তাই না। একটা উদাহরন দিলে বিষয়টি বুঝতে পারবেন।

function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 2;

findValue(array, target)

উপরে কোডে টাইম কমেপ্লেক্সিটি কত হবে?

টাইম কমেপ্লেক্সিটি নির্ভর করে কোডের ইনপুটের উপর। এখানে একটা লুপ চলেছে এবং লুপ টা n (n হচ্ছে array এর length) পরিমান সময় ধরে চলেছে। তাহলে এখানে টাইম কমেপ্লেক্সিটি হবে O(n) (Order of n) or ( Big O of n)

বিঃদ্রঃ বোঝার সুবিধার্থে array এর length কে n ধরে নিব।

function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return arr[i];
    }
  }
}

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 2;

findValue(array, target)

এখানে টাইম কমেপ্লেক্সিটি কত হবে?

উপরের কোড দেখে বোঝায় যাচ্ছে for লুপ ২ বার চলে থেমে যাবে। তাহলে সাধারন ভাবে এখানে টাইম কমেপ্লেক্সিটি O(2) হবে , তাই না। তাই তো হওয়ার কথা।

এখানে লুপ ২ বার চলছে কারন target ভ্যালু 1 ইনডেক্স এ আছে। কিন্তু যদি target ভ্যালু সবার শেষে থাকত তাহলে কি হত? তাহলে তো টাইম কমেপ্লেক্সিটি O(n) হত।

টাইম কমেপ্লেক্সিটি নির্ণয় করতে হলে কিছু নিয়ম মেনে চলা হয় ।

• সব সময় worst-case কে ধরা হয়।
• constant ভ্যালুকে avoid করা হয় ।

• সব সময় বড় ভ্যালু কে প্রাধান্য দেওয়া হয়।

  মনে করুন আপনার আপনার কোডে দুই টা অংশের প্রথমটাতে O(n^2) এবং শেষটাতে O(n) হয়েছে । এখানে আমাদেরকেে O(n^2) কে ধরতে হবে কারন n^2, n এর থেকে বড়।
  

function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; i < arr[i].length; i++) {
      if (arr[i] === target) {
        return arr[i];
      }
    }
  }
}

const array = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
const target = 2;

findValue(array, target);

এই কোডের টাইম কমেপ্লেক্সিটি কত হবে?

এখানে লক্ষ্য করলে দেখবেন যে, প্রথমে array এর জন্য একটা লুপ চলেছে , তার ভিতরে নেস্টেট array গুলোর জন্য আবার লুপ চলেছে । এখন array এর lenght কে n এবং নেস্টেট array এর length কে m ধরি তাহলে হিসাব টা ধারাবে ঠিক এই রকম

O(n) * (O(m) + O(m) + O(m))
O(n) * 3 O(m);
O(n) * O(m)
O(n*m)

তাহলে উপরোক্ত কোডের টাইম কমেপ্লেক্সিটি হবে O(n*m)

Source: Collected from google

উপরে ছবিতে বিভিন্ন টাইম কমেপ্লেক্সিটির জন্য চার্ট দেওয়ার হয়েছে। এর ভিতরে O(1) হলে সব থেকে ভালো। এই কমেপ্লেক্সিটির কোডে আপনি ইনপুুট যাই দিন না কেন constant সময়ে রান হবে।

মনে করুন , আপনাকে ১ থেকে ১০০ পর্যন্ত সকল সংখ্যার গুলোর যোগফল নির্ণয় করা কোড লিখতে বলা হল । তাহলে আপনি কি সহজ ভাবে এই ভাবে কোড লিখবেন

const start = 1;
const end = 100;
const total = 0
for(let i = start; i <= end; i++){
    total += i
}

এখানে কোডের টাইম কমেপ্লেক্সিটি হবে O(n)

বিঃদ্রঃ এখানে n হচ্ছে শেষ সংখা

এখন এখানে যদি ধারার গাণিতিক সূত্র প্রয়োগ করি তাহলে কোড এই রকম হবে ।

const *total* = **(100 **/ **2) *** **(2 *** **1 **+ **(100 **- **1) *** **1);

এখানে শুধু মাত্র একবার হিসাব নিকাশ হবে। এখানে ইনপুটের সংখা যাই একবারই ক্যাকুলেশন হবে।

এক্ষেত্রে টাইম টাইম কমেপ্লেক্সিটি হবে O(1)

স্পেস কমেপ্লেক্সিটি ( Space Coplexity )

একটি প্রোগ্রাম রান হতে কি পরিমান মেমরি ব্যবহৃত হবে, তাই হচ্ছে স্পেস কমেপ্লেক্সিটি।

টাইম কমেপ্লেক্সিটি বুঝলে আপনি স্পেস কমেপ্লেক্সিটি বুঝতে পারবেন। টাইম কমেপ্লেক্সিটি এর ক্ষেত্রে আমরা সময় নিয়ে হিসাব নিকাশ করতাম কিন্তু এখানে স্পেস বা মেমরি নিয়ে হিসাব নিকাশ করব এবং বাকি সব নিয়ম কানুন সব ঠিক থাকবে।

এবার যদি উপরে লেখা সব কোড গুলো এক এক করে স্পেস কমেপ্লেক্সিটি বের করি তাহলে বিষয় আরো পরিষ্কার হবে ।

function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 2;

findValue(array, target)

এখানে স্পেস কমেপ্লেক্সিটি হবে O(n) । কারন এখানে array তে n পরিমান ডাটা store করা হয়েছে।

function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return arr[i];
    }
  }
}

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const target = 2;

findValue(array, target)

এখানে কোডের স্পেস কমেপ্লেক্সিটি হবে O(n) ।

function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; i < arr[i].length; i++) {
      if (arr[i][j] === target) {
        return arr[i][j];
      }
    }
  }
}

const array = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
const target = 2;

findValue(array, target);

কিন্তু এখানে স্পেস কমেপ্লেক্সিটি হবে O(n*m) । এখানে n হচ্ছে array এর length আর m হচ্ছে নেস্টেট array এর length

const start = 1;
const end = 100;
const total = 0
for(let i = start; i <= end; i++){
    total += i
}

const *total* = **(100 **/ **2) *** **(2 *** **1 **+ **(100 **- **1) *** **1);

কিন্তু এই দুই টা কোডে স্পেস কমেপ্লেক্সিটি হবে O(1) । বুঝতে একটু কষ্ট হচ্ছে, তাই না?

আপনার এখন ঠিক এই রকম উক্তি ঘোরপাক খাচ্ছে, ২য় কোডে একটা ওটা না বুঝলাম কিন্তু প্রথমে টা অনেক গুলা মান এসাইন করা তাহলে তো আর বেশি হবে।

আচ্ছা একটু হিসাব করি চলুন

এখানে প্রত্যক ভেরিবল এর জন্য স্পেস কমেপ্লেক্সিটি হবে O(1) । এখান

ভেরিএবল আছে মোট 4 টা তাহলে হিসাব টা হবে ঠিক এরকম

O(1) + O(1) + O(1) + O(1)
= 4 O(1)
= O(1)

টাইম কমেপ্লেক্সিটির সময় জেনেছি যে ধ্রুবক বা constant মানকে avoid করে বা এড়িয়ে নির্ণয় করতে হয়।

তাহলে স্পেস কমেপ্লেক্সিটির হবে O(1)

এখন এই কোডের স্পেস কমেপ্লেক্সিটি কত হবে?

function findValue(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; i < arr[i].length; i++) {
      if (arr[i][j] === target) {
        return arr[i][j];
      }
    }
  }
}

এখানেও স্পেস কমেপ্লেক্সিটি হবে O(1) ।

এখানে লক্ষ্য করলে দেখবেন এখানে শুধুমাত্র একটা ফাংশন ডিফাইন করেছি এবং শুধু মাত্র এই ফাংশনের স্পেস কমেপ্লেক্সিটি বের করতে হবে। এখানে লক্ষ্য করলে দেখবেন এখানে দুইটা constant স্পেস নিচ্ছে। এখানে দুইটি ভেরিএবল আছে আর তারা একবার ই এসাইন আচ্ছে এবং পরবর্তীতে আপডেট হচ্ছে ।

প্রয়োজনীয়তা

টাইম কমেপ্লেক্সিটি বা স্পেস কমেপ্লেক্সিটি দুই টা জিনিসই প্রোগ্রামিং এর জন্য খুবই গুরুত্বপূর্ণ। এই দুইটা জিনিসের মাধ্যমে একটা প্রোগ্রাম কতটা efficient তা বোঝা যায়।

ছোট ইনপুটের জন্যে টাইম কমেপ্লেক্সিটি বা স্পেস কমেপ্লেক্সিটি তেমন একটা প্রয়োজন হয় না। কিন্তু যখনই অনেক বড় ইনপুট এর কথা চিন্তা করা হবে তখন টাইম কমেপ্লেক্সিটি বা স্পেস কমেপ্লেক্সিটি অবশ্যই প্রয়োজন হবে।

Short Note

Time Complexity - সময় হিসাব করা হয়
Space Complexity - স্পেস বা মেমরী হিসাব করা হয়
O() - Big O Notation
0(1) - Constant Complexity