آموزش طراحی و تحلیل الگوریتم قسمت چهارم

--- 1395/1/18 2183

آموزش طراحی و تحلیل الگوریتم قسمت چهارم

به نام خدا

سلام عرض می کنم خدمت همه ی شما دوستان عزیز و ارجمند

ضیادید هستم و با قسمت چهارم آموزش طراحی و تحلیل الگوریتم ها در خدمت شما خواهم بود .

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

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

تذکر مهم: از ساختار این الگوریتم هم مشخصه که فقط زمانی میتونیم از این الگوریتم استفاده کنیم که آرایه به صورت غیر نزولی (صعودی ) مرتب شده باشه .

مثلا فرض کنیم عدد 19 رو بخوایم توی آرایه ی زیر پیدا کنیم :

10  11  14  18  19  29  40  41  48  50  51

 

در اولین گام ، آرایه به دو زیر آرایه تقسیم میشه . عنصر میانی عدد 29 هست که با 19 برابر نیست . چون 29>19  پس باید به زیر آرایه ی سمت چپ بریم یعنی این آرایه

 

10  11  14  18  19

حالا مرحله ی گذشته برای آرایه ی جدید ما اجرا خواهد شد و درنتیجه ی ادامه ی همین روند ، عدد مورد نظر پیدا میشه .

خب حالا بریم سراغ شبه کد این الگوریتم

الگوریتم جستجوی دو دویی

اما پیچیدگی زمانی این الگوریتم به چه صورت هست ؟

ببینید دوستان ، اگه ما پیچیدگی این الگوریتم رو با T(n) نشون بدیم ، به این معناست که داریم پیچیدگی زمانی رو برای n متغیر ( آرایه ای با طول n ) بررسی می کنیم . اگه مرحله ی اول انجام بشه ، یعنی یک مقایسه بین عدد x و عنصر میانی آرایه صورت گرفته و نصف آرایه دور ریخته میشه و همون مکانیزم برای n/2 عضو باقیمانده ی  آرایه تکرار خواهد شد . در واقع بین T(n) و T(n/2) فقط 1 واحد زمانی فاصله هست . پس ما میتونیم ادعا کنیم که رابطه ی زیر رو داریم :

 

T(n) =T(n/2)+1

 

با استفاده از قضیه ی اساسی پیچیدگی الگوریتم (تئوری Master) واضح هست که پیچیدگی این الگوریتم از مرتبه ی log n خواهد بود .

اما الگوریتم بعدی مرتب سازی ادغامی هست . دراینجا هدف ما مرتب سازی یک آرایه ی به هم ریخته به روش ادغام هست . (merge sort)

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

 

ما نیاز به دو الگوریتم داریم .. یکی برای ادغام و دیگری برای مرتب سازی ادغامی که هردو رو به صورت شبه کد بیان می کنیم .

الگوریتم ادغام

الگوریتم مرتب سازس ادغامی

تحلیل ادغام

اگر بخوایم بدترین حالت الگوریتم ادغام رو تحلیل کنیم ، باید بگیم که در زمان خروج از حلقه ، اندیس i به h میرسه و j به m-1 خواهد رسید . لذا برای دو متغیر m و h داریم :

T(h,m)=h+m-1

اما برای مرتب سازی ادغامی باید بگیم که تعداد کل مقایسه ها برابر هست با مجموع تعداد مقایسه ها در فراخوانی بازگشتی با U و تعداد مقایسه ها در فراخوانی بازگشتی با V به علاوه ی تعداد مقایسه های موجود در فراخوانی تابع merge . پس داریم :

W(n)= W(h)+W(m)+h+m-1

با جایگذاری مناسب کل داده ها ی n داریم :

W(n)=W(n/2)+W(n/2)+n+1

 

که با حل معادله ی بازگشتی فوق به n log n خواهید رسید .

روش بعدی هم الگوریتم مرتب سازی سریع هست quick sort

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

اول شبه کد افراز رو میگیم که در الگوریتم مرتب سازی سریع استفاده شده و سپس شبه کد خود الگوریتم رو بیان می کنیم .

الگوریتم افراز

الگوریتم مرتب سازی سریع

تحلیل:

پیچیدگی زمانی الگوریتم افراز T(n)=n-1 هست چون تمام عناصر به جز اولی مقایسه میشن .

اما برای مرتب سازی سریع بدترین حالت زمانی هست که آرایه به صورت غیر نزولی مرتب شده باشه از اول . ( به عنوان تمرین خودتون فکر کنید که چرا !!)

در این صورت خواهیم داشت :

 

T(n)=T(0) + T(n-1) + n-1

در فرمول بالا ، زمان اجرای مرتب سازی زیر آرایه ی چپ ، زیر آرایه ی راست و زمان لازم برای افراز با هم جمع شدند.

 

با حل معادله ی بازگشتی فوق به رابطه ی زیر میرسید

T(n) = (n*(n-1))/2

که مشخصا معلوم میکنه الگوریتم از مرتبه ی  n به توان 2 هست

لازم به ذکر هست که پیچیدگی این الگوریتم در حالت میانگین از مرتبه ی  nlog n هست .

اما برنامه ریزی پویا چیه ؟؟

این روش از لحاظ تقسیم کل مسئله به مسائل کوچک تر، مشابه روش تقسیم و حل هست ولی ما اول تقسیم می کنیم و نتایج رو ذخیره می کنیم و در ادامه هر زمان که به یکی از اونها احساس نیاز شد ، به جای محاسبه ی دوباره ، اون نتایج رو به اصطلاح بازیابی می کنیم .

خب دوستان عزیز ، برای این جلسه کافیه ..

ان شاءالله در جلسه ی بعد بحث برنامه ریزی پویا رو ادامه میدیم و با برخی الگوریتم ها و مباحث مرتبط با اون آشنا میشیم .

تا دیدار بعدی خدانگهدار همه ی شما

قسمت بعدی قسمت قبلی