סיבוכיות זמן – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←זמן ריצה מעריכי: הרחבה |
|||
שורה 38:
מקובל לקשר זמן ריצה פולינומי עם [[חישוב יעיל]], כך ש[[אלגוריתם]] ייחשב יעיל אם זמן הריצה שלו פולינומי. מעשית, לא כל זמן ריצה פולינומי מעיד על יעילות, שכן קיימים פולינומים בעלי חזקות גבוהות - בעת פיתוח אלגוריתם נעדיף זמן ריצה פולינומי מסדר נמוך, כגון זמן ליניארי או ריבועי.
=== זמן ריצה מעריכי (אקספוננציאלי) ===
סיבוכיות זמן הריצה של אלגוריתם היא מעריכית אם ורק אם [[פונקציה|פונקציית]] זמן הריצה שלו [[חסם|חסומה]] על ידי [[פונקציה מעריכית]] (k<sup>n</sup>) כפול קבוע, כאשר בסיס הפונקציה המעריכית (k) גדול מ-1.
| |||