סיבוכיות זמן – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תמונה |
←פתיח: צמצום כפילויות |
||
שורה 1:
[[קובץ:Comparison computational complexity.svg|300px|ממוזער|פונקציות הנפוצות ב[[ניתוח אלגוריתמים]] המציגות את מספר הפעולות הנדרשות לפונקציה לעומת גודל הקלט]]
בתורת ה[[חישוביות]], '''סיבוכיות זמן''' של [[אלגוריתם]] היא הערכה, באמצעות [[חסם|חסמים]], על מספר הפעולות שמבצע האלגוריתם
אין בוחנים את זמן הריצה ביחידות זמן (כגון שניות), משום שמשך הזמן לביצוע פעולה תלוי ב[[מודל חישובי|מודל החישובי]] וב[[מחשב]] שעליו רץ האלגוריתם. למשל, ייתכן שבמודל או בארכיטקטורה מסוימת ניתן [[חילוק|לחלק]] שני מספרים בצעד אחד, ואילו במודל או ארכיטקטורה אחרת יידרשו לאותה פעולה מספר צעדים. משום כך, בניתוח הסיבוכיות של אלגוריתם מקובל להביא בחשבון רק את סדרי הגודל, ולהתעלם מקבועים. למשל, אלגוריתם המבצע 8n+112 פעולות על קלט בגודל n הוא בעל "[[סיבוכיות_זמן#זמן_ריצה_ליניארי|זמן ריצה ליניארי]]".
הסימון הרווח לזמן הריצה של אלגוריתמים הוא:
| |||