יעילות אלגוריתמית

יעילות אלגוריתמית מתייחסת לכמה משאבים אלגוריתם צורך. המשאבים העיקריים הם זמן ורוחב זיכרון, אך גם אנרגיה או רוחב פס יכולים להיחשב.
לעתים יש תחרות בין משאבים, למשל אלגוריתם שצריך פחות זמן יכול להשתמש ביותר זיכרון. לכן לא תמיד אפשר לומר בצורה חד-משמעית איזה אלגוריתם "טוב" יותר.

כבר ב-1843 כתבה עדה לאבלייס תוכנית למחשב מכני של צ'ארלס בבג'. בעידן המחשבים הראשונים הזיכרון והמהירות היו מוגבלים, ולכן פיתוח אלגוריתמים חסכוניים היה הכרחי. גם היום, למרות שהמחשבים מהירים ויש להם זיכרון רב יותר, יעילות נשארת שיקול מרכזי בהנדסת תוכנה.
אלגוריתם נחשב יעיל אם צריכת המשאבים שלו נמוכה מספיק כדי להריץ אותו על המחשבים היעדיים.

מדדים נפוצים לבחינת יעילות כוללים: מהירות חישוב, מהירות שידור נתונים, זמן תגובה, זיכרון נדרש, ניצול דיסק, רוחב פס, וכן עלויות כמו צריכת אנרגיה ושכר עובדים.
הדרך הבסיסית להעריך יעילות היא חישוב סיבוכיות החישובית של האלגוריתם.

בסיבוכיות זמן בוחנים את מספר הפעולות שהאלגוריתם מבצע כפונקציה של גודל הקלט. סיבוכיות הזמן היא הערכה, לא מדידה בשניות, כי זמן ריצה תלוי במכונה ובמודל החישוב.
בחישוב סיבוכיות מתעלמים מקבועים: למשל 10n ו־100n נחשבים שניהם ליניאריים.
עם זאת, בבחינת יעילות מעשית יש חשיבות לקבועים ולמימוש התוכנית על המכונה הרלוונטית.
חישובי סיבוכיות מתמקדים בסדרי גודל. הסימון המקובל הוא Θ(f(n)), שמשמעו זמן ריצה פרופורציונלי, עד קבוע, לפונקציה f(n).
הפונקציות העיקריות הן: לוגריתמית, ליניארית, פולינומית ומעריכית. בדרך כלל פולינומית נחשבת ליעילה, ואילו פונקציה מעריכית אינה יעילה כי היא גדלה מהר מאוד.

יעילות אלגוריתמית אומרת כמה משאבים אלגוריתם צורך. משאב הוא זמן או זיכרון.
אלגוריתם הוא סדרת פעולות לפתור בעיה.
לפעמים צריך לבחור בין פחות זמן ליותר זיכרון.

ב-1843 כתבה עדה לאבלייס תוכנית למחשב מכני של בבג'.
המחשבים הראשונים היו איטיים ובעלי מעט זיכרון. לכן המציאו אלגוריתמים חיסכוניים.
גם היום חשוב לחשוב על יעילות, למרות שהמחשבים חזקים יותר.

סיבוכיות זמן אומרת כמה צעדים האלגוריתם עושה לפי גודל הקלט. הקלט זה המידע שהאלגוריתם מקבל.
לא מודדים זמן בשניות, כי מחשבים שונים הם לא זהים.
חישובים מתמקדים בסדרים גדולים. יש פונקציות כמו לוגריתם, ליניארית, פולינומית ומעריכית.
פונקציה פולינומית היא בדרך כלל טובה. פונקציה מעריכית גדלה מהר מאוד, ולכן פחות טובה.