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

הוסרו 523 בתים ,  לפני 11 שנים
שכתוב טבלה (מיד אתקן כיווניות)
מ
(שכתוב טבלה (מיד אתקן כיווניות))
 
דוגמה זו ממחישה שלבעיות שונות עשויה להיות רמת סיבוכיות שונה. הטבלה הבאה מציגה רמות אחדות של סיבוכיות בסדר יעילות יורד (n הוא גודל הקלט, c הוא קבוע):
 
<TABLE cellpadding=5 border=1 dir="ltr">
{| class="wikitable"
<TR><TD align=center>סימון</TD><TD>שם</TD></TR>
! שם !! סימון
<TR><TD align=center><math>O(1)</math></TD><TD align=center>קבוע</TD></TR>
|-
<TR><TD align=center><math>O(log(n))</math></TD><TD align=center>[[זמן ריצה לוגריתמי|לוגריתמי]]</TD></TR>
|קבוע
<TR><TD align=center><math>O(n)</math></TD><TD align=center>[[זמן ריצה לינארי|לינארי]]</TD></TR>
|align=left|O(1)
<TR><TD align=center><math>O(n log(n))</math></TD><TD align=center>&nbsp;</TD></TR>
|-
<TR><TD align=center><math>O(n^c)</math></TD><TD align=center>[[זמן ריצה פולינומי|פולינומי]]</TD></TR>
|לוגריתמי
<TR><TD align=center><math>O(c^n)</math></TD><TD align=center>[[זמן ריצה מעריכי|מעריכי]]</TD></TR>
|align=left|O(log(n))
<TR><TD align=center><math>O(n!)</math></TD><TD align=center>עצרתי</TD></TR>
|-
</TABLE>
|לינארי
|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 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה.