הבדלים בין גרסאות בדף "סיבוכיות"
מתוך Math-Wiki
(←יחסים בין פונקציות נפוצות) |
(←יחסים בין פונקציות נפוצות) |
||
שורה 33: | שורה 33: | ||
== יחסים בין פונקציות נפוצות == | == יחסים בין פונקציות נפוצות == | ||
− | * לכל <math>a,b,c | + | * לכל <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>a<b</math> ממשיים <math>n^a\ll n^b</math>. | ||
* לכל <math>1\leq a<b</math> ממשיים <math>a^n\ll b^n</math>. | * לכל <math>1\leq a<b</math> ממשיים <math>a^n\ll b^n</math>. |
גרסה אחרונה מ־11:53, 24 בנובמבר 2011
סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-0).
או גדול, אומגה, תטה
הגדרה תהיינה פונקציות אי שליליות מהטבעיים לממשיים.
- נאמר ש-
אם קיים
ממשי ו-
כך ש-
לכל
(הקבוע
יכול להיות גדול כרצוננו).
- נאמר ש-
אם קיים
ממשי ו-
כך ש-
לכל
(הקבוע
יכול קטן גדול כרצוננו).
- נאמר ש-
אם
וגם
, כלומר קיימים
ממשיים ו-
כך ש-
לכל
.
לעיתים משתמשים גם בהגדה הבאה:
- נאמר ש-
(סימון אחר
) אם
. (הגדרה זו תקפה גם עבור פונקציות המקבלות ערכים שליליים ולכן הערך המוחלט.)
דוגמא: אם ו-
אז לא קשה לראות ש-
ו-
אבל לא מתקיים
.
קצת אינטואיציה: אומר ש-
גדלה כמו
או פחות מכך (עד כדי כפל בקבוע).
אומר ש-
גדלה כמו
או יותר מכך (עד כדי כפל בקבוע).
הערה: כשכותבים בחישובים (לדוגמא:
) בדרך כלל מתכוונים לפונקציה שהיא
. הנ"ל נכון גם עבור
.
הערה: ההגדרות לעיל תקפות גם עבור פונקציות מ- ל-
תכונות בסיסיות
נניח כי אזי:
. כנ"ל עבור
. (זהירות:
!)
אם ורק אם
.
-
. כנ"ל עבור
.
-
. כנ"ל עבור
.
-
לכל
. כנ"ל עבור
.
- היחס
הוא טרנזיטיבי. (ניסוח אחר:
.) כנ"ל עבור
.
- היחס
הוא יחס שקילות.
-
.
יחסים בין פונקציות נפוצות
- לכל
ו-
ממשיים מתקיים
.
- לכל
ממשיים
.
- לכל
ממשיים
.