چند گزاره از گزارههای زیر درست است؟ ـ هر الگوریتم قطعی که n کلید متمایز را فقط با مقایسه کلیدها مرتبسازی میکند، باید در بدترین حالت حداقل ⌈ log(n!) ⌉ مقایسه کلیدها را انجام دهد. ـ اگر m تعداد برگها در یک درخت دودویی و d عمق آن باشد آنگاه d ≥ ⌈ log m ⌉ . ـ الگوریتم مرتبسازی شمارشی یک الگوریتم مبتنیبر مقایسه است که در بدترین وضعیت از مرتبه O(n) است.

سوال ۶۳ کنکور ارشد مهندسی کامپیوتر ۱۴۰۴

طراحی الگوریتم‌هامتوسطمرتب‌سازی مبتنی بر مقایسه (سریع، ادغامی، هرمی)

اهمیت

۰/۵

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

ـ هر الگوریتم قطعی که n کلید متمایز را فقط با مقایسه کلیدها مرتب‌سازی می‌کند، باید در بدترین حالت حداقل $\lceil \log(n!) \rceil$ مقایسه کلیدها را انجام دهد.

ـ اگر m تعداد برگ‌ها در یک درخت دودویی و d عمق آن باشد آنگاه $d \ge \lceil \log m \rceil$ .

ـ الگوریتم مرتب‌سازی شمارشی یک الگوریتم مبتنی‌بر مقایسه است که در بدترین وضعیت از مرتبه $O(n)$ است.

#comparison-sort#decision-tree#lower-bound#counting-sort#binary-tree-height