سلام
یک سوالی برام پیش اومد.
مگه بر اساس درخت تصمیم به این نتیجه نرسیدیم که حد پایین برای مرتب سازی ها در الگوریتم های مبتنی بر مقایسه nlogn هست؟
ولی ما در مرتب سازی درجی که خب مبتنی بر مقایسه هست ، حد پایین n داریم ، بعد این دو تا با هم تناقض نداره؟
باید بدترین حالت الگوریتم های مرتب سازی را با این حد پایین ( nlogn ) مقایسه کنید.
(۰۳ آذر ۱۳۹۲ ۱۱:۴۶ ق.ظ)mhm-pc نوشته شده توسط: باید بدترین حالت الگوریتم های مرتب سازی را با این حد پایین ( nlogn ) مقایسه کنید.
من متوجه اشتباهم شدم. نه بدترین حالت نیست ، باید حالت متوسط ها رو مقایسه کنیم. clrs اینجوری گفته.
ممنون
نه
حالت میانگین اصلا اینجا معنی نمیده. قضیه یی که توی کتاب گفته اینه: هر الگوریتم مرتب سازی در بدترین حالت به [tex]\Omega (n lg n)[/tex] مقایسه احتیاج دارد.
معنی خودمونیش اینه که مرتبه زمانی هر الگوریتم مرتب سازی در بدترین حالت بزرگتر و مساوی n lg n است.
(۰۳ آذر ۱۳۹۲ ۱۲:۵۴ ب.ظ)mhm-pc نوشته شده توسط: نه
حالت میانگین اصلا اینجا معنی نمیده. قضیه یی که توی کتاب گفته اینه: هر الگوریتم مرتب سازی در بدترین حالت به [tex]\Omega (n lg n)[/tex] مقایسه احتیاج دارد.
معنی خودمونیش اینه که مرتبه زمانی هر الگوریتم مرتب سازی در بدترین حالت بزرگتر و مساوی n lg n است.
آهان. فکر کنم فهمیدم. ممنون
سلام دوستان، در تست کنور سراسری سال ۹۱ حداقل مقایسه ها رو در بدترین حالت از
n log n!
چررااااا؟