מהו סימון Big-O?

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

סימון Big-O נותן לך דרך לחשב כמה זמן ייקח להפעלת הקוד שלך. אתה יכול זמן פיזי כמה זמן לוקח לקוד שלך להריץ, אך עם שיטה זו, קשה לתפוס הפרשי זמן קטנים. לדוגמה, הזמן שנדרש בין הפעלת 20 ל- 50 שורות קוד הוא קטן מאוד. עם זאת, בתוכנית גדולה, חוסר היעילות הזה יכול להוסיף.

כיצד להוריד סרטוני יוטיוב בחינם

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

כיצד מחשבים את סימון Big-O

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

אלגוריתם 1:

def sockCounter(numberOfPairs):  
 individualSocks = 0  
 for x in range(numberOfPairs):  
 individualSocks = individualSocks + 2  
 return individualSocks

אלגוריתם 2:

def sockCounter(numberOfPairs):  
 return numberOfPairs * 2

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

קָשׁוּר: מהי פונקציה בתכנות?

לאלגוריתם 1 יש שלבים רבים:

הוא מקצה ערך של אפס למשתנה individualSocks.
הוא מקצה ערך אחד למשתנה i.
הוא משווה את הערך של i ל- numberOfPairs.
זה מוסיף שניים ל IndividualSocks.
הוא מייחס לעצמו את הערך המוגדל של individualSocks.
זה מגדיל אני אחד אחד.
לאחר מכן הוא חוזר בשלבים 3 עד 6 באותו מספר פעמים כמו (indiviualSocks - 1).

ניתן לבטא את מספר השלבים שעלינו לבצע עבור אלגוריתם אחד כדלקמן:

4n + 2

ישנם ארבעה שלבים שעלינו לבצע n פעמים. במקרה זה, n יהיה שווה לערך numberOfPairs. ישנם גם 2 שלבים המסתיימים פעם אחת.

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

1

אם זה לא היה ברור כבר, נוכל לראות בקלות שאלגוריתם 2 יעיל לא מעט.

ניתוח Big-O

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

בדוגמאות לעיל, אלגוריתם 2 יתבטא כאחד:

O(1)

אך אלגוריתם 1 יתפשט כך:

O(n)

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

קוד לינארי

קרדיט תמונה: ניק פלדדרוס/ פרויקט שם עצם

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

קוד ריבוע

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

def searchForValue(targetValue, arraySearched):  
 foundTarget = False  
 for x in arraySearched:  
 for y in x:  
 if(y == targetValue):  
 foundTarget = True  
 return foundTarget

בדוגמה זו, מספר השלבים תלוי במספר המערכים ב- arraySearched ובמספר הערכים בכל מערך. לכן, מספר השלבים הפשוט יהיה n * n או n².

איך אדע אם הטלפון שלי נפרץ

קרדיט תמונה: ניק פלדדרוס/ פרויקט שם עצם

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

O(n²)

קָשׁוּר: כלים שימושיים לבדיקה, ניקוי ואופטימיזציה של קבצי CSS

קוד לוגריתמי

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

log 2 (8) = 3

היומן שווה לשלושה מכיוון שאם בסיסנו היה 2 היינו זקוקים לערך מעריך של 3 כדי להגיע למספר 8.

קרדיט תמונה: ניק פלדדרוס/ פרויקט שם עצם

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

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

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

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

O(log(n))

חשיבות הסימון Big-O

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

כיצד לגשת להודעות אינסטגרם במחשב

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

לַחֲלוֹק לַחֲלוֹק צִיוּץ אימייל 10 טעויות התכנות והקידוד הנפוצות ביותר

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

קרא הבא נושאים קשורים

תִכנוּת
תִכנוּת

על הסופר ג'ניפר סיטון(פורסמו 21 מאמרים)

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

עוד מאת ג'ניפר סיטון

הירשם לניוזלטר שלנו

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

לחצו כאן להרשמה