streamalism.org

1. סקירה כללית

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

2. האינטואיציה של סימון ביג או

לעתים קרובות אנו שומעים את ביצועים של אלגוריתם המתואר באמצעות Big O Notation.

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

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

3. אלגוריתמים לזמן קבוע - O (1)

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

שקול את פיסת הקוד הפשוטה הזו:

int n = 1000; System.out.println ("היי - הקלט שלך הוא:" + n);

ברור שזה לא משנה מה נ הוא, מעל. לחלק הקוד הזה לוקח זמן קבוע להפעלה. זה לא תלוי בגודל של n.

בדומה לכך:

int n = 1000; System.out.println ("היי - הקלט שלך הוא:" + n); System.out.println ("הממ .. אני עושה עוד דברים עם:" + n); System.out.println ("ועוד:" + n);

הדוגמה לעיל היא גם זמן קבוע. גם אם זה לוקח שלוש פעמים זמן לרוץ, זה לא תלוי בגודל הקלט, n. אנו מציינים אלגוריתמי זמן קבועים כדלקמן: O (1). ציין זאת O (2), O (3) או אפילו O (1000) פירושו אותו דבר.

לא אכפת לנו בדיוק כמה זמן לוקח לרוץ, רק שזה לוקח זמן קבוע.

4. אלגוריתמים של זמן לוגריתמי - O (יומן n)

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

אחת הדוגמאות הנפוצות לאלגוריתם של זמן לוגריתמי הוא אלגוריתם החיפוש הבינארי. כדי לראות כיצד ליישם חיפוש בינארי בג'אווה לחץ כאן.

מה שחשוב כאן הוא שה- זמן הריצה גדל ביחס ללוגריתם של הקלט (במקרה זה, היכנס לבסיס 2):

עבור (int i = 1; i <n; i = i * 2) {System.out.println ("היי - אני עסוק בלראות:" + i); }

אם נ הוא 8, הפלט יהיה הבא:

היי - אני עסוק בהסתכלות על: 1 היי - אני עסוק בהסתכלות על: 2 היי - אני עסוק בהסתכלות על: 4

האלגוריתם הפשוט שלנו רץ יומן (8) = 3 פעמים.

5. אלגוריתמים לזמן ליניארי - עַל)

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

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

חשוב על לולאה פשוטה:

עבור (int i = 0; i <n; i ++) {System.out.println ("היי - אני עסוק בלראות:" + i); }

כמה פעמים זה פועל עבור לולאה? נ פעמים, כמובן! אנחנו לא יודעים בדיוק כמה זמן זה ייקח לרוץ - ואנחנו לא דואגים לזה.

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

אנו מעדיפים זמן ריצה של 0.1n מאשר (1000n + 1000), אך שניהם עדיין אלגוריתמים לינאריים; שניהם גדלים ישירות ביחס לגודל התשומות שלהם.

שוב, אם האלגוריתם השתנה לדברים הבאים:

עבור (int i = 0; i <n; i ++) {System.out.println ("היי - אני עסוק בלראות:" + i); System.out.println ("הממ .. בואו נסתכל שוב על:" + i); System.out.println ("ועוד:" + i); }

זמן הריצה עדיין יהיה ליניארי בגודל הקלט שלו, נ. אנו מציינים אלגוריתמים ליניאריים כדלקמן: עַל).

כמו באלגוריתמי הזמן הקבועים, לא אכפת לנו מהפרטים של זמן הריצה. O (2n + 1) זהה ל עַל), מכיוון ש- Big O Notation מתייחס לצמיחה בגודל קלט.

6. N Log N אלגוריתמים בזמן - O (n יומן n)

n יומן n הוא המחלקה הבאה של אלגוריתמים. זמן הריצה גדל ביחס ל n יומן n של הקלט:

עבור (int i = 1; i <= n; i ++) {for (int j = 1; j <n; j = j * 2) {System.out.println ("היי - אני עסוק בלראות:" + i + "ו-" + j); }} 

לדוגמא, אם נ הוא 8, ואז האלגוריתם הזה יפעל 8 * יומן (8) = 8 * 3 = 24 פִּי. בין אם יש לנו אי שוויון קפדני ובין אם לא במעגל הפורום, זה לא רלוונטי לטובת סימון ביג או.

7. אלגוריתמים של זמן פולינומי - O (np)

בהמשך יש לנו אלגוריתמים של זמן פולינומי. אלגוריתמים אלה הם אפילו איטיים יותר מ n יומן n אלגוריתמים.

המונח פולינום הוא מונח כללי המכיל ריבועי (n2), מעוקב (n3), קוורטיק (n4)פונקציות וכו '. מה שחשוב לדעת זה O (n2) מהיר יותר מ- O (n3) שהוא מהיר יותר מ O (n4), וכו.

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

עבור (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {System.out.println ("היי - אני עסוק בלראות:" + i + "ו-" + j); }} 

אלגוריתם זה יפעל 82 = 64 פִּי. שים לב, אם היינו מקננים עוד לולאה, זה יהפוך ל- O (n3) אַלגוֹרִיתְם.

8. אלגוריתמים של זמן אקספוננציאלי - O (kn)

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

לדוגמה, O (2n) אלגוריתמים כפולים עם כל קלט נוסף. אז אם n = 2, אלגוריתמים אלה יפעלו ארבע פעמים; אם n = 3, הם יפעלו שמונה פעמים (בערך ההפך מאלגוריתמי זמן לוגריתמיים).

O (3n) אלגוריתמים משולשים עם כל קלט נוסף, אוקיי נ) האלגוריתמים יגדלו פי k עם כל קלט נוסף.

בואו נסתכל על דוגמה פשוטה ל- O (2n) אלגוריתם זמן:

עבור (int i = 1; i <= Math.pow (2, n); i ++) {System.out.println ("היי - אני עסוק בלראות:" + i); }

אלגוריתם זה יפעל 28 = 256 פִּי.

9. אלגוריתמים של זמן עובדה - עַל!)

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

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

הסבר על הפיתרון לבעיית איש המכירות הנוסע הוא מחוץ לתחום מאמר זה.

במקום זאת, בואו נסתכל על פשוט עַל!) אלגוריתם, כמו בסעיפים הקודמים:

עבור (int i = 1; i <= factorial (n); i ++) {System.out.println ("היי - אני עסוק בלראות:" + i); }

איפה מפעל (n) פשוט מחשב n !. אם n הוא 8, אלגוריתם זה יפעל 8! = 40320 פִּי.

10. פונקציות אסימפטוטיות

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

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

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

כדי להבין את ההבדלים בין 3 הפונקציות החשובות הללו, ראשית עלינו לדעת שכל אחד מ- Big O, Big Θ ו- Big Ω מתאר מַעֲרֶכֶת (כלומר, אוסף של אלמנטים).

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

• Big O מתאר את מערך כל האלגוריתמים הפועלים לא גרוע יותר ממהירות מסוימת (זה גבול עליון)
• לעומת זאת, Big Ω מתאר את מערך כל האלגוריתמים הפועלים לא יותר טוב ממהירות מסוימת (זה גבול תחתון)
• לבסוף, Big Θ מתאר את מערך כל האלגוריתמים הפועלים בְּ- מהירות מסוימת (זה כמו שוויון)

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

בדרך כלל תשמע דברים המתוארים באמצעות Big O, אבל לא כואב לדעת על Big Θ ו- Big Ω.

11. מסקנה

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

הדמיה נהדרת של שיעורי המורכבות השונים ניתן למצוא כאן.

כרגיל, ניתן למצוא את קטעי הקוד עבור הדרכה זו באתר GitHub.