1
00:00:00,000 --> 00:00:00,030

2
00:00:00,030 --> 00:00:00,460
>> DAVID Malan: Tất cả các quyền.

3
00:00:00,460 --> 00:00:01,094
Chúng tôi đã trở lại.

4
00:00:01,094 --> 00:00:04,260
Vì vậy, trong phân khúc này trên chương trình gì
Tôi nghĩ rằng chúng tôi muốn làm là một kết hợp của sự vật.

5
00:00:04,260 --> 00:00:06,340
Một, làm một chút
của một cái gì đó tay-on,

6
00:00:06,340 --> 00:00:08,690
mặc dù sử dụng một vui tươi hơn
environment-- lập trình

7
00:00:08,690 --> 00:00:11,620
một trong đó là minh chứng của
chính xác các loại ý tưởng

8
00:00:11,620 --> 00:00:14,220
chúng tôi đã được nói đến,
nhưng một ít chính thức hơn.

9
00:00:14,220 --> 00:00:18,200
Hai, xem xét một số
những cách kỹ thuật hơn

10
00:00:18,200 --> 00:00:21,520
mà một lập trình sẽ thực sự giải quyết
vấn đề như vấn đề tìm kiếm

11
00:00:21,520 --> 00:00:24,530
mà chúng ta nhìn trước và
cũng là một cách cơ bản hơn

12
00:00:24,530 --> 00:00:26,020
vấn đề thú vị của phân loại.

13
00:00:26,020 --> 00:00:28,840
>> Chúng tôi chỉ là giả định từ nhận đi
rằng cuốn sách điện thoại đã được sắp xếp,

14
00:00:28,840 --> 00:00:31,980
nhưng mà mình thực sự là loại một
vấn đề khó khăn với nhiều cách khác nhau

15
00:00:31,980 --> 00:00:32,479
để giải quyết nó.

16
00:00:32,479 --> 00:00:34,366
Vì vậy, chúng tôi sẽ sử dụng như là
một lớp học của các vấn đề

17
00:00:34,366 --> 00:00:36,740
đại diện của những điều mà
có thể được giải quyết nói chung.

18
00:00:36,740 --> 00:00:38,980
Và sau đó chúng tôi sẽ nói chuyện
về một số chi tiết những gì

19
00:00:38,980 --> 00:00:42,360
được gọi là dữ liệu structures--
cách fancier như danh sách liên kết

20
00:00:42,360 --> 00:00:46,290
và bảng băm và cây
một lập trình viên sẽ thực sự

21
00:00:46,290 --> 00:00:48,890
sử dụng và thường sử dụng
trên một tấm bảng vẽ

22
00:00:48,890 --> 00:00:51,840
một bức tranh về những gì anh ta hoặc cô
hình dung thực hiện

23
00:00:51,840 --> 00:00:52,980
một số phần của phần mềm.

24
00:00:52,980 --> 00:00:55,130
>> Vì vậy, chúng ta hãy làm những thực hành phần đầu tiên.

25
00:00:55,130 --> 00:01:00,090
Vì vậy, chỉ có được bàn tay của bạn bẩn với một
môi trường được gọi scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Đây là một công cụ mà chúng tôi sử dụng
trong lớp học của chúng tôi.

27
00:01:02,636 --> 00:01:04,510
Mặc dù nó được thiết kế
cho lứa tuổi từ 12 trở lên,

28
00:01:04,510 --> 00:01:07,570
chúng tôi sử dụng nó cho lên
phần của điều đó khá một chút

29
00:01:07,570 --> 00:01:10,020
vì nó là một tốt đẹp, vui vẻ
cách đồ họa của việc học

30
00:01:10,020 --> 00:01:12,160
một chút gì đó về lập trình.

31
00:01:12,160 --> 00:01:17,600
Vì vậy, đi tới URL đó, nơi bạn
sẽ thấy một trang khá như thế này,

32
00:01:17,600 --> 00:01:23,330
và đi trước và bấm
Tham gia Scratch ở góc trên bên phải

33
00:01:23,330 --> 00:01:28,300
và chọn một tên người dùng và một
Mật khẩu và cuối cùng là có được cho mình

34
00:01:28,300 --> 00:01:29,970
một scratch.mit.edu account--.

35
00:01:29,970 --> 00:01:32,165

36
00:01:32,165 --> 00:01:34,665
Tôi nghĩ rằng tôi muốn sử dụng như là một
cơ hội đầu tiên để hiển thị này.

37
00:01:34,665 --> 00:01:39,120
Một câu hỏi nảy ra trong giờ nghỉ
về những gì đang thực sự trông như thế nào.

38
00:01:39,120 --> 00:01:41,315
Và chúng tôi đã nói chuyện
trong giờ nghỉ về C,

39
00:01:41,315 --> 00:01:45,060
trong particular-- đặc biệt là một
mức thấp hơn trong một ngôn ngữ trở lên.

40
00:01:45,060 --> 00:01:47,750
Và tôi chỉ cần làm một cách nhanh chóng
Google tìm kiếm để tìm mã C

41
00:01:47,750 --> 00:01:51,574
cho tìm kiếm nhị phân, các thuật toán mà chúng tôi
sử dụng để tìm kiếm cuốn sách điện thoại trước đó.

42
00:01:51,574 --> 00:01:54,240
Điều này ví dụ cụ thể, tất nhiên,
không tìm kiếm một cuốn sách điện thoại.

43
00:01:54,240 --> 00:01:57,840
Nó chỉ là tìm kiếm một bó toàn bộ
số trong bộ nhớ của máy tính.

44
00:01:57,840 --> 00:02:01,000
Nhưng nếu bạn muốn chỉ có được một hình ảnh
ý nghĩa của những gì một chương trình thực tế

45
00:02:01,000 --> 00:02:05,370
ngôn ngữ có vẻ như, có vẻ
một chút gì đó như thế này.

46
00:02:05,370 --> 00:02:09,759
Vì vậy, nó là khoảng 20-cộng,
Khoảng 30 dòng mã,

47
00:02:09,759 --> 00:02:12,640
nhưng cuộc trò chuyện chúng tôi
đã có trên nghỉ

48
00:02:12,640 --> 00:02:16,000
khoảng cách này thực sự
bị biến thành số không và những người thân

49
00:02:16,000 --> 00:02:19,200
và nếu bạn không thể chỉ trở lại mà
xử lý và đi từ số không và những người thân

50
00:02:19,200 --> 00:02:20,210
sao để mã.

51
00:02:20,210 --> 00:02:22,620
>> Thật không may, quá trình
là để biến đổi

52
00:02:22,620 --> 00:02:24,890
rằng đó là dễ dàng hơn nhiều hơn làm.

53
00:02:24,890 --> 00:02:29,400
Tôi đã đi trước và thực sự bật
rằng chương trình, tìm kiếm nhị phân,

54
00:02:29,400 --> 00:02:32,700
thành số không và những người thân bằng cách của một
chương trình được gọi là trình biên dịch mà tôi

55
00:02:32,700 --> 00:02:34,400
xảy ra để có ở đây ngay trên máy Mac của tôi.

56
00:02:34,400 --> 00:02:37,850
Và nếu bạn nhìn vào màn hình
ở đây, đặc biệt tập trung

57
00:02:37,850 --> 00:02:43,520
trên sáu cột giữa chỉ,
bạn sẽ thấy chỉ số không và những người thân.

58
00:02:43,520 --> 00:02:48,290
Và đó là những số không và những người
soạn một cách chính xác rằng chương trình tìm kiếm.

59
00:02:48,290 --> 00:02:53,720
>> Và vì vậy mỗi đoạn năm bit,
mỗi byte của số không và những người ở đây,

60
00:02:53,720 --> 00:02:57,310
đại diện một số chỉ dẫn
thường bên trong của một máy tính.

61
00:02:57,310 --> 00:03:00,730
Và trên thực tế, nếu bạn đã nghe
marketing khẩu hiệu "Intel bên trong" - đó là,

62
00:03:00,730 --> 00:03:04,610
Tất nhiên, chỉ có nghĩa là bạn có một
Intel CPU hoặc bộ não bên trong máy tính.

63
00:03:04,610 --> 00:03:08,000
Và điều đó có nghĩa là một CPU
rằng bạn có một tập lệnh,

64
00:03:08,000 --> 00:03:08,840
vậy để nói chuyện.

65
00:03:08,840 --> 00:03:11,620
>> Mỗi CPU trên thế giới, nhiều người trong
chúng được thực hiện bởi Intel những ngày này,

66
00:03:11,620 --> 00:03:13,690
hiểu một hữu hạn
số lượng hướng dẫn.

67
00:03:13,690 --> 00:03:18,690
Và những người hướng dẫn là mức quá thấp
như thêm hai con số này với nhau,

68
00:03:18,690 --> 00:03:22,560
nhân hai số này với nhau,
di chuyển này mảnh dữ liệu từ đây

69
00:03:22,560 --> 00:03:27,340
đến đây trong bộ nhớ, lưu này
thông tin từ đây đến đây trong bộ nhớ,

70
00:03:27,340 --> 00:03:32,200
và vì vậy forth-- rất, rất
Ở mức độ thấp, chi tiết gần như điện tử.

71
00:03:32,200 --> 00:03:34,780
Nhưng với những toán học
hoạt động cùng

72
00:03:34,780 --> 00:03:37,410
với những gì chúng ta đã thảo luận trước đó,
các đại diện của dữ liệu

73
00:03:37,410 --> 00:03:40,450
là số không và những người thân, có thể
bạn xây dựng tất cả mọi thứ

74
00:03:40,450 --> 00:03:44,180
mà máy tính có thể làm ngày hôm nay, cho dù
đó là văn bản, đồ họa, âm nhạc,

75
00:03:44,180 --> 00:03:45,580
hay nói cách khác.

76
00:03:45,580 --> 00:03:49,450
>> Vì vậy, điều này rất dễ dàng để có được
bị mất trong cỏ dại một cách nhanh chóng.

77
00:03:49,450 --> 00:03:52,150
Và có rất nhiều
thách thức cú pháp

78
00:03:52,150 --> 00:03:56,630
theo đó nếu bạn thực hiện đơn giản,
ngu ngốc nhất của lỗi chính tả không ai trong số các chương trình

79
00:03:56,630 --> 00:03:57,860
sẽ làm việc gì.

80
00:03:57,860 --> 00:04:00,366
Và do đó, thay vì sử dụng một
ngôn ngữ như C sáng nay,

81
00:04:00,366 --> 00:04:02,240
Tôi nghĩ rằng nó sẽ được
vui hơn để thực sự làm

82
00:04:02,240 --> 00:04:04,840
một cái gì đó trực quan hơn, mà
trong khi thiết kế cho trẻ em

83
00:04:04,840 --> 00:04:08,079
thực sự là một biểu hiện hoàn hảo
của một chương trình thực tế

84
00:04:08,079 --> 00:04:10,370
language-- chỉ xảy ra
sử dụng hình ảnh thay vì văn bản

85
00:04:10,370 --> 00:04:11,710
để đại diện cho những ý tưởng.

86
00:04:11,710 --> 00:04:15,470
>> Vì vậy, một khi bạn thực sự có một
tài khoản trên scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
nhấp vào nút Create
ở phía trên bên trái của trang web.

88
00:04:21,070 --> 00:04:24,620
Và bạn sẽ thấy một môi trường như
một trong những Tôi về để nhìn thấy trên màn hình của tôi

89
00:04:24,620 --> 00:04:26,310
đây.

90
00:04:26,310 --> 00:04:29,350
Và chúng tôi sẽ dành một chút
chút thời gian chơi ở đây.

91
00:04:29,350 --> 00:04:34,080
Hãy xem, nếu chúng ta không thể giải quyết một số bài
vấn đề với nhau trong các cách sau đây.

92
00:04:34,080 --> 00:04:39,420
>> Vì vậy, những gì bạn sẽ thấy bên trong này
environment-- và thực sự chỉ cho

93
00:04:39,420 --> 00:04:40,050
tôi tạm dừng.

94
00:04:40,050 --> 00:04:42,680
Có ai không đây?

95
00:04:42,680 --> 00:04:45,070
Không phải ở đây?

96
00:04:45,070 --> 00:04:45,800
ĐƯỢC.

97
00:04:45,800 --> 00:04:49,030
Vì vậy, hãy để tôi chỉ ra một vài
đặc điểm của môi trường này.

98
00:04:49,030 --> 00:04:55,024
>> Vì vậy, ở phía trên bên trái của màn hình, chúng tôi
có giai đoạn Scratch, vì vậy để nói chuyện.

99
00:04:55,024 --> 00:04:57,440
Scratch không chỉ là tên
của ngôn ngữ lập trình này;

100
00:04:57,440 --> 00:05:00,356
nó cũng là tên của con mèo
bạn nhìn thấy bằng cách mặc định có màu cam.

101
00:05:00,356 --> 00:05:02,160
Ông là trên sân khấu, vì vậy
giống như tôi đã mô tả

102
00:05:02,160 --> 00:05:05,770
rùa đầu xuất hiện trong một
hình chữ nhật môi trường bảng trắng.

103
00:05:05,770 --> 00:05:09,800
thế giới của con mèo này chỉ hạn chế hoàn toàn
cho rằng hình chữ nhật lên trên đó.

104
00:05:09,800 --> 00:05:12,210
>> Trong khi đó, ở bên phải
Mặt bên đây, đó là

105
00:05:12,210 --> 00:05:15,610
chỉ là một khu vực kịch bản, một
slate trống nếu bạn sẽ.

106
00:05:15,610 --> 00:05:18,590
Đây là nơi mà chúng ta sẽ viết
chương trình của chúng tôi chỉ trong một khoảnh khắc.

107
00:05:18,590 --> 00:05:22,935
Và các khối xây dựng mà chúng tôi có trách nhiệm
sử dụng để viết này program-- câu đố

108
00:05:22,935 --> 00:05:25,310
miếng, nếu bạn là will--
những người ở đây ở giữa,

109
00:05:25,310 --> 00:05:27,500
và họ đang được phân loại
bởi chức năng.

110
00:05:27,500 --> 00:05:31,000
Vì vậy, ví dụ, tôi sẽ đi trước
và chứng minh ít nhất một trong số này.

111
00:05:31,000 --> 00:05:33,690
Tôi sẽ đi trước và bấm
các loại điều khiển lên hàng đầu.

112
00:05:33,690 --> 00:05:35,720
>> Vì vậy, đây là những loại lên hàng đầu.

113
00:05:35,720 --> 00:05:39,410
Tôi sẽ nhấp vào mục Control.

114
00:05:39,410 --> 00:05:44,020
Thay vào đó, tôi sẽ nhấp vào Sự kiện
thể loại, một trong những động đầu tiên hàng đầu.

115
00:05:44,020 --> 00:05:47,790
Và nếu bạn muốn theo cùng thậm chí
khi chúng ta làm điều này, bạn hoàn toàn hoan nghênh.

116
00:05:47,790 --> 00:05:52,180
Tôi sẽ để click và kéo này
Người đầu tiên ", khi lá cờ màu xanh lá cây nhấp vào."

117
00:05:52,180 --> 00:05:58,410
Và sau đó tôi sẽ thả nó chỉ
khoảng ở phía trên cùng của bảng đá phiến trống của tôi.

118
00:05:58,410 --> 00:06:01,450
>> Và những gì tốt đẹp về Scratch
là điều này mảnh ghép, khi

119
00:06:01,450 --> 00:06:04,560
khóa liên động với câu đố khác
miếng, sẽ làm đúng nghĩa đen

120
00:06:04,560 --> 00:06:06,460
những gì những mảnh ghép nói để làm.

121
00:06:06,460 --> 00:06:09,710
Vì vậy, ví dụ, Scratch là đúng
tại ở giữa thế giới của mình.

122
00:06:09,710 --> 00:06:14,660
Tôi sẽ đi trước và chọn
bây giờ, chúng ta hãy nói, các loại chuyển động,

123
00:06:14,660 --> 00:06:18,000
nếu bạn muốn làm việc
same-- loại Motion.

124
00:06:18,000 --> 00:06:20,430
Và bây giờ nhận thấy tôi có một toàn bộ
bó của mảnh ghép ở đây

125
00:06:20,430 --> 00:06:23,370
rằng, một lần nữa, loại làm những gì họ nói.

126
00:06:23,370 --> 00:06:28,110
Và tôi sẽ đi trước và kéo và
thả các khối di chuyển ngay trên đây.

127
00:06:28,110 --> 00:06:31,860
>> Và nhận thấy rằng ngay sau khi bạn nhận được
gần dưới cùng của "lá cờ màu xanh lá cây

128
00:06:31,860 --> 00:06:34,580
nhấp nút ", thông báo
làm thế nào một dòng trắng xuất hiện,

129
00:06:34,580 --> 00:06:36,950
như thể đó là gần như
từ tính, nó muốn đi đến đó.

130
00:06:36,950 --> 00:06:43,070
Chỉ cần cho đi, và nó sẽ chụp
với nhau và hình dạng sẽ phù hợp.

131
00:06:43,070 --> 00:06:46,620
có lẽ Và bây giờ bạn có thể hầu như
đoán nơi chúng tôi đang đi với điều này.

132
00:06:46,620 --> 00:06:51,570
>> Nếu bạn nhìn vào các giai đoạn Scratch
trên đây và nhìn vào phần đầu của nó,

133
00:06:51,570 --> 00:06:55,142
bạn sẽ thấy một ánh sáng màu đỏ, một
dừng ký và một lá cờ màu xanh lá cây.

134
00:06:55,142 --> 00:06:57,100
Và tôi sẽ đi trước
và xem màn hình-- của tôi

135
00:06:57,100 --> 00:06:58,460
chỉ trong một khoảnh khắc, nếu bạn có thể.

136
00:06:58,460 --> 00:07:01,960
Tôi sẽ nhấp vào
màu xanh lá cây cờ ngay bây giờ,

137
00:07:01,960 --> 00:07:07,850
và ông chuyển những gì dường như là 10 bước
hoặc 10 pixel, 10 chấm, trên màn hình.

138
00:07:07,850 --> 00:07:13,390
>> Và như vậy không phải là thú vị,
nhưng hãy để tôi đề xuất

139
00:07:13,390 --> 00:07:17,440
mà không hề dạy này, chỉ cần
bằng cách sử dụng riêng let intuition-- của riêng bạn

140
00:07:17,440 --> 00:07:22,560
tôi đề nghị bạn tìm hiểu làm thế nào để
làm Scratch đi bộ phải ra khỏi sân khấu.

141
00:07:22,560 --> 00:07:28,700
ông đã thực hiện theo cách cho phía bên phải của
màn hình, tất cả các con đường bên phải.

142
00:07:28,700 --> 00:07:32,200
Hãy để tôi cung cấp cho bạn một thời điểm
hoặc để vật lộn với điều đó.

143
00:07:32,200 --> 00:07:37,681
Bạn có thể muốn có một cái nhìn
ở các thể loại khác của các khối.

144
00:07:37,681 --> 00:07:38,180
Tất cả các quyền.

145
00:07:38,180 --> 00:07:41,290
Như vậy chỉ cần tóm tắt lại, khi chúng ta có
lá cờ màu xanh lá cây nhấp vào đây

146
00:07:41,290 --> 00:07:44,850
và di chuyển 10 bước là
chỉ dẫn, mỗi lần tôi

147
00:07:44,850 --> 00:07:46,720
nhấp vào lá cờ màu xanh lá cây, những gì đang xảy ra?

148
00:07:46,720 --> 00:07:50,070
Vâng, đó là chạy chương trình của tôi.

149
00:07:50,070 --> 00:07:52,450
Vì vậy, tôi có thể làm điều này
có lẽ 10 lần bằng tay,

150
00:07:52,450 --> 00:07:55,130
nhưng điều này cảm thấy một chút
chút hackish, có thể nói,

151
00:07:55,130 --> 00:07:57,480
nhờ đó mà tôi không thực sự
giải quyết vấn đề.

152
00:07:57,480 --> 00:08:00,530
Tôi chỉ cố gắng một lần nữa và
Một lần nữa và một lần nữa

153
00:08:00,530 --> 00:08:03,180
cho đến khi tôi sắp xếp của vô tình
đạt được các chỉ thị

154
00:08:03,180 --> 00:08:05,560
mà tôi đặt ra để đạt được trước đó.

155
00:08:05,560 --> 00:08:08,200
>> Nhưng chúng ta biết từ chúng tôi
giả trước đó rằng có

156
00:08:08,200 --> 00:08:11,870
khái niệm này trong lập trình của vòng lặp,
làm một cái gì đó một lần nữa và một lần nữa.

157
00:08:11,870 --> 00:08:14,888
Và vì vậy tôi thấy rằng một bó của bạn
đạt cho mảnh gì đố?

158
00:08:14,888 --> 00:08:17,870

159
00:08:17,870 --> 00:08:18,730
Lặp lại cho đến khi.

160
00:08:18,730 --> 00:08:21,400
Vì vậy, chúng ta có thể làm điều gì đó
như lặp lại cho đến khi.

161
00:08:21,400 --> 00:08:23,760
Và những gì đã làm bạn lặp lại cho đến khi chính xác?

162
00:08:23,760 --> 00:08:27,720

163
00:08:27,720 --> 00:08:28,540
>> ĐƯỢC.

164
00:08:28,540 --> 00:08:31,974
Và hãy để tôi đi với một trong đó là
hơi đơn giản chỉ là một khoảnh khắc.

165
00:08:31,974 --> 00:08:33,140
Hãy để tôi đi trước và làm điều này.

166
00:08:33,140 --> 00:08:35,559
Chú ý rằng, như bạn có thể
phát hiện dưới kiểm soát,

167
00:08:35,559 --> 00:08:38,409
có khối lặp lại này, mà
không giống như nó là lớn.

168
00:08:38,409 --> 00:08:41,039
Không có nhiều phòng
giữa hai vạch vàng.

169
00:08:41,039 --> 00:08:43,539
Nhưng như một số bạn có thể có
nhận thấy, nếu bạn kéo và thả,

170
00:08:43,539 --> 00:08:45,150
thấy thế nào nó phát triển để điền vào hình dạng.

171
00:08:45,150 --> 00:08:46,274
>> Và thậm chí bạn có thể nhồi nhét hơn.

172
00:08:46,274 --> 00:08:48,670
Nó sẽ chỉ tiếp tục phát triển nếu
bạn kéo và di chuột qua nó.

173
00:08:48,670 --> 00:08:51,110
Và tôi không biết điều gì
tốt nhất ở đây, vì vậy hãy để

174
00:08:51,110 --> 00:08:54,760
tôi ít nhất lặp lại năm lần,
Chẳng hạn, và sau đó quay trở lại sân khấu

175
00:08:54,760 --> 00:08:56,720
và nhấp vào lá cờ màu xanh lá cây.

176
00:08:56,720 --> 00:08:59,110
Và bây giờ nhận thấy nó không hoàn toàn ở đó.

177
00:08:59,110 --> 00:09:02,400
>> Bây giờ một số bạn đề xuất, như
Victoria chỉ cần không, lặp lại 10 lần.

178
00:09:02,400 --> 00:09:05,140
Và điều đó thường làm
có được anh ta tất cả các cách,

179
00:09:05,140 --> 00:09:10,510
nhưng sẽ không có được một mạnh mẽ hơn
cách tùy tiện hơn để tìm ra

180
00:09:10,510 --> 00:09:12,640
bao nhiêu di chuyển để thực hiện?

181
00:09:12,640 --> 00:09:17,680
Điều gì có thể tốt hơn một khối
hơn lặp lại 10 lần được?

182
00:09:17,680 --> 00:09:20,380
>> Yeah, vậy tại sao không làm một cái gì đó mãi mãi?

183
00:09:20,380 --> 00:09:24,390
Và bây giờ hãy để tôi di chuyển mảnh ghép này
bên đó và thoát khỏi một này.

184
00:09:24,390 --> 00:09:28,300
Bây giờ thấy không có vấn đề nơi Scratch
bắt đầu, ông đi đến cạnh.

185
00:09:28,300 --> 00:09:30,700
Và may mắn MIT,
ai làm cho cào, chỉ

186
00:09:30,700 --> 00:09:33,190
làm cho chắc chắn rằng ông không bao giờ
biến mất hoàn toàn.

187
00:09:33,190 --> 00:09:35,360
Bạn luôn có thể lấy cái đuôi của mình.

188
00:09:35,360 --> 00:09:37,680
>> Và chỉ bằng trực giác,
tại sao lại tiếp tục di chuyển?

189
00:09:37,680 --> 00:09:38,892
Chuyện gì đang xảy ra ở đây?

190
00:09:38,892 --> 00:09:41,440

191
00:09:41,440 --> 00:09:43,824
Ông dường như đã dừng lại, nhưng
sau đó nếu tôi chọn lên và kéo

192
00:09:43,824 --> 00:09:45,240
ông tiếp tục muốn đi qua đó.

193
00:09:45,240 --> 00:09:46,123
Tại sao vậy?

194
00:09:46,123 --> 00:09:51,610

195
00:09:51,610 --> 00:09:54,360
Quả thật, một máy tính là nghĩa đen
sẽ làm những gì bạn nói với nó để làm.

196
00:09:54,360 --> 00:09:58,380
Vì vậy, nếu bạn nói với nó trước đó làm
sau điều mãi mãi, di chuyển 10 bước,

197
00:09:58,380 --> 00:10:01,860
nó sẽ tiếp tục đi và đi
cho đến khi tôi nhấn dấu hiệu dừng lại màu đỏ

198
00:10:01,860 --> 00:10:04,620
và ngăn chặn các chương trình hoàn toàn.

199
00:10:04,620 --> 00:10:06,610
>> Vì vậy, ngay cả khi bạn không
làm điều này, làm thế nào có thể tôi

200
00:10:06,610 --> 00:10:09,510
làm Scratch di chuyển nhanh hơn
trên màn hình?

201
00:10:09,510 --> 00:10:12,060

202
00:10:12,060 --> 00:10:13,280
Bước khác nữa, phải không?

203
00:10:13,280 --> 00:10:15,710
Vì vậy, thay vì làm 10
tại một thời điểm, tại sao chúng ta không

204
00:10:15,710 --> 00:10:20,100
đi trước và thay đổi nó đối với:
những gì bạn sẽ propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Vì vậy, bây giờ tôi sẽ nhấp vào màu xanh lá cây
cờ, và quả thực, ông đi rất nhanh.

206
00:10:24,410 --> 00:10:27,180
>> Và điều này, tất nhiên, chỉ là
một biểu hiện của hình ảnh động.

207
00:10:27,180 --> 00:10:28,060
hình ảnh động là gì?

208
00:10:28,060 --> 00:10:33,090
Nó chỉ cho bạn thấy một con người
bó toàn bộ các hình ảnh vẫn thực sự,

209
00:10:33,090 --> 00:10:34,160
thực sự, thực sự nhanh chóng.

210
00:10:34,160 --> 00:10:36,500
Và như vậy, nếu chúng ta chỉ cho
anh di chuyển nhiều bước,

211
00:10:36,500 --> 00:10:39,750
chúng tôi chỉ có tác dụng được với
thay đổi nơi ông là trên màn hình

212
00:10:39,750 --> 00:10:42,900
tất cả các nhanh hơn trên một đơn vị thời gian.

213
00:10:42,900 --> 00:10:46,454
>> Bây giờ thử thách tiếp theo mà tôi đề xuất
là để có anh bật ra khỏi mép.

214
00:10:46,454 --> 00:10:49,120
Và không biết những gì đố
mảnh exist-- vì nó tốt

215
00:10:49,120 --> 00:10:53,030
nếu bạn không nhận được để
giai đoạn của challenge-- gì

216
00:10:53,030 --> 00:10:54,280
Bạn muốn làm bằng trực giác?

217
00:10:54,280 --> 00:10:58,030
Làm thế nào chúng ta sẽ có anh ta nhảy qua nhảy lại
ra, giữa bên trái và phải không?

218
00:10:58,030 --> 00:11:02,630

219
00:11:02,630 --> 00:11:03,810
>> Yeah.

220
00:11:03,810 --> 00:11:05,680
Vì vậy, chúng tôi cần một số loại
các điều kiện, và chúng tôi

221
00:11:05,680 --> 00:11:09,710
dường như có điều kiện, do đó, để
nói chuyện, thuộc thể loại điều khiển.

222
00:11:09,710 --> 00:11:14,110
Mà trong các khối
Chúng ta có thể muốn?

223
00:11:14,110 --> 00:11:15,200
Vâng, có thể "nếu, sau đó."

224
00:11:15,200 --> 00:11:18,780
Vì vậy, nhận thấy rằng trong số các khối màu vàng
chúng tôi có ở đây, có này "nếu"

225
00:11:18,780 --> 00:11:23,920
hay đây "nếu, khác" khối đó sẽ
cho phép chúng tôi đưa ra quyết định để làm điều này

226
00:11:23,920 --> 00:11:25,000
hoặc để làm điều đó.

227
00:11:25,000 --> 00:11:27,380
và thậm chí bạn có thể làm tổ chúng
để làm nhiều điều.

228
00:11:27,380 --> 00:11:34,910
Hoặc nếu bạn đã không đi đến chưa,
đi trước để loại Sensing

229
00:11:34,910 --> 00:11:39,612
và- hãy xem nếu nó ở đây.

230
00:11:39,612 --> 00:11:43,050

231
00:11:43,050 --> 00:11:52,050
>> Vì vậy, những gì khối có thể là hữu ích ở đây
để phát hiện nếu anh ta ra khỏi sân khấu?

232
00:11:52,050 --> 00:11:56,740
Yeah, nhận thấy rằng một số các khối
có thể được parametrized, vậy để nói chuyện.

233
00:11:56,740 --> 00:12:00,706
Chúng có thể được sắp xếp tùy chỉnh, không
không giống như HTML hôm qua với các thuộc tính,

234
00:12:00,706 --> 00:12:03,330
nơi những thuộc tính loại
tùy chỉnh hành vi của một thẻ.

235
00:12:03,330 --> 00:12:08,880
Tương tự như vậy ở đây, tôi có thể lấy cảm động này
khối và thay đổi và đặt câu hỏi,

236
00:12:08,880 --> 00:12:11,500
bạn đang chạm vào chuột
con trỏ như con trỏ

237
00:12:11,500 --> 00:12:13,250
hoặc là bạn chạm vào các cạnh?

238
00:12:13,250 --> 00:12:15,210
>> Vì vậy, hãy để tôi đi vào và làm điều này.

239
00:12:15,210 --> 00:12:18,130
Tôi sẽ thu nhỏ cho một thời điểm.

240
00:12:18,130 --> 00:12:21,320
Hãy để tôi lấy mảnh ghép này
ở đây, câu đố này tác phẩm này,

241
00:12:21,320 --> 00:12:24,570
và tôi sẽ lẫn lộn
chúng chỉ trong một khoảnh khắc.

242
00:12:24,570 --> 00:12:27,620
Tôi sẽ di chuyển này,
thay đổi này để cạnh cảm động,

243
00:12:27,620 --> 00:12:38,590
và tôi sẽ chuyển động làm điều này.

244
00:12:38,590 --> 00:12:40,490
Vì vậy, đây là một số thành phần.

245
00:12:40,490 --> 00:12:42,570
Tôi nghĩ rằng tôi đã có tất cả mọi thứ tôi muốn.

246
00:12:42,570 --> 00:12:47,710
>> một người nào đó muốn đề nghị làm thế nào tôi
có thể kết nối những lẽ đầu xuống dưới

247
00:12:47,710 --> 00:12:52,020
để giải quyết các vấn đề của việc có
Scratch di chuyển phải sang trái sang phải để

248
00:12:52,020 --> 00:12:57,020
trái sang phải sang trái, mỗi
Hiện chỉ đập vào tường?

249
00:12:57,020 --> 00:12:58,050
Tôi muốn làm gì?

250
00:12:58,050 --> 00:13:01,097
Những khối tôi nên kết nối đến
"Cờ khi màu xanh lá cây nhấp đầu tiên"?

251
00:13:01,097 --> 00:13:04,060

252
00:13:04,060 --> 00:13:06,200
>> OK, vì vậy chúng ta hãy bắt đầu với "mãi mãi."

253
00:13:06,200 --> 00:13:07,170
Những gì diễn ra bên trong tiếp theo?

254
00:13:07,170 --> 00:13:10,290
Một người nào khác.

255
00:13:10,290 --> 00:13:11,850
OK, di chuyển bước.

256
00:13:11,850 --> 00:13:12,350
Tất cả các quyền.

257
00:13:12,350 --> 00:13:14,470
Rồi sao?

258
00:13:14,470 --> 00:13:15,120
Vì vậy, sau đó nếu.

259
00:13:15,120 --> 00:13:17,720
Và nhận thấy, mặc dù có vẻ
kẹp chặt chẽ với nhau,

260
00:13:17,720 --> 00:13:19,500
nó sẽ chỉ phát triển để điền vào.

261
00:13:19,500 --> 00:13:21,500
Nó sẽ chỉ nhảy ở nơi tôi muốn nó.

262
00:13:21,500 --> 00:13:25,920
>> Và để tôi đặt những gì giữa
nếu và sau đó?

263
00:13:25,920 --> 00:13:27,180
Có lẽ "nếu chạm vào cạnh."

264
00:13:27,180 --> 00:13:31,800
Và thông báo, một lần nữa, nó quá lớn
cho nó, nhưng nó sẽ phát triển để điền vào.

265
00:13:31,800 --> 00:13:35,002
Và sau đó lần lượt 15 độ?

266
00:13:35,002 --> 00:13:35,710
Bao nhiêu độ?

267
00:13:35,710 --> 00:13:38,800

268
00:13:38,800 --> 00:13:41,196
Yeah, vì vậy 180 sẽ quay
tôi tất cả các con đường xung quanh.

269
00:13:41,196 --> 00:13:42,570
Vì vậy, chúng ta hãy xem nếu tôi có quyền này.

270
00:13:42,570 --> 00:13:43,930
Hãy để tôi thu nhỏ.

271
00:13:43,930 --> 00:13:45,130
>> Hãy để tôi kéo cào lên.

272
00:13:45,130 --> 00:13:50,030
Vì vậy, ông là một chút méo
bây giờ, nhưng đó là tốt.

273
00:13:50,030 --> 00:13:52,231
Làm thế nào tôi có thể thiết lập lại anh ấy dễ dàng?

274
00:13:52,231 --> 00:13:59,879

275
00:13:59,879 --> 00:14:01,045
Tôi sẽ ăn gian một chút.

276
00:14:01,045 --> 00:14:04,074

277
00:14:04,074 --> 00:14:05,990
Vì vậy, tôi thêm một
khối, chỉ để được rõ ràng.

278
00:14:05,990 --> 00:14:08,424
Tôi muốn anh ấy chỉ 90 độ
bên phải theo mặc định,

279
00:14:08,424 --> 00:14:10,840
vì vậy tôi chỉ cần đi để nói cho anh ta
để làm điều đó theo chương trình.

280
00:14:10,840 --> 00:14:11,632
Và ở đây chúng tôi đi.

281
00:14:11,632 --> 00:14:14,740

282
00:14:14,740 --> 00:14:15,740
Chúng ta dường như đã thực hiện nó.

283
00:14:15,740 --> 00:14:19,980
Đó là một chút kỳ lạ, bởi vì
ông đang đi lộn ngược.

284
00:14:19,980 --> 00:14:21,250
Hãy gọi đó là một lỗi.

285
00:14:21,250 --> 00:14:22,120
Đó là một sai lầm.

286
00:14:22,120 --> 00:14:27,320
Một lỗi là một sai lầm trong một chương trình, một
lỗi logic mà tôi, những con người, thực hiện.

287
00:14:27,320 --> 00:14:28,985
Tại sao ông đi lộn ngược?

288
00:14:28,985 --> 00:14:33,560

289
00:14:33,560 --> 00:14:35,250
Đã MIT vít lên hoặc đã làm tôi?

290
00:14:35,250 --> 00:14:38,840

291
00:14:38,840 --> 00:14:42,550
>> Vâng, tôi có nghĩa là, nó không phải của MIT
lỗi. Họ đã cho tôi một mảnh ghép

292
00:14:42,550 --> 00:14:44,970
nói rằng một số biến số của độ.

293
00:14:44,970 --> 00:14:47,672
Và theo gợi ý của Victoria,
Tôi quay 180 độ,

294
00:14:47,672 --> 00:14:48,880
đó là trực giác đúng.

295
00:14:48,880 --> 00:14:53,700
Nhưng quay 180 độ theo nghĩa đen
có nghĩa là quay 180 độ,

296
00:14:53,700 --> 00:14:55,860
và đó không phải thực sự
những gì tôi muốn, rõ ràng.

297
00:14:55,860 --> 00:14:58,026
Bởi vì ít nhất anh ta ở
thế giới hai chiều này,

298
00:14:58,026 --> 00:15:00,740
nên bước ngoặt thực sự đi
để lật ngược cậu lên.

299
00:15:00,740 --> 00:15:04,030
>> Tôi có thể muốn sử dụng những gì khối
thay vào đó, dựa trên những gì bạn nhìn thấy ở đây?

300
00:15:04,030 --> 00:15:11,890

301
00:15:11,890 --> 00:15:14,790
Làm thế nào chúng ta có thể khắc phục điều này?

302
00:15:14,790 --> 00:15:18,380
Yeah, vì vậy chúng tôi có thể chỉ
theo hướng ngược lại.

303
00:15:18,380 --> 00:15:22,300
Và trên thực tế, ngay cả đó là
sẽ không đủ,

304
00:15:22,300 --> 00:15:26,410
bởi vì chúng ta chỉ có thể cứng mã
để chỉ trái hoặc phải.

305
00:15:26,410 --> 00:15:27,920
>> Bạn biết những gì chúng ta có thể làm gì?

306
00:15:27,920 --> 00:15:30,160
Có vẻ như chúng ta có một
khối thuận tiện ở đây.

307
00:15:30,160 --> 00:15:32,987
Nếu tôi phóng to, xem
một cái gì đó chúng tôi muốn ở đây?

308
00:15:32,987 --> 00:15:36,120

309
00:15:36,120 --> 00:15:40,020
Vì vậy, nó trông giống như MIT có một
trừu tượng được xây dựng tại đây.

310
00:15:40,020 --> 00:15:45,440
Khối này có vẻ là tương đương
mà các khối khác, số nhiều?

311
00:15:45,440 --> 00:15:49,510
>> một khối này có vẻ là tương đương
để toàn bộ ba này của khối

312
00:15:49,510 --> 00:15:50,880
mà chúng ta có ở đây.

313
00:15:50,880 --> 00:15:54,670
Vì vậy, nó quay ra tôi có thể đơn giản hóa của tôi
chương trình bằng cách loại bỏ tất cả mà

314
00:15:54,670 --> 00:15:58,270
và chỉ cần đặt này tại đây.

315
00:15:58,270 --> 00:16:01,620
Và bây giờ anh vẫn còn một chút
lỗi, và đó là tốt cho bây giờ.

316
00:16:01,620 --> 00:16:03,370
Chúng tôi sẽ để lại được.

317
00:16:03,370 --> 00:16:06,000
Nhưng chương trình của tôi thậm chí còn
đơn giản hơn, và điều này, quá,

318
00:16:06,000 --> 00:16:09,060
sẽ là đại diện
của một mục tiêu trong programming--

319
00:16:09,060 --> 00:16:13,430
là lý tưởng làm cho mã của bạn như
đơn giản, nhỏ gọn càng tốt,

320
00:16:13,430 --> 00:16:15,650
trong khi vẫn đang là
đọc càng tốt.

321
00:16:15,650 --> 00:16:20,310
Bạn không muốn làm cho nó rất gọn gàng
rằng đó là khó hiểu.

322
00:16:20,310 --> 00:16:22,826
>> Nhưng nhận thấy tôi đã thay thế
ba khối với một,

323
00:16:22,826 --> 00:16:24,200
và đó là cho là một điều tốt.

324
00:16:24,200 --> 00:16:27,280
Tôi đã tóm tắt đi những khái niệm
kiểm tra xem bạn đang

325
00:16:27,280 --> 00:16:29,120
trên các cạnh chỉ với một khối.

326
00:16:29,120 --> 00:16:31,520
Bây giờ chúng ta có thể vui vẻ với điều này, trên thực tế.

327
00:16:31,520 --> 00:16:35,790
Điều này không có thêm rất nhiều
giá trị trí tuệ nhưng giá trị vui tươi.

328
00:16:35,790 --> 00:16:39,730
Tôi sẽ đi trước
và lấy âm thanh này ở đây.

329
00:16:39,730 --> 00:16:42,900

330
00:16:42,900 --> 00:16:46,420
Vì vậy, hãy để tôi đi trước, và cho tôi
ngăn chặn các chương trình cho một thời điểm.

331
00:16:46,420 --> 00:16:52,070
Tôi sẽ ghi lại như sau,
cho phép truy cập vào micro của tôi.

332
00:16:52,070 --> 00:16:53,181
>> Ở đây chúng tôi đi.

333
00:16:53,181 --> 00:16:53,680
Ouch.

334
00:16:53,680 --> 00:16:58,710

335
00:16:58,710 --> 00:17:01,140
Hãy thử điều này một lần nữa.

336
00:17:01,140 --> 00:17:02,279
Ở đây chúng tôi đi.

337
00:17:02,279 --> 00:17:03,570
OK, tôi ghi lại những điều sai trái.

338
00:17:03,570 --> 00:17:04,580
Ở đây chúng tôi đi.

339
00:17:04,580 --> 00:17:05,080
Ouch.

340
00:17:05,080 --> 00:17:07,910

341
00:17:07,910 --> 00:17:08,800
Ouch.

342
00:17:08,800 --> 00:17:09,300
Tất cả các quyền.

343
00:17:09,300 --> 00:17:10,791
Bây giờ tôi cần phải thoát khỏi điều đó.

344
00:17:10,791 --> 00:17:11,290
Tất cả các quyền.

345
00:17:11,290 --> 00:17:13,950
>> Vì vậy, bây giờ tôi có một
ghi chỉ "ouch".

346
00:17:13,950 --> 00:17:18,040
Vì vậy, bây giờ tôi sẽ đi
trước và gọi đây là "ouch".

347
00:17:18,040 --> 00:17:20,270
Tôi sẽ quay trở lại
để kịch bản của tôi, và bây giờ

348
00:17:20,270 --> 00:17:25,460
thông báo có khối này được gọi là
chơi âm thanh "meo meo" hoặc chơi âm thanh "ouch".

349
00:17:25,460 --> 00:17:28,920
Tôi sẽ kéo này, và ở đâu
Tôi nên đặt này cho hiệu ứng hài hước?

350
00:17:28,920 --> 00:17:31,740

351
00:17:31,740 --> 00:17:37,860
Yeah, vì vậy bây giờ nó là loại
lỗi, bởi vì bây giờ này block--

352
00:17:37,860 --> 00:17:42,050
nhận thấy cách này "nếu trên bờ,
thư bị trả lại "là loại khép kín.

353
00:17:42,050 --> 00:17:43,704
Vì vậy, tôi cần phải sửa lỗi này.

354
00:17:43,704 --> 00:17:44,870
Hãy để tôi đi trước và làm điều này.

355
00:17:44,870 --> 00:17:48,630
Hãy để tôi nhận được thoát khỏi điều này và quay trở lại
để gốc của chúng tôi, thận trọng hơn

356
00:17:48,630 --> 00:17:49,870
chức năng.

357
00:17:49,870 --> 00:18:01,080
Vì vậy, "nếu chạm vào cạnh, sau đó" Tôi muốn
biến, như Victoria đề xuất,

358
00:18:01,080 --> 00:18:02,480
180 độ.

359
00:18:02,480 --> 00:18:05,497
Và tôi muốn chơi
âm thanh "ouch" đó?

360
00:18:05,497 --> 00:18:11,800

361
00:18:11,800 --> 00:18:15,580
>> Yeah, nhận thấy nó ở bên ngoài
rằng khối màu vàng.

362
00:18:15,580 --> 00:18:17,680
Vì vậy, đây cũng sẽ là một
lỗi, nhưng tôi đã nhận thấy nó.

363
00:18:17,680 --> 00:18:21,290
Vì vậy, tôi sẽ kéo nó lên đây,
và thông báo bây giờ là bên trong "nếu".

364
00:18:21,290 --> 00:18:24,250
Vì vậy, "nếu" là loại này
giống như blot cánh tay giống như

365
00:18:24,250 --> 00:18:26,260
mà chỉ sẽ
làm những gì bên trong của nó.

366
00:18:26,260 --> 00:18:30,216
Vì vậy, bây giờ nếu tôi thu nhỏ tại
nguy cơ annoying--

367
00:18:30,216 --> 00:18:32,860

368
00:18:32,860 --> 00:18:36,470
>> MÁY TÍNH: Ouch, ouch, ouch.

369
00:18:36,470 --> 00:18:39,910
>> DAVID Malan: Và nó
sẽ chỉ đi mãi mãi.

370
00:18:39,910 --> 00:18:44,160
Bây giờ chỉ cần đẩy nhanh việc
ở đây, hãy để tôi đi trước và mở ra,

371
00:18:44,160 --> 00:18:50,460
hãy say-- cho tôi đi đến một số
các công cụ của riêng tôi từ lớp.

372
00:18:50,460 --> 00:18:53,000

373
00:18:53,000 --> 00:19:00,220
Và hãy để tôi mở ra, hãy nói, này
một được làm theo một nghiên cứu sinh giảng dạy của chúng tôi

374
00:19:00,220 --> 00:19:01,500
một vài năm trước đây.

375
00:19:01,500 --> 00:19:04,732
Vì vậy, một số bạn có thể gọi lại
game này từ năm qua,

376
00:19:04,732 --> 00:19:05,940
và nó thực sự đáng chú ý.

377
00:19:05,940 --> 00:19:08,190
Mặc dù chúng tôi đã thực hiện các
đơn giản nhất của chương trình ngay bây giờ,

378
00:19:08,190 --> 00:19:09,980
chúng ta hãy xem xét điều này
thực sự trông như thế nào.

379
00:19:09,980 --> 00:19:10,650
Hãy để tôi nhấn play.

380
00:19:10,650 --> 00:19:14,210

381
00:19:14,210 --> 00:19:18,980
>> Vì vậy, trong trò chơi này, chúng ta có một
ếch, và sử dụng các mũi tên keys--

382
00:19:18,980 --> 00:19:23,340
anh sẽ bước lớn hơn tôi remember--
Tôi có thể kiểm soát ếch này.

383
00:19:23,340 --> 00:19:29,630
Và mục tiêu là để có được trên bận rộn
đường mà không cần chạy vào xe ô tô.

384
00:19:29,630 --> 00:19:34,735
Và chúng ta hãy see-- nếu tôi lên đây, tôi
phải chờ đợi cho một đăng nhập để di chuyển bằng.

385
00:19:34,735 --> 00:19:38,130

386
00:19:38,130 --> 00:19:39,274
Điều này cảm thấy giống như một lỗi.

387
00:19:39,274 --> 00:19:42,240

388
00:19:42,240 --> 00:19:43,495
Đây là loại lỗi.

389
00:19:43,495 --> 00:19:45,980

390
00:19:45,980 --> 00:19:46,480
Tất cả các quyền.

391
00:19:46,480 --> 00:19:51,550
Tôi đang trên này ở đây,
ở đó, và sau đó bạn giữ

392
00:19:51,550 --> 00:19:54,100
đi cho đến khi bạn nhận được tất cả
các con ếch, các miếng lily.

393
00:19:54,100 --> 00:19:55,920
Bây giờ điều này có thể trông
tất cả các phức tạp hơn,

394
00:19:55,920 --> 00:19:57,840
nhưng chúng ta hãy cố gắng để phá vỡ
này xuống tinh thần

395
00:19:57,840 --> 00:20:00,040
và bằng lời nói thành các khối thành phần của nó.

396
00:20:00,040 --> 00:20:03,910
Vì vậy, có lẽ là một câu đố
mảnh mà chúng tôi đã không nhìn thấy được nêu

397
00:20:03,910 --> 00:20:07,440
nhưng đó là phản ứng với tổ hợp phím,
đến những điều tôi nhấn trên bàn phím.

398
00:20:07,440 --> 00:20:11,660
>> Vì vậy, có lẽ một số loại
khối mà nói, nếu khóa bằng lên,

399
00:20:11,660 --> 00:20:15,965
sau đó làm điều gì đó với Scratch--
có thể di chuyển nó 10 bước theo cách này.

400
00:20:15,965 --> 00:20:20,240
Nếu phím xuống được nhấn, di chuyển 10 bước
Bằng cách này, hoặc phím trái, di chuyển 10 bước

401
00:20:20,240 --> 00:20:21,710
Bằng cách này, 10 bước mà.

402
00:20:21,710 --> 00:20:23,644
Tôi đã bật rõ con mèo vào một con ếch.

403
00:20:23,644 --> 00:20:26,060
Vì vậy, đó chỉ là nơi
trang phục, như các cuộc gọi Scratch it-- chúng tôi

404
00:20:26,060 --> 00:20:28,440
chỉ cần nhập khẩu một hình ảnh của con ếch.

405
00:20:28,440 --> 00:20:29,570
>> Nhưng những gì khác đang xảy ra?

406
00:20:29,570 --> 00:20:32,794
Những dòng mã khác
những mảnh ghép khác

407
00:20:32,794 --> 00:20:35,460
đã Blake, giáo viên của chúng tôi,
sử dụng trong chương trình này, rõ ràng?

408
00:20:35,460 --> 00:20:38,320

409
00:20:38,320 --> 00:20:42,730
Có gì làm cho mọi thứ move--
những gì chương trình xây dựng?

410
00:20:42,730 --> 00:20:44,950
>> Motion, sure-- nên
di chuyển khối, chắc chắn.

411
00:20:44,950 --> 00:20:49,330
Và đó khối di chuyển là những gì
bên trong, nhiều khả năng?

412
00:20:49,330 --> 00:20:52,850
Vâng, một số loại vòng lặp, có thể một
mãi mãi chặn, có thể lặp lại block--

413
00:20:52,850 --> 00:20:54,070
lặp lại cho đến khi khối.

414
00:20:54,070 --> 00:20:57,330
Và đó là những gì làm cho các bản ghi và
các miếng lily và mọi thứ khác di chuyển

415
00:20:57,330 --> 00:20:57,990
quay đi quay lại.

416
00:20:57,990 --> 00:21:00,270
Nó chỉ xảy ra không ngừng.

417
00:21:00,270 --> 00:21:03,180
>> Tại sao một số xe ô tô
di chuyển nhanh hơn so với những người khác?

418
00:21:03,180 --> 00:21:06,607
khác nhau về những chương trình này là gì?

419
00:21:06,607 --> 00:21:09,690
Vâng, có thể là một số trong số họ đang dùng
nhiều bước cùng một lúc và một số trong số họ

420
00:21:09,690 --> 00:21:10,690
ít bước cùng một lúc.

421
00:21:10,690 --> 00:21:14,670
Và các hiệu ứng hình ảnh
là nhanh so với chậm.

422
00:21:14,670 --> 00:21:16,030
>> bạn nghĩ chuyện gì đã xảy ra?

423
00:21:16,030 --> 00:21:19,700
Khi tôi nhận ếch của tôi tất cả các cách
trên đường phố và dòng sông

424
00:21:19,700 --> 00:21:23,560
lên lily pad, một cái gì đó
đáng chú ý xảy ra.

425
00:21:23,560 --> 00:21:26,540
Những gì đã xảy ra ngay sau khi tôi đã làm điều đó?

426
00:21:26,540 --> 00:21:27,210
Nó đã dừng lại.

427
00:21:27,210 --> 00:21:29,680
ếch mà dừng lại, và
Tôi có một con ếch thứ hai.

428
00:21:29,680 --> 00:21:33,155
Vì vậy, những gì xây dựng phải
sử dụng ở đó, tính năng gì?

429
00:21:33,155 --> 00:21:36,020

430
00:21:36,020 --> 00:21:38,660
>> Yeah, do đó, có một số loại
"Nếu" điều kiện trên đó, quá.

431
00:21:38,660 --> 00:21:41,909
Và nó quay out-- chúng tôi không thấy này--
nhưng có các khối khác trong đó mà

432
00:21:41,909 --> 00:21:45,300
có thể nói, nếu bạn đang cảm động
một điều khác trên màn hình,

433
00:21:45,300 --> 00:21:47,720
nếu bạn đang chạm vào pad lily, "sau đó."

434
00:21:47,720 --> 00:21:50,810
Và sau đó đó là khi chúng ta
làm cho con ếch thứ hai xuất hiện.

435
00:21:50,810 --> 00:21:54,969
Vì vậy, mặc dù trò chơi này chắc chắn là
rất ngày, mặc dù ở cái nhìn đầu tiên

436
00:21:54,969 --> 00:21:58,010
có rất nhiều đang xảy on-- và Blake
không whip này lên trong hai phút,

437
00:21:58,010 --> 00:22:00,390
nó có lẽ ông đã mất vài
giờ để tạo ra trò chơi này

438
00:22:00,390 --> 00:22:03,850
dựa trên bộ nhớ hoặc video của mình
của phiên bản năm qua của nó.

439
00:22:03,850 --> 00:22:07,940
Nhưng tất cả những điều nhỏ nhặt
đi trên màn hình trong sự cô lập

440
00:22:07,940 --> 00:22:11,550
đun sôi xuống những rất đơn giản
phong trào constructs-- hoặc báo cáo

441
00:22:11,550 --> 00:22:15,519
như chúng ta đã thảo luận, các vòng lặp và
điều kiện, và đó là về nó.

442
00:22:15,519 --> 00:22:17,060
Có một vài tính năng khác fancier.

443
00:22:17,060 --> 00:22:19,130
Một số trong số đó là hoàn toàn
thẩm mỹ, âm thanh,

444
00:22:19,130 --> 00:22:20,964
như những âm thanh tôi chỉ chơi với.

445
00:22:20,964 --> 00:22:23,380
Nhưng đối với hầu hết các phần, bạn
có trong ngôn ngữ này, Scratch,

446
00:22:23,380 --> 00:22:25,350
tất cả các nền tảng
xây dựng khối mà bạn

447
00:22:25,350 --> 00:22:29,280
có trong C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
và nhiều ngôn ngữ khác.

449
00:22:32,960 --> 00:22:36,720
Mọi thắc mắc về Scratch?

450
00:22:36,720 --> 00:22:37,220
Tất cả các quyền.

451
00:22:37,220 --> 00:22:40,303
Vì vậy, chúng tôi sẽ không đi sâu vào sâu hơn để cào,
mặc dù bạn đang chào đón cuối tuần này,

452
00:22:40,303 --> 00:22:42,860
đặc biệt là nếu bạn có con hay
cháu gái và cháu trai và như vậy,

453
00:22:42,860 --> 00:22:44,220
để giới thiệu họ đến Scratch.

454
00:22:44,220 --> 00:22:47,960
Nó thực sự là một tuyệt vời vui tươi
môi trường với, như tác giả của nó nói,

455
00:22:47,960 --> 00:22:49,120
trần nhà rất cao.

456
00:22:49,120 --> 00:22:51,670
Mặc dù chúng ta bắt đầu với
rất thấp cấp thông tin chi tiết,

457
00:22:51,670 --> 00:22:54,890
bạn thực sự có thể làm khá một chút
với nó, và điều này có lẽ là

458
00:22:54,890 --> 00:22:57,360
một cuộc biểu tình chính xác điều đó.

459
00:22:57,360 --> 00:23:02,920
>> Nhưng bây giờ chúng ta chuyển sang một số chi tiết
vấn đề phức tạp, nếu bạn muốn,

460
00:23:02,920 --> 00:23:05,870
được gọi là "tìm kiếm" và
"Phân loại", thông thường hơn.

461
00:23:05,870 --> 00:23:09,500
Chúng tôi đã có danh bạ điện thoại này earlier-- đây
khác chỉ cho discussion--

462
00:23:09,500 --> 00:23:13,460
rằng chúng ta đã có thể tìm kiếm
hiệu quả hơn vì

463
00:23:13,460 --> 00:23:15,270
của một giả định quan trọng.

464
00:23:15,270 --> 00:23:17,655
Và chỉ để được rõ ràng, những gì
giả định là tôi làm

465
00:23:17,655 --> 00:23:19,280
khi tìm kiếm thông qua các cuốn sách điện thoại này?

466
00:23:19,280 --> 00:23:23,342

467
00:23:23,342 --> 00:23:25,300
Đó Mike Smith là trong
danh bạ điện thoại, mặc dù tôi

468
00:23:25,300 --> 00:23:27,410
sẽ có thể xử lý
kịch bản mà không có anh

469
00:23:27,410 --> 00:23:30,720
đó nếu tôi chỉ dừng lại sớm.

470
00:23:30,720 --> 00:23:31,806
Cuốn sách là chữ cái.

471
00:23:31,806 --> 00:23:33,930
Và đó là một rất hào phóng
giả định, bởi vì đó

472
00:23:33,930 --> 00:23:36,580
nghĩa someone-- tôi là loại
cắt một góc,

473
00:23:36,580 --> 00:23:40,580
như tôi nhanh hơn bởi vì một người nào đó
khác đã làm rất nhiều công việc khó khăn đối với tôi.

474
00:23:40,580 --> 00:23:43,120
>> Nhưng những gì nếu điện thoại
Cuốn sách đã được phân?

475
00:23:43,120 --> 00:23:47,050
Có lẽ Verizon đã lười biếng, chỉ ném
tên và số của tất cả mọi người ở đó

476
00:23:47,050 --> 00:23:50,120
có thể trong thứ tự mà họ
đăng ký dịch vụ điện thoại.

477
00:23:50,120 --> 00:23:54,570
Và bao nhiêu thời gian nó đưa tôi
để tìm một người như Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1.000 điện thoại trang book-- bao nhiêu
trang nào để xem xét thông qua?

479
00:23:58,160 --> 00:23:58,905
>> Tất cả bọn họ.

480
00:23:58,905 --> 00:24:00,030
Bạn đang loại ra khỏi may mắn.

481
00:24:00,030 --> 00:24:03,420
Bạn có nghĩa là phải nhìn vào mỗi
trang nếu các cuốn sách điện thoại chỉ là

482
00:24:03,420 --> 00:24:04,450
được sắp xếp ngẫu nhiên.

483
00:24:04,450 --> 00:24:06,910
Bạn có thể nhận được may mắn và tìm Mike
trên trang đầu tiên, bởi vì ông

484
00:24:06,910 --> 00:24:08,826
là khách hàng đầu tiên
để đặt hàng dịch vụ điện thoại.

485
00:24:08,826 --> 00:24:10,760
Nhưng ông có thể đã được người cuối cùng, quá.

486
00:24:10,760 --> 00:24:12,500
>> Vì vậy, thứ tự ngẫu nhiên là không tốt.

487
00:24:12,500 --> 00:24:16,750
Vì vậy, giả sử chúng ta phải sắp xếp
danh bạ điện thoại hoặc dữ liệu phân loại chung

488
00:24:16,750 --> 00:24:18,520
mà chúng ta đã được ban cho.

489
00:24:18,520 --> 00:24:19,440
Làm thế nào chúng ta có thể làm điều đó?

490
00:24:19,440 --> 00:24:21,360
>> Vâng, hãy để tôi chỉ cần cố gắng
một ví dụ đơn giản ở đây.

491
00:24:21,360 --> 00:24:24,290
Hãy để tôi đi trước và quăng một
vài con số trên bảng.

492
00:24:24,290 --> 00:24:35,480
Giả sử những con số chúng tôi có được,
hãy nói, bốn, hai, một, và ba.

493
00:24:35,480 --> 00:24:38,390
Và, Ben, sắp xếp những con số này cho chúng tôi.

494
00:24:38,390 --> 00:24:39,017
>> Được rồi, tốt lắm.

495
00:24:39,017 --> 00:24:39,850
Cậu đã làm thế nào vậy?

496
00:24:39,850 --> 00:24:42,731

497
00:24:42,731 --> 00:24:43,230
Tất cả các quyền.

498
00:24:43,230 --> 00:24:44,710
Vì vậy, bắt đầu với nhỏ nhất
giá trị và cao nhất,

499
00:24:44,710 --> 00:24:46,084
và đó thực sự trực giác tốt.

500
00:24:46,084 --> 00:24:48,080
Và nhận ra chúng tôi rằng
con người là thực sự khá

501
00:24:48,080 --> 00:24:49,913
giỏi giải quyết vấn đề
như thế này, ít nhất là

502
00:24:49,913 --> 00:24:51,810
khi dữ liệu là tương đối nhỏ.

503
00:24:51,810 --> 00:24:54,860
Ngay sau khi bạn bắt đầu có hàng trăm
số, hàng ngàn số,

504
00:24:54,860 --> 00:24:58,440
hàng triệu con số, Ben lẽ
không thể làm điều đó khá là nhanh,

505
00:24:58,440 --> 00:25:00,620
giả sử rằng có
những khoảng trống trong các con số.

506
00:25:00,620 --> 00:25:03,450
Khá dễ dàng để truy cập đến một triệu
cách khác, tiêu thụ chỉ là thời gian.

507
00:25:03,450 --> 00:25:07,150
>> Vì vậy, các thuật toán nó âm thanh
như Ben sử dụng chỉ cần bây giờ

508
00:25:07,150 --> 00:25:08,930
là tìm kiếm cho số nhỏ nhất.

509
00:25:08,930 --> 00:25:12,900
Vì vậy, mặc dù con người chúng ta có thể mất
trong rất nhiều thông tin trực quan,

510
00:25:12,900 --> 00:25:14,830
một máy tính thực sự là
hạn chế hơn một chút.

511
00:25:14,830 --> 00:25:17,560
Các máy tính có thể chỉ
nhìn vào một byte tại một thời điểm

512
00:25:17,560 --> 00:25:20,770
hoặc có thể bốn byte tại một time--
những ngày này có lẽ 8 byte tại một time--

513
00:25:20,770 --> 00:25:24,450
nhưng một số lượng rất nhỏ
các byte tại một thời điểm nhất định.

514
00:25:24,450 --> 00:25:28,480
>> Vì vậy, cho rằng chúng ta thực sự có
bốn giá trị riêng biệt đây--

515
00:25:28,480 --> 00:25:32,440
và bạn có thể nghĩ về Ben là có
bị mù mắt nếu ông là một máy tính như vậy

516
00:25:32,440 --> 00:25:36,450
rằng ông không thể nhìn thấy bất cứ điều gì khác
hơn một số tại một time--

517
00:25:36,450 --> 00:25:39,720
vì vậy chúng tôi sẽ thường giả định, như trong
Tiếng Anh, chúng ta sẽ đọc từ phải sang trái.

518
00:25:39,720 --> 00:25:42,870
Vì vậy, số đầu tiên Bến lẽ trông
tại bốn và sau đó rất nhanh chóng

519
00:25:42,870 --> 00:25:44,770
nhận ra đó là một khá lớn
number-- cho tôi tiếp tục tìm.

520
00:25:44,770 --> 00:25:45,357
>> Có hai.

521
00:25:45,357 --> 00:25:45,940
Chờ một chút.

522
00:25:45,940 --> 00:25:47,070
Hai là nhỏ hơn so với bốn.

523
00:25:47,070 --> 00:25:47,986
Tôi sẽ nhớ.

524
00:25:47,986 --> 00:25:49,070
Hai bây giờ là nhỏ nhất.

525
00:25:49,070 --> 00:25:50,417
Bây giờ cùng-- mà thậm chí còn tốt hơn.

526
00:25:50,417 --> 00:25:51,250
Điều đó thậm chí nhỏ hơn.

527
00:25:51,250 --> 00:25:54,000
Tôi sẽ quên đi hai
và chỉ cần nhớ một cái bây giờ.

528
00:25:54,000 --> 00:25:56,550
>> Và anh có thể ngừng tìm kiếm?

529
00:25:56,550 --> 00:25:58,360
Vâng, anh ấy có thể dựa
trên thông tin này,

530
00:25:58,360 --> 00:26:00,477
nhưng ông muốn tìm kiếm tốt hơn
phần còn lại của danh sách.

531
00:26:00,477 --> 00:26:02,060
Bởi vì những gì nếu không có trong danh sách?

532
00:26:02,060 --> 00:26:03,643
Điều gì nếu tiêu cực một là trong danh sách?

533
00:26:03,643 --> 00:26:07,720
Ông chỉ biết rằng câu trả lời của mình
là đúng nếu anh ta triệt

534
00:26:07,720 --> 00:26:08,729
đã kiểm tra toàn bộ danh sách.

535
00:26:08,729 --> 00:26:10,020
Vì vậy, chúng ta nhìn vào những việc còn lại.

536
00:26:10,020 --> 00:26:11,394
Three-- đó là một sự lãng phí thời gian.

537
00:26:11,394 --> 00:26:13,540
Got không may mắn, nhưng tôi đã
vẫn chính xác để làm như vậy.

538
00:26:13,540 --> 00:26:17,857
Và vì vậy bây giờ anh có lẽ
chọn số nhỏ nhất

539
00:26:17,857 --> 00:26:20,440
và chỉ cần đặt nó ở đầu
của danh sách, như tôi sẽ làm ở đây.

540
00:26:20,440 --> 00:26:23,480
Bây giờ bạn đã làm gì tiếp theo, mặc dù
bạn không nghĩ về nó gần

541
00:26:23,480 --> 00:26:25,962
đến mức độ này?

542
00:26:25,962 --> 00:26:27,670
Lặp lại quá trình này,
vì vậy một số loại vòng lặp.

543
00:26:27,670 --> 00:26:28,920
Có một ý tưởng quen thuộc.

544
00:26:28,920 --> 00:26:30,860
Vì vậy, đây là bốn.

545
00:26:30,860 --> 00:26:32,110
Đó là hiện nhỏ nhất.

546
00:26:32,110 --> 00:26:33,220
Đó là một ứng cử viên.

547
00:26:33,220 --> 00:26:33,900
Không còn nữa.

548
00:26:33,900 --> 00:26:34,770
Bây giờ tôi đã nhìn thấy hai.

549
00:26:34,770 --> 00:26:36,630
Đó là phần tử nhỏ nhất tiếp theo.

550
00:26:36,630 --> 00:26:40,800
Three-- đó không phải là nhỏ, vì vậy
tại Bến có thể nhổ ra hai.

551
00:26:40,800 --> 00:26:44,510
>> Và bây giờ chúng ta lặp lại quá trình này, và
tất nhiên ba bị kéo ra sau.

552
00:26:44,510 --> 00:26:45,420
Lặp lại quá trình này.

553
00:26:45,420 --> 00:26:46,990
Bốn bị kéo ra.

554
00:26:46,990 --> 00:26:50,140
Và bây giờ chúng ta đang trên con số,
vì vậy danh sách phải được sắp xếp.

555
00:26:50,140 --> 00:26:51,960
>> Và quả thực, đây là một thuật toán chính thức.

556
00:26:51,960 --> 00:26:56,610
Một nhà khoa học máy tính sẽ
gọi đây là "sắp xếp chọn"

557
00:26:56,610 --> 00:27:00,880
ý tưởng là loại một
liệt kê iteratively-- lại

558
00:27:00,880 --> 00:27:03,807
và một lần nữa và một lần nữa lựa chọn
số nhỏ nhất.

559
00:27:03,807 --> 00:27:06,140
Và những gì tốt đẹp về nó là
nó chỉ là như vậy darn trực quan.

560
00:27:06,140 --> 00:27:07,470
Đó là đơn giản như vậy.

561
00:27:07,470 --> 00:27:11,100
Và bạn có thể lặp lại cùng một
hoạt động một lần nữa và một lần nữa.

562
00:27:11,100 --> 00:27:12,150
Nó đơn giản.

563
00:27:12,150 --> 00:27:17,170
>> Trong trường hợp này nó đã được nhanh chóng, nhưng
bao lâu nó thực sự mất?

564
00:27:17,170 --> 00:27:19,880
Hãy làm cho nó có vẻ và
cảm thấy tẻ nhạt hơn một chút.

565
00:27:19,880 --> 00:27:24,150
Vì vậy, một, hai, ba, bốn, năm sáu,
bảy, tám, chín, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- số tùy ý.

567
00:27:26,160 --> 00:27:28,780
Tôi chỉ muốn có thêm này
thời gian hơn so với chỉ bốn.

568
00:27:28,780 --> 00:27:30,780
Vì vậy, nếu tôi đã có một toàn bộ
loạt các con số now-- nó

569
00:27:30,780 --> 00:27:32,420
thậm chí không quan trọng
những gì họ are-- của chúng

570
00:27:32,420 --> 00:27:34,380
suy nghĩ về điều này
thuật toán thực sự là như thế.

571
00:27:34,380 --> 00:27:35,857
>> Giả sử có số đó.

572
00:27:35,857 --> 00:27:38,190
Một lần nữa, không có vấn đề gì
họ, nhưng họ là ngẫu nhiên.

573
00:27:38,190 --> 00:27:39,679
Tôi đang áp dụng thuật toán của Ben.

574
00:27:39,679 --> 00:27:41,220
Tôi cần phải chọn số nhỏ nhất.

575
00:27:41,220 --> 00:27:41,761
Tôi làm gì?

576
00:27:41,761 --> 00:27:44,240
Và tôi sẽ phải thể chất
làm điều đó thời gian này để hành động nó ra.

577
00:27:44,240 --> 00:27:46,099
Nhìn, nhìn,
tìm kiếm, tìm kiếm, tìm kiếm.

578
00:27:46,099 --> 00:27:48,140
Chỉ bằng thời gian tôi nhận được để
cuối của danh sách có thể

579
00:27:48,140 --> 00:27:51,230
Tôi nhận ra nhỏ nhất
Số là hai thời gian này.

580
00:27:51,230 --> 00:27:52,720
Một không có trong danh sách.

581
00:27:52,720 --> 00:27:54,400
Vì vậy, tôi đặt xuống hai.

582
00:27:54,400 --> 00:27:55,590
>> Tôi làm gì tiếp theo?

583
00:27:55,590 --> 00:27:58,600
Nhìn, nhìn, nhìn, nhìn.

584
00:27:58,600 --> 00:28:02,250
Bây giờ tôi thấy số bảy, vì
có những khoảng trống trong những numbers--

585
00:28:02,250 --> 00:28:03,300
nhưng chỉ tùy ý.

586
00:28:03,300 --> 00:28:03,800
Tất cả các quyền.

587
00:28:03,800 --> 00:28:06,030
Vì vậy, bây giờ tôi có thể đặt xuống bảy.

588
00:28:06,030 --> 00:28:08,860
Nhìn tìm kiếm, tìm kiếm.

589
00:28:08,860 --> 00:28:11,030
>> Bây giờ tôi giả định, các
Tất nhiên, đó Ben không

590
00:28:11,030 --> 00:28:14,780
có thêm RAM, thêm
bộ nhớ, bởi vì, tất nhiên,

591
00:28:14,780 --> 00:28:16,080
Tôi đang nhìn vào cùng một số.

592
00:28:16,080 --> 00:28:18,246
Chắc chắn tôi có thể nhớ
tất cả những con số,

593
00:28:18,246 --> 00:28:19,930
và điều đó hoàn toàn đúng.

594
00:28:19,930 --> 00:28:22,610
Nhưng nếu Ben nhớ lại tất cả
của các con số ông nhìn thấy,

595
00:28:22,610 --> 00:28:24,430
ông đã không thực sự làm
tiến bộ cơ bản

596
00:28:24,430 --> 00:28:26,170
bởi vì anh ta đã có
khả năng tìm kiếm

597
00:28:26,170 --> 00:28:27,540
thông qua các số trên bảng.

598
00:28:27,540 --> 00:28:29,373
Nhớ tất cả các
số không giúp đỡ,

599
00:28:29,373 --> 00:28:32,490
bởi vì anh ta vẫn có thể là một máy tính
chỉ nhìn vào, chúng tôi đã nói, một số

600
00:28:32,490 --> 00:28:33,080
tại một thời điểm.

601
00:28:33,080 --> 00:28:35,760
Vì vậy, không loại cheat
có mà bạn có thể tận dụng.

602
00:28:35,760 --> 00:28:39,170
>> Vì vậy, trong thực tế, như tôi
tiếp tục tìm kiếm danh sách,

603
00:28:39,170 --> 00:28:44,200
Tôi nghĩa là có phải chỉ cần tiếp tục đi
qua lại thông qua nó, tuốt ra

604
00:28:44,200 --> 00:28:45,710
số nhỏ nhất tiếp theo.

605
00:28:45,710 --> 00:28:48,810
Và như bạn có thể loại suy luận
từ phong trào ngớ ngẩn của tôi,

606
00:28:48,810 --> 00:28:50,860
này chỉ được rất
tẻ nhạt rất nhanh chóng,

607
00:28:50,860 --> 00:28:54,850
và tôi dường như được đi lại và
ra, qua lại khá một chút.

608
00:28:54,850 --> 00:29:03,220
Bây giờ để cho công bằng, tôi không phải đi
khá, tốt, chúng ta hãy see-- để được công bằng,

609
00:29:03,220 --> 00:29:06,310
Tôi không phải đi bộ khá
nhiều bước mỗi lần.

610
00:29:06,310 --> 00:29:09,200
Bởi vì, tất nhiên, như tôi
chọn số điện thoại từ danh sách,

611
00:29:09,200 --> 00:29:11,860
danh sách còn lại là nhận được ngắn hơn.

612
00:29:11,860 --> 00:29:14,240
>> Và như vậy chúng ta hãy suy nghĩ về
bao nhiêu bước Tôi thực sự

613
00:29:14,240 --> 00:29:16,010
traipsing qua từng thời gian.

614
00:29:16,010 --> 00:29:18,950
Trong tình huống đầu tiên
chúng tôi đã có 16 con số,

615
00:29:18,950 --> 00:29:22,210
và vì vậy chúng ta hãy chỉ maximally--
làm điều này cho một discussion--

616
00:29:22,210 --> 00:29:25,640
Tôi đã xem xét thông qua 16
số để tìm nhỏ nhất.

617
00:29:25,640 --> 00:29:28,420
Nhưng một khi tôi móc con
số nhỏ nhất, làm thế nào

618
00:29:28,420 --> 00:29:30,590
dài là danh sách còn lại, tất nhiên?

619
00:29:30,590 --> 00:29:31,420
Chỉ cần 15.

620
00:29:31,420 --> 00:29:34,670
Vì vậy, có bao nhiêu số đã Ben hoặc tôi có
để xem xét thông qua lần thứ hai xung quanh?

621
00:29:34,670 --> 00:29:36,832
15, chỉ để đi tìm nhỏ nhất.

622
00:29:36,832 --> 00:29:39,540
Nhưng bây giờ, tất nhiên, danh sách này là,
quá, nhỏ hơn so với trước đây.

623
00:29:39,540 --> 00:29:42,540
Vì vậy, có bao nhiêu bước đã làm tôi
phải dành thời gian tiếp theo?

624
00:29:42,540 --> 00:29:49,970
14 và sau đó 13 và sau đó 12, cộng với dấu chấm,
dấu chấm, dấu chấm, cho đến khi tôi là trái với chỉ một.

625
00:29:49,970 --> 00:29:53,146
Vì vậy, bây giờ là một nhà khoa học máy tính sẽ
yêu cầu, cũng, những gì mà tất cả bằng nhau?

626
00:29:53,146 --> 00:29:55,770
Nó thực sự tương đương với một số bê tông
số mà chúng ta có thể chắc chắn

627
00:29:55,770 --> 00:30:00,490
làm số học, nhưng chúng tôi muốn nói
về hiệu quả của thuật toán

628
00:30:00,490 --> 00:30:04,940
một chút formulaically hơn,
độc lập bao lâu trong danh sách là.

629
00:30:04,940 --> 00:30:06,240
>> Và như vậy bạn biết những gì?

630
00:30:06,240 --> 00:30:09,860
Đây là 16, nhưng như tôi đã nói trước đây,
chúng ta chỉ cần gọi cho kích thước của vấn đề

631
00:30:09,860 --> 00:30:10,970
n, trong đó n là một số số.

632
00:30:10,970 --> 00:30:13,220
Có thể đó là 16, có lẽ nó
ba, có lẽ đó là một triệu.

633
00:30:13,220 --> 00:30:13,761
Tôi không biết.

634
00:30:13,761 --> 00:30:14,390
Tôi không quan tâm.

635
00:30:14,390 --> 00:30:16,520
Những gì tôi thực sự muốn là
một công thức mà tôi có thể

636
00:30:16,520 --> 00:30:19,420
sử dụng để so sánh các thuật toán này
chống lại các thuật toán khác

637
00:30:19,420 --> 00:30:22,350
rằng ai đó có thể yêu cầu bồi thường
tốt hơn hoặc tồi tệ hơn.

638
00:30:22,350 --> 00:30:25,430
>> Vì vậy, nó quay ra, và chỉ có tôi
biết điều này từ hồi phổ thông,

639
00:30:25,430 --> 00:30:34,790
rằng điều này thực sự hoạt động ra để cùng
điều khi n trên n cộng với một trong hai.

640
00:30:34,790 --> 00:30:40,020
Và điều này xảy ra để bằng, của
Tất nhiên, n bình phương cộng với n qua hai.

641
00:30:40,020 --> 00:30:43,250
Vì vậy, nếu tôi muốn có một công thức
cho bao nhiêu bước

642
00:30:43,250 --> 00:30:46,330
đã tham gia tìm kiếm ở tất cả
của những con số một lần nữa và một lần nữa

643
00:30:46,330 --> 00:30:52,681
và một lần nữa và một lần nữa, tôi sẽ nói
nó n bình phương cộng với n qua hai.

644
00:30:52,681 --> 00:30:53,430
Nhưng bạn biết những gì?

645
00:30:53,430 --> 00:30:54,500
Điều này chỉ có vẻ lộn xộn.

646
00:30:54,500 --> 00:30:56,470
Tôi chỉ thực sự muốn có một
cảm giác chung của sự vật.

647
00:30:56,470 --> 00:30:58,810
Và bạn có thể nhớ lại từ
trường trung học mà có

648
00:30:58,810 --> 00:31:00,660
là khái niệm hạn cao nhất.

649
00:31:00,660 --> 00:31:05,300
Mà những điều khoản này, các n
bình phương, n, hoặc một nửa,

650
00:31:05,300 --> 00:31:07,550
có tác động nhất theo thời gian?

651
00:31:07,550 --> 00:31:11,920
Các n lớn hơn được, mà
những vấn đề này nhiều nhất?

652
00:31:11,920 --> 00:31:15,560
>> Nói cách khác, nếu tôi cắm
trong một triệu, n bình phương

653
00:31:15,560 --> 00:31:17,900
sẽ có nhiều khả năng nhất
các yếu tố chi phối,

654
00:31:17,900 --> 00:31:21,670
vì một triệu lần
chính nó là lớn hơn rất nhiều

655
00:31:21,670 --> 00:31:23,682
hơn cộng thêm một thêm triệu.

656
00:31:23,682 --> 00:31:24,390
Vì vậy, bạn biết những gì?

657
00:31:24,390 --> 00:31:27,305
Đây là một darn như lớn
số nếu bạn vuông một số.

658
00:31:27,305 --> 00:31:28,430
Điều này không thực sự quan trọng.

659
00:31:28,430 --> 00:31:30,596
Chúng tôi chỉ đi ngang đó
ra và quên nó đi.

660
00:31:30,596 --> 00:31:34,250
Và do đó, một nhà khoa học máy tính sẽ nói
rằng hiệu quả của thuật toán này

661
00:31:34,250 --> 00:31:37,850
là vào thứ tự của n squared--
Tôi có nghĩa là thực sự là một xấp xỉ.

662
00:31:37,850 --> 00:31:40,810
Nó là loại khoảng n bình phương.

663
00:31:40,810 --> 00:31:44,130
Qua thời gian, lớn hơn
và lớn hơn n được, điều này

664
00:31:44,130 --> 00:31:47,610
là một ước lượng tốt cho những gì
hiệu quả hoặc thiếu hiệu quả

665
00:31:47,610 --> 00:31:49,400
của thuật toán này là thực sự.

666
00:31:49,400 --> 00:31:52,040
Và tôi lấy được rằng, tất nhiên,
từ thực sự làm toán.

667
00:31:52,040 --> 00:31:54,040
Nhưng bây giờ tôi chỉ vẫy
bàn tay của tôi, bởi vì tôi chỉ

668
00:31:54,040 --> 00:31:55,790
muốn có một cảm giác chung của thuật toán này.

669
00:31:55,790 --> 00:31:58,850
>> Vì vậy, bằng cách sử dụng cùng một logic, trong khi đó,
chúng ta hãy xem xét thuật toán khác

670
00:31:58,850 --> 00:32:01,162
chúng tôi đã nhìn at-- tìm kiếm tuyến tính.

671
00:32:01,162 --> 00:32:02,870
Khi tôi đã được tìm kiếm
cho book-- điện thoại

672
00:32:02,870 --> 00:32:05,980
không phân loại nó, tìm kiếm
qua book-- điện thoại

673
00:32:05,980 --> 00:32:09,197
chúng tôi luôn nói rằng đó là
1000 bước, hoặc 500 bước.

674
00:32:09,197 --> 00:32:10,280
Nhưng chúng ta hãy khái quát đó.

675
00:32:10,280 --> 00:32:12,860
Nếu có n trang trong
danh bạ điện thoại, có chuyện gì

676
00:32:12,860 --> 00:32:17,250
thời gian chạy hoặc
hiệu quả của tìm kiếm tuyến tính?

677
00:32:17,250 --> 00:32:19,750
Đó là vào thứ tự của
bao nhiêu bước để tìm

678
00:32:19,750 --> 00:32:24,210
Mike Smith sử dụng tìm kiếm tuyến tính,
Thuật toán đầu tiên, hoặc thậm chí thứ hai?

679
00:32:24,210 --> 00:32:27,240

680
00:32:27,240 --> 00:32:31,710
>> Trong trường hợp xấu nhất, Mike
là ở phần cuối của cuốn sách.

681
00:32:31,710 --> 00:32:35,590
Vì vậy, nếu các cuốn sách điện thoại có 1.000 trang,
chúng ta nói thời gian qua, trong trường hợp xấu nhất,

682
00:32:35,590 --> 00:32:38,380
nó có thể mất khoảng bao
nhiều trang để tìm Mike?

683
00:32:38,380 --> 00:32:38,990
Giống như 1000.

684
00:32:38,990 --> 00:32:39,830
Đây là một ràng buộc trên.

685
00:32:39,830 --> 00:32:41,790
Đó là một tình huống tồi tệ nhất có thể.

686
00:32:41,790 --> 00:32:44,410
Nhưng một lần nữa, chúng ta đang di chuyển ra
từ con số như 1000 bây giờ.

687
00:32:44,410 --> 00:32:45,730
Nó chỉ là n.

688
00:32:45,730 --> 00:32:47,470
>> Vì vậy, kết luận hợp lý là những gì?

689
00:32:47,470 --> 00:32:50,210
Tìm Mike trong điện thoại
cuốn sách đó có các trang n

690
00:32:50,210 --> 00:32:55,280
có thể mất, trong trường hợp tồi tệ nhất,
bao nhiêu bước vào thứ tự của n?

691
00:32:55,280 --> 00:32:58,110
Và thực sự là một máy tính
nhà khoa học sẽ nói

692
00:32:58,110 --> 00:33:02,340
rằng thời gian chạy, hoặc
hiệu suất hoặc hiệu quả

693
00:33:02,340 --> 00:33:07,470
hoặc không hiệu quả, của một thuật toán như
một tìm kiếm tuyến tính là vào thứ tự của n.

694
00:33:07,470 --> 00:33:10,010
Và chúng ta có thể áp dụng cùng một
logic của một cái gì đó vượt ra ngoài

695
00:33:10,010 --> 00:33:13,170
như tôi chỉ cần làm vào thứ hai
thuật toán chúng ta đã có với các cuốn sách điện thoại,

696
00:33:13,170 --> 00:33:16,040
nơi mà chúng tôi đã đi hai trang tại một thời điểm.

697
00:33:16,040 --> 00:33:20,120
>> Vì vậy, 1.000 trang điện thoại cuốn sách có thể
đưa chúng tôi 500 lượt trang, cộng với một

698
00:33:20,120 --> 00:33:21,910
nếu chúng ta tăng gấp đôi trở lại một chút.

699
00:33:21,910 --> 00:33:26,590
Vì vậy, nếu một cuốn sách điện thoại có các trang n, nhưng
chúng tôi đang làm hai trang tại một thời điểm,

700
00:33:26,590 --> 00:33:28,900
đó là khoảng những gì?

701
00:33:28,900 --> 00:33:33,190
N qua hai, vì vậy đó là giống như n qua hai.

702
00:33:33,190 --> 00:33:38,490
Nhưng tôi đã yêu một
thời điểm trước đó n qua two--

703
00:33:38,490 --> 00:33:41,060
đó là loại giống như chỉ n.

704
00:33:41,060 --> 00:33:44,050
Nó chỉ là một yếu tố không đổi,
các nhà khoa học máy tính sẽ nói.

705
00:33:44,050 --> 00:33:45,970
Hãy chỉ tập trung vào
các biến, really--

706
00:33:45,970 --> 00:33:47,780
các biến lớn nhất trong phương trình.

707
00:33:47,780 --> 00:33:52,530
>> Vì vậy, tìm kiếm tuyến tính, cho dù thực hiện một
trang tại một thời điểm hoặc hai trang tại một thời điểm,

708
00:33:52,530 --> 00:33:54,810
là loại cơ bản giống nhau.

709
00:33:54,810 --> 00:33:56,880
Nó vẫn là vào thứ tự của n.

710
00:33:56,880 --> 00:34:01,930
Nhưng tôi khẳng định với hình ảnh của tôi trước đó
rằng các thuật toán thứ ba là không

711
00:34:01,930 --> 00:34:02,480
tuyến tính.

712
00:34:02,480 --> 00:34:03,605
Đó không phải là một đường thẳng.

713
00:34:03,605 --> 00:34:08,659
Nó là đường cong, và các
đại số công thức có là gì?

714
00:34:08,659 --> 00:34:11,812
Log của n-- để đăng nhập cơ sở hai của n.

715
00:34:11,812 --> 00:34:14,520
Và chúng tôi không phải đi vào quá
chi tiết hơn về logarit ngày hôm nay,

716
00:34:14,520 --> 00:34:17,394
nhưng hầu hết các nhà khoa học máy tính sẽ không
thậm chí nói với bạn những gì cơ bản là.

717
00:34:17,394 --> 00:34:20,639
Bởi vì nó là tất cả chỉ
yếu tố liên tục, có thể nói,

718
00:34:20,639 --> 00:34:22,659
chỉ khác nhau số nhẹ.

719
00:34:22,659 --> 00:34:31,179
Và vì vậy đây sẽ là một rất phổ biến
cách cho máy tính đặc biệt chính thức

720
00:34:31,179 --> 00:34:33,949
các nhà khoa học tại một hội đồng quản trị hoặc
lập trình viên tại một bảng trắng

721
00:34:33,949 --> 00:34:36,889
thực sự tranh cãi đó
thuật toán họ sẽ sử dụng

722
00:34:36,889 --> 00:34:39,500
hoặc những gì hiệu quả
các thuật toán của họ.

723
00:34:39,500 --> 00:34:42,960
>> Và đây không phải là điều gì cần thiết
bạn thảo luận tại bất kỳ chi tiết,

724
00:34:42,960 --> 00:34:47,889
nhưng một lập trình tốt là một người nào đó
người có một, nền chính thức vững chắc.

725
00:34:47,889 --> 00:34:50,120
Anh ấy có thể nói chuyện với
bạn trong các loại hình cách

726
00:34:50,120 --> 00:34:53,350
và thực sự làm
lập luận định tính như

727
00:34:53,350 --> 00:34:56,870
tại sao một thuật toán hoặc
một phần của phần mềm

728
00:34:56,870 --> 00:35:00,165
là cấp trên trong một số cách khác.

729
00:35:00,165 --> 00:35:02,540
Bởi vì bạn có thể chắc chắn
chỉ cần chạy chương trình của một người

730
00:35:02,540 --> 00:35:04,980
và đếm số giây
nó cần để sắp xếp một số con số,

731
00:35:04,980 --> 00:35:06,710
và bạn có thể chạy một số
chương trình của người khác

732
00:35:06,710 --> 00:35:08,418
và đếm số
giây nó mất.

733
00:35:08,418 --> 00:35:12,840
Nhưng đây là một cách tổng quát hơn,
bạn có thể sử dụng để phân tích các thuật toán,

734
00:35:12,840 --> 00:35:15,520
nếu bạn muốn, chỉ cần trên
giấy hay chỉ bằng lời nói.

735
00:35:15,520 --> 00:35:18,430
Thậm chí không cần chạy nó, mà không
thậm chí cố gắng đầu vào mẫu,

736
00:35:18,430 --> 00:35:20,180
bạn chỉ có thể lý do thông qua nó.

737
00:35:20,180 --> 00:35:24,670
Và do đó, với việc thuê một nhà phát triển hoặc nếu
có anh ta hoặc cô loại tranh luận với bạn

738
00:35:24,670 --> 00:35:28,460
tại sao thuật toán của họ, bí mật của họ
nước sốt để tìm kiếm tỷ

739
00:35:28,460 --> 00:35:30,580
các trang web cho bạn
công ty là tốt hơn, những

740
00:35:30,580 --> 00:35:33,302
là các loại của các đối số họ
lý tưởng nên có thể thực hiện.

741
00:35:33,302 --> 00:35:35,010
Hoặc ít nhất đó là những
các loại vật

742
00:35:35,010 --> 00:35:40,211
rằng sẽ đưa ra trong cuộc thảo luận, tại
ít nhất là trong một cuộc thảo luận rất chính thức.

743
00:35:40,211 --> 00:35:40,710
Tất cả các quyền.

744
00:35:40,710 --> 00:35:44,400
Vì vậy, Ben đề nghị một cái gì đó
gọi là chọn loại.

745
00:35:44,400 --> 00:35:48,200
Nhưng tôi sẽ đề xuất rằng có
cách khác để làm điều này, quá.

746
00:35:48,200 --> 00:35:50,400
Những gì tôi đã không thực sự thích
về thuật toán của Ben

747
00:35:50,400 --> 00:35:54,400
là ông tiếp tục đi, hoặc
khi tôi đi bộ qua lại

748
00:35:54,400 --> 00:35:56,930
và qua lại và lui.

749
00:35:56,930 --> 00:36:04,130
Điều gì nếu thay vào đó tôi được làm
một cái gì đó giống như những con số ở đây

750
00:36:04,130 --> 00:36:08,200
và tôi được chỉ đối phó với mỗi
số lần lượt như tôi cho nó?

751
00:36:08,200 --> 00:36:10,780
>> Nói cách khác, đây là
danh sách các số điện thoại.

752
00:36:10,780 --> 00:36:12,944
Bốn là, một, ba, hai.

753
00:36:12,944 --> 00:36:14,360
Và tôi sẽ làm như sau.

754
00:36:14,360 --> 00:36:17,230
Tôi sẽ chèn số
nơi mà họ thuộc khá

755
00:36:17,230 --> 00:36:18,980
hơn chọn chúng cùng một thời gian.

756
00:36:18,980 --> 00:36:20,820
Nói cách khác, đây là con số bốn.

757
00:36:20,820 --> 00:36:22,430
>> Dưới đây là danh sách ban đầu của tôi.

758
00:36:22,430 --> 00:36:25,290
Và tôi sẽ duy trì
cơ bản là một danh sách mới đây.

759
00:36:25,290 --> 00:36:26,710
Vì vậy, đây là danh sách cũ.

760
00:36:26,710 --> 00:36:28,560
Đây là danh sách mới.

761
00:36:28,560 --> 00:36:30,220
Tôi thấy số bốn đầu tiên.

762
00:36:30,220 --> 00:36:34,500
danh sách mới của tôi là bước đầu trống rỗng,
do đó, nó là trivially trường hợp

763
00:36:34,500 --> 00:36:36,410
bốn mà bây giờ cả mọi loại danh sách.

764
00:36:36,410 --> 00:36:39,560
Tôi chỉ lấy số tôi đưa ra,
và tôi đặt nó trong danh sách mới của tôi.

765
00:36:39,560 --> 00:36:41,460
>> Là danh sách mới này được sắp xếp?

766
00:36:41,460 --> 00:36:41,990
Yeah.

767
00:36:41,990 --> 00:36:45,090
Đó là ngu ngốc vì chỉ có một
yếu tố, nhưng nó hoàn toàn được sắp xếp.

768
00:36:45,090 --> 00:36:46,390
Không có gì ra khỏi vị trí là.

769
00:36:46,390 --> 00:36:49,290
Thật thú vị hơn, thuật toán này,
khi tôi chuyển sang bước tiếp theo.

770
00:36:49,290 --> 00:36:50,550
>> Bây giờ tôi có một.

771
00:36:50,550 --> 00:36:55,430
Vì vậy, một, tất nhiên, thuộc về tại
bắt đầu hoặc kết thúc của danh sách mới này?

772
00:36:55,430 --> 00:36:56,360
Sự bắt đầu.

773
00:36:56,360 --> 00:36:58,530
Vì vậy, tôi phải làm một số công việc bây giờ.

774
00:36:58,530 --> 00:37:01,410
Tôi đã tham gia một số
quyền tự do với điểm đánh dấu của tôi

775
00:37:01,410 --> 00:37:03,120
bằng cách chỉ vẽ mọi thứ
nơi tôi muốn họ,

776
00:37:03,120 --> 00:37:05,320
nhưng đó không thực sự
chính xác trong một máy tính.

777
00:37:05,320 --> 00:37:08,530
Một máy tính, như chúng ta biết, có
RAM, hay Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
và đó là một byte và
một byte và byte khác.

779
00:37:12,411 --> 00:37:14,910
Và nếu bạn có một gigabyte của
RAM, bạn có một tỷ byte,

780
00:37:14,910 --> 00:37:16,680
nhưng chúng thể chất ở một địa điểm.

781
00:37:16,680 --> 00:37:19,540
Bạn không thể chỉ di chuyển những thứ xung quanh
bằng cách vẽ lên bảng

782
00:37:19,540 --> 00:37:20,750
bất cứ nơi nào bạn muốn.

783
00:37:20,750 --> 00:37:24,090
Vì vậy, nếu danh sách mới của tôi có
bốn địa điểm trong bộ nhớ,

784
00:37:24,090 --> 00:37:27,480
tiếc là bốn là
đã ở vị trí sai.

785
00:37:27,480 --> 00:37:30,410
>> Vì vậy, để chèn số một
Tôi không thể chỉ vẽ nó ở đây.

786
00:37:30,410 --> 00:37:31,901
bộ nhớ vị trí này không tồn tại.

787
00:37:31,901 --> 00:37:35,150
Đó sẽ là lừa dối, và tôi đã
gian lận trong những bức tranh cho một vài phút

788
00:37:35,150 --> 00:37:35,800
đây.

789
00:37:35,800 --> 00:37:40,950
Vì vậy, thực sự, nếu tôi muốn đặt một ở đây,
Tôi phải tạm thời sao chép bốn

790
00:37:40,950 --> 00:37:43,030
và sau đó đặt một ở đó.

791
00:37:43,030 --> 00:37:45,500
>> Đó là tốt, đó là đúng,
đó là kỹ thuật có thể,

792
00:37:45,500 --> 00:37:48,410
nhưng nhận ra đó là việc làm thêm.

793
00:37:48,410 --> 00:37:50,460
Tôi không chỉ đưa số tại chỗ.

794
00:37:50,460 --> 00:37:53,026
đầu tiên tôi đã phải di chuyển một
số lượng, sau đó đặt nó tại chỗ,

795
00:37:53,026 --> 00:37:54,650
vì vậy tôi loại tăng gấp đôi số lượng làm việc của mình.

796
00:37:54,650 --> 00:37:55,660
Vì vậy, giữ cho rằng trong tâm trí.

797
00:37:55,660 --> 00:37:57,120
>> Nhưng bây giờ tôi đang thực hiện với yếu tố này.

798
00:37:57,120 --> 00:37:59,056
Bây giờ tôi muốn lấy số ba.

799
00:37:59,056 --> 00:38:00,430
Ở đâu, tất nhiên, nó thuộc về ai?

800
00:38:00,430 --> 00:38:01,480
Ở giữa.

801
00:38:01,480 --> 00:38:03,650
Tôi không thể ăn gian nữa
và chỉ cần đặt nó ở đó,

802
00:38:03,650 --> 00:38:06,770
bởi vì, một lần nữa, bộ nhớ này
là ở vị trí vật lý.

803
00:38:06,770 --> 00:38:10,900
Vì vậy, tôi phải sao chép bốn
và đặt ba trên đây.

804
00:38:10,900 --> 00:38:11,550
Không phải là một thỏa thuận lớn.

805
00:38:11,550 --> 00:38:14,610
Nó chỉ là một bước thêm
again-- cảm thấy rất rẻ tiền.

806
00:38:14,610 --> 00:38:16,445
>> Nhưng bây giờ tôi chuyển sang hai.

807
00:38:16,445 --> 00:38:17,820
Hai, tất nhiên, thuộc về đây.

808
00:38:17,820 --> 00:38:20,990
Bây giờ bạn bắt đầu để xem như thế nào
công việc có thể chồng chất lên.

809
00:38:20,990 --> 00:38:23,520
Bây giờ những gì tôi phải làm gì?

810
00:38:23,520 --> 00:38:28,570
Vâng, tôi phải di chuyển bốn,
sau đó tôi phải sao chép ba,

811
00:38:28,570 --> 00:38:31,200
và bây giờ tôi có thể chèn hai.

812
00:38:31,200 --> 00:38:34,460
Và bắt với điều này
thuật toán, thú vị đủ,

813
00:38:34,460 --> 00:38:41,050
được rằng giả sử chúng ta có một chi tiết cực đoan
Trường hợp đó là hãy nói tám, bảy,

814
00:38:41,050 --> 00:38:45,150
sáu, năm, bốn, ba, hai, một.

815
00:38:45,150 --> 00:38:49,450
Đây là, trong nhiều trường hợp,
trường hợp xấu nhất,

816
00:38:49,450 --> 00:38:51,570
vì điều darn
là nghĩa đen về phía sau.

817
00:38:51,570 --> 00:38:53,670
>> Nó không thực sự
ảnh hưởng đến thuật toán của Ben,

818
00:38:53,670 --> 00:38:55,940
bởi vì trong lựa chọn của Ben
loại anh ta sẽ giữ

819
00:38:55,940 --> 00:38:58,359
đi lui trong danh sách.

820
00:38:58,359 --> 00:39:01,150
Và bởi vì ông luôn tìm kiếm
thông qua danh sách còn lại toàn bộ,

821
00:39:01,150 --> 00:39:02,858
nó không quan trọng
nơi mà các yếu tố này.

822
00:39:02,858 --> 00:39:05,630
Nhưng trong trường hợp này với chèn của tôi
approach-- hãy thử này.

823
00:39:05,630 --> 00:39:08,616
>> Vì vậy, một, hai, ba, bốn,
năm, sáu, bảy, tám.

824
00:39:08,616 --> 00:39:11,630
Một hai ba bốn,
năm, sáu, bảy, tám.

825
00:39:11,630 --> 00:39:14,320
Tôi sẽ lấy tám,
và nơi nào tôi đặt nó?

826
00:39:14,320 --> 00:39:17,260
Vâng, vào đầu danh sách của tôi,
bởi vì danh sách mới này được sắp xếp.

827
00:39:17,260 --> 00:39:18,760
Và tôi vượt qua nó ra.

828
00:39:18,760 --> 00:39:20,551
>> Tôi đặt bảy ở đâu?

829
00:39:20,551 --> 00:39:21,050
Khỉ thật.

830
00:39:21,050 --> 00:39:23,174
Nó cần phải đi đến đó, vì vậy
Tôi phải làm một số sao chép.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Và bây giờ bảy tại đây.

833
00:39:28,480 --> 00:39:29,860
Bây giờ tôi chuyển sang sáu.

834
00:39:29,860 --> 00:39:30,980
Bây giờ nó làm việc nhiều hơn.

835
00:39:30,980 --> 00:39:32,570
>> Tám phải đi đây.

836
00:39:32,570 --> 00:39:33,920
Bảy phải đi đây.

837
00:39:33,920 --> 00:39:35,450
Bây giờ sáu có thể đi đây.

838
00:39:35,450 --> 00:39:37,950
Bây giờ tôi lấy năm.

839
00:39:37,950 --> 00:39:40,560
Bây giờ tám phải đi
ở đây, bảy phải đi đây,

840
00:39:40,560 --> 00:39:43,650
Sáu phải đi đây, và
tại ngũ và lặp lại.

841
00:39:43,650 --> 00:39:46,610
Và tôi là khá nhiều
di chuyển nó liên tục.

842
00:39:46,610 --> 00:39:52,950
>> Vì vậy, ở cuối, algorithm-- này chúng ta sẽ
gọi nó chèn sort-- thực

843
00:39:52,950 --> 00:39:55,020
có rất nhiều công việc, quá.

844
00:39:55,020 --> 00:39:56,970
Nó chỉ khác nhau
loại công việc hơn so với Ben.

845
00:39:56,970 --> 00:40:00,090
công việc của Ben đã cho tôi đi
qua lại tất cả các thời gian,

846
00:40:00,090 --> 00:40:03,510
chọn tiếp theo nhỏ nhất
yếu tố một lần nữa và một lần nữa.

847
00:40:03,510 --> 00:40:06,660
Vì vậy, nó là loại này rất trực quan của công việc.

848
00:40:06,660 --> 00:40:10,600
>> thuật toán khác này, đó vẫn là
correct-- nó sẽ có được công việc done--

849
00:40:10,600 --> 00:40:12,800
chỉ thay đổi số lượng công việc.

850
00:40:12,800 --> 00:40:15,420
Nó trông giống như ban đầu bạn
tiết kiệm, bởi vì bạn chỉ

851
00:40:15,420 --> 00:40:19,190
đối phó với mỗi phần tử
lên phía trước mà không đi tất cả

852
00:40:19,190 --> 00:40:20,930
các cách thức thông qua danh sách như Ben đã.

853
00:40:20,930 --> 00:40:25,300
Nhưng vấn đề là, đặc biệt là trong những
trường hợp điên nơi mà nó là tất cả về phía sau,

854
00:40:25,300 --> 00:40:27,830
bạn chỉ cần loại
trì hoãn công việc khó khăn

855
00:40:27,830 --> 00:40:30,360
cho đến khi bạn có để sửa chữa sai lầm của bạn.

856
00:40:30,360 --> 00:40:33,919
>> Và vì vậy nếu bạn có thể tưởng tượng này
tám và bảy và sáu và năm

857
00:40:33,919 --> 00:40:36,710
và sau bốn ba và hai
di chuyển theo cách của họ thông qua danh sách,

858
00:40:36,710 --> 00:40:39,060
chúng tôi đã chỉ cần thay đổi
loại công việc chúng tôi đang làm.

859
00:40:39,060 --> 00:40:42,340
Thay vì làm việc đó tại
bắt đầu lặp đi lặp lại của tôi,

860
00:40:42,340 --> 00:40:45,250
Tôi chỉ làm nó ở
Cuối mỗi lần lặp.

861
00:40:45,250 --> 00:40:50,550
Vì vậy, nó chỉ ra rằng thuật toán này,
quá, thường được gọi là sắp xếp chèn,

862
00:40:50,550 --> 00:40:52,190
cũng là thứ tự của n bình phương.

863
00:40:52,190 --> 00:40:56,480
Nó thực sự không tốt,
không tốt ở tất cả.

864
00:40:56,480 --> 00:41:00,810
>> Tuy nhiên, có một cách tiếp cận thứ ba
Tôi sẽ khuyến khích chúng ta phải xem xét,

865
00:41:00,810 --> 00:41:02,970
đó là điều này.

866
00:41:02,970 --> 00:41:07,850
Vì vậy, giả danh sách của tôi, vì đơn giản
một lần nữa, là bốn, một, ba,

867
00:41:07,850 --> 00:41:11,080
two-- chỉ bốn số.

868
00:41:11,080 --> 00:41:13,300
Ben có trực giác tốt,
trực giác tốt của con người

869
00:41:13,300 --> 00:41:16,340
trước đây, mà chúng tôi cố định toàn bộ
liệt kê eventually-- loại chèn.

870
00:41:16,340 --> 00:41:18,020
Tôi dỗ dành chúng tôi cùng.

871
00:41:18,020 --> 00:41:22,530
Nhưng chúng ta hãy xem xét các
Cách đơn giản để sửa danh sách này.

872
00:41:22,530 --> 00:41:24,110
>> Danh sách này không được sắp xếp.

873
00:41:24,110 --> 00:41:26,130
Tại sao?

874
00:41:26,130 --> 00:41:31,920
Trong tiếng Anh, giải thích lý do tại sao
nó không thực sự được sắp xếp.

875
00:41:31,920 --> 00:41:33,400
có nghĩa là gì không để được sắp xếp?

876
00:41:33,400 --> 00:41:34,220
>> HỌC SINH: Nó không phải tuần tự.

877
00:41:34,220 --> 00:41:34,990
>> DAVID Malan: Không tuần tự.

878
00:41:34,990 --> 00:41:35,822
Hãy cho tôi một ví dụ.

879
00:41:35,822 --> 00:41:37,180
>> HỌC SINH: Đặt chúng theo thứ tự.

880
00:41:37,180 --> 00:41:37,440
>> DAVID Malan: OK.

881
00:41:37,440 --> 00:41:38,790
Hãy cho tôi một ví dụ cụ thể hơn.

882
00:41:38,790 --> 00:41:39,832
>> HỌC SINH: Sắp xếp tăng dần.

883
00:41:39,832 --> 00:41:41,206
DAVID Malan: Không thứ tự tăng dần.

884
00:41:41,206 --> 00:41:42,100
Được chính xác hơn.

885
00:41:42,100 --> 00:41:45,190
Tôi không biết những gì bạn có nghĩa là tăng dần.

886
00:41:45,190 --> 00:41:47,150
Chuyện gì vậy?

887
00:41:47,150 --> 00:41:49,930
>> HỌC SINH: Nhỏ nhất trong số
số không có trong không gian đầu tiên.

888
00:41:49,930 --> 00:41:51,140
>> DAVID Malan: số nhỏ nhất của
không phải trong không gian đầu tiên.

889
00:41:51,140 --> 00:41:52,120
Hãy cụ thể hơn.

890
00:41:52,120 --> 00:41:55,000
Tôi bắt đầu để đón về.

891
00:41:55,000 --> 00:41:59,470
Chúng tôi sẽ tính được, nhưng
những gì ra khỏi trật tự ở đây?

892
00:41:59,470 --> 00:42:00,707
>> HỌC SINH: dãy số học.

893
00:42:00,707 --> 00:42:02,040
DAVID Malan: dãy số học.

894
00:42:02,040 --> 00:42:04,248
loại tất cả mọi người của công tác kế
nó đây-- mức rất cao.

895
00:42:04,248 --> 00:42:07,450
Chỉ cần theo nghĩa đen cho tôi biết những gì
sai lầm như một sức lăm tuổi.

896
00:42:07,450 --> 00:42:08,310
>> HỌC SINH: Thêm một.

897
00:42:08,310 --> 00:42:08,750
>> DAVID Malan: Đó là gì?

898
00:42:08,750 --> 00:42:09,610
>> HỌC SINH: Thêm một.

899
00:42:09,610 --> 00:42:11,235
>> DAVID Malan: Bạn có nghĩa là một cộng gì?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Hãy cho tôi một khác nhau lăm tuổi.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
sai, mẹ là gì?

904
00:42:18,330 --> 00:42:19,940
sai, cha là gì?

905
00:42:19,940 --> 00:42:22,808
bạn có ý nghĩa gì này không được sắp xếp?

906
00:42:22,808 --> 00:42:24,370
>> HỌC SINH: Đây không phải là nơi thích hợp.

907
00:42:24,370 --> 00:42:25,580
>> DAVID Malan: có gì
không đúng chỗ?

908
00:42:25,580 --> 00:42:26,174
>> HỌC SINH: Bốn.

909
00:42:26,174 --> 00:42:27,090
DAVID Malan: OK, tốt.

910
00:42:27,090 --> 00:42:29,110
Vì vậy, bốn không phải là nơi mà nó nên được.

911
00:42:29,110 --> 00:42:30,590
Đặc biệt, là quyền này?

912
00:42:30,590 --> 00:42:33,000
Bốn và một, đầu tiên
hai số tôi nhìn thấy.

913
00:42:33,000 --> 00:42:34,930
Thê nay đung không?

914
00:42:34,930 --> 00:42:36,427
Không, chúng ra lệnh, phải không?

915
00:42:36,427 --> 00:42:38,135
Trong thực tế, cho rằng bây giờ
về một máy tính, quá.

916
00:42:38,135 --> 00:42:40,824
Nó chỉ có thể nhìn vào có thể một,
có lẽ hai việc cùng once--

917
00:42:40,824 --> 00:42:43,240
và thực sự chỉ có một điều
tại một thời điểm, nhưng nó có thể ít nhất

918
00:42:43,240 --> 00:42:45,790
nhìn vào một điều thì
Điều tiếp theo ngay bên cạnh nó.

919
00:42:45,790 --> 00:42:47,380
>> Vì vậy, có những theo thứ tự?

920
00:42:47,380 --> 00:42:48,032
Tất nhiên là không.

921
00:42:48,032 --> 00:42:48,740
Vì vậy, bạn biết những gì?

922
00:42:48,740 --> 00:42:51,020
Tại sao chúng ta không đem em bé
bước sửa chữa vấn đề này

923
00:42:51,020 --> 00:42:53,410
thay vì làm những ưa thích
các thuật toán như Ben, nơi

924
00:42:53,410 --> 00:42:56,440
ông loại sửa chữa nó bằng cách
Looping qua danh sách

925
00:42:56,440 --> 00:42:59,670
thay vì làm những gì tôi đã làm, nơi
Tôi chỉ là loại cố định nó như chúng ta đi đâu?

926
00:42:59,670 --> 00:43:03,650
Hãy chỉ theo nghĩa đen phá vỡ
khái niệm về số thứ tự order--,

927
00:43:03,650 --> 00:43:06,990
gọi nó là bất cứ điều gì bạn want--
vào những so sánh theo cặp.

928
00:43:06,990 --> 00:43:07,590
>> Bốn và một.

929
00:43:07,590 --> 00:43:09,970
Đây có phải là thứ tự đúng?

930
00:43:09,970 --> 00:43:11,310
Vì vậy, hãy khắc phục điều đó.

931
00:43:11,310 --> 00:43:14,700
Một và bốn, và sau đó
chúng tôi sẽ chỉ sao chép đó.

932
00:43:14,700 --> 00:43:15,560
Được rồi, tốt.

933
00:43:15,560 --> 00:43:17,022
Tôi cố định một trong bốn người.

934
00:43:17,022 --> 00:43:18,320
Ba và hai?

935
00:43:18,320 --> 00:43:18,820
Không.

936
00:43:18,820 --> 00:43:21,690
Hãy để những lời của tôi phù hợp với ngón tay của tôi.

937
00:43:21,690 --> 00:43:23,695
Bốn và ba?

938
00:43:23,695 --> 00:43:27,930
>> Nó không phải theo thứ tự, vì vậy tôi sẽ
để làm một, ba, bốn, hai.

939
00:43:27,930 --> 00:43:28,680
Được rồi, tốt lắm.

940
00:43:28,680 --> 00:43:32,310
Bây giờ bốn và hai?

941
00:43:32,310 --> 00:43:33,370
Chúng tôi cần phải sửa lỗi này, quá.

942
00:43:33,370 --> 00:43:36,700
Vì vậy, một, ba, hai, bốn người.

943
00:43:36,700 --> 00:43:39,820
Vì vậy, nó được sắp xếp?

944
00:43:39,820 --> 00:43:43,170
Không, nhưng nó gần gũi hơn với sắp xếp?

945
00:43:43,170 --> 00:43:48,930
>> Đó là, bởi vì chúng tôi cố định này
sai lầm, chúng tôi cố định sai lầm này,

946
00:43:48,930 --> 00:43:50,370
và chúng tôi cố định sai lầm này.

947
00:43:50,370 --> 00:43:52,420
Vì vậy, chúng tôi cố định ba sai lầm cho là.

948
00:43:52,420 --> 00:43:58,100
Tuy không thực sự tìm được sắp xếp, nhưng
nó là quan gần gũi hơn với sắp xếp

949
00:43:58,100 --> 00:44:00,080
bởi vì chúng ta cố định một số những sai lầm.

950
00:44:00,080 --> 00:44:02,047
>> Bây giờ tôi phải làm gì tiếp theo?

951
00:44:02,047 --> 00:44:03,630
Tôi loại đạt đến cuối danh sách.

952
00:44:03,630 --> 00:44:05,680
Tôi dường như đã cố định
tất cả những sai lầm, nhưng không có.

953
00:44:05,680 --> 00:44:08,510
Bởi vì trong trường hợp này, một số con số
có thể có bọt lên gần gũi hơn

954
00:44:08,510 --> 00:44:10,410
với các số khác mà
vẫn đang trong trật tự.

955
00:44:10,410 --> 00:44:12,951
Vì vậy, hãy làm điều đó một lần nữa, và tôi sẽ
chỉ làm điều đó ở nơi thời gian này.

956
00:44:12,951 --> 00:44:14,170
Một và ba?

957
00:44:14,170 --> 00:44:14,720
Tốt rồi.

958
00:44:14,720 --> 00:44:16,070
Ba và hai?

959
00:44:16,070 --> 00:44:17,560
Tất nhiên không có, vì vậy chúng ta hãy thay đổi điều đó.

960
00:44:17,560 --> 00:44:19,160
Vì vậy, hai, ba.

961
00:44:19,160 --> 00:44:21,340
Ba và bốn?

962
00:44:21,340 --> 00:44:24,370
Và bây giờ chúng ta chỉ cần có
đặc biệt là mô phạm ở đây.

963
00:44:24,370 --> 00:44:26,350
Có phải sắp xếp?

964
00:44:26,350 --> 00:44:29,280
Bạn con người biết nó được sắp xếp.

965
00:44:29,280 --> 00:44:30,400
>> Tôi phải cố gắng một lần nữa.

966
00:44:30,400 --> 00:44:31,900
Vì vậy, Olivia đang đề nghị tôi thử lại.

967
00:44:31,900 --> 00:44:32,530
Tại sao?

968
00:44:32,530 --> 00:44:35,810
Bởi vì một máy tính không có
sự sang trọng của đôi mắt con người của chúng tôi

969
00:44:35,810 --> 00:44:38,080
chỉ liếc back-- OK, tôi đang thực hiện.

970
00:44:38,080 --> 00:44:41,610
Làm thế nào để các máy tính xác định
rằng danh sách này hiện đang được sắp xếp?

971
00:44:41,610 --> 00:44:44,590
Cơ học.

972
00:44:44,590 --> 00:44:47,650
>> Tôi nên đi qua
một lần nữa, và chỉ khi tôi

973
00:44:47,650 --> 00:44:51,190
không thực hiện / tìm thấy bất kỳ sai lầm có thể tôi
sau đó kết luận như máy tính, vâng,

974
00:44:51,190 --> 00:44:51,980
chúng tôi đang tốt để đi.

975
00:44:51,980 --> 00:44:54,850
Vì vậy, một và hai, hai và
ba, ba và bốn.

976
00:44:54,850 --> 00:44:58,030
Bây giờ tôi không nói rằng đây là
sắp xếp, bởi vì tôi đã không có thay đổi.

977
00:44:58,030 --> 00:45:01,940
Bây giờ nó sẽ là một lỗi và chỉ
Thật ngớ ngẩn nếu tôi, máy tính,

978
00:45:01,940 --> 00:45:05,640
hỏi những câu hỏi tương tự một lần nữa
mong câu trả lời khác nhau.

979
00:45:05,640 --> 00:45:07,110
không nên xảy ra.

980
00:45:07,110 --> 00:45:08,600
>> Và vì vậy bây giờ danh sách được sắp xếp.

981
00:45:08,600 --> 00:45:12,630
Thật không may, thời gian chạy của
Thuật toán này cũng là n bình phương.

982
00:45:12,630 --> 00:45:13,130
Tại sao?

983
00:45:13,130 --> 00:45:19,520
Bởi vì bạn có n số, và trong
trường hợp xấu nhất bạn phải di chuyển số n

984
00:45:19,520 --> 00:45:23,637
n lần vì bạn phải tiếp tục đi
lại để kiểm tra và có thể khắc phục

985
00:45:23,637 --> 00:45:24,220
những con số này.

986
00:45:24,220 --> 00:45:26,280
Và chúng ta có thể làm một nhiều hơn
phân tích chính thức, quá.

987
00:45:26,280 --> 00:45:29,530
>> Vì vậy, đây là tất cả để nói rằng chúng tôi đã thực hiện
ba cách tiếp cận khác nhau, một

988
00:45:29,530 --> 00:45:32,210
của chúng trực quan ngay lập tức
off the bat từ Ben

989
00:45:32,210 --> 00:45:35,170
để chèn đề nghị của tôi
loại với trang này

990
00:45:35,170 --> 00:45:38,540
nơi bạn loại đánh mất
rừng cho cây ban đầu.

991
00:45:38,540 --> 00:45:41,760
Nhưng sau đó nếu bạn lùi lại một bước,
thì đấy, chúng tôi đã cố định các khái niệm phân loại.

992
00:45:41,760 --> 00:45:43,824
Vì vậy, đây là, dám nói,
một mức độ thấp hơn có lẽ

993
00:45:43,824 --> 00:45:45,740
hơn một số người khác
thuật toán, nhưng chúng ta hãy

994
00:45:45,740 --> 00:45:48,550
xem nếu chúng ta không thể hình dung
những bằng cách này.

995
00:45:48,550 --> 00:45:51,450
>> Vì vậy, đây là một số đẹp
phần mềm mà một người nào đó

996
00:45:51,450 --> 00:45:56,110
viết sử dụng các thanh đầy màu sắc đó là
sẽ làm những điều sau đây cho chúng ta.

997
00:45:56,110 --> 00:45:57,736
Mỗi một thanh đại diện cho một số.

998
00:45:57,736 --> 00:46:00,026
Taller thanh, lớn hơn
số lượng, thanh nhỏ hơn,

999
00:46:00,026 --> 00:46:00,990
nhỏ hơn số lượng.

1000
00:46:00,990 --> 00:46:05,880
Vì vậy, lý tưởng chúng ta muốn có một kim tự tháp đẹp
nơi nó bắt đầu nhỏ và trở nên trầm trọng,

1001
00:46:05,880 --> 00:46:08,330
và điều đó có nghĩa rằng
các thanh này đều được sắp xếp.

1002
00:46:08,330 --> 00:46:11,200
Vì vậy, tôi sẽ đi trước và chọn,
Ví dụ, thuật toán của Ben

1003
00:46:11,200 --> 00:46:13,990
first-- sắp xếp chọn.

1004
00:46:13,990 --> 00:46:16,220
>> Và nhận thấy những gì nó làm.

1005
00:46:16,220 --> 00:46:18,670
Cách họ đã chọn
hình dung thuật toán này

1006
00:46:18,670 --> 00:46:22,090
là, giống như tôi là
đi bộ qua danh sách của tôi,

1007
00:46:22,090 --> 00:46:24,710
Chương trình này là đi bộ
thông qua danh sách các số,

1008
00:46:24,710 --> 00:46:28,160
nổi bật trong mỗi màu hồng
số mà nó đang tìm kiếm tại.

1009
00:46:28,160 --> 00:46:32,360
Và những gì sắp xảy ra ngay bây giờ?

1010
00:46:32,360 --> 00:46:35,154
>> Số lượng nhỏ nhất
Tôi hay Ben tìm thấy bất ngờ

1011
00:46:35,154 --> 00:46:36,820
được chuyển lên đầu danh sách.

1012
00:46:36,820 --> 00:46:40,037
Và việc thông báo họ đã đuổi
số đó là có,

1013
00:46:40,037 --> 00:46:41,120
và đó là hoàn toàn tốt đẹp.

1014
00:46:41,120 --> 00:46:42,600
Tôi đã không nhận ra rằng mức độ chi tiết.

1015
00:46:42,600 --> 00:46:44,308
Nhưng chúng ta cần phải đặt
rằng số nơi nào đó,

1016
00:46:44,308 --> 00:46:47,775
vì vậy chúng tôi chỉ cần di chuyển nó vào
chỗ mở đã được tạo ra.

1017
00:46:47,775 --> 00:46:49,900
Vì vậy, tôi sẽ tăng tốc độ này
lên, bởi vì nếu không nó

1018
00:46:49,900 --> 00:46:51,871
trở nên rất tẻ nhạt một cách nhanh chóng.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animation speed-- có chúng tôi đi.

1021
00:46:58,600 --> 00:47:01,850
Vì vậy, tại cùng một nguyên tắc
Tôi đã được áp dụng, nhưng bạn

1022
00:47:01,850 --> 00:47:06,540
có thể bắt đầu cảm thấy các thuật toán, nếu bạn
sẽ, hoặc nhìn thấy nó rõ ràng hơn một chút.

1023
00:47:06,540 --> 00:47:13,190
Và thuật toán này có tác dụng
lựa chọn các phần tử nhỏ nhất tiếp theo,

1024
00:47:13,190 --> 00:47:16,422
do đó, bạn đang đi để bắt đầu
nhìn thấy nó lên đoạn đường nối bên trái.

1025
00:47:16,422 --> 00:47:19,130
Và trên mỗi lần lặp, như tôi
đề xuất, nó làm một chút công việc ít hơn.

1026
00:47:19,130 --> 00:47:21,921
Nó không phải đi tất cả các cách
trở về đầu bên trái của danh sách,

1027
00:47:21,921 --> 00:47:23,900
vì nó đã
biết những đều được sắp xếp.

1028
00:47:23,900 --> 00:47:28,129
Vì vậy, nó loại cảm thấy như nó
tăng tốc, mặc dù mỗi bước là

1029
00:47:28,129 --> 00:47:29,420
uống cùng một lượng thời gian.

1030
00:47:29,420 --> 00:47:31,600
Chỉ là có ít hơn các bước còn lại.

1031
00:47:31,600 --> 00:47:35,240
Và bây giờ bạn có thể loại cảm nhận
thuật toán làm sạch kết thúc của nó,

1032
00:47:35,240 --> 00:47:37,040
và thực hiện nó được sắp xếp.

1033
00:47:37,040 --> 00:47:41,620
>> Vì vậy, sắp xếp chèn là hoàn tất.

1034
00:47:41,620 --> 00:47:43,600
Tôi cần phải ngẫu nhiên mảng.

1035
00:47:43,600 --> 00:47:45,940
Và nhận thấy tôi có thể chỉ
giữ ngẫu nhiên đó,

1036
00:47:45,940 --> 00:47:50,630
và chúng ta sẽ có được một xấp xỉ của
các phương pháp tương tự, sắp xếp chèn.

1037
00:47:50,630 --> 00:47:55,050
Hãy để tôi làm chậm nó xuống đây.

1038
00:47:55,050 --> 00:47:56,915
Hãy bắt đầu rằng hơn.

1039
00:47:56,915 --> 00:47:57,414
Dừng lại.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Hãy bỏ qua bốn.

1042
00:48:02,410 --> 00:48:03,200
Hiện chúng tôi đi.

1043
00:48:03,200 --> 00:48:04,190
Chọn ngẫu nhiên mảng họ.

1044
00:48:04,190 --> 00:48:05,555
Và ở đây chúng tôi go-- sắp xếp chèn.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Chơi.

1047
00:48:12,800 --> 00:48:17,280
Chú ý rằng nó đối phó với mỗi
yếu tố nó gặp ngay lập tức,

1048
00:48:17,280 --> 00:48:20,282
nhưng nếu nó thuộc về
thông báo sai chỗ

1049
00:48:20,282 --> 00:48:21,740
tất cả các công việc đó đã xảy ra.

1050
00:48:21,740 --> 00:48:24,700
Chúng tôi phải tiếp tục chuyển hơn
và nhiều yếu tố để làm cho căn phòng

1051
00:48:24,700 --> 00:48:27,340
cho một trong chúng tôi muốn đưa ra.

1052
00:48:27,340 --> 00:48:30,740
>> Vì vậy, chúng tôi đang tập trung vào các
đầu bên trái của chỉ danh sách.

1053
00:48:30,740 --> 00:48:34,460
Thông báo của chúng tôi thậm chí còn không nhìn at-- chúng tôi
đã không được nhấn mạnh trong bất cứ điều gì màu hồng

1054
00:48:34,460 --> 00:48:35,610
rẽ phải.

1055
00:48:35,610 --> 00:48:38,180
Chúng tôi chỉ đối phó với
những vấn đề như chúng tôi đi,

1056
00:48:38,180 --> 00:48:40,430
nhưng chúng tôi đang tạo ra rất nhiều
làm việc cho chính mình vẫn còn.

1057
00:48:40,430 --> 00:48:44,410
Và như vậy, nếu chúng ta tăng tốc độ này lên
bây giờ để đi đến hoàn thành,

1058
00:48:44,410 --> 00:48:46,210
nó có một cảm giác khác nhau để nó thực sự.

1059
00:48:46,210 --> 00:48:50,150
Nó chỉ tập trung vào cuối bên trái nhưng
làm một công việc ít hơn như needed--

1060
00:48:50,150 --> 00:48:53,230
loại thứ mịn
trên, sửa chữa những điều,

1061
00:48:53,230 --> 00:48:58,350
nhưng giao dịch cuối cùng với
mỗi phần tử cùng một lúc

1062
00:48:58,350 --> 00:49:07,740
cho đến khi chúng tôi nhận được là-- tốt, chúng tôi
tất cả biết cách này sẽ kết thúc,

1063
00:49:07,740 --> 00:49:09,700
vì vậy nó là một underwhelming chút có lẽ.

1064
00:49:09,700 --> 00:49:12,830
>> Nhưng danh sách trong end--
spoiler-- sẽ được sắp xếp.

1065
00:49:12,830 --> 00:49:15,300
Vì vậy, chúng ta hãy nhìn vào một người cuối cùng.

1066
00:49:15,300 --> 00:49:16,840
Chúng ta không thể bỏ qua bây giờ.

1067
00:49:16,840 --> 00:49:18,000
Chúng ta gần đến rồi.

1068
00:49:18,000 --> 00:49:19,980
Hai để đi, một đi.

1069
00:49:19,980 --> 00:49:22,680
Và thì đấy.

1070
00:49:22,680 --> 00:49:23,450
Xuất sắc.

1071
00:49:23,450 --> 00:49:27,220
>> Vì vậy bây giờ chúng ta hãy làm một cái cuối cùng,
lại ngẫu nhiên với bong bóng sắp xếp.

1072
00:49:27,220 --> 00:49:31,690
Và hãy chú ý ở đây, đặc biệt là nếu tôi làm chậm nó
xuống, điều này không giữ sà qua.

1073
00:49:31,690 --> 00:49:36,830
Nhưng nhận thấy nó chỉ làm cho cặp
loại comparisons-- các giải pháp địa phương.

1074
00:49:36,830 --> 00:49:39,050
Nhưng ngay khi chúng tôi nhận được
cuối của danh sách trong màu hồng,

1075
00:49:39,050 --> 00:49:40,690
những gì sẽ phải xảy ra một lần nữa?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Yeah, nó sẽ phải
bắt đầu lại, bởi vì nó chỉ

1078
00:49:46,830 --> 00:49:49,870
sai lầm cố định theo cặp.

1079
00:49:49,870 --> 00:49:53,120
Và đó có thể đã tiết lộ nhưng những người khác.

1080
00:49:53,120 --> 00:49:58,950
Và vì vậy nếu bạn tăng tốc độ này lên, bạn sẽ
thấy rằng, giống như tên của nó,

1081
00:49:58,950 --> 00:50:01,870
nhỏ hơn elements-- hay đúng hơn,
các elements-- lớn đang bắt đầu

1082
00:50:01,870 --> 00:50:03,740
bong bóng lên đến đỉnh, nếu bạn muốn.

1083
00:50:03,740 --> 00:50:07,380
Và các yếu tố nhỏ hơn
bắt đầu bong bóng xuống bên trái.

1084
00:50:07,380 --> 00:50:10,780
Và quả thực, đó là loại
các hiệu ứng hình ảnh là tốt.

1085
00:50:10,780 --> 00:50:17,150
Và điều này sẽ kết thúc kết thúc
theo một cách rất giống nhau, quá.

1086
00:50:17,150 --> 00:50:19,160
>> Chúng tôi không có để ở
trên một đặc biệt này.

1087
00:50:19,160 --> 00:50:21,010
Hãy để tôi mở này ngay bây giờ, quá.

1088
00:50:21,010 --> 00:50:24,040
Có một vài thuật toán sắp xếp khác
trên thế giới, một vài trong số đó

1089
00:50:24,040 --> 00:50:25,580
bị bắt ở đây.

1090
00:50:25,580 --> 00:50:29,960
Và đặc biệt là cho người học không phải là người
nhất thiết phải hình ảnh hay toán học,

1091
00:50:29,960 --> 00:50:31,930
như chúng ta đã làm trước đây, chúng ta có thể
cũng làm điều này audially

1092
00:50:31,930 --> 00:50:34,210
nếu chúng ta kết hợp một âm thanh với điều này.

1093
00:50:34,210 --> 00:50:36,990
Và chỉ để cho vui, đây là một
vài thuật toán khác nhau,

1094
00:50:36,990 --> 00:50:40,950
và một trong số họ nói riêng bạn
sẽ nhận thấy được gọi là "sắp xếp hợp nhất."

1095
00:50:40,950 --> 00:50:43,250
>> Nó thực sự là một cơ bản
thuật toán tốt hơn,

1096
00:50:43,250 --> 00:50:45,860
mà hợp nhất phân loại, một trong những
những người bạn đang về để xem,

1097
00:50:45,860 --> 00:50:49,170
không phải là thứ tự của n bình phương.

1098
00:50:49,170 --> 00:50:57,280
Đó là vào thứ tự của n lần đăng nhập của
n, mà thực sự là nhỏ hơn và do đó

1099
00:50:57,280 --> 00:50:58,940
nhanh hơn so với những người ba khác.

1100
00:50:58,940 --> 00:51:00,670
Và có một vài khác
những người ngớ ngẩn mà chúng ta sẽ thấy.

1101
00:51:00,670 --> 00:51:01,933
>> Vì vậy, ở đây chúng tôi đi với một số âm thanh.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Đây là sắp xếp chèn, vì vậy một lần nữa
nó chỉ là đối phó với các yếu tố

1104
00:51:10,490 --> 00:51:13,420
khi họ đến.

1105
00:51:13,420 --> 00:51:17,180
Đây là bong bóng sắp xếp, vì vậy nó
coi đó là những cặp cùng một lúc.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Và một lần nữa, các yếu tố lớn nhất
đang sủi bọt lên đầu trang.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Tiếp theo sắp xếp chọn.

1110
00:51:41,710 --> 00:51:45,420
Đây là thuật toán của Ben, nơi
một lần nữa anh ấy chọn lặp đi lặp lại

1111
00:51:45,420 --> 00:51:46,843
phần tử nhỏ nhất tiếp theo.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Và một lần nữa, bây giờ bạn có thể thực sự nghe
nó tăng tốc nhưng chỉ trong chừng mực

1114
00:51:53,900 --> 00:51:58,230
như nó đang làm ít hơn và ít hơn
làm việc trên mỗi lần lặp.

1115
00:51:58,230 --> 00:52:04,170
Đây là một nhanh hơn, hợp nhất phân loại,
đó là phân loại các cụm số

1116
00:52:04,170 --> 00:52:05,971
với nhau và sau đó kết hợp chúng.

1117
00:52:05,971 --> 00:52:07,720
Vì vậy look-- trái
một nửa đã được sắp xếp.

1118
00:52:07,720 --> 00:52:14,165
>> Bây giờ nó sắp xếp nửa bên phải, và
bây giờ nó sẽ kết hợp chúng thành một.

1119
00:52:14,165 --> 00:52:19,160
Đây là một cái gì đó gọi là "Gnome loại."

1120
00:52:19,160 --> 00:52:23,460
Và bạn có thể phần nào thấy rằng
nó sẽ trở lại và ra,

1121
00:52:23,460 --> 00:52:27,950
sửa chữa làm việc một chút ở đây và
đó trước khi nó tiến hành công việc mới.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Và đó là nó.

1124
00:52:33,692 --> 00:52:36,400
Có một loại, đó là
thực sự chỉ cho mục đích học tập,

1125
00:52:36,400 --> 00:52:40,980
gọi là "ngu ngốc loại", trong đó có
dữ liệu của bạn, sắp xếp nó một cách ngẫu nhiên,

1126
00:52:40,980 --> 00:52:43,350
và sau đó kiểm tra nếu nó được sắp xếp.

1127
00:52:43,350 --> 00:52:47,880
Và nếu nó không phải là, nó lại loại nó
ngẫu nhiên, kiểm tra nếu nó được sắp xếp,

1128
00:52:47,880 --> 00:52:49,440
và nếu không lặp đi lặp lại.

1129
00:52:49,440 --> 00:52:52,660
Và trên lý thuyết, xác suất
này sẽ hoàn thành,

1130
00:52:52,660 --> 00:52:54,140
nhưng sau khi khá một chút thời gian.

1131
00:52:54,140 --> 00:52:56,930
Đây không phải là nhất
hiệu quả của thuật toán.

1132
00:52:56,930 --> 00:53:02,550
Vì vậy, bất kỳ câu hỏi về những
các thuật toán cụ thể hoặc bất cứ điều gì

1133
00:53:02,550 --> 00:53:04,720
liên quan ở đó, quá?

1134
00:53:04,720 --> 00:53:09,430
>> Vâng, bây giờ chúng ta trêu chọc nhau những gì tất cả
những dòng này mà tôi đã vẽ

1135
00:53:09,430 --> 00:53:15,090
và những gì tôi giả sử máy tính
có thể làm bên dưới mui xe.

1136
00:53:15,090 --> 00:53:18,650
Tôi cho rằng tất cả những con số
Tôi giữ drawing-- họ cần phải nhận được

1137
00:53:18,650 --> 00:53:21,330
được lưu trữ ở đâu đó trong bộ nhớ.

1138
00:53:21,330 --> 00:53:24,130
Chúng tôi sẽ thoát khỏi anh chàng này ngay bây giờ, quá.

1139
00:53:24,130 --> 00:53:30,110
>> Vì vậy, một phần của bộ nhớ trong
computer-- nên RAM DIMM là

1140
00:53:30,110 --> 00:53:35,480
những gì chúng tôi đã tìm kiếm cho ngày hôm qua, kép
bộ nhớ nội tuyến module-- trông như thế này.

1141
00:53:35,480 --> 00:53:39,370
Và mỗi người trong các con chip nhỏ màu đen
là một số byte, thông thường.

1142
00:53:39,370 --> 00:53:44,380
Và sau đó các chân vàng là như
dây kết nối nó với máy tính,

1143
00:53:44,380 --> 00:53:47,521
và bảng silicon màu xanh lá cây chỉ là
những gì giữ tất cả mọi thứ lại với nhau.

1144
00:53:47,521 --> 00:53:48,770
Vì vậy, điều này thực sự nghĩa là gì?

1145
00:53:48,770 --> 00:53:53,180
Nếu tôi loại vẽ bức tranh này giống nhau,
giả sử vì đơn giản

1146
00:53:53,180 --> 00:53:55,280
mà DIMM này, kép
mô-đun bộ nhớ nội tuyến,

1147
00:53:55,280 --> 00:54:00,530
là một gigabyte bộ nhớ RAM, một gigabyte
bộ nhớ, mà là bao nhiêu tổng số byte?

1148
00:54:00,530 --> 00:54:02,100
Một gigabyte là bao nhiêu byte?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Nhiều hơn thế.

1151
00:54:06,030 --> 00:54:09,960
1.124 là kg, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega là triệu.

1153
00:54:11,730 --> 00:54:14,570
Giga là một tỷ đồng.

1154
00:54:14,570 --> 00:54:15,070
>> Tôi nói dối?

1155
00:54:15,070 --> 00:54:16,670
chúng tôi thậm chí có thể đọc các nhãn?

1156
00:54:16,670 --> 00:54:19,920
Điều này thực sự là 128
gigabyte, do đó, nó nhiều hơn.

1157
00:54:19,920 --> 00:54:22,130
Nhưng chúng tôi sẽ giả vờ này
chỉ là một gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Vì vậy, đó có nghĩa là có một tỷ
byte của bộ nhớ có sẵn cho tôi

1159
00:54:25,640 --> 00:54:29,770
hoặc 8 tỷ bit, nhưng chúng ta sẽ
để nói chuyện về các byte bây giờ,

1160
00:54:29,770 --> 00:54:30,750
tiến về phía trước.

1161
00:54:30,750 --> 00:54:36,330
>> Vì vậy, điều đó có nghĩa là đây là
một byte, đây là một byte,

1162
00:54:36,330 --> 00:54:38,680
đây là một byte,
và nếu chúng ta thực sự muốn

1163
00:54:38,680 --> 00:54:43,280
được cụ thể chúng ta sẽ phải
vẽ một tỷ hình vuông nhỏ.

1164
00:54:43,280 --> 00:54:44,320
Nhưng điều đó có nghĩa gì?

1165
00:54:44,320 --> 00:54:46,420
Vâng, hãy để tôi chỉ phóng to
ở trên hình ảnh này.

1166
00:54:46,420 --> 00:54:50,900
Nếu tôi đã có cái gì đó trông
như bây giờ điều này, đó là bốn byte.

1167
00:54:50,900 --> 00:54:53,710
>> Và vì vậy tôi có thể đặt bốn số ở đây.

1168
00:54:53,710 --> 00:54:54,990
Một hai ba bốn.

1169
00:54:54,990 --> 00:55:00,170
Hoặc tôi có thể đặt bốn chữ hoặc biểu tượng.

1170
00:55:00,170 --> 00:55:02,620
"Chào!" có thể đi ngay,
bởi vì mỗi chữ cái,

1171
00:55:02,620 --> 00:55:04,370
chúng ta đã thảo luận trước đó,
có thể được biểu

1172
00:55:04,370 --> 00:55:06,650
với tám bit hoặc ASCII hoặc một byte.

1173
00:55:06,650 --> 00:55:09,370
Vì vậy, nói cách khác, bạn có thể
đặt 8 tỉ những thứ bên trong

1174
00:55:09,370 --> 00:55:11,137
điều này một thanh bộ nhớ.

1175
00:55:11,137 --> 00:55:14,345
Bây giờ những gì nó có nghĩa là để đưa mọi thứ trở lại
sao để sao lưu trong bộ nhớ như thế này?

1176
00:55:14,345 --> 00:55:17,330
Đây là những gì một lập trình viên
sẽ gọi một "mảng".

1177
00:55:17,330 --> 00:55:21,250
Trong một chương trình máy tính, bạn không nghĩ rằng
về phần cứng cơ bản, mỗi se.

1178
00:55:21,250 --> 00:55:24,427
Bạn chỉ nghĩ về mình là có
truy cập vào một tổng tỷ byte,

1179
00:55:24,427 --> 00:55:26,010
và bạn có thể bất cứ điều gì bạn muốn với nó.

1180
00:55:26,010 --> 00:55:27,880
Nhưng để thuận tiện
nó thường hữu ích

1181
00:55:27,880 --> 00:55:31,202
để giữ đúng bộ nhớ của bạn
bên cạnh nhau như thế này.

1182
00:55:31,202 --> 00:55:33,660
Vì vậy, nếu tôi phóng to trên này--
bởi vì chúng ta chắc chắn sẽ không

1183
00:55:33,660 --> 00:55:39,310
để vẽ một tỷ squares-- chút
chúng ta hãy giả sử rằng ban này đại diện

1184
00:55:39,310 --> 00:55:40,610
rằng thanh bộ nhớ bây giờ.

1185
00:55:40,610 --> 00:55:43,800
Và tôi sẽ chỉ thu hút nhiều người như tôi
đánh dấu kết thúc cho tôi ở đây.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Vì vậy, bây giờ chúng tôi có một cây gậy
bộ nhớ trên bảng

1188
00:55:52,300 --> 00:55:56,400
đó là có một, hai, ba, bốn, năm,
sáu, một, hai, ba, bốn, năm, sáu,

1189
00:55:56,400 --> 00:56:01,130
seven-- quá 42 byte
bộ nhớ trên tổng số màn hình.

1190
00:56:01,130 --> 00:56:01,630
Cho tôi biết.

1191
00:56:01,630 --> 00:56:02,838
Vâng, đã làm số học của tôi ngay.

1192
00:56:02,838 --> 00:56:05,120
Vì vậy, 42 byte của bộ nhớ ở đây.

1193
00:56:05,120 --> 00:56:06,660
Vì vậy, điều này thực sự nghĩa là gì?

1194
00:56:06,660 --> 00:56:09,830
Vâng, một lập trình viên máy tính
sẽ thực sự nói chung

1195
00:56:09,830 --> 00:56:12,450
nghĩ về bộ nhớ này là địa chỉ.

1196
00:56:12,450 --> 00:56:16,630
Nói cách khác, mỗi một trong những
địa điểm trong bộ nhớ, trong phần cứng,

1197
00:56:16,630 --> 00:56:18,030
có một địa chỉ duy nhất.

1198
00:56:18,030 --> 00:56:22,020
>> Nó không phải là phức tạp như Một Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Thay vào đó, nó chỉ là một con số.

1200
00:56:23,830 --> 00:56:27,930
Đây là byte số không, điều này là
một, đây là hai, đây là ba,

1201
00:56:27,930 --> 00:56:30,327
và điều này là 41.

1202
00:56:30,327 --> 00:56:30,910
Chờ một chút.

1203
00:56:30,910 --> 00:56:32,510
Tôi nghĩ tôi đã nói 42 là thời điểm trước đây.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Tôi bắt đầu đếm từ số không,
vì vậy đó là thực sự chính xác.

1206
00:56:37,772 --> 00:56:40,980
Bây giờ chúng ta không phải thực sự rút ra nó
như một mạng lưới, và nếu bạn vẽ nó như một mạng lưới

1207
00:56:40,980 --> 00:56:43,520
Tôi nghĩ rằng điều này thực sự
có được một chút sai lầm.

1208
00:56:43,520 --> 00:56:46,650
Thật là một lập trình viên sẽ,
trong tâm trí riêng của mình,

1209
00:56:46,650 --> 00:56:50,310
thường nghĩ về điều này
bộ nhớ như là giống như một băng,

1210
00:56:50,310 --> 00:56:53,340
giống như một miếng băng che
mà chỉ cần đi và mãi mãi

1211
00:56:53,340 --> 00:56:54,980
hoặc cho đến khi bạn chạy ra khỏi bộ nhớ.

1212
00:56:54,980 --> 00:56:59,200
Vì vậy, một cách phổ biến hơn để vẽ
và chỉ nghĩ về bộ nhớ

1213
00:56:59,200 --> 00:57:03,710
sẽ được rằng đây là byte số không, một,
hai, ba, và sau đó dấu chấm, dấu chấm, dấu chấm.

1214
00:57:03,710 --> 00:57:07,650
Và bạn có tổng số 42 byte như vậy, thậm chí
mặc dù thể chất nó có thể thực sự

1215
00:57:07,650 --> 00:57:09,480
có một cái gì đó như thế này.

1216
00:57:09,480 --> 00:57:12,850
>> Vì vậy, nếu bây giờ bạn nghĩ về bạn
bộ nhớ như thế này, giống như một băng,

1217
00:57:12,850 --> 00:57:17,640
đây là những gì một lập trình một lần nữa
sẽ gọi một mảng của bộ nhớ.

1218
00:57:17,640 --> 00:57:20,660
Và khi bạn muốn thực sự lưu trữ
một cái gì đó trong bộ nhớ của máy tính,

1219
00:57:20,660 --> 00:57:23,290
bạn thường làm cửa hàng thứ
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Vì vậy, chúng tôi đã nói chuyện về những con số.

1221
00:57:25,010 --> 00:57:30,880
Và khi tôi muốn giải quyết vấn đề
như bốn, một, ba, hai,

1222
00:57:30,880 --> 00:57:33,820
mặc dù tôi đã chỉ vẽ
chỉ số có bốn người, một, ba,

1223
00:57:33,820 --> 00:57:39,490
hai trên bảng, máy tính sẽ
thực sự đã thiết lập này trong bộ nhớ.

1224
00:57:39,490 --> 00:57:43,347
>> Và những gì sẽ là bên cạnh
hai trong bộ nhớ của máy tính?

1225
00:57:43,347 --> 00:57:44,680
Vâng, không có câu trả lời cho điều đó.

1226
00:57:44,680 --> 00:57:45,770
Chúng tôi thực sự không biết.

1227
00:57:45,770 --> 00:57:48,200
Và do đó, miễn là
máy tính không cần nó,

1228
00:57:48,200 --> 00:57:51,440
nó không phải chăm sóc những gì tiếp theo
với những con số đó không chăm sóc về.

1229
00:57:51,440 --> 00:57:55,130
Và khi tôi nói trước đó rằng một máy tính
chỉ có thể nhìn vào một địa chỉ ở một thời gian,

1230
00:57:55,130 --> 00:57:56,170
đây là loại lý do tại sao.

1231
00:57:56,170 --> 00:57:59,490
>> Không giống như một kỷ lục
máy nghe nhạc và một đầu đọc

1232
00:57:59,490 --> 00:58:03,030
chỉ có thể nhìn một lúc nào đó
rãnh trong một bản ghi cũ-học vật lý

1233
00:58:03,030 --> 00:58:06,500
tại một thời điểm, tương tự
có thể một máy tính nhờ

1234
00:58:06,500 --> 00:58:09,810
CPU của nó và của nó
tập lệnh Intel,

1235
00:58:09,810 --> 00:58:12,480
trong có hướng dẫn
được đọc từ bộ nhớ

1236
00:58:12,480 --> 00:58:15,590
hoặc lưu vào một memory--
máy tính chỉ có thể nhìn

1237
00:58:15,590 --> 00:58:19,210
tại một địa điểm ở một time--
đôi khi một sự kết hợp của họ,

1238
00:58:19,210 --> 00:58:21,770
nhưng thực sự chỉ là một địa điểm tại một thời điểm.

1239
00:58:21,770 --> 00:58:24,770
Vì vậy, khi chúng tôi đã làm
các thuật toán khác nhau,

1240
00:58:24,770 --> 00:58:28,110
Tôi không chỉ viết trong một
vacuum-- bốn, một, ba, hai.

1241
00:58:28,110 --> 00:58:30,849
Những con số này thực sự thuộc về
ở đâu đó vật lý trong bộ nhớ.

1242
00:58:30,849 --> 00:58:32,890
Vì vậy, có chút nhỏ
transistor hoặc một số loại

1243
00:58:32,890 --> 00:58:35,840
thiết bị điện tử bên dưới
mui xe lưu trữ các giá trị.

1244
00:58:35,840 --> 00:58:40,460
>> Và trong tổng số, bao nhiêu bit là
tham gia ngay bây giờ, chỉ để được rõ ràng?

1245
00:58:40,460 --> 00:58:45,580
Vì vậy, đây là bốn byte, hoặc
bây giờ nó là tổng số 32 bit.

1246
00:58:45,580 --> 00:58:49,280
Vì vậy, thực sự có 32 số và
những sáng tác bốn điều.

1247
00:58:49,280 --> 00:58:52,070
Thậm chí còn nhiều hơn ở đây, nhưng
một lần nữa chúng tôi không quan tâm về điều đó.

1248
00:58:52,070 --> 00:58:55,120
>> Vì vậy, bây giờ hãy hỏi khác
câu hỏi sử dụng bộ nhớ,

1249
00:58:55,120 --> 00:58:57,519
bởi vì đó là lúc kết thúc
trong ngày là ở phương sai.

1250
00:58:57,519 --> 00:59:00,310
Không có vấn đề gì, chúng tôi có thể làm gì với
máy tính, vào cuối ngày

1251
00:59:00,310 --> 00:59:02,560
phần cứng vẫn là
cùng bên dưới mui xe.

1252
00:59:02,560 --> 00:59:04,670
Làm thế nào tôi có thể lưu trữ một từ trong đây?

1253
00:59:04,670 --> 00:59:09,710
Vâng, một từ trong một máy tính như
"Chào!" sẽ được lưu trữ như thế này.

1254
00:59:09,710 --> 00:59:12,300
Và nếu bạn muốn có một còn
từ, bạn có thể chỉ đơn giản

1255
00:59:12,300 --> 00:59:19,120
ghi đè lên đó và nói điều gì đó
như "hello" và cửa hàng đó ở đây.

1256
00:59:19,120 --> 00:59:23,930
>> Và như vậy ở đây, quá, contiguousness này
thực sự là một lợi thế,

1257
00:59:23,930 --> 00:59:26,530
vì một máy tính có thể chỉ
đọc từ phải sang trái.

1258
00:59:26,530 --> 00:59:28,680
Nhưng đây là một câu hỏi.

1259
00:59:28,680 --> 00:59:33,480
Trong bối cảnh của từ này,
h-e-l-l-o, dấu chấm than,

1260
00:59:33,480 --> 00:59:38,740
như thế nào có thể máy tính biết nơi
từ bắt đầu và nơi từ kết thúc?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Trong bối cảnh các số,
làm thế nào các máy tính

1263
00:59:43,800 --> 00:59:48,396
biết bao lâu chuỗi các
số là hoặc nơi nó bắt đầu?

1264
00:59:48,396 --> 00:59:50,270
Vâng, nó quay out--
và chúng ta sẽ không đi quá nhiều

1265
00:59:50,270 --> 00:59:54,970
vào mức độ detail--
máy tính di chuyển những thứ xung quanh trong bộ nhớ

1266
00:59:54,970 --> 00:59:57,800
nghĩa đen bằng cách các địa chỉ này.

1267
00:59:57,800 --> 01:00:02,080
Vì vậy, trong một máy tính, nếu bạn
viết code để lưu trữ những thứ

1268
01:00:02,080 --> 01:00:05,800
như lời nói, những gì bạn đang
thực sự làm là đánh máy

1269
01:00:05,800 --> 01:00:11,320
biểu thức có nhớ nơi ở
bộ nhớ của máy tính những lời này.

1270
01:00:11,320 --> 01:00:14,370
Vì vậy, hãy để tôi làm một rất,
ví dụ rất đơn giản.

1271
01:00:14,370 --> 01:00:18,260
>> Tôi sẽ đi trước và
mở ra một chương trình văn bản đơn giản,

1272
01:00:18,260 --> 01:00:20,330
và tôi sẽ tạo ra
một tập tin gọi là hello.c.

1273
01:00:20,330 --> 01:00:22,849
Hầu hết các thông tin này, chúng tôi
sẽ không đi vào chi tiết,

1274
01:00:22,849 --> 01:00:25,140
nhưng tôi sẽ viết thư
chương trình có cùng ngôn ngữ,

1275
01:00:25,140 --> 01:00:31,140
C. Đây là mức đáng sợ hơn,
Tôi cho rằng, so với Scratch,

1276
01:00:31,140 --> 01:00:32,490
nhưng nó rất giống nhau trong tinh thần.

1277
01:00:32,490 --> 01:00:34,364
Trong thực tế, những xoăn
loại braces-- bạn có thể của

1278
01:00:34,364 --> 01:00:37,820
nghĩ về những gì tôi chỉ cần làm như thế này.

1279
01:00:37,820 --> 01:00:39,240
>> Hãy làm điều này, thực sự.

1280
01:00:39,240 --> 01:00:45,100
Khi lá cờ màu xanh lá cây nhấp,
làm như sau.

1281
01:00:45,100 --> 01:00:50,210
Tôi muốn in ra "hello".

1282
01:00:50,210 --> 01:00:51,500
Vì vậy, đây là bây giờ giả.

1283
01:00:51,500 --> 01:00:53,000
Tôi là loại làm mờ các dòng.

1284
01:00:53,000 --> 01:00:56,750
Trong C, ngôn ngữ này tôi đang nói
về, in dòng này hello

1285
01:00:56,750 --> 01:01:01,940
thực sự trở thành "printf" với
một số dấu ngoặc đơn và dấu chấm phẩy.

1286
01:01:01,940 --> 01:01:03,480
>> Nhưng đó là ý tưởng chính xác.

1287
01:01:03,480 --> 01:01:06,730
Và điều này rất dễ sử dụng
"Khi lá cờ màu xanh lá cây nhấp" trở thành

1288
01:01:06,730 --> 01:01:10,182
các nhiều phức tạp hơn "int void main."

1289
01:01:10,182 --> 01:01:12,890
Và điều này thực sự không có bản đồ,
vì vậy tôi chỉ cần đi để bỏ qua điều đó.

1290
01:01:12,890 --> 01:01:17,210
Nhưng các dấu ngoặc nhọn giống như các
mảnh ghép cong như thế này.

1291
01:01:17,210 --> 01:01:18,700
>> Vì vậy, bạn có thể loại của đoán.

1292
01:01:18,700 --> 01:01:22,357
Thậm chí nếu bạn đã không bao giờ được lập trình trước,
những gì chương trình này có thể làm gì?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Có lẽ in chào
với một dấu chấm than.

1295
01:01:28,000 --> 01:01:29,150
>> Vì vậy, hãy cố gắng đó.

1296
01:01:29,150 --> 01:01:30,800
Tôi sẽ lưu nó.

1297
01:01:30,800 --> 01:01:34,000
Và điều này là, một lần nữa, rất
môi trường học cũ.

1298
01:01:34,000 --> 01:01:35,420
Tôi có thể không kích, tôi không thể kéo.

1299
01:01:35,420 --> 01:01:36,910
Tôi phải gõ lệnh.

1300
01:01:36,910 --> 01:01:41,320
Vì vậy, tôi muốn chạy chương trình của tôi, vì vậy
Tôi có thể làm được điều này, như hello.c.

1301
01:01:41,320 --> 01:01:42,292
Đó là các tập tin tôi chạy.

1302
01:01:42,292 --> 01:01:43,500
Nhưng chờ đợi, tôi đang thiếu một bước.

1303
01:01:43,500 --> 01:01:46,470
Điều gì đã làm chúng ta nói là một cần thiết
bước cho một ngôn ngữ như C?

1304
01:01:46,470 --> 01:01:49,470
Tôi đã chỉ viết mã nguồn
mã, nhưng những gì tôi cần?

1305
01:01:49,470 --> 01:01:50,670
Vâng, tôi cần một trình biên dịch.

1306
01:01:50,670 --> 01:01:57,670
Vì vậy, trên máy Mac của tôi ở đây, tôi có một
chương trình gọi là GCC, GNU C compiler,

1307
01:01:57,670 --> 01:02:03,990
cho phép tôi làm điều này-- lượt
mã nguồn của tôi vào, chúng tôi sẽ gọi nó,

1308
01:02:03,990 --> 01:02:04,930
mã máy.

1309
01:02:04,930 --> 01:02:10,180
>> Và tôi có thể thấy rằng,
một lần nữa, như sau, những

1310
01:02:10,180 --> 01:02:14,090
là số không và cái tôi chỉ
tạo ra từ mã nguồn của tôi,

1311
01:02:14,090 --> 01:02:15,730
tất cả các số không và những người thân.

1312
01:02:15,730 --> 01:02:17,770
Và nếu tôi muốn chạy
tôi program-- nó xảy ra

1313
01:02:17,770 --> 01:02:23,010
để được gọi là a.out cho
reasons-- lịch sử "hello".

1314
01:02:23,010 --> 01:02:24,070
Tôi có thể chạy nó một lần nữa.

1315
01:02:24,070 --> 01:02:25,690
Xin chào xin chào xin chào.

1316
01:02:25,690 --> 01:02:27,430
Và có vẻ như được làm việc.

1317
01:02:27,430 --> 01:02:31,000
>> Nhưng điều đó có nghĩa là ở đâu đó trong tôi
bộ nhớ của máy tính là những lời

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, dấu chấm than.

1319
01:02:35,279 --> 01:02:38,070
Và hóa ra, chỉ là một sang một bên,
những gì một máy tính sẽ thường

1320
01:02:38,070 --> 01:02:40,550
làm sao cho nó biết nơi
mọi thứ bắt đầu và end-- nó

1321
01:02:40,550 --> 01:02:42,460
sẽ đặt một biểu tượng đặc biệt ở đây.

1322
01:02:42,460 --> 01:02:46,064
Và ước là đặt
số không ở cuối của một từ

1323
01:02:46,064 --> 01:02:48,230
để bạn biết nó ở đâu
thực sự kết thúc, vì vậy mà bạn

1324
01:02:48,230 --> 01:02:52,750
không giữ in ra nhiều hơn và nhiều hơn nữa
nhân vật hơn bạn thực sự có ý định.

1325
01:02:52,750 --> 01:02:55,400
>> Nhưng takeaway ở đây, thậm chí
mặc dù điều này là khá phức tạp,

1326
01:02:55,400 --> 01:02:58,140
là nó cuối cùng
tương đối đơn giản.

1327
01:02:58,140 --> 01:03:04,550
Bạn đã được đưa ra sắp xếp của một băng, một trống
không gian mà bạn có thể viết thư.

1328
01:03:04,550 --> 01:03:07,150
Bạn chỉ cần phải có một
biểu tượng đặc biệt, giống như tùy tiện

1329
01:03:07,150 --> 01:03:10,316
số không, để đặt ở cuối
lời nói của bạn để máy tính biết được,

1330
01:03:10,316 --> 01:03:13,410
oh, tôi nên dừng lại sau khi in ấn
Tôi thấy các dấu chấm than.

1331
01:03:13,410 --> 01:03:16,090
Bởi vì điều tiếp theo có
là một giá trị ASCII của số không,

1332
01:03:16,090 --> 01:03:19,125
hoặc các ký tự null như
ai đó sẽ gọi nó.

1333
01:03:19,125 --> 01:03:21,500
Nhưng có loại của một vấn đề
ở đây, và chúng ta hãy quay trở lại

1334
01:03:21,500 --> 01:03:23,320
đến các số trong một khoảnh khắc.

1335
01:03:23,320 --> 01:03:28,720
Giả sử rằng tôi làm, trên thực tế,
có một dãy số,

1336
01:03:28,720 --> 01:03:30,730
và giả sử rằng
chương trình tôi đang viết là

1337
01:03:30,730 --> 01:03:34,680
giống như một cuốn sách cấp cho giáo viên
và một giáo viên lớp học.

1338
01:03:34,680 --> 01:03:38,720
Và chương trình này cho phép anh ta hoặc cô
gõ vào điểm số của học sinh

1339
01:03:38,720 --> 01:03:39,960
về câu đố.

1340
01:03:39,960 --> 01:03:43,750
Và giả sử rằng các học sinh bị rơi
100 trên bài kiểm tra đầu tiên của họ, có thể

1341
01:03:43,750 --> 01:03:49,920
như một 80 người tiếp theo, sau đó một
75, sau đó 90 trên bài kiểm tra thứ tư.

1342
01:03:49,920 --> 01:03:54,150
>> Vì vậy, tại thời điểm này trong những câu chuyện,
mảng có kích thước bốn.

1343
01:03:54,150 --> 01:03:58,470
Có bộ nhớ hoàn toàn ở những
máy tính, nhưng các mảng, có thể nói,

1344
01:03:58,470 --> 01:04:00,350
có kích thước bốn.

1345
01:04:00,350 --> 01:04:06,060
Giả sử bây giờ mà giáo viên muốn
để gán một bài kiểm tra thứ năm đến lớp.

1346
01:04:06,060 --> 01:04:08,510
Vâng, một trong những điều ông
hoặc cô ấy sẽ phải làm

1347
01:04:08,510 --> 01:04:10,650
bây giờ là lưu trữ một giá trị khác ở đây.

1348
01:04:10,650 --> 01:04:15,490
Nhưng nếu mảng giáo viên có
tạo trong chương trình này là các kích thước cho,

1349
01:04:15,490 --> 01:04:22,440
một trong những vấn đề với một mảng là
bạn không thể chỉ giữ thêm vào bộ nhớ.

1350
01:04:22,440 --> 01:04:26,470
Bởi vì những gì nếu một phần khác của
chương trình có chữ "hey" đúng không?

1351
01:04:26,470 --> 01:04:29,650
>> Nói cách khác, bộ nhớ của tôi có thể
sử dụng cho bất cứ điều gì trong một chương trình.

1352
01:04:29,650 --> 01:04:33,250
Và nếu trước tôi gõ, hey,
Tôi muốn nhập vào bốn điểm bài kiểm tra,

1353
01:04:33,250 --> 01:04:34,784
họ có thể đi ở đây và ở đây.

1354
01:04:34,784 --> 01:04:37,700
Và nếu bạn đột nhiên thay đổi tâm trí của bạn
sau đó và nói rằng tôi muốn có một bài kiểm tra thứ năm

1355
01:04:37,700 --> 01:04:40,872
điểm số, bạn không thể chỉ
đặt nó bất cứ nơi nào bạn muốn,

1356
01:04:40,872 --> 01:04:42,580
bởi vì những gì nếu điều này
bộ nhớ đang được sử dụng

1357
01:04:42,580 --> 01:04:45,990
cho một cái gì đó else-- một số chương trình khác
hoặc một số tính năng khác của chương trình

1358
01:04:45,990 --> 01:04:46,910
rằng bạn đang chạy?

1359
01:04:46,910 --> 01:04:50,650
Vì vậy, bạn phải suy nghĩ trước
làm thế nào bạn muốn để lưu trữ dữ liệu của bạn,

1360
01:04:50,650 --> 01:04:54,480
bởi vì bây giờ bạn đã vẽ
mình vào một góc kỹ thuật số.

1361
01:04:54,480 --> 01:04:57,280
>> Vì vậy, một giáo viên might thay vì
nói khi viết một chương trình

1362
01:04:57,280 --> 01:04:59,360
để lưu trữ của mình
lớp, bạn biết những gì?

1363
01:04:59,360 --> 01:05:04,180
Tôi sẽ yêu cầu,
khi viết chương trình của tôi,

1364
01:05:04,180 --> 01:05:12,070
mà tôi muốn không, một, hai, ba,
bốn, năm, sáu, tám lớp tổng số.

1365
01:05:12,070 --> 01:05:15,320
Vì vậy, một, hai, ba, bốn,
năm, sáu, bảy, tám.

1366
01:05:15,320 --> 01:05:18,612
Giáo viên có thể chỉ hơn phân bổ
bộ nhớ khi viết chương trình của mình

1367
01:05:18,612 --> 01:05:19,570
và nói, bạn biết những gì?

1368
01:05:19,570 --> 01:05:22,236
Tôi sẽ không bao giờ phải chỉ định nhiều
hơn tám câu đố trong một học kỳ.

1369
01:05:22,236 --> 01:05:23,130
Đó chỉ là điên.

1370
01:05:23,130 --> 01:05:24,470
Tôi sẽ không bao giờ phân bổ đó.

1371
01:05:24,470 --> 01:05:28,270
Vì vậy, mà cách này người đó có
linh hoạt để điểm số cửa hàng sinh viên,

1372
01:05:28,270 --> 01:05:33,010
như 75, 90, và có thể một phụ nơi
học sinh có thêm tín dụng, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Nhưng nếu giáo viên không bao giờ
sử dụng ba không gian,

1374
01:05:36,130 --> 01:05:38,860
có một takeaway trực quan ở đây.

1375
01:05:38,860 --> 01:05:41,410
Anh ta hoặc cô ấy chỉ là lãng phí thời gian.

1376
01:05:41,410 --> 01:05:44,790
Vì vậy, nói cách khác, có này
sự cân bằng chung trong lập trình

1377
01:05:44,790 --> 01:05:48,241
nơi bạn có thể phân bổ
chính xác như bộ nhớ nhiều như bạn muốn,

1378
01:05:48,241 --> 01:05:51,490
lộn ngược trong số đó là bạn siêu
efficient-- bạn không bị lãng phí

1379
01:05:51,490 --> 01:05:54,640
tại all-- nhưng nhược điểm trong đó
là gì nếu bạn thay đổi tâm trí của bạn khi

1380
01:05:54,640 --> 01:05:58,780
sử dụng các chương trình mà bạn muốn lưu trữ
nhiều dữ liệu hơn bạn dự định ban đầu.

1381
01:05:58,780 --> 01:06:03,030
>> Vì vậy, có lẽ giải pháp là, sau đó,
viết chương trình của bạn trong một cách như vậy

1382
01:06:03,030 --> 01:06:05,605
mà họ sử dụng nhiều bộ nhớ hơn
hơn là họ thực sự cần.

1383
01:06:05,605 --> 01:06:07,730
Bằng cách này bạn sẽ không
chạy vào vấn đề đó,

1384
01:06:07,730 --> 01:06:09,730
nhưng bạn đang bị lãng phí.

1385
01:06:09,730 --> 01:06:12,960
Và các bộ nhớ chương trình của bạn sử dụng,
như chúng ta đã thảo luận ngày hôm qua, ít

1386
01:06:12,960 --> 01:06:15,410
bộ nhớ có sẵn
cho các chương trình khác,

1387
01:06:15,410 --> 01:06:18,790
sớm hơn máy tính của bạn có thể làm chậm
xuống vì bộ nhớ ảo.

1388
01:06:18,790 --> 01:06:22,670
Và vì vậy giải pháp lý tưởng có thể là những gì?

1389
01:06:22,670 --> 01:06:24,610
>> Theo phân giao có vẻ xấu.

1390
01:06:24,610 --> 01:06:27,030
Qua phân giao có vẻ xấu.

1391
01:06:27,030 --> 01:06:31,120
Vì vậy, những gì có thể là một giải pháp tốt hơn?

1392
01:06:31,120 --> 01:06:32,390
Việc phân bổ lại.

1393
01:06:32,390 --> 01:06:33,590
Hãy năng động hơn.

1394
01:06:33,590 --> 01:06:37,520
Đừng ép buộc mình phải chọn một
tiên, ngay từ đầu, những gì bạn muốn.

1395
01:06:37,520 --> 01:06:41,370
Và chắc chắn không quá phân bổ,
vì sợ rằng bạn là lãng phí.

1396
01:06:41,370 --> 01:06:45,770
>> Và do đó, để đạt được mục tiêu đó, chúng tôi
cần phải ném cấu trúc dữ liệu này,

1397
01:06:45,770 --> 01:06:48,100
vậy để nói chuyện, đi.

1398
01:06:48,100 --> 01:06:51,080
Và vì vậy những gì là một lập trình
thường sẽ sử dụng

1399
01:06:51,080 --> 01:06:55,940
được cái gì gọi là không phải là một
mảng nhưng một danh sách liên kết.

1400
01:06:55,940 --> 01:07:00,860
Nói cách khác, anh ta hoặc cô ấy sẽ
bắt đầu suy nghĩ về bộ nhớ của họ

1401
01:07:00,860 --> 01:07:05,280
như là loại hình dạng của họ
có thể rút ra theo cách sau.

1402
01:07:05,280 --> 01:07:08,520
Nếu tôi muốn để lưu trữ một số trong
một program-- vì vậy nó là tháng chín,

1403
01:07:08,520 --> 01:07:12,600
Tôi đã trao cho sinh viên của tôi một bài kiểm tra; tôi muốn
để lưu trữ bài kiểm tra đầu tiên của học sinh,

1404
01:07:12,600 --> 01:07:16,220
và họ đã nhận 100 trên it-- tôi
sẽ hỏi máy tính của tôi,

1405
01:07:16,220 --> 01:07:19,540
bằng cách của chương trình tôi đã
bằng văn bản, trong một đoạn bộ nhớ.

1406
01:07:19,540 --> 01:07:22,570
Và tôi sẽ lưu trữ
số 100 trong nó, và đó là nó.

1407
01:07:22,570 --> 01:07:24,820
>> Sau đó, một vài tuần sau đó
khi tôi nhận được bài kiểm tra thứ hai của tôi,

1408
01:07:24,820 --> 01:07:27,890
và đó là thời gian để gõ
trong đó 90%, tôi sẽ

1409
01:07:27,890 --> 01:07:32,129
để yêu cầu máy tính, hey, máy tính,
Tôi có thể có một đoạn bộ nhớ?

1410
01:07:32,129 --> 01:07:34,170
Nó sẽ cung cấp cho tôi điều này
đoạn trống của bộ nhớ.

1411
01:07:34,170 --> 01:07:39,370
Tôi sẽ đưa vào các số 90,
nhưng trong chương trình của tôi bằng cách nào đó hoặc other--

1412
01:07:39,370 --> 01:07:42,100
và chúng ta sẽ không phải lo lắng về
cú pháp cho này-- tôi cần

1413
01:07:42,100 --> 01:07:44,430
bằng cách nào đó chuỗi những thứ cùng nhau.

1414
01:07:44,430 --> 01:07:47,430
Và tôi sẽ chuỗi chúng lại với nhau với
những gì trông giống như một mũi tên ở đây.

1415
01:07:47,430 --> 01:07:50,050
>> Các bài kiểm tra thứ ba mà đi lên,
Tôi sẽ nói, hey, máy tính,

1416
01:07:50,050 --> 01:07:51,680
cho tôi một đoạn bộ nhớ.

1417
01:07:51,680 --> 01:07:54,660
Và tôi sẽ đặt xuống
bất cứ điều gì nó được, như 75,

1418
01:07:54,660 --> 01:07:56,920
và tôi phải chuỗi này
nhau ngay bây giờ bằng cách nào đó.

1419
01:07:56,920 --> 01:08:00,290
đố thứ tư đến cùng, và có lẽ
đó là vào cuối học kỳ.

1420
01:08:00,290 --> 01:08:03,140
Và bởi thời điểm đó chương trình của tôi
có thể sử dụng bộ nhớ

1421
01:08:03,140 --> 01:08:05,540
khắp nơi, trên khắp cơ thể.

1422
01:08:05,540 --> 01:08:08,170
Và vì vậy chỉ cần cho đá, tôi
sẽ vẽ này ra

1423
01:08:08,170 --> 01:08:11,260
quiz-- tôi quên những gì nó là; tôi
nghĩ có lẽ 80 hoặc một cái gì đó--

1424
01:08:11,260 --> 01:08:12,500
cách trên đây.

1425
01:08:12,500 --> 01:08:15,920
>> Nhưng đó là tốt, bởi vì những bức tranh
Tôi sẽ vẽ đường này.

1426
01:08:15,920 --> 01:08:19,063
Nói cách khác, trong thực tế,
trong phần cứng của máy tính,

1427
01:08:19,063 --> 01:08:20,979
số điểm đầu tiên có thể
kết thúc ở đây vì nó là

1428
01:08:20,979 --> 01:08:22,529
đúng vào lúc bắt đầu của học kỳ.

1429
01:08:22,529 --> 01:08:25,810
Người tiếp theo có thể kết thúc ở đây
bởi vì một chút thời gian đã trôi qua

1430
01:08:25,810 --> 01:08:27,210
và chương trình tiếp tục chạy.

1431
01:08:27,210 --> 01:08:30,060
Điểm số tiếp theo, đó là
75, có thể là ở đây.

1432
01:08:30,060 --> 01:08:33,420
Và điểm cuối cùng có thể là
80, đó là ở đây.

1433
01:08:33,420 --> 01:08:38,729
>> Vì vậy, trong thực tế, thể chất, điều này có thể là
những gì bộ nhớ của máy tính của bạn trông như thế nào.

1434
01:08:38,729 --> 01:08:41,569
Nhưng điều này không phải là một tinh thần hữu ích
mô hình cho một lập trình viên máy tính.

1435
01:08:41,569 --> 01:08:44,649
Tại sao bạn nên chăm sóc nơi
quái dữ liệu của bạn là kết thúc?

1436
01:08:44,649 --> 01:08:46,200
Bạn chỉ muốn để lưu trữ dữ liệu.

1437
01:08:46,200 --> 01:08:49,390
>> Đây là loại giống như cuộc thảo luận của chúng tôi
trước đó của bản vẽ các khối lập phương.

1438
01:08:49,390 --> 01:08:52,200
Tại sao bạn quan tâm
là góc của khối lập phương

1439
01:08:52,200 --> 01:08:53,740
và làm thế nào bạn có để biến để rút ra nó?

1440
01:08:53,740 --> 01:08:54,950
Bạn chỉ muốn một khối lập phương.

1441
01:08:54,950 --> 01:08:57,359
Tương tự như vậy ở đây, bạn
chỉ muốn cuốn sách lớp.

1442
01:08:57,359 --> 01:08:59,559
Bạn chỉ muốn nghĩ về
này như là một danh sách các số.

1443
01:08:59,559 --> 01:09:01,350
Ai quan tâm làm thế nào nó
thực hiện trong phần cứng?

1444
01:09:01,350 --> 01:09:05,180
>> Vì vậy, sự trừu tượng hiện nay
là hình ảnh ở đây.

1445
01:09:05,180 --> 01:09:07,580
Đây là một danh sách liên kết, như
một lập trình viên sẽ gọi nó,

1446
01:09:07,580 --> 01:09:10,640
chừng nào bạn có một
danh sách, rõ ràng là các con số.

1447
01:09:10,640 --> 01:09:14,990
Nhưng nó được liên kết trong những bức tranh
bằng cách của những mũi tên,

1448
01:09:14,990 --> 01:09:18,510
và tất cả những mũi tên bên dưới are--
mui xe, nếu bạn tò mò,

1449
01:09:18,510 --> 01:09:23,210
nhớ lại rằng phần cứng vật lý của chúng tôi có
địa chỉ số không, một, hai, ba, bốn.

1450
01:09:23,210 --> 01:09:28,465
Tất cả các mũi tên này là giống như một bản đồ
hoặc hướng dẫn, nơi mà nếu 90 hợp-- nay

1451
01:09:28,465 --> 01:09:29,090
Tôi đã để đếm.

1452
01:09:29,090 --> 01:09:31,750
>> Zero, một, hai, ba,
bốn, năm, sáu, bảy.

1453
01:09:31,750 --> 01:09:35,640
Dường như 90 là
địa chỉ bộ nhớ số bảy.

1454
01:09:35,640 --> 01:09:38,460
Tất cả những mũi tên rất là
giống như một mẩu giấy nhỏ

1455
01:09:38,460 --> 01:09:42,439
đó là đem lại hướng đến
chương trình nói rằng theo bản đồ này

1456
01:09:42,439 --> 01:09:43,880
để có được vị trí bảy.

1457
01:09:43,880 --> 01:09:46,680
Và ở đó bạn sẽ tìm thấy
số điểm bài kiểm tra thứ hai của học sinh.

1458
01:09:46,680 --> 01:09:52,100
Trong khi đó, 75-- nếu tôi tiếp tục này,
đây là bảy, tám, chín, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> mũi tên khác này chỉ đại diện cho
một bản đồ bộ nhớ vị trí 15.

1461
01:09:59,080 --> 01:10:02,550
Nhưng một lần nữa, các lập trình viên thường làm
không quan tâm về mức độ chi tiết này.

1462
01:10:02,550 --> 01:10:05,530
Và trong hầu hết tất cả các lập trình
ngôn ngữ ngày nay, các lập trình viên

1463
01:10:05,530 --> 01:10:10,490
thậm chí sẽ không biết đâu trong bộ nhớ
những con số thực tế.

1464
01:10:10,490 --> 01:10:14,830
Tất cả các anh hay cô ấy phải quan tâm là
rằng họ bằng cách nào đó liên kết với nhau

1465
01:10:14,830 --> 01:10:18,390
trong một cấu trúc dữ liệu như thế này.

1466
01:10:18,390 --> 01:10:21,580
>> Nhưng hóa ra không
để có được quá kỹ thuật.

1467
01:10:21,580 --> 01:10:27,430
Nhưng chỉ vì chúng ta có thể có lẽ
đủ khả năng để có cuộc thảo luận này ở đây,

1468
01:10:27,430 --> 01:10:33,630
giả sử rằng chúng ta lại
vấn đề này ở đây của một mảng.

1469
01:10:33,630 --> 01:10:35,780
Chúng ta hãy xem nếu chúng ta hối tiếc sẽ ở đây.

1470
01:10:35,780 --> 01:10:42,950
Đây là 100, 90, 75, và 80.

1471
01:10:42,950 --> 01:10:44,980
>> Hãy cho tôi một thời gian ngắn làm cho tuyên bố này.

1472
01:10:44,980 --> 01:10:48,980
Đây là một mảng, và một lần nữa,
Nét đặc trưng của một mảng

1473
01:10:48,980 --> 01:10:52,400
là tất cả các dữ liệu của bạn trở lại
trở lại trở lại trong memory-- nghĩa đen

1474
01:10:52,400 --> 01:10:56,830
một byte hoặc có thể bốn byte,
một số số cố định của byte đi.

1475
01:10:56,830 --> 01:11:00,710
Trong một danh sách liên kết, mà chúng ta có thể rút ra
như thế này, bên dưới mui xe người

1476
01:11:00,710 --> 01:11:02,000
biết đâu những thứ đó là gì?

1477
01:11:02,000 --> 01:11:03,630
Nó thậm chí không cần phải chảy như thế này.

1478
01:11:03,630 --> 01:11:06,050
Một số dữ liệu có thể là
trở lại trái lên ở đó.

1479
01:11:06,050 --> 01:11:07,530
Bạn thậm chí không biết.

1480
01:11:07,530 --> 01:11:15,430
>> Và như vậy với một mảng, bạn có một
tính năng được gọi là truy cập ngẫu nhiên.

1481
01:11:15,430 --> 01:11:20,570
Và những gì các phương tiện truy cập ngẫu nhiên là
mà máy tính có thể nhảy ngay lập tức

1482
01:11:20,570 --> 01:11:22,730
đến vị trí bất kỳ trong một mảng.

1483
01:11:22,730 --> 01:11:23,580
Tại sao?

1484
01:11:23,580 --> 01:11:26,000
Bởi vì máy tính biết
rằng vị trí đầu tiên là

1485
01:11:26,000 --> 01:11:29,540
bằng không, một, hai và ba.

1486
01:11:29,540 --> 01:11:33,890
>> Và vì vậy nếu bạn muốn đi từ
yếu tố này để các phần tử tiếp theo,

1487
01:11:33,890 --> 01:11:36,099
bạn có nghĩa là, trong
tâm trí của máy tính, chỉ cần thêm một.

1488
01:11:36,099 --> 01:11:39,140
Nếu bạn muốn đi đến yếu tố thứ ba,
chỉ cần thêm cùng-- phần tử tiếp theo, chỉ cần

1489
01:11:39,140 --> 01:11:40,290
thêm một.

1490
01:11:40,290 --> 01:11:42,980
Tuy nhiên, trong phiên bản này
của câu chuyện, giả sử

1491
01:11:42,980 --> 01:11:46,080
máy tính hiện đang tìm kiếm
tại hoặc đối phó với số lượng 100.

1492
01:11:46,080 --> 01:11:49,770
Làm thế nào để bạn có thể tiếp theo
lớp trong sổ điểm?

1493
01:11:49,770 --> 01:11:52,560
>> Bạn phải mất bảy
bước, mà là tùy ý.

1494
01:11:52,560 --> 01:11:58,120
Để có được một kế tiếp, bạn phải
mất thêm tám bước để có được 15.

1495
01:11:58,120 --> 01:12:02,250
Nói cách khác, nó không phải là một
khoảng cách liên tục giữa các con số,

1496
01:12:02,250 --> 01:12:04,857
và do đó, nó chỉ mất
máy tính nhiều hơn thời gian là điểm.

1497
01:12:04,857 --> 01:12:06,940
Các máy tính có để tìm kiếm
thông qua bộ nhớ trong trật tự

1498
01:12:06,940 --> 01:12:08,990
để tìm thấy những gì bạn đang tìm kiếm.

1499
01:12:08,990 --> 01:12:14,260
>> Vì vậy, trong khi một mảng có xu hướng được một
dữ liệu nhanh structure-- vì bạn

1500
01:12:14,260 --> 01:12:17,610
có nghĩa là chỉ làm phép tính đơn giản
và có được nơi bạn muốn bằng cách thêm một,

1501
01:12:17,610 --> 01:12:21,300
cho instance-- một danh sách liên kết,
bạn hy sinh tính năng đó.

1502
01:12:21,300 --> 01:12:24,020
Bạn có thể không chỉ đi từ đầu tiên
thứ hai đến thứ ba thứ tư.

1503
01:12:24,020 --> 01:12:25,240
Bạn phải làm theo bản đồ.

1504
01:12:25,240 --> 01:12:28,160
Bạn phải mất nhiều bước
để có được những giá trị,

1505
01:12:28,160 --> 01:12:30,230
có vẻ như là thêm một chi phí.

1506
01:12:30,230 --> 01:12:35,910
Vì vậy, chúng tôi đang phải trả giá, nhưng những gì là
các tính năng mà Dan đã tìm kiếm ở đây?

1507
01:12:35,910 --> 01:12:38,110
Những gì hiện một danh sách liên kết
rõ ràng cho phép chúng ta làm,

1508
01:12:38,110 --> 01:12:40,240
đó là nguồn gốc của
Câu chuyện đặc biệt này?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Chính xác.

1511
01:12:43,830 --> 01:12:46,220
Một kích thước động đến nó.

1512
01:12:46,220 --> 01:12:48,040
Chúng tôi có thể thêm vào danh sách này.

1513
01:12:48,040 --> 01:12:51,430
Chúng tôi thậm chí có thể thu nhỏ danh sách, vì
rằng chúng ta chỉ sử dụng như là bộ nhớ

1514
01:12:51,430 --> 01:12:55,560
như chúng ta thực sự muốn và vì vậy
chúng tôi không bao giờ qua phân giao.

1515
01:12:55,560 --> 01:12:58,470
>> Bây giờ chỉ cần để được thực sự Nít-cầu kỳ,
có một chi phí ẩn.

1516
01:12:58,470 --> 01:13:01,980
Vì vậy, bạn không nên chỉ cho tôi thuyết phục
bạn biết rằng đây là một sự cân bằng hấp dẫn.

1517
01:13:01,980 --> 01:13:04,190
Có một chi phí ẩn ở đây.

1518
01:13:04,190 --> 01:13:06,550
Lợi ích, để được rõ ràng,
là chúng ta có được tính năng động.

1519
01:13:06,550 --> 01:13:10,359
Nếu tôi muốn một yếu tố khác, tôi có thể chỉ
rút ra nó và đặt một số trong đó.

1520
01:13:10,359 --> 01:13:12,150
Và sau đó tôi có thể liên kết nó
với một hình ảnh ở đây,

1521
01:13:12,150 --> 01:13:14,970
trong khi ở đây, một lần nữa, nếu tôi đã
vẽ bản thân mình vào một góc,

1522
01:13:14,970 --> 01:13:19,410
nếu cái gì khác đã được sử dụng
bộ nhớ ở đây, tôi gặp may.

1523
01:13:19,410 --> 01:13:21,700
Tôi đã vẽ bản thân mình vào một góc.

1524
01:13:21,700 --> 01:13:24,390
>> Nhưng những gì là ẩn
chi phí trong bức tranh này?

1525
01:13:24,390 --> 01:13:27,690
Nó không phải chỉ là số tiền
thời gian mà nó cần

1526
01:13:27,690 --> 01:13:29,870
để đi từ đây đến đây,
đó là bảy bước, sau đó

1527
01:13:29,870 --> 01:13:32,820
tám bước, mà là nhiều hơn một.

1528
01:13:32,820 --> 01:13:34,830
một chi phí ẩn là gì?

1529
01:13:34,830 --> 01:13:35,440
Không chỉ là thời gian.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Thông tin bổ sung
cần thiết để đạt được hình ảnh này.

1532
01:13:49,940 --> 01:13:53,210
>> Vâng, đó là bản đồ, những mẩu nhỏ của
giấy, như tôi tiếp tục miêu tả họ như.

1533
01:13:53,210 --> 01:13:55,650
Những arrows-- những không được tự do.

1534
01:13:55,650 --> 01:13:57,660
Một computer-- bạn biết
những gì một máy tính có.

1535
01:13:57,660 --> 01:13:58,790
Nó có số không và những người thân.

1536
01:13:58,790 --> 01:14:03,170
Nếu bạn muốn đại diện cho một mũi tên hay một
bản đồ hoặc một số, bạn cần một số bộ nhớ.

1537
01:14:03,170 --> 01:14:05,950
Vì vậy, các giá khác bạn
trả cho một danh sách liên kết,

1538
01:14:05,950 --> 01:14:09,070
một khoa học máy tính thông thường
tài nguyên, cũng là không gian.

1539
01:14:09,070 --> 01:14:11,710
>> Và quả thực như vậy, do đó thường,
trong cân bằng

1540
01:14:11,710 --> 01:14:15,580
trong việc thiết kế kỹ thuật phần mềm
hệ thống là thời gian và space--

1541
01:14:15,580 --> 01:14:18,596
là hai trong số các thành phần của bạn, hai
của các thành phần đắt nhất của bạn.

1542
01:14:18,596 --> 01:14:21,220
Đây là chi phí cho tôi thêm thời gian
bởi vì tôi phải làm theo bản đồ này,

1543
01:14:21,220 --> 01:14:25,730
nhưng nó cũng được chi phí cho tôi nhiều không gian hơn
bởi vì tôi phải giữ bản đồ này xung quanh.

1544
01:14:25,730 --> 01:14:28,730
Vì vậy, hy vọng, như chúng ta đã loại
thảo luận ngày hôm qua và ngày hôm nay,

1545
01:14:28,730 --> 01:14:31,720
là những lợi ích
sẽ lớn hơn chi phí.

1546
01:14:31,720 --> 01:14:33,870
>> Nhưng không có giải pháp rõ ràng ở đây.

1547
01:14:33,870 --> 01:14:35,870
Có lẽ nó là better--
một cách nhanh chóng la và dơ bẩn,

1548
01:14:35,870 --> 01:14:38,660
như Kareem đề xuất earlier--
để ném bộ nhớ vào vấn đề.

1549
01:14:38,660 --> 01:14:42,520
Chỉ cần mua thêm bộ nhớ, suy nghĩ ít hơn
khó khăn về việc giải quyết vấn đề,

1550
01:14:42,520 --> 01:14:44,595
và giải quyết nó một cách dễ dàng hơn.

1551
01:14:44,595 --> 01:14:46,720
Và quả thực trước đó, khi
chúng tôi nói chuyện về sự cân bằng,

1552
01:14:46,720 --> 01:14:49,190
nó không phải là không gian trong
máy tính và thời gian.

1553
01:14:49,190 --> 01:14:51,810
Đó là thời gian phát triển, trong đó
lại là một nguồn tài nguyên.

1554
01:14:51,810 --> 01:14:54,829
>> Vì vậy, một lần nữa, đó là hành động cân bằng này
cố gắng để quyết định những điều

1555
01:14:54,829 --> 01:14:55,870
bạn có sẵn sàng để chi tiêu?

1556
01:14:55,870 --> 01:14:57,380
Đó là ít tốn kém nhất?

1557
01:14:57,380 --> 01:15:01,040
Trong đó sản lượng các kết quả tốt hơn?

1558
01:15:01,040 --> 01:15:01,540
Yeah?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Thật.

1561
01:15:12,580 --> 01:15:15,970
Trong trường hợp này, nếu bạn
đại diện cho các số trong maps--

1562
01:15:15,970 --> 01:15:18,820
chúng được gọi bằng nhiều thứ tiếng
"Con trỏ" hoặc "Địa chỉ" -

1563
01:15:18,820 --> 01:15:20,390
đó là gấp đôi không gian.

1564
01:15:20,390 --> 01:15:24,390
Đó không nhất thiết phải là xấu như tăng gấp đôi nếu
ngay bây giờ chúng tôi chỉ lưu trữ số.

1565
01:15:24,390 --> 01:15:27,410
Giả sử chúng ta được lưu trữ
hồ sơ bệnh nhân trong một hospital--

1566
01:15:27,410 --> 01:15:30,870
nên tên Pierson của, số điện thoại,
số an sinh xã hội, bác sĩ

1567
01:15:30,870 --> 01:15:31,540
lịch sử.

1568
01:15:31,540 --> 01:15:34,160
Hộp này có thể là nhiều,
lớn hơn nhiều, trong trường hợp này

1569
01:15:34,160 --> 01:15:38,000
một con trỏ nhỏ bé, địa chỉ của
tiếp theo element-- nó không phải là một vấn đề lớn.

1570
01:15:38,000 --> 01:15:40,620
Đó là một rìa như vậy
giá nó không quan trọng.

1571
01:15:40,620 --> 01:15:43,210
Nhưng trong trường hợp này, yeah, nó tăng lên gấp đôi.

1572
01:15:43,210 --> 01:15:45,290
Câu hỏi hay.

1573
01:15:45,290 --> 01:15:47,900
>> Hãy nói về thời gian một
ít cụ thể hơn.

1574
01:15:47,900 --> 01:15:50,380
thời gian chạy là gì
tìm kiếm danh sách này?

1575
01:15:50,380 --> 01:15:53,640
Giả sử tôi muốn tìm kiếm
thông qua tất cả các lớp của học sinh,

1576
01:15:53,640 --> 01:15:55,980
và có n lớp
trong cấu trúc dữ liệu này.

1577
01:15:55,980 --> 01:15:58,830
Ở đây, chúng ta có thể mượn
từ vựng của trước đó.

1578
01:15:58,830 --> 01:16:00,890
Đây là một cấu trúc dữ liệu tuyến tính.

1579
01:16:00,890 --> 01:16:04,570
>> Big O của n là những gì cần thiết để có được
đến cuối của cấu trúc dữ liệu này,

1580
01:16:04,570 --> 01:16:08,410
whereas-- và chúng tôi đã không nhìn thấy
này before-- một mảng mang lại cho bạn

1581
01:16:08,410 --> 01:16:13,555
những gì được gọi là hằng số thời gian, có nghĩa là
một bước hoặc hai bước hoặc 10 steps--

1582
01:16:13,555 --> 01:16:14,180
không quan trọng.

1583
01:16:14,180 --> 01:16:15,440
Đó là một số cố định.

1584
01:16:15,440 --> 01:16:17,440
Nó không có gì để làm với
kích thước của mảng.

1585
01:16:17,440 --> 01:16:20,130
Và lý do đó,
một lần nữa, là truy cập ngẫu nhiên.

1586
01:16:20,130 --> 01:16:23,180
Các máy tính có thể chỉ ngay lập tức
nhảy đến một vị trí khác,

1587
01:16:23,180 --> 01:16:27,770
bởi vì chúng ta đều như nhau
khoảng cách từ tất cả mọi thứ khác.

1588
01:16:27,770 --> 01:16:29,112
Không có nghĩ như thế.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Tất cả các quyền.

1591
01:16:32,400 --> 01:16:39,230
Vì vậy, nếu tôi có thể, hãy để tôi cố gắng
vẽ hai hình ảnh chính thức.

1592
01:16:39,230 --> 01:16:42,830
Một trong rất phổ biến được biết đến như một bảng băm.

1593
01:16:42,830 --> 01:16:51,120
Vì vậy, để thúc đẩy cuộc thảo luận này,
để em suy nghĩ làm thế nào để làm điều này.

1594
01:16:51,120 --> 01:16:52,610
>> Vậy làm thế nào về điều này?

1595
01:16:52,610 --> 01:16:55,160
Giả sử rằng các vấn đề
chúng ta muốn giải quyết hiện nay

1596
01:16:55,160 --> 01:16:58,360
được thực hiện trong một dictionary--
do đó, một bó toàn bộ các từ tiếng Anh

1597
01:16:58,360 --> 01:16:59,330
hay bất cứ cái gì.

1598
01:16:59,330 --> 01:17:02,724
Và mục tiêu là để có thể trả lời
câu hỏi của form là này một từ?

1599
01:17:02,724 --> 01:17:04,640
Vì vậy, bạn muốn thực hiện
kiểm tra chính tả, chỉ

1600
01:17:04,640 --> 01:17:07,220
như một từ điển vật lý
mà bạn có thể tìm những thứ lên trong.

1601
01:17:07,220 --> 01:17:10,490
Giả sử tôi đã làm điều này với một mảng.

1602
01:17:10,490 --> 01:17:12,590
Tôi có thể làm điều này.

1603
01:17:12,590 --> 01:17:20,756
>> Và giả sử các từ này là táo
và chuối và dưa đỏ.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Và tôi không thể nghĩ rằng các loại trái cây
bắt đầu bằng d, vì vậy chúng tôi chỉ

1606
01:17:26,465 --> 01:17:27,590
sẽ có ba quả.

1607
01:17:27,590 --> 01:17:31,510
Vì vậy, đây là một mảng, và chúng tôi
lưu trữ tất cả những từ này

1608
01:17:31,510 --> 01:17:34,200
trong từ điển này là một mảng.

1609
01:17:34,200 --> 01:17:39,350
Câu hỏi đặt ra, sau đó, là làm thế nào khác
bạn có thể lưu trữ thông tin này?

1610
01:17:39,350 --> 01:17:43,160
>> Vâng, tôi là loại gian lận ở đây, bởi vì
mỗi một trong các chữ cái trong từ

1611
01:17:43,160 --> 01:17:44,490
thực sự là một byte cá nhân.

1612
01:17:44,490 --> 01:17:46,740
Vì vậy, nếu tôi thực sự muốn trở thành
nit-kén chọn, tôi thực sự cần

1613
01:17:46,740 --> 01:17:49,600
được chia nhỏ ra thành nhiều
những phần nhỏ hơn của bộ nhớ,

1614
01:17:49,600 --> 01:17:51,289
và chúng tôi có thể làm chính xác điều đó.

1615
01:17:51,289 --> 01:17:53,580
Nhưng chúng ta sẽ chạy vào
các vấn đề tương tự như trước.

1616
01:17:53,580 --> 01:17:56,674
Nếu như, như Merriam Webster hoặc Oxford
làm mỗi year-- họ thêm từ

1617
01:17:56,674 --> 01:17:59,340
đến dictionary-- chúng tôi không
nhất thiết muốn vẽ chính mình

1618
01:17:59,340 --> 01:18:00,780
vào một góc với một mảng?

1619
01:18:00,780 --> 01:18:05,710
>> Vì vậy, thay vào đó, có thể là một cách tiếp cận thông minh hơn
là đặt quả táo vào nút hoặc hộp riêng của mình,

1620
01:18:05,710 --> 01:18:11,190
như chúng ta sẽ nói, chuối, và
sau đó ở đây chúng tôi có dưa đỏ.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Và chúng tôi chuỗi những thứ cùng nhau.

1623
01:18:16,790 --> 01:18:19,980
Vì vậy, đây là mảng, và
đây là danh sách liên kết.

1624
01:18:19,980 --> 01:18:23,300
Nếu bạn có thể không hoàn toàn nhìn thấy, nó chỉ
nói "mảng", và điều này cho biết "danh sách."

1625
01:18:23,300 --> 01:18:25,780
>> Vì vậy, chúng tôi có cùng một
các vấn đề chính xác như trước,

1626
01:18:25,780 --> 01:18:28,600
nhờ đó mà chúng ta có
năng động trong danh sách liên kết của chúng tôi.

1627
01:18:28,600 --> 01:18:31,090
Nhưng chúng tôi có một từ điển khá chậm.

1628
01:18:31,090 --> 01:18:32,870
Giả sử tôi muốn tìm kiếm một từ.

1629
01:18:32,870 --> 01:18:35,430
Nó có thể đưa tôi O lớn của n
bước, bởi vì Từ này có thể

1630
01:18:35,430 --> 01:18:37,840
được tất cả các con đường ở cuối
danh sách, như dưa đỏ.

1631
01:18:37,840 --> 01:18:40,600
Và nó chỉ ra rằng
trong lập trình, sắp xếp

1632
01:18:40,600 --> 01:18:42,700
của Chén thánh của dữ liệu
cấu trúc, là một cái gì đó

1633
01:18:42,700 --> 01:18:46,620
cung cấp cho bạn liên tục
thời gian giống như một mảng

1634
01:18:46,620 --> 01:18:50,870
nhưng mà vẫn mang lại cho bạn sự năng động.

1635
01:18:50,870 --> 01:18:52,940
>> Vì vậy, chúng ta có thể có tốt nhất của cả hai thế giới?

1636
01:18:52,940 --> 01:18:55,570
Và quả thực, có cái gì đó
gọi là bảng băm

1637
01:18:55,570 --> 01:18:59,320
cho phép bạn thực hiện chính xác
rằng, mặc dù khoảng.

1638
01:18:59,320 --> 01:19:03,140
Một bảng băm là một fancier
cấu trúc dữ liệu mà chúng ta

1639
01:19:03,140 --> 01:19:06,340
có thể nghĩ đến như là
sự kết hợp của một array--

1640
01:19:06,340 --> 01:19:12,390
và tôi sẽ rút ra nó
như này-- và danh sách liên kết

1641
01:19:12,390 --> 01:19:17,310
rằng tôi sẽ vẽ như thế này ở đây.

1642
01:19:17,310 --> 01:19:19,760
>> Và cách điều này
công trình như sau.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Nếu đây now-- băm table--
là cấu trúc dữ liệu thứ ba của tôi,

1645
01:19:29,540 --> 01:19:32,590
và tôi muốn lưu trữ
từ này, tôi không

1646
01:19:32,590 --> 01:19:35,440
muốn chỉ cần lưu trữ tất cả các
Nói cách trở lại trở lại để trở lại để trở lại.

1647
01:19:35,440 --> 01:19:37,430
Tôi muốn tận dụng một số
mẩu thông tin

1648
01:19:37,430 --> 01:19:40,330
về các từ đó sẽ cho phép
tôi có được nó mà nó nhanh hơn.

1649
01:19:40,330 --> 01:19:43,666
>> Vì vậy, cho những lời táo
và chuối và dưa đỏ,

1650
01:19:43,666 --> 01:19:45,040
Tôi cố tình chọn những từ đó.

1651
01:19:45,040 --> 01:19:45,340
Tại sao?

1652
01:19:45,340 --> 01:19:47,631
Có gì loại cơ bản
khác nhau về ba?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Có gì rõ ràng?

1655
01:19:51,484 --> 01:19:52,900
Họ bắt đầu bằng chữ cái khác nhau.

1656
01:19:52,900 --> 01:19:53,900
>> Vì vậy, bạn biết những gì?

1657
01:19:53,900 --> 01:19:57,120
Thay vì đặt tất cả những lời ta trong
xô cùng, có thể nói,

1658
01:19:57,120 --> 01:20:00,390
giống như trong một danh sách lớn, tại sao không
Tôi ít nhất là cố gắng tối ưu

1659
01:20:00,390 --> 01:20:04,180
và làm cho danh sách của tôi 1/26 như lâu dài.

1660
01:20:04,180 --> 01:20:07,440
Một tối ưu hóa hấp dẫn
có thể là lý do tại sao không

1661
01:20:07,440 --> 01:20:10,650
I-- khi chèn một từ
vào cấu trúc dữ liệu này,

1662
01:20:10,650 --> 01:20:14,300
vào bộ nhớ của máy tính, tại sao
tôi không đặt tất cả các 'a' từ đây,

1663
01:20:14,300 --> 01:20:17,270
tất cả các 'b' từ đây,
và tất cả các 'c' từ đây?

1664
01:20:17,270 --> 01:20:24,610
Vì vậy, điều này kết thúc lên đặt một quả táo
ở đây, chuối ở đây, dưa đỏ ở đây,

1665
01:20:24,610 --> 01:20:25,730
và kể từ đó trở đi.

1666
01:20:25,730 --> 01:20:31,700
>> Và nếu tôi có thêm
từ like-- gì khác?

1667
01:20:31,700 --> 01:20:36,640
Táo, chuối, lê.

1668
01:20:36,640 --> 01:20:39,370
Bất cứ ai cũng nghĩ đến một loại trái cây
bắt đầu với a, b, c?

1669
01:20:39,370 --> 01:20:40,570
hoàn hảo Blueberry--.

1670
01:20:40,570 --> 01:20:43,990
Có nghĩa là sẽ kết thúc ở đây.

1671
01:20:43,990 --> 01:20:47,530
Và vì vậy chúng tôi dường như có một
nhẹ giải pháp tốt hơn,

1672
01:20:47,530 --> 01:20:50,820
bởi vì bây giờ nếu tôi muốn
để tìm kiếm cho táo, tôi

1673
01:20:50,820 --> 01:20:53,200
first-- tôi không chỉ lặn
vào cấu trúc dữ liệu của tôi.

1674
01:20:53,200 --> 01:20:54,850
Tôi không đi sâu vào bộ nhớ máy tính của tôi.

1675
01:20:54,850 --> 01:20:56,530
lần đầu tiên tôi nhìn vào các chữ cái đầu tiên.

1676
01:20:56,530 --> 01:20:58,610
>> Và đây là những gì một máy tính
nhà khoa học nói.

1677
01:20:58,610 --> 01:21:00,760
Bạn băm vào cấu trúc dữ liệu của bạn.

1678
01:21:00,760 --> 01:21:04,100
Bạn lấy đầu vào của bạn, mà trong
trường hợp này là một từ như táo.

1679
01:21:04,100 --> 01:21:07,150
Bạn phân tích nó, nhìn vào
chữ cái đầu tiên trong trường hợp này,

1680
01:21:07,150 --> 01:21:08,340
do đó băm nó.

1681
01:21:08,340 --> 01:21:10,950
Băm là một trong đó thuật ngữ chung
bạn có một cái gì đó như là đầu vào

1682
01:21:10,950 --> 01:21:12,116
và bạn sản xuất một số sản lượng.

1683
01:21:12,116 --> 01:21:15,090
Và đầu ra trong đó
trường hợp là vị trí

1684
01:21:15,090 --> 01:21:18,150
bạn muốn tìm kiếm, người đầu tiên
địa điểm, vị trí thứ hai, thứ ba.

1685
01:21:18,150 --> 01:21:22,160
Vì vậy, đầu vào là táo,
đầu ra là đầu tiên.

1686
01:21:22,160 --> 01:21:25,054
Đầu vào là chuối, các
đầu ra nên được thứ hai.

1687
01:21:25,054 --> 01:21:27,220
Đầu vào là dưa đỏ,
sản lượng nên được ba.

1688
01:21:27,220 --> 01:21:30,320
Đầu vào là quả việt quất, các
đầu ra nên lại lần hai.

1689
01:21:30,320 --> 01:21:34,010
Và đó là những gì giúp bạn lấy
các phím tắt thông qua bộ nhớ của bạn

1690
01:21:34,010 --> 01:21:39,050
để có được những lời
hoặc dữ liệu hiệu quả hơn.

1691
01:21:39,050 --> 01:21:43,330
>> Bây giờ này cắt giảm thời gian của chúng tôi có khả năng
bởi nhiều như một trong số 26,

1692
01:21:43,330 --> 01:21:45,850
bởi vì nếu bạn cho rằng bạn
có nhiều "một" lời nói như "z"

1693
01:21:45,850 --> 01:21:48,080
từ như chữ "q", mà
là không thực sự realistic--

1694
01:21:48,080 --> 01:21:50,830
bạn sẽ phải nghiêng qua
thư nhất định của alphabet--

1695
01:21:50,830 --> 01:21:53,204
nhưng điều này sẽ là một gia tăng
cách tiếp cận mà không cho phép

1696
01:21:53,204 --> 01:21:55,930
bạn để có được những lời nhanh hơn nhiều.

1697
01:21:55,930 --> 01:21:59,660
Và trong thực tế, một tinh vi
chương trình, Googles của thế giới,

1698
01:21:59,660 --> 01:22:02,180
các Facebooks của world--
họ sẽ sử dụng một bảng băm

1699
01:22:02,180 --> 01:22:03,740
cho rất nhiều mục đích khác nhau.

1700
01:22:03,740 --> 01:22:06,590
Nhưng họ sẽ không ngây thơ
chỉ cần nhìn vào các chữ cái đầu tiên

1701
01:22:06,590 --> 01:22:09,700
trong táo hoặc chuối hoặc
lê hay dưa đỏ,

1702
01:22:09,700 --> 01:22:13,420
bởi vì khi bạn có thể thấy những
danh sách vẫn có thể có được lâu dài.

1703
01:22:13,420 --> 01:22:17,130
>> Và do đó, đây vẫn có thể là loại
của linear-- để loại chậm,

1704
01:22:17,130 --> 01:22:19,980
như với O lớn của n
mà chúng ta đã thảo luận trước đó.

1705
01:22:19,980 --> 01:22:25,290
Vì vậy, những gì một thực tế bảng băm tốt sẽ
do-- nó sẽ có một mảng lớn hơn nhiều.

1706
01:22:25,290 --> 01:22:28,574
Và nó sẽ sử dụng một nhiều hơn
hàm băm phức tạp,

1707
01:22:28,574 --> 01:22:30,240
do đó nó không chỉ cần nhìn vào "một."

1708
01:22:30,240 --> 01:22:35,480
Có lẽ nó nhìn vào "a-p-p-l-e" và
bằng cách nào đó chuyển đổi những năm chữ cái

1709
01:22:35,480 --> 01:22:38,400
vào vị trí nơi
táo nên được lưu trữ.

1710
01:22:38,400 --> 01:22:42,660
Chúng tôi chỉ đơn thuần sử dụng chữ 'a'
một mình, bởi vì nó đẹp và đơn giản.

1711
01:22:42,660 --> 01:22:44,600
>> Nhưng một bảng băm, trong
Cuối cùng, bạn có thể nghĩ

1712
01:22:44,600 --> 01:22:47,270
như là một sự kết hợp của
một mảng, mỗi trong số đó

1713
01:22:47,270 --> 01:22:51,700
có một danh sách liên kết mà lý tưởng
nên càng ngắn càng tốt.

1714
01:22:51,700 --> 01:22:54,364
Và đây không phải là một giải pháp rõ ràng.

1715
01:22:54,364 --> 01:22:57,280
Trong thực tế, phần lớn việc điều chỉnh
mà đi vào bên dưới mui xe khi

1716
01:22:57,280 --> 01:22:59,654
thực hiện các loại
cấu trúc dữ liệu phức tạp

1717
01:22:59,654 --> 01:23:01,640
là bên phải là những gì
chiều dài của mảng?

1718
01:23:01,640 --> 01:23:03,250
hàm băm phải là gì?

1719
01:23:03,250 --> 01:23:04,830
Làm thế nào để bạn lưu trữ những thứ trong bộ nhớ?

1720
01:23:04,830 --> 01:23:07,249
>> Nhưng nhận ra như thế nào một cách nhanh chóng
loại này thảo luận

1721
01:23:07,249 --> 01:23:10,540
leo thang, hoặc là cho đến nay mà nó là loại
trên đầu của một người tại thời điểm này, mà

1722
01:23:10,540 --> 01:23:11,360
Ổn.

1723
01:23:11,360 --> 01:23:18,820
Nhưng chúng tôi bắt đầu, thu hồi, với sự
một cái gì đó ở mức độ thấp và điện tử.

1724
01:23:18,820 --> 01:23:20,819
Và do đó, đây lại là thế này
chủ đề trừu tượng,

1725
01:23:20,819 --> 01:23:23,610
mà một khi bạn bắt đầu để đưa cho
cấp, OK, tôi đã có it-- có

1726
01:23:23,610 --> 01:23:26,680
bộ nhớ vật lý, OK, đã nhận nó, mỗi
vị trí địa lý có địa chỉ,

1727
01:23:26,680 --> 01:23:29,910
OK, tôi đã nhận nó, tôi có thể đại diện
những địa chỉ như arrows--

1728
01:23:29,910 --> 01:23:34,650
bạn có thể nhanh chóng bắt đầu có
cuộc hội thoại phức tạp hơn

1729
01:23:34,650 --> 01:23:38,360
cuối cùng dường như được cho phép chúng tôi
để giải quyết vấn đề như tìm kiếm

1730
01:23:38,360 --> 01:23:41,620
và phân loại hiệu quả hơn.

1731
01:23:41,620 --> 01:23:44,190
Và yên tâm, too--
bởi vì tôi nghĩ rằng đây

1732
01:23:44,190 --> 01:23:48,700
là sâu nhất, chúng tôi đã đi vào một số
các chủ đề CS proper-- chúng tôi đã

1733
01:23:48,700 --> 01:23:51,880
thực hiện trong một ngày và một nửa ở đây
chỉ những gì bạn thường có thể làm hơn

1734
01:23:51,880 --> 01:23:55,520
quá trình tám tuần trong một học kỳ.

1735
01:23:55,520 --> 01:23:59,670
>> Mọi thắc mắc về những?

1736
01:23:59,670 --> 01:24:01,100
Không?

1737
01:24:01,100 --> 01:24:01,940
Tất cả các quyền.

1738
01:24:01,940 --> 01:24:05,610
Vâng, tại sao chúng ta không dừng lại ở đó,
bắt đầu ăn trưa sớm vài phút,

1739
01:24:05,610 --> 01:24:07,052
tiếp tục chỉ trong khoảng một giờ?

1740
01:24:07,052 --> 01:24:08,760
Và tôi sẽ nán lại cho
một chút với câu hỏi.

1741
01:24:08,760 --> 01:24:11,343
Sau đó, tôi sẽ phải đi
mất một vài cuộc gọi nếu đó là OK.

1742
01:24:11,343 --> 01:24:15,000
Tôi sẽ bật nhạc trong khi chờ đợi,
nhưng trưa nên quanh góc.

1743
01:24:15,000 --> 01:24:17,862