מורכבות אלגוריתם

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

• לָבוּשׁ
• לְנַקוֹת
• ניזון היטב

איזה אלגוריתם יאפשר לך להשיג תוצאה זו?

1. להתעורר לשעון מעורר.
2. תתקלח, תשטוף פנים.
3. להכין ארוחת בוקר, להכין קפה/תה.
4. לאכול.
5. אם לא גיהצת את הבגדים שלך מאז הערב, גהץ אותם.
6. להתלבש.
7. עזוב את הבית.

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

1. קנה או הורד באינטרנט "מילון שמות אישיים רוסיים" מהדורת 1966.
2. מצא כל שם ברשימה שלנו במילון זה.
3. רשום על פיסת נייר באיזה עמוד במילון מופיע השם.
4. סדר את השמות באמצעות ההערות על פיסת נייר.

האם רצף כזה של פעולות יאפשר לנו לפתור את הבעיה שלנו? כן, זה יאפשר זאת לחלוטין. האם פתרון זה יהיה יעיל ? בְּקוֹשִׁי. כאן אנו מגיעים למאפיין חשוב נוסף של אלגוריתמים - היעילות שלהם . ניתן לפתור את הבעיה בדרכים שונות. אבל גם בתכנות וגם בחיי היום יום אנחנו בוחרים בשיטה שתהיה הכי יעילה. אם המשימה שלכם היא להכין כריך עם חמאה, אפשר כמובן להתחיל בזריעת חיטה וחליבת פרה. אבל זה יהיה פתרון לא יעיל - זה ייקח הרבה זמן ויעלה הרבה כסף. כדי לפתור את הבעיה הפשוטה שלך, אתה יכול פשוט לקנות לחם וחמאה. והאלגוריתם עם חיטה ופרה, למרות שהוא מאפשר לך לפתור את הבעיה, מורכב מכדי ליישם אותו בפועל. כדי להעריך את מורכבות האלגוריתמים בתכנות, נוצר סימון מיוחד בשם Big-O ("ביג O") . Big-O מאפשר לך להעריך עד כמה זמן הביצוע של אלגוריתם תלוי בנתונים המועברים אליו . בואו נסתכל על הדוגמה הפשוטה ביותר - העברת נתונים. תארו לעצמכם שאתם צריכים להעביר מידע כלשהו בצורה של קובץ למרחקים ארוכים (לדוגמה, 5000 קילומטרים). איזה אלגוריתם יהיה היעיל ביותר? זה תלוי בנתונים שהוא צריך לעבוד איתם. לדוגמה, יש לנו קובץ אודיו בגודל 10 מגה בייט. במקרה זה, האלגוריתם היעיל ביותר יהיה העברת הקובץ דרך האינטרנט. זה ייקח רק כמה דקות! אז בואו נשמיע שוב את האלגוריתם שלנו: "אם אתה צריך להעביר מידע בצורה של קבצים למרחק של 5000 קילומטרים, אתה צריך להשתמש בשידור נתונים דרך האינטרנט." גדול. עכשיו בואו ננתח את זה. האם זה פותר לנו את הבעיה? באופן כללי, כן, זה פותר את זה לחלוטין. אבל מה אתה יכול לומר על המורכבות שלו? הממ, עכשיו זה המקום שבו הדברים נעשים מעניינים. העובדה היא שהאלגוריתם שלנו תלוי מאוד בנתונים הנכנסים, כלומר בגודל הקבצים. עכשיו יש לנו 10 מגה-בייט והכל בסדר. מה אם נצטרך להעביר 500 מגה בייט? 20 גיגה בייט? 500 טרה-בייט? 30 פטה-בייט? האם האלגוריתם שלנו יפסיק לעבוד? לא, עדיין ניתן להעביר את כל כמויות הנתונים הללו. האם זה ייקח יותר זמן להשלים? כן, זה יהיה! כעת אנו מכירים תכונה חשובה של האלגוריתם שלנו: ככל שגודל הנתונים שיש להעביר, כך ייקח יותר זמן להשלמת האלגוריתם . אבל נרצה להבין יותר במדויק איך נראה הקשר הזה (בין גודל הנתונים לזמן שנדרש להעברתם). במקרה שלנו, המורכבות של האלגוריתם תהיה ליניארית. "ליניארי" פירושו שככל שנפח הנתונים גדל, זמן השידור שלהם יגדל באופן יחסי. אם יש פי 2 יותר נתונים, וייקח פי 2 יותר זמן להעביר אותם. אם יש פי 10 יותר נתונים, זמן ההעברה יגדל פי 10. באמצעות סימון Big-O, המורכבות של האלגוריתם שלנו מוגדרת כ- O(N) . סימון זה זכור בצורה הטובה ביותר לעיון עתידי; הוא משמש תמיד עבור אלגוריתמים עם מורכבות ליניארית. שימו לב: אנחנו לא מדברים כאן בכלל על דברים "משתנים" שונים: מהירות אינטרנט, עוצמת המחשב שלנו וכו'. כאשר מעריכים את המורכבות של אלגוריתם, זה פשוט לא הגיוני - ממילא אין לנו שליטה עליו. Big-O מעריכה את האלגוריתם עצמו, ללא קשר ל"סביבה" שבה הוא יצטרך לעבוד. בואו נמשיך עם הדוגמה שלנו. נניח שבסופו של דבר יתברר שגודל הקבצים שיש להעביר הוא 800 טרה-בייט. אם נעביר אותם דרך האינטרנט, הבעיה כמובן תיפתר. יש רק בעיה אחת: שידור דרך קישור מודרני סטנדרטי (ב-100 מגה-ביט לשנייה) שרובנו משתמשים בו בבתים שלנו ייקח בערך 708 ימים. כמעט שנתיים! :O אז ברור שהאלגוריתם שלנו לא מתאים כאן. אנחנו צריכים פתרון אחר! לפתע, ענקית ה-IT אמזון באה לעזרתנו! שירות אמזון Snowmobile שלה מאפשר להעמיס כמויות גדולות של נתונים ליחידות אחסון ניידות ולמסור אותם לכתובת הרצויה באמצעות משאית! אז יש לנו אלגוריתם חדש! "אם אתה צריך להעביר מידע בצורה של קבצים למרחק של 5,000 קילומטרים, והתהליך ייקח יותר מ-14 ימים בהעברתו דרך האינטרנט, אתה צריך להשתמש בהובלת משאיות של אמזון". הנתון של 14 ימים נבחר כאן באופן אקראי: נניח שזו התקופה המקסימלית שאנחנו יכולים להרשות לעצמנו. בואו ננתח את האלגוריתם שלנו. מה לגבי מהירות? גם אם המשאית תיסע במהירות של 50 קמ"ש בלבד, היא תעבור 5,000 קילומטרים ב-100 שעות בלבד. זה קצת יותר מארבעה ימים! זה הרבה יותר טוב מאשר אפשרות השידור באינטרנט. מה לגבי המורכבות של האלגוריתם הזה? האם זה יהיה גם ליניארי, O(N)? לא זה לא יקרה. אחרי הכל, למשאית לא אכפת כמה תעמיס אותה - היא עדיין תיסע באותה מהירות בערך ותגיע בזמן. בין אם יש לנו 800 טרה-בייט, או פי 10 יותר נתונים, המשאית עדיין תגיע לשם תוך 5 ימים. במילים אחרות, לאלגוריתם לאספקת נתונים באמצעות משאית יש מורכבות מתמדת . "קבוע" פירושו שהוא אינו תלוי בנתונים המועברים לאלגוריתם. הכנס כונן הבזק של 1GB למשאית והוא יגיע תוך 5 ימים. שימו שם דיסקים עם 800 טרה-בייט של נתונים וזה יגיע תוך 5 ימים. בעת שימוש ב-Big-O, מורכבות קבועה מסומנת כ- O(1) . מאז התוודענו ל- O(N) וO(1) , בוא נסתכל כעת על דוגמאות נוספות של "מתכנתים" :) נניח שניתן לך מערך של 100 מספרים, והמשימה היא להדפיס כל אחד מהם לקונסולה. אתה כותב לולאה רגילה forשמבצעת את המשימה הזו

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

מהי המורכבות של האלגוריתם הכתוב? ליניארי, O(N). מספר הפעולות שעל התוכנית לבצע תלוי בדיוק בכמה מספרים הועברו אליה. אם יש 100 מספרים במערך, יהיו 100 פעולות (פלטים על המסך). אם יש 10,000 מספרים במערך, יהיה צורך לבצע 10,000 פעולות. האם ניתן לשפר את האלגוריתם שלנו? לא. בכל מקרה, נצטרך לבצע N מעברים דרך המערך ולבצע N פלטים לקונסולה. בואו נסתכל על דוגמה נוספת.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

יש לנו אחד ריק LinkedListשלתוכו נכניס כמה מספרים. עלינו להעריך את המורכבות של האלגוריתם להכנסת מספר בודד לדוגמא LinkedListשלנו, וכיצד זה תלוי במספר האלמנטים ברשימה. התשובה היא O(1) - מורכבות קבועה . למה? שימו לב: בכל פעם אנו מכניסים מספר בתחילת הרשימה. בנוסף, כזכור, בעת הכנסת מספרים לאלמנטים LinkedList, הם לא מוזזים לשום מקום - קישורים מוגדרים מחדש (אם שכחתם פתאום איך LinkedList עובד, תסתכל באחת ההרצאות הישנות שלנו ). אם כעת המספר הראשון ברשימה שלנו הוא המספר х, ונכניס את המספר y בתחילת הרשימה, כל מה שצריך הוא:

x.previous  = y;
y.previous = null;
y.next = x;

להגדרה מחדש של התייחסות זו, זה לא משנה לנו כמה מספרים יש עכשיוLinkedList - לפחות אחד, לפחות מיליארד. מורכבות האלגוריתם תהיה קבועה - O(1).

מורכבות לוגריתמית

לא להיבהל! :) אם המילה "לוגריתמית" גורמת לך לרצות לסגור את ההרצאה ולא לקרוא יותר, המתן מספר דקות. לא יהיו כאן קשיים מתמטיים (יש הרבה הסברים כאלה במקומות אחרים), וננתח את כל הדוגמאות "על האצבעות". תאר לעצמך שהמשימה שלך היא למצוא מספר אחד ספציפי במערך של 100 מספרים. ליתר דיוק, בדוק אם הוא קיים בכלל. ברגע שנמצא המספר הדרוש, יש להפסיק את החיפוש, ולהציג את הערך "המספר הדרוש נמצא!" במסוף. האינדקס שלו במערך = ....” איך הייתם פותרים בעיה כזו? כאן הפתרון ברור: צריך לעבור על רכיבי המערך בזה אחר זה, החל מהראשון (או האחרון) ולבדוק האם המספר הנוכחי תואם למספר הרצוי. בהתאם לכך, מספר הפעולות תלוי ישירות במספר האלמנטים במערך. אם יש לנו 100 מספרים, אז אנחנו צריכים ללכת לאלמנט הבא 100 פעמים ולבדוק אם המספר מתאים 100 פעמים. אם יש 1000 מספרים, אז יהיו 1000 שלבי בדיקה. ברור שזו מורכבות לינארית, O(N) . כעת נוסיף הבהרה אחת לדוגמא שלנו: המערך שבו אתה צריך למצוא מספר ממוין בסדר עולה . האם זה משנה משהו עבור המשימה שלנו? אנחנו עדיין יכולים לחפש את המספר הרצוי בכוח גס. אבל אנחנו יכולים להשתמש באלגוריתם החיפוש הבינארי הידוע במקום . בשורה העליונה של התמונה אנו רואים מערך ממוין. בו אנחנו צריכים למצוא את המספר 23. במקום לחזור על המספרים, פשוט מחלקים את המערך ל-2 חלקים ובודקים את המספר הממוצע במערך. נמצא את המספר שנמצא בתא 4 ונבדוק אותו (שורה שנייה בתמונה). המספר הזה הוא 16, ואנחנו מחפשים 23. המספר הנוכחי הוא פחות. מה זה אומר? שלא צריך לבדוק את כל המספרים הקודמים (שממוקמים עד המספר 16) : הם בהחלט יהיו פחות מזה שאנחנו מחפשים, כי המערך שלנו ממוין! בואו נמשיך בחיפוש בין 5 האלמנטים הנותרים. שים לב:עשינו רק בדיקה אחת, אבל כבר ביטלנו חצי מהאפשרויות האפשריות. נותרו לנו רק 5 אלמנטים. נחזור על הצעד שלנו - שוב נחלק את המערך הנותר ב-2 ושוב ניקח את האלמנט האמצעי (שורה 3 באיור). המספר הזה הוא 56, והוא גדול יותר מהמספר שאנחנו מחפשים. מה זה אומר? שנשליך 3 אפשרויות נוספות - המספר 56 עצמו, ושני מספרים אחריו (הם בהחלט גדולים מ-23, כי המערך ממוין). נותרו לנו רק 2 מספרים לבדוק (השורה האחרונה באיור) - מספרים עם מדדי מערך 5 ו-6. אנחנו בודקים את הראשון שבהם, וזה מה שחיפשנו - המספר 23! האינדקס שלו = 5! בואו נסתכל על תוצאות האלגוריתם שלנו, ואז נבין את המורכבות שלו. (אגב, עכשיו אתה מבין למה זה נקרא בינארי: המהות שלו היא לחלק כל הזמן נתונים ב-2). התוצאה מרשימה! אם היינו מחפשים את המספר הרצוי באמצעות חיפוש לינארי, היינו צריכים 10 צ'קים, אבל בחיפוש בינארי עשינו את זה ב-3! במקרה הגרוע, יהיו 4 כאלה, אם בשלב האחרון המספר שהיינו צריכים יתברר כשני, ולא הראשון. מה לגבי המורכבות שלו? זו נקודה מאוד מעניינת :) אלגוריתם החיפוש הבינארי תלוי הרבה פחות במספר האלמנטים במערך מאשר באלגוריתם החיפוש הליניארי (כלומר, ספירה פשוטה). עם 10 אלמנטים במערך, חיפוש לינארי יצטרך מקסימום 10 צ'קים, וחיפוש בינארי יצטרך מקסימום 4 צ'קים. ההבדל הוא פי 2.5. אבל עבור מערך של 1000 אלמנטים, חיפוש לינארי יצטרך 1000 בדיקות, וחיפוש בינארי יצטרך רק 10 ! ההבדל הוא כבר פי 100! שים לב:מספר האלמנטים במערך גדל פי 100 (מ-10 ל-1000), ומספר הבדיקות הנדרשות לחיפוש בינארי גדל רק פי 2.5 - מ-4 ל-10. אם נגיע ל-10,000 אלמנטים , ההבדל מרשים עוד יותר: 10,000 בדיקות לחיפוש ליניארי, ובסך הכל 14 בדיקות לבינארי. ושוב: מספר הרכיבים גדל פי 1000 (מ-10 ל-10000), אך מספר הצ'קים גדל רק פי 3.5 (מ-4 ל-14). המורכבות של אלגוריתם החיפוש הבינארי היא לוגריתמית , או, בסימון Big-O, O(log n) . למה זה נקרא כך? לוגריתם הוא היפוך של אקספוננציה. הלוגריתם הבינארי משמש לחישוב החזקה של 2. לדוגמה, יש לנו 10,000 אלמנטים שעלינו לעבור באמצעות חיפוש בינארי. עכשיו יש לך תמונה לנגד עיניך, ואתה יודע שזה דורש מקסימום 14 צ'קים. אבל מה אם אין תמונה לנגד עיניך, ואתה צריך לחשב את המספר המדויק של הבדיקות הדרושות? מספיק לענות על שאלה פשוטה: לאיזה עוצמה יש להעלות את המספר 2 כך שהתוצאה המתקבלת תהיה >= מספר האלמנטים הנבדקים? עבור 10000 זה יהיה החזקה ה-14. 2 בחזקת 13 קטן מדי (8192) אבל 2 בחזקת 14 = 16384 , המספר הזה עונה על התנאי שלנו (הוא >= מספר האלמנטים במערך). מצאנו את הלוגריתם - 14. זה כמה צ'קים אנחנו צריכים! :) אלגוריתמים ומורכבותם הם נושא נרחב מכדי להיכלל בהרצאה אחת. אבל לדעת את זה חשוב מאוד: בראיונות רבים תקבלו בעיות אלגוריתמיות. לתיאוריה, אני יכול להמליץ ​​לך על מספר ספרים. מקום טוב להתחיל בו הוא " אלגוריתמים גרוקים ": למרות שהדוגמאות בספר כתובות בפייתון, השפה והדוגמאות של הספר פשוטות מאוד. האפשרות הטובה ביותר למתחילים, והיא גם קטנה בנפח. קריאה רצינית יותר: ספרים מאת רוברט לפורט ורוברט סדג'וויק . שניהם כתובים ב-Java, מה שיקל עליך מעט את הלמידה. אחרי הכל, אתה די מכיר את השפה הזו! :) עבור תלמידים עם רקע מתמטי טוב, האפשרות הטובה ביותר תהיה הספר של תומס קורמן . אבל לא תסתפק רק בתיאוריה! "יודע" != "להיות מסוגל" אתה יכול לתרגל פתרון בעיות אלגוריתמים ב- HackerRank ו- Leetcode . הרבה פעמים משתמשים בבעיות משם גם במהלך ראיונות בגוגל ובפייסבוק, אז בהחלט לא תשתעממו :) כדי לחזק את חומר ההרצאה, אני ממליץ לכם לצפות בסרטון מעולה על Big-O ביוטיוב. נתראה בהרצאות הבאות! :)