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