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

2
00:00:11,270 --> 00:00:14,910
>> SPEAKER: Được rồi, đây là CS50.

3
00:00:14,910 --> 00:00:19,020
Đây là cuối tuần ba, và nếu
bạn chưa tận dụng đã có,

4
00:00:19,020 --> 00:00:21,790
biết rằng sẽ có bữa ăn trưa
thứ sáu này như thường lệ, nơi

5
00:00:21,790 --> 00:00:25,430
bạn có thể thưởng thức cuộc trò chuyện tốt
và thực phẩm tại Lửa và Băng

6
00:00:25,430 --> 00:00:27,980
với một số CS50 của
nhân viên và các bạn cùng lớp.

7
00:00:27,980 --> 00:00:30,170
Đi đến URL này ở đây.

8
00:00:30,170 --> 00:00:33,420
>> Bây giờ bạn có thể nhớ lại, hoặc bạn
có thể sớm được làm quen với,

9
00:00:33,420 --> 00:00:35,970
những điều này ở đây, mà
được đưa ra ở cuối

10
00:00:35,970 --> 00:00:37,850
của học kỳ cho nhiều lớp học.

11
00:00:37,850 --> 00:00:40,870
Cuốn sách màu xanh được gọi là kỳ thi, trong đó
bạn viết câu trả lời cho các kỳ thi.

12
00:00:40,870 --> 00:00:44,240
Bây giờ tôi có ở đây 26 chẳng hạn
cuốn sách màu xanh, trên mỗi người

13
00:00:44,240 --> 00:00:47,580
được viết bằng một cái tên, từ A đến Z. Và
thực sự những cái tên đơn giản, A

14
00:00:47,580 --> 00:00:50,490
thông qua Z. Và một trong
các mục tiêu trong tầm tay hôm nay

15
00:00:50,490 --> 00:00:53,910
là có được để tiếp tục những gì
chúng tôi bắt đầu vào thứ hai, mà không phải là

16
00:00:53,910 --> 00:00:57,830
rất nhiều nhìn vào mã, nhưng thực sự
nhìn vào những ý tưởng và giải quyết vấn đề.

17
00:00:57,830 --> 00:01:00,170
Một trong những mục tiêu và
lời hứa của khóa học này

18
00:01:00,170 --> 00:01:02,985
là để dạy cho bạn để suy nghĩ nhiều hơn
cẩn thận, có phương pháp hơn,

19
00:01:02,985 --> 00:01:05,400
và để giải quyết vấn đề hiệu quả hơn.

20
00:01:05,400 --> 00:01:09,526
Và quả thực, chúng ta có thể làm điều đó thực sự
mà không cần chạm vào một dòng mã.

21
00:01:09,526 --> 00:01:12,150
Vì vậy, tôi có một vài con voi
ở đây ngày hôm nay, màu cam và màu xanh,

22
00:01:12,150 --> 00:01:15,780
nếu chúng ta có thể có được một tình nguyện viên,
có thể từ xa trở lại hơn bình thường.

23
00:01:15,780 --> 00:01:18,070
Làm thế nào về ngay, nhanh lên xuống.

24
00:01:18,070 --> 00:01:24,180
Mục tiêu trong số đó là có được để
giúp đỡ cộng với quản lý kỳ thi này ở đây.

25
00:01:24,180 --> 00:01:24,935
Tên của bạn là gì?

26
00:01:24,935 --> 00:01:25,768
>> TƯỢNG: Mary Beth.

27
00:01:25,768 --> 00:01:27,560
SPEAKER: Mary Beth, đi lên trên.

28
00:01:27,560 --> 00:01:29,560
Hãy để tôi có được microphone ở bên em.

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
Rất vui được gặp bạn.

31
00:01:32,880 --> 00:01:34,005
>> TƯỢNG: Rất vui được gặp bạn.

32
00:01:34,005 --> 00:01:36,790
SPEAKER: Được rồi, vì vậy tôi có
ở đây cuốn sách màu xanh từ A đến Z,

33
00:01:36,790 --> 00:01:41,680
và tôi sẽ giả vờ rằng
Tôi có một trong các sinh viên,

34
00:01:41,680 --> 00:01:45,770
và họ đang đến trong hơi ngẫu nhiên
ở phần cuối của một khối thi ba giờ,

35
00:01:45,770 --> 00:01:49,400
vì vậy họ kết thúc trong một số
để bán ngẫu nhiên như thế này.

36
00:01:49,400 --> 00:01:54,510
Bây giờ công việc của bạn chỉ trong một thời điểm sẽ
để be-- này thực sự là như thế nào họ nhận được

37
00:01:54,510 --> 00:01:56,820
lại vào cuối năm
lớp, có khả năng nhất.

38
00:01:56,820 --> 00:02:01,120
Công việc của bạn bây giờ là có được, khá
đơn giản, để sắp xếp những cuốn sách màu xanh cho chúng tôi

39
00:02:01,120 --> 00:02:05,220
từ A đến Z.

40
00:02:05,220 --> 00:02:08,400
>> TƯỢNG: Ồ, đây là
sẽ mất mãi mãi.

41
00:02:08,400 --> 00:02:13,747
>> SPEAKER: Và chúng ta sẽ xem
khi bạn làm điều này, không có áp lực.

42
00:02:13,747 --> 00:02:15,330
TƯỢNG: Không, không có áp lực hay bất cứ điều gì.

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> SPEAKER: Và cho vui,
chúng ta hãy đưa ra một bộ đếm thời gian.

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> TƯỢNG: Vì vậy, nhiều niềm vui, rất nhiều niềm vui.

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> SPEAKER: Tôi có thể giữ mic cho bạn.

49
00:02:38,574 --> 00:02:40,240
Được rồi, chúng tôi đã chỉ tăng gấp đôi tốc độ của chúng tôi.

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
Vì vậy, trong khi chờ đợi, hãy để tôi đặt ra những gì
sẽ là câu hỏi dành cho Mary Beth

52
00:02:49,060 --> 00:02:51,540
là những gì cô ấy làm, làm thế nào là
cô đi về giải quyết này?

53
00:02:51,540 --> 00:02:54,040
Và trong thực tế, bạn có thể không có
bao giờ nghĩ về một cái gì đó

54
00:02:54,040 --> 00:02:57,440
rất đơn giản như khi bạn chọn
tăng 26 cuốn sách như thế này,

55
00:02:57,440 --> 00:02:59,350
mà không có một tự nhiên
ra lệnh cho họ.

56
00:02:59,350 --> 00:03:01,335
Quá trình này là gì
mà bạn thực sự sử dụng không?

57
00:03:01,335 --> 00:03:03,770
Có khá ngẫu nhiên chỉ
chọn một trong những đầu tiên bạn thấy

58
00:03:03,770 --> 00:03:05,250
và đặt nó trong vị trí của nó?

59
00:03:05,250 --> 00:03:09,680
Đừng đầu tiên bạn di chuyển bàn tay của bạn xung quanh
tìm kiếm A sau đó tìm kiếm B?

60
00:03:09,680 --> 00:03:11,722
Bạn hãy nhìn vào một
cặp chúng cạnh nhau

61
00:03:11,722 --> 00:03:14,680
và chỉ nói, chờ một phút, điều này
là không đúng, và sau đó trao đổi thứ tự?

62
00:03:14,680 --> 00:03:16,960
Chúng tôi đã nhìn thấy vào hôm thứ Hai
rằng có một số cách

63
00:03:16,960 --> 00:03:22,140
trong đó chúng ta có thể làm điều này, và
thực sự là chúng tôi gần kết thúc ở đây,

64
00:03:22,140 --> 00:03:26,360
Tôi sẽ để ý có lẽ
những gì Mary Beth đang làm.

65
00:03:26,360 --> 00:03:30,040
Chúng tôi có một vài cọc có vẻ như, một
lớn hơn một, ba nhỏ hơn.

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> TƯỢNG: Tôi ra lệnh cho họ
khi tôi tìm thấy hai chữ cái

68
00:03:36,415 --> 00:03:39,540
mà tôi biết ở bên nhau trong một chuỗi,
Tôi đặt chúng lại với nhau vì vậy mà tôi không

69
00:03:39,540 --> 00:03:42,915
phải lo lắng về việc giữ gìn
theo dõi của một hàng toàn bộ cuốn sách.

70
00:03:42,915 --> 00:03:45,706
Nó chỉ là, oh, A là lần đầu tiên,
Tôi đã có chồng này ở đây.

71
00:03:45,706 --> 00:03:47,580
SPEAKER: Vì vậy, gần như
một mảnh ghép mà

72
00:03:47,580 --> 00:03:49,860
có hình dạng quyền
phù hợp với nhau.

73
00:03:49,860 --> 00:03:51,026
TƯỢNG: Khá nhiều, yeah.

74
00:03:51,026 --> 00:03:55,320
SPEAKER: OK, tuyệt vời.

75
00:03:55,320 --> 00:03:59,850
Và bây giờ mỗi
cọc có lẽ đó là sắp xếp?

76
00:03:59,850 --> 00:04:00,990
>> TƯỢNG: Vâng.

77
00:04:00,990 --> 00:04:09,900
>> SPEAKER: Được rồi, từ A đến Z. Tất cả
đúng, xin chúc mừng, bạn đã làm nó.

78
00:04:09,900 --> 00:04:11,461
Bạn có sự lựa chọn của bạn.

79
00:04:11,461 --> 00:04:11,960
Màu xanh?

80
00:04:11,960 --> 00:04:13,530
Được rồi, cảm ơn bạn vì điều đó.

81
00:04:13,530 --> 00:04:16,679
Vì vậy, Mary Beth đã đề xuất
những cách tiếp cận cô,

82
00:04:16,679 --> 00:04:19,720
nhưng cách tiếp cận khác là những gì làm thế nào bạn
có thể đi về sắp xếp những việc này?

83
00:04:19,720 --> 00:04:21,130
Những gì bạn sẽ làm gì?

84
00:04:21,130 --> 00:04:24,060
Biên bản để đánh bại sẽ có được
một phút và 50 giây hoặc lâu hơn,

85
00:04:24,060 --> 00:04:26,039
cộng với những cái tôi quên đếm.

86
00:04:26,039 --> 00:04:27,080
Những gì bạn sẽ làm gì?

87
00:04:27,080 --> 00:04:27,579
Vâng?

88
00:04:27,579 --> 00:04:28,735
TƯỢNG: Lấy chồng.

89
00:04:28,735 --> 00:04:29,776
Bắt đầu từ đầu.

90
00:04:29,776 --> 00:04:32,284
Kiểm tra giấy tờ của bạn.

91
00:04:32,284 --> 00:04:36,586
Và nếu một trong những đầu cao
hơn, có thể, họ đang có,

92
00:04:36,586 --> 00:04:38,980
một trong những chốt là
cao hơn, sau đó chuyển đổi chúng.

93
00:04:38,980 --> 00:04:41,300
>> SPEAKER: OK, vì vậy bắt đầu
ở phía trên và phía dưới,

94
00:04:41,300 --> 00:04:43,716
và sau đó làm việc theo cách của bạn
hướng nội như vậy, trao đổi chúng?

95
00:04:43,716 --> 00:04:46,580
OK, vì vậy một chút tương tự
với tinh thần bong bóng sắp xếp,

96
00:04:46,580 --> 00:04:49,160
nhưng việc lựa chọn những thái cực
không phải là cặp liền kề.

97
00:04:49,160 --> 00:04:52,080
Nhưng ngắn của nó là có
chắc chắn là một loạt các cách khác nhau

98
00:04:52,080 --> 00:04:54,210
chúng ta có thể làm điều này, và
thẳng thắn, tôi nghĩ rằng bạn loại

99
00:04:54,210 --> 00:04:55,700
áp dụng một vài phương pháp tiếp cận, phải không?

100
00:04:55,700 --> 00:05:00,567
Bạn đã thực hiện sắp xếp của bốn cọc được sắp xếp, và
sau đó hiệu quả hợp chúng lại với nhau.

101
00:05:00,567 --> 00:05:02,650
Và đó là, dám nói, một
kỹ thuật hoàn toàn.

102
00:05:02,650 --> 00:05:06,950
Bạn đã không xử lý nó như một chồng,
bạn chia vấn đề thành bốn quads,

103
00:05:06,950 --> 00:05:09,820
nếu bạn muốn, và sau đó bằng cách nào đó
sáp nhập chúng cuối cùng.

104
00:05:09,820 --> 00:05:13,410
>> Vì vậy, hãy cân nhắc, cuối cùng,
làm thế nào khác chúng ta có thể làm điều này.

105
00:05:13,410 --> 00:05:15,860
Chúng tôi chính thức hóa khái niệm
các bong bóng sắp xếp thời gian qua,

106
00:05:15,860 --> 00:05:18,780
và bong bóng sắp xếp thu hồi là một
thuật toán mà chúng tôi hình dung

107
00:05:18,780 --> 00:05:22,640
với tám người bạn cùng lớp của bạn lên đây,
dường như được sắp xếp ngẫu nhiên lần đầu tiên.

108
00:05:22,640 --> 00:05:26,110
Và sau đó chúng tôi quyết định cặp, nếu
hai yếu tố là ra lệnh,

109
00:05:26,110 --> 00:05:26,950
chỉ đơn giản là trao đổi chúng.

110
00:05:26,950 --> 00:05:28,930
Vì vậy, bốn và hai là
rõ ràng là ra lệnh,

111
00:05:28,930 --> 00:05:31,080
vì vậy hai bạn cùng lớp
chuyển vị trí.

112
00:05:31,080 --> 00:05:35,390
Và sau đó chúng ta lặp đi lặp lại với bốn và sáu,
sau đó sáu và tám, trên mỗi lần lặp,

113
00:05:35,390 --> 00:05:36,980
di chuyển sang phải.

114
00:05:36,980 --> 00:05:42,590
>> Vì vậy, cho tám người, có bao nhiêu cặp
so sánh những gì đã làm trong khi đi bộ từ

115
00:05:42,590 --> 00:05:45,220
trái sang phải trong một sự lặp lại như vậy?

116
00:05:45,220 --> 00:05:48,410
Có bao nhiêu so sánh?

117
00:05:48,410 --> 00:05:49,197
Bảy, phải không?

118
00:05:49,197 --> 00:05:51,405
Bởi vì nếu có tám
mọi người nhưng bạn có cặp

119
00:05:51,405 --> 00:05:53,880
họ và bạn tiếp tục di chuyển
một hop bên phải,

120
00:05:53,880 --> 00:05:56,060
bạn sẽ không có tám
so sánh bởi vì bạn không thể so sánh

121
00:05:56,060 --> 00:05:59,226
một yếu tố chống lại chính nó, hoặc nó sẽ
chỉ là vô nghĩa, vì vậy bạn có bảy.

122
00:05:59,226 --> 00:06:01,290
Hay rộng hơn, nếu
chúng tôi có n người, chúng tôi

123
00:06:01,290 --> 00:06:04,300
làm n trừ đi 1 so sánh
với bong bóng sắp xếp.

124
00:06:04,300 --> 00:06:08,150
>> Vì vậy, chúng ta hãy xem xét bây giờ như thế nào tốt hay
bong bóng xấu loại thực sự là, và cố gắng

125
00:06:08,150 --> 00:06:13,570
để cung cấp cho mình vốn từ vựng với
để thuật toán phê bình như thế này,

126
00:06:13,570 --> 00:06:14,430
và ngay sau đó của chúng ta.

127
00:06:14,430 --> 00:06:16,970
Vì vậy, đầu tiên vượt qua thông qua
bong bóng sắp xếp, lần đầu tiên

128
00:06:16,970 --> 00:06:20,909
Tôi đi từ trái qua phải của
sân khấu, đã cho tôi n trừ đi 1 so sánh.

129
00:06:20,909 --> 00:06:22,950
Và đó sẽ là của tôi
đơn vị đo lường, phải không?

130
00:06:22,950 --> 00:06:26,170
Tôi đã loại nói chuyện và đi dạo,
hơi nhanh, hơi chậm,

131
00:06:26,170 --> 00:06:29,300
để đếm số của tôi giây
không đặc biệt nói,

132
00:06:29,300 --> 00:06:32,260
nhưng đếm số lượng
hoạt động mà tôi đã làm vào thứ hai,

133
00:06:32,260 --> 00:06:35,900
so sánh hai người, mà cảm thấy
như một đơn vị tốt đẹp của các biện pháp.

134
00:06:35,900 --> 00:06:40,980
>> Vì vậy, n trừ đi 1 bước là lần đầu tiên,
nhưng sau đó những gì xảy ra sau đó?

135
00:06:40,980 --> 00:06:46,610
Một trong những xu hướng tăng của một đường chuyền là gì
thông qua một danh sách khác được phân loại?

136
00:06:46,610 --> 00:06:49,840
Những gì bạn có thể cho tôi biết về các yếu tố
là ai tất cả các cách trên không?

137
00:06:49,840 --> 00:06:51,300
Vâng?

138
00:06:51,300 --> 00:06:52,870
Đó là yếu tố lớn nhất, phải không?

139
00:06:52,870 --> 00:06:55,710
Số tám, mặc dù cô
bắt đầu ở đây, mỗi khi tôi

140
00:06:55,710 --> 00:06:57,860
so sánh cô với
một người hàng xóm, cô vẫn giữ

141
00:06:57,860 --> 00:07:00,480
nổi lên bên phải
bên của danh sách.

142
00:07:00,480 --> 00:07:02,710
Và quả thực, đó là nơi
các thuật toán được tên của nó.

143
00:07:02,710 --> 00:07:07,630
>> Bây giờ bằng cách logic, có bao nhiêu so sánh
cần tôi thực hiện trên lần thứ hai

144
00:07:07,630 --> 00:07:09,800
Tôi thực hiện qua đó từ trái sang phải?

145
00:07:09,800 --> 00:07:10,730
n trừ đi 2, phải không?

146
00:07:10,730 --> 00:07:14,297
Nó sẽ chỉ lãng phí thời gian của tôi nếu tôi
giữ tám so sánh với một người nào đó

147
00:07:14,297 --> 00:07:16,630
khác vì chúng ta đã biết
cô đã ở đúng nơi.

148
00:07:16,630 --> 00:07:19,760
Vì vậy, đó là một chút của một
tối ưu hóa, do đó, qua tiếp theo

149
00:07:19,760 --> 00:07:23,899
là có được cộng với n trừ đi hai bước,
trong đó n là số lượng người.

150
00:07:23,899 --> 00:07:26,940
Bây giờ bạn có thể loại suy, thậm chí
nếu bạn không phải là một nhà khoa học máy tính,

151
00:07:26,940 --> 00:07:27,680
cách này kết thúc.

152
00:07:27,680 --> 00:07:31,259
Vào cuối của thuật toán này, có lẽ
bạn đã có chỉ là một so sánh lại.

153
00:07:31,259 --> 00:07:33,800
Bạn cần phải loại sửa chữa
bắt đầu của danh sách trong trường hợp hai

154
00:07:33,800 --> 00:07:36,540
và một là ra lệnh
và nên là một và hai,

155
00:07:36,540 --> 00:07:40,330
vì vậy đây đáy hiện tại
cộng thêm 1 so sánh thức.

156
00:07:40,330 --> 00:07:44,500
>> Bây giờ các dấu chấm, dấu chấm, dấu chấm loại sóng đó là
tay ở một số chi tiết juicier,

157
00:07:44,500 --> 00:07:46,452
nhưng chúng ta chỉ cần đi trước và đơn giản hóa.

158
00:07:46,452 --> 00:07:48,660
Nếu bạn nhớ lại từ mức cao
trường học, thẳng thắn, rất nhiều bạn

159
00:07:48,660 --> 00:07:50,340
có cuốn sách toán học mà có
một chút cheat sheet

160
00:07:50,340 --> 00:07:52,550
trên trang bìa hoặc
bìa sau cho thấy bạn

161
00:07:52,550 --> 00:07:56,400
summations loạt như những gì
điều này cuối cùng thêm lên đến.

162
00:07:56,400 --> 00:07:59,600
Trong trường hợp chung, nếu bạn có một
biến như n, và thực sự thế này,

163
00:07:59,600 --> 00:08:01,634
nếu bạn nhìn của bạn
cuốn sách toán học cũ,

164
00:08:01,634 --> 00:08:04,050
bạn sẽ thấy rằng điều này thực sự
thêm lên đến số tiền này ở đây,

165
00:08:04,050 --> 00:08:07,970
n lần n trừ đi 1 tất cả chia cho 2.

166
00:08:07,970 --> 00:08:11,172
Vì vậy, bây giờ hãy để tôi chỉ định
điều này là đúng, như vậy một bước nhảy vọt của đức tin,

167
00:08:11,172 --> 00:08:12,880
đó là những gì này tóm tắt
đến, và chúng ta có thể

168
00:08:12,880 --> 00:08:14,341
chứng minh rằng trong trường hợp tổng quát hơn.

169
00:08:14,341 --> 00:08:15,590
Nhưng bây giờ chúng ta hãy mở rộng này ra.

170
00:08:15,590 --> 00:08:19,920
Vì vậy, hãy nhân này ra, vì vậy đó là
n bình phương, trừ đi n, tất cả chia cho 2.

171
00:08:19,920 --> 00:08:23,200
Đó là thực sự n bình phương,
chia cho 2, trừ n hơn 2,

172
00:08:23,200 --> 00:08:25,010
vì vậy đó là tất cả tốt đẹp và thú vị.

173
00:08:25,010 --> 00:08:27,060
Nhưng những gì xảy ra nếu chúng ta
tại plug-in một giá trị?

174
00:08:27,060 --> 00:08:29,724
Giả sử tôi không có tám
người, nhưng nói một triệu USD.

175
00:08:29,724 --> 00:08:31,890
Và một triệu chỉ vì
đó là một số lượng khá lớn,

176
00:08:31,890 --> 00:08:34,039
hãy cắm vào đó và xem những gì sẽ xảy ra.

177
00:08:34,039 --> 00:08:39,039
Vì vậy, nếu tôi cắm một triệu USD vào công thức
Tôi sẽ nhận được một triệu phương,

178
00:08:39,039 --> 00:08:42,868
chia cho 2, trừ một
triệu, chia cho 2.

179
00:08:42,868 --> 00:08:44,159
Bây giờ những gì mà sẽ bằng?

180
00:08:44,159 --> 00:08:47,354
Vì vậy, 500 tỷ, trừ đi 500.000.

181
00:08:47,354 --> 00:08:49,270
Và nếu tôi thực sự làm
mà toán học ra, có nghĩa là

182
00:08:49,270 --> 00:08:53,920
mà sắp xếp một triệu
những người có các loại bong bóng

183
00:08:53,920 --> 00:09:01,800
có thể đưa tôi 499.999.500.000
bước hoặc so sánh cuối cùng,

184
00:09:01,800 --> 00:09:02,900
chúng tôi chỉ ngoại suy.

185
00:09:02,900 --> 00:09:06,860
>> Mà cảm thấy khá chậm, nhưng thẳng thắn
đo một đầu vào đặc biệt

186
00:09:06,860 --> 00:09:09,160
như thế này, không phải là tất cả những gì kể.

187
00:09:09,160 --> 00:09:14,050
Nhưng thực sự nó không cho thấy có đến n
được lớn hơn và lớn hơn, thuật toán này

188
00:09:14,050 --> 00:09:16,280
loại cảm thấy tồi tệ hơn và
tồi tệ hơn, hoặc bạn thực sự

189
00:09:16,280 --> 00:09:20,450
bắt đầu cảm thấy nỗi đau đó
lũy thừa, n là hình vuông,

190
00:09:20,450 --> 00:09:21,770
được biết thêm khá nhanh.

191
00:09:21,770 --> 00:09:25,340
Và chi tiết này không phải là
bị mất trên người, trên thực tế

192
00:09:25,340 --> 00:09:29,640
một số năm trước, một thượng nghị sĩ nào đó là ai
vận động, ngồi xuống cho một cuộc phỏng vấn

193
00:09:29,640 --> 00:09:32,180
với Eric của Google
Schmidt, Giám đốc điều hành vào thời điểm đó,

194
00:09:32,180 --> 00:09:36,380
và đã được thử thách với một câu hỏi
giống như chúng ta đang khai thác hiện nay.

195
00:09:36,380 --> 00:09:38,468
Chúng ta hãy có một cái nhìn.

196
00:09:38,468 --> 00:09:45,280
>> [VIDEO xem lại]

197
00:09:45,280 --> 00:09:48,560
>> -Senator, Bạn đang ở đây
tại Google, và tôi thích

198
00:09:48,560 --> 00:09:53,382
suy nghĩ của tổng thống
như một cuộc phỏng vấn việc làm.

199
00:09:53,382 --> 00:09:56,434
Bây giờ, thật khó để có được
một công việc làm tổng thống,

200
00:09:56,434 --> 00:09:58,100
và bạn đang trải qua sự khắc nghiệt bây giờ.

201
00:09:58,100 --> 00:10:01,860
Nó cũng khó để có được một công việc tại Google.

202
00:10:01,860 --> 00:10:05,490
Chúng tôi có câu hỏi, và chúng tôi
đặt câu hỏi các ứng cử viên của chúng tôi,

203
00:10:05,490 --> 00:10:09,770
và điều này là từ Larry Schwimmer.

204
00:10:09,770 --> 00:10:14,760
What-- các bạn nghĩ tôi
đùa, đó là ngay tại đây.

205
00:10:14,760 --> 00:10:17,930
Cách hiệu quả nhất để là gì
sắp xếp một số nguyên triệu 32-bit?

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> Tôi xin lỗi, maybe--

209
00:10:25,200 --> 00:10:27,400
>> Không, không, không.

210
00:10:27,400 --> 00:10:30,700
Tôi nghĩ rằng các loại bong bóng
sẽ là con đường sai để đi.

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> -Thôi Nào, người nói với anh điều này?

213
00:10:38,180 --> 00:10:40,590
Tôi không nhìn thấy máy tính
khoa học trong nền của bạn.

214
00:10:40,590 --> 00:10:42,130
>> -We've Có gián điệp của chúng tôi trong đó.

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -Ok, Hãy hỏi một khác nhau
câu hỏi phỏng vấn.

217
00:10:48,444 --> 00:10:49,300
>> [END IMG xem lại]

218
00:10:49,300 --> 00:10:52,290
>> SPEAKER: Vì vậy, nói về
mặc dù con số cụ thể,

219
00:10:52,290 --> 00:10:53,890
sẽ không có tất cả những gì hữu ích.

220
00:10:53,890 --> 00:10:56,810
Nó không phải là một bài học cuộc sống mà bong bóng
sắp xếp, cho một triệu đầu vào,

221
00:10:56,810 --> 00:10:58,590
có thể mất bao nhiêu là 500 tỷ bước.

222
00:10:58,590 --> 00:11:01,120
Bạn có thể không thực sự khái quát
quá hiệu quả từ đó

223
00:11:01,120 --> 00:11:03,560
và đưa ra quyết định thiết kế tốt
khi viết chương trình.

224
00:11:03,560 --> 00:11:07,070
Vì vậy, hãy tập trung mặc dù về cách
chúng ta có thể đơn giản hóa kết quả này.

225
00:11:07,070 --> 00:11:11,780
>> Vì vậy, tôi đã đánh dấu màu vàng ở đây
kết quả của n bình phương chia cho 2,

226
00:11:11,780 --> 00:11:14,330
do đó, một triệu phương
chia cho 2, và sau đó

227
00:11:14,330 --> 00:11:16,710
Tôi đã nhấn mạnh những gì
câu trả lời cuối cùng là

228
00:11:16,710 --> 00:11:20,180
một khi chúng ta trừ đi n chia cho 2.

229
00:11:20,180 --> 00:11:24,850
Và tuyên bố tôi sẽ làm bây giờ,
người có hề quan tâm nếu bạn trừ đi

230
00:11:24,850 --> 00:11:30,060
một chút n cũ hơn 2 khi lần đầu tiên
một phần của công thức này là như vậy lớn hơn nhiều?

231
00:11:30,060 --> 00:11:33,910
Nó chi phối khác
hạn, n bình phương chia cho 2

232
00:11:33,910 --> 00:11:37,510
có kích thước lớn, rõ ràng, như
n được lớn như một triệu,

233
00:11:37,510 --> 00:11:41,450
đó là có thực sự là một sự khác biệt lớn ở
cuối ngày giữa 500 tỷ

234
00:11:41,450 --> 00:11:45,730
và 499.999.500.000?

235
00:11:45,730 --> 00:11:46,349
Không thực sự.

236
00:11:46,349 --> 00:11:48,640
Và vì vậy những gì chúng ta sẽ
làm như các nhà khoa học máy tính

237
00:11:48,640 --> 00:11:53,270
bỏ qua những điều kiện bậc thấp hơn và
có một cái gì đó như thế này và thực sự

238
00:11:53,270 --> 00:11:56,050
chỉ đơn giản hóa nó đến
hạn đó sẽ có vấn đề.

239
00:11:56,050 --> 00:12:00,315
Lớn hơn các bộ dữ liệu của chúng tôi có được, lớn hơn
cơ sở dữ liệu của chúng tôi có được, các trang web nhiều hơn

240
00:12:00,315 --> 00:12:02,690
chúng ta phải tìm kiếm, càng có nhiều
bạn bè bạn có trên Facebook.

241
00:12:02,690 --> 00:12:07,340
>> Khi n càng lớn hơn, chúng tôi thực sự
sẽ quan tâm lớn nhất

242
00:12:07,340 --> 00:12:11,560
hạn trong bất kỳ phân tích như vậy
thực hiện các thuật toán của chúng tôi.

243
00:12:11,560 --> 00:12:16,230
Và tôi sẽ nói, bạn biết những gì,
bong bóng sắp xếp là vào thứ tự của O lớn,

244
00:12:16,230 --> 00:12:18,060
vào thứ tự của n bình phương.

245
00:12:18,060 --> 00:12:20,090
Nó không chính xác n
phương như chúng ta đã thấy,

246
00:12:20,090 --> 00:12:22,060
nhưng những người thực sự quan tâm
về những điều khoản nhỏ hơn,

247
00:12:22,060 --> 00:12:24,390
và thẳng thắn, những người thực sự
quan tâm nếu chúng ta chia cho 2?

248
00:12:24,390 --> 00:12:25,870
Đó chỉ là một yếu tố không đổi.

249
00:12:25,870 --> 00:12:29,480
Và là 500 tỷ đồng so với 250
tỷ thực sự là vấn đề lớn?

250
00:12:29,480 --> 00:12:32,190
Tôi chỉ có thể chờ đợi một năm,
cho máy tính xách tay của tôi theo nghĩa đen

251
00:12:32,190 --> 00:12:34,810
được nhanh gấp hai lần trong phần cứng,
và sắp xếp của sự khác biệt

252
00:12:34,810 --> 00:12:36,650
chỉ mất đi một cách tự nhiên theo thời gian.

253
00:12:36,650 --> 00:12:39,300
>> Những gì chúng tôi quan tâm là
các biểu hiện, phần

254
00:12:39,300 --> 00:12:42,489
của biểu thức đó là sẽ thay đổi
như là đầu vào của chúng tôi được lớn hơn và lớn hơn.

255
00:12:42,489 --> 00:12:45,280
Và quả thực, trong thế giới thực,
đó là những gì đang xảy ra ngày càng

256
00:12:45,280 --> 00:12:48,330
là đầu vào cho các vấn đề của chúng tôi và
thuật toán được nhận được lớn hơn.

257
00:12:48,330 --> 00:12:53,470
Vì vậy, O lớn là có được các ký hiệu,
các ký hiệu tiệm cận, mà chúng tôi chỉ

258
00:12:53,470 --> 00:12:57,160
sử dụng như là các nhà khoa học máy tính để mô tả
hiệu quả hoạt động, hoặc thời gian chạy,

259
00:12:57,160 --> 00:12:58,130
của một thuật toán.

260
00:12:58,130 --> 00:13:00,800
Vì vậy, chúng ta có thể so sánh các thuật toán
trên các máy tính khác nhau bằng văn bản

261
00:13:00,800 --> 00:13:04,170
bởi những người khác nhau, bằng cách sử dụng
một số số liệu về cơ bản tương tự

262
00:13:04,170 --> 00:13:07,557
như số lượng so sánh bạn
làm, hoặc có thể là số lượng giao dịch hoán đổi

263
00:13:07,557 --> 00:13:08,140
bạn đang làm.

264
00:13:08,140 --> 00:13:11,910
>> Những gì chúng ta sẽ không
số là số lượng thời gian

265
00:13:11,910 --> 00:13:13,981
mà đi trên đồng hồ
trên tường thường.

266
00:13:13,981 --> 00:13:16,230
Những gì chúng ta sẽ không phải lo lắng
về là bao nhiêu bộ nhớ

267
00:13:16,230 --> 00:13:17,820
bạn đang sử dụng ngày hôm nay tại
ít nhất, mặc dù đó là

268
00:13:17,820 --> 00:13:19,370
một nguồn tài nguyên chúng ta có thể đo lường.

269
00:13:19,370 --> 00:13:23,610
Chúng tôi sẽ cố gắng để căn cứ phân tích của chúng tôi
trên chỉ là hoạt động cơ bản, những người,

270
00:13:23,610 --> 00:13:25,930
thẳng thắn, bạn có thể xem trực quan nhất.

271
00:13:25,930 --> 00:13:30,700
Vì vậy, với một cái gì đó như O lớn của n
phương, tôi cho rằng O n bình phương

272
00:13:30,700 --> 00:13:35,820
là một trên ràng buộc về cái gọi là
chạy thời điểm bong bóng sắp xếp.

273
00:13:35,820 --> 00:13:38,820
Nói cách khác, nếu bạn
muốn khẳng định rằng có

274
00:13:38,820 --> 00:13:41,370
giới hạn trên này có bao nhiêu
bước một thuật toán có thể mất,

275
00:13:41,370 --> 00:13:46,240
nó sẽ được trong O lớn của n
phương trong trường hợp này, một trên ràng buộc.

276
00:13:46,240 --> 00:13:49,710
>> Nếu tôi thay vì thay đổi
câu chuyện là không về bong bóng sắp xếp,

277
00:13:49,710 --> 00:13:50,910
nhưng về điều này ràng buộc trên.

278
00:13:50,910 --> 00:13:54,030
Bạn có thể nghĩ về một thuật toán
mà chúng tôi đã nhìn đã

279
00:13:54,030 --> 00:13:59,530
có trên ràng buộc, tối đa
đo thời gian hoặc hoạt động,

280
00:13:59,530 --> 00:14:04,300
sẽ được cho là được bao quanh
bởi n, chức năng tuyến tính,

281
00:14:04,300 --> 00:14:07,260
không phải là một bậc hai đó là cong?

282
00:14:07,260 --> 00:14:10,780
Một thuật toán là cái gì
luôn luôn có không

283
00:14:10,780 --> 00:14:12,860
hơn như n bước, hoặc
Bước 2n, hoặc các bước 3n?

284
00:14:12,860 --> 00:14:13,360
Vâng?

285
00:14:13,360 --> 00:14:15,030
>> TƯỢNG: Tìm kiếm
số lượng lớn nhất trong một danh sách?

286
00:14:15,030 --> 00:14:16,930
>> SPEAKER: Perfect, tìm kiếm
số lượng lớn nhất trong danh sách.

287
00:14:16,930 --> 00:14:18,940
Nếu tôi đưa ra một danh sách các
người chẳng hạn,

288
00:14:18,940 --> 00:14:21,440
mỗi người đang nắm giữ một số,
số lượng tối đa là những gì

289
00:14:21,440 --> 00:14:23,770
các bước nó sẽ đưa tôi,
một người khá thông minh,

290
00:14:23,770 --> 00:14:27,530
để tìm thấy những người lớn nhất trong danh sách đó?

291
00:14:27,530 --> 00:14:28,100
n, phải không?

292
00:14:28,100 --> 00:14:31,320
Bởi vì trong trường hợp xấu nhất, nơi
có giá trị lớn nhất là gì?

293
00:14:31,320 --> 00:14:32,700
Phải, tất cả các cách ở cuối.

294
00:14:32,700 --> 00:14:34,575
Vì vậy, trong trường hợp xấu nhất
trên ràng buộc, tôi có thể

295
00:14:34,575 --> 00:14:36,450
phải đi tất cả các cách
ở đây và như thế nào,

296
00:14:36,450 --> 00:14:39,170
oh, đây là số tám,
hoặc bất cứ điều gì giá trị là.

297
00:14:39,170 --> 00:14:41,330
Bây giờ nó sẽ chỉ là ngu ngốc
nếu tôi tiếp tục đi, phải không?

298
00:14:41,330 --> 00:14:43,840
Tìm kiếm ngày càng nhiều yếu tố
nếu cuối cùng của họ là ở đó?

299
00:14:43,840 --> 00:14:45,340
Vì vậy, chắc chắn, n là một ràng buộc trên.

300
00:14:45,340 --> 00:14:47,420
Tôi không cần phải
bước nhiều hơn thế.

301
00:14:47,420 --> 00:14:51,580
>> Vì vậy, nếu thay vào đó tôi đã đề xuất
có những thuật toán trong thế giới này mà

302
00:14:51,580 --> 00:14:57,750
có một thời gian chạy đó là
giới hạn bởi O lớn của log n, log n?

303
00:14:57,750 --> 00:15:00,390
Trong trường hợp chúng tôi đã nhìn thấy điều này trước khi?

304
00:15:00,390 --> 00:15:00,890
Vâng?

305
00:15:00,890 --> 00:15:03,309
>> TƯỢNG: Trong vấn đề danh bạ điện thoại?

306
00:15:03,309 --> 00:15:04,850
SPEAKER: Cũng giống như các vấn đề danh bạ điện thoại.

307
00:15:04,850 --> 00:15:07,754
Biện pháp như thế nào là gì
nhiều thời gian hoặc có bao nhiêu nước mắt nó

308
00:15:07,754 --> 00:15:10,170
took tôi tìm thấy một người như
Mike Smith trong sổ điện thoại?

309
00:15:10,170 --> 00:15:13,212
Chúng tôi tuyên bố đó là log n, và
ngay cả khi không quen thuộc hoặc nó nó

310
00:15:13,212 --> 00:15:15,170
mơ hồ một chút những gì một
logarit hoặc mũ là,

311
00:15:15,170 --> 00:15:17,650
chỉ cần nhớ rằng log n
thường dùng để chỉ quá trình này,

312
00:15:17,650 --> 00:15:20,790
trong trường hợp này, chia
một cái gì đó trong một nửa một lần nữa, và một lần nữa,

313
00:15:20,790 --> 00:15:25,790
và một lần nữa, và một lần nữa, như vậy mà nó
được ngày càng nhỏ như bạn làm điều đó.

314
00:15:25,790 --> 00:15:28,470
>> Vì vậy, đăng nhập của n đề cập, chắc chắn,
với ví dụ danh bạ điện thoại,

315
00:15:28,470 --> 00:15:32,662
để tìm kiếm nhị phân trong lý thuyết, khi chúng tôi
có cửa ảo trên diễn đàn,

316
00:15:32,662 --> 00:15:34,370
hoặc khi Sean là
tìm kiếm một cái gì đó.

317
00:15:34,370 --> 00:15:37,374
Nếu ông đã sử dụng tìm kiếm nhị phân, đăng nhập n
sẽ là giới hạn trên bao nhiêu

318
00:15:37,374 --> 00:15:38,040
thời gian mà có.

319
00:15:38,040 --> 00:15:44,027
Nhưng những thuật toán chạy trong
log n giả định những gì quan trọng cụ thể?

320
00:15:44,027 --> 00:15:45,360
Đó là danh sách đã được sắp xếp, phải không?

321
00:15:45,360 --> 00:15:47,789
Thuật toán của bạn là sai lầm nếu
đầu vào của bạn không được sắp xếp,

322
00:15:47,789 --> 00:15:49,830
nhưng bạn đang sử dụng
cái gì đó như tìm kiếm nhị phân

323
00:15:49,830 --> 00:15:51,704
bởi vì bạn có thể nhảy
quyền đối với các phần tử

324
00:15:51,704 --> 00:15:53,600
mà không nhận ra nó thực sự có.

325
00:15:53,600 --> 00:15:55,600
>> Bây giờ điều này có thể có nghĩa là, O lớn của một trong những?

326
00:15:55,600 --> 00:15:59,117
Điều này không có nghĩa là thuật toán của bạn
có một và chỉ một bước,

327
00:15:59,117 --> 00:16:01,200
nó chỉ có nghĩa là phải mất một
hằng số của các bước.

328
00:16:01,200 --> 00:16:04,060
Có thể đó là 1, có thể đó là
10, có lẽ đó là 1000,

329
00:16:04,060 --> 00:16:07,750
nhưng nó độc lập
kích thước của vấn đề.

330
00:16:07,750 --> 00:16:10,850
Không có vấn đề lớn như thế nào là n,
một thuật toán thời gian cố định

331
00:16:10,850 --> 00:16:12,747
luôn luôn có cùng một số bước.

332
00:16:12,747 --> 00:16:15,080
Vì vậy, những gì có thể là một thuật toán
chúng tôi đã nói về hoặc chỉ

333
00:16:15,080 --> 00:16:20,418
trực giác mà đến với bạn rằng
luôn luôn chạy trong cái gọi là hằng số thời gian?

334
00:16:20,418 --> 00:16:20,918
Vâng?

335
00:16:20,918 --> 00:16:22,001
>> TƯỢNG: Thêm hai con số.

336
00:16:22,001 --> 00:16:25,320
SPEAKER: Thêm hai con số,
2 cộng 2 bằng 4, thực hiện.

337
00:16:25,320 --> 00:16:27,227
Vì vậy, có thể làm việc, những gì khác?

338
00:16:27,227 --> 00:16:28,560
Làm thế nào về thế giới thực hơn, được chứ?

339
00:16:28,560 --> 00:16:30,686
>> TƯỢNG: Tìm kiếm
Điều đầu tiên trong danh sách.

340
00:16:30,686 --> 00:16:32,810
SPEAKER: Tìm kiếm đầu tiên
phần tử trong một danh sách, chắc chắn.

341
00:16:32,810 --> 00:16:34,540
Chúng tôi đã thực sự được nói
về mảng đã có,

342
00:16:34,540 --> 00:16:36,540
làm thế nào để bạn nhận được ở
Yếu tố đầu tiên trong một mảng,

343
00:16:36,540 --> 00:16:40,465
không có vấn đề bao lâu
mảng trong C?

344
00:16:40,465 --> 00:16:43,090
Bạn chỉ cần sử dụng như khung
không ký hiệu, bam, bạn đang có.

345
00:16:43,090 --> 00:16:46,120
Và thực sự mảng, như là một sang một bên,
hỗ trợ một cái gì đó thường được biết đến

346
00:16:46,120 --> 00:16:49,240
như truy cập ngẫu nhiên, truy cập ngẫu nhiên
bộ nhớ, bởi vì bạn có thể theo nghĩa đen

347
00:16:49,240 --> 00:16:50,284
nhảy đến bất kỳ một nơi.

348
00:16:50,284 --> 00:16:52,700
Chúng ta có thể làm điều này thậm chí đơn giản hơn
chúng ta có thể quay lại với tuần không

349
00:16:52,700 --> 00:16:53,900
khi chúng tôi đã làm cào.

350
00:16:53,900 --> 00:16:59,707
Bao nhiêu thời gian đã làm nó đưa cho
nói khối trong Scratch để thực hiện?

351
00:16:59,707 --> 00:17:00,790
Chỉ cần thời gian liên tục, phải không?

352
00:17:00,790 --> 00:17:03,960
Nói điều gì đó, nói
một cái gì đó, nó không quan trọng

353
00:17:03,960 --> 00:17:07,359
cách vết xước lớn trên thế giới là, nó luôn luôn
sẽ mất cùng một lượng thời gian

354
00:17:07,359 --> 00:17:08,490
chỉ đơn giản là nói điều gì đó.

355
00:17:08,490 --> 00:17:11,089
>> Vì vậy, đó là thời gian liên tục,
nhưng mặt trái là những gì?

356
00:17:11,089 --> 00:17:13,030
Nếu đó là trên
giới hạn, nếu chúng ta muốn

357
00:17:13,030 --> 00:17:17,089
để mô tả các giới hạn thấp hơn
các thuật toán của chúng tôi thời gian chạy?

358
00:17:17,089 --> 00:17:19,852
Gần một trường hợp tốt nhất
có khả năng, nếu bạn muốn,

359
00:17:19,852 --> 00:17:23,060
mặc dù các điều khoản này có thể áp dụng cho tốt nhất
trường hợp, trường hợp xấu nhất, trường hợp trung bình hơn

360
00:17:23,060 --> 00:17:26,359
nói chung, nhưng hãy tập trung
về giới hạn thấp hơn nói chung.

361
00:17:26,359 --> 00:17:31,920
Một thuật toán mà có là gì
một giới hạn thấp hơn n bậc,

362
00:17:31,920 --> 00:17:33,350
hoặc các bước 2n, hoặc các bước 3n?

363
00:17:33,350 --> 00:17:36,241
Một số yếu tố của n bước,
đó là thấp hơn của nó bị ràng buộc.

364
00:17:36,241 --> 00:17:36,740
Vâng?

365
00:17:36,740 --> 00:17:37,910
>> TƯỢNG: Sắp xếp nổi bọt?

366
00:17:37,910 --> 00:17:41,610
>> SPEAKER: Sắp xếp nổi bọt có
bạn n tối thiểu các bước, tại sao?

367
00:17:41,610 --> 00:17:42,279
Tại sao vậy?

368
00:17:42,279 --> 00:17:45,320
Tại sao nên đầu rằng để đến với bạn
trực giác, ngay cả khi nó không chỉ

369
00:17:45,320 --> 00:17:46,530
chưa?

370
00:17:46,530 --> 00:17:47,030
Vâng?

371
00:17:47,030 --> 00:17:47,990
>> TƯỢNG: [không nghe được].

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
SPEAKER: Chính xác.

374
00:17:52,360 --> 00:17:55,810
Trong kịch bản tốt nhất có thể
bong bóng sắp xếp, và rất nhiều các thuật toán,

375
00:17:55,810 --> 00:17:58,769
nếu tôi đưa cho bạn tám người
những người đã được sắp xếp,

376
00:17:58,769 --> 00:18:00,560
nó sẽ là ngu ngốc
cho bạn, các thuật toán,

377
00:18:00,560 --> 00:18:02,202
đi lại
nhiều hơn một lần, phải không?

378
00:18:02,202 --> 00:18:04,285
Bởi vì ngay sau khi bạn
đi bộ qua danh sách một lần,

379
00:18:04,285 --> 00:18:08,090
bạn nên nhận ra, oh, tôi đã không có
giao dịch hoán đổi, danh sách này được sắp xếp, xuất cảnh.

380
00:18:08,090 --> 00:18:09,700
Nhưng điều đó sẽ đưa bạn n bước.

381
00:18:09,700 --> 00:18:12,033
>> Và ngược lại, những gì khác
cách suy nghĩ về nó?

382
00:18:12,033 --> 00:18:15,240
Sắp xếp nổi bọt là một omega,
có thể nói, của n,

383
00:18:15,240 --> 00:18:19,050
bởi vì nếu bạn nhìn vào
ít hơn n yếu tố, những gì

384
00:18:19,050 --> 00:18:23,009
là vấn đề cơ bản đó?

385
00:18:23,009 --> 00:18:24,550
Bạn không biết nếu nó được sắp xếp, phải.

386
00:18:24,550 --> 00:18:26,800
Chúng tôi con người sức mạnh trong nháy mắt tại tám
người và được như thế, oh, nó được sắp xếp,

387
00:18:26,800 --> 00:18:28,430
rằng tôi đã không mất n bước này, nhưng nó đã làm.

388
00:18:28,430 --> 00:18:30,810
Đôi mắt của bạn, ngay cả khi bạn loại
trong có một lĩnh vực lớn của tầm nhìn,

389
00:18:30,810 --> 00:18:33,184
bạn nhìn vào tám yếu tố,
bạn nhìn vào tám người,

390
00:18:33,184 --> 00:18:34,610
đó là tám bước có hiệu quả.

391
00:18:34,610 --> 00:18:38,612
Và chỉ khi tôi đi qua toàn bộ
danh sách làm tôi nhận ra, có, được sắp xếp.

392
00:18:38,612 --> 00:18:41,320
Nếu tôi dừng lại nửa chừng suy nghĩ, tất cả
phải, nó khá sắp xếp cho đến nay,

393
00:18:41,320 --> 00:18:42,520
tỷ lệ cược nó không được sắp xếp là gì?

394
00:18:42,520 --> 00:18:44,186
Đó là thuật toán sẽ không được chính xác.

395
00:18:44,186 --> 00:18:46,250
Có thể là nhanh hơn, nhưng không chính xác.

396
00:18:46,250 --> 00:18:48,500
>> Vì vậy, bây giờ chúng ta có một cách
mô tả một giới hạn thấp hơn,

397
00:18:48,500 --> 00:18:49,710
và những gì về thời gian liên tục?

398
00:18:49,710 --> 00:18:54,565
Một thuật toán mà có thấp hơn là những gì
bị ràng buộc về thời gian hoạt động của một trong những?

399
00:18:54,565 --> 00:18:58,350
1 bước, 2 bước, 10 bước, nhưng
không đổi, không phụ thuộc vào n,

400
00:18:58,350 --> 00:18:59,310
kích thước của đầu vào?

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
Vâng, ở phía sau.

403
00:19:04,600 --> 00:19:05,309
>> TƯỢNG: printf?

404
00:19:05,309 --> 00:19:06,183
SPEAKER: Cái gì thế?

405
00:19:06,183 --> 00:19:07,184
TƯỢNG: printf?

406
00:19:07,184 --> 00:19:07,850
SPEAKER: printf.

407
00:19:07,850 --> 00:19:08,400
OK, chắc chắn.

408
00:19:08,400 --> 00:19:10,720
Vì vậy, nó có một số cố định các bước.

409
00:19:10,720 --> 00:19:13,170
Và tôi nên now-- bây giờ mà
chúng ta đang nói về mã C

410
00:19:13,170 --> 00:19:16,040
và không cào, một cái gì đó
như nói, với printf,

411
00:19:16,040 --> 00:19:17,710
chúng ta nên bắt đầu để có được cẩn thận.

412
00:19:17,710 --> 00:19:21,090
Bởi vì printf không mất
đầu vào, đó là một chuỗi,

413
00:19:21,090 --> 00:19:23,220
và chuỗi làm kỹ thuật có chiều dài.

414
00:19:23,220 --> 00:19:25,530
Vì vậy, nếu bây giờ chúng ta muốn chọn
bạn, nếu bạn không nhớ,

415
00:19:25,530 --> 00:19:29,430
về mặt kỹ thuật chúng ta có thể tranh luận rằng printf
không mất một đầu vào biến chiều dài,

416
00:19:29,430 --> 00:19:32,270
và chắc chắn nó có thể mất nhiều hơn
thời gian in một chuỗi dài này,

417
00:19:32,270 --> 00:19:33,560
dài hơn này.

418
00:19:33,560 --> 00:19:36,570
>> Vì vậy, nếu chúng ta xem xét chỉ
phân loại và tìm kiếm các ví dụ?

419
00:19:36,570 --> 00:19:40,450
Những gì về Mike Smith trong điện thoại
cuốn sách, hoặc tìm kiếm nhị phân thường nhiều hơn?

420
00:19:40,450 --> 00:19:42,220
Trong trường hợp tốt nhất, những gì có thể xảy ra?

421
00:19:42,220 --> 00:19:45,577
Tôi mở cuốn sách điện thoại và, bam,
có số lượng Mike Smith.

422
00:19:45,577 --> 00:19:46,660
Tôi có thể gọi anh ta ngay lập tức.

423
00:19:46,660 --> 00:19:49,390
>> Bước một bước, có lẽ hai bước,
nhưng một số liên tục của bước

424
00:19:49,390 --> 00:19:50,230
nếu tôi có may mắn.

425
00:19:50,230 --> 00:19:52,570
Và thẳng thắn mà nói, chúng ta đã thấy trên
Thứ hai bạn cùng lớp của bạn

426
00:19:52,570 --> 00:19:54,710
nhận được khá may mắn hai lần liên tiếp.

427
00:19:54,710 --> 00:19:57,050
Và đó là thực sự liên tục
thời gian trong một giới hạn thấp hơn

428
00:19:57,050 --> 00:20:01,280
vào các thuật toán trong câu hỏi cho việc tìm kiếm
số 50 đằng sau những đóng

429
00:20:01,280 --> 00:20:01,830
cửa ra vào.

430
00:20:01,830 --> 00:20:06,400
>> Bây giờ, khi một sang một bên, nếu bạn phát hiện ra
rằng cả hai O lớn, các ràng buộc trên,

431
00:20:06,400 --> 00:20:09,310
và omega, thấp hơn bị ràng buộc,
là một trong cùng, đó

432
00:20:09,310 --> 00:20:11,830
là cùng một công thức trong
ngoặc đơn, bạn cũng có thể

433
00:20:11,830 --> 00:20:15,170
nói, chỉ được ưa thích,
cái gì đó là trong theta

434
00:20:15,170 --> 00:20:18,270
n hoặc theta của một số giá trị khác.

435
00:20:18,270 --> 00:20:20,661
Điều đó chỉ có nghĩa là khi lớn
O và omega đều giống nhau.

436
00:20:20,661 --> 00:20:21,910
Bây giờ những gì về việc lựa chọn loại?

437
00:20:21,910 --> 00:20:23,400
Hãy sử dụng từ vựng mới này.

438
00:20:23,400 --> 00:20:27,407
Trong việc lựa chọn loại, là những gì chúng tôi
làm một lần nữa, và một lần nữa, và một lần nữa?

439
00:20:27,407 --> 00:20:29,990
Tôi đã trở lại và ra thông qua
danh sách, tìm kiếm ai?

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
Số lượng nhỏ nhất.

442
00:20:34,730 --> 00:20:37,560
>> Vì vậy, có bao nhiêu bước, làm thế nào
nhiều sự so sánh đã làm tôi

443
00:20:37,560 --> 00:20:43,250
phải thực hiện để tìm ra người
phần tử nhỏ nhất trong danh sách là?

444
00:20:43,250 --> 00:20:44,437
n trừ đi 1, phải không?

445
00:20:44,437 --> 00:20:47,770
Bởi vì nếu tôi chỉ cần bắt đầu với một trong những tôi
đưa ra và tôi bắt đầu so sánh anh ta hoặc cô,

446
00:20:47,770 --> 00:20:49,519
sau đó anh ta hoặc cô ấy, anh ấy
mình, anh ta hoặc cô ấy, tôi

447
00:20:49,519 --> 00:20:52,010
chỉ có thể ghép các yếu tố
cùng n trừ đi 1 lần.

448
00:20:52,010 --> 00:20:55,630
Vì vậy, lựa chọn có loại tương tự
n trừ đi 1 bước lần đầu tiên.

449
00:20:55,630 --> 00:20:59,540
>> Có bao nhiêu bước nó đưa tôi đến
tìm các phần tử nhỏ nhất thứ hai?

450
00:20:59,540 --> 00:21:02,920
n trừ đi 2, bởi vì tôi bị câm
nếu tôi cứ nhìn những người cùng

451
00:21:02,920 --> 00:21:06,280
một lần nữa nếu tôi đã chọn anh
mình và đặt chúng ở vị trí của họ.

452
00:21:06,280 --> 00:21:09,270
Và bước thứ ba, n
trừ đi 3, sau đó n trừ đi 4.

453
00:21:09,270 --> 00:21:11,020
Chúng tôi đã nhìn thấy mô hình này
trước, và thực sự

454
00:21:11,020 --> 00:21:13,460
lựa chọn loại tương tự
có một trên ràng buộc

455
00:21:13,460 --> 00:21:16,210
n bình nếu chúng ta làm tăng tổng kết đó.

456
00:21:16,210 --> 00:21:19,790
Ràng buộc thấp hơn, lựa chọn phân loại của nó là gì?

457
00:21:19,790 --> 00:21:25,350
Tối thiểu, bao nhiêu thời gian lựa chọn phải
loại có, như chúng ta định nghĩa nó vào thứ hai?

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
Đề xuất hai lựa chọn.

460
00:21:30,490 --> 00:21:32,360
Có lẽ đó là n, như trước đây.

461
00:21:32,360 --> 00:21:35,040
Có thể nó n bình phương, vì nó
giờ là như ranh giới trên.

462
00:21:35,040 --> 00:21:35,874
>> TƯỢNG: n bình phương.

463
00:21:35,874 --> 00:21:36,664
SPEAKER: n bình phương.

464
00:21:36,664 --> 00:21:37,368
Tại sao?

465
00:21:37,368 --> 00:21:40,060
>> TƯỢNG: Bởi vì bạn có
để xác định [không nghe được].

466
00:21:40,060 --> 00:21:41,510
>> SPEAKER: Chính xác.

467
00:21:41,510 --> 00:21:45,077
Ít nhất là tôi đã xác định lựa chọn loại
nó đã được khá ngây thơ, tiếp tục đi,

468
00:21:45,077 --> 00:21:46,160
tìm các phần tử nhỏ nhất.

469
00:21:46,160 --> 00:21:47,770
Tới một lần nữa, tìm các phần tử nhỏ nhất.

470
00:21:47,770 --> 00:21:49,490
Tới một lần nữa, tìm các phần tử nhỏ nhất.

471
00:21:49,490 --> 00:21:51,700
Không có loại
tối ưu hóa trong đó mà

472
00:21:51,700 --> 00:21:54,350
có thể cho tôi sau khi hủy bỏ
chỉ n, hay như vậy bước.

473
00:21:54,350 --> 00:21:57,080
Vì vậy, trên thực tế, lựa chọn
sắp xếp, omega n bình phương.

474
00:21:57,080 --> 00:22:00,667
>> Những gì về sắp xếp chèn, nơi mà tôi đã
người mà tôi đã được đưa ra, và sau đó tôi ngồi phịch anh

475
00:22:00,667 --> 00:22:01,750
mình vào đúng chỗ?

476
00:22:01,750 --> 00:22:04,958
Sau đó, tôi tiếp tục đến người thứ hai,
ngồi phịch người đó ở đúng nơi.

477
00:22:04,958 --> 00:22:07,910
Sau đó, người kế tiếp, ngồi phịch
anh ta hoặc cô ở đúng nơi.

478
00:22:07,910 --> 00:22:10,537
Chú ý rằng điều này là rất
tuyến tính, vậy để nói chuyện.

479
00:22:10,537 --> 00:22:12,620
Tôi là một đường thẳng, tôi
không đi lại,

480
00:22:12,620 --> 00:22:16,080
Tôi chưa bao giờ nhìn lại thực sự, nhưng
những gì đang xảy ra khi tôi chèn ông

481
00:22:16,080 --> 00:22:20,302
mình vào đầu
danh sách như chúng tôi đã làm vào thứ hai?

482
00:22:20,302 --> 00:22:21,010
Điều gì đang xảy ra?

483
00:22:21,010 --> 00:22:21,510
Vâng?

484
00:22:21,510 --> 00:22:23,122
TƯỢNG: [không nghe được].

485
00:22:23,122 --> 00:22:24,830
SPEAKER: Vâng, đó
là đánh bắt, phải không?

486
00:22:24,830 --> 00:22:26,746
Bạn có thể nhớ lại từ
bạn cùng lớp của bạn, nếu họ

487
00:22:26,746 --> 00:22:29,670
được thực hiện bất kỳ chuyển động với
đôi chân của mình, đó là một hoạt động.

488
00:22:29,670 --> 00:22:33,610
Vì vậy, nếu ba người dân ở đây đó và
người mới áp đảo thuộc về cách qua đó,

489
00:22:33,610 --> 00:22:37,360
vào một giai đoạn dài như thế này, chắc chắn, ông
hay cô chỉ có thể đi đến cuối cùng.

490
00:22:37,360 --> 00:22:40,074
Nhưng nếu chúng ta đang suy nghĩ về một
máy tính và một mảng của bộ nhớ,

491
00:22:40,074 --> 00:22:41,990
những người này sẽ
phải xáo trộn trên

492
00:22:41,990 --> 00:22:43,260
để nhường chỗ cho người đó.

493
00:22:43,260 --> 00:22:46,930
Và đó n trừ đi 1 shufflings,
n trừ đi 2 shufflings, n

494
00:22:46,930 --> 00:22:50,660
trừ 3 shufflings chỉ là loại
xảy ra đằng sau tôi, không phải trước mặt tôi

495
00:22:50,660 --> 00:22:52,710
như trước đây, trong một ý nghĩa.

499
00:22:52,557 --> 00:22:54,640
Bây giờ là một sang một bên, và như
bạn có thể đã nhìn thấy trực tuyến

500
00:22:54,640 --> 00:22:57,699
nếu bạn bắt đầu chĩa ra xung quanh về
các loại, có rất nhiều những người khác nhau

501
00:22:57,699 --> 00:22:59,490
trên mạng, một số trong số họ
tốt hơn so với những người khác.

502
00:22:59,490 --> 00:23:02,200
Thật vậy, bogosort là một
đó là loại thú vị để tìm kiếm.

503
00:23:02,200 --> 00:23:06,650
Bogosort có một tập hợp các
số hoặc nói một cỗ bài,

504
00:23:06,650 --> 00:23:09,870
lê bước ngẫu nhiên họ, và
kiểm tra nếu họ đang sắp xếp.

505
00:23:09,870 --> 00:23:12,130
Và nếu không, hiện nó một lần nữa.

506
00:23:12,130 --> 00:23:14,140
Và nếu không, hiện nó một lần nữa.

507
00:23:14,140 --> 00:23:15,440
Nếu không, hiện nó một lần nữa.

508
00:23:15,440 --> 00:23:17,060
Cực kỳ ngu ngốc.

509
00:23:17,060 --> 00:23:19,520
>> Và quả thực, nếu bạn đọc
như bài viết Wikipedia,

510
00:23:19,520 --> 00:23:21,200
biệt danh của nó là loại ngu ngốc.

511
00:23:21,200 --> 00:23:25,180
Nó cuối cùng sẽ làm việc,
hy vọng, có đủ thời gian,

512
00:23:25,180 --> 00:23:28,240
nhưng số lượng thời gian
có thể mất một thời gian khá lâu.

513
00:23:28,240 --> 00:23:31,650
Vì vậy, điều tốc độ nếu tôi có thể, chúng ta hãy
từ ví dụ của Mary Beth trước đó,

514
00:23:31,650 --> 00:23:35,150
bởi có một vài yếu tố khác,
nhưng hai bộ xử lý hơn.

515
00:23:35,150 --> 00:23:37,100
Hai con người, nếu bạn
sẽ không nhớ tôi tham gia.

516
00:23:37,100 --> 00:23:40,972
Làm thế nào về 1 trên đây, và
hãy go-- không có ai ở đó không?

517
00:23:40,972 --> 00:23:41,722
Không ai ở đó không?

518
00:23:41,722 --> 00:23:42,221
OK.

519
00:23:42,221 --> 00:23:44,190
Bạn với màu đen
áo sơ mi, có, đi trên xuống.

520
00:23:44,190 --> 00:23:45,000
Được rồi, tên của bạn là gì?

521
00:23:45,000 --> 00:23:45,720
>> TƯỢNG: Peter.

522
00:23:45,720 --> 00:23:46,100
>> SPEAKER: Cái gì thế?

523
00:23:46,100 --> 00:23:46,766
>> TƯỢNG: Peter.

524
00:23:46,766 --> 00:23:49,450
SPEAKER: Peter, David, rất vui được gặp bạn.

525
00:23:49,450 --> 00:23:53,670
Được rồi, chúng ta có Peter ở đây, nếu bạn
muốn đi lên bàn ở đây.

526
00:23:53,670 --> 00:23:54,550
Và tên của bạn là gì?

527
00:23:54,550 --> 00:23:55,216
>> TƯỢNG: Elena.

528
00:23:55,216 --> 00:23:55,970
SPEAKER: Elena.

529
00:23:55,970 --> 00:23:57,030
OK, rất vui được gặp bạn.

530
00:23:57,030 --> 00:23:58,060
Elena gặp Peter.

531
00:23:58,060 --> 00:23:59,170
Peter, Elena.

532
00:23:59,170 --> 00:24:02,290
Và chúng ta sẽ cần Andrew
ở đây là tốt, xin vui lòng.

533
00:24:02,290 --> 00:24:06,107
Và thách thức của bạn sẽ
là để sắp xếp một bộ bài.

534
00:24:06,107 --> 00:24:08,190
Và nếu không quen thuộc, boong
thẻ nên cuối cùng

535
00:24:08,190 --> 00:24:11,064
được sắp xếp một chút gì đó giống như
này, nơi chúng tôi sẽ làm các câu lạc bộ, sau đó

536
00:24:11,064 --> 00:24:13,660
các mai, sau đó trái tim và
kim cương, từ ace như một,

537
00:24:13,660 --> 00:24:15,570
tất cả các con đường lên cho nhà vua.

538
00:24:15,570 --> 00:24:20,890
>> Các thẻ tôi sẽ cung cấp cho bạn
đang có được 52 trong số lượng.

539
00:24:20,890 --> 00:24:23,160
Chúng ta sẽ tương tự
Hiện bạn, chỉ trong một thời điểm.

540
00:24:23,160 --> 00:24:26,410
Chúng ta sẽ ném Andrew
lên trên màn hình ở đây,

541
00:24:26,410 --> 00:24:28,170
để xem như là bạn làm điều này.

542
00:24:28,170 --> 00:24:31,070
Và đó là tất cả điều này
là tất cả các rõ ràng hơn,

543
00:24:31,070 --> 00:24:33,490
đó là những thẻ tôi đã nhận trên Amazon.

544
00:24:33,490 --> 00:24:42,861
Vì vậy, họ đã ngẫu nhiên
sắp xếp, và chúng ta sẽ để thời gian bạn.

545
00:24:42,861 --> 00:24:44,610
Và chúng ta sẽ
giữ nó thực sự thời gian này,

546
00:24:44,610 --> 00:24:47,820
vì vậy chúng tôi sẽ cố gắng để áp lực cho bạn
bởi vì nếu không điều này sẽ giúp tẻ nhạt

547
00:24:47,820 --> 00:24:48,460
một cách nhanh chóng.

548
00:24:48,460 --> 00:24:53,860
Nếu bạn có thể tiến hành để sắp xếp 52
các yếu tố với nhau thông qua một số phương tiện, bây giờ.

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> Và một lần nữa, như chúng ta xem những
kẻ làm những gì, cuối cùng

551
00:25:07,180 --> 00:25:10,200
sẽ tạo ra một rõ ràng
Kết quả, suy nghĩ về thực sự

552
00:25:10,200 --> 00:25:12,962
làm thế nào họ đang từng làm việc đó,
làm thế nào bạn có thể mô tả nó.

553
00:25:12,962 --> 00:25:15,045
Bởi vì một lần nữa, đây là những
tất cả các quá trình, các thuật toán

554
00:25:15,045 --> 00:25:17,090
mà chúng tôi đưa cho các cấp như một con người.

555
00:25:17,090 --> 00:25:22,349
Tuy nhiên, bạn đã có thể lâu đã
trực giác, rất lâu trước khi bạn thậm chí

556
00:25:22,349 --> 00:25:24,390
nghĩ về việc tham gia một
khoa học máy tính lớp bạn

557
00:25:24,390 --> 00:25:27,223
có thể có trực giác với
để giải quyết vấn đề như thế này.

558
00:25:27,223 --> 00:25:29,560
Nhưng một khi bạn nhận ra
các mô hình và bắt đầu

559
00:25:29,560 --> 00:25:32,407
để chính thức hóa các bước mà
bạn đang giải quyết những vấn đề này,

560
00:25:32,407 --> 00:25:35,490
bạn sẽ thấy rằng bạn có thể giải quyết nhiều
thú vị hơn và phức tạp hơn nhiều

561
00:25:35,490 --> 00:25:39,190
vấn đề một cách nhanh chóng.

562
00:25:39,190 --> 00:25:42,351
Vì vậy, một người nào đó từ phía khán giả, là những gì
ít nhất một phần tử của thuật toán

563
00:25:42,351 --> 00:25:43,350
rằng họ đang sử dụng ở đây?

564
00:25:43,350 --> 00:25:44,275
>> TƯỢNG: [không nghe được]

565
00:25:44,275 --> 00:25:45,150
SPEAKER: Cái gì thế?

566
00:25:45,150 --> 00:25:47,062
TƯỢNG: Bằng cách phù hợp.

567
00:25:47,062 --> 00:25:47,770
SPEAKER: Bằng cách phù hợp.

568
00:25:47,770 --> 00:25:50,630
Vì vậy, đầu tiên họ được phân nhóm
tất cả các viên kim cương cùng

569
00:25:50,630 --> 00:25:52,560
có vẻ như, tất cả các
trái tim lại với nhau có vẻ như,

570
00:25:52,560 --> 00:25:56,520
và vv, mà không có sự tôn trọng
cho những con số trên thẻ.

571
00:25:56,520 --> 00:26:00,900
Và bây giờ chúng xuất hiện, ví dụ,
được phân loại chúng theo số lượng.

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
Rất tốt.

574
00:26:08,910 --> 00:26:12,370
>> Được rồi, vậy điều gì sẽ
là bước cuối cùng sau đó ở đây?

575
00:26:12,370 --> 00:26:16,950
Khi chúng ta có bốn bộ quần áo được sắp xếp, những gì
chúng ta cần phải làm gì để bốn cọc

576
00:26:16,950 --> 00:26:20,059
để đạt được một
sắp xếp tầng, khá đơn giản?

577
00:26:20,059 --> 00:26:21,350
Vì vậy, chúng ta cần phải hợp nhất chúng lại một lần nữa.

578
00:26:21,350 --> 00:26:25,160
>> Vì vậy, có một ý tưởng thú vị mà
một lần nữa, dám nói, thậm chí là rất trực quan

579
00:26:25,160 --> 00:26:28,140
nếu bạn không bao giờ có thể đã tát
là loại nhãn trên đó.

580
00:26:28,140 --> 00:26:31,900
Điều này khái niệm cơ bản của phân chia
vấn đề không phải trong một nửa thời gian này,

581
00:26:31,900 --> 00:26:33,410
nhưng ít nhất thành bốn miếng.

582
00:26:33,410 --> 00:26:36,810
Giải quyết khá nhiều
vấn đề cơ bản giống hệt nhau

583
00:26:36,810 --> 00:26:40,480
trong sự cô lập của nhau,
và sau đó kết hợp các kết quả.

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
Và, tuyệt vời, thực hiện.

586
00:26:50,140 --> 00:26:52,140
Được rồi, một vòng lớn
vỗ tay, nếu chúng ta có thể.

587
00:26:52,140 --> 00:26:56,480
>> [Vỗ tay]

588
00:26:56,480 --> 00:26:59,740
>> SPEAKER: Tôi không có ý tưởng những gì bạn sẽ thấy
làm với này, nhưng ở đây bạn đi.

589
00:26:59,740 --> 00:27:01,690
Cảm ơn bạn rất nhiều.

590
00:27:01,690 --> 00:27:04,660
Vì vậy, chúng ta hãy xem, hai phút
và tám giây,

591
00:27:04,660 --> 00:27:07,490
nếu bạn muốn thách thức bạn bè của bạn.

592
00:27:07,490 --> 00:27:12,160
Điều gì sau đó sẽ
là một lấy đi từ này

593
00:27:12,160 --> 00:27:13,830
chúng ta có thể tận dụng nói chung?

594
00:27:13,830 --> 00:27:16,080
Vâng, nghĩ lại
mảng này các con số,

595
00:27:16,080 --> 00:27:19,060
và bây giờ nghĩ lại cho một số các
giả chúng tôi đã viết trong quá khứ,

596
00:27:19,060 --> 00:27:22,080
và đây là giả cho
giải quyết vấn đề danh bạ điện thoại.

597
00:27:22,080 --> 00:27:25,150
Nhờ đó mà trong giả tôi
liệt kê một cách có phương pháp hơn

598
00:27:25,150 --> 00:27:28,400
mô tả làm thế nào tôi đã làm một rất trực quan
Thuật toán nhân chia điện thoại

599
00:27:28,400 --> 00:27:31,650
cuốn sách trong một nửa, lặp lại, lặp lại, lặp lại,
cho đến khi tôi tìm thấy một người như Mike Smith,

600
00:27:31,650 --> 00:27:33,790
nếu anh ta thực sự là trong sổ điện thoại.

601
00:27:33,790 --> 00:27:37,610
>> Nhưng tôi loại sử dụng những gì tôi sẽ gọi
một cách tiếp cận rất lặp đi lặp lại ở đây,

602
00:27:37,610 --> 00:27:42,160
trong thông báo cụ thể đường 8 và đường 11.

603
00:27:42,160 --> 00:27:46,750
Đó là những bằng chứng cho thấy lặp đi lặp lại
cách tiếp cận, một cách tiếp cận vòng lặp,

604
00:27:46,750 --> 00:27:49,040
bởi vì đó là chính xác
hành vi mà họ gây ra.

605
00:27:49,040 --> 00:27:52,910
Những dòng đều nói đi
loại ba dòng, và bạn có thể của

606
00:27:52,910 --> 00:27:55,140
nghĩ về điều đó trong bạn
mắt của tâm trí như là một vòng lặp.

607
00:27:55,140 --> 00:27:59,080
Nó nói cho bạn để quay trở lại bước
ba và lặp lại, một lần nữa, và một lần nữa,

608
00:27:59,080 --> 00:28:00,010
và một lần nữa.

609
00:28:00,010 --> 00:28:04,410
>> Nhưng nếu chúng ta tận dụng một ý tưởng quan trọng
ở đây là chúng tôi đã làm không phải là lần cuối cùng,

610
00:28:04,410 --> 00:28:10,280
và đơn giản hóa dòng 8 và
dòng 11 và hàng xóm

611
00:28:10,280 --> 00:28:12,840
như chỉ này, màu vàng.

612
00:28:12,840 --> 00:28:16,480
Đó là về cơ bản không rút ngắn
mã giả rất nhiều,

613
00:28:16,480 --> 00:28:20,530
nhưng nó thay đổi căn bản
bản chất của thuật toán của tôi.

614
00:28:20,530 --> 00:28:24,220
Những gì chúng ta đang nói
trong bước 7, trong bước 10,

615
00:28:24,220 --> 00:28:29,140
là để tìm kiếm Mike
trong một cách chính xác,

616
00:28:29,140 --> 00:28:31,580
nhưng chỉ ở bên trái
một nửa hoặc nửa bên phải.

617
00:28:31,580 --> 00:28:33,420
>> Vì vậy, nói cách khác, nếu
Tôi bắt đầu từ bước một,

618
00:28:33,420 --> 00:28:36,150
nhận cuốn sách điện thoại, mở cửa cho trung
danh bạ điện thoại, nhìn vào tên,

619
00:28:36,150 --> 00:28:39,010
nếu Smith là một trong những
tên, gọi Mike, khác

620
00:28:39,010 --> 00:28:44,340
Smith là nếu trước đó trong cuốn sách, bước bảy
tìm kiếm Mike ở nửa bên trái của cuốn sách.

621
00:28:44,340 --> 00:28:47,130
Tuy nhiên, các cảm giác như
nó để lại cho tôi treo, phải không?

622
00:28:47,130 --> 00:28:49,240
Màu vàng, là một
hướng dẫn, nhưng làm cách nào để

623
00:28:49,240 --> 00:28:51,870
tìm kiếm Mike ở bên trái
một nửa số danh bạ điện thoại?

624
00:28:51,870 --> 00:28:54,210
Tôi có một nơi
thuật toán mà tôi

625
00:28:54,210 --> 00:28:57,100
có thể tìm kiếm một người như Mike Smith?

626
00:28:57,100 --> 00:28:58,980
Vâng, nó nhìn chằm chằm chúng tôi trong khuôn mặt.

627
00:28:58,980 --> 00:29:03,090
Tôi nghĩa là có thể sử dụng chính xác cùng
chương trình có hiệu quả sẽ lên đến đỉnh

628
00:29:03,090 --> 00:29:06,490
một lần nữa và lại chạy
cùng một dòng mã.

629
00:29:06,490 --> 00:29:10,610
>> Vì vậy, mặc dù điều này nên cảm thấy
giống như một chút của một định nghĩa mang tính chu kỳ

630
00:29:10,610 --> 00:29:13,480
nơi bạn đang trả lời một ai đó
câu hỏi bằng cách chỉ là loại yêu cầu

631
00:29:13,480 --> 00:29:15,990
cùng một câu hỏi một lần nữa,
như lý do tại sao, tại sao, tại sao?

632
00:29:15,990 --> 00:29:21,580
Thực tế là bởi vì chúng tôi đã cứng mã hoá
một vài dòng đặc biệt, bước 4,

633
00:29:21,580 --> 00:29:25,320
mà là một nếu, và bước 12,
là có hiệu quả một chi nhánh,

634
00:29:25,320 --> 00:29:30,120
bởi vì chúng tôi có những biện pháp lấp chỗ trống,
thuật toán này sẽ chấm dứt nếu chúng ta

635
00:29:30,120 --> 00:29:32,050
Mike tìm thấy, hoặc nếu chúng ta không.

636
00:29:32,050 --> 00:29:36,810
Nhưng trong bước 7 và 10 giờ, chúng tôi có
những gì chúng tôi sẽ gọi một thuật toán đệ quy.

637
00:29:36,810 --> 00:29:40,420
Và đệ quy thực sự là một ý tưởng mạnh mẽ
đó là một chút tâm uốn lúc đầu,

638
00:29:40,420 --> 00:29:42,500
mà bây giờ chúng ta có thể áp dụng như sau.

639
00:29:42,500 --> 00:29:46,600
>> Kết hợp các loại sẽ là loại cuối cùng mà
chúng ta nhìn vào, ít nhất là trong các lớp học chính thức.

640
00:29:46,600 --> 00:29:50,040
Và đó là cơ bản khác nhau
từ những người cuối cùng ba, và chắc chắn

641
00:29:50,040 --> 00:29:52,140
cuối cùng bốn nếu chúng tôi bao gồm bogosort.

642
00:29:52,140 --> 00:29:54,810
Đây là giả cho sắp xếp hợp nhất.

643
00:29:54,810 --> 00:30:00,170
Khi vào đầu vào của n phần tử, vì vậy được
một mảng có kích thước n, nếu n là ít hơn 2,

644
00:30:00,170 --> 00:30:01,040
trở lại.

645
00:30:01,040 --> 00:30:03,610
Vì vậy, tại sao tôi có mà
sự tỉnh táo kiểm tra đầu tiên?

646
00:30:03,610 --> 00:30:09,477
Ngụ ý gì nếu tôi đưa cho bạn
một mảng có n chiều dài là ít hơn 2?

647
00:30:09,477 --> 00:30:11,060
Nó đã được sắp xếp, rõ ràng, đúng không?

648
00:30:11,060 --> 00:30:13,640
Bởi vì danh sách hoặc có
một yếu tố, đó là tầm thường

649
00:30:13,640 --> 00:30:15,180
sắp xếp bởi vì nó
điều duy nhất đó.

650
00:30:15,180 --> 00:30:18,138
Hoặc, nó có kích thước bằng không có nghĩa là
không có gì để sắp xếp là, do bản chất

651
00:30:18,138 --> 00:30:18,720
nó được sắp xếp.

652
00:30:18,720 --> 00:30:20,410
Không chỉ là không có gì sai trái đó.

653
00:30:20,410 --> 00:30:22,310
Vì vậy, đó là cái gọi là trường hợp cơ sở của chúng tôi.

654
00:30:22,310 --> 00:30:24,440
>> Đó là tinh thần tương tự
những gì chúng ta đã làm với Mike.

655
00:30:24,440 --> 00:30:26,023
Nếu Mike trong sổ điện thoại, gọi anh ta.

656
00:30:26,023 --> 00:30:27,740
Nếu anh ta không có ở đó, bỏ cuộc.

657
00:30:27,740 --> 00:30:31,240
Đó là một trường hợp cơ sở cái gọi là, để đảm bảo
thuật toán này vào cuối ngày

658
00:30:31,240 --> 00:30:33,540
sẽ chấm dứt trong những trường hợp nhất định.

659
00:30:33,540 --> 00:30:37,890
>> Nhưng đây là bước nhảy vọt của đức tin bây giờ, khác,
sắp xếp nửa trái của các yếu tố,

660
00:30:37,890 --> 00:30:39,740
sau đó sắp xếp bên phải
một nửa trong số các yếu tố,

661
00:30:39,740 --> 00:30:41,189
và sau đó hợp nhất hai nửa được sắp xếp.

662
00:30:41,189 --> 00:30:43,230
Và đây là nơi mà nó cảm thấy
như chúng ta đang Copping ra.

663
00:30:43,230 --> 00:30:46,900
Tôi đã hỏi bạn sắp xếp
n yếu tố, và tôi

664
00:30:46,900 --> 00:30:50,712
nói, OK, làm điều đó bằng cách phân loại
bên trái và phân loại bên phải.

665
00:30:50,712 --> 00:30:52,420
Nhưng tôi nói một
điều khác, và điều này

666
00:30:52,420 --> 00:30:55,530
là chủ đề quan trọng có vẻ như
trong trực giác vậy, đến nay,

667
00:30:55,530 --> 00:30:57,380
có bước thứ ba này hợp nhất.

668
00:30:57,380 --> 00:31:00,430
Mà mặc dù nó
có vẻ rất ngớ ngẩn trong tinh thần,

669
00:31:00,430 --> 00:31:02,320
như chỉ hợp điều
với nhau, có vẻ như

670
00:31:02,320 --> 00:31:05,380
là một bước quan trọng hướng tới
tái gộp hai vấn đề mà

671
00:31:05,380 --> 00:31:07,330
cuối cùng được chia một nửa.

672
00:31:07,330 --> 00:31:12,090
>> Vì vậy, hợp nhất phân loại, chúng ta hãy làm điều này, nếu bạn sẽ
hài hước tôi, với một cuộc biểu tình nhiều,

673
00:31:12,090 --> 00:31:14,730
chỉ để chúng tôi có một số
số điện thoại để làm việc với.

674
00:31:14,730 --> 00:31:19,470
Tôi có thể trao đổi tám căng thẳng
quả bóng cho tám người?

675
00:31:19,470 --> 00:31:29,320
Được rồi, làm thế nào về bạn ba, bốn bạn
trong phần này, năm, sáu, và chúng ta hãy

676
00:31:29,320 --> 00:31:30,720
làm 7, 8, đến ngày lên.

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
OK, yeah OK.

679
00:31:36,520 --> 00:31:38,640
Trừ đi 8, có chúng tôi đi, cộng với 1.

680
00:31:38,640 --> 00:31:39,150
Tuyệt vời.

681
00:31:39,150 --> 00:31:42,000
Rồi đến ngày lên, chúng ta hãy
nhanh chóng cung cấp cho bạn số điện thoại.

682
00:31:42,000 --> 00:31:50,800
Thứ hai, thứ ba, thứ tư,
thứ năm, sáu, bảy, tám người.

683
00:31:50,800 --> 00:31:52,140
Tôi đã làm tám một cách chính xác thời gian này.

684
00:31:52,140 --> 00:31:56,390
>> OK, nên đi trước nếu bạn có thể, và
chúng ta hãy sắp xếp theo thứ tự ban đầu

685
00:31:56,390 --> 00:31:59,810
rằng chúng tôi đã có ngày hôm qua mà nhìn
như thế này, nếu bạn không quan tâm.

686
00:31:59,810 --> 00:32:03,620
Và chúng ta hãy làm điều đó trước mặt bàn.

687
00:32:03,620 --> 00:32:06,510
Được rồi, để hợp nhất phân loại.

688
00:32:06,510 --> 00:32:08,820
Đây là nơi mà nó sẽ
để có được loại thú vị,

689
00:32:08,820 --> 00:32:12,800
bởi vì tôi dường như được cho bản thân mình
quá nhiều ngày nay ít thông tin.

690
00:32:12,800 --> 00:32:15,149
>> Vì vậy, hợp nhất phân loại đầu tiên của tất cả các
trên đầu vào của các yếu tố n,

691
00:32:15,149 --> 00:32:18,440
và rõ ràng là không ít hơn hai, đó là
tám, vì vậy tôi có một số công việc nhiều hơn để làm.

692
00:32:18,440 --> 00:32:21,140
Vì vậy, bây giờ tinh thần chúng tôi như là một lớp
hiện nay trong ngành khác,

693
00:32:21,140 --> 00:32:22,540
có nghĩa là ba bước.

694
00:32:22,540 --> 00:32:25,017
Trước tiên, tôi phải sắp xếp các
nửa bên trái của các yếu tố.

695
00:32:25,017 --> 00:32:26,350
Vì vậy, làm thế nào để đi về việc này?

696
00:32:26,350 --> 00:32:28,950
Vâng, tôi sẽ loại
tinh thần chia danh sách ở đây,

697
00:32:28,950 --> 00:32:30,700
bạn không cần phải
thể chất di chuyển, và tôi

698
00:32:30,700 --> 00:32:33,180
sẽ chỉ tập trung vào
nửa bên trái của các yếu tố ở đây.

699
00:32:33,180 --> 00:32:36,770
Vậy làm thế nào để tôi đi về phân loại
một danh sách hiện nay có kích thước bốn?

700
00:32:36,770 --> 00:32:38,730
Thuật toán của tôi là gì?

701
00:32:38,730 --> 00:32:42,580
Lần đầu tiên tôi kiểm tra là n ít hơn hai, không,
vì vậy tôi tiến hành các khối khác nữa.

702
00:32:42,580 --> 00:32:43,900
Sắp xếp lại một nửa số yếu tố.

703
00:32:43,900 --> 00:32:45,608
>> Vì vậy, bây giờ một lần nữa, tinh thần,
và đây là nơi

704
00:32:45,608 --> 00:32:49,550
bạn phải tích lũy rất nhiều
lịch sử tâm thần, nếu bạn sẽ.

705
00:32:49,550 --> 00:32:51,940
Bây giờ tôi đang sắp xếp bên trái
một nửa của một nửa trái.

706
00:32:51,940 --> 00:32:57,000
Được rồi, vì vậy bây giờ tôi gọi cùng hợp nhất của tôi
thuật toán phân loại, được n ít hơn hai?

707
00:32:57,000 --> 00:33:00,590
Không, nó là hai, vì vậy tôi phải sắp xếp
nửa bên trái và nửa bên phải.

708
00:33:00,590 --> 00:33:02,042
Vì vậy, ở đây chúng tôi đi, sắp xếp các nửa trái.

709
00:33:02,042 --> 00:33:03,750
Tại sao bạn không chỉ
đi trước một bước.

710
00:33:03,750 --> 00:33:04,415
Tên của bạn là gì?

711
00:33:04,415 --> 00:33:04,860
>> TƯỢNG: Darren.

712
00:33:04,860 --> 00:33:05,260
>> SPEAKER: Dan.

713
00:33:05,260 --> 00:33:06,040
Dan đã bước về phía trước.

714
00:33:06,040 --> 00:33:06,748
>> TƯỢNG: Darren.

715
00:33:06,748 --> 00:33:09,000
SPEAKER: Darren, thực hiện.

716
00:33:09,000 --> 00:33:10,090
Bạn đã nói Darren hoặc Dan?

717
00:33:10,090 --> 00:33:10,550
>> TƯỢNG: Darren.

718
00:33:10,550 --> 00:33:11,216
>> SPEAKER: Darren.

719
00:33:11,216 --> 00:33:14,422
OK, Darren đã tăng cường
về phía trước và bây giờ anh đã được sắp xếp.

720
00:33:14,422 --> 00:33:16,130
Và điều này gần như là một
tuyên bố ngớ ngẩn, phải không?

721
00:33:16,130 --> 00:33:18,862
Tôi không thực sự dường như đạt được
bất cứ điều gì, nhưng chúng ta hãy tiến hành.

722
00:33:18,862 --> 00:33:20,820
Bây giờ hãy để tôi sắp xếp bên phải
một nửa trong số các yếu tố.

723
00:33:20,820 --> 00:33:21,200
Tên của bạn là gì?

724
00:33:21,200 --> 00:33:21,690
>> TƯỢNG: Luke.

725
00:33:21,690 --> 00:33:22,273
>> SPEAKER: Luke.

726
00:33:22,273 --> 00:33:23,400
Thôi nào, bước về phía trước.

727
00:33:23,400 --> 00:33:25,640
Thực hiện, tôi đã sắp xếp Luke.

728
00:33:25,640 --> 00:33:28,570
Nửa bên trái bây giờ được sắp xếp và
nửa bên phải bây giờ được sắp xếp,

729
00:33:28,570 --> 00:33:30,770
nhưng một lần nữa, có một bước tiến quan trọng ở đây.

730
00:33:30,770 --> 00:33:32,940
Tôi phải làm gì tiếp theo cần phải làm gì?

731
00:33:32,940 --> 00:33:33,941
Hợp nhất nửa sắp xếp.

732
00:33:33,941 --> 00:33:36,648
Bây giờ chúng ta sẽ chỉ có
tất cả mọi người qua lại theo cách này,

733
00:33:36,648 --> 00:33:38,620
bởi vì tôi cần phải loại
một số không gian đầu.

734
00:33:38,620 --> 00:33:40,411
Nó gần giống như những
kẻ đang ở trên một bảng,

735
00:33:40,411 --> 00:33:42,460
và tôi cần một số phòng
để di chuyển chúng xung quanh trên.

736
00:33:42,460 --> 00:33:44,170
Vì vậy, tôi sẽ hợp nhất
các bạn bằng cách tìm kiếm

737
00:33:44,170 --> 00:33:45,960
ở nửa trái và nửa bên phải.

738
00:33:45,960 --> 00:33:48,740
Và rõ ràng là người đến trước,
nửa trái hoặc nửa phải không?

739
00:33:48,740 --> 00:33:52,710
Vì vậy, nửa bên phải, vì vậy chúng ta hãy chuyển qua Luke
ở đây vị trí ban đầu của Darren.

740
00:33:52,710 --> 00:33:57,640
Và bây giờ kết hợp của họ trong nửa trái,
Darren sẽ di chuyển ngay.

741
00:33:57,640 --> 00:33:59,750
>> Vì vậy, cảm thấy giống như hầu hết
một hiệu ứng bong bóng sắp xếp,

742
00:33:59,750 --> 00:34:02,482
nhưng thuật toán cơ bản của tôi,
rất khác nhau thời gian này.

743
00:34:02,482 --> 00:34:04,815
Nhưng bây giờ là nơi mà mọi thứ có được một
ít gây phiền nhiễu bởi vì bạn

744
00:34:04,815 --> 00:34:06,810
phải tua lại tinh thần
nơi mà tôi không còn.

745
00:34:06,810 --> 00:34:09,893
Tôi vừa mới sáp nhập hai nửa đã được sắp xếp,
có nghĩa là tôi đang ở đâu trong thuật toán của tôi?

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
Tôi phải sắp xếp nửa bên phải, phải không?

748
00:34:13,770 --> 00:34:15,910
>> Nếu bạn quay lại, theo nghĩa đen
trên video, bạn sẽ

749
00:34:15,910 --> 00:34:18,339
thấy rằng chúng tôi đã đến đây
điểm của Luke và Darren

750
00:34:18,339 --> 00:34:21,370
bằng cách phân loại trái
một nửa của một nửa trái.

751
00:34:21,370 --> 00:34:23,430
Sau đó, chúng tôi kết hợp những
nửa sắp xếp, mà

752
00:34:23,430 --> 00:34:27,941
có nghĩa là bước tiếp theo là sắp xếp các
nửa bên phải của một nửa trái.

753
00:34:27,941 --> 00:34:29,649
Được rồi, vậy chúng ta hãy
làm điều này một cách nhanh chóng hơn.

754
00:34:29,649 --> 00:34:33,282
Được rồi, sáu, tôi sẽ yêu cầu bồi thường
bây giờ bạn đều được sắp xếp, đi về phía trước.

755
00:34:33,282 --> 00:34:33,990
Tên của bạn là gì?

756
00:34:33,990 --> 00:34:34,589
>> TƯỢNG: Adriano.

757
00:34:34,589 --> 00:34:35,200
>> SPEAKER: Adriano.

758
00:34:35,200 --> 00:34:36,010
Adriano hiện đang được sắp xếp.

759
00:34:36,010 --> 00:34:36,450
Và tên của bạn là gì?

760
00:34:36,450 --> 00:34:37,080
>> TƯỢNG: Alex.

761
00:34:37,080 --> 00:34:38,379
>> SPEAKER: Alex bây giờ được sắp xếp.

762
00:34:38,379 --> 00:34:40,750
Còn lại một nửa, nửa bên phải,
bước cuối cùng là gì?

763
00:34:40,750 --> 00:34:41,250
Merge.

764
00:34:41,250 --> 00:34:44,310
Khá tầm thường, vì vậy tôi
sẽ hợp nhất trong sáu,

765
00:34:44,310 --> 00:34:46,930
lùi lại một bước,
tám, lùi lại một bước.

766
00:34:46,930 --> 00:34:49,530
Và bây giờ nhận thấy điều này là
một takeaway hữu ích, những gì

767
00:34:49,530 --> 00:34:53,930
bây giờ là sự thật về nửa bên trái của
danh sách, bất kể như thế nào chúng tôi bắt đầu?

768
00:34:53,930 --> 00:34:55,090
Nó được sắp xếp.

769
00:34:55,090 --> 00:34:57,750
>> Bây giờ nó không được sắp xếp trong
các đề án lớn của sự vật,

770
00:34:57,750 --> 00:35:00,250
nhưng nó được sắp xếp một cách độc lập
của nửa kia.

771
00:35:00,250 --> 00:35:04,100
Bây giờ những gì tôi bước vào nếu tôi giữ
tua như thế nào câu chuyện bắt đầu?

772
00:35:04,100 --> 00:35:05,680
Bây giờ tôi phải sắp xếp nửa bên phải.

773
00:35:05,680 --> 00:35:07,630
Vì vậy, bây giờ chúng tôi cách trở lại
đầu của câu chuyện,

774
00:35:07,630 --> 00:35:08,921
và chúng ta hãy làm điều này nhanh hơn.

775
00:35:08,921 --> 00:35:11,320
Vì vậy, tôi sẽ sắp xếp
nửa bên phải của toàn bộ danh sách.

776
00:35:11,320 --> 00:35:13,060
Bước tiếp theo là gì?

777
00:35:13,060 --> 00:35:15,840
Sắp xếp một nửa còn lại của nửa bên phải.

778
00:35:15,840 --> 00:35:18,715
Sắp xếp một nửa bên trái của
nửa bên trái của nửa bên phải.

779
00:35:18,715 --> 00:35:19,590
Và tên của bạn là gì?

780
00:35:19,590 --> 00:35:20,230
>> TƯỢNG: Omar.

781
00:35:20,230 --> 00:35:21,970
>> SPEAKER: Omar, bước về phía trước, thực hiện.

782
00:35:21,970 --> 00:35:22,860
Nửa còn lại được sắp xếp.

783
00:35:22,860 --> 00:35:23,330
Và tên của bạn là gì?

784
00:35:23,330 --> 00:35:23,820
>> TƯỢNG: Chris.

785
00:35:23,820 --> 00:35:25,620
>> SPEAKER: Chris, có một bước
về phía trước, bạn đang sắp xếp.

786
00:35:25,620 --> 00:35:27,010
Các bước quan trọng bây giờ là gì?

787
00:35:27,010 --> 00:35:27,510
Merge.

788
00:35:27,510 --> 00:35:30,509
Vì vậy, một là sẽ hợp nhất vào vị trí
ở đây, nếu bạn có thể lùi lại một bước,

789
00:35:30,509 --> 00:35:32,930
và ba sẽ
lùi lại một bước, sáp nhập.

790
00:35:32,930 --> 00:35:38,080
Vì vậy, nửa bên trái của
nửa bên phải, bây giờ được sắp xếp.

791
00:35:38,080 --> 00:35:41,747
Thành thật mà nói, thuật toán này cảm thấy như chúng tôi
đang lãng phí thời gian cách hơn trước,

792
00:35:41,747 --> 00:35:44,830
nhưng nếu chúng ta đã làm điều này trong thời gian thực, chúng ta sẽ
xem những gì takeaways có được.

793
00:35:44,830 --> 00:35:47,970
Bây giờ tôi ở đây, phải
một nửa nửa bên phải,

794
00:35:47,970 --> 00:35:50,170
hãy để tôi đi trước và sắp xếp nửa trái.

795
00:35:50,170 --> 00:35:51,482
Bước về phía trước, tên của bạn là gì?

796
00:35:51,482 --> 00:35:52,190
TƯỢNG: Ramsey.

797
00:35:52,190 --> 00:35:53,210
SPEAKER: Ramsey hiện đang được sắp xếp.

798
00:35:53,210 --> 00:35:53,570
Tên của bạn là gì?

799
00:35:53,570 --> 00:35:54,200
>> TƯỢNG: Marina.

800
00:35:54,200 --> 00:35:57,033
>> SPEAKER: Marina giờ được sắp xếp như
tốt, nếu bạn đi trước một bước.

801
00:35:57,033 --> 00:36:00,690
Bước quan trọng ở đây là hợp nhất, tôi
sẽ nhổ từ hai danh sách của tôi,

802
00:36:00,690 --> 00:36:01,720
trái và phải.

803
00:36:01,720 --> 00:36:05,150
Năm là sẽ đi đầu tiên,
và bảy là sẽ đi tiếp theo.

804
00:36:05,150 --> 00:36:06,410
Và một lần nữa, điều này là có chủ ý.

805
00:36:06,410 --> 00:36:08,535
Thực tế là họ đang dùng
bước lên phía trước và trở lại

806
00:36:08,535 --> 00:36:12,997
có nghĩa là để bảo đảm rằng chúng ta không thể
làm thuật toán này ở vị trí một cách dễ dàng

807
00:36:12,997 --> 00:36:15,830
như bong bóng sắp xếp, lựa chọn và sắp xếp,
và sắp xếp chèn nơi chúng tôi chỉ

808
00:36:15,830 --> 00:36:16,960
tiếp tục trao đổi người.

809
00:36:16,960 --> 00:36:19,940
Tôi thật sự cần một loại
giấy đầu trong đó

810
00:36:19,940 --> 00:36:21,827
để đưa những người này
trong khi tôi làm việc sáp nhập,

811
00:36:21,827 --> 00:36:23,410
và sau đó tôi có thể đưa chúng trở lại tại chỗ.

812
00:36:23,410 --> 00:36:27,260
Và đó là quan trọng bởi vì tôi đang sử dụng một
tài nguyên mới, không gian, không chỉ là thời gian.

813
00:36:27,260 --> 00:36:28,270
>> OK, điều này là tuyệt vời.

814
00:36:28,270 --> 00:36:32,050
Còn lại một nửa được sắp xếp, nửa bên phải là
sắp xếp, bây giờ mà chính hợp nhất bước.

815
00:36:32,050 --> 00:36:33,450
Làm thế nào tôi sẽ kết hợp này?

816
00:36:33,450 --> 00:36:35,470
Vì vậy, nếu bạn làm theo tôi
tay trái và tay phải,

817
00:36:35,470 --> 00:36:38,930
Tôi sẽ chỉ cho tay trái của tôi
ở nửa bên trái, tay phải của tôi

818
00:36:38,930 --> 00:36:42,680
ở nửa bên phải, và bây giờ tôi phải
quyết định từng bước mà để trộn.

819
00:36:42,680 --> 00:36:44,650
Ai rõ ràng đến trước?

820
00:36:44,650 --> 00:36:45,150
Số một.

821
00:36:45,150 --> 00:36:47,327
Vì vậy, đến trên đây,
đây là pad đầu của chúng tôi.

822
00:36:47,327 --> 00:36:49,910
Vì vậy, bây giờ số một, và thông báo
những gì tôi sẽ làm gì với bàn tay phải của tôi,

823
00:36:49,910 --> 00:36:54,152
Tôi sẽ di chuyển một bàn tay phải của tôi
bước qua chỉ số ba,

824
00:36:54,152 --> 00:36:55,860
và bây giờ tôi phải làm
quyết định tương tự.

825
00:36:55,860 --> 00:36:58,387
Và thực sự đứng ngay
phía trước của Luke ở đây nếu bạn có thể,

826
00:36:58,387 --> 00:36:59,720
bởi vì đây là pad đầu của chúng tôi.

827
00:36:59,720 --> 00:37:00,610
Vì vậy, những người đến tiếp theo?

828
00:37:00,610 --> 00:37:05,000
Chúng tôi có với Luke thứ hai
hoặc với Chris thứ ba.

829
00:37:05,000 --> 00:37:07,460
Rõ ràng là Luke, số
hai, vì vậy bạn đến đây.

830
00:37:07,460 --> 00:37:11,270
>> Nhưng bàn tay trái của tôi bây giờ sẽ
được tăng lên tới điểm Darren,

831
00:37:11,270 --> 00:37:15,160
và đây là chìa khóa lấy đi với
sáp nhập, tôi sẽ tiếp tục làm điều này,

832
00:37:15,160 --> 00:37:17,340
rõ ràng là, nếu bạn loại
của theo logic.

833
00:37:17,340 --> 00:37:19,670
Nhưng bàn tay của tôi là không bao giờ
sẽ đi ngược trở lại,

834
00:37:19,670 --> 00:37:23,861
có nghĩa là tôi chỉ có bao giờ di chuyển đến
trái với quá trình sáp nhập của tôi,

835
00:37:23,861 --> 00:37:26,360
và đó sẽ là chìa khóa để
phân tích của chúng tôi chỉ trong một khoảnh khắc.

836
00:37:26,360 --> 00:37:27,859
>> Vì vậy, bây giờ chúng ta hãy hoàn thành điều này nhanh chóng.

837
00:37:27,859 --> 00:37:31,650
Vì vậy, ba đến tiếp theo,
sau đó bốn đến tiếp theo,

838
00:37:31,650 --> 00:37:38,750
và bây giờ năm đến tiếp theo, sau đó sáu,
và bảy, và cuối cùng tám.

839
00:37:38,750 --> 00:37:42,960
Có cảm giác như các thuật toán chậm nhất
nêu ra, nhưng nếu chúng ta không thực sự

840
00:37:42,960 --> 00:37:45,510
chạy nó ở cùng một loại
tốc độ đồng hồ, do đó, để

841
00:37:45,510 --> 00:37:48,106
nói, với cùng một
đánh dấu đồng hồ như trước đây.

842
00:37:48,106 --> 00:37:48,605
Tại sao?

843
00:37:48,605 --> 00:37:51,100
Vâng, Chúng ta hãy
nhìn vào kết quả cuối cùng.

844
00:37:51,100 --> 00:37:56,990
>> Hãy trở lại đây, cho tôi
kéo lên một cuộc biểu tình trực quan

845
00:37:56,990 --> 00:37:59,030
về những gì chúng ta đã làm.

846
00:37:59,030 --> 00:38:06,110
Phóng to ở đây, trên này
trang ở đây, nói với Firefox

847
00:38:06,110 --> 00:38:08,200
mà chúng tôi muốn xếp hàng
trong hộp này, chúng ta hãy

848
00:38:08,200 --> 00:38:11,260
nói bong bóng sắp xếp, mà
chúng tôi bây giờ cũng quen thuộc,

849
00:38:11,260 --> 00:38:14,130
lựa chọn sắp xếp, mà là một
một khá đơn giản,

850
00:38:14,130 --> 00:38:18,250
và bây giờ loại hợp nhất hiện nay, trong đó
sẽ kết thúc cao trào của chúng tôi.

851
00:38:18,250 --> 00:38:21,530
Lý do phải mất quá nhiều thời gian
ở đây với con người và tôi bằng lời nói là,

852
00:38:21,530 --> 00:38:23,480
rõ ràng, tôi giải thích từng bước.

853
00:38:23,480 --> 00:38:26,920
Nhưng nếu bạn chỉ đơn giản là thực hiện điều này, nhiều
như chúng tôi đã làm bong bóng sắp xếp và lựa chọn

854
00:38:26,920 --> 00:38:30,890
loại không chỉ trực quan, xem
chỉ có bao nhiêu hiệu quả hơn

855
00:38:30,890 --> 00:38:33,330
đòn bẩy này
phân chia và chinh phục

856
00:38:33,330 --> 00:38:39,150
có thể được khi áp dụng cho một tập dữ liệu đó là
thậm chí không kích thước tám, nhưng ngay cả nhiều,

857
00:38:39,150 --> 00:38:39,970
lớn hơn nhiều.

858
00:38:39,970 --> 00:38:44,585
Tôi cung cấp cho bạn hợp nhất phân loại, bên
mặt với những thuật toán khác.

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
Điều này sẽ có được đau đớn
nhanh chóng, và kết thúc

861
00:38:58,530 --> 00:39:00,890
không phải là đặc biệt về khí hậu,
họ chỉ kết thúc được sắp xếp.

862
00:39:00,890 --> 00:39:05,280
Nhưng chìa khóa lấy đi là
trông như thế nào nhanh hơn nhiều hợp nhất phân loại

863
00:39:05,280 --> 00:39:08,110
là, trừ khi bạn nghĩ tôi
chỉ cần loại rối tung với bạn.

864
00:39:08,110 --> 00:39:13,100
Nếu chúng ta làm một lần cuối cùng này,
hãy để của lại này, hãy quay trở lại

865
00:39:13,100 --> 00:39:14,960
và chọn bong bóng sắp xếp,
và chỉ cần cho đá,

866
00:39:14,960 --> 00:39:17,330
hãy chọn chèn
sắp xếp, chỉ dành cho các biện pháp tốt.

867
00:39:17,330 --> 00:39:20,020
Và lần này một lần nữa, chúng ta hãy
chọn sắp xếp hợp nhất và chúng ta hãy

868
00:39:20,020 --> 00:39:21,595
thực sự chạy các cạnh.

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> Và nó không phải là, trên thực tế, một sự may mắn.

871
00:39:26,930 --> 00:39:31,140
Những gì tôi đã thực hiện có hiệu quả là tôi đã
chia đầu vào của tôi trong một nửa, một lần nữa,

872
00:39:31,140 --> 00:39:32,240
và một lần nữa, và một lần nữa.

873
00:39:32,240 --> 00:39:35,590
Và chỉ có rất nhiều lần bạn có thể
chia đầu vào của bạn thành hai nửa, còn lại

874
00:39:35,590 --> 00:39:36,240
và phải.

875
00:39:36,240 --> 00:39:39,425
Công thức mà chúng ta tiếp tục nhìn thấy gì
mô tả sự phân chia trong một nửa

876
00:39:39,425 --> 00:39:41,050
một lần nữa, và một lần nữa, và một lần nữa, và một lần nữa?

877
00:39:41,050 --> 00:39:41,890
>> TƯỢNG: Đăng nhập n.

878
00:39:41,890 --> 00:39:42,760
>> SPEAKER: Đăng nhập n.

879
00:39:42,760 --> 00:39:46,300
Nhưng sau đó có một bước tiến quan trọng khác,
Thuật toán này không được đăng nhập n bước.

880
00:39:46,300 --> 00:39:48,992
Nếu nó chỉ được log n bước,
chúng ta sẽ được ở cùng một vấn đề

881
00:39:48,992 --> 00:39:51,200
như trước khi mà chúng ta không thể
chắc chắn mọi thứ đều được sắp xếp.

882
00:39:51,200 --> 00:39:54,480
Bạn cần phải nhìn vào các yếu tố tối thiểu n
chắc chắn n yếu tố đều được sắp xếp,

883
00:39:54,480 --> 00:39:55,950
nếu không nó là một bước nhảy vọt của đức tin.

884
00:39:55,950 --> 00:39:59,810
>> Vì vậy, nó ghi tối thiểu n bước, nhưng
những gì về bước kết hợp phím này

885
00:39:59,810 --> 00:40:04,370
nơi tôi sáp nhập một nửa bên trái và bên phải
một nửa và đi ngang qua sân khấu?

886
00:40:04,370 --> 00:40:06,980
Có bao nhiêu bước là để hợp nhất?

887
00:40:06,980 --> 00:40:10,150
Đó là n, nhưng tôi đã không chỉ
hợp nhất lần cuối cùng.

888
00:40:10,150 --> 00:40:15,089
Trên mỗi của những cuộc gọi lồng nhau, trên mỗi
hòa trộn của những lồng nhau, tôi vẫn sắp xếp.

889
00:40:15,089 --> 00:40:18,380
Tôi kết hợp hai người này, sau đó hai
chàng trai, sau đó hai người này và vân vân.

890
00:40:18,380 --> 00:40:19,955
>> Vì vậy, tôi đã kết hợp một lần nữa, và một lần nữa.

891
00:40:19,955 --> 00:40:20,580
Đã bao nhiêu lần?

892
00:40:20,580 --> 00:40:23,510
Vì vậy, mỗi khi tôi chia
danh sách một nửa, tôi đã làm một hợp nhất.

893
00:40:23,510 --> 00:40:25,460
Chia danh sách trong một nửa, làm một hợp nhất.

894
00:40:25,460 --> 00:40:28,570
Vì vậy, nếu phân chia danh sách
có thể được thực hiện log n lần,

895
00:40:28,570 --> 00:40:33,880
và cuối cùng là sự kết hợp có n
bước, những gì có thể tại phía trên

896
00:40:33,880 --> 00:40:37,000
bị ràng buộc vào các hoạt động
thời gian của thuật toán của chúng tôi?

897
00:40:37,000 --> 00:40:37,980
n log n.

898
00:40:37,980 --> 00:40:40,560
>> Và quả thực, đó là những gì
chúng tôi đã đạt được ở đây.

899
00:40:40,560 --> 00:40:44,650
Vì vậy, những cảm nhận mà bạn nhìn thấy bằng mắt khi
những ba điều chạy bên cạnh

900
00:40:44,650 --> 00:40:47,930
được n bình phương với n
phương với n log n.

901
00:40:47,930 --> 00:40:51,010
Mà về cơ bản chúng ta sẽ thấy,
không chỉ ngày hôm nay nhưng trong tương lai,

902
00:40:51,010 --> 00:40:52,760
là nhiều, nhanh hơn nhiều.

903
00:40:52,760 --> 00:40:56,010
Một tràng pháo tay cho những kẻ,
Tôi sẽ thưởng cho họ với quả bóng căng thẳng.

904
00:40:56,010 --> 00:41:00,260
Hãy hoãn ở đây ngày hôm nay, và
chúng ta sẽ thấy bạn vào thứ hai.

905
00:41:00,260 --> 00:41:02,255