סיבוכיות: הבדלים בין גרסאות בדף
(יצירת דף עם התוכן "סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפע...") |
אין תקציר עריכה |
||
| שורה 2: | שורה 2: | ||
== או גדול, אומגה, תטה | == או גדול, אומגה, תטה == | ||
'''הגדרה''' תהיינה <math>f,g:\mathbb{N}\to\mathbb{R}_{\geq 0}</math> פונקציות אי שליליות מהטבעיים לממשיים. | '''הגדרה''' תהיינה <math>f,g:\mathbb{N}\to\mathbb{R}_{\geq 0}</math> פונקציות אי שליליות מהטבעיים לממשיים. | ||
* נאמר ש-<math>f(n)=O(g(n))</math> אם קיים <math>C>0</math> ממשי ו-<math>n_0\in\mathbb{N}</math> כך ש-<math>f(n)\leq Cg(n)</math> לכל <math>n>n_0</math> (הקבוע <math>C</math> יכול להיות גדול כרצוננו). | * נאמר ש-<math>f(n)=O(g(n))</math> אם קיים <math>C>0</math> ממשי ו-<math>n_0\in\mathbb{N}</math> כך ש-<math>f(n)\leq Cg(n)</math> לכל <math>n>n_0</math> (הקבוע <math>C</math> יכול להיות גדול כרצוננו). | ||
* נאמר ש-<math>f(n)=\Omega(g(n))</math> אם קיים <math>C>0</math> ממשי ו-<math>n_0\in\mathbb{N}</math> כך ש-<math>f(n)\geq Cg(n)</math> לכל <math>n>n_0</math> (הקבוע <math>C</math> יכול קטן גדול כרצוננו). | * נאמר ש-<math>f(n)=\Omega(g(n))</math> אם קיים <math>C>0</math> ממשי ו-<math>n_0\in\mathbb{N}</math> כך ש-<math>f(n)\geq Cg(n)</math> לכל <math>n>n_0</math> (הקבוע <math>C</math> יכול קטן גדול כרצוננו). | ||
* נאמר ש-<math>f(n)=\Theta(g(n))</math> אם <math>f(n)=O(g(n))</math> וגם <math>f(n)=\Omega(g(n))</math>, כלומר קיימים <math>C_1,C_2>0</math> ממשיים ו-<math>n_0\in\mathbb{N}</math> כך ש-<math>C_1g(n)\leq f(n)\leq C_2g(n)</math> לכל <math>n>n_0</math>. | * נאמר ש-<math>f(n)=\Theta(g(n))</math> אם <math>f(n)=O(g(n))</math> וגם <math>f(n)=\Omega(g(n))</math>, כלומר קיימים <math>C_1,C_2>0</math> ממשיים ו-<math>n_0\in\mathbb{N}</math> כך ש-<math>C_1g(n)\leq f(n)\leq C_2g(n)</math> לכל <math>n>n_0</math>. | ||
גרסה מ־14:30, 31 באוקטובר 2011
סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-0).
או גדול, אומגה, תטה
הגדרה תהיינה [math]\displaystyle{ f,g:\mathbb{N}\to\mathbb{R}_{\geq 0} }[/math] פונקציות אי שליליות מהטבעיים לממשיים.
- נאמר ש-[math]\displaystyle{ f(n)=O(g(n)) }[/math] אם קיים [math]\displaystyle{ C\gt 0 }[/math] ממשי ו-[math]\displaystyle{ n_0\in\mathbb{N} }[/math] כך ש-[math]\displaystyle{ f(n)\leq Cg(n) }[/math] לכל [math]\displaystyle{ n\gt n_0 }[/math] (הקבוע [math]\displaystyle{ C }[/math] יכול להיות גדול כרצוננו).
- נאמר ש-[math]\displaystyle{ f(n)=\Omega(g(n)) }[/math] אם קיים [math]\displaystyle{ C\gt 0 }[/math] ממשי ו-[math]\displaystyle{ n_0\in\mathbb{N} }[/math] כך ש-[math]\displaystyle{ f(n)\geq Cg(n) }[/math] לכל [math]\displaystyle{ n\gt n_0 }[/math] (הקבוע [math]\displaystyle{ C }[/math] יכול קטן גדול כרצוננו).
- נאמר ש-[math]\displaystyle{ f(n)=\Theta(g(n)) }[/math] אם [math]\displaystyle{ f(n)=O(g(n)) }[/math] וגם [math]\displaystyle{ f(n)=\Omega(g(n)) }[/math], כלומר קיימים [math]\displaystyle{ C_1,C_2\gt 0 }[/math] ממשיים ו-[math]\displaystyle{ n_0\in\mathbb{N} }[/math] כך ש-[math]\displaystyle{ C_1g(n)\leq f(n)\leq C_2g(n) }[/math] לכל [math]\displaystyle{ n\gt n_0 }[/math].