অ্যালগরিদম কমপ্লেক্সিটি(বিগ "O" নোটেশন)

তুমি যখন একটা অ্যালগরিদমকে কোডে ইমপ্লিমেন্ট করবে তার আগে তোমার জানা দরকার অ্যালগরিদমটি কতটা কার্যকর। অ্যালগোরিদম লেখার আগে নিজে নিজে কিছু প্রশ্নের উত্তর দিতে হবে, যেমন: ১. আমার অ্যালগোরিদম কি নির্ধারিত সময়ের মধ্যে ফলাফল এনে দিবে? ২. সর্বোচ্চ কত বড় ইনপুটের জন্য আমার অ্যালগোরিদম কাজ করবে? ৩. আমার অ্যালগোরিদম কতখানি মেমরি ব্যবহার করছে?

আমরা অ্যালগোরিদমের কমপ্লেক্সিটি বের করে প্রথম দুটি প্রশ্নের উত্তর দিতে পারি। একটি অ্যালগরিদম যতগুলো "ইনস্ট্রাকশন" ব্যবহার করে কাজ করে সেটাই সোজা কথাই সেই অ্যালগোরিদমের কমপ্লেক্সিটি। ফলাফল আসতে কতক্ষণ লাগবে সেটা সিপিউর প্রসেসরের উপর নির্ভর করবে, কমপ্লেক্সিটি আমাদের cputime বলে দিবেনা, কমপ্লেক্সিটি আমাদের বলে দিবে আমাদের অ্যালগরিদমটি তুলনামূলকভাবে কতটা ভালো।

আর BIG $O$ নোটেশন হলো কমপ্লেক্সিটি লিখে প্রকাশ করার নোটেশন।

O(1) - Constant Time

আমরা একটা উদাহরণ দিয়ে শুরু করি। আমাদের একটি ফাংশন আছে:

int myAlgorithm(int n) {
    int x = n + 5;
    int y = x * 2;
    return y;
}

এই অ্যালগোরিদমটি $n$ এর ভ্যালু যাই হোকনা কেন সবসময় একটি constant সংখ্যক ইনস্ট্রাকশন নিয়ে কাজ করবে। অ্যালগোরিদমের কমপ্লেক্সিটি হলো $O(1)$, এর মানে হলো ইনপুটের আকার যেমনই হোকনা কেন একটি constant টাইমে অ্যালগোরিদমটি কাজ করা শেষ করবে।

O(n) - Linear Time

এবার পরের কোডটি দেখ:

int myAlgorithm(int n) {
    int sum = 0;
    for(int i=0; i<n; i++) {
        sum += i;
        if(sum > 1000) break;
    }
    return sum;
}

উপরের অ্যালগোরিদমের কমপ্লেক্সিটি $O(n)$ কারণ এখানে লুপটি $n$ বার চলবে। তুমি বলতে পারো sum যদি ১০০০ এর থেকে বড় হয় তাহলে break করে দিচ্ছি, $n$ পর্যন্ত চলার আগেই লুপটি break হয়ে যেতে পারে। কিন্তু প্রোগ্রামাররা সবসময় worst case বা সবথেকে খারাপ কেস নিয়ে কাজ করে! worst case এ লুপটি $n$ পর্যন্তইতো চলবে।

O(n²) - Quadratic Time

int myAlgorithm(int n) {
    int sum = 0;
    for(int i=0; i<n; i++) {
        for(int j=i; j<n; j++) {
            sum += i * j;
        }
    }
    return sum;
}

উপরের কোডে ভিতরের লুপটা প্রথমবার $n$ বার চলছে, পরেরবার $n-1$ বার। তাহলে মোট লুপ চলছে $(n^2+n)/2$ বার। তাই কমপ্লেক্সিটি হবে $O(n^2)$। কমপ্লেক্সিটি হিসাবের সময় constant factor গুলোকে বাদ দিয়ে দিতে হয়।

O(log n) - Logarithmic Time

পরের কোডটি দেখো:

int myAlgorithm(int n) {
    int low = 1, high = n;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(mid * mid > n) high = mid - 1;
        else low = mid + 1;
    }
    return low;
}

এটা একটা বাইনারি সার্চের কোড। প্রতিবার $low+high$ বা $n$ এর মান দুই ভাগে ভাগ হয়ে যাচ্ছে। একটি সংখ্যাকে সর্বোচ্চ কতবার ২দিয়ে ভাগ করা যায়? হিসাব করলেই বের করতে পারবে সর্বোচ্চ ভাগ করা যাবে $\log_2{n}$ বার। তারমানে কমপ্লেক্সিটি হবে $O(\log_2{n})$।

Time Limit এবং 10^8

প্রোগ্রামিং কনটেস্টে আমরা ধরে নেই জাজ এর পিসি ১ সেকেন্ডে মোটামুটি $10^8$ টা ইনস্ট্রাকশন রান করতে পারবে। কনটেস্টে প্রবলেমের ইনপুট সাইজ দেখে অনেক সময় expected algorithm অনুমান করা যায়। যেমন $n=100$ হলে সম্ভাবনা আছে এটা একটা $n^3$ কমপ্লেক্সিটির ডিপি প্রবলেম। $n=10^5$ হলে সাধারণ $O(n \log n)$ কমপ্লেক্সিটিতে প্রবলেম সলভ করতে হয় তাই সম্ভাবনা আছে এটা একটা বাইনারি সার্চ বা সেগমেন্ট ট্রি এর প্রবলেম।