সম্ভাব্য পদ্ধতি

কম্পিউটেশনাল জটিলতা তত্ত্ব অনুসারে, সম্ভাব্য পদ্ধতিটিকে একটি ডেটা কাঠামোর পরিমার্জিত সময় এবং স্থান জটিলতা বিশ্লেষণ করার জন্য প্রয়োগ করা একটি পদ্ধতি হিসাবে সংজ্ঞায়িত করা হয়, অপারেশনগুলির ক্রমগুলির উপর এটির কার্যকারিতার একটি পরিমাপ যা বিরল কিন্তু ব্যয়বহুল অপারেশনগুলির খরচ দূর করে৷

সম্ভাব্য পদ্ধতিতে, একটি ফাংশন Φ নির্বাচন করা হয় যা ডেটা স্ট্রাকচারের অবস্থাকে অ-নেতিবাচক সংখ্যায় রূপান্তর করে। যদি S কে ডেটা স্ট্রাকচারের অবস্থা হিসাবে বিবেচনা করা হয়, Φ(S) সেই কাজগুলিকে নির্দেশ করে যা পরিবর্ধিত বিশ্লেষণে হিসাব করা হয়েছে কিন্তু এখনও সম্পাদিত হয়নি। এইভাবে, Φ(S) কে সেই অবস্থায় সঞ্চিত সম্ভাব্য শক্তির পরিমাণ গণনা হিসাবে কল্পনা করা যেতে পারে। একটি ডেটা স্ট্রাকচার শুরু করার আগে, সম্ভাব্য মানটি শূন্য হিসাবে সংজ্ঞায়িত করা হয়। বিকল্পভাবে, Φ(S) কে S রাজ্যে ব্যাধির পরিমাণ বা একটি আদর্শ অবস্থা থেকে এর দূরত্বের প্রতিনিধিত্বকারী হিসাবে কল্পনা করা যেতে পারে।

উদাহরণ

আসুন আমরা একটি সম্ভাব্য ফাংশন Φ বোঝাতে পারি (পড়ুন "Phi") একটি ডেটা স্ট্রাকচারের অবস্থার উপর নিম্নলিখিত বৈশিষ্ট্যগুলিকে সন্তুষ্ট করে -

• Φ(a0) =0, যেখানে a0 হল ডেটা স্ট্রাকচারের শুরুর অবস্থা।
• Φ(at) ≥ 0 সমস্ত রাজ্যের জন্য ডেটা স্ট্রাকচারের সময় যে কম্পিউটেশনের সময় ঘটে।

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

তারপরে আমরা একটি অপারেশনের পরিমার্জিত সময়কে

c + Φ(a') − Φ(a),

যেখানে c হল অপারেশনের মূল খরচ এবং a এবং a' যথাক্রমে অপারেশনের আগে এবং পরে ডেটা স্ট্রাকচারের অবস্থা। এইভাবে পরিমার্জিত সময়কে প্রকৃত সময় এবং সম্ভাব্য পরিবর্তন হিসাবে সংজ্ঞায়িত করা হয়। আদর্শভাবে, Φ সংজ্ঞায়িত করা উচিত যাতে প্রতিটি অপারেশনের পরিমার্জিত সময় ছোট হওয়া উচিত। এইভাবে সম্ভাব্য পরিবর্তনকে কম খরচের অপারেশনের জন্য ইতিবাচক এবং উচ্চ খরচের অপারেশনের জন্য নেতিবাচক হিসাবে পরিমাপ করা উচিত।