הבדלים בין גרסאות בדף "סיבוכיות"
מתוך Math-Wiki
(יצירת דף עם התוכן "סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפע...") |
(←יחסים בין פונקציות נפוצות) |
||
| (13 גרסאות ביניים של אותו משתמש אינן מוצגות) | |||
| שורה 2: | שורה 2: | ||
| − | == או גדול, אומגה, תטה | + | == או גדול, אומגה, תטה == |
'''הגדרה''' תהיינה <math>f,g:\mathbb{N}\to\mathbb{R}_{\geq 0}</math> פונקציות אי שליליות מהטבעיים לממשיים. | '''הגדרה''' תהיינה <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)=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)=\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>. | * נאמר ש-<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>. | ||
| + | לעיתים משתמשים גם בהגדה הבאה: | ||
| + | * נאמר ש-<math>f(n)=o(g(n))</math> (סימון אחר <math>f(n)\ll g(n)</math>) אם <math>\lim_{n\to\infty}\left|\frac{f(n)}{g(n)}\right|=0</math>. (הגדרה זו תקפה גם עבור פונקציות המקבלות ערכים שליליים ולכן הערך המוחלט.) | ||
| + | |||
| + | '''דוגמא:''' אם <math>f(n)=n^3</math> ו-<math>g(n)=2n^2</math> אז לא קשה לראות ש-<math>f(n)=\Omega(g(n))</math> ו-<math>g(n)=O(f(n))</math> אבל לא מתקיים <math>f(n)=\Theta(g(n))</math>. | ||
| + | |||
| + | '''קצת אינטואיציה:''' <math>f(n)=O(g(n))</math> אומר ש-<math>f</math> גדלה כמו <math>g</math> או פחות מכך (עד כדי כפל בקבוע). <math>f(n)=\Omega(g(n))</math> אומר ש-<math>f</math> גדלה כמו <math>g</math> או יותר מכך (עד כדי כפל בקבוע). | ||
| + | |||
| + | '''הערה:''' כשכותבים <math>O(f(n))</math> בחישובים (לדוגמא: <math>n+O(\lg n)</math>) בדרך כלל מתכוונים לפונקציה שהיא <math>O(f(n))</math>. הנ"ל נכון גם עבור <math>\Theta,\Omega,o</math>. | ||
| + | |||
| + | '''הערה:''' ההגדרות לעיל תקפות גם עבור פונקציות מ-<math>\mathbb{R}_{\geq 0}</math> ל-<math>\mathbb{R}_{\geq 0}</math> | ||
| + | |||
| + | == תכונות בסיסיות == | ||
| + | |||
| + | נניח כי <math>f,g:\mathbb{N}\to\mathbb{R}_{\geq 0}</math> אזי: | ||
| + | *<math>f(n)=O(f(n))</math>. כנ"ל עבור <math>\Theta,\Omega</math>. (זהירות: <math>f(n)\neq o(f(n))</math>!) | ||
| + | *<math>f(n)=O(g(n))</math> אם ורק אם <math>g(n)=\Omega(f(n))</math>. | ||
| + | * <math>O(f(n))+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>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)+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).
או גדול, אומגה, תטה
הגדרה תהיינה 
פונקציות אי שליליות מהטבעיים לממשיים.
- נאמר ש-
אם קיים 
ממשי ו-
כך ש-
לכל 
(הקבוע 
יכול להיות גדול כרצוננו). - נאמר ש-
אם קיים ממשי ו- כך ש-
לכל (הקבוע יכול קטן גדול כרצוננו). - נאמר ש-
אם וגם , כלומר קיימים 
ממשיים ו- כך ש-
לכל .
לעיתים משתמשים גם בהגדה הבאה:
- נאמר ש-
(סימון אחר 
) אם 
. (הגדרה זו תקפה גם עבור פונקציות המקבלות ערכים שליליים ולכן הערך המוחלט.)
דוגמא: אם 
ו-
אז לא קשה לראות ש- ו-
אבל לא מתקיים .
קצת אינטואיציה: אומר ש-
גדלה כמו 
או פחות מכך (עד כדי כפל בקבוע). אומר ש- גדלה כמו או יותר מכך (עד כדי כפל בקבוע).
הערה: כשכותבים 
בחישובים (לדוגמא: 
) בדרך כלל מתכוונים לפונקציה שהיא . הנ"ל נכון גם עבור 
.
הערה: ההגדרות לעיל תקפות גם עבור פונקציות מ-
ל-
תכונות בסיסיות
נניח כי אזי:
. כנ"ל עבור 
. (זהירות: 
!)- אם ורק אם
. -
. כנ"ל עבור . -
. כנ"ל עבור . -
לכל 
. כנ"ל עבור . - היחס הוא טרנזיטיבי. (ניסוח אחר:
.) כנ"ל עבור . - היחס הוא יחס שקילות.
-
.
יחסים בין פונקציות נפוצות
- לכל
ו-
ממשיים מתקיים 
. - לכל
ממשיים 
. - לכל
ממשיים 
.
