סיבוכיות: הבדלים בין גרסאות בדף
(3 גרסאות ביניים של אותו משתמש אינן מוצגות) | |||
שורה 26: | שורה 26: | ||
* <math>O(f(n))\cdot O(g(n))=O(f(n)g(n))</math>. כנ"ל עבור <math>\Theta, \Omega</math>. | * <math>O(f(n))\cdot O(g(n))=O(f(n)g(n))</math>. כנ"ל עבור <math>\Theta, \Omega</math>. | ||
* <math>O(f(n))^\alpha=O(f(n)^\alpha)</math> לכל <math>\alpha>0</math>. כנ"ל עבור <math>\Theta,\Omega</math>. | * <math>O(f(n))^\alpha=O(f(n)^\alpha)</math> לכל <math>\alpha>0</math>. כנ"ל עבור <math>\Theta,\Omega</math>. | ||
* היחס <math>f(n)=O(g(n))</math> הוא טרנזיטיבי. (ניסוח אחר: <math>O(O(f(n)))=O(f(n))</math>.) כנ"ל עבור <math>\Omega</math>. | * היחס <math>f(n)=O(g(n))</math> הוא טרנזיטיבי. (ניסוח אחר: <math>O(O(f(n)))=O(f(n))</math>.) כנ"ל עבור <math>\Theta,\Omega</math>. | ||
* היחס <math>f(n)=\Theta(g(n))</math> הוא יחס שקילות. | * היחס <math>f(n)=\Theta(g(n))</math> הוא יחס שקילות. | ||
* <math>f(n)+o(f(n))=\Theta(f(n))</math>. | * <math>f(n)+o(f(n))=\Theta(f(n))</math>. | ||
== יחסים בין פונקציות נפוצות == | |||
* לכל <math>a,b,c>0</math> ו-<math>d>1</math> ממשיים מתקיים <math>\dots\ll (\ln\ln n)^a\ll (\ln n)^b\ll n^c\ll d^n\ll n!\ll n^n</math>. | |||
* לכל <math>a<b</math> ממשיים <math>n^a\ll n^b</math>. | |||
* לכל <math>1\leq a<b</math> ממשיים <math>a^n\ll b^n</math>. |
גרסה אחרונה מ־11:53, 24 בנובמבר 2011
סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-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].
קצת אינטואיציה: [math]\displaystyle{ f(n)=O(g(n)) }[/math] אומר ש-[math]\displaystyle{ f }[/math] גדלה כמו [math]\displaystyle{ g }[/math] או פחות מכך (עד כדי כפל בקבוע). [math]\displaystyle{ f(n)=\Omega(g(n)) }[/math] אומר ש-[math]\displaystyle{ f }[/math] גדלה כמו [math]\displaystyle{ g }[/math] או יותר מכך (עד כדי כפל בקבוע).
הערה: כשכותבים [math]\displaystyle{ O(f(n)) }[/math] בחישובים (לדוגמא: [math]\displaystyle{ n+O(\lg n) }[/math]) בדרך כלל מתכוונים לפונקציה שהיא [math]\displaystyle{ O(f(n)) }[/math]. הנ"ל נכון גם עבור [math]\displaystyle{ \Theta,\Omega,o }[/math].
הערה: ההגדרות לעיל תקפות גם עבור פונקציות מ-[math]\displaystyle{ \mathbb{R}_{\geq 0} }[/math] ל-[math]\displaystyle{ \mathbb{R}_{\geq 0} }[/math]
תכונות בסיסיות
נניח כי [math]\displaystyle{ f,g:\mathbb{N}\to\mathbb{R}_{\geq 0} }[/math] אזי:
- [math]\displaystyle{ f(n)=O(f(n)) }[/math]. כנ"ל עבור [math]\displaystyle{ \Theta,\Omega }[/math]. (זהירות: [math]\displaystyle{ f(n)\neq o(f(n)) }[/math]!)
- [math]\displaystyle{ f(n)=O(g(n)) }[/math] אם ורק אם [math]\displaystyle{ g(n)=\Omega(f(n)) }[/math].
- [math]\displaystyle{ O(f(n))+O(g(n))=O(f(n)+g(n)) }[/math]. כנ"ל עבור [math]\displaystyle{ \Theta,\Omega }[/math].
- [math]\displaystyle{ O(f(n))\cdot O(g(n))=O(f(n)g(n)) }[/math]. כנ"ל עבור [math]\displaystyle{ \Theta, \Omega }[/math].
- [math]\displaystyle{ O(f(n))^\alpha=O(f(n)^\alpha) }[/math] לכל [math]\displaystyle{ \alpha\gt 0 }[/math]. כנ"ל עבור [math]\displaystyle{ \Theta,\Omega }[/math].
- היחס [math]\displaystyle{ f(n)=O(g(n)) }[/math] הוא טרנזיטיבי. (ניסוח אחר: [math]\displaystyle{ O(O(f(n)))=O(f(n)) }[/math].) כנ"ל עבור [math]\displaystyle{ \Theta,\Omega }[/math].
- היחס [math]\displaystyle{ f(n)=\Theta(g(n)) }[/math] הוא יחס שקילות.
- [math]\displaystyle{ f(n)+o(f(n))=\Theta(f(n)) }[/math].
יחסים בין פונקציות נפוצות
- לכל [math]\displaystyle{ a,b,c\gt 0 }[/math] ו-[math]\displaystyle{ d\gt 1 }[/math] ממשיים מתקיים [math]\displaystyle{ \dots\ll (\ln\ln n)^a\ll (\ln n)^b\ll n^c\ll d^n\ll n!\ll n^n }[/math].
- לכל [math]\displaystyle{ a\lt b }[/math] ממשיים [math]\displaystyle{ n^a\ll n^b }[/math].
- לכל [math]\displaystyle{ 1\leq a\lt b }[/math] ממשיים [math]\displaystyle{ a^n\ll b^n }[/math].