Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
خب حالا بریم سراغ شبه کد این الگوریتم
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اما پیچیدگی زمانی این الگوریتم به چه صورت هست ؟
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
ببینید دوستان ، اگه ما پیچیدگی این الگوریتم رو با T(n) نشون بدیم ، به این معناست که داریم پیچیدگی زمانی رو برای n متغیر ( آرایه ای با طول n ) بررسی می کنیم . اگه مرحله ی اول انجام بشه ، یعنی یک مقایسه بین عدد x و عنصر میانی آرایه صورت گرفته و نصف آرایه دور ریخته میشه و همون مکانیزم برای n/2 عضو باقیمانده ی آرایه تکرار خواهد شد . در واقع بین T(n) و T(n/2) فقط 1 واحد زمانی فاصله هست . پس ما میتونیم ادعا کنیم که رابطه ی زیر رو داریم :
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
T(n) =T(n/2)+1
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
با استفاده از قضیه ی اساسی پیچیدگی الگوریتم (تئوری Master) واضح هست که پیچیدگی این الگوریتم از مرتبه ی log n خواهد بود .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اما الگوریتم بعدی مرتب سازی ادغامی هست . دراینجا هدف ما مرتب سازی یک آرایه ی به هم ریخته به روش ادغام هست . (merge sort)
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
یه اصطلاحی هست به نام" ادغام دوطرفه" و به معنی ترکیب دو آرایه ی مرتب شده در یک آرایه هست . وقتی شما به طور متوالی از فرایند ادغام استفاده کنید ، میتونید تمام اعضای یک آرایه رو مرتب کنید . مثلا اگه یک آرایه ی 8 عضوی داشته باشید ، با تقسیم اون به دو زیر آرایه ی 4 عضوی آنها رو مرتب و سپس ادغام کنید . یعنی با استفاده از این الگوریتم ، کل آرایه ابتدا تقسیم میشه و راه حل ما روی اونها اعمال میشه و سپس با ادغام زیر آرایه ها ، کل آرایه به دست میاد و شما میتونید متوجه بشید که در این الگوریتم هم از روش تقسیم و حل داره استفاده میشه .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
ما نیاز به دو الگوریتم داریم .. یکی برای ادغام و دیگری برای مرتب سازی ادغامی که هردو رو به صورت شبه کد بیان می کنیم .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
تحلیل ادغام
اگر بخوایم بدترین حالت الگوریتم ادغام رو تحلیل کنیم ، باید بگیم که در زمان خروج از حلقه ، اندیس i به h میرسه و j به m-1 خواهد رسید . لذا برای دو متغیر m و h داریم :
اگر بخوایم بدترین حالت الگوریتم ادغام رو تحلیل کنیم ، باید بگیم که در زمان خروج از حلقه ، اندیس i به h میرسه و j به m-1 خواهد رسید . لذا برای دو متغیر m و h داریم :
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
T(h,m)=h+m-1
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اما برای مرتب سازی ادغامی باید بگیم که تعداد کل مقایسه ها برابر هست با مجموع تعداد مقایسه ها در فراخوانی بازگشتی با U و تعداد مقایسه ها در فراخوانی بازگشتی با V به علاوه ی تعداد مقایسه های موجود در فراخوانی تابع merge . پس داریم :
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
W(n)= W(h)+W(m)+h+m-1
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
با جایگذاری مناسب کل داده ها ی n داریم :
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
W(n)=W(n/2)+W(n/2)+n+1
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
که با حل معادله ی بازگشتی فوق به n log n خواهید رسید .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
روش بعدی هم الگوریتم مرتب سازی سریع هست quick sort
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
این روش نسبتا مشابه روش قبلی هست . توی این روش ما یک عنصر رو به عنوان عنصر محوری انتخاب می کنیم و عناصر کوچکتر از محور رو در یک زیر آرایه و عناصر بزرگتر رو به سمت زیر آرایه ی دیگه ای می بریم . عنصر محوری دلخواه هست ولی معمولا برای سهولت ، از عنصر اول به عنوان محور استفاد می کنن . زیر آرایه ها هم عنصر محوری میگیرن و همون روند تکرار میشه و به همین ترتیب ادامه پیدا میکنه تا کل آرایه با مرتب شدن زیر آرایه ها ، مرتب بشه . واضح هست که اینم نوعی روش تقسیم و حل هست .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اول شبه کد افراز رو میگیم که در الگوریتم مرتب سازی سریع استفاده شده و سپس شبه کد خود الگوریتم رو بیان می کنیم .