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

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

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

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

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

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

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

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