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

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

• לָבוּשׁ
• לְנַקוֹת
• האכיל

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

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

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

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

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

int[] numbers = new int[100];
// ...fill the array with numbers

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), כלומר מורכבות קבועה . למה? שימו לב שאנו מכניסים כל מספר בתחילת הרשימה. בנוסף, תזכרו שכאשר אתם מכניסים מספר ל-a LinkedList, האלמנטים לא זזים לשום מקום. הקישורים (או ההפניות) מתעדכנים (אם שכחת איך LinkedList עובד, עיין באחד השיעורים הישנים שלנו ). אם המספר הראשון ברשימה שלנו הוא x, ואנו מכניסים את המספר 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 אלמנטים. נחזור על השלב הקודם שלנו על ידי חלוקת שוב את תת-המערך הנותר לשניים ושוב ניקח את האלמנט האמצעי (השורה השלישית בתמונה). המספר הוא 56, והוא גדול יותר מהמספר שאנו מחפשים. מה זה אומר? זה אומר שחיסלנו עוד 3 אפשרויות: המספר 56 עצמו וכן שני המספרים שאחריו (שכן מובטח שהם גדולים מ-23, כי המערך ממוין). נותרו לנו רק 2 מספרים לבדוק (השורה האחרונה בתמונה) - המספרים עם מדדי המערך 5 ו-6. אנחנו בודקים את הראשון שבהם, ומוצאים את מה שחיפשנו - המספר 23! המדד שלו הוא 5! בואו נסתכל על תוצאות האלגוריתם שלנו, ואז ננתח את מורכבותו. אגב, עכשיו אתה מבין למה זה נקרא חיפוש בינארי: זה מסתמך על חלוקה חוזרת של הנתונים לשניים. התוצאה מרשימה! אם השתמשנו בחיפוש ליניארי כדי לחפש את המספר, נצטרך עד 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). המורכבות של אלגוריתם החיפוש הבינארי היא לוגריתמית , או, אם אנו משתמשים בסימון O גדול, O(log n) . למה זה נקרא כך? הלוגריתם הוא כמו ההפך מאקספונציה. הלוגריתם הבינארי הוא החזקה שאליה יש להעלות את המספר 2 כדי לקבל מספר. לדוגמה, יש לנו 10,000 אלמנטים שעלינו לחפש באמצעות אלגוריתם החיפוש הבינארי. נכון לעכשיו, אתה יכול להסתכל בטבלת הערכים כדי לדעת שביצוע זה ידרוש מקסימום 14 השוואות. אבל מה אם אף אחד לא סיפק טבלה כזו ואתה צריך לחשב את המספר המקסימלי המדויק של השוואות? אתה רק צריך לענות על שאלה פשוטה: לאיזה כוח אתה צריך להעלות את המספר 2 כך שהתוצאה תהיה גדולה או שווה למספר האלמנטים שיש לבדוק? עבור 10,000, זוהי החזקה ה-14. 2 בחזקת 13 קטן מדי (8192), אבל 2 בחזקת 14 = 16384 , ומספר זה עונה על התנאי שלנו (הוא גדול או שווה למספר האלמנטים במערך). מצאנו את הלוגריתם: 14. זה כמה השוואות אולי נצטרך! :) אלגוריתמים ומורכבות אלגוריתמית הם נושא רחב מכדי להשתלב בשיעור אחד. אבל לדעת את זה חשוב מאוד: ראיונות עבודה רבים יכללו שאלות הכרוכות באלגוריתמים. לתיאוריה, אני יכול להמליץ ​​לך על כמה ספרים. אתה יכול להתחיל עם " Grokking Algorithms ". הדוגמאות בספר זה כתובות בפייתון, אך הספר משתמש בשפה ובדוגמאות פשוטות מאוד. זו האפשרות הטובה ביותר למתחילים, מה גם שהיא לא גדולה במיוחד. בין הקריאה הרצינית יותר, יש לנו ספרים מאת רוברט לאפור ורוברט סדג'וויק . שניהם כתובים ב-Java, מה שיקל עליך מעט את הלמידה. אחרי הכל, אתה די מכיר את השפה הזו! :) עבור תלמידים עם כישורי מתמטיקה טובים, האפשרות הטובה ביותר היא הספר של תומס קורמן . אבל תיאוריה לבדה לא תמלא את הבטן שלך! ידע != יכולת . אתה יכול לתרגל פתרון בעיות הקשורות אלגוריתמים ב- HackerRank ו- LeetCode . הרבה פעמים נעשה שימוש במשימות מאתרים אלו גם במהלך ראיונות בגוגל ובפייסבוק, כך שבהחלט לא תשתעממו :) כדי לחזק את חומר השיעור הזה, אני ממליץ לכם לצפות בסרטון המצוין הזה על סימון O גדול ביוטיוב. נתראה בשיעורים הבאים! :)