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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

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

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

תוכן עניינים

1 מימוש תור בעזרת שתי מחסניות
- 1.1 שאלה
- 1.2 תשובה

[עריכה] מימוש תור בעזרת שתי מחסניות

[עריכה] שאלה

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

[עריכה] תשובה

[עריכה] הרעיון הכללי

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

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):

קובץ:Dsa queue from 2 stacks Dequeue 5.png

[עריכה] פסוודו-קוד

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

# 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 שבתור:

Push(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 = Dequeue(q.in-stack)
4			Push(q.out-stack, v)
 
5	return Dequeue(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$ איברים.

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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

[עריכה] מימוש תור בעזרת שתי מחסניות

[עריכה] שאלה

[עריכה] תשובה

[עריכה] הרעיון הכללי

[עריכה] פסוודו-קוד

[עריכה] הוכחת נכונות

[עריכה] ניתוח סיבוכיות

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא