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

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

דוגמאות: מיון ערימה, מיון בועות.

דוגמאות

נגדיר מערך '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\left(\begin{array}{c}\frac{n}{2}\end{array}\right)$. כך שיוצא שהפונקציה השנייה יעילה במקצת בסיבוכיות.

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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