Potential method
গণনামূলক জটিলতা তত্ত্বে, সম্ভাব্য পদ্ধতি হল একটি পদ্ধতি যা একটি তথ্য কাঠামোর পরিশোধিত সময় এবং স্থান জটিলতা বিশ্লেষণ করতে ব্যবহৃত হয়, যা ক্রিয়াকলাপের ক্রমের উপর তার কার্যকারিতার একটি পরিমাপ যা বিরল কিন্তু ব্যয়বহুল ক্রিয়াকলাপের ব্যয়কে মসৃণ করে। ঋণ পরিশোধিত সময়ের সংজ্ঞা সম্ভাব্য পদ্ধতিতে, একটি ফাংশন φ বেছে নেওয়া হয় যা অ-ঋণাত্মক সংখ্যার সাথে তথ্য কাঠামোর অবস্থার মানচিত্র তৈরি করে। যদি এস তথ্য কাঠামোর একটি অবস্থা হয়, ± (এস) এমন কাজের প্রতিনিধিত্ব করে যা ঋণ পরিশোধিত বিশ্লেষণে হিসাব করা হয়েছে ("প্রদত্ত") কিন্তু এখনও সম্পাদিত হয়নি। সুতরাং, φ (S) কে সেই অবস্থায় সঞ্চিত সম্ভাব্য শক্তির পরিমাণ গণনা হিসাবে বিবেচনা করা যেতে পারে। একটি তথ্য কাঠামো শুরু করার আগে সম্ভাব্য মান শূন্য হিসাবে সংজ্ঞায়িত করা হয়। বিকল্পভাবে, φ (S)-কে S অবস্থার বিশৃঙ্খলার পরিমাণ বা একটি আদর্শ অবস্থা থেকে তার দূরত্বের প্রতিনিধিত্বকারী হিসাবে বিবেচনা করা যেতে পারে। ধরা যাক কোনও ডেটা স্ট্রাকচারের ক্রমানুসারে যে কোনও পৃথক ক্রিয়াকলাপ হতে পারে, যার মধ্যে 'ও' ক্রিয়াকলাপের আগে ডেটা স্ট্রাকচারের অবস্থা নির্দেশ করার আগে 'ও' এবং 'ও' ক্রিয়াকলাপ শেষ হওয়ার পরে 'সাফ্টার' তার অবস্থা নির্দেশ করে। একবার φ নির্বাচিত হয়ে গেলে, অপারেশন o-এর জন্য ঋণ পরিশোধিত সময়কে এমনভাবে সংজ্ঞায়িত করা হয় যেখানে C হল আনুপাতিকতা (সময়ের এককে)-র একটি অ-ঋণাত্মক ধ্রুবক যা বিশ্লেষণ জুড়ে স্থির থাকতে হবে। অর্থাৎ, ঋণ পরিশোধের সময়কে অপারেশন দ্বারা গৃহীত প্রকৃত সময় এবং অপারেশন দ্বারা সৃষ্ট সম্ভাবনার পার্থক্যের সি গুণ হিসাবে সংজ্ঞায়িত করা হয়। বড় ও স্বরলিপি ব্যবহার করে অ্যাসিম্পটোটিক গণনামূলক জটিলতা অধ্যয়ন করার সময়, ধ্রুবক কারণগুলি অপ্রাসঙ্গিক এবং তাই ধ্রুবক সি সাধারণত বাদ দেওয়া হয়। ঋণ পরিশোধিত এবং প্রকৃত সময়ের মধ্যে সম্পর্ক এর কৃত্রিম চেহারা সত্ত্বেও, ক্রিয়াকলাপের একটি ক্রমের মোট ঋণ পরিশোধিত সময় ক্রিয়াকলাপের একই ক্রমের জন্য প্রকৃত সময়ে একটি বৈধ ঊর্ধ্বসীমা প্রদান করে। ক্রিয়াকলাপের যে কোনও ক্রমের জন্য, সংজ্ঞায়িত করুনঃ মোট পরিশোধিত সময়ঃ মোট প্রকৃত সময়ঃ তারপরঃ যেখানে সম্ভাব্য ফাংশনের মানগুলির ক্রম একটি টেলিস্কোপিং সিরিজ গঠন করে যেখানে প্রাথমিক এবং চূড়ান্ত সম্ভাব্য ফাংশনের মান ব্যতীত সমস্ত পদ জোড়ায় বাতিল হয়। এটি পুনর্বিন্যাস করে, আমরা পাইঃ যেহেতু এবং, তাই ঋণ পরিশোধিত সময়টি ক্রিয়াকলাপের একটি ক্রমের প্রকৃত সময়ের উপর একটি সঠিক ঊর্ধ্বসীমা প্রদান করতে ব্যবহার করা যেতে পারে, যদিও একটি পৃথক ক্রিয়াকলাপের জন্য ঋণ পরিশোধিত সময় তার প্রকৃত সময়ের থেকে ব্যাপকভাবে পরিবর্তিত হতে পারে। সবচেয়ে খারাপ-কেস ইনপুটগুলির আমোর্টাইজড বিশ্লেষণ সাধারণত, আমোর্টাইজড বিশ্লেষণ ইনপুট ক্রম সম্পর্কে সবচেয়ে খারাপ কেস অনুমানের সাথে সংমিশ্রণে ব্যবহৃত হয়। এই অনুমানের সাথে, যদি এক্স একটি ধরনের অপারেশন যা ডেটা স্ট্রাকচার দ্বারা সম্পাদিত হতে পারে, এবং এন একটি পূর্ণসংখ্যা যা প্রদত্ত ডেটা স্ট্রাকচারের আকারকে সংজ্ঞায়িত করে (উদাহরণস্বরূপ, এতে থাকা আইটেমগুলির সংখ্যা), তবে টাইপ এক্স-এর ক্রিয়াকলাপের জন্য ঋণ পরিশোধের সময়কে সর্বাধিক হিসাবে সংজ্ঞায়িত করা হয়, আকার এন-এর ডেটা স্ট্রাকচারের ক্রিয়াকলাপের সমস্ত সম্ভাব্য ক্রম এবং ক্রমানুসারে টাইপ এক্স-এর সমস্ত ক্রিয়াকলাপের মধ্যে, অপারেশন ওআই-এর জন্য ঋণ পরিশোধের সময়। এই সংজ্ঞার সাথে, ক্রিয়াকলাপের ক্রম সম্পাদনের সময়টি ক্রমানুসারে প্রতিটি ধরণের ক্রিয়াকলাপের জন্য পরিশোধিত সময়কে সেই ধরণের ক্রিয়াকলাপের সংখ্যা দ্বারা গুণ করে অনুমান করা যেতে পারে। উদাহরণ গতিশীল অ্যারে একটি গতিশীল অ্যারে হল আইটেমগুলির একটি অ্যারে বজায় রাখার জন্য একটি ডেটা স্ট্রাকচার, যা অ্যারের মধ্যে অবস্থানগুলিতে এলোমেলো অ্যাক্সেস এবং অ্যারের আকার এক দ্বারা বাড়ানোর ক্ষমতা উভয়কেই অনুমতি দেয়। এটি জাভাতে "অ্যারে-লিস্ট" টাইপ এবং পাইথনে "লিস্ট" টাইপ হিসাবে পাওয়া যায়। একটি গতিশীল অ্যারে একটি ডেটা স্ট্রাকচার দ্বারা প্রয়োগ করা যেতে পারে যা কিছু দৈর্ঘ্যের এন আইটেমগুলির একটি অ্যারে নিয়ে গঠিত, একসাথে একটি সংখ্যা এন ≤ এন যা এখনও পর্যন্ত ব্যবহৃত অ্যারের মধ্যে অবস্থানগুলি উপস্থাপন করে। এই কাঠামোর সাহায্যে, অভ্যন্তরীণ অ্যারে এ-এর একই কোষে প্রবেশের মাধ্যমে গতিশীল অ্যারেতে এলোমেলো প্রবেশাধিকার প্রয়োগ করা যেতে পারে এবং যখন n <N একটি অপারেশন যা গতিশীল অ্যারের আকার বৃদ্ধি করে কেবল n বৃদ্ধি করে প্রয়োগ করা যেতে পারে। তবে, যখন n = N, তখন A-এর আকার পরিবর্তন করা প্রয়োজন, এবং এটি করার জন্য একটি সাধারণ কৌশল হল এর আকার দ্বিগুণ করা, A-কে 2n দৈর্ঘ্যের একটি নতুন অ্যারে দ্বারা প্রতিস্থাপন করা। এই কাঠামোটি সম্ভাব্য ফাংশন ব্যবহার করে বিশ্লেষণ করা যেতে পারেঃ যেহেতু আকার পরিবর্তনের কৌশলটি সর্বদা এ-কে কমপক্ষে অর্ধ-পূর্ণ করে তোলে, তাই এই সম্ভাব্য ফাংশনটি সর্বদা অ-নেতিবাচক হয়। যখন একটি বৃদ্ধি-আকারের ক্রিয়াকলাপ একটি আকার পরিবর্তন ক্রিয়াকলাপের দিকে পরিচালিত করে না, তখন 2 দ্বারা বৃদ্ধি হয়, একটি ধ্রুবক। অতএব, অপারেশনের ধ্রুবক প্রকৃত সময় এবং সম্ভাবনার ধ্রুবক বৃদ্ধি এই ধরনের অপারেশনের জন্য একটি ধ্রুবক ঋণ পরিশোধিত সময় দিতে একত্রিত হয়। যাইহোক, যখন একটি বৃদ্ধি-আকারের ক্রিয়াকলাপ একটি আকার পরিবর্তন করে, তখন আকার পরিবর্তনের পরে φ এর সম্ভাব্য মান শূন্যে নেমে আসে। একটি নতুন অভ্যন্তরীণ অ্যারে এ বরাদ্দ করা এবং পুরানো অভ্যন্তরীণ অ্যারে থেকে নতুন অ্যারেতে সমস্ত মান অনুলিপি করতে ও (এন) প্রকৃত সময় লাগে, তবে (আনুপাতিকতা সি-এর ধ্রুবকের উপযুক্ত পছন্দ সহ) সম্ভাব্য ফাংশন হ্রাসের কারণে এটি সম্পূর্ণরূপে বাতিল হয়ে যায়, আবার অপারেশনের জন্য একটি ধ্রুবক মোট পরিশোধিত সময় রেখে যায়। তথ্য কাঠামোর অন্যান্য ক্রিয়াকলাপগুলি (অ্যারের আকার পরিবর্তন না করে অ্যারের কোষগুলি পড়া এবং লেখা) সম্ভাব্য ফাংশনকে পরিবর্তন করে না এবং তাদের প্রকৃত সময়ের মতো একই ধ্রুবক ঋণ পরিশোধিত সময় থাকে। অতএব, আকার পরিবর্তন কৌশল এবং সম্ভাব্য ক্রিয়াকলাপের এই পছন্দের সাথে, সম্ভাব্য পদ্ধতিটি দেখায় যে সমস্ত গতিশীল অ্যারে ক্রিয়াকলাপগুলি ধ্রুবক পরিশোধিত সময় নেয়। ক্রিয়াকলাপের ক্রমের উপর ঋণ পরিশোধিত সময় এবং প্রকৃত সময় সম্পর্কিত বৈষম্যের সাথে এটি একত্রিত করে, এটি দেখায় যে n গতিশীল অ্যারে ক্রিয়াকলাপের যে কোনও ক্রম সবচেয়ে খারাপ ক্ষেত্রে O (n) প্রকৃত সময় নেয়, যদিও কিছু পৃথক ক্রিয়াকলাপ নিজেরাই একটি রৈখিক পরিমাণ সময় নিতে পারে। যখন গতিশীল অ্যারেতে এমন ক্রিয়াকলাপ অন্তর্ভুক্ত থাকে যা অ্যারের আকার হ্রাস করার পাশাপাশি এটি বৃদ্ধি করে, তখন সম্ভাব্য ফাংশনটি নেতিবাচক হতে বাধা দেওয়ার জন্য অবশ্যই সংশোধন করা উচিত। এটি করার একটি উপায় হল উপরের সূত্রটিকে তার পরম মান দ্বারা প্রতিস্থাপিত করা। মাল্টি-পপ স্ট্যাক একটি স্ট্যাক বিবেচনা করুন যা নিম্নলিখিত ক্রিয়াকলাপগুলিকে সমর্থন করেঃ ইনিশিয়ালাইজ-একটি খালি স্ট্যাক তৈরি করুন। ধাক্কা-স্ট্যাকের উপরে একটি একক উপাদান যোগ করুন, স্ট্যাকটি 1 দ্বারা প্রসারিত করুন। পপ (কে)-স্ট্যাকের শীর্ষ থেকে কে উপাদানগুলি সরিয়ে ফেলুন, যেখানে কে বর্তমান স্ট্যাকের আকারের চেয়ে বেশি নয় পপ (কে) এর জন্য ও (কে) সময় প্রয়োজন, তবে আমরা দেখাতে চাই যে সমস্ত ক্রিয়াকলাপ ও (1) পরিশোধিত সময় নেয়। এই কাঠামোটি সম্ভাব্য ফাংশন ব্যবহার করে বিশ্লেষণ করা যেতে পারেঃ ± = উপাদানগুলির সংখ্যা-ইন-স্ট্যাক এই সংখ্যাটি সর্বদা অ-নেতিবাচক, প্রয়োজন অনুসারে। একটি পুশ অপারেশন ধ্রুবক সময় নেয় এবং φ কে 1 দ্বারা বৃদ্ধি করে, তাই এর পরিশোধিত সময় ধ্রুবক। একটি পপ অপারেশনে ও (কে) সময় লাগে তবে কে দ্বারা কে হ্রাস করে, তাই এর ঋণ পরিশোধের সময়ও স্থির থাকে। এটি প্রমাণ করে যে, এম ক্রিয়াকলাপের যে কোনও ক্রম সবচেয়ে খারাপ ক্ষেত্রে ও (এম) প্রকৃত সময় নেয়। বাইনারি কাউন্টার একটি বাইনারি সংখ্যা হিসাবে উপস্থাপিত এবং নিম্নলিখিত ক্রিয়াকলাপগুলিকে সমর্থনকারী একটি কাউন্টার বিবেচনা করুনঃ আরম্ভ করুনঃ 0 মান সহ একটি কাউন্টার তৈরি করুন। ইনকঃ কাউন্টারে 1 যোগ করুন। পড়ুনঃ বর্তমান পাল্টা মান ফেরত দিন। এই উদাহরণের জন্য, আমরা ট্রান্সডিকোটোমাস মেশিন মডেল ব্যবহার করছি না, বরং ইনক্রিমেন্টে প্রতি বিট অপারেশনে সময়ের একটি ইউনিট প্রয়োজন। আমরা দেখাতে চাই যে ইনক ও (1) ঋণ পরিশোধের সময় নেয়। এই কাঠামোটি সম্ভাব্য ফাংশন ব্যবহার করে বিশ্লেষণ করা যেতে পারেঃ ± = বিটের সংখ্যা-সমান-থেকে-1 = হ্যামিংওয়েট (পাল্টা) এই সংখ্যাটি সর্বদা অ-নেতিবাচক এবং প্রয়োজন অনুযায়ী 0 দিয়ে শুরু হয়। একটি ইনক অপারেশন সবচেয়ে কম উল্লেখযোগ্য বিট উল্টায়। তারপর, যদি এলএসবি 1 থেকে 0-তে উল্টে যায়, তাহলে পরবর্তী বিটটিও উল্টে যায়। এটি চলতে থাকে যতক্ষণ না শেষ পর্যন্ত একটি বিট 0 থেকে 1 এ উল্টে যায়, যে সময়ে উল্টানো বন্ধ হয়ে যায়। যদি কাউন্টারটি প্রাথমিকভাবে কে 1 বিটে শেষ হয়, আমরা মোট কে + 1 বিট উল্টাই, প্রকৃত সময় কে + 1 নিয়ে এবং সম্ভাব্য কে-1 দ্বারা হ্রাস করি, তাই ঋণ পরিশোধিত সময় হল 2। অতএব, এম ইনক অপারেশন চালানোর প্রকৃত সময় হল ও (এম)। অ্যাপ্লিকেশনগুলি সম্ভাব্য ফাংশন পদ্ধতিটি সাধারণত ফিবোনাচি স্তূপ বিশ্লেষণ করতে ব্যবহৃত হয়, যা অগ্রাধিকার সারির একটি রূপ যেখানে কোনও আইটেম অপসারণ করতে লগারিদমিক আমোর্টাইজড সময় লাগে এবং অন্যান্য সমস্ত ক্রিয়াকলাপে ধ্রুবক আমোর্টাইজড সময় লাগে। এটি স্প্লে ট্রি বিশ্লেষণ করতেও ব্যবহার করা যেতে পারে, যা বাইনারি সার্চ ট্রি-র একটি স্ব-সামঞ্জস্যপূর্ণ রূপ, যেখানে প্রতি অপারেশনে লগারিদমিক আমোর্টাইজড সময় থাকে। অ্যালগরিদমের তথ্যসূত্র বিশ্লেষণ