1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [שבוע 3, המשך]

2
00:00:02,280 --> 00:00:04,110
>> [דוד י מלאן - אוניברסיטת הרווארד]

3
00:00:04,110 --> 00:00:07,130
>> [זה CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> בסדר. ברוך שובך. זה CS50 וזה סוף השבוע 3.

5
00:00:11,010 --> 00:00:14,680
>> אז לאלה שנה לא מוכר, שעבר אוניברסיטה הרווארד השיקה מה שנקרא מעבדת החדשנות,

6
00:00:14,680 --> 00:00:18,530
או i-מעבדה, שהוא בניין נפלא מעבר לנהר בקמפוס של הרוורד

7
00:00:18,530 --> 00:00:22,640
כי הוא פתוח לסטודנטים, סטודנטי GSAS, סטודנטים מכל רחבי הקמפוס,

8
00:00:22,640 --> 00:00:27,000
כולל סגל, וזה מקום לבוא יחד כדי לעבוד על דברים חדשניים,

9
00:00:27,000 --> 00:00:29,180
דברים במיוחד יזמיים

10
00:00:29,180 --> 00:00:33,410
אם אתה וחברים 0 או יותר חושבים לעשות משהו יזמי

11
00:00:33,410 --> 00:00:37,080
גם במהלך השיעור הזה, אחרי זה בכיתה, או מעבר לו.

12
00:00:37,080 --> 00:00:41,540
>> אז אחד הדברים שהם עושים מעל טווח J הוא הטיולים הללו,

13
00:00:41,540 --> 00:00:44,510
אחד מהם הוא לניו יורק, שאחד מהם הוא לעמק הסיליקון.

14
00:00:44,510 --> 00:00:47,530
החלל הוא מאוד מוגבל, אבל זה הזדמנות להתחכך עם תואר במנהל עסקים

15
00:00:47,530 --> 00:00:52,200
וסטודנטים לתארים מתקדמים ברחבי קמפוס ולמעשה מבלים זמן באזורים האלה בהתאמה

16
00:00:52,200 --> 00:00:55,500
מפטפט על סטארט, יפטפט יזמים וכדומה.

17
00:00:55,500 --> 00:00:57,870
אז אם מתעניייין, לבדוק את כתובת האתר כאן.

18
00:00:57,870 --> 00:01:01,220
זה זמין גם בשקופיות באינטרנט.

19
00:01:01,220 --> 00:01:04,610
>> אנחנו יכולים למתן את אודי הבית רק קצת?

20
00:01:04,610 --> 00:01:08,640
אם ברצונך להצטרף אלינו לארוחת צהריים ביום שישי, השעה 1:15 באש וקרח, אנא בראש שם.

21
00:01:08,640 --> 00:01:11,390
אני מתנצל אם הטופס כבר מלא עד שאתה מגיע לשם.

22
00:01:11,390 --> 00:01:13,750
אבל אנחנו נמשיך הלאה את המסורת הזאת.

23
00:01:13,750 --> 00:01:17,350
>> היום אנחנו ממשיכים את הדיון ברמה הגבוהה יותר של בעיות שונות שאנו יכולים לפתור,

24
00:01:17,350 --> 00:01:21,330
התמקדות הרבה פחות, היום לפחות, על קוד והרבה יותר על רעיונות.

25
00:01:21,330 --> 00:01:24,720
אז תחשוב שוב לשבוע 0 כאשר קרעו ספר טלפונים במחצית,

26
00:01:24,720 --> 00:01:28,260
שמטרתה הייתה לעשות משהו, יש להודות, קצת דרמטית

27
00:01:28,260 --> 00:01:32,360
אבל כדי לשלוח את הנקודה שחיפוש אינו צריך להיות, בהכרח,

28
00:01:32,360 --> 00:01:35,100
כמובן מאליו במבט ראשון כמו שחושב.

29
00:01:35,100 --> 00:01:40,200
ופתרון הבעיות באופן כללי לא בהכרח תמיד להיות הטוב ביותר -

30
00:01:40,200 --> 00:01:44,130
הפתרון המתבקש ביותר לא בהכרח יהיה הטוב ביותר.

31
00:01:44,130 --> 00:01:47,300
אז היה לנו ספר טלפונים וזה, למען האמת, כולנו בחדר הזה היה אינסטינקטים,

32
00:01:47,300 --> 00:01:51,470
ככל הנראה, להתחיל באמצע כאשר מחפשים מייק סמית ואז ללכת ימינה או שמאלה

33
00:01:51,470 --> 00:01:54,280
בהתבסס על מה שהאות של אלף היינו במקרה בסופו של דבר.

34
00:01:54,280 --> 00:01:57,560
>> אבל את הרעיון פשוט שאנו בני האדם נלקח כמובן מאליו כל כך הרבה זמן

35
00:01:57,560 --> 00:02:00,670
באמת צריך להתחיל לבוא אל החזית של המוח שלך

36
00:02:00,670 --> 00:02:03,900
כי כמו הבעיות לקבל הרבה יותר מורכב ממה שספר טלפונים,

37
00:02:03,900 --> 00:02:07,420
אותן תובנה פשוטות האלה, מבריקות הן מה הולכים כדי לאפשר לנו

38
00:02:07,420 --> 00:02:10,259
כדי לפתור את הבעיות הרבה יותר מסובכות והרבה יותר מעניינות,

39
00:02:10,259 --> 00:02:12,930
ביניהם כמה מהדברים שאנחנו לוקחים כמובן מאליו כבר בימים אלה.

40
00:02:12,930 --> 00:02:15,720
מיליארדי דפי אינטרנט שם בחוץ, ובכל זאת גוגל ובינג וכמו

41
00:02:15,720 --> 00:02:17,660
תוכלו למצוא דברים בשבילנו ככה.

42
00:02:17,660 --> 00:02:22,300
זה לא קורה באמצעות חיפוש ליניארי, וחפש בכל דפי האינטרנט האפשריים.

43
00:02:22,300 --> 00:02:25,290
פייסבוק הוא מסוגל לומר לך שכל החברים שלך או חברים של חברים,

44
00:02:25,290 --> 00:02:28,250
וגם את זה ניתן לעשות לכאורה במיידי בימים אלה

45
00:02:28,250 --> 00:02:30,820
למרות שיש להם מיליוני משתמשים.

46
00:02:30,820 --> 00:02:34,250
>> ואז איך אנחנו באמת לפתור את הבעיות שבסופו של דבר להפחית את ההיקף

47
00:02:34,250 --> 00:02:37,830
לרעיונות הסתכלנו בשבוע 0 וקצת יותר היום.

48
00:02:37,830 --> 00:02:42,320
אנחנו לא מחדש לבצע אלגוריתם זה, אבל אנחנו גם זוכרים שעשינו בשבוע 0 התרגיל הזה

49
00:02:42,320 --> 00:02:44,780
המקום שבו כולם לקום, לקחת על המספר 1,

50
00:02:44,780 --> 00:02:48,720
ואז היה לנו כל ספירה עצמית על ידי זוגות זוגות, והוסיף את המספרים שלך יחד,

51
00:02:48,720 --> 00:02:51,930
מחצית מהחבורה התיישבה על כל איטרציה.

52
00:02:51,930 --> 00:02:56,750
אז הלכתי מ500 תלמידים ל250-125 וכן הלאה.

53
00:02:56,750 --> 00:03:00,080
אבל כפי שאמרנו ביום שני, רעיון רב העצמה יש

54
00:03:00,080 --> 00:03:02,460
היה שאם הכפיל את גודל הבעיה

55
00:03:02,460 --> 00:03:06,480
וכל הילדים ממשפטים או EC 10 חזרו לחדר והצטרפו אלינו,

56
00:03:06,480 --> 00:03:09,510
טוב, אפשר שתחשיבו את הקבוצה כולה המצרפי

57
00:03:09,510 --> 00:03:13,380
רק עם חזרה גדולה 1 יותר מהלולאה כי הם היו רק אולי, כפולים בגודל

58
00:03:13,380 --> 00:03:15,630
או במקרה של Ec 10 קצת יותר מכפול בגודל.

59
00:03:15,630 --> 00:03:18,440
ואז הייתי צריך להשקיע קצת יותר זמן,

60
00:03:18,440 --> 00:03:22,000
אבל אנחנו לא צריכים להשקיע 400 או 700 שלבים נוספים.

61
00:03:22,000 --> 00:03:26,550
>> רק כדי לצייר את התמונה הזאת באופן שקצת פחות מופשט, בואו לא כולם לעמוד על הרגליים.

62
00:03:26,550 --> 00:03:31,100
אבל אם אלו מכם שבחרו לשבת בתזמורת היום לא היו אכפת בעמידה,

63
00:03:31,100 --> 00:03:34,580
בואו נראה אם ​​אנחנו יכולים להבין שביניכם שאדם הגבוה ביותר הוא

64
00:03:34,580 --> 00:03:36,730
על ידי עושה את אותו הסוג של אלגוריתם השוואתי.

65
00:03:36,730 --> 00:03:41,830
אז אם אתה יושב בתזמורת, את התנצלותי, אבל השלב 1, לעמוד;

66
00:03:41,830 --> 00:03:44,650
שלב 2, בזוגות עם מישהו בסביבה,

67
00:03:44,650 --> 00:03:49,360
להבין מי הוא גבוה יותר, ולשבת אם אתה קצר יותר.

68
00:03:49,360 --> 00:03:51,360
ואז לחזור.

69
00:03:51,360 --> 00:03:56,280
[סטודנטי ממלמל]

70
00:04:13,450 --> 00:04:15,320
>> אוקיי.

71
00:04:15,320 --> 00:04:19,010
אוקיי. אחד נשאר עומד. מה שמך? >> אנדרו.

72
00:04:19,010 --> 00:04:21,959
>> אנדרו, אתה האדם הגבוה ביותר בסעיף התזמורת היום.

73
00:04:21,959 --> 00:04:28,100
>> מזל טוב. [מחיאות כפות ומריעות] אוקיי. יש מושב. אז מצאתי את אנדרו.

74
00:04:28,100 --> 00:04:30,870
אבל כמה זמן היה לוקח לי, למשל, למצוא אנדרו

75
00:04:30,870 --> 00:04:33,740
בסעיף זה של תזמורת 50 + או כך אנשים?

76
00:04:33,740 --> 00:04:36,900
אני יכול לקחת את גישה פשוטה למדי ולהתחיל כאן.

77
00:04:36,900 --> 00:04:39,270
ויש לי 2 אנשים לקום ואני רק משווה ביניהם,

78
00:04:39,270 --> 00:04:42,120
ואז אני אומר לכל מי שקצת יותר קצר: "בסדר, אתה מתיישב,"

79
00:04:42,120 --> 00:04:44,380
ואני הולך לזכור מי היה האדם הגבוה יותר.

80
00:04:44,380 --> 00:04:49,030
ואז אני חוזר, חוזר, חוזר, ואני תולה באדם הגבוה ביותר

81
00:04:49,030 --> 00:04:51,920
עד שאני מוצא מישהו קצת יותר גבוה מהם, ובשלב

82
00:04:51,920 --> 00:04:54,950
האדם מעט הקצר לאחר מכן יש לשבת.

83
00:04:54,950 --> 00:04:57,690
אבל שבאלגוריתם בסעיף תזמורת זו, אם יש n שלך,

84
00:04:57,690 --> 00:05:00,480
כמה צעדים הוא אלגוריתם שהולך לקחת? >> [תלמיד] נ

85
00:05:00,480 --> 00:05:03,580
>> זה הולך לקחת n, נכון, כי במקרה הגרוע ביותר, אם אפשר לומר כך,

86
00:05:03,580 --> 00:05:09,090
האדם הגבוה ביותר הוא האדם האחרון שאני מקבל רק על ידי מזל רע אקראי.

87
00:05:09,090 --> 00:05:14,260
אז במקרה הגרוע ביותר, זמן הריצה של אלגוריתם שהוא ליניארי, זה n,

88
00:05:14,260 --> 00:05:18,070
כאשר n הוא המספר הכולל של אנשים בשטח, בגודל של הבעיה.

89
00:05:18,070 --> 00:05:19,600
מה לגבי אלגוריתם זה?

90
00:05:19,600 --> 00:05:22,080
העובדה שכולכם קמו ואז שוב חצי מהתיישבה,

91
00:05:22,080 --> 00:05:23,950
המחצית מכם התיישבה, חצי מכם ישבו.

92
00:05:23,950 --> 00:05:26,070
כמה צעדים צריכים שלקח אם יש n שלך כאן?

93
00:05:26,070 --> 00:05:30,200
[תלמיד] N log n. >> זה יהיה יותר גרוע. היכנס n.

94
00:05:30,200 --> 00:05:32,930
>> אז להתחבר n, גם אם אתה לא ממש זוכר מה לוגריתם הוא,

95
00:05:32,930 --> 00:05:38,410
לעת עתה, רק מעריך שזה קשור איכשהו לזה וhalving halving וhalving.

96
00:05:38,410 --> 00:05:41,000
זה לא חייב להיות פקטור של 2. זה יכול להיות פקטור של 3.

97
00:05:41,000 --> 00:05:46,560
אבל זה זו חזרה על אותו הסוג של גורם כזה שגודל הבעיה מתחיל כאן

98
00:05:46,560 --> 00:05:49,620
אבל אז מייד עובר לכאן, אז הנה, אז כאן, אז הנה.

99
00:05:49,620 --> 00:05:53,580
אתה לא לוקח נגיסות קטנות של הבעיה, אתה באמת קצצת אותו

100
00:05:53,580 --> 00:05:56,160
עם גדול בבת בכל פעם.

101
00:05:56,160 --> 00:06:00,810
אז היו לנו 50 אנשים, אז 25, אז 12 וחצי או 13 אנשים בעמידה,

102
00:06:00,810 --> 00:06:05,370
לאחר מכן 6 ½ וכך הלאה עד שעמד לבסוף רק אנדרו שנשאר.

103
00:06:05,370 --> 00:06:08,710
אז אנחנו הולכים לקרוא ליומן של n, ואתה יכול לדמיין את זה באופן בא.

104
00:06:08,710 --> 00:06:12,570
זוכר את התמונה הזאת כאן שבו אלגוריתם ליניארי הוא כמו הקו האדום שם,

105
00:06:12,570 --> 00:06:17,520
הקו הצהוב היה הספירה על ידי אלגוריתם 2s ששמש לנו לחשבון סטודנטים

106
00:06:17,520 --> 00:06:22,300
בעבר, אבל היום הגביע הקדוש הולך להישאר הקו הירוק הזה

107
00:06:22,300 --> 00:06:25,470
היכן אם הכפלנו את מספר אנשים שבסעיף התזמורת או רק אמר,

108
00:06:25,470 --> 00:06:29,170
לעזאזל, בואו כולם בחדר כולו עומד, לא כזה ביג דיל

109
00:06:29,170 --> 00:06:31,560
כי אנחנו בערך להכפיל כמה אנשים נמצאים כאן למטה,

110
00:06:31,560 --> 00:06:33,500
1 יותר איטרציה, לא בעיה.

111
00:06:33,500 --> 00:06:36,200
>> מצאנו אנדרו או מי קורה להיות גבוה יותר מאנדרו

112
00:06:36,200 --> 00:06:38,770
בקומת ביניים או במרפסת.

113
00:06:38,770 --> 00:06:42,140
אז הרעיון הפשוט הזה שלקחנו כל כך הרבה מאליו בספר טלפונים,

114
00:06:42,140 --> 00:06:46,170
הבין שיש כל כך הרבה מקומות שונים שבן תוכל ליישם אותו.

115
00:06:46,170 --> 00:06:50,810
רק כדי להרביץ מעט ז'רגון - למעשה, ולא בז'רגון ראשון,

116
00:06:50,810 --> 00:06:52,750
תן לי ללכת לתמונה הזאת כאן.

117
00:06:52,750 --> 00:06:56,970
כרגע אנחנו מדברים על n ו n / 2 ולאחר מכן היכנסו של n,

118
00:06:56,970 --> 00:07:00,500
אבל אנחנו בהחלט יכולים לבוא עם, כפי שיהיו במהלך הסמסטר,

119
00:07:00,500 --> 00:07:05,130
סוג שני של נוסחות מתמטיות כדי לתאר את הרעיון הכללי הזה של זמן ריצה.

120
00:07:05,130 --> 00:07:07,580
אלה הם מחוץ לההקשר לעת עתה, מפני שאנחנו רואים לפני זמן רב

121
00:07:07,580 --> 00:07:09,900
אלגוריתמים שמדוברים בעצם מייצג.

122
00:07:09,900 --> 00:07:17,990
>> שלא להבחין כאן בקו ליניארי n, הקו הישר, הוא למעשה נמוך מאוד והצביע עכשיו.

123
00:07:17,990 --> 00:07:22,950
זה סוג של אשליה אופטית שבאנחנו פשוט לשנות את מה שציר x מייצג

124
00:07:22,950 --> 00:07:26,130
וציר Y, ​​ואנחנו יכולים לעשות את נקודת קו ישר בכל כיוון שאנחנו רוצים.

125
00:07:26,130 --> 00:07:30,350
אבל הסיבה שזה כל כך לכאורה שטוח עכשיו

126
00:07:30,350 --> 00:07:35,690
בגלל שהיינו צריך כדי לפנות מקום על הגרף הזה לזמני ריצה הרבה יותר איטיים.

127
00:07:35,690 --> 00:07:39,030
לעת עתה, יודע שיש כמה אלגוריתמים די רעים בחיים,

128
00:07:39,030 --> 00:07:43,790
שחלקם לא ינקטו צעדי n, או טוב יותר, להתחבר צעדי n אבל יותר.

129
00:07:43,790 --> 00:07:48,820
אז מעל קו n כאן בהודעת תחתיתו יש n פי יומן של n,

130
00:07:48,820 --> 00:07:51,410
ונראה מה זה אומר לפני זמן רב.

131
00:07:51,410 --> 00:07:56,010
מעל זה הוא n בריבוע, ואנחנו לא ראינו שום אלגוריתמים בריבוע n עדיין אבל אנחנו עומדים.

132
00:07:56,010 --> 00:07:57,660
וזה נראה ממש רע.

133
00:07:57,660 --> 00:08:01,610
יש 2 עד n, משהו מעריכים, שמרגיש אפילו יותר גרוע.

134
00:08:01,610 --> 00:08:05,760
ובכל זאת, בסקרנות, אז יש n קוביות, שאם אתה סוג של חשיבה קדימה,

135
00:08:05,760 --> 00:08:10,000
אם אתה סוג של לעשות את המתמטיקה, 2 עד n בעצם הופך להיות הרבה יותר ישר,

136
00:08:10,000 --> 00:08:15,930
הרבה יותר למעלה מ n קוביות אם אתה מסתכל על הצירים די רחוק.

137
00:08:15,930 --> 00:08:19,890
אז שם לב עכשיו הצירים הללו אינם שרירותיים 2-10 על ציר x.

138
00:08:19,890 --> 00:08:21,770
>> ומה זה אומר?

139
00:08:21,770 --> 00:08:23,890
כלומר, 2 אנשים, 10 אנשים בחדר.

140
00:08:23,890 --> 00:08:27,200
זה כל אמצעי x: גודל הבעיה, מה הוא ההקשר.

141
00:08:27,200 --> 00:08:30,420
וציר אנכי עכשיו הוא מספר השניות או מספר השלבים -

142
00:08:30,420 --> 00:08:31,840
כמה יחידת הזמן.

143
00:08:31,840 --> 00:08:34,740
אבל שם לב שזה 0-60 ו0 עד 10.

144
00:08:34,740 --> 00:08:38,549
אבל אם אנחנו סוג של זום החוצה, כמו שאתה יכול ב-Excel או בתוכנה ליצירת תרשימים,

145
00:08:38,549 --> 00:08:43,370
ואנחנו הולכים עד 200.000, נבחין שמשהו כמו 2 עד n

146
00:08:43,370 --> 00:08:47,520
הולך להציף את זמני ההצגה של n בריבוע לחלוטין,

147
00:08:47,520 --> 00:08:50,960
n חתוך לקוביות, n log n - כל מה שדברנו עליו עד כה.

148
00:08:50,960 --> 00:08:54,190
ובכל זאת לתפוס את זה כשאתה מתחיל לדבר על דברים כמו פייסבוק

149
00:08:54,190 --> 00:08:57,150
שם יש לך המון אנשים, רבים בכל קשורים,

150
00:08:57,150 --> 00:09:00,650
יש לך n אנשים, כל אחד מהם עשוי להיות רבים כמו חברי n

151
00:09:00,650 --> 00:09:02,860
אם כולם הוא סוג של הסחבק בעולם,

152
00:09:02,860 --> 00:09:08,100
טוב, זה כבר n n פעמים, כך שחברויות של N אפשריות בריבוע,

153
00:09:08,100 --> 00:09:10,950
לפחות בכיוון 1, n חברויות אפשריות בריבוע.

154
00:09:10,950 --> 00:09:15,330
אז זה כבר מצביע על כך שמחפש הגרף החברתי של פייסבוק, אם אפשר לומר כך,

155
00:09:15,330 --> 00:09:18,090
יכול להתחיל לבוא לידי ביטוי בסוגים אלה של נוסחות.

156
00:09:18,090 --> 00:09:19,820
>> אנחנו נחזור ולהפוך את זה הרבה יותר קונקרטי,

157
00:09:19,820 --> 00:09:23,280
אך לעת עתה, במטרה לשבועות הקרובים הרבים

158
00:09:23,280 --> 00:09:27,170
הולך להיות בטוח שלא ללכת על אלגוריתמים או קוד יישום

159
00:09:27,170 --> 00:09:29,870
שסופו של דבר לוקח את כל זמן שמשהו כזה.

160
00:09:29,870 --> 00:09:33,110
אבל הדבר המרתק במדעי מחשב אם אתה ממשיך בתחום זה

161
00:09:33,110 --> 00:09:38,320
לוקח שיעורים כמו CS121, CS124, אשר שניהם קורסי תאוריה,

162
00:09:38,320 --> 00:09:41,300
הוא שלמעשה יש כמה בעיות שקיימות בעולם הזה

163
00:09:41,300 --> 00:09:45,710
שיסודו, עד כמה שאנחנו יודעים, שלא ניתן לפתור מהר יותר

164
00:09:45,710 --> 00:09:48,880
מהגרוע מהגרפים האלה בעצם מציע.

165
00:09:48,880 --> 00:09:53,660
אז יש הרבה בעיות פתוחות בעולם הזה כדי לעשות הרבה יותר טוב מאשר לבני אדם יש עד כה.

166
00:09:53,660 --> 00:09:56,130
>> אז בואו נתחיל אז עם דוגמה זו.

167
00:09:56,130 --> 00:09:59,650
ראינו מאבק שון עם מצלמה על זה, יותר מדי מגושם בוידאו.

168
00:09:59,650 --> 00:10:05,270
אבל המציאות הייתה כאשר שון הוטל למצוא על לוח כמו זה המספר 7,

169
00:10:05,270 --> 00:10:10,300
זוכר שאמרתי את זה, "יש אי שם מאחורי פיסות נייר הללו או דלתות לבנות

170
00:10:10,300 --> 00:10:12,570
"המספר 7. שון, תמצא את זה בשבילנו."

171
00:10:12,570 --> 00:10:14,200
וזה היה נפלא מביך לצפות

172
00:10:14,200 --> 00:10:15,790
כי הוא ממש נאבק עם בעיה זו.

173
00:10:15,790 --> 00:10:19,720
אבל המציאות הייתה שון כמו גם עשה מישהו בחדר היה יכול לעשות.

174
00:10:19,720 --> 00:10:21,890
הוא קצת יותר מאדם טיפוסי לקח אולי,

175
00:10:21,890 --> 00:10:24,760
אבל הוא הניח שיש איזה טריק לבעיה זו,

176
00:10:24,760 --> 00:10:26,590
הוא הניח שהוא היה חסר משהו.

177
00:10:26,590 --> 00:10:29,320
וזה לא עזר כי מאת עיניים היו מסתערים עליו.

178
00:10:29,320 --> 00:10:34,250
>> אבל המציאות הייתה אם הקלט לבעיה הוא חבורה של מספרים אקראיים

179
00:10:34,250 --> 00:10:37,120
ואתה מתבקש למצוא מספר כזה 1,

180
00:10:37,120 --> 00:10:39,770
הכי הטוב שאתה יכול לעשות הוא חיפוש ליניארי.

181
00:10:39,770 --> 00:10:44,060
התחל בצד השמאל, עבר לימין, או להתחיל בצד ימין, תעבור לשמאל.

182
00:10:44,060 --> 00:10:48,300
בדיעבד, אנו עשויים לחשוב, "שון, למה לא פשוט להתחיל מהקצה השני?"

183
00:10:48,300 --> 00:10:52,120
ובכן, 7 היו יכול להיות באותה קלות כאן באופן אקראי,

184
00:10:52,120 --> 00:10:54,980
אבל אני בכוונה שמתי את זה שם, כי חשבתי שהוא לא מתכוון להתחיל בסוף.

185
00:10:54,980 --> 00:10:59,320
אז אני סוג של מניפולציה את המצב, אבל במקרה אקראי 7 יכול להיות בכל מקום.

186
00:10:59,320 --> 00:11:02,380
אז החל מהקצה הימני היה יכול להיות יותר טוב,

187
00:11:02,380 --> 00:11:04,320
אבל מה אם בשנה הבאה אני עובר 7 מקומות אחרים?

188
00:11:04,320 --> 00:11:06,830
זה לא פתרון יסודי לבעיה חדשה -

189
00:11:06,830 --> 00:11:10,520
החל מסוף 1 או האחר - כאשר אתה נתון אין הנחות אחרות.

190
00:11:10,520 --> 00:11:13,620
אז שון התחיל לחפש דרך המספרים והוא אמר, "5. זה לא כאן".

191
00:11:13,620 --> 00:11:17,280
ואז הוא הלך לשם וראה 19, אז הוא עצר לכ 20 שניות,

192
00:11:17,280 --> 00:11:22,330
אז הוא פתח את זה בשביל 13, ולאחר מכן התברר

193
00:11:22,330 --> 00:11:24,270
שלא נראה שיהיה כאן דפוס.

194
00:11:24,270 --> 00:11:28,090
זה לא היה 1, 2, 3, 4 או כמו. היו פערים במספרים, מה שלא עזר.

195
00:11:28,090 --> 00:11:32,320
וגם העובדה שנהגתי פיסות נייר הללו זולים כדי לכסות את המספרים

196
00:11:32,320 --> 00:11:35,270
הוא למעשה מכוון, כי אם אני הסרתי את כל פיסות נייר הללו,

197
00:11:35,270 --> 00:11:38,760
רובנו, שון כלל, כנראה שהייתי סוג של ציץ macroscopically

198
00:11:38,760 --> 00:11:43,410
בלוח ואמר, "הו, 7 הן ללא ספק נכון לשם". אנחנו עשינו את זה באופן מיידי.

199
00:11:43,410 --> 00:11:46,460
>> וזה יכול להיות הדרך בה המוח האנושי עובד במידה מסוימת,

200
00:11:46,460 --> 00:11:50,730
אבל במציאות, העיניים או המחשבה שלו הייתה כנראה ברפרוף את המספרים מימין לשמאל,

201
00:11:50,730 --> 00:11:55,190
משמאל לימין, אמצע והלאה - משהו קורה מבחינה פיזיולוגית

202
00:11:55,190 --> 00:11:57,640
כך שהרגיש כאילו זה היה קורה באופן מיידי,

203
00:11:57,640 --> 00:12:01,360
אבל רוב הסיכויים שגם באופן פנימי היה איזה סוג של שיטה למציאת 7.

204
00:12:01,360 --> 00:12:05,160
ואכן, עכשיו שאנחנו מדברים על מערכים ומבני נתונים

205
00:12:05,160 --> 00:12:08,780
ובתוך זיכרון של מחשב, הדבר היחיד שאנו בני האדם יכול לעשות

206
00:12:08,780 --> 00:12:13,070
די להסתכל במיקומי זיכרון בודדים 1 בכל פעם.

207
00:12:13,070 --> 00:12:16,600
>> אז בכל מקום אחר יכול גם להיות מכוסה פיסת נייר

208
00:12:16,600 --> 00:12:21,170
כי אנחנו לא יכולים לראות את זה בכל מקרה. אנחנו יכולים לעשות דבר 1 בלבד בכל פעם.

209
00:12:21,170 --> 00:12:25,030
אז במקרה הזה, במקרה של שון, הלכו לכאן ואז הלכו כאן

210
00:12:25,030 --> 00:12:31,040
ואז הלכנו לכאן, כאן, כאן, כאן, יש חכם עד הסוף

211
00:12:31,040 --> 00:12:34,450
ורק סוג של דילוג זה באופן שרירותי ומצא 7 שם.

212
00:12:34,450 --> 00:12:37,470
האישה הזאת לא הייתה מיוחדת במיוחד. זה גם לא היה בתוקף.

213
00:12:37,470 --> 00:12:39,530
אבל הוא סוף הסוף מצא 7.

214
00:12:39,530 --> 00:12:45,360
אבל עכשיו ממסעדה באמת היא שהכי הטוב שאתה יכול לעשות אם תינתן שום מידע

215
00:12:45,360 --> 00:12:50,400
מלבד מספרים ממוינים באופן אקראי הוא להתחיל משמאל או להתחיל מימין.

216
00:12:50,400 --> 00:12:54,950
או לעזאזל, אתה יכול לפתוח את דלתות באופן אקראי, אבל גם אז מה זה אומר להיות אקראי?

217
00:12:54,950 --> 00:12:57,220
ובכן, הייתי צריך איכשהו למסד מה זה אומר להתחיל כאן,

218
00:12:57,220 --> 00:13:01,150
אז ללכת לכאן, ואז ללכת לכאן. שון היית נהדר, וזה היה פשוט כיף לראות.

219
00:13:01,150 --> 00:13:06,340
מה אם במקום נשנינו את הבעיה קצת ולהביא את שון לשנה זו, אם תרצה?

220
00:13:06,340 --> 00:13:09,460
האם יהיה מי שיהיה נוח לבוא לבמה ופתרון בעיה מעט שונה

221
00:13:09,460 --> 00:13:12,330
ומופיע במצלמה?

222
00:13:12,330 --> 00:13:15,720
>> בואו נלך מעבר לתזמורת כי אתם היינו מעורבים למדי היום כבר.

223
00:13:15,720 --> 00:13:21,430
מה דעתך על בורוד, בכובע? בואו למטה. מה שמך? >> אלכס. >> אלכס. אוקיי.

224
00:13:21,430 --> 00:13:24,580
אז אלכס יהיה שון של השנה ויופיע בשנים הקרובות

225
00:13:24,580 --> 00:13:27,770
שווי של CS50 הרצאות.

226
00:13:27,770 --> 00:13:30,340
אלכס, נחמד לפגוש אותך. >> נע להכיר אותך יותר מדי.

227
00:13:30,340 --> 00:13:33,470
האתגר בהישג יד עבורך הוא שאתה צריך זה קצת יותר קל

228
00:13:33,470 --> 00:13:38,950
בזה שאני אומר לך את אותם מספרים כאן, אבל עכשיו הם מסודרים.

229
00:13:38,950 --> 00:13:41,800
אז עכשיו המטרה שלך היא למצוא את המספר 7.

230
00:13:41,800 --> 00:13:45,370
ולמעשה, אנחנו באמת צריכות לעשות את זה - אתה בא מסוג המרמה, מחשב לא הייתי עולה,

231
00:13:45,370 --> 00:13:47,990
על ידי התבוננות במה שהמספרים היו לפני רגע.

232
00:13:47,990 --> 00:13:50,360
בגיר זה ממש לא הולך לעזור לכל כך הרבה,

233
00:13:50,360 --> 00:13:52,810
אבל בואו נעמיד פנים שאתה לא יודע מה הוא המערך המקורי.

234
00:13:52,810 --> 00:13:56,600
כל מה שאתה יודע כרגע הוא שיש לך מערך של מספרים ממוינים

235
00:13:56,600 --> 00:14:00,360
שאולי יש פערים ביניהם, והמטרה שלך היא למצוא את המספר 7.

236
00:14:00,360 --> 00:14:05,080
איך היית, אדם סביר, ללכת על מציאת המספר 7?

237
00:14:05,080 --> 00:14:07,770
>> עבור מנמוך לגבוה? >> אוקיי. ללכת נמוך לגבוה.

238
00:14:07,770 --> 00:14:10,990
ולא לתלוש אותם. בואו רק להרים אותם כדי שנוכל לעשות שימוש חוזרים בם.

239
00:14:10,990 --> 00:14:14,730
אוקיי, אז 1. חכה. לפני שאתם ממשיכים הלאה, זה היה 1, שגוי בבירור.

240
00:14:14,730 --> 00:14:17,270
אז מה עובר לך עכשיו? מה הצעד הבא שלך?

241
00:14:17,270 --> 00:14:23,250
הבא. >> אוקיי. הבא. טוב. 3, כל כך שגויים. מה הצעד הבא שלך?

242
00:14:23,250 --> 00:14:27,670
תמשיך. >> בסדר. תמשיך. 5.

243
00:14:27,670 --> 00:14:31,110
אז להמשיך הלאה, ותן לי למסור לך את זה לדורות הבאים.

244
00:14:31,110 --> 00:14:35,720
7. >> מצוין. טוב מאוד. מצא את המספר 7. [מחיאות כפות]

245
00:14:35,720 --> 00:14:39,720
אז זה היה טוב, אבל שון מצא המספר 7 מדי.

246
00:14:39,720 --> 00:14:44,490
ואני טוען שלא באמת נצלתי פיסה הנוספת של מידע,

247
00:14:44,490 --> 00:14:47,780
אשר הוא שמספרים אלה מסודרים.

248
00:14:47,780 --> 00:14:51,520
אז אנחנו יכולים לעשות טובים יותר? כל הצעה כאן? כן, מאחור.

249
00:14:51,520 --> 00:14:54,710
[תלמיד] חיפוש בינארי. >> אין לי מושג מה הוא החיפוש בינארי.

250
00:14:54,710 --> 00:14:58,030
>> [תלמיד] התחל באמצע. התחל >> באמצע. אוקיי. אז בואו נראה אם ​​אנחנו יכולים להגיע לשם.

251
00:14:58,030 --> 00:15:02,580
אז אם במקום שאומר לך להתחיל מהאמצע, קדימה, לפתוח את הדלת באמצע.

252
00:15:02,580 --> 00:15:04,580
יש 8 מהם, כך שתצטרך לבחור באופן שרירותי 1

253
00:15:04,580 --> 00:15:09,800
מעט שמאלה או ימינה. אוקיי. 7! [מחיאות כפות] נחמדות מאוד.

254
00:15:09,800 --> 00:15:11,410
בסדר, אבל איפה היינו הולכים עם זה?

255
00:15:11,410 --> 00:15:14,990
בואו נניח שרק כדי לשבור את העניבה, היית מתחיל כאן

256
00:15:14,990 --> 00:15:16,670
כי באותה מידה יכולה היה לקרות גם כן.

257
00:15:16,670 --> 00:15:19,540
אנחנו רק במקרה ידענו ש7 היו שם. אז זה 13.

258
00:15:19,540 --> 00:15:21,980
אז אם הם מסודרים ואנחנו רק התחלנו באמצע,

259
00:15:21,980 --> 00:15:24,600
מה יהיה הצעד הבא של האופטימלי היית?

260
00:15:24,600 --> 00:15:27,740
עבור שמאל. ואז הנה מגיע דוגמה שוב בספר טלפונים.

261
00:15:27,740 --> 00:15:30,130
אם 13 הוא כאן ואנחנו יודעים הרשימה ממוינת,

262
00:15:30,130 --> 00:15:33,900
אז כל פיסות נייר הללו הם שלא מעניינים אותנו עכשיו

263
00:15:33,900 --> 00:15:37,400
כי אנחנו כבר יודעים ש7 חייבים להיות בצד השמאל

264
00:15:37,400 --> 00:15:39,510
אם מספרים אלה מסודרים ומצאנו 13.

265
00:15:39,510 --> 00:15:42,500
>> אז מה הצעד הבא שלך כאן? עבור >> לשמאל. >> אוקיי, טוב.

266
00:15:42,500 --> 00:15:45,080
אז ללכת לשמאל, ו-- לחכות, היי, היי, היי. שמרמה.

267
00:15:47,140 --> 00:15:51,350
אז מצאת את 7, אבל מה היה האלגוריתם פשוט מיושמים?

268
00:15:51,350 --> 00:15:56,450
התחל באמצע. >> טוב. אז מה ההמשך ההגיוני של אותו רעיון?

269
00:15:56,450 --> 00:15:58,970
אה, רק לאלה. >> בדיוק. >> אז אני מתחיל כאן. >> טוב.

270
00:15:58,970 --> 00:16:02,020
אז עכשיו הלכנו מעט שמאלה שוב. זה 3.

271
00:16:02,020 --> 00:16:05,310
אבל ממסעדה המעניינת כרגע היא איזה מהם אתם לא צריכים לדאוג?

272
00:16:05,310 --> 00:16:08,040
2 אלה. אלה >> 2. אז עכשיו זה יכול ללכת, זה יכול ללכת משם.

273
00:16:08,040 --> 00:16:12,330
עכשיו הבעיה שהייתה 8 ולאחר מכן הייתה 4 גודל כרגע הם בגודל 2.

274
00:16:12,330 --> 00:16:16,430
אנחנו מקבלים די קרובים. שוב, ללכת לאמצע של 2 האלמנטים הללו.

275
00:16:16,430 --> 00:16:20,430
>> אוקיי. אז זה סוג של מזל שעכשיו אנחנו הולכים תמיד נשארנו בגלל שאנחנו עיגול כלפי מטה.

276
00:16:20,430 --> 00:16:25,150
אבל זה בסדר, כי עכשיו אנחנו להשליך את כל זה וכל דבר אחר, והשאירו אותנו רק עם 7.

277
00:16:25,150 --> 00:16:30,490
בואו ניתן למחיאות כפות סוערות. מצאנו 7 שוב. [מחיאות כפות] אוקיי. בטח.

278
00:16:30,490 --> 00:16:32,220
חכה רק 1 יותר 2.

279
00:16:32,220 --> 00:16:36,630
למרות שהסוג הבא של התהליך ארך קצת יותר ממה שאנחנו מרגישים שזה יהיה,

280
00:16:36,630 --> 00:16:40,150
בכנות, האינסטינקטים הראשונים שלך היו הכי הטוב, נכון? מצאנו 7 באופן מיידי.

281
00:16:40,150 --> 00:16:46,740
אבל היינו מוצא 7 מהר יותר, לא משנה מה, בדוגמה זו לעומת זו 1

282
00:16:46,740 --> 00:16:50,100
כי אם המספרים מסודרים כל, כמו הדפים בספר טלפונים,

283
00:16:50,100 --> 00:16:54,580
אתה אכן יכול לקצוץ חצי מהבעיה שוב ושוב ושוב.

284
00:16:54,580 --> 00:16:56,740
וזה לא ממש קל כמו לראות את זה רק עם 8 ספרות

285
00:16:56,740 --> 00:17:00,100
בניגוד לספר טלפונים של 1,000 דף שבו אתה באמת רואה את זה מבחינה ויזואלית,

286
00:17:00,100 --> 00:17:03,120
אבל במקרה הזה כאן כאשר שון חפש 7,

287
00:17:03,120 --> 00:17:06,020
כמה שלבים במקרה הגרוע ביותר היה נדרש לו? >> [תלמיד] 7.

288
00:17:06,020 --> 00:17:11,670
7 במקרה הגרוע ביותר. ובכן, במקרה הגרוע ביותר לא 7 אם יש 8 דלתות כאן.

289
00:17:11,670 --> 00:17:13,440
זה היה לוקח לו 8 צעדים.

290
00:17:13,440 --> 00:17:18,170
>> אז אם יש דלתות n, זה אולי לקח את שון לפני כמה שנתי צעדי n.

291
00:17:18,170 --> 00:17:21,520
עכשיו, במקרה שלך, אלכס, בהתחשב בכך שהמספרים אלה מסודרים -

292
00:17:21,520 --> 00:17:25,130
ואנחנו יכולים להסיק מסוג זה מאיפה שהייתם עד כה בסיפור הזה -

293
00:17:25,130 --> 00:17:28,300
מה זמן הריצה של האלגוריתם החכם יותר של אלכס

294
00:17:28,300 --> 00:17:30,770
להתחיל מהאמצע ולאחר מכן חזרה?

295
00:17:30,770 --> 00:17:36,490
[תלמיד] 3. >> אז זה הולך להיות 3, פחות או יותר, אם אתה רוצה ללכת 8-4 2 עד 1.

296
00:17:36,490 --> 00:17:40,660
אז או 3 שלבים, באופן כללי יותר, זה יומן n שוב.

297
00:17:40,660 --> 00:17:43,380
בכל פעם שאתה halving וhalving וhalving וhalving,

298
00:17:43,380 --> 00:17:45,290
זה ביטוי לרעיון הזה של היומן n.

299
00:17:45,290 --> 00:17:48,140
וכך זה היה לוקח לך רק 3 שלבים, והיא אכן עשתה

300
00:17:48,140 --> 00:17:50,890
ברגע שפתחנו את הדלתות וhalving halving,

301
00:17:50,890 --> 00:17:53,770
אילו זה היה לוקח כמה שון 7 או 8 צעדים.

302
00:17:53,770 --> 00:17:56,330
אז תודה שהיית איתנו השנה. >> תודה לך. היה נעים להכיר אותך.

303
00:17:56,330 --> 00:18:00,170
תודה לאלכס. >> גם לי. [מחיאות כפות]

304
00:18:00,170 --> 00:18:02,150
>> אז מה המשמעות האמיתית של זה?

305
00:18:02,150 --> 00:18:06,050
עכשיו דמיינו שזה לא 8 דלתות, שלמען אמת, כולנו יכולתי למצוא משהו

306
00:18:06,050 --> 00:18:10,430
מאחורי 8 דלתות די מהר על ידי פשוט קורע את פיסות נייר והולך עם האינסטינקטים שלנו.

307
00:18:10,430 --> 00:18:14,430
אבל מה אם זה מ'דלתות? ומה אם זה 4000000000 דלתות?

308
00:18:14,430 --> 00:18:19,630
במקרה של 4 מיליארדים דלתות, אתה באמת תרצה ללכת עם האלגוריתם של אלכס,

309
00:18:19,630 --> 00:18:23,150
חיפוש בינארי כנתחיל לקרוא אותו או להפריד ולמשול, באופן כללי יותר,

310
00:18:23,150 --> 00:18:25,220
בו אתה שומר halving וhalving הבעיה,

311
00:18:25,220 --> 00:18:30,510
כי אם יש לך 4000000000 דלתות, כמה פעמים אפשר לקצוץ 4 מליארד חצי?

312
00:18:30,510 --> 00:18:33,870
[תלמיד] 32. >> זה בעצם 32. אתה יכול לפתור את זה על פיסת נייר או בראש שלך.

313
00:18:33,870 --> 00:18:38,490
אתה הולך 4000000000-2000000000 to 1 מיליארדים חצי מיליארדים, 250 מ', נקודה, נקודה, נקודה.

314
00:18:38,490 --> 00:18:41,620
ואם אתה עושה את החשבון, אתה הולך אכן כדי לקבל 32,

315
00:18:41,620 --> 00:18:44,950
ושלמעשה מתייחס למדעי מחשב, כי אנחנו בדרך כלל לספור בחזקים של 2.

316
00:18:44,950 --> 00:18:47,600
2 עד 32 קורים להיות 4 מיליארדים שקל.

317
00:18:47,600 --> 00:18:51,440
אז יש הרבה רלוונטי לסוגים אלה של חזקים של 2 במדעי מחשב.

318
00:18:51,440 --> 00:18:55,120
>> אבל מה כ 8 מיליארדים? כמה צעדים שהוא הולך לקחת אם יש 8000000000 דלתות?

319
00:18:55,120 --> 00:19:00,350
[תלמיד] 33. אז >> 33. מה אם יש 16000000000 דלתות? כמה צעדים שהוא הולך לקחת?

320
00:19:00,350 --> 00:19:05,020
[תלמיד] 34. >> 34. סוג שלנו יכול להמשיך עד לזרא זה. אבל זה דבר חזק.

321
00:19:05,020 --> 00:19:09,430
אתה יכול להציג מיליארדים תשומות נוספות לבעיה שלך, אבל, לא ביג דיל,

322
00:19:09,430 --> 00:19:14,140
אתה פשוט לוקח ביס נוסף 1 מתוכה ובכך נותן לנו משהו כמו חיפוש בינארי

323
00:19:14,140 --> 00:19:15,920
או להפריד ולמשול, באופן כללי יותר.

324
00:19:15,920 --> 00:19:17,990
אבל אני סוג של רמאות כאן, נכון?

325
00:19:17,990 --> 00:19:22,410
במקרה של האלגוריתם של אלכס, היה לה יתרון על שון.

326
00:19:22,410 --> 00:19:27,780
היא ידעה שמספרים אלו מוינו, אבל אלכס לא היה צריך למיין אותם בעצמה.

327
00:19:27,780 --> 00:19:30,520
אני מראש באתי ללוח והסוג של וידא

328
00:19:30,520 --> 00:19:33,670
שציירתי את כולם כדי מיון, אז כיסיתי אותם בנייר.

329
00:19:33,670 --> 00:19:35,850
אבל כמה עבודה שלא ייקח אותי?

330
00:19:35,850 --> 00:19:40,110
אם היה לנו התחלנו עם המספרים הללו בקצת סדר אקראי לכאורה -

331
00:19:40,110 --> 00:19:43,320
במקרה זה המספרים האלה פשוטים, 1 עד 8 לכאן -

332
00:19:43,320 --> 00:19:46,090
איך אנחנו הולכים על מיון ערכים אלה?

333
00:19:46,090 --> 00:19:52,530
אם היית אדם ניתן משימה זו, איזה סוג של גישה אינטואיטיבית היית לוקח

334
00:19:52,530 --> 00:19:54,800
למיון ולכל מיני מספרים?

335
00:19:54,800 --> 00:19:57,050
הדברים האלה היו מניחים אותם כחלקי פאזל. כן.

336
00:19:57,050 --> 00:19:59,950
>> [תלמיד] הייתי לוקח את כל מספר והשוויתי אותו לכל אחד

337
00:19:59,950 --> 00:20:03,180
ולהמשיך ללכת לצד השמאל. >> אוקיי, טוב.

338
00:20:03,180 --> 00:20:05,720
אז קח את כל מספר, השווה אותו לזה שלידו,

339
00:20:05,720 --> 00:20:09,610
ואז פשוט להמשיך לנוע לאורך הרשימה, סוג של rejiggering דברים כמו שאתה הולך.

340
00:20:09,610 --> 00:20:13,800
אז הנה יש לנו סיכוי לאולי עוד כמה אנשים שיהיו מעורב.

341
00:20:13,800 --> 00:20:16,290
האם יש לנו 8 מתנדבים נוספים שהיו רוצה לבוא?

342
00:20:16,290 --> 00:20:23,950
לחץ קצת פחות כיוון שאתה לא יחיד. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
בואו למטה. אתם הולכים להיות במספרי 1 עד 8.

344
00:20:28,190 --> 00:20:36,050
בואו נראה אם ​​אנחנו לא יכולים לעשות את המיון הזה לאלכס הרבה באותו אופן שעשיתי אותו מראש.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
קדימה, אם אפשר, בשורה על במה בין עמדת מוסיקה ואותי לכאן

347
00:20:40,760 --> 00:20:44,960
באותו סדר הגודל כמו שקופית על המסך.

348
00:20:47,910 --> 00:20:49,680
אוי לא.

349
00:20:50,370 --> 00:20:53,230
אנחנו נעבוד לך לדוגמא הבאה. הו, חכה, חכה. הנה אנחנו מתחילים. חכה.

350
00:20:53,230 --> 00:20:57,570
הדוגמא הבאה היא עכשיו. הנה לך. מספר 8. בואו נעלה.

351
00:20:57,570 --> 00:21:00,270
בסדר. מיין עצמכם על פי זה.

352
00:21:00,270 --> 00:21:03,620
הסט קצת לצד של המוזיקה עומד כאן.

353
00:21:03,620 --> 00:21:12,310
אז יש לנו 4, 2, 6 - להגיע לשם, לכאן, ממש שם - 3.

354
00:21:12,310 --> 00:21:17,570
כן. אוקיי. אתה הולך לכאן. לא, לך להישאר שם.

355
00:21:17,570 --> 00:21:21,840
כן, ממש שם. מספר שאני טועה. בדיוק שם. אוקיי, טוב מאוד. אוקיי.

356
00:21:21,840 --> 00:21:24,930
אז עכשיו בואו למיין אותם במטרה להגדיל.

357
00:21:24,930 --> 00:21:26,210
>> איך אני יכול ללכת על עושה את זה?

358
00:21:26,210 --> 00:21:28,630
האלגוריתם שהוצע לפני רגע היה למה אנחנו לא פשוט להשוות

359
00:21:28,630 --> 00:21:31,970
את האנשים שהם סוג של אחד ליד שני ולאחר מכן לתקן את כל טעויות,

360
00:21:31,970 --> 00:21:33,540
עובר משמאל לימין.

361
00:21:33,540 --> 00:21:36,580
אז הנה יש לנו 4 ו 2, ברור שלא לפי סדר. בואו נחליף אותך. אוקיי.

362
00:21:36,580 --> 00:21:40,760
אז עכשיו אני הולך לעבור את הקו. 4 ו 6, זה לא. [שחוק]

363
00:21:40,760 --> 00:21:45,010
6 ו 8, די טוב. 8 ו 1, בואו נחליף אותך חבר 'ה אותי. בסדר.

364
00:21:45,010 --> 00:21:48,030
אז 8 ו 3, להחליף אתכם.

365
00:21:48,030 --> 00:21:52,280
8 ו 7, בואו נחליף אותך חבר 'ה אותי. 5 ו 8, מצוינים.

366
00:21:52,280 --> 00:21:54,820
אני אתן לך רשימה ממוינת.

367
00:21:54,820 --> 00:21:56,860
בסדר. אז לא ממש.

368
00:21:56,860 --> 00:22:01,180
אבל זה יותר טוב כי במספרים הגדולים יותר - במקרה בנקודה 8 -

369
00:22:01,180 --> 00:22:04,030
סוג של שבעבע מהשמאל לימין.

370
00:22:04,030 --> 00:22:08,010
אז יש לי 1 מהם צודקים, אבל זה מרגיש כאילו זה לא ממש יפתור את הבעיה.

371
00:22:08,010 --> 00:22:11,150
>> אז מה אתה היית מציע שנעשיתם עכשיו? >> [תלמיד] תמשיך לעשות את זה. >> אנו ממשיכים לעשות את זה.

372
00:22:11,150 --> 00:22:13,740
ולהבין, שוב, אנחנו מכינים את הדברים רק על ידי שכל בני האדם

373
00:22:13,740 --> 00:22:17,180
סוג של תבונה לארגן את עצמם המבוססים על תמונה,

374
00:22:17,180 --> 00:22:19,040
אבל עכשיו אנחנו צריכים להיות הרבה יותר שיטתיים.

375
00:22:19,040 --> 00:22:21,510
אנחנו צריכים להיות אלגוריתמיים על זה כאילו אנחנו כותבים קוד -

376
00:22:21,510 --> 00:22:23,520
במקרה זה pseudocode המילולי.

377
00:22:23,520 --> 00:22:26,040
אז תן לי לנסות את זה שוב. זה עבד די טוב. זה לא פתר את זה.

378
00:22:26,040 --> 00:22:30,400
אבל כאשר הוא בספק, פשוט לנסות ולנסות שוב. אז 2 ו 4, לא עזרו יותר.

379
00:22:30,400 --> 00:22:33,200
4 ו 6. אה! 6 ו 1, קצת יותר טוב עכשיו.

380
00:22:33,200 --> 00:22:39,740
6 ו 3, טובים. 6 ו 7, 7 ו 5, 7 ו 8, טוב.

381
00:22:39,740 --> 00:22:44,060
ואתם יודעים, אני יכול כנראה להתעלם 8 עכשיו בגלל שהוא בסוף הרשימה.

382
00:22:44,060 --> 00:22:47,250
אולי אנחנו לא צריכים לדאוג למישהו שמגיע לו בעבר.

383
00:22:47,250 --> 00:22:49,240
אבל בואו נראים אם זה הנחה בטוחה.

384
00:22:49,240 --> 00:22:52,340
עכשיו רשימה היא - ארור - אינה ממוין. בואו ננסה את זה שוב.

385
00:22:52,340 --> 00:22:56,440
אז 2 ו 4, 4 ו 1, 4 ו 3.

386
00:22:56,440 --> 00:22:59,230
4 ו 6, טוב. 6 ו 5, טוב.

387
00:22:59,230 --> 00:23:04,890
6, 7 ו 8, טוב. אבל שים לב, אני יכול רק לעצור כאן ועכשיו לעצור כאן עכשיו?

388
00:23:04,890 --> 00:23:07,770
[תלמיד] כן. >> כן?

389
00:23:07,770 --> 00:23:11,160
מה אם אחד מכם היה המספר 9 כל הדרך לשם?

390
00:23:11,160 --> 00:23:13,640
זה היה מסודר. >> טוב. זה היה מסודר בסיבוב הראשון.

391
00:23:13,640 --> 00:23:16,050
טוב. אז בואו נחזור שוב. אנחנו כמעט שם.

392
00:23:16,050 --> 00:23:22,800
1 ו 2, 2, 3, 3 ו 4, 4, 5, 5 ו 6, 6 ו 7, 7 ו 8.

393
00:23:22,800 --> 00:23:26,640
>> אני עושה עכשיו, אבל, שוב, אני מחשב שיכול לעשות רק מה שאומר לי לעשות,

394
00:23:26,640 --> 00:23:30,120
והזיכרון היחיד שלי כרגע הוא שאני למעשה רק עשיתי קצת עבודה.

395
00:23:30,120 --> 00:23:31,700
משהו השתנה כאן.

396
00:23:31,700 --> 00:23:37,100
אז אני לא אשרתי טכני חזותי או אלגוריתמי כי רשימה זו היא מסודרת מאוד.

397
00:23:37,100 --> 00:23:40,720
אז רק למען סדר טוב, רק כדי להיות אנאלי על זה, בואו נעשיתי 1 יותר הפעם.

398
00:23:40,720 --> 00:23:44,040
אז 1 ו 2, 2, 3, 3 ו 4. ואתם יודעים מה?

399
00:23:44,040 --> 00:23:46,190
רק למען סדר טוב, אני הולך לעקוב על היד שלי הפעם

400
00:23:46,190 --> 00:23:51,110
כמה החלפות אני עושה רק כדי שאדע כמה עבודה למעשה שעשיתי.

401
00:23:51,110 --> 00:23:56,930
3 ו 4, 4, 5, 5 ו 6, 6 ו 7, 7 ו 8. אין החלפות.

402
00:23:56,930 --> 00:24:00,800
אז עכשיו הייתי לגיטימי להיות אידיוט כדי לעשות את זה שוב

403
00:24:00,800 --> 00:24:03,330
כי אם אני לא עבדתי בשום דרך לעבור את זה של בני האדם,

404
00:24:03,330 --> 00:24:06,710
אז ברור שזה הולך לקרות שוב אם אף אחד מהם הוא סוג של אקראי

405
00:24:06,710 --> 00:24:10,410
adversarially נע סביב עצמם. אז עכשיו אני יכול להפסיק.

406
00:24:10,410 --> 00:24:15,120
עכשיו בואו לשאול את השאלה, כמה עבודה שזה בעצם לקחת אותי?

407
00:24:15,120 --> 00:24:18,260
כמה צעדים שלא ייקח? >> N בריבוע.

408
00:24:18,260 --> 00:24:20,400
כן, אז n בריבוע. מאיפה אתה לוקח n בריבוע מ?

409
00:24:20,400 --> 00:24:22,660
אתה צריך לבדוק כל num -

410
00:24:22,660 --> 00:24:26,530
יש מספרי n, ואתה צריך לבדוק כל מספר עם מספרי n האחרים.

411
00:24:26,530 --> 00:24:29,030
טוב. >> אז זה n בריבוע. >> טוב.

412
00:24:29,030 --> 00:24:31,060
>> אז זה מרגיש כאילו זה יכול להיות מאוד שn בריבוע, נכון?

413
00:24:31,060 --> 00:24:33,820
יש N של החבר 'ה האלה, 8 במיוחד במקרה זה,

414
00:24:33,820 --> 00:24:37,590
אבל בכל פעם שעברתי את הרשימה הזאת אני משווה את האדם הראשון נגד שני,

415
00:24:37,590 --> 00:24:39,650
השני נגד השלישי שוב ושוב ושוב,

416
00:24:39,650 --> 00:24:42,450
וכשהגעתי לסוף, מה אני עושה? אני בניתי אותה מחדש.

417
00:24:42,450 --> 00:24:46,280
אז אם אנחנו מכלילים את ההסבר הזה, יש לנו n אנשים

418
00:24:46,280 --> 00:24:51,090
ואני עושה, כמובן, 8 שלבים, n צעדים, בכל פעם שאני עובר אלגוריתם זה.

419
00:24:51,090 --> 00:24:56,070
אבל כמה פעמים במקרה הגרוע ביותר שאני צריך לעבור את זה רשימה של אנשים?

420
00:24:56,070 --> 00:24:59,370
[תלמיד] N פעמים. כנראה >> n, נכון, כי במקרה הגרוע ביותר,

421
00:24:59,370 --> 00:25:03,410
מה כנראה מקרה ההסדר הגרוע ביותר של החבר 'ה האלה מהרגע הראשון?

422
00:25:03,410 --> 00:25:06,520
אם הם הפוכים לחלוטין כדי

423
00:25:06,520 --> 00:25:09,310
כי פשוט מניח נפשי, בואי - מה שמך? >> בואן.

424
00:25:09,310 --> 00:25:12,510
בואן. אוקיי. אז בואן, יבוא לכאן לרגע.

425
00:25:12,510 --> 00:25:16,150
>> תניח שבואן היה כאן בתחילת האלגוריתם,

426
00:25:16,150 --> 00:25:19,790
ואנחנו לא יודעים מה כל אחד אחר, אבל בואן כאן, על פי אלגוריתם זה -

427
00:25:19,790 --> 00:25:23,820
ואם אתה רוצה רק כדי לטייל איתי - הוא הולך לבעבע, כפי שעשה בסיבוב הראשון,

428
00:25:23,820 --> 00:25:25,740
כל הדרך עד הסוף.

429
00:25:25,740 --> 00:25:29,400
אבל יניח שהאדם הבא לבואן היה המספר 7.

430
00:25:29,400 --> 00:25:33,450
אני חייב לחזור ולקבל מספר 7, מה שאומר שאני צריך ללכת כל הדרך חזרה לכאן.

431
00:25:33,450 --> 00:25:36,980
עכשיו אני צריך שיהיה לי אותו טיול עם האדם שהוא מספר 7.

432
00:25:36,980 --> 00:25:40,140
אבל מה אם אז מספר 6 היה לידו גם כן?

433
00:25:40,140 --> 00:25:42,180
ואז אני צריך לחזור ולקבל 6.

434
00:25:42,180 --> 00:25:46,490
אז שוב, בכל איטרציה של הלולאה הזאת אני מדבר לכל אחד מאנשי n,

435
00:25:46,490 --> 00:25:50,090
ואולי אני אצטרך לעשות n של טיולים אלה כדי לוודא שאני מושך

436
00:25:50,090 --> 00:25:53,760
כל האלמנטים הגדולים שוב ושוב ושוב עד הסוף של הרשימה.

437
00:25:53,760 --> 00:25:58,230
דברי n פעמים אז n הם רק n פעמי n או n בריבוע.

438
00:25:58,230 --> 00:26:02,050
>> אז הנה כבר יש לנו אלגוריתם שכבר לא n, זה כבר לא היומן n,

439
00:26:02,050 --> 00:26:04,820
זה בעצם יותר גרוע מכל דבר שעשינו בעבר.

440
00:26:04,820 --> 00:26:09,840
אז סוג של אלכס לי מזל שבעשיתי את כל העבודה, ככל הנראה מראש עבורה,

441
00:26:09,840 --> 00:26:14,690
כל העבודה היקרה, כדי שאוכל ליהנות באלגוריתם החיפוש הבינארי הזה,

442
00:26:14,690 --> 00:26:16,420
שהוא יומן של n.

443
00:26:16,420 --> 00:26:18,240
אבל זה עולה בקנה אחד עם הנושא של יום שני.

444
00:26:18,240 --> 00:26:23,260
אנחנו נתנו קצת יותר מקום, הייתי עוד חתיכות, כדי להאיץ את זמן הריצה שלנו.

445
00:26:23,260 --> 00:26:26,170
כל כך הרבה כמו שיש תחלופה בין הזמן ומרחב,

446
00:26:26,170 --> 00:26:31,060
יש גם רק יכול להיות פשרות בין משך זמן עד מיון קדמי של מקבל דברים מוכנים ללכת

447
00:26:31,060 --> 00:26:35,000
ואלגוריתם שמבצע בפועל כמו חיפוש. בואו ננסה עוד אחד.

448
00:26:35,000 --> 00:26:39,050
אם אתם לא היו אכפת רק ארגון מחדש במהירות את עצמכם כדי להתאים את זה שוב,

449
00:26:39,050 --> 00:26:42,240
בואו ננסה משהו קצת שונה שבם זה לא ממש פשוט

450
00:26:42,240 --> 00:26:45,760
כפשוט לתקן את כל טעויות pairwise, שהוא הסופר אינטואיטיבי.

451
00:26:45,760 --> 00:26:48,150
בואו במקום להיות קצת יותר מכוון ולעשות את זה.

452
00:26:48,150 --> 00:26:51,010
האחד זה יותר מדי הייתי מציע הוא כנראה די אינטואיטיבי.

453
00:26:51,010 --> 00:26:55,070
>> בואו לבחור את האדם הקטן ביותר מהרשימה שוב ושוב. אז הנה זה בא.

454
00:26:55,070 --> 00:26:57,350
4, אתה האדם הקטן ביותר שראיתי עד כה ובכך,

455
00:26:57,350 --> 00:27:00,520
אז אני הולך נפשי לזכור שרק על ידי הצבעה עליך לעת עתה.

456
00:27:00,520 --> 00:27:05,020
2. אווה! תשכח ממספר 4. אני פשוט מצאתי את היסוד הקטן ביותר החדש ברשימה זו.

457
00:27:05,020 --> 00:27:07,410
אני הולך לסוג של זוכר את זה. 6, 8.

458
00:27:07,410 --> 00:27:11,190
אווה! 1. להתראות. אז עכשיו אני הולך לזכור את המספר 1.

459
00:27:11,190 --> 00:27:14,790
אנו יודעים כי 1 הוא הקטן ביותר, אבל אני המחשב. מה אם יש 0?

460
00:27:14,790 --> 00:27:17,140
מה אם יש -1? אני צריך להמשיך הלאה.

461
00:27:17,140 --> 00:27:20,990
אז 3, 7, 5, זה לא. אוקיי. אז המספר 1 היה הקטן ביותר.

462
00:27:20,990 --> 00:27:23,640
תן לי לבחור לך מהרשימה - אנחנו נלך בדרך זו -

463
00:27:23,640 --> 00:27:27,760
ולשים אותך באופן שרירותי בתחילת הרשימה.

464
00:27:27,760 --> 00:27:29,740
עכשיו, חכה רגע. אני סוג של מרומה.

465
00:27:29,740 --> 00:27:34,010
אם החבר 'ה האלה לא מייצג רשימה של 8 אנשים, אבל מערך,

466
00:27:34,010 --> 00:27:37,050
8 נתחי זיכרון רציף - אכפת לך צעד לאחור לרגע?

467
00:27:37,050 --> 00:27:39,060
אין למעשה שום מקום בשבילך כאן.

468
00:27:39,060 --> 00:27:41,840
אז איך אנחנו עושים את מקום ל-- מה השם שלך? >> סמי. >> סמי.

469
00:27:41,840 --> 00:27:43,710
איך לפנות מקום לסמי?

470
00:27:43,710 --> 00:27:46,760
>> אנחנו עוברים את n שלפני. >> אוקיי.

471
00:27:46,760 --> 00:27:48,850
כדי שנוכל להעביר את אנשי n שלפניו,

472
00:27:48,850 --> 00:27:52,400
כך שאם אתם רוצים לקחת 1 צעד מכוון, דרמטי לשמאל.

473
00:27:52,400 --> 00:27:57,000
כולם עשו את זה ביחד, אבל בפעם האחרונה שכתבתי קצת קוד,

474
00:27:57,000 --> 00:27:59,740
אתה לא יכול כאילו זזת הרבה דברים בבת אחת.

475
00:27:59,740 --> 00:28:02,450
אנחנו יכולים לעשות את זה בלולאה, להעביר את כולם פעם אחת בכל פעם.

476
00:28:02,450 --> 00:28:04,340
אז אם אתם לא היו אכפת לי וחוזרים בחזרה לימין,

477
00:28:04,340 --> 00:28:07,230
וסמי, אם אתה יכול צעד אחורה, כי עדיין אין מקום בשבילך,

478
00:28:07,230 --> 00:28:11,420
עכשיו בואו נעשיתי את זה. איפה היה סמי לפני רגע? בדיוק שם.

479
00:28:11,420 --> 00:28:16,140
אז יש פער שם. אז אתה יכול לעבור למקומו של הסמים.

480
00:28:16,140 --> 00:28:20,580
עכשיו האדם הבא ועכשיו האדם הבא, עכשיו האדם הבא. עכשיו יש לנו מקום לסמי.

481
00:28:20,580 --> 00:28:23,490
עכשיו, מישהו מהקהל - שהיה טוב, זה היה נכון,

482
00:28:23,490 --> 00:28:27,070
זה הרגיש זמן רב קטן - מה יותר מהר? כן.

483
00:28:27,070 --> 00:28:29,440
[תלמיד] מערך חדש? >> מה זה? >> [תלמיד] מערך חדש? >> אוקיי, טוב.

484
00:28:29,440 --> 00:28:33,200
>> אז עולה בקנה אחד עם הנושא הזה של רק פשרות, למה שלא פשוט לעשות מערך חדש

485
00:28:33,200 --> 00:28:36,570
 ואז סמי היה שוחה בחלל מול האנשים האלה, למשל,

486
00:28:36,570 --> 00:28:39,600
ואנחנו רק יכולים להתחיל למלא את המערך חדש לגמרי. גם זה יעבוד.

487
00:28:39,600 --> 00:28:42,450
אבל אני לא מעוניין בהוצאות יותר חלל היום. מה גישה אחרת?

488
00:28:42,450 --> 00:28:46,630
[תלמיד] החלפה. >> אוקיי. אנחנו רק יכולים להחליף 2 הבחורים האלה. מה שמך?

489
00:28:46,630 --> 00:28:49,390
מריו. >> מריו. אז מריו, היית כרגע כאן.

490
00:28:49,390 --> 00:28:52,480
סמי, אתה יכול לגבות רק לרגע? מריו היה כאן.

491
00:28:52,480 --> 00:28:55,830
אין לנו מקום בשבילך יותר, כך שאם לא היית אכפת לו ללכת למקום בו הוא סמי,

492
00:28:55,830 --> 00:29:02,430
אנחנו נשים את סמי כאן, ועכשיו אני הייתי טוען כי פעולתו של סמי ההחלפה הייתה הרבה יותר מהר.

493
00:29:02,430 --> 00:29:06,370
עשינו מבצע 1 להחליף את הבחורים האלה, או אולי להחליף 2 החבר 'ה האלה,

494
00:29:06,370 --> 00:29:11,210
אבל אנחנו לא עשינו 1, 2, 3, 4, כך שמרגישים טוב יותר. עכשיו, חכה רגע.

495
00:29:11,210 --> 00:29:14,660
אני סוג של הפכתי את הבעיה יותר גרועה כי המספר 4 היה סוג של קרוב להתחלה.

496
00:29:14,660 --> 00:29:19,470
עכשיו מספר 4 הוא קצת יותר קרוב לסוף, אבל אני לא ממש יודע ולא אכפת מזה.

497
00:29:19,470 --> 00:29:23,330
כך שזה רק המזל רע שמספר 4 הוא מעט רחוק יותר ממקומה המיועד.

498
00:29:23,330 --> 00:29:25,110
אז בואו עכשיו חזור על האלגוריתם הזה.

499
00:29:25,110 --> 00:29:28,410
>> לסיכום, כל עוד סיפור שהיה, כל מה שעשינו היה ללכת דרך הרשימה

500
00:29:28,410 --> 00:29:31,130
מחפש את האדם הממוספר הקטן ביותר.

501
00:29:31,130 --> 00:29:34,530
אז עכשיו בואו נעשה את זה שוב. אנחנו לא צריכים לדאוג לסמי יותר.

502
00:29:34,530 --> 00:29:37,590
אנחנו פשוט יכולים ללכת כאן. אווה! מספר 2. זה מספר די קטן.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. בסדר, טוב.

504
00:29:41,180 --> 00:29:43,770
ותודה לאל, במקרה, אני לא צריך לעבור - >> וילי.

505
00:29:43,770 --> 00:29:45,910
וילי בגלל שהוא במקום הנכון שלו עכשיו.

506
00:29:45,910 --> 00:29:48,110
בואו נעשה זאת שוב ולהתעלם 2 הבחורים האלה.

507
00:29:48,110 --> 00:29:50,460
6. זה מספר די קטן. אווה! 8 הם בהחלט גדולים.

508
00:29:50,460 --> 00:29:53,410
4. בואו נתמקד ב4. אווה! 3 הם אפילו טובים יותר.

509
00:29:53,410 --> 00:29:58,290
7 ו 5. אז מה אנחנו עושים עכשיו עם - >> רוג'ר. >> רוג'ר?

510
00:29:58,290 --> 00:30:00,250
בואו נחליף אותו עם מספר 6.

511
00:30:00,250 --> 00:30:03,570
אז אם 6 ו 3 היינו רוצים להחליף,

512
00:30:03,570 --> 00:30:07,320
עכשיו אנחנו סוג של קבלנו מזל שב6 הוא יותר קרוב למקום בו היא צריכה להיות,

513
00:30:07,320 --> 00:30:10,300
אבל זה רק צירוף מקרים כאן. אז בואו עכשיו ללכת כאן.

514
00:30:10,300 --> 00:30:13,430
8 הם מספר די קטן. אווה! 4 הם קטנים יותר.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. מה אנחנו עושים עכשיו? החלפה. >> >> בדיוק.

516
00:30:17,130 --> 00:30:19,010
אז עכשיו בואו לעשות את זה סוג של מהר יותר.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. איפה 5 ללכת? טוב. אוקיי.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 מקבלים להישאר איפה היא. מה שמך? >> רוזלי.

519
00:30:28,380 --> 00:30:31,770
רוזלי מקבל להישאר איפה היא. 7 מגיעים ל-- בואו לראות. 7, 8. אוקיי.

520
00:30:31,770 --> 00:30:35,100
אז 7 מקבלים להישאר איפה היא. מה שמך? >> אמנה. >> אמנה.

521
00:30:35,100 --> 00:30:39,670
>> אז האמנה מקבלת להישאר איפה שהיא, ומספר 8 הוא כבר שם הוא צריך להיות עכשיו.

522
00:30:39,670 --> 00:30:43,960
בסדר, טוב. הרגשה הוא שאנחנו פשוט יצירת עבודה לעצמנו לכאן.

523
00:30:43,960 --> 00:30:47,440
מה סופו של דבר זמן הריצה של אלגוריתם זה?

524
00:30:47,440 --> 00:30:51,900
אם אנו חושבים על האנשים האלה לא כמו 8 אבל כn? >> זה n.

525
00:30:51,900 --> 00:30:55,440
זה n צעדים, אבל אנחנו בודקים בכל פעם אחת.

526
00:30:55,440 --> 00:30:57,570
אוקיי. N אבל אתה בודק כל פעם אחת?

527
00:30:57,570 --> 00:31:03,450
אוקיי, אבל אם זה של N צעדים, שאני לא היה יכול למיין אותך רק על ידי הולך 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
הו! אוקיי, זה הבדל גדול.

529
00:31:05,590 --> 00:31:08,050
אז n זקף מדוע? מה באמת קורה?

530
00:31:08,050 --> 00:31:12,130
יש אנשי n ברשימה זו, אך כדי למצוא את האדם הקטן ביותר ברשימה

531
00:31:12,130 --> 00:31:16,200
במקרה הגרוע ביותר, כמה צעדים שאני צריך לקחת? נ >>

532
00:31:16,200 --> 00:31:19,160
>> N, נכון, כי במקרה הגרוע ביותר, מספר 1 הוא את כל הדרך לשם,

533
00:31:19,160 --> 00:31:20,990
אז אני צריך ללכת להביא אותו או אותה.

534
00:31:20,990 --> 00:31:25,500
ואז כשאני סוף הסוף מבין 1 היה הקטן ביותר, אז זה די מהר כדי להחליף אותם.

535
00:31:25,500 --> 00:31:28,450
אבל עכשיו אני צריך להתחיל מההתחלה ולחפש את מי?

536
00:31:28,450 --> 00:31:31,980
האדם הבא הקטן ביותר, שהוא 2. איפה במקרה הגרוע ביותר הוא 2?

537
00:31:31,980 --> 00:31:34,320
הו, אלוהים שלי. זה כל הדרך לכאן בסוף.

538
00:31:34,320 --> 00:31:37,000
אז עכשיו זה עתה עשה עוד צעדים, צעדי n n עוד.

539
00:31:37,000 --> 00:31:41,200
אם יש לנו אנשי n ובמקרה הגרוע ביותר לאדם הוא הקטן ביותר n צעדים ו,

540
00:31:41,200 --> 00:31:45,230
זה שוב n הפעמים n, ולכן שוב לא n בריבוע.

541
00:31:45,230 --> 00:31:47,280
זה לא מרגיש כל כך טוב.

542
00:31:47,280 --> 00:31:52,150
ואכן, גם במקרה הטוב ביותר - תניח שהם מתחילים למיין את -

543
00:31:52,150 --> 00:31:59,080
כמה צעדים נדרש לי באמצעות אלגוריתם זה כדי למיין את האנשים האלה n?

544
00:31:59,080 --> 00:32:01,010
N בריבוע. >> שמעתי n בריבוע. למה n זקף?

545
00:32:01,010 --> 00:32:05,240
מכיוון שאתה עדיין צריך לבדוק בכל פעם מחדש. >> כן.

546
00:32:05,240 --> 00:32:08,060
ואתה צריך להחליף אותם. >> אף אנו, בני האדם הוא סוג של כל יודע

547
00:32:08,060 --> 00:32:10,770
במובן חזותי שאנחנו יכולים פשוט סוג של לראות שזה מסודר,

548
00:32:10,770 --> 00:32:12,140
מחשב הוא לא כל כך חכם.

549
00:32:12,140 --> 00:32:14,040
זה הולך להיראות כאן וכאן וכאן,

550
00:32:14,040 --> 00:32:16,610
אבל אם מה שהוא מחפש הוא היסוד הקטן ביותר,

551
00:32:16,610 --> 00:32:22,110
אתה רק יודע שאתה מצאת היסוד הקטן ביותר של מה טעם? ברגע שאתה בסופו של דבר.

552
00:32:22,110 --> 00:32:25,880
אך בשלב זה שמצאת את האלמנט הקטן ביותר כרגע בלבד.

553
00:32:25,880 --> 00:32:28,810
אתה לא בהכרח יודע עוד משהו על מצבו של העולם.

554
00:32:28,810 --> 00:32:30,880
אז אתה צריך ללכת שוב ושוב ושוב.

555
00:32:30,880 --> 00:32:34,880
>> אז הפעם אני באמת נראה מטומטם כי אני בודק, בסדר, 2, אתה קטן,

556
00:32:34,880 --> 00:32:37,530
אבל אני לא יודע שבסיכום עדיין.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. בסדר, טוב. 2 אכן היו הקטנים ביותר.

558
00:32:41,090 --> 00:32:43,150
עכשיו נמצא לי הנמוך הבא. אוקיי.

559
00:32:43,150 --> 00:32:48,350
3, אתה כרגע הקטן ביותר. בואו נראים. 4, 5, 6, 7, 8. אוקיי, יש את המזל שוב.

560
00:32:48,350 --> 00:32:53,170
3 אכן היו במקום הנכון. אבל אני הולך להמשיך לעשות את זה שוב ושוב ושוב.

561
00:32:53,170 --> 00:32:55,990
איך אנחנו יכולים לעשות אי פעם כל כך מעט טובים יותר?

562
00:32:55,990 --> 00:33:00,120
במקום שיש עד pairwise מקטן ועד גדולים ביותר אנשי בועה

563
00:33:00,120 --> 00:33:04,350
ובמקום ללכת קדימה ואחורה ברשימת בחירת האדם אז הקטן ביותר,

564
00:33:04,350 --> 00:33:09,780
למה אנחנו לא במקום להכניס את האנשים האלה לרשימה חדש צעד אחר צעד?

565
00:33:09,780 --> 00:33:13,080
בואו ננסה את זה. עכשיו בואו תקראו לי סוג החדרת הדבר הזה.

566
00:33:13,080 --> 00:33:17,250
אז הנה אנחנו כאן. מספר 1. לא אכפת לי על מישהו אחר ברשימה זו.

567
00:33:17,250 --> 00:33:21,310
המטרה שלי עכשיו היא לשים מספר 1 בתחילת רשימה ממוינת.

568
00:33:21,310 --> 00:33:23,910
ואני הולך להציע מאז יש לי 8 חתיכות של זיכרון בלבד,

569
00:33:23,910 --> 00:33:28,670
באופן שרירותי כרגע אני החומה בין הרשימה הממוינת כביכול שלי,

570
00:33:28,670 --> 00:33:32,740
ומי שעומד מאחוריי אני הולך לתבוע ממוין.

571
00:33:32,740 --> 00:33:34,680
אז עכשיו יש לנו מספר 1.

572
00:33:34,680 --> 00:33:39,240
אני רוצה להכניס אותו לרשימה הממוינת שלי, אז אני פשוט הולך לעבור הקיר שלי כאן,

573
00:33:39,240 --> 00:33:43,930
ועכשיו אני טוען רשימה זו היא מסודרת, רשימה זו היא ללא מיון - לפחות עד כמה שאני יודע.

574
00:33:43,930 --> 00:33:46,070
אני לא יכול לראות את כל המספרים בפעם אחת.

575
00:33:46,070 --> 00:33:49,000
>> עכשיו אני במקרה נתקל במספר 2. מה עליי לעשות איתו?

576
00:33:49,000 --> 00:33:54,380
אני מכניס אותך עכשיו לרשימה הממוינת. אבל שים לב כמה קל זה היה.

577
00:33:54,380 --> 00:33:59,650
אני רק צריך לחפש. מספר 1 הוא שם. אה, ברור 2 הולכים לצד של מספר 1.

578
00:33:59,650 --> 00:34:03,700
עכשיו מה שאני עושה עם 3? אני אכניס אותך לרשימה הממוינת. אבל זה היה סופר קל.

579
00:34:03,700 --> 00:34:07,250
זה סופר קל, זה סופר קל, זה סופר קל, סופר קל, סופר קל.

580
00:34:07,250 --> 00:34:12,790
ועכשיו הכל מסודר מאחוריי, וכמה צעדים לא שייקח?

581
00:34:12,790 --> 00:34:15,620
[סטודנטים] נ >> אז זה n בלבד. היינו לנו מזל.

582
00:34:15,620 --> 00:34:18,860
זה היה רק ​​n מדוע? >> [תלמיד] כי הרשימה הייתה ממוינת.

583
00:34:18,860 --> 00:34:21,630
הרשימה כבר ממוינת. אז היינו לנו מזל.

584
00:34:21,630 --> 00:34:25,639
אבל אנחנו תוכננו אלגוריתם הזמן הזה שרותם זה סוג של מזל,

585
00:34:25,639 --> 00:34:29,420
שהמקרה הטוב, בכך שלא לבזבז זמן מיותר.

586
00:34:29,420 --> 00:34:31,750
אז עכשיו יש לנו את מה שאנחנו קוראים למיני בועה

587
00:34:31,750 --> 00:34:33,949
שבו אנשים מסוג של בועה עד pairwise.

588
00:34:33,949 --> 00:34:38,100
עכשיו יש לנו מיון בחירה בו אנו קוטפים את האדם הקטן ביותר שוב ושוב.

589
00:34:38,100 --> 00:34:42,350
ועכשיו יש לנו מעין כניסה בה אנחנו כאילו באופן יזום את אנשים שבו הם שייכים

590
00:34:42,350 --> 00:34:45,000
ברשימה ממוינת יותר ויותר.

591
00:34:45,000 --> 00:34:49,679
אם היינו יכול, מחיאות כפות לחבר 'ה אלה כאן. [מחיאות כפות]

592
00:34:49,679 --> 00:34:52,310
בואו ניקח ההפסקה שלנו 5-הרגע פה.

593
00:34:52,310 --> 00:34:55,139
וכשנחזור, שנפוצץ את כל האלגוריתמים האלה מחוץ למים

594
00:34:55,139 --> 00:35:00,260
עם משהו טוב יותר. בסדר. תודה רבה מאוד. אתה יכול לשמור אותם למזכרת.

595
00:35:01,710 --> 00:35:04,330
בסדר. אנחנו נחזור.

596
00:35:04,330 --> 00:35:08,420
>> ולסכם ממש מהר, היו לנו 3 גישות השונות האלה למיון,

597
00:35:08,420 --> 00:35:13,000
כל העניין של שהיה להגיע לנקודה שבה מישהו כמו אלכס

598
00:35:13,000 --> 00:35:16,930
תוכל לחפש ברשימה של מספרים יותר מהר ממישהו כמו שון יכל.

599
00:35:16,930 --> 00:35:19,830
למרות שיש לנו דוגמאות פשוטות כאלה עם 8 מספרים ו,

600
00:35:19,830 --> 00:35:24,000
אתה יכול להסיק בקלות עד 8 דפי אינטרנט, 8 מליארד דפי אינטרנט,

601
00:35:24,000 --> 00:35:26,680
או 800 מיליון חברים בפייסבוק.

602
00:35:26,680 --> 00:35:30,090
אז האלגוריתמים האלה בהחלט ניתנים להרחבה לאלו סוגים של ערכים,

603
00:35:30,090 --> 00:35:32,300
והרעיונות הם בסופו.

604
00:35:32,300 --> 00:35:36,140
אז מיון בועות היה הראשון שבו אנחנו סוג של פעפעו האדם הגדול ביותר

605
00:35:36,140 --> 00:35:39,110
כל הדרך לצד ימין על ידי החלפת אנשי pairwise.

606
00:35:39,110 --> 00:35:42,040
ואז היו לנו את מה שאנחנו קוראים למיון בחירה שבו אני קצת יותר בכוונה

607
00:35:42,040 --> 00:35:46,480
המשיך להסתכל ברשימה, בחירת המספר הקטן שוב ושוב ושוב,

608
00:35:46,480 --> 00:35:49,530
התוצאה ההגיונית שלו היא שהרשימה ממוינת סופו של דבר.

609
00:35:49,530 --> 00:35:53,780
אז בשליש, הכנסתי את אנשים למקום הראוי שלהם,

610
00:35:53,780 --> 00:35:57,720
ועשינו את דוגמה מאוד מאולצת שברשימה הייתה ממוינת כבר,

611
00:35:57,720 --> 00:36:01,100
אבל זה היה לשלוח את ההודעה כי במקרה של סוג ההכנסה,

612
00:36:01,100 --> 00:36:02,670
אתה יכול לקבל מזל.

613
00:36:02,670 --> 00:36:07,930
אם המספרים כבר מסודרים, זה רק הולך לקחת אותך n צעדים כדי לאשר כל כך הרבה,

614
00:36:07,930 --> 00:36:10,870
ואילו מיון בחירה אתה ראיית מנהרה קצת יותר

615
00:36:10,870 --> 00:36:14,360
ואתה אף פעם לא מבין שהרשימה כבר ממוינת.

616
00:36:14,360 --> 00:36:16,830
אז בואו לראות מיון בועות בפעולה כאן.

617
00:36:16,830 --> 00:36:19,590
בדוגמא הבאה, אנחנו עומדים לראות קווים אנכיים

618
00:36:19,590 --> 00:36:23,030
גבהים שמייצגים מספרים, כך שאנחנו יכולים לעשות משהו של לדמיין מיון לקרות.

619
00:36:23,030 --> 00:36:26,630
קטן על הבר, קטן המספר; הבר הגדול יותר, המספר הגדול יותר.

620
00:36:26,630 --> 00:36:28,860
>> ונשחקנו אותו במהירות זו כברירת מחדל.

621
00:36:28,860 --> 00:36:33,460
זה הולך לעבור מהר קטן לעת עתה, אך אדום הוא מה שמראה 2 פסים

622
00:36:33,460 --> 00:36:35,480
לצורך ההשוואה זה לצד זה.

623
00:36:35,480 --> 00:36:39,520
ואם אתם צופים הדוקים, מה שקורה הוא שאם את הסורגים הם מקולקלים,

624
00:36:39,520 --> 00:36:42,300
הקטן אחד לא עבר לשמאל, אחד הגדול יותר בצד ימין,

625
00:36:42,300 --> 00:36:44,360
ואז אתה ממשיך להתקדם.

626
00:36:44,360 --> 00:36:48,520
אז אם אנחנו עושים את זה שוב ושוב, שים לב שהברים הקטנים

627
00:36:48,520 --> 00:36:51,090
הולכים לשמור התקדם דרכם לשמאל

628
00:36:51,090 --> 00:36:54,130
והברים הגדולים הולכים לשמור התקדם דרכם לימין.

629
00:36:54,130 --> 00:36:58,490
ואכן, אנחנו מתחילים לראות דפוס כל הדרך בצד ימין

630
00:36:58,490 --> 00:37:04,790
בדיוק כמו שראינו 8 ואז 7 סופו של דבר מבעבעים עד הקצה המרוחק של הרשימה האנושית שלנו.

631
00:37:04,790 --> 00:37:08,750
אז זה הולך מהר מאוד לקבל קצת משעמם, אז בוא תעצור אותי לרגע.

632
00:37:08,750 --> 00:37:10,980
הרשה לי לשנות את המהירות להיות הרבה יותר מהר.

633
00:37:10,980 --> 00:37:15,380
אני לא משנה את האלגוריתם, שאני רק עושה את האנימציה תקרה מהר יותר.

634
00:37:15,380 --> 00:37:18,410
עדיין מיון בועות, אותו אלגוריתם,

635
00:37:18,410 --> 00:37:21,910
אבל עכשיו אתה יכול לראות הרבה יותר מהר מאשר ההפגנה המילולית שלנו

636
00:37:21,910 --> 00:37:25,900
כי האלמנטים הגדולים אכן מבעבעים לראש.

637
00:37:25,900 --> 00:37:29,860
>> במאמר מוסגר, ריבועים אלה קטנים בצד השמאל למטה ותחתונים ימניים

638
00:37:29,860 --> 00:37:33,520
הם רק תזכורות קטנות כמו לכמה השוואות שאתה עושה.

639
00:37:33,520 --> 00:37:37,620
אבל נכון לעכשיו, אנו יכולים להתמקד בפירמידה שלוקחת צורה, והנה זה בא.

640
00:37:37,620 --> 00:37:41,510
האלמנט הקטן ביותר הוא בצד השמאל, הגדול ביותר בצד ימין, וכל הדבר אחר באמצע.

641
00:37:41,510 --> 00:37:44,470
עכשיו בואו במקום להעיף מבט במיון בחירה.

642
00:37:44,470 --> 00:37:47,260
אני הולך קדימה ופגעתי בעצירה. אנחנו הולכים לקבל קבוצה אקראית חדשה של ברים.

643
00:37:47,260 --> 00:37:50,930
מיון בחירה, כזכור, על הרשימה שוב ושוב ושוב,

644
00:37:50,930 --> 00:37:54,900
מריטת היסוד הקטן ביותר. אז הנה הוא מיון בחירה.

645
00:37:54,900 --> 00:37:58,390
זה נראה כאילו יש פחות עבודה של קורית עכשיו כי אנחנו לא משווים pairwise

646
00:37:58,390 --> 00:38:02,590
אבל אנחנו סתם מין לקטוף דובדבני האלמנטים הקטנים ביותר מימין לשמאל.

647
00:38:02,590 --> 00:38:06,890
זה לקח מעט מאוד זמן, כך שאין כבר הדיכוטומיה.

648
00:38:06,890 --> 00:38:11,820
רק בגלל שאלגוריתם הוא אמר לקחת זמן ריבוע n, כמו מיון בועות

649
00:38:11,820 --> 00:38:16,100
וכמו מיון בחירה, אלה הם באמת פעמים רצופות במקרה הגרוע ביותר.

650
00:38:16,100 --> 00:38:21,790
לדוגמה, במקרה של, יניח, מיון בחירה,

651
00:38:21,790 --> 00:38:27,240
אני דווקא בחירה באדם הקטן ולשים אותו או אותה לכאן,

652
00:38:27,240 --> 00:38:29,620
אז אני עושה את זה שוב, ואז אני עושה את זה שוב,

653
00:38:29,620 --> 00:38:32,070
אבל לא הייתה שם אופטימיזציה קלה אני יכול לעשות.

654
00:38:32,070 --> 00:38:35,040
>> ברגע שעברתי מספר 1 כאן - סמי במקרה זה -

655
00:38:35,040 --> 00:38:38,630
מה שאני לא צריך לעשות איתו לאחר מכן? >> [תלמיד] עזוב אותו.

656
00:38:38,630 --> 00:38:40,140
תעזוב אותו, נכון? שום דבר.

657
00:38:40,140 --> 00:38:44,310
אני לא צריך בכלל לדבר עם סמי שוב כי אם הייתי נבחרתי היסוד הקטן ביותר

658
00:38:44,310 --> 00:38:48,580
והכניס אותו לכאן, למה לבזבז זמן הולך לסוף כל הרשימה שלי?

659
00:38:48,580 --> 00:38:54,590
באיטרציה הבאה תנו לי למעשה לנוע רק למספר 2, רק למספר 3.

660
00:38:54,590 --> 00:38:57,640
אז במציאות, לא הייתי עושה את דברי n n פעמים.

661
00:38:57,640 --> 00:39:05,380
אני עושה דברים n, אז n - 1 בעניינים, אז n - 2 דברים, אז n - 3 דברים,

662
00:39:05,380 --> 00:39:07,080
אז n - 4, נקודה, נקודה, נקודה.

663
00:39:07,080 --> 00:39:09,470
יש לנו קצת סדרה גיאומטרית, שרק אומר

664
00:39:09,470 --> 00:39:11,450
אתה מוסיף את מספרים בהדרגה קטנות יותר.

665
00:39:11,450 --> 00:39:17,940
לא n + n + n + n אבל n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
ומה שבדרך כלל פועל יוצא להיות -

667
00:39:21,380 --> 00:39:24,280
אני הולך לעשות בלגן בלוח שלי כאן רק לרגע -

668
00:39:24,280 --> 00:39:28,990
זה הולך לעבוד כדי להיות משהו כמו n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
אם רק לנו סוג של מראה בחלק האחורי של ספר מתמטיקה שבו יש לך את כל גיליונות לרמות

670
00:39:31,930 --> 00:39:33,410
לנוסחות.

671
00:39:33,410 --> 00:39:37,760
אם אתה רק מוסיף משהו n + n - 1 + n - 2, זה פועל יוצא להיות משהו כזה.

672
00:39:37,760 --> 00:39:42,320
ואם אנחנו פשוט סוג של להכפיל את זה, זה n בריבוע מינוס n / 2.

673
00:39:42,320 --> 00:39:46,400
אני כל זמן אמר n בריבוע, אם כי, וזה בגלל שאני סוג של עושה קיצור דרך נפש

674
00:39:46,400 --> 00:39:51,950
כי במציאות, n בריבוע מינוס n חלק 2 הוא אכן המספר הנכון של צעדים

675
00:39:51,950 --> 00:39:55,510
שאלגוריתם כמו מיון בחירה היה לוקח אם אנחנו באמת ספרנו עד

676
00:39:55,510 --> 00:39:58,800
כל ההשוואות האלה ואת כל העבודה הקטנה והעסוקה שאנחנו עושים.

677
00:39:58,800 --> 00:40:03,210
אבל בכנות, ברגע שמקבל n להיות כמו מ'או מיליארדים, מי לעזאזל אכפת

678
00:40:03,210 --> 00:40:07,160
אם אתה עושה מליארד מינוס בריבוע מיליארדים חלק 2?

679
00:40:07,160 --> 00:40:09,320
בריבוע מליארד הוא מספר עצום.

680
00:40:09,320 --> 00:40:13,580
אתה יכול לקחת את זה ממנו במיליארדים - n. זה לא כזה ביג דיל.

681
00:40:13,580 --> 00:40:18,770
אז גדול יותר לקבל את המספרים, את פחות החשוב מבחינת המסודר הנמוך אלה.

682
00:40:18,770 --> 00:40:24,230
למי אכפת אם אתה מחלק ידי 2 אם אתה מדבר על quadrillions של מספרים של שלבים?

683
00:40:24,230 --> 00:40:29,710
>> אז באופן כללי, מדעני מחשב נוטים להשליך הכל אבל הטווח הגדול ביותר,

684
00:40:29,710 --> 00:40:33,140
ואנחנו פשוט סוג של לפשט את העולם ולומר שאלגוריתם

685
00:40:33,140 --> 00:40:38,130
צעדים בערך n בריבוע. זה זמן הריצה של אלגוריתם.

686
00:40:38,130 --> 00:40:40,760
אז תחזרו לזה ברגע עם דוגמאות קונקרטיות,

687
00:40:40,760 --> 00:40:45,940
אך לעת עתה, זה סוג של המוטיבציה מאחורי אינטואיטיבי פשוט לפשט את העולם שלנו

688
00:40:45,940 --> 00:40:51,170
ומדבר על התנאים החשובים ביותר ולא להיכנס לכל הנוסחות המפוארות האלה.

689
00:40:51,170 --> 00:40:53,540
אז זה היה מיון בחירה, ויש לנו קצת מזל שם.

690
00:40:53,540 --> 00:40:57,360
בואו נסתכל על סוג ההכנסה. תן לי ללכת קדימה ולהתחיל גם את זה.

691
00:40:57,360 --> 00:41:00,330
עכשיו שים לב לדפוס שקורה הוא קצת שונה,

692
00:41:00,330 --> 00:41:03,410
ואנחנו התחלנו עם מספרים אקראיים,

693
00:41:03,410 --> 00:41:06,890
אבל אם אנחנו ממש לספור את מספר הצעדים במקרה הגרוע ביותר,

694
00:41:06,890 --> 00:41:11,070
אם הרשימה התחילה לגמרי בבסדר הנכונה,

695
00:41:11,070 --> 00:41:13,380
היינו לנקוט בצעדי n רק כדי להבין עד כמה.

696
00:41:13,380 --> 00:41:18,240
>> אבל אם הרשימה הייתה למעשה לאחור - למשל, במקרה הזה כאן -

697
00:41:18,240 --> 00:41:23,860
אז שם לב שאנחנו באמת צריכים לעשות הרבה יותר עבודה במקרה זה.

698
00:41:23,860 --> 00:41:27,080
ואת זה צריך סוג של מרגיש לך כמו זה הוא סוג של עבודה קשה

699
00:41:27,080 --> 00:41:30,900
כדי לקבל אותם האלמנטים קטנים לשמאל, וזה בגלל שיש לנו מזל.

700
00:41:30,900 --> 00:41:34,210
הרשימה מוינה בטעות בכיוון הפוך.

701
00:41:34,210 --> 00:41:38,110
לעומת זאת, עם סוג ההכנסה אם לחקות את מה שעשינו עם האנשים שלנו כאן

702
00:41:38,110 --> 00:41:42,670
על ידי התחלה עם כולם מסודרים ואז להתחיל, זה אלגוריתם די טוב, נכון?

703
00:41:42,670 --> 00:41:45,010
זה כבר, למעשה, מיון.

704
00:41:45,010 --> 00:41:48,670
אז בואו ננסה לסכם בדיוק כמה זמן הדברים האלה לוקחים אותנו

705
00:41:48,670 --> 00:41:52,360
על ידי החדרה רק קצת ז'רגון או סימון שבעצם הרבה יותר פשוט

706
00:41:52,360 --> 00:41:54,320
מסוג fanciness של מציע.

707
00:41:54,320 --> 00:41:59,030
הדבר הזה כאן, גדול O זה על המסך, מה שמדען מחשב בדרך כלל להשתמש

708
00:41:59,030 --> 00:42:03,640
כדי לתאר את זמן הריצה במקרה הגרוע ביותר של אלגוריתם.

709
00:42:03,640 --> 00:42:07,360
>> שוב, על ידי מקרה הגרוע ביותר, זה לגמרי תלוי קשר.

710
00:42:07,360 --> 00:42:10,890
למה אנחנו מתכוונים במקרה הגרוע לחלוטין משתנה בהתבסס על הבעיה שאנחנו מדברים עליו.

711
00:42:10,890 --> 00:42:14,550
אבל במקרה של מיון, מה התרחיש הגרוע ביותר האפשרי?

712
00:42:14,550 --> 00:42:17,860
הכל אחורה כי זה פשוט מרגיש כמו שאומר הרבה עבודה בשבילנו.

713
00:42:17,860 --> 00:42:21,330
אני כבר רשמתי כמה מהאלגוריתמים שראינו עד כה:

714
00:42:21,330 --> 00:42:24,930
חיפוש לינארי, חיפוש בינארי כמו בספר טלפונים או את פיסות נייר,

715
00:42:24,930 --> 00:42:28,960
אז מיון בועות, מיון בחירה, והחדרת מין כמו שראינו בבני האדם שלנו,

716
00:42:28,960 --> 00:42:31,770
ואז 1 אחר זה הסוף של דבר הולך להיות שם למזג מיון.

717
00:42:31,770 --> 00:42:37,710
אז בחיפוש ליניארי במקרה הגרוע ביותר, כמה צעדים נדרש כדי למצוא את המספר 7

718
00:42:37,710 --> 00:42:40,690
אם יש דלתות n כמו שון פנים? >> [תלמיד] נ

719
00:42:40,690 --> 00:42:44,180
נ אז אנחנו הולכים לכתוב גדול O של n.

720
00:42:44,180 --> 00:42:47,010
אני רק הולך למלא מקומות מסוימים. זה רק רשת של חללים.

721
00:42:47,010 --> 00:42:52,990
אבל במקרה הטוב לחיפוש ליניארי, 7 אולי היו בתחילה מאוד של הרשימה,

722
00:42:52,990 --> 00:42:55,520
שון ואולי התחיל לחפש בתחילת הרשימה.

723
00:42:55,520 --> 00:42:58,940
אז אם אתה משתמש בחיפוש ליניארי ורק בודק משמאל לימין או אולי ימין לשמאל -

724
00:42:58,940 --> 00:43:02,650
הם שווים ערך - במקרה הטוב כמה צעדים עשויים לחפש ליניארי,

725
00:43:02,650 --> 00:43:05,550
כמו האלגוריתם של שון, לקחת? רק שלב 1.

726
00:43:05,550 --> 00:43:09,450
>> אז אני הולך להגיד שזה סימון האומגה.

727
00:43:09,450 --> 00:43:11,570
זה רק אומגת הון.

728
00:43:11,570 --> 00:43:15,000
אומגה היא פשוט הדרך של אמירה הסקסית מקרה טוב זמן הריצה.

729
00:43:15,000 --> 00:43:18,900
אז במקרה הטוב את זמן הריצה הוא צעד אחד או מספר קבוע של צעדים -

730
00:43:18,900 --> 00:43:24,270
1 במקרה זה - אבל במקרה הגרוע ביותר, הגדול O, הוא למעשה שלבי n.

731
00:43:24,270 --> 00:43:28,110
וזה כאן, תטא, אנחנו באמת לא הולכים להסתכל על עכשיו.

732
00:43:28,110 --> 00:43:30,090
זה לא רלוונטי לדוגמה זו בפרט.

733
00:43:30,090 --> 00:43:31,990
אבל עכשיו בואו ננסה חיפוש בינארי.

734
00:43:31,990 --> 00:43:35,990
במקרה הגרוע ביותר, עם חיפוש בינארי, כמה צעדים זה הולך לקחת כדי למצוא את המספר 7

735
00:43:35,990 --> 00:43:38,340
או מה שאנחנו מחפשים? >> [התלמיד] התחבר n.

736
00:43:38,340 --> 00:43:40,980
עדיין הולך לקחת n יומן כי בדיוק כמו אלכס קבל מזל

737
00:43:40,980 --> 00:43:44,030
כאשר אנחנו באמת עבדנו דרך הבעיה באופן שיטתי

738
00:43:44,030 --> 00:43:48,220
והיא לא מוצאת את המספר 7, עד שהדלת האחרונה שהיא מביטה בו,

739
00:43:48,220 --> 00:43:51,720
למרות, בהגינות, היא חייבת לזרוק את דלתות מסוימות לאורך הדרך,

740
00:43:51,720 --> 00:43:56,920
החיפוש בינארי במקרה הגרוע יש לו זמן ריצה של log n.

741
00:43:56,920 --> 00:43:59,230
ושוב, שמדבר אל חלוקה הזאת וכובשת.

742
00:43:59,230 --> 00:44:01,140
אבל מה במקרה הטוב?

743
00:44:01,140 --> 00:44:04,790
ואלכס ממש חווה שמקרה הטוב צדק כשעלה על במה.

744
00:44:04,790 --> 00:44:07,290
כמה צעדים שלא ייקח בחיפוש בינארי? >> [תלמיד] 1.

745
00:44:07,290 --> 00:44:09,380
1, רק בגלל שהיא זכתה בכבוד גדול.

746
00:44:09,380 --> 00:44:12,520
אבל זה בסדר, כי האומגה מתייחסת לתרחישים במקרה הטובים ביותר,

747
00:44:12,520 --> 00:44:15,770
כניסות הטובות ביותר במקרה, גם אם זה רק מזל עיוור אקראי.

748
00:44:15,770 --> 00:44:18,900
>> עכשיו, גם את זה אנחנו הולכים פשוט סוג של חופשה ריקה לעת עתה.

749
00:44:18,900 --> 00:44:21,010
מה דעתך על עכשיו מיון בועות?

750
00:44:21,010 --> 00:44:24,290
במקרה הגרוע ביותר במיון בועות, כולם בסדר הפוך,

751
00:44:24,290 --> 00:44:26,380
לכן אנחנו צריכים לעשות הרבה מבעבעים.

752
00:44:26,380 --> 00:44:30,190
אבל כמה צעדים שהוא מתכוון לנקוט במקרה הגרוע ביותר? >> [התלמיד] N בריבוע.

753
00:44:30,190 --> 00:44:32,550
זה היה n בריבוע, משום שאם אתה חושב על זה,

754
00:44:32,550 --> 00:44:36,410
אם הרשימה היא לגמרי הפוכה - 8 הן כאן, 1 הוא כאן -

755
00:44:36,410 --> 00:44:40,530
כדבר מתחיל לבעבע, המספר 8 הוא הולך לעבור בדרך זו, בדרך זו,

756
00:44:40,530 --> 00:44:44,540
בדרך זו, בדרך זו, אבל איפה היא המספר 7 במקרה הגרוע ביותר?

757
00:44:44,540 --> 00:44:47,720
הנה הוא עדיין שם. אז אנחנו צריכים לעשות את זה שוב ושוב.

758
00:44:47,720 --> 00:44:53,190
וזה שבו אנו מקבלים את צעדי n, אז n - 1 צעדים, ואז n - 2 שלבים.

759
00:44:53,190 --> 00:44:55,960
ואם אתה לוקח את המילה שלי בשביל זה - כי אם סוג של להכפיל אותו,

760
00:44:55,960 --> 00:45:00,110
זה בערך n בריבוע בסוף עם כמה מונחים אחרים שאנחנו פשוט מתעלמים לעת עתה -

761
00:45:00,110 --> 00:45:06,890
אז במקרה הכי הגרוע מיון הבועות הוא n בריבוע, פחות או יותר.

762
00:45:06,890 --> 00:45:09,490
אבל מה במקרה הטוב למיון בועות?

763
00:45:09,490 --> 00:45:13,050
מהו התרחיש הטוב ביותר? כל המספרים מסודרים כבר.

764
00:45:13,050 --> 00:45:15,920
ומה היה האוריסטי נהגתי, הטריק הייתי,

765
00:45:15,920 --> 00:45:20,110
להבין שלא עשיתי כל עבודה ולכן יכול להפסיק מוקדם?

766
00:45:20,110 --> 00:45:23,590
[תלמיד] תבדקו את זה פעם אחת. >> בדוק את זה פעם אחת. אבל מה שאני עושה בדרך?

767
00:45:23,590 --> 00:45:26,130
אני עוקב אחרי כמה חילופים שעשיתי.

768
00:45:26,130 --> 00:45:30,650
והבנתי שאם לא ספרתי כל החלפות על האצבעות שלי, אז אני לא עשיתי את עבודה.

769
00:45:30,650 --> 00:45:34,300
אני בהחלט לא צריך לנסות לעשות שום עבודה שוב, אז אני יכול פשוט להפסיק.

770
00:45:34,300 --> 00:45:37,830
>> אז במקרה הטוב של מיון בועות כאשר הרשימה כבר ממוינת,

771
00:45:37,830 --> 00:45:41,530
מה היית אומר סימון האומגה הוא, במקרה הטוב זמן ריצה?

772
00:45:41,530 --> 00:45:48,040
זה פשוט n. יש לנו עבודה לעשות, אבל יש לנו רק לעשות טיול שווה של 1 של עבודה.

773
00:45:48,040 --> 00:45:50,490
וגם כאן אני הולך לעזוב את החלק הזה ריק.

774
00:45:50,490 --> 00:45:52,430
ועכשיו מיון בחירה.

775
00:45:52,430 --> 00:45:56,010
מיון בחירתי שמריטת האדם הקטן ביותר שוב ושוב.

776
00:45:56,010 --> 00:45:58,380
ומה שאנחנו לא אומרים את משך ההפעלה של שהיה?

777
00:45:58,380 --> 00:46:00,590
זה היה n בריבוע במקרה הגרוע ביותר.

778
00:46:00,590 --> 00:46:05,220
ולרוע המזל, במקרה הטוב זה גם n בריבוע

779
00:46:05,220 --> 00:46:08,840
משום שאין לי מין נוף היודע כל של העולם כולו;

780
00:46:08,840 --> 00:46:13,140
אני יודע רק על איטרציה מלאה כי אני כבר מצאתי את האדם הקטן מאוד.

781
00:46:13,140 --> 00:46:15,860
אז סוג של מיון בחירה מבאסת במובן זה,

782
00:46:15,860 --> 00:46:17,920
אבל היתרון הוא שזה די אינטואיטיבי.

783
00:46:17,920 --> 00:46:21,470
זה די קל לקוד עד כי כל מה שאתה צריך לעשות הוא לכתוב כמה מקונן ללולאות,

784
00:46:21,470 --> 00:46:24,620
בדרך כלל, שעובר מחפש את האלמנט הקטן ביותר

785
00:46:24,620 --> 00:46:27,840
ואז מניח את היסוד הקטן ביותר שבו היא שייכת בסוף הרשימה.

786
00:46:27,840 --> 00:46:29,900
אז גם כאן הולך להיות תחלופה.

787
00:46:29,900 --> 00:46:34,440
כמות הזמן שלוקח לך לחשוב ולמעשה לפתח משהו על ידי כתיבת קוד

788
00:46:34,440 --> 00:46:39,460
יכול מאוד לקחת יותר זמן אם אתה רוצה ביצועים טובים יותר ומהר יותר אלגוריתם.

789
00:46:39,460 --> 00:46:41,780
>> אבל אם אתה באמת רק סוג של משהו עד קוד מהיר ומלוכלך

790
00:46:41,780 --> 00:46:45,000
ורק סוג של לקחת את הרעיון המטופש ביותר האפשרי שאתה יכול לחשוב,

791
00:46:45,000 --> 00:46:47,580
זה עלול לקחת לך כמה דקות לקוד, אבל עם ערכות נתונים גדולות

792
00:46:47,580 --> 00:46:49,580
האלגוריתם שלך עלול לקחת שעות כדי לרוץ.

793
00:46:49,580 --> 00:46:51,690
וגם אני בבית הספר למוסמכים הייתי לפעמים להפוך אותם לפשרות.

794
00:46:51,690 --> 00:46:55,660
זה יהיה 03:00, אני מנסה לנתח כמה ערכת נתונים גדולות מאוד

795
00:46:55,660 --> 00:46:59,650
קשור למחקר הביטחון שאני עושה, וזה היה או לבלות 5 דקות

796
00:46:59,650 --> 00:47:03,210
tweaking התכנית שלי כדי לנתח את הנתונים והולכים לישון

797
00:47:03,210 --> 00:47:08,420
או לבלות 8 שעות מקבלות אותו בדיוק כך שהוא פועל באופן מיידי ולא ללכת לישון.

798
00:47:08,420 --> 00:47:10,530
וכך גם שם זה סוג של החלטה מודעת.

799
00:47:10,530 --> 00:47:12,740
פחות זמן פיתוח, לישון יותר.

800
00:47:12,740 --> 00:47:14,780
במבט לאחור, אני בטח לא צריך לעודד זאת

801
00:47:14,780 --> 00:47:19,120
כאשר המטרה כאן היא כדי לייעל את האיכות של הקוד,

802
00:47:19,120 --> 00:47:21,280
אלא שגם בעולם האמיתי היא תחלופה סבירה מאוד.

803
00:47:21,280 --> 00:47:25,130
פחות זמן, פחות ביצועים, או להיפך.

804
00:47:25,130 --> 00:47:28,110
אז הנה אנחנו סוף הסוף מקבלים הזדמנות לדבר על תטא.

805
00:47:28,110 --> 00:47:32,830
תטא סימון הוא משהו מדעני מחשב יכולים להעלות בשיחה

806
00:47:32,830 --> 00:47:36,160
כאשר גדול O והאומגה יקרו להיות אותו הדבר.

807
00:47:36,160 --> 00:47:40,160
אתה אומר לתטא באמת לשלוח את ההודעה שזה סוג של כל כך סתום.

808
00:47:40,160 --> 00:47:43,340
לא משנה אם התרחיש הוא טוב או רע, זה של N בריבוע.

809
00:47:43,340 --> 00:47:46,510
אז זה פשוט לא רלוונטי בסיפורים אלה כאן.

810
00:47:46,510 --> 00:47:48,560
מיון ההכנסה הוא אחד האחרון שהסתכלנו,

811
00:47:48,560 --> 00:47:50,830
שבו אני פשוט מכניס את כולם למקום הנכון.

812
00:47:50,830 --> 00:47:54,930
במקרה הטוב מה היה זמן הריצה של מיון הכנסה כפי שראינו אותו כאן?

813
00:47:54,930 --> 00:47:57,250
[התלמיד] המקרה הטוב? >> המקרה הטוב.

814
00:47:57,250 --> 00:48:00,100
>> זה היה n כי במקרה הטוב כולם מסודרים,

815
00:48:00,100 --> 00:48:02,580
וסמי ואף אחד אחר לא באמת היינו צריכים לזוז בכלל.

816
00:48:02,580 --> 00:48:04,610
הם כבר היו במקום הנכון שלהם.

817
00:48:04,610 --> 00:48:08,570
אז סוג ההכנסה במקרה הטוב הוא, במקרה זה, n.

818
00:48:08,570 --> 00:48:12,770
אבל במקרה הגרוע ביותר זה סוג של n בריבוע. למה?

819
00:48:12,770 --> 00:48:16,230
אם הרשימה של בני אדם שלי היא בסדר הפוך,

820
00:48:16,230 --> 00:48:21,260
אני מתחיל ראשון עם המספר 8 ואני מכניס אותו או אותה למיקום הנכון, וזה ממש כאן.

821
00:48:21,260 --> 00:48:25,270
אני סוג של מעבר לצד. החבר 'ה האלה לא ממוינים, הוא או היא מסודרת.

822
00:48:25,270 --> 00:48:28,970
אבל עכשיו אני במקרה שתמצא הבא? >> [תלמיד] 7.

823
00:48:28,970 --> 00:48:31,250
7 במקרה הגרוע ביותר, כי זה בסדר הפוך.

824
00:48:31,250 --> 00:48:34,920
>> אז הנה הם 7. בו 7 לא שייכים? בהחלט מאחורי.

825
00:48:34,920 --> 00:48:39,460
אבל עכשיו 7 בעצם שייכים לא מייד מאחוריי, אבל מאחורי המספר 8,

826
00:48:39,460 --> 00:48:41,880
אז יש לי לומר, "סלח לי, מספר 8, אתה יכול בבקשה לעבור דרך זו

827
00:48:41,880 --> 00:48:44,640
"כדי לפנות מקום ל7?" עכשיו אני נתקל 6.

828
00:48:44,640 --> 00:48:48,530
"אה, סליחה, מספר 8 ומספר 7, אתה יכול לעבור כדי לפנות מקום ל6?"

829
00:48:48,530 --> 00:48:52,360
אז במילים אחרות, עם סוג ההכנסה, למרות שאני לא עושה הרבה תנועה,

830
00:48:52,360 --> 00:48:56,330
אנשים שמאחוריי עושים הרבה יותר עבודה, ושיש לו לעלות פעם מישהו.

831
00:48:56,330 --> 00:48:58,000
זה הולך לעלות זמן המחשב.

832
00:48:58,000 --> 00:49:01,450
אז במקרה של סוג ההכנסה שעדיין סובלים.

833
00:49:01,450 --> 00:49:06,260
אם אתה מתחיל להוסיף את המספר הכולל של צעדים, אנחנו בסופו של דבר פוגעים בגסות n בריבוע

834
00:49:06,260 --> 00:49:11,160
כי החבר 'ה האלה צריכים לפנות מקום לאדם להיות מוכנס בחזרה לאותה רשימה.

835
00:49:11,160 --> 00:49:15,960
ולכן במקרה זה הוא פשוט תטא אינו ישים לסיפור המסוים בהישג יד.

836
00:49:15,960 --> 00:49:21,100
זה כל מה שנחמד וטוב. יש לנו 3 דרכים שונות אלה מדברים על זמן הריצה.

837
00:49:21,100 --> 00:49:26,370
אבל מה זה בעצם אומר במונחים ריאליים, אם אנחנו באמת מנסים לקודד את אלגוריתם?

838
00:49:26,370 --> 00:49:31,620
>> הרשו לי להציע שיש אלגוריתם אפילו טוב יותר שם בחוץ

839
00:49:31,620 --> 00:49:33,740
שעצמו יש כמה פשרות.

840
00:49:33,740 --> 00:49:36,890
אנחנו הולכים לקרוא לזה מיזוג כזה, וזה סוג של האלגוריתם הקסום הזה

841
00:49:36,890 --> 00:49:42,840
שפשוט עובד מהר יותר איכשהו, וזה כל כך קל לבטא, לפחות בpseudocode.

842
00:49:42,840 --> 00:49:46,900
היישום מסוג מיזוג אלגוריתם זה הולך להיות כדלקמן.

843
00:49:46,900 --> 00:49:50,860
כאשר אתה נתון n אלמנטים - מספרי n, n אנשים, מה - ראשית יש לבדוק את השפיות.

844
00:49:50,860 --> 00:49:56,340
אם n הוא פחות מ 2, למזג מיון פשוט מפסיק. הוא חוזר, אם אפשר לומר כך.

845
00:49:56,340 --> 00:50:00,830
למה שתפסיק אם n הוא פחות מ 2? >> [תגובת תלמיד לא נשמעה]

846
00:50:00,830 --> 00:50:04,480
נכון. ושוב, n הוא לא המספר ברשימה, n הוא הגודל של הרשימה.

847
00:50:04,480 --> 00:50:07,660
אם n הוא פחות מ 2, זה אומר שהרשימה שלך היא 1,

848
00:50:07,660 --> 00:50:09,640
לאן אתה מסודר ברור אם זה מספר 1,

849
00:50:09,640 --> 00:50:11,710
או 0, ובמקרה כזה אין מה למיין,

850
00:50:11,710 --> 00:50:13,570
כך שאנחנו צריכים את זה סוג של מקרה בסיס.

851
00:50:13,570 --> 00:50:20,350
אם הרשימה היא כל כך קצרה שיש לך בכלל מה לעשות, ממש לא עושה כלום. Return.

852
00:50:20,350 --> 00:50:25,090
אחרת לסדר את חלקו השמאלי של היסודות, לאחר מכן למיין את החצי הימני של האלמנטים,

853
00:50:25,090 --> 00:50:27,410
לאחר מכן למזג את 2 חצי הממוינים.

854
00:50:27,410 --> 00:50:32,130
>> זה סוג של נראה כמו רמאי קטן שבי אני שואל אותך איך למיין אלמנטים

855
00:50:32,130 --> 00:50:34,900
ואתה אומר לי, "מיין המחצית השמאלית, למיין המחצית הנכונה."

856
00:50:34,900 --> 00:50:37,240
אני כמו, "בסדר. איך למיין את חלקו השמאלי?"

857
00:50:37,240 --> 00:50:40,670
"מיין את המחצית השמאלית של המחצית השמאלית, למיין את המחצית הימנית של מחצית השמאל, ולאחר מכן עשה".

858
00:50:40,670 --> 00:50:44,060
אתה סוג של הגדרת המחזור מה זה אומר למיין,

859
00:50:44,060 --> 00:50:46,790
אבל מסתבר שזה ממש מבריק במקרה זה.

860
00:50:46,790 --> 00:50:50,230
זה לא באמת מעגל הקסמים הזה שלא נגמר

861
00:50:50,230 --> 00:50:52,550
בגלל זה נגמר מתי? >> [תלמיד] בעת שתגיע הדבר 1.

862
00:50:52,550 --> 00:50:54,220
כאשר אתם מגיעים דבר 1.

863
00:50:54,220 --> 00:50:57,850
אז למרות שאתה יכול להתחיל עם 8 אנשים ואני אומר, "מיין במחצית השמאלית של האנשים האלה,

864
00:50:57,850 --> 00:51:00,480
4 האנשים האלה ", אז אני אומר," איך אתה למיין את חלקו השמאלי? "

865
00:51:00,480 --> 00:51:03,450
"טוב, למיין את 2 אנשים כאן". ואז אתה כמו, "בסדר, בסדר".

866
00:51:03,450 --> 00:51:05,520
"איך אתה למיין את המחצית השמאלית של האנשים האלה?"

867
00:51:05,520 --> 00:51:09,040
"רק בערך אדם 1 זה כאן." מה ההתגלות המבריקה עכשיו?

868
00:51:09,040 --> 00:51:13,050
יש לי למיין אדם 1. עשה. אני לא צריך לעשות את כל עבודה.

869
00:51:13,050 --> 00:51:16,580
אבל עכשיו יש לי למיין את האדם הזה, אבל הם אדם אחד, אין מה לעשות.

870
00:51:16,580 --> 00:51:21,490
>> אז כנראה הקסם הוא בשלב השלישי: למזג את החצאים הממוינים.

871
00:51:21,490 --> 00:51:25,770
סוג אז למזג לוקח תובנה המבריקה הזה, שאם אתה שובר בעיה גדולה למטה

872
00:51:25,770 --> 00:51:28,650
ל 2 בעיות קטנות יותר, באופן זהה בגודל

873
00:51:28,650 --> 00:51:32,710
ואז פשוט סוג של דבק יחד את הפתרונים הקטנים יותר בסוף,

874
00:51:32,710 --> 00:51:34,720
אני מציע שאנחנו יכולים לעשות הרבה, [קול קשה] הרבה יותר טוב

875
00:51:34,720 --> 00:51:38,050
מכל מיון בחירה או מיון הכנסה.

876
00:51:38,050 --> 00:51:40,690
אני בעצם כבר התעלמות שבמשך חצי שעה, אבל אני באמת לא יודע מה קורה

877
00:51:40,690 --> 00:51:45,040
בחוץ היום. [זמזום] [שחוק]

878
00:51:45,040 --> 00:51:49,660
אז בואו נראה אם ​​אנחנו יכולים לראות את זה עם קצת עזרה מידידנו רוב באודן.

879
00:51:49,660 --> 00:51:52,810
ישנם 2 צעדים גדולים בתהליך של מיון מיזוג.

880
00:51:52,810 --> 00:51:56,400
ראשית, ברציפות לפצל את הרשימה של כוסות לחצי

881
00:51:56,400 --> 00:51:59,610
עד שיש לנו חבורה של רשימות רק עם 1 הכוס ב.

882
00:51:59,610 --> 00:52:02,150
אל תדאגו אם רשימה מכילה מספר אי זוגי

883
00:52:02,150 --> 00:52:04,830
ואתה לא יכול לעשות חתך נקי לחלוטין ביניהם.

884
00:52:04,830 --> 00:52:08,740
רק באופן שרירותי לבחור לאיזו רשימה שתכלול את הכוס הנוספת פנימה

885
00:52:08,740 --> 00:52:11,320
אז בואו לפצל הרשימות האלה.

886
00:52:12,420 --> 00:52:14,570
עכשיו יש לנו 2 רשימות.

887
00:52:18,930 --> 00:52:20,930
עכשיו יש לנו 4 רשימות.

888
00:52:25,730 --> 00:52:28,740
עכשיו יש לנו 8 רשימות עם כוס אחת בכל רשימה.

889
00:52:28,740 --> 00:52:31,520
אז זהו זה לשלב 1.

890
00:52:31,520 --> 00:52:37,280
עבור שלב 2 שוב ושוב למזג זוגות של רשימות באמצעות אלגוריתם המיזוג שלמדנו בעבר.

891
00:52:37,280 --> 00:52:44,320
מיזוג 108 ו 15 אנחנו בסופו עם הרשימה 15, 108.

892
00:52:45,240 --> 00:52:51,330
מיזוג 50 ו 4 אנחנו בסופו של דבר עם 4, 50.

893
00:52:51,330 --> 00:52:56,950
מיזוג 8 ו 42 שנסיים עם 8, 42.

894
00:52:57,790 --> 00:53:04,360
ומיזוג של 23 ו 16 אנחנו בסופו של דבר עם 16, 23.

895
00:53:04,360 --> 00:53:08,030
עכשיו כל הרשימות שלנו הן בגודל 2.

896
00:53:08,030 --> 00:53:10,980
שים לב שכל אחד 4 הרשימות ממוינת,

897
00:53:10,980 --> 00:53:14,230
כדי שנוכל להתחיל התמזגות זוגות של רשימות שוב.

898
00:53:14,230 --> 00:53:22,150
מיזוג 15 ו 108 ו 4 ו 50 אנחנו לוקחים 1 4, אז 15,

899
00:53:22,150 --> 00:53:26,250
אז 50, אז 108.

900
00:53:26,250 --> 00:53:33,020
מיזוג 8, 42 ו 16, 23 אנחנו לוקחים 8, 16, 1

901
00:53:33,020 --> 00:53:37,170
אז 23, ואז 42.

902
00:53:37,170 --> 00:53:42,490
אז עכשיו יש לנו רק 2 רשימות של גודל 4, כל אחד מהם ממוין.

903
00:53:42,490 --> 00:53:45,940
אז עכשיו אנחנו למזג 2 הרשימות האלה.

904
00:53:45,940 --> 00:53:54,230
ראשית אנחנו לוקחים 4, אז אנחנו לוקחים 8, אז ניקח 15

905
00:53:54,230 --> 00:54:05,280
ו 16 ו 23 ו 42 ו 50 ו108.

906
00:54:05,280 --> 00:54:09,020
ואנחנו נעשינו. עכשיו יש לנו רשימה ממוינת.

907
00:54:09,020 --> 00:54:13,740
>> רוב היה סוג של ניצול של משהו שלא עשו עדיין.

908
00:54:13,740 --> 00:54:16,540
הוא הציע, אבל אנחנו לא ממש נעשה את זה.

909
00:54:16,540 --> 00:54:19,230
הוא עושה משהו פיזי עם כוסות שמרמזות

910
00:54:19,230 --> 00:54:23,680
הוא בילה חלק המשאב מלבד זמן. >> [תלמיד] חלל. >> זה היה חלל.

911
00:54:23,680 --> 00:54:27,360
העובדה שהוא היה זה סוג של שולחן דו רמה שם היה לו מקום כאן

912
00:54:27,360 --> 00:54:31,960
וכאן מקום למעשה רומז שהוא משתמש בכמות הכפול של החלל

913
00:54:31,960 --> 00:54:36,390
כמו כל האלגוריתמים שלנו עד כה - סוג ההכנסה, מיון בועות, או בחירת סוג -

914
00:54:36,390 --> 00:54:40,780
אבל הוא היה מינוף שטח נוסף לזה סוג של דברים לנוע קדימה ואחורה

915
00:54:40,780 --> 00:54:42,600
תוך שמירה על סדר בדברים.

916
00:54:42,600 --> 00:54:47,540
ולמרות שזה מרגיש כאילו הגענו לרשימה ממוינת, שהרגיש כאילו זה לקח זמן.

917
00:54:47,540 --> 00:54:51,060
במציאות, מה שרוב עושה בדיוק את זה אלגוריתם.

918
00:54:51,060 --> 00:54:56,780
הוא לקח תחילה את הבעיה של הגודל n, חלק אותה לחלק שמאלי וחצי נכון.

919
00:54:56,780 --> 00:54:59,380
זה הזמן שבו עבר את הכוסות. ואז הוא חזר על תהליך זה.

920
00:54:59,380 --> 00:55:03,390
הוא חלק 4 לתוך 2 סטים של 2 לכאן וכאן.

921
00:55:03,390 --> 00:55:08,520
ואז הוא חזר על תהליך זה וחלק 2 לתוך 2 סטים של 1 לכל אחת מהכוסות השונות האלה.

922
00:55:08,520 --> 00:55:11,000
וכאן ההזדמנות המבריקה מתעוררת.

923
00:55:11,000 --> 00:55:15,840
בשלב זה בסיפור, רוב היו 8 רשימות של גודל 1,

924
00:55:15,840 --> 00:55:18,860
שכולם מסודרים כבר.

925
00:55:18,860 --> 00:55:20,630
>> אז מה הוא ממשיך לעשות?

926
00:55:20,630 --> 00:55:25,260
Pairwise הוא לקח רשימה זו מסודרת ורשימה ממוינת זו ומזג אותם.

927
00:55:25,260 --> 00:55:28,200
ואז הוא לקח את זה ומזג אותם, אז זה אחד ומזג אותם,

928
00:55:28,200 --> 00:55:30,670
אז זה אחד ומזג אותם.

929
00:55:30,670 --> 00:55:32,390
ואז מה הוא עושה עכשיו?

930
00:55:32,390 --> 00:55:36,580
הוא מחדש התמזג לאחר מכן את הרשימות הגדולות יותר, ואז לחזור מתמזג הרשימות הגדולות יותר.

931
00:55:36,580 --> 00:55:41,170
ואם אתה חושב על זה רק באופן אינטואיטיבי לעכשיו, מה שהוא באמת עושה?

932
00:55:41,170 --> 00:55:45,450
הוא חלק את הבעיה במחצית, במחצית, במחצית, במחצית

933
00:55:45,450 --> 00:55:47,600
על מנת לקבל את הרשימות קטנות אלה סופר.

934
00:55:47,600 --> 00:55:51,290
ואז הוא היה סוג של שילוב כפול, כפול, כפול, כפול.

935
00:55:51,290 --> 00:55:54,120
אז הוא עושה עבודה כפולה כפי שראינו עד כה

936
00:55:54,120 --> 00:55:56,930
עם כל מה שקשור פרד ומשול, אבל לא עניין גדול.

937
00:55:56,930 --> 00:55:59,630
כפליים עבודה היא לא כזה ביג דיל. זה רק גורם קבוע.

938
00:55:59,630 --> 00:56:03,920
וממש כמו ביטוי אריתמטי בעבר, אני רק הולך לחצות את גורמים קבועים

939
00:56:03,920 --> 00:56:10,170
כמו פעמים 2. למי אכפת? אם זה 2 מיליארדים פעמים 2, זה עדיין הרבה שלבים.

940
00:56:10,170 --> 00:56:13,160
אז בשלב מיזוג זה נראה תובנה המרכזית.

941
00:56:13,160 --> 00:56:17,000
בואו נעבור את זה רק לפני בחינה מספרית - אה, זה לא צריך להימשך עוד.

942
00:56:17,000 --> 00:56:22,890
בואו נעבור את זה מבחינה מספרית רק כדי לראות באמת איך זה יתגלגל.

943
00:56:22,890 --> 00:56:25,940
זה בעיקר רק האנימציה של איש קטן ומסכן.

944
00:56:25,940 --> 00:56:27,750
בואו מציעים זאת.

945
00:56:27,750 --> 00:56:31,480
זמן הריצה של מיון מיזוג - אנחנו רק צריכים דרך לדבר על זה.

946
00:56:31,480 --> 00:56:34,380
זה לא מתמטיקה, זה פשוט סוג של דרך תמציתית להביע את עצמנו.

947
00:56:34,380 --> 00:56:39,080
אז T מייצג את הזמן וn מייצג את מה? >> [תלמיד] גודל -

948
00:56:39,080 --> 00:56:41,400
>> [מלאן] גודל הבעיה, את מספר האנשים.

949
00:56:41,400 --> 00:56:45,470
אז אני טוען שהזמן פועל כדי למיין אנשי n הולך להיות 0 כמות הזמן

950
00:56:45,470 --> 00:56:50,290
אם n הוא פחות מ 2, כי אם יש לך 1 כוס או אין כוסות, אין לך מה למיין.

951
00:56:50,290 --> 00:56:55,160
אבל באופן כללי יותר, אני הולך להציע כי הזמן פועל כדי למיין אלמנטי n

952
00:56:55,160 --> 00:56:59,350
הולך להיות הזמן שלוקח כדי למיין את חיצו השמאלי בתוספת המחצית הימנית

953
00:56:59,350 --> 00:57:03,110
תוספת - מה זה נוסף + n? >> [תלמיד] מיון מיזוג.

954
00:57:03,110 --> 00:57:07,260
[מלאן] הם ממש מתמזגים, כי אם יש לך n / 2 אלמנטים כאן

955
00:57:07,260 --> 00:57:11,500
ויש לך n / 2 אלמנטים כאן, כמה זמן לוקח לאחד אותם?

956
00:57:11,500 --> 00:57:15,050
בדיוק כמו רוב, אתה צריך לאזור את זה כאן, אולי לקטוף כאן,

957
00:57:15,050 --> 00:57:17,120
לקטוף כאן, למרוט כאן, למרוט לכאן.

958
00:57:17,120 --> 00:57:19,400
אתה חייב לגעת בי כל אחת מכוסות פעם אחת.

959
00:57:19,400 --> 00:57:22,030
ואם יש 4 כוסות ועוד 4 כוסות, זה 8 כוסות

960
00:57:22,030 --> 00:57:25,200
או אופן כללי יותר, 8 כוסות n.

961
00:57:25,200 --> 00:57:28,470
לכן, שלב המיזוג נוכל לבטא כn,

962
00:57:28,470 --> 00:57:31,330
וזה ממש כרוך במספר הפעמים לשדוד נגע פיזי

963
00:57:31,330 --> 00:57:33,410
אחד מאותם כוסות מפלסטיק.

964
00:57:33,410 --> 00:57:35,850
אז בואו עכשיו נעשה דוגמה שרירותית.

965
00:57:35,850 --> 00:57:41,850
אם יש 16 כוסות, מה זמן הריצה של מיון, באמצעות האלגוריתם של רוב, 16 כוסות?

966
00:57:41,850 --> 00:57:44,710
זה פי 2 מכמות הזמן שלוקח למיין 8 כוסות

967
00:57:44,710 --> 00:57:46,920
בגלל שיש לנו 8 כוסות כאן, 8 כוסות כאן.

968
00:57:46,920 --> 00:57:51,520
אני לא יודע כמה זמן זה לוקח, אז אנחנו מכלילים אותו כT לרגע.

969
00:57:51,520 --> 00:57:53,320
מי יודע מה זה?

970
00:57:53,320 --> 00:57:58,990
אבל עכשיו אני יכול למיין של רקורסיבי או שוב ושוב שואל את אותה השאלה.

971
00:57:58,990 --> 00:58:01,920
כמה זמן לוקח למיין 8 כוסות?

972
00:58:01,920 --> 00:58:07,030
8 כוסות אני עומד לומר לוקחת את כמות הזמן שלוקח למיין 4 כוסות ועוד 4 כוסות,

973
00:58:07,030 --> 00:58:08,880
אז התמזגותם יחד.

974
00:58:08,880 --> 00:58:13,080
בסדר. אנחנו נכנסים למחזור כבר. כמה זמן זה לוקח כדי למיין 4 כוסות?

975
00:58:13,080 --> 00:58:19,150
הזמן שלוקח למיון 4 כוסות הוא 2 כוסות בתוספת 2 כוסות מיון תוספת תהליך המיזוג.

976
00:58:19,150 --> 00:58:21,440
בסדר. כמה זמן זה לוקח כדי למיין 2 כוסות?

977
00:58:21,440 --> 00:58:26,290
2 כוסות היא כמות הזמן שלוקח למיין 1 כוס בתוספת הזמן שלוקח למיין עוד כוס

978
00:58:26,290 --> 00:58:29,040
עוד הסכום של זמן שלוקח למיזוג, וזה רק 2.

979
00:58:29,040 --> 00:58:33,340
>> בסדר. השאלה אחרונה. כמה זמן זה לוקח כדי למיין 1 כוס?

980
00:58:33,340 --> 00:58:37,260
הנה מקרה הבסיס שבו צפו היינו נפגעתי קודם לכן.

981
00:58:37,260 --> 00:58:42,250
העובדה שהיא לא לוקחת עבודה כלשהי כדי למיין הקטן ביותר של הבעיות

982
00:58:42,250 --> 00:58:44,120
אמצעים שעכשיו, סוג של סגנון בית הספר יסודי,

983
00:58:44,120 --> 00:58:46,460
אנחנו יכולים פשוט ללכת להתחיל חיבור המספרים האלה בחזרה פנימה

984
00:58:46,460 --> 00:58:50,630
כעת אנו יודעים מה T של 1 הוא, ולכן אני יכול לחבר 0 עבור T של 1.

985
00:58:50,630 --> 00:58:54,420
שייתן לי את התשובה לT של 2, אשר אז יכול לחבר עד גבוה.

986
00:58:54,420 --> 00:58:56,930
זה ייתן לי T של 4, שבו אני יכול לחבר עד גבוה.

987
00:58:56,930 --> 00:58:58,920
זה ייתן לי T של 8, שבו אני יכול לחבר עד גבוה.

988
00:58:58,920 --> 00:59:04,330
אם באמת הייתי עושה את המתמטיקה שעל ידי חיבור בתשובות האלה ו,

989
00:59:04,330 --> 00:59:08,590
אז אני מקבל T של 16 הוא 64.

990
00:59:08,590 --> 00:59:12,090
ומה 64 מייצגים?

991
00:59:12,090 --> 00:59:15,700
אם T הוא 16, כן, זה פעמים 16 4.

992
00:59:15,700 --> 00:59:20,120
אז אני טוען עכשיו שזמן הריצה של הדבר הזה שנקרא למזג מיון -

993
00:59:20,120 --> 00:59:22,590
וזה הולך להיות הכי מפואר מאלה שראינו עד כה -

994
00:59:22,590 --> 00:59:26,160
הולך להיות שם n log n

995
00:59:26,160 --> 00:59:31,140
כי כמה פעמים יכול לשדוד התפצל חבורה שלמה של כוסות בחצי? היכנס n.

996
00:59:31,140 --> 00:59:34,370
זה אותו כדוגמא ספר טלפונים, זה אותו כדוגמא עצמית הספירה.

997
00:59:34,370 --> 00:59:36,380
>> כמה פעמים אתה יכול לחלק משהו בחצי?

998
00:59:36,380 --> 00:59:38,410
עם זאת, יש צעד מיזוג זה.

999
00:59:38,410 --> 00:59:42,920
ייתכן שתצטרך לחלק את הכוסות לתוך חצי שוב ושוב ושוב,

1000
00:59:42,920 --> 00:59:45,640
אבל בכל פעם שאתה הולך צריכה להתמזג.

1001
00:59:45,640 --> 00:59:48,270
ואנחנו אמרנו מוקדם יותר כי מיזוג כוסות n נוקט צעדי n

1002
00:59:48,270 --> 00:59:52,060
כי יש לך לתלוש כוס, לתלוש כוס, ואתה צריך לגעת בכל כוס אחת,

1003
00:59:52,060 --> 00:59:53,510
בדיוק כמו רוב עשה.

1004
00:59:53,510 --> 00:59:59,430
אז אם אנחנו עושים משהו יומן n פעמים ואנחנו עושים דברי n בכל אחת מהחזרות האלה,

1005
00:59:59,430 --> 01:00:03,090
כל אחד מhalvings האלה, יש לנו n זמני log n.

1006
01:00:03,090 --> 01:00:07,220
אז אם נחבר 16 בדוגמה זו, 16 פעמים להיכנס של 16 -

1007
01:00:07,220 --> 01:00:10,600
לא לדאוג למה זה מקרה לעת עתה כי אני לא ציירתי את הבסיס -

1008
01:00:10,600 --> 01:00:16,100
אבל יומן של בסיס 2 של 16 הוא 4, 16 פעמים 4 הן 64.

1009
01:00:16,100 --> 01:00:22,350
אבל לעומת זאת, אם הייתי משתמש במיון בועות או מיון מיון או החדרת בחירה עם 16 מספרים,

1010
01:00:22,350 --> 01:00:26,420
מה יהיה זמן הריצה היה אם n הוא 16?

1011
01:00:26,420 --> 01:00:33,310
זה יהיה 16 בריבוע, שהוא 256, גם אם לא עקב אחרי כל המתמטיקה די בי,

1012
01:00:33,310 --> 01:00:38,390
256 הם יותר גדולים מ 64. זה באמת takeaway הקסום כאן.

1013
01:00:38,390 --> 01:00:41,990
ולהבין שעובד דרך זו בדוגמאות קטנות כרצונכם על pset

1014
01:00:41,990 --> 01:00:44,260
עושה את הכל הרבה יותר אינטואיטיבי.

1015
01:00:44,260 --> 01:00:49,070
אבל מה זה באמת אומר במונחים של התחושה של אלגוריתם זה הוא זה:

1016
01:00:49,070 --> 01:00:54,520
אם אנחנו באמת מסתכלים על סוג המיזוג כאן - תן לי למשוך אותו בחלון זה כאן -

1017
01:00:54,520 --> 01:00:58,560
זו היא דוגמה מעט שונה לפיה יש לנו את כל 3 של אלגוריתמים אלה -

1018
01:00:58,560 --> 01:01:01,440
בועה, בחירה, ולמזג - רק לצד זה.

1019
01:01:01,440 --> 01:01:03,740
>> כולם התחילו עם ברים אקראיים, וזה טוב.

1020
01:01:03,740 --> 01:01:06,240
לאף אחד אין יתרון מהותי על פני אחר.

1021
01:01:06,240 --> 01:01:09,500
אני הולך ברגע לחץ על כל אחד מאלה אנימציות - התחל, לחץ על התחל, התחל -

1022
01:01:09,500 --> 01:01:13,270
מהר ככל שאני יכול, כדי ש, בערך, כולן מתחיל באותו הזמן,

1023
01:01:13,270 --> 01:01:17,450
ובואו נחשוב שהמקרה הגרוע של מיון בועות פועלים זמן מה? >> [התלמיד] N בריבוע.

1024
01:01:17,450 --> 01:01:21,560
N בריבוע. המקרה הגרוע ביותר של מיון הבחירה זמן הריצה הוא? N בריבוע.

1025
01:01:21,560 --> 01:01:25,150
ומעין מיזוג היא ככל הנראה - גם אם אתה לא ממש מבין את כל המתמטיקה עכשיו,

1026
01:01:25,150 --> 01:01:30,610
זה יהפוך הרבה יותר אינטואיטיבי לאורך זמן - כלומר, אנחנו טוענים, n הזמנים log n.

1027
01:01:30,610 --> 01:01:35,210
ובגלל יומן n הוא בהחלט פחות מ n פעם יש לנו מספרים גדולים,

1028
01:01:35,210 --> 01:01:40,230
n זמני היומן n הוא קטן מ n פעמי n או n בריבוע.

1029
01:01:40,230 --> 01:01:44,410
אז מה זה בעצם מרגיש להיות אלגוריתם טוב יותר במונחים של זמן ריצה,

1030
01:01:44,410 --> 01:01:50,380
זמני יומן n n לעומת n בריבוע? הנה אנחנו מתחילים. קליק, קליק, קליק.

1031
01:01:55,690 --> 01:01:58,650
>> זה מה שזה אומר להשתמש במשהו כמו סוג המיזוג.

1032
01:01:58,650 --> 01:02:01,680
יש לנו כרגע. בואו לראות מה קורה כאן.

1033
01:02:09,440 --> 01:02:12,440
[מגחך] כסף של מי הוא על מיון בועות?

1034
01:02:14,960 --> 01:02:16,730
זה לא תלוי בקלט לפעמים.

1035
01:02:16,730 --> 01:02:18,120
בואו נראים.

1036
01:02:18,120 --> 01:02:23,320
נו באמת. זה מרגיש כאילו הוא תופס. >> [תלמיד] עבור, מיון בועות!

1037
01:02:23,320 --> 01:02:27,370
[סטודנטי ממלמל]

1038
01:02:27,370 --> 01:02:29,120
[מלאן] כן, כן.

1039
01:02:29,120 --> 01:02:34,520
[סטודנטים הממלמלות] קדימה, קדימה, קדימה!

1040
01:02:37,210 --> 01:02:40,450
[כל מריע] [מחיאות כפות]

1041
01:02:40,450 --> 01:02:46,240
אז עכשיו עם 1 ההדגמה אחרונה, סופית, אם זה קצת מסובך לקלוט את המתמטיקה

1042
01:02:46,240 --> 01:02:49,280
או סוג של ההדמיה לשם, אתה ממש יכול לשמוע את מהירויות

1043
01:02:49,280 --> 01:02:51,000
של אלגוריתמים שונים בצורה שונה.

1044
01:02:51,000 --> 01:02:53,900
זה מישהו שממש עשה אנימצית מקורבים נשמעים

1045
01:02:53,900 --> 01:02:56,980
בתהליך של החלפה והגובה של הסורגים.

1046
01:02:56,980 --> 01:03:00,440
כפי שנראים כאן, יש עוד כמה אלגוריתמי מיון שם בחוץ, כי אנשים שחשבו עליו.

1047
01:03:00,440 --> 01:03:03,660
ראשון זה הולך להיות סוג ההכנסה, וזה יהיה לטוס דרך

1048
01:03:03,660 --> 01:03:07,090
ולתת לך תחושה נשמעת של איך זה עובד אלגוריתמים השונים.

1049
01:03:07,090 --> 01:03:09,080
כאן מעין כניסה.

1050
01:03:09,080 --> 01:03:18,410
[צפצוף אלקטרוני]

1051
01:03:18,410 --> 01:03:20,730
[מלאן] מעין בועה.

1052
01:03:20,730 --> 01:03:46,850
[מהר צפצוף אלקטרוני]

1053
01:03:46,850 --> 01:03:48,950
[מלאן] מיון בחירה.

1054
01:03:48,950 --> 01:04:03,580
[מהר צפצוף אלקטרוני]

1055
01:04:03,580 --> 01:04:05,770
[מלאן] מיון מיזוג.

1056
01:04:05,770 --> 01:04:17,270
[צפצוף אלקטרוני]

1057
01:04:17,270 --> 01:04:20,180
[צפצוף מאט] [שחוק]

1058
01:04:20,180 --> 01:04:22,590
[מלאן] סוג Gnome.

1059
01:04:22,590 --> 01:04:38,580
[צפצוף אלקטרוני]

1060
01:04:39,740 --> 01:04:46,150
>> זה CS50. ניראה אותך בשבוע הבא. [מחיאות כפות ומריעות]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]