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
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
که مشخصا معلوم میکنه الگوریتم از مرتبه ی n به توان 2 هست
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
لازم به ذکر هست که پیچیدگی این الگوریتم در حالت میانگین از مرتبه ی nlog n هست .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اما برنامه ریزی پویا چیه ؟؟
این روش از لحاظ تقسیم کل مسئله به مسائل کوچک تر، مشابه روش تقسیم و حل هست ولی ما اول تقسیم می کنیم و نتایج رو ذخیره می کنیم و در ادامه هر زمان که به یکی از اونها احساس نیاز شد ، به جای محاسبه ی دوباره ، اون نتایج رو به اصطلاح بازیابی می کنیم .
این روش از لحاظ تقسیم کل مسئله به مسائل کوچک تر، مشابه روش تقسیم و حل هست ولی ما اول تقسیم می کنیم و نتایج رو ذخیره می کنیم و در ادامه هر زمان که به یکی از اونها احساس نیاز شد ، به جای محاسبه ی دوباره ، اون نتایج رو به اصطلاح بازیابی می کنیم .