DataStructures2026

📚 סיבוכיות חישובית

סיבוכיות חישובית מודדת כמה זמן או זיכרון נדרשים לאלגוריתם בהתאם לגודל הקלט. אנחנו משתמשים בכתיב (O) (Big O) כדי לתאר חסם עליון אסימפטוטי – כלומר איך הגדילה מתנהגת עבור קלטים גדולים מאוד.

O(1) – זמן קבוע

האלגוריתם מבצע מספר קבוע של פעולות שאינן תלויות בגודל הקלט.

int x = arr[0];
System.out.println(x);

O(n) – זמן ליניארי

מספר הפעולות פרופורציונלי לגודל הקלט.

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

O(n*m) – תלות בשני פרמטרים

הלולאות תלויות בשני גדלים שונים, לדוגמה גובה ורוחב מטריצה.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        process(i, j);
    }
}

O(n^2) – זמן ריבועי

כל איבר בקלט עובר על כל האיברים האחרים.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        compare(i, j);
    }
}

O(log n) – זמן לוגריתמי

הקלט מצטמצם כל פעם בחצי (או במנה קבועה אחרת).

int i = n;
while (i > 1) {
    i = i / 2;
}

בניתוח סיבוכיות נרצה בדרך כלל להתמקד בחלק הדומיננטי ביותר – זה שמכתיב את קצב הגדילה האסימפטוטי.

This site is open source. Improve this page.