অ্যালগরিদম কী — pseudocode আর RAM model

১ · অ্যালগরিদম — নিয়ম মেনে চলা ধাপের তালিকা

সকালে আপনি bKash অ্যাপ খুলে মাকে টাকা পাঠালেন। ধাপগুলো ভাবুন: “Send Money” চাপুন → নম্বর দিন → টাকার পরিমাণ দিন → PIN দিন → নিশ্চিত করুন। প্রতিটি ধাপ স্পষ্ট, ক্রম নির্দিষ্ট, আর শেষে একটি ফল আসে — টাকা পৌঁছায়, নয়তো “ব্যালান্স যথেষ্ট নয়” বার্তা। এই ধরনের ধাপের তালিকাকেই গণিত আর কম্পিউটার বিজ্ঞানে বলা হয় অ্যালগরিদম।

একটু আনুষ্ঠানিকভাবে বললে: অ্যালগরিদম হলো সুনির্দিষ্টভাবে বর্ণিত একটি গণনা-পদ্ধতি, যা কিছু মান input হিসেবে নেয়, ধাপে ধাপে কাজ করে, এবং কিছু মান output হিসেবে দেয়। CLRS (Cormen, Leiserson, Rivest ও Stein-এর বিখ্যাত বই Introduction to Algorithms) প্রায় এভাবেই সংজ্ঞা দেয়: অ্যালগরিদম হলো input-কে output-এ রূপান্তরের গণনামূলক ধাপের একটি ক্রম।

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

২ · Knuth-এর পাঁচ শর্ত — কোনটা অ্যালগরিদম, কোনটা নয়

“ধাপের তালিকা” বললে তো রান্নার রেসিপিও পড়ে। তাহলে কি রেসিপিও অ্যালগরিদম? এই প্রশ্নের নিখুঁত উত্তর দিয়েছেন Stanford বিশ্ববিদ্যালয়ের Donald Knuth, তাঁর বিখ্যাত বই The Art of Computer Programming-এর প্রথম খণ্ডে (১৯৬৮)। তাঁর মতে একটি অ্যালগরিদমের পাঁচটি বৈশিষ্ট্য থাকতেই হবে:

এবার কয়েকটি পদ্ধতি এই পাঁচ শর্তের পাল্লায় মেপে দেখি:

৩ · সমস্যা, instance, অ্যালগরিদম আর প্রোগ্রাম — চারটি আলাদা জিনিস

নতুনরা প্রায়ই এই চারটি শব্দ গুলিয়ে ফেলেন। অথচ পরীক্ষার খাতায় ঠিক এই পার্থক্যই জিজ্ঞেস করা হয়। একটি সমস্যা (problem) বলে কী চাই; অ্যালগরিদম বলে কীভাবে পাব; প্রোগ্রাম সেই “কীভাবে”-কে একটি নির্দিষ্ট ভাষায় লেখে। আর সমস্যার একটি নির্দিষ্ট input-কে বলে instance. নিচের ডায়াগ্রামে “পরে” চাপুন:

Input : n টি পূর্ণসংখ্যার একটি অ্যারে A, যেখানে n ≥ 1
Output: এমন একটি মান m, যা A-তে আছে এবং
        A-এর প্রতিটি উপাদান x-এর জন্য x ≤ m

A = [4, 8, 2, 9, 6]      n = 5   সঠিক উত্তর 9
A = [-3, -7, -1]         n = 3   সঠিক উত্তর -1
A = [42]                 n = 1   সঠিক উত্তর 42
A = [5, 5, 5, 5]         n = 4   সঠিক উত্তর 5

ARRAY-MAX(A, n)
1  max ← A[1]
2  for i ← 2 to n
3      if A[i] > max
4          max ← A[i]
5  return max

// C++
int mx = a[0];
for (size_t i = 1; i < a.size(); i++)
    if (a[i] > mx) mx = a[i];

# Python
mx = a[0]
for i in range(1, len(a)):
    if a[i] > mx: mx = a[i]

$ ./max
9
এক সমস্যা → অনেক অ্যালগরিদম → প্রতিটির অনেক প্রোগ্রাম → প্রতিটির অনেক রান

শেষ ধাপের কথাটি আবার বলি, কারণ এটিই পুরো কোর্সের মেরুদণ্ড। একটি অ্যালগরিদমকে সঠিক (correct) বলা হয় তখনই, যখন সমস্যার প্রতিটি instance-এ এটি থামে এবং সঠিক output দেয়। দশটি উদাহরণে ঠিক চললেও একটিমাত্র instance-এ ভুল হলে অ্যালগরিদমটি ভুল। উল্টো দিকে, ভুল অ্যালগরিদমও মাঝে মাঝে কাজের হয় — যদি ভুলের হার নিয়ন্ত্রণ করা যায় (পর্ব ৬১-এর randomized অ্যালগরিদম) বা উত্তর “প্রায় সেরা” হলেই চলে (পর্ব ৬৬)।

আরেকটি শব্দ এখনই শিখে রাখুন: input size বা input-এর আকার, সাধারণত n লেখা হয়। অ্যারের ক্ষেত্রে এটি উপাদানের সংখ্যা; গ্রাফের ক্ষেত্রে vertex আর edge-এর সংখ্যা; আর একটি বড় সংখ্যার ক্ষেত্রে তার অঙ্কের (বা bit-এর) সংখ্যা। অ্যালগরিদমের খরচ আমরা সবসময় এই আকারের ফাংশন হিসেবে মাপব।

৪ · একটু ইতিহাস — বাগদাদ, আলেকজান্দ্রিয়া আর একটি কাল্পনিক যন্ত্র

তবে নামটা নবম শতকের হলেও, অ্যালগরিদমের ধারণা আরও অনেক পুরোনো। খ্রিস্টপূর্ব প্রায় ৩০০ সালে আলেকজান্দ্রিয়ার গণিতবিদ Euclid তাঁর Elements বইয়ের সপ্তম খণ্ডে দুটি সংখ্যার গরিষ্ঠ সাধারণ গুণনীয়ক (GCD, গসাগু) বের করার একটি পদ্ধতি লেখেন। Knuth একে বলেছেন টিকে থাকা সবচেয়ে পুরোনো অ-তুচ্ছ অ্যালগরিদমগুলোর একটি। আজও এটি প্রতিদিন কোটি কোটিবার চলে — আপনার ব্রাউজারের এনক্রিপশন থেকে শুরু করে ভগ্নাংশ লঘিষ্ঠ করা পর্যন্ত।

Euclid-এর মূল যুক্তি

ধরুন a = q·b + r, যেখানে r হলো ভাগশেষ, অর্থাৎ r = a mod b (mod মানে ভাগশেষ)। এখন যে সংখ্যা a আর b দুটিকেই নিঃশেষে ভাগ করে, সে a − q·b = r-কেও ভাগ করে। উল্টো দিকে, যে b আর r দুটিকে ভাগ করে, সে q·b + r = a-কেও ভাগ করে। অর্থাৎ (a, b) জোড়ার সাধারণ গুণনীয়ক আর (b, r) জোড়ার সাধারণ গুণনীয়ক হুবহু একই সেট — তাই সবচেয়ে বড়টিও একই:

প্রতিবার দ্বিতীয় সংখ্যাটি ছোট হয় (r < b), আর ঋণাত্মক হয় না — তাই একসময় শূন্য হতেই হবে। এটাই সসীমতার প্রমাণ। Euclid নিজে অবশ্য ভাগ নয়, বারবার বিয়োগ ব্যবহার করেছিলেন (বড়টি থেকে ছোটটি বিয়োগ); ভাগশেষ হলো অনেকগুলো বিয়োগ একসাথে করার সংক্ষিপ্ত রূপ। এবার Euclid-এর অ্যালগরিদম হাতে চালিয়ে দেখি — gcd(252, 105):

0EUCLID(a, b)1while b ≠ 02    r ← a mod b3    a ← b4    b ← r5return a

৫ · Pseudocode — কোনো ভাষার নয়, তবু নিখুঁত

অ্যালগরিদম লিখব কোন ভাষায়? বাংলা গদ্যে লিখলে দ্ব্যর্থতা থাকে; C++-এ লিখলে #include, টাইপ আর সেমিকোলনের ভিড়ে মূল যুক্তি হারিয়ে যায়। মাঝামাঝি সমাধান pseudocode — প্রোগ্রামিং ভাষার মতো কাঠামো, কিন্তু কোনো compiler-এর নিয়ম মানতে হয় না। পাঠ্যবই, বিশ্ববিদ্যালয়ের প্রশ্নপত্র আর গবেষণাপত্র — সবখানে অ্যালগরিদম এভাবেই লেখা হয়।

Pseudocode-এর কোনো একক “সরকারি” নিয়ম নেই। তাই প্রতিটি বই শুরুতেই নিজের নিয়ম বলে দেয়। এই কোর্সের নিয়ম (CLRS-ধাঁচের):

• অ্যারে 1-based: A[1..n] — প্রথম উপাদান A[1], শেষটি A[n]. কোনো পর্বে 0-based লিখলে সেখানে আলাদা করে বলা থাকবে।
• মান রাখা ←, তুলনা =: max ← A[1] মানে “max-এ A[1] রাখো”; if x = y মানে “x আর y সমান কি না”। (CLRS-এর তৃতীয় সংস্করণ থেকে মান রাখতে = আর তুলনায় == লেখা হয় — দুটোই চলে, শুধু একটি লেখায় একটি নিয়মই মানবেন।)
• লুপ: for i ← 2 to n মানে i = 2, 3, …, n — দুই প্রান্তসহ। downto হলে উল্টো দিকে। while শর্ত চেনা নিয়মেই চলে। লুপ শেষ হলে for-এর i-এর মান হয় n + 1 (শেষবার শর্ত মিথ্যা হয়েছিল ওই মানে)।
• Indentation-ই block: কোনো { } বা end নেই — Python-এর মতো, ভেতরে সরানো লাইনগুলো লুপ বা if-এর অংশ।
• লাইন নম্বর আর মন্তব্য: প্রতিটি লাইনের নম্বর থাকে, যাতে ব্যাখ্যায় “লাইন ৩” বলা যায়; মন্তব্য // দিয়ে।
• and, or short-circuit: i ≤ n and A[i] ≠ x-এ প্রথম অংশ মিথ্যা হলে দ্বিতীয় অংশ যাচাইই হয় না — তাই A[n+1] পড়ার ভুল হয় না।
• উচ্চস্তরের কথা চলে, যদি সেটা মৌলিক কাজ হয়: “x আর y অদলবদল করো” চলে; কিন্তু “অ্যারেটি সাজাও” লিখলে সেটি একটি পুরো অ্যালগরিদমকে লুকিয়ে ফেলে — খরচ হিসাবের সময় আলাদা করে ধরতে হবে।

এই নিয়মে আমাদের দুই অ্যালগরিদম:

ARRAY-MAX(A, n)              // A[1..n], n ≥ 1
1  max ← A[1]
2  for i ← 2 to n
3      if A[i] > max
4          max ← A[i]
5  return max

EUCLID(a, b)                 // a, b ≥ 0 পূর্ণসংখ্যা, দুটোই শূন্য নয়
1  while b ≠ 0
2      r ← a mod b
3      a ← b
4      b ← r
5  return a

Pseudocode থেকে C++ আর Python — অনুবাদের অভিধান

Python-এর একটি সূক্ষ্মতাও খেয়াল রাখুন: ঋণাত্মক সংখ্যায় C++-এর % আর Python-এর % আলাদা ফল দেয় (-7 % 3 C++-এ −1, Python-এ 2). Euclid-এ আমরা অঋণাত্মক সংখ্যা ধরে নিয়েছি, তাই এখানে সমস্যা নেই — কিন্তু অনুবাদের সময় এই ধরনের “দেখতে এক, আচরণে ভিন্ন” জিনিসগুলোই ফাঁদ।

৬ · RAM model — হিসাবের জন্য একটি কাল্পনিক কম্পিউটার

“এই অ্যালগরিদম কত দ্রুত?” — প্রশ্নটির উত্তর সেকেন্ডে দিলে বিপদ। একই কোড পুরোনো ল্যাপটপে ২ সেকেন্ড, নতুন ডেস্কটপে ০.৩ সেকেন্ড, ফোনে আরেক রকম। তাহলে দুটি অ্যালগরিদম তুলনা করব কীভাবে? সমাধান: একটি সরল, কাল্পনিক কম্পিউটার ঠিক করে নেওয়া, আর সেখানে কতগুলো ধাপ লাগে তা গোনা। সবচেয়ে প্রচলিত এমন মডেলের নাম RAM model (Random-Access Machine — মেমরির যেকোনো ঘরে সরাসরি যাওয়া যায় বলে এই নাম; এটি আপনার কম্পিউটারের “RAM” চিপ নয়)।

Word size — একটি ছোট কিন্তু জরুরি শর্ত

“প্রতিটি যোগ এক একক” — কিন্তু যদি সংখ্যা দুটি এক হাজার অঙ্কের হয়? তখনো এক একক ধরলে মডেলটি প্রতারণার সুযোগ দেয়: পুরো একটি অ্যারেকে একটি বিশাল সংখ্যার ভেতরে ঠেসে রেখে এক “ধাপে” যোগ করে ফেলা যায়! তাই RAM model একটি মেমরি ঘরের আকার (word size) সীমিত রাখে: input আকার n হলে প্রায় c·log₂ n bit (c কোনো ছোট ধ্রুবক)। এতে n পর্যন্ত index বা গণনা একটি ঘরে আঁটে, কিন্তু অসীম তথ্য আঁটে না। বাস্তবের ৬৪-bit কম্পিউটারও তা-ই করে — একটি word-এ ৬৪ bit, তার বেশি নয়।

কোনটা “এক ধাপ”, কোনটা নয়

শেষ চারটি সারিই নতুনদের সবচেয়ে বেশি ঠকায়: কোডে এক লাইন দেখে মনে হয় “এক ধাপ”, অথচ ভেতরে লুকিয়ে আছে পুরো একটি লুপ। কনটেস্টে Time Limit Exceeded পাওয়ার একটি বড় কারণ এটাই।

৭ · ধাপ গোনা — ARRAY-MAX-এর নিখুঁত হিসাব

এবার RAM model-এ ARRAY-MAX-এর running time একদম নিখুঁতভাবে বের করি। CLRS-এর পদ্ধতি: pseudocode-এর লাইন k একবার চলতে ck সময় নেয় (ধ্রুবক), আর আমরা গুনব প্রতিটি লাইন কতবার চলে। ধরুন n টি উপাদানের মধ্যে t বার নতুন সর্বোচ্চ পাওয়া যায় (লাইন ৪ চলে)।

সব যোগ করলে:

লাইন ২-এর “n বার” (n − 1 নয়) — এখানেই সবচেয়ে বেশি ভুল হয়। লুপের শর্ত শেষবার একবার মিথ্যা হয়ে লুপ থামায়, সেই যাচাইটিও একটি ধাপ। এবার A = [4, 8, 2, 9, 6] instance-এ গোনাটি চোখে দেখুন:

0ARRAY-MAX(A, n)1max ← A[1]2for i ← 2 to n3    if A[i] > max4        max ← A[i]5return max

সবচেয়ে ভালো আর সবচেয়ে খারাপ ক্ষেত্র

T(n) একটি মাত্র সংখ্যা নয় — t-এর ওপর নির্ভর করে, আর t নির্ভর করে input কীভাবে সাজানো তার ওপর:

• সবচেয়ে ভালো (best case): প্রথম উপাদানই সর্বোচ্চ, যেমন [9, 7, 5, 3, 1]. t = 0, T(n) = 2n + 1.
• সবচেয়ে খারাপ (worst case): কঠোরভাবে ঊর্ধ্বক্রম, যেমন [1, 3, 5, 7, 9] — প্রতিবারই নতুন সর্বোচ্চ। t = n − 1, T(n) = 3n.

দুই ক্ষেত্রেই T(n) n-এর সাথে সরলরেখায় বাড়ে। সময়: Θ(n) — প্রতিটি উপাদান অন্তত একবার দেখতেই হয়, আর একবারের বেশি দেখা হয় না। বাড়তি জায়গা: Θ(1) — শুধু max আর i, n যত বড়ই হোক। Best, worst আর average case নিয়ে পুরো আলোচনা পর্ব ৫-এ।

ধ্রুবকগুলো কেন ফেলে দিই

এবার একটি মজার পরীক্ষা। লাইন না গুনে যদি C++-এর প্রতিটি মৌলিক কাজ আলাদা করে গুনি — অ্যারে পড়া একটি, তুলনা একটি, মান রাখা একটি, i++ একটি?

যোগফল: 2 + 1 + n + (n − 1) + (2n − 2) + 2t + 1 = 4n + 1 + 2t — best case 4n + 1, worst case 6n − 1. আগের হিসাবে ছিল 2n + 1 আর 3n. কোনটা ঠিক? দুটোই — শুধু “এক ধাপ” কাকে বলছি তা আলাদা। বাস্তবে আবার compiler কয়েকটি কাজ একসাথে জুড়ে দেয়, CPU একই চক্রে একাধিক নির্দেশ চালায় — আসল ধ্রুবক আরেক রকম হবে।

৮ · কাজের উদাহরণ — ধাপ গুনতে গুনতে max আর Euclid

এবার দুই অ্যালগরিদমকেই আসল কোডে লিখি — সাথে একটি গণনাকারী (counter), যা RAM model-এর হিসাবটিই করে। প্রথমে ARRAY-MAX: প্রতিটি pseudocode লাইন চললে counter এক বাড়ে। আপনার ভাষার ট্যাবটি বেছে নিন, তারপর চালান:

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

// ARRAY-MAX with a counter: +1 for every executed pseudocode line
int arrayMax(const vector<int>& a, int& steps, int& t) {
    int mx = a[0];
    steps = 1; t = 0;                          // line 1
    for (size_t i = 1; i < a.size(); i++) {
        steps += 2;                            // line 2 (test true) + line 3
        if (a[i] > mx) { mx = a[i]; steps++; t++; }   // line 4
    }
    steps += 2;                                // line 2 (final test) + line 5
    return mx;
}

int main() {
    vector<vector<int>> tests = {{9, 7, 5, 3, 1}, {1, 3, 5, 7, 9},
                                 {4, 8, 2, 9, 6}, {6, 2, 6, 1, 7, 3, 7, 5}};
    for (const auto& a : tests) {
        int steps, t;
        int mx = arrayMax(a, steps, t);
        int n = static_cast<int>(a.size());
        cout << "n=" << n << " max=" << mx << " t=" << t << " steps=" << steps
             << " 2n+1+t=" << 2 * n + 1 + t << '\n';
    }
}

n=5 max=9 t=0 steps=11 2n+1+t=11
n=5 max=9 t=4 steps=15 2n+1+t=15
n=5 max=9 t=2 steps=13 2n+1+t=13
n=8 max=7 t=1 steps=18 2n+1+t=18

# ARRAY-MAX with a counter: +1 for every executed pseudocode line
def array_max(a):
    mx = a[0]
    steps, t = 1, 0                     # line 1
    for i in range(1, len(a)):
        steps += 2                      # line 2 (test true) + line 3
        if a[i] > mx:
            mx = a[i]
            steps += 1                  # line 4
            t += 1
    steps += 2                          # line 2 (final test) + line 5
    return mx, steps, t

tests = [[9, 7, 5, 3, 1], [1, 3, 5, 7, 9], [4, 8, 2, 9, 6], [6, 2, 6, 1, 7, 3, 7, 5]]
for a in tests:
    mx, steps, t = array_max(a)
    n = len(a)
    print(f"n={n} max={mx} t={t} steps={steps} 2n+1+t={2 * n + 1 + t}")

n=5 max=9 t=0 steps=11 2n+1+t=11
n=5 max=9 t=4 steps=15 2n+1+t=15
n=5 max=9 t=2 steps=13 2n+1+t=13
n=8 max=7 t=1 steps=18 2n+1+t=18

চারটি লাইনেই গোনা ধাপ আর সূত্র 2n + 1 + t হুবহু মিলেছে। প্রথম লাইন best case (11 = 2·5 + 1), দ্বিতীয়টি worst case (15 = 3·5), তৃতীয়টি স্টেপারের instance (13). চতুর্থটি খেয়াল করুন: 6 দুবার আর 7 দুবার আছে, কিন্তু t = 1 — কারণ শর্তটি >, ≥ নয়; সমান মান পেলে max বদলায় না। ≥ লিখলে উত্তর একই থাকত, কিন্তু t আর ধাপ বাড়ত, আর “প্রথম সর্বোচ্চের index” চাইলে ভুল index আসত। একটি অক্ষরের পার্থক্য — এটাই অ্যালগরিদমের নিখুঁততা।

এবার Euclid. পাশাপাশি রাখছি একটি brute force পদ্ধতি: min(a, b) থেকে শুরু করে নিচে নামতে নামতে প্রথম যে সংখ্যা দুটিকেই ভাগ করে। দুটির উত্তর মিলিয়ে দেখা হবে, আর গোনা হবে কে কতবার ভাগশেষ বের করল:

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

// EUCLID: gcd(a, b) = gcd(b, a mod b); count the mod operations
long long euclid(long long a, long long b, int& divs, bool show) {
    divs = 0;
    while (b != 0) {
        long long r = a % b; divs++;
        if (show) cout << "  " << a << " = " << a / b << "*" << b << " + " << r << '\n';
        a = b; b = r;
    }
    return a;
}
// brute force: try d = min(a, b), min(a, b) - 1, ..., 1
long long brute(long long a, long long b, long long& tries) {
    tries = 0;
    for (long long d = min(a, b); d >= 1; d--) {
        tries++;
        if (a % d == 0 && b % d == 0) return d;
    }
    return 1;
}
int main() {
    long long pairs[][2] = {{252, 105}, {1071, 462}, {89, 55}, {1000000, 999999}};
    for (auto& p : pairs) {
        bool show = (p[0] == 252);
        if (show) cout << "trace of gcd(252, 105):\n";
        int divs; long long tries;
        long long g = euclid(p[0], p[1], divs, show), gb = brute(p[0], p[1], tries);
        cout << "gcd(" << p[0] << ", " << p[1] << ") = " << g << "  euclid_divisions=" << divs
             << "  brute_tries=" << tries << (g == gb ? "" : "  MISMATCH") << '\n';
    }
}

trace of gcd(252, 105):
  252 = 2*105 + 42
  105 = 2*42 + 21
  42 = 2*21 + 0
gcd(252, 105) = 21  euclid_divisions=3  brute_tries=85
gcd(1071, 462) = 21  euclid_divisions=3  brute_tries=442
gcd(89, 55) = 1  euclid_divisions=9  brute_tries=55
gcd(1000000, 999999) = 1  euclid_divisions=2  brute_tries=999999

# EUCLID: gcd(a, b) = gcd(b, a mod b); count the mod operations
def euclid(a, b, show=False):
    divs = 0
    while b != 0:
        r = a % b
        divs += 1
        if show:
            print(f"  {a} = {a // b}*{b} + {r}")
        a, b = b, r
    return a, divs

# brute force: try d = min(a, b), min(a, b) - 1, ..., 1
def brute(a, b):
    tries = 0
    for d in range(min(a, b), 0, -1):
        tries += 1
        if a % d == 0 and b % d == 0:
            return d, tries
    return 1, tries

for x, y in [(252, 105), (1071, 462), (89, 55), (1000000, 999999)]:
    show = x == 252
    if show:
        print("trace of gcd(252, 105):")
    g, divs = euclid(x, y, show)
    gb, tries = brute(x, y)
    tail = "" if g == gb else "  MISMATCH"
    print(f"gcd({x}, {y}) = {g}  euclid_divisions={divs}  brute_tries={tries}{tail}")

trace of gcd(252, 105):
  252 = 2*105 + 42
  105 = 2*42 + 21
  42 = 2*21 + 0
gcd(252, 105) = 21  euclid_divisions=3  brute_tries=85
gcd(1071, 462) = 21  euclid_divisions=3  brute_tries=442
gcd(89, 55) = 1  euclid_divisions=9  brute_tries=55
gcd(1000000, 999999) = 1  euclid_divisions=2  brute_tries=999999

কোথাও MISMATCH নেই — দুই পদ্ধতির উত্তর সব জোড়ায় মিলেছে। কিন্তু খরচের পার্থক্য দেখুন: শেষ জোড়ায় Euclid দুটি ভাগে শেষ (1000000 = 1·999999 + 1, তারপর 999999 = 999999·1 + 0), আর brute force-কে প্রায় দশ লাখ সংখ্যা পরীক্ষা করতে হলো। দশ লাখের জায়গায় ১৮ অঙ্কের সংখ্যা হলে সেকেন্ডে একশো কোটি চেষ্টা করেও brute force-এর কয়েক দশক লেগে যেত; Euclid তখনো ১০০-এর কম ভাগে শেষ করত।

Euclid-এর খরচ কত? ১৮৪৪ সালে ফরাসি গণিতবিদ Gabriel Lamé প্রমাণ করেন: ভাগের সংখ্যা কখনো ছোট সংখ্যাটির দশমিক অঙ্কের সংখ্যার ৫ গুণের বেশি হয় না। সবচেয়ে খারাপ ক্ষেত্র আসে পাশাপাশি দুটি Fibonacci সংখ্যায় — যেমন (89, 55): প্রতিটি ভাগফল 1, তাই সংখ্যা সবচেয়ে ধীরে ছোট হয়, লাগে ৯টি ভাগ (৫৫ দুই অঙ্কের, সীমা ৫ × ২ = ১০)। সহজ একটি যুক্তিও আছে: দুই ধাপ পরপর বড় সংখ্যাটি অন্তত অর্ধেক হয়ে যায় (কারণ a ≥ b হলে a mod b < a/2 সবসময় সত্য)। তাই ভাগের সংখ্যা O(log min(a, b)), আর বাড়তি জায়গা Θ(1). brute force-এর খরচ O(min(a, b)) — দুটির পার্থক্য log বনাম সংখ্যাটি নিজে।

৯ · অ্যালগরিদম ডিজাইনের কর্মপ্রবাহ — আট ধাপ

নতুন একটি সমস্যা হাতে পেলে অনেকে সরাসরি কোড লিখতে বসেন — আর আধঘণ্টা পর বোঝেন সমস্যাটাই ভুল বুঝেছিলেন। অভিজ্ঞ প্রোগ্রামার, কনটেস্টের প্রতিযোগী আর ইন্টারভিউয়ের সফল প্রার্থীরা প্রায় একই ক্রমে ভাবেন। একটি বাস্তব সমস্যায় পুরো কর্মপ্রবাহটি দেখুন: ভর্তি পরীক্ষার রোল-তালিকায় কোনো রোল নম্বর দুবার উঠে গেছে কি না?

Input : n টি পূর্ণসংখ্যা (রোল নম্বর), 0 ≤ n ≤ 200000
Output: কোনো মান দুবার বা তার বেশি থাকলে YES, নইলে NO
প্রশ্ন: তালিকা কি বদলানো যাবে? মান কত বড়? n = 0 হলে?

[12, 5, 31, 5]   → YES
[3, 1, 2]        → NO
[]               → NO     (খালি তালিকা)
[7]              → NO     (একটি মাত্র)
[4, 4, 4]        → YES    (সব সমান)

for i ← 1 to n − 1
    for j ← i + 1 to n
        if A[i] = A[j]  return YES
return NO
তুলনা: n(n − 1)/2  →  n = 200000 হলে প্রায় 2 × 10^10

SORT(A)                       // O(n log n)
for i ← 1 to n − 1
    if A[i] = A[i + 1]  return YES
return NO
বিকল্প: hash set — গড়ে O(n) (পর্ব ৩২)

YES দিলে: A[i] = A[i+1] — সত্যিই দুটি সমান মান আছে।
duplicate থাকলে: ধরুন x আছে দুবার, সাজানোর পর অবস্থান p < q.
  p আর q-এর মাঝের প্রতিটি মান ≥ x এবং ≤ x, অর্থাৎ = x.
  তাই A[p] = A[p+1] — লুপ এটি ধরবেই।  ∎

সময়  : sort Θ(n log n) + এক পাস Θ(n) = Θ(n log n)
জায়গা: in-place sort হলে O(log n) বাড়তি (recursion);
        মূল তালিকা বদলানো না গেলে কপি — Θ(n)
n = 200000: n log₂ n ≈ 3.5 × 10^6 তুলনা — চোখের পলকে

// C++
sort(a.begin(), a.end());
bool dup = adjacent_find(a.begin(), a.end()) != a.end();

# Python
dup = len(set(a)) != len(a)

১. ধাপ ২-এর সব উদাহরণ — খালি, একটি, সব সমান
২. ১০০০ বার: এলোমেলো ছোট তালিকা (n ≤ 8, মান 1..5)
   brute(A) ≠ fast(A) হলে সেই A ছাপো, থামো
৩. n = 200000 দিয়ে সময় মাপো

১০ · AI-এর যুগে — অ্যালগরিদম বোঝা কেন আরও জরুরি

আজ যেকোনো AI চ্যাটবটকে “GCD-র কোড দাও” বললে কয়েক সেকেন্ডে পেয়ে যাবেন। তাহলে অ্যালগরিদম শেখার মানে কী? মানে হলো — AI লেখে, কিন্তু সেটি ঠিক কি না, কত দ্রুত, কোন input-এ ভেঙে পড়বে — এগুলো যাচাইয়ের দায় আপনার। আর ঠিক এই পর্বের বিষয়গুলোতেই AI নিয়মিত ভুল করে, খুব আত্মবিশ্বাসের সাথে।

এই বিষয়ে AI-এর যে ভুলগুলো বারবার দেখা যায়

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

• অন্তত একটি ছোট instance (৪–৬ উপাদান) নিজে হাতে trace করেছি, AI-এর টেবিলের সাথে মিলিয়েছি
• edge case-এ চালিয়েছি — খালি বা একটি উপাদান, সব সমান, ঋণাত্মক, সবচেয়ে বড় মান
• একটি brute force লিখে হাজারটি এলোমেলো ছোট input-এ দুটির উত্তর মিলিয়েছি (stress test)
• প্রতিটি complexity দাবিতে জেনেছি n দিয়ে কী বোঝানো হয়েছে, আর এক লাইনের লাইব্রেরি কলের ভেতরের খরচও ধরেছি
• 1-based থেকে 0-based অনুবাদে প্রতিটি index আর লুপের সীমা আলাদা করে মিলিয়েছি
• “কেন ঠিক” — শুদ্ধতার যুক্তিটি নিজের ভাষায় বলতে পারি; না পারলে AI-কে প্রমাণ চেয়েছি, আর সেটিও যাচাই করেছি