Techdiary
টাইম ও স্পেস কমপ্লেক্সিটি (Time & Space Complexity)
fahim
Md. Fahim Morshed
·1 min read

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

কোন সমস্যা সমানের জন্য একাধিক অ্যালগরিদম থাকতে পারে । কিন্তু উপযুক্ত অ্যালগরিদম বাছাই করাও অত্যন্ত জরুরি একটি বিষয় । কিন্তু কেন ? এই প্রশ্নের উত্তর জানতে হলে " টাইম ও স্পেস কমপ্লেক্সিটি (Time & Space Complexity) " সম্পর্কে জানতে হবে । চলো প্রথমে টাইম কমপ্লেক্সিটি সম্পর্কে অবগত হই ।

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

ছবিটি লক্ষ্য করো- You.png তোমার সামনে ৩ টি রাস্তা , গন্তব্য একটাই । ৩টি রাস্তা দিয়েই তুমি তোমার গন্তব্যে পৌঁছাতে পারবে । কিন্তু একই সময়ে পৌঁছাতে পারবে কি? অবশ্যই না । way-1, way-2, way-3 এর মধ্যে way-1, way-3 এর তুলনায় way-2 দিয়ে তুমি তাড়াতাড়ি তোমার গন্তব্যে পৌঁছাতে পারবে । এতে করে তোমার সময় ও কম লাগবে । এখানেই চলে আসে টাইম কমপ্লেক্সিটি ।

এখন বলতো আমরা কম্পিউটারকে দিয়ে কেন কাজ করে নেই ? উত্তরটা হচ্ছে , কম্পিউটার খুব দ্রুত ও নির্ভুল ভাবে কাজ করতে পারে । মানুষ যে কাজ করতে ১ ঘণ্টা সময় ব্যয় করবে কম্পিউটার সেই কাজটি ১ সেকেন্ডরও কম সময়ে করে দিবে। কিন্তু যদি তা না ঘটত, তাহলে কম্পিউটারকে দিয়ে কাজ করানোর দরকারও ছিলনা । এজন্য প্রোগ্রাম লিখার সময় টাইম কমপ্লেক্সিটি খুবই গুরুত্বপূর্ণ ।

এবার কিছু উদাহরণ দেখা যাক , অমি এখানে সি প্রোগ্রামিং ভাষা ব্যাবহার করবো -

#include <stdio.h>

int main()
{
    int num1, num2, sub;
    num1 = 10;
    num2 = 5;
    sub = num1 - num2;
                
    return 0;
}

টাইম ও স্পেস কমপ্লেক্সিটি পরিমাপের জন্য বিভিন্ন গাণিতিক ফাংশন আছে, থেটা(Ѳ), ওমেগা(Ω) এবং বিগ-ও (O)। সি ভাষায় লাইব্রেরি ফাংশন ব্যাবহার করেও খুব সহজেই টাইম কমপ্লেক্সিটি বের করা যাবে। কিন্তু আমদের উদ্দেশ্য হচ্ছে একটি প্রোগ্রাম দেখই যেন বলে দিতে পারি সেই প্রোগ্রামের টাইম কমপ্লেক্সিটি কত হবে । তোমরা কি উপরের প্রোগ্রামটির টাইম কমপ্লেক্সিটি বলতে পারবে ? যারা পারবে তাদের জন্য শুভকামনা ।

এবার ব্যাখ্যা করা যাক । একটু ভালো করে লক্ষ্য করো প্রোগ্রামটিতে কয়টি কাজ হচ্ছে -

১। num1 ভেরিয়েবলের ভেতরে ১০ রাখা

২। num2 ভেরিয়েবলের ভেতরে ৫ রাখা

৩। num1, num2 ভেরিয়েবল দুটি বিয়োগ করা

৪। বিয়োগফলটি sub নামক ভেরিয়েবলে রাখা ।

এখানে দুইটি ভেরিয়েবলের যদি মান পরিবর্তন করা হয় তাহলেও কম্পিউটার ৪ টি অপারেশনই করবে । ৩টি এ্যাসাইনমেন্ট , ১টি বিয়োগ । তাহলে আমরা বলতে পারি প্রোগ্রামটির টাইম কমপ্লেক্সিটি হবে O(1) - অর্ডার অব ওয়ান । কারণটা হচ্ছে যেকোনো ইনপুটের ক্ষেত্রে প্রোগ্রামে অপারেশন সংখ্যা ধ্রুবক হলে , প্রোগ্রামটির টাইম কমপ্লেক্সিটি হবে O(1) । বোঝাতে পারছি আশা করি ।

চলো আরো একটি উদাহরণ দেখি -

#include <stdio.h>

int main()
{
    int i, n, count;

    scanf("%d", &n);

    count = 0;

    for (i = 0; i < n; i++)
    {
        count = count + 1;
    }

    printf("n = %d, count = %d\n", n, count);

    return 0;
}

এই প্রোগ্রামটির টাইম কমপ্লেক্সিটি কত হবে ? একটু মাথা খাটালেই উত্তর বলতে পারবে ।

প্রোগ্রামটি লক্ষ্য করো , প্রথমে আমরা ভেরিয়েবল ডিক্লেয়ার করেছি । তারপর ইউজারের কাছে থেকে n এর মান ইনপুট নিয়েছি । count = 0 ইনিশিয়াল করেছি , তারপর লুপ চালিয়ে i < n শর্তটি পরীক্ষা করে count = count + 1 করে মান বাড়িয়ে দিয়েছি । এখন n এর মান যত হবে, প্রোগ্রামটিও তাহলে n সংখ্যক বার চলবে এবং count = count + 1 ও n সংখ্যক বার চলবে । তাহলে এই প্রোগ্রামটির কমপ্লেক্সিটি দাঁড়াচ্ছে 0(n) ।

চলো ঝটপট আরো ১টি প্রোগ্রাম লিখে ফেলি -

#include <stdio.h>

int main()
{
   int i, j, k, n, count;

   scanf("%d", &n);

   count = 0;

   for (i = 0; i < n; i++)
   {
       for (j = 0; j < n; j++)
       {
           for (k = 0; k < n; k++)
           {
               count = count + 1;
           }
       }
   }

   printf("n = %d, count = %d\n", n, count);

   return 0;
}

প্রোগ্রামটির টাইম কমপ্লেক্সিটি হবে O(n3) কিন্তু কেন?

প্রোগ্রামে যদি ৩টি ন্যাস্টেড লুপ থাকে তাহলে কমপ্লেক্সিটি হবে O(n3) , আবার ২ টি ন্যাস্টেড লুপ থাকলে কমপ্লেক্সিটি হবে O(n2) । আশা করি বুঝাতে পেড়েছি ।

যদি বুঝে থাক তাহলে নিচের প্রোগ্রামটির কমপ্লেক্সিটি কত হবে ? উত্তরটি নিচে কমেন্টে করে জানিয়ে দিও ।

#include <stdio.h>

int main()
{
    int i, j, n, count;

    scanf("%d", &n);

    count = 0;

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            count = count + 1;
        }
    }

    for (i = 0; i < n; i++)
    {
        count = count + 1;
    }

    printf("count= %d\n", count);

    return 0;
}

[ NOTE: কোন প্রোগ্রামে ১ টি স্টেটমেন্ট থাকলেও কমপ্লেক্সিটি 0(1) . ১০ টি স্টেটমেন্ট থাকলেও কমপ্লেক্সিটি 0(1) । কারণ 0(1) দ্বারা আসলে একটি অপারেশন বোঝায় না , বোঝায় ধ্রুবক অপারেশন । এখন বাকি প্রোগ্রামের কমপ্লেক্সিটি যদি O(n) হয় , তবে কমপ্লেক্সিটি হবে O(n) + O(1) = O(n) । কারণ টা কি জান ? অমিই বলে দিচ্ছি - O(n) এর তুলনায় O(1) অনেক ছোট / নগণ্য , তাই O(1) আমরা গণ্য করবো না । ঠিক যেমন বাসে যাওয়ার সময় ছোট বাচ্চাদের কোলে নিলে বাস ভাড়া দেওয়া লাগে না । তাহলে O(n5) + O(n4) + O(n3) + O(n2) + O(n1) = কত ? ]

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

কম্পিউটারকে দিয়ে দ্রুত কাজ করিয়ে নেওয়ার সাথে সাথে আমাদের দেখতে হবে সেটি কতটুকু মেমরি ব্যাবহার করছে । আমরা যারা কম্পিউটার সম্পর্কে একটু হলেও জানি , তারা নিশ্চয় জানি যে কম্পিউটারের ডেটা মেমরিতে সংরক্ষণ করা হয় । বিভিন্ন ধরনের মেমরি হয়ে থাকে নিচের চিত্র দেখলে বুঝতে পারবে- Register.png চিত্রটিতে মেমরিগুলোর ধারণ ক্ষমতা ও গতির তুলনা তুলে ধরা হয়েছে । মেমরি সম্পর্কে বিস্তারিত জনার জন্য নেট থেকে সার্চ করে জেনে নিবে । ছাত্রনং অধ্যয়নং তপঃ । স্পেস কমপ্লেক্সিটি পরিমাপের জন্য বিগ ০ নোটেশন ব্যাবহার করা হয় । একটি উদাহরণ দিয়ে বিষয়টি বুঝাবার চেষ্টা করি -

#include <stdio.h>

int main()
{
    int num;
    num = 10;
             
    return 0;
}

একটু আগেই আমরা জেনেছি টাইম কমপ্লেক্সিটি কীভাবে বের করতে হয়। সুতরাং এর টাইম কমপ্লেক্সিটি হবে O(1)। তাহলে এর স্পেস কমপ্লেক্সিটি কত হবে কেউ কি বলতে পারবে ? এর স্পেস কমপ্লেক্সিটিও হবে O(1) । কিন্তু কেন ? কারণটা হচ্ছে num এর মান যাই হোক না কেন আমরা প্রোগ্রামটিতে ১ টি মাত্র ভেরিয়েবল ব্যবহার করেছি , যা একটি ইন্টেজার ভেরিয়েবল । ইন্টেজার ৪ বাইট মেমরি ব্যবহার করে । num এর মান ১ হলেও ৪ বাইট জায়গা নিবে আবার ১০০০০০ হলেও ৪ বাইত জায়গা নিবে । আর একটি উদাহরণ দেখা যাক-

int main()
{
	int i, num, even_list[51];
    
    for(i = 0; i < 101; i++)
    {
    	even_list[i] = 0;
    }
    
    for(i = 0; i < 51; i+=2)
    {
    	even_list[i] = 1;
    }
    
    num = 10;
    
    if(even_list[num])
    {
    	printf("even");
    }
    else{
    	printf("odd");
    }
    
    return 0;
}

এর স্পেস কমপ্লেক্সিটি কত হবে ? এর স্পেস কম্পেক্সিটি হবে O(n)। কিন্তু কেন এবং কিভাবে ? এখানে বলা হয়েছে num এর সর্বোচ্চ মান হবে ৫০ , তাই আমরা even_list টিতে ৫১ নিয়েছি । যদি বলা হত num এর মান ৫০০ তাহলে লিস্টটিতে ৫০১ নিতাম । আমরা দেখতে পাচ্ছি num এর মানের সাথে সমানুপাতিক হারে স্পেস বাড়ছে । তাই এর স্পেস কমপ্লেক্সিটি হবে O(n) । আশা করি বুঝাতে পেরেছি । এখন অ্যারেটি যদি 2D/3D হয় তবে এর কমপ্লেক্সিটি কত হবে ? আবারও বলছি - " ছাত্রনং অধ্যয়নং তপঃ " যারা শেষ পর্যন্ত পড়েছ তোমদের ধন্যবাদ ও স্বাগতম । ভুল ত্রুটি মার্জনীয় । আল্লাহ হফেজ ।