حل تشریحی سوال شماره 41 دروس مشترک (ساختمان‌های گسسته، ساختمان داده‌ها، طراحی الگوریتم، مهندسی نرم‌افزار، شبکه‌های کامپیوتری)

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

از الگوریتم محاسبه جایگشتهای اعداد $1,2,\dots ,n$ می‌توان یک الگوریتم برای حل مسئله 1 وزیر در صفحه شطرنجی nxn استخراج کرد در نتیجه مرتبه الگوریتم مذکور $\Omega \left(n!\right)$ خواهد بود.

برای مرتب کردن هر ۶ عدد بر مبنای مرتب سازی مقایسه‌ای حداقل ۱۰ مقایسه لازم دارد.

در الگوریتم مرتب سازی ادغامی، در بدترین حالت تعداد مقایسه‌های لازم بین عناصر آرایه برای مرتب کردن هر ۱۰ عنصر (با فرض اینکه مسئله کوچک آرایه یک عنصری می‌باشد). برابر ۲۵ است.