אלגוריתם אין פלייס

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

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

דוגמאות

נגדיר מערך '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

אלגוריתם אין פלייס43471103Q657037