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

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

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

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

קהל: אה, זה הוא הולך לקחת לנצח. 

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

דובר: ובשביל כיף, בואו נשים את שעון עצר. 

קהל: כל כך הרבה כל כך הרבה כיף כיף,. 

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

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

קהל: כן. 

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

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

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

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

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

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

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

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

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

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

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

-Well-- 

-אני מצטער, maybe-- 

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

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

-We've לי המרגלים שלנו שם. 

"או-קיי, בואו לשאול שונה שאלת ראיון. 

[END הפעלת וידאו] 

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

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

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

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

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

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

קהל: מציאת המספר הגדול ביותר ברשימה? 

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

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

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

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

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

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

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

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

קהל: מיון בועות? 

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

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

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

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

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

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

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

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

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

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

קהל: n בריבוע. דובר: n בריבוע. למה? 

קהל: בגלל שיש לך להגדיר [לא ברור]. 

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

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

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

קהל: פיטר. 

דובר: מה זה? 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

קהל: דארן. 

דובר: דן. דן צעד קדימה. 

קהל: דארן. דובר: דארן, עשה. האם אתה אומר דארן או דן? 

קהל: דארן. 

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

קהל: לוק. 

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

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

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

קהל: אדריאנו. 

דובר: אדריאנו. אדריאנו כעת מסודרים. ואיך קוראים לך? 

קהל: אלכס. 

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

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

קהל: עומר. 

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

קהל: כריס. 

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

קהל: מרינה. 

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

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

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

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

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

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

קהל: התחבר n. 

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

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

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

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