সার্চিং ও সিলেকশন৮ মিনিট পড়া

মিডিয়ান অফ মিডিয়ানস (Median of Medians)

একটি নিশ্চিতভাবে ভালো পিভট — একদম প্রতিবার
time:\(O(n)\) নিশ্চিত (guaranteed)space:\(O(n)\)pivot quality:পিভটের উভয় পাশে কমপক্ষে ৩০% উপাদান থাকে

ধরুন আপনার ক্লাসে খুব পক্ষপাতিত্বহীনভাবে একটি স্পোর্টস দলের ক্যাপ্টেন বেছে নেওয়া দরকার। সবাই একসাথে ভোট না দিয়ে (কারণ এতে কারচুপি হতে পারে), আপনারা একটু ভিন্ন পদ্ধতি অবলম্বন করলেন: সবাইকে ৫ জনের ছোট ছোট দলে ভাগ করে দিলেন, তারপর প্রতিটি দলকে তাদের নিজেদের লিডার বা ক্যাপ্টেন বেছে নিতে বললেন। এরপরে সব দলের লিডাররা নিজেদের মধ্যে ভোট দিয়ে আরেকজনকে নির্বাচন করলো। এই পদ্ধতিতে যে জিতবে, সে সবার একজন ভালো প্রতিনিধি হবে।

মিডিয়ান অফ মিডিয়ানস (Median of Medians) ঠিক এই কাজটিই করে — এবং একই যুক্তিতে কাজ করে। এটি এমন একটি পিভট উপাদান (pivot element) বেছে নেয় যা অ্যারেটিকে এমনভাবে ভাগ করার নিশ্চয়তা দেয় যেন কোনো হ্যাকার বা অ্যাডভারসারি (adversary) এটিকে বোকা বানিয়ে \(O(n^2)\) কমপ্লেক্সিটিতে নিয়ে যেতে না পারে।

কুইক-সিলেক্টের (QuickSelect) সমস্যা

র্যান্ডমাইজড কুইক-সিলেক্ট বা দৈবচয়নভিত্তিক কুইক-সিলেক্ট বাস্তবে চমৎকার কাজ করে — এটি প্রায় শতভাগ ক্ষেত্রেই প্রত্যাশিত \(O(n)\) সময়ে সম্পন্ন হয়। কিন্তু যদি কেউ ইচ্ছে করে এমন একটি ইনপুট দেয় যা আপনার অ্যালগরিদমকে বিপর্যস্ত করতে পারে, তখন আপনার র্যান্ডম পিভট সবসময়ই বাজে হতে পারে, এবং আপনাকে \(O(n^2)\) এ ঠেলে দিতে পারে। সিকিউরিটি-ক্রিটিকাল কোডে (যেখানে নিরাপত্তা খুবই গুরুত্বপূর্ণ), অথবা যেখানে আপনার প্রমাণযোগ্য (provable) ওয়ার্স্ট-কেস বা সবচেয়ে খারাপ অবস্থার গ্যারান্টি দরকার, সেখানে প্রামাণ্য এবং সুনিশ্চিত (deterministic) কিছু দরকার হয়।

অ্যালগরিদমের ধাপে ধাপে প্রক্রিয়া

ধাপ ১ — ৫ জনের দলে ভাগ করা: n সংখ্যক উপাদানকে ঠিক ৫টি উপাদানের একেকটি দলে ভাগ করুন (তবে সর্বশেষ দলটিতে একটু কম উপাদান থাকতে পারে)। ৫টি উপাদানের দল হলো সবচেয়ে সেরা মাপ — এটি এতই ছোট যে সাথে সাথে সর্ট করা যায়, আবার এটি এত বড় যে মানের ক্ষেত্রে একটি গ্যারান্টিও পাওয়া যায়।

ধাপ ২ — প্রতিটি দল সর্ট করুন এবং এদের মধ্যবর্তী বা মিডিয়ানটি নিন: প্রতিটি ৫ উপাদানের দলকে ইনসার্শন সর্ট (insertion sort) দিয়ে সর্ট করুন (যার জন্য সর্বোচ্চ ৭ বার তুলনা করতে হয়)। এরপর মাঝখানের উপাদানটি নিন। এবার আপনার কাছে ⌈n/5⌉ সংখ্যক দলের মিডিয়ান বা মধ্যবর্তী মান রয়েছে।

ধাপ ৩ — এই মিডিয়ানগুলোর মধ্য থেকে রিকার্সিভলি (recursively) মিডিয়ান বের করুন: পুরো অ্যালগরিদমটিকে এখন শুধু এই ⌈n/5⌉ মিডিয়ানগুলোর ওপর রিকার্সিভলি প্রয়োগ করুন। এর ফলাফলই হলো মিডিয়ানগুলোর মিডিয়ান (median of medians) — চলুন এর নাম দিই M।

ধাপ ৪ — M-কে আপনার পিভট হিসেবে ব্যবহার করুন: এবার M-কে পিভট ধরে মূল অ্যারেকে পার্টিশন (partition) বা ভাগ করুন। যেহেতু M একটি ভালো পিভট (যা সুনিশ্চিতভাবে ৩০-৭০ অনুপাতে ভাগ করে), তাই আপনি শুধু সেই দিকেই রিকার্শন প্রয়োগ করুন যেদিকে আপনার খোঁজা উপাদানটি (target element) থাকার কথা।

কেন M একটি ভালো পিভট?

M হলো ⌈n/5⌉ সংখ্যক মানের মিডিয়ান। এই মানগুলোর অন্তত অর্ধেক হলো M এর চেয়ে বড় বা সমান (≥ M)। এই মানগুলোর প্রত্যেকেই আবার ৫ উপাদানের একেকটি দলের মিডিয়ান ছিল, অর্থাৎ ঐ দলে এদের ছাড়াও কমপক্ষে আরও ২টি উপাদান ছিল যারা এদের চেয়ে বড় বা সমান (≥ M)। তার মানে, পুরো অ্যারের ওই দলগুলো থেকেই কমপক্ষে (n/5)/2 × 2 = n/5 সংখ্যক উপাদান M এর চেয়ে বড় বা সমান (≥ M) — এর সাথে M তো আছেই। খুব ভালোভাবে হিসাব করলে দেখা যায়, কমপক্ষে 3n/10 সংখ্যক উপাদান M এর প্রতিটি পাশে থাকাটা সুনিশ্চিত। ফলে এই পার্টিশন কখনও 70%-30% এর চেয়ে বেশি বৈষম্যমূলক হয় না বা এটি কখনোই পুরোপুরি একপেশে হয় না।

এর রিকারেন্স (The recurrence)

T(n) = T(n/5) + T(7n/10) + \(O(n)\)। এখানে T(n/5) হলো মিডিয়ানগুলোর মিডিয়ান রিকার্সিভলি বের করার জন্য। T(7n/10) হলো বড় অংশের ওপর পার্টিশন রিকার্শনের জন্য। আর \(O(n)\) হলো দল তৈরি, দলগুলোকে সর্ট করা এবং পার্টিশন করার জন্য। এটি সমাধান করলে আমরা পাই T(n) = \(O(n)\)।

দ্রষ্টব্য: কেন নির্দিষ্ট করে ৫ জনের দল বেছে নেওয়া হলো? ৩ জনের দল যথেষ্ট ভালো গ্যারান্টি দিতে পারে না — সেক্ষেত্রে রিকারেন্সটি দাঁড়ায় T(n)=T(n/3)+T(2n/3)+\(O(n)\), যার সমাধান হলো \(O(n \log n)\)। অন্যদিকে ৭ জনের দল কাজ করে কিন্তু তা বাড়তি ওভারহেড বা সময় নিয়ে আসে। তাই পাঁচ (৫) হলো সবচেয়ে ছোট আকার, যা প্রমাণযোগ্যভাবে \(O(n)\) কমপ্লেক্সিটি দিতে পারে।

মিডিয়ান অফ মিডিয়ানস (Median of Medians)

def median_of_five(arr):
    arr.sort()
    return arr[len(arr) // 2]


def partition_around(arr, lo, hi, pivot):
    # Move pivot to end
    for i in range(lo, hi + 1):
        if arr[i] == pivot:
            arr[i], arr[hi] = arr[hi], arr[i]
            break
    p = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] <= p:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i


def mom_select(arr, lo, hi, k):
    if hi - lo < 5:
        arr[lo:hi+1] = sorted(arr[lo:hi+1])
        return arr[lo + k - lo]
    # Step 1-2: find medians of groups of 5
    medians = []
    for i in range(lo, hi + 1, 5):
        group = arr[i:min(i + 5, hi + 1)]
        medians.append(median_of_five(group))
    # Step 3: recursively find median of medians
    pivot = mom_select(medians, 0, len(medians) - 1, len(medians) // 2)
    # Step 4: partition and recurse
    p = partition_around(arr, lo, hi, pivot)
    if p == k:
        return arr[p]
    elif p > k:
        return mom_select(arr, lo, p - 1, k)
    else:
        return mom_select(arr, p + 1, hi, k)


arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(mom_select(arr[:], 0, len(arr) - 1, 4))  # 5th smallest = 3
Output
3

Complexity

🏆 সামগ্রিক নির্বাচন (Overall selection)
ডিটারমিনিস্টিক (Deterministic); সবচেয়ে খারাপ এবং গড়ের ক্ষেত্রটি সমান; ক্ষতিকর ইনপুট একে বোকা বানাতে পারে না
লিনিয়ার (Linear) — একদম সুনিশ্চিত \(O(n)\)
🎯 পিভটের মানের গ্যারান্টি (Pivot quality guarantee)
পিভটের প্রতিটি পাশে কমপক্ষে 3n/10 সংখ্যক উপাদান থাকে — কখনো বাজেভাবে ভাগ হতে পারে না
সর্বদা ৩০%-৭০% অনুপাতে ভাগ করে \(\Theta(n)\)
💾 মেমরি বা স্পেস (Space)
প্রতিটি লেভেলেই মিডিয়ানের জন্য অ্যারে লাগে; রিকার্শন স্ট্যাক লাগে \(O(\log n)\); সব মিলিয়ে মোট \(O(n)\)
লিনিয়ার অক্সিলিয়ারি মেমরি (Linear auxiliary) \(O(n)\)
🐢 ব্যবহারের গতি (Practical speed)
বারবার দলে ভাগ করা ও সর্ট করার কারণে এর কনস্ট্যান্ট ফ্যাক্টর অনেক বেশি হয়; বাস্তবে এটি খুব কমই ব্যবহৃত হয়
কুইক-সিলেক্টের (QuickSelect) চেয়ে ৫-১০ গুণ ধীর \(O(n)\)

ছোট কুইজ

আমরা ৩ জনের বদলে ঠিক ৫ জনের দল কেন ব্যবহার করি?

পড়া চালিয়ে যান