מודלים חישוביים ויעילות אלגוריתמית
דומיין זה בודק ניתוח יעילות ומודלים של חישוב: כיצד מודדים זמן ומקום, מהו חסם הדוק, ואיך משפיעים רקורסיה, לולאות וגודל קלט על הסיבוכיות. זהו החיבור בין אלגוריתם לבין טענה מתמטית על התנהגותו.
מושגי יסוד
- O(f(n)) הוא חסם מלמעלה; Ω(f(n)) חסם מלמטה; Θ(f(n)) חסם הדוק משני הצדדים.
- קבועים ומחברים בעלי סדר נמוך מוזנחים: 3n^2+7n+2 הוא Θ(n^2).
- מנתחים מקרה גרוע, ממוצע וטוב, אך מציינים במפורש איזה מהם.
- רקורסיה מנותחת באמצעות נוסחת נסיגה או עץ רקורסיה; דוגמה: T(n)=2T(n/2)+n נותן Θ(n log n).
- מודל RAM מניח גישה בזמן קבוע לזיכרון, ולכן הניתוח אינו תלוי במהירות המחשב.
- החלפת מקום בזמן היא לעיתים הכרחית: טבלת גיבוב מהירה יותר אך צורכת זיכרון.
דוגמה מעובדת
לולאה כפולה: for i=1..n, for j=1..i. מספר האיטרציות הוא 1+2+...+n = n(n+1)/2 = Θ(n^2). הנימוק: הסכום הוא פולינום ריבועי, והמקדם 1/2 קבוע ולכן אינו משנה את סדר הגדילה. לולאה כפולה על כל n עבור כל n הייתה n^2, ואילו לולאה אחת הייתה Θ(n).
מלכודות
- כתיבת O(n^2) כאשר נדרש Θ(n^2), או להפך.
- התעלמות מכך שלולאה פנימית תלויה באינדקס החיצוני.
- ניתוח רקורסיה בלי לספור את עלות הפיצול והמיזוג.
- בלבול בין סיבוכיות זמן לסיבוכיות מקום.
- הנחה שכל פעולה בשפה היא O(1), כולל חיבור מחרוזות ארוכות.