חולמים על קריירה בהייטק?
בדקו את הקורסים שלנו:
סיבוכיות זמן ריצה למתחילים
סיבוכיות זמן ריצה למתחילים
כאשר אנחנו כותבים קוד, חשוב להבין את סיבוכיות זמן הריצה של האלגוריתמים שלנו. סיבוכיות זמן ריצה מתארת את כמה זמן ידרוש האלגוריתם לבצע משימה מסוימת בהתחשב בגודל הקלט.
ישנן מספר דרגות של סיבוכיות זמן ריצה. נסקור כמה מהן ונראה איך להבין אותן בעזרת דוגמאות קוד.
סיבוכיות קבועה - O(1)
סיבוכיות קבועה מתארת אלגוריתם שבו זמן הריצה לא תלוי בגודל הקלט. כלומר, גם אם נזין יותר נתונים, זמן הריצה לא ישתנה.
1
2
let x = 10;
console.log(x);הקוד לעיל מריץ פקודה אחת בלבד, ולכן זמן הריצה הוא O(1), כלומר קבוע.
סיבוכיות לינארית - O(n)
סיבוכיות לינארית מתארת אלגוריתם שבו זמן הריצה תלוי ישירות בגודל הקלט. כלומר, אם גודל הקלט יכפיל את עצמו, זמן הריצה גם יכפיל את עצמו.
1
2
3
4
let n = 10;
for (let i = 0; i < n; i++) {
console.log(i);
}הקוד לעיל מבצע לולאת for שהופכת את זמן הריצה לתלוי ישירות בגודל הקלט. אם n גדל, זמן הריצה יגדל בהתאם.
סיבוכיות ריבועית - O(n^2)
סיבוכיות ריבועית מתארת אלגוריתם שבו זמן הריצה כפול בגודל הקלט (למשל, עבור רשימה של גודל n, יהיו n^2 פעולות).
1
2
3
4
5
6
let n = 10;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i, j);
}
}הקוד לעיל ייצור לולאה פנימית בתוך לולאה חיצונית, וכך זמן הריצה יהיה O(n^2), תלוי בגודל הקלט.
סיבוכיות לוגריתמית - O(log n)
סיבוכיות לוגריתמית מתארת אלגוריתם שמפחית את גודל הקלט בחצי בכל שלב, למשל בחיפושי ביניים.
1
2
3
4
5
6
let n = 16;
let i = 1;
while (i < n) {
console.log(i);
i *= 2;
}הקוד לעיל יפחית את גודל הקלט בחצי בכל שלב, ולכן זמן הריצה יהיה O(log n).
סיבוכיות קובייתית - O(n^3)
סיבוכיות קובייתית מתארת אלגוריתם שבו זמן הריצה תלוי בקוביה של גודל הקלט.
1
2
3
4
5
6
7
8
let n = 10;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
console.log(i, j, k);
}
}
}הקוד לעיל מבצע שלוש לולאות, כל אחת תלויה בגודל הקלט, ולכן זמן הריצה יהיה O(n^3).
סיבוכיות אקספוננציאלית - O(2^n)
סיבוכיות אקספוננציאלית מתארת אלגוריתם שבו זמן הריצה עולה בצורה אקספוננציאלית עם גידול הקלט.
1
2
3
4
5
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(10));הקוד לעיל מציג פונקציה שמבצעת חישוב בסיבוכיות O(2^n), כי היא מחשבת את כל הערכים הקודמים מחדש בכל פעם.
סיכום
סיבוכיות זמן ריצה היא קריטית להבנת ביצועי האלגוריתמים שלנו. כאשר אנחנו כותבים קוד, חשוב לדעת אילו אלגוריתמים יעילים יותר עבור סוגי הקלט השונים, כדי למנוע בעיות ביצועים בעת הריצה.
למידה על סיבוכיות זמן ריצה תעזור לנו לבנות אלגוריתמים טובים יותר, שמספקים את התוצאה בצורה מהירה ויעילה יותר.
הצטרפו לאתר קודבוקס והתחילו ללמוד תכנות לבד.
אין צורך בידע מקדים, לומדים לתכנת מאפס.
פלטפורמת תכנות המוטמעת בדפדפן שתבדוק את הקוד שלכם בזמן אמת.
קודי, מורה הבינה המלאכותית של אתר קודבוקס שיעזור לכם בפתרון שאלות הקוד באתר.
צוברים מטבעות קודבוקס במהלך הלמידה,
