জটিলতা ও বিশ্লেষণ৭ মিনিট পড়া

অ্যামোর্টাইজড অ্যানালাইসিস (Amortized Analysis)

একটি বড় বিল, ছোট ছোট কিস্তিতে পরিশোধ করা
push (typical):O(1) — শুধু রাইট (write) করাpush (with resize):O(n) — কদাচিৎ বড় খরচpush (amortized):O(1)* গড়ে খরচn pushes total:নিশ্চিতভাবে O(n)

ধরুন একটি জিমের সদস্যপদের কথা চিন্তা করুন। বেশিরভাগ মাসেই আপনি শুধু ৩০ ডলার দেন এবং জিমে যান। কিন্তু বছরে একবার সেখানে ৩০০ ডলারের বার্ষিক ফি বা ইকুইপমেন্ট ফি দিতে হয়। আপনি যদি সেই ফি ১২ মাসের সবার মধ্যে ভাগ করে দেন, তাহলে গড়ে মাসে মাত্র ২৫ ডলার করে বেশি দিতে হয়। অর্থাৎ, একবারের বড় পেমেন্ট প্রথম দেখাতে কষ্টকর মনে হলেও — সেটি ভাগ করে দিলে বেশ সাশ্রয়ী হয়।

অ্যামোর্টাইজড অ্যানালাইসিস (Amortized Analysis) ঠিক একইভাবে কাজ করে। "একটি একক অপারেশনে কতটা সর্বোচ্চ সময় লাগতে পারে?" এই প্রশ্নটি জিজ্ঞাসা করার পরিবর্তে, এটি জিজ্ঞাসা করে "দীর্ঘক্ষণ ধরে চলা অনেকগুলো অপারেশনে প্রতিটি অপারেশনের জন্য গড়ে কত খরচ হয়?" কিছু অপারেশন বেশ ব্যয়বহুল বা দামি হতে পারে, তবে যদি সেগুলো যথেষ্ট বিরল (rare) হয়, তবে দীর্ঘমেয়াদে গড় (average) খরচ খুব কমই থাকে।

ক্লাসিক উদাহরণ: ডাইনামিক অ্যারে পুশ (Dynamic Array Push)

একটি ডাইনামিক অ্যারে (Python-এর list, Java-এর ArrayList) ছোট আকার থেকে শুরু হয় এবং যখন এটি ভরে যায় তখন এর ধারণক্ষমতা (capacity) বা সাইজ দ্বিগুণ করে। বেশিরভাগ push কলগুলো হলো O(1) — অর্থাৎ শুধুমাত্র পরবর্তী ফাঁকা জায়গায় রাইট (write) করা। কিন্তু যখন অ্যারেটি সম্পূর্ণ ভরে যায়, তখন এটি অবশ্যই পূর্বের চেয়ে দ্বিগুণ বড় একটি নতুন অ্যারে তৈরি করে এবং সব ডেটা সেখানে কপি করে। এই রিসাইজ (resize) করতে সময় লাগে O(n)।

একবারের ব্যয়বহুল রিসাইজ দেখে আপনার মনে হতে পারে যে পুশ করাটা বেশ ধীরগতির। কিন্তু পুরো চিত্রটা একটু কল্পনা করুন: যদি অ্যারেটি সবেমাত্র n/2 সাইজ থেকে দ্বিগুণ হয়ে n হয়ে থাকে, আপনি n/2 সংখ্যক উপাদান কপি করেছেন। পুনরায় রিসাইজ করার আগে, আপনাকে আরও n/2 সংখ্যক সস্তা বা কম খরচের পুশ করতে হবে। তাই প্রতিটি উপাদান নিজস্ব ভবিষ্যৎ কপির জন্য একপ্রকার আগাম মূল্য বা "পেমেন্ট" পরিশোধ করে রাখে। সমস্ত পুশগুলোর মধ্যে ছড়িয়ে দিলে, প্রতিটি পুশের জন্য গড়ে অ্যামোর্টাইজড খরচ বা সময় O(1) হয়ে দাঁড়ায়।

এটি প্রমাণের তিনটি পদ্ধতি (The Three Methods for Proving It)

অ্যাগ্রিগেট পদ্ধতি (Aggregate method): n সংখ্যক অপারেশনের জন্য মোট কাজের পরিমাণ গণনা করুন, তারপর সেটিকে n দিয়ে ভাগ করুন। ডাবলিং বা দ্বিগুণ করার মাধ্যমে n বার পুশ করার জন্য: রিসাইজগুলোতে 1 + 2 + 4 + … + n/2 সংখ্যক উপাদান, অর্থাৎ মোট O(n) সংখ্যক উপাদান কপি করা হয়। সুতরাং n সংখ্যক পুশের জন্য মোট খরচ O(n) → তাই প্রতিটির জন্য খরচ O(1)।

অ্যাকাউন্টিং পদ্ধতি (Accounting method): প্রতিটি পুশকে 3 ইউনিটের একটি "ক্রেডিট" দিন: 1 ইউনিট ইনসার্ট করার জন্য, এবং 2 ইউনিট জমা রাখার জন্য। যখন একটি রিসাইজ ঘটে, তখন প্রতিটি উপাদানের জন্য ওই জমা রাখা 2 ক্রেডিট দিয়ে সেই উপাদানটিকে এবং নতুন অ্যারের অতিরিক্ত একটি জায়গাকেও কপি করার খরচ মেটানো হয়। ক্রেডিট কখনোই নেগেটিভ হয় না, যা এর সত্যতাকে জোরালোভাবে প্রমাণ করে।

পটেনশিয়াল পদ্ধতি (Potential method): একটি পটেনশিয়াল বা সম্ভাবনা Φ (সঞ্চিত শক্তির মতো) সংজ্ঞায়িত করুন যা অ্যারে ভরার সাথে সাথে বেড়ে যায় এবং রিসাইজ হওয়ার সময় কমে যায়। অ্যামোর্টাইজড খরচ = আসল খরচ + ΔΦ। ডাইনামিক অ্যারের জন্য একটি ভালো Φ হতে পারে 2·(size) − capacity। এই পদ্ধতিটি জটিল ডেটা কাঠামোর বেলায়ও দারুণভাবে কাজ করে যেখানে শুধুমাত্র সাধারণ কল্পনা করাটা যথেষ্ট নয়।

দ্রষ্টব্য: অ্যামোর্টাইজড O(1) এর মানে এই নয় যে প্রতিটি অপারেশনই দ্রুত। এর মানে হলো আপনি যতগুলো অপারেশনই করেন না কেন, মোট খরচকে গণনা দিয়ে ভাগ করলে তা O(1)-ই হবে। মাঝে মাঝে একটি বড় স্পাইক বা খরচ থাকাটা স্বাভাবিক — যতক্ষণ না সেটি বারবার বা ঘন ঘন ঘটছে।

ডাইনামিক অ্যারে পুশ — রিসাইজিং পর্যবেক্ষণ

import sys


class DynamicArray:
    def __init__(self):
        self._cap = 1
        self._size = 0
        self._data = [None] * self._cap


    def push(self, val):
        if self._size == self._cap:
            self._resize()
        self._data[self._size] = val
        self._size += 1


    def _resize(self):
        new_cap = self._cap * 2
        print(f"  Resize! {self._cap} -> {new_cap}, copying {self._cap} elements")
        new_data = [None] * new_cap
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._cap = new_cap


arr = DynamicArray()
for i in range(9):
    print(f"Push {i}")
    arr.push(i)
Output
Push 0
  Resize! 1 -> 2, copying 1 elements
Push 1
  Resize! 2 -> 4, copying 2 elements
Push 2
Push 3
  Resize! 4 -> 8, copying 4 elements
Push 4
Push 5
Push 6
Push 7
  Resize! 8 -> 16, copying 8 elements
Push 8

Complexity

⚡ পুশ (রিসাইজের প্রয়োজন নেই)
সাধারণ কেস — এটি সবচেয়ে বেশি বা প্রায়শই ঘটে
তাৎক্ষণিক — শুধু লেখা বা রাইট করা O(1)
💸 পুশ (রিসাইজ ট্রিগার করে)
বিরল স্পাইক — ক্যাপাসিটি দ্বিগুণ করে এবং সমস্ত উপাদান কপি করে
বর্তমান সাইজের সাপেক্ষে লিনিয়ার (Linear) O(n)
📊 পুশ (অ্যামোর্টাইজড হিসেবে গড়ে)
রিসাইজ করার এই বিশাল খরচকে পূর্বে করা সব পুশগুলোর মধ্যে ভাগ বা ছড়িয়ে দেওয়া হয়
গড়ে একটি কনস্ট্যান্ট বা ধ্রুবক O(1)*
🧮 সর্বমোট n সংখ্যক পুশ
1 + 2 + 4 + … + n = 2n, প্রতিটি রিসাইজে সব কপিগুলো মিলিয়ে মোট কপি
মোট কাজের পরিমাণ লিনিয়ার (Linear) O(n)

ছোট কুইজ

একটি ডাইনামিক অ্যারে উপচে পড়লে বা ওভারফ্লো (overflow) হলে এর ক্যাপাসিটি দ্বিগুণ করে। মোট n বার পুশ করার পর, সমস্ত রিসাইজ ইভেন্ট মিলিয়ে মোট কপি করার কাজের পরিমাণ কত হবে?

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