1
00:00:00,000 --> 00:00:00,990

2
00:00:00,990 --> 00:00:02,970
>> [השמעת מוסיקה]

3
00:00:02,970 --> 00:00:10,400

4
00:00:10,400 --> 00:00:12,550
>> דוד י מלאן: זה CS50.

5
00:00:12,550 --> 00:00:14,612
וזה הוא ההתחלה של שבוע שלושה.

6
00:00:14,612 --> 00:00:16,820
אז יש לנו הרבה מרגש
דברים כדי לכסות היום.

7
00:00:16,820 --> 00:00:20,160
הרבה הזדמנויות ל
מתנדב על במה.

8
00:00:20,160 --> 00:00:22,780
וסופו של דבר, היום הוא
לא על קוד בכל.

9
00:00:22,780 --> 00:00:24,820
אבל זה על רעיונות, ו
זה על אלגוריתמים,

10
00:00:24,820 --> 00:00:28,420
ומביא למעשה בחזרה חלק מ
הלקחים שנלמדו מהשבוע אפס,

11
00:00:28,420 --> 00:00:31,910
בי כזכור, אנחנו
הציג מפלצתי הזה.

12
00:00:31,910 --> 00:00:33,880
והשראה אשראי
מזה, להתחיל

13
00:00:33,880 --> 00:00:36,879
כדי לפתור אי פעם מתוחכם יותר
בעיות אלגוריתמית.

14
00:00:36,879 --> 00:00:38,420
אבל קודם, כמה הודעות.

15
00:00:38,420 --> 00:00:42,020
אז אחת, אם ברצונך להצטרף ל
צוות של CS50 וחבריו לכיתה בארוחת הצהריים

16
00:00:42,020 --> 00:00:44,670
ביום שישי הקרוב, גם כאן וגם ב
קיימברידג ', ובניו הייבן,

17
00:00:44,670 --> 00:00:48,060
בקר בקורס של
אתר, שבו ניתן למצוא את כתובת אתר.

18
00:00:48,060 --> 00:00:50,390
הרצאה ביום רביעי יהיה
לא יהיה כאן בסנדרס.

19
00:00:50,390 --> 00:00:53,610
זה יהיה רק ​​באינטרנט, ולכן
מנגינה באתר של CS50,

20
00:00:53,610 --> 00:00:55,850
אם כאן בקיימברידג '
או ניו הייבן, כמו גם.

21
00:00:55,850 --> 00:00:58,110
>> ואז בעיה להגדיר שתי
כבר נמצא בידיים שלך.

22
00:00:58,110 --> 00:01:03,067
אם לא צלל בבכל זאת, הרשה לי
להציע הצעה החריפה

23
00:01:03,067 --> 00:01:05,150
ש, במיוחד עכשיו, כ
הבעיה קובעת מראש,

24
00:01:05,150 --> 00:01:08,669
אתה באמת רוצה להתחיל עכשיו, אם לא
להשתכשך קצת בסוף השבוע או לפני

25
00:01:08,669 --> 00:01:10,710
כשהם יוצאים ראשון ב
ימי שישי, כי אתה

26
00:01:10,710 --> 00:01:14,380
למצוא שהם לא בהכרח
מקבל יותר ויותר מאתגרים ל

27
00:01:14,380 --> 00:01:14,950
SE.

28
00:01:14,950 --> 00:01:17,575
אני חושב שאתה תמצא כי, ב
כללי, הם נוטים לקחת פחות או יותר

29
00:01:17,575 --> 00:01:18,892
סביב אותה כמות של זמן.

30
00:01:18,892 --> 00:01:20,850
אבל זה בהחלט תלוי
על התלמיד, וזה

31
00:01:20,850 --> 00:01:22,880
תלוי בהלך הרוח
שבה אתה להתקרב אליו.

32
00:01:22,880 --> 00:01:24,910
אבל תמיד, אתה הולך
לרוץ נגד כמה קיר,

33
00:01:24,910 --> 00:01:26,350
ואתה הולך להכות
כמה באגים, ואתה פשוט

34
00:01:26,350 --> 00:01:27,950
לא הולך להיות מסוגל
להתגבר על זה בשלב מסוים.

35
00:01:27,950 --> 00:01:31,380
וזה הרבה מאוד יקר כדי להיות מסוגל
להתרחק, לחזור למחרת,

36
00:01:31,380 --> 00:01:35,286
ללכת לשעתי עבודה, הודעה על דיון CS50
או כמו, כדי לקבל חסימה בפועל.

37
00:01:35,286 --> 00:01:36,160
אז לשמור את זה בחשבון.

38
00:01:36,160 --> 00:01:40,830
החל מוקדמים ככל האפשר
זה הדבר הטוב ביותר שאתה יכול לעשות.

39
00:01:40,830 --> 00:01:44,160
אז הנה מקום שבו התחלנו
הכיתה, מעל בשבוע אפס.

40
00:01:44,160 --> 00:01:47,441
ואנחנו יכולים לקבל מתנדבים
כאן כדי לעזור לי למצוא את מיקרופונים?

41
00:01:47,441 --> 00:01:47,940
אוקיי.

42
00:01:47,940 --> 00:01:48,900
עמידה כבר.

43
00:01:48,900 --> 00:01:50,080
בואו למעלה.

44
00:01:50,080 --> 00:01:53,707
מניח שזה איך זה הולך לעבוד.

45
00:01:53,707 --> 00:01:54,415
מה השם שלך?

46
00:01:54,415 --> 00:01:55,570
ALAN אסטרדה: אלן אסטרדה.

47
00:01:55,570 --> 00:01:56,778
דוד י מלאן: אלן אסטרדה.

48
00:01:56,778 --> 00:01:57,910
בואו למעלה.

49
00:01:57,910 --> 00:01:58,619
נחמד לפגוש אותך.

50
00:01:58,619 --> 00:01:59,910
ALAN אסטרדה: נחמד לפגוש אותך.

51
00:01:59,910 --> 00:02:02,772
דוד י מלאן: ואתה היית כאן
איתנו בשבוע אפס, כמובן.

52
00:02:02,772 --> 00:02:03,028
ALAN אסטרדה: הייתי.

53
00:02:03,028 --> 00:02:03,160
הייתי.

54
00:02:03,160 --> 00:02:05,868
>> דוד י מלאן: אז אתה יכול ללכת
קדימה ולמצוא לנו מייק סמית,

55
00:02:05,868 --> 00:02:08,639
הכי מהר שאתה יכול?

56
00:02:08,639 --> 00:02:10,639
הכי מהר שאתה יכול.

57
00:02:10,639 --> 00:02:13,756
פשוטו כמשמעו, קורע את הבעיה
במחצית כמו שאתה צריך.

58
00:02:13,756 --> 00:02:15,130
>> ALAN אסטרדה: אום.

59
00:02:15,130 --> 00:02:17,380
דוד י מלאן: פשוטו כמשמעו
קורע את הבעיה במחצית.

60
00:02:17,380 --> 00:02:20,210

61
00:02:20,210 --> 00:02:22,083
>> ALAN אסטרדה: אה.

62
00:02:22,083 --> 00:02:22,583
מ"מ.

63
00:02:22,583 --> 00:02:23,300
טוב מאד.

64
00:02:23,300 --> 00:02:23,700
>> דוד י מלאן: אישור.

65
00:02:23,700 --> 00:02:24,200
טוב.

66
00:02:24,200 --> 00:02:24,701
תודה.

67
00:02:24,701 --> 00:02:25,700
ALAN אסטרדה: טוב מאוד.

68
00:02:25,700 --> 00:02:26,210
אוקיי.

69
00:02:26,210 --> 00:02:27,610
>> דוד י מלאן: אז עכשיו,
שגלפת אותו

70
00:02:27,610 --> 00:02:29,320
למחצית מגודלה של הבעיה.

71
00:02:29,320 --> 00:02:31,267
עכשיו, אנחנו למטה לרבעון.

72
00:02:31,267 --> 00:02:33,475
האם אתה שם לב ל
באיזה צד אנחנו שומרים?

73
00:02:33,475 --> 00:02:34,405
>> [צוחק]

74
00:02:34,405 --> 00:02:35,970
>> ALAN אסטרדה: כן, אני חושב--

75
00:02:35,970 --> 00:02:37,594
>> דוד י מלאן: מה קטע הם שאנחנו ב?

76
00:02:37,594 --> 00:02:39,150
ALAN אסטרדה: עמעם, כך.

77
00:02:39,150 --> 00:02:39,941
>> דוד י מלאן: אישור.

78
00:02:39,941 --> 00:02:42,810
אבל מייק סמית הולכת
להיות אחרי עמעם.

79
00:02:42,810 --> 00:02:44,130
אז--

80
00:02:44,130 --> 00:02:48,180
>> [צוחק]

81
00:02:48,180 --> 00:02:48,742
>> בסדר.

82
00:02:48,742 --> 00:02:50,200
ALAN אסטרדה: לאן אנחנו מחפשים?

83
00:02:50,200 --> 00:02:52,049
דוד י מלאן: מייק סמית.

84
00:02:52,049 --> 00:02:53,090
ALAN אסטרדה: מייק סמית.

85
00:02:53,090 --> 00:02:54,760
דוד י מלאן: עכשיו, אנחנו בניתוח.

86
00:02:54,760 --> 00:02:57,840
עכשיו, רופאים.

87
00:02:57,840 --> 00:02:58,340
Now--

88
00:02:58,340 --> 00:02:59,856
>> ALAN אסטרדה: Let's- בואו נלך עם אמת.

89
00:02:59,856 --> 00:03:00,370
אמיתי.

90
00:03:00,370 --> 00:03:00,970
>> דוד י מלאן: נדל.

91
00:03:00,970 --> 00:03:01,470
אוקיי.

92
00:03:01,470 --> 00:03:03,700
אם אתה צורך אמיתי.

93
00:03:03,700 --> 00:03:05,250
עכשיו, שהדרך היא מייק סמית?

94
00:03:05,250 --> 00:03:06,250
>> ALAN אסטרדה: בדרך זו.

95
00:03:06,250 --> 00:03:07,333
>> דוד י מלאן: באיזו דרך?

96
00:03:07,333 --> 00:03:08,240
ALAN אסטרדה: המתן.

97
00:03:08,240 --> 00:03:08,790
הנכון הוא-- M?

98
00:03:08,790 --> 00:03:09,110
התחלנו with--

99
00:03:09,110 --> 00:03:10,090
>> דוד י מלאן: כן.

100
00:03:10,090 --> 00:03:10,650
הם עזבו.

101
00:03:10,650 --> 00:03:11,430
זכותך.

102
00:03:11,430 --> 00:03:11,710
>> ALAN אסטרדה: כן.

103
00:03:11,710 --> 00:03:13,126
>> דוד י מלאן: אז מייק בכאן.

104
00:03:13,126 --> 00:03:13,990
ALAN אסטרדה: מה?

105
00:03:13,990 --> 00:03:14,665
>> [צוחק]

106
00:03:14,665 --> 00:03:17,365

107
00:03:17,365 --> 00:03:18,330
>> דוגמא רעה, בחורים.

108
00:03:18,330 --> 00:03:18,830
מצטער.

109
00:03:18,830 --> 00:03:21,610
דוד י מלאן: זה ילמד
לך לקפוץ מהכיסא שלך.

110
00:03:21,610 --> 00:03:22,318
>> ALAN אסטרדה: אה.

111
00:03:22,318 --> 00:03:22,890
אה.

112
00:03:22,890 --> 00:03:23,390
השגתי אותך.

113
00:03:23,390 --> 00:03:24,670
השגתי אותך.

114
00:03:24,670 --> 00:03:25,170
אה.

115
00:03:25,170 --> 00:03:25,669
אה.

116
00:03:25,669 --> 00:03:26,812
זה הוא-- אישור, יש לי אותך.

117
00:03:26,812 --> 00:03:27,520
סמית 'כאן?

118
00:03:27,520 --> 00:03:28,894
>> דוד י מלאן: סמית ', תודה לך.

119
00:03:28,894 --> 00:03:30,535
אז אני אמשיך לחפש את סמית '?

120
00:03:30,535 --> 00:03:30,790
>> ALAN אסטרדה: הו, כן.

121
00:03:30,790 --> 00:03:31,340
לא לא לא.

122
00:03:31,340 --> 00:03:31,600
אוי לא.

123
00:03:31,600 --> 00:03:31,940
זה שלי.

124
00:03:31,940 --> 00:03:32,580
>> דוד י מלאן: אה, יש לך סמית.

125
00:03:32,580 --> 00:03:33,415
אוקיי.

126
00:03:33,415 --> 00:03:34,040
>> ALAN אסטרדה: כן, אני
יש לי סמית ממש כאן.

127
00:03:34,040 --> 00:03:34,700
מצטער, חבר'ה.

128
00:03:34,700 --> 00:03:35,860
חשבתי Michael--
חיפשנו מיכאל.

129
00:03:35,860 --> 00:03:36,550
מצטער.

130
00:03:36,550 --> 00:03:37,550
>> דוד י מלאן: זה בסדר.

131
00:03:37,550 --> 00:03:39,950
בסדר, עכשיו אנחנו
לPaccini ובניו.

132
00:03:39,950 --> 00:03:41,242
>> ALAN אסטרדה: Paccini ובנים.

133
00:03:41,242 --> 00:03:43,158
דוד י מלאן: רק אתה
ואני נמצא בזה.

134
00:03:43,158 --> 00:03:44,050
אוקיי.

135
00:03:44,050 --> 00:03:45,130
מצא אותנו מייק סמית.

136
00:03:45,130 --> 00:03:45,830
סמית '.

137
00:03:45,830 --> 00:03:46,310
>> ALAN אסטרדה: סמית '.

138
00:03:46,310 --> 00:03:46,750
>> דוד י מלאן: סמית '.

139
00:03:46,750 --> 00:03:47,728
אנחנו בR זבל.

140
00:03:47,728 --> 00:03:48,644
ALAN אסטרדה: שטויות.

141
00:03:48,644 --> 00:03:50,096
אה.

142
00:03:50,096 --> 00:03:52,480
זה הולך לקחת זמן.

143
00:03:52,480 --> 00:03:54,340
>> [צוחק]

144
00:03:54,340 --> 00:03:55,804

145
00:03:55,804 --> 00:03:56,720
דוד י מלאן: נעליים.

146
00:03:56,720 --> 00:03:58,080
אנחנו בנעליים.

147
00:03:58,080 --> 00:04:00,210
>> ALAN אסטרדה: עכשיו אנחנו gonna--

148
00:04:00,210 --> 00:04:01,105
>> דוד י מלאן: נחמד.

149
00:04:01,105 --> 00:04:01,980
ALAN אסטרדה: Which--

150
00:04:01,980 --> 00:04:03,620
[צוחק]

151
00:04:03,620 --> 00:04:05,440
הו, זה נהדר.

152
00:04:05,440 --> 00:04:06,910
[צוחק]

153
00:04:06,910 --> 00:04:08,380

154
00:04:08,380 --> 00:04:09,390
>> דוד י מלאן: זה בסדר.

155
00:04:09,390 --> 00:04:11,365
>> ALAN אסטרדה: אה, זה טוב.

156
00:04:11,365 --> 00:04:14,425
אני לא חושב שאני הולך
יש חברי PSAT אחרי זה.

157
00:04:14,425 --> 00:04:15,300
דוד י מלאן: טוב.

158
00:04:15,300 --> 00:04:16,078
ספורט.

159
00:04:16,078 --> 00:04:17,036
ALAN אסטרדה: ספורט.

160
00:04:17,036 --> 00:04:18,668
אום, L, M, N, O, פ

161
00:04:18,668 --> 00:04:19,459
דוד י מלאן: אישור.

162
00:04:19,459 --> 00:04:21,600
אז בואו לקרוע זה במחצית.

163
00:04:21,600 --> 00:04:22,270
זה בסדר.

164
00:04:22,270 --> 00:04:25,606
זה מסתיים בצורה גרועה בכל מקרה, בגלל מייק
סמית 'לא תהיה בדפי הזהב.

165
00:04:25,606 --> 00:04:26,430
>> ALAN אסטרדה: או והאזור.

166
00:04:26,430 --> 00:04:27,140
>> דוד י מלאן: לא, זה בסדר.

167
00:04:27,140 --> 00:04:28,930
אבל בואו נעמיד פנים כמו
הוא בדף זה.

168
00:04:28,930 --> 00:04:33,260
אז עכשיו, אתה כבר גלפת את הבעיה למטה
לדף אחד, ומצאנו מייק סמית.

169
00:04:33,260 --> 00:04:35,180
>> [מריע]

170
00:04:35,180 --> 00:04:35,757

171
00:04:35,757 --> 00:04:36,340
בסדר תודה.

172
00:04:36,340 --> 00:04:40,700

173
00:04:40,700 --> 00:04:41,200
אוקיי.

174
00:04:41,200 --> 00:04:43,646
זה היה יוצא דופן.

175
00:04:43,646 --> 00:04:45,954
אבל זה עדיין מהיר יותר היה
מחיפוש ליניארי,

176
00:04:45,954 --> 00:04:47,870
שבו אנו מתחילים ב
תחילת הספר,

177
00:04:47,870 --> 00:04:51,210
ואנחנו עוברים בדרך שלנו משמאל לימין,
סופו של דבר מחפש מייק סמית.

178
00:04:51,210 --> 00:04:53,540
וכך, אם בספר טלפונים
היו אולי 1,000 דפים,

179
00:04:53,540 --> 00:04:56,300
אולי זה היה לוקח
שלנו 10 או כך דמעות דף.

180
00:04:56,300 --> 00:04:59,380
>> אבל ייתכן שמנפת
נגע הנחה

181
00:04:59,380 --> 00:05:03,602
במהלך כל זה, מה שאומר
שספר טלפונים מראש היה מה?

182
00:05:03,602 --> 00:05:04,310
קהל: מסודר.

183
00:05:04,310 --> 00:05:05,000
דוד י מלאן: זה מסודרים.

184
00:05:05,000 --> 00:05:05,160
נכון?

185
00:05:05,160 --> 00:05:07,909
זה בסדר אלפביתי, כך
שכל אלה שמות ומספרים

186
00:05:07,909 --> 00:05:11,230
מסודרים משל ל
Z של, ובסדר אלפביתי שביניהם.

187
00:05:11,230 --> 00:05:13,100
אבל היום, עכשיו אנחנו שואלים
השאלה, טוב,

188
00:05:13,100 --> 00:05:16,170
איך Verizon עשה או הטלפון
חברה לקבל אותו לתוך המדינה ש?

189
00:05:16,170 --> 00:05:19,560
>> כי זה דבר אחד למנף
הנחה ש, ולכן,

190
00:05:19,560 --> 00:05:22,570
לפתור בעיה עם
אלגוריתם יעיל יותר.

191
00:05:22,570 --> 00:05:24,900
אבל אנחנו אף פעם לא באמת
שאל בשבוע שאפס, גם,

192
00:05:24,900 --> 00:05:27,790
כמה זה עולה
ורייזון או מישהו אחר

193
00:05:27,790 --> 00:05:29,620
כדי לקבל את ספר טלפונים על מנת מיון?

194
00:05:29,620 --> 00:05:29,780
>> נכון?

195
00:05:29,780 --> 00:05:31,529
זה לא משנה אם
מחפש את מייק סמית

196
00:05:31,529 --> 00:05:35,190
הוא סופר מהיר, אם זה לוקח לך
שנה כדי למיין את הדפים בתחילה.

197
00:05:35,190 --> 00:05:35,690
נכון?

198
00:05:35,690 --> 00:05:38,620
אתה יכול גם פשוט לנפות
דרך ספר טלפונים באקראי,

199
00:05:38,620 --> 00:05:40,690
אם זה הולך להיות סופר
יקר כדי למיין אותו.

200
00:05:40,690 --> 00:05:42,350
אז אם אנחנו יכולים להיות מתנדב נוסף.

201
00:05:42,350 --> 00:05:46,350
בואו נסתכל כאן ב
איך אנחנו might-- לבוא על up-- איך

202
00:05:46,350 --> 00:05:48,100
אנחנו עלולים ללכת על מיון אלה.

203
00:05:48,100 --> 00:05:51,990
>> ואם ירדן באמת יכול
הצטרף אלינו לכאן על במה.

204
00:05:51,990 --> 00:05:55,100
בואו לרגע.

205
00:05:55,100 --> 00:05:56,359
מה השם שלך?

206
00:05:56,359 --> 00:05:57,150
קרוליין: קרוליין.

207
00:05:57,150 --> 00:05:58,691
דוד י מלאן: קרוליין, לבוא בעד.

208
00:05:58,691 --> 00:06:02,070
ואתה תהיה הצטרף
על ידי לי וירדן כאן.

209
00:06:02,070 --> 00:06:03,800
קרוליין, תודה.

210
00:06:03,800 --> 00:06:04,300
בסדר.

211
00:06:04,300 --> 00:06:08,330
אז מה יש לנו כאן ל
קרוליין הוא 26 ספרים כחולים

212
00:06:08,330 --> 00:06:10,747
שFAS משתמש כדי לנהל
בחינות סופיות מסוימות.

213
00:06:10,747 --> 00:06:13,330
אלה מקבלים קשים למצוא,
אבל מה שעשינו מראש

214
00:06:13,330 --> 00:06:15,800
הוא שאנחנו כבר לשים את שמו של מישהו
בחזית של כל אחד מאלה,

215
00:06:15,800 --> 00:06:18,133
אבל אנחנו כבר המשכנו את זה פשוט על ידי
לאחר מכן לשים את שמות מלאים.

216
00:06:18,133 --> 00:06:22,720
אז היינו לשים את האדם בשם
L, D, J, B, כל הדרך עד Z,

217
00:06:22,720 --> 00:06:24,090
אבל הם בסדר אקראיים.

218
00:06:24,090 --> 00:06:26,890
ולכן אם היית, מדבר
את דרכה בבעיה כמו שאתה

219
00:06:26,890 --> 00:06:31,620
לעשות את זה, אתה יכול ללכת קדימה ו
למיין את אלה לנו, מ- A עד Z.

220
00:06:31,620 --> 00:06:34,070
>> קהל: בסדר, אז L הוא כמו, האמצע.

221
00:06:34,070 --> 00:06:35,050
C מתחיל.

222
00:06:35,050 --> 00:06:42,410
ב J לפני ל 'ב', ש

223
00:06:42,410 --> 00:06:45,140
>> דוד י מלאן: החזק ש
חשבתי לשנייה אחת.

224
00:06:45,140 --> 00:06:48,910
כי אחר, זה רק
מעניין לך, לי, וירדן.

225
00:06:48,910 --> 00:06:49,724
יש לנו ללכת.

226
00:06:49,724 --> 00:06:50,640
קהל: [לא ברור].

227
00:06:50,640 --> 00:06:57,299
ר '

228
00:06:57,299 --> 00:06:58,090
דוד י מלאן: אישור.

229
00:06:58,090 --> 00:06:59,310
מה אתה עושה?

230
00:06:59,310 --> 00:07:01,730
>> קרוליין: M מגיע לאחר O.

231
00:07:01,730 --> 00:07:02,564
>> דוד י מלאן: אישור.

232
00:07:02,564 --> 00:07:03,064
>> קרוליין: O.

233
00:07:03,064 --> 00:07:04,120
דוד י מלאן: O, טוב.

234
00:07:04,120 --> 00:07:04,970
>> קרוליין: א

235
00:07:04,970 --> 00:07:06,730
>> דוד י מלאן: E, F. כן.

236
00:07:06,730 --> 00:07:07,620
>> קרוליין: T, U, V.

237
00:07:07,620 --> 00:07:10,689
>> דוד י מלאן: V, T, U, V. אז זה
נראה כאילו אתה making-- להמשיך.

238
00:07:10,689 --> 00:07:12,730
זה נראה כאילו אתה עושה
ערימה גדולה כאן,

239
00:07:12,730 --> 00:07:13,910
וסוג של ערימה גדולה שם.

240
00:07:13,910 --> 00:07:16,230
אז במחצית הראשונה של האלף-בית,
מחצית שנייה של האלף-בית.

241
00:07:16,230 --> 00:07:16,460
אוקיי.

242
00:07:16,460 --> 00:07:16,960
טוב.

243
00:07:16,960 --> 00:07:19,680
סוג של פיצול הבעיה בשתי.

244
00:07:19,680 --> 00:07:21,771
M, N, X. כן.

245
00:07:21,771 --> 00:07:22,270
קרוליין: ק

246
00:07:22,270 --> 00:07:22,980
דוד י מלאן: אישור.

247
00:07:22,980 --> 00:07:25,070
ק אז אתה סוג של בחירה
שלהם אחד אחרי השני,

248
00:07:25,070 --> 00:07:27,620
לשים אותו שמאלה או ימינה,
או Z של הולכים על הרצפה.

249
00:07:27,620 --> 00:07:28,012
אוקיי.

250
00:07:28,012 --> 00:07:29,190
>> קרוליין: Z הולך על הרצפה.

251
00:07:29,190 --> 00:07:29,360
>> דוד י מלאן: אישור.

252
00:07:29,360 --> 00:07:30,920
Y הולך על הרצפה.

253
00:07:30,920 --> 00:07:31,735
עכשיו אנחנו יכולים לשים X.

254
00:07:31,735 --> 00:07:32,409
>> קרוליין: ג '

255
00:07:32,409 --> 00:07:33,700
דוד י מלאן: G הולך שמאלה.

256
00:07:33,700 --> 00:07:36,017
S הולך תקין.

257
00:07:36,017 --> 00:07:37,642
בסדר, הוא הולך כל דרך שמאל.

258
00:07:37,642 --> 00:07:38,790
>> קרוליין: A, B, C, D.

259
00:07:38,790 --> 00:07:39,873
>> דוד י מלאן: עכשיו, טוב.

260
00:07:39,873 --> 00:07:43,260
יש לנו, B, C. W של הולך שם למטה.

261
00:07:43,260 --> 00:07:45,566
בסדר, ט

262
00:07:45,566 --> 00:07:46,611
>> קרוליין: H, אני, ג '

263
00:07:46,611 --> 00:07:47,860
דוד י מלאן: H, אני, ג 'טוב.

264
00:07:47,860 --> 00:07:49,160
קרוליין: במרכז, אני gonna--

265
00:07:49,160 --> 00:07:50,000
דוד י מלאן: אישור.

266
00:07:50,000 --> 00:07:52,375
אז עכשיו, אנחנו הולכים לסוג
של למזג אלה ערימות שונות.

267
00:07:52,375 --> 00:08:00,730
אז דרך C, אז אני רואה D, ו
E ו- F, G ו, ו- H, ואני נחמד.

268
00:08:00,730 --> 00:08:05,540
J, ק 'ואז, ערימה זה
הפוך, אבל זה בסדר.

269
00:08:05,540 --> 00:08:06,040
בטח.

270
00:08:06,040 --> 00:08:07,240
אנחנו יכולים לחתוך כמה פינות.

271
00:08:07,240 --> 00:08:07,950
אוקיי.

272
00:08:07,950 --> 00:08:10,530
ואז אנחנו צריכים W, X, Y, Z.

273
00:08:10,530 --> 00:08:11,250
>> קרוליין: כן.

274
00:08:11,250 --> 00:08:11,880
>> דוד י מלאן: מצוין.

275
00:08:11,880 --> 00:08:14,122
אז תודה גדולה ל
קרוליין למיון אלה.

276
00:08:14,122 --> 00:08:15,030
>> [מריע]

277
00:08:15,030 --> 00:08:17,287
>> תודה.

278
00:08:17,287 --> 00:08:18,120
תודה רבה.

279
00:08:18,120 --> 00:08:22,910
אז עכשיו בואו נשקול לרגע
איך קרוליין הלך על עושה את זה,

280
00:08:22,910 --> 00:08:26,040
ומה בדיוק אנחנו
הצליחו צריכה-- איך אנחנו

281
00:08:26,040 --> 00:08:28,409
היו מסוגל לפתור את זה
בעיה כאשר היינו רק

282
00:08:28,409 --> 00:08:29,950
נתן חבורה של תשומות אקראיות לגמרי.

283
00:08:29,950 --> 00:08:31,610
>> ובכן, זה נראה כאילו יש
היה קצת מערכת שם?

284
00:08:31,610 --> 00:08:32,110
תקין.

285
00:08:32,110 --> 00:08:34,495
אז המכתבים הקודמים
באלף-הבית, היא

286
00:08:34,495 --> 00:08:37,120
היה לשים בצד השמאל, ו
מכתבים מאוחר יותר באלפבית,

287
00:08:37,120 --> 00:08:38,270
היא מכניסה לימין.

288
00:08:38,270 --> 00:08:40,500
וברגע שהיא מצאה
כמה מכתבים הפרוקסימלי, אלה

289
00:08:40,500 --> 00:08:43,124
שתלך ממש ליד אחד את השני,
היא הייתה לשים אותם לפי סדר.

290
00:08:43,124 --> 00:08:46,750
וכך אנו סוג של היו קטנים האלה
ערימות של תשומות ממוינות המתרחשות.

291
00:08:46,750 --> 00:08:50,540
>> ואז זה די דומה למה ש
רובנו בני האדם היה עושים.

292
00:08:50,540 --> 00:08:53,530
היינו סוג של לנפות אותו,
והייתי סוג של יש לנו מנגנון.

293
00:08:53,530 --> 00:08:56,930
אבל זה יכול להיות קשה לכתוב
אותו בנוסחה כשלעצמה.

294
00:08:56,930 --> 00:08:59,010
זה הרגיש קצת יותר אורגני מזה.

295
00:08:59,010 --> 00:09:02,560
אז בואו לראות אם אנחנו יכולים עכשיו קשורים
הבעיה עם פחות תשומות.

296
00:09:02,560 --> 00:09:05,170
>> במקום 26, בואו
לעשות משהו הרבה פחות

297
00:09:05,170 --> 00:09:09,890
עם רק לומר, שבע, מאחורי
דלתות אלה, אם אפשר לומר כך.

298
00:09:09,890 --> 00:09:11,300
האם יש רק שבעה מספרים?

299
00:09:11,300 --> 00:09:15,240
ואם המטרה עכשיו ב
יד היא למצוא ערך,

300
00:09:15,240 --> 00:09:17,850
בואו לראות איך ביעילות
אנחנו יכולים ללכת על עושים את זה.

301
00:09:17,850 --> 00:09:22,460
ובואו נראה אם ​​עכשיו אנחנו יכולים
להתחיל ליישם כמה מספרים,

302
00:09:22,460 --> 00:09:26,310
או כמה נוסחות שבי לתאר
היעילות של ספר הטלפונים שלנו

303
00:09:26,310 --> 00:09:31,060
אלגוריתם, אלגוריתם ספר בחינה שלנו, ו
באופן כללי יותר, מציאת מידע.

304
00:09:31,060 --> 00:09:34,770
>> אז לזה, תן לי ללכת קדימה, ו
על מסך המגע לכאן,

305
00:09:34,770 --> 00:09:41,100
לשים את דפדפן אינטרנט שיש
בדיוק אלה שבע דלתות.

306
00:09:41,100 --> 00:09:46,670
ואם אנחנו יכולים לקבל אחד אחר
מתנדב לבוא לכאן ב,

307
00:09:46,670 --> 00:09:48,480
שמתי אותו דלתות אלה כאן.

308
00:09:48,480 --> 00:09:49,170
מתנדב מהיר.

309
00:09:49,170 --> 00:09:51,130
>> הדגמות one-- זה הולכים
למהיר יותר ומהיר יותר עכשיו.

310
00:09:51,130 --> 00:09:51,600
בואו למטה.

311
00:09:51,600 --> 00:09:52,308
מה השם שלך?

312
00:09:52,308 --> 00:09:53,040
TREVOR: טרוור.

313
00:09:53,040 --> 00:09:53,998
>> דוד י מלאן: טרבור?

314
00:09:53,998 --> 00:09:55,770
בסדר, טרבור, בא למטה.

315
00:09:55,770 --> 00:09:59,212
אז טרבור התנדב כאן ל
לעשות בעיה דומה, אבל אף אחד כי זה

316
00:09:59,212 --> 00:10:02,170
צר יותר בהיקפה, וזה הולך
כדי לאפשר לנו לנסות למסד עכשיו

317
00:10:02,170 --> 00:10:03,970
תהליך מיון למספרים האלה.

318
00:10:03,970 --> 00:10:05,500
>> אז טרבור, נחמד לפגוש אותך.

319
00:10:05,500 --> 00:10:08,720
אז הנה הוא מערך, כך ל
לדבר, רשימה של שבע דלתות.

320
00:10:08,720 --> 00:10:10,327
קדימה ותמצא אותנו במספר 50.

321
00:10:10,327 --> 00:10:12,410
ולאחר מכן לאחר מעשה,
לספר לנו איך מצא את זה.

322
00:10:12,410 --> 00:10:19,124

323
00:10:19,124 --> 00:10:20,040
צריך להיות-- בסדר.

324
00:10:20,040 --> 00:10:21,945
כן, זה הוא אחד כאן?

325
00:10:21,945 --> 00:10:24,680
או הו.

326
00:10:24,680 --> 00:10:25,560
אוקיי.

327
00:10:25,560 --> 00:10:26,680
לחצת כי אחד.

328
00:10:26,680 --> 00:10:28,690
טוב.

329
00:10:28,690 --> 00:10:29,780
>> וטוב.

330
00:10:29,780 --> 00:10:30,970
עכשיו אתה לוחץ שאחד.

331
00:10:30,970 --> 00:10:34,060
ותן לי לתת לך את המיקרופון,
כך שיש לך את זה ברגע.

332
00:10:34,060 --> 00:10:37,000
קדימה, לחץ על
השכן שאתה מתכוון.

333
00:10:37,000 --> 00:10:39,812
כן טוב.

334
00:10:39,812 --> 00:10:41,020
TREVOR: האם אני יכול מבטל דלת?

335
00:10:41,020 --> 00:10:42,620
דוד י מלאן: לא, אתה לא יכול בטל.

336
00:10:42,620 --> 00:10:43,119
TREVOR: אישור.

337
00:10:43,119 --> 00:10:43,974
זֶה.

338
00:10:43,974 --> 00:10:45,640
דוד י מלאן: איפה אתה רוצה ללכת?

339
00:10:45,640 --> 00:10:46,410
איזה?

340
00:10:46,410 --> 00:10:47,230
>> TREVOR: אחד זה.

341
00:10:47,230 --> 00:10:48,042
>> דוד י מלאן: מס '

342
00:10:48,042 --> 00:10:48,450
>> TREVOR: אישור.

343
00:10:48,450 --> 00:10:48,735
זֶה.

344
00:10:48,735 --> 00:10:49,020
>> דוד י מלאן: כן.

345
00:10:49,020 --> 00:10:49,700
זה היה טוב.

346
00:10:49,700 --> 00:10:50,380
בסדר.

347
00:10:50,380 --> 00:10:53,900
אז מה היה האלגוריתם שלך או
הליך עושה את זה, טרבור?

348
00:10:53,900 --> 00:10:56,149
>> TREVOR: אני רק עברתי
דלתות עד שמצאתי 50.

349
00:10:56,149 --> 00:10:56,940
דוד י מלאן: אישור.

350
00:10:56,940 --> 00:10:58,150
אלגוריתם מצוין.

351
00:10:58,150 --> 00:10:59,540
אז זה בסדר.

352
00:10:59,540 --> 00:11:03,120
כי למעשה, אם אני מגלה מה
מאחורי שתי דלתות אחרות אלה, מה ש

353
00:11:03,120 --> 00:11:06,954
אנחנו תמצאו כאן הוא ש
יש לנו רק קלט אקראי.

354
00:11:06,954 --> 00:11:08,870
אז זה היה ממש כמו
טוב כמו שאתה יכול לקבל.

355
00:11:08,870 --> 00:11:12,509
ואכן, יש לך טוב יותר מ
ממצה חיפוש בכל המערך,

356
00:11:12,509 --> 00:11:15,300
כי זה היה באמת
מזל אם אתה פגע במספר

357
00:11:15,300 --> 00:11:16,604
50 בדלת האחרון.

358
00:11:16,604 --> 00:11:18,520
אבל מה אם אנחנו במקום
נתתי לך הנחה.

359
00:11:18,520 --> 00:11:20,630
נניח שכל סוג
דלתות אלה בסביבה,

360
00:11:20,630 --> 00:11:23,500
כך שיש לך
מספרים מסודרים הפעם,

361
00:11:23,500 --> 00:11:29,730
אבל פעם זה באמת
different-- הפעם,

362
00:11:29,730 --> 00:11:32,640
זה באמת סדר לך.

363
00:11:32,640 --> 00:11:35,380
ועכשיו המטרה בהישג היד
הוא להכות את המספר 50.

364
00:11:35,380 --> 00:11:36,090
>> TREVOR: אישור.

365
00:11:36,090 --> 00:11:37,670
>> דוד י מלאן: מה
האלגוריתם שלך הולך להיות?

366
00:11:37,670 --> 00:11:39,628
>> TREVOR: ובכן, אם זה
מסודרים, זה גם הולך

367
00:11:39,628 --> 00:11:42,710
ללהיות-- אם הגדול ביותר לגדול ביותר,
יורד, זה יהיה ראשון,

368
00:11:42,710 --> 00:11:44,751
או אם זה ההפך,
זה יהיה אחרון.

369
00:11:44,751 --> 00:11:48,897
אז אני רק להקיש את הדלת הזאת, ו
אז פשוט להקיש על הדלת האחרונה.

370
00:11:48,897 --> 00:11:49,980
דוד י מלאן: מצוין.

371
00:11:49,980 --> 00:11:50,270
בסדר.

372
00:11:50,270 --> 00:11:51,150
אז מצאנו את המספר 50.

373
00:11:51,150 --> 00:11:52,970
אז ברגע שאתה יודע
הם מסודרים, אנחנו

374
00:11:52,970 --> 00:11:55,040
הצליחו למנף הנחה זו.

375
00:11:55,040 --> 00:11:57,040
אז הם יותר מדי כמו
דוגמא ספר טלפונים.

376
00:11:57,040 --> 00:11:59,540
ברגע שיש לך, אפילו עם
בעיה קטנה כמו זה,

377
00:11:59,540 --> 00:12:02,380
התשומות שלך-מסודרים מראש, אנחנו יכולים
למעשה למצוא את הערך לטעון

378
00:12:02,380 --> 00:12:03,130
בצורה יעילה יותר.

379
00:12:03,130 --> 00:12:05,800
>> ואני לא אומר לך אם זה היה
מסודרים קטן לגדול, או גדול לקטן,

380
00:12:05,800 --> 00:12:08,080
ואז זה היה מאוד סביר
כדי להתחיל בקצה אחד או אחר

381
00:12:08,080 --> 00:12:09,750
למעשה לגלות כי ערך היעד.

382
00:12:09,750 --> 00:12:11,400
אז תודה לטרוור גם כן.

383
00:12:11,400 --> 00:12:13,260
ואני propose-- עשיתי יפה.

384
00:12:13,260 --> 00:12:16,960
יש לנו קצת קליפ, בעצם, ש
הוא בין הרגעים האהובים עלינו בCS50,

385
00:12:16,960 --> 00:12:19,700
לפי לפעמים הדגמות אלה
לא ממש הולכים לפי תכנית.

386
00:12:19,700 --> 00:12:22,050
ואכן עכשיו, אני
משך את הממשק הלא נכון

387
00:12:22,050 --> 00:12:23,508
עם שלשימוש במסך המגע.

388
00:12:23,508 --> 00:12:24,660
אז זה היה באשמתי שם.

389
00:12:24,660 --> 00:12:26,600
>> אז זה יגרום ל
קליפ בשנה הבאה כ

390
00:12:26,600 --> 00:12:28,570
למה אני לחיצה על המסך שלי.

391
00:12:28,570 --> 00:12:31,390
אבל בואו ניקח מבט מהיר
על מה שקרה בשנה שעברה

392
00:12:31,390 --> 00:12:34,770
עם ג'יי, שפרץ, הרבה
כמו טרבור כאן, התנדב,

393
00:12:34,770 --> 00:12:39,380
ובקליפ קצר זה, תראה
איך אותה הדגמה זו לא עשתה די

394
00:12:39,380 --> 00:12:41,074
לחשוף אותו הלקחים.

395
00:12:41,074 --> 00:12:41,740
[וידאו השמעה]

396
00:12:41,740 --> 00:12:45,360
'כל אני רוצה שתעשה עכשיו הוא
כדי למצוא לי, ולנו,

397
00:12:45,360 --> 00:12:51,674
באמת, המספר 50
צעד אחד בכל פעם.

398
00:12:51,674 --> 00:12:52,450
>> בחור' מספר 50?

399
00:12:52,450 --> 00:12:53,190
>> בחור' מספר 50.

400
00:12:53,190 --> 00:12:55,356
ואתה יכול לחשוף מה
מאחורי כל אחד מדלתות אלה

401
00:12:55,356 --> 00:12:58,540
פשוט על ידי נגיעה בו עם אצבע.

402
00:12:58,540 --> 00:13:00,910
לעזאזל.

403
00:13:00,910 --> 00:13:02,870
>> [צוחק]

404
00:13:02,870 --> 00:13:03,806
>> [סוף ההשמעה]

405
00:13:03,806 --> 00:13:05,430
דוד י מלאן: אז זה הלך טוב מאוד.

406
00:13:05,430 --> 00:13:06,796
אלה היו הדלתות הרגילות.

407
00:13:06,796 --> 00:13:08,670
וג'יי, כמובן,
מצא אותה מהר מדי.

408
00:13:08,670 --> 00:13:12,910
טרבור עשה עבודה הרבה יותר טובה
במונחים של רגע למיד,

409
00:13:12,910 --> 00:13:15,850
כביכול, לשנה זו ב
לוקח יותר זמן למצוא אותו.

410
00:13:15,850 --> 00:13:17,950
כמובן, אז נתנו לי
ג'יי הזדמנות שנייה,

411
00:13:17,950 --> 00:13:20,320
לפיה אנו מסודרים הדלתות,
בדיוק כפי שעשינו לטרבור,

412
00:13:20,320 --> 00:13:22,300
וטרבור עשה סופר גם הפעם.

413
00:13:22,300 --> 00:13:26,124
אבל ג'יי עשה את זה חצי במהירות.

414
00:13:26,124 --> 00:13:26,790
[וידאו השמעה]

415
00:13:26,790 --> 00:13:29,650
בחור' מטרה עכשיו היא גם
תמצא אותנו במספר 50,

416
00:13:29,650 --> 00:13:33,030
אבל לעשות את זה אלגוריתמי, ו
לספר לנו איך אתה הולך על זה.

417
00:13:33,030 --> 00:13:33,660
>> -אוקיי.

418
00:13:33,660 --> 00:13:35,604
>> : ואם אתה מוצא את זה, אתה שומר את הסרט.

419
00:13:35,604 --> 00:13:37,228
אם אתה לא מוצא את זה, אתה נותן אותו בחזרה.

420
00:13:37,228 --> 00:13:38,044
>> -אדם.

421
00:13:38,044 --> 00:13:38,860
>> אה!

422
00:13:38,860 --> 00:13:40,800
>> - [לא ברור] על אישור.

423
00:13:40,800 --> 00:13:46,236
אז אני הולך לבדוק את הקצוות
ראשון כדי לקבוע אם יש-- הו.

424
00:13:46,236 --> 00:13:48,646
>> [מחיאות כפות]

425
00:13:48,646 --> 00:13:53,948

426
00:13:53,948 --> 00:13:55,729
>> [סוף ההשמעה]

427
00:13:55,729 --> 00:13:56,520
דוד י מלאן: אישור.

428
00:13:56,520 --> 00:13:59,760
אז מיון דלתות ברור
מוביל ליעילות גבוהה יותר.

429
00:13:59,760 --> 00:14:01,680
וכך, במהירות כפולה
זה מה שהתכוונתי שם.

430
00:14:01,680 --> 00:14:03,270
וכך ג'יי לי מזל בשתי הפעמים.

431
00:14:03,270 --> 00:14:06,685
והוא גם קיבל מזל שבעבר
שנה, הזמנתי כמה דיסקי Blu-ray

432
00:14:06,685 --> 00:14:07,560
לתת בפועל.

433
00:14:07,560 --> 00:14:09,768
אני מצטער זה שנה, אנחנו
לא היה לו הדבר, טרבור.

434
00:14:09,768 --> 00:14:11,540
אבל עוד יותר טוב היה לפני כמה שנים.

435
00:14:11,540 --> 00:14:14,820
וחלק מכם אולי יודע את זה
בחור, שון, שכשהוא היה בCS50,

436
00:14:14,820 --> 00:14:17,780
היה לערער עם מדויק
אותה בעיה, אם כי בSD,

437
00:14:17,780 --> 00:14:19,360
כפי שאתה בקרוב לראות, חזרה ביום.

438
00:14:19,360 --> 00:14:22,622
ואתה תמצא שלא רק
הוא ייקח קצת יותר זמן מאשר ג'יי,

439
00:14:22,622 --> 00:14:25,580
קצת יותר מטרבור, זה היה
למעשה הזדמנות נפלאה זו

440
00:14:25,580 --> 00:14:29,820
לעסוק כמעט כולם ב
קהל לה מחיר הוא נכון, עידוד

441
00:14:29,820 --> 00:14:31,889
שלו כדי למצוא את המספר שאנחנו מחפשים.

442
00:14:31,889 --> 00:14:32,930
בואו. להעיף מבט מהיר.

443
00:14:32,930 --> 00:14:33,320
>> [וידאו השמעה]

444
00:14:33,320 --> 00:14:33,820
>> -אוקיי.

445
00:14:33,820 --> 00:14:36,680
אז המשימה שלך כאן,
שון, הוא הבא.

446
00:14:36,680 --> 00:14:40,860
אני מסתתר מאחורי אלה
דלתות המספר שבע.

447
00:14:40,860 --> 00:14:45,120
אבל חבוי בחלק מדלתות אלה
כמו גם מספרים שליליים אחרים.

448
00:14:45,120 --> 00:14:47,500
והמטרה שלך היא לחשוב
של שורה העליונה זו של מספרים

449
00:14:47,500 --> 00:14:50,390
כפשוט מערך, או סתם
רצף של פיסות נייר

450
00:14:50,390 --> 00:14:51,510
עם מספרים שמאחוריהם.

451
00:14:51,510 --> 00:14:55,540
והמטרה שלך היא, רק באמצעות העליון
מערך כאן, תמצא לי את המספר שבע.

452
00:14:55,540 --> 00:14:58,570
ואז אנחנו הולכים לביקורת
איך אתה הולך על עושה את זה.

453
00:14:58,570 --> 00:14:59,070
-בסדר.

454
00:14:59,070 --> 00:15:00,850
, מצא אותנו במספר שבע, בבקשה.

455
00:15:00,850 --> 00:15:10,500

456
00:15:10,500 --> 00:15:11,000
מס '

457
00:15:11,000 --> 00:15:15,050

458
00:15:15,050 --> 00:15:18,550
חמש, 19, 13.

459
00:15:18,550 --> 00:15:22,240

460
00:15:22,240 --> 00:15:24,770
>> [צוחק]

461
00:15:24,770 --> 00:15:25,910
>> זה לא שאלה מכשילה.

462
00:15:25,910 --> 00:15:29,410

463
00:15:29,410 --> 00:15:29,910
אחד.

464
00:15:29,910 --> 00:15:33,218

465
00:15:33,218 --> 00:15:34,695
>> [צוחק]

466
00:15:34,695 --> 00:15:37,861
בשלב זה, הציון שלך הוא לא מאוד
טוב, אז אתה יכול גם להמשיך.

467
00:15:37,861 --> 00:15:40,610

468
00:15:40,610 --> 00:15:41,110
שלוש.

469
00:15:41,110 --> 00:15:43,890

470
00:15:43,890 --> 00:15:45,378
>> [צוחק]

471
00:15:45,378 --> 00:15:46,370

472
00:15:46,370 --> 00:15:47,774
>> תמשיך.

473
00:15:47,774 --> 00:15:50,690
למען האמת, אני לא יכול שלא לתהות
מה שאתה אפילו חושב על, אז--

474
00:15:50,690 --> 00:15:51,959
>> [צוחק]

475
00:15:51,959 --> 00:15:53,229

476
00:15:53,229 --> 00:15:55,020
רק בשורה העליונה, כך
יש לך שלושה שמאל.

477
00:15:55,020 --> 00:15:56,200
אז תמצא אותי שבע.

478
00:15:56,200 --> 00:15:59,700

479
00:15:59,700 --> 00:16:02,167
>> [צוחק]

480
00:16:02,167 --> 00:16:14,870

481
00:16:14,870 --> 00:16:15,370
17.

482
00:16:15,370 --> 00:16:25,675

483
00:16:25,675 --> 00:16:26,946
שבע.

484
00:16:26,946 --> 00:16:28,780
>> [מחיאות כפות]

485
00:16:28,780 --> 00:16:29,426
>> בסדר.

486
00:16:29,426 --> 00:16:30,360
>> [סוף ההשמעה]

487
00:16:30,360 --> 00:16:31,840
>> דוד י מלאן: כדי שנוכל
לצפות האלה כל היום.

488
00:16:31,840 --> 00:16:34,090
וכמובן, חלק מ
ההדגמות של השנה אולי

489
00:16:34,090 --> 00:16:36,330
עכשיו בסופו של הדבר הבא
הווידאו של השנה, כמו גם.

490
00:16:36,330 --> 00:16:39,040
אז עכשיו בואו למעשה
תתמקד באלגוריתמים

491
00:16:39,040 --> 00:16:42,140
כאן, ולראות אם אנחנו לא יכולים
עכשיו תתחיל למסד

492
00:16:42,140 --> 00:16:46,650
איך אנחנו יכולים ללכת על מקבלים את הנתונים שלנו
למצב זה שזה מסודרים,

493
00:16:46,650 --> 00:16:50,054
כך שבסופו, אנחנו באמת יכולים
לחפש אותו בצורה יעילה יותר.

494
00:16:50,054 --> 00:16:52,470
ולמרות שאנחנו הולכים
להשתמש ערכות נתונים קטנות למדי,

495
00:16:52,470 --> 00:16:54,511
כמונו שמונה מספרים
יש כאן על הלוח,

496
00:16:54,511 --> 00:16:58,230
סופו של דבר אותו רעיונות אלה יכולים לחול
1,000 כניסות, מיליון כניסות,

497
00:16:58,230 --> 00:17:02,100
4 מיליארדים תשומות, כי האלגוריתמים
הולך להיות ביסוד זהה.

498
00:17:02,100 --> 00:17:05,359
>> ואז זה האחרון שלנו
הזדמנות להיום מתנדב,

499
00:17:05,359 --> 00:17:09,790
אבל אולי המעורב ביותר,
שאנחנו צריכים שמונה מתנדבים

500
00:17:09,790 --> 00:17:12,960
לבוא וללוות אותנו ב
תהליך של מיון מה בקרוב

501
00:17:12,960 --> 00:17:15,212
להיות במוסיקה אלה עומד כאן.

502
00:17:15,212 --> 00:17:16,170
תן לי להתחיל לחזור לכאן.

503
00:17:16,170 --> 00:17:19,692
>> אז אחת בירוק turquoise-- זה?

504
00:17:19,692 --> 00:17:21,130
האם אתה מבצע?

505
00:17:21,130 --> 00:17:21,630
שני.

506
00:17:21,630 --> 00:17:23,069
בואו למטה.

507
00:17:23,069 --> 00:17:23,569
אוקיי.

508
00:17:23,569 --> 00:17:24,420
שלוש.

509
00:17:24,420 --> 00:17:25,400
ארבעה.

510
00:17:25,400 --> 00:17:27,247
בוא me-- אישור, חמש.

511
00:17:27,247 --> 00:17:28,830
אתה להיות מועמד על ידי חבר שלך.

512
00:17:28,830 --> 00:17:31,340
שש, שבע, שמונה ו.

513
00:17:31,340 --> 00:17:32,130
בואו למעלה.

514
00:17:32,130 --> 00:17:32,630
בסדר.

515
00:17:32,630 --> 00:17:33,190
תודה רבה לך.

516
00:17:33,190 --> 00:17:33,689
בואו למעלה.

517
00:17:33,689 --> 00:17:34,790
בואו למעלה.

518
00:17:34,790 --> 00:17:35,330
>> בסדר.

519
00:17:35,330 --> 00:17:38,890
אז מה יש לנו כאן-- וזה
הוא בין מביך יותר,

520
00:17:38,890 --> 00:17:42,390
מאז זה דורש שהומור
שלי לקצת זמן.

521
00:17:42,390 --> 00:17:43,442
אתה יהיה מספר אחד.

522
00:17:43,442 --> 00:17:44,150
מה השם שלך?

523
00:17:44,150 --> 00:17:44,610
>> ענאן: אנאן.

524
00:17:44,610 --> 00:17:45,526
>> דוד י מלאן: אנאן.

525
00:17:45,526 --> 00:17:46,092
דוד.

526
00:17:46,092 --> 00:17:46,800
מה השם שלך?

527
00:17:46,800 --> 00:17:47,140
>> יוסף: יוסף.

528
00:17:47,140 --> 00:17:49,190
>> דוד י מלאן: יוסף,
אתה מספר שתיים.

529
00:17:49,190 --> 00:17:52,260
>> סרינה: סרינה, מספר שלוש.

530
00:17:52,260 --> 00:17:53,722
סטפן, מספר ארבעה.

531
00:17:53,722 --> 00:17:54,430
סינתיה: סינתיה.

532
00:17:54,430 --> 00:17:57,548
דוד י מלאן: סינתיה, מספר חמש.

533
00:17:57,548 --> 00:17:58,452
[לא ברור]

534
00:17:58,452 --> 00:17:59,618
דוד י מלאן: [לא ברור].

535
00:17:59,618 --> 00:18:00,391
דוד, מספר שש.

536
00:18:00,391 --> 00:18:00,890
מאט: מאט.

537
00:18:00,890 --> 00:18:02,160
דוד י מלאן: המספר של מאט שבע.

538
00:18:02,160 --> 00:18:02,850
ו?

539
00:18:02,850 --> 00:18:03,210
>> Waverly: Waverly.

540
00:18:03,210 --> 00:18:04,470
>> דוד י מלאן: Waverly, מספר שמונה.

541
00:18:04,470 --> 00:18:04,970
בסדר.

542
00:18:04,970 --> 00:18:06,510
אם אתה could-- אופס.

543
00:18:06,510 --> 00:18:08,820
אם כל מה שאתה, כ
אתגר ראשון, יש

544
00:18:08,820 --> 00:18:10,820
שמונה דוכני מוסיקה
כאן מול הקהל.

545
00:18:10,820 --> 00:18:14,200
אם אתה יכול לשים את המספרים שלך ב
מוסיקה אלה עומדת בצורה כזאת

546
00:18:14,200 --> 00:18:16,560
שהם בקנה אחד עם
אותם מספרים על הלוח.

547
00:18:16,560 --> 00:18:19,560
אז להפוך את עצמכם להיראות כמו שעל ידי
לשים המספרים שלך על מוסיקה אלה

548
00:18:19,560 --> 00:18:21,960
עומד כאן.

549
00:18:21,960 --> 00:18:25,980
מצוין עד כה.

550
00:18:25,980 --> 00:18:26,600
>> מצוין.

551
00:18:26,600 --> 00:18:26,890
אוקיי.

552
00:18:26,890 --> 00:18:29,556
אז עכשיו, אנחנו הולכים לשאול
שאלה בכמה דרכים שונות.

553
00:18:29,556 --> 00:18:31,610
איך אנחנו יכולים ללכת על מיון
אנשים אלה עד כאן?

554
00:18:31,610 --> 00:18:34,500
כי היו לנו כמה גישות
קודם לכן, לפיה היינו

555
00:18:34,500 --> 00:18:36,360
סוג של מה שהופך את שני דליים שונים.

556
00:18:36,360 --> 00:18:38,842
ואז היינו בדרך כלל
piecing דברים ביחד.

557
00:18:38,842 --> 00:18:41,050
ברגע שראינו את שני מספרים
שהיה שייכים יחד,

558
00:18:41,050 --> 00:18:41,975
אנחנו שמים אותם יחד.

559
00:18:41,975 --> 00:18:43,350
שני מכתבים ששייכים זה לזה.

560
00:18:43,350 --> 00:18:45,058
>> אבל בואו תראו אם אנחנו
לא יכול למסד זה,

561
00:18:45,058 --> 00:18:48,044
כך שבסופו יש לנו
כמה פסאודו-קוד תרצה,

562
00:18:48,044 --> 00:18:49,710
שבה אתה יכול לפתור את הבעיות הללו.

563
00:18:49,710 --> 00:18:51,870
אז עכשיו, אני מחפש את
במספרים האלה כאן.

564
00:18:51,870 --> 00:18:55,030
ואני רואה חבורה של טעויות כולה.

565
00:18:55,030 --> 00:18:57,750
סופו של דבר, אני רוצה אחד ב
עזב ושמונה בצד הימין.

566
00:18:57,750 --> 00:19:00,650
>> ואז אני מסתכל על
שני אלה, ארבעת ושני.

567
00:19:00,650 --> 00:19:02,930
ומה הבעיה, ברורה?

568
00:19:02,930 --> 00:19:04,261
כן.

569
00:19:04,261 --> 00:19:04,760
כן."

570
00:19:04,760 --> 00:19:07,160
שני כמובן בא לפני
ארבעה, אז אתה יודע מה?

571
00:19:07,160 --> 00:19:10,210
תן לי לנקוט בגישה חמדנית ראשון,
אם תרצה, הרבה בעיה כמו

572
00:19:10,210 --> 00:19:13,790
להגדיר one-- אם אתה זוכר מ
מהדורה סטנדרטית של הבעיה הגדר אחת,

573
00:19:13,790 --> 00:19:16,820
שבו אני פשוט באופן מקומי לפתור את הבעיה
זה ממש כאן מולי

574
00:19:16,820 --> 00:19:17,690
ולראות לאן זה מוביל אותי.

575
00:19:17,690 --> 00:19:17,870
>> אוקיי.

576
00:19:17,870 --> 00:19:20,161
אז שתיים וארבעה, תן לי ללכת
קדימה ופשוט להחליף לך שני.

577
00:19:20,161 --> 00:19:22,400
אם אתה יכול להזיז פיזי
את עצמכם ונייר שלך,

578
00:19:22,400 --> 00:19:25,040
נדמה לי שהתבגרתי
רשימה במצב טוב יותר.

579
00:19:25,040 --> 00:19:26,330
>> עכשיו, הם טובים.

580
00:19:26,330 --> 00:19:28,480
אני הולך לעבור,
ארבעה ושש, נראים טובים.

581
00:19:28,480 --> 00:19:29,110
אין בעיה.

582
00:19:29,110 --> 00:19:30,440
שישה ושמונה, על אישור.

583
00:19:30,440 --> 00:19:31,860
שמונה ואחד, בעיה נוספת.

584
00:19:31,860 --> 00:19:34,750
כי מה שנכון לגבי שמונה ואחד?

585
00:19:34,750 --> 00:19:36,990
אחד בא לפני שמונה,
ואז מה עלינו לעשות?

586
00:19:36,990 --> 00:19:38,090
בואו להחליף שני אלה.

587
00:19:38,090 --> 00:19:39,316
אחת ושמונה.

588
00:19:39,316 --> 00:19:40,690
ועכשיו, אני הולך להמשיך.

589
00:19:40,690 --> 00:19:42,030
אני הולך לשמור על מבט קדימה.

590
00:19:42,030 --> 00:19:42,840
ובואו לראות מה קורה.

591
00:19:42,840 --> 00:19:44,680
שמונה ושלושה, של
כמובן, מקולקל.

592
00:19:44,680 --> 00:19:45,815
בואו החלפה.

593
00:19:45,815 --> 00:19:46,940
שמונה ושבע, כמובן.

594
00:19:46,940 --> 00:19:47,481
מקולקל.

595
00:19:47,481 --> 00:19:48,280
בואו החלפה.

596
00:19:48,280 --> 00:19:49,940
שמונה וחמש, כמובן, בואו החלפה.

597
00:19:49,940 --> 00:19:50,560
בסדר.

598
00:19:50,560 --> 00:19:51,880
רשימה ממוינת.

599
00:19:51,880 --> 00:19:53,060
כן?

600
00:19:53,060 --> 00:19:54,280
>> אישור, כמובן לא.

601
00:19:54,280 --> 00:19:55,860
אבל זה קצת יותר טוב, נכון?

602
00:19:55,860 --> 00:19:57,270
משום מה הודעה שקרה.

603
00:19:57,270 --> 00:20:01,749
בכל פעם שבצענו החלפה, קטן יותר
מספר סוג של חלחל ככה,

604
00:20:01,749 --> 00:20:03,790
ומספר גדול יותר
חלחל בדרך זו, או ש

605
00:20:03,790 --> 00:20:06,880
להתחיל לומר מבעבעים ל
שמאלה או בועות ימינה.

606
00:20:06,880 --> 00:20:10,080
>> עכשיו, זה לא מספיק, כי
במקרה הטוב אולי מספר

607
00:20:10,080 --> 00:20:11,990
עברתי מקום אחד
קדימה, או במקרה הגרוע ביותר,

608
00:20:11,990 --> 00:20:13,880
מספר שאולי יש לי
עבר נקודה אחת נוסף.

609
00:20:13,880 --> 00:20:16,369
אז אתה יודע מה, זה סוג
של עבד די טוב עד כה.

610
00:20:16,369 --> 00:20:17,410
תן לי רק לנסות את זה שוב.

611
00:20:17,410 --> 00:20:18,880
שני וארבעה, הם בסדר.

612
00:20:18,880 --> 00:20:20,180
ארבעה ושש, הם בסדר.

613
00:20:20,180 --> 00:20:21,790
שש ואחד, מקולקל.

614
00:20:21,790 --> 00:20:23,007
אז בואו להחליף לך שני.

615
00:20:23,007 --> 00:20:25,840
ועכשיו, שים לב הבעיה של
מתחיל לקבל קצת יותר טוב שוב.

616
00:20:25,840 --> 00:20:27,006
שש ושלוש, מקולקל.

617
00:20:27,006 --> 00:20:28,100
בואו להחליף לך שני.

618
00:20:28,100 --> 00:20:29,730
שש ושבע, שאתה טובים.

619
00:20:29,730 --> 00:20:32,230
שבע וחמש, כמובן, מקולקל.

620
00:20:32,230 --> 00:20:33,920
שבע ושמונה, במטרה.

621
00:20:33,920 --> 00:20:36,470
ועכשיו, אולי אני צריך ל
לעשות את זה עוד כמה פעמים.

622
00:20:36,470 --> 00:20:39,830
ולמעשה, חושב לעצמכם
אולי כמה פעמים מקסימלי

623
00:20:39,830 --> 00:20:41,330
אולי אני צריך ללכת קדימה ואחורה?

624
00:20:41,330 --> 00:20:42,390
>> אנחנו נחזור לזה.

625
00:20:42,390 --> 00:20:43,700
אז שניים וארבעה עדיין אישור.

626
00:20:43,700 --> 00:20:44,940
ארבע ואחד, לא כלום.

627
00:20:44,940 --> 00:20:45,747
אז, בואו החלפה.

628
00:20:45,747 --> 00:20:47,830
ושוב, שים לב חזותי
אחד הוא סוג של מבעבע

629
00:20:47,830 --> 00:20:49,163
לשמאל, איפה שהוא צריך להיות.

630
00:20:49,163 --> 00:20:50,010
ארבעה ושלוש החלפה.

631
00:20:50,010 --> 00:20:51,330
ארבעה ושש.

632
00:20:51,330 --> 00:20:53,100
שש וחמש החלפה.

633
00:20:53,100 --> 00:20:53,959
שש ושבע.

634
00:20:53,959 --> 00:20:55,000
שבעה ושמונה הם טובים.

635
00:20:55,000 --> 00:20:55,500
>> טוב.

636
00:20:55,500 --> 00:20:58,460
אנחנו מקבלים אפילו טובים יותר.

637
00:20:58,460 --> 00:20:59,130
אז בואו לראות.

638
00:20:59,130 --> 00:21:00,940
עכשיו, יש לנו שתי ואחד.

639
00:21:00,940 --> 00:21:02,520
כמובן להחליף,.

640
00:21:02,520 --> 00:21:07,520
שתיים ושלוש, שלוש וארבעה, ארבעה ו
חמש, שישה ושבעה, שבעה ושמונה.

641
00:21:07,520 --> 00:21:08,020
טוב.

642
00:21:08,020 --> 00:21:08,730
ואתם יודעים מה?

643
00:21:08,730 --> 00:21:11,190
כי אני עשיתי שינוי אחד שם,
תן לי לעשות בדיקת שפיות אחד.

644
00:21:11,190 --> 00:21:13,023
תן לי ללכת את כל הדרך
בחזרה להתחלה.

645
00:21:13,023 --> 00:21:13,680
אוקיי.

646
00:21:13,680 --> 00:21:14,750
אחד, two-- יאפ, רואה?

647
00:21:14,750 --> 00:21:15,870
משהו לא בסדר.

648
00:21:15,870 --> 00:21:18,420
שלוש, ארבעה, חמש, שש, שבע, שמונה.

649
00:21:18,420 --> 00:21:21,920
ובמעבר אחרון זה, הם
נוח לך עם שלי עכשיו

650
00:21:21,920 --> 00:21:23,830
בטענה שזה מיון?

651
00:21:23,830 --> 00:21:24,330
אוקיי.

652
00:21:24,330 --> 00:21:25,880
מבחינה ויזואלית, זה נכון לחלוטין.

653
00:21:25,880 --> 00:21:28,410
אבל מבחינה תפקודית, מה
לא רק יקרה גם

654
00:21:28,410 --> 00:21:31,870
שבמעבר האחרון שמאפשר לך
כדי לוודא שרשימה זו היא אכן

655
00:21:31,870 --> 00:21:32,660
מסודרים?

656
00:21:32,660 --> 00:21:34,477
>> מה עשיתי או לא עשה מעבר אחרון זה?

657
00:21:34,477 --> 00:21:35,810
קהל: לא היו שינויים.

658
00:21:35,810 --> 00:21:36,120
דוד י מלאן: מצטער?

659
00:21:36,120 --> 00:21:37,070
קהל: לא היה שינויים.

660
00:21:37,070 --> 00:21:38,653
דוד י מלאן: לא היו שינויים.

661
00:21:38,653 --> 00:21:41,947
אז זה יהיה טיפשי שלי
לעשות את זה באותו אלגוריתם שוב

662
00:21:41,947 --> 00:21:43,780
אם אני לא עושה שום
משנה את הפעם הראשונה.

663
00:21:43,780 --> 00:21:45,160
והמדינה לא השתנתה.

664
00:21:45,160 --> 00:21:47,576
אין ספק, אני לא הולך לעשות
כל שינוי בפעם השנייה.

665
00:21:47,576 --> 00:21:49,820
וכך, זה בטוח עכשיו
לומר, רשימה ממוינת.

666
00:21:49,820 --> 00:21:52,069
>> ואכן, זה עכשיו
משהו שבדרך כלל אנחנו תמצאו

667
00:21:52,069 --> 00:21:56,900
מיון בועות שיחה, לפי pairwise,
אתה לתקן את טעויות שוב,

668
00:21:56,900 --> 00:22:00,210
ושוב, ושוב, ואתה
להמשיך קדימה ואחורה,

669
00:22:00,210 --> 00:22:03,370
ושוב ושוב, עד ש
לא עושה שום חילופים כאלה, ובשלב זה

670
00:22:03,370 --> 00:22:07,089
אתה יכול להיות בטוח, כן, אני
סיימתי לתקן את כל הטעויות.

671
00:22:07,089 --> 00:22:08,630
בואו לאפס ולנסות גישה אחרת.

672
00:22:08,630 --> 00:22:11,590
אם אתם יכולים לחזור ל
כדי שהיית לפני רגע,

673
00:22:11,590 --> 00:22:13,780
שנראה כמו זה.

674
00:22:13,780 --> 00:22:17,640
עכשיו, בואו לקחת גישה
קצת יותר כמו ספר בחינה,

675
00:22:17,640 --> 00:22:21,122
לפי שהיינו כל הזמן
בחירת האות של האלף בית

676
00:22:21,122 --> 00:22:22,830
שאנחנו סוג של רצינו
כדי להתמודד עם הבא.

677
00:22:22,830 --> 00:22:26,420
אולי זה היה מכתב גבוה,
כמו, או אות Z. נמוך

678
00:22:26,420 --> 00:22:28,170
>> אז כולם חוזרים בצו זה.

679
00:22:28,170 --> 00:22:29,800
ועכשיו תנו לי לעשות את זה.

680
00:22:29,800 --> 00:22:34,880
בואו לראות אני יודע שיש לי
שמונה מספרים כאן.

681
00:22:34,880 --> 00:22:37,410
אני הולך קדימה ו
רק בכוונה בחר

682
00:22:37,410 --> 00:22:38,520
האלמנטים הקטנים ביותר.

683
00:22:38,520 --> 00:22:38,760
נכון?

684
00:22:38,760 --> 00:22:39,801
זה נראה אינטואיטיבי מדי.

685
00:22:39,801 --> 00:22:42,560
למה אני לא מוצא את קטן
אלמנט, לשים אותו למקום שלו,

686
00:22:42,560 --> 00:22:45,280
לאחר מכן לקבל את האלמנט הקטן ביותר הבא, לשים
זה מקום שלו, ורק לחזור.

687
00:22:45,280 --> 00:22:46,820
>> משום באופן אינטואיטיבי,
שצריך לעבוד יותר מדי.

688
00:22:46,820 --> 00:22:48,441
אז ארבעה, שזה מספר די קטן.

689
00:22:48,441 --> 00:22:49,940
אני הולך לזכור איפה זה.

690
00:22:49,940 --> 00:22:50,523
חכה דקה.

691
00:22:50,523 --> 00:22:51,577
שני קטנים.

692
00:22:51,577 --> 00:22:53,910
עכשיו תן לי להיזכר בו שני
הוא, ולשכוח ארבעה.

693
00:22:53,910 --> 00:22:55,050
אנחנו נתמודד עם זה אחר כך.

694
00:22:55,050 --> 00:22:56,460
שש, אני לא מעוניין.

695
00:22:56,460 --> 00:22:57,810
שמונה, אני לא מעוניין ב.

696
00:22:57,810 --> 00:22:59,780
אחד מהם הוא המספר הקטן החדש שלי.

697
00:22:59,780 --> 00:23:01,470
אז אני הולך לזכור היכן הוא אחד.

698
00:23:01,470 --> 00:23:02,534
שלוש, לא מעוניין.

699
00:23:02,534 --> 00:23:03,450
שבע, לא מעוניין.

700
00:23:03,450 --> 00:23:04,530
חמש, לא מעוניין.

701
00:23:04,530 --> 00:23:07,390
>> אז בלי ליפול
השלב זה שנה,

702
00:23:07,390 --> 00:23:09,890
אני הולך לתפוס את מספר one--
ומה היה השם שלך שוב?

703
00:23:09,890 --> 00:23:10,150
>> ענאן: אנאן.

704
00:23:10,150 --> 00:23:11,220
>> דוד י מלאן: אנאן.

705
00:23:11,220 --> 00:23:13,540
ואם אתה יכול להצטרף אליי ב
תחילתה של הרשימה,

706
00:23:13,540 --> 00:23:14,870
בואו נכניס אותך שבו אתה שייך.

707
00:23:14,870 --> 00:23:16,080
Unfortunately-- מה שמך?

708
00:23:16,080 --> 00:23:16,650
>> סטפן: סטפן.

709
00:23:16,650 --> 00:23:18,191
>> דוד י מלאן: סטפן הוא בדרך.

710
00:23:18,191 --> 00:23:23,490
אז לפני שסטפן פותר את זה
בעיה, מה עלינו לעשות?

711
00:23:23,490 --> 00:23:25,412
מה עושה עם סטפן?

712
00:23:25,412 --> 00:23:27,269
>> קהל: [לא ברור].

713
00:23:27,269 --> 00:23:28,060
דוד י מלאן: אישור.

714
00:23:28,060 --> 00:23:28,850
אז אנחנו יכולים לעשות את זה.

715
00:23:28,850 --> 00:23:31,730
אנחנו יכולים לקחת סוג של סטפן ו
ארבעה, ורק לשים אותו במשתנה

716
00:23:31,730 --> 00:23:33,530
ולהחזיק בו ל
כמות מסוימת של זמן,

717
00:23:33,530 --> 00:23:35,220
וכך מקום למספר אחד.

718
00:23:35,220 --> 00:23:36,280
וזה לא רע.

719
00:23:36,280 --> 00:23:39,270
אני יכול להציע, למה לא
רק אנחנו שמים סטפן כאן?

720
00:23:39,270 --> 00:23:41,610
למה זה עלול להפר אחד
של הרעיונות שהתחלנו

721
00:23:41,610 --> 00:23:44,830
מדבר על הפעם האחרונה, בשבוע שעבר?

722
00:23:44,830 --> 00:23:45,330
כן?

723
00:23:45,330 --> 00:23:45,740
>> קהל: [לא ברור].

724
00:23:45,740 --> 00:23:46,860
>> דוד י מלאן: אין מדד לזה.

725
00:23:46,860 --> 00:23:49,735
אם אתה חושב על זה, אכן, כ
מערך, זה כמו שלילי אחת,

726
00:23:49,735 --> 00:23:52,900
כך שאין למעשה זיכרון
כאן אם זה אכן מערך,

727
00:23:52,900 --> 00:23:55,090
כמו שהכרזנו בשבוע שעבר בהרצאה.

728
00:23:55,090 --> 00:23:56,250
אז אנחנו לא צריכים לעשות את זה.

729
00:23:56,250 --> 00:23:57,340
אנחנו יכולים לאחסן אותו במשתנה.

730
00:23:57,340 --> 00:23:57,820
>> או שאתה יודע מה?

731
00:23:57,820 --> 00:23:59,153
שמעתי מישהו אחר מציע את זה.

732
00:23:59,153 --> 00:24:01,020
מה עוד אנחנו יכולים לעשות עם סטפן?

733
00:24:01,020 --> 00:24:03,770
למה אנחנו לא רק לגרש אותו ו
לשים אותו על שם מספר אחד היה.

734
00:24:03,770 --> 00:24:05,170
אז אם אתה רוצה ללכת לשם.

735
00:24:05,170 --> 00:24:07,300
ואכן, זה הוא
פתרון די טוב.

736
00:24:07,300 --> 00:24:10,480
עכשיו מצד האחד, יש לי סוג
של עשה את הבעיה יותר גרוע.

737
00:24:10,480 --> 00:24:13,650
ארבעה הוא כעת רחוק
מהמקום שבו צריך להיות.

738
00:24:13,650 --> 00:24:14,900
זה צריך להיות כיוון המחצית.

739
00:24:14,900 --> 00:24:16,100
>> אבל אתה יודע מה?

740
00:24:16,100 --> 00:24:17,630
שהיה יכול להיות מזל רע.

741
00:24:17,630 --> 00:24:18,822
אולי מספר שמונה היה כאן.

742
00:24:18,822 --> 00:24:20,530
וכך, אולי הייתי
מקבל מזל,

743
00:24:20,530 --> 00:24:22,460
ודחף שמונה קרוב יותר לסוף.

744
00:24:22,460 --> 00:24:24,710
אז בסופו של היום,
זה סוג של כל הממוצעים החוצה.

745
00:24:24,710 --> 00:24:26,085
אנחנו לא צריכים לדאוג לגבי ארבעה.

746
00:24:26,085 --> 00:24:29,400
כל אכפת לי עכשיו הוא
בחירת האלמנט הקטן ביותר.

747
00:24:29,400 --> 00:24:32,030
>> ועכשיו, מה אני הולך
לעשות הוא לשכוח מספר אחד

748
00:24:32,030 --> 00:24:35,160
באופן קבוע, כי אני יודע ש
רשימה מאחורי כעת מסודרים.

749
00:24:35,160 --> 00:24:36,720
אז הרשימה שלי הייתה בעבר גודל שמונה.

750
00:24:36,720 --> 00:24:37,720
עכשיו, זה בגודל שבע.

751
00:24:37,720 --> 00:24:40,340
אז הבעיה שלי היא מקבלת
קטן יותר, אם כי באופן ליניארי.

752
00:24:40,340 --> 00:24:43,022
אז עכשיו, אני הולך כדי לבחור את
אלמנט הנוכחי קטן, שתי.

753
00:24:43,022 --> 00:24:46,520
שש, שמונה, ארבעה, שלוש, שבע, חמש.

754
00:24:46,520 --> 00:24:47,770
זה היה היסוד הקטן ביותר.

755
00:24:47,770 --> 00:24:49,416
אז מה אני הולך לעשות with--
מה היה השם שלך שוב?

756
00:24:49,416 --> 00:24:49,760
>> יוסף: יוסף.

757
00:24:49,760 --> 00:24:50,085
>> דוד י מלאן: יוסף?

758
00:24:50,085 --> 00:24:52,000
אנחנו הולכים לעזוב יוסף במקום.

759
00:24:52,000 --> 00:24:54,842
עכשיו, אני הולך להעמיד פן
שהבחורים האלה הן-- גם,

760
00:24:54,842 --> 00:24:56,550
אני יודע ששני אלה
כבר מסודרים.

761
00:24:56,550 --> 00:24:58,424
בואו עכשיו להתמקד ב
שאר הרשימה.

762
00:24:58,424 --> 00:25:00,080
שש הוא הנוכחי הקטנים ביותר.

763
00:25:00,080 --> 00:25:01,190
שמונה הוא גדולים יותר.

764
00:25:01,190 --> 00:25:02,970
ארבעה הוא החברה הנוכחית הקטנים ביותר.

765
00:25:02,970 --> 00:25:04,762
שלוש הוא החברה הנוכחית הקטנים ביותר.

766
00:25:04,762 --> 00:25:07,720
אז עכשיו, אני הולך כדי לבחור שלוש,
שהוא-- מה השם שלך שוב?

767
00:25:07,720 --> 00:25:08,190
סרינה: סרינה.

768
00:25:08,190 --> 00:25:10,620
דוד י מלאן: סרינה, אם אתה יכול
לתפוס את המספר שלך והחלפת with--

769
00:25:10,620 --> 00:25:11,550
KALSANG: Kalsang.

770
00:25:11,550 --> 00:25:12,940
דוד י מלאן: Kalsang.

771
00:25:12,940 --> 00:25:15,220
בואו על גב, ואנחנו
הולך להחליף את שני אלה.

772
00:25:15,220 --> 00:25:17,360
ועכשיו, בואו נשים את זה על טייס אוטומטי.

773
00:25:17,360 --> 00:25:21,589
אני הולך ללכת ולהשאיר אותה אליך בחורים
כדי לבחור את האלמנטים הקטנים ביותר הבאים.

774
00:25:21,589 --> 00:25:22,380
דן, דן, דן, דן.

775
00:25:22,380 --> 00:25:24,560
מספר ארבעה, מה שאתה צריך לעשות?

776
00:25:24,560 --> 00:25:26,261
מצוין.

777
00:25:26,261 --> 00:25:27,760
עכשיו, אני הולך לעשות את מעבר אחר.

778
00:25:27,760 --> 00:25:28,590
דן, דן, דן, דן.

779
00:25:28,590 --> 00:25:31,465
אני רואה חמישה הוא הבא הקטן ביותר.

780
00:25:31,465 --> 00:25:32,840
עכשיו, אני הולך לקחת את מסירה נוספת.

781
00:25:32,840 --> 00:25:33,631
דן, דן, דן, דן.

782
00:25:33,631 --> 00:25:34,880
שש הוא הקטנים ביותר.

783
00:25:34,880 --> 00:25:35,520
טוב.

784
00:25:35,520 --> 00:25:36,585
שבע הוא הקטנים ביותר.

785
00:25:36,585 --> 00:25:37,085
ללא שינוי.

786
00:25:37,085 --> 00:25:38,630
שמונה הוא הקטנים ביותר.

787
00:25:38,630 --> 00:25:39,170
בוצע.

788
00:25:39,170 --> 00:25:43,900
>> אז מה בדיוק עשינו על ידי iteratively
בחירת אלמנט אחד אחרי השני

789
00:25:43,900 --> 00:25:47,230
הוא ליישם משהו שאנחנו
הולך למסד כסוג בחירה.

790
00:25:47,230 --> 00:25:49,120
וזה אולי אפילו
פשוט להסביר,

791
00:25:49,120 --> 00:25:51,310
שבפשוטו כמשמעו כל מה שאתה
רוצה לעשות הוא פשוט לשמור

792
00:25:51,310 --> 00:25:54,700
הולך קדימה ואחורה ברשימה
בחירה, היסוד הקטן ביותר הבא,

793
00:25:54,700 --> 00:25:55,720
עד שתסיים.

794
00:25:55,720 --> 00:25:58,650
>> אז זה אפילו פשוט יותר, אולי
באופן אינטואיטיבי, מאשר אחרון.

795
00:25:58,650 --> 00:26:00,020
בואו ננסה שעבר אחד אחד.

796
00:26:00,020 --> 00:26:03,060
אם אתם יכולים לאפס את עצמכם
לעמדות הבאות

797
00:26:03,060 --> 00:26:08,600
פעם אחרונה, בואו נראה אם ​​אנחנו לא יכולים
עכשיו למסד גישה אחת אחרת.

798
00:26:08,600 --> 00:26:12,857
למעשה, היית מישהו
בחוץ רוצה להציע

799
00:26:12,857 --> 00:26:14,440
איך עוד אנחנו יכולים ללכת על עושים את זה?

800
00:26:14,440 --> 00:26:17,439
ללא לזרוק את buzzwords או סוג
תשובות שכבר ידועות,

801
00:26:17,439 --> 00:26:19,689
רק באופן אינטואיטיבי, מה אנחנו יכולים לעשות?

802
00:26:19,689 --> 00:26:21,635
>> קהל: [לא ברור].

803
00:26:21,635 --> 00:26:22,510
דוד י מלאן: כן.

804
00:26:22,510 --> 00:26:24,620
אז יש כמה אינטואיציה גדולה שם.

805
00:26:24,620 --> 00:26:28,020
דברים טובים נראים לקרות עד כה
במדעי מחשב, כאשר אנו מחלקים

806
00:26:28,020 --> 00:26:30,832
ולכבוש את הבעיה של החלוקה
זה במחצית וחצי וחצי.

807
00:26:30,832 --> 00:26:32,540
וכך אכן, אנחנו
יכול להתחיל לעשות את זה.

808
00:26:32,540 --> 00:26:35,754
ולמעשה, זה הולך להיות, אנחנו
לראות, אחד מהפתרונים הטובים ביותר שלנו עדיין.

809
00:26:35,754 --> 00:26:37,420
אבל בואו נחזור לזה לפני זמן רב.

810
00:26:37,420 --> 00:26:40,500
למעשה, אנחנו הולכים לעשות
שקצת מאוחר יותר השבוע.

811
00:26:40,500 --> 00:26:42,180
מה עוד שאנו עשויים לעשות כדי לפתור את זה?

812
00:26:42,180 --> 00:26:44,647
אז כולם כאן ב
כדי אקראי לכאורה.

813
00:26:44,647 --> 00:26:45,230
אתה יודע מה?

814
00:26:45,230 --> 00:26:48,320
במקום ללכת קדימה ואחורה,
הלוך ושוב, הלוך ושוב

815
00:26:48,320 --> 00:26:50,624
בכל פעם, זה מרגיש כמו
אני עושה הרבה הליכה.

816
00:26:50,624 --> 00:26:52,790
למה אני לא פשוט להתחיל ב
תחילתה של הרשימה,

817
00:26:52,790 --> 00:26:54,960
ופשוט לשים ארבעה למקום שלו?

818
00:26:54,960 --> 00:26:59,680
אז הרשה לי להניח לרגע ש
הרשימה שלי היא רק אלמנט ראשון.

819
00:26:59,680 --> 00:27:04,937
האם ארבעה מסודרים ברגע זה בזמן,
אם כל אכפת לי הוא הכל כאן?

820
00:27:04,937 --> 00:27:06,520
זה סוג של trivially אמיתי, נכון?

821
00:27:06,520 --> 00:27:10,000
כמו הרשימה המכילה מספר אחד, ו
המספר שארבעה הוא כמובן מסודרים.

822
00:27:10,000 --> 00:27:13,070
>> אז תן לי רק קובע
שרשימה זו היא מסודרת.

823
00:27:13,070 --> 00:27:15,090
אבל עכשיו יש לי את שאר רשימה זו.

824
00:27:15,090 --> 00:27:17,240
אז עכשיו, אני נתקל בשתי.

825
00:27:17,240 --> 00:27:21,690
איפה עושה שני ברור
שייך ביחס לארבעה?

826
00:27:21,690 --> 00:27:22,580
לפני ארבעה.

827
00:27:22,580 --> 00:27:23,862
אז מה אני יכול לעשות כאן?

828
00:27:23,862 --> 00:27:24,820
מה שמך שוב?

829
00:27:24,820 --> 00:27:25,090
>> יוסף: יוסף.

830
00:27:25,090 --> 00:27:26,030
>> דוד י מלאן: יוסף,
אם אתה יכול צעד אחורה

831
00:27:26,030 --> 00:27:27,790
רק לרגע עם המספר שלך.

832
00:27:27,790 --> 00:27:31,130
ועכשיו מה שצריך לעשות כאן סטפן?

833
00:27:31,130 --> 00:27:33,720
בואו להעביר סטפן כאן.

834
00:27:33,720 --> 00:27:35,520
ועכשיו, בוא יוסף בא לכאן.

835
00:27:35,520 --> 00:27:39,660
ועכשיו, תן לי טוען ש
הכל כאן ממוין.

836
00:27:39,660 --> 00:27:42,474
אז, תוצאה דומה, אבל
גישה שונה במהותו.

837
00:27:42,474 --> 00:27:44,140
אני אפילו לא הסתכלתי מה שם למטה.

838
00:27:44,140 --> 00:27:46,310
אני רק לשמור על לקיחת האלמנטים
כפי שהם מסרו לי,

839
00:27:46,310 --> 00:27:47,240
ולהתמודד איתם.

840
00:27:47,240 --> 00:27:48,330
>> אז עכשיו, אני רואה את המספר שש.

841
00:27:48,330 --> 00:27:51,110
איפה מספר שש שייך?

842
00:27:51,110 --> 00:27:53,250
יש לנו שני, ארבעה, שש.

843
00:27:53,250 --> 00:27:54,800
בדיוק איפה היא עכשיו.

844
00:27:54,800 --> 00:27:57,750
אז בואו נשאיר את זה לבד, ועכשיו
טוען כי חלק זה של הרשימה

845
00:27:57,750 --> 00:27:58,772
כעת מסודרים.

846
00:27:58,772 --> 00:28:01,230
וכך, זה מרגיש ביסוד
שונה בכך שאני רק

847
00:28:01,230 --> 00:28:05,230
נע ברשימה כאן
באופן ליניארי, ואני לא הכפלה בחזרה.

848
00:28:05,230 --> 00:28:05,730
כן.

849
00:28:05,730 --> 00:28:06,230
בסדר.

850
00:28:06,230 --> 00:28:08,190
אז שמונה, שבו אתה שייך?

851
00:28:08,190 --> 00:28:08,730
ממש כאן.

852
00:28:08,730 --> 00:28:09,310
ללא רבב.

853
00:28:09,310 --> 00:28:10,210
אז עכשיו, אחד.

854
00:28:10,210 --> 00:28:10,900
או הו.

855
00:28:10,900 --> 00:28:13,010
זה מרגיש כאילו זה
הולך להיות יקר.

856
00:28:13,010 --> 00:28:15,690
עכשיו, באלגוריתם הקודם,
אני פשוט החלפתי אנשים.

857
00:28:15,690 --> 00:28:18,648
אז אני יכול לשים אותו כל הדרך ב
ההתחלה, אבל אז עברה יוסף.

858
00:28:18,648 --> 00:28:21,450
אבל אם אני מעביר יוסף, עכשיו
מה הולך להיות לא בסדר?

859
00:28:21,450 --> 00:28:24,250
>> עכשיו, יש לי סוג של undone-- לי
לקח צעד אחד קדימה ולאחר מכן

860
00:28:24,250 --> 00:28:26,300
צעד אחד אחורה, כי עכשיו
יוסף היה מקולקל.

861
00:28:26,300 --> 00:28:26,830
אז בואו נעשה את זה.

862
00:28:26,830 --> 00:28:29,150
אם אתה יכול לקחת מספר אחד
וצעד ​​אחורה לרגע.

863
00:28:29,150 --> 00:28:30,490
איך אנחנו יכולים put-- מה
היה השם שלך שוב?

864
00:28:30,490 --> 00:28:31,130
>> ענאן: אנאן.

865
00:28:31,130 --> 00:28:32,610
>> דוד י מלאן: אנאן במקום?

866
00:28:32,610 --> 00:28:36,091
מה צריך לקרות עם כבוד
לשתיים, ארבעה, שישה ושמונה?

867
00:28:36,091 --> 00:28:37,570
כולם צריך לעבור.

868
00:28:37,570 --> 00:28:42,590
אז אם שמונה רוצה להעביר
ראשון, ולאחר מכן שש, אז ארבעה, ואז שני.

869
00:28:42,590 --> 00:28:45,380
ולאחר מכן אנאן, אם היית
רוצה לבוא לכאן, טוב.

870
00:28:45,380 --> 00:28:47,760
אבל כאן, יש לנו רק
סוג של שילם מחיר

871
00:28:47,760 --> 00:28:49,510
בנקודה באלגוריתם שונה.

872
00:28:49,510 --> 00:28:52,550
ואילו בפעם האחרונה עם בחירה
סוג, ואפילו סוג של בועה,

873
00:28:52,550 --> 00:28:54,700
אני הולך אחורה ו
שוב, הלוך ושוב,

874
00:28:54,700 --> 00:28:58,360
אשר בהחלט מוסיף את
זמן-חכם, וממש בשלבים.

875
00:28:58,360 --> 00:29:00,660
>> מיון הכנסה, בהתחלה
מבט, נראה כמו זה

876
00:29:00,660 --> 00:29:05,150
סופר חכם, שבאני רק
התקדמות איטית, הדרגתית,

877
00:29:05,150 --> 00:29:07,120
אבל אני לא הולך זה הלוך ושוב.

878
00:29:07,120 --> 00:29:09,410
אבל אם מישהו הוא אכן
מקולקל, הודעה

879
00:29:09,410 --> 00:29:10,840
כל העבודה רק שהייתי צריכה לעשות.

880
00:29:10,840 --> 00:29:14,750
הייתי צריך להזיז מחצית מהרשימה
רק כדי לפנות מקום למספר אחד.

881
00:29:14,750 --> 00:29:16,790
אז זה אותו הסכום
העבודה עד כה זה

882
00:29:16,790 --> 00:29:18,690
מרגיש, רק סוג שונה של עבודה.

883
00:29:18,690 --> 00:29:19,370
>> בואו נמשיך.

884
00:29:19,370 --> 00:29:22,657
אז עכשיו אנחנו יודעים שכולם
בין אחד ושמונה מסודרים.

885
00:29:22,657 --> 00:29:23,740
הנה, יש לי מספר שלוש.

886
00:29:23,740 --> 00:29:25,864
אם אתה רוצה להרים
מספר שלוש, צעד אחורה אחת.

887
00:29:25,864 --> 00:29:28,260
ומה אתם צריכים לעשות?

888
00:29:28,260 --> 00:29:28,760
כן.

889
00:29:28,760 --> 00:29:33,070
אז זה עוד אחד, שתיים, שלושה צעדים.

890
00:29:33,070 --> 00:29:36,010
שלוש יחידות זמן שרק יעלו
שלי, כך ששלוש יכולים כעת להתאים.

891
00:29:36,010 --> 00:29:37,460
לבסוף, שבע.

892
00:29:37,460 --> 00:29:39,730
>> בואו נלך קדימה ויש לי
אתה לוקח בחזרה צעד.

893
00:29:39,730 --> 00:29:42,780
זה רק הולך לעלות לנו
יחידה אחת של זמן, אבל זה בסדר.

894
00:29:42,780 --> 00:29:44,170
ועכשיו, חמש של הולכים
להיות קצת יותר יקר.

895
00:29:44,170 --> 00:29:45,340
אם ברצונך לקחת צעד אחורה.

896
00:29:45,340 --> 00:29:48,380
אנחנו צריכים לעבור שמונה,
ושבע, ושש.

897
00:29:48,380 --> 00:29:50,749
ואז כולם עכשיו מסודרים.

898
00:29:50,749 --> 00:29:52,290
אז יד גדולה למתנדבים שלנו כאן.

899
00:29:52,290 --> 00:29:53,554
תודה רבה לך.

900
00:29:53,554 --> 00:29:56,220
>> [מחיאות כפות]

901
00:29:56,220 --> 00:29:56,860
>> תודה לכולכם.

902
00:29:56,860 --> 00:29:57,520
תודה לכולכם.

903
00:29:57,520 --> 00:30:02,940
אז בואו לראות עכשיו איך בדיוק
יקר כל שהיה.

904
00:30:02,940 --> 00:30:06,210
הבה נבחן אולי
הפשוט ביותר של אלה, מיון בועות.

905
00:30:06,210 --> 00:30:09,950
ואני אומר פשוטים, רק משום ש
אתה יכול לפתור אותה בתאווה רק על ידי

906
00:30:09,950 --> 00:30:11,660
לתקן את הבעיה pairwise כאן.

907
00:30:11,660 --> 00:30:13,720
לתקן את הבעיה pairwise
כאן, שוב ושוב

908
00:30:13,720 --> 00:30:17,680
ושוב, חוזר כרב
פעמים כמו שאתה באמת צריכים.

909
00:30:17,680 --> 00:30:21,050
>> אז מתברר ש
במין בועה, גם,

910
00:30:21,050 --> 00:30:25,820
כמה צעדים שאני צריך לקחת ב
את המסירה הראשונה של אלגוריתם זה?

911
00:30:25,820 --> 00:30:30,850
אני יכול take-- בואו see-- אחד,
שתיים, שלוש, ארבעה, חמש, שש, שבע.

912
00:30:30,850 --> 00:30:32,190
ויש שמונה אלמנטים כאן.

913
00:30:32,190 --> 00:30:35,280
אז זה כמו צעדים n מינוס 1 ל
לקבל מההתחלה של הרשימה

914
00:30:35,280 --> 00:30:36,380
לסוף הרשימה.

915
00:30:36,380 --> 00:30:41,350
>> אבל עם סוג הבחירה, שאני זוכר
בחירת האלמנטים שוב ושוב

916
00:30:41,350 --> 00:30:44,590
ושוב זה הקטן ביותר,
אני שם אותו במקום,

917
00:30:44,590 --> 00:30:46,616
אבל אז אני לא
מחפש מאחוריי שוב.

918
00:30:46,616 --> 00:30:49,490
אז אני חושב שזה קצת יותר ברור
אז שבפעם הראשונה, אולי אני

919
00:30:49,490 --> 00:30:52,680
צריך לקחת את כל n מינוס 1 צעדים
כדי למצוא את האלמנט הקטן ביותר.

920
00:30:52,680 --> 00:30:55,920
אז שמתי אותם במקום, ואני
פינוי מי שהיה כאן בעבר.

921
00:30:55,920 --> 00:30:57,500
>> אבל אז אין לי ל
להמשיך לחפש ברכיב זה,

922
00:30:57,500 --> 00:30:59,040
כי אני יודע שזה
כבר הקטן ביותר.

923
00:30:59,040 --> 00:31:01,581
אז עכשיו, אני יכול להסתכל רק שבע
אלמנטים, אז שישה אלמנטים,

924
00:31:01,581 --> 00:31:03,290
אז חמישה אלמנטים, אז ארבעה יסודות.

925
00:31:03,290 --> 00:31:06,900
וכך מבחינה מתמטית, אם n הוא
מספר האלמנטים או מספרים

926
00:31:06,900 --> 00:31:11,990
שהתחלנו עם, אתה יכול לדמיין
שזה אותו הדבר כמו n מינוס 1,

927
00:31:11,990 --> 00:31:14,250
בתוספת n מינוס 2 שלבים,
בתוספת n מינוס 3 שלבים,

928
00:31:14,250 --> 00:31:16,780
בתוספת n מינוס 4 שלבים, כל
דרך למטה רק צעד אחד.

929
00:31:16,780 --> 00:31:18,160
ואני באדם האחרון שלי.

930
00:31:18,160 --> 00:31:20,650
>> ואם אתה זוכר שהרבה
של סטטיסטיקת ספרים או ספרי מתמטיקה

931
00:31:20,650 --> 00:31:24,730
יש לי אלה נוסחות ב
כריכה קשה בגב או לפניהם,

932
00:31:24,730 --> 00:31:27,690
מתברר כי סדרה זו
ניתן לבטא במילים פשוטות יותר

933
00:31:27,690 --> 00:31:28,857
כפעמי n n מינוס 1 על 2.

934
00:31:28,857 --> 00:31:31,273
וזה בסדר אם זה לא
בחוד החנית של המוח שלך.

935
00:31:31,273 --> 00:31:32,420
אבל זה אכן נכון.

936
00:31:32,420 --> 00:31:34,449
זה פשוט דרך פשוטה של ​​כתיבתו.

937
00:31:34,449 --> 00:31:36,240
ואז אם אתה חושב
חזרה לבית הספר יסודי,

938
00:31:36,240 --> 00:31:38,698
כאשר אתה רק מתחיל הכפלה
דברים החוצה, זה כמובן,

939
00:31:38,698 --> 00:31:41,820
רק n בריבוע מינוס n מתחלק ב -2.

940
00:31:41,820 --> 00:31:44,772
כל מה שעשיתי הוא להרחיב
הביטויים שיש.

941
00:31:44,772 --> 00:31:46,730
ואז בואו לשכתב זה
קצת אחר.

942
00:31:46,730 --> 00:31:49,780
זה n בריבוע מחולק 2 מינוס n / 2.

943
00:31:49,780 --> 00:31:53,270
>> אז שוב, אני פשוט סוג של יישום
קצת חשבון שולט שם.

944
00:31:53,270 --> 00:31:57,140
אבל שם לב עכשיו שהטווח הגדול ביותר
בביטוי זה, אם אפשר לומר כך,

945
00:31:57,140 --> 00:31:58,540
הוא שn בריבוע.

946
00:31:58,540 --> 00:32:02,910
אז כן, זה n בריבוע
חלקי 2, מינוס n / 2.

947
00:32:02,910 --> 00:32:05,080
>> אבל בדרך כלל, אם n הוא
הולך להיות ערך גדול,

948
00:32:05,080 --> 00:32:08,740
אני הולך לתבוע n שבריבוע
הולך להיות הגורם הדומיננטי.

949
00:32:08,740 --> 00:32:10,490
זה פשוט הולך להיות
תורם גדול

950
00:32:10,490 --> 00:32:12,877
למספר צעדים מ n / 2.

951
00:32:12,877 --> 00:32:13,960
אז מה שאני מתכוון לעשות את זה?

952
00:32:13,960 --> 00:32:16,795
בואו ננסה דוגמא פשוטה, אפילו
למרות שהמתמטיקה מקבלת גדולה קטנה.

953
00:32:16,795 --> 00:32:20,210
>> אז נניח שיש לנו 1 מיליון אנשים
על במה, או 1 מיליון דברים

954
00:32:20,210 --> 00:32:21,320
כי אנחנו רוצים למיין.

955
00:32:21,320 --> 00:32:23,730
בואו נחבר מיליון
לזה בדיוק נוסחה

956
00:32:23,730 --> 00:32:27,230
כדי לראות כמה צעדים שנדרש כלל
כדי למיין מיליון אלמנטים באמצעות למשל,

957
00:32:27,230 --> 00:32:28,560
מיון בחירה.

958
00:32:28,560 --> 00:32:30,760
>> כדי שיהיה לנו את אותה הנוסחה כמו קודם.

959
00:32:30,760 --> 00:32:34,120
הייתי לחבר מיליון, כך שאני מקבל
מיליון בריבוע מחולק 2,

960
00:32:34,120 --> 00:32:35,990
מינוס מיליון מחולקים 2.

961
00:32:35,990 --> 00:32:40,180
אם אני עושה את המתמטיקה שמראש
כאן, יש לנו 500 מליארד

962
00:32:40,180 --> 00:32:47,460
מינוס 500,000, ש
נותן לנו 499999500000,

963
00:32:47,460 --> 00:32:49,270
וזה די גדול לתקן.

964
00:32:49,270 --> 00:32:54,370
>> למעשה, אם אתה משווה עכשיו
499,000,000,000, 999 מ',

965
00:32:54,370 --> 00:33:01,210
500,000 נגד הערך המקורי שלנו,
500 מיליארדים, זה כל כך קרוב ארור.

966
00:33:01,210 --> 00:33:06,850
נכון? n בריבוע מחולק 2 נותן
us-- או לייתר דיוק, n בריבוע מחולק 2

967
00:33:06,850 --> 00:33:08,370
נתן לנו 500 מיליארדים.

968
00:33:08,370 --> 00:33:13,510
זה די המעצבן הזה קרוב
ל499999500000,

969
00:33:13,510 --> 00:33:17,970
כלומר הפחתה את 500,000,
או באופן כללי יותר, הפחתה מ

970
00:33:17,970 --> 00:33:20,010
n בריבוע, לא ממש עניין גדול.

971
00:33:20,010 --> 00:33:22,490
N בריבוע עושה אלה
מספרים גדלים ממש מהר.

972
00:33:22,490 --> 00:33:25,790
>> עכשיו, זה חשוב רק במידה
כפי שאנו, כמדעני מחשב,

973
00:33:25,790 --> 00:33:29,350
בדרך כלל לא הולכים אכפת כל כך הרבה
על הדקויות של נוסחות אלה

974
00:33:29,350 --> 00:33:31,400
ובדיוק מה ש
תשובות מדויקות הן.

975
00:33:31,400 --> 00:33:33,390
אכפת לנו רק זה, אתה יודע מה?

976
00:33:33,390 --> 00:33:37,810
בסופו של היום, נוסחה זו
הוא בסדר הגודל של n בריבוע.

977
00:33:37,810 --> 00:33:39,350
>> כן, אנחנו מחלקים על ידי 2 שם.

978
00:33:39,350 --> 00:33:41,360
כן, אנחנו הפחתה מn מינוס 2.

979
00:33:41,360 --> 00:33:46,860
אבל בסופו של היום, לטווח
כי באמת כואב לנו ועולה לנו

980
00:33:46,860 --> 00:33:48,995
הרבה שלבים הוא שהטווח רבוע.

981
00:33:48,995 --> 00:33:51,370
ואז מה מדען מחשב
הולך בדרך כלל לעשות

982
00:33:51,370 --> 00:33:54,160
הוא מתעלם מכל אלה
תנאי סדר קטנים,

983
00:33:54,160 --> 00:33:56,900
ורק מסתכל על אחד ש
תורם ביותר למחיר.

984
00:33:56,900 --> 00:34:00,530
>> וזה נחמד, כי אנחנו יכולים
עכשיו מדבר בכלליות הרבה יותר

985
00:34:00,530 --> 00:34:02,470
על אלגוריתמים, ויכול להשוות אותם.

986
00:34:02,470 --> 00:34:04,550
והעובדה שאני
באמצעות O זה מכוון.

987
00:34:04,550 --> 00:34:06,680
כשאני אומר על מנת
של, אני באופן ספציפי

988
00:34:06,680 --> 00:34:09,560
בהתייחסו למשהו
בשם א 'גדול וO הגדול

989
00:34:09,560 --> 00:34:14,090
הוא סימון שמחשב
מדען משתמש כדי לתאר

990
00:34:14,090 --> 00:34:16,710
מחויב עליון על משהו.

991
00:34:16,710 --> 00:34:21,150
>> אז אם אתה אומר שאלגוריתם
הוא בO הגדול של n בריבוע,

992
00:34:21,150 --> 00:34:23,380
כפי שהצעתי רק
רגע לפני, אמצעים ש

993
00:34:23,380 --> 00:34:27,710
כי במונחים של הריצה שלה
זמן או את היעילות שלה,

994
00:34:27,710 --> 00:34:30,090
זה לוקח על מנת
של n בריבוע צעדים.

995
00:34:30,090 --> 00:34:31,420
אולי יותר, אולי פחות.

996
00:34:31,420 --> 00:34:33,435
אבל זה בסדר הגודל של n בריבוע.

997
00:34:33,435 --> 00:34:34,560
וזה הגבול העליון.

998
00:34:34,560 --> 00:34:36,530
זה לא הולך להיות
יותר כואב מזה.

999
00:34:36,530 --> 00:34:40,800
זה לא הולך להיות n קוביות, או 2
לn, או משהו הרבה יותר גדול.

1000
00:34:40,800 --> 00:34:43,800
זהו גבול עליון
בכל המחיר שהוא.

1001
00:34:43,800 --> 00:34:46,150
אז בהתחשב בכך ש, בואו
לשקול רק כמה דוגמאות.

1002
00:34:46,150 --> 00:34:49,820
וזו רק רשימה סופית
פעמים ריצה של מאוד נפוצות

1003
00:34:49,820 --> 00:34:52,870
לאלגוריתמים שנועדו להיות
המחשה של כמה דברים יש לנו

1004
00:34:52,870 --> 00:34:53,600
ראה כבר.

1005
00:34:53,600 --> 00:34:58,060
>> כך למשל, במקרה של
מיון בחירה, מה שאני טוען כאן

1006
00:34:58,060 --> 00:35:02,250
פועל ששל מיון הבחירה
הזמן הוא בסדר הגודל של n בריבוע.

1007
00:35:02,250 --> 00:35:06,260
במקרה הגרוע ביותר, אני הולך יש לי
חבורה שלמה של מספרים אקראיים כאן.

1008
00:35:06,260 --> 00:35:08,600
וכפי שראינו מבחינה מתמטית,
אם אני ממשיך ללכת

1009
00:35:08,600 --> 00:35:11,310
ברשימה, באמצעות
רשימה, בחירה הבאה הקטן ביותר

1010
00:35:11,310 --> 00:35:14,410
אלמנט שוב ​​ושוב, אם אני
למעשה לרשום את כל השלבים

1011
00:35:14,410 --> 00:35:18,750
אני לוקח כהצעתי פי נוסחה
לפני, זה בסדר הגודל של n בריבוע

1012
00:35:18,750 --> 00:35:20,370
צעדים שאני לוקח.

1013
00:35:20,370 --> 00:35:24,520
>> ומתברר שבועה
מיין וההכנסה

1014
00:35:24,520 --> 00:35:27,370
רק איטיים כמו במקרה הגרוע ביותר.

1015
00:35:27,370 --> 00:35:32,040
לשקול, למשל, מיון הכנסה,
האלגוריתם האחרון עסקנו ב,

1016
00:35:32,040 --> 00:35:35,500
שהיה לנו להסתכל על האלמנט,
ולאחר מכן הכנס אותו למקום שלו.

1017
00:35:35,500 --> 00:35:38,720
ואז הסתכלנו על האלמנט הבא,
והכניס אותו למקום שלו.

1018
00:35:38,720 --> 00:35:40,990
>> אז לשקול את התרחיש הטוב ביותר האפשרי.

1019
00:35:40,990 --> 00:35:45,590
נניח שהמתנדבים שלי בשורה
ממש כמו זה, אחד עד שמונה,

1020
00:35:45,590 --> 00:35:47,440
כבר מסודרים.

1021
00:35:47,440 --> 00:35:51,300
כמה צעדים הוא מיון ההכנסה
הולך לקחת כדי למיין שמונה אנשים,

1022
00:35:51,300 --> 00:35:55,640
אם הם מגיעים בשלב
נראה כמו זה?

1023
00:35:55,640 --> 00:35:57,410
>> שמונה אנשים כבר מסודרים.

1024
00:35:57,410 --> 00:35:58,760
ואני משתמש במיון הכנסה.

1025
00:35:58,760 --> 00:36:02,180
כי האחרון של האלגוריתמים.

1026
00:36:02,180 --> 00:36:03,640
ובכן, בואו לשחזר ממש מהר.

1027
00:36:03,640 --> 00:36:05,504
אז אם אני מתחיל כאן, אני רואה אחד.

1028
00:36:05,504 --> 00:36:06,420
איפה אחד? שייך

1029
00:36:06,420 --> 00:36:07,730
היא שייכת ממש כאן.

1030
00:36:07,730 --> 00:36:08,330
אני רואה שני.

1031
00:36:08,330 --> 00:36:09,660
איפה שני שייכים?

1032
00:36:09,660 --> 00:36:10,260
ממש כאן.

1033
00:36:10,260 --> 00:36:10,900
אני רואה שלוש.

1034
00:36:10,900 --> 00:36:11,920
איפה שלוש שייכים?

1035
00:36:11,920 --> 00:36:12,480
ממש כאן.

1036
00:36:12,480 --> 00:36:13,100
>> אני רואה ארבעה.

1037
00:36:13,100 --> 00:36:13,600
ממש כאן.

1038
00:36:13,600 --> 00:36:15,660
חמש, שש, שבע, שמונה.

1039
00:36:15,660 --> 00:36:17,320
אין שום סיבה לחזור על עצמי.

1040
00:36:17,320 --> 00:36:21,260
וצעדים כל כך, כמה
הוא שבמונחים של n?

1041
00:36:21,260 --> 00:36:23,870
זה בסדר הגודל של n
צעדים, נכון? n מינוס 1.

1042
00:36:23,870 --> 00:36:27,567
אבל לקחתי מספר ליניארי
צעדים, ועכשיו אני עשיתי.

1043
00:36:27,567 --> 00:36:28,900
אז זה המקרה הטוב, אם כי.

1044
00:36:28,900 --> 00:36:29,983
מה לגבי המקרה הגרוע ביותר?

1045
00:36:29,983 --> 00:36:32,730
מה שמונה על היו שם,
ושבעה למטה היו שם,

1046
00:36:32,730 --> 00:36:35,840
והיו אחד ושני כאן, כל כך
כי הרשימה באמת היו הפוכה?

1047
00:36:35,840 --> 00:36:38,300
>> ובכן, מה שקורה באמת
אם זה המספר?

1048
00:36:38,300 --> 00:36:41,300
ואנחנו נעשה את רק כמה דוגמאות.

1049
00:36:41,300 --> 00:36:49,300
מה אם, אכן, המספר שמונה
הוא כאן, ואופס number--.

1050
00:36:49,300 --> 00:36:52,660

1051
00:36:52,660 --> 00:36:56,430
אז מה אם, אכן, המספר
שמונה הוא כל הדרך לכאן,

1052
00:36:56,430 --> 00:36:57,790
ואני משתמש במיון הכנסה?

1053
00:36:57,790 --> 00:36:58,290
>> אוקיי.

1054
00:36:58,290 --> 00:37:00,280
אני טוען ברגע זה במקום.

1055
00:37:00,280 --> 00:37:03,152
אבל עכשיו, seven-- איפה שבע ללכת?

1056
00:37:03,152 --> 00:37:04,360
כמובן, זה הולך לכאן.

1057
00:37:04,360 --> 00:37:06,760
אז אני צריך לעבור שמונה על מקום אחד.

1058
00:37:06,760 --> 00:37:08,554
עכשיו שש, לאן זה הולך?

1059
00:37:08,554 --> 00:37:09,220
טוב, בסדר.

1060
00:37:09,220 --> 00:37:13,150
עכשיו, אני צריך לעבור על שמונה
מקום, ושבעה על מקום,

1061
00:37:13,150 --> 00:37:14,440
ואז אני מתרסק שש.

1062
00:37:14,440 --> 00:37:16,870
>> אז בפעם הראשונה, זה עלות
שלי צעד אחד כדי לתקן את הדברים,

1063
00:37:16,870 --> 00:37:18,570
אז זה עלה לי שני צעדים כדי לתקן את הדברים.

1064
00:37:18,570 --> 00:37:20,370
כמה צעדים זה
הולך לקחת לתקן

1065
00:37:20,370 --> 00:37:22,720
דברים לשים חמישה במקום הנכון?

1066
00:37:22,720 --> 00:37:23,340
שלוש.

1067
00:37:23,340 --> 00:37:29,520
כי עכשיו יש לי
לעבור אחד, שתיים, שלוש.

1068
00:37:29,520 --> 00:37:32,430
כמה צעדים שזה הולך לקחת
לשים ארבעה במקום הנכון?

1069
00:37:32,430 --> 00:37:36,040
4 בתוספת 5, בתוספת 6, בתוספת 7.

1070
00:37:36,040 --> 00:37:40,260
>> ואז זה מבחינה מתמטית זהה ל
מה שתארנו למיון בחירה.

1071
00:37:40,260 --> 00:37:42,130
יש לנו סדרה זו
זה רק הולך וגדל.

1072
00:37:42,130 --> 00:37:45,650
1 בתוספת 2 פלוס 3 בתוספת 4,
או לחלופין, 7 בתוספת 6

1073
00:37:45,650 --> 00:37:52,610
בתוספת 5 ועוד 4 מוסיף להיום
מטרות לבסדר הגודל של n בריבוע.

1074
00:37:52,610 --> 00:37:57,640
>> אז תן לי לקבוע גם ש
מיון בועות הוא גם בn בריבוע.

1075
00:37:57,640 --> 00:38:01,340
כי עם מיון בועות, כל
פעם שאני עובר על הרשימה,

1076
00:38:01,340 --> 00:38:03,100
אני לוקח את צעדים בערך כמה?

1077
00:38:03,100 --> 00:38:06,260
בכל פעם שאני ממש
ללכת משם לשם?

1078
00:38:06,260 --> 00:38:07,960
בערך n צעדים.

1079
00:38:07,960 --> 00:38:12,650
אבל כמה פעמים אולי אני
צריך לעבור את הרשימה?

1080
00:38:12,650 --> 00:38:13,920
>> ובכן, בערך n זמן.

1081
00:38:13,920 --> 00:38:15,680
אולי n מינוס 1, אבל בערך n פעמים.

1082
00:38:15,680 --> 00:38:16,430
ובכן, מדוע זה כך?

1083
00:38:16,430 --> 00:38:19,560
ובכן, עם מיון בועות, אם
אנחנו מתחילים עם מיון בועות,

1084
00:38:19,560 --> 00:38:23,570
עם הרשימה במקרה הגרוע ביותר האפשרי
מצב, ששוב הוא לגמרי

1085
00:38:23,570 --> 00:38:25,550
לאחור, מה יקרה?

1086
00:38:25,550 --> 00:38:28,830
אני עובר על הרשימה, ומספר
אחד שייך כל הדרך לשם.

1087
00:38:28,830 --> 00:38:33,280
>> אבל עם מיון בועות, כמה רחוק עושה אחד
לעבור על המעבר הראשון שלי ברשימה?

1088
00:38:33,280 --> 00:38:36,620
כמה נקודות שהוא מקבל
קרוב יותר למקום הנכון?

1089
00:38:36,620 --> 00:38:37,240
רק אחד.

1090
00:38:37,240 --> 00:38:40,281
אז אם אתה סיבת סוג של דרך זו,
בכל פעם דרך אלגוריתם זה,

1091
00:38:40,281 --> 00:38:41,880
בערך n הצעדים לוקחים של דוד.

1092
00:38:41,880 --> 00:38:44,940
אבל עובר כמה
ברשימה היא זה

1093
00:38:44,940 --> 00:38:49,060
הולך לקחת לאחד לבועה
לשמאל שבו הוא שייך?

1094
00:38:49,060 --> 00:38:51,840
>> יש לו לנוע כמו,
חללי n בדרך זו.

1095
00:38:51,840 --> 00:38:57,960
אז רק כדי לעשות המיון של הרשימה,
אני צריך ללכת קדימה ואחורה פעמים n.

1096
00:38:57,960 --> 00:39:01,540
ובכל פעם, אני
מסתכל על n אלמנטים.

1097
00:39:01,540 --> 00:39:05,410
אז לעשות על דברים n n פעמים
סדר n בריבוע.

1098
00:39:05,410 --> 00:39:07,220
>> עכשיו, אנו רואים בכמה
של המכנסיים הקצרים ש

1099
00:39:07,220 --> 00:39:10,440
מוטמעים בבעיה הבאה של CS50
נקבע, גישה אחרת באלה,

1100
00:39:10,440 --> 00:39:13,490
אך לעת עתה, בואו פשוט לשקול
כמה פעמים בריצה אחרות,

1101
00:39:13,490 --> 00:39:16,840
במיוחד אם אלה המיון לקחת
קצת זמן לשקוע ב.

1102
00:39:16,840 --> 00:39:21,790
מה אלגוריתם שראינו כבר
שלוקח על עצם את סדר פעולות n?

1103
00:39:21,790 --> 00:39:27,560
>> מה צריך לקחת מספר יניארי
צעדים שראינו עד כה?

1104
00:39:27,560 --> 00:39:29,350
מה זה?

1105
00:39:29,350 --> 00:39:30,480
החיפוש במדריך הטלפון.

1106
00:39:30,480 --> 00:39:31,390
האלגוריתם הראשון.

1107
00:39:31,390 --> 00:39:31,560
נכון?

1108
00:39:31,560 --> 00:39:33,650
איפה אנחנו באופן ליניארי
מחפש מייק סמית?

1109
00:39:33,650 --> 00:39:34,150
אכן.

1110
00:39:34,150 --> 00:39:37,180
משבוע אפס, כשהתחלתי
הפיכת דף אחד בכל פעם,

1111
00:39:37,180 --> 00:39:40,095
ואפילו אמר שזה היה סוג
של אלגוריתם ליניארי תחושה,

1112
00:39:40,095 --> 00:39:42,720
והיו לנו תמונה שעל
לוח עם הקו האדום הישר

1113
00:39:42,720 --> 00:39:44,678
וצהוב ישר
קו, אלה אכן היו

1114
00:39:44,678 --> 00:39:46,810
אלגוריתמים שנמצאים בO הגדול של n.

1115
00:39:46,810 --> 00:39:50,680
>> בגלל למצוא מייק סמית בטלפון
ספר של דפי n, במקרה הגרוע ביותר,

1116
00:39:50,680 --> 00:39:52,422
אולי תיקח אותי n צעדים.

1117
00:39:52,422 --> 00:39:53,630
מה לגבי לקיחת נוכחות?

1118
00:39:53,630 --> 00:39:55,790
אחד שתיים שלוש ארבע חמש שש.

1119
00:39:55,790 --> 00:39:59,420
מה זמן הריצה של זה
אלגוריתם ללקיחת נוכחות?

1120
00:39:59,420 --> 00:40:03,070
O הגדול של n, כי בתאוריה אני
יש לציין שבחדר כולם.

1121
00:40:03,070 --> 00:40:05,861
>> עכשיו כצד, מה על
אופטימיזציה אחרים משבוע אפס?

1122
00:40:05,861 --> 00:40:08,117
שני, ארבעה, שש, שמונה, 10, 12.

1123
00:40:08,117 --> 00:40:10,200
מדען מחשב היית
מבין, חכה רגע,

1124
00:40:10,200 --> 00:40:12,320
זה על סדר
מחולק n על ידי שני שלבים.

1125
00:40:12,320 --> 00:40:12,820
נכון?

1126
00:40:12,820 --> 00:40:14,444
בגלל שאני עושה שני אנשים בכל פעם.

1127
00:40:14,444 --> 00:40:17,015
אבל אנחנו הולכים להתעלם
תנאי סדר נמוכים אלה,

1128
00:40:17,015 --> 00:40:19,140
ואנחנו רק הולכים
לזרוק את הפער על ידי 2,

1129
00:40:19,140 --> 00:40:21,830
ורק אומר, O הגדול של n
לאלגוריתם שכן.

1130
00:40:21,830 --> 00:40:22,760
>> מה לגבי זה?

1131
00:40:22,760 --> 00:40:26,170
אנחנו לדלג על חלק מאלה, אבל מה
היה אלגוריתם שהיה יומן של n?

1132
00:40:26,170 --> 00:40:29,900
זה לקח בערך להיכנס צעדי n?

1133
00:40:29,900 --> 00:40:30,870
הפרד ומשול.

1134
00:40:30,870 --> 00:40:31,369
בדיוק.

1135
00:40:31,369 --> 00:40:33,900
כמו למשל ספר טלפונים ב
שבוע אפס ומוקדם יותר היום,

1136
00:40:33,900 --> 00:40:36,191
שבו חילקנו את הבעיה
שוב ושוב ושוב.

1137
00:40:36,191 --> 00:40:39,070
ציירנו אותו על הלוח בשבוע
אפס כקו ירוק מעוקל,

1138
00:40:39,070 --> 00:40:41,460
ואמרנו שהיום זה היה
אלגוריתם לוגריתמים.

1139
00:40:41,460 --> 00:40:44,970
>> ואכן, צעדי מספר זה
לוקח לבצע הפרד ומשול,

1140
00:40:44,970 --> 00:40:48,610
או החיפוש בינארי כנתחיל
קורא לזה, כמו בספר טלפונים,

1141
00:40:48,610 --> 00:40:50,680
הוא בסדר הגודל של יומן וצעדים.

1142
00:40:50,680 --> 00:40:52,470
וזה קצת מוזר אחד.

1143
00:40:52,470 --> 00:40:54,910
>> מה לוקח צעד אחד,
או לייתר דיוק

1144
00:40:54,910 --> 00:40:56,240
מספר קבוע של צעדים?

1145
00:40:56,240 --> 00:40:58,865
אולי זה שתיים, אולי זה שלוש,
אבל מדען מחשב פשוט

1146
00:40:58,865 --> 00:41:01,423
מפשט אותו כO הגדול של 1,
כמה מספר קבוע של צעדים.

1147
00:41:01,423 --> 00:41:04,256
מה זה משהו שאתה יכול לעשות את זה
לוקח מספר קבוע של צעדים?

1148
00:41:04,256 --> 00:41:08,030

1149
00:41:08,030 --> 00:41:10,930
>> מה זמן הריצה של מחיאות כפיים?

1150
00:41:10,930 --> 00:41:11,920
זמן קבוע.

1151
00:41:11,920 --> 00:41:12,420
נכון?

1152
00:41:12,420 --> 00:41:15,490
כמו, מה זמן הריצה של
עושה כל דבר שלוקח רק אחד

1153
00:41:15,490 --> 00:41:18,570
פעולה, כמו להדפיס F שלום העולם.

1154
00:41:18,570 --> 00:41:24,110
זה יכול להיות אמר להיות זמן קבוע,
אלא אם כן מקרה פינה פחות עם F הדפסה,

1155
00:41:24,110 --> 00:41:28,260
מה עלול זמן הריצה
ההדפסה F להיות בעצם?

1156
00:41:28,260 --> 00:41:28,790
ולמה?

1157
00:41:28,790 --> 00:41:30,550
מה היא מדידת n במקרה זה?

1158
00:41:30,550 --> 00:41:32,251
>> קהל: [לא ברור].

1159
00:41:32,251 --> 00:41:33,250
דוד י מלאן: בדיוק.

1160
00:41:33,250 --> 00:41:34,900
מספר התווים
אנחנו רוצים להדפיס.

1161
00:41:34,900 --> 00:41:36,191
אז זה מאוד תלוי-קשר.

1162
00:41:36,191 --> 00:41:39,910
היום, אנחנו כבר מתמקדים הרבה על
אותיות ומספרים כאן על הלוח.

1163
00:41:39,910 --> 00:41:43,540
אבל זה יכול להיות גם
תווים במחרוזת בפועל.

1164
00:41:43,540 --> 00:41:46,420
אז מתברר שיש עוד
מדד שיתחיל אכפתיות,

1165
00:41:46,420 --> 00:41:48,530
וזה ההפך
של O הגדול, אם אפשר לומר כך.

1166
00:41:48,530 --> 00:41:50,120
>> זה סימון אומגה.

1167
00:41:50,120 --> 00:41:53,380
בעוד O הגדול אומר מה,
גבול עליון על זמן הריצה שלך?

1168
00:41:53,380 --> 00:41:55,580
מקסימאלי, כמה זמן
אולי משהו לקחת?

1169
00:41:55,580 --> 00:41:59,250
מצטער Omega-- זה שומר הקרוב
up-- הוא ההפך מזה,

1170
00:41:59,250 --> 00:42:02,960
לפי זה חסם תחתון על
כמות זמן משהו עלולה לקחת.

1171
00:42:02,960 --> 00:42:10,480
>> כן." למשל, מה אלגוריתם
שנוקט צעדים תמיד בריבוע n?

1172
00:42:10,480 --> 00:42:15,600
ובכן, אחד האלגוריתמים שראינו
היום, למעשה, יכול להיות שגם כן.

1173
00:42:15,600 --> 00:42:16,720
מיון בחירה.

1174
00:42:16,720 --> 00:42:18,270
בחירת סוג די טפשה.

1175
00:42:18,270 --> 00:42:21,760
גם אם מצטער algorithm--, אפילו
אם המערך כבר ממוין,

1176
00:42:21,760 --> 00:42:24,150
מיון בחירה הולך
להמשיך ללכת ברשימה

1177
00:42:24,150 --> 00:42:28,907
לוודא יש לו הקטן ביותר
אלמנט שוב ​​ושוב ושוב.

1178
00:42:28,907 --> 00:42:31,740
ולמרות שאתה בני האדם ב
קהל יודע את זה, חכה רגע,

1179
00:42:31,740 --> 00:42:33,948
אתה כבר עברת את
האלמנט הקטן ביותר, המחשב

1180
00:42:33,948 --> 00:42:37,300
לא יודע שעד שזה נראה
לאורך כל הדרך את הרשימה.

1181
00:42:37,300 --> 00:42:40,240
באופן דומה, גבול תחתון ש
אולי גם לקחת בחשבון

1182
00:42:40,240 --> 00:42:42,000
ייתכן שהגיע הזמן ליניארי.

1183
00:42:42,000 --> 00:42:48,260
>> כמה זמן לוקח ל
אלמנטי n סוג בטוב ביותר

1184
00:42:48,260 --> 00:42:52,420
מקרה באמצעות משהו כמו מיון בועות?

1185
00:42:52,420 --> 00:42:54,280
נניח הרשימה שלך כבר מסודרים.

1186
00:42:54,280 --> 00:42:56,696
אמרנו מיון הבועות לוקח על
סדר n בריבוע צעדים.

1187
00:42:56,696 --> 00:42:59,640
אבל מה אם זה כבר מסודרים?

1188
00:42:59,640 --> 00:43:02,310
מה אם אתה מבין אחרי
מעבר אחד באמצעות המערך

1189
00:43:02,310 --> 00:43:03,540
כי אתה כבר לא עשית שום חילופים?

1190
00:43:03,540 --> 00:43:05,970
האם אתה צריך לשמור על מה שהופך יותר עובר?

1191
00:43:05,970 --> 00:43:06,470
>> מס '

1192
00:43:06,470 --> 00:43:10,340
אז חסם תחתון על מיון בועות
אפשר לומר להיות ליניארי.

1193
00:43:10,340 --> 00:43:11,830
אומגה של n.

1194
00:43:11,830 --> 00:43:14,450
ואנחנו יכולים להסתכל ב
כמו גם אחרים של אלה.

1195
00:43:14,450 --> 00:43:17,990
אז בואו ניקח מבט מהיר
בבית רק להדמיה כאן

1196
00:43:17,990 --> 00:43:20,790
כדי לראות איך אלה להבדיל את עצמם.

1197
00:43:20,790 --> 00:43:24,592
אני הולך לרדת כאן לזה
דף זה זמין באתר האינטרנט של C50,

1198
00:43:24,592 --> 00:43:27,550
אבל זה יהיה כאב כדי לקבל עבודה,
מאז היא משתמשת בטכנולוגיה הנקראת

1199
00:43:27,550 --> 00:43:30,560
יישומוני Java, שהוא
במידה רבה, שאינו נתמך בימים אלה,

1200
00:43:30,560 --> 00:43:32,730
לפחות על ידי Chrome ואחרים מסוימים.

1201
00:43:32,730 --> 00:43:37,070
>> ותן לי ללכת קדימה ולהאיץ זה
ולהסביר מה קורה.

1202
00:43:37,070 --> 00:43:40,840
זוהי הפגנה של בועה
סוג, האלגוריתם הראשון הסתכלנו.

1203
00:43:40,840 --> 00:43:43,950
וזה להדמיה שבכל
ברים אלה מייצג מספר.

1204
00:43:43,950 --> 00:43:45,710
הגדול על הבר,
גדול יותר במספר.

1205
00:43:45,710 --> 00:43:47,520
הקטן על הבר,
קטן המספר.

1206
00:43:47,520 --> 00:43:50,353
ומה שאתה יכול לראות מבחינה ויזואלית, אפילו
למרות שזה הולך סופר מהיר,

1207
00:43:50,353 --> 00:43:53,699
הוא שהבר האדום הוא כמוני,
הליכה הלוך ושוב תיקון בעיות.

1208
00:43:53,699 --> 00:43:56,740
אתה יכול לראות שהאלמנטים גדולים יותר
אכן מבעבע עד תקין,

1209
00:43:56,740 --> 00:43:59,650
והאלמנטים הקטנים יותר
מבעבעים עד השמאל.

1210
00:43:59,650 --> 00:44:01,870
וכאן למטה, אם
למעשה נראה יותר מקרוב,

1211
00:44:01,870 --> 00:44:04,330
אנחנו באמת יכולים לסמוך
מספר ההשוואות ועסקות החלף

1212
00:44:04,330 --> 00:44:05,350
שנעשים.

1213
00:44:05,350 --> 00:44:07,360
>> אבל במקום זה, בואו נסתכל
באלגוריתם השני

1214
00:44:07,360 --> 00:44:11,240
הסתכלנו קודם לכן עימנו
מתנדב, מיון בחירה.

1215
00:44:11,240 --> 00:44:13,500
מבחינה ויזואלית, יש לו
השפעה שונה מאוד.

1216
00:44:13,500 --> 00:44:16,820
אבל זה, שוב, מאוד אינטואיטיבי, ב
כי אנחנו שומרים בחירה הבאה הקטן ביותר

1217
00:44:16,820 --> 00:44:18,660
אלמנט, ויש לנו קצת מזל.

1218
00:44:18,660 --> 00:44:20,110
שהרגשתי ביסוד מהר יותר.

1219
00:44:20,110 --> 00:44:22,840
אבל אם רצנו את זה שוב ושוב
ושוב עם הרבה כניסות,

1220
00:44:22,840 --> 00:44:26,680
היינו רואה שזה אכן
עדיין בריבוע בO הגדול של n.

1221
00:44:26,680 --> 00:44:29,920
>> בואו נעשה שעבר אחד אחד
כאן, מיון הכנסה,

1222
00:44:29,920 --> 00:44:33,180
שהיה האלגוריתם השלישי
הסתכלנו, וזוכר

1223
00:44:33,180 --> 00:44:36,700
שזה אחד עוסק ב
אלמנטים כפי שנתקל בהם,

1224
00:44:36,700 --> 00:44:39,290
אבל אז זה אולי משמרות
דברים על מנת לפנות מקום,

1225
00:44:39,290 --> 00:44:41,660
החדרת אלמנטים שבו הם שייכים.

1226
00:44:41,660 --> 00:44:45,330
>> וזה גם בסופו של מתן
תוצאה סופית. עכשיו כל שלושת אלה

1227
00:44:45,330 --> 00:44:46,490
הרגיש די מהר.

1228
00:44:46,490 --> 00:44:48,740
ואכן, רצתי אותם
בסרטון די טוב.

1229
00:44:48,740 --> 00:44:52,510
אבל ביסודו, הם כולם
די נורא, אם להיות כנה.

1230
00:44:52,510 --> 00:44:56,960
כל אלגוריתמים אלה עד כה
ריצה שבO הגדול של n בריבוע

1231
00:44:56,960 --> 00:44:59,270
לקחת לא מעט
זמן לרוץ בסופו של הדבר.

1232
00:44:59,270 --> 00:45:01,920
>> ואכן, אנו יכולים לראות
ומרגיש את זה לבסוף

1233
00:45:01,920 --> 00:45:04,090
אם אני מושך את הדגמה שלישית ואחרונה זה.

1234
00:45:04,090 --> 00:45:05,840
זהו עוד
ההדמיה שקורה

1235
00:45:05,840 --> 00:45:08,500
להראות מיון בועות בצד השמאל,
מיון בחירה באמצע,

1236
00:45:08,500 --> 00:45:13,410
ומשהו, כאחד משלנו
יד מעלה קודם לכן הציע,

1237
00:45:13,410 --> 00:45:15,020
מיון מיזוג מימין.

1238
00:45:15,020 --> 00:45:16,937
הפרד ומשול
אסטרטגיה בצד הימין.

1239
00:45:16,937 --> 00:45:19,520
וזה, למעשה, מה שאנחנו
הולך להסתכל ביום רביעי.

1240
00:45:19,520 --> 00:45:21,990
אבל בואו זמן אלה לרוץ במקביל.

1241
00:45:21,990 --> 00:45:26,765
זה בערך אותו המספר של
אלמנטים, כל פועלים באותו הזמן.

1242
00:45:26,765 --> 00:45:30,940

1243
00:45:30,940 --> 00:45:34,440
מיון בועות לעומת בחירה
סוג vs סוג המיזוג.

1244
00:45:34,440 --> 00:45:36,760
>> עכשיו, הם כולם פועלים
בתאוריה באותו הזמן.

1245
00:45:36,760 --> 00:45:39,830
המעבד פועל ב
באותה מהירות, אבל אתה

1246
00:45:39,830 --> 00:45:44,014
יכול להרגיש איך זה משעמם
הולך מהר מאוד להפוך ל,

1247
00:45:44,014 --> 00:45:45,930
ורק כמה מהר כש
אנו מזריקים קצת שבוע

1248
00:45:45,930 --> 00:45:49,330
אלגוריתמים של אפס יכול
אנחנו לזרז את העניינים.

1249
00:45:49,330 --> 00:45:51,760
>> ועכשיו בואו להשוות
אלה בצורה זו האחרונה.

1250
00:45:51,760 --> 00:45:55,710
אני הולך קדימה
לאתר האינטרנט של CS50, בי

1251
00:45:55,710 --> 00:45:59,020
יש לנו קישור זה סופי להיום,
שבו מישהו באינטרנט

1252
00:45:59,020 --> 00:46:03,960
באדיבות להרכיב וידאו ש
לוכד מה מיון שונה

1253
00:46:03,960 --> 00:46:07,510
אלגוריתמים נשמעים כמו.

1254
00:46:07,510 --> 00:46:09,577
זה מיון הכנסה.

1255
00:46:09,577 --> 00:46:12,072
>> [צפצוף]

1256
00:46:12,072 --> 00:46:13,070

1257
00:46:13,070 --> 00:46:16,850
>> לפי אתה החלים תדירות
בהתבסס על הגובה של בר הבר.

1258
00:46:16,850 --> 00:46:19,826
זה סוג בועה.

1259
00:46:19,826 --> 00:46:21,822
>> [צפצוף מעוות]

1260
00:46:21,822 --> 00:46:33,299

1261
00:46:33,299 --> 00:46:45,774
>> מתקרב הבא הוא-- הקרוב
עד מיון בחירה הוא-- הבא,

1262
00:46:45,774 --> 00:46:48,820
שבו שוב, אנחנו בחירה
האלמנט הקטן ביותר הבא,

1263
00:46:48,820 --> 00:46:51,820
ואנחנו יכולים לראות את זה הולך וגדל
משמאל לימין.

1264
00:46:51,820 --> 00:47:01,120

1265
00:47:01,120 --> 00:47:04,000
>> מיון מיזוג, הזוכה שלנו עד כה היום.

1266
00:47:04,000 --> 00:47:09,659

1267
00:47:09,659 --> 00:47:12,450
שים לב איך זה חלוקת דברים
ל[ לא ברור] מחצית ורבעים.

1268
00:47:12,450 --> 00:47:17,510

1269
00:47:17,510 --> 00:47:21,660
סוג Gnome, שאין לנו
דיבר על, ויוצר באופן חזותי

1270
00:47:21,660 --> 00:47:24,450
וaudally קצת
צורה שונה וצליל.

1271
00:47:24,450 --> 00:47:27,060

1272
00:47:27,060 --> 00:47:30,160
הולך קדימה ואחורה,
לנקות דברים.

1273
00:47:30,160 --> 00:47:32,230
כמו כן לבדוק את מיון הערימה
באתר האינטרנט של הבחור הזה.

1274
00:47:32,230 --> 00:47:36,100

1275
00:47:36,100 --> 00:47:36,810
>> וזה הכל.

1276
00:47:36,810 --> 00:47:38,210
אנחנו אראה אותך בפעם הבאה.

1277
00:47:38,210 --> 00:47:42,647

1278
00:47:42,647 --> 00:47:48,334
>> [Whooshing ומוסיקה]

1279
00:47:48,334 --> 00:50:24,839