אלגוריתמי חיפוש (לינאריבינארי)אלגוריתמי מיון (בחירהבועותהכנסה)סיבוכיות זמן ומקום (Big O notation)רקורסיה ואיטרציה
ברוכים הבאים ליחידת הלימוד "אלגוריתמים בסיסיים וניתוח סיבוכיות" בקורס "מעבדה בתכנות מערכות" (20465). יחידה זו חיונית להבנת היעילות של תוכניות מחשב. נלמד כיצד למדוד ולשפר את ביצועי האלגוריתמים שלנו באמצעות כלים כמו סיבוכיות זמן ומקום, ונכיר אלגוריתמי חיפוש ומיון בסיסיים.
יסודות אלגוריתמים וניתוח סיבוכיות
כמתכנתי מערכות, עלינו לכתוב קוד יעיל. ניתוח סיבוכיות מאפשר לנו להעריך את ביצועי האלגוריתמים באופן תיאורטי, ללא תלות בחומרה או בשפת התכנות.
סיבוכיות זמן: מדד לכמות הזמן הנדרשת לאלגוריתם, כפונקציה של גודל הקלט (N).
סיבוכיות מקום: מדד לכמות הזיכרון הנדרשת לאלגוריתם, כפונקציה של גודל הקלט (N).
סימון Big O: כלי לתיאור קצב הגידול של פונקציה, המשמש לתיאור סיבוכיות זמן ומקום במקרה הגרוע ביותר. מתמקד בהתנהגות האסימפטוטית ככל ש-N שואף לאינסוף, תוך התעלמות מקבועים ואיברים מסדר נמוך.
סימון Big O: נושא קריטי לבחינה. הבנה מעמיקה של Big O חיונית לניתוח ותכנון אלגוריתמים. הקפידו להבין את המשמעות של O(1), O(log N), O(N), O(N log N), O(N^2), O(2^N) ו-O(N!).
אלגוריתמי חיפוש
אלגוריתמי חיפוש מאפשרים לנו למצוא איבר במבנה נתונים. נתמקד בשני אלגוריתמים למערכים.
חיפוש לינארי
הסבר: עובר על כל איברי המערך בזה אחר זה עד למציאת האיבר או הגעה לסוף. מתאים למערכים לא ממוינים.