best, worst আর average case — সময় ও জায়গার বিশ্লেষণ

১ · একই অ্যালগরিদম, ভিন্ন ইনপুট, ভিন্ন সময়

একটি পরীক্ষার হলের দৃশ্য ভাবুন। পরীক্ষা শেষে শিক্ষক ৬০টি খাতা রোল নম্বর অনুযায়ী সাজাবেন। তিনি একটি একটি করে খাতা হাতে নেন, আর আগের সাজানো স্তূপে সেটির ঠিক জায়গা খুঁজে ঢুকিয়ে দেন। এখন দুটি দিন কল্পনা করুন:

• প্রথম দিন: ছাত্রছাত্রীরা রোল নম্বর অনুযায়ী লাইন ধরে খাতা জমা দিয়েছে। প্রতিটি নতুন খাতা স্তূপের একদম ওপরে যায় — একবার তাকালেই কাজ শেষ।
• দ্বিতীয় দিন: খাতা জমা পড়েছে ঠিক উল্টো ক্রমে — ৬০ থেকে ১। এবার প্রতিটি নতুন খাতাকে পুরো স্তূপের নিচে নিয়ে যেতে হয়, সবগুলোর সাথে মিলিয়ে।

খাতার সংখ্যা দুই দিনই ৬০টি। শিক্ষকের পদ্ধতিও একই। অথচ খাটুনি একেবারে আলাদা। পর্ব ৪-এ আমরা চলার সময়কে T(n) লিখেছিলাম, যেন শুধু আকার n জানলেই সময় ঠিক হয়ে যায়। এই পর্বের মূল কথাটি হলো — অনেক অ্যালগরিদমের জন্য একই আকারের ভিন্ন ভিন্ন ইনপুটে খরচ ভিন্ন হয়। ৮টি ভিন্ন সংখ্যা সাজানোর ইনপুটই আছে 8! = 40320 রকম ক্রমে।

প্রশ্নগুলো নিখুঁত করতে প্রথমে ঠিক করতে হয় কী গুনব। একে বলে cost model. পর্ব ২-এর RAM model-এ প্রতিটি সরল কাজের খরচ একক ধরা হয়। সর্টিং আর সার্চিংয়ে সাধারণত গোনা হয় দুটি উপাদানের তুলনা (key comparison) — কারণ বাকি কাজের পরিমাণ মোটামুটি তুলনার সংখ্যার সমানুপাতিক। ইনপুটের আকার (input size) n মানে array-তে উপাদানের সংখ্যা।

২ · Linear search — এক, n, আর (n+1)/2

সবচেয়ে সরল উদাহরণ দিয়ে শুরু করি। Linear search একটি array-র শুরু থেকে একটি একটি করে উপাদান দেখে, যতক্ষণ না লক্ষ্যটি (target) মেলে বা array শেষ হয়। ফোনবুকের নামগুলো যদি কোনো ক্রমে সাজানো না থাকে, একটি নাম খুঁজতে আপনিও ঠিক এভাবেই ওপর থেকে নিচে পড়বেন।

LINEAR-SEARCH(a[0..n-1], x)
    for i = 0 to n-1
        if a[i] == x          // একটি তুলনা
            return i
    return NOT-FOUND

এখানে খরচ = a[i] == x তুলনার সংখ্যা। নিচের array-তে ৮টি রোল নম্বর আছে। চারটি ভিন্ন লক্ষ্য খুঁজে দেখুন — প্রতিবার কোন কোন ঘরের সাথে তুলনা হলো, লাল দাগে দেখাবে:

target = 42

গড়টি কেন (n+1)/2 — প্রমাণ

অনুমান: লক্ষ্যটি array-তে আছে, আর nটি অবস্থানের প্রতিটিতে থাকার সম্ভাবনা 1/n. লক্ষ্য k-তম অবস্থানে (১ থেকে গুনে) থাকলে তুলনা লাগে ঠিক kটি। তাহলে প্রত্যাশিত তুলনা —

মাঝখানে আমরা ব্যবহার করেছি 1 + 2 + … + n = n(n+1)/2 — গাউসের সেই বিখ্যাত যোগফল, যা পর্ব ৬-এ বিস্তারিত দেখবেন। আর লক্ষ্য তালিকায় না থাকলে প্রতিবারই nটি তুলনা লাগে। সব মিলিয়ে:

লক্ষ করুন, গড়টি worst case-এর প্রায় অর্ধেক — কিন্তু বৃদ্ধির হার একই, Θ(n). পর্ব ৪-এর ভাষায়, ধ্রুবক ১/২ বৃদ্ধির হার বদলায় না। ১০ লাখ উপাদানে গড়ে ৫ লাখ তুলনা আর সবচেয়ে খারাপে ১০ লাখ — দুটোই লাখের ঘরে।

৩ · Insertion sort — সাজানো, উল্টো আর এলোমেলো ইনপুট

শুরুর সেই শিক্ষকের পদ্ধতিটিরই নাম insertion sort. তাস খেলার সময় হাতে নতুন কার্ড এলে আমরাও এটাই করি — ডান দিক থেকে বাঁয়ে তাকিয়ে কার্ডটিকে ঠিক জায়গায় ঢুকিয়ে দিই। পর্ব ২০-এ এই সর্টটি বিস্তারিত দেখবেন; এখানে আমরা শুধু এর খরচ গুনব, কারণ তিন case বোঝার জন্য এর চেয়ে ভালো উদাহরণ কম আছে।

INSERTION-SORT(a[0..n-1])
    for i = 1 to n-1
        key = a[i]
        j = i
        while j > 0 and a[j-1] > key     // প্রতিবার একটি তুলনা
            a[j] = a[j-1]                 // বড়টিকে এক ঘর ডানে সরাও
            j = j - 1
        a[j] = key

প্রতিটি পাস i-তে আমরা a[0..i-1] অংশটি আগে থেকেই সাজানো পাই (এটিই loop invariant — পর্ব ৩), আর key = a[i]-কে তার জায়গায় বসাই। খরচ = a[j-1] > key তুলনার সংখ্যা। একই আকারের (n = 5) দুটি ইনপুট পাশাপাশি চালিয়ে দেখুন — একটি আগে থেকেই সাজানো, অন্যটি পুরো উল্টো:

sorted   start      [1 2 3 4 5]

কেন এগুলোই best আর worst — যুক্তি

নিম্নসীমা: প্রতিটি পাস i ≥ 1-এ অন্তত একটি তুলনা হয় (j = i > 0, তাই while-এর শর্ত অন্তত একবার যাচাই হয়)। তাই যেকোনো ইনপুটে তুলনা ≥ n−1, আর সাজানো ইনপুটে ঠিক এটুকুই হয় — অর্থাৎ best case ঠিক n−1.

ঊর্ধ্বসীমা: পাস i-তে j সর্বোচ্চ i বার কমতে পারে, তাই তুলনা সর্বোচ্চ iটি। মোট ≤ Σi=1..n−1 i = n(n−1)/2. উল্টো ইনপুটে প্রতিটি key তার আগের সবার চেয়ে ছোট, তাই প্রতিটি পাসে ঠিক iটি তুলনা হয় — worst case ঠিক n(n−1)/2.

এলোমেলো ইনপুট — inversion-এর হিসাব

সাজানো আর উল্টো ইনপুট দুটি চরম প্রান্ত। মাঝখানের সব ইনপুটের খরচ মাপার জন্য একটি সুন্দর ধারণা আছে — inversion. একটি array-তে i < j কিন্তু a[i] > a[j] — এমন প্রতিটি জোড়া (i, j) একটি inversion. অর্থাৎ যে দুটি উপাদান একে অপরের “ভুল পাশে” আছে। [2 4 1 3]-এ inversion তিনটি: (2,1), (4,1), (4,3). সাজানো array-তে inversion ০, উল্টো array-তে সব জোড়াই inversion — n(n−1)/2টি।

এখন average case. ধরে নিই ইনপুটটি nটি ভিন্ন সংখ্যার একটি সম্পূর্ণ এলোমেলো বিন্যাস — n!টি বিন্যাসের প্রতিটি সমান সম্ভাব্য। যেকোনো একটি জোড়া (i, j) নিন। এর দুটি উপাদান সঠিক ক্রমে থাকার সম্ভাবনা আর উল্টো ক্রমে থাকার সম্ভাবনা সমান — প্রতিটি ১/২ (প্রতিটি বিন্যাসে ওই দুটির জায়গা বদলে আরেকটি বিন্যাস পাওয়া যায়, এভাবে জোড়ায় জোড়ায় মেলে)। জোড়া আছে n(n−1)/2টি। প্রত্যাশার যোগফলের নিয়ম (linearity of expectation) অনুযায়ী —

সবচেয়ে ছোট উদাহরণে নিজের চোখে মিলিয়ে নিন। {1, 2, 3}-এর ৬টি বিন্যাসের প্রতিটিতে insertion sort চালিয়ে তুলনা আর inversion গুনুন:

[1 2 3]  inversions: none (0)

নিজে চালিয়ে দেখুন — n = 8 আর n = 16

নিচের প্রোগ্রামটি insertion sort-এর প্রতিটি তুলনা গোনে, আর তিনটি ইনপুটে চালায়: সাজানো 1..n, উল্টো n..1, আর একটি নির্দিষ্ট এলোমেলো বিন্যাস (প্রতিবার একই ফল পেতে এটি কোডেই লিখে দেওয়া)। পাশে তিনটি সূত্রের মানও ছাপে। আপনার ভাষার ট্যাবটি বেছে নিন:

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
// insertion sort on a copy; returns the number of a[j-1] > key comparisons
long long countComparisons(vector<int> a) {
    long long cmp = 0;
    for (size_t i = 1; i < a.size(); ++i) {
        int key = a[i];
        size_t j = i;
        while (j > 0) {
            ++cmp;                          // one comparison
            if (a[j - 1] <= key) break;
            a[j] = a[j - 1];                // shift right
            --j;
        }
        a[j] = key;
    }
    return cmp;
}
int main() {
    vector<vector<int>> shuffled = {{5, 2, 7, 1, 8, 3, 6, 4},
        {11, 3, 14, 7, 1, 9, 16, 5, 12, 2, 8, 15, 6, 10, 4, 13}};
    for (const auto& sh : shuffled) {
        int n = (int)sh.size();
        vector<int> up(n);
        iota(up.begin(), up.end(), 1);              // 1, 2, ..., n
        vector<int> down(up.rbegin(), up.rend());   // n, ..., 2, 1
        cout << "n=" << n << "  sorted=" << countComparisons(up)
             << "  reversed=" << countComparisons(down)
             << "  shuffled=" << countComparisons(sh) << '\n';
        cout << "     n-1=" << n - 1 << "  n(n-1)/2=" << n * (n - 1) / 2
             << "  n(n-1)/4=" << n * (n - 1) / 4 << '\n';
    }
}

def count_comparisons(a):
    """Insertion sort on a copy; count a[j-1] > key comparisons."""
    a = list(a)
    cmp = 0
    for i in range(1, len(a)):
        key, j = a[i], i
        while j > 0:
            cmp += 1                     # one comparison
            if a[j - 1] <= key:
                break
            a[j] = a[j - 1]              # shift right
            j -= 1
        a[j] = key
    return cmp


shuffled = [[5, 2, 7, 1, 8, 3, 6, 4],
            [11, 3, 14, 7, 1, 9, 16, 5, 12, 2, 8, 15, 6, 10, 4, 13]]
for sh in shuffled:
    n = len(sh)
    up = list(range(1, n + 1))          # 1, 2, ..., n
    down = up[::-1]                     # n, ..., 2, 1
    print(f"n={n}  sorted={count_comparisons(up)}"
          f"  reversed={count_comparisons(down)}"
          f"  shuffled={count_comparisons(sh)}")
    print(f"     n-1={n - 1}  n(n-1)/2={n * (n - 1) // 2}"
          f"  n(n-1)/4={n * (n - 1) // 4}")

একটি এলোমেলো ইনপুট কেবল একটি নমুনা। আসল average case হলো সব n! বিন্যাসের গড়। ছোট n-এর জন্য কম্পিউটার সেটি সরাসরি গুনে ফেলতে পারে। নিচের ব্রাউজার-টুলটি n = 2 থেকে 8 পর্যন্ত প্রতিটি বিন্যাসে insertion sort চালিয়ে best, worst আর সঠিক গড় বের করে (৮-এর জন্য ৪০,৩২০টি বিন্যাস!):

// insertion sort: n-এর সব বিন্যাসে তুলনা গুনে best, worst, average
function countCmp(arr) {
  const a = arr.slice(); let c = 0;
  for (let i = 1; i < a.length; i++) {
    const key = a[i]; let j = i;
    while (j > 0) { c++; if (a[j - 1] <= key) break; a[j] = a[j - 1]; j--; }
    a[j] = key;
  }
  return c;
}
function eachPermutation(n, visit) {     // Heap's algorithm, iterative
  const a = Array.from({ length: n }, (_, i) => i + 1), c = new Array(n).fill(0);
  visit(a);
  let i = 1;
  while (i < n) {
    if (c[i] < i) {
      const k = i % 2 === 0 ? 0 : c[i];
      [a[k], a[i]] = [a[i], a[k]];
      visit(a); c[i]++; i = 1;
    } else { c[i] = 0; i++; }
  }
}
for (let n = 2; n <= 8; n++) {
  let lo = Infinity, hi = 0, sum = 0, cnt = 0;
  eachPermutation(n, p => { const x = countCmp(p); lo = Math.min(lo, x); hi = Math.max(hi, x); sum += x; cnt++; });
  console.log(`n=${n} perms=${cnt} best=${lo} worst=${hi} average=${(sum / cnt).toFixed(2)} n(n-1)/4=${(n * (n - 1) / 4).toFixed(2)}`);
}

৪ · কোন case জানাবেন — worst case কেন সাধারণত

কেউ যখন বলেন “এই অ্যালগরিদম O(n log n)”, আর কিছু না বলেন, তখন প্রায় সবসময় তিনি worst case বোঝান। এর পেছনে কয়েকটি শক্ত কারণ আছে:

1. গ্যারান্টি: worst case একটি প্রতিশ্রুতি — “যেকোনো ইনপুটে এর বেশি লাগবে না।” পরীক্ষার আগের রাতে ঢাকার জ্যামে বাসা থেকে কেন্দ্রে যাওয়ার সময় আপনি গড় দেখে নয়, সবচেয়ে খারাপ অবস্থা ধরে বের হন।
2. অনুমানের দরকার নেই: average case বলতে ইনপুটের বণ্টন জানতে হয়। বাস্তবের ডেটা প্রায়ই “সম্পূর্ণ এলোমেলো” নয় — প্রায়-সাজানো, অনেক পুনরাবৃত্তি, বা নির্দিষ্ট ধাঁচের।
3. শত্রুভাবাপন্ন ইনপুট: ইন্টারনেটে খোলা সার্ভারে কেউ ইচ্ছা করে সবচেয়ে খারাপ ইনপুট পাঠাতে পারে — একে বলে adversarial input. তখন গড়ের হিসাব কোনো কাজে আসে না (ভাবনার প্রশ্ন ২ দেখুন)।
4. সময়-সংবেদনশীল সিস্টেম: মেট্রোরেলের ব্রেক-নিয়ন্ত্রণ, হৃদযন্ত্রের pacemaker বা বিমানের সফটওয়্যারে “গড়ে দ্রুত” যথেষ্ট নয় — প্রতিবারই নির্দিষ্ট সময়ের মধ্যে কাজ শেষ হতে হবে।
5. সাধারণত হিসাব সহজ: worst case বের করতে একটি খারাপ ইনপুট আর একটি ঊর্ধ্বসীমার যুক্তিই যথেষ্ট; average case-এ সম্ভাবনার হিসাব লাগে।

তবু average case গুরুত্বহীন নয়। Quick sort-এর worst case Θ(n²), অথচ বাস্তবে এটি প্রায়ই সবচেয়ে দ্রুত সর্টগুলোর একটি — কারণ গড়ে (এবং এলোমেলো pivot বেছে নিলে প্রত্যাশিতভাবে) এটি Θ(n log n) (পর্ব ২২)। Hash table-এ খোঁজার worst case Θ(n), কিন্তু ভালো hash function থাকলে গড়ে O(1) (পর্ব ৩২)। এসব জায়গায় average বা expected খরচই আসল গল্প বলে।

আর best case? একা এটি প্রায় অর্থহীন। যেকোনো সর্টিং অ্যালগরিদমের শুরুতে “array আগেই সাজানো কি না” যাচাই (n−1টি তুলনা) জুড়ে দিলেই best case Θ(n) হয়ে যায় — অ্যালগরিদম একটুও ভালো না হয়েই! তবে best case-এর একটি ব্যবহার আছে: insertion sort-এর মতো কোনো অ্যালগরিদম যদি স্বাভাবিকভাবেই প্রায়-সাজানো ডেটায় দ্রুত হয়, আর আপনার ডেটা সত্যিই প্রায়-সাজানো হয়, তাহলে সেটি কাজের তথ্য।

সবচেয়ে প্রচলিত বিভ্রান্তি: case বনাম O, Ω, Θ

অনেকে ভাবেন “best case মানে Ω, worst case মানে O.” এটি ভুল। দুটি সম্পূর্ণ আলাদা প্রশ্ন:

• Case বলে কোন ইনপুটের খরচ দেখছি — প্রতিটি n-এর জন্য একটি ফাংশন পাই: Tbest(n), Tworst(n), Tavg(n).
• Big-O, Ω, Θ (পর্ব ৪) বলে সেই ফাংশনটি কত দ্রুত বাড়ে — ওপর থেকে, নিচ থেকে, নাকি দুই দিক থেকেই আঁটসাঁট।

তাই প্রতিটি case-এর জন্যই O, Ω, Θ তিনটিই বলা যায়। Insertion sort-এর worst case Θ(n²) — অর্থাৎ worst case O(n²) এবং Ω(n²). Best case Θ(n).

৫ · আরও দুই রকম “গড়” — expected time আর amortized খরচ

“গড়ে দ্রুত” কথাটি অ্যালগরিদমের জগতে তিনটি আলাদা অর্থে ব্যবহৃত হয়। গুলিয়ে ফেললে পরীক্ষায় নম্বর কাটা যায়, আর ইন্টারভিউতে ভুল বার্তা যায়।

Average case বনাম expected time

Average case-এ এলোমেলোতা থাকে ইনপুটে — আমরা ধরে নিই ইনপুট কোনো একটি বণ্টন থেকে আসছে। কিন্তু একটি randomized algorithm নিজেই কয়েন ছোড়ে — যেমন quick sort-এ pivot হিসেবে এলোমেলো একটি উপাদান বেছে নেওয়া। তখন ইনপুট যা-ই হোক, অ্যালগরিদমের নিজের এলোমেলো সিদ্ধান্তের ওপর গড় করা খরচকে বলে expected running time.

এই পার্থক্যটি গুরুত্বপূর্ণ: random pivot-এর quick sort-এর expected time প্রতিটি ইনপুটের জন্য O(n log n) — সাজানো, উল্টো, যেকোনো ইনপুট। অন্যদিকে প্রথম উপাদানকে pivot ধরা quick sort-এর average case O(n log n) হলেও, সাজানো ইনপুটে সেটি নির্ভরযোগ্যভাবে Θ(n²). বিস্তারিত দেখবেন পর্ব ২২ (quick sort) আর পর্ব ৬১ (randomized অ্যালগরিদম)-এ।

Amortized খরচ — একটি সংক্ষিপ্ত পরিচয়

তৃতীয় অর্থটিতে কোনো সম্ভাবনাই নেই। Amortized analysis বলে: অনেকগুলো অপারেশনের একটি পুরো ক্রমের worst-case মোট খরচ কত, আর সেটিকে অপারেশনের সংখ্যা দিয়ে ভাগ করলে প্রতি অপারেশনে কত পড়ে।

সবচেয়ে পরিচিত উদাহরণ dynamic array — C++-এর std::vector বা Python-এর list. জায়গা ফুরিয়ে গেলে এটি দ্বিগুণ বড় নতুন জায়গা নেয়, আর পুরোনো সব উপাদান কপি করে। একটি push-এর খরচ ধরি “লেখা ১ + কপি করা উপাদানের সংখ্যা”, শুরুর capacity ১:

একটি একক push-এর worst case Θ(n) (৫ নম্বর push-এ ৪টি কপি)। কিন্তু ৮টি push-এর মোট খরচ ১৫ — গড়ে ২-এরও কম। সাধারণভাবে nটি push-এ মোট কপি 1 + 2 + 4 + … < 2n, আর লেখা nটি — মোট < 3n. তাই প্রতি push-এর amortized খরচ O(1) — এবং এটি একটি গ্যারান্টি, কোনো ভাগ্যের ব্যাপার নয়। বাস্তবে বৃদ্ধির গুণক সবসময় ২ নয় (C++-এর কোনো কোনো বাস্তবায়ন ১.৫ গুণ বাড়ায়), কিন্তু যেকোনো ধ্রুবক গুণে বাড়ালেই ফল O(1) amortized থাকে। বিস্তারিত পর্ব ১০ (dynamic array) আর পর্ব ৬০ (amortized analysis)-এ।

৬ · জায়গার হিসাব — input space, auxiliary space আর recursion-এর stack

সময়ের মতো জায়গাও একটি সম্পদ। ফোনের মেমরি, সার্ভারের RAM, বা কনটেস্টে ২৫৬ MB-এর সীমা — সবখানেই জায়গা সীমিত। Space complexity বলে অ্যালগরিদম চলার সময় সর্বোচ্চ কতটা মেমরি লাগে, n-এর ফাংশন হিসেবে।

এখানে দুটি অংশ আলাদা করে দেখা দরকার:

• Input space: ইনপুট নিজেই যে জায়গা নেয় — nটি উপাদানের array-তে Θ(n). এটি অ্যালগরিদমের দোষ নয়, ইনপুট তো আসবেই।
• Auxiliary space: ইনপুটের বাইরে অ্যালগরিদম বাড়তি যে জায়গা নেয় — অস্থায়ী array, ভ্যারিয়েবল, আর recursion-এর stack.

অ্যালগরিদম তুলনা করার সময় সাধারণত auxiliary space-ই বলা হয়, কারণ সেখানেই পার্থক্য। Linear search আর insertion sort দুটোরই auxiliary space Θ(1) — কয়েকটি ভ্যারিয়েবল (i, j, key) ছাড়া কিছু লাগে না। Merge sort (পর্ব ২১) একটি অস্থায়ী array নেয়, তাই Θ(n).

Recursion-এর লুকানো খরচ: call stack

নতুনরা প্রায়ই বলেন, “আমার recursive ফাংশনে তো কোনো array নেই, তাই জায়গা O(1).” কিন্তু প্রতিটি ফাংশন-ডাক call stack-এ একটি frame রাখে — প্যারামিটার, লোকাল ভ্যারিয়েবল, ফেরার ঠিকানা। ডাকটি শেষ না হওয়া পর্যন্ত frame-টি থাকে। তাই recursion-এর auxiliary space অন্তত সর্বোচ্চ recursion depth × একটি frame-এর আকার। নিচে a = [3, 1, 4, 1]-এর যোগফল recursive-ভাবে বের করা দেখুন:

1// a = {3, 1, 4, 1}; call sum(a, 4)2int sum(const vector<int>& a, int n) {3    if (n == 0) return 0;4    return sum(a, n - 1) + a[n - 1];5}

sum(a, 4)   waiting

এই হিসাবটির বাস্তব পরিণতি আছে। Call stack-এর আকার সীমিত (অনেক সিস্টেমে ডিফল্ট কয়েক MB), আর Python ডিফল্টভাবে প্রায় ১০০০ স্তরের বেশি recursion করতে দেয় না। তাই ১০ লাখ উপাদানের array-তে ওপরের recursive যোগফল চালালে stack overflow হবে — C++-এ প্রোগ্রাম crash করবে, Python-এ RecursionError আসবে। কনটেস্টে ১ লাখ node-এর একটি লম্বা শিকলের মতো গ্রাফে recursive DFS চালালে ঠিক এই সমস্যাই হয় (পর্ব ৪১)। অন্যদিকে recursive binary search প্রতিবার অর্ধেক অংশে যায়, তাই তার গভীরতা মাত্র ⌈log₂(n+1)⌉ — জায়গা Θ(log n), যা কখনো সমস্যা করে না।

জায়গারও best, worst, average case থাকতে পারে। Insertion sort-এর জায়গা সব ইনপুটেই Θ(1), কিন্তু ইনপুটের ধরন অনুযায়ী quick sort-এর stack-এর গভীরতা বদলায়। সাধারণভাবে “space complexity” বললে worst-case auxiliary space বোঝানো হয়।

৭ · সময় বনাম জায়গা — দরদামের খেলা

প্রায়ই জায়গা খরচ করে সময় কেনা যায়, আবার সময় খরচ করে জায়গা বাঁচানো যায়। একে বলে time–space trade-off. আপনার ফোনের কনট্যাক্ট লিস্ট এর সহজ উদাহরণ: প্রতিটি নম্বর একবার সেভ করতে কিছু জায়গা যায়, কিন্তু বারবার মনে করার বা কাগজ খোঁজার সময় বাঁচে।

Fibonacci সংখ্যা দিয়ে দরদামটি স্পষ্ট দেখা যায়। সরল recursive fib(n) = fib(n−1) + fib(n−2) একই মান বারবার হিসাব করে — fib(30) বের করতে মোট ২৬,৯২,৫৩৭টি ফাংশন-ডাক হয়, সময় সূচকীয় (exponential). Memoization দিয়ে প্রতিটি fib(k) একবারই হিসাব হয় — ৩১টি মান, Θ(n) সময়, বিনিময়ে Θ(n) জায়গা (টেবিল আর recursion-এর stack). আর একটু বুদ্ধি খাটালে দেখা যায় শুধু শেষ দুটি মান মনে রাখলেই চলে — একটি লুপে Θ(n) সময় আর মাত্র Θ(1) জায়গা। একই সমস্যা, তিনটি ভিন্ন সময়–জায়গার মিশ্রণ।

কনটেস্টেও এই চিন্তা সবখানে: অনেক প্রশ্নের উত্তর দিতে হলে factorial বা prime-এর তালিকা একবার আগেই বানিয়ে রাখা (sieve — পর্ব ৬২), বা prefix sum-এর array রেখে প্রতিটি রেঞ্জ-যোগফল O(1)-এ দেওয়া (পর্ব ১৭)। প্রশ্ন সবসময় একই — মেমরির সীমার মধ্যে কতটা আগে থেকে রেখে দিলে সময়ের সীমা পার হওয়া যায়?

৮ · বাস্তবে মাপা — benchmark-এর ফাঁদ

তাত্ত্বিক বিশ্লেষণ বলে খরচ কীভাবে বাড়ে; কিন্তু “আমার মেশিনে ১০ লাখ উপাদানে কত মিলিসেকেন্ড” — তা জানতে মাপতেই হয়। এই মাপাকে বলে benchmarking. কাজটি সহজ শোনায়, কিন্তু ভুল করা আরও সহজ। প্রচলিত ফাঁদগুলো:

• একবার মেপেই সিদ্ধান্ত: অপারেটিং সিস্টেম, অন্য প্রোগ্রাম আর CPU-র গতি-পরিবর্তনের কারণে প্রতিবার সময় একটু আলাদা আসে। কয়েকবার চালিয়ে মধ্যমা (median) বা সর্বনিম্ন মান নিন।
• Compiler কাজটাই মুছে দিল: -O2-এ ফলাফল কোথাও ব্যবহার না হলে compiler পুরো লুপ বাদ দিতে পারে — সময় আসবে প্রায় শূন্য। ফলটি ছাপুন বা অন্যভাবে ব্যবহার করুন।
• Debug build মাপা: optimization ছাড়া (-O0) মাপা সময় বাস্তবের প্রতিনিধিত্ব করে না।
• প্রথম চালানো (warm-up): প্রথমবার ডেটা cache-এ থাকে না, মেমরি বরাদ্দ হয়; পরেরবার দ্রুত। আগে একবার “গরম” করে নিন।
• I/O-সহ মাপা: ইনপুট পড়া বা আউটপুট ছাপার সময় প্রায়ই আসল অ্যালগরিদমের চেয়ে বেশি। মাপার অংশ থেকে I/O বাদ দিন।
• খুব ছোট n: ১০টি উপাদানে সবকিছুই মাইক্রোসেকেন্ডে শেষ — বৃদ্ধির হার দেখা যায় না, ঘড়ির নিখুঁততার সীমাও এসে পড়ে।
• শুধু একরকম ইনপুট: এই পর্বের মূল শিক্ষা! সাজানো ইনপুটে মেপে insertion sort-কে “linear” ভাবা, বা এলোমেলো ইনপুটে মেপে quick sort-এর worst case ভুলে যাওয়া — দুটোই ভুল সিদ্ধান্তে নিয়ে যায়।

সময় মাপার জন্য C++-এ std::chrono::steady_clock (যে ঘড়ি কখনো পেছনে যায় না) আর Python-এ time.perf_counter() ব্যবহার করুন। কাঠামোটি দেখতে এমন (এগুলো নিজের কম্পিউটারে চালানোর জন্য — সময় প্রতিবার আলাদা আসবে):

#include <chrono>
// ... countComparisons(...) আর ইনপুট a আগের মতো ...
auto t0 = std::chrono::steady_clock::now();
long long c = countComparisons(a);          // ফল ব্যবহার করতে হবে
auto t1 = std::chrono::steady_clock::now();
auto us = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
std::cout << "n=" << a.size() << " cmp=" << c << " time=" << us << " us\n";

import time
# ... count_comparisons(...) আর ইনপুট a আগের মতো ...
t0 = time.perf_counter()
c = count_comparisons(a)
t1 = time.perf_counter()
print(f"n={len(a)} cmp={c} time={(t1 - t0) * 1e6:.0f} us")
# বারবার চালিয়ে সবচেয়ে ভালো মান নিতে: timeit মডিউল

একটি কার্যকর কৌশল হলো দ্বিগুণ-পরীক্ষা (doubling experiment): n, 2n, 4n-এ সময় মাপুন আর পরপর দুটির অনুপাত দেখুন। অনুপাত ২-এর কাছে হলে বৃদ্ধি linear, ৪-এর কাছে হলে quadratic, ২-এর একটু বেশি হলে সম্ভবত n log n. ওপরের প্রোগ্রামের তুলনা-সংখ্যাতেও এটি দেখা গেছে — উল্টো ইনপুটে ২৮ থেকে ১২০, প্রায় ৪ গুণ।

৯ · AI-এর যুগে case analysis

AI-কে “এই কোডের time complexity কত?” জিজ্ঞেস করলে প্রায় সবসময় একটি আত্মবিশ্বাসী উত্তর আসে। সমস্যা হলো, উত্তরটি প্রায়ই অসম্পূর্ণ — কোন case, কোন অনুমান, কোন জায়গা, তা বাদ পড়ে যায়। কয়েকটি সাধারণ ভুল:

AI-এর বিশ্লেষণ হাতে পেলে — যাচাইয়ের চেকলিস্ট

• AI-এর দেওয়া ছোট ইনপুটে নিজে হাতে trace করে অপারেশন গুনেছি — সংখ্যা মিলেছে
• কোডে একটি counter বসিয়ে সাজানো, উল্টো আর এলোমেলো ইনপুটে চালিয়েছি, আর সংখ্যাগুলো সূত্রের সাথে মিলিয়েছি
• n দ্বিগুণ করে দেখেছি গণনা ঠিক যত গুণ বাড়ার কথা, তত গুণ বাড়ছে কি না
• Edge case-এ চালিয়েছি: n = 0, n = 1, সব উপাদান সমান, লক্ষ্য তালিকায় নেই
• Recursion থাকলে বড় n-এ stack overflow হয় কি না পরীক্ষা করেছি
• “Average” শব্দটি দেখলে জিজ্ঞেস করেছি — কোন বণ্টনের ওপর গড়, নাকি অ্যালগরিদমের এলোমেলো সিদ্ধান্তের ওপর?