אלגוריתם תוך-מקומי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

דוגמאות[עריכת קוד מקור | עריכה]

נגדיר מערך 'a' באורך 'n' .

עכשיו, נגדיר פונקציה בשם reverse שתחזיר את המערך בצורה ההפוכה.

למשל:

אם הפונקציה תקבל את המערך [1,2,3] היא תחזיר [3,2,1]

עכשיו נציג שתי דרכים לעשות זאת:


שיטת אלגוריתם חוץ-מקומי:

function reverse(a[0..n - 1])
     allocate b[0..n - 1]
     for i from 0 to n - 1
         b[n − 1 − i] := a[i]
     return b

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


שיטת אלגוריתם תוך-מקומי:

 function reverse_in_place(a[0..n])
     for i from 0 to floor(n/2)
         tmp := a[i]
         a[i] := a[n − 1 − i]
         a[n − 1 − i] := tmp

כפי שניתן לראות האלגוריתם השני (אלגוריתם תוך-מקומי יעיל בהרבה, מבחינת ניצול הזיכרון. מבחינת סיבוכיות ריצה ללא הפיכה לO(n) ניתן לראות שהפונקציה הראשונה תהיה O(2n) והשנייה O\begin{pmatrix}{n\over 2}\end{pmatrix}. כך שיוצא שהפונקציה השנייה יעילה במקצת בסיבוכיות.

P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.