====== سوال ۵ ======

مساله یکتاسازی بدین شکل تعریف می شود:
  * ورودی: یک دنباله از اعداد
  * خرووجی: افراز اعداد دنباله ورودی به تعدادی دسته، با این شرط که دو عدد با هم برابر هستند اگر و فقط اگر در یک دسته باشند. (اعداد هر دسته با اندیس‌شان مشخص می‌شوند)
  -   اثبات کنید که هر الگوریتم یکتاسازی مبتنی بر مقایسه روی n عنصر از $\Omega(n\log n)$ است. 
  -    فرض کنید یک لیست مجاورت از یال های یک گراف در اختیار داریم. الگوریتمی خطی $O(n+m)$ برای حذف یال های تکراری در این لیست ارائه دهید. (نکته: درنظر گرفتن یک حافظه به طول $k$ زمان $O(k)$ لازم دارد)
  -  آیا الگوریتم شما در قسمت ب، مثال نقضی برای اثبات قسمت الف نیست؟ 

  * [[سوال ۶|سوال بعد]]
  * [[سوال ۴|سوال قبل]]