1
00:00:00,000 --> 00:00:11,100
>> [השמעת מוסיקה]

2
00:00:11,100 --> 00:00:11,490
>> דוד י Malan: בסדר.

3
00:00:11,490 --> 00:00:12,170
אז ברוך הבא.

4
00:00:12,170 --> 00:00:15,180
זה CS50, והוא
בסוף השבוע שלוש.

5
00:00:15,180 --> 00:00:17,770
>> אז זוכר בשבועות האחרונים,
אנחנו כבר בילינו לא מעט

6
00:00:17,770 --> 00:00:20,820
זמן על C, בתכנות, בתחביר.

7
00:00:20,820 --> 00:00:24,680
וזה די נורמלי, אם אתה עדיין
נאבק עם בעיה סט 2, להיות

8
00:00:24,680 --> 00:00:25,950
לדפוק את הראש בקיר.

9
00:00:25,950 --> 00:00:28,310
זה הודעות שגיאה למראה מסתורי
ובאגים שאתה

10
00:00:28,310 --> 00:00:29,220
לא ממש יכול לרדוף אחרי.

11
00:00:29,220 --> 00:00:32,310
מכיוון, היה סמוך ובטוח, כי רק
הזמן של כמה שבועות תוכל להביט לאחור על

12
00:00:32,310 --> 00:00:35,930
דברים כמו קיסר, ו[? V-genair,?]
אולי אפילו סדק, ו

13
00:00:35,930 --> 00:00:40,050
להבין עד כמה רחוק הגעת
בתקופה קצרה של זמן.

14
00:00:40,050 --> 00:00:43,670
אז אם זה מנחם אותך,
להיתקע שם לעת עתה.

15
00:00:43,670 --> 00:00:46,610
>> היום, לעומת זאת, אנו מתחילים מעבר
לרמה גבוהה יותר דברים.

16
00:00:46,610 --> 00:00:49,820
ואנחנו מתחילים לקחת כמובן מאליו כי
אתם יודעים איך לתכנת, או

17
00:00:49,820 --> 00:00:52,090
לפחות את ראשיתה של
שרמת הנוחות.

18
00:00:52,090 --> 00:00:56,520
ונתחיל לחשוב איך אנחנו יכולים
ללכת על עיצוב תוכניות יותר

19
00:00:56,520 --> 00:00:57,440
בצורה יעילה.

20
00:00:57,440 --> 00:01:01,090
איך אנחנו יכולים ללכת על ייעול
יעילות של האלגוריתמים שלנו, ו

21
00:01:01,090 --> 00:01:03,110
בדרך כלל פתרון יותר
בעיות מעניינות.

22
00:01:03,110 --> 00:01:06,850
ומתחיל לקחת כמובן מאליו את זה,
אם אנחנו רוצים, אנחנו יכולים לקודד את כל

23
00:01:06,850 --> 00:01:08,350
מדוגמאות שיש לנו בראש.

24
00:01:08,350 --> 00:01:11,430
אז היום, אנחנו לא לגעת במקלדת
לכל צורה של קוד.

25
00:01:11,430 --> 00:01:15,150
זה יהיה ברמה הרבה יותר גבוהה, ו
סופו של דבר, על פתרון בעיות.

26
00:01:15,150 --> 00:01:20,490
>> אז כדי להגיע לנקודה הזאת, הרשה לי להציע
שהשבע הבאים

27
00:01:20,490 --> 00:01:24,290
מלבנים מייצגים שבע דלתות, מאחורי
שהם חבורה שלמה של

28
00:01:24,290 --> 00:01:26,340
מספרים, ביניהם הוא המספר 50.

29
00:01:26,340 --> 00:01:30,470
תן לי את הפרויקט הזה על זה
מסך גם כאן.

30
00:01:30,470 --> 00:01:36,770
ומציע שאנחנו צריכים מתנדבים ל
לעזור למצוא לי מספר לפני

31
00:01:36,770 --> 00:01:38,140
האינטרנט כאן כדי לראות.

32
00:01:38,140 --> 00:01:40,755
בואו למעלה, בצבע הוורוד.

33
00:01:40,755 --> 00:01:43,050
בסדר.

34
00:01:43,050 --> 00:01:43,930
מה שמך?

35
00:01:43,930 --> 00:01:44,850
>> ג'ניפר: [לא ברור]

36
00:01:44,850 --> 00:01:45,170
>> דוד י Malan: סליחה?

37
00:01:45,170 --> 00:01:45,860
>> ג'ניפר: ג'ניפר.

38
00:01:45,860 --> 00:01:46,390
>> דוד י Malan: ג'ניפר.

39
00:01:46,390 --> 00:01:46,980
בסדר, ג'ניפר.

40
00:01:46,980 --> 00:01:47,630
נע מאוד.

41
00:01:47,630 --> 00:01:48,370
בואו נעלה.

42
00:01:48,370 --> 00:01:52,430
אז אלה הנה שבע דלתות, ומה
אני הייתי רוצה שתעשה לנו כאן,

43
00:01:52,430 --> 00:01:56,560
מול כל הכיתה שלך,
הוא ימצא אותנו במספר, 50.

44
00:01:56,560 --> 00:02:00,860
כדי למצוא את מספר, אתה יכול להציץ מאחורי
כל אחת מדלתות אלה פשוט על ידי הקשה

45
00:02:00,860 --> 00:02:03,030
על אחת הדלתות, וזה
יחשוף את מספרו.

46
00:02:03,030 --> 00:02:06,080
ובואו נראה כמה מהר אתה
תוכל למצוא אותנו במספר, 50.

47
00:02:06,080 --> 00:02:09,979

48
00:02:09,979 --> 00:02:11,229
>> 15.

49
00:02:11,229 --> 00:02:13,110

50
00:02:13,110 --> 00:02:14,360
16.

51
00:02:14,360 --> 00:02:16,270

52
00:02:16,270 --> 00:02:16,530
50.

53
00:02:16,530 --> 00:02:17,350
יפה עשה.

54
00:02:17,350 --> 00:02:18,040
בסדר.

55
00:02:18,040 --> 00:02:19,906
מחיאות כפות לג'ניפר.

56
00:02:19,906 --> 00:02:21,530
>> [מחיאות כפות]

57
00:02:21,530 --> 00:02:22,320
>> בסדר.

58
00:02:22,320 --> 00:02:25,254
אז מה הייתה האסטרטגיה שלך עבור
מציאת המספר, 50?

59
00:02:25,254 --> 00:02:27,222
>> ג'ניפר: אום, חשבתי שאולי, אם -

60
00:02:27,222 --> 00:02:27,714
[לא ברור]

61
00:02:27,714 --> 00:02:28,206
>> דוד י Malan: אה.

62
00:02:28,206 --> 00:02:29,630
נותן לו שנייה אחת.

63
00:02:29,630 --> 00:02:32,420
אז הייתה האסטרטגיה שלך עבור
מציאת המספר, 50?

64
00:02:32,420 --> 00:02:34,760
>> ג'ניפר: אז אני פשוט אתחיל בשעה
מתחיל לראות את מה שהמספר הראשון

65
00:02:34,760 --> 00:02:38,590
היה, ואז חשבתי לעצמי, אולי אם
הם מסודרים, אני פשוט אמשיך

66
00:02:38,590 --> 00:02:39,970
הקשה גבוה יותר?

67
00:02:39,970 --> 00:02:40,140
>> דוד י Malan: אישור.

68
00:02:40,140 --> 00:02:42,910
ונראים שאנחנו מוצאים
כי כדי להיות במקרה.

69
00:02:42,910 --> 00:02:45,670
אמנם, בואו לקלף את השכבות
רק קצת, ואתה רוצה ללכת

70
00:02:45,670 --> 00:02:47,640
קדימה ולחשוף את הדלתות האחרות
אתה היה יכול לבחור?

71
00:02:47,640 --> 00:02:50,400

72
00:02:50,400 --> 00:02:51,712
>> ג'ניפר: הו, יקירים.

73
00:02:51,712 --> 00:02:53,128
>> דוד י Malan: אה.

74
00:02:53,128 --> 00:02:54,280
>> ג'ניפר: אז יש לי רק מזל.

75
00:02:54,280 --> 00:02:55,270
>> דוד י Malan: אז יש לך מזל.

76
00:02:55,270 --> 00:02:55,710
בסדר.

77
00:02:55,710 --> 00:02:56,795
אז לא רע.

78
00:02:56,795 --> 00:02:58,750
אבל זה מעניין
תובנה, נכון?

79
00:02:58,750 --> 00:03:01,870
אם אתה מניח, ואתה לא מקבל,
אכן, קצת מזל שם.

80
00:03:01,870 --> 00:03:05,350
אבל אם אתה מניח שהמספרים היו
מיון, אתה יכול להיות מדויק יותר

81
00:03:05,350 --> 00:03:08,750
באשר לאופן שהשפיע על
ההתנהגות שלך?

82
00:03:08,750 --> 00:03:11,715
>> ג'ניפר: אז אם הם מסודרים, אני
חשבתי שאולי הקטן ביותר לגדול ביותר.

83
00:03:11,715 --> 00:03:11,970
>> דוד י Malan: אישור.

84
00:03:11,970 --> 00:03:15,260
>> ג'ניפר: או אם זה בסופו של דבר להיות
ממש גדול, אז הגדול ביותר לקטן ביותר.

85
00:03:15,260 --> 00:03:15,540
>> דוד י Malan: אישור.

86
00:03:15,540 --> 00:03:18,170
אז הגדול ביותר לקטן ביותר, או
הקטן ביותר לגדול ביותר.

87
00:03:18,170 --> 00:03:21,990
אבל הרשה לי להציע, נניח שהיה לך
קיבל חסר מזל, ומניח שהם

88
00:03:21,990 --> 00:03:26,840
לא היו, למעשה, מיון, כמה
הדלתות האלה אולי היו לך להציץ

89
00:03:26,840 --> 00:03:28,590
מאחורי שבמקרה הגרוע ביותר?

90
00:03:28,590 --> 00:03:29,860
>> ג'ניפר: כל אחד מהם.

91
00:03:29,860 --> 00:03:30,420
>> דוד י Malan: כל אחד מהם.

92
00:03:30,420 --> 00:03:31,740
אז בואו להכליל כי כn.

93
00:03:31,740 --> 00:03:34,790
יש קורה להיות 7, אבל בואו יותר
בדרך כלל אומרים שיש דלתות של n על

94
00:03:34,790 --> 00:03:35,650
מסך כאן.

95
00:03:35,650 --> 00:03:40,110
אז במקרה הגרוע ביותר, היית צריכים
להסתכל מאחורי 7 דלתות, או דלתות n.

96
00:03:40,110 --> 00:03:44,140
וכך זה באמת, זה קצת
מזל היום, אבל זה באמת ליניארי

97
00:03:44,140 --> 00:03:46,440
אלגוריתם של מיני, למרות שאתה
היה סוג של דילוג על הסביבה.

98
00:03:46,440 --> 00:03:47,080
האם זה הוגן?

99
00:03:47,080 --> 00:03:47,500
>> ג'ניפר: כן.

100
00:03:47,500 --> 00:03:50,000
>> דוד י Malan: ובכן, תן לי לראות אם שלך
שינויי אסטרטגיה אם אני מעביר לנו

101
00:03:50,000 --> 00:03:52,190
הדוגמא השנייה שלנו כאן עם
7 דלתות שונות.

102
00:03:52,190 --> 00:03:55,240
אותם מספרים, אבל זה
זמן שהם מסודרים.

103
00:03:55,240 --> 00:03:58,350
מה האסטרטגיה שלך הולכת להיות כאן,
מנסה לשים את יצא מדעתך מה

104
00:03:58,350 --> 00:03:59,310
את המספרים האחרים היו -

105
00:03:59,310 --> 00:03:59,930
>> ג'ניפר: אישור.

106
00:03:59,930 --> 00:04:02,290
>> דוד י Malan: - קודם לכן?

107
00:04:02,290 --> 00:04:03,180
>> ג'ניפר: בואו נתחיל
עם הראשון.

108
00:04:03,180 --> 00:04:03,540
>> דוד י Malan: בסדר.

109
00:04:03,540 --> 00:04:05,190
תתחיל עם הראשונה.

110
00:04:05,190 --> 00:04:05,960
4.

111
00:04:05,960 --> 00:04:08,810
עכשיו שבו אתה הולך, ולמה?

112
00:04:08,810 --> 00:04:10,040
>> ג'ניפר: 4 הוא ממש קטן.

113
00:04:10,040 --> 00:04:12,500
אז אם הם פחות או אולי הקטנים ביותר
לגדול ביותר, שהוא צריך

114
00:04:12,500 --> 00:04:13,290
יהיה פעמיים ש, ו--.

115
00:04:13,290 --> 00:04:13,670
>> דוד י Malan: אישור.

116
00:04:13,670 --> 00:04:15,990
בואו נראה, מה שאתה חושב?

117
00:04:15,990 --> 00:04:19,050
>> ג'ניפר: נסה את האחרון.

118
00:04:19,050 --> 00:04:19,500
נחמד.

119
00:04:19,500 --> 00:04:20,880
>> דוד י Malan: מאוד יפה עשה.

120
00:04:20,880 --> 00:04:21,860
בסדר.

121
00:04:21,860 --> 00:04:23,010
>> [מחיאות כפות]

122
00:04:23,010 --> 00:04:24,310
>> דוד י Malan: אישור.

123
00:04:24,310 --> 00:04:26,790
אז אתה בעצם עושה את זה
נורא, כי אתה

124
00:04:26,790 --> 00:04:27,700
עושה את זה טוב מאוד.

125
00:04:27,700 --> 00:04:31,150
מה שמשאיר אותנו לא הצליחו
להפוך נקודות מסוימות.

126
00:04:31,150 --> 00:04:32,565
אז בואו ננסה לגלגל חזרה לכאן.

127
00:04:32,565 --> 00:04:34,560
>> ג'ניפר: אישור.

128
00:04:34,560 --> 00:04:35,980
>> דוד י Malan: טוב מאוד
עשה, בכל זאת.

129
00:04:35,980 --> 00:04:39,060
אז אתה התחיל בהתחלה,
אתה ראית שזה היה 4, אז אתה

130
00:04:39,060 --> 00:04:40,240
עבר לסוף.

131
00:04:40,240 --> 00:04:42,320
אבל נניח שאתה לא מקבל מזל
שם, ומניח 50

132
00:04:42,320 --> 00:04:42,890
היה במקום אחר.

133
00:04:42,890 --> 00:04:46,190
מה הצעד השלישי שלך כבר?

134
00:04:46,190 --> 00:04:47,680
>> ג'ניפר: תחזור להתחלה.

135
00:04:47,680 --> 00:04:48,320
>> דוד י Malan: חזור
להתחלה.

136
00:04:48,320 --> 00:04:51,320
אוקיי, אז אתה כבר נגעת
דלת זו, שהייתה 8.

137
00:04:51,320 --> 00:04:51,660
בסדר.

138
00:04:51,660 --> 00:04:52,650
אז זה לא 50.

139
00:04:52,650 --> 00:04:55,380
איפה היית נראה הבא?

140
00:04:55,380 --> 00:04:56,720
>> ג'ניפר: אם לא עשיתי את זה
יודעים שהם מסודרים.

141
00:04:56,720 --> 00:04:57,005
>> דוד י Malan: נכון.

142
00:04:57,005 --> 00:04:58,490
ובכן, אם אתה לא יודע
הם מסודרים על -

143
00:04:58,490 --> 00:04:58,700
>> ג'ניפר: אה, לא יודע, כן.

144
00:04:58,700 --> 00:05:00,910
>> דוד י Malan: - אבל אתה לא
יודע איפה היו 50 עדיין?

145
00:05:00,910 --> 00:05:01,785
>> ג'ניפר: פשוט להמשיך ללכת.

146
00:05:01,785 --> 00:05:02,130
>> דוד י Malan: בסדר.

147
00:05:02,130 --> 00:05:02,520
אישור.

148
00:05:02,520 --> 00:05:03,800
תמשיך.

149
00:05:03,800 --> 00:05:05,270
בסדר, שאני יכול לעבוד איתו.

150
00:05:05,270 --> 00:05:05,610
>> ג'ניפר: אישור.

151
00:05:05,610 --> 00:05:07,210
>> דוד י Malan: עכשיו, אם אתה רק
הולך להמשיך, מה שלך

152
00:05:07,210 --> 00:05:09,680
האלגוריתם צלל מגובה ל.

153
00:05:09,680 --> 00:05:10,740
>> ג'ניפר: יניארי -.

154
00:05:10,740 --> 00:05:11,820
>> דוד י Malan: זה סוג של ליניארי.

155
00:05:11,820 --> 00:05:13,480
אבל הרשה לי להציע, בואו
לי לשים על המקום.

156
00:05:13,480 --> 00:05:14,900
הרשה לי לרענן את הדף.

157
00:05:14,900 --> 00:05:17,120
אותו מספר, אותו הסדר,
אותן דלתות.

158
00:05:17,120 --> 00:05:21,350
אבל תחשוב אחורה לאותו היום הראשון ב
כיתה כשקרענו ספר טלפונים ב

159
00:05:21,350 --> 00:05:25,480
חצי, פחות או יותר, ומה שהיה
האסטרטגיה שלנו שם?

160
00:05:25,480 --> 00:05:26,450
>> ג'ניפר: התחל באמצע.

161
00:05:26,450 --> 00:05:26,690
>> דוד י Malan: אישור.

162
00:05:26,690 --> 00:05:27,610
אז להתחיל באמצע.

163
00:05:27,610 --> 00:05:28,790
אז בואו נלך קדימה ולדמות ש.

164
00:05:28,790 --> 00:05:30,720
התחל באמצע על ידי
חושף כי דלת.

165
00:05:30,720 --> 00:05:31,660
אז את המספר 16.

166
00:05:31,660 --> 00:05:35,290
אז מה הייתי הבחור החזק שעשה,
שקרע את ספר טלפונים במחצית,

167
00:05:35,290 --> 00:05:38,450
כדי להגיע לניחוש הבא?

168
00:05:38,450 --> 00:05:39,400
>> ג'ניפר: לכו במחצית זו.

169
00:05:39,400 --> 00:05:41,700
>> דוד י Malan: ולמה לימין?

170
00:05:41,700 --> 00:05:43,900
>> ג'ניפר: סוג אם הם היו הקטנים ביותר של
לגודלה, אז צריכים להיות 50

171
00:05:43,900 --> 00:05:44,720
בסופו של דבר זה.

172
00:05:44,720 --> 00:05:44,920
>> דוד י Malan: טוב.

173
00:05:44,920 --> 00:05:45,390
לגמרי סביר.

174
00:05:45,390 --> 00:05:48,380
אז כמו ספר טלפונים, אתה הולך ל
ימין לעומת השמאל, אבל כאן

175
00:05:48,380 --> 00:05:49,500
היא ממסעדה המפתח.

176
00:05:49,500 --> 00:05:53,930
עכשיו אתה יכול לזרוק, או לתלוש,
מחצית מבעיה זו, לא עוזב אותך

177
00:05:53,930 --> 00:05:55,970
עם 7 דלתות, אבל באמת רק עם 3.

178
00:05:55,970 --> 00:05:57,870
שהוא כמחצית מ
גודלה של הבעיה.

179
00:05:57,870 --> 00:05:58,350
בסדר.

180
00:05:58,350 --> 00:06:01,890
אז עכשיו מה יש לך
עשה אחרי שאתה הולך נכון?

181
00:06:01,890 --> 00:06:05,870
>> ג'ניפר: אז 16 הוא עדיין די קטן,
ביחס ל -50, אז אולי אני אנסה,

182
00:06:05,870 --> 00:06:06,700
כאילו, זה אחד.

183
00:06:06,700 --> 00:06:07,890
>> דוד י Malan: בסדר.

184
00:06:07,890 --> 00:06:08,720
42.

185
00:06:08,720 --> 00:06:10,830
בסדר, אז עכשיו מה
אינסטינקט אומר לך?

186
00:06:10,830 --> 00:06:12,100
>> ג'ניפר: אני יכול לזרוק
זה ולאחר מכן פשוט -

187
00:06:12,100 --> 00:06:12,360
>> דוד י Malan: אישור.

188
00:06:12,360 --> 00:06:14,212
טוב, אתה יכול לזרוק
המחצית השמאלית שם.

189
00:06:14,212 --> 00:06:14,890
>> ג'ניפר: - להרים את זה.

190
00:06:14,890 --> 00:06:15,530
>> דוד י Malan: והנכון.

191
00:06:15,530 --> 00:06:15,760
>> ג'ניפר: כן.

192
00:06:15,760 --> 00:06:17,820
>> דוד י Malan: אז למרות שזה קשה
כדי לראות אולי, כאשר יש רק

193
00:06:17,820 --> 00:06:21,320
7 דלתות, לחשוב עליו, עכשיו,
העקביות של

194
00:06:21,320 --> 00:06:22,620
אלגוריתם אתה פשוט ליישם.

195
00:06:22,620 --> 00:06:24,510
במקרה הקודם, שעשית
מזל, שהיה נהדר.

196
00:06:24,510 --> 00:06:26,540
אבל עשית שימוש היוריסטי,
הייתי אומר.

197
00:06:26,540 --> 00:06:29,150
אתה משמש סוג של האינסטינקטים שלך, ו
ידיעה שזה מסודרים, אם זה די

198
00:06:29,150 --> 00:06:31,600
קטן בהתחלה, כמובן, יש לנו
צריך ללכת יותר לצד ימין.

199
00:06:31,600 --> 00:06:34,990
אבל במובן מסוים, יש לך מזל,
כי אולי זה היה המספר 100,

200
00:06:34,990 --> 00:06:36,220
ואולי 50 היו יותר באמצע.

201
00:06:36,220 --> 00:06:37,910
אולי אפילו 50 היו כאן.

202
00:06:37,910 --> 00:06:40,960
>> אבל מה שעשית קצת אחר
הפעם היה, שעשית את אותו הדבר

203
00:06:40,960 --> 00:06:42,150
שוב ושוב.

204
00:06:42,150 --> 00:06:45,310
ואני טוען כי מה שאתה רק
לא, אם כי הושפע מהטלפון

205
00:06:45,310 --> 00:06:48,100
דוגמא ספר, הוא משהו הרבה יותר
יותר אלגוריתמי, ועוד הרבה

206
00:06:48,100 --> 00:06:49,930
בדק פחות מיוחד.

207
00:06:49,930 --> 00:06:51,620
הרבה פחות אינסטינקטיבי.

208
00:06:51,620 --> 00:06:57,160
אז בסופו של היום, איך היית
אתה מתאר את היעילות של

209
00:06:57,160 --> 00:07:00,530
האלגוריתם ראשון, שבו אתה נכנס
משמאל לימין, לעומת

210
00:07:00,530 --> 00:07:03,430
אלגוריתם שני כאן?

211
00:07:03,430 --> 00:07:06,460
>> ג'ניפר: צריך זה אחד, כמו, אולי
לקצץ בחצי את הזמן, או אפילו יותר, כן.

212
00:07:06,460 --> 00:07:07,320
>> דוד י Malan: אוקיי, אולי אפילו יותר.

213
00:07:07,320 --> 00:07:10,150
בואו לדחוף קצת יותר על זה.

214
00:07:10,150 --> 00:07:13,030
מה שבאמת, אם נמשיך זה
היגיון, אנחנו בהחלט חצויים

215
00:07:13,030 --> 00:07:15,830
זמן פועל עם האלגוריתם השני
על ידי לזרוק מחצית

216
00:07:15,830 --> 00:07:18,470
מספרים, אבל מה שאנחנו עושים על הבאים
איטרציה, כאשר חשף ג'ניפר

217
00:07:18,470 --> 00:07:20,615
המספר השני?

218
00:07:20,615 --> 00:07:22,830
>> אנחנו חצויים את המספרים של דלתות שוב.

219
00:07:22,830 --> 00:07:25,270
ואז מה עשה אחרי זה, אם
היו יותר דלתות לשחק איתם?

220
00:07:25,270 --> 00:07:27,520
היינו לחצות אותם, ושוב,
ושוב, ושוב.

221
00:07:27,520 --> 00:07:30,420
וזה היה בדיוק כמו שאתם כל
בעמידה בשבוע הראשון של

222
00:07:30,420 --> 00:07:33,000
בכיתה, חצי מכם יושב, מחצית
שלך בישיבה, חצי מכם

223
00:07:33,000 --> 00:07:35,440
בישיבה, עד שאחד בודד
נשמתו עמדה.

224
00:07:35,440 --> 00:07:39,050
ואנחנו אמרו שזמן הריצה של
כי, את מספר הצעדים שנדרש היה

225
00:07:39,050 --> 00:07:40,430
על הסדר של מה?

226
00:07:40,430 --> 00:07:41,230
>> רמקול 1: [לא ברור]

227
00:07:41,230 --> 00:07:43,970
>> דוד י Malan: אז יומן בסיס 2 של n,
או פשוט יותר פשוט, היכנס של n.

228
00:07:43,970 --> 00:07:45,060
אז משהו לוגריתמי.

229
00:07:45,060 --> 00:07:48,380
והגרף לא היה קו ישר
כי פשוט יש לי יותר ויותר גרוע, זה היה

230
00:07:48,380 --> 00:07:52,490
עקומה מעניינת זה שלא
לקבל כל כך גרוע לאורך זמן.

231
00:07:52,490 --> 00:07:53,910
אז בואו להחזיק ברעיון הזה.

232
00:07:53,910 --> 00:07:54,690
בואו להודות לג'ניפר.

233
00:07:54,690 --> 00:07:56,150
תודה רבה על שבאו עליו.

234
00:07:56,150 --> 00:07:57,400
וגם, שנייה אחת.

235
00:07:57,400 --> 00:08:00,170

236
00:08:00,170 --> 00:08:02,925
אין מנורות שולחן היום, אבל אנחנו
יש לי CS50 כדורי לחץ.

237
00:08:02,925 --> 00:08:03,420
>> ג'ניפר: יש.

238
00:08:03,420 --> 00:08:04,410
>> דוד י Malan: בסדר, כאן.

239
00:08:04,410 --> 00:08:06,545
תודה לך על גביית
לחץ כאן.

240
00:08:06,545 --> 00:08:07,350
בסדר.

241
00:08:07,350 --> 00:08:10,620
אז בואו נראה אם ​​אנחנו לא יכולים עכשיו
למסד את זה קצת יותר.

242
00:08:10,620 --> 00:08:14,820
אז שוב, מה שאנחנו פשוט עשינו היו
בעצם את אותו הדבר כפי שעשינו

243
00:08:14,820 --> 00:08:16,660
בשבוע הראשון ש.

244
00:08:16,660 --> 00:08:23,780
אבל במקום סוף רק עם יניארי
אלגוריתם, שבו אנו מצטיירים

245
00:08:23,780 --> 00:08:27,210
בעבר כקו הישר הזה,
לפיו, אם אנחנו שמים את דלת אחת נוספת על

246
00:08:27,210 --> 00:08:29,610
המסך, ולאחר מכן היית ג'ניפר
יש לו להיראות, באופן פוטנציאלי,

247
00:08:29,610 --> 00:08:30,600
מאחורי דלת אחת יותר.

248
00:08:30,600 --> 00:08:33,490
אם אנחנו שמים את שתי דלתות נוספות, שאולי יש לה
להסתכל מאחורי שתי דלתות נוספות.

249
00:08:33,490 --> 00:08:35,990
>> וכך, לא היה זה ליניארי
קשר בין הגודל של

250
00:08:35,990 --> 00:08:39,059
בעיה, למשל, על ציר x, ו
משך זמן שנדרש כדי

251
00:08:39,059 --> 00:08:40,440
לפתור על y.

252
00:08:40,440 --> 00:08:43,330
אבל התמונה שמרמז על
קודם לכן היה זה קו ירוק.

253
00:08:43,330 --> 00:08:45,970
בכוונה ירוק, משום
זה פשוט הרגיש יותר טוב.

254
00:08:45,970 --> 00:08:49,790
בתאוריה, את האלגוריתם, כשעשינו את זה
עם ספר טלפונים, כשעשינו את זה

255
00:08:49,790 --> 00:08:52,420
עם אתם סומכים אחד את השני, ו
במקרה השני, כאשר רק ג'ניפר

256
00:08:52,420 --> 00:08:55,250
עשה את זה כאן, זה היה סוג
של יסוד טוב יותר.

257
00:08:55,250 --> 00:08:57,180
כי זה לא היה רק ​​במהירות כפולה.

258
00:08:57,180 --> 00:08:58,870
זה לא היה אפילו ארבע פעמים מהר.

259
00:08:58,870 --> 00:09:03,290
זה היה תלוי לחלוטין במה
גודל של הקלט היה, לגבי כמה

260
00:09:03,290 --> 00:09:05,220
צעדים שסופו של דבר לקח.

261
00:09:05,220 --> 00:09:08,040
>> ואז זה רעיון פשוט שכולנו לקחנו
כמובן מאליו בספר טלפונים,

262
00:09:08,040 --> 00:09:10,200
באופן דומה ניתן ליישם
למשהו כמו זה.

263
00:09:10,200 --> 00:09:12,380
וזה עשוי להיות יותר כבדרך אגב
המכונה, כמו שאתה יכול

264
00:09:12,380 --> 00:09:13,940
לדמיין, פרד ומשול.

265
00:09:13,940 --> 00:09:16,390
שלא כמו מה שעשינו, כמובן,
עם ספר טלפונים.

266
00:09:16,390 --> 00:09:18,300
>> אבל pseudocode, כזכור, היה זה.

267
00:09:18,300 --> 00:09:21,800
אז אנחנו לא עושים את זה שוב, אבל זוכרים
בשבוע הראשון, כולנו קמתי

268
00:09:21,800 --> 00:09:25,140
ולאחר מכן מחצית מכם התיישבה, מחצית
אתה התיישב, חצי מכם התיישב.

269
00:09:25,140 --> 00:09:29,280
אלגוריתם שיושם ב
קצת רמאות אגב, בזה, זה

270
00:09:29,280 --> 00:09:32,870
הייתה לא רק אחד ממני לספור,
ביסודו, בצורה יעילה יותר.

271
00:09:32,870 --> 00:09:35,830
במקרה כזה, הייתי מינוף
משאב המשני.

272
00:09:35,830 --> 00:09:39,470
סוג של, מספר מעבדים, מוח מרובים,
אנשים חכמים רבים ב

273
00:09:39,470 --> 00:09:42,740
החדר היה עוזר לי להגיע ממשהו
ליניארית למשהו

274
00:09:42,740 --> 00:09:45,190
לוגריתמי, ממשהו
אדום למשהו ירוק.

275
00:09:45,190 --> 00:09:48,650
>> אבל במקרה הזה, ג'ניפר לבד יכולים
ביסודו לשפר

276
00:09:48,650 --> 00:09:52,370
ביצועים של האלגוריתם הראשון שלה על ידי,
שוב, רק לחשוב קצת יותר קשה.

277
00:09:52,370 --> 00:09:56,650
ועכשיו, כשזה מגיע זמן ליישם
את הדברים האלה, להבין

278
00:09:56,650 --> 00:10:00,670
מה שורות הקוד אתה יכול לכתוב כזה
כי אתה יכול לחזור עליהם שוב, ו

279
00:10:00,670 --> 00:10:03,350
שוב, ושוב, סוג של
בצורה לולאה.

280
00:10:03,350 --> 00:10:06,370
בגלל שאתה לא הולך להיות
יוקרה, כמו ג'ניפר עשתה בהתחלה, כדי

281
00:10:06,370 --> 00:10:10,460
פשוט יש חבורה שלמה של IFS ואומר,
הממ, אם זה מספר הראשון הוא 4,

282
00:10:10,460 --> 00:10:11,800
הרשה לי לקפוץ את כל הדרך עד הסוף.

283
00:10:11,800 --> 00:10:14,180
אוו, אם מספר זה גדול מדי,
תנו לי להעביר באופן שרירותי בחזרה

284
00:10:14,180 --> 00:10:15,220
לאלמנט השני.

285
00:10:15,220 --> 00:10:18,210
אתה תמצא שזה הולך להיות הרבה
קשה יותר למסד את מה שאנו, בני האדם

286
00:10:18,210 --> 00:10:21,270
לוקח כמובן מאליו כסביר מאוד
היוריסטיות, אבל מחשב הוא רק

287
00:10:21,270 --> 00:10:23,260
הולך לעשות את מה שאתה אומר לו לעשות.

288
00:10:23,260 --> 00:10:25,280
>> עכשיו זה מעניין מאוד
השלכות.

289
00:10:25,280 --> 00:10:29,950
הגרף הזה הוא סוג של אמור למיין של
להציף מבחינה ויזואלית, אבל שים לב, שבו

290
00:10:29,950 --> 00:10:32,230
הוא הקו הישר בגרף הזה?

291
00:10:32,230 --> 00:10:35,330
איפה הוא הגרף ליניארי
שאנו קוראים לי n?

292
00:10:35,330 --> 00:10:37,580
ובכן, זה סוג של כיוון החלק התחתון
של התמונה הזאת, נכון?

293
00:10:37,580 --> 00:10:40,500
אז כל מה שעשינו הוא שיש לנו סוג של
תצוגה מוקטן לציר ה-x ו

294
00:10:40,500 --> 00:10:44,780
ציר ה-Y כדי לנסות לקבל תחושה של מה
סוגים אחרים של עקומות להיראות.

295
00:10:44,780 --> 00:10:47,760
>> ואת הפרטים של מתמטי
ביטויים היום לא משנה כל כך

296
00:10:47,760 --> 00:10:52,440
הרבה, אבל שם לב שיש הרבה
אלגוריתמים שהם הרבה יותר גרועים מאשר

297
00:10:52,440 --> 00:10:53,470
משהו שהוא ליניארי.

298
00:10:53,470 --> 00:10:55,410
ואכן, n קוביות נראה די רע.

299
00:10:55,410 --> 00:10:58,400
2 עד n נראה די רעים.
n בריבוע נראה די רע.

300
00:10:58,400 --> 00:11:01,630
ואנו רואים את מה שחלק מאלה
יכול להיות במציאות היום.

301
00:11:01,630 --> 00:11:05,430
והיומן n לא מרגיש רע, אבל
טוב יותר מאשר n הוא יומן בסיס 2 של n.

302
00:11:05,430 --> 00:11:08,080
אבל אתה יודע, זה היה אפילו
יותר מדהים אם ג'ניפר, או אם אנחנו,

303
00:11:08,080 --> 00:11:12,910
בשבוע הראשון, הגיע עם
משהו שהוא יומן של יומן של n.

304
00:11:12,910 --> 00:11:15,880
>> אז במילים אחרות, אין זה כל
מגוון רחב של פתרונות אפשריים ל

305
00:11:15,880 --> 00:11:18,570
בעיות, אך גם כאן, שים לב
מה שהולך לקרות.

306
00:11:18,570 --> 00:11:22,910
כשלהקטין את התצוגה, שבי של העקומות האלה
הוא הולך להוכיח להיות מוחלט

307
00:11:22,910 --> 00:11:26,630
גרוע מאלה המופיעים על המסך עכשיו?

308
00:11:26,630 --> 00:11:28,680
אז n קוביות נראית די
רע באותו הרגע.

309
00:11:28,680 --> 00:11:32,470
אבל אם אנחנו להקטין את התצוגה ולראות יותר של
X וציר ה-Y, מי הולך

310
00:11:32,470 --> 00:11:34,550
לשלוט בסופו של דבר?

311
00:11:34,550 --> 00:11:37,120
אז מתברר למעשה כי ל2
n, ואתה יכול להבין את זה רק על ידי

312
00:11:37,120 --> 00:11:39,990
חיבור בחלק גדול יותר ויותר
מספרים, ואתה תראה ש2 עד

313
00:11:39,990 --> 00:11:42,070
n, אכן, נעשה גדול יותר במהירות רבה יותר.

314
00:11:42,070 --> 00:11:45,530
אם אנחנו באמת להקטין את התצוגה, ל2
אלגוריתם N מבאס לחלוטין.

315
00:11:45,530 --> 00:11:48,170
אני מתכוון לזה הולך לקחת
לא מעט זמן ל

316
00:11:48,170 --> 00:11:49,460
מחשב לנטישת דרך.

317
00:11:49,460 --> 00:11:52,500
>> אבל תראה לאורך זמן, במיוחד
עם סטי בעיה בעתיד ואפילו

318
00:11:52,500 --> 00:11:55,600
פרויקט גמר, הוא את הנתונים שלך
הסט מקבל גדול, בסדר?

319
00:11:55,600 --> 00:11:58,300
גם בגרסה הראשונה של פייסבוק,
ככל שמספר חברים, ו

320
00:11:58,300 --> 00:12:01,840
מספר המשתמשים הרשומים לי גדול,
אתה יכול למיין של טלפון אותו וב

321
00:12:01,840 --> 00:12:05,530
ליישם משהו עם חיפוש ליניארי,
או מיון פשוט מאוד

322
00:12:05,530 --> 00:12:07,030
אלגוריתם, כפי שאנו רואים היום.

323
00:12:07,030 --> 00:12:09,280
אתה צריך להתחיל לחשוב יותר
ויותר על בעיות אלה.

324
00:12:09,280 --> 00:12:12,070
ואת סוגי בעיות כמו מקומות
פייסבוק, וגוגל, ומיקרוסופט,

325
00:12:12,070 --> 00:12:16,350
ולעבוד על אחרים הוא בדיוק אלה
סוג של סוג נתונים גדול של שאלות

326
00:12:16,350 --> 00:12:18,530
יותר ויותר בימים אלה.

327
00:12:18,530 --> 00:12:18,900
>> בסדר.

328
00:12:18,900 --> 00:12:23,800
אז ההצלחה של ג'ניפר שבשני
אלגוריתם, בכנות, שהיא עשתה להפליא

329
00:12:23,800 --> 00:12:26,110
גם בפעם הראשונה, אבל בואו
לכתוב את זה כמזל כדי ש

330
00:12:26,110 --> 00:12:27,000
יכול להפוך לנקודה זו.

331
00:12:27,000 --> 00:12:30,970
במקרה השני, היא ממונפת
אלגוריתם שחזר שוב ו

332
00:12:30,970 --> 00:12:34,670
שוב, אבל היא לקחה כמובן מאליו
הנחה מסוימת שאפשרנו

333
00:12:34,670 --> 00:12:39,370
שלה, אבל היא ניצלו כמה פרטים
פעם שנייה שלא היה לה

334
00:12:39,370 --> 00:12:39,840
הפעם ראשונה.

335
00:12:39,840 --> 00:12:41,800
שהיה מה?

336
00:12:41,800 --> 00:12:43,050
>> שהרשימה ממוינת.

337
00:12:43,050 --> 00:12:46,350
אז ברגע שהרשימה הייתה ממוינת, אנחנו
טוען שג'ניפר היה מסוגל לעשות

338
00:12:46,350 --> 00:12:47,480
ביסודו טוב יותר.

339
00:12:47,480 --> 00:12:51,450
7 דלתות, כן, לא כל כך מעניינת,
אבל מניח שזה אנחנו 7 מ'דלתות.

340
00:12:51,450 --> 00:12:54,080
יומן של n הוא בהחלט הולך
כדי לבצע עוד הרבה, הרבה

341
00:12:54,080 --> 00:12:55,610
מהר יותר בטווח הארוך.

342
00:12:55,610 --> 00:12:58,880
אבל היא הייתה צריכה להיות
דלתות מסודרים בשבילה.

343
00:12:58,880 --> 00:13:02,320
עכשיו, לקחתי את החירות לעשות את זה
מראש על מסך המחשב

344
00:13:02,320 --> 00:13:05,160
כאן, אבל מניח שג'ניפר
הייתי צריך לעשות את זה בעצמה?

345
00:13:05,160 --> 00:13:10,120
נניח שהדלתות בשאלה
נתונים המיוצגים במסד נתונים, או

346
00:13:10,120 --> 00:13:14,260
חברים שנרשמו לפייסבוק, או
כל דפי אינטרנט באינטרנט ה

347
00:13:14,260 --> 00:13:16,880
אתרי אינטרנט שונים עשויים להזדקק
למדד או חיפוש נגמר.

348
00:13:16,880 --> 00:13:20,940
>> נניח שאתה פשוט היה נתונים גולמיים
להגדיר וזה נשאר לך, או ל

349
00:13:20,940 --> 00:13:23,010
ג'ניפר לעשות מיון זה?

350
00:13:23,010 --> 00:13:26,950
זה, ולא, מחייב אותנו לענות
השאלה, טוב, כמה זמן

351
00:13:26,950 --> 00:13:31,080
היה לוקח את ג'ניפר, או אפילו אותי,
כדי למיין את המספרים האלה מראש, כך

352
00:13:31,080 --> 00:13:32,680
שהיא יכולה לנצל את זה?

353
00:13:32,680 --> 00:13:32,880
נכון?

354
00:13:32,880 --> 00:13:36,620
בגלל המשמעות, כמובן, היא
אם זה לוקח לי די הרבה זמן כדי למיין

355
00:13:36,620 --> 00:13:40,800
את המספרים, מי לעזאזל אכפת שאתה
ניתן למצוא מספר כמו 50 כל כך מהר,

356
00:13:40,800 --> 00:13:44,850
כמו במקרה של ג'ניפר, אם לנו יותר מ
המום כמות הזמן כולל

357
00:13:44,850 --> 00:13:46,920
זה לקח ידי מיון דברים מראש?

358
00:13:46,920 --> 00:13:49,320
>> אז בואו נראה אם ​​אנחנו לא יכולים
לצייר את התמונה כאן.

359
00:13:49,320 --> 00:13:51,370
יש לי חבורה שלמה יותר מתח
כדורים, אם זה עוזר

360
00:13:51,370 --> 00:13:52,270
לשבור את הקרח כאן.

361
00:13:52,270 --> 00:13:55,690
ואם לא אכפת לך, אנחנו
צריכים שבע מתנדב -

362
00:13:55,690 --> 00:13:57,060
ב, בסדר.

363
00:13:57,060 --> 00:13:57,240
וואו.

364
00:13:57,240 --> 00:13:59,250
ולכן אנחנו לא צריכים להשקיע
על מנורות שולחן, שזה נראה.

365
00:13:59,250 --> 00:13:59,690
בסדר.

366
00:13:59,690 --> 00:14:01,530
אז מה איתך שתיים בחזית.

367
00:14:01,530 --> 00:14:04,160
מה איתך שני בחורים בגב.

368
00:14:04,160 --> 00:14:04,870
אז זה ארבע.

369
00:14:04,870 --> 00:14:09,890
מה הדעה על אותך מול
חמש, שישה ושבע.

370
00:14:09,890 --> 00:14:10,320
ממש שם.

371
00:14:10,320 --> 00:14:13,260
חבר שלך מצביע לך,
כך שאתה מקבל את הפרס.

372
00:14:13,260 --> 00:14:13,700
>> בסדר.

373
00:14:13,700 --> 00:14:14,410
בואו נעלה.

374
00:14:14,410 --> 00:14:17,120
ולמה אנחנו לא צריכים אותך
החבר 'ה תבוא לכאן.

375
00:14:17,120 --> 00:14:18,960
אני הולך לתת לך את כל מספר.

376
00:14:18,960 --> 00:14:22,150
וללכת קדימה ולסדר את עצמכם
באופן זהה למה שהוא

377
00:14:22,150 --> 00:14:25,180
מתואר על המסך.

378
00:14:25,180 --> 00:14:26,530
>> [חציצת קולות]

379
00:14:26,530 --> 00:14:28,160
>> דוד י Malan: אופס, סליחה.

380
00:14:28,160 --> 00:14:30,210
באג.

381
00:14:30,210 --> 00:14:32,180
בסדר.

382
00:14:32,180 --> 00:14:32,750
ובכן, הנה זה באנו.

383
00:14:32,750 --> 00:14:34,180
מספר חמש.

384
00:14:34,180 --> 00:14:35,136
מספר שש.

385
00:14:35,136 --> 00:14:37,770
אחת, שתיים, שלוש, ארבעה,
חמש, שש, שבע.

386
00:14:37,770 --> 00:14:39,410
אה, זה מביך.

387
00:14:39,410 --> 00:14:41,210
>> רמקול 2: אני רק מקבל -.

388
00:14:41,210 --> 00:14:41,900
>> דוד י Malan: עסקה טובה.

389
00:14:41,900 --> 00:14:43,130
בסדר.

390
00:14:43,130 --> 00:14:44,611
תודה לך על השתתפותך.

391
00:14:44,611 --> 00:14:47,200
>> [מחיאות כפות]

392
00:14:47,200 --> 00:14:48,580
>> אישור.

393
00:14:48,580 --> 00:14:48,860
בסדר.

394
00:14:48,860 --> 00:14:51,970
אז יש לנו ארבעה, שתיים, שש,
אחת, שלוש, שבע, חמש.

395
00:14:51,970 --> 00:14:56,010
כל כך מושלם שיש לנו שבע מתנדב
כאן שהם שווים ברוחב

396
00:14:56,010 --> 00:14:57,430
מערך שאנחנו משחקים
עם קודם לכן.

397
00:14:57,430 --> 00:14:59,470
ואני בחרתי בשבע מסיבות
שיהיה רק

398
00:14:59,470 --> 00:15:00,840
נוח בקצת.

399
00:15:00,840 --> 00:15:04,400
ואני הולך להציע ראשון ש
אנו למיין שבע מתנדבים אלה.

400
00:15:04,400 --> 00:15:06,786
אם ברצונך, ראשון,
להגיד שלום אף.

401
00:15:06,786 --> 00:15:08,970
מאז זה הולך להיות
מביכות כמה דקות.

402
00:15:08,970 --> 00:15:10,370
הציגו את עצמכם.

403
00:15:10,370 --> 00:15:10,980
>> חסד: היי, אני גרייס.

404
00:15:10,980 --> 00:15:14,190
אני בכיתה י 'בבית וורט.

405
00:15:14,190 --> 00:15:14,620
>> ברנסון: היי.

406
00:15:14,620 --> 00:15:15,620
אני רנסון.

407
00:15:15,620 --> 00:15:16,920
אני בכיתה ט 'בולד.

408
00:15:16,920 --> 00:15:19,755

409
00:15:19,755 --> 00:15:20,230
>> GABE: היי.

410
00:15:20,230 --> 00:15:21,040
אני גייב.

411
00:15:21,040 --> 00:15:22,300
אני זוטר בקאבוט.

412
00:15:22,300 --> 00:15:24,826

413
00:15:24,826 --> 00:15:25,980
>> ניל: אני ניל.

414
00:15:25,980 --> 00:15:29,090
אני בכיתה ט 'במתיוס.

415
00:15:29,090 --> 00:15:29,550
>> ג'ייסון: אני ג'ייסון.

416
00:15:29,550 --> 00:15:32,816
אני בכיתה ט 'בGreenough.

417
00:15:32,816 --> 00:15:33,700
>> מייק: מייק לי.

418
00:15:33,700 --> 00:15:37,360
אני בכיתה ט 'באפור.

419
00:15:37,360 --> 00:15:37,990
>> JESS: אני ג'ס.

420
00:15:37,990 --> 00:15:40,313
אני בכיתה י 'בוורט.

421
00:15:40,313 --> 00:15:41,300
>> דוד י Malan: מצוין.

422
00:15:41,300 --> 00:15:41,850
בסדר.

423
00:15:41,850 --> 00:15:44,190
טוב, תודה לכולנו
מתנדבים כאן עד כה.

424
00:15:44,190 --> 00:15:47,110
והאתגר בהישג יד עכשיו הוא הולך
להיות למיין של החבר 'ה האלה, אבל אז

425
00:15:47,110 --> 00:15:50,250
אנחנו הולכים צריכים לחשוב קצת
קשה על מידת יעילות אנחנו באמת

426
00:15:50,250 --> 00:15:51,110
מסודרים עליהם.

427
00:15:51,110 --> 00:15:52,580
אז בואו ננסה את זה ראשון.

428
00:15:52,580 --> 00:15:55,970
אתם יכולים לראות את מספריו של זה
פשוט על ידי הצבת סביב הפינות.

429
00:15:55,970 --> 00:15:59,380
קדימה, לקחת כמה שניות, ו
מיין עצמכם מהקטנים ביותר על

430
00:15:59,380 --> 00:16:01,240
השאיר לגדול ביותר בצד ימין.

431
00:16:01,240 --> 00:16:02,490
ללכת.

432
00:16:02,490 --> 00:16:07,010

433
00:16:07,010 --> 00:16:07,530
>> אישור.

434
00:16:07,530 --> 00:16:08,030
טוב.

435
00:16:08,030 --> 00:16:09,370
זה היה מהיר ממש המעצבן הזה.

436
00:16:09,370 --> 00:16:14,040
עכשיו מישהו כאן, מה שהיה באלגוריתם
שהחבר 'ה האלה מיושם?

437
00:16:14,040 --> 00:16:14,900
>> 1 רמקול: לפחות לגדול ביותר.

438
00:16:14,900 --> 00:16:15,000
>> דוד י Malan: אישור.

439
00:16:15,000 --> 00:16:18,070
לפחות לגדול ביותר הוא באמת סוג של
אובייקטיבי, אבל אני לא בטוח שזה

440
00:16:18,070 --> 00:16:18,890
באמת אלגוריתם.

441
00:16:18,890 --> 00:16:21,810
לפחות לגדול ביותר לא אומר לי
לי צעד אחר צעד מה לעשות.

442
00:16:21,810 --> 00:16:22,833
כן?

443
00:16:22,833 --> 00:16:24,083
>> רמקול 1: [לא ברור]

444
00:16:24,083 --> 00:16:26,010

445
00:16:26,010 --> 00:16:26,280
>> דוד י Malan: אישור.

446
00:16:26,280 --> 00:16:28,920
אז אם אתם רואים אדם קטן יותר
את המספר שלך, ולאחר מכן לעבור ל

447
00:16:28,920 --> 00:16:29,680
זכותם שלהם.

448
00:16:29,680 --> 00:16:32,800
כך שעכשיו מתחיל להיות יותר אקספרסיבי,
יותר כמו אלגוריתם, כי אתה

449
00:16:32,800 --> 00:16:35,410
ניתן לומר, אם כך, אז זה.

450
00:16:35,410 --> 00:16:37,050
אז יש לנו איזה
מבנה מותנה.

451
00:16:37,050 --> 00:16:39,700
ונראה שהחבר 'ה האלה לעשות את זה כמה
פעמים, כי כמה מכם עברו קצת

452
00:16:39,700 --> 00:16:40,420
ממרחק.

453
00:16:40,420 --> 00:16:43,410
כך שלא היה ככל הנראה סוג כלשהו של
לולאה שמתרחשת במוחם.

454
00:16:43,410 --> 00:16:44,610
>> אבל בואו ננסה למסד את זה.

455
00:16:44,610 --> 00:16:47,540
אם אתם יכולים לאפס בחזרה
להסדר זה.

456
00:16:47,540 --> 00:16:50,650
בואו תראו אם אנחנו לא יכולים להסדיר את זה
קצת, ולאחר מכן לשאול את השאלה, רק

457
00:16:50,650 --> 00:16:51,580
כמה יעיל זה?

458
00:16:51,580 --> 00:16:54,220
כמובן, כאשר אנחנו עושים את זה לאט יותר,
זה הולך להרגיש טוב כמו של

459
00:16:54,220 --> 00:16:57,210
אלגוריתם, אבל בואו נראה אם ​​אנחנו יכולים
לשים את האצבעות שלנו על המדרגות המדויקות.

460
00:16:57,210 --> 00:16:58,670
>> אז שניכם ארבעה ושתיים.

461
00:16:58,670 --> 00:17:01,020
או שאתה בסדר נכון או שגוי?

462
00:17:01,020 --> 00:17:01,900
ברור שלא נכון.

463
00:17:01,900 --> 00:17:02,710
אז החליף.

464
00:17:02,710 --> 00:17:05,170
עכשיו אני הולך לזוז הצידה
כאן ואומרים, ארבעה לשש.

465
00:17:05,170 --> 00:17:06,240
האם אתה נכון או שגוי?

466
00:17:06,240 --> 00:17:06,599
>> GABE: נכון.

467
00:17:06,599 --> 00:17:07,180
>> דוד י Malan: נכון.

468
00:17:07,180 --> 00:17:08,300
שש ואחד?

469
00:17:08,300 --> 00:17:08,609
לא ולא.

470
00:17:08,609 --> 00:17:09,630
להחליף.

471
00:17:09,630 --> 00:17:10,490
אז זה שתי החלפות.

472
00:17:10,490 --> 00:17:11,710
שש ושלוש?

473
00:17:11,710 --> 00:17:11,980
לא ולא.

474
00:17:11,980 --> 00:17:13,000
להחליף.

475
00:17:13,000 --> 00:17:13,930
שש ושבע?

476
00:17:13,930 --> 00:17:14,630
נראה טוב.

477
00:17:14,630 --> 00:17:15,396
שבע וחמש?

478
00:17:15,396 --> 00:17:16,150
>> JESS: [לא ברור]

479
00:17:16,150 --> 00:17:17,089
>> דוד י Malan: אוקיי, להחליף.

480
00:17:17,089 --> 00:17:19,770
ומיון.

481
00:17:19,770 --> 00:17:19,980
בסדר.

482
00:17:19,980 --> 00:17:21,440
אז ברור שלא, נכון?

483
00:17:21,440 --> 00:17:22,470
אז יש יותר קורה.

484
00:17:22,470 --> 00:17:24,920
אבל, אכן, החבר 'ה האלה, אפילו
רק באופן אינסטינקטיבי.

485
00:17:24,920 --> 00:17:25,450
המשיך לנוע.

486
00:17:25,450 --> 00:17:27,710
הם לא רק לעצור, ברגע שהם
תיקן את הבעיה אחת.

487
00:17:27,710 --> 00:17:27,839
אז.

488
00:17:27,839 --> 00:17:29,390
ואכן, אני הולך יש לי
לעשות את אותו דבר.

489
00:17:29,390 --> 00:17:32,720
אני הולך צריך למיין מאחורה חזרה
לתחילתו של בעיה זו,

490
00:17:32,720 --> 00:17:35,630
או תחילתו של מערך זה של
אנשים, נתחיל לקרוא אותם.

491
00:17:35,630 --> 00:17:38,366
>> ועכשיו מה שצריך האלגוריתם שלי
במעבר השני יהיה?

492
00:17:38,366 --> 00:17:39,220
>> רמקול 1: אותו דבר.

493
00:17:39,220 --> 00:17:39,940
>> דוד י Malan: אותו דבר.

494
00:17:39,940 --> 00:17:41,460
ואת זה, אני מתחיל לחבב, נכון?

495
00:17:41,460 --> 00:17:44,720
ברגע שאתה יכול למצוא את עצמך עושה
את אותו הדבר שוב ושוב, זה

496
00:17:44,720 --> 00:17:47,890
הופך להיות יותר כמו אלגוריתם,
ופחות אינסטינקט אנושי.

497
00:17:47,890 --> 00:17:48,680
>> אז עכשיו, הנה זה בא שוב.

498
00:17:48,680 --> 00:17:49,870
שניים לארבעה?

499
00:17:49,870 --> 00:17:50,220
לא.

500
00:17:50,220 --> 00:17:51,050
ארבע ואחת?

501
00:17:51,050 --> 00:17:53,380
אה, אכן היה חלק
עובד עדיין צריך להיעשות.

502
00:17:53,380 --> 00:17:53,620
ולשלוש?

503
00:17:53,620 --> 00:17:54,572
טוב.

504
00:17:54,572 --> 00:17:56,000
ארבעה ושש?

505
00:17:56,000 --> 00:17:58,380
שש וחמש?

506
00:17:58,380 --> 00:17:59,470
שש ושבע?

507
00:17:59,470 --> 00:18:00,970
אוקיי, עכשיו, עשה.

508
00:18:00,970 --> 00:18:01,550
אוקיי, לא.

509
00:18:01,550 --> 00:18:02,710
אני חייב לחזור לשם.

510
00:18:02,710 --> 00:18:05,130
>> אז עכשיו, שוב, אנחנו עושים את זה
קצת יותר בכוונה.

511
00:18:05,130 --> 00:18:08,700
ועכשיו, יש רק מוח אחד
ביצוע אלגוריתם זה.

512
00:18:08,700 --> 00:18:10,290
מעבד אחד, אם תרצה.

513
00:18:10,290 --> 00:18:13,090
ולמען האמת, זה המשאב היחיד
אנחנו הולכים כדי לקבל גישה.

514
00:18:13,090 --> 00:18:16,280
וברגע שאנחנו חוזרים למקלדת
ויש לי משהו כמו C ב

515
00:18:16,280 --> 00:18:19,600
לרשות, אנחנו כותבים תכנית היחידה
שיכול לעשות דבר אחד בכל פעם.

516
00:18:19,600 --> 00:18:22,900
לעומת זאת, החבר 'ה האלה לפני רגע, אנחנו
ממונף כוח המוח הקולקטיבי שלהם

517
00:18:22,900 --> 00:18:24,180
כמו שאתם עשו באפס שבוע.

518
00:18:24,180 --> 00:18:24,980
אז בואו נמשיך לעשות את זה.

519
00:18:24,980 --> 00:18:26,260
>> שתיים ואחד.

520
00:18:26,260 --> 00:18:26,945
שתיים ושלוש.

521
00:18:26,945 --> 00:18:27,460
שלוש וארבעה.

522
00:18:27,460 --> 00:18:28,310
ארבעה וחמש.

523
00:18:28,310 --> 00:18:28,620
חמש ושש.

524
00:18:28,620 --> 00:18:30,510
שש ושבע.

525
00:18:30,510 --> 00:18:31,880
עשה?

526
00:18:31,880 --> 00:18:34,560
אז אני, אבל תן לי לשחק
פרקליטו של השטן.

527
00:18:34,560 --> 00:18:37,950
האם אני, הסוג של מחשב שפשוט
עשה עובר דרך מערך זה של

528
00:18:37,950 --> 00:18:40,225
אנשים, יודעים שאני עושה?

529
00:18:40,225 --> 00:18:40,670
>> רמקול 1: מס '

530
00:18:40,670 --> 00:18:41,050
>> דוד י Malan: אז למה?

531
00:18:41,050 --> 00:18:46,900
מה הייתי צריך לעשות כדי
מסקנה נחרצת שאני עושה?

532
00:18:46,900 --> 00:18:48,230
כנראה לעבור עוד אחד.

533
00:18:48,230 --> 00:18:48,430
נכון?

534
00:18:48,430 --> 00:18:51,760
בגלל כל מה שאני יודע מזה קודם
מעבר הוא שתקנתי את טעות.

535
00:18:51,760 --> 00:18:53,920
וזה אומר, אולי יש
עדיין עוד טעות

536
00:18:53,920 --> 00:18:54,840
שאני צריך לתקן.

537
00:18:54,840 --> 00:18:58,680
אז אני יכול רק להיות בטוח על ידי אחורה, ו
לאחר מכן בדיקה, אחד לשתיים, שתיים ו

538
00:18:58,680 --> 00:19:00,940
שלוש, שלושה וארבע, ארבעה וחמש,
חמש ושש, שישה ושבע.

539
00:19:00,940 --> 00:19:02,510
אוקיי, עכשיו אני לא עשיתי את העבודה.

540
00:19:02,510 --> 00:19:05,990
>> אני בהחלט יכול לזכור שאני לא עשיתי
לעבוד עם משהו כמו משתנה,

541
00:19:05,990 --> 00:19:06,975
רוצה int.

542
00:19:06,975 --> 00:19:12,490
תקרא לזה חילופים, ואם החלפות היא 0 ברגע שאני
להגיע לכאן, וזה התחיל ב 0, אז

543
00:19:12,490 --> 00:19:15,520
אני פשוט יהיה טיפשי להמשיך
הלוך ושוב, בודק שוב, ו

544
00:19:15,520 --> 00:19:16,450
שוב, ושוב, נכון?

545
00:19:16,450 --> 00:19:18,450
בגלל שאתה נתקע בחלק
סוג של לולאה אינסופית.

546
00:19:18,450 --> 00:19:21,250
אז ברגע שיש 0 עסקות החלף,
אנחנו יכולים לטעון שזה

547
00:19:21,250 --> 00:19:23,810
האלגוריתם הוא אכן מלא.

548
00:19:23,810 --> 00:19:25,400
>> עכשיו, בואו לשים שם על זה.

549
00:19:25,400 --> 00:19:28,930
האלגוריתם שאני מציע שאנחנו פשוט
יישם משהו שנקרא בועה

550
00:19:28,930 --> 00:19:32,800
סוג שהוא, הידוע בשם כזה, במובן זה
המספרים, כי הם סוג גדול יותר של

551
00:19:32,800 --> 00:19:37,990
בועה עד לקצה את דרכם, או עד
לסוף המערך של מספרים.

552
00:19:37,990 --> 00:19:40,270
אבל איך היה יעיל אלגוריתם זה?

553
00:19:40,270 --> 00:19:44,600
כמה צעדים אני פיזי לא צריך
תיקח, לדוגמה, כדי למיין אלו

554
00:19:44,600 --> 00:19:45,850
שבעה בני אדם?

555
00:19:45,850 --> 00:19:48,560

556
00:19:48,560 --> 00:19:49,550
>> ארבעה עד חמש?

557
00:19:49,550 --> 00:19:51,420
בסדר, יותר מדי הסוף של דבר
הולך להיות התשובה.

558
00:19:51,420 --> 00:19:54,960
אבל אפילו אז, מספר המסוים
הוא לא כל כך מעניין.

559
00:19:54,960 --> 00:19:56,670
בואו להכליל אותו כn.

560
00:19:56,670 --> 00:20:00,520
אז אם הייתי לי n אנשים לכאן, והם
היו, בערך, בסדר אקראיים ב

561
00:20:00,520 --> 00:20:02,180
מתחיל, שבהזמנה המקורית.

562
00:20:02,180 --> 00:20:04,910
ובכן, כמה צעדים שיש לי
לקחת על עצמו לעבור את הראשון?

563
00:20:04,910 --> 00:20:09,810
זה היה אחד, שתיים, שלוש, ארבע, חמש,
שש, והם שבעה בני אדם, ולכן

564
00:20:09,810 --> 00:20:13,670
זה שבע, שש -, אז זה n
מינוס אחד שלבים בפעם הראשונה.

565
00:20:13,670 --> 00:20:16,280
>> עכשיו, כמה צעדים שיש לי
לקחת כשהחזרתי את הסרט?

566
00:20:16,280 --> 00:20:19,310
ובכן, אנחנו יכולים למעשה להכפיל כי אם
באמת שרצינו, אך לעת עתה, אני

567
00:20:19,310 --> 00:20:22,300
פשוט הולך להגיד, בסדר,
n אחר מינוס 1.

568
00:20:22,300 --> 00:20:25,240
אז n מינוס 1 הוא הולך לקבל
מעצבן כדי לעקוב אחר, אז בואו

569
00:20:25,240 --> 00:20:26,400
רק לאסוף מעט.

570
00:20:26,400 --> 00:20:27,770
אז 2n צעדים.

571
00:20:27,770 --> 00:20:29,310
אז 14 צעדים, פחות או יותר.

572
00:20:29,310 --> 00:20:31,930
>> כמה פעמים אני לוקח
צעד בפעם הבאה?

573
00:20:31,930 --> 00:20:33,740
ובכן, זה 3n.

574
00:20:33,740 --> 00:20:34,510
באמת.

575
00:20:34,510 --> 00:20:37,920
ועכשיו, במקרה הגרוע ביותר, עבור
למשל, כמה פעמים הייתי לי

576
00:20:37,920 --> 00:20:41,730
הלך הלוך ושוב, הלוך ושוב,
ביצוע אלגוריתם זה, החלפה

577
00:20:41,730 --> 00:20:44,620
אנשים בכל מעבר, בערך?

578
00:20:44,620 --> 00:20:47,720

579
00:20:47,720 --> 00:20:50,010
זה בעצם n בריבוע, נכון?

580
00:20:50,010 --> 00:20:53,000
>> משום שבמקרה הגרוע ביותר, שאתה יכול סוג
מלחשוב על זה באופן אינטואיטיבי,

581
00:20:53,000 --> 00:20:54,800
למרות שזה עלול לקחת קצת
קצת הזמן להיקלט

582
00:20:54,800 --> 00:20:57,590
במקרה הגרוע ביותר, היית מה אלה
שבעה אנשים שנראים, ב

583
00:20:57,590 --> 00:21:00,230
תנאי ההסדר
המספרים שלהם?

584
00:21:00,230 --> 00:21:01,460
לחלוטין לאחור, נכון?

585
00:21:01,460 --> 00:21:02,815
ורק כדי לדמות את זה,
מה היה השם שלך שוב?

586
00:21:02,815 --> 00:21:03,360
>> מייק: מייק.

587
00:21:03,360 --> 00:21:03,640
>> דוד י Malan: מייק?

588
00:21:03,640 --> 00:21:08,100
אוקיי, מייק, אתה יכול פשוט להצטרף אליי על
כאן רק לשנייה אחת?

589
00:21:08,100 --> 00:21:08,880
למעשה, לא.

590
00:21:08,880 --> 00:21:10,150
מצטער מייק, בואו אחורה.

591
00:21:10,150 --> 00:21:10,910
מה שמך שוב?

592
00:21:10,910 --> 00:21:11,180
>> ניל: ניל.

593
00:21:11,180 --> 00:21:11,640
>> דוד י Malan: ניל.

594
00:21:11,640 --> 00:21:13,750
אוקיי, ניל, אתה בא עם
, אם לא אכפת לך אותי.

595
00:21:13,750 --> 00:21:17,150
אז אני הולך להציע, רק בשביל
פשטות, שניל הוא עכשיו בו

596
00:21:17,150 --> 00:21:18,510
המקרה הגרוע ביותר האפשרי.

597
00:21:18,510 --> 00:21:20,720
אבל אני זוכר איך מיושם
האלגוריתם שלי.

598
00:21:20,720 --> 00:21:24,530
אני משווה, השוואה, השוואה,
השוואה, השוואה, הו.

599
00:21:24,530 --> 00:21:26,640
עכשיו החבר 'ה האלה נמצאים מחוץ
של סדר, ולכן אני מתקן.

600
00:21:26,640 --> 00:21:27,980
אז אתם להחליף.

601
00:21:27,980 --> 00:21:31,630
אבל רואים עכשיו, כמה רחוק
אין ניל צריך ללכת?

602
00:21:31,630 --> 00:21:32,690
זה בערך n.

603
00:21:32,690 --> 00:21:33,570
אתה יודע, זה לא ממש n.

604
00:21:33,570 --> 00:21:36,040
זה כמו, n 1 מינוס, אבל אני מקבל
שמירה על מסלול של מוטרד מעט

605
00:21:36,040 --> 00:21:37,550
מספר, אז בואו פשוט נקראים לזה n.

606
00:21:37,550 --> 00:21:42,860
>> אז אם ניל נע צעד אחד בכל אופן מקסימאלי
זמן, ולנוע צעד אחד ניל,

607
00:21:42,860 --> 00:21:46,580
אני חייב לעשות את המעבר הזה ממש מייגע
הלוך ושוב, זה פחות או יותר

608
00:21:46,580 --> 00:21:52,080
עושה את זה, n צעדים, סך של n פעמים,
כי זה הולך לקחת לי

609
00:21:52,080 --> 00:21:55,820
שצעדים רבים כדי לקבל את כל ניל
בדרך לשם הוא שייך.

610
00:21:55,820 --> 00:21:58,620
שלא לדבר על כל אחד אחר, אם אתם
היו כל אי - הזמין גם כן.

611
00:21:58,620 --> 00:22:01,100
>> אז בואו נקראים למיון בועות n בריבוע.

612
00:22:01,100 --> 00:22:04,860
זמן הריצה של אלגוריתם זה,
ביצועים של אלגוריתם זה,

613
00:22:04,860 --> 00:22:07,120
יעילות של אלגוריתם זה,
אנחנו רק נתאר יותר

614
00:22:07,120 --> 00:22:08,800
בדרך כלל כn בריבוע.

615
00:22:08,800 --> 00:22:11,650
וזה נחמד, כי אני יכול לעשות
אותה דוגמה עם שמונה אנשים, תשע

616
00:22:11,650 --> 00:22:15,450
אנשים, מיליון אנשים, וזה
תשובה היא לא הולכת להשתנות.

617
00:22:15,450 --> 00:22:18,870
>> אז אם אתם לא היו אכפת, בואו
לאפס אותך למקום שבו התחלה.

618
00:22:18,870 --> 00:22:22,510
ובואו ננסה שתי גישות אחרות ו
לראות אם אנחנו לא יכולים לעשות את היסוד

619
00:22:22,510 --> 00:22:23,820
יותר טוב מזה.

620
00:22:23,820 --> 00:22:27,130
אז הפעם, אני הולך להציע
סוג של אלגוריתם שונה.

621
00:22:27,130 --> 00:22:29,950
זה היה חכם מאוד שלנו בפעם האחרונה,
ואתם היו זכות יש לי

622
00:22:29,950 --> 00:22:32,470
אינסטינקטים של רק סוג נכון
של החלפת pairwise.

623
00:22:32,470 --> 00:22:36,500
אבל אם אני באמת רוצה להתקרב לזה
בפשטות, והמטרה שלי היא להעביר את

624
00:22:36,500 --> 00:22:39,800
כל המספרים הקטנים בדרך זו, ו
לדחוף את כל המספרים הגדולים, כי

625
00:22:39,800 --> 00:22:43,030
דרך אגב, למה שאני לא פשוט לעשות את זה ב
נאיבי ביותר דרך אפשרית ולראות אם אני

626
00:22:43,030 --> 00:22:45,730
יכול לעשות טוב יותר ממה שהיה
אלגוריתם מורכב למדי?

627
00:22:45,730 --> 00:22:46,620
>> אז בואו נראה.

628
00:22:46,620 --> 00:22:48,940
ארבעה הוא מספר די קטן, ולכן אני
הולך לעזוב אותך לשם רגע.

629
00:22:48,940 --> 00:22:50,610
או, מספר שתיים הוא אפילו טוב יותר.

630
00:22:50,610 --> 00:22:52,230
אז אתה פשוט יכול לצעוד קדימה
לרגע?

631
00:22:52,230 --> 00:22:55,670
זה נמצא כעת ממוספר הקטן ביותר שלי
מועמד, ואני הולך לזכור

632
00:22:55,670 --> 00:22:57,000
כי איתו, אוהב, משתנה.

633
00:22:57,000 --> 00:22:57,930
אבל אני הולך להמשיך לבדוק.

634
00:22:57,930 --> 00:22:59,890
האם יש מישהו ש
המספר קטן יותר?

635
00:22:59,890 --> 00:23:00,460
שש, לא.

636
00:23:00,460 --> 00:23:01,390
אה, יש ניל שוב.

637
00:23:01,390 --> 00:23:04,050
>> אז אני הולך לדחוף אותך בחזרה
סוג של בחינה מושגית.

638
00:23:04,050 --> 00:23:05,120
ניל יבוא קדימה.

639
00:23:05,120 --> 00:23:08,440
ועכשיו, במשתנה שאני משתמש כדי
לעקוב אחר מי שיש לו הקטן ביותר

640
00:23:08,440 --> 00:23:11,390
מספר מתעדכן להכיל
מיקומו של ניל.

641
00:23:11,390 --> 00:23:12,110
ובכן, הבה נראה.

642
00:23:12,110 --> 00:23:13,960
שלוש, שבע, חמש.

643
00:23:13,960 --> 00:23:15,590
בסדר, אני יודע שניל היה הקטן ביותר.

644
00:23:15,590 --> 00:23:18,110
מה הדבר הפשוט ביותר
בשבילי לעשות עכשיו?

645
00:23:18,110 --> 00:23:21,410
אני לא מתכוון לבזבז את הזמן שלי רק על ידי
מבעבע נקודת ניל אחד לשמאל.

646
00:23:21,410 --> 00:23:25,350
למה שלא פשוט שמתי את ניל שבו הוא
שייך, וזה כמובן לאן?

647
00:23:25,350 --> 00:23:26,160
>> כל הדרך בתחילת.

648
00:23:26,160 --> 00:23:27,720
אז ניל, בואו איתי.

649
00:23:27,720 --> 00:23:28,910
ומה היה השם שלך שוב?

650
00:23:28,910 --> 00:23:29,310
>> חסד: גרייס.

651
00:23:29,310 --> 00:23:29,710
>> דוד י Malan: גרייס.

652
00:23:29,710 --> 00:23:29,920
אישור.

653
00:23:29,920 --> 00:23:32,490
אז גרייס, למרבה הצער, אתה
סוג של בדרך.

654
00:23:32,490 --> 00:23:34,290
אז איך לפתור את הבעיה הזו?

655
00:23:34,290 --> 00:23:34,490
נכון?

656
00:23:34,490 --> 00:23:37,500
אם זה מערך, יש
רק שבעה יישובים.

657
00:23:37,500 --> 00:23:40,830
נזכיר כי, עם רוב, שדברנו עליו
הכרזת גילים, והיה לנו רק

658
00:23:40,830 --> 00:23:41,740
מספר סופי של גילים?

659
00:23:41,740 --> 00:23:42,535
אותו הרעיון כאן.

660
00:23:42,535 --> 00:23:44,300
יש לנו רק מספר סופי של ints.

661
00:23:44,300 --> 00:23:47,590
גרייס היא סוג של בנו
דרך, אז איך אנו לתקן?

662
00:23:47,590 --> 00:23:49,555
>> הדרך הפשוטה ביותר היא כמו,
גרייס, מצטער.

663
00:23:49,555 --> 00:23:51,870
אתה הולך צריך לעבור על
שם, כדי שנוכל להפוך את החדר.

664
00:23:51,870 --> 00:23:55,290
עכשיו, אם אתה חושב על זה, אולי
אנחנו רק החמירו את הבעיה.

665
00:23:55,290 --> 00:23:58,510
ואולי מה שעשינו, משום מה אם
גרייס היו במקום הנכון?

666
00:23:58,510 --> 00:24:01,730
אבל אנחנו יודעים שהיא לא, כי
אחרת, היא הייתה

667
00:24:01,730 --> 00:24:03,980
קדימה עומד במקום
ניל בשלב זה, נכון?

668
00:24:03,980 --> 00:24:05,550
אנחנו כבר בדקנו את מספר הטלפון שלה.

669
00:24:05,550 --> 00:24:05,770
>> בסדר.

670
00:24:05,770 --> 00:24:09,110
אז עכשיו, ניל הוא במקום הנכון, ו
אני יכול לעשות אופטימיזציה קלה.

671
00:24:09,110 --> 00:24:11,740
לרגע הבא, אני הולך להתעלם
ניל כולם יחד, כדי שלא

672
00:24:11,740 --> 00:24:15,280
לבזבז את הזמן שלו, או בטעות
להחליף אותו למקום הלא נכון.

673
00:24:15,280 --> 00:24:17,805
אז עכשיו, איך אני מוצא הבא
אלמנט זה הקטן ביותר?

674
00:24:17,805 --> 00:24:18,480
שתיים.

675
00:24:18,480 --> 00:24:20,225
זה מספר די טוב, אם
אתה רוצה לצעוד קדימה ו

676
00:24:20,225 --> 00:24:21,100
אני זוכר אותך.

677
00:24:21,100 --> 00:24:21,980
שש, לא טוב.

678
00:24:21,980 --> 00:24:24,820
ארבעה, שלוש, שבע, חמש, לא טוב.

679
00:24:24,820 --> 00:24:26,800
אז הרשה לי להעביר לך
המקום הנכון שלך.

680
00:24:26,800 --> 00:24:28,470
ואנחנו רק לי מזל הפעם.

681
00:24:28,470 --> 00:24:31,350
>> עכשיו, אני הולך להתעלם מאלה
שני בחורים, ועכשיו עושה עוד אחד

682
00:24:31,350 --> 00:24:32,260
לעבור את זה.

683
00:24:32,260 --> 00:24:33,490
שש, שמספר די קטן.

684
00:24:33,490 --> 00:24:34,300
יאללה קדימה.

685
00:24:34,300 --> 00:24:35,220
אה, סליחה.

686
00:24:35,220 --> 00:24:37,640
המספר של גרייס הוא טוב יותר,
כך לדרוך על קדימה.

687
00:24:37,640 --> 00:24:38,260
ארבע.

688
00:24:38,260 --> 00:24:39,120
מצטער, גרייס.

689
00:24:39,120 --> 00:24:39,950
אחזור שוב.

690
00:24:39,950 --> 00:24:41,550
מספר שלוש הוא טוב יותר.

691
00:24:41,550 --> 00:24:42,290
שבע.

692
00:24:42,290 --> 00:24:42,720
חמש.

693
00:24:42,720 --> 00:24:43,550
ועכשיו איך קוראים לך שוב?

694
00:24:43,550 --> 00:24:44,000
>> ג'ייסון: ג'ייסון.

695
00:24:44,000 --> 00:24:44,420
>> דוד י Malan: ג'ייסון.

696
00:24:44,420 --> 00:24:47,050
אז ג'ייסון הוא החברה הקטנה ביותר
אלמנט שבחרתי.

697
00:24:47,050 --> 00:24:49,160
איפה הוא מתכוון ללכת?

698
00:24:49,160 --> 00:24:50,380
אז איפה הוא שש.

699
00:24:50,380 --> 00:24:51,210
והשם שלך הוא שוב?

700
00:24:51,210 --> 00:24:51,710
>> GABE: גייב.

701
00:24:51,710 --> 00:24:52,340
>> דוד י Malan: גייב.

702
00:24:52,340 --> 00:24:53,220
גייב הוא בדרך.

703
00:24:53,220 --> 00:24:54,640
מה הדבר הכי קל לעשות?

704
00:24:54,640 --> 00:24:58,390
להחליף את שני החבר 'ה האלה ולהמשיך.

705
00:24:58,390 --> 00:24:59,020
אז עכשיו בואו נראה.

706
00:24:59,020 --> 00:25:00,170
מי הקטן?

707
00:25:00,170 --> 00:25:01,030
ארבע.

708
00:25:01,030 --> 00:25:01,990
תן לי רק סוג של רמאות.

709
00:25:01,990 --> 00:25:03,090
חמישה הולכים להיות הקטן ביותר.

710
00:25:03,090 --> 00:25:05,220
אני מוצא הבא, אם, אתה רוצה לשלב
קדימה, מה אני צריך לעשות עם

711
00:25:05,220 --> 00:25:06,820
החבר 'ה האלה, עם גייב?

712
00:25:06,820 --> 00:25:08,450
להחליף שוב.

713
00:25:08,450 --> 00:25:10,740
אז עכשיו, עדיין מעט מקולקל.

714
00:25:10,740 --> 00:25:14,140
מצאתי את גייב להיות הקטן ביותר, ולכן
אני קופץ החוצה אותו, להעביר לך החבר 'ה נגמרה.

715
00:25:14,140 --> 00:25:15,190
ועשה.

716
00:25:15,190 --> 00:25:17,200
>> אז תשובה היא אותו הדבר.

717
00:25:17,200 --> 00:25:18,600
התוצאה הסופית היא זהה.

718
00:25:18,600 --> 00:25:22,730
איזו משני אלגוריתמים אלה
מה עדיף?

719
00:25:22,730 --> 00:25:23,500
השנייה אחת, ששמעתי.

720
00:25:23,500 --> 00:25:24,252
למה?

721
00:25:24,252 --> 00:25:25,900
>> רמקול 3: הוא n צעדים [לא ברור].

722
00:25:25,900 --> 00:25:27,600
>> דוד י Malan: זה n צעדים לכל היותר.

723
00:25:27,600 --> 00:25:28,490
מעניין.

724
00:25:28,490 --> 00:25:30,610
אז האם זה בכל זאת?

725
00:25:30,610 --> 00:25:33,630
אז איך אני מוצא
האלמנט הקטן ביותר?

726
00:25:33,630 --> 00:25:37,060
כמה צעדים שאני צריך לקחת
למצוא את האלמנט הקטן ביותר?

727
00:25:37,060 --> 00:25:39,220
הייתי לי להסתכל כל הדרך
בסוף, נכון?

728
00:25:39,220 --> 00:25:41,530
משום שבמקרה הגרוע ביותר, מה
אם ניל היה כאן?

729
00:25:41,530 --> 00:25:45,700
כל כך פשוט למצוא את האיבר הקטן ביותר
לוקח לי n צעדים, או n מינוס 1.

730
00:25:45,700 --> 00:25:46,100
אבל, בסדר.

731
00:25:46,100 --> 00:25:46,980
אז לתקן את ניל.

732
00:25:46,980 --> 00:25:48,740
זכור כי, דקה או שתיים לפני.

733
00:25:48,740 --> 00:25:51,680
>> אבל איך אני לא מוצא הבא
האלמנט הקטן ביותר?

734
00:25:51,680 --> 00:25:54,830
זה n 1 מינוס, או n מינוס 2 באמת,
ממספר השלבים.

735
00:25:54,830 --> 00:25:55,440
אז על אישור.

736
00:25:55,440 --> 00:25:57,390
אז אני לא n מינוס 2.

737
00:25:57,390 --> 00:25:57,600
בסדר.

738
00:25:57,600 --> 00:25:59,130
אז זה מרגיש קצת יותר טוב.

739
00:25:59,130 --> 00:25:59,730
בסדר.

740
00:25:59,730 --> 00:26:03,270
כמה צעדים בפעם הבאה
כדי למצוא את המספר שלוש?

741
00:26:03,270 --> 00:26:04,420
אז n מינוס 4.

742
00:26:04,420 --> 00:26:07,670
אז זה יורד, אחד פחות
לדרוך על כל איטרציה.

743
00:26:07,670 --> 00:26:08,740
אז זה מרגיש יותר טוב, נכון?

744
00:26:08,740 --> 00:26:13,450
אם הפעם האחרונה שזה היה בערך הפעמים n n,
הפעם זה n 1 מינוס, פלוס מינוס n

745
00:26:13,450 --> 00:26:16,500
2, בתוספת n מינוס 3, בתוספת n
4 מינוס, נקודה, נקודה, נקודה.

746
00:26:16,500 --> 00:26:18,750
אבל אם אתה זוכר מהתיכון שלך
ספרי לימוד, לרמות קצת

747
00:26:18,750 --> 00:26:24,380
גיליון בחלק האחורי שיש נוסחאות, אם
אתה מוסיף את זה סדרה של מספרים,

748
00:26:24,380 --> 00:26:31,280
מה הוא המספר הכולל של צעדים
הולך להיות שאני לוקח כאן?

749
00:26:31,280 --> 00:26:36,580
>> זה אחד מאלה, כמו, n מינוס
1, הפעמים n, מחולק על ידי 2.

750
00:26:36,580 --> 00:26:39,040
אז תן לי לראות אם אני יכול למשוך
את זה רק לרגע.

751
00:26:39,040 --> 00:26:42,230
ושוב, אני סוג של עיגול חלק
מספרים רק כדי לשמור על החיים שלנו פשוט,

752
00:26:42,230 --> 00:26:47,830
אבל ככל הזכור לי, זה משהו כמו אם
אני עושה n מינוס 1 דברים, אז n מינוס

753
00:26:47,830 --> 00:26:53,570
2, ולאחר מכן n מינוס 3, זה בערך
משהו כזה מעל 2, ואם אני

754
00:26:53,570 --> 00:26:55,510
תכפיל את זה, זה
למעשה n מרובע.

755
00:26:55,510 --> 00:26:58,940
זה לא מרגיש כל כך טוב.
n מינוס n מעל 2.

756
00:26:58,940 --> 00:27:00,350
>> אבל הנה הדבר.

757
00:27:00,350 --> 00:27:03,720
במדעי מחשב, כאשר הבעיות
מתחיל להיות מעניין הוא כאשר n

758
00:27:03,720 --> 00:27:04,700
נהיה ממש גדול.

759
00:27:04,700 --> 00:27:08,110
וכאשר n נהיה ממש גדול, שמתוך
הערכים אלה הולכים לשלוט בכל

760
00:27:08,110 --> 00:27:09,750
של אחרים?

761
00:27:09,750 --> 00:27:10,990
זה סוג של n בריבוע, נכון?

762
00:27:10,990 --> 00:27:13,340
כן, החלוקה ב 2 היא די טובה.

763
00:27:13,340 --> 00:27:16,740
אבל על מיליארדים, אם אתה מדבר
של פיסות מידע או טריליוני

764
00:27:16,740 --> 00:27:18,700
פיסות מידע, בסדר, אז
אתה במהירות כפולה.

765
00:27:18,700 --> 00:27:22,440
אבל מי שבאמת אכפת אם מספר גדול זה,
אם גורם זה הוא מה שמקבל

766
00:27:22,440 --> 00:27:23,040
יותר ויותר גדול.

767
00:27:23,040 --> 00:27:25,990
ואין ספק, זה עושה יותר
הבדל מהבחור הזה.

768
00:27:25,990 --> 00:27:29,120
אז למרות שאתם צודקים,
אלגוריתם שני, אנחנו קוראים לזה

769
00:27:29,120 --> 00:27:32,970
מיון בחירה, הוא, בעולם האמיתי,
קצת יותר מהר באופן פוטנציאלי, משום שאני

770
00:27:32,970 --> 00:27:35,360
לוקח פחות ופחות
צעדים בכל פעם.

771
00:27:35,360 --> 00:27:37,340
>> זה לא באמת מהותי יותר מהר.

772
00:27:37,340 --> 00:27:41,430
כי אם אנחנו באמת לשחק את זה ל
ערכים גדולים של n, בסוף

773
00:27:41,430 --> 00:27:44,750
היום, למספיק n הגדול, זה עדיין
הולך להרגיש די איטי.

774
00:27:44,750 --> 00:27:46,770
ובכן, הרשה לי לקחת את אחד
המעבר אחרון בזה.

775
00:27:46,770 --> 00:27:48,920
זה מה שאני מכנה
מיון בחירה.

776
00:27:48,920 --> 00:27:51,040
אתם יכולים לאפס את עצמכם
בפעם האחרונה?

777
00:27:51,040 --> 00:27:53,550
ובמקרה האחרון זה, אני הולך
להציע משהו

778
00:27:53,550 --> 00:27:54,970
נקרא סוג כניסה.

779
00:27:54,970 --> 00:27:57,470
להיות סוג תחיבה, רעיוני,
קצת שונה.

780
00:27:57,470 --> 00:28:00,980
>> במקום ללכת קדימה ואחורה ו
בחירת האלמנט הקטן ביותר, אני

781
00:28:00,980 --> 00:28:05,030
פשוט הולך להתמודד עם כל אחד מאלה
חבר 'ה כמו שאני נתקל בהם, ולהכניס

782
00:28:05,030 --> 00:28:06,850
אותם למקום הנכון שלהם.

783
00:28:06,850 --> 00:28:10,160
אז אני פשוט הולך להתחיל עם גרייס,
ואני רואה שהיא מספר ארבע.

784
00:28:10,160 --> 00:28:11,720
איפה שייך מספר ארבע?

785
00:28:11,720 --> 00:28:14,940
אני לא התחלתי מיון שום דבר,
כך מקבלת גרייס להישאר שם.

786
00:28:14,940 --> 00:28:18,355
ועכשיו אני הולך לתבוע, אם אתה יכול
לקחת צעד לימינך, זה

787
00:28:18,355 --> 00:28:21,650
הרשימה הממוינת שלי, זה שלי
רשימה שנותרה לא ממוינת.

788
00:28:21,650 --> 00:28:23,260
אז עכשיו אני הולך להמשיך הבא,
ואיך קוראים לך שוב?

789
00:28:23,260 --> 00:28:23,700
>> ברנסון: רנסון.

790
00:28:23,700 --> 00:28:24,150
>> דוד י Malan: רנסון.

791
00:28:24,150 --> 00:28:25,375
אז ברנסון הוא מספר שתיים.

792
00:28:25,375 --> 00:28:27,490
אז אני הולך לקחת אותך
יצא לרגע.

793
00:28:27,490 --> 00:28:30,940
ועכשיו, לאן אתה שייך
במערך זה?

794
00:28:30,940 --> 00:28:32,360
אז בצד הימין של גרייס.

795
00:28:32,360 --> 00:28:35,670
אז שוב, אנחנו סוג של עושה
גרייס לעשות הרבה עבודה כאן.

796
00:28:35,670 --> 00:28:37,290
איפה שמים אותך?

797
00:28:37,290 --> 00:28:40,120
אז אנחנו הולכים להחליק לך
עזב, ולהכניס לשם ברנסון.

798
00:28:40,120 --> 00:28:41,680
אבל עכשיו אני טוען כי
אתם עשו.

799
00:28:41,680 --> 00:28:43,240
אבל שים לב, אני לא משתמש בשטח נוסף.

800
00:28:43,240 --> 00:28:45,130
זה עדיין 2 אלמנטים
כאן, 5 לכאן.

801
00:28:45,130 --> 00:28:47,910
גודל מערך כולל הוא 7, ולכן אני
לא בוגד, בסדר?

802
00:28:47,910 --> 00:28:51,950
>> אז עכשיו יש לנו, עם גייב כאן,
מספר שש, שבו אתה שייך?

803
00:28:51,950 --> 00:28:52,650
יש לך מזל שוב.

804
00:28:52,650 --> 00:28:53,820
אז אתה מקבל זכות להישאר שם.

805
00:28:53,820 --> 00:28:57,210
פשוט לקחת צעד קל לצד ימין
רק כדי להבהיר שאתה מסודרים.

806
00:28:57,210 --> 00:29:00,520
ועכשיו יש לנו ניל שוב, מספר
אחד, לאן אתה הולך?

807
00:29:00,520 --> 00:29:03,540
ועכשיו שבו אנחנו מתחילים לראות ש
אלגוריתם זה, אם כי בראשון

808
00:29:03,540 --> 00:29:05,950
מבט חטוף, מרגיש די חכם, לצפות
מה שעומד לקרות.

809
00:29:05,950 --> 00:29:07,370
אם אתה יכול לצעוד קדימה.

810
00:29:07,370 --> 00:29:09,260
>> איפה אנחנו רוצים לשים את ניל?

811
00:29:09,260 --> 00:29:11,830
אז ברור כאן, אז איך
אנחנו מקבלים ניל שם?

812
00:29:11,830 --> 00:29:12,970
בואו לעשות צעד אחר צעד זה.

813
00:29:12,970 --> 00:29:15,620
גייב, שבו אתה צריך ללכת?

814
00:29:15,620 --> 00:29:19,590
כן, כל כך לקחת את זה צעד אחד גדול,
או שני חצאי צעדים כדי להפוך את

815
00:29:19,590 --> 00:29:20,820
צעד אחד לשם.

816
00:29:20,820 --> 00:29:21,750
גרייס, לאן אתה הולך?

817
00:29:21,750 --> 00:29:22,510
טוב.

818
00:29:22,510 --> 00:29:23,500
אז עוד צעד.

819
00:29:23,500 --> 00:29:24,960
ולבסוף, ברנסון?

820
00:29:24,960 --> 00:29:25,460
צעד נוסף.

821
00:29:25,460 --> 00:29:27,190
ועכשיו אנחנו יכולים לשים את ניל למקומו.

822
00:29:27,190 --> 00:29:28,440
>> אז עכשיו, תמשיך את ההיגיון הזה.

823
00:29:28,440 --> 00:29:32,420
למרות שאנחנו לא עוברים ניל
שוב, ושוב, ושוב, בלשונו

824
00:29:32,420 --> 00:29:36,420
לאן הוא הולך, במקרה הגרוע ביותר,
המספר הבא אנו עלולים להיתקל יכולים

825
00:29:36,420 --> 00:29:42,220
להיות המספר, למשל, היה מספר
אפס, ואז אנחנו הולכים להעביר את כל

826
00:29:42,220 --> 00:29:42,730
החבר 'ה האלה.

827
00:29:42,730 --> 00:29:44,950
נניח שיש מספר, שלילי
אחד, ואז אנחנו צריכים לעבור

828
00:29:44,950 --> 00:29:46,080
כל החבר 'ה האלה.

829
00:29:46,080 --> 00:29:48,500
אז אנחנו באמת רק סוג של רפרף
הבעיה בסביבה, כך שאנחנו

830
00:29:48,500 --> 00:29:52,620
העברת חשבון מ
תהליך בחירה ולכן ההכנסה

831
00:29:52,620 --> 00:29:56,930
תהליך, כך שאתם פשוט לא הייתם לי
להזיז משהו בערך n מינוס

832
00:29:56,930 --> 00:29:57,940
מספר הצעדים.

833
00:29:57,940 --> 00:30:01,200
וכי מספר צעדים הוא רק הולך
כדי להגדיל ככל שבוחר מספרים נוספים,

834
00:30:01,200 --> 00:30:04,730
אם אני צריך לשמור דוחף אתכם
בחזרה, ובגב, וגב.

835
00:30:04,730 --> 00:30:08,320
>> אז מה שעצוב כרגע הוא כל אלה
אלגוריתמים הם N בריבוע.

836
00:30:08,320 --> 00:30:10,570
בואו נלך קדימה ותודה לאלה
חבר 'ה, ולדמיין את אלה קצת

837
00:30:10,570 --> 00:30:11,090
באופן שונה.

838
00:30:11,090 --> 00:30:12,312
עשה טוב מאוד.

839
00:30:12,312 --> 00:30:14,120
>> [מחיאות כפות]

840
00:30:14,120 --> 00:30:15,030
>> בסדר.

841
00:30:15,030 --> 00:30:16,280
הנה לך.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
תודה על -

844
00:30:18,470 --> 00:30:19,190
>> ברנסון: [לא ברור] לשמור את המספרים.

845
00:30:19,190 --> 00:30:21,990
>> דוד י Malan: לא, אתה עלול
לשמור את המספרים גם כן.

846
00:30:21,990 --> 00:30:23,440
בסדר.

847
00:30:23,440 --> 00:30:24,100
יפה עשה.

848
00:30:24,100 --> 00:30:25,300
בסדר.

849
00:30:25,300 --> 00:30:30,510
אז בואו נראה אם ​​אנחנו לא יכולים עכשיו לסכם
במהירות רבה יותר, ויותר מבחינה ויזואלית,

850
00:30:30,510 --> 00:30:33,410
בדיוק מה בדיוק קרה
כאן כדלקמן.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
אני הולך קדימה
ולמשוך את פיירפוקס.

853
00:30:38,770 --> 00:30:41,310
אנו נקשר הפגנה זו
באתר האינטרנט של הקורס.

854
00:30:41,310 --> 00:30:43,870
ג'אווה היא קצת מעצבן לקבל עבודה
בחלק מהדפדפנים בימים אלה.

855
00:30:43,870 --> 00:30:46,760
אז אם אתה משחק עם זה בבית,
מבין שאולי אתה צריך להשתמש ב-Firefox

856
00:30:46,760 --> 00:30:47,990
כדי לקבל את זה עובד.

857
00:30:47,990 --> 00:30:50,440
ומה אני הולך לעשות עם זה
ההפגנה היא הבאה.

858
00:30:50,440 --> 00:30:54,875
>> בתחתית, יש לי חבורה שלמה של
אפשרויות תפריט, כולל התחלה ו

859
00:30:54,875 --> 00:30:55,840
לעצור את הכפתור.

860
00:30:55,840 --> 00:30:59,450
גם במאמר מוסגר, יש, נראה שיש
באג בתוכניות אלה, שבו אתה

861
00:30:59,450 --> 00:31:03,720
לא יכול ממש לראות להפעיל או להפסיק
כפתור אלא אם כן אתה מחזיק פיקוד או Alt

862
00:31:03,720 --> 00:31:06,560
בתוספת וגדלה, אשר בסקרנות
מראה לך לחצנים נוספים.

863
00:31:06,560 --> 00:31:09,090
אז רק לידיעתך, אם אתה משחק
עם זה בבית.

864
00:31:09,090 --> 00:31:12,870
עכשיו אני הולך ללחוץ על התחל בפשוט
רגע, אחרי עיכוב של ציון,

865
00:31:12,870 --> 00:31:16,810
כמו, 200 אלפיות שנייה כאן, רק
כדי שנוכל לראות מה קורה.

866
00:31:16,810 --> 00:31:20,180
>> אז אני טוען שמדובר בהדמיה
של האלגוריתם הראשון

867
00:31:20,180 --> 00:31:23,730
החבר 'ה האלה עשה, מיון בועות, לפיה
אנחנו החלפנו אנשים חכמים-זוג.

868
00:31:23,730 --> 00:31:27,490
תובנה המפתח להדמיה זו
הוא שהגובה של הסורגים

869
00:31:27,490 --> 00:31:30,510
מייצג את גודלו של המספר.

870
00:31:30,510 --> 00:31:32,210
אז הגבוה יותר על הבר,
גדול יותר במספר.

871
00:31:32,210 --> 00:31:33,680
הקצר על הבר, קטן יותר במספר.

872
00:31:33,680 --> 00:31:38,630
ואם תשימו לב, אנחנו עוברים
איטרציה הראשונה של אלגוריתם זה,

873
00:31:38,630 --> 00:31:42,620
החלפת מספרים גדולים וקטנים, כך ש
המספר הקטן מגיע ראשון ו

874
00:31:42,620 --> 00:31:44,280
המספר הגדול הולך לצד ימין.

875
00:31:44,280 --> 00:31:48,770
>> וברגע שאנחנו מקבלים את סוף המערך
רבים של יותר משבעה מספרים, אנחנו

876
00:31:48,770 --> 00:31:49,900
הולך לחזור להתחלה.

877
00:31:49,900 --> 00:31:51,140
ולצפות את זה.

878
00:31:51,140 --> 00:31:54,860
בשמאל הקיצוני, שהבחור קטן הולך
כדי להחליף בצד, ואת זה

879
00:31:54,860 --> 00:31:56,010
חוזר על תהליך.

880
00:31:56,010 --> 00:31:59,450
עכשיו הדמיה זו מקבלת במהירות
משעמם, אז תן לי ללכת קדימה ולהפסיק

881
00:31:59,450 --> 00:32:04,170
אותו, לשנות את עיכוב משהו הרבה
מהר יותר רק כדי לקבל עכשיו, תחושה של

882
00:32:04,170 --> 00:32:05,060
אלגוריתם זה.

883
00:32:05,060 --> 00:32:07,840
>> אז למרות שאני האיץ אותו, זו היא
כמו שדרוג המעבד שלי, קנייה

884
00:32:07,840 --> 00:32:08,580
מחשב חדש.

885
00:32:08,580 --> 00:32:12,980
אני לא השתנה ביסודי
אלגוריתם, אבל אתה אכן יכול לראות יותר

886
00:32:12,980 --> 00:32:16,800
באופן ברור יותר מאשר עם בני אדם, שגדול
מספרים מבעבעים עד לקצה,

887
00:32:16,800 --> 00:32:20,900
והמספרים הקטנים מבעבעים
עד לתחתית.

888
00:32:20,900 --> 00:32:22,390
ועכשיו הדבר הזה כאן מסודרים.

889
00:32:22,390 --> 00:32:25,260
וכמאמר מוסגר, בכיכרות, יש
רק כמה חשבונות יש לי

890
00:32:25,260 --> 00:32:28,010
לעזור לך לספור כמה השוואות,
או כמה החלפות יש לי

891
00:32:28,010 --> 00:32:28,950
נעשה בפועל.

892
00:32:28,950 --> 00:32:30,750
>> ובכן, בואו ננסה אחד
האחרים שראינו.

893
00:32:30,750 --> 00:32:37,116
תן לי ללחוץ על מיון בועות כאן, ו
תן לי לבחור, וכל דף אינטרנט זה

894
00:32:37,116 --> 00:32:38,936
היא עגלה קטנה.

895
00:32:38,936 --> 00:32:41,155
בואו לקבל את הסיכון
ולהפעיל אותו שוב.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
שם אנחנו הולכים.

898
00:32:45,030 --> 00:32:47,180
אז בואו נעשה מיון בחירה.

899
00:32:47,180 --> 00:32:49,140
אני לא יודע למה התפריט
מופיע שם.

900
00:32:49,140 --> 00:32:54,070
בואו קרב כדי לתקן את זה
באג, לשנות את זה ל -50.

901
00:32:54,070 --> 00:32:56,020
אה, בואו בעצם עושה
זה הרבה יותר מהר.

902
00:32:56,020 --> 00:32:59,160
חמש אלפיות שנייה בערך, ולהתחיל.

903
00:32:59,160 --> 00:33:00,470
>> אז זהו מיון בחירה.

904
00:33:00,470 --> 00:33:03,070
אז שוב, על מה שאנחנו חושבים
עשה עם בני האדם כאן.

905
00:33:03,070 --> 00:33:08,490
עברנו את המערך ונבחרתי
האלמנט הקטן ביותר שוב,

906
00:33:08,490 --> 00:33:09,250
ושוב, ושוב.

907
00:33:09,250 --> 00:33:11,110
עכשיו אני טוען שעדיין היה די רע.

908
00:33:11,110 --> 00:33:15,010
זה עדיין היה n בריבוע, פחות או יותר,
אבל זה היה, בעולם האמיתי, קצת

909
00:33:15,010 --> 00:33:18,280
מהר יותר, כי אני אכן לוקח
מעט פחות צעדים בכל פעם.

910
00:33:18,280 --> 00:33:19,800
אבל אנחנו מדברים רק מה?

911
00:33:19,800 --> 00:33:21,830
אולי 40 או משהו כזה ברים כאן?

912
00:33:21,830 --> 00:33:23,200
אנחנו לא מדברים על 40 מיליון דולרים.

913
00:33:23,200 --> 00:33:27,430
אז זה לא לגמרי ברור לי כי
אכן הייתה עלייה משמעותית.

914
00:33:27,430 --> 00:33:32,530
>> עכשיו תן לי לחזור ולשנות לשלנו
אלגוריתם שלישי, שבחר

915
00:33:32,530 --> 00:33:33,180
סוג הכניסה.

916
00:33:33,180 --> 00:33:36,380
ועכשיו זה באמת עגלה, כי
תפריט באמת לא צריך להיות שם למטה.

917
00:33:36,380 --> 00:33:40,840
אז עכשיו אנחנו לגלול חזרה לכאן
ולהתחיל אלגוריתם זה.

918
00:33:40,840 --> 00:33:43,270
ופ, להתחיל ולהפסיק.

919
00:33:43,270 --> 00:33:47,160
אז יש אחד מסוג זה דפוס די
אליו, לפיה אנו נמצאים שוב

920
00:33:47,160 --> 00:33:50,240
החדרת בני האדם, או ב
מקרה זה, את הסורגים לתוך

921
00:33:50,240 --> 00:33:52,620
המיקום המתאים שלהם.

922
00:33:52,620 --> 00:33:55,430
וזה כבר נעשה בעבר
הסתובבתי.

923
00:33:55,430 --> 00:33:58,940
אבל גם זה, בתאוריה,
עדיין n בריבוע.

924
00:33:58,940 --> 00:34:01,430
>> אז בואו נראה אם ​​אנחנו לא יכולים לסכם
אלה כדלקמן.

925
00:34:01,430 --> 00:34:04,750
אני הולך קדימה, רק כדי לתת לי
מיין אותנו על דרך משותפת של מדבר

926
00:34:04,750 --> 00:34:08,489
על הדברים האלה, הרשו לי להציג
רק קצת סימון כאן.

927
00:34:08,489 --> 00:34:12,480
אתה עומד לראות משהו שנקרא גדול
O, כי זה ממש גדול

928
00:34:12,480 --> 00:34:16,320
א 'וזו דרך שמחשב
מדען או מתמטיקאי אפילו משתמש

929
00:34:16,320 --> 00:34:19,230
כדי לתאר את זמן הריצה
חלק מהאלגוריתם.

930
00:34:19,230 --> 00:34:21,400
כמה מדרגות זה באמת לוקח?

931
00:34:21,400 --> 00:34:25,080
>> עכשיו אני הולך להביך את עצמי עם
כתב היד שלי כאן ברגע.

932
00:34:25,080 --> 00:34:29,020
אבל תן לי להמשיך ולומר כי
זה יהיה גדול O כאן.

933
00:34:29,020 --> 00:34:33,610
והרשו לי להציג אחד אחר
סמל, אומגה הון.

934
00:34:33,610 --> 00:34:37,080
אומגה הולכת להיות הפוך,
למעשה, הגדולה של א 'ואילו הגדול O

935
00:34:37,080 --> 00:34:40,790
פירושו, במקרה הגרוע ביותר, כמה זמן
אולי איזה אלגוריתם לקחת, ב

936
00:34:40,790 --> 00:34:43,480
מונחים של n, אומגה הולכת
להיות כמה זמן אולי זה

937
00:34:43,480 --> 00:34:45,409
לקחת במקרה הטוב.

938
00:34:45,409 --> 00:34:48,090
ואנו רואים מה שאנחנו מתכוונים
במקרה טוב רק לרגע.

939
00:34:48,090 --> 00:34:49,940
>> אז בואו נתחיל משהו פשוט.

940
00:34:49,940 --> 00:34:54,719
הרשו לי להתחיל בחיפוש ליניארי.

941
00:34:54,719 --> 00:34:55,679
אז לא מיון.

942
00:34:55,679 --> 00:34:58,000
אנחנו קוראים לזה חיפוש ליניארי.

943
00:34:58,000 --> 00:35:01,140
ועכשיו, לעשות קצת
שולחן מחוץ לזה.

944
00:35:01,140 --> 00:35:06,600
ועכשיו, במקרה של חיפוש ליניארי,
במקרה הגרוע ביותר, כמה צעדים הוא

945
00:35:06,600 --> 00:35:11,770
זה הולך לקחת לי למצוא
מספר הבחירה שרירותית?

946
00:35:11,770 --> 00:35:14,540
ויש דלתות כלל n
או n מספרים בסך הכל.

947
00:35:14,540 --> 00:35:15,940
במקרה הגרוע ביותר.

948
00:35:15,940 --> 00:35:18,800
כמה צעדים אני הולך צריך
לקחת כדי למצוא את המספר 50 במערך

949
00:35:18,800 --> 00:35:20,830
דלתות של n?

950
00:35:20,830 --> 00:35:21,410
ולמה?

951
00:35:21,410 --> 00:35:23,680
כי זה יכול להיות כל
דרך על על הסוף.

952
00:35:23,680 --> 00:35:27,120
כל כך הרבה כמו ג'ניפר נתקל,
מספר 50 היה כל הדרך, כך ב

953
00:35:27,120 --> 00:35:30,760
החיפוש ליניארי המקרה הגרוע ביותר
הוא גדול O של n, אנחנו אומרים.

954
00:35:30,760 --> 00:35:33,430
>> מה בנוגע למקרה הטוב ביותר,
אם אתה מקבל מזל באמת?

955
00:35:33,430 --> 00:35:36,200
זה פשוט הולך לקחת את זה צעד אחד,
או מספר קבוע של צעדים.

956
00:35:36,200 --> 00:35:37,830
אז אנחנו מתארים את זה כ1.

957
00:35:37,830 --> 00:35:39,010
אז זה די טוב.

958
00:35:39,010 --> 00:35:41,210
עכשיו מה אם עשו משהו
כמו חיפוש בינארי?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
אז חיפוש בינארי, בגרוע ביותר
מקרה, לקח כמה זמן?

961
00:35:47,846 --> 00:35:49,250
>> [חציצת קולות]

962
00:35:49,250 --> 00:35:51,310
>> דוד י Malan: אז בעצם, אני
שמע את זה בכמה מקומות.

963
00:35:51,310 --> 00:35:56,390
אז זה בעצם log n, פחות או יותר,
כי כמו שאנו מחלקים את הרשימה במחצית

964
00:35:56,390 --> 00:36:00,730
שוב, ושוב, ושוב, אנחנו יכולים
למצוא, סופו של דבר, הערך,

965
00:36:00,730 --> 00:36:04,750
אם זה שם, אבל יש מלכוד.

966
00:36:04,750 --> 00:36:08,590
מה ההנחה שיש לנו כדי
לוקח כמובן מאליו לחיפוש בינארי?

967
00:36:08,590 --> 00:36:09,700
יש לו להיות מסודר.

968
00:36:09,700 --> 00:36:12,770
זה לא מסודרים, אתה יכול לפצל את הדבר
במחצית שוב ושוב, ואתה

969
00:36:12,770 --> 00:36:15,490
יכול ללכת שמאלה, ואתה יכול ללכת ימינה, ו
אתה יכול ללכת שמאלה וימינה, אבל אתה

970
00:36:15,490 --> 00:36:18,070
לא הולך למצוא את האלמנט אם
הרשימה אינה ממוינת, כי

971
00:36:18,070 --> 00:36:18,790
אתה עלול לפספס את זה.

972
00:36:18,790 --> 00:36:22,120
בגלל היוריסטי שלך, להולך שמאל
או ימינה הולך להיות פגום אם זה

973
00:36:22,120 --> 00:36:23,420
אכן אינו ממוין.

974
00:36:23,420 --> 00:36:26,110
אז יש סוג של עלות נסתרת
לשימוש במשהו כזה.

975
00:36:26,110 --> 00:36:29,250
>> עכשיו, בואו נלך למיון שלנו
אלגוריתמים לא מחפשים -

976
00:36:29,250 --> 00:36:31,140
אה, בעצם בואו נלך בשדה זה ריק.

977
00:36:31,140 --> 00:36:33,190
חיפוש בינארי במקרה הטוב?

978
00:36:33,190 --> 00:36:36,290
זה גם 1 אם זה קורה רק כדי להיות
באמצע מאוד של המערך, או

979
00:36:36,290 --> 00:36:37,810
אמצע ספר טלפונים.

980
00:36:37,810 --> 00:36:39,710
עכשיו בואו לעשות מיון בועות.

981
00:36:39,710 --> 00:36:42,570
אז שוב, עכשיו אנחנו נכנסים
מיני, לא את החיפושים.

982
00:36:42,570 --> 00:36:47,220
>> במקרה הגרוע ביותר, כמה צעדים עשו לנו
מיון בועות טענה הולך לקחת?

983
00:36:47,220 --> 00:36:48,410
n בריבוע.

984
00:36:48,410 --> 00:36:49,200
אז אני הולך לצייר את זה.

985
00:36:49,200 --> 00:36:51,710
אוו, כתב היד שלי נראית עוד יותר גרועה
כאשר זה צפוי כי גדול.

986
00:36:51,710 --> 00:36:52,510
בסדר.

987
00:36:52,510 --> 00:36:53,570
אז זה של נ 'בריבוע.

988
00:36:53,570 --> 00:36:59,460
ובמקרה הטוב ביותר של מיון בועות,
כמה צעדים שזה הולך לקחת?

989
00:36:59,460 --> 00:37:00,980
1, שמעתי.

990
00:37:00,980 --> 00:37:01,760
>> רמקול 1: n.

991
00:37:01,760 --> 00:37:03,286
>> דוד י Malan: n, שמעתי.

992
00:37:03,286 --> 00:37:04,200
>> רמקול 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> דוד י Malan: 2, שמעתי.

994
00:37:05,010 --> 00:37:06,670
האם אני שומע 3?

995
00:37:06,670 --> 00:37:07,080
בסדר.

996
00:37:07,080 --> 00:37:11,390
אז שמעתי 1, n, 2, אבל בואו לבחור
חוץ לפחות הראשון של אלה

997
00:37:11,390 --> 00:37:12,330
הצעות, 1.

998
00:37:12,330 --> 00:37:15,370
זה לא אינסטינקט רע, משום שהיא
סוג של כדלקמן דפוס כאן.

999
00:37:15,370 --> 00:37:19,670
אבל אם זה לוקח צעד 1, איך בבלבד
עולם שאני יכול לטעון שהרשימה

1000
00:37:19,670 --> 00:37:22,900
הוא מיון, כי אם מותר לי רק
לקחת את זה צעד 1, כמה אלמנטים

1001
00:37:22,900 --> 00:37:25,230
אני באמת יכול לבדוק כדי להיות בטוח?

1002
00:37:25,230 --> 00:37:28,270
ובכן, רק 1 ש, אומר שיש n
מינוס 1 אלמנטים שיכולים להיות מחוץ

1003
00:37:28,270 --> 00:37:31,310
צו, ואני רק הולך באמונה לאחר
מסתכל על אלמנט ש1

1004
00:37:31,310 --> 00:37:31,850
דבר הוא מיון.

1005
00:37:31,850 --> 00:37:33,930
אז 1 לא נכון כאן.

1006
00:37:33,930 --> 00:37:35,710
אז מינימאלי, כמה
אני צריך להסתכל?

1007
00:37:35,710 --> 00:37:36,680
>> [חציצת קולות]

1008
00:37:36,680 --> 00:37:40,160
>> דוד י Malan: N מינוס 1, או באמת,
n, כי אני צריך להסתכל על כל

1009
00:37:40,160 --> 00:37:42,190
אלמנט לוודא כי
זה לא מקולקל.

1010
00:37:42,190 --> 00:37:44,750
אבל שוב, אנחנו נטפל בגל שלנו
ידי במספרים הקטנים יותר ו

1011
00:37:44,750 --> 00:37:47,100
להניח כי, כפי שמקבל n גדול, הם
לא מעניין בכל מקרה.

1012
00:37:47,100 --> 00:37:48,380
אז זה מיון בועות.

1013
00:37:48,380 --> 00:37:49,830
ועכשיו, בואו נעשינו את שני אלה שעבר.

1014
00:37:49,830 --> 00:37:53,520
מיון בחירה, ואז אנחנו
לעשות סוג כניסה.

1015
00:37:53,520 --> 00:37:57,160
ואז תוכל לפוצצך
מוחות עם משהו הרבה

1016
00:37:57,160 --> 00:37:58,926
יותר טוב מכל אלה.

1017
00:37:58,926 --> 00:38:00,410
בסדר.

1018
00:38:00,410 --> 00:38:04,700
>> מהו המקרה הגרוע ביותר פועל
זמן של מיון בחירה?

1019
00:38:04,700 --> 00:38:05,680
>> רמקול 4: n בריבוע.

1020
00:38:05,680 --> 00:38:06,710
>> דוד י Malan: N כיכר, אני שומע.

1021
00:38:06,710 --> 00:38:09,790
אבל למה n בריבוע, באופן אינטואיטיבי?

1022
00:38:09,790 --> 00:38:11,170
>> רמקול 4: כי אנחנו פשוט עשינו את זה.

1023
00:38:11,170 --> 00:38:12,260
>> דוד י Malan: כי אנחנו פשוט עשינו את זה.

1024
00:38:12,260 --> 00:38:12,550
אישור.

1025
00:38:12,550 --> 00:38:13,380
תשובה טובה.

1026
00:38:13,380 --> 00:38:16,660
אבל באופן אינטואיטיבי, מדוע היא בחירה
סוג n בריבוע?

1027
00:38:16,660 --> 00:38:18,980
מה שאנחנו צריכים לעשות
שוב ושוב?

1028
00:38:18,980 --> 00:38:22,570
היו לנו כדי לשמור על הסריקה דרך, הם
אתה קטן, אתה

1029
00:38:22,570 --> 00:38:24,020
הקטן ביותר, הוא שאתה קטן.

1030
00:38:24,020 --> 00:38:27,480
ומובן מאליו, היינו יכול לקחת את n
צעדים, ואז n 1 מינוס, אז n מינוס 2.

1031
00:38:27,480 --> 00:38:30,700
אבל אם אתה סוג של להוסיף את כל אלה,
או לקחת אותו באמונה שאני הוספתי

1032
00:38:30,700 --> 00:38:34,810
אותם מראש, אנחנו מקבלים בערך n
בריבוע מינוס כמה מספרים קטנים יותר.

1033
00:38:34,810 --> 00:38:36,730
אז אני הולך לקרוא לזה n בריבוע.

1034
00:38:36,730 --> 00:38:39,530
אבל עם מיון בחירה בטוב ביותר
מקרה, כמה צעדים הוא זה

1035
00:38:39,530 --> 00:38:40,632
הולך לקחת לי?

1036
00:38:40,632 --> 00:38:41,840
>> רמקול 5: [לא ברור]

1037
00:38:41,840 --> 00:38:44,350
>> דוד י Malan: זה למרבה הצער
עדיין n בריבוע, נכון?

1038
00:38:44,350 --> 00:38:49,590
כי אם אני בחירה הקטנה ביותר
אלמנט, והיו לנו שבעה אנשים כאן,

1039
00:38:49,590 --> 00:38:53,280
אני רק יודע, ברגע שאני מגיע למאוד
הסוף, שאני כבר נמצא הקטן ביותר

1040
00:38:53,280 --> 00:38:55,670
מספר, בכל מקום שהוא או
ייתכן שהיא היית.

1041
00:38:55,670 --> 00:38:58,820
אבל איך אני מוצא הבא
המספר הקטן ביותר?

1042
00:38:58,820 --> 00:39:00,160
אני חייב לעשות את מעבר אחר.

1043
00:39:00,160 --> 00:39:04,810
אז במקרה הטוב ביותר, מה הוא
קלט למיון בחירה?

1044
00:39:04,810 --> 00:39:07,830
זה כבר רשימת מיון, מספר אחד,
מספר שתיים, מספר שלוש, מספר ארבע.

1045
00:39:07,830 --> 00:39:08,600
אבל אני מחשב.

1046
00:39:08,600 --> 00:39:10,190
אני יכול רק להסתכל על אחד
דבר בכל פעם.

1047
00:39:10,190 --> 00:39:12,465
אני לא יכול כאילו לקחת צעד
חזרה כמו בן אדם ואומר,

1048
00:39:12,465 --> 00:39:14,030
אוו, זה נראה נכון.

1049
00:39:14,030 --> 00:39:17,580
>> אני יכול רק לדון בתקינות
מיון בחירה על ידי בחירה

1050
00:39:17,580 --> 00:39:18,370
המספר הקטן ביותר.

1051
00:39:18,370 --> 00:39:21,390
אבל גם אם אני מוצא את המספר ראשון,
אם אני לא יודע שום דבר אחר על

1052
00:39:21,390 --> 00:39:24,460
את המספרים האחרים, שאני לא, כל מה שאני
יודע שכבר נתן לי מערך

1053
00:39:24,460 --> 00:39:27,930
או קבוצה של דלתות שמאחוריו הן
מספרים, הדרך היחידה שאני יודע שאחד

1054
00:39:27,930 --> 00:39:28,680
היה הקטן ביותר?

1055
00:39:28,680 --> 00:39:32,440
אם אני מקבל את כל הדרך לכאן ולהבין,
לעזאזל, אחד אכן היה הקטן ביותר.

1056
00:39:32,440 --> 00:39:34,870
>> אבל איך אני מכן לקבוע כי
שתיים הוא הקטנים ביותר הבאה?

1057
00:39:34,870 --> 00:39:38,350
על ידי עושה את אותו חוסר היעילות
שוב ושוב.

1058
00:39:38,350 --> 00:39:42,210
אז סוף סוף, עם סוג ההכנסה,
כיצד, במקרה הגרוע ביותר,

1059
00:39:42,210 --> 00:39:44,990
לא שאנחנו אומרים שהוא מבצע?

1060
00:39:44,990 --> 00:39:49,100
גם את זה הוא n בריבוע.

1061
00:39:49,100 --> 00:39:53,020
ומה לגבי במקרה הטוב?

1062
00:39:53,020 --> 00:39:56,282
נשאיר את זה כמו סחרור מסוכן.

1063
00:39:56,282 --> 00:40:00,090
אנחנו ממלאים שבפעם הבאה ריקה,
אבל קודם תן לי מציע לנו

1064
00:40:00,090 --> 00:40:02,620
היסוד לעשות טוב יותר מאשר
כל אלה, בסדר?

1065
00:40:02,620 --> 00:40:05,220
>> אז תחשוב בעצמך מה הכנסה
סוג זה הולך להיות.

1066
00:40:05,220 --> 00:40:06,910
ובכן, זה לא היה דרמטי מאוד,
בגלל שאני רק אחד

1067
00:40:06,910 --> 00:40:08,970
כי ראה את השינוי.

1068
00:40:08,970 --> 00:40:09,620
וואו.

1069
00:40:09,620 --> 00:40:10,420
אישור.

1070
00:40:10,420 --> 00:40:12,615
אז הנה יש לנו מעט
הפגנה שונה.

1071
00:40:12,615 --> 00:40:16,580
אם אני להתקרב לכאן, תראה שעל
מהשמאל יש לנו סוג של בועה, ב

1072
00:40:16,580 --> 00:40:20,740
באמצע יש לנו מיון בחירה, ועל
ימין קיצוני, שיש לנו משהו שאנחנו

1073
00:40:20,740 --> 00:40:23,380
לא הסתכל עדיין
קרא למזג מיון.

1074
00:40:23,380 --> 00:40:26,080
אבל לחשוב על מה שהיינו
עושה כאן עד כה היום.

1075
00:40:26,080 --> 00:40:29,200
כאשר ג'ניפר הראשון עלה על במה,
אנחנו עברנו המערך של מספרים

1076
00:40:29,200 --> 00:40:33,750
שוב, ושוב, עם חיפוש ליניארי,
ויש לנו זמן ריצה לינארי, הגדול O

1077
00:40:33,750 --> 00:40:35,100
של n, אם אפשר לומר כך.

1078
00:40:35,100 --> 00:40:41,000
>> כאשר אנו רואים כעת בשבוע הראשון של
בכיתה, כאשר היינו לנו פרד ומשול,

1079
00:40:41,000 --> 00:40:43,740
והיינו לנו לקרוע את ספר טלפונים,
וג'ניפר, ואנחנו ביחד

1080
00:40:43,740 --> 00:40:47,500
למנף את תובנה מרכזית ש, שהייתה אמורה
לחזור על עצמך שוב ושוב על ידי

1081
00:40:47,500 --> 00:40:50,930
איכשהו לזרוק, לזרוק,
לזרוק, חצי מהבעיה, או

1082
00:40:50,930 --> 00:40:55,320
בדרך כלל, חלוקת בעיה לשתיים,
ולאחר מכן טיפול בחתיכה קטנה של

1083
00:40:55,320 --> 00:40:59,630
הבעיה מושגית כשווה ערך
לצד השני, אנחנו איכשהו עשינו

1084
00:40:59,630 --> 00:41:00,910
ביסודו טוב יותר.

1085
00:41:00,910 --> 00:41:04,720
אבל עם סוג של בועה, עם בחירה
סוג שהוא, עם סוג ההכנסה, יש לנו אולי

1086
00:41:04,720 --> 00:41:06,560
אין תובנות כאלה שג'ניפר עשה.

1087
00:41:06,560 --> 00:41:10,220
אנחנו פחות או יותר פשוט הלכנו אחורה ו
שוב חבורה שלמה של פעמים, ואנחנו

1088
00:41:10,220 --> 00:41:12,650
דברים צבטו קצת, החלפה
בצו זה, אולי

1089
00:41:12,650 --> 00:41:13,730
הוספה או בחירה.

1090
00:41:13,730 --> 00:41:16,950
אבל בסופו של היום, עשיתי הרבה
של הליכה מגושמת קדימה ואחורה.

1091
00:41:16,950 --> 00:41:21,160
אנחנו לא באמת למנף משהו
חכמה כמו ג'ניפר עשה כמו החלוקה

1092
00:41:21,160 --> 00:41:22,040
וכובש.

1093
00:41:22,040 --> 00:41:25,620
>> אז למזג מיון, לעומת זאת, שבו אנו
לא תראה עד השבוע הבא, זה הולך

1094
00:41:25,620 --> 00:41:29,540
כדי למנף את הרעיון מרכזי שעל ידי החלוקה
הקלט, ולאחר מכן חצייה, ולאחר מכן

1095
00:41:29,540 --> 00:41:30,580
חצייה, ולאחר מכן חצייה.

1096
00:41:30,580 --> 00:41:34,590
ועל כל איטרציה של לולאה ש,
מיון מחצית השמאל, והזכות

1097
00:41:34,590 --> 00:41:38,200
מחצית, ואז במחצית השמאלית של החצי שמאלי,
ואת החצי הימני של השמאל, ולאחר מכן

1098
00:41:38,200 --> 00:41:40,990
המחצית השמאלית של המחצית הימנית, ו
המחצית הימנית של החצי הימני.

1099
00:41:40,990 --> 00:41:42,840
וחוזר שוב ושוב.

1100
00:41:42,840 --> 00:41:46,170
>> אז אתה רואה את זה מבחינה ויזואלית, אבל זה
זה מה שמחכה לנו בשבוע הבא.

1101
00:41:46,170 --> 00:41:49,760
ובאופן כללי, כאשר אנו חושבים קצת
קצת יותר קשה על כל בעיה כזו.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
יש לנו n בריבוע בצד השמאל, n
ריבוע באמצע, וn

1104
00:41:57,970 --> 00:41:59,400
log n בצד ימין.

1105
00:41:59,400 --> 00:42:00,590
אז יש הסחרור המסוכן האמיתי שלך.

1106
00:42:00,590 --> 00:42:02,040
נתראה ביום שני.

1107
00:42:02,040 --> 00:42:05,163
>> [מחיאות כפות]