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