סיבוכיות של זמן

בחישוב סיבוכיות הזמן, מה שיעניין אותנו איננו מספר הפעולות אלא המדד לקצב הגידול בעבודה הנדרשת כפונקציה של 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;
}
				
			

פוסט זה נכתב על מנת לסייע לסטודנטים בלימוד הנושא סיבוכיות. הפוסט צפוי להתעדכן ונושאים נוספים צפויים להתווסף.