למחשב יש שני משאבים חשובים עיקריים. משאב הזמן ומשאב הזיכרון. כאשר תכנית מחשב רצה היא צורכת זיכרון. מדד סיבוכיות המקום מתייחס לשאלה כמה זיכרון האלגוריתם צורך.
הגדרת המושג ׳סיבוכיות מקום׳
סיבוכיות המקום מהווה מדד לכמות הזיכרון שנצרך. סיבוכיות המקום היא סדר הגודל של מספר תאי הזיכרון שמנצל האלגוריתם בזמן ריצתו.
דוגמא לאלגוריתם עם סיבוכיות מקום קבועה - O(1)
בדוגמת הקוד שלהלן, נעשה שימוש בשני משתנים בלבד. המשתנים i ו-n. מספר המשתנים בדוגמת הקוד שלהלן לא משתנה. מספר המשתנים נותר קבוע ללא קשר לערך של n, ולכן, בדוגמת הקוד שלהלן סיבוכיות המקום היא O(1).
בכל הנוגע לסיבוכיות הזמן, כיוון שמספר הפעולות הוא גם ערכו של המשתנה n נוכל לומר שככל ש-n יותר גדול, גם מספר הפעולות יהיה יותר גדול, וכיוון שמדובר ביחס ישר, סיבוכיות הזמן היא O(n).
int i,n;
for(i=0;i<n;i++) {
System.out.println(i);
}
בשפת התכנות Java כל מערך מיוצג באמצעות אובייקט. כאשר מגדירים פונקציה שמקבלת reference לאובייקט אשר מייצג מערך (כפי שניתן לראות בדוגמת הקוד שלהלן), סיבוכיות המקום לא תושפע מגודלו של המערך. בדוגמת הקוד שלהלן, סיבוכיום המקום תהיה קבועה, O(1). בדוגמת הקוד שלהלן, מספר המשתנים נותר תמיד 2 (המשתנים הם numbers ו-i). המערך שה-reference שלו נשלח לפונקציה total נוצר במקום אחר. הזיכרון שמשמש אותו לא יילקח בחשבון כאשר נחשב את מדד סיבוכיות המקום של הפונקציה שלהלן.
public void total(int[] numbers) {
int i,n;
for(i=0;i<numbers.size;i++) {
System.out.println(numbers[i]);
}
}
דוגמא לאלגוריתם עם סיבוכיות מקום ליניארית - O(n)
בדוגמת הקוד שלהלן, גודל המערך שיוגדר הוא size. ככל שערכו של size יהיה יותר גדול כך גם גודלו של המערך. גודלו של המערך יגדל ביחס ישר לערכו של size, ולכן נוכל לומר שבדוגמת הקוד שלהלן סיבוכיות המקום היא ליניארית, ונתאר אותה באמצעות O(n).
int size;
int numbers[] = new int[size];
פוסט זה יעודכן בחלוף הזמן בהסברים ובדוגמאות נוספות בנושא סיבוכיות מקום. המטרה בכתיבת פוסט זה היא לפשט ככל האפשר את הנושא על מנת לאפשר לסטודנטים רבים ככל האפשר להבינו באופן מלא ומסודר.
