מהי Big-O Notation?

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

מהי סימון ביג-או?

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

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

כיצד מחשבים סימון ביג-או

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

אלגוריתם 1:

def sockCounter (numberOfPairs):
individualSocks = 0
עבור x בטווח (numberOfPairs):
individualSocks = individualSocks + 2
להחזיר individualSocks

אלגוריתם 2:

def sockCounter (numberOfPairs):
מספר החזרה אופפרס * 2

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

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

מהי פונקציה בתכנות?

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

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

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

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

4n + 2

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

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

1

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

ניתוח Big-O

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

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

O (1)

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

עַל)

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

קוד לינארי

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

קוד ריבועי

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

def searchForValue (targetValue, arraySearched):
foundTarget = שקר
עבור x במערך
עבור y ב x:
אם (y == targetValue):
foundTarget = נכון
החזר נמצא יעד

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

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

O (n²)

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

קוד לוגריתמי

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

יומן 2 (8) = 3

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

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

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

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

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

O (יומן (n))

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

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

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

10 טעויות התכנות והקידוד הנפוצות ביותר

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

על הסופר