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

עוד חסמים

שאלה

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

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.

תשובה

שני הפתרונות מתחילים בצורה זהה. מייצרים מערך של $\displaystyle n$ קבוצות זרות (1-3). מכאן ואילך הפתרונות מתחלקים לפי הסעיף:

סדרת פעולות עבור המימוש הנאיבי

עוברים בלולאה (4-5) על איברי המערך (משמאל לימין), ומצרפים כל קבוצה לקבוצה שלפניה:

1	Sets = Make-Array(n)

2	for i in [1, ..., n]
3		Sets[i] = Make-Set()

4	for i in [1, ..., n - 1]
5		Union(Sets[i + 1], Sets[i])

הסיבוכיות של 4-5 הנה:

$\displaystyle \sum _{i=1}^{n-1}[\Theta (i)]=\Theta (\sum _{i=1}^{n-1}[i])=\Theta (n^{2})$

סדרת פעולות עבור איחוד רשימות על פי גודל

עובדים בשלבים, כשכל שלב מכיל לולאה. בשלב הראשון מאחדים את קבוצה 1 עם קבוצה 2, את קבוצה 3 עם קבוצה 4, וכולי. בשלב השני מאחדים את קבוצה 1 עם קבוצה 3, את קבוצה 5 עם קבוצה 7, וכולי. ממשיכים בשלבים עוד ועוד, עד שכל הקבוצות מאוחדות לקבוצה אחת גדולה:

1	Sets = Make-Array(n)

2	for i in [1, ..., n]
3		Sets[i] = Make-Set()

4	d = 0

5	while n / 2^d > 1
6		j = 1

7		while j < n
8			Union(Sets[j], Sets[j + 2^d])
			
9			j = j + 2 &middot; 2^d
		
10		d = d + 1

הסיבוכיות של 5-10 הנה:

$\displaystyle \sum _{d=1}^{\log(n)}[n/2^{d}\Theta (2^{d})]=n\cdot \sum _{d=1}^{\log(n)}[\Theta (1)]=\Theta (n\cdot \log(n))$