قضیه مستر یا قضیه اصلی در طراحی الگوریتمآموزش طراحی الگوریتم به زبان سادهدرس طراحی الگوریتم یکی از مهمترین و بنیادیترین دروس رشته کامپیوتر است. هدف از این درس، معرفی روشهای مختلف طراحی الگوریتمها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است.، یکی از روشهای متعددی است که برای محاسبه پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبی
این صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده
الگوریتم ها بهکار میرود. در تجزیه و تحلیل، پیچیدگیهای زمانی برای یافتن بهترین منطق یک الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوان
در این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد محاسبه میشود. قضیه اصلی بر روی رابطه بازگشتیتوضیح تابع بازگشتی، دنباله بازگشتی و رابطه بازگشتی
این صفحه عالی به توضیح تابع بازگشتی و دنباله بازگشتی و رابطه بازگشتی پرداخته و توضیح داده تابع بازگشتی چیست و چگونه کار می کند و کاربرد توابع بازگشتی را گفته
اعمال میشود. در این مقاله به شرح این قضیه میپردازیم و با چند مثال نحوه عملکرد آن را درک خواهیم کرد.
قضیه اصلی (مستر)
قبل از این که عمیقاً به قضیه مستر بپردازیم، اجازه دهید ابتدا بررسی کنیم که روابط بازگشتی چیست: روابط بازگشتی معادلاتی هستند که دنبالهای از عناصر را تعریف میکنند که در آنها یک عبارت تابعی از عبارت قبلی است. در تحلیل الگوریتم، روابط بازگشتی معمولاً زمانی شکل میگیرند که فراخوانی تابع توسط خودش، در یک الگوریتم وجود داشته باشند. قضیه اصلی را فقط میتوان در توابع تقسیمی و کاهشی بازگشتی به کار برد. اگر رابطه کاهشی یا تقسیمی نباشد، قضیه اصلی نباید اعمال شود.
قضیه اصلی برای توابع بازگشتی
رابطهای از نوع زیر را در نظر بگیرید:
[فرمول]
که در آن:
- [فرمول] و [فرمول]
- [فرمول]: اندازه مسئله
- [فرمول]: تعداد زیرمسائل در رابطه بازگشتی
- [فرمول]: اندازه زیرمسائل با این فرض که همه زیر مسائل هماندازه هستند.
- [فرمول]: هزینه کار انجام شده در خارج از بخش بازگشتی را نشان میدهد. پیچیدگی زمانی آن از مرتبه زمانی [فرمول] است که در آن [فرمول] و [فرمول] یک عدد واقعی است.
اگر رابطه بازگشتی به شکل فوق باشد، در قضیه اصلی سه حالت برای تعیین نمادهای مجانبی وجود دارد.
- اگر [فرمول]، آنگاه [فرمول]
- اگر [فرمول] آنگاه:
- اگر [فرمول]، آنگاه [فرمول]
- اگر [فرمول]، آنگاه [فرمول]
- اگر [فرمول]، آنگاه [فرمول]
- اگر [فرمول] آنگاه:
- اگر [فرمول]، آنگاه [فرمول]
- اگر [فرمول]، آنگاه [فرمول]
قضیه اصلی برای توابع کاهشی
رابطهای از نوع زیر را در نظر بگیرید:
[فرمول]
که در آن:
- [فرمول] و [فرمول]، [فرمول] مجانبی مثبت است.
- [فرمول]: اندازه مسئله
- [فرمول]: تعداد زیرمسائل در رابطه بازگشتی
- [فرمول]: اندازه زیرمسائل با این فرض که همه زیر مسائل هماندازه هستند.
- [فرمول]: نشاندهنده هزینه کار انجام شده در خارج از بخش بازگشتی است. پیچیدگی زمانی آن از مرتبه زمانی [فرمول]، که در آن [فرمول] است.
اگر رابطه بازگشتی به شکل فوق باشد، در قضیه اصلی سه حالت برای تعیین نمادهای مجانبی وجود دارد:
- اگر [فرمول]، [فرمول]
- اگر [فرمول]، [فرمول]
- اگر [فرمول]، [فرمول]
مثال های قضیه اصلی (Master theorem)
در ادامه برای درک بهتر این قضیه، تعدادی مثال را بررسی میکنیم:
مثال 1 تقسیمی
یک رابطه بازگشتی داده شده به صورت [فرمول] را در نظر بگیرید:
در این مسئله، [فرمول]، [فرمول] و [فرمول]، به ما [فرمول] و [فرمول] میدهد.
[فرمول]
بنابراین، مورد 1 باید برای این معادله اعمال شود.
برای محاسبه، [فرمول]
بنابراین، [فرمول] کران این معادله است.
مثال 2 تقسیمی
یک رابطه بازگشتی داده شده به صورت [فرمول] را در نظر بگیرید:
در این مسئله، [فرمول]، [فرمول] و [فرمول]، به ما [فرمول] و [فرمول] میدهد.
[فرمول]
بنابراین، مورد 2 باید برای این معادله اعمال شود.
برای محاسبه، [فرمول]
بنابراین، [فرمول] کران معادله است.
مثال 3 تقسیمی
یک رابطه بازگشتی داده شده به صورت [فرمول] را در نظر بگیرید.
در این مسئله، [فرمول]، [فرمول] و [فرمول]، به ما [فرمول] و [فرمول] میدهد.
[فرمول]
بنابراین، مورد 2 باید برای این معادله اعمال شود.
برای محاسبه، [فرمول]
بنابراین، [فرمول] کران این معادله است.
مثال 1 کاهشی
یک رابطه بازگشتی را به صورت [فرمول] در نظر بگیرید.
در این مسئله، [فرمول]، [فرمول] و [فرمول]، به ما [فرمول] میدهد.
از آنجایی که [فرمول] است، مورد 1 باید برای این معادله اعمال شود.
برای محاسبه، [فرمول]
بنابراین، [فرمول] کران این معادله است.
مثال 2 کاهشی
یک رابطه بازگشتی داده شده به صورت [فرمول] را در نظر بگیرید.
در این مسئله، [فرمول]، [فرمول] و [فرمول]، به ما [فرمول] میدهد.
از آنجایی که [فرمول]، مورد 2 باید برای این معادله اعمال شود.
برای محاسبه، [فرمول]
بنابراین، [فرمول] کران این معادله است.
مثال 3 کاهشی
یک رابطه بازگشتی را در نظر بگیرید که به صورت [فرمول] است.
در این مسئله، [فرمول] و [فرمول]، به ما [فرمول] میدهد.
از آنجایی که [فرمول]، مورد 3 باید برای این معادله اعمال شود.
برای محاسبه، [فرمول]
بنابراین، [فرمول] کران این معادله است.
محدودیت های قضیه مستر
از قضیه اصلی نمیتوان استفاده کرد اگر:
- [فرمول] یکنواخت نیست. به عنوان مثال: [فرمول]
- [فرمول] چند جمله ای نیست. به عنوان مثال: [فرمول]
- a ثابت نیست به عنوان مثال: [فرمول]
- وقتی a کمتر از 1 باشد.
جمعبندی
قضیه مستر یا قضیه اصلی در طراحی الگوریتم یکی از بهترین روشها برای یافتن سریع پیچیدگی زمانی الگوریتم از رابطه بازگشتی آن است. این قضیه را میتوان برای توابع کاهشی و همچنین توابع تقسیمی اعمال کرد، که در این مقاله به جزئیات هرکدام پرداختیم و مثالهایی را برای هر کدام بررسی کردیم.
قضیه مستر یا قضیه اصلی چیست؟
قضیه اصلی، فرمولی برای حل روابط بازگشتی به فرم مقابل است: [فرمول]، که در آن، [فرمول] = اندازه ورودی، [فرمول] = تعداد زیرمسائل در بازگشت، [فرمول] = اندازه هر زیر مسئله است. فرض بر این است که همه زیرمسائل هماندازه هستند.
چه مسائلی را نمی توان با قضیه اصلی حل کرد؟
قضیه اصلی را نمیتوان برای هر رابطه بازگشتی به شکل [فرمول] اعمال کرد. وقتی a کمتر از 1 باشد یا a ثابت نباشد، نمیتوان قضیه اصلی را اعمال کرد. زمانی که [فرمول] چندجملهای نباشد و [فرمول] یکنواخت نباشد، نمیتوان آن را اعمال کرد.
چه کسی قضیه مستر را اختراع کرد؟
این رویکرد برای اولین بار توسط جان بنتلی، دوروتیا بلوستاین (با نام خانوادگی هاکن) و جیمز بی ساکس در سال 1980 ارائه شد و به عنوان یک "روش متحدکننده" برای حل روابط بازگشتی توصیف شد.