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

2
00:00:11,100 --> 00:00:12,300
>> 1 SPEAKER: היי לכולם!

3
00:00:12,300 --> 00:00:13,890
ברוכים השבים לסעיף.

4
00:00:13,890 --> 00:00:17,480
כל כך שמח לראות כל כך הרבה מכם גם כאן,
וכל מי שצופה באינטרנט.

5
00:00:17,480 --> 00:00:18,760

6
00:00:18,760 --> 00:00:20,920
אז, כמו גב בברכה רגיל.

7
00:00:20,920 --> 00:00:24,360
אני מקווה שכל מה שהיית יפה
בסוף השבוע, מלא של מנוחה, הרפיה.

8
00:00:24,360 --> 00:00:26,026
זה היה יפה אתמול.

9
00:00:26,026 --> 00:00:27,525
אז, אני מקווה שנהנה בחוץ.

10
00:00:27,525 --> 00:00:28,840

11
00:00:28,840 --> 00:00:30,610
>> אז קודם כל כמה הודעות.

12
00:00:30,610 --> 00:00:31,920

13
00:00:31,920 --> 00:00:32,700
לדירוג.

14
00:00:32,700 --> 00:00:37,350
אז, רוב אתה צריך קיבל
דוא"ל ממני על Pset Scratch שלך,

15
00:00:37,350 --> 00:00:39,920
כמו גם לדירוג ל1 Pset.

16
00:00:39,920 --> 00:00:41,000

17
00:00:41,000 --> 00:00:42,220
אז, רק כמה דברים.

18
00:00:42,220 --> 00:00:45,150
הקפד להשתמש check50 בstyle50.

19
00:00:45,150 --> 00:00:47,250
אלה אמורים להיות
משאבים בשבילכם,

20
00:00:47,250 --> 00:00:50,660
כדי לוודא שאתה מקבל
נקודות רבות ככל שאתה יכול

21
00:00:50,660 --> 00:00:52,390
ללא צורך לאבד אותם.

22
00:00:52,390 --> 00:00:54,407
אז, דברים כמו סגנון
חשובים מאוד.

23
00:00:54,407 --> 00:00:55,740
אנחנו הולכים לקחת את זה ל.

24
00:00:55,740 --> 00:00:58,115
חלק מכם אולי כבר
שם לב שמPset שלך.

25
00:00:58,115 --> 00:00:58,920

26
00:00:58,920 --> 00:01:01,450
וcheck50 הוא רק
באמת דרך קלה לוודא

27
00:01:01,450 --> 00:01:05,050
כי אנחנו בעצם חוזרים מה
צריך להיות מוחזרות למשתמש,

28
00:01:05,050 --> 00:01:06,690
וכל מה שהוא פועל כראוי.

29
00:01:06,690 --> 00:01:08,690

30
00:01:08,690 --> 00:01:12,040
>> על הפתק השני, לוודא שלך
העלאת דברים לתיקייה הנכונה.

31
00:01:12,040 --> 00:01:14,470
זה עושה את החיים שלי רק
קצת יותר קשה

32
00:01:14,470 --> 00:01:18,836
אם אתה מעלה Pset 2 לתוך 1 Pset
כי כשאני מוריד דברים,

33
00:01:18,836 --> 00:01:20,085
הם לא להוריד בצורה נכונה.

34
00:01:20,085 --> 00:01:21,690

35
00:01:21,690 --> 00:01:24,560
ואני יודע שזה קצת רופף
במערכת להתרגל ל,

36
00:01:24,560 --> 00:01:26,950
אבל רק להיות סופר
זהיר, אם רק בשבילי,

37
00:01:26,950 --> 00:01:30,080
כך שכאשר אתה מקבל מיילים
בכ02:00 ואני לדירוג.

38
00:01:30,080 --> 00:01:33,710
אם לא יגרום לי להיראות
בכל רחבי לPset שלך.

39
00:01:33,710 --> 00:01:34,440
מגניב.

40
00:01:34,440 --> 00:01:37,270
>> אני יודע שזה מוקדם, אבל אני
לגמרי יש המריא שומר

41
00:01:37,270 --> 00:01:40,800
על ידי חיבור זה עקב ביום שישי הקרוב, ש
המרצים שלי פשוט היו כמו, אה, כן.

42
00:01:40,800 --> 00:01:42,550
זכרו, יש לך
מאמר עקב ביום שישי.

43
00:01:42,550 --> 00:01:45,780
אז, אני יודע שאף אחד לא אוהב
לחשוב על מבחני אמצע סמסטר,

44
00:01:45,780 --> 00:01:50,620
אבל החידון הראשון שלך הוא ב -15 באוקטובר,
שאוקטובר הוא החל מהשבוע.

45
00:01:50,620 --> 00:01:53,290
אז, זה יכול להיות מוקדם
ממה שציפית הוא כל.

46
00:01:53,290 --> 00:01:57,510
כך שאתה לא נזרק משומר כש
אני מזכיר סעיף בשבוע הבא כי הו,

47
00:01:57,510 --> 00:02:00,560
בשבוע הבא החידון שלך, חשבתי ש
אני הייתי נותן לך קצת יותר

48
00:02:00,560 --> 00:02:01,500
של ראשים עד עכשיו.

49
00:02:01,500 --> 00:02:02,970

50
00:02:02,970 --> 00:02:04,660
>> אז, להגדיר את הבעיה שלך, מספר שלוש.

51
00:02:04,660 --> 00:02:07,070
איך אנשים שקראו
spec מתוך סקרנות?

52
00:02:07,070 --> 00:02:08,560

53
00:02:08,560 --> 00:02:09,199
אישור.

54
00:02:09,199 --> 00:02:10,229
יש לנו כמה.

55
00:02:10,229 --> 00:02:12,320
סוג של למטה מ אחרון
שבוע אבל זה בסדר.

56
00:02:12,320 --> 00:02:13,650
אני יודע שהוא היה יפה.

57
00:02:13,650 --> 00:02:15,120

58
00:02:15,120 --> 00:02:16,660
אז תפרוץ.

59
00:02:16,660 --> 00:02:21,010
בהחלט לאחר להספיק
היום לקרוא את האפיון שלך לפחות

60
00:02:21,010 --> 00:02:25,240
תנסה כמו הורדה
קוד הפצה וריצה

61
00:02:25,240 --> 00:02:27,430
כמו האות הראשונה
דבר שהם מבקשים ממך.

62
00:02:27,430 --> 00:02:28,681

63
00:02:28,681 --> 00:02:32,590
מכיוון שאנו משתמשים ב
קוד הפצה וספרייה

64
00:02:32,590 --> 00:02:36,790
שרק עכשיו using-- --It רק
בפעם השנייה שעשינו Pset זה,

65
00:02:36,790 --> 00:02:38,650
דברים מטורפים יכולים לקרות
עם המכשיר שלך,

66
00:02:38,650 --> 00:02:41,370
ואתה רוצה למצוא ש
עכשיו לעומת מאוחר יותר.

67
00:02:41,370 --> 00:02:45,570
>> כי אם זה יום חמישי בערב או שזה
יום רביעי בלילה, ומסיבה כלשהי

68
00:02:45,570 --> 00:02:48,912
המכשיר שלך עושה בדיוק את לא
רוצה לרוץ עם הספרייה

69
00:02:48,912 --> 00:02:50,620
או עם ההפצה
קוד, שאמצעי

70
00:02:50,620 --> 00:02:52,309
אתה אפילו לא יכול להתחיל לעשות את הקידוד.

71
00:02:52,309 --> 00:02:54,100
בגלל שאתה לא יכול לבדוק
כדי לראות אם זה עובד.

72
00:02:54,100 --> 00:02:55,975
לא הולך שלך תוכל
כדי לראות אם זה הידור.

73
00:02:55,975 --> 00:03:00,500
אתה רוצה לטפל באלה בשלב מוקדם ב
השבוע, כשאתה עדיין יכול לשלוח לי דוא"ל

74
00:03:00,500 --> 00:03:03,100
או אחד מTFS האחר,
ואנחנו יכולים לקבל אותם קבועים.

75
00:03:03,100 --> 00:03:05,410
כי אלה הם נושאים
כי הם הולכים לעצור אותך

76
00:03:05,410 --> 00:03:07,120
מלעשות כל התקדמות של ממש.

77
00:03:07,120 --> 00:03:10,055
זה לא כמו באג אחד, ש
אתה יכול פשוט סוג של לדלג על.

78
00:03:10,055 --> 00:03:10,712

79
00:03:10,712 --> 00:03:13,420
אם אתה נתקלת בבעיות עם שלך
מכשיר או קוד הפצה,

80
00:03:13,420 --> 00:03:16,211
אתה באמת רוצה לקבל את זה לקח
אכפת לי של במוקדם ולא במאוחר.

81
00:03:16,211 --> 00:03:20,410
אז גם אם אתה לא הולך ממש
להתחיל לקודד, להוריד את ההפצה

82
00:03:20,410 --> 00:03:24,040
קוד, לקרוא את המפרט, לוודא
כל מה שעובד שם.

83
00:03:24,040 --> 00:03:25,134
בסדר?

84
00:03:25,134 --> 00:03:27,675
אם אתה יכול פשוט לעשות את זה, אני
מבטיח חייכם יהיו קל יותר.

85
00:03:27,675 --> 00:03:28,800

86
00:03:28,800 --> 00:03:31,410
ואז אתה כנראה הולך
לעשות את זה עכשיו נכון?

87
00:03:31,410 --> 00:03:32,100
אישור.

88
00:03:32,100 --> 00:03:33,950
אז, כל שאלות שם?

89
00:03:33,950 --> 00:03:35,850
כל דברים לוגיסטיים?

90
00:03:35,850 --> 00:03:36,910
כולם טובים?

91
00:03:36,910 --> 00:03:38,270
אישור.

92
00:03:38,270 --> 00:03:41,700
>> כתב ויתור לאלה של
אתה בחדר והאינטרנט.

93
00:03:41,700 --> 00:03:45,437
אני הולך להיות מנסה לעבור
בין PowerPoint במכשיר

94
00:03:45,437 --> 00:03:47,270
כי אנחנו הולכים
להיות עושה קצת קידוד

95
00:03:47,270 --> 00:03:53,630
היום לפי דרישת קהל של אנונימי
סקר הצעה שנשלח שבוע שעבר.

96
00:03:53,630 --> 00:03:55,480
אז, יהיה לנו לעשות כמה קידוד.

97
00:03:55,480 --> 00:03:57,800
אז, אם אתם רוצים גם
לפטר את המכשירים שלכם,

98
00:03:57,800 --> 00:04:02,910
ואתה צריך יש לי דואר אלקטרוני
ממני, עם קובץ לדוגמה.

99
00:04:02,910 --> 00:04:04,310
אתם מוזמנים לעשות את זה.

100
00:04:04,310 --> 00:04:07,340
>> אז, אנחנו הולכים לדבר על
GDB, אשר הוא הבאגים.

101
00:04:07,340 --> 00:04:09,970
זה הולך לעזור לך
סוג של להבין איפה

102
00:04:09,970 --> 00:04:11,860
דברים הולכים בסדר בקוד שלך.

103
00:04:11,860 --> 00:04:15,370
זה באמת רק דרך בשבילך כדי להגביר
דרך הקוד שלך כפי שהוא קורה,

104
00:04:15,370 --> 00:04:19,100
ולהיות מסוגל להדפיס את המשתנים
או לראות מה באמת קורה

105
00:04:19,100 --> 00:04:22,980
מתחת למכסת מנוע פסוקי התכנית שלך
פשוט רצתי, זה כמו בהעתקים גיאולוגיים,

106
00:04:22,980 --> 00:04:25,030
ואתם כמו, אין לו מושג
מה בדיוק קרה כאן.

107
00:04:25,030 --> 00:04:26,730
אני לא יודע מה קו שהוא נכשל ב.

108
00:04:26,730 --> 00:04:29,040
אני לא יודע איפה זה השתבש.

109
00:04:29,040 --> 00:04:31,280
אז, GDB הוא הולך לעזור לך עם זה.

110
00:04:31,280 --> 00:04:35,240
כמו כן, אם אתה מחליט
להמשיך כן, ולקחת את 61,

111
00:04:35,240 --> 00:04:38,430
זה באמת, באמת להיות שלך
החבר הכי טוב, כי אני יכול להגיד לך

112
00:04:38,430 --> 00:04:40,840
בגלל שאני עובר כיתה ש.

113
00:04:40,840 --> 00:04:43,620
>> אנחנו הולכים להסתכל על ינארי
חיפוש, שאם אתם זוכרים

114
00:04:43,620 --> 00:04:47,540
ספר טלפונים לדוגמא נהדרת
מחזה מכיתה.

115
00:04:47,540 --> 00:04:50,620
אנחנו נהיה יישום ש, ו
הליכה דרך שקצת יותר,

116
00:04:50,620 --> 00:04:54,650
ולאחר מכן אנחנו עוברים ארבעה
מיני שונים, שהם בועה,

117
00:04:54,650 --> 00:04:56,285
בחירה, החדרה, ומיזוג.

118
00:04:56,285 --> 00:04:57,830

119
00:04:57,830 --> 00:04:58,330
מגניב.

120
00:04:58,330 --> 00:05:00,390
אז, GDB כפי שציינתי, הוא הבאגים.

121
00:05:00,390 --> 00:05:01,400

122
00:05:01,400 --> 00:05:09,370
ואלה הם סוג של גדול
דברים, פונקציות או פקודות הגדולות

123
00:05:09,370 --> 00:05:13,240
כי אתה משתמש בGDB, ואני אלך
שלך דרך הדגמה שלה ברגע אחד.

124
00:05:13,240 --> 00:05:15,360
>> אז, זה לא רק
הולך להישאר מופשט.

125
00:05:15,360 --> 00:05:18,000
אני אנסה לעשות את זה כמו בטון
ככל האפשר עבורכם.

126
00:05:18,000 --> 00:05:19,870
אז, לשבור.

127
00:05:19,870 --> 00:05:22,200
או שזה יהיה הפסקה
כמו, חלק מספר, ש

128
00:05:22,200 --> 00:05:26,900
מייצג קו בתכנית שלך,
או שאתה יכול לנקוב בשם פונקציה.

129
00:05:26,900 --> 00:05:30,150
אז, אם אתה אומר לשבור עיקרי,
הוא יפסיק בעיקרי,

130
00:05:30,150 --> 00:05:32,400
ולתת לך ללכת דרך פונקציה ש.

131
00:05:32,400 --> 00:05:36,350
>> כמו כן, אם יש לך כמה חיצוני
לתפקד כמו החלפה או קובייה,

132
00:05:36,350 --> 00:05:38,450
שהסתכלנו בשבוע שעבר.

133
00:05:38,450 --> 00:05:41,780
אם אתה אומר לשבור אחד מאותם,
בכל פעם שהתכנית שלך פוגעת ש,

134
00:05:41,780 --> 00:05:44,290
זה יחכו לך ל
תגיד לו מה לעשות.

135
00:05:44,290 --> 00:05:47,860
לפני זה פשוט יבצע, כך ש
באמת יכול לשלב בתוך הפונקציה

136
00:05:47,860 --> 00:05:49,020
ותראה מה קורה.

137
00:05:49,020 --> 00:05:50,370

138
00:05:50,370 --> 00:05:53,515
אז, בשלב הבא, רק מדלג על
השורה הבאה, הולכת על פונקציות.

139
00:05:53,515 --> 00:05:54,730

140
00:05:54,730 --> 00:05:55,560
צעד.

141
00:05:55,560 --> 00:05:56,810
כל אלה הם מופשטים הקטנים.

142
00:05:56,810 --> 00:06:00,530
אז, אני פשוט הולך לרוץ דרכם,
אבל אתה תראה אותם בשימוש בשני.

143
00:06:00,530 --> 00:06:01,810
>> צעד לתוך פונקציה.

144
00:06:01,810 --> 00:06:04,170
אז כפי שאמרתי,
כמו עם החלפה, זה היה

145
00:06:04,170 --> 00:06:07,110
מאפשר לך בעצם כאילו אתה
כמו כניסה פיזית בתוך,

146
00:06:07,110 --> 00:06:10,990
אתה יכול להתעסק עם משתנים אלו, הדפסה
מתוך מה שהם, לראות מה קורה.

147
00:06:10,990 --> 00:06:12,140

148
00:06:12,140 --> 00:06:14,830
רשימה תהיה ממש פשוט להדפיס
את הקוד שמסביב.

149
00:06:14,830 --> 00:06:17,570
אז, אם אתה סוג של לשכוח
שבו אתה נמצא בתכנית שלך,

150
00:06:17,570 --> 00:06:19,880
או שאתה תוהה
מה קורה סביבו,

151
00:06:19,880 --> 00:06:23,790
זה יהיה פשוט להדפיס את קטע
של אוהב חמישה או שישה קווים סביבו.

152
00:06:23,790 --> 00:06:26,080
אז, אתה יכול להתאפס
על איפה אתה נמצא.

153
00:06:26,080 --> 00:06:27,230

154
00:06:27,230 --> 00:06:28,650
>> להדפיס כמה משתנים.

155
00:06:28,650 --> 00:06:34,590
אז, אם יש לך מפתח כמו
בקיסר, שאנחנו מסתכלים.

156
00:06:34,590 --> 00:06:36,220
אתה יכול להגיד מפתח הדפסה בכל נקודה.

157
00:06:36,220 --> 00:06:40,070
זה יגיד לך מה הוא הערך כל כך
כי, אולי איפשהו בדרך,

158
00:06:40,070 --> 00:06:42,070
אתה החלפת את המפתח שלך.

159
00:06:42,070 --> 00:06:45,495
אתה באמת יכול להגיד את זה כי
למעשה ניתן לראות כי ערך.

160
00:06:45,495 --> 00:06:46,500

161
00:06:46,500 --> 00:06:48,780
>> בהמקומיים, רק הדפסים
את המשתנים המקומיים שלך.

162
00:06:48,780 --> 00:06:53,120
אז, בכל עת שאתה בתוך לולאה,
ואתה רק רוצה לראות כמו, אה.

163
00:06:53,120 --> 00:06:54,270
מה אני שלי?

164
00:06:54,270 --> 00:06:57,020
מהו ערך מפתח זה
כי אני לאתחל כאן?

165
00:06:57,020 --> 00:06:58,537
מהו המסר בשלב זה?

166
00:06:58,537 --> 00:07:00,370
זה יהיה פשוט להדפיס את כל
של אלה, כך שאתה

167
00:07:00,370 --> 00:07:04,330
לא צריך בנפרד
אומר, מסר הדפסת I. הדפסה.

168
00:07:04,330 --> 00:07:04,970
מפתח הדפסה.

169
00:07:04,970 --> 00:07:06,190

170
00:07:06,190 --> 00:07:07,700
ולאחר מכן להציג.

171
00:07:07,700 --> 00:07:10,370
מה שעושה זה כמו שאתה
המשך בתכנית,

172
00:07:10,370 --> 00:07:13,980
זה פשוט לוודא שזה
בו מוצגות כמה משתנים מסוימים

173
00:07:13,980 --> 00:07:14,780
בכל נקודה.

174
00:07:14,780 --> 00:07:17,160
כך שאתה also-- --it זה
סוג של קיצור דרך שבי

175
00:07:17,160 --> 00:07:19,530
אתה לא צריך להמשיך ככה, אה.

176
00:07:19,530 --> 00:07:23,150
מפתח הדפס או I. הדפסה זה פשוט
באופן אוטומטי לעשות את זה בשבילך.

177
00:07:23,150 --> 00:07:25,959
>> אז, עם זה, אנחנו הולכים
כדי לראות איך זה הולך.

178
00:07:25,959 --> 00:07:28,000
אני הולך לנסות ומתג
מעל למכשיר שלי.

179
00:07:28,000 --> 00:07:30,200

180
00:07:30,200 --> 00:07:31,271
לראות אם אני יכול לעשות את זה.

181
00:07:31,271 --> 00:07:31,770
כל.

182
00:07:31,770 --> 00:07:40,970

183
00:07:40,970 --> 00:07:42,370
אנחנו רק לשקף אותו.

184
00:07:42,370 --> 00:07:44,530
אין שום דבר מטורף
על המחשב הנייד שלי בכל מקרה.

185
00:07:44,530 --> 00:07:49,600

186
00:07:49,600 --> 00:07:50,100
אישור.

187
00:07:50,100 --> 00:07:57,030

188
00:07:57,030 --> 00:08:01,054
זה צריך להיות זה אחד.

189
00:08:01,054 --> 00:08:01,795
זה כל כך זעיר.

190
00:08:01,795 --> 00:08:03,730

191
00:08:03,730 --> 00:08:05,120
בואו תראו אם אנחנו יכולים לעשות את זה.

192
00:08:05,120 --> 00:08:09,970

193
00:08:09,970 --> 00:08:10,940
>> אישור.

194
00:08:10,940 --> 00:08:15,305
אליס היא ללא ספק נאבקת
כאן רק קצת,

195
00:08:15,305 --> 00:08:17,995
אבל בואו נעשינו את זה במזכרת.

196
00:08:17,995 --> 00:08:20,810

197
00:08:20,810 --> 00:08:22,020
אישור.

198
00:08:22,020 --> 00:08:25,900
אנחנו רק הולכים להגדיל את זה.

199
00:08:25,900 --> 00:08:28,770

200
00:08:28,770 --> 00:08:29,380
אישור.

201
00:08:29,380 --> 00:08:31,679
יכול כולם סוג של רואה את זה?

202
00:08:31,679 --> 00:08:32,470
אולי קצת?

203
00:08:32,470 --> 00:08:33,594
אני יודע שזה קצת קטן.

204
00:08:33,594 --> 00:08:34,570

205
00:08:34,570 --> 00:08:37,530
אתה לא ממש יכול להבין
איך לעשות את זה גדול יותר.

206
00:08:37,530 --> 00:08:38,350
אם מישהו יודע.

207
00:08:38,350 --> 00:08:40,309
האם מישהו יודע איך לעשות את זה גדול יותר?

208
00:08:40,309 --> 00:08:40,932
אישור.

209
00:08:40,932 --> 00:08:42,140
אנחנו הולכים לזרום עם זה.

210
00:08:42,140 --> 00:08:45,801
לא משנה בכל מקרה, כי זה פשוט
זה הקוד שאתם צריכים

211
00:08:45,801 --> 00:08:46,300
יש לי.

212
00:08:46,300 --> 00:08:48,310
>> מה שחשוב יותר
הוא המסוף כאן.

213
00:08:48,310 --> 00:08:52,840

214
00:08:52,840 --> 00:08:58,690
ויש לנו כאן למה זה כל כך קטן?

215
00:08:58,690 --> 00:09:02,325

216
00:09:02,325 --> 00:09:02,825
הגדרות.

217
00:09:02,825 --> 00:09:07,920

218
00:09:07,920 --> 00:09:08,420
אה.

219
00:09:08,420 --> 00:09:09,500
אייק האמיתי.

220
00:09:09,500 --> 00:09:10,880
מה קורה כאן?

221
00:09:10,880 --> 00:09:11,770
משם.

222
00:09:11,770 --> 00:09:19,370

223
00:09:19,370 --> 00:09:21,810
האם זה טוב יותר לכולם?

224
00:09:21,810 --> 00:09:22,525
אישור ,.

225
00:09:22,525 --> 00:09:23,025
מגניב.

226
00:09:23,025 --> 00:09:25,830

227
00:09:25,830 --> 00:09:28,220
>> אתה יודע כשאתה בCS
קשיים טכניים ברמה

228
00:09:28,220 --> 00:09:32,971
הם סוג של חלק מthe--
אז, בואו לנקות את זה.

229
00:09:32,971 --> 00:09:33,470
אישור.

230
00:09:33,470 --> 00:09:38,060
אז, ממש כאן בסעיף,
שהיו לנו כאן.

231
00:09:38,060 --> 00:09:40,830
קיסר הוא קובץ הפעלה.

232
00:09:40,830 --> 00:09:41,800
אז עשיתי את זה.

233
00:09:41,800 --> 00:09:46,370
אז, דבר אחד להבין עם GDB הוא
כי זה עובד רק בקבצי הפעלה.

234
00:09:46,370 --> 00:09:48,040
אז, אתה לא יכול להפעיל אותו בdotsy.

235
00:09:48,040 --> 00:09:50,532
אתה חייב לעשות את בעצם
בטוח שהקוד שלך הידור,

236
00:09:50,532 --> 00:09:51,865
ושזה באמת יכול להיות מנוהל.

237
00:09:51,865 --> 00:09:52,970

238
00:09:52,970 --> 00:09:56,186
>> לכן, ודא שאם זה לא
לקמפל, לקבל את זה כדי לקמפל,

239
00:09:56,186 --> 00:09:57,810
כך שסוג של אתה יכול לרוץ דרכו.

240
00:09:57,810 --> 00:10:04,590
לכן, כדי להתחיל GDB, כל מה שאתה עושה,
סוג GDB גלוריה, ואז פשוט

241
00:10:04,590 --> 00:10:06,250
קובץ שברצון.

242
00:10:06,250 --> 00:10:08,240
אני תמיד באיות קיסר.

243
00:10:08,240 --> 00:10:11,730
אבל אתה רוצה לוודא
מכיוון שזה הפעלה,

244
00:10:11,730 --> 00:10:14,210
הבזק הנקודה של TI, כך ש
אומר שאתה הולך

245
00:10:14,210 --> 00:10:19,240
לרוץ CSI אתה הולך לבצע
זה קבצים או עם הבאגים.

246
00:10:19,240 --> 00:10:19,910
אישור.

247
00:10:19,910 --> 00:10:22,885
אז, אתה עושה את זה, אתה מקבל
סוג זה של ג'יבריש.

248
00:10:22,885 --> 00:10:24,250

249
00:10:24,250 --> 00:10:25,750
זה פשוט כל הדברים על הבאגים.

250
00:10:25,750 --> 00:10:28,200
אתה לא באמת צריך
תדאג בקשר לזה עכשיו.

251
00:10:28,200 --> 00:10:31,460
וכמו שאתה רואה, יש לנו את זה
parens הפתוח, תוצר מקומי גולמי, קרוב parens,

252
00:10:31,460 --> 00:10:34,690
ורק נראה כמו סוג של
שורת הפקודה שלנו, נכון?

253
00:10:34,690 --> 00:10:37,010
>> אז, מה שאנחנו רוצים do--
--So, הדבר הראשון

254
00:10:37,010 --> 00:10:39,570
הוא שאנחנו רוצים לבחור
מקום לשבור אותו.

255
00:10:39,570 --> 00:10:42,332
אז, יש באג אחד
בתכנית קיסר זה

256
00:10:42,332 --> 00:10:44,290
שאני מציג, ש
אנחנו הולכים לברר.

257
00:10:44,290 --> 00:10:45,330

258
00:10:45,330 --> 00:10:56,350
זה מה שהיא עושה זה לוקח את הקלט
Barfoo בכל כמוסות, ומשום מה

259
00:10:56,350 --> 00:11:01,950
זה לא משנה א 'זה פשוט משאיר
את זה לבד, האם כל דבר אחר נכון,

260
00:11:01,950 --> 00:11:03,980
אבל המכתב השני
נותר ללא שינוי.

261
00:11:03,980 --> 00:11:07,120
אז, אנחנו הולכים לנסות ו
להבין למה זה.

262
00:11:07,120 --> 00:11:10,440
לכן, הדבר הראשון שאתה בדרך כלל
רוצה לעשות בכל פעם שאתה מתחיל בGDB

263
00:11:10,440 --> 00:11:12,010
הוא להבין איפה לשבור אותו.

264
00:11:12,010 --> 00:11:14,956
>> אז הקיסר הוא תכנית די קצרה.

265
00:11:14,956 --> 00:11:16,330
רק יש לנו תפקיד אחד, נכון?

266
00:11:16,330 --> 00:11:18,520
מה היה התפקיד שלנו בקיסר?

267
00:11:18,520 --> 00:11:19,590

268
00:11:19,590 --> 00:11:24,350
יש רק פונקציה אחת, נכון ראשי?

269
00:11:24,350 --> 00:11:26,490
העיקרי היא פונקציה
לכל התוכניות שלך.

270
00:11:26,490 --> 00:11:29,230
אם לא היה לך ראשי, אולי אני
להיות קצת מודאג עכשיו,

271
00:11:29,230 --> 00:11:31,000
אבל אני מקווה שכולכם היה ראשי לשם.

272
00:11:31,000 --> 00:11:34,150
אז, מה אנחנו יכולים לעשות הוא שאנחנו יכולים
פשוט לשבור ראשי, סתם ככה.

273
00:11:34,150 --> 00:11:35,190
אז, זה אומר, בסדר.

274
00:11:35,190 --> 00:11:37,430
אנו קובעים נקודת העצירה אחת שלנו יש.

275
00:11:37,430 --> 00:11:42,870
>> אז, עכשיו מה שצריך לזכור הוא קיסר
לוקח נכון טענת שורת פקודה אחת

276
00:11:42,870 --> 00:11:45,150
ואנחנו לא עשינו את זה בכל מקום עדיין.

277
00:11:45,150 --> 00:11:47,560
אז, מה שאתה עושה הוא כאשר
אתה בעצם ללכת לרוץ

278
00:11:47,560 --> 00:11:51,540
התכנית, כל תכנית שאתה
פועל בGDB שצריך שורת הפקודה

279
00:11:51,540 --> 00:11:55,010
טיעונים, אתה הולך קלט
כאשר אתה ראשון להתחיל להריץ אותה.

280
00:11:55,010 --> 00:11:59,280
אז, במקרה זה, אנחנו עושים
לרוץ עם מפתח של שלוש.

281
00:11:59,280 --> 00:12:00,770

282
00:12:00,770 --> 00:12:02,040
וזה באמת יתחיל.

283
00:12:02,040 --> 00:12:08,480
>> לכן, אם אתם רואים כאן, יש לנו
אם RC הוא לא שווה ל 2.

284
00:12:08,480 --> 00:12:12,210
אז אם אתם כל מה שיש
קובץ ששלחתי אותו

285
00:12:12,210 --> 00:12:15,100
אתה תראה שזה כמו
השורה הראשונה הפונקציה העיקרית שלנו, נכון?

286
00:12:15,100 --> 00:12:17,890
זה בודק אם יש לנו
את המספר הנכון של טיעונים.

287
00:12:17,890 --> 00:12:20,620
אז, אם אתה תוהה
אם RC הוא נכון,

288
00:12:20,620 --> 00:12:23,250
אתה יכול לעשות משהו פשוט כמו RC הדפסה.

289
00:12:23,250 --> 00:12:24,380

290
00:12:24,380 --> 00:12:28,640
RC הוא שני, שהוא
מה צפוי לנו, נכון?

291
00:12:28,640 --> 00:12:32,010
>> אז, אנחנו יכולים ללכת הבא,
וממשיך דרך.

292
00:12:32,010 --> 00:12:33,200
אז, יש לנו כמה מפתח יש.

293
00:12:33,200 --> 00:12:34,260

294
00:12:34,260 --> 00:12:37,090
ואנחנו יכולים להדפיס את המפתח שלנו
כדי לוודא שזה נכון.

295
00:12:37,090 --> 00:12:38,380

296
00:12:38,380 --> 00:12:39,500
מעניין.

297
00:12:39,500 --> 00:12:41,210
לא בדיוק מה שציפינו.

298
00:12:41,210 --> 00:12:44,810
אז, דבר אחד הוא מבין
עם GDB גם, הוא

299
00:12:44,810 --> 00:12:49,000
שזה לא עד שאתה בעצם פגע
הבא, כי הקו שאתה פשוט ראית

300
00:12:49,000 --> 00:12:50,720
מבוצע בפועל.

301
00:12:50,720 --> 00:12:53,870
לכן, במקרה זה מפתח
לא הוקצה עדיין.

302
00:12:53,870 --> 00:12:57,050
אז, מפתח הוא כמה ערך זבל
שאתה רואה בחלק התחתון יש.

303
00:12:57,050 --> 00:13:03,680
שלילי 120-- $ --It מיליארדים של אחד
ודברים מוזרים משהו נכון?

304
00:13:03,680 --> 00:13:05,340
זה לא המפתח שציפינו.

305
00:13:05,340 --> 00:13:10,720
אבל אם פגע הבא, ולאחר מכן אנו
לנסות ומפתח הדפסה, זה שלושה.

306
00:13:10,720 --> 00:13:11,710
>> כולם רואים את זה?

307
00:13:11,710 --> 00:13:13,780
אז, אם אתה מקבל משהו
שאתה אוהב את, לחכות.

308
00:13:13,780 --> 00:13:15,540
זה לגמרי
לא נכון, ואני לא יודע

309
00:13:15,540 --> 00:13:20,150
איך זה יקרה בגלל כל מה שאני רוצה
לעשות הוא להקצות מספר, משתנה,

310
00:13:20,150 --> 00:13:22,900
לנסות להכות הבא, נסה להדפיס
זה שוב, ולראות אם זה עובד.

311
00:13:22,900 --> 00:13:27,830
כי זה רק הולך לבצע ו
למעשה להקצות משהו אחריך

312
00:13:27,830 --> 00:13:29,340
הלהיט הבא.

313
00:13:29,340 --> 00:13:30,336
הגיוני לכולם?

314
00:13:30,336 --> 00:13:30,836
אה הא?

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: כאשר אתה אקראי
מספרים מה זה אומר?

316
00:13:33,220 --> 00:13:34,790
>> 1 דובר: זה פשוט אקראי.

317
00:13:34,790 --> 00:13:35,710
זה פשוט זבל.

318
00:13:35,710 --> 00:13:38,320
זה פשוט משהו ש
מחשב באופן אקראי להקצות.

319
00:13:38,320 --> 00:13:39,721

320
00:13:39,721 --> 00:13:40,220
מגניב.

321
00:13:40,220 --> 00:13:45,760
אז, עכשיו אנחנו יכולים לעבור, וכך
עכשיו יש לנו GetString טקסט רגיל זה.

322
00:13:45,760 --> 00:13:48,600
אז, תן לי רק להציג את מה ש
יקרה כאשר פגעו הבא כאן.

323
00:13:48,600 --> 00:13:51,320
GDB שלנו סוג של נעלם, נכון?

324
00:13:51,320 --> 00:13:55,720
זה בגלל GetString
עכשיו מבצע, נכון?

325
00:13:55,720 --> 00:14:01,460
אז, כשראינו טקסט רגיל שווה
GetString, parens וparens פתוחים,

326
00:14:01,460 --> 00:14:04,380
ואנחנו להיט הבאים, שיש
למעשה להורג עכשיו.

327
00:14:04,380 --> 00:14:06,580
אז, זה מחכה לי
לנו קלט משהו.

328
00:14:06,580 --> 00:14:13,560
>> אז, אנחנו הולכים קלט המזון שלנו ש
זה מה שזה לא הצליח כמו שאמרתי לך

329
00:14:13,560 --> 00:14:18,020
וכי רק אומר שזה
סיימתי ביצוע, שנסגר

330
00:14:18,020 --> 00:14:19,980
הסוגר אומר שזה
יציאה החוצה של לולאה ש.

331
00:14:19,980 --> 00:14:21,170

332
00:14:21,170 --> 00:14:25,420
לכן, אנו יכולים להיט בא, ועכשיו, כמו שאני
בטוח שאת מכירה מקיסר,

333
00:14:25,420 --> 00:14:27,260
זה, מה זה קו הולך לעשות.

334
00:14:27,260 --> 00:14:32,030
זה לInt אני שווה 0, N שווה
Strlen, טקסט רגיל, ולאחר מכן

335
00:14:32,030 --> 00:14:33,960
אני הוא פחות מ n, אני, בתוספת, בתוספת.

336
00:14:33,960 --> 00:14:35,210
מה היא לולאה זה הולך לעשות?

337
00:14:35,210 --> 00:14:37,900

338
00:14:37,900 --> 00:14:39,160
פתח את ההודעה שלך.

339
00:14:39,160 --> 00:14:39,770
מגניב.

340
00:14:39,770 --> 00:14:41,330
אז, בואו נתחיל לעשות את זה.

341
00:14:41,330 --> 00:14:47,210
>> אז, צריך את המצב הזה
להתאים, לראשון שלנו?

342
00:14:47,210 --> 00:14:52,250
אם זה B, זה אנחנו I. טקסט רגיל
ניתן לקבל מידע על המקומיים שלנו.

343
00:14:52,250 --> 00:14:53,610

344
00:14:53,610 --> 00:14:57,970
אז, אני הוא אפס, ואם שש, ש
אנו מצפים, והמפתח שלנו הוא שלוש.

345
00:14:57,970 --> 00:14:59,227
כל זה הגיוני, נכון?

346
00:14:59,227 --> 00:15:01,310
המספרים האלה הם כל
בדיוק מה שהם צריכים להיות.

347
00:15:01,310 --> 00:15:02,590

348
00:15:02,590 --> 00:15:03,870
אז, זמזם?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: יש לי
מספרים אקראיים למכרה.

350
00:15:05,620 --> 00:15:09,156

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: ובכן, אנחנו יכולים check-- --we
יכול לשוחח על זה בשנייה.

352
00:15:12,030 --> 00:15:14,110

353
00:15:14,110 --> 00:15:15,750
אבל אתה צריך להיות מקבל את זה.

354
00:15:15,750 --> 00:15:17,700

355
00:15:17,700 --> 00:15:20,130
אז, אם יש לנו הון
B לראשון שלנו,

356
00:15:20,130 --> 00:15:22,080
מצב זה צריך לתפוס אותו, נכון?

357
00:15:22,080 --> 00:15:27,120
אז, אם פגעו הבא, אנו רואים
כי אם זה מבצע למעשה.

358
00:15:27,120 --> 00:15:29,220
כי אם אתה הבא
לאורך בקוד שלך,

359
00:15:29,220 --> 00:15:33,460
הקו הזה כאן, שבו אני טקסט רגיל
מוחלף בחשבון זה,

360
00:15:33,460 --> 00:15:35,720
רק מבצע אם אם
מצב נכון נכונה?

361
00:15:35,720 --> 00:15:36,905

362
00:15:36,905 --> 00:15:40,240
>> GDB הוא רק הולך להראות לך
דברים שמבצעים בפועל.

363
00:15:40,240 --> 00:15:45,140
אז אם מצב אם זה לא הושג, זה
רק הולך לדלג לשורה הבאה.

364
00:15:45,140 --> 00:15:46,540
בסדר?

365
00:15:46,540 --> 00:15:48,510
אז, יש לנו את זה.

366
00:15:48,510 --> 00:15:51,171
הסוגר זה אומר שזה
סגור מחוץ ללולאה שעכשיו.

367
00:15:51,171 --> 00:15:52,420
אז, זה הולך להתחיל שוב.

368
00:15:52,420 --> 00:15:54,760

369
00:15:54,760 --> 00:15:56,280
פשוט ככה.

370
00:15:56,280 --> 00:15:59,120
אז, שאנחנו יכולים לקבל מידע
על המקומיים שלנו כאן,

371
00:15:59,120 --> 00:16:02,575
ואנחנו רואים ש הראשונים
המכתב השתנה, נכון?

372
00:16:02,575 --> 00:16:05,150
עכשיו זה E, כפי שהוא אמור להיות.

373
00:16:05,150 --> 00:16:07,360
אז, אנחנו יכולים להמשיך הלאה.

374
00:16:07,360 --> 00:16:08,500
>> ויש לנו סימון זו.

375
00:16:08,500 --> 00:16:09,916
ובדיקה זו צריכה לעבוד, נכון?

376
00:16:09,916 --> 00:16:12,570
זה א צריך להיות שונה זה
שלוש אותיות קדימה.

377
00:16:12,570 --> 00:16:14,320

378
00:16:14,320 --> 00:16:16,530
אבל אם תשימו לב, אנחנו
לקבל משהו שונה.

379
00:16:16,530 --> 00:16:17,580

380
00:16:17,580 --> 00:16:22,860
אז במקרה כאן זה, זה תפס
זה, וכן את הקו הזה להורג,

381
00:16:22,860 --> 00:16:28,620
ששונה ב 'שלנו
אבל, במקרה הזה כאן,

382
00:16:28,620 --> 00:16:32,860
יש לנו שזה פשוט לדלג עליה,
והלכתי ל[? siff L. ?]

383
00:16:32,860 --> 00:16:34,660
אז משהו קורה שם.

384
00:16:34,660 --> 00:16:37,780
מה זה אומר לך הוא ש,
אנחנו יודעים שהוא היה אמור לתפוס כאן,

385
00:16:37,780 --> 00:16:39,200
אבל זה לא.

386
00:16:39,200 --> 00:16:42,210
כל אחד יכול לראות מה שלנו
בעיה היא בקו זה?

387
00:16:42,210 --> 00:16:45,380

388
00:16:45,380 --> 00:16:46,969
זה דבר מאוד דקות.

389
00:16:46,969 --> 00:16:48,510
ואתה יכול גם להסתכל על הקוד שלך.

390
00:16:48,510 --> 00:16:49,980

391
00:16:49,980 --> 00:16:54,940
זה גם line-- לשכוח את מה קו זה
בthere-- אבל זה ב[ לא ברור].

392
00:16:54,940 --> 00:16:55,480
כן?

393
00:16:55,480 --> 00:16:58,639
>> 4 רמקול: זה על יותר מ
דף אם אתה קורא את זה בספר.

394
00:16:58,639 --> 00:16:59,430
1 SPEAKER: בדיוק.

395
00:16:59,430 --> 00:17:02,620
אז, הבאגים לא יכולים להגיד לי
שלך ש, אבל הבאגים

396
00:17:02,620 --> 00:17:05,880
יכול לקבל אותך לקו
כי אתה יודע שהוא לא מתפקד.

397
00:17:05,880 --> 00:17:09,319
ולפעמים, כאשר במיוחד
מאוחר יותר בסמסטר, כאשר

398
00:17:09,319 --> 00:17:12,910
עם מאה, יש לך עסק
מאה כמה שורות קוד, ואתה

399
00:17:12,910 --> 00:17:16,190
לא יודע איפה זה כושל,
זו היא דרך מצוינת לעשות את זה.

400
00:17:16,190 --> 00:17:17,900

401
00:17:17,900 --> 00:17:18,989
אז, מצאנו באג שלנו.

402
00:17:18,989 --> 00:17:21,530
אתה יכול לתקן את זה בקובץ שלך,
ואז אתה יכול להפעיל אותו שוב,

403
00:17:21,530 --> 00:17:23,029
וכל מה שהיה עובדים בצורה מושלמת.

404
00:17:23,029 --> 00:17:24,970

405
00:17:24,970 --> 00:17:30,590
וזה הדבר הגדול ביותר
זה יכול להיראות כמו, אישור.

406
00:17:30,590 --> 00:17:31,090
כן.

407
00:17:31,090 --> 00:17:31,370
מגניב.

408
00:17:31,370 --> 00:17:32,744
אתה יודע מה שאתה מחפש.

409
00:17:32,744 --> 00:17:34,910
אז, אתה יודע מה לעשות.

410
00:17:34,910 --> 00:17:39,021
>> GDB יכול להיות סופר מועיל, כי אתה
ניתן להדפיס את כל הדברים האלה שאתה

411
00:17:39,021 --> 00:17:39,520
לא היית.

412
00:17:39,520 --> 00:17:41,160
זה הרבה יותר מועיל מאשר printf.

413
00:17:41,160 --> 00:17:43,440
כמה מכם משתמש ב
כמו דוחות printf

414
00:17:43,440 --> 00:17:46,200
להבין איפה הבאג היה, נכון?

415
00:17:46,200 --> 00:17:48,450
אז, עם זה, אתה לא
צריך לשמור חוזר,

416
00:17:48,450 --> 00:17:51,139
ורוצה להעיר ב
Printf, או להעיר את,

417
00:17:51,139 --> 00:17:52,930
ולהבין מה
אתה צריך להיות בהדפסה.

418
00:17:52,930 --> 00:17:55,670
זה בעצם רק מאפשר לך
צעד דרך, להדפיס את הדברים

419
00:17:55,670 --> 00:18:00,000
כמו שאתה הולך דרך, כל כך, שאתה יכול
לבחון כיצד הם משתנים בזמן אמת,

420
00:18:00,000 --> 00:18:02,190
כתכנית שלך פועל.

421
00:18:02,190 --> 00:18:04,390
>> וזה ייקח קצת
קצת הזמן להתרגל אליו.

422
00:18:04,390 --> 00:18:07,850
אני מאוד ממליץ פשוט סוג
להיות קצת מתוסכל עם זה

423
00:18:07,850 --> 00:18:08,930
לעכשיו.

424
00:18:08,930 --> 00:18:13,450
אם אתם מבלים שעות על
בשבוע הבא לומד כיצד להשתמש GDB,

425
00:18:13,450 --> 00:18:16,140
תוכל לחסוך לעצמך
כל כך הרבה זמן מאוחר יותר.

426
00:18:16,140 --> 00:18:18,750
ופשוטו כמשמעו. אנחנו אומרים לי
לאנשים בכל שנה זה,

427
00:18:18,750 --> 00:18:23,890
ואני זוכר שלקחתי את
כיתה, הייתי כמו, אני יהיה בסדר.

428
00:18:23,890 --> 00:18:24,700
מס '

429
00:18:24,700 --> 00:18:27,030
Pset 6 נכנס ואני היה
כאילו, אני הולך ללמוד

430
00:18:27,030 --> 00:18:29,500
כיצד להשתמש GDB כי אני לא
יודע מה קורה כאן.

431
00:18:29,500 --> 00:18:32,940
>> אז אם אתה לוקח את הזמן כל כך
להשתמש בו בתוכניות קטנות יותר

432
00:18:32,940 --> 00:18:35,697
שאתה הולך להיות
עובד על, כמו לעבוד

433
00:18:35,697 --> 00:18:37,530
דרך משהו כמו
Visionare, כמו זה.

434
00:18:37,530 --> 00:18:38,800

435
00:18:38,800 --> 00:18:42,850
או אם אתה רוצה תרגול נוסף, אני בטוח ש
אני יכול לבוא עם תוכניות מרכבה,

436
00:18:42,850 --> 00:18:45,300
לך לאתר באגים, אם תרצה.

437
00:18:45,300 --> 00:18:49,300
>> אבל אם אתה פשוט לקחת קצת זמן כדי לקבל
מתרגל לזה, פשוט לשחק עם זה,

438
00:18:49,300 --> 00:18:50,550
זה באמת ישרת אותך היטב.

439
00:18:50,550 --> 00:18:52,591
וזה באמת אחד מ
הדברים האלה שאתה פשוט

440
00:18:52,591 --> 00:18:57,340
צריך לנסות, ולקבל את הידיים מלוכלכות
עם, לפני שאתה באמת מבין את זה.

441
00:18:57,340 --> 00:19:02,090
אני באמת רק הבנתי את זה פעם אחת
היה דברים באגים עם זה אני,

442
00:19:02,090 --> 00:19:08,170
וזה הרבה יותר נחמד יש לי רעיון של
איך לאתר באגים במוקדם ולא במאוחר.

443
00:19:08,170 --> 00:19:08,850
אישור.

444
00:19:08,850 --> 00:19:09,625
מגניב.

445
00:19:09,625 --> 00:19:12,960
אני יודע שזה כמו סוג של
קורס מזורז בGDB,

446
00:19:12,960 --> 00:19:16,400
ואני בהחלט לעבוד על מקבל
אלה להסתכל הפעם הבאה גדולה יותר.

447
00:19:16,400 --> 00:19:17,590

448
00:19:17,590 --> 00:19:18,280
מגניב.

449
00:19:18,280 --> 00:19:20,390
>> אז, אם נחזור ל- PowerPoint שלנו.

450
00:19:20,390 --> 00:19:27,194

451
00:19:27,194 --> 00:19:28,110
האם זה הולך לעבוד?

452
00:19:28,110 --> 00:19:29,711

453
00:19:29,711 --> 00:19:30,210
AWH.

454
00:19:30,210 --> 00:19:31,101
כן.

455
00:19:31,101 --> 00:19:31,600
אישור.

456
00:19:31,600 --> 00:19:35,480
אז, אם אתה אי פעם צריך את כל
שוב אלה, יש הרשימה.

457
00:19:35,480 --> 00:19:37,160

458
00:19:37,160 --> 00:19:40,830
חיפוש בינארי כך, שכולם
זוכר את המחזה הגדול של דוד

459
00:19:40,830 --> 00:19:42,259
קורע ספרי טלפון במחצית.

460
00:19:42,259 --> 00:19:44,050
אני לא ממש מקבל את
ספרי טלפון יותר,

461
00:19:44,050 --> 00:19:46,530
כי כמו איפה אתה
לקבל ספרי טלפון בימים אלה?

462
00:19:46,530 --> 00:19:48,220
אני באמת לא יודע.

463
00:19:48,220 --> 00:19:49,840

464
00:19:49,840 --> 00:19:50,590
החיפוש בינארי.

465
00:19:50,590 --> 00:19:52,464
האם מישהו זוכר
איך ינארי עבודות חיפוש?

466
00:19:52,464 --> 00:19:54,380

467
00:19:54,380 --> 00:19:55,220
מישהו בכלל?

468
00:19:55,220 --> 00:19:56,325
כן?

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: אתה יודע מתי
אתה מסתכל על איזה חצי

470
00:19:58,283 --> 00:20:01,146
זה יהיה ב, בהתבסס על כך,
כדי להיפטר מאת החצי השני.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 בדיוק.

472
00:20:01,896 --> 00:20:06,290
אז, חיפוש בינארי, שזה סוג של a--
--we אוהב לקרוא לזה פרד ומשול.

473
00:20:06,290 --> 00:20:09,170
אז, מה תוכל לעשות הוא
אתה תיראה באמצע,

474
00:20:09,170 --> 00:20:11,990
ותראה אם ​​היא מתאימה
מה שאתה מחפש.

475
00:20:11,990 --> 00:20:15,420
ואם זה לא, אז אתה מנסה
להבין, זה הולך להיות שמאל

476
00:20:15,420 --> 00:20:16,450
מחצית או חצי הנכון.

477
00:20:16,450 --> 00:20:19,325
אז, זה יכול להיות אם אתה מחפש
במשהו שלפי האלפבית,

478
00:20:19,325 --> 00:20:20,720
אתה רואה, הו.

479
00:20:20,720 --> 00:20:22,750
האם מגיע אליסון לפני M?

480
00:20:22,750 --> 00:20:23,250
כן.

481
00:20:23,250 --> 00:20:25,030
אז, אנחנו הולכים
מסתכל על המחצית הראשונה.

482
00:20:25,030 --> 00:20:26,450
>> או שזה יכול להיות כמו עם מספרים.

483
00:20:26,450 --> 00:20:28,830
כל דבר שאתה יכול
להשוות, ניתן למיין אותו.

484
00:20:28,830 --> 00:20:29,920

485
00:20:29,920 --> 00:20:31,260
ניתן להשתמש בחיפוש בינארי ב.

486
00:20:31,260 --> 00:20:32,340

487
00:20:32,340 --> 00:20:37,455
אז, מישהו זוכר את זה
גרף או מה זה?

488
00:20:37,455 --> 00:20:39,520
זה מורכבות אסימפטוטי.

489
00:20:39,520 --> 00:20:42,830
אז, גרף זה פשוט
מתאר כמה זמן זה

490
00:20:42,830 --> 00:20:46,230
לוקח אותך לפתרון בעיה כ
אם תגדיל את מספרם של הדברים

491
00:20:46,230 --> 00:20:47,090
שאתה משתמש.

492
00:20:47,090 --> 00:20:51,260
>> אז, יש לנו N, שהוא הזמן ליניארי.

493
00:20:51,260 --> 00:20:54,560
אם N יותר משני, שהוא מעט
, עדיין גדל טוב יותר סופר מהיר.

494
00:20:54,560 --> 00:20:58,360
ולאחר מכן יש לנו כניסה, אשר הוא
מה שאנו מחשיבים חיפוש בינארי.

495
00:20:58,360 --> 00:21:03,630
אם אנחנו שמים לב, כבעיה שלך
מקבל הרבה והרבה יותר גדול,

496
00:21:03,630 --> 00:21:06,600
הזמן שלוקח לך לפתור אותה
לא ממש להגדיל כל כך הרבה.

497
00:21:06,600 --> 00:21:09,010
זה כמו להשוות
כאן בהתחלה.

498
00:21:09,010 --> 00:21:10,060
אתה כמו, אישור.

499
00:21:10,060 --> 00:21:13,000
שום דבר כאן לא ממש
משנה איזה מהם אנחנו משתמשים,

500
00:21:13,000 --> 00:21:16,220
אבל אתה מקבל למ', מיליארדים.

501
00:21:16,220 --> 00:21:20,010
אתה מנסה למצוא some-- --you're
מנסה למצוא מחט בערימת שחת.

502
00:21:20,010 --> 00:21:21,550
>> אני חושב שאתה רוצה את הבעיה הזו.

503
00:21:21,550 --> 00:21:25,850
אתה רוצה את המורכבות הזאת, לא
ליניארי, כי לכל מה שאתה

504
00:21:25,850 --> 00:21:30,049
לדעתך הולכים להיות מחפש דרך
כל מחט בודדת, דבר חציר,

505
00:21:30,049 --> 00:21:31,340
מנסה לחפש המחט שלך.

506
00:21:31,340 --> 00:21:34,730
וזה לא כיף מדי לדעתי.

507
00:21:34,730 --> 00:21:35,500
אני אוהב מהר.

508
00:21:35,500 --> 00:21:36,620
אני אוהב יעיל.

509
00:21:36,620 --> 00:21:40,450
ותלמידים חרוצים כמו שאתה
חבר'ה, יודע שאתה עובד בצורה חכמה יותר,

510
00:21:40,450 --> 00:21:43,010
לא דבר סוג קשה יותר, איך אתה
יכול לפצות אלגוריתמים אלה.

511
00:21:43,010 --> 00:21:45,110

512
00:21:45,110 --> 00:21:47,910
>> אז, אנחנו הולכים ללכת
דרך רק דוגמה קטנה.

513
00:21:47,910 --> 00:21:51,090
אני חושב שאתם צריכים
יד על חיפוש בינארי,

514
00:21:51,090 --> 00:21:54,352
אבל במקרה שמישהו הוא קצת
מטושטש, רוצה לחזק אותו,

515
00:21:54,352 --> 00:21:56,310
אנחנו הולכים רק כדי ללכת
באמצעות דוגמא כאן.

516
00:21:56,310 --> 00:21:59,490
אז, אנחנו מחפשים אם
המערך מכיל שבע.

517
00:21:59,490 --> 00:22:00,540

518
00:22:00,540 --> 00:22:06,010
>> אז, הדבר הראשון שאנחנו עושים הוא
נראה באמצע, נכון?

519
00:22:06,010 --> 00:22:09,340
וגם אתה הולך להיות קידוד
חיפוש בינארי רק שני.

520
00:22:09,340 --> 00:22:11,310
אז, זה הולך להיות כיף.

521
00:22:11,310 --> 00:22:13,710
אז אנחנו מסתכלים ב
מערכים קטנים באמצע 3.

522
00:22:13,710 --> 00:22:15,501
האם 3 שווים 7?

523
00:22:15,501 --> 00:22:16,000
לא.

524
00:22:16,000 --> 00:22:18,670

525
00:22:18,670 --> 00:22:19,550
זה שש.

526
00:22:19,550 --> 00:22:21,480
אז, האם זה פחות מ
או יותר משבעה?

527
00:22:21,480 --> 00:22:23,080

528
00:22:23,080 --> 00:22:23,960
פחות מ.

529
00:22:23,960 --> 00:22:24,570
כן.

530
00:22:24,570 --> 00:22:25,170
נחמדים עבודת בחורים.

531
00:22:25,170 --> 00:22:25,569

532
00:22:25,569 --> 00:22:27,360
אני מרגיש שאני אוהב אני צריך
יש לי ממתקים כי אני

533
00:22:27,360 --> 00:22:29,460
רוצה לזרוק אותו החוצה לחצרות.

534
00:22:29,460 --> 00:22:30,270
זה מה שאני הולך לעשות בשבוע הבא.

535
00:22:30,270 --> 00:22:31,436
זה ישמור אותך בחורים חדים.

536
00:22:31,436 --> 00:22:32,560

537
00:22:32,560 --> 00:22:34,690
>> אז, אנחנו זורקים ש
המחצית ראשונה, נכון?

538
00:22:34,690 --> 00:22:35,670
זה היה פחות מ.

539
00:22:35,670 --> 00:22:39,325
אנחנו יודעים כל מה ש
שבצד שמאל

540
00:22:39,325 --> 00:22:41,700
הולך להיות פחות ממה ש
אנחנו באמת מחפשים.

541
00:22:41,700 --> 00:22:43,491
אז, אין צורך ל
לשים לב לזה.

542
00:22:43,491 --> 00:22:45,120
פשוט לשכוח אותו.

543
00:22:45,120 --> 00:22:48,720
אז, עכשיו אנחנו מסתכלים בצד ימין שלנו,
ואנחנו מסתכל על האמצע שם,

544
00:22:48,720 --> 00:22:50,510
ועכשיו זה תשע.

545
00:22:50,510 --> 00:22:55,510
אז, 9 is-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
גדול יותר ממה שאנחנו
מחפש, נכון?

547
00:22:57,470 --> 00:22:59,860
אז, אנחנו הולכים לזרוק
משם הכל בצד הימין.

548
00:22:59,860 --> 00:23:00,970

549
00:23:00,970 --> 00:23:01,940
כמו ש.

550
00:23:01,940 --> 00:23:03,700
עכשיו, כל מה שאנחנו נשארים עם אחד.

551
00:23:03,700 --> 00:23:07,760
אז אנחנו בודקים, זה אחד מה
אנחנו מחפשים? זה.

552
00:23:07,760 --> 00:23:08,970
מצאנו את מה שרצינו.

553
00:23:08,970 --> 00:23:10,440

554
00:23:10,440 --> 00:23:11,690
אז סיימנו.

555
00:23:11,690 --> 00:23:12,550
Bilinear חיפוש.

556
00:23:12,550 --> 00:23:15,740
>> ואם אתה שם לב, אנחנו
היו שם שבע תשומות.

557
00:23:15,740 --> 00:23:24,320
זה רק לקח אותנו כמו שלוש פעמים,
אבל אם אתה עושה כמו מיליארדים,

558
00:23:24,320 --> 00:23:28,190
אתם יודעים כמה צעדים שהיית
לקחת אם היו לנו ארבעה מליארד דברים?

559
00:23:28,190 --> 00:23:29,940

560
00:23:29,940 --> 00:23:30,455
ניחושים?

561
00:23:30,455 --> 00:23:32,286

562
00:23:32,286 --> 00:23:33,960
זה 32.

563
00:23:33,960 --> 00:23:37,110
32 צעדים כדי למצוא משהו
בארבעה מיליארדים

564
00:23:37,110 --> 00:23:39,650
מערך אלמנט בגלל כוחות של שני.

565
00:23:39,650 --> 00:23:43,550
אז שני הוא 32, הוא ארבעה מיליארדים.

566
00:23:43,550 --> 00:23:50,430
>> אז די מטורף איך אתה עדיין בתוך
כמו מספר קטן למדי של צעדים

567
00:23:50,430 --> 00:23:52,650
למצוא משהו ב
ארבעה מליארד אלמנטים.

568
00:23:52,650 --> 00:23:55,730
אז בנימה זאת, אנחנו
הולך לקוד זה

569
00:23:55,730 --> 00:23:58,950
כך אתם בעצם יכולים
סוג של לראות איך זה עובד.

570
00:23:58,950 --> 00:24:01,520
בסדר, אז אתם יכולים קוד.

571
00:24:01,520 --> 00:24:04,100
אני הולך לתת לכם
לדבר קצת.

572
00:24:04,100 --> 00:24:07,970
להכיר את אנשים סביבך, שהוא
מה שמישהו רוצה מן הסעיף אחרון.

573
00:24:07,970 --> 00:24:10,280
>> אז להכיר את האנשים סביבך.

574
00:24:10,280 --> 00:24:11,305
לדבר קצת.

575
00:24:11,305 --> 00:24:12,580

576
00:24:12,580 --> 00:24:15,730
וכל מה שאני רוצה ממך
בחורים עכשיו הוא רק

577
00:24:15,730 --> 00:24:17,575
מנסה ליצור קווי המתאר של פסאודו קוד.

578
00:24:17,575 --> 00:24:18,075
בסדר?

579
00:24:18,075 --> 00:24:20,825

580
00:24:20,825 --> 00:24:21,325
וואו.

581
00:24:21,325 --> 00:24:23,320

582
00:24:23,320 --> 00:24:29,520
כל מה שאני רוצה מכם הוא שאתה
רק הולך למלא במקרה בזמן זה.

583
00:24:29,520 --> 00:24:32,170
אז אני צריך להגדיר עליון אלה
וחסמים התחתונים ש

584
00:24:32,170 --> 00:24:35,250
מייצג את תחילת
וסוף המערך שלנו.

585
00:24:35,250 --> 00:24:40,440
ואתה הולך בעצם
לולאה דרך ולהבין

586
00:24:40,440 --> 00:24:42,470
מה שאנחנו עושים בתוך לולאת ה while זה.

587
00:24:42,470 --> 00:24:45,810
>> אז אם אתה יכול להבין out-- יש לי
רמז there-- מה הם המקרים

588
00:24:45,810 --> 00:24:46,640
שיש לנו כאן?

589
00:24:46,640 --> 00:24:48,100

590
00:24:48,100 --> 00:24:51,560
אז אם אתה רוצה להבין
מקרים, אנו פסאודו קוד אלה

591
00:24:51,560 --> 00:24:53,350
ואז למעשה את הקוד שלהן.

592
00:24:53,350 --> 00:24:55,330
וזה הולך להיות, אני
חושב, אני מקווה שזה

593
00:24:55,330 --> 00:24:56,788
להיות קצת יותר קל ממה שאתה מצפה.

594
00:24:56,788 --> 00:24:57,554

595
00:24:57,554 --> 00:25:00,220
כי זה לא כל כך הרבה קוד,
למעשה, שהוא ממש מגניב.

596
00:25:00,220 --> 00:25:34,110

597
00:25:34,110 --> 00:25:35,018
>> ממ-הממ?

598
00:25:35,018 --> 00:25:35,893
>> תלמיד: [לא ברור]?

599
00:25:35,893 --> 00:25:36,984

600
00:25:36,984 --> 00:25:37,650
מנחה: כן.

601
00:25:37,650 --> 00:25:38,595
היה משהו
למצוא באמצע.

602
00:25:38,595 --> 00:25:39,552
>> תלמיד: אז אנחנו יכולים להשתמש בזה.

603
00:25:39,552 --> 00:25:39,770
אישור.

604
00:25:39,770 --> 00:25:40,603
>> מנחה: מושלמת.

605
00:25:40,603 --> 00:25:42,950
אז זה הדבר הראשון שאנחנו צריכים לעשות.

606
00:25:42,950 --> 00:25:44,330
אז למצוא את האמצע.

607
00:25:44,330 --> 00:25:45,415

608
00:25:45,415 --> 00:25:45,915
גדול.

609
00:25:45,915 --> 00:25:47,770

610
00:25:47,770 --> 00:25:55,010
אז יש לך רעיון כיצד תוכל
למעשה למצוא את האמצע עם קוד?

611
00:25:55,010 --> 00:25:55,980
>> סטודנט: כן.

612
00:25:55,980 --> 00:25:57,000
n מעל 2?

613
00:25:57,000 --> 00:25:58,500

614
00:25:58,500 --> 00:25:59,500
מנחה: אז n מעל 2.

615
00:25:59,500 --> 00:26:05,170
אז דבר אחד שיש לזכור הוא ש
הגבול העליון ותחתון שלך לשנות.

616
00:26:05,170 --> 00:26:08,110
אנחנו ממשיכים הצרת החלק
של המערך שאנחנו מחפשים.

617
00:26:08,110 --> 00:26:11,970
אז n מעל 2 יפעל רק
את הדבר הראשון שאנחנו עושים.

618
00:26:11,970 --> 00:26:17,810
אז לוקח עליון ותחתון בחשבון,
איך יכול להיות שנקבל אלמנט האמצע?

619
00:26:17,810 --> 00:26:20,640
מכיוון שאנחנו רוצים האמצע
בין עליון ותחתון, נכון?

620
00:26:20,640 --> 00:26:21,730

621
00:26:21,730 --> 00:26:22,494
ממ-הממ?

622
00:26:22,494 --> 00:26:23,369
>> תלמיד: [לא ברור].

623
00:26:23,369 --> 00:26:26,170

624
00:26:26,170 --> 00:26:28,080
>> מנחה: אז יש לנו קצת באמצע.

625
00:26:28,080 --> 00:26:32,730
וזה יהיה עליון בתוספת נמוכה יותר מ -2.

626
00:26:32,730 --> 00:26:34,740

627
00:26:34,740 --> 00:26:35,690
מדהים.

628
00:26:35,690 --> 00:26:36,570
הנה אנחנו מתחילים.

629
00:26:36,570 --> 00:26:37,280
למטה בשורה אחת.

630
00:26:37,280 --> 00:26:38,560
אתם בדרך שלך.

631
00:26:38,560 --> 00:26:41,400
אז עכשיו שיש לנו שלנו
אמצע, מה אנחנו רוצים לעשות?

632
00:26:41,400 --> 00:26:45,050

633
00:26:45,050 --> 00:26:45,900
רק באופן כללי.

634
00:26:45,900 --> 00:26:47,734
אתה לא צריך קוד זה.

635
00:26:47,734 --> 00:26:48,335
כן.

636
00:26:48,335 --> 00:26:49,210
תלמיד: [לא ברור]?

637
00:26:49,210 --> 00:27:00,310

638
00:27:00,310 --> 00:27:10,310
מנחה: אז זה תוספת בגלל שאתה
מציאת הממוצעת בין שני

639
00:27:10,310 --> 00:27:10,810
שלהם.

640
00:27:10,810 --> 00:27:11,890

641
00:27:11,890 --> 00:27:17,370
אז אם אתה חושב עליהם כעל סוג
של הגדלת מהצדדים,

642
00:27:17,370 --> 00:27:21,640
אחשוב על זה כאשר אתה מתקרב
האמצע, אתה רוצה כמו ש.

643
00:27:21,640 --> 00:27:27,150
אז אם הייתם משני צדי
אמצע, ויש לי כמו 5 ו -7.

644
00:27:27,150 --> 00:27:31,440
כאשר אתה מוסיף אותם יחד אתה
מקבלים 12, אתה מחלק על ידי 2, הוא 6.

645
00:27:31,440 --> 00:27:33,726
>> לפעמים קשה ל
להסביר למה זה עובד,

646
00:27:33,726 --> 00:27:35,600
אבל אם אתה עובד דרך
דוגמא לפעמים,

647
00:27:35,600 --> 00:27:37,962
זה יעזור לך להבין אם
זה צריך להיות תוספת או בניכוי.

648
00:27:37,962 --> 00:27:38,846
כן.

649
00:27:38,846 --> 00:27:40,830
>> תלמיד: [לא ברור]
בדיוק באמצע

650
00:27:40,830 --> 00:27:43,950
אם היה להם מקרה שבו
יש הרבה מספרים קטנים יותר

651
00:27:43,950 --> 00:27:45,860
וכמו מספר אחד גדול?

652
00:27:45,860 --> 00:27:49,750
>> מנחה: אז כל מה שאתה צריך
הוא אמצע המערך.

653
00:27:49,750 --> 00:27:53,010
אז אם היה לך חבורה של מספרים קטנים
ולאחר מכן מספר אחד גדול באמת

654
00:27:53,010 --> 00:27:54,799
בסוף, זה לא משנה.

655
00:27:54,799 --> 00:27:56,840
כל מה שמשנה הוא ש
הם מסודרים, אתה פשוט

656
00:27:56,840 --> 00:27:59,339
רוצה להסתכל על אמצע
המערך בגלל שאתה עדיין

657
00:27:59,339 --> 00:28:00,700
חותך את הבעיה שלך במחצית.

658
00:28:00,700 --> 00:28:03,020

659
00:28:03,020 --> 00:28:03,680
מגניב.

660
00:28:03,680 --> 00:28:06,430
אז עכשיו שיש לנו
אמצע, מה עושים עכשיו?

661
00:28:06,430 --> 00:28:07,150
>> תלמיד: שקלו.

662
00:28:07,150 --> 00:28:08,150
מנחה: להשוות.

663
00:28:08,150 --> 00:28:11,670
אז להשוות מרכז לvalue_wanted.

664
00:28:11,670 --> 00:28:14,300

665
00:28:14,300 --> 00:28:15,160
מגניב.

666
00:28:15,160 --> 00:28:17,950
אז אתה רואה כאן יש לנו
ערך זה שאנחנו רוצים כאן.

667
00:28:17,950 --> 00:28:22,012

668
00:28:22,012 --> 00:28:23,095
זכור את זה הוא מערך.

669
00:28:23,095 --> 00:28:24,100

670
00:28:24,100 --> 00:28:26,970
אז אמצע מתייחס למדד.

671
00:28:26,970 --> 00:28:29,785
אז אנחנו רוצים לעשות ערכים של אמצעי.

672
00:28:29,785 --> 00:28:32,380

673
00:28:32,380 --> 00:28:35,650
אל תשכחו, אם אתה רוצה
כדי להשוות, שווים כפולים.

674
00:28:35,650 --> 00:28:38,250
אתה עושה אחד שווה אתה
רק הולך להקצות מחדש אותו,

675
00:28:38,250 --> 00:28:41,090
ואז, כמובן, זה
הולך להיות הערך שאתה רוצה.

676
00:28:41,090 --> 00:28:42,300
אז לא עושה את זה.

677
00:28:42,300 --> 00:28:44,350
>> אז אנחנו הולכים כדי לראות אם
הערכים באמצע

678
00:28:44,350 --> 00:28:46,460
שווה לערך שאנחנו רוצים.

679
00:28:46,460 --> 00:28:47,749

680
00:28:47,749 --> 00:28:48,790
אל תשכח הפלטה שלך.

681
00:28:48,790 --> 00:28:50,520

682
00:28:50,520 --> 00:28:52,235
Dropbox צריך ללכת.

683
00:28:52,235 --> 00:28:54,140

684
00:28:54,140 --> 00:28:56,200
אז מה עושים במקרה זה?

685
00:28:56,200 --> 00:28:59,360
אם זה מה שאנחנו רוצים לחזור?

686
00:28:59,360 --> 00:29:01,510

687
00:29:01,510 --> 00:29:02,626
אנחנו מנסים לומר.

688
00:29:02,626 --> 00:29:03,440
>> תלמיד: הדפסה מ.

689
00:29:03,440 --> 00:29:05,314
>> מנחה: ובכן, אנחנו
לא רוצה להדפיס את.

690
00:29:05,314 --> 00:29:08,220
אז זה בול כאן, כדי ש
רוצה לחזור אמת או שקר.

691
00:29:08,220 --> 00:29:12,280
אנחנו אומרים, הוא מספר זה
[? RRA? ?] אז אם זה,

692
00:29:12,280 --> 00:29:13,788
אנחנו פשוט להחזיר אותו נכונים.

693
00:29:13,788 --> 00:29:16,780

694
00:29:16,780 --> 00:29:17,760
אם אני יכול לאיית נכון.

695
00:29:17,760 --> 00:29:18,830

696
00:29:18,830 --> 00:29:20,805
>> תלמיד: למה שלא תחזור אפס?

697
00:29:20,805 --> 00:29:22,930
מנחה: אז אתה יכול
לחזור אפס, אם אתה רוצה.

698
00:29:22,930 --> 00:29:26,780
אבל במקרה הזה, כי
הפונקציה שלנו חוזרת בול,

699
00:29:26,780 --> 00:29:28,962
אנחנו צריכים לחזור אמת או שקר.

700
00:29:28,962 --> 00:29:30,920
תלמיד: כשאתה
אומר ביטוי בוליאני,

701
00:29:30,920 --> 00:29:33,450
אתה יכול להגדיר את זה שווה לשקר?

702
00:29:33,450 --> 00:29:39,860
כמו אם אני רוצה לומר, אם זה מצב
לא נפגש, כמו הוא עליון שווה כוזב.

703
00:29:39,860 --> 00:29:42,332
האם זה להבין אם אתה רק
לשים שווא בצד השני?

704
00:29:42,332 --> 00:29:43,040
מנחה: כן.

705
00:29:43,040 --> 00:29:44,820
אז בעצם אם אתה
אי פעם לעשות משהו

706
00:29:44,820 --> 00:29:49,600
כמו הוא עליון או נמוך,
שמחזיר אמת או שקר

707
00:29:49,600 --> 00:29:53,850
וזה סגנון בעצם רע ל
למשל שווה שווה אמיתי או שווה

708
00:29:53,850 --> 00:29:54,840
שווה כוזב.

709
00:29:54,840 --> 00:30:00,210
אתה רוצה להשתמש בתוצאה ש
כעצמו כשק שלך.

710
00:30:00,210 --> 00:30:04,720

711
00:30:04,720 --> 00:30:05,860
לא מה שרציתי.

712
00:30:05,860 --> 00:30:08,150

713
00:30:08,150 --> 00:30:09,240
זה מה שאני רוצה.

714
00:30:09,240 --> 00:30:13,205
אז במקרה שלך אתה שואל
על משהו כמו לשמור את זה בג.

715
00:30:13,205 --> 00:30:16,320

716
00:30:16,320 --> 00:30:25,150
>> אז אם יש לנו int main (void)
ומשהו כזה.

717
00:30:25,150 --> 00:30:31,922
ויש לך אם הוא עליון
של קצת קלט ואתה

718
00:30:31,922 --> 00:30:33,630
שואל אם אתה יכול לעשות
משהו כמו זה?

719
00:30:33,630 --> 00:30:35,010

720
00:30:35,010 --> 00:30:35,679
נכון?

721
00:30:35,679 --> 00:30:37,470
תלמיד: אני מנסה
לעשות [לא ברור] זה.

722
00:30:37,470 --> 00:30:38,450
כי אם it's--

723
00:30:38,450 --> 00:30:39,200
מנחה: העכבר.

724
00:30:39,200 --> 00:30:41,197
אז אתה רוצה שזה יהיה שקר, נכון?

725
00:30:41,197 --> 00:30:41,780
סטודנט: כן.

726
00:30:41,780 --> 00:30:45,960
מנחה: אז במקרה הזה אתה
רוצה אותו לבצע אם זה לא נכון.

727
00:30:45,960 --> 00:30:50,510
אז הדבר מגניב שאתה עושה יש את זה.

728
00:30:50,510 --> 00:30:52,900

729
00:30:52,900 --> 00:30:55,650
אז לזכור קריאה
נקודה שוללת דברים?

730
00:30:55,650 --> 00:30:58,270
זה אומר [לא ברור] פירושו לא.

731
00:30:58,270 --> 00:31:03,590
אז אם אנחנו מסתכלים רק
חלק זה כאן, שהיית

732
00:31:03,590 --> 00:31:05,740
אומר שמעריך ל
שווא כפי שאתה רוצה אותו.

733
00:31:05,740 --> 00:31:06,790

734
00:31:06,790 --> 00:31:09,880
לא שקר הוא אמת ש
פירוש זה היה לבצע.

735
00:31:09,880 --> 00:31:11,037
האם זה הגיוני?

736
00:31:11,037 --> 00:31:11,620
סטודנט: כן.

737
00:31:11,620 --> 00:31:12,453
מנחה: מדהימה.

738
00:31:12,453 --> 00:31:13,800

739
00:31:13,800 --> 00:31:14,300
אישור.

740
00:31:14,300 --> 00:31:16,330
אז אנחנו פשוט יכולים לחזור
נכון במקרה הזה.

741
00:31:16,330 --> 00:31:20,357
אז עכשיו יש לנו שתי אחרים
מקרים במקרה זה.

742
00:31:20,357 --> 00:31:21,565
מה הם שני מקרים האחרים שלנו?

743
00:31:21,565 --> 00:31:31,610

744
00:31:31,610 --> 00:31:32,900
בואו פשוט נעשה את זה ככה.

745
00:31:32,900 --> 00:31:40,660
אז בואו נתחיל עם דבר אחר
אם ערכים באמצע

746
00:31:40,660 --> 00:31:43,230
הוא פחות מהערך שאנחנו רוצים.

747
00:31:43,230 --> 00:31:47,200

748
00:31:47,200 --> 00:31:52,020
אז הערך שלנו במרכז הוא פחות
מהערך שאנחנו מחפשים.

749
00:31:52,020 --> 00:31:53,765

750
00:31:53,765 --> 00:31:56,720
>> אז איזה גבול אתה
חושב שאנחנו רוצים לעדכן?

751
00:31:56,720 --> 00:31:57,870

752
00:31:57,870 --> 00:31:58,780
עליון או תחתון?

753
00:31:58,780 --> 00:32:01,440

754
00:32:01,440 --> 00:32:01,940
עליון?

755
00:32:01,940 --> 00:32:03,230

756
00:32:03,230 --> 00:32:06,470
אז באיזה צד של המערך
אנחנו הולכים להיות מסתכלים?

757
00:32:06,470 --> 00:32:07,500
>> תלמיד: נמוך.

758
00:32:07,500 --> 00:32:09,750
>> מנחה: אנחנו אנחנו הולכים
להיות מסתכל מהשמאל.

759
00:32:09,750 --> 00:32:11,120
אז אחר אם הערך קטן הוא פחות.

760
00:32:11,120 --> 00:32:14,730
אז הערך האמצעי שלך כאן
הוא פחות ממה שאנחנו רוצים.

761
00:32:14,730 --> 00:32:17,202
אז אנחנו רוצים לקחת
צד ימני של המערך שלנו.

762
00:32:17,202 --> 00:32:18,910
אז אנחנו הולכים ל
לעדכן את הגבול התחתון שלנו.

763
00:32:18,910 --> 00:32:20,210

764
00:32:20,210 --> 00:32:23,020
כך תהיה לנו להקצות מחדש נמוך שלנו.

765
00:32:23,020 --> 00:32:25,221
ומה אתה חושב נמוך צריך להיות?

766
00:32:25,221 --> 00:32:26,304
תלמיד: הערך האמצעי?

767
00:32:26,304 --> 00:32:27,446

768
00:32:27,446 --> 00:32:28,820
מנחה: אז value-- האמצע

769
00:32:28,820 --> 00:32:30,136
תלמיד: פלוס 1.

770
00:32:30,136 --> 00:32:31,010
מנחה: --plus 1.

771
00:32:31,010 --> 00:32:32,300

772
00:32:32,300 --> 00:32:34,380
מישהו יכול להגיד לי למה
יש לנו שתוספת 1?

773
00:32:34,380 --> 00:32:35,730
>> תלמיד: [? אין ערך?]
יותר שווה לזה.

774
00:32:35,730 --> 00:32:36,120
>> מנחה: העכבר.

775
00:32:36,120 --> 00:32:38,661
כי אנחנו כבר יודעים ש
הערך האמצעי שלנו אינו שווה ל

776
00:32:38,661 --> 00:32:42,750
את זה ואנחנו רוצים להוציא את זה
מכל החיפושים שלאחר מכן.

777
00:32:42,750 --> 00:32:46,360
אם אתה שוכח שתוספת 1, זה
יאהב את הלולאה ללא הגבלת זמן.

778
00:32:46,360 --> 00:32:49,620
ואתה פשוט נתפס ב
לולאה אינסופית ואז אתה segfault

779
00:32:49,620 --> 00:32:50,370
והדברים הולכים רעים.

780
00:32:50,370 --> 00:32:54,780
אז תמיד לוודא שאתה לא
כולל ערך שזה עתה

781
00:32:54,780 --> 00:32:55,380
הסתכל.

782
00:32:55,380 --> 00:32:58,530
אז אנחנו דואגים שעם פלוס 1.

783
00:32:58,530 --> 00:33:04,840
>> אז עכשיו יש לנו המצב האחרון שלנו
שבו אני תמיד למען הבטיחות

784
00:33:04,840 --> 00:33:12,664
אתה יכול לבדוק כאן, אם ערך באחר
האמצע הוא גדול מהערך

785
00:33:12,664 --> 00:33:13,163
אנחנו רוצים.

786
00:33:13,163 --> 00:33:16,260

787
00:33:16,260 --> 00:33:20,230
זה אומר שאנחנו רוצים
יד המחצית השמאלית.

788
00:33:20,230 --> 00:33:21,350

789
00:33:21,350 --> 00:33:23,260
אז איזה מהם אנחנו הולכים לעדכן?

790
00:33:23,260 --> 00:33:23,760
עליון.

791
00:33:23,760 --> 00:33:25,470

792
00:33:25,470 --> 00:33:26,970
ומה זה הולך להיות שווה?

793
00:33:26,970 --> 00:33:31,630

794
00:33:31,630 --> 00:33:33,690
התיכון מינוס 1, כי,
כמובן, אנחנו רוצים

795
00:33:33,690 --> 00:33:38,370
כדי לוודא שאנחנו לא
מסתכל על שערך מרכזה שוב.

796
00:33:38,370 --> 00:33:41,830

797
00:33:41,830 --> 00:33:45,110
ולאחר מכן יש לנו את זה.

798
00:33:45,110 --> 00:33:45,610
זֶה הַכֹּל.

799
00:33:45,610 --> 00:33:46,820
זה כל מה שהחיפוש בינארי הוא.

800
00:33:46,820 --> 00:33:48,190
זה לא שרע, נכון?

801
00:33:48,190 --> 00:33:51,590
זה כמו 10 שורות של
קוד עם שטח לבן.

802
00:33:51,590 --> 00:33:57,510
אז מאוד חזק, מאוד שימושי, אתה יהיה
אשתמש בו באחד מpsets מאוחר יותר.

803
00:33:57,510 --> 00:33:59,360
אולי לא במקרה הזה, אבל מאוחר יותר.

804
00:33:59,360 --> 00:34:00,670
אז ללמוד את זה.

805
00:34:00,670 --> 00:34:01,510
אוהב את זה.

806
00:34:01,510 --> 00:34:02,980
זה יתייחס אליך גם.

807
00:34:02,980 --> 00:34:05,370
אז האם מישהו יש לך
שאלות על החיפוש בינארי?

808
00:34:05,370 --> 00:34:06,196
כן.

809
00:34:06,196 --> 00:34:09,840
>> תלמיד: האם זה משנה
אם n שלך הוא או אפילו מוזר?

810
00:34:09,840 --> 00:34:10,750
>> מנחה: מס '

811
00:34:10,750 --> 00:34:18,150
מכיוון שאנו מטילים אותו לאמצע כ
int, זה יהיה פשוט לחתוך אותו.

812
00:34:18,150 --> 00:34:21,600
אז הוא יישאר שלם וזה יהיה
סופו של דבר למיין את הכל.

813
00:34:21,600 --> 00:34:23,909
אז אתה לא צריך לדאוג בקשר לזה.

814
00:34:23,909 --> 00:34:24,580
כולם טובים?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
מדהים.

817
00:34:26,850 --> 00:34:27,919
מגניב.

818
00:34:27,919 --> 00:34:30,836
אז, אתם קיבלת את זה.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
מצגת.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
אז כפי שאנחנו מדברים על, אני יודע
דוד הזכיר זמני ריצת מורכבות.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> אז במקרה הטוב, זה רק
אחד, שאנו מכנים זמן קבוע.

825
00:34:50,340 --> 00:34:51,909
מישהו יכול להגיד לי למה שעשוי להיות?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
איזה סוג של תרחיש יהיה כרוך?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
ממ-הממ.

830
00:34:58,760 --> 00:34:59,926
>> תלמיד: [לא ברור] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
מנחה: אז האמצע להיות
אלמנט ראשון שאנו מגיעים ל, נכון?

833
00:35:03,830 --> 00:35:08,167
אז או מערך של אחד או
כל מה שאנחנו מחפשים רק

834
00:35:08,167 --> 00:35:09,750
קורה להיות טיפה, ממש באמצע.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
אז זה המקרה הכי טוב שלנו.

837
00:35:13,380 --> 00:35:17,540
אתה מקבל בבעיות אמיתיות, כנראה שלא
הולך להגיע [לא ברור] שלעתים קרובות.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
מה לגבי המקרה הגרוע ביותר שלנו?

840
00:35:19,750 --> 00:35:21,270
במקרה הגרוע ביותר שלנו הוא n יומן.

841
00:35:21,270 --> 00:35:25,360
וכי יש לעשות עם כל
כוחות של שני דברים שאני מדבר עליהם.

842
00:35:25,360 --> 00:35:30,930
>> אז במקרה הגרוע ביותר זה אומר
שהיינו צריך לקצוץ את המערך מטה

843
00:35:30,930 --> 00:35:33,270
עד שזה היה אלמנט של אחד.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
אז הייתי צריך לכרות אותו במחצית
כמספר פעמים שאנחנו יכולים להיות.

846
00:35:38,930 --> 00:35:41,430
זו הסיבה שזה n היומן כי
אתה פשוט ממשיך להתחלק על ידי שתי.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
אז הנחות, דברים שאתה
צריך לדעת אם אתה אי פעם

849
00:35:45,830 --> 00:35:48,050
הולך להשתמש בחיפוש בינארי.

850
00:35:48,050 --> 00:35:50,680
האלמנטים שלך חייבים להיות מסודרים.

851
00:35:50,680 --> 00:35:53,890
יש להם להיות מסודר, כי
כי זו הדרך היחידה ש

852
00:35:53,890 --> 00:35:57,060
יכול לדעת אם אתה מסוגל
לזרוק חצי מזה.

853
00:35:57,060 --> 00:36:00,260
>> אם היה לך שקית מעורבבת זה
של מספרים ואתה אומר,

854
00:36:00,260 --> 00:36:05,380
אישור, אני הולך לבדוק את האמצע
מספר והמספר שאני מחפש

855
00:36:05,380 --> 00:36:08,510
הוא פחות מזה, אני פשוט הולך
לזרוק באופן שרירותי את מחצית.

856
00:36:08,510 --> 00:36:11,130
אתה לא יודע אם שלך
מספרים שבמחצית השנייה.

857
00:36:11,130 --> 00:36:12,655
הרשימה שלך צריכה להיות מסודרת.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
כמו גם, זה עשוי להיות
הולך קדימה קצת,

860
00:36:16,560 --> 00:36:18,360
אבל אתה צריך להיות גישה אקראית.

861
00:36:18,360 --> 00:36:21,940
אתה צריך להיות מסוגל רק
ללכת שלאלמנט אמצעי.

862
00:36:21,940 --> 00:36:25,110
אם אתה צריך לעבור
באמצעות משהו ש

863
00:36:25,110 --> 00:36:28,630
או שלוקח צעדים נוספים
כדי להגיע לזה אלמנט אמצע,

864
00:36:28,630 --> 00:36:31,750
זה לא להתחבר n יותר, כי
אתה מוסיף עוד עבודה לתוכה.

865
00:36:31,750 --> 00:36:34,800
וזה יגרום לי קטן
יותר הגיוני בשבועות,

866
00:36:34,800 --> 00:36:37,950
אבל אני פשוט סוג של רציתי להקדים,
לתת לכם מושג על מה

867
00:36:37,950 --> 00:36:38,999
לבוא.

868
00:36:38,999 --> 00:36:40,790
אבל אלה שני
הנחות חשובות

869
00:36:40,790 --> 00:36:44,804
שאתה צריך לרשימת ינארי.

870
00:36:44,804 --> 00:36:45,720
ודא זה מסודרים.

871
00:36:45,720 --> 00:36:47,920
זה אחד הגדול ל
אתם עכשיו.

872
00:36:47,920 --> 00:36:52,170
ועל זה אנחנו יכולים ללכת ל
שאר מיני שלנו.

873
00:36:52,170 --> 00:36:56,444
אז ארבע בועת sorts--,
הכנסה, בחירה, ומיזוג.

874
00:36:56,444 --> 00:36:57,485
הם כולם הסוג של מגניב.

875
00:36:57,485 --> 00:37:02,860
אם אתם מחליטים לקחת CS 124,
תוכל ללמוד על כל מיני מיני.

876
00:37:02,860 --> 00:37:07,575
ואם אתה אוהד xkcd, שם
הוא על קומיקס ממש מגניב

877
00:37:07,575 --> 00:37:11,530
כמו מיני באמת לא יעילים, שבו אני
מאוד ממליץ לך הולך להסתכל.

878
00:37:11,530 --> 00:37:16,170
אחד מהם הוא כמו סוג פאניקה, ש
זה כמו, הו לא, תחזור מערך אקראי.

879
00:37:16,170 --> 00:37:16,991
מערכת כיבוי.

880
00:37:16,991 --> 00:37:17,490
השאר.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
אז הומור חנונית הוא תמיד טוב.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> אז האם מישהו זוכר את סוג
כמו רק רעיון כללי

885
00:37:25,750 --> 00:37:27,810
איך מיון בועות עובד.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
אתה זוכר?

888
00:37:32,155 --> 00:37:32,755
>> סטודנט: כן.

889
00:37:32,755 --> 00:37:33,970
>> מנחה: לכו על זה.

890
00:37:33,970 --> 00:37:38,980
>> תלמיד: אז אתם עוברים ו
אם זה גדול יותר, אז אתה להחליף את שני.

891
00:37:38,980 --> 00:37:39,820
>> מנחה: ממ-הממ.

892
00:37:39,820 --> 00:37:40,564
בדיוק.

893
00:37:40,564 --> 00:37:41,730
אז אתה פשוט לחזר דרך.

894
00:37:41,730 --> 00:37:43,050
אתה בודק את שני מספרים.

895
00:37:43,050 --> 00:37:46,510
אם אחד לפני יותר גדול
יותר מזה שלאחר מכן,

896
00:37:46,510 --> 00:37:50,230
אתה פשוט להחליף אותם כל כך, כי ב
זה כל המספרים גבוהים יותר בדרך

897
00:37:50,230 --> 00:37:54,990
בועה עד לקראת סוף הרשימה
ואת כל המספרים הנמוכים בועה למטה.

898
00:37:54,990 --> 00:37:59,355
>> האם הוא להראות לכם מגניב
אפקט צליל מיון וידאו?

899
00:37:59,355 --> 00:38:00,480
זה סוג של מגניב.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
אז כפי שרוברט פשוט אמר, האלגוריתם
כי אתה פשוט המשך ברשימה,

902
00:38:05,200 --> 00:38:07,930
החלפת הערכים הסמוכים
אם הם לא במטרה.

903
00:38:07,930 --> 00:38:10,975
ואז פשוט ממשיך לחזור
עד שאתה לא עושה חילופים.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
אז לא רע, נכון?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
אז רק שיש לנו דוגמא מהירה כאן.

908
00:38:16,319 --> 00:38:18,360
אז זה הולך למיין
שלהם בעולים סדר.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
לכן, כאשר אנחנו עוברים הראשונים
זמן, אנחנו מסתכלים דרך שמונה

911
00:38:23,470 --> 00:38:26,880
ושישה הם כמובן לא
על מנת, שלהחליף אותם.

912
00:38:26,880 --> 00:38:27,985
>> אז מסתכל על הבא.

913
00:38:27,985 --> 00:38:29,430
שמונה וארבעה לא כדי.

914
00:38:29,430 --> 00:38:30,450
להחליף אותם.

915
00:38:30,450 --> 00:38:32,530
ואז בת שמונה ושני, להחליף אותם.

916
00:38:32,530 --> 00:38:33,470
הנה אנחנו מתחילים.

917
00:38:33,470 --> 00:38:39,519
אז אחרי המסירה הראשונה שלך, לך
יודע שהמספר הגדול ביותר שלך

918
00:38:39,519 --> 00:38:41,810
הולך להיות כל הדרך
בראש כי זה פשוט

919
00:38:41,810 --> 00:38:44,210
הולך להיות כל הזמן
גדול יותר מכל דבר אחר

920
00:38:44,210 --> 00:38:46,810
וזה רק הולך לבועה
את כל הדרך עד הסוף שם.

921
00:38:46,810 --> 00:38:48,226
האם זה הגיוני לכולם?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
מגניב.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> אז אנחנו מסתכלים על המעבר השני שלנו.

926
00:38:53,920 --> 00:38:54,980
שישה וארבעה, מתג.

927
00:38:54,980 --> 00:38:55,920
שישה ושני, מתג.

928
00:38:55,920 --> 00:38:58,700
ועכשיו יש לנו כמה דברים כדי.

929
00:38:58,700 --> 00:39:02,240
אז לכל מסירה ש
לעשות דרך כל הרשימה שלנו,

930
00:39:02,240 --> 00:39:06,320
אנו יודעים כי כמו שמספרים רבים
בסוף יהיה כבר מסודרים.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
אז אנחנו עושים גיחה שלישית,
אשר היא החלפה אחת.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
ולאחר מכן על הרביעי שלנו
עובר, יש לנו אפס חריצים.

935
00:39:15,910 --> 00:39:18,570
וכך אנו יודעים כי
מערך כבר ממוין.

936
00:39:18,570 --> 00:39:20,900
>> וזה גדול
דבר עם מיון בועות.

937
00:39:20,900 --> 00:39:23,720
אנו יודעים כי כאשר אנו
יש אפס עסקות החלף, ש

938
00:39:23,720 --> 00:39:26,497
משמעות הדבר היא כל מה ש
הוא בסדר גמור.

939
00:39:26,497 --> 00:39:27,580
זה סוג של איך אנחנו בודקים.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
אז אנחנו גם הולכים לקוד בועה
סוג שגם הוא לא כל כך נורא.

942
00:39:36,480 --> 00:39:38,120
אף אחד מאלה שרעים.

943
00:39:38,120 --> 00:39:40,210
אני יודע שהם יכולים להיראות קצת מפחידים.

944
00:39:40,210 --> 00:39:42,124
אני יודע מתי אני לקחתי
הכיתה, גם כשאני

945
00:39:42,124 --> 00:39:44,290
לימד את הכיתה ל
בפעם הראשונה בשנה שעברה,

946
00:39:44,290 --> 00:39:46,165
אני היה כמו, איך אני עושה את זה?

947
00:39:46,165 --> 00:39:48,540
זה הגיוני בתאוריה, אבל
איך אנחנו באמת עושים את זה?

948
00:39:48,540 --> 00:39:51,420
וזו הסיבה שאני גם רוצה ללכת
באמצעות קוד שאתם פה.

949
00:39:51,420 --> 00:39:54,915
אז יש לי פסאודו קוד
בשבילכם זה זמן.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
כל כך פשוט לשמור את זה בחשבון כ
אנחנו עומדים להעביר מעל.

952
00:39:58,970 --> 00:40:04,210
אז יש לנו כמה דלפק ש
עוקב אחר ההחלפות שלנו,

953
00:40:04,210 --> 00:40:08,370
כי אנחנו צריכים לוודא ש
שאנחנו בודקים את זה.

954
00:40:08,370 --> 00:40:11,830
ושנעמיק את המערך כל
כפי שאנו רק עשינו עם דוגמא זו.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
אם האלמנט לפני גדול מ
האלמנט אחרי שבו אנחנו נמצאים בבית,

957
00:40:17,325 --> 00:40:20,760
אנו להחליף אותם ואנחנו להגדילנו
הדלפק כי ברגע שאנחנו מחליפים,

958
00:40:20,760 --> 00:40:23,850
אנחנו רוצים לתת לדלפק שלנו יודע את זה.

959
00:40:23,850 --> 00:40:26,247
כל שאלות שם?

960
00:40:26,247 --> 00:40:27,580
משהו נראה מצחיק כאן.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
תלמיד: האם אתה מגדיר את המונה לאפס
בכל פעם שאתה עובר את הלולאה?

963
00:40:32,350 --> 00:40:34,339
אתה לא להמשיך
חזרה לאפס בכל פעם?

964
00:40:34,339 --> 00:40:35,505
מנחה: לא בהכרח.

965
00:40:35,505 --> 00:40:39,710
אז מה שקורה הוא שאנחנו עוברים כאן.

966
00:40:39,710 --> 00:40:43,830
אז לעשות בזמן, לזכור, זה
יתבצע פעם אחת מבלי להיכשל.

967
00:40:43,830 --> 00:40:46,480
אז זה הולך להגדיר את
דלפק שווה לאפס,

968
00:40:46,480 --> 00:40:48,070
אז זה הולך לחזר דרך.

969
00:40:48,070 --> 00:40:50,590
כפי שזה סובב בין,
זה עדכן דלפק.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
כפי שמעדכן דלפק, כאשר זה נעשה,
כאשר הוא הגיע לקצה המערך,

972
00:40:56,900 --> 00:41:00,830
אם הרשימה שלנו לא מסודרים,
מונה עודכן.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> אז הוא בודק את מצבו ואת זה
אומר, בסדר, הוא דלפק גדול מאפס.

975
00:41:07,150 --> 00:41:09,290
אם זה, לעשות את זה שוב.

976
00:41:09,290 --> 00:41:14,340
ברצונך לאפס, כך שכאשר אתה
לעבור, הדלפק שווה לאפס.

977
00:41:14,340 --> 00:41:18,240
אם אתה עובר מיון
מערך, שום דבר לא משתנה,

978
00:41:18,240 --> 00:41:21,355
זה נכשל, ואתה
להחזיר את הרשימה הממוינת.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
האם זה הגיוני?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
תלמיד: זה אולי בקצת.

983
00:41:26,356 --> 00:41:27,147
מנחה: אישור.

984
00:41:27,147 --> 00:41:28,980
אם יש אחר
שאלה שעולה.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
כן.

987
00:41:30,680 --> 00:41:33,760
>> תלמיד: מה היה התפקיד
להיות להעברת האלמנטים?

988
00:41:33,760 --> 00:41:36,900
>> מנחה: אז אנחנו באמת יכולים לכתוב
שאם אנחנו הולכים עכשיו.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
מגניב.

991
00:41:38,300 --> 00:41:42,155
אז בנימה זאת, אליסון הולך
כדי לעבור בחזרה למכשיר.

992
00:41:42,155 --> 00:41:43,080
זה הולך להיות כיף.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
ויש לנו נחמד שלנו
דבר מיון בועות כאן.

995
00:41:47,390 --> 00:41:50,800
אז אני כבר עשיתי רכיבה על אופניים
באמצעות המערך.

996
00:41:50,800 --> 00:41:53,030
יש לנו עסקות החלף שלנו ש
שווים לאפס.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
אז אנחנו רוצים להחליף סמוכים
אלמנטים אם הם מקולקלים.

999
00:41:58,440 --> 00:42:03,020
אז הדבר הראשון שאנחנו צריכים
לעשות הוא לחזר באמצעות המערך שלנו.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> אז איך אתה חושב שיש סיכוי
איטרציות במערך שלנו?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
יש לנו ולאני שווה 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
אנחנו רוצים אני להיות פחות
מ n מינוס 1 מינוס k.

1006
00:42:22,454 --> 00:42:23,870
ואני אסביר, כי בשני.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
אז זה אופטימיזציה כאן איפה,
זוכר איך אמרתי אחרי כל מסירה

1009
00:42:32,830 --> 00:42:36,655
דרכנו המערך
יודע שכל מה שהוא on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> אז אחרי מעבר האחד
יודע שזה מסודרים.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
אחרי שני מעברים שאנו מכירים
שכל זה הוא מסודר.

1014
00:42:50,060 --> 00:42:52,750
לאחר שלושה עוברים
יודע שזה מסודרים.

1015
00:42:52,750 --> 00:42:55,620
אז כמו שאני iterating
באמצעות המערך כאן,

1016
00:42:55,620 --> 00:43:01,090
הוא זה והקפד ללכת רק
דרך מה שאנחנו יודעים הוא לא ממוינים.

1017
00:43:01,090 --> 00:43:01,644
בסדר?

1018
00:43:01,644 --> 00:43:02,810
זה בדיוק אופטימיזציה.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
אתה יכול לכתוב את זה בתמימות רק
iterating דרך כל דבר,

1021
00:43:08,210 --> 00:43:09,970
זה ייקח זמן רב יותר רק.

1022
00:43:09,970 --> 00:43:12,470
עם ארבע לולאה זה זה
רק אופטימיזציה נחמדה

1023
00:43:12,470 --> 00:43:18,460
כי אנחנו יודעים שאחרי כל מלאים
איטרציה באמצעות המערך כאן,

1024
00:43:18,460 --> 00:43:24,050
כמו כל לולאה מלאה כאן, אנחנו יודעים
שאחד יותר מאלמנטים אלו

1025
00:43:24,050 --> 00:43:25,760
ימויין בסוף.

1026
00:43:25,760 --> 00:43:28,294
>> אז אנחנו לא צריכים לדאוג לאלה.

1027
00:43:28,294 --> 00:43:29,710
האם זה הגיוני לכולם?

1028
00:43:29,710 --> 00:43:30,950
את הטריק הקטן הזה מגניב?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
אז במקרה זה, אם
אנחנו iterating דרך,

1031
00:43:37,270 --> 00:43:50,590
אנחנו יודעים שאנחנו רוצים לבדוק אם
n המערך וn בתוספת 1 הוא בסדר.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
אישור.

1034
00:43:53,559 --> 00:43:54,600
אז הנה פסאודו הקוד.

1035
00:43:54,600 --> 00:43:57,540
אנחנו רוצים לבדוק אם n מערך
וn בתוספת 1 הוא בסדר.

1036
00:43:57,540 --> 00:43:59,520
אז מה ביכולתנו שם?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
זה הולך להיות קצת מותנה.

1039
00:44:03,120 --> 00:44:04,220
זה יהיה אם.

1040
00:44:04,220 --> 00:44:07,066
>> תלמיד: אם n המערך הוא
פחות ממערך n בתוספת 1.

1041
00:44:07,066 --> 00:44:07,816
מנחה: ממ-הממ.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
ובכן, פחות או יותר מ.

1044
00:44:10,699 --> 00:44:11,615
תלמיד: גדול מ.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
אז אנחנו רוצים להחליף אותם.

1047
00:44:17,620 --> 00:44:18,570
בדיוק.

1048
00:44:18,570 --> 00:44:23,570
אז עכשיו אנחנו מקבלים לתוך מה
מנגנון להעברתם?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
וכך עברו את בקצרה,
סוג של פונקצית swap בשבוע שעבר.

1051
00:44:28,137 --> 00:44:29,595
מישהו זוכר איך זה עובד?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
אז אנחנו לא יכולים פשוט להקצות מחדש אותם, נכון?

1054
00:44:34,950 --> 00:44:36,640
כי אחד מהם ילך לאיבוד.

1055
00:44:36,640 --> 00:44:41,696
אם אמרו שווה ל- B ואז B
שווה, כל שניהם פתאומיים

1056
00:44:41,696 --> 00:44:43,150
הם פשוט שווים ל- B

1057
00:44:43,150 --> 00:44:45,720
>> אז מה שאנחנו צריכים לעשות הם
יש לי משתנה זמני זה

1058
00:44:45,720 --> 00:44:49,055
הולך להחזיק משלנו בזמן
אנחנו בתהליך של החלפה.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
אז מה יש לנו הוא שנהיה לנו כמה int
זמני הוא שווה to-- אתה יכול להקצות אותו

1061
00:44:56,464 --> 00:44:59,130
לאיזה אחד אתה רוצה, רק
הקפד לעקוב אחר it--

1062
00:44:59,130 --> 00:45:01,840
כך במקרה זה, אני הולך
להקצות אותו למערך n בתוספת 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
אז זה הולך להחזיק כל מה ש
ערך הוא שבבלוק השני

1065
00:45:07,674 --> 00:45:08,590
שאנחנו מסתכלים.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> ואז אנחנו יכולים לעשות הוא שאנחנו יכולים ללכת
קדימה ומערך להקצות מחדש n בתוספת 1,

1068
00:45:13,240 --> 00:45:14,990
כי אנחנו יודעים שאנחנו
יש ערך שמאוחסן.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
זהו גם אחד הגדול
things-- אני לא יודע אם מישהו מכם

1071
00:45:19,270 --> 00:45:23,780
היו בעיות שבו אם אתה עובר שני
שורות קוד פתאום דברים עבדו.

1072
00:45:23,780 --> 00:45:25,880
להזמין חשוב מאוד בCS.

1073
00:45:25,880 --> 00:45:29,450
כדי לוודא שאתה שרטטת
דברים אם ניתן לעשות

1074
00:45:29,450 --> 00:45:31,230
כלמה שבאמת קורה.

1075
00:45:31,230 --> 00:45:34,256
אז עכשיו אנחנו הולכים ל
להקצות מחדש n מערך פלוס 1,

1076
00:45:34,256 --> 00:45:36,005
כי אנחנו יודעים שאנחנו
יש ערך שמאוחסן.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> ואנחנו יכולים להקצות את זה למערך
n או במקרה מערך זה אני.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
יותר מדי משתנה.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
אישור.

1083
00:45:55,470 --> 00:46:01,500
מערך אז עכשיו מחדש אני
בתוספת 1 שווה מה שיש במערך i.

1084
00:46:01,500 --> 00:46:08,240
ועכשיו אנחנו יכולים לחזור ו
להקצות מערך i למה?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
כל אחד?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> תלמיד: 10.

1089
00:46:14,010 --> 00:46:14,680
>> מנחה: 10.

1090
00:46:14,680 --> 00:46:15,180
בדיוק.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
ועוד דבר אחד אחרון.

1093
00:46:18,640 --> 00:46:21,840
אם יש לנו החלפנו את זה עכשיו,
מה שאנחנו צריכים לעשות?

1094
00:46:21,840 --> 00:46:23,740
מה הדבר אחד
זה הולך לספר לנו

1095
00:46:23,740 --> 00:46:27,542
אם אי פעם לסיים תכנית זו?

1096
00:46:27,542 --> 00:46:29,250
מה אומר לנו שאנו
יש רשימה ממוינת?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
אם אנחנו לא לבצע כל עסקות החלף, נכון?

1099
00:46:33,750 --> 00:46:36,900
אם חילופים שווים ל
אפס בסוף זה.

1100
00:46:36,900 --> 00:46:42,975
אז בכל פעם שאתה מבצע החלפה, כפי שאנו
רק עשיתי כאן, אנחנו רוצים לעדכן את חילופים.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
ואני יודע שלא היה
שאלה קודם לכן על שאתה יכול

1103
00:46:47,210 --> 00:46:49,689
להשתמש אפס או אחד במקום
של אמת או שקר.

1104
00:46:49,689 --> 00:46:50,980
וזה מה שזה עושה כאן.

1105
00:46:50,980 --> 00:46:52,750
אז זה אומר שאם לא חילופי.

1106
00:46:52,750 --> 00:47:01,310
אז אם חילופים הוא אפס, שis-- תמיד
לקבל האמיתות שלי וfalses שלי מעורבות.

1107
00:47:01,310 --> 00:47:03,960
אנחנו רוצים אותנו להעריך
לנכון, וזה לא.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
אז אם זה אפס, אז זה שקר.

1110
00:47:09,630 --> 00:47:12,560
אם אתה שולל אותו עם
[? לדפוק?] הוא הופך להיות אמיתי.

1111
00:47:12,560 --> 00:47:13,975
אז קו זה מבצע.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> אמיתות ושקר ו
אפסים ואחדים לקבל מטורפים.

1114
00:47:17,370 --> 00:47:20,690
רק אם אתה הולך לאט
דרכו זה יהיה הגיוני.

1115
00:47:20,690 --> 00:47:23,320
אבל זה מה שזה קטן
קצת קוד כאן עושה.

1116
00:47:23,320 --> 00:47:26,490
אז זה בודק
אנחנו עשינו כל עסקות החלף.

1117
00:47:26,490 --> 00:47:30,054
אז אם זה כל דבר חוץ מזה
אפס, זה הולך להיות כוזב

1118
00:47:30,054 --> 00:47:31,970
וכל העניין הוא
הולך לבצע שוב.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
מגניב?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> תלמיד: מה הפסקה עושה?

1123
00:47:36,000 --> 00:47:38,990
>> מנחה: לשבור רק
שובר אותך מחוץ לעניינים.

1124
00:47:38,990 --> 00:47:41,570
אז במקרה הזה זה היה
בדיוק כמו בסופו של התכנית

1125
00:47:41,570 --> 00:47:43,828
ואתה פשוט היית
יש לך רשימה הממוינת.

1126
00:47:43,828 --> 00:47:44,536
תלמיד: מדהים.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
מנחה: אני מצטער?

1129
00:47:49,010 --> 00:47:52,110
תלמיד: בגלל שאנחנו בעבר
השתמש בכתב 1 על כתב אפס

1130
00:47:52,110 --> 00:47:54,170
להציג שאם
זה יעבוד או לא.

1131
00:47:54,170 --> 00:47:54,878
>> מנחה: כן.

1132
00:47:54,878 --> 00:47:56,410
כך שאתה יכול לחזור אפס או 1.

1133
00:47:56,410 --> 00:47:58,950
במקרה זה, כי אנחנו לא ממש
עושה שום דבר עם הפונקציה,

1134
00:47:58,950 --> 00:48:00,150
אנחנו רק רוצים את זה כדי לשבור.

1135
00:48:00,150 --> 00:48:02,680
באמת לא אכפת לנו על זה.

1136
00:48:02,680 --> 00:48:06,960
הבלם טוב גם אם
הוא משמש לפריצה

1137
00:48:06,960 --> 00:48:10,710
של ארבע לולאות או תנאים ש
אתה לא רוצה לשמור על ביצוע.

1138
00:48:10,710 --> 00:48:12,110
זה פשוט לוקח אותך מהם.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
זה קצת של דבר ניואנס.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
אני מרגיש שיש שם
הרבה נפנוף יד,

1143
00:48:18,445 --> 00:48:19,740
כמו שאתה תלמד על זה בקרוב.

1144
00:48:19,740 --> 00:48:20,955
>> אבל תוכל ללמוד על זה בקרוב.

1145
00:48:20,955 --> 00:48:21,500
אני מבטיח.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
אישור.

1148
00:48:23,170 --> 00:48:24,840
אז האם כולם מקבלים מיון בועות?

1149
00:48:24,840 --> 00:48:25,550
לא רע.

1150
00:48:25,550 --> 00:48:31,910
איטרציות ב, דברים החלפת שימוש ב
משתנה זמני, וכולנו מוכנים לשם?

1151
00:48:31,910 --> 00:48:32,960
מגניב.

1152
00:48:32,960 --> 00:48:34,080
מדהים.

1153
00:48:34,080 --> 00:48:34,807
אישור.

1154
00:48:34,807 --> 00:48:35,765
חזור ל- PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
כל שאלות באופן כללי
על אלה עד כה?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
מגניב.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
ממ-הממ.

1161
00:48:43,695 --> 00:48:45,279
>> תלמיד: [לא ברור] int ראשי בדרך כלל.

1162
00:48:45,279 --> 00:48:46,695
האם יש לך כדי לקבל אותו לזה?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> מנחה: אז אנחנו פשוט מחפשים
רק באלגוריתם המיון בפועל.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
אם היה לו שאתה בתוך
כמו תכנית גדולה יותר,

1167
00:48:56,350 --> 00:48:57,891
היית במקום עיקרי int.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
תלוי איפה אתה
להשתמש באלגוריתם זה,

1170
00:49:02,880 --> 00:49:05,860
זה יהיה לקבוע מה
הוחזר על ידו.

1171
00:49:05,860 --> 00:49:09,960
אבל למקרה שלנו, אנחנו בהחלט
מסתכל איך עושה את זה בפועל

1172
00:49:09,960 --> 00:49:11,300
לחזר באמצעות מערך.

1173
00:49:11,300 --> 00:49:12,570
אז אנחנו לא לדאוג בקשר לזה.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> אז אנחנו מדברים על המקרה הטוב ביותר ו
התרחישים הגרועים ביותר לחיפוש בינארי.

1176
00:49:19,830 --> 00:49:22,470
אז זה גם חשוב לעשות
כי לכל אחד מהמינים שלנו.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
אז מה אתה חושב שהוא הגרוע ביותר
מקרה זמן ריצה של מיון בועות?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
אתם זוכרים?

1181
00:49:30,700 --> 00:49:31,784
>> תלמיד: N מינוס 1.

1182
00:49:31,784 --> 00:49:32,700
מנחה: N מינוס 1.

1183
00:49:32,700 --> 00:49:35,070
אז זה אומר שיש
n מינוס 1 השוואות.

1184
00:49:35,070 --> 00:49:40,060
אז דבר אחד הוא להבין
כי בגרסה הראשונה,

1185
00:49:40,060 --> 00:49:43,360
אנו עוברים, אנו משווים
two-- אלה אז זה 1.

1186
00:49:43,360 --> 00:49:46,685
שני אלה, שלוש, ארבעה.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
אז אחרי איטרציה האחת
כבר יש ארבע השוואות.

1189
00:49:55,050 --> 00:49:58,230
כאשר על זמן ריצה וn אני מדבר.

1190
00:49:58,230 --> 00:50:04,680
N מייצג את מספר ההשוואות
כפונקציה של מרכיבים כמה

1191
00:50:04,680 --> 00:50:05,570
יש לנו.

1192
00:50:05,570 --> 00:50:06,430
בסדר?

1193
00:50:06,430 --> 00:50:08,860
>> אז אנחנו עוברים, יש לנו ארבעה.

1194
00:50:08,860 --> 00:50:11,780
בפעם הבאה שאתה יודע שאנחנו לא
צריך לטפל בזה.

1195
00:50:11,780 --> 00:50:15,140
אנו משווים את שני אלה,
שני אלה, שני אלה,

1196
00:50:15,140 --> 00:50:20,050
ואם לא היה לנו כי אופטימיזציה
עם ארבע הלולאה שכתבתי,

1197
00:50:20,050 --> 00:50:22,750
היית להשוות בכאן בכל מקרה.

1198
00:50:22,750 --> 00:50:26,170
אז היית צריך
לרוץ דרך המערך

1199
00:50:26,170 --> 00:50:34,380
ולעשות השוואות n n
פעמים, כי בכולנו זמן

1200
00:50:34,380 --> 00:50:36,670
לרוץ דרכו אנחנו פחות דבר אחד.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> ובכל פעם שאנחנו מריצים דרך
המערך, אנחנו עושים השוואות n.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
אז זמן הריצה שלנו לכך היא
למעשה n בריבוע, ש

1205
00:50:46,330 --> 00:50:48,400
הרבה יותר גרוע בנו
יומן הסוף בגלל ש

1206
00:50:48,400 --> 00:50:51,965
משמעות הוא שאם היו לנו ארבעה
מיליארדים אלמנטים, זה

1207
00:50:51,965 --> 00:50:55,260
הולך לקחת לנו ארבעה מליארד
בריבוע במקום 32.

1208
00:50:55,260 --> 00:51:01,240
אז לא זמן הריצה הטובה ביותר,
אבל עבור כמה דברים,

1209
00:51:01,240 --> 00:51:04,610
אתה יודע, אם אתה נמצא ב
טווח מסוים של אלמנטים

1210
00:51:04,610 --> 00:51:06,540
מיון בועות יכול להיות בסדר להשתמש.

1211
00:51:06,540 --> 00:51:07,530
>> אישור.

1212
00:51:07,530 --> 00:51:12,290
אז עכשיו מה שקורה זמן הריצה הטובה ביותר?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
תלמיד: אפס?

1215
00:51:14,940 --> 00:51:16,420
או 1?

1216
00:51:16,420 --> 00:51:18,140
>> מנחה: אז 1 היית
להיות השוואה אחת.

1217
00:51:18,140 --> 00:51:19,114
תקין.

1218
00:51:19,114 --> 00:51:20,002
>> תלמיד: N מינוס 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> מנחה: אז, כן.

1221
00:51:22,320 --> 00:51:22,990
אז n מינוס 1.

1222
00:51:22,990 --> 00:51:26,510
בכל פעם שיש לך מושג כמו n
מינוס 1, אנחנו נוטים פשוט שחררו אותו

1223
00:51:26,510 --> 00:51:31,680
ואנחנו רק אומרים n כי יש לך
כדי להשוות כל אחד מthese-- כל זוג.

1224
00:51:31,680 --> 00:51:36,470
כך שזה יהיה n מינוס 1, שבו אנו
אנחנו רק רוצים לומר הוא כ n.

1225
00:51:36,470 --> 00:51:39,280
עם זמן ריצה כאשר יש לך עסק,
הכל בקירוב.

1226
00:51:39,280 --> 00:51:43,860
כל עוד המעריך הוא
נכון, אתה די טוב.

1227
00:51:43,860 --> 00:51:45,700
>> זה איך אנחנו מתמודדים עם זה.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
כך שהמקרה הטוב הוא n, ש
משמעות הדבר היא שהרשימה כבר מסודרים,

1230
00:51:51,780 --> 00:51:54,320
וכל מה שאנחנו צריכים לעשות זה לרוץ דרך
ולבדוק שזה מסודרים.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
מגניב.

1233
00:51:56,855 --> 00:51:57,355
בְּסֵדֶר.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
אז כפי שאתם רואים כאן, אנחנו
רק צריכים כמה גרפים יותר.

1236
00:52:01,920 --> 00:52:02,660
אז n בריבוע.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
כיף.

1239
00:52:05,120 --> 00:52:09,730
הרבה יותר גרוע מn כפי שאנו רואים, ו
הרבה, הרבה יותר גרוע מ2n היומן.

1240
00:52:09,730 --> 00:52:12,060
ואז אתה גם מקבל לתוך יומני יומן.

1241
00:52:12,060 --> 00:52:18,020
ואתה לקחת את 124, אתה נכנסת ל
כמו כוכב יומן, שהוא כמו משוגע.

1242
00:52:18,020 --> 00:52:20,172
אז אם אתה מעוניין,
יומן בדיקת כוכב.

1243
00:52:20,172 --> 00:52:20,880
זה סוג של כיף.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
אז יש לנו התרשים הגדול הזה.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
, רק ראש בראש זה
תרשים נפלא שיש

1248
00:52:28,720 --> 00:52:31,350
לאמצע הקדנציה שלך, כי אנחנו
עוד לשאול אותך המדלל אלה.

1249
00:52:31,350 --> 00:52:36,090
אז פשוט ראש בראש, יש לי זה עליך
אמצע הקדנציה בגיליון לרמות נחמד שלך

1250
00:52:36,090 --> 00:52:36,616
יש.

1251
00:52:36,616 --> 00:52:37,990
אז אנחנו פשוט הסתכלנו על מיון בועות.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
במקרה הגרוע ביותר, n בריבוע, מקרה טוב, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
ואנחנו הולכים להסתכל על אחרים.

1256
00:52:44,950 --> 00:52:47,940
>> וכפי שאתם יכולים לראות, רק
אחד שבאמת עושה טוב

1257
00:52:47,940 --> 00:52:50,910
הוא סוג של מיזוג, אשר נגיע למה.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
אז אנחנו הולכים ללכת ל
הסוג הבא here-- בחירה.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
מישהו זוכר איך
מבחר עבד מין?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
לכו על זה.

1264
00:53:05,700 --> 00:53:08,210
>> תלמיד: בעיקרון לעבור
סדר וליצור רשימה חדשה.

1265
00:53:08,210 --> 00:53:11,001
ובדיוק כפי שאתה שם את המרכיבים
ב, לשים אותם במקום הנכון

1266
00:53:11,001 --> 00:53:11,750
ברשימה החדשה.

1267
00:53:11,750 --> 00:53:14,040
>> מנחה: אז שצלילים
יותר כמו סוג ההכנסה.

1268
00:53:14,040 --> 00:53:15,040
אבל אתה ממש קרוב.

1269
00:53:15,040 --> 00:53:15,915
הם דומים מאוד.

1270
00:53:15,915 --> 00:53:17,440
גם אני מקבל אותם מעורב לעתים.

1271
00:53:17,440 --> 00:53:18,981
לפני סעיף זה הייתי כמו, לחכות.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
אישור.

1274
00:53:20,630 --> 00:53:24,141
אז מה אתה רוצה
לעשות הוא מיון בחירה,

1275
00:53:24,141 --> 00:53:25,890
הדרך שאתה יכול לחשוב
על זה ועל הדרך

1276
00:53:25,890 --> 00:53:30,140
אני מוודא שאני משתדל לא להיכנס
לערבב אותם, זה עובר

1277
00:53:30,140 --> 00:53:33,280
והוא בוחר
המספר הקטן ביותר ואת זה

1278
00:53:33,280 --> 00:53:36,070
מכניס כי בתחילת הרשימה שלך.

1279
00:53:36,070 --> 00:53:37,730
זה מחליף אותו עם זה מקום ראשון.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
למעשה יש להם דוגמא בשבילי.

1282
00:53:45,370 --> 00:53:46,540
מדהים.

1283
00:53:46,540 --> 00:53:50,130
אז רק דרך לחשוב על בחירת it--
סוג, בחר את הערך הקטן ביותר.

1284
00:53:50,130 --> 00:53:51,940
ואנחנו הולכים
לרוץ דרך דוגמא

1285
00:53:51,940 --> 00:53:55,320
כי אני חושב שאעזור לי כי
אני חושב חזותיים תמיד לעזור.

1286
00:53:55,320 --> 00:53:58,510
אז אנחנו מתחילים עם משהו
כי הוא לא ממוינים לחלוטין.

1287
00:53:58,510 --> 00:54:00,730
האדום יהיה ממוין,
ירוק ימויין.

1288
00:54:00,730 --> 00:54:02,190
כל זה יהיה הגיוני בשני.

1289
00:54:02,190 --> 00:54:08,950
>> אז אנחנו עוברים ושנעמיק
מההתחלה ועד הסוף.

1290
00:54:08,950 --> 00:54:12,320
ואנחנו אומרים, בסדר, 2 הוא
המספר הקטן ביותר שלנו.

1291
00:54:12,320 --> 00:54:15,680
אז אנחנו הולכים לקחת 2 ואנחנו הולכים
כדי להעביר אותה מול המערך שלנו

1292
00:54:15,680 --> 00:54:17,734
כי זה
המספר הקטן ביותר שיש לנו.

1293
00:54:17,734 --> 00:54:19,150
אז זה מה שזה עושה כאן.

1294
00:54:19,150 --> 00:54:20,820
זה רק הולך להחליף את שני אלה.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
אז עכשיו יש לנו מסודרים
חלק וחלק לא ממוינת.

1297
00:54:25,450 --> 00:54:27,810
ומה טוב לזכור
על מיון בחירה

1298
00:54:27,810 --> 00:54:30,690
הוא שאנחנו בחירה היחידה
מחלק לא ממוינים.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> חלק ממוין אתה פשוט להשאיר לבד.

1301
00:54:34,527 --> 00:54:35,660
ממ-הממ?

1302
00:54:35,660 --> 00:54:38,452
>> תלמיד: איך הוא יודע מה הוא
הקטן ביותר ללא השוואתה

1303
00:54:38,452 --> 00:54:39,868
לכל ערך אחר במערך.

1304
00:54:39,868 --> 00:54:41,250
מנחה: זה להשוות את זה.

1305
00:54:41,250 --> 00:54:42,041
אנחנו אוהבים לדלג עליה.

1306
00:54:42,041 --> 00:54:43,850
זה רק כללי כללי.

1307
00:54:43,850 --> 00:54:44,831
כן.

1308
00:54:44,831 --> 00:54:47,205
כאשר אנו כותבים את הקוד אני
בטוח שאתה אהיה מרוצה יותר.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
אבל לך לאחסן את זה ראשון
אלמנט כקטן ביותר.

1311
00:54:53,030 --> 00:54:56,110
אתה משווה את ואתה
אומר, בסדר, זה קטן יותר?

1312
00:54:56,110 --> 00:54:56,660
כן.

1313
00:54:56,660 --> 00:54:57,460
שמור את זה.

1314
00:54:57,460 --> 00:54:58,640
הנה הוא קטן יותר?

1315
00:54:58,640 --> 00:54:59,660
לא?

1316
00:54:59,660 --> 00:55:02,510
>> זה הקטן ביותר שלך,
להקצות מחדש אותו לערך שלך.

1317
00:55:02,510 --> 00:55:06,340
ואתה תהיה הרבה יותר מאושר
כאשר אנו עוברים את הקוד.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
אז אנחנו עוברים, אנחנו להחליף אותו, אז
אנחנו מסתכלים על חלק לא ממוינים זה.

1320
00:55:13,970 --> 00:55:15,810
אז אנחנו הולכים כדי לבחור שלוש מתוך.

1321
00:55:15,810 --> 00:55:18,890
אנחנו הולכים לשים על זה ב
סוף החלק ממוין שלנו.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
ואנחנו פשוט הולכים להמשיך לעשות
ש, עושה את זה, ועושה את זה.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
אז זה הסוג שלנו של פסאודו קוד כאן.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
אנחנו לקודד אותו כאן בשניים.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
אבל רק משהו ללכת
דרך ברמה גבוהה.

1330
00:55:37,270 --> 00:55:40,275
אתה הולך לעבור מ
אני שווה 0 עד n מינוס 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
זה ייעול נוסף.

1333
00:55:43,530 --> 00:55:45,020
אל תדאגו יותר מדי על זה.

1334
00:55:45,020 --> 00:55:46,620
אז כפי שאתם אומרים.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
כיעקב אמר, איך אנחנו
לעקוב אחר מה הוא המינימום שלנו?

1337
00:55:54,406 --> 00:55:55,030
איך אנחנו יודעים?

1338
00:55:55,030 --> 00:55:57,060
אנחנו צריכים להשוות
כל מה שברשימה שלנו.

1339
00:55:57,060 --> 00:55:59,600
>> אז מינימום שווה i.

1340
00:55:59,600 --> 00:56:03,870
זה רק אומר שבמקרה זה
המדד של הערך המינימאלי שלנו.

1341
00:56:03,870 --> 00:56:07,660
אז זה הולך לחזר דרך
וזה הולך מj שווה i בתוספת 1.

1342
00:56:07,660 --> 00:56:11,420
אז אנחנו כבר יודעים ש
זה האלמנט הראשון שלנו.

1343
00:56:11,420 --> 00:56:13,240
אנחנו לא צריכים להשוות את זה לעצמו.

1344
00:56:13,240 --> 00:56:16,970
אז אנחנו מתחילים להשוות אותו למשנהו
אחד וזו הסיבה שזה אני בתוספת 1 לn

1345
00:56:16,970 --> 00:56:20,110
מינוס 1, שהוא
קצה המערך שם.

1346
00:56:20,110 --> 00:56:25,090
ואנחנו אומרים שאם מערך ב
j הוא פחות מ דקות מערך,

1347
00:56:25,090 --> 00:56:29,200
אז להקצות מחדש בי
המדדים המינימליים שלנו הוא.

1348
00:56:29,200 --> 00:56:37,470
>> ואם דקות לא שווה לי, כ
שבבו היינו חוזר לכאן.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
אז כמו בעת שעשינו את זה ראשון.

1351
00:56:41,790 --> 00:56:49,310
במקרה זה, זה היה מתחיל ב
אפס, זה יהיה סופו של דבר שני.

1352
00:56:49,310 --> 00:56:53,010
אז דקות לא הייתם שווה לי בסופו של הדבר.

1353
00:56:53,010 --> 00:56:55,720
ש מאפשר לי יודע ש
אנחנו צריכים להחליף אותם.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
אני מרגיש כמו דוגמא מוחשית
יעזור הרבה יותר מזה.

1356
00:57:00,470 --> 00:57:04,970
אז אני לקודד את זה איתכם
עכשיו ואני חושב שזה יהיה טוב יותר.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> מיני נוטים לעבוד ככה שב
זה בדרך כלל טוב יותר, רק כדי לראות אותם.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
אז מה שאנחנו רוצים לעשות הוא
אנחנו רוצים ראשון הקטנים ביותר

1361
00:57:17,280 --> 00:57:19,890
אלמנט בעמדתה במערך.

1362
00:57:19,890 --> 00:57:21,280
בדיוק מה שיעקב אמר.

1363
00:57:21,280 --> 00:57:23,090
אתה צריך לאחסן, שאיכשהו.

1364
00:57:23,090 --> 00:57:25,900
אז אנחנו הולכים להתחיל כאן
iterating על המערך.

1365
00:57:25,900 --> 00:57:28,970
אנחנו הולכים להגיד שזה שלנו
ראשון, רק כדי להתחיל עם.

1366
00:57:28,970 --> 00:57:38,308
אז אנחנו הולכים להיות int
הקטן ביותר הוא שווה למערך בi.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> אז דבר אחד שם לב, כל
לולאת זמן זה מבצע,

1369
00:57:45,050 --> 00:57:48,550
אנחנו מתחילים צעד אחד קדימה לאורך.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
כאשר אנחנו מתחילים להסתכל על זה אחד.

1372
00:57:57,440 --> 00:58:00,840
בפעם הבאה שנעמיק דרך,
אנחנו מתחילים בזה

1373
00:58:00,840 --> 00:58:02,680
והקצאה את הערך הקטן ביותר שלנו.

1374
00:58:02,680 --> 00:58:10,450
אז זה מאוד דומה למיון בועות
שבו אנחנו יודעים שאחרי מעבר אחד,

1375
00:58:10,450 --> 00:58:11,700
המרכיב האחרון הוא מסודרים.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
עם מיון בחירה,
זה בדיוק ההפך.

1378
00:58:15,120 --> 00:58:18,950
>> בכל מסירה, אנו יודעים ש
הראשון הוא מסודר.

1379
00:58:18,950 --> 00:58:21,360
לאחר המעבר שני,
שנייה אחת ימויין.

1380
00:58:21,360 --> 00:58:26,470
וכפי שראית בדוגמאות השקופיות,
החלק מסודרים שלנו רק הולך וגובר.

1381
00:58:26,470 --> 00:58:34,020
זאת על ידי הגדרה הקטנה ביותר שלנו
למערכים אני, כל מה שהוא עושה

1382
00:58:34,020 --> 00:58:37,340
הוא ההצרה מה
אנחנו מסתכלים על כך כ

1383
00:58:37,340 --> 00:58:40,164
כדי למזער את המספר
השוואות שאנחנו עושים.

1384
00:58:40,164 --> 00:58:41,770
האם זה הגיוני לכולם?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
האם אתה צריך אותי כדי לרוץ דרך ש
שוב איטי יותר או במילים אחרות?

1387
00:58:46,380 --> 00:58:47,180
אני שמח.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
אישור.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> אז אנחנו אחסון
ערך בנקודה זו,

1392
00:58:55,540 --> 00:58:57,840
אבל אנחנו גם רוצים לאחסן את המדד.

1393
00:58:57,840 --> 00:59:01,010
אז אנחנו הולכים לחנות
עמדה של קטן

1394
00:59:01,010 --> 00:59:02,770
אחד, שרק הולך להיות אני.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
אז עכשיו יעקב הוא מרוצה.

1397
00:59:05,440 --> 00:59:06,870
יש לנו דברים מאוחסנים.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
ועכשיו אנחנו צריכים להסתכל דרך
החלק ממוין של המערך.

1400
00:59:11,870 --> 00:59:18,170
אז במקרה הזה זה
יהיה ממוין שלנו.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
זה אני.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
אישור.

1405
00:59:26,210 --> 00:59:30,040
>> אז מה אנחנו הולכים לעשות
הולך להיות ללולאה.

1406
00:59:30,040 --> 00:59:32,066
בכל פעם שאתה צריך
לחזר באמצעות מערך,

1407
00:59:32,066 --> 00:59:33,440
המוח שלך יכול ללכת ללולאה.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
אז לכמה k int
equals-- מה שאנחנו חושבים

1410
00:59:38,090 --> 00:59:39,700
k הולך שווה להתחיל?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
זה מה שאנחנו מוגדרים כקטנים ביותר שלנו
ערך ואנחנו רוצים להשוות אותו.

1413
00:59:44,766 --> 00:59:47,090
מה אנחנו רוצים להשוות את זה ל?

1414
00:59:47,090 --> 00:59:48,730
זה הולך להיות הבא זה, נכון?

1415
00:59:48,730 --> 00:59:53,200
ולכן אנחנו רוצים k להיות מאותחלים
כדי שאני ועוד 1 כדי להתחיל.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> ואנחנו רוצים k במקרה זה אנו
כבר גודל מאוחסן כאן,

1418
01:00:02,800 --> 01:00:03,930
כדי שנוכל פשוט להשתמש בגודל.

1419
01:00:03,930 --> 01:00:06,240
גודל להיות הגודל של המערך.

1420
01:00:06,240 --> 01:00:09,620
ואנחנו רק רוצים
לעדכן את k ידי אחד בכל פעם.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
מגניב.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
אז עכשיו אנחנו צריכים למצוא
האלמנט הקטן ביותר כאן.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
אז אם אנחנו לחזר דרך, אנחנו
רוצה לומר, אם מערך בk

1427
01:00:31,380 --> 01:00:37,080
הוא פחות מ value-- הקטן ביותר שלנו
זה מקום שבי שאנחנו בעצם

1428
01:00:37,080 --> 01:00:42,950
שמירה על המסלול של מה
here-- הקטן ביותר

1429
01:00:42,950 --> 01:00:47,740
אז אנחנו רוצים להקצות מחדש
מהו ערך הקטן ביותר שלנו.

1430
01:00:47,740 --> 01:00:50,645
>> משמעות דבר היא כי, הו, אנחנו
iterating דרך כאן.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
לא משנה מה הערך הוא כאן הוא
לא הדבר הקטן ביותר שלנו.

1433
01:00:53,740 --> 01:00:54,448
אנחנו לא רוצים את זה.

1434
01:00:54,448 --> 01:00:56,100
אנחנו רוצים להקצות מחדש אותו.

1435
01:00:56,100 --> 01:01:02,050
אז אם אנחנו reassigning זה, מה לעשות
אתה חושב שאולי יהיה בקוד זה כאן?

1436
01:01:02,050 --> 01:01:04,160
אנחנו רוצים להקצות מחדש
הקטן ביותר ומיקום.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
אז מה הוא הקטן ביותר עכשיו?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
תלמיד: k מערך.

1441
01:01:09,130 --> 01:01:09,963
מנחה: k מערך.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
ומה היא עמדה עכשיו?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
מה המדדים
הערך הקטן ביותר שלנו?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
זה פשוט k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
אז k מערך, k, הם מתאימים.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
לכן אנחנו רוצים להקצות מחדש ש.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
ואז אחרי שמצאנו הקטן ביותר שלנו,
כך בסוף זה ללולאה

1454
01:01:39,950 --> 01:01:45,100
כאן מצאנו מה הקטן ביותר שלנו
הערך הוא, אז אנחנו פשוט להחליף אותו.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
במקרה זה, כמו לומר שלנו
הערך הקטן ביותר הוא כאן.

1457
01:01:50,816 --> 01:01:51,940
זהו הערך הקטן ביותר שלנו.

1458
01:01:51,940 --> 01:01:57,690
>> אנחנו רק רוצים להחליף אותו כאן, שהוא
מה שפונקצית swap בתחתית

1459
01:01:57,690 --> 01:02:01,270
עשה, שאנחנו פשוט כתבנו את
יחד לפני כמה דקות.

1460
01:02:01,270 --> 01:02:02,775
אז זה צריך להיראות מוכר.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
ואז זה יהיה פשוט לחזר
דרך עד שהוא מגיע כל הדרך

1463
01:02:08,030 --> 01:02:13,100
עד הסוף, מה שאומר שאתה
יש אפס אלמנטים שהם לא ממוינים

1464
01:02:13,100 --> 01:02:14,800
וכל דבר אחר כבר מסודרים.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
הגיוני?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
קצת יותר קונקרטי?

1469
01:02:19,280 --> 01:02:19,990
העזרה הקוד?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> תלמיד: לגודל, אתה אף פעם לא
להגדיר אותו או לשנות אותו,

1472
01:02:26,410 --> 01:02:27,340
איך הוא יודע?

1473
01:02:27,340 --> 01:02:32,380
>> מנחה: אז דבר אחד
תבחין כאן הוא גודל int.

1474
01:02:32,380 --> 01:02:35,680
אז אנחנו אומרים בסוג sort-- זה
היא פונקציה בזה case-- זה

1475
01:02:35,680 --> 01:02:40,770
מיון בחירה, זה עבר
עם הפונקציה.

1476
01:02:40,770 --> 01:02:43,460
אז אם זה לא עבר
ב, היית עושה משהו

1477
01:02:43,460 --> 01:02:47,840
כמו עם האורך של המערך
או שהיית איטרציות ב

1478
01:02:47,840 --> 01:02:49,390
כדי למצוא את האורך.

1479
01:02:49,390 --> 01:02:52,680
אבל בגלל זה עבר
ב, אנחנו יכולים פשוט להשתמש בו.

1480
01:02:52,680 --> 01:02:55,720
אתה פשוט מניח שהמשתמש
נתתי לך גודל חוקי ש

1481
01:02:55,720 --> 01:02:57,698
מייצג למעשה
גודל של המערך שלך.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
מגניב?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> אם יש לכם בעיות עם אלה
או רוצה מיני יותר תרגול קידוד

1486
01:03:05,870 --> 01:03:08,050
בעצמך, אתה צריך
ללכת לstudy.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
זה כלי.

1489
01:03:12,670 --> 01:03:15,040
יש להם בודק ש
למעשה אתה יכול לכתוב.

1490
01:03:15,040 --> 01:03:16,180
הם עושים פסאודו קוד.

1491
01:03:16,180 --> 01:03:19,310
יש להם עוד קטעי וידאו ושקופיות
כולל אלה שאני משתמש כאן.

1492
01:03:19,310 --> 01:03:23,150
אז אם אתה עדיין מרגיש
קצת מטושטש, לנסות את זה.

1493
01:03:23,150 --> 01:03:25,670
כמו תמיד, באו לדבר איתי, מדי.

1494
01:03:25,670 --> 01:03:26,320
שאלה?

1495
01:03:26,320 --> 01:03:28,611
>> תלמיד: האם אתה אומר
גודל מוגדר בעבר?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
מנחה: כן.

1498
01:03:29,900 --> 01:03:35,570
גודל המוגדר עד בעבר
כאן בהצהרה על הפונקציה.

1499
01:03:35,570 --> 01:03:39,060
אז אתה מניח שזה כבר עבר ב
על ידי המשתמש, ולמען הפשטות,

1500
01:03:39,060 --> 01:03:41,896
אנחנו הולכים להניח ש
משתמשים נתנו לנו את הגודל הנכון.

1501
01:03:41,896 --> 01:03:43,240
מגניב.

1502
01:03:43,240 --> 01:03:44,390
אז זה מיון בחירה.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
חבר'ה, אני יודע שאנחנו לומדים הרבה היום.

1505
01:03:47,640 --> 01:03:49,710
זה נתונים צפופים לסעיף.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
אז עם זה, אנחנו הולכים
ללכת למיון הכנסה.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> אישור.

1510
01:04:02,510 --> 01:04:06,100
אז לפני שאנחנו צריכים לעשות
ניתוח זמן הריצה שלנו כאן.

1511
01:04:06,100 --> 01:04:10,190
אז במקרה הטוב,
מובן מאליו מאז שהראיתי לך

1512
01:04:10,190 --> 01:04:11,960
השולחן כבר
סוג של נתן אותו.

1513
01:04:11,960 --> 01:04:15,430
אבל מקרה זמן הריצה הטובה ביותר, מה אנחנו חושבים?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
הכל מסודרים.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N בריבוע.

1518
01:04:22,070 --> 01:04:24,780
למישהו יש הסבר
למה אתה חושב?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> תלמיד: אתה משווה through--

1521
01:04:30,519 --> 01:04:31,268
מנחה: העכבר.

1522
01:04:31,268 --> 01:04:32,540
אתה משווה דרך.

1523
01:04:32,540 --> 01:04:35,630
בכל איטרציה, למרות ש
אנחנו decrementing זה על ידי אחד,

1524
01:04:35,630 --> 01:04:38,950
אתה עדיין מחפש דרך
הכל כדי למצוא לו הקטן ביותר.

1525
01:04:38,950 --> 01:04:42,390
אז גם אם הערך הקטן ביותר שלך
הוא כאן בתחילת,

1526
01:04:42,390 --> 01:04:44,710
אתה עדיין אתה משווה את זה
נגד כל דבר אחר

1527
01:04:44,710 --> 01:04:46,550
כדי לוודא שזה הדבר הקטן ביותר.

1528
01:04:46,550 --> 01:04:49,820
אז תקבלו בסופו פועל באמצעות
כ n בריבוע פעמים.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
בְּסֵדֶר.

1531
01:04:51,590 --> 01:04:52,785
ומה במקרה הגרוע ביותר?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
גם n בריבוע בגלל שאתה הולך
לעושה אותו הליך.

1534
01:04:57,980 --> 01:05:01,670
אז במקרה הזה, בחירה
סוג יש משהו

1535
01:05:01,670 --> 01:05:04,010
כי אנחנו גם קוראים לריצה צפויה.

1536
01:05:04,010 --> 01:05:07,400
אז באחרים, אנחנו רק יודעים
הגבולות העליונים ותחתונים.

1537
01:05:07,400 --> 01:05:11,180
בהתאם לאופן מטורף שלנו
רשימה היא או איך לא ממוינים זה,

1538
01:05:11,180 --> 01:05:15,350
הם נעים בין n או n בריבוע.

1539
01:05:15,350 --> 01:05:16,550
אנחנו לא יודעים.

1540
01:05:16,550 --> 01:05:22,820
>> אבל בגלל שיש לי מיון בחירה זהה
הגרוע ביותר ומקרה הטוב ביותר, שאומר לנו ש

1541
01:05:22,820 --> 01:05:25,880
לא משנה איזה סוג של קלט אנו
יש לי, בין אם זה לחלוטין

1542
01:05:25,880 --> 01:05:29,130
מיון או לחלוטין
להפוך מסודרים, זה

1543
01:05:29,130 --> 01:05:30,740
הולך לקחת את אותה הכמות של זמן.

1544
01:05:30,740 --> 01:05:33,760
אז במקרה זה, אם אתה
זוכר מהשולחן שלנו,

1545
01:05:33,760 --> 01:05:38,610
זה באמת היה ערך ש
שני מיני אלה לא צריכים,

1546
01:05:38,610 --> 01:05:40,390
וזה זמן ריצה צפויה.

1547
01:05:40,390 --> 01:05:43,350
כך אנו יודעים כי בכל פעם ש
אנו מפעילים מיון בחירה,

1548
01:05:43,350 --> 01:05:45,380
זה מובטח
לרוץ זמן n בריבוע.

1549
01:05:45,380 --> 01:05:46,630
אין שונות קיימים.

1550
01:05:46,630 --> 01:05:47,630
זה פשוט צפוי.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
ו, שוב, אם אתה רוצה ללמוד
יותר, לקחת CS 124 באביב.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
בְּסֵדֶר.

1555
01:05:56,712 --> 01:05:57,545
אנחנו כבר ראינו את זה.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
מגניב.

1558
01:05:59,030 --> 01:06:00,930
סוג אז הכנסה.

1559
01:06:00,930 --> 01:06:03,330
ואני כנראה הולך
ללהבה לעבור את זה.

1560
01:06:03,330 --> 01:06:05,440
אני לא יש לכם קוד זה.

1561
01:06:05,440 --> 01:06:06,580
אנחנו פשוט לעבור את זה.

1562
01:06:06,580 --> 01:06:10,500
אז מיון ההכנסה הוא סוג
של דומה למיון בחירה

1563
01:06:10,500 --> 01:06:14,460
שביש לנו שני לא ממוינת
ומסודר על חלק מהמערך.

1564
01:06:14,460 --> 01:06:20,260
>> אבל מה ששונה הוא ש
כפי שאנו עוברים אחד אחד,

1565
01:06:20,260 --> 01:06:24,210
רק שאנחנו לוקחים כל מספר
הוא הבא לא ממוינים שלנו,

1566
01:06:24,210 --> 01:06:28,507
וכראוי למיין את זה
למערך ממוין שלנו.

1567
01:06:28,507 --> 01:06:30,090
זה יהיה הגיוני יותר עם דוגמא.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
אז כל מה שמתחיל כלא ממוין,
בדיוק כמו עם מיון בחירה.

1570
01:06:35,430 --> 01:06:38,740
ואנחנו הולכים כדי למיין את זה
עולה סדר כפי שאנו כבר.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
אז בסיבוב הקודם שלנו
אנחנו לוקחים את הערך הראשון

1573
01:06:43,340 --> 01:06:46,700
ואנחנו אומרים, בסדר, אתה
עכשיו ברשימה בעצמך.

1574
01:06:46,700 --> 01:06:49,150
>> מכיוון שאתה ברשימה
בעצמך, אתה מסודרים.

1575
01:06:49,150 --> 01:06:52,460
ברכות על היותו
האלמנט ראשון במערך זה.

1576
01:06:52,460 --> 01:06:54,800
אתה כבר מסודרים כל בעצמך.

1577
01:06:54,800 --> 01:06:58,900
אז עכשיו יש לנו מסודרים
ומערך לא ממוינת.

1578
01:06:58,900 --> 01:07:01,760
אז עכשיו אנחנו לוקחים הראשונים.

1579
01:07:01,760 --> 01:07:05,600
מה קורה בין כאן
וכאן הוא שאנחנו אומרים,

1580
01:07:05,600 --> 01:07:08,890
בסדר, אנחנו הולכים להסתכל על
הערך הראשון של המערך ממוין שלנו

1581
01:07:08,890 --> 01:07:13,270
ואנחנו הולכים להכניס אותה בה
מקום נכון במערך ממוין.

1582
01:07:13,270 --> 01:07:21,460
>> אז מה אנחנו הוא לקחת 5 ו
אנחנו אומרים, בסדר, 5 גדול מ- 3,

1583
01:07:21,460 --> 01:07:24,630
אז אנחנו פשוט להכניס את זה נכון
בצד הימין של זה.

1584
01:07:24,630 --> 01:07:25,130
אנחנו טובים.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
אז אנחנו הולכים לצד אחד שלנו.

1587
01:07:28,420 --> 01:07:29,720
ואנחנו לוקחים 2.

1588
01:07:29,720 --> 01:07:34,330
אנחנו אומרים, בסדר, 2 פחות
מ -3, כך שאנחנו יודעים שזה

1589
01:07:34,330 --> 01:07:36,220
צריך להיות ב
מול הרשימה שלנו עכשיו.

1590
01:07:36,220 --> 01:07:41,800
אז מה שאנחנו עושים זה לדחוף 3 ו -5 למטה
ואנחנו עוברים 2 שלחריץ הראשון.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
אז אנחנו רק הכנסתו ל
המקום הנכון זה צריך להיות.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> ואז אנחנו מסתכלים עלינו
הבא, ואנחנו אומרים 6.

1595
01:07:49,470 --> 01:07:53,620
אישור, 6 גדול מ
כל דבר במערך ממוין שלנו,

1596
01:07:53,620 --> 01:07:56,000
אז אנחנו פשוט לתייג אותו עד הסוף.

1597
01:07:56,000 --> 01:07:56,960
ואז אנחנו מסתכלים על 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 הוא פחות מ -6, זה פחות
מ 5 אבל זה יותר מ 3.

1600
01:08:03,020 --> 01:08:06,270
אז אנחנו פשוט להכניס אותו ישר לתוך
האמצע בין 3 ל 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
אז כדי לעשות את זה קצת
קצת יותר קונקרטי,

1603
01:08:10,530 --> 01:08:12,280
כאן הוא סוג של
רעיון של מה שקרה.

1604
01:08:12,280 --> 01:08:16,430
אז עבור כל רכיב לא ממוינים, אנחנו
לקבוע היכן בחלק ממוין

1605
01:08:16,430 --> 01:08:17,090
זה.

1606
01:08:17,090 --> 01:08:20,680
>> אז תוך התחשבות
מסודרים ולא ממוין,

1607
01:08:20,680 --> 01:08:26,080
אנחנו צריכים לעבור דרך ודמות
איפה זה משתלב במערך ממוין.

1608
01:08:26,080 --> 01:08:31,460
ואנחנו מכניסים אותו על ידי העברה
אלמנטים בצד הימין שלו למטה.

1609
01:08:31,460 --> 01:08:34,910
ואז אנחנו פשוט לשמור
iterating דרך עד ש

1610
01:08:34,910 --> 01:08:39,270
יש רשימה ממוינת לחלוטין
שבו לא ממוינים כעת אפס

1611
01:08:39,270 --> 01:08:41,720
וממוין תופס
שלמות של הרשימה שלנו.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
אז, שוב, לעשות עוד דברים
יותר קונקרטי, יש לנו פסאודו קוד.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> אז בעצם להוא אני
שווה ל0 עד n מינוס 1,

1616
01:08:52,410 --> 01:08:54,790
זה רק האורך של המערך שלנו.

1617
01:08:54,790 --> 01:09:00,979
יש לנו כמה אלמנט שהוא שווה ל
המערך הראשון או המדדים הראשונים.

1618
01:09:00,979 --> 01:09:03,200
אנו קובעים j שווה לזה.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
אז בזמן j גדול מ
אפס והמערך, j מינוס 1

1621
01:09:09,210 --> 01:09:11,660
גדול מ
אלמנט, אז כל מה שעושה

1622
01:09:11,660 --> 01:09:17,479
הוא לוודא ש
j שלך באמת מייצג

1623
01:09:17,479 --> 01:09:20,010
החלק ממוין של המערך.

1624
01:09:20,010 --> 01:09:30,745
>> אז בזמן שעדיין יש דברים
כדי למיין ומינוס j אחד is-- מה

1625
01:09:30,745 --> 01:09:31,840
הוא היסוד שלה?

1626
01:09:31,840 --> 01:09:34,760
J לא הוגדר כאן.

1627
01:09:34,760 --> 01:09:35,677
זה סוג של מעצבן.

1628
01:09:35,677 --> 01:09:36,176
אישור.

1629
01:09:36,176 --> 01:09:36,689
בכל אופן.

1630
01:09:36,689 --> 01:09:39,899
אז j מינוס 1, אתה בודק
האלמנט לפני ש.

1631
01:09:39,899 --> 01:09:46,460
אתה אומר, בסדר, הוא האלמנט
לפני כל המקום שאני am-- בוא

1632
01:09:46,460 --> 01:09:47,540
למעשה לצייר את זה.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
אז בואו נגיד שזה הוא
כמו במעבר השני שלנו.

1635
01:09:56,830 --> 01:09:59,525
אז אני הולך להיות שווה
ל1, שהוא כאן.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> אז אני הולך להיות שווה ל 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
זה יהיה 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
בְּסֵדֶר.

1642
01:10:16,750 --> 01:10:20,945
אז האלמנט שלנו במקרה זה
הולך להיות שווה ל 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
ויש לנו כמה j זה
הולך להיות שווה ל 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
אה, j הוא decrementing.

1647
01:10:30,971 --> 01:10:31,720
כי זה מה שזה.

1648
01:10:31,720 --> 01:10:35,680
אז j שווה ל i, אז מה זה
אמרה היא שככל שאנו מתקדמים,

1649
01:10:35,680 --> 01:10:37,530
אנחנו רק לוודא
שאנחנו לא מעל

1650
01:10:37,530 --> 01:10:43,520
אינדקס בדרך זו, כאשר אנחנו מנסים
להכניס דברים לרשימה הממוינת שלנו.

1651
01:10:43,520 --> 01:10:49,850
>> לכן, כאשר j שווה ל -1 במקרה זה ו
מינוס j מערך one-- כך 1 מינוס j מערך

1652
01:10:49,850 --> 01:10:54,610
הוא 2 בcase-- זה אם זה
גדול יותר מהאלמנט,

1653
01:10:54,610 --> 01:10:57,700
אז כל זה עושה
הוא הסטה את רוחות.

1654
01:10:57,700 --> 01:11:04,790
אז במקרה הזה, אחד מינוס j מערך
יהיה מערך אפס, אשר 2.

1655
01:11:04,790 --> 01:11:08,430
2 הוא לא גדולים יותר מ -4,
אז זה לא מתבצע.

1656
01:11:08,430 --> 01:11:11,460
אז השינוי לא זז כלפי מטה.

1657
01:11:11,460 --> 01:11:18,790
מה שזה עושה כאן הוא פשוט
נע המערך ממוין שלך למטה.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
במקרה זה, בעצם, אנחנו
יכול do-- בואו נעשה את זה 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
אז אם אנחנו ללכת דרך עם
דוגמא זו, אנחנו עכשיו כאן.

1662
01:11:31,970 --> 01:11:32,740
זה מסודרים.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
זה לא ממוינים.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
מגניב?

1667
01:11:39,860 --> 01:11:46,620
אז היא i שווה ל 2, כך
האלמנט שלנו הוא שווה ל- 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
וי שלנו הוא שווה ל 2.

1670
01:11:52,270 --> 01:12:00,620
אז אנחנו מסתכלים דרך ואנחנו
אומר, בסדר, הוא מינוס j מערך אחד

1671
01:12:00,620 --> 01:12:03,470
גדול יותר מהאלמנט
שאנחנו מסתכלים?

1672
01:12:03,470 --> 01:12:05,540
והתשובה היא כן, נכון?

1673
01:12:05,540 --> 01:12:11,275
4 הוא יותר מ 3 וי
הוא 2, כך הקוד הזה.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> אז עכשיו מה שאנחנו עושים מערך ב
2, כל כך כאן, אנו להחליף אותם.

1676
01:12:18,550 --> 01:12:25,620
אז אנחנו פשוט אומרים, בסדר, מערך
ב -2 עכשיו הולך להיות 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
וי הולך להיות שווה
מינוס j 1, שהוא 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
זה נורא, אבל
אתם מבינים את הרעיון.

1681
01:12:37,200 --> 01:12:38,360
J הוא שווה ל 1 עכשיו.

1682
01:12:38,360 --> 01:12:44,360
וי מערך הוא רק הולך להיות
שווה לאלמנט שלנו, שהיה 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
אני מחקתי משהו שאני לא צריך
יש להם או משהו miswrote,

1685
01:12:48,570 --> 01:12:49,910
אבל אתם מבינים את הרעיון.

1686
01:12:49,910 --> 01:12:50,640
>> זה לעבור בn.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
ואז, אם זה היה, היית זה לולאה
שוב וזה הייתי אומר, בסדר, j הוא 1 עכשיו.

1689
01:12:57,960 --> 01:13:00,665
ומינוס j מערך 1 הוא כעת 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
האם 2 פחות מהאלמנט שלנו?

1692
01:13:03,760 --> 01:13:04,540
לא?

1693
01:13:04,540 --> 01:13:07,970
זה אומר שיש לנו
הכניס את האלמנט הזה

1694
01:13:07,970 --> 01:13:10,110
במקום הנכון במערך ממוין שלנו.

1695
01:13:10,110 --> 01:13:14,400
אז אנחנו יכולים לקחת את זה ואנחנו אומרים,
אישור, מערך המיון שלנו הוא כאן.

1696
01:13:14,400 --> 01:13:19,940
וזה היה לוקח מספר זה 6 ולהיות
כמו, אישור, הוא 6 פחות ממספר זה?

1697
01:13:19,940 --> 01:13:20,480
לא?

1698
01:13:20,480 --> 01:13:21,080
מגניב.

1699
01:13:21,080 --> 01:13:22,680
אנחנו בסדר.

1700
01:13:22,680 --> 01:13:23,530
>> לעשות את זה שוב.

1701
01:13:23,530 --> 01:13:24,740
אנחנו אומרים 7.

1702
01:13:24,740 --> 01:13:29,010
האם 7 פחות מהסוף
של המערך ממוין שלנו?

1703
01:13:29,010 --> 01:13:29,520
מס '

1704
01:13:29,520 --> 01:13:30,430
אז אנחנו בסדר.

1705
01:13:30,430 --> 01:13:32,760
אז זה יהיה מסודר.

1706
01:13:32,760 --> 01:13:38,610
בעיקרון כל זה עושה
האם זה אומר לקחת

1707
01:13:38,610 --> 01:13:42,060
האלמנט הראשון של
המערך לא ממוינת שלך,

1708
01:13:42,060 --> 01:13:46,010
להבין לאן זה הולך
במערך ממוין שלך.

1709
01:13:46,010 --> 01:13:48,780
וזה רק מטפל
של חילופים לעשות את זה.

1710
01:13:48,780 --> 01:13:51,300
אתה בעצם רק החלפה
עד שזה במקום הנכון.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
הדימוי החזותי הוא שאתה
נע בכל מה שעל ידי עושה את זה.

1713
01:13:56,990 --> 01:13:59,420
>> אז זה כמו מחצית בועת סוג-בבניין.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
עזיבה מחקר 50.

1716
01:14:03,420 --> 01:14:06,000
אני מאוד ממליץ לנסות
לקוד זה בעצמך.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
אם יש לך בעיות או שאתה רוצה
לראות את הקוד לדוגמה עבור סוג הכנסה,

1719
01:14:12,450 --> 01:14:13,750
אנא הודע לי.

1720
01:14:13,750 --> 01:14:14,500
אני תמיד בסביבה.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
מקרה הגרוע ביותר זמן הריצה אז
ומקרה זמן הריצה הטובה ביותר.

1723
01:14:20,200 --> 01:14:30,700
כפי שראית בחור מהשולחן אני כבר
הראיתי לך, זה גם וגם n בריבוע וn.

1724
01:14:30,700 --> 01:14:35,590
>> אז סוג של הנוסע של מה שדברנו
על עם מיני הקודמים שלנו, הגרוע ביותר

1725
01:14:35,590 --> 01:14:38,760
מקרה ריצה היא שאם
זה לא ממוינים לחלוטין,

1726
01:14:38,760 --> 01:14:42,530
אנחנו צריכים להשוות את כל הפעמים n אלה.

1727
01:14:42,530 --> 01:14:47,020
אנחנו עושים המון השוואות
כי אם זה בסדר הפוך,

1728
01:14:47,020 --> 01:14:50,360
אנחנו הולכים להגיד, בסדר, זה
הוא אותו, זה טוב,

1729
01:14:50,360 --> 01:14:54,650
וזה אחד לא צריך להיות בהשוואה
נגד הראשונה שחזרה.

1730
01:14:54,650 --> 01:14:56,710
וכמו שאנחנו מקבלים ל
קצה הזנב, יש לנו

1731
01:14:56,710 --> 01:14:59,440
כדי להשוות, להשוות, ו
להשוות נגד כל מה.

1732
01:14:59,440 --> 01:15:03,030
>> אז זה בסופו להיות
כ n בריבוע.

1733
01:15:03,030 --> 01:15:09,510
אם זה נכון אז אתה
אומר, בסדר, 2, אתה טוב.

1734
01:15:09,510 --> 01:15:11,330
3, אתה לעומת 2.

1735
01:15:11,330 --> 01:15:12,310
אתה טוב.

1736
01:15:12,310 --> 01:15:14,150
4, אתה פשוט להשוות את הזנב.

1737
01:15:14,150 --> 01:15:14,990
אתה טוב.

1738
01:15:14,990 --> 01:15:17,140
6, להשוות את הזנב, אתה בסדר.

1739
01:15:17,140 --> 01:15:20,870
אז לכל נקודה אם זה כבר
מסודרים, אתה עושה השוואה אחד.

1740
01:15:20,870 --> 01:15:22,320
כך שזה רק n.

1741
01:15:22,320 --> 01:15:26,840
וכי יש לנו מקרה של זמן ריצה הטובה ביותר
של n ומקרה זמן ריצה הגרועה ביותר של n

1742
01:15:26,840 --> 01:15:28,680
בריבוע, אין לנו זמן ריצה צפויה.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> זה פשוט תלוי ב
תוהו ובוהו של הרשימה שלנו יש.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
ושוב, אחר
גרף וטבלה אחרת.

1747
01:15:39,530 --> 01:15:41,170
אז הבדלים בין מיני.

1748
01:15:41,170 --> 01:15:44,180
אני רק הולך לרוח באמצעות, אני
מרגיש כמו שדיברנו בהרחבה

1749
01:15:44,180 --> 01:15:46,570
על איך שהם כל הסוג
של להשתנות וקישור יחד.

1750
01:15:46,570 --> 01:15:50,564
אז מיון מיזוג הוא האחרון
אני נשא אתכם עם.

1751
01:15:50,564 --> 01:15:52,105
יש לנו תמונה יפה וצבעונית.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
אז למזג מיון הוא אלגוריתם הרקורסיבי.

1754
01:15:56,040 --> 01:15:59,910
אז אתם יודעים מה
פונקציה רקורסיבית היא?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> כל אחד רוצה לומר?

1757
01:16:03,320 --> 01:16:04,739
אתה רוצה לנסות?

1758
01:16:04,739 --> 01:16:07,280
אז פונקציה רקורסיבית היא רק
פונקציה שקוראת לעצמו.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
אז אם אתם מכירים
עם רצף פיבונאצ'י,

1761
01:16:11,590 --> 01:16:15,670
זה ייחשב רקורסיבית כי
אתה לוקח את שני הקודמים

1762
01:16:15,670 --> 01:16:17,530
ולהוסיף אותם ביחד
לתפוס את הבא בתור שלך.

1763
01:16:17,530 --> 01:16:21,440
אז רקורסיבית, אני תמיד חושב
של רקורסיה ככמו ספירלה

1764
01:16:21,440 --> 01:16:24,430
אז אתה כמו מתפתל במורדו.

1765
01:16:24,430 --> 01:16:27,150
אבל זה רק פונקציה
שקורא לעצמו.

1766
01:16:27,150 --> 01:16:32,660
>> ו, למעשה, ממש במהירות אני
יכול להראות לך מה שנראה כמו.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
אז רקורסיבית כאן, אם אנחנו מסתכלים, זה הוא
הדרך רקורסיבית כדי לסכם על מערך.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
אז כל מה שאנחנו עושים זה
יש לנו פונקצית סכום

1771
01:16:47,880 --> 01:16:52,210
סכום שלוקח גודל ומערך.

1772
01:16:52,210 --> 01:16:55,210
ואם אתה שם לב, גודל
decrements על ידי אחד בכל פעם.

1773
01:16:55,210 --> 01:17:00,365
וכל שהיא עושה הוא אם x הוא שווה ל
zero-- כך שאם הגודל של המערך

1774
01:17:00,365 --> 01:17:02,710
שווה לzero-- היא מחזירה אפס.

1775
01:17:02,710 --> 01:17:10,440
>> אחרת זה מסכם את זה
האלמנט האחרון של המערך,

1776
01:17:10,440 --> 01:17:14,790
ואז לוקח את הסכום של
שאר המערך.

1777
01:17:14,790 --> 01:17:17,555
אז זה פשוט לשבור אותו
בבעיות קטנות יותר ויותר.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
סיפור ארוך קצרה, רקורסיה,
פונקציה שקוראת לעצמו.

1780
01:17:21,890 --> 01:17:25,740
אם זה כל מה שיצאת מזה,
זה מה שהיא פונקציה רקורסיבית.

1781
01:17:25,740 --> 01:17:29,870
אם אתה לוקח 51, תקבל מאוד,
מאוד נוח עם רקורסיה.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
זה ממש מגניב.

1784
01:17:32,370 --> 01:17:34,660
זה נראה הגיוני כב
03:00 לילה אחד יצא.

1785
01:17:34,660 --> 01:17:37,900
ואני הייתי כמו, למה
יש לי אף פעם לא משתמש בזה?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> אז לסוג מיזוג, בעצם
מה זה הולך לעשות הוא זה

1788
01:17:42,430 --> 01:17:45,620
הולך לפרק אותו ולשבור אותו
מטה עד שהאלמנטים רק אחת.

1789
01:17:45,620 --> 01:17:47,570
האלמנטים בודדים קלים למיין.

1790
01:17:47,570 --> 01:17:48,070
אנחנו רואים את זה.

1791
01:17:48,070 --> 01:17:50,760
אם יש לך אלמנט אחד, זה
כבר נחשב ממוין.

1792
01:17:50,760 --> 01:17:53,800
אז על קלט של n אלמנטים,
אם n הוא פחות מ 2,

1793
01:17:53,800 --> 01:17:58,120
רק לחזור כי אמצעים ש
זה או 0 או 1 כפי שראינו.

1794
01:17:58,120 --> 01:18:00,050
אלה נחשבים אלמנטים ממוינים.

1795
01:18:00,050 --> 01:18:02,170
>> אחרת לשבור אותו לשתיים.

1796
01:18:02,170 --> 01:18:06,336
מיין את המחצית הראשונה, למיין את השנייה
מחצית, ואז למזג אותם יחד.

1797
01:18:06,336 --> 01:18:07,460
למה זה נקרא סוג המיזוג.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
אז יש לנו כאן אנחנו נטפל אלה.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
אז אנחנו שומרים שיש להם
עד שגודל המערך הוא 1.

1802
01:18:17,210 --> 01:18:20,790
לכן, כאשר התוצאה 1, אנחנו פשוט לחזור
בגלל זה הוא מערך ממוין,

1803
01:18:20,790 --> 01:18:23,940
ואת זה הוא מערך ממוין, וזה
מערך ממוין, כולנו מסודרים.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
אז מה שאנחנו עושים זה
להתחיל ממזג אותם יחד.

1806
01:18:29,420 --> 01:18:31,820
>> אז כפי שאתה יכול
לחשוב על מיזוג הוא

1807
01:18:31,820 --> 01:18:36,240
אתה פשוט להסיר את קטן יותר
מספר של כל אחד ממערכים תת

1808
01:18:36,240 --> 01:18:38,330
ורק להוסיף אותו למערך יצא.

1809
01:18:38,330 --> 01:18:44,290
אז אם אתה מסתכל כאן, כאשר יש לנו
ערכות אלה יש לנו 4, 6, ו -1.

1810
01:18:44,290 --> 01:18:47,280
כאשר אנו רוצים למזג אלה,
אנחנו מסתכלים על שני ראשונים אלה

1811
01:18:47,280 --> 01:18:50,730
ואנחנו אומרים, בסדר, 1 קטן,
זה הולך לחזית.

1812
01:18:50,730 --> 01:18:54,330
4 ו -6, אין מה להשוות
זה ל, רק לתייג אותו עד הסוף.

1813
01:18:54,330 --> 01:18:58,020
>> כאשר אנחנו משלבים את שני אלה, אנחנו פשוט
לקחת את קטן יותר באחת משני אלה,

1814
01:18:58,020 --> 01:18:59,310
אז זה 1.

1815
01:18:59,310 --> 01:19:01,690
ועכשיו אנחנו שותים
קטן יותר של שני אלה, כך 2.

1816
01:19:01,690 --> 01:19:03,330
קטן יותר של שני אלה, 3.

1817
01:19:03,330 --> 01:19:06,260
קטן יותר של שני, 4, 5, 6 הבאים.

1818
01:19:06,260 --> 01:19:08,630
אז אתה פשוט מושך את אלה.

1819
01:19:08,630 --> 01:19:11,210
וכי יש להם
מוין בעבר,

1820
01:19:11,210 --> 01:19:14,300
רק יש לך אחד
השוואה בכל פעם שיש.

1821
01:19:14,300 --> 01:19:19,610
אז עוד קוד כאן, רק ייצוג.

1822
01:19:19,610 --> 01:19:24,410
אז אתה מתחיל באמצע ו
אתה סוג ימין ומהשמאל

1823
01:19:24,410 --> 01:19:26,180
ואז אתה פשוט למזג אותם.

1824
01:19:26,180 --> 01:19:30,080
>> ואין לנו קוד
למיזוג ממש כאן.

1825
01:19:30,080 --> 01:19:34,110
אבל, שוב, אם אתה רוצה ללכת על
ללמוד 50, היא תהיה שם.

1826
01:19:34,110 --> 01:19:36,860
אחרת תבואו לדבר איתי
אם אתה עדיין מבולבל.

1827
01:19:36,860 --> 01:19:42,340
אז דבר מגניב כאן הוא שהמקרה הטוב ביותר,
במקרה הגרוע ביותר, וזמן ריצה צפוי

1828
01:19:42,340 --> 01:19:46,250
כולם ביומן n, ש
הרבה יותר טוב מאשר יש לנו

1829
01:19:46,250 --> 01:19:48,000
ראיתי לשאר מיני שלנו.

1830
01:19:48,000 --> 01:19:51,840
ראינו n בריבוע
ומה שאנחנו באמת

1831
01:19:51,840 --> 01:19:54,380
להגיע לכאן הוא n n יומן, וזה נהדר.

1832
01:19:54,380 --> 01:19:55,830
>> תראה כמה טוב שהוא.

1833
01:19:55,830 --> 01:19:56,780
כגון עקומה יפה.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
כל כך הרבה יותר יעיל.

1836
01:20:00,120 --> 01:20:03,510
אם אי פעם שאתה יכול, להשתמש במיזוג מהסוג.

1837
01:20:03,510 --> 01:20:04,810
זה יחסוך לך זמן.

1838
01:20:04,810 --> 01:20:07,670
ואז שוב, כפי שאמרנו, אם
אתה למטה באזור הנמוך הזה,

1839
01:20:07,670 --> 01:20:09,480
זה לא עושה ש
הרבה הבדל.

1840
01:20:09,480 --> 01:20:11,360
אתה קם לאלפים
ואלפי כניסות,

1841
01:20:11,360 --> 01:20:13,318
אתה בהחלט רוצה
אלגוריתם יעיל יותר.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
ושוב, השולחן היפה שלנו, של כל
מיני שאתם למדו היום.

1844
01:20:19,400 --> 01:20:21,157
>> אז אני יודע שזה היה יום צפוף.

1845
01:20:21,157 --> 01:20:23,490
זה לא הולך בהכרח
כדי לעזור עם pset שלך אתה.

1846
01:20:23,490 --> 01:20:28,250
אבל אני רק רוצה להפוך את כתב ויתור
הסעיף שהוא לא רק על psets.

1847
01:20:28,250 --> 01:20:31,240
כל החומר הזה הוא הוגן
משחק למבחני אמצע הסמסטר שלך.

1848
01:20:31,240 --> 01:20:35,430
וגם אם אתה עושה להמשיך עם CS,
אלה הם יסודות חשובים באמת

1849
01:20:35,430 --> 01:20:37,870
שהיית צריך לדעת.

1850
01:20:37,870 --> 01:20:41,700
אז כמה ימים יהיו
עזרה נוספת pset קטנה,

1851
01:20:41,700 --> 01:20:44,600
אבל כמה שבועות יהיו
תוכן ממשי הרבה יותר

1852
01:20:44,600 --> 01:20:46,600
שאולי לא נראה סופר
שימושי לך עכשיו,

1853
01:20:46,600 --> 01:20:51,215
אבל אני מבטיח אם תמשיך
ביהיה מאוד, מאוד שימושי.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> אז זהו זה לסעיף.

1856
01:20:54,250 --> 01:20:55,250
עד לחוט.

1857
01:20:55,250 --> 01:20:56,570
אני עשיתי את זה בתוך דקה אחת.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
אבל הנה לך.

1860
01:20:58,970 --> 01:21:01,240
ויהיה לי סופגניות או ממתקים.

1861
01:21:01,240 --> 01:21:03,464
האם מישהו אלרגי ל
כל דבר, דרך אגב?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
ביצים וחלב.

1864
01:21:05,890 --> 01:21:08,120
אז סופגניות הן לא?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
אישור.

1867
01:21:10,160 --> 01:21:10,770
בְּסֵדֶר.

1868
01:21:10,770 --> 01:21:12,120
לא שוקולד?

1869
01:21:12,120 --> 01:21:12,620
מטר של כוכבים.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
מטר כוכבים טובים.

1872
01:21:14,670 --> 01:21:15,170
אישור.

1873
01:21:15,170 --> 01:21:17,045
אנחנו הולכים יש לי
מטר של כוכבים בשבוע הבא ולאחר מכן.

1874
01:21:17,045 --> 01:21:18,240
זה מה שאני אקבל.

1875
01:21:18,240 --> 01:21:19,690
יש לכם שבוע נהדר.

1876
01:21:19,690 --> 01:21:20,460
לקרוא את האפיון שלך.

1877
01:21:20,460 --> 01:21:22,130
>> תודיע לי אם יש לך שאלות.

1878
01:21:22,130 --> 01:21:25,300
שתי כיתות Pset צריכה להיות
יוצא לך עד יום חמישי.

1879
01:21:25,300 --> 01:21:28,320
אם יש לך שאלות
על איך אני מדורג משהו

1880
01:21:28,320 --> 01:21:32,250
או למה אני מדורג משהו כמו שאני
לא, אנא שלח לי, תבואו לדבר איתי.

1881
01:21:32,250 --> 01:21:34,210
אני זה מטורף קצת
שבוע, אבל אני מבטיח

1882
01:21:34,210 --> 01:21:36,340
אני עדיין אשיב תוך 24 שעות.

1883
01:21:36,340 --> 01:21:38,240
אז יש לי שבוע, כולם נהדרים.

1884
01:21:38,240 --> 01:21:40,090
מזל טוב על pset שלך.

1885
01:21:40,090 --> 01:21:41,248