حل تشریحی سوال شماره 63 طراحی الگوریتم

چند گزاره از گزاره های زیر درست است؟

• هر الگوریتم قطعی که n کلید متمایز را فقط با مقایسه کلیدها مرتب سازی می کند، باید در بدترین حالت حداقل $\left[\log \left(n!\right)\right]$ مقایسه کلیدها را انجام دهد.
• اگر m تعداد برگ ها در یک درخت دودویی و d عمق آن باشد آنگاه $d\ge \left[\log m\right]$.
• الگوریتم مرتب سازی شمارشی یک الگوریتم مبتنی بر مقایسه است که در بدترین وضعیت از مرتبه O(n) است.