مجموعه‌های مجزا / Union-Find
Disjoint SetDisjoint Set یا Union-Find مجموعه‌ای از گروه‌های جدا از هم را نگه می‌دارد و دو عملیات اصلی دارد: find برای پیدا کردن نماینده گروه و union برای ادغام دو گروه.
اول این مفهوم را در ذهن نگه دار
Disjoint Set یا Union-Find مجموعه‌ای از گروه‌های جدا از هم را نگه می‌دارد و دو عملیات اصلی دارد: find برای پیدا کردن نماینده گروه و union برای ادغام دو گروه.
چطور کار می‌کند؟ ساده و مرحله‌ای
هر مجموعه یک root نماینده دارد.
Path Compression و Union by Rank/Size باعث می‌شوند عملیات تکراری در عمل تقریباً ثابت باشند.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
Invariant اصلی ساختار را مشخص کن.
مسیر read/update را در ساختار دنبال کن.
بعد از mutation قبل از return invariant را دوباره برقرار کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مجموعه‌های مجزا / Union-Find هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
amortized near O(1)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- Kruskal
- پرسش اتصال بین Nodeها
- تشخیص cycle در گراف بدون جهت
کجا معمولاً اشتباه می‌کنیم؟
- پیچیدگی را بدون فهم representation حفظ نکن.
- بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
دو optimization اصلی یعنی Path Compression و Union by Rank/Size را نام ببر و بگو پیچیدگی amortized از نوع inverse-Ackermann است که در اندازه‌های واقعی تقریباً ثابت محسوب می‌شود.
مجموعه‌های مجزا / Union-Find چه مسئله‌ای را حل می‌کند؟
Disjoint Set یا Union-Find مجموعه‌ای از گروه‌های جدا از هم را نگه می‌دارد و دو عملیات اصلی دارد: find برای پیدا کردن نماینده گروه و union برای ادغام دو گروه.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا amortized near O(1) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
پیچیدگی را بدون فهم representation حفظ نکن.