אנליזה של אלגוריתמים

ניתוח זמן ריצה

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

רמות של קצב גידול

באופן לא רשמי, ניתן לומר כי אלגוריתם מציג צמיחה בשיעור מסדר גודל של פונקציות מתמטיות אם עבור קלט מסוים בגודל n, פונקציה  כפול קבוע חיובי מספקת את החסם העליון או הגבול של זמן הריצה של האלגוריתם. במילים אחרות, עבור גודל קלט n אשר גדול יותר מ-n₀ וקבוע c, זמן הריצה של אלגוריתם לעולם לא יהיה גדול מאשר . ביטוי זה מיוצג לעיתים קרובות על ידי סימון O גדולה. לדוגמה, כיוון שזמן הריצה של מיון הכנסה גדל בצורה מרובעת כמו שלה הקלט גדל, ההכנסה סוג יכול להיות אמר להיות של סדר O(n²).
סימון O גדולה הוא דרך נוחה כדי לבטא את התרחיש הגרוע ביותר עבור אלגוריתם נתון, אף על פי שזה יכול לשמש גם כדי להביע את המקרה הממוצע — לדוגמה, התרחיש הגרוע ביותר עבור quicksort הוא O(n²), אבל זמן הריצה עבור המקרה הממוצע הוא O(n log n).

ניתוח קצב גידול של משאבים אחרים

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

 
while (file still open)
 let n = size of file
 for every 100,000 kilobytes of increase in file size
 double the amount of memory reserved
במקרה הזה, ככל שגודל הקובץ n גדל, הזיכרון נצרך בקצב גידול מעריכי, אשר מסדר O(2ⁿ). זה מאוד מהיר ורוב הסיכויים קצת גידול לא ניתן לניהול של שימוש משאבי זיכרון.

רלוונטיות

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

גורמים קבועים

אנליזה של אלגוריתמים בדרך כלל מתמקדת בביצועים אסימפטוטיים, במיוחד ברמה הבסיסית, אבל ביישומים מעשיים גורמים קבועים הם חשובים, ונתונים בעולם האמיתי תמיד מוגבלים בגודל בפועל. הגבול הוא בדרך כלל בגודל של זיכרון השמיש, אז על מערכות של 32 סיביות 2³² = 4  GiB (או יותר אם מזיכרון מקוטע), ובמערכות של-64 סיביות 2⁶⁴ = 16 EiB. לפיכך תחת גודל מוגבל, סדר הגודל (זמן או מקום) יכול להיות מוחלף על ידי גורם קבוע, ובמובן זה כל האלגוריתמים המעשיים הם O(1) עבור קבוע מספיק גדול, או גודל נתונים קטן מספיק.
פרשנות זו היא יעילה בעיקר עבור פונקציות הגדלות לאט מאוד: (בינארית) הלוגריתם החוזר (log*) הוא פחות מ-5 לכל כמות נתונים מעשית (2⁶⁵⁵³⁶ ביטים); (בינארי) log-log (log log n) הוא פחות מ-6 לכמעט כל כמות נתונים מעשית (2⁶⁴ סיביות); ובינארית (log (log n) הוא פחות מ-64 לכמעט כל כמות נתונים מעשית (2⁶⁴ סיביות). אלגוריתם עם מרוכבות שאינה קבועה מורכבות עשוי בכל זאת להיות יותר יעיל מאשר אלגוריתם קבוע על נתונים פרקטיים אם החסם העליות של הזמן הקבוע יוצר תוצאה קבועה גדולה יותר לדוגמה  יכול להיות  כל עוד  ו .
עבור כמות גדולה של מידע לא ניתן להתעלם מגורמים ליניארים או ריבועיים, אבל עבור כמויות קטנות של מידע אלגוריתם לא יעיל אסימפטוטית להיות יעיל יותר. זה במיוחד בשימוש במקרה של אלגוריתמים היברידיים, כמו Timsort, אשר משתמש באלגוריתם לא יעיל אסימפטוטית (כאן במיון מיזוג, עם מרוכבות הזמן ), אבל מחליף לאלגוריתם יעיל אסימפטוטית (כאן מיון החדרה, עם מרוכבות הזמן ) עבור כמות נתונים קטנה, כיוון שהאלגוריתם הפשוט יותר הוא מהיר יותר על כמות קטנה של נתונים.