דלג לתוכן

חשיבה חישובית ופתיחת בעיות

מדעי המחשב A-Level · נושא 19

שיעור וידאו לנושא זה פתח את עמוד הוידאו
15:32

חיפוש ומיון

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

קריינות באנגלית · כתוביות באנגלית ובסינית 中文 שאפשר להחליף ביניהן

19.1

אלגוריתמי חיפוש

סיילבוס
המועמדים צריכים להיות מסוגלים: הערות והנחיות
להראות הבנה של 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 כדי לציין מורכבות זמן ומרחב

מקור: הסיילבוס הבינלאומי של קמבריד'ג'

Big O: כיצד אלגוריתמים מתרחבים
סינון הכנסה: החלקת כל כרטיס למקומו
מיון בועות, מעבר אחר מעבר
חיפוש בינארי: חלוקה לשתיים וכיבוש

חיפוש מוצא ערך מבוקש באוסף (לעיתים קרובות מערך) ומחזיר את מיקומו, או „לא נמצא”.

מדריך טלפונים פתוח
חיפוש ברשימה מסודרת, כמו מדריך טלפונים, מהיר משמעותית מבדיקה של כל פנייה בנפרד

חיפוש ליניארי

חיפוש ליני עובר מהתחלה לסוף, ומשווה כל אלמנט למטרה:

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 ושומרת על האינדקס. הנקודות הן עבור הלולאה על כל אלמנט, ההשוואה, והמה שמוחזר כאשר הערך לא קיים.

שורה של תאים באלפבית A עד Z; תאים A עד V מצופים כבדוקים, ו-W מודגש כתוצאה, עם מחוון מתחת ל-W
חיפוש ליניארי בודק כל אות בתור — 23 השוואות כדי למצוא W

חיפוש בינארי

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

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$ השוואות.

שלוש שורות המראות חיפוש בינארי על האלפבית המסודר; הטווח הפעיל מאופי/גבוה נחצף בכל צעד כאשר האות המרכזית M, אחר כך T, ואחר כך W מושוואות ל-W
חיפוש בינארי חוצה את הטווח בכל צעד (נמוך / אמצע / גבוה) — רק 3 השוואות כדי למצוא את W
קטלוג כרטיסים בספרייה: קיר של מגירות עץ קטנות, אחת נשלפת לחוץ כדי להציג את הכרטיסים המסודרים
קטלוג כרטיסים: רשומות מסודרות הן מה שמאפשר חיפוש בינארי — חצו, בדקו, חצו שוב
חקור

חיפוש ליניארי לעומת חיפוש בינארי

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

מילון מונחים אימון
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].

Snapshot of insertion sort
מיון השחלה במערך נתוני הקורס: כל שורה היא השחלה אחת; הקידמה המוצללת כבר מסודרת

אותו מערך נע אחרת במיון בועות: מעבר 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 בשלושה מעברים; הקידמה הממוינת מצופה וחצים מראים כל אלמנט גדול יותר הזז ימינה כדי לאפשר למפתח לרדת למקומו
מיון הכנסה של [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, כך שכל תא משמש מחדש.

תור מעגלי של שש תאי מערך המכילים שלושה פריטים בתאי 3 עד 5, עם מצביע קדמי ב3 ואחורי ב5, וחץ מקווקע המראה שהפריט הבא יעוטף לתוך תא 0
תור מעגלי: מצייני האחורי והקדמי צועדים קדימה עם 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$) מסמן את סוף הרשימה. ביישום באמצעות מערך, שני מערכים מקבילים מאחסנים את המידע והכיוונים, והתאים הלא משמשים מקושרים לרשימת תאים פנויים כך שההוסעה תדע איפה להציב את הצמת החדש.

Two parallel arrays Data and Pointer implementing a linked list of the names Ann, Ben and Dan: the start pointer is 1, the pointers chain 1 to 3 to 2 to 0, and the unused cells 4, 5 and 6 form the free list
רשימה מקושרת בשני מערכים: הסדר של הרשימה נקבע בכיוונים ולא במיקומיהם; הוסעת שם דורשת לקחת תא מרשימת התאים הפנויים ולמסלול מחדש שני כיוונים
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 הישן.

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

עץ חיפוש בינארי ששורשו 27, תת-העץ השמאלי שלו כולל את 19, 16, 21 ו-17, ותת-העץ הימני שלו כולל את 36, 30, 55 ו-89, עם סימון השורש, המצביעים שמאלה וימינה וצומת עלה
עץ חיפוש בינארי: לכל צומת עד שני צומתי בן
עץ חיפוש דו-סעיפי עם שורש 4 (ענף שמאלי המורכב מ2, 1 ו3, ענף ימני המורכב מ6, 5 ו7); בביקור קדמי נבקר 4 2 1 3 6 5 7, בביקור פנימי נבקר 1 2 3 4 5 6 7 (בסדר ערכים), ובביקור אחורי נבקר 1 3 2 5 7 6 4
שלושה סוגי ביקור בעומק לעץ דו-סעיפי: ביקור קדמי, ביקור פנימי (בסדר ערכים) וביקור אחורי
מילון מונחים אימון
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})$.

גרף של זמן ריצה כנגד גודל הקלט n עבור הסדרים הנפוצים: O(1) ו-O(log n) נשארים כמעט שטוחים, O(n) עולה בעדינות, O(n log n) בחוד יותר, ו-O(ריבוע n) עולה במהירות הגדולה ביותר
השוואת סדרי הגודל הנפוצים: סדר קטן יותר מנצח בקנה מידה גדול
גרף קווי של זמן ביצוע כנגד מספר האלמנטים n: בסייסון בועה ובסייסון הכנסה עולים בתלול כ-O(n squared), בעוד שסייסון מהיר נשאר נמוך כ-O(n log n)
איך זמן המיון גדל בהתאם למספר האלמנטים $n$: מיונים $O(n^2)$ מתרחקים ממיון $O(n\log n)$

מורכבות מרחב

מורכבות מרחב היא הזיכרון הנוסף הנדרש. מיון בועות ומיון הכנסה משתמשים ב-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
הקריאות יורדות למקרה הבסיס; התוצאות חוזרות כלפי מעלה

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

פקטוריאל:

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

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

סטק הקריאות עבור Factorial(4): כל קריאה דוחפת מסגרת כלפי מטה עד למקרה הבסיסי Factorial(1)=1, ואז הסטק מתפרק, מחזיר 2 = 2 כפול 1, 6 = 3 כפול 2 ו-24 = 4 כפול 6
החזרה משתמשת בסטק הקריאות: קריאות דוחפות מסגרות כלפי מטה למקרה הבסיסי, ולאחר מכן ההחזרות מתפרקות כלפי מעלה

סיכונים

  • חזרה אינסופית אם המקרה הבסיסי מופסד — קריסה עם התמלאות סטק (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

מה המעבד עושה לקוד רקורסיבי

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

מערך קריאות עבור factorial(3): כל קריאה מחכה, ולאחר מכן מחזירה ערך בסדר הפוך
מערך קריאות עבור factorial(3): כל קריאה מחכה, ולאחר מכן מחזירה ערך בסדר הפוך

מכיוון שלכל קריאה מסגרת משלה, קריאות רקורסיביות אינן דורסות זו את המשתנים של זו. המחסנית עלולה לגדול מאוד ברקורסיה עמוקה, ולכן רקורסיה עמוקה מאוד עלולה לגרום לגלישתה. זהו אותו מנגנון קריאה וחזרה המשמש לקריאות רגילות שאינן רקורסיביות — אין „מנגנון רקורסיה” מיוחד.

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

מילון מונחים אימון
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) משתנים.
  • פונקציה רקורסיבית ללא מקרה בסיס, או אחת שהקריאה הרקורסיבית שלה לא מקטינה את הבעיה.
  • מעקב אחר קריאה רקורסיבית אך שכחת להוסיף את העבודה המתוקפלת בעת החזרה למעלה.
  • תשובה לשאלה „למה מחסנית” בנימוק „מפני שהיא מהירה”; הסיבה היא סדר החזרה של אחרון נכנס, ראשון יוצא.

שיעורים אינטראקטיביים בנושא זה

לעבור על הדברים צעד אחר צעד, עם תרגילים לבדיקה מיידית.

מבחני עבר

נושאים נוספים במדעי המחשב A-Level

היכנס או צור חשבון

IGCSE, A-Level & AP