הבדלים בין גרסאות בדף "סיבוכיות"
מתוך Math-Wiki
(←תכונות בסיסיות) |
(←תכונות בסיסיות) |
||
שורה 22: | שורה 22: | ||
נניח כי <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(f(n))</math>. כנ"ל עבור <math>\Theta,\Omega</math>. (זהירות: <math>f(n)\neq o(f(n))</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>. |
גרסה מ־14:30, 3 בנובמבר 2011
סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-0).
או גדול, אומגה, תטה
הגדרה תהיינה פונקציות אי שליליות מהטבעיים לממשיים.
- נאמר ש-
אם קיים
ממשי ו-
כך ש-
לכל
(הקבוע
יכול להיות גדול כרצוננו).
- נאמר ש-
אם קיים
ממשי ו-
כך ש-
לכל
(הקבוע
יכול קטן גדול כרצוננו).
- נאמר ש-
אם
וגם
, כלומר קיימים
ממשיים ו-
כך ש-
לכל
.
לעיתים משתמשים גם בהגדה הבאה:
- נאמר ש-
(סימון אחר
) אם
. (הגדרה זו תקפה גם עבור פונקציות המקבלות ערכים שליליים ולכן הערך המוחלט.)
דוגמא: אם ו-
אז לא קשה לראות ש-
ו-
אבל לא מתקיים
.
קצת אינטואיציה: אומר ש-
גדלה כמו
או פחות מכך (עד כדי כפל בקבוע).
אומר ש-
גדלה כמו
או יותר מכך (עד כדי כפל בקבוע).
הערה: כשכותבים בחישובים (לדוגמא:
) בדרך כלל מתכוונים לפונקציה שהיא
. הנ"ל נכון גם עבור
.
הערה: ההגדרות לעיל תקפות גם עבור פונקציות מ- ל-
תכונות בסיסיות
נניח כי אזי:
. כנ"ל עבור
. (זהירות:
!)
אם ורק אם
.