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