মেল্ড অপারেশনের অ্যামোর্টাইজড কস্ট

মেল্ড অপারেশনের অ্যামোর্টাইজড কস্ট ক্যালকুলেট করা একটি কঠিন কাজ। প্রধান সমস্যা হল র‍্যান্ডম অপারেশন সিকোয়েন্সে বিভিন্ন পয়েন্টে একই অপারেশনের খরচের বিস্তৃত পরিবর্তনশীলতা গড়ে তোলা। যদিও আমাদের ডিজাইন লক্ষ্য অপারেশন সিকোয়েন্সের খরচ দ্বারা প্রভাবিত হয়, অ্যামোর্টাইজড কস্টের ধারণা কেবল সিকোয়েন্সের খরচের পদের মাধ্যমে ডিফাইন করলে কিছুই হয় না। একটি পটেনশিয়াল ফাংশন বাস্তবায়ন করে বাস্তব খরচের পরিবর্তনশীলতা অফসেট করা পরিস্থিতি হ্যান্ডেল করার একটি সঠিক উপায়। পরবর্তী টপিকে আমরা অ্যামোর্টাইজড কস্টের ধারণা আলোচনা করব।

মনে করুন B হল একটি অ্যাবস্ট্রাক্ট ডেটা টাইপ (ADT) যার বেসিক অপারেশন P = {P₁, P₂, …, Pₖ} এবং DS হল B-কে বাস্তবায়নকারী একটি ডেটা স্ট্রাকচার। F হল ডেটা স্ট্রাকচার কনফিগারেশনে নির্দিষ্ট একটি পটেনশিয়াল ফাংশন যেটি নন-নেগেটিভ রিয়েল নম্বর রিটার্ন করে। আরও মনে করুন F(Φ) = 0। DSʲ নির্দেশ করে যে কনফিগারেশন আমরা পাই যদি কনফিগারেশন DS-এ একটি অপারেশন Pₖ পারফর্ম করি এবং C নির্দেশ করে Pₖ কে DS-এ পারফর্ম করার বাস্তব খরচ।

তাহলে, DS-এ অপারেট করে Pₖ-এর অ্যামোর্টাইজড কস্ট, a(Pₖ, DS) দ্বারা প্রকাশিত, নিচের সূত্র দিয়ে দেয়া হয়:

a(Pₖ, DS) = C + F(DSʲ) – F(DS)

যদি সব m সাইজের কনফিগারেশন DS-এ a(Pₖ, DS) ≤ c·g(m) হয়, তবে আমরা বুঝতে পারি যে Pₖ-এর অ্যামোর্টাইজড কস্ট O(g(m))।