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

דוד י Malan: בסדר. אז ברוך הבא. זה CS50, והוא בסוף השבוע שלוש. 

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

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

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

ג'ניפר: [לא ברור] 

דוד י Malan: סליחה? 

ג'ניפר: ג'ניפר. 

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

15. 16. 50. יפה עשה. בסדר. מחיאות כפות לג'ניפר. 

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

בסדר. אז מה הייתה האסטרטגיה שלך עבור מציאת המספר, 50? 

ג'ניפר: אום, חשבתי שאולי, אם - [לא ברור] 

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

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

דוד י Malan: אישור. ונראים שאנחנו מוצאים כי כדי להיות במקרה. אמנם, בואו לקלף את השכבות רק קצת, ואתה רוצה ללכת קדימה ולחשוף את הדלתות האחרות אתה היה יכול לבחור? 

ג'ניפר: הו, יקירים. 

דוד י Malan: אה. 

ג'ניפר: אז יש לי רק מזל. 

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

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

דוד י Malan: אישור. 

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

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

ג'ניפר: כל אחד מהם. 

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

ג'ניפר: כן. 

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

ג'ניפר: אישור. 

דוד י Malan: - קודם לכן? 

ג'ניפר: בואו נתחיל עם הראשון. 

דוד י Malan: בסדר. תתחיל עם הראשונה. 4. עכשיו שבו אתה הולך, ולמה? 

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

דוד י Malan: אישור. בואו נראה, מה שאתה חושב? 

ג'ניפר: נסה את האחרון. נחמד. 

דוד י Malan: מאוד יפה עשה. בסדר. 

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

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

ג'ניפר: אישור. 

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

ג'ניפר: תחזור להתחלה. 

דוד י Malan: חזור להתחלה. אוקיי, אז אתה כבר נגעת דלת זו, שהייתה 8. בסדר. אז זה לא 50. איפה היית נראה הבא? 

ג'ניפר: אם לא עשיתי את זה יודעים שהם מסודרים. 

דוד י Malan: נכון. ובכן, אם אתה לא יודע הם מסודרים על - 

ג'ניפר: אה, לא יודע, כן. 

דוד י Malan: - אבל אתה לא יודע איפה היו 50 עדיין? 

ג'ניפר: פשוט להמשיך ללכת. 

דוד י Malan: בסדר. אישור. תמשיך. בסדר, שאני יכול לעבוד איתו. 

ג'ניפר: אישור. 

דוד י Malan: עכשיו, אם אתה רק הולך להמשיך, מה שלך האלגוריתם צלל מגובה ל. 

ג'ניפר: יניארי -. 

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

ג'ניפר: התחל באמצע. 

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

ג'ניפר: לכו במחצית זו. 

דוד י Malan: ולמה לימין? 

ג'ניפר: סוג אם הם היו הקטנים ביותר של לגודלה, אז צריכים להיות 50 בסופו של דבר זה. 

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

ג'ניפר: אז 16 הוא עדיין די קטן, ביחס ל -50, אז אולי אני אנסה, כאילו, זה אחד. 

דוד י Malan: בסדר. 42. בסדר, אז עכשיו מה אינסטינקט אומר לך? 

ג'ניפר: אני יכול לזרוק זה ולאחר מכן פשוט - 

דוד י Malan: אישור. טוב, אתה יכול לזרוק המחצית השמאלית שם. 

ג'ניפר: - להרים את זה. 

דוד י Malan: והנכון. 

ג'ניפר: כן. 

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

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

ג'ניפר: צריך זה אחד, כמו, אולי לקצץ בחצי את הזמן, או אפילו יותר, כן. 

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

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

רמקול 1: [לא ברור] 

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

ג'ניפר: יש. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[חציצת קולות] 

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

רמקול 2: אני רק מקבל -. 

דוד י Malan: עסקה טובה. בסדר. תודה לך על השתתפותך. 

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

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

חסד: היי, אני גרייס. אני בכיתה י 'בבית וורט. 

ברנסון: היי. אני רנסון. אני בכיתה ט 'בולד. 

GABE: היי. אני גייב. אני זוטר בקאבוט. 

ניל: אני ניל. אני בכיתה ט 'במתיוס. 

ג'ייסון: אני ג'ייסון. אני בכיתה ט 'בGreenough. 

מייק: מייק לי. אני בכיתה ט 'באפור. 

JESS: אני ג'ס. אני בכיתה י 'בוורט. 

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

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

1 רמקול: לפחות לגדול ביותר. 

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

רמקול 1: [לא ברור] 

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

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

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

GABE: נכון. 

דוד י Malan: נכון. שש ואחד? לא ולא. להחליף. אז זה שתי החלפות. שש ושלוש? לא ולא. להחליף. שש ושבע? נראה טוב. שבע וחמש? 

JESS: [לא ברור] 

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

ועכשיו מה שצריך האלגוריתם שלי במעבר השני יהיה? 

רמקול 1: אותו דבר. 

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

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

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

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

רמקול 1: מס ' 

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

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

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

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

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

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

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

מייק: מייק. 

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

ניל: ניל. 

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

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

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

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

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

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

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

חסד: גרייס. 

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

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

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

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

ג'ייסון: ג'ייסון. 

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

GABE: גייב. 

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

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

רמקול 3: הוא n צעדים [לא ברור]. 

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

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

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

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

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

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

ברנסון: רנסון. 

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

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

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

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

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

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

בסדר. הנה לך. תודה על - 

ברנסון: [לא ברור] לשמור את המספרים. 

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

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

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

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

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

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

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

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

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

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

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

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

[חציצת קולות] 

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

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

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

רמקול 1: n. 

דוד י Malan: n, שמעתי. 

רמקול 1: 2. 

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

[חציצת קולות] 

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

מהו המקרה הגרוע ביותר פועל זמן של מיון בחירה? 

רמקול 4: n בריבוע. 

דוד י Malan: N כיכר, אני שומע. אבל למה n בריבוע, באופן אינטואיטיבי? 

רמקול 4: כי אנחנו פשוט עשינו את זה. 

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

רמקול 5: [לא ברור] 

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

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

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

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

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

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

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

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