בחישוב סיבוכיות הזמן, מה שיעניין אותנו איננו מספר הפעולות אלא המדד לקצב הגידול בעבודה הנדרשת כפונקציה של n.
סדר גודל קבוע - (1)O
כאשר מספר הפעולות שמתבצעות לא משתנה כאשר n משתנה, נוכל לסכם ולומר שמדד סיבוכיות הזמן הוא (1)O. בדוגמת הקוד שלהלן, סיבוכיות הזמן היא (1)O. האלגוריתם להלן מבצע 10 פעולות. שינוי בגודל המערך שאל תוך הפרמטר numbers נכנס ה-reference שלו לא ישנה את מספר הפעולות שהאלגוריתם להלן מבצע.
public void f(int[] numbers) {
for(int i=0; i<10; i++) {
System.out.println("hello");
}
}
סדר גודל קבוע - (n)O
כאשר מספר הפעולות שמתבצעות משתנה ביחס ישר ל-n אז נאמר שסיבוכיות הזמן היא (n)O. בדוגמת הקוד להלן, סיבוכיות הזמן O(n). גידול ב-n (גודל המערך שה-reference שלו נשלח כארגומנט לפונקציה) יגרום לגידול ביחס ישר (בקירוב) במספר הפעולות. הפעולות הקבועות שמתבצעות לפני הלולאה ואחריה אינן משמעותיות בקביעת סיבוכיות זמן הריצה.
public void f(int[] numbers) {
System.out.println("before...");
for(int i=0; i<numbers.length; i++) {
System.out.println(numbers[i]);
}
System.out.println("after...");
}
גם כאשר מספר הפעולות שמתבצעות משתנה ביחס ישר ל-n, והיחס שבו מדובר גדול מ-1, גם אז נאמר שסיבוכיות הזמן היא (n)O. בדוגמא הבא סיבוכיות הזמן היא (n)O, וזאת למרות שכל גידול ב-n יגרום לכך שהגידול במספר הפעולות יהיה פי 20 (לדוגמא: כאשר n הוא 10 אז מספר הפעולות הוא 200, וכאשר n הוא 11 אז מספר הפעולות הוא 220ֿֿ. כלומר, גידול של n ב-1 הביא לגידול של מספר הפעולות ב-20). הסיבוכיות (n)O מתאימה יותר מ- (2^n)O לתיאור האלגוריתם. כאשר מדובר בסיבוכיות (n^2)O גידול של 1000 ב-n צפוי להוביל לגידול של 1000000 במספר הפעולות. כאשר מדובר באלגוריתם לעיל, גידול של 1000 ב-n יוביל לגידול של 20000 במספר הפעולות. משמעותית פחות מ-1000000.
public void f(int[] numbers) {
System.out.println("before...");
for(int i=0; i<numbers.length; i++) {
for(int j=0; j<20; j++) {
System.out.println(numbers[i]);
}
}
System.out.println("after...");
}
סדר גודל לוגריתמי - (log n)O
כאשר n גדל מ-n1 ל-n2 ומספר הפעולות גדל ב-log (n2/n1) (לפי בסיס מסויים וקבוע) נוכל לומר שסיבוכיות הזמן היא O(log n). אחת הדוגמאות השכיחות לסיבוכיות זו היא האלגוריתם לחיפוש בינארי. אם גודל המערך הממויין שבו מתבצע החיפוש יגדל פי 8 מספר הפעולות יגדל ב-3, הערך של log 8 לפי בסיס 2. בדוגמת הקוד הבאה סיבוכיות הזמן היא log n לפי בסיס 2.
public static int findMissingIndex(int []a) {
int delta = 0;
int d1 = a[2]-a[1];
int d2 = a[1]-a[0];
if(d1==d2) {
delta = d1;
} else {
if(d1<d2) {
delta = d1;
} else {
delta = d2;
}
}
int hi = a.length-1;
int low = 0;
while(low<=hi) {
int mid = (low+hi)/2;
if(mid>0 && a[mid]-a[mid-1]>delta) {
return mid;
}
else {
int expectedElementAtHigh = a[mid] + delta*(hi-mid);
if(a[hi]==expectedElementAtHigh) {
hi = mid-1;;
} else {
low = mid+1;
}
}
}
return a.length;
}
פוסט זה נכתב על מנת לסייע לסטודנטים בלימוד הנושא סיבוכיות. הפוסט צפוי להתעדכן ונושאים נוספים צפויים להתווסף.
