יחידה 4
אלגוריתמים ויעילות.
להשוות אלגוריתמים בלי שעון: ארבע שיטות מיון, חיפוש בחציה, והסימון O גדולה.
לפני היחידה הזאת
- ביטים ונתונים
- חזקות ולוגריתמים מתמטיקה
היחידה, שיעור אחר שיעור
שיעורים
4 שיעורים · 22 שאלות תרגול · כשעתיים
הצעדים של אלגוריתם
מה זה אלגוריתם, דרך שיטה אחת למיין: מיון בועות משווה שכנים ומחליף אותם, מעבר אחר מעבר. סופרים השוואות והחלפות, ורואים איך השורה שמתחילים ממנה משנה את העבודה.
להשוות בין מיונים
ארבע שיטות לאותה בעיה: מיון בועות, מיון הכנסה, מיון מיזוג ומיון מהיר. מודדים כמה השוואות כל אחת עושה על אותה שורה, מגלים שמספר ההחלפות קבוע, ורואים שגם לשיטה מהירה יש מקרה גרוע.
חיפוש וחציה
שתי דרכים למצוא שם ברשימה: לבדוק אחד אחד, או לפתוח באמצע ולהשליך חצי. למה חיפוש בינארי צריך רשימה ממוינת, ואיך הלוגריתם לפי בסיס שתיים סופר כמה חציות הוא צריך.
קצב גדילה ו־O גדולה
מה קורה לעבודה כשהרשימה מוכפלת: מיון בועות גדל כמו ריבוע האורך, ומיון מיזוג רק מעט מהר יותר מהאורך עצמו. הגרף שמשווה ביניהם, הסימון O גדולה, ולמה אלגוריתם טוב מנצח מחשב מהיר.