סיבוכיות זמן – הבדלי גרסאות

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

 

=== זמן ריצה לינארי ===

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

 

== ראו גם ==

 

== קישורים חיצוניים ==

* [http://www.queue.co.il/ניתוח-זמן-ריצה/ ניתוח זמן ריצה] בQueue

 

[[קטגוריה:סיבוכיות]]