অ্যালগরিদম অ্যানালাইসিসের সাধারণ ভুল

১ · ভুল ১ — ওয়ার্স্ট-কেসকে অ্যাভারেজ-কেস ভেবে গুলিয়ে ফেলা

M2/L08-এ বেস্ট, ওয়ার্স্ট ও অ্যাভারেজ কেসের সংজ্ঞা রিগোরাসভাবে দেখা হয়েছে। একটি সাধারণ ভুল হলো "কুইক সর্ট $O(n \log n)$" এভাবে বলে ফেলা — প্রকৃতপক্ষে কুইক সর্টের ওয়ার্স্ট-কেস $\Theta(n^2)$ (L16-এ দেখা হয়েছে, ইতিমধ্যে-সর্টেড ইনপুটে নাইভ পিভট বেছে নিলে), আর $\Theta(n \log n)$ শুধু অ্যাভারেজ-কেসে সত্য। একটি প্রোডাকশন সিস্টেমে যদি ইনপুট সবসময় র‍্যান্ডম না হয়ে মাঝেমধ্যে প্রায়-সর্টেড আসে (যেমন লগ ফাইল, টাইম-সিরিজ ডেটা), তাহলে "গড়ে $O(n \log n)$" ধরে নেওয়া একটি প্রোডাকশন আউটেজের কারণ হতে পারে।

২ · ভুল ২ — প্রমাণ ছাড়াই গ্রিডিকে অপটিমাল ধরে নেওয়া

M5-এ দেখা প্রতিটি গ্রিডি অ্যালগরিদম (অ্যাক্টিভিটি সিলেকশন, হাফম্যান কোডিং, ফ্র্যাকশনাল ন্যাপস্যাক, MST) একটি রিগোরাস এক্সচেঞ্জ-আর্গুমেন্ট প্রমাণসহ এসেছে। কিন্তু "গ্রিডি" পদ্ধতি নিজেই কোনো গ্যারান্টি বহন করে না — এটি শুধুই একটি টেমপ্লেট (প্রতি ধাপে স্থানীয়ভাবে সেরা পছন্দ করা)। L55-এর কেস স্টাডিতে ঠিক এই ভুলটি দেখা গেছে: আর্লিয়েস্ট-ফিনিশ গ্রিডি "সংখ্যা" সর্বোচ্চ করায় প্রমাণিত, কিন্তু "লাভ" সর্বোচ্চ করায় প্রমাণিত নয় — তবু দেখতে প্রায় একই রকম "যুক্তিসঙ্গত" মনে হয়। নিচের কোড সেলে আরেকটি ধ্রুপদী উদাহরণ — কয়েন-চেঞ্জ — দিয়ে এই ভুলটি সরাসরি কম্পিউট করে দেখানো হয়েছে।

৩ · কম্পিউটেশনাল কাউন্টার-এক্সাম্পল — গ্রিডি কয়েন-চেঞ্জ ব্যর্থ হয়

সাধারণ কারেন্সি সিস্টেমে (যেমন $\{1, 5, 10, 25\}$) সবচেয়ে বড় বৈধ কয়েনটি বারবার বেছে নেওয়ার গ্রিডি নিয়ম সবসময় সর্বনিম্ন সংখ্যক কয়েনে সঠিক উত্তর দেয় — কিন্তু এটি নির্দিষ্ট এই কয়েন সিস্টেমগুলোর একটি বিশেষ গাণিতিক বৈশিষ্ট্যের (ক্যানোনিক্যাল সিস্টেম) কারণে, "গ্রিডি চিরকাল কাজ করে" এমন কোনো সাধারণ সূত্র নেই। একটি নন-ক্যানোনিক্যাল কয়েন সিস্টেম $\{1, 3, 4\}$ নিয়ে টার্গেট $6$ তৈরি করতে চাইলে:

• গ্রিডি: সবচেয়ে বড় বৈধ কয়েন বারবার নেয় — $4$ (অবশিষ্ট $2$), তারপর $1$ (অবশিষ্ট $1$), তারপর $1$ (অবশিষ্ট $0$) — মোট $4+1+1 = 3$টি কয়েন।
• প্রকৃত অপটিমাল: $3+3 = 6$ — মোট মাত্র $2$টি কয়েন।

গ্রিডি এখানে বৈধ উত্তর দেয় (যোগফল ঠিক $6$) কিন্তু অপটিমাল নয় (৩টি কয়েন, যেখানে ২টিতেই সম্ভব)। নিচের কোডে এই দাবিটি এবং আরও কয়েকটি টার্গেটে গ্রিডি বনাম DP-র প্রকৃত তুলনা কম্পিউট করে দেখানো হয়েছে — যাতে বোঝা যায় গ্রিডি মাঝে মাঝে ঠিক উত্তর দেয় (যা বিভ্রান্তিকর ও বিপজ্জনক, কারণ টেস্টিংয়ে ধরা নাও পড়তে পারে) কিন্তু সবসময় নয়।

import math

coins = [1, 3, 4]   # নন-ক্যানোনিক্যাল কয়েন সিস্টেম

def greedy_coin_change(coins, target):
    # লোভীভাবে সবসময় বৈধ সবচেয়ে বড় কয়েনটি বেছে নেওয়া
    used = []
    remaining = target
    for c in sorted(coins, reverse=True):
        while remaining >= c:
            used.append(c)
            remaining -= c
    return used

def optimal_coin_change_dp(coins, target):
    # ট্যাবুলেশন DP -- সব সম্ভাবনা বিবেচনা করে প্রকৃত সর্বনিম্ন সংখ্যক কয়েন বের করে
    dp = [0] + [math.inf] * target
    choice = [None] * (target + 1)
    for amt in range(1, target + 1):
        for c in coins:
            if c <= amt and dp[amt - c] + 1 < dp[amt]:
                dp[amt] = dp[amt - c] + 1
                choice[amt] = c
    used, amt = [], target
    while amt > 0:
        used.append(choice[amt])
        amt -= choice[amt]
    return used

print(f"{'টার্গেট':>8} | {'গ্রিডি':>14} | {'গ্রিডি সংখ্যা':>13} | {'অপটিমাল (DP)':>14} | {'অপটিমাল সংখ্যা':>15} | {'গ্রিডি ব্যর্থ?':>13}")
for target in [6, 7, 8, 10, 12]:
    g = greedy_coin_change(coins, target)
    o = optimal_coin_change_dp(coins, target)
    fails = len(g) > len(o)
    print(f"{target:>8} | {str(g):>14} | {len(g):>13} | {str(o):>14} | {len(o):>15} | {str(fails):>13}")

৪ · ভুল ৩ — RAM মডেলের অনুমান ভুলে যাওয়া

M1/L04-এ দেখা হয়েছে যে অ্যাসিম্পটোটিক অ্যানালাইসিস ধরে নেয় প্রতিটি মৌলিক অপারেশন (যোগ, তুলনা, ইনডেক্সিং) $O(1)$ সময়ে হয় — এটি সাধারণ-আকারের সংখ্যার জন্য বাস্তবসম্মত একটি সরলীকরণ। কিন্তু যখন সংখ্যাগুলো অস্বাভাবিক রকম বড় হয় (যেমন ক্রিপ্টোগ্রাফিতে শত-অঙ্কের সংখ্যা, বা ফ্যাক্টোরিয়াল/ফিবোনাচির মতো দ্রুত-বর্ধনশীল ফাংশনের ফলাফল), তখন একটি একক "গুণন" বা "যোগ" অপারেশন আর $O(1)$ থাকে না — বড় পূর্ণসংখ্যা গুণনের নিজস্ব জটিলতা থাকে (Python-এ বড় int গুণন $O(d^{1.585})$-এর কাছাকাছি, যেখানে $d$ অঙ্কসংখ্যা, Karatsuba-ধর্মী অ্যালগরিদম ব্যবহার করে)। RAM মডেলের এই সীমা ভুলে গিয়ে "লুপ $n$ বার চলে, তাই $O(n)$" বলে ফেলাটা তখন ভুল হতে পারে যদি লুপের ভেতরের প্রতিটি অপারেশন সংখ্যার আকারের সাথে সাথে ধীর হতে থাকে।

৫ · ভুল ৪ — প্রোফাইলিং ছাড়া প্রিম্যাচিউর অপটিমাইজেশন

একটি অ্যালগরিদমের অ্যাসিম্পটোটিক জটিলতা জানা থাকলেও, কোন অংশ আসলে ধীরগতির তা অনুমান না করে (প্রোফাইল না করে) অপটিমাইজ করতে শুরু করা একটি সাধারণ সময়-অপচয়। ডোনাল্ড কানুথের বিখ্যাত পর্যবেক্ষণ — "প্রিম্যাচিউর অপটিমাইজেশনই সব মন্দের মূল" — এখানে প্রাসঙ্গিক: একটি প্রোগ্রামের ৯৭% কোড হয়তো ইনপুটের আকারের তুলনায় নগণ্য সময় নেয়, আর ৩% অংশই প্রকৃত বটলনেক। এই কোর্সের রিগোরাস অ্যাসিম্পটোটিক অ্যানালাইসিস আপনাকে বলে দেয় কোন অ্যালগরিদম তাত্ত্বিকভাবে দ্রুততর হতে পারে, কিন্তু বাস্তব কোডে ঠিক কোথায় সময় ব্যয় হচ্ছে তা যাচাই করতে হয় প্রকৃত প্রোফাইলিং টুল দিয়ে (যেমন Python-এর cProfile) — অনুমান দিয়ে নয়।

৬ · ভুল ৫ — $O(n \log n)$-কে সবসময় "যথেষ্ট দ্রুত" ধরে নেওয়া

বিগ-ও নোটেশন ধ্রুবক ফ্যাক্টর ও নিম্ন-ক্রমের পদ উপেক্ষা করে (M2/L06)। এর মানে দুটি $O(n \log n)$ অ্যালগরিদমের প্রকৃত রানটাইম বহুগুণ ভিন্ন হতে পারে — একটির ধ্রুবক ফ্যাক্টর $2$, আরেকটির $200$ হতে পারে, যদিও দুটোই "একই" অ্যাসিম্পটোটিক ক্লাসে। এমনকি একটি $O(n^2)$ অ্যালগরিদম ছোট $n$-এ (বা ছোট ধ্রুবক ফ্যাক্টরসহ) একটি খারাপভাবে লেখা $O(n \log n)$ অ্যালগরিদমের চেয়ে দ্রুত হতে পারে। অ্যাসিম্পটোটিক নোটেশন আমাদের বলে ইনপুট যথেষ্ট বড় হলে কী ঘটবে — কিন্তু "যথেষ্ট বড়" ঠিক কত বড় তা নির্ভর করে লুকানো ধ্রুবকের উপর, যা নোটেশন নিজেই বলে না।