সেরা, গড় ও সবচেয়ে খারাপ কেস বিশ্লেষণ

১ · তিনটি সংজ্ঞা

একটি অ্যালগরিদমের জটিলতা বলতে সবসময় একটি একক সংখ্যা বোঝায় না — কারণ একই ইনপুট সাইজ $n$-এর হাজারো ভিন্ন ইনপুট থাকতে পারে, এবং অ্যালগরিদম তাদের প্রতিটিতে ভিন্ন সংখ্যক ধাপ নিতে পারে। তাই তিনটি ভিন্ন প্রশ্ন জিজ্ঞাসা করা হয়:

২ · ওয়ার্কড উদাহরণ — Linear Search

ধরুন একটি $n$ সাইজের array-এ (কোনো নির্দিষ্ট ক্রম ছাড়াই) একটি টার্গেট মান খুঁজছি, একে একে প্রতিটি এলিমেন্ট চেক করে (linear search)।

• Best case: টার্গেট প্রথম এলিমেন্টেই পাওয়া গেল — মাত্র ১ তুলনা — $\Theta(1)$।
• Worst case: টার্গেট শেষ এলিমেন্টে (অথবা array-তে নেইই) — পুরো $n$টি তুলনা — $\Theta(n)$।
• Average case: ধরি টার্গেট অবশ্যই array-তে আছে, এবং এটি সমান সম্ভাব্যতায় (uniformly random) যেকোনো অবস্থানে থাকতে পারে ($1$ থেকে $n$)। তাহলে প্রত্যাশিত তুলনা সংখ্যা: $$E[\text{comparisons}] = \frac{1+2+\cdots+n}{n} = \frac{n(n+1)/2}{n} = \frac{n+1}{2}$$ n=10-এ এটি $\frac{11}{2}=5.5$ — অর্থাৎ গড়ে সাড়ে পাঁচটি তুলনা লাগবে।

def comparisons_to_find(target_pos, n):
    # টার্গেট target_pos (0-ইনডেক্সড) অবস্থানে থাকলে, তা খুঁজে পেতে ঠিক (target_pos + 1)টি তুলনা লাগে
    return target_pos + 1

n = 10
all_counts = [comparisons_to_find(pos, n) for pos in range(n)]

best = min(all_counts)
worst = max(all_counts)
average = sum(all_counts) / n

print("সব অবস্থানে তুলনা সংখ্যা:", all_counts)
print("Best case  :", best)
print("Worst case :", worst)
print("Average    :", average)

# হাতে-হিসাবের সূত্র (n+1)/2-এর সাথে মিলিয়ে দেখা
formula_average = (n + 1) / 2
print("সূত্র (n+1)/2 থেকে:", formula_average)
assert average == formula_average, "গড় সূত্রের সাথে মিলছে না!"
print("যাচাই সম্পন্ন — কোড ও সূত্র হুবহু মিলে গেছে।")

৩ · কেন Worst Case সবচেয়ে বেশি ব্যবহৃত হয়

শিল্পে, গবেষণাপত্রে, এবং টেক ইন্টারভিউয়ে যখন কারো "জটিলতা" জিজ্ঞাসা করা হয়, প্রায় সবসময় worst-case বোঝানো হয়। তিনটি কারণ —

• এটি একটি গ্যারান্টি: "এই অ্যালগরিদম কখনোই এর চেয়ে বেশি সময় নেবে না" — এটি একটি নিশ্চিত প্রতিশ্রুতি।
• বিতরণ-নিরপেক্ষ: Average case বের করতে ইনপুটের সম্ভাব্যতা বিতরণ সম্পর্কে একটি অনুমান লাগে (এখানে "uniform random"), যা বাস্তবে সবসময় সত্য নাও হতে পারে। Worst case কোনো অনুমান ছাড়াই সংজ্ঞায়িত।
• নিরাপত্তা-সংবেদনশীল সিস্টেমে জরুরি: একটি বিমান নিয়ন্ত্রণ সিস্টেম বা রিয়েল-টাইম সিস্টেমে "গড়ে দ্রুত" যথেষ্ট নয় — সবচেয়ে খারাপ পরিস্থিতিতেও সময়সীমা মানতে হবে।

৪ · একটি গুরুত্বপূর্ণ ব্যতিক্রম — Quicksort

Quicksort (DSA কোর্সে বিস্তারিত) একটি চমৎকার উদাহরণ যেখানে average ও worst case শুধু কনস্ট্যান্ট নয়, সম্পূর্ণ ভিন্ন জটিলতা ক্লাসের:

• Worst case: $\Theta(n^2)$ — যখন ইনপুট ইতিমধ্যে সাজানো এবং pivot সবসময় সবচেয়ে ছোট/বড় এলিমেন্ট বাছাই করা হয় (naive pivot choice)।
• Average case: $\Theta(n \log n)$ — random বা typical ইনপুটে, যা একই ক্লাসে যেখানে merge sort পড়ে।

এই পার্থক্যই দেখায় কেন "average case" শুধু একটি ছোট অলংকরণ নয় — এটি মাঝে মাঝে একটি অ্যালগরিদমকে ব্যবহারিকভাবে চমৎকার (কারণ worst case বিরল) বনাম সম্পূর্ণ অচল প্রমাণ করতে পারে।