অমোরটাইজড কমপ্লেক্সিটি

অমোরটাইজড অ্যানালিসিস

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

হ্যাশ-টেবিলে অধিকাংশ সময় সার্চিং টাইম কমপ্লেক্সিটি O(1), কিন্তু কখনও কখনও এটি O(n) অপারেশন এক্সিকিউট করে। হ্যাশ টেবিলে এলিমেন্ট সার্চ বা ইনসার্ট করার সময় অধিকাংশ কেসে এটি কনস্ট্যান্ট টাইম নেয়, কিন্তু колиশন হলে সংঘাত সমাধানের জন্য O(n) টাইম অপারেশন দরকার হয়।

এগ্রিগেট মেথড

এগ্রিগেট মেথড মোট খরচ বের করতে ব্যবহৃত হয়। যদি আমরা অনেক ডেটা যোগ করতে চাই, তবে আমরা এই ফর্মুলা দিয়ে অমোরটাইজড কস্ট বের করি।

n সংখ্যক অপারেশনের সিকোয়েন্সের জন্য, খরচ হলো −

অমোরটাইজড অ্যানালিসিসের উদাহরণ

ডাইনামিক অ্যারে জন্য, আইটেম একটি নির্দিষ্ট ইন্ডেক্সে O(1) টাইমে ইনসার্ট করা যায়। কিন্তু যদি সে ইন্ডেক্স অ্যারেতে না থাকে, তবে এটি কনস্ট্যান্ট টাইমে টাস্ক সম্পন্ন করতে ব্যর্থ হয়। সেক্ষেত্রে, এটি প্রাথমিকভাবে অ্যারের আকার ডাবল করে তারপর এলিমেন্ট ইনসার্ট করে যদি ইন্ডেক্স উপস্থিত থাকে।

ডাইনামিক অ্যারের জন্য, ci = i-তম ইনসারশনের কস্ট।