کمترین مرتبه زمانی الگوریتم پیدا کردن مرتبه iامین کوچکترین عنصر از میان n عنصر کدام است؟
(سراسری IT- سال۸۵)
جواب: [attachment=8905]
در پاسخ تشریحی پارسه گفته که از الگوریتم Selection استفاده می کنیم.
[attachment=8903]
سوال:
مگه نه اینکه مرتب سازی انتخابی (Selection) در بهترین، بدترین و متوسط از [attachment=8906] هست؟
نه
در بهترین و متوسط O(N)
در بدترین O(n^2)
(۲۶ دى ۱۳۹۱ ۰۱:۵۴ ق.ظ)adel28 نوشته شده توسط: در پاسخ تشریحی پارسه گفته که از الگوریتم Selection استفاده می کنیم.منظور الگوریتم Selection هست نه مرتب‌سازی انتخابی (selection sort). این دوتا کاملا به هم متفاوت هستن
[/quote]
منظور الگوریتم Selection هست نه مرتب‌سازی انتخابی (selection sort). این دوتا کاملا به هم متفاوت هستن
[/quote]
فکر کنم اشتباه من هم همین هست.
میشه در مورد الگوریتم Selection یکم توضیح بدید.
مربوط به کدوم بحث هست؟
فصل ۹ ویراست سوم CLRS
متوسط O_N
بدترین : O_N^2
حالت متوسط الگوریتم مرتب سازی انتخابی میشه n
--
نکته : مرتب سازی سریع در حالت متوسط میشد :nLogN
--
نکته: در حالت متوسط مرتب سازی انتخابی از مرتب سازی سریع بهتر هست.
فایل پیوست رو دانلود کن
(۲۷ دى ۱۳۹۱ ۰۲:۱۷ ق.ظ)csharpisatechnology نوشته شده توسط: حالت متوسط الگوریتم مرتب سازی انتخابی میشه nمرتبه مرتب‌سازی انتخابی در هر سه حالت بهترین، متوسط و بدترین میشه بیگ اوی n^2
نکته: در حالت متوسط مرتب سازی انتخابی از مرتب سازی سریع بهتر هست.
در نتیجه هر دو جمله بالا غلط هستن
سلام. توی کتاب ساختمان داده پوران یه اثباتی نوشته شده که من متوجهش نشدم. فکر کنم نوشته بود میشه با پیچیدگی خطی، i امین کوچکترین عنصر در آرایه رو پیدا کنیم. تا اونجایی که یادمه آرایه رو مرتب نمیکرد. از اثباتش چیزی نفهمیدم برای همین بیخیالش شدم.
بچه ها بالاخره چی شد؟الگوریتم selection در بدترین و بهترین حالت توی کتاب پوران نوشته o(n) هست ...متوسطش هم n هست یا n به توان۲ ؟؟
توی selection داریم :
بهترین و متوسط میشه o_n
بدترین میشه n^2
-----
توی quick sort داریم:
متوسط : NlogN
بدترین : n^2
----
نکته ی دیگه : مرتب سازی انتخابی در حالت متوسط از مرتب سازی سریع بهتره.
بذارید به طور واضح یه جمع بندی بکنم.
از الگوریتم selection به طور کلی برای یافتن kامین بزرگترین (یا کوچکترین) عنصر یک آرایه استفاده میشه. این الگوریتم رو با مرتب‌سازی انتخابی (Selection Sort) اشتباه نگیرید. برای مسئله selection الگوریتمی وجود داره که در بهترین، بدترین و حالت متوسط دارای مرتبه بیگ اوی n هستش. این یعنی اون چیزی که تو پوران نوشته درسته. توضیح این الگوریتم هم تو فصل ۹ CLRS اومده.
دوستان حق با mfXpert هست.
الگوریتم انتخابی (Selection) با مرتب سازی انتخابی (Selection) متفاوت هست.
اشتباه من هم همین بود که این دو رو یکی در نظر می گرفتم.