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

2
00:00:11,100 --> 00:00:12,300
>> SPEAKER 1: Hei semua orang!

3
00:00:12,300 --> 00:00:13,890
Selamat kembali ke bahagian.

4
00:00:13,890 --> 00:00:17,480
Sangat senang melihat begitu ramai di antara anda berdua di sini,
dan semua orang yang menonton online.

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

6
00:00:18,760 --> 00:00:20,920
Jadi, seperti biasa selamat datang kembali.

7
00:00:20,920 --> 00:00:24,360
Saya harap anda semua telah tinggal yang indah
hujung minggu, penuh dengan rehat, istirahat.

8
00:00:24,360 --> 00:00:26,026
Itu indah daripada kemarin.

9
00:00:26,026 --> 00:00:27,525
Jadi, saya berharap anda menikmati alam bebas.

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

11
00:00:28,840 --> 00:00:30,610
>> Jadi pertama beberapa pengumuman.

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

13
00:00:31,920 --> 00:00:32,700
Penilaian.

14
00:00:32,700 --> 00:00:37,350
Jadi, kebanyakan kamu harus mendapatkan satu
email dari saya tentang Serangga Scratch anda,

15
00:00:37,350 --> 00:00:39,920
dan juga kadar untuk Serangga 1.

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

17
00:00:41,000 --> 00:00:42,220
Jadi, hanya beberapa perkara.

18
00:00:42,220 --> 00:00:45,150
Pastikan anda menggunakan check50 di style50.

19
00:00:45,150 --> 00:00:47,250
Ini dimaksudkan untuk menjadi
sumber untuk kalian,

20
00:00:47,250 --> 00:00:50,660
memastikan bahawa anda mendapat
sebagai mata sebanyak yang anda boleh

21
00:00:50,660 --> 00:00:52,390
sia-sia tanpa kehilangan mereka.

22
00:00:52,390 --> 00:00:54,407
Jadi, hal-hal seperti gaya
sangat penting.

23
00:00:54,407 --> 00:00:55,740
Kita akan mengambil kira untuk itu.

24
00:00:55,740 --> 00:00:58,115
Sebahagian daripada anda mungkin sudah
melihat bahawa dari Serangga anda.

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

26
00:00:58,920 --> 00:01:01,450
Dan check50 hanyalah
cara yang sangat mudah untuk memastikan

27
00:01:01,450 --> 00:01:05,050
bahawa kita benar-benar kembali apa
perlu dikembalikan kepada pengguna,

28
00:01:05,050 --> 00:01:06,690
dan semua yang bekerja dengan baik.

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

30
00:01:08,690 --> 00:01:12,040
>> Dalam perkembangan yang kedua, pastikan anda
memuat naik perkara ke folder yang betul.

31
00:01:12,040 --> 00:01:14,470
Ia menjadikan hidup saya hanya
sedikit lebih sukar

32
00:01:14,470 --> 00:01:18,836
jika anda memuat naik Serangga Serangga 2 ke 1
kerana apabila saya memuat turun perkara-perkara,

33
00:01:18,836 --> 00:01:20,085
mereka tidak turun dengan betul.

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

35
00:01:21,690 --> 00:01:24,560
Dan saya tahu itu miring sedikit
dalam satu sistem untuk membiasakan diri,

36
00:01:24,560 --> 00:01:26,950
tetapi hanya menjadi super
berhati-hati, jika hanya untuk saya,

37
00:01:26,950 --> 00:01:30,080
supaya apabila anda mendapat e-mel
di seperti 2:00 dan saya grading.

38
00:01:30,080 --> 00:01:33,710
Jika tidak menyebabkan saya perlu melihat
di sekitar untuk Serangga anda.

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

40
00:01:34,440 --> 00:01:37,270
>> Aku tahu itu lebih awal, tetapi saya
sama sekali tak lengah

41
00:01:37,270 --> 00:01:40,800
oleh satu esei itu karena Jumaat ini, yang
profesor saya hanya suka, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Ingat, anda mempunyai
esei kerana pada hari Jumaat.

43
00:01:42,550 --> 00:01:45,780
Jadi, saya tahu tidak ada orang suka
untuk berfikir tentang ujian tengah semester,

44
00:01:45,780 --> 00:01:50,620
tetapi kuiz pertama anda adalah pada 15 Oktober,
Oktober ini yang bermula minggu ini.

45
00:01:50,620 --> 00:01:53,290
Jadi, ia mungkin lebih cepat
dari yang Anda harapkan adalah semua.

46
00:01:53,290 --> 00:01:57,510
Supaya anda tidak dibuang dalam keadaan tidak bersedia apabila
Saya menyebut seksyen minggu depan yang oh,

47
00:01:57,510 --> 00:02:00,560
kuiz minggu depan anda, saya fikir
Saya akan memberikan anda sedikit lebih

48
00:02:00,560 --> 00:02:01,500
dari kepala sekarang.

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

50
00:02:02,970 --> 00:02:04,660
>> Jadi, masalah anda ditetapkan, nombor tiga.

51
00:02:04,660 --> 00:02:07,070
Bagaimana orang telah membaca
spec daripada rasa ingin tahu?

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

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

54
00:02:09,199 --> 00:02:10,229
Kami mendapat pasangan.

55
00:02:10,229 --> 00:02:12,320
Jenis turun dari lepas
minggu tetapi tidak apa-apa.

56
00:02:12,320 --> 00:02:13,650
Saya tahu itu keluar indah.

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

58
00:02:15,120 --> 00:02:16,660
Jadi Break.

59
00:02:16,660 --> 00:02:21,010
Sudah pasti selepas anda mendapatkan dilakukan
hari ini membaca spec anda sekurang-kurangnya

60
00:02:21,010 --> 00:02:25,240
cuba seperti memuat turun
kod pengedaran dan berjalan

61
00:02:25,240 --> 00:02:27,430
seperti permulaan pertama
hal yang mereka meminta anda.

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

63
00:02:28,681 --> 00:02:32,590
Oleh kerana kita menggunakan
kod pengedaran dan perpustakaan

64
00:02:32,590 --> 00:02:36,790
bahawa kita hanya telah using-- --Ini hanya
kali kedua kami telah melakukan Serangga ini,

65
00:02:36,790 --> 00:02:38,650
perkara gila boleh berlaku
dengan alat anda,

66
00:02:38,650 --> 00:02:41,370
dan anda ingin mencari yang
keluar sekarang berbanding nanti.

67
00:02:41,370 --> 00:02:45,570
>> Kerana jika itu malam Khamis atau itu
Rabu malam dan untuk sebab-sebab tertentu

68
00:02:45,570 --> 00:02:48,912
alat anda hanya tidak
ingin menjalankan dengan perpustakaan

69
00:02:48,912 --> 00:02:50,620
atau dengan taburan
kod, yang cara

70
00:02:50,620 --> 00:02:52,309
Anda tidak boleh mula melakukan coding.

71
00:02:52,309 --> 00:02:54,100
Kerana anda tidak boleh menyemak
untuk melihat jika ia berfungsi.

72
00:02:54,100 --> 00:02:55,975
Anda tidak akan dapat
untuk melihat jika ia menyusun.

73
00:02:55,975 --> 00:03:00,500
Anda mahu untuk menjaga mereka di awal
minggu itu, ketika anda masih boleh e-mel saya

74
00:03:00,500 --> 00:03:03,100
atau salah satu daripada TF yang lain,
dan kita boleh mendapatkan orang-orang yang tetap.

75
00:03:03,100 --> 00:03:05,410
Kerana mereka adalah isu-isu
yang akan menghalang anda

76
00:03:05,410 --> 00:03:07,120
daripada membuat apa-apa kemajuan yang nyata.

77
00:03:07,120 --> 00:03:10,055
Ini tidak seperti satu bug, yang
Anda boleh hanya jenis melewatkan.

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

79
00:03:10,712 --> 00:03:13,420
Jika anda menghadapi masalah dengan anda
perkakas atau kod pengedaran,

80
00:03:13,420 --> 00:03:16,211
Anda benar-benar mahu untuk mendapatkan yang diambil
mengurus lebih awal daripada kemudian.

81
00:03:16,211 --> 00:03:20,410
Jadi, walaupun anda tidak benar-benar gonna
mulai coding, muat turun pengedaran

82
00:03:20,410 --> 00:03:24,040
kod, baca spec, memastikan
segala-galanya yang bekerja di sana.

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

84
00:03:25,134 --> 00:03:27,675
Jika anda hanya boleh melakukan itu, saya
menjanjikan kehidupan anda akan menjadi lebih mudah.

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

86
00:03:28,800 --> 00:03:31,410
Dan supaya anda mungkin akan
untuk melakukannya dengan betul sekarang kan?

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

88
00:03:32,100 --> 00:03:33,950
Jadi, mana-mana soalan di sana?

89
00:03:33,950 --> 00:03:35,850
Hal-hal logistik?

90
00:03:35,850 --> 00:03:36,910
Semua orang yang baik?

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

92
00:03:38,270 --> 00:03:41,700
>> Penafian bagi
Anda di dalam bilik dan dalam talian.

93
00:03:41,700 --> 00:03:45,437
Saya akan cuba untuk menukar
antara PowerPoint pada alat

94
00:03:45,437 --> 00:03:47,270
kerana kita akan
cuba membuat beberapa coding

95
00:03:47,270 --> 00:03:53,630
hari ini oleh permintaan popular daripada tanpa nama
cadangan jajak pendapat saya dihantar minggu lepas.

96
00:03:53,630 --> 00:03:55,480
Jadi, kita akan melakukan beberapa coding.

97
00:03:55,480 --> 00:03:57,800
Jadi, jika anda lelaki juga mahu
untuk menjalankan peralatan anda,

98
00:03:57,800 --> 00:04:02,910
dan anda harus sudah mendapat e-mel
dari saya, dengan contoh file.

99
00:04:02,910 --> 00:04:04,310
Sila berasa bebas untuk berbuat demikian.

100
00:04:04,310 --> 00:04:07,340
>> Jadi, kita akan bercakap tentang
GDB, yang debugger.

101
00:04:07,340 --> 00:04:09,970
Ia akan membantu anda
jenis memikirkan di mana

102
00:04:09,970 --> 00:04:11,860
hal-hal yang tidak baik di dalam kod anda.

103
00:04:11,860 --> 00:04:15,370
Ia benar-benar hanya satu cara bagi Anda untuk melangkah
melalui kod anda kerana ia berlaku,

104
00:04:15,370 --> 00:04:19,100
dan mampu untuk mencetak pembolehubah
atau melihat apa yang sebenarnya berlaku

105
00:04:19,100 --> 00:04:22,980
di bawah tenda ayat program anda
hanya berjalan, ia seperti faulting,

106
00:04:22,980 --> 00:04:25,030
dan anda seperti, tidak tahu
apa yang baru saja terjadi di sini.

107
00:04:25,030 --> 00:04:26,730
Saya tidak tahu apa yang talian itu gagal.

108
00:04:26,730 --> 00:04:29,040
Saya tidak tahu di mana ia pergi salah.

109
00:04:29,040 --> 00:04:31,280
Jadi, GDB akan membantu anda dengan itu.

110
00:04:31,280 --> 00:04:35,240
Juga, jika anda membuat keputusan untuk
terus ya, dan mengambil 61,

111
00:04:35,240 --> 00:04:38,430
ia akan benar-benar, benar-benar menjadi anda
kawan baik, sebab saya boleh memberitahu anda

112
00:04:38,430 --> 00:04:40,840
kerana saya akan melalui kelas itu.

113
00:04:40,840 --> 00:04:43,620
>> Kita akan melihat binari
carian, yang jika kalian ingat

114
00:04:43,620 --> 00:04:47,540
contoh buku telefon besar
cermin mata dalam kelas.

115
00:04:47,540 --> 00:04:50,620
Kami akan melaksanakan itu, dan
berjalan melalui yang lebih sedikit,

116
00:04:50,620 --> 00:04:54,650
dan kemudian kita akan melalui empat
macam yang berbeda, yang gelembung,

117
00:04:54,650 --> 00:04:56,285
Pemilihan, Pemasukan, dan Gabung.

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

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

120
00:04:58,330 --> 00:05:00,390
Jadi, GDB seperti yang saya sebutkan, adalah debugger.

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

122
00:05:01,400 --> 00:05:09,370
Dan ini adalah jenis yang besar
perkara, fungsi besar atau perintah

123
00:05:09,370 --> 00:05:13,240
yang anda gunakan dalam GDB, dan saya akan berjalan
Anda melalui demo dalam satu saat.

124
00:05:13,240 --> 00:05:15,360
>> Jadi, ini bukan sahaja
akan tinggal abstrak.

125
00:05:15,360 --> 00:05:18,000
Saya akan cuba dan menjadikannya sebagai konkrit
mungkin bagi kalian.

126
00:05:18,000 --> 00:05:19,870
Jadi, istirahat.

127
00:05:19,870 --> 00:05:22,200
Ia sama ada akan istirahat
seperti ini, cukup banyak, yang

128
00:05:22,200 --> 00:05:26,900
merupakan garis dalam program anda,
atau anda boleh nama fungsi.

129
00:05:26,900 --> 00:05:30,150
Jadi, jika anda mengatakan memecahkan utama,
ia akan berhenti di utama,

130
00:05:30,150 --> 00:05:32,400
dan membiarkan anda berjalan melalui fungsi itu.

131
00:05:32,400 --> 00:05:36,350
>> Demikian juga, jika anda mempunyai beberapa luaran
berfungsi seperti Tukar atau Cube,

132
00:05:36,350 --> 00:05:38,450
yang kita melihat pada minggu lepas.

133
00:05:38,450 --> 00:05:41,780
Jika anda mengatakan memecahkan salah satu dari mereka,
setiap kali program anda sebagai rumah anda itu,

134
00:05:41,780 --> 00:05:44,290
ia akan menunggu untuk anda
beritahu apa yang perlu dilakukan.

135
00:05:44,290 --> 00:05:47,860
Sebelum itu hanya akan melaksanakan sehingga Anda
sebenarnya boleh melangkah di dalam fungsi

136
00:05:47,860 --> 00:05:49,020
dan melihat apa yang sedang berlaku.

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

138
00:05:50,370 --> 00:05:53,515
Jadi, Seterusnya, hanya melompat ke atas
baris berikutnya, berjalan di atas fungsi.

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

140
00:05:54,730 --> 00:05:55,560
Langkah.

141
00:05:55,560 --> 00:05:56,810
Ini semua adalah abstrak sedikit.

142
00:05:56,810 --> 00:06:00,530
Jadi, aku hanya akan berjalan melalui mereka,
tetapi anda akan melihat mereka digunakan dalam satu saat.

143
00:06:00,530 --> 00:06:01,810
>> Melangkah ke fungsi.

144
00:06:01,810 --> 00:06:04,170
Jadi seperti yang saya katakan,
seperti dengan Swap, ia akan

145
00:06:04,170 --> 00:06:07,110
membolehkan anda untuk benar-benar seolah-olah anda
seperti fizikal melangkah di dalam,

146
00:06:07,110 --> 00:06:10,990
anda boleh main-main dengan variabel, mencetak
tahu apa yang mereka, lihat apa yang berlaku.

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

148
00:06:12,140 --> 00:06:14,830
Senarai akan benar-benar hanya mencetak
daripada kod di sekitarnya.

149
00:06:14,830 --> 00:06:17,570
Jadi, jika anda jenis lupa
mana anda berada dalam program anda,

150
00:06:17,570 --> 00:06:19,880
atau anda tertanya-tanya
apa yang berlaku di sekitarnya,

151
00:06:19,880 --> 00:06:23,790
ini hanya akan mencetak segmen
dari seperti lima atau enam baris di sekitarnya.

152
00:06:23,790 --> 00:06:26,080
Jadi, anda boleh mendapatkan berorientasi
kira-kira di mana anda berada.

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

154
00:06:27,230 --> 00:06:28,650
>> Mencetak beberapa pembolehubah.

155
00:06:28,650 --> 00:06:34,590
Jadi, jika anda mempunyai kunci seperti
di Caesar, yang kita akan melihat.

156
00:06:34,590 --> 00:06:36,220
Anda boleh mengatakan Cetak utama pada bila-bila.

157
00:06:36,220 --> 00:06:40,070
Ia akan memberitahu anda apa nilai yang begitu
itu, mungkin di suatu tempat di sepanjang jalan,

158
00:06:40,070 --> 00:06:42,070
Anda menimpa kunci anda.

159
00:06:42,070 --> 00:06:45,495
Anda benar-benar boleh mengatakan bahawa kerana
Anda benar-benar boleh melihat nilai tersebut.

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

161
00:06:46,500 --> 00:06:48,780
>> Dalam penduduk tempatan, hanya cetakan
daripada pembolehubah tempatan anda.

162
00:06:48,780 --> 00:06:53,120
Jadi, bila-bila masa anda dalam satu lingkaran,
dan anda hanya ingin melihat seperti, oh.

163
00:06:53,120 --> 00:06:54,270
Apa yang saya saya?

164
00:06:54,270 --> 00:06:57,020
Apa nilai utama ini
yang saya memulakan di sini?

165
00:06:57,020 --> 00:06:58,537
Apa pesan itu pada ketika ini?

166
00:06:58,537 --> 00:07:00,370
Ini hanya akan mencetak semua
dari mereka, supaya anda

167
00:07:00,370 --> 00:07:04,330
tidak perlu secara individu
berkata, Cetak I. Cetak mesej.

168
00:07:04,330 --> 00:07:04,970
Cetak Utama.

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

170
00:07:06,190 --> 00:07:07,700
Dan kemudian Paparkan.

171
00:07:07,700 --> 00:07:10,370
Apa yang dilakukan adalah kerana anda
langkah melalui program ini,

172
00:07:10,370 --> 00:07:13,980
ia hanya akan memastikan bahawa itu
menampilkan beberapa variabel tertentu

173
00:07:13,980 --> 00:07:14,780
pada setiap titik.

174
00:07:14,780 --> 00:07:17,160
Supaya anda also-- --Ini Ini
jenis pintasan di mana

175
00:07:17,160 --> 00:07:19,530
anda tidak perlu terus berjalan seperti, oh.

176
00:07:19,530 --> 00:07:23,150
Cetak Kunci atau Cetak I. Ia hanya
secara automatik akan melakukannya untuk anda.

177
00:07:23,150 --> 00:07:25,959
>> Jadi, dengan itu, kita akan
untuk melihat bagaimana ini pergi.

178
00:07:25,959 --> 00:07:28,000
Saya akan cuba dan beralih
kepada alat saya.

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

180
00:07:30,200 --> 00:07:31,271
Lihat jika saya boleh melakukan hal ini.

181
00:07:31,271 --> 00:07:31,770
Semua.

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

183
00:07:40,970 --> 00:07:42,370
Kami hanya akan cermin itu.

184
00:07:42,370 --> 00:07:44,530
Tidak ada yang gila
di laptop saya anyways.

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

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

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

188
00:07:57,030 --> 00:08:01,054
Ini perlu menjadi satu ini.

189
00:08:01,054 --> 00:08:01,795
Ia amat kecil.

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

191
00:08:03,730 --> 00:08:05,120
Mari kita lihat apakah yang boleh kita lakukan ini.

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

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

194
00:08:10,940 --> 00:08:15,305
Alice jelas berjuang
di sini hanya sedikit,

195
00:08:15,305 --> 00:08:17,995
tetapi kita akan mendapatkannya dalam momento.

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

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

198
00:08:22,020 --> 00:08:25,900
Kami hanya akan meningkat ini.

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

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

201
00:08:29,380 --> 00:08:31,679
Bolehkah semua orang jenis lihat itu?

202
00:08:31,679 --> 00:08:32,470
Mungkin sedikit?

203
00:08:32,470 --> 00:08:33,594
Aku tahu itu agak kecil.

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

205
00:08:34,570 --> 00:08:37,530
Anda tidak boleh agak memikirkan
bagaimana untuk membuat ini lebih besar.

206
00:08:37,530 --> 00:08:38,350
Jika ada yang tahu.

207
00:08:38,350 --> 00:08:40,309
Adakah sesiapa yang tahu bagaimana untuk membuat ia lebih besar?

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

209
00:08:40,932 --> 00:08:42,140
Kami akan melancarkan dengan itu.

210
00:08:42,140 --> 00:08:45,801
Tidak kira anyways kerana ia hanya
itulah kod yang kalian harus

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

212
00:08:46,300 --> 00:08:48,310
>> Apa yang lebih penting
adalah terminal itu di sini.

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

214
00:08:52,840 --> 00:08:58,690
Dan kami ada di sini Mengapa begitu kecil?

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

216
00:09:02,325 --> 00:09:02,825
Tetapan.

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

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

219
00:09:08,420 --> 00:09:09,500
Ike benar.

220
00:09:09,500 --> 00:09:10,880
Bagaimana ini?

221
00:09:10,880 --> 00:09:11,770
Keluar dari sana.

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

223
00:09:19,370 --> 00:09:21,810
Apakah yang lebih baik untuk semua orang?

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

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

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

227
00:09:25,830 --> 00:09:28,220
>> Anda tahu apabila anda berada dalam CS
masalah teknikal kelas

228
00:09:28,220 --> 00:09:32,971
adalah jenis sebahagian daripada the--
Jadi, mari kita jelas ini.

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

230
00:09:33,470 --> 00:09:38,060
Jadi, di sini, di bahagian,
yang kami di sini.

231
00:09:38,060 --> 00:09:40,830
Caesar adalah fail boleh laku.

232
00:09:40,830 --> 00:09:41,800
Jadi saya membuat ia.

233
00:09:41,800 --> 00:09:46,370
Jadi, satu perkara untuk merealisasikan dengan GDB adalah
yang hanya bekerja pada fail boleh laku.

234
00:09:46,370 --> 00:09:48,040
Jadi, anda tidak boleh menjalankannya pada dotsy a.

235
00:09:48,040 --> 00:09:50,532
Anda perlu benar-benar membuat
memastikan bahawa kod anda mengkompilasi,

236
00:09:50,532 --> 00:09:51,865
dan bahawa ia sebenarnya boleh dijalankan.

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

238
00:09:52,970 --> 00:09:56,186
>> Jadi, pastikan bahawa jika ia tidak
menyusun, dapatkan ia untuk mengkompilasi,

239
00:09:56,186 --> 00:09:57,810
supaya anda jenis boleh berjalan melaluinya.

240
00:09:57,810 --> 00:10:04,590
Jadi, untuk memulakan GDB, semua yang anda lakukan,
Gloria jenis GDB, dan kemudian hanya

241
00:10:04,590 --> 00:10:06,250
fail yang anda mahu.

242
00:10:06,250 --> 00:10:08,240
Saya selalu salah mengeja Caesar.

243
00:10:08,240 --> 00:10:11,730
Tetapi anda ingin memastikan
karena itu laksana,

244
00:10:11,730 --> 00:10:14,210
titik kilat ti supaya
bermakna anda akan

245
00:10:14,210 --> 00:10:19,240
untuk menjalankan CSI anda akan melaksanakan
file ini sama ada dengan debugger.

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

247
00:10:19,910 --> 00:10:22,885
Jadi, anda melakukan itu, anda akan mendapat
seperti ini omong kosong.

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

249
00:10:24,250 --> 00:10:25,750
Ia hanya kira-kira tiap-tiap sesuatu penyahpepijat.

250
00:10:25,750 --> 00:10:28,200
Anda tidak benar-benar perlu
bimbang tentang hal itu sekarang.

251
00:10:28,200 --> 00:10:31,460
Dan seperti yang anda lihat, kita mempunyai ini
parens terbuka, KDNK, parens dekat,

252
00:10:31,460 --> 00:10:34,690
dan hanya jenis kelihatan seperti
baris arahan kita, kan?

253
00:10:34,690 --> 00:10:37,010
>> Jadi, apa yang kita mahu do--
--So, Perkara pertama yang

254
00:10:37,010 --> 00:10:39,570
adalah kita ingin memilih
tempat untuk memecahkannya.

255
00:10:39,570 --> 00:10:42,332
Jadi, ada satu bug
dalam program ini Caesar

256
00:10:42,332 --> 00:10:44,290
bahawa saya memperkenalkan, yang
kita akan mencari tahu.

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

258
00:10:45,330 --> 00:10:56,350
Ini Apa yang dilakukannya adalah ia mengambil input
Barfoo dalam semua topi, dan untuk sebab-sebab tertentu

259
00:10:56,350 --> 00:11:01,950
itu tidak mengubah A. Ia hanya meninggalkan
itu sahaja, Apakah segala sesuatu yang lain yang benar,

260
00:11:01,950 --> 00:11:03,980
tetapi huruf kedua
A tetap tidak berubah.

261
00:11:03,980 --> 00:11:07,120
Jadi, kita akan cuba
memikirkan mengapa itu.

262
00:11:07,120 --> 00:11:10,440
Jadi, perkara pertama yang anda biasanya
ingin melakukan setiap kali anda mula pada GDB

263
00:11:10,440 --> 00:11:12,010
adalah mencari tahu di mana untuk memecahkannya.

264
00:11:12,010 --> 00:11:14,956
>> Jadi Caesar adalah program yang cukup singkat.

265
00:11:14,956 --> 00:11:16,330
Kami hanya mempunyai satu fungsi, kan?

266
00:11:16,330 --> 00:11:18,520
Apakah fungsi kita di Caesar?

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

268
00:11:19,590 --> 00:11:24,350
Hanya ada satu fungsi, hak utama?

269
00:11:24,350 --> 00:11:26,490
Utama adalah fungsi
untuk semua program anda.

270
00:11:26,490 --> 00:11:29,230
Jika anda tidak mempunyai Utama, saya mungkin
menjadi sedikit bimbang sekarang,

271
00:11:29,230 --> 00:11:31,000
tetapi saya berharap anda semua memiliki Utama di sana.

272
00:11:31,000 --> 00:11:34,150
Jadi, apa yang kita boleh lakukan ialah kita boleh
hanya memecahkan Utama, begitu saja.

273
00:11:34,150 --> 00:11:35,190
Jadi, ia mengatakan, OK.

274
00:11:35,190 --> 00:11:37,430
Kami menetapkan satu titik pecah yang kami ada.

275
00:11:37,430 --> 00:11:42,870
>> Jadi, hal yang perlu diingat adalah Caesar
mengambil satu perintah argumen baris kanan

276
00:11:42,870 --> 00:11:45,150
dan kami tidak melakukan hal itu di mana-mana lagi.

277
00:11:45,150 --> 00:11:47,560
Jadi, apa yang anda lakukan adalah apabila
Anda benar-benar pergi untuk menjalankan

278
00:11:47,560 --> 00:11:51,540
program ini, apa-apa program yang anda
berjalan dalam GDB yang perlu baris perintah

279
00:11:51,540 --> 00:11:55,010
hujah, anda akan input
saat pertama kali menjalankannya.

280
00:11:55,010 --> 00:11:59,280
Jadi, dalam hal ini, kami
Main dengan kunci tiga.

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

282
00:12:00,770 --> 00:12:02,040
Dan ia benar-benar akan bermula.

283
00:12:02,040 --> 00:12:08,480
>> Jadi, jika anda lihat di sini, kami mempunyai
Jika RC tidak sama dengan 2.

284
00:12:08,480 --> 00:12:12,210
Oleh itu, jika kalian semua mempunyai
fail yang saya dihantar sehingga

285
00:12:12,210 --> 00:12:15,100
Anda akan melihat bahawa itu seperti yang
baris pertama fungsi utama kita, kan?

286
00:12:15,100 --> 00:12:17,890
Ia memeriksa untuk melihat jika kita mempunyai
nombor yang betul bagi hujah.

287
00:12:17,890 --> 00:12:20,620
Jadi, jika anda bertanya-tanya
jika RC adalah benar,

288
00:12:20,620 --> 00:12:23,250
Anda dapat melakukan sesuatu seperti Cetak RC.

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

290
00:12:24,380 --> 00:12:28,640
RC adalah dua, iaitu
apa yang kita harapkan, bukan?

291
00:12:28,640 --> 00:12:32,010
>> Jadi, kita boleh pergi depan,
dan terus melalui.

292
00:12:32,010 --> 00:12:33,200
Jadi, kita mempunyai beberapa kunci di sana.

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

294
00:12:34,260 --> 00:12:37,090
Dan kita boleh mencetak utama kami
memastikan itu benar.

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

296
00:12:38,380 --> 00:12:39,500
Menarik.

297
00:12:39,500 --> 00:12:41,210
Tidak cukup apa yang kita harapkan.

298
00:12:41,210 --> 00:12:44,810
Jadi, satu perkara untuk merealisasikan
dengan GDB juga, adalah

299
00:12:44,810 --> 00:12:49,000
bahawa ia bukan sehingga anda benar-benar memukul
Selanjutnya, bahawa garis yang anda hanya melihat

300
00:12:49,000 --> 00:12:50,720
benar-benar dijalankan.

301
00:12:50,720 --> 00:12:53,870
Jadi, dalam hal ini Key
belum ditetapkan lagi.

302
00:12:53,870 --> 00:12:57,050
Jadi, kunci adalah beberapa nilai sampah
yang anda lihat di bawah sana.

303
00:12:57,050 --> 00:13:03,680
Negatif $ 120-- --Ini ini satu bilion
dan perkara-perkara yang aneh bukan?

304
00:13:03,680 --> 00:13:05,340
Ia bukan yang utama yang kita harapkan.

305
00:13:05,340 --> 00:13:10,720
Tetapi jika kita tekan Next, dan kemudian kita
mencuba dan kunci Cetak, itu tiga.

306
00:13:10,720 --> 00:13:11,710
>> Semua orang melihat itu?

307
00:13:11,710 --> 00:13:13,780
Jadi, jika anda mendapat sesuatu
bahawa anda seperti, tunggu.

308
00:13:13,780 --> 00:13:15,540
Ini benar-benar
salah, dan aku tidak tahu

309
00:13:15,540 --> 00:13:20,150
bagaimana ini akan berlaku kerana semua yang saya mahu
lakukan adalah memberikan nombor telefon, variabel,

310
00:13:20,150 --> 00:13:22,900
cuba memukul Seterusnya, cuba percetakan
lagi, dan melihat apakah yang bekerja.

311
00:13:22,900 --> 00:13:27,830
Kerana ia hanya akan melaksanakan dan
sebenarnya menetapkan sesuatu selepas anda

312
00:13:27,830 --> 00:13:29,340
tekan Next.

313
00:13:29,340 --> 00:13:30,336
Masuk akal untuk semua orang?

314
00:13:30,336 --> 00:13:30,836
Eh eh?

315
00:13:30,836 --> 00:13:33,220
>> SPEAKER 2: Apabila anda rawak
nombor apa artinya?

316
00:13:33,220 --> 00:13:34,790
>> SPEAKER 1: Ia hanya secara rawak.

317
00:13:34,790 --> 00:13:35,710
Ia hanya sampah.

318
00:13:35,710 --> 00:13:38,320
Ia hanya sesuatu yang anda
komputer secara rawak akan menetapkan.

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

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

321
00:13:40,220 --> 00:13:45,760
Jadi, kita boleh bergerak melalui, dan sebagainya
sekarang kita mempunyai GetString teks biasa.

322
00:13:45,760 --> 00:13:48,600
Jadi, saya hanya memperkenalkan apa
akan berlaku apabila kita tekan Next sini.

323
00:13:48,600 --> 00:13:51,320
GDB kami semacam hilang, kan?

324
00:13:51,320 --> 00:13:55,720
Ini kerana GetString
kini melaksanakan, bukan?

325
00:13:55,720 --> 00:14:01,460
Jadi, ketika kita melihat teks biasa sama
GetString, parens terbuka dan parens,

326
00:14:01,460 --> 00:14:04,380
dan kita memukul Seterusnya, yang mempunyai
sebenarnya dilaksanakan sekarang.

327
00:14:04,380 --> 00:14:06,580
Jadi, ia menunggu
kita untuk memasukkan sesuatu.

328
00:14:06,580 --> 00:14:13,560
>> Jadi, kita akan input makanan kami yang
apa itu gagal seperti yang saya katakan

329
00:14:13,560 --> 00:14:18,020
dan hanya mengatakan bahawa itu
selesai melaksanakan, yang ditutup

330
00:14:18,020 --> 00:14:19,980
braket berarti itu
keluar daripada gelung itu.

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

332
00:14:21,170 --> 00:14:25,420
Jadi, kita boleh tekan Next, dan sekarang, yang saya
pasti anda semua biasa dari Caesar,

333
00:14:25,420 --> 00:14:27,260
ini adalah, apa baris ini akan lakukan.

334
00:14:27,260 --> 00:14:32,030
Ini untuk Int saya sama dengan 0, N sama
Strlen, teks biasa, dan kemudian

335
00:14:32,030 --> 00:14:33,960
Saya kurang daripada n, saya, ditambah, ditambah.

336
00:14:33,960 --> 00:14:35,210
Apa yang gelung ini akan lakukan?

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

338
00:14:37,900 --> 00:14:39,160
Buka mesej anda.

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

340
00:14:39,770 --> 00:14:41,330
Jadi, mari kita mulai melakukan hal itu.

341
00:14:41,330 --> 00:14:47,210
>> Jadi, sekiranya keadaan ini
sesuai, untuk yang pertama kita?

342
00:14:47,210 --> 00:14:52,250
Jika ia merupakan satu B, itu teks biasa I. Kami
boleh mendapatkan maklumat mengenai penduduk tempatan kami.

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

344
00:14:53,610 --> 00:14:57,970
Jadi, saya adalah sifar, dan jika enam, yang
kita harapkan, dan utama kami adalah tiga.

345
00:14:57,970 --> 00:14:59,227
Semua yang masuk akal, bukan?

346
00:14:59,227 --> 00:15:01,310
Nombor-nombor tersebut adalah semua
apa yang mereka perlu.

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

348
00:15:02,590 --> 00:15:03,870
Jadi, bersenandung?

349
00:15:03,870 --> 00:15:05,620
SPEAKER 3: Saya
nombor rawak untuk saya.

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

351
00:15:09,156 --> 00:15:12,030
SPEAKER 1: Baik, kami boleh check-- --Kami
boleh berbual tentang itu dalam satu saat.

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

353
00:15:14,110 --> 00:15:15,750
Tetapi anda harus mendapatkan ini.

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

355
00:15:17,700 --> 00:15:20,130
Jadi, jika kita mempunyai modal yang
B untuk yang pertama kami,

356
00:15:20,130 --> 00:15:22,080
keadaan ini harus menangkapnya, bukan?

357
00:15:22,080 --> 00:15:27,120
Jadi, jika kita memukul Seterusnya, kita lihat
bahawa Jika ini benar-benar dijalankan.

358
00:15:27,120 --> 00:15:29,220
Kerana jika anda sedang mengikuti
bersama-sama dalam kod anda,

359
00:15:29,220 --> 00:15:33,460
talian ini di sini, di mana teks biasa saya
diganti dengan aritmetik ini,

360
00:15:33,460 --> 00:15:35,720
hanya dijalankan jika Jika
keadaan yang tepat betul?

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

362
00:15:36,905 --> 00:15:40,240
>> GDB hanya akan menunjukkan kepada anda
perkara-perkara yang benar-benar melaksanakan.

363
00:15:40,240 --> 00:15:45,140
Oleh itu, jika keadaan Jika ini tidak dipenuhi, itu
hanya akan melangkau ke baris seterusnya.

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

365
00:15:46,540 --> 00:15:48,510
Jadi, kita harus itu.

366
00:15:48,510 --> 00:15:51,171
Kurungan Ini bermakna ia
menutup gelung itu sekarang.

367
00:15:51,171 --> 00:15:52,420
Jadi, ia akan bermula sekali lagi.

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

369
00:15:54,760 --> 00:15:56,280
Begitu sahaja.

370
00:15:56,280 --> 00:15:59,120
Jadi, kita boleh mendapatkan maklumat
kira-kira penduduk tempatan kita di sini,

371
00:15:59,120 --> 00:16:02,575
dan kita melihat bahawa kita yang pertama
surat telah berubah, kan?

372
00:16:02,575 --> 00:16:05,150
Sekarang E, seperti yang diharapkan.

373
00:16:05,150 --> 00:16:07,360
Jadi, kita boleh meneruskan.

374
00:16:07,360 --> 00:16:08,500
>> Dan kami mempunyai cek ini.

375
00:16:08,500 --> 00:16:09,916
Dan pemeriksaan ini harus bekerja, bukan?

376
00:16:09,916 --> 00:16:12,570
Ini A. Ia perlu ditukar
tiga surat ke hadapan.

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

378
00:16:14,320 --> 00:16:16,530
Tetapi jika anda perhatikan, kita
mendapatkan sesuatu yang berbeza.

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

380
00:16:17,580 --> 00:16:22,860
Jadi dalam hal ini di sini, ia tertangkap
itu, dan sebagainya baris ini dilaksanakan,

381
00:16:22,860 --> 00:16:28,620
yang diubahsuai B. kami
Tetapi, dalam hal ini di sini,

382
00:16:28,620 --> 00:16:32,860
yang kita ada bahawa ia hanya melewatkan itu,
dan pergi ke [yang? L SIFF. ?]

383
00:16:32,860 --> 00:16:34,660
Jadi sesuatu yang terjadi di sana.

384
00:16:34,660 --> 00:16:37,780
Apa yang memberitahu anda adalah bahawa,
kita tahu bahawa ia harus menangkap sini,

385
00:16:37,780 --> 00:16:39,200
tetapi ia bukan.

386
00:16:39,200 --> 00:16:42,210
Sesiapa sahaja boleh melihat apa yang kami
masalah ini sejalan itu?

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

388
00:16:45,380 --> 00:16:46,969
Ia satu perkara yang sangat minit.

389
00:16:46,969 --> 00:16:48,510
Dan anda juga boleh melihat kod anda.

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

391
00:16:49,980 --> 00:16:54,940
Ia juga line-- lupa apa garis itu
di besar-- tetapi ia dalam [terdengar].

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

393
00:16:55,480 --> 00:16:58,639
>> SPEAKER 4: Ada di yang lebih besar dari
Halaman jika anda membacanya dalam buku ini.

394
00:16:58,639 --> 00:16:59,430
SPEAKER 1: Tepat sekali.

395
00:16:59,430 --> 00:17:02,620
Jadi, debugger tidak tahu
anda itu, tetapi debugger

396
00:17:02,620 --> 00:17:05,880
boleh membawa anda ke garis
Anda tahu tidak berfungsi.

397
00:17:05,880 --> 00:17:09,319
Dan kadang-kadang, apabila terutama
kemudian pada semester, apabila

398
00:17:09,319 --> 00:17:12,910
Anda sedang berhadapan dengan seratus,
ratus beberapa baris kod, dan anda

399
00:17:12,910 --> 00:17:16,190
tidak tahu di mana ia gagal,
ini merupakan cara terbaik untuk melakukannya.

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

401
00:17:17,900 --> 00:17:18,989
Jadi, kami menemukan bug.

402
00:17:18,989 --> 00:17:21,530
Anda boleh memperbaikinya dalam fail anda,
dan kemudian anda boleh berjalan lagi,

403
00:17:21,530 --> 00:17:23,029
dan semuanya akan bekerja dengan sempurna.

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

405
00:17:24,970 --> 00:17:30,590
Dan yang paling besar adalah
ini boleh kelihatan seperti, OK.

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

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

408
00:17:31,370 --> 00:17:32,744
Anda tahu apa yang anda cari.

409
00:17:32,744 --> 00:17:34,910
Jadi, anda tahu apa yang perlu dilakukan.

410
00:17:34,910 --> 00:17:39,021
>> GDB dapat super berguna kerana anda
boleh mencetak semua hal yang anda

411
00:17:39,021 --> 00:17:39,520
tidak.

412
00:17:39,520 --> 00:17:41,160
Ini jauh lebih berguna daripada printf.

413
00:17:41,160 --> 00:17:43,440
Berapa ramai daripada anda menggunakan
seperti pernyataan printf

414
00:17:43,440 --> 00:17:46,200
untuk memikirkan di mana bug itu, bukan?

415
00:17:46,200 --> 00:17:48,450
Jadi, dengan ini, anda tidak melakukan
perlu terus kembali,

416
00:17:48,450 --> 00:17:51,139
dan suka mengulas di
Printf, atau mengulas keluar,

417
00:17:51,139 --> 00:17:52,930
dan mencari tahu apa
Anda perlu mencetak.

418
00:17:52,930 --> 00:17:55,670
Ini sebenarnya hanya membolehkan anda
langkah melalui, mencetak perkara

419
00:17:55,670 --> 00:18:00,000
seperti yang anda akan melalui, jadi, anda boleh
bagaimana mereka berubah dalam masa sebenar,

420
00:18:00,000 --> 00:18:02,190
sebagai program anda berjalan.

421
00:18:02,190 --> 00:18:04,390
>> Dan ia mengambil sedikit
sedikit untuk membiasakan diri.

422
00:18:04,390 --> 00:18:07,850
Saya sangat akan mengesyorkan hanya jenis
menjadi sedikit kecewa dengan itu

423
00:18:07,850 --> 00:18:08,930
untuk sekarang.

424
00:18:08,930 --> 00:18:13,450
Jika anda menghabiskan satu jam selama
minggu depan belajar bagaimana menggunakan GDB,

425
00:18:13,450 --> 00:18:16,140
Anda akan menyelamatkan diri
begitu banyak masa di kemudian hari.

426
00:18:16,140 --> 00:18:18,750
Dan benar-benar. kami adalah orang-
ini kepada orang-orang setiap tahun,

427
00:18:18,750 --> 00:18:23,890
dan saya ingat ketika saya mengambil
kelas, aku seperti, saya akan baik-baik.

428
00:18:23,890 --> 00:18:24,700
Tidak.

429
00:18:24,700 --> 00:18:27,030
Serangga 6 datang dan saya
seperti, aku akan belajar

430
00:18:27,030 --> 00:18:29,500
bagaimana menggunakan GDB kerana saya tidak
tahu apa yang sedang berlaku di sini.

431
00:18:29,500 --> 00:18:32,940
>> Jadi, jika anda mengambil masa yang begitu
menggunakannya pada program yang lebih kecil

432
00:18:32,940 --> 00:18:35,697
bahawa anda akan menjadi
kerjakan, seperti bekerja

433
00:18:35,697 --> 00:18:37,530
melalui sesuatu seperti
Visionare, seperti ini.

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

435
00:18:38,800 --> 00:18:42,850
Atau jika anda mahu amalan tambahan, saya yakin
Saya boleh datang dengan program kereta,

436
00:18:42,850 --> 00:18:45,300
untuk anda untuk debug jika anda suka.

437
00:18:45,300 --> 00:18:49,300
>> Tetapi jika anda hanya mengambil sedikit masa untuk mendapatkan
digunakan untuk itu, hanya bermain-main dengan itu,

438
00:18:49,300 --> 00:18:50,550
ia benar-benar akan melayani anda dengan baik.

439
00:18:50,550 --> 00:18:52,591
Dan ia benar-benar salah satu daripada
perkara-perkara yang anda hanya

440
00:18:52,591 --> 00:18:57,340
perlu mencuba dan mendapatkan tangan anda kotor
dengan, sebelum anda benar-benar memahaminya.

441
00:18:57,340 --> 00:19:02,090
Saya benar-benar hanya difahami sekali
Saya terpaksa perkara debug dengan itu,

442
00:19:02,090 --> 00:19:08,170
dan ia adalah jauh lebih baik untuk mempunyai idea tentang
cara debug lebih awal daripada kemudian.

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

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

445
00:19:09,625 --> 00:19:12,960
Aku tahu itu jenis seperti
kursus kilat dalam GDB,

446
00:19:12,960 --> 00:19:16,400
dan saya pasti akan bekerja pada mendapatkan
ini untuk melihat waktu yang lebih besar akan datang.

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

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

449
00:19:18,280 --> 00:19:20,390
>> Jadi, jika kita kembali ke PowerPoint kami.

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

451
00:19:27,194 --> 00:19:28,110
Adakah ini akan berfungsi?

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

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

454
00:19:30,210 --> 00:19:31,101
Ya.

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

456
00:19:31,600 --> 00:19:35,480
Jadi, jika anda memerlukan apa-apa dari
mereka lagi, ada senarai.

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

458
00:19:37,160 --> 00:19:40,830
Search sehingga Perduaan, yang semua orang
ingat cermin mata besar Daud

459
00:19:40,830 --> 00:19:42,259
merobek buku telefon pada separuh.

460
00:19:42,259 --> 00:19:44,050
Saya tidak benar-benar mendapatkan
buku telefon lagi,

461
00:19:44,050 --> 00:19:46,530
kerana seperti mana yang anda
mendapatkan buku-buku telefon hari ini?

462
00:19:46,530 --> 00:19:48,220
Saya benar-benar tidak tahu.

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

464
00:19:49,840 --> 00:19:50,590
Search Binary.

465
00:19:50,590 --> 00:19:52,464
Apakah ada yang ingat
bagaimana Binary Search kerja-kerja?

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

467
00:19:54,380 --> 00:19:55,220
Siapa pun?

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

469
00:19:56,325 --> 00:19:58,283
SPEAKER 5: Anda tahu bila
Anda melihat yang setengah

470
00:19:58,283 --> 00:20:01,146
ia akan berada dalam, Berdasarkan itu,
dan menyingkirkan separuh yang lain.

471
00:20:01,146 --> 00:20:01,896
>> SPEAKER 1 Tepat.

472
00:20:01,896 --> 00:20:06,290
Jadi, Cari Perduaan, itu agak a--
--Kami suka menyebutnya membahagi dan menakluk.

473
00:20:06,290 --> 00:20:09,170
Jadi, apa yang anda akan lakukan adalah
Anda akan melihat di tengah-tengah,

474
00:20:09,170 --> 00:20:11,990
dan anda akan melihat apakah itu sesuai
apa yang anda cari.

475
00:20:11,990 --> 00:20:15,420
Dan jika tidak, maka anda cuba untuk
memikirkan, apakah akan dibiarkan

476
00:20:15,420 --> 00:20:16,450
setengah atau separuh benar.

477
00:20:16,450 --> 00:20:19,325
Jadi, mungkin ini jika anda sedang mencari
sesuatu yang menurut abjad,

478
00:20:19,325 --> 00:20:20,720
Anda lihat, oh.

479
00:20:20,720 --> 00:20:22,750
Adakah Allison datang sebelum M?

480
00:20:22,750 --> 00:20:23,250
Ya.

481
00:20:23,250 --> 00:20:25,030
Jadi, kita akan
melihat separuh masa pertama.

482
00:20:25,030 --> 00:20:26,450
>> Atau ia boleh menjadi seperti dengan nombor.

483
00:20:26,450 --> 00:20:28,830
Apa sahaja yang anda boleh
membandingkan, ia boleh disusun.

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

485
00:20:29,920 --> 00:20:31,260
Anda boleh menggunakan carian dedua pada.

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

487
00:20:32,340 --> 00:20:37,455
Jadi, ada yang ingat ini
grafik atau apa ini?

488
00:20:37,455 --> 00:20:39,520
Ini Kerumitan asimptot.

489
00:20:39,520 --> 00:20:42,830
Jadi, grafik ini hanya
menerangkan berapa lama

490
00:20:42,830 --> 00:20:46,230
membawa anda untuk menyelesaikan masalah kerana
anda meningkatkan jumlah perkara

491
00:20:46,230 --> 00:20:47,090
yang anda gunakan.

492
00:20:47,090 --> 00:20:51,260
>> Jadi, kita mempunyai N, yang merupakan masa linear.

493
00:20:51,260 --> 00:20:54,560
Jika N lebih dari dua, yang sedikit
yang lebih baik, masih tumbuh super cepat.

494
00:20:54,560 --> 00:20:58,360
Dan kemudian kami Masuk, yang
apa yang kita anggap Cari Perduaan.

495
00:20:58,360 --> 00:21:03,630
Kalau kita lihat, sebagai masalah anda
mendapat banyak dan lebih besar,

496
00:21:03,630 --> 00:21:06,600
masa yang diperlukan anda untuk menyelesaikannya
tidak benar-benar meningkat banyak.

497
00:21:06,600 --> 00:21:09,010
Ia seperti yang setanding
di sini pada mulanya.

498
00:21:09,010 --> 00:21:10,060
Kau seperti, OK.

499
00:21:10,060 --> 00:21:13,000
Apa-apa sahaja di sini tidak benar-benar
penting yang mana yang kita gunakan,

500
00:21:13,000 --> 00:21:16,220
tetapi anda keluar untuk satu juta, bilion.

501
00:21:16,220 --> 00:21:20,010
Anda sedang cuba untuk mencari --you're some--
cuba mencari jarum di tumpukan jerami.

502
00:21:20,010 --> 00:21:21,550
>> Saya fikir anda mahu masalah ini.

503
00:21:21,550 --> 00:21:25,850
Anda mahu kerumitan ini, tidak
linear kerana untuk semua anda

504
00:21:25,850 --> 00:21:30,049
tahu akan anda mencari melalui
jarum individu, sesuatu dari rumput kering,

505
00:21:30,049 --> 00:21:31,340
cuba mencari jarum anda.

506
00:21:31,340 --> 00:21:34,730
Dan itu bukan yang turut pada pendapat saya.

507
00:21:34,730 --> 00:21:35,500
Saya suka cepat.

508
00:21:35,500 --> 00:21:36,620
Saya suka cekap.

509
00:21:36,620 --> 00:21:40,450
Dan pelajar sebagai pekerja keras anda
Orang-orang ini, anda tahu bekerja lebih cerdas,

510
00:21:40,450 --> 00:21:43,010
bukan lebih keras hal jenis, bagaimana anda
dapat membuat algoritma ini.

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

512
00:21:45,110 --> 00:21:47,910
>> Jadi, kita akan berjalan
melalui hanya contoh cepat.

513
00:21:47,910 --> 00:21:51,090
Saya rasa anda semua perlu mempunyai
tangan pencarian Binary,

514
00:21:51,090 --> 00:21:54,352
tetapi dalam kasus orang adalah sedikit
kabur, ingin agar lebih kuat,

515
00:21:54,352 --> 00:21:56,310
kita akan hanya pergi
melalui contoh di sini.

516
00:21:56,310 --> 00:21:59,490
Jadi, kita cari jika
array mengandungi tujuh.

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

518
00:22:00,540 --> 00:22:06,010
>> Jadi, perkara pertama yang kita lakukan adalah
melihat di tengah-tengah, kan?

519
00:22:06,010 --> 00:22:09,340
Dan juga anda akan coding
Cari Perduaan hanya dalam satu saat.

520
00:22:09,340 --> 00:22:11,310
Jadi, ia akan menjadi seronok.

521
00:22:11,310 --> 00:22:13,710
Jadi kita lihat dalam
array sedikit pertengahan 3.

522
00:22:13,710 --> 00:22:15,501
Adakah 3 sama dengan 7?

523
00:22:15,501 --> 00:22:16,000
Tidak.

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

525
00:22:18,670 --> 00:22:19,550
Ini enam.

526
00:22:19,550 --> 00:22:21,480
Jadi, adalah kurang daripada
atau lebih daripada tujuh?

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

528
00:22:23,080 --> 00:22:23,960
Kurang daripada.

529
00:22:23,960 --> 00:22:24,570
Ya.

530
00:22:24,570 --> 00:22:25,170
Nice job guys.

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

532
00:22:25,569 --> 00:22:27,360
Saya rasa saya seperti saya harus
mempunyai gula-gula kerana saya

533
00:22:27,360 --> 00:22:29,460
ingin membuangnya ke dalam meter.

534
00:22:29,460 --> 00:22:30,270
Ia adalah apa yang saya akan lakukan minggu depan.

535
00:22:30,270 --> 00:22:31,436
Ini akan membuat kalian tajam.

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

537
00:22:32,560 --> 00:22:34,690
>> Jadi, kita buang jauh-jauh
babak pertama, kan?

538
00:22:34,690 --> 00:22:35,670
itu kurang dari.

539
00:22:35,670 --> 00:22:39,325
kita tahu segala-galanya yang
pada yang sebelah kiri

540
00:22:39,325 --> 00:22:41,700
akan menjadi kurang daripada apa yang
kita benar-benar cari.

541
00:22:41,700 --> 00:22:43,491
Jadi, tidak ada keperluan untuk
memberi perhatian kepadanya.

542
00:22:43,491 --> 00:22:45,120
Lupakan saja.

543
00:22:45,120 --> 00:22:48,720
Jadi, kita melihat di sebelah kanan kami,
dan kita melihat pertengahan di sana,

544
00:22:48,720 --> 00:22:50,510
dan sekarang ini sembilan.

545
00:22:50,510 --> 00:22:55,510
Jadi, 9 is-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Lebih besar daripada apa yang kita
cari, kan?

547
00:22:57,470 --> 00:22:59,860
Jadi, kita akan membuang
segala sesuatu ke kanan.

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

549
00:23:00,970 --> 00:23:01,940
Seperti itu.

550
00:23:01,940 --> 00:23:03,700
Sekarang, semua kami pergi dengan adalah satu.

551
00:23:03,700 --> 00:23:07,760
Oleh itu, kita semak, adakah ini satu apa
yang kami cari? ia adalah.

552
00:23:07,760 --> 00:23:08,970
Kami mendapati apa yang kita inginkan.

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

554
00:23:10,440 --> 00:23:11,690
Oleh itu, kita sudah selesai.

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

556
00:23:12,550 --> 00:23:15,740
>> Dan jika anda perhatikan, kita
mempunyai tujuh input di sana.

557
00:23:15,740 --> 00:23:24,320
Ia hanya membawa kami seperti tiga kali,
tetapi jika anda lakukan seperti bilion,

558
00:23:24,320 --> 00:23:28,190
kalian tahu berapa banyak langkah-langkah yang akan
mengambil jika kita mempunyai empat bilion-tiap sesuatu?

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

560
00:23:29,940 --> 00:23:30,455
Mana-mana tekaan?

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

562
00:23:32,286 --> 00:23:33,960
Ini 32.

563
00:23:33,960 --> 00:23:37,110
32 langkah-langkah untuk mencari sesuatu
dalam empat bilion

564
00:23:37,110 --> 00:23:39,650
elemen array kerana kuasa dua.

565
00:23:39,650 --> 00:23:43,550
Jadi kedua-duanya adalah 32, adalah untuk empat bilion.

566
00:23:43,550 --> 00:23:50,430
>> Bagaimana begitu cantik gila anda masih berada dalam
seperti jumlah yang cukup kecil langkah-langkah

567
00:23:50,430 --> 00:23:52,650
untuk mencari sesuatu di
empat bilion elemen.

568
00:23:52,650 --> 00:23:55,730
Maka pada masa yang sama, kami
akan kode ini

569
00:23:55,730 --> 00:23:58,950
jadi kalian benar-benar dapat
jenis melihat bagaimana ini bekerja.

570
00:23:58,950 --> 00:24:01,520
Baiklah, jadi kalian dapat kode.

571
00:24:01,520 --> 00:24:04,100
Saya akan membiarkan kalian
bercakap untuk sedikit.

572
00:24:04,100 --> 00:24:07,970
Mengenal orang-orang di sekeliling anda, yang
apa yang orang inginkan dari bagian terakhir.

573
00:24:07,970 --> 00:24:10,280
>> Jadi untuk mengenal orang-orang di sekeliling anda.

574
00:24:10,280 --> 00:24:11,305
Bercakap untuk sedikit.

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

576
00:24:12,580 --> 00:24:15,730
Dan semua yang saya inginkan dari anda
orang sekarang hanya

577
00:24:15,730 --> 00:24:17,575
cuba untuk membuat garis besar pseudokod.

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

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

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

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

582
00:24:23,320 --> 00:24:29,520
Apa yang saya mahu dari anda semua adalah anda
hanya akan mengisi dalam kes semasa ini.

583
00:24:29,520 --> 00:24:32,170
Jadi saya telah menetapkan atas ini
dan batas bawah yang

584
00:24:32,170 --> 00:24:35,250
mewakili permulaan
dan akhir array kita.

585
00:24:35,250 --> 00:24:40,440
Dan anda akan benar-benar
loop melalui dan memikirkan

586
00:24:40,440 --> 00:24:42,470
apa yang kita lakukan dalam loop selama ini.

587
00:24:42,470 --> 00:24:45,810
>> Jadi jika anda boleh mencari out-- saya mempunyai
Petunjuk besar-- apakah kes-kes

588
00:24:45,810 --> 00:24:46,640
yang kita ada di sini?

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

590
00:24:48,100 --> 00:24:51,560
Jadi, jika anda ingin mengetahui
kes, kami akan pseudokod mereka

591
00:24:51,560 --> 00:24:53,350
dan kemudian kita akan benar-benar memberi kod kepada mereka.

592
00:24:53,350 --> 00:24:55,330
Dan ia akan menjadi, saya
berfikir, mudah-mudahan ia bakal

593
00:24:55,330 --> 00:24:56,788
menjadi sedikit lebih mudah daripada yang anda harapkan.

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

595
00:24:57,554 --> 00:25:00,220
Oleh kerana ia tidak bahawa kod banyak,
sebenarnya, yang benar-benar sejuk.

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

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

598
00:25:35,018 --> 00:25:35,893
>> PELAJAR: [didengar]?

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

600
00:25:36,984 --> 00:25:37,650
PENGAJAR: Ya.

601
00:25:37,650 --> 00:25:38,595
Ada sesuatu
untuk mencari di tengah-tengah.

602
00:25:38,595 --> 00:25:39,552
>> PELAJAR: Jadi kita boleh menggunakannya.

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

604
00:25:39,770 --> 00:25:40,603
>> PENGAJAR: Perfect.

605
00:25:40,603 --> 00:25:42,950
Jadi itulah perkara pertama yang perlu kita lakukan.

606
00:25:42,950 --> 00:25:44,330
Jadi mencari tengah-tengah.

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

608
00:25:45,415 --> 00:25:45,915
Besar.

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

610
00:25:47,770 --> 00:25:55,010
Jadi adakah anda mempunyai idea tentang bagaimana kita mungkin
benar-benar menemukan tengah dengan kod?

611
00:25:55,010 --> 00:25:55,980
>> PELAJAR: Ya.

612
00:25:55,980 --> 00:25:57,000
n lebih dari 2?

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

614
00:25:58,500 --> 00:25:59,500
PENGAJAR: Jadi n lebih dari 2.

615
00:25:59,500 --> 00:26:05,170
Jadi, satu hal yang perlu diingat adalah bahawa
batas atas dan bawah Anda.

616
00:26:05,170 --> 00:26:08,110
Kami terus mengecutkan bahagian
array kami sedang mencari untuk.

617
00:26:08,110 --> 00:26:11,970
Jadi n lebih dari 2 hanya akan bekerja
untuk perkara pertama yang kami lakukan.

618
00:26:11,970 --> 00:26:17,810
Jadi mengambil atas dan bawah kira,
bagaimana mungkin kita mendapatkan bahwa unsur menengah?

619
00:26:17,810 --> 00:26:20,640
Kerana kita mahu tengah
antara atas dan bawah, kan?

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

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

622
00:26:22,494 --> 00:26:23,369
>> PELAJAR: [didengar].

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

624
00:26:26,170 --> 00:26:28,080
>> PENGAJAR: Oleh itu, kita mempunyai beberapa menengah.

625
00:26:28,080 --> 00:26:32,730
Dan ia akan menjadi lebih rendah atas ditambah lebih dari 2.

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

627
00:26:34,740 --> 00:26:35,690
Awesome.

628
00:26:35,690 --> 00:26:36,570
Di sana kami pergi.

629
00:26:36,570 --> 00:26:37,280
Satu baris ke bawah.

630
00:26:37,280 --> 00:26:38,560
Kalian dalam perjalanan anda.

631
00:26:38,560 --> 00:26:41,400
Jadi sekarang kita mempunyai kita
pertengahan, apa yang kita mahu lakukan?

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

633
00:26:45,050 --> 00:26:45,900
Hanya pada umumnya.

634
00:26:45,900 --> 00:26:47,734
Anda tidak perlu memberi kod itu.

635
00:26:47,734 --> 00:26:48,335
Ya.

636
00:26:48,335 --> 00:26:49,210
PELAJAR: [didengar]?

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

638
00:27:00,310 --> 00:27:10,310
PENGAJAR: Jadi itu ditambah kerana anda
mencari purata antara kedua-dua

639
00:27:10,310 --> 00:27:10,810
daripada mereka.

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

641
00:27:11,890 --> 00:27:17,370
Jadi, jika anda menganggap mereka sebagai jenis
peningkatan dalam dari sisi,

642
00:27:17,370 --> 00:27:21,640
berfikir tentang hal itu sebagai pendekatan
tengah-tengah, anda mahu seperti itu.

643
00:27:21,640 --> 00:27:27,150
Jadi, jika anda berada di kedua sisi
menengah, dan kami mempunyai seperti 5 dan 7.

644
00:27:27,150 --> 00:27:31,440
Apabila anda menambah mereka bersama-sama anda
mendapatkan 12, anda membahagi dengan 2, adalah 6.

645
00:27:31,440 --> 00:27:33,726
>> Kadang-kadang ia sukar untuk
menjelaskan mengapa yang bekerja,

646
00:27:33,726 --> 00:27:35,600
tetapi jika anda bekerja dengan
contoh kadang-kadang,

647
00:27:35,600 --> 00:27:37,962
ia akan membantu anda memahami jika
ia perlu tambah atau tolak.

648
00:27:37,962 --> 00:27:38,846
Ya.

649
00:27:38,846 --> 00:27:40,830
>> PELAJAR: [didengar]
betul-betul di tengah-tengah

650
00:27:40,830 --> 00:27:43,950
jika mereka mempunyai kes di mana
ada banyak dari jumlah yang lebih kecil

651
00:27:43,950 --> 00:27:45,860
dan seperti satu jumlah yang besar?

652
00:27:45,860 --> 00:27:49,750
>> PENGAJAR: Jadi semua yang anda perlukan
adalah tengah array.

653
00:27:49,750 --> 00:27:53,010
Jadi, jika anda telah mempunyai banyak bilangan yang kecil
dan kemudian satu nombor benar-benar besar

654
00:27:53,010 --> 00:27:54,799
pada akhirnya, ia tidak mengapa.

655
00:27:54,799 --> 00:27:56,840
Apa yang penting ialah bahawa
mereka disusun, anda hanya

656
00:27:56,840 --> 00:27:59,339
ingin melihat pertengahan
array kerana anda masih

657
00:27:59,339 --> 00:28:00,700
mengiris masalah anda pada separuh.

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

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

660
00:28:03,680 --> 00:28:06,430
Jadi sekarang kita mempunyai
pertengahan, apa yang kita lakukan seterusnya?

661
00:28:06,430 --> 00:28:07,150
>> PELAJAR: Bandingkan.

662
00:28:07,150 --> 00:28:08,150
PENGAJAR: The membandingkan.

663
00:28:08,150 --> 00:28:11,670
Jadi membandingkan tengah untuk value_wanted.

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

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

666
00:28:15,160 --> 00:28:17,950
Jadi anda lihat di sini kita mempunyai
nilai ini kita mahu di sini.

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

668
00:28:22,012 --> 00:28:23,095
Ingat ini adalah array.

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

670
00:28:24,100 --> 00:28:26,970
Jadi tengah merujuk kepada indeks.

671
00:28:26,970 --> 00:28:29,785
Oleh itu, kita ingin melakukan nilai-nilai tengah.

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

673
00:28:32,380 --> 00:28:35,650
Jangan lupa jika anda mahu
untuk membandingkan, sama dengan dua kali ganda.

674
00:28:35,650 --> 00:28:38,250
Anda boleh melakukan satu sama anda
hanya akan menetapkan kembali,

675
00:28:38,250 --> 00:28:41,090
dan kemudian, tentu saja, itu
akan menjadi nilai yang anda mahu.

676
00:28:41,090 --> 00:28:42,300
Jadi, jangan lakukan itu.

677
00:28:42,300 --> 00:28:44,350
>> Jadi kita akan melihat apakah
nilai-nilai yang di tengah-tengah

678
00:28:44,350 --> 00:28:46,460
adalah sama dengan nilai yang kami mahu.

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

680
00:28:47,749 --> 00:28:48,790
Jangan lupa kawat gigi anda.

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

682
00:28:50,520 --> 00:28:52,235
Dropbox harus pergi.

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

684
00:28:54,140 --> 00:28:56,200
Jadi apa yang kita lakukan dalam hal ini?

685
00:28:56,200 --> 00:28:59,360
Jika ia adalah apa yang kita mahu untuk kembali?

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

687
00:29:01,510 --> 00:29:02,626
Kami katakan.

688
00:29:02,626 --> 00:29:03,440
>> PELAJAR: Cetak off.

689
00:29:03,440 --> 00:29:05,314
>> PENGAJAR: Kami
tidak mahu mencetak.

690
00:29:05,314 --> 00:29:08,220
Jadi, ini adalah bool di sini, jadi kami
mahu kembali benar atau salah.

691
00:29:08,220 --> 00:29:12,280
Kami katakan, adalah nombor ini
sebuah [? RRA? ?] Oleh itu, jika ia adalah,

692
00:29:12,280 --> 00:29:13,788
kita hanya mengembalikannya benar.

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

694
00:29:16,780 --> 00:29:17,760
Jika saya boleh mengeja benar.

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

696
00:29:18,830 --> 00:29:20,805
>> PELAJAR: Mengapa tidak anda kembali sifar?

697
00:29:20,805 --> 00:29:22,930
PENGAJAR: Jadi, anda boleh
kembali sifar jika anda mahu.

698
00:29:22,930 --> 00:29:26,780
Tetapi dalam kes ini kerana
fungsi kita kembali bool,

699
00:29:26,780 --> 00:29:28,962
kita perlu kembali sama ada benar atau salah.

700
00:29:28,962 --> 00:29:30,920
PELAJAR: Apabila anda
mengatakan ungkapan boolean,

701
00:29:30,920 --> 00:29:33,450
anda boleh menetapkan ia sama dengan salah?

702
00:29:33,450 --> 00:29:39,860
Seperti jika saya ingin mengatakan, jika keadaan ini
tidak dipenuhi, seperti atas adalah sama dengan yang salah.

703
00:29:39,860 --> 00:29:42,332
Adakah ia akan memahami jika anda hanya
menempatkan palsu di sebelah yang lain?

704
00:29:42,332 --> 00:29:43,040
PENGAJAR: Ya.

705
00:29:43,040 --> 00:29:44,820
Jadi sebenarnya jika anda
pernah melakukan sesuatu

706
00:29:44,820 --> 00:29:49,600
seperti adalah atas atau lebih rendah,
yang mengembalikan benar atau salah

707
00:29:49,600 --> 00:29:53,850
dan itu gaya sebenarnya buruk untuk
katakan sama sama benar atau sama dengan

708
00:29:53,850 --> 00:29:54,840
sama dengan yang salah.

709
00:29:54,840 --> 00:30:00,210
Anda ingin menggunakan hasil itu
sebagai dirinya sebagai cek.

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

711
00:30:04,720 --> 00:30:05,860
Tidak apa yang saya mahu.

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

713
00:30:08,150 --> 00:30:09,240
Itu yang saya mahu.

714
00:30:09,240 --> 00:30:13,205
Jadi, dalam kes anda bertanya
tentang sesuatu seperti menyimpan ini dalam c.

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

716
00:30:16,320 --> 00:30:25,150
>> Jadi, jika kita mempunyai int main (void)
dan sesuatu seperti ini.

717
00:30:25,150 --> 00:30:31,922
Dan jika anda mempunyai adalah atas
input beberapa dan anda

718
00:30:31,922 --> 00:30:33,630
menanyakan apakah yang boleh anda lakukan
sesuatu seperti ini?

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

720
00:30:35,010 --> 00:30:35,679
Betul?

721
00:30:35,679 --> 00:30:37,470
PELAJAR: Saya cuba
untuk melakukannya [terdengar].

722
00:30:37,470 --> 00:30:38,450
Kerana jika it's--

723
00:30:38,450 --> 00:30:39,200
PENGAJAR: Benar.

724
00:30:39,200 --> 00:30:41,197
Jadi, anda mahu ini adalah palsu, bukan?

725
00:30:41,197 --> 00:30:41,780
PELAJAR: Ya.

726
00:30:41,780 --> 00:30:45,960
PENGAJAR: Jadi dalam hal ini anda
mahu ia untuk melaksanakan jika ia tidak benar.

727
00:30:45,960 --> 00:30:50,510
Jadi perkara yang sejuk yang anda lakukan ada ini.

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

729
00:30:52,900 --> 00:30:55,650
Jadi ingat seru
titik meniadakan tiap sesuatu?

730
00:30:55,650 --> 00:30:58,270
Dikatakan [terdengar] tidak bermakna.

731
00:30:58,270 --> 00:31:03,590
Oleh itu, jika kita melihat hanya
bahagian ini di sini, Anda lebih

732
00:31:03,590 --> 00:31:05,740
mengatakan bahawa untuk menilai
palsu seperti yang anda mahu ia.

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

734
00:31:06,790 --> 00:31:09,880
Tidak palsu benar yang
bermakna ini akan melaksanakan.

735
00:31:09,880 --> 00:31:11,037
Adakah ini masuk akal?

736
00:31:11,037 --> 00:31:11,620
PELAJAR: Ya.

737
00:31:11,620 --> 00:31:12,453
PENGAJAR: Awesome.

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

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

740
00:31:14,300 --> 00:31:16,330
Jadi kita hanya boleh kembali
benar dalam kes ini.

741
00:31:16,330 --> 00:31:20,357
Jadi sekarang kita mempunyai dua lain
kes dalam kes ini.

742
00:31:20,357 --> 00:31:21,565
Apakah dua kes kami yang lain?

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

744
00:31:31,610 --> 00:31:32,900
Mari kita melakukannya dengan cara ini.

745
00:31:32,900 --> 00:31:40,660
Jadi mari kita mulakan dengan yang lain
jika nilai-nilai di tengah-tengah

746
00:31:40,660 --> 00:31:43,230
adalah kurang daripada nilai yang kami mahu.

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

748
00:31:47,200 --> 00:31:52,020
Jadi nilai kita di tengah-tengah adalah kurang
daripada nilai yang kami cari.

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

750
00:31:53,765 --> 00:31:56,720
>> Jadi yang terikat yang anda
fikir kita mahu update?

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

752
00:31:57,870 --> 00:31:58,780
Atas atau bawah?

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

754
00:32:01,440 --> 00:32:01,940
Atas?

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

756
00:32:03,230 --> 00:32:06,470
Jadi pihak mana array
kita akan melihat?

757
00:32:06,470 --> 00:32:07,500
>> PELAJAR: yang lebih rendah.

758
00:32:07,500 --> 00:32:09,750
>> PENGAJAR: Kami akan kita
untuk melihat sebelah kiri.

759
00:32:09,750 --> 00:32:11,120
Jadi lain jika kita terlalu kurang.

760
00:32:11,120 --> 00:32:14,730
Jadi nilai tengah anda di sini
adalah kurang daripada apa yang kita inginkan.

761
00:32:14,730 --> 00:32:17,202
Oleh itu, kita ingin mengambil
kanan array kita.

762
00:32:17,202 --> 00:32:18,910
Oleh itu, kita akan
mengemaskini batas bawah kami.

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

764
00:32:20,210 --> 00:32:23,020
Jadi kita akan menyerahhakkan semula yang lebih rendah kami.

765
00:32:23,020 --> 00:32:25,221
Dan apa yang anda berfikir yang lebih rendah seharusnya?

766
00:32:25,221 --> 00:32:26,304
PELAJAR: Nilai menengah?

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

768
00:32:27,446 --> 00:32:28,820
PENGAJAR: Jadi value-- tengah

769
00:32:28,820 --> 00:32:30,136
PELAJAR: Plus 1.

770
00:32:30,136 --> 00:32:31,010
PENGAJAR: --plus 1.

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

772
00:32:32,300 --> 00:32:34,380
Bolehkah sesiapa beritahu saya mengapa
kita ada yang ditambah 1?

773
00:32:34,380 --> 00:32:35,730
>> PELAJAR: [? Tidak ada nilai?]
lebih sama dengan itu.

774
00:32:35,730 --> 00:32:36,120
>> PENGAJAR: Benar.

775
00:32:36,120 --> 00:32:38,661
Kerana kita sudah tahu bahawa
nilai menengah kita tidak sama dengan

776
00:32:38,661 --> 00:32:42,750
dan kami mahu ia tidak termasuk
daripada semua carian berikutnya.

777
00:32:42,750 --> 00:32:46,360
Jika anda terlupa bahawa campur 1, ini
akan seperti gelung tanpa batas.

778
00:32:46,360 --> 00:32:49,620
Dan anda hanya akan terperangkap dalam
gelung tak terhingga dan kemudian anda akan segfault

779
00:32:49,620 --> 00:32:50,370
dan sesuatu yang buruk.

780
00:32:50,370 --> 00:32:54,780
Jadi selalu memastikan bahawa anda tidak
termasuk nilai yang anda hanya

781
00:32:54,780 --> 00:32:55,380
memandang.

782
00:32:55,380 --> 00:32:58,530
Oleh itu, kita berhati-hati itu dengan ditambah 1.

783
00:32:58,530 --> 00:33:04,840
>> Jadi sekarang kita mempunyai keadaan terakhir kami
yang saya selalu demi keamanan

784
00:33:04,840 --> 00:33:12,664
anda boleh menyemak di sini, lain jika nilai-pada
tengah adalah lebih besar daripada nilai

785
00:33:12,664 --> 00:33:13,163
yang kita mahu.

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

787
00:33:16,260 --> 00:33:20,230
Ini bermakna bahawa kita mahu
separuh kiri.

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

789
00:33:21,350 --> 00:33:23,260
Jadi mana yang kita akan mengemas kini?

790
00:33:23,260 --> 00:33:23,760
Atas.

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

792
00:33:25,470 --> 00:33:26,970
Dan apa yang satu ini akan sama?

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

794
00:33:31,630 --> 00:33:33,690
Tengah tolak 1 kerana,
sudah tentu, kita mahu

795
00:33:33,690 --> 00:33:38,370
memastikan bahawa kita tidak
melihat bahawa nilai pertengahan lagi.

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

797
00:33:41,830 --> 00:33:45,110
Dan kemudian kita ada.

798
00:33:45,110 --> 00:33:45,610
Itu saja.

799
00:33:45,610 --> 00:33:46,820
Itu sahaja carian binari adalah.

800
00:33:46,820 --> 00:33:48,190
Ia bukan yang buruk, benar?

801
00:33:48,190 --> 00:33:51,590
Ia seperti 10 baris
kod dengan ruang putih.

802
00:33:51,590 --> 00:33:57,510
Jadi sangat kuat, sangat berguna, anda akan
akan menggunakannya di salah satu pşet anda kemudian.

803
00:33:57,510 --> 00:33:59,360
Mungkin tidak yang satu ini, tetapi kemudian.

804
00:33:59,360 --> 00:34:00,670
Jadi mempelajarinya.

805
00:34:00,670 --> 00:34:01,510
Sukakannya.

806
00:34:01,510 --> 00:34:02,980
Ini akan melayan anda dengan baik.

807
00:34:02,980 --> 00:34:05,370
Jadi tidak ada yang punya
soalan pada carian binari?

808
00:34:05,370 --> 00:34:06,196
Ya.

809
00:34:06,196 --> 00:34:09,840
>> PELAJAR: Apa itu penting
sama ada anda adalah n genap atau ganjil?

810
00:34:09,840 --> 00:34:10,750
>> PENGAJAR: No.

811
00:34:10,750 --> 00:34:18,150
Kerana kita membuangnya ke tengah seperti
int, ia hanya akan memotong ia.

812
00:34:18,150 --> 00:34:21,600
Jadi ia akan kekal integer dan akan
akhirnya menyusun melalui semua.

813
00:34:21,600 --> 00:34:23,909
Jadi anda tidak perlu bimbang tentang itu.

814
00:34:23,909 --> 00:34:24,580
Semua orang yang baik?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Awesome.

817
00:34:26,850 --> 00:34:27,919
Sejuk.

818
00:34:27,919 --> 00:34:30,836
Jadi, kalian mendapat ini.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Tayangan slaid.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
Jadi seperti yang kita bercakap tentang, saya tahu
Daud disebutkan runtimes kerumitan.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Jadi dalam kes ini, ia hanya
satu, yang kita panggil masa yang sama.

825
00:34:50,340 --> 00:34:51,909
Bolehkah sesiapa beritahu saya mengapa yang mungkin?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Apakah jenis senario akan yang memerlukan?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> PELAJAR: [didengar] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
PENGAJAR: Jadi tengah yang yang
Elemen pertama ini dapat kita, kan?

833
00:35:03,830 --> 00:35:08,167
Jadi baik pelbagai satu atau
apa sahaja yang kami cari hanya

834
00:35:08,167 --> 00:35:09,750
kebetulan memukul dab di tengah-tengah.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Jadi itu yang terjadi terbaik.

837
00:35:13,380 --> 00:35:17,540
Anda masuk ke dalam masalah sebenar, mungkin tidak
akan mencapai [terdengar] yang sering.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Bagaimana pula dengan kes kami yang paling teruk?

840
00:35:19,750 --> 00:35:21,270
Kes kami terburuk adalah log n.

841
00:35:21,270 --> 00:35:25,360
Dan yang ada hubungannya dengan keseluruhan
kuasa dua perkara yang saya bercakap tentang.

842
00:35:25,360 --> 00:35:30,930
>> Jadi dalam hal yang paling teruk ia bermakna
bahawa kami terpaksa memotong pelbagai ke bawah

843
00:35:30,930 --> 00:35:33,270
sehingga unsur satu.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Jadi kami terpaksa memotong ke bawah pada separuh
sebanyak yang mungkin kami bisa.

846
00:35:38,930 --> 00:35:41,430
Itulah mengapa ia log n kerana
Anda hanya terus membahagikan dengan dua.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Jadi andaian, perkara yang anda
perlu tahu jika anda pernah

849
00:35:45,830 --> 00:35:48,050
akan menggunakan carian dedua.

850
00:35:48,050 --> 00:35:50,680
Unsur-unsur anda harus diurutkan.

851
00:35:50,680 --> 00:35:53,890
Mereka perlu disusun kerana
itulah satu-satunya cara yang anda

852
00:35:53,890 --> 00:35:57,060
boleh tahu jika anda mampu
untuk membuang setengah dari itu.

853
00:35:57,060 --> 00:36:00,260
>> Jika anda mempunyai beg bercampur aduk ini
nombor dan kau mengatakan,

854
00:36:00,260 --> 00:36:05,380
OK, saya akan memeriksa tengah
jumlah dan bilangan yang saya cari

855
00:36:05,380 --> 00:36:08,510
adalah kurang dari itu, aku hanya akan
untuk sewenang-wenangnya membuang satu setengah.

856
00:36:08,510 --> 00:36:11,130
Anda tidak akan tahu jika anda
nombor pada separuh yang lain.

857
00:36:11,130 --> 00:36:12,655
Senarai anda harus diurutkan.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Selain itu, ini mungkin
pergi ke depan sedikit,

860
00:36:16,560 --> 00:36:18,360
tetapi anda perlu mempunyai akses rawak.

861
00:36:18,360 --> 00:36:21,940
Anda perlu dapat langsung
pergi ke elemen menengah.

862
00:36:21,940 --> 00:36:25,110
Jika anda mempunyai untuk melintasi
melalui sesuatu

863
00:36:25,110 --> 00:36:28,630
atau ia akan membawa anda langkah-langkah tambahan
untuk sampai ke elemen tengah,

864
00:36:28,630 --> 00:36:31,750
ia tidak log n lagi kerana
anda menambah lebih banyak kerja ke dalamnya.

865
00:36:31,750 --> 00:36:34,800
Dan ini akan membuat sedikit
arti yang lebih dalam dua minggu,

866
00:36:34,800 --> 00:36:37,950
tetapi saya hanya jenis mahu pengantar,
memberikan kalian idea tentang apa yang

867
00:36:37,950 --> 00:36:38,999
yang akan datang.

868
00:36:38,999 --> 00:36:40,790
Tetapi mereka adalah dua
andaian penting

869
00:36:40,790 --> 00:36:44,804
yang anda perlukan untuk daftar binari.

870
00:36:44,804 --> 00:36:45,720
Pastikan itu disusun.

871
00:36:45,720 --> 00:36:47,920
Itu salah satu yang besar untuk
kalian sekarang.

872
00:36:47,920 --> 00:36:52,170
Dan pada yang kita dapat masuk ke
sisa macam kami.

873
00:36:52,170 --> 00:36:56,444
Jadi empat gelembung sorts--,
penyisipan, pemilihan, dan gabungan.

874
00:36:56,444 --> 00:36:57,485
Mereka semua jenis sejuk.

875
00:36:57,485 --> 00:37:02,860
Jika kalian membuat keputusan untuk mengambil CS 124,
Anda akan belajar tentang pelbagai macam.

876
00:37:02,860 --> 00:37:07,575
Dan jika anda seorang penggemar XKCD, ada
adalah tentang komik yang menyeronokkan!

877
00:37:07,575 --> 00:37:11,530
seperti macam benar-benar berkesan, yang saya
sangat menyarankan anda akan melihat.

878
00:37:11,530 --> 00:37:16,170
Salah seorang daripada mereka adalah seperti semacam panik, yang
adalah seperti, oh tidak, kembali pelbagai rawak.

879
00:37:16,170 --> 00:37:16,991
Sistem shutdown.

880
00:37:16,991 --> 00:37:17,490
Tinggalkan.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Jadi humor culun selalu baik.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Jadi tidak ada yang ingat jenis
seperti hanya idea umum

885
00:37:25,750 --> 00:37:27,810
bagaimana semacam gelembung berfungsi.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Anda masih ingat?

888
00:37:32,155 --> 00:37:32,755
>> PELAJAR: Ya.

889
00:37:32,755 --> 00:37:33,970
>> PENGAJAR: Pergi untuk itu.

890
00:37:33,970 --> 00:37:38,980
>> PELAJAR: Jadi, anda akan melalui dan
jika ia lebih besar, maka anda menukar dua.

891
00:37:38,980 --> 00:37:39,820
>> PENGAJAR: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Tepat.

893
00:37:40,564 --> 00:37:41,730
Jadi anda hanya beralih melalui.

894
00:37:41,730 --> 00:37:43,050
Anda memeriksa dua nombor.

895
00:37:43,050 --> 00:37:46,510
Jika yang sebelumnya lebih besar
daripada yang selepas itu,

896
00:37:46,510 --> 00:37:50,230
Anda hanya menukar mereka supaya dalam
cara ini semua nombor yang lebih tinggi

897
00:37:50,230 --> 00:37:54,990
meluap menjelang akhir senarai
dan semua jumlah yang lebih rendah gelembung bawah.

898
00:37:54,990 --> 00:37:59,355
>> Adakah dia menunjukkan kalian sejuk
kesan bunyi menyortir video?

899
00:37:59,355 --> 00:38:00,480
Ia adalah jenis sejuk.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Supaya Robert hanya berkata, algoritma
bahawa anda hanya langkah melalui senarai,

902
00:38:05,200 --> 00:38:07,930
menukar nilai-nilai yang berdekatan
jika mereka tidak teratur.

903
00:38:07,930 --> 00:38:10,975
Dan kemudian hanya terus mengulangi
sehingga anda tidak membuat sebarang pertukaran.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Jadi tidak buruk, kan?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Oleh itu, kita hanya mempunyai satu contoh yang cepat di sini.

908
00:38:16,319 --> 00:38:18,360
Jadi ini akan menyusun
mereka dalam urutan menaik.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Oleh itu, apabila kita pergi melalui pertama
masa, kita melihat melalui lapan

911
00:38:23,470 --> 00:38:26,880
dan enam yang jelas tidak
dalam rangka, kita menukar mereka.

912
00:38:26,880 --> 00:38:27,985
>> Jadi melihat satu depan.

913
00:38:27,985 --> 00:38:29,430
Lapan dan empat tidak teratur.

914
00:38:29,430 --> 00:38:30,450
Swap mereka.

915
00:38:30,450 --> 00:38:32,530
Dan kemudian lapan dan dua, swap mereka.

916
00:38:32,530 --> 00:38:33,470
Di sana kami pergi.

917
00:38:33,470 --> 00:38:39,519
Jadi setelah pertama anda, anda
tahu bahawa jumlah terbesar anda

918
00:38:39,519 --> 00:38:41,810
akan menjadi sepanjang jalan
di bahagian atas kerana ia hanya

919
00:38:41,810 --> 00:38:44,210
akan terus-menerus
lebih besar daripada segala sesuatu yang lain

920
00:38:44,210 --> 00:38:46,810
dan ia hanya akan gelembung
sehingga sampai ke akhir di sana.

921
00:38:46,810 --> 00:38:48,226
Adakah ini masuk akal untuk semua orang?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Sejuk.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Jadi kita melihat pas kedua kami.

926
00:38:53,920 --> 00:38:54,980
Enam dan empat, suis.

927
00:38:54,980 --> 00:38:55,920
Enam dan dua, suis.

928
00:38:55,920 --> 00:38:58,700
Dan sekarang kita mempunyai beberapa perkara dalam rangka.

929
00:38:58,700 --> 00:39:02,240
Jadi untuk setiap pas yang kita
membuat melalui semua senarai kami,

930
00:39:02,240 --> 00:39:06,320
kita tahu bahawa seperti yang banyak nombor
pada akhirnya akan sudah diselesaikan.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Jadi kita lulus ketiga,
yang merupakan salah satu swap.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
Dan kemudian pada keempat kami
lulus, kita mempunyai sifar slot.

935
00:39:15,910 --> 00:39:18,570
Dan dengan itu kita tahu bahawa kita
array sudah disusun.

936
00:39:18,570 --> 00:39:20,900
>> Dan itu adalah besar
perkara dengan semacam gelembung.

937
00:39:20,900 --> 00:39:23,720
Kita tahu bahawa apabila kita
mempunyai swap sifar, yang

938
00:39:23,720 --> 00:39:26,497
bermakna segala sesuatu yang
adalah dalam rangka lengkap.

939
00:39:26,497 --> 00:39:27,580
Ini semacam bagaimana kita memeriksa.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Oleh itu, kita juga akan memberi kod gelembung
semacam yang juga tidak terlalu buruk.

942
00:39:36,480 --> 00:39:38,120
Tiada seorang pun daripada ini adalah yang buruk.

943
00:39:38,120 --> 00:39:40,210
Saya tahu bahawa mereka boleh kelihatan sedikit menakutkan.

944
00:39:40,210 --> 00:39:42,124
Saya tahu apabila saya mengambil
kelas, walaupun saya

945
00:39:42,124 --> 00:39:44,290
mengajar kelas untuk
kali pertama tahun lalu,

946
00:39:44,290 --> 00:39:46,165
Aku seperti, bagaimana saya boleh melakukan ini?

947
00:39:46,165 --> 00:39:48,540
Ia masuk akal dalam teori, tetapi
bagaimana kita benar-benar melakukan ini?

948
00:39:48,540 --> 00:39:51,420
Oleh sebab itulah saya juga ingin berjalan
melalui kod dengan kalian di sini.

949
00:39:51,420 --> 00:39:54,915
Jadi saya mempunyai satu pseudokod
untuk kalian kali ini.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Jadi, ingatlah ini sebagai
kami akan beralih ke atas.

952
00:39:58,970 --> 00:40:04,210
Oleh itu, kita mempunyai beberapa kaunter yang
menjejaki swap kami,

953
00:40:04,210 --> 00:40:08,370
kerana kita perlu memastikan
bahawa kami sedang memeriksa itu.

954
00:40:08,370 --> 00:40:11,830
Dan kita beralih seluruh array
kerana kami hanya melakukan dengan contoh ini.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Jika elemen yang sebelum ini lebih besar daripada
elemen setelah di mana kita berada,

957
00:40:17,325 --> 00:40:20,760
kita swap mereka dan kita kenaikan kami
kaunter kerana sebaik sahaja kami menukar,

958
00:40:20,760 --> 00:40:23,850
Kami menulis untuk memberitahu kaunter kami tahu itu.

959
00:40:23,850 --> 00:40:26,247
Mana-mana soalan di sana?

960
00:40:26,247 --> 00:40:27,580
Sesuatu kelihatan lucu di sini.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
PELAJAR: Apakah anda menetapkan kaunter untuk sifar
setiap kali anda pergi melalui loop?

963
00:40:32,350 --> 00:40:34,339
Adakah anda tidak terus
kembali kepada sifar setiap kali?

964
00:40:34,339 --> 00:40:35,505
PENGAJAR: Tidak semestinya.

965
00:40:35,505 --> 00:40:39,710
Jadi apa yang berlaku ialah kita pergi ke sini.

966
00:40:39,710 --> 00:40:43,830
Begitu juga semasa, ingat, ini
akan melaksanakan sekali tanpa gagal.

967
00:40:43,830 --> 00:40:46,480
Jadi ia akan menetapkan
kaunter sama dengan nol,

968
00:40:46,480 --> 00:40:48,070
kemudian ia akan beralih melalui.

969
00:40:48,070 --> 00:40:50,590
Sebagai iterates melalui,
itu akan memperbarui kaunter.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Seperti update kaunter, ketika selesai,
apabila ia sampai ke penghujung array,

972
00:40:56,900 --> 00:41:00,830
jika senarai tidak disusun,
kaunter akan telah dikemaskini.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Jadi kemudian ia memeriksa keadaan dan ia
berkata, OK, adalah tidak lebih besar daripada sifar.

975
00:41:07,150 --> 00:41:09,290
Jika ya, melakukannya sekali lagi.

976
00:41:09,290 --> 00:41:14,340
Anda mahu menetapkan semula supaya apabila anda
melalui, kaunter adalah sama dengan sifar.

977
00:41:14,340 --> 00:41:18,240
Jika anda pergi melalui diurutkan
array, tidak ada perubahan,

978
00:41:18,240 --> 00:41:21,355
ini gagal, dan anda
kembali senarai disusun.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Adakah ini masuk akal?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
PELAJAR: Ia mungkin dalam sedikit.

983
00:41:26,356 --> 00:41:27,147
PENGAJAR: OK.

984
00:41:27,147 --> 00:41:28,980
Jika ada apa-apa yang lain
pertanyaan yang muncul.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Ya.

987
00:41:30,680 --> 00:41:33,760
>> PELAJAR: Apa yang akan fungsi
adalah untuk menukar unsur-unsur?

988
00:41:33,760 --> 00:41:36,900
>> PENGAJAR: Oleh itu, kita sebenarnya boleh menulis
bahawa jika kita akan ke kanan sekarang.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Sejuk.

991
00:41:38,300 --> 00:41:42,155
Maka pada masa yang sama, Alison akan
untuk beralih kembali ke perkakas.

992
00:41:42,155 --> 00:41:43,080
Ia akan menjadi seronok.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
Dan kita mempunyai baik kami
hal semacam gelembung sini.

995
00:41:47,390 --> 00:41:50,800
Jadi saya sudah melakukan berbasikal
melalui array.

996
00:41:50,800 --> 00:41:53,030
Kami mempunyai swap kami bahawa
adalah sama dengan sifar.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Oleh itu, kita ingin menukar berdekatan
elemen jika mereka rusak.

999
00:41:58,440 --> 00:42:03,020
Jadi perkara pertama yang kita perlu
lakukan adalah beralih melalui array kita.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Jadi bagaimana anda rasa kami mungkin
beralih melalui array kita?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Kami ada untuk dan saya sama dengan 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Kami mahu saya menjadi kurang
dari n tolak 1 tolak k.

1006
00:42:22,454 --> 00:42:23,870
Dan saya akan menjelaskan bahawa dalam satu saat.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Jadi, ini adalah pengoptimuman di sini di mana,
ingat bagaimana saya berkata selepas setiap lulus

1009
00:42:32,830 --> 00:42:36,655
melalui kita array
tahu bahawa apa pun yang on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Jadi, selepas satu lulus kami
tahu bahawa ini disusun.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Selepas dua pas kita tahu
bahawa semua ini disusun.

1014
00:42:50,060 --> 00:42:52,750
Selepas tiga penerbangan yang kita
tahu yang disusun.

1015
00:42:52,750 --> 00:42:55,620
Jadi cara yang saya iterasi
melalui array di sini,

1016
00:42:55,620 --> 00:43:01,090
adalah ia memastikan hanya pergi
melalui apa yang kita tahu adalah tidak dipisahkan.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
Itu hanya pengoptimuman.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Anda boleh menulis secara naif hanya
iterasi melalui segala-galanya,

1021
00:43:08,210 --> 00:43:09,970
ia hanya akan mengambil masa yang lama.

1022
00:43:09,970 --> 00:43:12,470
Dengan gelung empat itu
hanya pengoptimuman baik

1023
00:43:12,470 --> 00:43:18,460
kerana kita tahu bahawa selepas setiap penuh
lelaran melalui array di sini,

1024
00:43:18,460 --> 00:43:24,050
seperti setiap gelung penuh di sini, kita tahu
yang satu lagi elemen-elemen ini

1025
00:43:24,050 --> 00:43:25,760
akan disusun di akhir.

1026
00:43:25,760 --> 00:43:28,294
>> Oleh itu, kita tidak perlu bimbang tentang mereka.

1027
00:43:28,294 --> 00:43:29,710
Adakah ini masuk akal untuk semua orang?

1028
00:43:29,710 --> 00:43:30,950
Itu helah sedikit sejuk?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
Jadi, dalam hal ini, jika
kami iterasi melalui,

1031
00:43:37,270 --> 00:43:50,590
kita tahu bahawa yang kita inginkan untuk memeriksa jika
pelbagai n dan n ditambah 1 adalah teratur.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Jadi, inilah pseudocode.

1035
00:43:54,600 --> 00:43:57,540
Kami ingin memeriksa jika array n
dan n ditambah 1 adalah teratur.

1036
00:43:57,540 --> 00:43:59,520
Jadi apa yang kita ada di sana?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
Ia akan menjadi beberapa bersyarat.

1039
00:44:03,120 --> 00:44:04,220
Ini akan menjadi jika.

1040
00:44:04,220 --> 00:44:07,066
>> PELAJAR: Jika array n adalah
kurang daripada pelbagai n campur 1.

1041
00:44:07,066 --> 00:44:07,816
PENGAJAR: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Nah, kurang daripada atau lebih besar dari.

1044
00:44:10,699 --> 00:44:11,615
PELAJAR: Lebih besar dari.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Kemudian kita ingin menukar mereka.

1047
00:44:17,620 --> 00:44:18,570
Tepat.

1048
00:44:18,570 --> 00:44:23,570
Jadi sekarang kita masuk ke dalam apa
mekanisme untuk menukar mereka?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Oleh itu, kita telah melalui secara ringkas ini,
sejenis fungsi swap minggu lepas.

1051
00:44:28,137 --> 00:44:29,595
Apakah ada yang masih ingat bagaimana ia bekerja?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Oleh itu, kita tidak boleh hanya menetapkan kembali mereka, kan?

1054
00:44:34,950 --> 00:44:36,640
Oleh kerana salah seorang daripada mereka akan hilang.

1055
00:44:36,640 --> 00:44:41,696
Jika kita mengatakan A sama dengan B, kemudian B
adalah sama dengan A, semua tiba-tiba kedua-dua mereka

1056
00:44:41,696 --> 00:44:43,150
hanya sama dengan B.

1057
00:44:43,150 --> 00:44:45,720
>> Jadi apa yang harus kita lakukan adalah kita
mempunyai variabel sementara itu

1058
00:44:45,720 --> 00:44:49,055
akan memegang salah satu dari sementara kita
kami dalam proses menukar.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Jadi apa yang kita ada adalah kita akan mempunyai beberapa int
suhu adalah sama supaya- anda boleh menetapkan

1061
00:44:56,464 --> 00:44:59,130
kepada mana-mana satu yang anda mahu, hanya
pastikan anda menjejaki itu--

1062
00:44:59,130 --> 00:45:01,840
sehingga dalam hal ini, saya akan
menetapkan ke pelbagai n campur 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Jadi itu akan memegang apa sahaja
nilai adalah dalam blok kedua

1065
00:45:07,674 --> 00:45:08,590
bahawa kita sedang melihat.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> Dan kemudian kita boleh lakukan ialah kita boleh pergi
ke depan dan pelbagai menyerahhakkan semula n campur 1,

1068
00:45:13,240 --> 00:45:14,990
kerana kita tahu bahawa kita
mempunyai nilai yang disimpan.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Ini juga salah satu besar
things-- Saya tidak tahu sesiapa di antara kamu

1071
00:45:19,270 --> 00:45:23,780
mempunyai isu-isu di mana jika anda menghidupkan dua
baris kod tiba-tiba perkara yang bekerja.

1072
00:45:23,780 --> 00:45:25,880
Perintah ini sangat penting dalam CS.

1073
00:45:25,880 --> 00:45:29,450
Jadi, pastikan anda diagram
hal-hal jika boleh

1074
00:45:29,450 --> 00:45:31,230
mengenai apa yang sebenarnya berlaku.

1075
00:45:31,230 --> 00:45:34,256
Jadi sekarang kita akan
menetapkan kembali pelbagai n campur 1,

1076
00:45:34,256 --> 00:45:36,005
kerana kita tahu bahawa kita
mempunyai nilai yang disimpan.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> Dan kita boleh menetapkan bahwa untuk pelbagai
n atau dalam hal ini pelbagai i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Terlalu banyak pembolehubah.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Pelbagai Jadi sekarang kita telah ditugaskan semula i
ditambah 1 untuk sama apa yang ada di pelbagai i.

1084
00:46:01,500 --> 00:46:08,240
Dan sekarang kita boleh kembali dan
menetapkan pelbagai saya untuk apa?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Sesiapa sahaja?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> PELAJAR: 10.

1089
00:46:14,010 --> 00:46:14,680
>> PENGAJAR: 10.

1090
00:46:14,680 --> 00:46:15,180
Tepat.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
Dan satu hal.

1093
00:46:18,640 --> 00:46:21,840
Jika kita telah bertukar sekarang,
apa yang kita perlu buat?

1094
00:46:21,840 --> 00:46:23,740
Apakah perkara yang salah
perkara yang berlaku untuk memberitahu kita

1095
00:46:23,740 --> 00:46:27,542
jika kita pernah menamatkan program ini?

1096
00:46:27,542 --> 00:46:29,250
Apa yang memberitahu kita bahawa kita
mempunyai senarai yang disusun?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Jika kita tidak melakukan apa-apa pertukaran, kan?

1099
00:46:33,750 --> 00:46:36,900
Jika pertukaran adalah sama dengan
sifar pada akhir ini.

1100
00:46:36,900 --> 00:46:42,975
Jadi, setiap kali anda melakukan pertukaran, seperti yang kita
hanya lakukan di sini, kita mahu untuk mengemaskini swap.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
Dan saya tahu ada
pertanyaan sebelumnya tentang boleh anda

1103
00:46:47,210 --> 00:46:49,689
menggunakan sifar atau salah satu daripada
dari benar atau salah.

1104
00:46:49,689 --> 00:46:50,980
Dan itulah apa yang dilakukan di sini.

1105
00:46:50,980 --> 00:46:52,750
Jadi ini mengatakan, jika tak swap.

1106
00:46:52,750 --> 00:47:01,310
Jadi jika swap adalah sifar, yang is-- saya selalu
mendapatkan kebenaran saya dan kesalahan-kesalahan saya bercampur.

1107
00:47:01,310 --> 00:47:03,960
Kami mahu kita menilai
kepada benar dan ia bukan.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Jadi, jika itu sifar, maka itu salah.

1110
00:47:09,630 --> 00:47:12,560
Jika anda menafikan ia dengan
[? bang?] ia menjadi kenyataan.

1111
00:47:12,560 --> 00:47:13,975
Demikian maka baris ini dijalankan.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Kebenaran dan yang salah dan
sifar dan orang-orang gila.

1114
00:47:17,370 --> 00:47:20,690
Hanya jika anda perlahan-lahan berjalan
melaluinya ia akan masuk akal.

1115
00:47:20,690 --> 00:47:23,320
Tapi itulah yang kecil ini
sedikit kod di sini tidak.

1116
00:47:23,320 --> 00:47:26,490
Jadi ini memeriksa untuk melihat
yang telah kita lakukan apa-apa swap.

1117
00:47:26,490 --> 00:47:30,054
Jadi, jika itu apa-apa selain
sifar, ia akan menjadi palsu

1118
00:47:30,054 --> 00:47:31,970
dan perkara ini adalah
akan melaksanakan lagi.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Cool?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> PELAJAR: Apa istirahat lakukan?

1123
00:47:36,000 --> 00:47:38,990
>> PENGAJAR: Break hanya
memecahkan kamu dari gelung.

1124
00:47:38,990 --> 00:47:41,570
Jadi dalam hal ini ia akan
hanya suka mengakhiri program

1125
00:47:41,570 --> 00:47:43,828
dan anda akan hanya
mempunyai senarai disusun anda.

1126
00:47:43,828 --> 00:47:44,536
PELAJAR: Amazing.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
PENGAJAR: Saya minta maaf?

1129
00:47:49,010 --> 00:47:52,110
PELAJAR: Oleh kerana sebelum ini kita
digunakan bertulis 1 lebih ditulis nol

1130
00:47:52,110 --> 00:47:54,170
membentangkan bahawa jika
yang akan bekerja atau tidak.

1131
00:47:54,170 --> 00:47:54,878
>> PENGAJAR: Ya.

1132
00:47:54,878 --> 00:47:56,410
Jadi, anda boleh kembali sifar atau 1.

1133
00:47:56,410 --> 00:47:58,950
Dalam kes ini, kerana kita tidak benar-benar
melakukan apa-apa dengan fungsi tersebut,

1134
00:47:58,950 --> 00:48:00,150
kami hanya mahu ia untuk memecahkan.

1135
00:48:00,150 --> 00:48:02,680
Kami tidak benar-benar mengambil berat tentang hal itu.

1136
00:48:02,680 --> 00:48:06,960
Brek juga baik jika
ia digunakan untuk melanggar

1137
00:48:06,960 --> 00:48:10,710
empat gelung atau syarat-syarat yang
Anda tidak mahu untuk menjaga melaksanakan.

1138
00:48:10,710 --> 00:48:12,110
Ia hanya akan membawa anda keluar dari mereka.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Ini adalah sedikit hal nuansa.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Aku merasa seperti ada
banyak melambaikan tangan,

1143
00:48:18,445 --> 00:48:19,740
seperti anda akan belajar tentang perkara ini tidak lama lagi.

1144
00:48:19,740 --> 00:48:20,955
>> Tetapi anda akan belajar tentang perkara ini tidak lama lagi.

1145
00:48:20,955 --> 00:48:21,500
Aku janji.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Jadi tidak semua orang mendapatkan semacam gelembung?

1149
00:48:24,840 --> 00:48:25,550
Tidak terlalu buruk.

1150
00:48:25,550 --> 00:48:31,910
Beralih melalui, hal-hal swap menggunakan
suhu berubah-ubah, dan kami sudah siap di sana?

1151
00:48:31,910 --> 00:48:32,960
Sejuk.

1152
00:48:32,960 --> 00:48:34,080
Awesome.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Kembali ke PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Apa-apa soalan secara umum
mengenai setakat ini?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Sejuk.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> PELAJAR: [didengar] int utama biasanya.

1162
00:48:45,279 --> 00:48:46,695
Adakah anda perlu mempunyai bahawa untuk ini?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> PENGAJAR: Oleh itu, kita hanya mencari
hanya pada algoritma sorting sebenar.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Jika anda mempunyai ia dalam
seperti program yang lebih besar,

1167
00:48:56,350 --> 00:48:57,891
Anda akan memiliki tempat utama int.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
Bergantung kepada di mana anda
menggunakan algoritma ini,

1170
00:49:02,880 --> 00:49:05,860
ia akan menentukan apa yang
dipulangkan olehnya.

1171
00:49:05,860 --> 00:49:09,960
Tetapi bagi kes kami, kami tidak ketat
melihat bagaimana ini sebenarnya

1172
00:49:09,960 --> 00:49:11,300
beralih melalui array.

1173
00:49:11,300 --> 00:49:12,570
Oleh itu, kita tidak bimbang tentang hal itu.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Jadi kita bercakap tentang hal terbaik dan
senario kes terburuk untuk carian binari.

1176
00:49:19,830 --> 00:49:22,470
Jadi ia juga penting untuk dilakukan
bahwa untuk setiap macam kami.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Jadi apa yang anda fikir adalah yang paling teruk
kes runtime semacam gelembung?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Anda semua masih ingat?

1181
00:49:30,700 --> 00:49:31,784
>> PELAJAR: N tolak 1.

1182
00:49:31,784 --> 00:49:32,700
PENGAJAR: Tiada tolak 1.

1183
00:49:32,700 --> 00:49:35,070
Ini bermakna terdapat
n tolak 1 perbandingan.

1184
00:49:35,070 --> 00:49:40,060
Jadi, satu perkara yang perlu sedar ialah
bahawa pada lelaran pertama,

1185
00:49:40,060 --> 00:49:43,360
kita pergi melalui, kita bandingkan
ini two-- jadi itu 1.

1186
00:49:43,360 --> 00:49:46,685
Kedua-dua, tiga, empat.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Jadi selepas satu lelaran kami
sudah mempunyai empat perbandingan.

1189
00:49:55,050 --> 00:49:58,230
Apabila saya bercakap tentang masa jalanan dan n.

1190
00:49:58,230 --> 00:50:04,680
N mewakili bilangan perbandingan
sebagai fungsi dari berapa banyak elemen

1191
00:50:04,680 --> 00:50:05,570
kita ada.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Oleh itu, kita pergi melalui, kami mempunyai empat.

1194
00:50:08,860 --> 00:50:11,780
Masa seterusnya yang anda tahu kita tidak melakukan
harus mengurus ini.

1195
00:50:11,780 --> 00:50:15,140
Kita bandingkan kedua-dua,
kedua-dua, kedua-dua,

1196
00:50:15,140 --> 00:50:20,050
dan jika kita tidak mempunyai pengoptimuman yang
dengan gelung empat yang saya tulis,

1197
00:50:20,050 --> 00:50:22,750
Anda akan membandingkan di sini anyways.

1198
00:50:22,750 --> 00:50:26,170
Jadi, anda perlu
dijalankan melalui array

1199
00:50:26,170 --> 00:50:34,380
dan membuat perbandingan n n
kali, kerana setiap kali kita

1200
00:50:34,380 --> 00:50:36,670
dijalankan melalui itu kita semacam satu perkara.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> Dan setiap kali kami berjalan melalui
array, kita buat n perbandingan.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Jadi runtime kami untuk ini adalah
sebenarnya n kuasa dua, yang

1205
00:50:46,330 --> 00:50:48,400
jauh lebih buruk kita
log akhir kerana itu

1206
00:50:48,400 --> 00:50:51,965
ertinya jika kita mempunyai empat
bilion elemen, itu

1207
00:50:51,965 --> 00:50:55,260
akan membawa kita empat bilion
kuasa dua bukan 32.

1208
00:50:55,260 --> 00:51:01,240
Jadi tidak runtime yang terbaik,
tetapi untuk beberapa hal,

1209
00:51:01,240 --> 00:51:04,610
Anda tahu, jika anda dalam
jarak tertentu dari unsur-unsur

1210
00:51:04,610 --> 00:51:06,540
semacam gelembung mungkin baik untuk digunakan.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Jadi sekarang apa yang mana-mana yang terbaik runtime?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
PELAJAR: Zero?

1215
00:51:14,940 --> 00:51:16,420
Atau 1?

1216
00:51:16,420 --> 00:51:18,140
>> PENGAJAR: Jadi 1 akan
menjadi salah satu perbandingan.

1217
00:51:18,140 --> 00:51:19,114
Betul.

1218
00:51:19,114 --> 00:51:20,002
>> PELAJAR: N tolak 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> PENGAJAR: Jadi, ya.

1221
00:51:22,320 --> 00:51:22,990
Jadi n tolak 1.

1222
00:51:22,990 --> 00:51:26,510
Setiap kali anda mempunyai konsep seperti n
tolak 1, kita cenderung untuk hanya menjatuhkannya

1223
00:51:26,510 --> 00:51:31,680
dan kami hanya mengatakan n kerana anda mempunyai
untuk membandingkan setiap these-- setiap pasangan.

1224
00:51:31,680 --> 00:51:36,470
Jadi ia akan menjadi n tolak 1, yang kita
kita hanya akan mengatakan adalah lebih kurang n.

1225
00:51:36,470 --> 00:51:39,280
Ketika anda sedang berhadapan dengan runtime,
semuanya dalam lebih kurang.

1226
00:51:39,280 --> 00:51:43,860
Selama eksponen adalah
betul, kau cukup baik.

1227
00:51:43,860 --> 00:51:45,700
>> Itulah cara kita menghadapinya.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Supaya mana-mana yang terbaik adalah n, yang
bermakna bahawa senarai itu sudah disusun,

1230
00:51:51,780 --> 00:51:54,320
dan semua yang kita lakukan adalah menjalankan melalui
dan pastikan ia disusun.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Sejuk.

1233
00:51:56,855 --> 00:51:57,355
Baik.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Jadi seperti yang anda lihat di sini, kita
hanya mempunyai beberapa lebih grafik.

1236
00:52:01,920 --> 00:52:02,660
Jadi n kuasa dua.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Fun.

1239
00:52:05,120 --> 00:52:09,730
Jauh lebih buruk daripada n seperti yang kita lihat, dan
jauh, jauh lebih buruk daripada log 2n.

1240
00:52:09,730 --> 00:52:12,060
Dan kemudian anda juga masuk ke dalam log log.

1241
00:52:12,060 --> 00:52:18,020
Dan anda mengambil 124, anda masuk ke dalam
seperti bintang log, yang seperti gila.

1242
00:52:18,020 --> 00:52:20,172
Jadi, jika anda berminat,
bintang log pencarian.

1243
00:52:20,172 --> 00:52:20,880
Ia adalah jenis yang menyeronokkan.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Jadi kita mempunyai grafik yang hebat ini.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Hanya kepala naik, ini
grafik yang indah untuk mempunyai

1248
00:52:28,720 --> 00:52:31,350
selama tempoh pertengahan anda kerana kami
lama untuk meminta anda menipis ini.

1249
00:52:31,350 --> 00:52:36,090
Jadi hanya kepala, memiliki ini pada anda
jangka menengah pada contekan baik anda

1250
00:52:36,090 --> 00:52:36,616
ada.

1251
00:52:36,616 --> 00:52:37,990
Oleh itu, kita hanya melihat semacam gelembung.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Kes terburuk, n kuasa dua, kes terbaik, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
Dan kita akan melihat yang lain.

1256
00:52:44,950 --> 00:52:47,940
>> Dan seperti yang anda boleh lihat, satu-satunya
salah satu yang benar-benar baik

1257
00:52:47,940 --> 00:52:50,910
adalah gabungan semacam, yang kita akan masuk ke mengapa.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Jadi, kita akan pergi ke
satu jenis pilihan di sini-depan.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Apakah ada yang masih ingat bagaimana
pemilihan jenis bekerja?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Pergi untuk itu.

1264
00:53:05,700 --> 00:53:08,210
>> PELAJAR: Pada dasarnya melalui
pesanan dan membuat senarai baru.

1265
00:53:08,210 --> 00:53:11,001
Dan seperti yang anda meletakkan unsur-unsur
dalam, meletakkan mereka di tempat yang betul

1266
00:53:11,001 --> 00:53:11,750
dalam senarai baru.

1267
00:53:11,750 --> 00:53:14,040
>> PENGAJAR: Supaya suara
lebih seperti jenis sisipan.

1268
00:53:14,040 --> 00:53:15,040
Tetapi anda benar-benar dekat.

1269
00:53:15,040 --> 00:53:15,915
Mereka sangat mirip.

1270
00:53:15,915 --> 00:53:17,440
Walaupun saya dicampuradukkan kadang-kadang.

1271
00:53:17,440 --> 00:53:18,981
Sebelum seksyen ini aku seperti, menunggu.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Jadi apa yang anda mahu
lakukan adalah jenis pemilihan,

1275
00:53:24,141 --> 00:53:25,890
cara yang anda boleh berfikir
mengenainya dan cara

1276
00:53:25,890 --> 00:53:30,140
Saya memastikan saya tidak cuba untuk mendapatkan
dicampuradukkan, adakah ia akan melalui

1277
00:53:30,140 --> 00:53:33,280
dan ia memilih
jumlah yang paling kecil dan ia

1278
00:53:33,280 --> 00:53:36,070
meletakkan bahawa pada awal senarai anda.

1279
00:53:36,070 --> 00:53:37,730
Ia menukar dengan yang tempat pertama.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Mereka benar-benar mempunyai satu contoh untuk saya.

1282
00:53:45,370 --> 00:53:46,540
Awesome.

1283
00:53:46,540 --> 00:53:50,130
Jadi hanya satu cara untuk memikirkan pemilihan itu--
macam, pilih nilai yang paling kecil.

1284
00:53:50,130 --> 00:53:51,940
Dan kita akan
dijalankan melalui contoh

1285
00:53:51,940 --> 00:53:55,320
yang saya fikir akan membantu kerana
Saya rasa visual sentiasa membantu.

1286
00:53:55,320 --> 00:53:58,510
Oleh itu, kita bermula dengan sesuatu yang
yang benar-benar tidak dipisahkan.

1287
00:53:58,510 --> 00:54:00,730
Merah akan menjadi tidak dipisahkan,
hijau akan diurutkan.

1288
00:54:00,730 --> 00:54:02,190
Semuanya akan masuk akal di saat.

1289
00:54:02,190 --> 00:54:08,950
>> Oleh itu, kita melalui dan kita beralih
dari awal hingga akhir.

1290
00:54:08,950 --> 00:54:12,320
Dan kita berkata, OK, 2 adalah
jumlah yang paling kecil kami.

1291
00:54:12,320 --> 00:54:15,680
Jadi, kita akan mengambil 2 dan kita akan
untuk memindahkannya ke hadapan array kita

1292
00:54:15,680 --> 00:54:17,734
kerana itu adalah
jumlah paling kecil yang kita ada.

1293
00:54:17,734 --> 00:54:19,150
Jadi itulah yang ini lakukan di sini.

1294
00:54:19,150 --> 00:54:20,820
Ini hanya akan menukar dua.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Jadi sekarang kita telah yang disusun
bahagian dan satu bahagian yang tidak dipisahkan.

1297
00:54:25,450 --> 00:54:27,810
Dan apa yang baik untuk diingat
mengenai jenis pilihan

1298
00:54:27,810 --> 00:54:30,690
adalah kita hanya memilih
dari bahagian yang tidak dipisahkan.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Bahagian yang diurutkan anda biarkan.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> PELAJAR: Bagaimana ia tahu apa yang
yang paling kecil tanpa membandingkannya

1303
00:54:38,452 --> 00:54:39,868
untuk setiap nilai lain dalam array.

1304
00:54:39,868 --> 00:54:41,250
PENGAJAR: Itu membandingkannya.

1305
00:54:41,250 --> 00:54:42,041
Kami suka melewatkan itu.

1306
00:54:42,041 --> 00:54:43,850
Ini hanyalah umum secara keseluruhan.

1307
00:54:43,850 --> 00:54:44,831
Yeah.

1308
00:54:44,831 --> 00:54:47,205
Apabila kita menulis kod saya
pasti anda akan lebih berpuas hati.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Tetapi anda menyimpan ini pertama
sebagai unsur yang paling kecil.

1311
00:54:53,030 --> 00:54:56,110
Anda membandingkan dan anda
berkata, OK, adalah lebih kecil?

1312
00:54:56,110 --> 00:54:56,660
Ya.

1313
00:54:56,660 --> 00:54:57,460
Menyimpannya.

1314
00:54:57,460 --> 00:54:58,640
Di sini adalah lebih kecil?

1315
00:54:58,640 --> 00:54:59,660
Tidak?

1316
00:54:59,660 --> 00:55:02,510
>> Ini adalah yang paling kecil anda,
menetapkan kembali ke nilai anda.

1317
00:55:02,510 --> 00:55:06,340
Dan anda akan lebih gembira
apabila kita melalui kod.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Oleh itu, kita pergi melalui, kita tukar, jadi kemudian
kita melihat bahagian yang tidak dipisahkan ini.

1320
00:55:13,970 --> 00:55:15,810
Jadi, kita akan memilih tiga daripada.

1321
00:55:15,810 --> 00:55:18,890
Kami akan meletakkannya di di
akhir bahagian diurutkan kami.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
Dan kita hanya akan terus melakukan
itu, melakukan hal itu, dan melakukan hal itu.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Jadi, ini adalah semacam kami pseudo di sini.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Kami akan memberi kod itu di sini dalam satu saat.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Tetapi hanya sesuatu untuk berjalan
melalui pada tahap yang tinggi.

1330
00:55:37,270 --> 00:55:40,275
Anda akan pergi daripada
i sama dengan 0 ke n tolak 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
Itu pengoptimuman lain.

1333
00:55:43,530 --> 00:55:45,020
Jangan bimbang terlalu banyak tentang hal itu.

1334
00:55:45,020 --> 00:55:46,620
Jadi seperti yang anda katakan.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Sebagai Yakub berkata, bagaimana kita
menjejaki apa yang minimum kami adalah?

1337
00:55:54,406 --> 00:55:55,030
Bagaimana kita tahu?

1338
00:55:55,030 --> 00:55:57,060
Kami perlu membandingkan
segala-galanya dalam senarai kami.

1339
00:55:57,060 --> 00:55:59,600
>> Jadi sekurang-kurangnya sama dengan saya.

1340
00:55:59,600 --> 00:56:03,870
Ia hanya mengatakan dalam hal ini
indeks nilai minimum kami.

1341
00:56:03,870 --> 00:56:07,660
Demikian maka ia akan beralih melalui
dan pergi dari j sama i ditambah 1.

1342
00:56:07,660 --> 00:56:11,420
Oleh itu, kita sudah tahu bahawa
itulah elemen pertama kami.

1343
00:56:11,420 --> 00:56:13,240
Kita tidak perlu untuk membandingkannya dengan sendiri.

1344
00:56:13,240 --> 00:56:16,970
Oleh itu, kita mula membandingkannya dengan yang akan datang
salah satu yang adalah mengapa ia i ditambah 1 hingga n

1345
00:56:16,970 --> 00:56:20,110
tolak 1, yang merupakan
akhir array sana.

1346
00:56:20,110 --> 00:56:25,090
Dan kita berkata jika array di
j adalah kurang dari pelbagai min,

1347
00:56:25,090 --> 00:56:29,200
maka kita menetapkan kembali di mana
indeks minimum kami adalah.

1348
00:56:29,200 --> 00:56:37,470
>> Dan jika min tidak sama dengan saya, sebagai
di mana kami kembali ke sini.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Jadi seperti ketika kita mula-mula melakukan satu ini.

1351
00:56:41,790 --> 00:56:49,310
Dalam kes ini, ia akan bermula pada
sifar, ia akan berakhir menjadi dua.

1352
00:56:49,310 --> 00:56:53,010
Jadi min tidak akan sama saya pada akhirnya.

1353
00:56:53,010 --> 00:56:55,720
Yang membolehkan kita tahu bahawa
kita perlu untuk menukar mereka.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Saya rasa seperti contoh yang konkrit
akan membantu lebih dari ini.

1356
00:57:00,470 --> 00:57:04,970
Jadi saya akan kode atas ini dengan kalian
sekarang dan saya fikir ia akan menjadi lebih baik.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Macam cenderung bekerja dengan cara itu dalam
itu sering lebih baik hanya untuk melihat mereka.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Jadi apa yang kita ingin lakukan adalah
pertama kita mahu yang paling kecil

1361
00:57:17,280 --> 00:57:19,890
elemen dalam kedudukannya dalam array.

1362
00:57:19,890 --> 00:57:21,280
Tepat apa Yakub berkata.

1363
00:57:21,280 --> 00:57:23,090
Anda perlu untuk menyimpan yang entah bagaimana.

1364
00:57:23,090 --> 00:57:25,900
Jadi kita akan bermula di sini
iterasi array.

1365
00:57:25,900 --> 00:57:28,970
Kita akan mengatakan itu kami
yang pertama hanya bermula dengan.

1366
00:57:28,970 --> 00:57:38,308
Oleh itu, kita akan mempunyai int
yang paling kecil adalah sama dengan pelbagai di i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Jadi, satu perkara yang perlu melihat, setiap
masa lingkaran ini dijalankan,

1369
00:57:45,050 --> 00:57:48,550
kita mulai satu langkah lebih jauh.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Apabila kita mula kita melihat yang satu ini.

1372
00:57:57,440 --> 00:58:00,840
Lain kali kita beralih melalui,
kita mulai pada satu ini

1373
00:58:00,840 --> 00:58:02,680
dan menetapkan nilai yang paling kecil kami.

1374
00:58:02,680 --> 00:58:10,450
Jadi ia adalah hampir sama dengan semacam gelembung
di mana kita tahu bahawa selepas satu pas,

1375
00:58:10,450 --> 00:58:11,700
elemen terakhir ini disusun.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Dengan jenis pemilihan,
itu sebaliknya.

1378
00:58:15,120 --> 00:58:18,950
>> Pada setiap pas, kita tahu bahawa
yang pertama disusun.

1379
00:58:18,950 --> 00:58:21,360
Setelah lulus kedua,
yang kedua akan diurutkan.

1380
00:58:21,360 --> 00:58:26,470
Dan seperti yang anda lihat pada contoh slaid,
bahagian disusun kami hanya terus berkembang.

1381
00:58:26,470 --> 00:58:34,020
Jadi dengan menetapkan satu yang paling kecil kami
kepada barisan saya, semua yang dilakukannya

1382
00:58:34,020 --> 00:58:37,340
adalah mengecutkan apa
kita sedang melihat supaya

1383
00:58:37,340 --> 00:58:40,164
untuk mengurangkan bilangan
perbandingan yang kita buat.

1384
00:58:40,164 --> 00:58:41,770
Adakah ini masuk akal untuk semua orang?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Adakah anda memerlukan saya untuk menjalankan melalui yang
lagi lambat atau dalam kata yang lain?

1387
00:58:46,380 --> 00:58:47,180
Saya gembira.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Jadi kita menyimpan
nilai pada masa ini,

1392
00:58:55,540 --> 00:58:57,840
tapi kami juga ingin untuk menyimpan indeks.

1393
00:58:57,840 --> 00:59:01,010
Jadi, kita akan untuk menyimpan
kedudukan yang paling kecil

1394
00:59:01,010 --> 00:59:02,770
satu, yang hanya akan menjadi i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Jadi sekarang Yakub berpuas hati.

1397
00:59:05,440 --> 00:59:06,870
Kami memiliki hal-hal yang disimpan.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
Dan sekarang kita perlu melihat melalui
bahagian yang tidak dipisahkan dari array.

1400
00:59:11,870 --> 00:59:18,170
Jadi dalam hal ini ini
akan unsorted kami.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
Ini adalah i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Jadi apa yang kita akan lakukan
akan menjadi untuk satu lingkaran.

1406
00:59:30,040 --> 00:59:32,066
Bila-bila masa anda perlu
beralih melalui array,

1407
00:59:32,066 --> 00:59:33,440
fikiran anda boleh pergi ke untuk satu lingkaran.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Jadi untuk beberapa int k
equals-- apa yang kita berfikir

1410
00:59:38,090 --> 00:59:39,700
k akan sama untuk memulakan dengan?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
Inilah yang kita tetapkan sebagai yang paling kecil kami
nilai dan kami mahu membandingkannya.

1413
00:59:44,766 --> 00:59:47,090
Apa yang kita mahu membandingkannya dengan?

1414
00:59:47,090 --> 00:59:48,730
Ia akan menjadi salah satu yang akan datang ini, kan?

1415
00:59:48,730 --> 00:59:53,200
Oleh itu, kita mahu k yang akan dimulakan
ke i ditambah 1 untuk memulakan.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> Dan kami ingin k dalam hal ini kita
sudah saiz disimpan di sini,

1418
01:00:02,800 --> 01:00:03,930
jadi kami hanya boleh menggunakan saiz.

1419
01:00:03,930 --> 01:00:06,240
Saiz yang saiz array.

1420
01:00:06,240 --> 01:00:09,620
Dan kami hanya mahu
mengemaskini k per satu setiap kali.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Sejuk.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Jadi sekarang kita perlu mencari
unsur yang paling kecil di sini.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Jadi jika kita beralih melalui, kami
ingin mengatakan, jika array di k

1427
01:00:31,380 --> 01:00:37,080
kurang dari value-- terkecil kita
ini adalah di mana kita benar-benar

1428
01:00:37,080 --> 01:00:42,950
mencatat apa yang
sini-yang paling kecil

1429
01:00:42,950 --> 01:00:47,740
maka kita ingin menetapkan kembali
apa nilai yang paling kecil kita.

1430
01:00:47,740 --> 01:00:50,645
>> Ini bermakna, oh, kami tidak
iterasi melalui sini.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Apa sahaja nilai di sini adalah
bukan perkara yang paling kecil kami.

1433
01:00:53,740 --> 01:00:54,448
Kita tidak mahu itu.

1434
01:00:54,448 --> 01:00:56,100
Kami ingin menetapkannya semula.

1435
01:00:56,100 --> 01:01:02,050
Jadi jika kita pemindahan itu, apa yang
anda berfikir seperti di dalam kod ini di sini?

1436
01:01:02,050 --> 01:01:04,160
Kami ingin menetapkan kembali
terkecil dan kedudukan.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Jadi apa yang paling kecil ini?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
PELAJAR: Array k.

1441
01:01:09,130 --> 01:01:09,963
PENGAJAR: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
Dan apakah kedudukan ini?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Apa indeks bagi
nilai yang paling kecil kita?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
Hanya saja k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Jadi pelbagai k, k, mereka cocok.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Jadi kita ingin untuk menetapkan kembali itu.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
Dan kemudian selepas kami mendapati yang paling kecil kami,
sehingga pada akhir ini untuk gelung

1454
01:01:39,950 --> 01:01:45,100
di sini kita telah memperoleh apa yang paling kecil kami
nilai adalah, jadi kita tukar.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
Dalam kes ini, seperti mengatakan kami
nilai yang paling kecil adalah di sini.

1457
01:01:50,816 --> 01:01:51,940
Ini adalah nilai yang paling kecil kami.

1458
01:01:51,940 --> 01:01:57,690
>> Kami hanya ingin tukar di sini, yang
apa fungsi pertukaran di bahagian bawah

1459
01:01:57,690 --> 01:02:01,270
lakukan, yang kita hanya menuliskan
bersama-sama beberapa minit yang lalu.

1460
01:02:01,270 --> 01:02:02,775
Jadi ia perlu kelihatan biasa.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
Dan kemudian ia hanya akan beralih
melalui hingga mencapai semua jalan

1463
01:02:08,030 --> 01:02:13,100
hingga akhir, yang bermakna anda
mempunyai sifar unsur-unsur yang tidak dipisahkan

1464
01:02:13,100 --> 01:02:14,800
dan segala sesuatu yang lain telah disusun.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Masuk akal?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Sedikit lebih kukuh?

1469
01:02:19,280 --> 01:02:19,990
Kod ini membantu?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> PELAJAR: Untuk saiz, anda tidak
benar-benar menetapkan atau mengubahnya,

1472
01:02:26,410 --> 01:02:27,340
bagaimana cara mengetahui?

1473
01:02:27,340 --> 01:02:32,380
>> PENGAJAR: Jadi, satu perkara yang perlu
perhatikan di sini adalah saiz int.

1474
01:02:32,380 --> 01:02:35,680
Oleh itu, kita katakan dalam jenis sort-- ini
adalah fungsi dalam case-- itu

1475
01:02:35,680 --> 01:02:40,770
jenis pilihan, ia berlalu
masuk dengan fungsi.

1476
01:02:40,770 --> 01:02:43,460
Jadi, jika ia tidak disahkan
masuk, anda akan melakukan sesuatu

1477
01:02:43,460 --> 01:02:47,840
seperti dengan panjang array
atau anda akan beralih melalui

1478
01:02:47,840 --> 01:02:49,390
untuk mencari panjang.

1479
01:02:49,390 --> 01:02:52,680
Tetapi oleh kerana ia diluluskan
dalam, kami hanya boleh menggunakannya.

1480
01:02:52,680 --> 01:02:55,720
Anda hanya menganggap bahawa pengguna
memberikan anda saiz yang sah yang

1481
01:02:55,720 --> 01:02:57,698
sebenarnya mewakili
saiz array Anda.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Cool?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Jika anda mempunyai sebarang masalah dengan ini
atau mahu lebih banyak latihan coding macam

1486
01:03:05,870 --> 01:03:08,050
pada anda sendiri, anda perlu
pergi ke study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
Ini alat.

1489
01:03:12,670 --> 01:03:15,040
Mereka mempunyai pemeriksa yang
Anda benar-benar boleh menulis.

1490
01:03:15,040 --> 01:03:16,180
Mereka pseudokod.

1491
01:03:16,180 --> 01:03:19,310
Mereka mempunyai lebih banyak video dan slaid
termasuk yang saya gunakan di sini.

1492
01:03:19,310 --> 01:03:23,150
Jadi, jika anda masih merasa
agak kabur, cuba yang keluar.

1493
01:03:23,150 --> 01:03:25,670
Seperti biasa, datang bercakap dengan saya juga.

1494
01:03:25,670 --> 01:03:26,320
Soalan?

1495
01:03:26,320 --> 01:03:28,611
>> PELAJAR: Adakah anda mengatakan yang
saiz yang sebelum ini ditakrifkan?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
PENGAJAR: Ya.

1498
01:03:29,900 --> 01:03:35,570
Saiz sebelum ini ditakrifkan sehingga
sini dalam akuan fungsi.

1499
01:03:35,570 --> 01:03:39,060
Jadi anda menganggap bahawa ia telah diluluskan pada
oleh pengguna, dan untuk mudahnya,

1500
01:03:39,060 --> 01:03:41,896
kita akan menganggap bahawa
pengguna memberi kami saiz yang betul.

1501
01:03:41,896 --> 01:03:43,240
Sejuk.

1502
01:03:43,240 --> 01:03:44,390
Jadi itulah jenis pemilihan.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Guys, saya tahu kita belajar banyak hari ini.

1505
01:03:47,640 --> 01:03:49,710
Ini adalah data yang padat untuk bahagian.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Maka dengan itu, kita akan
untuk pergi ke jenis sisipan.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Jadi sebelum itu kami perlu lakukan
analisis runtime kami di sini.

1511
01:04:06,100 --> 01:04:10,190
Jadi dalam kes ini,
diberikan kerana saya menunjukkan anda

1512
01:04:10,190 --> 01:04:11,960
jadual saya sudah
jenis beri tahu.

1513
01:04:11,960 --> 01:04:15,430
Tetapi kes terbaik runtime, apa yang kita fikir?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Semuanya disusun.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N kuasa dua.

1518
01:04:22,070 --> 01:04:24,780
Ada yang punya penjelasan
mengapa anda berfikir?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> PELAJAR: Anda membandingkan through--

1521
01:04:30,519 --> 01:04:31,268
PENGAJAR: Benar.

1522
01:04:31,268 --> 01:04:32,540
Anda membandingkan melalui.

1523
01:04:32,540 --> 01:04:35,630
Pada setiap lelaran, walaupun
kami decrementing ini dengan satu,

1524
01:04:35,630 --> 01:04:38,950
Anda masih mencari melalui
segala-galanya untuk mencari satu yang paling kecil.

1525
01:04:38,950 --> 01:04:42,390
Jadi, walaupun nilai yang paling kecil anda
di sini di awal,

1526
01:04:42,390 --> 01:04:44,710
Anda masih membandingkannya
terhadap segala sesuatu yang lain

1527
01:04:44,710 --> 01:04:46,550
memastikan ia adalah perkara yang paling kecil.

1528
01:04:46,550 --> 01:04:49,820
Jadi, anda akan berakhir dengan berjalan melalui
kira-kira n kali kuasa dua.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Baik.

1531
01:04:51,590 --> 01:04:52,785
Dan apa yang mana-mana yang paling teruk?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Juga n kuasa dua kerana anda akan
yang akan melakukan prosedur yang sama.

1534
01:04:57,980 --> 01:05:01,670
Jadi dalam hal ini, pemilihan
semacam sesuatu

1535
01:05:01,670 --> 01:05:04,010
bahawa kami juga menyeru runtime yang diharapkan.

1536
01:05:04,010 --> 01:05:07,400
Jadi pada orang lain, kita hanya tahu
batas-batas bawah dan atas.

1537
01:05:07,400 --> 01:05:11,180
Bergantung kepada bagaimana kita gila
daftar atau bagaimana unsorted itu,

1538
01:05:11,180 --> 01:05:15,350
mereka berbeza-beza antara n atau n kuasa dua.

1539
01:05:15,350 --> 01:05:16,550
Kita tidak tahu.

1540
01:05:16,550 --> 01:05:22,820
>> Tetapi oleh kerana jenis pemilihan mempunyai yang sama
paling teruk dan kes terbaik, yang memberitahu kita bahawa

1541
01:05:22,820 --> 01:05:25,880
tidak kira jenis input apa yang kita
mempunyai, sama ada ia benar-benar

1542
01:05:25,880 --> 01:05:29,130
disusun atau benar-benar
membalikkan disusun, itu

1543
01:05:29,130 --> 01:05:30,740
akan mengambil jumlah yang sama.

1544
01:05:30,740 --> 01:05:33,760
Jadi dalam hal ini, jika anda
ingat dari meja kami,

1545
01:05:33,760 --> 01:05:38,610
ia sebenarnya mempunyai nilai yang
kedua-dua macam tidak punya,

1546
01:05:38,610 --> 01:05:40,390
yang runtime diharapkan.

1547
01:05:40,390 --> 01:05:43,350
Jadi kita tahu bahawa setiap kali
kami menjalankan jenis pemilihan,

1548
01:05:43,350 --> 01:05:45,380
itu dijamin
menjalankan kuasa dua n masa yang.

1549
01:05:45,380 --> 01:05:46,630
Tidak ada kebolehubahan di sana.

1550
01:05:46,630 --> 01:05:47,630
Hanya saja yang diharapkan.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
Dan, sekali lagi, jika anda mahu belajar
lebih, mengambil CS 124 di musim semi.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Baik.

1555
01:05:56,712 --> 01:05:57,545
Kami telah melihat yang satu ini.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Sejuk.

1558
01:05:59,030 --> 01:06:00,930
Semacam Jadi penyisipan.

1559
01:06:00,930 --> 01:06:03,330
Dan Aku mungkin akan
untuk merintis melalui ini.

1560
01:06:03,330 --> 01:06:05,440
Saya tidak akan mempunyai anda semua kode itu.

1561
01:06:05,440 --> 01:06:06,580
Kami hanya akan berjalan melaluinya.

1562
01:06:06,580 --> 01:06:10,500
Jadi semacam penyisipan adalah jenis
dari serupa dengan jenis pilihan

1563
01:06:10,500 --> 01:06:14,460
kerana kami mempunyai satu unsorted
dan disusun sebahagian daripada array.

1564
01:06:14,460 --> 01:06:20,260
>> Tetapi apa yang berbeza ialah
seperti yang kita pergi melalui satu per satu,

1565
01:06:20,260 --> 01:06:24,210
kita hanya mengambil apa jumlah
yang berikutnya dalam unsorted kami,

1566
01:06:24,210 --> 01:06:28,507
dan benar mengatasinya
ke dalam array diurutkan kami.

1567
01:06:28,507 --> 01:06:30,090
Ia akan lebih masuk akal dengan satu contoh.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Jadi semuanya bermula sebagai tidak dipisahkan,
hanya suka dengan jenis pilihan.

1570
01:06:35,430 --> 01:06:38,740
Dan kita akan menyelesaikan masalah ini di
urutan menaik seperti yang kita telah.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Maka pada kami pertama berlalu
kita mengambil nilai pertama

1573
01:06:43,340 --> 01:06:46,700
dan kita berkata, OK, anda
sekarang dalam senarai sendiri.

1574
01:06:46,700 --> 01:06:49,150
>> Kerana anda berada dalam senarai
sendiri, anda disusun.

1575
01:06:49,150 --> 01:06:52,460
Tahniah kerana menjadi
Elemen pertama dalam array ini.

1576
01:06:52,460 --> 01:06:54,800
Anda sudah menyusun semua sendiri.

1577
01:06:54,800 --> 01:06:58,900
Jadi sekarang kita telah yang disusun
dan pelbagai yang tidak dipisahkan.

1578
01:06:58,900 --> 01:07:01,760
Jadi sekarang kita mengambil pertama.

1579
01:07:01,760 --> 01:07:05,600
Apa yang berlaku antara sini
dan di sini ialah kita mengatakan,

1580
01:07:05,600 --> 01:07:08,890
OK, kita akan melihat
Nilai pertama array unsorted kami

1581
01:07:08,890 --> 01:07:13,270
dan kita akan input dalam nya
tempat yang benar dalam array diurutkan.

1582
01:07:13,270 --> 01:07:21,460
>> Jadi apa yang kita lakukan adalah kita mengambil 5 dan
kita kata, OK, 5 adalah lebih besar dari 3,

1583
01:07:21,460 --> 01:07:24,630
jadi kami hanya memasukkan dengan betul
di sebelah kanan itu.

1584
01:07:24,630 --> 01:07:25,130
Kami baik.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Jadi kami pergi ke salah satu yang akan datang.

1587
01:07:28,420 --> 01:07:29,720
Dan kita mengambil 2.

1588
01:07:29,720 --> 01:07:34,330
Kami berkata, OK, 2 kurang
dari 3, jadi kita tahu bahawa ia

1589
01:07:34,330 --> 01:07:36,220
perlu berada di
depan senarai kami sekarang.

1590
01:07:36,220 --> 01:07:41,800
Jadi apa yang kita lakukan adalah kita menolak 3 dan 5 ke bawah
dan kita bergerak 2 ke slot pertama.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Jadi kami hanya memasukkan ke
tempat yang betul yang sepatutnya.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Kemudian kami melihat kami
yang berikutnya, dan kita katakan 6.

1595
01:07:49,470 --> 01:07:53,620
OK, 6 adalah lebih besar daripada
segala-galanya dalam array diurutkan kami,

1596
01:07:53,620 --> 01:07:56,000
jadi kita tag ke akhirnya.

1597
01:07:56,000 --> 01:07:56,960
Dan kemudian kita melihat 4.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 adalah kurang dari 6, itu kurang
daripada 5 tetapi ia lebih besar dari 3.

1600
01:08:03,020 --> 01:08:06,270
Jadi kita hanya masukkan terus ke dalam
tengah di antara 3 dan 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Jadi untuk membuat yang sedikit
sedikit lebih konkrit,

1603
01:08:10,530 --> 01:08:12,280
di sini adalah jenis yang
idea dari apa yang berlaku.

1604
01:08:12,280 --> 01:08:16,430
Jadi untuk setiap unsur yang tidak dipisahkan, kami
menentukan di mana di bahagian diurutkan

1605
01:08:16,430 --> 01:08:17,090
ia adalah.

1606
01:08:17,090 --> 01:08:20,680
>> Jadi dengan mengambil kira
disusun dan tidak dipisahkan,

1607
01:08:20,680 --> 01:08:26,080
kita perlu melintasi melalui dan angka
di mana ia sesuai dalam array diurutkan.

1608
01:08:26,080 --> 01:08:31,460
Dan kita masukkannya dengan menggeser
unsur-unsur di sebelah kanan bawah.

1609
01:08:31,460 --> 01:08:34,910
Dan kemudian kita terus
iterasi melalui sehingga kita

1610
01:08:34,910 --> 01:08:39,270
mempunyai senarai yang sama sekali disusun
di mana tidak dipisahkan kini sifar

1611
01:08:39,270 --> 01:08:41,720
dan diurutkan memakan
keseluruhannya dari senarai kami.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Jadi, sekali lagi, untuk membuat sesuatu yang
lebih konkrit, kami mempunyai pseudo.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> Jadi, pada asasnya adalah untuk i
sama dengan 0 ke n tolak 1,

1616
01:08:52,410 --> 01:08:54,790
itu hanya panjang array kami.

1617
01:08:54,790 --> 01:09:00,979
Kami mempunyai beberapa elemen yang sama dengan
array pertama atau indeks pertama.

1618
01:09:00,979 --> 01:09:03,200
Kami menetapkan j sama dengan itu.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Oleh itu, sambil j adalah lebih besar daripada
sifar dan array, j tolak 1

1621
01:09:09,210 --> 01:09:11,660
adalah lebih besar daripada
elemen, sehingga semua yang melakukan

1622
01:09:11,660 --> 01:09:17,479
adalah memastikan bahawa
j anda benar-benar mewakili

1623
01:09:17,479 --> 01:09:20,010
bahagian yang tidak dipisahkan dari array.

1624
01:09:20,010 --> 01:09:30,745
>> Jadi sementara masih ada perkara-perkara
untuk menyusun dan j minus one is-- apa

1625
01:09:30,745 --> 01:09:31,840
adalah elemen yang dia?

1626
01:09:31,840 --> 01:09:34,760
J tidak pernah ditakrifkan di sini.

1627
01:09:34,760 --> 01:09:35,677
Ini semacam menjengkelkan.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Anyways.

1630
01:09:36,689 --> 01:09:39,899
Jadi j tolak 1, anda sedang menyemak
elemen sebelumnya.

1631
01:09:39,899 --> 01:09:46,460
Anda katakan, OK, adalah elemen yang
sebelum di mana sahaja aku am-- mari kita

1632
01:09:46,460 --> 01:09:47,540
benar-benar menarik ini.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Jadi, bila ini
seperti di celah kedua kami.

1635
01:09:56,830 --> 01:09:59,525
Jadi saya akan menjadi sama
1, yang ada di sini.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> Jadi saya akan menjadi sama dengan 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
Ini akan menjadi 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Baik.

1642
01:10:16,750 --> 01:10:20,945
Jadi elemen kami dalam hal ini
akan menjadi sama dengan 4.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
Dan kami mempunyai beberapa j itu
akan menjadi sama dengan 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Oh, j decrementing.

1647
01:10:30,971 --> 01:10:31,720
Itulah apa yang ada.

1648
01:10:31,720 --> 01:10:35,680
Jadi j sama dengan saya, jadi apa ini
katakan adalah bahawa seperti yang kita bergerak ke hadapan,

1649
01:10:35,680 --> 01:10:37,530
kami hanya memastikan
bahawa kita tidak lebih

1650
01:10:37,530 --> 01:10:43,520
mengindeks cara ini apabila kita cuba
memasukkan sesuatu ke dalam senarai disusun kami.

1651
01:10:43,520 --> 01:10:49,850
>> Oleh itu, apabila j sama dengan 1 dalam kes ini dan
pelbagai j tolak satu-- sehingga pelbagai j tolak 1

1652
01:10:49,850 --> 01:10:54,610
adalah 2 dalam case-- ini jika itu
lebih besar daripada elemen,

1653
01:10:54,610 --> 01:10:57,700
maka semua ini adalah melakukan
beralih segalanya.

1654
01:10:57,700 --> 01:11:04,790
Jadi dalam hal ini, pelbagai j minus one
akan pelbagai sifar, yang 2.

1655
01:11:04,790 --> 01:11:08,430
2 tidak lebih besar dari 4,
jadi ini tidak melaksanakan.

1656
01:11:08,430 --> 01:11:11,460
Jadi peralihan tidak bergerak ke bawah.

1657
01:11:11,460 --> 01:11:18,790
Apa yang dilakukan di sini adalah hanya
bergerak array diurutkan anda ke bawah.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
Dalam kes ini, sebenarnya, kita
boleh do-- mari kita membuat 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Jadi jika kita berjalan melalui dengan
contoh ini, kita sekarang di sini.

1662
01:11:31,970 --> 01:11:32,740
Ini disusun.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
Ini adalah tidak dipisahkan.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Cool?

1667
01:11:39,860 --> 01:11:46,620
Jadi saya adalah sama dengan 2, jadi
unsur kita adalah sama dengan 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
Dan j kami adalah sama dengan 2.

1670
01:11:52,270 --> 01:12:00,620
Oleh itu, kita melihat melalui dan kami
berkata, OK, adalah pelbagai j minus one

1671
01:12:00,620 --> 01:12:03,470
lebih besar daripada unsur
yang kita lihat?

1672
01:12:03,470 --> 01:12:05,540
Dan jawapannya adalah ya, bukan?

1673
01:12:05,540 --> 01:12:11,275
4 adalah lebih besar dari 3 dan j
adalah 2, sehingga kod ini dijalankan.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Jadi sekarang apa yang kami lakukan array di
2, jadi di sini, kita menukar mereka.

1676
01:12:18,550 --> 01:12:25,620
Oleh itu, kita hanya berkata, OK, pelbagai
pada 2 kini akan menjadi 3.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
Dan j akan sama
j tolak 1, iaitu 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
Itu mengerikan, tetapi
kalian mendapat idea.

1681
01:12:37,200 --> 01:12:38,360
J kini sama dengan 1.

1682
01:12:38,360 --> 01:12:44,360
Dan pelbagai j hanya akan menjadi
sama dengan elemen kita, yang 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
Saya dipadam sesuatu yang saya tidak boleh
mempunyai atau sesuatu miswrote,

1685
01:12:48,570 --> 01:12:49,910
tapi kalian mendapat idea.

1686
01:12:49,910 --> 01:12:50,640
>> Ia bergerak pada n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
Dan kemudian jika ini, ia akan loop
sekali lagi dan ia akan berkata, OK, j adalah 1 sekarang.

1689
01:12:57,960 --> 01:13:00,665
Dan pelbagai j tolak 1 sekarang 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Adalah kurang daripada 2 elemen kita?

1692
01:13:03,760 --> 01:13:04,540
Tidak?

1693
01:13:04,540 --> 01:13:07,970
Ini bermakna bahawa kita telah
dimasukkan elemen ini

1694
01:13:07,970 --> 01:13:10,110
di tempat yang betul dalam array diurutkan kami.

1695
01:13:10,110 --> 01:13:14,400
Maka kita boleh mengambil ini dan kita berkata,
OK, array diurutkan kami ada di sini.

1696
01:13:14,400 --> 01:13:19,940
Dan ia akan mengambil nombor ini 6 dan
seperti, OK, adalah 6 kurang dari angka ini?

1697
01:13:19,940 --> 01:13:20,480
Tidak?

1698
01:13:20,480 --> 01:13:21,080
Sejuk.

1699
01:13:21,080 --> 01:13:22,680
Kami baik-baik.

1700
01:13:22,680 --> 01:13:23,530
>> Melakukannya sekali lagi.

1701
01:13:23,530 --> 01:13:24,740
Kami mengatakan 7.

1702
01:13:24,740 --> 01:13:29,010
Adalah kurang dari 7 akhir
array diurutkan kita?

1703
01:13:29,010 --> 01:13:29,520
Tidak.

1704
01:13:29,520 --> 01:13:30,430
Oleh itu, kita baik-baik saja.

1705
01:13:30,430 --> 01:13:32,760
Jadi ini akan diurutkan.

1706
01:13:32,760 --> 01:13:38,610
Pada dasarnya semua ini tidak
adalah ia mengatakan mengambil

1707
01:13:38,610 --> 01:13:42,060
unsur pertama
pelbagai unsorted anda,

1708
01:13:42,060 --> 01:13:46,010
mencari tahu di mana ia pergi
dalam array diurutkan anda.

1709
01:13:46,010 --> 01:13:48,780
Dan ini hanya mengambil penjagaan
swap untuk melakukan itu.

1710
01:13:48,780 --> 01:13:51,300
Anda pada dasarnya hanya menukar
sehingga ia di tempat yang betul.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Imej visual adalah bahawa anda
bergerak segala sesuatu ke bawah dengan melakukan itu.

1713
01:13:56,990 --> 01:13:59,420
>> Jadi seperti setengah bubble sort-esque.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Semak kajian 50.

1716
01:14:03,420 --> 01:14:06,000
Saya sangat mengesyorkan cuba
kode ini sendiri.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Jika anda mempunyai masalah atau anda mahu
lihat contoh kod untuk jenis penyisipan,

1719
01:14:12,450 --> 01:14:13,750
sila maklumkan kepada saya.

1720
01:14:13,750 --> 01:14:14,500
Saya selalu sekitar.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Jadi yang paling teruk kes runtime
dan kes terbaik runtime.

1723
01:14:20,200 --> 01:14:30,700
Seperti yang anda melihat seorang lelaki dari meja saya sudah
menunjukkan anda, ia kedua-dua kuasa dua n dan n.

1724
01:14:30,700 --> 01:14:35,590
>> Sungguh baik pergi daripada apa yang kita bercakap
mengenai dengan macam kami sebelum ini, yang paling teruk

1725
01:14:35,590 --> 01:14:38,760
kes runtime adalah bahawa jika
ia benar-benar unsorted,

1726
01:14:38,760 --> 01:14:42,530
kita perlu membandingkan semua ini n masa.

1727
01:14:42,530 --> 01:14:47,020
Kami melakukan banyak seluruh perbandingan
kerana jika ia dalam urutan terbalik,

1728
01:14:47,020 --> 01:14:50,360
kita akan berkata, OK, ini
adalah sama, ini adalah baik,

1729
01:14:50,360 --> 01:14:54,650
dan yang satu ini perlu dibandingkan
terhadap orang pertama yang dipindahkan kembali.

1730
01:14:54,650 --> 01:14:56,710
Dan seperti yang kita mendapatkan arah
hujung ekor, kita mempunyai

1731
01:14:56,710 --> 01:14:59,440
untuk membandingkan, membandingkan, dan
membandingkan terhadap segala-galanya.

1732
01:14:59,440 --> 01:15:03,030
>> Sehingga akhirnya menjadi
kira-kira n kuasa dua.

1733
01:15:03,030 --> 01:15:09,510
Jika benar maka anda
berkata, OK, 2, kau baik.

1734
01:15:09,510 --> 01:15:11,330
3, anda dibandingkan dengan 2.

1735
01:15:11,330 --> 01:15:12,310
Kau baik.

1736
01:15:12,310 --> 01:15:14,150
4, anda hanya dibandingkan dengan ekor.

1737
01:15:14,150 --> 01:15:14,990
Kau baik.

1738
01:15:14,990 --> 01:15:17,140
6, berbanding dengan ekor, anda baik-baik saja.

1739
01:15:17,140 --> 01:15:20,870
Jadi untuk setiap tempat jika sudah
disusun, anda membuat satu perbandingan.

1740
01:15:20,870 --> 01:15:22,320
Jadi itu hanya n.

1741
01:15:22,320 --> 01:15:26,840
Dan kerana kita mempunyai kes runtime terbaik
n dan kes runtime paling teruk n

1742
01:15:26,840 --> 01:15:28,680
kuasa dua, kita tidak mempunyai masa jalanan yang diharapkan.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> Ia hanya bergantung kepada
huru-hara dalam senarai kami di sana.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
Dan sekali lagi, satu lagi
graf dan jadual lain.

1747
01:15:39,530 --> 01:15:41,170
Jadi perbezaan antara macam.

1748
01:15:41,170 --> 01:15:44,180
Saya hanya akan angin melalui, saya
berasa seperti kita telah berbincang secara meluas

1749
01:15:44,180 --> 01:15:46,570
tentang bagaimana mereka semua jenis
berbeza-beza dari dan link bersama-sama.

1750
01:15:46,570 --> 01:15:50,564
Jadi bergabung sort adalah yang terakhir
Saya akan melahirkan kalian dengan.

1751
01:15:50,564 --> 01:15:52,105
Kami mempunyai gambar yang cantik berwarna-warni.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Jadi menggabungkan semacam adalah algoritma rekursif.

1754
01:15:56,040 --> 01:15:59,910
Jadi jangan kalian tahu apa yang
fungsi rekursif adalah?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Sesiapa pun mahu katakan?

1757
01:16:03,320 --> 01:16:04,739
Anda mahu mencuba?

1758
01:16:04,739 --> 01:16:07,280
Jadi fungsi rekursif hanya
fungsi yang memanggil dirinya sendiri.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Oleh itu, jika kalian kenal
dengan jujukan Fibonacci,

1761
01:16:11,590 --> 01:16:15,670
yang dianggap rekursif kerana
Anda mengambil dua sebelumnya

1762
01:16:15,670 --> 01:16:17,530
dan menambah mereka bersama-sama
untuk mendapatkan satu di sebelah anda.

1763
01:16:17,530 --> 01:16:21,440
Jadi rekursif, saya selalu berfikir
rekursi sebagai seperti lingkaran

1764
01:16:21,440 --> 01:16:24,430
jadi anda seperti ini semakin ke dalamnya.

1765
01:16:24,430 --> 01:16:27,150
Tetapi ia hanya satu majlis
yang menyebut dirinya.

1766
01:16:27,150 --> 01:16:32,660
>> Dan, benar-benar, benar-benar cepat saya
dapat menunjukkan apa yang kelihatan seperti.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Jadi rekursif di sini, kalau kita lihat, ini adalah
cara rekursif untuk jumlah lebih array.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Jadi semua yang kita lakukan adalah
kita mempunyai fungsi penjumlahan

1771
01:16:47,880 --> 01:16:52,210
jumlah wang itu mengambil ukuran dan array.

1772
01:16:52,210 --> 01:16:55,210
Dan jika anda perhatikan, saiz
pengurangan per satu setiap kali.

1773
01:16:55,210 --> 01:17:00,365
Dan semua hal ini adalah jika x sama dengan
zero-- jadi jika saiz array

1774
01:17:00,365 --> 01:17:02,710
adalah sama dengan zero-- itu kembali sifar.

1775
01:17:02,710 --> 01:17:10,440
>> Jika tidak, jumlah ini
elemen terakhir dari array,

1776
01:17:10,440 --> 01:17:14,790
dan kemudian mengambil sejumlah
sisa array.

1777
01:17:14,790 --> 01:17:17,555
Jadi ia hanya memecahkannya
ke dalam masalah yang lebih kecil dan lebih kecil.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Singkat cerita, rekursi,
fungsi yang memanggil dirinya.

1780
01:17:21,890 --> 01:17:25,740
Jika itu semua yang anda keluar dari ini,
itulah yang fungsi rekursif.

1781
01:17:25,740 --> 01:17:29,870
Jika anda mengambil 51, anda akan mendapat sangat,
sangat selesa dengan rekursi.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
Ia benar-benar sejuk.

1784
01:17:32,370 --> 01:17:34,660
Masuk akal pada seperti
03:00 satu malam.

1785
01:17:34,660 --> 01:17:37,900
Dan aku seperti, mengapa
yang saya tidak pernah menggunakan ini?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Jadi untuk gabungan semacam, pada dasarnya
apa yang ia akan lakukan ialah ia

1788
01:17:42,430 --> 01:17:45,620
akan memecahnya dan pecah
ke bawah sehingga ia hanya satu elemen.

1789
01:17:45,620 --> 01:17:47,570
Unsur-unsur tunggal yang mudah untuk menyusun.

1790
01:17:47,570 --> 01:17:48,070
Kita lihat bahawa.

1791
01:17:48,070 --> 01:17:50,760
Jika anda mempunyai salah satu elemen, itu
sudah dianggap diurutkan.

1792
01:17:50,760 --> 01:17:53,800
Maka pada masukan n unsur,
jika n adalah kurang daripada 2,

1793
01:17:53,800 --> 01:17:58,120
hanya kembali kerana cara yang
itu sama ada 0 atau 1 seperti yang kita lihat.

1794
01:17:58,120 --> 01:18:00,050
Mereka yang dianggap unsur-unsur diurutkan.

1795
01:18:00,050 --> 01:18:02,170
>> Jika tidak pecah menjadi dua.

1796
01:18:02,170 --> 01:18:06,336
Susun separuh pertama, menyusun kedua
setengah, dan kemudian menggabungkan mereka bersama-sama.

1797
01:18:06,336 --> 01:18:07,460
Mengapa ia dipanggil gabungan semacam.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Jadi kami ada di sini kami akan menyusun ini.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Oleh itu, kita tetap memiliki mereka
sehingga saiz array adalah 1.

1802
01:18:17,210 --> 01:18:20,790
Oleh itu, apabila ia adalah 1, kita hanya kembali
kerana ini adalah array diurutkan,

1803
01:18:20,790 --> 01:18:23,940
dan ini adalah array diurutkan, dan itulah
array diurutkan, kami semua disusun.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Jadi maka apa yang kita lakukan adalah kita
mulai menggabungkan mereka bersama-sama.

1806
01:18:29,420 --> 01:18:31,820
>> Jadi cara yang anda boleh
berfikir tentang penggabungan adalah

1807
01:18:31,820 --> 01:18:36,240
Anda hanya menghapus kecil
jumlah setiap sub tatasusunan

1808
01:18:36,240 --> 01:18:38,330
dan hanya menambahkan ke array muncul.

1809
01:18:38,330 --> 01:18:44,290
Jadi, jika anda lihat di sini, apabila kita mempunyai
set ini kita ada 4, 6, dan 1.

1810
01:18:44,290 --> 01:18:47,280
Apabila kita ingin menggabungkan ini,
kita melihat kedua pertama

1811
01:18:47,280 --> 01:18:50,730
dan kita berkata, OK, 1 adalah lebih kecil,
ia pergi ke depan.

1812
01:18:50,730 --> 01:18:54,330
4 dan 6, ada apa-apa untuk membandingkan
untuk, hanya tag ke akhirnya.

1813
01:18:54,330 --> 01:18:58,020
>> Apabila kita menggabungkan kedua, kita hanya
mengambil salah satu yang lebih kecil dari kedua orang ini,

1814
01:18:58,020 --> 01:18:59,310
jadi ia adalah 1.

1815
01:18:59,310 --> 01:19:01,690
Dan kini kita mengambil
lebih kecil dari kedua orang ini, jadi 2.

1816
01:19:01,690 --> 01:19:03,330
Lebih kecil dari kedua-dua, 3.

1817
01:19:03,330 --> 01:19:06,260
Lebih kecil dari kedua-dua, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Jadi anda hanya menarik dari ini.

1819
01:19:08,630 --> 01:19:11,210
Dan kerana mereka telah
telah disusun sebelum ini,

1820
01:19:11,210 --> 01:19:14,300
Anda hanya mempunyai satu
perbandingan setiap waktu di sana.

1821
01:19:14,300 --> 01:19:19,610
Kod Jadi lebih lanjut di sini, perwakilan adil.

1822
01:19:19,610 --> 01:19:24,410
Jadi anda akan bermula pada tengah-tengah dan
Anda semacam kiri dan kanan

1823
01:19:24,410 --> 01:19:26,180
dan kemudian anda hanya menggabungkan mereka.

1824
01:19:26,180 --> 01:19:30,080
>> Dan kita tidak mempunyai kod
untuk bergabung di sini.

1825
01:19:30,080 --> 01:19:34,110
Tetapi, sekali lagi, jika anda pergi ke atas
mengkaji 50, ia akan berada di sana.

1826
01:19:34,110 --> 01:19:36,860
Jika tidak datang bercakap dengan saya
jika anda masih keliru.

1827
01:19:36,860 --> 01:19:42,340
Jadi perkara yang menarik di sini adalah bahawa hal terbaik,
kes terburuk, dan runtime dijangka

1828
01:19:42,340 --> 01:19:46,250
semua dalam log n, yang
adalah jauh lebih baik daripada kita sudah

1829
01:19:46,250 --> 01:19:48,000
dilihat untuk sisa macam kami.

1830
01:19:48,000 --> 01:19:51,840
Kami telah melihat n kuasa dua
dan apa yang kita sebenarnya

1831
01:19:51,840 --> 01:19:54,380
mendapatkan di sini adalah n log n, yang besar.

1832
01:19:54,380 --> 01:19:55,830
>> Lihatlah betapa jauh lebih baik itu.

1833
01:19:55,830 --> 01:19:56,780
Seperti keluk baik.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
Jadi jauh lebih efisien.

1836
01:20:00,120 --> 01:20:03,510
Jika anda boleh, penggunaan menggabungkan semacam.

1837
01:20:03,510 --> 01:20:04,810
Ini akan menjimatkan masa anda.

1838
01:20:04,810 --> 01:20:07,670
Kemudian lagi, seperti yang kita katakan, jika
Anda turun di rantau yang lebih rendah,

1839
01:20:07,670 --> 01:20:09,480
ia tidak membuat yang
banyak perbezaan.

1840
01:20:09,480 --> 01:20:11,360
Anda akan mendapat sehingga beribu-ribu
dan beribu-ribu input,

1841
01:20:11,360 --> 01:20:13,318
Anda pasti mahu
algoritma yang lebih cekap.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
Dan, sekali lagi, meja yang indah kami semua
macam yang anda semua tahu hari ini.

1844
01:20:19,400 --> 01:20:21,157
>> Jadi saya tahu ia pernah ada hari yang padat.

1845
01:20:21,157 --> 01:20:23,490
Ini belum tentu akan
untuk membantu anda dengan Serangga anda.

1846
01:20:23,490 --> 01:20:28,250
Tetapi saya hanya ingin membuat penafian
seksyen itu bukan hanya tentang pşet.

1847
01:20:28,250 --> 01:20:31,240
Semua bahan ini adalah adil
permainan untuk ujian tengah semester anda.

1848
01:20:31,240 --> 01:20:35,430
Dan juga jika anda melakukan melanjutkan dengan CS,
ini adalah asas-asas yang sangat penting

1849
01:20:35,430 --> 01:20:37,870
yang anda perlu tahu.

1850
01:20:37,870 --> 01:20:41,700
Jadi beberapa hari akan menjadi
Serangga kecil bantuan lanjut,

1851
01:20:41,700 --> 01:20:44,600
tetapi beberapa minggu akan
kandungan banyak lagi sebenarnya

1852
01:20:44,600 --> 01:20:46,600
yang mungkin tidak kelihatan super
berguna untuk anda sekarang,

1853
01:20:46,600 --> 01:20:51,215
tapi aku berjanji jika anda terus
atas akan menjadi sangat, sangat berguna.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Jadi itu sahaja untuk bahagian.

1856
01:20:54,250 --> 01:20:55,250
Ke kawat.

1857
01:20:55,250 --> 01:20:56,570
Aku melakukannya dalam masa satu minit.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Tetapi ada anda pergi.

1860
01:20:58,970 --> 01:21:01,240
Dan aku akan donat atau gula-gula.

1861
01:21:01,240 --> 01:21:03,464
Apakah orang alah kepada
apa-apa, dengan cara itu?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Telur dan susu.

1864
01:21:05,890 --> 01:21:08,120
Jadi donat adalah tidak?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Baik.

1868
01:21:10,770 --> 01:21:12,120
Coklat tidak?

1869
01:21:12,120 --> 01:21:12,620
Starburst.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts baik.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Kita akan mempunyai
Starburst minggu depan itu.

1874
01:21:17,045 --> 01:21:18,240
Itu yang saya akan mendapatkan.

1875
01:21:18,240 --> 01:21:19,690
Kalian mempunyai minggu yang besar.

1876
01:21:19,690 --> 01:21:20,460
Baca spec anda.

1877
01:21:20,460 --> 01:21:22,130
>> Beritahu saya jika anda mempunyai sebarang soalan.

1878
01:21:22,130 --> 01:21:25,300
Serangga dua gred harus
kepada anda pada hari Kamis.

1879
01:21:25,300 --> 01:21:28,320
Jika anda mempunyai sebarang pertanyaan
tentang bagaimana saya dinilai sesuatu

1880
01:21:28,320 --> 01:21:32,250
atau mengapa saya dinilai sesuatu cara saya
tidak, sila e-mel saya, datang bercakap dengan saya.

1881
01:21:32,250 --> 01:21:34,210
Saya ini gila sedikit
minggu, tetapi saya berjanji

1882
01:21:34,210 --> 01:21:36,340
Saya masih akan membalas dalam masa 24 jam.

1883
01:21:36,340 --> 01:21:38,240
Jadi mempunyai minggu yang besar, semua orang.

1884
01:21:38,240 --> 01:21:40,090
Nasib baik pada Serangga anda.

1885
01:21:40,090 --> 01:21:41,248