বিভক্ত এবং পুনরাবৃত্তি জয়ের জন্য উন্নত মাস্টার উপপাদ্য

বিভক্ত করুন এবং জয় করুন এটি একটি অ্যালগরিদম যা একই ধরণের একাধিক উপ-সমস্যাগুলির মধ্যে পুনরাবৃত্তভাবে শাখা সমস্যাগুলির উপর ভিত্তি করে দৃষ্টান্তের উপর কাজ করে যা সহজেই সমাধান করা যায়।

উদাহরণ

ডিভাইড অ্যান্ড কনক্যুয়ার টেকনিক −

function recursive(input x size n)
   if(n < k)
      Divide the input into m subproblems of size n/p.
      and call f recursively of each sub problem
   else
      Solve x and return

সমস্ত উপ-সমস্যার ফলাফল একত্রিত করুন এবং মূল সমস্যার সমাধান ফিরিয়ে দিন।

ব্যাখ্যা − উপরোক্ত সমস্যায়, সমস্যা সেটটিকে ছোট ছোট উপসমস্যাগুলিতে ভাগ করতে হবে যা সহজেই সমাধান করা যেতে পারে।

বিভাজন এবং জয়ের জন্য মাস্টার্স থিওরেম একটি বিশ্লেষণ উপপাদ্য যা পুনরাবৃত্তিমূলক সম্পর্ক অ্যালগরিদমের জন্য একটি বড়-0 মান নির্ধারণ করতে ব্যবহার করা যেতে পারে। এটি অ্যালগরিদম দ্বারা প্রয়োজনীয় সময় খুঁজে বের করতে এবং এটিকে অ্যাসিম্পটোটিক নোটেশন আকারে উপস্থাপন করতে ব্যবহৃত হয়।

উপরের উদাহরণে সমস্যার রানটাইম মানের উদাহরণ -

T(n) = f(n) + m.T(n/p)

বেশিরভাগ পুনরাবৃত্ত অ্যালগরিদমের জন্য, আপনি মাস্টারের উপপাদ্য ব্যবহার করে অ্যালগরিদমের জন্য সময় জটিলতা খুঁজে পেতে সক্ষম হবেন, কিন্তু কিছু ক্ষেত্রে মাস্টারের উপপাদ্য প্রযোজ্য নাও হতে পারে। এগুলি এমন ক্ষেত্রে যেখানে মাস্টারের উপপাদ্য প্রযোজ্য নয়। যখন সমস্যা T(n) একঘেয়ে না হয়, উদাহরণস্বরূপ, T(n) =sin n. সমস্যা ফাংশন f(n) একটি বহুপদ নয়।

সময় জটিলতা খুঁজে বের করার জন্য মাস্টার থিওরেম এই ক্ষেত্রে গরম দক্ষ নয়, এবং পুনরাবৃত্ত পুনরাবৃত্তির জন্য উন্নত মাস্টার উপপাদ্য ডিজাইন করা হয়েছিল। এটি ফর্ম −

T(n) = aT(n/b) + ø((n^k)logpn)

যেখানে n হল সমস্যার আকার।

a =পুনরাবৃত্তিতে উপ-সমস্যাগুলির সংখ্যা, a> 0

n/b =প্রতিটি উপসমস্যার আকার b> 1, k>=0 এবং p হল একটি বাস্তব সংখ্যা।

এই ধরনের সমস্যা সমাধানের জন্য, আমরা নিম্নলিখিত সমাধানগুলি ব্যবহার করব,

• যদি a>b_k হয় , তারপর T(n) =∅ (nlogba)
• যদি a =b_k হয় , তারপর
  • যদি p> -1 হয়, তাহলে T(n) =∅(nlogba log ^p+1 n)
  • যদি p =-1 হয়, তাহলে T(n) =∅(nlog_ba loglogn)
  • যদি p <-1 হয়, তাহলে T(n) =∅(nlog_ba )
• যদি ak হয় , তারপর
  • যদি p> =0, তাহলে T(n)=∅(n_k লগ_p n)
  • যদি p<0 হয়, তাহলে T(n) =∅(nk)

উন্নত মাস্টার অ্যালগরিদম ব্যবহার করে, আমরা কিছু অ্যালগরিদমের জটিলতা গণনা করব -

বাইনারী অনুসন্ধান − t(n) =θ(logn)

বাছাই মার্জ করুন − T(n) =θ(nlogn)