| המועמדים צריכים להיות מסוגלים: | הערות והנחיות |
|---|---|
| להראות הבנה של linear search ו-binary search | כתוב אלגוריתם ליישום linear search. כתוב אלגוריתם ליישום binary search. התנאים הנדרשים לשימוש ב-binary search. איך הביצועים של binary search משתנים בהתאם למספר פריטי הנתונים |
| להראות הבנה של insertion sort ו-bubble sort | כתוב אלגוריתם ליישום insertion sort. כתוב אלגוריתם ליישום bubble sort. ביצועי פעולת מיון עשויים להסתמך על הסדר ההתחלתי של הנתונים ומספר פריטי הנתונים |
| להראות הבנה ושימוש ב-Abstract Data Types (ADT) | כתוב אלגוריתמים למציאת פריט בכל אחד מ: linked list, binary tree. כתוב אלגוריתמים להכנסת פריט לכל אחד מ: stack, queue, linked list, binary tree. כתוב אלגוריתמים למחיקת פריט מכל אחד מ: stack, queue, linked list. הראה הבנה ש-גרף הוא דוגמה ל-ADT. תאר את התכונות המרכזיות של גרף והסבר את שימושו למצב נתון. תלמידים לא ידרשו לכתוב קוד למבנה גרף |
| להראות כיצד ADTs ניתן ליישם באמצעות ADT אחר | תאר את ADTs הבא והראה כיצד ניתן ליישם אותם מסוגים מובנים או ADTs אחרים מתאימים: stack, queue, linked list, dictionary, binary tree |
| להראות הבנה שאפשר להשוות בין אלגוריתמים שונים המבצעים אותו משימה באמצעות קריטריונים (למשל זמן ביצוע השיטה והזיכרון המשמש) | כולל שימוש ב-Big O notation כדי לציין מורכבות זמן ומרחב |
חשיבה חישובית ופתיחת בעיות
מדעי המחשב A-Level · נושא 19
15:32
חיפוש ומיון
ספר טלפונים עם מיליון שמות. אם תבדוק אותם אחד אחד, ייתכן שתבצע מיליון השוואות. אבל כבר ידוע לך הטריק: פתח אותו בחצי…
קריינות באנגלית · כתוביות באנגלית ובסינית 中文 שאפשר להחליף ביניהן
19.1
אלגוריתמי חיפוש
סיילבוס
מקור: הסיילבוס הבינלאומי של קמבריד'ג'
חיפוש מוצא ערך מבוקש באוסף (לעיתים קרובות מערך) ומחזיר את מיקומו, או „לא נמצא”.

חיפוש ליניארי
חיפוש ליני עובר מהתחלה לסוף, ומשווה כל אלמנט למטרה:
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
אין צורך בהכנה, ולכן השיטה פועלת על כל רשימה. במקרה הגרוע O($n$) (הערך המבוקש בסוף או חסר); במקרה הטוב 1 השוואות. השתמשו בה בנתונים לא ממוינים או ברשימות קטנות. (הערך -1 המוחזר הוא ערך זקיף — מיקום בלתי אפשרי שמשמעותו „לא נמצא”; הקוד הקורא בודק את IF result = -1.)
הגרסה במבחן. בבחן 3 עליך להשלים חיפוש ליניארי שנכתב עם דגל וWHILE לולאה, ובבחן 4 לכתוב פונקציה שהמחזירה אינדקס או ספירה. שניהם נראים כך:
FUNCTION LinearSearch(Data : ARRAY OF INTEGER, Target : INTEGER) RETURNS INTEGER
DECLARE Index, Count : INTEGER
Count ← 0
FOR Index ← 1 TO 100
IF Data[Index] = Target THEN
Count ← Count + 1
ENDIF
NEXT Index
RETURN Count // how many times Target occurs; 0 means not found
ENDFUNCTION
כדי לעצור בתוצאה הראשונה במקום זאת, השתמש בWHILE Index <= 100 AND NOT Found לולאה שמגדירה Found ← TRUE ושומרת על האינדקס. הנקודות הן עבור הלולאה על כל אלמנט, ההשוואה, והמה שמוחזר כאשר הערך לא קיים.

חיפוש בינארי
חיפוש בינארי דורש שהנתונים יהיו מסודרים. התבונן באלמנט האמצעי; אם הוא היעד, הגמר; אם היעד קטן יותר, חפש בחצי השמאלי, אחרת בחצי הימני — מחלק את הטווח בכל פעם:
low ← 1
high ← n
WHILE low <= high DO
MiddleIndex ← (low + high) DIV 2
IF A[MiddleIndex] = target THEN
RETURN MiddleIndex
ENDIF
IF A[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDWHILE
RETURN -1
מקרה גרוע O($\log_{2} n$) — עבור מיליון פריטים, כ-20 השוואות. מהיר משמעותית מחיפוש ליניארי על מערכים מסודרים גדולים, אך יש לסדר קודם לכן (עלות חד-פעמית של O($n \log n$)), מה ששווה את העדפה אם מבצעים חיפוש רבות.
„ציינו את התנאי הדרוש לחיפוש בינארי.” הנתונים חייבים להיות מסודרים (ממוינים בסדר עולה או יורד לפי המפתח שמחפשים). „תארו כיצד מבצעים חיפוש בינארי” (שלוש נקודות): (1) מצאו את הפריט האמצעי ברשימה (או בטווח הנוכחי) והשוו אותו לערך המבוקש; (2) אם יש התאמה, החיפוש מסתיים; אם הערך המבוקש קטן יותר, חזרו על הפעולה בחצי התחתון, ואם הוא גדול יותר, בחצי העליון; (3) המשיכו לחצות את הטווח עד שהפריט נמצא או שהטווח ריק, כלומר הפריט אינו קיים.
הגרסה של הבחינה, עם הגבולות ודגל, היא זו שיש לשחזר כאשר מבקשים להשלם את האלגוריתם:
DECLARE Lower, Upper, MiddleIndex : INTEGER
DECLARE Found : BOOLEAN
Lower ← 0
Upper ← 99
Found ← FALSE
WHILE Lower <= Upper AND NOT Found
MiddleIndex ← (Lower + Upper) DIV 2
IF Names[MiddleIndex] = Target THEN
Found ← TRUE
ELSE
IF Names[MiddleIndex] < Target THEN
Lower ← MiddleIndex + 1
ELSE
Upper ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
IF Found THEN
OUTPUT MiddleIndex
ELSE
OUTPUT "Not found"
ENDIF
דוגמה פתורה (מעקב אחר חיפוש בינארי). Names[0:9] מכיל את Ali, Ben, Cai, Dev, Eva, Fay, Gus, Hal, Ivy, Jo. עקבו אחר גרסת הבחינה עבור Target = "Ivy", ואז עבור Target = "Cat", וציינו את Lower, Upper ו-MiddleIndex בכל שלב.
עבור „אייבי”:
| גבול תחתון | גבול עליון | אינדקס אמצעי | שמות[אינדקס אמצעי] | תוצאה |
|---|---|---|---|---|
| 0 | 9 | 4 | אווה | אווה < אייבי, לכן גבול תחתון ← 5 |
| 5 | 9 | 7 | האל | האל < אייבי, לכן גבול תחתון ← 8 |
| 8 | 9 | 8 | אייבי | נמצא ← TRUE |
הפלט הוא 8, לאחר שלוש השוואות. עבור „קאט”: האמצע הוא 4 (אווה > קאט, גבול עליון ← 3); האמצע הוא 1 (בן < Cat, Lower ← 2); middle 2 (Cai < Cat, Lower ← 3); middle 3 (Dev > קאט, גבול עליון ← 2). כעת Lower (3) גדול מ-Upper (2), ולכן הלולאה מסתיימת ומוצג הפלט „לא נמצא” לאחר ארבע השוואות, המקרה הגרוע ביותר לעשרה פריטים ($\lceil\log_2 10\rceil = 4$). DIV מעגל כלפי מטה, ולכן האמצע של 0 ו-9 הוא 4, ולא 4.5 או 5. מחרוזות מושוות לפי סדר אלפביתי (קוד התווים).
„הסבירו כיצד הביצועים משתנים עם מספר הפריטים.” כל השוואה חוצה את מספר הפריטים שנותרו, ולכן מספר ההשוואות המרבי הוא בערך $\log_{2} n$: הכפלת גודל הרשימה מוסיפה השוואה אחת בלבד. זהו O($\log n$). „השוו בין חיפוש ליניארי לחיפוש בינארי”: חיפוש ליניארי דורש עד $n$ השוואות (O($n$)) ובממוצע מחצית מכך, אך פועל על נתונים לא ממוינים; חיפוש בינארי דורש לכל היותר $\log_{2} n$ השוואות (O($\log n$)) ומהיר בהרבה ברשימות גדולות, אך הנתונים חייבים להיות ממוינים תחילה ולאפשר גישה ישירה לפריט האמצעי (מערך, לא רשימה מקושרת). עבור $1000$ פריטים: $1000$ לעומת $10$ השוואות.


חיפוש ליניארי לעומת חיפוש בינארי
חפש ערך מסוים. חיפוש בינארי מחלק את הרשימה למחצה בכל שלב (רק על נתונים מסודרים); חיפוש ליניארי בודק אלמנט אחד אחר השני.
| English | עברית |
|---|---|
| insertion sort/ɪnˈsɜːʃn sɔːt/ | מיון הכנסה |
| bubble sort/ˈbʌbl sɔːt/ | מיון בועה |
| binary search/ˈbaɪnəri sɜːtʃ/ | חיפוש בינארי |
| array/əˈreɪ/ | מערך |
| linear search/ˈlɪnɪə sɜːtʃ/ | חיפוש ליניארי |
19.1
אלגוריתמי סידור
סידור בועות
מיון בועות עובר שוב ושוב על המערך ומחליף זוגות סמוכים שאינם בסדר הנכון, כך שהפריט הגדול ביותר „צף” לסוף בכל מעבר:
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
temp ← A[i]
A[i] ← A[i + 1]
A[i + 1] ← temp
swapped ← TRUE
ENDIF
NEXT i
IF swapped = FALSE THEN // already sorted
EXIT FOR
ENDIF
NEXT pass
מקרה מיטבי O($n$) (כבר מסודר, עם יציאה מוקדפת); ממוצע/גרוע O($n^{2}$). פשוט אך איטי עבור מערכים גדולים $n$.
סידור הזרקה
סידור הזרקה בונה קדמה מסודרת משמאל, ומזריק כל פריט חדש למקומו על ידי הזזה של ערכים גדולים יותר ימינה:
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j]
j ← j - 1
ENDWHILE
A[j + 1] ← key
NEXT i
מקרה מיטבי O($n$) (כבר מסודר); גרוע O($n^{2}$). טוב לערכים קטנים או קריב למערכת סידור. הוא מסדר בתוך המערך והוא יציב (שומר על סדר הפריטים השווים).
מעקב אחר סידור
משימה נפוצה היא להציג את המערך לאחר כל מעבר חיצוני. עבור [D, T, H, R] עם סינון הכנסה: מעבר 1 (מפתח T) ללא שינוי; מעבר 2 (מפתח H) → [D, H, T, R]; מעבר 3 (מפתח R) → [D, H, R, T].

אותו מערך נע אחרת במיון בועות: מעבר 1 משווה בין ד/ט (ללא החלפה), ט/ה (החלפה) ו-ט/ר (החלפה), ומתקבל [D, H, R, T] עם הפריט הגדול ביותר בסוף; במעבר 2 אין החלפות, ולכן הדגל עוצר את המיון. הציגו את המערך כולו אחרי כל מעבר, וספרו את ההשוואות אם התבקשתם: $3$ במעבר 1 ו-$2$ במעבר 2 (הגרסה שלעיל עוצרת מקום אחד מוקדם יותר בכל מעבר), $5$ בסך הכול.
כתיבת מיון מאפס. על השאלה „כתבו פסאודו-קוד למיון DataArray[1:1000] בסדר עולה” עונים באמצעות מיון בועות מלא עם דגל ליציאה מוקדמת, או מיון הכנסה, עם הצהרות והזחות; כל אחד מהם מזכה במלוא הנקודות אם הוא פועל לכל קלט:
DECLARE Pass, Index, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Pass ← 1
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO 1000 - Pass
IF DataArray[Index] > DataArray[Index + 1] THEN
Temp ← DataArray[Index]
DataArray[Index] ← DataArray[Index + 1]
DataArray[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Pass ← Pass + 1
UNTIL Swapped = FALSE OR Pass = 1000
לסדר יורד החליפו את > ב-<; כדי למיין רשומות או מערך 2-ממדי לפי שדה אחד, השוו את השדה הזה אך החליפו את הרשומה כולה (או כל עמודה). אם התבקשתם לכתוב מיון הכנסה „המבצע את אותה משימה” כמו מיון בועות נתון, שמרו על אותו שם מערך ואותו כיוון מיון ושחזרו את מיון ההכנסה שלעיל, עם השוואה הפוכה אם הסדר יורד.
„תארו שתי דרכים שבהן הנתונים משפיעים על ביצועי מיון” (שתי נקודות). (1) מספר הפריטים: מיון $O(n^{2})$ נמשך פי ארבעה כאשר מספר הפריטים מוכפל. (2) המידה שבה הנתונים כבר מסודרים: מיון בועות עם דגל או מיון הכנסה מסתיים במעבר אחד על נתונים שכבר ממוינים ($O(n)$), ומבצע את העבודה הרבה ביותר על נתונים בסדר הפוך; מספר ההחלפות תלוי במספר הזוגות שאינם בסדר. (מתקבלים גם: טווח הערכים או מספר הערכים הכפולים, והאם הפריטים הם רשומות גדולות שעלות העברתן גבוהה.) מיון בועות ומיון הכנסה הם שניהם O($n^{2}$) במקרים הגרוע והממוצע ו-O($n$) במקרה הטוב; מיון מהיר ומיון מיזוג הם O($n \log n$), ולכן משתמשים בהם לנתונים רבים.

[D, T, H, R], בה כל מפתח מוזז למקומו מעבר אחר מעברצפה בביצוע מיון
תנוע לאורך סידור והצפה איך העמודות מתכוננות לסדר — כיצד אלגוריתם מיון פועל צעד אחר צעד.
19.1
ADTs באלגוריתמים
טיפוסי הנתונים המופשטים מנושא 10 מופיעים באלגוריתמים רבים: מחסנית משמשת למעבר לעומק ולביטול פעולות; תור משמש למעבר לרוחב ולסידור הדפסות; רשימה מקושרת מאפשרת לנתונים לגדול ולהצטמצם.
ADTs יכולים לבנות מאחרים ADTs, לא רק ממערכים: תור מ-שני סטים; סט מרשימה מקושרת (push = הוספת ראש צומת); תור מרשימה מקושרת עם ראש וזנב מציינים; עץ בינארי מצומתים עם שני מצייני ילדים; מילון מאחסן זוגות מפתח→ערך (לרוב על טבלת hash). שכבה כזו מפרידה בין דאגות – האלגוריתם המשמש את ה-ADT אינו צריך לדעת איך הוא בנוי.
ה-ADTs שהמבחן מבקש לתאר ולממש
סט (אחרון נכנס, ראשון יוצא): פריטים מוסיפים (pushed) ומסירים (popped) באותו קצה, ה-עליון; מצביע TopOfStack אחראי על אינדקס הפריט העליון. ממומשם באמצעות מערך ומצביע אחד זה: push בודק שהסט אינו מלא, מגדיל את המצביע ואחסן את הפריט; pop בודק שהוא אינו ריק, מחזיר את הפריט העליון ומקטין את המצביע.
FUNCTION Push(Item : INTEGER) RETURNS BOOLEAN
IF TopOfStack = 9 THEN // full (array 0 to 9)
RETURN FALSE
ENDIF
TopOfStack ← TopOfStack + 1
StackData[TopOfStack] ← Item
RETURN TRUE
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
IF TopOfStack = -1 THEN // empty
RETURN -1
ENDIF
TopOfStack ← TopOfStack - 1
RETURN StackData[TopOfStack + 1]
ENDFUNCTION
תור (ראשון נכנס, ראשון יוצא): פריטים מצטרפים בסוף התור (הכנסה לתור) ויוצאים מראש התור (הוצאה מהתור); יש שני מצביעים ומונה. בתור ליניארי מצביע הראש מתקדם לאורך המערך עד שהמקום בתחילתו מתבזבז; תור מעגלי מחזיר את שני המצביעים לתחילת המערך באמצעות MOD, כך שכל תא משמש מחדש.

FUNCTION Enqueue(Item : STRING) RETURNS BOOLEAN
IF Count = 6 THEN // full
RETURN FALSE
ENDIF
Rear ← (Rear + 1) MOD 6
QueueArray[Rear] ← Item
Count ← Count + 1
RETURN TRUE
ENDFUNCTION
FUNCTION Dequeue() RETURNS STRING
IF Count = 0 THEN // empty
RETURN ""
ENDIF
DECLARE Item : STRING
Item ← QueueArray[Front]
Front ← (Front + 1) MOD 6
Count ← Count - 1
RETURN Item
ENDFUNCTION
רשימה מקושרת: רצף של צמתים, כל אחד מהם מחזיק פריט מידע וכיוון לצמת הבא; כיוון התחלה מצביע על הצמת הראשונה וכיוון ריק (0 או $-1$) מסמן את סוף הרשימה. ביישום באמצעות מערך, שני מערכים מקבילים מאחסנים את המידע והכיוונים, והתאים הלא משמשים מקושרים לרשימת תאים פנויים כך שההוסעה תדע איפה להציב את הצמת החדש.

FUNCTION FindInList(Target : STRING) RETURNS INTEGER // index, or 0 if absent
DECLARE Current : INTEGER
Current ← Start
WHILE Current <> 0
IF Data[Current] = Target THEN
RETURN Current
ENDIF
Current ← Pointer[Current]
ENDWHILE
RETURN 0
ENDFUNCTION
להוסיף הוספה לרשימה מסודרת: לקחת את התא הפנוי הראשון (NewNode ← FreeList, FreeList ← Pointer[FreeList]), לאחסן את הפריט, ואז לעבור על הרשימה עם כיווני Previous ו-Current עד למציאת Data[Current] > Item או לסוף; הגדר את Pointer[NewNode] ← Current ו-Pointer[Previous] ← NewNode (או Start ← NewNode אם זה צריך להיות ראש). עבור מחיקה, מסלול מחדש את הצמת הקודם כדי לדלג על הצמת הנמחק והחזר את התא לרשימת התאים הפנויים.
Binary tree: a root node, each node holding data, a left pointer to a subtree of smaller values and a right pointer to a subtree of larger values. Implemented as a 2D array (or three 1D arrays) Tree[Index, 0..2] for left pointer, data, right pointer, with a root pointer and a next-free pointer.
FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER // index, or -1
DECLARE Current : INTEGER
Current ← Root
WHILE Current <> -1
IF Tree[Current, 1] = Target THEN
RETURN Current
ENDIF
IF Target < Tree[Current, 1] THEN
Current ← Tree[Current, 0] // go left
ELSE
Current ← Tree[Current, 2] // go right
ENDIF
ENDWHILE
RETURN -1
ENDFUNCTION
להוסיף הוספה: אחסן את הפריט בצמת הפנוי הבא עם שני הכיוונים $-1$; אם העץ ריק, עשה אותו לשורש; אחרת, עבור מטה מהשורש, שמאל או ימין בהתבסס על השוואה, עד לכיוון שתעבור יהיה $-1$, והגדר כיוון זה לצמת החדש. ADT מתוך ADT אחר: קפיצה היא רשימה מקושרת שבה הדחה והוצאה עובדות בשורה הראשונה; תור הוא רשימה מקושרת עם כיוון התחלה וכיוון סוף; תור ניתן לבנות משתי קפיצות (הדח על אחת, הוצאה מהשנייה, העברת הכל למעבר כאשר השנייה ריקה); צמתי עץ בינארי הם רקעים או אובייקטים המקושרים בכיוונים, ולכן הוא בנוי ממבנה מקושר של צמתים. אמור אילו פעולות של ה-ADT החדש תואמות לפעולות של ה-ADT הישן.
האיור הראשון מציג עץ חיפוש בינארי: לכל צומת עד שני צומתי בן, ערכים קטנים מערך הצומת מופיעים משמאלו וערכים גדולים ממנו מימינו. האיור השני מציג את שלוש הדרכים למעבר על עץ.


| English | עברית |
|---|---|
| linked list/lɪŋkt lɪst/ | רשימה מקושרת |
| in place/ɪn pleɪs/ | במקום |
| stable/ˈsteɪbl/ | יציב |
| stack/stæk/ | סטק |
| queue/kjuː/ | תור |
| node/nəʊd/ | נודה |
| pointers/ˈpɔɪntəz/ | מצביעים |
| binary tree/ˈbaɪnəri triː/ | עץ בינארי |
| dictionary/ˈdɪkʃənəri/ | מילון |
| circular queue/ˈsɜːkjʊlə kjuː/ | תור סביבתי |
| free list/friː lɪst/ | רשימת פנויים |
| time complexity/taɪm kəmˈpleksɪti/ | מורכבות זמן |
| Big-O notation/bɪɡ əʊ nəʊˈteɪʃn/ | סמנציות Big-O |
| space complexity/speɪs kəmˈpleksɪti/ | מורכבות מרחב |
19.1
השוואת אלגוריתמים
מורכבות זמנית
מורכבות זמנית היא אופן הגדילת זמן הריצה בהתאם לגודל הקלט $n$, נכתב ב-סימון ביג-או O (האיבר הדומיננטי): O(1) קבוע, O($\log n$) חיפוש בינארי, O($n$) חיפוש ליניארי, O($n \log n$) מיון טוב, O($n^{2}$) מיון בועות/הכנסה. סדר קטן יותר עדיף בקנה מידה גדול, גם אם אלגוריתם אחר מהיר יותר עבור קלט קטן $n$.
כדי להמחיש זאת: כדי למיין מיליון פריטים, מיון $O(n \log n)$ יסתיים בשבר שנייה, בעוד שמיון $O(n^{2})$ עלול לקחת דקות.
דוגמה פתורה. רשימה מסודרת מכילה $1000$ פריטים. כמה השוואות צריך כל חיפוש במקרה הגרוע?
חיפוש ליניארי בודק פריטים אחד אחרי השני, ולכן עשוי לצרוך עד $1000$ השוואות — זהו $O(n)$. חיפוש בינארי חוצה את הרשימה למחצה בכל שלב, ולכן הוא צריך מקסימום $\lceil \log_2 1000 \rceil = 10$ השוואות — זהו $O(\log n)$. הכפלת הרשימה ל-$2000$ פריטים מוסיפה רק שוויה אחת לחיפוש הבינארי, אך עד עוד $1000$ לחיפוש הליניארי — והעובדה הזאת היא שהסדר הגדילה, ולא המהירות הגורסת, קובע את המנצח בקנה מידה גדול.
תיאור סדר גודל. O(1): הזמן קבוע, ללא תלות במספר הפריטים (הכנסה למחסנית, קריאת איבר במערך). O($\log n$): הזמן גדל לפי הלוגריתם של מספר הפריטים, ולכן הכפלת הנתונים מוסיפה רק צעד קבוע נוסף (חיפוש בינארי). O($n$): הזמן גדל ביחס ישר למספר הפריטים (חיפוש ליניארי, מעבר אחד ברשימה). O($n \log n$): מעט גרוע מליניארי (מיונים יעילים). O($n^{2}$): הזמן גדל לפי ריבוע מספר הפריטים, ולכן הכפלת הנתונים מגדילה את הזמן פי ארבעה (מיון בועות ומיון הכנסה). על „ציינו את סדר הגודל של חיפוש בינארי של Names[0:99]” עונים $O(\log n)$, ואת משמעותו מתארים כפי שמופיע לעיל; סדר גודל מודד כיצד הזמן או הזיכרון גדלים, ולא את הזמן בפועל.
דוגמה פתורה (סדר הגודל של קטע קוד). ציינו את סיבוכיות הזמן של כל קטע, כאשר n הוא מספר הפריטים.
// Fragment A
FOR i ← 1 TO n
FOR j ← 1 TO n
Total ← Total + Grid[i, j]
NEXT j
NEXT i
// Fragment B
Count ← 0
WHILE n > 1
n ← n DIV 2
Count ← Count + 1
ENDWHILE
// Fragment C
FOR i ← 1 TO n
Total ← Total + A[i]
NEXT i
FOR i ← 1 TO n
OUTPUT A[i] / Total
NEXT i
A הוא $O(n^{2})$: ההוראה הפנימית רצה $n$ פעמים בכל אחד מ-$n$ המעברים החיצוניים, ובסך הכול $n \times n$ פעמים. B הוא $O(\log n)$: $n$ נחצה בכל מעבר, ולכן הלולאה רצה בערך $\log_2 n$ פעמים (עבור $n = 64$, שישה מעברים). C הוא $O(n)$: שתי לולאות בזו אחר זו אורכות $n + n = 2n$ צעדים, ומשמיטים קבועים. הכלל: לולאות מקוננות מכפילים, לולאות ברצף מחברים, ומשאירים רק את האיבר שגדל במהירות הרבה ביותר, ולכן $3n^{2} + 5n + 2$ הוא $O(n^{2})$.


מורכבות מרחב
מורכבות מרחב היא הזיכרון הנוסף הנדרש. מיון בועות ומיון הכנסה משתמשים ב-O(1) נוסף (מיקום); מיון מיזוג משתמש ב-O($n$); רקורסיה משתמשת בזיכרון ערימה פרופורציונלי לעומק שלה. לעיתים קרובות יש קונטרסט בין זמן לזיכרון.
קריטריונים אחרים
פשטות (קל יותר לתכנן ולתחזק), יציבות, ואדפטביות (מהיר יותר על נתונים כמעט מסודרים). האלגוריתם המתאים תלוי בנתונים ובמגבלות.
כיצד זמן הרצה גדל עם גודל n
הזזו את ציר ה-n כלפי מעלה והשוו בין העקומות: O(1) ו-O(log n) נשארים כמעט שטוחים, O(n) עולה באופן רציף, ו-O(n²) מתפוצץ. זוהי הסיבה לכך ש-Big-O — ולא סופר זמן בפועל — הוא הכלי להשוואת אלגוריתמים על קלט גדול.
גדילת Big-O
שנה את גודל הקלט n והשווה איזה מהאלגוריתמים גדלים מהר יותר — הרעיון מאחורי מורכבות זמן.
19.2
רקורסיה
סיילבוס
| המועמדים צריכים להיות מסוגלים: | הערות והנחיות |
|---|---|
| להראות הבנה של רקורסיה | תכונות חיוניות של רקורסיה. איך רקורסיה מבטאת בשפת תכנות. כתוב ועקוב אחרי אלגוריתמים רקורסיביים. מתי שימוש ב-רקורסיה הוא יועיל |
| להראות מודעות למה שמחייב עשות מחשב צ'יפ (compil er) כדי לתרגם רקורסיבי קוד תכנות | שימוש ב-stacks ו-unwinding |
מקור: הסיילבוס הבינלאומי של קמבריד'ג'
![ארבעת קופסאות הקריאה, כל אחת מוזזת ימינה מהקודמת: total([4, 7, 2]) = 4 + total([7, 2]); total([7, 2]) = 7 + total([2]); total([2]) = 2 + total([]); total([]) = 0 הוא המקרה הבסיס. הערכים חוזרים כלפי מעלה: 2, ולאחר מכן 9, ולאחר מכן 13](/handout-media/a_level_computer_science/assets/19-recursion.png?v=1794647943)
אלגוריתמי רקורסיה משתמשים ברקורסיה: הפונקציה קוראת לעצמה עם גרסה קטנה יותר מאותו בעיה, עד שמקרה בסיס מפסיק את השרשרת. יש שני חלקים: המקרה הבסיסי (קטן מספיק לפתרון ישיר — בלעדיו הרקורסיה לעולם לא תפסיק) והמקרה הרקורסיבי (צמצום הקלט וקריאה לעצמה).
פקטוריאל:
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1
ELSE
RETURN n * Factorial(n - 1)
ENDIF
ENDFUNCTION
חזרה (Recursion) היא טבעית לבעיות בעלות תכונה של חזר-עצמי: עצים, פירוק-ו-כיבוש (חיפוש בינארי, מייף סדר), ומבני נתונים מקושרים. כאשר זו אינה מתאימה, לולאה (Loop) היא בדרך כלל נקייה יותר.
„תארו למה הכוונה ברקורסיה” (שתי נקודות). פונקציה או פרוצדורה המוגדרת באמצעות עצמה: היא קוראת לעצמה מתוך גופה, בכל פעם עם גרסה קטנה יותר של הבעיה, עד שמגיעים למקרה בסיס. „ציינו שלושה מאפיינים חיוניים של רקורסיה”: (1) מקרה בסיס (תנאי עצירה) שמחזיר ערך ללא קריאה נוספת; (2) מקרה כללי שבו השגרה קוראת לעצמה; (3) כל קריאה מקרבת את הבעיה למקרה הבסיס (הפרמטר קטן), כך שהרקורסיה מסתיימת. בחלק מהמחוונים מוסיפים: הערכים מוחזרים כשהקריאות מסתיימות בסדר הפוך.
„תארו מתי השימוש ברקורסיה מועיל ותנו דוגמה.” כאשר הבעיה מוגדרת באופן טבעי באמצעות גרסאות קטנות יותר של עצמה, כך שהפתרון הרקורסיבי קצר וברור יותר וקרוב יותר להגדרה המתמטית מפתרון באמצעות לולאה: עצרת או מספר פיבונאצ׳י, חיפוש בינארי, מעבר על עץ בינארי, מיון מיזוג או מיון מהיר, ועיבוד מבנים מקוננים כגון תיקיות בתוך תיקיות. זו בחירה גרועה כאשר העומק גדול (המחסנית עלולה לגלוש) או כאשר אותה תת-בעיה מחושבת פעמים רבות (חישוב פיבונאצ׳י נאיבי).
מעקב אחר קריאה רקורסיבית
עבור Factorial(4): הקריאות יורדות לFactorial(1)=1, ואז הפריקה כופלת חזרה כלפי מעלה: 2*1=2, 3*2=6, 4*6=24. התוצאה הסופית 24. יש לעקוב אחר כל קריאה תלויה על גבי סטק.
דוגמה מפורטת. הפונקציה להלן נתונה ללא הסבר. בצע מעקב עבור Unknown(3, 5) ופרט את הפלט והערך ההחזרתי שלה.
FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
IF X < Y THEN
OUTPUT X + Y
RETURN Unknown(X + 1, Y - 1) + 1
ELSE
RETURN 0
ENDIF
ENDFUNCTION
קריאה 1: $X = 3, Y = 5$: $3 < 5$, פלט 8, קריאה Unknown(4, 4). קריאה 2: $4 < 4$ הוא שגוי, החזר 0. הפריקה: קריאה 1 מחזירה $0 + 1 = 1$. פלט 8, ערך החזרה 1. כתוב את המעקב בטבלה עם שורה לכל קריאה (פרמטרים, תנאי, פלט, מה שהיא מחזירה), ובצע את ההחזרות מהקריאה העמוקה כלפי מעלה: זוהי הפריקה שהפתרון מצפה לה.
דוגמה מפורטת (פיבונאצי). Fib(n) מחזירה n כאשר n < 2, אחרת Fib(n - 1) + Fib(n - 2). מצא Fib(5).
Fib(5) = Fib(4) + Fib(3); Fib(4) = Fib(3) + Fib(2); Fib(3) = Fib(2) + Fib(1); Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. לכן Fib(3) = 1 + 1 = 2, Fib(4) = 2 + 1 = 3, Fib(5) = 3 + 2 = 5. מקרה הבסיס מושג רבות (Fib(2) מחושב שלוש פעמים), והסיבה לכך שהגרסה הזו איטית היא she makes 15 קריאות עבור $n = 5$ וכמעט משנה למעלה את מספר הקריאות בכל עלייה ב$n$.
המרת חזרה לאיטרציה. כל פונקציה רקורסיבית ניתנת לכתיבה מחדש באמצעות לולאה, המשמשת זיכרון פחות ומהירה יותר: שמור על תוצאה צוברית וסרק מנקודת הבסיס כלפי מעלה. פקטוריאל כלולאה:
FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
DECLARE Result, Count : INTEGER
Result ← 1
FOR Count ← 2 TO N
Result ← Result * Count
NEXT Count
RETURN Result
ENDFUNCTION
כאשר מבקשים לשנות מיון השחצה רקורסיבי או חיפוש לאלגוריתם איטרטיבי, החלף את הקריאה לעצמה בלולאה על האינדקס שעליו הייתה הרקורסיה הולכת, והמיר את המקרה הבסיסי לתנאי יציאה של הלולאה.

סיכונים
- חזרה אינסופית אם המקרה הבסיסי מופסד — קריסה עם התמלאות סטק (Stack Overflow).
- צריכת זיכרון גבוהה לחזרה עמוקה.
- איטיות אם היא חוזרת על עבודה (פיבונאצי פשוט הוא אקספוננצי — יש להשתמש בלולאה או ממוניזציה (Memoisation)).
ריקורסיה מתפרקת מהעלים כלפי מעלה
עבור את fib(4) בסדר שבו הקריאות למעשה נגמרות: העלים (מקרים בסיסיים) נפתרים תחילה, ולאחר מכן כל אב משלב את הילדים שלו. שים לב ש-fib(2) מחושב פעמיים — העבודה המוחזרת הזו היא הסיבה שהריקורסיה פשוטה איטית.
| English | עברית |
|---|---|
| recursion/rɪˈkɜːʃn/ | רקורסיה |
| factorial/fækˈtɔːrɪəl/ | פאקטוריאל |
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | פרק-שלווה |
| general case/ˈdʒenərəl keɪs/ | מקרה כללי |
| parameters/pəˈræmɪtəz/ | פרמטרים |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | שפע ערימה |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | ממוחזור |
| local variables/ˈləʊkl ˈveərɪəblz/ | משתנים מקומיים |
| stack frame/stæk freɪm/ | מסגרת ערימה |
| return address/rɪˈtɜːn əˈdres/ | כתובת חזרה |
19.2
מה המעבד עושה לקוד רקורסיבי
חזרה דורשת לקריאה כלשהי להיות לה עותק משלה של הפרמטרים והמשתנים המקומיים. המעבד שומר אותם על סטק הקריאות. עבור כל קריאה הוא דוחף מסגרת סטק המכילה את הפרמטרים, המשתנים המקומיים, ואת כתובת ההחזרה (איפה להמשיך בקורא). כאשר הפונקציה מחזירה, ערך ההחזרה מועבר, המסגרת נשלפת, והשליטה ממשיכה בכתובת ההחזרה.

מכיוון שלכל קריאה מסגרת משלה, קריאות רקורסיביות אינן דורסות זו את המשתנים של זו. המחסנית עלולה לגדול מאוד ברקורסיה עמוקה, ולכן רקורסיה עמוקה מאוד עלולה לגרום לגלישתה. זהו אותו מנגנון קריאה וחזרה המשמש לקריאות רגילות שאינן רקורסיביות — אין „מנגנון רקורסיה” מיוחד.
„הסבירו מדוע מחסנית מתאימה למימוש רקורסיה” (שלוש נקודות). כל קריאה רקורסיבית חייבת לשמור את כתובת החזרה, את הפרמטרים ואת המשתנים המקומיים שלה, והקריאות מסתיימות בסדר הפוך לסדר שבו בוצעו (הקריאה האחרונה היא הראשונה להסתיים). זוהי בדיוק התנהגות אחרון נכנס, ראשון יוצא של מחסנית: כל קריאה חדשה דוחפת מסגרת למחסנית, וכל חזרה שולפת את המסגרת האחרונה, משחזרת את מצב השגרה הקוראת ומציינת היכן להמשיך. זו משימת המהדר כשהוא מתרגם קוד רקורסיבי: הוא יוצר דחיפה של מסגרת מחסנית בכל קריאה ושליפה בכל חזרה, והמסגרות נשלפות בסדר הפוך עם החזרת התוצאות.
| English | עברית |
|---|---|
| call stack/kɔːl stæk/ | ערימת קריאות |
| base case/beɪs keɪs/ | מקרה בסיסי |
| recursive case/rɪˈkɜːsɪv keɪs/ | מקרה רקורסיבי |
19.2
הגדרות מקובלות בקורס
שאלת הגדרה מוקדמת לפי טקסט קבוע. לימודן במדויק, ותן תשובה אחת בלבד.
| מונח | הגדרה |
|---|---|
| חיפוש ליניארי | בדיקה של כל פריט ברצף מהתחלה עד שמצאים את המטרה או מגיעים לסוף |
| חיפוש בינארי | השוואה חוזרת של המטרה לפריט האמצעי של רשימה מסודרת והשלכה של המחצית שאינה יכולה להכילה |
| בסייסון בועה | מעבר חוזר הרצף, החלפת פריטים שכנים הנמצאים בסדר שגוי, עד שמעבר אחד לא מבצע החלפות |
| בסייסון הכנסה | לקיחת כל פריט ברצף והכנסתו למקומו הנכון בקרב הפריטים שמסודרים כבר |
| abstract data type | a collection of data and the operations that can be performed on it, defined independently of how it is stored |
| ערימה | מבנה אחרון נכנס, ראשון יוצא עם דחיפה והורדה בחלק העליון |
| תור | מבנה ראשון נכנס, ראשון יוצא עם הוספת פריטים באחור והסרתם מקדמה |
| רשימה מקושרת | רצף של צמתים, כל אחד מכיל נתונים ושקע לצומת הבא, עם שקע התחלה |
| עץ דו-סעיפי | צמתים המכילים נתונים ושקעים לענף שמאלי של ערכים קטנים וענף ימני של ערכים גדולים |
| סימון Big O | דרך למיון זמן (או זיכרון) שאלגוריתם זקוק לו על פי גודל הגידול שלו עם גודל הקלט |
| רקורסיה | פונקציה הקוראת לעצמה עם גרסה קטנה יותר של הבעיה עד שמקרה בסיס מפסיק את הקריאות |
| מקרה בסיס | התנאי שבו פונקציה רקורסיבית חוזרת ללא קריאה לעצמה |
| פירוק | החזרת ערכי שרשרת של קריאות רקורסיביות, מהקריאה העמוקה ביותר חזרה לקריאה הראשונה, כאשר מסגרות הסטק נמחקים |
19.2
טיפים לבחינות
- חיפוש: ליניארי אינו דורש סדר ו-O($n$); בינארי דורש מיון ומחלק למחצית בכל פעילה והוא O($\log n$). יש לדעת את שני האלגוריתמים בעל-כח, כולל הגבולות והדגל.
- מיונים: בועה עם דגל לשינוי, הזרעה עם מקדיש שמזיז פריטים גדולים ימינה; שניהם O($n^{2}$) בחמורה, O($n$) על נתונים ממוינים. הביצועים תלויים במספר הפריטים ובמידת המיון שלהם.
- מימוש ADT הוא טיפול באמצעיות: מצביע על הקצה; קדמה, אחורה וספירה עם MOD; התחלה, מצביעים ורשימת חופשיים; שורש עם מצביעים שמאלה וימינה. תמיד לבדוק אם המבנה מלא או ריק.
- סדר גודל עוסק בקצב הגידול: קבוע, לוגריתמי, ליניארי, ריבועי. בחיפוש בינארי ציינו כי „הכפלת הנתונים מוסיפה השוואה אחת”.
- רקורסיה: מקרה בסיס, מקרה כללי, התקדמות לעבר המקרה הבסיס; מועיל כאשר הבעיה מוגדרת בתלות עצמה; סטק מחזיק כתובות החזרה ומשתנים מכיוון שהקריאות חוזרות בסדר הפוך. מעקב מתבצע בטבלה ופירוק מתחיל מהקריאה העמוקה ביותר.
טעויות נפוצות
- כתיבת $O(2n)$ או $O(n^{2} + n)$: השמיטו קבועים ואיברים קטנים יותר, וכך תקבלו $O(n)$ ו-$O(n^{2})$.
- חישוב האינדקס האמצעי כ-$(Lower + Upper) / 2$ במעקב: גרסת הבחינה משתמשת ב-
DIV, לכן עגלו כלפי מטה. - שימוש בחיפוש בינארי על נתונים לא ממוינים, או ברשימה מקושרת; וגם הגדרת
Lower ← MiddleIndexבמקוםMiddleIndex + 1, שיצור לופ אינסופי. - לולאת פנימית של מיון בועות המרצת עד סוף המערך בכל מעבר, או החלפה ללא משתנה זמנית.
- הזרקה (push) או הכנסה לתור (enqueue) שאינה בודקת אם המבנה מלא, או פריקה (pop) או יציאה מתור (dequeue) שאינה בודקת אם הוא ריק.
- הזזת איחורי החזית (front pointer) של התור ללא שימוש בפונקציית MOD בתור מעגלי, או התייחסות לכך ש- front = rear תמיד משמעותו ריק.
- הכנסה לרשימה מקושרת על ידי הזזת תוכן המערך; רק השערים (pointers) משתנים.
- פונקציה רקורסיבית ללא מקרה בסיס, או אחת שהקריאה הרקורסיבית שלה לא מקטינה את הבעיה.
- מעקב אחר קריאה רקורסיבית אך שכחת להוסיף את העבודה המתוקפלת בעת החזרה למעלה.
- תשובה לשאלה „למה מחסנית” בנימוק „מפני שהיא מהירה”; הסיבה היא סדר החזרה של אחרון נכנס, ראשון יוצא.
שיעורים אינטראקטיביים בנושא זה
לעבור על הדברים צעד אחר צעד, עם תרגילים לבדיקה מיידית.