סיבוכיות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה |
הגמל התימני (שיחה | תרומות) שכתוב טבלה (מיד אתקן כיווניות) |
||
שורה 8:
דוגמה זו ממחישה שלבעיות שונות עשויה להיות רמת סיבוכיות שונה. הטבלה הבאה מציגה רמות אחדות של סיבוכיות בסדר יעילות יורד (n הוא גודל הקלט, c הוא קבוע):
{| class="wikitable"
! שם !! סימון
|-
|קבוע
|align=left|O(1)
|-
|לוגריתמי
|align=left|O(log(n))
|-
|לינארי
|align=left| O(n)
|-
|
|align=left| O(nlog(n))
|-
|פולינומי
|align=left| O(n<sup>c</sup>)
|-
|מעריכי
|align=left|O(c<sup>n</sup>)
|-
|עצרתי
|align=left|O(n!)
|}
כאשר רמת הסיבוכיות של בעיה היא [[פולינום|פולינומית]] (או פחות מזה) הבעיה נחשבת כבעלת פתרון "[[חישוב יעיל|יעיל]]", משום שהגדלת אורך הקלט אינה מביאה לשינוי דרמטי בזמן הנחוץ לפתרון הבעיה. לעומת זאת, כאשר לבעיה סיבוכיות [[פונקציה מעריכית|מעריכית]] (אקספוננציאלית), שינוי קטן באורך הקלט מביא לשינוי מהותי בזמן הנחוץ לפתרון הבעיה. לדוגמה, כאשר הזמן הנחוץ לפתרונה של בעיה הוא <math>\ O(2^n)</math> (סיבוכיות מעריכית) הגדלת אורך הקלט ב-1 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה.
| |||