(۰۲ دى ۱۳۸۹ ۰۳:۰۷ ب.ظ)bahar نوشته شده توسط:  حداقل تعداد مقایسه برای مرتب کردنn عدد چند میباشد ؟ تو جزوه پارسه حداقل مقایسه برای مرتب سازی بین n تا n به توان ۲ است یعنی n<nlogn<n^2

اگه درباره بازه اعداد اطلاعی نداشته باشیم از مرتبه nlogn هست اما اگه اطلاعاتی داشته باشیم از جمله بازه اعداد( مرتب سازی شمارشی )‌، آنگاه تعداد جستجو از مرتبه n هست.

سلام البته سوالی که امروز تو پارسه اومده گفته n عدد در بازه ۱//n بعد گفته کدوم بهتره randix-count-select-insertion
خوب حالا اگه n خیلی بزرگ باشه فکر کنم randix sort بهتر باشه اما اگه بازه n کم باشه مسلما counting بهتره

اگر بخوایم با روش مقایسه کلیدها داده‌ها را مرتب کنیم بر طبق درخت تصمیم حداقل نیاز به nlogn زمان هست.
اگر max اعداد رو بدانیم میتونیم از الگوریتم شمارشی یا Counting استفاده کنیم، در الگوریتم شمارشی کلیدها رو با هم مقایسه نمی کنیم و از مرتبه n هست.
n^2 هم حداکثر مقایسه بین کلیدها هست که مثلا تو الگوریتم انتخابی اینجوریه.

دوستان خب جلسه اول درس طراحی الگوریتم رو داشتم که استاد این سوال رو تمرین قرار داد
- نشان دهید مرتب سازی ادغامی برای ان صفر بزرگتر مساوی ۳۰ (N>30) بهتر از درجی است !؟
میتونید کمک کنید !؟ چون راستش نمیدونم باید چیکار کنم ! باید مثال بزنم یا توضیح بدم !!

(۰۶ مهر ۱۳۹۱ ۰۳:۲۹ ب.ظ)S2AR نوشته شده توسط:  نشان دهید مرتب سازی ادغامی برای ان صفر بزرگتر مساوی ۳۰ (N>30) بهتر از درجی است !؟

سوال مشکل داره. شما درصورتی میتونی چنین چیزی رو ثابت کنی که تعداد دقیق گامهای اجرایی دو الگوریتم مرتب‌سازی ادغامی و درجی رو بدونی. از روی مرتبه زمانی دو الگوریتم نمیشه چنین چیزی رو ثابت کرد.