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

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

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

פרימיטיבים

פקודות מסויימות פשוטות כ"כ שברור שכ"א אורכת $\displaystyle O(1)$. להלן מספר דוגמות:

Print( "Hello" )

a = 3

if i == j

פעולות חשבוניות

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

++b

mid = ⌊(left + right) / 2⌋

קריאות לפונקציות

נניח שאנו רואים בקוד את הפקודה Foo(a, B, 3). הפונקציה Foo אורכת זמן כלשהו, אך כמה עולה הקריאה עצמה? חשוב להבין שהקריאה עצמה אורכת $\displaystyle O(1)$ זמן.

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

רצפים

כל רצף של פקודות עולה סך הזמן של כל אחת מהפקודות. לדוגמה, אם Foo(a, B, 3) עולה $\displaystyle \Theta (n)$ (כאשר $\displaystyle n$ הוא (Length(B)), אז קטע הקוד הבא אורך $\displaystyle \Theta (n)$.

1	a = 3

2	Foo(a, B, 3)

3	if j == 1
4		print "Hello"

1, 3, ו4 אורכות כל אחת $\displaystyle \Theta (1)$, ו2 אורכת $\displaystyle \Theta (n)$. סה"כ נקבל $\displaystyle \Theta (1)+\Theta (n)+\Theta (1)+\Theta (1)=\Theta (3+n)=\Theta (n)$ (עפ"י אדיטיביות).

לולאות

נתבונן בלולאה בקטע הקוד הבא.

1	for i in [1, …, n]
2		Foo(a, B, 3)

ברור לחלוטין ש2 מתבצעת $\displaystyle n$ פעמים. לכן, אם Foo היא $\displaystyle O(1)$, אז 2 תורמת $\displaystyle \Theta (n)$ לסיבוכיות, ואם Foo היא $\displaystyle \Theta (n)$, אז 2 תורמת $\displaystyle \Theta (n^{2})$ לסיבוכיות.

מה סיבוכיות שתי השורות, 1-2? במקרה הראשון גם כן $\displaystyle \Theta (n)$, ובמקרה השני גם כן $\displaystyle \Theta (n^{2})$.‏ 1 עולה $\displaystyle \Theta (n)$: ככלות הכל, בשפת C, היינו כותבים אותה כך:

for(i = 1; i <= n; ++i)

לכן במקרה הראשון הסיבוכיות היא $\displaystyle \Theta (n)+\Theta (n)=\Theta (n)$, ובמקרה השני $\displaystyle \Theta (n)+\Theta (n^{2})=\Theta (n^{2})$.

באופן דומה, נתבונן בלולאה הכפולה בקטע הקוד הבא.

1	for i in [1, …, n]
2		for j in [1, …, m]
3			Foo(a, B, 3)

ברור ש2 מתבצעת $\displaystyle n$ פעמים, ו3 מתבצעת $\displaystyle m\cdot n$ פעמים. לכן אם Foo היא $\displaystyle O(1)$, אז הסיבוכיות היא $\displaystyle \Theta (n)+\Theta (m\cdot n)+\Theta (m\cdot n)=\Theta (m\cdot n)$ ואם Foo היא $\displaystyle \Theta (n)$, אז הסיבוכיות היא $\displaystyle \Theta (n)+\Theta (m\cdot n)+\Theta (m\cdot n^{2})=\Theta (m\cdot n^{2})$

לסיום, נתבונן בלולאה הכפולה בקטע הקוד הבא.

1	for i in [1, …, n]
2		for j in [1, …, f(i)]
3			Print( "Hello" )

כאן $\displaystyle f$ היא פונקציה מתמטית כלשהי המתרגמת מספרים שלמים חיוביים למספרים שלמים חיוביים. ודא שהנך יכול להראות שהסיבוכיות היא $\displaystyle \Theta (n+\sum _{i=1}^{n}[f(i)])$.

פונקציות רקורסיביות רגילות

להלן דוגמה לפונקציה רקורסיבית.

Foo(n)
1	if n == 1
2		return 1
	
3	return Foo(n - 1)

כיצד אפשר לנתח זאת? לרוב כדאי לפעול לפי הרעיון הבא. נגדיר את זמן הריצה של Foo בהנתן קלט בגודל $\displaystyle i$ כ$\displaystyle T(i)$. בגוף הפונקציה, נחייב כל קריאה לפונקציה לפי הגדרה זאת.

לדוגמה, 3 אורכת $\displaystyle T(n-1)$. לפי מה שראינו ברצפים, גוף הפונקציה, כאשר הארגומנט הוא $\displaystyle n$, אורך $\displaystyle \Theta (1)+T(n-1)$. זהו בדיוק $\displaystyle T(n)$, על פי ההגדרה. קיבלנו את נוסחת הנסיגה $\displaystyle T(n)=\Theta (1)+T(n-1)$.

דוגמה: להלן הפסוודו-קוד של מיון מיזוג: # Merge sort. # Takes an array (Values). # Returns an array of the same elements, sorted in increasing order. Merge-Sort(Values) 1 if Length(Values) <= 1 2 return Values 3 mid = ⌊(1 + Length(Values)) / 2⌋ 4 L = Merge-Sort( Values[1, ... , mid] ) 5 R = Merge-Sort( Values[mid + 1, ... , Length(Values)] ) 6 return Merge(L, R) הפונקציה Merge פועלת בזמן לינארי. נקבל, לכן, את נוסחת הנסיגה $\displaystyle T(n)=2\cdot T(n/2)+\Theta (n)$, שאותה נוכל לפתור (בין היתר) על ידי הפרישה הבאה: עץ הפרישה של מיון מיזוג. נשים לב שבעץ זה, כל צומת מתאר קריאה אחת של האלגוריתם. צומת הראש, לדוגמה, פועל בזמן $\displaystyle \Theta (n)$, אך מבצע שתי קריאות נוספות. ‏

פונקציות רקורסיביות עם Memoization

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

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

1. זמן הריצה של הפונקציה על קלט בגודל $\displaystyle n$ הוא $\displaystyle O\left(\sum _{i=1}^{n}T'(i)\right)$.
2. אם קריאה עם קלט בגודל $\displaystyle n$ בהכרח תיקרא רקורסיבית לכל הגדלים בגודל פחות מ$\displaystyle n$, אז זמן הריצה הוא $\displaystyle \Theta \left(\sum _{i=1}^{n}T'(i)\right)$.

(את ההסבר לכך נלמד בבעיית דג הסלמון.)

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

הפרק הקודם: נוסחאות נסיגה

מציאת סיבוכיות פסוודו-קוד תרגילים

הפרק הבא: מיון הכנסה ומיזוג