টাইম কমপ্লেক্সিটি || কোডের পারফরম্যান্স বোঝার সহজ উপায়

 

প্রোগ্রামিং শিখতে গেলে আমরা সাধারণত প্রথমেই কোড কিভাবে কাজ করে তা বুঝতে চেষ্টা করি। কিন্তু একটা বড় প্রশ্ন হলো – "এই কোডটি কত দ্রুত রান করবে?" অর্থাৎ, একটি নির্দিষ্ট ইনপুটের জন্য আমাদের কোড কত সময় নিবে? এই প্রশ্নের উত্তর খুঁজতে গেলে আমাদের বুঝতে হবে টাইম কমপ্লেক্সিটি।

টাইম কমপ্লেক্সিটি মূলত বলে দেয় একটি অ্যালগরিদম কীভাবে বড় ইনপুটের ক্ষেত্রে আচরণ করবে। এটি বোঝার জন্য আমাদের কিছু গাণিতিক প্রকাশ এবং ধারণা জানতে হবে। চলুন ধাপে ধাপে টাইম কমপ্লেক্সিটির বিভিন্ন বিষয় বুঝে নেই।

---

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

একটি অ্যালগরিদম কতবার রান হবে বা এক্সিকিউশন সময়ের সাথে ইনপুটের সম্পর্ক কেমন হবে, সেটাই টাইম কমপ্লেক্সিটি। এটাকে সাধারণত Big-O নোটেশন দ্বারা প্রকাশ করা হয়।

উদাহরণস্বরূপ, যদি আমাদের একটি অ্যারে থাকে এবং আমরা সেটার সব উপাদান প্রিন্ট করতে চাই, তাহলে আমাদের লুপ ইনপুটের সাথে বাড়বে।

#include <iostream>
using namespace std;

int main() {
    string friends[] = {"abul", "babul", "cabul", "dabul"};
    int n = sizeof(friends) / sizeof(friends[0]);
    
    for(int i = 0; i < n; i++) {
        cout << friends[i] << endl;
    }
    return 0;
}

এই ক্ষেত্রে, যদি অ্যারেতে n সংখ্যক উপাদান থাকে, তাহলে আমাদের লুপ n বার চলবে। তাই, এই লুপের টাইম কমপ্লেক্সিটি O(n)।

---

বিভিন্ন টাইম কমপ্লেক্সিটির প্রকারভেদ

টাইম কমপ্লেক্সিটি বিভিন্ন ধরণের হতে পারে। সবচেয়ে কমন টাইম কমপ্লেক্সিটি গুলো নিচে ব্যাখ্যা করা হলো:

 ১. O(1) – কনস্ট্যান্ট টাইম কমপ্লেক্সিটি

যদি কোন অ্যালগরিদম সব সময় এক নির্দিষ্ট সময়ে রান হয়, ইনপুটের আকার বড় হোক বা ছোট, তাহলে তাকে O(1) বলা হয়।

#include <iostream>
using namespace std;

int main() {
    string friends[] = {"abul", "babul", "cabul", "dabul"};
    cout << friends[2] << endl; // কেবল একটি নির্দিষ্ট ইন্ডেক্স থেকে উপাদান বের করা
    return 0;
}

এখানে আমরা সরাসরি একটি নির্দিষ্ট ইন্ডেক্সে যাচ্ছি, ফলে টাইম কমপ্লেক্সিটি O(1)। কারণ, এখানে ইনপুট যত বড়ই হোক, এটি সর্বদা একবারেই রান হবে।

---

২. O(n) – লিনিয়ার টাইম কমপ্লেক্সিটি

যদি কোন লুপ বা প্রসেস ইনপুটের আকার অনুযায়ী সরাসরি বৃদ্ধি পায়, তাহলে তার কমপ্লেক্সিটি O(n)। যেমন:

#include <iostream>
using namespace std;

int main() {
    string friends[] = {"abul", "babul", "cabul", "dabul"};
    int n = sizeof(friends) / sizeof(friends[0]);
    
    for(int i = 0; i < n; i++) {
        cout << friends[i] << endl;
    }
    return 0;
}

এই ক্ষেত্রে, যদি n = ১০০ হয়, তাহলে লুপ ১০০ বার চলবে। তাই, টাইম কমপ্লেক্সিটি O(n)।

---

৩. O(n^2) – কোয়াড্রাটিক টাইম কমপ্লেক্সিটি

যদি একটি লুপের ভিতরে আরেকটি লুপ থাকে, তাহলে টাইম কমপ্লেক্সিটি O(n^2) হয়। যেমনঃ

#include <iostream>
using namespace std;

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

এখানে বাইরের লুপ n বার চলবে, আর প্রতিটি বাইরের লুপের জন্য ভিতরের লুপও n বার চলবে। ফলে মোট রান হবে n × n = n^2। তাই, টাইম কমপ্লেক্সিটি হবে O(n^2)।

---

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

যদি প্রতিবার ইনপুটের সাইজ অর্ধেক করে কমতে থাকে, তাহলে এটি O(log n) টাইম কমপ্লেক্সিটির মধ্যে পড়ে। সবচেয়ে ভালো উদাহরণ Binary Search।

#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    cout << "Found at index: " << binarySearch(arr, 0, n - 1, target) << endl;
    return 0;
}

এখানে, প্রত্যেক ধাপে অ্যারের অর্ধেক বাদ চলে যায়, ফলে ইনপুট n হলে রান হবে log n বার। তাই টাইম কমপ্লেক্সিটি O(log n)।

---

৫. O(n log n) – লগ-লিনিয়ার টাইম কমপ্লেক্সিটি

বেশিরভাগ efficient sorting algorithm, যেমন Merge Sort এবং Quick Sort , টাইম কমপ্লেক্সিটি O(n log n) থাকে।

#include <iostream>
#include <vector>
using namespace std;

void mergeSort(vector<int>& arr) {
    if (arr.size() <= 1) return;
    // Sorting logic (not fully implemented here)
}

int main() {
    vector<int> arr = {4, 2, 8, 5, 7};
    mergeSort(arr);
    return 0;
}

---

টাইম কমপ্লেক্সিটি বুঝলে আপনি জানতে পারবেন কোন অ্যালগরিদম বড় ইনপুটের ক্ষেত্রে ভালো পারফর্ম করবে।

- O(1) → দ্রুততম (কনস্ট্যান্ট টাইম)

- O(log n) → দ্রুত (বাইনারি সার্চের মতো)

- O(n) → মাঝারি (লিনিয়ার লুপ)

- O(n log n) → কার্যকরী (Merge Sort, Quick Sort)

- O(n^2) → ধীর (নেস্টেড লুপ)

✒️Al Kayes Rifat

Blog Link :  https://alkayesblog.netlify.app/blog/time-complexity

#algorithms