1
00:00:00,000 --> 00:00:03,332
>> [MUSIC CHƠI]

2
00:00:03,332 --> 00:00:06,490
>> Andi PENG: Chào mừng bạn đến tuần thứ 3 của phần.

3
00:00:06,490 --> 00:00:09,550
Cảm ơn, anh chàng này, tất cả đều đến
đến thời điểm này bắt đầu sớm hơn ngày hôm nay.

4
00:00:09,550 --> 00:00:11,466
Chúng tôi đã có một tốt đẹp, ít
nhóm thân mật ngày hôm nay.

5
00:00:11,466 --> 00:00:14,570
Vì vậy, chúng tôi hy vọng sẽ nhận được để
kết thúc, có lẽ, sớm,

6
00:00:14,570 --> 00:00:15,780
một chút sớm hôm nay.

7
00:00:15,780 --> 00:00:22,057
Vì vậy, một cách nhanh chóng, chỉ cần một số
thông báo cho chương trình ngày hôm nay.

8
00:00:22,057 --> 00:00:23,890
Trước khi chúng tôi bắt đầu, chúng tôi
sẽ chỉ đi qua

9
00:00:23,890 --> 00:00:28,910
một số vấn đề về hậu cần ngắn gọn, pset
câu hỏi, & rút, những điều như thế.

10
00:00:28,910 --> 00:00:30,250
Và sau đó chúng tôi sẽ nhảy ngay vào.

11
00:00:30,250 --> 00:00:34,710
Chúng tôi sẽ sử dụng một trình gỡ lỗi được gọi là GDB để
bắt đầu lật tẩy mã của chúng tôi, mà David

12
00:00:34,710 --> 00:00:36,550
giải thích trong bài giảng ngày khác.

13
00:00:36,550 --> 00:00:39,420
Chúng tôi sẽ đi qua bốn loại của các loại.

14
00:00:39,420 --> 00:00:42,310
Chúng tôi sẽ đi qua chúng khá nhanh chóng
kể từ khi họ đang khá tích cực.

15
00:00:42,310 --> 00:00:45,710
Nhưng biết rằng tất cả các slide và
mã nguồn luôn trực tuyến.

16
00:00:45,710 --> 00:00:50,810
Vì vậy, cảm thấy tự do, tại nhìn chăm chú của bạn, để
quay trở lại và hãy nhìn vào đó.

17
00:00:50,810 --> 00:00:53,930
>> Chúng tôi sẽ đi qua
ký hiệu tiệm cận, mà

18
00:00:53,930 --> 00:00:55,944
chỉ là một cách ưa thích
nói "runtimes,"

19
00:00:55,944 --> 00:00:58,360
nơi chúng ta có O lớn, mà
David giải thích trong bài giảng.

20
00:00:58,360 --> 00:01:01,550
Và chúng tôi cũng có Omega, mà
là thời gian chạy thấp hơn bị ràng buộc.

21
00:01:01,550 --> 00:01:06,450
Và chúng ta sẽ nói nhiều hơn một chút
chuyên sâu về cách những người làm việc.

22
00:01:06,450 --> 00:01:10,160
Và cuối cùng, chúng ta sẽ đi qua tìm kiếm nhị phân,
bởi vì rất nhiều bạn của những người đã có

23
00:01:10,160 --> 00:01:15,190
liếc nhìn psets của bạn có thể biết rằng
đó là một câu hỏi đó là trong pset của bạn.

24
00:01:15,190 --> 00:01:17,470
Vì vậy, tất cả các bạn sẽ được hạnh phúc
rằng chúng tôi bao gồm điều này hôm nay.

25
00:01:17,470 --> 00:01:20,610
>> Và cuối cùng, mỗi bạn
phần thông tin phản hồi, tôi thực sự

26
00:01:20,610 --> 00:01:23,000
còn lại khoảng 15 phút ở
Cuối cùng chỉ cần đi qua

27
00:01:23,000 --> 00:01:27,730
logistics của pset3, bất kỳ câu hỏi,
có thể một chút hướng dẫn, nếu bạn muốn,

28
00:01:27,730 --> 00:01:28,990
trước khi chúng tôi bắt đầu lập trình.

29
00:01:28,990 --> 00:01:30,890
Vì vậy, hãy cố gắng để có được thông qua
vật liệu khá nhanh chóng.

30
00:01:30,890 --> 00:01:33,880
Và sau đó chúng ta có thể dành thời gian
lấy thêm nhiều câu hỏi cho các pset.

31
00:01:33,880 --> 00:01:35,230
ĐƯỢC.

32
00:01:35,230 --> 00:01:39,570
>> Nhanh chóng, vì vậy chỉ cần một vài
thông báo trước khi chúng tôi bắt đầu ngày hôm nay.

33
00:01:39,570 --> 00:01:45,410
Trước hết, chào đón để làm
nó thông qua hai của psets của bạn.

34
00:01:45,410 --> 00:01:49,432
Tôi lấy một cái nhìn tại yeah, chúng ta hãy your--
nhận được một tràng pháo tay cho rằng một.

35
00:01:49,432 --> 00:01:51,140
Trên thực tế, tôi đã thực sự,
thực sự ấn tượng.

36
00:01:51,140 --> 00:01:55,800
Tôi phân loại các pset đầu tiên cho các bạn
tuần và bạn kẻ cuối cùng đã không thể tin được.

37
00:01:55,800 --> 00:01:58,290
>> Phong cách là ở điểm
bên cạnh một vài ý kiến.

38
00:01:58,290 --> 00:02:00,660
Hãy chắc chắn rằng bạn luôn luôn
cho ý kiến ​​mã của bạn.

39
00:02:00,660 --> 00:02:03,040
Nhưng psets của bạn là ở điểm.

40
00:02:03,040 --> 00:02:05,549
Và giữ cho nó lên.

41
00:02:05,549 --> 00:02:08,090
Và đó là tốt cho các học sinh lớp để
thấy rằng các bạn đang đặt

42
00:02:08,090 --> 00:02:10,704
trong khi nhiều nỗ lực trong phong cách của bạn
và thiết kế của bạn trong mã của bạn

43
00:02:10,704 --> 00:02:12,120
mà chúng tôi muốn cho bạn xem.

44
00:02:12,120 --> 00:02:16,450
Vì vậy, tôi đi dọc theo lòng biết ơn của tôi
cho phần còn lại của các hỗ trợ kỹ thuật.

45
00:02:16,450 --> 00:02:19,210
>> Tuy nhiên có một
vài câu hỏi & rút

46
00:02:19,210 --> 00:02:22,010
Tôi chỉ muốn đi qua đó
sẽ làm cho cả cuộc sống của tôi

47
00:02:22,010 --> 00:02:24,900
và rất nhiều các khác
Hỗ trợ kỹ thuật "sống một chút dễ dàng hơn.

48
00:02:24,900 --> 00:02:28,220
Thứ nhất, tôi đã nhận thấy điều này
qua week-- có bao nhiêu bạn

49
00:02:28,220 --> 00:02:32,301
đã được chạy trên check50
mã của bạn trước khi bạn gửi?

50
00:02:32,301 --> 00:02:32,800
ĐƯỢC.

51
00:02:32,800 --> 00:02:36,690
Vì vậy, tất cả mọi người nên làm check50,
because-- một secret-- chúng tôi thực sự

52
00:02:36,690 --> 00:02:41,540
chạy check50 như là một phần của tính đúng đắn của chúng tôi
kịch bản để kiểm tra mã của bạn.

53
00:02:41,540 --> 00:02:45,480
Vì vậy, nếu mã của bạn được không
check50, trong tất cả các khả năng,

54
00:02:45,480 --> 00:02:47,570
nó có lẽ sẽ
không kiểm tra của chúng tôi là tốt.

55
00:02:47,570 --> 00:02:49,320
Đôi khi các bạn
có câu trả lời đúng.

56
00:02:49,320 --> 00:02:52,200
Giống như, trong tham lam, một số
bạn có con số đúng,

57
00:02:52,200 --> 00:02:53,960
bạn chỉ cần in ra một số công cụ bổ sung.

58
00:02:53,960 --> 00:02:55,940
Và đó là công cụ bổ sung
thực sự không kiểm tra,

59
00:02:55,940 --> 00:02:58,440
bởi vì máy tính không
thực sự biết những gì nó đang tìm kiếm.

60
00:02:58,440 --> 00:03:00,981
Và do đó, nó sẽ chỉ chạy qua,
thấy rằng sản lượng của bạn không

61
00:03:00,981 --> 00:03:03,810
phù hợp với những gì chúng tôi mong đợi câu trả lời
được, và đánh dấu nó là sai.

62
00:03:03,810 --> 00:03:06,560
>> Và tôi biết rằng đã xảy ra trong
một số trường hợp của bạn trong tuần này.

63
00:03:06,560 --> 00:03:09,870
Vì vậy, tôi đã đi lại và tự
regraded mã của tất cả mọi người.

64
00:03:09,870 --> 00:03:12,780
Trong tương lai mặc dù,
xin vui lòng, xin vui lòng chắc chắn

65
00:03:12,780 --> 00:03:14,570
rằng bạn đang chạy
kiểm tra 50 trên mã của bạn.

66
00:03:14,570 --> 00:03:17,970
Bởi vì nó là loại đau đớn cho TA
phải đi lại và tự chuyển loại

67
00:03:17,970 --> 00:03:21,197
mỗi pset duy nhất cho mỗi
duy nhất, ví dụ ít bỏ lỡ.

68
00:03:21,197 --> 00:03:22,530
Vì vậy, tôi đã không mất đi bất kỳ điểm.

69
00:03:22,530 --> 00:03:25,210
Tôi nghĩ rằng tôi có thể cất cánh
một hoặc hai cho thiết kế.

70
00:03:25,210 --> 00:03:27,710
Trong tương lai, mặc dù nếu
bạn đang không check50,

71
00:03:27,710 --> 00:03:31,330
điểm sẽ được thực hiện
off cho đúng đắn.

72
00:03:31,330 --> 00:03:35,020
>> Hơn nữa, psets là
do thứ Sáu lúc giữa trưa.

73
00:03:35,020 --> 00:03:38,990
Tôi nghĩ rằng có một bảy phút
thời gian ân hạn cuối mà chúng tôi cung cấp cho bạn.

74
00:03:38,990 --> 00:03:42,434
Mỗi lần Harvard, họ được phép
là bảy phút cuối để tất cả mọi thứ.

75
00:03:42,434 --> 00:03:44,350
Vì vậy, ở đây tại Yale, chúng tôi sẽ
tuân thủ đó là tốt.

76
00:03:44,350 --> 00:03:47,910
Nhưng khá nhiều, lúc 12:07,
nếu pset của bạn không có trong,

77
00:03:47,910 --> 00:03:49,720
nó sẽ được đánh dấu là muộn.

78
00:03:49,720 --> 00:03:53,160
Và như vậy trong khi nó được đánh dấu
là muộn, TA-- tôi

79
00:03:53,160 --> 00:03:54,870
vẫn sẽ được chấm điểm psets của bạn.

80
00:03:54,870 --> 00:03:56,760
Vì vậy, bạn vẫn sẽ thấy một lớp xuất hiện.

81
00:03:56,760 --> 00:03:58,820
Tuy nhiên, biết rằng ở
kết thúc học kỳ,

82
00:03:58,820 --> 00:04:02,270
tất cả psets muộn sẽ chỉ được
tự động xóa trắng bởi máy tính.

83
00:04:02,270 --> 00:04:04,490
>> Chúng tôi làm điều này vì hai lý do.

84
00:04:04,490 --> 00:04:09,220
Một, đôi khi chúng ta có được
phép, như lời bào chữa của hiệu trưởng,

85
00:04:09,220 --> 00:04:10,762
sau này mà tôi không biết về chưa.

86
00:04:10,762 --> 00:04:13,761
Vì vậy, chúng tôi muốn chắc chắn rằng chúng tôi đang phân loại
tất cả mọi thứ chỉ trong trường hợp, như thế, tôi

87
00:04:13,761 --> 00:04:15,080
thiếu cái cớ của một hiệu trưởng.

88
00:04:15,080 --> 00:04:17,000
Và thứ hai, giữ trong
tâm trí, bạn vẫn có thể

89
00:04:17,000 --> 00:04:19,370
thả một pset đó
có đầy đủ điểm phạm vi.

90
00:04:19,370 --> 00:04:21,430
Và vì vậy chúng tôi muốn đến lớp
tất cả các psets bạn chỉ

91
00:04:21,430 --> 00:04:24,730
để đảm bảo rằng phạm vi của bạn
ở đó và bạn đang cố gắng cho họ.

92
00:04:24,730 --> 00:04:29,150
Vì vậy, ngay cả khi nó là muộn, bạn sẽ vẫn
có được tín dụng cho phạm vi điểm, tôi nghĩ.

93
00:04:29,150 --> 00:04:33,730
>> Vì vậy, đạo đức của câu chuyện là, làm cho
bảo psets của bạn đang ở đúng thời gian.

94
00:04:33,730 --> 00:04:38,350
Và nếu họ không ở trên thời gian,
biết rằng nó không phải là tuyệt vời.

95
00:04:38,350 --> 00:04:41,678
Vâng, trước khi đi tiếp, không ai có
bất kỳ câu hỏi về phản hồi pset?

96
00:04:41,678 --> 00:04:42,178
Yeah.

97
00:04:42,178 --> 00:04:43,630
>> Đung Bạn nói chúng tôi
có thể thả một trong những psets?

98
00:04:43,630 --> 00:04:44,296
>> Andi PENG: Yeah.

99
00:04:44,296 --> 00:04:47,050
Vì vậy, có chín psets tổng thể
trong quá trình của các học kỳ.

100
00:04:47,050 --> 00:04:50,610
Và nếu bạn có phạm vi
points-- quá phạm vi chỉ là,

101
00:04:50,610 --> 00:04:53,567
khá nhiều, bạn đang cố các
vấn đề, là bạn đưa trong thời gian,

102
00:04:53,567 --> 00:04:56,150
bạn đang hiển thị mà bạn đã
chứng minh bạn đã đọc spec.

103
00:04:56,150 --> 00:04:57,191
Đó là khá nhiều phạm vi.

104
00:04:57,191 --> 00:04:59,370
Và nếu bạn đang thực hiện
phạm vi điểm, chúng tôi

105
00:04:59,370 --> 00:05:03,360
có thể thả thấp nhất
một ra khỏi phạm vi đầy đủ.

106
00:05:03,360 --> 00:05:06,790
Vì vậy, đó là lợi thế của bạn để
hoàn thành và cố gắng mỗi pset.

107
00:05:06,790 --> 00:05:10,320
>> Ngay cả upload-- nếu không ai trong số
họ làm việc, tải lên tất cả.

108
00:05:10,320 --> 00:05:13,711
Và sau đó chúng tôi sẽ hy vọng có thể
cung cấp cho bạn một số những điểm trở lại.

109
00:05:13,711 --> 00:05:14,210
Mát.

110
00:05:14,210 --> 00:05:16,780
Bất kỳ câu hỏi khác?

111
00:05:16,780 --> 00:05:17,840
Thật tuyệt.

112
00:05:17,840 --> 00:05:21,960
>> Thứ hai, văn phòng hours-- một vài
ghi chú nhanh chóng về giờ làm việc.

113
00:05:21,960 --> 00:05:24,300
Vì vậy, đầu tiên, đi vào đầu tuần.

114
00:05:24,300 --> 00:05:26,909
Không ai bao giờ ở
giờ làm việc vào thứ Hai.

115
00:05:26,909 --> 00:05:28,700
Christabel đến
giờ làm việc đêm qua.

116
00:05:28,700 --> 00:05:29,691
Yeah, Christabel.

117
00:05:29,691 --> 00:05:32,190
Và những gì mà chúng ta đã có tại văn phòng
giờ đêm qua, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> Đung Chúng tôi đã có kem.

119
00:05:33,020 --> 00:05:36,160
>> Andi PENG: Vì vậy, đó là đúng, chúng tôi đã có
kem tại văn phòng giờ đêm qua.

120
00:05:36,160 --> 00:05:39,390
Trong khi tôi không thể hứa với bạn rằng
chúng tôi sẽ có kem vào giờ văn phòng

121
00:05:39,390 --> 00:05:43,230
mỗi tuần, những gì tôi có thể hứa với bạn
là sẽ có một cách đáng kể

122
00:05:43,230 --> 00:05:45,380
sinh viên tốt hơn để tỷ lệ TA.

123
00:05:45,380 --> 00:05:47,650
Giống như VN, nó giống như 3-1.

124
00:05:47,650 --> 00:05:50,350
Trong khi đó, độ tương phản mà với
Thứ năm, bạn đã có khoảng 150

125
00:05:50,350 --> 00:05:52,830
thực sự nhấn mạnh trẻ em và không có kem.

126
00:05:52,830 --> 00:05:55,360
Và nó chỉ là không hiệu quả cho bất cứ ai.

127
00:05:55,360 --> 00:05:58,730
Vì vậy, đạo đức của câu chuyện là, đến sớm
đến giờ làm việc và những điều tốt đẹp

128
00:05:58,730 --> 00:06:00,310
sẽ xảy ra.

129
00:06:00,310 --> 00:06:02,110
>> Ngoài ra, đến chuẩn bị đặt câu hỏi.

130
00:06:02,110 --> 00:06:03,200
Bạn biết?

131
00:06:03,200 --> 00:06:05,420
Bất kể những gì hỗ trợ kỹ thuật, tôi
nghĩ, đã nói,

132
00:06:05,420 --> 00:06:10,710
chúng tôi đã nhận được một vài sinh viên
Những người đến hôm qua là, như, 10:50

133
00:06:10,710 --> 00:06:15,100
không đọc spec
được như thế giúp tôi, giúp tôi.

134
00:06:15,100 --> 00:06:18,200
Thật không may vào thời điểm đó, có
không nhiều, chúng tôi có thể làm gì để giúp đỡ bạn.

135
00:06:18,200 --> 00:06:19,590
Vì vậy, xin vui lòng đến vào đầu tuần.

136
00:06:19,590 --> 00:06:22,040
Hãy đến sớm để giờ hành chính.

137
00:06:22,040 --> 00:06:23,350
Hãy chuẩn bị sẵn sàng để đặt câu hỏi.

138
00:06:23,350 --> 00:06:25,310
Hãy chắc chắn là bạn, là
một sinh viên, là nơi

139
00:06:25,310 --> 00:06:27,620
bạn cần phải để các
Hỗ trợ kỹ thuật có thể hướng dẫn bạn trên,

140
00:06:27,620 --> 00:06:32,850
đó là những gì giờ văn phòng
nên được phân bổ cho.

141
00:06:32,850 --> 00:06:37,380
>> Thứ hai, vì vậy tôi biết giáo sư
muốn chúng ta ngạc nhiên với các bài kiểm tra.

142
00:06:37,380 --> 00:06:39,439
Tôi đã có một giáo sư người
như, yo, bằng cách này,

143
00:06:39,439 --> 00:06:41,230
nhớ giữa kì
bạn có vào thứ hai tới.

144
00:06:41,230 --> 00:06:42,855
Vâng, tôi đã không biết về giữa kì.

145
00:06:42,855 --> 00:06:45,630
Vì vậy, tôi sẽ được rằng TA
nhắc nhở bạn rằng tất cả các bài kiểm tra

146
00:06:45,630 --> 00:06:47,270
0-- vì, bạn biết đấy, chúng tôi CS.

147
00:06:47,270 --> 00:06:50,730
Bây giờ chúng ta đã mảng làm, bạn sẽ có được
tại sao nó đố 0, không phải thi đố 1, eh?

148
00:06:50,730 --> 00:06:51,320
ĐƯỢC.

149
00:06:51,320 --> 00:06:52,490
Oh, tôi đã nhận một số cười thầm rằng một ngày.

150
00:06:52,490 --> 00:06:53,120
ĐƯỢC.

151
00:06:53,120 --> 00:06:59,710
>> Vì vậy, đố 0 sẽ October 14 nếu
bạn đang ở trong phần thứ hai-thứ tư

152
00:06:59,710 --> 00:07:02,920
và 15 tháng 10, nếu bạn đang ở trong
phần thứ ba, thứ năm.

153
00:07:02,920 --> 00:07:05,630
Điều này không áp dụng cho
những người bạn ở Harvard

154
00:07:05,630 --> 00:07:10,350
who-- Tôi nghĩ rằng tất cả các bạn sẽ có
dùng câu đố của bạn vào ngày 14.

155
00:07:10,350 --> 00:07:13,560
>> Vì vậy, yeah, tuần tới, nếu
David, trong bài giảng, đi,

156
00:07:13,560 --> 00:07:15,747
yeah, vì vậy về điều đó
đố tuần tới, tất cả các bạn

157
00:07:15,747 --> 00:07:17,580
sẽ không bị sốc vì
bạn đã đến phần

158
00:07:17,580 --> 00:07:19,664
và bạn biết rằng bạn
đố 0 là trong hai tuần.

159
00:07:19,664 --> 00:07:21,580
Và chúng tôi sẽ phải xem xét lại
phiên họp và tất cả mọi thứ.

160
00:07:21,580 --> 00:07:26,360
Vì vậy, không phải lo lắng về
sợ hãi cho điều đó.

161
00:07:26,360 --> 00:07:29,890
Bất kỳ câu hỏi before-- bất kỳ câu hỏi
ở tất cả các vấn đề liên quan đến hậu cần,

162
00:07:29,890 --> 00:07:32,591
chấm điểm, giờ làm việc, phần?

163
00:07:32,591 --> 00:07:33,090
Yeah.

164
00:07:33,090 --> 00:07:35,100
>> Đung Vì vậy, các bài kiểm tra là
sẽ có trong bài giảng?

165
00:07:35,100 --> 00:07:35,766
>> Andi PENG: Yeah.

166
00:07:35,766 --> 00:07:39,460
Vì vậy, các bài kiểm tra, tôi nghĩ, là 60
phút được phân bổ trong đó khe thời gian

167
00:07:39,460 --> 00:07:42,240
mà bạn sẽ chỉ mất
trong giảng đường.

168
00:07:42,240 --> 00:07:44,810
Vì vậy, bạn không cần phải đi vào
trên, như, một ngẫu nhiên 07:00.

169
00:07:44,810 --> 00:07:46,140
Tất cả đều tốt.

170
00:07:46,140 --> 00:07:47,100
Yeah.

171
00:07:47,100 --> 00:07:50,060
Mát.

172
00:07:50,060 --> 00:07:50,840
>> Được rồi.

173
00:07:50,840 --> 00:07:54,330
Vì vậy, chúng ta sẽ
giới thiệu một khái niệm để bạn

174
00:07:54,330 --> 00:08:00,760
tuần này rằng David có đã loại
của đụng vào trong bài giảng trong tuần vừa qua.

175
00:08:00,760 --> 00:08:02,010
Nó được gọi là GDB.

176
00:08:02,010 --> 00:08:05,570
Và bao nhiêu người bạn, trong khi ở
quá trình viết psets của bạn,

177
00:08:05,570 --> 00:08:09,981
đã nhận thấy một nút lớn mà nói
"Debug" trên đỉnh của IDE của bạn?

178
00:08:09,981 --> 00:08:10,480
ĐƯỢC.

179
00:08:10,480 --> 00:08:13,770
Vì vậy, bây giờ chúng ta sẽ thực sự có được khai quật
những bí ẩn của những nút mà thực sự

180
00:08:13,770 --> 00:08:14,270
làm.

181
00:08:14,270 --> 00:08:16,790
Và tôi đảm bảo với bạn, nó là một
xinh đẹp, điều đẹp đẽ.

182
00:08:16,790 --> 00:08:20,740
>> Vì vậy, cho đến bây giờ, tôi nghĩ rằng
có được hai điều

183
00:08:20,740 --> 00:08:23,320
sinh viên đã thường
làm khi gỡ lỗi psets.

184
00:08:23,320 --> 00:08:27,635
Một, họ hoặc thêm vào
printf () - vì vậy mỗi vài dòng,

185
00:08:27,635 --> 00:08:29,760
họ thêm vào một printf () -
oh, biến này là gì?

186
00:08:29,760 --> 00:08:32,551
Oh, biến này là gì now--
và bạn loại thấy sự tiến triển

187
00:08:32,551 --> 00:08:33,940
mã của bạn khi nó chạy.

188
00:08:33,940 --> 00:08:37,030
Hoặc phương pháp thứ hai trẻ em làm là
rằng họ chỉ viết toàn bộ điều

189
00:08:37,030 --> 00:08:38,610
và sau đó đi như thế này ở cuối.

190
00:08:38,610 --> 00:08:39,970
Hy vọng rằng nó hoạt động.

191
00:08:39,970 --> 00:08:44,851
Tôi đảm bảo với bạn, GDB là tốt hơn
hơn cả các phương pháp đó.

192
00:08:44,851 --> 00:08:45,350
Yeah.

193
00:08:45,350 --> 00:08:46,980
Vì vậy, đây sẽ là người bạn tốt nhất của bạn mới.

194
00:08:46,980 --> 00:08:51,780
Bởi vì đó là một điều đẹp
trực quan hiển thị cả

195
00:08:51,780 --> 00:08:54,850
mã những gì bạn đang làm
tại một điểm cụ thể

196
00:08:54,850 --> 00:08:57,486
cũng như tất cả những gì của bạn
biến được thực hiện,

197
00:08:57,486 --> 00:08:59,610
giống như những gì giá trị của họ,
ở thời điểm cụ thể.

198
00:08:59,610 --> 00:09:02,670
Và bằng cách này, bạn có thể thực sự
đặt breakpoint trong mã của bạn.

199
00:09:02,670 --> 00:09:04,350
Bạn có thể chạy qua từng dòng.

200
00:09:04,350 --> 00:09:07,324
Và GDB sẽ chỉ có cho
bạn, hiển thị cho bạn,

201
00:09:07,324 --> 00:09:09,490
những gì tất cả các biến của bạn
được, họ đang làm gì,

202
00:09:09,490 --> 00:09:10,656
những gì đang xảy ra trong các mã.

203
00:09:10,656 --> 00:09:13,240
Và trong một cách như vậy, đó là
để dễ dàng hơn để xem

204
00:09:13,240 --> 00:09:17,120
những gì đang xảy ra thay vì printf-ing
hoặc viết xuống báo cáo của bạn.

205
00:09:17,120 --> 00:09:19,160
>> Vì vậy, chúng tôi sẽ làm một ví dụ về điều này sau.

206
00:09:19,160 --> 00:09:20,660
Vì vậy, điều này có vẻ trừu tượng chút.

207
00:09:20,660 --> 00:09:23,490
Không có lo lắng, chúng tôi sẽ làm ví dụ.

208
00:09:23,490 --> 00:09:29,170
Và do đó, về cơ bản, ba lớn nhất,
được sử dụng nhiều chức năng mà bạn sẽ cần trong GDB

209
00:09:29,170 --> 00:09:32,500
Tiếp theo là, Bước qua,
và Bước vào nút.

210
00:09:32,500 --> 00:09:34,860
Tôi sẽ đi qua
ở đó, trên thực tế, ngay bây giờ.

211
00:09:34,860 --> 00:09:40,930
>> Vì vậy, tất cả các bạn có thể thấy rằng
hay tôi nên phóng to một chút?

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
Ở phía sau, bạn có thể nhìn thấy không?

214
00:09:44,470 --> 00:09:45,730
Tôi có nên phóng to?

215
00:09:45,730 --> 00:09:46,480
Chỉ một ít thôi?

216
00:09:46,480 --> 00:09:49,390
OK, mát mẻ.

217
00:09:49,390 --> 00:09:50,280
Hiện chúng tôi đi.

218
00:09:50,280 --> 00:09:50,960
ĐƯỢC.

219
00:09:50,960 --> 00:09:57,000
>> Vì vậy, tôi có, ở đây, tôi
thực hiện cho tham lam.

220
00:09:57,000 --> 00:10:01,430
Và trong khi rất nhiều các bạn đã viết
tham lam trong khi vòng lặp form-- đó

221
00:10:01,430 --> 00:10:04,890
là một cách hoàn toàn chấp nhận làm
it-- một cách khác để làm điều đó là để đơn giản

222
00:10:04,890 --> 00:10:06,280
chia trong modulo.

223
00:10:06,280 --> 00:10:09,290
Bởi vì sau đó bạn có thể có của bạn
giá trị và sau đó có còn lại của bạn.

224
00:10:09,290 --> 00:10:11,150
Và sau đó bạn có thể chỉ
thêm nó tất cả cùng nhau.

225
00:10:11,150 --> 00:10:13,390
Liệu các logic của những gì tôi đang làm
ở đây có ý nghĩa với tất cả mọi người,

226
00:10:13,390 --> 00:10:14,117
trước khi chúng tôi bắt đầu?

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
Loại?

229
00:10:17,980 --> 00:10:18,710
Mát.

230
00:10:18,710 --> 00:10:19,210
Thật tuyệt.

231
00:10:19,210 --> 00:10:21,290
Đó là một mảnh khá sexy
mã, tôi sẽ nói.

232
00:10:21,290 --> 00:10:23,502
Giống như tôi đã nói, David, trong
giảng bài, sau một thời gian,

233
00:10:23,502 --> 00:10:25,960
tất cả các bạn sẽ bắt đầu nhìn thấy mã
như một cái gì đó là đẹp.

234
00:10:25,960 --> 00:10:29,950
Và đôi khi bạn thấy đẹp
mã, đó là một cảm giác tuyệt vời như vậy.

235
00:10:29,950 --> 00:10:35,410
>> Vì vậy, tuy nhiên, trong khi mã này là rất
xinh đẹp, nó không hoạt động đúng cách.

236
00:10:35,410 --> 00:10:37,750
Vì vậy, chúng ta hãy chạy check50 về điều này.

237
00:10:37,750 --> 00:10:39,440
Kiểm tra 50 20-- oop.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2?

240
00:10:43,720 --> 00:10:44,990
Là pset2 đó?

241
00:10:44,990 --> 00:10:46,870
Yeah.

242
00:10:46,870 --> 00:10:47,520
Oh, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
ĐƯỢC.

245
00:10:52,890 --> 00:10:53,900
Vì vậy, chúng tôi chạy check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> Và như các bạn có thể thấy ở đây,
nó rớt một vài trường hợp.

248
00:11:07,170 --> 00:11:10,165
Và đối với một số bạn, trong
trình làm bộ vấn đề của bạn,

249
00:11:10,165 --> 00:11:11,110
bạn giống như, ah, tại sao không phải là nó làm việc.

250
00:11:11,110 --> 00:11:13,318
Tại sao nó làm việc cho một số
giá trị nhưng không phải cho người khác?

251
00:11:13,318 --> 00:11:17,760
Vâng, GDB sẽ giúp con bạn
ra lý do tại sao những yếu tố đầu vào không được làm việc.

252
00:11:17,760 --> 00:11:18,320
>> ĐƯỢC.

253
00:11:18,320 --> 00:11:21,640
Vì vậy, chúng ta hãy xem, một trong những
kiểm tra tôi đã thất bại trong check50

254
00:11:21,640 --> 00:11:24,920
là giá trị đầu vào của 0,41.

255
00:11:24,920 --> 00:11:27,830
Vì vậy, câu trả lời chính xác mà
bạn cần phải nhận là 4.

256
00:11:27,830 --> 00:11:33,090
Nhưng thay vì những gì tôi đang in ra
là 3-n, đó là không đúng.

257
00:11:33,090 --> 00:11:36,190
Vì vậy, chúng ta hãy chỉ chạy này bằng tay, chỉ
chắc chắn rằng check50 đang làm việc.

258
00:11:36,190 --> 00:11:36,940
Hãy làm ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Rất tiếc, tôi phải thực hiện tham lam.

261
00:11:43,340 --> 00:11:43,840
Hiện chúng tôi đi.

262
00:11:43,840 --> 00:11:44,381
Bây giờ ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> Còn nợ bao nhiêu?

265
00:11:47,670 --> 00:11:49,550
Hãy làm 0,41.

266
00:11:49,550 --> 00:11:52,590
Và vâng, chúng ta thấy ở đây
mà nó xuất ra 3

267
00:11:52,590 --> 00:11:55,160
khi câu trả lời chính xác,
trong thực tế, nên là 4.

268
00:11:55,160 --> 00:12:01,460
Vì vậy, hãy nhập GDB và xem cách chúng tôi
có thể đi về sửa chữa vấn đề này.

269
00:12:01,460 --> 00:12:03,992
>> Vì vậy, bước đầu tiên trong
luôn luôn gỡ lỗi mã của bạn

270
00:12:03,992 --> 00:12:05,950
là để thiết lập một breakpoint,
hoặc một điểm mà tại đó bạn

271
00:12:05,950 --> 00:12:09,079
muốn máy tính hoặc các
debugger để bắt đầu tìm kiếm tại.

272
00:12:09,079 --> 00:12:11,120
Vì vậy, nếu bạn không thực sự
biết vấn đề của bạn là,

273
00:12:11,120 --> 00:12:14,670
thường, điều điển hình chúng ta muốn
làm là để đặt breakpoint của chúng tôi tại chính.

274
00:12:14,670 --> 00:12:18,520
Vì vậy, nếu các bạn có thể thấy điều này
nút màu đỏ ở ngay đó,

275
00:12:18,520 --> 00:12:22,860
vâng, tôi đã được thiết lập một
breakpoint cho các chức năng chính.

276
00:12:22,860 --> 00:12:24,130
Tôi bấm vào đó.

277
00:12:24,130 --> 00:12:26,130
>> Và sau đó tôi có thể đi đến nút gỡ lỗi của tôi.

278
00:12:26,130 --> 00:12:27,036
Tôi nhấn nút đó.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Hãy để tôi thu nhỏ trở lại nếu tôi có thể.

281
00:12:36,555 --> 00:12:38,020
Hiện chúng tôi đi.

282
00:12:38,020 --> 00:12:40,730
Vì vậy, chúng ta có, ở đây, một bảng điều khiển ở bên phải.

283
00:12:40,730 --> 00:12:43,680
Tôi xin lỗi, kẻ ở phía sau, bạn
có thể không thực sự thấy thực sự tốt.

284
00:12:43,680 --> 00:12:49,090
Nhưng về cơ bản, tất cả
bảng bên phải này đang làm

285
00:12:49,090 --> 00:12:53,130
được theo dõi của cả hai được đánh dấu
dòng, đó là các dòng mã

286
00:12:53,130 --> 00:12:56,640
mà hiện máy tính đang chạy,
cũng như tất cả các biến của bạn

287
00:12:56,640 --> 00:12:57,600
Xuống đây.

288
00:12:57,600 --> 00:13:00,487
>> Vì vậy, bạn đã có xu, tiền xu, n,
tất cả các tuyên bố với những thứ khác nhau

289
00:13:00,487 --> 00:13:01,070
tại điểm này.

290
00:13:01,070 --> 00:13:04,850
Không có lo lắng, bởi vì chúng tôi đã không thực sự
khởi tạo chúng cho bất kỳ biến nào.

291
00:13:04,850 --> 00:13:07,200
Vì vậy, trong máy tính của bạn, bạn
máy tính chỉ là nhìn thấy,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 là chức năng được sử dụng cuối cùng
mà không gian bộ nhớ trong máy tính của tôi.

293
00:13:14,376 --> 00:13:16,000
Và đó là nơi mà xu hiện tại là.

294
00:13:16,000 --> 00:13:19,360
Nhưng không một khi bạn chạy các mã
nó nên trở thành khởi tạo.

295
00:13:19,360 --> 00:13:24,110
>> Vì vậy, hãy đi qua, dòng bởi
dòng, những gì đang xảy ra ở đây.

296
00:13:24,110 --> 00:13:25,350
ĐƯỢC.

297
00:13:25,350 --> 00:13:29,400
Vì vậy, ở đây là ba
nút mà tôi vừa giải thích.

298
00:13:29,400 --> 00:13:34,090
Bạn có Play, hoặc các chức năng Run,
nút, bạn có nút Step hơn,

299
00:13:34,090 --> 00:13:36,600
và bạn cũng có nút Step vào.

300
00:13:36,600 --> 00:13:41,260
Và về cơ bản, cả ba
họ chỉ cần đi qua mã của bạn

301
00:13:41,260 --> 00:13:42,690
và làm những việc khác nhau.

302
00:13:42,690 --> 00:13:45,680
>> Vì vậy, thông thường, khi bạn gỡ lỗi,
chúng tôi không muốn chỉ cần nhấn Play,

303
00:13:45,680 --> 00:13:47,930
vì Play sẽ chỉ chạy
mã của bạn để kết thúc của nó.

304
00:13:47,930 --> 00:13:49,070
Và sau đó bạn sẽ không thực sự
biết vấn đề của bạn

305
00:13:49,070 --> 00:13:51,432
là trừ khi bạn thiết lập nhiều các điểm ngắt.

306
00:13:51,432 --> 00:13:53,890
Nếu bạn thiết lập nhiều các điểm ngắt,
nó sẽ chỉ tự động

307
00:13:53,890 --> 00:13:56,030
chạy từ một breakpoint,
kế tiếp, đến tiếp theo.

308
00:13:56,030 --> 00:13:58,030
Nhưng trong trường hợp này, chúng tôi đã
chỉ một mà, bởi vì chúng tôi

309
00:13:58,030 --> 00:13:59,970
muốn làm việc theo cách của chúng tôi
từ trên xuống dưới.

310
00:13:59,970 --> 00:14:04,830
Vì vậy, chúng ta sẽ bỏ qua nút
ngay bây giờ cho các mục đích của chương trình này.

311
00:14:04,830 --> 00:14:08,230
>> Vì vậy, Bước qua chức năng chỉ
bước trên mỗi dòng

312
00:14:08,230 --> 00:14:11,510
và cho bạn biết những gì
máy tính là làm.

313
00:14:11,510 --> 00:14:14,630
Bước vào chức năng đi
vào các chức năng thực tế

314
00:14:14,630 --> 00:14:16,000
đó là trên dòng code của bạn.

315
00:14:16,000 --> 00:14:19,070
Vì vậy, ví dụ, như printf (),
đó là một chức năng, phải không?

316
00:14:19,070 --> 00:14:21,980
Nếu tôi muốn thể chất bước
vào printf () chức năng,

317
00:14:21,980 --> 00:14:25,610
Tôi thực sự sẽ đi vào chi tiết của
mã nơi printf () được viết và xem

318
00:14:25,610 --> 00:14:26,730
những gì đang xảy ra ở đó.

319
00:14:26,730 --> 00:14:29,924
>> Nhưng thông thường, chúng ta giả định rằng
mã mà chúng tôi cung cấp cho bạn các công trình.

320
00:14:29,924 --> 00:14:31,340
Chúng tôi giả định printf () đang làm việc.

321
00:14:31,340 --> 00:14:33,170
Chúng tôi giả định rằng getInt () đang làm việc.

322
00:14:33,170 --> 00:14:35,170
Vì vậy, không cần thiết phải
bước vào những chức năng.

323
00:14:35,170 --> 00:14:37,170
Nhưng nếu có chức năng
mà bạn tự viết

324
00:14:37,170 --> 00:14:39,060
mà bạn muốn kiểm tra
ra những gì đang xảy ra,

325
00:14:39,060 --> 00:14:41,200
bạn sẽ muốn bước
vào chức năng đó.

326
00:14:41,200 --> 00:14:43,940
>> Vì vậy, ngay bây giờ chúng tôi chỉ cần đi
bước qua đoạn mã này.

327
00:14:43,940 --> 00:14:44,485
Vì vậy, chúng ta hãy xem.

328
00:14:44,485 --> 00:14:46,547
Oh, in ấn, "Oh hai, làm thế nào
nhiều thay đổi được nợ? "

329
00:14:46,547 --> 00:14:47,130
Chúng tôi không quan tâm.

330
00:14:47,130 --> 00:14:49,830
Chúng tôi biết đó là làm việc,
vì vậy chúng tôi bước qua nó.

331
00:14:49,830 --> 00:14:53,290
>> Vì vậy, n, mà là float của chúng tôi
chúng tôi đã initialized-- hoặc declared--

332
00:14:53,290 --> 00:14:56,810
lên ở đầu, chúng tôi hiện
bằng đó để GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Vì vậy, chúng ta hãy bước qua đó.

334
00:14:57,810 --> 00:14:59,580
Và chúng ta thấy tại
dưới đây, các chương trình

335
00:14:59,580 --> 00:15:03,360
đang thúc giục tôi để nhập vào một giá trị.

336
00:15:03,360 --> 00:15:08,580
Vì vậy, hãy nhập giá trị mà chúng ta muốn
để kiểm tra ở đây, đó là 0,41.

337
00:15:08,580 --> 00:15:09,160
Thật tuyệt.

338
00:15:09,160 --> 00:15:12,780
>> Vì vậy bây giờ n-- làm các bạn thấy
ở đây, tại bottom-- nó

339
00:15:12,780 --> 00:15:15,140
stored-- bởi vì chúng tôi
đã không làm tròn được nêu ra, đó là

340
00:15:15,140 --> 00:15:19,540
lưu trữ trong khổng lồ như thế này
float đó là 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
đó là đủ để chúng tôi gần
mục đích, ngay bây giờ, 0,41.

342
00:15:22,550 --> 00:15:26,090
Và sau đó chúng ta sẽ thấy sau này, khi chúng tôi
Tiếp tục đẩy mạnh hơn các chương trình,

343
00:15:26,090 --> 00:15:29,850
sau đây, n đã trở thành
tròn và xu đã trở thành 41.

344
00:15:29,850 --> 00:15:30,350
Thật tuyệt.

345
00:15:30,350 --> 00:15:32,230
Vì vậy, chúng ta biết rằng làm việc tròn của chúng tôi.

346
00:15:32,230 --> 00:15:34,700
Chúng tôi biết rằng chúng tôi có
số lượng chính xác của cent,

347
00:15:34,700 --> 00:15:36,990
vì vậy chúng tôi biết rằng đó là
không thực sự là vấn đề.

348
00:15:36,990 --> 00:15:40,050
>> Vì vậy, chúng tôi tiếp tục đẩy mạnh
vào trong chương trình này.

349
00:15:40,050 --> 00:15:40,900
Chúng tôi đi đây.

350
00:15:40,900 --> 00:15:46,139
Và như vậy sau khi dòng mã này, chúng tôi
nên biết bao nhiêu phần tư chúng tôi có.

351
00:15:46,139 --> 00:15:46,680
Chúng tôi bước qua.

352
00:15:46,680 --> 00:15:52,040
Và bạn nhìn thấy chúng tôi, trên thực tế, có một
quý bởi vì chúng tôi đã trừ 25

353
00:15:52,040 --> 00:15:53,790
từ giá trị ban đầu của chúng tôi là 41.

354
00:15:53,790 --> 00:15:55,890
Và chúng tôi có 16 trái cho xu của chúng tôi.

355
00:15:55,890 --> 00:15:58,830
>> Có phải mọi người hiểu như thế nào
chương trình được đẩy mạnh thông qua

356
00:15:58,830 --> 00:16:02,980
và tại sao xu đã trở thành 16
và tại sao, bây giờ, tiền xu đã trở thành 1?

357
00:16:02,980 --> 00:16:04,610
Được tất cả mọi người sau logic?

358
00:16:04,610 --> 00:16:05,110
Mát.

359
00:16:05,110 --> 00:16:07,860
Vì vậy, như trong thời điểm này,
làm việc của chương trình, phải không?

360
00:16:07,860 --> 00:16:09,797
Chúng tôi biết nó đang làm chính xác
những gì chúng ta muốn nó.

361
00:16:09,797 --> 00:16:11,880
Và chúng tôi đã không thực sự
phải in ra, oh, những gì

362
00:16:11,880 --> 00:16:14,430
là cent, ở thời điểm này,
là những gì đồng tiền vào thời điểm này.

363
00:16:14,430 --> 00:16:17,170
>> Chúng tôi tiếp tục đi qua các chương trình.

364
00:16:17,170 --> 00:16:18,100
Bước qua.

365
00:16:18,100 --> 00:16:18,620
Mát.

366
00:16:18,620 --> 00:16:19,700
Chúng tôi đi qua hào.

367
00:16:19,700 --> 00:16:20,200
Thật tuyệt.

368
00:16:20,200 --> 00:16:22,367
Chúng tôi thấy rằng nó được thực hiện
off $ 0,10 cho một đồng xu.

369
00:16:22,367 --> 00:16:23,450
Và bây giờ chúng tôi có hai đồng tiền.

370
00:16:23,450 --> 00:16:25,260
Đúng rồi.

371
00:16:25,260 --> 00:16:31,555
>> Chúng tôi đi qua đồng xu và chúng ta thấy
mà chúng tôi đã có trái qua cent.

372
00:16:31,555 --> 00:16:32,680
Hmm, đó là lạ.

373
00:16:32,680 --> 00:16:37,540
Up ở đây tại chương trình, tôi đã được yêu
đã trừ đồng xu của tôi.

374
00:16:37,540 --> 00:16:39,400
Có lẽ tôi chỉ là không
làm điều đó đúng tuyến.

375
00:16:39,400 --> 00:16:42,190
Và than ôi, bạn có thể nhìn thấy
ở đây, bởi vì chúng tôi biết

376
00:16:42,190 --> 00:16:44,360
rằng chúng ta đang bước
thông qua đường dây 32 và 33,

377
00:16:44,360 --> 00:16:50,560
đó là nơi mà chương trình chúng tôi
không đúng cách có biến chạy.

378
00:16:50,560 --> 00:16:55,136
Vì vậy, chúng ta có thể nhìn và thấy, oh,
Tôi trừ cent ở đây,

379
00:16:55,136 --> 00:16:57,010
nhưng tôi không thực sự
thêm vào giá trị đồng tiền của tôi.

380
00:16:57,010 --> 00:16:57,860
Tôi thêm để cent.

381
00:16:57,860 --> 00:17:00,234
Và tôi không muốn thêm vào
cent, tôi muốn thêm vào đồng tiền.

382
00:17:00,234 --> 00:17:05,420
Vì vậy, nếu chúng ta thay đổi mà để tiền xu,
chúng ta đã có một chương trình làm việc.

383
00:17:05,420 --> 00:17:06,730
Tôi có thể chạy check50.

384
00:17:06,730 --> 00:17:11,063
Bạn chỉ có thể thoát ra khỏi GDB đúng
ở đây và sau đó chạy check50 một lần nữa.

385
00:17:11,063 --> 00:17:11,938
Tôi chỉ có thể làm điều này.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Tôi phải làm cho tham lam.

388
00:17:18,480 --> 00:17:19,940
0,41.

389
00:17:19,940 --> 00:17:22,819
Và ở đây, nó đang in
ra câu trả lời đúng.

390
00:17:22,819 --> 00:17:26,569
>> Vì vậy, các bạn có thể thấy, GDB
là một công cụ thực sự mạnh mẽ

391
00:17:26,569 --> 00:17:29,940
khi chúng tôi có rất nhiều mã
xảy ra và rất nhiều biến

392
00:17:29,940 --> 00:17:32,510
rằng thật khó cho chúng tôi, như
một con người, để theo dõi.

393
00:17:32,510 --> 00:17:35,360
Các máy tính, trong GDB
debugger, có khả năng

394
00:17:35,360 --> 00:17:37,020
để theo dõi tất cả mọi thứ.

395
00:17:37,020 --> 00:17:40,480
Tôi biết, trong Visionaire, các bạn có thể
có thể đã đạt một số lỗi segmentation

396
00:17:40,480 --> 00:17:43,150
bởi vì bạn đang chạy
ngoài giới hạn của mảng của bạn.

397
00:17:43,150 --> 00:17:46,510
Trong ví dụ của Caesar, đó là
chính xác những gì tôi đã thực hiện ở đây.

398
00:17:46,510 --> 00:17:50,060
>> Vì vậy, tôi quên kiểm tra
điều gì sẽ xảy ra nếu tôi

399
00:17:50,060 --> 00:17:52,510
không có hai đối số dòng lệnh.

400
00:17:52,510 --> 00:17:53,880
Tôi chỉ không đưa vào tờ séc đó.

401
00:17:53,880 --> 00:17:57,380
Và do đó, nếu tôi chạy Debug-- tôi đặt
breakpoint của tôi sang phải ở đó.

402
00:17:57,380 --> 00:17:58,055
Tôi chạy Debug.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> ĐƯỢC.

405
00:18:16,550 --> 00:18:17,050
Yeah.

406
00:18:17,050 --> 00:18:20,350
Vì vậy, trên thực tế, GDB đã được yêu
đã nói với tôi có

407
00:18:20,350 --> 00:18:22,300
là một lỗi phân khúc đó.

408
00:18:22,300 --> 00:18:24,883
Tôi không biết những gì đang xảy ra
đúng đó, nhưng khi tôi chạy nó,

409
00:18:24,883 --> 00:18:25,590
nó đã làm việc.

410
00:18:25,590 --> 00:18:29,410
Khi bạn chạy dòng mã thông qua và
GDB có thể chỉ đột nhiên bỏ về bạn,

411
00:18:29,410 --> 00:18:31,540
đi lên và nhìn những gì các lỗi màu đỏ là.

412
00:18:31,540 --> 00:18:33,930
Nó sẽ cho bạn biết, hey, bạn
có một lỗi phân khúc,

413
00:18:33,930 --> 00:18:38,550
có nghĩa là bạn cố gắng truy cập
không gian trong một mảng không tồn tại.

414
00:18:38,550 --> 00:18:39,050
Yeah.

415
00:18:39,050 --> 00:18:43,280
>> Vì vậy, trong các vấn đề tiếp theo
thiết lập trong tuần này, các bạn

416
00:18:43,280 --> 00:18:45,600
có lẽ sẽ có rất nhiều
biến nổi xung quanh.

417
00:18:45,600 --> 00:18:48,560
Bạn sẽ không chắc chắn những gì
Chúng nghĩa là tại một thời điểm nhất định.

418
00:18:48,560 --> 00:18:53,560
Vì vậy, GDB thực sự sẽ giúp bạn trong việc tìm
hiểu những gì họ đang tất cả bằng

419
00:18:53,560 --> 00:18:55,940
và có thể thấy rằng thị.

420
00:18:55,940 --> 00:19:01,995
Có ai nhầm lẫn về cách
bất kỳ điều đó đã làm việc?

421
00:19:01,995 --> 00:19:02,495
Mát.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
Được rồi.

424
00:19:10,620 --> 00:19:14,260
Vì vậy, sau đó, chúng tôi
sẽ nhảy ngay

425
00:19:14,260 --> 00:19:17,562
vào bốn khác nhau
loại của các loại cho tuần này.

426
00:19:17,562 --> 00:19:19,520
Làm thế nào nhiều bạn, đầu tiên
hết, trước khi chúng ta bắt đầu,

427
00:19:19,520 --> 00:19:23,020
đã đọc toàn bộ spec cho pset3?

428
00:19:23,020 --> 00:19:23,824
ĐƯỢC.

429
00:19:23,824 --> 00:19:24,740
Tôi tự hào về các bạn.

430
00:19:24,740 --> 00:19:29,110
Điều đó giống như một nửa của lớp, mà
là nhiều hơn đáng kể so với thời gian trước.

431
00:19:29,110 --> 00:19:33,950
>> Vì vậy, đó là tuyệt vời, bởi vì khi
chúng ta nói về nội dung

432
00:19:33,950 --> 00:19:36,170
trong lecture-- hoặc xin lỗi,
trong section-- tôi thích

433
00:19:36,170 --> 00:19:38,210
để liên quan rất nhiều mà
trở lại với những gì các pset là

434
00:19:38,210 --> 00:19:40,210
và làm thế nào bạn muốn
thực hiện điều đó trong pset của bạn.

435
00:19:40,210 --> 00:19:42,400
Vì vậy, nếu bạn đến gặp
đọc spec, nó sẽ thấy

436
00:19:42,400 --> 00:19:45,510
được dễ dàng hơn nhiều cho bạn để hiểu
những gì tôi đang nói về khi tôi nói,

437
00:19:45,510 --> 00:19:48,720
oh hey, điều này có thể là một thực sự
nơi tốt để thực hiện việc này.

438
00:19:48,720 --> 00:19:52,870
Vì vậy, những người bạn của những người đã đọc
spec biết rằng, như là một phần của pset của bạn,

439
00:19:52,870 --> 00:19:54,900
bạn sẽ phải
viết một kiểu loại.

440
00:19:54,900 --> 00:19:58,670
Vì vậy, điều này có thể rất hữu ích
cho rất nhiều bạn ngày hôm nay.

441
00:19:58,670 --> 00:20:01,760
>> Vì vậy, chúng tôi sẽ bắt đầu với,
về cơ bản, kiểu đơn giản nhất

442
00:20:01,760 --> 00:20:04,580
các loại, các loại lựa chọn.

443
00:20:04,580 --> 00:20:06,800
Các thuật toán điển hình cho
làm thế nào chúng tôi đi về điều này

444
00:20:06,800 --> 00:20:10,460
is-- David đã đi qua các tất cả trong
bài giảng, vì vậy tôi sẽ nhanh chóng di chuyển dọc

445
00:20:10,460 --> 00:20:13,900
here-- cơ bản là, bạn
có một mảng các giá trị.

446
00:20:13,900 --> 00:20:17,170
Và sau đó bạn tìm thấy
giá trị nhỏ nhất không được phân loại

447
00:20:17,170 --> 00:20:20,200
và bạn trao đổi các giá trị đó với
giá trị chưa phân loại đầu tiên.

448
00:20:20,200 --> 00:20:22,700
Và sau đó bạn chỉ cần giữ lặp đi lặp lại
với phần còn lại của danh sách của bạn.

449
00:20:22,700 --> 00:20:25,740
>> Và đây là một lời giải thích trực quan
làm thế nào mà có thể làm việc.

450
00:20:25,740 --> 00:20:30,460
Vì vậy, ví dụ, nếu chúng ta bắt đầu
với một mảng của năm yếu tố, chỉ số

451
00:20:30,460 --> 00:20:35,910
0-4, có 3, 5, 2, 6, và 4 giá trị
đặt trong array-- vậy ngay bây giờ,

452
00:20:35,910 --> 00:20:38,530
chúng tôi chỉ cần đi để giả
rằng họ đang tất cả được phân loại

453
00:20:38,530 --> 00:20:41,130
bởi vì chúng tôi đã không kiểm tra khác.

454
00:20:41,130 --> 00:20:44,130
>> Vậy làm thế nào một loại lựa chọn sẽ
công việc là nó sẽ đầu tiên

455
00:20:44,130 --> 00:20:46,800
chạy qua toàn bộ
của mảng được phân loại.

456
00:20:46,800 --> 00:20:49,120
Nó sẽ nhận ra giá trị nhỏ nhất.

457
00:20:49,120 --> 00:20:51,750
Trong trường hợp này, 3, bên phải
bây giờ, là nhỏ nhất.

458
00:20:51,750 --> 00:20:52,680
Nó được cho 5.

459
00:20:52,680 --> 00:20:55,620
Nope, 5 là không lớn than--
hoặc xin lỗi, không phải là ít than-- 3.

460
00:20:55,620 --> 00:20:57,779
Vì vậy, giá trị tối thiểu vẫn là 3.

461
00:20:57,779 --> 00:20:58,695
Và sau đó bạn sẽ có được đến 2.

462
00:20:58,695 --> 00:21:00,990
Các máy tính thấy, oh, 2 là ít hơn 3.

463
00:21:00,990 --> 00:21:02,750
2 bây giờ phải là giá trị tối thiểu.

464
00:21:02,750 --> 00:21:06,630
Và do đó, 2 giao dịch hoán đổi với giá trị đầu tiên.

465
00:21:06,630 --> 00:21:10,702
>> Vì vậy, một đường chuyền sau đó, chúng tôi thực sự thấy
rằng 2 và 3 được đổi chỗ.

466
00:21:10,702 --> 00:21:13,910
Và chúng tôi chỉ cần đi để tiếp tục làm
này một lần nữa với phần còn lại của mảng.

467
00:21:13,910 --> 00:21:17,660
Vì vậy, chúng ta sẽ chỉ cần chạy qua
bốn chỉ số cuối cùng của mảng.

468
00:21:17,660 --> 00:21:20,670
Chúng ta sẽ thấy rằng 3 là
giá trị nhỏ nhất tiếp theo.

469
00:21:20,670 --> 00:21:23,240
Vì vậy, chúng tôi đang đi để trao đổi điều đó với 4.

470
00:21:23,240 --> 00:21:26,900
Và sau đó, chúng tôi chỉ cần đi để giữ
chạy qua cho đến khi, cuối cùng, bạn

471
00:21:26,900 --> 00:21:33,730
để có được một mảng được sắp xếp trong đó
2, 3, 4, 5, 6 trong số tất cả được sắp xếp.

472
00:21:33,730 --> 00:21:37,530
Có tất cả mọi người hiểu được logic
làm thế nào một loại lựa chọn công trình?

473
00:21:37,530 --> 00:21:39,669
>> Bạn chỉ có một số loại
của một giá trị tối thiểu.

474
00:21:39,669 --> 00:21:41,210
Bạn đang theo dõi của những gì được.

475
00:21:41,210 --> 00:21:45,170
Và bất cứ khi nào bạn tìm thấy nó, bạn thay đổi nó
với giá trị đầu tiên trong array--

476
00:21:45,170 --> 00:21:48,740
hoặc, không phải là value-- đầu tiên
giá trị tiếp theo trong mảng.

477
00:21:48,740 --> 00:21:50,150
Mát.

478
00:21:50,150 --> 00:21:55,460
>> Vì vậy, như các bạn loại
thấy từ một cái nhìn ngắn gọn,

479
00:21:55,460 --> 00:21:58,450
chúng ta sẽ giả này ra.

480
00:21:58,450 --> 00:22:02,510
Vì vậy, nếu các bạn ở phía sau muốn
tạo thành một nhóm, tất cả mọi người ở một bảng

481
00:22:02,510 --> 00:22:06,170
có thể hình thành một đối tác ít, tôi sẽ
để cung cấp cho các bạn giống như ba phút

482
00:22:06,170 --> 00:22:08,190
chỉ nói chuyện qua
logic, tiếng Anh,

483
00:22:08,190 --> 00:22:14,161
làm thế nào chúng ta có thể có thể thực hiện
giả để viết một loại lựa chọn.

484
00:22:14,161 --> 00:22:14,910
Và có kẹo.

485
00:22:14,910 --> 00:22:16,118
Hãy đến và nhận được kẹo.

486
00:22:16,118 --> 00:22:19,520
Nếu bạn đang ở phía sau và bạn muốn
kẹo, tôi có thể ném kẹo vào bạn.

487
00:22:19,520 --> 00:22:22,850
Trên thực tế, làm you-- mát.

488
00:22:22,850 --> 00:22:23,552
Ồ xin lỗi.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
ĐƯỢC.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Vì vậy, nếu chúng ta muốn, như
một lớp học, ghi giả

493
00:25:27,140 --> 00:25:30,466
để làm thế nào người ta có thể tiếp cận
vấn đề này, chỉ cảm thấy miễn phí.

494
00:25:30,466 --> 00:25:32,340
Tôi sẽ chỉ đi xung quanh và,
theo thứ tự, yêu cầu các nhóm

495
00:25:32,340 --> 00:25:35,065
cho các dòng tiếp theo của
những gì chúng ta nên làm.

496
00:25:35,065 --> 00:25:37,840
Vì vậy, nếu các bạn muốn bắt đầu
tắt, điều đầu tiên là những gì

497
00:25:37,840 --> 00:25:40,600
Phải làm gì khi bạn đang cố gắng để
thực hiện một cách để giải quyết chương trình này

498
00:25:40,600 --> 00:25:43,480
để chọn lọc sắp xếp một danh sách?

499
00:25:43,480 --> 00:25:46,349
Hãy chỉ giả sử chúng ta
có một mảng, tất cả phải không?

500
00:25:46,349 --> 00:25:49,088
>> Đung Bạn muốn tạo ra một số
loại [Không nghe thấy] mà bạn

501
00:25:49,088 --> 00:25:50,420
chạy qua toàn bộ mảng của bạn.

502
00:25:50,420 --> 00:25:51,128
>> Andi PENG: Đúng vậy.

503
00:25:51,128 --> 00:25:54,100
Vì vậy, bạn sẽ muốn lặp
qua mọi không gian, phải không?

504
00:25:54,100 --> 00:26:05,490
Vì vậy, tuyệt vời.

505
00:26:05,490 --> 00:26:08,600
Nếu các bạn muốn để cho tôi
tiếp theo line-- yeah, ở phía sau.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> Đung Kiểm tra xem chúng
tất cả cho nhỏ nhất.

508
00:26:13,290 --> 00:26:14,248
>> Andi PENG: Hiện chúng tôi đi.

509
00:26:14,248 --> 00:26:17,438
Vì vậy, chúng tôi muốn đi qua và kiểm tra
xem những gì giá trị tối thiểu là, phải không?

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Tôi sẽ viết tắt đó để "min".

512
00:26:24,840 --> 00:26:27,658
Những gì các bạn muốn làm sau khi
bạn đã tìm thấy những giá trị tối thiểu?

513
00:26:27,658 --> 00:26:28,533
>> Đung [Không nghe thấy]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
Andi PENG: Vì vậy, bạn sẽ muốn
chuyển đổi nó với sự đầu tiên của mảng đó,

516
00:26:33,150 --> 00:26:33,650
bên phải?

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
Đó là khởi đầu, tôi sẽ nói.

519
00:26:46,850 --> 00:26:47,220
Được rồi.

520
00:26:47,220 --> 00:26:50,386
Vì vậy, bây giờ mà bạn đã đổi chỗ đầu tiên
một, những gì bạn muốn làm gì sau đó?

521
00:26:50,386 --> 00:26:54,840
Vì vậy, bây giờ chúng ta biết rằng một trong những điều này ở đây
phải có giá trị nhỏ nhất, phải không?

522
00:26:54,840 --> 00:26:58,310
Sau đó, bạn có một phần còn lại bổ sung
của mảng đó là không được phân loại.

523
00:26:58,310 --> 00:27:01,569
Vì vậy, những gì bạn muốn làm ở đây, nếu bạn
kẻ muốn cung cấp cho tôi những dòng tiếp theo?

524
00:27:01,569 --> 00:27:04,610
Đung Vì vậy, sau đó bạn muốn lặp
thông qua phần còn lại của mảng.

525
00:27:04,610 --> 00:27:05,276
Andi PENG: Yeah.

526
00:27:05,276 --> 00:27:09,857
Và vì vậy những gì không lặp lại thông qua
loại hàm ý chúng ta có lẽ sẽ cần?

527
00:27:09,857 --> 00:27:10,440
Loại of-- gì

528
00:27:10,440 --> 00:27:12,057
>> Đung Oh, một biến?

529
00:27:12,057 --> 00:27:13,890
Andi PENG: Có thể
một vòng lặp for, phải không?

530
00:27:13,890 --> 00:27:28,914
Vì vậy, chúng ta có lẽ sẽ muốn
để lặp through-- tuyệt vời.

531
00:27:28,914 --> 00:27:31,830
Và sau đó bạn sẽ quay trở lại và
có thể kiểm tra tối thiểu một lần nữa,

532
00:27:31,830 --> 00:27:32,100
bên phải?

533
00:27:32,100 --> 00:27:34,975
Và bạn sẽ tiếp tục lặp
này, vì các vòng chỉ cần đi

534
00:27:34,975 --> 00:27:36,010
để tiếp tục chạy, phải không?

535
00:27:36,010 --> 00:27:39,190
>> Vì vậy, các bạn có thể thấy, chúng tôi
chỉ có một mã giả nói chung

536
00:27:39,190 --> 00:27:41,480
làm thế nào chúng ta muốn chương trình này để xem xét.

537
00:27:41,480 --> 00:27:46,646
Iterate này đây, những gì chúng tôi làm
thường cần phải viết trong mã của chúng tôi

538
00:27:46,646 --> 00:27:49,270
nếu chúng ta muốn lặp thông qua một
mảng, kiểu cấu trúc?

539
00:27:49,270 --> 00:27:51,030
Tôi nghĩ Christabel
đã nói điều này trước.

540
00:27:51,030 --> 00:27:51,500
>> Đung A cho vòng lặp.

541
00:27:51,500 --> 00:27:52,160
>> Andi PENG: A cho vòng lặp?

542
00:27:52,160 --> 00:27:52,770
Đúng như vậy.

543
00:27:52,770 --> 00:27:56,060
Vì vậy, đây có lẽ là
sẽ là một vòng lặp for.

544
00:27:56,060 --> 00:27:59,240
Kiểm tra ở đây sẽ có nghĩa là gì?

545
00:27:59,240 --> 00:28:02,536
Thông thường, nếu bạn muốn kiểm tra
nếu một cái gì đó là một cái gì đó else--

546
00:28:02,536 --> 00:28:03,270
>> Đung Nếu.

547
00:28:03,270 --> 00:28:06,790
>> Andi PENG: An nếu, phải không?

548
00:28:06,790 --> 00:28:10,790
Và sau đó hoán đổi ở đây, chúng tôi sẽ
đi qua sau, vì David

549
00:28:10,790 --> 00:28:12,770
đã đi qua mà trong bài giảng là tốt.

550
00:28:12,770 --> 00:28:14,580
Và sau đó lặp thứ hai implies--

551
00:28:14,580 --> 00:28:15,120
>> Đung Một vòng lặp for.

552
00:28:15,120 --> 00:28:16,745
>> Andi PENG: --another cho vòng lặp, chính xác.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Vì vậy, nếu chúng tôi đang tìm kiếm
lúc này một cách chính xác, chúng tôi

555
00:28:22,000 --> 00:28:24,680
có thể thấy rằng chúng tôi có thể
sẽ cần một vòng lặp lồng nhau cho

556
00:28:24,680 --> 00:28:28,330
với một câu lệnh điều kiện trong đó
và sau đó một mảnh thực tế của mã đó là

557
00:28:28,330 --> 00:28:31,360
đi để trao đổi các giá trị.

558
00:28:31,360 --> 00:28:35,980
Vì vậy, tôi đã chỉ nói chung bằng văn bản
một mã giả ở đây.

559
00:28:35,980 --> 00:28:38,910
Và sau đó chúng tôi đang thực sự đi
thể chất, như một lớp,

560
00:28:38,910 --> 00:28:40,700
cố gắng thực hiện điều này hôm nay.

561
00:28:40,700 --> 00:28:42,486
Chúng ta hãy quay trở lại vào IDE này.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> Uh-oh.

564
00:28:50,230 --> 00:28:51,754
Tại sao là not-- có nó được.

565
00:28:51,754 --> 00:28:52,253
ĐƯỢC.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Xin lỗi, chúng tôi cố gắng để phóng to một chút hơn.

568
00:28:57,500 --> 00:28:59,310
Hiện chúng tôi đi.

569
00:28:59,310 --> 00:29:05,060
Tất cả tôi đang làm ở đây là tôi đã tạo ra
một chương trình gọi là "lựa chọn / sort.c."

570
00:29:05,060 --> 00:29:10,860
Tôi đã tạo ra một mảng của chín
giá trị, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Hiện nay, như bạn có thể
thấy, họ không có thứ tự.

572
00:29:14,370 --> 00:29:17,880
n là có được những con số đó
cho bạn biết số lượng các giá trị

573
00:29:17,880 --> 00:29:18,920
bạn có trong mảng của bạn.

574
00:29:18,920 --> 00:29:20,670
Trong trường hợp này, chúng ta có chín giá trị.

575
00:29:20,670 --> 00:29:23,760
Và tôi đã chỉ có một vòng lặp ở đây
mà in ra mảng phân loại.

576
00:29:23,760 --> 00:29:28,370
>> Và cuối cùng, tôi cũng đã có một cho
vòng lặp mà chỉ cần in nó ra một lần nữa.

577
00:29:28,370 --> 00:29:32,070
Vì vậy, về mặt lý thuyết, nếu chương trình này
đang làm việc một cách chính xác, lúc kết thúc,

578
00:29:32,070 --> 00:29:35,670
bạn sẽ thấy một vòng lặp in
trong đó 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 là tất cả một cách chính xác theo thứ tự.

580
00:29:39,310 --> 00:29:43,410
>> Vì vậy, chúng tôi đã có giả của chúng tôi ở đây.

581
00:29:43,410 --> 00:29:46,090
Có ai muốn đối với: Tôi chỉ
sẽ đi hỏi cho volunteers--

582
00:29:46,090 --> 00:29:49,540
cho tôi biết chính xác những gì để gõ nếu
chúng ta muốn, đầu tiên, chỉ cần lặp

583
00:29:49,540 --> 00:29:52,840
thông qua vào đầu mảng này?

584
00:29:52,840 --> 00:29:55,204
Các dòng mã tôi là gì
có lẽ sẽ cần phải ở đây?

585
00:29:55,204 --> 00:29:56,990
>> Đung [Không nghe thấy]

586
00:29:56,990 --> 00:29:59,010
>> Andi PENG: Yeah, cảm thấy
miễn phí đối với: xin lỗi, bạn

587
00:29:59,010 --> 00:30:02,318
không phải đứng cảm giác up--
miễn phí để nâng cao tiếng nói của bạn một chút.

588
00:30:02,318 --> 00:30:08,190
>> Đung Đối int i bằng 0--

589
00:30:08,190 --> 00:30:10,690
>> Andi PENG: Yeah, tốt.

590
00:30:10,690 --> 00:30:15,220
>> Đung i nhỏ hơn chiều dài mảng.

591
00:30:15,220 --> 00:30:19,630
>> Andi PENG: Vì vậy, hãy
tâm ở đây, bởi vì chúng tôi

592
00:30:19,630 --> 00:30:23,060
không có một chức năng mà
cho chúng ta biết độ dài của một mảng,

593
00:30:23,060 --> 00:30:25,790
chúng tôi đã có một
giá trị mà các cửa hàng đó.

594
00:30:25,790 --> 00:30:27,920
Bên phải?

595
00:30:27,920 --> 00:30:31,010
Một điều cần lưu
trong mind-- trong một mảng

596
00:30:31,010 --> 00:30:33,940
chín các giá trị, các chỉ số là gì?

597
00:30:33,940 --> 00:30:38,720
Hãy chỉ nói rằng mảng này là 0-3.

598
00:30:38,720 --> 00:30:41,500
Bạn thấy rằng cuối cùng
chỉ số thực sự là 3.

599
00:30:41,500 --> 00:30:45,530
Nó không phải 4, mặc dù có
bốn giá trị trong mảng.

600
00:30:45,530 --> 00:30:49,866
>> Vì vậy, ở đây, chúng ta phải rất cẩn thận
của những điều kiện của chúng tôi cho chiều dài

601
00:30:49,866 --> 00:30:50,490
là có được.

602
00:30:50,490 --> 00:30:51,948
>> Đung Nó sẽ không thể n trừ đi 1?

603
00:30:51,948 --> 00:30:54,440
Andi PENG: Nó sẽ
n trừ đi 1, chính xác.

604
00:30:54,440 --> 00:30:57,379
Liệu đó có ý nghĩa, tại sao
nó n trừ đi 1, tất cả mọi người?

605
00:30:57,379 --> 00:30:58,920
Đó là bởi vì mảng là zero-lập chỉ mục.

606
00:30:58,920 --> 00:31:02,010
Họ bắt đầu từ 0 và chạy lên n trừ đi 1.

607
00:31:02,010 --> 00:31:03,210
Vâng, đó là một chút khéo léo.

608
00:31:03,210 --> 00:31:03,730
ĐƯỢC.

609
00:31:03,730 --> 00:31:05,929
Và sau đó--

610
00:31:05,929 --> 00:31:08,054
Đung Isnt'1 đó
đã đưa về chăm sóc, mặc dù

611
00:31:08,054 --> 00:31:11,400
bởi chỉ cần không nói "ít hơn hoặc
bằng "và chỉ nói" ít hơn? "

612
00:31:11,400 --> 00:31:13,108
>> Andi PENG: Đó là một
Câu hỏi thực sự tốt.

613
00:31:13,108 --> 00:31:13,630
Vì vậy, có.

614
00:31:13,630 --> 00:31:17,410
Nhưng cũng có thể, cách mà chúng tôi
thực hiện quyền kiểm tra,

615
00:31:17,410 --> 00:31:19,120
bạn cần so sánh hai giá trị.

616
00:31:19,120 --> 00:31:21,009
Vì vậy, bạn thực sự muốn
rời khỏi "để" trống rỗng.

617
00:31:21,009 --> 00:31:23,050
Bởi vì nếu bạn so sánh
thế này, bạn sẽ không

618
00:31:23,050 --> 00:31:25,530
có bất cứ điều gì sau khi nó
để so sánh, phải không?

619
00:31:25,530 --> 00:31:27,460
Yeah.

620
00:31:27,460 --> 00:31:29,297
Vì vậy, i ++.

621
00:31:29,297 --> 00:31:30,380
Hãy thêm dấu ngoặc của chúng tôi ở.

622
00:31:30,380 --> 00:31:30,880
Lỗi chính.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Thật tuyệt.

625
00:31:34,710 --> 00:31:39,117
Vì vậy, chúng tôi có đầu
của vòng ngoài của chúng tôi.

626
00:31:39,117 --> 00:31:41,450
Vì vậy, bây giờ chúng ta có thể muốn
tạo ra một biến để giữ

627
00:31:41,450 --> 00:31:43,085
theo dõi các giá trị nhỏ nhất, phải không?

628
00:31:43,085 --> 00:31:45,751
Có ai muốn để cho tôi
dòng mã mà sẽ làm điều đó?

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
Những gì chúng ta cần, nếu chúng ta đang đi
muốn để lưu trữ một cái gì đó?

631
00:31:53,570 --> 00:31:55,047
>> Bên phải.

632
00:31:55,047 --> 00:31:57,630
Có lẽ một tên tốt hơn cho rằng
sẽ be-- "temp" hoàn toàn works--

633
00:31:57,630 --> 00:32:00,655
có lẽ đúng hơn là một tên sẽ được,
nếu chúng ta muốn value-- nhỏ nhất

634
00:32:00,655 --> 00:32:01,624
>> Đung Min.

635
00:32:01,624 --> 00:32:02,790
Andi PENG: min, có chúng tôi đi.

636
00:32:02,790 --> 00:32:05,230
min sẽ là tốt.

637
00:32:05,230 --> 00:32:08,340
Và đây, những gì chúng tôi
muốn khởi tạo nó?

638
00:32:08,340 --> 00:32:09,620
Đây là một chút khéo léo.

639
00:32:09,620 --> 00:32:13,580
Bởi vì ngay bây giờ tại
bắt đầu của mảng này,

640
00:32:13,580 --> 00:32:15,730
bạn đã không nhìn bất cứ điều gì, phải không?

641
00:32:15,730 --> 00:32:19,200
Vì vậy, những gì, tự động, nếu
chúng tôi chỉ là trên i bằng 0,

642
00:32:19,200 --> 00:32:22,302
những gì chúng ta muốn khởi tạo
giá trị tối thiểu đầu tiên của chúng tôi đến?

643
00:32:22,302 --> 00:32:22,802
Đung i.

644
00:32:22,802 --> 00:32:24,790
Andi PENG: i, chính xác.

645
00:32:24,790 --> 00:32:27,040
Christabel, tại sao chúng ta muốn
để khởi tạo nó i?

646
00:32:27,040 --> 00:32:28,510
>> Đung Bởi vì, tốt,
chúng tôi đang bắt đầu với 0.

647
00:32:28,510 --> 00:32:31,660
Vì vậy, bởi vì chúng tôi không có gì để so sánh
nó đến, tối thiểu sẽ kết thúc được 0.

648
00:32:31,660 --> 00:32:32,451
>> Andi PENG: Chính xác.

649
00:32:32,451 --> 00:32:34,400
Vì vậy, cô ấy hoàn toàn đúng.

650
00:32:34,400 --> 00:32:36,780
Bởi vì chúng tôi đã không thực sự
nhìn bất cứ điều gì chưa,

651
00:32:36,780 --> 00:32:38,680
chúng ta không biết những gì giá trị nhỏ nhất của chúng tôi là.

652
00:32:38,680 --> 00:32:41,960
Chúng tôi muốn chỉ cần khởi tạo nó
i, trong đó, hiện nay, là phải ở đây.

653
00:32:41,960 --> 00:32:44,750
Và khi chúng ta tiếp tục
di chuyển xuống mảng này,

654
00:32:44,750 --> 00:32:48,122
chúng ta sẽ thấy rằng, với mỗi
thêm pass, i increments.

655
00:32:48,122 --> 00:32:49,830
Và vì vậy tại thời điểm đó,
i có lẽ sẽ

656
00:32:49,830 --> 00:32:52,329
muốn là tối thiểu,
bởi vì nó sẽ là bất cứ điều gì

657
00:32:52,329 --> 00:32:54,520
là sự khởi đầu của mảng được phân loại.

658
00:32:54,520 --> 00:32:55,270
Mát.

659
00:32:55,270 --> 00:32:58,720
>> Vì vậy, bây giờ chúng tôi muốn thêm
một vòng lặp ở đây đó là

660
00:32:58,720 --> 00:33:03,225
đi lặp lại qua các
không được phân loại, hoặc phần còn lại của mảng này.

661
00:33:03,225 --> 00:33:05,808
Có ai muốn để cho tôi một
dòng mã mà sẽ làm điều đó?

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- những gì chúng ta cần phải xuống đây?

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
Điều gì đang xảy đến trong này cho vòng lặp?

666
00:33:18,820 --> 00:33:19,465
Yeah.

667
00:33:19,465 --> 00:33:21,590
Đung Vì vậy, chúng tôi muốn
có một số nguyên khác nhau,

668
00:33:21,590 --> 00:33:25,080
bởi vì chúng tôi đang chạy qua phần còn lại
của mảng thay vì i, như vậy có lẽ

669
00:33:25,080 --> 00:33:25,760
j.

670
00:33:25,760 --> 00:33:27,301
>> Andi PENG: Yeah, j âm thanh tốt với tôi.

671
00:33:27,301 --> 00:33:27,850
Bình đẳng?

672
00:33:27,850 --> 00:33:33,930
>> Đung Vì vậy, sẽ là i + 1, vì
bạn đang bắt đầu từ giá trị tiếp theo.

673
00:33:33,930 --> 00:33:40,395
Và sau đó đến end-- vậy một lần nữa, j là
ít hơn n trừ đi 1, và sau đó j ++.

674
00:33:40,395 --> 00:33:41,103
Andi PENG: Great.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> Và sau đó ở đây, chúng ta sẽ muốn
để kiểm tra xem tình trạng của chúng tôi được đáp ứng,

677
00:33:52,750 --> 00:33:53,250
bên phải?

678
00:33:53,250 --> 00:33:55,740
Bởi vì bạn muốn
thay đổi giá trị tối thiểu

679
00:33:55,740 --> 00:33:58,700
nếu nó thực sự nhỏ hơn so với những gì
bạn đang so sánh nó, phải không?

680
00:33:58,700 --> 00:34:01,146
Vì vậy, những gì chúng ta sẽ muốn ở đây?

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Kiểm tra để xem.

683
00:34:04,897 --> 00:34:06,730
Loại gì của câu
Chúng ta có lẽ sẽ

684
00:34:06,730 --> 00:34:08,389
ti muốn sử dụng nếu chúng tôi
muốn kiểm tra một cái gì đó?

685
00:34:08,389 --> 00:34:09,360
>> Đung Một câu lệnh if.

686
00:34:09,360 --> 00:34:10,485
>> Andi PENG: Một câu lệnh if.

687
00:34:10,485 --> 00:34:13,155
Vì vậy if-- và những gì sẽ được
với điều kiện là chúng tôi muốn bên trong

688
00:34:13,155 --> 00:34:13,988
của câu lệnh if của chúng tôi?

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> Đung Nếu giá trị của j
là ít hơn giá trị của i--

691
00:34:22,960 --> 00:34:24,600
>> Andi PENG: Chính xác.

692
00:34:24,600 --> 00:34:27,480
Vì vậy if-- nên mảng này được gọi là "mảng".

693
00:34:27,480 --> 00:34:27,980
Thật tuyệt.

694
00:34:27,980 --> 00:34:30,465
Vì vậy, nếu array-- đó là cái gì?

695
00:34:30,465 --> 00:34:31,090
Nói lại đi.

696
00:34:31,090 --> 00:34:39,590
>> Đung Nếu mảng j là ít hơn
mảng-i, sau đó chúng tôi sẽ thay đổi min.

697
00:34:39,590 --> 00:34:41,590
Vì vậy, các min sẽ là j.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> Andi PENG: Liệu đó có ý nghĩa?

700
00:34:47,249 --> 00:34:48,670
ĐƯỢC.

701
00:34:48,670 --> 00:34:52,929
Và bây giờ xuống đây, chúng tôi thực sự
muốn thực hiện việc hoán đổi, phải không?

702
00:34:52,929 --> 00:34:58,285
Vì vậy, nhớ lại, trong bài giảng, rằng David, khi
ông đã cố gắng để trao đổi những gì đã the--

703
00:34:58,285 --> 00:34:59,996
nước cam it-- và milk--

704
00:34:59,996 --> 00:35:01,150
>> Đung Đó là gộp.

705
00:35:01,150 --> 00:35:02,816
>> Andi PENG: Yeah, đó là loại gộp.

706
00:35:02,816 --> 00:35:05,310
Nhưng đó là một khá tốt
Khái niệm thời gian chứng minh.

707
00:35:05,310 --> 00:35:08,430
Vì vậy, suy nghĩ về giá trị của bạn ở đây.

708
00:35:08,430 --> 00:35:10,794
Bạn đã có một mảng
min, một mảng của tôi,

709
00:35:10,794 --> 00:35:12,460
hoặc bất cứ điều gì chúng tôi đang cố gắng để trao đổi tại đây.

710
00:35:12,460 --> 00:35:15,310
Và có lẽ bạn không thể đổ chúng vào
nhau cùng một lúc, phải không?

711
00:35:15,310 --> 00:35:17,180
Vì vậy, những gì chúng ta đi
cần phải tạo ở đây

712
00:35:17,180 --> 00:35:19,126
để trao đổi các giá trị chính xác?

713
00:35:19,126 --> 00:35:19,820
>> Đung A biến tạm thời.

714
00:35:19,820 --> 00:35:21,370
>> Andi PENG: Một biến tạm thời.

715
00:35:21,370 --> 00:35:22,570
Vì vậy, chúng ta hãy làm int temp.

716
00:35:22,570 --> 00:35:25,681
Hãy xem, đây sẽ là một tốt hơn
thời gian đối với: whoa, đó là cái gì?

717
00:35:25,681 --> 00:35:26,180
ĐƯỢC.

718
00:35:26,180 --> 00:35:29,800
Vì vậy, đây sẽ là một tốt hơn
thời gian để đặt tên cho "temp." biến

719
00:35:29,800 --> 00:35:30,730
Vì vậy, chúng ta hãy làm int temp.

720
00:35:30,730 --> 00:35:32,563
Chúng ta sẽ đến
set temp bằng ở đây?

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
Đung Min?

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
Andi PENG: Đó là một chút khéo léo.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
Nó thực sự không quan trọng cuối cùng.

727
00:35:44,880 --> 00:35:47,690
Nó không có vấn đề gì
thứ tự mà bạn chọn để trao đổi trong

728
00:35:47,690 --> 00:35:50,862
miễn là bạn đang làm cho chắc chắn rằng bạn đang
theo dõi những gì bạn đang trao đổi.

729
00:35:50,862 --> 00:35:52,250
>> Đung Nó có thể là mảng-i.

730
00:35:52,250 --> 00:35:53,666
>> Andi PENG: Vâng, chúng ta hãy làm mảng-i.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
Và sau đó các dòng tiếp theo là những gì
mã chúng tôi muốn có ở đây?

733
00:35:59,305 --> 00:36:00,680
Đung mảng-i bằng mảng j.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
Andi PENG: Và cuối cùng?

736
00:36:08,070 --> 00:36:12,070
Đung mảng j bằng mảng-i.

737
00:36:12,070 --> 00:36:14,525
Đung Hoặc mảng j equals
mảng temp-- hay, temp.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> Andi PENG: OK.

740
00:36:19,430 --> 00:36:21,510
Vì vậy, chúng ta hãy chạy này và xem
nếu nó sẽ làm việc.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
Ở đâu mà ra?

743
00:36:39,335 --> 00:36:40,210
Oh, đó là một vấn đề.

744
00:36:40,210 --> 00:36:44,320
Thấy, trên đường 40, chúng tôi
cố gắng sử dụng mảng j?

745
00:36:44,320 --> 00:36:47,022
Nhưng nơi nào j chỉ tồn tại trong?

746
00:36:47,022 --> 00:36:48,402
>> Đung Trong vòng lặp for.

747
00:36:48,402 --> 00:36:49,110
Andi PENG: Đúng vậy.

748
00:36:49,110 --> 00:36:51,730
Vì vậy, những gì chúng ta sẽ cần phải làm gì?

749
00:36:51,730 --> 00:36:53,170
>> Đung Xác định nó bên ngoài the--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
Đung Vâng, tôi đoán bạn có
sử dụng một lệnh if khác, phải không?

752
00:37:00,610 --> 00:37:05,230
Vì vậy, như thế nào, nếu minimum--
tất cả các quyền, hãy để tôi nghĩ.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> Andi PENG: Guys, thử
để có một cái nhìn Hãy

755
00:37:09,990 --> 00:37:11,270
thấy, những gì một cái gì đó chúng ta có thể làm ở đây?

756
00:37:11,270 --> 00:37:11,811
>> Đung OK.

757
00:37:11,811 --> 00:37:15,900
Vì vậy, nếu tối thiểu không bằng
j-- vì vậy nếu tối thiểu là vẫn i--

758
00:37:15,900 --> 00:37:17,570
sau đó chúng ta sẽ không phải trao đổi.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> Andi PENG: Liệu rằng bằng i?

761
00:37:24,712 --> 00:37:25,920
Làm những gì bạn muốn nói ở đây?

762
00:37:25,920 --> 00:37:30,494
>> Đung Hoặc yeah, nếu
tối thiểu nào tôi không bằng nhau, yeah.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
Andi PENG: OK.

765
00:37:40,210 --> 00:37:42,040
Vâng mà giải quyết, loại, vấn đề của chúng tôi.

766
00:37:42,040 --> 00:37:47,265
Nhưng điều đó vẫn không giải quyết được
Vấn đề của những gì sẽ xảy ra nếu j-- từ j

767
00:37:47,265 --> 00:37:49,890
không tồn tại bên ngoài của nó, những gì
Bạn chúng tôi muốn làm gì với nó?

768
00:37:49,890 --> 00:37:50,698
Khai báo bên ngoài?

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Hãy thử chạy này.

771
00:38:02,730 --> 00:38:04,435
Uh-oh.

772
00:38:04,435 --> 00:38:06,200
Loại của chúng tôi không phải làm việc.

773
00:38:06,200 --> 00:38:10,060
>> Như bạn có thể thấy, ban đầu của chúng tôi
mảng có những giá trị.

774
00:38:10,060 --> 00:38:14,800
Và sau đó nó cần phải có
được trong 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Nó không hoạt động.

776
00:38:15,530 --> 00:38:16,030
Ahh.

777
00:38:16,030 --> 00:38:17,184
Chúng ta làm gì?

778
00:38:17,184 --> 00:38:17,850
Đung Debug.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
Andi PENG: Được rồi, chúng ta có thể cố gắng đó.

781
00:38:23,370 --> 00:38:25,030
Chúng tôi có thể gỡ lỗi.

782
00:38:25,030 --> 00:38:26,042
Thu nhỏ một chút.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Hãy đặt breakpoint của chúng tôi.

785
00:38:33,656 --> 00:38:37,280
Hãy đi like-- OK.

786
00:38:37,280 --> 00:38:40,444
>> Vì vậy, bởi vì chúng ta đã biết rằng
những dòng này, 15 đến 22,

787
00:38:40,444 --> 00:38:43,610
được working-- bởi vì tất cả tôi đang làm là
chỉ lặp lại thông qua và printing--

788
00:38:43,610 --> 00:38:45,406
Tôi có thể đi trước và bỏ qua.

789
00:38:45,406 --> 00:38:47,280
Hãy bắt đầu tại dòng 25.

790
00:38:47,280 --> 00:38:48,712
Oop, hãy để tôi bỏ nó đi.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> Đung vậy của breakpoint
nơi gỡ lỗi khởi động?

793
00:38:54,057 --> 00:38:54,890
Andi PENG: Hoặc dừng.

794
00:38:54,890 --> 00:38:55,670
Đung Hoặc dừng.

795
00:38:55,670 --> 00:38:55,930
Andi PENG: Yeah.

796
00:38:55,930 --> 00:38:58,640
Bạn có thể thiết lập nhiều các điểm ngắt và
nó chỉ có thể nhảy từ một đến khác.

797
00:38:58,640 --> 00:39:01,590
Nhưng trong trường hợp này, chúng ta không biết
nơi mà các lỗi đang xảy ra.

798
00:39:01,590 --> 00:39:03,780
Vì vậy, chúng tôi chỉ muốn
bắt đầu từ trên xuống dưới.

799
00:39:03,780 --> 00:39:05,020
Yep.

800
00:39:05,020 --> 00:39:05,550
ĐƯỢC.

801
00:39:05,550 --> 00:39:08,460
>> Vì vậy, dòng này ở đây, chúng ta có thể bước vào.

802
00:39:08,460 --> 00:39:11,499
Bạn có thể thấy ở đây,
chúng tôi đã có một mảng.

803
00:39:11,499 --> 00:39:13,290
Đó là những giá trị
đó là trong mảng.

804
00:39:13,290 --> 00:39:16,360
Bạn có thấy rằng, làm thế nào chỉ số 0, nó
tương ứng với value-- oh,

805
00:39:16,360 --> 00:39:17,526
Tôi sẽ cố gắng để phóng to.

806
00:39:17,526 --> 00:39:20,650
Xin lỗi, nó thực sự khó
để see-- ở mảng chỉ số 0,

807
00:39:20,650 --> 00:39:24,090
chúng ta có một giá trị của 4 và
sau đó vân vân và vân vân.

808
00:39:24,090 --> 00:39:25,670
Chúng tôi có các biến địa phương của chúng tôi.

809
00:39:25,670 --> 00:39:28,570
Ngay bây giờ tôi là bằng
0, mà chúng tôi muốn nó được.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> Và như vậy chúng ta hãy giữ bước qua.

812
00:39:33,690 --> 00:39:36,850
Tối thiểu của chúng tôi là bằng 0,
mà chúng tôi cũng muốn nó được.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
Và sau đó chúng tôi nhập thứ hai của chúng tôi cho
vòng lặp, nếu mảng-j là ít hơn so với mảng-i,

815
00:39:45,560 --> 00:39:46,380
mà nó không được.

816
00:39:46,380 --> 00:39:48,130
Vì vậy, bạn đã thấy như thế nào
mà bỏ qua điều đó?

817
00:39:48,130 --> 00:39:52,430
>> Đung Vì vậy nên nếu
tối thiểu, tất cả that-- không nên mà

818
00:39:52,430 --> 00:39:55,424
được bên trong những người đầu tiên cho vòng lặp?

819
00:39:55,424 --> 00:39:57,340
Andi PENG: Không, bởi vì
bạn vẫn còn muốn thử nghiệm.

820
00:39:57,340 --> 00:40:00,329
Bạn muốn làm một so sánh mỗi
thời gian, ngay cả sau khi bạn chạy qua nó.

821
00:40:00,329 --> 00:40:02,620
Bạn không chỉ muốn làm điều đó
trên pass-thông qua đầu tiên.

822
00:40:02,620 --> 00:40:05,240
Bạn muốn làm điều đó với
từng vượt qua thêm một lần nữa.

823
00:40:05,240 --> 00:40:07,198
Vì vậy, bạn muốn kiểm tra
tình trạng của bạn bên trong.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Vì vậy, chúng tôi chỉ cần đi để
tiếp tục chạy qua đây.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Tôi sẽ cung cấp cho các bạn một gợi ý.

828
00:40:18,420 --> 00:40:23,910
Nó đã làm với thực tế là khi
bạn đang kiểm tra điều kiện của bạn,

829
00:40:23,910 --> 00:40:26,600
bạn không kiểm tra
cho các chỉ số chính xác.

830
00:40:26,600 --> 00:40:32,510
Vì vậy, ngay bây giờ bạn đang kiểm tra
mảng chỉ số j là ít hơn so với mảng

831
00:40:32,510 --> 00:40:33,970
chỉ số của tôi.

832
00:40:33,970 --> 00:40:36,580
Nhưng những gì bạn đang làm tại
đầu cho vòng lặp?

833
00:40:36,580 --> 00:40:38,260
Bạn không phải cài đặt j bằng i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Yeah, vì vậy chúng tôi có thể thực sự
thoát khỏi các trình gỡ lỗi ở đây.

836
00:40:45,415 --> 00:40:47,040
Vì vậy, chúng ta hãy nhìn vào mã giả của chúng tôi.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- chúng ta sẽ
bắt đầu từ i bằng 0.

839
00:40:52,580 --> 00:40:54,760
Chúng ta sẽ đi đến n trừ đi 1.

840
00:40:54,760 --> 00:40:58,040
Hãy kiểm tra, chúng tôi đã có quyền đó?

841
00:40:58,040 --> 00:40:59,580
Đúng, đó là đúng.

842
00:40:59,580 --> 00:41:02,080
>> Vì vậy, sau đó bên trong ở đây, chúng tôi
sẽ tạo ra một giá trị tối thiểu

843
00:41:02,080 --> 00:41:03,630
và thiết lập đó bằng i.

844
00:41:03,630 --> 00:41:04,950
Chúng tôi đã làm điều đó?

845
00:41:04,950 --> 00:41:06,270
Yep, đã làm điều đó.

846
00:41:06,270 --> 00:41:10,430
Bây giờ chúng tôi ở bên trong vòng lặp, chúng tôi
sẽ làm j bằng i cho n trừ đi 1.

847
00:41:10,430 --> 00:41:11,950
Chúng tôi đã làm điều đó?

848
00:41:11,950 --> 00:41:15,540
Thật vậy, chúng tôi đã làm điều đó.

849
00:41:15,540 --> 00:41:19,922
>> Vì vậy, tuy nhiên, những gì chúng ta đang so sánh ở đây?

850
00:41:19,922 --> 00:41:20,925
>> Đung j + 1.

851
00:41:20,925 --> 00:41:21,716
Andi PENG: Chính xác.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
Và sau đó bạn sẽ muốn thiết lập
tối thiểu của bạn bằng j + 1 là tốt.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Vì vậy, tôi đã đi qua mà thực sự nhanh chóng.

856
00:41:32,640 --> 00:41:36,190
Do you guys hiểu
lý do tại sao nó là j + 1?

857
00:41:36,190 --> 00:41:36,890
ĐƯỢC.

858
00:41:36,890 --> 00:41:40,700
>> Vì vậy, trong mảng của bạn, trong
qua đầu tiên của bạn thông qua,

859
00:41:40,700 --> 00:41:44,850
bạn cho vòng lặp, cho int
i bằng 0, chúng ta hãy chỉ

860
00:41:44,850 --> 00:41:46,740
giả định này đã không được thay đổi nào.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Chúng tôi có một mảng, hoàn toàn,
chỉ bốn yếu tố không được phân loại, phải không?

863
00:41:56,760 --> 00:42:00,760
Vì vậy, chúng ta muốn khởi tạo i bằng 0.

864
00:42:00,760 --> 00:42:03,650
Và tôi sẽ chỉ
chạy qua vòng lặp này.

865
00:42:03,650 --> 00:42:08,560
Và như vậy trong các lần trước, chúng ta đang đi
để khởi tạo một biến gọi là "min"

866
00:42:08,560 --> 00:42:11,245
mà còn bằng i, vì
chúng ta không có một giá trị tối thiểu.

867
00:42:11,245 --> 00:42:12,870
Vì vậy, đó là hiện bằng 0 là tốt.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
Và sau đó chúng ta sẽ đi qua.

870
00:42:17,640 --> 00:42:19,270
Và chúng tôi muốn lặp lại.

871
00:42:19,270 --> 00:42:22,900
Bây giờ chúng ta đã tìm thấy những gì tối thiểu của chúng tôi
là, chúng tôi muốn lặp qua

872
00:42:22,900 --> 00:42:25,190
một lần nữa để xem nếu nó so sánh, phải không?

873
00:42:25,190 --> 00:42:40,440
Vì vậy, j, ở đây, được đi
để tôi bình đẳng, mà là 0.

874
00:42:40,440 --> 00:42:46,320
Và sau đó nếu mảng j cộng với tôi, đó
là một trong đó là sau hơn, như ít

875
00:42:46,320 --> 00:42:49,270
hơn những gì tối thiểu hiện tại của bạn
giá trị, bạn muốn trao đổi.

876
00:42:49,270 --> 00:42:56,850
>> Vì vậy, chúng ta hãy chỉ nói rằng chúng ta đã
có, như, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Ngay bây giờ, tôi là bằng
0 và j là bằng 0.

878
00:43:01,610 --> 00:43:05,210
Và đó là giá trị nhỏ nhất của chúng tôi.

879
00:43:05,210 --> 00:43:09,950
Nếu mảng j cộng i-- vì vậy nếu một trong các
đó là sau khi một trong chúng tôi đang tìm kiếm tại

880
00:43:09,950 --> 00:43:13,450
là lớn hơn so với cái trước đó,
nó sẽ trở thành tối thiểu.

881
00:43:13,450 --> 00:43:18,120
>> Vì vậy, ở đây chúng tôi thấy rằng 5
không phải là ít hơn thế.

882
00:43:18,120 --> 00:43:19,730
Vì vậy, nó sẽ không là 5.

883
00:43:19,730 --> 00:43:23,580
Chúng tôi thấy rằng 1 là ít hơn 2, phải không?

884
00:43:23,580 --> 00:43:32,970
Vì vậy, bây giờ chúng ta biết rằng tối thiểu của chúng tôi là
sẽ có giá trị chỉ số 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Yeah?

886
00:43:34,030 --> 00:43:39,170
Và sau đó khi bạn nhận được xuống đây,
bạn có thể trao đổi các giá trị đúng.

887
00:43:39,170 --> 00:43:42,610
>> Vì vậy, khi các bạn đã chỉ có j
trước khi, bạn không chỉ nhìn vào một trong các

888
00:43:42,610 --> 00:43:43,260
sau đó.

889
00:43:43,260 --> 00:43:44,520
Bạn đang tìm kiếm tại
giá trị như nhau, trong đó

890
00:43:44,520 --> 00:43:46,290
là lý do tại sao nó chỉ là không làm gì cả.

891
00:43:46,290 --> 00:43:49,721
Điều đó có ý nghĩa với tất cả mọi người,
tại sao chúng ta cần thiết mà cộng 1 có?

892
00:43:49,721 --> 00:43:50,220
ĐƯỢC.

893
00:43:50,220 --> 00:43:53,345
Bây giờ chúng ta hãy chỉ cần chạy qua nó để làm cho
chắc chắn các phần còn lại của mã này là chính xác.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Tại sao điều đó xảy ra?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, đó là phút ngay tại đây.

898
00:44:16,364 --> 00:44:17,780
Chúng tôi đã so sánh các giá trị sai.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Ồ không.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Oh yeah, xuống đây chúng tôi
trao đổi các giá trị sai là tốt.

903
00:44:33,482 --> 00:44:34,940
Bởi vì chúng tôi đang tìm kiếm tại i và j.

904
00:44:34,940 --> 00:44:36,440
Đó là những người chúng tôi đã được kiểm tra.

905
00:44:36,440 --> 00:44:39,160
Chúng tôi thực sự muốn trao đổi
tối thiểu, tối thiểu hiện hành,

906
00:44:39,160 --> 00:44:40,550
với bất cứ ai bên ngoài là.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
Và như các bạn có thể nhìn xuống
ở đây, chúng tôi có một mảng được sắp xếp.

909
00:45:05,402 --> 00:45:07,110
Nó chỉ cần có để làm với
thực tế là khi

910
00:45:07,110 --> 00:45:09,350
chúng tôi đã kiểm tra
giá trị chúng tôi đã so sánh,

911
00:45:09,350 --> 00:45:11,226
chúng ta không chỉ nhìn vào những giá trị đúng.

912
00:45:11,226 --> 00:45:13,850
Chúng tôi đang tìm kiếm tại cùng một
ở đây, không thực sự trao đổi nó.

913
00:45:13,850 --> 00:45:17,135
Bạn phải nhìn vào một trong những tiếp theo
để nó và sau đó bạn có thể trao đổi.

914
00:45:17,135 --> 00:45:19,260
Vì vậy, đó là những gì đã được loại
bugging mã của chúng tôi trước.

915
00:45:19,260 --> 00:45:22,460
Và những gì tôi đã làm ở đây là tất cả mọi thứ
trình gỡ lỗi có thể làm cho bạn

916
00:45:22,460 --> 00:45:23,810
Tôi chỉ làm nó trên
hội đồng quản trị, bởi vì nó dễ dàng hơn

917
00:45:23,810 --> 00:45:26,320
để xem hơn là cố gắng
để phóng to trên các trình gỡ lỗi.

918
00:45:26,320 --> 00:45:29,391
Điều đó có ý nghĩa với tất cả mọi người?

919
00:45:29,391 --> 00:45:29,890
Mát.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Được rồi.

922
00:45:35,410 --> 00:45:41,070
Chúng tôi có thể chuyển sang nói về
ký hiệu tiệm cận, mà

923
00:45:41,070 --> 00:45:44,580
chỉ là một cách nói của
runtimes của tất cả các loại.

924
00:45:44,580 --> 00:45:47,650
Vì vậy, tôi biết David, trong bài giảng,
xúc động khi runtimes.

925
00:45:47,650 --> 00:45:52,124
Và ông đã đi qua toàn bộ công thức
làm thế nào để tính toán các runtimes.

926
00:45:52,124 --> 00:45:53,040
Không có lo lắng về điều đó.

927
00:45:53,040 --> 00:45:54,660
Nếu bạn đang thực sự tò mò
về cách mà các công trình,

928
00:45:54,660 --> 00:45:55,810
cảm thấy miễn phí để nói chuyện với tôi sau khi phần.

929
00:45:55,810 --> 00:45:57,560
Chúng tôi có thể đi bộ qua
các công thức với nhau.

930
00:45:57,560 --> 00:46:00,689
Nhưng tất cả các bạn phải thực sự
biết là n bình trên 2

931
00:46:00,689 --> 00:46:01,980
là những điều tương tự như n bình phương.

932
00:46:01,980 --> 00:46:04,710
Bởi vì số lượng lớn nhất,
số mũ, mọc nhiều nhất.

933
00:46:04,710 --> 00:46:06,590
Và do đó, cho các mục đích của chúng tôi,
tất cả chúng ta quan tâm

934
00:46:06,590 --> 00:46:09,470
là số lượng khổng lồ đang phát triển.

935
00:46:09,470 --> 00:46:13,340
>> Vì vậy, các trường hợp tốt nhất là gì
thời gian chạy của sắp xếp chọn?

936
00:46:13,340 --> 00:46:15,830
Nếu bạn đang đi để có
để lặp qua một danh sách

937
00:46:15,830 --> 00:46:18,712
và sau đó lặp qua
phần còn lại của danh sách đó,

938
00:46:18,712 --> 00:46:20,420
bao nhiêu lần
bạn sẽ có thể,

939
00:46:20,420 --> 00:46:24,612
trong case-- tồi tệ nhất trong
tốt nhất trường hợp, sorry-- chạy qua?

940
00:46:24,612 --> 00:46:27,070
Có lẽ câu hỏi tốt hơn là
hỏi, trường hợp xấu nhất là gì

941
00:46:27,070 --> 00:46:28,153
thời gian chạy của sắp xếp chọn.

942
00:46:28,153 --> 00:46:29,366
Đung n bình phương.

943
00:46:29,366 --> 00:46:30,740
Andi PENG: Nó n bình phương, phải.

944
00:46:30,740 --> 00:46:36,986
Vì vậy, một cách dễ dàng để nghĩ về điều này là như thế,
bất cứ lúc nào bạn có hai lồng nhau cho các vòng,

945
00:46:36,986 --> 00:46:38,110
nó sẽ được n bình phương.

946
00:46:38,110 --> 00:46:40,386
Bởi vì không chỉ là bạn
chạy qua một lần nữa,

947
00:46:40,386 --> 00:46:42,260
bạn phải đi lại
xung quanh và chạy qua nó

948
00:46:42,260 --> 00:46:44,980
một lần nữa bên trong cho mỗi giá trị.

949
00:46:44,980 --> 00:46:48,640
Vì vậy, trong trường hợp đó, bạn đang chạy n
lần n bình phương, mà is-- xin lỗi,

950
00:46:48,640 --> 00:46:50,505
n lần n, trong đó n bằng với bình phương.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> Và loại cũng là một chút
độc đáo trong ý nghĩa

953
00:46:56,360 --> 00:46:59,774
rằng nó không quan trọng nếu những
giá trị đã có trong trật tự.

954
00:46:59,774 --> 00:47:01,440
Nó vẫn sẽ chạy qua anyways.

955
00:47:01,440 --> 00:47:03,872
Hãy chỉ nói rằng đây là 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Bất kể có hay không nó đã ở
trật tự, nó vẫn sẽ chạy qua

957
00:47:07,080 --> 00:47:08,620
và vẫn còn kiểm tra các giá trị tối thiểu.

958
00:47:08,620 --> 00:47:10,100
Nó sẽ làm việc
cùng một số kiểm tra

959
00:47:10,100 --> 00:47:12,780
mỗi lần duy nhất, ngay cả khi nó
không thực sự chạm vào bất cứ điều gì.

960
00:47:12,780 --> 00:47:16,940
>> Vì vậy, trong trường hợp này, tốt nhất và tồi tệ nhất
runtimes thực sự tương đương.

961
00:47:16,940 --> 00:47:19,160
Vì vậy, thời gian chạy dự kiến
lựa chọn sắp xếp,

962
00:47:19,160 --> 00:47:23,790
mà chúng ta thiết kế bởi các biểu tượng
của theta, theta, trong trường hợp này,

963
00:47:23,790 --> 00:47:24,790
cũng sẽ được n bình phương.

964
00:47:24,790 --> 00:47:26,480
Tất cả ba trong số này sẽ được n bình phương.

965
00:47:26,480 --> 00:47:29,653
Là tất cả mọi người rõ ràng vì sao
thời gian chạy là n bình?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Được rồi.

968
00:47:33,980 --> 00:47:39,120
Vì vậy, tôi chỉ cần đi để nhanh chóng chạy
thông qua phần còn lại của các loại.

969
00:47:39,120 --> 00:47:41,137
Các thuật toán cho
bong bóng sort-- nhớ,

970
00:47:41,137 --> 00:47:43,220
này là người đầu tiên
David đã đi qua trong bài giảng.

971
00:47:43,220 --> 00:47:46,000
Về cơ bản, bạn bước
thông qua toàn bộ danh sách

972
00:47:46,000 --> 00:47:48,950
và bạn swap-- bạn chỉ
so sánh hai tại một thời điểm.

973
00:47:48,950 --> 00:47:51,350
Và nếu có ai là lớn hơn,
hơn bạn chỉ cần trao đổi chúng.

974
00:47:51,350 --> 00:47:53,590
Vì vậy, nếu đây là lớn hơn, bạn sẽ trao đổi.

975
00:47:53,590 --> 00:47:56,180
Tôi đã chính thức ngay tại đây.

976
00:47:56,180 --> 00:47:59,100
>> Vì vậy, chúng ta hãy chỉ nói rằng bạn đã có 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Bạn muốn so sánh 8 và 6.

978
00:48:00,571 --> 00:48:01,570
Bạn sẽ cần phải trao đổi chúng.

979
00:48:01,570 --> 00:48:02,610
Bạn sẽ so sánh 8 và 4.

980
00:48:02,610 --> 00:48:03,609
Bạn sẽ cần phải trao đổi chúng.

981
00:48:03,609 --> 00:48:07,000
Nếu bạn phải trao đổi 8 và
2, thay đổi họ là tốt.

982
00:48:07,000 --> 00:48:10,760
Vì vậy, trong một cảm giác như vậy, bạn có thể thấy,
diễn ra trong một khoảng thời gian dài,

983
00:48:10,760 --> 00:48:13,730
cách các giá trị loại bong bóng để
kết thúc, đó là lý do tại sao chúng tôi gọi nó

984
00:48:13,730 --> 00:48:15,320
bong bóng sắp xếp.

985
00:48:15,320 --> 00:48:19,950
>> Chúng tôi sẽ chỉ cần chạy qua lại trên
qua thứ hai của chúng tôi, và vượt qua thứ ba của chúng tôi,

986
00:48:19,950 --> 00:48:21,150
và vượt qua thứ tư của chúng tôi.

987
00:48:21,150 --> 00:48:25,820
Về cơ bản, bong bóng sắp xếp chỉ chạy
cho đến khi bạn không thực hiện bất kỳ giao dịch hoán đổi hơn.

988
00:48:25,820 --> 00:48:31,109
Vì vậy, trong ý nghĩa đó, đây chỉ là
mã giả chung của nó.

989
00:48:31,109 --> 00:48:32,650
Không có lo lắng, những tất cả sẽ được trực tuyến.

990
00:48:32,650 --> 00:48:34,990
Chúng tôi không có để thực sự đi qua này.

991
00:48:34,990 --> 00:48:38,134
>> Chúng tôi chỉ khởi tạo một truy cập
biến mà bắt đầu từ 0.

992
00:48:38,134 --> 00:48:39,800
Và chúng ta lặp qua toàn bộ mảng.

993
00:48:39,800 --> 00:48:43,420
Và nếu một giá trị is-- nếu điều này
giá trị lớn hơn giá trị đó,

994
00:48:43,420 --> 00:48:44,610
bạn đang đi để trao đổi chúng.

995
00:48:44,610 --> 00:48:46,860
Và sau đó bạn chỉ
sẽ tiếp tục đi.

996
00:48:46,860 --> 00:48:47,970
Và bạn đang đi để đếm.

997
00:48:47,970 --> 00:48:50,845
Và bạn chỉ cần đi để tiếp tục làm
này khi truy cập lớn

998
00:48:50,845 --> 00:48:53,345
hơn 0, có nghĩa là
mỗi khi bạn phải trao đổi,

999
00:48:53,345 --> 00:48:55,220
bạn biết bạn muốn đi
trở lại và kiểm tra lại.

1000
00:48:55,220 --> 00:48:59,510
Bạn muốn giữ lại kiểm tra cho đến khi bạn biết
rằng bạn không phải trao đổi nữa.

1001
00:48:59,510 --> 00:49:05,570
>> Vì vậy, những gì là tốt nhất và tồi tệ nhất
trường hợp thời gian chạy cho bong bóng sắp xếp?

1002
00:49:05,570 --> 00:49:09,300
Và hint-- này thực sự là khác nhau
từ sắp xếp chọn theo ý nghĩa

1003
00:49:09,300 --> 00:49:11,810
rằng hai câu trả lời này là không giống nhau.

1004
00:49:11,810 --> 00:49:14,709
Hãy suy nghĩ về những gì sẽ xảy ra trong
một trường hợp nếu nó đã được sắp xếp.

1005
00:49:14,709 --> 00:49:16,500
Và suy nghĩ về những gì
sẽ xảy ra nếu nó đã được

1006
00:49:16,500 --> 00:49:18,372
trong các trường hợp mà trong đó nó đã không được sắp xếp.

1007
00:49:18,372 --> 00:49:20,580
Và bạn có thể loại chạy
thông qua tại sao điều đó đang xảy ra.

1008
00:49:20,580 --> 00:49:22,954
Tôi sẽ cung cấp cho các bạn, như, 30
giây để suy nghĩ về điều đó.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> ĐƯỢC.

1011
00:49:53,540 --> 00:49:57,462
Có ai có một đoán vào những gì các
thời gian chạy trường hợp tồi tệ nhất của bong bóng sắp xếp là?

1012
00:49:57,462 --> 00:49:57,962
Yeah.

1013
00:49:57,962 --> 00:50:07,810
>> Đung nó Sẽ được, như, n lần
n trừ đi 1 hoặc một cái gì đó như thế?

1014
00:50:07,810 --> 00:50:10,650
Giống như, mỗi khi nó chạy,
nó chỉ là, như, một hoán đổi ít

1015
00:50:10,650 --> 00:50:10,960
rằng bất cứ điều gì nó được.

1016
00:50:10,960 --> 00:50:12,668
>> Andi PENG: Yeah, vì vậy
bạn đã hoàn toàn đúng.

1017
00:50:12,668 --> 00:50:15,940
Và đây là một trường hợp mà trong đó bạn
Câu trả lời là thực sự phức tạp hơn

1018
00:50:15,940 --> 00:50:17,240
so với cái chúng ta cần phải cung cấp cho.

1019
00:50:17,240 --> 00:50:19,772
Vì vậy, nó sẽ run-- tôi
sẽ xóa tất cả điều này ở đây.

1020
00:50:19,772 --> 00:50:20,480
Là tất cả mọi người tốt?

1021
00:50:20,480 --> 00:50:21,869
Tôi có thể xoá này?

1022
00:50:21,869 --> 00:50:22,368
ĐƯỢC.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Bạn sẽ phải chạy qua n
lần lần đầu tiên, phải không?

1025
00:50:30,320 --> 00:50:33,200
Và chúng ta sẽ chạy qua
n trừ đi 1 lần thứ hai, phải không?

1026
00:50:33,200 --> 00:50:37,130
Và sau đó bạn sẽ giữ
đi, n mỏ 2, vân vân.

1027
00:50:37,130 --> 00:50:40,210
David đã làm điều này trong một bài giảng, ở đâu,
nếu bạn thêm lên tất cả những giá trị,

1028
00:50:40,210 --> 00:50:48,080
bạn sẽ có được một cái gì đó là like-- yeah--
hơn 2, trong đó chủ yếu chỉ giảm

1029
00:50:48,080 --> 00:50:49,784
xuống n bình phương.

1030
00:50:49,784 --> 00:50:51,700
Bạn sẽ nhận được một
phần kỳ lạ trong đó.

1031
00:50:51,700 --> 00:50:53,892
Và do đó, chỉ biết rằng
n bình phương luôn

1032
00:50:53,892 --> 00:50:55,350
được ưu tiên hơn các phân số.

1033
00:50:55,350 --> 00:50:58,450
Và như vậy trong trường hợp này, điều tồi tệ nhất
runtime sẽ được n bình phương.

1034
00:50:58,450 --> 00:51:00,210
Nếu nó đã được giảm dần
trật tự, suy nghĩ, bạn

1035
00:51:00,210 --> 00:51:02,530
phải thực hiện một trao đổi mỗi lần duy nhất.

1036
00:51:02,530 --> 00:51:05,170
>> Điều gì sẽ là, có khả năng,
trường hợp thời gian chạy tốt nhất?

1037
00:51:05,170 --> 00:51:08,580
Hãy chỉ nói rằng, nếu trong danh sách là đã
theo thứ tự, những gì sẽ là thời gian chạy được?

1038
00:51:08,580 --> 00:51:09,565
>> Đung n.

1039
00:51:09,565 --> 00:51:10,690
Andi PENG: Đó là n, chính xác.

1040
00:51:10,690 --> 00:51:11,600
Và tại sao nó n?

1041
00:51:11,600 --> 00:51:13,850
Đung Bởi vì bạn chỉ
phải kiểm tra mỗi một lần.

1042
00:51:13,850 --> 00:51:14,770
Andi PENG: Chính xác.

1043
00:51:14,770 --> 00:51:17,150
Vì vậy, trong thời gian chạy tốt nhất có thể,
nếu danh sách này đã là

1044
00:51:17,150 --> 00:51:20,270
sorted-- hãy nói 1, 2, 3, 4-- bạn
sẽ chỉ đi qua, bạn sẽ kiểm tra,

1045
00:51:20,270 --> 00:51:21,720
bạn sẽ thấy, oh, tất cả họ đều chảo ra.

1046
00:51:21,720 --> 00:51:22,636
Tôi không có để trao đổi.

1047
00:51:22,636 --> 00:51:23,370
Tôi đa xong.

1048
00:51:23,370 --> 00:51:26,500
Vì vậy, trong trường hợp đó, nó chỉ là n
hoặc số lượng các bước bạn chỉ

1049
00:51:26,500 --> 00:51:29,870
phải kiểm tra trong danh sách đầu tiên.

1050
00:51:29,870 --> 00:51:33,990
>> Và sau đó, bây giờ chúng ta nhấn
sắp xếp chèn, nơi

1051
00:51:33,990 --> 00:51:39,260
các thuật toán cơ bản là để phân chia
nó vào một phần được sắp xếp và phân loại.

1052
00:51:39,260 --> 00:51:42,810
Và sau đó từng người một,
các giá trị không được phân loại là

1053
00:51:42,810 --> 00:51:46,880
lắp vào thích hợp của họ
vị trí ở đầu danh sách.

1054
00:51:46,880 --> 00:51:52,120
>> Vì vậy, ví dụ, chúng ta có một
danh sách 3, 5, 2, 6, 4 lần nữa.

1055
00:51:52,120 --> 00:51:54,750
Chúng tôi biết rằng đó là hiện
không được phân loại bởi vì chúng tôi đã chỉ

1056
00:51:54,750 --> 00:51:57,030
bắt đầu nhìn vào nó.

1057
00:51:57,030 --> 00:52:00,610
Chúng tôi có một cái nhìn và chúng tôi biết rằng
giá trị đầu tiên được sắp xếp, phải không?

1058
00:52:00,610 --> 00:52:04,190
Nếu bạn chỉ nhìn vào một mảng của
kích thước của nó, bạn biết rằng nó được sắp xếp.

1059
00:52:04,190 --> 00:52:08,230
>> Vì vậy, sau đó chúng ta biết rằng
bốn người kia là không được phân loại.

1060
00:52:08,230 --> 00:52:10,980
Chúng tôi đi qua và chúng ta thấy giá trị đó.

1061
00:52:10,980 --> 00:52:11,730
Hãy quay trở lại.

1062
00:52:11,730 --> 00:52:13,130
Thấy rằng giá trị của 5?

1063
00:52:13,130 --> 00:52:14,110
Chúng ta hãy nhìn vào nó.

1064
00:52:14,110 --> 00:52:15,204
Chúng tôi so sánh nó với 3.

1065
00:52:15,204 --> 00:52:17,870
Chúng tôi biết rằng nó lớn hơn
3, vì vậy chúng tôi biết rằng đó là sắp xếp.

1066
00:52:17,870 --> 00:52:22,940
Vì vậy, bây giờ chúng ta biết rằng hai đầu
đều được sắp xếp và cuối cùng ba không.

1067
00:52:22,940 --> 00:52:24,270
>> Chúng ta hãy nhìn vào 2.

1068
00:52:24,270 --> 00:52:25,720
Đầu tiên chúng ta kiểm tra xem nó có 5.

1069
00:52:25,720 --> 00:52:26,700
Có ít hơn 5?

1070
00:52:26,700 --> 00:52:27,240
Không phải vậy.

1071
00:52:27,240 --> 00:52:29,510
Vì vậy, chúng ta phải tiếp tục tìm kiếm xuống.

1072
00:52:29,510 --> 00:52:30,940
Sau đó, bạn kiểm tra 2 off 3.

1073
00:52:30,940 --> 00:52:31,850
Là nó ít hơn?

1074
00:52:31,850 --> 00:52:32,350
Không.

1075
00:52:32,350 --> 00:52:35,430
Vì vậy, bạn biết 2 đã được chèn
vào mặt trước và 3 và 5

1076
00:52:35,430 --> 00:52:38,200
cả hai đều bị đẩy ra ngoài.

1077
00:52:38,200 --> 00:52:42,190
Làm điều này một lần nữa với 6 và 4.

1078
00:52:42,190 --> 00:52:48,962
Và chúng ta chỉ giữ lại kiểm tra cơ bản,
nơi mà chúng ta chỉ cần kiểm tra, rà soát, kiểm tra.

1079
00:52:48,962 --> 00:52:51,170
Và cho đến khi nó ở bên phải
vị trí, chúng tôi loại chỉ

1080
00:52:51,170 --> 00:52:54,890
chèn nó vào đúng vị trí,
đó là nơi mà tên của nó đến từ đâu.

1081
00:52:54,890 --> 00:52:59,830
>> Vì vậy, đó chỉ là những thuật toán,
giả cho mỗi gia nhập, loại,

1082
00:52:59,830 --> 00:53:04,990
về cách chúng tôi sẽ thực hiện
một loại chèn.

1083
00:53:04,990 --> 00:53:05,954
Giả là ở đây.

1084
00:53:05,954 --> 00:53:06,620
Đó là tất cả trực tuyến.

1085
00:53:06,620 --> 00:53:10,720
Không phải lo lắng nếu các bạn là
cố gắng để sao chép này xuống.

1086
00:53:10,720 --> 00:53:14,500
Vì vậy, một lần nữa, cùng question-- gì
sẽ là tốt nhất và tồi tệ nhất runtimes

1087
00:53:14,500 --> 00:53:16,120
cho sắp xếp chèn?

1088
00:53:16,120 --> 00:53:17,750
Nó rất giống với câu hỏi cuối cùng.

1089
00:53:17,750 --> 00:53:20,479
Tôi sẽ cung cấp cho các bạn, như, 30
giây để suy nghĩ về điều này như là tốt.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Có ai muốn
cho tôi thời gian chạy tồi tệ nhất?

1092
00:53:50,071 --> 00:53:50,570
Yeah.

1093
00:53:50,570 --> 00:53:51,490
>> Đung n bình phương.

1094
00:53:51,490 --> 00:53:52,573
>> Andi PENG: Nó n bình phương.

1095
00:53:52,573 --> 00:53:53,730
Và tại sao nó n bình?

1096
00:53:53,730 --> 00:53:57,562
>> Đung Bởi vì trong
thứ tự ngược lại, bạn có

1097
00:53:57,562 --> 00:54:02,619
đi qua n lần n, mà is--

1098
00:54:02,619 --> 00:54:03,660
Andi PENG: Yeah, chính xác.

1099
00:54:03,660 --> 00:54:06,610
Vì vậy, điều tương tự như trong các loại bong bóng.

1100
00:54:06,610 --> 00:54:08,720
Nếu danh sách này là trong
thứ tự giảm dần, bạn

1101
00:54:08,720 --> 00:54:11,240
sẽ phải kiểm tra một lần đầu tiên.

1102
00:54:11,240 --> 00:54:13,470
Và sau đó với mỗi
giá trị bổ sung, bạn

1103
00:54:13,470 --> 00:54:16,390
sẽ phải kiểm tra xem nó chống lại
mỗi giá trị duy nhất, phải không?

1104
00:54:16,390 --> 00:54:20,290
Và như vậy hoàn toàn, bạn sẽ làm cho
một n vượt qua lần khác n vượt qua, mà

1105
00:54:20,290 --> 00:54:21,750
được n bình phương.

1106
00:54:21,750 --> 00:54:22,860
Những gì về trường hợp tốt nhất?

1107
00:54:22,860 --> 00:54:24,360
Yeah.

1108
00:54:24,360 --> 00:54:28,840
>> Đung n trừ đi 1, bởi vì
là một trong những đầu tiên đã được bình phương.

1109
00:54:28,840 --> 00:54:30,270
>> Andi PENG: Vì vậy, gần gũi.

1110
00:54:30,270 --> 00:54:31,850
Câu trả lời thực sự là n.

1111
00:54:31,850 --> 00:54:37,189
Bởi vì trong khi người đầu tiên là
sắp xếp, nó có thể không actually-- nó

1112
00:54:37,189 --> 00:54:38,980
chúng tôi chỉ lucked ra, trong
ví dụ, rằng 2

1113
00:54:38,980 --> 00:54:40,930
xảy ra là số lượng nhỏ nhất.

1114
00:54:40,930 --> 00:54:43,680
Nhưng điều đó sẽ không phải luôn luôn là trường hợp.

1115
00:54:43,680 --> 00:54:48,040
Nếu 2 đã được sắp xếp trong đầu
nhưng bạn nhìn và có một 1 ở đây,

1116
00:54:48,040 --> 00:54:49,144
1 là sẽ bump nó.

1117
00:54:49,144 --> 00:54:51,060
Và nó sẽ kết thúc
lên được đụng anyways.

1118
00:54:51,060 --> 00:54:56,250
>> Vì vậy, trong trường hợp tốt nhất,
nó thực sự chỉ có được n.

1119
00:54:56,250 --> 00:54:59,090
Nếu bạn có 1, 2, 3,
4, 5, 6, 7, 8, bạn

1120
00:54:59,090 --> 00:55:00,940
sẽ chạy qua
rằng toàn bộ danh sách một lần

1121
00:55:00,940 --> 00:55:03,430
để kiểm tra xem nếu tất cả mọi thứ tốt đẹp của.

1122
00:55:03,430 --> 00:55:07,390
Là tất cả mọi người rõ ràng về hoạt động
lần lựa chọn là tốt?

1123
00:55:07,390 --> 00:55:09,960
Tôi biết tôi sẽ thông qua
những thực sự nhanh chóng.

1124
00:55:09,960 --> 00:55:13,330
Nhưng chỉ biết rằng nếu bạn biết
khái niệm chung, bạn nên được tốt.

1125
00:55:13,330 --> 00:55:16,070
ĐƯỢC.

1126
00:55:16,070 --> 00:55:19,790
Vì vậy, tôi sẽ chỉ cho các bạn cái có thể, như,
một phút để nói chuyện với hàng xóm của bạn

1127
00:55:19,790 --> 00:55:21,890
về những gì đang có chỉ số
những khác biệt chính

1128
00:55:21,890 --> 00:55:23,540
giữa các loại của các loại.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Chúng tôi sẽ đi qua đó sớm.

1131
00:56:25,570 --> 00:56:26,444
Đung Oh, OK.

1132
00:56:26,444 --> 00:56:27,320
Andi PENG: Yeah.

1133
00:56:27,320 --> 00:56:28,380
ĐƯỢC.

1134
00:56:28,380 --> 00:56:33,420
Cool, hãy triệu tập lại như một lớp học.

1135
00:56:33,420 --> 00:56:34,330
ĐƯỢC.

1136
00:56:34,330 --> 00:56:37,579
Vì vậy, đây là loại một
mở câu hỏi trong ý nghĩa

1137
00:56:37,579 --> 00:56:39,120
rằng có rất nhiều câu trả lời cho họ.

1138
00:56:39,120 --> 00:56:40,746
Và chúng ta sẽ đi qua một số trong số họ một thời gian ngắn.

1139
00:56:40,746 --> 00:56:43,411
Tôi chỉ muốn để có được các bạn
suy nghĩ về những gì phân biệt

1140
00:56:43,411 --> 00:56:44,530
cả ba loại của các loại.

1141
00:56:44,530 --> 00:56:47,440
Và tôi nghe, cũng, một tuyệt vời
question-- gì merge sort làm gì?

1142
00:56:47,440 --> 00:56:50,110
Great câu hỏi, bởi vì đó là
những gì chúng tôi đang bao phủ tới.

1143
00:56:50,110 --> 00:56:52,850
>> Vì vậy, hợp nhất phân loại là
một loại có chức năng

1144
00:56:52,850 --> 00:56:56,100
rất khác với các loại khác.

1145
00:56:56,100 --> 00:56:58,180
Như các bạn có thể see--
David đã làm demo

1146
00:56:58,180 --> 00:57:01,130
nơi ông đã có tất cả các mát
tiếng động khi nhìn thấy như thế nào hợp nhất

1147
00:57:01,130 --> 00:57:04,010
loại chạy, như thế, vô hạn
nhanh hơn so với hai loại khác?

1148
00:57:04,010 --> 00:57:04,510
ĐƯỢC.

1149
00:57:04,510 --> 00:57:07,580
Vì vậy, đó là bởi vì hợp nhất
loại thực hiện phân chia đó

1150
00:57:07,580 --> 00:57:11,020
và chinh phục khái niệm mà chúng ta đã
nói chuyện về rất nhiều trong bài giảng.

1151
00:57:11,020 --> 00:57:14,550
Trong ý nghĩa đó, chúng tôi muốn làm việc
thông minh hơn, không khó khăn hơn, khi bạn chia

1152
00:57:14,550 --> 00:57:18,120
và chinh phục các vấn đề, và phá vỡ chúng
xuống, và sau đó đặt chúng lại với nhau,

1153
00:57:18,120 --> 00:57:19,930
những điều tốt đẹp luôn luôn xảy ra.

1154
00:57:19,930 --> 00:57:21,960
>> Vì vậy, cách đó hợp nhất
loại cơ bản các công trình

1155
00:57:21,960 --> 00:57:24,660
là nó chia một
mảng được phân loại trong một nửa.

1156
00:57:24,660 --> 00:57:26,500
Và sau đó nó có hai nửa của mảng.

1157
00:57:26,500 --> 00:57:28,220
Và nó chỉ sắp xếp những hai nửa.

1158
00:57:28,220 --> 00:57:31,750
Nó chỉ cần giữ chia một nửa, trong
một nửa, một nửa cho đến khi tất cả mọi thứ được sắp xếp

1159
00:57:31,750 --> 00:57:33,680
và sau đó đệ quy
đặt nó tất cả cùng nhau.

1160
00:57:33,680 --> 00:57:36,550
>> Vì vậy, đó là thực sự trừu tượng.

1161
00:57:36,550 --> 00:57:38,750
Vì vậy, đây chỉ là một chút của mã giả.

1162
00:57:38,750 --> 00:57:41,040
Điều đó có ý nghĩa trong
cách nó đang chạy?

1163
00:57:41,040 --> 00:57:43,870
Vì vậy, chúng ta hãy chỉ nói rằng bạn có một
mảng n phần tử, phải không?

1164
00:57:43,870 --> 00:57:45,450
Nếu n là nhỏ hơn 2, bạn có thể quay trở lại.

1165
00:57:45,450 --> 00:57:49,040
Bởi vì bạn biết rằng nếu có
chỉ có một điều, nó phải được sắp xếp.

1166
00:57:49,040 --> 00:57:52,600
Ngoài ra, bạn sắp xếp một nửa trái,
và sau đó bạn sắp xếp một nửa bên phải,

1167
00:57:52,600 --> 00:57:54,140
và sau đó bạn hợp nhất.

1168
00:57:54,140 --> 00:57:56,979
>> Vì vậy, trong khi đó có vẻ rất dễ dàng,
trong thực tế, suy nghĩ về nó

1169
00:57:56,979 --> 00:58:00,270
loại khó khăn. Bởi vì bạn đang như,
tốt, đó là loại chạy trên chính nó.

1170
00:58:00,270 --> 00:58:00,769
Bên phải?

1171
00:58:00,769 --> 00:58:02,430
Nó đang chạy trên chính nó.

1172
00:58:02,430 --> 00:58:05,479
Vì vậy, trong ý nghĩa đó, David xúc động
khi đệ quy trong lớp.

1173
00:58:05,479 --> 00:58:07,270
Và đó là một khái niệm
chúng ta sẽ nói về nhiều hơn.

1174
00:58:07,270 --> 00:58:11,430
Đó là điều này, hai dòng
ở đây, thực sự chỉ là các chương trình

1175
00:58:11,430 --> 00:58:13,860
nói cho nó tự chạy
với đầu vào khác nhau.

1176
00:58:13,860 --> 00:58:17,230
Vì vậy, thay vì chạy trốn chính nó với
toàn bộ các yếu tố n,

1177
00:58:17,230 --> 00:58:20,530
bạn có thể phá vỡ nó xuống
nửa bên trái và nửa bên phải

1178
00:58:20,530 --> 00:58:22,680
và sau đó chạy nó một lần nữa.

1179
00:58:22,680 --> 00:58:26,050
>> Và sau đó chúng tôi sẽ xem xét nó trực quan,
bởi vì tôi là một người học trực quan.

1180
00:58:26,050 --> 00:58:27,270
Nó hoạt động tốt hơn cho tôi.

1181
00:58:27,270 --> 00:58:29,890
Vì vậy, chúng tôi sẽ xem xét một ví dụ trực quan ở đây.

1182
00:58:29,890 --> 00:58:36,237
>> Hãy nói rằng chúng tôi có một mảng, sáu
yếu tố, 3, 5, 2, 6, 4, 1, không được sắp xếp.

1183
00:58:36,237 --> 00:58:37,820
Được rồi, có rất nhiều trên trang này.

1184
00:58:37,820 --> 00:58:43,179
Vì vậy, nếu các bạn có thể ghé qua
Bước đầu tiên ở đây, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
bạn có thể chia nhỏ nó ra.

1186
00:58:44,220 --> 00:58:45,976
Bạn có 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Bạn biết rằng những aren't-- bạn
không biết nếu họ đang sắp xếp hay không,

1188
00:58:48,850 --> 00:58:52,517
vì vậy bạn giữ phá vỡ chúng xuống, một nửa,
một nửa, một nửa, cho đến khi cuối cùng,

1189
00:58:52,517 --> 00:58:53,600
bạn chỉ có một phần tử.

1190
00:58:53,600 --> 00:58:56,790
Và một trong những yếu tố luôn được sắp xếp, phải không?

1191
00:58:56,790 --> 00:59:01,560
>> Vì vậy, chúng ta biết rằng 3, 5, 2, 4, 6,
1, bởi chính họ, đều được sắp xếp.

1192
00:59:01,560 --> 00:59:05,870
Và bây giờ chúng tôi có thể đặt chúng lại với nhau.

1193
00:59:05,870 --> 00:59:07,510
Vì vậy, chúng ta biết được 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Chúng tôi đưa những người với nhau.

1195
00:59:08,510 --> 00:59:09,617
Chúng tôi biết đó là sắp xếp.

1196
00:59:09,617 --> 00:59:10,450
2 nhân vẫn còn đó.

1197
00:59:10,450 --> 00:59:11,830
Chúng ta có thể đặt 4 và 6 với nhau.

1198
00:59:11,830 --> 00:59:13,996
Chúng tôi biết rằng đó là sắp xếp,
vì vậy chúng tôi đặt lại với nhau.

1199
00:59:13,996 --> 00:59:14,940
Và 1 là có.

1200
00:59:14,940 --> 00:59:18,720
>> Và sau đó bạn chỉ cần nhìn vào
hai nửa này ngay tại đây.

1201
00:59:18,720 --> 00:59:21,300
Bạn có 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Bạn chỉ có thể so sánh
bắt đầu của tất cả mọi thứ.

1203
00:59:23,465 --> 00:59:26,340
Bởi vì bạn biết rằng điều này được sắp xếp
và bạn biết rằng đó là sắp xếp.

1204
00:59:26,340 --> 00:59:29,360
Vì vậy, sau đó bạn thậm chí không phải
so sánh 5, bạn chỉ cần so sánh 3.

1205
00:59:29,360 --> 00:59:32,070
Và 2 là ít hơn 3, vì vậy
Bạn có biết 2 phải đi cuối cùng.

1206
00:59:32,070 --> 00:59:33,120
>> Điều tương tự cũng ở đó.

1207
00:59:33,120 --> 00:59:34,740
1 phải đi đây.

1208
00:59:34,740 --> 00:59:37,330
Và sau đó khi bạn đi đến đặt
hai giá trị với nhau,

1209
00:59:37,330 --> 00:59:39,950
Bạn có biết rằng điều này được sắp xếp và
Bạn có biết rằng đó là sắp xếp.

1210
00:59:39,950 --> 00:59:43,240
Vì vậy, sau đó là 1 và
2, 1 là ít hơn 2.

1211
00:59:43,240 --> 00:59:45,570
Điều đó nói với bạn rằng 1
nên đi vào cuối năm nay

1212
00:59:45,570 --> 00:59:47,480
mà không cần nhìn vào 3 hoặc 5.

1213
00:59:47,480 --> 00:59:50,100
Và sau đó là 4, bạn có thể chỉ
kiểm tra, nó đi ngay đây.

1214
00:59:50,100 --> 00:59:51,480
Bạn không cần phải nhìn vào 5.

1215
00:59:51,480 --> 00:59:52,570
Cùng một điều với 6.

1216
00:59:52,570 --> 00:59:55,860
Bạn biết rằng nó chỉ 6--
không cần phải được xem xét.

1217
00:59:55,860 --> 00:59:57,870
>> Và như vậy theo cách đó, bạn
chỉ tiết kiệm cho mình

1218
00:59:57,870 --> 00:59:59,526
rất nhiều các bước khi bạn đang so sánh.

1219
00:59:59,526 --> 01:00:02,150
Bạn không cần phải so sánh mỗi
yếu tố chống lại các yếu tố khác.

1220
01:00:02,150 --> 01:00:05,230
Bạn chỉ cần so sánh với những người
mà bạn cần phải so sánh nó với.

1221
01:00:05,230 --> 01:00:06,870
Vì vậy, đó là loại một khái niệm trừu tượng.

1222
01:00:06,870 --> 01:00:10,540
Không phải lo lắng nếu nó không
khá đánh bạn phải được nêu ra.

1223
01:00:10,540 --> 01:00:14,740
Nhưng nhìn chung, đây là
làm thế nào một loại hợp nhất hoạt động.

1224
01:00:14,740 --> 01:00:17,750
Câu hỏi, câu hỏi nhanh,
trước khi tôi di chuyển trên?

1225
01:00:17,750 --> 01:00:18,550
Yeah.

1226
01:00:18,550 --> 01:00:22,230
>> Đung Vì vậy, bạn nói rằng bạn có
1, và sau đó là 4, và 6

1227
01:00:22,230 --> 01:00:23,860
và đặt chúng trong.

1228
01:00:23,860 --> 01:00:26,800
Vì vậy, không those-- không
bạn nhìn vào họ

1229
01:00:26,800 --> 01:00:28,544
như các yếu tố riêng biệt, không phải là toàn bộ?

1230
01:00:28,544 --> 01:00:29,210
Andi PENG: Yeah.

1231
01:00:29,210 --> 01:00:32,020
Vì vậy, những gì đang xảy ra
là bạn cơ bản

1232
01:00:32,020 --> 01:00:33,650
đang tạo ra một mảng mới.

1233
01:00:33,650 --> 01:00:36,690
Vì vậy, bạn biết rằng, ở đây, tôi có
hai mảng có kích thước 3, phải không?

1234
01:00:36,690 --> 01:00:39,600
Vì vậy, bạn biết rằng mảng được sắp xếp của tôi
cần phải có sáu yếu tố.

1235
01:00:39,600 --> 01:00:42,270
Vì vậy, bạn chỉ cần tạo một
số tiền mới của bộ nhớ.

1236
01:00:42,270 --> 01:00:44,270
Vì vậy, bạn đang loại như
đang lãng phí bộ nhớ,

1237
01:00:44,270 --> 01:00:46,186
nhưng điều đó không quan trọng
vì nó quá nhỏ.

1238
01:00:46,186 --> 01:00:48,590
Vì vậy, bạn nhìn vào 1
và bạn nhìn vào 2.

1239
01:00:48,590 --> 01:00:50,770
Và bạn có biết rằng 1 là ít hơn 2.

1240
01:00:50,770 --> 01:00:53,840
Vì vậy, bạn có biết rằng 1 cần đi
đầu của tất cả những người.

1241
01:00:53,840 --> 01:00:55,850
>> Bạn thậm chí không cần phải
nhìn vào 3 và 5.

1242
01:00:55,850 --> 01:00:57,400
Vì vậy, bạn biết 1 đến đó.

1243
01:00:57,400 --> 01:00:59,300
Sau đó, về cơ bản bạn chop off 1.

1244
01:00:59,300 --> 01:01:00,370
Đó là, như, đã chết cho chúng ta.

1245
01:01:00,370 --> 01:01:03,690
Sau đó, chúng tôi chỉ có 2,
3, 5, và sau đó 4 và 6.

1246
01:01:03,690 --> 01:01:06,270
Và sau đó bạn biết rằng, bạn
so sánh 4 và 2,

1247
01:01:06,270 --> 01:01:07,560
oh, 2 nên đi vào đó.

1248
01:01:07,560 --> 01:01:09,685
Vì vậy, bạn tiếng tom 2 xuống, bạn cắt nó đi.

1249
01:01:09,685 --> 01:01:12,060
Vì vậy, sau đó bạn chỉ có 3
và 5 trong 4 và 6.

1250
01:01:12,060 --> 01:01:14,650
Và bạn chỉ cần giữ chặt nó đi
cho đến khi bạn đặt chúng trong mảng.

1251
01:01:14,650 --> 01:01:17,110
>> Đung Vì vậy, bạn chỉ cần luôn luôn
so sánh [Không nghe thấy]?

1252
01:01:17,110 --> 01:01:17,710
>> Andi PENG: Chính xác.

1253
01:01:17,710 --> 01:01:19,590
Vì vậy, trong ý nghĩa đó, bạn
chỉ so sánh, về cơ bản,

1254
01:01:19,590 --> 01:01:21,240
một số đối số khác.

1255
01:01:21,240 --> 01:01:22,990
Và bởi vì bạn biết
mà nó được sắp xếp, bạn

1256
01:01:22,990 --> 01:01:24,350
không cần phải xem xét thông qua
tất cả các con số.

1257
01:01:24,350 --> 01:01:25,870
Bạn chỉ cần nhìn vào cái đầu tiên.

1258
01:01:25,870 --> 01:01:27,582
Và sau đó bạn chỉ có thể tiếng tom
chúng xuống, bởi vì bạn biết

1259
01:01:27,582 --> 01:01:29,640
họ thuộc về nơi họ cần phải thuộc về.

1260
01:01:29,640 --> 01:01:31,030
Yeah.

1261
01:01:31,030 --> 01:01:32,920
Câu hỏi hay.

1262
01:01:32,920 --> 01:01:35,290
>> Và sau đó nếu có của bạn
có một chút tham vọng,

1263
01:01:35,290 --> 01:01:38,660
cảm thấy miễn phí để xem xét mã này.

1264
01:01:38,660 --> 01:01:40,680
Đây thực sự là
thực hiện vật lý

1265
01:01:40,680 --> 01:01:42,150
làm thế nào chúng ta sẽ viết sắp xếp hợp nhất.

1266
01:01:42,150 --> 01:01:44,070
Và bạn có thể thấy, nó rất ngắn.

1267
01:01:44,070 --> 01:01:46,310
Nhưng những ý tưởng đằng sau
nó là khá phức tạp.

1268
01:01:46,310 --> 01:01:50,865
Vì vậy, nếu bạn cảm thấy như bản vẽ này ra
trong tối nay ở nhà của bạn, cảm thấy tự do để.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> ĐƯỢC.

1271
01:01:54,740 --> 01:01:58,070
Vì vậy, David cũng đã đi qua này trong bài giảng.

1272
01:01:58,070 --> 01:02:00,660
Trường hợp tốt nhất là gì
runtimes, runtimes trường hợp xấu nhất,

1273
01:02:00,660 --> 01:02:05,680
và các runtimes dự kiến ​​sắp xếp hợp nhất?

1274
01:02:05,680 --> 01:02:07,260
Một vài giây để suy nghĩ.

1275
01:02:07,260 --> 01:02:11,198
Điều này là khá khó khăn, nhưng loại
trực quan nếu bạn nghĩ về nó.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Được rồi.

1278
01:02:23,054 --> 01:02:25,269
>> Đung là điều tồi tệ nhất log n trường hợp n?

1279
01:02:25,269 --> 01:02:26,060
Andi PENG: Chính xác.

1280
01:02:26,060 --> 01:02:29,380
Và tại sao nó n log n.

1281
01:02:29,380 --> 01:02:32,230
>> Đung không phải vì nó
trở nên nhanh hơn theo cấp số nhân,

1282
01:02:32,230 --> 01:02:35,390
Nó giống như một chức năng mà
thay vì chỉ đơn giản là n

1283
01:02:35,390 --> 01:02:37,529
bình phương hay một cái gì đó?

1284
01:02:37,529 --> 01:02:38,320
Andi PENG: Chính xác.

1285
01:02:38,320 --> 01:02:40,750
Vì vậy, lý do tại sao
thời gian chạy trên này là n log

1286
01:02:40,750 --> 01:02:44,310
n là because-- bạn là gì
làm trong tất cả các bước?

1287
01:02:44,310 --> 01:02:46,190
Bạn chỉ cần cắt nó ra, phải không?

1288
01:02:46,190 --> 01:02:48,750
Và như vậy khi chúng tôi đang làm việc
đăng nhập, tất cả những gì nó đang làm gì

1289
01:02:48,750 --> 01:02:53,150
được phân chia một vấn đề trong một nửa,
một nửa, một nửa, trong hơn nửa.

1290
01:02:53,150 --> 01:02:56,430
Và trong ý nghĩa đó, bạn có thể loại
loại bỏ các mô hình tuyến tính

1291
01:02:56,430 --> 01:02:57,510
mà chúng ta đã sử dụng.

1292
01:02:57,510 --> 01:03:00,254
Bởi vì khi bạn chop
mọi thứ trong một nửa, đó là một bản ghi.

1293
01:03:00,254 --> 01:03:02,420
Đó chỉ là toán học
cách đại diện cho nó.

1294
01:03:02,420 --> 01:03:06,310
>> Và cuối cùng, ở cuối, bạn
chỉ cần làm một đường chuyền cuối cùng thông qua

1295
01:03:06,310 --> 01:03:07,930
để đặt tất cả chúng theo thứ tự, phải không?

1296
01:03:07,930 --> 01:03:10,330
Và do đó, nếu bạn chỉ cần có để
kiểm tra một điều, đó là n.

1297
01:03:10,330 --> 01:03:13,420
Và như vậy bạn đang loại
nhân hai cùng nhau.

1298
01:03:13,420 --> 01:03:17,660
Vì vậy, nó giống như bạn đã có mà thức
kiểm tra n xuống đây với một bản ghi của n

1299
01:03:17,660 --> 01:03:18,390
trên này này.

1300
01:03:18,390 --> 01:03:21,060
Và nếu bạn nhân
họ, đó là n log n.

1301
01:03:21,060 --> 01:03:26,100
>> Và do đó, các trường hợp tốt nhất và tồi tệ nhất
trường hợp và dự kiến ​​sẽ được tất cả n log n.

1302
01:03:26,100 --> 01:03:27,943
Nó cũng giống như loại khác.

1303
01:03:27,943 --> 01:03:30,090
Nó giống như sắp xếp chọn
trong ý nghĩa rằng nó

1304
01:03:30,090 --> 01:03:32,131
không có vấn đề gì của bạn
danh sách là, nó chỉ đi

1305
01:03:32,131 --> 01:03:34,801
để làm điều tương tự mỗi lần duy nhất.

1306
01:03:34,801 --> 01:03:35,300
ĐƯỢC.

1307
01:03:35,300 --> 01:03:39,950
Vì vậy, các bạn có thể thấy, mặc dù
các loại mà chúng ta đã đi through-- n

1308
01:03:39,950 --> 01:03:41,660
bình phương, nó không phải là rất hiệu quả.

1309
01:03:41,660 --> 01:03:47,060
Và ngay cả điều này n log n là
không phải là hiệu quả nhất.

1310
01:03:47,060 --> 01:03:49,720
Nếu các bạn đang tò mò,
có cơ chế loại

1311
01:03:49,720 --> 01:03:54,310
mà rất hiệu quả mà họ đang
gần như cơ bản phẳng trong thời gian chạy.

1312
01:03:54,310 --> 01:03:55,420
>> Bạn đã có một số log n của.

1313
01:03:55,420 --> 01:03:58,190
Bạn đã có một số bản ghi log n của.

1314
01:03:58,190 --> 01:04:00,330
Chúng tôi không động chạm đến họ
trong lớp học này ngay bây giờ.

1315
01:04:00,330 --> 01:04:02,663
Nhưng nếu các bạn đang tò mò,
cảm thấy tự do để google, có chuyện gì

1316
01:04:02,663 --> 01:04:04,392
việc phân loại các cơ chế hiệu quả nhất.

1317
01:04:04,392 --> 01:04:06,350
Tôi không biết, có rất
một số những người thực sự buồn cười,

1318
01:04:06,350 --> 01:04:09,860
like-- có một số thực sự
những vui mà mọi người thực hiện.

1319
01:04:09,860 --> 01:04:12,210
Và bạn tự hỏi làm thế nào họ
bao giờ nghĩ về điều đó.

1320
01:04:12,210 --> 01:04:15,730
Vì vậy, google, nếu bạn có một số phụ tùng
Hiện, trên, một số cách hài hước là những gì

1321
01:04:15,730 --> 01:04:17,730
rằng people-- cũng như
người ways-- hiệu quả

1322
01:04:17,730 --> 01:04:20,371
đã có thể thực hiện các loại.

1323
01:04:20,371 --> 01:04:20,870
ĐƯỢC.

1324
01:04:20,870 --> 01:04:22,880
Và đây chỉ là một biểu đồ nhỏ tiện dụng.

1325
01:04:22,880 --> 01:04:26,850
Tôi biết tất cả các bạn, trước đó đố 0,
sẽ được ở trong phòng của bạn có thể cố gắng

1326
01:04:26,850 --> 01:04:27,960
để ghi nhớ đó.

1327
01:04:27,960 --> 01:04:30,940
Vì vậy, đó là tốt đẹp trong đó cho các bạn.

1328
01:04:30,940 --> 01:04:37,120
Chỉ cần đừng quên rằng logic made--
tại sao những con số đã xảy ra.

1329
01:04:37,120 --> 01:04:39,870
Nếu bạn luôn bị mất, chỉ cần thực hiện
chắc chắn rằng bạn biết những gì các loại đang có.

1330
01:04:39,870 --> 01:04:40,820
Và bạn có thể chạy qua
chúng trong tâm trí của bạn

1331
01:04:40,820 --> 01:04:42,903
để tìm ra lý do tại sao những người
câu trả lời là những câu trả lời.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Được rồi.

1334
01:04:47,600 --> 01:04:49,680
Vì vậy, chúng ta sẽ di chuyển
trên, cuối cùng, để tìm kiếm.

1335
01:04:49,680 --> 01:04:51,638
Bởi vì như những người bạn
những người đã đọc pset,

1336
01:04:51,638 --> 01:04:55,175
tìm kiếm cũng là một phần của
Vấn đề của tuần này đề ra.

1337
01:04:55,175 --> 01:04:57,300
Bạn sẽ được yêu cầu để thực hiện
hai loại tìm kiếm.

1338
01:04:57,300 --> 01:05:00,070
Một là tìm kiếm tuyến tính và
một là một tìm kiếm nhị phân.

1339
01:05:00,070 --> 01:05:01,760
>> Vì vậy, việc tìm kiếm tuyến tính là khá dễ dàng.

1340
01:05:01,760 --> 01:05:04,070
Bạn chỉ muốn tìm kiếm yếu tố
của một danh sách để xem nếu bạn nhận được nó.

1341
01:05:04,070 --> 01:05:05,444
Bạn chỉ cần có để lặp qua.

1342
01:05:05,444 --> 01:05:08,170
Và nếu nó bằng gì gì đó,
bạn chỉ có thể trả lại nó, phải không?

1343
01:05:08,170 --> 01:05:10,890
Nhưng một trong những điều đó chúng tôi nhất
thích nói chuyện về

1344
01:05:10,890 --> 01:05:14,550
là tìm kiếm nhị phân, phải, đó là
phân chia và cơ chế chinh phục mà

1345
01:05:14,550 --> 01:05:18,190
David đã được chứng minh trong bài giảng.

1346
01:05:18,190 --> 01:05:20,810
>> Hãy nhớ rằng các ví dụ cuốn sách điện thoại
rằng ông tiếp tục đưa lên,

1347
01:05:20,810 --> 01:05:23,960
một trong đó ông loại vật lộn
một chút về năm vừa qua,

1348
01:05:23,960 --> 01:05:27,530
nơi bạn chia các vấn đề trong một nửa,
một nửa, một nửa, một lần nữa và một lần nữa,

1349
01:05:27,530 --> 01:05:30,730
cho đến khi bạn tìm thấy những gì bạn đang tìm kiếm?

1350
01:05:30,730 --> 01:05:33,727
Và bạn đã có
thời gian chạy của điều đó.

1351
01:05:33,727 --> 01:05:35,810
Và bạn có thể thấy, đó là
đáng kể hiệu quả hơn

1352
01:05:35,810 --> 01:05:39,080
hơn bất kỳ loại hình khác của tìm kiếm.

1353
01:05:39,080 --> 01:05:41,880
>> Vì vậy, cách mà chúng ta sẽ đi về
thực hiện một tìm kiếm nhị phân

1354
01:05:41,880 --> 01:05:46,510
là, nếu chúng ta có một mảng,
Chỉ số 0-6, bảy yếu tố,

1355
01:05:46,510 --> 01:05:49,790
chúng ta có thể nhìn vào giữa, right--
xin lỗi, nếu câu hỏi của chúng tôi first--

1356
01:05:49,790 --> 01:05:53,840
nếu chúng ta muốn đặt câu hỏi về, không
mảng chứa đựng yếu tố 7,

1357
01:05:53,840 --> 01:05:56,840
rõ ràng, là con người, và có
như một mảng nhỏ, thật dễ dàng cho chúng tôi

1358
01:05:56,840 --> 01:05:58,210
nói có.

1359
01:05:58,210 --> 01:06:05,750
Nhưng cách thức để thực hiện một số nhị phân
tìm kiếm sẽ được xem xét ở giữa.

1360
01:06:05,750 --> 01:06:08,020
>> Chúng ta biết rằng chỉ số 3 là
giữa, bởi vì chúng tôi

1361
01:06:08,020 --> 01:06:09,270
biết có bảy yếu tố.

1362
01:06:09,270 --> 01:06:10,670
Những gì 7 chia cho 2?

1363
01:06:10,670 --> 01:06:12,850
Bạn có thể chặt rằng thêm 1.

1364
01:06:12,850 --> 01:06:14,850
Bạn đã có 3 ở giữa.

1365
01:06:14,850 --> 01:06:17,590
Vì vậy, là mảng của 3 bằng 7?

1366
01:06:17,590 --> 01:06:18,900
Nó không phải là, phải không?

1367
01:06:18,900 --> 01:06:21,050
Nhưng chúng ta có thể làm một vài kiểm tra.

1368
01:06:21,050 --> 01:06:25,380
Là mảng của 3 ít hơn 7 hoặc
là mảng của 3 lớn hơn 7?

1369
01:06:25,380 --> 01:06:27,240
>> Và chúng ta biết rằng nó ít hơn 7.

1370
01:06:27,240 --> 01:06:30,259
Vì vậy, chúng ta biết rằng, oh, nó phải
không thể là trong nửa trái.

1371
01:06:30,259 --> 01:06:32,300
Chúng tôi biết rằng nó phải được
ở nửa bên phải, phải không?

1372
01:06:32,300 --> 01:06:34,662
Vì vậy, chúng tôi chỉ có thể chặt một nửa mảng.

1373
01:06:34,662 --> 01:06:36,370
Chúng tôi thậm chí không có để
nhìn vào nó nữa.

1374
01:06:36,370 --> 01:06:38,711
Bởi vì chúng ta biết rằng
một nửa của problem-- của chúng tôi

1375
01:06:38,711 --> 01:06:41,210
chúng ta biết rằng câu trả lời là trong
nửa bên phải của vấn đề của chúng tôi.

1376
01:06:41,210 --> 01:06:42,580
Vì vậy, chúng ta chỉ cần nhìn vào đó bây giờ.

1377
01:06:42,580 --> 01:06:44,860
>> Vì vậy, bây giờ chúng ta nhìn vào
giữa những gì còn lại.

1378
01:06:44,860 --> 01:06:46,880
Đó chỉ số 5.

1379
01:06:46,880 --> 01:06:50,200
Chúng tôi làm việc kiểm tra một lần nữa
và chúng tôi thấy rằng nó nhỏ hơn.

1380
01:06:50,200 --> 01:06:52,050
Vì vậy, chúng tôi nhìn bên trái của điều đó.

1381
01:06:52,050 --> 01:06:53,430
Và sau đó chúng tôi nhìn thấy tờ séc đó.

1382
01:06:53,430 --> 01:06:57,600
Là giá trị mảng ở
Chỉ số 4 bằng 7?

1383
01:06:57,600 --> 01:06:58,260
Nó là.

1384
01:06:58,260 --> 01:07:03,580
Vì vậy, chúng ta có thể trở thành sự thật, bởi vì
chúng tôi thấy các giá trị trong danh sách của chúng tôi.

1385
01:07:03,580 --> 01:07:06,738
Liệu cách tôi đã đi qua
đó có ý nghĩa với tất cả mọi người?

1386
01:07:06,738 --> 01:07:08,760
ĐƯỢC.

1387
01:07:08,760 --> 01:07:11,670
Tôi sẽ cho các bạn cái có thể, như,
ba, bốn phút để tìm ra

1388
01:07:11,670 --> 01:07:13,270
làm thế nào để giả này.

1389
01:07:13,270 --> 01:07:18,070
>> Vì vậy, hãy tưởng tượng tôi hỏi bạn phải viết một
chức năng gọi là search () đó quay trở lại

1390
01:07:18,070 --> 01:07:20,640
một giá trị, một giá trị Boolean,
đó là sự thật hay false-- như,

1391
01:07:20,640 --> 01:07:22,970
đúng nếu bạn thấy
giá trị, false nếu bạn đã không.

1392
01:07:22,970 --> 01:07:25,230
Và sau đó bạn có
thông qua vào giá trị bạn

1393
01:07:25,230 --> 01:07:28,410
đang tìm kiếm vào các giá trị, trong đó
là array-- oh, chắc chắn tôi đặt

1394
01:07:28,410 --> 01:07:29,410
mà ở chỗ sai.

1395
01:07:29,410 --> 01:07:29,580
ĐƯỢC.

1396
01:07:29,580 --> 01:07:31,829
Anyways, mà cần phải có
từng đến quyền của các giá trị.

1397
01:07:31,829 --> 01:07:36,280
Và sau đó int n là số
các phần tử trong mảng đó.

1398
01:07:36,280 --> 01:07:39,430
Làm thế nào bạn sẽ đi về cố gắng
để giả rằng vấn đề trong?

1399
01:07:39,430 --> 01:07:41,630
Tôi sẽ cung cấp cho các bạn thích
ba phút để làm điều đó.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Không, tôi nghĩ rằng có only--
yeah, có một trong những quyền lên đây.

1402
01:08:02,595 --> 01:08:03,261
Đung, được không?

1403
01:08:03,261 --> 01:08:04,388
Andi PENG: Vâng, tôi đã có em.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Là làm việc đó?

1406
01:08:11,050 --> 01:08:12,290
OK, mát mẻ.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> ĐƯỢC.

1409
01:10:44,720 --> 01:10:47,630
Tất cả các chàng trai phải, chúng tôi
sẽ kiềm chế nó trong.

1410
01:10:47,630 --> 01:10:49,730
ĐƯỢC.

1411
01:10:49,730 --> 01:10:54,020
Vì vậy, giả sử chúng ta đã có này đáng yêu
ít mảng với giá trị n trong đó.

1412
01:10:54,020 --> 01:10:55,170
Tôi không vẽ các đường.

1413
01:10:55,170 --> 01:10:58,649
Nhưng làm thế nào chúng ta sẽ đi về
cố gắng viết này?

1414
01:10:58,649 --> 01:11:00,440
Có ai muốn
cung cấp cho tôi những dòng đầu tiên?

1415
01:11:00,440 --> 01:11:02,814
Nếu bạn muốn cho tôi
Dòng đầu tiên của mã giả này.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> Đung [Không nghe thấy]

1418
01:11:08,430 --> 01:11:10,138
Đung Bạn muốn
để lặp through--

1419
01:11:10,138 --> 01:11:11,094
Đung Chỉ cần một vòng lặp?

1420
01:11:11,094 --> 01:11:11,760
Đung --cho.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> Andi PENG: Vì vậy, con này một chút khéo léo.

1423
01:11:17,780 --> 01:11:23,130
Hãy nghĩ about-- bạn muốn
để tiếp tục chạy vòng lặp này

1424
01:11:23,130 --> 01:11:27,950
hơn và hơn một lần nữa cho đến khi nào?

1425
01:11:27,950 --> 01:11:30,819
>> Đung Cho đến [Không nghe thấy]
giá trị bằng với giá trị đó.

1426
01:11:30,819 --> 01:11:31,610
Andi PENG: Chính xác.

1427
01:11:31,610 --> 01:11:33,900
Vì vậy, bạn có thể thực sự chỉ write--
chúng tôi thậm chí có thể đơn giản hóa nó hơn.

1428
01:11:33,900 --> 01:11:35,630
Chúng tôi chỉ có thể làm một vòng lặp trong khi, phải không?

1429
01:11:35,630 --> 01:11:39,380
Vì vậy, bạn chỉ có thể có loop--
chúng tôi biết rằng đó là một thời gian.

1430
01:11:39,380 --> 01:11:42,850
Nhưng đối với ngay bây giờ, tôi sẽ
để nói "loop" - thông qua những gì?

1431
01:11:42,850 --> 01:11:46,640
Vòng until-- là gì
điều kiện kết thúc của chúng tôi?

1432
01:11:46,640 --> 01:11:47,510
Tôi nghĩ rằng tôi nghe nó.

1433
01:11:47,510 --> 01:11:48,530
Tôi nghe ai đó nói nó.

1434
01:11:48,530 --> 01:11:51,255
>> Đung giá trị tương đương với trung bình.

1435
01:11:51,255 --> 01:11:52,255
Andi PENG: Nói lại lần nữa.

1436
01:11:52,255 --> 01:11:54,470
Đung Hoặc, cho đến khi
giá trị mà bạn đang tìm kiếm

1437
01:11:54,470 --> 01:11:58,470
cho là tương đương với giá trị trung bình.

1438
01:11:58,470 --> 01:12:00,280
>> Andi PENG: Điều gì nếu nó không ở trong đó?

1439
01:12:00,280 --> 01:12:03,113
Điều gì nếu giá trị bạn đang tìm kiếm
cho là không thực sự trong mảng này?

1440
01:12:03,113 --> 01:12:05,890
Đung Bạn quay trở lại 1.

1441
01:12:05,890 --> 01:12:08,850
>> Andi PENG: Nhưng những gì chúng ta muốn
vòng lặp cho đến khi chúng tôi có một điều kiện?

1442
01:12:08,850 --> 01:12:09,350
Yeah.

1443
01:12:09,350 --> 01:12:11,239
>> Đung Cho đến khi chỉ có một giá trị?

1444
01:12:11,239 --> 01:12:13,530
Andi PENG: Bạn có thể lặp
until-- để bạn biết rằng bạn đang

1445
01:12:13,530 --> 01:12:15,714
sẽ có một giá trị tối đa, phải không?

1446
01:12:15,714 --> 01:12:18,130
Và bạn biết rằng bạn đang đi
để có một giá trị min, phải không?

1447
01:12:18,130 --> 01:12:20,379
Bởi vì cũng có, đó là một cái gì đó
Tôi quên nói trước,

1448
01:12:20,379 --> 01:12:22,640
rằng đó là một cái gì đó
quan trọng về tìm kiếm nhị phân

1449
01:12:22,640 --> 01:12:24,182
là mảng của bạn đã được sắp xếp.

1450
01:12:24,182 --> 01:12:26,973
Bởi vì không có cách nào làm
này nếu họ giá trị chỉ là ngẫu nhiên.

1451
01:12:26,973 --> 01:12:29,190
Bạn không biết nếu một là
lớn hơn khác, phải không?

1452
01:12:29,190 --> 01:12:32,720
>> Vì vậy, bạn biết rằng tối đa của bạn và
phút của bạn đang ở đây, phải không?

1453
01:12:32,720 --> 01:12:35,590
Nếu bạn đang đi để được điều chỉnh
tối đa của bạn trong phút bạn và mid--

1454
01:12:35,590 --> 01:12:38,470
chúng ta hãy giả định của bạn
giữa giá trị là here-- đúng

1455
01:12:38,470 --> 01:12:43,910
bạn sẽ cơ bản
vòng lặp cho đến khi bạn tối thiểu là

1456
01:12:43,910 --> 01:12:47,510
về giống như tối đa của bạn, phải, hoặc
nếu tối đa của bạn không giống như min của bạn.

1457
01:12:47,510 --> 01:12:48,040
Bên phải?

1458
01:12:48,040 --> 01:12:51,340
Bởi vì khi điều đó xảy ra, bạn có biết rằng
cuối cùng bạn đã đánh giá trị như nhau.

1459
01:12:51,340 --> 01:12:59,135
Vì vậy, bạn muốn lặp cho đến phút của bạn
là nhỏ hơn hoặc bằng với: oops,

1460
01:12:59,135 --> 01:13:01,510
không ít hơn hoặc bằng,
cách khác around-- max là.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Điều đó có ý nghĩa?

1463
01:13:16,160 --> 01:13:18,810
Tôi lấy một vài cố gắng để có được quyền đó.

1464
01:13:18,810 --> 01:13:21,869
Nhưng vòng lặp cho đến giá trị tối đa của bạn
về cơ bản là hầu như ít

1465
01:13:21,869 --> 01:13:23,410
hơn hoặc bằng tối thiểu của bạn, phải không?

1466
01:13:23,410 --> 01:13:25,201
Đó là khi bạn biết
rằng bạn đã hội tụ.

1467
01:13:25,201 --> 01:13:29,290
Đung Khi sẽ tối đa của bạn
giá trị ít hơn mức tối thiểu?

1468
01:13:29,290 --> 01:13:31,040
Andi PENG: Nếu bạn giữ
điều chỉnh nó, mà

1469
01:13:31,040 --> 01:13:32,380
là những gì chúng ta đang đi
được làm trong này.

1470
01:13:32,380 --> 01:13:33,460
Điều đó có ý nghĩa?

1471
01:13:33,460 --> 01:13:35,750
Tối thiểu và tối đa chỉ
số nguyên mà chúng tôi có lẽ

1472
01:13:35,750 --> 01:13:39,260
sẽ muốn tạo ra để giữ
theo dõi các nơi mà chúng tôi đang tìm kiếm.

1473
01:13:39,260 --> 01:13:41,790
Vì mảng tồn tại
bất kể những gì chúng tôi đang làm.

1474
01:13:41,790 --> 01:13:45,030
Giống như, chúng tôi không thực sự thể chất
cắt bỏ các mảng, phải không?

1475
01:13:45,030 --> 01:13:47,261
Chúng tôi chỉ điều chỉnh
nơi mà chúng tôi đang tìm kiếm.

1476
01:13:47,261 --> 01:13:48,136
Điều đó có ý nghĩa?

1477
01:13:48,136 --> 01:13:48,472
>> Đung Yeah.

1478
01:13:48,472 --> 01:13:49,110
>> Andi PENG: OK.

1479
01:13:49,110 --> 01:13:57,090
Vì vậy, nếu đó là điều kiện cho vòng lặp của chúng tôi,
những gì chúng ta muốn bên trong của vòng lặp này?

1480
01:13:57,090 --> 01:13:58,700
Chúng ta sẽ phải muốn làm gì?

1481
01:13:58,700 --> 01:14:02,390
Vì vậy, ngay bây giờ, chúng tôi đã có
một tối đa và một phút, phải,

1482
01:14:02,390 --> 01:14:04,962
có thể tạo ra ở đây một nơi nào đó.

1483
01:14:04,962 --> 01:14:07,170
Chúng ta sẽ có thể muốn
để tìm một trung, phải không?

1484
01:14:07,170 --> 01:14:08,450
Làm thế nào chúng ta sẽ được
có thể tìm thấy giữa?

1485
01:14:08,450 --> 01:14:09,491
Các mathematical-- là gì

1486
01:14:09,491 --> 01:14:11,079
Đung Max cộng min chia cho 2.

1487
01:14:11,079 --> 01:14:11,870
Andi PENG: Chính xác.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Điều đó có ý nghĩa?

1490
01:14:21,620 --> 01:14:25,780
Và các bạn thấy lý do tại sao chúng tôi
không chỉ use-- do của việc làm này

1491
01:14:25,780 --> 01:14:27,850
thay vì chỉ cần làm n chia cho 2?

1492
01:14:27,850 --> 01:14:30,310
Đó là bởi vì n là một giá trị
đó là sẽ ở lại cùng.

1493
01:14:30,310 --> 01:14:30,979
Bên phải?

1494
01:14:30,979 --> 01:14:34,020
Nhưng khi chúng ta điều chỉnh tối thiểu của chúng tôi và
giá trị tối đa, chúng ta sẽ thay đổi.

1495
01:14:34,020 --> 01:14:36,040
Và kết quả là, giữa chúng tôi
là sẽ thay đổi quá.

1496
01:14:36,040 --> 01:14:37,873
Vì vậy, đó là lý do tại sao chúng tôi muốn
để làm điều này đúng ở đây.

1497
01:14:37,873 --> 01:14:38,510
ĐƯỢC.

1498
01:14:38,510 --> 01:14:41,600
>> Và sau đó, bây giờ mà
chúng tôi đã tìm thấy our-- yeah.

1499
01:14:41,600 --> 01:14:44,270
>> Đung Chỉ cần một question-- nhanh
khi bạn nói min và max,

1500
01:14:44,270 --> 01:14:46,410
Chúng ta giả định rằng
nó đã được sắp xếp?

1501
01:14:46,410 --> 01:14:48,400
>> Andi PENG: Vâng, đó thực sự là một
điều kiện tiên quyết cho một tìm kiếm nhị phân,

1502
01:14:48,400 --> 01:14:49,816
mà bạn phải biết nó được sắp xếp.

1503
01:14:49,816 --> 01:14:53,660
Đó là lý do tại sao sắp xếp, bạn viết trong của bạn
vấn đề thiết lập trước khi tìm kiếm nhị phân của bạn.

1504
01:14:53,660 --> 01:14:55,910
ĐƯỢC.

1505
01:14:55,910 --> 01:14:58,876
Vì vậy, bây giờ mà chúng ta biết nơi trung điểm của chúng tôi
được, những gì bạn muốn làm ở đây?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> Đung Chúng tôi muốn so sánh
rằng để một khác.

1508
01:15:04,319 --> 01:15:05,110
Andi PENG: Chính xác.

1509
01:15:05,110 --> 01:15:12,280
Vì vậy, bạn đang đi để so sánh
giữa giá trị, phải không?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
Và những gì mà không nói
chúng ta khi chúng ta so sánh?

1512
01:15:18,670 --> 01:15:22,226
Những gì chúng tôi muốn làm sau đó?

1513
01:15:22,226 --> 01:15:25,389
>> Đung Nếu giá trị lớn
hơn trung, chúng tôi muốn cắt nó đi.

1514
01:15:25,389 --> 01:15:26,180
Andi PENG: Chính xác.

1515
01:15:26,180 --> 01:15:33,940
Vì vậy, nếu giá trị lớn
hơn trung, chúng tôi

1516
01:15:33,940 --> 01:15:36,550
sẽ muốn thay đổi những
đạt cực đại và tối thiểu, phải không?

1517
01:15:36,550 --> 01:15:38,980
Những gì chúng tôi muốn thay đổi?

1518
01:15:38,980 --> 01:15:42,145
Vì vậy, nếu chúng ta biết giá trị là một nơi nào đó
ở đây, những gì bạn làm chúng ta phải thay đổi?

1519
01:15:42,145 --> 01:15:44,758
Chúng tôi muốn thay đổi của chúng tôi
tối thiểu là mid, phải không?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
Và sau đó khác, nếu nó ở trong này
một nửa, những gì chúng tôi muốn thay đổi?

1522
01:15:54,292 --> 01:15:55,306
>> Đung tối đa của bạn.

1523
01:15:55,306 --> 01:15:55,972
Andi PENG: Yeah.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
Và sau đó bạn chỉ cần đi
để giữ cho vòng lặp, phải không?

1526
01:16:04,680 --> 01:16:08,920
Bởi vì bây giờ, sau một lần lặp
thông qua, bạn đã có một tối đa ở đây.

1527
01:16:08,920 --> 01:16:10,760
Và sau đó bạn có thể tính toán lại một trung.

1528
01:16:10,760 --> 01:16:11,990
Và sau đó bạn có thể so sánh.

1529
01:16:11,990 --> 01:16:14,766
Và bạn sẽ tiếp tục đi
cho đến phút và đạt cực đại

1530
01:16:14,766 --> 01:16:15,890
trên cơ bản đã hội tụ.

1531
01:16:15,890 --> 01:16:17,890
Và đó là khi bạn biết rằng
bạn đã nhấn kết thúc của nó.

1532
01:16:17,890 --> 01:16:20,280
Và một trong hai bạn đã tìm thấy nó
hoặc bạn có không vào thời điểm đó.

1533
01:16:20,280 --> 01:16:23,170
>> Liệu điều này có ý nghĩa với tất cả mọi người?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
ĐƯỢC.

1536
01:16:26,770 --> 01:16:27,900
Điều này là khá quan trọng,
bởi vì bạn sẽ có

1537
01:16:27,900 --> 01:16:29,760
để viết này trong mã của bạn đêm nay.

1538
01:16:29,760 --> 01:16:32,660
Nhưng các bạn có một khá tốt
ý nghĩa của những gì bạn cần phải làm,

1539
01:16:32,660 --> 01:16:34,051
cái nào tốt.

1540
01:16:34,051 --> 01:16:34,550
ĐƯỢC.

1541
01:16:34,550 --> 01:16:38,840
Vì vậy, chúng tôi đã có khoảng bảy
phút còn lại phần.

1542
01:16:38,840 --> 01:16:43,170
Vì vậy, chúng ta sẽ nói về
pset này rằng chúng tôi sẽ làm.

1543
01:16:43,170 --> 01:16:46,410
Vì vậy, các pset được chia thành hai nửa.

1544
01:16:46,410 --> 01:16:50,230
Nửa đầu tiên liên quan
thực hiện một tìm thấy

1545
01:16:50,230 --> 01:16:54,210
trong đó bạn viết một tìm kiếm tuyến tính, một
tìm kiếm nhị phân, và một thuật toán sắp xếp.

1546
01:16:54,210 --> 01:16:56,690
>> Vì vậy, đây là lần đầu tiên
thời gian trong một pset nơi

1547
01:16:56,690 --> 01:17:00,050
chúng tôi sẽ đem lại cho các bạn những gì được gọi là
Mã phân phối, đó là mã

1548
01:17:00,050 --> 01:17:02,740
rằng chúng tôi đã sẵn bằng văn bản,
nhưng chỉ để lại một số mảnh off

1549
01:17:02,740 --> 01:17:04,635
cho bạn để hoàn thành văn bản.

1550
01:17:04,635 --> 01:17:07,510
Vì vậy các bạn, khi bạn nhìn vào điều này
mã, bạn có thể nhận được thực sự sợ hãi.

1551
01:17:07,510 --> 01:17:08,630
Nếu bạn chỉ thích, ahh, tôi
không biết đó là làm,

1552
01:17:08,630 --> 01:17:11,670
Tôi không biết, như thế, mà có vẻ
quá phức tạp, ahh, thư giãn.

1553
01:17:11,670 --> 01:17:12,170
Đó là OK.

1554
01:17:12,170 --> 01:17:12,930
Đọc spec.

1555
01:17:12,930 --> 01:17:16,920
Spec sẽ giải thích cho bạn biết chính xác
những gì tất cả các chương trình đang làm.

1556
01:17:16,920 --> 01:17:20,560
>> Ví dụ, generate.c là một chương trình
đó sẽ đến với pset của bạn.

1557
01:17:20,560 --> 01:17:24,060
Bạn không thực sự cần chạm vào nó, nhưng
bạn nên hiểu những gì nó làm.

1558
01:17:24,060 --> 01:17:28,550
Và generate.c, tất cả nó làm là
hoặc tạo ra các số ngẫu nhiên

1559
01:17:28,550 --> 01:17:32,400
hoặc bạn có thể cung cấp cho nó một hạt giống, giống như một
số chuẩn bị trước mà nó cần,

1560
01:17:32,400 --> 01:17:34,140
và nó tạo ra nhiều con số hơn.

1561
01:17:34,140 --> 01:17:37,170
Vì vậy, có một cách cụ thể để
thực hiện generate.c trong đó

1562
01:17:37,170 --> 01:17:42,760
bạn chỉ có thể thực hiện một loạt các con số
cho bạn để thử nghiệm các phương pháp khác của bạn trên.

1563
01:17:42,760 --> 01:17:45,900
>> Vì vậy, nếu bạn muốn, cho
Ví dụ, kiểm tra tìm bạn,

1564
01:17:45,900 --> 01:17:48,970
bạn sẽ muốn chạy generate.c,
tạo ra một loạt các con số,

1565
01:17:48,970 --> 01:17:50,880
và sau đó chạy chức năng giúp đỡ của bạn.

1566
01:17:50,880 --> 01:17:53,930
Chức năng giúp đỡ của bạn là nơi bạn
thực chất viết code.

1567
01:17:53,930 --> 01:17:59,330
Và suy nghĩ của những người giúp đỡ như một tập tin thư viện
bạn đang viết tìm được kêu gọi.

1568
01:17:59,330 --> 01:18:02,950
Và như vậy trong vòng helpers.c, bạn sẽ
làm tìm kiếm và phân loại.

1569
01:18:02,950 --> 01:18:06,500
>> Và sau đó bạn sẽ cơ bản
chỉ cần đặt chúng lại với nhau.

1570
01:18:06,500 --> 01:18:10,350
Spec sẽ cho bạn biết làm thế nào để
đặt trên các dòng lệnh.

1571
01:18:10,350 --> 01:18:14,880
Và bạn sẽ có thể kiểm tra hay
không sắp xếp và tìm kiếm của bạn đang làm việc.

1572
01:18:14,880 --> 01:18:15,870
Mát.

1573
01:18:15,870 --> 01:18:18,720
Có ai đã bắt đầu và
vấn đề gặp phải hoặc câu hỏi

1574
01:18:18,720 --> 01:18:20,520
họ có ngay bây giờ với điều này?

1575
01:18:20,520 --> 01:18:21,020
ĐƯỢC.

1576
01:18:21,020 --> 01:18:21,476
>> Đung đợi.

1577
01:18:21,476 --> 01:18:21,932
Tôi có một câu hỏi.

1578
01:18:21,932 --> 01:18:22,844
>> Andi PENG: Yeah.

1579
01:18:22,844 --> 01:18:28,390
>> Đung Vì vậy, tôi bắt đầu làm
tìm kiếm tuyến tính trong helpers.c

1580
01:18:28,390 --> 01:18:29,670
và nó đã không thực sự làm việc.

1581
01:18:29,670 --> 01:18:34,590
Nhưng sau đó, tôi phát hiện ra chúng ta chỉ
phải xóa nó và làm tìm kiếm nhị phân.

1582
01:18:34,590 --> 01:18:36,991
Vì vậy, không vấn đề gì nếu nó không hoạt động?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> Andi PENG: Câu trả lời ngắn gọn là không.

1585
01:18:41,510 --> 01:18:42,642
Nhưng kể từ khi chúng tôi not--

1586
01:18:42,642 --> 01:18:44,350
Đung Nhưng không có ai của
thực sự kiểm tra.

1587
01:18:44,350 --> 01:18:46,058
Andi PENG: Chúng tôi không bao giờ
sẽ thấy điều đó.

1588
01:18:46,058 --> 01:18:49,590
Nhưng có thể bạn muốn làm
chắc chắn tìm kiếm của bạn đang làm việc.

1589
01:18:49,590 --> 01:18:51,700
Bởi vì nếu tuyến tính của bạn
tìm kiếm không hoạt động,

1590
01:18:51,700 --> 01:18:54,410
sau đó rất có thể là nhị phân của bạn
tìm kiếm không phải là đi để làm việc tốt.

1591
01:18:54,410 --> 01:18:56,646
Bởi vì bạn có tương tự
logic trong cả hai.

1592
01:18:56,646 --> 01:18:58,020
Và không có, nó không thực sự quan trọng.

1593
01:18:58,020 --> 01:19:01,300
Vì vậy, những người duy nhất bạn sẽ biến
trong là sắp xếp và tìm kiếm nhị phân.

1594
01:19:01,300 --> 01:19:02,490
Yeah.

1595
01:19:02,490 --> 01:19:06,610
>> Và cũng có thể, rất nhiều trẻ em đã
cố gắng để biên dịch helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Bạn không thực sự cho phép
để làm điều đó, bởi vì helpers.c

1597
01:19:09,550 --> 01:19:11,200
không có chức năng chính.

1598
01:19:11,200 --> 01:19:13,550
Và do đó, bạn chỉ nên
được thực sự biên dịch

1599
01:19:13,550 --> 01:19:18,670
tạo ra và tìm thấy, vì thấy cuộc gọi
helpers.c và các chức năng bên trong nó.

1600
01:19:18,670 --> 01:19:20,790
Vì vậy, mà làm cho gỡ lỗi
một cơn đau ở mông.

1601
01:19:20,790 --> 01:19:22,422
Nhưng đó là những gì chúng ta phải làm.

1602
01:19:22,422 --> 01:19:23,880
Đung Bạn chỉ cần thực hiện tất cả, phải không?

1603
01:19:23,880 --> 01:19:27,290
Andi PENG: Bạn chỉ có thể
làm cho tất cả là tốt, yeah.

1604
01:19:27,290 --> 01:19:28,060
ĐƯỢC.

1605
01:19:28,060 --> 01:19:32,570
Vì vậy, đó là nó về những gì
các pset là yêu cầu tất cả các bạn phải làm.

1606
01:19:32,570 --> 01:19:35,160
Nếu bạn có bất kỳ câu hỏi, cảm thấy
hỏi tôi sau khi phần.

1607
01:19:35,160 --> 01:19:37,580
Tôi sẽ ở đây, như thế, 20 phút.

1608
01:19:37,580 --> 01:19:40,500
>> Và yeah, các pset của
thực sự không phải là xấu.

1609
01:19:40,500 --> 01:19:41,680
Các bạn nên có OK.

1610
01:19:41,680 --> 01:19:43,250
Những điều này, chỉ cần làm theo hướng dẫn.

1611
01:19:43,250 --> 01:19:47,840
Loại có một cảm giác, một cách hợp lý, những gì
nên xảy ra và bạn sẽ bị phạt.

1612
01:19:47,840 --> 01:19:48,690
Đừng quá sợ hãi.

1613
01:19:48,690 --> 01:19:50,220
Có rất nhiều mã
đã viết ở đó.

1614
01:19:50,220 --> 01:19:53,011
Đừng quá sợ hãi nếu bạn làm không
hiểu những gì tất cả điều đó có nghĩa.

1615
01:19:53,011 --> 01:19:54,749
Nếu đó là một rất nhiều, nó hoàn toàn tốt.

1616
01:19:54,749 --> 01:19:55,790
Và đến giờ làm việc.

1617
01:19:55,790 --> 01:19:57,520
Chúng tôi sẽ giúp bạn có một cái nhìn.

1618
01:19:57,520 --> 01:20:00,810
>> Đung Với thêm
chức năng, chúng tôi nhìn những người lên?

1619
01:20:00,810 --> 01:20:03,417
>> Andi PENG: Yeah, những người ở trong mã.

1620
01:20:03,417 --> 01:20:05,750
Trong các trò chơi của 15, một nửa
nó đã được viết cho bạn.

1621
01:20:05,750 --> 01:20:09,310
Vì vậy, những chức năng này
đã có trong mã.

1622
01:20:09,310 --> 01:20:12,020
Yep.

1623
01:20:12,020 --> 01:20:12,520
Được rồi.

1624
01:20:12,520 --> 01:20:14,000
Vâng, tốt nhất của may mắn.

1625
01:20:14,000 --> 01:20:15,180
Đó là một ngày kinh tởm.

1626
01:20:15,180 --> 01:20:19,370
Vì vậy, hy vọng các bạn không cảm thấy quá
Ơû bên trong và mã hóa.

1627
01:20:19,370 --> 01:20:22,133