סיבוכיות

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

לעיתים משתמשים גם בהגדה הבאה:

• נאמר ש-[math]\displaystyle{ f(n)=o(g(n)) }[/math] (סימון אחר [math]\displaystyle{ f(n)\ll g(n) }[/math]) אם [math]\displaystyle{ \lim_{n\to\infty}\left|\frac{f(n)}{g(n)}\right|=0 }[/math]. (הגדרה זו תקפה גם עבור פונקציות המקבלות ערכים שליליים ולכן הערך המוחלט.)

דוגמא: אם [math]\displaystyle{ f(n)=n^3 }[/math] ו-[math]\displaystyle{ g(n)=2n^2 }[/math] אז לא קשה לראות ש-[math]\displaystyle{ f(n)=\Omega(g(n)) }[/math] ו-[math]\displaystyle{ g(n)=O(f(n)) }[/math] אבל לא מתקיים [math]\displaystyle{ f(n)=\Theta(g(n)) }[/math].