1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [Chơi nhạc]

3
00:00:10,800 --> 00:00:13,500
DAVID Malan: Được rồi.

4
00:00:13,500 --> 00:00:14,670
Được rồi, chào đón trở lại.

5
00:00:14,670 --> 00:00:18,120
Vì vậy, đây là tuần 4, đầu
của chúng, đã.

6
00:00:18,120 --> 00:00:21,320
Và bạn sẽ nhớ lại rằng tuần trước, chúng tôi đặt
mã dành cho chỉ cần một chút

7
00:00:21,320 --> 00:00:24,240
và chúng tôi bắt đầu nói chuyện nhiều hơn một chút
cấp cao, về những thứ như

8
00:00:24,240 --> 00:00:28,130
tìm kiếm và phân loại, mà mặc dù
ý tưởng khá đơn giản, là

9
00:00:28,130 --> 00:00:31,840
đại diện của một lớp học của các vấn đề
bạn sẽ bắt đầu để giải quyết đặc biệt

10
00:00:31,840 --> 00:00:34,820
khi bạn bắt đầu suy nghĩ về thức
dự án và các giải pháp thú vị mà bạn

11
00:00:34,820 --> 00:00:36,760
có thể có các vấn đề thực tế.

12
00:00:36,760 --> 00:00:39,490
Bây giờ bong bóng sắp xếp là một trong những đơn giản nhất
các thuật toán như vậy, và nó

13
00:00:39,490 --> 00:00:42,900
làm việc bởi có những con số nhỏ
trong một danh sách hoặc trong một loạt các loại

14
00:00:42,900 --> 00:00:46,530
bong bóng theo cách của họ lên đến đỉnh, và
số lượng lớn di chuyển theo cách của họ xuống

15
00:00:46,530 --> 00:00:47,930
cuối danh sách đó.

16
00:00:47,930 --> 00:00:50,650
>> Và nhớ lại rằng chúng ta có thể hình dung
bong bóng sắp xếp một chút

17
00:00:50,650 --> 00:00:52,310
một cái gì đó như thế này.

18
00:00:52,310 --> 00:00:53,640
Vì vậy, hãy để tôi đi về phía trước và nhấn Start.

19
00:00:53,640 --> 00:00:55,350
Tôi đã chọn trước bong bóng sắp xếp.

20
00:00:55,350 --> 00:00:58,920
Và nếu bạn nhớ lại rằng màu xanh cao
dòng đại diện cho số lớn, nhỏ

21
00:00:58,920 --> 00:01:03,300
đường màu xanh đại diện cho số lượng nhỏ, như
chúng tôi đi qua này một lần nữa và một lần nữa và

22
00:01:03,300 --> 00:01:07,680
một lần nữa, so sánh hai thanh cạnh nhau
khác màu đỏ, chúng ta sẽ trao đổi các

23
00:01:07,680 --> 00:01:11,010
lớn nhất và nhỏ nhất nếu
họ ra lệnh.

24
00:01:11,010 --> 00:01:14,150
>> Vì vậy, đây sẽ đi vào và đi vào và đi
trên, và bạn sẽ thấy rằng càng lớn

25
00:01:14,150 --> 00:01:16,700
yếu tố này được thực hiện theo cách của họ đến
phải, và các yếu tố nhỏ hơn

26
00:01:16,700 --> 00:01:17,900
thực hiện theo cách của họ bên trái.

27
00:01:17,900 --> 00:01:21,380
Nhưng chúng tôi bắt đầu để định lượng
hiệu quả, các

28
00:01:21,380 --> 00:01:22,970
chất lượng của thuật toán này.

29
00:01:22,970 --> 00:01:25,200
Và chúng tôi cho rằng trong điều tồi tệ nhất
trường hợp, thuật toán này mất

30
00:01:25,200 --> 00:01:27,940
khoảng bao nhiêu bước?

31
00:01:27,940 --> 00:01:28,980
>> Vì vậy, n bình phương.

32
00:01:28,980 --> 00:01:30,402
Và là những gì n?

33
00:01:30,402 --> 00:01:31,650
>> ĐỐI TƯỢNG: Số phần tử.

34
00:01:31,650 --> 00:01:32,790
>> DAVID Malan: Vì vậy, n là
số yếu tố.

35
00:01:32,790 --> 00:01:33,730
Và vì vậy chúng tôi sẽ làm điều này thường xuyên.

36
00:01:33,730 --> 00:01:36,650
Bất cứ lúc nào chúng ta muốn nói về kích thước
của một vấn đề hoặc kích thước của một

37
00:01:36,650 --> 00:01:39,140
đầu vào, hoặc số lượng thời gian cần
để sản xuất ra, chúng tôi sẽ chỉ

38
00:01:39,140 --> 00:01:41,610
tổng quát bất cứ điều gì
đầu vào là như n.

39
00:01:41,610 --> 00:01:45,970
Vì vậy, trở lại trong tuần 0, trang số
trong danh bạ điện thoại là n.

40
00:01:45,970 --> 00:01:47,550
Số lượng sinh viên
trong căn phòng n.

41
00:01:47,550 --> 00:01:49,630
Vì vậy, ở đây, chúng tôi đang theo
rằng mô hình.

42
00:01:49,630 --> 00:01:52,800
>> Bây giờ n bình phương là không đặc biệt
nhanh chóng, vì vậy chúng tôi đã cố gắng để làm tốt hơn.

43
00:01:52,800 --> 00:01:55,970
Và vì vậy chúng tôi đã xem xét một vài
các thuật toán khác, trong đó

44
00:01:55,970 --> 00:01:57,690
là lựa chọn sắp xếp.

45
00:01:57,690 --> 00:01:59,180
Vì vậy, lựa chọn loại là
một chút khác nhau.

46
00:01:59,180 --> 00:02:03,130
Nó đã gần như đơn giản, tôi dám nói,
theo đó tôi bắt đầu vào đầu của

47
00:02:03,130 --> 00:02:06,740
danh sách các tình nguyện viên của chúng tôi và tôi chỉ một lần nữa
và một lần nữa và một lần nữa đã đi qua

48
00:02:06,740 --> 00:02:10,060
danh sách, tuốt ra nhỏ nhất
yếu tố tại một thời gian và đưa anh ta hoặc

49
00:02:10,060 --> 00:02:13,040
mình vào đầu danh sách.

50
00:02:13,040 --> 00:02:16,410
>> Nhưng điều này cũng vậy, một khi chúng ta bắt đầu suy nghĩ
qua toán học và lớn hơn

51
00:02:16,410 --> 00:02:19,860
hình ảnh, nghĩ về bao nhiêu lần
Tôi đã đi lại và trở lại

52
00:02:19,860 --> 00:02:24,090
và ra, chúng tôi đã nói trong trường hợp xấu nhất,
lựa chọn sắp xếp, cũng là những gì?

53
00:02:24,090 --> 00:02:24,960
n bình phương.

54
00:02:24,960 --> 00:02:27,490
Bây giờ trong thế giới thực, nó có thể
thực sự được nhẹ nhanh hơn.

55
00:02:27,490 --> 00:02:30,620
Bởi vì một lần nữa, tôi đã không cần phải giữ
thụt lùi trong khi tôi đã sắp xếp các

56
00:02:30,620 --> 00:02:31,880
nhỏ nhất yếu tố.

57
00:02:31,880 --> 00:02:35,090
Nhưng nếu chúng ta suy nghĩ về rất lớn n, và
nếu bạn loại làm ra toán học như

58
00:02:35,090 --> 00:02:39,170
Tôi đã làm trên bảng, với phương n
một cái gì đó trừ đi, tất cả mọi thứ khác

59
00:02:39,170 --> 00:02:41,850
bên cạnh n bình phương, một lần n
được thực sự lớn, không

60
00:02:41,850 --> 00:02:42,850
thực sự quan trọng nhiều.

61
00:02:42,850 --> 00:02:45,470
Vì vậy, các nhà khoa học máy tính, chúng tôi sắp xếp của
nhắm mắt làm ngơ để nhỏ hơn

62
00:02:45,470 --> 00:02:49,220
yếu tố và chỉ tập trung vào các yếu tố trong
một biểu thức sẽ làm cho

63
00:02:49,220 --> 00:02:50,330
sự khác biệt lớn nhất.

64
00:02:50,330 --> 00:02:52,840
>> Vâng, cuối cùng, chúng tôi đã
tại sắp xếp chèn.

65
00:02:52,840 --> 00:02:56,620
Và điều này cũng tương tự như trong tinh thần, nhưng
chứ không phải là đi qua và lặp đi lặp lại

66
00:02:56,620 --> 00:03:01,250
chọn một trong những phần tử nhỏ nhất ở một
thời gian, tôi thay vào đó là bàn tay tôi

67
00:03:01,250 --> 00:03:04,070
đã được xử lý, và tôi quyết định, tất cả
bên phải, bạn thuộc về nơi này.

68
00:03:04,070 --> 00:03:06,160
Sau đó, tôi chuyển sang phần tử tiếp theo
và quyết định rằng ông hoặc

69
00:03:06,160 --> 00:03:07,470
cô thuộc về đây.

70
00:03:07,470 --> 00:03:08,810
Và sau đó tôi chuyển trên và trên.

71
00:03:08,810 --> 00:03:11,780
Và tôi có thể đến, trên đường đi,
chuyển những người này để

72
00:03:11,780 --> 00:03:13,030
nhường chỗ cho họ.

73
00:03:13,030 --> 00:03:16,880
Vì vậy, đó là sắp xếp của đảo ngược tinh thần
lựa chọn loại mà chúng ta

74
00:03:16,880 --> 00:03:18,630
gọi là sắp xếp chèn.

75
00:03:18,630 --> 00:03:20,810
>> Vì vậy, các chủ đề này xảy ra
trong thế giới thực.

76
00:03:20,810 --> 00:03:23,640
Chỉ cần một vài năm trước đây, khi một số
Thượng nghị sĩ tranh cử tổng thống,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, tại thời điểm Giám đốc điều hành của
Google, thực sự đã có cơ hội

78
00:03:27,160 --> 00:03:28,040
phỏng vấn ông.

79
00:03:28,040 --> 00:03:32,010
Và chúng tôi nghĩ rằng chúng tôi muốn chia sẻ YouTube
cắt cho bạn ở đây, nếu chúng ta có thể bật lên

80
00:03:32,010 --> 00:03:32,950
khối lượng.

81
00:03:32,950 --> 00:03:39,360
>> [VIDEO xem lại]

82
00:03:39,360 --> 00:03:44,620
>> -Bây giờ, Thượng nghị sĩ, bạn đang ở đây tại Google,
và tôi thích nghĩ về nhiệm kỳ tổng thống

83
00:03:44,620 --> 00:03:46,042
như một cuộc phỏng vấn việc làm.

84
00:03:46,042 --> 00:03:47,770
>> [Cười]

85
00:03:47,770 --> 00:03:50,800
>> -Bây giờ thật khó để có được
một công việc như tổng thống.

86
00:03:50,800 --> 00:03:52,480
Và bạn đang trải qua
sự khắc nghiệt tại.

87
00:03:52,480 --> 00:03:54,330
Nó cũng khó để có được một công việc tại Google.

88
00:03:54,330 --> 00:03:59,610
Chúng tôi có thắc mắc và chúng tôi yêu cầu
các ứng cử viên của chúng tôi câu hỏi.

89
00:03:59,610 --> 00:04:02,250
Và điều này là từ Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Cười]

91
00:04:05,325 --> 00:04:06,400
-Các bạn nghĩ tôi đang đùa à?

92
00:04:06,400 --> 00:04:08,750
Nó ở ngay đây.

93
00:04:08,750 --> 00:04:12,110
Cách hiệu quả nhất để là gì
sắp xếp một triệu số nguyên hai-bit?

94
00:04:12,110 --> 00:04:15,810
>> [Cười]

95
00:04:15,810 --> 00:04:18,260
>> -À, uh -

96
00:04:18,260 --> 00:04:19,029
>> -Tôi xin lỗi.

97
00:04:19,029 --> 00:04:19,745
Có lẽ chúng ta nên -

98
00:04:19,745 --> 00:04:21,000
>> -Không, không, không, không, không.

99
00:04:21,000 --> 00:04:21,470
>> -Đó không phải là một -

100
00:04:21,470 --> 00:04:22,185
OK.

101
00:04:22,185 --> 00:04:25,328
>> -Tôi nghĩ rằng bong bóng sắp xếp sẽ
là con đường sai để đi.

102
00:04:25,328 --> 00:04:26,792
>> [Cười]

103
00:04:26,792 --> 00:04:28,510
>> [Cổ vũ và vỗ tay]

104
00:04:28,510 --> 00:04:31,211
>> -Thôi nào, người nói với anh điều này?

105
00:04:31,211 --> 00:04:32,155
OK.

106
00:04:32,155 --> 00:04:33,350
>> [END xem video]

107
00:04:33,350 --> 00:04:35,070
>> DAVID Malan: Vì vậy, có bạn có nó.

108
00:04:35,070 --> 00:04:39,600
Vì vậy, chúng tôi bắt đầu để định lượng các hoạt động
thời gian, có thể nói, với một cái gì đó

109
00:04:39,600 --> 00:04:43,480
được gọi là ký hiệu tiệm cận, đó là
chỉ đề cập đến loại của chúng tôi biến

110
00:04:43,480 --> 00:04:47,420
nhắm mắt làm ngơ để những yếu tố nhỏ hơn và
chỉ nhìn vào thời gian chạy,

111
00:04:47,420 --> 00:04:51,250
hiệu quả hoạt động của các thuật toán,
như n được thực sự lớn theo thời gian.

112
00:04:51,250 --> 00:04:55,110
Và vì vậy chúng tôi giới thiệu lớn O. Và O lớn
một cái gì đó đại diện mà chúng tôi nghĩ

113
00:04:55,110 --> 00:04:57,000
như là một trên ràng buộc.

114
00:04:57,000 --> 00:04:59,570
Và trên thực tế, Barry, chúng ta có thể giảm
hơn mic một chút?

115
00:04:59,570 --> 00:05:01,040
>> Chúng tôi nghĩ đây là một ràng buộc trên.

116
00:05:01,040 --> 00:05:04,710
O quá lớn của n có nghĩa là bình phương trong
trường hợp xấu nhất, một cái gì đó như

117
00:05:04,710 --> 00:05:07,780
lựa chọn loại sẽ mất
n bước phương.

118
00:05:07,780 --> 00:05:10,310
Hoặc một cái gì đó như sắp xếp chèn
sẽ bước n bình phương.

119
00:05:10,310 --> 00:05:15,150
Bây giờ cho một cái gì đó như chèn
sắp xếp, là trường hợp xấu nhất những gì?

120
00:05:15,150 --> 00:05:18,200
Cho một mảng, những gì là tồi tệ nhất
kịch bản có thể bạn có thể tìm thấy

121
00:05:18,200 --> 00:05:20,650
mình phải đối mặt với?

122
00:05:20,650 --> 00:05:21,860
>> Nó hoàn toàn ngược lại, phải không?

123
00:05:21,860 --> 00:05:24,530
Bởi vì nếu nó hoàn toàn ngược lại,
bạn phải làm nhiều công việc.

124
00:05:24,530 --> 00:05:26,420
Bởi vì nếu bạn hoàn toàn ngược lại,
bạn sẽ tìm thấy những

125
00:05:26,420 --> 00:05:28,840
yếu tố lớn nhất ở đây, mặc dù
nó thuộc về dưới đó.

126
00:05:28,840 --> 00:05:31,140
Vì vậy, bạn sẽ nói, được rồi, tại
thời điểm này trong thời gian, bạn thuộc về nơi này,

127
00:05:31,140 --> 00:05:32,310
do đó, bạn để lại một mình.

128
00:05:32,310 --> 00:05:35,425
>> Sau đó, bạn nhận ra, oh, chết tiệt, tôi phải
di chuyển này phần tử nhỏ hơn một chút để

129
00:05:35,425 --> 00:05:36,470
bên trái của bạn.

130
00:05:36,470 --> 00:05:38,770
Sau đó, tôi phải làm điều đó một lần nữa
và một lần nữa và một lần nữa.

131
00:05:38,770 --> 00:05:41,410
Và nếu tôi đi tới đi lui, bạn
sẽ sắp xếp của cảm thấy hiệu suất của

132
00:05:41,410 --> 00:05:45,540
thuật toán đó, bởi vì tôi liên tục
xáo trộn tất cả mọi người khác xuống trong

133
00:05:45,540 --> 00:05:46,510
mảng để nhường chỗ cho nó.

134
00:05:46,510 --> 00:05:47,750
Vì vậy, đó là trường hợp tồi tệ nhất.

135
00:05:47,750 --> 00:05:48,570
>> Ngược lại -

136
00:05:48,570 --> 00:05:50,320
và đây là một cliffhanger lần cuối cùng -

137
00:05:50,320 --> 00:05:54,065
chúng tôi cho rằng sắp xếp chèn
là một omega của những gì?

138
00:05:54,065 --> 00:05:57,530
Là tốt nhất-trường hợp chạy là những gì
thời gian sắp xếp chèn?

139
00:05:57,530 --> 00:05:58,520
Vì vậy, nó thực sự n.

140
00:05:58,520 --> 00:06:00,980
Đó là trống mà chúng tôi rời
trên diễn đàn thời gian qua.

141
00:06:00,980 --> 00:06:03,160
>> Và đó là omega n vì lý do tại sao?

142
00:06:03,160 --> 00:06:06,630
Vâng, trong trường hợp tốt nhất, những gì
sắp xếp chèn sẽ được bàn giao?

143
00:06:06,630 --> 00:06:09,830
Vâng, một danh sách đó là hoàn toàn sắp xếp
đã có, công việc tối thiểu để làm.

144
00:06:09,830 --> 00:06:12,460
Nhưng những gì gọn về sắp xếp chèn
là bởi vì nó bắt đầu ở đây và

145
00:06:12,460 --> 00:06:15,340
quyết định, oh, bạn là số lượng
một, bạn thuộc về nơi này.

146
00:06:15,340 --> 00:06:16,970
Ồ, thật là may mắn.

147
00:06:16,970 --> 00:06:17,740
>> Anh là số hai.

148
00:06:17,740 --> 00:06:19,030
Bạn cũng thuộc về nơi này.

149
00:06:19,030 --> 00:06:21,010
Số ba, thậm chí tốt hơn,
bạn thuộc về nơi này.

150
00:06:21,010 --> 00:06:25,210
Ngay sau khi nó được cho là cuối
giả danh sách, mỗi sắp xếp chèn của

151
00:06:25,210 --> 00:06:28,010
mà chúng tôi đi qua bằng lời nói
Lần cuối cùng, hoàn thành công việc.

152
00:06:28,010 --> 00:06:32,790
Nhưng lựa chọn loại, ngược lại,
tiếp tục làm những gì?

153
00:06:32,790 --> 00:06:35,260
>> Tiếp tục đi qua danh sách
một lần nữa và một lần nữa và một lần nữa.

154
00:06:35,260 --> 00:06:39,160
Bởi vì cái nhìn sâu sắc quan trọng là chỉ có
một khi bạn đã xem xét tất cả các cách để các

155
00:06:39,160 --> 00:06:42,500
cuối danh sách, bạn có thể chắc chắn
rằng các phần tử bạn chọn là

156
00:06:42,500 --> 00:06:45,560
thực sự là yếu tố nhỏ nhất hiện nay.

157
00:06:45,560 --> 00:06:48,920
Vì vậy, các mô hình về tinh thần kết thúc khác nhau
tăng năng suất một số rất thực tế

158
00:06:48,920 --> 00:06:53,130
sự khác biệt cho chúng ta, cũng như những
sự khác biệt tiệm cận lý thuyết.

159
00:06:53,130 --> 00:06:56,910
>> Vì vậy, tóm lại là, sau đó, O lớn của n
phương, chúng tôi đã nhìn thấy một vài ví dụ

160
00:06:56,910 --> 00:06:58,350
các thuật toán cho đến nay.

161
00:06:58,350 --> 00:06:59,580
O lớn của n?

162
00:06:59,580 --> 00:07:02,870
Một thuật toán mà có thể là những gì
được cho là lớn O n?

163
00:07:02,870 --> 00:07:06,930
Trong trường hợp xấu nhất, phải mất
một số tuyến tính của các bước.

164
00:07:06,930 --> 00:07:07,810
>> OK, tìm kiếm tuyến tính.

165
00:07:07,810 --> 00:07:10,470
Và trong trường hợp xấu nhất, mà là
yếu tố bạn đang tìm kiếm khi

166
00:07:10,470 --> 00:07:12,950
áp dụng tìm kiếm tuyến tính?

167
00:07:12,950 --> 00:07:14,680
>> OK, trong trường hợp xấu nhất,
nó thậm chí không có.

168
00:07:14,680 --> 00:07:17,000
Hoặc trong trường hợp thứ hai tồi tệ nhất, nó
tất cả các cách cuối cùng, đó là

169
00:07:17,000 --> 00:07:18,880
cộng-hay-trừ một sự khác biệt một bước.

170
00:07:18,880 --> 00:07:21,180
Vì vậy, vào cuối ngày,
chúng ta có thể nói đó là tuyến tính.

171
00:07:21,180 --> 00:07:23,910
O lớn của n sẽ tìm kiếm tuyến tính,
bởi vì trong trường hợp xấu nhất, các

172
00:07:23,910 --> 00:07:26,610
yếu tố thậm chí không có hoặc nó
tất cả các cách ở cuối.

173
00:07:26,610 --> 00:07:29,370
>> Vâng, O lớn của nhật ký của n.

174
00:07:29,370 --> 00:07:32,760
Chúng tôi đã không nói chuyện rất chi tiết về
này, nhưng chúng tôi đã nhìn thấy điều này trước đây.

175
00:07:32,760 --> 00:07:36,840
Những gì chạy trong cái gọi là logarit
thời gian, trong trường hợp xấu nhất?

176
00:07:36,840 --> 00:07:38,500
>> Yeah, tìm kiếm để nhị phân.

177
00:07:38,500 --> 00:07:42,930
Và tìm kiếm nhị phân trong trường hợp xấu nhất
có thể có yếu tố một nơi nào đó trong

178
00:07:42,930 --> 00:07:45,640
giữa, hoặc ở một nơi
trong mảng.

179
00:07:45,640 --> 00:07:48,040
Nhưng bạn chỉ tìm thấy nó khi bạn
phân chia danh sách trong một nửa, trong

180
00:07:48,040 --> 00:07:48,940
một nửa, một nửa, còn một nửa.

181
00:07:48,940 --> 00:07:50,200
Và sau đó thì đấy, nó ở đó.

182
00:07:50,200 --> 00:07:52,500
Hoặc một lần nữa, trường hợp xấu nhất,
nó thậm chí không có.

183
00:07:52,500 --> 00:07:56,770
Nhưng bạn không biết rằng nó không có
cho đến khi bạn loại đạt đến cuối cùng

184
00:07:56,770 --> 00:08:00,470
dưới hầu hết các yếu tố bằng cách chia đôi
và giảm một nửa và giảm một nửa.

185
00:08:00,470 --> 00:08:01,400
>> O lớn của 1.

186
00:08:01,400 --> 00:08:03,540
Vì vậy, chúng ta có thể lớn O 2, O lớn của 3.

187
00:08:03,540 --> 00:08:06,260
Bất cứ lúc nào bạn muốn chỉ là một số không đổi,
chúng ta chỉ cần sắp xếp chỉ đơn giản hóa

188
00:08:06,260 --> 00:08:07,280
đó là O lớn của 1.

189
00:08:07,280 --> 00:08:10,440
Mặc dù nếu thực tế, phải mất
2 hoặc thậm chí 100 bước, nếu đó là một

190
00:08:10,440 --> 00:08:13,680
hằng số của các bước,
chúng ta chỉ nói O lớn của 1.

191
00:08:13,680 --> 00:08:15,930
Một thuật toán đó là những gì
trong O lớn trong tổng số 1?

192
00:08:15,930 --> 00:08:18,350
>> ĐỐI TƯỢNG: Tìm chiều dài
của một biến.

193
00:08:18,350 --> 00:08:21,090
>> DAVID Malan: Tìm kiếm
chiều dài của một biến?

194
00:08:21,090 --> 00:08:23,870
>> ĐỐI TƯỢNG: Không, chiều dài
nếu nó đã được sắp xếp.

195
00:08:23,870 --> 00:08:24,160
>> DAVID Malan: Tốt.

196
00:08:24,160 --> 00:08:27,850
OK, vì vậy việc tìm kiếm theo chiều dài của một cái gì đó
nếu chiều dài của một cái gì đó, như

197
00:08:27,850 --> 00:08:30,020
một mảng, được lưu trữ trong một số biến.

198
00:08:30,020 --> 00:08:33,380
Bởi vì bạn chỉ có thể đọc các biến,
hoặc in các biến, hoặc

199
00:08:33,380 --> 00:08:34,960
chỉ thường truy cập vào biến đó.

200
00:08:34,960 --> 00:08:37,299
Và thì đấy, mà cần có thời gian liên tục.

201
00:08:37,299 --> 00:08:38,909
>> Ngược lại, nghĩ lại đến đầu.

202
00:08:38,909 --> 00:08:42,460
Hãy nhớ lại tuần đầu tiên của C,
gọi chỉ printf và in ấn

203
00:08:42,460 --> 00:08:46,240
một cái gì đó trên màn hình được cho là
thời gian liên tục, bởi vì nó chỉ mất

204
00:08:46,240 --> 00:08:50,880
một số chu kỳ CPU để hiển thị
rằng văn bản trên màn hình.

205
00:08:50,880 --> 00:08:52,720
Hoặc chờ đợi - hiện nó?

206
00:08:52,720 --> 00:08:56,430
Làm thế nào khác chúng ta có thể mô hình
thực hiện printf?

207
00:08:56,430 --> 00:09:00,420
Ai đó muốn không đồng ý, mà
có lẽ đó là thời gian thực sự không liên tục?

208
00:09:00,420 --> 00:09:03,600
Trong ý thức những gì có thể printf đang chạy
thời gian, thực sự in một chuỗi trên

209
00:09:03,600 --> 00:09:05,580
màn hình, có một cái gì đó
khác hơn liên tục.

210
00:09:05,580 --> 00:09:07,860
>> ĐỐI TƯỢNG: [nghe được].

211
00:09:07,860 --> 00:09:08,230
>> DAVID Malan: Vâng.

212
00:09:08,230 --> 00:09:09,300
Vì vậy, nó phụ thuộc vào quan điểm của chúng tôi.

213
00:09:09,300 --> 00:09:13,390
Nếu chúng ta thực sự nghĩ về đầu vào
printf như là chuỗi, và

214
00:09:13,390 --> 00:09:16,380
do đó chúng tôi đo kích thước của mà
đầu vào theo chiều dài của nó - vì vậy chúng ta hãy gọi

215
00:09:16,380 --> 00:09:17,780
có chiều dài n cũng -

216
00:09:17,780 --> 00:09:21,990
cho là, printf là tự O lớn của n
bởi vì nó sẽ đưa bạn bước n

217
00:09:21,990 --> 00:09:24,750
để in ra mỗi người n
nhân vật, rất có thể.

218
00:09:24,750 --> 00:09:27,730
Ít nhất là trong phạm vi mà chúng tôi giả định
rằng có lẽ nó sử dụng một vòng lặp for

219
00:09:27,730 --> 00:09:28,560
bên dưới mui xe.

220
00:09:28,560 --> 00:09:30,860
>> Nhưng chúng ta sẽ phải nhìn vào đó
code để hiểu nó tốt hơn.

221
00:09:30,860 --> 00:09:33,650
Và thực sự, một khi các bạn bắt đầu
phân tích thuật toán của riêng bạn, bạn sẽ

222
00:09:33,650 --> 00:09:34,900
nghĩa là làm việc đó.

223
00:09:34,900 --> 00:09:37,765
Loại nhãn cầu mã của bạn và suy nghĩ
về - tất cả các quyền, tôi có vòng lặp này

224
00:09:37,765 --> 00:09:41,870
đây hoặc tôi có một vòng lặp lồng nhau đây,
đó là sẽ làm n thứ n lần,

225
00:09:41,870 --> 00:09:46,050
và bạn có thể sắp xếp các lý do theo cách của bạn
thông qua các mã, ngay cả khi nó

226
00:09:46,050 --> 00:09:47,980
giả và không mã thực tế.

227
00:09:47,980 --> 00:09:49,730
>> Vì vậy, những gì về omega n bình phương?

228
00:09:49,730 --> 00:09:53,582
Một thuật toán là những gì mà trong sản phẩm tốt nhất
trường hợp, phải mất n bước bình?

229
00:09:53,582 --> 00:09:54,014
Yeah?

230
00:09:54,014 --> 00:09:54,880
>> ĐỐI TƯỢNG: [nghe được].

231
00:09:54,880 --> 00:09:55,900
>> DAVID Malan: Vì vậy, lựa chọn loại.

232
00:09:55,900 --> 00:09:59,150
Bởi vì trong vấn đề đó thực sự giảm
thực tế là một lần nữa, tôi không biết

233
00:09:59,150 --> 00:10:02,600
Tôi đã tìm thấy nhỏ nhất hiện nay cho đến khi
Tôi đã kiểm tra tất cả các yếu tố darn.

234
00:10:02,600 --> 00:10:08,050
Vì vậy, omega, nói rằng, n, chúng tôi
chỉ đến với một.

235
00:10:08,050 --> 00:10:09,300
Sắp xếp chèn.

236
00:10:09,300 --> 00:10:12,370
Nếu danh sách này sẽ xảy ra để được sắp xếp
đã có, trong trường hợp tốt nhất, chúng tôi chỉ có

237
00:10:12,370 --> 00:10:15,090
để làm cho một đi qua nó,
lúc này chúng tôi chắc chắn.

238
00:10:15,090 --> 00:10:17,890
Và sau đó có thể được cho biết
là tuyến tính, chắc chắn.

239
00:10:17,890 --> 00:10:20,570
>> Những gì về omega của 1?

240
00:10:20,570 --> 00:10:23,790
Những gì, trong trường hợp tốt nhất, có thể mất
một hằng số của các bước?

241
00:10:23,790 --> 00:10:27,220
Vì vậy, tìm kiếm tuyến tính, nếu bạn chỉ nhận được may mắn
và các yếu tố bạn đang tìm kiếm

242
00:10:27,220 --> 00:10:31,000
là ngay từ đầu của danh sách,
nếu đó là nơi bạn đang bắt đầu của bạn

243
00:10:31,000 --> 00:10:33,070
tuyến tính traversal của danh sách đó.

244
00:10:33,070 --> 00:10:35,180
>> Và điều này là thực sự của một
số thứ.

245
00:10:35,180 --> 00:10:37,660
Ví dụ, ngay cả nhị phân
tìm kiếm là omega của 1.

246
00:10:37,660 --> 00:10:40,310
Bởi vì những gì nếu bạn thực sự darn
may mắn và Smack-thoa ở giữa

247
00:10:40,310 --> 00:10:42,950
mảng của bạn là số
bạn đang tìm kiếm?

248
00:10:42,950 --> 00:10:45,730
Vì vậy, bạn có thể nhận được may mắn đó, là tốt.

249
00:10:45,730 --> 00:10:49,190
>> Này, cuối cùng, omega n log n.

250
00:10:49,190 --> 00:10:52,573
Vì vậy, n log n, chúng tôi đã không thực sự
nói về, nhưng -

251
00:10:52,573 --> 00:10:53,300
>> ĐỐI TƯỢNG: Kết nối loại?

252
00:10:53,300 --> 00:10:53,960
>> DAVID Malan: Merge loại.

253
00:10:53,960 --> 00:10:56,920
Đó là cliffhanger thời gian qua,
nơi mà chúng tôi đề xuất, và chúng tôi cho thấy

254
00:10:56,920 --> 00:10:58,600
trực quan, mà có những thuật toán.

255
00:10:58,600 --> 00:11:02,470
Và hợp nhất các loại chỉ là một ví dụ
thuật toán đó là nhanh cơ bản

256
00:11:02,470 --> 00:11:03,450
hơn một số trong những kẻ khác.

257
00:11:03,450 --> 00:11:07,800
Trong thực tế, kết hợp ngắn không chỉ trong
trường hợp tốt nhất n n log, trong điều tồi tệ nhất

258
00:11:07,800 --> 00:11:09,460
trường hợp n n log.

259
00:11:09,460 --> 00:11:14,540
Và khi bạn có sự trùng hợp này
omega và lớn O được điều tương tự?

260
00:11:14,540 --> 00:11:17,310
Chúng ta có thể mô tả đó là những gì
gọi là theta, mặc dù đó là một

261
00:11:17,310 --> 00:11:18,220
chút ít phổ biến hơn.

262
00:11:18,220 --> 00:11:21,730
Nhưng điều đó chỉ có nghĩa là hai giới hạn,
trong trường hợp này là như nhau.

263
00:11:21,730 --> 00:11:25,770
>> Vì vậy, hợp nhất phân loại, những gì thực hiện điều này
thực sự sôi xuống để cho chúng tôi?

264
00:11:25,770 --> 00:11:27,000
Vâng, nhớ lại những động lực.

265
00:11:27,000 --> 00:11:30,340
Hãy để tôi kéo lên một hình ảnh động
chúng tôi đã không nhìn vào thời gian qua.

266
00:11:30,340 --> 00:11:33,390
Điều này, cùng một ý tưởng, nhưng
nó lớn hơn một chút.

267
00:11:33,390 --> 00:11:36,160
Và tôi sẽ đi trước và chỉ ra
đầu tiên - chúng tôi đã sắp xếp chèn trên

268
00:11:36,160 --> 00:11:39,410
phía trên bên trái, sau đó lựa chọn sắp xếp,
bong bóng sắp xếp, một vài loại khác -

269
00:11:39,410 --> 00:11:42,670
vỏ và nhanh chóng - mà chúng tôi đã không nói chuyện
về, và đống và hợp nhất phân loại.

270
00:11:42,670 --> 00:11:47,090
>> Vì vậy, ít nhất là cố gắng tập trung vào đôi mắt của bạn
ba người đứng đầu bên trái và sau đó

271
00:11:47,090 --> 00:11:49,120
hợp nhất phân loại khi tôi nhấp
mũi tên màu xanh lá cây này.

272
00:11:49,120 --> 00:11:51,900
Nhưng tôi sẽ cho tất cả chúng chạy, chỉ để
cung cấp cho bạn một cảm giác của sự đa dạng của

273
00:11:51,900 --> 00:11:53,980
các thuật toán tồn tại trên thế giới.

274
00:11:53,980 --> 00:11:56,180
Tôi sẽ để cho chạy này
cho chỉ một vài giây.

275
00:11:56,180 --> 00:11:59,640
Và nếu bạn tập trung đôi mắt của bạn - chọn một
thuật toán, tập trung vào nó chỉ là một

276
00:11:59,640 --> 00:12:02,970
giây - bạn sẽ bắt đầu thấy
mô hình mà nó được thực hiện.

277
00:12:02,970 --> 00:12:04,530
>> Hợp nhất phân loại, thông báo, được thực hiện.

278
00:12:04,530 --> 00:12:06,430
Đống phân loại, sắp xếp nhanh chóng, vỏ -

279
00:12:06,430 --> 00:12:09,480
vậy có vẻ như chúng tôi giới thiệu ba
tồi tệ nhất các thuật toán tuần trước.

280
00:12:09,480 --> 00:12:12,960
Nhưng đó là tốt mà chúng ta ở đây ngày hôm nay để
nhìn vào hợp nhất loại, trong đó là một trong những

281
00:12:12,960 --> 00:12:16,500
những người dễ dàng hơn là nhìn vào, thậm chí
mặc dù nó có thể sẽ uốn cong tâm trí của bạn

282
00:12:16,500 --> 00:12:17,490
chỉ cần một chút.

283
00:12:17,490 --> 00:12:21,130
Ở đây chúng ta có thể thấy chỉ có bao nhiêu
lựa chọn loại hút.

284
00:12:21,130 --> 00:12:24,600
>> Nhưng theo khía cạnh khác, đó là
thực sự dễ dàng để thực hiện.

285
00:12:24,600 --> 00:12:28,160
Và có thể cho P Set 3, đó là một trong những
các thuật toán bạn đã chọn để thực hiện

286
00:12:28,160 --> 00:12:28,960
cho phiên bản tiêu chuẩn.

287
00:12:28,960 --> 00:12:30,970
Hoàn toàn tốt đẹp, hoàn toàn chính xác.

288
00:12:30,970 --> 00:12:35,210
>> Nhưng một lần nữa, như n được lớn, nếu bạn
chọn để thực hiện một thuật toán nhanh hơn

289
00:12:35,210 --> 00:12:39,020
thích hợp nhất phân loại, tỷ lệ cược là trong lớn hơn và
đầu vào lớn hơn, mã của bạn chỉ là

290
00:12:39,020 --> 00:12:39,800
sẽ chạy nhanh hơn.

291
00:12:39,800 --> 00:12:41,090
Trang web của bạn sẽ làm việc tốt hơn.

292
00:12:41,090 --> 00:12:42,650
Người dùng của bạn sẽ được hạnh phúc hơn.

293
00:12:42,650 --> 00:12:45,280
Và do đó, có những tác dụng
của thực sự cho

294
00:12:45,280 --> 00:12:47,350
chúng tôi một số sâu suy nghĩ.

295
00:12:47,350 --> 00:12:49,990
>> Vì vậy, chúng ta hãy nhìn vào những gì hợp nhất
loại thực sự là tất cả về.

296
00:12:49,990 --> 00:12:52,992
Điều thú vị là hợp nhất
loại chỉ là thế này.

297
00:12:52,992 --> 00:12:56,300
Đây là, một lần nữa, những gì chúng tôi đã gọi
giả, con giả

298
00:12:56,300 --> 00:12:57,720
Cú pháp tiếng Anh như thế nào.

299
00:12:57,720 --> 00:12:59,890
Và đơn giản là
loại hấp dẫn.

300
00:12:59,890 --> 00:13:02,840
>> Vì vậy, trên đầu vào của n phần tử - để
chỉ có nghĩa là, đây là một mảng.

301
00:13:02,840 --> 00:13:04,000
Nó có mọi thứ n trong nó.

302
00:13:04,000 --> 00:13:05,370
Đó là tất cả chúng ta đang nói ở đó.

303
00:13:05,370 --> 00:13:07,560
>> Nếu n là ít hơn 2, quay trở lại.

304
00:13:07,560 --> 00:13:08,640
Vì vậy, đó chỉ là trường hợp tầm thường.

305
00:13:08,640 --> 00:13:12,580
Nếu n là ít hơn 2, thì rõ ràng đó là
1 hoặc 0, trong trường hợp này, điều

306
00:13:12,580 --> 00:13:14,780
đã được sắp xếp hay không tồn tại,
vì vậy chỉ cần quay trở lại.

307
00:13:14,780 --> 00:13:15,900
Không có gì để làm.

308
00:13:15,900 --> 00:13:18,360
Vì vậy, đó là một trường hợp đơn giản để nhổ ra.

309
00:13:18,360 --> 00:13:20,110
>> Khác, chúng tôi có ba bước.

310
00:13:20,110 --> 00:13:23,650
Sắp xếp nửa bên trái của các yếu tố, loại
nửa bên phải của các yếu tố,

311
00:13:23,650 --> 00:13:26,650
và sau đó hợp nhất hai nửa được sắp xếp.

312
00:13:26,650 --> 00:13:29,400
Điều thú vị ở đây là
Tôi là loại punting, phải không?

313
00:13:29,400 --> 00:13:32,300
Có loại một định nghĩa tròn
thuật toán này.

314
00:13:32,300 --> 00:13:35,986
Trong ý thức những gì là thuật toán của này
tròn nghĩa?

315
00:13:35,986 --> 00:13:37,850
>> ĐỐI TƯỢNG: [nghe được].

316
00:13:37,850 --> 00:13:41,670
>> DAVID Malan: Vâng, thuật toán sắp xếp của tôi,
hai bước của nó là "loại

317
00:13:41,670 --> 00:13:44,640
một cái gì đó. "Và như vậy đó đặt ra
câu hỏi, tốt, những gì tôi sẽ sử dụng

318
00:13:44,640 --> 00:13:46,460
để sắp xếp nửa bên trái
và nửa bên phải?

319
00:13:46,460 --> 00:13:49,600
Và vẻ đẹp ở đây là mặc dù
một lần nữa, đây là tâm-uốn

320
00:13:49,600 --> 00:13:54,030
một phần có khả năng, bạn có thể sử dụng cùng một
thuật toán sắp xếp nửa trái.

321
00:13:54,030 --> 00:13:54,700
>> Nhưng chờ một phút.

322
00:13:54,700 --> 00:13:57,070
Khi bạn đang nói để sắp xếp các
nửa bên trái, hai là những gì

323
00:13:57,070 --> 00:13:58,240
bước tiếp theo sẽ là?

324
00:13:58,240 --> 00:14:00,550
Chúng tôi sẽ sắp xếp nửa bên trái của
nửa bên trái và bên phải

325
00:14:00,550 --> 00:14:01,420
một nửa của một nửa trái.

326
00:14:01,420 --> 00:14:04,430
Chết tiệt, làm thế nào để sắp xếp hai
nửa, hoặc quý, bây giờ?

327
00:14:04,430 --> 00:14:05,260
>> Nhưng đó là OK.

328
00:14:05,260 --> 00:14:07,830
Chúng tôi có một thuật toán sắp xếp ở đây.

329
00:14:07,830 --> 00:14:10,660
Và mặc dù bạn có thể lo lắng ở
đầu tiên này là loại vô hạn

330
00:14:10,660 --> 00:14:12,780
vòng lặp, đó là một chu kỳ đó là không bao giờ
sẽ kết thúc - nó sẽ

331
00:14:12,780 --> 00:14:15,770
kết thúc khi những gì sẽ xảy ra?

332
00:14:15,770 --> 00:14:16,970
Một khi n là ít hơn 2.

333
00:14:16,970 --> 00:14:19,180
Mà cuối cùng sẽ xảy ra,
bởi vì nếu bạn giữ giảm một nửa và

334
00:14:19,180 --> 00:14:23,020
giảm một nửa trong giảm một nửa những nửa, chắc chắn
cuối cùng bạn sẽ kết thúc

335
00:14:23,020 --> 00:14:25,350
với chỉ 1 hoặc 0 yếu tố.

336
00:14:25,350 --> 00:14:28,500
Tại thời điểm đó, thuật toán này
nói rằng bạn đang thực hiện.

337
00:14:28,500 --> 00:14:31,020
>> Vì vậy, sự kỳ diệu thực trong này
thuật toán có vẻ là trong

338
00:14:31,020 --> 00:14:33,470
là bước cuối cùng, sáp nhập.

339
00:14:33,470 --> 00:14:37,190
Đó là ý tưởng đơn giản chỉ là sáp nhập hai
điều, đó là cuối cùng là những gì sẽ

340
00:14:37,190 --> 00:14:40,920
cho phép chúng tôi để sắp xếp một mảng của,
hãy nói, tám yếu tố.

341
00:14:40,920 --> 00:14:44,410
Vì vậy, tôi có tám quả bóng căng thẳng hơn lên
ở đây, tám miếng giấy, và một

342
00:14:44,410 --> 00:14:45,500
Google Glass -

343
00:14:45,500 --> 00:14:46,140
mà tôi nhận được để giữ.

344
00:14:46,140 --> 00:14:46,960
>> [Cười]

345
00:14:46,960 --> 00:14:48,970
>> DAVID Malan: Nếu chúng ta có thể mất tám
tình nguyện viên, và hãy xem liệu chúng ta có thể

346
00:14:48,970 --> 00:14:51,430
chơi này ra, vì vậy.

347
00:14:51,430 --> 00:14:52,500
Wow, OK.

348
00:14:52,500 --> 00:14:53,565
Khoa học máy tính là nhận được vui vẻ.

349
00:14:53,565 --> 00:14:54,320
Được rồi.

350
00:14:54,320 --> 00:14:57,770
Vì vậy, làm thế nào về bạn ba,
bàn tay lớn nhất ở đó.

351
00:14:57,770 --> 00:14:58,580
Bốn ở phía sau.

352
00:14:58,580 --> 00:15:02,220
Và làm thế nào về chúng tôi sẽ làm bạn
ba trong hàng này?

353
00:15:02,220 --> 00:15:03,390
Và bốn ở phía trước.

354
00:15:03,390 --> 00:15:04,920
Vì vậy, bạn tám, đi lên trên.

355
00:15:04,920 --> 00:15:12,060
>> [Cười]

356
00:15:12,060 --> 00:15:13,450
>> DAVID Malan: Tôi thực sự
không chắc chắn những gì nó được.

357
00:15:13,450 --> 00:15:14,810
Đó có phải là quả bóng căng thẳng?

358
00:15:14,810 --> 00:15:16,510
Các loại đèn bàn?

359
00:15:16,510 --> 00:15:18,650
Vật liệu?

360
00:15:18,650 --> 00:15:19,680
Internet?

361
00:15:19,680 --> 00:15:20,160
>> OK.

362
00:15:20,160 --> 00:15:21,310
Vì vậy, đến ngày lên.

363
00:15:21,310 --> 00:15:22,310
Ai muốn -

364
00:15:22,310 --> 00:15:23,570
tiếp tục đến.

365
00:15:23,570 --> 00:15:24,240
Chúng ta hãy xem.

366
00:15:24,240 --> 00:15:26,460
Và điều này đặt bạn vào vị trí -

367
00:15:26,460 --> 00:15:27,940
bạn đang ở trong vị trí một.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, chờ một phút.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - oh, tốt.

370
00:15:30,760 --> 00:15:31,310
Được rồi, chúng tôi đang tốt.

371
00:15:31,310 --> 00:15:35,130
Được rồi, vì vậy tất cả mọi người có một chỗ ngồi,
nhưng không phải trên kính Google.

372
00:15:35,130 --> 00:15:36,475
Hãy để tôi xếp hàng này lên.

373
00:15:36,475 --> 00:15:37,115
Tên của bạn là gì?

374
00:15:37,115 --> 00:15:37,440
>> Michelle: Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID Malan: Michelle?

376
00:15:38,090 --> 00:15:42,000
Tất cả các bên phải, bạn có thể trông giống như
đam mê, nếu đó là OK.

377
00:15:42,000 --> 00:15:44,625
Vâng, tôi cũng vậy, tôi cho rằng,
chỉ trong khoảnh khắc.

378
00:15:44,625 --> 00:15:45,875
Được rồi, chế độ chờ.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Chúng tôi đã cố gắng để đưa ra một
trường hợp sử dụng cho Google Glass, và chúng tôi

381
00:15:50,950 --> 00:15:53,750
nghĩ rằng nó sẽ được vui vẻ để chỉ cần làm
này khi mọi người trên sân khấu.

382
00:15:53,750 --> 00:15:57,120
Chúng tôi sẽ ghi lại thế giới
từ quan điểm của họ.

383
00:15:57,120 --> 00:15:58,410
Được rồi.

384
00:15:58,410 --> 00:15:59,830
Không lẽ là những gì Google dự định.

385
00:15:59,830 --> 00:16:02,260
Được rồi, nếu bạn không nhớ mặc
này cho lúng túng phút tiếp theo,

386
00:16:02,260 --> 00:16:03,150
đó sẽ là tuyệt vời.

387
00:16:03,150 --> 00:16:08,620
>> Được rồi, vì vậy chúng tôi có ở đây một loạt các
các yếu tố, và mảng, theo

388
00:16:08,620 --> 00:16:11,480
mảnh giấy với những kẻ '
bàn tay, hiện đang được phân loại.

389
00:16:11,480 --> 00:16:12,050
>> Michelle: Ồ, thật là kỳ lạ.

390
00:16:12,050 --> 00:16:12,810
>> DAVID Malan: Đó là khá nhiều ngẫu nhiên.

391
00:16:12,810 --> 00:16:15,760
Và chỉ trong một thời điểm, chúng tôi sẽ cố gắng
thực hiện hợp nhất phân loại lại với nhau

392
00:16:15,760 --> 00:16:17,950
và nhìn thấy nơi đó chính là cái nhìn sâu sắc.

393
00:16:17,950 --> 00:16:21,970
Và các trick ở đây với hợp nhất là loại
một cái gì đó mà chúng tôi đã không giả định được nêu ra.

394
00:16:21,970 --> 00:16:24,030
Chúng tôi thực sự cần một số
không gian bổ sung.

395
00:16:24,030 --> 00:16:26,650
Vì vậy, những gì đang có được đặc biệt
quan tâm ở đây là những

396
00:16:26,650 --> 00:16:29,270
kẻ sẽ di chuyển xung quanh một chút
chút, bởi vì tôi sẽ cho rằng

397
00:16:29,270 --> 00:16:31,880
có một mảng thêm không gian,
nói, ngay sau họ.

398
00:16:31,880 --> 00:16:34,570
>> Vì vậy, nếu họ đang đứng sau ghế của mình,
đó là mảng thứ cấp.

399
00:16:34,570 --> 00:16:36,960
Nếu họ đang ngồi ở đây, đó là
mảng chính.

400
00:16:36,960 --> 00:16:40,170
Nhưng đây là một nguồn tài nguyên mà chúng ta có
không thừa hưởng vậy, đến nay với bong bóng

401
00:16:40,170 --> 00:16:42,040
sắp xếp, với các lựa chọn sắp xếp,
với sắp xếp chèn.

402
00:16:42,040 --> 00:16:44,600
Nhớ lại tuần trước, tất cả mọi người chỉ
loại xáo trộn tại chỗ.

403
00:16:44,600 --> 00:16:46,840
Họ không sử dụng bất kỳ bộ nhớ bổ sung.

404
00:16:46,840 --> 00:16:49,310
Chúng tôi đã làm chỗ cho mọi người bằng cách
di chuyển những người xung quanh.

405
00:16:49,310 --> 00:16:50,580
>> Vì vậy, đây là một cái nhìn sâu sắc quan trọng, quá.

406
00:16:50,580 --> 00:16:53,410
Có này cân bằng, nói chung trong
khoa học máy tính, các nguồn tài nguyên.

407
00:16:53,410 --> 00:16:55,800
Nếu bạn muốn tăng tốc độ một cái gì đó
như thời gian, bạn sẽ

408
00:16:55,800 --> 00:16:56,900
phải trả một giá.

409
00:16:56,900 --> 00:17:00,750
Và một trong những giá là rất thường xuyên
không gian, số lượng bộ nhớ hoặc cứng

410
00:17:00,750 --> 00:17:01,700
không gian đĩa mà bạn đang sử dụng.

411
00:17:01,700 --> 00:17:03,640
Hoặc, thẳng thắn, số tiền
thời gian lập trình.

412
00:17:03,640 --> 00:17:06,700
Bao nhiêu thời gian nó sẽ đưa bạn, con người,
để thực sự thực hiện một số chi tiết

413
00:17:06,700 --> 00:17:07,829
thuật toán phức tạp.

414
00:17:07,829 --> 00:17:09,760
Nhưng ngày hôm nay, thương mại-off
là thời gian và không gian.

415
00:17:09,760 --> 00:17:11,930
>> Vì vậy, nếu các bạn chỉ có thể giữ lên của bạn
số vì vậy chúng tôi có thể thấy rằng bạn đang

416
00:17:11,930 --> 00:17:15,839
thực sự phù hợp với 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Tuyệt vời.

418
00:17:16,599 --> 00:17:19,520
Vì vậy, tôi sẽ cố gắng dàn xếp
điều, nếu các bạn có thể chỉ cần

419
00:17:19,520 --> 00:17:21,800
theo sự hướng dẫn của tôi ở đây.

420
00:17:21,800 --> 00:17:26,650
>> Vì vậy, tôi sẽ thực hiện, đầu tiên,
Bước đầu tiên của mã giả, đó là

421
00:17:26,650 --> 00:17:29,440
trên đầu vào của n phần tử, nếu n là
ít hơn 2, sau đó quay trở lại.

422
00:17:29,440 --> 00:17:31,370
Rõ ràng, đó không
áp dụng, vì vậy chúng tôi di chuyển trên.

423
00:17:31,370 --> 00:17:33,340
Vì vậy, sắp xếp nửa bên trái của các yếu tố.

424
00:17:33,340 --> 00:17:36,220
Vì vậy, có nghĩa là tôi sẽ tập trung của tôi
sự chú ý cho một thời điểm trên những

425
00:17:36,220 --> 00:17:37,310
bốn chàng trai ở đây.

426
00:17:37,310 --> 00:17:39,774
Được rồi, tôi làm những gì tiếp theo làm gì?

427
00:17:39,774 --> 00:17:40,570
>> ĐỐI TƯỢNG: Sắp xếp nửa trái.

428
00:17:40,570 --> 00:17:42,780
>> DAVID Malan: Vì vậy, bây giờ tôi phải sắp xếp
nửa bên trái của những kẻ.

429
00:17:42,780 --> 00:17:45,580
Bởi vì một lần nữa, giả định cho mình những
Mục đích là để sắp xếp một nửa trái.

430
00:17:45,580 --> 00:17:46,440
Làm thế nào để bạn làm điều đó?

431
00:17:46,440 --> 00:17:49,140
Chỉ cần làm theo các hướng dẫn, thậm chí
mặc dù chúng tôi đang làm điều đó một lần nữa.

432
00:17:49,140 --> 00:17:50,160
Vì vậy, sắp xếp nửa trái.

433
00:17:50,160 --> 00:17:52,030
Bây giờ tôi sắp xếp hai chàng trai.

434
00:17:52,030 --> 00:17:53,563
Những gì xảy ra tiếp theo?

435
00:17:53,563 --> 00:17:54,510
>> ĐỐI TƯỢNG: Sắp xếp nửa trái.

436
00:17:54,510 --> 00:17:55,460
>> DAVID Malan: Sắp xếp nửa trái.

437
00:17:55,460 --> 00:18:00,680
Vì vậy, bây giờ này, chỗ này đây,
là một danh sách các kích thước 1.

438
00:18:00,680 --> 00:18:01,365
Và tên của bạn là gì nữa?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Công chúa Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID Malan: Công chúa Daisy là đây.

441
00:18:03,690 --> 00:18:07,470
Và vì vậy cô đã được sắp xếp, bởi vì
danh sách có kích thước 1.

442
00:18:07,470 --> 00:18:09,490
Tôi phải làm gì tiếp theo làm gì?

443
00:18:09,490 --> 00:18:13,680
OK, quay trở lại, bởi vì danh sách đó là của
kích thước 1, đó là ít hơn 2.

444
00:18:13,680 --> 00:18:14,320
Sau đó, bước tiếp theo là gì?

445
00:18:14,320 --> 00:18:17,490
Và bây giờ bạn phải loại
quay lại trong tâm trí của bạn.

446
00:18:17,490 --> 00:18:19,340
>> Sắp xếp nửa bên phải, đó là -

447
00:18:19,340 --> 00:18:19,570
Tên của bạn là gì?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID Malan: Linda.

450
00:18:20,980 --> 00:18:23,210
Và do đó chúng ta làm gì bây giờ
chúng tôi có một danh sách các kích thước 1?

451
00:18:23,210 --> 00:18:24,440
>> ĐỐI TƯỢNG: Trở về.

452
00:18:24,440 --> 00:18:24,760
>> DAVID Malan: cẩn thận.

453
00:18:24,760 --> 00:18:29,540
Chúng tôi quay trở lại đầu tiên, và bây giờ là thứ ba
bước - và nếu tôi loại mô tả nó bằng cách

454
00:18:29,540 --> 00:18:33,490
ôm lấy hai chỗ ngồi bây giờ, bây giờ tôi
phải kết hợp hai yếu tố này.

455
00:18:33,490 --> 00:18:35,530
Vì vậy, bây giờ không may, các yếu tố
là ra lệnh.

456
00:18:35,530 --> 00:18:39,920
Nhưng đó là nơi quá trình sáp nhập
bắt đầu để có được hấp dẫn.

457
00:18:39,920 --> 00:18:42,410
>> Vì vậy, nếu các bạn có thể đứng lên chỉ
một thời điểm, tôi sẽ cần bạn, trong một

458
00:18:42,410 --> 00:18:44,170
thời điểm, bước đằng sau ghế của bạn.

459
00:18:44,170 --> 00:18:46,480
Và nếu Linda, bởi vì 2 là
nhỏ hơn 4, tại sao không

460
00:18:46,480 --> 00:18:48,130
bạn đi xung quanh đầu tiên?

461
00:18:48,130 --> 00:18:48,690
Ở lại đó.

462
00:18:48,690 --> 00:18:50,520
Vì vậy, Linda, bạn đi xung quanh đầu tiên.

463
00:18:50,520 --> 00:18:53,820
>> Bây giờ trong thực tế nếu nó chỉ là một mảng
chúng tôi chỉ có thể di chuyển của cô trong thời gian thực

464
00:18:53,820 --> 00:18:55,360
từ ghế này đến chỗ này.

465
00:18:55,360 --> 00:18:57,770
Vì vậy, hãy tưởng tượng rằng lấy một số không đổi
số bước 1.

466
00:18:57,770 --> 00:18:58,480
Và bây giờ -

467
00:18:58,480 --> 00:19:01,490
nhưng chúng ta cần phải đưa bạn vào
vị trí đầu tiên ở đây.

468
00:19:01,490 --> 00:19:03,930
>> Và bây giờ nếu bạn có thể đi xung quanh,
là tốt, chúng ta sẽ

469
00:19:03,930 --> 00:19:06,300
được vị trí hai.

470
00:19:06,300 --> 00:19:09,120
Và mặc dù điều này cảm thấy như đó là
một khoảng thời gian, những gì tốt đẹp hiện nay là

471
00:19:09,120 --> 00:19:14,710
rằng nửa bên trái của
nửa bên trái bây giờ được sắp xếp.

472
00:19:14,710 --> 00:19:18,010
Vì vậy, những gì đã được bước tiếp theo, nếu chúng ta bây giờ
tua lại tiếp tục trong câu chuyện này?

473
00:19:18,010 --> 00:19:18,980
>> ĐỐI TƯỢNG: phải nửa.

474
00:19:18,980 --> 00:19:19,900
>> DAVID Malan: Sắp xếp đúng một nửa.

475
00:19:19,900 --> 00:19:21,320
Vì vậy, các bạn phải làm điều này, là tốt.

476
00:19:21,320 --> 00:19:23,510
Vì vậy, nếu bạn có thể đứng lên
cho một thời điểm?

477
00:19:23,510 --> 00:19:25,192
Và tên của bạn là gì?

478
00:19:25,192 --> 00:19:25,540
>> JESS: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID Malan: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, vì vậy Jess hiện đang là trái
một nửa của nửa bên phải.

481
00:19:29,720 --> 00:19:31,400
Và vì vậy cô ấy là một danh sách các kích thước 1.

482
00:19:31,400 --> 00:19:32,380
Cô ấy rõ ràng là sắp xếp.

483
00:19:32,380 --> 00:19:33,070
Và tên của bạn một lần nữa?

484
00:19:33,070 --> 00:19:33,630
>> Michelle: Michelle.

485
00:19:33,630 --> 00:19:35,340
>> DAVID Malan: Michelle là rõ ràng
một danh sách các kích thước 1.

486
00:19:35,340 --> 00:19:36,050
Cô ấy đã được sắp xếp.

487
00:19:36,050 --> 00:19:38,690
Vì vậy, bây giờ sự kỳ diệu xảy ra,
quá trình sáp nhập.

488
00:19:38,690 --> 00:19:39,790
Vì vậy, ai sẽ đến trước?

489
00:19:39,790 --> 00:19:41,560
Rõ ràng là Michelle.

490
00:19:41,560 --> 00:19:43,280
Vì vậy, nếu bạn có thể đi xung quanh trở lại.

491
00:19:43,280 --> 00:19:47,090
Không gian, chúng tôi đã có sẵn cho cô ấy bây giờ
là ngay phía sau ghế này đây.

492
00:19:47,090 --> 00:19:51,580
Và bây giờ nếu bạn có thể trở lại là tốt,
bây giờ chúng ta có, để được rõ ràng, hai

493
00:19:51,580 --> 00:19:53,810
nửa, mỗi kích thước 2 -

494
00:19:53,810 --> 00:19:57,090
và chỉ vì lợi ích của mô tả, nếu bạn
có thể làm cho một chút của một không gian -

495
00:19:57,090 --> 00:19:59,780
còn ai nửa đây,
nửa bên phải ở đây.

496
00:19:59,780 --> 00:20:01,160
>> Tua lại tiếp tục trong câu chuyện.

497
00:20:01,160 --> 00:20:02,270
Bước gì tiếp theo?

498
00:20:02,270 --> 00:20:03,030
>> ĐỐI TƯỢNG: Merge.

499
00:20:03,030 --> 00:20:04,160
>> DAVID Malan: Vì vậy, bây giờ chúng ta phải hợp nhất.

500
00:20:04,160 --> 00:20:07,490
Vì vậy, OK, vì vậy bây giờ, may mắn thay, chúng tôi
chỉ giải phóng lên bốn ghế.

501
00:20:07,490 --> 00:20:11,480
Vì vậy, chúng tôi đã sử dụng gấp đôi bộ nhớ, nhưng
chúng tôi có thể cung cấp cho thể đảo ngược giữa

502
00:20:11,480 --> 00:20:12,330
hai mảng.

503
00:20:12,330 --> 00:20:14,190
Vì vậy, con số nào thì đến đầu tiên?

504
00:20:14,190 --> 00:20:14,850
Vì vậy, Michelle, rõ ràng.

505
00:20:14,850 --> 00:20:16,680
Vì vậy, đến xung quanh và mất
chỗ ngồi của bạn ở đây.

506
00:20:16,680 --> 00:20:19,120
Và sau đó số 2 là rõ ràng
tiếp theo, vì vậy bạn đến đây.

507
00:20:19,120 --> 00:20:21,520
Số 4, số 6.

508
00:20:21,520 --> 00:20:23,390
Và một lần nữa, mặc dù có một
chút đi bộ có liên quan,

509
00:20:23,390 --> 00:20:26,010
thực sự, đây có thể xảy ra ngay lập tức,
bằng cách di chuyển một -

510
00:20:26,010 --> 00:20:26,880
OK, cũng chơi.

511
00:20:26,880 --> 00:20:28,350
>> [Cười]

512
00:20:28,350 --> 00:20:29,680
>> DAVID Malan: Và bây giờ chúng tôi
trong hình dạng khá tốt.

513
00:20:29,680 --> 00:20:34,910
Nửa bên trái của toàn bộ
đầu vào đã được sắp xếp.

514
00:20:34,910 --> 00:20:37,370
Được rồi, vì vậy những kẻ có
lợi thế của tôi -

515
00:20:37,370 --> 00:20:40,340
làm thế nào nó kết thúc tất cả các cô gái trên
trái và tất cả các chàng trai bên phải?

516
00:20:40,340 --> 00:20:42,450
>> OK, vì vậy chàng trai 'biến ngay bây giờ.

517
00:20:42,450 --> 00:20:44,680
Vì vậy, tôi sẽ không hướng dẫn bạn qua
các bước sau.

518
00:20:44,680 --> 00:20:46,550
Chúng ta sẽ thấy nếu chúng ta có thể nộp đơn xin lại
cùng giả.

519
00:20:46,550 --> 00:20:50,050
Nếu bạn muốn đi trước và đứng lên,
và các bạn, hãy để tôi cung cấp cho bạn mic.

520
00:20:50,050 --> 00:20:52,990
Xem nếu bạn không thể tái tạo những gì
chúng ta chỉ cần làm ở đây trên

521
00:20:52,990 --> 00:20:53,880
đầu kia của danh sách.

522
00:20:53,880 --> 00:20:59,530
Ai có nhu cầu nói chuyện đầu tiên,
dựa trên các thuật toán?

523
00:20:59,530 --> 00:21:03,210
Vì vậy, giải thích những gì bạn đang làm trước
bạn thực hiện bất kỳ chuyển động chân.

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1: Được rồi, như vậy kể từ
Tôi là một nửa bên trái của

525
00:21:05,930 --> 00:21:07,790
nửa bên trái, tôi quay trở lại.

526
00:21:07,790 --> 00:21:08,730
Phải không?

527
00:21:08,730 --> 00:21:09,250
>> DAVID Malan: Tốt.

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1: Và sau đó -

529
00:21:10,350 --> 00:21:11,800
>> DAVID Malan: Ai làm
mic đi đến tiếp theo?

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1: số kế tiếp.

531
00:21:12,920 --> 00:21:14,720
>> SPEAKER 2: Vì vậy, tôi nửa bên phải
nửa bên trái của

532
00:21:14,720 --> 00:21:17,830
nửa bên trái, và tôi quay trở lại.

533
00:21:17,830 --> 00:21:18,050
>> DAVID Malan: Tốt.

534
00:21:18,050 --> 00:21:18,550
Bạn quay trở lại.

535
00:21:18,550 --> 00:21:21,855
Vì vậy bây giờ lên tới cho bạn hai là những gì?

536
00:21:21,855 --> 00:21:23,740
>> SPEAKER 2: Chúng tôi muốn xem ai là nhỏ hơn.

537
00:21:23,740 --> 00:21:24,200
>> DAVID Malan: Chính xác.

538
00:21:24,200 --> 00:21:24,940
Chúng tôi muốn kết hợp.

539
00:21:24,940 --> 00:21:27,590
Không gian chúng ta sẽ sử dụng để hợp nhất
bạn vào, mặc dù họ

540
00:21:27,590 --> 00:21:30,250
rõ ràng là đã được sắp xếp, chúng ta sẽ
theo cùng một thuật toán.

541
00:21:30,250 --> 00:21:31,560
Vì vậy, những người đi ở phía trước?

542
00:21:31,560 --> 00:21:35,720
Vì vậy, 3, và sau đó 7.

543
00:21:35,720 --> 00:21:38,570
Và bây giờ là mic đi
để những kẻ, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Vì vậy, tôi nửa bên phải của
nửa bên trái, và n của tôi là ít hơn

545
00:21:43,590 --> 00:21:45,048
1, vì vậy tôi chỉ cần đi để vượt qua -

546
00:21:45,048 --> 00:21:46,380
>> DAVID Malan: Tốt.

547
00:21:46,380 --> 00:21:49,450
>> SPEAKER 4: Tôi là một nửa bên phải của
nửa bên phải của nửa bên phải, và tôi

548
00:21:49,450 --> 00:21:51,740
cũng là một người, vì vậy tôi
sẽ trở lại.

549
00:21:51,740 --> 00:21:52,990
Vì vậy, bây giờ chúng tôi hợp nhất.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Vì vậy, chúng tôi quay trở lại.

552
00:21:56,150 --> 00:21:57,160
>> DAVID Malan: Vì vậy, bạn đi vào phía sau.

553
00:21:57,160 --> 00:21:59,200
Vì vậy, 5 đi đầu tiên, sau đó 8.

554
00:21:59,200 --> 00:22:01,240
Và bây giờ khán giả, đó là
bước chúng ta phải bây giờ quay lại

555
00:22:01,240 --> 00:22:02,200
sao để trong tâm trí của chúng tôi?

556
00:22:02,200 --> 00:22:02,940
>> ĐỐI TƯỢNG: Merge.

557
00:22:02,940 --> 00:22:07,270
>> DAVID Malan: sáp nhập nửa trái và phải
một nửa của một nửa trái ban đầu.

558
00:22:07,270 --> 00:22:08,840
Vì vậy, bây giờ -

559
00:22:08,840 --> 00:22:10,520
và chỉ để làm cho rõ ràng,
làm cho một ít không gian

560
00:22:10,520 --> 00:22:11,690
giữa hai chàng trai.

561
00:22:11,690 --> 00:22:13,800
Vì vậy, bây giờ đó là hai danh sách,
trái và phải.

562
00:22:13,800 --> 00:22:18,320
Vì vậy, làm thế nào để chúng ta hợp nhất các bạn vào
hàng ghế đầu của ghế một lần nữa?

563
00:22:18,320 --> 00:22:19,600
>> 3 đi đầu tiên.

564
00:22:19,600 --> 00:22:20,850
Sau đó, 5, rõ ràng.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Sau đó, 7, và bây giờ 8.

567
00:22:27,330 --> 00:22:28,710
OK, và bây giờ chúng tôi?

568
00:22:28,710 --> 00:22:29,650
>> ĐỐI TƯỢNG: Không thực hiện.

569
00:22:29,650 --> 00:22:32,440
>> DAVID Malan: Không thực hiện, bởi vì
rõ ràng, có một bước còn lại.

570
00:22:32,440 --> 00:22:35,720
Nhưng một lần nữa, lý do tôi đang sử dụng này
thuật ngữ như "tua lại trong tâm trí của bạn,"

571
00:22:35,720 --> 00:22:37,160
đó là bởi vì đó là thực sự
những gì đang xảy ra.

572
00:22:37,160 --> 00:22:39,610
Chúng tôi đang trải qua tất cả các bước,
nhưng chúng tôi đang sắp xếp tạm dừng cho một

573
00:22:39,610 --> 00:22:42,480
thời điểm, lặn sâu hơn vào
thuật toán, tạm dừng một lúc,

574
00:22:42,480 --> 00:22:45,840
lặn sâu hơn vào các thuật toán, và
bây giờ chúng tôi phải sắp xếp của tua lại trong chúng tôi

575
00:22:45,840 --> 00:22:49,430
tâm trí và quay lại tất cả các lớp
mà chúng tôi đã loại tay vào.

576
00:22:49,430 --> 00:22:51,790
>> Vì vậy, bây giờ chúng tôi có hai danh sách có kích thước 4.

577
00:22:51,790 --> 00:22:54,790
Nếu các bạn có thể đứng lên một lần cuối cùng
và làm cho một chút không gian ở đây để

578
00:22:54,790 --> 00:22:57,230
làm cho rõ ràng rằng đây là trái
một nửa của bản gốc,

579
00:22:57,230 --> 00:22:58,620
nửa bên phải của bản gốc.

580
00:22:58,620 --> 00:23:01,060
Ai là số đầu tiên mà chúng tôi
cần phải kéo vào phía sau?

581
00:23:01,060 --> 00:23:01,870
Michelle, tất nhiên.

582
00:23:01,870 --> 00:23:03,230
>> Vì vậy, chúng tôi đưa Michelle đây.

583
00:23:03,230 --> 00:23:05,080
Và những người có số 2?

584
00:23:05,080 --> 00:23:06,440
Số 2 đi kèm trên lại là tốt.

585
00:23:06,440 --> 00:23:07,800
Số 3?

586
00:23:07,800 --> 00:23:08,510
Tuyệt vời.

587
00:23:08,510 --> 00:23:16,570
Số 4, số 5, số 6,
số 7 và số 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, vì vậy nó cảm thấy như rất nhiều
các bước, chắc chắn.

589
00:23:18,850 --> 00:23:22,390
Nhưng bây giờ chúng ta hãy xem nếu chúng tôi không thể xác nhận
loại trực giác rằng điều này

590
00:23:22,390 --> 00:23:26,190
thuật toán cơ bản, đặc biệt là
n được thực sự lớn, như chúng ta đã thấy

591
00:23:26,190 --> 00:23:29,170
với những hình ảnh động, là
về cơ bản nhanh hơn.

592
00:23:29,170 --> 00:23:33,400
Vì vậy, tôi khẳng định thuật toán này, trong điều tồi tệ nhất
trường hợp và thậm chí cả trong trường hợp tốt nhất,

593
00:23:33,400 --> 00:23:36,160
là O lớn của n lần log n.

594
00:23:36,160 --> 00:23:39,160
Đó là, có một số khía cạnh của này
thuật toán mà phải mất n bước, nhưng

595
00:23:39,160 --> 00:23:43,110
có một khía cạnh khác nơi nào đó trong
đó lặp đi lặp lại, vòng lặp đó, mà

596
00:23:43,110 --> 00:23:44,410
có log n bước.

597
00:23:44,410 --> 00:23:49,154
Chúng ta có thể đặt ngón tay của chúng tôi về những gì những
hai con số được đề cập đến?

598
00:23:49,154 --> 00:23:51,320
Vâng, nơi -

599
00:23:51,320 --> 00:23:54,160
đi đâu rồi cầm mic đi?

600
00:23:54,160 --> 00:23:58,660
>> SPEAKER 1: Liệu đăng nhập n là
phá vỡ chúng thành hai -

601
00:23:58,660 --> 00:23:59,630
chia hai, về cơ bản.

602
00:23:59,630 --> 00:24:00,120
>> DAVID Malan: Chính xác.

603
00:24:00,120 --> 00:24:03,000
Bất cứ lúc nào chúng ta thấy trong bất kỳ thuật toán như vậy,
đến nay, đã có mô hình này

604
00:24:03,000 --> 00:24:04,200
phân chia, phân chia, phân chia.

605
00:24:04,200 --> 00:24:05,700
Và nó thường được giảm
để một cái gì đó

606
00:24:05,700 --> 00:24:07,100
logarit, đăng nhập cơ sở 2.

607
00:24:07,100 --> 00:24:10,180
Nhưng nó thực sự có thể là bất cứ điều gì,
nhưng đăng nhập cơ sở 2.

608
00:24:10,180 --> 00:24:11,330
>> Bây giờ những gì về n?

609
00:24:11,330 --> 00:24:14,550
Tôi có thể thấy rằng chúng tôi loại chia bạn
kẻ - chia bạn, chia bạn,

610
00:24:14,550 --> 00:24:15,910
chia bạn, chia bạn.

611
00:24:15,910 --> 00:24:18,760
Trường hợp nào cuối cùng đến từ đâu?

612
00:24:18,760 --> 00:24:19,810
>> Vì vậy, đó là sáp nhập.

613
00:24:19,810 --> 00:24:20,610
Bởi vì suy nghĩ về nó.

614
00:24:20,610 --> 00:24:25,420
Khi bạn kết hợp tám người với nhau,
trong đó một nửa trong số đó là một bộ bốn

615
00:24:25,420 --> 00:24:27,770
và một nửa khác là khác
bộ bốn, làm thế nào để bạn đi

616
00:24:27,770 --> 00:24:28,820
về làm việc sáp nhập?

617
00:24:28,820 --> 00:24:30,830
Vâng, các bạn đã làm nó
khá trực quan.

618
00:24:30,830 --> 00:24:34,140
>> Nhưng nếu tôi thay vì làm điều đó nhiều hơn một chút
có phương pháp, tôi có thể chỉ vào

619
00:24:34,140 --> 00:24:38,090
người ngoài cùng bên trái đầu tiên với trái của tôi
tay, chỉ vào người ngoài cùng bên trái

620
00:24:38,090 --> 00:24:42,080
của một nửa với bàn tay phải của tôi, và
chỉ sau đó đi qua

621
00:24:42,080 --> 00:24:46,990
danh sách, chỉ vào phần tử nhỏ nhất
mỗi thời gian, di chuyển ngón tay của tôi hơn và

622
00:24:46,990 --> 00:24:48,970
hơn là cần thiết trong suốt danh sách.

623
00:24:48,970 --> 00:24:51,890
Nhưng điều quan trọng về việc sáp nhập này
quá trình là tôi so sánh những cặp

624
00:24:51,890 --> 00:24:53,460
các yếu tố.

625
00:24:53,460 --> 00:24:57,270
Từ nửa bên phải và từ bên trái
một nửa, tôi sẽ không bao giờ một lần thụt lùi.

626
00:24:57,270 --> 00:25:00,570
>> Vì vậy, việc hợp nhất chính nó được dùng
không quá n bước.

627
00:25:00,570 --> 00:25:03,250
Và bao nhiêu lần tôi có
để làm điều đó sáp nhập?

628
00:25:03,250 --> 00:25:07,150
Vâng, không quá n, và chúng tôi chỉ
thấy rằng với sự hợp nhất thức.

629
00:25:07,150 --> 00:25:13,120
Và vì vậy nếu bạn làm điều gì đó mà có
đăng nhập n bước n lần, hoặc ngược lại,

630
00:25:13,120 --> 00:25:15,210
nó sẽ cung cấp cho chúng tôi n lần log n.

631
00:25:15,210 --> 00:25:16,310
>> Và tại sao điều này tốt hơn?

632
00:25:16,310 --> 00:25:19,600
Vâng, nếu chúng ta đã biết bản ghi
n là tốt hơn so với n - phải không?

633
00:25:19,600 --> 00:25:22,590
Chúng ta đã thấy trong tìm kiếm nhị phân, danh bạ điện thoại
Ví dụ, đăng nhập n là chắc chắn

634
00:25:22,590 --> 00:25:23,760
tốt hơn so với tuyến tính.

635
00:25:23,760 --> 00:25:28,420
Vì vậy, có nghĩa là n lần đăng nhập n là
chắc chắn tốt hơn so với n lần khác

636
00:25:28,420 --> 00:25:30,390
n, AKA n bình phương.

637
00:25:30,390 --> 00:25:32,400
Và đó là cuối cùng những gì chúng tôi cảm thấy.

638
00:25:32,400 --> 00:25:34,928
>> Vòng quá lớn của tiếng vỗ tay, nếu
chúng ta có thể, những người này.

639
00:25:34,928 --> 00:25:38,920
>> [Vỗ tay]

640
00:25:38,920 --> 00:25:41,550
>> DAVID Malan: Và món quà chia tay của bạn -
bạn có thể giữ cho các con số,

641
00:25:41,550 --> 00:25:44,010
nếu bạn muốn.

642
00:25:44,010 --> 00:25:45,620
Và món quà chia tay của bạn, như thường lệ.

643
00:25:45,620 --> 00:25:47,290
Oh, và chúng tôi sẽ gửi cho bạn
các cảnh quay, Michelle.

644
00:25:47,290 --> 00:25:48,343
Cảm ơn bạn.

645
00:25:48,343 --> 00:25:49,250
Được rồi.

646
00:25:49,250 --> 00:25:50,400
Giúp mình để một quả bóng căng thẳng.

647
00:25:50,400 --> 00:25:54,110
>> Và cho tôi kéo lên, trong khi đó,
người bạn của chúng tôi Rob Bowden cung cấp

648
00:25:54,110 --> 00:25:59,520
quan điểm hơi khác nhau về điều này,
vì bạn có thể suy nghĩ về những

649
00:25:59,520 --> 00:26:01,280
bước xảy ra trong một phần nào
cách khác nhau.

650
00:26:01,280 --> 00:26:04,750
Trong thực tế, các thiết lập cho những gì Rob là về
để cho chúng ta giả định rằng chúng tôi đã

651
00:26:04,750 --> 00:26:09,030
đã thực hiện các phân chia của
danh sách lớn thành tám danh sách nhỏ,

652
00:26:09,030 --> 00:26:10,570
mỗi kích thước 1.

653
00:26:10,570 --> 00:26:13,350
>> Vì vậy, chúng tôi đang thay đổi một giả
chút chỉ để sắp xếp của có được ở các

654
00:26:13,350 --> 00:26:15,320
ý tưởng cốt lõi của cách thức hoạt động sáp nhập.

655
00:26:15,320 --> 00:26:17,600
Nhưng thời gian chạy của những gì
anh đang làm là vẫn còn

656
00:26:17,600 --> 00:26:19,110
sẽ được như vậy.

657
00:26:19,110 --> 00:26:23,540
Và một lần nữa, các thiết lập ở đây là anh ấy
bắt đầu với tám danh sách các kích thước 1.

658
00:26:23,540 --> 00:26:27,730
Vì vậy, bạn đã bị mất một phần nơi ông là
thực sự thực hiện các log n, n log, log n

659
00:26:27,730 --> 00:26:31,205
phân chia của đầu vào.

660
00:26:31,205 --> 00:26:32,120
>> [VIDEO xem lại]

661
00:26:32,120 --> 00:26:33,615
>> -Đó là nó cho bước một.

662
00:26:33,615 --> 00:26:38,270
Đối với bước hai, nhiều lần
kết hợp cặp danh sách.

663
00:26:38,270 --> 00:26:39,210
>> DAVID Malan: Hm.

664
00:26:39,210 --> 00:26:41,270
Chỉ có âm thanh là đến
ra khỏi máy tính của tôi.

665
00:26:41,270 --> 00:26:42,520
Hãy thử này một lần nữa.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Chỉ cần tùy tiện chọn đó -
bây giờ chúng tôi có bốn danh sách.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Tìm hiểu trước.

670
00:26:52,120 --> 00:26:53,040
>> DAVID Malan: Hiện chúng tôi đi.

671
00:26:53,040 --> 00:27:00,510
>> -Kết hợp 108 và 15, chúng tôi kết thúc
với danh sách 15, 108.

672
00:27:00,510 --> 00:27:07,170
Sáp nhập 50 và 4, chúng tôi
kết thúc với 4, 50.

673
00:27:07,170 --> 00:27:12,990
Sáp nhập 8 và 42, chúng tôi
kết thúc với 8, 42.

674
00:27:12,990 --> 00:27:19,970
Và sáp nhập 23 và 16, chúng tôi
kết thúc với 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Bây giờ tất cả danh sách của chúng tôi có kích thước 2.

676
00:27:23,270 --> 00:27:26,690
Chú ý rằng mỗi
bốn danh sách được sắp xếp.

677
00:27:26,690 --> 00:27:29,450
Vì vậy, chúng ta có thể bắt đầu sáp nhập
cặp danh sách một lần nữa.

678
00:27:29,450 --> 00:27:38,420
Sáp nhập 15 và 108 và 4 và 50, chúng tôi
đầu tiên lấy 4, sau đó 15, sau đó

679
00:27:38,420 --> 00:27:41,500
50, sau đó là 108.

680
00:27:41,500 --> 00:27:50,610
Sáp nhập 8, 42 và 16, 23, đầu tiên chúng tôi thực hiện
8, sau đó là 16, sau đó 23,

681
00:27:50,610 --> 00:27:52,700
sau đó là 42.

682
00:27:52,700 --> 00:27:57,600
>> Vì vậy, bây giờ chúng tôi chỉ có hai danh sách các kích thước
4, mỗi trong số đó được sắp xếp.

683
00:27:57,600 --> 00:28:01,170
Vì vậy, bây giờ chúng ta hợp nhất hai danh sách này.

684
00:28:01,170 --> 00:28:11,835
Đầu tiên, chúng ta lấy 4, sau đó chúng tôi đi
8, sau đó chúng ta lấy 15, sau đó 16, sau đó

685
00:28:11,835 --> 00:28:19,456
23, sau đó 42, sau đó 50, sau đó 108.

686
00:28:19,456 --> 00:28:19,872
>> [END xem video]

687
00:28:19,872 --> 00:28:23,430
>> DAVID Malan: Một lần nữa, thông báo, ông không bao giờ
chạm vào một tách cho nhiều hơn một thời gian

688
00:28:23,430 --> 00:28:24,860
sau khi tiến xa hơn nữa.

689
00:28:24,860 --> 00:28:26,200
Vì vậy, ông không bao giờ lặp lại.

690
00:28:26,200 --> 00:28:29,850
Vì vậy ông ta luôn luôn di chuyển sang một bên,
và đó là nơi chúng tôi có n của chúng tôi.

691
00:28:29,850 --> 00:28:33,290
>> Tại sao không cho tôi kéo lên một hình ảnh động
mà chúng ta đã thấy trước đó, nhưng lần này

692
00:28:33,290 --> 00:28:35,110
chỉ tập trung vào việc hợp nhất loại.

693
00:28:35,110 --> 00:28:38,030
Hãy để tôi đi trước và phóng to
trong này đây.

694
00:28:38,030 --> 00:28:42,530
Trước tiên cho tôi chọn một đầu vào ngẫu nhiên,
phóng đại này, và bạn có thể sắp xếp của thấy

695
00:28:42,530 --> 00:28:46,600
những gì chúng tôi đã cho các cấp, trước đó,
hợp nhất phân loại là thực sự làm.

696
00:28:46,600 --> 00:28:50,330
>> Vì vậy, nhận thấy rằng bạn có được những nửa hoặc
các khu vực này hoặc những phần tám của

697
00:28:50,330 --> 00:28:53,140
vấn đề mà tất cả của một đột ngột
bắt đầu hình thành tốt.

698
00:28:53,140 --> 00:28:57,070
Và cuối cùng, bạn nhìn thấy ở
kết thúc rất có bam,

699
00:28:57,070 --> 00:28:58,860
tất cả mọi thứ được sáp nhập với nhau.

700
00:28:58,860 --> 00:29:01,690
>> Vì vậy, đây chỉ là ba khác nhau
có trên ý tưởng tương tự.

701
00:29:01,690 --> 00:29:05,980
Nhưng cái nhìn sâu sắc quan trọng, giống như chia
và chinh phục trong các lớp học đầu tiên,

702
00:29:05,980 --> 00:29:10,640
là chúng tôi quyết định bằng cách nào đó chia
vấn đề thành một cái gì đó lớn, thành

703
00:29:10,640 --> 00:29:14,760
một cái gì đó loại giống hệt nhau trong tinh thần,
nhưng nhỏ hơn và nhỏ hơn và nhỏ hơn

704
00:29:14,760 --> 00:29:15,660
và nhỏ hơn.

705
00:29:15,660 --> 00:29:18,420
>> Bây giờ một cách thú vị để sắp xếp các suy nghĩ
về các, mặc dù nó không

706
00:29:18,420 --> 00:29:20,520
sẽ cung cấp cho bạn cùng trực quan
sự hiểu biết, là

707
00:29:20,520 --> 00:29:21,640
các hình ảnh động sau đây.

708
00:29:21,640 --> 00:29:25,400
Vì vậy, đây là một người nào đó phim cùng nhau
có liên quan khác nhau

709
00:29:25,400 --> 00:29:29,970
âm thanh với các hoạt động khác nhau cho
sắp xếp chèn, cho hợp nhất sắp xếp, và

710
00:29:29,970 --> 00:29:31,150
cho một vài người khác.

711
00:29:31,150 --> 00:29:32,330
Vì vậy, trong một thời điểm, tôi sẽ nhấn Play.

712
00:29:32,330 --> 00:29:33,600
Đó là khoảng một phút dài.

713
00:29:33,600 --> 00:29:37,410
Và ngay cả khi bạn vẫn có thể thấy
mô hình xảy ra, thời gian này bạn có thể

714
00:29:37,410 --> 00:29:41,420
cũng nghe như thế nào các thuật toán
thực hiện khác nhau và với

715
00:29:41,420 --> 00:29:43,950
mô hình hơi khác nhau.

716
00:29:43,950 --> 00:29:45,830
>> Đây là sắp xếp chèn.

717
00:29:45,830 --> 00:29:50,400
>> [Nhạc CHƠI]

718
00:29:50,400 --> 00:29:52,400
>> DAVID Malan: Một lần nữa, đang cố gắng
để chèn mỗi phần tử

719
00:29:52,400 --> 00:29:52,900
vào nơi mà nó thuộc về.

720
00:29:52,900 --> 00:29:54,628
Đây là bong bóng sắp xếp.

721
00:29:54,628 --> 00:30:10,097
>> [Nhạc CHƠI]

722
00:30:10,097 --> 00:30:13,630
>> DAVID Malan: Và bạn có thể sắp xếp của cảm giác
cách tương đối ít làm việc nó làm

723
00:30:13,630 --> 00:30:15,834
trên mỗi bước.

724
00:30:15,834 --> 00:30:20,470
Đây là những gì tediousness giống như âm thanh.

725
00:30:20,470 --> 00:30:21,472
>> [Nhạc CHƠI]

726
00:30:21,472 --> 00:30:25,222
>> DAVID Malan: Đây là lựa chọn sắp xếp,
nơi mà chúng tôi lựa chọn các yếu tố chúng ta muốn bằng cách

727
00:30:25,222 --> 00:30:28,845
đi qua một lần nữa và một lần nữa và một lần nữa
và đặt nó ngay từ đầu.

728
00:30:28,845 --> 00:30:37,674
>> [Nhạc CHƠI]

729
00:30:37,674 --> 00:30:43,970
>> DAVID Malan: Đây là hợp nhất phân loại, mà
bạn thực sự có thể bắt đầu cảm thấy.

730
00:30:43,970 --> 00:30:51,810
>> [Nhạc CHƠI]

731
00:30:51,810 --> 00:30:54,770
>> [Cười]

732
00:30:54,770 --> 00:30:58,395
>> DAVID Malan: Một cái gì đó gọi là gnome
loại, trong đó chúng tôi đã không nhìn.

733
00:30:58,395 --> 00:31:13,630
>> [Nhạc CHƠI]

734
00:31:13,630 --> 00:31:17,910
>> DAVID Malan: Vì vậy, chúng tôi thấy, bây giờ,
bị phân tâm như bạn hy vọng là do

735
00:31:17,910 --> 00:31:21,110
âm nhạc, nếu tôi có thể ra một chút
bit của toán học trong đây.

736
00:31:21,110 --> 00:31:24,850
Vì vậy, có một cách thứ tư mà chúng ta có thể
suy nghĩ về những gì nó có nghĩa là các

737
00:31:24,850 --> 00:31:29,210
chức năng được nhanh hơn so với những người
mà chúng ta đã thấy trước đây.

738
00:31:29,210 --> 00:31:32,470
Và nếu bạn đến vào khóa học từ
một nền tảng toán học, bạn

739
00:31:32,470 --> 00:31:36,030
thực sự biết có lẽ đã là bạn
có thể tát một thuật ngữ về kỹ thuật này -

740
00:31:36,030 --> 00:31:40,400
cụ thể là đệ quy, một chức năng
bằng cách nào đó tự gọi mình.

741
00:31:40,400 --> 00:31:44,780
>> Và một lần nữa, nhớ lại rằng hợp nhất loại
giả là đệ quy trong ý nghĩa

742
00:31:44,780 --> 00:31:48,460
là một trong những bước hợp nhất của loại
đã gọi loại -

743
00:31:48,460 --> 00:31:49,740
có nghĩa là, chính nó.

744
00:31:49,740 --> 00:31:52,480
Nhưng may mắn, bởi vì chúng tôi giữ
gọi loại, hoặc hợp nhất phân loại,

745
00:31:52,480 --> 00:31:55,880
đặc biệt, trên một nhỏ hơn và nhỏ hơn
và danh sách nhỏ hơn, chúng tôi cuối cùng

746
00:31:55,880 --> 00:32:00,005
đáy nhờ vào những gì chúng tôi sẽ gọi
một trường hợp cơ sở, các trường hợp mã hóa cứng mà

747
00:32:00,005 --> 00:32:04,270
cho biết nếu danh sách là nhỏ, ít hơn 2
trong trường hợp đó, chỉ trả lại ngay lập tức.

748
00:32:04,270 --> 00:32:07,550
Nếu chúng ta không có mà trường hợp đặc biệt, các
thuật toán sẽ không bao giờ chạm đáy,

749
00:32:07,550 --> 00:32:11,010
và bạn thực sự sẽ nhận được vào một
vòng lặp vô hạn thực sự mãi mãi.

750
00:32:11,010 --> 00:32:14,330
>> Nhưng giả sử rằng chúng tôi muốn bây giờ đặt
một số con số về điều này, một lần nữa, sử dụng n

751
00:32:14,330 --> 00:32:15,660
như kích thước của đầu vào.

752
00:32:15,660 --> 00:32:18,680
Và tôi muốn hỏi bạn, những gì
tổng thời gian tham gia vào

753
00:32:18,680 --> 00:32:19,800
chạy hợp nhất loại?

754
00:32:19,800 --> 00:32:22,960
Hay rộng hơn, những gì
chi phí của nó trong thời gian?

755
00:32:22,960 --> 00:32:24,730
>> Vâng đó là khá dễ dàng để đo lường đó.

756
00:32:24,730 --> 00:32:29,010
Nếu n là ít hơn 2, thời gian tham gia
trong sắp xếp n phần tử,

757
00:32:29,010 --> 00:32:30,480
trong đó n là 2, là 0.

758
00:32:30,480 --> 00:32:31,410
Bởi vì chúng tôi chỉ trả lại.

759
00:32:31,410 --> 00:32:32,510
Không có việc phải làm.

760
00:32:32,510 --> 00:32:35,660
Bây giờ cho là, có lẽ đó là một bước hoặc hai
các bước để tìm ra số lượng

761
00:32:35,660 --> 00:32:38,420
làm việc, nhưng nó đủ gần để 0 mà
Tôi chỉ muốn nói không làm việc là

762
00:32:38,420 --> 00:32:40,940
yêu cầu nếu danh sách là quá nhỏ
được nhàm chán.

763
00:32:40,940 --> 00:32:42,580
>> Nhưng trường hợp này rất thú vị.

764
00:32:42,580 --> 00:32:47,320
Trường hợp đệ quy là chi nhánh của
mã giả mà nói khác, loại

765
00:32:47,320 --> 00:32:52,000
nửa bên trái, sắp xếp quyền
một nửa, hợp nhất hai nửa.

766
00:32:52,000 --> 00:32:55,530
Bây giờ tại sao biểu hiện này
đại diện cho chi phí đó?

767
00:32:55,530 --> 00:32:58,690
Vâng, T n chỉ có nghĩa là
thời gian để sắp xếp các yếu tố n.

768
00:32:58,690 --> 00:33:03,070
Và sau đó ở phía bên phải của
dấu bằng ở đó, T n chia

769
00:33:03,070 --> 00:33:06,600
2 là đề cập đến chi phí của những gì?

770
00:33:06,600 --> 00:33:07,570
Sắp xếp nửa trái.

771
00:33:07,570 --> 00:33:10,990
T khác của n khi chia cho 2 là
có lẽ đề cập đến chi phí để

772
00:33:10,990 --> 00:33:12,390
sắp xếp nửa bên phải.

773
00:33:12,390 --> 00:33:14,590
>> Và sau đó là n cộng?

774
00:33:14,590 --> 00:33:15,420
Là sáp nhập.

775
00:33:15,420 --> 00:33:19,120
Bởi vì nếu bạn có hai danh sách, một trong những
kích thước n hơn 2 và một kích thước n

776
00:33:19,120 --> 00:33:22,580
hơn 2, bạn phải chạm vào cơ bản
mỗi người trong những yếu tố, giống như Rob

777
00:33:22,580 --> 00:33:24,990
chạm vào mỗi ly, và chỉ
như chúng tôi chỉ vào từng

778
00:33:24,990 --> 00:33:26,310
tình nguyện viên trên sân khấu.

779
00:33:26,310 --> 00:33:28,790
Vì vậy, n là các chi phí của hợp nhất.

780
00:33:28,790 --> 00:33:31,780
>> Bây giờ không may, công thức này
cũng là chính nó đệ quy.

781
00:33:31,780 --> 00:33:36,390
Vì vậy, nếu hỏi những câu hỏi, nếu n là, nói,
16, nếu có 16 người trên sân khấu

782
00:33:36,390 --> 00:33:40,670
hoặc 16 ly trong video, bao nhiêu tổng số
bước hiện nó đi để sắp xếp chúng

783
00:33:40,670 --> 00:33:41,550
hợp nhất với loại?

784
00:33:41,550 --> 00:33:45,790
Nó thực sự không phải là một câu trả lời rõ ràng,
bởi vì bây giờ bạn phải phân loại của

785
00:33:45,790 --> 00:33:48,500
đệ quy trả lời công thức này.

786
00:33:48,500 --> 00:33:51,190
>> Nhưng đó là OK, vì cho tôi đề xuất
mà chúng ta làm như sau.

787
00:33:51,190 --> 00:33:56,670
Thời gian tham gia để sắp xếp 16 người hoặc
16 ly sẽ được đại diện

788
00:33:56,670 --> 00:33:58,020
nói chung như T 16.

789
00:33:58,020 --> 00:34:01,400
Nhưng mà bằng, theo chúng tôi
công thức trước, 2 lần số tiền

790
00:34:01,400 --> 00:34:04,780
thời gian cần thiết để sắp xếp
8 ly cộng với 16.

791
00:34:04,780 --> 00:34:08,590
Và một lần nữa, cộng với 16 là thời gian để hợp nhất,
và hai lần T của 8 là

792
00:34:08,590 --> 00:34:10,790
thời gian để sắp xếp một nửa trái và nửa bên phải.

793
00:34:10,790 --> 00:34:11,989
>> Nhưng một lần nữa, điều này là không đủ.

794
00:34:11,989 --> 00:34:13,210
Chúng ta phải lặn sâu hơn.

795
00:34:13,210 --> 00:34:16,409
Điều này có nghĩa chúng ta phải trả lời
câu hỏi, là những gì T của 8?

796
00:34:16,409 --> 00:34:19,610
Cũng T của 8 chỉ là 2
lần T của 4 cộng với 8.

797
00:34:19,610 --> 00:34:20,520
Vâng, T 4 là gì?

798
00:34:20,520 --> 00:34:23,780
T của 4 chỉ là 2 lần T của 2 cộng 4.

799
00:34:23,780 --> 00:34:25,489
Vâng, T 2 là gì?

800
00:34:25,489 --> 00:34:29,030
T của 2 chỉ là 2 lần T của 1 cộng với 2.

801
00:34:29,030 --> 00:34:31,940
>> Và một lần nữa, chúng ta đang loại nhận
bị mắc kẹt trong chu kỳ này.

802
00:34:31,940 --> 00:34:34,790
Nhưng đó là về để đạt mà
cái gọi là trường hợp cơ sở.

803
00:34:34,790 --> 00:34:37,310
Bởi vì những gì là T 1, đã làm chúng tôi yêu cầu bồi thường?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Vì vậy, bây giờ cuối cùng, chúng ta có thể làm việc ngược.

806
00:34:39,730 --> 00:34:44,290
>> Nếu T của 1 là 0, tôi bây giờ có thể quay trở lại một
xếp hàng để anh chàng này ở đây, và tôi có thể

807
00:34:44,290 --> 00:34:46,330
cắm vào 0 cho T 1.

808
00:34:46,330 --> 00:34:51,770
Vì vậy, có nghĩa là nó tương đương với 2 lần số không,
hay còn gọi là 0, cộng với 2.

809
00:34:51,770 --> 00:34:53,739
Và để biểu hiện toàn bộ là 2.

810
00:34:53,739 --> 00:34:58,740
>> Bây giờ nếu tôi lấy T 2, có câu trả lời
là 2, cắm nó vào các đường trung tuyến, T

811
00:34:58,740 --> 00:35:02,740
4, cung cấp cho tôi 2 lần
2 cộng với 4, do đó 8.

812
00:35:02,740 --> 00:35:07,080
Nếu tôi sau đó cắm trong 8 với trước đó
đường, cung cấp cho tôi 2 lần 8, 16.

813
00:35:07,080 --> 00:35:12,470
Và nếu chúng ta sau đó tiếp tục có với
24, thêm vào 16, chúng tôi cuối cùng đã có được một

814
00:35:12,470 --> 00:35:13,820
giá trị 64.

815
00:35:13,820 --> 00:35:18,480
>> Bây giờ trong và của chính nó loại nói
không có gì để ký hiệu n,

816
00:35:18,480 --> 00:35:20,700
O lớn, omega rằng chúng tôi đã
được nói đến.

817
00:35:20,700 --> 00:35:24,890
Nhưng nó chỉ ra rằng 64 thực sự là
16, kích thước của đầu vào,

818
00:35:24,890 --> 00:35:27,110
đăng nhập cơ sở 2 của 16.

819
00:35:27,110 --> 00:35:30,200
Và nếu điều này là một chút không quen thuộc, chỉ
nghĩ lại, và nó sẽ trở lại

820
00:35:30,200 --> 00:35:30,700
để bạn cuối cùng.

821
00:35:30,700 --> 00:35:33,775
Nếu đây là nhật ký cơ sở 2, nó giống như 2
nâng lên những gì cho bạn 16?

822
00:35:33,775 --> 00:35:36,380
Ồ, đó là 4, vì vậy 16 lần 4.

823
00:35:36,380 --> 00:35:39,380
>> Và một lần nữa, nó không phải là một vấn đề lớn nếu điều này
là sắp xếp của một bộ nhớ mơ hồ bây giờ.

824
00:35:39,380 --> 00:35:43,720
Nhưng hiện nay, có trên đức tin
có 16 bản ghi 16 là 64.

825
00:35:43,720 --> 00:35:46,590
Và như vậy thực sự, với sự tỉnh táo đơn giản này
kiểm tra, chúng tôi đã xác nhận -

826
00:35:46,590 --> 00:35:48,250
nhưng không chứng minh chính thức -

827
00:35:48,250 --> 00:35:52,800
rằng thời gian hoạt động của hợp nhất
loại thực sự là n log n.

828
00:35:52,800 --> 00:35:53,790
>> Vì vậy, không xấu.

829
00:35:53,790 --> 00:35:57,260
Đó chắc chắn là tốt hơn so với
các thuật toán chúng tôi đã nhìn thấy cho đến nay, và

830
00:35:57,260 --> 00:36:00,710
đó là bởi vì chúng ta đã thừa hưởng, một,
một kỹ thuật được gọi là đệ quy.

831
00:36:00,710 --> 00:36:03,880
Nhưng thú vị hơn đó, mà
khái niệm về phân chia và chinh phục.

832
00:36:03,880 --> 00:36:07,460
Một lần nữa, thực sự tuần 0 thứ mà
ngay cả bây giờ được tái diễn trong một

833
00:36:07,460 --> 00:36:08,740
hơn cách thuyết phục.

834
00:36:08,740 --> 00:36:11,750
>> Bây giờ một ít tập thể dục vui vẻ, nếu bạn đã
không bao giờ làm điều này - và bạn có thể

835
00:36:11,750 --> 00:36:14,660
sẽ không có, bởi vì loại bình thường
mọi người không nghĩ để làm điều này.

836
00:36:14,660 --> 00:36:20,650
Nhưng nếu tôi đi vào google.com và nếu
Tôi muốn tìm hiểu về

837
00:36:20,650 --> 00:36:22,356
đệ quy, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Cười]

840
00:36:29,058 --> 00:36:32,030
[THÊM cười]

841
00:36:32,030 --> 00:36:33,385
DAVID Malan: Bad trò đùa từ từ lan rộng.

842
00:36:33,385 --> 00:36:34,450
[Cười]

843
00:36:34,450 --> 00:36:36,970
DAVID Malan: Chỉ trong trường hợp, nó ở đó.

844
00:36:36,970 --> 00:36:38,710
Tôi không đánh vần sai,
và có những trò đùa.

845
00:36:38,710 --> 00:36:40,810
Được rồi.

846
00:36:40,810 --> 00:36:42,950
Giải thích cho những người bên cạnh bạn nếu
nó đã không hoàn toàn nhấp chỉ được nêu ra.

847
00:36:42,950 --> 00:36:47,650
Nhưng đệ quy, nói chung, đề cập
đến quá trình một chức năng gọi điện

848
00:36:47,650 --> 00:36:51,430
chính nó, hay rộng hơn, phân chia một
vấn đề thành một cái gì đó có thể được

849
00:36:51,430 --> 00:36:56,220
giải quyết từng phần bằng cách giải quyết giống hệt nhau
vấn đề đại diện.

850
00:36:56,220 --> 00:36:58,400
>> Vâng, chúng ta hãy thay đổi bánh răng
chỉ trong khoảnh khắc.

851
00:36:58,400 --> 00:37:00,840
Chúng tôi muốn kết thúc vào cliffhangers nhất định,
vì vậy hãy bắt đầu thiết lập

852
00:37:00,840 --> 00:37:05,870
sân khấu, trong vài phút,
trên một ý tưởng rất đơn giản -

853
00:37:05,870 --> 00:37:07,620
trao đổi của hai yếu tố này, phải không?

854
00:37:07,620 --> 00:37:10,040
Tất cả các thuật toán chúng tôi đã
nói về quá khứ vài

855
00:37:10,040 --> 00:37:12,420
bài giảng liên quan đến một số
loại trao đổi.

856
00:37:12,420 --> 00:37:14,630
Hôm nay nó đã được hình dung bằng cách họ nhận được
ra khỏi ghế và

857
00:37:14,630 --> 00:37:18,570
đi bộ xung quanh, nhưng trong mã, chúng tôi sẽ
chỉ cần lấy một phần tử từ một mảng

858
00:37:18,570 --> 00:37:20,370
và tiếng tom nó vào một.

859
00:37:20,370 --> 00:37:21,880
>> Vì vậy, làm thế nào để chúng tôi đi về việc này?

860
00:37:21,880 --> 00:37:24,850
Vâng, hãy để tôi đi trước và viết
một chương trình nhanh chóng ở đây.

861
00:37:24,850 --> 00:37:31,600
Tôi sẽ đi trước và làm
này như sau.

862
00:37:31,600 --> 00:37:33,910
Chúng ta hãy gọi này -

863
00:37:33,910 --> 00:37:38,070
những gì chúng ta muốn gọi này?

864
00:37:38,070 --> 00:37:38,650
>> Trên thực tế, không.

865
00:37:38,650 --> 00:37:39,420
Hãy để tôi quay lại.

866
00:37:39,420 --> 00:37:41,220
Tôi không muốn làm điều đó
cliffhanger được nêu ra.

867
00:37:41,220 --> 00:37:42,270
Nó sẽ làm hỏng sự vui vẻ.

868
00:37:42,270 --> 00:37:43,600
Hãy làm điều này để thay thế.

869
00:37:43,600 --> 00:37:47,430
>> Giả sử tôi muốn viết một chút
chương trình và giờ đây đã này

870
00:37:47,430 --> 00:37:48,700
ý tưởng của đệ quy.

871
00:37:48,700 --> 00:37:50,370
Tôi loại có trước bản thân mình có.

872
00:37:50,370 --> 00:37:51,420
Tôi sẽ phải làm như sau.

873
00:37:51,420 --> 00:38:00,220
>> Đầu tiên, một cách nhanh chóng bao gồm các tiêu chuẩn io.h,
cũng như bao gồm các cs50.h.

874
00:38:00,220 --> 00:38:03,200
Và sau đó tôi sẽ đi trước
và tuyên bố int main trống

875
00:38:03,200 --> 00:38:04,360
theo cách thông thường.

876
00:38:04,360 --> 00:38:07,920
Tôi nhận ra tôi đã bị đặt tên sai các tập tin, để
hãy để tôi chỉ cần thêm một c mở rộng. đây để

877
00:38:07,920 --> 00:38:09,510
chúng tôi có thể biên dịch nó đúng cách.

878
00:38:09,510 --> 00:38:10,970
Bắt đầu chức năng này.

879
00:38:10,970 --> 00:38:13,290
>> Và các chức năng tôi muốn viết, khá
đơn giản, là một trong những yêu cầu

880
00:38:13,290 --> 00:38:16,210
người sử dụng cho một số và sau đó tăng dần lên
tất cả các số giữa các

881
00:38:16,210 --> 00:38:19,920
số lượng và, nói, 0.

882
00:38:19,920 --> 00:38:22,510
Vì vậy, đầu tiên tôi sẽ đi trước
và tuyên bố n int.

883
00:38:22,510 --> 00:38:24,760
Sau đó sao chép một số mã
chúng tôi đã sử dụng trong một thời gian.

884
00:38:24,760 --> 00:38:26,660
Trong khi một cái gì đó là sự thật.

885
00:38:26,660 --> 00:38:28,000
Tôi sẽ trở lại đó trong một thời điểm.

886
00:38:28,000 --> 00:38:29,010
>> Tôi phải làm gì muốn làm gì?

887
00:38:29,010 --> 00:38:33,460
Tôi muốn nói printf tích cực
nguyên xin.

888
00:38:33,460 --> 00:38:36,130
Và sau đó tôi sẽ
nói n được lấy int.

889
00:38:36,130 --> 00:38:38,800
Vì vậy, một lần nữa, một số mã soạn
mà chúng ta đã sử dụng trước.

890
00:38:38,800 --> 00:38:40,810
Và tôi sẽ làm điều này
trong khi n là nhỏ hơn 1.

891
00:38:40,810 --> 00:38:44,120
Vì vậy, điều này sẽ đảm bảo rằng người sử dụng
mang lại cho tôi một số nguyên dương.

892
00:38:44,120 --> 00:38:45,490
>> Và bây giờ tôi sẽ phải làm như sau.

893
00:38:45,490 --> 00:38:51,020
Tôi muốn thêm lên tất cả các con số
từ 1 đến n, hoặc 0 và n,

894
00:38:51,020 --> 00:38:52,570
tương đương, để có được tổng số tiền.

895
00:38:52,570 --> 00:38:55,100
Vì vậy, các biểu tượng sigma lớn
mà bạn có thể nhớ lại.

896
00:38:55,100 --> 00:38:59,050
Vì vậy, tôi sẽ làm điều này bằng cách gọi đầu tiên
một chức năng gọi là sigma,

897
00:38:59,050 --> 00:39:06,030
đi qua nó trong n, và sau đó tôi sẽ
printf nói, câu trả lời là phải có.

898
00:39:06,030 --> 00:39:08,180
>> Vì vậy, trong ngắn hạn, tôi nhận được và
int từ người sử dụng.

899
00:39:08,180 --> 00:39:09,280
Tôi đảm bảo nó là tích cực.

900
00:39:09,280 --> 00:39:12,700
Tôi khai báo một biến được gọi là câu trả lời của
kiểu int và lưu trữ nó trong sự trở lại

901
00:39:12,700 --> 00:39:15,610
giá trị của sigma, đi qua trong n như đầu vào.

902
00:39:15,610 --> 00:39:17,060
Và sau đó tôi in ra câu trả lời.

903
00:39:17,060 --> 00:39:19,550
>> Thật không may, mặc dù sigma âm thanh
như một cái gì đó mà có thể trong

904
00:39:19,550 --> 00:39:24,040
các tập tin math.h, tuyên bố của mình,
nó thực sự không.

905
00:39:24,040 --> 00:39:24,690
Vì vậy, đó là OK.

906
00:39:24,690 --> 00:39:26,170
Tôi có thể thực hiện điều này bản thân mình.

907
00:39:26,170 --> 00:39:29,160
Tôi sẽ thực hiện một chức năng được gọi là
sigma, và nó sẽ mất một

908
00:39:29,160 --> 00:39:29,900
tham số -

909
00:39:29,900 --> 00:39:32,100
chúng ta hãy gọi nó là m, chỉ
vì vậy nó khác nhau.

910
00:39:32,100 --> 00:39:35,910
Và sau đó lên đây, tôi sẽ nói,
tốt, nếu m là ít hơn 1 - đây là một

911
00:39:35,910 --> 00:39:38,180
rất không thú vị của chương trình.

912
00:39:38,180 --> 00:39:41,700
Vì vậy, tôi sẽ đi trước và
ngay lập tức trở về 0.

913
00:39:41,700 --> 00:39:45,920
Nó chỉ có ý nghĩa để gắn lên tất cả
các con số từ 1 đến m nếu m

914
00:39:45,920 --> 00:39:48,470
bản thân nó là 0 hoặc âm.

915
00:39:48,470 --> 00:39:50,900
>> Và sau đó tôi sẽ đi trước
và làm điều này rất lặp đi lặp lại.

916
00:39:50,900 --> 00:39:53,090
Tôi sẽ làm việc này của trường học cũ,
và tôi sẽ đi trước

917
00:39:53,090 --> 00:39:57,150
và nói rằng tôi sẽ
khai báo một số tiền là 0.

918
00:39:57,150 --> 00:39:59,630
Sau đó, tôi sẽ có
một vòng lặp của int -

919
00:39:59,630 --> 00:40:02,820
và để cho tôi làm điều đó để phù hợp với chúng tôi
đang phân phối, vì vậy bạn có một bản sao

920
00:40:02,820 --> 00:40:07,500
ở nhà. int i được 1 trên lên đến
i nhỏ hơn hoặc bằng m.

921
00:40:07,500 --> 00:40:09,430
i cộng cộng.

922
00:40:09,430 --> 00:40:11,430
Và sau đó bên trong này cho vòng lặp -

923
00:40:11,430 --> 00:40:12,440
chúng tôi hầu như có -

924
00:40:12,440 --> 00:40:15,810
tổng số tiền được cộng thêm 1.

925
00:40:15,810 --> 00:40:17,670
Và sau đó tôi sẽ trả lại số tiền.

926
00:40:17,670 --> 00:40:19,420
>> Vì vậy, tôi đã làm điều này một cách nhanh chóng,
khá thừa nhận.

927
00:40:19,420 --> 00:40:22,775
Nhưng một lần nữa, các chức năng chính khá
đơn giản, dựa trên mã chúng tôi đã

928
00:40:22,775 --> 00:40:23,190
bằng văn bản cho đến nay.

929
00:40:23,190 --> 00:40:25,610
Sử dụng vòng lặp kép để có được một dương
int từ người sử dụng.

930
00:40:25,610 --> 00:40:29,870
Sau đó tôi vượt qua int rằng đến một chức năng mới
gọi là sigma, gọi đó là, một lần nữa, n.

931
00:40:29,870 --> 00:40:33,100
Và tôi lưu trữ các giá trị trả về, câu trả lời
từ hộp đen hiện nay

932
00:40:33,100 --> 00:40:35,460
được biết đến như sigma, trong một biến
gọi là câu trả lời.

933
00:40:35,460 --> 00:40:36,580
Sau đó, tôi in nó.

934
00:40:36,580 --> 00:40:39,090
>> Nếu bây giờ chúng ta tiếp tục câu chuyện,
làm thế nào là sigma thực hiện?

935
00:40:39,090 --> 00:40:40,840
Tôi đề nghị để thực hiện như sau.

936
00:40:40,840 --> 00:40:43,560
Đầu tiên, một chút kiểm tra lỗi
để đảm bảo rằng người dùng không

937
00:40:43,560 --> 00:40:46,480
rối tung với tôi và đi qua trong
một số giá trị âm hoặc 0.

938
00:40:46,480 --> 00:40:49,710
Sau đó, tôi khai báo một biến được gọi là
tổng hợp và đặt nó là 0.

939
00:40:49,710 --> 00:40:55,910
>> Và bây giờ tôi bắt đầu di chuyển từ tôi bằng
1 tất cả các con đường lên đến và bao gồm m,

940
00:40:55,910 --> 00:41:00,130
bởi vì tôi muốn bao gồm tất cả các
số từ một đến m, đã bao gồm.

941
00:41:00,130 --> 00:41:04,350
Và bên trong này cho vòng lặp, tôi chỉ cần làm
số tiền được bất cứ điều gì nó là bây giờ, cộng với

942
00:41:04,350 --> 00:41:08,900
giá trị của tôi.

943
00:41:08,900 --> 00:41:10,370
Cộng với giá trị của tôi.

944
00:41:10,370 --> 00:41:14,090
>> Như một sang một bên, nếu bạn đã không nhìn thấy điều này
trước đây, có một số cú pháp đường

945
00:41:14,090 --> 00:41:14,870
cho dòng này.

946
00:41:14,870 --> 00:41:21,120
Tôi có thể viết lại này như cộng bằng tôi,
chỉ để tiết kiệm cho mình một vài tổ hợp phím

947
00:41:21,120 --> 00:41:22,570
và để tìm một chút mát.

948
00:41:22,570 --> 00:41:23,140
Nhưng đó là tất cả.

949
00:41:23,140 --> 00:41:24,660
Đó là chức năng điều tương tự.

950
00:41:24,660 --> 00:41:26,710
>> Thật không may, mã này của
sẽ không biên dịch được nêu ra.

951
00:41:26,710 --> 00:41:31,600
Nếu tôi chạy làm cho sigma 0, làm thế nào am
Tôi sẽ bị mắng?

952
00:41:31,600 --> 00:41:33,473
Đó là những gì sẽ không như thế nào?

953
00:41:33,473 --> 00:41:35,740
>> ĐỐI TƯỢNG: [nghe được].

954
00:41:35,740 --> 00:41:37,800
>> DAVID Malan: Vâng, tôi đã không khai báo
chức năng lên hàng đầu, phải không?

955
00:41:37,800 --> 00:41:40,590
C là ngu ngốc, nó chỉ ở đó
những gì bạn nói với nó để làm, và bạn

956
00:41:40,590 --> 00:41:41,880
phải làm điều đó trong thứ tự đó.

957
00:41:41,880 --> 00:41:45,910
Và do đó, nếu tôi nhấn Enter ở đây, tôi sẽ
nhận được một cảnh báo về sigma ngầm

958
00:41:45,910 --> 00:41:46,860
kê khai.

959
00:41:46,860 --> 00:41:48,120
>> Oh, không phải là một vấn đề.

960
00:41:48,120 --> 00:41:50,370
Tôi có thể đi lên đến đỉnh, và tôi có thể
nói, được rồi, chờ một phút.

961
00:41:50,370 --> 00:41:54,240
Sigma là một hàm trả về
một int và dự kiến ​​một

962
00:41:54,240 --> 00:41:56,620
int như đầu vào, dấu chấm phẩy.

963
00:41:56,620 --> 00:41:59,550
Hoặc tôi có thể đặt toàn bộ chức năng
trên chính, nhưng nói chung, tôi muốn

964
00:41:59,550 --> 00:42:02,260
khuyên bạn nên chống lại điều đó, bởi vì nó
tốt đẹp luôn luôn có chính ở phía trên để

965
00:42:02,260 --> 00:42:06,310
bạn có thể nhảy ngay trong và biết những gì một
chương trình đang làm bằng cách đọc chính đầu tiên.

966
00:42:06,310 --> 00:42:07,930
>> Vì vậy, bây giờ hãy để tôi xóa màn hình.

967
00:42:07,930 --> 00:42:09,330
Làm lại sigma 0.

968
00:42:09,330 --> 00:42:10,340
Tất cả dường như để kiểm tra.

969
00:42:10,340 --> 00:42:11,970
Cho phép tôi chạy sigma 0.

970
00:42:11,970 --> 00:42:12,770
Liên quan.

971
00:42:12,770 --> 00:42:15,580
Tôi sẽ cho nó số
3 để giữ cho nó đơn giản.

972
00:42:15,580 --> 00:42:18,710
Vì vậy, cần cung cấp cho tôi 3
cộng với 2 cộng với 1, vì vậy 6.

973
00:42:18,710 --> 00:42:20,750
Nhập, và thực sự tôi nhận được 6.

974
00:42:20,750 --> 00:42:21,820
>> Tôi có thể làm một cái gì đó lớn hơn -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Cũng giống như một tiếp tuyến, tôi sẽ làm
một cái gì đó vô lý như một thực sự lớn

977
00:42:27,690 --> 00:42:30,375
số lượng, Oh, mà thực sự đã làm việc ra -

978
00:42:30,375 --> 00:42:31,600
eh, tôi không nghĩ điều đó đúng.

979
00:42:31,600 --> 00:42:32,810
Chúng ta hãy xem.

980
00:42:32,810 --> 00:42:34,060
Chúng ta hãy thực sự gây rối với nó.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> Đó là một vấn đề.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Những gì đang xảy ra?

985
00:42:44,970 --> 00:42:46,050
Mã này không phải là xấu.

986
00:42:46,050 --> 00:42:48,470
Nó vẫn còn tuyến tính.

987
00:42:48,470 --> 00:42:50,810
Huýt sáo là một hiệu ứng tốt, mặc dù.

988
00:42:50,810 --> 00:42:52,060
Những gì đang xảy ra?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Không chắc chắn nếu tôi nghe nó.

991
00:42:55,620 --> 00:42:57,620
Vì vậy, nó quay ra - và
đây là như một sang một bên.

992
00:42:57,620 --> 00:42:59,400
Đây không phải là cốt lõi cho
ý tưởng của đệ quy.

993
00:42:59,400 --> 00:43:02,480
Hóa ra, vì tôi đang cố gắng để
đại diện cho một số lượng lớn như vậy, nhất

994
00:43:02,480 --> 00:43:06,980
khả năng nó được diễn giải sai
bằng C như một số không tích cực,

995
00:43:06,980 --> 00:43:09,980
nhưng số âm.

996
00:43:09,980 --> 00:43:12,690
>> Chúng tôi đã không nói về điều này, nhưng nó
Hóa ra có một số lượng tiêu cực

997
00:43:12,690 --> 00:43:14,210
trong thế giới ngoài
với số dương.

998
00:43:14,210 --> 00:43:16,290
Và các phương tiện mà bạn có thể
đại diện một số tiêu cực

999
00:43:16,290 --> 00:43:19,530
chủ yếu là, bạn sử dụng một
bit đặc biệt để chỉ ra

1000
00:43:19,530 --> 00:43:20,400
tích cực hơn tiêu cực.

1001
00:43:20,400 --> 00:43:22,950
Đó là một ít phức tạp hơn,
nhưng đó là ý tưởng cơ bản.

1002
00:43:22,950 --> 00:43:26,740
>> Vì vậy, không may, nếu C là khó hiểu một
của các bit như thực sự có nghĩa là,

1003
00:43:26,740 --> 00:43:30,790
oh, đây là một số âm, vòng lặp của tôi
ở đây, ví dụ, thực sự là không bao giờ

1004
00:43:30,790 --> 00:43:31,740
sẽ chấm dứt.

1005
00:43:31,740 --> 00:43:33,850
Vì vậy, nếu tôi đã thực sự in một cái gì đó
một lần nữa và một lần nữa, chúng tôi sẽ

1006
00:43:33,850 --> 00:43:34,650
thấy một toàn bộ rất nhiều.

1007
00:43:34,650 --> 00:43:36,220
Nhưng một lần nữa, đây là bên cạnh những điểm.

1008
00:43:36,220 --> 00:43:38,590
Điều này thực sự chỉ là một loại
sự tò mò trí tuệ mà chúng ta sẽ đến

1009
00:43:38,590 --> 00:43:39,550
sao để cuối cùng.

1010
00:43:39,550 --> 00:43:43,400
Nhưng bây giờ, đây là một chính xác
thực hiện nếu chúng ta giả định rằng

1011
00:43:43,400 --> 00:43:45,970
người sử dụng sẽ cung cấp cho ints
mà phù hợp trong số nguyên.

1012
00:43:45,970 --> 00:43:49,370
>> Nhưng tôi cho rằng mã này, thẳng thắn,
có thể được thực hiện rất nhiều đơn giản hơn.

1013
00:43:49,370 --> 00:43:54,060
Nếu mục tiêu trong tầm tay là để có một số
như m và thêm lên tất cả các

1014
00:43:54,060 --> 00:43:59,510
số giữa nó và 1, hoặc ngược lại
từ 1 đến nó, tôi yêu cầu bồi thường

1015
00:43:59,510 --> 00:44:03,380
mà tôi có thể mượn ý tưởng này hợp nhất
loại đã có, đã được tham gia một vấn đề

1016
00:44:03,380 --> 00:44:05,660
kích thước này và chia
vào một cái gì đó nhỏ hơn.

1017
00:44:05,660 --> 00:44:09,875
Có lẽ không một nửa, nhưng nhỏ hơn, nhưng
representatively cùng.

1018
00:44:09,875 --> 00:44:12,130
Cùng một ý tưởng, nhưng một vấn đề nhỏ hơn.

1019
00:44:12,130 --> 00:44:15,470
>> Vì vậy, tôi thực sự - cho tôi lưu tập tin này
với một số phiên bản khác nhau.

1020
00:44:15,470 --> 00:44:17,670
Chúng tôi sẽ gọi phiên bản này
1 thay vì 0.

1021
00:44:17,670 --> 00:44:20,790
Và tôi cho rằng tôi có thể thực sự
reimplement này trong loại này

1022
00:44:20,790 --> 00:44:22,160
tâm-uốn cách.

1023
00:44:22,160 --> 00:44:23,710
>> Tôi sẽ để lại một phần của nó một mình.

1024
00:44:23,710 --> 00:44:27,710
Tôi sẽ nói rằng nếu m là ít
hơn hoặc thậm chí bằng 0 -

1025
00:44:27,710 --> 00:44:29,280
Tôi chỉ đi được một chút
hậu môn hơn thời gian này

1026
00:44:29,280 --> 00:44:30,520
với kiểm tra lỗi của tôi -

1027
00:44:30,520 --> 00:44:33,190
Tôi sẽ đi trước và trở về 0.

1028
00:44:33,190 --> 00:44:34,490
Này là tùy ý.

1029
00:44:34,490 --> 00:44:37,500
Tôi chỉ đơn giản là quyết định nếu người dùng
mang lại cho tôi một số tiêu cực, tôi

1030
00:44:37,500 --> 00:44:41,490
trở về 0, và họ nên đã đọc
các tài liệu hướng dẫn chặt chẽ hơn.

1031
00:44:41,490 --> 00:44:42,170
>> Khác -

1032
00:44:42,170 --> 00:44:44,070
thông báo những gì tôi sẽ làm.

1033
00:44:44,070 --> 00:44:49,260
Khác tôi sẽ quay trở lại cộng với m -

1034
00:44:49,260 --> 00:44:51,010
sigma của m là gì?

1035
00:44:51,010 --> 00:44:56,710
Vâng, sigma m cộng trừ 1 m,
cộng trừ m 2, cộng trừ 3 m.

1036
00:44:56,710 --> 00:44:58,030
Tôi không muốn viết tất cả ra ngoài.

1037
00:44:58,030 --> 00:44:59,120
Tại sao không tôi chỉ punt?

1038
00:44:59,120 --> 00:45:05,080
Đệ quy gọi bản thân mình với một chút
vấn đề nhỏ hơn, dấu chấm phẩy,

1039
00:45:05,080 --> 00:45:06,840
và gọi nó là một ngày?

1040
00:45:06,840 --> 00:45:07,040
>> Phải không?

1041
00:45:07,040 --> 00:45:10,980
Bây giờ ở đây, bạn có thể cảm thấy lo lắng hay
rằng đây là một vòng lặp vô hạn mà tôi

1042
00:45:10,980 --> 00:45:15,450
dụ dỗ, theo đó tôi đang thực hiện
sigma bằng cách gọi sigma.

1043
00:45:15,450 --> 00:45:20,342
Nhưng đó là hoàn toàn OK, bởi vì tôi
nghĩ trước một thêm vào đó dòng?

1044
00:45:20,342 --> 00:45:22,600
>> ĐỐI TƯỢNG: [nghe được].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID Malan: 23-26, mà
là nếu tình trạng của tôi.

1046
00:45:25,430 --> 00:45:28,390
Vì những gì tốt đẹp về
trừ ở đây, bởi vì tôi giữ

1047
00:45:28,390 --> 00:45:31,180
bàn giao vấn đề nhỏ hơn sigma, nhỏ hơn
vấn đề, nhỏ hơn - đó là không

1048
00:45:31,180 --> 00:45:31,870
một nửa kích thước.

1049
00:45:31,870 --> 00:45:34,380
Nó chỉ là một bước nhỏ bé,
nhưng đó là OK.

1050
00:45:34,380 --> 00:45:38,050
Bởi vì cuối cùng, chúng tôi sẽ làm việc
cách của chúng tôi xuống 1 hoặc 0.

1051
00:45:38,050 --> 00:45:41,630
Và một khi chúng ta nhấn 0, sigma là không
sẽ gọi cho bản thân nữa.

1052
00:45:41,630 --> 00:45:43,590
Nó sẽ ngay lập tức trở về 0.

1053
00:45:43,590 --> 00:45:47,960
>> Vì vậy, có hiệu lực, nếu bạn loại gió này
lên trong tâm trí của bạn, là thêm m cộng

1054
00:45:47,960 --> 00:45:52,740
m trừ đi 1, cộng trừ 2 m, cộng với m trừ
3, cộng với dấu chấm, dấu chấm, dấu chấm, trừ m

1055
00:45:52,740 --> 00:45:57,820
m, cuối cùng đem lại cho bạn 0, và
hiệu quả là cuối cùng để thêm tất cả

1056
00:45:57,820 --> 00:45:59,070
những điều này lại với nhau.

1057
00:45:59,070 --> 00:46:02,380
Vì vậy, chúng ta có không, với đệ quy,
giải quyết các vấn đề mà chúng tôi

1058
00:46:02,380 --> 00:46:03,470
không thể giải quyết trước.

1059
00:46:03,470 --> 00:46:06,840
Trên thực tế, phiên bản 0 điều này, và mỗi
vấn đề cho đến nay, đã có khả năng giải quyết

1060
00:46:06,840 --> 00:46:09,980
với chỉ sử dụng cho vòng lặp hoặc trong khi
vòng hoặc các cấu trúc tương tự.

1061
00:46:09,980 --> 00:46:13,150
>> Nhưng đệ quy, tôi dám khẳng định rằng, cho chúng ta
một cách nghĩ khác nhau về

1062
00:46:13,150 --> 00:46:17,010
vấn đề, theo đó nếu chúng ta có thể có một
vấn đề, phân chia nó từ một cái gì đó

1063
00:46:17,010 --> 00:46:22,340
phần lớn thành một cái gì đó hơi
nhỏ hơn, tôi cho rằng chúng ta có thể giải quyết nó

1064
00:46:22,340 --> 00:46:26,040
có lẽ một chút thanh lịch hơn về
của thiết kế, với mã ít hơn,

1065
00:46:26,040 --> 00:46:30,980
và thậm chí có thể giải quyết vấn đề mà có thể
khó khăn hơn, như chúng tôi sẽ cuối cùng

1066
00:46:30,980 --> 00:46:33,280
thấy, giải quyết hoàn toàn lặp đi lặp lại.

1067
00:46:33,280 --> 00:46:35,980
>> Nhưng cliffhanger mà tôi đã làm
muốn để lại cho chúng tôi, đây.

1068
00:46:35,980 --> 00:46:40,720
Hãy để tôi đi trước và mở
lên một tập tin từ -

1069
00:46:40,720 --> 00:46:44,300
thực sự, hãy để tôi đi và
làm nhanh thật này.

1070
00:46:44,300 --> 00:46:46,875
Hãy để tôi đi trước và đề xuất
sau.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Trong số đang ngày nay là tập tin này đây.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Này ở đây, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Vì vậy, đây là một chương trình nhỏ ngu ngốc mà
Tôi whipped lên rằng tuyên bố để làm

1076
00:47:06,260 --> 00:47:06,940
sau.

1077
00:47:06,940 --> 00:47:10,140
Trong chính, nó đầu tiên khai báo một
int x và gán nó

1078
00:47:10,140 --> 00:47:11,100
giá trị của 1.

1079
00:47:11,100 --> 00:47:13,520
Sau đó, nó tuyên bố một y int và
gán cho nó giá trị 2.

1080
00:47:13,520 --> 00:47:15,310
Sau đó nó in ra những gì x và y được.

1081
00:47:15,310 --> 00:47:17,781
Sau đó nó nói, trao đổi, chấm chấm chấm.

1082
00:47:17,781 --> 00:47:21,670
>> Sau đó nó tuyên bố được gọi một chức năng
được gọi là trao đổi, đi qua trong x và

1083
00:47:21,670 --> 00:47:24,290
y, ý tưởng trong số đó là hy vọng
x và y sẽ quay trở lại

1084
00:47:24,290 --> 00:47:25,620
khác nhau, điều ngược lại.

1085
00:47:25,620 --> 00:47:27,110
Sau đó, nó tuyên bố trao đổi!

1086
00:47:27,110 --> 00:47:28,420
với một dấu chấm than.

1087
00:47:28,420 --> 00:47:30,190
Sau đó nó in ra x và y.

1088
00:47:30,190 --> 00:47:33,480
>> Nhưng nó quay ra rằng điều này rất
trình diễn đơn giản xuống

1089
00:47:33,480 --> 00:47:35,570
đây thực sự là lỗi.

1090
00:47:35,570 --> 00:47:38,870
Mặc dù tôi tuyên bố tạm thời
biến và tạm thời đặt một trong

1091
00:47:38,870 --> 00:47:42,010
nó, sau đó tôi giao lại
một giá trị của b -

1092
00:47:42,010 --> 00:47:45,080
mà cảm thấy hợp lý, bởi vì tôi đã
lưu một bản sao của một trong tạm thời.

1093
00:47:45,080 --> 00:47:48,410
Sau đó, tôi cập nhật b để bằng
bất cứ điều gì là trong tạm thời.

1094
00:47:48,410 --> 00:47:51,610
Điều này loại trò chơi vỏ di chuyển một
vào b và b thành một bằng cách sử dụng này

1095
00:47:51,610 --> 00:47:54,360
người đàn ông trung được gọi là tạm thời cảm thấy
hoàn toàn hợp lý.

1096
00:47:54,360 --> 00:47:57,270
>> Nhưng tôi cho rằng khi tôi chạy
mã, như tôi sẽ làm gì bây giờ -

1097
00:47:57,270 --> 00:47:59,490
hãy để tôi đi trước và dán nó vào đây.

1098
00:47:59,490 --> 00:48:01,995
Tôi sẽ gọi noswap.c này.

1099
00:48:01,995 --> 00:48:05,630
Và như tên cho thấy, đây không phải là
sẽ là một chương trình chính xác.

1100
00:48:05,630 --> 00:48:09,460
Làm noswap. / Không trao đổi.

1101
00:48:09,460 --> 00:48:12,110
x 1, y là 2, trao đổi, trao đổi.

1102
00:48:12,110 --> 00:48:14,220
x 1, y là 2.

1103
00:48:14,220 --> 00:48:16,920
Điều này là sai về cơ bản, thậm chí
mặc dù điều này dường như hoàn hảo

1104
00:48:16,920 --> 00:48:17,730
hợp lý với tôi.

1105
00:48:17,730 --> 00:48:21,330
Và có một lý do, nhưng chúng tôi không
sẽ tiết lộ lý do chỉ được nêu ra.

1106
00:48:21,330 --> 00:48:24,610
>> Chính vì điều đó cliffhanger thứ hai tôi muốn
để lại cho bạn là điều này, một

1107
00:48:24,610 --> 00:48:27,120
thông báo của các loại trên mã số phiếu giảm giá.

1108
00:48:27,120 --> 00:48:31,590
Đổi mới của chúng tôi với cuối ngày trong năm nay
đã gây nên một số lượng không nhỏ

1109
00:48:31,590 --> 00:48:33,830
các câu hỏi, đó là
không ý định của chúng tôi.

1110
00:48:33,830 --> 00:48:36,590
Mục đích của các mã số phiếu giảm giá,
theo đó nếu bạn làm một phần của vấn đề

1111
00:48:36,590 --> 00:48:39,850
thiết lập ban đầu, do đó nhận thêm một ngày,
đã thực sự để giúp các bạn giúp đỡ

1112
00:48:39,850 --> 00:48:42,420
mình bắt đầu sớm, sắp xếp
bởi các tổn của bạn.

1113
00:48:42,420 --> 00:48:44,880
Giúp chúng tôi phân phối tải trên
giờ làm việc tốt hơn để

1114
00:48:44,880 --> 00:48:45,740
đó là loại win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Thật không may, tôi nghĩ rằng hướng dẫn của tôi
đã không được, cho đến nay, rất rõ ràng, vì vậy

1116
00:48:48,860 --> 00:48:52,230
Tôi quay trở lại vào cuối tuần này và cập nhật
spec trong lớn hơn, táo bạo hơn để văn bản

1117
00:48:52,230 --> 00:48:53,600
giải thích đạn như thế này.

1118
00:48:53,600 --> 00:48:56,900
Và chỉ để nói rằng nó công khai hơn, bởi
Mặc định, bộ vấn đề là do thứ năm

1119
00:48:56,900 --> 00:48:58,400
vào buổi trưa, mỗi giáo trình.

1120
00:48:58,400 --> 00:49:02,030
Nếu bạn bắt đầu sớm, kết thúc một phần của
vấn đề đặt ra hôm qua tại 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, phần có liên quan đến một phiếu giảm giá
mã, ý tưởng là bạn có thể mở rộng

1122
00:49:05,170 --> 00:49:07,710
thời hạn của bạn cho
P thiết lập cho đến thứ sáu.

1123
00:49:07,710 --> 00:49:10,890
Đó là, chút đi một phần nhỏ của P
thiết lập liên quan đến những gì thường là

1124
00:49:10,890 --> 00:49:13,200
vấn đề lớn hơn, và bạn mua
mình thêm một ngày.

1125
00:49:13,200 --> 00:49:15,190
Một lần nữa, nó giúp bạn suy nghĩ về
bộ vấn đề, giúp bạn để

1126
00:49:15,190 --> 00:49:16,380
giờ làm việc sớm hơn.

1127
00:49:16,380 --> 00:49:20,670
Nhưng vấn đề mã phiếu giảm giá vẫn còn
cần thiết, ngay cả khi bạn không gửi nó.

1128
00:49:20,670 --> 00:49:23,340
>> Nhưng compellingly hơn là thế này.

1129
00:49:23,340 --> 00:49:26,520
(Giai đoạn WHISPER) Và những folks để lại
đầu là sẽ hối tiếc.

1130
00:49:26,520 --> 00:49:28,620
Như là những người bạn trên ban công.

1131
00:49:28,620 --> 00:49:32,510
Tôi xin lỗi trước tới những người trên
ban công vì lý do đó sẽ

1132
00:49:32,510 --> 00:49:33,920
rõ ràng chỉ trong một thời điểm.

1133
00:49:33,920 --> 00:49:37,050
>> Vì vậy, chúng ta may mắn có một trong
Cựu nghiên cứu sinh giảng dạy đầu CS50 tại

1134
00:49:37,050 --> 00:49:39,302
một công ty gọi là dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Họ đã rất hào phóng tặng một
phiếu mua hàng ở đây cho nhiều không gian này,

1136
00:49:45,500 --> 00:49:48,180
đó là từ các
bình thường 2 GB.

1137
00:49:48,180 --> 00:49:51,740
Vì vậy, những gì tôi nghĩ chúng tôi sẽ làm gì về điều này
lưu ý cuối cùng là làm một chút về một quà tặng,

1138
00:49:51,740 --> 00:49:55,380
theo đó chỉ trong một thời điểm, chúng tôi sẽ tiết lộ
người chiến thắng và những người có một phiếu giảm giá

1139
00:49:55,380 --> 00:49:57,980
mã mà bạn có thể đi đến của họ
trang web, gõ vào, và thì đấy, có được một

1140
00:49:57,980 --> 00:50:01,370
nhiều hơn cả không gian Dropbox cho bạn
thiết bị và cho các tập tin cá nhân của bạn.

1141
00:50:01,370 --> 00:50:05,690
>> Và lần đầu tiên, những người muốn tham gia
trong bản vẽ này?

1142
00:50:05,690 --> 00:50:09,630
OK, bây giờ mà làm cho nó thú vị hơn nữa.

1143
00:50:09,630 --> 00:50:14,010
Người nhận này 25 GB
phiếu mua hàng - đó là xa

1144
00:50:14,010 --> 00:50:16,150
hấp dẫn hơn vào cuối
ngày nay, có lẽ -

1145
00:50:16,150 --> 00:50:20,620
là một trong những người đang ngồi trên đầu trang của một
ghế đệm bên dưới mà có

1146
00:50:20,620 --> 00:50:21,620
mã phiếu giảm giá.

1147
00:50:21,620 --> 00:50:23,480
Bây giờ bạn có thể xem bên dưới
đệm ghế của bạn.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [VIDEO xem lại]

1150
00:50:29,680 --> 00:50:31,620
>> -Một, hai, ba.

1151
00:50:31,620 --> 00:50:35,015
>> [Hét]

1152
00:50:35,015 --> 00:50:35,985
>> -Bạn sẽ có được một chiếc xe hơi!

1153
00:50:35,985 --> 00:50:36,670
Bạn sẽ có được một chiếc xe hơi!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID Malan: Chúng ta sẽ thấy
bạn vào thứ tư.

1155
00:50:37,970 --> 00:50:38,904
>> -Bạn sẽ có được một chiếc xe hơi!

1156
00:50:38,904 --> 00:50:39,371
Bạn sẽ có được một chiếc xe hơi!

1157
00:50:39,371 --> 00:50:40,305
Bạn sẽ có được một chiếc xe hơi!

1158
00:50:40,305 --> 00:50:41,706
Bạn sẽ có được một chiếc xe hơi!

1159
00:50:41,706 --> 00:50:43,107
Bạn sẽ có được một chiếc xe hơi!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID Malan: folks Ban công, đến
xuống đây phía trước,

1161
00:50:45,530 --> 00:50:46,866
nơi chúng tôi có tính năng bổ sung.

1162
00:50:46,866 --> 00:50:50,282
>> -Mọi người đều có một chiếc xe!

1163
00:50:50,282 --> 00:50:52,234
Tất cả mọi người có một chiếc xe!

1164
00:50:52,234 --> 00:50:52,722
>> [END xem video]

1165
00:50:52,722 --> 00:50:54,590
>> Người kể chuyện: Tại tới CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5: Ôi chúa ơi ơi ơi ơi
Chúa ơi ơi ơi ơi ơi ơi -

1167
00:51:00,374 --> 00:51:02,106
>> [UKELELE lượt]