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

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

פרימיטיבים

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

Print( "Hello" )

a = 3

if i == j

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

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

++b

mid = ⌊(left + right) / 2⌋

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

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

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

רצפים

כל רצף של פקודות עולה סך הזמן של כל אחת מהפקודות. לדוגמה, אם תבנית:קוד בשורה עולה $\mathrm{\Theta }(n)$ (כאשר $n$ הוא תבנית:קוד בשורה), אז קטע הקוד הבא אורך $\mathrm{\Theta }(n)$.

1	a = 3

2	Foo(a, B, 3)

3	if j == 1
4		print "Hello"

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

לולאות

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

תבנית:מבנה תבנית

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

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

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

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