مسیر رتبه‌برترشدن در کنکور ارشد مهندسی کامپیوتر و IT
ثبت‌نام رایگان
مدت زمان باقیمانده :
ثانیه -
دقیقه -
ساعت -
روز -
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

قضیه اصلی (Master) در ساختمان داده و طراحی الگوریتم

قضیه اصلی (Master) در ساختمان داده و طراحی الگوریتم چیست؟ این صفحه عالی به آموزش قضیه اصلی برای روابط بازگشتی و مثال ها متنوعی را آورده

قضیه مستر یا قضیه اصلی در طراحی الگوریتمآموزش طراحی الگوریتم به زبان سادهآموزش طراحی الگوریتم به زبان سادهدرس طراحی الگوریتم‌ یکی از مهم‌ترین و بنیادیترین دروس‌ رشته کامپیوتر است. هدف از این درس، معرفی روش‌های مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است.، یکی از روش‌های متعددی است که برای محاسبه پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده  الگوریتم‌ ها به‌کار می‌رود. در تجزیه و تحلیل، پیچیدگی‌های زمانی برای یافتن بهترین منطق یک الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد محاسبه می‌شود. قضیه اصلی بر روی رابطه بازگشتیتوضیح تابع بازگشتی، دنباله بازگشتی و رابطه بازگشتیتوضیح تابع بازگشتی، دنباله بازگشتی و رابطه بازگشتیاین صفحه عالی به توضیح تابع بازگشتی و دنباله بازگشتی و رابطه بازگشتی پرداخته و توضیح داده تابع بازگشتی چیست و چگونه کار می کند و کاربرد توابع بازگشتی را گفته  اعمال می‌شود. در این مقاله به شرح این قضیه می‌پردازیم و با چند مثال نحوه عملکرد آن را درک خواهیم کرد.

قضیه مستر یا قضیه اصلی چیست؟

قضیه اصلی (مستر)

قبل از این که عمیقاً به قضیه مستر بپردازیم، اجازه دهید ابتدا بررسی کنیم که روابط بازگشتی چیست: روابط بازگشتی معادلاتی هستند که دنباله‌ای از عناصر را تعریف می‌کنند که در آنها یک عبارت تابعی از عبارت قبلی است. در تحلیل الگوریتم، روابط بازگشتی معمولاً زمانی شکل می‌گیرند که فراخوانی تابع توسط خودش، در یک الگوریتم وجود داشته باشند. قضیه اصلی را فقط می‌توان در توابع تقسیمی و کاهشی بازگشتی به کار برد. اگر رابطه کاهشی یا تقسیمی نباشد، قضیه اصلی نباید اعمال شود.

قضیه اصلی برای توابع بازگشتی

رابطه‌ای از نوع زیر را در نظر بگیرید:

$\mathrm{T}\left(\mathrm{n}\right)\mathrm{=aT}\left(\frac{\mathrm{n}}{\mathrm{b}}\right)\mathrm{+f}\left(\mathrm{n}\right)$

که در آن:

اگر رابطه بازگشتی به شکل فوق باشد، در قضیه اصلی سه حالت برای تعیین نمادهای مجانبی وجود دارد.

  1. اگر $\mathrm{a>}{\mathrm{b}}^{\mathrm{k}}$، آن‌گاه $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{{{\mathrm{log}}_{\mathrm{b}} \mathrm{a}\ }}\right)\left[{{\mathrm{log}}_{\mathrm{b}} \mathrm{a}\ }\mathrm{=}\frac{{\mathrm{log} \mathrm{a}\ }}{{\mathrm{log} \mathrm{b}\ }}\right]$
  2. اگر $\mathrm{a=}{\mathrm{b}}^{\mathrm{k}}$ آن‌گاه:
    • اگر $\mathrm{p>-1}$، آن‌گاه $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left(\mathrm{n}^{{{\mathrm{log}}_{\mathrm{b}} \mathrm{a}\ }}{\mathrm{log} \mathrm{p}\ }\mathrm{+1n}\right)$
    • اگر $\mathrm{p=-1}$، آن‌گاه $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{{{\mathrm{log}}_{\mathrm{b}} \mathrm{a}\ }}{\mathrm{log} {\mathrm{log} \mathrm{n}\ }\ }\right)$
    • اگر $\mathrm{p\lt-1}$، آن‌گاه $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{{{\mathrm{log}}_{\mathrm{b}} \mathrm{a}\ }}\right)$
  3. اگر $\mathrm{a}\mathrm{\lt}{\mathrm{b}}^{\mathrm{k}}$ آن‌گاه:
    • اگر $\mathrm{p}\mathrm{\ge }\mathrm{0}$، آن‌گاه $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{\mathrm{k}}{{\mathrm{log}}^{\mathrm{p}} \mathrm{n}\ }\right)$
    • اگر $\mathrm{p\lt0}$، آن‌گاه $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{\mathrm{k}}\right)$

قضیه اصلی برای توابع کاهشی

رابطه‌ای از نوع زیر را در نظر بگیرید:

$\mathrm{T}\left(\mathrm{n}\right)\mathrm{=aT}\left({\mathrm{n-b}}\right)\mathrm{+f}\left(\mathrm{n}\right)$

که در آن:

اگر رابطه بازگشتی به شکل فوق باشد، در قضیه اصلی سه حالت برای تعیین نمادهای مجانبی وجود دارد:

مثال های قضیه اصلی (Master theorem)

در ادامه برای درک بهتر این قضیه، تعدادی مثال را بررسی می‌کنیم:

مثال 1 تقسیمی

یک رابطه بازگشتی داده شده به صورت $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=8T}\left(\frac{\mathrm{n}}{\mathrm{2}}\right)\mathrm{+}{\mathrm{n}}^{\mathrm{2}}$ را در نظر بگیرید:

در این مسئله، $\mathrm{a=8}$، $\mathrm{b=2}$ و $\mathrm{f}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{\mathrm{k}}{{\mathrm{log}}_{\mathrm{n}} \mathrm{p}\ }\right)\mathrm{=}{\mathrm{n}}^{\mathrm{2}}$، به ما $\mathrm{k=2}$ و $\mathrm{p=0}$ می‌دهد.

$\mathrm{a=8>}{\mathrm{b}}^{\mathrm{k}}\mathrm{=}{\mathrm{2}}^{\mathrm{2}}\mathrm{=4}$

بنابراین، مورد 1 باید برای این معادله اعمال شود.

برای محاسبه، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{{{\mathrm{log}}_{\mathrm{b}} \mathrm{a}\ }}\right)\mathrm{=n}{{\mathrm{log}}_{\mathrm{2}} \mathrm{8}\ }\mathrm{=}{\mathrm{n}}^{\left(\frac{{\mathrm{log} \mathrm{8}\ }}{{\mathrm{log} \mathrm{2}\ }}\right)}\mathrm{=}{\mathrm{n}}^{\mathrm{3}}$

بنابراین، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{\mathrm{3}}\right)$ کران این معادله است.

مثال 2 تقسیمی

یک رابطه بازگشتی داده شده به صورت $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=4T}\left(\frac{\mathrm{n}}{\mathrm{2}}\right)\mathrm{+}{\mathrm{n}}^{\mathrm{2}}$ را در نظر بگیرید:

در این مسئله، $\mathrm{a=4}$، $\mathrm{b=2}$ و $\mathrm{f}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{\mathrm{k}}{{\mathrm{log}}_{\mathrm{n}} \mathrm{p}\ }\right)\mathrm{=}{\mathrm{n}}^{\mathrm{2}}$، به ما $\mathrm{k=2}$ و $\mathrm{p=0}$ می‌دهد.

$\mathrm{a=4=}{\mathrm{b}}^{\mathrm{k}}\mathrm{=}{\mathrm{2}}^{\mathrm{2}}\mathrm{=4,p>-1}$

بنابراین، مورد 2 باید برای این معادله اعمال شود.

برای محاسبه، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{{{\mathrm{log}}_{\mathrm{b}} \mathrm{a}\ }}{{\mathrm{log}}^{\mathrm{p+1}} \mathrm{n}\ }\right)\mathrm{=}{\mathrm{n}}^{{{\mathrm{log}}_{\mathrm{2}} \mathrm{4}\ }}{{\mathrm{log}}^{\mathrm{0+1}} \mathrm{n}\ }\mathrm{=}{\mathrm{n}}^{\mathrm{2}}{\mathrm{log} \mathrm{n}\ }$

بنابراین، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{\mathrm{2}}{\mathrm{log} \mathrm{n}\ }\right)$ کران معادله است.

مثال 3 تقسیمی

یک رابطه بازگشتی داده شده به صورت $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=2T}\left(\frac{\mathrm{n}}{\mathrm{2}}\right)\mathrm{+}\frac{\mathrm{n}}{{\mathrm{log} \mathrm{n}\ }}$ را در نظر بگیرید.

در این مسئله، $\mathrm{a=2}$، $\mathrm{b=2}$ و $\mathrm{f}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{\mathrm{k}}{{\mathrm{log}}_{\mathrm{n}} \mathrm{p}\ }\right)\mathrm{=}\frac{\mathrm{n}}{{\mathrm{log} \mathrm{n}\ }}$، به ما $\mathrm{k=1}$ و $\mathrm{p=-1}$ می‌دهد.

$\mathrm{a=2=}{\mathrm{b}}^{\mathrm{k}}\mathrm{=}{\mathrm{2}}^{\mathrm{1}}\mathrm{=2,p=-1}$

بنابراین، مورد 2 باید برای این معادله اعمال شود.

برای محاسبه، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left({\mathrm{n}}^{{{\mathrm{log}}_{\mathrm{b}} \mathrm{a}\ }}{\mathrm{log} {\mathrm{log} \mathrm{n}\ }\ }\right)\mathrm{=n}{{\mathrm{log}}_{\mathrm{4}} \mathrm{4}\ }\mathrm{=n}{\mathrm{log} \left({\mathrm{log} \mathrm{n}\ }\right)\ }$

بنابراین، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}\mathrm{\Theta }\left(\mathrm{n}{\mathrm{log} \left({\mathrm{log} \mathrm{n}\ }\right)\ }\right)$ کران این معادله است.

مثال 1 کاهشی

یک رابطه بازگشتی را به صورت $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=T}\left(\mathrm{n-1}\right)\mathrm{+}{\mathrm{n}}^{\mathrm{2}}$ در نظر بگیرید.

در این مسئله، $\mathrm{a=1}$، $\mathrm{b=1}$ و $\mathrm{f}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{k}}\right)\mathrm{=}{\mathrm{n}}^{\mathrm{2}}$، به ما $\mathrm{k=2}$ می‌دهد.

از آن‌جایی که $\mathrm{a=1}$ است، مورد 1 باید برای این معادله اعمال شود.

برای محاسبه، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{k+1}}\right)\mathrm{=}{\mathrm{n}}^{\mathrm{2+1}}\mathrm{=}{\mathrm{n}}^{\mathrm{3}}$

بنابراین، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{3}}\right)$ کران این معادله است.

مثال 2 کاهشی

یک رابطه بازگشتی داده شده به صورت $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=2T}\left(\mathrm{n-1}\right)\mathrm{+n}$ را در نظر بگیرید.

در این مسئله، $\mathrm{a=2}$، $\mathrm{b=1}$ و $\mathrm{f}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{k}}\right)\mathrm{=}\mathrm{n}$، به ما $\mathrm{k=1}$ می‌دهد.

از آن‌جایی که $\mathrm{a>1}$، مورد 2 باید برای این معادله اعمال شود.

برای محاسبه، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{a}}^{\mathrm{n}\mathrm{/ }\mathrm{b}}\mathrm{*}{\mathrm{n}}^{\mathrm{k}}\right)\mathrm{=O}\left({\mathrm{2}}^{\mathrm{n}\mathrm{/ }\mathrm{1}}\mathrm{*}{\mathrm{n}}^{\mathrm{1}}\right)\mathrm{=O}\left(\mathrm{n}{\mathrm{2}}^{\mathrm{n}}\right)$

بنابراین، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=O}\left(\mathrm{n}{\mathrm{2}}^{\mathrm{n}}\right)$ کران این معادله است.

مثال 3 کاهشی

یک رابطه بازگشتی را در نظر بگیرید که به صورت $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=}{\mathrm{n}}^{\mathrm{4}}$ است.

در این مسئله، $\mathrm{a=0}$ و $\mathrm{f}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{k}}\right)\mathrm{=}{\mathrm{n}}^{\mathrm{4}}$، به ما $\mathrm{k=4}$ می‌دهد.

از آن‌جایی که $\mathrm{a\lt1}$، مورد 3 باید برای این معادله اعمال شود.

برای محاسبه، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{k}}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{4}}\right)$

بنابراین، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{4}}\right)$ کران این معادله است.

محدودیت های قضیه مستر

از قضیه اصلی نمی‌توان استفاده کرد اگر:

جمع‌بندی

قضیه مستر یا قضیه اصلی در طراحی الگوریتم یکی از بهترین روش‌ها برای یافتن سریع پیچیدگی زمانی الگوریتم از رابطه بازگشتی آن است. این قضیه را می‌توان برای توابع کاهشی و همچنین توابع تقسیمی اعمال کرد، که در این مقاله به جزئیات هرکدام پرداختیم و مثال‌هایی را برای هر کدام بررسی کردیم.

قضیه مستر یا قضیه اصلی چیست؟

قضیه اصلی، فرمولی برای حل روابط بازگشتی به فرم مقابل است: $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=aT}\left(\frac{\mathrm{n}}{\mathrm{b}}\right)\mathrm{+f}\left(\mathrm{n}\right)$، که در آن، $\mathrm{n}$ = اندازه ورودی، $\mathrm{n}$ = تعداد زیرمسائل در بازگشت، $\frac{\mathrm{n}}{\mathrm{b}}$ = اندازه هر زیر مسئله است. فرض بر این است که همه زیرمسائل هم‌اندازه هستند.

چه مسائلی را نمی توان با قضیه اصلی حل کرد؟

قضیه اصلی را نمی‌توان برای هر رابطه بازگشتی به شکل $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=aT}\left(\frac{\mathrm{n}}{\mathrm{b}}\right)\mathrm{+f}\left(\mathrm{n}\right)$ اعمال کرد. وقتی a کمتر از 1 باشد یا a ثابت نباشد، نمی‌توان قضیه اصلی را اعمال کرد. زمانی که $\mathrm{f}\left(\mathrm{n}\right)$ چندجمله‌ای نباشد و $\mathrm{T}\left(\mathrm{n}\right)$ یکنواخت نباشد، نمی‌توان آن را اعمال کرد.

چه کسی قضیه مستر را اختراع کرد؟

این رویکرد برای اولین بار توسط جان بنتلی، دوروتیا بلوستاین (با نام خانوادگی هاکن) و جیمز بی ساکس در سال 1980 ارائه شد و به عنوان یک "روش متحدکننده" برای حل روابط بازگشتی توصیف شد.

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (3 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام