فرض کنید مثلا شکل پیچیدگی زمانی یک الگوریتم به فرم بالا باشه ☝️☝️☝️☝️☝️

طبق قضیه ی اصلی واضح هست که مرتبه ی زمانی چنین الگوریتمی θ(n^2 هست .

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

اما اجازه بدید بریم سراغ روش تقسیم و حل :


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

از جمله مهمترین الگوریتم هایی که در این روش قرار میگیرن عبارت هستن از :
1-جست و جوی دودویی
2-مرتب سازی ادغامی
3-مرتب سازی سریع
4-الگوریتم استراسن

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

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

1- زمانی که نمونه ای با اندازه ی n به دو یا چند نمونه تقسیم بشه که اندازه ی اونها هم تقریبا n باشه .
در این حالت معمولا پیچیدگی زمانی الگوریتم به صورت نمایی خواهد بود که اصلا جالب نیست !!

2- زمانی که نمونه ای با اندازه ی n تقریبا به n نمونه ی با اندازه ی n/k تقسیم بشه که k یک عدد ثابت هست .
در این جا هم پیچیدگی زمانی الگوریتم به صورت n^log n خواهد بود .

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

📝 پایان قسمت سوم آموزش الگوریتم 📝


🌴🌱🌿☘🍀🍃🌷🌼🌸💐🌳🌲🎄🌵

دوستان عزیز ..
همونطور که مشخص بود ، منبع آموزش بالا هم کانال زیر بود : 👇👇👇👇👇

سوال مسابقه ی شماره 5 رو تقدیم میکنیم که مربوط به تحلیل الگوریتم و ساختمان داده هست .. لطفا پاسخ صحیح رو به @SaeedZiadid ارسال کنید

ممنون که همراه ما بودید .. تا فردا خدانگهدار شما🌹🌹

🎄🌲🌳🌿🌱🌴☘🍀🌺🌹🌷🌸🌼💐

پایان قسمت نهم عیدانه ی علوم کامپیوتری

سلام عرض می کنم خدمت همه ی شما عزیزان
خسته نباشید
امیدواریم حالتون خوب باشه
در خدمت شما هستیم با قسمت دهم عیدانه ی علوم کامپیوتری ..
با ما همراه باشید 🌹🌹

سوال مسابقه ی شماره 5 رو تقدیم میکنیم که مربوط به تحلیل الگوریتم و ساختمان داده هست .. لطفا پاسخ صحیح رو به @SaeedZiadid ارسال کنید