سلام دوستان
در بیشتر سوالات دیده میشه که میگن در آرایه نا مرتب میانه در زمان n بدست میاد اچه طوری؟
من خودم فکر می کنم باید ابتدا آرایه رو مرتب کنیم بعد عنصر وسط یا میانگین دو عنصر وصط رو بدست بیاریم خب این مرتب سازی به چه روشی انجام میشه که مرتبه اش از n اه؟
یعنی از مرتب سازی پیمانه ای و شمارشی و مبنایی برای اینکار استفاده میکنن؟ یا روش دیگری داره ؟
ممنون میشم نظراتتون رو بگین
سلام
تا انجایی که یادم میاد اینه که یک الگوریتمی به نام Selection داریم که این کار را انجام میده عین همون مرتب سازی سریع هستش با این تفاوت که فقط بازگشت روی نیمی از دادهای خودش برای پیدا کردن جواب مسئله داره و کمتر از n هم فکر کنم پیچیدگیش باشه.
لطفا دوستان نظر بدن؟
از الگوریتم selection من اینجوری متوجه شدم که وقتی n تا عنصر رو به دسته های ۵ تایی تقسیم میکنیم n/5 دسته داریم خب توی یک حلقه به تعداد تکرار n/5 همه دسته های ۵ تایی رو مرتب میکنیم مثلا با مرتب سازی درجی (از مرتبه n^2) اما این مرتبه برای ما اهمیت نداره چون زمان اجرای هر دسته میشه ۲۵ که بستگی به مقدار n نداره پس فقط میمونه زمان اجرای حلقه که از مرتبه n هست.
(۲۱ آذر ۱۳۹۰ ۰۲:۱۲ ب.ظ)مهشاد نوشته شده توسط: از الگوریتم selection من اینجوری متوجه شدم که وقتی n تا عنصر رو به دسته های ۵ تایی تقسیم میکنیم n/5 دسته داریم خب توی یک حلقه به تعداد تکرار n/5 همه دسته های ۵ تایی رو مرتب میکنیم مثلا با مرتب سازی درجی (از مرتبه n^2) اما این مرتبه برای ما اهمیت نداره چون زمان اجرای هر دسته میشه ۲۵ که بستگی به مقدار n نداره پس فقط میمونه زمان اجرای حلقه که از مرتبه n هست.این مطلبی که شما نوشتید تقریبا درسته اما یه قسمتی از اون کاملا از نظر مفهومی غلط هستش:
'همه دسته های ۵ تایی رو مرتب میکنیم مثلا با مرتب سازی درجی (از مرتبه n^2) اما این مرتبه برای ما اهمیت نداره چون زمان اجرای هر دسته میشه ۲۵'
فرض کنید مرتبه اجرایی یه الگوریتم به صورت [tex]T(n)=\Theta (n^{2})[/tex] هستش.اگر از شما پرسیده بشه مقدار [tex]T(5)[/tex] چی میشه جواب شما چیه؟
این سوال اصلا جوابی نداره چون کلا سوالی که پرسیده شده بی معنی هستش
ممنون دوست عزیز حق با شماست.
به نظرتون میشه اینجوری گفت که مرتب سازی هر دسته از مرتبه ۱ هستش؟
ممنون میشم اگه بچه‌ها این سوال بدست آوردن میانه با این الگوریتمی که بچه‌ها گفتن و با تحلیل مرتبه‌ی زمانیش واضح توضیح بدن
(۲۱ آذر ۱۳۹۰ ۰۶:۱۴ ب.ظ)مهشاد نوشته شده توسط: ممنون دوست عزیز حق با شماست.نه.چنین نتیجه گیری هم غلط خواهد بود
به نظرتون میشه اینجوری گفت که مرتب سازی هر دسته از مرتبه ۱ هستش؟
(۲۱ آذر ۱۳۹۰ ۰۸:۳۶ ب.ظ)homa نوشته شده توسط: ممنون میشم اگه بچه‌ها این سوال بدست آوردن میانه با این الگوریتمی که بچه‌ها گفتن و با تحلیل مرتبه‌ی زمانیش واضح توضیح بدناین الگوریتم تو کتاب CLRS آورده شده (فقط به صورت تشریحی و بدون شبه کد) و رابطه بازگشتی ای هم که از این الگوریتم به دست میاد حلش سر راست نیست.
مرسی از پاسختون دوست عزیز ولی من دلیلش رو متوجه نمیشم. ممنون میشم یکم بیشتر توضیح بدید.
(۲۴ آذر ۱۳۹۰ ۰۵:۵۵ ب.ظ)مهشاد نوشته شده توسط: مرسی از پاسختون دوست عزیز ولی من دلیلش رو متوجه نمیشم. ممنون میشم یکم بیشتر توضیح بدید.
خب این مطلب جای صحبت زیاد داره و بهترین مرجع همون کتاب clrs هست اما در چند خط من روش کار رو الگوریتم وار مینویسم .
ببنید این روش بر اساس میانه میانه‌ها استوار هست یعنی به این صورت:
۱ - در ابتدا ارایه به دسته های پنج تایی تقسم میشود و تعداد دسته‌ها برابر است با: [tex]\left \lceil \frac{N}{5} \right \rceil[/tex]
۲- هر دسته به وسیله اگوریتم درجی مرتب میشه واز انجایی که تعداد هر دسته ثابت هست لذا مرتب سازی هر دسته از مرتبه [tex]O(1)[/tex] هست و از انجا که تعداد دسته برابر است با
[tex]\left \lceil \frac{N}{5} \right \rceil[/tex] لذا هزینه این مرحله برابر است با :
[tex]\left \lceil \frac{N}{5} \right \rceil *O(1) = \Theta (n)[/tex]
۳ - در این مرحله میانه هر دسته مشخص شده که تعداد این میانه‌ها برابر است با [tex]\left \lceil \frac{N}{5} \right \rceil[/tex] حالا ببه روش بازگشتی میانه این میانه‌ها رو بدست میاره که برابر است با: [tex]T(\frac{N}{5})[/tex]
۴- در این مرحله ارایه را حول میانه میانه‌ها افزار میکنیم (همان الگوریتم پارتیشن در اگرویتم مرتب سازی سریع که هزینه ان هم از مرتبه N است . حالا اگر اندیکس بازگشتی توسط الگوریتم پارتیشن برابر با اندیکس وسطی ارایه باشد که کار تمام است و در غیر اینصورت بصورت بازگشتی این روند رو ادامه میدهیم و فرض میکنیم که در بدترین حالت میانه در نیمه بیشتر میباشد و ثابت میشود که تعداد این عناصر: [tex]\frac{3N}{10} 6[/tex] میباشد (ارجاع به کتاب clrs ).پس در نهایت تداریم:
[tex]T(n) =T(\frac{N}{5}) T(\frac{3N}{10} 6 ) O(N)[/tex]
توجه کنید که [tex]O(N)[/tex] مربوط به هزینه مرتبت سازی و افراز هست که هر دو از مرتبه N بودن با یک ضریب ثابت مثل a .
که درنهایت با حل این رابطه بازگشتی به مقدار میرسید .
[tex]O(N)[/tex]
البته اینجا بهتر از این نمتونستم توضیح بدم
اگر رسانه قاصر در بیان بود شما ببخشید.
یه چیز دیگه میانه ارایه در واقع بدست اوردین [tex]\left \lfloor \frac{N}{2} \right \rfloor[/tex]
مین عنصر کوچتر ارایه است
(۲۱ آذر ۱۳۹۰ ۱۱:۵۰ ب.ظ)mfXpert نوشته شده توسط:(21 آذر ۱۳۹۰ ۰۶:۱۴ ب.ظ)مهشاد نوشته شده توسط: ممنون دوست عزیز حق با شماست.نه.چنین نتیجه گیری هم غلط خواهد بود
به نظرتون میشه اینجوری گفت که مرتب سازی هر دسته از مرتبه ۱ هستش؟
(۲۱ آذر ۱۳۹۰ ۰۸:۳۶ ب.ظ)homa نوشته شده توسط: ممنون میشم اگه بچه‌ها این سوال بدست آوردن میانه با این الگوریتمی که بچه‌ها گفتن و با تحلیل مرتبه‌ی زمانیش واضح توضیح بدناین الگوریتم تو کتاب CLRS آورده شده (فقط به صورت تشریحی و بدون شبه کد) و رابطه بازگشتی ای هم که از این الگوریتم به دست میاد حلش سر راست نیست.
این معادله بازگشتی شاید قیافه غلط اندازی داشته باشه و یه کم وحشتناک و بد ریخت اما در واقع قیافه اش وحشت بر اندز هست و کافیه در بی نهایت حدش رو حساب کنید و در این صورت از مقادیر ثابتی مثل ۶ چشم پوشی میکنیم .
خود کتاب clrs بر اساس روش جایگذاری حل کرده اما راحتتر هم میشه به همون نتیجه رسید.
اگر احیانا با حلش مشکلی داشتین بگین تا مبسوط‌تر توضیح بدم .
ممنونم آقای Hadi_m شما خیلی خوب توضیح دادین.مرسی
برداشت منم این بود که مرتب سازی هر دسته ۵ تایی از مرتبه یک هستش ولی آقای mfxpert فرمودن غلطه.دلیلشم از توضیح ایشون اینجوری فهمیدم که چون مقدار ورودی ثابته مرتبه تعیین کردن مفهومی نداره.
دوستان ببخشید که من خیلی به این الگوریتم گیر دادم ولی یه سواله دیگه برام پیش اومده که وقتی میانه میانه‌ها به صورت بازگشتی بدست میاد یعنی اینکه میانه‌ها به دسته های ۵ تایی تقسیم میشن و بعد مرتب میشن و میانه میانه ها(mm) بدست میاد؟؟ خب اگه اینجوری باشه جواب غلط میشه!
از اینکه گفتین جواب غلط میشه من تنها تونستم این رو برداشت کنم که اینطور تصور کردین که میانه میانه‌ها همان میانه ارایه هست !!!
اگر برداشتتون این باشه باید بگم حق با شماست و مطمئنا جواب غلط میشه چون میانه میانه منطبق بر میانه ارایه نیست . ینکته اینجاست که هدفمون از بدست اوردن میانه میانه اصلا چی هست ؟
من در اخر صحبتهام به این موضع اشاره کردم که میانه ارایه در واقع همان مسئله یافتن i مین عنصر کوچکتر ارایه است ویافتن این عنصر از مرتبه N هست و یافتن عنصر میانه به طبع همان یافتن [tex]\left \lfloor \frac{N}{2} \right \rfloor[/tex] مین عنصر کوچکتر ارایه هست .
ایده اصلی در پیدا کردن i مین عنصر کوچکتر ارایه همان تفکر موجود در الگوریتم افراز هست که ارایه رو حول محور افزار میکرد و وقتی و در پایان عنصر محور در جای خودش تثبیت میشد و این الگوریتم اندیکس عنصر محور را بر میگرداند که اگر این اندیس برابر با i بود که ما موفق به پیدا کردن ان شدیم وگرنه با توجه به i یکی از دو نیمه رو به صورت بازگشتی برای یافتن ان اجرا میکرد.
تا اینجا مسئله کاملا واضح هست اما مشکلی که با ان موجه هستیم این هست که الگوریتم افراز عنصر محور رو به توصرت تصادفی انتخاب میکرد مثلا اولین عنصر ارایه و این احتمال وجود داشت که ارایه به صورت مناسب افراز نشه مثلا همواره بزرگترین عنصر ارایه رو به عنوان عنصر محور انتخاب کنیم و در این شرایط بود که به علت عدم افراز مناسب برای بعضی ورودیها مرتبه ان افزایش پیدا میکرد.
نکته: این ورژن از الگوریتم افراز که به افراز تصادفی هم مشهور هست باز هم همان مرتبه N را دارد اما در بدترنی حالت خیر.
پس باید به دنبال راهی باشیم که به ازای هر ورودی تصادفی , مطمئن شویم ارایه به صورت مناسبی افراز میشود و برای رسیدن به این هدف بود که ابتدا عنصر میانه میانه‌ها را پیدا میکنیم و از این عنصر به عنوان محور استفاده میکنیم .
اگر خاطتون باشهمن گفتم ارایه را حول میانه میانه‌ها افراز میکنیم .و مطمئنا میانه میانه‌ها , میانه خود ارایه نیست و نباید این تشابه اسمی شما رو به اشتباه بیندازد.
نکته: ابن ورژن از الگوریتم افراز دیگه تصادفی عمل نمیکنه و در بدترین حالت هم مرتبه N را برای ما تضمین میکند .
البته از سئوال شما من اینطور تصور کردم و شاید منظور شما رو به درستی متوجه نشده باشم .
امیدوارم جواب سئوالتون رو تا اندازه یی گرفته باشین.
از توضیحات کاملتون خیلی ممنونم.لطف کردین.
راستش در فهم کلی الگوریتم مشکلی نداشتم. سوال من که الان متوجه شدم خیلی بدیهی بوده ,در مورد این بود که الگوریتم وقتی خودش رو فراخوانی میکنه که میانه میانه‌ها رو به صورت بازگشتی پیدا کنه چه جوری عمل میکنه؟
من از کتاب پارسه این الگوریتم رو خوندم و وقتی با مثالی که خود کتاب زده بود مقایسه کردم دیدم mm رو تو این مثال ۵۰ بدست آورده ولی من یه عدد دیگه بدست میووردم.
توضیحات شما رو که خوندم فهمیدم که وقتی ترتیب داده های ورودی فرق کنه مسلما میانه هم متفاوت میشه!
من با همون ترتیبی که داده‌ها رو تو کتاب نوشته بود mm رو پیدا میکردم اما طبیعتا داده‌ها با همین ترتیب وارد نشدن و مرتب شده اونها رو تو کتاب نوشته.
بازم ممنون.