(۲۴ آذر ۱۳۹۰ ۰۵:۵۵ ب.ظ)مهشاد نوشته شده توسط: مرسی از پاسختون دوست عزیز ولی من دلیلش رو متوجه نمیشم. ممنون میشم یکم بیشتر توضیح بدید.
خب این مطلب جای صحبت زیاد داره و بهترین مرجع همون کتاب clrs هست اما در چند خط من روش کار رو الگوریتم وار مینویسم .
ببنید این روش بر اساس میانه میانهها استوار هست یعنی به این صورت:
۱ - در ابتدا ارایه به دسته های پنج تایی تقسم میشود و تعداد دستهها برابر است با:
⌈N5⌉
۲- هر دسته به وسیله اگوریتم درجی مرتب میشه واز انجایی که تعداد هر دسته ثابت هست لذا مرتب سازی هر دسته از مرتبه
O(1) هست و از انجا که تعداد دسته برابر است با
⌈N5⌉ لذا هزینه این مرحله برابر است با :
⌈N5⌉∗O(1)=Θ(n)
۳ - در این مرحله میانه هر دسته مشخص شده که تعداد این میانهها برابر است با
⌈N5⌉ حالا ببه روش بازگشتی میانه این میانهها رو بدست میاره که برابر است با:
T(N5)
۴- در این مرحله ارایه را حول میانه میانهها افزار میکنیم (همان الگوریتم پارتیشن در اگرویتم مرتب سازی سریع که هزینه ان هم از مرتبه N است . حالا اگر اندیکس بازگشتی توسط الگوریتم پارتیشن برابر با اندیکس وسطی ارایه باشد که کار تمام است و در غیر اینصورت بصورت بازگشتی این روند رو ادامه میدهیم و فرض میکنیم که در بدترین حالت میانه در نیمه بیشتر میباشد و ثابت میشود که تعداد این عناصر:
3N106 میباشد (ارجاع به کتاب clrs ).پس در نهایت تداریم:
T(n)=T(N5)T(3N106)O(N)
توجه کنید که
O(N) مربوط به هزینه مرتبت سازی و افراز هست که هر دو از مرتبه N بودن با یک ضریب ثابت مثل a .
که درنهایت با حل این رابطه بازگشتی به مقدار میرسید .
O(N)
البته اینجا بهتر از این نمتونستم توضیح بدم
اگر رسانه قاصر در بیان بود شما ببخشید.
یه چیز دیگه میانه ارایه در واقع بدست اوردین
⌊N2⌋
مین عنصر کوچتر ارایه است
(۲۱ آذر ۱۳۹۰ ۱۱:۵۰ ب.ظ)mfXpert نوشته شده توسط: (21 آذر ۱۳۹۰ ۰۶:۱۴ ب.ظ)مهشاد نوشته شده توسط: ممنون دوست عزیز حق با شماست.
به نظرتون میشه اینجوری گفت که مرتب سازی هر دسته از مرتبه ۱ هستش؟
نه.چنین نتیجه گیری هم غلط خواهد بود
(۲۱ آذر ۱۳۹۰ ۰۸:۳۶ ب.ظ)homa نوشته شده توسط: ممنون میشم اگه بچهها این سوال بدست آوردن میانه با این الگوریتمی که بچهها گفتن و با تحلیل مرتبهی زمانیش واضح توضیح بدن
این الگوریتم تو کتاب CLRS آورده شده (فقط به صورت تشریحی و بدون شبه کد) و رابطه بازگشتی ای هم که از این الگوریتم به دست میاد حلش سر راست نیست.
این معادله بازگشتی شاید قیافه غلط اندازی داشته باشه و یه کم وحشتناک و بد ریخت اما در واقع قیافه اش وحشت بر اندز هست و کافیه در بی نهایت حدش رو حساب کنید و در این صورت از مقادیر ثابتی مثل ۶ چشم پوشی میکنیم .
خود کتاب clrs بر اساس روش جایگذاری حل کرده اما راحتتر هم میشه به همون نتیجه رسید.
اگر احیانا با حلش مشکلی داشتین بگین تا مبسوطتر توضیح بدم .