سوالات المپیاد:دوره ی تابستان:دوره ی ۲۲:الگوریتم ها:سوال ۵
سوال ۵
مساله یکتاسازی بدین شکل تعریف می شود:
اثبات کنید که هر الگوریتم یکتاسازی مبتنی بر مقایسه روی n عنصر از Ω(nlogn) است.
فرض کنید یک لیست مجاورت از یال های یک گراف در اختیار داریم. الگوریتمی خطی O(n+m) برای حذف یال های تکراری در این لیست ارائه دهید. (نکته: درنظر گرفتن یک حافظه به طول k زمان O(k) لازم دارد)
آیا الگوریتم شما در قسمت ب، مثال نقضی برای اثبات قسمت الف نیست؟