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

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

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

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

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

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

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

که در آن:

• $\mathrm{b>1}$ و $\mathrm{a}\mathrm{\ge }\mathrm{1}$
• $\mathrm{n}$: اندازه مسئله
• $\mathrm{a}$: تعداد زیرمسائل در رابطه بازگشتی
• $\frac{\mathrm{n}}{\mathrm{b}}$: اندازه زیرمسائل با این فرض که همه زیر مسائل هم‌اندازه هستند.
• $\mathrm{f}\left(\mathrm{n}\right)$: هزینه کار انجام شده در خارج از بخش بازگشتی را نشان می‌دهد. پیچیدگی زمانی آن از مرتبه زمانی ${\Theta }\left({\mathrm{n}}^{\mathrm{k}}{{\mathrm{log}}_{\mathrm{n}} \mathrm{p}\ }\right)$ است که در آن $\mathrm{k}\mathrm{\ge }\mathrm{0}$ و $\mathrm{p}$ یک عدد واقعی است.

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

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)$

که در آن:

• $\mathrm{a}\mathrm{\ge }\mathrm{1}$ و $\mathrm{b>1}$، $\mathrm{f}\left(\mathrm{n}\right)$ مجانبی مثبت است.
• $\mathrm{n}$: اندازه مسئله
• $\mathrm{a}$: تعداد زیرمسائل در رابطه بازگشتی
• $\mathrm{n-b}$: اندازه زیرمسائل با این فرض که همه زیر مسائل هم‌اندازه هستند.
• $\mathrm{f}\left(\mathrm{n}\right)$: نشان‌دهنده هزینه کار انجام شده در خارج از بخش بازگشتی است. پیچیدگی زمانی آن از مرتبه زمانی $\mathrm{\Theta }\left({\mathrm{n}}^{\mathrm{k}}\right)$، که در آن $\mathrm{k}\mathrm{\ge }\mathrm{0}$ است.

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

• اگر $\mathrm{a=1}$، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{k+1}}\right)$
• اگر $\mathrm{a\gt1}$، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{a}}^{\mathrm{n}\mathrm{/ }\mathrm{b}}\mathrm{*}{\mathrm{n}}^{\mathrm{k}}\right)$
• اگر $\mathrm{a\lt1}$، $\mathrm{T}\left(\mathrm{n}\right)\mathrm{=O}\left({\mathrm{n}}^{\mathrm{k}}\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{T}\left(\mathrm{n}\right)\mathrm{=}{\mathrm{sin} \mathrm{n}\ }$
• $\mathrm{f}\left(\mathrm{n}\right)$ چند جمله ای نیست. به عنوان مثال: $\mathrm{f}\left(\mathrm{n}\right)\mathrm{=2n}$
• a ثابت نیست به عنوان مثال: $\mathrm{a=2n}$
• وقتی a کمتر از 1 باشد.

جمع‌بندی

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

مطالب مرتبط

همه مقالات

الگوریتم فلوید چیست، آموزش الگوریتم فلوید

پایتون یا سی شارپ؟ – آینده پایتون بهتر است یا سی شارپ

رمزنگاری با پایتون

انواع پایگاه‌ داده