סיבוכיות

סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-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$.