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