הסבר על תטא ביג וסימן אסימפטוטי

אומגה גדולה מספרת לנו את הגבול התחתון של זמן הריצה של פונקציה, ו- Big O אומר לנו את הגבול העליון.

לעתים קרובות, הם שונים ואנחנו לא יכולים להבטיח זמן ריצה - זה ישתנה בין שני הגבולות והתשומות. אבל מה קורה כשהם זהים? אז אנחנו יכולים לתת תטא (Θ) מאוגד - הפונקציה שלנו תפעל באותה תקופה, לא משנה איזה קלט אנחנו נותנים לה.

באופן כללי, אנחנו תמיד רוצים לתת תטא קשור במידת האפשר מכיוון שהוא הכרוך המדויק והדוק ביותר. אם אנחנו לא יכולים לתת תטא קשור, הדבר הבא הכי טוב הוא ה- O הקשור הכי חזק שאפשר.

קח לדוגמא פונקציה המחפשת במערך את הערך 0:

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false

1. מה המקרה הטוב ביותר? ובכן, אם למערך שאנו נותנים לו 0 את הערך הראשון, זה ייקח זמן קבוע: Ω (1)
2. מה המקרה הגרוע ביותר? אם המערך אינו מכיל 0, נקבל את כל המערך: O (n)

נתנו לו אומגה ו- O מאוגד, אז מה עם תטא? אנחנו לא יכולים לתת לזה אחד! בהתאם למערך שאנו נותנים לו, זמן הריצה יהיה איפשהו בין קבוע ליניארי.

בואו ונשנה קצת את הקוד שלנו.

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

אתה יכול לחשוב על המקרה הטוב ביותר והמקרה הגרוע ביותר ?? אני לא יכול! לא משנה איזה מערך אנו נותנים לו, עלינו לחזור על כל ערך במערך. אז הפונקציה תארך לפחות n זמן (Ω (n)), אבל אנחנו גם יודעים שזה לא ייקח יותר מ n זמן (O (n)). מה זה אומר? התפקיד שלנו ייקח n זמן בדיוק : Θ (n).

אם הגבולות מבלבלים, חשוב על זה ככה. יש לנו 2 מספרים, x ו- y. ניתן לנו ש- x <= y וכי y <= x. אם x קטן מ- y או שווה ל- y, ו- y קטן או שווה ל- x, אז x צריך להיות שווה ל- y!

אם אתה מכיר רשימות מקושרות, בדוק את עצמך וחשוב על זמני הריצה של כל אחת מהפונקציות הללו!

1. לקבל
2. לְהַסִיר
3. לְהוֹסִיף

הדברים נעשים מעניינים עוד יותר כאשר בוחנים רשימה מקושרת כפליים!

סימון אסימפטוטי

כיצד נמדוד את ערך הביצועים של אלגוריתמים?

שקול כיצד הזמן הוא אחד המשאבים החשובים ביותר שלנו. במחשוב נוכל למדוד ביצועים לפי משך הזמן של תהליך לוקח להשלים. אם הנתונים המעובדים על ידי שני אלגוריתמים זהים, אנו יכולים להחליט על היישום הטוב ביותר לפתרון בעיה.

אנו עושים זאת על ידי הגדרת הגבולות המתמטיים של אלגוריתם. אלה הם ה- Big-O, big-omega ו- the big-theta, או הסימנים האסימפטוטיים של אלגוריתם. בגרף ה- Big-O יהיה הארוך ביותר שאלגוריתם יכול לקחת עבור כל קבוצת נתונים נתונה, או "הגבול העליון". אומגה גדולה היא כמו ההפך מ- big-O, "הגבול התחתון". שם האלגוריתם מגיע למהירות הגבוהה ביותר עבור כל ערכת נתונים. תטא גדול הוא ערך הביצועים המדויק של האלגוריתם, או טווח שימושי בין גבולות עליונים לתחתונים צרים.

כמה דוגמאות:

• "המשלוח יהיה שם במהלך חייכם." (גדול-O, גבול עליון)
• "אני יכול לשלם לך לפחות דולר אחד." (אומגה גדולה, גבול תחתון)
• "היום הגבוה יהיה 25 מעלות צלזיוס והנמוך יהיה 19 מעלות צלזיוס." (תטא גדול, צר)
• "זה קילומטר הליכה לחוף הים." (תטא גדול, מדויק)

עוד מידע:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notation-represent //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/