סיבוכיות

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

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

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

דוגמא: אם $f(n)=n^3$ ו-$g(n)=2n^2$ אז לא קשה לראות ש-$f(n)=\Omega(g(n))$ ו-$g(n)=O(f(n))$ אבל לא מתקיים $f(n)=\Theta(g(n))$.

קצת אינטואיציה: $f(n)=O(g(n))$ אומר ש-$f$ גדלה כמו $g$ או פחות מכך (עד כדי כפל בקבוע). $f(n)=\Omega(g(n))$ אומר ש-$f$ גדלה כמו $g$ או יותר מכך (עד כדי כפל בקבוע).

הערה: כשכותבים $O(f(n))$ בחישובים (לדוגמא: $n+O(\lg n)$) בדרך כלל מתכוונים לפונקציה שהיא $O(f(n))$. הנ"ל נכון גם עבור $\Theta,\Omega,o$.

הערה: ההגדרות לעיל תקפות גם עבור פונקציות מ-$\mathbb{R}_{\geq 0}$ ל-$\mathbb{R}_{\geq 0}$

תכונות בסיסיות

נניח כי $f,g:\mathbb{N}\to\mathbb{R}_{\geq 0}$ אזי:

• $f(n)=O(f(n))$. כנ"ל עבור $\Theta,\Omega$. (זהירות: $f(n)\neq o(f(n))$!)
• $f(n)=O(g(n))$ אם ורק אם $g(n)=\Omega(f(n))$.
• $O(f(n))+O(g(n))=O(f(n)+g(n))$. כנ"ל עבור $\Theta,\Omega$.
• $O(f(n))\cdot O(g(n))=O(f(n)g(n))$. כנ"ל עבור $\Theta, \Omega$.
• $O(f(n))^\alpha=O(f(n)^\alpha)$ לכל $\alpha>0$. כנ"ל עבור $\Theta,\Omega$.
• היחס $f(n)=O(g(n))$ הוא טרנזיטיבי. (ניסוח אחר: $O(O(f(n)))=O(f(n))$.) כנ"ל עבור $\Theta,\Omega$.
• היחס $f(n)=\Theta(g(n))$ הוא יחס שקילות.
• $f(n)+o(f(n))=\Theta(f(n))$.

יחסים בין פונקציות נפוצות

• לכל $a,b,c>0$ ו-$d>1$ ממשיים מתקיים $\dots\ll (\ln\ln n)^a\ll (\ln n)^b\ll n^c\ll d^n\ll n!\ll n^n$.
• לכל $a<b$ ממשיים $n^a\ll n^b$.
• לכל $1\leq a<b$ ממשיים $a^n\ll b^n$.