ניתן להתייחס ליעילות אלגוריתמית כמקרה פרטי של יעילות הנדסית.
להגדלת היעילות יש לצמצם את השימוש במשאבים. עם זאת, המשאבים השונים אינם ניתנים להשוואה בצורה חד משמעית, ולכן לא תמיד ניתן לקבוע באופן חד משמעי שאלגוריתם יעיל ממשנהו, למשל, פעמים רבות אלגוריתם אחד צורך יותר זמן ופחות זיכרון ממשנהו וצריך לבחון בכל מקרה לגופו איזה משאב יותר חשוב.
רקע.
כבר בשנת 1843 כתבה עדה לאבלייס, הידועה כמתכנתת הראשונה (כתבה תוכנית למחשב מכני תאורטי שהמציא צ'ארלס בבג'):
המחשבים האלקטרוניים הראשונים היו מוגבלים מאוד בזיכרון ובמהירות הפעולות, והיה ברור שיש לתכנן אלגוריתמים חסכוניים על מנת שניתן יהיה להריצם על מחשבים אלו. במקרים מסוימים הבחינו שיש מאזן תמורות (trade-off) בין צריכת זמן ומקום של אלגוריתם, והאתגר היה למצוא אלגוריתם המבצע את החישוב הדרוש במינימום זמן במסגרת הזיכרון המוגבל של המחשב. מאזן תמורות בין משאבים קיים בפתרונות של בעיות רבות, גם כאשר היקף המשאבים הזמינים הוא גדול, ולכן במקרים רבים לא ניתן לקבוע בצורה חד-משמעית איזה אלגוריתם יעיל יותר.
המחשבים בימינו מהירים בהרבה וכמות הזיכרון בהם גדולה בסדרי גודל רבים (מחשבי על מודרניים יכולים לגשת למרחבי זיכרון הנמדדים בטרה-בית, לעומת מרחב של קילובתים במחשבים הראשונים) אך עדיין יעילות מהווה שיקול מרכזי בהנדסת תוכנה.
אלגוריתם נחשב יעיל אם צריכת המשאבים שלו קטנה מסף מסוים. בדרך כלל הסף נקבע על פי האפשרות להריץ את האלגוריתם על המחשבים אליהם מיועדת התוכנה.
מדדים לבחינת יעילות: מהירות חישובים, מהירות שידור נתונים, מהירות תגובה. זיכרון: זיכרון הדרוש לריצת התוכנית, ניצול זמני של שטח הדיסק או שטח הדיסק הדרוש לאורך זמן, רוחב הפס בשידור נתונים. כסף: צריכת אנרגיה, שכר מתכנתים, TCO- עלות בעלות כוללת.
הדרך הבסיסית לבחון יעילות היא על ידי הערכת סיבוכיות חישובית של האלגוריתם.
חישובי סיבוכיות.
לשם המחשה נשתמש בחישובי סיבוכיות זמן, כי היעילות נמדדת בראש ובראשונה לפי משאב הזמן.
בתורת החישוביות, סיבוכיות זמן של אלגוריתם היא הערכה, באמצעות חסמים, על מספר הפעולות שמבצע האלגוריתם במהלך פעולתו, כפונקציה של מורכבות הקלט.
היות שמספר הפעולות שמבצע אלגוריתם משתנה על פי רוב בהתאם לגודל הקלט שלו, מוגדרת מורכבות הקלט על פי רוב כגודל הקלט.
אין בוחנים את זמן הריצה ביחידות זמן (שניות, דקות וכו'), שכן משך הזמן לביצוע פעולות משתנה מסביבת ריצה אחת לשנייה. כמות ה"עבודה" הניתנת לביצוע בצעד בודד עשויה להיות שונה בין מודלים חישוביים שונים - ובין מחשבים שונים.
לכן, בחישובי סיבוכיות נוטים להתעלם מקבועים, ולומר, למשל, כי הן אלגוריתם שדורש 10n צעדים על קלטים ממורכבות n, והן אלגוריתם שדורש 100n צעדים על קלטים כאלו הם שניהם אלגוריתמים בעלי זמן ריצה ליניארי.
בניגוד לחישוב סיבוכיות, כאשר עוסקים בבדיקת יעילות האלגוריתם, חשוב המימוש המעשי של התוכנית, ויש משמעות למכונות אליהן מיועדת התוכנית. יש חשיבות לקבועים ולזמן הנדרש בפועל עבור קלטים סבירים בתוכנה.
חישובי סיבוכיות מתרכזים בסדרי גודל של צריכת משאבים.
הסימון הרווח לציון סדר גודל של סיבוכיות אלגוריתם: formula_1
זמן ריצה פרופורציונלי, עד כדי קבוע, לפונקציה formula_2.
הפונקציות העיקריות המשמשות לציון סדרי גודל הן: לוגריתם, פונקציה ליניארית, פולינום ופונקציה מעריכית.
בחישובי סיבוכיות מקובל שכל עוד סיבוכיות האלגוריתם פולינומית, האלגוריתם יעיל. בבדיקת יעילות לא די בכך שהאלגוריתם מסיבוכיות פולינומית, אלא יש לוודא שהאלגוריתם אכן יעיל וניתן להרצה על המכונות הרלוונטיות ושאין חלופות יעילות יותר. על פי רוב, אלגוריתמים בעלי זמן ריצה מעריכי אינם נחשבים ליעילים, וזאת משום שהפונקציה המעריכית גדלה מהר מאוד ביחס לקלט.
זמן ריצה פולינומאלי
זמן ריצה פולינומי
סיבוכיות זמן
בתורת החישוביות, סיבוכיות זמן של אלגוריתם היא הערכה, באמצעות חסמים, על מספר הפעולות שמבצע האלגוריתם כפונקציה של גודל הקלט.
אין בוחנים את זמן הריצה ביחידות זמן (כגון שניות), משום שמשך הזמן לביצוע פעולה תלוי במודל החישובי ובמחשב שעליו רץ האלגוריתם. למשל, ייתכן שבמודל או בארכיטקטורה מסוימת ניתן לחלק מספר אחד בחברו בצעד אחד, ואילו במודל או ארכיטקטורה אחרת יידרשו לאותה פעולה מספר צעדים. משום כך, בניתוח הסיבוכיות של אלגוריתם מקובל להביא בחשבון רק את סדרי הגודל, ולהתעלם מקבועים. למשל, אלגוריתם המבצע 8n+112 פעולות על קלט בגודל n הוא בעל "זמן ריצה ליניארי".
הסימון הרווח לזמן הריצה של אלגוריתמים הוא:
הגדרות פורמליות יותר למושגים אלו ניתן למצוא ב.
סדרי גודל נפוצים.
זמן ריצה לוגריתמי.
אלגוריתם בעל זמן ריצה לוגריתמי מסתיים תוך זמן פרופורציוני ללוגריתם של גודל הקלט. אין צורך לציין את בסיס הלוגריתם, משום שהחלפת בסיס שקולה לכפל בקבוע, ולכן אם זמן הריצה פרופורציוני לגודל הקלט לפי בסיס לוגריתם כלשהו, הוא פרופורציוני לגודל הקלט גם לפי כל בסיס לוגריתם אחר.
לדוגמה, חיפוש ברשימה ממוינת (בשיטת החצייה) מתבצע בזמן ריצה לוגריתמי. תפקידו של האינדקס בבסיס נתונים הוא לאפשר זמן ריצה לוגריתמי בחיפושים, כאשר ללא אינדקס זמן הריצה הוא ליניארי.
זמן ריצה ליניארי.
נאמר על אלגוריתם שזמן ריצתו ליניארי אם זמן הריצה שלו חסום על ידי פונקציה ליניארית בגודל הקלט, או - באופן שקול - פרופורציונלי לאורך הקלט.
לדוגמה, אלגוריתם אשר מחפש את המספר הגדול ביותר ברשימת מספרים נתונה על ידי מעבר סדרתי על הרשימה הוא בעל זמן ריצה ליניארי שכן אם גודל הקלט הוא n, האלגוריתם יבצע n צעדים.
מאידך, אלגוריתם מיון אשר ממיין רשימת מספרים על ידי בחירת המספר הגדול ביותר והסרתו מהרשימה, בחירת השני בגודלו והסרתו, וכן הלאה, אינו בעל זמן ריצה ליניארי. זאת משום שאם גודל הקלט הוא n, האלגוריתם מבצע n שלבים, ובכל שלב מבצע n-1 צעדים (מעבר על כל המספרים שנותרו) ולכן זמן הריצה יהיה ריבועי (פולינום ממעלה שנייה).
זמן ריצה ליניארי הוא בפרט פולינומי ועל כן נחשב חישוב יעיל.
זמן ריצה פולינומי.
לאלגוריתם נתון ישנו זמן ריצה פולינומי אם קיים פולינום formula_1 כך שזמן הריצה של האלגוריתם עבור קלטים בגודל n חסום על ידי ערך הפולינום עבור n. אלגוריתמים אשר זמן ריצתם אינו חסום על ידי פולינום, כגון אלגוריתמים בעלי זמן ריצה מעריכי, נקראים לעיתים "סופר-פולינומיים".
מקובל לקשר זמן ריצה פולינומי עם חישוב יעיל, כך שאלגוריתם ייחשב יעיל אם זמן הריצה שלו פולינומי. מעשית, לא כל זמן ריצה פולינומי מעיד על יעילות, שכן קיימים פולינומים בעלי חזקות גבוהות - בעת פיתוח אלגוריתם נעדיף זמן ריצה פולינומי מסדר נמוך, כגון זמן ליניארי או ריבועי.
זמן ריצה מעריכי (אקספוננציאלי).
סיבוכיות זמן הריצה של אלגוריתם היא מעריכית אם ורק אם פונקציית זמן הריצה שלו חסומה על ידי פונקציה מעריכית (kn) כפול קבוע, כאשר בסיס הפונקציה המעריכית (k) גדול מ-1.
על פי רוב, אלגוריתמים בעלי זמן ריצה מעריכי אינם נחשבים ליעילים, וזאת משום שהפונקציה המעריכית "גדלה מהר מאוד" ביחס לקלט; לכן, מועדף השימוש באלגוריתמים מזמני ריצה טובים יותר. דוגמה לאלגוריתם שכזה: אלגוריתם לפתרון בעיית מגדלי האנוי.
זמן ריצה תת-מעריכי.
סיבוכיות זמן ריצה תת-מעריכית או תת-אקספוננציאלית, מוערכת על ידי formula_2, כאשר:
formula_4 הוא משקל החלק הלוגריתמי במעריך, בעוד שהמשלים ל-formula_4 הוא משקל החלק הלוג-לוגריתמי, הקטן יותר. לכל ערך של formula_4, הפונקציה מייצגת סיבוכיות גדולה יותר ככל ש-formula_7 גדול יותר. לשם השוואה, formula_8 היא סיבוכיות אקספוננציאלית, בעוד ש-formula_9 היא סיבוכיות פולינומית. על סולם זה, קל להעריך את מידת היעילות של האלגוריתם מתוך התבוננות בערך formula_4 למשל formula_11 נמצאת ב"אמצע הדרך" בין סיבוכיות אקספוננציאלית לפולינומית.
זמן ריצה עצרתי.
מונח זה מתאר אלגוריתמים שזמן הריצה שלהם חסום על ידי פונקציית עצרת. בדומה לאלגוריתמים בעלי זמן ריצה מעריכי, אלגוריתם שפועל בזמן ריצה עצרתי נחשב ללא-יעיל במיוחד כאשר מדובר בקלטים גדולים. האלגוריתם המדויק הידוע לפתרון בעיית הסוכן הנוסע נחשב לאלגוריתם בעל זמן ריצה שכזה.
זמן הריצה של פתרון בעיית הפירוק לגורמים.
בעיית הפירוק של מספר שלם לגורמים נחשבה במשך שנים לבעיה אקספוננציאלית והיא עמדה על סיבוכיות משוערת מסדר גודל formula_11 והושגו רק שיפורים מינוריים בערכו של הקבוע formula_7. שיפור משמעותי הושג ב-1988, כאשר המתמטיקאים ג'ון פולארד, מארק מאנאס, הנדריק לנסטרה וארג'ן לנסטרה פרסמו את שיטת נפת שדה מספרים המיוחדת לפירוק מספרים בעלי מבנה מיוחד כמספרי פרמה ומספרי קנינגהם. לשיטה זו סיבוכיות מהצורה formula_14 כשהקבוע formula_15. כמספר שנים לאחר מכן, פותח האלגוריתם הכללי - "נפת שדה המספרים הכללית" המתאים לפירוק כל מספר שלם ויעילותו מוערכת ב-formula_14, כשהקבוע formula_17. בכל המקרים נוסחאות הסיבוכיות מנומקות, מוסכמות על כל המומחים, מגובות בתוצאות אמפיריות - אך אינן מוכחות.
מומחים הראו שעל ידי אלגוריתם קוונטי המבוצע במחשב קוונטי, כגון אלגוריתם שור, ניתן להפחית את זמן הריצה של בעיית הפירוק לגורמים לזמן ריצה של formula_18 הנמוך משמעותית.
בעיית הכרעה
במתמטיקה ובמדעי המחשב, בעיית הכרעה היא בעיה אשר יש לה תשובה של "כן" או "לא".
דוגמה: השאלה האם מספר טבעי נתון הוא ראשוני היא בעיית הכרעה. מאידך, הבעיה "מציאת המספר הראשוני הקטן ביותר בעל 77 ספרות" אינה בעיית הכרעה, שכן התשובה עבורה אינה "כן" או "לא".