چرا تمامی الگوریتم های مقایسه ای در حالت متوسط از تتای nlogn بهتر نمی شوند؟
اثباتش رو هر جا گشتم پیدا نکردم.
(۱۳ خرداد ۱۳۹۴ ۰۴:۱۵ ب.ظ)ali hjt نوشته شده توسط: چرا تمامی الگوریتم های مقایسه ای در حالت متوسط از تتای nlogn بهتر نمی شوند؟
اثباتش رو هر جا گشتم پیدا نکردم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
یه درخت تصمیم گیری برای مرتب سازی بر اساس مقایسه لازم داریم. این درخت یه درخت دودوییه [tex]binary\: tree[/tex]
هر گره داخلی این درخت یه مقایسه بین دو عنصر رو نشون میده. هر برگ یه نتیجه مرتب شده رو نشون میده.
بخاطر [tex]n![/tex] چینش [tex]n[/tex] عنصر پس درخت ما حداکثر [tex]n![/tex] برگ داره. این درخت حداکثر [tex]2n!-1[/tex] گره داره.
پس عمق این درخت حداقل [tex]\log(n!)[/tex] هست.
رابطه [tex]n!\ge(\frac{n}{2})^{(\frac{n}{2})}[/tex] یه رابطه صحیحه. پس [tex]\log n!\ge\log(\frac{n}{2})^{(\frac{n}{2})}[/tex]
در نتیجه : عمق درخت از مرتبه [tex]O(n\: \log\: n)[/tex] هست. البته در حالت متوسط.