باید بدترین حالت الگوریتم های مرتب سازی را با این حد پایین ( 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!
چررااااا؟