מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/מבני נתונים לקבוצות זרות/תרגילים/עוד חסמים/שאלה

ראינו שני מימושים למבנה נתונים המתאר קבוצות זרות ע"י מערך של רשימות מקושרות: מימוש רשימות נאיבי מאחד שתי קבוצות בלי קשר לגדלן, ומימוש רשומות עם איחוד עפ"י גודל מאחד את הקבוצה הקטנה לתוך הקבוצה הגדולה.

1. עבור המימוש הראשון, אנא מצא סדרת $\displaystyle m$ פעולות, שמתוכן $\displaystyle n$ הן פעולות Make-Set, שסיבוכיותה הכוללת היא $\displaystyle \Theta (m+n^{2})$.
2. עבור המימוש השני, אנא מצא סדרת $\displaystyle m$ פעולות, שמתוכן $\displaystyle n$ הן פעולות Make-Set, שסיבוכיותה הכוללת היא $\displaystyle \Theta (m+n\cdot \log(n))$.

שימו לב: בסעיף השני הזנח שגיאות עיגול, או, לחלופין, הנח ש$\displaystyle n$ הוא חזקה שלמה של 2.