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

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: Baiklah.

3
00:00:00,460 --> 00:00:01,094
Kita kembali.

4
00:00:01,094 --> 00:00:04,260
Jadi, dalam segmen ini pengaturcaraan apa
Saya fikir kita akan lakukan adalah campuran perkara.

5
00:00:04,260 --> 00:00:06,340
Satu, melakukan sedikit
sesuatu yang tangan-on,

6
00:00:06,340 --> 00:00:08,690
walaupun menggunakan lebih suka bermain
program environment--

7
00:00:08,690 --> 00:00:11,620
satu yang demikian menggambarkan
betul-betul jenis idea

8
00:00:11,620 --> 00:00:14,220
kita telah bercakap tentang,
tetapi sedikit lebih secara rasmi.

9
00:00:14,220 --> 00:00:18,200
Kedua, melihat beberapa
cara-cara yang lebih teknikal

10
00:00:18,200 --> 00:00:21,520
bahawa programmer sebenarnya akan menyelesaikan
masalah seperti masalah mencari

11
00:00:21,520 --> 00:00:24,530
bahawa kita melihat sebelum dan
juga lebih asas

12
00:00:24,530 --> 00:00:26,020
masalah yang menarik sorting.

13
00:00:26,020 --> 00:00:28,840
>> Kami hanya menganggap dari mendapatkan pergi
bahawa buku telefon telah disusun,

14
00:00:28,840 --> 00:00:31,980
tetapi itu sahaja sebenarnya jenis yang
masalah keras dengan pelbagai cara

15
00:00:31,980 --> 00:00:32,479
untuk menyelesaikannya.

16
00:00:32,479 --> 00:00:34,366
Oleh itu, kita akan menggunakan ini sebagai
kelas masalah

17
00:00:34,366 --> 00:00:36,740
wakil perkara-perkara yang
mungkin perlu diselesaikan secara umum.

18
00:00:36,740 --> 00:00:38,980
Dan kemudian kita akan bercakap
mengenai dengan terperinci apa

19
00:00:38,980 --> 00:00:42,360
dipanggil data structures--
cara pelamun seperti senarai berkaitan

20
00:00:42,360 --> 00:00:46,290
dan jadual hash dan pokok-pokok yang
programmer akan sebenarnya

21
00:00:46,290 --> 00:00:48,890
digunakan dan biasanya menggunakan
pada papan putih untuk cat

22
00:00:48,890 --> 00:00:51,840
gambar apa yang dia
bermatlamat untuk melaksanakan

23
00:00:51,840 --> 00:00:52,980
beberapa perisian.

24
00:00:52,980 --> 00:00:55,130
>> Jadi mari kita buat tangan-pada bahagian pertama.

25
00:00:55,130 --> 00:01:00,090
Jadi hanya mendapatkan tangan anda kotor dengan
persekitaran dipanggil scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Ini adalah alat yang kita gunakan
dalam kelas ijazah pertama kami.

27
00:01:02,636 --> 00:01:04,510
Walaupun ia direka
untuk peringkat umur 12 dan ke atas,

28
00:01:04,510 --> 00:01:07,570
kita menggunakannya untuk sehingga
sebahagian daripada yang agak sedikit

29
00:01:07,570 --> 00:01:10,020
kerana ia adalah yang baik, menyeronokkan
cara grafik pengajian

30
00:01:10,020 --> 00:01:12,160
sesuatu yang sedikit tentang pengaturcaraan.

31
00:01:12,160 --> 00:01:17,600
Jadi menuju ke URL yang, di mana anda
perlu melihat halaman yang agak seperti ini,

32
00:01:17,600 --> 00:01:23,330
dan pergi ke depan dan klik
Sertai Scratch di sebelah kanan atas

33
00:01:23,330 --> 00:01:28,300
dan memilih nama pengguna dan
kata laluan dan akhirnya mendapatkan diri anda

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

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

36
00:01:32,165 --> 00:01:34,665
Saya fikir saya akan menggunakan ini sebagai
peluang pertama untuk menunjukkan ini.

37
00:01:34,665 --> 00:01:39,120
Soalan yang datang semasa rehat
tentang apa kod sebenarnya kelihatan seperti.

38
00:01:39,120 --> 00:01:41,315
Dan kita bercakap
semasa rehat mengenai C,

39
00:01:41,315 --> 00:01:45,060
khususnya-- terutamanya yang
tahap yang lebih rendah dalam bahasa yang lebih tua.

40
00:01:45,060 --> 00:01:47,750
Dan saya hanya melakukan yang cepat
Carian Google untuk mencari kod C

41
00:01:47,750 --> 00:01:51,574
untuk carian binari, algoritma yang kita
digunakan untuk mencari buku telefon sebelum ini.

42
00:01:51,574 --> 00:01:54,240
Ini contoh tertentu, sudah tentu,
tidak mencari buku telefon.

43
00:01:54,240 --> 00:01:57,840
Ia hanya mencari sejumlah besar
nombor dalam ingatan komputer.

44
00:01:57,840 --> 00:02:01,000
Tetapi jika anda hanya ingin mendapatkan visual
rasa apa pengaturcaraan sebenar

45
00:02:01,000 --> 00:02:05,370
bahasa kelihatan seperti, ia kelihatan
sesuatu yang kecil seperti ini.

46
00:02:05,370 --> 00:02:09,759
Jadi ia adalah kira-kira 20-plus,
30 atau lebih baris kod,

47
00:02:09,759 --> 00:02:12,640
tetapi perbualan kita
telah mempunyai lebih rehat

48
00:02:12,640 --> 00:02:16,000
adalah kira-kira bagaimana ini sebenarnya
mendapat berubah menjadi sifar dan satu

49
00:02:16,000 --> 00:02:19,200
dan jika anda tidak boleh hanya kembali yang
memproses dan pergi dari sifar dan satu

50
00:02:19,200 --> 00:02:20,210
belakang untuk kod.

51
00:02:20,210 --> 00:02:22,620
>> Malangnya, proses
begitu transformatif

52
00:02:22,620 --> 00:02:24,890
bahawa ia adalah lebih mudah berkata daripada dilakukan.

53
00:02:24,890 --> 00:02:29,400
Saya pergi ke hadapan dan benar-benar bertukar
program itu, Binary Search,

54
00:02:29,400 --> 00:02:32,700
ke sifar dan orang-orang yang melalui
program dipanggil pengkompil bahawa saya

55
00:02:32,700 --> 00:02:34,400
berlaku kepada ada di kanan pada Mac saya.

56
00:02:34,400 --> 00:02:37,850
Dan jika anda melihat skrin
di sini, memberi tumpuan khusus

57
00:02:37,850 --> 00:02:43,520
di Syarikat-pertengahan enam tiang sahaja,
anda hanya akan melihat sifar dan satu.

58
00:02:43,520 --> 00:02:48,290
Dan mereka adalah sifar dan orang-orang yang
mengarang tepat bahawa program pencarian.

59
00:02:48,290 --> 00:02:53,720
>> Dan sebagainya setiap sebahagian daripada lima bit,
setiap bait sifar dan satu di sini,

60
00:02:53,720 --> 00:02:57,310
mewakili beberapa arahan
biasanya dalam komputer.

61
00:02:57,310 --> 00:03:00,730
Dan sebenarnya, jika anda telah mendengar
slogan pemasaran "Intel dalam" - iaitu,

62
00:03:00,730 --> 00:03:04,610
sudah tentu, hanya bermakna anda mempunyai yang
Intel CPU atau otak dalam komputer.

63
00:03:04,610 --> 00:03:08,000
Dan apa yang bermakna untuk menjadi CPU adalah
bahawa anda mempunyai set arahan,

64
00:03:08,000 --> 00:03:08,840
boleh dikatakan.

65
00:03:08,840 --> 00:03:11,620
>> Setiap CPU di dunia, banyak
mereka dibuat oleh Intel hari ini,

66
00:03:11,620 --> 00:03:13,690
memahami yang terhad
beberapa arahan.

67
00:03:13,690 --> 00:03:18,690
Dan orang-arahan adalah tahap begitu rendah
sebagai menambah kedua-dua nombor bersama-sama,

68
00:03:18,690 --> 00:03:22,560
darabkan kedua-dua nombor bersama-sama,
bergerak sekeping data dari sini

69
00:03:22,560 --> 00:03:27,340
ke sini dalam ingatan, menyimpan ini
maklumat dari sini ke sini dalam ingatan,

70
00:03:27,340 --> 00:03:32,200
dan sebagainya forth-- begitu sangat, sangat
peringkat rendah, butiran hampir elektronik.

71
00:03:32,200 --> 00:03:34,780
Tetapi dengan orang-orang matematik
operasi ditambah

72
00:03:34,780 --> 00:03:37,410
dengan apa yang kita dibincangkan sebelum ini,
perwakilan data

73
00:03:37,410 --> 00:03:40,450
sebagai sifar dan satu, boleh
anda membina segala-galanya

74
00:03:40,450 --> 00:03:44,180
yang komputer boleh lakukan hari ini, sama ada
ia teks, grafik, muzik,

75
00:03:44,180 --> 00:03:45,580
atau sebaliknya.

76
00:03:45,580 --> 00:03:49,450
>> Jadi ini adalah sangat mudah untuk mendapatkan
hilang dalam rumpai daripada cepat.

77
00:03:49,450 --> 00:03:52,150
Dan ada banyak
cabaran sintaksis

78
00:03:52,150 --> 00:03:56,630
di mana jika anda membuat yang paling mudah,
bodoh daripada kesilapan menaip tiada program

79
00:03:56,630 --> 00:03:57,860
akan bekerja sekalipun.

80
00:03:57,860 --> 00:04:00,366
Dan sebagainya dan bukannya menggunakan
bahasa seperti C pagi ini,

81
00:04:00,366 --> 00:04:02,240
Saya fikir ia akan menjadi
lebih seronok untuk benar-benar melakukan

82
00:04:02,240 --> 00:04:04,840
sesuatu yang lebih visual, yang
manakala yang direka untuk kanak-kanak

83
00:04:04,840 --> 00:04:08,079
sebenarnya manifestasi yang sempurna
suatu program sebenar

84
00:04:08,079 --> 00:04:10,370
language-- hanya berlaku untuk
menggunakan gambar bukan teks

85
00:04:10,370 --> 00:04:11,710
untuk mewakili idea-idea.

86
00:04:11,710 --> 00:04:15,470
>> Jadi apabila anda memang mempunyai
akaun pada scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
klik butang Buat
di bahagian kiri laman web ini.

88
00:04:21,070 --> 00:04:24,620
Dan anda akan dapat melihat persekitaran seperti
yang saya kira-kira untuk melihat pada skrin saya

89
00:04:24,620 --> 00:04:26,310
di sini.

90
00:04:26,310 --> 00:04:29,350
Dan kita akan menghabiskan hanya sedikit
sedikit masa bermain di sini.

91
00:04:29,350 --> 00:04:34,080
Mari kita lihat jika kita tidak boleh semua menyelesaikan beberapa
masalah bersama-sama dengan cara yang berikut.

92
00:04:34,080 --> 00:04:39,420
>> Jadi apa yang anda akan lihat di ini
environment-- dan sebenarnya hanya membiarkan

93
00:04:39,420 --> 00:04:40,050
saya berhenti seketika.

94
00:04:40,050 --> 00:04:42,680
Adakah sesiapa yang tidak di sini?

95
00:04:42,680 --> 00:04:45,070
Bukan disini?

96
00:04:45,070 --> 00:04:45,800
OKEY.

97
00:04:45,800 --> 00:04:49,030
Jadi biarlah saya menunjukkan beberapa
ciri-ciri persekitaran ini.

98
00:04:49,030 --> 00:04:55,024
>> Jadi pada sebelah kiri atas skrin, kita
mempunyai peringkat awal, jadi untuk bercakap.

99
00:04:55,024 --> 00:04:57,440
Scratch adalah bukan sahaja nama
bahasa pengaturcaraan ini;

100
00:04:57,440 --> 00:05:00,356
ia juga nama kucing yang
anda lihat dengan lalai terdapat dalam oren.

101
00:05:00,356 --> 00:05:02,160
Dia berada di atas pentas, jadi
sama seperti saya sebut

102
00:05:02,160 --> 00:05:05,770
penyu lebih awal sebagaimana yang berada dalam
persekitaran papan putih segi empat tepat.

103
00:05:05,770 --> 00:05:09,800
Dunia ini kucing dikurung sepenuhnya
dengan yang segi empat tepat sehingga atas sana.

104
00:05:09,800 --> 00:05:12,210
>> Sementara itu, di sebelah kanan
sebelah sini, ia

105
00:05:12,210 --> 00:05:15,610
hanya kawasan skrip, yang
sabak kosong jika anda akan.

106
00:05:15,610 --> 00:05:18,590
Ini adalah di mana kita akan menulis
program kami dalam hanya seketika.

107
00:05:18,590 --> 00:05:22,935
Dan pembinaan usaha kita hendaklah
gunakan untuk menulis ini program-- teka-teki

108
00:05:22,935 --> 00:05:25,310
keping, jika anda will-- adalah
orang-orang di sini di tengah-tengah,

109
00:05:25,310 --> 00:05:27,500
dan mereka dikategorikan
oleh fungsi.

110
00:05:27,500 --> 00:05:31,000
Jadi, sebagai contoh, saya akan pergi ke hadapan
dan menunjukkan sekurang-kurangnya salah satu daripada.

111
00:05:31,000 --> 00:05:33,690
Saya akan pergi ke hadapan dan klik
kategori Kawalan sehingga atas.

112
00:05:33,690 --> 00:05:35,720
>> Jadi ini adalah kategori sehingga atas.

113
00:05:35,720 --> 00:05:39,410
Saya akan klik kategori Kawalan.

114
00:05:39,410 --> 00:05:44,020
Sebaliknya, saya akan klik Events
kategori, satu sehingga bahagian yang pertama.

115
00:05:44,020 --> 00:05:47,790
Dan jika anda ingin untuk ikut bersama-sama walaupun
seperti yang kita lakukan ini, anda agak selamat datang ke.

116
00:05:47,790 --> 00:05:52,180
Saya akan klik dan tarik ini
Yang pertama, "apabila bendera hijau diklik."

117
00:05:52,180 --> 00:05:58,410
Dan kemudian saya akan menjatuhkannya hanya
secara kasar di bahagian atas papan tulis kosong saya.

118
00:05:58,410 --> 00:06:01,450
>> Dan apa yang baik tentang Scratch
ialah sekeping teka-teki ini, apabila

119
00:06:01,450 --> 00:06:04,560
berinteraksi dengan teka-teki yang lain
keping, akan melakukan secara literal

120
00:06:04,560 --> 00:06:06,460
apa yang orang-orang keping teka-teki patut dilakukan.

121
00:06:06,460 --> 00:06:09,710
Jadi, sebagai contoh, Scratch adalah betul
kini di pertengahan dunianya.

122
00:06:09,710 --> 00:06:14,660
Saya akan pergi ke hadapan dan memilih
sekarang, katakan, kategori Motion itu,

123
00:06:14,660 --> 00:06:18,000
jika anda ingin melakukan
same-- kategori Motion.

124
00:06:18,000 --> 00:06:20,430
Dan kini melihat Saya mempunyai keseluruhannya
sekumpulan kepingan teka-teki di sini

125
00:06:20,430 --> 00:06:23,370
bahawa, sekali lagi, jenis melakukan apa yang mereka katakan.

126
00:06:23,370 --> 00:06:28,110
Dan saya akan pergi ke hadapan dan tarik dan
drop blok langkah yang betul di sini.

127
00:06:28,110 --> 00:06:31,860
>> Dan perhatikan bahawa sebaik sahaja anda
berhampiran dengan bahagian bawah "bendera hijau

128
00:06:31,860 --> 00:06:34,580
klik "butang, notis
bagaimana garisan putih muncul,

129
00:06:34,580 --> 00:06:36,950
seolah-olah ia hampir
magnet, ia mahu pergi ke sana.

130
00:06:36,950 --> 00:06:43,070
Hanya melepaskan, dan ia akan snap
bersama-sama dan bentuk akan sepadan.

131
00:06:43,070 --> 00:06:46,620
mungkin dan sekarang anda boleh hampir
meneka di mana kita akan dengan ini.

132
00:06:46,620 --> 00:06:51,570
>> Jika anda lihat pada peringkat awal yang
di sini dan melihat ke atas itu,

133
00:06:51,570 --> 00:06:55,142
anda akan melihat cahaya merah,
berhenti tanda, dan bendera hijau.

134
00:06:55,142 --> 00:06:57,100
Dan saya akan pergi ke hadapan
dan menonton screen-- saya

135
00:06:57,100 --> 00:06:58,460
hanya untuk seketika, jika anda boleh.

136
00:06:58,460 --> 00:07:01,960
Saya akan klik
hijau bendera sekarang,

137
00:07:01,960 --> 00:07:07,850
dan beliau berpindah apa yang kelihatan sebagai 10 langkah
atau 10 piksel, 10 titik, pada skrin.

138
00:07:07,850 --> 00:07:13,390
>> Dan sebagainya tidak yang menarik,
tetapi biarlah saya mencadangkan

139
00:07:13,390 --> 00:07:17,440
tanpa mengajar ini, hanya
menggunakan sendiri let intuition-- anda sendiri

140
00:07:17,440 --> 00:07:22,560
saya mencadangkan bahawa anda memikirkan bagaimana untuk
membuat Scratch berjalan kaki kanan pentas.

141
00:07:22,560 --> 00:07:28,700
Adakah dia memberi laluan kepada sebelah kanan
skrin, sepanjang jalan ke kanan.

142
00:07:28,700 --> 00:07:32,200
Biar saya memberi anda seketika
atau supaya bertumbuk dengan itu.

143
00:07:32,200 --> 00:07:37,681
Anda mungkin mahu untuk melihat dengan
pada kategori lain blok.

144
00:07:37,681 --> 00:07:38,180
Baiklah.

145
00:07:38,180 --> 00:07:41,290
Jadi, untuk mengulang, apabila kita mempunyai
bendera hijau diklik di sini

146
00:07:41,290 --> 00:07:44,850
dan bergerak 10 langkah-langkah yang yang
hanya arahan, setiap kali saya

147
00:07:44,850 --> 00:07:46,720
klik bendera hijau, apa yang berlaku?

148
00:07:46,720 --> 00:07:50,070
Well, yang menjalankan program saya.

149
00:07:50,070 --> 00:07:52,450
Jadi saya boleh melakukan ini
mungkin 10 kali secara manual,

150
00:07:52,450 --> 00:07:55,130
tetapi ini berasa sedikit
bit hackish, jadi untuk bercakap,

151
00:07:55,130 --> 00:07:57,480
di mana saya tidak benar-benar
menyelesaikan masalah tersebut.

152
00:07:57,480 --> 00:08:00,530
Saya hanya mencuba sekali lagi dan
lagi dan lagi dan lagi

153
00:08:00,530 --> 00:08:03,180
sehingga saya semacam sengaja
mencapai arahan

154
00:08:03,180 --> 00:08:05,560
yang saya sasarkan untuk dicapai lebih awal.

155
00:08:05,560 --> 00:08:08,200
>> Tetapi kita tahu daripada kami
pseudokod sebelum ini bahawa ada

156
00:08:08,200 --> 00:08:11,870
idea ini dalam pengaturcaraan gegelung,
melakukan sesuatu lagi dan lagi.

157
00:08:11,870 --> 00:08:14,888
Oleh itu, saya melihat bahawa sekumpulan anda
dihubungi untuk mendapatkan sekeping apa teka-teki?

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

159
00:08:17,870 --> 00:08:18,730
Ulangi sehingga.

160
00:08:18,730 --> 00:08:21,400
Oleh itu, kita boleh melakukan sesuatu
seperti ulangi sehingga.

161
00:08:21,400 --> 00:08:23,760
Dan apa yang anda mengulangi sehingga betul-betul?

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

163
00:08:27,720 --> 00:08:28,540
>> OKEY.

164
00:08:28,540 --> 00:08:31,974
Dan biarlah saya pergi dengan satu yang
agak lebih mudah untuk hanya seketika.

165
00:08:31,974 --> 00:08:33,140
Biar saya pergi ke hadapan dan melakukan ini.

166
00:08:33,140 --> 00:08:35,559
Perhatikan bahawa, kerana anda mungkin mempunyai
ditemui di bawah kawalan,

167
00:08:35,559 --> 00:08:38,409
terdapat blok berulang ini, yang
tidak kelihatan seperti ia yang besar.

168
00:08:38,409 --> 00:08:41,039
Ada tidak banyak ruang dalam
antara kedua-dua garisan kuning.

169
00:08:41,039 --> 00:08:43,539
Tetapi sebagai sebahagian daripada anda mungkin mempunyai
perasan, jika anda seret dan lepaskan,

170
00:08:43,539 --> 00:08:45,150
melihat bagaimana ia tumbuh untuk mengisi bentuk.

171
00:08:45,150 --> 00:08:46,274
>> Dan anda juga boleh mengasak lagi.

172
00:08:46,274 --> 00:08:48,670
Ia hanya akan terus berkembang jika
anda menyeret dan berlegar di atasnya.

173
00:08:48,670 --> 00:08:51,110
Dan saya tidak tahu apa yang
terbaik di sini, jadi mari

174
00:08:51,110 --> 00:08:54,760
saya sekurang-kurangnya mengulangi lima kali, untuk
misalnya, dan kemudian kembali ke peringkat

175
00:08:54,760 --> 00:08:56,720
dan klik bendera hijau.

176
00:08:56,720 --> 00:08:59,110
Dan kini melihat ia tidak cukup di sana.

177
00:08:59,110 --> 00:09:02,400
>> Sekarang sebahagian dari kamu dicadangkan itu, mengikut
Victoria hanya tidak, ulangi 10 kali.

178
00:09:02,400 --> 00:09:05,140
Dan yang biasanya tidak
mendapatkan dia sepanjang jalan,

179
00:09:05,140 --> 00:09:10,510
tetapi tidak akan ada yang lebih mantap
cara daripada sewenang-wenangnya memikirkan

180
00:09:10,510 --> 00:09:12,640
berapa banyak bergerak untuk membuat?

181
00:09:12,640 --> 00:09:17,680
Apa yang mungkin menjadi batu yang lebih baik
daripada berulang 10 kali menjadi?

182
00:09:17,680 --> 00:09:20,380
>> Yeah, jadi mengapa tidak melakukan sesuatu yang selama-lamanya?

183
00:09:20,380 --> 00:09:24,390
Dan sekarang mari saya bergerak sekeping teka-teki ini
dalam sana dan menghapuskan satu ini.

184
00:09:24,390 --> 00:09:28,300
Sekarang notis tidak kira di mana Scratch
bermula, dia pergi ke tepi.

185
00:09:28,300 --> 00:09:30,700
Dan bersyukur kerana MIT,
yang membuat Awal, hanya

186
00:09:30,700 --> 00:09:33,190
akan memastikan bahawa dia tidak pernah
hilang sama sekali.

187
00:09:33,190 --> 00:09:35,360
Anda sentiasa boleh merebut ekornya.

188
00:09:35,360 --> 00:09:37,680
>> Dan hanya intuitif,
mengapa dia terus bergerak?

189
00:09:37,680 --> 00:09:38,892
Apa yang sedang berlaku di sini?

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

191
00:09:41,440 --> 00:09:43,824
Dia seolah-olah telah berhenti, tetapi
kemudian jika saya mengambil dan drag

192
00:09:43,824 --> 00:09:45,240
dia terus mahu pergi ke sana.

193
00:09:45,240 --> 00:09:46,123
Kenapa begitu?

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

195
00:09:51,610 --> 00:09:54,360
Sesungguhnya, komputer adalah benar-benar
akan melakukan apa yang anda beritahu kepada lakukan.

196
00:09:54,360 --> 00:09:58,380
Jadi, jika anda memberitahu lebih awal melakukan
berikut perkara selama-lamanya, bergerak 10 langkah,

197
00:09:58,380 --> 00:10:01,860
ia akan terus pergi dan pergi
sehingga saya memukul tanda berhenti merah

198
00:10:01,860 --> 00:10:04,620
dan berhenti program ini sama sekali.

199
00:10:04,620 --> 00:10:06,610
>> Jadi, walaupun anda tidak
melakukan ini, bagaimana boleh saya

200
00:10:06,610 --> 00:10:09,510
membuat Scratch langkah lebih cepat
di skrin?

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

202
00:10:12,060 --> 00:10:13,280
Lebih langkah, bukan?

203
00:10:13,280 --> 00:10:15,710
Jadi, daripada melakukan 10
pada satu masa, mengapa tidak kita

204
00:10:15,710 --> 00:10:20,100
teruskan dan mengubahnya supaya-
apa yang anda akan propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Jadi sekarang saya akan klik hijau
bendera, dan sesungguhnya, dia pergi dengan pantas.

206
00:10:24,410 --> 00:10:27,180
>> Dan ini, sudah tentu, adalah hanya
manifestasi animasi.

207
00:10:27,180 --> 00:10:28,060
Apakah animasi?

208
00:10:28,060 --> 00:10:33,090
Ia hanya menunjukkan anda seorang manusia
seluruh sekumpulan imej masih benar-benar,

209
00:10:33,090 --> 00:10:34,160
benar-benar, benar-benar cepat.

210
00:10:34,160 --> 00:10:36,500
Dan jadi jika kita hanya memberitahu
beliau untuk bergerak lebih langkah-langkah,

211
00:10:36,500 --> 00:10:39,750
kami hanya mempunyai kesan yang sama adalah untuk
perubahan di mana dia berada di atas skrin

212
00:10:39,750 --> 00:10:42,900
semua unit yang lebih cepat setiap masa.

213
00:10:42,900 --> 00:10:46,454
>> Sekarang cabaran seterusnya yang saya mencadangkan
adalah untuk mempunyai dia melantun dari tepi.

214
00:10:46,454 --> 00:10:49,120
Dan tanpa mengetahui apa teka-teki
keping exist-- kerana ia adalah baik

215
00:10:49,120 --> 00:10:53,030
jika anda tidak sampai ke
peringkat challenge-- apa

216
00:10:53,030 --> 00:10:54,280
yang anda mahu lakukan intuitif?

217
00:10:54,280 --> 00:10:58,030
Bagaimana kita akan dia bangkit semula dan
sebagainya, antara kiri dan kanan?

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
Oleh itu, kita perlu beberapa jenis
keadaan, dan kami

221
00:11:05,680 --> 00:11:09,710
seolah-olah mempunyai conditional, jadi untuk
berkata-kata, di bawah kategori Kawalan.

222
00:11:09,710 --> 00:11:14,110
Yang mana blok ini
kita mungkin mahu?

223
00:11:14,110 --> 00:11:15,200
Ya, mungkin "jika, kemudian."

224
00:11:15,200 --> 00:11:18,780
Jadi notis bahawa di antara blok kuning
kami ada di sini, ada ini "jika"

225
00:11:18,780 --> 00:11:23,920
atau ini "jika, lain" blok yang akan
membolehkan kita untuk membuat keputusan untuk melakukan ini

226
00:11:23,920 --> 00:11:25,000
atau untuk berbuat demikian.

227
00:11:25,000 --> 00:11:27,380
walaupun dan anda dapat bersarang mereka
untuk melakukan pelbagai perkara.

228
00:11:27,380 --> 00:11:34,910
Atau jika anda tidak pergi sini lagi,
pergi ke depan untuk kategori Sensing yang

229
00:11:34,910 --> 00:11:39,612
dan- mari kita lihat jika ia di sini.

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

231
00:11:43,050 --> 00:11:52,050
>> Jadi apa blok mungkin dapat membantu di sini
untuk mengesan jika dia pentas?

232
00:11:52,050 --> 00:11:56,740
Ya, perasan bahawa beberapa blok-blok
boleh parametrized, jadi untuk bercakap.

233
00:11:56,740 --> 00:12:00,706
Mereka boleh bentuk disesuaikan, tidak
tidak seperti HTML semalam dengan sifat-sifat,

234
00:12:00,706 --> 00:12:03,330
di mana mereka sifat-sifat jenis
menyesuaikan tingkah laku tag.

235
00:12:03,330 --> 00:12:08,880
Begitu juga di sini, saya boleh merebut menyentuh ini
blok dan perubahan dan bertanya soalan,

236
00:12:08,880 --> 00:12:11,500
yang anda menyentuh tetikus
penunjuk seperti kursor

237
00:12:11,500 --> 00:12:13,250
atau yang anda menyentuh tepi?

238
00:12:13,250 --> 00:12:15,210
>> Jadi biarlah saya masuk dan melakukan ini.

239
00:12:15,210 --> 00:12:18,130
Saya akan zum keluar untuk seketika.

240
00:12:18,130 --> 00:12:21,320
Biar saya merebut sekeping teka-teki ini
di sini, teka-teki sekeping ini,

241
00:12:21,320 --> 00:12:24,570
dan saya akan campurkannya
mereka untuk hanya seketika.

242
00:12:24,570 --> 00:12:27,620
Saya akan bergerak ini,
menukar ini ke tepi menyentuh,

243
00:12:27,620 --> 00:12:38,590
dan saya akan gerakan melakukan ini.

244
00:12:38,590 --> 00:12:40,490
Jadi di sini adalah beberapa bahan-bahan.

245
00:12:40,490 --> 00:12:42,570
Saya rasa saya telah mendapat segala-galanya yang saya mahu.

246
00:12:42,570 --> 00:12:47,710
>> Adakah seseorang suka untuk mencadangkan bagaimana saya
boleh menyambung ini mungkin atas ke bawah

247
00:12:47,710 --> 00:12:52,020
untuk menyelesaikan masalah yang mempunyai
Scratch langkah kanan ke kiri ke kanan untuk

248
00:12:52,020 --> 00:12:57,020
kiri ke kanan ke kiri, setiap
masa hanya memantul dari dinding?

249
00:12:57,020 --> 00:12:58,050
Apa yang saya mahu lakukan?

250
00:12:58,050 --> 00:13:01,097
Blok yang perlu saya menyambung kepada
"Bendera apabila hijau klik pertama"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, jadi mari kita mulakan dengan "selama-lamanya."

253
00:13:06,200 --> 00:13:07,170
Apa yang berlaku di dalam yang akan datang?

254
00:13:07,170 --> 00:13:10,290
Orang lain.

255
00:13:10,290 --> 00:13:11,850
OK, bergerak langkah.

256
00:13:11,850 --> 00:13:12,350
Baiklah.

257
00:13:12,350 --> 00:13:14,470
Kemudian apa?

258
00:13:14,470 --> 00:13:15,120
Sebab itu jika.

259
00:13:15,120 --> 00:13:17,720
Dan perhatikan, walaupun ia kelihatan
diapit bersama-sama ketat,

260
00:13:17,720 --> 00:13:19,500
ia hanya akan berkembang untuk mengisi.

261
00:13:19,500 --> 00:13:21,500
Ia hanya akan melompat di mana saya mahu ia.

262
00:13:21,500 --> 00:13:25,920
>> Dan apa yang saya meletakkan antara
jika dan ketika itu?

263
00:13:25,920 --> 00:13:27,180
Mungkin "jika menyentuh kelebihan."

264
00:13:27,180 --> 00:13:31,800
Dan notis, sekali lagi, ia terlalu besar
untuk itu, tetapi ia akan berkembang untuk mengisi.

265
00:13:31,800 --> 00:13:35,002
Dan kemudian berpaling 15 darjah?

266
00:13:35,002 --> 00:13:35,710
Berapa banyak darjah?

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

268
00:13:38,800 --> 00:13:41,196
Ya, jadi 180 akan berputar
saya sepanjang jalan di sekitar.

269
00:13:41,196 --> 00:13:42,570
Jadi mari kita lihat jika saya mendapat hak ini.

270
00:13:42,570 --> 00:13:43,930
Biar saya zum keluar.

271
00:13:43,930 --> 00:13:45,130
>> Biar saya seret Scratch up.

272
00:13:45,130 --> 00:13:50,030
Jadi dia sedikit diputarbelitkan
sekarang, tetapi itulah denda.

273
00:13:50,030 --> 00:13:52,231
Bagaimana saya boleh menetapkan semula beliau dengan mudah?

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

275
00:13:59,879 --> 00:14:01,045
Saya akan menipu sedikit.

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

277
00:14:04,074 --> 00:14:05,990
Jadi, saya menambah satu lagi
blok, hanya untuk menjadi jelas.

278
00:14:05,990 --> 00:14:08,424
Saya mahu dia menunjukkan 90 darjah
ke kanan secara lalai,

279
00:14:08,424 --> 00:14:10,840
jadi saya hanya akan beritahu dia
untuk berbuat demikian pengaturcaraan.

280
00:14:10,840 --> 00:14:11,632
Dan di sini kita pergi.

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

282
00:14:14,740 --> 00:14:15,740
Kita seolah-olah telah melakukannya.

283
00:14:15,740 --> 00:14:19,980
Ia sedikit pelik, kerana
dia berjalan terbalik.

284
00:14:19,980 --> 00:14:21,250
Mari kita memanggil bahawa pepijat.

285
00:14:21,250 --> 00:14:22,120
Itulah kesilapan.

286
00:14:22,120 --> 00:14:27,320
bug A adalah satu kesilapan dalam program, yang
ralat logik bahawa saya, manusia, yang dibuat.

287
00:14:27,320 --> 00:14:28,985
Mengapa dia akan terbalik?

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

289
00:14:33,560 --> 00:14:35,250
Adakah MIT skru sehingga atau tidak saya?

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

291
00:14:38,840 --> 00:14:42,550
>> Ya, maksud saya, ia bukan MIT
kesalahan. Mereka memberikan saya sekeping teka-teki

292
00:14:42,550 --> 00:14:44,970
yang mengatakan menghidupkan beberapa beberapa darjah.

293
00:14:44,970 --> 00:14:47,672
Dan pada cadangan Victoria,
Saya beralih 180 darjah,

294
00:14:47,672 --> 00:14:48,880
yang merupakan gerak hati yang betul.

295
00:14:48,880 --> 00:14:53,700
Tetapi beralih 180 darjah secara literal
ertinya berpaling 180 darjah,

296
00:14:53,700 --> 00:14:55,860
dan itu tidak benar-benar
apa yang saya mahu, nampaknya.

297
00:14:55,860 --> 00:14:58,026
Kerana sekurang-kurangnya dia dalam
dunia ini dua dimensi,

298
00:14:58,026 --> 00:15:00,740
supaya perubahan yang sedang berlaku
untuk flip dia terbalik.

299
00:15:00,740 --> 00:15:04,030
>> Saya mungkin mahu menggunakan apa blok
sebaliknya, berdasarkan apa yang anda lihat di sini?

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

301
00:15:11,890 --> 00:15:14,790
Bagaimana kita boleh menetapkan ini?

302
00:15:14,790 --> 00:15:18,380
Ya, jadi kami akan menunjukkan
ke arah yang bertentangan.

303
00:15:18,380 --> 00:15:22,300
Dan sebenarnya walaupun itulah
tidak akan mencukupi,

304
00:15:22,300 --> 00:15:26,410
kerana kita hanya kod keras
untuk menunjuk kiri atau kanan.

305
00:15:26,410 --> 00:15:27,920
>> Anda tahu apa yang boleh kita lakukan?

306
00:15:27,920 --> 00:15:30,160
Ia kelihatan seperti kita mempunyai
blok mudah di sini.

307
00:15:30,160 --> 00:15:32,987
Jika saya zum masuk, lihat
sesuatu yang kita suka di sini?

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

309
00:15:36,120 --> 00:15:40,020
Supaya ia kelihatan seperti MIT mempunyai
abstraksi dibina di sini.

310
00:15:40,020 --> 00:15:45,440
Blok ini seolah-olah menjadi bersamaan
yang blok lain, kata ganda?

311
00:15:45,440 --> 00:15:49,510
>> Ini satu blok seolah-olah menjadi bersamaan
untuk ketiga-tiga mereka ini seluruh blok

312
00:15:49,510 --> 00:15:50,880
yang kita ada di sini.

313
00:15:50,880 --> 00:15:54,670
Jadi ternyata saya boleh memudahkan saya
program dengan menyingkirkan semua itu

314
00:15:54,670 --> 00:15:58,270
dan hanya meletakkan ini di sini.

315
00:15:58,270 --> 00:16:01,620
Dan kini dia masih sedikit
kereta, dan itulah denda buat masa sekarang.

316
00:16:01,620 --> 00:16:03,370
Kami akan meninggalkan yang berkenaan.

317
00:16:03,370 --> 00:16:06,000
Tetapi program saya adalah lebih
mudah, dan ini juga,

318
00:16:06,000 --> 00:16:09,060
akan menjadi wakil
satu gol dalam programming--

319
00:16:09,060 --> 00:16:13,430
adalah untuk membuat pilihan kod anda sebagai
mudah, padat yang mungkin,

320
00:16:13,430 --> 00:16:15,650
namun masih lagi sebagai
boleh dibaca yang mungkin.

321
00:16:15,650 --> 00:16:20,310
Anda tidak mahu untuk membuat ia begitu ringkas
bahawa ia sukar untuk difahami.

322
00:16:20,310 --> 00:16:22,826
>> Tetapi notis saya digantikan
tiga blok dengan satu,

323
00:16:22,826 --> 00:16:24,200
dan itulah boleh dikatakan satu perkara yang baik.

324
00:16:24,200 --> 00:16:27,280
Saya telah disarikan jauh tanggapan
memeriksa sama ada anda

325
00:16:27,280 --> 00:16:29,120
di pinggir dengan hanya satu blok.

326
00:16:29,120 --> 00:16:31,520
Sekarang kita boleh bersenang-senang dengan ini, sebenarnya.

327
00:16:31,520 --> 00:16:35,790
Ini tidak menambah begitu banyak
nilai intelek tetapi nilai suka bermain.

328
00:16:35,790 --> 00:16:39,730
Saya akan pergi ke hadapan
dan merebut bunyi ini di sini.

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

330
00:16:42,900 --> 00:16:46,420
Jadi biarlah saya pergi ke hadapan, dan biarlah saya
menghentikan program untuk seketika.

331
00:16:46,420 --> 00:16:52,070
Saya akan merakam berikut,
membenarkan akses kepada mikrofon saya.

332
00:16:52,070 --> 00:16:53,181
>> Di sini kita pergi.

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

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

335
00:16:58,710 --> 00:17:01,140
Mari kita cuba ini lagi.

336
00:17:01,140 --> 00:17:02,279
Di sini kita pergi.

337
00:17:02,279 --> 00:17:03,570
OK, saya mencatatkan perkara yang salah.

338
00:17:03,570 --> 00:17:04,580
Di sini kita pergi.

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

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

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

342
00:17:08,800 --> 00:17:09,300
Baiklah.

343
00:17:09,300 --> 00:17:10,791
Sekarang saya perlu untuk menghilangkan itu.

344
00:17:10,791 --> 00:17:11,290
Baiklah.

345
00:17:11,290 --> 00:17:13,950
>> Jadi sekarang saya mempunyai
rakaman hanya "ouch."

346
00:17:13,950 --> 00:17:18,040
Jadi sekarang saya akan pergi ke
hadapan dan memanggil ini "ouch."

347
00:17:18,040 --> 00:17:20,270
Saya akan kembali
untuk skrip saya, dan kini

348
00:17:20,270 --> 00:17:25,460
notis ada blok ini yang dinamakan
memainkan bunyi "meow" atau memainkan bunyi "ouch."

349
00:17:25,460 --> 00:17:28,920
Saya akan tarik ini, dan di mana
perlu saya meletakkan ini untuk kesan lucu?

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

351
00:17:31,740 --> 00:17:37,860
Yeah, jadi sekarang ia adalah jenis
kereta, kerana sekarang ini block--

352
00:17:37,860 --> 00:17:42,050
melihat bagaimana ini "jika di pinggir,
melantun "adalah jenis yang serba lengkap.

353
00:17:42,050 --> 00:17:43,704
Jadi saya perlu untuk menetapkan ini.

354
00:17:43,704 --> 00:17:44,870
Biar saya pergi ke hadapan dan melakukan ini.

355
00:17:44,870 --> 00:17:48,630
Biar saya menghilangkan ini dan kembali
kepada asal kita, lebih sengaja

356
00:17:48,630 --> 00:17:49,870
fungsi.

357
00:17:49,870 --> 00:18:01,080
Jadi "jika menyentuh tepi, kemudian" Saya hendak
untuk menghidupkan, sebagai Victoria dicadangkan,

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

359
00:18:02,480 --> 00:18:05,497
Dan saya mahu bermain
bunyi "ouch" di sana?

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

361
00:18:11,800 --> 00:18:15,580
>> Yeah, notis itu di luar
bahawa blok kuning.

362
00:18:15,580 --> 00:18:17,680
Jadi ini, juga, akan menjadi
bug, tetapi saya dapati ia.

363
00:18:17,680 --> 00:18:21,290
Jadi, saya akan tarik di sini,
dan notis kini ia di dalam "jika."

364
00:18:21,290 --> 00:18:24,250
Oleh itu, "jika" adalah seperti ini
daripada seperti lengan seperti hapuskanlah

365
00:18:24,250 --> 00:18:26,260
yang hanya akan
melakukan apa yang di dalamnya.

366
00:18:26,260 --> 00:18:30,216
Jadi sekarang jika saya zum keluar di
risiko annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> KOMPUTER: Aduh, aduh, aduh.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: Dan ia
hanya akan berterusan selama-lamanya.

370
00:18:39,910 --> 00:18:44,160
Kini hanya untuk mempercepatkan perkara
di sini, saya pergi ke hadapan dan membuka,

371
00:18:44,160 --> 00:18:50,460
mari kita iaitu- biarlah saya pergi ke beberapa
barangan saya sendiri dari kelas.

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

373
00:18:53,000 --> 00:19:00,220
Dan biarlah saya membuka, katakan, ini
satu yang dibuat oleh salah seorang felo pengajaran kami

374
00:19:00,220 --> 00:19:01,500
beberapa tahun yang lalu.

375
00:19:01,500 --> 00:19:04,732
Jadi sebahagian daripada anda mungkin ingat
permainan ini dari tadi,

376
00:19:04,732 --> 00:19:05,940
dan ia sebenarnya luar biasa.

377
00:19:05,940 --> 00:19:08,190
Walaupun kita telah melakukan perkara yang
paling mudah program sekarang,

378
00:19:08,190 --> 00:19:09,980
mari kita mempertimbangkan apa ini
sebenarnya kelihatan seperti.

379
00:19:09,980 --> 00:19:10,650
Biar saya tekan bermain.

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

381
00:19:14,210 --> 00:19:18,980
>> Jadi, dalam permainan ini, kita mempunyai
katak, dan menggunakan anak panah keys--

382
00:19:18,980 --> 00:19:23,340
dia mengambil langkah-langkah yang lebih besar daripada yang saya remember--
Saya mempunyai kawalan ke atas katak ini.

383
00:19:23,340 --> 00:19:29,630
Dan matlamatnya adalah untuk mendapatkan di seluruh sibuk
jalan tanpa berjalan ke kereta.

384
00:19:29,630 --> 00:19:34,735
Dan mari kita see-- jika saya pergi di sini, saya
perlu menunggu log untuk menatal dengan.

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

386
00:19:38,130 --> 00:19:39,274
Ini berasa seperti pepijat.

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

388
00:19:42,240 --> 00:19:43,495
Ini adalah jenis pepijat.

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

390
00:19:45,980 --> 00:19:46,480
Baiklah.

391
00:19:46,480 --> 00:19:51,550
Saya pada ini di sini,
sana, dan kemudian anda menyimpan

392
00:19:51,550 --> 00:19:54,100
usaha sehingga anda mendapatkan semua
katak-katak pad lily.

393
00:19:54,100 --> 00:19:55,920
Sekarang ini mungkin kelihatan
semua lebih kompleks,

394
00:19:55,920 --> 00:19:57,840
tetapi mari kita cuba untuk memecahkan
ini turun mental

395
00:19:57,840 --> 00:20:00,040
dan secara lisan ke dalam blok komponen.

396
00:20:00,040 --> 00:20:03,910
Jadi ada mungkin teka-teki
sekeping yang kita tidak pernah melihat lagi

397
00:20:03,910 --> 00:20:07,440
tetapi itu menjawab ketukan kekunci,
kepada perkara-perkara saya memukul pada papan kekunci.

398
00:20:07,440 --> 00:20:11,660
>> Jadi ada mungkin beberapa jenis
blok yang mengatakan, jika kunci sama sehingga,

399
00:20:11,660 --> 00:20:15,965
kemudian melakukan sesuatu dengan Scratch--
mungkin bergerak 10 langkah cara ini.

400
00:20:15,965 --> 00:20:20,240
Jika kunci ke bawah ditekan, bergerak 10 langkah
cara ini, atau kekunci kiri, bergerak 10 langkah

401
00:20:20,240 --> 00:20:21,710
cara ini, 10 tidak perlu pergi itu.

402
00:20:21,710 --> 00:20:23,644
Saya jelas bertukar kucing menjadi katak.

403
00:20:23,644 --> 00:20:26,060
Jadi itu hanya di mana
pakaian, panggilan Scratch it-- kita

404
00:20:26,060 --> 00:20:28,440
hanya diimport gambar katak.

405
00:20:28,440 --> 00:20:29,570
>> Tetapi apa lagi yang berlaku?

406
00:20:29,570 --> 00:20:32,794
Apa yang lain-lain talian kod,
apa kepingan teka-teki yang lain

407
00:20:32,794 --> 00:20:35,460
lakukan Blake, rakan-rakan pengajaran kami,
digunakan dalam program ini, nampaknya?

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

409
00:20:38,320 --> 00:20:42,730
Apa yang membuat segala-galanya move--
apa program bina?

410
00:20:42,730 --> 00:20:44,950
>> Gerakan, sure-- jadi
menggerakkan blok, yang pasti.

411
00:20:44,950 --> 00:20:49,330
Dan apa yang blok langkah
di dalam, kemungkinan besar?

412
00:20:49,330 --> 00:20:52,850
Ya, beberapa jenis gelung, mungkin
selama-lamanya menyekat, mungkin berulang block--

413
00:20:52,850 --> 00:20:54,070
ulangi sehingga blok.

414
00:20:54,070 --> 00:20:57,330
Dan itulah apa yang membuat log dan
pad lily dan segala langkah lagi

415
00:20:57,330 --> 00:20:57,990
belakang dan sebagainya.

416
00:20:57,990 --> 00:21:00,270
Ia hanya berlaku tanpa henti.

417
00:21:00,270 --> 00:21:03,180
>> Mengapa beberapa kereta
bergerak lebih cepat daripada yang lain?

418
00:21:03,180 --> 00:21:06,607
Apa yang berbeza tentang program-program?

419
00:21:06,607 --> 00:21:09,690
Ya, mungkin sebahagian daripada mereka mengambil
lebih langkah dalam satu masa dan sebahagian daripada mereka

420
00:21:09,690 --> 00:21:10,690
kurang langkah dalam satu masa.

421
00:21:10,690 --> 00:21:14,670
Dan kesan visual
cepat berbanding perlahan.

422
00:21:14,670 --> 00:21:16,030
>> Apa yang anda fikir berlaku?

423
00:21:16,030 --> 00:21:19,700
Apabila saya tiba katak saya sepanjang jalan
di seberang jalan dan sungai

424
00:21:19,700 --> 00:21:23,560
ke pad lily, sesuatu
perlu diberi perhatian yang berlaku.

425
00:21:23,560 --> 00:21:26,540
Apa yang berlaku dengan seberapa segera seperti yang saya lakukan itu?

426
00:21:26,540 --> 00:21:27,210
Ia berhenti.

427
00:21:27,210 --> 00:21:29,680
katak yang berhenti, dan
Saya mendapat katak kedua.

428
00:21:29,680 --> 00:21:33,155
Jadi apa konstruk mesti
digunakan di sana, apa ciri?

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

430
00:21:36,020 --> 00:21:38,660
>> Ya, jadi ada beberapa jenis
"Jika" merapikan sana juga.

431
00:21:38,660 --> 00:21:41,909
Dan ternyata out-- kita tidak melihat this--
tetapi ada blok lain di sana yang

432
00:21:41,909 --> 00:21:45,300
boleh katakan, jika anda menyentuh
perkara lain pada skrin,

433
00:21:45,300 --> 00:21:47,720
jika anda menyentuh pad lily, "kemudian."

434
00:21:47,720 --> 00:21:50,810
Dan kemudian itulah apabila kita
membuat katak kedua muncul.

435
00:21:50,810 --> 00:21:54,969
Jadi, walaupun permainan ini adalah pasti
sangat bertarikh, walaupun pada pandangan pertama

436
00:21:54,969 --> 00:21:58,010
terdapat begitu banyak berlaku Blake pada-- dan
tidak cambuk ini dalam dua minit,

437
00:21:58,010 --> 00:22:00,390
ia mungkin mengambil beliau beberapa
jam untuk menghasilkan permainan ini

438
00:22:00,390 --> 00:22:03,850
berdasarkan ingatan atau video beliau
versi tadi itu daripadanya.

439
00:22:03,850 --> 00:22:07,940
Tetapi semua ini perkara-perkara kecil
akan pada skrin secara berasingan

440
00:22:07,940 --> 00:22:11,550
mendidih ke ini sangat mudah
pergerakan constructs-- atau penyata

441
00:22:11,550 --> 00:22:15,519
seperti yang kita telah dibincangkan, gelung dan
syarat, dan itulah mengenainya.

442
00:22:15,519 --> 00:22:17,060
Ada beberapa ciri-ciri lain pelamun.

443
00:22:17,060 --> 00:22:19,130
Sesetengah daripada mereka adalah semata-mata
estetik atau akustik,

444
00:22:19,130 --> 00:22:20,964
seperti bunyi Saya hanya bermain dengan.

445
00:22:20,964 --> 00:22:23,380
Tetapi bagi sebahagian besar, anda
mempunyai dalam bahasa ini, Awal,

446
00:22:23,380 --> 00:22:25,350
semua asas
pembinaan usaha anda

447
00:22:25,350 --> 00:22:29,280
ada dalam C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
dan apa-apa bilangan bahasa lain.

449
00:22:32,960 --> 00:22:36,720
Sebarang soalan mengenai calar?

450
00:22:36,720 --> 00:22:37,220
Baiklah.

451
00:22:37,220 --> 00:22:40,303
Oleh itu, kita tidak akan menyelam lebih dalam untuk Awal,
walaupun sama-sama pada hujung minggu ini,

452
00:22:40,303 --> 00:22:42,860
terutamanya jika anda mempunyai anak-anak atau
anak saudara perempuan dan anak saudara dan sebagainya,

453
00:22:42,860 --> 00:22:44,220
untuk memperkenalkan mereka kepada Scratch.

454
00:22:44,220 --> 00:22:47,960
Ia sebenarnya satu hebat suka bermain
persekitaran dengan, sebagai penulis yang mengatakan,

455
00:22:47,960 --> 00:22:49,120
siling yang tinggi.

456
00:22:49,120 --> 00:22:51,670
Walaupun kami bermula dengan
sangat butiran tahap rendah,

457
00:22:51,670 --> 00:22:54,890
anda benar-benar boleh lakukan agak sedikit
dengan itu, dan ini mungkin

458
00:22:54,890 --> 00:22:57,360
demonstrasi perkara tersebut.

459
00:22:57,360 --> 00:23:02,920
>> Tetapi mari kita kini beralih kepada lebih banyak
masalah canggih, jika anda akan,

460
00:23:02,920 --> 00:23:05,870
dikenali sebagai "mencari" dan
"Menyusun," amnya.

461
00:23:05,870 --> 00:23:09,500
Kami mempunyai buku telefon ini earlier-- sini
satu sama lain hanya untuk discussion--

462
00:23:09,500 --> 00:23:13,460
yang kami dapat untuk mencari
dengan lebih cekap kerana

463
00:23:13,460 --> 00:23:15,270
daripada andaian ketara.

464
00:23:15,270 --> 00:23:17,655
Dan hanya untuk menjadi jelas, apa
andaian adalah saya membuat

465
00:23:17,655 --> 00:23:19,280
ketika mencari melalui buku telefon ini?

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

467
00:23:23,342 --> 00:23:25,300
Bahawa Mike Smith adalah
buku telefon, walaupun saya

468
00:23:25,300 --> 00:23:27,410
akan dapat mengendalikan
senario tanpa dia

469
00:23:27,410 --> 00:23:30,720
sana jika saya hanya berhenti awal.

470
00:23:30,720 --> 00:23:31,806
Buku ini adalah abjad.

471
00:23:31,806 --> 00:23:33,930
Dan itulah yang sangat murah hati
andaian, kerana itu

472
00:23:33,930 --> 00:23:36,580
bermakna someone-- Saya jenis
memotong sudut,

473
00:23:36,580 --> 00:23:40,580
seperti saya lebih cepat kerana seseorang
lagi yang melakukan banyak kerja keras untuk saya.

474
00:23:40,580 --> 00:23:43,120
>> Tetapi bagaimana jika telefon
buku telah terisih?

475
00:23:43,120 --> 00:23:47,050
Mungkin Verizon mendapat malas, hanya melemparkan
nama dan nombor semua orang di sana

476
00:23:47,050 --> 00:23:50,120
mungkin dalam perintah itu di mana mereka
mendaftar untuk perkhidmatan telefon.

477
00:23:50,120 --> 00:23:54,570
Dan berapa banyak masa yang diperlukan saya
untuk mencari seseorang seperti Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1000 halaman telefon book-- berapa banyak
laman saya perlu melihat melalui?

479
00:23:58,160 --> 00:23:58,905
>> Kesemuanya.

480
00:23:58,905 --> 00:24:00,030
Anda jenis daripada nasib.

481
00:24:00,030 --> 00:24:03,420
Anda benar-benar perlu melihat setiap
halaman jika buku telefon hanya

482
00:24:03,420 --> 00:24:04,450
disusun secara rawak.

483
00:24:04,450 --> 00:24:06,910
Anda mungkin akan bernasib baik dan mencari Mike
pada halaman yang pertama, kerana dia

484
00:24:06,910 --> 00:24:08,826
merupakan pelanggan pertama
untuk memerintahkan perkhidmatan telefon.

485
00:24:08,826 --> 00:24:10,760
Tetapi dia mungkin telah lepas juga.

486
00:24:10,760 --> 00:24:12,500
>> Jadi susunan rawak tidak baik.

487
00:24:12,500 --> 00:24:16,750
Jadi rasa kita perlu menyusun
buku telefon atau dalam data jenis umum

488
00:24:16,750 --> 00:24:18,520
yang kita telah diberikan.

489
00:24:18,520 --> 00:24:19,440
Bagaimana kita boleh berbuat demikian?

490
00:24:19,440 --> 00:24:21,360
>> Baiklah, biar saya hanya cuba
contoh yang mudah di sini.

491
00:24:21,360 --> 00:24:24,290
Biar saya pergi ke hadapan dan membuat undian
beberapa nombor di papan.

492
00:24:24,290 --> 00:24:35,480
Katakan nombor yang kita ada adalah,
katakan, empat, dua, satu, dan tiga.

493
00:24:35,480 --> 00:24:38,390
Dan, Ben, menyusun nombor-nombor ini untuk kita.

494
00:24:38,390 --> 00:24:39,017
>> Ok baik.

495
00:24:39,017 --> 00:24:39,850
Bagaimana anda melakukannya?

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

497
00:24:42,731 --> 00:24:43,230
Baiklah.

498
00:24:43,230 --> 00:24:44,710
Jadi bermula dengan yang paling kecil
nilai dan yang paling tinggi,

499
00:24:44,710 --> 00:24:46,084
dan itu benar-benar gerak hati yang baik.

500
00:24:46,084 --> 00:24:48,080
Dan menyedari bahawa kita yang
manusia sebenarnya cukup

501
00:24:48,080 --> 00:24:49,913
baik pada penyelesaian masalah
seperti ini, sekurang-kurangnya

502
00:24:49,913 --> 00:24:51,810
apabila data adalah agak kecil.

503
00:24:51,810 --> 00:24:54,860
Sebaik sahaja anda mula mempunyai beratus-ratus
nombor, beribu-ribu nombor,

504
00:24:54,860 --> 00:24:58,440
berjuta-juta nombor, Ben mungkin
tidak boleh melakukannya cukup yang cepat,

505
00:24:58,440 --> 00:25:00,620
dengan anggapan bahawa terdapat
jurang dalam nombor.

506
00:25:00,620 --> 00:25:03,450
Agak mudah untuk mengira satu juta
sebaliknya, memakan hanya masa.

507
00:25:03,450 --> 00:25:07,150
>> Jadi algoritma ia kedengaran
seperti Ben digunakan tadi

508
00:25:07,150 --> 00:25:08,930
adalah carian untuk jumlah yang paling kecil.

509
00:25:08,930 --> 00:25:12,900
Jadi, walaupun kita manusia boleh mengambil
dalam banyak maklumat visual,

510
00:25:12,900 --> 00:25:14,830
komputer sebenarnya
sedikit lebih terhad.

511
00:25:14,830 --> 00:25:17,560
Komputer hanya boleh
melihat satu bait pada satu masa

512
00:25:17,560 --> 00:25:20,770
atau mungkin empat bait di time-- yang
hari ini mungkin 8 bytes di time-- yang

513
00:25:20,770 --> 00:25:24,450
tetapi jumlah yang sangat kecil
daripada bait pada masa yang diberikan.

514
00:25:24,450 --> 00:25:28,480
>> Jadi memandangkan kita benar-benar mempunyai
empat nilai berasingan sini--

515
00:25:28,480 --> 00:25:32,440
dan anda boleh berfikir Ben sebagai mempunyai
blinders pada-olah dia adalah komputer seperti

516
00:25:32,440 --> 00:25:36,450
bahawa ia tidak dapat melihat apa-apa selain
daripada satu nombor di time-- yang

517
00:25:36,450 --> 00:25:39,720
supaya kita biasanya akan mengambil alih, seperti dalam
Bahasa Inggeris, kami akan dibaca dari kanan ke kiri.

518
00:25:39,720 --> 00:25:42,870
Jadi nombor pertama Ben mungkin kelihatan
di empat dan kemudian dengan cepat

519
00:25:42,870 --> 00:25:44,770
menyedari itu adalah satu yang cukup besar
number-- biarlah saya terus mencari.

520
00:25:44,770 --> 00:25:45,357
>> Ada dua.

521
00:25:45,357 --> 00:25:45,940
Tunggu sebentar.

522
00:25:45,940 --> 00:25:47,070
Dua adalah lebih kecil daripada empat.

523
00:25:47,070 --> 00:25:47,986
Saya akan ingat.

524
00:25:47,986 --> 00:25:49,070
Dua kini yang paling kecil.

525
00:25:49,070 --> 00:25:50,417
Sekarang one-- itulah yang lebih baik.

526
00:25:50,417 --> 00:25:51,250
Itulah yang lebih kecil.

527
00:25:51,250 --> 00:25:54,000
Saya akan lupa kira-kira dua
dan hanya ingat sekarang.

528
00:25:54,000 --> 00:25:56,550
>> Dan dia boleh berhenti mencari?

529
00:25:56,550 --> 00:25:58,360
Well, dia boleh berdasarkan
maklumat ini,

530
00:25:58,360 --> 00:26:00,477
tetapi dia akan carian yang lebih baik
yang lain dalam senarai itu.

531
00:26:00,477 --> 00:26:02,060
Kerana apa jika sifar berada dalam senarai?

532
00:26:02,060 --> 00:26:03,643
Bagaimana jika negatif satu berada dalam senarai?

533
00:26:03,643 --> 00:26:07,720
Dia hanya tahu bahawa jawapan beliau
adalah betul jika dia mendalam

534
00:26:07,720 --> 00:26:08,729
diperiksakan keseluruhan senarai.

535
00:26:08,729 --> 00:26:10,020
Oleh itu, kita melihat seluruh ini.

536
00:26:10,020 --> 00:26:11,394
Three-- itu adalah satu pembaziran masa.

537
00:26:11,394 --> 00:26:13,540
Hanya tidak bernasib baik, tetapi saya
masih betul untuk berbuat demikian.

538
00:26:13,540 --> 00:26:17,857
Dan sekarang dia mungkin
memilih nombor yang paling kecil

539
00:26:17,857 --> 00:26:20,440
dan hanya meletakkan ia pada permulaan
senarai, seperti yang saya akan lakukan di sini.

540
00:26:20,440 --> 00:26:23,480
Sekarang apa yang kamu buat selepas, walaupun
anda tidak berfikir tentang hal itu hampir

541
00:26:23,480 --> 00:26:25,962
setakat ini?

542
00:26:25,962 --> 00:26:27,670
Ulangi proses ini,
jadi beberapa jenis gelung.

543
00:26:27,670 --> 00:26:28,920
Ada idea biasa.

544
00:26:28,920 --> 00:26:30,860
Jadi di sini adalah empat.

545
00:26:30,860 --> 00:26:32,110
Itulah masa yang paling kecil.

546
00:26:32,110 --> 00:26:33,220
Itulah calon.

547
00:26:33,220 --> 00:26:33,900
Tidak lagi.

548
00:26:33,900 --> 00:26:34,770
Sekarang saya lihat dua.

549
00:26:34,770 --> 00:26:36,630
Itulah elemen seterusnya yang paling kecil.

550
00:26:36,630 --> 00:26:40,800
Three-- itu bukan kecil, jadi
sekarang Ben boleh cabut kedua-dua.

551
00:26:40,800 --> 00:26:44,510
>> Dan sekarang kita mengulangi proses, dan
sudah tentu tiga mendapat ditarik keluar depan.

552
00:26:44,510 --> 00:26:45,420
Mengulangi proses tersebut.

553
00:26:45,420 --> 00:26:46,990
Empat mendapat ditarik keluar.

554
00:26:46,990 --> 00:26:50,140
Dan sekarang kita berada di luar nombor,
jadi senarai yang perlu diselesaikan.

555
00:26:50,140 --> 00:26:51,960
>> Dan sesungguhnya, ini adalah satu algoritma formal.

556
00:26:51,960 --> 00:26:56,610
Seorang saintis komputer akan
memanggil ini "apapun pemilihan,"

557
00:26:56,610 --> 00:27:00,880
idea itu jenis yang
menyenaraikan iteratively-- lagi

558
00:27:00,880 --> 00:27:03,807
dan lagi dan lagi memilih
nombor yang paling kecil.

559
00:27:03,807 --> 00:27:06,140
Dan apa yang baik tentang hal itu adalah
ia hanya begitu darn intuitif.

560
00:27:06,140 --> 00:27:07,470
Ia amat mudah.

561
00:27:07,470 --> 00:27:11,100
Dan anda boleh mengulangi yang sama
operasi lagi dan lagi.

562
00:27:11,100 --> 00:27:12,150
Ia mudah.

563
00:27:12,150 --> 00:27:17,170
>> Dalam kes ini ia laju, tetapi
berapa lama masa yang benar-benar mengambil?

564
00:27:17,170 --> 00:27:19,880
Mari kita membuat ia kelihatan dan
berasa sedikit lebih membosankan.

565
00:27:19,880 --> 00:27:24,150
Jadi satu, dua, tiga, empat, lima enam,
tujuh, lapan, sembilan, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- nombor sewenang-wenangnya.

567
00:27:26,160 --> 00:27:28,780
Saya hanya mahu lebih ini
masa daripada hanya empat.

568
00:27:28,780 --> 00:27:30,780
Jadi, jika saya telah mendapat keseluruhan
sekumpulan nombor sekarang-- ia

569
00:27:30,780 --> 00:27:32,420
langsung tidak kira
apa yang mereka ialah- ini membiarkan

570
00:27:32,420 --> 00:27:34,380
berfikir tentang apa yang ini
algoritma benar-benar adalah seperti.

571
00:27:34,380 --> 00:27:35,857
>> Katakan terdapat nombor di sana.

572
00:27:35,857 --> 00:27:38,190
Sekali lagi, tidak kira apa
mereka, tetapi ia secara rawak.

573
00:27:38,190 --> 00:27:39,679
Saya memohon algoritma Ben.

574
00:27:39,679 --> 00:27:41,220
Saya perlu untuk memilih nombor yang paling kecil.

575
00:27:41,220 --> 00:27:41,761
Apa yang saya buat?

576
00:27:41,761 --> 00:27:44,240
Dan saya akan secara fizikal
melakukannya kali ini untuk bertindak keluar.

577
00:27:44,240 --> 00:27:46,099
Mencari, mencari,
mencari, mencari, mencari.

578
00:27:46,099 --> 00:27:48,140
Hanya dengan masa yang saya dapat
akhir senarai yang boleh

579
00:27:48,140 --> 00:27:51,230
Saya sedar yang paling kecil
nombor adalah dua masa ini.

580
00:27:51,230 --> 00:27:52,720
Tidak ada di dalam senarai.

581
00:27:52,720 --> 00:27:54,400
Jadi saya meletakkan dua.

582
00:27:54,400 --> 00:27:55,590
>> Apa yang saya lakukan seterusnya?

583
00:27:55,590 --> 00:27:58,600
Mencari, mencari, mencari, mencari.

584
00:27:58,600 --> 00:28:02,250
Sekarang saya mendapati nombor tujuh, kerana
ada jurang dalam numbers-- ini

585
00:28:02,250 --> 00:28:03,300
tetapi hanya sewenang-wenangnya.

586
00:28:03,300 --> 00:28:03,800
Baiklah.

587
00:28:03,800 --> 00:28:06,030
Jadi sekarang saya boleh meletakkan tujuh.

588
00:28:06,030 --> 00:28:08,860
Mencari Lelaki, mencari.

589
00:28:08,860 --> 00:28:11,030
>> Sekarang saya menganggap, sudah
tentu, bahawa Ben tidak

590
00:28:11,030 --> 00:28:14,780
mempunyai RAM tambahan, tambahan
memori, kerana, sudah tentu,

591
00:28:14,780 --> 00:28:16,080
Saya melihat nombor yang sama.

592
00:28:16,080 --> 00:28:18,246
Sesungguhnya saya boleh ingat
semua orang-orang nombor,

593
00:28:18,246 --> 00:28:19,930
dan itu sememangnya benar.

594
00:28:19,930 --> 00:28:22,610
Tetapi jika Ben ingat semua
nombor dia dilihat,

595
00:28:22,610 --> 00:28:24,430
dia tidak benar-benar membuat
kemajuan asas

596
00:28:24,430 --> 00:28:26,170
kerana dia sudah mempunyai
keupayaan untuk mencari

597
00:28:26,170 --> 00:28:27,540
melalui nombor di papan.

598
00:28:27,540 --> 00:28:29,373
Mengingati semua
nombor tidak membantu,

599
00:28:29,373 --> 00:28:32,490
kerana dia masih boleh seperti komputer
hanya melihat, kita telah berkata satu nombor,

600
00:28:32,490 --> 00:28:33,080
pada satu masa.

601
00:28:33,080 --> 00:28:35,760
Jadi tidak ada semacam cheat
sana yang boleh anda manfaatkan.

602
00:28:35,760 --> 00:28:39,170
>> Jadi pada hakikatnya, seperti yang saya
terus mencari senarai,

603
00:28:39,170 --> 00:28:44,200
Saya benar-benar perlu teruskannya
belakang dan sebagainya melaluinya, mencabut keluar

604
00:28:44,200 --> 00:28:45,710
nombor seterusnya yang paling kecil.

605
00:28:45,710 --> 00:28:48,810
Dan seperti yang anda jenis boleh membuat kesimpulan
daripada pergerakan bodoh saya,

606
00:28:48,810 --> 00:28:50,860
ini hanya mendapat sangat
membosankan dengan cepat,

607
00:28:50,860 --> 00:28:54,850
dan saya seolah-olah akan kembali dan
sebagainya, belakang dan sebagainya agak sedikit.

608
00:28:54,850 --> 00:29:03,220
Sekarang untuk berlaku adil, saya tidak perlu pergi
cukup, baik, mari kita see-- untuk berlaku adil,

609
00:29:03,220 --> 00:29:06,310
Saya tidak perlu berjalan agak
kerana banyak langkah setiap kali.

610
00:29:06,310 --> 00:29:09,200
Kerana, sudah tentu, kerana saya
pilih nombor dari senarai,

611
00:29:09,200 --> 00:29:11,860
senarai baki semakin pendek.

612
00:29:11,860 --> 00:29:14,240
>> Dan jadi mari kita berfikir tentang
jumlah langkah Saya sebenarnya

613
00:29:14,240 --> 00:29:16,010
traipsing melalui setiap masa.

614
00:29:16,010 --> 00:29:18,950
Dalam keadaan yang pertama
kami mempunyai 16 nombor,

615
00:29:18,950 --> 00:29:22,210
dan sebagainya maximally-- mari kita
melakukan ini untuk discussion-- yang

616
00:29:22,210 --> 00:29:25,640
Saya melihat melalui 16
nombor untuk mencari yang paling kecil.

617
00:29:25,640 --> 00:29:28,420
Tetapi apabila saya dipetik daripada
jumlah yang paling kecil, bagaimana

618
00:29:28,420 --> 00:29:30,590
lama adalah senarai yang masih ada, sudah tentu?

619
00:29:30,590 --> 00:29:31,420
Hanya 15.

620
00:29:31,420 --> 00:29:34,670
Jadi berapa banyak nombor lakukan Ben atau saya mempunyai
untuk melihat melalui kali kedua?

621
00:29:34,670 --> 00:29:36,832
15, hanya untuk pergi dan mencari yang paling kecil.

622
00:29:36,832 --> 00:29:39,540
Tetapi sekarang, sudah tentu, senarai adalah,
juga, lebih kecil berbanding sebelum ia.

623
00:29:39,540 --> 00:29:42,540
Jadi berapa banyak langkah-langkah yang tidak saya
perlu mengambil masa yang akan datang?

624
00:29:42,540 --> 00:29:49,970
14 dan kemudian 13 dan kemudian 12, ditambah dot,
dot, dot, sehingga saya ditinggalkan dengan hanya satu.

625
00:29:49,970 --> 00:29:53,146
Jadi sekarang seorang saintis komputer akan
bertanya, baik, apa adakah itu semua sama?

626
00:29:53,146 --> 00:29:55,770
Ia sebenarnya sama dengan beberapa konkrit
jumlah itu kita boleh pasti

627
00:29:55,770 --> 00:30:00,490
melakukan arithmetically, tetapi kita mahu bercakap
tentang kecekapan algoritma

628
00:30:00,490 --> 00:30:04,940
sedikit lebih formulaically,
bebas daripada berapa lama senarai adalah.

629
00:30:04,940 --> 00:30:06,240
>> Dan supaya anda tahu apa?

630
00:30:06,240 --> 00:30:09,860
Ini adalah 16, tetapi seperti yang saya katakan sebelum ini,
mari kita memanggil saiz masalah

631
00:30:09,860 --> 00:30:10,970
n, di mana n adalah nombor.

632
00:30:10,970 --> 00:30:13,220
Mungkin ia adalah 16, mungkin ia
tiga, mungkin ia adalah satu juta.

633
00:30:13,220 --> 00:30:13,761
Saya tidak tahu.

634
00:30:13,761 --> 00:30:14,390
Saya tidak peduli.

635
00:30:14,390 --> 00:30:16,520
Apa yang saya inginkan adalah
formula yang saya boleh

636
00:30:16,520 --> 00:30:19,420
gunakan untuk membandingkan algoritma ini
terhadap algoritma lain

637
00:30:19,420 --> 00:30:22,350
bahawa seseorang mungkin menuntut
adalah lebih baik atau lebih teruk lagi.

638
00:30:22,350 --> 00:30:25,430
>> Jadi ternyata, dan saya hanya
tahu ini dari sekolah rendah,

639
00:30:25,430 --> 00:30:34,790
bahawa ini sebenarnya kerja-kerja kepada yang sama
Perkara seperti n lebih n tambah satu lebih dua.

640
00:30:34,790 --> 00:30:40,020
Dan ini berlaku untuk sama, sudah
Sudah tentu, n kuasa dua tambah n lebih dua.

641
00:30:40,020 --> 00:30:43,250
Jadi jika saya mahu formula
berapa banyak langkah

642
00:30:43,250 --> 00:30:46,330
terlibat dalam melihat semua
daripada nombor-nombor lagi dan lagi

643
00:30:46,330 --> 00:30:52,681
dan lagi dan lagi, saya akan berkata
ia n kuasa dua tambah n lebih dua.

644
00:30:52,681 --> 00:30:53,430
Tetapi anda tahu apa?

645
00:30:53,430 --> 00:30:54,500
Ini hanya kelihatan tidak kemas.

646
00:30:54,500 --> 00:30:56,470
Saya hanya mahu
pengertian umum perkara.

647
00:30:56,470 --> 00:30:58,810
Dan anda mungkin ingat dari
sekolah tinggi yang terdapat

648
00:30:58,810 --> 00:31:00,660
adalah tanggapan jangka perintah tertinggi.

649
00:31:00,660 --> 00:31:05,300
Yang syarat-syarat ini, n
kuasa dua, n, atau separuh,

650
00:31:05,300 --> 00:31:07,550
mempunyai kesan yang paling dari masa ke masa?

651
00:31:07,550 --> 00:31:11,920
N lebih besar mendapat, yang
ini perkara-perkara yang paling?

652
00:31:11,920 --> 00:31:15,560
>> Dalam erti kata lain, jika saya pasang
dalam sejuta, n kuasa dua

653
00:31:15,560 --> 00:31:17,900
akan menjadi yang paling mungkin
faktor mendominasi,

654
00:31:17,900 --> 00:31:21,670
kerana satu juta kali
itu sendiri adalah jauh lebih besar

655
00:31:21,670 --> 00:31:23,682
daripada tambah satu tambahan juta.

656
00:31:23,682 --> 00:31:24,390
Jadi, anda tahu apa?

657
00:31:24,390 --> 00:31:27,305
Ini adalah seperti darn besar
nombor jika anda mengambil ancang-nombor.

658
00:31:27,305 --> 00:31:28,430
Ini tidak benar-benar perkara.

659
00:31:28,430 --> 00:31:30,596
Kami hanya akan silang yang
keluar dan lupa mengenainya.

660
00:31:30,596 --> 00:31:34,250
Dan supaya seorang saintis komputer akan berkata
bahawa kecekapan algoritma ini

661
00:31:34,250 --> 00:31:37,850
adalah atas perintah n squared--
Maksud saya benar-benar satu penghampiran.

662
00:31:37,850 --> 00:31:40,810
Ia umpama secara kasar n kuasa dua.

663
00:31:40,810 --> 00:31:44,130
Dari masa ke masa, yang lebih besar
dan n lebih besar mendapat, ini

664
00:31:44,130 --> 00:31:47,610
adalah anggaran yang baik untuk apa yang
kecekapan atau kekurangan kecekapan

665
00:31:47,610 --> 00:31:49,400
algoritma ini sebenarnya.

666
00:31:49,400 --> 00:31:52,040
Dan saya mendapatkan bahawa, sudah tentu,
dari sebenarnya melakukan matematik.

667
00:31:52,040 --> 00:31:54,040
Tetapi sekarang saya hanya melambai
tangan saya, kerana saya hanya

668
00:31:54,040 --> 00:31:55,790
mahu rasa umum algoritma ini.

669
00:31:55,790 --> 00:31:58,850
>> Jadi menggunakan logik yang sama, sementara itu,
mari kita mempertimbangkan algoritma lain

670
00:31:58,850 --> 00:32:01,162
kita sudah kelihatan carian at-- linear.

671
00:32:01,162 --> 00:32:02,870
Apabila saya telah mencari
untuk book-- telefon

672
00:32:02,870 --> 00:32:05,980
tidak mengasingkan ia, mencari
melalui book-- telefon

673
00:32:05,980 --> 00:32:09,197
kita terus berkata bahawa ia adalah
1000 langkah-langkah, atau 500 langkah.

674
00:32:09,197 --> 00:32:10,280
Tetapi mari kita umum itu.

675
00:32:10,280 --> 00:32:12,860
Jika ada n muka surat dalam
buku telefon, apa yang

676
00:32:12,860 --> 00:32:17,250
masa berjalan atau
kecekapan carian linear?

677
00:32:17,250 --> 00:32:19,750
Ia adalah atas perintah
berapa banyak langkah-langkah untuk mencari

678
00:32:19,750 --> 00:32:24,210
Mike Smith menggunakan carian linear,
algoritma pertama, atau kedua?

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

680
00:32:27,240 --> 00:32:31,710
>> Dalam kes terburuk, Mike
adalah pada akhir buku ini.

681
00:32:31,710 --> 00:32:35,590
Jadi, jika buku telefon mempunyai 1,000 muka surat,
kita kata masa lalu, dalam kes paling teruk,

682
00:32:35,590 --> 00:32:38,380
ia mungkin mengambil masa kira-kira bagaimana
banyak halaman untuk mencari Mike?

683
00:32:38,380 --> 00:32:38,990
Seperti 1000.

684
00:32:38,990 --> 00:32:39,830
Ia merupakan satu had atas.

685
00:32:39,830 --> 00:32:41,790
Ia adalah keadaan yang paling teruk mungkin.

686
00:32:41,790 --> 00:32:44,410
Tetapi sekali lagi, kita beralih
dari nombor-nombor seperti 1000 sekarang.

687
00:32:44,410 --> 00:32:45,730
Ia hanya n.

688
00:32:45,730 --> 00:32:47,470
>> Jadi apa kesimpulan yang logik?

689
00:32:47,470 --> 00:32:50,210
Mencari Mike dalam telefon
buku yang mempunyai halaman n

690
00:32:50,210 --> 00:32:55,280
mungkin mengambil masa, dalam kes yang teruk,
jumlah langkah atas perintah n?

691
00:32:55,280 --> 00:32:58,110
Dan sesungguhnya komputer
saintis akan berkata

692
00:32:58,110 --> 00:33:02,340
bahawa masa berjalan, atau
prestasi atau kecekapan

693
00:33:02,340 --> 00:33:07,470
atau ketidakcekapan, daripada algoritma seperti
carian linear adalah atas perintah n.

694
00:33:07,470 --> 00:33:10,010
Dan kita boleh memohon yang sama
logik menyeberangi sesuatu daripada

695
00:33:10,010 --> 00:33:13,170
kerana saya hanya lakukan kepada kedua
algoritma kami dengan buku telefon,

696
00:33:13,170 --> 00:33:16,040
mana kita pergi dua halaman pada satu masa.

697
00:33:16,040 --> 00:33:20,120
>> Jadi 1000 halaman buku telefon mungkin
membawa kita 500 halaman bertukar, tambah satu

698
00:33:20,120 --> 00:33:21,910
jika kita menggandakan belakang sedikit.

699
00:33:21,910 --> 00:33:26,590
Jadi, jika buku telefon mempunyai halaman n, tetapi
yang kita lakukan dua halaman pada satu masa,

700
00:33:26,590 --> 00:33:28,900
itulah kira-kira apa?

701
00:33:28,900 --> 00:33:33,190
N lebih dua, jadi itu seperti n lebih dua.

702
00:33:33,190 --> 00:33:38,490
Tetapi saya membuat tuntutan yang
masa yang lalu bahawa n lebih two--

703
00:33:38,490 --> 00:33:41,060
itu jenis yang sama dengan hanya n.

704
00:33:41,060 --> 00:33:44,050
Ia hanya satu faktor yang tetap,
ahli sains komputer akan berkata.

705
00:33:44,050 --> 00:33:45,970
Mari kita hanya memberi tumpuan kepada
pembolehubah, really--

706
00:33:45,970 --> 00:33:47,780
pembolehubah terbesar dalam persamaan.

707
00:33:47,780 --> 00:33:52,530
>> carian supaya linear, sama ada dibuat satu
halaman pada satu masa atau dua halaman pada satu masa,

708
00:33:52,530 --> 00:33:54,810
adalah jenis asas yang sama.

709
00:33:54,810 --> 00:33:56,880
Ia masih atas perintah n.

710
00:33:56,880 --> 00:34:01,930
Tetapi saya mendakwa dengan gambar saya sebelum ini
bahawa algoritma ketiga tidak

711
00:34:01,930 --> 00:34:02,480
linear.

712
00:34:02,480 --> 00:34:03,605
Ia bukan satu garis lurus.

713
00:34:03,605 --> 00:34:08,659
Ia adalah bahawa garis melengkung, dan
algebra formula ada apa?

714
00:34:08,659 --> 00:34:11,812
Log n-- supaya log asas dua n.

715
00:34:11,812 --> 00:34:14,520
Dan kita tidak perlu pergi ke terlalu
lebih terperinci mengenai logaritma hari ini,

716
00:34:14,520 --> 00:34:17,394
tetapi kebanyakan ahli-ahli sains komputer tidak akan
walaupun memberitahu anda apa yang asas adalah.

717
00:34:17,394 --> 00:34:20,639
Kerana itu semua hanya
faktor-faktor yang berterusan, boleh dikatakan,

718
00:34:20,639 --> 00:34:22,659
hanya perbezaan angka sedikit.

719
00:34:22,659 --> 00:34:31,179
Dan sebagainya ini akan menjadi perkara biasa
cara untuk komputer terutamanya formal

720
00:34:31,179 --> 00:34:33,949
ahli-ahli sains di papan atau
pengaturcara di papan putih

721
00:34:33,949 --> 00:34:36,889
sebenarnya dengan alasan yang
algoritma mereka akan menggunakan

722
00:34:36,889 --> 00:34:39,500
atau apa kecekapan
algoritma mereka.

723
00:34:39,500 --> 00:34:42,960
>> Dan ini tidak semestinya sesuatu
anda berbincang dalam mana-mana terperinci,

724
00:34:42,960 --> 00:34:47,889
tetapi programmer yang baik adalah seseorang
yang mempunyai, latar belakang formal yang kukuh.

725
00:34:47,889 --> 00:34:50,120
Dia dapat bercakap dengan
anda dalam jenis ini cara

726
00:34:50,120 --> 00:34:53,350
dan benar-benar membuat
hujah-hujah kualitatif

727
00:34:53,350 --> 00:34:56,870
mengapa satu algoritma atau
satu perisian

728
00:34:56,870 --> 00:35:00,165
adalah lebih baik dalam beberapa cara yang lain.

729
00:35:00,165 --> 00:35:02,540
Kerana anda boleh pasti
hanya menjalankan program seseorang itu

730
00:35:02,540 --> 00:35:04,980
dan mengira bilangan saat
yang diperlukan untuk menyelesaikan beberapa nombor,

731
00:35:04,980 --> 00:35:06,710
dan anda boleh menjalankan beberapa
program orang lain

732
00:35:06,710 --> 00:35:08,418
dan mengira bilangan
saat yang diperlukan.

733
00:35:08,418 --> 00:35:12,840
Tetapi ini adalah cara yang lebih umum yang
anda boleh gunakan untuk menganalisis algoritma,

734
00:35:12,840 --> 00:35:15,520
jika anda akan, hanya pada
kertas atau hanya secara lisan.

735
00:35:15,520 --> 00:35:18,430
Tanpa berjalan, tanpa
walaupun cuba input sampel,

736
00:35:18,430 --> 00:35:20,180
anda hanya boleh sebab melaluinya.

737
00:35:20,180 --> 00:35:24,670
Dan sebagainya dengan menyewa pemaju atau jika
mempunyai dia atau dia semacam berhujah kepada anda

738
00:35:24,670 --> 00:35:28,460
mengapa algoritma mereka, rahsia mereka
sos untuk mencari berbilion

739
00:35:28,460 --> 00:35:30,580
halaman web untuk anda
syarikat adalah lebih baik, ini

740
00:35:30,580 --> 00:35:33,302
adalah jenis hujah-hujah mereka
ideal harus dapat dilupakan.

741
00:35:33,302 --> 00:35:35,010
Atau sekurang-kurangnya ini adalah
jenis perkara

742
00:35:35,010 --> 00:35:40,211
yang akan datang dalam perbincangan, di
kurangnya dalam perbincangan yang sangat formal.

743
00:35:40,211 --> 00:35:40,710
Baiklah.

744
00:35:40,710 --> 00:35:44,400
Jadi Ben dicadangkan sesuatu
dipanggil jenis pemilihan.

745
00:35:44,400 --> 00:35:48,200
Tetapi saya akan mencadangkan bahawa ada
cara-cara lain untuk berbuat demikian juga.

746
00:35:48,200 --> 00:35:50,400
Apa yang saya tidak benar-benar suka
mengenai algoritma Ben

747
00:35:50,400 --> 00:35:54,400
adalah bahawa dia terus berjalan, atau
setelah saya berjalan, belakang dan sebagainya

748
00:35:54,400 --> 00:35:56,930
dan belakang dan sebagainya dan belakang dan sebagainya.

749
00:35:56,930 --> 00:36:04,130
Bagaimana jika sebaliknya saya adalah untuk melakukan
sesuatu seperti nombor-nombor ini di sini

750
00:36:04,130 --> 00:36:08,200
dan saya hanya berurusan dengan setiap
nombor seterusnya kerana saya memberikannya?

751
00:36:08,200 --> 00:36:10,780
>> Dalam erti kata lain, di sini
senarai saya nombor.

752
00:36:10,780 --> 00:36:12,944
Empat, satu, tiga, dua.

753
00:36:12,944 --> 00:36:14,360
Dan saya akan melakukan yang berikut.

754
00:36:14,360 --> 00:36:17,230
Saya akan memasukkan nombor
di mana mereka berada dan bukan

755
00:36:17,230 --> 00:36:18,980
daripada memilihnya satu pada satu masa.

756
00:36:18,980 --> 00:36:20,820
Dalam erti kata lain, di sini adalah nombor empat.

757
00:36:20,820 --> 00:36:22,430
>> Berikut adalah senarai asal saya.

758
00:36:22,430 --> 00:36:25,290
Dan saya akan mengekalkan
dasarnya senarai baru di sini.

759
00:36:25,290 --> 00:36:26,710
Jadi ini adalah senarai lama.

760
00:36:26,710 --> 00:36:28,560
Ini senarai baru.

761
00:36:28,560 --> 00:36:30,220
Saya melihat nombor empat pertama.

762
00:36:30,220 --> 00:36:34,500
senarai baru saya pada mulanya kosong,
jadi ia adalah trivially kes

763
00:36:34,500 --> 00:36:36,410
bahawa empat kini aneka senarai.

764
00:36:36,410 --> 00:36:39,560
Saya hanya mengambil bilangan saya diberikan,
dan saya meletakkan ia di dalam senarai baru saya.

765
00:36:39,560 --> 00:36:41,460
>> Adalah senarai baru ini disusun?

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

767
00:36:41,990 --> 00:36:45,090
Ia bodoh kerana ada hanya satu
elemen, tetapi ia benar-benar disusun.

768
00:36:45,090 --> 00:36:46,390
Tidak ada yang keluar dari tempat.

769
00:36:46,390 --> 00:36:49,290
Ia lebih menarik, algoritma ini,
apabila saya bergerak ke langkah seterusnya.

770
00:36:49,290 --> 00:36:50,550
>> Sekarang saya mempunyai satu.

771
00:36:50,550 --> 00:36:55,430
Jadi satu, sudah tentu, tergolong di
bermula atau akhir senarai baru ini?

772
00:36:55,430 --> 00:36:56,360
Permulaan.

773
00:36:56,360 --> 00:36:58,530
Jadi saya perlu membuat kerja-kerja sekarang.

774
00:36:58,530 --> 00:37:01,410
Saya telah mengambil beberapa
kebebasan dengan penanda saya

775
00:37:01,410 --> 00:37:03,120
dengan hanya melukis perkara
di mana saya mahu mereka,

776
00:37:03,120 --> 00:37:05,320
tetapi itu tidak benar-benar
tepat dalam komputer.

777
00:37:05,320 --> 00:37:08,530
Komputer, seperti yang kita tahu, mempunyai
RAM atau Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
dan itulah salah satu bait dan
bait lain dan bait lain.

779
00:37:12,411 --> 00:37:14,910
Dan jika anda mempunyai gigabit
RAM, anda mempunyai bilion bait,

780
00:37:14,910 --> 00:37:16,680
tetapi ia secara fizikal di satu lokasi.

781
00:37:16,680 --> 00:37:19,540
Anda tidak boleh hanya bergerak barangan sekitar
dengan melukis pada papan

782
00:37:19,540 --> 00:37:20,750
mana sahaja yang anda mahu.

783
00:37:20,750 --> 00:37:24,090
Jadi, jika senarai baru saya mempunyai
empat lokasi dalam ingatan,

784
00:37:24,090 --> 00:37:27,480
malangnya empat adalah
sudah di tempat yang salah.

785
00:37:27,480 --> 00:37:30,410
>> Jadi untuk memasukkan nombor satu
Saya tidak boleh hanya menarik di sini.

786
00:37:30,410 --> 00:37:31,901
lokasi memori ini tidak wujud.

787
00:37:31,901 --> 00:37:35,150
Yang akan menipu, dan saya telah
menipu bergambar untuk beberapa minit

788
00:37:35,150 --> 00:37:35,800
di sini.

789
00:37:35,800 --> 00:37:40,950
Jadi benar-benar, jika saya mahu meletakkan satu di sini,
Saya mempunyai untuk menyalin sementara empat

790
00:37:40,950 --> 00:37:43,030
dan kemudian meletakkan satu di sana.

791
00:37:43,030 --> 00:37:45,500
>> Itu baik, itu betul,
yang secara teknikal mungkin,

792
00:37:45,500 --> 00:37:48,410
tetapi sedar itulah kerja tambahan.

793
00:37:48,410 --> 00:37:50,460
Saya tidak hanya meletakkan nombor di tempat.

794
00:37:50,460 --> 00:37:53,026
Saya pertama terpaksa bergerak
nombor, kemudian memasukkannya ke dalam tempat,

795
00:37:53,026 --> 00:37:54,650
jadi saya jenis dua kali ganda jumlah saya kerja.

796
00:37:54,650 --> 00:37:55,660
Jadi menyimpan bahawa dalam fikiran.

797
00:37:55,660 --> 00:37:57,120
>> Tetapi saya kini sudah selesai dengan elemen ini.

798
00:37:57,120 --> 00:37:59,056
Sekarang saya mahu merebut nombor tiga.

799
00:37:59,056 --> 00:38:00,430
Di mana, sudah tentu, ia tergolong?

800
00:38:00,430 --> 00:38:01,480
Di antara.

801
00:38:01,480 --> 00:38:03,650
Saya tidak boleh menipu lagi
dan hanya meletakkan ia di sana,

802
00:38:03,650 --> 00:38:06,770
kerana, sekali lagi, ingatan ini
adalah di lokasi fizikal.

803
00:38:06,770 --> 00:38:10,900
Jadi saya perlu menyalin empat
dan meletakkan tiga di sini.

804
00:38:10,900 --> 00:38:11,550
Bukan masalah besar.

805
00:38:11,550 --> 00:38:14,610
Ia hanya satu langkah tambahan
again-- berasa sangat murah.

806
00:38:14,610 --> 00:38:16,445
>> Tetapi sekarang saya beralih kepada kedua-dua.

807
00:38:16,445 --> 00:38:17,820
Kedua-dua, sudah tentu, tergolong di sini.

808
00:38:17,820 --> 00:38:20,990
Sekarang anda mula melihat bagaimana
kerja yang boleh terkumpul.

809
00:38:20,990 --> 00:38:23,520
Sekarang apa yang saya perlu lakukan?

810
00:38:23,520 --> 00:38:28,570
Ya, saya perlu bergerak empat,
Saya kemudian perlu menyalin tiga,

811
00:38:28,570 --> 00:38:31,200
dan sekarang saya boleh memasukkan kedua-dua.

812
00:38:31,200 --> 00:38:34,460
Dan menangkap dengan ini
algoritma, yang menariknya,

813
00:38:34,460 --> 00:38:41,050
adalah bahawa rasa kita mempunyai lebih ekstrem
kes di mana ia katakan lapan, tujuh,

814
00:38:41,050 --> 00:38:45,150
enam, lima, empat, tiga, dua, satu.

815
00:38:45,150 --> 00:38:49,450
Ini adalah, dalam banyak konteks,
senario kes terburuk,

816
00:38:49,450 --> 00:38:51,570
kerana perkara yang darn
literal ke belakang.

817
00:38:51,570 --> 00:38:53,670
>> Ia tidak benar-benar
menjejaskan algoritma Ben,

818
00:38:53,670 --> 00:38:55,940
kerana dalam pemilihan Ben
semacam dia akan menjaga

819
00:38:55,940 --> 00:38:58,359
pergi dan balik melalui senarai.

820
00:38:58,359 --> 00:39:01,150
Dan kerana dia sentiasa mencari
melalui senarai baki keseluruhan,

821
00:39:01,150 --> 00:39:02,858
ia tidak penting
di mana unsur-unsur adalah.

822
00:39:02,858 --> 00:39:05,630
Tetapi dalam kes ini dengan memasukkan saya
approach-- mari kita cuba ini.

823
00:39:05,630 --> 00:39:08,616
>> Jadi satu, dua, tiga, empat,
lima, enam, tujuh, lapan.

824
00:39:08,616 --> 00:39:11,630
Satu dua tiga empat,
lima, enam, tujuh, lapan.

825
00:39:11,630 --> 00:39:14,320
Saya akan mengambil lapan,
dan di mana saya meletakkan ia?

826
00:39:14,320 --> 00:39:17,260
Nah, pada awal senarai saya,
kerana senarai baru ini disusun.

827
00:39:17,260 --> 00:39:18,760
Dan saya memotongnya.

828
00:39:18,760 --> 00:39:20,551
>> Di mana saya meletakkan tujuh?

829
00:39:20,551 --> 00:39:21,050
Celaka.

830
00:39:21,050 --> 00:39:23,174
Ia perlu untuk pergi ke sana, jadi
Saya mempunyai untuk melakukan penyalinan.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Dan kini tujuh pergi di sini.

833
00:39:28,480 --> 00:39:29,860
Sekarang saya beralih kepada enam.

834
00:39:29,860 --> 00:39:30,980
Sekarang ia lebih kerja.

835
00:39:30,980 --> 00:39:32,570
>> Lapan telah pergi di sini.

836
00:39:32,570 --> 00:39:33,920
Seven telah pergi di sini.

837
00:39:33,920 --> 00:39:35,450
Kini enam boleh pergi di sini.

838
00:39:35,450 --> 00:39:37,950
Sekarang saya merebut lima.

839
00:39:37,950 --> 00:39:40,560
Kini lapan telah pergi
sini, tujuh telah pergi di sini,

840
00:39:40,560 --> 00:39:43,650
enam telah pergi di sini, dan
kini lima dan berulang.

841
00:39:43,650 --> 00:39:46,610
Dan saya cukup banyak
bergerak ia sentiasa.

842
00:39:46,610 --> 00:39:52,950
>> Jadi pada akhirnya, algorithm-- ini kita akan
memanggilnya sisipan sort-- sebenarnya

843
00:39:52,950 --> 00:39:55,020
mempunyai banyak kerja juga.

844
00:39:55,020 --> 00:39:56,970
Ia hanya berbeza
jenis kerja daripada Ben.

845
00:39:56,970 --> 00:40:00,090
kerja Ben telah saya akan
belakang dan sebagainya sepanjang masa,

846
00:40:00,090 --> 00:40:03,510
memilih seterusnya terkecil
elemen lagi dan lagi.

847
00:40:03,510 --> 00:40:06,660
Oleh itu, jenis ini sangat visual kerja.

848
00:40:06,660 --> 00:40:10,600
>> Ini algoritma lain, yang masih
correct-- ia akan mendapatkan pekerjaan yang done--

849
00:40:10,600 --> 00:40:12,800
hanya perubahan jumlah kerja.

850
00:40:12,800 --> 00:40:15,420
Ia kelihatan seperti pada mulanya anda berada
menjimatkan, kerana anda hanya

851
00:40:15,420 --> 00:40:19,190
berurusan dengan setiap elemen
depan tanpa berjalan semua

852
00:40:19,190 --> 00:40:20,930
jalan melalui senarai seperti Ben adalah.

853
00:40:20,930 --> 00:40:25,300
Tetapi masalahnya ialah, terutama dalam
kes gila di mana itu semua ke belakang,

854
00:40:25,300 --> 00:40:27,830
anda hanya jenis
menangguhkan kerja keras

855
00:40:27,830 --> 00:40:30,360
sehingga anda perlu untuk menetapkan kesilapan anda.

856
00:40:30,360 --> 00:40:33,919
>> Dan jadi jika anda boleh bayangkan ini
lapan dan tujuh dan enam dan lima

857
00:40:33,919 --> 00:40:36,710
dan kemudian empat dan tiga dan dua
bergerak dengan cara mereka melalui senarai,

858
00:40:36,710 --> 00:40:39,060
kita baru sahaja mengubah
jenis kerja yang kami lakukan.

859
00:40:39,060 --> 00:40:42,340
Daripada melakukan ia di
permulaan lelaran saya,

860
00:40:42,340 --> 00:40:45,250
Saya hanya melakukannya pada
akhir setiap lelaran.

861
00:40:45,250 --> 00:40:50,550
Jadi ia ternyata bahawa algoritma ini,
juga, umumnya dipanggil jenis kemasukan,

862
00:40:50,550 --> 00:40:52,190
juga atas perintah n kuasa dua.

863
00:40:52,190 --> 00:40:56,480
Ia sebenarnya tidak lebih baik,
tidak lebih baik pada semua.

864
00:40:56,480 --> 00:41:00,810
>> Walau bagaimanapun, ada pendekatan ketiga
Saya akan menggalakkan kita untuk mempertimbangkan,

865
00:41:00,810 --> 00:41:02,970
yang ini.

866
00:41:02,970 --> 00:41:07,850
Jadi andaikan senarai saya, untuk kesederhanaan
sekali lagi, empat, satu, tiga,

867
00:41:07,850 --> 00:41:11,080
two-- hanya empat nombor.

868
00:41:11,080 --> 00:41:13,300
Ben mempunyai gerak hati yang baik,
gerak hati manusia yang baik

869
00:41:13,300 --> 00:41:16,340
sebelum ini, yang mana kita tetap seluruh
menyenaraikan eventually-- jenis sisipan.

870
00:41:16,340 --> 00:41:18,020
Saya dipujuk kita bersama-sama.

871
00:41:18,020 --> 00:41:22,530
Tetapi mari kita mempertimbangkan
Cara yang paling mudah untuk menetapkan senarai ini.

872
00:41:22,530 --> 00:41:24,110
>> Senarai ini tidak diselesaikan.

873
00:41:24,110 --> 00:41:26,130
Mengapa?

874
00:41:26,130 --> 00:41:31,920
Dalam bahasa Inggeris, menjelaskan mengapa
ia tidak benar-benar disusun.

875
00:41:31,920 --> 00:41:33,400
Apakah ertinya tidak diselesaikan?

876
00:41:33,400 --> 00:41:34,220
>> PELAJAR: Ia tidak berurutan.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: Tidak berurutan.

878
00:41:34,990 --> 00:41:35,822
Berikan saya satu contoh.

879
00:41:35,822 --> 00:41:37,180
>> PELAJAR: Meletakkan mereka dalam perintah.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Beri saya contoh yang lebih spesifik.

882
00:41:38,790 --> 00:41:39,832
>> PELAJAR: Menaik perintah.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Tidak menaik perintah.

884
00:41:41,206 --> 00:41:42,100
Lebih tepat.

885
00:41:42,100 --> 00:41:45,190
Saya tidak tahu apa yang anda maksudkan dengan naik.

886
00:41:45,190 --> 00:41:47,150
Apa yang tidak kena?

887
00:41:47,150 --> 00:41:49,930
>> PELAJAR: Yang paling kecil daripada
nombor tidak dalam ruang pertama.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: nombor terkecil yang
tidak dalam ruang pertama.

889
00:41:51,140 --> 00:41:52,120
Menjadi lebih khusus.

890
00:41:52,120 --> 00:41:55,000
Saya mula menangkap.

891
00:41:55,000 --> 00:41:59,470
Kami mengira, tetapi
apa yang di luar perintah di sini?

892
00:41:59,470 --> 00:42:00,707
>> PELAJAR: urutan berangka.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: urutan berangka.

894
00:42:02,040 --> 00:42:04,248
jenis semua orang penyimpanan
ia sini-- tahap yang sangat tinggi.

895
00:42:04,248 --> 00:42:07,450
Hanya literal beritahu saya apa yang
salah seperti kekuatan yang berusia lima tahun.

896
00:42:07,450 --> 00:42:08,310
>> PELAJAR: Plus satu.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Apa itu?

898
00:42:08,750 --> 00:42:09,610
>> PELAJAR: Plus satu.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Apa yang kamu maksudkan satu plus?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Berikan saya berbeza lima tahun berusia a.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Apa salahnya, ibu?

904
00:42:18,330 --> 00:42:19,940
Apa salahnya, ayah?

905
00:42:19,940 --> 00:42:22,808
Apa yang kamu maksudkan ini tidak diselesaikan?

906
00:42:22,808 --> 00:42:24,370
>> PELAJAR: Ia bukan tempat yang betul.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Apa
tidak di tempat yang betul?

908
00:42:25,580 --> 00:42:26,174
>> PELAJAR: Four.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, baik.

910
00:42:27,090 --> 00:42:29,110
Jadi empat tidak di mana ia sepatutnya.

911
00:42:29,110 --> 00:42:30,590
Khususnya, adalah hak ini?

912
00:42:30,590 --> 00:42:33,000
Empat dan satu, yang pertama
dua nombor yang saya lihat.

913
00:42:33,000 --> 00:42:34,930
Adakah ini betul?

914
00:42:34,930 --> 00:42:36,427
Tidak, mereka berada di luar perintah, bukan?

915
00:42:36,427 --> 00:42:38,135
Malah, rasa sekarang
mengenai komputer, terlalu.

916
00:42:38,135 --> 00:42:40,824
Ia hanya boleh melihat mungkin satu,
mungkin dua perkara pada once--

917
00:42:40,824 --> 00:42:43,240
dan benar-benar hanya satu perkara
pada satu masa, tetapi ia boleh sekurang-kurangnya

918
00:42:43,240 --> 00:42:45,790
melihat satu perkara maka
Perkara seterusnya yang betul di sebelahnya.

919
00:42:45,790 --> 00:42:47,380
>> Jadi adakah ini dalam rangka?

920
00:42:47,380 --> 00:42:48,032
Sudah tentu tidak.

921
00:42:48,032 --> 00:42:48,740
Jadi, anda tahu apa?

922
00:42:48,740 --> 00:42:51,020
Mengapa kita tidak mengambil bayi
langkah-langkah untuk memperbaiki masalah ini

923
00:42:51,020 --> 00:42:53,410
daripada melakukan mewah ini
algoritma seperti Ben, di mana

924
00:42:53,410 --> 00:42:56,440
dia semacam membetulkannya oleh
menggelung melalui senarai

925
00:42:56,440 --> 00:42:59,670
daripada melakukan apa yang saya lakukan, di mana
Saya hanya jenis tetap ia seperti yang kita pergi?

926
00:42:59,670 --> 00:43:03,650
Mari kita literal memecahkan
tanggapan tertib berangka perintah-,

927
00:43:03,650 --> 00:43:06,990
memanggilnya apa sahaja yang anda want--
ke dalam ini perbandingan dari segi pasangan.

928
00:43:06,990 --> 00:43:07,590
>> Empat dan satu.

929
00:43:07,590 --> 00:43:09,970
Adakah ini susunan yang betul?

930
00:43:09,970 --> 00:43:11,310
Jadi mari kita menetapkan bahawa.

931
00:43:11,310 --> 00:43:14,700
Satu dan empat, dan kemudian
kita hanya akan menyalin itu.

932
00:43:14,700 --> 00:43:15,560
Baiklah, baik.

933
00:43:15,560 --> 00:43:17,022
Saya tetap satu dan empat.

934
00:43:17,022 --> 00:43:18,320
Tiga dan dua?

935
00:43:18,320 --> 00:43:18,820
No.

936
00:43:18,820 --> 00:43:21,690
Biar kata-kata saya sepadan jari saya.

937
00:43:21,690 --> 00:43:23,695
Empat dan tiga?

938
00:43:23,695 --> 00:43:27,930
>> Ia bukan dalam perintah, jadi saya akan
untuk melakukan satu, tiga, empat, dua.

939
00:43:27,930 --> 00:43:28,680
Ok baik.

940
00:43:28,680 --> 00:43:32,310
Sekarang empat dan dua?

941
00:43:32,310 --> 00:43:33,370
Kita perlu untuk menetapkan ini, juga.

942
00:43:33,370 --> 00:43:36,700
Jadi satu, tiga, dua, empat.

943
00:43:36,700 --> 00:43:39,820
Begitu juga ia disusun?

944
00:43:39,820 --> 00:43:43,170
Tiada, tetapi ia lebih dekat dengan disusun?

945
00:43:43,170 --> 00:43:48,930
>> Ia adalah, kerana kita tetap ini
kesilapan, kita tetap kesilapan ini,

946
00:43:48,930 --> 00:43:50,370
dan Kami telah tetapkan satu kesilapan ini.

947
00:43:50,370 --> 00:43:52,420
Oleh itu, kita tetap tiga kesilapan boleh dikatakan.

948
00:43:52,420 --> 00:43:58,100
Masih tidak benar-benar melihat disusun, tetapi
ia adalah objektif lebih dekat dengan disusun

949
00:43:58,100 --> 00:44:00,080
kerana kita tetap beberapa orang-orang kesilapan.

950
00:44:00,080 --> 00:44:02,047
>> Sekarang apa yang saya lakukan seterusnya?

951
00:44:02,047 --> 00:44:03,630
Saya jenis sampai ke penghujung senarai.

952
00:44:03,630 --> 00:44:05,680
Saya seolah-olah telah tetap
semua kesilapan, tetapi tidak.

953
00:44:05,680 --> 00:44:08,510
Kerana dalam kes ini, beberapa nombor
mungkin telah dipam lebih dekat

954
00:44:08,510 --> 00:44:10,410
kepada nombor lain yang
masih keluar perintah.

955
00:44:10,410 --> 00:44:12,951
Jadi mari kita buat sekali lagi, dan saya akan
hanya melakukannya di tempat masa ini.

956
00:44:12,951 --> 00:44:14,170
Satu dan tiga?

957
00:44:14,170 --> 00:44:14,720
Tidak mengapa.

958
00:44:14,720 --> 00:44:16,070
Tiga dan dua?

959
00:44:16,070 --> 00:44:17,560
Sudah tentu tidak, jadi mari kita mengubah itu.

960
00:44:17,560 --> 00:44:19,160
Jadi dua, tiga.

961
00:44:19,160 --> 00:44:21,340
Tiga dan empat?

962
00:44:21,340 --> 00:44:24,370
Dan sekarang mari kita hanya menjadi
terutamanya bengah sini.

963
00:44:24,370 --> 00:44:26,350
Adakah ia disusun?

964
00:44:26,350 --> 00:44:29,280
Anda manusia tahu ia disusun.

965
00:44:29,280 --> 00:44:30,400
>> Saya harus cuba lagi.

966
00:44:30,400 --> 00:44:31,900
Jadi Olivia mencadangkan saya cuba lagi.

967
00:44:31,900 --> 00:44:32,530
Mengapa?

968
00:44:32,530 --> 00:44:35,810
Kerana komputer yang tidak mempunyai
kemewahan mata manusia

969
00:44:35,810 --> 00:44:38,080
hanya mengerling back-- OK, aku selesai.

970
00:44:38,080 --> 00:44:41,610
Bagaimanakah komputer menentukan
bahawa senarai itu kini disusun?

971
00:44:41,610 --> 00:44:44,590
Mekanikal.

972
00:44:44,590 --> 00:44:47,650
>> Saya perlu melalui
sekali lagi, dan hanya jika saya

973
00:44:47,650 --> 00:44:51,190
tidak membuat / mencari apa-apa kesilapan yang boleh saya
kemudian membuat kesimpulan seperti komputer, yep,

974
00:44:51,190 --> 00:44:51,980
kita baik pergi.

975
00:44:51,980 --> 00:44:54,850
Jadi, satu dan dua, dua dan
tiga, tiga dan empat.

976
00:44:54,850 --> 00:44:58,030
Sekarang saya secara muktamad boleh mengatakan ini adalah
disusun, kerana saya tidak membuat sebarang perubahan.

977
00:44:58,030 --> 00:45:01,940
Sekarang ia akan menjadi bug dan hanya
bodoh jika saya, komputer,

978
00:45:01,940 --> 00:45:05,640
bertanya soalan-soalan yang sama sekali lagi
mengharapkan jawapan yang berbeza.

979
00:45:05,640 --> 00:45:07,110
tidak sepatutnya berlaku.

980
00:45:07,110 --> 00:45:08,600
>> Dan sehingga kini senarai itu disusun.

981
00:45:08,600 --> 00:45:12,630
Malangnya, berlari masa
algoritma ini juga n kuasa dua.

982
00:45:12,630 --> 00:45:13,130
Mengapa?

983
00:45:13,130 --> 00:45:19,520
Kerana anda mempunyai nombor n, dan dalam
kes paling teruk anda perlu bergerak nombor n

984
00:45:19,520 --> 00:45:23,637
kali n kerana anda perlu terus pergi
kembali untuk memeriksa dan berpotensi menetapkan

985
00:45:23,637 --> 00:45:24,220
nombor-nombor ini.

986
00:45:24,220 --> 00:45:26,280
Dan kita boleh melakukan yang lebih
analisis formal, terlalu.

987
00:45:26,280 --> 00:45:29,530
>> Semua ini untuk mengatakan bahawa kita telah mengambil
tiga pendekatan yang berbeza, satu

988
00:45:29,530 --> 00:45:32,210
daripada mereka segera intuitif
off kelawar dari Ben

989
00:45:32,210 --> 00:45:35,170
untuk kemasukan yang dicadangkan saya
jenis yang ini

990
00:45:35,170 --> 00:45:38,540
di mana anda jenis terlepas pandang
hutan untuk pokok-pokok pada mulanya.

991
00:45:38,540 --> 00:45:41,760
Tetapi jika anda mengambil langkah ke belakang,
Voilà, kami tetap tanggapan sorting.

992
00:45:41,760 --> 00:45:43,824
Jadi ini, berani mengatakan,
tahap yang lebih rendah mungkin

993
00:45:43,824 --> 00:45:45,740
daripada beberapa orang-orang lain
algoritma, tetapi mari kita

994
00:45:45,740 --> 00:45:48,550
lihat jika kita tidak boleh menggambarkan
ini dengan cara ini.

995
00:45:48,550 --> 00:45:51,450
>> Jadi ini adalah beberapa nice
perisian yang seseorang

996
00:45:51,450 --> 00:45:56,110
menulis menggunakan bar yang berwarna-warni itu
akan melakukan yang berikut untuk kita.

997
00:45:56,110 --> 00:45:57,736
Setiap bar ini mewakili nombor.

998
00:45:57,736 --> 00:46:00,026
Taller bar, semakin besar
jumlah itu, lebih kecil bar,

999
00:46:00,026 --> 00:46:00,990
lebih kecil bilangan.

1000
00:46:00,990 --> 00:46:05,880
Begitu ideal kita mahu piramid nice
di mana ia bermula kecil dan mendapat besar,

1001
00:46:05,880 --> 00:46:08,330
dan yang akan bermakna bahawa
Bar ini disusun.

1002
00:46:08,330 --> 00:46:11,200
Jadi, saya akan pergi ke hadapan dan memilih,
misalnya, algoritma Ben

1003
00:46:11,200 --> 00:46:13,990
first-- apapun pemilihan.

1004
00:46:13,990 --> 00:46:16,220
>> Dan perhatikan apa yang ia lakukan.

1005
00:46:16,220 --> 00:46:18,670
Cara mereka telah memilih untuk
menggambarkan algoritma ini

1006
00:46:18,670 --> 00:46:22,090
adalah bahawa, sama seperti saya
berjalan melalui senarai saya,

1007
00:46:22,090 --> 00:46:24,710
program ini berjalan
melalui senarai nama nombor,

1008
00:46:24,710 --> 00:46:28,160
menonjolkan in pink setiap
jumlah itu ia melihat.

1009
00:46:28,160 --> 00:46:32,360
Dan apa yang akan berlaku sekarang?

1010
00:46:32,360 --> 00:46:35,154
>> Bilangan terkecil yang
I atau Ben mendapati tiba-tiba

1011
00:46:35,154 --> 00:46:36,820
mendapat berpindah ke permulaan senarai.

1012
00:46:36,820 --> 00:46:40,037
Dan notis yang mereka lakukan mengusir
nombor yang berada di sana,

1013
00:46:40,037 --> 00:46:41,120
dan yang betul-betul halus.

1014
00:46:41,120 --> 00:46:42,600
Saya tidak masuk ke dalam tahap yang terperinci.

1015
00:46:42,600 --> 00:46:44,308
Tetapi kita perlu meletakkan
jumlah itu di suatu tempat,

1016
00:46:44,308 --> 00:46:47,775
jadi kita bergerak kepada
tempat terbuka yang telah dicipta.

1017
00:46:47,775 --> 00:46:49,900
Jadi saya akan mempercepatkan ini
sehingga, kerana jika tidak ia

1018
00:46:49,900 --> 00:46:51,871
menjadi sangat membosankan dengan cepat.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animasi speed-- ada kita pergi.

1021
00:46:58,600 --> 00:47:01,850
prinsip Jadi sekarang sama
Saya telah memohon, tetapi anda

1022
00:47:01,850 --> 00:47:06,540
boleh mula berasa algoritma, jika anda
akan, atau melihat ia sedikit lebih jelas.

1023
00:47:06,540 --> 00:47:13,190
Dan algoritma ini mempunyai kesan
memilih elemen yang paling kecil akan datang,

1024
00:47:13,190 --> 00:47:16,422
jadi anda akan mula
melihatnya jalan sehingga di sebelah kiri.

1025
00:47:16,422 --> 00:47:19,130
Dan pada setiap lelaran, seperti yang saya
dicadangkan, ia bekerja yang kurang sedikit.

1026
00:47:19,130 --> 00:47:21,921
Ia tidak perlu pergi sepanjang jalan
kembali ke hujung kiri senarai,

1027
00:47:21,921 --> 00:47:23,900
kerana ia sudah
mengetahui orang-orang yang disusun.

1028
00:47:23,900 --> 00:47:28,129
Jadi ia jenis berasa seperti ia
mempercepatkan, walaupun setiap langkah adalah

1029
00:47:28,129 --> 00:47:29,420
mengambil jumlah yang sama.

1030
00:47:29,420 --> 00:47:31,600
Terdapat hanya lebih sedikit langkah yang seterusnya.

1031
00:47:31,600 --> 00:47:35,240
Dan sekarang anda jenis boleh merasai
algoritma membersihkan akhir itu,

1032
00:47:35,240 --> 00:47:37,040
dan sesungguhnya kini ia disusun.

1033
00:47:37,040 --> 00:47:41,620
>> Jadi jenis kemasukan semua dilakukan.

1034
00:47:41,620 --> 00:47:43,600
Saya perlu semula Rawakkan-array.

1035
00:47:43,600 --> 00:47:45,940
Dan perhatikan saya boleh hanya
menjaga randomizing ia,

1036
00:47:45,940 --> 00:47:50,630
dan kami akan mendapat anggaran
pendekatan yang sama, jenis kemasukan.

1037
00:47:50,630 --> 00:47:55,050
Biar saya memperlahankannya ke sini.

1038
00:47:55,050 --> 00:47:56,915
Mari kita mulakan yang lebih.

1039
00:47:56,915 --> 00:47:57,414
Berhenti.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Mari kita skip empat.

1042
00:48:02,410 --> 00:48:03,200
Di sana kami pergi.

1043
00:48:03,200 --> 00:48:04,190
Rawakkan lokasi mereka.

1044
00:48:04,190 --> 00:48:05,555
Dan di sini kita go-- jenis kemasukan.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Play.

1047
00:48:12,800 --> 00:48:17,280
Perhatikan bahawa ia berurusan dengan setiap
unsur ia menghadapi merta,

1048
00:48:17,280 --> 00:48:20,282
tetapi jika ia tergolong dalam
tempat notis salah

1049
00:48:20,282 --> 00:48:21,740
semua kerja yang telah berlaku.

1050
00:48:21,740 --> 00:48:24,700
Kami perlu terus beralih lebih
dan banyak lagi elemen untuk membuat bilik

1051
00:48:24,700 --> 00:48:27,340
untuk apa yang kita mahu dimasukkan ke dalam tempat.

1052
00:48:27,340 --> 00:48:30,740
>> Jadi, kita memberi tumpuan kepada
hujung kiri senarai sahaja.

1053
00:48:30,740 --> 00:48:34,460
Notis yang kami telah tidak kelihatan at-- kita
telah tidak ditonjolkan dalam apa-apa merah jambu

1054
00:48:34,460 --> 00:48:35,610
ke kanan.

1055
00:48:35,610 --> 00:48:38,180
Kami hanya berurusan dengan
masalah seperti yang kita pergi,

1056
00:48:38,180 --> 00:48:40,430
tetapi kami mewujudkan banyak
bekerja untuk diri kita sendiri masih.

1057
00:48:40,430 --> 00:48:44,410
Dan jadi jika kita mempercepatkan ini sehingga
sekarang untuk pergi ke siap,

1058
00:48:44,410 --> 00:48:46,210
ia mempunyai rasa yang berbeza untuk itu sesungguhnya.

1059
00:48:46,210 --> 00:48:50,150
Ia hanya memberi tumpuan kepada hujung kiri tetapi
melakukan kerja lebih sedikit sebagai needed--

1060
00:48:50,150 --> 00:48:53,230
jenis perkara melicinkan
lebih, menetapkan perkara-perkara,

1061
00:48:53,230 --> 00:48:58,350
tetapi berurusan akhirnya dengan
setiap unsur satu demi satu

1062
00:48:58,350 --> 00:49:07,740
sehingga kita sampai ke hanya-- baik, kita
semua tahu bagaimana ini akan berakhir,

1063
00:49:07,740 --> 00:49:09,700
maka ia adalah satu underwhelming sedikit mungkin.

1064
00:49:09,700 --> 00:49:12,830
>> Tetapi senarai dalam end-- yang
spoiler-- akan diselesaikan.

1065
00:49:12,830 --> 00:49:15,300
Jadi mari kita lihat di salah satu lepas.

1066
00:49:15,300 --> 00:49:16,840
Kita tidak boleh hanya melangkau sekarang.

1067
00:49:16,840 --> 00:49:18,000
Kita sudah hampir.

1068
00:49:18,000 --> 00:49:19,980
Dua untuk pergi, satu pergi.

1069
00:49:19,980 --> 00:49:22,680
Dan Voilà.

1070
00:49:22,680 --> 00:49:23,450
Cemerlang.

1071
00:49:23,450 --> 00:49:27,220
>> Jadi sekarang mari kita buat satu yang terakhir,
semula randomizing dengan gelembung macam.

1072
00:49:27,220 --> 00:49:31,690
Dan perhatikan di sini, terutamanya jika saya memperlahankannya
ke bawah, ini tidak menyimpan swooping melalui.

1073
00:49:31,690 --> 00:49:36,830
Tetapi notis ia hanya membuat berpasangan
jenis comparisons-- penyelesaian tempatan.

1074
00:49:36,830 --> 00:49:39,050
Tetapi sebaik sahaja kita dapat
akhir senarai dalam merah jambu,

1075
00:49:39,050 --> 00:49:40,690
apa yang akan perlu berlaku lagi?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Ya, ia akan perlu
mula semula, kerana ia hanya

1078
00:49:46,830 --> 00:49:49,870
kesilapan dari segi pasangan tetap.

1079
00:49:49,870 --> 00:49:53,120
Dan yang mungkin telah didedahkan lagi orang lain.

1080
00:49:53,120 --> 00:49:58,950
Dan jadi jika anda mempercepatkan sehingga ini, anda akan
melihat bahawa, banyak yang namanya,

1081
00:49:58,950 --> 00:50:01,870
yang lebih kecil elements-- atau sebaliknya,
yang elements-- lebih besar bermula

1082
00:50:01,870 --> 00:50:03,740
gelembung sehingga ke atas, jika anda akan.

1083
00:50:03,740 --> 00:50:07,380
Dan unsur-unsur yang lebih kecil
mula gelembung ke kiri.

1084
00:50:07,380 --> 00:50:10,780
Dan sesungguhnya, itulah jenis
kesan visual juga.

1085
00:50:10,780 --> 00:50:17,150
Dan sebagainya ini akan berakhir kemasan
dengan cara yang hampir sama juga.

1086
00:50:17,150 --> 00:50:19,160
>> Kami tidak mempunyai mereka kekal
pada salah satu tertentu ini.

1087
00:50:19,160 --> 00:50:21,010
Biar saya membuka ini sekarang juga.

1088
00:50:21,010 --> 00:50:24,040
Ada beberapa algoritma sorting lain
di dunia, beberapa yang

1089
00:50:24,040 --> 00:50:25,580
direkodkan di sini.

1090
00:50:25,580 --> 00:50:29,960
Dan terutama untuk pelajar yang tidak
semestinya visual atau matematik,

1091
00:50:29,960 --> 00:50:31,930
seperti yang kita lakukan sebelum ini, kita boleh
juga melakukan ini audially

1092
00:50:31,930 --> 00:50:34,210
jika kita kaitkan bunyi dengan ini.

1093
00:50:34,210 --> 00:50:36,990
Dan hanya untuk keseronokan, di sini adalah
Beberapa algoritma yang berbeza,

1094
00:50:36,990 --> 00:50:40,950
dan salah seorang daripada mereka khususnya anda berada
akan perasan dipanggil "merge."

1095
00:50:40,950 --> 00:50:43,250
>> Ia sebenarnya adalah asasnya
algoritma yang lebih baik,

1096
00:50:43,250 --> 00:50:45,860
seperti yang bergabung jenis, salah satu daripada
orang-orang yang anda kira-kira untuk melihat,

1097
00:50:45,860 --> 00:50:49,170
bukan perintah n kuasa dua.

1098
00:50:49,170 --> 00:50:57,280
Ia pada perintah itu n kali log daripada
n, yang sebenarnya lebih kecil dan dengan itu

1099
00:50:57,280 --> 00:50:58,940
lebih cepat daripada yang tiga lain.

1100
00:50:58,940 --> 00:51:00,670
Dan ada pasangan lain
orang-orang yang bodoh yang kita akan lihat.

1101
00:51:00,670 --> 00:51:01,933
>> Jadi di sini kita pergi dengan beberapa bunyi.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Ini adalah jenis kemasukan, jadi sekali lagi
ia hanya berurusan dengan unsur-unsur

1104
00:51:10,490 --> 00:51:13,420
kerana mereka datang.

1105
00:51:13,420 --> 00:51:17,180
Ini adalah jenis gelembung, jadi ia
menganggap mereka pasangan pada satu masa.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Dan sekali lagi, unsur-unsur terbesar
sedang menggelegak sehingga ke atas.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Seterusnya apapun pemilihan.

1110
00:51:41,710 --> 00:51:45,420
Ini adalah algoritma Ben, di mana
lagi dia memilih iterative

1111
00:51:45,420 --> 00:51:46,843
elemen seterusnya yang paling kecil.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Dan sekali lagi, kini anda boleh benar-benar mendengar bahawa
ia mempercepatkan tetapi hanya setakat

1114
00:51:53,900 --> 00:51:58,230
kerana ia melakukan kurang dan kurang
bekerja pada setiap lelaran.

1115
00:51:58,230 --> 00:52:04,170
Ini adalah lebih cepat satu, bergabung apapun,
yang menyusun kelompok nombor

1116
00:52:04,170 --> 00:52:05,971
bersama-sama dan kemudian menggabungkan mereka.

1117
00:52:05,971 --> 00:52:07,720
Jadi look-- kiri
setengah sudah disusun.

1118
00:52:07,720 --> 00:52:14,165
>> Kini ia menyusun separuh yang betul, dan
kini ia akan menggabungkan mereka menjadi satu.

1119
00:52:14,165 --> 00:52:19,160
Ini adalah sesuatu yang dinamakan "Gnome macam."

1120
00:52:19,160 --> 00:52:23,460
Dan anda boleh jenis melihat bahawa
ia akan belakang dan sebagainya,

1121
00:52:23,460 --> 00:52:27,950
menetapkan kerja sedikit di sini dan
di sana sebelum ia bertindak untuk kerja-kerja baru.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Dan itu sahaja.

1124
00:52:33,692 --> 00:52:36,400
Ada jenis lain, yang
benar-benar hanya untuk tujuan akademik,

1125
00:52:36,400 --> 00:52:40,980
dipanggil "jenis bodoh," yang mengambil
data anda, menyusun ia secara rawak,

1126
00:52:40,980 --> 00:52:43,350
dan kemudian memeriksa jika ia disusun.

1127
00:52:43,350 --> 00:52:47,880
Dan jika tidak, ia semula menyusun ia
secara rawak, memeriksa jika ia disusun,

1128
00:52:47,880 --> 00:52:49,440
dan jika tidak mengulangi.

1129
00:52:49,440 --> 00:52:52,660
Dan dalam teori, probabilistically
ini akan melengkapkan,

1130
00:52:52,660 --> 00:52:54,140
tetapi selepas agak sedikit masa.

1131
00:52:54,140 --> 00:52:56,930
Ia bukan yang paling
cekap algoritma.

1132
00:52:56,930 --> 00:53:02,550
Jadi apa-apa soalan kepada orang-orang
algoritma atau apa-apa tertentu

1133
00:53:02,550 --> 00:53:04,720
berkaitan di sana juga?

1134
00:53:04,720 --> 00:53:09,430
>> Nah, mari kita kini mengusik selain apa yang semua
ayat-ayat ini adalah bahawa saya telah melukis

1135
00:53:09,430 --> 00:53:15,090
dan apa yang saya menganggap komputer
boleh lakukan di bawah hood.

1136
00:53:15,090 --> 00:53:18,650
Saya berpendapat bahawa semua nombor-nombor
Saya menyimpan drawing-- mereka perlu mendapatkan

1137
00:53:18,650 --> 00:53:21,330
disimpan di suatu tempat dalam ingatan.

1138
00:53:21,330 --> 00:53:24,130
Kami akan menghilangkan lelaki ini sekarang juga.

1139
00:53:24,130 --> 00:53:30,110
>> Jadi sekeping memori dalam
computer-- supaya RAM DIMM adalah

1140
00:53:30,110 --> 00:53:35,480
apa yang kita dicari semalam, dua
memori sebaris module-- kelihatan seperti ini.

1141
00:53:35,480 --> 00:53:39,370
Dan masing-masing cip hitam sedikit
adalah nombor bait, biasanya.

1142
00:53:39,370 --> 00:53:44,380
Dan kemudian pin emas adalah seperti
wayar yang menyambung ke komputer,

1143
00:53:44,380 --> 00:53:47,521
dan lembaga silikon hijau adalah hanya
apa yang membuat segala-galanya bersama-sama.

1144
00:53:47,521 --> 00:53:48,770
Jadi apakah ini benar-benar bermakna?

1145
00:53:48,770 --> 00:53:53,180
Jika saya jenis menarik gambar yang sama,
mari kita andaikan untuk kesederhanaan

1146
00:53:53,180 --> 00:53:55,280
yang DIMM ini, dua
modul memori sebaris,

1147
00:53:55,280 --> 00:54:00,530
adalah satu gigabait RAM, satu gigabit
ingatan, yang berapa banyak bait jumlah?

1148
00:54:00,530 --> 00:54:02,100
Satu gigabyte adalah berapa banyak bait?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Lebih daripada itu.

1151
00:54:06,030 --> 00:54:09,960
1124 adalah kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega juta.

1153
00:54:11,730 --> 00:54:14,570
Giga adalah satu bilion.

1154
00:54:14,570 --> 00:54:15,070
>> Adakah saya berbohong?

1155
00:54:15,070 --> 00:54:16,670
Bolehkah kita walaupun membaca label?

1156
00:54:16,670 --> 00:54:19,920
Ini sebenarnya 128
gigabait, jadi ia lebih.

1157
00:54:19,920 --> 00:54:22,130
Tetapi kita akan berpura-pura ini
hanya salah satu gigabit.

1158
00:54:22,130 --> 00:54:25,640
Ini bermakna ada satu bilion
bait memori yang tersedia untuk saya

1159
00:54:25,640 --> 00:54:29,770
atau 8 bilion bit, tetapi kita akan
bercakap dari segi bait sekarang,

1160
00:54:29,770 --> 00:54:30,750
bergerak ke hadapan.

1161
00:54:30,750 --> 00:54:36,330
>> Jadi apa yang bermakna adalah ini adalah
satu bait, ini adalah bait lain,

1162
00:54:36,330 --> 00:54:38,680
ini adalah bait lain,
dan jika kita benar-benar mahu

1163
00:54:38,680 --> 00:54:43,280
untuk menjadi tertentu kita perlu
menarik satu bilion dataran kecil.

1164
00:54:43,280 --> 00:54:44,320
Tetapi apa maksudnya?

1165
00:54:44,320 --> 00:54:46,420
Baiklah, biar saya hanya zum
dalam pada gambar ini.

1166
00:54:46,420 --> 00:54:50,900
Jika saya ada sesuatu yang kelihatan
seperti ini sekarang, itu empat bait.

1167
00:54:50,900 --> 00:54:53,710
>> Oleh itu, saya boleh meletakkan empat nombor tersebut di sini.

1168
00:54:53,710 --> 00:54:54,990
Satu dua tiga empat.

1169
00:54:54,990 --> 00:55:00,170
Atau saya boleh meletakkan empat huruf atau simbol.

1170
00:55:00,170 --> 00:55:02,620
"Hey!" boleh pergi di sana,
kerana setiap huruf,

1171
00:55:02,620 --> 00:55:04,370
kita dibincangkan sebelum ini,
boleh diwakili

1172
00:55:04,370 --> 00:55:06,650
dengan lapan bit atau ASCII atau satu bait.

1173
00:55:06,650 --> 00:55:09,370
Jadi dalam erti kata lain, anda boleh
meletakkan 8 bilion perkara di dalam

1174
00:55:09,370 --> 00:55:11,137
satu kayu ini memori.

1175
00:55:11,137 --> 00:55:14,345
Sekarang apa yang ia bermaksud untuk meletakkan perkara-perkara kembali
ke belakang untuk kembali dalam ingatan seperti ini?

1176
00:55:14,345 --> 00:55:17,330
Ini adalah apa yang programmer
akan panggil "array."

1177
00:55:17,330 --> 00:55:21,250
Dalam program komputer, anda tidak fikir
mengenai perkakasan asas, per se.

1178
00:55:21,250 --> 00:55:24,427
Anda hanya memikirkan diri anda sebagai mempunyai
akses kepada sejumlah bilion bait,

1179
00:55:24,427 --> 00:55:26,010
dan anda boleh apa sahaja yang anda mahu dengan ia.

1180
00:55:26,010 --> 00:55:27,880
Tetapi untuk kemudahan
ia biasanya berguna

1181
00:55:27,880 --> 00:55:31,202
untuk menjaga hak ingatan anda
bersebelahan antara satu sama lain seperti ini.

1182
00:55:31,202 --> 00:55:33,660
Jadi jika saya mengezum masuk pada this--
kerana kita pasti tidak akan

1183
00:55:33,660 --> 00:55:39,310
untuk menarik satu bilion squares-- sedikit
mari kita andaikan bahawa lembaga ini mewakili

1184
00:55:39,310 --> 00:55:40,610
bahawa kayu memori sekarang.

1185
00:55:40,610 --> 00:55:43,800
Dan saya hanya akan menarik seramai saya
penanda berakhir memberikan saya di sini.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Jadi sekarang kita mempunyai kayu
memori pada papan

1188
00:55:52,300 --> 00:55:56,400
itu mendapat satu, dua, tiga, empat, lima,
enam, satu, dua, tiga, empat, lima, enam,

1189
00:55:56,400 --> 00:56:01,130
seven-- jadi 42 bait
memori pada jumlah skrin.

1190
00:56:01,130 --> 00:56:01,630
Terima kasih.

1191
00:56:01,630 --> 00:56:02,838
Ya, adakah aritmetik saya betul.

1192
00:56:02,838 --> 00:56:05,120
Jadi 42 bait memori di sini.

1193
00:56:05,120 --> 00:56:06,660
Jadi apakah ini sebenarnya bermakna?

1194
00:56:06,660 --> 00:56:09,830
Nah, seorang pengaturcara komputer
akan sebenarnya umumnya

1195
00:56:09,830 --> 00:56:12,450
memikirkan memori ini sebagai addressable.

1196
00:56:12,450 --> 00:56:16,630
Dalam erti kata lain, setiap satu daripada
lokasi dalam ingatan, dalam perkakasan,

1197
00:56:16,630 --> 00:56:18,030
mempunyai alamat yang unik.

1198
00:56:18,030 --> 00:56:22,020
>> Ia bukan seperti yang kompleks seperti One Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Sebaliknya, ia hanya nombor.

1200
00:56:23,830 --> 00:56:27,930
Ini adalah bilangan bait sifar, ini adalah
satu, ini adalah dua, ini adalah tiga,

1201
00:56:27,930 --> 00:56:30,327
dan ini adalah 41.

1202
00:56:30,327 --> 00:56:30,910
Tunggu sebentar.

1203
00:56:30,910 --> 00:56:32,510
Saya fikir saya berkata 42 sebentar tadi.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Saya mula mengira pada sifar,
jadi itulah sebenarnya betul.

1206
00:56:37,772 --> 00:56:40,980
Sekarang kita tidak mempunyai untuk benar-benar menarik ia
sebagai grid, dan jika anda menarik ia sebagai grid

1207
00:56:40,980 --> 00:56:43,520
Saya rasa perkara yang sebenarnya
mendapatkan sedikit mengelirukan.

1208
00:56:43,520 --> 00:56:46,650
Apa programmer akan,
dalam fikiran mereka sendiri,

1209
00:56:46,650 --> 00:56:50,310
umumnya berfikir ini
memori yang sama seperti pita,

1210
00:56:50,310 --> 00:56:53,340
seperti sekeping pita pelekat
yang hanya berjalan dan terus selama-lamanya

1211
00:56:53,340 --> 00:56:54,980
atau sehingga anda kehabisan memori.

1212
00:56:54,980 --> 00:56:59,200
Jadi cara yang lebih biasa untuk menarik
dan hanya berfikir tentang memori

1213
00:56:59,200 --> 00:57:03,710
akan bahawa ini adalah bait sifar, satu,
dua, tiga, dan kemudian dot, dot, dot.

1214
00:57:03,710 --> 00:57:07,650
Dan anda mempunyai 42 bytes seperti jumlah, walaupun
walaupun secara fizikal ia mungkin sebenarnya

1215
00:57:07,650 --> 00:57:09,480
menjadi sesuatu yang lebih seperti ini.

1216
00:57:09,480 --> 00:57:12,850
>> Jadi, jika anda sekarang memikirkan anda
memori ini, seperti pita,

1217
00:57:12,850 --> 00:57:17,640
ini adalah apa yang programmer lagi
akan memanggil pelbagai ingatan.

1218
00:57:17,640 --> 00:57:20,660
Dan apabila anda mahu untuk benar-benar menyimpan
sesuatu dalam memori komputer,

1219
00:57:20,660 --> 00:57:23,290
biasanya anda lakukan kedai perkara
back-to-back untuk back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Oleh itu, kita telah bercakap tentang nombor.

1221
00:57:25,010 --> 00:57:30,880
Dan apabila saya mahu menyelesaikan masalah
seperti empat, satu, tiga, dua,

1222
00:57:30,880 --> 00:57:33,820
walaupun saya hanya melukis
hanya pada nombor empat, satu, tiga,

1223
00:57:33,820 --> 00:57:39,490
dua di atas kapal, komputer akan
benar-benar mempunyai persediaan ini dalam ingatan.

1224
00:57:39,490 --> 00:57:43,347
>> Dan apa yang akan menjadi sebelah
dua dalam ingatan komputer?

1225
00:57:43,347 --> 00:57:44,680
Well, tidak ada jawapan untuk itu.

1226
00:57:44,680 --> 00:57:45,770
Kami tidak tahu.

1227
00:57:45,770 --> 00:57:48,200
Dan selagi
komputer tidak memerlukannya,

1228
00:57:48,200 --> 00:57:51,440
ia tidak perlu mengambil berat apa yang akan datang
kepada nombor ia berat tentang.

1229
00:57:51,440 --> 00:57:55,130
Dan apabila saya berkata sebelum ini bahawa komputer
hanya boleh melihat satu alamat pada satu masa,

1230
00:57:55,130 --> 00:57:56,170
ini adalah jenis mengapa.

1231
00:57:56,170 --> 00:57:59,490
>> Tidak seperti rekod
pemain dan kepala membaca

1232
00:57:59,490 --> 00:58:03,030
hanya dapat melihat yang tertentu
alur dalam rekod lama-sekolah fizikal

1233
00:58:03,030 --> 00:58:06,500
pada satu masa, sama
boleh komputer terima kasih

1234
00:58:06,500 --> 00:58:09,810
untuk CPU dan yang
Intel set arahan,

1235
00:58:09,810 --> 00:58:12,480
antara yang arahan
dibaca daripada ingatan

1236
00:58:12,480 --> 00:58:15,590
atau simpan ke memory-- yang
komputer hanya boleh melihat

1237
00:58:15,590 --> 00:58:19,210
di satu lokasi di time-- yang
kadang-kadang kombinasi,

1238
00:58:19,210 --> 00:58:21,770
tetapi benar-benar hanya satu lokasi pada satu masa.

1239
00:58:21,770 --> 00:58:24,770
Oleh itu, apabila kita telah melakukan
ini pelbagai algoritma,

1240
00:58:24,770 --> 00:58:28,110
Saya tidak hanya menulis dalam
vacuum-- empat, satu, tiga, dua.

1241
00:58:28,110 --> 00:58:30,849
Nombor-nombor tersebut sebenarnya milik
suatu tempat fizikal dalam ingatan.

1242
00:58:30,849 --> 00:58:32,890
Jadi, terdapat sedikit kecil
transistor atau beberapa jenis

1243
00:58:32,890 --> 00:58:35,840
elektronik di bawahnya
hood menyimpan nilai-nilai ini.

1244
00:58:35,840 --> 00:58:40,460
>> Dan secara keseluruhan, berapa banyak bit adalah
terlibat sekarang, hanya untuk menjadi jelas?

1245
00:58:40,460 --> 00:58:45,580
Jadi ini adalah empat bait, atau
kini ia 32 bit jumlah.

1246
00:58:45,580 --> 00:58:49,280
Jadi sebenarnya ada 32 sifar dan
yang mengarang empat perkara.

1247
00:58:49,280 --> 00:58:52,070
Terdapat juga lebih di sini, tetapi
sekali lagi kita tidak peduli tentang itu.

1248
00:58:52,070 --> 00:58:55,120
>> Jadi sekarang mari kita tanya lain
soalan menggunakan memori,

1249
00:58:55,120 --> 00:58:57,519
kerana bahawa pada akhir
hari ini adalah dalam varians.

1250
00:58:57,519 --> 00:59:00,310
Tidak kira apa yang kita lakukan dengan
komputer, pada akhir hari

1251
00:59:00,310 --> 00:59:02,560
perkakasan yang masih
sama di bawah hood.

1252
00:59:02,560 --> 00:59:04,670
Bagaimana saya akan menyimpan perkataan dalam sini?

1253
00:59:04,670 --> 00:59:09,710
Well, kata dalam komputer seperti
"Hey!" akan disimpan sama seperti ini.

1254
00:59:09,710 --> 00:59:12,300
Dan jika anda mahu yang lebih lama
perkataan, anda hanya boleh

1255
00:59:12,300 --> 00:59:19,120
menulis ganti itu dan mengatakan sesuatu
seperti "hello" dan kedai yang di sini.

1256
00:59:19,120 --> 00:59:23,930
>> Dan sebagainya di sini, juga, contiguousness ini
sebenarnya kelebihan,

1257
00:59:23,930 --> 00:59:26,530
kerana komputer hanya boleh
dibaca dari kanan ke kiri.

1258
00:59:26,530 --> 00:59:28,680
Tetapi di sini adalah satu soalan.

1259
00:59:28,680 --> 00:59:33,480
Dalam konteks perkataan ini,
h-e-l-l-o, tanda seru,

1260
00:59:33,480 --> 00:59:38,740
bagaimana mungkin komputer tahu di mana
perkataan bermula dan di mana perkataan itu berakhir?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Dalam konteks nombor,
bagaimana komputer

1263
00:59:43,800 --> 00:59:48,396
tahu berapa lama urutan
nombor adalah atau di mana ia bermula?

1264
00:59:48,396 --> 00:59:50,270
Nah, ternyata out--
dan kami tidak akan pergi terlalu banyak

1265
00:59:50,270 --> 00:59:54,970
ke tahap ini detail--
komputer bergerak barangan sekitar dalam ingatan

1266
00:59:54,970 --> 00:59:57,800
secara literal melalui alamat ini.

1267
00:59:57,800 --> 01:00:02,080
Jadi dalam komputer, jika anda
menulis kod untuk menyimpan perkara

1268
01:00:02,080 --> 01:00:05,800
seperti kata-kata, apa yang anda
benar-benar lakukan adalah menaip

1269
01:00:05,800 --> 01:00:11,320
ungkapan-ungkapan yang ingat di mana dalam
ingatan komputer kata-kata ini.

1270
01:00:11,320 --> 01:00:14,370
Jadi biarlah saya melakukan yang sangat,
contoh yang sangat mudah.

1271
01:00:14,370 --> 01:00:18,260
>> Saya akan pergi ke hadapan dan
membuka program teks yang mudah,

1272
01:00:18,260 --> 01:00:20,330
dan saya akan membuat
fail yang dipanggil hello.c.

1273
01:00:20,330 --> 01:00:22,849
Kebanyakan maklumat ini kita
tidak akan pergi ke dengan terperinci,

1274
01:00:22,849 --> 01:00:25,140
tetapi saya akan menulis
program dalam bahasa yang sama,

1275
01:00:25,140 --> 01:00:31,140
C. Ini adalah jauh lebih menakutkan,
Saya berpendapat, daripada calar,

1276
01:00:31,140 --> 01:00:32,490
tetapi ia sangat sama dalam semangat.

1277
01:00:32,490 --> 01:00:34,364
Malah, kerinting ini
jenis braces-- anda boleh sudah

1278
01:00:34,364 --> 01:00:37,820
memikirkan apa yang saya hanya melakukan seperti ini.

1279
01:00:37,820 --> 01:00:39,240
>> Mari kita buat ini, sebenarnya.

1280
01:00:39,240 --> 01:00:45,100
Apabila bendera hijau diklik,
lakukan yang berikut.

1281
01:00:45,100 --> 01:00:50,210
Saya hendak mencetak "hello."

1282
01:00:50,210 --> 01:00:51,500
Jadi sekarang ini adalah kod pseudo.

1283
01:00:51,500 --> 01:00:53,000
Saya jenis mengaburkan garis.

1284
01:00:53,000 --> 01:00:56,750
Dalam C, bahasa ini Saya bercakap
kira-kira, talian cetak ini hello

1285
01:00:56,750 --> 01:01:01,940
sebenarnya menjadi "printf" dengan
beberapa kurungan dan koma bertitik.

1286
01:01:01,940 --> 01:01:03,480
>> Tetapi ia adalah idea yang sama.

1287
01:01:03,480 --> 01:01:06,730
Dan ini sangat user-friendly
"Apabila bendera hijau diklik" menjadi

1288
01:01:06,730 --> 01:01:10,182
lebih sukar difahami "tidak sah utama int." yang

1289
01:01:10,182 --> 01:01:12,890
Dan ini benar-benar tidak mempunyai pemetaan,
jadi saya hanya akan mengabaikan itu.

1290
01:01:12,890 --> 01:01:17,210
Tetapi pendakap kerinting adalah seperti
kepingan teka-teki melengkung seperti ini.

1291
01:01:17,210 --> 01:01:18,700
>> Jadi anda jenis boleh sudah meneka.

1292
01:01:18,700 --> 01:01:22,357
Walaupun anda tidak pernah diprogramkan sebelum ini,
apakah program ini mungkin lakukan?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Mungkin mencetak hello
dengan tanda seru.

1295
01:01:28,000 --> 01:01:29,150
>> Jadi mari kita cuba.

1296
01:01:29,150 --> 01:01:30,800
Saya akan menyimpannya.

1297
01:01:30,800 --> 01:01:34,000
Dan ini, sekali lagi, yang sangat
persekitaran sekolah lama.

1298
01:01:34,000 --> 01:01:35,420
Saya tidak boleh klik, saya tidak boleh seret.

1299
01:01:35,420 --> 01:01:36,910
Saya perlu menaip arahan.

1300
01:01:36,910 --> 01:01:41,320
Jadi saya mahu menjalankan program saya, jadi
Saya mungkin melakukan ini, seperti hello.c.

1301
01:01:41,320 --> 01:01:42,292
Itulah fail saya berlari.

1302
01:01:42,292 --> 01:01:43,500
Tetapi tunggu, saya hilang langkah.

1303
01:01:43,500 --> 01:01:46,470
Apa yang kita katakan adalah sesuatu yang perlu
langkah untuk bahasa seperti C?

1304
01:01:46,470 --> 01:01:49,470
Saya baru sahaja ditulis sumber
kod, tetapi apa yang saya perlukan?

1305
01:01:49,470 --> 01:01:50,670
Ya, saya perlu pengkompil.

1306
01:01:50,670 --> 01:01:57,670
Maka pada Mac saya di sini, saya mempunyai
program dipanggil GCC, GNU C compiler,

1307
01:01:57,670 --> 01:02:03,990
yang membolehkan saya untuk berpatah this--
kod sumber saya ke dalam, kami akan memanggilnya,

1308
01:02:03,990 --> 01:02:04,930
kod mesin.

1309
01:02:04,930 --> 01:02:10,180
>> Dan saya boleh melihat bahawa,
sekali lagi, seperti berikut, ini

1310
01:02:10,180 --> 01:02:14,090
adalah sifar dan orang-orang yang saya
dicipta dari kod sumber saya,

1311
01:02:14,090 --> 01:02:15,730
semua sifar dan satu.

1312
01:02:15,730 --> 01:02:17,770
Dan jika saya mahu menjalankan
saya program-- ia berlaku

1313
01:02:17,770 --> 01:02:23,010
untuk dipanggil a.out untuk
reasons-- sejarah "hello."

1314
01:02:23,010 --> 01:02:24,070
Saya boleh berjalan lagi.

1315
01:02:24,070 --> 01:02:25,690
Hello, hello, hello.

1316
01:02:25,690 --> 01:02:27,430
Dan ia seolah-olah bekerja.

1317
01:02:27,430 --> 01:02:31,000
>> Tetapi itu bermakna suatu tempat di saya
memori komputer adalah kata-kata

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, tanda seru.

1319
01:02:35,279 --> 01:02:38,070
Dan ternyata, hanya sebagai diketepikan,
apa yang komputer akan biasanya

1320
01:02:38,070 --> 01:02:40,550
lakukan supaya ia tahu di mana
perkara mula dan end-- ia

1321
01:02:40,550 --> 01:02:42,460
akan meletakkan simbol khas di sini.

1322
01:02:42,460 --> 01:02:46,064
Dan konvensyen adalah untuk meletakkan
nombor sifar pada akhir perkataan

1323
01:02:46,064 --> 01:02:48,230
supaya anda tahu di mana ia
sebenarnya berakhir, supaya anda

1324
01:02:48,230 --> 01:02:52,750
tidak menyimpan mencetak lebih banyak
watak-watak daripada yang anda sebenarnya berniat.

1325
01:02:52,750 --> 01:02:55,400
>> Tetapi bisa dibesarkan di sini, walaupun
walaupun ini agak sukar difahami,

1326
01:02:55,400 --> 01:02:58,140
adalah bahawa ia akhirnya
agak mudah.

1327
01:02:58,140 --> 01:03:04,550
Anda telah diberi jenis pita, kosong
ruang di mana anda boleh menulis surat.

1328
01:03:04,550 --> 01:03:07,150
Anda hanya perlu mempunyai
simbol khas, seperti sewenang-wenangnya

1329
01:03:07,150 --> 01:03:10,316
nombor sifar, untuk meletakkan pada akhir
kata-kata anda supaya komputer tahu,

1330
01:03:10,316 --> 01:03:13,410
oh, saya perlu berhenti percetakan selepas
Saya melihat tanda seru.

1331
01:03:13,410 --> 01:03:16,090
Oleh kerana perkara yang akan datang terdapat
adalah nilai ASCII sifar,

1332
01:03:16,090 --> 01:03:19,125
atau watak nol sebagai
ada orang yang memanggilnya.

1333
01:03:19,125 --> 01:03:21,500
Tetapi ada jenis masalah
di sini, dan mari kita kembali semula

1334
01:03:21,500 --> 01:03:23,320
kepada nombor untuk seketika.

1335
01:03:23,320 --> 01:03:28,720
Katakan yang saya lakukan, sebenarnya,
mempunyai pelbagai nombor,

1336
01:03:28,720 --> 01:03:30,730
dan andaikan bahawa
program saya menulis adalah

1337
01:03:30,730 --> 01:03:34,680
seperti buku gred untuk guru
dan kelas guru.

1338
01:03:34,680 --> 01:03:38,720
Dan program ini membolehkan dia atau dia
menaip dalam skor pelajar mereka

1339
01:03:38,720 --> 01:03:39,960
pada kuiz.

1340
01:03:39,960 --> 01:03:43,750
Dan andaikan bahawa pelajar mendapat
100 pada kuiz pertama mereka, mungkin

1341
01:03:43,750 --> 01:03:49,920
seperti 80 pada yang akan datang, maka
75, maka 90 kuiz keempat.

1342
01:03:49,920 --> 01:03:54,150
>> Jadi pada ketika ini dalam cerita,
array adalah saiz empat.

1343
01:03:54,150 --> 01:03:58,470
Ada memori benar-benar lebih dalam
komputer, tetapi pelbagai, jadi untuk bercakap,

1344
01:03:58,470 --> 01:04:00,350
adalah saiz empat.

1345
01:04:00,350 --> 01:04:06,060
Katakan sekarang bahawa guru mahu
untuk menetapkan kuiz kelima kelas.

1346
01:04:06,060 --> 01:04:08,510
Nah, salah satu daripada perkara-perkara yang
atau dia akan perlu lakukan

1347
01:04:08,510 --> 01:04:10,650
kini menyimpan nilai tambahan di sini.

1348
01:04:10,650 --> 01:04:15,490
Tetapi jika array guru mempunyai
diwujudkan dalam program ini adalah saiz untuk,

1349
01:04:15,490 --> 01:04:22,440
salah satu masalah dengan array adalah yang
anda tidak boleh hanya terus menambah kepada ingatan.

1350
01:04:22,440 --> 01:04:26,470
Kerana bagaimana jika satu lagi sebahagian daripada
program mempunyai perkataan "hey" di sana?

1351
01:04:26,470 --> 01:04:29,650
>> Dengan kata lain, ingatan saya boleh
digunakan untuk apa-apa dalam program.

1352
01:04:29,650 --> 01:04:33,250
Dan jika terlebih dahulu saya menaip dalam, hey,
Saya hendak input empat markah kuiz,

1353
01:04:33,250 --> 01:04:34,784
mereka mungkin pergi di sini dan di sini.

1354
01:04:34,784 --> 01:04:37,700
Dan jika anda tiba-tiba berubah fikiran
kemudian dan berkata saya mahu kuiz kelima

1355
01:04:37,700 --> 01:04:40,872
skor, anda tidak boleh hanya
meletakkan ia di mana sahaja yang anda mahu,

1356
01:04:40,872 --> 01:04:42,580
kerana apa jika ini
memori yang digunakan

1357
01:04:42,580 --> 01:04:45,990
sesuatu else-- beberapa program lain
atau beberapa ciri lain program

1358
01:04:45,990 --> 01:04:46,910
bahawa anda berjalan?

1359
01:04:46,910 --> 01:04:50,650
Jadi, anda perlu berfikir terlebih dahulu
bagaimana anda mahu menyimpan data anda,

1360
01:04:50,650 --> 01:04:54,480
kerana sekarang anda telah dicat
diri anda ke dalam sudut digital.

1361
01:04:54,480 --> 01:04:57,280
>> Jadi seorang guru mungkin sebaliknya
mengatakan apabila menulis program

1362
01:04:57,280 --> 01:04:59,360
untuk menyimpan nya
gred, anda tahu apa?

1363
01:04:59,360 --> 01:05:04,180
Saya akan meminta,
semasa menulis program saya,

1364
01:05:04,180 --> 01:05:12,070
yang saya mahu sifar, satu, dua, tiga,
empat, lima, enam, lapan gred jumlah.

1365
01:05:12,070 --> 01:05:15,320
Jadi satu, dua, tiga, empat,
lima, enam, tujuh, lapan.

1366
01:05:15,320 --> 01:05:18,612
guru boleh hanya lebih-memperuntukkan
memori semasa menulis program masing-masing

1367
01:05:18,612 --> 01:05:19,570
dan berkata, anda tahu apa?

1368
01:05:19,570 --> 01:05:22,236
Saya tidak akan memberikan lebih
daripada lapan kuiz dalam sesuatu semester.

1369
01:05:22,236 --> 01:05:23,130
Itu hanya gila.

1370
01:05:23,130 --> 01:05:24,470
Saya tidak akan memperuntukkan bahawa.

1371
01:05:24,470 --> 01:05:28,270
Supaya dengan cara ini dia mempunyai
fleksibiliti untuk skor kedai pelajar,

1372
01:05:28,270 --> 01:05:33,010
seperti 75, 90, dan mungkin satu tambahan di mana
pelajar mendapat kredit tambahan, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Tetapi jika guru tidak pernah
menggunakan ketiga-tiga ruang,

1374
01:05:36,130 --> 01:05:38,860
ada Fleet intuitif di sini.

1375
01:05:38,860 --> 01:05:41,410
Dia hanya membazirkan ruang.

1376
01:05:41,410 --> 01:05:44,790
Jadi dalam erti kata lain, ini
tradeoff biasa dalam pengaturcaraan

1377
01:05:44,790 --> 01:05:48,241
di mana anda boleh sama ada memperuntukkan
memori tepat seberapa banyak yang anda mahu,

1378
01:05:48,241 --> 01:05:51,490
terbalik yang adalah bahawa anda super
efficient-- anda tidak membazir

1379
01:05:51,490 --> 01:05:54,640
di all-- tetapi keburukan yang
adalah apa yang jika anda menukar fikiran anda apabila

1380
01:05:54,640 --> 01:05:58,780
menggunakan program yang anda mahu menyimpan
lebih banyak data daripada anda asalnya bertujuan.

1381
01:05:58,780 --> 01:06:03,030
>> Jadi mungkin penyelesaian adalah, maka,
menulis program anda dalam apa-apa cara

1382
01:06:03,030 --> 01:06:05,605
bahawa mereka menggunakan lebih banyak memori
melebihi daripada keperluannya.

1383
01:06:05,605 --> 01:06:07,730
Dengan cara ini anda tidak akan
untuk menghadapi masalah itu,

1384
01:06:07,730 --> 01:06:09,730
tetapi anda satu pembaziran.

1385
01:06:09,730 --> 01:06:12,960
Dan memori yang lebih program anda menggunakan,
seperti yang kita bincangkan semalam, kurang

1386
01:06:12,960 --> 01:06:15,410
memori yang tersedia
untuk program lain,

1387
01:06:15,410 --> 01:06:18,790
lebih cepat komputer anda mungkin memperlahankan
turun kerana ingatan maya.

1388
01:06:18,790 --> 01:06:22,670
Dan supaya penyelesaian yang ideal mungkin apa?

1389
01:06:22,670 --> 01:06:24,610
>> Under-Memperuntukkan kelihatan buruk.

1390
01:06:24,610 --> 01:06:27,030
Lebih-Memperuntukkan kelihatan buruk.

1391
01:06:27,030 --> 01:06:31,120
Jadi apa yang mungkin menjadi penyelesaian yang lebih baik?

1392
01:06:31,120 --> 01:06:32,390
Pembahagian semula.

1393
01:06:32,390 --> 01:06:33,590
Menjadi lebih dinamik.

1394
01:06:33,590 --> 01:06:37,520
Jangan memaksa diri anda untuk memilih
priori, pada awal, apa yang anda mahu.

1395
01:06:37,520 --> 01:06:41,370
Dan sudah tentu tidak lebih-memperuntukkan,
supaya kamu jangan membazir.

1396
01:06:41,370 --> 01:06:45,770
>> Dan sebagainya untuk mencapai matlamat itu, kita
perlu membuang struktur data ini,

1397
01:06:45,770 --> 01:06:48,100
jadi untuk bercakap, jauh.

1398
01:06:48,100 --> 01:06:51,080
Dan supaya apa yang programmer
biasanya akan menggunakan

1399
01:06:51,080 --> 01:06:55,940
adalah sesuatu yang tidak yang dikenali
mudah tetapi senarai berpaut.

1400
01:06:55,940 --> 01:07:00,860
Dalam erti kata lain, dia akan
mula memikirkan ingatan mereka

1401
01:07:00,860 --> 01:07:05,280
sebagai jenis yang bentuk yang mereka
boleh menarik dengan cara yang berikut.

1402
01:07:05,280 --> 01:07:08,520
Jika saya mahu menyimpan satu nombor dalam
yang program-- jadi ia September,

1403
01:07:08,520 --> 01:07:12,600
Saya telah diberikan pelajar saya kuiz; saya mahu
untuk menyimpan kuiz pertama pelajar,

1404
01:07:12,600 --> 01:07:16,220
dan mereka mendapat 100 pada saya it--
Aku akan meminta komputer saya,

1405
01:07:16,220 --> 01:07:19,540
melalui program yang saya telah
bertulis, untuk satu sebahagian memori.

1406
01:07:19,540 --> 01:07:22,570
Dan saya akan untuk menyimpan
nombor 100 di dalamnya, dan itu sahaja.

1407
01:07:22,570 --> 01:07:24,820
>> Kemudian beberapa minggu kemudian
apabila saya kuiz kedua saya,

1408
01:07:24,820 --> 01:07:27,890
dan ia adalah masa untuk menaip
dalam 90%, saya akan

1409
01:07:27,890 --> 01:07:32,129
untuk meminta komputer, hey, komputer,
boleh saya mempunyai satu lagi sebahagian memori?

1410
01:07:32,129 --> 01:07:34,170
Ia akan memberi saya ini
sebahagian kosong memori.

1411
01:07:34,170 --> 01:07:39,370
Saya akan dimasukkan ke dalam jumlah 90,
tetapi dalam program saya entah bagaimana atau other--

1412
01:07:39,370 --> 01:07:42,100
dan kami tidak akan bimbang tentang
sintaks untuk this-- saya perlu

1413
01:07:42,100 --> 01:07:44,430
entah bagaimana rantai perkara-perkara ini bersama-sama.

1414
01:07:44,430 --> 01:07:47,430
Dan saya akan rantai mereka bersama-sama dengan
apa yang kelihatan seperti anak panah di sini.

1415
01:07:47,430 --> 01:07:50,050
>> Kuiz yang ketiga yang datang,
Saya akan berkata, hey, komputer,

1416
01:07:50,050 --> 01:07:51,680
memberi saya satu lagi sebahagian memori.

1417
01:07:51,680 --> 01:07:54,660
Dan saya akan meletakkan
apa pun ia, seperti 75,

1418
01:07:54,660 --> 01:07:56,920
dan saya perlu rantaian ini
bersama-sama sekarang entah bagaimana.

1419
01:07:56,920 --> 01:08:00,290
kuiz Keempat datang bersama-sama, dan mungkin
itulah ke arah akhir semester.

1420
01:08:00,290 --> 01:08:03,140
Dan ketika itu program saya
mungkin menggunakan memori

1421
01:08:03,140 --> 01:08:05,540
di seluruh tempat, di seluruh fizikal.

1422
01:08:05,540 --> 01:08:08,170
Dan sebagainya hanya untuk tendangan, Saya
akan menarik ini sebagainya

1423
01:08:08,170 --> 01:08:11,260
quiz-- saya terlupa apa yang ia adalah; Saya
rasa mungkin 80 atau something--

1424
01:08:11,260 --> 01:08:12,500
cara di sini.

1425
01:08:12,500 --> 01:08:15,920
>> Tetapi itu tidak mengapa, kerana bergambar
Saya akan menarik garis ini.

1426
01:08:15,920 --> 01:08:19,063
Dalam erti kata lain, pada hakikatnya,
dalam perkakasan komputer anda,

1427
01:08:19,063 --> 01:08:20,979
skor pertama mungkin
berakhir di sini kerana ia

1428
01:08:20,979 --> 01:08:22,529
di awal semester.

1429
01:08:22,529 --> 01:08:25,810
Yang seterusnya mungkin berakhir di sini
kerana sedikit masa telah berlalu

1430
01:08:25,810 --> 01:08:27,210
dan program terus berjalan.

1431
01:08:27,210 --> 01:08:30,060
Rata-rata yang akan datang, yang
75, mungkin di sini.

1432
01:08:30,060 --> 01:08:33,420
Dan skor yang terakhir mungkin
80, yang di sini.

1433
01:08:33,420 --> 01:08:38,729
>> Jadi pada hakikatnya, secara fizikal, ini mungkin
apa memori komputer anda kelihatan seperti.

1434
01:08:38,729 --> 01:08:41,569
Tetapi ini bukan mental berguna
paradigma seorang pengaturcara komputer.

1435
01:08:41,569 --> 01:08:44,649
Mengapa anda perlu mengambil berat di mana
palang pintu data anda berakhir?

1436
01:08:44,649 --> 01:08:46,200
Anda hanya mahu untuk menyimpan data.

1437
01:08:46,200 --> 01:08:49,390
>> Ini adalah jenis seperti perbincangan kita
awal lukisan kiub.

1438
01:08:49,390 --> 01:08:52,200
Mengapa kamu peduli apa
sudut adalah kiub

1439
01:08:52,200 --> 01:08:53,740
dan bagaimana anda perlu untuk menghidupkan untuk menarik ia?

1440
01:08:53,740 --> 01:08:54,950
Anda hanya mahu kiub.

1441
01:08:54,950 --> 01:08:57,359
Begitu juga di sini, anda
hanya mahu buku gred.

1442
01:08:57,359 --> 01:08:59,559
Anda hanya mahu memikirkan
ini sebagai senarai nombor.

1443
01:08:59,559 --> 01:09:01,350
Siapa yang peduli bagaimana ia
dilaksanakan dalam perkakasan?

1444
01:09:01,350 --> 01:09:05,180
>> Jadi abstraksi sekarang
adalah gambar ini di sini.

1445
01:09:05,180 --> 01:09:07,580
Ini adalah senarai dikaitkan, kerana
programmer akan memanggilnya,

1446
01:09:07,580 --> 01:09:10,640
setakat yang anda mempunyai
senarai, jelas nombor.

1447
01:09:10,640 --> 01:09:14,990
Tetapi ia dikaitkan bergambar
melalui anak panah ini,

1448
01:09:14,990 --> 01:09:18,510
dan semua anak panah ini ialah- bawah
hood, jika anda ingin tahu,

1449
01:09:18,510 --> 01:09:23,210
ingat bahawa perkakasan fizikal kita mempunyai
alamat sifar, satu, dua, tiga, empat.

1450
01:09:23,210 --> 01:09:28,465
Semua anak panah ini adalah seperti peta
atau arahan, di mana jika 90 is-- sekarang

1451
01:09:28,465 --> 01:09:29,090
Saya mendapat untuk mengira.

1452
01:09:29,090 --> 01:09:31,750
>> Sifar, satu, dua, tiga,
empat, lima, enam, tujuh.

1453
01:09:31,750 --> 01:09:35,640
Ia kelihatan seperti 90 adalah di
memori nombor alamat tujuh.

1454
01:09:35,640 --> 01:09:38,460
Semua anak panah ini adalah
seperti sekerap sedikit kertas

1455
01:09:38,460 --> 01:09:42,439
yang yang memberi arahan kepada
program yang mengatakan ikut peta ini

1456
01:09:42,439 --> 01:09:43,880
untuk sampai ke lokasi tujuh.

1457
01:09:43,880 --> 01:09:46,680
Dan di sana anda akan mencari yang
skor kuiz kedua pelajar.

1458
01:09:46,680 --> 01:09:52,100
Sementara itu, 75-- jika saya terus ini,
ini adalah tujuh, lapan, sembilan, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Ini anak panah lain hanya mewakili
Peta ke lokasi memori 15.

1461
01:09:59,080 --> 01:10:02,550
Tetapi sekali lagi, pengaturcara umumnya tidak
tidak mengambil berat tentang tahap ini lanjut.

1462
01:10:02,550 --> 01:10:05,530
Dan dalam kebanyakan setiap program
bahasa hari ini, pengaturcara

1463
01:10:05,530 --> 01:10:10,490
tidak akan tahu di mana dalam ingatan
nombor-nombor ini sebenarnya.

1464
01:10:10,490 --> 01:10:14,830
Semua dia mempunyai untuk mengambil berat tentang adalah
bahawa mereka entah bagaimana dikaitkan bersama-sama

1465
01:10:14,830 --> 01:10:18,390
dalam struktur data seperti ini.

1466
01:10:18,390 --> 01:10:21,580
>> Tetapi ternyata tidak
untuk mendapatkan terlalu teknikal.

1467
01:10:21,580 --> 01:10:27,430
Tetapi hanya kerana kita boleh mungkin
mampu untuk mempunyai perbincangan ini di sini,

1468
01:10:27,430 --> 01:10:33,630
katalah kita semula
isu ini di sini array.

1469
01:10:33,630 --> 01:10:35,780
Mari kita lihat jika kita kesal kerana pergi di sini.

1470
01:10:35,780 --> 01:10:42,950
Ini adalah 100, 90, 75, dan 80.

1471
01:10:42,950 --> 01:10:44,980
>> Biar saya secara ringkas membuat tuntutan ini.

1472
01:10:44,980 --> 01:10:48,980
Ini adalah pelbagai, dan sekali lagi,
ciri-ciri penting array

1473
01:10:48,980 --> 01:10:52,400
adalah bahawa semua data anda kembali ke
kembali ke belakang dalam memory-- literal

1474
01:10:52,400 --> 01:10:56,830
satu bait atau mungkin empat bait,
beberapa nombor tetap bait jauh.

1475
01:10:56,830 --> 01:11:00,710
Dalam senarai berpaut, yang kita mungkin menarik
seperti ini, di bawah hood yang

1476
01:11:00,710 --> 01:11:02,000
tahu di mana barangan itu?

1477
01:11:02,000 --> 01:11:03,630
Ia juga tidak perlu mengalir seperti ini.

1478
01:11:03,630 --> 01:11:06,050
Antara data boleh menjadi
kembali ke sebelah kiri di sana.

1479
01:11:06,050 --> 01:11:07,530
Anda tidak tahu.

1480
01:11:07,530 --> 01:11:15,430
>> Dan sebagainya dengan array, anda mempunyai
ciri dikenali sebagai capaian rawak.

1481
01:11:15,430 --> 01:11:20,570
Dan apa cara akses rawak adalah
bahawa komputer boleh melompat serta-merta

1482
01:11:20,570 --> 01:11:22,730
kepada mana-mana lokasi dalam array.

1483
01:11:22,730 --> 01:11:23,580
Mengapa?

1484
01:11:23,580 --> 01:11:26,000
Kerana komputer itu tahu
lokasi itu yang pertama adalah

1485
01:11:26,000 --> 01:11:29,540
sifar, satu, dua, dan tiga.

1486
01:11:29,540 --> 01:11:33,890
>> Dan jadi jika anda mahu pergi dari
elemen ini kepada elemen seterusnya,

1487
01:11:33,890 --> 01:11:36,099
anda secara literal, dalam
fikiran komputer, hanya menambah satu.

1488
01:11:36,099 --> 01:11:39,140
Jika anda ingin pergi ke elemen yang ketiga,
hanya menambah one-- elemen seterusnya, hanya

1489
01:11:39,140 --> 01:11:40,290
menambah satu.

1490
01:11:40,290 --> 01:11:42,980
Walau bagaimanapun, dalam versi ini
cerita, rasa

1491
01:11:42,980 --> 01:11:46,080
komputer kini sedang
pada atau berurusan dengan nombor 100.

1492
01:11:46,080 --> 01:11:49,770
Bagaimana anda mendapatkan ke depan
gred dalam buku gred?

1493
01:11:49,770 --> 01:11:52,560
>> Anda perlu mengambil masa tujuh
langkah-langkah, yang sewenang-wenangnya.

1494
01:11:52,560 --> 01:11:58,120
Untuk sampai ke satu depan, anda perlu untuk
mengambil masa lapan langkah-langkah lain untuk sampai ke 15.

1495
01:11:58,120 --> 01:12:02,250
Dalam erti kata lain, ia bukan satu
jurang yang berterusan antara nombor,

1496
01:12:02,250 --> 01:12:04,857
dan sebagainya ia hanya mengambil
komputer lebih banyak masa titik.

1497
01:12:04,857 --> 01:12:06,940
Komputer mempunyai untuk mencari
melalui memori untuk

1498
01:12:06,940 --> 01:12:08,990
untuk mencari apa yang anda cari.

1499
01:12:08,990 --> 01:12:14,260
>> Jadi manakala array cenderung menjadi
data yang cepat structure-- kerana anda

1500
01:12:14,260 --> 01:12:17,610
boleh benar-benar hanya melakukan aritmetik mudah
dan mendapatkan di mana anda mahu dengan menambah satu,

1501
01:12:17,610 --> 01:12:21,300
untuk instance-- senarai berpaut,
kausembelih ciri asal.

1502
01:12:21,300 --> 01:12:24,020
Anda tidak boleh hanya pergi dari pertama
untuk kedua ketiga keempat.

1503
01:12:24,020 --> 01:12:25,240
Anda perlu mengikuti peta.

1504
01:12:25,240 --> 01:12:28,160
Anda perlu mengambil langkah-langkah yang lebih
untuk sampai ke nilai-nilai, yang

1505
01:12:28,160 --> 01:12:30,230
seolah-olah menjadi menambah kos.

1506
01:12:30,230 --> 01:12:35,910
Jadi, kita membayar harga yang, tetapi apa yang
ciri yang Dan telah memohon di sini?

1507
01:12:35,910 --> 01:12:38,110
Apakah senarai berpaut
nampaknya membolehkan kita untuk melakukan,

1508
01:12:38,110 --> 01:12:40,240
yang merupakan asal-usul
cerita tertentu ini?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Tepat sekali.

1511
01:12:43,830 --> 01:12:46,220
A saiz dinamik kepadanya.

1512
01:12:46,220 --> 01:12:48,040
Kita boleh menambah kepada senarai ini.

1513
01:12:48,040 --> 01:12:51,430
Kami juga boleh mengecutkan senarai, jadi
bahawa kita hanya menggunakan memori sebanyak

1514
01:12:51,430 --> 01:12:55,560
seperti yang kita benar-benar mahu dan sebagainya
kami tidak pernah lebih-Memperuntukkan.

1515
01:12:55,560 --> 01:12:58,470
>> Kini hanya menjadi benar-benar nit-cerewet,
ada kos tersembunyi.

1516
01:12:58,470 --> 01:13:01,980
Jadi, anda tidak boleh hanya beritahu saya meyakinkan
anda bahawa ini adalah tradeoff menarik.

1517
01:13:01,980 --> 01:13:04,190
Ada kos tersembunyi lain di sini.

1518
01:13:04,190 --> 01:13:06,550
Manfaat ini, jelas,
ialah kita mendapatkan dinamik.

1519
01:13:06,550 --> 01:13:10,359
Jika saya mahu elemen lain, saya boleh hanya
menarik dan meletakkan nombor di sana.

1520
01:13:10,359 --> 01:13:12,150
Dan kemudian saya boleh menghubungkannya
dengan gambar di sini,

1521
01:13:12,150 --> 01:13:14,970
sedangkan di sini, sekali lagi, jika saya telah
dicat diri saya ke satu sudut,

1522
01:13:14,970 --> 01:13:19,410
jika sesuatu yang lain telah menggunakan
memori di sini, saya daripada nasib.

1523
01:13:19,410 --> 01:13:21,700
Saya telah dicat diri saya ke sudut.

1524
01:13:21,700 --> 01:13:24,390
>> Tetapi apa yang tersembunyi
kos dalam gambar ini?

1525
01:13:24,390 --> 01:13:27,690
Ia bukan hanya jumlah yang
masa yang diperlukan

1526
01:13:27,690 --> 01:13:29,870
untuk pergi dari sini ke sini,
iaitu tujuh langkah, kemudian

1527
01:13:29,870 --> 01:13:32,820
lapan langkah-langkah, yang lebih daripada satu.

1528
01:13:32,820 --> 01:13:34,830
Apa yang lain kos tersembunyi?

1529
01:13:34,830 --> 01:13:35,440
Bukan sahaja masa.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Maklumat tambahan boleh
perlu untuk mencapai gambar ini.

1532
01:13:49,940 --> 01:13:53,210
>> Ya, peta itu, mereka sisa sedikit
kertas, kerana saya terus menggambarkan mereka sebagai.

1533
01:13:53,210 --> 01:13:55,650
Ini arrows-- mereka tidak bebas.

1534
01:13:55,650 --> 01:13:57,660
A computer-- anda tahu
apa komputer mempunyai.

1535
01:13:57,660 --> 01:13:58,790
Ia mempunyai sifar dan satu.

1536
01:13:58,790 --> 01:14:03,170
Jika anda mahu untuk mewakili anak panah atau
peta atau nombor, anda memerlukan ingatan.

1537
01:14:03,170 --> 01:14:05,950
Jadi harga lain yang anda
membayar untuk senarai berpaut,

1538
01:14:05,950 --> 01:14:09,070
sains komputer biasa
sumber, juga ruang.

1539
01:14:09,070 --> 01:14:11,710
>> Dan sesungguhnya begitu, jadi biasa,
antara melepas

1540
01:14:11,710 --> 01:14:15,580
dalam mereka bentuk kejuruteraan perisian
sistem adalah masa dan space--

1541
01:14:15,580 --> 01:14:18,596
adalah dua daripada bahan-bahan anda, dua
bahan-bahan yang paling mahal anda.

1542
01:14:18,596 --> 01:14:21,220
Ini menelan belanja saya lebih banyak masa
kerana saya perlu mengikuti peta ini,

1543
01:14:21,220 --> 01:14:25,730
tetapi ia juga menelan belanja saya lebih banyak ruang
kerana saya perlu menjaga peta ini sekitar.

1544
01:14:25,730 --> 01:14:28,730
Jadi harapan, kerana kita ada jenis
dibincangkan lebih semalam dan hari ini,

1545
01:14:28,730 --> 01:14:31,720
adalah bahawa faedah
akan melebihi kos.

1546
01:14:31,720 --> 01:14:33,870
>> Tetapi tidak ada penyelesaian yang jelas di sini.

1547
01:14:33,870 --> 01:14:35,870
Mungkin ia adalah better--
cepat la dan kotor,

1548
01:14:35,870 --> 01:14:38,660
sebagai Kareem dicadangkan earlier--
untuk membuang memori pada masalah ini.

1549
01:14:38,660 --> 01:14:42,520
Hanya membeli lebih banyak memori, berfikir kurang
keras tentang menyelesaikan masalah ini,

1550
01:14:42,520 --> 01:14:44,595
dan menyelesaikannya dengan cara yang lebih mudah.

1551
01:14:44,595 --> 01:14:46,720
Dan sesungguhnya sebelum ini, apabila
kita bercakap tentang melepas,

1552
01:14:46,720 --> 01:14:49,190
ia bukan ruang dalam
komputer dan masa.

1553
01:14:49,190 --> 01:14:51,810
Ia adalah masa pemaju, yang
lagi sumber lain.

1554
01:14:51,810 --> 01:14:54,829
>> Jadi sekali lagi, ia adalah tindakan penyeimbangan ini
cuba untuk membuat keputusan yang mana perkara-perkara

1555
01:14:54,829 --> 01:14:55,870
adakah anda bersedia untuk berbelanja?

1556
01:14:55,870 --> 01:14:57,380
Yang adalah yang paling mahal?

1557
01:14:57,380 --> 01:15:01,040
Yang menghasilkan keputusan yang lebih baik?

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
>> Sungguh benar.

1561
01:15:12,580 --> 01:15:15,970
Dalam kes ini, jika anda
mewakili nombor dalam maps-- yang

1562
01:15:15,970 --> 01:15:18,820
ini dipanggil dalam pelbagai bahasa
"Petunjuk" atau "alamat" -

1563
01:15:18,820 --> 01:15:20,390
ia adalah dua ruang.

1564
01:15:20,390 --> 01:15:24,390
Yang tidak semestinya seburuk berganda jika
sekarang kita hanya menyimpan nombor.

1565
01:15:24,390 --> 01:15:27,410
Katakan bahawa kita telah menyimpan
rekod pesakit di hospital-- yang

1566
01:15:27,410 --> 01:15:30,870
supaya nama Pierson, nombor telefon,
nombor keselamatan sosial, doktor

1567
01:15:30,870 --> 01:15:31,540
sejarah.

1568
01:15:31,540 --> 01:15:34,160
Kotak ini mungkin banyak,
lebih besar, di mana

1569
01:15:34,160 --> 01:15:38,000
penunjuk kecil sedikit, alamat
seterusnya element-- ia bukan satu masalah besar.

1570
01:15:38,000 --> 01:15:40,620
Ia seperti pinggiran yang
kos ia tidak mengapa.

1571
01:15:40,620 --> 01:15:43,210
Tetapi dalam kes ini, ya, ia adalah dua kali ganda a.

1572
01:15:43,210 --> 01:15:45,290
Soalan yang baik.

1573
01:15:45,290 --> 01:15:47,900
>> Mari kita bercakap tentang masa yang
sedikit dengan lebih kukuh.

1574
01:15:47,900 --> 01:15:50,380
Apakah masa yang berjalan
pencarian senarai ini?

1575
01:15:50,380 --> 01:15:53,640
Katakan saya mahu mencari
melalui semua gred pelajar,

1576
01:15:53,640 --> 01:15:55,980
dan ada gred n
dalam struktur data ini.

1577
01:15:55,980 --> 01:15:58,830
Di sini juga, kita boleh meminjam
perbendaharaan kata lebih awal.

1578
01:15:58,830 --> 01:16:00,890
Ini adalah struktur data linear.

1579
01:16:00,890 --> 01:16:04,570
>> O Big n adalah apa yang diperlukan untuk mendapatkan
ke akhir struktur data ini,

1580
01:16:04,570 --> 01:16:08,410
whereas-- dan kami tidak melihat
ini sebelum itu array memberikan anda

1581
01:16:08,410 --> 01:16:13,555
apa yang dipanggil masa yang berterusan, yang bermaksud
satu langkah atau dua langkah atau 10 steps--

1582
01:16:13,555 --> 01:16:14,180
tidak mengapa.

1583
01:16:14,180 --> 01:16:15,440
Ia adalah nombor yang tetap.

1584
01:16:15,440 --> 01:16:17,440
Ia tidak ada kena mengena dengan
saiz array.

1585
01:16:17,440 --> 01:16:20,130
Dan sebab itu,
sekali lagi, capaian rawak.

1586
01:16:20,130 --> 01:16:23,180
Komputer hanya boleh segera
melompat ke lokasi lain,

1587
01:16:23,180 --> 01:16:27,770
kerana mereka semua yang sama
jarak dari segala-galanya.

1588
01:16:27,770 --> 01:16:29,112
Tidak ada pemikiran yang terlibat.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Baiklah.

1591
01:16:32,400 --> 01:16:39,230
Jadi, jika saya boleh, saya cuba untuk
cat dua gambar akhir.

1592
01:16:39,230 --> 01:16:42,830
A satu yang biasa dikenali sebagai jadual hash.

1593
01:16:42,830 --> 01:16:51,120
Jadi untuk memberi motivasi kepada perbincangan ini,
biarlah saya berfikir tentang bagaimana untuk melakukan ini.

1594
01:16:51,120 --> 01:16:52,610
>> Jadi bagaimana pula ini?

1595
01:16:52,610 --> 01:16:55,160
Katakan bahawa masalah ini
kita mahu menyelesaikan sekarang

1596
01:16:55,160 --> 01:16:58,360
sedang melaksanakan dalam dictionary-- yang
supaya sejumlah besar perkataan Inggeris

1597
01:16:58,360 --> 01:16:59,330
atau apa sahaja.

1598
01:16:59,330 --> 01:17:02,724
Dan matlamatnya adalah untuk dapat menjawab
soalan bentuk ini ialah perkataan?

1599
01:17:02,724 --> 01:17:04,640
Jadi, anda mahu untuk melaksanakan
penyemak ejaan, hanya

1600
01:17:04,640 --> 01:17:07,220
seperti kamus fizikal
bahawa anda boleh melihat perkara dalam.

1601
01:17:07,220 --> 01:17:10,490
Katakan saya adalah untuk melakukan ini dengan array.

1602
01:17:10,490 --> 01:17:12,590
Saya boleh melakukan ini.

1603
01:17:12,590 --> 01:17:20,756
>> Dan andaikan perkataan epal
dan pisang dan tembikai.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Dan saya tidak boleh berfikir buah-buahan
yang bermula dengan d, jadi kami hanya

1606
01:17:26,465 --> 01:17:27,590
akan mempunyai tiga buah-buahan.

1607
01:17:27,590 --> 01:17:31,510
Jadi ini adalah pelbagai, dan kami
menyimpan semua kata-kata ini

1608
01:17:31,510 --> 01:17:34,200
dalam kamus ini sebagai array.

1609
01:17:34,200 --> 01:17:39,350
Persoalannya, maka, adalah bagaimana lagi
anda boleh menyimpan maklumat ini?

1610
01:17:39,350 --> 01:17:43,160
>> Well, Saya jenis menipu di sini, kerana
setiap huruf-huruf dalam perkataan

1611
01:17:43,160 --> 01:17:44,490
adalah benar-benar satu bait individu.

1612
01:17:44,490 --> 01:17:46,740
Jadi jika saya benar-benar mahu menjadi
nit-cerewet, saya perlu benar-benar

1613
01:17:46,740 --> 01:17:49,600
dapat membahagikan ini ke dalam banyak
ketulan yang lebih kecil memori,

1614
01:17:49,600 --> 01:17:51,289
dan kita boleh melakukan perkara tersebut.

1615
01:17:51,289 --> 01:17:53,580
Tetapi kita akan menghadapi
masalah yang sama seperti sebelum ini.

1616
01:17:53,580 --> 01:17:56,674
Bagaimana jika, sebagai Merriam Webster atau Oxford
juga setiap year-- mereka menambah kata-kata

1617
01:17:56,674 --> 01:17:59,340
kepada dictionary-- kita tidak
semestinya mahu cat diri kita

1618
01:17:59,340 --> 01:18:00,780
ke penjuru dengan array?

1619
01:18:00,780 --> 01:18:05,710
>> Jadi, mungkin pendekatan yang lebih bijak
adalah untuk meletakkan epal dalam nod sendiri atau kotak,

1620
01:18:05,710 --> 01:18:11,190
seperti yang kita katakan, pisang, dan
maka di sini kita ada tembikai.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Dan kita rentetan perkara-perkara ini bersama-sama.

1623
01:18:16,790 --> 01:18:19,980
Jadi ini adalah array, dan
ini adalah senarai yang dipautkan.

1624
01:18:19,980 --> 01:18:23,300
Jika anda tidak boleh agak lihat, ia hanya
berkata "array," dan ini mengatakan "senarai."

1625
01:18:23,300 --> 01:18:25,780
>> Oleh itu, kita mempunyai yang sama
isu-isu sebenar seperti sebelum ini,

1626
01:18:25,780 --> 01:18:28,600
di mana kita kini mempunyai
dinamik dalam senarai dikaitkan kami.

1627
01:18:28,600 --> 01:18:31,090
Tetapi kita mempunyai kamus yang agak perlahan.

1628
01:18:31,090 --> 01:18:32,870
Katakan Saya hendak mencari perkataan.

1629
01:18:32,870 --> 01:18:35,430
Ia mungkin mengambil masa saya O besar n
langkah-langkah, kerana perkataan yang mungkin

1630
01:18:35,430 --> 01:18:37,840
menjadi sepanjang jalan pada akhir
senarai, seperti tembikai.

1631
01:18:37,840 --> 01:18:40,600
Dan ternyata bahawa
dalam pengaturcaraan, jenis

1632
01:18:40,600 --> 01:18:42,700
daripada kaedah berpotensi suci data
struktur, adalah sesuatu

1633
01:18:42,700 --> 01:18:46,620
yang memberikan anda berterusan
masa seperti array

1634
01:18:46,620 --> 01:18:50,870
tetapi yang masih memberikan anda dinamik.

1635
01:18:50,870 --> 01:18:52,940
>> Jadi boleh kita mempunyai yang terbaik daripada kedua-dua dunia?

1636
01:18:52,940 --> 01:18:55,570
Dan sesungguhnya, ada sesuatu
dipanggil jadual hash

1637
01:18:55,570 --> 01:18:59,320
yang membolehkan anda untuk melakukan perkara
yang, walaupun kira-kira.

1638
01:18:59,320 --> 01:19:03,140
Satu jadual hash adalah pelamun
struktur data yang kita

1639
01:19:03,140 --> 01:19:06,340
boleh berfikir sebagai
kombinasi array-- yang

1640
01:19:06,340 --> 01:19:12,390
dan saya akan menarik ia
seperti this-- dan senarai berkaitan

1641
01:19:12,390 --> 01:19:17,310
bahawa saya akan menarik seperti ini di sini.

1642
01:19:17,310 --> 01:19:19,760
>> Dan cara perkara ini
kerja-kerja adalah seperti berikut.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Jika ini sekarang-- hash table--
adalah struktur data ketiga saya,

1645
01:19:29,540 --> 01:19:32,590
dan saya mahu menyimpan
kata-kata dalam hal ini, saya tidak

1646
01:19:32,590 --> 01:19:35,440
mahu hanya menyimpan semua
fakta yang kembali ke belakang untuk kembali ke belakang.

1647
01:19:35,440 --> 01:19:37,430
Saya mahu memanfaatkan beberapa
sekeping maklumat

1648
01:19:37,430 --> 01:19:40,330
mengenai kata-kata yang akan membiarkan
saya mendapatkannya di mana ia lebih cepat.

1649
01:19:40,330 --> 01:19:43,666
>> Jadi memandangkan epal kata-kata
dan pisang dan tembikai,

1650
01:19:43,666 --> 01:19:45,040
Saya sengaja memilih kata-kata.

1651
01:19:45,040 --> 01:19:45,340
Mengapa?

1652
01:19:45,340 --> 01:19:47,631
Apakah jenis asasnya
berbeza tentang tiga?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Apa yang jelas?

1655
01:19:51,484 --> 01:19:52,900
Mereka bermula dengan huruf yang berbeza.

1656
01:19:52,900 --> 01:19:53,900
>> Jadi, anda tahu apa?

1657
01:19:53,900 --> 01:19:57,120
Bukannya meletakkan segala perkataan-Ku di
baldi yang sama, jadi untuk bercakap,

1658
01:19:57,120 --> 01:20:00,390
seperti dalam satu senarai yang besar, mengapa tidak melakukannya
Saya sekurang-kurangnya cuba pengoptimuman

1659
01:20:00,390 --> 01:20:04,180
dan membuat senarai saya 1/26 lama.

1660
01:20:04,180 --> 01:20:07,440
A pengoptimuman menarik
mungkin mengapa tidak

1661
01:20:07,440 --> 01:20:10,650
Saya-- apabila memasukkan perkataan
ke dalam struktur data ini,

1662
01:20:10,650 --> 01:20:14,300
ke dalam ingatan komputer, mengapa
saya tidak meletakkan semua 'a' perkataan di sini,

1663
01:20:14,300 --> 01:20:17,270
segala perkataan 'b' di sini,
dan semua perkataan 'c' di sini?

1664
01:20:17,270 --> 01:20:24,610
Jadi ini berakhir meletakkan epal
di sini, pisang sini, tembikai sini,

1665
01:20:24,610 --> 01:20:25,730
dan sebagainya.

1666
01:20:25,730 --> 01:20:31,700
>> Dan jika saya mempunyai tambahan
perkataan like-- apa yang lain?

1667
01:20:31,700 --> 01:20:36,640
Apple, pisang, pir.

1668
01:20:36,640 --> 01:20:39,370
Sesiapa memikirkan buah
yang bermula dengan a, b, atau c?

1669
01:20:39,370 --> 01:20:40,570
sempurna Blueberry--.

1670
01:20:40,570 --> 01:20:43,990
Yang akan berakhir di sini.

1671
01:20:43,990 --> 01:20:47,530
Dan dengan itu kita seolah-olah mempunyai
sedikit penyelesaian yang lebih baik,

1672
01:20:47,530 --> 01:20:50,820
kerana sekarang jika saya mahu
untuk mencari epal, saya

1673
01:20:50,820 --> 01:20:53,200
first-- Saya tidak hanya menyelam
ke dalam struktur data saya.

1674
01:20:53,200 --> 01:20:54,850
Saya tidak menyelam ke dalam memori komputer saya.

1675
01:20:54,850 --> 01:20:56,530
Saya mula-mula melihat surat pertama.

1676
01:20:56,530 --> 01:20:58,610
>> Dan ini adalah apa yang komputer
saintis akan berkata.

1677
01:20:58,610 --> 01:21:00,760
Anda hash ke dalam struktur data anda.

1678
01:21:00,760 --> 01:21:04,100
Anda mengambil input anda, yang
kes ini adalah satu perkataan seperti epal.

1679
01:21:04,100 --> 01:21:07,150
Anda menganalisisnya, melihat
huruf pertama dalam kes ini,

1680
01:21:07,150 --> 01:21:08,340
dengan itu hashing ia.

1681
01:21:08,340 --> 01:21:10,950
Hashing adalah di mana istilah umum
anda mengambil sesuatu sebagai input

1682
01:21:10,950 --> 01:21:12,116
dan anda menghasilkan beberapa output.

1683
01:21:12,116 --> 01:21:15,090
Dan output dalam yang
kes adalah lokasi yang

1684
01:21:15,090 --> 01:21:18,150
anda ingin cari, yang pertama
lokasi, lokasi kedua, ketiga.

1685
01:21:18,150 --> 01:21:22,160
Jadi input adalah epal,
keluaran adalah pertama.

1686
01:21:22,160 --> 01:21:25,054
input adalah pisang, yang
output harus kedua.

1687
01:21:25,054 --> 01:21:27,220
input adalah tembikai,
output harus ketiga.

1688
01:21:27,220 --> 01:21:30,320
input adalah blueberry, yang
output perlu lagi menjadi kedua.

1689
01:21:30,320 --> 01:21:34,010
Dan itulah yang membantu anda mengambil
pintasan melalui ingatan anda

1690
01:21:34,010 --> 01:21:39,050
untuk mendapatkan kata-kata
atau data yang lebih berkesan.

1691
01:21:39,050 --> 01:21:43,330
>> Sekarang ini menjimatkan masa kita berpotensi
sebanyak satu daripada 26,

1692
01:21:43,330 --> 01:21:45,850
kerana jika anda menganggap bahawa anda
mempunyai banyak "a" perkataan sebagai "z"

1693
01:21:45,850 --> 01:21:48,080
perkataan yang perkataan "q", yang
tidak benar-benar realistic--

1694
01:21:48,080 --> 01:21:50,830
anda akan mempunyai condong seluruh
surat tertentu alphabet-- yang

1695
01:21:50,830 --> 01:21:53,204
tetapi ini akan menjadi tambahan
pendekatan yang tidak membenarkan

1696
01:21:53,204 --> 01:21:55,930
anda untuk mendapatkan kata-kata lebih cepat.

1697
01:21:55,930 --> 01:21:59,660
Dan pada hakikatnya, yang canggih
program, Googles dunia,

1698
01:21:59,660 --> 01:22:02,180
yang Facebooks daripada world--
mereka akan menggunakan jadual hash

1699
01:22:02,180 --> 01:22:03,740
untuk banyak tujuan yang berlainan.

1700
01:22:03,740 --> 01:22:06,590
Tetapi mereka tidak akan menjadi begitu naif
untuk hanya melihat huruf pertama

1701
01:22:06,590 --> 01:22:09,700
dalam epal atau pisang atau
pir atau tembikai,

1702
01:22:09,700 --> 01:22:13,420
kerana seperti yang anda lihat ini
senarai masih boleh lama.

1703
01:22:13,420 --> 01:22:17,130
>> Dan hal ini masih ada semacam
daripada linear-- jadi semacam perlahan,

1704
01:22:17,130 --> 01:22:19,980
seperti dengan o besar n
yang kita dibincangkan sebelum ini.

1705
01:22:19,980 --> 01:22:25,290
Jadi apa jadual hash yang baik yang sebenar akan
do-- ia akan mempunyai pelbagai yang lebih besar.

1706
01:22:25,290 --> 01:22:28,574
Dan ia akan menggunakan lebih
fungsi hashing canggih,

1707
01:22:28,574 --> 01:22:30,240
supaya ia tidak hanya melihat "a."

1708
01:22:30,240 --> 01:22:35,480
Mungkin ia kelihatan pada "a-p-p-l-e" dan
entah bagaimana menukarkan mereka lima huruf

1709
01:22:35,480 --> 01:22:38,400
ke lokasi di mana
epal perlu disimpan.

1710
01:22:38,400 --> 01:22:42,660
Kami hanya naif menggunakan huruf 'a'
sahaja, kerana ia adalah baik dan mudah.

1711
01:22:42,660 --> 01:22:44,600
>> Tetapi jadual hash, dalam
Akhirnya, anda boleh berfikir

1712
01:22:44,600 --> 01:22:47,270
sebagai gabungan
pelbagai, setiap yang

1713
01:22:47,270 --> 01:22:51,700
mempunyai senarai berpaut yang ideal
perlu sebagai pendek yang mungkin.

1714
01:22:51,700 --> 01:22:54,364
Dan ini bukanlah satu penyelesaian yang jelas.

1715
01:22:54,364 --> 01:22:57,280
Malah, banyak penalaan halus
yang berlaku di bawah hood apabila

1716
01:22:57,280 --> 01:22:59,654
melaksanakan ini jenis
struktur data yang canggih

1717
01:22:59,654 --> 01:23:01,640
adalah apa yang kanan
panjang array?

1718
01:23:01,640 --> 01:23:03,250
Apakah fungsi hash yang betul?

1719
01:23:03,250 --> 01:23:04,830
Bagaimana anda menyimpan perkara-perkara dalam ingatan?

1720
01:23:04,830 --> 01:23:07,249
>> Tetapi sedar berapa cepat
seperti ini perbincangan

1721
01:23:07,249 --> 01:23:10,540
meningkat, sama ada setakat ini bahawa ia adalah jenis
lebih kepala seseorang pada ketika ini, yang

1722
01:23:10,540 --> 01:23:11,360
adalah baik.

1723
01:23:11,360 --> 01:23:18,820
Tetapi kami mula, ingat, dengan benar-benar
sesuatu peringkat rendah dan elektronik.

1724
01:23:18,820 --> 01:23:20,819
Dan hal ini sekali lagi adalah ini
tema abstraksi,

1725
01:23:20,819 --> 01:23:23,610
di mana sebaik sahaja anda mula untuk mengambil untuk
diberikan, OK, saya telah mendapat it-- ada

1726
01:23:23,610 --> 01:23:26,680
memori fizikal, OK, faham, setiap
lokasi fizikal mempunyai alamat,

1727
01:23:26,680 --> 01:23:29,910
OK, saya mendapat ia, saya boleh mewakili
alamat tersebut sebagai arrows--

1728
01:23:29,910 --> 01:23:34,650
anda boleh dengan cepat mula mempunyai
perbualan yang lebih canggih yang

1729
01:23:34,650 --> 01:23:38,360
pada akhirnya seolah-olah akan membolehkan kita
untuk menyelesaikan masalah seperti mencari

1730
01:23:38,360 --> 01:23:41,620
dan menyusun dengan lebih berkesan.

1731
01:23:41,620 --> 01:23:44,190
Dan yakinlah, too--
kerana saya rasa ini

1732
01:23:44,190 --> 01:23:48,700
adalah yang paling dalam kami telah pergi ke beberapa
ini topik CS proper-- kami telah

1733
01:23:48,700 --> 01:23:51,880
dilakukan dalam sehari dan setengah di ini
menunjukkan apa yang anda biasanya boleh melakukan lebih

1734
01:23:51,880 --> 01:23:55,520
perjalanan lapan minggu dalam sesuatu semester.

1735
01:23:55,520 --> 01:23:59,670
>> Sebarang pertanyaan mengenai ini?

1736
01:23:59,670 --> 01:24:01,100
Tidak?

1737
01:24:01,100 --> 01:24:01,940
Baiklah.

1738
01:24:01,940 --> 01:24:05,610
Nah, mengapa tidak kita berhenti seketika di sana,
mula makan tengah hari beberapa minit awal,

1739
01:24:05,610 --> 01:24:07,052
disambung semula pada hanya kira-kira satu jam?

1740
01:24:07,052 --> 01:24:08,760
Dan saya akan berlama-lama untuk
sedikit dengan soalan.

1741
01:24:08,760 --> 01:24:11,343
Kemudian saya akan perlu pergi
mengambil panggilan pasangan jika itu OK.

1742
01:24:11,343 --> 01:24:15,000
Saya akan menghidupkan muzik beberapa dalam masa yang sama,
tetapi makan tengah hari harus sekitar sudut.

1743
01:24:15,000 --> 01:24:17,862