বেস্ট, ওয়ার্স্ট ও অ্যাভারেজ কেস অ্যানালাইসিস

১ · তিনটি ভিন্ন প্রশ্ন, তিনটি ভিন্ন উত্তর

একই অ্যালগরিদম বিভিন্ন ইনপুটে ভিন্ন ভিন্ন সময় নিতে পারে — শুধু ইনপুট সাইজ $n$-এর উপর নয়, ইনপুটের গঠনের উপরও এটি নির্ভর করে। তাই একটি একক সংখ্যা দিয়ে "কমপ্লেক্সিটি" প্রকাশ করা অসম্পূর্ণ — বদলে আমরা তিনটি ভিন্ন প্রশ্ন জিজ্ঞাসা করি:

লক্ষ্য করুন — অ্যাভারেজ কেস সংজ্ঞায়িত করতে হলে ইনপুটের উপর একটি সম্ভাব্যতা ডিস্ট্রিবিউশন ধরে নিতে হয়। এই পাঠে আমরা সবচেয়ে সাধারণ অনুমানটি ব্যবহার করব — সফল সার্চে লক্ষ্য এলিমেন্ট অ্যারের যেকোনো পজিশনে সমান সম্ভাবনায় (uniformly random) থাকতে পারে।

২ · লিনিয়ার সার্চ — তিনটি কেসের গণনা

লিনিয়ার সার্চ (দেখুন DSA কোর্স ইমপ্লিমেন্টেশনের বিস্তারিত জন্য) একটি অ্যারের প্রতিটি এলিমেন্ট একে একে পরীক্ষা করে, লক্ষ্য এলিমেন্ট পাওয়া গেলেই থেমে যায়। $n$ সাইজের একটি অ্যারেতে:

• বেস্ট কেস: লক্ষ্য এলিমেন্ট $\text{arr}[0]$-এ — মাত্র $1$টি তুলনা লাগে, $T_{best}(n) = O(1)$।
• ওয়ার্স্ট কেস: লক্ষ্য এলিমেন্ট $\text{arr}[n-1]$-এ, অথবা অ্যারেতে নেই — ঠিক $n$টি তুলনা লাগে, $T_{worst}(n) = \Theta(n)$।
• অ্যাভারেজ কেস: লক্ষ্য এলিমেন্ট যদি সমান সম্ভাবনায় $\text{arr}[0]$ থেকে $\text{arr}[n-1]$-এর যেকোনো পজিশনে থাকতে পারে, তাহলে পজিশন $i$ (0-ইনডেক্সড)-এ থাকলে ঠিক $i+1$টি তুলনা লাগে। প্রত্যাশিত মান:

$$E[\text{তুলনা}] = \sum_{i=0}^{n-1} \frac{1}{n}(i+1) = \frac{1}{n}\sum_{k=1}^{n} k = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2}$$

অর্থাৎ গড়ে অ্যারের ঠিক অর্ধেক স্ক্যান করতে হয় — একটি পরিষ্কার, ছোট সামেশন থেকে সরাসরি ডেরাইভ করা সূত্র। $n=50$ হলে এই সূত্র অনুযায়ী গড় $\frac{51}{2}=25.5$ হওয়ার কথা।

৩ · কোড সেল — এম্পিরিক্যাল গড় বনাম তাত্ত্বিক গড়

নিচের কোড সেলে $n=50$ সাইজের একটি অ্যারেতে ২ লক্ষ (200,000) স্বতন্ত্র র‍্যান্ডম ট্রায়াল চালানো হয়েছে — প্রতিবার একটি সমান-সম্ভাবনার লক্ষ্য এলিমেন্ট বেছে নিয়ে লিনিয়ার সার্চ চালিয়ে প্রকৃত তুলনার সংখ্যা গোনা হয়েছে, তারপর সব ট্রায়ালের গড় বের করা হয়েছে। এই এম্পিরিক্যাল গড়কে তাত্ত্বিক $\frac{n+1}{2}$-এর সাথে সরাসরি তুলনা করা হয়েছে।

import random

def linear_search(arr, target):
    comparisons = 0
    for i, x in enumerate(arr):
        comparisons += 1
        if x == target:
            return i, comparisons
    return -1, comparisons

rng = random.Random(42)   # ফিক্সড সিড -- ফলাফল পুনরুৎপাদনযোগ্য
n = 50
arr = list(range(n))

trials = 200_000
total_comparisons = 0
for _ in range(trials):
    target = rng.randrange(n)   # প্রতিটি পজিশন সমান সম্ভাবনায় -- সফল সার্চ, লক্ষ্য সবসময় অ্যারেতে আছে
    _, c = linear_search(arr, target)
    total_comparisons += c

empirical_avg = total_comparisons / trials
theoretical_avg = (n + 1) / 2

print(f"n = {n}")
print(f"ট্রায়াল সংখ্যা: {trials:,}")
print(f"এম্পিরিক্যাল গড় তুলনার সংখ্যা: {empirical_avg:.4f}")
print(f"তাত্ত্বিক গড় (n+1)/2 = {theoretical_avg:.4f}")
print(f"পার্থক্য: {abs(empirical_avg - theoretical_avg):.4f}")

# --- বেস্ট ও ওয়ার্স্ট কেস সরাসরি দেখা ---
_, best_c = linear_search(arr, arr[0])
_, worst_c = linear_search(arr, arr[-1])
_, notfound_c = linear_search(arr, n)   # n অ্যারেতে নেই -- অনুপস্থিত এলিমেন্ট

print(f"\nবেস্ট কেস (arr[0] খোঁজা): {best_c} তুলনা")
print(f"ওয়ার্স্ট কেস (arr[-1] খোঁজা): {worst_c} তুলনা")
print(f"ওয়ার্স্ট কেস (অনুপস্থিত এলিমেন্ট খোঁজা): {notfound_c} তুলনা")