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 آموزش برنامه نویسی - از مبتدی تا حرفه ای
اول شبه کد افراز رو میگیم که در الگوریتم مرتب سازی سریع استفاده شده و سپس شبه کد خود الگوریتم رو بیان می کنیم .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
تحلیل:
پیچیدگی زمانی الگوریتم افراز T(n)=n-1 هست چون تمام عناصر به جز اولی مقایسه میشن .
پیچیدگی زمانی الگوریتم افراز T(n)=n-1 هست چون تمام عناصر به جز اولی مقایسه میشن .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اما برای مرتب سازی سریع بدترین حالت زمانی هست که آرایه به صورت غیر نزولی مرتب شده باشه از اول . ( به عنوان تمرین خودتون فکر کنید که چرا !!)📝
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
در این صورت خواهیم داشت :
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
T(n)=T(0) + T(n-1) + n-1
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
در فرمول بالا ، زمان اجرای مرتب سازی زیر آرایه ی چپ ، زیر آرایه ی راست و زمان لازم برای افراز با هم جمع شدند.
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
با حل معادله ی بازگشتی فوق به رابطه ی زیر میرسید
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
T(n) = (n*(n-1))/2