টাইম ও স্পেস কমপ্লেক্সিটি

টাইম কমপ্লেক্সিটি

টাইম কমপ্লেক্সিটি নামটা শুনলে ইনিশিয়ালি মাথায় আসতে পারে, টাইম কমপ্লেক্সিটি মানে একটা কোড রান হতে কতক্ষন সময় লাগে। যেমন আমরা হয়তো মনে করতে পারি একটা কোড রান হইতে 2 সেকেন্ড সময় লাগে, তাহলে এর টাইম কমপ্লেক্সিটি হয়তো 2 সেকেন্ড। কিন্তু আসলে একটা কোড রান হতে যে সময় লাগে টা ডিভাইস, অপারেটিং সিস্টেম এইসবে ডিফার করে। যেমন একটা সেইম কোড এর রান হইতে লিনাক্স এ যে সময় লাগে ম্যাক কিংবা উইন্ডোজ এক্সপির কম র‍্যাম সহ সিস্টেমে রান টাইমে অনেক ডিফ্রেন্স থাকতে পারে। তাই কোন কোড এর রান হওয়ার সময়টা আমরা একদম ফিক্সড বলতে পারবোনা।

টাইম কমপ্লেক্সিটি আসলে কোড রান এর টাইম নিয়ে কাজ করেনা, এরা কাজ করে স্টেপ নিয়ে বা অপারেশন নিয়ে। এখানে আমরা পরিমাপ করি আমাদের কোনো ইনপুটের কারনে অপারেশন নাম্বার কেমন হবে সেটা।


    for(int i = 0; i < 5; i++) 
    {
        cout << "Hello Batman" << endl;
    }

ধরি এই কোডটির টাইম কমপ্লেক্সিটি বের করতে হবে। সেক্ষেত্রে আমাদের চিন্তা করতে হবে এটি কয়টি অপারেশন রান করছে। এখানে কোডটি n টাইম চলছে। সেক্ষেত্রে ইনপুটে যে মান দিবো কোডটি ততবার চলবে ততবার cout << "Hello Batman" >> endl; এই লাইনটি এক্সিকিউট হবে। অর্থাৎ এই কোডে টাইম কমপ্লেক্সিটি হচ্ছে অর্ডার অফ n ‘o(n)’

কিভাবে টাইম কমপ্লেক্সিটি ক্যালকুলেট করবো?

টাইম কমপ্লেক্সিটি ক্যালকুলেট করতে আমাদেরকে সবার আগে Asymptotic Notation সম্পর্কে জানতে হবে। একে আমরা টাইম কমপ্লেক্সিটির একক ও বলতে পারি।

তিন ধরনের Asymptotic Notation আছে,
1. Omega Notation(Ω)- Best Case
2. Theta Notation(θ)- Average Case
3. Big O Notation(O)- Worst Case

এখানে কেইস টি কি জিনিস? ধরি আমার কাছে একটি array আছে 7 সাইজের arr[7] = {1, 2, 3, 4, 5, 6, 7} এখানে আমাকে একটি ইন্টিজার নাম্বার কোথায় আছে খুজতে হবে। এখানে Best Case হচ্ছে 0 ইনডেক্সেই আমি আমার ইন্টিজার টা খুজে পেয়ে গেলাম। তাহলে Worst Case কি হতে পারে? একদম শেষ ইনডেক্সে যদি আমি আমার ইন্টিজার টা খুজে পাই অথবা এই array তে কোথাও না থাকে। লাস্ট ইনডেক্সে পাওয়া আর না পাওয়া একই কারন দুই ক্ষেত্রেই সেইম পরিমান অপারেশন হবে কোড রান করতে। আরে এভারেজ কেস হচ্ছে মিডেলে কোথাও পেয়ে গেলে, যেটা আমাদের বেস্ট অথবা ওর্স্ট কোন কেইসেই পরেনাই। আমরা মেইনলি টাইম কমপ্লেক্সিটি যখন বের করি তখন Worst Case নিয়ে চিন্তা করি অর্থাৎ Big O Notation ইউজ করি। যেটা প্রকাশ করা হয় O(Time Complexity) এভাবে। একে Order of n ‘O(n)’ বা Big O of n বলে।

বেসিক রুলস:
- সবসময় Worst Case নিয়ে কাজ করতে হবে।
- কনস্ট্যান্ট ইগ্নোর করতে হবে।

কনস্ট্যান্ট ইগনোর করতে হবে কারন। লুপের n এর মান এর সাথে কনস্ট্যান্ট থাকলে এটা টাইম কমপ্লেক্সিটিতে খুব একটা ডিফার করেনা। যেমন এই লুপে for(int i = 0; i < n - 1; i++) আমরা টাইম কমপ্লেক্সিটি O(n - 1) না লিখে O(n) ই লিখবো। আবার এই লুপের ক্ষেত্রেও for(int i = 0; i < 2n; i++) কমপ্লেক্সিটি হবে O(n), এক্ষেত্রে O(2n) হয়নি কারন, রিয়েল লাইফে দ্বিগুন নাম্বার কে অনেক বেশি মনে হলেও কোডের ক্ষেত্রে এটা তেমন কিছু না। কারন আমাদের কম্পাইলার যদি 10000 বার রান করতে পারে তাহলে সেটা 20000 বার অপারেশন রান করতে পারবে। অর্থাৎ কোডের ক্ষেত্রে 100 অপারেশন আর 200 অপারেশন সেইম তবে 100 অপারেশন আর 1000000 ডিফার করে।

লিনিয়ার কমপ্লেক্সিটি O(n)

নিচের কোডের প্রতিটি লাইনের কমপ্লেক্সিটি দেখি,


    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cout << i << " ";
    }

O(1) - int n;
O(1) - cin >> n;
O(n) - for(int i = 1; i ⁢= n; i++)
সবচেয়ে বড় বা Worst কমপ্লেক্সিটিই হবে ফাইনাল কমপ্লেক্সিটি অর্থাৎ O(n)

for(int i = 1; i ⁢= n; i++) এই লুপে যদি আমরা কিছু মডিফিকেশন করি -
for(int i = 1; i ⁢= n - 5; i++) এক্ষেত্রেও কমপ্লেক্সিটি হবে O(n) কারন O(n - 5) এ আমরা কন্সট্যান্ট ইগ্নোর করবো।
for(int i = 1; i ⁢= n / 5; i++) এক্ষেত্রেও কমপ্লেক্সিটি হবে O(n) কারন O(n / 5) এ আমরা কন্সট্যান্ট ইগ্নোর করবো।
for(int i = 1; i ⁢= n; i+=2)এক্ষেত্রেও কমপ্লেক্সিটি হবে O(n) কারন O(n / 2) এ আমরা কন্সট্যান্ট ইগ্নোর করবো।

নিচের কোডের প্রতিটি লাইনের কমপ্লেক্সিটি দেখি,


    int n;
    cin >> n;

    for(int i = 1; i <= n; i+=2)
    {
        cout << i << " ";
    }

    for(int i = 1; i <= n; i++)
    {
        cout << i << " ";
    }

for(int i = 1; i ⁢= n; i+=2) এই লুপের কমপ্লেক্সিটি O(n)
for(int i = 1; i ⁢= n; i++)এই লুপের কমপ্লেক্সিটি O(n)

ফাইনাল কমপ্লেক্সিটি হবে O(n + n) অর্থাৎ O(2n), এখানে কনস্ট্যান্ট 2 কে আমরা ইগ্নোর করবো তাই ফাইনাল কমপ্লেক্সিটি হবে O(n)

লগারিদমিক কমপ্লেক্সিটি O(log n)

for(int i = 1; i ⁢= n; i++) এই লুপের অনেকগুলো ভ্যারিয়েশনে কমপ্লেক্সিটি আসে O(n), যেমনঃ

for(int i = 1; i ⁢= 2 * n; i++)
for(int i = 1; i ⁢= n / 2; i++)
for(int i = 1; i ⁢= n; i+=2)

কিন্তু যদি আমরা for(int i = 1; i ⁢= n; i*=2) করি তখন কিন্তু আর অপারেশন সেইম থাকেনা। লুপের ইটারেশন অনেক কমে যায়। এই কোডের ক্ষেত্রে n = 1000 হলে i এর মান 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 টোটাল 10 বার অপারেট হচ্ছে অর্থাৎ n এর মান থেকে অনেক অনেক কম ইটারেট হচ্ছে তাই কমপ্লেক্সিটি আর O(n) থাকছে না।

তাহলে কমপ্লেক্সিটি কতো হবে? কোডের অপারেশনগুলো লক্ষ্য করি, Simple Table

1	2	4	8	16	32	64	128	256	512	...
2⁰	2¹	2²	2³	2⁴	2⁵	2⁶	2⁷	2⁸	2⁹	2^x

এখানে x বার অপারেশন হচ্ছে তাই x এর সাথে n এর কানেকশন বের করতে পারলেই আমরা আমাদের কমপ্লেক্সিটি বের করতে পারবো।

2^x = 1000
log 2 base 2^x = log 2 base 1000 (দুইপাশে 2 base লগ নিয়ে)
x log 2 base 2 = log 2 base 1000
x = log 2 base 1000 (log 2 base 2 = 1)

এখানে 2 কনস্ট্যান্ট হিসেবে আমরা বাদ দিতে পারি। সেক্ষেত্রে কমপ্লেক্সিটি দাড়ায়, O(log n)
তো সহজ ভাষায় আমাদের লুপের ইনক্রিমেন্ট/ডিক্রিমেন্ট পার্টটি যদি গুন বা ভাগ আকারে বাড়ে সেক্ষেত্রে আমরা বলতে পারবো এটি লগারিদমিক কমপ্লেক্সিটি। আরেকটি উদাহরন দেখতে পারি, for(int i = n; i >= 1; i /= 3) এই লুপের ক্ষেত্রে চোখ বন্ধ করেই বলে দিতে পারি কমপ্লেক্সিটি হবে O(log n), এখন এটি যাচাই করে নিই। n = 1000 হলে লুপটি রান করলে দেখি টোটাল রান হয় 7 বার, i এর মান যথাক্রমে, 1000, 333, 111, 37, 12, 4, 1 এখন log 3 base 1000 = 6.28 অর্থাৎ 7, এটাই এই লুপের কমপ্লেক্সিটি।

এখন আমরা এই কোডের ক্ষেত্রে কমপ্লেক্সিটি দেখি,


    int n;
    cin >> n;
    int k = 2;
   
    for(int i = 1; i < n; i++)
    {
        cout << i << endl;
        i = i * k;
    }

লুপের দিকে তাকালে দেখি ইনক্রিমেট 1 করে হচ্ছে সেক্ষেত্রে কমপ্লেক্সিটি হওয়ার কথা O(n), তবে লুপের ভেতরে i এর মান k এর সাথে মাল্টিপ্লাই হয়ে ইনক্রিমেন্ট হচ্ছে। সেক্ষেত্রে একচুয়াল কমপ্লেক্সিটি হবে O(log k base n);

স্কোয়ার-রুট কমপ্লেক্সিটি O(sqrt(N))

নিচের কোডটিতে কমপ্লেক্সিটি বের করা চেষ্টা করি,


   for(int i = 1; i <= sqrt(n); i++)
   {
        cout << i << endl;
   }

এই কোডের n = 100 হলে টোটাল আউটপুট আসে 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 অর্থাৎ 10 টি আউটপুট। এটির কমপ্লেক্সিটি O(n) বা O(log n) কোনটিই কাজ করছেনা। সেক্ষেত্রে আমরা ব্যবহার করবো স্কোয়ার-রুট কমপ্লেক্সিটি O(sqrt(N)) এখানে n = 100 এর জন্যে টোটাল অপারেশন sqrt(100) অর্থাৎ 10 হবে।

এখন একটি প্রবলেম আমরা চিন্তা করি, যেকোন নাম্বার n এর divisors বের করতে হবে। এটার সলিউশন হতে পারে এমন,


    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        if(n % i == 0) cout << i << " ";
    }

কিন্তু এখানে n এর মান যদি 10000 হয় সেক্ষেত্রে লুপ চলবে ততবার। সেক্ষেত্রে কোডটা অপটিমাইজ হলো না। কিন্তু আমরা সেইম প্রবলেমটি sqrt(n) পর্যন্ত লুপ চালিয়ে সলভ করতে পারবো।

ধরে নেই n = 36,


    int n;
    cin >> n;

    for(int i = 1; i <= sqrt(n); i++)
    {
        if(n % i == 0) cout << i << " " << n / i << " ";
    }

এই কোডে লুপ ইটারেশন,

i = 1 প্রিন্ট হবে 1, 36
i = 2 প্রিন্ট হবে 2, 18
i = 3 প্রিন্ট হবে 3, 12
i = 4 প্রিন্ট হবে 4, 9
i = 5 কন্ডিশন ম্যাচ করবেনা
i = 6 প্রিন্ট হবে 6, 6

এখানে বিচ্ছিন্নভাবে হলেও সবগুলো divisors পেয়েছি sqrt(n) বার লুপ চালিয়ে। অর্থাৎ n = 10000 হলে 10000 বার লুপ না চালিয়ে 100 বার চালালেই হবে। কোডটি অপটিমাইজ হয়ে গেলো। এছাড়াও এই for(int i = 1; i * i⁢= n; i++) লুপের ক্ষেত্রেও আমরা স্কোয়ার রুট কমপ্লেক্সিটি ইউজ করবো।

আরেকটি কোড বিশ্লেষন করি,


    int n;
    cin >> n;
    int i = 1, s = 1;

    while(s < n)
    {
        s = s + i;
        i++;
    }

এই কোডে n = 10 হলে ইটারেশন হবে,

i = 1 s = 1 + 1
i = 2 s = 1 + 1 + 2
i = 3 s = 1 + 1 + 2 + 3
i = 4 s = 1 + 1 + 2 + 3 + 4

প্রতিবার ন্যাচারাল নাম্বারের যোগফলরুপে আপডেট হচ্ছে। আমরা জানি ন্যাচারাল নাম্বারের যোগফল বের করার ফরমুলা, s = k(k + 1) / 2 যেখানে k হলো i-এর মান যা প্রতিবার 1 করে বাড়ে।

s = 1 + 1 + 2 + 3 + 4………… + k = n

অর্থাৎ 1 + k(k + 1) / 2 = n বা k^2/2 + k/2 = n এখানে ছোট ফ্যাক্টর আর কনস্ট্যান্ট বাদ দিলেই পাওয়া যাবে sqrt(n) তাই লুপ চলবে ততক্ষন-যতক্ষন এখানে k এর মান sqrt(n), এর মান sqrt(n) এর সমান হলেই লুপ শেষ। তাই টাইম কমপ্লেক্সিটি O(sqrt(n)); এখানে ছোট ফ্যাক্টর বাদ দেয়ার কারনে কিছু অপারেশন কম বেশি হতে পারে তবে কমপ্লেক্সিটি হবে O(sqrt(n)) ই।

কোয়াড্রেটিক কমপ্লেক্সিটি O(n * n) বা O(n^2)

কোয়াড্রেটিক কমপ্লেক্সিটি মূলত নেস্টেড লুপের ক্ষেত্রে ব্যবহার করা হয়। নিচের কোডটি লক্ষ করি,


   for (int i = 0; i < n; i++)
   {
       for (int j = 0; j < n; j++)
       {
           cout << "Batman" << endl;
       }       
   }

এই কোডের ক্ষেত্রে প্রথম লুপের কমপ্লেক্সিটি O(n) এবং এর ভেতরের লুপের কমপ্লেক্সিটি O(n) যেহেতু নেস্টেড লুপ তাই একচুয়াল কমপ্লেক্সিটি হবে O(n * n)

আমরা আরেকটি কোড দেখি,


    int n, m;
    cin >> n >> m;
   
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << "Batman" << endl;
        }    
    }

এই কোডের ক্ষেত্রে কমপ্লেক্সিটি হবে O(n * m) আবার তিনটা লুপ নেস্টেড আকারে থাকলে কমপ্লেক্সিটি হবে O(n^3), এরকম অনেক কমপ্লেক্সিটি হতে পারে।

লিনিয়ারিদমিক কমপ্লেক্সিটি O(n log n)

আগের সেকশনের নেস্টেড লুপের ভেতরের লুপটিতে গুন করে ইনক্রিমেন্ট করা হলো,


    for (int i = 0; i < n; i++)
    {
        for (int j = 0; i < n; i*=2)
        {
            cout << "Batman" << endl;
        }       
    }

এখন এখানে কমপ্লেক্সিটি হবে বাইরের লুপের জন্য O(n) এবং ভেতরে লুপের জন্য O(log n), তো ফাইনাল কমপ্লেক্সিটি হবে O(n log n);

Note: C++ এর ডিফল্ট sort() ফাংশন সাধারণত Introsort ব্যবহার করে, যা Quick Sort, Heap Sort, এবং Insertion Sort এর কম্বিনেশন। এর টাইম কমপ্লেক্সিটি O(n log n) হয়।

Best এবং Worst কমপ্লেক্সিটি

Simple Table

Complexity Type	Big-O Notation
Constant	O(1)
Linear	O(n)
Logarithmic	O(log n)
Square root	O(sqrt(n))
Quadratic	*O(n n)**
Linearithmic	O(n log n)

বেস্ট কমপ্লেক্সিটি বের করার জন্য n এর যেকোন একটা মান ধরে নিব এরপর সেটা সবগুলো তে বসিয়ে যার মান সবচেয়ে কম আসবে সেটা সবচেয়ে কম অপারেশন চালাবে, তাই কমপ্লেক্সিটি তত ভালো হবে।

ধরি n = 1000 হলে অপারেশন লাগবে,

Simple Table

Complexity	Operation
Constant	1
Linear	1000
Logarithmic	10
Square root	32
Quadratic	1,000,000
Linearithmic	100

এক্ষেত্রে বেস্ট কমপ্লেক্সিটির সিরিয়াল হচ্ছে Constant, Logarithmic, Square root, Linearithmic, Linear, Quadratic.

কমপ্লেক্সিটি ক্যালকুলেশন

সাধারনত আমরা বিভিন্ন অনলাইন জাজে যখন কোন প্রবলেম দেখি সেখানে আমরা 1 - 2 সেকেন্ড টাইম লিমিট দেখতে পাই। আমাদের কম্পাইলার বা অনলাইন জাজের সার্ভার 10^7 থেকে 10^8 সংখ্যক অপারেশন চালাতে পারে। এর বেশি অপারেশন চালাতে গেলে সেটা টাইম লিমিট exceed করবে। অর্থাৎ ধরি কোন একটা প্রবলেমে আমার কমপ্লেক্সিটি O(n * n), এখানে 1 ⁢= n ⁢= 10^5, এক্ষেত্রে টাইম লিমিট exceed করবে কারন n * n হবে 10^10 যা কোন সার্ভারে রান হওয়া পসিবল না।

স্পেস কমপ্লেক্সিটি

মেইনলি আমাদের কোড মেমোরিতে কেমন জায়গা দখল করছে সেটা থেকে আমরা স্পেস কমপ্লেক্সিটি বুঝতে পারি। আমরা কোন কোডে যদি একটি ভ্যারিয়েবল নিই ধরে নিই int x, এটার স্পেস কমপ্লেক্সিটি O(1) অর্থাৎ একবারই। সেইম কোডে মাল্টিপল ভ্যারিয়েবল নিলেও টাইম কমপ্লেক্সিটির মতোই এর স্পেস কমপ্লেক্সিটি কাউন্ট হবে একটি অর্থাৎ O(1). তবে টাইম কমপ্লেক্সিটি যেমন লুপে ডিফ্রেন্স ক্রিয়েট করতো ঠিক তেমনি স্পেস কমপ্লেক্সিটি ডিফ্রেন্স ক্রিয়েট করবে অ্যারে তে। একই কোডে যদি এমরা একটা অ্যারে নিই int a[n], সেক্ষেত্রে আমার স্পেস কমপ্লেক্সিটি হবে O(n). কারন তখন আমার ইনপুটের n এর উপর ডিপেন্ড করবে ভ্যারিয়েবল কতটুকু জায়গা নিবে মেমোরিতে। আবার আমরা যদি একটা 2D অ্যারে int a[n][n] নিই, সেটার স্পেস কমপ্লেক্সিটি হবে O(n * n), কারন যদি n এর মান 10 ইনপুট দিই।

আরো অনেক ধরনের টাইম ও স্পেস কমপ্লেক্সিটি হতে পারে যেটা আমরা বেসিক কমপ্লেক্সিটির মাধ্যমের বের করতে পারব। এই আর্টিকেলে খুব ইজি ভাবে বেসিক টাইম কমপ্লেক্সিটি ও স্পেস কমপ্লেক্সিটির ধারনা দেয়ার চেষ্টা করেছি। ধন্যবাদ।

টাইম ও স্পেস কমপ্লেক্সিটি - ডেটা স্ট্রাকচার

Posted by নাজিব হোসাইন নাহিন

Post a Comment

1 Comments

Popular Blog