סיבוכיות זמן ריצה
- פותח הנושא ASHY
- פורסם בתאריך
בדיוק כך
סיבוכיות זמן-הריצה היא פונקציה שמראה כמה פעולות חישוב דרושות על מנת לבצע פעולה ביחס לגודל הקלט. לדוגמא: בשביל למצוא את האיבר המינימלי במערך בגודל n איברים צריך לעבור על כולם - כלומר לבצע n פעולות, ולכן הסיבוכיות תהא (O(n. בשביל הדפיס את לוח הכפל עבור n מספרים נצטרך לבצע n בריבוע פעולות (n שורות עם n איברים בכל אחת).
סיבוכיות זמן-הריצה היא פונקציה שמראה כמה פעולות חישוב דרושות על מנת לבצע פעולה ביחס לגודל הקלט. לדוגמא: בשביל למצוא את האיבר המינימלי במערך בגודל n איברים צריך לעבור על כולם - כלומר לבצע n פעולות, ולכן הסיבוכיות תהא (O(n. בשביל הדפיס את לוח הכפל עבור n מספרים נצטרך לבצע n בריבוע פעולות (n שורות עם n איברים בכל אחת).
הייתי מוסיף - קצת יותר פורמלית
עבור פונקציה g(x) , נגדיר את O(g(x)) d (די בשביל ליישר את הכתב), כקבוצת כל הפונקציות שנחסמות מלעמעלה ע"י כפולה של g(x) בקבוע החל מ x0 מסוים. כלומר, אם קיים a ו x0 כך שלכל x>x0, מתקיים f(x)<=a*g(x) d, נאמר כי f(x) = O
(מסמנים שווה מטעמי נוחות, אך המשמעות היא שייכות לקבוצה) כמו כן ישנו סימון של אומגה גדולה, לחסימה מלמטה, ותטא גדולה אם הפונקציה שייכת גם לאו, וגם לאומגה.
עבור פונקציה g(x) , נגדיר את O(g(x)) d (די בשביל ליישר את הכתב), כקבוצת כל הפונקציות שנחסמות מלעמעלה ע"י כפולה של g(x) בקבוע החל מ x0 מסוים. כלומר, אם קיים a ו x0 כך שלכל x>x0, מתקיים f(x)<=a*g(x) d, נאמר כי f(x) = O
(מסמנים שווה מטעמי נוחות, אך המשמעות היא שייכות לקבוצה) כמו כן ישנו סימון של אומגה גדולה, לחסימה מלמטה, ותטא גדולה אם הפונקציה שייכת גם לאו, וגם לאומגה.Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.