تمرین اول کلاس تحلیل‌های ماورای بدترین حالت

لینک تمرین: http://timroughgarden.org/f14/hw/hw1.pdf

تمرینات جلسه ۱

۱- زیرمجموعه‌ای از حالت‌های الگوریتم B را در نظر بگیرید که هر کدام به ترتیب یک جایگشت خاص از اندیس‌ها مسئله را حل می‌کنند. یعنی به ترتیب آن جایگشت اندیس‌های آرایه را برای پیدا کردن عنصر مورد نظر شما چک می‌کنند. مثلاً اگر همانی باشد جستجوی خطی است. به ازای هر عنصری، یکی از این الگوریتم‌ها آن را در زمان ۱ پیدا می‌کند چون اولین مقایسه‌ای که انجام می‌دهد با آن عنصر است. از آنجا که c ثابت است پس الگوریتم A باید در زمان ثابت به ازای هر عنصری این کار را انجام دهد. یعنی در بدترین حالت هم زمان آن O(1) می‌شود، در حالی که کران پایین پیدا کردن عنصر در مدل مقایسه‌ای log n است. (اثبات این موضوع مثلاً از طریق درخت تصمیم جبری امکان پذیر است). پس به تناقض رسیدیم و الگوریتم A با این مشخصات نیست.

۲- مشابه قسمت قبل عمل می‌کنیم و الگوریتم B را هم به ازای هر جایگشت ورودی در نظر می‌گیریم که اول آن جایگشت را چک می‌کند و اگر نشد مرتب‌سازی را به یکی از روش‌های متداول انجام می‌دهد. پس هم یک الگوریتم مرتب‌سازی است و هم به ازای هر ورودی، یکی از این الگوریتم‌ها هست که آن را در زمان O(n) حل کند. پس اگر الگوریتم بهینه مصداقی (instance optimal) برای آن وجود داشته باشد، باید مرتب‌سازی را در زمان O(n) حل کند. در حالی که مرتب‌سازی در مدل مقایسه‌ای به حداقل n log n مقایسه نیاز دارد. پس به تناقض رسیدیم و چنین الگوریتمی وجود ندارد.