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

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

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

אז n בריבוע. ומה היה n? 

קהל: מספר האלמנטים. 

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

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

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

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

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

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

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

[שחוק] 

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

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

[שחוק] 

-טוב, אה - 

-אני מצטער. אולי אנחנו צריכים - 

לא, לא, לא, לא, לא. 

-זה לא - אישור. 

אני חושב שהיית עושה-מיון הבועות תהיה בדרך הלא נכונה ללכת אליו. 

[שחוק] 

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

-קדימה, שאמר לו את זה? אישור. 

[השמעת וידאו הסוף] 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

קהל: מציאת האורך של משתנה. 

דוד Malan: מציאת אורך משתנה? 

קהל: לא, אורך אם זה כבר מסודר. 

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

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

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

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

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

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

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

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

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

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

זה אחד, ולבסוף, אומגה של n log n. אז n log n, אנחנו לא ממש לדבר על עדיין, אבל - 

קהל: מיזוג סוג? 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[שחוק] 

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

[שחוק] 

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

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

מישל: מישל. 

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

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

מישל: הו, זה כל כך מוזר. 

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

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

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

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

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

קהל: מיין המחצית השמאלית. 

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

קהל: מיין המחצית השמאלית. 

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

PRINCESS דייזי: הנסיכה דייזי. 

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

מיין המחצית הימנית, שהיא - מה השם שלך? 

לינדה: לינדה. 

דוד Malan: לינדה. ולכן מה שאנחנו עושים עכשיו, כי יש לנו רשימה של גודל 1? 

קהל: שבות. 

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

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

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

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

קהל: מחצית ימנית. 

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

JESS: ג'ס. 

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

מישל: מישל. 

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

להריץ אחורה עוד יותר בסיפור. מה הצעד בא? 

קהל: מיזוג. 

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

[שחוק] 

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

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

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

דוד Malan: טוב. 

רמקול 1: ואז - 

דוד Malan: מי עושה המיקרופון ללכת הלאה? 

רמקול 1: המספר הבא. 

רמקול 2: אז אני חצי נכון של המחצית השמאלית של מחצית שמאלית, ואני חוזר. 

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

רמקול 2: אנחנו רוצים לראות מי קטנים יותר. 

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

רמקול 3: אז אני מחצית מימין מחצית שמאלית, וn שלי היא פחות מ 1, אז אני פשוט הולך לעבור - 

דוד Malan: טוב. 

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

רמקול 3: אז אנחנו הולכים אחורה. 

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

קהל: מיזוג. 

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

3 הולך ראשונה. ואז 5, כמובן. לאחר מכן 7, ועכשיו 8. אוקיי, ועכשיו אנחנו? 

קהל: לא נעשה. 

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

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

אז אנחנו שמים את מישל כאן. ומי שיש לי מספר 2? מספר 2 מגיע על גב גם כן. מספר 3? מצוין. מספר 4, מספר 5, מספר 6, מספר 7, ואת מספר 8. 

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

רמקול 1: האם להיכנס n להיות לשבור אותנו לשניים - החלוקה לשתיים, למעשה. 

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

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

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

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

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

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

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

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

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

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

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

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

-זה צעד אחד לזה. עבור שלב השני, שוב ושוב למזג זוגות של רשימות. 

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

באופן שרירותי, רק לבחור את - עכשיו יש לנו ארבע רשימות. למד בעבר. 

מלאן דוד: יש לנו ללכת. 

108-מיזוג ו15, אנחנו בסופו עם הרשימה 15, 108. מיזוג 50 ו -4, אנחנו בסופו של דבר עם 4, 50. התמזגות 8 ו -42, אנחנו בסופו של דבר עם 8, 42. ומיזוג של 23 ו -16, אנחנו בסופו של דבר עם 16, 23. 

עכשיו כל הרשימות שלנו הן בגודל 2. שים לב שכל אחד מ ארבע רשימות ממוינות. אז אנחנו יכולים להתחיל מיזוג זוגות של רשימות שוב. מיזוג 15 ו108 ו 4 ו -50, אנחנו הראשונה לקחת 4, אז 15, ולאחר מכן 50, אז 108. התמזגות 8, 42 ו -16, 23, ראשון שאנחנו לוקחים 8, ולאחר מכן 16, ולאחר מכן 23, לאחר מכן 42. 

אז עכשיו יש לנו רק שתי רשימות של גודל 4, כל אחד מהם הוא מיון. אז עכשיו אנחנו למזג את שתי הרשימות האלה. ראשית, עלינו לקחת את 4, אז אנחנו לוקחים את 8, ולאחר מכן אנחנו לוקחים 15, ואז 16, ולאחר מכן 23, אז 42, אז 50, אז 108. 

[השמעת וידאו הסוף] 

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

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

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

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

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

זהו סוג כניסה. 

[TONES PLAYING] 

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

[TONES PLAYING] 

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

[TONES PLAYING] 

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

[TONES PLAYING] 

דוד Malan: זהו סוג המיזוג, אשר באמת אתה יכול להתחיל להרגיש. 

[TONES PLAYING] 

[שחוק] 

דוד Malan: משהו שנקרא GNOME סוג שהוא, שיש לנו לא הסתכל. 

[TONES PLAYING] 

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

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

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

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

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

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

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

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

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

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

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

עכשיו, אם אני לוקח T של 2, שהתשובה עליה הוא 2, חבר אותו לקו האמצעי, T של 4, זה נותן לי 2 פעמים 2 בתוספת 4, אז 8. אם אני לאחר מכן חבר ב8 הקודמים קו, זה נותן לי 2 פעמים 8, 16. ואם אנחנו לא אז נמשיך עם זה 24, והוסיף ב16, אנחנו סוף סוף מקבלים ערך של 64. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אז זו היא תוכנה קטנה טיפשית ש שלפתי את טענות כי לעשות את הדברים הבאים. בעיקרי, הוא מצהיר ראשון קרא int x ומקצה לו הערך של 1. אז זה מצהיר y int ו מקצה לו את הערך 2. ואז זה מדפיס את מה שהוא X ו-Y. אז זה אומר, החלפה, נקודת נקודת נקודה. 

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

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

אבל אני טוען שכאשר אני מפעיל את זה קוד, כמו שאני עושה עכשיו - תן לי ללכת קדימה ולהדביק בזה כאן. אני אתקשר noswap.c זה. וכפי שהשם מרמז, זה לא הולך להיות תכנית נכונה. הפוך noswap. / לא החלפה. X הוא 1, 2 y הוא, להחליף, החליף. X הוא 1, y הוא 2. זו בטעות יסודה, אפילו למרות שזה נראה מושלם לי סביר. ויש לכך סיבה, אבל אנחנו לא הולך לחשוף את הסיבה עדיין. 

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

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

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

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

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

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

-אחת, שתיים, שלוש. 

[צורח] 

-אתה מקבל מכונית! אתה מקבל מכונית! 

דוד Malan: אנו רואים שלך ביום רביעי. 

-אתה מקבל מכונית! אתה מקבל מכונית! אתה מקבל מכונית! אתה מקבל מכונית! אתה מקבל מכונית! 

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

-כל אחד מקבל מכונית! כל אחד מקבל מכונית! 

[השמעת וידאו הסוף] 

קריין: בCS50 הבא - 

רמקול 5: אוי ואבוי אלוהים אלוהים אלוהים אלוהים אלוהים אלוהים אלוהים אלוהים אלוהים - 

[משחק ukelele]