ডিভাইড অ্যান্ড কঙ্কার৬ মিনিট পড়া

ইনভার্সন গণনা (Count Inversions)

একটি সিকোয়েন্স (sequence) বা ক্রম ঠিক কতটা এলোমেলো অবস্থায় আছে তা পরিমাপ করুন — \(O(n \log n)\) সময়ে
time:\(O(n \log n)\)space:\(O(n)\)

ধরুন আপনি একটি গানের প্লেলিস্ট (playlist) তৈরি করেছেন এবং আপনার কোনো এক বন্ধু সেটিকে সম্পূর্ণ এলোমেলো করে দিয়েছে। তাদের সাজানো ভার্সনটি বা সংস্করণটি আপনার আসল প্লেলিস্টের থেকে কতটা আলাদা? এটি পরিমাপ করার একটি উপায় হতে পারে: ঠিক কত জোড়া গান ভুল আপেক্ষিক ক্রমানুসারে (wrong relative order) আছে তা গণনা বা হিসাব করা। যদি আপনার আসল প্লেলিস্টে গান A, গান B এর আগে থেকে থাকে, কিন্তু এখন গান B যদি গান A এর আগে চলে আসে — তবে এটি হলো একটি ইনভার্সন (inversion)। যত বেশি ইনভার্সন থাকবে, তার মানে হলো জিনিসগুলো ঠিক তত বেশি এলোমেলো হয়ে গেছে।

আনুষ্ঠানিকভাবে বলতে গেলে, একটি ইনভার্সন (inversion) হলো পজিশন বা অবস্থানের এমন একটি জোড়া (i, j) যেখানে i < j কিন্তু A[i] > A[j] — অর্থাৎ দুটি উপাদান বা এলিমেন্ট (elements) তাদের স্বাভাবিক ক্রমানুসারের বা অর্ডারের বাইরে অবস্থান করছে। একটি সম্পূর্ণ সাজানো বা সর্টেড অ্যারের ০ টি বা 0 ইনভার্সন থাকে। একটি সম্পূর্ণ বিপরীতভাবে বা উল্টোভাবে সাজানো (reversed) অ্যারের ক্ষেত্রে সর্বোচ্চ: n(n−1)/2 সংখ্যক ইনভার্সন থাকে (এর সম্ভাব্য প্রতিটি জোড়াই সাধারণ অর্ডারের বা ক্রমানুসারের বাইরে থাকে)।

লেইজি বা সাধারণ পদ্ধতি (The naive approach) — অতিমাত্রায় ধীরগতির

প্রতিটি জোড়াকে (i, j) চেক বা পরীক্ষা করুন যেখানে i < j। যদি A[i] > A[j] হয়, তবে এটি গণনা বা কাউন্ট (count) করুন। এটি বেশ সহজ একটি পদ্ধতি হলেও, এর কমপ্লেক্সিটি (complexity) হলো \(O(n^2)\) — অর্থাৎ এক মিলিয়ন বা দশ লক্ষ গানের জন্য, এটি এক ট্রিলিয়ন (trillion) বা এক লক্ষ কোটি বার তুলনা বা কম্পারিজন (comparisons) করবে।

চতুর অন্তর্দৃষ্টি (The clever insight): মার্জ সর্ট (merge sort) করার সময় গণনা করুন

এখানে আশ্চর্যের বা বোঝার বিষয়টি হলো: মার্জ সর্টের বা merge sort এর মার্জ করার ধাপটি আগে থেকেই ইনভার্সনগুলো ধরতে বা শনাক্ত করতে পারে — শুধু এটিকে এখন পর্যন্ত সেভাবে গণনা করা হয়নি, এই টুকুই যা পার্থক্য।

যখন দুটি সাজানো বা সর্টেড হওয়া অর্ধাংশ [Left] এবং [Right] কে মার্জ বা একত্রিত করা হয়, তখন যদি আমরা রাইট বা Right অংশ থেকে কোনো উপাদান বা এলিমেন্ট (element) বেছে নেই কারণ এটি বর্তমান লেফট বা Left উপাদানের বা এলিমেন্টের চেয়ে ছোট থাকে — তখন লেফটে থাকা অবশিষ্ট প্রতিটি এলিমেন্ট বা উপাদানই এর থেকে বড় হয় এবং আসল অ্যারেতে এটি তার আগেই আসার কথা ছিল। আর এখানকার প্রতিটি উপাদানই মূলত আমরা এইমাত্র বেছে নেওয়া রাইট বা Right উপাদানটির সাথে একটি করে ইনভার্সন (inversion) ঘটাবে।

সুতরাং: আপনি যখন রাইট বা Right থেকে অনুলিপি বা কপি করবেন, তখন ইনভার্সন কাউন্ট বা গণনার সাথে (Left এ থাকা বাকি বা অবশিষ্ট উপাদানগুলোর সংখ্যা) যোগ করে নিন। এটি কোনো অতিরিক্ত অ্যাসিম্পটোটিক (asymptotic) খরচ ছাড়াই মার্জ সর্টের বা merge sort এর স্কন্ধের ওপর ভর করে চলে — যার মানে এটি সর্বমোট \(O(n \log n)\) সময়েই তার কাজ সম্পন্ন করতে পারে।

উদাহরণের সাহায্যে পর্যালোচনা (Example walkthrough)

অ্যারে বা Array: [3, 1, 2]। এখানকার ইনভার্সনগুলো হলো (3,1) এবং (3,2) — অর্থাৎ কাউন্ট বা গণনা = 2।

মার্জ সর্ট (Merge sort) এটিকে [3] এবং [1, 2] তে বিভক্ত করে। Left=[3], Right=[1,2]। প্রথমত, আমরা Right থেকে 1 তুলি (1 < 3) — Left এ অবশিষ্ট থাকা 1 টি উপাদান যোগ করুন → কাউন্ট count += 1। তারপর Right থেকে 2 তুলি (2 < 3) — Left এ অবশিষ্ট থাকা 1 টি উপাদান যোগ করুন → কাউন্ট count += 1। মোট বা Total = 2। একদম সঠিক উত্তর!

দ্রষ্টব্য: ইনভার্সনগুলো (Inversions) শুধুমাত্র কোনো কৌতূহলের বিষয় নয় — এগুলো মূলত কোলাবোরেটিভ ফিল্টারিং বা সহযোগী ফিল্টারিংয়ে (collaborative filtering) (দুজন ব্যক্তির পছন্দের র‍্যাঙ্কিং বা তালিকা কতটা সীমান বা একই রকম?), সর্টিং অ্যালগরিদমগুলোর (sorting algorithms) পারফরম্যান্স বা কর্মক্ষমতা পরিমাপ করতে এবং এমনকি জেনেটিক্সের (genetics) জিন সিকোয়েন্সের বা জিনের ক্রমানুসারের তুলনা করতেও ব্যাপকভাবে ব্যবহৃত হয়।

মডিফাইড বা পরিবর্তিত মার্জ সর্টের সাহায্যে ইনভার্সন গণনা (Count Inversions via Modified Merge Sort)

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, left_inv = count_inversions(arr[:mid])
    right, right_inv = count_inversions(arr[mid:])
    merged, split_inv = merge_count(left, right)
    return merged, left_inv + right_inv + split_inv


def merge_count(left, right):
    result = []
    inversions = 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            # All remaining left elements form inversions with right[j]
            inversions += len(left) - i
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result, inversions


arr = [3, 1, 4, 1, 5, 9, 2, 6]
_, count = count_inversions(arr)
print(count)  # 9
Output
9

Complexity

🐌 সাধারণ বা লেইজি পেয়ার চেক (Naive pair check)
i < j এর সাথে থাকা সমস্ত (i, j) জোড়াগুলো পরীক্ষা বা চেক করুন — এটি ছোট অ্যারেগুলোর জন্য ঠিক থাকলেও, বড় অ্যারেগুলোর ক্ষেত্রে এটি অনেক কষ্টদায়ক বা পেইনফুল (painful)
কোয়াড্রাটিক বা দ্বিঘাতী (Quadratic) \(O(n^2)\)
⚡ পরিবর্তিত বা মডিফাইড মার্জ সর্ট (Modified merge sort)
মার্জ সর্টের কাঁধে ভর দিয়ে বা পিগিব্যাক (Piggybacks) করে চলে — এর গণনার জন্য কোনো অতিরিক্ত অ্যাসিম্পটোটিক (asymptotic) খরচ যোগ করতে হয় না
লগ-লিনিয়্যার (Log-linear) \(O(n \log n)\)
💾 মেমরি বা স্পেস (অক্সিলিয়ারি অ্যারে বা auxiliary array)
এটি মূলত একটি সাধারণ মার্জ সর্টের (merge sort) মতোই একটি অস্থায়ী বা টেম্পরারি মার্জ বাফার (Temporary merge buffer) ব্যবহার করে
লিনিয়ার (Linear) \(O(n)\)
📊 সম্ভাব্য সর্বোচ্চ ইনভার্সন (Max possible inversions)
এখানে থাকা প্রতিটি জোড়াই মূলত অর্ডারের বা ক্রমানুসারের বাইরে থাকে — এটি হলো সম্ভাব্য সবচেয়ে এলোমেলো বা শাফল (shuffled) করা আয়োজন বা অ্যারেঞ্জমেন্ট
বিপরীতভাবে সাজানো বা রিভার্স-সর্টেড (Reverse-sorted) অ্যারে n(n−1)/2

ছোট কুইজ

[4, 3, 2, 1] এই অ্যারেটিতে ঠিক কতগুলো ইনভার্সন (inversions) আছে?

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