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

גרסה מ־14:30, 31 באוקטובר 2011

סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-0).

הגדרה תהיינה $f,g:\mathbb{N}\to\mathbb{R}_{\geq 0}$ פונקציות אי שליליות מהטבעיים לממשיים.

נאמר ש- $f(n)=O(g(n))$ אם קיים $C>0$ ממשי ו- $n_0\in\mathbb{N}$ כך ש- $f(n)\leq Cg(n)$ לכל $n>n_0$ (הקבוע $C$ יכול להיות גדול כרצוננו).
נאמר ש- $f(n)=\Omega(g(n))$ אם קיים $C>0$ ממשי ו- $n_0\in\mathbb{N}$ כך ש- $f(n)\geq Cg(n)$ לכל $n>n_0$ (הקבוע $C$ יכול קטן גדול כרצוננו).
נאמר ש- $f(n)=\Theta(g(n))$ אם $f(n)=O(g(n))$ וגם $f(n)=\Omega(g(n))$ , כלומר קיימים $C_1,C_2>0$ ממשיים ו- $n_0\in\mathbb{N}$ כך ש- $C_1g(n)\leq f(n)\leq C_2g(n)$ לכל $n>n_0$ .

@@ שורה 2: / שורה 2: @@
-== או גדול, אומגה, תטה ואו קטן ==
+== או גדול, אומגה, תטה ==
 '''הגדרה''' תהיינה <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)=\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>.