[השמעת מוסיקה] 

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

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

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

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

ALAN אסטרדה: אה. מ"מ. טוב מאד. 

דוד י מלאן: אישור. טוב. תודה. ALAN אסטרדה: טוב מאוד. אוקיי. 

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

[צוחק] 

ALAN אסטרדה: כן, אני חושב-- 

דוד י מלאן: מה קטע הם שאנחנו ב? ALAN אסטרדה: עמעם, כך. 

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

[צוחק] 

בסדר. ALAN אסטרדה: לאן אנחנו מחפשים? דוד י מלאן: מייק סמית. ALAN אסטרדה: מייק סמית. דוד י מלאן: עכשיו, אנחנו בניתוח. עכשיו, רופאים. Now-- 

ALAN אסטרדה: Let's- בואו נלך עם אמת. אמיתי. 

דוד י מלאן: נדל. אוקיי. אם אתה צורך אמיתי. עכשיו, שהדרך היא מייק סמית? 

ALAN אסטרדה: בדרך זו. 

דוד י מלאן: באיזו דרך? ALAN אסטרדה: המתן. הנכון הוא-- M? התחלנו with-- 

דוד י מלאן: כן. הם עזבו. זכותך. 

ALAN אסטרדה: כן. 

דוד י מלאן: אז מייק בכאן. ALAN אסטרדה: מה? 

[צוחק] 

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

ALAN אסטרדה: אה. אה. השגתי אותך. השגתי אותך. אה. אה. זה הוא-- אישור, יש לי אותך. סמית 'כאן? 

דוד י מלאן: סמית ', תודה לך. אז אני אמשיך לחפש את סמית '? 

ALAN אסטרדה: הו, כן. לא לא לא. אוי לא. זה שלי. 

דוד י מלאן: אה, יש לך סמית. אוקיי. 

ALAN אסטרדה: כן, אני יש לי סמית ממש כאן. מצטער, חבר'ה. חשבתי Michael-- חיפשנו מיכאל. מצטער. 

דוד י מלאן: זה בסדר. בסדר, עכשיו אנחנו לPaccini ובניו. 

ALAN אסטרדה: Paccini ובנים. דוד י מלאן: רק אתה ואני נמצא בזה. אוקיי. מצא אותנו מייק סמית. סמית '. 

ALAN אסטרדה: סמית '. 

דוד י מלאן: סמית '. אנחנו בR זבל. ALAN אסטרדה: שטויות. אה. זה הולך לקחת זמן. 

[צוחק] דוד י מלאן: נעליים. אנחנו בנעליים. 

ALAN אסטרדה: עכשיו אנחנו gonna-- 

דוד י מלאן: נחמד. ALAN אסטרדה: Which-- [צוחק] הו, זה נהדר. [צוחק] 

דוד י מלאן: זה בסדר. 

ALAN אסטרדה: אה, זה טוב. אני לא חושב שאני הולך יש חברי PSAT אחרי זה. דוד י מלאן: טוב. ספורט. ALAN אסטרדה: ספורט. אום, L, M, N, O, פ דוד י מלאן: אישור. אז בואו לקרוע זה במחצית. זה בסדר. זה מסתיים בצורה גרועה בכל מקרה, בגלל מייק סמית 'לא תהיה בדפי הזהב. 

ALAN אסטרדה: או והאזור. 

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

[מריע] בסדר תודה. אוקיי. זה היה יוצא דופן. אבל זה עדיין מהיר יותר היה מחיפוש ליניארי, שבו אנו מתחילים ב תחילת הספר, ואנחנו עוברים בדרך שלנו משמאל לימין, סופו של דבר מחפש מייק סמית. וכך, אם בספר טלפונים היו אולי 1,000 דפים, אולי זה היה לוקח שלנו 10 או כך דמעות דף. 

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

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

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

ואם ירדן באמת יכול הצטרף אלינו לכאן על במה. בואו לרגע. מה השם שלך? קרוליין: קרוליין. דוד י מלאן: קרוליין, לבוא בעד. ואתה תהיה הצטרף על ידי לי וירדן כאן. קרוליין, תודה. בסדר. אז מה יש לנו כאן ל קרוליין הוא 26 ספרים כחולים שFAS משתמש כדי לנהל בחינות סופיות מסוימות. אלה מקבלים קשים למצוא, אבל מה שעשינו מראש הוא שאנחנו כבר לשים את שמו של מישהו בחזית של כל אחד מאלה, אבל אנחנו כבר המשכנו את זה פשוט על ידי לאחר מכן לשים את שמות מלאים. אז היינו לשים את האדם בשם L, D, J, B, כל הדרך עד Z, אבל הם בסדר אקראיים. ולכן אם היית, מדבר את דרכה בבעיה כמו שאתה לעשות את זה, אתה יכול ללכת קדימה ו למיין את אלה לנו, מ- A עד Z. 

קהל: בסדר, אז L הוא כמו, האמצע. C מתחיל. ב J לפני ל 'ב', ש 

דוד י מלאן: החזק ש חשבתי לשנייה אחת. כי אחר, זה רק מעניין לך, לי, וירדן. יש לנו ללכת. קהל: [לא ברור]. ר ' דוד י מלאן: אישור. מה אתה עושה? 

קרוליין: M מגיע לאחר O. 

דוד י מלאן: אישור. 

קרוליין: O. דוד י מלאן: O, טוב. 

קרוליין: א 

דוד י מלאן: E, F. כן. 

קרוליין: T, U, V. 

דוד י מלאן: V, T, U, V. אז זה נראה כאילו אתה making-- להמשיך. זה נראה כאילו אתה עושה ערימה גדולה כאן, וסוג של ערימה גדולה שם. אז במחצית הראשונה של האלף-בית, מחצית שנייה של האלף-בית. אוקיי. טוב. סוג של פיצול הבעיה בשתי. M, N, X. כן. קרוליין: ק דוד י מלאן: אישור. ק אז אתה סוג של בחירה שלהם אחד אחרי השני, לשים אותו שמאלה או ימינה, או Z של הולכים על הרצפה. אוקיי. 

קרוליין: Z הולך על הרצפה. 

דוד י מלאן: אישור. Y הולך על הרצפה. עכשיו אנחנו יכולים לשים X. 

קרוליין: ג ' דוד י מלאן: G הולך שמאלה. S הולך תקין. בסדר, הוא הולך כל דרך שמאל. 

קרוליין: A, B, C, D. 

דוד י מלאן: עכשיו, טוב. יש לנו, B, C. W של הולך שם למטה. בסדר, ט 

קרוליין: H, אני, ג ' דוד י מלאן: H, אני, ג 'טוב. קרוליין: במרכז, אני gonna-- דוד י מלאן: אישור. אז עכשיו, אנחנו הולכים לסוג של למזג אלה ערימות שונות. אז דרך C, אז אני רואה D, ו E ו- F, G ו, ו- H, ואני נחמד. J, ק 'ואז, ערימה זה הפוך, אבל זה בסדר. בטח. אנחנו יכולים לחתוך כמה פינות. אוקיי. ואז אנחנו צריכים W, X, Y, Z. 

קרוליין: כן. 

דוד י מלאן: מצוין. אז תודה גדולה ל קרוליין למיון אלה. 

[מריע] 

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

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

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

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

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

הדגמות one-- זה הולכים למהיר יותר ומהיר יותר עכשיו. בואו למטה. מה השם שלך? TREVOR: טרוור. 

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

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

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

TREVOR: אחד זה. 

דוד י מלאן: מס ' 

TREVOR: אישור. זֶה. 

דוד י מלאן: כן. זה היה טוב. בסדר. אז מה היה האלגוריתם שלך או הליך עושה את זה, טרבור? 

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

TREVOR: אישור. 

דוד י מלאן: מה האלגוריתם שלך הולך להיות? 

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

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

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

בחור' מספר 50? 

בחור' מספר 50. ואתה יכול לחשוף מה מאחורי כל אחד מדלתות אלה פשוט על ידי נגיעה בו עם אצבע. לעזאזל. 

[צוחק] 

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

-אוקיי. 

: ואם אתה מוצא את זה, אתה שומר את הסרט. אם אתה לא מוצא את זה, אתה נותן אותו בחזרה. 

-אדם. 

אה! 

- [לא ברור] על אישור. אז אני הולך לבדוק את הקצוות ראשון כדי לקבוע אם יש-- הו. 

[מחיאות כפות] 

[סוף ההשמעה] דוד י מלאן: אישור. אז מיון דלתות ברור מוביל ליעילות גבוהה יותר. וכך, במהירות כפולה זה מה שהתכוונתי שם. וכך ג'יי לי מזל בשתי הפעמים. והוא גם קיבל מזל שבעבר שנה, הזמנתי כמה דיסקי Blu-ray לתת בפועל. אני מצטער זה שנה, אנחנו לא היה לו הדבר, טרבור. אבל עוד יותר טוב היה לפני כמה שנים. וחלק מכם אולי יודע את זה בחור, שון, שכשהוא היה בCS50, היה לערער עם מדויק אותה בעיה, אם כי בSD, כפי שאתה בקרוב לראות, חזרה ביום. ואתה תמצא שלא רק הוא ייקח קצת יותר זמן מאשר ג'יי, קצת יותר מטרבור, זה היה למעשה הזדמנות נפלאה זו לעסוק כמעט כולם ב קהל לה מחיר הוא נכון, עידוד שלו כדי למצוא את המספר שאנחנו מחפשים. בואו. להעיף מבט מהיר. 

[וידאו השמעה] 

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

[צוחק] 

זה לא שאלה מכשילה. אחד. 

[צוחק] בשלב זה, הציון שלך הוא לא מאוד טוב, אז אתה יכול גם להמשיך. שלוש. 

[צוחק] 

תמשיך. למען האמת, אני לא יכול שלא לתהות מה שאתה אפילו חושב על, אז-- 

[צוחק] רק בשורה העליונה, כך יש לך שלושה שמאל. אז תמצא אותי שבע. 

[צוחק] 17. שבע. 

[מחיאות כפות] 

בסדר. 

[סוף ההשמעה] 

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

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

אז אחת בירוק turquoise-- זה? האם אתה מבצע? שני. בואו למטה. אוקיי. שלוש. ארבעה. בוא me-- אישור, חמש. אתה להיות מועמד על ידי חבר שלך. שש, שבע, שמונה ו. בואו למעלה. בסדר. תודה רבה לך. בואו למעלה. בואו למעלה. 

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

ענאן: אנאן. 

דוד י מלאן: אנאן. דוד. מה השם שלך? 

יוסף: יוסף. 

דוד י מלאן: יוסף, אתה מספר שתיים. 

סרינה: סרינה, מספר שלוש. סטפן, מספר ארבעה. סינתיה: סינתיה. דוד י מלאן: סינתיה, מספר חמש. [לא ברור] דוד י מלאן: [לא ברור]. דוד, מספר שש. מאט: מאט. דוד י מלאן: המספר של מאט שבע. ו? 

Waverly: Waverly. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אז בלי ליפול השלב זה שנה, אני הולך לתפוס את מספר one-- ומה היה השם שלך שוב? 

ענאן: אנאן. 

דוד י מלאן: אנאן. ואם אתה יכול להצטרף אליי ב תחילתה של הרשימה, בואו נכניס אותך שבו אתה שייך. Unfortunately-- מה שמך? 

סטפן: סטפן. 

דוד י מלאן: סטפן הוא בדרך. אז לפני שסטפן פותר את זה בעיה, מה עלינו לעשות? מה עושה עם סטפן? 

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

קהל: [לא ברור]. 

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

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

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

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

יוסף: יוסף. 

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

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

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

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

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

יוסף: יוסף. 

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

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

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

ענאן: אנאן. 

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

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

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

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

[מחיאות כפות] 

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

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

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

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

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

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

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

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

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

למעשה, אם אתה משווה עכשיו 499,000,000,000, 999 מ', 500,000 נגד הערך המקורי שלנו, 500 מיליארדים, זה כל כך קרוב ארור. נכון? n בריבוע מחולק 2 נותן us-- או לייתר דיוק, n בריבוע מחולק 2 נתן לנו 500 מיליארדים. זה די המעצבן הזה קרוב ל499999500000, כלומר הפחתה את 500,000, או באופן כללי יותר, הפחתה מ n בריבוע, לא ממש עניין גדול. N בריבוע עושה אלה מספרים גדלים ממש מהר. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[צפצוף] 

לפי אתה החלים תדירות בהתבסס על הגובה של בר הבר. זה סוג בועה. 

[צפצוף מעוות] 

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

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

וזה הכל. אנחנו אראה אותך בפעם הבאה. 

[Whooshing ומוסיקה]