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

2
00:00:11,100 --> 00:00:12,300
>> SPEAKER 1: Hey tất cả mọi người!

3
00:00:12,300 --> 00:00:13,890
Chào mừng trở lại phần.

4
00:00:13,890 --> 00:00:17,480
Vì vậy, vui mừng khi thấy rất nhiều bạn cả ở đây,
và tất cả những ai đang xem trực tuyến.

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

6
00:00:18,760 --> 00:00:20,920
Vì vậy, như thường lệ chào đón trở lại.

7
00:00:20,920 --> 00:00:24,360
Tôi hy vọng rằng tất cả các bạn đã có một đáng yêu
cuối tuần, đầy đủ nghỉ ngơi, thư giãn.

8
00:00:24,360 --> 00:00:26,026
Đó là đẹp ra ngày hôm qua.

9
00:00:26,026 --> 00:00:27,525
Vì vậy, tôi hy vọng bạn thích hoạt động ngoài trời.

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

11
00:00:28,840 --> 00:00:30,610
>> Vì vậy, đầu tiên một vài thông báo.

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

13
00:00:31,920 --> 00:00:32,700
Chấm điểm.

14
00:00:32,700 --> 00:00:37,350
Vì vậy, hầu hết các bạn nên đã nhận một
gửi email từ tôi về Pset Scratch của bạn,

15
00:00:37,350 --> 00:00:39,920
cũng như chấm điểm cho Pset 1.

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

17
00:00:41,000 --> 00:00:42,220
Vì vậy, chỉ cần một vài điều.

18
00:00:42,220 --> 00:00:45,150
Hãy chắc chắn để sử dụng check50 trong style50.

19
00:00:45,150 --> 00:00:47,250
Đây có nghĩa là để được
nguồn lực cho các bạn,

20
00:00:47,250 --> 00:00:50,660
để đảm bảo rằng bạn đang nhận được
càng nhiều điểm như bạn có thể

21
00:00:50,660 --> 00:00:52,390
không cần thiết mà không mất chúng.

22
00:00:52,390 --> 00:00:54,407
Vì vậy, những thứ như phong cách
là rất quan trọng.

23
00:00:54,407 --> 00:00:55,740
Chúng tôi sẽ cất cánh cho nó.

24
00:00:55,740 --> 00:00:58,115
Một số bạn có thể đã
nhận thấy rằng từ Pset của bạn.

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

26
00:00:58,920 --> 00:01:01,450
Và check50 chỉ là
cách thực sự dễ dàng để đảm bảo

27
00:01:01,450 --> 00:01:05,050
rằng chúng tôi đang thực sự trở về những gì
cần phải được trả lại cho người sử dụng,

28
00:01:05,050 --> 00:01:06,690
và rằng tất cả mọi thứ đang làm việc đúng cách.

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

30
00:01:08,690 --> 00:01:12,040
>> Trên lưu ý thứ hai, hãy chắc chắn bạn
tải lên những thứ về đúng thư mục.

31
00:01:12,040 --> 00:01:14,470
Nó làm cho cuộc sống của tôi chỉ là một
một chút khó khăn hơn

32
00:01:14,470 --> 00:01:18,836
nếu bạn tải lên Pset 2 vào Pset 1
bởi vì khi tôi tải về mọi thứ,

33
00:01:18,836 --> 00:01:20,085
họ không tải một cách chính xác.

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

35
00:01:21,690 --> 00:01:24,560
Và tôi biết đó là một chút rung rinh
trong một hệ thống để có được sử dụng để,

36
00:01:24,560 --> 00:01:26,950
nhưng chỉ được siêu
cẩn thận, nếu chỉ cho tôi,

37
00:01:26,950 --> 00:01:30,080
do đó khi bạn đang nhận được email
tại như 02:00 và tôi chấm điểm.

38
00:01:30,080 --> 00:01:33,710
Nếu không gây ra tôi phải nhìn
tất cả các xung quanh cho Pset của bạn.

39
00:01:33,710 --> 00:01:34,440
Cool.

40
00:01:34,440 --> 00:01:37,270
>> Tôi biết đó là sớm, nhưng tôi
hoàn toàn bị lấy mất cảnh giác

41
00:01:37,270 --> 00:01:40,800
bằng một bài luận đó là do thứ sáu này, mà
giáo sư của tôi đã được chỉ thích, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Hãy nhớ rằng, bạn có một
bài luận do vào thứ Sáu.

43
00:01:42,550 --> 00:01:45,780
Vì vậy, tôi biết không ai thích
để suy nghĩ về midterms,

44
00:01:45,780 --> 00:01:50,620
nhưng bài kiểm tra đầu tiên của bạn là vào ngày 15 tháng 10,
Tháng Mười đó được bắt đầu trong tuần này.

45
00:01:50,620 --> 00:01:53,290
Vì vậy, nó có thể là sớm hơn
hơn bạn mong đợi là tất cả.

46
00:01:53,290 --> 00:01:57,510
Vì vậy, bạn không ném mất cảnh giác khi
Tôi đề cập đến phần vào tuần tới mà oh,

47
00:01:57,510 --> 00:02:00,560
đố tuần tiếp theo của bạn, tôi nghĩ
Tôi muốn cung cấp cho bạn một chút hơn

48
00:02:00,560 --> 00:02:01,500
của một người đứng đầu ngay bây giờ.

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

50
00:02:02,970 --> 00:02:04,660
>> Vì vậy, vấn đề của bạn được thiết lập, số ba.

51
00:02:04,660 --> 00:02:07,070
Làm thế nào mọi người đã đọc
spec ra tò mò?

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

53
00:02:08,560 --> 00:02:09,199
OK.

54
00:02:09,199 --> 00:02:10,229
Chúng tôi có một cặp vợ chồng.

55
00:02:10,229 --> 00:02:12,320
Loại giảm từ cuối cùng
tuần nhưng đó là OK.

56
00:02:12,320 --> 00:02:13,650
Tôi biết nó đã được ra khỏi đẹp.

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

58
00:02:15,120 --> 00:02:16,660
Vì vậy, Break Out.

59
00:02:16,660 --> 00:02:21,010
Chắc chắn sau khi bạn được thực hiện
ngày nay đọc spec của bạn ít nhất

60
00:02:21,010 --> 00:02:25,240
thử như tải
đang phân phối và chạy

61
00:02:25,240 --> 00:02:27,430
như ban đầu đầu tiên
điều mà họ yêu cầu bạn.

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

63
00:02:28,681 --> 00:02:32,590
Bởi vì chúng ta đang sử dụng
đang phân phối và một thư viện

64
00:02:32,590 --> 00:02:36,790
mà chúng tôi đã chỉ được using-- --It chỉ
lần thứ hai chúng tôi đã thực hiện Pset này,

65
00:02:36,790 --> 00:02:38,650
những điều điên rồ có thể xảy ra
với thiết bị của bạn,

66
00:02:38,650 --> 00:02:41,370
và bạn muốn để thấy rằng
ra ngay bây giờ so với sau này.

67
00:02:41,370 --> 00:02:45,570
>> Bởi vì nếu đó là đêm thứ năm hoặc nó
Tối thứ Tư và vì một lý do

68
00:02:45,570 --> 00:02:48,912
thiết bị của bạn chỉ cần không
muốn chạy với thư viện

69
00:02:48,912 --> 00:02:50,620
hoặc với phân phối
mã, mà phương tiện

70
00:02:50,620 --> 00:02:52,309
bạn thậm chí không thể bắt đầu thực hiện việc mã hóa.

71
00:02:52,309 --> 00:02:54,100
Bởi vì bạn không thể kiểm tra
để xem nếu nó hoạt động.

72
00:02:54,100 --> 00:02:55,975
Không gonna của bạn có thể
để xem nếu nó biên dịch.

73
00:02:55,975 --> 00:03:00,500
Bạn muốn chăm sóc những đầu
tuần, khi bạn vẫn có thể gửi email cho tôi

74
00:03:00,500 --> 00:03:03,100
hoặc một trong các TF khác,
và chúng ta có thể có được những cố định.

75
00:03:03,100 --> 00:03:05,410
Bởi vì những người đang có vấn đề
mà sẽ ngăn chặn bạn

76
00:03:05,410 --> 00:03:07,120
từ thực hiện bất kỳ tiến bộ thực sự.

77
00:03:07,120 --> 00:03:10,055
Nó không giống như một lỗi, mà
bạn có thể chỉ cần loại bỏ qua.

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

79
00:03:10,712 --> 00:03:13,420
Nếu bạn đang gặp vấn đề với bạn
thiết bị hoặc mã phân phối,

80
00:03:13,420 --> 00:03:16,211
bạn thực sự muốn nhận được rằng thực hiện
quan tâm của sớm hơn là sau đó.

81
00:03:16,211 --> 00:03:20,410
Vì vậy, ngay cả khi bạn không gonna thực
bắt đầu viết mã, tải về phân phối

82
00:03:20,410 --> 00:03:24,040
mã, đọc spec, hãy chắc chắn
tất cả mọi thứ đang làm việc ở đó.

83
00:03:24,040 --> 00:03:25,134
OK?

84
00:03:25,134 --> 00:03:27,675
Nếu bạn chỉ có thể làm điều đó, tôi
hứa hẹn cuộc sống của bạn sẽ được dễ dàng hơn.

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

86
00:03:28,800 --> 00:03:31,410
Và như vậy bạn có thể sẽ
để làm điều đó ngay bây giờ phải không?

87
00:03:31,410 --> 00:03:32,100
OK.

88
00:03:32,100 --> 00:03:33,950
Vì vậy, bất kỳ câu hỏi đó?

89
00:03:33,950 --> 00:03:35,850
Bất kỳ điều logistic?

90
00:03:35,850 --> 00:03:36,910
Tất cả mọi người là tốt?

91
00:03:36,910 --> 00:03:38,270
OK.

92
00:03:38,270 --> 00:03:41,700
>> Disclaimer đối với những người
bạn trong phòng và trực tuyến.

93
00:03:41,700 --> 00:03:45,437
Tôi sẽ phải cố gắng để chuyển đổi
giữa PowerPoint trong thiết bị

94
00:03:45,437 --> 00:03:47,270
bởi vì chúng ta sẽ
được làm một số mã hóa

95
00:03:47,270 --> 00:03:53,630
hiện nay do nhu cầu phổ biến của vô danh
đề nghị thăm dò ý kiến ​​tôi đã gửi ra tuần trước.

96
00:03:53,630 --> 00:03:55,480
Vì vậy, chúng tôi sẽ làm một số mã hóa.

97
00:03:55,480 --> 00:03:57,800
Vì vậy, nếu các bạn cũng muốn
cháy lên thiết bị của bạn,

98
00:03:57,800 --> 00:04:02,910
và bạn nên đã nhận được một email
từ tôi, với một tập tin mẫu.

99
00:04:02,910 --> 00:04:04,310
Xin vui lòng làm điều đó.

100
00:04:04,310 --> 00:04:07,340
>> Vì vậy, chúng ta sẽ nói về
GDB, mà là một trình gỡ lỗi.

101
00:04:07,340 --> 00:04:09,970
Nó sẽ giúp bạn
loại tìm ra nơi

102
00:04:09,970 --> 00:04:11,860
mọi thứ đang đi sai trong mã của bạn.

103
00:04:11,860 --> 00:04:15,370
Nó thực sự chỉ là một cách để bạn có thể bước
thông qua mã của bạn như nó đang xảy ra,

104
00:04:15,370 --> 00:04:19,100
và có thể in ra các biến
hoặc xem những gì đang thực sự xảy ra

105
00:04:19,100 --> 00:04:22,980
dưới mui xe các câu chương trình của bạn
chỉ cần chạy, nó giống như đứt gãy,

106
00:04:22,980 --> 00:04:25,030
và bạn giống như, không có ý tưởng
những gì vừa xảy ra ở đây.

107
00:04:25,030 --> 00:04:26,730
Tôi không biết những dòng nó không thành công tại.

108
00:04:26,730 --> 00:04:29,040
Tôi không biết nơi mà nó đã đi sai.

109
00:04:29,040 --> 00:04:31,280
Vì vậy, GDB sẽ giúp bạn với điều đó.

110
00:04:31,280 --> 00:04:35,240
Ngoài ra, nếu bạn quyết định
tiếp tục có, và mất 61,

111
00:04:35,240 --> 00:04:38,430
nó sẽ thực sự, thực sự là của bạn
người bạn tốt nhất, vì tôi có thể cho bạn biết

112
00:04:38,430 --> 00:04:40,840
bởi vì tôi đang đi qua lớp đó.

113
00:04:40,840 --> 00:04:43,620
>> Chúng ta sẽ nhìn vào nhị phân
tìm kiếm, nếu các bạn nhớ

114
00:04:43,620 --> 00:04:47,540
các ví dụ tuyệt vời cuốn sách điện thoại
cảnh tượng từ lớp học.

115
00:04:47,540 --> 00:04:50,620
Chúng tôi sẽ thực hiện điều đó, và
đi bộ qua đó hơn một chút,

116
00:04:50,620 --> 00:04:54,650
và sau đó chúng ta sẽ thông qua bốn
các loại khác nhau, đó là bong bóng,

117
00:04:54,650 --> 00:04:56,285
Lựa chọn, chèn, và Merge.

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

119
00:04:57,830 --> 00:04:58,330
Cool.

120
00:04:58,330 --> 00:05:00,390
Vì vậy, GDB như tôi đã đề cập, là một trình gỡ lỗi.

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

122
00:05:01,400 --> 00:05:09,370
Và đây là những loại lớn
điều, các chức năng lớn hoặc lệnh

123
00:05:09,370 --> 00:05:13,240
mà bạn sử dụng trong GDB, và tôi sẽ đi bộ
bạn thông qua một bản demo của nó trong một giây.

124
00:05:13,240 --> 00:05:15,360
>> Vì vậy, đây không phải chỉ là
sẽ ở lại trừu tượng.

125
00:05:15,360 --> 00:05:18,000
Tôi sẽ cố gắng và làm cho nó như bê tông
nhất có thể cho các bạn.

126
00:05:18,000 --> 00:05:19,870
Vì vậy, phá vỡ.

127
00:05:19,870 --> 00:05:22,200
Nó hoặc là sẽ được nghỉ
như, một số số, mà

128
00:05:22,200 --> 00:05:26,900
đại diện cho một dòng trong chương trình của bạn,
hoặc bạn có thể đặt tên cho một chức năng.

129
00:05:26,900 --> 00:05:30,150
Vì vậy, nếu bạn nói phá vỡ chính,
nó sẽ dừng lại ở chính,

130
00:05:30,150 --> 00:05:32,400
và cho phép bạn đi bộ qua chức năng đó.

131
00:05:32,400 --> 00:05:36,350
>> Tương tự như vậy, nếu bạn có một số bên ngoài
hoạt động như trao đổi hoặc Cube,

132
00:05:36,350 --> 00:05:38,450
mà chúng ta nhìn vào tuần trước.

133
00:05:38,450 --> 00:05:41,780
Nếu bạn nói phá vỡ một trong những,
bất cứ khi nào chương trình của bạn đạt rằng,

134
00:05:41,780 --> 00:05:44,290
nó sẽ chờ đợi cho bạn để
nói với nó làm gì.

135
00:05:44,290 --> 00:05:47,860
Trước khi nó sẽ chỉ thực hiện, do đó bạn
có thể thực sự bước vào bên trong chức năng

136
00:05:47,860 --> 00:05:49,020
và xem những gì đang xảy ra.

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

138
00:05:50,370 --> 00:05:53,515
Vì vậy, tiếp theo, chỉ cần bỏ qua trên
dòng tiếp theo, đi qua các chức năng.

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

140
00:05:54,730 --> 00:05:55,560
Bước.

141
00:05:55,560 --> 00:05:56,810
Đây là tất cả trừu tượng ít.

142
00:05:56,810 --> 00:06:00,530
Vì vậy, tôi chỉ cần đi để chạy qua chúng,
nhưng bạn sẽ thấy chúng được sử dụng trong một giây.

143
00:06:00,530 --> 00:06:01,810
>> Bước vào một chức năng.

144
00:06:01,810 --> 00:06:04,170
Vì vậy, như tôi đã nói,
như với Swap, nó sẽ

145
00:06:04,170 --> 00:06:07,110
cho phép bạn thực sự là nếu bạn
như thể chất bước vào bên trong,

146
00:06:07,110 --> 00:06:10,990
bạn có thể gây rối với các biến, in ấn
ra những gì họ đang có, xem những gì đang xảy ra.

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

148
00:06:12,140 --> 00:06:14,830
Danh sách theo nghĩa đen sẽ chỉ cần in
ra các mã xung quanh.

149
00:06:14,830 --> 00:06:17,570
Vì vậy, nếu bạn loại quên
nơi bạn đang ở trong chương trình của bạn,

150
00:06:17,570 --> 00:06:19,880
hoặc bạn đang tự hỏi
những gì đang xảy ra xung quanh nó,

151
00:06:19,880 --> 00:06:23,790
điều này sẽ chỉ in ra một phân khúc
thích của năm hay sáu đường xung quanh nó.

152
00:06:23,790 --> 00:06:26,080
Vì vậy, bạn có thể định hướng
về nơi bạn đang ở.

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

154
00:06:27,230 --> 00:06:28,650
>> In một số biến.

155
00:06:28,650 --> 00:06:34,590
Vì vậy, nếu bạn có quan trọng như
trong Caesar, rằng chúng tôi sẽ xem xét.

156
00:06:34,590 --> 00:06:36,220
Bạn có thể nói In chính tại bất kỳ điểm nào.

157
00:06:36,220 --> 00:06:40,070
Nó sẽ cho bạn biết những gì giá trị là như vậy
đó, có thể ở đâu đó trên đường đi,

158
00:06:40,070 --> 00:06:42,070
bạn ghi đè lên chìa khóa của bạn.

159
00:06:42,070 --> 00:06:45,495
Bạn thực sự có thể nói rằng vì
bạn thực sự có thể quan sát giá trị đó.

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

161
00:06:46,500 --> 00:06:48,780
>> Trong người dân địa phương, chỉ cần in
ra biến địa phương của bạn.

162
00:06:48,780 --> 00:06:53,120
Vì vậy, bất cứ lúc nào bạn đang trong một vòng lặp,
và bạn chỉ muốn xem như, oh.

163
00:06:53,120 --> 00:06:54,270
Tôi của tôi là gì?

164
00:06:54,270 --> 00:06:57,020
Giá trị quan trọng này là gì
mà tôi khởi tạo ở đây?

165
00:06:57,020 --> 00:06:58,537
Được thông báo vào thời điểm này là gì?

166
00:06:58,537 --> 00:07:00,370
Nó sẽ chỉ in tất cả
của những người, do đó bạn

167
00:07:00,370 --> 00:07:04,330
không phải cá nhân
nói, In I. In tin nhắn.

168
00:07:04,330 --> 00:07:04,970
In Key.

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

170
00:07:06,190 --> 00:07:07,700
Và sau đó hiển thị.

171
00:07:07,700 --> 00:07:10,370
Có gì đó không được như bạn
bước qua chương trình,

172
00:07:10,370 --> 00:07:13,980
nó sẽ chỉ cần đảm bảo rằng đó là
hiển thị một số biến nhất định

173
00:07:13,980 --> 00:07:14,780
tại mỗi điểm.

174
00:07:14,780 --> 00:07:17,160
Vì vậy mà bạn also-- --it là
loại một phím tắt nơi

175
00:07:17,160 --> 00:07:19,530
bạn không có để tiếp tục đi như thế, oh.

176
00:07:19,530 --> 00:07:23,150
In Key hoặc In I. Nó chỉ
sẽ tự động làm điều đó cho bạn.

177
00:07:23,150 --> 00:07:25,959
>> Vì vậy, với điều đó, chúng ta sẽ
để xem cách này đi.

178
00:07:25,959 --> 00:07:28,000
Tôi sẽ cố gắng và chuyển đổi
qua thiết bị của tôi.

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

180
00:07:30,200 --> 00:07:31,271
Xem nếu tôi có thể làm điều này.

181
00:07:31,271 --> 00:07:31,770
Tất cả.

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

183
00:07:40,970 --> 00:07:42,370
Chúng tôi chỉ cần đi để nhân bản nó.

184
00:07:42,370 --> 00:07:44,530
Không có gì là điên
trên máy tính xách tay của tôi anyways.

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

186
00:07:49,600 --> 00:07:50,100
OK.

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

188
00:07:57,030 --> 00:08:01,054
Điều này cần phải được thế này.

189
00:08:01,054 --> 00:08:01,795
Đó là quá nhỏ bé.

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

191
00:08:03,730 --> 00:08:05,120
Hãy xem nếu chúng ta có thể làm điều này.

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

193
00:08:09,970 --> 00:08:10,940
>> OK.

194
00:08:10,940 --> 00:08:15,305
Alice rõ ràng là đang gặp khó khăn
đây chỉ là một chút,

195
00:08:15,305 --> 00:08:17,995
nhưng chúng tôi sẽ nhận được nó trong một Momento.

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

197
00:08:20,810 --> 00:08:22,020
OK.

198
00:08:22,020 --> 00:08:25,900
Chúng tôi chỉ là đi để tăng này.

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

200
00:08:28,770 --> 00:08:29,380
OK.

201
00:08:29,380 --> 00:08:31,679
Tất cả mọi người có thể loại thấy rằng?

202
00:08:31,679 --> 00:08:32,470
Có lẽ một chút?

203
00:08:32,470 --> 00:08:33,594
Tôi biết đó là một chút nhỏ.

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

205
00:08:34,570 --> 00:08:37,530
Bạn có thể không khá ra
làm thế nào để làm cho lớn hơn này.

206
00:08:37,530 --> 00:08:38,350
Nếu có ai biết.

207
00:08:38,350 --> 00:08:40,309
Có ai biết làm thế nào để làm cho nó lớn hơn?

208
00:08:40,309 --> 00:08:40,932
OK.

209
00:08:40,932 --> 00:08:42,140
Chúng tôi sẽ để cuộn với nó.

210
00:08:42,140 --> 00:08:45,801
Không quan trọng dù sao bởi vì nó chỉ
đó là mã mà các bạn nên

211
00:08:45,801 --> 00:08:46,300
có.

212
00:08:46,300 --> 00:08:48,310
>> Điều quan trọng hơn
là thiết bị đầu cuối ở đây.

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

214
00:08:52,840 --> 00:08:58,690
Và chúng tôi có ở đây Tại sao nó là quá nhỏ?

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

216
00:09:02,325 --> 00:09:02,825
Cài đặt.

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

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

219
00:09:08,420 --> 00:09:09,500
Đúng Ike.

220
00:09:09,500 --> 00:09:10,880
Làm thế nào đây?

221
00:09:10,880 --> 00:09:11,770
Ra khỏi đó.

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

223
00:09:19,370 --> 00:09:21,810
Là tốt hơn cho tất cả mọi người?

224
00:09:21,810 --> 00:09:22,525
OK ,.

225
00:09:22,525 --> 00:09:23,025
Cool.

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

227
00:09:25,830 --> 00:09:28,220
>> Bạn biết khi bạn đang ở trong một CS
khó khăn kỹ thuật lớp

228
00:09:28,220 --> 00:09:32,971
là loại một phần của the--
Vì vậy, chúng ta cần xóa này.

229
00:09:32,971 --> 00:09:33,470
OK.

230
00:09:33,470 --> 00:09:38,060
Vì vậy, ngay tại đây trong phần,
mà chúng tôi có ở đây.

231
00:09:38,060 --> 00:09:40,830
Caesar là một tập tin thực thi.

232
00:09:40,830 --> 00:09:41,800
Vì vậy, tôi đã làm cho nó.

233
00:09:41,800 --> 00:09:46,370
Vì vậy, có một điều nhận ra với GDB là
nó chỉ hoạt động trên các tập tin thực thi.

234
00:09:46,370 --> 00:09:48,040
Vì vậy, bạn không thể chạy nó trên một dotsy.

235
00:09:48,040 --> 00:09:50,532
Bạn phải thực sự làm
chắc chắn rằng mã của bạn biên dịch,

236
00:09:50,532 --> 00:09:51,865
và rằng nó thực sự có thể được chạy.

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

238
00:09:52,970 --> 00:09:56,186
>> Vì vậy, hãy chắc chắn rằng nếu nó không
biên dịch, làm cho nó biên dịch,

239
00:09:56,186 --> 00:09:57,810
để bạn có thể loại chạy qua nó.

240
00:09:57,810 --> 00:10:04,590
Vì vậy, để bắt đầu GDB, tất cả các bạn làm,
Gloria loại GDB, và sau đó chỉ

241
00:10:04,590 --> 00:10:06,250
tập tin mà bạn muốn.

242
00:10:06,250 --> 00:10:08,240
Tôi luôn luôn đánh sai Caesar.

243
00:10:08,240 --> 00:10:11,730
Nhưng bạn muốn chắc chắn
vì nó là một thực thi,

244
00:10:11,730 --> 00:10:14,210
ti chấm đèn flash để
có nghĩa là bạn đang đi

245
00:10:14,210 --> 00:10:19,240
để chạy CSI bạn sẽ thực hiện
tập tin này hoặc với trình gỡ rối.

246
00:10:19,240 --> 00:10:19,910
OK.

247
00:10:19,910 --> 00:10:22,885
Vì vậy, bạn làm điều đó, bạn sẽ có được
loại này vô nghĩa.

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

249
00:10:24,250 --> 00:10:25,750
Nó chỉ là tất cả mọi thứ về gỡ rối.

250
00:10:25,750 --> 00:10:28,200
Bạn không thực sự phải
lo lắng về nó ngay bây giờ.

251
00:10:28,200 --> 00:10:31,460
Và như bạn thấy, chúng tôi có điều này
dấu ngoặc mở, GDP, dấu ngoặc đóng,

252
00:10:31,460 --> 00:10:34,690
và chỉ cần loại trông giống như
dòng lệnh của chúng tôi, phải không?

253
00:10:34,690 --> 00:10:37,010
>> Vì vậy, những gì chúng tôi muốn do--
--So, Điều đầu tiên

254
00:10:37,010 --> 00:10:39,570
là chúng tôi muốn chọn
một nơi để phá vỡ nó.

255
00:10:39,570 --> 00:10:42,332
Vì vậy, có một lỗi
Caesar trong chương trình này

256
00:10:42,332 --> 00:10:44,290
mà tôi giới thiệu, đó là
chúng ta sẽ tìm hiểu.

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

258
00:10:45,330 --> 00:10:56,350
Điều gì nó là nó có đầu vào
Barfoo trong tất cả các mũ, và vì một lý do

259
00:10:56,350 --> 00:11:01,950
nó không thay đổi A. Nó chỉ là lá
nó một mình, có phải là tất cả mọi thứ khác chính xác,

260
00:11:01,950 --> 00:11:03,980
nhưng bức thư thứ hai
A vẫn không thay đổi.

261
00:11:03,980 --> 00:11:07,120
Vì vậy, chúng tôi sẽ cố gắng và
tìm ra lý do tại sao đó là.

262
00:11:07,120 --> 00:11:10,440
Vì vậy, điều đầu tiên bạn thường
muốn làm bất cứ khi nào bạn bắt đầu vào GDB

263
00:11:10,440 --> 00:11:12,010
là tìm ra nơi để phá vỡ nó.

264
00:11:12,010 --> 00:11:14,956
>> Vì vậy, Caesar là một chương trình khá ngắn.

265
00:11:14,956 --> 00:11:16,330
Chúng tôi chỉ có một chức năng, phải không?

266
00:11:16,330 --> 00:11:18,520
Chức năng của chúng tôi trong Caesar là gì?

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

268
00:11:19,590 --> 00:11:24,350
Chỉ có một chức năng, chính quyền?

269
00:11:24,350 --> 00:11:26,490
Chính là một chức năng
cho tất cả các chương trình của bạn.

270
00:11:26,490 --> 00:11:29,230
Nếu bạn không có chính, tôi có thể
có một chút lo lắng ngay bây giờ,

271
00:11:29,230 --> 00:11:31,000
nhưng tôi hy vọng tất cả các bạn đã có chính trong đó.

272
00:11:31,000 --> 00:11:34,150
Vì vậy, những gì chúng tôi có thể làm chúng ta là có thể
chỉ phá vỡ chính, chỉ cần như thế.

273
00:11:34,150 --> 00:11:35,190
Vì vậy, nó nói, OK.

274
00:11:35,190 --> 00:11:37,430
Chúng tôi thiết lập một breakpoint của chúng tôi ở đó.

275
00:11:37,430 --> 00:11:42,870
>> Vì vậy, bây giờ điều cần nhớ là Caesar
mất một đối số dòng lệnh bên phải

276
00:11:42,870 --> 00:11:45,150
và chúng tôi đã không làm điều đó bất cứ nơi nào được nêu ra.

277
00:11:45,150 --> 00:11:47,560
Vì vậy, những gì bạn làm là khi
bạn thực sự đi để chạy

278
00:11:47,560 --> 00:11:51,540
các chương trình, bất kỳ chương trình mà bạn
chạy trong GDB cần dòng lệnh

279
00:11:51,540 --> 00:11:55,010
đối số, bạn sẽ đầu vào
khi bạn lần đầu tiên bắt đầu chạy nó.

280
00:11:55,010 --> 00:11:59,280
Vì vậy, trong trường hợp này, chúng tôi làm
Chạy với khóa ba.

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

282
00:12:00,770 --> 00:12:02,040
Và nó sẽ thực sự bắt đầu.

283
00:12:02,040 --> 00:12:08,480
>> Vì vậy, nếu bạn thấy ở đây, chúng tôi có
Nếu RC là không bằng 2.

284
00:12:08,480 --> 00:12:12,210
Vì vậy, nếu các bạn có tất cả
tập tin đó mà tôi gửi lên

285
00:12:12,210 --> 00:12:15,100
bạn sẽ thấy rằng đó là giống như
Dòng đầu tiên chức năng chính của chúng tôi, phải không?

286
00:12:15,100 --> 00:12:17,890
Nó kiểm tra để xem nếu chúng ta có
số lượng chính xác của các đối số.

287
00:12:17,890 --> 00:12:20,620
Vì vậy, nếu bạn đang tự hỏi
nếu RC là chính xác,

288
00:12:20,620 --> 00:12:23,250
bạn có thể làm một cái gì đó giống như In RC.

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

290
00:12:24,380 --> 00:12:28,640
RC là hai, đó là
những gì chúng ta mong đợi, phải không?

291
00:12:28,640 --> 00:12:32,010
>> Vì vậy, chúng ta có thể đi tiếp,
và tiếp tục thông qua.

292
00:12:32,010 --> 00:12:33,200
Vì vậy, chúng tôi có một số trọng điểm có.

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

294
00:12:34,260 --> 00:12:37,090
Và chúng tôi có thể in ra chìa khóa của chúng tôi
để đảm bảo rằng đó là đúng.

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

296
00:12:38,380 --> 00:12:39,500
Thú vị.

297
00:12:39,500 --> 00:12:41,210
Không hẳn những gì chúng tôi mong đợi.

298
00:12:41,210 --> 00:12:44,810
Vì vậy, có một điều nhận ra
với GDB cũng là

299
00:12:44,810 --> 00:12:49,000
rằng nó không phải cho đến khi bạn thực sự đạt
Tiếp theo, các dòng mà bạn chỉ thấy

300
00:12:49,000 --> 00:12:50,720
được thực thi.

301
00:12:50,720 --> 00:12:53,870
Vì vậy, trong trường hợp này chính
chưa được ấn định nào.

302
00:12:53,870 --> 00:12:57,050
Vì vậy, chính là một số giá trị rác
mà bạn nhìn thấy ở phía dưới đó.

303
00:12:57,050 --> 00:13:03,680
Âm $ 120-- --It của một tỷ
và điều gì đó kỳ lạ phải không?

304
00:13:03,680 --> 00:13:05,340
Đây không phải là chính mà chúng ta mong đợi.

305
00:13:05,340 --> 00:13:10,720
Nhưng nếu chúng ta nhấn Next, và sau đó chúng tôi
cố gắng và phím Print, đó là ba.

306
00:13:10,720 --> 00:13:11,710
>> Mọi người đều nhìn thấy điều đó không?

307
00:13:11,710 --> 00:13:13,780
Vì vậy, nếu bạn nhận được một cái gì đó
rằng bạn có giống, chờ đợi.

308
00:13:13,780 --> 00:13:15,540
Điều này là hoàn toàn
sai, và tôi không biết

309
00:13:15,540 --> 00:13:20,150
làm thế nào điều này sẽ xảy ra bởi vì tất cả tôi muốn
để làm được gán một số, một biến,

310
00:13:20,150 --> 00:13:22,900
hãy thử nhấn Tiếp theo, hãy thử in
nó một lần nữa, và thấy rằng nếu các công trình.

311
00:13:22,900 --> 00:13:27,830
Bởi vì nó chỉ sẽ thực hiện và
thực sự chỉ định một cái gì đó sau khi bạn

312
00:13:27,830 --> 00:13:29,340
nhấn Next.

313
00:13:29,340 --> 00:13:30,336
Có ý nghĩa với tất cả mọi người?

314
00:13:30,336 --> 00:13:30,836
Uh huh?

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: Khi bạn ngẫu nhiên
số có nghĩa là gì?

316
00:13:33,220 --> 00:13:34,790
>> SPEAKER 1: Nó chỉ là ngẫu nhiên.

317
00:13:34,790 --> 00:13:35,710
Nó chỉ là rác.

318
00:13:35,710 --> 00:13:38,320
Nó chỉ là một cái gì đó của bạn
máy tính sẽ chỉ định một cách ngẫu nhiên.

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

320
00:13:39,721 --> 00:13:40,220
Cool.

321
00:13:40,220 --> 00:13:45,760
Vì vậy, bây giờ chúng ta có thể di chuyển qua, và như vậy
bây giờ chúng tôi có GetString văn bản đơn giản này.

322
00:13:45,760 --> 00:13:48,600
Vì vậy, hãy để tôi chỉ giới thiệu những gì
sẽ xảy ra khi chúng ta nhấn Next ở đây.

323
00:13:48,600 --> 00:13:51,320
GDB của chúng tôi loại biến mất, phải không?

324
00:13:51,320 --> 00:13:55,720
Đó là bởi vì GetString
bây giờ được thực hiện, phải không?

325
00:13:55,720 --> 00:14:01,460
Vì vậy, khi chúng ta nhìn thấy văn bản đơn giản bằng
GetString, dấu ngoặc mở và dấu ngoặc,

326
00:14:01,460 --> 00:14:04,380
và chúng tôi nhấn Next, có
thực tế thực hiện ngay bây giờ.

327
00:14:04,380 --> 00:14:06,580
Vì vậy, nó đang đợi
chúng tôi nhập vào một cái gì đó.

328
00:14:06,580 --> 00:14:13,560
>> Vì vậy, chúng ta sẽ phải nhập vào thực phẩm của chúng tôi
là những gì nó không như tôi đã nói với bạn

329
00:14:13,560 --> 00:14:18,020
và chỉ nói rằng đó là
thực hiện hoàn thành, đóng cửa

330
00:14:18,020 --> 00:14:19,980
khung có nghĩa là nó
thoát ra khỏi vòng lặp đó.

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

332
00:14:21,170 --> 00:14:25,420
Vì vậy, chúng ta có thể nhấn Next, và bây giờ, như tôi
chắc chắn rằng bạn đang quen thuộc từ Caesar,

333
00:14:25,420 --> 00:14:27,260
đây là, dòng này sẽ làm những gì.

334
00:14:27,260 --> 00:14:32,030
Nó cho Int tôi bằng 0, N bằng
Strlen, văn bản đơn giản, và sau đó

335
00:14:32,030 --> 00:14:33,960
Tôi là ít hơn n, I, cộng với, cộng.

336
00:14:33,960 --> 00:14:35,210
Vòng lặp này sẽ làm là gì?

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

338
00:14:37,900 --> 00:14:39,160
Mở tin nhắn của bạn.

339
00:14:39,160 --> 00:14:39,770
Cool.

340
00:14:39,770 --> 00:14:41,330
Vì vậy, hãy bắt đầu làm điều đó.

341
00:14:41,330 --> 00:14:47,210
>> Vì vậy, nên tình trạng này
phù hợp, cho một đầu tiên của chúng tôi?

342
00:14:47,210 --> 00:14:52,250
Nếu đó là một B, đó là văn bản đơn giản I. Chúng tôi
có thể nhận được thông tin về người dân địa phương của chúng tôi.

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

344
00:14:53,610 --> 00:14:57,970
Vì vậy, tôi là số không, và nếu sáu,
chúng ta mong đợi, và quan trọng của chúng tôi là ba.

345
00:14:57,970 --> 00:14:59,227
Tất cả những gì có ý nghĩa, phải không?

346
00:14:59,227 --> 00:15:01,310
Những con số này là tất cả
chính xác những gì họ cần.

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

348
00:15:02,590 --> 00:15:03,870
Vì vậy, ngâm nga?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Tôi có
số ngẫu nhiên cho tôi.

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

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: Vâng, chúng ta có thể check-- --we
có thể trò chuyện về điều đó trong một giây.

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

353
00:15:14,110 --> 00:15:15,750
Nhưng bạn nên nhận được điều này.

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

355
00:15:17,700 --> 00:15:20,130
Vì vậy, nếu chúng ta có một vốn
B cho một đầu tiên của chúng tôi,

356
00:15:20,130 --> 00:15:22,080
tình trạng này nên bắt nó, phải không?

357
00:15:22,080 --> 00:15:27,120
Vì vậy, nếu chúng ta nhấn Next, chúng ta thấy
Nếu đây là thực sự thực hiện.

358
00:15:27,120 --> 00:15:29,220
Bởi vì nếu bạn đang theo dõi
cùng trong mã của bạn,

359
00:15:29,220 --> 00:15:33,460
dòng này ở đây, nơi đồng bằng văn bản tôi
được thay thế bằng số học này,

360
00:15:33,460 --> 00:15:35,720
chỉ thực hiện nếu Nếu
điều kiện là đúng phải không?

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

362
00:15:36,905 --> 00:15:40,240
>> GDB chỉ sẽ cho bạn thấy
những điều thực sự thực hiện.

363
00:15:40,240 --> 00:15:45,140
Vì vậy, nếu tình trạng này Nếu không được đáp ứng, đó là
chỉ cần đi để chuyển sang dòng tiếp theo.

364
00:15:45,140 --> 00:15:46,540
OK?

365
00:15:46,540 --> 00:15:48,510
Vì vậy, chúng tôi có điều đó.

366
00:15:48,510 --> 00:15:51,171
Khung này có nghĩa là nó
đóng cửa ra của vòng lặp đó bây giờ.

367
00:15:51,171 --> 00:15:52,420
Vì vậy, nó sẽ bắt đầu lại.

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

369
00:15:54,760 --> 00:15:56,280
Chỉ cần như thế.

370
00:15:56,280 --> 00:15:59,120
Vì vậy, chúng tôi có thể nhận được thông tin
về người dân địa phương của chúng tôi ở đây,

371
00:15:59,120 --> 00:16:02,575
và chúng ta thấy rằng đầu tiên của chúng tôi
thư đã thay đổi, phải không?

372
00:16:02,575 --> 00:16:05,150
Nó bây giờ là một E, như nó phải được.

373
00:16:05,150 --> 00:16:07,360
Vì vậy, chúng tôi có thể tiếp tục.

374
00:16:07,360 --> 00:16:08,500
>> Và chúng tôi có kiểm tra này.

375
00:16:08,500 --> 00:16:09,916
Và việc kiểm tra này nên làm việc, phải không?

376
00:16:09,916 --> 00:16:12,570
Đó là A. Nó nên được thay đổi
ba chữ cái về phía trước.

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

378
00:16:14,320 --> 00:16:16,530
Nhưng nếu bạn thông báo, chúng tôi
có được một cái gì đó khác nhau.

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

380
00:16:17,580 --> 00:16:22,860
Vì vậy, trong trường hợp này lên đây, nó bắt
nó, và để dòng này thực hiện,

381
00:16:22,860 --> 00:16:28,620
mà sửa đổi B. của chúng tôi
Nhưng, trong trường hợp này đây,

382
00:16:28,620 --> 00:16:32,860
chúng tôi có mà nó chỉ bỏ qua nó,
và đã đi đến [? L SIFF. ?]

383
00:16:32,860 --> 00:16:34,660
Vì vậy, một cái gì đó đang xảy ra ở đó.

384
00:16:34,660 --> 00:16:37,780
Điều đó nói cho bạn đó là,
chúng ta biết rằng nó nên bắt ở đây,

385
00:16:37,780 --> 00:16:39,200
nhưng nó không phải.

386
00:16:39,200 --> 00:16:42,210
Bất cứ ai có thể xem những gì chúng tôi
vấn đề là trong dòng đó?

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

388
00:16:45,380 --> 00:16:46,969
Đó là một điều rất phút.

389
00:16:46,969 --> 00:16:48,510
Và bạn cũng có thể nhìn vào code của bạn.

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

391
00:16:49,980 --> 00:16:54,940
Nó cũng line-- quên những gì nó là dòng
trong there-- nhưng nó trong [không nghe được].

392
00:16:54,940 --> 00:16:55,480
Có?

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: Đó là vào lớn hơn
trang nếu bạn đọc nó trong cuốn sách.

394
00:16:58,639 --> 00:16:59,430
SPEAKER 1: Chính xác.

395
00:16:59,430 --> 00:17:02,620
Vì vậy, các trình gỡ lỗi không thể nói
bạn đó, nhưng chương trình gỡ rối

396
00:17:02,620 --> 00:17:05,880
có thể giúp bạn xuống một dòng
mà bạn biết là không hoạt động.

397
00:17:05,880 --> 00:17:09,319
Và đôi khi, đặc biệt là khi
sau này trong học kỳ, khi

398
00:17:09,319 --> 00:17:12,910
bạn đang đối phó với một trăm, một
trăm vài dòng mã, và bạn

399
00:17:12,910 --> 00:17:16,190
không biết nơi mà nó thất bại,
đây là một cách tuyệt vời để làm điều đó.

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

401
00:17:17,900 --> 00:17:18,989
Vì vậy, chúng tôi tìm thấy lỗi của chúng tôi.

402
00:17:18,989 --> 00:17:21,530
Bạn có thể sửa chữa nó trong tập tin của bạn,
và sau đó bạn có thể chạy nó một lần nữa,

403
00:17:21,530 --> 00:17:23,029
và tất cả mọi thứ sẽ làm việc hoàn hảo.

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

405
00:17:24,970 --> 00:17:30,590
Và điều lớn nhất là
điều này có thể có vẻ như, OK.

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

407
00:17:31,090 --> 00:17:31,370
Cool.

408
00:17:31,370 --> 00:17:32,744
Bạn biết những gì bạn đang tìm kiếm.

409
00:17:32,744 --> 00:17:34,910
Vì vậy, bạn biết phải làm gì.

410
00:17:34,910 --> 00:17:39,021
>> GDB có thể được siêu hữu ích bởi vì bạn
có thể in ra tất cả những điều mà bạn

411
00:17:39,021 --> 00:17:39,520
sẽ không được.

412
00:17:39,520 --> 00:17:41,160
Đó là hữu ích hơn nhiều so với printf.

413
00:17:41,160 --> 00:17:43,440
Có bao nhiêu bạn sử dụng
như printf

414
00:17:43,440 --> 00:17:46,200
để tìm ra nơi một lỗi là, phải không?

415
00:17:46,200 --> 00:17:48,450
Vì vậy, với điều này, bạn không
phải tiếp tục đi trở lại,

416
00:17:48,450 --> 00:17:51,139
và như ý kiến ​​trong
Printf, hoặc cho ý kiến ​​ra,

417
00:17:51,139 --> 00:17:52,930
và tìm ra những gì
bạn nên in.

418
00:17:52,930 --> 00:17:55,670
Điều này thực sự chỉ cho phép bạn
bước qua, in ra những thứ

419
00:17:55,670 --> 00:18:00,000
như bạn đang trải qua, vì vậy, bạn có thể
quan sát cách họ thay đổi trong thời gian thực,

420
00:18:00,000 --> 00:18:02,190
như chương trình của bạn đang chạy.

421
00:18:02,190 --> 00:18:04,390
>> Và nó mất một ít
chút về việc sử dụng để.

422
00:18:04,390 --> 00:18:07,850
Tôi rất muốn giới thiệu chỉ loại
trở thành một chút thất vọng với nó

423
00:18:07,850 --> 00:18:08,930
cho ngay bây giờ.

424
00:18:08,930 --> 00:18:13,450
Nếu bạn dành một giờ qua
tuần tới học cách sử dụng GDB,

425
00:18:13,450 --> 00:18:16,140
bạn sẽ tiết kiệm cho mình
rất nhiều thời gian sau này.

426
00:18:16,140 --> 00:18:18,750
Và theo nghĩa đen. chúng tôi nói
này để người mỗi năm,

427
00:18:18,750 --> 00:18:23,890
và tôi nhớ khi tôi đã
lớp học, tôi đã như thế, tôi sẽ bị phạt.

428
00:18:23,890 --> 00:18:24,700
Không.

429
00:18:24,700 --> 00:18:27,030
Pset 6 đã vào sân và tôi đã
như thế, tôi sẽ học

430
00:18:27,030 --> 00:18:29,500
làm thế nào để sử dụng GDB bởi vì tôi không
biết những gì đang xảy ra ở đây.

431
00:18:29,500 --> 00:18:32,940
>> Vì vậy, nếu bạn dành thời gian để
sử dụng nó trên chương trình nhỏ hơn

432
00:18:32,940 --> 00:18:35,697
rằng bạn sẽ được
làm việc trên, như làm việc

433
00:18:35,697 --> 00:18:37,530
thông qua một cái gì đó như
Visionare, như thế này.

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

435
00:18:38,800 --> 00:18:42,850
Hoặc nếu bạn muốn thực hành thêm, tôi chắc chắn
Tôi có thể đến với các chương trình lỗi,

436
00:18:42,850 --> 00:18:45,300
để bạn có thể gỡ lỗi nếu bạn muốn.

437
00:18:45,300 --> 00:18:49,300
>> Nhưng nếu bạn chỉ mất một thời gian để có được
sử dụng nó, chỉ chơi đùa với nó,

438
00:18:49,300 --> 00:18:50,550
nó sẽ thực sự phục vụ bạn tốt.

439
00:18:50,550 --> 00:18:52,591
Và nó thực sự là một trong
những điều mà bạn chỉ

440
00:18:52,591 --> 00:18:57,340
phải cố gắng, và có được bàn tay của bạn bẩn
với, trước khi bạn thực sự hiểu nó.

441
00:18:57,340 --> 00:19:02,090
Tôi thực sự chỉ hiểu nó một lần
Tôi đã phải debug việc với nó,

442
00:19:02,090 --> 00:19:08,170
và nó đẹp hơn nhiều để có một ý tưởng
làm thế nào để gỡ lỗi càng sớm càng tốt.

443
00:19:08,170 --> 00:19:08,850
OK.

444
00:19:08,850 --> 00:19:09,625
Cool.

445
00:19:09,625 --> 00:19:12,960
Tôi biết đó là loại giống như
một khóa học sụp đổ trong GDB,

446
00:19:12,960 --> 00:19:16,400
và tôi chắc chắn sẽ làm việc trên nhận được
những nhìn lớn hơn thời gian tới.

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

448
00:19:17,590 --> 00:19:18,280
Cool.

449
00:19:18,280 --> 00:19:20,390
>> Vì vậy, nếu chúng ta trở lại PowerPoint của chúng tôi.

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

451
00:19:27,194 --> 00:19:28,110
Điều này sẽ làm việc?

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

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

454
00:19:30,210 --> 00:19:31,101
Vâng.

455
00:19:31,101 --> 00:19:31,600
OK.

456
00:19:31,600 --> 00:19:35,480
Vì vậy, nếu bạn cần bất kỳ
những người một lần nữa, có trong danh sách.

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

458
00:19:37,160 --> 00:19:40,830
Vì vậy, tìm kiếm nhị phân, mà tất cả mọi người
nhớ lại cảnh tượng tuyệt vời của David

459
00:19:40,830 --> 00:19:42,259
trích xuất sách điện thoại trong một nửa.

460
00:19:42,259 --> 00:19:44,050
Tôi không thực sự có được
sách điện thoại nữa,

461
00:19:44,050 --> 00:19:46,530
bởi vì như nơi nào bạn
nhận được sách điện thoại những ngày này?

462
00:19:46,530 --> 00:19:48,220
Tôi thực sự không biết.

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

464
00:19:49,840 --> 00:19:50,590
Tìm kiếm nhị phân.

465
00:19:50,590 --> 00:19:52,464
Có ai nhớ
cách tìm kiếm nhị phân công trình?

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

467
00:19:54,380 --> 00:19:55,220
Bất cứ ai ở tất cả?

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

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Bạn biết khi nào
bạn nhìn vào đó một nửa

470
00:19:58,283 --> 00:20:01,146
nó sẽ được ở, Trên cơ sở đó,
và thoát khỏi một nửa khác.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 Chính xác.

472
00:20:01,896 --> 00:20:06,290
Vì vậy, tìm kiếm nhị phân, nó là loại a--
--we thích gọi nó là phân chia và chinh phục.

473
00:20:06,290 --> 00:20:09,170
Vì vậy, những gì bạn sẽ làm là
bạn sẽ nhìn ở giữa,

474
00:20:09,170 --> 00:20:11,990
và bạn sẽ thấy nó có phù hợp
những gì bạn đang tìm kiếm.

475
00:20:11,990 --> 00:20:15,420
Và nếu không, sau đó bạn cố gắng
tìm ra, là nó sẽ bị bỏ lại

476
00:20:15,420 --> 00:20:16,450
một nửa hoặc nửa bên phải.

477
00:20:16,450 --> 00:20:19,325
Vì vậy, đây có thể là nếu bạn đang tìm kiếm
tại cái gì đó là chữ cái là,

478
00:20:19,325 --> 00:20:20,720
bạn nhìn thấy, oh.

479
00:20:20,720 --> 00:20:22,750
Có Allison đến trước khi M?

480
00:20:22,750 --> 00:20:23,250
Vâng.

481
00:20:23,250 --> 00:20:25,030
Vì vậy, chúng ta sẽ
nhìn vào nửa đầu.

482
00:20:25,030 --> 00:20:26,450
>> Hoặc nó có thể là giống như với các con số.

483
00:20:26,450 --> 00:20:28,830
Bất cứ điều gì mà bạn có thể
so sánh, nó có thể được sắp xếp.

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

485
00:20:29,920 --> 00:20:31,260
Bạn có thể sử dụng tìm kiếm nhị phân trên.

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

487
00:20:32,340 --> 00:20:37,455
Vì vậy, bất cứ ai nhớ này
đồ thị hoặc này là gì?

488
00:20:37,455 --> 00:20:39,520
Nó phức tạp tiệm cận.

489
00:20:39,520 --> 00:20:42,830
Vì vậy, đồ thị này chỉ
mô tả bao lâu

490
00:20:42,830 --> 00:20:46,230
sẽ đưa bạn đến giải quyết một vấn đề như
bạn tăng số lượng các điều

491
00:20:46,230 --> 00:20:47,090
mà bạn đang sử dụng.

492
00:20:47,090 --> 00:20:51,260
>> Vì vậy, chúng tôi có tồn tại, đó là thời gian tuyến tính.

493
00:20:51,260 --> 00:20:54,560
Nếu N hơn hai, đó là hơi
tốt hơn, vẫn phát triển nhanh chóng.

494
00:20:54,560 --> 00:20:58,360
Và sau đó chúng tôi đã đăng nhập, đó là
những gì chúng ta xem xét tìm kiếm nhị phân.

495
00:20:58,360 --> 00:21:03,630
Nếu chúng tôi nhận thấy, là vấn đề của bạn
được lớn hơn nhiều và nhiều hơn,

496
00:21:03,630 --> 00:21:06,600
thời gian nó sẽ đưa bạn để giải quyết nó
không thực sự tăng nhiều.

497
00:21:06,600 --> 00:21:09,010
Nó giống như so sánh
ở đây trong đầu.

498
00:21:09,010 --> 00:21:10,060
Bạn giống như, OK.

499
00:21:10,060 --> 00:21:13,000
Bất cứ điều gì ở đây không thực sự
vấn đề mà chúng ta sử dụng,

500
00:21:13,000 --> 00:21:16,220
nhưng bạn nhận ra một triệu, một tỷ đồng.

501
00:21:16,220 --> 00:21:20,010
Bạn đang cố gắng để tìm some-- --you're
cố gắng tìm một cây kim trong một đống cỏ khô.

502
00:21:20,010 --> 00:21:21,550
>> Tôi nghĩ rằng bạn muốn vấn đề này.

503
00:21:21,550 --> 00:21:25,850
Bạn muốn phức tạp này, không
tuyến tính bởi vì đối với tất cả các bạn

504
00:21:25,850 --> 00:21:30,049
biết sẽ của bạn được tìm kiếm thông qua
mỗi kim cá nhân, điều cỏ khô,

505
00:21:30,049 --> 00:21:31,340
cố gắng để tìm kim của bạn.

506
00:21:31,340 --> 00:21:34,730
Và đó không phải là quá vui vẻ theo ý kiến ​​của tôi.

507
00:21:34,730 --> 00:21:35,500
Tôi thích nhanh.

508
00:21:35,500 --> 00:21:36,620
Tôi thích hiệu quả.

509
00:21:36,620 --> 00:21:40,450
Và sinh viên chăm chỉ như bạn
kẻ đang có, bạn biết làm việc thông minh hơn,

510
00:21:40,450 --> 00:21:43,010
không khó khăn hơn loại điều, làm thế nào bạn
có thể tạo nên các thuật toán.

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

512
00:21:45,110 --> 00:21:47,910
>> Vì vậy, chúng ta sẽ đi bộ
thông qua chỉ là một ví dụ nhanh chóng.

513
00:21:47,910 --> 00:21:51,090
Tôi nghĩ các bạn nên có
một bàn tay lên tìm kiếm nhị phân,

514
00:21:51,090 --> 00:21:54,352
nhưng trong trường hợp bất cứ ai là một chút
mờ, muốn củng cố nó,

515
00:21:54,352 --> 00:21:56,310
chúng ta sẽ chỉ cần đi
thông qua một ví dụ ở đây.

516
00:21:56,310 --> 00:21:59,490
Vì vậy, chúng tôi đang tìm kiếm nếu
mảng chứa bảy.

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

518
00:22:00,540 --> 00:22:06,010
>> Vì vậy, điều đầu tiên chúng tôi làm là
nhìn ở giữa, phải không?

519
00:22:06,010 --> 00:22:09,340
Và cũng có thể bạn sẽ được mã hóa
Tìm kiếm nhị phân chỉ trong một giây.

520
00:22:09,340 --> 00:22:11,310
Vì vậy, nó sẽ được vui vẻ.

521
00:22:11,310 --> 00:22:13,710
Vì vậy, chúng ta hãy nhìn vào
mảng nhỏ giữa 3.

522
00:22:13,710 --> 00:22:15,501
Có 3 bằng 7?

523
00:22:15,501 --> 00:22:16,000
Không.

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

525
00:22:18,670 --> 00:22:19,550
Đó là sáu.

526
00:22:19,550 --> 00:22:21,480
Vì vậy, nó ít hơn
hoặc lớn hơn bảy?

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

528
00:22:23,080 --> 00:22:23,960
Ít hơn.

529
00:22:23,960 --> 00:22:24,570
Vâng.

530
00:22:24,570 --> 00:22:25,170
Tốt công việc guys.

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

532
00:22:25,569 --> 00:22:27,360
Tôi cảm thấy tôi thích nên tôi
có kẹo vì tôi

533
00:22:27,360 --> 00:22:29,460
muốn ném nó ra vào bãi.

534
00:22:29,460 --> 00:22:30,270
Đó là những gì tôi sẽ làm trong tuần tiếp theo.

535
00:22:30,270 --> 00:22:31,436
Nó sẽ giữ cho bạn kẻ sắc nét.

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

537
00:22:32,560 --> 00:22:34,690
>> Vì vậy, chúng ta vứt đi mà
nửa đầu, phải không?

538
00:22:34,690 --> 00:22:35,670
nó là ít hơn.

539
00:22:35,670 --> 00:22:39,325
chúng ta biết rằng tất cả mọi thứ
trên đó phía bên tay trái

540
00:22:39,325 --> 00:22:41,700
là có được ít hơn những gì
chúng tôi đang thực sự tìm kiếm.

541
00:22:41,700 --> 00:22:43,491
Vì vậy, không có nhu cầu
chú ý đến nó.

542
00:22:43,491 --> 00:22:45,120
Chỉ cần quên nó.

543
00:22:45,120 --> 00:22:48,720
Vì vậy, bây giờ chúng ta nhìn vào phía bên tay phải của chúng tôi,
và chúng ta nhìn vào giữa ở đó,

544
00:22:48,720 --> 00:22:50,510
và bây giờ là chín.

545
00:22:50,510 --> 00:22:55,510
Vì vậy, 9 is-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Lớn hơn những gì chúng tôi
tìm kiếm, phải không?

547
00:22:57,470 --> 00:22:59,860
Vì vậy, chúng ta sẽ ném
đi tất cả mọi thứ bên phải.

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

549
00:23:00,970 --> 00:23:01,940
Như thế.

550
00:23:01,940 --> 00:23:03,700
Bây giờ, tất cả chúng tôi đang trái với là một.

551
00:23:03,700 --> 00:23:07,760
Vì vậy, chúng tôi kiểm tra, là một trong những gì này
chúng tôi đang tìm kiếm? nó được.

552
00:23:07,760 --> 00:23:08,970
Chúng tôi tìm thấy những gì chúng tôi muốn.

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

554
00:23:10,440 --> 00:23:11,690
Vì vậy, chúng tôi đang thực hiện.

555
00:23:11,690 --> 00:23:12,550
Bilinear Search.

556
00:23:12,550 --> 00:23:15,740
>> Và nếu bạn thấy, chúng tôi
có bảy đầu vào đó.

557
00:23:15,740 --> 00:23:24,320
Nó chỉ đưa chúng tôi như ba lần,
nhưng nếu bạn đang làm như một tỷ đồng,

558
00:23:24,320 --> 00:23:28,190
Các bạn có biết có bao nhiêu bước nó sẽ
mất nếu chúng ta có bốn tỉ những thứ?

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

560
00:23:29,940 --> 00:23:30,455
Bất kỳ dự đoán?

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

562
00:23:32,286 --> 00:23:33,960
Đó là 32.

563
00:23:33,960 --> 00:23:37,110
32 bước để tìm một cái gì đó
trong bốn tỷ

564
00:23:37,110 --> 00:23:39,650
phần tử mảng vì quyền hạn của hai.

565
00:23:39,650 --> 00:23:43,550
Vì vậy, hai là 32, là bốn tỷ.

566
00:23:43,550 --> 00:23:50,430
>> Vì vậy, cách khá điên rồ bạn vẫn còn trong vòng
như một số lượng khá nhỏ bước

567
00:23:50,430 --> 00:23:52,650
để tìm một cái gì đó trong
bốn tỷ yếu tố.

568
00:23:52,650 --> 00:23:55,730
Vì vậy, trên lưu ý rằng, chúng tôi
sẽ mã này

569
00:23:55,730 --> 00:23:58,950
vậy các bạn có thể thực sự
loại xem cách làm việc này.

570
00:23:58,950 --> 00:24:01,520
Được rồi, vậy các bạn có thể mã.

571
00:24:01,520 --> 00:24:04,100
Tôi sẽ để cho các bạn
nói chuyện một chút.

572
00:24:04,100 --> 00:24:07,970
Nhận biết những người xung quanh bạn, mà là
những gì một người nào đó muốn từ phần cuối.

573
00:24:07,970 --> 00:24:10,280
>> Vì vậy, nhận biết những người xung quanh bạn.

574
00:24:10,280 --> 00:24:11,305
Nói chuyện một chút.

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

576
00:24:12,580 --> 00:24:15,730
Và tất cả tôi muốn từ bạn
kẻ ngay bây giờ chỉ là

577
00:24:15,730 --> 00:24:17,575
cố gắng tạo ra một phác thảo của giả.

578
00:24:17,575 --> 00:24:18,075
OK?

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

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

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

582
00:24:23,320 --> 00:24:29,520
Tất cả tôi muốn từ các bạn là bạn
chỉ cần đi để điền vào trong trường hợp trong khi điều này.

583
00:24:29,520 --> 00:24:32,170
Vì vậy, tôi đã thiết lập các trên
và giới hạn thấp hơn mà

584
00:24:32,170 --> 00:24:35,250
đại diện đầu
và cuối mảng của chúng tôi.

585
00:24:35,250 --> 00:24:40,440
Và bạn sẽ thực sự
lặp qua và tìm ra

586
00:24:40,440 --> 00:24:42,470
những gì chúng ta đang làm trong vòng lặp trong khi điều này.

587
00:24:42,470 --> 00:24:45,810
>> Vì vậy, nếu bạn có thể tìm out-- tôi có
một gợi ý there-- các trường hợp là gì

588
00:24:45,810 --> 00:24:46,640
mà chúng ta có ở đây?

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

590
00:24:48,100 --> 00:24:51,560
Vì vậy, nếu bạn muốn tìm ra
trường hợp, chúng tôi sẽ giả những

591
00:24:51,560 --> 00:24:53,350
và sau đó chúng tôi sẽ thực sự mã chúng.

592
00:24:53,350 --> 00:24:55,330
Và nó sẽ được, tôi
nghĩ, hy vọng nó sẽ thấy

593
00:24:55,330 --> 00:24:56,788
là một chút dễ dàng hơn bạn mong đợi.

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

595
00:24:57,554 --> 00:25:00,220
Bởi vì nó không phải là nhiều mã,
trên thực tế, đó là thực sự mát mẻ.

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

597
00:25:34,110 --> 00:25:35,018
>> Mm-hm?

598
00:25:35,018 --> 00:25:35,893
>> HỌC SINH: [không nghe được]?

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

600
00:25:36,984 --> 00:25:37,650
GIẢNG: Có.

601
00:25:37,650 --> 00:25:38,595
Có cái gì đó
tìm ở giữa.

602
00:25:38,595 --> 00:25:39,552
>> SINH VIÊN: Vì vậy, chúng ta có thể sử dụng đó.

603
00:25:39,552 --> 00:25:39,770
OK.

604
00:25:39,770 --> 00:25:40,603
>> GIẢNG: Hoàn hảo.

605
00:25:40,603 --> 00:25:42,950
Vì vậy, đó là điều đầu tiên chúng ta cần làm.

606
00:25:42,950 --> 00:25:44,330
Vì vậy, tìm thấy giữa.

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

608
00:25:45,415 --> 00:25:45,915
Tuyệt vời.

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

610
00:25:47,770 --> 00:25:55,010
Vì vậy, bạn có một ý tưởng làm thế nào chúng ta có thể
thực sự tìm thấy giữa với mã?

611
00:25:55,010 --> 00:25:55,980
>> HỌC SINH: Yeah.

612
00:25:55,980 --> 00:25:57,000
n hơn 2?

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

614
00:25:58,500 --> 00:25:59,500
GIẢNG: Vì vậy, n hơn 2.

615
00:25:59,500 --> 00:26:05,170
Vì vậy, có một điều cần nhớ là
giới hạn trên và dưới của bạn thay đổi.

616
00:26:05,170 --> 00:26:08,110
Chúng tôi tiếp tục thắt phần
của mảng, chúng tôi đang tìm kiếm.

617
00:26:08,110 --> 00:26:11,970
Vì vậy, n trên 2 sẽ chỉ làm việc
cho điều đầu tiên chúng tôi làm.

618
00:26:11,970 --> 00:26:17,810
Vì vậy, lấy trên và dưới vào tài khoản,
làm thế nào chúng ta có thể nhận được rằng yếu tố trung?

619
00:26:17,810 --> 00:26:20,640
Bởi vì chúng tôi muốn giữa
giữa trên và dưới, phải không?

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

621
00:26:21,730 --> 00:26:22,494
Mm-hm?

622
00:26:22,494 --> 00:26:23,369
>> HỌC SINH: [không nghe được].

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

624
00:26:26,170 --> 00:26:28,080
>> GIẢNG: Vì vậy, chúng tôi có một số trung lưu.

625
00:26:28,080 --> 00:26:32,730
Và nó sẽ được trên cộng thấp hơn 2.

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

627
00:26:34,740 --> 00:26:35,690
Tuyệt vời.

628
00:26:35,690 --> 00:26:36,570
Hiện chúng tôi đi.

629
00:26:36,570 --> 00:26:37,280
Một dòng xuống.

630
00:26:37,280 --> 00:26:38,560
Các bạn đang trên đường của bạn.

631
00:26:38,560 --> 00:26:41,400
Vì vậy, bây giờ chúng ta có của chúng tôi
trung, những gì chúng tôi muốn làm gì?

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

633
00:26:45,050 --> 00:26:45,900
Chỉ cần nói chung.

634
00:26:45,900 --> 00:26:47,734
Bạn không cần phải mã nó.

635
00:26:47,734 --> 00:26:48,335
Vâng.

636
00:26:48,335 --> 00:26:49,210
HỌC SINH: [không nghe được]?

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

638
00:27:00,310 --> 00:27:10,310
GIẢNG: Vì vậy, nó cộng vì bạn
việc tìm kiếm trung bình giữa hai

639
00:27:10,310 --> 00:27:10,810
trong số họ.

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

641
00:27:11,890 --> 00:27:17,370
Vì vậy, nếu bạn nghĩ về họ như loại
tăng từ hai bên,

642
00:27:17,370 --> 00:27:21,640
suy nghĩ về nó khi bạn tiếp cận
giữa, bạn muốn như thế.

643
00:27:21,640 --> 00:27:27,150
Vì vậy, nếu bạn đang ở hai bên của
trung bình, và chúng tôi có giống như 5 và 7.

644
00:27:27,150 --> 00:27:31,440
Khi bạn thêm chúng với nhau bạn
nhận được 12, bạn chia cho 2, 6.

645
00:27:31,440 --> 00:27:33,726
>> Đôi khi thật khó để
giải thích lý do tại sao mà các công trình,

646
00:27:33,726 --> 00:27:35,600
nhưng nếu bạn làm việc thông qua
một ví dụ đôi khi,

647
00:27:35,600 --> 00:27:37,962
nó sẽ giúp bạn tìm ra nếu
nó phải được cộng hoặc trừ.

648
00:27:37,962 --> 00:27:38,846
Vâng.

649
00:27:38,846 --> 00:27:40,830
>> HỌC SINH: [không nghe được]
chính xác ở giữa

650
00:27:40,830 --> 00:27:43,950
nếu họ đã có một trường hợp
có rất nhiều con số nhỏ hơn

651
00:27:43,950 --> 00:27:45,860
và như một số lượng lớn?

652
00:27:45,860 --> 00:27:49,750
>> GIẢNG: Vì vậy, tất cả các bạn cần
là giữa mảng.

653
00:27:49,750 --> 00:27:53,010
Vì vậy, nếu bạn đã có một loạt các con số nhỏ
và sau đó một số thực sự lớn

654
00:27:53,010 --> 00:27:54,799
ở cuối, nó không quan trọng.

655
00:27:54,799 --> 00:27:56,840
Tất cả những vấn đề là
họ đang sắp xếp, bạn chỉ cần

656
00:27:56,840 --> 00:27:59,339
muốn nhìn vào giữa
mảng bởi vì bạn vẫn còn

657
00:27:59,339 --> 00:28:00,700
cắt vấn đề của bạn trong một nửa.

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

659
00:28:03,020 --> 00:28:03,680
Cool.

660
00:28:03,680 --> 00:28:06,430
Vì vậy, bây giờ chúng ta có
trung bình, chúng ta làm gì tiếp theo?

661
00:28:06,430 --> 00:28:07,150
>> HỌC SINH: So sánh.

662
00:28:07,150 --> 00:28:08,150
GIẢNG: Các so sánh.

663
00:28:08,150 --> 00:28:11,670
Vì vậy, so sánh giữa để value_wanted.

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

665
00:28:14,300 --> 00:28:15,160
Cool.

666
00:28:15,160 --> 00:28:17,950
Vì vậy, bạn nhìn thấy ở đây chúng tôi có
giá trị này, chúng tôi muốn ở đây.

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

668
00:28:22,012 --> 00:28:23,095
Hãy nhớ rằng đây là một mảng.

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

670
00:28:24,100 --> 00:28:26,970
Vì vậy, trung đề cập đến chỉ số.

671
00:28:26,970 --> 00:28:29,785
Vì vậy, chúng tôi muốn làm giá trị trung bình.

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

673
00:28:32,380 --> 00:28:35,650
Đừng quên nếu bạn muốn
để so sánh, bình đẳng đôi.

674
00:28:35,650 --> 00:28:38,250
Bạn làm đơn bằng bạn
chỉ cần đi để gán lại nó,

675
00:28:38,250 --> 00:28:41,090
và sau đó, tất nhiên, đó là
sẽ là giá trị bạn muốn.

676
00:28:41,090 --> 00:28:42,300
Vì vậy, không làm điều đó.

677
00:28:42,300 --> 00:28:44,350
>> Vì vậy, chúng ta sẽ xem
các giá trị ở giữa

678
00:28:44,350 --> 00:28:46,460
bằng với giá trị chúng ta muốn.

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

680
00:28:47,749 --> 00:28:48,790
Đừng quên niềng răng của bạn.

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

682
00:28:50,520 --> 00:28:52,235
Dropbox sẽ biến mất.

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

684
00:28:54,140 --> 00:28:56,200
Vì vậy, chúng ta làm gì trong trường hợp này?

685
00:28:56,200 --> 00:28:59,360
Nếu đó là những gì chúng ta muốn quay trở lại?

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

687
00:29:01,510 --> 00:29:02,626
Chúng tôi đang cố gắng để nói.

688
00:29:02,626 --> 00:29:03,440
>> HỌC SINH: In tắt.

689
00:29:03,440 --> 00:29:05,314
>> GIẢNG: Vâng, chúng tôi
không muốn in ra.

690
00:29:05,314 --> 00:29:08,220
Vì vậy, đây là một bool ở đây, vì vậy chúng tôi
muốn trở lại đúng hay sai.

691
00:29:08,220 --> 00:29:12,280
Chúng ta đang nói, là con số này
một [? RRA? ?] Vì vậy, nếu nó là,

692
00:29:12,280 --> 00:29:13,788
chúng tôi chỉ trả lại sự thật.

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

694
00:29:16,780 --> 00:29:17,760
Nếu tôi có thể đánh vần đúng.

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

696
00:29:18,830 --> 00:29:20,805
>> HỌC SINH: Tại sao bạn sẽ không quay trở lại không?

697
00:29:20,805 --> 00:29:22,930
GIẢNG: Vì vậy, bạn có thể
trở về zero nếu bạn muốn.

698
00:29:22,930 --> 00:29:26,780
Nhưng trong trường hợp này bởi vì
chức năng của chúng tôi trả về một bool,

699
00:29:26,780 --> 00:29:28,962
chúng ta cần phải trở về đúng hoặc sai.

700
00:29:28,962 --> 00:29:30,920
HỌC SINH: Khi bạn
nói rằng biểu thức boolean,

701
00:29:30,920 --> 00:29:33,450
bạn có thể thiết lập nó bằng giả?

702
00:29:33,450 --> 00:29:39,860
Cũng giống như nếu tôi muốn nói, nếu tình trạng này
không được đáp ứng, giống như là trên bằng giả.

703
00:29:39,860 --> 00:29:42,332
Nó sẽ hiểu nếu bạn chỉ
đặt sai ở phía bên kia?

704
00:29:42,332 --> 00:29:43,040
GIẢNG: Yeah.

705
00:29:43,040 --> 00:29:44,820
Vì vậy, thực sự nếu bạn
bao giờ làm điều gì đó

706
00:29:44,820 --> 00:29:49,600
như là trên hoặc thấp hơn,
trả về đúng hay sai

707
00:29:49,600 --> 00:29:53,850
và đó là phong cách thực sự xấu
nói bằng bằng đúng hay equals

708
00:29:53,850 --> 00:29:54,840
bằng giả.

709
00:29:54,840 --> 00:30:00,210
Bạn muốn sử dụng kết quả đó
như chính nó như là kiểm tra của bạn.

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

711
00:30:04,720 --> 00:30:05,860
Không phải những gì tôi muốn.

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

713
00:30:08,150 --> 00:30:09,240
Đó là những gì tôi muốn.

714
00:30:09,240 --> 00:30:13,205
Vì vậy, trong trường hợp bạn đang yêu cầu
về một cái gì đó giống như tiết kiệm này trong c.

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

716
00:30:16,320 --> 00:30:25,150
>> Vì vậy, nếu chúng tôi có int main (void)
và một cái gì đó như thế này.

717
00:30:25,150 --> 00:30:31,922
Và nếu bạn có là trên
của một số đầu vào và bạn

718
00:30:31,922 --> 00:30:33,630
yêu cầu nếu bạn có thể làm
một cái gì đó như thế này?

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

720
00:30:35,010 --> 00:30:35,679
Phải không?

721
00:30:35,679 --> 00:30:37,470
HỌC SINH: Tôi đã cố gắng
để làm điều đó [không nghe được].

722
00:30:37,470 --> 00:30:38,450
Bởi vì nếu it's--

723
00:30:38,450 --> 00:30:39,200
GIẢNG: Đúng vậy.

724
00:30:39,200 --> 00:30:41,197
Vì vậy, bạn muốn điều này là sai lầm, phải không?

725
00:30:41,197 --> 00:30:41,780
HỌC SINH: Yeah.

726
00:30:41,780 --> 00:30:45,960
GIẢNG: Vì vậy, trong trường hợp này bạn
muốn nó để thực thi nếu nó không đúng sự thật.

727
00:30:45,960 --> 00:30:50,510
Vì vậy, điều bạn làm mát có này.

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

729
00:30:52,900 --> 00:30:55,650
Vì vậy, nhớ chấm than
điểm phủ nhận điều này?

730
00:30:55,650 --> 00:30:58,270
Nó nói [không nghe được] có nghĩa là không.

731
00:30:58,270 --> 00:31:03,590
Vì vậy, nếu chúng ta nhìn vào chỉ
phần này ở đây, bạn muốn

732
00:31:03,590 --> 00:31:05,740
nói rằng để đánh giá
giả như bạn muốn nó.

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

734
00:31:06,790 --> 00:31:09,880
Không sai là đúng mà
có nghĩa là điều này sẽ thực thi.

735
00:31:09,880 --> 00:31:11,037
Điều đó có ý nghĩa?

736
00:31:11,037 --> 00:31:11,620
HỌC SINH: Yeah.

737
00:31:11,620 --> 00:31:12,453
GIẢNG: Awesome.

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

739
00:31:13,800 --> 00:31:14,300
OK.

740
00:31:14,300 --> 00:31:16,330
Vì vậy, chúng tôi chỉ có thể trở lại
đúng trong trường hợp này.

741
00:31:16,330 --> 00:31:20,357
Vì vậy, bây giờ chúng tôi có hai khác
trường hợp trong trường hợp này.

742
00:31:20,357 --> 00:31:21,565
Hai trường hợp khác của chúng tôi là gì?

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

744
00:31:31,610 --> 00:31:32,900
Hãy làm theo cách này.

745
00:31:32,900 --> 00:31:40,660
Vì vậy, hãy bắt đầu với người khác
nếu giá trị ở giữa

746
00:31:40,660 --> 00:31:43,230
là thấp hơn giá trị chúng ta muốn.

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

748
00:31:47,200 --> 00:31:52,020
Vì vậy, giá trị của chúng tôi ở giữa là ít
hơn giá trị mà chúng ta đang tìm kiếm.

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

750
00:31:53,765 --> 00:31:56,720
>> Vì vậy mà ràng buộc làm bạn
nghĩ rằng chúng tôi muốn cập nhật?

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

752
00:31:57,870 --> 00:31:58,780
Trên hoặc thấp hơn?

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

754
00:32:01,440 --> 00:32:01,940
Trên?

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

756
00:32:03,230 --> 00:32:06,470
Vì vậy, mà phía của mảng
chúng ta sẽ được xem xét?

757
00:32:06,470 --> 00:32:07,500
>> HỌC SINH: càng thấp.

758
00:32:07,500 --> 00:32:09,750
>> GIẢNG: Chúng tôi chúng ta sẽ
được tìm kiếm ở bên trái.

759
00:32:09,750 --> 00:32:11,120
Vì vậy, nếu người nào khác ít có giá trị ít hơn.

760
00:32:11,120 --> 00:32:14,730
Vì vậy, giá trị trung bình của bạn ở đây
là ít hơn những gì chúng ta muốn.

761
00:32:14,730 --> 00:32:17,202
Vì vậy, chúng tôi muốn đi
phía bên phải của mảng của chúng tôi.

762
00:32:17,202 --> 00:32:18,910
Vì vậy, chúng ta sẽ
cập nhật ràng buộc thấp hơn của chúng tôi.

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

764
00:32:20,210 --> 00:32:23,020
Vì vậy, chúng tôi sẽ phân công lại thấp hơn của chúng tôi.

765
00:32:23,020 --> 00:32:25,221
Và điều gì làm bạn nghĩ thấp nên được?

766
00:32:25,221 --> 00:32:26,304
HỌC SINH: Giá trị trung?

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

768
00:32:27,446 --> 00:32:28,820
GIẢNG: Vì vậy, các value-- trung

769
00:32:28,820 --> 00:32:30,136
HỌC SINH: Plus 1.

770
00:32:30,136 --> 00:32:31,010
GIẢNG: --plus 1.

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

772
00:32:32,300 --> 00:32:34,380
Bất cứ ai có thể cho tôi biết tại sao
chúng tôi đã có cộng với 1?

773
00:32:34,380 --> 00:32:35,730
>> HỌC SINH: [? Không có giá trị?]
là bình đẳng hơn với nó.

774
00:32:35,730 --> 00:32:36,120
>> GIẢNG: Đúng vậy.

775
00:32:36,120 --> 00:32:38,661
Bởi vì chúng ta đã biết rằng
giá trị trung bình của chúng tôi không phải là bằng

776
00:32:38,661 --> 00:32:42,750
nó và chúng tôi muốn loại trừ nó
từ tất cả tìm kiếm tiếp theo.

777
00:32:42,750 --> 00:32:46,360
Nếu bạn quên rằng cộng với 1, điều này
sẽ giống như vòng lặp vô thời hạn.

778
00:32:46,360 --> 00:32:49,620
Và bạn sẽ chỉ được bắt gặp trong một
vòng lặp vô hạn và sau đó bạn sẽ segfault

779
00:32:49,620 --> 00:32:50,370
và những điều xấu đi.

780
00:32:50,370 --> 00:32:54,780
Vì vậy, luôn luôn đảm bảo rằng bạn không
bao gồm cả các giá trị mà bạn chỉ cần

781
00:32:54,780 --> 00:32:55,380
nhìn.

782
00:32:55,380 --> 00:32:58,530
Vì vậy, chúng tôi chăm sóc đó với một cộng thêm 1.

783
00:32:58,530 --> 00:33:04,840
>> Vì vậy, bây giờ chúng tôi có điều kiện cuối cùng của chúng tôi
mà tôi luôn luôn vì lợi ích an toàn

784
00:33:04,840 --> 00:33:12,664
bạn có thể kiểm tra ở đây, hoặc nếu giá trị tại
giữa là lớn hơn giá trị

785
00:33:12,664 --> 00:33:13,163
chúng ta muốn.

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

787
00:33:16,260 --> 00:33:20,230
Điều đó có nghĩa rằng chúng ta muốn
Mặt nửa trái.

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

789
00:33:21,350 --> 00:33:23,260
Vì vậy, mà một trong những chúng tôi sẽ cập nhật?

790
00:33:23,260 --> 00:33:23,760
Thượng.

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

792
00:33:25,470 --> 00:33:26,970
Và điều này sẽ tương đương là gì?

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

794
00:33:31,630 --> 00:33:33,690
Trung trừ đi 1 bởi vì,
Tất nhiên, chúng tôi muốn

795
00:33:33,690 --> 00:33:38,370
để đảm bảo rằng chúng tôi không
nhìn vào đó giá trị trung bình một lần nữa.

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

797
00:33:41,830 --> 00:33:45,110
Và sau đó chúng tôi có nó.

798
00:33:45,110 --> 00:33:45,610
Có bấy nhiêu thôi.

799
00:33:45,610 --> 00:33:46,820
Đó là tất cả tìm kiếm nhị phân là.

800
00:33:46,820 --> 00:33:48,190
Nó không phải là xấu, phải không?

801
00:33:48,190 --> 00:33:51,590
Nó giống như 10 dòng
mã với không gian trắng.

802
00:33:51,590 --> 00:33:57,510
Vì vậy, rất mạnh mẽ, rất hữu ích, bạn sẽ
được sử dụng nó trong một trong psets sau này của bạn.

803
00:33:57,510 --> 00:33:59,360
Có lẽ không phải thế này, nhưng sau đó.

804
00:33:59,360 --> 00:34:00,670
Vì vậy, tìm hiểu nó.

805
00:34:00,670 --> 00:34:01,510
Tình yêu nó.

806
00:34:01,510 --> 00:34:02,980
Nó sẽ đối xử với bạn tốt.

807
00:34:02,980 --> 00:34:05,370
Vì vậy, không ai có bất cứ
câu hỏi về tìm kiếm nhị phân?

808
00:34:05,370 --> 00:34:06,196
Vâng.

809
00:34:06,196 --> 00:34:09,840
>> HỌC SINH: Có vấn đề gì
dù n của bạn là chẵn hay lẻ?

810
00:34:09,840 --> 00:34:10,750
>> GIẢNG: số

811
00:34:10,750 --> 00:34:18,150
Bởi vì chúng tôi bỏ nó vào giữa như
một int, nó sẽ chỉ cắt nó.

812
00:34:18,150 --> 00:34:21,600
Vì vậy, nó sẽ ở lại một số nguyên và nó sẽ
cuối cùng sắp xếp thông qua tất cả mọi thứ.

813
00:34:21,600 --> 00:34:23,909
Vì vậy, bạn không phải lo lắng về điều đó.

814
00:34:23,909 --> 00:34:24,580
Tất cả mọi người tốt?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Tuyệt vời.

817
00:34:26,850 --> 00:34:27,919
Cool.

818
00:34:27,919 --> 00:34:30,836
Vì vậy, các bạn đã nhận điều này.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Slideshow.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
Vì vậy, như chúng tôi đã nói về, tôi biết
David đề cập runtimes phức tạp.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Vì vậy, trong trường hợp tốt nhất, nó chỉ là
một, mà chúng ta gọi là hằng số thời gian.

825
00:34:50,340 --> 00:34:51,909
Bất cứ ai có thể cho tôi biết lý do tại sao mà có thể được?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Loại kịch bản đó sẽ đòi hỏi?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> HỌC SINH: [không nghe được] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
GIẢNG: Vì vậy, giữa là
Yếu tố đầu tiên mà chúng tôi đến, phải không?

833
00:35:03,830 --> 00:35:08,167
Vì vậy, hoặc một mảng của một hoặc
bất cứ điều gì chúng ta đang tìm kiếm chỉ

834
00:35:08,167 --> 00:35:09,750
sẽ xảy ra là smack thoa ở giữa.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Vì vậy, đó là trường hợp tốt nhất của chúng tôi.

837
00:35:13,380 --> 00:35:17,540
Bạn nhận được vào vấn đề thực sự, có lẽ không
sẽ đạt tới [không nghe được] thường.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Những gì về trường hợp tồi tệ nhất của chúng tôi?

840
00:35:19,750 --> 00:35:21,270
Trường hợp xấu nhất của chúng tôi là log n.

841
00:35:21,270 --> 00:35:25,360
Và điều đó đã làm với toàn bộ
quyền hạn của hai điều mà tôi đã nói.

842
00:35:25,360 --> 00:35:30,930
>> Vì vậy, trong trường hợp xấu nhất nó sẽ có nghĩa
mà chúng tôi đã để cắt các mảng xuống

843
00:35:30,930 --> 00:35:33,270
cho đến khi nó là một phần tử của một.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Vì vậy, chúng tôi phải đốn chặt nó xuống một nửa
nhiều lần chúng tôi có thể có thể.

846
00:35:38,930 --> 00:35:41,430
Đó là lý do tại sao nó log n vì
bạn chỉ cần tiếp tục phân chia bởi hai.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Vì vậy, giả định, mọi thứ bạn
cần phải biết nếu bạn đã từng

849
00:35:45,830 --> 00:35:48,050
sẽ sử dụng tìm kiếm nhị phân.

850
00:35:48,050 --> 00:35:50,680
Các yếu tố của bạn phải được sắp xếp.

851
00:35:50,680 --> 00:35:53,890
Họ phải được sắp xếp bởi vì
đó là cách duy nhất bạn

852
00:35:53,890 --> 00:35:57,060
có thể biết nếu bạn có thể
để ném ra một nửa của nó.

853
00:35:57,060 --> 00:36:00,260
>> Nếu bạn có túi lộn xộn này
các con số và bạn đang nói,

854
00:36:00,260 --> 00:36:05,380
OK, tôi sẽ kiểm tra giữa
số lượng và số lượng tôi đang tìm kiếm

855
00:36:05,380 --> 00:36:08,510
là ít hơn, tôi chỉ cần đi
tự ý ném ra một nửa.

856
00:36:08,510 --> 00:36:11,130
Bạn sẽ không biết nếu bạn
trong số đó một nửa khác.

857
00:36:11,130 --> 00:36:12,655
Danh sách của bạn đã được sắp xếp.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Cũng như vậy, điều này có thể
đi về phía trước một chút,

860
00:36:16,560 --> 00:36:18,360
nhưng bạn cần phải có quyền truy cập ngẫu nhiên.

861
00:36:18,360 --> 00:36:21,940
Bạn cần để có thể chỉ
đi đến đó yếu tố trung.

862
00:36:21,940 --> 00:36:25,110
Nếu bạn phải đi qua
thông qua một cái gì đó

863
00:36:25,110 --> 00:36:28,630
hoặc nó sẽ đưa bạn thêm bước
để có được yếu tố đó giữa,

864
00:36:28,630 --> 00:36:31,750
nó không phải đăng nhập nữa vì n
bạn đang thêm nhiều công việc hơn vào nó.

865
00:36:31,750 --> 00:36:34,800
Và điều này sẽ làm cho một ít
ý nghĩa hơn trong hai tuần,

866
00:36:34,800 --> 00:36:37,950
nhưng tôi chỉ loại muốn lời nói đầu,
cung cấp cho các bạn một ý tưởng về những gì

867
00:36:37,950 --> 00:36:38,999
tới.

868
00:36:38,999 --> 00:36:40,790
Nhưng những người là hai
giả định quan trọng

869
00:36:40,790 --> 00:36:44,804
mà bạn cần cho một danh sách nhị phân.

870
00:36:44,804 --> 00:36:45,720
Hãy chắc chắn rằng nó được sắp xếp.

871
00:36:45,720 --> 00:36:47,920
Đó là một lớn đối với
các bạn ngay bây giờ.

872
00:36:47,920 --> 00:36:52,170
Và ngày đó chúng ta có thể đi vào
phần còn lại của các loại của chúng tôi.

873
00:36:52,170 --> 00:36:56,444
Vì vậy, bốn bong bóng sorts--,
chèn, lựa chọn, và hợp nhất.

874
00:36:56,444 --> 00:36:57,485
Họ là tất cả các loại mát mẻ.

875
00:36:57,485 --> 00:37:02,860
Nếu các bạn quyết định đi CS 124,
bạn sẽ tìm hiểu về tất cả các loại của các loại.

876
00:37:02,860 --> 00:37:07,575
Và nếu bạn là một fan hâm mộ XKCD, có
là về truyện tranh thực sự mát mẻ

877
00:37:07,575 --> 00:37:11,530
giống như các loại thực sự không hiệu quả, mà tôi
khuyên bạn nên bạn sẽ xem xét.

878
00:37:11,530 --> 00:37:16,170
Một trong số họ là như hoảng loạn sắp xếp, mà
là như thế, oh không, trở về mảng ngẫu nhiên.

879
00:37:16,170 --> 00:37:16,991
Hệ thống Shutdown.

880
00:37:16,991 --> 00:37:17,490
Để lại.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Vì vậy, sự hài hước geeky là luôn luôn tốt.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Vì vậy, không ai nhớ loại
giống như chỉ là một ý tưởng chung

885
00:37:25,750 --> 00:37:27,810
làm thế nào bong bóng sắp xếp hoạt động.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Bạn có nhớ không?

888
00:37:32,155 --> 00:37:32,755
>> HỌC SINH: Yeah.

889
00:37:32,755 --> 00:37:33,970
>> GIẢNG: Go cho nó.

890
00:37:33,970 --> 00:37:38,980
>> SINH VIÊN: Vì vậy, bạn đang trải qua và
nếu nó lớn hơn, sau đó bạn trao đổi hai.

891
00:37:38,980 --> 00:37:39,820
>> GIẢNG: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Chính xác.

893
00:37:40,564 --> 00:37:41,730
Vì vậy, bạn chỉ cần lặp qua.

894
00:37:41,730 --> 00:37:43,050
Bạn hãy kiểm tra hai con số.

895
00:37:43,050 --> 00:37:46,510
Nếu một trước khi lớn
hơn một sau đó,

896
00:37:46,510 --> 00:37:50,230
bạn chỉ cần trao đổi chúng vì vậy mà trong
cách này tất cả các con số cao hơn

897
00:37:50,230 --> 00:37:54,990
bong bóng lên vào cuối danh sách
và tất cả các con số thấp hơn bong bóng xuống.

898
00:37:54,990 --> 00:37:59,355
>> Anh ấy đã cho mọi người thấy mát mẻ
hiệu ứng âm thanh phân loại video?

899
00:37:59,355 --> 00:38:00,480
Đó là loại mát mẻ.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Vì vậy, như Robert vừa nói, thuật toán
mà bạn chỉ cần bước qua danh sách,

902
00:38:05,200 --> 00:38:07,930
trao đổi các giá trị liền kề
nếu họ không theo thứ tự.

903
00:38:07,930 --> 00:38:10,975
Và sau đó chỉ cần giữ lặp đi lặp lại
cho đến khi bạn không thực hiện bất kỳ giao dịch hoán đổi.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Vì vậy, không xấu, phải không?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Vì vậy, chúng tôi chỉ có một ví dụ nhanh chóng ở đây.

908
00:38:16,319 --> 00:38:18,360
Vì vậy, điều này sẽ sắp xếp
chúng trong thứ tự tăng dần.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Vì vậy, khi chúng tôi đi qua đầu tiên
thời gian, chúng tôi xem xét thông qua tám

911
00:38:23,470 --> 00:38:26,880
và sáu rõ ràng không phải
theo thứ tự, chúng tôi trao đổi chúng.

912
00:38:26,880 --> 00:38:27,985
>> Vì vậy, nhìn vào kế tiếp.

913
00:38:27,985 --> 00:38:29,430
Tám và bốn không theo thứ tự.

914
00:38:29,430 --> 00:38:30,450
Trao đổi chúng.

915
00:38:30,450 --> 00:38:32,530
Và sau đó tám và hai, trao đổi chúng.

916
00:38:32,530 --> 00:38:33,470
Hiện chúng tôi đi.

917
00:38:33,470 --> 00:38:39,519
Vì vậy, vượt qua đầu tiên của bạn sau khi bạn
biết rằng số lượng lớn nhất của bạn

918
00:38:39,519 --> 00:38:41,810
là có được tất cả các cách
ở phía trên bởi vì nó chỉ

919
00:38:41,810 --> 00:38:44,210
sẽ liên tục
lớn hơn mọi thứ khác

920
00:38:44,210 --> 00:38:46,810
và nó chỉ cần đi để bong bóng
lên tất cả các cách để kết thúc ở đó.

921
00:38:46,810 --> 00:38:48,226
Điều đó có ý nghĩa với tất cả mọi người?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Cool.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Vì vậy, sau đó chúng ta nhìn qua thứ hai của chúng tôi.

926
00:38:53,920 --> 00:38:54,980
Sáu và bốn, chuyển đổi.

927
00:38:54,980 --> 00:38:55,920
Sáu và thứ hai, chuyển đổi.

928
00:38:55,920 --> 00:38:58,700
Và bây giờ chúng tôi có một vài điều theo thứ tự.

929
00:38:58,700 --> 00:39:02,240
Vì vậy, cho mỗi đường chuyền mà chúng ta
thực hiện thông qua toàn bộ danh sách của chúng tôi,

930
00:39:02,240 --> 00:39:06,320
chúng ta biết rằng như thế nhiều số
cuối cùng sẽ được sắp xếp.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Vì vậy, chúng tôi làm một vượt qua thứ ba,
đó là một trong trao đổi.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
Và sau đó vào thứ tư của chúng tôi
vượt qua, chúng tôi đã không khe.

935
00:39:15,910 --> 00:39:18,570
Và vì vậy chúng tôi biết rằng chúng tôi
mảng đã được sắp xếp.

936
00:39:18,570 --> 00:39:20,900
>> Và đó là lớn
điều với bong bóng sắp xếp.

937
00:39:20,900 --> 00:39:23,720
Chúng ta biết rằng khi chúng ta
có không hoán đổi, mà

938
00:39:23,720 --> 00:39:26,497
có nghĩa là tất cả mọi thứ
là để hoàn tất.

939
00:39:26,497 --> 00:39:27,580
Đó là loại như thế nào chúng tôi kiểm tra.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Vì vậy, chúng tôi cũng sẽ mã bong bóng
loại mà cũng không phải là xấu.

942
00:39:36,480 --> 00:39:38,120
Không ai trong số này là xấu.

943
00:39:38,120 --> 00:39:40,210
Tôi biết họ có thể có vẻ một chút đáng sợ.

944
00:39:40,210 --> 00:39:42,124
Tôi biết khi tôi lấy
lớp học, ngay cả khi tôi

945
00:39:42,124 --> 00:39:44,290
đang dạy lớp cho
lần đầu tiên vào năm ngoái,

946
00:39:44,290 --> 00:39:46,165
Tôi đã như thế, làm thế nào để làm điều này?

947
00:39:46,165 --> 00:39:48,540
Nó có ý nghĩa về mặt lý thuyết, nhưng
làm thế nào để chúng tôi thực sự làm điều này?

948
00:39:48,540 --> 00:39:51,420
Đó là lý do tại sao tôi cũng muốn đi bộ
thông qua các mã với các bạn ở đây.

949
00:39:51,420 --> 00:39:54,915
Vì vậy, tôi có một giả
cho các bạn thời gian này.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Vì vậy, chỉ giữ điều này trong tâm trí như
chúng tôi sắp chuyển qua.

952
00:39:58,970 --> 00:40:04,210
Vì vậy, chúng tôi có một số truy cập mà
theo dõi giao dịch hoán đổi của chúng tôi,

953
00:40:04,210 --> 00:40:08,370
bởi vì chúng tôi cần phải chắc chắn
rằng chúng tôi đang kiểm tra đó.

954
00:40:08,370 --> 00:40:11,830
Và chúng ta lặp toàn bộ mảng
như chúng ta chỉ cần làm với ví dụ này.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Nếu phần tử trước lớn hơn
các yếu tố sau, nơi chúng tôi đang ở,

957
00:40:17,325 --> 00:40:20,760
chúng tôi trao đổi chúng và chúng tôi tăng của chúng tôi
truy cập bởi vì ngay khi chúng tôi trao đổi,

958
00:40:20,760 --> 00:40:23,850
chúng tôi muốn cho truy cập của chúng tôi biết điều đó.

959
00:40:23,850 --> 00:40:26,247
Bất kỳ câu hỏi đó?

960
00:40:26,247 --> 00:40:27,580
Một cái gì đó có vẻ buồn cười ở đây.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
HỌC SINH: Bạn thiết lập các truy cập đến số không
mỗi khi bạn đi qua các vòng lặp?

963
00:40:32,350 --> 00:40:34,339
Không bạn tiếp tục đi
trở lại bằng không mỗi lần?

964
00:40:34,339 --> 00:40:35,505
GIẢNG: Không nhất thiết.

965
00:40:35,505 --> 00:40:39,710
Vì vậy, những gì xảy ra là chúng tôi đi qua ở đây.

966
00:40:39,710 --> 00:40:43,830
Vì vậy, thời gian, hãy nhớ, đây
sẽ thực hiện một lần mà không thất bại.

967
00:40:43,830 --> 00:40:46,480
Vì vậy, nó sẽ thiết lập
truy cập bằng không,

968
00:40:46,480 --> 00:40:48,070
sau đó nó sẽ lặp qua.

969
00:40:48,070 --> 00:40:50,590
Khi nó lặp thông qua,
nó sẽ cập nhật truy cập.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Khi nó cập nhật truy cập, khi nó được thực hiện,
khi nó đạt đến kết thúc của mảng,

972
00:40:56,900 --> 00:41:00,830
nếu danh sách của chúng tôi đã không được sắp xếp,
truy cập sẽ được cập nhật.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Vì vậy, sau đó nó sẽ kiểm tra điều kiện và nó
nói, OK, là truy cập lớn hơn không.

975
00:41:07,150 --> 00:41:09,290
Nếu có, làm điều đó một lần nữa.

976
00:41:09,290 --> 00:41:14,340
Bạn muốn thiết lập lại để khi bạn
đi qua, đếm bằng số không.

977
00:41:14,340 --> 00:41:18,240
Nếu bạn đi qua một sắp xếp
mảng, không có gì thay đổi,

978
00:41:18,240 --> 00:41:21,355
điều này không, và bạn
trở về danh sách được sắp xếp.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Điều đó làm cho tinh thần?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
HỌC SINH: Nó có thể trong một chút.

983
00:41:26,356 --> 00:41:27,147
GIẢNG: OK.

984
00:41:27,147 --> 00:41:28,980
Nếu có bất kỳ khác
câu hỏi mà đi lên.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Vâng.

987
00:41:30,680 --> 00:41:33,760
>> HỌC SINH: Điều gì sẽ chức năng
là để trao đổi các yếu tố?

988
00:41:33,760 --> 00:41:36,900
>> GIẢNG: Vì vậy, chúng tôi thực sự có thể viết
rằng nếu chúng ta đang đi sang phải bây giờ.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Cool.

991
00:41:38,300 --> 00:41:42,155
Vì vậy, trên lưu ý rằng, Alison sẽ
chuyển đổi trở lại thiết bị.

992
00:41:42,155 --> 00:41:43,080
Nó sẽ được vui vẻ.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
Và chúng tôi có đẹp của chúng tôi
bong bóng sắp xếp điều ở đây.

995
00:41:47,390 --> 00:41:50,800
Vì vậy, tôi đã làm xe đạp
thông qua mảng.

996
00:41:50,800 --> 00:41:53,030
Chúng tôi có giao dịch hoán đổi của chúng tôi
là bằng không.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Vì vậy, chúng tôi muốn trao đổi liền kề
yếu tố nếu họ ra lệnh.

999
00:41:58,440 --> 00:42:03,020
Vì vậy, điều đầu tiên chúng ta cần phải
làm là lặp qua mảng của chúng tôi.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Vì vậy, làm thế nào để bạn nghĩ rằng chúng ta có thể
lặp qua mảng của chúng tôi?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Chúng tôi có cho và i bằng 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Chúng tôi muốn tôi là ít
hơn n trừ đi 1 trừ đi k.

1006
00:42:22,454 --> 00:42:23,870
Và tôi sẽ giải thích rằng trong một giây.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Vì vậy, đây là một tối ưu hóa ở đây, nơi,
nhớ làm thế nào tôi đã nói mỗi đường chuyền sau

1009
00:42:32,830 --> 00:42:36,655
thông qua các mảng chúng tôi
biết rằng bất cứ điều gì on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Vì vậy, một đường chuyền sau khi chúng tôi
biết rằng điều này đã được sắp xếp.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Sau khi hai qua chúng ta đã biết
rằng tất cả điều này được sắp xếp.

1014
00:42:50,060 --> 00:42:52,750
Sau khi ba đi chúng tôi
biết đó là sắp xếp.

1015
00:42:52,750 --> 00:42:55,620
Vì vậy, cách tôi đang lặp lại
qua mảng ở đây,

1016
00:42:55,620 --> 00:43:01,090
là nó làm cho chắc chắn chỉ đi
thông qua những gì chúng ta biết là không được phân loại.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Đó chỉ là một tối ưu hóa.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Bạn có thể viết nó ngây thơ chỉ
lặp qua tất cả mọi thứ,

1021
00:43:08,210 --> 00:43:09,970
nó sẽ chỉ mất nhiều thời gian.

1022
00:43:09,970 --> 00:43:12,470
Với vòng bốn này nó
chỉ là một tối ưu hóa đẹp

1023
00:43:12,470 --> 00:43:18,460
bởi vì chúng ta biết rằng sau mỗi lần đầy đủ
lặp qua mảng ở đây,

1024
00:43:18,460 --> 00:43:24,050
như mỗi vòng lặp đầy đủ ở đây, chúng ta biết
rằng một trong nhiều các yếu tố

1025
00:43:24,050 --> 00:43:25,760
sẽ được sắp xếp ở cuối.

1026
00:43:25,760 --> 00:43:28,294
>> Vì vậy, chúng tôi không phải lo lắng về những người.

1027
00:43:28,294 --> 00:43:29,710
Điều đó có ý nghĩa với tất cả mọi người?

1028
00:43:29,710 --> 00:43:30,950
Đó là mẹo nhỏ mát mẻ?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Vì vậy, trong trường hợp đó, nếu
chúng ta đang lặp lại thông qua,

1031
00:43:37,270 --> 00:43:50,590
chúng tôi biết rằng chúng tôi muốn kiểm tra xem
mảng n và n + 1 là theo thứ tự.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Vì vậy, đây là giả.

1035
00:43:54,600 --> 00:43:57,540
Chúng tôi muốn kiểm tra xem mảng n
và n + 1 là theo thứ tự.

1036
00:43:57,540 --> 00:43:59,520
Vì vậy, những gì chúng ta có thể có ở đó?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Nó sẽ có một số điều kiện.

1039
00:44:03,120 --> 00:44:04,220
Nó sẽ là một nếu.

1040
00:44:04,220 --> 00:44:07,066
>> HỌC SINH: Nếu mảng n là
ít hơn mảng n + 1.

1041
00:44:07,066 --> 00:44:07,816
GIẢNG: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Vâng, nhỏ hơn hoặc lớn hơn.

1044
00:44:10,699 --> 00:44:11,615
HỌC SINH: Lớn hơn.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Sau đó, chúng tôi muốn trao đổi chúng.

1047
00:44:17,620 --> 00:44:18,570
Chính xác.

1048
00:44:18,570 --> 00:44:23,570
Vì vậy, bây giờ chúng tôi nhận được vào những gì là
cơ chế trao đổi chúng?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Vì vậy, chúng tôi đã đi qua một thời gian ngắn,
một loại chức năng trao đổi tuần trước.

1051
00:44:28,137 --> 00:44:29,595
Có ai nhớ nó như thế nào làm việc?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Vì vậy, chúng ta không thể gán cho họ, phải không?

1054
00:44:34,950 --> 00:44:36,640
Bởi vì một trong số họ sẽ bị mất.

1055
00:44:36,640 --> 00:44:41,696
Nếu chúng ta nói A là bằng B và sau đó B
bằng A, tất cả đột nhiên cả hai

1056
00:44:41,696 --> 00:44:43,150
chỉ bằng B.

1057
00:44:43,150 --> 00:44:45,720
>> Vì vậy, những gì chúng ta phải làm là chúng tôi
có một biến tạm thời đó là

1058
00:44:45,720 --> 00:44:49,055
sẽ tổ chức một trong những khi chúng ta
chúng tôi trong quá trình trao đổi.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Vì vậy, những gì chúng tôi có là chúng tôi sẽ có một số int
tạm thời bằng đối với: bạn có thể gán cho nó

1061
00:44:56,464 --> 00:44:59,130
để bất cứ một trong những bạn muốn, chỉ cần
chắc chắn rằng bạn theo dõi it--

1062
00:44:59,130 --> 00:45:01,840
vậy trong trường hợp này, tôi sẽ
gán nó vào mảng n + 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Vì vậy, đó là sẽ giữ bất cứ điều gì
giá trị trong đó khối thứ hai

1065
00:45:07,674 --> 00:45:08,590
mà chúng ta đang tìm kiếm.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> Và sau đó chúng ta có thể làm là chúng ta có thể đi
trước và mảng phân công lại n + 1,

1068
00:45:13,240 --> 00:45:14,990
bởi vì chúng tôi biết chúng tôi
có giá trị lưu trữ.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Đây cũng là một trong những lớn
things-- Tôi không biết nếu có của bạn

1071
00:45:19,270 --> 00:45:23,780
có vấn đề mà nếu bạn chuyển đổi hai
dòng mã đột nhiên mọi thứ làm việc.

1072
00:45:23,780 --> 00:45:25,880
Trật tự là rất quan trọng trong CS.

1073
00:45:25,880 --> 00:45:29,450
Vì vậy, hãy chắc chắn rằng bạn sơ đồ
những điều trên nếu có thể

1074
00:45:29,450 --> 00:45:31,230
như những gì đang thực sự xảy ra.

1075
00:45:31,230 --> 00:45:34,256
Vì vậy, bây giờ chúng tôi đang đi để
phân công lại mảng n + 1,

1076
00:45:34,256 --> 00:45:36,005
bởi vì chúng tôi biết chúng tôi
có giá trị lưu trữ.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> Và chúng ta có thể gán vào mảng
n hoặc trong trường hợp này mảng i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Quá nhiều biến.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Vì vậy, bây giờ chúng tôi đã bố trí mảng i
cộng thêm 1 để bằng những gì trong mảng i.

1084
00:46:01,500 --> 00:46:08,240
Và bây giờ chúng ta có thể quay trở lại và
gán mảng tôi những gì?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Bất cứ ai?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> HỌC SINH: 10.

1089
00:46:14,010 --> 00:46:14,680
>> GIẢNG: 10.

1090
00:46:14,680 --> 00:46:15,180
Chính xác.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
Và một điều cuối cùng.

1093
00:46:18,640 --> 00:46:21,840
Nếu chúng ta đã trao đổi nó bây giờ,
những gì chúng ta cần phải làm gì?

1094
00:46:21,840 --> 00:46:23,740
Một điều gì
đó là sẽ để cho chúng tôi

1095
00:46:23,740 --> 00:46:27,542
nếu chúng ta bao giờ chấm dứt chương trình này?

1096
00:46:27,542 --> 00:46:29,250
Những gì cho chúng ta biết rằng chúng ta
có một danh sách được sắp xếp?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Nếu chúng ta không thực hiện bất kỳ giao dịch hoán đổi, phải không?

1099
00:46:33,750 --> 00:46:36,900
Nếu giao dịch hoán đổi bằng
zero vào cuối này.

1100
00:46:36,900 --> 00:46:42,975
Vì vậy, bất cứ khi nào bạn thực hiện một trao đổi, như chúng tôi
chỉ cần làm ở đây, chúng tôi muốn cập nhật giao dịch hoán đổi.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
Và tôi biết có một
câu hỏi trước đó về có thể bạn

1103
00:46:47,210 --> 00:46:49,689
sử dụng không có hoặc có một thay vì
của đúng hay sai.

1104
00:46:49,689 --> 00:46:50,980
Và đó là điều này không có gì ở đây.

1105
00:46:50,980 --> 00:46:52,750
Vì vậy, điều này nói nếu không giao dịch hoán đổi.

1106
00:46:52,750 --> 00:47:01,310
Vì vậy, nếu giao dịch hoán đổi là số không, mà tôi luôn luôn is--
được sự thật của tôi và falses của tôi lẫn lộn.

1107
00:47:01,310 --> 00:47:03,960
Chúng tôi muốn chúng tôi đánh giá
đúng sự thật và nó không phải.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Vì vậy, nếu nó không, thì đó là sai.

1110
00:47:09,630 --> 00:47:12,560
Nếu bạn phủ nhận nó với một
[? đập?] nó trở thành sự thật.

1111
00:47:12,560 --> 00:47:13,975
Vì vậy, sau đó dòng này thực hiện.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Chân lý và sai lầm và
số không và những người nhận được điên.

1114
00:47:17,370 --> 00:47:20,690
Chỉ cần nếu bạn từ từ đi bộ
thông qua đó nó sẽ có ý nghĩa.

1115
00:47:20,690 --> 00:47:23,320
Nhưng đó là những gì nhỏ này
bit mã ở đây không.

1116
00:47:23,320 --> 00:47:26,490
Vì vậy, đây sẽ kiểm tra xem
Chúng ta đã thực hiện bất kỳ giao dịch hoán đổi.

1117
00:47:26,490 --> 00:47:30,054
Vì vậy, nếu đó là bất cứ điều gì ngoài
bằng không, nó sẽ là sai lầm

1118
00:47:30,054 --> 00:47:31,970
và toàn bộ điều là
sẽ thực hiện một lần nữa.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Mát mẻ?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> HỌC SINH: không nghỉ làm gì?

1123
00:47:36,000 --> 00:47:38,990
>> GIẢNG: Phá vỡ chỉ
phá vỡ bạn ra khỏi vòng lặp.

1124
00:47:38,990 --> 00:47:41,570
Vì vậy, trong trường hợp này nó sẽ
chỉ muốn kết thúc chương trình

1125
00:47:41,570 --> 00:47:43,828
và bạn sẽ chỉ
có danh sách được sắp xếp của bạn.

1126
00:47:43,828 --> 00:47:44,536
HỌC SINH: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
GIẢNG: Tôi xin lỗi?

1129
00:47:49,010 --> 00:47:52,110
SINH VIÊN: Bởi vì trước đây chúng tôi
được sử dụng bằng văn bản 1 hơn bằng văn bản không

1130
00:47:52,110 --> 00:47:54,170
trình bày rằng nếu
mà sẽ làm việc hay không.

1131
00:47:54,170 --> 00:47:54,878
>> GIẢNG: Yeah.

1132
00:47:54,878 --> 00:47:56,410
Vì vậy, bạn có thể trở lại không hay 1.

1133
00:47:56,410 --> 00:47:58,950
Trong trường hợp này, bởi vì chúng tôi không thực sự
làm bất cứ điều gì với chức năng,

1134
00:47:58,950 --> 00:48:00,150
chúng tôi chỉ muốn nó để phá vỡ.

1135
00:48:00,150 --> 00:48:02,680
Chúng tôi không thực sự quan tâm về nó.

1136
00:48:02,680 --> 00:48:06,960
Phanh cũng tốt nếu
nó được sử dụng để phá vỡ ra

1137
00:48:06,960 --> 00:48:10,710
của bốn tuyến hoặc điều kiện
bạn không muốn tiếp tục thực hiện.

1138
00:48:10,710 --> 00:48:12,110
Nó chỉ đưa bạn ra khỏi chúng.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Đó là một chút của một điều sắc thái.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Tôi cảm thấy như có
rất nhiều tay vẫy,

1143
00:48:18,445 --> 00:48:19,740
như bạn sẽ tìm hiểu về điều này sớm.

1144
00:48:19,740 --> 00:48:20,955
>> Nhưng bạn sẽ tìm hiểu về điều này sớm.

1145
00:48:20,955 --> 00:48:21,500
Tôi hứa.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Vì vậy, không tất cả mọi người có được bong bóng sắp xếp?

1149
00:48:24,840 --> 00:48:25,550
Không quá xấu.

1150
00:48:25,550 --> 00:48:31,910
Lặp thông qua, trao đổi việc sử dụng một
biến temp, và tất cả chúng ta thiết lập ở đó?

1151
00:48:31,910 --> 00:48:32,960
Cool.

1152
00:48:32,960 --> 00:48:34,080
Tuyệt vời.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Quay lại PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Bất kỳ câu hỏi nói chung
về những cho đến nay?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Cool.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> HỌC SINH: [không nghe được] int chính thường.

1162
00:48:45,279 --> 00:48:46,695
Bạn phải có mà cho điều này?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> GIẢNG: Vì vậy, chúng tôi chỉ tìm kiếm
chỉ tại các thuật toán phân loại thực tế.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Nếu bạn đã có nó trong vòng
giống như một chương trình lớn hơn,

1167
00:48:56,350 --> 00:48:57,891
bạn sẽ có một nơi nào đó chính int.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Tùy thuộc vào nơi bạn
sử dụng thuật toán này,

1170
00:49:02,880 --> 00:49:05,860
nó sẽ xác định những gì
được trả về bởi nó.

1171
00:49:05,860 --> 00:49:09,960
Nhưng đối với trường hợp của chúng tôi, chúng tôi nghiêm chỉnh
nhìn vào cách thực hiện điều này thực sự

1172
00:49:09,960 --> 00:49:11,300
lặp thông qua một mảng.

1173
00:49:11,300 --> 00:49:12,570
Vì vậy, chúng tôi không lo lắng về nó.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Vì vậy, chúng ta đang nói về trường hợp tốt nhất và
tình huống xấu nhất cho tìm kiếm nhị phân.

1176
00:49:19,830 --> 00:49:22,470
Vì vậy, nó cũng quan trọng để làm
rằng đối với mỗi loại của chúng tôi.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Vì vậy, những gì bạn nghĩ là tồi tệ nhất
trường hợp thời gian chạy của bong bóng sắp xếp?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Các bạn nhớ không?

1181
00:49:30,700 --> 00:49:31,784
>> HỌC SINH: N trừ 1.

1182
00:49:31,784 --> 00:49:32,700
GIẢNG: N trừ 1.

1183
00:49:32,700 --> 00:49:35,070
Vì vậy, đó có nghĩa là có
n trừ đi 1 so sánh.

1184
00:49:35,070 --> 00:49:40,060
Vì vậy, một điều nhận ra là
mà trên phiên đầu tiên,

1185
00:49:40,060 --> 00:49:43,360
chúng tôi đi qua, chúng ta so sánh
các two-- vì vậy đó là 1.

1186
00:49:43,360 --> 00:49:46,685
Hai, ba, bốn.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Vì vậy, sau một lần lặp chúng tôi
đã có bốn so sánh.

1189
00:49:55,050 --> 00:49:58,230
Khi tôi đang nói về thời gian chạy và n.

1190
00:49:58,230 --> 00:50:04,680
N đại diện cho số lượng so sánh
như một chức năng của bao nhiêu yếu tố

1191
00:50:04,680 --> 00:50:05,570
chúng tôi có.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Vì vậy, chúng tôi đi qua, chúng tôi có bốn.

1194
00:50:08,860 --> 00:50:11,780
Thời gian tiếp theo bạn biết chúng tôi không
phải chăm sóc này.

1195
00:50:11,780 --> 00:50:15,140
Chúng tôi so sánh hai,
hai, hai,

1196
00:50:15,140 --> 00:50:20,050
và nếu chúng ta không có tối ưu hóa
với các vòng lặp bốn mà tôi đã viết,

1197
00:50:20,050 --> 00:50:22,750
bạn sẽ được so sánh ở đây anyways.

1198
00:50:22,750 --> 00:50:26,170
Vì vậy, bạn sẽ phải
chạy qua mảng

1199
00:50:26,170 --> 00:50:34,380
và thực hiện so sánh n n
lần, bởi vì mỗi lần chúng tôi

1200
00:50:34,380 --> 00:50:36,670
chạy qua nó we loại một điều.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> Và mỗi khi chúng ta chạy qua
mảng, chúng tôi làm n so sánh.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Vì vậy, thời gian chạy của chúng tôi cho điều này là
thực sự n bình phương, mà

1205
00:50:46,330 --> 00:50:48,400
là tồi tệ hơn trong của chúng tôi
cuối vì đó đăng nhập

1206
00:50:48,400 --> 00:50:51,965
có nghĩa là nếu chúng ta có bốn
tỷ yếu tố, đó là

1207
00:50:51,965 --> 00:50:55,260
sẽ đưa chúng ta bốn tỷ
bình phương thay vì 32.

1208
00:50:55,260 --> 00:51:01,240
Vì vậy, không phải là thời gian chạy tốt nhất,
nhưng đối với một số điều,

1209
00:51:01,240 --> 00:51:04,610
bạn đã biết, nếu bạn đang trong vòng
một phạm vi nhất định của các yếu tố

1210
00:51:04,610 --> 00:51:06,540
bong bóng sắp xếp có thể là tốt để sử dụng.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Vì vậy, bây giờ là thời gian chạy trường hợp tốt nhất là gì?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
HỌC SINH: Zero?

1215
00:51:14,940 --> 00:51:16,420
Hay 1?

1216
00:51:16,420 --> 00:51:18,140
>> GIẢNG: 1 Vì vậy, sẽ
là một so sánh.

1217
00:51:18,140 --> 00:51:19,114
Phải.

1218
00:51:19,114 --> 00:51:20,002
>> HỌC SINH: N trừ 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> GIẢNG: Vì vậy, yeah.

1221
00:51:22,320 --> 00:51:22,990
Vì vậy, n trừ đi 1.

1222
00:51:22,990 --> 00:51:26,510
Bất cứ khi nào bạn có một khái niệm như n
trừ đi 1, chúng ta có xu hướng chỉ cần thả nó đi

1223
00:51:26,510 --> 00:51:31,680
và chúng tôi chỉ nói n bởi vì bạn có
để so sánh mỗi these-- mỗi cặp.

1224
00:51:31,680 --> 00:51:36,470
Vì vậy, nó sẽ là n trừ đi 1, mà chúng tôi
chúng tôi chỉ nói là khoảng n.

1225
00:51:36,470 --> 00:51:39,280
Khi bạn đang làm việc với thời gian chạy,
tất cả mọi thứ là trong xấp xỉ.

1226
00:51:39,280 --> 00:51:43,860
Miễn là các số mũ là
chính xác, bạn đang khá tốt.

1227
00:51:43,860 --> 00:51:45,700
>> Đó là cách chúng ta đối phó với nó.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Vì vậy, trường hợp tốt nhất là n, mà
có nghĩa là danh sách đã được sắp xếp,

1230
00:51:51,780 --> 00:51:54,320
và tất cả chúng tôi làm là chạy qua
và kiểm tra xem nó được sắp xếp.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Cool.

1233
00:51:56,855 --> 00:51:57,355
Được rồi.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Vì vậy, như bạn thấy ở đây, chúng tôi
chỉ có một số đồ thị hơn.

1236
00:52:01,920 --> 00:52:02,660
Vì vậy, n bình phương.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Fun.

1239
00:52:05,120 --> 00:52:09,730
Nhiều tồi tệ hơn n như chúng ta thấy, và
nhiều, tồi tệ hơn nhiều so với đăng nhập 2n.

1240
00:52:09,730 --> 00:52:12,060
Và sau đó bạn cũng nhận được vào các bản ghi log.

1241
00:52:12,060 --> 00:52:18,020
Và bạn có 124, bạn nhận được vào
như sao nhật ký, mà là giống như điên.

1242
00:52:18,020 --> 00:52:20,172
Vì vậy, nếu bạn quan tâm,
tra cứu sao log.

1243
00:52:20,172 --> 00:52:20,880
Đó là loại vui vẻ.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Vì vậy, chúng ta có biểu đồ này rất lớn.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Chỉ cần một người đứng đầu lên, một này
biểu đồ tuyệt vời để có

1248
00:52:28,720 --> 00:52:31,350
cho trung hạn của bạn bởi vì chúng tôi
thời gian để yêu cầu bạn những mỏng.

1249
00:52:31,350 --> 00:52:36,090
Vì vậy, chỉ là một người đứng đầu lên, có này của bạn
giữa kỳ về đẹp cheat sheet của bạn

1250
00:52:36,090 --> 00:52:36,616
có.

1251
00:52:36,616 --> 00:52:37,990
Vì vậy, chúng ta chỉ cần nhìn vào bong bóng sắp xếp.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Trường hợp xấu nhất, n bình phương, trường hợp tốt nhất, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
Và chúng ta sẽ nhìn vào những người khác.

1256
00:52:44,950 --> 00:52:47,940
>> Và như bạn có thể thấy, chỉ
một thực sự làm tốt

1257
00:52:47,940 --> 00:52:50,910
là sắp xếp hợp nhất, mà chúng tôi sẽ nhận được vào lý do tại sao.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Vì vậy, chúng ta sẽ đi đến
tiếp theo một lựa chọn loại here--.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Có ai nhớ làm thế nào
lựa chọn loại làm việc?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Đi cho nó.

1264
00:53:05,700 --> 00:53:08,210
>> HỌC SINH: Về cơ bản đi qua
một trật tự và tạo ra một danh sách mới.

1265
00:53:08,210 --> 00:53:11,001
Và cũng giống như bạn đang đặt yếu tố
trong, đặt chúng vào đúng vị trí

1266
00:53:11,001 --> 00:53:11,750
trong danh sách mới.

1267
00:53:11,750 --> 00:53:14,040
>> GIẢNG: Vì vậy, âm thanh
giống như sắp xếp chèn.

1268
00:53:14,040 --> 00:53:15,040
Nhưng bạn thực sự gần gũi.

1269
00:53:15,040 --> 00:53:15,915
Họ rất giống nhau.

1270
00:53:15,915 --> 00:53:17,440
Ngay cả khi tôi nhận được chúng lẫn lộn đôi khi.

1271
00:53:17,440 --> 00:53:18,981
Trước khi phần này, tôi được như thế, chờ đợi.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Vì vậy, những gì bạn muốn
làm là lựa chọn sắp xếp,

1275
00:53:24,141 --> 00:53:25,890
cách bạn có thể nghĩ
về nó và cách

1276
00:53:25,890 --> 00:53:30,140
Tôi chắc chắn rằng tôi không cố gắng để có được
họ hỗn hợp lên, là nó đi qua

1277
00:53:30,140 --> 00:53:33,280
và nó chọn
số nhỏ nhất và nó

1278
00:53:33,280 --> 00:53:36,070
đặt rằng vào đầu danh sách của bạn.

1279
00:53:36,070 --> 00:53:37,730
Nó hoán đổi nó với vị trí đầu tiên.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Họ thực sự có một ví dụ cho tôi.

1282
00:53:45,370 --> 00:53:46,540
Tuyệt vời.

1283
00:53:46,540 --> 00:53:50,130
Vì vậy, chỉ là một cách để suy nghĩ lựa chọn it--
sắp xếp, chọn giá trị nhỏ nhất.

1284
00:53:50,130 --> 00:53:51,940
Và chúng ta sẽ
chạy qua một ví dụ

1285
00:53:51,940 --> 00:53:55,320
mà tôi nghĩ rằng sẽ giúp đỡ vì
Tôi nghĩ rằng hình ảnh luôn luôn giúp đỡ.

1286
00:53:55,320 --> 00:53:58,510
Vì vậy, chúng ta bắt đầu với một cái gì đó
đó là hoàn toàn không được phân loại.

1287
00:53:58,510 --> 00:54:00,730
Red sẽ không được phân loại,
màu xanh lá cây sẽ được sắp xếp.

1288
00:54:00,730 --> 00:54:02,190
Tất cả sẽ làm cho tinh thần trong một giây.

1289
00:54:02,190 --> 00:54:08,950
>> Vì vậy, chúng tôi đi qua và chúng ta lặp
từ đầu đến cuối.

1290
00:54:08,950 --> 00:54:12,320
Và chúng ta nói, OK, 2 là
số lượng nhỏ nhất của chúng tôi.

1291
00:54:12,320 --> 00:54:15,680
Vì vậy, chúng ta sẽ mất 2 và chúng ta sẽ
để di chuyển nó vào phía trước của mảng của chúng tôi

1292
00:54:15,680 --> 00:54:17,734
bởi vì đó là
số nhỏ nhất chúng ta có.

1293
00:54:17,734 --> 00:54:19,150
Vì vậy, đó là những gì đang thực hiện ở đây.

1294
00:54:19,150 --> 00:54:20,820
Nó chỉ đi để trao đổi hai.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Vì vậy, bây giờ chúng tôi đã sắp xếp một
một phần và một phần được phân loại.

1297
00:54:25,450 --> 00:54:27,810
Và những gì tốt để nhớ
về việc lựa chọn loại

1298
00:54:27,810 --> 00:54:30,690
là chúng tôi chỉ lựa chọn
từ phần phân loại.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Các phần được sắp xếp bạn chỉ để lại một mình.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> HỌC SINH: Làm thế nào để biết nó là gì
nhỏ nhất mà không so sánh nó

1303
00:54:38,452 --> 00:54:39,868
để các giá trị khác trong mảng.

1304
00:54:39,868 --> 00:54:41,250
GIẢNG: Nó không so sánh nó.

1305
00:54:41,250 --> 00:54:42,041
Chúng tôi thích bỏ qua nó.

1306
00:54:42,041 --> 00:54:43,850
Đây chỉ là nói chung chung.

1307
00:54:43,850 --> 00:54:44,831
Yeah.

1308
00:54:44,831 --> 00:54:47,205
Khi chúng tôi viết mã tôi
chắc chắn bạn sẽ hài lòng hơn.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Nhưng bạn lưu trữ này đầu tiên
yếu tố như là nhỏ nhất.

1311
00:54:53,030 --> 00:54:56,110
Bạn so sánh và bạn
nói, OK, là nó nhỏ hơn?

1312
00:54:56,110 --> 00:54:56,660
Vâng.

1313
00:54:56,660 --> 00:54:57,460
Giữ nó.

1314
00:54:57,460 --> 00:54:58,640
Đây là nó nhỏ hơn?

1315
00:54:58,640 --> 00:54:59,660
Không có?

1316
00:54:59,660 --> 00:55:02,510
>> Đây là nhỏ nhất của bạn,
phân công lại nó để giá trị của bạn.

1317
00:55:02,510 --> 00:55:06,340
Và bạn sẽ có nhiều hạnh phúc hơn
khi chúng tôi đi qua các mã.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Vì vậy, chúng tôi đi qua, chúng tôi trao đổi nó, vì vậy sau đó
chúng ta nhìn vào phần không được phân loại này.

1320
00:55:13,970 --> 00:55:15,810
Vì vậy, chúng ta sẽ chọn ra ba.

1321
00:55:15,810 --> 00:55:18,890
Chúng ta sẽ đặt nó trên tại
cuối phần được sắp xếp của chúng tôi.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
Và chúng tôi chỉ cần đi để tiếp tục làm
rằng, làm điều đó, và làm điều đó.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Vì vậy, đây là loại của chúng tôi giả ở đây.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Chúng tôi sẽ mã nó lên ở đây trong một giây.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Nhưng chỉ cần một cái gì đó để đi bộ
thông qua trên một mức độ cao.

1330
00:55:37,270 --> 00:55:40,275
Bạn sẽ đi từ
i bằng từ 0 đến n trừ đi 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Đó là tối ưu hóa khác.

1333
00:55:43,530 --> 00:55:45,020
Đừng lo lắng quá nhiều về nó.

1334
00:55:45,020 --> 00:55:46,620
Vì vậy, như bạn đã nói.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Như Jacob đã nói, làm thế nào chúng ta
theo dõi những gì tối thiểu của chúng tôi là gì?

1337
00:55:54,406 --> 00:55:55,030
Làm thế nào để chúng ta biết?

1338
00:55:55,030 --> 00:55:57,060
Chúng ta phải so sánh
tất cả mọi thứ trong danh sách của chúng tôi.

1339
00:55:57,060 --> 00:55:59,600
>> Vì vậy, tối thiểu bằng i.

1340
00:55:59,600 --> 00:56:03,870
Nó chỉ nói rằng trong trường hợp này
chỉ số của giá trị tối thiểu của chúng tôi.

1341
00:56:03,870 --> 00:56:07,660
Vì vậy, sau đó nó sẽ lặp qua
và nó đi từ j bằng i cộng thêm 1.

1342
00:56:07,660 --> 00:56:11,420
Vì vậy, chúng tôi đã biết rằng
đó là yếu tố đầu tiên của chúng tôi.

1343
00:56:11,420 --> 00:56:13,240
Chúng tôi không cần phải so sánh nó với chính nó.

1344
00:56:13,240 --> 00:56:16,970
Vì vậy, chúng tôi bắt đầu so sánh nó với các tiếp theo
một trong đó là lý do tại sao nó là i + 1 đến n

1345
00:56:16,970 --> 00:56:20,110
trừ đi 1, đó là
cuối mảng đó.

1346
00:56:20,110 --> 00:56:25,090
Và chúng tôi đã nói nếu mảng ở
j là ít hơn mảng min,

1347
00:56:25,090 --> 00:56:29,200
sau đó chúng tôi phân công lại nơi
chỉ số tối thiểu của chúng tôi là.

1348
00:56:29,200 --> 00:56:37,470
>> Và nếu min là không bằng tôi, như
ở nơi mà chúng tôi đã trở lại ở đây.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Vì vậy, giống như khi chúng tôi lần đầu tiên đã làm một này.

1351
00:56:41,790 --> 00:56:49,310
Trong trường hợp này, nó sẽ bắt đầu
bằng không, nó sẽ kết thúc được hai.

1352
00:56:49,310 --> 00:56:53,010
Vì vậy, min sẽ không bằng i cuối cùng.

1353
00:56:53,010 --> 00:56:55,720
Điều đó cho phép chúng ta biết rằng
chúng ta cần phải trao đổi chúng.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Tôi cảm thấy như một ví dụ cụ thể
sẽ giúp nhiều hơn này.

1356
00:57:00,470 --> 00:57:04,970
Vì vậy, tôi sẽ mã này với các bạn
ngay bây giờ và tôi nghĩ rằng nó sẽ được tốt hơn.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Loại có xu hướng làm việc theo cách đó trong đó
nó thường tốt hơn chỉ để nhìn thấy chúng.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Vì vậy, những gì chúng tôi muốn làm là
trước tiên chúng ta muốn nhỏ nhất

1361
00:57:17,280 --> 00:57:19,890
phần tử trong vị trí của nó trong mảng.

1362
00:57:19,890 --> 00:57:21,280
Chính xác những gì Jacob đã nói.

1363
00:57:21,280 --> 00:57:23,090
Bạn cần lưu trữ bằng cách nào đó.

1364
00:57:23,090 --> 00:57:25,900
Vì vậy, chúng ta sẽ bắt đầu ở đây
iterating trên mảng.

1365
00:57:25,900 --> 00:57:28,970
Chúng tôi sẽ nói đó là của chúng tôi
Người đầu tiên chỉ để bắt đầu.

1366
00:57:28,970 --> 00:57:38,308
Vì vậy, chúng ta sẽ có int
nhỏ nhất là bằng với mảng ở i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Vì vậy, một điều cần lưu ý, mỗi
thời gian vòng lặp này thực hiện,

1369
00:57:45,050 --> 00:57:48,550
chúng tôi đang bắt đầu một bước xa hơn.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Khi chúng tôi bắt đầu chúng ta nhìn vào một này.

1372
00:57:57,440 --> 00:58:00,840
Lần sau chúng ta lặp qua,
chúng tôi đang bắt đầu tại một này

1373
00:58:00,840 --> 00:58:02,680
và gán cho nó giá trị nhỏ nhất của chúng tôi.

1374
00:58:02,680 --> 00:58:10,450
Vì vậy, nó rất giống với bong bóng sắp xếp
nơi chúng ta biết rằng một đường chuyền sau,

1375
00:58:10,450 --> 00:58:11,700
Yếu tố cuối cùng này được sắp xếp.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Với lựa chọn sắp xếp,
nó chỉ là ngược lại.

1378
00:58:15,120 --> 00:58:18,950
>> Tại mỗi vượt qua, chúng ta biết rằng
người đầu tiên được sắp xếp.

1379
00:58:18,950 --> 00:58:21,360
Sau khi vượt qua thứ hai,
thứ hai sẽ được sắp xếp.

1380
00:58:21,360 --> 00:58:26,470
Và như bạn đã thấy với các ví dụ slide,
phần sắp xếp của chúng tôi chỉ tiếp tục tăng.

1381
00:58:26,470 --> 00:58:34,020
Vì vậy, bằng cách thiết lập một nhỏ nhất của chúng tôi
để mảng i, tất cả nó làm

1382
00:58:34,020 --> 00:58:37,340
được thắt những gì
chúng tôi đang tìm kiếm như vậy là

1383
00:58:37,340 --> 00:58:40,164
để giảm thiểu số
so sánh chúng tôi thực hiện.

1384
00:58:40,164 --> 00:58:41,770
Điều đó có ý nghĩa với tất cả mọi người?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Bạn có cần tôi để chạy thông qua đó
một lần nữa chậm hơn hay nói cách khác nhau?

1387
00:58:46,380 --> 00:58:47,180
Tôi rất vui.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Vì vậy, chúng ta giữ
giá trị tại thời điểm này,

1392
00:58:55,540 --> 00:58:57,840
nhưng chúng tôi cũng muốn để lưu trữ các chỉ số.

1393
00:58:57,840 --> 00:59:01,010
Vì vậy, chúng ta sẽ lưu trữ
vị trí nhỏ nhất

1394
00:59:01,010 --> 00:59:02,770
một, mà chỉ là có được tôi.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Vì vậy bây giờ Jacob là hài lòng.

1397
00:59:05,440 --> 00:59:06,870
Chúng tôi có những thứ được lưu trữ.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
Và bây giờ chúng ta cần phải xem xét thông qua
phần không được phân loại của mảng.

1400
00:59:11,870 --> 00:59:18,170
Vì vậy, trong trường hợp này này
sẽ không được phân loại của chúng tôi.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Đây là i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Vì vậy, những gì chúng tôi đang đi làm
là có được một vòng lặp.

1406
00:59:30,040 --> 00:59:32,066
Bất cứ khi nào bạn cần
lặp thông qua một mảng,

1407
00:59:32,066 --> 00:59:33,440
tâm trí của bạn có thể đi đến một vòng lặp.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Vì vậy, đối với một số int k
equals-- những gì chúng ta nghĩ

1410
00:59:38,090 --> 00:59:39,700
k sẽ bằng để bắt đầu với?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Đây là những gì chúng tôi thiết lập như là nhỏ nhất của chúng tôi
giá trị và chúng tôi muốn so sánh nó.

1413
00:59:44,766 --> 00:59:47,090
Những gì chúng tôi muốn so sánh nó với?

1414
00:59:47,090 --> 00:59:48,730
Nó sẽ là một trong những tiếp theo này, phải không?

1415
00:59:48,730 --> 00:59:53,200
Vì vậy, chúng tôi muốn k phải được khởi tạo
để tôi cộng thêm 1 để bắt đầu.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> Và chúng tôi muốn k trong trường hợp này chúng tôi
đã có kích thước lưu trữ ở đây,

1418
01:00:02,800 --> 01:00:03,930
vì vậy chúng tôi chỉ có thể sử dụng kích thước.

1419
01:00:03,930 --> 01:00:06,240
Kích thước là kích thước của mảng.

1420
01:00:06,240 --> 01:00:09,620
Và chúng tôi chỉ muốn
k cập nhật bởi một mỗi lần.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Cool.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Vì vậy, bây giờ chúng tôi cần phải tìm
phần tử nhỏ nhất ở đây.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Vì vậy, nếu chúng ta lặp qua, chúng tôi
muốn nói, nếu mảng tại k

1427
01:00:31,380 --> 01:00:37,080
là ít hơn value-- nhỏ nhất của chúng tôi
đây là nơi mà chúng tôi thực sự

1428
01:00:37,080 --> 01:00:42,950
theo dõi những gì là
các here-- nhỏ nhất

1429
01:00:42,950 --> 01:00:47,740
sau đó chúng tôi muốn gán
những gì giá trị nhỏ nhất của chúng tôi là.

1430
01:00:47,740 --> 01:00:50,645
>> Điều này có nghĩa rằng, oh, chúng tôi
lặp lại thông qua đây.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Dù giá trị ở đây là
không phải là điều nhỏ nhất của chúng tôi.

1433
01:00:53,740 --> 01:00:54,448
Chúng tôi không muốn nó.

1434
01:00:54,448 --> 01:00:56,100
Chúng tôi muốn gán nó.

1435
01:00:56,100 --> 01:01:02,050
Vì vậy, nếu chúng ta giao lại nó, những gì làm
bạn nghĩ rằng có thể là trong mã này ở đây?

1436
01:01:02,050 --> 01:01:04,160
Chúng tôi muốn gán
nhỏ nhất và vị trí.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Vì vậy, những gì bây giờ là nhỏ nhất?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
HỌC SINH: Array k.

1441
01:01:09,130 --> 01:01:09,963
GIẢNG: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
Và bây giờ là những gì vị trí?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Các chỉ số của là gì
giá trị nhỏ nhất của chúng tôi?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Nó chỉ k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Vì vậy, mảng k, k, họ phù hợp lên.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Vì vậy, chúng tôi muốn phân công lại đó.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Và sau đó sau khi chúng tôi tìm thấy nhỏ nhất của chúng tôi,
do đó vào cuối những điều này cho vòng lặp

1454
01:01:39,950 --> 01:01:45,100
ở đây chúng tôi đã tìm thấy những gì nhỏ nhất của chúng tôi
giá trị, vì vậy chúng tôi chỉ trao đổi nó.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
Trong trường hợp này, như nói của chúng tôi
giá trị nhỏ nhất là ra ở đây.

1457
01:01:50,816 --> 01:01:51,940
Đây là giá trị nhỏ nhất của chúng tôi.

1458
01:01:51,940 --> 01:01:57,690
>> Chúng tôi chỉ muốn trao đổi nó ở đây, đó là
những gì mà chức năng trao đổi ở phía dưới

1459
01:01:57,690 --> 01:02:01,270
đã làm, mà chúng tôi chỉ viết lên
cùng một vài phút trước đây.

1460
01:02:01,270 --> 01:02:02,775
Vì vậy, nó nên trông quen thuộc.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
Và sau đó nó sẽ chỉ lặp đi lặp lại
thông qua cho đến khi nó đạt đến tất cả các cách

1463
01:02:08,030 --> 01:02:13,100
đến cuối, có nghĩa là bạn
có không yếu tố đó là không được phân loại

1464
01:02:13,100 --> 01:02:14,800
và mọi thứ khác đã được sắp xếp.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Có ý nghĩa?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Một ít cụ thể hơn?

1469
01:02:19,280 --> 01:02:19,990
Mã giúp đỡ?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> HỌC SINH: Đối với một kích thước, bạn không bao giờ
thực sự định nghĩa nó hoặc thay đổi nó,

1472
01:02:26,410 --> 01:02:27,340
như thế nào biết?

1473
01:02:27,340 --> 01:02:32,380
>> GIẢNG: Vì vậy, có một điều để
nhận thấy ở đây là int size.

1474
01:02:32,380 --> 01:02:35,680
Vì vậy, chúng ta đang nói ở loại sort-- này
là một chức năng trong này case-- nó

1475
01:02:35,680 --> 01:02:40,770
lựa chọn loại, nó được thông qua
với các chức năng.

1476
01:02:40,770 --> 01:02:43,460
Vì vậy, nếu nó không được thông qua
trong, bạn sẽ làm điều gì đó

1477
01:02:43,460 --> 01:02:47,840
như với chiều dài của mảng
hoặc bạn sẽ lặp qua

1478
01:02:47,840 --> 01:02:49,390
để tìm độ dài.

1479
01:02:49,390 --> 01:02:52,680
Nhưng vì nó được thông qua
tại, chúng tôi chỉ có thể sử dụng nó.

1480
01:02:52,680 --> 01:02:55,720
Bạn chỉ cần giả định rằng người sử dụng
cho bạn một kích thước hợp lệ

1481
01:02:55,720 --> 01:02:57,698
thực sự đại diện
một kích thước của mảng của bạn.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Mát mẻ?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Nếu bạn có bất kỳ rắc rối với những
hoặc muốn biết thêm thực hành mã hóa các loại

1486
01:03:05,870 --> 01:03:08,050
trên của riêng bạn, bạn nên
đi đến study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Đó là một công cụ.

1489
01:03:12,670 --> 01:03:15,040
Họ có một kiểm tra mà
bạn thực sự có thể viết.

1490
01:03:15,040 --> 01:03:16,180
Họ làm giả.

1491
01:03:16,180 --> 01:03:19,310
Họ có nhiều video và slide
bao gồm cả những cái tôi sử dụng ở đây.

1492
01:03:19,310 --> 01:03:23,150
Vì vậy, nếu bạn vẫn còn cảm thấy một
chút mờ, cố gắng mà ra.

1493
01:03:23,150 --> 01:03:25,670
Như mọi khi, đến nói chuyện với tôi, quá.

1494
01:03:25,670 --> 01:03:26,320
Câu hỏi?

1495
01:03:26,320 --> 01:03:28,611
>> HỌC SINH: Bạn có nói rằng các
kích thước trước đây được định nghĩa?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
GIẢNG: Có.

1498
01:03:29,900 --> 01:03:35,570
Kích thước trước đây được xác định lên
ở đây trong phần khai báo hàm.

1499
01:03:35,570 --> 01:03:39,060
Vì vậy, bạn cho rằng nó được thông qua trong
bởi người sử dụng, và để đơn giản,

1500
01:03:39,060 --> 01:03:41,896
chúng ta sẽ giả định rằng
người sử dụng đã cho chúng tôi kích thước chính xác.

1501
01:03:41,896 --> 01:03:43,240
Cool.

1502
01:03:43,240 --> 01:03:44,390
Vì vậy, đó là lựa chọn loại.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Guys, Tôi biết chúng tôi học được rất nhiều ngày hôm nay.

1505
01:03:47,640 --> 01:03:49,710
Đó là một dữ liệu dày đặc cho phần.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Vì vậy, với điều đó, chúng ta sẽ
để đi đến sắp xếp chèn.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Vì vậy, trước đó chúng ta phải làm
phân tích thời gian chạy của chúng tôi ở đây.

1511
01:04:06,100 --> 01:04:10,190
Vì vậy, trong trường hợp tốt nhất,
cấp kể từ khi tôi chỉ cho bạn

1512
01:04:10,190 --> 01:04:11,960
bảng tôi đã
loại đã cho nó đi.

1513
01:04:11,960 --> 01:04:15,430
Nhưng thời gian chạy trường hợp tốt nhất, những gì chúng ta nghĩ?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Tất cả mọi thứ được sắp xếp.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N phương.

1518
01:04:22,070 --> 01:04:24,780
Bất cứ ai có một lời giải thích
cho lý do tại sao bạn nghĩ sao?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> HỌC SINH: Bạn đang so sánh through--

1521
01:04:30,519 --> 01:04:31,268
GIẢNG: Đúng vậy.

1522
01:04:31,268 --> 01:04:32,540
Bạn đang so sánh thông qua.

1523
01:04:32,540 --> 01:04:35,630
Tại mỗi lần lặp, mặc dù
chúng tôi đang decrementing này bằng một,

1524
01:04:35,630 --> 01:04:38,950
bạn vẫn tìm kiếm thông qua
tất cả mọi thứ để tìm một nhỏ nhất.

1525
01:04:38,950 --> 01:04:42,390
Vì vậy, ngay cả khi giá trị nhỏ nhất của bạn
là ở đây ngay từ đầu,

1526
01:04:42,390 --> 01:04:44,710
bạn vẫn so sánh nó
chống lại tất cả mọi thứ khác

1527
01:04:44,710 --> 01:04:46,550
để chắc chắn rằng đó là điều nhỏ nhất.

1528
01:04:46,550 --> 01:04:49,820
Vì vậy, bạn sẽ kết thúc chạy qua
khoảng n bình phương lần.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Được rồi.

1531
01:04:51,590 --> 01:04:52,785
Và trường hợp xấu nhất là gì?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Ngoài ra n bình vì bạn đang đi
để được làm điều đó cùng một thủ tục.

1534
01:04:57,980 --> 01:05:01,670
Vì vậy, trong trường hợp này, lựa chọn
loại có một cái gì đó

1535
01:05:01,670 --> 01:05:04,010
rằng chúng ta cũng gọi thời gian chạy dự kiến.

1536
01:05:04,010 --> 01:05:07,400
Vì vậy, trong những người khác, chúng ta chỉ cần biết
các giới hạn trên và dưới.

1537
01:05:07,400 --> 01:05:11,180
Tùy thuộc vào cách điên của chúng tôi
danh sách là như thế nào hoặc không được phân loại nó là,

1538
01:05:11,180 --> 01:05:15,350
chúng khác nhau giữa n hoặc n bình phương.

1539
01:05:15,350 --> 01:05:16,550
Chúng tôi không biết.

1540
01:05:16,550 --> 01:05:22,820
>> Nhưng vì lựa chọn loại có cùng
tồi tệ nhất và trường hợp tốt nhất, cho chúng ta biết rằng

1541
01:05:22,820 --> 01:05:25,880
không có vấn đề gì loại của đầu vào chúng tôi
có, cho dù đó là hoàn toàn

1542
01:05:25,880 --> 01:05:29,130
sắp xếp hoặc hoàn toàn
sắp xếp đảo ngược, đó là

1543
01:05:29,130 --> 01:05:30,740
sẽ mất cùng một lượng thời gian.

1544
01:05:30,740 --> 01:05:33,760
Vì vậy, trong trường hợp đó, nếu bạn
nhớ từ bảng của chúng tôi,

1545
01:05:33,760 --> 01:05:38,610
nó thực sự đã có một giá trị
hai loại này không có,

1546
01:05:38,610 --> 01:05:40,390
đó là thời gian chạy dự kiến.

1547
01:05:40,390 --> 01:05:43,350
Vì vậy, chúng ta biết rằng bất cứ khi nào
chúng tôi chạy lựa chọn sắp xếp,

1548
01:05:43,350 --> 01:05:45,380
nó đảm bảo
chạy một thời gian n bình phương.

1549
01:05:45,380 --> 01:05:46,630
Không có sự thay đổi đó.

1550
01:05:46,630 --> 01:05:47,630
Nó chỉ là dự kiến.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
Và, một lần nữa, nếu bạn muốn tìm hiểu
hơn, có CS 124 vào mùa xuân.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Được rồi.

1555
01:05:56,712 --> 01:05:57,545
Chúng tôi đã nhìn thấy một này.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Cool.

1558
01:05:59,030 --> 01:06:00,930
Vì vậy, loại chèn.

1559
01:06:00,930 --> 01:06:03,330
Và tôi có lẽ sẽ
để ngọn lửa thông qua này.

1560
01:06:03,330 --> 01:06:05,440
Tôi sẽ không có các bạn mã nó.

1561
01:06:05,440 --> 01:06:06,580
Chúng tôi sẽ chỉ cần đi bộ qua nó.

1562
01:06:06,580 --> 01:06:10,500
Vì vậy, sắp xếp chèn là loại
tương tự để lựa chọn loại

1563
01:06:10,500 --> 01:06:14,460
trong đó chúng ta có cả một không được phân loại
và sắp xếp một phần của mảng.

1564
01:06:14,460 --> 01:06:20,260
>> Nhưng điều khác biệt là
như chúng tôi đi qua từng người một,

1565
01:06:20,260 --> 01:06:24,210
chúng ta chỉ cần lấy bất cứ số
là tiếp theo của chúng tôi không được phân loại,

1566
01:06:24,210 --> 01:06:28,507
và sắp xếp nó một cách chính xác
vào mảng được sắp xếp của chúng tôi.

1567
01:06:28,507 --> 01:06:30,090
Nó sẽ có ý nghĩa hơn với một ví dụ.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Vì vậy, tất cả mọi thứ bắt đầu như không được phân loại,
giống như với các lựa chọn sắp xếp.

1570
01:06:35,430 --> 01:06:38,740
Và chúng ta sẽ sắp xếp này trong
thứ tự tăng dần như chúng tôi có được.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Vì vậy, trên đèo đầu tiên của chúng tôi
chúng ta lấy giá trị đầu tiên

1573
01:06:43,340 --> 01:06:46,700
và chúng ta nói, OK, bạn có
bây giờ trong một danh sách của mình.

1574
01:06:46,700 --> 01:06:49,150
>> Bởi vì bạn đang ở trong một danh sách
của chính mình, bạn đều được sắp xếp.

1575
01:06:49,150 --> 01:06:52,460
Xin chúc mừng cho là
Yếu tố đầu tiên trong mảng này.

1576
01:06:52,460 --> 01:06:54,800
Bạn đã sắp xếp tất cả các ngày của riêng bạn.

1577
01:06:54,800 --> 01:06:58,900
Vì vậy, bây giờ chúng tôi đã sắp xếp một
và một mảng được phân loại.

1578
01:06:58,900 --> 01:07:01,760
Vì vậy, bây giờ chúng ta đi đầu tiên.

1579
01:07:01,760 --> 01:07:05,600
Điều gì xảy ra giữa đây
và ở đây là chúng ta nói,

1580
01:07:05,600 --> 01:07:08,890
OK, chúng ta sẽ nhìn vào
giá trị đầu tiên của mảng không được phân loại của chúng tôi

1581
01:07:08,890 --> 01:07:13,270
và chúng ta sẽ phải nhập vào nó trong của nó
địa điểm chính xác trong mảng được sắp xếp.

1582
01:07:13,270 --> 01:07:21,460
>> Vì vậy, những gì chúng tôi làm là chúng ta mất 5 và
chúng ta nói, OK, 5 lớn hơn 3,

1583
01:07:21,460 --> 01:07:24,630
vì vậy chúng tôi chỉ cần chèn nó bên phải
bên phải đó.

1584
01:07:24,630 --> 01:07:25,130
Chúng tôi đang tốt.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Vì vậy, sau đó chúng tôi tiếp tục tiếp theo của chúng tôi.

1587
01:07:28,420 --> 01:07:29,720
Và chúng tôi mất 2.

1588
01:07:29,720 --> 01:07:34,330
Chúng ta nói, OK, 2 là ít
hơn 3, vì vậy chúng tôi biết rằng nó

1589
01:07:34,330 --> 01:07:36,220
cần phải được ở
trước danh sách của chúng tôi bây giờ.

1590
01:07:36,220 --> 01:07:41,800
Vì vậy, những gì chúng ta làm chúng ta đẩy 3 và 5 xuống là
và chúng tôi di chuyển vào 2 khe đầu tiên.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Vì vậy, chúng tôi chỉ chèn nó vào
địa điểm chính xác nó nên được.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Sau đó, chúng ta nhìn vào chúng tôi
kế tiếp, chúng ta nói 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 lớn hơn
tất cả mọi thứ trong mảng được sắp xếp của chúng tôi,

1596
01:07:53,620 --> 01:07:56,000
vì vậy chúng tôi chỉ cần gắn thẻ trên để kết thúc.

1597
01:07:56,000 --> 01:07:56,960
Và sau đó chúng ta nhìn vào 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 là ít hơn 6, nó ít hơn
hơn 5 nhưng nó lớn hơn 3.

1600
01:08:03,020 --> 01:08:06,270
Vì vậy, chúng tôi chỉ cần chèn nó vào
giữa giữa 3 và 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Vì vậy, để làm cho rằng một chút
bit cụ thể hơn,

1603
01:08:10,530 --> 01:08:12,280
đây là loại của
ý tưởng về những gì đã xảy ra.

1604
01:08:12,280 --> 01:08:16,430
Vì vậy, cho mỗi phần tử không được phân loại, chúng tôi
xác định nơi ở phần sắp xếp

1605
01:08:16,430 --> 01:08:17,090
nó được.

1606
01:08:17,090 --> 01:08:20,680
>> Vì vậy, giữ trong tâm trí
sắp xếp và không được phân loại,

1607
01:08:20,680 --> 01:08:26,080
chúng ta phải đi qua thông qua và con số
nơi nó phù hợp trong mảng được sắp xếp.

1608
01:08:26,080 --> 01:08:31,460
Và chúng ta chèn nó bằng cách thay đổi
các yếu tố bên phải của nó xuống.

1609
01:08:31,460 --> 01:08:34,910
Và sau đó chúng tôi chỉ cần giữ
lặp lại thông qua cho đến khi chúng tôi

1610
01:08:34,910 --> 01:08:39,270
có một danh sách được sắp xếp hoàn toàn
nơi không được phân loại tại là zero

1611
01:08:39,270 --> 01:08:41,720
và được sắp xếp chiếm các
toàn bộ danh sách của chúng tôi.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Vì vậy, một lần nữa, để thực hiện những điều
cụ thể hơn, chúng ta có giả.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Vì vậy, về cơ bản tôi cho là
bằng 0 đến n trừ đi 1,

1616
01:08:52,410 --> 01:08:54,790
đó chỉ là chiều dài của mảng của chúng tôi.

1617
01:08:54,790 --> 01:09:00,979
Chúng tôi có một số yếu tố đó là bằng
mảng đầu tiên hoặc các chỉ số đầu tiên.

1618
01:09:00,979 --> 01:09:03,200
Chúng tôi thiết lập j bằng đó.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Vì vậy, trong khi j lớn hơn
không và mảng, j trừ 1

1621
01:09:09,210 --> 01:09:11,660
lớn hơn
yếu tố, vì vậy tất cả đó là làm

1622
01:09:11,660 --> 01:09:17,479
là đảm bảo rằng
j của bạn thực sự đại diện cho

1623
01:09:17,479 --> 01:09:20,010
phần không được phân loại của mảng.

1624
01:09:20,010 --> 01:09:30,745
>> Vì vậy, trong khi vẫn còn là điều
để sắp xếp và j trừ một is-- gì

1625
01:09:30,745 --> 01:09:31,840
là yếu tố cô ấy?

1626
01:09:31,840 --> 01:09:34,760
J không bao giờ được định nghĩa ở đây.

1627
01:09:34,760 --> 01:09:35,677
Đó là loại gây phiền nhiễu.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Anyways.

1630
01:09:36,689 --> 01:09:39,899
Vì vậy, j trừ đi 1, bạn đang kiểm tra
các yếu tố trước khi nó.

1631
01:09:39,899 --> 01:09:46,460
Bạn đang nói, OK, là phần tử
trước khi bất cứ nơi nào tôi am-- hãy

1632
01:09:46,460 --> 01:09:47,540
thực sự rút ra được điều này.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Vì vậy, hãy nói điều này là
như trên đèo thứ hai của chúng tôi.

1635
01:09:56,830 --> 01:09:59,525
Vì vậy, tôi sẽ là bằng
1, mà là ở đây.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Vì vậy, tôi sẽ là bằng 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Đây sẽ là 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Được rồi.

1642
01:10:16,750 --> 01:10:20,945
Vì vậy, yếu tố của chúng tôi trong trường hợp này
là có được bằng 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
Và chúng tôi có một số j đó
sẽ bằng 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Oh, j là decrementing.

1647
01:10:30,971 --> 01:10:31,720
Đó là những gì nó được.

1648
01:10:31,720 --> 01:10:35,680
Vì vậy, j bằng i, vì vậy đây là những gì
nói là khi chúng tôi di chuyển về phía trước,

1649
01:10:35,680 --> 01:10:37,530
chúng tôi chỉ đảm bảo
rằng chúng ta không hơn

1650
01:10:37,530 --> 01:10:43,520
lập chỉ mục theo cách này khi chúng ta đang cố gắng
để chèn mọi thứ vào danh sách được sắp xếp của chúng tôi.

1651
01:10:43,520 --> 01:10:49,850
>> Vì vậy, khi j bằng 1 trong trường hợp này và
mảng j trừ one-- nên mảng j trừ 1

1652
01:10:49,850 --> 01:10:54,610
là 2 trong case-- này nếu đó là
lớn hơn các yếu tố,

1653
01:10:54,610 --> 01:10:57,700
sau đó tất cả điều này đang làm
đang chuyển điều xuống.

1654
01:10:57,700 --> 01:11:04,790
Vì vậy, trong trường hợp này, mảng j trừ một
sẽ là mảng không, đó là 2.

1655
01:11:04,790 --> 01:11:08,430
2 là không lớn hơn 4,
vì vậy điều này không thực hiện.

1656
01:11:08,430 --> 01:11:11,460
Vì vậy, sự thay đổi không di chuyển xuống.

1657
01:11:11,460 --> 01:11:18,790
Điều này không có ở đây chỉ là
di chuyển mảng được sắp xếp của bạn xuống.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
Trong trường hợp này, trên thực tế, chúng tôi
có thể do-- chúng ta hãy thực hiện 3 này.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Vì vậy, nếu chúng tôi đi bộ qua với
ví dụ này, chúng ta đang ở đây.

1662
01:11:31,970 --> 01:11:32,740
Điều này được sắp xếp.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Đây là phân loại.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Mát mẻ?

1667
01:11:39,860 --> 01:11:46,620
Vì vậy, tôi là bằng 2, do đó
yếu tố của chúng tôi là bằng 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
Và j của chúng tôi là bằng 2.

1670
01:11:52,270 --> 01:12:00,620
Vì vậy, chúng tôi xem xét thông qua và chúng tôi
nói, OK, là mảng j trừ một

1671
01:12:00,620 --> 01:12:03,470
lớn hơn các phần tử
mà chúng ta đang tìm kiếm?

1672
01:12:03,470 --> 01:12:05,540
Và câu trả lời là có, đúng không?

1673
01:12:05,540 --> 01:12:11,275
4 lớn hơn 3 và j
là 2, do đó, mã này được thực thi.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Vì vậy, bây giờ những gì chúng tôi làm một mảng ở
2, do đó ngay tại đây, chúng tôi trao đổi chúng.

1676
01:12:18,550 --> 01:12:25,620
Vì vậy, chúng tôi chỉ nói, OK, mảng
2 giờ là có được 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
Và j sẽ bằng
j trừ đi 1, đó là 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Đó là khủng khiếp, nhưng
các bạn có được ý tưởng.

1681
01:12:37,200 --> 01:12:38,360
J tại là bằng 1.

1682
01:12:38,360 --> 01:12:44,360
Và mảng j chỉ là có được
bằng yếu tố của chúng tôi, đó là 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Tôi xóa một cái gì đó tôi không nên
có hoặc một cái gì đó miswrote,

1685
01:12:48,570 --> 01:12:49,910
nhưng các bạn có được ý tưởng.

1686
01:12:49,910 --> 01:12:50,640
>> Nó di chuyển với n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Và sau đó nếu điều này là, nó sẽ lặp
một lần nữa và nó sẽ nói, OK, j là 1 bây giờ.

1689
01:12:57,960 --> 01:13:00,665
Và mảng j trừ 1 bây giờ là 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Là 2 ít hơn yếu tố của chúng tôi?

1692
01:13:03,760 --> 01:13:04,540
Không có?

1693
01:13:04,540 --> 01:13:07,970
Điều đó có nghĩa rằng chúng tôi đã
đưa yếu tố này

1694
01:13:07,970 --> 01:13:10,110
ở vị trí chính xác trong mảng được sắp xếp của chúng tôi.

1695
01:13:10,110 --> 01:13:14,400
Sau đó, chúng ta có thể thực hiện việc này và chúng tôi nói,
OK, mảng được sắp xếp của chúng tôi là ở đây.

1696
01:13:14,400 --> 01:13:19,940
Và nó sẽ đưa con số này 6 và được
như, OK, 6 ít hơn con số này?

1697
01:13:19,940 --> 01:13:20,480
Không có?

1698
01:13:20,480 --> 01:13:21,080
Cool.

1699
01:13:21,080 --> 01:13:22,680
Chúng tôi đang sử dụng tốt.

1700
01:13:22,680 --> 01:13:23,530
>> Làm điều đó một lần nữa.

1701
01:13:23,530 --> 01:13:24,740
Chúng ta nói 7.

1702
01:13:24,740 --> 01:13:29,010
7 ít hơn cuối cùng
của mảng được sắp xếp của chúng tôi?

1703
01:13:29,010 --> 01:13:29,520
Không.

1704
01:13:29,520 --> 01:13:30,430
Vì vậy, chúng tôi đang sử dụng tốt.

1705
01:13:30,430 --> 01:13:32,760
Vì vậy, điều này sẽ được sắp xếp.

1706
01:13:32,760 --> 01:13:38,610
Về cơ bản tất cả điều này
là nó nói cất

1707
01:13:38,610 --> 01:13:42,060
các yếu tố đầu tiên của
mảng không được phân loại của bạn,

1708
01:13:42,060 --> 01:13:46,010
tìm ra nơi nó đi
trong mảng được sắp xếp của bạn.

1709
01:13:46,010 --> 01:13:48,780
Và điều này chỉ chăm sóc
giao dịch hoán đổi để làm điều đó.

1710
01:13:48,780 --> 01:13:51,300
Bạn về cơ bản chỉ trao đổi
cho đến khi nó ở đúng chỗ.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Các hình ảnh thị giác là bạn đang
di chuyển tất cả mọi thứ xuống bằng cách làm đó.

1713
01:13:56,990 --> 01:13:59,420
>> Vì vậy, nó giống như một nửa bong bóng sắp xếp-esque.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Kiểm tra 50 nghiên cứu.

1716
01:14:03,420 --> 01:14:06,000
Tôi khuyên bạn nên cố gắng
mã này trên của riêng bạn.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Nếu bạn có bất kỳ vấn đề hoặc bạn muốn
xem mẫu mã cho một loại chèn,

1719
01:14:12,450 --> 01:14:13,750
xin vui lòng cho tôi biết.

1720
01:14:13,750 --> 01:14:14,500
Tôi luôn luôn xung quanh.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Vì vậy, thời gian chạy trường hợp xấu nhất
và thời gian chạy trường hợp tốt nhất.

1723
01:14:20,200 --> 01:14:30,700
Như bạn thấy anh chàng từ bảng tôi đã
cho thấy bạn, nó cả n bình phương và n.

1724
01:14:30,700 --> 01:14:35,590
>> Vì vậy, loại đi tắt của những gì chúng tôi nói chuyện
về với các loại trước đây của chúng tôi, tồi tệ nhất

1725
01:14:35,590 --> 01:14:38,760
trường hợp thời gian chạy là nếu
nó hoàn toàn không được phân loại,

1726
01:14:38,760 --> 01:14:42,530
chúng ta phải so sánh tất cả các lần n.

1727
01:14:42,530 --> 01:14:47,020
Chúng tôi làm một toàn bộ rất nhiều so sánh
bởi vì nếu nó theo thứ tự ngược,

1728
01:14:47,020 --> 01:14:50,360
chúng ta sẽ nói, OK, điều này
là như nhau, điều này là tốt,

1729
01:14:50,360 --> 01:14:54,650
và điều này sẽ phải được so sánh
chống lại một trong những người đầu tiên được chuyển trở lại.

1730
01:14:54,650 --> 01:14:56,710
Và khi chúng ta có được về phía
đuôi kết thúc, chúng tôi có

1731
01:14:56,710 --> 01:14:59,440
để so sánh, so sánh, và
so sánh với tất cả mọi thứ.

1732
01:14:59,440 --> 01:15:03,030
>> Vì vậy, nó kết thúc lên được
khoảng n bình phương.

1733
01:15:03,030 --> 01:15:09,510
Nếu chính xác thì bạn
nói, OK, 2, bạn tốt.

1734
01:15:09,510 --> 01:15:11,330
3, bạn đang so với 2.

1735
01:15:11,330 --> 01:15:12,310
Bạn tốt.

1736
01:15:12,310 --> 01:15:14,150
4, bạn chỉ cần so sánh với đuôi.

1737
01:15:14,150 --> 01:15:14,990
Bạn tốt.

1738
01:15:14,990 --> 01:15:17,140
6, so với đuôi, bạn đang sử dụng tốt.

1739
01:15:17,140 --> 01:15:20,870
Vì vậy, cho tất cả các điểm nếu nó đã
sắp xếp, bạn đang làm một so sánh.

1740
01:15:20,870 --> 01:15:22,320
Vì vậy, nó chỉ là n.

1741
01:15:22,320 --> 01:15:26,840
Và bởi vì chúng tôi có một thời gian chạy trường hợp tốt nhất
của n và một thời gian chạy trường hợp xấu nhất của n

1742
01:15:26,840 --> 01:15:28,680
bình phương, chúng tôi không có thời gian chạy dự kiến.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Nó chỉ phụ thuộc vào
hỗn loạn của danh sách của chúng tôi ở đó.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
Và một lần nữa, một
đồ thị và bảng khác.

1747
01:15:39,530 --> 01:15:41,170
Vì vậy, sự khác biệt giữa các loại.

1748
01:15:41,170 --> 01:15:44,180
Tôi chỉ cần đi để lướt qua, tôi
cảm thấy như chúng tôi đã nói chuyện rộng rãi

1749
01:15:44,180 --> 01:15:46,570
về cách họ tất cả các loại
của khác nhau và liên kết với nhau.

1750
01:15:46,570 --> 01:15:50,564
Vì vậy, merge sort là người cuối cùng
Tôi sẽ mang các bạn với.

1751
01:15:50,564 --> 01:15:52,105
Chúng tôi có một bức tranh khá đầy màu sắc.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Vì vậy, hợp nhất phân loại là một thuật toán đệ quy.

1754
01:15:56,040 --> 01:15:59,910
Vì vậy, các bạn biết những gì
một hàm đệ quy là gì?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Bất cứ ai muốn nói không?

1757
01:16:03,320 --> 01:16:04,739
Bạn có muốn thử không?

1758
01:16:04,739 --> 01:16:07,280
Vì vậy, một hàm đệ quy chỉ là
một chức năng mà tự gọi mình.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Vì vậy, nếu các bạn đã quen thuộc
với dãy Fibonacci,

1761
01:16:11,590 --> 01:16:15,670
đó là coi là đệ quy vì
bạn mất trước đó hai

1762
01:16:15,670 --> 01:16:17,530
và thêm chúng với nhau
để có được một tiếp theo của bạn.

1763
01:16:17,530 --> 01:16:21,440
Vì vậy, đệ quy, tôi luôn luôn nghĩ
của đệ quy là giống như một xoắn ốc

1764
01:16:21,440 --> 01:16:24,430
vì vậy bạn như vun vút đổ vào nó.

1765
01:16:24,430 --> 01:16:27,150
Nhưng nó chỉ là một chức năng
mà tự gọi mình.

1766
01:16:27,150 --> 01:16:32,660
>> Và, thực sự, thực sự nhanh chóng tôi
có thể cho bạn những gì trông như thế nào.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Vì vậy, đệ quy ở đây, nếu chúng ta nhìn, đây là
cách đệ quy tổng hợp trên một mảng.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Vì vậy, tất cả những gì chúng tôi làm là
chúng tôi có chức năng tổng hợp

1771
01:16:47,880 --> 01:16:52,210
tổng hợp mà phải mất một kích thước và một mảng.

1772
01:16:52,210 --> 01:16:55,210
Và nếu bạn nhận thấy, kích thước
xác suất của một mỗi lần.

1773
01:16:55,210 --> 01:17:00,365
Và tất cả nó là nếu x bằng
zero-- vì vậy nếu kích thước của mảng

1774
01:17:00,365 --> 01:17:02,710
bằng zero-- nó trả về số không.

1775
01:17:02,710 --> 01:17:10,440
>> Nếu không thì nó tóm tắt này
Yếu tố cuối cùng của mảng,

1776
01:17:10,440 --> 01:17:14,790
và sau đó có một khoản
phần còn lại của mảng.

1777
01:17:14,790 --> 01:17:17,555
Vì vậy, nó chỉ phá vỡ nó xuống
vấn đề nhỏ hơn và nhỏ hơn.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Long câu chuyện ngắn, đệ quy,
chức năng mà tự gọi mình.

1780
01:17:21,890 --> 01:17:25,740
Nếu đó là tất cả các bạn đã nhận ra điều này,
đó là những gì một hàm đệ quy là.

1781
01:17:25,740 --> 01:17:29,870
Nếu bạn có 51, bạn sẽ nhận được rất,
rất thoải mái với đệ quy.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Đó là thực sự mát mẻ.

1784
01:17:32,370 --> 01:17:34,660
Nó có ý nghĩa như tại
03:00 một đêm ra.

1785
01:17:34,660 --> 01:17:37,900
Và tôi đã được như thế, tại sao
đã Tôi không bao giờ sử dụng này?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Vì vậy, sắp xếp hợp nhất, về cơ bản
những gì nó sẽ làm là nó

1788
01:17:42,430 --> 01:17:45,620
sẽ phá vỡ nó xuống và phá vỡ nó
xuống cho đến khi nó là yếu tố chỉ duy nhất.

1789
01:17:45,620 --> 01:17:47,570
Các yếu tố duy nhất là dễ dàng để sắp xếp.

1790
01:17:47,570 --> 01:17:48,070
Chúng tôi thấy điều đó.

1791
01:17:48,070 --> 01:17:50,760
Nếu bạn có một yếu tố, đó là
đã xem xét sắp xếp.

1792
01:17:50,760 --> 01:17:53,800
Vì vậy, trên một đầu vào của n phần tử,
nếu n là ít hơn 2,

1793
01:17:53,800 --> 01:17:58,120
chỉ quay trở lại vì điều đó có nghĩa
nó hoặc là 0 hoặc 1 như chúng ta đã thấy.

1794
01:17:58,120 --> 01:18:00,050
Những người được coi là yếu tố được sắp xếp.

1795
01:18:00,050 --> 01:18:02,170
>> Nếu không phá vỡ nó một nửa.

1796
01:18:02,170 --> 01:18:06,336
Sắp xếp nửa đầu, sắp xếp thứ hai
một nửa, và sau đó kết hợp chúng lại với nhau.

1797
01:18:06,336 --> 01:18:07,460
Tại sao nó được gọi là sắp xếp hợp nhất.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Vì vậy, chúng tôi có ở đây chúng tôi sẽ sắp xếp này.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Vì vậy, chúng tôi tiếp tục có họ
cho đến khi kích thước mảng là 1.

1802
01:18:17,210 --> 01:18:20,790
Vì vậy, khi nó là 1, chúng ta chỉ trả lại
bởi vì đây là một mảng được sắp xếp,

1803
01:18:20,790 --> 01:18:23,940
và đây là một mảng được sắp xếp, và đó là
một mảng được sắp xếp, chúng ta tất cả được sắp xếp.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Vì vậy, sau đó những gì chúng tôi làm là chúng tôi
bắt đầu kết hợp chúng lại với nhau.

1806
01:18:29,420 --> 01:18:31,820
>> Vì vậy, cách bạn có thể
suy nghĩ về việc sáp nhập là

1807
01:18:31,820 --> 01:18:36,240
bạn chỉ cần loại bỏ nhỏ
số của mỗi mảng phụ

1808
01:18:36,240 --> 01:18:38,330
và chỉ cần thêm nó vào mảng nổi lên.

1809
01:18:38,330 --> 01:18:44,290
Vì vậy, nếu bạn nhìn ở đây, khi chúng ta có
các bộ chúng tôi có 4, 6, và 1.

1810
01:18:44,290 --> 01:18:47,280
Khi chúng tôi muốn kết hợp này,
chúng ta nhìn vào hai đầu tiên

1811
01:18:47,280 --> 01:18:50,730
và chúng ta nói, OK, 1 là nhỏ hơn,
nó đi vào phía trước.

1812
01:18:50,730 --> 01:18:54,330
4 và 6, không có gì để so sánh là
nó, chỉ cần gắn thẻ trên để kết thúc.

1813
01:18:54,330 --> 01:18:58,020
>> Khi chúng tôi kết hợp hai điều này, chúng ta chỉ
lấy một nhỏ hơn của hai,

1814
01:18:58,020 --> 01:18:59,310
vì vậy nó là 1.

1815
01:18:59,310 --> 01:19:01,690
Và bây giờ chúng ta đi
nhỏ hơn của hai, vì vậy 2.

1816
01:19:01,690 --> 01:19:03,330
Nhỏ hơn của hai, 3.

1817
01:19:03,330 --> 01:19:06,260
Nhỏ hơn của hai, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Vì vậy, bạn chỉ cần kéo ra khỏi các.

1819
01:19:08,630 --> 01:19:11,210
Và bởi vì họ đã
được sắp xếp trước,

1820
01:19:11,210 --> 01:19:14,300
bạn chỉ có một
so sánh mỗi lần có.

1821
01:19:14,300 --> 01:19:19,610
Vì vậy, nhiều mã ở đây, chỉ là đại diện.

1822
01:19:19,610 --> 01:19:24,410
Vì vậy, bạn bắt đầu ở giữa và
bạn sắp xếp trái và bên phải

1823
01:19:24,410 --> 01:19:26,180
và sau đó bạn chỉ cần kết hợp những người.

1824
01:19:26,180 --> 01:19:30,080
>> Và chúng tôi không có mã
cho hợp nhất ngay tại đây.

1825
01:19:30,080 --> 01:19:34,110
Nhưng, một lần nữa, nếu bạn đi trên
nghiên cứu 50, nó sẽ ở đó.

1826
01:19:34,110 --> 01:19:36,860
Nếu không đến nói chuyện với tôi
nếu bạn vẫn còn lẫn lộn.

1827
01:19:36,860 --> 01:19:42,340
Vì vậy, điều thú vị ở đây là trường hợp tốt nhất,
trường hợp xấu nhất, và thời gian chạy dự kiến

1828
01:19:42,340 --> 01:19:46,250
là tất cả trong log n, mà
là tốt hơn so với chúng tôi đã

1829
01:19:46,250 --> 01:19:48,000
thấy cho phần còn lại của các loại của chúng tôi.

1830
01:19:48,000 --> 01:19:51,840
Chúng tôi đã nhìn thấy n bình phương
và những gì chúng tôi thực sự

1831
01:19:51,840 --> 01:19:54,380
nhận được ở đây là n log n, đó là rất tốt.

1832
01:19:54,380 --> 01:19:55,830
>> Hãy nhìn cách tốt hơn nhiều đó là.

1833
01:19:55,830 --> 01:19:56,780
Như một đường cong đẹp.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Vì vậy, nhiều hiệu quả hơn.

1836
01:20:00,120 --> 01:20:03,510
Nếu bạn đã bao giờ có thể, sử dụng hợp nhất phân loại.

1837
01:20:03,510 --> 01:20:04,810
Nó sẽ giúp bạn tiết kiệm thời gian.

1838
01:20:04,810 --> 01:20:07,670
Sau đó, một lần nữa, như chúng tôi đã nói, nếu
bạn đang xuống thấp trong khu vực này,

1839
01:20:07,670 --> 01:20:09,480
nó không làm cho rằng
nhiều sự khác biệt.

1840
01:20:09,480 --> 01:20:11,360
Bạn nhận được lên đến hàng ngàn
và hàng ngàn đầu vào,

1841
01:20:11,360 --> 01:20:13,318
bạn chắc chắn muốn có một
thuật toán hiệu quả hơn.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
Và, một lần nữa, bàn đáng yêu của chúng ta về tất cả
các loại mà các bạn đã học được ngày hôm nay.

1844
01:20:19,400 --> 01:20:21,157
>> Vì vậy, tôi biết nó được một ngày dày đặc.

1845
01:20:21,157 --> 01:20:23,490
Điều này không nhất thiết sẽ
để giúp bạn với pset của bạn.

1846
01:20:23,490 --> 01:20:28,250
Nhưng tôi chỉ muốn làm cho một sự từ bỏ
phần đó không chỉ là về psets.

1847
01:20:28,250 --> 01:20:31,240
Tất cả các tài liệu này là công bằng
trò chơi cho midterms của bạn.

1848
01:20:31,240 --> 01:20:35,430
Và cũng nếu bạn tiếp tục với CS,
đây là những nguyên tắc cơ bản thực sự quan trọng

1849
01:20:35,430 --> 01:20:37,870
mà bạn sẽ cần phải biết.

1850
01:20:37,870 --> 01:20:41,700
Vì vậy, một số ngày sẽ là một
ít pset giúp đỡ thêm,

1851
01:20:41,700 --> 01:20:44,600
nhưng một vài tuần sẽ có
nội dung thực tế nhiều hơn nữa

1852
01:20:44,600 --> 01:20:46,600
mà có thể không có vẻ siêu
hữu ích cho bạn ngay bây giờ,

1853
01:20:46,600 --> 01:20:51,215
nhưng tôi hứa nếu bạn tiếp tục
trên sẽ rất, rất hữu ích.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Vì vậy, đó là nó cho phần.

1856
01:20:54,250 --> 01:20:55,250
Xuống dây.

1857
01:20:55,250 --> 01:20:56,570
Tôi đã làm nó trong vòng một phút.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Nhưng có bạn đi.

1860
01:20:58,970 --> 01:21:01,240
Và tôi sẽ có bánh rán hay bánh kẹo.

1861
01:21:01,240 --> 01:21:03,464
Có ai bị dị ứng với
bất cứ điều gì, bằng cách này?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Trứng và sữa.

1864
01:21:05,890 --> 01:21:08,120
Vì vậy, bánh rán là một không?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Được rồi.

1868
01:21:10,770 --> 01:21:12,120
Sô cô la không?

1869
01:21:12,120 --> 01:21:12,620
Starburst.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts là tốt.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Chúng ta sẽ có
Starburst tuần tiếp theo sau đó.

1874
01:21:17,045 --> 01:21:18,240
Đó là những gì tôi sẽ nhận được.

1875
01:21:18,240 --> 01:21:19,690
Các bạn có một tuần tuyệt vời.

1876
01:21:19,690 --> 01:21:20,460
Đọc spec của bạn.

1877
01:21:20,460 --> 01:21:22,130
>> Hãy cho tôi biết nếu bạn có bất kỳ câu hỏi.

1878
01:21:22,130 --> 01:21:25,300
Pset hai lớp nên được
ra cho bạn thứ Năm.

1879
01:21:25,300 --> 01:21:28,320
Nếu bạn có bất kỳ câu hỏi
về cách tôi phân loại một cái gì đó

1880
01:21:28,320 --> 01:21:32,250
hoặc lý do tại sao tôi chấm một cái gì đó là cách tôi
đã, xin vui lòng gửi email cho tôi, đến nói chuyện với tôi.

1881
01:21:32,250 --> 01:21:34,210
Tôi là một chút điên rồ này
tuần, nhưng tôi hứa

1882
01:21:34,210 --> 01:21:36,340
Tôi vẫn sẽ trả lời trong vòng 24 giờ.

1883
01:21:36,340 --> 01:21:38,240
Vì vậy, có một tuần tuyệt vời, tất cả mọi người.

1884
01:21:38,240 --> 01:21:40,090
Chúc may mắn trên pset của bạn.

1885
01:21:40,090 --> 01:21:41,248