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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אריק שמידט: יש לנו שאלות, ואנו שואלים שאלות המועמדים שלנו, ואת זה הוא מלארי שווימר. 

הנשיא אובמה: על אישור. 

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

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

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

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

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

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

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

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

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

באופן ספציפי למקום בCS50 IDE, וזה, מדי, יהיה קצת פשטני לרגע, יש, או היה על זמן, קובץ בשם io.c הסטנדרטי, שמישהו הידור ל io.s סטנדרטי או שווה הערך, שמישהו אז התאסף לio.o הסטנדרטי, או שמתברר ל קובץ שונה מעט פורמט שיכול להיות שונה סיומת קובץ לגמרי, אבל בתאוריה ומושגית, בדיוק צעדים אלה היו צריכים לקרות בצורה כלשהי. כלומר, שעכשיו כאשר אני כותב תכנית, hello.c, שרק אומר, שלום עולם, ואני משתמש בקוד של מישהו אחר כמו printf, שהיה פעם על זמן, בקובץ בשם io.c הסטנדרטי, אז איכשהו אני צריך לקחת אותי קוד אובייקט, אפסים שלי ואלה, והאובייקט של האדם ש קוד, או אפסים ואחדים, ואיכשהו לקשר אותם יחד ל קובץ סופי אחד, בשם שלום, ש יש את כל האפסים ו אלה מתפקידו העיקרי שלי, וכל האפסים ואלה לprintf. 

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

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

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

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

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

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

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

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

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

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

SPEAKER 1: הוא היה בחטיף בר אכילת גלידה שוקולד חמה. היה לו את זה על כל פניו. הוא לובש שוקולד שכמו זקן SPEAKER 2: מה אתה עושה? SPEAKER 3: המממ? מה? 

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

SPEAKER 3: אתה יודע מה, דן? אתה טובל את הדרך שאתה רוצה לטבול. אני טובל את הדרך שאני רוצה לטבול.