סיבוכיות זמן

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

לכן, במדעי המחשב נוטים להתעלם מקבועים בעת התיחסות לסיבוכיות זמן ריצה של אלגוריתם, ולומר, למשל, כי הן אלגוריתם שדורש 8n צעדים על קלטים ממורכבות n, והן אלגוריתם שדורש 112n צעדים על קלטים כאלו הינם שניהם אלגוריתמים בעלי זמן ריצה לינארי.

הסימון הרווח לזמן הריצה של אלגוריתמים הינו:

$\Theta\left(f(n)\right)$	זמן ריצה פרופורציונלי, עד כדי קבוע, לפונקציה $f\left(n\right)$
$O\left(f(n)\right)$	זמן ריצה שאינו עולה על הפונקציה $f\left(n\right)$ , עד כדי קבוע
$\Omega\left(f(n)\right)$	זמן ריצה שאינו פוחת מהפונקציה $f\left(n\right)$ , עד כדי קבוע