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

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

Share This Post

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

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

הירשמו לניוזלטר שלנו

התעדכנו בחידושים הטכנולוגים

פוסטים נוספים

הזנק את העסק שלך!

נשמח להיפגש לקפה!

life michael academy asynchronous online courses

Java | Python | JavaScript | TypeScript

Update cookies preferences