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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

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

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

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

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

שפות אחרות