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

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

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

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

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

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

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

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

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

אני דאג לויד, זה CS50.