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

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

דוגמאות

נגדיר מערך '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}}$. כך שיוצא שהפונקציה השנייה יעילה במקצת בסיבוכיות.

קישורים חיצוניים

מדיה וקבצים בנושא אלגוריתם תוך-מקומי בוויקישיתוף

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