יחידה 2: רקורסיה ומשפט האב

בניית יחסי נסיגה

כדי לבנות יחס נסיגה, עלינו לזהות את שלושת המרכיבים הבאים:

• מקרה בסיס: העלות עבור הקלט הקטן ביותר (לרוב `T(1) = O(1)`).
• מספר הקריאות הרקורסיביות: כמה פעמים הפונקציה קוראת לעצמה.
• גודל הקלט בכל קריאה רקורסיבית: באיזה גודל קלט הפונקציה קוראת לעצמה.
• עלות העבודה מחוץ לקריאות הרקורסיביות: כמה עבודה מתבצעת בכל צעד רקורסיבי (איחוד תוצאות, חלוקת קלט וכו').

דוגמאות:

• חיפוש בינארי: `T(n) = T(n/2) + O(1)` (קריאה רקורסיבית אחת על חצי מהקלט, עבודה קבועה).
• מיזוג ממוין (Merge Sort): `T(n) = 2T(n/2) + O(n)` (שתי קריאות רקורסיביות על חצי מהקלט כל אחת, עבודה לינארית במיזוג).

שיטות לפתרון יחסי נסיגה

משפט האב: כלי עוצמתי לפתרון מהיר

משפט האב מספק פתרונות אסימפטוטיים (Big-O) ליחסי נסיגה מהצורה הכללית:

T(n) = aT(n/b) + f(n)

כאשר:

שלושת המקרים של משפט האב

נגדיר את הערך הקריטי c_crit = log_b a. נשווה את f(n) ל-n^(c_crit).

• מקרה 1: אם f(n) = O(n^(c_crit - ε)) עבור איזשהו ε > 0 (כלומר, f(n) קטן פולינומית מ-n^(c_crit)), אז:

  T(n) = Θ(n^(log_b a))

  העלות נשלטת על ידי העבודה בעלים של עץ הרקורסיה.

• מקרה 2: אם f(n) = Θ(n^(c_crit)) (כלומר, f(n) שווה אסימפטוטית ל-n^(c_crit)), אז:

  T(n) = Θ(n^(log_b a) * log n)

  העלות מתחלקת באופן שווה בין כל רמות עץ הרקורסיה.

• מקרה 3: אם f(n) = Ω(n^(c_crit + ε)) עבור איזשהו ε > 0 (כלומר, f(n) גדול פולינומית מ-n^(c_crit)), וגם מתקיים התנאי הרגולרי: a * f(n/b) ≤ c * f(n) עבור איזשהו קבוע c < 1 ו-n גדול מספיק, אז:

  T(n) = Θ(f(n))

  העלות נשלטת על ידי העבודה בשורש עץ הרקורסיה.

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

דוגמאות ויישומים נפוצים

מיזוג ממוין (Merge Sort)

יחס נסיגה: T(n) = 2T(n/2) + O(n)

כאן: a=2, b=2, f(n)=O(n). נחשב log_b a = log_2 2 = 1. לכן, n^(log_b a) = n^1 = n. f(n) = O(n), וזה מתאים למקרה 2 של משפט האב. פתרון: T(n) = Θ(n log n).

חיפוש בינארי (Binary Search)

יחס נסיגה: T(n) = T(n/2) + O(1)

כאן: a=1, b=2, f(n)=O(1). נחשב log_b a = log_2 1 = 0. לכן, n^(log_b a) = n^0 = 1. f(n) = O(1), וזה מתאים למקרה 2 של משפט האב. פתרון: T(n) = Θ(log n).

שאלות לדיון

• 1. נתח את סיבוכיות הזמן של האלגוריתם הבא באמצעות משפט האב: T(n) = 3T(n/4) + n log n.
• 2. נתח את סיבוכיות הזמן של האלגוריתם הבא: T(n) = 2T(n/2) + n / log n. האם משפט האב ישים? אם לא, מדוע?
• 3. תאר אלגוריתם רקורסיבי לחישוב חזקה x^n בזמן O(log n). הצג את יחס הנסיגה המתאים ופתור אותו.

נקודות לתשובת מודל

• 1. זיהוי: a=3, b=4, f(n) = n log n. חישוב log_b a = log_4 3 ≈ 0.792. נשווה f(n) ל-n^(0.792). מכיוון ש-n log n גדול פולינומית מ-n^(0.792) (לדוגמה, n log n = Ω(n^(0.792 + ε)) עבור ε = 0.1), נבדוק את מקרה 3. יש לבדוק את התנאי הרגולרי: 3 * (n/4) log(n/4) ≤ c * n log n. עבור c = 3/4 < 1, התנאי מתקיים עבור n גדול מספיק. לכן, T(n) = Θ(n log n).
• 2. זיהוי: a=2, b=2, f(n) = n / log n. חישוב log_b a = log_2 2 = 1. נשווה f(n) ל-n^1 = n. הפונקציה f(n) = n / log n אינה קטנה פולינומית מ-n (מקרה 1), אינה שווה אסימפטוטית ל-n (מקרה 2), ואינה גדולה פולינומית מ-n (מקרה 3). הפער בין f(n) ל-n^(log_b a) אינו פולינומי. לכן, משפט האב אינו ישים. יש להשתמש בשיטות אחרות כגון עץ הרקורסיה.
• 3. אלגוריתם רקורסיבי לחישוב x^n ב-O(log n):

  power(x, n):

  if n == 0: return 1

  if n % 2 == 0: return power(x * x, n / 2)

  else: return x * power(x * x, (n - 1) / 2)

  יחס נסיגה: T(n) = T(n/2) + O(1). (בכל שלב, אנו מבצעים קריאה רקורסיבית אחת על חצי מהקלט, בתוספת עבודה קבועה של כפל ובדיקת זוגיות/אי-זוגיות). פתרון באמצעות משפט האב (מקרה 2, כאשר log_2 1 = 0): T(n) = Θ(log n).