יעילות אלגוריתמית
במדעי המחשב, יעילות אלגוריתמית מתייחסת לכמות צריכת משאבי מערכת של אלגוריתם, ובפרט משאבי זמן וזיכרון, אך גם משאבי אנרגיה או רוחב פס יכולים להיכלל בבחינת יעילות של אלגוריתם.
ניתן להתייחס ליעילות אלגוריתמית כמקרה פרטי של יעילות הנדסית.
להגדלת היעילות יש לצמצם את השימוש במשאבים. עם זאת, המשאבים השונים אינם ניתנים להשוואה בצורה חד משמעית, ולכן לא תמיד ניתן לקבוע באופן חד משמעי שאלגוריתם יעיל ממשנהו, למשל, פעמים רבות אלגוריתם אחד צורך יותר זמן ופחות זיכרון ממשנהו וצריך לבחון בכל מקרה לגופו איזה משאב יותר חשוב.
רקע
כבר בשנת 1843 כתבה עדה לאבלייס, הידועה כמתכנתת הראשונה (כתבה תוכנית למחשב מכני תאורטי שהמציא צ'ארלס בבג'):
כמעט בכל חישוב קיים מגוון גדול של סידורים אפשריים לביצוע החישוב בהצלחה, ומגוון שיקולים חייבים להשפיע על הבחירה ביניהם, בהקשר של מכונה חישובית. אחת המטרות המרכזיות היא לבחור סידור שינטה להפחית למינימום את הזמן הנדרש להשלמת החישוב.[1]
המחשבים האלקטרוניים הראשונים היו מוגבלים מאד בזיכרון ובמהירות הפעולות, והיה ברור שיש לתכנן אלגוריתמים חסכוניים על מנת שניתן יהיה להריצם על מחשבים אלו. במקרים מסוימים הבחינו[דרושה הבהרה] שיש מאזן תמורות (trade-off) בין צריכת זמן ומקום של אלגוריתם, והאתגר היה למצוא אלגוריתם המבצע את החישוב הדרוש במינימום זמן במסגרת הזיכרון המוגבל של המחשב. מאזן תמורות בין משאבים קיים בפתרונות של בעיות רבות, גם כאשר היקף המשאבים הזמינים הוא גדול, ולכן במקרים רבים לא ניתן לקבוע בצורה חד-משמעית איזה אלגוריתם יעיל יותר.
המחשבים בימינו מהירים בהרבה וכמות הזיכרון בהם גדולה בסדרי גודל רבים (מחשבי על מודרניים יכולים לגשת למרחבי זיכרון הנמדדים בטרה-בית, לעומת מרחב של קילובתים במחשבים הראשונים) אך עדיין יעילות מהווה שיקול מרכזי בהנדסת תוכנה.
אלגוריתם נחשב יעיל אם צריכת המשאבים שלו קטנה מסף מסוים. בדרך כלל הסף נקבע על פי האפשרות להריץ את האלגוריתם על המחשבים אליהם מיועדת התוכנה.
מדדים לבחינת יעילות: מהירות חישובים, מהירות שידור נתונים, מהירות תגובה. זיכרון: זיכרון הדרוש לריצת התוכנית, ניצול זמני של שטח הדיסק או שטח הדיסק הדרוש לאורך זמן, רוחב הפס בשידור נתונים. כסף: צריכת אנרגיה, שכר מתכנתים, TCO- עלות בעלות כוללת.
הדרך הבסיסית לבחון יעילות היא על ידי הערכת סיבוכיות חישובית של האלגוריתם.
חישובי סיבוכיות
לשם המחשה נשתמש בחישובי סיבוכיות זמן, כי היעילות נמדדת בראש ובראשונה לפי משאב הזמן.
בתורת החישוביות, סיבוכיות זמן של אלגוריתם היא הערכה, באמצעות חסמים, על מספר הפעולות שמבצע האלגוריתם במהלך פעולתו, כפונקציה של מורכבות הקלט.
היות שמספר הפעולות שמבצע אלגוריתם משתנה על פי רוב בהתאם לגודל הקלט שלו, מוגדרת מורכבות הקלט על פי רוב כגודל הקלט.
אין בוחנים את זמן הריצה ביחידות זמן (שניות, דקות וכו'), שכן משך הזמן לביצוע פעולות משתנה מסביבת ריצה אחת לשנייה. כמות ה"עבודה" הניתנת לביצוע בצעד בודד עשויה להיות שונה בין מודלים חישוביים שונים - ובין מחשבים שונים.
לכן, בחישובי סיבוכיות נוטים להתעלם מקבועים, ולומר, למשל, כי הן אלגוריתם שדורש 10n צעדים על קלטים ממורכבות n, והן אלגוריתם שדורש 100n צעדים על קלטים כאלו הינם שניהם אלגוריתמים בעלי זמן ריצה לינארי.
בניגוד לחישוב סיבוכיות, כאשר עוסקים בבדיקת יעילות האלגוריתם, חשוב המימוש המעשי של התוכנית, ויש משמעות למכונות אליהן מיועדת התוכנית. יש חשיבות לקבועים ולזמן הנדרש בפועל עבור קלטים סבירים בתוכנה.
חישובי סיבוכיות מתרכזים בסדרי גודל של צריכת משאבים.
הסימון הרווח לציון סדר גודל של סיבוכיות אלגוריתם: זמן ריצה פרופורציונלי, עד כדי קבוע, לפונקציה .
הפונקציות העיקריות המשמשות לציון סדרי גודל הן: לוגריתם, פונקציה לינארית, פולינום ופונקציה מעריכית.
בחישובי סיבוכיות מקובל שכל עוד סיבוכיות האלגוריתם פולינומית, האלגוריתם יעיל. בבדיקת יעילות לא די בכך שהאלגוריתם מסיבוכיות פולינומית, אלא יש לוודא שהאלגוריתם אכן יעיל וניתן להרצה על המכונות הרלוונטיות ושאין חלופות יעילות יותר. על פי רוב, אלגוריתמים בעלי זמן ריצה מעריכי אינם נחשבים ליעילים, וזאת משום שהפונקציה המעריכית גדלה מהר מאד ביחס לקלט.
ראו גם
הערות שוליים
- ^ Augusta Ada Byron King, Countess of Lovelace, Sketch of the Analytical Engine invented by Charles Babbage, Esq. - Notes by the translator, from "Classics in the History of Psychology", 1843