הבדלים בין גרסאות בדף "סיבוכיות"
מתוך Math-Wiki
(←תכונות בסיסיות) |
(←יחסים בין פונקציות נפוצות) |
||
(4 גרסאות ביניים של אותו משתמש אינן מוצגות) | |||
שורה 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>\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).
או גדול, אומגה, תטה
הגדרה תהיינה פונקציות אי שליליות מהטבעיים לממשיים.
- נאמר ש- אם קיים ממשי ו- כך ש- לכל (הקבוע יכול להיות גדול כרצוננו).
- נאמר ש- אם קיים ממשי ו- כך ש- לכל (הקבוע יכול קטן גדול כרצוננו).
- נאמר ש- אם וגם , כלומר קיימים ממשיים ו- כך ש- לכל .
לעיתים משתמשים גם בהגדה הבאה:
- נאמר ש- (סימון אחר ) אם . (הגדרה זו תקפה גם עבור פונקציות המקבלות ערכים שליליים ולכן הערך המוחלט.)
דוגמא: אם ו- אז לא קשה לראות ש- ו- אבל לא מתקיים .
קצת אינטואיציה: אומר ש- גדלה כמו או פחות מכך (עד כדי כפל בקבוע). אומר ש- גדלה כמו או יותר מכך (עד כדי כפל בקבוע).
הערה: כשכותבים בחישובים (לדוגמא: ) בדרך כלל מתכוונים לפונקציה שהיא . הנ"ל נכון גם עבור .
הערה: ההגדרות לעיל תקפות גם עבור פונקציות מ- ל-
תכונות בסיסיות
נניח כי אזי:
- . כנ"ל עבור . (זהירות: !)
- אם ורק אם .
- . כנ"ל עבור .
- . כנ"ל עבור .
- לכל . כנ"ל עבור .
- היחס הוא טרנזיטיבי. (ניסוח אחר: .) כנ"ל עבור .
- היחס הוא יחס שקילות.
- .
יחסים בין פונקציות נפוצות
- לכל ו- ממשיים מתקיים .
- לכל ממשיים .
- לכל ממשיים .