সর্টিং৬ মিনিট পড়া

কম্পারিজন লোয়ার বাউন্ড (Comparison Lower Bound)

কেন কোনো কম্পারিজন সর্ট (comparison sort) কখনোই \(O(n \log n)\)-কে হারাতে পারে না — তার একটি গাণিতিক প্রমাণ (mathematical proof)
lower bound:\(\Omega(n \log n)\)proof method:ডিসিশন ট্রি (Decision tree)leaves needed:\(n!\) পারমুটেশন বা বিন্যাস (permutations)tree height:\(\ge \log_2(n!)\)

ধরুন আপনি ২০ টি প্রশ্নের এমন একটি গেম বা খেলা খেলছেন বা খেলে বের করার চেষ্টা করছেন যে এতগুলো সম্ভাব্য বিন্যাসের বা অ্যারেঞ্জমেন্টের (arrangements) মধ্যে ঠিক কোনটি সঠিক। এর মধ্যকার প্রতিটি হ্যাঁ/না (yes/no) উত্তর থাকা অবশিষ্ট সম্ভাব্যগুলোর বা পসিবিলিটির প্রায় অর্ধেককে বাতিল করে দেয়। এরপর সম্ভাব্য বিন্যাস বা অ্যারেঞ্জমেন্ট বা আয়োজন যত বেশি বাড়তে থাকবে, আপনি সম্পূর্ণ নিশ্চিত হওয়ার আগে আপনাকে আরও তত বেশি সংখ্যক প্রশ্ন জিজ্ঞাসা করতে হবে।

n সংখ্যক আইটেম বা জিনিসকে সর্ট করার বা সাজানোর জন্য n! সংখ্যক সম্ভাব্য বিন্যাস বা ক্রমানুসারের (orderings) প্রয়োজন হয়। প্রতিটি তুলনাই বা কম্পারিজনই (comparison) ("A কি B এর আগে?") মূলত এক একটি হ্যাঁ/না (yes/no) প্রশ্ন যা কিছু অর্ডার বা বিন্যাসকে বাতিল করে দেয়। এখানকার লোয়ার বাউন্ড প্রুফ (lower bound proof) বা নিম্নসীমার প্রমাণটি দেখায় বা নিশ্চিত করে যে আপনার কম্পারিজন স্ট্র্যাটেজি (comparison strategy) বা তুলনার কৌশলটি যতই বুদ্ধিদীপ্ত বা চতুর হোক না কেন, সমস্ত n! সম্ভাবনাকে বা পসিবিলিটিকে (possibilities) যাচাই বা পরিচালনা করতে আপনাকে অবশ্যই অন্ততপক্ষে \(\Omega(n \log n)\) সংখ্যক প্রশ্ন জিজ্ঞাসা করতে হবে। এর মানে হলো সবচেয়ে খারাপ পরিস্থিতিতে বা ওয়ার্স্ট-কেসের ক্ষেত্রে কোনো কম্পারিজন সর্ট (comparison sort) কখনোই \(O(n \log n)\) এর চেয়ে দ্রুত বা দ্রুততর হতে পারে না — তা কোনো কৌশল বা ট্রিক খাটিয়েও নয়, কখনোই নয়।

ডিসিশন ট্রি বা সিদ্ধান্তের গাছ মডেল (The Decision Tree Model)

প্রতিটি কম্পারিজন-ভিত্তিক সর্ট বা তুলনা নির্ভর ক্রমানুসার পদ্ধতিকেই একটি বাইনারি ডিসিশন ট্রি (binary decision tree) হিসেবে মডেল করা যেতে পারে। এর মধ্যকার প্রতিটি অভ্যন্তরীণ নোডই বা ইন্টারনাল নোড (internal node) হলো মূলত দুটি উপাদানের বা এলিমেন্টের মধ্যকার একটি তুলনা: "arr[i] ≤ arr[j] কি না?"। এর উত্তরের (হ্যাঁ বা না) ওপর ভিত্তি করে, এই অ্যালগরিদমটি যেকোনো একটি ব্রাঞ্চ বা শাখাকে অনুসরণ করে। আর অনুসরণ করতে করতে এটি এক পর্যায়ে গিয়ে এমন একটি লিফ-এ বা পাতায় (leaf) পৌঁছায় — যে নোডে আর কোনো নতুন তুলনা বা কম্পারিজন থাকে না — যা মূলত এর চূড়ান্ত সাজানো বা সর্টেট ফলাফলটিকে (sorted output) নির্ধারণ বা নির্দিষ্ট করে দেয়।

প্রতিটি সম্ভাব্য ইনপুটই (input) এই ট্রি বা গাছটির মধ্য দিয়ে একটি অনন্য (unique) রুট-থেকে-লিফ (root-to-leaf) পথ বা পাথ (path) অনুসরণ করে বা ট্রেস (traces) করে। একটি নির্দিষ্ট ইনপুটের বা মানের জন্য এর তুলনার বা কম্পারিজনের (comparisons) সংখ্যা মূলত তার লিফের (leaf) গভীরতার বা ডেপথের (depth) সমান হয়। এই ওয়ার্স্ট-কেস বা সবচেয়ে খারাপ পরিস্থিতির কম্পারিজন কাউন্ট বা তুলনার গণনাটিই (worst-case comparison count) হলো এই ট্রি বা গাছের উচ্চতা বা হাইট (সবচেয়ে গভীর বা ডিপেস্ট (deepest) লিফের (leaf) গভীরতা)।

ট্রি বা গাছটিতে কমপক্ষে n! সংখ্যক লিফ (Leaves) বা পাতা প্রয়োজন (The Tree Needs at Least n! Leaves)

যেকোনো একটি অ্যালগরিদমকে নির্ভুল বা সঠিক হওয়ার জন্য, তাকে অবশ্যই সম্ভাব্য প্রতিটি ইনপুটের বা মানের জন্য সঠিক আউটপুট (output) বা ফলাফল প্রদান করতে হবে। n সংখ্যক আলাদা আলাদা বা স্বতন্ত্র উপাদানগুলোর (distinct elements) জন্য ঠিক n! সংখ্যক সম্ভাব্য ক্রমানুসারে সাজানো পদ্ধতি (orderings) থাকতে পারে বা বিদ্যমান। যদি দুটি সম্পূর্ণ ভিন্ন অর্ডারিং বা ক্রমানুসার (orderings) একই লিফে (leaf) বা পাতায় গিয়ে পৌঁছায়, তবে অ্যালগরিদমটি তাদের উভয়ের জন্যই একই আউটপুট বা ফলাফল প্রদান করবে — কিন্তু তাদের নিজেদের মধ্যকার সঠিক সাজানো ক্রমানুসার বা অর্ডারটি আলাদা হবে বা ভিন্ন হবে, যার ফলে তাদের অন্তত একটি উত্তর বা ফলাফল ভুল বা রং (wrong) বলে গণ্য হবে।

আর ঠিক এ কারণেই, একটি নির্ভরযোগ্য বা সঠিক কম্পারিজন সর্টের বা তুলনা সাজানো পদ্ধতির ডিসিশন ট্রিতে (decision tree) অন্তত n! সংখ্যক লিফ বা পাতা থাকতে হবে।

উচ্চতা (Height) ≥ \(\log_2(n!)\) ≈ n log n

L সংখ্যক লিফ (leaves) বা পাতা থাকা একটি বাইনারি ট্রির বা গাছের উচ্চতা (height) থাকে কমপক্ষে ⌈\(\log_2(L)\)⌉ পরিমাণ। যেখানে L ≥ n!, সেখানে উচ্চতা হবে কমপক্ষে \(\log_2(n!)\)। স্টার্লিং-এর অ্যাপ্রক্সিমেশন (Stirling's approximation) অনুসারে বা অনুযায়ী: \(\log_2(n!)\) = \(\Sigma_i \log_2(i)\) ≥ (n/2)·\(\log_2(n/2)\) = \(\Omega(n \log n)\)। এটিকে আরও সুনির্দিষ্টভাবে বলতে গেলে, \(\log_2(n!)\) = \(\Theta(n \log n)\)।

তাই প্রতিটি কম্পারিজন সর্টকে (comparison sort) সবচেয়ে খারাপ পরিস্থিতিতে বা ওয়ার্স্ট-কেসে (worst case) কমপক্ষে \(\Omega(n \log n)\) সংখ্যক তুলনা বা কম্পারিজন সম্পন্ন করতে হবে। আর যেহেতু মার্জ সর্ট (merge sort) এবং হিপ সর্ট (heap sort) \(O(n \log n)\) কে অর্জন করতে পারে, তাই আমরা বলতে পারি যে এই বাউন্ড বা সীমাটি বেশ আঁটোসাঁটো বা টাইট (tight) — এরা সমস্ত কম্পারিজন বা তুলনা নির্ভর ধরনের বা সর্টের মধ্যে অ্যাসিম্পটোটিক্যালি অপ্টিমাল (asymptotically optimal) বা উপসর্গ দিক দিয়ে সেরা।

রেখাশ্রয়ী বা লিনিয়ার সর্টগুলো (Linear Sorts) কেন একে ফাঁকি দিতে পারে বা বাইপাস বা স্কিপ (Bypass) করতে পারে

যেহেতু লিনিয়ার সর্টগুলো (যেমন: কাউন্টিং সর্ট/counting sort, র‍্যাডিক্স সর্ট/radix sort, বাকেট সর্ট/bucket sort) কোনোভাবেই এই ডিসিশন ট্রি (decision tree) বা সিদ্ধান্তের গাছ মডেলের সাথে খাপ খায় না — তাই এগুলো কখনোই জিজ্ঞাসা করে না যে "A ≤ B কি না?" এর পরিবর্তে, তারা সরাসরি পূর্ণসংখ্যার বা ইন্টিজার (integer) মানগুলো (values) পড়ে এবং একই সাথে উপাদানগুলোকে (elements) সরাসরি তাদের নিজ নিজ জায়গাতে বসিয়ে দেয় বা স্থাপন করে। তারা সম্পূর্ণ অন্য ধরনের বা ভিন্ন একটি তথ্যের উৎসের (source of information) ব্যবহার করে, তাই এই \(\Omega(n \log n)\) লোয়ার বাউন্ড বা নিম্নসীমাটি তাদের ক্ষেত্রে কোনোভাবেই প্রয়োগ করা বা খাটানো যায় না।

দ্রষ্টব্য: এই প্রমাণটি বা প্রুফটি (proof) কখনোই বলে না যে সর্টিং বা সাজানো জিনিসটা (sorting) ধীরগতির (slow)। এটি মূলত এটাই বলে যে যেকোনো অ্যালগরিদম যা শুধুমাত্র তুলনা নির্ভর বা কম্পারিজন (comparisons) ব্যবহার করে তাকে অবশ্যই এর মধ্যে \(\Omega(n \log n)\) সংখ্যক তৈরি করতে হবে। এটি মূলত একটি মৌলিক তথ্য-তাত্ত্বিক বা ইনফরমেশন-থিওরেটিক (information-theoretic) সীমা বা লিমিট — যেখানে মূলত n! পরিমাণে সম্ভাব্য ক্রমানুসার বা অর্ডারিং (orderings) থাকে আর প্রতিটি তুলনাই বা কম্পারিজনই তার অর্ধেক সম্ভাবনাকে বা পসিবিলিটিকে (possibility) বাতিল করে দেয় বা রুলে আউট (rules out) করে।

ডিসিশন ট্রি বা সিদ্ধান্তের গাছ (Decision Tree) ধারণাটি বা কনসেপ্টটি এক্সপ্লোর করা (Exploring)

import math


def min_comparisons_needed(n):
    """Lower bound: ceil(log2(n!)) comparisons needed."""
    log_n_factorial = sum(math.log2(i) for i in range(1, n + 1))
    return math.ceil(log_n_factorial)


# Compare to actual merge sort comparisons (~n*log2(n))
for n in [4, 8, 16, 32, 64]:
    lb = min_comparisons_needed(n)
    approx = round(n * math.log2(n))
    print(f"n={n:3d}: lower bound={lb:6d},  n*log2(n)≈{approx:6d},  n!={math.factorial(n):>15,}")
Output
n=  4: lower bound=     5,  n*log2(n)≈     8,  n!=              24
n=  8: lower bound=    16,  n*log2(n)≈    24,  n!=           40320
n= 16: lower bound=    45,  n*log2(n)≈    64,  n!=  20922789888000
n= 32: lower bound=   118,  n*log2(n)≈   160,  n!=263130836933693530000000000000000000
n= 64: lower bound=   296,  n*log2(n)≈   384,  n!=1268869321858841641...0000000000000

Complexity

🧮 কম্পারিজন সর্ট লোয়ার বাউন্ড (Comparison sort lower bound)
কোনো কম্পারিজন সর্টই এর চেয়ে চরম খারাপ পরিস্থিতিতে (worst case) গিয়ে এর চাইতে বেশি ভালোভাবে বা বেটার (better) কোনো কাজ করতে পারে না — যা প্রমাণিত (provably)
সর্বনিম্ন বা কমপক্ষে লিনিয়ারিদমিক (Linearithmic) — সবসময় (always) \(\Omega(n \log n)\)
🌳 ডিসিশন ট্রির লিফের প্রয়োজনীয়তা (Decision tree leaves needed)
সঠিকতা বা কারেক্টনেসের (correctness) জন্য n! সংখ্যক ইনপুটের প্রতিটি পারমুটেশন বা বিন্যাসের (permutations) নিজস্ব বা আলাদা লিফ (leaf) থাকা প্রয়োজন
ফ্যাক্টরিয়াল (Factorial) — প্রতি ক্রমানুসারের বা অর্ডারিংয়ের (ordering) জন্য একটি করে n!
📏 ন্যূনতম ট্রির উচ্চতা (Minimum tree height)
n! সংখ্যক লিফ (leaves) সমন্বিত একটি বাইনারি ট্রির বা গাছের উচ্চতা স্টার্লিংয়ের (Stirling) নীতি অনুসারে বা অনুযায়ী ≥ \(\log_2(n!)\) এর সমান হয়
n! এর লগারিদম (Logarithm) \(\Omega(n \log n)\)
✅ অপ্টিমাল বা সর্বোত্তম কম্পারিজন সর্টগুলো (Optimal comparison sorts)
মার্জ সর্ট (Merge sort) এবং হিপ সর্ট (heap sort) অ্যাসিম্পটোটিক্যালি অপ্টিমাল (asymptotically optimal) — এর চেয়ে ভালো করা কখনোই সম্ভব নয়
লোয়ার বাউন্ডের (lower bound) সাথে মেলে বা ম্যাচ (Match) করে \(\Theta(n \log n)\)

ছোট কুইজ

ডিসিশন ট্রি (decision tree) বা সিদ্ধান্তের গাছ মডেলে, লিফ বা পাতাগুলো (leaves) মূলত কী উপস্থাপন করে বা প্রদর্শন করে?

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