הבדלים בין גרסאות בדף "סיבוכיות"
מתוך Math-Wiki
(←או גדול, אומגה, תטה) |
(←או גדול, אומגה, תטה) |
||
שורה 12: | שורה 12: | ||
'''דוגמא:''' אם <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)=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>O(f(n))</math> בחישובים (לדוגמא: <math>n+O(\lg n)</math>) בדרך כלל מתכוונים לפונקציה שהיא <math>O(f(n))</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>. |
גרסה מ־14:23, 3 בנובמבר 2011
סיבוכיות היא דרך להשוות בין קצב גידול של פונקציות ממשיות. הסיבוכיות של פונקציה אינה מושפעת מהכפלתה בקבוע (גדול מ-0).
או גדול, אומגה, תטה
הגדרה תהיינה פונקציות אי שליליות מהטבעיים לממשיים.
- נאמר ש-
אם קיים
ממשי ו-
כך ש-
לכל
(הקבוע
יכול להיות גדול כרצוננו).
- נאמר ש-
אם קיים
ממשי ו-
כך ש-
לכל
(הקבוע
יכול קטן גדול כרצוננו).
- נאמר ש-
אם
וגם
, כלומר קיימים
ממשיים ו-
כך ש-
לכל
.
לעיתים משתמשים גם בהגדה הבאה:
- נאמר ש-
(סימון אחר
) אם
. (הגדרה זו תקפה גם עבור פונקציות המקבלות ערכים שליליים ולכן הערך המוחלט.)
דוגמא: אם ו-
אז לא קשה לראות ש-
ו-
אבל לא מתקיים
.
הערה: כשכותבים בחישובים (לדוגמא:
) בדרך כלל מתכוונים לפונקציה שהיא
. הנ"ל נכון גם עבור
.
הערה: ההגדרות לעיל תקפות גם עבור פונקציות מ- ל-
תכונות בסיסיות
נניח כי אזי:
. כנ"ל עבור
.