שינויים

קפיצה אל: ניווט, חיפוש

סיבוכיות

נוספו 1,196 בתים, 14:29, 31 באוקטובר 2011
יצירת דף עם התוכן "סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפע..."
סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-0).


== או גדול, אומגה, תטה ואו קטן ==
'''הגדרה''' תהיינה <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>.
485
עריכות