কমপ্লেক্সিটি — Big-O দিয়ে গতি মাপা

১ · নতুন মডিউল — “চলে” থেকে “দ্রুত চলে”

অভিনন্দন — পাঁচটি মডিউল পেরিয়ে আপনি এখন linked list, stack, queue, tree, hash table আর graph চেনেন। এবার শুরু হলো মডিউল ৬, “অ্যালগরিদম ও প্রবলেম সলভিং”. এতদিন প্রশ্ন ছিল “কোডটা কি ঠিক উত্তর দেয়?” এখন থেকে আরেকটি প্রশ্ন যোগ হবে: “ডেটা ১০ লাখ গুণ বড় হলেও কি এটি সময়মতো উত্তর দেবে?” এই মডিউলে আমরা সর্টিং, সার্চিং, ডায়নামিক প্রোগ্রামিং, greedy আর কনটেস্টের কৌশল দেখব। কিন্তু সবগুলোর আগে দরকার একটি মাপকাঠি — আর সেটিই এই পর্বের বিষয়।

একটি ঘটনা দিয়ে শুরু করি। নাদিয়া একটি কোচিং সেন্টারের জন্য প্রোগ্রাম লিখল। ১০০ জন ছাত্রের তালিকায় একই নাম দুবার আছে কি না, তা খুঁজে বের করে। ল্যাপটপে চোখের পলকে উত্তর এলো। পরে বোর্ডের ফলাফলের ১০ লাখ রেকর্ডে সেই একই প্রোগ্রাম চালানো হলো — আর সারা রাত পেরিয়েও শেষ হলো না। কোডে কোনো bug ছিল না। সমস্যা ছিল অ্যালগরিদমের বৃদ্ধির ধরনে।

সেকেন্ড কেন ভালো মাপকাঠি নয়

“এই প্রোগ্রাম ০.৩ সেকেন্ড নেয়” — কথাটি শুনতে নির্দিষ্ট, কিন্তু আসলে প্রায় অর্থহীন। একই কোড:

• মেশিনভেদে বদলায়: নতুন গেমিং ল্যাপটপ আর পাঁচ বছরের পুরোনো অফিস কম্পিউটারে সময় কয়েক গুণ আলাদা।
• চাপভেদে বদলায়: পাশে ব্রাউজারে দশটি ট্যাব খোলা থাকলে, বা অ্যান্টিভাইরাস স্ক্যান চললে সময় বেড়ে যায়।
• ভাষা ও compiler-ভেদে বদলায়: একই অ্যালগরিদম C-তে -O2 দিয়ে, আর Python-এ — সময়ের পার্থক্য দশ গুণ বা তারও বেশি হতে পারে।

২ · ধাপ গোনা — ইনপুট বাড়লে কাজ কত বাড়ে

ধাপ গোনার জন্য গণিতবিদ হতে হয় না। শুধু জিজ্ঞেস করুন: “কোন লাইনটি কতবার চলে?” নাদিয়ার duplicate খোঁজার কোড ছিল এরকম — প্রতিটি নামকে বাকি প্রতিটি নামের সাথে মেলানো। এটি একটি nested loop. একে ছোট n দিয়ে হাতে গুনে দেখি। n = ৪ ধরে “পরে” চাপুন:

1int count = 0;2for (int i = 0; i < n; i++)3    for (int j = 0; j < n; j++)4        count++;      /* basic step */5printf("count = %d\n", count);

একটি ছোট উন্নতি করা যায়: প্রতিটি জোড়া একবারই দেখলে চলে, তাই ভেতরের লুপ j = i + 1 থেকে শুরু করা যায়। তখন ধাপ হয় ৩ + ২ + ১ + ০ = ৬, সাধারণভাবে n(n − 1) / 2. কাজ প্রায় অর্ধেক হলো — কিন্তু n = ১০ লাখে সেটিও প্রায় ৫০ হাজার কোটি। অর্ধেক করা ভালো, কিন্তু বৃদ্ধির ধরন বদলায়নি: n দ্বিগুণ হলে কাজ এখনো চার গুণ।

৩ · Big-O — শুধু বড় ছবিটা দেখা

ধরুন হিসাব করে পেলেন, একটি প্রোগ্রাম মোট 3n² + 100n + 5000 টি ধাপ নেয়। এই পুরো সূত্র মনে রাখা ঝামেলার। Big-O notation একে ছোট করে লেখে: O(n²). কীভাবে? দুটি নিয়মে:

1. সবচেয়ে দ্রুত বাড়া পদটি রাখুন, বাকিগুলো বাদ দিন। n = ১০ হলে 3n² = ৩০০ আর 5000 বড় দেখায়। কিন্তু n = ১০ লাখে 3n² = ৩ × ১০¹², আর 100n মাত্র ১০⁸ — তুলনায় প্রায় শূন্য। n যত বাড়ে, সবচেয়ে বড় পদটিই সব দখল করে নেয়।
2. ধ্রুবক গুণ বাদ দিন। 3n² আর n²-এর পার্থক্য তিন গুণ — ঠিক যেমন দ্রুত আর ধীর কম্পিউটারের পার্থক্য। মেশিন বদলালে এটি বদলায়, তাই এটি অ্যালগরিদমের মৌলিক বৈশিষ্ট্য নয়। কিন্তু n দ্বিগুণ হলে কাজ চার গুণ হওয়া — এটি যেকোনো মেশিনে সত্য।

একটু আনুষ্ঠানিকভাবে বললে: f(n) = O(g(n)) মানে এমন একটি ধ্রুবক c আর একটি শুরুর বিন্দু n₀ আছে, যার পর থেকে সবসময় f(n) ≤ c · g(n). অর্থাৎ যথেষ্ট বড় n-এ, কোনো এক ধ্রুবক গুণ বাদে, g(n) হলো f(n)-এর ওপরের সীমা. ইনপুট খুব বড় হলে খরচ কেমন আচরণ করে, শুধু সেদিকে তাকানোর এই পদ্ধতিকে বলে asymptotic analysis.

Best, average আর worst case

একই অ্যালগরিদম ইনপুটভেদে ভিন্ন সময় নিতে পারে। ক্লাসের হাজিরা খাতায় রোল নম্বর না জেনে “রাফি” নামটি খুঁজছেন, ওপর থেকে একজন একজন করে — অর্থাৎ linear search:

সাধারণত “এই অ্যালগরিদম O(n)” বললে worst case বোঝানো হয়। ব্যতিক্রম আছে — hash table-এর “O(1)” আসলে average case; worst case O(n). কোনটির কথা হচ্ছে, তা সবসময় জিজ্ঞেস করে নেওয়া ভালো অভ্যাস।

Ω আর Θ — দুটি ভাইবোন চিহ্ন

যেমন linear search-এর worst case Θ(n): n টির কম তুলনায় নিশ্চিত হওয়া যায় না যে নামটি নেই, আবার n-এর বেশিও লাগে না। কঠোর গণিতে O(n²) লেখাও ভুল নয় (ওপরের সীমা তো!), কিন্তু তাতে তথ্য কমে যায়। বাস্তবে প্রোগ্রামাররা “O” বলেন, কিন্তু প্রায়ই মনে মনে Θ বোঝান।

৪ · ছয়টি পরিচিত শ্রেণি — O(1) থেকে O(2ⁿ)

বাস্তবে যত অ্যালগরিদম দেখবেন, তার বেশিরভাগই নিচের ছয়টি শ্রেণির কোনো একটিতে পড়ে। প্রতিটির জন্য একটি চেনা দৃশ্য মনে রাখুন:

সংখ্যাগুলো পাশাপাশি রাখলে পার্থক্যটা গায়ে লাগে। নিচের টেবিলে মোটামুটি কত ধাপ লাগে, দেখুন (log মানে এখানে log₂, আর মান গোল করা):

একটি সাধারণ কম্পিউটার সেকেন্ডে মোটামুটি ১০⁸ (১০ কোটি) সরল ধাপ করতে পারে — এটি একটি মোটা দাগের আন্দাজ, যা অংশ ৮-এ আবার দেখব। সেই হিসাবে n = ১০ লাখে O(n log n) লাগে এক সেকেন্ডের অনেক কম, O(n²) প্রায় ১০,০০০ সেকেন্ড — প্রায় পৌনে তিন ঘণ্টা। আর n = ১,০০০-এ O(2ⁿ)? মহাবিশ্বের বয়স সেকেন্ডে হিসাব করলে ১০¹⁸-এরও কম; এখানে ধাপ ১০³⁰¹. কোনো কম্পিউটারই কখনো এটি শেষ করতে পারবে না।

এবার একটি দৌড় দেখুন। প্রতিটি ধাপে n দ্বিগুণ হচ্ছে — কোন শ্রেণির কাজ কতটা লাফ দেয়, খেয়াল করুন:

৫ · log n-এর জাদু — প্রতি ধাপে অর্ধেক

log n শব্দটি অনেকের কাছে স্কুলের গণিতের ভয় ফিরিয়ে আনে। কিন্তু প্রোগ্রামিংয়ে এর অর্থ খুব সহজ: log₂ n = n-কে কতবার অর্ধেক করলে ১-এ পৌঁছায়. ১৬ → ৮ → ৪ → ২ → ১: চারবার, তাই log₂ ১৬ = ৪. পর্ব ২-এ ১ থেকে ১০০-এর মধ্যে সংখ্যা আন্দাজের খেলায় আপনি দেখেছিলেন, সবচেয়ে বেশি ৭টি প্রশ্নই যথেষ্ট। এবার সেই binary search চালাই ১০ লাখ সাজানো রোল নম্বরের ওপর:

log-এর base কেন লেখা হয় না

O(log n) লেখার সময় কেউ log₂ না log₁₀, তা বলে না। কারণ base বদলালে শুধু একটি ধ্রুবক গুণ বদলায়: log₂ n = ৩.৩২ × log₁₀ n (প্রায়)। আর Big-O ধ্রুবক গুণ বাদ দেয়। তাই সব log একই শ্রেণির। তিন ভাগে ভাগ করা অ্যালগরিদমও O(log n), আধাআধি ভাগ করাটিও O(log n).

৬ · কোড দেখে complexity পড়া

বেশিরভাগ ক্ষেত্রে complexity বের করতে কোনো সূত্র লাগে না — কয়েকটি প্যাটার্ন চিনলেই চলে। প্রশ্ন একটাই: “n-এর সাথে কোন লাইনটি কতবার চলে?”

কথাগুলো নিজে মেপে দেখুন। নিচের প্রোগ্রাম তিন রকম লুপে মৌলিক ধাপ গোনে, আর প্রতিবার n দ্বিগুণ করে:

#include <stdio.h>

int main(void) {
    printf("%6s %8s %10s %8s\n", "n", "linear", "nested", "halving");
    for (int n = 1000; n <= 8000; n *= 2) {
        long long lin = 0, nest = 0, half = 0;
        for (int i = 0; i < n; i++) lin++;              /* O(n)     */
        for (int i = 0; i < n; i++)                     /* O(n^2)   */
            for (int j = 0; j < n; j++) nest++;
        for (int k = n; k > 0; k /= 2) half++;          /* O(log n) */
        printf("%6d %8lld %10lld %8lld\n", n, lin, nest, half);
    }
    return 0;
}

রিকার্শন — call tree গুনে দেখা

রিকার্সিভ ফাংশনে লুপ চোখে পড়ে না, তাই complexity বুঝতে call tree আঁকতে হয়। পর্ব ১৫-এর সেই সরল Fibonacci মনে করুন: fib(n) = fib(n-1) + fib(n-2). প্রতিটি কল আরও দুটি কল করে। fib(5)-এর গাছে মোট ১৫টি কল, fib(40)-এ ৩৩ কোটিরও বেশি (৩৩,১১,৬০,২৮১টি)।

                    fib(5)
            /                  \
        fib(4)                fib(3)
       /      \              /      \
   fib(3)    fib(2)      fib(2)    fib(1)
   /    \     /   \      /   \
fib(2) fib(1) f(1) f(0) f(1) f(0)
 /  \
f(1) f(0)                 মোট কল: 15

n এক বাড়লে কলের সংখ্যা প্রায় ১.৬ গুণ হয় (ঠিক মানটি সোনালি অনুপাত, প্রায় ১.৬১৮)। তাই সরল fib-এর সময় সূচকীয় — ওপরের সীমা হিসেবে O(2ⁿ) বলা হয়, আরও সূক্ষ্মভাবে Θ(১.৬১৮ⁿ). পর্ব ১৫-এ দেখা memoization প্রতিটি fib(k) একবারই হিসাব করে মনে রাখে — তখন কল হয় মাত্র n-এর কাছাকাছি, অর্থাৎ O(n). একই উত্তর, অথচ fib(40)-এ ৩৩ কোটি কলের বদলে প্রায় ৪০টি হিসাব। পর্ব ৪২-এর ডায়নামিক প্রোগ্রামিং পুরোপুরি এই ধারণার ওপর দাঁড়িয়ে।

৭ · Space complexity আর amortized খরচ

মেমরিও একটি সম্পদ

সময়ের মতো মেমরিও সীমিত। Space complexity মাপে: ইনপুটের বাইরে অ্যালগরিদম বাড়তি কত মেমরি নেয়, আর n বাড়লে সেটি কীভাবে বাড়ে।

• Array-র যোগফল: শুধু একটি sum আর একটি i — n যত বড়ই হোক। বাড়তি মেমরি O(1).
• Array-র একটি কপি বানানো: n টি নতুন ঘর — O(n).
• n × n টেবিল (যেমন পর্ব ৩৮-এর adjacency matrix): O(n²). ১ লাখ vertex-এর matrix মানে ১০¹⁰ ঘর — প্রতিটি এক byte হলেও ১০ GB!
• রিকার্শন: প্রতিটি অসমাপ্ত কল call stack-এ একটি frame দখল করে রাখে। সরল fib(n)-এর সময় সূচকীয় হলেও stack-এর গভীরতা সর্বোচ্চ n — তাই space O(n). পর্ব ২০-এ দেখেছেন, stack-এর জায়গা সাধারণত মাত্র কয়েক MB (Linux-এ প্রায় ৮, Windows-এ প্রায় ১); গভীরতা খুব বেশি হলে stack overflow.

Amortized — মাঝে মাঝে দামি, গড়ে সস্তা

পর্ব ২০-এর dynamic array মনে করুন: জায়গা ফুরোলে realloc দিয়ে capacity দ্বিগুণ, আর পুরোনো সব উপাদান নতুন জায়গায় কপি। পর্ব ৩৭-এ hash table-এর resizing-ও একই কৌশল। একটি push কখনো কখনো n টি কপি ঘটায় — তাহলে কি push O(n)? নিচে capacity ১ থেকে শুরু করে ৯টি push গুনে দেখি। প্রতিটি নতুন উপাদান লেখা = ১ কাজ, প্রতিটি কপি = ১ কাজ:

কেন দ্বিগুণ করাই জরুরি? ধরুন capacity প্রতিবার শুধু ১০ করে বাড়ানো হলো। তাহলে প্রতি ১০টি push-এ একবার পুরো array কপি — ১০, ২০, ৩০… মোট কপি প্রায় n²/২০, অর্থাৎ O(n²). গুণ করে বাড়ালে (দ্বিগুণ, বা ১.৫ গুণ) মোট কপি থাকে O(n). বাস্তবের অনেক dynamic array ১.৫ থেকে ২ গুণের মধ্যে কোনো গুণক ব্যবহার করে।

৮ · বাস্তবের হিসাব — ধ্রুবক, cache, সময়ের বাজেট আর মেপে দেখা

Big-O ধ্রুবক বাদ দেয় — কিন্তু আপনার কম্পিউটার বাদ দেয় না। একই O(n) হয়েও দুটি প্রোগ্রামের গতিতে দশ গুণ পার্থক্য থাকতে পারে।

• Cache-এর প্রভাব: array আর linked list — দুটিতেই সব উপাদান একবার করে দেখা O(n). কিন্তু array-র উপাদান মেমরিতে পাশাপাশি, তাই CPU একবারে কয়েকটি একসাথে cache-এ টেনে আনে (spatial locality). Linked list-এর node ছড়ানো থাকে, প্রায় প্রতিটি ধাপে cache miss. ফলে বাস্তবে array অনেক গুণ দ্রুত হতে পারে।
• ছোট n-এ ধ্রুবকই রাজা: ধরুন অ্যালগরিদম A নেয় 2n² ধাপ, আর B নেয় 50 n log₂ n. n = ১০০-এ A লাগে ২০,০০০, B প্রায় ৩৩,০০০ — O(n²) জিতল! n প্রায় ১৯০ পেরোলে তবেই B এগিয়ে যায়, আর n = ১,০০০-এ B প্রায় চার গুণ দ্রুত। এজন্য অনেক লাইব্রেরির সর্টিং ছোট অংশে এসে সরল O(n²) পদ্ধতিতে চলে যায় — পরের পর্বে দেখবেন।

সময়ের বাজেট — “সেকেন্ডে ১০⁸” নিয়ম

প্রোগ্রামিং কনটেস্টে সাধারণত সময়সীমা ১–২ সেকেন্ড, আর ইনপুটের সর্বোচ্চ আকার (constraint) আগেই বলা থাকে। একটি মোটা দাগের নিয়ম: C-তে সেকেন্ডে মোটামুটি ১০⁸ সরল কাজ. এটি নিখুঁত নয় — CPU, কাজের ধরন আর মেমরি-প্যাটার্নভেদে কয়েক গুণ কমবেশি হয়। কিন্তু constraint দেখে কোন complexity চলবে, তা আন্দাজ করার জন্য যথেষ্ট:

উল্টো দিক থেকে ভাবুন: constraint যদি বলে n ≤ ২ লাখ, তাহলে O(n²) মানে ৪ × ১০¹⁰ — প্রায় ৪০০ সেকেন্ড। সমাধান লেখার আগেই বোঝা যায়, এই পথ চলবে না; O(n log n) খুঁজতে হবে। এই হিসাব কনটেস্টে কীভাবে কাজে লাগে, তা পর্ব ৪৪-এ বিস্তারিত দেখব।

নিজে মেপে দেখা — n দ্বিগুণ করার পরীক্ষা

তত্ত্বের হিসাব বাস্তবে মেলে কি না, তা যাচাইয়ের সবচেয়ে সহজ উপায় একটি ছোট benchmark. কৌশলটি হলো: n দ্বিগুণ করুন, আর দেখুন সময় কত গুণ হলো। প্রায় ২ গুণ মানে O(n), প্রায় ৪ গুণ মানে O(n²), প্রায় ৮ গুণ মানে O(n³). নিচের প্রোগ্রাম time.h-এর clock() দিয়ে দুটি কাজের সময় মাপে — একটি O(n) যোগফল, আর একটি O(n²) কাজ: কতগুলো জোড়া উল্টো ক্রমে আছে (বাঁয়ের সংখ্যা ডানেরটির চেয়ে বড়), তা গোনা।

#include <stdio.h>
#include <time.h>
#define MAX 16000
int a[MAX];
int main(void) {
    for (int i = 0; i < MAX; i++) a[i] = (i * 7919) % 10007;   /* mixed-up values */
    for (int n = 4000; n <= MAX; n *= 2) {
        clock_t t0 = clock();
        long long sum = 0, inv = 0;
        for (int i = 0; i < n; i++) sum += a[i];                 /* O(n)   */
        clock_t t1 = clock();
        for (int i = 0; i < n; i++)                               /* O(n^2) */
            for (int j = i + 1; j < n; j++)
                if (a[i] > a[j]) inv++;
        clock_t t2 = clock();
        printf("n=%5d  sum=%lld %.4fs  pairs=%lld %.4fs\n", n, sum, (double)(t1 - t0) / CLOCKS_PER_SEC,
               inv, (double)(t2 - t1) / CLOCKS_PER_SEC);
    }
    return 0;
}

৯ · AI-এর যুগে complexity — “এটি O(n)” দাবি যাচাই

AI-কে “এই কোডের time complexity কত?” জিজ্ঞেস করলে সে আত্মবিশ্বাসের সাথে উত্তর দেয় — বেশিরভাগ সময় ঠিকও হয়। কিন্তু AI প্রায়ই দৃশ্যমান লুপ গোনে, আর লুপের ভেতরে ডাকা ফাংশনের খরচ উপেক্ষা করে। সবচেয়ে বিখ্যাত ফাঁদটি দেখুন:

for (int i = 0; i < strlen(s); i++) {      /* AI: "single loop, so O(n)" */
    if (s[i] == ' ') spaces++;
}

দেখতে একটি লুপ। কিন্তু পর্ব ১৯-এ দেখেছেন, strlen নিজেই পুরো string হেঁটে '\0' খোঁজে — O(n). আর শর্তটি লুপের প্রতিটি ঘোরায় আবার যাচাই হয়। তাই n বার × n ধাপ = O(n²). ১০ লাখ অক্ষরের একটি ফাইলে এটি এক লাখ কোটি ধাপের কাছাকাছি! সমাধান সহজ: লুপের আগে একবার size_t len = strlen(s); লিখে i < len ব্যবহার করুন। কখনো কখনো compiler নিজেই এই হিসাব লুপের বাইরে সরিয়ে নেয় (hoisting), কিন্তু লুপের ভেতরে string বদলালে বা optimization বন্ধ থাকলে পারে না — এর ওপর ভরসা করবেন না।

AI সাধারণত complexity-তে যেসব ভুল করে

AI-এর দেওয়া complexity হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি লুপের শর্ত আর ভেতরের প্রতিটি ফাংশন কলের খরচ আলাদা করে দেখেছি
• ছোট n-এ (যেমন n = ৪) মৌলিক ধাপ হাতে গুনে সূত্রের সাথে মিলিয়েছি
• n দ্বিগুণ করে অন্তত তিনবার মেপেছি — সময়ের অনুপাত দাবির সাথে মেলে
• Worst-case ইনপুট নিজে বানিয়ে চালিয়েছি — শুধু সুন্দর এলোমেলো ইনপুটে নয়
• রিকার্শনের গভীরতা আর বাড়তি মেমরি (space complexity) জিজ্ঞেস করেছি