[Powered by Google Translate] [סעיף 3 - יותר נוח]
[רוב אודן - אוניברסיטת הרווארד]
>> [זה CS50. - CS50.TV]
>> אז השאלה הראשונה מנוסחת באופן מוזר.
GDB מאפשר לך "באגים" בתכנית, אבל, באופן ספציפי יותר, מה זה ייתן לך לעשות?
אני אענה על השאלה הזו, ואני לא יודע מה בדיוק צפוי,
אז אני מנחש שזה משהו בסגנון שלו מאפשר לך צעד אחר צעד
ללכת דרך התכנית, אינטראקציה עימו, משתנה שינוי, לעשות את כל הדברים האלה -
בעצם לשלוט ביצוע של תכנית לחלוטין
ולבדוק כל חלק נתון של ביצוע התכנית.
אז התכונות האלה תיתנה לך באגים דברים.
אוקיי.
מדוע החיפוש בינארי דורש שמערך יהיה מסודר?
מי רוצה לענות על זה?
[תלמיד] כי זה לא יעבוד אם זה לא מיון. >> כן. [שחוק]
אם זה לא מיון, אי אפשר לפצל אותו לשניים
ולדעת כל מה שמצד שמאל יש פחות והכל בצד הימין
הוא גדול מהערך האמצעי.
כך זה צריך להיות מסודר.
אוקיי.
למה הוא מיון בועות ב O של n בריבוע?
האם מישהו רוצה 1 לתת סקירה מהירה מאוד ברמה גבוהה ממה שמיון בועות הוא?
[תלמיד] אתה בעצם עובר כל רכיב ותקיש את מספר האלמנטים 1.
אם הם יצאו משם להחליף אותם, ואחר כך בודקים כמה האלמנטים הבאים וכך הלאה.
כשאתה מגיע לסוף, אז אתה יודע שהמרכיב הגדול ביותר ממוקם בסוף,
כך שאתה מתעלם מכך כי אחד אז אתה ממשיך בדרכו,
ובכל פעם שיש לך כדי לבדוק פחות אלמנט אחד עד שלא בצע שום שינוי. >> כן.
זה נקרא מיון בועות כי אם להפוך את המערך על צידו כך שזה למעלה ולמטה, אנכי,
אז את הערכים הגדולים ישקעו לקרקעית ואת הערכים הקטנים מבעבעים לראש.
ככה זה קבל את שמה.
וכן, אתה פשוט לעבור.
אתה כל הזמן עובר על המערך, החלפת הערך הגדול יותר
כדי לקבל את הערכים הגדולים ביותר לתחתית.
>> למה זה O של n בריבוע?
ראשית, האם מישהו רוצה לומר למה זה ריבוע O של n?
[תלמיד] כי לכל ריצה זה הולך n פעמים.
אתה יכול להיות בטוח שאתה כבר לקחת את האלמנט הכי הגדול כל הדרך למטה בלבד,
אז אתה צריך לחזור על זה כלאלמנטים רבים. >> כן.
אז קח בחשבון את מה שגדול O אומר ומה אמצעי אומגה גדולים.
הגדול O הוא כמו החסם העליון על כמה איטי זה יכול לרוץ ממש.
אז באומרה של O של n בריבוע, זה לא O של n או אחר זה יהיה מסוגל לרוץ
בזמן ליניארי, אבל זה O של n קוביות
כי זה מתוחם בO של n לקוביות.
אם זה מתוחם בO של n בריבוע, אז זה מתוחם גם על ידי n לקוביות.
אז זה הוא n בריבוע, ובמקרה הגרוע ביותר המוחלט הוא לא יכול לעשות יותר טוב מn בריבוע,
וזו הסיבה שזה O של n בריבוע.
אז לראות מתמטיקה קלה על איך זה יוצא להיות n בריבוע,
אם יש לנו חמישה דברים ברשימה שלנו, בפעם הראשונה כמה החלפות יכולנו פוטנציאלית צריכות לעשות
כדי לקבל את זה? בואו בעצם רק -
כמה החלפות אנחנו הולכים צריכים לעשות בהרצה הראשונה של מיון בועות במערך?
[התלמיד] n - 1. >> כן.
>> אם יש 5 אלמנטים, אנחנו הולכים צריכים לעשות n - 1.
אז בשנייה אחת כמה החלפות אנחנו הולכים צריכים לעשות?
[התלמיד] n - 2. >> כן.
והשלישי הולך להיות n - 3, ולאחר מכן לנוחות אני אכתוב את שני האחרונים
כמו אז אנחנו הולכים צריכים לעשות 2 חילופים והחלפה 1.
אני מניח שהאחרון יכול או לא יכול בעצם צריך לקרות.
האם זה החלפה? אני לא יודע.
אז אלו הם סכומים הכוללים של עסקות חלף או לפחות השוואות אתה צריך לעשות.
גם אם אתה לא מחליף, אתה עדיין צריך להשוות את הערכים.
אז יש n - 1 השוואות בהרצה הראשונה במערך.
אם אתה משנה את סדר הדברים האלה, בואו נעשה אותו שישה דברים כך דברים להיערם יפה,
ואז אני אעשה 3, 2, 1.
אז פשוט סדרנו את הסכומים הללו, אנחנו רוצים לראות כמה השוואות שאנחנו עושים
בכל האלגוריתם.
אז אם אנחנו מביאים החבר 'ה האלה כאן למטה,
אז אנחנו עדיין רק סיכום זאת השוואות רבות נמצאים בה.
אם נסכם אלה ונסכם אלה ונסכם אלה אבל,
זה עדיין אותה הבעיה. אנחנו פשוט לסכם את אותן קבוצות מסוימות.
>> אז עכשיו אנחנו מסכמים n 3 של. זה לא רק 3 של n.
זה תמיד הולך להיות n / 2 של n.
אז הנה אנחנו במקרה יש 6.
אם היה לנו 10 דברים, אז אנחנו יכולים לעשות את זה לקיבוץ 5 זוגות שונים של דברים
וסופו של דבר עם n + n + n + n + n.
אז אתה תמיד הולך לקבל n / 2 n של, ואז זה נעשה לרשום אותו לריבוע n / 2.
וכך למרות שזה הפקטור של חצי, וזה קורה לבוא
בגלל העובדה שדרך כל איטרציה על המערך נשווה 1 פחות
אז ככה אנחנו מקבלים יותר מ 2, אבל זה עדיין הוא n בריבוע.
לא אכפת לנו על הגורם הקבוע של מחצית.
אז הרבה דברי O גדולים כמו זו מסתמכת על פשוט סוג של עושה את זה סוג של מתמטיקה,
עושה סיכומים בחשבון וכאלה סדרה גיאומטריים,
אבל רובם בקורס הזה הם די פשוטים.
אוקיי.
למה הוא מעין כניסה באומגה של n? מה האומגה מתכוונת?
[שני תלמידים שמדברים בו פעם אחת - סתומים] כן. >>
האומגה אתה יכול לחשוב עליו כחסם תחתון.
>> אז לא משנה כמה יעיל אלגוריתם מיון ההכנסה שלך הוא,
ללא קשר לרשימה שחלף ב, תמיד יש להשוות לפחות n דברים
או שיש לו לחזר על דברי n.
מדוע זה כך?
[תלמיד] כי אם הרשימה כבר מיון, דרך החזרה הראשונה
אתה יכול להבטיח רק שהאלמנט הראשון הוא לפחות,
והחזרה השנייה אתה יכול להבטיח רק את שני הראשונות הן
כי אתה לא יודע ששאר הרשימה ממוינת. >> כן.
אם אתה עובר ברשימה ממוינת לחלוטין, לפחות יש לך לעבור על כל המרכיבים
כדי לראות ששום דבר לא צריך להיות עבר בסביבה.
אז עובר על הרשימה ואומר אה, זה כבר מסודר,
זה בלתי אפשרי בשבילך יודע שזה מסודר עד שתבדוק את כל רכיב
כדי לראות שהם מסודרים במטרה.
אז החסם התחתון על מיון הכנסה הוא אומגה של n.
מה המקרה הגרוע ביותר של זמן ריצה מסוג המיזוג,
מקרה הגרוע ביותר להיות גדול O שוב?
אז במקרה הכי הגרוע, איך מעין מיזוג לרוץ?
[תלמיד] N log n. >> כן.
אלגוריתמי המיון הכלליים הם המהירים ביותר n log n. אתה לא יכול לעשות יותר טוב.
>> יש מקרים מיוחדים, ואם יש לנו זמן היום - אבל אנחנו כנראה לא מוכנים -
אנחנו יכולים לראות אחד שעושה טובים יותר מn log n.
אבל במקרה הכללי, אתה לא יכול לעשות יותר טוב מn log n.
וסוג למזג קורה להיות אחד שאתה צריך לדעת על קורס זה שהוא n log n.
ואז אנחנו בעצם להיות יישום זה היום.
ולבסוף, בלא יותר משלושה משפטים, איך עושה את עבודת מיון בחירה?
האם מישהו רוצה לענות, ואני אספור את המשפטים שלך
כי אם אתה הולך על 3 -
מישהו זוכר מיון בחירה?
מיון בחירה הוא בדרך כלל די קל לזכור רק משם.
אתה פשוט לחזר על המערך, למצוא מה הערך הגדול ביותר או קטן ביותר הוא -
מה מטרה שאתה ממיין פנימה
אז בואו נאמר שאנו ממיינים מקטנים ביותר לגדולים ביותר.
אתה לחזר על המערך, מחפש כל האלמנט המינימאלי הוא,
בחר אותו, ואז פשוט להחליף אותו מה שנמצא במקום הראשון.
ולאחר מכן במעבר שני על המערך, לחפש את האלמנט המינימאלי שוב,
בחר אותו, ולאחר מכן להחליף אותו עם מה שיש בעמדה 2.
אז אנחנו רק לקטוף ובחירה בערכי המינימום
והחדרתם לחלק הקדמי של המערך עד שהוא ממוין.
שאלות על זה?
>> אלה בהכרח מופיעים בטפסים שצריכים למלא בזמן שאת הגשת pset.
אלה הם בעצם את התשובות לאלה.
אוקיי, אז עכשיו קידוד בעיות.
אני כבר שלחתי בדוא"ל - האם מישהו לא מקבל דוא"ל ש? אוקיי.
אני כבר שלחתי בדוא"ל את המרחב שאנחנו הולכים להיות באמצעות,
ואם תלחץ על השם שלי - אז אני חושב שאני הולך להיות בתחתית
בגלל r לאחור - אבל אם אתה לוחץ על השם שלי תראה 2 תיקונים.
הגרסה 1 הולכת אני כבר להעתיק ולהדביק את הקוד לתוך החללים
לחיפוש הדבר אתה תצטרך ליישם.
וגרסה 2 תהיה דבר הסוג שאנחנו ליישם לאחר מכן.
אז אתה יכול ללחוץ על גרסת 1 שלי ולעבוד משם.
ועכשיו אנחנו רוצים ליישם חיפוש בינארי.
>> האם מישהו רוצה רק כדי לתת הסבר pseudocode ברמה גבוהה
של מה שאנחנו הולכים לעשות לחיפוש? כן.
[תלמיד] אתה פשוט לקחת את אמצע המערך ולראות אם מה שאתה מחפש
הוא פחות מזה או יותר מזה.
ואם זה פחות, אתה הולך למחצית זה פחות,
ואם זה יותר, אתה הולך למחצית זה יותר ואתה חוזר ואומר שעד שאתה מקבל רק דבר אחד.
[אודן] כן.
שים לב שמערך המספרים שלנו כבר מסודר,
ואז זה אומר שאנחנו יכולים לנצל את זה ואנחנו ראשונים יכולים לבדוק,
בסדר, אני מחפש את המספר 50.
אז אני יכול להיכנס לאמצע.
מזרח קשה להגדיר מתי זה מספר זוגי של דברים,
אבל בואו נגיד שתמיד לחתוך לאמצע.
אז הנה יש לנו 8 דברים, אז באמצע יהיה 16.
אני מחפש 50, ולכן 50 הם יותר מ 16.
אז עכשיו אני יכול בעצם לטפל במערך שלי כרכיבים אלה.
אני יכול לזרוק הכל מ16 מעל.
עכשיו המערך שלי הוא רק 4 האלמנטים האלה, ואני חוזר ואומר.
אז אני רוצה למצוא שוב באמצע, שהוא הולך להיות 42.
42 הם פחות מ 50, אז אני יכול לזרוק את שני היסודות האלה.
זה המערך שנותר לי.
אני הולך למצוא שוב באמצע.
אני מניח 50 היה דוגמה רעה כי אני תמיד זורק דברים לשמאל,
אך באותה המידה, אם אני מחפש משהו
וזה פחות מהאלמנט אני כרגע מסתכל,
אז אני הולך לזרוק את הכל בצד ימין.
אז עכשיו אנחנו צריכים ליישם את זה.
שים לב שאנו צריכים לעבור בגודלו.
אנחנו יכולים גם לא צריכים לגודל שקשה קוד.
אז אם אנחנו להיפטר מזה # להגדיר -
אוקיי.
איך אני יפה יכול להבין מה הגודל של מערך המספרים כיום הוא?
>> כמה אלמנטים במערך המספרים?
[סטודנטים] במדבר, מסגרות ו. האורך?
[אודן] זה לא מקיים ב C.
זקוקים. אורך.
מערכים אין לי נכסים, כך שאין מאפיין אורך של מערכים
שרק ייתן לך עוד עם זאת זה קורה להיות.
[תלמיד] ראה כמה זיכרון יש לו ולחלק בכמה - כן. >>
אז איך אנחנו יכולים לראות כמה זיכרון יש לו? >> [תלמיד] sizeof. >> כן, sizeof.
Sizeof הוא המפעיל שהולך להחזיר את הגודל של מערך המספרים.
וזה הולך להיות שלמים עם זאת יש פעמים רבות בגודל של מספר שלם
מכיוון שזה כמה זיכרון זה באמת תופס.
אז אם אני רוצה מספר דברים במערך,
אז אני הולך לרוצה לחלק בגודל של מספר שלם.
אוקיי. אז זה מאפשר לי לעבור בגודל כאן.
למה אני צריך לעבור בגודל בכלל?
למה אני לא יכול פשוט לעשות כאן גודל int = sizeof (ערימת שחת) / sizeof (int)?
למה זה לא עובד?
[תלמיד] זה לא משתנה גלובלי.
[אודן] שחת קיים ואנחנו עוברים במספרים כערימת שחת,
וזה סוג של בשר על הבאות. כן.
[תלמיד] שחת הוא רק ההתייחסות אליו, כך שהוא יחזור כמה גדול היא שההתייחסות.
כן.
אני בספק אם בהרצאה שראית ערימה עדיין באמת, נכון?
שמנו רק דברתי על זה.
אז הערימה היא שבו כל המשתנים שלך הולכת להיות מאוחסנים.
>> כל זיכרון שהוא הוקצה למשתנים מקומיים הולך במחסנית,
וכל פונקציה מקבלת מקום משלו במחסנית, מסגרתו של המחסנית היא מה זה נקרא.
אז ראשי יש מסגרת המחסנית שלו, ובתוכו הולך להתקיים מערך מספרים זה,
וזה הולך להיות בגודל sizeof (מספרים).
זה הולך להיות גודל של מספרים מחולקים בגודל של אלמנטים,
אבל שכל החיים בתוך המסגרת של המחסנית הראשית.
כאשר אנו קוראים חיפוש, חיפוש מקבל מסגרתו של המחסנית,
מרחב משלו כדי לאחסן את כל המשתנים המקומיים שלה.
אבל טיעונים אלה - כך ערימת השחת הוא לא עותק של כל המערך הזה.
אנחנו לא עוברים בכל המערך כעותק לחיפוש.
הוא רק עובר להתייחסות שהמערך.
אז חיפוש יכול לגשת למספרים אלה באמצעות הפניה זו.
זה עדיין גישה לדברים שחיים בתוך המסגרת של המחסנית הראשית,
אבל בעצם, כשנגיע למצביעים, שאמור להיות בקרוב,
זה מה שהמצביעים הם.
מצביעים הם רק התייחסויות לדברים, ואתה יכול להשתמש במצביעים לגשת לדברים
שנמצאים במסגרות הערימה 'דברים אחרים.
אז למרות שהמספרים הם מקומיים לעיקרי, אנחנו עדיין יכולים לגשת אליה דרך מצביע זה.
אבל מאחר שזה רק מצביע וזה רק הפניה,
sizeof (ערימת שחת) פשוט מחזיר את הגודל של ההתייחסות עוצמה.
זה לא יחזיר את הגודל של דבר זה מצביע.
זה לא יחזיר את הגודל האמיתי של מספרים.
וכך זה לא הולך לעבוד כמו שאנחנו רוצים אותו.
>> שאלות על זה?
מצביעים יהיו הושקעו בפירוט מזוויע יותר באופן משמעותי בשבועות קרובים.
ובגלל זה הרבה דברים שאתה רואה, דברי חיפוש רוב או דברי מיון,
הם כמעט כולם הולכים צריכים לקחת את גודלו האמיתי של המערך,
כי ב-C, אין לנו מושג מה הגודל של המערך הוא.
אתה צריך לעבור באופן ידני את זה פנימה
ואתה לא יכול לעבור באופן ידני בכל המערך כי אתה פשוט עובר בהתייחסות
והיא לא יכולה לקבל את הגודל מההפניה.
אוקיי.
אז עכשיו אנחנו רוצים ליישם את מה שהסביר קודם.
אתה יכול לעבוד על זה לרגע,
ואתה לא צריך לדאוג מקבל הכל באופן מושלם 100% עובדים.
פשוט לכתוב את pseudocode החצי איך אתה חושב שזה צריך לעבוד.
אוקיי.
לא צריך לעשות עם זה לחלוטין עדיין.
אבל, האם מישהו מרגיש בנוח עם מה שיש להם עד כה,
כמו משהו שאנחנו יכולים לעבוד עם ביחד?
האם מישהו רוצה להתנדב? או שאני אאסוף אקראי.
זה לא חייב להיות צודק בכל קנה מידה, אבל משהו שאנחנו יכולים לשנות את מצב עבודה.
[תלמיד] בטח. >> אוקיי.
אז אתה יכול לשמור את השינוי על ידי לחיצה על הסמל השמור הקטן.
אתה Ramya, נכון? >> [תלמיד] כן. >> [אודן] אוקיי.
אז עכשיו אני יכול להציג הגרסה שלך וכל אחד יכול למשוך את התיקון.
וכאן יש לנו - אוקיי.
אז Ramya הלך עם הפתרון רקורסיבית, שהוא בהחלט פתרון חוקי.
יש שתי דרכים שאתה יכול לעשות את הבעיה הזו.
אתה יכול גם לעשות את זה או ערוך את אופן רקורסיבי.
רוב הבעיות שאתה נתקל כי ניתן לעשות זאת באופן רקורסיבי יכולות להיעשות גם ערוך את.
אז הנה אנחנו כבר עשינו את זה באופן רקורסיבי.
>> האם מישהו רוצה להגדיר מה זה אומר לעשות פונקציה רקורסיבית?
[תלמיד] כאשר יש לך פונקציה קורא לעצמו
ולאחר מכן לקרוא על עצמו עד שהוא יוצא עם אמיתי ונכון. >> כן.
פונקציה רקורסיבית היא רק פונקציה שקוראה לעצמו.
יש שלושה דברים גדולים שפונקציה רקורסיבית חייבת להיות.
הראשון הוא כמובן, שהיא ממכנת את עוצמה.
השני הוא מקרה הבסיס.
אז בשלב מסוים הפונקציה צריכה להפסיק לקרוא לעצמו,
וזה מה שמקרה הבסיס הוא עבור.
אז הנה אנחנו יודעים שאנחנו צריכים להפסיק, אנחנו צריכים לוותר בחיפוש שלנו
כאשר תחילת הסוף שווה - ואנחנו מתכוונים לעבור על מה שאומרים.
אבל לבסוף, הדבר האחרון שחשוב לי פונקציות רקורסיביות:
הפונקציות איכשהו צריכות להתקרב למקרה הבסיס.
כמו שאם אתה לא ממש מעדכן כל דבר בעת ביצוע השיחה השנייה רקורסיבית,
אם אתה ממש רק להתקשר לפונקציה שוב באותם טיעונים
ואין משתנים גלובליים השתנו או משהו,
אתה לעולם לא להגיע למקרה בסיס, ובמקרה זה לא טוב.
זה יהיה רקורסיה אינסופית והצפת ערימה.
אבל כאן אנחנו רואים שהעדכון שקורה מאז אנחנו מעדכנים להתחיל + סוף / 2,
אנחנו מעדכנים את טיעון הסוף כאן, אנו מעדכנים את הוויכוח מתחיל כאן.
אז בכל השיחות רקורסיבית אנו מעדכנים משהו. אוקיי.
האם אתה רוצה ללכת אלינו באמצעות הפתרון שלך? >> בטח.
אני משתמש SearchHelp כך שכל זמן אני עושה קריאה לפונקציה זו
יש לי התחלה של איפה אני מחפש במערך וסופו של דבר
למקום בו אני מחפש את המערך.
>> בכל השלב שבו הוא אומר שזה האלמנט האמצעי, שהוא התחילה + הסוף / 2,
הוא ששווה למה שאנחנו מחפשים?
ואם כן, אז מצאנו אותה, ואני מניח שזה יעבור את הרמות של רקורסיה.
ואם זה לא נכון, ואז תבדקו אם זה ערך אמצע המערך הוא גדול מדי,
ובמקרה כזה אנו מסתכלים על חיצו השמאלי של המערך על ידי הולך מהתחלה למדד האמצע.
ואחרת אנו עושים סוף המחצית.
[אודן] אוקיי.
זה נשמע טוב.
אוקיי, אז כמה דברים, ובעצם, זה דבר מאוד ברמה גבוהה
כי אתה לעולם לא צריך לדעת לקורס זה, אבל זה נכון.
פונקציות רקורסיבית, אתה תמיד שומעים שהם עסקה גרועה
כי אם אתה קורא לעצמך באופן רקורסיבי פעמים רבות מדי, אתה מקבל הצפת ערימה
מאז, כמו שאמרתי קודם, כל פונקציה מקבלת מסגרתו של המחסנית.
אז כל שיחה של הפונקציה רקורסיבית מקבלת מסגרתו של המחסנית.
אז אם אתה עושה 1000 שיחות רקורסיבית, אתה מקבל 1,000 מסגרות מחסנית,
ומהר אתה להוביל שיש יותר מדי מסגרות מחסנית ודברים פשוט לשבור.
אז בגלל זה פונקציות רקורסיביות הן בדרך כלל רעות.
למרות זאת, קיימת תת קבוצה נחמדה של פונקציות רקורסיביות נקראת פונקציות זנב רקורסיבית,
וזה קורה להיות דוגמה לאחד שבו אם למהדר מבחין זו
ושהוא צריך, אני חושב - בקלאנג, אם תעבור אותו הדגל-O2
אז זה יבחין זה זנב רקורסיבית ולעשות דברים טובים.
>> זה יהיה שימוש חוזר באותה מסגרת מחסנית שוב ושוב עבור כל שיחה רקורסיבית.
וכך מאז שאתה משתמש באותה מסגרת מחסנית, אתה לא צריך לדאוג
אי מחסנית עולה על גדותיו, ובו בזמן, כמו שאמרת קודם,
ברגע שאתה שם החזר אמיתי, אז זה חייב להחזיר את כל המסגרות הללו המחסנית
והשיחה 10 לSearchHelp יש לחזור ל9, יש לחזור ל8.
אז גם זה לא צריך לקרות כאשר פונקציות הן זנב רקורסיבית.
וכן מה שעושה את זנב פונקציה רקורסיבית זה היא הודעה שניתנה לכל קריאה לsearchHelp
השיחה רקורסיבית שהוא עושה מה שהוא חוזר.
אז בקריאה הראשונה לSearchHelp, או שאנחנו בתמורת שווא באופן מיידי,
לחזור מייד אמיתי, או שאנחנו עושים שיחה רקורסיבית לSearchHelp
שבו מה שאנחנו חוזרים הוא מה קריאה שחוזרת.
ואנחנו לא יכולים לעשות את זה אם אנחנו עושים משהו כזה int x = SearchHelp, תשואת x * 2,
רק כמה שינוי אקראי.
>> אז עכשיו שיחה רקורסיבית זה, זה int x = שיחה רקורסיבית SearchHelp,
כבר לא זנב רקורסיבית משום שהוא בעצם אינו צריך לחזור
חזרה למסגרת מחסנית קודמת כך שהשיחה הקודמת לפונקציה
אז יכול לעשות משהו עם ערך ההחזרה.
אז זה לא זנב רקורסיבית, אבל מה שהיינו לנו לפני שהוא יפה זנב רקורסיבית. כן.
[תלמיד] האם אין מקרה הבסיס השני ייבדק 1
כיוון שיכול להיות מצב שבו בעת שתעבור אותו בטענה
יש לך להתחיל = סוף, אבל הם ערך המחט.
השאלה הייתה אנחנו לא יכולים נתקלנו במקרה שבו הסוף הוא ערך המחט
או להתחיל = הסוף, כראוי, תתחיל = הסוף
ואתה לא ממש בדקת כי ערך מסוים עדיין,
אז תתחיל + הסוף / 2 היא רק הולך להיות אותו הערך.
אבל כבר חזרתי כוזב ואנחנו אף פעם לא ממש בדקנו את הערך.
אז לכל הפחות, בקריאה הראשונה, אם גודל הוא 0, אז אנחנו רוצים לחזור שווא.
אבל אם גודל הוא 1, אז ההתחלה היא לא הולכת לסוף שווה,
ואנחנו לפחות לבדוק אלמנט אחד.
אבל אני חושב שאתה צודק בכך שאנו יכולים בסופו של מקרה שבו מתחילים + סוף / 2,
תחילת סופו להיות זהה להתחלה + הסוף / 2,
אבל אנחנו אף פעם לא ממש בדקנו את המרכיב הזה.
>> אז אם אנחנו בודקים ראשונים הוא אלמנט אמצע הערך שאנחנו מחפשים,
אז אנחנו יכולים לחזור אמיתיים באופן מיידי.
אחר אם הן זהות, אז אין טעם להמשיך
מאז אנחנו רק הולכים לעדכן למקרה שבו אנחנו נמצאים במערך בודד רכיב.
אם כי אלמנט היחיד הוא לא זה שאנחנו מחפשים,
אז הכל בסדר. כן.
[תלמיד] העניין הוא שמאז גודל הוא למעשה גדול יותר ממספר האלמנטים במערך,
יש כבר קיזוז - >> כך גם גודל -
[תלמיד] תגיד אם המערך היה בגודל 0, אז SearchHelp יהיה למעשה לבדוק את ערימת שחת של 0
בשיחה הראשונה.
המערך יש גודל 0, אז 0 הם - >> כן.
יש עוד דבר ש-- זה יכול להיות טוב. בואו נחשוב.
אז אם המערך היה 10 אלמנטים והאחד באמצע שאנחנו הולכים לבדוק הוא מדד 5,
כך אנחנו בודקים 5, ונניח שהערך הוא פחות.
אז אנחנו זורקים הכל מ5 ואילך.
אז תתחיל + הסוף / 2 הולך להיות הסוף החדש שלנו,
אז כן, זה תמיד הולך להישאר מעבר לסוף המערך.
אם זה מקרה, אם זה היה אפילו מוזר או, אז היינו בודק, יניח, 4,
אבל אנחנו עדיין זורקים -
אז כן, בסוף הוא תמיד יהיה מעבר לסוף בפועל של המערך.
אז האלמנטים שאנו מתמקדים ב, הסוף הוא תמיד יהיה זה שאחריו.
ולכן אם עושה תחילת הסוף שווה אי פעם, אנחנו נמצאים במערך בגודל 0.
>> הדבר השני שחשבתי הוא שאנחנו מעדכנים מתחילים להיות מתחילים + הסוף / 2,
אז זה מקרה שאני מתקשה עם, שבו מתחיל + הסוף / 2
הוא האלמנט אנחנו בודקים.
בואו נגיד שיש לנו מערך זה 10-אלמנט. לא משנה מה.
אז תתחיל + הסוף / 2 הולך להיות משהו דומה לזה,
ואם זה לא הערך, שאנו רוצים לעדכן.
הערך הוא גדול יותר, ולכן אנחנו רוצים להסתכל על מחצית זו של המערך.
אז איך אנחנו מעדכנים את ההתחלה, אנו מעדכנים את התחילה עכשיו להיות האלמנט הזה.
אבל זה עדיין יכול לעבוד, או לכל הפחות, אתה יכול לעשות את תחילת הסוף + / 2 + 1.
[תלמיד] אתה לא צריך להפעיל את + הסוף [לא ברור] >> כן.
כבר בדקנו את האלמנט הזה ויודעים שזה לא זה שאנחנו מחפשים.
אז אנחנו לא צריכים לעדכן את ההתחלה להיות האלמנט הזה.
אנחנו פשוט יכולים לדלג על זה ולעדכן להתחיל להיות האלמנט הזה.
והאם יש בכלל מקרה, בואו נגיד, שזה היה סוף,
כן אז להתחיל יהיה זה, יתחיל + הסוף / 2 יהיו זה,
+ להתחיל סוף - כן, אני חושב שזה יכול בסופו הלולאה אינסופית.
בואו נגיד שזה רק מערך של 2 או גודל מערך בגודל 1. אני חושב שזה יעבוד.
אז כרגע, ההתחלה היא שרכיב וסופו של דבר הוא 1 מעבר לו.
אז האלמנט שאנחנו הולכים לבדוק את זה הוא אחת,
ואז, כשלעדכן התחלה, אנו מעדכנים את ההתחלה להיות 0 + 1/2,
שהוא הולך לסיים אותנו בחזרה עם התחילה להיות האלמנט הזה.
>> אז אנחנו בודקים אותו היסוד שוב ושוב.
אז זה מקרה שבו כל קריאה רקורסיבית חייבת בעצם לעדכן משהו.
אז אנחנו צריכים לעשות התחלה + הסוף / 2 + 1, אחרת יש עילה לתביעה
לאן אנחנו לא ממש מעדכנים התחלה.
כולם רואים את זה?
אוקיי.
האם יש למישהו שאלות על פתרון זה או כל עוד הערות?
אוקיי. האם יש למישהו פתרון איטרטיבי שכולנו יכול להסתכל?
האם כולנו עושים את זה באופן רקורסיבי?
או גם אני מניח שאם אתה פתחת, אז אתה יכול לדרוס הקודם שלך.
האם זה לשמור באופן אוטומטי? אני לא חיובי.
האם מישהו היה איטרטיבי?
אנחנו יכולים לעבור את זה ביחד אם לא.
הרעיון הולך להיות אותו הדבר.
איטרטיבי פתרון.
אנחנו הולכים לרוצים בעצם לעשות את אותו הרעיון
לאן אנחנו רוצים לעקוב אחר הסיום החדש של המערך וההתחלה החדשה של המערך
ולעשות את זה שוב ושוב.
ואם מה שאנחנו עוקבים אחרי כהתחלה והסוף תמיד מצטלב,
אז אנחנו לא מוצאים אותו ואנחנו יכולים לחזור שווא.
אז איך אני עושה את זה? למישהו יש הצעות או קוד לי למשוך את?
[תלמיד] האם לולאה בזמן. >> כן.
אתה הולך רוצה לעשות לולאה.
>> האם יש לך קוד שאני יכול למשוך למעלה, או מה שאתה הולך להציע?
[תלמיד] אני חושב שכן. >> בסדר. זה עושה את הדברים יותר קלים. מה היה השם שלך?
[תלמיד] לוקאס.
גרסות 1. אוקיי.
נמוך הוא מה שאנחנו מכנים נתחיל לפני.
למעלה זה לא ממש מה שקראנו לפני הסוף.
למעשה, סופו הוא כעת במערך. זה אלמנט שצריך לשקול.
כל כך נמוך הוא 0, הוא עד הגודל של המערך - 1,
ועכשיו אנחנו לופים, ואנחנו בודקים -
אני מניח שאתה יכול לעבור אותו.
מה הייתה החשיבה שלך בכל זה? תראה לנו את הקוד שלך.
[תלמיד] בטח. תראה את ערך ערימת השחת באמצע והשווית אותו למחט.
אז אם זה גדול מהמחט שלך, אז אתה רוצה - אה, בעצם, זה צריך להיות הפוך.
אתה הולך רוצה לזרוק המחצית הימנית, ואז כן, זה צריך להיות בדרך.
[אודן] אז זה צריך להיות פחות? האם זה מה שאמרת? >> [תלמיד] כן.
[אודן] אוקיי. פחות.
אז אם מה שאנחנו מחפשים בהוא קטן יותר ממה שאנחנו רוצים,
אז כן, אנחנו רוצים לזרוק את חיצו השמאלי,
שאומרים שאנחנו מעדכנים את כל מה שאנחנו שוקלים
על ידי ההעברה נמוכה בצד הימין של המערך.
זה נראה טוב.
אני חושב שיש לו את אותה בעיה שאמרנו על קודמו,
שבו אם נמוך הוא 0 ועד הוא 1, אז נמוך + עד / 2 הולכים להגדיר להיות אותו הדבר שוב.
>> וגם אם זה לא המקרה, הוא עדיין יעיל יותר לפחות
רק כדי לזרוק את האלמנט פשוט הסתכלנו בו אנו יודעים הוא שגוי.
כל כך נמוך עד + / 2 + 1 - >> [תלמיד] זה צריך להיות דרך האחרת.
[אודן] או שזה צריך להיות - 1 והשני צריך להיות + 1.
[תלמיד] ולא צריך להיות כפול סימן שוויון. >> [אודן] כן.
[תלמיד] כן.
אוקיי.
וסוף סוף, עכשיו שיש לנו + 1 זה - דבר 1,
זה - זה לא יכול להיות - האם זה בכלל אפשרי לנמוך כדי לגמור עם ערך גדול יותר מאשר עד?
אני חושב שהדרך היחידה שיכול לקרות - האם זה אפשרי? >> [תלמיד] אני לא יודע.
אבל אם זה יגיע חתוך ואז הוא מקבל מינוס ש1 ולאחר מכן - >> כן.
[תלמיד] זה יהיה אולי מסתבך.
אני חושב שזה צריך להיות טוב רק בגלל
כדי שזה בסופו נמוך הם היו צריכים להיות שווים, אני חושב.
אבל אם הם שווים, אז לא היה עושים את הלולאה בזמן כדי להתחיל עם
ואנחנו רק היו מחזירים את הערך. אז אני חושב שאנחנו טובים עכשיו.
שים לב שלמרות שבעיה זו היא כבר לא רקורסיבית,
אותו הסוג של רעיונות חל בו אנו יכולים לראות איך זה כל כך בקלות משאיל את עצמו
לפתרון רקורסיבית על ידי העובדה שאנחנו רק מעדכנים את המדדים שוב ושוב,
אנחנו עושים את הבעיה קטנה יותר ויותר, אנחנו מתמקדים בקבוצת משנה של המערך.
[תלמיד] אם נמוך הוא 0 ועד הוא 1, שניהם יהיו 0 + 1/2, שהייתי הולכים ל0,
ואז אחד תהיה + 1, אחד יהיה - 1.
[תלמיד] איפה אנחנו בודקים שוויון?
כמו שאם האמצעי הוא למעשה מחט?
כרגע אנחנו לא עושים את זה? הו!
אם זהו -
כן. אנחנו לא יכולים פשוט לעשות את הבדיקה לכאן, כי נניח האמצע הראשון -
[תלמיד] הם ממש כמו לא לזרוק מאוגדים.
אז אם אתה זורק כרוך, אתה צריך לבדוק את זה ראשון או משהו כזה.
אה. כן. >> [תלמיד] כן.
אז עכשיו יש לנו לזרוק אותנו כרגע הסתכלנו,
מה שאומר שעכשיו אנחנו צריכים גם שנהיה לי
אם (ערימת שחת [(נמוך + עד) / 2] == מחט), ואז אנחנו יכולים לחזור אמיתיים.
ואם אני שם אחר או סתם אם, זה אומר פשוטו כמשמעו אותו הדבר
בגלל זה היה חוזר נכון.
אז אני אשים אחר אם, אבל זה לא משנה.
>> אז אם זה אחר, זה אחר, וזה דבר שכיח שאני עושה
שבו גם אם זה המקרה שבו הכל טוב כאן,
כמו נמוך לא יכול להיות גדולה מלמעלה, זה לא שווה את החשיבה לגבי שאלה אם זה נכון.
אז אתה יכול גם לומר אילו נמוך הוא פחות או שווה ל
או בזמן נמוך הוא פחות מ
כך שאם הם אי פעם שווים או נמוכים קורה לוותר,
אז אנחנו יכולים לצאת מהלולאה הזו.
שאלות, חששות, הערות?
אוקיי. זה נראה טוב.
עכשיו אנחנו רוצים לעשות את זה.
אם נלך לגרסה השנייה שלי, אנחנו רואים את אותם מספרים אלה,
אבל עכשיו הם כבר לא במטרת מיון.
ואנחנו רוצים ליישם את סוג שימוש בכל אלגוריתם ב O של n log n.
אז איזה אלגוריתם אתה חושב שאנחנו צריכים ליישם כאן? >> [תלמיד] מיון מיזוג.
[אודן] כן. סוג המיזוג הוא O (n log n), כך שזה מה שאנחנו הולכים לעשות.
והבעיה הולכת להיות די דומה,
שבו בקלות משאילה את עצמו לפתרון רקורסיבית.
אנחנו גם יכולים לבוא עם פתרון איטרטיבי אם אנחנו רוצים,
אבל רקורסיה תהיה יותר קלה כאן ואנחנו צריכים לעשות רקורסיה.
אני מניח שהוא יעבור סוג המיזוג ראשון,
למרות שיש וידאו מקסים במיון מיזוג כבר. [שחוק]
אז למזג מיון יש - אני מבזבז כל כך הרבה של מאמר זה.
אה, יש רק כדור אחד.
אז מיזוג.
אה, 1, 3, 5.
אוקיי.
המיזוג לוקח שני מערכים נפרדים.
בנפרד שני המערכים האלה שניהם מסודרים.
אז מערך זה, 1, 3, 5, מיון. מערך זה, 0, 2, 4, ממוין.
עכשיו מה שצריך לעשות הוא מיזוג לשלב אותם לתוך מערך בודד שבעצמו מיון.
אז אנחנו רוצים מערך בגודל 6 שהוא הולך להיות האלמנטים הללו בתוכו
כדי למיין.
>> וכדי שנוכל לנצל את העובדה ששני המערכים האלה מסודרים
לעשות את זה בזמן ליניארי,
משמעות של זמן ליניארי אם מערך זה הוא x גודל וזה y גודל,
אז האלגוריתם הכולל צריך להיות O (x + y). אוקיי.
אז הצעות.
[תלמיד] האם אנו יכולים להתחיל מהשמאל?
אז אתה תשים 0 למטה ראשון ולאחר מכן 1 ולאחר מכן כאן אתה נמצא בבית 2.
אז זה כמו סוג של יש לך כרטיסייה שנעה לצד ימין. >> [אודן] כן.
עבור שני המערכים האלה אם רק להתמקד באלמנט השמאלי ביותר.
מפני ששני המערכים מסודרים, אנחנו יודעים ש2 האלמנטים הללו
הם המרכיבים הקטנים ביותר במערך אחד.
אז זה אומר ש1 מתוך 2 האלמנטים הללו חייב להיות האלמנט הקטן ביותר במערך הממוזג שלנו.
זה פשוט כל כך קורה כי הקטן ביותר הוא האחד מצד ימין הפעם.
לכן אנחנו לוקחים 0, להכניס אותו בצד השמאל, כי 0 הן פחות מ 1,
אז קח 0, להכניס אותו למקומו הראשון שלנו, ואז אנחנו מעדכנים את זה
עכשיו להתמקד בשלישייה הראשונה.
ועכשיו אנחנו חוזרים.
אז עכשיו אנו משווים 2 ו 1. 1 הוא קטן יותר, ולכן נכניס 1.
אנו מעדכנים מצביע זה כדי להצביע על הבחור הזה.
עכשיו אנחנו עושים את זה שוב, ולכן 2. זה יעדכן, להשוות אלה 2, 3.
זה עדכונים, ולאחר מכן 4 ו 5.
אז זה מיזוג.
>> זה צריך להיות די ברור שזה הזמן ליניארי מאז אנחנו פשוט ללכת על פני כל רכיב פעם אחת.
וזה הצעד הגדול ביותר ליישום סוג המיזוג עושה את זה.
וזה לא כל כך קשה.
כמה דברים צריכים להדאיג אותנו הם, בואו נאמר שהיו המיזוג 1, 2, 3, 4, 5, 6.
במקרה זה אנו בסופו של התרחיש שבו זה הולך להיות יותר קטן,
אז לעדכן מצביע זה, זה הולך להיות יותר קטן, עדכון זה,
זה נראה קטן יותר, ועכשיו יש לך להכיר
כשאתה כבר ממש נגמר של אלמנטים להשוות עם.
מכיוון שאנו כבר השתמשנו בכל המערך הזה,
הכל במערך זה עכשיו רק מוכנס כאן.
אז אם אי פעם נתקלו במצב שבו אחד מהמערכים שלנו ממוזג כבר לגמרי,
אז פשוט לקחת את כל האלמנטים של מערך האחר ולהכניס אותם לתוך סוף המערך.
אז אנחנו פשוט יכולים להוסיף 4, 5, 6. אוקיי.
זה דבר אחד שצריך להיזהר.
יישום שצריך להיות שלב 1.
מיזוג למיין אז בהתבסס על זה, זה 2 שלבים, 2 צעדים מטופשים.
בואו רק לתת מערך זה.
אז למזג מיון, שלב 1 הוא באופן רקורסיבי לשבור את המערך לחצי.
אז לפצל מערך זה לחצי.
עכשיו יש לנו 4, 15, 16, 50 ו 8, 23, 42, 108.
ועכשיו אנחנו עושים את זה שוב ונפרדנו אלה לחצי.
אני פשוט אעשה את זה בצד זה.
אז 4, 15 ו 16, 50.
היינו עושה את אותו דבר שוב כאן.
ועכשיו אנחנו לפצל אותו לשני חצאים שוב.
ויש לנו 4, 15, 16, 50.
אז זה מקרה הבסיס שלנו.
ברגע שהמערכים הם בגודל 1, אז אנחנו מפסיקים עם פיצול לחצי.
>> עכשיו מה עושים עם זה?
אנחנו בסופו של זה יהיה גם להתפרק 8, 23, 42, ו 108.
אז עכשיו שאנחנו בשלב זה, עכשיו לשלב 2 מסוג המיזוג היא פשוט מתמזגים זוגות לרשימות.
אז אנחנו רוצים למזג אלה. אנחנו רק קוראים מיזוג.
אנחנו יודעים מיזוג יחזור אלה כדי למיין.
4, 15.
עכשיו אנחנו רוצים למזג אלה, ושיחזירו רשימה עם אלה כדי למיין,
16, 50.
אנו משלבים אלה - אני לא יכול לכתוב - 8, 23 ו 42, 108.
אז יש לנו זוגות ממוזגים פעם אחת.
עכשיו אנחנו רק למזג שוב.
שימו לב שכל אחת מהרשימות אלה מסודרים בעצמו,
ואז אנחנו יכולים רק למזג רשימות אלו כדי לקבל רשימה של גודל 4 אשר מסודרת
ולמזג שתי רשימות אלו כדי לקבל רשימה של גודל 4 שממוינות.
ולבסוף, אנו יכולים למזג שתי רשימות אלה בגודל 4 כדי לקבל רשימה של גודל 8 אחד שהיא מסודר.
אז כדי לראות שזה הוא כללי n log n, אנחנו כבר ראינו שמיזוג הוא ליניארי,
ולכן כאשר יש לנו עסק עם המיזוג אלה, דומים כל כך את העלות הכוללת של מיזוג
לשתי רשימות אלה הם רק 2 כי -
או טוב, זה O של n, אבל n כאן הוא רק 2 האלמנטים הללו, כך שזה 2.
ו 2 אלה יהיו 2 ו 2 אלה יהיו 2 ו 2 אלה יהיו 2,
כך על פני כל המיזוגים שאנחנו צריכים לעשות, אנחנו בסופו של הדבר עושים n.
כמו 2 + 2 + 2 + 2 הם 8, שהוא n,
לכן העלות של מיזוג בקבוצה זו היא n.
ואז אותו הדבר כאן.
אנחנו למזג 2 האלה, אז אלה 2, ובנפרד מיזוג זה ייקח ארבע פעולות,
מיזוג זה ייקח ארבע פעולות, אבל שוב, בין כל אלה,
אנחנו בסופו מתמזגים n דברים כלל, ולכן צעד זה לוקח n.
וכך כל רמה לוקחת אלמנטים n שהתמזגו.
>> וכמה רמות יש?
בכל רמה, המערך שלנו גדל בגודל 2.
הנה המערכים שלנו הם בגודל 1, כאן הם בגודל 2, כאן הם בגודל 4,
ולבסוף, הם בגודל 8.
אז מכיוון שהוא הכפלה, יש הולך להיות כולל של יומן n של רמות אלו.
אז עם היומן n רמות, כל רמת פרט לוקח n פעולות כלל,
אנחנו מקבלים יומן n אלגוריתם n.
שאלות?
יש אנשים שכבר עשו התקדמות על איך ליישם את זה?
האם מישהו כבר במצב שבו אני פשוט לא יכול למשוך את הקוד שלהם?
אני יכול לתת לי דקה.
זה הולך להיות ארוך יותר.
אני מאוד ממליץ ישנתי -
אתה לא צריך לעשות רקורסיה למיזוג
כי לעשות רקורסיה למיזוג, אתה הולך צריך לעבור חבורה של גדלים שונים.
אתה יכול, אבל זה מעצבן.
אבל רקורסיה למיון עצמו היא די קלה.
אתה פשוט קורא ממש סוג של מחצית שמאל, סוג של מחצית ימין. אוקיי.
למישהו יש משהו שאני יכול למשוך את עדיין?
או שאני אתן לי דקה.
אוקיי.
למישהו יש משהו שאנחנו יכולים לעבוד איתו?
או שאנחנו פשוט לעבוד עם זה ולאחר מכן להרחיב משם.
>> למישהו יש יותר מזה שאני יכול להעלות?
[תלמיד] כן. אתה יכול למשוך אותי. >> בסדר.
כן!
[תלמיד] היו הרבה תנאים. >> אה, לירות. האם אתם יכולים -
[תלמיד] אני צריך לשמור אותו. >> כן.
אז עשית את המיזוג בנפרד.
אה, אבל זה לא כל כך רע.
אוקיי.
אז מיון הוא עצם רק להתקשר mergeSortHelp.
תסביר לנו מה עושה mergeSortHelp.
[תלמיד] MergeSortHelp די הרבה האם שני השלבים העיקריים,
אשר הוא למיין כל מחצית של המערך ולאחר מכן למזג את שניהם.
[אודן] אוקיי, אז תן לי שני.
אני חושב שזה - >> [תלמיד] אני צריך -
כן. חסר לי משהו.
במיזוג, אני מבין שאני צריך ליצור מערך חדש
כי אני לא יכול לעשות אותו במקום. >> כן. אתה לא יכול. לתקן.
[תלמיד] אז אני יוצר מערך חדש.
שכחתי בסוף יתמזגו מחדש לשנות.
אוקיי. אנו זקוקים למערך חדש.
במיון מיזוג, זה כמעט תמיד נכון.
חלק מהעלות של אלגוריתם טוב יותר זמן מבחינת
כמעט תמיד הוא את הצורך להשתמש בקצת יותר זיכרון.
אז הנה, לא משנה כמה אתה עושה למזג מיון,
היית בהכרח צריכים להשתמש בכמה זיכרון נוסף.
הוא או היא יצר מערך חדש.
ואז אתה אומר בסוף, אנחנו פשוט צריכים להעתיק מערך חדש למערך המקורי.
[תלמיד] אני חושב שכן, כן.
אני לא יודע אם זה עובד במונחים של ספירה בהתייחסות או מה -
כן, זה יעבוד. >> [תלמיד] אוקיי.
האם אתה מנסה לרוץ בזה? >> [תלמיד] לא, עדיין לא. >> אוקיי.
נסה להריץ אותו, ולאחר מכן אני אדבר על זה לרגע.
[תלמיד] אני אף צריך לקבל את כל אבות הטיפוס לפונקציות והכילו,, נכון?
אבות הטיפוס של הפונקציות. אה, אתה מתכוון כמו - כן.
מיין קורא mergeSortHelp.
>> אז כדי לקרוא לסוג mergeSortHelp, mergeSortHelp עליך הוגדר
לפני המיון או שאנחנו פשוט צריכים אב טיפוס. פשוט להעתיק ולהדביק את זה.
ובאופן דומה, mergeSortHelp קורא מיזוג,
אבל המיזוג לא הוגדר עדיין, ולכן אנחנו יכולים פשוט לתת mergeSortHelp יודע
שזה מה שהוא הולך להתמזג ייראה, וזהו זה.
אז mergeSortHelp.
יש לנו בעיה כאן איפה שאין לנו מקרה בסיס.
MergeSortHelp הוא רקורסיבי, ולכן כל פונקציה רקורסיבית
הולך צריך איזה מקרה בסיס לדעת מתי להפסיק באופן רקורסיבי קורא את עצמו.
מה מקרה הבסיס שלנו הולך להיות כאן? כן.
[תלמיד] אם הגודל הוא 1? >> [אודן] כן.
אז כמו שראינו שם, עצרו מערכי פיצול
ברגע שנכנסנו למערכים בגודל 1, אשר בהכרח ממוינים עצמם.
אז אם גודל שווה 1, אנחנו יודעים שהמערך כבר ממוין
אז אנחנו פשוט יכולים לחזור.
>> שים לב שזה מבוטל, ולכן אנחנו לא נחזור בשום דבר מיוחד, פשוט לחזור.
אוקיי. אז זה מקרה הבסיס שלנו.
אני מניח שמקרה הבסיס שלנו יכול להיות גם אם יקרו לך להיות מיזוג מערך בגודל 0,
אנחנו כנראה רוצים לעצור בנקודה מסוימת,
אז אנחנו יכולים רק להגיד גודל פחות מ 2 או קטן או שווה ל 1
כדי שזה יעבוד עבור כל מערך עכשיו.
אוקיי.
אז זה מקרה הבסיס שלנו.
עכשיו אתה רוצה ללכת אלינו באמצעות מיזוג?
מה כל המקרים האלה מתכוונים?
עד כאן, אנחנו רק עושים אותו הרעיון, -
[תלמיד] אני צריך להיות גודל עובר עם כל שיחות mergeSortHelp.
הוספתי גודל כמו עיקרי נוספת וזה לא שם, כמו גודל / 2.
[אודן] הו, גודל / 2, גודל / 2. >> [תלמיד] כן, וגם בפונקציה הנ"ל גם כן.
[אודן] כאן? >> [תלמיד] רק גודל. >> [אודן] הו. גודל, גודל? >> [תלמיד] כן.
[אודן] אוקיי.
תן לי לחשוב לרגע.
האם אנו נתקלנו בבעיה?
אנחנו תמיד מתייחסים אל השמאל כמו 0. >> [תלמיד] מס
זה לא נכון גם. סליחה. זה צריך להיות התחלה. כן.
[אודן] אוקיי. אני אוהב את זה יותר טוב.
וסופו של דבר. אוקיי.
אז עכשיו אתה רוצה שתראה לנו את המיזוג? >> [תלמיד] אוקיי.
אני רק הולך במערך החדש שיצרתי.
הגודל שלו הוא בגודל של החלק מהמערך שאנחנו רוצים להיות מסודרים
ומנסה למצוא את האלמנט שאני צריך לשים בשלב המערך החדש.
אז כדי לעשות את זה, קודם אני בודק אם את חלקו השמאלי של המערך ממשיך יש לך עוד אלמנטים,
ואם לא, אז אתה יורד למצב שאחר, שפשוט אומר
בסדר, זה חייב להיות במערך הנכון, ואנחנו נשים את זה במדד הנוכחי של newArray.
>> ואז אחרת, אני בודק אם בצד ימין של המערך הוא גם סיים,
במקרה כזה אני פשוט לשים בצד השמאל.
שאולי הוא לא הכרחי. אני לא בטוח.
אבל בכל מקרה, שני סימון האחר שמשתיים קטנים בצד השמאל או הימין.
וגם בכל מקרה, אני הגדלה לפי מציין מיקום אני לעלות.
[אודן] אוקיי.
זה נראה טוב.
האם יש למישהו הערות או חששות או שאלות?
אז בארבעת המקרים שיש לנו להביא את דברים לפשוט להיות - או שזה נראה כמו חמש -
אבל יש לנו לשקול אם מערך השמאל נגמר של דברים שאנחנו צריכים למזג,
אם מערך ימין נגמר של דברים שאנחנו צריכים למזג -
אני מצביע על כלום.
אז אם מערך השמאל נגמר של דברים או מערך ימין נגמר של דברים.
אלה שני מקרים.
אנחנו גם צריכים מקרה טריוויאלי של הדבר אם השמאל הוא פחות מהדבר הנכון.
אז אנחנו רוצים לבחור את דבר השמאל.
אלה התיקים.
אז זה היה נכון, אז זהו זה.
מערך עזב. זה 1, 2, 3. אוקיי. אז כן, אלו הם הארבעה הדברים שייתכן שירצו לעשות.
ואנחנו לא הולכים על פתרון איטרטיבי.
לא הייתי ממליץ -
סוג המיזוג הוא דוגמה לפונקציה שהוא גם לא זנב רקורסיבית,
זה לא קל לעשות את זה זנב רקורסיבית,
אבל גם זה לא כל כך קל לעשות את זה איטרטיבי.
זה קל מאוד.
יישום זה מסוג המיזוג,
מיזוג, לא משנים מה אתה עושה, אתה הולך לבנות מיזוג.
>> אז למזג מיון נבנה על גבי מיזוג רקורסיבי הוא רק שלוש שורות אלה.
ערוך את, זה יותר מעצבן וקשה יותר לחשוב עליו.
אבל שם לב שזה לא זנב רקורסיבית מאז mergeSortHelp - כאשר היא ממכנת את עוצמה -
זה עדיין צריך לעשות את הדברים לאחר שיחה חוזרת רקורסיבית זה.
אז ערימת מסגרת זו חייבת להמשיך להתקיים גם אחרי שקרא את זה.
ואז כשאתה קורא את זה, את מסגרת המחסנית להמשיך להתקיים
כי גם אחרי שהשיחה, אנחנו עדיין צריכים מיזוג.
וזה משימה קל להפוך את הזנב זה רקורסיבית.
שאלות?
בסדר.
אז חוזר למיון - הו, יש שני דברים שאני רוצה להראות. אוקיי.
חוזרים למיון, אנחנו נעשה את זה במהירות.
או חיפוש. מיין? מיון. כן.
אם אחזור לתחילתו של מיון.
אנחנו רוצים ליצור אלגוריתם שממיין את המערך באמצעות כל אלגוריתם
ב O של n.
אז איך זה אפשרי? האם יש למישהו כל סוג של -
שרמזתי קודם ב--
אם אנחנו עומדים לשפר מn log n לO של n,
יש לנו שיפור האלגוריתם שלנו זמן, החכם,
מה שאומר שאנחנו הולכים צריכים לעשות כדי לכפר על זה?
[תלמיד] חלל. >> כן. אנחנו הולכים להיות באמצעות יותר מקום.
ואפילו לא רק יותר מקום, זה מקום אקספוננציאלית יותר.
אז אני חושב שזה סוג של אלגוריתם הוא משהו מדומה, polynom פסאודו -
פסאודו - אני לא זוכר. משהו מדומה.
אבל זה בגלל שאנחנו צריכים להשתמש בכל כך הרבה מקום
שזה הוא בר השגה, אך לא מציאותי.
>> ואיך אנחנו משיגים את זה?
אנחנו יכולים להשיג את זה, אם אנו מבטיחים שכל אלמנט מסוים במערך
הוא מתחת לגודל מסוים.
אז בואו רק נאמר שגודל הוא 200,
כל אלמנט במערך הוא מתחת הגודל 200.
וזה דווקא מאוד מציאותי.
אתה יכול בקלות יש מערך שאתה יודע הכל בזה
הולך להיות נמוך ממספר מסוים.
כמו שאם יש לך קצת וקטור או משהו ענקי ממש
אבל אתה יודע מה הולך להיות בין 0 ל 5,
אז זה הולך להיות משמעותי יותר מהר לעשות את זה.
והכרוך בכל אחד מהמרכיבים הם 5,
אז זה כרוך, כלומר כמה זיכרון אתה הולך להיות משתמש.
אז הכבול הוא 200.
בתאוריה יש תמיד כרוך מאז מספר שלם יכול להיות עד ל -4 מיליארדים בלבד,
אבל זה לא מציאותי שכן אז הייתי שימוש בשטח
על הסדר של 4 מיליארדים. אז זה לא מציאותי.
אבל הנה אנחנו נגיד כרוכים הוא 200.
הטריק כדי לעשות את זה ב O של n הוא שאנחנו עושים מערך אחר שנקרא סעיפים של גודל מחויבים.
כך שלמעשה, זה קיצור ל-- אני באמת לא יודע אם קלאנג עושה זאת.
אבל בGCC לכל הפחות - קלאנג בהנחה אני עושה את זה יותר מדי -
זה יהיה פשוט לאתחל את כל המערך להיות 0s.
אז אם אני לא רוצה לעשות את זה, אז אני יכול לעשות בנפרד עבור (אני int = 0;
i <Bound; i + +) וספירה [i] = 0;
אז עכשיו הכל מאותחל ל 0.
אני לחזר על המערך שלי,
ומה שאני עושה הוא שאני סופר את כל - בוא ארד כאן.
יש לנו 4, 15, 16, 50, 8, 23, 42, 108.
מה אני סומך הוא מספר מופעים של כל אחד מהאלמנטים האלה.
בואו בעצם להוסיף עוד כמה לכאן עם כמה חזרות.
אז יש לנו כאן הערך, הערך שהוא הולך להיות מערך [i].
אז val יכול להיות 4 או 8 או לא משנה מה.
ועכשיו אני סופר כמה שערך שאני ראיתי,
כך ספירה [val] + +;
אחרי שזה נעשה, ספירה עומדת להיראות משהו כמו 0001.
בואו נעשה ספירה [val] - מחויב + 1.
>> עכשיו זה רק כדי להסביר את העובדה שאנחנו מתחילים מ 0.
אז אם 200 הולכים להיות המספר הגדול ביותר שלנו,
אז 0-200 הם 201 דברים.
אז ספירה, זה ייראה כמו 00001 כי יש לנו אחד 4.
אז יהיה לנו 0001 בו תהיה לנו 1 במדד ה -8 של ספירה.
תהיה לנו 2 במדד ה -23 של ספירה.
תהיה לנו 2 במדד 42 של ספירה.
אז אנחנו יכולים להשתמש בספירה.
אז num_of_item = ספירה [i].
ולכן אם num_of_item הוא 2, זה אומר שאנחנו רוצים להכניס 2 לספרה
למערך המיון שלנו.
אז אנחנו צריכים לעקוב אחר כמה רחוקים אנחנו לתוך המערך.
אז = מדד 0.
מערך - אני פשוט אכתוב אותו.
ספירות -
מערך [ראשים + +] = i;
האם זה מה שאני רוצה? אני חושב שזה מה שאני רוצה.
כן, זה נראה טוב. אוקיי.
אז לכולם להבין מה המטרה של מערך הספירות שלי היא?
הוא סופר את מספר מופעים של כל אחד מהמספרים האלה.
אז אני iterating על מערך ספירות ש,
ועמדת ה-i במערך הספירות
הוא מספר שזה שאמור להופיע במערך המיון שלי.
זו הסיבה שהסעיפים של 4 הולכים להיות 1
והספירה של 8 הולכת להיות 1, סעיפים של 23 הולכים להיות 2.
אז ככה רבים מהם אני רוצה להכניס לתוך המערך הממוין שלי.
אז אני פשוט עושה את זה.
אני מכניס num_of_item אני זה למערך המיון שלי.
>> שאלות?
וכך שוב, זה זמן ליניארי מאז אנחנו רק iterating על זה פעם אחת,
אבל זה גם מה יניארי במספר זה קורה להיות,
ואז זה תלוי במידה רבה על מה שהכרוך הוא.
עם כפות של 200, זה לא כל כך נורא.
אם הכבול שלך הולך להיות 10000, אז זה קצת יותר גרוע,
אבל אם הכריכה שלך הולכת להיות 4 מליארד דולרים, זה לגמרי לא מציאותי
ומערך זה הולך להיות בגודל 4 מליארד דולרים, שאינו מציאותי.
אז זהו זה. שאלות?
[תגובת תלמיד לא נשמעה] >> אוקיי.
הבנתי דבר אחד כאשר היינו עובר.
אני חושב שהבעיה הייתה בלוקאס וכנראה כל אחד ואחד שראינו.
שכחתי לגמרי.
הדבר היחיד שאני רוצה להגיב על זה שכאשר אתה מתעסק עם דברים כמו מדדים,
אתה לא באמת רואה את זה כשאתה כותב ללולאה,
אבל מבחינה טכנית, בכל פעם שאתה מתעסק עם מדדים אלה,
אתה צריך פחות או יותר תמיד להתמודד עם מספרים שלמים שאינם חתומים.
הסיבה לכך היא כאשר אתה מתעסק עם מספרים שלמים שנחתמו,
כך שאם יש לך 2 מספרים שלמים שנחתמו ואתה מוסיף אותם יחד
והם בסופו גדול מדי, אז אתה בסופו של דבר עם מספר שלילי.
אז זה מה שהצפה היא מספר שלמה.
>> אם אני מוסיף 2 מיליארדים 1 מליארד, שאתקע עם 1000000000 שליליים.
ככה מספרים שלמים לעבוד במחשבים.
אז הבעיה בשימוש -
זה בסדר אלא אם נמוך קורה להיות 2 מיליארדים ועד קורה להיות 1 מיליארדים,
אז זה הולך להיות שלילי 1 מיליארדים ואז אנחנו הולכים לחלק את זה על ידי 2
וסופו של דבר עם 500,000,000 שליליים.
אז זה רק בעיה אם קורים לך להיות מחפש דרך מערך
של מליארד דברים.
אבל אם + נמוך עד שקורה להצפה, אז זה בעיה.
ברגע שאנחנו עושים אותם לא חתומים, אז 2000000000 פלוס 1 מליארד ש"ח הנם 3 מליארד דולרים.
3000000000 חלקים 2 הם 1.5 מליארד דולרים.
אז ברגע שהם לא חתומים, הכל מושלם.
ואז זה גם בעיה כשאתה כותב ללולאות,
ובעצם, זה כנראה עושה את זה באופן אוטומטי.
זה באמת פשוט לצעוק עליך.
אז אם מספר זה הוא גדול מדי כדי להיות בפשוט שלם אבל זה יתאים בשלם חתום,
הוא צעק עליך, כך שזו הסיבה שאף פעם לא באמת נתקלה בבעיה.
ניתן לראות שמדד לא הולך להיות שלילי,
ואז כשאתם iterating על מערך,
אתה כמעט תמיד יכול להגיד int חתום אני, אבל אתה לא באמת צריך.
דברים הולכים לעבוד די הרבה באותה מידה.
אוקיי. [לוחש] מה השעה?
הדבר האחרון שרציתי להראות - ואני פשוט אעשה את זה ממש מהר.
אתה יודע כמה יש לנו ולכן אנחנו מגדירים # # יכולים להגדיר כמקס 5 או משהו?
בואו לא נעשה את המקסימום. # Define הכפות 200. זה מה שעשינו בעבר.
שמגדיר מתמיד, שרק הולך להעתיק ולהדביק
כל מקום שאנחנו קורים לכתוב מאוגדים.
>> אז אנחנו באמת יכולים לעשות יותר עם # מגדיר.
אנו יכולים להגדיר פונקציות #.
הם לא באמת פונקציות, אבל אנחנו קוראים להם פונקציות.
דוגמה תהיה משהו כמו מקס (x, y) מוגדר (x <y y:? X). אוקיי.
אז אתה צריך להתרגל לתחביר מפעיל משולש,
אך הוא פחות מ x y? תשואת y, אחר לחזור x.
אז אתה יכול לראות שאתה יכול לעשות זה פונקציה נפרדת,
והפונקציה יכולה להיות כמו bool מקס לוקח 2 טענות, להחזיר את זה.
זה אחד מאלה הנפוצים ביותר שאני רואה שנעשו כזה. אנו קוראים להם פקודות מאקרו.
זה מאקרו.
זה רק תחביר לזה.
אתה יכול לכתוב מאקרו לעשות מה שאתה רוצה.
לעתים קרובות אתה רואה פקודות מאקרו לאיתור באגים printfs וכאלה.
אז סוג של printf, יש קבועים מיוחדים בC כמו מדגישים את הקו תחתון,
2 מדגישים קו תחתון,
ויש גם אני חושב 2 מדגיש FUNC. זה יכול להיות אותו. משהו כזה.
אלה דברים יוחלפו עם השם של הפונקציה
או מספר הקו שאתה נמצא.
לעתים קרובות, אתה כותב printfs איתור הבאגים שכאן אני יכול אז פשוט לכתוב
DEBUG וזה יהיה להדפיס את מספר הקו והפונקציה שאני במקרה ב
שהיא נתקלה באמירת DEBUG.
ואתה יכול גם להדפיס דברים אחרים.
אז דבר אחד אתה צריך להיזהר הוא אם אני במקרה # להגדיר DOUBLE_MAX
משהו כמו 2 * 2 * y וx.
אז מה סיבה, קורה לך לעשות את זה הרבה.
אז לעשות את זה במאקרו.
זה בעצם שבור.
אני הייתי קורא לזה על ידי עושה משהו כמו DOUBLE_MAX (3, 6).
אז מה יש להחזיר?
[תלמיד] 12.
כן, יש להחזיר 12, ו 12 הוא חזר.
3 מתחלפים עבור x, 6 מתחלפים עבור y, ואנחנו חוזרים 2 * 6, שהוא 12.
עכשיו מה לגבי זה? מה יש להחזיר?
[תלמיד] 14. >> באופן אידיאלי, 14.
הבעיה היא שכמה חשיש מגדיר עבודה, זכור שזה העתק ודבק מילולי
של כל דבר די הרבה, אז מה זה הולך להתפרש כ
הוא 3 פחות מ 1 ועוד 6, 2 1 פעמים בתוספת 6, 2 3 פעמים.
>> הנה, זו סיבה שכמעט תמיד לעטוף הכל בסוגריים.
כל משתנה שכמעט תמיד לעטוף בסוגריים.
יש מקרים שבו אתה לא צריך, כמו שאני יודע שאני לא צריך לעשות את זה כאן
כי פחות מזה די הרבה זמן רק הולך לעבודה,
למרות שאפילו לא יכול להיות אמיתי.
אם יש משהו מגוחך כמו DOUBLE_MAX (1 == 2),
אז זה הולך לקבל החליף עם 3 פחות מ 1 שווה שווה 2,
וכן אז זה הולך לעשות 3 פחות מ 1, האם זה שווה 2,
וזה לא מה שאנחנו רוצים.
אז כדי למנוע בעיות קדימות מפעיל,
תמיד לעטוף בסוגריים.
אוקיי. וזהו, 5:30.
אם יש לך שאלות כלשהן על pset, יידע אותנו.
זה צריך להיות כיף, ומהדורת ההאקר גם היא הרבה יותר מציאותי
ממהדורת ההאקר של השנה שעברה, אז אנחנו מקווים שהרבה מכם לנסות את זה.
בשנה שעברה הייתה מאוד מכרעת.
>> [CS50.TV]