[Powered by Google Translate] [שבוע 3, המשך]
>> [דוד י מלאן - אוניברסיטת הרווארד]
>> [זה CS50. - CS50.TV]
>> בסדר. ברוך שובך. זה CS50 וזה סוף השבוע 3.
>> אז לאלה שנה לא מוכר, שעבר אוניברסיטה הרווארד השיקה מה שנקרא מעבדת החדשנות,
או i-מעבדה, שהוא בניין נפלא מעבר לנהר בקמפוס של הרוורד
כי הוא פתוח לסטודנטים, סטודנטי GSAS, סטודנטים מכל רחבי הקמפוס,
כולל סגל, וזה מקום לבוא יחד כדי לעבוד על דברים חדשניים,
דברים במיוחד יזמיים
אם אתה וחברים 0 או יותר חושבים לעשות משהו יזמי
גם במהלך השיעור הזה, אחרי זה בכיתה, או מעבר לו.
>> אז אחד הדברים שהם עושים מעל טווח J הוא הטיולים הללו,
אחד מהם הוא לניו יורק, שאחד מהם הוא לעמק הסיליקון.
החלל הוא מאוד מוגבל, אבל זה הזדמנות להתחכך עם תואר במנהל עסקים
וסטודנטים לתארים מתקדמים ברחבי קמפוס ולמעשה מבלים זמן באזורים האלה בהתאמה
מפטפט על סטארט, יפטפט יזמים וכדומה.
אז אם מתעניייין, לבדוק את כתובת האתר כאן.
זה זמין גם בשקופיות באינטרנט.
>> אנחנו יכולים למתן את אודי הבית רק קצת?
אם ברצונך להצטרף אלינו לארוחת צהריים ביום שישי, השעה 1:15 באש וקרח, אנא בראש שם.
אני מתנצל אם הטופס כבר מלא עד שאתה מגיע לשם.
אבל אנחנו נמשיך הלאה את המסורת הזאת.
>> היום אנחנו ממשיכים את הדיון ברמה הגבוהה יותר של בעיות שונות שאנו יכולים לפתור,
התמקדות הרבה פחות, היום לפחות, על קוד והרבה יותר על רעיונות.
אז תחשוב שוב לשבוע 0 כאשר קרעו ספר טלפונים במחצית,
שמטרתה הייתה לעשות משהו, יש להודות, קצת דרמטית
אבל כדי לשלוח את הנקודה שחיפוש אינו צריך להיות, בהכרח,
כמובן מאליו במבט ראשון כמו שחושב.
ופתרון הבעיות באופן כללי לא בהכרח תמיד להיות הטוב ביותר -
הפתרון המתבקש ביותר לא בהכרח יהיה הטוב ביותר.
אז היה לנו ספר טלפונים וזה, למען האמת, כולנו בחדר הזה היה אינסטינקטים,
ככל הנראה, להתחיל באמצע כאשר מחפשים מייק סמית ואז ללכת ימינה או שמאלה
בהתבסס על מה שהאות של אלף היינו במקרה בסופו של דבר.
>> אבל את הרעיון פשוט שאנו בני האדם נלקח כמובן מאליו כל כך הרבה זמן
באמת צריך להתחיל לבוא אל החזית של המוח שלך
כי כמו הבעיות לקבל הרבה יותר מורכב ממה שספר טלפונים,
אותן תובנה פשוטות האלה, מבריקות הן מה הולכים כדי לאפשר לנו
כדי לפתור את הבעיות הרבה יותר מסובכות והרבה יותר מעניינות,
ביניהם כמה מהדברים שאנחנו לוקחים כמובן מאליו כבר בימים אלה.
מיליארדי דפי אינטרנט שם בחוץ, ובכל זאת גוגל ובינג וכמו
תוכלו למצוא דברים בשבילנו ככה.
זה לא קורה באמצעות חיפוש ליניארי, וחפש בכל דפי האינטרנט האפשריים.
פייסבוק הוא מסוגל לומר לך שכל החברים שלך או חברים של חברים,
וגם את זה ניתן לעשות לכאורה במיידי בימים אלה
למרות שיש להם מיליוני משתמשים.
>> ואז איך אנחנו באמת לפתור את הבעיות שבסופו של דבר להפחית את ההיקף
לרעיונות הסתכלנו בשבוע 0 וקצת יותר היום.
אנחנו לא מחדש לבצע אלגוריתם זה, אבל אנחנו גם זוכרים שעשינו בשבוע 0 התרגיל הזה
המקום שבו כולם לקום, לקחת על המספר 1,
ואז היה לנו כל ספירה עצמית על ידי זוגות זוגות, והוסיף את המספרים שלך יחד,
מחצית מהחבורה התיישבה על כל איטרציה.
אז הלכתי מ500 תלמידים ל250-125 וכן הלאה.
אבל כפי שאמרנו ביום שני, רעיון רב העצמה יש
היה שאם הכפיל את גודל הבעיה
וכל הילדים ממשפטים או EC 10 חזרו לחדר והצטרפו אלינו,
טוב, אפשר שתחשיבו את הקבוצה כולה המצרפי
רק עם חזרה גדולה 1 יותר מהלולאה כי הם היו רק אולי, כפולים בגודל
או במקרה של Ec 10 קצת יותר מכפול בגודל.
ואז הייתי צריך להשקיע קצת יותר זמן,
אבל אנחנו לא צריכים להשקיע 400 או 700 שלבים נוספים.
>> רק כדי לצייר את התמונה הזאת באופן שקצת פחות מופשט, בואו לא כולם לעמוד על הרגליים.
אבל אם אלו מכם שבחרו לשבת בתזמורת היום לא היו אכפת בעמידה,
בואו נראה אם ​​אנחנו יכולים להבין שביניכם שאדם הגבוה ביותר הוא
על ידי עושה את אותו הסוג של אלגוריתם השוואתי.
אז אם אתה יושב בתזמורת, את התנצלותי, אבל השלב 1, לעמוד;
שלב 2, בזוגות עם מישהו בסביבה,
להבין מי הוא גבוה יותר, ולשבת אם אתה קצר יותר.
ואז לחזור.
[סטודנטי ממלמל]
>> אוקיי.
אוקיי. אחד נשאר עומד. מה שמך? >> אנדרו.
>> אנדרו, אתה האדם הגבוה ביותר בסעיף התזמורת היום.
>> מזל טוב. [מחיאות כפות ומריעות] אוקיי. יש מושב. אז מצאתי את אנדרו.
אבל כמה זמן היה לוקח לי, למשל, למצוא אנדרו
בסעיף זה של תזמורת 50 + או כך אנשים?
אני יכול לקחת את גישה פשוטה למדי ולהתחיל כאן.
ויש לי 2 אנשים לקום ואני רק משווה ביניהם,
ואז אני אומר לכל מי שקצת יותר קצר: "בסדר, אתה מתיישב,"
ואני הולך לזכור מי היה האדם הגבוה יותר.
ואז אני חוזר, חוזר, חוזר, ואני תולה באדם הגבוה ביותר
עד שאני מוצא מישהו קצת יותר גבוה מהם, ובשלב
האדם מעט הקצר לאחר מכן יש לשבת.
אבל שבאלגוריתם בסעיף תזמורת זו, אם יש n שלך,
כמה צעדים הוא אלגוריתם שהולך לקחת? >> [תלמיד] נ
>> זה הולך לקחת n, נכון, כי במקרה הגרוע ביותר, אם אפשר לומר כך,
האדם הגבוה ביותר הוא האדם האחרון שאני מקבל רק על ידי מזל רע אקראי.
אז במקרה הגרוע ביותר, זמן הריצה של אלגוריתם שהוא ליניארי, זה n,
כאשר n הוא המספר הכולל של אנשים בשטח, בגודל של הבעיה.
מה לגבי אלגוריתם זה?
העובדה שכולכם קמו ואז שוב חצי מהתיישבה,
המחצית מכם התיישבה, חצי מכם ישבו.
כמה צעדים צריכים שלקח אם יש n שלך כאן?
[תלמיד] N log n. >> זה יהיה יותר גרוע. היכנס n.
>> אז להתחבר n, גם אם אתה לא ממש זוכר מה לוגריתם הוא,
לעת עתה, רק מעריך שזה קשור איכשהו לזה וhalving halving וhalving.
זה לא חייב להיות פקטור של 2. זה יכול להיות פקטור של 3.
אבל זה זו חזרה על אותו הסוג של גורם כזה שגודל הבעיה מתחיל כאן
אבל אז מייד עובר לכאן, אז הנה, אז כאן, אז הנה.
אתה לא לוקח נגיסות קטנות של הבעיה, אתה באמת קצצת אותו
עם גדול בבת בכל פעם.
אז היו לנו 50 אנשים, אז 25, אז 12 וחצי או 13 אנשים בעמידה,
לאחר מכן 6 ½ וכך הלאה עד שעמד לבסוף רק אנדרו שנשאר.
אז אנחנו הולכים לקרוא ליומן של n, ואתה יכול לדמיין את זה באופן בא.
זוכר את התמונה הזאת כאן שבו אלגוריתם ליניארי הוא כמו הקו האדום שם,
הקו הצהוב היה הספירה על ידי אלגוריתם 2s ששמש לנו לחשבון סטודנטים
בעבר, אבל היום הגביע הקדוש הולך להישאר הקו הירוק הזה
היכן אם הכפלנו את מספר אנשים שבסעיף התזמורת או רק אמר,
לעזאזל, בואו כולם בחדר כולו עומד, לא כזה ביג דיל
כי אנחנו בערך להכפיל כמה אנשים נמצאים כאן למטה,
1 יותר איטרציה, לא בעיה.
>> מצאנו אנדרו או מי קורה להיות גבוה יותר מאנדרו
בקומת ביניים או במרפסת.
אז הרעיון הפשוט הזה שלקחנו כל כך הרבה מאליו בספר טלפונים,
הבין שיש כל כך הרבה מקומות שונים שבן תוכל ליישם אותו.
רק כדי להרביץ מעט ז'רגון - למעשה, ולא בז'רגון ראשון,
תן לי ללכת לתמונה הזאת כאן.
כרגע אנחנו מדברים על n ו n / 2 ולאחר מכן היכנסו של n,
אבל אנחנו בהחלט יכולים לבוא עם, כפי שיהיו במהלך הסמסטר,
סוג שני של נוסחות מתמטיות כדי לתאר את הרעיון הכללי הזה של זמן ריצה.
אלה הם מחוץ לההקשר לעת עתה, מפני שאנחנו רואים לפני זמן רב
אלגוריתמים שמדוברים בעצם מייצג.
>> שלא להבחין כאן בקו ליניארי n, הקו הישר, הוא למעשה נמוך מאוד והצביע עכשיו.
זה סוג של אשליה אופטית שבאנחנו פשוט לשנות את מה שציר x מייצג
וציר Y, ​​ואנחנו יכולים לעשות את נקודת קו ישר בכל כיוון שאנחנו רוצים.
אבל הסיבה שזה כל כך לכאורה שטוח עכשיו
בגלל שהיינו צריך כדי לפנות מקום על הגרף הזה לזמני ריצה הרבה יותר איטיים.
לעת עתה, יודע שיש כמה אלגוריתמים די רעים בחיים,
שחלקם לא ינקטו צעדי n, או טוב יותר, להתחבר צעדי n אבל יותר.
אז מעל קו n כאן בהודעת תחתיתו יש n פי יומן של n,
ונראה מה זה אומר לפני זמן רב.
מעל זה הוא n בריבוע, ואנחנו לא ראינו שום אלגוריתמים בריבוע n עדיין אבל אנחנו עומדים.
וזה נראה ממש רע.
יש 2 עד n, משהו מעריכים, שמרגיש אפילו יותר גרוע.
ובכל זאת, בסקרנות, אז יש n קוביות, שאם אתה סוג של חשיבה קדימה,
אם אתה סוג של לעשות את המתמטיקה, 2 עד n בעצם הופך להיות הרבה יותר ישר,
הרבה יותר למעלה מ n קוביות אם אתה מסתכל על הצירים די רחוק.
אז שם לב עכשיו הצירים הללו אינם שרירותיים 2-10 על ציר x.
>> ומה זה אומר?
כלומר, 2 אנשים, 10 אנשים בחדר.
זה כל אמצעי x: גודל הבעיה, מה הוא ההקשר.
וציר אנכי עכשיו הוא מספר השניות או מספר השלבים -
כמה יחידת הזמן.
אבל שם לב שזה 0-60 ו0 עד 10.
אבל אם אנחנו סוג של זום החוצה, כמו שאתה יכול ב-Excel או בתוכנה ליצירת תרשימים,
ואנחנו הולכים עד 200.000, נבחין שמשהו כמו 2 עד n
הולך להציף את זמני ההצגה של n בריבוע לחלוטין,
n חתוך לקוביות, n log n - כל מה שדברנו עליו עד כה.
ובכל זאת לתפוס את זה כשאתה מתחיל לדבר על דברים כמו פייסבוק
שם יש לך המון אנשים, רבים בכל קשורים,
יש לך n אנשים, כל אחד מהם עשוי להיות רבים כמו חברי n
אם כולם הוא סוג של הסחבק בעולם,
טוב, זה כבר n n פעמים, כך שחברויות של N אפשריות בריבוע,
לפחות בכיוון 1, n חברויות אפשריות בריבוע.
אז זה כבר מצביע על כך שמחפש הגרף החברתי של פייסבוק, אם אפשר לומר כך,
יכול להתחיל לבוא לידי ביטוי בסוגים אלה של נוסחות.
>> אנחנו נחזור ולהפוך את זה הרבה יותר קונקרטי,
אך לעת עתה, במטרה לשבועות הקרובים הרבים
הולך להיות בטוח שלא ללכת על אלגוריתמים או קוד יישום
שסופו של דבר לוקח את כל זמן שמשהו כזה.
אבל הדבר המרתק במדעי מחשב אם אתה ממשיך בתחום זה
לוקח שיעורים כמו CS121, CS124, אשר שניהם קורסי תאוריה,
הוא שלמעשה יש כמה בעיות שקיימות בעולם הזה
שיסודו, עד כמה שאנחנו יודעים, שלא ניתן לפתור מהר יותר
מהגרוע מהגרפים האלה בעצם מציע.
אז יש הרבה בעיות פתוחות בעולם הזה כדי לעשות הרבה יותר טוב מאשר לבני אדם יש עד כה.
>> אז בואו נתחיל אז עם דוגמה זו.
ראינו מאבק שון עם מצלמה על זה, יותר מדי מגושם בוידאו.
אבל המציאות הייתה כאשר שון הוטל למצוא על לוח כמו זה המספר 7,
זוכר שאמרתי את זה, "יש אי שם מאחורי פיסות נייר הללו או דלתות לבנות
"המספר 7. שון, תמצא את זה בשבילנו."
וזה היה נפלא מביך לצפות
כי הוא ממש נאבק עם בעיה זו.
אבל המציאות הייתה שון כמו גם עשה מישהו בחדר היה יכול לעשות.
הוא קצת יותר מאדם טיפוסי לקח אולי,
אבל הוא הניח שיש איזה טריק לבעיה זו,
הוא הניח שהוא היה חסר משהו.
וזה לא עזר כי מאת עיניים היו מסתערים עליו.
>> אבל המציאות הייתה אם הקלט לבעיה הוא חבורה של מספרים אקראיים
ואתה מתבקש למצוא מספר כזה 1,
הכי הטוב שאתה יכול לעשות הוא חיפוש ליניארי.
התחל בצד השמאל, עבר לימין, או להתחיל בצד ימין, תעבור לשמאל.
בדיעבד, אנו עשויים לחשוב, "שון, למה לא פשוט להתחיל מהקצה השני?"
ובכן, 7 היו יכול להיות באותה קלות כאן באופן אקראי,
אבל אני בכוונה שמתי את זה שם, כי חשבתי שהוא לא מתכוון להתחיל בסוף.
אז אני סוג של מניפולציה את המצב, אבל במקרה אקראי 7 יכול להיות בכל מקום.
אז החל מהקצה הימני היה יכול להיות יותר טוב,
אבל מה אם בשנה הבאה אני עובר 7 מקומות אחרים?
זה לא פתרון יסודי לבעיה חדשה -
החל מסוף 1 או האחר - כאשר אתה נתון אין הנחות אחרות.
אז שון התחיל לחפש דרך המספרים והוא אמר, "5. זה לא כאן".
ואז הוא הלך לשם וראה 19, אז הוא עצר לכ 20 שניות,
אז הוא פתח את זה בשביל 13, ולאחר מכן התברר
שלא נראה שיהיה כאן דפוס.
זה לא היה 1, 2, 3, 4 או כמו. היו פערים במספרים, מה שלא עזר.
וגם העובדה שנהגתי פיסות נייר הללו זולים כדי לכסות את המספרים
הוא למעשה מכוון, כי אם אני הסרתי את כל פיסות נייר הללו,
רובנו, שון כלל, כנראה שהייתי סוג של ציץ macroscopically
בלוח ואמר, "הו, 7 הן ללא ספק נכון לשם". אנחנו עשינו את זה באופן מיידי.
>> וזה יכול להיות הדרך בה המוח האנושי עובד במידה מסוימת,
אבל במציאות, העיניים או המחשבה שלו הייתה כנראה ברפרוף את המספרים מימין לשמאל,
משמאל לימין, אמצע והלאה - משהו קורה מבחינה פיזיולוגית
כך שהרגיש כאילו זה היה קורה באופן מיידי,
אבל רוב הסיכויים שגם באופן פנימי היה איזה סוג של שיטה למציאת 7.
ואכן, עכשיו שאנחנו מדברים על מערכים ומבני נתונים
ובתוך זיכרון של מחשב, הדבר היחיד שאנו בני האדם יכול לעשות
די להסתכל במיקומי זיכרון בודדים 1 בכל פעם.
>> אז בכל מקום אחר יכול גם להיות מכוסה פיסת נייר
כי אנחנו לא יכולים לראות את זה בכל מקרה. אנחנו יכולים לעשות דבר 1 בלבד בכל פעם.
אז במקרה הזה, במקרה של שון, הלכו לכאן ואז הלכו כאן
ואז הלכנו לכאן, כאן, כאן, כאן, יש חכם עד הסוף
ורק סוג של דילוג זה באופן שרירותי ומצא 7 שם.
האישה הזאת לא הייתה מיוחדת במיוחד. זה גם לא היה בתוקף.
אבל הוא סוף הסוף מצא 7.
אבל עכשיו ממסעדה באמת היא שהכי הטוב שאתה יכול לעשות אם תינתן שום מידע
מלבד מספרים ממוינים באופן אקראי הוא להתחיל משמאל או להתחיל מימין.
או לעזאזל, אתה יכול לפתוח את דלתות באופן אקראי, אבל גם אז מה זה אומר להיות אקראי?
ובכן, הייתי צריך איכשהו למסד מה זה אומר להתחיל כאן,
אז ללכת לכאן, ואז ללכת לכאן. שון היית נהדר, וזה היה פשוט כיף לראות.
מה אם במקום נשנינו את הבעיה קצת ולהביא את שון לשנה זו, אם תרצה?
האם יהיה מי שיהיה נוח לבוא לבמה ופתרון בעיה מעט שונה
ומופיע במצלמה?
>> בואו נלך מעבר לתזמורת כי אתם היינו מעורבים למדי היום כבר.
מה דעתך על בורוד, בכובע? בואו למטה. מה שמך? >> אלכס. >> אלכס. אוקיי.
אז אלכס יהיה שון של השנה ויופיע בשנים הקרובות
שווי של CS50 הרצאות.
אלכס, נחמד לפגוש אותך. >> נע להכיר אותך יותר מדי.
האתגר בהישג יד עבורך הוא שאתה צריך זה קצת יותר קל
בזה שאני אומר לך את אותם מספרים כאן, אבל עכשיו הם מסודרים.
אז עכשיו המטרה שלך היא למצוא את המספר 7.
ולמעשה, אנחנו באמת צריכות לעשות את זה - אתה בא מסוג המרמה, מחשב לא הייתי עולה,
על ידי התבוננות במה שהמספרים היו לפני רגע.
בגיר זה ממש לא הולך לעזור לכל כך הרבה,
אבל בואו נעמיד פנים שאתה לא יודע מה הוא המערך המקורי.
כל מה שאתה יודע כרגע הוא שיש לך מערך של מספרים ממוינים
שאולי יש פערים ביניהם, והמטרה שלך היא למצוא את המספר 7.
איך היית, אדם סביר, ללכת על מציאת המספר 7?
>> עבור מנמוך לגבוה? >> אוקיי. ללכת נמוך לגבוה.
ולא לתלוש אותם. בואו רק להרים אותם כדי שנוכל לעשות שימוש חוזרים בם.
אוקיי, אז 1. חכה. לפני שאתם ממשיכים הלאה, זה היה 1, שגוי בבירור.
אז מה עובר לך עכשיו? מה הצעד הבא שלך?
הבא. >> אוקיי. הבא. טוב. 3, כל כך שגויים. מה הצעד הבא שלך?
תמשיך. >> בסדר. תמשיך. 5.
אז להמשיך הלאה, ותן לי למסור לך את זה לדורות הבאים.
7. >> מצוין. טוב מאוד. מצא את המספר 7. [מחיאות כפות]
אז זה היה טוב, אבל שון מצא המספר 7 מדי.
ואני טוען שלא באמת נצלתי פיסה הנוספת של מידע,
אשר הוא שמספרים אלה מסודרים.
אז אנחנו יכולים לעשות טובים יותר? כל הצעה כאן? כן, מאחור.
[תלמיד] חיפוש בינארי. >> אין לי מושג מה הוא החיפוש בינארי.
>> [תלמיד] התחל באמצע. התחל >> באמצע. אוקיי. אז בואו נראה אם ​​אנחנו יכולים להגיע לשם.
אז אם במקום שאומר לך להתחיל מהאמצע, קדימה, לפתוח את הדלת באמצע.
יש 8 מהם, כך שתצטרך לבחור באופן שרירותי 1
מעט שמאלה או ימינה. אוקיי. 7! [מחיאות כפות] נחמדות מאוד.
בסדר, אבל איפה היינו הולכים עם זה?
בואו נניח שרק כדי לשבור את העניבה, היית מתחיל כאן
כי באותה מידה יכולה היה לקרות גם כן.
אנחנו רק במקרה ידענו ש7 היו שם. אז זה 13.
אז אם הם מסודרים ואנחנו רק התחלנו באמצע,
מה יהיה הצעד הבא של האופטימלי היית?
עבור שמאל. ואז הנה מגיע דוגמה שוב בספר טלפונים.
אם 13 הוא כאן ואנחנו יודעים הרשימה ממוינת,
אז כל פיסות נייר הללו הם שלא מעניינים אותנו עכשיו
כי אנחנו כבר יודעים ש7 חייבים להיות בצד השמאל
אם מספרים אלה מסודרים ומצאנו 13.
>> אז מה הצעד הבא שלך כאן? עבור >> לשמאל. >> אוקיי, טוב.
אז ללכת לשמאל, ו-- לחכות, היי, היי, היי. שמרמה.
אז מצאת את 7, אבל מה היה האלגוריתם פשוט מיושמים?
התחל באמצע. >> טוב. אז מה ההמשך ההגיוני של אותו רעיון?
אה, רק לאלה. >> בדיוק. >> אז אני מתחיל כאן. >> טוב.
אז עכשיו הלכנו מעט שמאלה שוב. זה 3.
אבל ממסעדה המעניינת כרגע היא איזה מהם אתם לא צריכים לדאוג?
2 אלה. אלה >> 2. אז עכשיו זה יכול ללכת, זה יכול ללכת משם.
עכשיו הבעיה שהייתה 8 ולאחר מכן הייתה 4 גודל כרגע הם בגודל 2.
אנחנו מקבלים די קרובים. שוב, ללכת לאמצע של 2 האלמנטים הללו.
>> אוקיי. אז זה סוג של מזל שעכשיו אנחנו הולכים תמיד נשארנו בגלל שאנחנו עיגול כלפי מטה.
אבל זה בסדר, כי עכשיו אנחנו להשליך את כל זה וכל דבר אחר, והשאירו אותנו רק עם 7.
בואו ניתן למחיאות כפות סוערות. מצאנו 7 שוב. [מחיאות כפות] אוקיי. בטח.
חכה רק 1 יותר 2.
למרות שהסוג הבא של התהליך ארך קצת יותר ממה שאנחנו מרגישים שזה יהיה,
בכנות, האינסטינקטים הראשונים שלך היו הכי הטוב, נכון? מצאנו 7 באופן מיידי.
אבל היינו מוצא 7 מהר יותר, לא משנה מה, בדוגמה זו לעומת זו 1
כי אם המספרים מסודרים כל, כמו הדפים בספר טלפונים,
אתה אכן יכול לקצוץ חצי מהבעיה שוב ושוב ושוב.
וזה לא ממש קל כמו לראות את זה רק עם 8 ספרות
בניגוד לספר טלפונים של 1,000 דף שבו אתה באמת רואה את זה מבחינה ויזואלית,
אבל במקרה הזה כאן כאשר שון חפש 7,
כמה שלבים במקרה הגרוע ביותר היה נדרש לו? >> [תלמיד] 7.
7 במקרה הגרוע ביותר. ובכן, במקרה הגרוע ביותר לא 7 אם יש 8 דלתות כאן.
זה היה לוקח לו 8 צעדים.
>> אז אם יש דלתות n, זה אולי לקח את שון לפני כמה שנתי צעדי n.
עכשיו, במקרה שלך, אלכס, בהתחשב בכך שהמספרים אלה מסודרים -
ואנחנו יכולים להסיק מסוג זה מאיפה שהייתם עד כה בסיפור הזה -
מה זמן הריצה של האלגוריתם החכם יותר של אלכס
להתחיל מהאמצע ולאחר מכן חזרה?
[תלמיד] 3. >> אז זה הולך להיות 3, פחות או יותר, אם אתה רוצה ללכת 8-4 2 עד 1.
אז או 3 שלבים, באופן כללי יותר, זה יומן n שוב.
בכל פעם שאתה halving וhalving וhalving וhalving,
זה ביטוי לרעיון הזה של היומן n.
וכך זה היה לוקח לך רק 3 שלבים, והיא אכן עשתה
ברגע שפתחנו את הדלתות וhalving halving,
אילו זה היה לוקח כמה שון 7 או 8 צעדים.
אז תודה שהיית איתנו השנה. >> תודה לך. היה נעים להכיר אותך.
תודה לאלכס. >> גם לי. [מחיאות כפות]
>> אז מה המשמעות האמיתית של זה?
עכשיו דמיינו שזה לא 8 דלתות, שלמען אמת, כולנו יכולתי למצוא משהו
מאחורי 8 דלתות די מהר על ידי פשוט קורע את פיסות נייר והולך עם האינסטינקטים שלנו.
אבל מה אם זה מ'דלתות? ומה אם זה 4000000000 דלתות?
במקרה של 4 מיליארדים דלתות, אתה באמת תרצה ללכת עם האלגוריתם של אלכס,
חיפוש בינארי כנתחיל לקרוא אותו או להפריד ולמשול, באופן כללי יותר,
בו אתה שומר halving וhalving הבעיה,
כי אם יש לך 4000000000 דלתות, כמה פעמים אפשר לקצוץ 4 מליארד חצי?
[תלמיד] 32. >> זה בעצם 32. אתה יכול לפתור את זה על פיסת נייר או בראש שלך.
אתה הולך 4000000000-2000000000 to 1 מיליארדים חצי מיליארדים, 250 מ', נקודה, נקודה, נקודה.
ואם אתה עושה את החשבון, אתה הולך אכן כדי לקבל 32,
ושלמעשה מתייחס למדעי מחשב, כי אנחנו בדרך כלל לספור בחזקים של 2.
2 עד 32 קורים להיות 4 מיליארדים שקל.
אז יש הרבה רלוונטי לסוגים אלה של חזקים של 2 במדעי מחשב.
>> אבל מה כ 8 מיליארדים? כמה צעדים שהוא הולך לקחת אם יש 8000000000 דלתות?
[תלמיד] 33. אז >> 33. מה אם יש 16000000000 דלתות? כמה צעדים שהוא הולך לקחת?
[תלמיד] 34. >> 34. סוג שלנו יכול להמשיך עד לזרא זה. אבל זה דבר חזק.
אתה יכול להציג מיליארדים תשומות נוספות לבעיה שלך, אבל, לא ביג דיל,
אתה פשוט לוקח ביס נוסף 1 מתוכה ובכך נותן לנו משהו כמו חיפוש בינארי
או להפריד ולמשול, באופן כללי יותר.
אבל אני סוג של רמאות כאן, נכון?
במקרה של האלגוריתם של אלכס, היה לה יתרון על שון.
היא ידעה שמספרים אלו מוינו, אבל אלכס לא היה צריך למיין אותם בעצמה.
אני מראש באתי ללוח והסוג של וידא
שציירתי את כולם כדי מיון, אז כיסיתי אותם בנייר.
אבל כמה עבודה שלא ייקח אותי?
אם היה לנו התחלנו עם המספרים הללו בקצת סדר אקראי לכאורה -
במקרה זה המספרים האלה פשוטים, 1 עד 8 לכאן -
איך אנחנו הולכים על מיון ערכים אלה?
אם היית אדם ניתן משימה זו, איזה סוג של גישה אינטואיטיבית היית לוקח
למיון ולכל מיני מספרים?
הדברים האלה היו מניחים אותם כחלקי פאזל. כן.
>> [תלמיד] הייתי לוקח את כל מספר והשוויתי אותו לכל אחד
ולהמשיך ללכת לצד השמאל. >> אוקיי, טוב.
אז קח את כל מספר, השווה אותו לזה שלידו,
ואז פשוט להמשיך לנוע לאורך הרשימה, סוג של rejiggering דברים כמו שאתה הולך.
אז הנה יש לנו סיכוי לאולי עוד כמה אנשים שיהיו מעורב.
האם יש לנו 8 מתנדבים נוספים שהיו רוצה לבוא?
לחץ קצת פחות כיוון שאתה לא יחיד. 1, 2, 3, 4, 5, 6, 7, 8.
בואו למטה. אתם הולכים להיות במספרי 1 עד 8.
בואו נראה אם ​​אנחנו לא יכולים לעשות את המיון הזה לאלכס הרבה באותו אופן שעשיתי אותו מראש.
1, 2, 3, 4.
קדימה, אם אפשר, בשורה על במה בין עמדת מוסיקה ואותי לכאן
באותו סדר הגודל כמו שקופית על המסך.
אוי לא.
אנחנו נעבוד לך לדוגמא הבאה. הו, חכה, חכה. הנה אנחנו מתחילים. חכה.
הדוגמא הבאה היא עכשיו. הנה לך. מספר 8. בואו נעלה.
בסדר. מיין עצמכם על פי זה.
הסט קצת לצד של המוזיקה עומד כאן.
אז יש לנו 4, 2, 6 - להגיע לשם, לכאן, ממש שם - 3.
כן. אוקיי. אתה הולך לכאן. לא, לך להישאר שם.
כן, ממש שם. מספר שאני טועה. בדיוק שם. אוקיי, טוב מאוד. אוקיי.
אז עכשיו בואו למיין אותם במטרה להגדיל.
>> איך אני יכול ללכת על עושה את זה?
האלגוריתם שהוצע לפני רגע היה למה אנחנו לא פשוט להשוות
את האנשים שהם סוג של אחד ליד שני ולאחר מכן לתקן את כל טעויות,
עובר משמאל לימין.
אז הנה יש לנו 4 ו 2, ברור שלא לפי סדר. בואו נחליף אותך. אוקיי.
אז עכשיו אני הולך לעבור את הקו. 4 ו 6, זה לא. [שחוק]
6 ו 8, די טוב. 8 ו 1, בואו נחליף אותך חבר 'ה אותי. בסדר.
אז 8 ו 3, להחליף אתכם.
8 ו 7, בואו נחליף אותך חבר 'ה אותי. 5 ו 8, מצוינים.
אני אתן לך רשימה ממוינת.
בסדר. אז לא ממש.
אבל זה יותר טוב כי במספרים הגדולים יותר - במקרה בנקודה 8 -
סוג של שבעבע מהשמאל לימין.
אז יש לי 1 מהם צודקים, אבל זה מרגיש כאילו זה לא ממש יפתור את הבעיה.
>> אז מה אתה היית מציע שנעשיתם עכשיו? >> [תלמיד] תמשיך לעשות את זה. >> אנו ממשיכים לעשות את זה.
ולהבין, שוב, אנחנו מכינים את הדברים רק על ידי שכל בני האדם
סוג של תבונה לארגן את עצמם המבוססים על תמונה,
אבל עכשיו אנחנו צריכים להיות הרבה יותר שיטתיים.
אנחנו צריכים להיות אלגוריתמיים על זה כאילו אנחנו כותבים קוד -
במקרה זה pseudocode המילולי.
אז תן לי לנסות את זה שוב. זה עבד די טוב. זה לא פתר את זה.
אבל כאשר הוא בספק, פשוט לנסות ולנסות שוב. אז 2 ו 4, לא עזרו יותר.
4 ו 6. אה! 6 ו 1, קצת יותר טוב עכשיו.
6 ו 3, טובים. 6 ו 7, 7 ו 5, 7 ו 8, טוב.
ואתם יודעים, אני יכול כנראה להתעלם 8 עכשיו בגלל שהוא בסוף הרשימה.
אולי אנחנו לא צריכים לדאוג למישהו שמגיע לו בעבר.
אבל בואו נראים אם זה הנחה בטוחה.
עכשיו רשימה היא - ארור - אינה ממוין. בואו ננסה את זה שוב.
אז 2 ו 4, 4 ו 1, 4 ו 3.
4 ו 6, טוב. 6 ו 5, טוב.
6, 7 ו 8, טוב. אבל שים לב, אני יכול רק לעצור כאן ועכשיו לעצור כאן עכשיו?
[תלמיד] כן. >> כן?
מה אם אחד מכם היה המספר 9 כל הדרך לשם?
זה היה מסודר. >> טוב. זה היה מסודר בסיבוב הראשון.
טוב. אז בואו נחזור שוב. אנחנו כמעט שם.
1 ו 2, 2, 3, 3 ו 4, 4, 5, 5 ו 6, 6 ו 7, 7 ו 8.
>> אני עושה עכשיו, אבל, שוב, אני מחשב שיכול לעשות רק מה שאומר לי לעשות,
והזיכרון היחיד שלי כרגע הוא שאני למעשה רק עשיתי קצת עבודה.
משהו השתנה כאן.
אז אני לא אשרתי טכני חזותי או אלגוריתמי כי רשימה זו היא מסודרת מאוד.
אז רק למען סדר טוב, רק כדי להיות אנאלי על זה, בואו נעשיתי 1 יותר הפעם.
אז 1 ו 2, 2, 3, 3 ו 4. ואתם יודעים מה?
רק למען סדר טוב, אני הולך לעקוב על היד שלי הפעם
כמה החלפות אני עושה רק כדי שאדע כמה עבודה למעשה שעשיתי.
3 ו 4, 4, 5, 5 ו 6, 6 ו 7, 7 ו 8. אין החלפות.
אז עכשיו הייתי לגיטימי להיות אידיוט כדי לעשות את זה שוב
כי אם אני לא עבדתי בשום דרך לעבור את זה של בני האדם,
אז ברור שזה הולך לקרות שוב אם אף אחד מהם הוא סוג של אקראי
adversarially נע סביב עצמם. אז עכשיו אני יכול להפסיק.
עכשיו בואו לשאול את השאלה, כמה עבודה שזה בעצם לקחת אותי?
כמה צעדים שלא ייקח? >> N בריבוע.
כן, אז n בריבוע. מאיפה אתה לוקח n בריבוע מ?
אתה צריך לבדוק כל num -
יש מספרי n, ואתה צריך לבדוק כל מספר עם מספרי n האחרים.
טוב. >> אז זה n בריבוע. >> טוב.
>> אז זה מרגיש כאילו זה יכול להיות מאוד שn בריבוע, נכון?
יש N של החבר 'ה האלה, 8 במיוחד במקרה זה,
אבל בכל פעם שעברתי את הרשימה הזאת אני משווה את האדם הראשון נגד שני,
השני נגד השלישי שוב ושוב ושוב,
וכשהגעתי לסוף, מה אני עושה? אני בניתי אותה מחדש.
אז אם אנחנו מכלילים את ההסבר הזה, יש לנו n אנשים
ואני עושה, כמובן, 8 שלבים, n צעדים, בכל פעם שאני עובר אלגוריתם זה.
אבל כמה פעמים במקרה הגרוע ביותר שאני צריך לעבור את זה רשימה של אנשים?
[תלמיד] N פעמים. כנראה >> n, נכון, כי במקרה הגרוע ביותר,
מה כנראה מקרה ההסדר הגרוע ביותר של החבר 'ה האלה מהרגע הראשון?
אם הם הפוכים לחלוטין כדי
כי פשוט מניח נפשי, בואי - מה שמך? >> בואן.
בואן. אוקיי. אז בואן, יבוא לכאן לרגע.
>> תניח שבואן היה כאן בתחילת האלגוריתם,
ואנחנו לא יודעים מה כל אחד אחר, אבל בואן כאן, על פי אלגוריתם זה -
ואם אתה רוצה רק כדי לטייל איתי - הוא הולך לבעבע, כפי שעשה בסיבוב הראשון,
כל הדרך עד הסוף.
אבל יניח שהאדם הבא לבואן היה המספר 7.
אני חייב לחזור ולקבל מספר 7, מה שאומר שאני צריך ללכת כל הדרך חזרה לכאן.
עכשיו אני צריך שיהיה לי אותו טיול עם האדם שהוא מספר 7.
אבל מה אם אז מספר 6 היה לידו גם כן?
ואז אני צריך לחזור ולקבל 6.
אז שוב, בכל איטרציה של הלולאה הזאת אני מדבר לכל אחד מאנשי n,
ואולי אני אצטרך לעשות n של טיולים אלה כדי לוודא שאני מושך
כל האלמנטים הגדולים שוב ושוב ושוב עד הסוף של הרשימה.
דברי n פעמים אז n הם רק n פעמי n או n בריבוע.
>> אז הנה כבר יש לנו אלגוריתם שכבר לא n, זה כבר לא היומן n,
זה בעצם יותר גרוע מכל דבר שעשינו בעבר.
אז סוג של אלכס לי מזל שבעשיתי את כל העבודה, ככל הנראה מראש עבורה,
כל העבודה היקרה, כדי שאוכל ליהנות באלגוריתם החיפוש הבינארי הזה,
שהוא יומן של n.
אבל זה עולה בקנה אחד עם הנושא של יום שני.
אנחנו נתנו קצת יותר מקום, הייתי עוד חתיכות, כדי להאיץ את זמן הריצה שלנו.
כל כך הרבה כמו שיש תחלופה בין הזמן ומרחב,
יש גם רק יכול להיות פשרות בין משך זמן עד מיון קדמי של מקבל דברים מוכנים ללכת
ואלגוריתם שמבצע בפועל כמו חיפוש. בואו ננסה עוד אחד.
אם אתם לא היו אכפת רק ארגון מחדש במהירות את עצמכם כדי להתאים את זה שוב,
בואו ננסה משהו קצת שונה שבם זה לא ממש פשוט
כפשוט לתקן את כל טעויות pairwise, שהוא הסופר אינטואיטיבי.
בואו במקום להיות קצת יותר מכוון ולעשות את זה.
האחד זה יותר מדי הייתי מציע הוא כנראה די אינטואיטיבי.
>> בואו לבחור את האדם הקטן ביותר מהרשימה שוב ושוב. אז הנה זה בא.
4, אתה האדם הקטן ביותר שראיתי עד כה ובכך,
אז אני הולך נפשי לזכור שרק על ידי הצבעה עליך לעת עתה.
2. אווה! תשכח ממספר 4. אני פשוט מצאתי את היסוד הקטן ביותר החדש ברשימה זו.
אני הולך לסוג של זוכר את זה. 6, 8.
אווה! 1. להתראות. אז עכשיו אני הולך לזכור את המספר 1.
אנו יודעים כי 1 הוא הקטן ביותר, אבל אני המחשב. מה אם יש 0?
מה אם יש -1? אני צריך להמשיך הלאה.
אז 3, 7, 5, זה לא. אוקיי. אז המספר 1 היה הקטן ביותר.
תן לי לבחור לך מהרשימה - אנחנו נלך בדרך זו -
ולשים אותך באופן שרירותי בתחילת הרשימה.
עכשיו, חכה רגע. אני סוג של מרומה.
אם החבר 'ה האלה לא מייצג רשימה של 8 אנשים, אבל מערך,
8 נתחי זיכרון רציף - אכפת לך צעד לאחור לרגע?
אין למעשה שום מקום בשבילך כאן.
אז איך אנחנו עושים את מקום ל-- מה השם שלך? >> סמי. >> סמי.
איך לפנות מקום לסמי?
>> אנחנו עוברים את n שלפני. >> אוקיי.
כדי שנוכל להעביר את אנשי n שלפניו,
כך שאם אתם רוצים לקחת 1 צעד מכוון, דרמטי לשמאל.
כולם עשו את זה ביחד, אבל בפעם האחרונה שכתבתי קצת קוד,
אתה לא יכול כאילו זזת הרבה דברים בבת אחת.
אנחנו יכולים לעשות את זה בלולאה, להעביר את כולם פעם אחת בכל פעם.
אז אם אתם לא היו אכפת לי וחוזרים בחזרה לימין,
וסמי, אם אתה יכול צעד אחורה, כי עדיין אין מקום בשבילך,
עכשיו בואו נעשיתי את זה. איפה היה סמי לפני רגע? בדיוק שם.
אז יש פער שם. אז אתה יכול לעבור למקומו של הסמים.
עכשיו האדם הבא ועכשיו האדם הבא, עכשיו האדם הבא. עכשיו יש לנו מקום לסמי.
עכשיו, מישהו מהקהל - שהיה טוב, זה היה נכון,
זה הרגיש זמן רב קטן - מה יותר מהר? כן.
[תלמיד] מערך חדש? >> מה זה? >> [תלמיד] מערך חדש? >> אוקיי, טוב.
>> אז עולה בקנה אחד עם הנושא הזה של רק פשרות, למה שלא פשוט לעשות מערך חדש
ואז סמי היה שוחה בחלל מול האנשים האלה, למשל,
ואנחנו רק יכולים להתחיל למלא את המערך חדש לגמרי. גם זה יעבוד.
אבל אני לא מעוניין בהוצאות יותר חלל היום. מה גישה אחרת?
[תלמיד] החלפה. >> אוקיי. אנחנו רק יכולים להחליף 2 הבחורים האלה. מה שמך?
מריו. >> מריו. אז מריו, היית כרגע כאן.
סמי, אתה יכול לגבות רק לרגע? מריו היה כאן.
אין לנו מקום בשבילך יותר, כך שאם לא היית אכפת לו ללכת למקום בו הוא סמי,
אנחנו נשים את סמי כאן, ועכשיו אני הייתי טוען כי פעולתו של סמי ההחלפה הייתה הרבה יותר מהר.
עשינו מבצע 1 להחליף את הבחורים האלה, או אולי להחליף 2 החבר 'ה האלה,
אבל אנחנו לא עשינו 1, 2, 3, 4, כך שמרגישים טוב יותר. עכשיו, חכה רגע.
אני סוג של הפכתי את הבעיה יותר גרועה כי המספר 4 היה סוג של קרוב להתחלה.
עכשיו מספר 4 הוא קצת יותר קרוב לסוף, אבל אני לא ממש יודע ולא אכפת מזה.
כך שזה רק המזל רע שמספר 4 הוא מעט רחוק יותר ממקומה המיועד.
אז בואו עכשיו חזור על האלגוריתם הזה.
>> לסיכום, כל עוד סיפור שהיה, כל מה שעשינו היה ללכת דרך הרשימה
מחפש את האדם הממוספר הקטן ביותר.
אז עכשיו בואו נעשה את זה שוב. אנחנו לא צריכים לדאוג לסמי יותר.
אנחנו פשוט יכולים ללכת כאן. אווה! מספר 2. זה מספר די קטן.
6, 8, 4, 3, 7, 5. בסדר, טוב.
ותודה לאל, במקרה, אני לא צריך לעבור - >> וילי.
וילי בגלל שהוא במקום הנכון שלו עכשיו.
בואו נעשה זאת שוב ולהתעלם 2 הבחורים האלה.
6. זה מספר די קטן. אווה! 8 הם בהחלט גדולים.
4. בואו נתמקד ב4. אווה! 3 הם אפילו טובים יותר.
7 ו 5. אז מה אנחנו עושים עכשיו עם - >> רוג'ר. >> רוג'ר?
בואו נחליף אותו עם מספר 6.
אז אם 6 ו 3 היינו רוצים להחליף,
עכשיו אנחנו סוג של קבלנו מזל שב6 הוא יותר קרוב למקום בו היא צריכה להיות,
אבל זה רק צירוף מקרים כאן. אז בואו עכשיו ללכת כאן.
8 הם מספר די קטן. אווה! 4 הם קטנים יותר.
6, 7, 5. מה אנחנו עושים עכשיו? החלפה. >> >> בדיוק.
אז עכשיו בואו לעשות את זה סוג של מהר יותר.
8, 6, 7, 5. איפה 5 ללכת? טוב. אוקיי.
6, 7, 8. 6 מקבלים להישאר איפה היא. מה שמך? >> רוזלי.
רוזלי מקבל להישאר איפה היא. 7 מגיעים ל-- בואו לראות. 7, 8. אוקיי.
אז 7 מקבלים להישאר איפה היא. מה שמך? >> אמנה. >> אמנה.
>> אז האמנה מקבלת להישאר איפה שהיא, ומספר 8 הוא כבר שם הוא צריך להיות עכשיו.
בסדר, טוב. הרגשה הוא שאנחנו פשוט יצירת עבודה לעצמנו לכאן.
מה סופו של דבר זמן הריצה של אלגוריתם זה?
אם אנו חושבים על האנשים האלה לא כמו 8 אבל כn? >> זה n.
זה n צעדים, אבל אנחנו בודקים בכל פעם אחת.
אוקיי. N אבל אתה בודק כל פעם אחת?
אוקיי, אבל אם זה של N צעדים, שאני לא היה יכול למיין אותך רק על ידי הולך 1, 2, 3, 4?
הו! אוקיי, זה הבדל גדול.
אז n זקף מדוע? מה באמת קורה?
יש אנשי n ברשימה זו, אך כדי למצוא את האדם הקטן ביותר ברשימה
במקרה הגרוע ביותר, כמה צעדים שאני צריך לקחת? נ >>
>> N, נכון, כי במקרה הגרוע ביותר, מספר 1 הוא את כל הדרך לשם,
אז אני צריך ללכת להביא אותו או אותה.
ואז כשאני סוף הסוף מבין 1 היה הקטן ביותר, אז זה די מהר כדי להחליף אותם.
אבל עכשיו אני צריך להתחיל מההתחלה ולחפש את מי?
האדם הבא הקטן ביותר, שהוא 2. איפה במקרה הגרוע ביותר הוא 2?
הו, אלוהים שלי. זה כל הדרך לכאן בסוף.
אז עכשיו זה עתה עשה עוד צעדים, צעדי n n עוד.
אם יש לנו אנשי n ובמקרה הגרוע ביותר לאדם הוא הקטן ביותר n צעדים ו,
זה שוב n הפעמים n, ולכן שוב לא n בריבוע.
זה לא מרגיש כל כך טוב.
ואכן, גם במקרה הטוב ביותר - תניח שהם מתחילים למיין את -
כמה צעדים נדרש לי באמצעות אלגוריתם זה כדי למיין את האנשים האלה n?
N בריבוע. >> שמעתי n בריבוע. למה n זקף?
מכיוון שאתה עדיין צריך לבדוק בכל פעם מחדש. >> כן.
ואתה צריך להחליף אותם. >> אף אנו, בני האדם הוא סוג של כל יודע
במובן חזותי שאנחנו יכולים פשוט סוג של לראות שזה מסודר,
מחשב הוא לא כל כך חכם.
זה הולך להיראות כאן וכאן וכאן,
אבל אם מה שהוא מחפש הוא היסוד הקטן ביותר,
אתה רק יודע שאתה מצאת היסוד הקטן ביותר של מה טעם? ברגע שאתה בסופו של דבר.
אך בשלב זה שמצאת את האלמנט הקטן ביותר כרגע בלבד.
אתה לא בהכרח יודע עוד משהו על מצבו של העולם.
אז אתה צריך ללכת שוב ושוב ושוב.
>> אז הפעם אני באמת נראה מטומטם כי אני בודק, בסדר, 2, אתה קטן,
אבל אני לא יודע שבסיכום עדיין.
3, 4, 5, 6, 7, 8. בסדר, טוב. 2 אכן היו הקטנים ביותר.
עכשיו נמצא לי הנמוך הבא. אוקיי.
3, אתה כרגע הקטן ביותר. בואו נראים. 4, 5, 6, 7, 8. אוקיי, יש את המזל שוב.
3 אכן היו במקום הנכון. אבל אני הולך להמשיך לעשות את זה שוב ושוב ושוב.
איך אנחנו יכולים לעשות אי פעם כל כך מעט טובים יותר?
במקום שיש עד pairwise מקטן ועד גדולים ביותר אנשי בועה
ובמקום ללכת קדימה ואחורה ברשימת בחירת האדם אז הקטן ביותר,
למה אנחנו לא במקום להכניס את האנשים האלה לרשימה חדש צעד אחר צעד?
בואו ננסה את זה. עכשיו בואו תקראו לי סוג החדרת הדבר הזה.
אז הנה אנחנו כאן. מספר 1. לא אכפת לי על מישהו אחר ברשימה זו.
המטרה שלי עכשיו היא לשים מספר 1 בתחילת רשימה ממוינת.
ואני הולך להציע מאז יש לי 8 חתיכות של זיכרון בלבד,
באופן שרירותי כרגע אני החומה בין הרשימה הממוינת כביכול שלי,
ומי שעומד מאחוריי אני הולך לתבוע ממוין.
אז עכשיו יש לנו מספר 1.
אני רוצה להכניס אותו לרשימה הממוינת שלי, אז אני פשוט הולך לעבור הקיר שלי כאן,
ועכשיו אני טוען רשימה זו היא מסודרת, רשימה זו היא ללא מיון - לפחות עד כמה שאני יודע.
אני לא יכול לראות את כל המספרים בפעם אחת.
>> עכשיו אני במקרה נתקל במספר 2. מה עליי לעשות איתו?
אני מכניס אותך עכשיו לרשימה הממוינת. אבל שים לב כמה קל זה היה.
אני רק צריך לחפש. מספר 1 הוא שם. אה, ברור 2 הולכים לצד של מספר 1.
עכשיו מה שאני עושה עם 3? אני אכניס אותך לרשימה הממוינת. אבל זה היה סופר קל.
זה סופר קל, זה סופר קל, זה סופר קל, סופר קל, סופר קל.
ועכשיו הכל מסודר מאחוריי, וכמה צעדים לא שייקח?
[סטודנטים] נ >> אז זה n בלבד. היינו לנו מזל.
זה היה רק ​​n מדוע? >> [תלמיד] כי הרשימה הייתה ממוינת.
הרשימה כבר ממוינת. אז היינו לנו מזל.
אבל אנחנו תוכננו אלגוריתם הזמן הזה שרותם זה סוג של מזל,
שהמקרה הטוב, בכך שלא לבזבז זמן מיותר.
אז עכשיו יש לנו את מה שאנחנו קוראים למיני בועה
שבו אנשים מסוג של בועה עד pairwise.
עכשיו יש לנו מיון בחירה בו אנו קוטפים את האדם הקטן ביותר שוב ושוב.
ועכשיו יש לנו מעין כניסה בה אנחנו כאילו באופן יזום את אנשים שבו הם שייכים
ברשימה ממוינת יותר ויותר.
אם היינו יכול, מחיאות כפות לחבר 'ה אלה כאן. [מחיאות כפות]
בואו ניקח ההפסקה שלנו 5-הרגע פה.
וכשנחזור, שנפוצץ את כל האלגוריתמים האלה מחוץ למים
עם משהו טוב יותר. בסדר. תודה רבה מאוד. אתה יכול לשמור אותם למזכרת.
בסדר. אנחנו נחזור.
>> ולסכם ממש מהר, היו לנו 3 גישות השונות האלה למיון,
כל העניין של שהיה להגיע לנקודה שבה מישהו כמו אלכס
תוכל לחפש ברשימה של מספרים יותר מהר ממישהו כמו שון יכל.
למרות שיש לנו דוגמאות פשוטות כאלה עם 8 מספרים ו,
אתה יכול להסיק בקלות עד 8 דפי אינטרנט, 8 מליארד דפי אינטרנט,
או 800 מיליון חברים בפייסבוק.
אז האלגוריתמים האלה בהחלט ניתנים להרחבה לאלו סוגים של ערכים,
והרעיונות הם בסופו.
אז מיון בועות היה הראשון שבו אנחנו סוג של פעפעו האדם הגדול ביותר
כל הדרך לצד ימין על ידי החלפת אנשי pairwise.
ואז היו לנו את מה שאנחנו קוראים למיון בחירה שבו אני קצת יותר בכוונה
המשיך להסתכל ברשימה, בחירת המספר הקטן שוב ושוב ושוב,
התוצאה ההגיונית שלו היא שהרשימה ממוינת סופו של דבר.
אז בשליש, הכנסתי את אנשים למקום הראוי שלהם,
ועשינו את דוגמה מאוד מאולצת שברשימה הייתה ממוינת כבר,
אבל זה היה לשלוח את ההודעה כי במקרה של סוג ההכנסה,
אתה יכול לקבל מזל.
אם המספרים כבר מסודרים, זה רק הולך לקחת אותך n צעדים כדי לאשר כל כך הרבה,
ואילו מיון בחירה אתה ראיית מנהרה קצת יותר
ואתה אף פעם לא מבין שהרשימה כבר ממוינת.
אז בואו לראות מיון בועות בפעולה כאן.
בדוגמא הבאה, אנחנו עומדים לראות קווים אנכיים
גבהים שמייצגים מספרים, כך שאנחנו יכולים לעשות משהו של לדמיין מיון לקרות.
קטן על הבר, קטן המספר; הבר הגדול יותר, המספר הגדול יותר.
>> ונשחקנו אותו במהירות זו כברירת מחדל.
זה הולך לעבור מהר קטן לעת עתה, אך אדום הוא מה שמראה 2 פסים
לצורך ההשוואה זה לצד זה.
ואם אתם צופים הדוקים, מה שקורה הוא שאם את הסורגים הם מקולקלים,
הקטן אחד לא עבר לשמאל, אחד הגדול יותר בצד ימין,
ואז אתה ממשיך להתקדם.
אז אם אנחנו עושים את זה שוב ושוב, שים לב שהברים הקטנים
הולכים לשמור התקדם דרכם לשמאל
והברים הגדולים הולכים לשמור התקדם דרכם לימין.
ואכן, אנחנו מתחילים לראות דפוס כל הדרך בצד ימין
בדיוק כמו שראינו 8 ואז 7 סופו של דבר מבעבעים עד הקצה המרוחק של הרשימה האנושית שלנו.
אז זה הולך מהר מאוד לקבל קצת משעמם, אז בוא תעצור אותי לרגע.
הרשה לי לשנות את המהירות להיות הרבה יותר מהר.
אני לא משנה את האלגוריתם, שאני רק עושה את האנימציה תקרה מהר יותר.
עדיין מיון בועות, אותו אלגוריתם,
אבל עכשיו אתה יכול לראות הרבה יותר מהר מאשר ההפגנה המילולית שלנו
כי האלמנטים הגדולים אכן מבעבעים לראש.
>> במאמר מוסגר, ריבועים אלה קטנים בצד השמאל למטה ותחתונים ימניים
הם רק תזכורות קטנות כמו לכמה השוואות שאתה עושה.
אבל נכון לעכשיו, אנו יכולים להתמקד בפירמידה שלוקחת צורה, והנה זה בא.
האלמנט הקטן ביותר הוא בצד השמאל, הגדול ביותר בצד ימין, וכל הדבר אחר באמצע.
עכשיו בואו במקום להעיף מבט במיון בחירה.
אני הולך קדימה ופגעתי בעצירה. אנחנו הולכים לקבל קבוצה אקראית חדשה של ברים.
מיון בחירה, כזכור, על הרשימה שוב ושוב ושוב,
מריטת היסוד הקטן ביותר. אז הנה הוא מיון בחירה.
זה נראה כאילו יש פחות עבודה של קורית עכשיו כי אנחנו לא משווים pairwise
אבל אנחנו סתם מין לקטוף דובדבני האלמנטים הקטנים ביותר מימין לשמאל.
זה לקח מעט מאוד זמן, כך שאין כבר הדיכוטומיה.
רק בגלל שאלגוריתם הוא אמר לקחת זמן ריבוע n, כמו מיון בועות
וכמו מיון בחירה, אלה הם באמת פעמים רצופות במקרה הגרוע ביותר.
לדוגמה, במקרה של, יניח, מיון בחירה,
אני דווקא בחירה באדם הקטן ולשים אותו או אותה לכאן,
אז אני עושה את זה שוב, ואז אני עושה את זה שוב,
אבל לא הייתה שם אופטימיזציה קלה אני יכול לעשות.
>> ברגע שעברתי מספר 1 כאן - סמי במקרה זה -
מה שאני לא צריך לעשות איתו לאחר מכן? >> [תלמיד] עזוב אותו.
תעזוב אותו, נכון? שום דבר.
אני לא צריך בכלל לדבר עם סמי שוב כי אם הייתי נבחרתי היסוד הקטן ביותר
והכניס אותו לכאן, למה לבזבז זמן הולך לסוף כל הרשימה שלי?
באיטרציה הבאה תנו לי למעשה לנוע רק למספר 2, רק למספר 3.
אז במציאות, לא הייתי עושה את דברי n n פעמים.
אני עושה דברים n, אז n - 1 בעניינים, אז n - 2 דברים, אז n - 3 דברים,
אז n - 4, נקודה, נקודה, נקודה.
יש לנו קצת סדרה גיאומטרית, שרק אומר
אתה מוסיף את מספרים בהדרגה קטנות יותר.
לא n + n + n + n אבל n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
ומה שבדרך כלל פועל יוצא להיות -
אני הולך לעשות בלגן בלוח שלי כאן רק לרגע -
זה הולך לעבוד כדי להיות משהו כמו n (n - 1) / 2
אם רק לנו סוג של מראה בחלק האחורי של ספר מתמטיקה שבו יש לך את כל גיליונות לרמות
לנוסחות.
אם אתה רק מוסיף משהו n + n - 1 + n - 2, זה פועל יוצא להיות משהו כזה.
ואם אנחנו פשוט סוג של להכפיל את זה, זה n בריבוע מינוס n / 2.
אני כל זמן אמר n בריבוע, אם כי, וזה בגלל שאני סוג של עושה קיצור דרך נפש
כי במציאות, n בריבוע מינוס n חלק 2 הוא אכן המספר הנכון של צעדים
שאלגוריתם כמו מיון בחירה היה לוקח אם אנחנו באמת ספרנו עד
כל ההשוואות האלה ואת כל העבודה הקטנה והעסוקה שאנחנו עושים.
אבל בכנות, ברגע שמקבל n להיות כמו מ'או מיליארדים, מי לעזאזל אכפת
אם אתה עושה מליארד מינוס בריבוע מיליארדים חלק 2?
בריבוע מליארד הוא מספר עצום.
אתה יכול לקחת את זה ממנו במיליארדים - n. זה לא כזה ביג דיל.
אז גדול יותר לקבל את המספרים, את פחות החשוב מבחינת המסודר הנמוך אלה.
למי אכפת אם אתה מחלק ידי 2 אם אתה מדבר על quadrillions של מספרים של שלבים?
>> אז באופן כללי, מדעני מחשב נוטים להשליך הכל אבל הטווח הגדול ביותר,
ואנחנו פשוט סוג של לפשט את העולם ולומר שאלגוריתם
צעדים בערך n בריבוע. זה זמן הריצה של אלגוריתם.
אז תחזרו לזה ברגע עם דוגמאות קונקרטיות,
אך לעת עתה, זה סוג של המוטיבציה מאחורי אינטואיטיבי פשוט לפשט את העולם שלנו
ומדבר על התנאים החשובים ביותר ולא להיכנס לכל הנוסחות המפוארות האלה.
אז זה היה מיון בחירה, ויש לנו קצת מזל שם.
בואו נסתכל על סוג ההכנסה. תן לי ללכת קדימה ולהתחיל גם את זה.
עכשיו שים לב לדפוס שקורה הוא קצת שונה,
ואנחנו התחלנו עם מספרים אקראיים,
אבל אם אנחנו ממש לספור את מספר הצעדים במקרה הגרוע ביותר,
אם הרשימה התחילה לגמרי בבסדר הנכונה,
היינו לנקוט בצעדי n רק כדי להבין עד כמה.
>> אבל אם הרשימה הייתה למעשה לאחור - למשל, במקרה הזה כאן -
אז שם לב שאנחנו באמת צריכים לעשות הרבה יותר עבודה במקרה זה.
ואת זה צריך סוג של מרגיש לך כמו זה הוא סוג של עבודה קשה
כדי לקבל אותם האלמנטים קטנים לשמאל, וזה בגלל שיש לנו מזל.
הרשימה מוינה בטעות בכיוון הפוך.
לעומת זאת, עם סוג ההכנסה אם לחקות את מה שעשינו עם האנשים שלנו כאן
על ידי התחלה עם כולם מסודרים ואז להתחיל, זה אלגוריתם די טוב, נכון?
זה כבר, למעשה, מיון.
אז בואו ננסה לסכם בדיוק כמה זמן הדברים האלה לוקחים אותנו
על ידי החדרה רק קצת ז'רגון או סימון שבעצם הרבה יותר פשוט
מסוג fanciness של מציע.
הדבר הזה כאן, גדול O זה על המסך, מה שמדען מחשב בדרך כלל להשתמש
כדי לתאר את זמן הריצה במקרה הגרוע ביותר של אלגוריתם.
>> שוב, על ידי מקרה הגרוע ביותר, זה לגמרי תלוי קשר.
למה אנחנו מתכוונים במקרה הגרוע לחלוטין משתנה בהתבסס על הבעיה שאנחנו מדברים עליו.
אבל במקרה של מיון, מה התרחיש הגרוע ביותר האפשרי?
הכל אחורה כי זה פשוט מרגיש כמו שאומר הרבה עבודה בשבילנו.
אני כבר רשמתי כמה מהאלגוריתמים שראינו עד כה:
חיפוש לינארי, חיפוש בינארי כמו בספר טלפונים או את פיסות נייר,
אז מיון בועות, מיון בחירה, והחדרת מין כמו שראינו בבני האדם שלנו,
ואז 1 אחר זה הסוף של דבר הולך להיות שם למזג מיון.
אז בחיפוש ליניארי במקרה הגרוע ביותר, כמה צעדים נדרש כדי למצוא את המספר 7
אם יש דלתות n כמו שון פנים? >> [תלמיד] נ
נ אז אנחנו הולכים לכתוב גדול O של n.
אני רק הולך למלא מקומות מסוימים. זה רק רשת של חללים.
אבל במקרה הטוב לחיפוש ליניארי, 7 אולי היו בתחילה מאוד של הרשימה,
שון ואולי התחיל לחפש בתחילת הרשימה.
אז אם אתה משתמש בחיפוש ליניארי ורק בודק משמאל לימין או אולי ימין לשמאל -
הם שווים ערך - במקרה הטוב כמה צעדים עשויים לחפש ליניארי,
כמו האלגוריתם של שון, לקחת? רק שלב 1.
>> אז אני הולך להגיד שזה סימון האומגה.
זה רק אומגת הון.
אומגה היא פשוט הדרך של אמירה הסקסית מקרה טוב זמן הריצה.
אז במקרה הטוב את זמן הריצה הוא צעד אחד או מספר קבוע של צעדים -
1 במקרה זה - אבל במקרה הגרוע ביותר, הגדול O, הוא למעשה שלבי n.
וזה כאן, תטא, אנחנו באמת לא הולכים להסתכל על עכשיו.
זה לא רלוונטי לדוגמה זו בפרט.
אבל עכשיו בואו ננסה חיפוש בינארי.
במקרה הגרוע ביותר, עם חיפוש בינארי, כמה צעדים זה הולך לקחת כדי למצוא את המספר 7
או מה שאנחנו מחפשים? >> [התלמיד] התחבר n.
עדיין הולך לקחת n יומן כי בדיוק כמו אלכס קבל מזל
כאשר אנחנו באמת עבדנו דרך הבעיה באופן שיטתי
והיא לא מוצאת את המספר 7, עד שהדלת האחרונה שהיא מביטה בו,
למרות, בהגינות, היא חייבת לזרוק את דלתות מסוימות לאורך הדרך,
החיפוש בינארי במקרה הגרוע יש לו זמן ריצה של log n.
ושוב, שמדבר אל חלוקה הזאת וכובשת.
אבל מה במקרה הטוב?
ואלכס ממש חווה שמקרה הטוב צדק כשעלה על במה.
כמה צעדים שלא ייקח בחיפוש בינארי? >> [תלמיד] 1.
1, רק בגלל שהיא זכתה בכבוד גדול.
אבל זה בסדר, כי האומגה מתייחסת לתרחישים במקרה הטובים ביותר,
כניסות הטובות ביותר במקרה, גם אם זה רק מזל עיוור אקראי.
>> עכשיו, גם את זה אנחנו הולכים פשוט סוג של חופשה ריקה לעת עתה.
מה דעתך על עכשיו מיון בועות?
במקרה הגרוע ביותר במיון בועות, כולם בסדר הפוך,
לכן אנחנו צריכים לעשות הרבה מבעבעים.
אבל כמה צעדים שהוא מתכוון לנקוט במקרה הגרוע ביותר? >> [התלמיד] N בריבוע.
זה היה n בריבוע, משום שאם אתה חושב על זה,
אם הרשימה היא לגמרי הפוכה - 8 הן כאן, 1 הוא כאן -
כדבר מתחיל לבעבע, המספר 8 הוא הולך לעבור בדרך זו, בדרך זו,
בדרך זו, בדרך זו, אבל איפה היא המספר 7 במקרה הגרוע ביותר?
הנה הוא עדיין שם. אז אנחנו צריכים לעשות את זה שוב ושוב.
וזה שבו אנו מקבלים את צעדי n, אז n - 1 צעדים, ואז n - 2 שלבים.
ואם אתה לוקח את המילה שלי בשביל זה - כי אם סוג של להכפיל אותו,
זה בערך n בריבוע בסוף עם כמה מונחים אחרים שאנחנו פשוט מתעלמים לעת עתה -
אז במקרה הכי הגרוע מיון הבועות הוא n בריבוע, פחות או יותר.
אבל מה במקרה הטוב למיון בועות?
מהו התרחיש הטוב ביותר? כל המספרים מסודרים כבר.
ומה היה האוריסטי נהגתי, הטריק הייתי,
להבין שלא עשיתי כל עבודה ולכן יכול להפסיק מוקדם?
[תלמיד] תבדקו את זה פעם אחת. >> בדוק את זה פעם אחת. אבל מה שאני עושה בדרך?
אני עוקב אחרי כמה חילופים שעשיתי.
והבנתי שאם לא ספרתי כל החלפות על האצבעות שלי, אז אני לא עשיתי את עבודה.
אני בהחלט לא צריך לנסות לעשות שום עבודה שוב, אז אני יכול פשוט להפסיק.
>> אז במקרה הטוב של מיון בועות כאשר הרשימה כבר ממוינת,
מה היית אומר סימון האומגה הוא, במקרה הטוב זמן ריצה?
זה פשוט n. יש לנו עבודה לעשות, אבל יש לנו רק לעשות טיול שווה של 1 של עבודה.
וגם כאן אני הולך לעזוב את החלק הזה ריק.
ועכשיו מיון בחירה.
מיון בחירתי שמריטת האדם הקטן ביותר שוב ושוב.
ומה שאנחנו לא אומרים את משך ההפעלה של שהיה?
זה היה n בריבוע במקרה הגרוע ביותר.
ולרוע המזל, במקרה הטוב זה גם n בריבוע
משום שאין לי מין נוף היודע כל של העולם כולו;
אני יודע רק על איטרציה מלאה כי אני כבר מצאתי את האדם הקטן מאוד.
אז סוג של מיון בחירה מבאסת במובן זה,
אבל היתרון הוא שזה די אינטואיטיבי.
זה די קל לקוד עד כי כל מה שאתה צריך לעשות הוא לכתוב כמה מקונן ללולאות,
בדרך כלל, שעובר מחפש את האלמנט הקטן ביותר
ואז מניח את היסוד הקטן ביותר שבו היא שייכת בסוף הרשימה.
אז גם כאן הולך להיות תחלופה.
כמות הזמן שלוקח לך לחשוב ולמעשה לפתח משהו על ידי כתיבת קוד
יכול מאוד לקחת יותר זמן אם אתה רוצה ביצועים טובים יותר ומהר יותר אלגוריתם.
>> אבל אם אתה באמת רק סוג של משהו עד קוד מהיר ומלוכלך
ורק סוג של לקחת את הרעיון המטופש ביותר האפשרי שאתה יכול לחשוב,
זה עלול לקחת לך כמה דקות לקוד, אבל עם ערכות נתונים גדולות
האלגוריתם שלך עלול לקחת שעות כדי לרוץ.
וגם אני בבית הספר למוסמכים הייתי לפעמים להפוך אותם לפשרות.
זה יהיה 03:00, אני מנסה לנתח כמה ערכת נתונים גדולות מאוד
קשור למחקר הביטחון שאני עושה, וזה היה או לבלות 5 דקות
tweaking התכנית שלי כדי לנתח את הנתונים והולכים לישון
או לבלות 8 שעות מקבלות אותו בדיוק כך שהוא פועל באופן מיידי ולא ללכת לישון.
וכך גם שם זה סוג של החלטה מודעת.
פחות זמן פיתוח, לישון יותר.
במבט לאחור, אני בטח לא צריך לעודד זאת
כאשר המטרה כאן היא כדי לייעל את האיכות של הקוד,
אלא שגם בעולם האמיתי היא תחלופה סבירה מאוד.
פחות זמן, פחות ביצועים, או להיפך.
אז הנה אנחנו סוף הסוף מקבלים הזדמנות לדבר על תטא.
תטא סימון הוא משהו מדעני מחשב יכולים להעלות בשיחה
כאשר גדול O והאומגה יקרו להיות אותו הדבר.
אתה אומר לתטא באמת לשלוח את ההודעה שזה סוג של כל כך סתום.
לא משנה אם התרחיש הוא טוב או רע, זה של N בריבוע.
אז זה פשוט לא רלוונטי בסיפורים אלה כאן.
מיון ההכנסה הוא אחד האחרון שהסתכלנו,
שבו אני פשוט מכניס את כולם למקום הנכון.
במקרה הטוב מה היה זמן הריצה של מיון הכנסה כפי שראינו אותו כאן?
[התלמיד] המקרה הטוב? >> המקרה הטוב.
>> זה היה n כי במקרה הטוב כולם מסודרים,
וסמי ואף אחד אחר לא באמת היינו צריכים לזוז בכלל.
הם כבר היו במקום הנכון שלהם.
אז סוג ההכנסה במקרה הטוב הוא, במקרה זה, n.
אבל במקרה הגרוע ביותר זה סוג של n בריבוע. למה?
אם הרשימה של בני אדם שלי היא בסדר הפוך,
אני מתחיל ראשון עם המספר 8 ואני מכניס אותו או אותה למיקום הנכון, וזה ממש כאן.
אני סוג של מעבר לצד. החבר 'ה האלה לא ממוינים, הוא או היא מסודרת.
אבל עכשיו אני במקרה שתמצא הבא? >> [תלמיד] 7.
7 במקרה הגרוע ביותר, כי זה בסדר הפוך.
>> אז הנה הם 7. בו 7 לא שייכים? בהחלט מאחורי.
אבל עכשיו 7 בעצם שייכים לא מייד מאחוריי, אבל מאחורי המספר 8,
אז יש לי לומר, "סלח לי, מספר 8, אתה יכול בבקשה לעבור דרך זו
"כדי לפנות מקום ל7?" עכשיו אני נתקל 6.
"אה, סליחה, מספר 8 ומספר 7, אתה יכול לעבור כדי לפנות מקום ל6?"
אז במילים אחרות, עם סוג ההכנסה, למרות שאני לא עושה הרבה תנועה,
אנשים שמאחוריי עושים הרבה יותר עבודה, ושיש לו לעלות פעם מישהו.
זה הולך לעלות זמן המחשב.
אז במקרה של סוג ההכנסה שעדיין סובלים.
אם אתה מתחיל להוסיף את המספר הכולל של צעדים, אנחנו בסופו של דבר פוגעים בגסות n בריבוע
כי החבר 'ה האלה צריכים לפנות מקום לאדם להיות מוכנס בחזרה לאותה רשימה.
ולכן במקרה זה הוא פשוט תטא אינו ישים לסיפור המסוים בהישג יד.
זה כל מה שנחמד וטוב. יש לנו 3 דרכים שונות אלה מדברים על זמן הריצה.
אבל מה זה בעצם אומר במונחים ריאליים, אם אנחנו באמת מנסים לקודד את אלגוריתם?
>> הרשו לי להציע שיש אלגוריתם אפילו טוב יותר שם בחוץ
שעצמו יש כמה פשרות.
אנחנו הולכים לקרוא לזה מיזוג כזה, וזה סוג של האלגוריתם הקסום הזה
שפשוט עובד מהר יותר איכשהו, וזה כל כך קל לבטא, לפחות בpseudocode.
היישום מסוג מיזוג אלגוריתם זה הולך להיות כדלקמן.
כאשר אתה נתון n אלמנטים - מספרי n, n אנשים, מה - ראשית יש לבדוק את השפיות.
אם n הוא פחות מ 2, למזג מיון פשוט מפסיק. הוא חוזר, אם אפשר לומר כך.
למה שתפסיק אם n הוא פחות מ 2? >> [תגובת תלמיד לא נשמעה]
נכון. ושוב, n הוא לא המספר ברשימה, n הוא הגודל של הרשימה.
אם n הוא פחות מ 2, זה אומר שהרשימה שלך היא 1,
לאן אתה מסודר ברור אם זה מספר 1,
או 0, ובמקרה כזה אין מה למיין,
כך שאנחנו צריכים את זה סוג של מקרה בסיס.
אם הרשימה היא כל כך קצרה שיש לך בכלל מה לעשות, ממש לא עושה כלום. Return.
אחרת לסדר את חלקו השמאלי של היסודות, לאחר מכן למיין את החצי הימני של האלמנטים,
לאחר מכן למזג את 2 חצי הממוינים.
>> זה סוג של נראה כמו רמאי קטן שבי אני שואל אותך איך למיין אלמנטים
ואתה אומר לי, "מיין המחצית השמאלית, למיין המחצית הנכונה."
אני כמו, "בסדר. איך למיין את חלקו השמאלי?"
"מיין את המחצית השמאלית של המחצית השמאלית, למיין את המחצית הימנית של מחצית השמאל, ולאחר מכן עשה".
אתה סוג של הגדרת המחזור מה זה אומר למיין,
אבל מסתבר שזה ממש מבריק במקרה זה.
זה לא באמת מעגל הקסמים הזה שלא נגמר
בגלל זה נגמר מתי? >> [תלמיד] בעת שתגיע הדבר 1.
כאשר אתם מגיעים דבר 1.
אז למרות שאתה יכול להתחיל עם 8 אנשים ואני אומר, "מיין במחצית השמאלית של האנשים האלה,
4 האנשים האלה ", אז אני אומר," איך אתה למיין את חלקו השמאלי? "
"טוב, למיין את 2 אנשים כאן". ואז אתה כמו, "בסדר, בסדר".
"איך אתה למיין את המחצית השמאלית של האנשים האלה?"
"רק בערך אדם 1 זה כאן." מה ההתגלות המבריקה עכשיו?
יש לי למיין אדם 1. עשה. אני לא צריך לעשות את כל עבודה.
אבל עכשיו יש לי למיין את האדם הזה, אבל הם אדם אחד, אין מה לעשות.
>> אז כנראה הקסם הוא בשלב השלישי: למזג את החצאים הממוינים.
סוג אז למזג לוקח תובנה המבריקה הזה, שאם אתה שובר בעיה גדולה למטה
ל 2 בעיות קטנות יותר, באופן זהה בגודל
ואז פשוט סוג של דבק יחד את הפתרונים הקטנים יותר בסוף,
אני מציע שאנחנו יכולים לעשות הרבה, [קול קשה] הרבה יותר טוב
מכל מיון בחירה או מיון הכנסה.
אני בעצם כבר התעלמות שבמשך חצי שעה, אבל אני באמת לא יודע מה קורה
בחוץ היום. [זמזום] [שחוק]
אז בואו נראה אם ​​אנחנו יכולים לראות את זה עם קצת עזרה מידידנו רוב באודן.
ישנם 2 צעדים גדולים בתהליך של מיון מיזוג.
ראשית, ברציפות לפצל את הרשימה של כוסות לחצי
עד שיש לנו חבורה של רשימות רק עם 1 הכוס ב.
אל תדאגו אם רשימה מכילה מספר אי זוגי
ואתה לא יכול לעשות חתך נקי לחלוטין ביניהם.
רק באופן שרירותי לבחור לאיזו רשימה שתכלול את הכוס הנוספת פנימה
אז בואו לפצל הרשימות האלה.
עכשיו יש לנו 2 רשימות.
עכשיו יש לנו 4 רשימות.
עכשיו יש לנו 8 רשימות עם כוס אחת בכל רשימה.
אז זהו זה לשלב 1.
עבור שלב 2 שוב ושוב למזג זוגות של רשימות באמצעות אלגוריתם המיזוג שלמדנו בעבר.
מיזוג 108 ו 15 אנחנו בסופו עם הרשימה 15, 108.
מיזוג 50 ו 4 אנחנו בסופו של דבר עם 4, 50.
מיזוג 8 ו 42 שנסיים עם 8, 42.
ומיזוג של 23 ו 16 אנחנו בסופו של דבר עם 16, 23.
עכשיו כל הרשימות שלנו הן בגודל 2.
שים לב שכל אחד 4 הרשימות ממוינת,
כדי שנוכל להתחיל התמזגות זוגות של רשימות שוב.
מיזוג 15 ו 108 ו 4 ו 50 אנחנו לוקחים 1 4, אז 15,
אז 50, אז 108.
מיזוג 8, 42 ו 16, 23 אנחנו לוקחים 8, 16, 1
אז 23, ואז 42.
אז עכשיו יש לנו רק 2 רשימות של גודל 4, כל אחד מהם ממוין.
אז עכשיו אנחנו למזג 2 הרשימות האלה.
ראשית אנחנו לוקחים 4, אז אנחנו לוקחים 8, אז ניקח 15
ו 16 ו 23 ו 42 ו 50 ו108.
ואנחנו נעשינו. עכשיו יש לנו רשימה ממוינת.
>> רוב היה סוג של ניצול של משהו שלא עשו עדיין.
הוא הציע, אבל אנחנו לא ממש נעשה את זה.
הוא עושה משהו פיזי עם כוסות שמרמזות
הוא בילה חלק המשאב מלבד זמן. >> [תלמיד] חלל. >> זה היה חלל.
העובדה שהוא היה זה סוג של שולחן דו רמה שם היה לו מקום כאן
וכאן מקום למעשה רומז שהוא משתמש בכמות הכפול של החלל
כמו כל האלגוריתמים שלנו עד כה - סוג ההכנסה, מיון בועות, או בחירת סוג -
אבל הוא היה מינוף שטח נוסף לזה סוג של דברים לנוע קדימה ואחורה
תוך שמירה על סדר בדברים.
ולמרות שזה מרגיש כאילו הגענו לרשימה ממוינת, שהרגיש כאילו זה לקח זמן.
במציאות, מה שרוב עושה בדיוק את זה אלגוריתם.
הוא לקח תחילה את הבעיה של הגודל n, חלק אותה לחלק שמאלי וחצי נכון.
זה הזמן שבו עבר את הכוסות. ואז הוא חזר על תהליך זה.
הוא חלק 4 לתוך 2 סטים של 2 לכאן וכאן.
ואז הוא חזר על תהליך זה וחלק 2 לתוך 2 סטים של 1 לכל אחת מהכוסות השונות האלה.
וכאן ההזדמנות המבריקה מתעוררת.
בשלב זה בסיפור, רוב היו 8 רשימות של גודל 1,
שכולם מסודרים כבר.
>> אז מה הוא ממשיך לעשות?
Pairwise הוא לקח רשימה זו מסודרת ורשימה ממוינת זו ומזג אותם.
ואז הוא לקח את זה ומזג אותם, אז זה אחד ומזג אותם,
אז זה אחד ומזג אותם.
ואז מה הוא עושה עכשיו?
הוא מחדש התמזג לאחר מכן את הרשימות הגדולות יותר, ואז לחזור מתמזג הרשימות הגדולות יותר.
ואם אתה חושב על זה רק באופן אינטואיטיבי לעכשיו, מה שהוא באמת עושה?
הוא חלק את הבעיה במחצית, במחצית, במחצית, במחצית
על מנת לקבל את הרשימות קטנות אלה סופר.
ואז הוא היה סוג של שילוב כפול, כפול, כפול, כפול.
אז הוא עושה עבודה כפולה כפי שראינו עד כה
עם כל מה שקשור פרד ומשול, אבל לא עניין גדול.
כפליים עבודה היא לא כזה ביג דיל. זה רק גורם קבוע.
וממש כמו ביטוי אריתמטי בעבר, אני רק הולך לחצות את גורמים קבועים
כמו פעמים 2. למי אכפת? אם זה 2 מיליארדים פעמים 2, זה עדיין הרבה שלבים.
אז בשלב מיזוג זה נראה תובנה המרכזית.
בואו נעבור את זה רק לפני בחינה מספרית - אה, זה לא צריך להימשך עוד.
בואו נעבור את זה מבחינה מספרית רק כדי לראות באמת איך זה יתגלגל.
זה בעיקר רק האנימציה של איש קטן ומסכן.
בואו מציעים זאת.
זמן הריצה של מיון מיזוג - אנחנו רק צריכים דרך לדבר על זה.
זה לא מתמטיקה, זה פשוט סוג של דרך תמציתית להביע את עצמנו.
אז T מייצג את הזמן וn מייצג את מה? >> [תלמיד] גודל -
>> [מלאן] גודל הבעיה, את מספר האנשים.
אז אני טוען שהזמן פועל כדי למיין אנשי n הולך להיות 0 כמות הזמן
אם n הוא פחות מ 2, כי אם יש לך 1 כוס או אין כוסות, אין לך מה למיין.
אבל באופן כללי יותר, אני הולך להציע כי הזמן פועל כדי למיין אלמנטי n
הולך להיות הזמן שלוקח כדי למיין את חיצו השמאלי בתוספת המחצית הימנית
תוספת - מה זה נוסף + n? >> [תלמיד] מיון מיזוג.
[מלאן] הם ממש מתמזגים, כי אם יש לך n / 2 אלמנטים כאן
ויש לך n / 2 אלמנטים כאן, כמה זמן לוקח לאחד אותם?
בדיוק כמו רוב, אתה צריך לאזור את זה כאן, אולי לקטוף כאן,
לקטוף כאן, למרוט כאן, למרוט לכאן.
אתה חייב לגעת בי כל אחת מכוסות פעם אחת.
ואם יש 4 כוסות ועוד 4 כוסות, זה 8 כוסות
או אופן כללי יותר, 8 כוסות n.
לכן, שלב המיזוג נוכל לבטא כn,
וזה ממש כרוך במספר הפעמים לשדוד נגע פיזי
אחד מאותם כוסות מפלסטיק.
אז בואו עכשיו נעשה דוגמה שרירותית.
אם יש 16 כוסות, מה זמן הריצה של מיון, באמצעות האלגוריתם של רוב, 16 כוסות?
זה פי 2 מכמות הזמן שלוקח למיין 8 כוסות
בגלל שיש לנו 8 כוסות כאן, 8 כוסות כאן.
אני לא יודע כמה זמן זה לוקח, אז אנחנו מכלילים אותו כT לרגע.
מי יודע מה זה?
אבל עכשיו אני יכול למיין של רקורסיבי או שוב ושוב שואל את אותה השאלה.
כמה זמן לוקח למיין 8 כוסות?
8 כוסות אני עומד לומר לוקחת את כמות הזמן שלוקח למיין 4 כוסות ועוד 4 כוסות,
אז התמזגותם יחד.
בסדר. אנחנו נכנסים למחזור כבר. כמה זמן זה לוקח כדי למיין 4 כוסות?
הזמן שלוקח למיון 4 כוסות הוא 2 כוסות בתוספת 2 כוסות מיון תוספת תהליך המיזוג.
בסדר. כמה זמן זה לוקח כדי למיין 2 כוסות?
2 כוסות היא כמות הזמן שלוקח למיין 1 כוס בתוספת הזמן שלוקח למיין עוד כוס
עוד הסכום של זמן שלוקח למיזוג, וזה רק 2.
>> בסדר. השאלה אחרונה. כמה זמן זה לוקח כדי למיין 1 כוס?
הנה מקרה הבסיס שבו צפו היינו נפגעתי קודם לכן.
העובדה שהיא לא לוקחת עבודה כלשהי כדי למיין הקטן ביותר של הבעיות
אמצעים שעכשיו, סוג של סגנון בית הספר יסודי,
אנחנו יכולים פשוט ללכת להתחיל חיבור המספרים האלה בחזרה פנימה
כעת אנו יודעים מה T של 1 הוא, ולכן אני יכול לחבר 0 עבור T של 1.
שייתן לי את התשובה לT של 2, אשר אז יכול לחבר עד גבוה.
זה ייתן לי T של 4, שבו אני יכול לחבר עד גבוה.
זה ייתן לי T של 8, שבו אני יכול לחבר עד גבוה.
אם באמת הייתי עושה את המתמטיקה שעל ידי חיבור בתשובות האלה ו,
אז אני מקבל T של 16 הוא 64.
ומה 64 מייצגים?
אם T הוא 16, כן, זה פעמים 16 4.
אז אני טוען עכשיו שזמן הריצה של הדבר הזה שנקרא למזג מיון -
וזה הולך להיות הכי מפואר מאלה שראינו עד כה -
הולך להיות שם n log n
כי כמה פעמים יכול לשדוד התפצל חבורה שלמה של כוסות בחצי? היכנס n.
זה אותו כדוגמא ספר טלפונים, זה אותו כדוגמא עצמית הספירה.
>> כמה פעמים אתה יכול לחלק משהו בחצי?
עם זאת, יש צעד מיזוג זה.
ייתכן שתצטרך לחלק את הכוסות לתוך חצי שוב ושוב ושוב,
אבל בכל פעם שאתה הולך צריכה להתמזג.
ואנחנו אמרנו מוקדם יותר כי מיזוג כוסות n נוקט צעדי n
כי יש לך לתלוש כוס, לתלוש כוס, ואתה צריך לגעת בכל כוס אחת,
בדיוק כמו רוב עשה.
אז אם אנחנו עושים משהו יומן n פעמים ואנחנו עושים דברי n בכל אחת מהחזרות האלה,
כל אחד מhalvings האלה, יש לנו n זמני log n.
אז אם נחבר 16 בדוגמה זו, 16 פעמים להיכנס של 16 -
לא לדאוג למה זה מקרה לעת עתה כי אני לא ציירתי את הבסיס -
אבל יומן של בסיס 2 של 16 הוא 4, 16 פעמים 4 הן 64.
אבל לעומת זאת, אם הייתי משתמש במיון בועות או מיון מיון או החדרת בחירה עם 16 מספרים,
מה יהיה זמן הריצה היה אם n הוא 16?
זה יהיה 16 בריבוע, שהוא 256, גם אם לא עקב אחרי כל המתמטיקה די בי,
256 הם יותר גדולים מ 64. זה באמת takeaway הקסום כאן.
ולהבין שעובד דרך זו בדוגמאות קטנות כרצונכם על pset
עושה את הכל הרבה יותר אינטואיטיבי.
אבל מה זה באמת אומר במונחים של התחושה של אלגוריתם זה הוא זה:
אם אנחנו באמת מסתכלים על סוג המיזוג כאן - תן לי למשוך אותו בחלון זה כאן -
זו היא דוגמה מעט שונה לפיה יש לנו את כל 3 של אלגוריתמים אלה -
בועה, בחירה, ולמזג - רק לצד זה.
>> כולם התחילו עם ברים אקראיים, וזה טוב.
לאף אחד אין יתרון מהותי על פני אחר.
אני הולך ברגע לחץ על כל אחד מאלה אנימציות - התחל, לחץ על התחל, התחל -
מהר ככל שאני יכול, כדי ש, בערך, כולן מתחיל באותו הזמן,
ובואו נחשוב שהמקרה הגרוע של מיון בועות פועלים זמן מה? >> [התלמיד] N בריבוע.
N בריבוע. המקרה הגרוע ביותר של מיון הבחירה זמן הריצה הוא? N בריבוע.
ומעין מיזוג היא ככל הנראה - גם אם אתה לא ממש מבין את כל המתמטיקה עכשיו,
זה יהפוך הרבה יותר אינטואיטיבי לאורך זמן - כלומר, אנחנו טוענים, n הזמנים log n.
ובגלל יומן n הוא בהחלט פחות מ n פעם יש לנו מספרים גדולים,
n זמני היומן n הוא קטן מ n פעמי n או n בריבוע.
אז מה זה בעצם מרגיש להיות אלגוריתם טוב יותר במונחים של זמן ריצה,
זמני יומן n n לעומת n בריבוע? הנה אנחנו מתחילים. קליק, קליק, קליק.
>> זה מה שזה אומר להשתמש במשהו כמו סוג המיזוג.
יש לנו כרגע. בואו לראות מה קורה כאן.
[מגחך] כסף של מי הוא על מיון בועות?
זה לא תלוי בקלט לפעמים.
בואו נראים.
נו באמת. זה מרגיש כאילו הוא תופס. >> [תלמיד] עבור, מיון בועות!
[סטודנטי ממלמל]
[מלאן] כן, כן.
[סטודנטים הממלמלות] קדימה, קדימה, קדימה!
[כל מריע] [מחיאות כפות]
אז עכשיו עם 1 ההדגמה אחרונה, סופית, אם זה קצת מסובך לקלוט את המתמטיקה
או סוג של ההדמיה לשם, אתה ממש יכול לשמוע את מהירויות
של אלגוריתמים שונים בצורה שונה.
זה מישהו שממש עשה אנימצית מקורבים נשמעים
בתהליך של החלפה והגובה של הסורגים.
כפי שנראים כאן, יש עוד כמה אלגוריתמי מיון שם בחוץ, כי אנשים שחשבו עליו.
ראשון זה הולך להיות סוג ההכנסה, וזה יהיה לטוס דרך
ולתת לך תחושה נשמעת של איך זה עובד אלגוריתמים השונים.
כאן מעין כניסה.
[צפצוף אלקטרוני]
[מלאן] מעין בועה.
[מהר צפצוף אלקטרוני]
[מלאן] מיון בחירה.
[מהר צפצוף אלקטרוני]
[מלאן] מיון מיזוג.
[צפצוף אלקטרוני]
[צפצוף מאט] [שחוק]
[מלאן] סוג Gnome.
[צפצוף אלקטרוני]
>> זה CS50. ניראה אותך בשבוע הבא. [מחיאות כפות ומריעות]
>> [CS50.TV]