הבדלים בין גרסאות בדף "סיבוכיות"

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

תפריט ניווט