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

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

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

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

דוגמאות עריכה

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

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

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