מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 4/תשובות

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

1

נניח שמספר האיברים בקלט הוא $\displaystyle n$ .

א'

כל קריאה לInsert-Back של רשימה מקושרת היא $\displaystyle O(1)$ , ולכן סיבוכיות הלולאה היא $\displaystyle \Theta (n)$ .

פתרון זה יעיל הן בזמן הריצה והן בזכרון מבחינת סדרי גדילה, מפני שהן זמן הריצה והן דרישת הזכרון לינאריים במספר האיברים. עם זאת, קבועי זמן הריצה ודרישת הזכרון גבוהים למדי. לדוגמה, בגלל המצביעים בחוליות הרשימה המקושרת, כמות הזכרון שתדרש עבור עבור שמירת כל תו תהיה לפחות פי שלושה מכמות הזכרון המינימלית לשמירת תו.

ב'

נתבונן באיטרציה ה $\displaystyle i$ של הלולאה 3-12. בהכרח תופעל הלולאה הפנימית 9-10, וסיבוכיותה לינארית ב $\displaystyle i$ . זמן הריצה הוא לכן $\displaystyle \sum _{i=1}^{n}[\Theta (i)]=\Theta (n^{2})$ .

הפתרון אינו יעיל מבחינת זמן ריצה, אך הוא חסכוני מאד (בצורה קיצונית, אפילו) בדרישת הזכרון שלו.

ג'

נתבונן באיטרציה ה $\displaystyle i$ של הלולאה 3-12. הלולאה הפנימית 9-10 תופעל אמ"ם $\displaystyle i$ חזקה של 2, וסיבוכיותה לינארית ב $\displaystyle i$ . אם $\displaystyle h$ הוא מספר הפעמים שהופעלה הלולאה הפנימית, אז קל לראות שמתקיים $\displaystyle h=\log(n)\pm O(1)$ .

זמן הריצה הוא לכן $\displaystyle \sum _{i=1}^{h}[\Theta (i)]=\sum _{j=1}^{\log(n)\pm O(1)}[\Theta (2^{j})]=\Theta (2^{\log(n)\pm O(1)})=\Theta (n)$ .

הפתרון יעיל מבחינת זמן הריצה הכולל, וסביר מבחינת דרישת הזכרון שלו (הנמצאת בין אלו של שני הפתרונות הקודמים). נשים לב שלמרות שזמן הריצה הכולל הוא לינארי (כבפתרון 1), זמן הריצה של איטרציה בודדת אינו $\displaystyle O(1)$ (בנגוד לפתרון 1). המשתמש עלול להמתין זמן רב לפני מספר הקשות אם פתרון זה בשימוש.

2

א'

# Takes a list (l) and a value (v).
# Modifies all the links in the list so that their value is v.
List-Set-All(l, v)
1	lnk = l.front

2	while lnk != Nil
3		lnk.value = v
4		lnk = lnk.next

ב'

# Takes two lists (l1, l2).
# Modifies them so that all the links are in the first list (l1),
#	and the second list (l2) is empty.
List-Union(l1, l2)
1	if l1.back != Nil
2		l1.back.next = l2.front
3	if l2.front != Nil
4		l2.front.prev = l1.back

5	l1.back = l2.back
6	l1.size = l1.size + l2.size

7	l2.front = l2.back = Nil
8	l2.size = 0

3

פסוודו-קוד והסבר

להלן הפסוודו-קוד לפתרון:

#Takes a singly-linked list (l) and reverses it.
Reverse(l)
1	new-front = Nil
	
2	while l.front != Nil
3		nxt = l.front.next
4		l.front.next = new-front
5		new-front = l.front
6		l.front = nxt
		
7	l.front = new-front

נתבונן ברשימה המקושרת בתרשים הבא.

שורה 1 מייצרת מצביע new-front המצביע לNil ‏(A)‏. מצביע זה יצביע לרשימות החוליות שכבר הפכו את סדרן.
כעת נעבור בלולאה 2-6, כל עוד נותרו איברים אליהם מצביע l.front. בכל איטרציה:
- שורה 3 מייצרת מצביע nxt המצביע לl.front.next ‏(B)‏.
- שורה 4 גורמת לl.front.next להצביע לרשימת החוליות שאליה מצביע new-front ‏(C)‏ (בתחילה זו רשימת חוליות ריקה, כמובן).
- שורה 5 גורמת לnew-front להצביע לl.front ‏(D)‏
- שורה 6 מקדמת את l.front לחוליה הבאה (E).
- כלומר, כל איטרציה מעבירה חוליה מתחילת הרשימה לראש רשימת חוליות אליה מצביע new-front‏.‏ (F) מראה זאת בצורה ברורה יותר עבור האיטרציה הראשונה.
לאחר סיום הלולאה, שורה 7 עושה את כל מה שנותר: לגרום לl.front להצביע לחוליה הראשונה בnew-front.

ניתוח סיבוכיות וזיכרון

קל לראות שהסיבוכיות היא $\displaystyle \Theta (n)$ :

1 ו7 הן $\displaystyle O(1)$ .
3-6 הן $\displaystyle O(1)$ ולכן 2-6 $\displaystyle \Theta (n)$ (כי ברור שהלולאה מתבצעת $\displaystyle n$ פעמים).

כמו כן השתמשנו בכמות מוגבלת של זכרון (השתמשנו בשני משתני עזר בלבד).

4

המבנה הרקורסיבי של הבעיה

ראשית מספר סימונים:

כפי שצוין בשאלה, נגדיר את אורך $\displaystyle X$ כ $\displaystyle m$ , ואת אורך $\displaystyle Y$ כ $\displaystyle n$ .
נסמן את הרישה ה $\displaystyle i$ של מחרוזת $\displaystyle X$ כ $\displaystyle X_{i}$ . במילים אחרות, $\displaystyle X_{i}=x_{1},...,x_{i}$ .‏
נגדיר כ $\displaystyle l(i,j)$ את אורך הLCS של $\displaystyle X_{i}$ ו $\displaystyle Y_{j}$ . במילים אחרות, $\displaystyle l(i,j)$ היא אורך תת-הסדרה הארוכה ביותר המשותפת ל $\displaystyle X_{i}$ ו $\displaystyle Y_{j}$ .

עכשיו תורכם:

וודא שהמך מבין מדוע לפי הגדרה זו,

\displaystyle l(m,n)

הוא אורך הLCS של

\displaystyle X

ו

\displaystyle Y

.

משפט:

$\displaystyle l(i,j)$ מקיים את הנוסחה הבאה:

אם $\displaystyle i=0$ או $\displaystyle j=0$ ,‏ אז $\displaystyle l(i,j)=0$ .
אם לא,‏ אז:
1. אם $\displaystyle x_{i}=y_{j}$ , אז $\displaystyle l(i,j)=1+l(i-1,j-1)$ .
2. אם $\displaystyle x_{i}\neq y_{j}$ , אז $\displaystyle l(i,j)=\max\{l(i-1,j),l(i,j-1)\}$ .

הוכחה: אם $\displaystyle i=0$ או $\displaystyle j=0$ , אז (לפחות) אחת המחרוזות היא המחרוזת הריקה, ורק המחרוזת הריקה יכולה להיות תת-מחרוזת של המחרוזת הריקה. למחרוזת הריקה יש אורך 0, ומכאן החלק הראשון של המשפט.

מכאן נניח ששתי המחרוזות אינן ריקות.

נניח ש $\displaystyle x_{i}=y_{j}$ . ראשית, קל לראות שבהכרח תווה האחרון של $\displaystyle Z$ הוא $\displaystyle x_{i}$ - אם זה לא היה המצב, אז $\displaystyle Zx_{i}$ גם היא מחרוזת משותפת ל $\displaystyle X_{i}$ ו $\displaystyle Y_{j}$ , דבר שנוגד עפ"י ההגדרה את היותה של $\displaystyle Z$ תת-המחרוזת המשותפת הארוכה ביותר. נחשוב כעת על כל תתי המחרוזות המשותפות מהצורה $\displaystyle Z'x_{i}$ : עבור כל אחת מהן, קל לראות ש $\displaystyle Z'$ היא תת-מחרוזת משותפת ל $\displaystyle X_{i-1}$ ו $\displaystyle Y_{j-1}$ , ולכן בהכרח הארוכה שבהן היא זו שהרישה שלה היא הLCS של $\displaystyle X_{i-1}$ ו $\displaystyle Y_{j-1}$ .

לחלופין, נניח ש $\displaystyle x_{i}\neq y_{j}$ ; יש שלוש אפשרויות:

$\displaystyle Z$ מסתיימת ב $\displaystyle x_{i}$ - אם כן, הLCS בהכרח מהצורה $\displaystyle Z'x_{i}$ , כאשר $\displaystyle Z'$ היא הLCS של $\displaystyle X_{i}$ ו $\displaystyle Y_{j-1}$ .
$\displaystyle Z$ מסתיימת ב $\displaystyle y_{j}$ - אם כן, הLCS בהכרח מהצורה $\displaystyle Z'y_{j}$ , כאשר $\displaystyle Z'$ היא הLCS של $\displaystyle X_{i-1}$ ו $\displaystyle Y_{j}$ .
$\displaystyle Z$ אינה מסתיימת ב $\displaystyle x_{i}$ , וכן אינה מסתיימת ב $\displaystyle y_{j}$ - אם זה המצב, אז הLCS של $\displaystyle X_{i-1}$ ו $\displaystyle Y_{j-1}$ הוא הLCS של $\displaystyle X_{i-1}$ ו $\displaystyle Y_{j}$ (וכן גם הLCS של $\displaystyle X_{i}$ ו $\displaystyle Y_{j-1}$ ), כך ששתי הבדיקות הקודמות מכסות כבר (פעמיים אפילו) מקרה זה.

מציאת אורך הLCS

להלן פסוודו-קוד למציאת אורך הLCS.

1	L = Make-Matrix(m, n)

2	for i in [1, ..., m]
3		for j in [1, ..., n]
4			L[i][j] = Nil

LCS-Length(i, j)
1	if L[i][j] == Nil
2		if i == 0 or j == 0
3			return 0
4		else if X[i] == Y[j]
5			L[i][j] = 1 + LCS-Length(i - 1, j - 1)
6		else
7			guess-x = LCS-Length(i - 1, j)
8			guess-y = LCS-Length(i, j - 1)
		
9			L[i][j] = Max(guess-x, guess-y)

10	return L[i][j]

ארבע השורות הראשונות מאתחלות מטריצה המשמשת לmemoization, והפונקציה LCS-Length מוצאת את את האורך המבוקש. 1-4 מייצרות מטריצה (גלובלית) שכל אחד מאיבריה מאותחל לNil.‏ 2-9 של LCS-Length, פועלות בדיוק לפי נוסחת הנסיגה הקודמת (שאת נכונותה כבר הראינו). המטריצה L, בפרט ב1 של LCS-Length, מטפלות במצב בו הפונקציה נקראת עם פרמטרים שאתם היא כבר נקראה בעבר.

ניתוח סיבוכיות

נגדיר את $\displaystyle T'(i,j)$ כזמן שאורכת LCS-Length בהנחה שכל אחת מקריאותיה הרקורסיביות היא $\displaystyle O(1)$ . קל לראות ש $\displaystyle T'(i,j)=O(1)$ .

זמן הריצה של LCS-Length(m, n) חסום מלמעלה על ידי $\displaystyle \sum _{i=0}^{m}\sum _{j=0}^{n}[T'(i,j)]=\Theta (m\cdot n)$ . חוץ מכך ישנו האתחול 1-4 שאורך גם כן $\displaystyle \Theta (m\cdot n)$ . הזמן הכולל, לכן, הוא $\displaystyle O(m\cdot n)$ .

הדפסת איברי הLCS

ראשית נשנה מעט את הפסוודו-קוד הקודם.

1	L = Make-Matrix(m, n)
2	D = Make-Matrix(m, n)

3	for i in [1, ..., m]
4		for j in [1, ..., n]
5			L[i][j] = Nil


LCS-Length(i, j)
1	if L[i][j] == Nil
2		if i == 0 or j == 0
3			return 0
4		else if X[i] == Y[j]
5			L[i][j] = 1 + LCS-Length(i - 1, j - 1)
6			D[i][j] = 'b'
7		else
8			guess-x = LCS-Length(i - 1, j)
9			guess-y = LCS-Length(i, j - 1)
		
10			L[i][j] = Max(guess-x, guess-y)
	
11			if L[i][j] == guess-x
12				D[i][j] = 'x'
13			else
14				D[i][j] = 'y'	

15	return L[i][j]

המטריצה הגלובלית D מתארת בכניסה ה $\displaystyle (i,j)$ את ההחלטה לגבי הLCS של $\displaystyle X_{i}$ ו $\displaystyle Y_{j}$ :

'x' מסמלת את ההחלטה לוותר על התו האחרון ב $\displaystyle X_{i}$ .
'y' מסמלת את ההחלטה לוותר על התו האחרון ב $\displaystyle Y_{j}$ .
'b' מסמלת את ההחלטה לוותר על התו האחרון בשניהם. זה בדיוק המצב בו $\displaystyle X_{i}=Y_{j}$ נמצא כחלק מהLCS.הפונקציה הבאה מדפיסה את הLCS כאשר קוראים לPrint-LCS(m, n):

Print-LCS(i, j)
1	if i > 1 and j > 1
2		if D[i][j] == 'x':
3			Print-LCS(i - 1, j)
4		else if D[i][j] == 'y':
5			Print-LCS(i, j - 1)
6		else
7			Print-LCS(i - 1, j - 1)

1	if D[i][j] == 'b':
2		Print(X[i])

קל לראות שהסיבוכיות עדיין $\displaystyle \Theta (m\cdot n)$ : השינויים בLCS-Length אינם משנים את סיבוכיותה; כל קריאה לPrint-LCS(i, j) מורידה (לפחות) את אחד הארגומנטים שלה ב1, ולכן היא יכולה להיקרא לכל היותר $\displaystyle m+n$ פעמים. הסיבוכיות, לכן, היא $\displaystyle \Theta (m\cdot n)$ + $\displaystyle O(m+n)$ = $\displaystyle \Theta (m\cdot n)$ .

5

המבנה הרקורסיבי

נגדיר כ $\displaystyle m(i,j)$ את מקסימום הרווח מפיסת בד במידות $\displaystyle (i,j)$ .‏

משפט:

$\displaystyle m(i,j)$ נתונה על ידי נוסחת הנסיגה הבאה:

$\displaystyle m(i,j)=\max\{$
$\displaystyle \max _{1\leq i'<i}m(i',j)+m(i-i',j),$
$\displaystyle \max _{1\leq j'<j}m(i,j')+m(i,j'-j),$
$\displaystyle value(i,j)\}$
(כאשר $\displaystyle value(i,j)$ הוא הערך המוחזר מהפונקציה Value(i, j)).

כדאי לדעת:

שים לב שהנוסחה הנ"ל כוללת בתוכה תנאי עצירה, מפני שעבור

\displaystyle i=j=1

, מה שכתוב כאן הינו פשוט

\displaystyle value(i,j)\}

.

אפשר גם לכתוב את נוסחת הנסיגה בדרכים אחרות, ובחלקן גם יופיעו תנאי עצירה בצורה מפורשת יותר.

הוכחה: יש שלוש אפשרויות:

כדאי לחתוך את פיסת הבד אפקית באיזשהו $\displaystyle i'$ (כמתואר בתרשים הבא). נשים לב שאפשרות זו רלוונטית רק עבור עבור $\displaystyle i>1$ .
כדאי לחתוך את פיסת הבד אנכית באיזשהו $\displaystyle j'$ (כמתואר בתרשים הבא אחריו). נשים לב שאפשרות זו רלוונטית רק עבור עבור $\displaystyle j>1$ .
כלל לא משתלם לחתוך את פיסת הבד.

בתרשים הבא, לדוגמה, חיתוך אופקי של הצורה בA בשורה $\displaystyle i'$ ייצור שתי צורות מלבניות בB; לראשונה שבהן יהיו $\displaystyle i'$ שורות:

בתרשים הבא, לדוגמה, חיתוך אנכי של הצורה בA בעמודה $\displaystyle j'$ ייצור שתי צורות מלבניות בB; לראשונה שבהן יהיו $\displaystyle j'$ עמודות:

כעת נדון בכל אחת משלוש האפשרויות:

כדאי לחתוך את פיסת הבד אפקית באיזשהו $\displaystyle i'$ . במקרה זה נקבל שתי חתיכות בד, האחת במידות $\displaystyle (i',j)$ ,‏ והשניה במידות $\displaystyle (i-i',j)$ . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא $\displaystyle m(i',j)$ ,‏ ועבור השניה $\displaystyle m(i-i',j)$ .
כדאי לחתוך את פיסת הבד אנכית באיזשהו $\displaystyle j'$ . במקרה זה נקבל שתי חתיכות בד, האחת במידות $\displaystyle (i,j')$ ,‏ והשניה במידות $\displaystyle (i,j-j')$ . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא $\displaystyle m(i,j')$ ,‏ ועבור השניה $\displaystyle m(i,j-j')$ .
כלל לא משתלם לחתוך את פיסת הבד: הטוב ביותר האפשרי הוא Value(i, j).

היות שאיננו יודעים איזו משלוש האפשרויות היא הטובה ביותר, אנו לוקחים את המקסימום מבין שלושתן.

מימוש רקורסיבי נאיבי

הפסוודו-קוד הבא מראה מימוש פשוט לנוסחה הנ"ל:

Max-Value(i, j)
1	max-value = 0

	# Check horizontal cuts.

	# This loop means the C-language loop for(i' = 1; i' < i; ++i')
2	for i' in [1, ..., i - 1]
3		guess = Max-Value(i', j) + Max-Value(i - i', j)		
4		if guess > max-value
5			max-value = guess
		
	# Check vertical cuts.

	# This loop means the C-language loop for(j' = 1; j' < j; ++j')
6	for j' in [1, ..., j - 1]
7		guess = Max-Value(i, j') + Max-Value(i, j - j')		
8		if guess > max-value
9			max-value = guess

	# Check the worth of this shape.

19	guess = Value(i, j)
	
11	if guess > max-value
12		max-value = guess

13	return max-value

שימוש בmemoization

כרגיל, נוסיף מבנה נתונים פשוט (במקרה זה המטריצה M) כדי לשמור את הערכים שכבר חישבנו:

1	M = Make-Matrix(m, n)

2	for i in [1, ..., m]
3		for j in [1, ..., n]
4			M[i][j] = Nil


Max-Value(i, j)
1	if M[i, j] != Nil
2		return M[i, j]

4	max-value = 0

	# Check horizontal cuts.

5	for i' in [1, ..., i - 1]
6		guess = Max-Value(i', j) + Max-Value(i - i', j)		
7		if guess > max-value
8			max-value = guess
		
	# Check vertical cuts.

9	for j' in [1, ..., j - 1]
10		guess = Max-Value(i, j') + Max-Value(i, j - j')		
11		if guess > max-value
12			max-value = guess

	# Check the worth of this shape.

13	guess = Value(i, j)
	
14	if guess > max-value
15		max-value = guess
		
16	M[i, j] = max-value

17	return max-value

הדפסת החלטות החיתוך

שוב כרגיל, כדי לשמור גם את סדרת הפעולות (ולא רק תוצאתן), נוסיף עוד מבנה נתונים פשוט (במקרה זה המטריצה C):

1	M = Make-Matrix(m, n)
2	C = Make-Matrix(n, n)

3	for i in [1, ..., m]
4		for j in [1, ..., n]
5			M[i][j] = Nil
6			C[i][j] = Nil


Max-Value(i, j)
1	if M[i, j] != Nil
2		return M[i, j]

3	max-value = 0

	# Check horizontal cuts.

4	for i' in [1, ..., i - 1]
5		guess = Max-Value(i', j) + Max-Value(i - i', j)		
6		if guess > max-value
7			max-value = guess
8			C[i][j] = ('Horizontal', i')
		
	# Check vertical cuts.

9	for j' in [1, ..., j - 1]
10		guess = Max-Value(i, j') + Max-Value(i, j - j')		
11		if guess > max-value
12			max-value = guess
13			C[i][j] = ('Vertical', j')

	# Check the worth of this shape.

14	guess = Value(i, j)
	
15	if guess > max-value
16		max-value = guess
17		C[i][j] = ('Shape', 0)
		
18	M[i, j] = max-value

19	return max-value

המטריצה C היא מטריצה של זוגות (בשפת C היינו ממשים זאת בעזרת מטריצה של מבנים):

האיבר הראשון בכל זוג הוא מחרוזת, המתארת איזו משלוש האפשרויות היא בחרנו.
האיבר השני בכל זוג הוא מספר המתאר היכן חתכנו.

הנה הקוד המדפיס את סדרת הפעולות:

Print-Cuts(i, j)
1	Print('For the best value of ' + i + ' and ' + j)

2	(type, index) = C[i][j]

3	if type == 'Horizontal'
4		Print 'Cut horizontally at ' + index
5		Print-Cuts(index, j)
6		Print-Cuts(i - index, j)
7	else if type == 'Vertical'
8		Print 'Cut vertically at ' + index
9		Print-Cuts(i, index)
10		Print-Cuts(i, j - index)
11	else
12		Print 'Use the shape itself'

ניתוח סיבוכיות

נגדיר כ $\displaystyle T'(i,j)$ את סיבוכיות Max-Cuts(i, j) בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$ . קל מאד לראות מהקוד ש $\displaystyle T'(i,j)=\Theta (i+j)$ . נשים לב גם ש $\displaystyle \Theta (i+j)=O(m+n)$ , ולכן $\displaystyle T'(i,j)=O(m+n)$ . סיבוכיות $\displaystyle Max-Cuts(m,n)$ חסומה מלמעלה על ידי $\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}[T'(i,j)]=\sum _{i=1}^{m}\sum _{j=1}^{n}[O(m+n)]=O(m\cdot n\cdot (m+n))$ .

גם כאשר לוקחים בחשבון את האתחול והדפסת הפרטים, הפתרון עדיין $\displaystyle O(m\cdot n\cdot (m+n))$ .

6

הרעיון הכללי

נממש את התור כך שיכיל שתי מחסניות:

in-stack תשמש אותנו להכנסת איברים.
out-stack תשמש אותנו להוצאת איברים.

כאשר דוחפים איבר v (לתור), פשוט דוחפים אותו למחסנית in-stack שבתור.

דוגמה:

כך ייראה התור בתחילה:

מימוש תור בעזרת שתי מחסניות - מצב התחלתי.

נניח שלאחר יצירת התור אנו דוחפים את 3 לתוכו. כך ייראה התור:

אם נדחוף לתור כעת 5, כך ייראה התור:

בפעולת Dequeue, ננסה לבדוק האם אפשר לשלוף מout-stack. אם כן - סיימנו, אם לא, ראשית נעביר את כל האיבר מin-stack לout-stack, ואז נשלוף מתוכו.

דוגמה:

נניח שאנו שולפים כעת מהתור. היות שout-stack ריק, ראשית נעביר בלולאה את כל האיברים מin-stack אליו. כך הוא ייראה:

מימוש תור בעזרת שתי מחסניות - שליפת 3 - צעד 1.

כעת נשלוף מראש out-stack:

מימוש תור בעזרת שתי מחסניות - שליפת 3 - צעד 2.

עכשיו תורכם:

כיצד ייראה התור אם נדחוף אליו את 11?

פתרון

נדחוף זאת כרגיל לin-stack:

עכשיו תורכם:

כעת, כיצד ייראה התור אם נשלוף איבר?

פתרון

היות שout-stack אינו ריק, פשוט נשלוף את האיבר הראשון מתוכו (כלומר 5):

מימוש תור בעזרת שתי מחסניות - שליפת 5.

פסוודו-קוד

להלן מבנה התור (במימוש זה). הוא פשוט מכיל שתי מחסניות.

# A queue (implemented usin-stackg two stacks)
Queue
1	in-stack # A stack to which to Push elements.
2	out-stack # A stack from which to Dequeue elements.

כאשר דוחפים איבר v (לתור), פשוט דוחפים אותו למחסנית in-stack שבתור:

Enqueue(q, v)
1	Push(q.in-stack, v)

בפעולת Dequeue, ננסה לבדוק האם אפשר לשלוף מout-stack. אם כן - סיימנו, אם לא, ראשית נעביר את כל האיבר מin-stack לout-stack, ואז נשלוף מתוכו:

Dequeue(q)
1	if Size(q.out-stack) == 0
2		while Size(q.in-stack) > 0
3			v = Pop(q.in-stack)
4			Push(q.out-stack, v)
		
5	return Pop(q.out-stack)

קל לממש פעולות אחרות. לדוגמה, אם נניח שהמחסניות תומכות בפעולה Size (המחזירה את מספר האיברים), ורוצים לממש את פעולת Size לתור, פשוט נחזיר את סכום הגדלים:

Size(q)
1	return Size(q.in-stack) + Size(q.out-stack)

לחלופין, אם נניח שהמחסניות תומכות בפעולה Empty (המחזירה האם המחסנית ריקה), ורוצים לממש את פעולת Empty לתור, פשוט נחזיר האם כל אחת מהמחסניות ריקה:

Empty(q)
1	return Empty(q.in-stack) and Empty(q.out-stack)

עכשיו תורכם:

כיצד תממש את פעולת Front, המחזירה את האיבר הראשון המועמד להוצאה (אך אינה משנה את תוכן התור)?

פתרון

נממש זאת באופן דומה לזה שבDequeue של התור, אך נשתמש בTop של מחסנית, כך:

Front(q)
1	if Size(q.out-stack) == 0
2		while Size(q.in-stack) > 0
3			v = Dequeue(q.in-stack)
4			Push(q.out-stack, v)
		
5	return Top(q.out-stack)

הוכחת נכונות

משפט:

נניח שבin-stack יושבים $\displaystyle \ell$ איברים: $\displaystyle u_{1},\ldots ,u_{\ell }$ ‏ ( $\displaystyle u_{1}$ הוא האיבר הראשון שיישלף מהמחסנית , ו $\displaystyle v_{\ell }$ האחרון), ונניח שבout-stack יושבים $\displaystyle m$ איברים: $\displaystyle v_{1},\ldots ,v_{m}$ ‏ ( $\displaystyle v_{1}$ הוא האיבר הראשון שיישלף מהמחסנית , ו $\displaystyle v_{\ell }$ האחרון).

אז $\displaystyle v_{1},\ldots ,v_{m},u_{\ell },\ldots ,u_{1}$ (לפי סדר זה, משמאל לימין), הם בדיוק $\displaystyle m+\ell$ האיברים האחרונים שהוכנסו לתור וטרם הוצאו (כלומר $\displaystyle v_{1}$ הוא האיבר המוקדם ביותר שהוכנס וטרם נשלף, ו $\displaystyle u_{\ell }$ הוא האיבר המאוחר ביותר שהוכנס וטרם נשלף).

להלן טענת המשפט באופן גרפי:

הוכחה: נוכיח את הטענה באינדוקציה על מספר הפעולות.

(בסיס האינדוקציה) לפני הפעולה הראשונה, 0 איברים הוכנסו או נשלפו, ושתי המחסניות ריקות. הטענה נכונה באופן טריביאלי.

(מעבר האינדוקציה) נניח שהטענה נכונה לאחר מספר פעולות: כעת בin-stack יושבים $\displaystyle u_{1},\ldots ,u_{\ell }$ , בout-stack יושבים $\displaystyle v_{1},\ldots ,v_{m}$ , והטענה מתקיימת עד כה. נראה שהטענה מתקיימת לאחר הפעולה הבאה:

אם הפעולה הבאה היא Size (או Empty) או ‎Top, שום דבר אינו משתנה, והטענה בוודאי נכונה.
אם הפעולה הבאה היא Push של איבר u, אז out-stack לא ישתנה, ותוכן in-stack יהפוך להיות $\displaystyle u,u_{1},\ldots ,u_{m}$ . ואכן, לפי הנחת האינדוקציה, $\displaystyle v_{1},\ldots ,v_{m},u_{\ell },\ldots ,u_{1},u$ (לפי סדר זה, משמאל לימין), הם בדיוק $\displaystyle m+\ell +1$ האיברים האחרונים שהוכנסו לתור וטרם הוצאו. תוכל לראות זאת בתרשים בהמשך.
אם הפעולה הבאה היא ‎Top, יש שתי אפשרויות:
1. אם out-stack אינה ריקה, אז שום דבר אינו משתנה, והטענה בוודאי נכונה.
2. אם in-stack ריקה, אז לאחר 2-4 בFront, ‏ in-stack תהיה ריקה, וout-stack תכיל את האיברים $\displaystyle u_{\ell },\ldots ,u_{1}$ (כלומר $\displaystyle u_{\ell }$ האיבר הבא שיישלף). ואכן, לפי הנחת האינדוקציה $\displaystyle u_{\ell },\ldots ,u_{1}$ בדיוק $\displaystyle \ell$ האיברים האחרונים שהוכנסו וטרם הוצאו. תוכל לראות זאת בתרשים בהמשך.
אם הפעולה הבאה היא ‎Dequeue, הטענה דומה מאד לטענה ב‎Dequeue.

להלן תיאור גרפי של המצב בPush:

להלן תיאור גרפי של המצב בTop בו out-stack ריק בתחילה:

ניתוח סיבוכיות

משפט:

הסיבוכיות של $\displaystyle n$ פעולות הנה $\displaystyle O(n^{2})$ .

הוכחה: מהתבוננות בפונקציות, קל לראות את הדברים הבאים:

כל אחת מפעולות התור, למעט Dequeue (וTop), הנה $\displaystyle O(1)$ .
Dequeue (או לחלופין Top) הנה $\displaystyle \Theta (n')$ , כאשר $\displaystyle n'$ הוא מספר הפעולות במחסנית in-stack בעת הקריאה.

אפשר לראות זאת מכך שהלולאה היחידה היא 1-3 בDequeue (או לחלופין Top), וכל אחת מפעולות הרשימה המקושרת היא $\displaystyle O(1)$ .

אם מבצעים $\displaystyle n$ פעולות, הרי שבכל קריאה לDequeue יהיו לכל היותר $\displaystyle n$ איברים במחסנית. מכאן נקבל שזמן הריצה חסום מלמעלה על ידי $\displaystyle n\cdot O(n)=O(n^{2})$ .

אם כי המשפט הקודם נכון, נוכל לטעון טענה חזקה יותר.

משפט:

הסיבוכיות של $\displaystyle n$ פעולות הנה $\displaystyle \Theta (n)$ .

עכשיו תורכם:

וודא שהנך מבין מדוע שני המשפטים אינם סותרים זה את זה.

ראשית, קל לראות כי הסיבוכיות הנה $\displaystyle \Omega (n)$ , משום שאנו מבצעים $\displaystyle n$ קריאות לפונקציות, וכל אחת מהן הרי $\displaystyle \Omega (1)$ . כל שנותר, לכן, הוא להוכיח חסם $\displaystyle O(n)$ . להלן שתי הוכחות לכך.

כדאי לדעת:

כל אחת מההוכחות הבאות מסתמכת על צורת ניתוח הידועה בשם amortized analysis. בספר הקורס, הפרק "Amortized Analysis" עוסק בכך.

להלן ההוכחה הראשונה.

הוכחה: נוכיח את הטענה באינדוקציה על אורך סדרת הפעולות, $\displaystyle n$ .

(בסיס האינדוקציה) עבור $\displaystyle n=1$ עלינו להוכיח שסדרת הפעולות (שהיא פעולה יחידה במקרה זה) הנה $\displaystyle O(1)$ . ואכן, כשעוברים על הקוד של כל אחת מהפונקציות, ברור שכשהיא הפעולה הראשונה (והיחידה) בסדרת פעולות המתחילה בתור ריק - זמנה הוא $\displaystyle O(1)$ .

(מעבר האינדוקציה) נניח שהטענה נכונה לכל $\displaystyle n'$ קטן (ממש) מ $\displaystyle n$ , ונראה שהיא נכונה ל $\displaystyle n$ . כפי שהזכרנו, ברור מהתבוננות בקוד שרק לפעולות Dequeue וFront תתכן סיבוכיות שאיננה $\displaystyle O(1)$ (וגם זאת בהתאם למצב המחסניות) - לכל אחת מהפעולות האחרות בוודאות סיבוכיות $\displaystyle O(1)$ . אם בסדרת הפעולות לא נקראה אף אחת משתי פעולות אלו, ברור שהסיבוכיות היא $\displaystyle n\cdot O(1)=O(n)$ . אחרת, נגדיר כ $\displaystyle n'$ את מספר הפעולה האחרונה בסדרת הפעולות שהיתה מסוג Dequeue או Front (כל אחת מהפעולות אחריהן יכולה להיות, נניח, Enqueue, אך לא אחת משתי אלו). סיבוכיות סדרת הפעולות מ1 עד (כולל) $\displaystyle n'$ היא $\displaystyle O(n')$ , וזאת מהנחת האינדוקציה. סיבוכיות שאר הפעולות היא $\displaystyle (n-n')\cdot O(1)=O(n-n')$ . סך הכל, לכן, נקבל $\displaystyle O(n)+O(n-n')=O(n)$ .

ולהלן הוכחה חלופית.

הוכחה: כדי לראות שסך הפעולות הן $\displaystyle O(n)$ , נשים לב לעובדה הבאה. כל ערך v יכול לעבור לכל היותר פעם אחת את המסלול הבא:

Push(q.in-stack, v) (בקריאה לPush של התור).
Dequeue(q.in-stack) (בקריאה לDequeue של התור).
Push(q.out-stack, v) (בקריאה לDequeue של התור).

לכן כל איבר שנדחף לתור יכול לתרום לכל היותר $\displaystyle O(1)$ לסיבוכיות רצף הפעולות. ברור שברצף של $\displaystyle n$ פעולות, יידחפו לתור לכל היותר $\displaystyle n$ איברים.

7

שאלה זו ותשובתה דומים מאד לשאלה על מציאת איברים שלמים בתחום. מטרת השאלה היא להבין כיצד לעקוף הבדלים טפלים בין בעיות שונות.

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

Less-Than-Dist(Values, v)
1	return Less-Than-Dist'(Values, v, 1, Length(Values))


Less-Than-Dist'(Values, v, left, right)
1	if left > right
2		return right
		
3	mid = ⌊(left + right) / 2⌋
		
4	if Dist(v) <= Dist(Values[mid])
5		return Less-Than-Pos'(Values, v, left, mid - 1)

6	if Dist(v) > Dist(Values[mid])
7		return Less-Than-Pos'(Values, v, mid + 1, right)

כעת נותר לטפל בפונקציה האחרונה. פונקציה זו ביצעה שתי קריאות:

Less-Than-Dist(A, b) - כאן אין הבדל.
Less-Than-Dist(A, a + 1) - מדוע הוספנו דווקא את המספר 1? מהתבוננות בתשובה עולה שכל שהיינו צריכים לעשות הוא להוסיף ל $\displaystyle a$ מספר שגודלו הוא לכל היותר ההפרש בין שני איברים שונים במערך. במקרה שמדובר במספרים שלמים, ההפרש בין שני מספרים שונים במערך הוא לפחות 1.

במקרה החדש, נעבור על המערך, ונמצא את $\displaystyle d$ - ההפרש הקטן ביותר בין שני מספרים שונים. היות שהמערך ממויין, ברור שנוכל לעשות זאת בזמן לינארי. נסיים את הפתרון בהצגת הקריאה האחרונה:

Find-Num-In-Range(A, a, b)
1	d = Min-Dist-Between-Two-Elements(A) # Finds the smallest distance as was just described.
2	return Less-Than-Dist(A, b) - Less-Than-Dist(A, a + d)