অমর্টাইজড বিশ্লেষণ ক্রিয়াকলাপগুলির একটি অনুক্রমের জন্য রান টাইম নির্ধারণ করতে ব্যবহৃত হয়, ক্রম অনুসারে প্রয়োজনীয় গড় সময়। ইনকে অ্যালগরিদমে করা গড়-কেস বিশ্লেষণ হিসাবে বিবেচনা করা যায় না কারণ এটি সর্বদা গড় কেস পরিস্থিতি নেয় না। এমন কিছু ঘটনা রয়েছে যা বিশ্লেষণের সবচেয়ে খারাপ পরিস্থিতি হিসাবে ঘটে। সুতরাং, একটি ক্রমানুসারে একাধিক অপারেশনের জন্য পরিমার্জিত বিশ্লেষণকে সবচেয়ে খারাপ-কেস বিশ্লেষণ হিসাবে বিবেচনা করা যেতে পারে। এখানে, প্রতিটি অপারেশন করার খরচ বিভিন্ন এবং কিছু জন্য তার উচ্চ. এই সমস্যাটি বাইনারি কাউন্টার ব্যবহার করে একটি সাধারণ দৃশ্য।
চলুন c++ প্রোগ্রামিং ল্যাঙ্গুয়েজ এর কাজ এবং বাস্তবায়ন দেখি যাতে আমরা ধারণার সাথে পরিষ্কার হতে পারি।
একটি k-বিট বাইনারি কাউন্টার প্রয়োগ করা হয় k দৈর্ঘ্যের একটি বাইনারি অ্যারে ব্যবহার করে যার মূল্য প্রাথমিকভাবে 0। এই মানের উপর, ইনক্রিমেন্ট অপারেশন একাধিকবার সঞ্চালিত হয়। এখানে বাইনারি 8-বিট অ্যারে এটিতে সম্পাদিত বৃদ্ধির ক্রিয়াকলাপে কীভাবে আচরণ করবে।
প্রাথমিকভাবে, 00000000> 00000001> 00000010> 00000011> 00000100> 00000101>....> 11111111।
এই লজিকটি হল সংখ্যার শেষ বিট থেকে প্রথম 0 এর উপস্থিতি পরীক্ষা করা এবং এটি 1 এ ফ্লিপ করা এবং সমস্ত বিট ক্রমিকভাবে 0 এ অনুসরণ করা।
উদাহরণ
#include <iostream>
using namespace std;
int main(){
int number[] = {1,0,0,1,0,1,1,1};
int length = 8;
int i = length - 1;
while (number[i] == 1) {
number[i] = 0;
i--;
}
if (i >= 0)
str[i] = 1;
for(int i = 0 ; i<length ; i++)
cout<<number[i]<<" ";
} আউটপুট
1 0 0 1 0 0 0 0
এই সমস্যায়, প্রতিটি অপারেশনের খরচ স্থির থাকে এবং বিটের সংখ্যার উপর নির্ভর করে না,
এখানে একটি সিকোয়েন্সের খরচের জন্য অ্যাসিম্পোটিক বিশ্লেষণ হল O(n).
n অপারেশনে করা মোট ফ্লিপ সংখ্যা হল − n + n/2 + n/4 + ….. + n/k 2 ফ্লিপের সংখ্যায় k।
এটি একটি জিপি যার হর-এ HP রয়েছে।
ফ্লিপের যোগফল
যোগফল =n + n/2 + n/4 + ….. + n/k
2
এখন, অপারেশনের সুগন্ধযুক্ত খরচ হল O(n) / 2n =O(1)
ক্রমটি হল O(1) যা সংখ্যার বিটের সংখ্যা n এর সমানুপাতিক নয়।
