ניתוח זמן ריצה לא פורמלי
הוצג| English | משמעות |
|---|---|
| run time/rʌn taɪm/ | זמן הרצה |
| linear/ˈlɪnɪə/ | ליניארי |
| quadratic/kwɒˈdrætɪk/ | ריבועי |
ספירת העבודה
- אנו מודדים את זמן הריצה של תוכנית על ידי כמה פעמים פקודות המפתח שלה מתבצעות.
- לא בשניות (שהן משתנות לפי המכשיר) — אלא בספירת פעולות ככל שהקלט גדל.
- יותר פעולות עבור אותו גודל קלט → אלגוריתם איטי יותר.
- דבר זה מאפשר להשוות בין אלגוריתמים בצורה הוגנת, ללא תלות בחומרה.
לולאה יחידה: בערך n
- לולאה על
nפריטים רוצה את הגוף שלה כ-nפעמים. - הכפלת הקלט → כ-הכפלה בעבודה. זהו צמיחה ליניארית.
- סיכום מערך, חיפוש ברשימה אחד-אחד: כולם כ-
nצעדים. - כתוב באופן לא רשמי כ"סדר
n."
לולאה מושתתת: בערך n²
- לולאה מושתתת על
nפריטים רוצה את הגוף הפנימי כ-n × n = n²פעמים. - הכפלת הקלט → כ-ארבע פעמים העבודה. זהו צמיחה ריבועית.
- השוואת כל הזוגות, מילוי רשת
n × n: כ-n²צעדים. n²גדל הרבה מהר יותר מ-nכאשרnהופך לגדול.
השוואת צמיחה
- כדי להשוות אלגוריתמים, יש לשאול כיצד העבודה גדלה ככל שהקלט גדל.
- עבור
nגדול, אלגוריתםnעולה על אלגוריתםn²– לעיתים קרובות בהפרש רב. - התמקד בחלק מהקוד שרץ הכי הרבה (בדרך כלל הלולאה הפנימית ביותר).
- האיבר הגדל המהר ביותר שולט בזמן הריצה הכולל.
הערכו זמן ריצה לפי הגידול, לא לפי ספירה קבועה. אלגוריתם שמבצע n צעדים ואחד שמבצע 2n + 5 צעדים גדלים שניהם ליניארית — לעומת ההשוואה, הקבוע וה-+5 אינם חשובים; מה שחשוב הוא הצורה (n מול n²). לולאה אחת היא בערך n; לולאה משתלבת היא בערך n², שגדלת הרבה יותר עבור כניסות גדולות.
שתי דרכים למצוא חוזרות ב-n פריטים:
- לולאות משתלבות המשווות כל זוג: כ-
n²צעדים. - סדר קודם, ואז מעבר אחד: הרבה פחות צעדים עבור
nגדולה. - עבור
n = 1000,n²הוא מיליון צעדים – הגישת ה-n²איטית בהרבה.
ניתוח זמן ריצה לא-רשמי סופר כמה פעמים הודעות מריצות ככל שהקלט גדל. לולאה אחת על n פריטים היא בערך n (ליניארית); לולאה מקוננת היא בערך n² (ריבועית), שמגדלת הרבה יותר מהר. השווה אלגוריתמים לפי הגידול, ומתמקדים בקוד המוצרן ביותר (הפנימי ביותר).
כיצד העבודה גדלה עם n
לולאה מקוננת (n²) גדלה הרבה מהר יותר מאשר לולאה יחידה (n).
לולאה יחידה על n פריטים מבצעת את גופה כמה פעמים לערך?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
לולאה אחת על n פריטים → כ-n צעדים (קווי).
לולאה מקוננת על n פריטים מבצעת את גופה הפנימי כמה פעמים לערך?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
n × n = n² (ריבועי).
עבור n = 1000, כ多少 צעדים יש算法 נ°n² (במיליונים)?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
1000² = 1,000,000 = 1 מיליון.
עבור n גדול, אלגוריתם של n צעדים הוא לרוב מהיר יותר מאחד של n² צעדים.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
n² גדל הרבה מהר יותר, ולכן מבצע הרבה יותר עבודה ב-n גדול.
אנו מודדים זמן ריצה בשניות, שהוא זהה בכל מחשב.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אנו סופרים פעולות מול גודל הקלט — השניות משתנות לפי מכונה.