הצגת המקור של הדף "אנליזה של אלגוריתמים"

{{עריכה|הערך דורש הגהה, ויקיזציה וסידור חלק מהנוסחאות המתמטיות מופיעות בו|נושא=מחשוב|כל הערך=כן}}
'''אנליזה (ניתוח) של אלגוריתמים''' הוא תחום ב[[מדעי המחשב]], העוסק בגילוי מאפיינים שונים [[אלגוריתם|באלגוריתמים]], וסיווג רמת החיסכון שלהם במשאבים, כלומר קביעת כמות המשאבים הנדרשים עבור [[חישוב (מדעי המחשב)|ביצועו]].

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

המונח "ניתוח אלגוריתמים" נטבע על ידי [[דונלד קנות'|דונלד קונת']].{{הערה|[https://web.archive.org/web/20160828152021/http://www-cs-faculty.stanford.edu/~uno/news.html Donald Knuth, Recent News]}} ניתוח אלגוריתמים הוא חלק חשוב של [[תאוריה]] רחבה יותר הנקראת [[תורת הסיבוכיות]], אשר מספקת הערכות תאורטיות לכמות המשאבים הדרושים לכל אלגוריתם הפותר בעיה חישובית נתונה. הערכות אלו מספקות תובנות חשובות באשר לחיפוש אחר [[יעילות אלגוריתמית|אלגוריתמים יעילים]] יותר ויותר.

בניתוח תאורטי של אלגוריתמים, נהוג להעריך את המורכבות שלהם במובן [[אסימפטוטי]]. כלומר, להעריך את מורכבות האלגוריתם עבור קלט שרירותי גדול. [[סימון אסימפטוטי|סימון O גדולה]] [<math>O</math>], סימון אומגה גדול [<math>\Omega</math>] וסימון טטא גדול [<math>\Theta</math>] משמשים למטרה זו. למשל, [[חיפוש בינארי]] הוא חיפוש האמור לרוץ מספר צעדים, יחסי ללוגריתם של אורך הרשימה הממוינת שבה מתבצע החיפוש, או ב- <math>O(log(n))</math>, ב"[[סיבוכיות זמן|זמן לוגריתמי]]".

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

לדוגמה, אם ברשימה הממוינת עליה אנו מריצים חיפוש בינארי יש ''n'' אלמנטים, ואנחנו יכולים להבטיח כי כל בדיקה של אלמנט ברשימה יכולה להתבצע תוך יחידת זמן, אז צריך לכל היותר log<sub>2</sub> ''n'' + 1 יחידות זמן להחזיר תשובה.

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

יש שני מודלי חישוב עליות המשומשים בצורה נרחבת:{{הערה|שם=AhoHopcroft1974|{{cite book|title=The design and analysis of computer algorithms|publisher=Addison-Wesley Pub. Co.|year=1974|author1=Alfred V. Aho|author2=John E. Hopcroft|author3=Jeffrey D. Ullman}}}}{{הערה|שם=Hromkovič2004|{{cite book|url=https://books.google.com/books?id=KpNet-n262QC&pg=PA177|title=Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography|publisher=Springer|year=2004|isbn=978-3-540-14015-3|pages=177–178|author=Juraj Hromkovič}}}}{{הערה|שם=Ausiello1999|{{cite book|url=https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA3|title=Complexity and approximation: combinatorial optimization problems and their approximability properties|publisher=Springer|year=1999|isbn=978-3-540-65431-5|pages=3–8|author=Giorgio Ausiello}}}}{{הערה|שם=Wegener20|{{Citation|title=Complexity theory: exploring the limits of efficient algorithms|url=https://books.google.com/books?id=u7DZSDSUYlQC&pg=PA20|year=2005|last1=Wegener|first1=Ingo|page=20|location=Berlin, New York|publisher=[[Springer-Verlag]]|isbn=978-3-540-21045-0}}}}{{הערה|שם=Tarjan1983|{{cite book|url=https://books.google.com/books?id=JiC7mIqg-X4C&pg=PA3|title=Data structures and network algorithms|publisher=SIAM|year=1983|isbn=978-0-89871-187-5|pages=3–7|author=[[Robert Endre Tarjan]]}}}}
* '''מודל מחיר אחיד''', נקרא גם '''מדד עלות-אחיד''' (ווריאציות דומות), מקצה קבוע עלות לכל פעולת מכונה, ללא קשר לגודל של המספרים מעורבים.
* '''מודל עלות לוגריתמי''', נקרא גם '''מדד עלות-לוגריתמי''' (ווריאציות דומות), מקצה עלות כל פעולת מכונה באופן יחסי למספר הביטים המעורבים.
האחרון הוא יותר מסורבל לשימוש, לכן נעשה בו שימוש רק בעת הצורך, למשל בניתוח של אלגוריתמים מסוג דיוק-שרירותי אריתמטי, כמו אלה המשמשים ב[[קריפטוגרפיה]].

נקודת מפתח אשר נוטים להתעלם ממנה לעיתים קרובות היא ש[[חסם|חסמים תחתונים]] שפורסמו לבעיות לעיתים קרובות חושבו על מודל מחשוב אשר מוגבל יותר מאשר סט הפעולות שניתן להשתמש בו בפועל, ולכן יש אלגוריתמים מהירים יותר מאלה שניתן לדמיין בצורה נאיבית.{{הערה|[http://cstheory.stackexchange.com/questions/608/examples-of-the-price-of-abstraction Examples of the price of abstraction?], cstheory.stackexchange.com}}

== ניתוח זמן ריצה ==
[[קובץ:Comparison computational complexity.svg|250px|ממוזער|השוואת סיבוכיות]]
ניתוח זמן ריצה הוא סיווג תאורטי שמעריך וצופה את הגידול בזמן הריצה של אלגוריתם ככל שגודל הקלט שלו (לרוב מסומן כ-n) גדל. יעילות זמן ריצה היא נושא בעל חשיבות גבוהה במדעי המחשב: תוכנה יכולה לקחת שניות שעות או אפילו שנים כדי לסיים ביצוע, דבר שתלוי על איזה אלגוריתם היא מיישמת (ראו גם ניתוח ביצועים, כלומר הניתוח של זמן ריצה בצורה פרקטית).

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

ניתן לקחת כדוגמה תוכנה המחפשת ערך מסוים [[רשימה (מבנה נתונים)|רשימה ממוינת]] בגודל ''n''. נניח שתכנה זו הושמה על מחשב א', מחשב חדיש עם [[חומרה]] מרמה גבוהה, תוך שימוש באלגוריתם [[Linear search|חיפוש ליניארי]], ועל מחשב ב', אשר איטי בהרבה מן המחשב הקודם, באמצעות [[חיפוש בינארי|אלגוריתם חיפוש בינארי]]. [[בוחן ביצועים]] על שני המחשבים המריצים את התוכנה בהתאמה עשוי לקבל את הממצאים הבאים:
{| class="wikitable" style="margin-bottom: 10px;"
! ''n'' (גודל רשימה)
!זמן ריצה של מחשב א'<br>
(ננו שניות)
!זמן ריצה של מחשב ב'<br>
(ננו שניות)
|-
| 16
| 8
| 100,000
|-
| 63
| 32
| 150,000
|-
| 250
| 125
| 200,000
|-
| 1,000
| 500
| 250,000
|}
בהתבסס על ערכים אלה, זה ניתן לקפוץ למסקנה כי על '''מחשב א'''' פועל אלגוריתם יעיל בהרבה מיעילות של האלגוריתם של '''מחשב ב''''. עם זאת, אם נגדיל את גודל הקלט בצורה מספקת, מסקנה זו הוא מוכחת להיות שגיאה:
{| class="wikitable" style="margin-bottom: 34px;"
! ''n'' (גודל רשימה)
!זמן ריצה של מחשב א'
<br>
(ננו שניות)
!זמן ריצה של מחשב ב'<br>
(ננו שניות)
|-
| 16
| 8
| 100,000
|-
| 63
| 32
| 150,000
|-
| 250
| 125
| 200,000
|-
| 1,000
| 500
| 250,000
|-
| ...
| ...
| ...
|-
| 1,000,000
| 500,000
| 500,000
|-
| 4,000,000
| 2,000,000
| 550,000
|-
| 16,000,000
| 8,000,000
| 600,000
|-
| ...
| ...
| ...
|-
| 63,072 &#xD7; 10<sup>12</sup>
| 31,536 &#xD7; 10<sup>12</sup> ns,<br>
או 1 שנה
| 1,375,000 ns,<br>
או 1.375 מילישניות.
|}
מחשב א', מריץ את תוכנת החיפוש הליניארי, ומראה קצב גידול ליניארי. זמן הריצה של התוכנה הוא בעל יחס ישיר לגודל הקלט שלה. הכפלת גודל הקלט מכפיל את זמן הריצה, הכפלה פי ארבעה של גודל הקלט מכפילה פי ארבעה את זמן הריצה וכו' . מצד שני, מחשב ב', מריץ תוכנת חיפוש בינארי, ומראה קצב גידול [[לוגריתם|לוגריתמי]]. הכפלת גודל הקלט פי ארבעה מגדיל את זמן הריצה על ידי [[wiktionary:Constant|קבוע]] בלבד (בדוגמה זו, 50,000 ns). אף על פי שמחשב א' מהיר יותר, מאשר מחשב ב'. מחשב ב' יתגבר על מחשב א' באופן בלתי נמנע ביעילות זמן ריצה מפני שהאלגוריתם שהוא מריץ בעל קצב גידול נמוך בהרבה.

=== רמות של קצב גידול ===
באופן לא רשמי, ניתן לומר כי אלגוריתם מציג צמיחה בשיעור מסדר גודל של [[פונקציה|פונקציות מתמטיות]] אם עבור קלט מסוים בגודל ''n'', פונקציה <math>f(n)</math> כפול קבוע חיובי מספקת את החסם העליון או הגבול של זמן הריצה של האלגוריתם. במילים אחרות, עבור גודל קלט ''n'' אשר גדול יותר מ-''n''<sub>0</sub> וקבוע c, זמן הריצה של אלגוריתם לעולם לא יהיה גדול מאשר <math>c\times f(n)</math>. ביטוי זה מיוצג לעיתים קרובות על ידי סימון O גדולה. לדוגמה, כיוון שזמן הריצה של [[מיון הכנסה]] גדל בצורה מרובעת כמו שלה הקלט גדל, ההכנסה סוג יכול להיות אמר להיות של סדר ''O''(''n''<sup>2</sup>).

סימון O גדולה הוא דרך נוחה כדי לבטא את התרחיש הגרוע ביותר עבור אלגוריתם נתון, אף על פי שזה יכול לשמש גם כדי להביע את המקרה הממוצע &#x2014; לדוגמה, התרחיש הגרוע ביותר עבור [[מיון מהיר|quicksort]] הוא ''O''(''n''<sup>2</sup>), אבל זמן הריצה עבור המקרה הממוצע הוא ''O''(''n''&#x20;log&#x20;''n'').

=== רמות אמפיריות של קצב גידול ===
תחת ההנחה שזמן הביצוע עוקב אחר כלל הכוח,<math>t \approx k*n^a</math>, ניתן למצוא את המקדם{{הערה|[http://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ How To Avoid O-Abuse and Bribes], at the blog "Gödel’s Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick}} על ידי לקיחת מדידות אמפיריות של זמן ריצה <math>\{t_1, t_2\}</math> על נקודות בעלות גודל בעייתי <math>\{n_1, n_2\}</math> וחישוב <math>t_2/t_1 = (n_2/n_1)^a</math> כך <math>a = \log(t_2/t_1) / \log(n_2/n_1)</math>. במילים אחרות, זה מודד את השיפוע של קו אמפירי על log-log plot של זמן הביצוע לעומת גודל הבעיה, בנקודת גודל כלשהי. אם רמת הצמיחה אכן מלווה את כלל הכוח (אזי הקו על log-log-plot אכן [[ישר|קו ישר]]), הערך האמפירי של ''a'' יישאר קבוע בטווחים שונים, ואם לא, הוא ישתנה (ואז הקו הוא קו מעוגל) - אבל זה עדיין יכול לשמש להשוואה של כל שני אלגוריתמים נתונים בהתחשבות בהתנהגות של ''רמות קצב גידול מקומיות אמפיריות''. ובהחלה על הטבלה מלעיל:
{| class="wikitable" style="margin-bottom: 10px;"
! ''n'' (גודל רשימה)
!זמן הריצה של מחשב A<br>
(ננו שניות)
!רמת קצב גידול מקומית<br>
(n^_)
!זמן הריצה של מחשב B<br>
(ננו שניות)
!רמת קצב גידול מקומית<br>
(n^_)
|-
| 15
| 7
| 100,000
|-
| 65
| 32
| 1.04
| 150,000
| 0.28
|-
| 250
| 125
| 1.01
| 200,000
| 0.21
|-
| 1,000
| 500
| 1.00
| 250,000
| 0.16
|-
| ...
| ...
| ...
|-
| 1,000,000
| 500,000
| 1.00
| 500,000
| 0.10
|-
| 4,000,000
| 2,000,000
| 1.00
| 550,000
| 0.07
|-
| 16,000,000
| 8,000,000
| 1.00
| 600,000
| 0.06
|-
| ...
| ...
| ...
|}
קל לראות כי האלגוריתם הראשון מראה קצב גידול ליניארי אשר בבירור עוקב אחרי כלל הכוח. הערכים האמפיריים עבור השני הולכים ופוחתים במהירות, מה שרומז כי האלגוריתם השני עוקב אחרי חוק אחר של קצב גידול ובכל מקרה יש לו רמות קצב גידול מקומיות הרבה יותר נמוכות (אשר עדיין משתפרות), באופן אמפירי, מאשר לאלגוריתם הראשון.

=== הערכת סיבוכיות זמן ריצה ===
את מורכבות זמן הריצה למקרה הגרוע ביותר של אלגוריתם נתון ניתן לעיתים להעריך על ידי בחינת המבנה של האלגוריתם ולקיחת מספר הנחות מפשטות. נתבונן ב-[[פסאודו קוד|pseudocode]] הבא:
<syntaxhighlight lang="pascal" line="">
(* get a positive integer from input *)
if n > 10
 write 'This might take a while...'
for i = 1 to n
 for j = 1 to i
 write i * j
write 'Done!'
</syntaxhighlight>
מחשב נתון ייקח כמות הזמן בדידה לביצוע כל ה[[סט פקודות|פקודות]] המעורבות עם ביצוע האלגוריתם הזה. כמות הזמן המסוימת כדי לבצע פקודה נתונה ישתנו בהתאם לפקודה אשר מתבצעת, ועל פי איך המחשב מבצע אותה, אבל על מחשב רגיל, כמות זמן זו היא דטרמיניסטית (המקרה שונה במקרה של [[מחשב קוונטי]]). נניח כי הפעולות שבוצעו בשלב 1 נחשבות צורכות זמן ''T''<sub>1</sub>, אלה שבשלב 2 צורכות זמן ''T''<sub>2</sub>, וכך הלאה.

באלגוריתם לעיל, שלבים 1, 2 ו-7 ירוצו פעם אחת בלבד. עבור הערכה של המקרה הגרוע ביותר, יש להניח כי שלב 3 יורץ גם הוא. לפיכך, הסכום הכולל של זמן כדי להריץ את צעדים 1–3 וצעד 7 הוא:
:<math>T_1 + T_2 + T_3 + T_7. \,</math>
את ה[[בקרת זרימה|לולאות]] בשלבים 4, 5 ו-6 יותר מסובך להעריך. החיצונית בשלב 4 תרוץ (''n'' + 1)
פעמים (שימו לב כי צעד נוסף נדרש כדי לסיים את ללולאה, ולכן 1 + n ולא n ריצות), אשר יצרכו ''T''<sub>4</sub>(''n'' + 1) זמן. הלולאה הפנימית, לעומת זאת, נשלטת על ידי הערך של i, אשר [[איטרציה|נע]] מ-1 עד ''i''. במעבר הראשון דרך הלולאה החיצונית. j. נע מ-1 ל-1: הלולאה הפנימית רצה פעם אחת, אז הרצת הלולאה הפנימית (שלב 6) צורכת ''T''<sub>6</sub>, והלולאה הפנימית (שלב 5) צורכת 2''T''<sub>5. </sub>זמן. במעבר הבא דרך הלולאה החיצונית. j. נע מ-1 ל-2: לולאה הפנימית רצה פעמיים, אז הרצת הלולאה הפנימית (שלב 6) צורכת 2''T''<sub>6</sub>, והלולאה הפנימית (שלב 5) צורכת 3''T''<sub>5</sub> זמן.

בסך הכל, כל הזמן הנדרש כדי להפעיל את הלולאה הפנימית יכול לבוא לידי ביטוי כ[[סדרה חשבונית|התקדמות אריתמטית]]:
:<math>T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6</math>
אשר יכול להתווסף כ[[פירוק לגורמים|פקטור]] כך
<math>1 + 2 + 3 + \cdots + (n-1) + n = \frac{n(n+1)}{2}</math>
את הסך כל הזמן הנדרש כדי להפעיל את הלולאה החיצונית ניתן להעריך באופן דומה:
:<math>\begin{align}
& 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5\\
=\ &T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5
\end{align}</math>
אשר יכול להתווסף כפקטור כך
:<math>\begin{align}
& T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5 \\
=& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + (n + 1)T_5 - T_5 \\
=& T_5 \left[ \frac{1}{2} (n^2 + n) \right] + n T_5 \\
=& \left[ \frac{1}{2} (n^2 + 3n) \right] T_5
\end{align}</math>
לכן, סה"כ זמן ריצה עבור אלגוריתם זה הוא:
:<math>f(n) = T_1 + T_2 + T_3 + T_7 + (n + 1)T_4 + \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2+3n) \right] T_5 </math>
אשר יורד עד כדי
:<math>f(n) = \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7
</math>
כ[[כלל אצבע]], ניתן להניח שהסדר הגבוה ביותר בכל פונקציה שולט בקצב הצמיחה, ובכך מגדיר את סדר זמן הריצה. בדוגמה זו, n^2 הוא הסדר הגבוה ביותר, אז ניתן להסיק כי f(n) = O(n2). באופן רשמי, זה יכול להיות מוכח, כדלקמן:<blockquote class="">Prove that <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2,\ n \ge n_0</math>

<math>\begin{align}
&\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7\\
\le &(n^2 + n)T_6 + (n^2 + 3n)T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (\text{for } n \ge 0)
\end{align}</math>

Let ''k'' be a constant greater than or equal to [''T''<sub>1</sub>..''T''<sub>7</sub>]

<math>\begin{align}
&T_6(n^2 + n) + T_5(n^2 + 3n) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k(n^2 + n) + k(n^2 + 3n) + kn + 5k\\
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
\end{align}</math>

Therefore <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2, n \ge n_0 \text{ for } c = 12k, n_0 = 1</math>
</blockquote>גישה יותר אלגנטית לניתוח אלגוריתם זה תהיה להכריז כי [''T''<sub>1</sub>..''T''<sub>7</sub>] כל אחד שווים יחידת זמן אחת, במערכת של יחידות שנבחרו, כך שיחידה אחת הוא גדול או שווה לזמן בפועל פעמים של שלבים אלה. כלומר שזמן הריצה של האלגוריתם מחושב כדלקמן:<blockquote><math>4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2 \ (\text{for } n \ge 1) =O(n^2).</math></blockquote>

=== ניתוח קצב גידול של משאבים אחרים ===
ניתן להשתמש במתודולוגיה של ניתוח זמן ריצה לחישוב וחיזוי של קצבי הגידול של משאבים אחרים כגון צריכת זיכרון. כדוגמה, נתבונן ב־pseudocode אשר מנהל וממקם מחדש את השימוש בזיכרון על ידי תכנה, בהתבסס על הגודל של ה[[קובץ]] אשר התכנה מנהלת:
 <div style="direction: ltr;">'''while''' (''file still open'')</div><div style="direction: ltr;"> '''let''' n = ''size of file''</div><div style="direction: ltr;"> '''for''' ''every 100,000 kilobytes of increase in file size''</div><div style="direction: ltr;"> ''double the amount of memory reserved''</div>
במקרה הזה, ככל שגודל הקובץ n גדל, הזיכרון נצרך בקצב גידול מעריכי, אשר מסדר O(2<sup>n</sup>). זה מאוד מהיר ורוב הסיכויים קצב גידול לא ניתן לניהול של שימוש [[משאב מערכת|משאבי]] זיכרון.

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

== גורמים קבועים ==
אנליזה של אלגוריתמים בדרך כלל מתמקדת בביצועים אסימפטוטיים, במיוחד ברמה הבסיסית, אבל ביישומים מעשיים גורמים קבועים הם חשובים, ונתונים בעולם האמיתי תמיד מוגבלים בגודל בפועל. הגבול הוא בדרך כלל בגודל של זיכרון השמיש, אז על מערכות של 32 סיביות 2<sup>32</sup> = 4 GiB (או יותר אם [[מקטעי זיכרון|מזיכרון מקוטע]]), ובמערכות של-64 סיביות 2<sup>64</sup> = 16 EiB. לפיכך תחת גודל מוגבל, [[סדר גודל|סדר הגודל]] (זמן או מקום) יכול להיות מוחלף על ידי גורם קבוע, ובמובן זה כל האלגוריתמים המעשיים הם O(1) עבור קבוע מספיק גדול, או גודל נתונים קטן מספיק.

פרשנות זו היא יעילה בעיקר עבור פונקציות הגדלות לאט מאוד: (בינארית) [[לוגריתם חוזר|הלוגריתם החוזר]] (log<sup>*</sup>) הוא פחות מ-5 לכל כמות נתונים מעשית (2<sup>65536</sup> ביטים); (בינארי) log-log (log log ''n'') הוא פחות מ-6 לכמעט כל כמות נתונים מעשית (2<sup>64</sup> סיביות); ובינארית (log (log ''n'') הוא פחות מ-64 לכמעט כל כמות נתונים מעשית (2<sup>64</sup> סיביות). אלגוריתם עם מורכבות שאינה קבועה עשוי בכל זאת להיות יותר יעיל מאשר אלגוריתם קבוע על נתונים פרקטיים אם החסם העליות של הזמן הקבוע יוצר תוצאה קבועה גדולה יותר לדוגמה יכול להיות <math>K > k \log \log n</math> כל עוד <math>K/k > 6</math> ו-<math>n < 2^{2^6} = 2^{64}</math>.

עבור כמות גדולה של מידע לא ניתן להתעלם מגורמים ליניאריים או ריבועיים, אבל עבור כמויות קטנות של מידע אלגוריתם לא יעיל אסימפטוטית להיות יעיל יותר. זה במיוחד בשימוש במקרה של אלגוריתמים היברידיים, כמו Timsort, אשר משתמש באלגוריתם לא יעיל אסימפטוטית (כאן ב[[מיון מיזוג]], עם מורכבות הזמן <math>n \log n</math>), אבל מחליף לאלגוריתם יעיל אסימפטוטית (כאן [[מיון הכנסה|מיון החדרה]], עם מורכבות הזמן <math>n^2</math>) עבור כמות נתונים קטנה, כיוון שהאלגוריתם הפשוט יותר הוא מהיר יותר על כמות קטנה של נתונים.

== ראו גם==
* [[ניתוח לשיעורין]]
* [[סימון אסימפטוטי|O גדול]]
* [[תורת הסיבוכיות|תורת מורכבות חישובית]]
* [[שיטת האב|תיאורמת מאסטר]]
* [[אנליזה נומרית]]
* [[סיבוכיות זמן|פולינום זמן]]
* [[סילומיות|מדרגיות]]
* [[סיבוכיות זמן|מורכבות זמן]]

== לקריאה נוספת ==

<div class="mw-content-ltr">
* {{Cite book|title=Introduction to Algorithms|url=https://archive.org/details/introductiontoal00corm_691|last=Cormen|first=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald L.|last4=Stein|first4=Clifford|publisher=MIT Press and McGraw-Hill|others=Chapter 1: Foundations|year=2001|isbn=0-262-03293-7|edition=Second|location=Cambridge, MA|pages=[https://archive.org/details/introductiontoal00corm_691/page/n25 3]–122|author-link=Thomas H. Cormen|author-link2=Charles E. Leiserson|author-link3=Ronald L. Rivest|author-link4=Clifford Stein}}
* {{Cite book|title=Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching|last=Sedgewick|first=Robert|publisher=Addison-Wesley Professional|year=1998|isbn=978-0-201-31452-6|edition=3rd|location=Reading, MA|author-link=Robert Sedgewick (computer scientist)}}
* {{Cite book|title=The Art of Computer Programming|last=Knuth|first=Donald|publisher=Addison-Wesley|author-link=Donald Knuth}}
* {{Cite book|title=Mathematics for the Analysis of Algorithms|last=Greene|first=Daniel A.|last2=Knuth|first2=Donald E.|publisher=Birkhäuser|year=1982|isbn=3-7643-3102-X|edition=Second}}
* {{Cite book|title=Computational Complexity: A Conceptual Perspective|last=Goldreich|first=Oded|publisher=Cambridge University Press|year=2010|isbn=978-0-521-88473-0|author-link=Oded Goldreich}}

</div>

==קישורים חיצוניים==
* {{בריטניקה}}

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

{{מדעי המחשב}}
[[קטגוריה:סיבוכיות חישובית]]