1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> SPEAKER: בסדר, זה CS50.

3
00:00:14,910 --> 00:00:19,020
זהו סופו של שבוע שלושה, ואם
אתה לא ניצל כבר,

4
00:00:19,020 --> 00:00:21,790
יודע שלא תהיה ארוחת צהריים
ביום שישי הקרוב כרגיל, שבו

5
00:00:21,790 --> 00:00:25,430
אתה יכול ליהנות משיחה טובה
ומזון באש וקרח

6
00:00:25,430 --> 00:00:27,980
עם חלק מCS50 של
צוות וחברים לכיתה.

7
00:00:27,980 --> 00:00:30,170
הראש לכתובת אתר זו כאן.

8
00:00:30,170 --> 00:00:33,420
>> עכשיו אתם אולי זוכרים, או שאתה
ניתן עד מהרה הכיר,

9
00:00:33,420 --> 00:00:35,970
את הדברים האלה כאן, ש
מקבלים בסוף

10
00:00:35,970 --> 00:00:37,850
של הסמסטר לשיעורים רבים.

11
00:00:37,850 --> 00:00:40,870
ספרים כחולים בחינה מה שנקרא, שבו
אתה כותב את התשובות שלך לבחינות.

12
00:00:40,870 --> 00:00:44,240
עכשיו יש לי כאן 26 כזה
ספרים כחולים, בכל אחד מהם

13
00:00:44,240 --> 00:00:47,580
נכתב שם, דרך ז ו
אכן השמות הם כל כך פשוט,

14
00:00:47,580 --> 00:00:50,490
דרך ז ואחד
המטרות בהישג היד היום

15
00:00:50,490 --> 00:00:53,910
הולך להיות להמשיך את מה ש
התחלנו ביום שני, שהוא לא

16
00:00:53,910 --> 00:00:57,830
כל כך הרבה מסתכל על קוד, אבל באמת
מסתכל על רעיונות ופתרון בעיות.

17
00:00:57,830 --> 00:01:00,170
אחת מהמטרות ו
הבטחות של קורס זה

18
00:01:00,170 --> 00:01:02,985
הוא ללמד אותך לחשוב יותר
בזהירות, יותר באופן שיטתי,

19
00:01:02,985 --> 00:01:05,400
וכדי לפתור את הבעיות בצורה יעילה יותר.

20
00:01:05,400 --> 00:01:09,526
ואכן, אנחנו יכולים לעשות את זה באמת
בלי לגעת שורת קוד.

21
00:01:09,526 --> 00:01:12,150
אז יש לי כמה פילים
עד כאן היום, כתום וכחול,

22
00:01:12,150 --> 00:01:15,780
אם היינו יכול לקבל מתנדב אחד,
אולי ממקום מרוחק יותר מהרגיל.

23
00:01:15,780 --> 00:01:18,070
מה דעתך על שם, בואו למטה.

24
00:01:18,070 --> 00:01:24,180
מטרתה הולכת להיות ל
לעזור בתוספת לנהל בחינה זו כאן.

25
00:01:24,180 --> 00:01:24,935
מה שמך?

26
00:01:24,935 --> 00:01:25,768
>> קהל: מרי בת'.

27
00:01:25,768 --> 00:01:27,560
דובר: מרי בת, בחייך עד.

28
00:01:27,560 --> 00:01:29,560
תן לי את המיקרופון כאן בשבילך.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
נחמד לפגוש אותך.

31
00:01:32,880 --> 00:01:34,005
>> קהל: נחמד לפגוש אותך.

32
00:01:34,005 --> 00:01:36,790
SPEAKER: בסדר, אז אני צריך
כאן ספרים כחולים עד Z,

33
00:01:36,790 --> 00:01:41,680
ואני הולך להעמיד פנים ש
יש לי אחד מהתלמידים,

34
00:01:41,680 --> 00:01:45,770
והם באים באופן אקראי במידה מה
בסוף בלוק בחינה שלוש שעות ביממה,

35
00:01:45,770 --> 00:01:49,400
כך הם מגיעים לאיזה
כדי למחצה אקראי כמו זה.

36
00:01:49,400 --> 00:01:54,510
עכשיו התפקיד שלך ברגע שקורה
לbe-- זה בעצם איך שהם מקבלים

37
00:01:54,510 --> 00:01:56,820
פנה בסוף
הכיתה, סביר להניח.

38
00:01:56,820 --> 00:02:01,120
התפקיד שלך עכשיו הוא הולך להיות, די
פשוט, כדי למיין את הספרים הכחולים הללו בשבילנו

39
00:02:01,120 --> 00:02:05,220
מדרך Z.

40
00:02:05,220 --> 00:02:08,400
>> קהל: אה, זה הוא
הולך לקחת לנצח.

41
00:02:08,400 --> 00:02:13,747
>> דובר: ואנחנו נצפה
כמו שאתה עושה את זה, אין לחץ.

42
00:02:13,747 --> 00:02:15,330
קהל: לא, שום לחץ או משהו.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> דובר: ובשביל כיף,
בואו נשים את שעון עצר.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> קהל: כל כך הרבה כל כך הרבה כיף כיף,.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> דובר: אני יכול להחזיק את המיקרופון בשבילך.

49
00:02:38,574 --> 00:02:40,240
בסדר, יש לנו רק הכפלנו את המהירות שלנו.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
אז בינתיים, תן לי להציג את מה ש
הולך להיות השאלה עבור מרי בת

52
00:02:49,060 --> 00:02:51,540
זה מה שהיא עושה, איך היא
היא הולכת על הפתרון הזה?

53
00:02:51,540 --> 00:02:54,040
ואכן, ייתכן שאין לך
אי פעם חשב על משהו

54
00:02:54,040 --> 00:02:57,440
כל כך פשוט כפי שכאשר אתה בוחר
עד 26 ספרים כמו זה,

55
00:02:57,440 --> 00:02:59,350
שיש לי טבעי
הזמנה אליהם.

56
00:02:59,350 --> 00:03:01,335
מהו התהליך
כי אתה בעצם להשתמש?

57
00:03:01,335 --> 00:03:03,770
האם זה מקרית למדי רק
לקטוף את הראשון שאתה רואה

58
00:03:03,770 --> 00:03:05,250
ולשים אותו במקום שלה?

59
00:03:05,250 --> 00:03:09,680
האם אתה להזיז את הידיים שלך בסיבוב ראשון
מחפש אז מחפש B?

60
00:03:09,680 --> 00:03:11,722
האם אתה תסתכל על
שניהם זה לצד זה

61
00:03:11,722 --> 00:03:14,680
ורק אומר, רגע, רגע, זה
לא בסדר, ולאחר מכן להחליף את הסדר?

62
00:03:14,680 --> 00:03:16,960
אנחנו כבר ראינו ביום שני
שיש מספר דרכים

63
00:03:16,960 --> 00:03:22,140
שבו אנחנו יכולים לעשות את זה, ו
אכן כפי שאנו קרובים לסוף כאן,

64
00:03:22,140 --> 00:03:26,360
הייתי לוקח את הפתק אולי
ממה מרי בת עושה.

65
00:03:26,360 --> 00:03:30,040
יש לנו כמה ערימות נראה,
גדול אחד, שלוש קטנים יותר.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> קהל: אני מזמין אותם
כאשר אני מוצא את שני מכתבים

68
00:03:36,415 --> 00:03:39,540
כי אני יודע שהם יחד ברצף,
שמתי אותם יחד, כך שאני לא

69
00:03:39,540 --> 00:03:42,915
צריך לדאוג על שמירה
אחר שורה שלמה של ספרים.

70
00:03:42,915 --> 00:03:45,706
זה פשוט, אה, הוא ראשון,
יש לי ערימה זה כאן.

71
00:03:45,706 --> 00:03:47,580
דובר: אז, כמעט כמו
חלקי הפאזל ש

72
00:03:47,580 --> 00:03:49,860
יש לה את הצורה הנכונה ל
להתאים את אחד עם השני.

73
00:03:49,860 --> 00:03:51,026
קהל: די הרבה, כן.

74
00:03:51,026 --> 00:03:55,320
דובר: אישור, מצוין.

75
00:03:55,320 --> 00:03:59,850
ועכשיו כל אחד מאלה
ערימות ממוינות ככל הנראה?

76
00:03:59,850 --> 00:04:00,990
>> קהל: כן.

77
00:04:00,990 --> 00:04:09,900
>> SPEAKER: בסדר, באמצעות Z. כל
נכון, מזל טוב, אתה עשית את זה.

78
00:04:09,900 --> 00:04:11,461
יש לך הבחירה שלך.

79
00:04:11,461 --> 00:04:11,960
כחול?

80
00:04:11,960 --> 00:04:13,530
בסדר, תודה לך על זה.

81
00:04:13,530 --> 00:04:16,679
אז מרי בת לא להציע
מה הגישה שלה היה,

82
00:04:16,679 --> 00:04:19,720
אבל מה היא גישה אחרת איך אתה
אולי ללכת על מיון את הדברים האלה?

83
00:04:19,720 --> 00:04:21,130
מה היית עושה?

84
00:04:21,130 --> 00:04:24,060
השיא כדי לנצח היה
דקה אחת ו50 או כך שניות,

85
00:04:24,060 --> 00:04:26,039
בתוספת לאלה ששכחתי לספור.

86
00:04:26,039 --> 00:04:27,080
מה היית עושה?

87
00:04:27,080 --> 00:04:27,579
כן?

88
00:04:27,579 --> 00:04:28,735
קהל: קח את הערימה.

89
00:04:28,735 --> 00:04:29,776
תתחיל מההתחלה.

90
00:04:29,776 --> 00:04:32,284
בדקו את הניירות שלך.

91
00:04:32,284 --> 00:04:36,586
ואם הראש אחד הוא גבוה יותר
מ, אולי, שהם,

92
00:04:36,586 --> 00:04:38,980
התחתון הוא
גבוה יותר, ולאחר מכן לעבור אותם.

93
00:04:38,980 --> 00:04:41,300
>> דובר: אוקיי, אז מתחיל
בחלק העליון והחלק התחתון,

94
00:04:41,300 --> 00:04:43,716
ולאחר מכן לעבוד בדרך שלך
כמו פנימה ש, החלפתם?

95
00:04:43,716 --> 00:04:46,580
אוקיי, אז קצת דומה
ברוחו למיון בועות,

96
00:04:46,580 --> 00:04:49,160
אבל בחירה קיצונית
לא הזוגות הסמוכים.

97
00:04:49,160 --> 00:04:52,080
אבל הקצר שלו הוא שיש
בוודאי כמה דרכים שונות

98
00:04:52,080 --> 00:04:54,210
אנחנו יכולים לעשות את זה, ו
בכנות, אני חושב שאתה סוג של

99
00:04:54,210 --> 00:04:55,700
אימץ כמה גישות, נכון?

100
00:04:55,700 --> 00:05:00,567
אתה עשית סוג של ארבע ערימות ממוינות, ו
אז ביעילות מיזג אותם יחד.

101
00:05:00,567 --> 00:05:02,650
וזה, מעז לומר, אחר
טכניקה לחלוטין.

102
00:05:02,650 --> 00:05:06,950
אתה לא מתייחס לזה כערימה אחת גדולה,
אתה חילק את הבעיה לארבעה quads,

103
00:05:06,950 --> 00:05:09,820
אם תרצה, ואז איכשהו
מיזג אותם בסופו של הדבר.

104
00:05:09,820 --> 00:05:13,410
>> אז בואו נשקול, סופו של דבר,
איך עוד אנחנו יכולים לעשות את זה.

105
00:05:13,410 --> 00:05:15,860
אנחנו באופן רשמי את הרעיון
של בועת סוג הפעם האחרונה,

106
00:05:15,860 --> 00:05:18,780
וזכירת מיון בועות הייתה
אלגוריתם שדמיינו

107
00:05:18,780 --> 00:05:22,640
עם שמונה חבריו לכיתה שלך עד כאן,
לכאורה מסודרים באופן אקראי בהתחלה.

108
00:05:22,640 --> 00:05:26,110
ואז אנחנו החלטנו pairwise, אם
שני אלמנטים מקולקלים,

109
00:05:26,110 --> 00:05:26,950
פשוט להחליף אותם.

110
00:05:26,950 --> 00:05:28,930
אז ארבעה ושתיים
כמובן שלא לפי סדר,

111
00:05:28,930 --> 00:05:31,080
ולכן שני חברים לכיתה אלה
החליף תפקידים.

112
00:05:31,080 --> 00:05:35,390
ואז אנחנו חוזרים עם ארבעה ושש,
לאחר מכן שש ושמונה, בכל איטרציה,

113
00:05:35,390 --> 00:05:36,980
נע לימין.

114
00:05:36,980 --> 00:05:42,590
>> כך שבהתחשב בשמונה בני אדם, כמה pairwise
השוואות עשו את תוך כדי הליכה מ

115
00:05:42,590 --> 00:05:45,220
משמאל לימין באיטרציה אחת כזו?

116
00:05:45,220 --> 00:05:48,410
כמה השוואות?

117
00:05:48,410 --> 00:05:49,197
שבע, נכון?

118
00:05:49,197 --> 00:05:51,405
כי אם יש שמונה
אנשים אבל יש לך הזוג

119
00:05:51,405 --> 00:05:53,880
שלהם ואתה לא מפסיקים לזוז
אחד לקפוץ לימין,

120
00:05:53,880 --> 00:05:56,060
אתה לא הולך לקבל שמונה
השוואות, כי אתה לא יכול להשוות

121
00:05:56,060 --> 00:05:59,226
אלמנט נגד עצמו, או שזה היית
רק חסר טעם, אז יש לך שבע.

122
00:05:59,226 --> 00:06:01,290
או באופן כללי יותר, אם
יש לנו n אנשים, אנחנו

123
00:06:01,290 --> 00:06:04,300
לעשות n מינוס 1 השוואות
עם מיון בועות.

124
00:06:04,300 --> 00:06:08,150
>> אז בואו נשקול כעת כמה טוב או
בועה רעה סוג בעצם הייתה, ולנסות

125
00:06:08,150 --> 00:06:13,570
לתת לעצמנו את אוצר המילים עם
אשר לאלגוריתמי ביקורת כמו זו,

126
00:06:13,570 --> 00:06:14,430
ובקרוב שלנו.

127
00:06:14,430 --> 00:06:16,970
אז לעבור תחילה דרך
מיון בועות, בפעם הראשונה

128
00:06:16,970 --> 00:06:20,909
הלכתי ברגל משמאל לימין על פני
שלב, לקח לי n מינוס 1 השוואות.

129
00:06:20,909 --> 00:06:22,950
וזה הולך להיות שלי
יחידת המידה, נכון?

130
00:06:22,950 --> 00:06:26,170
אני היה סוג של דיבור ומטייל,
קצת מהיר, איטי במקצת,

131
00:06:26,170 --> 00:06:29,300
כך לספור את המספר שלי משניות
לא במיוחד לספר,

132
00:06:29,300 --> 00:06:32,260
אבל לספור את מספר
פעולות שעשיתי ביום שני,

133
00:06:32,260 --> 00:06:35,900
השוואה בין שני אנשים, שמרגיש
כמו יחידה נחמדה של מדד.

134
00:06:35,900 --> 00:06:40,980
>> אז n מינוס 1 על שלבים בפעם הראשונה,
אבל אז מה שקרה אחרי זה?

135
00:06:40,980 --> 00:06:46,610
מה הפוך אחד ממעבר אחד
באמצעות רשימה אחרת לא ממוינת?

136
00:06:46,610 --> 00:06:49,840
מה אתה יכול לספר לי על האלמנט
שהייתה כל הדרך לשם?

137
00:06:49,840 --> 00:06:51,300
כן?

138
00:06:51,300 --> 00:06:52,870
זה היה האלמנט הגדול ביותר, נכון?

139
00:06:52,870 --> 00:06:55,710
מספר שמונה, למרות שהיא
התחלתי כאן, בכל פעם שאני

140
00:06:55,710 --> 00:06:57,860
לעומתה נגד
השכן, היא שמרה

141
00:06:57,860 --> 00:07:00,480
מבעבע מימין
צד של הרשימה.

142
00:07:00,480 --> 00:07:02,710
ואכן, זה המקום שבי
האלגוריתם מקבל את שמו.

143
00:07:02,710 --> 00:07:07,630
>> עכשיו לפי ההיגיון הזה, כמה השוואות
צריך אני עושה בפעם השנייה

144
00:07:07,630 --> 00:07:09,800
אני עושה לעבור כי משמאל לימין?

145
00:07:09,800 --> 00:07:10,730
n מינוס 2, נכון?

146
00:07:10,730 --> 00:07:14,297
זה היה פשוט מבזבז את הזמן שלי, אם אני
לשמור על השוואת שמונה נגד מישהו

147
00:07:14,297 --> 00:07:16,630
אחר משום שאנו כבר יודעים
היא הייתה במקום הנכון.

148
00:07:16,630 --> 00:07:19,760
אז זה קצת
אופטימיזציה, כך לעבור הבא

149
00:07:19,760 --> 00:07:23,899
הוא הולך להיות בתוספת n מינוס שני שלבים,
כאשר n הוא מספר האנשים.

150
00:07:23,899 --> 00:07:26,940
עכשיו אתה סוג של יכול להסיק, אפילו
אם אתה לא מדען מחשב,

151
00:07:26,940 --> 00:07:27,680
איך זה מסתיים.

152
00:07:27,680 --> 00:07:31,259
בסופו של אלגוריתם זה, ככל הנראה
יש לך רק השוואה אחד עזב.

153
00:07:31,259 --> 00:07:33,800
אתה צריך לתקן את סוג של
תחילתה של הרשימה במקרה שני

154
00:07:33,800 --> 00:07:36,540
ואחד מקולקל
וצריך להיות אחד ושני,

155
00:07:36,540 --> 00:07:40,330
כך זה תחתית החוצה ב
בתוספת 1 השוואה סופית.

156
00:07:40,330 --> 00:07:44,500
>> עכשיו הנקודה, הנקודה, נקודת סוג של גלים זה
ידיים בחלק מהפרטים העסיסיים,

157
00:07:44,500 --> 00:07:46,452
אבל בואו פשוט להמשיך ולפשט.

158
00:07:46,452 --> 00:07:48,660
אם אתה זוכר מגבוה
בית ספר, בכנות, הרבה מכם

159
00:07:48,660 --> 00:07:50,340
היו לי ספרי מתמטיקה שהיו לי
גיליון לרמות קטן

160
00:07:50,340 --> 00:07:52,550
על העטיפה או הקדמיות
כיסוי אחורי שהראה לך

161
00:07:52,550 --> 00:07:56,400
סיכומים מה סדרה כמו
זה הוסיף את סופו של דבר ל.

162
00:07:56,400 --> 00:07:59,600
במקרה הכללי, אם יש לך
משתנה כמו n, ואכן זה אחד,

163
00:07:59,600 --> 00:08:01,634
אם אסתכל עליך
ספר מתמטיקה בית ספר ישן,

164
00:08:01,634 --> 00:08:04,050
היית רואה שזה בעצם
מוסיף עד לסכום זה כאן,

165
00:08:04,050 --> 00:08:07,970
n פעמים n מינוס 1 כל חלקי 2.

166
00:08:07,970 --> 00:08:11,172
אז לעת עתה תן לי רק קובעים
זה נכון, כל כך בקפיצה של אמונה,

167
00:08:11,172 --> 00:08:12,880
זה מה שזה מסכם
עד, ושיכולנו

168
00:08:12,880 --> 00:08:14,341
להוכיח כי במקרה כללי יותר.

169
00:08:14,341 --> 00:08:15,590
אבל עכשיו בואו נרחיב את זה.

170
00:08:15,590 --> 00:08:19,920
אז בואו נכפיל את זה, אז זה
n בריבוע, מינוס n, כל חלקי 2.

171
00:08:19,920 --> 00:08:23,200
זה באמת בריבוע n,
מחולק ב2, מינוס n מעל 2,

172
00:08:23,200 --> 00:08:25,010
כך שכל מה שנחמד ומעניין.

173
00:08:25,010 --> 00:08:27,060
אבל מה קורה אם אנחנו
עכשיו התוספת ערך?

174
00:08:27,060 --> 00:08:29,724
נניח שלא היו לי שמונה
אנשים, אבל אומרים מיליון.

175
00:08:29,724 --> 00:08:31,890
ומיליון רק בגלל ש
זה מספר די גדול,

176
00:08:31,890 --> 00:08:34,039
בואו נחבר את זה ולראות מה קורה.

177
00:08:34,039 --> 00:08:39,039
אז אם אני מחבר את מיליון לנוסחה ש
אני הולך לקבל מיליון בריבוע,

178
00:08:39,039 --> 00:08:42,868
מחולק ב2, מינוס
מיליון, מחולקים ב2.

179
00:08:42,868 --> 00:08:44,159
עכשיו מה שהולך להיות שווה?

180
00:08:44,159 --> 00:08:47,354
אז 500 מיליארדים, מינוס 500,000.

181
00:08:47,354 --> 00:08:49,270
ואם אני עושה
מתמטיקה ש, אמצעים ש

182
00:08:49,270 --> 00:08:53,920
כי מיון מיליון
אנשים עם מיון הבועות

183
00:08:53,920 --> 00:09:01,800
אולי תיקח אותי 499999500000
צעדים או השוואות בסופו של הדבר,

184
00:09:01,800 --> 00:09:02,900
אנחנו רק אקסטרפולציה.

185
00:09:02,900 --> 00:09:06,860
>> זה מרגיש די איטי, אבל בכנות
מדידת קלט אחד מסוים

186
00:09:06,860 --> 00:09:09,160
כמו זה, הוא לא כל הסיפור ש.

187
00:09:09,160 --> 00:09:14,050
אבל אכן זה מצביע על כך שכפי שn
מקבל גדול יותר ויותר, אלגוריתם זה

188
00:09:14,050 --> 00:09:16,280
סוג של מרגיש ויותר גרועים
באמת גרוע, או שאתה

189
00:09:16,280 --> 00:09:20,450
מתחיל להרגיש את הכאב של ש
exponentiation, n כי בריבוע,

190
00:09:20,450 --> 00:09:21,770
אשר מוסיף עד די מהר.

191
00:09:21,770 --> 00:09:25,340
ופרט זה הוא לא
איבד באנשים, בעובדה

192
00:09:25,340 --> 00:09:29,640
לפני כמה שנות סנטור מסוים שהיה
קמפיין, התיישב לראיון

193
00:09:29,640 --> 00:09:32,180
עם אריק של גוגל
שמידט, מנכ"ל באותה העת,

194
00:09:32,180 --> 00:09:36,380
והיה לערער בשאלה
ממש כמו שאנחנו בוחנים היום.

195
00:09:36,380 --> 00:09:38,468
בואו נסתכל.

196
00:09:38,468 --> 00:09:45,280
>> [וידאו השמעה]

197
00:09:45,280 --> 00:09:48,560
>> -Senator, שאתה כאן
בגוגל, ואני אוהב

198
00:09:48,560 --> 00:09:53,382
לחשוב על הנשיאות
כראיון עבודה.

199
00:09:53,382 --> 00:09:56,434
עכשיו, זה קשה להשגה
עבודה כנשיא,

200
00:09:56,434 --> 00:09:58,100
ושאתם עוברים הקשיים עכשיו.

201
00:09:58,100 --> 00:10:01,860
קשה גם למצוא עבודה בגוגל.

202
00:10:01,860 --> 00:10:05,490
יש לנו שאלות, ואנחנו
לשאול שאלות המועמדים שלנו,

203
00:10:05,490 --> 00:10:09,770
ואת זה הוא מלארי שווימר.

204
00:10:09,770 --> 00:10:14,760
What-- אתם חושבים שאני
צוחק, זה ממש כאן.

205
00:10:14,760 --> 00:10:17,930
מהי הדרך היעילה ביותר ל
למיין מיליון מספרים שלמים 32 סיביות?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> -אני מצטער, maybe--

209
00:10:25,200 --> 00:10:27,400
>> 'לא, לא, לא.

210
00:10:27,400 --> 00:10:30,700
אני חושב שמיון הבועות
יהיה בדרך הלא נכונה ללכת.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> "תיכנס על, שאמר לו את זה?

213
00:10:38,180 --> 00:10:40,590
אני לא רואה את המחשב
מדע ברקע שלך.

214
00:10:40,590 --> 00:10:42,130
>> -We've לי המרגלים שלנו שם.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> "או-קיי, בואו לשאול שונה
שאלת ראיון.

217
00:10:48,444 --> 00:10:49,300
>> [END הפעלת וידאו]

218
00:10:49,300 --> 00:10:52,290
>> דובר: אז דיבר על
מספרים ספציפיים אם כי,

219
00:10:52,290 --> 00:10:53,890
הוא לא הולך להיות כל כך שימושי.

220
00:10:53,890 --> 00:10:56,810
זה לא שיעור חיים בועה ש
סוג, נתן מיליון כניסות,

221
00:10:56,810 --> 00:10:58,590
עלול לקחת כמה ש500 מליארד צעדים.

222
00:10:58,590 --> 00:11:01,120
אתה לא באמת יכול להכליל
ביעילות גם שמ

223
00:11:01,120 --> 00:11:03,560
ולקבל החלטות עיצוב טובות
בעת כתיבת תוכניות.

224
00:11:03,560 --> 00:11:07,070
אז בואו נתמקד אם כי באופן
אנו עשויים לפשט את התוצאה הזאת.

225
00:11:07,070 --> 00:11:11,780
>> אז אני כבר מודגש בצהוב כאן
התוצאה של n בריבוע מתחלקת ב -2,

226
00:11:11,780 --> 00:11:14,330
כך מיליון בריבוע
מחולק ב2, ולאחר מכן

227
00:11:14,330 --> 00:11:16,710
אני כבר הדגיש את מה ש
התשובה הסופית הייתה

228
00:11:16,710 --> 00:11:20,180
ברגע שאנחנו נגרעו מן מחולקים n על ידי 2.

229
00:11:20,180 --> 00:11:24,850
והטענה שאני הולך לעשות עכשיו היא,
מי לעזאזל אכפת אם מחסר את

230
00:11:24,850 --> 00:11:30,060
n ישן קצת יותר מ 2 כאשר הראשון
חלק מנוסחה זו הוא כל כך הרבה יותר גדולה?

231
00:11:30,060 --> 00:11:33,910
הוא שולט אחר
טווח, n בריבוע מתחלק על ידי 2

232
00:11:33,910 --> 00:11:37,510
כל כך הרבה יותר גדול, באופן ברור, כפי ש
n מקבל גדול כמו מיליון,

233
00:11:37,510 --> 00:11:41,450
כי הוא באמת יש הבדל גדול ב
סופו של היום בין 500 מיליארדים

234
00:11:41,450 --> 00:11:45,730
ו499999500000?

235
00:11:45,730 --> 00:11:46,349
לא ממש.

236
00:11:46,349 --> 00:11:48,640
ואז מה אנחנו הולכים
לעשות כמדענים מחשב הוא

237
00:11:48,640 --> 00:11:53,270
להתעלם מונחים נמוכים כדי אלה ו
לקחת משהו כזה, ואם באמת

238
00:11:53,270 --> 00:11:56,050
רק לפשט אותו ל
מונח זה יהיה קובע.

239
00:11:56,050 --> 00:12:00,315
ערכות נתונים שלנו גדולות יותר לקבל, גדולות יותר
מאגרי המידע שלנו מקבלים, יותר דפי האינטרנט

240
00:12:00,315 --> 00:12:02,690
יש לנו לחפש, יותר
חברים יש לך בפייסבוק.

241
00:12:02,690 --> 00:12:07,340
>> ככל שתגדל, אנחנו באמת
הולך אכפת הגדול

242
00:12:07,340 --> 00:12:11,560
טווח בכל ניתוח כזה של
ביצועי האלגוריתמים שלנו.

243
00:12:11,560 --> 00:12:16,230
ואני הולך לומר, אתה יודע מה,
מיון בועות הוא בסדר הגודל של O הגדול,

244
00:12:16,230 --> 00:12:18,060
על סדר n בריבוע.

245
00:12:18,060 --> 00:12:20,090
זה לא בדיוק n
בריבוע כפי שראינו,

246
00:12:20,090 --> 00:12:22,060
אבל מי שבאמת אכפת לו
על התנאים הללו, קטנים יותר,

247
00:12:22,060 --> 00:12:24,390
ולמען אמת, מי באמת
אכפת אם אנו מחלקים על ידי 2?

248
00:12:24,390 --> 00:12:25,870
זה בדיוק גורם קבוע.

249
00:12:25,870 --> 00:12:29,480
והוא 500 מליארד לעומת 250
מיליארדים באמת כל כך גדול של עסקה?

250
00:12:29,480 --> 00:12:32,190
אני רק יכול לחכות לשנה אחת,
בואו המחשב הנייד שלי, פשוטו כמשמעו,

251
00:12:32,190 --> 00:12:34,810
לקבל במהירות כפולה בחומרה,
וזה סוג של הבדל

252
00:12:34,810 --> 00:12:36,650
פשוט הולך משם באופן טבעי לאורך זמן.

253
00:12:36,650 --> 00:12:39,300
>> מה אכפת לנו הוא
הביטוי, החלק

254
00:12:39,300 --> 00:12:42,489
של הביטוי זה הולך להשתנות
כקלט שלנו מקבל יותר ויותר גדול.

255
00:12:42,489 --> 00:12:45,280
ואכן, בעולם האמיתי,
זה מה שקורה יותר ויותר

256
00:12:45,280 --> 00:12:48,330
הוא התשומות לבעיות שלנו ו
אלגוריתמים מקבלים גדולים יותר.

257
00:12:48,330 --> 00:12:53,470
אז O הגדול הולך להיות הסימון,
סימון אסימפטוטי, שאנחנו פשוט

258
00:12:53,470 --> 00:12:57,160
להשתמש בו כמדענים מחשב כדי לתאר
ביצועים, או זמן הריצה,

259
00:12:57,160 --> 00:12:58,130
של אלגוריתם.

260
00:12:58,130 --> 00:13:00,800
כדי שנוכל להשוות אלגוריתמים
במחשבים שונים שנכתבו

261
00:13:00,800 --> 00:13:04,170
על ידי אנשים שונים, על ידי שימוש
כמה מטרי דומה בבסיס

262
00:13:04,170 --> 00:13:07,557
כמו מספר ההשוואות שאתה
מה שהופך, או אולי מספר עסקות החלף

263
00:13:07,557 --> 00:13:08,140
אתה עושה.

264
00:13:08,140 --> 00:13:11,910
>> מה אנחנו לא הולכים ל
ספירה היא כמות הזמן

265
00:13:11,910 --> 00:13:13,981
שעובר על השעון
על הקיר בדרך כלל.

266
00:13:13,981 --> 00:13:16,230
מה אנחנו לא הולכים לדאוג
עליו הוא כמה זיכרון

267
00:13:16,230 --> 00:13:17,820
אתה משתמש היום ב
לפחות, אם כי זה

268
00:13:17,820 --> 00:13:19,370
משאב אחר שאנחנו יכולים למדוד.

269
00:13:19,370 --> 00:13:23,610
אנחנו הולכים לנסות לבסס את הניתוחים שלנו
על רק את הפעולות הבסיסיות, אלה,

270
00:13:23,610 --> 00:13:25,930
בכנות, כי אתה יכול לראות ביותר מבחינה ויזואלית.

271
00:13:25,930 --> 00:13:30,700
אז עם משהו כמו O הגדול של n
בריבוע, אני טוען שO של n בריבוע

272
00:13:30,700 --> 00:13:35,820
הוא מחויב עליון על מה שנקרא
זמן ריצה של מיון בועות.

273
00:13:35,820 --> 00:13:38,820
במילים אחרות, אם אתה
רציתי לטעון שיש

274
00:13:38,820 --> 00:13:41,370
גבול עליון זה בכמה
צעדים אלגוריתם עלול לקחת,

275
00:13:41,370 --> 00:13:46,240
זה הולך להיות בO הגדול של n
בריבוע במקרה הזה, גבול עליון.

276
00:13:46,240 --> 00:13:49,710
>> מה אם אני במקום לשנות את
סיפור להיות לא על מיון בועות,

277
00:13:49,710 --> 00:13:50,910
אבל על גבול עליון זו.

278
00:13:50,910 --> 00:13:54,030
האם תוכל לחשוב על אלגוריתם
שאנחנו בדקנו כבר

279
00:13:54,030 --> 00:13:59,530
שגבולו העליון, לכל היותר
למדוד זמן או פעולות,

280
00:13:59,530 --> 00:14:04,300
יהיה אמר להיות חסום
על ידי n, פונקציה לינארית,

281
00:14:04,300 --> 00:14:07,260
לא אחת ריבועית זה מעוקל?

282
00:14:07,260 --> 00:14:10,780
מה אלגוריתם ש
תמיד לוקח לא יותר

283
00:14:10,780 --> 00:14:12,860
מ כמו צעדי n, או
צעדי 2n, או צעדי 3 יד?

284
00:14:12,860 --> 00:14:13,360
כן?

285
00:14:13,360 --> 00:14:15,030
>> קהל: מציאת
המספר הגדול ביותר ברשימה?

286
00:14:15,030 --> 00:14:16,930
>> דובר: מושלם, מציאת
המספר הגדול ביותר ברשימה.

287
00:14:16,930 --> 00:14:18,940
אם אני קבלתי רשימה של
אנשים למשל,

288
00:14:18,940 --> 00:14:21,440
כל אחד שממחזיק מספר,
מה הוא המספר המרבי

289
00:14:21,440 --> 00:14:23,770
צעדים שהוא צריך לקחת אותי,
אדם חכם באופן סביר,

290
00:14:23,770 --> 00:14:27,530
כדי למצוא את האדם הגדול ביותר ברשימה?

291
00:14:27,530 --> 00:14:28,100
n, נכון?

292
00:14:28,100 --> 00:14:31,320
משום שבמקרה הגרוע ביותר, שבו
יכול להיות הערך הגדול ביותר?

293
00:14:31,320 --> 00:14:32,700
תקין, כל הדרך בסוף.

294
00:14:32,700 --> 00:14:34,575
אז במקרה הגרוע ביותר
גבול עליון, אולי אני

295
00:14:34,575 --> 00:14:36,450
צריך ללכת את כל הדרך
לכאן ולהיות כמו,

296
00:14:36,450 --> 00:14:39,170
הו, הנה מספר שמונה,
או מה הערך ש.

297
00:14:39,170 --> 00:14:41,330
עכשיו זה יהיה פשוט טיפשי
אם אני כל הזמן הולך, נכון?

298
00:14:41,330 --> 00:14:43,840
מחפש עוד ועוד אלמנטים
אם האחרון שלהם הוא שם?

299
00:14:43,840 --> 00:14:45,340
אז בוודאי, n הוא גבול עליון.

300
00:14:45,340 --> 00:14:47,420
אני לא צריך לקחת
עוד צעדים מזה.

301
00:14:47,420 --> 00:14:51,580
>> אז מה אם במקום אני הצעתי ש
יש אלגוריתמים בעולם הזה ש

302
00:14:51,580 --> 00:14:57,750
יש לי זמן לרוץ זה
מתוחם על ידי O הגדול של n יומן, יומן n?

303
00:14:57,750 --> 00:15:00,390
שם יש לנו ראינו את זה?

304
00:15:00,390 --> 00:15:00,890
כן?

305
00:15:00,890 --> 00:15:03,309
>> קהל: בבעיה בספר טלפונים?

306
00:15:03,309 --> 00:15:04,850
דובר: כמו הבעיה בספר טלפונים.

307
00:15:04,850 --> 00:15:07,754
מה הייתה המידה של כמה
הרבה זמן או כמה דמעות זה

308
00:15:07,754 --> 00:15:10,170
לקחו לי למצוא מישהו כמו
מייק סמית בספר טלפונים?

309
00:15:10,170 --> 00:15:13,212
אנחנו טענו שזה n יומן, ו
גם אם לא מוכר או שזה זה

310
00:15:13,212 --> 00:15:15,170
קצת מעורפל מה
לוגריתם או מעריך היה,

311
00:15:15,170 --> 00:15:17,650
רק לזכור כי n היומן
בדרך כלל מתייחס לתהליך,

312
00:15:17,650 --> 00:15:20,790
במקרה זה, של החלוקה
משהו במחצית שוב, ושוב,

313
00:15:20,790 --> 00:15:25,790
ושוב, ושוב, באופן ש
מקבל קטן יותר ויותר ככל שאתה עושה את זה.

314
00:15:25,790 --> 00:15:28,470
>> אז להיכנס של n מתייחס, בטוח,
לדוגמא ספר טלפונים,

315
00:15:28,470 --> 00:15:32,662
לחיפוש בינארי בתאוריה, כאשר אנו
היה לי הדלתות הוירטואליות על הלוח,

316
00:15:32,662 --> 00:15:34,370
או כאשר שון היה
מחפש משהו.

317
00:15:34,370 --> 00:15:37,374
אם הוא היה בשימוש חיפוש בינארי, להתחבר n
יהיה הגבול העליון בכמה

318
00:15:37,374 --> 00:15:38,040
זמן שלוקח.

319
00:15:38,040 --> 00:15:44,027
אבל אלה אלגוריתמים שרצו ב
יומן n להניח מה פרט מפתח?

320
00:15:44,027 --> 00:15:45,360
שהרשימה מסודרים, נכון?

321
00:15:45,360 --> 00:15:47,789
האלגוריתם שלך לא בסדר אם
הקלט שלך לא מסודרים,

322
00:15:47,789 --> 00:15:49,830
ובכל זאת אתה משתמש
משהו כמו חיפוש בינארי

323
00:15:49,830 --> 00:15:51,704
כי אתה עלול לקפוץ
ממש מעל האלמנט

324
00:15:51,704 --> 00:15:53,600
בלי להבין שזה אכן קיים.

325
00:15:53,600 --> 00:15:55,600
>> עכשיו מה שזה אומר, O הגדול של אחד?

326
00:15:55,600 --> 00:15:59,117
זה לא אומר שהאלגוריתם שלך
לוקח אחד ורק צעד אחד,

327
00:15:59,117 --> 00:16:01,200
זה רק אומר שזה לוקח
מספר קבוע של צעדים.

328
00:16:01,200 --> 00:16:04,060
אולי זה 1, אולי זה
10, אולי זה 1,000,

329
00:16:04,060 --> 00:16:07,750
אבל זה בלתי תלוי
הגודל של הבעיה.

330
00:16:07,750 --> 00:16:10,850
לא משנה כמה גדול n הוא,
אלגוריתם זמן קבוע

331
00:16:10,850 --> 00:16:12,747
תמיד לוקח את אותו המספר של צעדים.

332
00:16:12,747 --> 00:16:15,080
אז מה יכול להיות אלגוריתם
אנחנו כבר דיברנו על או סתם

333
00:16:15,080 --> 00:16:20,418
באופן אינטואיטיבי שמגיע לך ש
תמיד פועל בזמן קבוע מה שנקרא?

334
00:16:20,418 --> 00:16:20,918
כן?

335
00:16:20,918 --> 00:16:22,001
>> קהל: הוספת שני מספרים.

336
00:16:22,001 --> 00:16:25,320
SPEAKER: הוסף שני מספרים,
2 ועוד 2 שווים 4, עשו.

337
00:16:25,320 --> 00:16:27,227
אז אולי שעובד, מה עוד?

338
00:16:27,227 --> 00:16:28,560
מה דעתך על עולם אמיתי יותר, כן?

339
00:16:28,560 --> 00:16:30,686
>> קהל: מציאת
הדבר ראשון ברשימה.

340
00:16:30,686 --> 00:16:32,810
דובר: מציאת הראשונה
אלמנט ברשימה, בטוח.

341
00:16:32,810 --> 00:16:34,540
אנחנו כבר בעצם מדברים
על מערכים כבר,

342
00:16:34,540 --> 00:16:36,540
איך אתה מקבל ב
האלמנט ראשון במערך,

343
00:16:36,540 --> 00:16:40,465
לא משנה כמה זמן
מערך הוא בקוד C?

344
00:16:40,465 --> 00:16:43,090
אתה פשוט להשתמש כמו הסוגר
אפס סימון, בום, אתה שם.

345
00:16:43,090 --> 00:16:46,120
ואכן מערכים, במאמר מוסגר,
תמיכת משהו בדרך כלל ידוע

346
00:16:46,120 --> 00:16:49,240
כגישה אקראית, גישה אקראית
זיכרון, כי פשוטו כמשמעו שאתה יכול

347
00:16:49,240 --> 00:16:50,284
לקפוץ לכל מקום אחד.

348
00:16:50,284 --> 00:16:52,700
אנחנו יכולים לעשות את זה אפילו יותר פשוט
אנחנו יכולים להריץ אחורה לשבוע אפס

349
00:16:52,700 --> 00:16:53,900
כשעשינו שריטה.

350
00:16:53,900 --> 00:16:59,707
כמה זמן היה לוקח לי
אומר בלוק בScratch לבצע?

351
00:16:59,707 --> 00:17:00,790
רק זמן קבוע, נכון?

352
00:17:00,790 --> 00:17:03,960
תגיד משהו, אומר
משהו, זה לא משנה

353
00:17:03,960 --> 00:17:07,359
איך עולם שריטות גדולות הוא, זה תמיד
הולך לקחת את אותה הכמות של זמן

354
00:17:07,359 --> 00:17:08,490
פשוט להגיד משהו.

355
00:17:08,490 --> 00:17:11,089
>> אז זה זמן קבוע,
אבל מה הצד השני של המטבע?

356
00:17:11,089 --> 00:17:13,030
אם זה היה עליון
גבולות, מה אם אנחנו רוצים

357
00:17:13,030 --> 00:17:17,089
כדי לתאר את החסמים התחתונים
האלגוריתמים שלנו פועל זמן?

358
00:17:17,089 --> 00:17:19,852
כמעט מקרה טוב
פוטנציאל, אם תרצה,

359
00:17:19,852 --> 00:17:23,060
למרות שהתנאים אלה ניתנים להחלה הטובה ביותר
מקרים, המקרים החמורים ביותר, מקרים ממוצע יותר

360
00:17:23,060 --> 00:17:26,359
בדרך כלל, אבל בואו פשוט להתמקד
על חסמים התחתונים באופן כללי יותר.

361
00:17:26,359 --> 00:17:31,920
מה אלגוריתם שיש
גבול תחתון של צעדי n,

362
00:17:31,920 --> 00:17:33,350
או צעדי 2n, או צעדי 3 יד?

363
00:17:33,350 --> 00:17:36,241
גורם חלק מצעדי n,
זה גבול תחתון.

364
00:17:36,241 --> 00:17:36,740
כן?

365
00:17:36,740 --> 00:17:37,910
>> קהל: מיון בועות?

366
00:17:37,910 --> 00:17:41,610
>> דובר: מיון בועות לוקח
אתה צעדי n המינימלי, למה?

367
00:17:41,610 --> 00:17:42,279
מדוע זה כך?

368
00:17:42,279 --> 00:17:45,320
למה מלכתחילה שלבוא אליך
באופן אינטואיטיבי, גם אם זה לא פשוט

369
00:17:45,320 --> 00:17:46,530
עדיין?

370
00:17:46,530 --> 00:17:47,030
כן?

371
00:17:47,030 --> 00:17:47,990
>> קהל: [לא ברור].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
SPEAKER: בדיוק.

374
00:17:52,360 --> 00:17:55,810
בתרחיש הטוב ביותר האפשרי של
מיון בועות, והרבה אלגוריתמים,

375
00:17:55,810 --> 00:17:58,769
אם אני נותן לך שמונה בני אדם
שכבר מסודרים,

376
00:17:58,769 --> 00:18:00,560
זה יהיה טיפשי
בשבילך, האלגוריתם,

377
00:18:00,560 --> 00:18:02,202
ללכת קדימה ואחורה
יותר מפעם אחת, נכון?

378
00:18:02,202 --> 00:18:04,285
כי ברגע שאתה
ללכת דרך הרשימה פעם אחת,

379
00:18:04,285 --> 00:18:08,090
אתה צריך להבין, הו, אני לא עשיתי שום
עסקות החלף, רשימה זו היא מסודרת, יציאה.

380
00:18:08,090 --> 00:18:09,700
אבל זה הולך לקחת לך n צעדים.

381
00:18:09,700 --> 00:18:12,033
>> ולהפך, מה עוד
דרך לחשוב על זה?

382
00:18:12,033 --> 00:18:15,240
מיון בועות הוא אומגה,
אם אפשר לומר כך, של n,

383
00:18:15,240 --> 00:18:19,050
כי אם אתה מסתכל על
פחות מ n אלמנטים, מה ש

384
00:18:19,050 --> 00:18:23,009
היא הסוגיה העקרונית שיש?

385
00:18:23,009 --> 00:18:24,550
אתה לא יודע אם זה מסודרים, תקין.

386
00:18:24,550 --> 00:18:26,800
אנחנו, בני אדם מבט חטוף כוח בשמונה
אנשים ולהיות כמו, אה, זה מסודרים,

387
00:18:26,800 --> 00:18:28,430
שלא לקח לי n צעדים, אבל זה לא.

388
00:18:28,430 --> 00:18:30,810
העיניים שלך, למרות שאתה סוג
יש לי של שדה גדול של חזון,

389
00:18:30,810 --> 00:18:33,184
אתה הסתכל על שמונה רכיבים,
אתה הסתכל על שמונה אנשים,

390
00:18:33,184 --> 00:18:34,610
זה שמונה שלבים בצורה יעילה.

391
00:18:34,610 --> 00:18:38,612
ורק אם אני הולך בכל
רשימה אני מבין, כן, מסודרים.

392
00:18:38,612 --> 00:18:41,320
כל באמצע הדרך אם אני מפסיק לחשוב,
נכון, זה די מסודרים עד כה,

393
00:18:41,320 --> 00:18:42,520
מה הסיכויים שזה לא מסודרים?

394
00:18:42,520 --> 00:18:44,186
שהאלגוריתמים לא הולכים להיות נכון.

395
00:18:44,186 --> 00:18:46,250
יכול להיות מהיר יותר, אבל לא נכון.

396
00:18:46,250 --> 00:18:48,500
>> אז עכשיו יש לנו דרך של
מתאר חסמים תחתון,

397
00:18:48,500 --> 00:18:49,710
ומה לגבי זמן קבוע?

398
00:18:49,710 --> 00:18:54,565
מה אלגוריתם שיש לו נמוך יותר
מחויב בזמן הריצה שלה של אחת?

399
00:18:54,565 --> 00:18:58,350
שלב 1, 2 שלבים, 10 צעדים, אבל
קבוע, עצמאי של n,

400
00:18:58,350 --> 00:18:59,310
הגודל של הקלט?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
כן, בגב.

403
00:19:04,600 --> 00:19:05,309
>> קהל: printf?

404
00:19:05,309 --> 00:19:06,183
דובר: מה זה?

405
00:19:06,183 --> 00:19:07,184
קהל: printf?

406
00:19:07,184 --> 00:19:07,850
דובר: printf.

407
00:19:07,850 --> 00:19:08,400
אישור, בטוח.

408
00:19:08,400 --> 00:19:10,720
אז זה לוקח מספר קבוע של צעדים.

409
00:19:10,720 --> 00:19:13,170
ואני צריך now-- עכשיו ש
על קוד C שאנחנו מדברים

410
00:19:13,170 --> 00:19:16,040
ולא גירוד, משהו
כמו למשל, עם printf,

411
00:19:16,040 --> 00:19:17,710
אנחנו צריכים להתחיל לקבל זהירים.

412
00:19:17,710 --> 00:19:21,090
בגלל printf לוקח
קלט, זה מחרוזת,

413
00:19:21,090 --> 00:19:23,220
ואל מבחינה טכנית יש לי מחרוזות באורך.

414
00:19:23,220 --> 00:19:25,530
אז אם אנחנו עכשיו רוצים לקחת
עליך, אם לא אכפת לך,

415
00:19:25,530 --> 00:19:29,430
מבחינה טכנית אנחנו יכולים להתווכח printf ש
לוקח קלט באורך משתנה,

416
00:19:29,430 --> 00:19:32,270
ובוודאי שזה יכול לקחת יותר
זמן להדפסת מחרוזת ארוכה זו,

417
00:19:32,270 --> 00:19:33,560
מזה זמן רב.

418
00:19:33,560 --> 00:19:36,570
>> אז מה אם ניקח בחשבון רק את
מיון וחיפוש דוגמאות?

419
00:19:36,570 --> 00:19:40,450
מה לגבי מייק סמית בטלפון
ספר, או חיפוש בינארי באופן כללי יותר?

420
00:19:40,450 --> 00:19:42,220
במקרה הטוב ביותר, מה שעלול לקרות?

421
00:19:42,220 --> 00:19:45,577
אני פותח את ספר טלפונים ו, ​​בום,
יש המספר של מייק סמית.

422
00:19:45,577 --> 00:19:46,660
אני יכול לקרוא לו באופן מיידי.

423
00:19:46,660 --> 00:19:49,390
>> לקח צעד אחד, אולי שני צעדים,
אבל מספר קבוע של צעדים

424
00:19:49,390 --> 00:19:50,230
אם יש לי מזל.

425
00:19:50,230 --> 00:19:52,570
ולמען אמת, שראינו ב
הכיתה שלך יום שני

426
00:19:52,570 --> 00:19:54,710
להגיע די מזלו פעמיים ברציפות.

427
00:19:54,710 --> 00:19:57,050
וזה היה אכן קבוע
זמן בחסמים תחתון

428
00:19:57,050 --> 00:20:01,280
על האלגוריתם בשאלה למציאת
המספר 50 מאחורי סגור אלה

429
00:20:01,280 --> 00:20:01,830
דלתות.

430
00:20:01,830 --> 00:20:06,400
>> עכשיו, במאמר מוסגר, אם אתה מגלה
ששניהם O הגדול, הגבול העליון,

431
00:20:06,400 --> 00:20:09,310
ואומגה, גבול תחתון,
אחד באותו, ש

432
00:20:09,310 --> 00:20:11,830
היא באותה הנוסחה ב
סוגריים, אתה גם יכול

433
00:20:11,830 --> 00:20:15,170
אומר, רק כדי להיות מפואר,
משהו שהוא בתטא

434
00:20:15,170 --> 00:20:18,270
של n או תטא של ערך אחר.

435
00:20:18,270 --> 00:20:20,661
זה רק אומר כאשר גדול
O ואומגה הם אותו הדבר.

436
00:20:20,661 --> 00:20:21,910
עכשיו מה עם מיון בחירה?

437
00:20:21,910 --> 00:20:23,400
בואו להשתמש אוצר מילים חדשים.

438
00:20:23,400 --> 00:20:27,407
במיון בחירה, מה היו לנו
עושה שוב, ושוב, ושוב?

439
00:20:27,407 --> 00:20:29,990
אני הולך הלוך ושוב דרך
הרשימה, מחפשת את מי?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
המספר הקטן ביותר.

442
00:20:34,730 --> 00:20:37,560
>> אז איך שלבים רבים, כיצד
השוואות רבות עשו לי

443
00:20:37,560 --> 00:20:43,250
צריך לעשות כדי להבין מי
האלמנט הקטן ביותר ברשימה היה?

444
00:20:43,250 --> 00:20:44,437
n מינוס 1, נכון?

445
00:20:44,437 --> 00:20:47,770
כי אם אני רק אתחיל עם זה שאני
ניתנו ואני מתחיל להשוות אותו או אותה,

446
00:20:47,770 --> 00:20:49,519
אז או לה, לו
או שלה, לו או לה, אני

447
00:20:49,519 --> 00:20:52,010
רק תוכל לשייך אלמנטים
יחד n מינוס 1 פעמים.

448
00:20:52,010 --> 00:20:55,630
אז בחירה לוקחת סוג דומה
n מינוס 1 על שלבים בפעם הראשונה.

449
00:20:55,630 --> 00:20:59,540
>> כמה צעדים נדרשים עליי
למצוא את האלמנט השני הקטן ביותר?

450
00:20:59,540 --> 00:21:02,920
n מינוס 2, כי אני להיות מטומטם
אם אני כל הזמן מסתכל על אותם האנשים

451
00:21:02,920 --> 00:21:06,280
שוב, אם אני כבר בחרתי אותו
או שלה ולשים אותם במקום שלהם.

452
00:21:06,280 --> 00:21:09,270
והצעד השלישי, n
מינוס 3, אז n מינוס 4.

453
00:21:09,270 --> 00:21:11,020
ראינו את הדפוס הזה
לפני, ואכן

454
00:21:11,020 --> 00:21:13,460
בחירת סוג דומה
יש גבול עליון

455
00:21:13,460 --> 00:21:16,210
של n בריבוע אם אתה עושה אותנו הסיכום ש.

456
00:21:16,210 --> 00:21:19,790
מהו הסוג, הגבול התחתון שלה בחירה?

457
00:21:19,790 --> 00:21:25,350
לכל הפחות, בחירת חובה זמן כמה
סוג לקחת, כפי שאנו מגדירים אותה ביום שני?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
להציע שתי אפשרויות.

460
00:21:30,490 --> 00:21:32,360
אולי זה n, כמו קודם.

461
00:21:32,360 --> 00:21:35,040
אולי זה N של ריבוע, כפי ש
כעת כגבול העליון.

462
00:21:35,040 --> 00:21:35,874
>> קהל: n בריבוע.

463
00:21:35,874 --> 00:21:36,664
דובר: n בריבוע.

464
00:21:36,664 --> 00:21:37,368
למה?

465
00:21:37,368 --> 00:21:40,060
>> קהל: בגלל שיש לך
להגדיר [לא ברור].

466
00:21:40,060 --> 00:21:41,510
>> SPEAKER: בדיוק.

467
00:21:41,510 --> 00:21:45,077
לפחות כפי שאני מוגדר מיון בחירה
זה היה די נאיבי, להמשיך,

468
00:21:45,077 --> 00:21:46,160
למצוא את האלמנט הקטן ביותר.

469
00:21:46,160 --> 00:21:47,770
ללכת שוב, למצוא את האלמנט הקטן ביותר.

470
00:21:47,770 --> 00:21:49,490
ללכת שוב, למצוא את האלמנט הקטן ביותר.

471
00:21:49,490 --> 00:21:51,700
אין סוג של
אופטימיזציה שם ש

472
00:21:51,700 --> 00:21:54,350
אולי תנו לי להפיל לאחר
רק n או כך צעדים.

473
00:21:54,350 --> 00:21:57,080
אז אכן, בחירה
סוג, אומגה של n בריבוע.

474
00:21:57,080 --> 00:22:00,667
>> מה לגבי סוג ההכנסה, שבו לקחתי
שנתן לי, ולאחר מכן צנחתי לו

475
00:22:00,667 --> 00:22:01,750
או שלה במקום הנכון?

476
00:22:01,750 --> 00:22:04,958
אחר כך המשכתי והאדם השני,
צנח לו או לה במקום הנכון.

477
00:22:04,958 --> 00:22:07,910
אז האדם הבא, צנח
לו או לה במקום הנכון.

478
00:22:07,910 --> 00:22:10,537
שימו לב שזה מאוד
ליניארי, אם אפשר לומר כך.

479
00:22:10,537 --> 00:22:12,620
אני בקו ישר, אני
לא הולך הלוך ושוב,

480
00:22:12,620 --> 00:22:16,080
אף פעם לא מסתכל אחורה ממש, אבל
מה קורה כאשר אני מכניס אותו

481
00:22:16,080 --> 00:22:20,302
או אותה לתחילה
הרשימה כפי שעשינו ביום שני?

482
00:22:20,302 --> 00:22:21,010
מה קורה?

483
00:22:21,010 --> 00:22:21,510
כן?

484
00:22:21,510 --> 00:22:23,122
קהל: [לא ברור].

485
00:22:23,122 --> 00:22:24,830
דובר: כן, ש
היה לתפוס, נכון?

486
00:22:24,830 --> 00:22:26,746
אתם אולי זוכרים מ
החברים לכיתה שלך, אם הם

487
00:22:26,746 --> 00:22:29,670
היו עושה כל תנועה עם
רגליהם, הייתה שפעולה.

488
00:22:29,670 --> 00:22:33,610
אז אם היו שלושה אנשים כאן ו
האדם החדש שייך דרך לשם,

489
00:22:33,610 --> 00:22:37,360
בשלב ארוך כזה, בטוח, הוא
או שהיא יכולה פשוט ללכת עד הסוף.

490
00:22:37,360 --> 00:22:40,074
אבל אם אנחנו חושבים על
מחשב ומערך של זיכרון,

491
00:22:40,074 --> 00:22:41,990
האנשים האלה הולכים
יש לערבב מעל

492
00:22:41,990 --> 00:22:43,260
כדי לפנות מקום עבור אותו אדם.

493
00:22:43,260 --> 00:22:46,930
וכדי שn מינוס 1 shufflings,
n מינוס 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
מינוס 3 shufflings הוא פשוט סוג של
קורה מאחוריי, לא מולי

495
00:22:50,660 --> 00:22:52,710
כמו קודם, במובן מסוים.

499
00:22:52,557 --> 00:22:54,640
עכשיו במאמר מוסגר, וכמו
שאולי ראו באינטרנט

500
00:22:54,640 --> 00:22:57,699
אם אתה מתחיל לחטט על
מיני, יש כל כך הרבה שונים אלה

501
00:22:57,699 --> 00:22:59,490
שם בחוץ, חלקם
טוב יותר מאחרים.

502
00:22:59,490 --> 00:23:02,200
ואכן, bogosort הוא אחד
זה סוג של כיף להסתכל למעלה.

503
00:23:02,200 --> 00:23:06,650
Bogosort לוקח סט של
מספרים או לומר חפיסת קלפים,

504
00:23:06,650 --> 00:23:09,870
באופן אקראי מערבב אותם, ו
בודק אם הם מסודרים.

505
00:23:09,870 --> 00:23:12,130
ואם לא, עושה את זה שוב.

506
00:23:12,130 --> 00:23:14,140
ואם לא, עושה את זה שוב.

507
00:23:14,140 --> 00:23:15,440
אם לא, עושה את זה שוב.

508
00:23:15,440 --> 00:23:17,060
מטומטם.

509
00:23:17,060 --> 00:23:19,520
>> ואכן, אם אתה קורא
כמו המאמר בויקיפדיה,

510
00:23:19,520 --> 00:23:21,200
הכינוי שלה הוא סוג טיפש.

511
00:23:21,200 --> 00:23:25,180
זה סופו של דבר יעבוד,
אני מקווה, מספיק זמן נתון,

512
00:23:25,180 --> 00:23:28,240
אבל כמות כזו של זמן
יכול לקחת די הרבה זמן.

513
00:23:28,240 --> 00:23:31,650
אז אם אני יכול, של לתת לדברים במהירות
מהדוגמא של מרי בת קודם לכן,

514
00:23:31,650 --> 00:23:35,150
על ידי בעל עוד כמה אלמנטים,
אבל שני מעבדים יותר.

515
00:23:35,150 --> 00:23:37,100
שני אנשים, אם אתה
לא היה אכפת לי להצטרף.

516
00:23:37,100 --> 00:23:40,972
מה דעתך על 1 כאן, ו
בואו go-- אף אחד לא שם?

517
00:23:40,972 --> 00:23:41,722
אף אחד לא שם?

518
00:23:41,722 --> 00:23:42,221
אישור.

519
00:23:42,221 --> 00:23:44,190
לך עם שחור
חולצה, כן, בואי למטה.

520
00:23:44,190 --> 00:23:45,000
בסדר, מה השם שלך?

521
00:23:45,000 --> 00:23:45,720
>> קהל: פיטר.

522
00:23:45,720 --> 00:23:46,100
>> דובר: מה זה?

523
00:23:46,100 --> 00:23:46,766
>> קהל: פיטר.

524
00:23:46,766 --> 00:23:49,450
הדובר: פיטר, דוד, נחמד לפגוש אותך.

525
00:23:49,450 --> 00:23:53,670
בסדר, יש לנו פיטר כאן, אם אתה
רוצה לבוא על השולחן כאן.

526
00:23:53,670 --> 00:23:54,550
ואיך קוראים לך?

527
00:23:54,550 --> 00:23:55,216
>> קהל: אלנה.

528
00:23:55,216 --> 00:23:55,970
דובר: אלנה.

529
00:23:55,970 --> 00:23:57,030
אישור, נחמד לפגוש אותך.

530
00:23:57,030 --> 00:23:58,060
אלנה לפגוש את פיטר.

531
00:23:58,060 --> 00:23:59,170
פיטר, אלנה.

532
00:23:59,170 --> 00:24:02,290
ואנחנו נצטרך אנדרו
עד כאן, כמו גם, בבקשה.

533
00:24:02,290 --> 00:24:06,107
והאתגר שלך הולך
להיות למיין חפיסת קלפים.

534
00:24:06,107 --> 00:24:08,190
ואם לא מוכר, סיפון
כרטיסים צריכים סופו של דבר

535
00:24:08,190 --> 00:24:11,064
להיות מסודר קצת משהו כמו
זה שבו יהיה לנו לעשות מועדונים, אז

536
00:24:11,064 --> 00:24:13,660
המעדרים, אז את לבם ו
יהלומים, מאס כאחד,

537
00:24:13,660 --> 00:24:15,570
כל הדרך עד למלך.

538
00:24:15,570 --> 00:24:20,890
>> הכרטיסים אני הולך לתת לך
הולכים להיות 52 בכמות.

539
00:24:20,890 --> 00:24:23,160
אנחנו הולכים באופן דומה
פעם שאתה, ברגע.

540
00:24:23,160 --> 00:24:26,410
אנחנו הולכים לזרוק את אנדרו
על המסך כאן,

541
00:24:26,410 --> 00:24:28,170
כדי לראות איך אתה עושה את זה.

542
00:24:28,170 --> 00:24:31,070
וכדי שכל זה
לא כל שנראה לעין,

543
00:24:31,070 --> 00:24:33,490
אלה הם הכרטיסים שקיבלתי באמזון.

544
00:24:33,490 --> 00:24:42,861
אז הם כבר באופן אקראי
מסודרים, ואנחנו הולכים לך זמן.

545
00:24:42,861 --> 00:24:44,610
ואנחנו הולכים
לשמור את זה אמיתי הפעם,

546
00:24:44,610 --> 00:24:47,820
אז אנחנו הולכים לנסות ללחוץ עליך
כי אחר זה יקבל מייגע

547
00:24:47,820 --> 00:24:48,460
במהירות.

548
00:24:48,460 --> 00:24:53,860
אם אתה יכול להמשיך למיין 52
אלמנטים יחד באמצעות כמה אמצעים, עכשיו.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> ושוב, כפי שאנו צופים אלה
החבר 'ה לעשות מה, בסופו של הדבר

551
00:25:07,180 --> 00:25:10,200
הוא הולך לייצר ברור
תוצאה, חושבת על באמת

552
00:25:10,200 --> 00:25:12,962
איך כל אחד מהם עושים את זה,
איך אתה יכול לתאר את זה.

553
00:25:12,962 --> 00:25:15,045
כי שוב, אלה הם
כל התהליכים, האלגוריתמים

554
00:25:15,045 --> 00:25:17,090
שאנחנו לוקחים כמובן מאליו כבן אדם.

555
00:25:17,090 --> 00:25:22,349
אבל כנראה כבר היה לך ארוך
אינטואיציה, הרבה לפני שאתה אפילו

556
00:25:22,349 --> 00:25:24,390
חשב על לקחת
כיתת מדעי מחשבך

557
00:25:24,390 --> 00:25:27,223
אולי הייתה לה האינטואיציה עם
שכדי לפתור בעיות כמו זו.

558
00:25:27,223 --> 00:25:29,560
אבל ברגע שאתה מזהה
הדפוסים ולהתחיל

559
00:25:29,560 --> 00:25:32,407
למסד את הצעדים שבי
שאתה פותר את הבעיות האלה,

560
00:25:32,407 --> 00:25:35,490
אתה תמצא שאתה יכול לפתור הרבה
יותר מעניין והרבה יותר מורכב

561
00:25:35,490 --> 00:25:39,190
בעיות במהירות.

562
00:25:39,190 --> 00:25:42,351
אז מישהו מהקהל, מה שהוא
אלמנט אחד לפחות של האלגוריתם

563
00:25:42,351 --> 00:25:43,350
כי הם משתמשים כאן?

564
00:25:43,350 --> 00:25:44,275
>> קהל: [לא ברור]

565
00:25:44,275 --> 00:25:45,150
דובר: מה זה?

566
00:25:45,150 --> 00:25:47,062
קהל: עד תביעה.

567
00:25:47,062 --> 00:25:47,770
SPEAKER: על ידי חליפה.

568
00:25:47,770 --> 00:25:50,630
אז קודם כל הם אשכולות
כל היהלומים יחד

569
00:25:50,630 --> 00:25:52,560
זה כל נראה,
לבבות נראה,

570
00:25:52,560 --> 00:25:56,520
וכן הלאה, בלי הכבוד
למספרים על הכרטיסים.

571
00:25:56,520 --> 00:26:00,900
ועכשיו הם מופיעים, למשל,
להיות ממיין אותם לפי מספר.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
טוב מאוד.

574
00:26:08,910 --> 00:26:12,370
>> בסדר, אז מה קורה ל
להיות השלב האחרון אז כאן?

575
00:26:12,370 --> 00:26:16,950
ברגע שיש לנו ארבע חליפות ממוינות, מה ש
לעשות שאנחנו צריכים לעשות לארבע הערימות

576
00:26:16,950 --> 00:26:20,059
על מנת להשיג אחד
מסודרים על הסיפון, בפשטות?

577
00:26:20,059 --> 00:26:21,350
אז אנחנו צריכים למזג אותם שוב.

578
00:26:21,350 --> 00:26:25,160
>> אז יש רעיון מעניין ש
שוב, מעז לומר, הוא מאוד אינטואיטיבי אפילו

579
00:26:25,160 --> 00:26:28,140
אם אתה אולי מעולם לא סטר
סוג זה של תווית עליו.

580
00:26:28,140 --> 00:26:31,900
רעיון בסיסי זה של החלוקה
הבעיה לא במחצית הזמן הזה,

581
00:26:31,900 --> 00:26:33,410
אבל לפחות לארבעה חלקים.

582
00:26:33,410 --> 00:26:36,810
פתרון די הרבה
בעיות יסודו זהות

583
00:26:36,810 --> 00:26:40,480
בבידוד של אחד את השני,
ולאחר מכן מיזוג התוצאות.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
ו, מצוין, עשה.

586
00:26:50,140 --> 00:26:52,140
בסדר, גדול ועגול
של מחיאות כפיים, אם היינו יכול.

587
00:26:52,140 --> 00:26:56,480
>> [מחיאות כפות]

588
00:26:56,480 --> 00:26:59,740
>> דובר: אין לי מושג מה אתה
לעשות עם אלה, אבל הנה לך.

589
00:26:59,740 --> 00:27:01,690
תודה רבה לך.

590
00:27:01,690 --> 00:27:04,660
אז בואו לראות שתי, דקות
ושמונה שניות,

591
00:27:04,660 --> 00:27:07,490
אם אתה רוצה לאתגר את החברים שלך.

592
00:27:07,490 --> 00:27:12,160
אז מה הוא הולך
להיות לקחת מן זו

593
00:27:12,160 --> 00:27:13,830
שאנו יכולים למנף באופן כללי יותר?

594
00:27:13,830 --> 00:27:16,080
ובכן, חושב לחזור
מערך זה של מספרים,

595
00:27:16,080 --> 00:27:19,060
וחושב אחורה עכשיו לחלק
pseudocode אנחנו כבר נכתבו בעבר,

596
00:27:19,060 --> 00:27:22,080
וזה היה pseudocode ל
פתרון הבעיה בספר טלפונים.

597
00:27:22,080 --> 00:27:25,150
לפיה באני pseudocode
מנה דרך שיטתית יותר

598
00:27:25,150 --> 00:27:28,400
לתאר איך עשיתי מאוד אינטואיטיבי
אלגוריתם אנושי של חלוקת הטלפון

599
00:27:28,400 --> 00:27:31,650
ספר במחצית, חזור, חזור, חזור,
עד שאני מוצא מישהו כמו מייק סמית,

600
00:27:31,650 --> 00:27:33,790
אם הוא אכן בספר טלפונים.

601
00:27:33,790 --> 00:27:37,610
>> אבל אני סוג של שימוש מה אני אתקשר
גישה מאוד איטרטיבי כאן,

602
00:27:37,610 --> 00:27:42,160
בהודעה מיוחדת שורת 8 והשורה 11.

603
00:27:42,160 --> 00:27:46,750
אלה הם עדות לאיטרטיבי
גישה, גישת לולאות,

604
00:27:46,750 --> 00:27:49,040
כי זה בדיוק
התנהגותם לגרום.

605
00:27:49,040 --> 00:27:52,910
קווים אלה הן אומרים ללכת ל
סוג יכולים קו שלוש, ואתה של

606
00:27:52,910 --> 00:27:55,140
חשבתי על זה בך
בעיני רוח כלולאה.

607
00:27:55,140 --> 00:27:59,080
זה אומר לך לחזור עד שלב
שלוש ולחזור, שוב, ושוב,

608
00:27:59,080 --> 00:28:00,010
ושוב.

609
00:28:00,010 --> 00:28:04,410
>> אבל מה אם אנחנו למנף רעיון מרכזי
כאן שאנחנו לא בפעם האחרונה,

610
00:28:04,410 --> 00:28:10,280
ולפשט את הקו 8 ו
שורה 11 ושכניהם

611
00:28:10,280 --> 00:28:12,840
כרק זה, בצבע צהוב.

612
00:28:12,840 --> 00:28:16,480
זה לא ביסוד קיצור
pseudocode מאוד,

613
00:28:16,480 --> 00:28:20,530
אבל זה שינוי יסודי
טבעו של האלגוריתם שלי.

614
00:28:20,530 --> 00:28:24,220
מה שאני אומר עכשיו
בשלב 7, בשלב 10,

615
00:28:24,220 --> 00:28:29,140
הוא לחפש מייק
באותו אופן בדיוק,

616
00:28:29,140 --> 00:28:31,580
אבל רק בצד השמאל
מחצית או חצי הנכון.

617
00:28:31,580 --> 00:28:33,420
>> אז במילים אחרות, אם
אני מתחיל מצעד אחד,

618
00:28:33,420 --> 00:28:36,150
להרים ספר טלפונים, פתוח לאמצע
של ספר טלפונים, מסתכלים על שמות,

619
00:28:36,150 --> 00:28:39,010
אם סמית היא בין
שמו של, קורא מייק, אחר

620
00:28:39,010 --> 00:28:44,340
אם סמית היא מוקדם יותר בספר, צעד שבעה
לחפש את מייק במחצית השמאלית של ספר.

621
00:28:44,340 --> 00:28:47,130
אבל זה סוג של מרגיש כמו
זה משאיר אותי תלוי, נכון?

622
00:28:47,130 --> 00:28:49,240
בצהוב, הוא
הוראה, אבל איך אני

623
00:28:49,240 --> 00:28:51,870
לחפש את מייק בשמאל
מחצית מהספר טלפונים?

624
00:28:51,870 --> 00:28:54,210
איפה יש לי
אלגוריתם שבה אני

625
00:28:54,210 --> 00:28:57,100
יכול לחפש מישהו כמו מייק סמית?

626
00:28:57,100 --> 00:28:58,980
ובכן, זה בוהה לנו בפרצוף.

627
00:28:58,980 --> 00:29:03,090
אני ממש יכול להשתמש באותו מדויק
תכנית ביעילות הולכת עד לקצה

628
00:29:03,090 --> 00:29:06,490
וריצה מחדש שוב
אותו שורות קוד.

629
00:29:06,490 --> 00:29:10,610
>> למרות שכך זה צריך להרגיש
קצת כמו הגדרה מחזורית

630
00:29:10,610 --> 00:29:13,480
שבו אתה עונה למישהו זה
שאלה רק על ידי סוג של שואל

631
00:29:13,480 --> 00:29:15,990
את אותה השאלה שוב,
כמו למה, למה, למה?

632
00:29:15,990 --> 00:29:21,580
המציאות היא כי יש לנו קשה מקודדת
כמה שורות מיוחדות, שלב 4,

633
00:29:21,580 --> 00:29:25,320
אשר הוא אם, וצעד 12, ש
הוא למעשה סניף נוסף,

634
00:29:25,320 --> 00:29:30,120
כי יש לנו אמצעי הנגד הזמני האלה,
אלגוריתם זה יסתיים אם

635
00:29:30,120 --> 00:29:32,050
למצוא מייק, או אם אנחנו לא.

636
00:29:32,050 --> 00:29:36,810
אבל בשלב 7 ו10 עכשיו, יש לנו
מה אנחנו קוראים לאלגוריתם רקורסיבי.

637
00:29:36,810 --> 00:29:40,420
ורקורסיה היא אכן רעיון חזק
זה קצת מוח כיפוף בהתחלה,

638
00:29:40,420 --> 00:29:42,500
שאנחנו יכולים כעת ליישם באופן הבא.

639
00:29:42,500 --> 00:29:46,600
>> מיזוג מהסוג יהיה מהסוג האחרון ש
אנחנו מסתכלים, לפחות בכיתה באופן רשמי.

640
00:29:46,600 --> 00:29:50,040
וזה שונה במהותו
מאלו שלוש האחרונים, ובוודאי

641
00:29:50,040 --> 00:29:52,140
ארבעה האחרונים אם יכללו bogosort.

642
00:29:52,140 --> 00:29:54,810
הנה pseudocode לסוג מיזוג.

643
00:29:54,810 --> 00:30:00,170
כאשר בקלט של n אלמנטים, כך שניתנו
מערך בגודל n, אם n הוא פחות מ 2,

644
00:30:00,170 --> 00:30:01,040
לחזור.

645
00:30:01,040 --> 00:30:03,610
אז למה יש לי ש
שפיות לבדוק קודם?

646
00:30:03,610 --> 00:30:09,477
מה המשמעות אם אני נותן לך
מערך שאורכו n הוא פחות מ 2?

647
00:30:09,477 --> 00:30:11,060
זה כבר מסודרים, ברור, נכון?

648
00:30:11,060 --> 00:30:13,640
בגלל הרשימה או יש
אלמנט אחד, שהוא חסר חשיבות

649
00:30:13,640 --> 00:30:15,180
מסודרים כי זה
הדבר היחיד שיש.

650
00:30:15,180 --> 00:30:18,138
או, זה בגודל אפס שפירושו
אין שום דבר כדי למיין, זאת על ידי הטבע

651
00:30:18,138 --> 00:30:18,720
הוא מסודרים.

652
00:30:18,720 --> 00:30:20,410
יש רק דבר רע יש.

653
00:30:20,410 --> 00:30:22,310
אז זה מקרה הבסיס מה שנקרא שלנו.

654
00:30:22,310 --> 00:30:24,440
>> זה דומה ברוח
למה שעשינו עם מייק.

655
00:30:24,440 --> 00:30:26,023
אם מייק בספר טלפונים, להתקשר אליו.

656
00:30:26,023 --> 00:30:27,740
אם הוא לא שם, לוותר.

657
00:30:27,740 --> 00:30:31,240
זה מקרה בסיס מה שנקרא, כדי לוודא ש
אלגוריתם זה בסופו של היום

658
00:30:31,240 --> 00:30:33,540
יפסיק בנסיבות מסוימות.

659
00:30:33,540 --> 00:30:37,890
>> אבל הנה הקפיצה של אמונה עכשיו, אחרת,
למיין את המחצית השמאלית של האלמנטים,

660
00:30:37,890 --> 00:30:39,740
לאחר מכן למיין את הזכות
מחצית מהאלמנטים,

661
00:30:39,740 --> 00:30:41,189
ולאחר מכן למזג את החצאים מסודרים.

662
00:30:41,189 --> 00:30:43,230
וכאן זה מרגיש
כמו שאנחנו להשתמט.

663
00:30:43,230 --> 00:30:46,900
אני כבר שאלתי אותך למיין
n אלמנטים, ואני

664
00:30:46,900 --> 00:30:50,712
אומר, בסדר, עושה את זה על ידי מיון
עזב ומיון הנכון.

665
00:30:50,712 --> 00:30:52,420
אבל אני אומר אחד
דבר אחר, וזה

666
00:30:52,420 --> 00:30:55,530
הוא הנושא המרכזי זה נראה
באינטואיציה של עד כה,

667
00:30:55,530 --> 00:30:57,380
יש שלב שלישי זה של מיזוג.

668
00:30:57,380 --> 00:31:00,430
שלמרות שזה
נראה כל כך מטומטם ברוח,

669
00:31:00,430 --> 00:31:02,320
סתם למזג דברים
יחד, זה נראה

670
00:31:02,320 --> 00:31:05,380
להיות צעד מפתח לקראת
הרכבה מחדש של שתי בעיות ש

671
00:31:05,380 --> 00:31:07,330
חולקו סופו של דבר במחצית.

672
00:31:07,330 --> 00:31:12,090
>> אז למזג סוג, בואו נעשיתי את זה, אם תוכל
הומורי, עם הפגנה אחת יותר,

673
00:31:12,090 --> 00:31:14,730
פשוט כל כך שיש לנו כמה
מספרים לעבוד איתו.

674
00:31:14,730 --> 00:31:19,470
האם אני יכול להחליף שמונה מתח
כדורים לשמונה אנשים?

675
00:31:19,470 --> 00:31:29,320
בסדר, מה איתך שלושה, לך ארבעה
בסעיף זה, חמש, שש, ובואו

676
00:31:29,320 --> 00:31:30,720
אל 7, 8, בחייך עד.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
אישור, כן על אישור.

679
00:31:36,520 --> 00:31:38,640
מינוס 8, יש לנו ללכת, בתוספת 1.

680
00:31:38,640 --> 00:31:39,150
מצוין.

681
00:31:39,150 --> 00:31:42,000
בסדר בואו ניכנס, בואו
ייתנו לך במהירות מספרים.

682
00:31:42,000 --> 00:31:50,800
מספר שתיים, מספר שלוש, מספר ארבעה,
מספר חמש, שש, שבע, ושמונה.

683
00:31:50,800 --> 00:31:52,140
עשיתי שמונה הפעם בצורה נכונה.

684
00:31:52,140 --> 00:31:56,390
>> אישור, אז קדימה, אם אתה יכול, ו
בואו למיין לפי הסדר המקורי

685
00:31:56,390 --> 00:31:59,810
שהיינו לנו אתמול שנראו
ככה, אם לא היית אכפת לי.

686
00:31:59,810 --> 00:32:03,620
ובואו נעשיתי את זה מול השולחן.

687
00:32:03,620 --> 00:32:06,510
בסדר, אז למזג מיון.

688
00:32:06,510 --> 00:32:08,820
זה המקום שבו קורה
כדי לקבל סוג של מעניין,

689
00:32:08,820 --> 00:32:12,800
כי אני כאילו נותן את עצמי
כל כך הרבה פחות מידע כיום.

690
00:32:12,800 --> 00:32:15,149
>> אז למזג סוג הראשון של כל
על קלט של n אלמנטים,

691
00:32:15,149 --> 00:32:18,440
וכמובן לא פחות משני, זה
שמונה, אז יש לי עוד קצת עבודה לעשות.

692
00:32:18,440 --> 00:32:21,140
אז עכשיו מבחינה נפשית אנו כתובענה
נמצא כעת בסניף אחר,

693
00:32:21,140 --> 00:32:22,540
מה שאומר ששלושה שלבים.

694
00:32:22,540 --> 00:32:25,017
ראשית, אני צריך למיין
מחצית השמאלית של האלמנטים.

695
00:32:25,017 --> 00:32:26,350
אז איך אני הולך לעשות את זה?

696
00:32:26,350 --> 00:32:28,950
ובכן, אני הולך לסוג של
מבחינה נפשית לחלק את הרשימה כאן,

697
00:32:28,950 --> 00:32:30,700
אין לך ל
מבחינה פיזית לנוע, ואני

698
00:32:30,700 --> 00:32:33,180
הולך להתמקד רק על
מחצית השמאלית של האלמנטים כאן.

699
00:32:33,180 --> 00:32:36,770
אז איך אני הולך על מיון
רשימה עכשיו בגודל ארבעה?

700
00:32:36,770 --> 00:32:38,730
מה האלגוריתם שלי?

701
00:32:38,730 --> 00:32:42,580
ראשית אני בודק הוא n פחות משני, לא,
אז אני ממשיך לבלוק אחר שוב.

702
00:32:42,580 --> 00:32:43,900
מיין עזב מחצית מאלמנטים.

703
00:32:43,900 --> 00:32:45,608
>> אז עכשיו שוב, מבחינה נפשית,
וזה מקום שבי

704
00:32:45,608 --> 00:32:49,550
אתה צריך לצבור הרבה
היסטוריה נפשית, אם תרצה.

705
00:32:49,550 --> 00:32:51,940
עכשיו אני ממיין את השמאל
המחצית ממחצית השמאלית.

706
00:32:51,940 --> 00:32:57,000
בסדר, אז עכשיו אני קורא אותו המיזוג שלי
מיון אלגוריתם, הוא n פחות משני?

707
00:32:57,000 --> 00:33:00,590
לא, זה שתי, כך שאני צריך למיין
המחצית השמאלית, והחצי הימני.

708
00:33:00,590 --> 00:33:02,042
אז הנה זה באנו, למיין את המחצית עזבה.

709
00:33:02,042 --> 00:33:03,750
למה אתה לא פשוט
לקחת צעד אחד קדימה.

710
00:33:03,750 --> 00:33:04,415
מה שמך?

711
00:33:04,415 --> 00:33:04,860
>> קהל: דארן.

712
00:33:04,860 --> 00:33:05,260
>> דובר: דן.

713
00:33:05,260 --> 00:33:06,040
דן צעד קדימה.

714
00:33:06,040 --> 00:33:06,748
>> קהל: דארן.

715
00:33:06,748 --> 00:33:09,000
דובר: דארן, עשה.

716
00:33:09,000 --> 00:33:10,090
האם אתה אומר דארן או דן?

717
00:33:10,090 --> 00:33:10,550
>> קהל: דארן.

718
00:33:10,550 --> 00:33:11,216
>> דובר: דארן.

719
00:33:11,216 --> 00:33:14,422
אישור, דארן הגביר
קדימה וכעת הוא מסודרים.

720
00:33:14,422 --> 00:33:16,130
ואת זה הוא כמעט
טענה מטופשת, נכון?

721
00:33:16,130 --> 00:33:18,862
אני לא באמת נראה השגת
שום דבר, אבל בואו נמשיך.

722
00:33:18,862 --> 00:33:20,820
עכשיו תנו לי למיין את הזכות
מחצית מהאלמנטים.

723
00:33:20,820 --> 00:33:21,200
מה שמך?

724
00:33:21,200 --> 00:33:21,690
>> קהל: לוק.

725
00:33:21,690 --> 00:33:22,273
>> דובר: לוק.

726
00:33:22,273 --> 00:33:23,400
יאללה, לצעוד קדימה.

727
00:33:23,400 --> 00:33:25,640
עשה, יש לי מסודרים על לוק.

728
00:33:25,640 --> 00:33:28,570
והחצי השמאלי כעת מסודרים
החצי הימני הוא כעת מסודרים,

729
00:33:28,570 --> 00:33:30,770
אבל שוב, יש צעד מפתח כאן.

730
00:33:30,770 --> 00:33:32,940
מה אני הבא צריך לעשות?

731
00:33:32,940 --> 00:33:33,941
מיזוג החצאים מסודרים.

732
00:33:33,941 --> 00:33:36,648
עכשיו אנחנו הולכים רק כדי להיות
כולם הלוך ושוב בדרך זו,

733
00:33:36,648 --> 00:33:38,620
כי אני סוג של צריך
קצת מרחב מאפס.

734
00:33:38,620 --> 00:33:40,411
זה כמעט כמו אלה
החבר 'ה נמצא על שולחן,

735
00:33:40,411 --> 00:33:42,460
ואני צריך קצת חדר
לנוע סביבם ב.

736
00:33:42,460 --> 00:33:44,170
אז אני הולך למיזוג
אתם ע"י הסתכלות

737
00:33:44,170 --> 00:33:45,960
במחצית השמאלית וחצי תקין.

738
00:33:45,960 --> 00:33:48,740
וברור מי בא קודם,
מחצית שמאלה או ימינה חצי?

739
00:33:48,740 --> 00:33:52,710
כל כך נכון חצי, אז בואו נעבור לוק על
כאן לעמדתו המקורית של דארן.

740
00:33:52,710 --> 00:33:57,640
ועכשיו למזג המחצית השמאלית שלהם ב,
דארן הולך לעבור שם.

741
00:33:57,640 --> 00:33:59,750
>> אז מרגיש כמו כמעט
השפעת מיון בועות,

742
00:33:59,750 --> 00:34:02,482
אבל האלגוריתם הבסיסי שלי,
מאוד שונה הפעם.

743
00:34:02,482 --> 00:34:04,815
אבל עכשיו מקום שבו דברים מקבלים
קצת מעצבן, כי אתה

744
00:34:04,815 --> 00:34:06,810
צריך להריץ אחורה מבחינה נפשית
מאיפה אני משאיר את.

745
00:34:06,810 --> 00:34:09,893
אני פשוט התמזג חצאים הממוינים,
מה שאומר באלגוריתם שלי אני איפה?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
אני צריך למיין את החצי הימני, נכון?

748
00:34:13,770 --> 00:34:15,910
>> אם אתה אחורה, פשוטו כמשמעו
בווידאו, שתצליח

749
00:34:15,910 --> 00:34:18,339
רואה שיש לנו לזה
נקודה של לוק ודארן

750
00:34:18,339 --> 00:34:21,370
על ידי מיון השמאל
המחצית ממחצית השמאלית.

751
00:34:21,370 --> 00:34:23,430
אז אנחנו התמזגו אלה
חצאים ממוינים, ש

752
00:34:23,430 --> 00:34:27,941
משמעות הדבר היא השלב הבא הוא סוג
מחצית ימנית של החצי השמאלי.

753
00:34:27,941 --> 00:34:29,649
בסדר, אז בואו
לעשות את זה במהירות רבה יותר.

754
00:34:29,649 --> 00:34:33,282
בסדר, שש, אני הולך לתבוע
אתה עכשיו מסודרים, לבוא על קדימה.

755
00:34:33,282 --> 00:34:33,990
מה שמך?

756
00:34:33,990 --> 00:34:34,589
>> קהל: אדריאנו.

757
00:34:34,589 --> 00:34:35,200
>> דובר: אדריאנו.

758
00:34:35,200 --> 00:34:36,010
אדריאנו כעת מסודרים.

759
00:34:36,010 --> 00:34:36,450
ואיך קוראים לך?

760
00:34:36,450 --> 00:34:37,080
>> קהל: אלכס.

761
00:34:37,080 --> 00:34:38,379
>> הדובר: אלכס כעת מסודרים.

762
00:34:38,379 --> 00:34:40,750
מחצית שמאלה, ימינה מחצית,
מה השלב האחרון?

763
00:34:40,750 --> 00:34:41,250
מיזוג.

764
00:34:41,250 --> 00:34:44,310
די טריוויאלי, ולכן אני
הולך למזג בשש,

765
00:34:44,310 --> 00:34:46,930
לקחת צעד אחורה,
שמונה, לקחת צעד אחורה.

766
00:34:46,930 --> 00:34:49,530
ועכשיו שם לב שזה
אוכל מוכן שימושי, מה ש

767
00:34:49,530 --> 00:34:53,930
עכשיו אמיתי על החצי השמאלי של
רשימה, ללא קשר לאופן בו אנו החלו?

768
00:34:53,930 --> 00:34:55,090
הוא מסודרים.

769
00:34:55,090 --> 00:34:57,750
>> עכשיו זה לא מסודרים ב
התכנית הגדולה של דברים,

770
00:34:57,750 --> 00:35:00,250
אבל הוא מסודרים באופן עצמאי
של החצי השני.

771
00:35:00,250 --> 00:35:04,100
עכשיו מה צעד אני באם אני שומר
אחורה איך הסיפור התחיל?

772
00:35:04,100 --> 00:35:05,680
עכשיו אני צריך למיין חצי תקין.

773
00:35:05,680 --> 00:35:07,630
אז עכשיו אנחנו בדרך חזרה ב
תחילתו של הסיפור,

774
00:35:07,630 --> 00:35:08,921
ובואו נעשיתי את זה במהירות רבה יותר.

775
00:35:08,921 --> 00:35:11,320
אז אני הולך כדי למיין את
מחצית ימנית של כל הרשימה.

776
00:35:11,320 --> 00:35:13,060
מה הצעד הבא?

777
00:35:13,060 --> 00:35:15,840
למיין את המחצית השמאלית של החצי הימני.

778
00:35:15,840 --> 00:35:18,715
למיין את המחצית השמאלית של
מחצית השמאלית של החצי הימני.

779
00:35:18,715 --> 00:35:19,590
ואיך קוראים לך?

780
00:35:19,590 --> 00:35:20,230
>> קהל: עומר.

781
00:35:20,230 --> 00:35:21,970
>> הדובר: עומר, לצעוד קדימה, לעשות.

782
00:35:21,970 --> 00:35:22,860
מחצית השמאלית ממוינת.

783
00:35:22,860 --> 00:35:23,330
ואיך קוראים לך?

784
00:35:23,330 --> 00:35:23,820
>> קהל: כריס.

785
00:35:23,820 --> 00:35:25,620
>> דובר: כריס, לקחת צעד
קדימה, לך עכשיו מסודרים.

786
00:35:25,620 --> 00:35:27,010
מה צעד מפתח עכשיו?

787
00:35:27,010 --> 00:35:27,510
מיזוג.

788
00:35:27,510 --> 00:35:30,509
אז אחד לא הולך להתמזג לתוך המקום
כאן, אם אתה יכול לקחת צעד אחורה,

789
00:35:30,509 --> 00:35:32,930
ושלוש הולכים
לקחת צעד אחורה, למזג.

790
00:35:32,930 --> 00:35:38,080
אז המחצית השמאלית של
נכון מחצית, כעת מסודרים.

791
00:35:38,080 --> 00:35:41,747
למען האמת, אלגוריתם זה מרגיש כאילו אנחנו
מבזבזים הרבה יותר זמן מאשר בעבר,

792
00:35:41,747 --> 00:35:44,830
אבל אם עשינו את זה בזמן אמת, אנחנו
לראות מה המזנונים הולכים להיות.

793
00:35:44,830 --> 00:35:47,970
עכשיו הנה אני כאן, נכון
המחצית ממחצית הימנית,

794
00:35:47,970 --> 00:35:50,170
תן לי ללכת קדימה ולמיין את המחצית השמאלית.

795
00:35:50,170 --> 00:35:51,482
צעד קדימה, מה השם שלך?

796
00:35:51,482 --> 00:35:52,190
קהל: Ramsey.

797
00:35:52,190 --> 00:35:53,210
הדובר: Ramsey כעת מסודרים.

798
00:35:53,210 --> 00:35:53,570
מה שמך?

799
00:35:53,570 --> 00:35:54,200
>> קהל: מרינה.

800
00:35:54,200 --> 00:35:57,033
>> הדובר: מרינה כעת מסודרים כ
גם, אם אתה לוקח צעד אחד קדימה.

801
00:35:57,033 --> 00:36:00,690
צעד מפתח כאן הוא עכשיו למזג, אני
הולך לקטוף משתי הרשימות שלי,

802
00:36:00,690 --> 00:36:01,720
משמאל ומימין.

803
00:36:01,720 --> 00:36:05,150
חמש עומדים לבוא ראשון,
ושבע הולכים לבוא הבא.

804
00:36:05,150 --> 00:36:06,410
ושוב, זה הוא מכוון.

805
00:36:06,410 --> 00:36:08,535
העובדה שהם לוקחים
צעדים קדימה ואחורה

806
00:36:08,535 --> 00:36:12,997
הוא אמור לייצג כי אנחנו לא יכולים
לעשות אלגוריתם זה במקום באותה קלות

807
00:36:12,997 --> 00:36:15,830
כמיון בועות, ומיון בחירה,
וסוג ההכנסה שבו אנחנו פשוט

808
00:36:15,830 --> 00:36:16,960
המשיך להחליף אנשים.

809
00:36:16,960 --> 00:36:19,940
אני ממש זקוק לסוג
נייר שריטה שבי

810
00:36:19,940 --> 00:36:21,827
לשים האנשים האלה
בזמן שאני עושה מיזוג,

811
00:36:21,827 --> 00:36:23,410
ואז אני יכול לשים אותם בחזרה למקומו.

812
00:36:23,410 --> 00:36:27,260
וזה מפתח, כי אני משתמש
משאב חדש, חלל, לא רק זמן.

813
00:36:27,260 --> 00:36:28,270
>> אוקיי, זה מדהים.

814
00:36:28,270 --> 00:36:32,050
המחצית עזבה ממוינת, תקין מחצית היא
צעד. ממוין, עכשיו מפתח שמתמזג

815
00:36:32,050 --> 00:36:33,450
איך אני הולך להתמזג זה?

816
00:36:33,450 --> 00:36:35,470
אז אם יעקוב אחר
יד שמאל ויד ימין,

817
00:36:35,470 --> 00:36:38,930
אני הולך להצביע לי את יד שמאל
במחצית השמאלית, יד ימין שלי

818
00:36:38,930 --> 00:36:42,680
בחצי הימני, ועכשיו אני צריך
להחליט צעד אחר צעדם להתמזג ב.

819
00:36:42,680 --> 00:36:44,650
מי ברור שיבוא קודם?

820
00:36:44,650 --> 00:36:45,150
מספר אחד.

821
00:36:45,150 --> 00:36:47,327
אז תבוא לכאן ב,
הנה הדפדפת שלנו.

822
00:36:47,327 --> 00:36:49,910
אז עכשיו מספר אחד, והודעה
מה אני אעשה עם יד ימין שלי,

823
00:36:49,910 --> 00:36:54,152
אני הולך להזיז את יד ימין שלי אחד
לדרוך על לנקודת מספר שלוש,

824
00:36:54,152 --> 00:36:55,860
ועכשיו אני צריך לעשות
אותה ההחלטה.

825
00:36:55,860 --> 00:36:58,387
ולמעשה עומד ממש ב
מול לוק כאן אם אתה יכול,

826
00:36:58,387 --> 00:36:59,720
בגלל זה הוא הדפדפת שלנו.

827
00:36:59,720 --> 00:37:00,610
אז מי שבא ליד?

828
00:37:00,610 --> 00:37:05,000
יש לנו לוק עם מספר שתיים
או כריס עם מספר שלוש.

829
00:37:05,000 --> 00:37:07,460
מספר ברור לוק,
שני, כך שאתה בא לכאן.

830
00:37:07,460 --> 00:37:11,270
>> אבל יד השמאל שלי עכשיו הוא הולכת
להיות מוגדל להצביע על דארן,

831
00:37:11,270 --> 00:37:15,160
והנה לקחת את המפתח משם עם
מיזוג, אני הולך להמשיך לעשות את זה,

832
00:37:15,160 --> 00:37:17,340
כמובן, אם אתה סוג
של מעקב ההיגיון.

833
00:37:17,340 --> 00:37:19,670
אבל הידיים שלי אף פעם לא
הולך אחורה,

834
00:37:19,670 --> 00:37:23,861
מה שאומר שאני היחיד שאי פעם אני עובר ל
נשאר עם תהליך המיזוג שלי,

835
00:37:23,861 --> 00:37:26,360
וזה הולך להיות מפתח ל
הניתוח שלנו ברגע.

836
00:37:26,360 --> 00:37:27,859
>> אז עכשיו בואו נסיים את זה במהירות.

837
00:37:27,859 --> 00:37:31,650
אז שלוש שבאו ליד,
לאחר מכן ארבעה מגיעים הבא,

838
00:37:31,650 --> 00:37:38,750
ועכשיו חמישה מגיע הבאה, ולאחר מכן שש,
ושבע, ולאחר מכן סוף סוף שמונה.

839
00:37:38,750 --> 00:37:42,960
מרגיש כמו האלגוריתם האיטי ביותר
עדיין, אבל לא אם אנחנו באמת

840
00:37:42,960 --> 00:37:45,510
להפעיל אותו באותו הסוג
של מהירות שעון, כך ל

841
00:37:45,510 --> 00:37:48,106
לדבר, עם אותו
שעון מתקתק כמו קודם.

842
00:37:48,106 --> 00:37:48,605
למה?

843
00:37:48,605 --> 00:37:51,100
ובכן, בואו ניקח
מסתכל על התוצאה הסופית.

844
00:37:51,100 --> 00:37:56,990
>> בואו נחזור לכאן, תן לי
למשוך את הפגנה חזותית

845
00:37:56,990 --> 00:37:59,030
של מה שאנחנו פשוט לא.

846
00:37:59,030 --> 00:38:06,110
התקרבות כאן, על זה
דף כאן, אומר לי פיירפוקס

847
00:38:06,110 --> 00:38:08,200
כי אנחנו רוצים לעמוד בתור
בתיבה זו, בואו

848
00:38:08,200 --> 00:38:11,260
אומר מיון בועות, שבה
אנחנו עכשיו מכירים היטב,

849
00:38:11,260 --> 00:38:14,130
מיון בחירה, וזה עוד
פשוט למדי אחד,

850
00:38:14,130 --> 00:38:18,250
ועכשיו סוג המיזוג של היום, שבי
יהיה סוף השיא שלנו.

851
00:38:18,250 --> 00:38:21,530
הסיבה שזה לקח כל כך הרבה זמן
כאן עם בני אדם ולי באופן מילולי הוא,

852
00:38:21,530 --> 00:38:23,480
כמובן, אני מסביר כל שלב ושלב.

853
00:38:23,480 --> 00:38:26,920
אבל אם אתה פשוט לבצע את זה, הרבה
מיון בועות כמו שעשינו ובחירה

854
00:38:26,920 --> 00:38:30,890
סוג לא רק מבחינה ויזואלית, שעון
עד כמה ביעילות רבה יותר

855
00:38:30,890 --> 00:38:33,330
מינוף זה של
החלוקה וכיבוש

856
00:38:33,330 --> 00:38:39,150
יכול להיות מיושם כאשר לערכת נתונים זה
אפילו לא בגודל שמונה, אבל גם הרבה,

857
00:38:39,150 --> 00:38:39,970
הרבה יותר גדול.

858
00:38:39,970 --> 00:38:44,585
אני נותן לך למזג סוג, צד על ידי
צד עם אלגוריתמים אחרים אלה.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
זה הולך לקבל כואב
במהירות, ואת הסוף

861
00:38:58,530 --> 00:39:00,890
לא במיוחד שיא,
הם פשוט בסופו של מיון.

862
00:39:00,890 --> 00:39:05,280
אבל המפתח לקחת הוא ש
תראה כמה הרבה יותר מהר למזג סוג

863
00:39:05,280 --> 00:39:08,110
היה, אלא אם כן אתה חושב שאני
פשוט סוג של להתעסק איתך.

864
00:39:08,110 --> 00:39:13,100
אם אנחנו עושים בזמן אחרון זה אחד,
בואו רענן, בואו נחזור

865
00:39:13,100 --> 00:39:14,960
ולבחור מיון בועות,
וסתם בשביל כיף,

866
00:39:14,960 --> 00:39:17,330
בואו לבחור הכנסה
סוג, רק למען סדר טוב.

867
00:39:17,330 --> 00:39:20,020
והפעם שוב, בואו
לבחור סוג המיזוג ובואו

868
00:39:20,020 --> 00:39:21,595
למעשה מנוהל על הצד אלה על ידי צד.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> וזה לא, למעשה, מזל.

871
00:39:26,930 --> 00:39:31,140
מה יעילות שעשיתי הוא לי
מחולק הקלט שלי במחצית, שוב,

872
00:39:31,140 --> 00:39:32,240
ושוב, ושוב.

873
00:39:32,240 --> 00:39:35,590
ויש רק כל כך הרבה פעמים שאתה יכול
לחלק את הקלט שלך לחצאים, עזב

874
00:39:35,590 --> 00:39:36,240
ונכון.

875
00:39:36,240 --> 00:39:39,425
מה הנוסחה שאנו ממשיכים לראות
המתאר את החלוקה במחצית

876
00:39:39,425 --> 00:39:41,050
שוב, ושוב, ושוב, ושוב?

877
00:39:41,050 --> 00:39:41,890
>> קהל: התחבר n.

878
00:39:41,890 --> 00:39:42,760
>> דובר: התחבר n.

879
00:39:42,760 --> 00:39:46,300
אבל אז יש צעד מפתח אחר אחד,
אלגוריתם זה אינו לוג n צעדים.

880
00:39:46,300 --> 00:39:48,992
אם זה רק היה להיכנס n צעדים,
היינו באותה הבעיה

881
00:39:48,992 --> 00:39:51,200
כמו קודם שבו אנחנו לא יכולים להיות
בטוח הכל מסודרים.

882
00:39:51,200 --> 00:39:54,480
אתה צריך להסתכל בצורה מינימאלית באלמנטי n
כדי להיות בטוח n אלמנטים מסודרים,

883
00:39:54,480 --> 00:39:55,950
אחר זה קפיצה של אמונה.

884
00:39:55,950 --> 00:39:59,810
>> אז זה יומן מינימאלי n צעדים, אבל
מה עם צעד מיזוג מפתח זה

885
00:39:59,810 --> 00:40:04,370
איפה אני התמזג המחצית השמאלית שלי ותקין
מחצית וחצתה את הבמה?

886
00:40:04,370 --> 00:40:06,980
כמה צעדים הוא שלהתמזג?

887
00:40:06,980 --> 00:40:10,150
זה n, אבל אני לא עשיתי בדיוק
למזג את הזמן הסופי.

888
00:40:10,150 --> 00:40:15,089
על כל אחד משיחות המקוננות אלה, על כל
של מיזוגים מקוננים אלה, אני עדיין מסודרים.

889
00:40:15,089 --> 00:40:18,380
אני התמזג שני החבר 'ה האלה, אז שני אלה
חבר 'ה, אז שני החבר' ה האלה וכן הלאה.

890
00:40:18,380 --> 00:40:19,955
>> אז אני לא מתמזג שוב, ושוב.

891
00:40:19,955 --> 00:40:20,580
כמה פעמים?

892
00:40:20,580 --> 00:40:23,510
אז כל פעם שאני חילקתי את
רשימה במחצית, שעשיתי מיזוג.

893
00:40:23,510 --> 00:40:25,460
מחלקים את הרשימה במחצית, לעשות מיזוג.

894
00:40:25,460 --> 00:40:28,570
אז אם מחלק את הרשימה
ניתן לעשות זאת פעמים n היומן,

895
00:40:28,570 --> 00:40:33,880
והתמזגות סופו של דבר לוקחת n
צעדים, מה שעשויים להיות עכשיו העליונים

896
00:40:33,880 --> 00:40:37,000
מחויב בריצה
זמן של האלגוריתם שלנו?

897
00:40:37,000 --> 00:40:37,980
n להתחבר n.

898
00:40:37,980 --> 00:40:40,560
>> ואכן, זה מה ש
שהשגנו כאן.

899
00:40:40,560 --> 00:40:44,650
אז את מרגיש שאתה רואה מבחינה ויזואלית כאשר
שלושת הדברים האלה לרוץ זה לצד זה

900
00:40:44,650 --> 00:40:47,930
בריבוע n נגד n
בריבוע נגד n יומן n.

901
00:40:47,930 --> 00:40:51,010
אשר ביסודו תוכל לראות,
לא רק היום אלא גם בעתיד,

902
00:40:51,010 --> 00:40:52,760
הרבה, הרבה יותר מהר.

903
00:40:52,760 --> 00:40:56,010
מחיאות כפיים לבחורים האלה,
אני יגמול אותם עם כדורי לחץ.

904
00:40:56,010 --> 00:41:00,260
בואו לדחות כאן היום, ו
אנחנו רואים אותך ביום שני.

905
00:41:00,260 --> 00:41:02,255