Command Palette

Search for a command to run...

টাইম ও স্পেস কমপ্লেক্সিটি (Time & Space Complexity)
fahim
Md. Fahim Morshed
·9 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 হয় তবে এর কমপ্লেক্সিটি কত হবে ? আবারও বলছি - " ছাত্রনং অধ্যয়নং তপঃ " যারা শেষ পর্যন্ত পড়েছ তোমদের ধন্যবাদ ও স্বাগতম । ভুল ত্রুটি মার্জনীয় । আল্লাহ হফেজ ।

Comments

  • Type and hit enter to post comment
  • For multiline comments, use Shift + Enter
  • You can use markdown syntax for formatting

Cookie Consent

We use cookies to enhance your browsing experience and analyze our traffic. By clicking "Accept", you consent to our use of cookies.