1
00:00:00,000 --> 00:00:03,332
>> [Bermain muzik]

2
00:00:03,332 --> 00:00:06,490
>> ANDI PENG: Selamat datang ke minggu 3 bahagian.

3
00:00:06,490 --> 00:00:09,550
Terima kasih, anda semua, untuk semua yang datang
ini masa mula awal hari ini.

4
00:00:09,550 --> 00:00:11,466
Kami telah mendapat yang baik, sedikit
kumpulan intim hari ini.

5
00:00:11,466 --> 00:00:14,570
Jadi mudah-mudahan kita akan mendapat
kemasan, mungkin, awal,

6
00:00:14,570 --> 00:00:15,780
sedikit awal hari ini.

7
00:00:15,780 --> 00:00:22,057
Begitu cepat, hanya beberapa
pengumuman untuk agenda hari ini.

8
00:00:22,057 --> 00:00:23,890
Sebelum kita bermula, kami
akan hanya pergi

9
00:00:23,890 --> 00:00:28,910
beberapa isu logistik ringkas, pset
soalan, Debrief, perkara seperti itu.

10
00:00:28,910 --> 00:00:30,250
Dan kemudian kita akan digalakkan untuk menterjemah.

11
00:00:30,250 --> 00:00:34,710
Kami akan menggunakan penyahpepijat dipanggil GDB untuk
mula membongkar kod kami, yang David

12
00:00:34,710 --> 00:00:36,550
dijelaskan dalam kuliah pada hari yang lain.

13
00:00:36,550 --> 00:00:39,420
Kami akan pergi ke atas empat jenis macam.

14
00:00:39,420 --> 00:00:42,310
Kami akan pergi ke atas mereka cukup cepat
sejak mereka cukup rapi.

15
00:00:42,310 --> 00:00:45,710
Tetapi tahu bahawa semua slaid dan
kod sumber sentiasa talian.

16
00:00:45,710 --> 00:00:50,810
Jadi berasa bebas, pada penelitian anda, untuk
kembali dan kita lihat itu.

17
00:00:50,810 --> 00:00:53,930
>> Kami akan pergi melalui
notasi asimptot, yang

18
00:00:53,930 --> 00:00:55,944
hanya cara yang mewah
berkata "runtimes,"

19
00:00:55,944 --> 00:00:58,360
di mana kita mempunyai O yang besar, yang
David menjelaskan dalam kuliah.

20
00:00:58,360 --> 00:01:01,550
Dan kami juga mempunyai Omega, yang
adalah runtime yang terikat lebih rendah.

21
00:01:01,550 --> 00:01:06,450
Dan kita akan bercakap sedikit lebih
mendalam mengenai bagaimana mereka bekerja.

22
00:01:06,450 --> 00:01:10,160
Dan akhir sekali, kita akan pergi ke carian binari,
kerana banyak yang sudah

23
00:01:10,160 --> 00:01:15,190
mengerling ke arah psets anda mungkin tahu bahawa
itu adalah soalan yang dalam pset anda.

24
00:01:15,190 --> 00:01:17,470
Jadi, anda semua akan senang
yang kami meliputi hari ini.

25
00:01:17,470 --> 00:01:20,610
>> Dan akhir sekali, setiap anda
seksyen maklum balas, saya benar-benar

26
00:01:20,610 --> 00:01:23,000
meninggalkan kira-kira 15 minit pada
akhir untuk hanya pergi

27
00:01:23,000 --> 00:01:27,730
logistik pset3, apa-apa soalan,
mungkin sedikit panduan, jika anda akan,

28
00:01:27,730 --> 00:01:28,990
sebelum kita mula pengaturcaraan.

29
00:01:28,990 --> 00:01:30,890
Jadi mari kita cuba untuk mendapatkan melalui
bahan yang cukup cepat.

30
00:01:30,890 --> 00:01:33,880
Dan kemudian kita boleh meluangkan sedikit masa
mengambil lebih banyak soalan untuk pset.

31
00:01:33,880 --> 00:01:35,230
OKAY.

32
00:01:35,230 --> 00:01:39,570
>> Dengan cepat, jadi hanya beberapa
pengumuman sebelum kita bermula hari ini.

33
00:01:39,570 --> 00:01:45,410
Pertama sekali, selamat datang untuk membuat
melalui dua daripada psets anda.

34
00:01:45,410 --> 00:01:49,432
Saya mengambil lihat pada your-- yeah, mari kita
mendapatkan satu pusingan tepukan untuk yang itu.

35
00:01:49,432 --> 00:01:51,140
Sebenarnya, saya benar-benar,
benar-benar kagum.

36
00:01:51,140 --> 00:01:55,800
Saya digred pset pertama untuk anda semua
minggu dan kali terakhir anda seorang lelaki lakukan yang luar biasa.

37
00:01:55,800 --> 00:01:58,290
>> Gaya adalah mengenai hal
selain beberapa komen.

38
00:01:58,290 --> 00:02:00,660
Pastikan anda sentiasa
mengulas kod anda.

39
00:02:00,660 --> 00:02:03,040
Tetapi psets anda berada di mata.

40
00:02:03,040 --> 00:02:05,549
Dan bertahan lama.

41
00:02:05,549 --> 00:02:08,090
Dan ia adalah baik untuk gred untuk
melihat bahawa kamu semua meletakkan

42
00:02:08,090 --> 00:02:10,704
sebagai banyak usaha dalam gaya anda
dan reka bentuk anda dalam kod anda

43
00:02:10,704 --> 00:02:12,120
yang kita ingin untuk anda lihat.

44
00:02:12,120 --> 00:02:16,450
Jadi, saya melewati terima kasih
untuk yang lain daripada TA.

45
00:02:16,450 --> 00:02:19,210
>> Walau bagaimanapun terdapat
beberapa soalan Debrief

46
00:02:19,210 --> 00:02:22,010
Saya hanya mahu pergi ke yang
akan menjadikan kedua-dua hidup saya

47
00:02:22,010 --> 00:02:24,900
dan banyak yang lain
TA 'hidup sedikit lebih mudah.

48
00:02:24,900 --> 00:02:28,220
Pertama sekali, saya dapati ini
lalu week-- berapa ramai daripada anda

49
00:02:28,220 --> 00:02:32,301
telah berjalan check50 pada
kod anda sebelum anda hantar?

50
00:02:32,301 --> 00:02:32,800
OKAY.

51
00:02:32,800 --> 00:02:36,690
Jadi semua orang harus lakukan check50,
because-- yang secret-- kita benar-benar

52
00:02:36,690 --> 00:02:41,540
menjalankan check50 sebagai sebahagian daripada kebenaran kami
skrip untuk menguji kod anda.

53
00:02:41,540 --> 00:02:45,480
Jadi, jika kod anda gagal
check50, dalam semua kemungkinan,

54
00:02:45,480 --> 00:02:47,570
ia mungkin akan
gagal mendaftar kita juga.

55
00:02:47,570 --> 00:02:49,320
Kadang-kadang anda semua
mempunyai jawapan yang betul.

56
00:02:49,320 --> 00:02:52,200
Seperti, dalam tamak, beberapa
anda mempunyai nombor yang betul,

57
00:02:52,200 --> 00:02:53,960
anda hanya mencetak beberapa perkara tambahan.

58
00:02:53,960 --> 00:02:55,940
Dan bahawa barangan tambahan
sebenarnya gagal cek,

59
00:02:55,940 --> 00:02:58,440
kerana komputer tidak
benar-benar tahu apa yang ia cari.

60
00:02:58,440 --> 00:03:00,981
Dan sebagainya ia hanya akan berjalan melalui,
melihat bahawa output anda tidak

61
00:03:00,981 --> 00:03:03,810
sepadan dengan apa yang kita harapkan jawapan
menjadi, dan menandakan ia adalah salah.

62
00:03:03,810 --> 00:03:06,560
>> Dan saya tahu yang berlaku di
beberapa kes anda minggu ini.

63
00:03:06,560 --> 00:03:09,870
Jadi saya kembali dan secara manual
digred semula kod semua orang.

64
00:03:09,870 --> 00:03:12,780
Pada masa akan datang walaupun,
sila, sila pastikan

65
00:03:12,780 --> 00:03:14,570
bahawa anda menjalankan
menyemak 50 pada kod anda.

66
00:03:14,570 --> 00:03:17,970
Oleh kerana ia adalah jenis sakit untuk TA
untuk mempunyai untuk kembali dan secara manual Regrade

67
00:03:17,970 --> 00:03:21,197
setiap pset tunggal bagi setiap
tunggal, misalnya sedikit terlepas.

68
00:03:21,197 --> 00:03:22,530
Jadi saya tidak mengambil kira apa-apa mata.

69
00:03:22,530 --> 00:03:25,210
Saya rasa saya mengambil kira mungkin
satu atau dua untuk reka bentuk.

70
00:03:25,210 --> 00:03:27,710
Pada masa akan datang walaupun, jika
anda gagal check50,

71
00:03:27,710 --> 00:03:31,330
mata akan diambil
padang kerana kebenaran.

72
00:03:31,330 --> 00:03:35,020
>> Tambahan pula, psets adalah
kerana hari Jumaat pada tengah hari.

73
00:03:35,020 --> 00:03:38,990
Saya fikir ada tujuh minit
Tambahan masa lewat yang kita berikan anda.

74
00:03:38,990 --> 00:03:42,434
Penerbangan masa Harvard, mereka dibenarkan untuk
tujuh minit lewat untuk segala-galanya.

75
00:03:42,434 --> 00:03:44,350
Jadi di sini di Yale, kami akan
mematuhi itu juga.

76
00:03:44,350 --> 00:03:47,910
Tetapi cukup banyak, pada 00:07,
jika pset anda tidak berada dalam,

77
00:03:47,910 --> 00:03:49,720
ia akan diingati sebagai lewat.

78
00:03:49,720 --> 00:03:53,160
Dan jadi sementara ia ditandakan
sebagai-an, TA-- Saya

79
00:03:53,160 --> 00:03:54,870
masih akan penggredan psets anda.

80
00:03:54,870 --> 00:03:56,760
Oleh itu, anda masih akan melihat gred yang muncul.

81
00:03:56,760 --> 00:03:58,820
Walau bagaimanapun, tahu bahawa pada
akhir semester,

82
00:03:58,820 --> 00:04:02,270
semua psets lewat hanya akan menjadi
secara automatik menumpukan perhatian oleh komputer.

83
00:04:02,270 --> 00:04:04,490
>> Kami melakukan ini kerana dua sebab.

84
00:04:04,490 --> 00:04:09,220
Satu, kadang-kadang kita mendapatkan
dimaafkan, seperti alasan dekan,

85
00:04:09,220 --> 00:04:10,762
kemudian bahawa saya tidak tahu tentang lagi.

86
00:04:10,762 --> 00:04:13,761
Oleh itu, kita suka untuk memastikan bahawa kami tidak penggredan
segala-galanya hanya dalam kes, seperti, Saya

87
00:04:13,761 --> 00:04:15,080
hilang alasan yang dekan.

88
00:04:15,080 --> 00:04:17,000
Dan kedua, perlu
fikiran, anda masih boleh

89
00:04:17,000 --> 00:04:19,370
menggugurkan satu Serangga yang
mempunyai mata skop penuh.

90
00:04:19,370 --> 00:04:21,430
Dan supaya kita suka untuk gred
semua psets anda hanya

91
00:04:21,430 --> 00:04:24,730
memastikan bahawa skop anda
di sana dan anda cuba mereka.

92
00:04:24,730 --> 00:04:29,150
Jadi, walaupun ia lewat, anda akan masih
mendapatkan kredit untuk mata skop, saya fikir.

93
00:04:29,150 --> 00:04:33,730
>> Jadi moral cerita ini adalah, membuat
memastikan psets anda berada dalam pada masa.

94
00:04:33,730 --> 00:04:38,350
Dan jika mereka tidak berada di dalam masa,
tahu bahawa ia bukan yang besar.

95
00:04:38,350 --> 00:04:41,678
Ya, sebelum saya bergerak ke atas, tidak sesiapa yang mempunyai
sebarang pertanyaan mengenai maklum balas pset?

96
00:04:41,678 --> 00:04:42,178
Yeah.

97
00:04:42,178 --> 00:04:43,630
>> PENONTON: Adakah anda mengatakan bahawa kita
boleh turun salah satu daripada psets?

98
00:04:43,630 --> 00:04:44,296
>> ANDI PENG: Ya.

99
00:04:44,296 --> 00:04:47,050
Jadi ada sembilan psets keseluruhan
sepanjang semester.

100
00:04:47,050 --> 00:04:50,610
Dan jika anda mempunyai skop
points-- supaya skop keadilan,

101
00:04:50,610 --> 00:04:53,567
cukup banyak, yang anda cuba yang
masalah, anda meletakkan dalam masa,

102
00:04:53,567 --> 00:04:56,150
yang anda menunjukkan bahawa anda telah
menunjukkan anda telah membaca spesifikasi.

103
00:04:56,150 --> 00:04:57,191
Itulah skop cukup banyak.

104
00:04:57,191 --> 00:04:59,370
Dan jika anda memenuhi
mata skop, kita

105
00:04:59,370 --> 00:05:03,360
boleh turun serendah
satu daripada skop penuh.

106
00:05:03,360 --> 00:05:06,790
Jadi itulah dalam kelebihan anda untuk
melengkapkan dan cuba setiap pset.

107
00:05:06,790 --> 00:05:10,320
>> Walaupun upload-- jika tiada
mereka bekerja, memuat naik mereka semua.

108
00:05:10,320 --> 00:05:13,711
Dan kemudian kita mudah-mudahan akan dapat
memberi anda beberapa mata tersebut kembali.

109
00:05:13,711 --> 00:05:14,210
Sejuk.

110
00:05:14,210 --> 00:05:16,780
Apa-apa soalan lain?

111
00:05:16,780 --> 00:05:17,840
Yang besar.

112
00:05:17,840 --> 00:05:21,960
>> Kedua, pejabat hours-- beberapa
nota ringkas mengenai waktu pejabat.

113
00:05:21,960 --> 00:05:24,300
Jadi pertama, datang awal minggu ini.

114
00:05:24,300 --> 00:05:26,909
Tiada siapa yang pernah di
waktu pejabat pada hari Isnin.

115
00:05:26,909 --> 00:05:28,700
Christabel datang ke
waktu pejabat, malam tadi.

116
00:05:28,700 --> 00:05:29,691
Ya, Christabel.

117
00:05:29,691 --> 00:05:32,190
Dan apa yang kita ada di pejabat
jam malam tadi, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> PENONTON: Kami mempunyai ais krim.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Jadi, itu betul, kita mempunyai
ais krim di waktu pejabat, malam tadi.

120
00:05:36,160 --> 00:05:39,390
Walaupun saya tidak boleh berjanji kepada anda bahawa
kita akan mempunyai ais krim di waktu pejabat

121
00:05:39,390 --> 00:05:43,230
setiap minggu, apa yang boleh saya berjanji kepada anda
adalah bahawa akan menjadi ketara

122
00:05:43,230 --> 00:05:45,380
pelajar yang lebih baik kepada nisbah TA.

123
00:05:45,380 --> 00:05:47,650
Seperti legit, ia seperti 3-1.

124
00:05:47,650 --> 00:05:50,350
Manakala, bezakan bahawa dengan
Khamis, anda mempunyai kira-kira 150

125
00:05:50,350 --> 00:05:52,830
benar-benar menekankan kanak-kanak dan tiada ais krim.

126
00:05:52,830 --> 00:05:55,360
Dan ia hanya tidak produktif untuk sesiapa sahaja.

127
00:05:55,360 --> 00:05:58,730
Jadi moral cerita itu, datang awal
kepada waktu pejabat dan perkara-perkara yang baik

128
00:05:58,730 --> 00:06:00,310
akan berlaku.

129
00:06:00,310 --> 00:06:02,110
>> Juga, datang bersedia untuk bertanya soalan.

130
00:06:02,110 --> 00:06:03,200
Awak tahu?

131
00:06:03,200 --> 00:06:05,420
Tidak kira apa TA, saya
berfikir, telah berkata,

132
00:06:05,420 --> 00:06:10,710
kita telah mendapat beberapa pelajar
yang datang pada hari Khamis pada, seperti, 10:50

133
00:06:10,710 --> 00:06:15,100
tidak membaca spec
menjadi seperti membantu saya, membantu saya.

134
00:06:15,100 --> 00:06:18,200
Malangnya pada ketika itu, ada
tidak banyak yang boleh kita lakukan untuk membantu anda.

135
00:06:18,200 --> 00:06:19,590
Oleh itu, sila datang awal minggu ini.

136
00:06:19,590 --> 00:06:22,040
Datang awal untuk waktu pejabat.

137
00:06:22,040 --> 00:06:23,350
Datang bersedia untuk bertanya soalan.

138
00:06:23,350 --> 00:06:25,310
Pastikan bahawa anda, sebagai
seorang pelajar, adalah di mana

139
00:06:25,310 --> 00:06:27,620
anda perlu supaya
TA boleh membimbing anda bersama-sama,

140
00:06:27,620 --> 00:06:32,850
iaitu apa waktu pejabat
sepatutnya diperuntukkan untuk.

141
00:06:32,850 --> 00:06:37,380
>> Kedua, jadi saya tahu profesor
suka untuk mengejutkan kita dengan ujian.

142
00:06:37,380 --> 00:06:39,439
Saya mempunyai seorang profesor mereka
seperti, yo, dengan cara itu,

143
00:06:39,439 --> 00:06:41,230
ingat separuh penggal yang
anda mempunyai Isnin depan.

144
00:06:41,230 --> 00:06:42,855
Ya, saya tidak tahu tentang separuh penggal itu.

145
00:06:42,855 --> 00:06:45,630
Jadi, saya akan menjadi yang TA
yang mengingatkan anda semua kuiz yang

146
00:06:45,630 --> 00:06:47,270
0-- kerana, anda tahu, kami CS.

147
00:06:47,270 --> 00:06:50,730
Sekarang kami telah tatasusunan dilakukan, anda akan mendapat
mengapa ia kuiz 0, bukan kuiz 1, eh?

148
00:06:50,730 --> 00:06:51,320
OKAY.

149
00:06:51,320 --> 00:06:52,490
Oh, saya mendapat beberapa chuckles pada yang satu.

150
00:06:52,490 --> 00:06:53,120
OKAY.

151
00:06:53,120 --> 00:06:59,710
>> Jadi kuiz 0 akan menjadi 14 Okt jika
anda berada dalam bahagian Isnin-Rabu

152
00:06:59,710 --> 00:07:02,920
dan 15 Oktober jika anda berada dalam
bahagian Selasa-Khamis.

153
00:07:02,920 --> 00:07:05,630
Ini tidak terpakai bagi
Pelawat di Harvard

154
00:07:05,630 --> 00:07:10,350
yang- saya rasa anda semua akan menjadi
mengambil kuiz anda pada ke-14.

155
00:07:10,350 --> 00:07:13,560
>> Jadi ya, minggu depan, jika
David, dalam kuliah, pergi,

156
00:07:13,560 --> 00:07:15,747
yeah, jadi kira-kira yang
kuiz minggu depan, anda semua

157
00:07:15,747 --> 00:07:17,580
tidak akan terkejut kerana
anda datang ke seksyen

158
00:07:17,580 --> 00:07:19,664
dan anda tahu bahawa anda
kuiz 0 adalah dalam dua minggu.

159
00:07:19,664 --> 00:07:21,580
Dan kita akan mempunyai kajian
sesi dan segala-galanya.

160
00:07:21,580 --> 00:07:26,360
Jadi tidak ada kebimbangan mengenai
menjadi takut untuk itu.

161
00:07:26,360 --> 00:07:29,890
Sebarang soalan sebelum itu apa-apa soalan
di semua isu-isu logistik mengenai,

162
00:07:29,890 --> 00:07:32,591
penggredan, waktu pejabat, bahagian-bahagian?

163
00:07:32,591 --> 00:07:33,090
Yeah.

164
00:07:33,090 --> 00:07:35,100
>> PENONTON: Jadi kuiz adalah
akan menjadi semasa kuliah?

165
00:07:35,100 --> 00:07:35,766
>> ANDI PENG: Ya.

166
00:07:35,766 --> 00:07:39,460
Jadi kuiz, saya fikir, adalah 60
minit yang diperuntukkan dalam bahawa slot masa

167
00:07:39,460 --> 00:07:42,240
bahawa anda hanya akan mengambil
di dalam dewan kuliah.

168
00:07:42,240 --> 00:07:44,810
Jadi anda tidak perlu datang dalam
pada, seperti, rawak 07:00.

169
00:07:44,810 --> 00:07:46,140
Itu semua baik.

170
00:07:46,140 --> 00:07:47,100
Yeah.

171
00:07:47,100 --> 00:07:50,060
Sejuk.

172
00:07:50,060 --> 00:07:50,840
>> Baiklah.

173
00:07:50,840 --> 00:07:54,330
Oleh itu, kita akan
memperkenalkan konsep kepada anda

174
00:07:54,330 --> 00:08:00,760
minggu ini bahawa Daud telah pun jenis
daripada menyentuh dalam syarahan ini minggu lalu.

175
00:08:00,760 --> 00:08:02,010
Ia dipanggil GDB.

176
00:08:02,010 --> 00:08:05,570
Dan berapa ramai daripada anda, manakala di
semasa menulis psets anda,

177
00:08:05,570 --> 00:08:09,981
perasan butang besar yang mengatakan
"Debug" pada bahagian atas IDE anda?

178
00:08:09,981 --> 00:08:10,480
OKAY.

179
00:08:10,480 --> 00:08:13,770
Oleh sebab itu kita benar-benar akan dapat mencungkil
misteri apa butang yang benar-benar

180
00:08:13,770 --> 00:08:14,270
tidak.

181
00:08:14,270 --> 00:08:16,790
Dan saya jamin anda, ia adalah satu
indah, perkara yang indah.

182
00:08:16,790 --> 00:08:20,740
>> Jadi sehingga kini, saya rasa
telah ada dua perkara

183
00:08:20,740 --> 00:08:23,320
pelajar ini adalah pada lazimnya
lakukan apabila debugging psets.

184
00:08:23,320 --> 00:08:27,635
Satu, mereka sama ada tambahkan
printf () - jadi setiap beberapa baris,

185
00:08:27,635 --> 00:08:29,760
mereka menambah dalam printf () -
oh, apa yang berubah-ubah ini?

186
00:08:29,760 --> 00:08:32,551
Oh, apa yang berubah-ubah ini sekarang--
dan anda jenis melihat perkembangan

187
00:08:32,551 --> 00:08:33,940
kod anda semasa jalanan.

188
00:08:33,940 --> 00:08:37,030
Atau kaedah kedua anak-anak lakukan adalah
bahawa mereka hanya menulis segala-galanya

189
00:08:37,030 --> 00:08:38,610
dan kemudian pergi seperti ini pada akhir.

190
00:08:38,610 --> 00:08:39,970
Mudah-mudahan ia berfungsi.

191
00:08:39,970 --> 00:08:44,851
Saya jamin anda, GDB adalah lebih baik
daripada kedua-dua mereka kaedah.

192
00:08:44,851 --> 00:08:45,350
Yeah.

193
00:08:45,350 --> 00:08:46,980
Jadi ini akan menjadi rakan baru anda yang terbaik.

194
00:08:46,980 --> 00:08:51,780
Kerana ia adalah satu perkara yang indah
yang visual memaparkan kedua-dua

195
00:08:51,780 --> 00:08:54,850
apa kod anda lakukan
pada satu titik tertentu

196
00:08:54,850 --> 00:08:57,486
dan juga apa yang semua anda
pemboleh ubah yang dibawa,

197
00:08:57,486 --> 00:08:59,610
seperti apa nilai-nilai mereka,
pada titik tertentu.

198
00:08:59,610 --> 00:09:02,670
Dan dengan cara ini, anda boleh benar-benar
menetapkan titik putus dalam kod anda.

199
00:09:02,670 --> 00:09:04,350
Anda boleh berjalan melalui baris demi baris.

200
00:09:04,350 --> 00:09:07,324
Dan GDB hanya perlu untuk
anda, dipaparkan untuk anda,

201
00:09:07,324 --> 00:09:09,490
apa semua pembolehubah anda
adalah, apa yang mereka lakukan,

202
00:09:09,490 --> 00:09:10,656
apa yang berlaku di dalam kod.

203
00:09:10,656 --> 00:09:13,240
Dan dalam apa-apa cara, ia adalah
lebih mudah untuk melihat

204
00:09:13,240 --> 00:09:17,120
apa yang berlaku bukannya printf-ing
atau menulis kenyataan anda.

205
00:09:17,120 --> 00:09:19,160
>> Oleh itu, kita akan melakukan satu contoh ini kemudian.

206
00:09:19,160 --> 00:09:20,660
Jadi ini seolah-olah satu abstrak bit.

207
00:09:20,660 --> 00:09:23,490
Jangan bimbang, kami akan melakukan contoh.

208
00:09:23,490 --> 00:09:29,170
Dan sebagainya pada dasarnya, ketiga-tiga terbesar,
Fungsi yang selalu digunakan yang anda perlukan dalam GDB

209
00:09:29,170 --> 00:09:32,500
adalah Seterusnya, Langkah ke atas,
dan Masuklah ke butang.

210
00:09:32,500 --> 00:09:34,860
Saya akan menuju
di sana, sebenarnya, sekarang.

211
00:09:34,860 --> 00:09:40,930
>> Jadi kalian semua dapat melihat bahawa
atau saya perlu zum masuk sedikit?

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
Di belakang, anda dapat melihat bahawa?

214
00:09:44,470 --> 00:09:45,730
Adakah saya perlu zum masuk?

215
00:09:45,730 --> 00:09:46,480
Cuma sedikit?

216
00:09:46,480 --> 00:09:49,390
OK, sejuk.

217
00:09:49,390 --> 00:09:50,280
Di sana kami pergi.

218
00:09:50,280 --> 00:09:50,960
OKAY.

219
00:09:50,960 --> 00:09:57,000
>> Jadi saya perlu, di sini, saya
pelaksanaan bagi tamak.

220
00:09:57,000 --> 00:10:01,430
Dan manakala banyak kamu menulis
tamak dalam gelung sementara form-- yang

221
00:10:01,430 --> 00:10:04,890
adalah cara yang boleh diterima untuk melakukan
kitab itu satu lagi cara untuk melakukannya adalah dengan hanya

222
00:10:04,890 --> 00:10:06,280
membahagikan dalam modulo itu.

223
00:10:06,280 --> 00:10:09,290
Kerana anda boleh mempunyai anda
nilai dan kemudian mempunyai baki anda.

224
00:10:09,290 --> 00:10:11,150
Dan kemudian anda boleh hanya
menambah semua bersama-sama.

225
00:10:11,150 --> 00:10:13,390
Adakah logik apa yang saya lakukan
di sini masuk akal untuk semua orang,

226
00:10:13,390 --> 00:10:14,117
sebelum kita bermula?

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
Jenis?

229
00:10:17,980 --> 00:10:18,710
Sejuk.

230
00:10:18,710 --> 00:10:19,210
Yang besar.

231
00:10:19,210 --> 00:10:21,290
Ia adalah sekeping cantik seksi
kod, saya akan berkata.

232
00:10:21,290 --> 00:10:23,502
Seperti saya katakan, Daud,
syarahan, selepas beberapa ketika,

233
00:10:23,502 --> 00:10:25,960
anda semua akan mula melihat kod
sebagai sesuatu yang indah.

234
00:10:25,960 --> 00:10:29,950
Dan kadang-kadang apabila anda melihat indah
kod, ia seperti satu perasaan yang indah.

235
00:10:29,950 --> 00:10:35,410
>> Jadi bagaimanapun, manakala kod ini adalah sangat
indah, ia tidak berfungsi dengan baik.

236
00:10:35,410 --> 00:10:37,750
Jadi mari kita berjalan check50 mengenai perkara ini.

237
00:10:37,750 --> 00:10:39,440
Semak 50 20-- oop.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2?

240
00:10:43,720 --> 00:10:44,990
Adakah pset2 itu?

241
00:10:44,990 --> 00:10:46,870
Yeah.

242
00:10:46,870 --> 00:10:47,520
Oh, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
OKAY.

245
00:10:52,890 --> 00:10:53,900
Oleh itu, kita menjalankan check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> Dan seperti yang anda semua boleh lihat di sini,
ia gagal beberapa kes.

248
00:11:07,170 --> 00:11:10,165
Dan bagi sesetengah daripada anda, dalam
proses menjalankan set masalah anda,

249
00:11:10,165 --> 00:11:11,110
anda seperti, ah, mengapa tidak ia bekerja.

250
00:11:11,110 --> 00:11:13,318
Mengapa ia bekerja untuk beberapa
nilai tetapi tidak untuk orang lain?

251
00:11:13,318 --> 00:11:17,760
Nah, GDB akan membantu angka anda
mengapa mereka input itu tidak berfungsi.

252
00:11:17,760 --> 00:11:18,320
>> OKAY.

253
00:11:18,320 --> 00:11:21,640
Jadi mari kita lihat, salah satu daripada
cek saya gagal dalam check50

254
00:11:21,640 --> 00:11:24,920
adalah nilai input 0.41.

255
00:11:24,920 --> 00:11:27,830
Jadi jawapan yang betul yang
anda perlu mendapatkan ialah 4.

256
00:11:27,830 --> 00:11:33,090
Tetapi sebaliknya apa yang saya mencetak
adalah 3-n, yang tidak betul.

257
00:11:33,090 --> 00:11:36,190
Jadi mari kita hanya menjalankan ini secara manual, hanya
memastikan bahawa check50 bekerja.

258
00:11:36,190 --> 00:11:36,940
Mari kita buat ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Oops, saya perlu membuat tamak.

261
00:11:43,340 --> 00:11:43,840
Di sana kami pergi.

262
00:11:43,840 --> 00:11:44,381
Sekarang ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> Berapa banyak yang berhutang?

265
00:11:47,670 --> 00:11:49,550
Mari kita buat 0.41.

266
00:11:49,550 --> 00:11:52,590
Dan yep, kita lihat di sini
bahawa ia keluarkan 3

267
00:11:52,590 --> 00:11:55,160
apabila jawapan yang betul,
sebenarnya, perlu 4.

268
00:11:55,160 --> 00:12:01,460
Jadi mari kita masukkan GDB dan melihat bagaimana kita
boleh pergi tentang cara menangani masalah ini.

269
00:12:01,460 --> 00:12:03,992
>> Jadi langkah pertama dalam
sentiasa debugging kod anda

270
00:12:03,992 --> 00:12:05,950
adalah untuk menetapkan titik putus a,
atau titik di mana anda

271
00:12:05,950 --> 00:12:09,079
mahu komputer atau
penyahpepijat untuk mula melihat.

272
00:12:09,079 --> 00:12:11,120
Jadi, jika anda tidak benar-benar
tahu apa masalah anda,

273
00:12:11,120 --> 00:12:14,670
biasanya, perkara yang biasa kita mahu
lakukan adalah untuk menetapkan titik putus kami di utama.

274
00:12:14,670 --> 00:12:18,520
Jadi, jika anda semua boleh melihat ini
butang merah di sana,

275
00:12:18,520 --> 00:12:22,860
yep, yang saya menetapkan
Titik Henti untuk fungsi utama.

276
00:12:22,860 --> 00:12:24,130
Saya klik itu.

277
00:12:24,130 --> 00:12:26,130
>> Dan kemudian saya boleh naik ke butang Debug saya.

278
00:12:26,130 --> 00:12:27,036
Saya tekan butang itu.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Biar saya zum keluar jika saya boleh.

281
00:12:36,555 --> 00:12:38,020
Di sana kami pergi.

282
00:12:38,020 --> 00:12:40,730
Jadi kita mempunyai, di sini, panel sebelah kanan.

283
00:12:40,730 --> 00:12:43,680
Saya minta maaf, lelaki di belakang, anda
tidak boleh benar-benar melihat dengan sangat baik.

284
00:12:43,680 --> 00:12:49,090
Tetapi pada dasarnya, semua
panel ini di lakukan

285
00:12:49,090 --> 00:12:53,130
yang mengesan kedua-dua yang diserlahkan
talian, yang merupakan baris kod

286
00:12:53,130 --> 00:12:56,640
bahawa komputer sedang berjalan,
dan juga semua pembolehubah anda

287
00:12:56,640 --> 00:12:57,600
di bawah ini.

288
00:12:57,600 --> 00:13:00,487
>> Jadi, anda telah mendapat sen, syiling, n,
semua diisytiharkan perkara yang berbeza

289
00:13:00,487 --> 00:13:01,070
pada ketika ini.

290
00:13:01,070 --> 00:13:04,850
Jangan bimbang, kerana kita tidak benar-benar
dimulakan mereka kepada mana-mana pemboleh ubah lagi.

291
00:13:04,850 --> 00:13:07,200
Jadi dalam komputer anda, anda
komputer baru sahaja melihat,

292
00:13:07,200 --> 00:13:14,376
oh, 32767 adalah fungsi yang terakhir digunakan
itu ruang ingatan dalam komputer saya.

293
00:13:14,376 --> 00:13:16,000
Dan supaya di mana sen pada masa ini.

294
00:13:16,000 --> 00:13:19,360
Tetapi tidak bahawa apabila anda menjalankan kod,
ia harus menjadi dimulakan.

295
00:13:19,360 --> 00:13:24,110
>> Jadi mari kita pergi melalui, baris demi
talian, apa yang berlaku di sini.

296
00:13:24,110 --> 00:13:25,350
OKAY.

297
00:13:25,350 --> 00:13:29,400
Jadi di sini adalah tiga
butang yang saya hanya menjelaskan.

298
00:13:29,400 --> 00:13:34,090
Anda perlu Main, atau fungsi Run,
butang, anda perlu Langkah butang ke atas,

299
00:13:34,090 --> 00:13:36,600
dan anda juga mempunyai Langkah ke butang.

300
00:13:36,600 --> 00:13:41,260
Dan pada dasarnya, ketiga-tiga
mereka hanya pergi melalui kod anda

301
00:13:41,260 --> 00:13:42,690
dan melakukan perkara-perkara yang berbeza.

302
00:13:42,690 --> 00:13:45,680
>> Jadi biasanya, apabila anda debugging,
kita tidak mahu hanya tekan Main,

303
00:13:45,680 --> 00:13:47,930
kerana Main hanya akan berjalan
kod anda untuk akhir itu.

304
00:13:47,930 --> 00:13:49,070
Dan kemudian anda tidak akan benar-benar
tahu apa masalah anda

305
00:13:49,070 --> 00:13:51,432
adalah melainkan jika anda menetapkan pelbagai titik putus.

306
00:13:51,432 --> 00:13:53,890
Jika anda menetapkan pelbagai titik putus,
ia akan hanya secara automatik

307
00:13:53,890 --> 00:13:56,030
berjalan dari satu titik putus,
ke depan, ke depan.

308
00:13:56,030 --> 00:13:58,030
Tetapi dalam kes ini kami telah
hanya satu yang, kerana kita

309
00:13:58,030 --> 00:13:59,970
mahu bekerja cara kita
dari atas turun ke bawah.

310
00:13:59,970 --> 00:14:04,830
Jadi, kita akan mengabaikan butang yang
sekarang untuk tujuan program ini.

311
00:14:04,830 --> 00:14:08,230
>> Jadi Langkah alih fungsi hanya
langkah-langkah ke atas setiap baris

312
00:14:08,230 --> 00:14:11,510
dan memberitahu anda apa
komputer lakukan.

313
00:14:11,510 --> 00:14:14,630
Langkah ke dalam fungsi pergi
ke dalam fungsi sebenar

314
00:14:14,630 --> 00:14:16,000
yang pada talian anda kod.

315
00:14:16,000 --> 00:14:19,070
Jadi, sebagai contoh, seperti printf (),
iaitu fungsi, bukan?

316
00:14:19,070 --> 00:14:21,980
Jika saya mahu langkah fizikal
ke dalam fungsi printf (),

317
00:14:21,980 --> 00:14:25,610
Saya benar-benar akan pergi ke dalam sekeping
kod di mana printf () telah ditulis dan melihat

318
00:14:25,610 --> 00:14:26,730
apa yang sedang berlaku di sana.

319
00:14:26,730 --> 00:14:29,924
>> Tetapi biasanya, kita menganggap bahawa
kod yang kami memberi anda berfungsi.

320
00:14:29,924 --> 00:14:31,340
Kami menganggap printf () bekerja.

321
00:14:31,340 --> 00:14:33,170
Kami menganggap bahawa GetInt () bekerja.

322
00:14:33,170 --> 00:14:35,170
Jadi tidak ada keperluan untuk
melangkah ke fungsi-fungsi itu.

323
00:14:35,170 --> 00:14:37,170
Tetapi jika ada fungsi
yang anda tulis sendiri

324
00:14:37,170 --> 00:14:39,060
yang anda mahu untuk memeriksa
mengetahui apa yang berlaku,

325
00:14:39,060 --> 00:14:41,200
anda yang sanggup membuat
ke dalam fungsi itu.

326
00:14:41,200 --> 00:14:43,940
>> Jadi sekarang kita hanya akan
melangkah ini sekeping kod.

327
00:14:43,940 --> 00:14:44,485
Jadi mari kita lihat.

328
00:14:44,485 --> 00:14:46,547
Oh, cetak, "Oh hai, bagaimana
banyak perubahan berhutang? "

329
00:14:46,547 --> 00:14:47,130
Kami tidak peduli.

330
00:14:47,130 --> 00:14:49,830
Kita tahu bahawa bekerja,
jadi kami melangkah ke atasnya.

331
00:14:49,830 --> 00:14:53,290
>> Jadi n, yang terapung kami yang
kami telah initialized-- atau declared--

332
00:14:53,290 --> 00:14:56,810
sehingga di bahagian atas, kami kini
menyamai bahawa untuk GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Jadi mari kita melangkah itu.

334
00:14:57,810 --> 00:14:59,580
Dan kita lihat di
bawah di sini, program ini

335
00:14:59,580 --> 00:15:03,360
adalah mendorong saya untuk input nilai.

336
00:15:03,360 --> 00:15:08,580
Jadi mari kita input nilai yang kami mahu
untuk menguji di sini, iaitu 0.41.

337
00:15:08,580 --> 00:15:09,160
Yang besar.

338
00:15:09,160 --> 00:15:12,780
>> Jadi sekarang n-- adakah anda seorang lelaki melihat
di sini, pada bottom-- ia

339
00:15:12,780 --> 00:15:15,140
stored-- kerana kita
tidak bulat lagi, ia

340
00:15:15,140 --> 00:15:19,540
disimpan dalam gergasi seperti ini
apungan yang ,4099999996,

341
00:15:19,540 --> 00:15:22,550
yang cukup dekat dengan kami
tujuan, sekarang, untuk 0.41.

342
00:15:22,550 --> 00:15:26,090
Dan kemudian kita akan melihat di kemudian hari, seperti yang kita
terus melangkah lebih program ini,

343
00:15:26,090 --> 00:15:29,850
selepas sini, n telah menjadi
bulat dan sen menjadi 41.

344
00:15:29,850 --> 00:15:30,350
Yang besar.

345
00:15:30,350 --> 00:15:32,230
Jadi kita tahu bahawa kerja pembundaran kita.

346
00:15:32,230 --> 00:15:34,700
Kita tahu bahawa kita mempunyai
nombor yang betul sen,

347
00:15:34,700 --> 00:15:36,990
jadi kita tahu bahawa itulah
tidak benar-benar masalah.

348
00:15:36,990 --> 00:15:40,050
>> Oleh itu, kita terus melangkah
di dalam program ini.

349
00:15:40,050 --> 00:15:40,900
Kami pergi di sini.

350
00:15:40,900 --> 00:15:46,139
Dan sebagainya selepas baris kod ini, kita
akan melihat bagaimana banyak pihak yang kita ada.

351
00:15:46,139 --> 00:15:46,680
Kami melangkah.

352
00:15:46,680 --> 00:15:52,040
Dan kamu melihat kita, sebenarnya, mempunyai satu
suku kerana kita telah ditolak 25

353
00:15:52,040 --> 00:15:53,790
daripada nilai awal kami 41.

354
00:15:53,790 --> 00:15:55,890
Dan kita mempunyai 16 kiri untuk sen kami.

355
00:15:55,890 --> 00:15:58,830
>> Adakah semua orang memahami bagaimana
program ini melangkah

356
00:15:58,830 --> 00:16:02,980
dan mengapa sen kini telah menjadi 16
dan mengapa, sekarang, syiling telah menjadi 1?

357
00:16:02,980 --> 00:16:04,610
Adakah semua orang mengikut logik itu?

358
00:16:04,610 --> 00:16:05,110
Sejuk.

359
00:16:05,110 --> 00:16:07,860
Jadi pada ketika ini,
kerja program ini, bukan?

360
00:16:07,860 --> 00:16:09,797
Kita tahu ia lakukan betul-betul
apa yang kita mahu ia.

361
00:16:09,797 --> 00:16:11,880
Dan kita tidak benar-benar
perlu mencetak, oh, apa

362
00:16:11,880 --> 00:16:14,430
adalah sen pada masa ini,
apa yang syiling pada ketika ini.

363
00:16:14,430 --> 00:16:17,170
>> Kami terus melalui program ini.

364
00:16:17,170 --> 00:16:18,100
Melangkah.

365
00:16:18,100 --> 00:16:18,620
Sejuk.

366
00:16:18,620 --> 00:16:19,700
Kami akan ke dimes.

367
00:16:19,700 --> 00:16:20,200
Yang besar.

368
00:16:20,200 --> 00:16:22,367
Kita lihat bahawa ia diambil
kira $ 0,10 untuk ada yang.

369
00:16:22,367 --> 00:16:23,450
Dan sekarang kita mempunyai dua syiling.

370
00:16:23,450 --> 00:16:25,260
Itulah betul.

371
00:16:25,260 --> 00:16:31,555
>> Kami pergi ke atas beberapa sen dan kita lihat
bahawa kami telah mendapat ditinggalkan sen.

372
00:16:31,555 --> 00:16:32,680
Hmm, itu pelik.

373
00:16:32,680 --> 00:16:37,540
Di sini pada program itu, saya sepatutnya
telah ditolak beberapa sen saya.

374
00:16:37,540 --> 00:16:39,400
Mungkin saya hanya tidak
melakukan hak itu garis.

375
00:16:39,400 --> 00:16:42,190
Dan malangnya, anda boleh melihat
di sini, kerana kita tahu

376
00:16:42,190 --> 00:16:44,360
bahawa kita melangkah
melalui talian 32 dan 33,

377
00:16:44,360 --> 00:16:50,560
itulah di mana program kami
secara tidak wajar mempunyai pembolehubah berjalan.

378
00:16:50,560 --> 00:16:55,136
Oleh itu, kita boleh melihat dan melihat, oh,
Saya menolak sen sini,

379
00:16:55,136 --> 00:16:57,010
tetapi saya tidak benar-benar
menambah nilai duit syiling saya.

380
00:16:57,010 --> 00:16:57,860
Saya menambah untuk sen.

381
00:16:57,860 --> 00:17:00,234
Dan saya tidak mahu menambah
sen, saya ingin menambah duit syiling.

382
00:17:00,234 --> 00:17:05,420
Jadi, jika kita menukar bahawa untuk syiling,
kami mempunyai program kerja.

383
00:17:05,420 --> 00:17:06,730
Saya boleh menjalankan check50.

384
00:17:06,730 --> 00:17:11,063
Anda hanya boleh keluar daripada GDB betul
di sini dan kemudian berjalan check50 lagi.

385
00:17:11,063 --> 00:17:11,938
Saya hanya boleh melakukan ini.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Saya perlu membuat tamak.

388
00:17:18,480 --> 00:17:19,940
0.41.

389
00:17:19,940 --> 00:17:22,819
Dan di sini, ia percetakan
jawapan yang betul.

390
00:17:22,819 --> 00:17:26,569
>> Jadi seperti yang anda semua boleh lihat, GDB
adalah alat yang benar-benar kuat

391
00:17:26,569 --> 00:17:29,940
apabila kita mempunyai begitu banyak kod
berlaku dan begitu banyak pembolehubah

392
00:17:29,940 --> 00:17:32,510
bahawa ia sukar untuk kita, kerana
manusia, untuk mengesan.

393
00:17:32,510 --> 00:17:35,360
Komputer, dalam GDB
penyahpepijat, mempunyai keupayaan

394
00:17:35,360 --> 00:17:37,020
untuk mengesan segala-galanya.

395
00:17:37,020 --> 00:17:40,480
Saya tahu, dalam Visionaire, anda semua mungkin
mungkin telah melanda beberapa kesalahan segmentasi

396
00:17:40,480 --> 00:17:43,150
kerana anda sedang berlari
di luar batas array anda.

397
00:17:43,150 --> 00:17:46,510
Dalam contoh Caesar, itu
apa yang saya telah dilaksanakan di sini.

398
00:17:46,510 --> 00:17:50,060
>> Jadi saya terlupa untuk memeriksa
apa yang akan berlaku jika saya

399
00:17:50,060 --> 00:17:52,510
tidak mempunyai dua hujah baris arahan.

400
00:17:52,510 --> 00:17:53,880
Saya hanya tidak dimasukkan ke dalam daftar itu.

401
00:17:53,880 --> 00:17:57,380
Dan jadi jika saya menjalankan Debug-- saya menetapkan
titik putus saya ke kanan sana.

402
00:17:57,380 --> 00:17:58,055
Saya menjalankan Debug.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> OKAY.

405
00:18:16,550 --> 00:18:17,050
Yeah.

406
00:18:17,050 --> 00:18:20,350
Jadi sebenarnya, GDB sepatutnya
telah memberitahu saya ada

407
00:18:20,350 --> 00:18:22,300
adalah satu kesalahan segmentasi sana.

408
00:18:22,300 --> 00:18:24,883
Saya tidak tahu apa yang berlaku
di sana, tetapi apabila saya berlari,

409
00:18:24,883 --> 00:18:25,590
ia telah bekerja.

410
00:18:25,590 --> 00:18:29,410
Apabila anda menjalankan baris kod melalui dan
GDB mungkin hanya tiba-tiba berhenti pada anda,

411
00:18:29,410 --> 00:18:31,540
naik dan lihat apa kesilapan merah.

412
00:18:31,540 --> 00:18:33,930
Ia akan memberitahu anda, hey, anda
mempunyai kesalahan segmentasi,

413
00:18:33,930 --> 00:18:38,550
yang bermaksud bahawa anda cuba untuk akses
ruang dalam array yang tidak wujud.

414
00:18:38,550 --> 00:18:39,050
Yeah.

415
00:18:39,050 --> 00:18:43,280
>> Jadi, dalam masalah yang akan datang
menetapkan minggu ini, anda semua

416
00:18:43,280 --> 00:18:45,600
mungkin akan mempunyai banyak
pembolehubah terapung di sekeliling.

417
00:18:45,600 --> 00:18:48,560
Anda tidak akan menjadi pasti apa
membawa makna pada titik tertentu.

418
00:18:48,560 --> 00:18:53,560
Jadi GDB benar-benar akan membantu anda dalam memikirkan
mengetahui apa yang mereka semua menyamai

419
00:18:53,560 --> 00:18:55,940
dan dapat melihat bahawa secara visual.

420
00:18:55,940 --> 00:19:01,995
Adakah sesiapa yang keliru tentang bagaimana
mana-mana yang bekerja?

421
00:19:01,995 --> 00:19:02,495
Sejuk.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
Baiklah.

424
00:19:10,620 --> 00:19:14,260
Jadi, selepas itu, kami
akan digalakkan untuk

425
00:19:14,260 --> 00:19:17,562
ke empat yang berbeza
jenis jenis untuk minggu ini.

426
00:19:17,562 --> 00:19:19,520
Berapa ramai daripada anda, pertama
sekali, sebelum kita bermula,

427
00:19:19,520 --> 00:19:23,020
telah membaca keseluruhan spec untuk pset3?

428
00:19:23,020 --> 00:19:23,824
OKAY.

429
00:19:23,824 --> 00:19:24,740
Saya bangga dengan anda semua.

430
00:19:24,740 --> 00:19:29,110
Itu seperti separuh daripada kelas, yang
adalah lebih banyak daripada masa lalu.

431
00:19:29,110 --> 00:19:33,950
>> Jadi yang hebat, kerana apabila
kita bercakap mengenai kandungan

432
00:19:33,950 --> 00:19:36,170
dalam lecture-- atau maaf,
dalam seksyen ini- saya suka

433
00:19:36,170 --> 00:19:38,210
untuk mengaitkan banyak yang
kembali kepada apa yang pset adalah

434
00:19:38,210 --> 00:19:40,210
dan bagaimana anda mahu
melaksanakan bahawa dalam pset anda.

435
00:19:40,210 --> 00:19:42,400
Jadi, jika anda datang mempunyai
membaca spec, ia akan mempunyai

436
00:19:42,400 --> 00:19:45,510
menjadi lebih mudah bagi anda untuk memahami
apa yang saya bercakap tentang apabila saya berkata,

437
00:19:45,510 --> 00:19:48,720
oh hey, ini mungkin benar-benar
Tempat yang baik untuk melaksanakan seperti ini.

438
00:19:48,720 --> 00:19:52,870
Maka orang-orang di antara kamu yang telah membaca
spec tahu bahawa, sebagai sebahagian daripada pset anda,

439
00:19:52,870 --> 00:19:54,900
anda akan perlu
menulis sejenis macam.

440
00:19:54,900 --> 00:19:58,670
Jadi ini mungkin sangat berguna
untuk banyak anda hari ini.

441
00:19:58,670 --> 00:20:01,760
>> Oleh itu, kita akan mulakan dengan,
pada dasarnya, jenis yang paling mudah

442
00:20:01,760 --> 00:20:04,580
daripada jenis, jenis pemilihan.

443
00:20:04,580 --> 00:20:06,800
Algoritma khas untuk
bagaimana kita akan pergi tentang perkara ini

444
00:20:06,800 --> 00:20:10,460
is-- David telah melalui ini semua dalam
kuliah, jadi saya dengan cepat akan bergerak bersama-sama

445
00:20:10,460 --> 00:20:13,900
sini-- asasnya, anda
mempunyai pelbagai nilai.

446
00:20:13,900 --> 00:20:17,170
Dan kemudian anda mencari
nilai terisih kecil

447
00:20:17,170 --> 00:20:20,200
dan anda menukar nilai itu dengan
nilai terisih pertama.

448
00:20:20,200 --> 00:20:22,700
Dan kemudian anda hanya terus mengulangi
dengan seluruh senarai anda.

449
00:20:22,700 --> 00:20:25,740
>> Dan di sini adalah penerangan visual
bagaimana yang akan bekerja.

450
00:20:25,740 --> 00:20:30,460
Jadi, sebagai contoh, jika kita mula
dengan pelbagai lima elemen, indeks

451
00:20:30,460 --> 00:20:35,910
0-4, dengan 3, 5, 2, 6, dan 4 nilai
diletakkan di array-- sehingga sekarang,

452
00:20:35,910 --> 00:20:38,530
kami hanya akan menganggap
bahawa mereka semua terisih

453
00:20:38,530 --> 00:20:41,130
kerana kita tidak diuji sebaliknya.

454
00:20:41,130 --> 00:20:44,130
>> Jadi bagaimana jenis pemilihan akan
kerja adalah bahawa ia akan pertama

455
00:20:44,130 --> 00:20:46,800
berjalan melalui keseluruhannya yang
array terisih.

456
00:20:46,800 --> 00:20:49,120
Ia akan memilih nilai yang paling kecil.

457
00:20:49,120 --> 00:20:51,750
Dalam kes ini, 3, betul-betul
sekarang, adalah yang paling kecil.

458
00:20:51,750 --> 00:20:52,680
Ia mendapat hingga 5.

459
00:20:52,680 --> 00:20:55,620
Nope, 5 tidak lebih besar than--
atau maaf, tidak kurang than-- 3.

460
00:20:55,620 --> 00:20:57,779
Jadi nilai minimum masih 3.

461
00:20:57,779 --> 00:20:58,695
Dan kemudian anda boleh 2.

462
00:20:58,695 --> 00:21:00,990
Komputer melihat, oh, 2 adalah kurang daripada 3.

463
00:21:00,990 --> 00:21:02,750
2 kini perlu menjadi nilai minimum.

464
00:21:02,750 --> 00:21:06,630
Dan sebagainya 2 swap dengan bahawa nilai pertama.

465
00:21:06,630 --> 00:21:10,702
>> Jadi selepas satu pas, kita memang melihat
bahawa 2 dan 3 adalah bertukar.

466
00:21:10,702 --> 00:21:13,910
Dan kita hanya akan terus melakukan
ini sekali lagi dengan seluruh array.

467
00:21:13,910 --> 00:21:17,660
Oleh itu, kita akan berjalan melalui
lepas empat indeks array.

468
00:21:17,660 --> 00:21:20,670
Kita akan melihat bahawa 3 adalah
nilai minimum yang akan datang.

469
00:21:20,670 --> 00:21:23,240
Jadi, kita akan menukar bahawa dengan 4.

470
00:21:23,240 --> 00:21:26,900
Dan kemudian kita hanya akan menyimpan
berjalan melalui, sehingga akhirnya, anda

471
00:21:26,900 --> 00:21:33,730
mendapatkan kepada pelbagai disusun di mana
2, 3, 4, 5, dan 6 semuanya disusun.

472
00:21:33,730 --> 00:21:37,530
Adakah semua orang memahami logik yang
bagaimana sebuah jenis pemilihan berfungsi?

473
00:21:37,530 --> 00:21:39,669
>> Anda hanya mempunyai beberapa jenis
daripada nilai minimum.

474
00:21:39,669 --> 00:21:41,210
Anda mengesan apa yang.

475
00:21:41,210 --> 00:21:45,170
Dan setiap kali anda mencari, anda tukar
dengan nilai pertama dalam array-- yang

476
00:21:45,170 --> 00:21:48,740
atau, tidak value-- pertama
nilai seterusnya dalam array.

477
00:21:48,740 --> 00:21:50,150
Sejuk.

478
00:21:50,150 --> 00:21:55,460
>> Jadi seperti yang anda semua jenis
melihat dari gambaran ringkas,

479
00:21:55,460 --> 00:21:58,450
kita akan pseudokod ini keluar.

480
00:21:58,450 --> 00:22:02,510
Jadi, jika anda seorang lelaki di belakang mahu
membentuk satu kumpulan, semua orang di meja

481
00:22:02,510 --> 00:22:06,170
boleh membentuk rakan kongsi sedikit, saya akan
untuk memberikan anda semua suka tiga minit

482
00:22:06,170 --> 00:22:08,190
hanya bercakap melalui
logik, dalam bahasa Inggeris,

483
00:22:08,190 --> 00:22:14,161
bagaimana kita mungkin dapat melaksanakan
pseudokod untuk menulis satu bentuk pemilihan.

484
00:22:14,161 --> 00:22:14,910
Dan ada gula-gula.

485
00:22:14,910 --> 00:22:16,118
Sila datang dan mendapatkan gula-gula.

486
00:22:16,118 --> 00:22:19,520
Jika anda berada di belakang dan anda mahu
gula-gula, saya boleh membuang gula-gula pada anda.

487
00:22:19,520 --> 00:22:22,850
Sebenarnya, tidak sejuk atasmu.

488
00:22:22,850 --> 00:22:23,552
Oh maaf.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
OKAY.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Jadi, jika kita mahu, sebagai
kelas, menulis kod pseudo

493
00:25:27,140 --> 00:25:30,466
untuk bagaimana seseorang boleh meminta
masalah ini, hanya berasa bebas.

494
00:25:30,466 --> 00:25:32,340
Saya hanya akan pergi sekitar dan,
teratur, meminta kumpulan

495
00:25:32,340 --> 00:25:35,065
untuk baris seterusnya
apa yang kita harus lakukan.

496
00:25:35,065 --> 00:25:37,840
Jadi jika anda semua ingin memulakan
off, apa perkara pertama

497
00:25:37,840 --> 00:25:40,600
yang perlu dilakukan apabila anda cuba untuk
melaksanakan satu cara untuk menyelesaikan program ini

498
00:25:40,600 --> 00:25:43,480
untuk terpilih menyusun senarai?

499
00:25:43,480 --> 00:25:46,349
Mari kita menganggap kita
mempunyai pelbagai, boleh?

500
00:25:46,349 --> 00:25:49,088
>> PENONTON: Anda ingin membuat beberapa
semacam [didengar] bahawa anda

501
00:25:49,088 --> 00:25:50,420
berjalan melalui seluruh lokasi anda.

502
00:25:50,420 --> 00:25:51,128
>> ANDI PENG: Betul.

503
00:25:51,128 --> 00:25:54,100
Jadi, anda akan mahu untuk melelar
melalui setiap ruang, bukan?

504
00:25:54,100 --> 00:26:05,490
Jadi, yang besar.

505
00:26:05,490 --> 00:26:08,600
Jika anda lelaki mahu memberi saya
berikut garis ini-- yeah, di belakang.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> PENONTON: Periksa mereka
semua untuk yang paling kecil.

508
00:26:13,290 --> 00:26:14,248
>> ANDI PENG: Ada kita pergi.

509
00:26:14,248 --> 00:26:17,438
Oleh itu, kita mahu pergi melalui dan semak untuk
melihat apa nilai minimum adalah, bukan?

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Saya akan menyingkatkan ke "min."

512
00:26:24,840 --> 00:26:27,658
Apa yang anda semua mahu lakukan selepas
anda memperolehi nilai minimum?

513
00:26:27,658 --> 00:26:28,533
>> PENONTON: [didengar]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Jadi, anda akan mahu untuk
hidupkan ia dengan yang pertama array itu,

516
00:26:33,150 --> 00:26:33,650
bukan?

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
Itulah permulaan, saya akan katakan.

519
00:26:46,850 --> 00:26:47,220
Baiklah.

520
00:26:47,220 --> 00:26:50,386
Jadi sekarang bahawa anda telah bertukar pertama
salah, apa yang anda mahu lakukan selepas itu?

521
00:26:50,386 --> 00:26:54,840
Jadi sekarang kita tahu bahawa salah satu ini di sini
mesti menjadi nilai yang paling kecil, bukan?

522
00:26:54,840 --> 00:26:58,310
Maka anda mempunyai rehat tambahan
array itulah terisih.

523
00:26:58,310 --> 00:27:01,569
Jadi apa yang anda mahu lakukan di sini, jika anda
lelaki mahu memberi saya baris seterusnya?

524
00:27:01,569 --> 00:27:04,610
PENONTON: Oleh itu, maka anda mahu untuk melelar
melalui baki array.

525
00:27:04,610 --> 00:27:05,276
ANDI PENG: Ya.

526
00:27:05,276 --> 00:27:09,857
Dan sebagainya apakah iterating melalui
jenis membayangkan kita mungkin akan perlukan?

527
00:27:09,857 --> 00:27:10,440
Apakah jenis daripada-

528
00:27:10,440 --> 00:27:12,057
>> PENONTON: Oh, pembolehubah tambahan?

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Mungkin
lain untuk gelung, bukan?

530
00:27:13,890 --> 00:27:28,914
Oleh itu, kita mungkin akan mahu
untuk melelar through-- besar.

531
00:27:28,914 --> 00:27:31,830
Dan kemudian anda akan kembali dan
mungkin menyemak minimum sekali lagi,

532
00:27:31,830 --> 00:27:32,100
bukan?

533
00:27:32,100 --> 00:27:34,975
Dan anda akan terus mengulangi
ini, kerana gelung hanya akan

534
00:27:34,975 --> 00:27:36,010
untuk terus berjalan, bukan?

535
00:27:36,010 --> 00:27:39,190
>> Jadi seperti yang anda semua boleh lihat, kami
hanya mempunyai kod pseudo umum

536
00:27:39,190 --> 00:27:41,480
bagaimana kita mahu program ini untuk melihat.

537
00:27:41,480 --> 00:27:46,646
Itekadar ini di sini, apa yang kita
biasanya perlu menulis kod kami

538
00:27:46,646 --> 00:27:49,270
jika kita mahu untuk melelar melalui
pelbagai, apa jenis struktur?

539
00:27:49,270 --> 00:27:51,030
Saya rasa Christabel
telah berkata ini sebelum ini.

540
00:27:51,030 --> 00:27:51,500
>> PENONTON: A untuk gelung.

541
00:27:51,500 --> 00:27:52,160
>> ANDI PENG: A untuk gelung?

542
00:27:52,160 --> 00:27:52,770
Tepat sekali.

543
00:27:52,770 --> 00:27:56,060
Jadi ini mungkin
akan menjadi satu untuk gelung.

544
00:27:56,060 --> 00:27:59,240
Apa yang cek di sini akan membayangkan?

545
00:27:59,240 --> 00:28:02,536
Biasanya, jika anda mahu untuk memeriksa
jika sesuatu adalah sesuatu else--

546
00:28:02,536 --> 00:28:03,270
>> PENONTON: Jika.

547
00:28:03,270 --> 00:28:06,790
>> ANDI PENG: Seorang jika, bukan?

548
00:28:06,790 --> 00:28:10,790
Dan kemudian swap di sini, kita akan
pergi lebih kemudian, kerana Daud

549
00:28:10,790 --> 00:28:12,770
pergi melalui itu dalam kuliah juga.

550
00:28:12,770 --> 00:28:14,580
Dan kemudian Itekadar kedua implies--

551
00:28:14,580 --> 00:28:15,120
>> PENONTON: Satu lagi untuk gelung.

552
00:28:15,120 --> 00:28:16,745
>> ANDI PENG: --another untuk gelung, betul-betul.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Jadi, jika kita sedang
pada ini dengan betul, kita

555
00:28:22,000 --> 00:28:24,680
dapat melihat bahawa kami mungkin
akan memerlukan bersarang untuk gelung

556
00:28:24,680 --> 00:28:28,330
dengan suatu pernyataan bersyarat di sana
dan kemudian sekeping sebenar kod yang yang

557
00:28:28,330 --> 00:28:31,360
akan menukar nilai-nilai.

558
00:28:31,360 --> 00:28:35,980
Jadi saya hanya umumnya bertulis
kod kod pseudo di sini.

559
00:28:35,980 --> 00:28:38,910
Dan kemudian kita sebenarnya akan
secara fizikal, sebagai sebuah kelas,

560
00:28:38,910 --> 00:28:40,700
cuba untuk melaksanakan hari ini.

561
00:28:40,700 --> 00:28:42,486
Mari kita kembali ke dalam IDE ini.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> Uh-oh.

564
00:28:50,230 --> 00:28:51,754
Mengapa yang tidak-- ada ia.

565
00:28:51,754 --> 00:28:52,253
OKAY.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Maaf, saya cuba untuk zum dalam sedikit lebih.

568
00:28:57,500 --> 00:28:59,310
Di sana kami pergi.

569
00:28:59,310 --> 00:29:05,060
Semua yang saya lakukan di sini saya telah membuat
program yang dikenali sebagai "pemilihan / sort.c."

570
00:29:05,060 --> 00:29:10,860
Saya telah membuat pelbagai sembilan
nilai, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Pada masa ini, yang anda boleh
melihat, mereka tidak tertib.

572
00:29:14,370 --> 00:29:17,880
n akan menjadi bilangan yang
memberitahu anda jumlah nilai

573
00:29:17,880 --> 00:29:18,920
anda ada dalam pelbagai anda.

574
00:29:18,920 --> 00:29:20,670
Dalam kes ini, kita ada sembilan nilai.

575
00:29:20,670 --> 00:29:23,760
Dan saya baru sahaja mendapat untuk gelung di sini
yang mencetak keluar array terisih.

576
00:29:23,760 --> 00:29:28,370
>> Dan pada akhirnya, saya juga telah mendapat untuk
gelung yang hanya mencetak ia keluar lagi.

577
00:29:28,370 --> 00:29:32,070
Jadi secara teori, jika program ini
berfungsi dengan betul, pada akhirnya,

578
00:29:32,070 --> 00:29:35,670
anda akan dapat melihat dicetak untuk gelung
di mana 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 semua dengan betul.

580
00:29:39,310 --> 00:29:43,410
>> Jadi kita telah mendapat pseudokod kami di sini.

581
00:29:43,410 --> 00:29:46,090
Adakah sesiapa yang mahu supaya- saya hanya
akan pergi meminta volunteers--

582
00:29:46,090 --> 00:29:49,540
beritahu saya apa yang perlu menaip jika
kita mahu, pertama, hanya melelar

583
00:29:49,540 --> 00:29:52,840
melalui permulaan array ini?

584
00:29:52,840 --> 00:29:55,204
Apa yang baris kod Saya
mungkin akan perlukan di sini?

585
00:29:55,204 --> 00:29:56,990
>> PENONTON: [didengar]

586
00:29:56,990 --> 00:29:59,010
>> ANDI PENG: Ya, sila
percuma supaya- maaf, anda

587
00:29:59,010 --> 00:30:02,318
tidak perlu berdiri rasa up--
percuma untuk menujukan suaramu sedikit.

588
00:30:02,318 --> 00:30:08,190
>> PENONTON: Untuk int i sama 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI PENG: Ya, baik.

590
00:30:10,690 --> 00:30:15,220
>> PENONTON: i adalah kurang daripada panjang array.

591
00:30:15,220 --> 00:30:19,630
>> ANDI PENG: Jadi perlu
kisah di sini, kerana kita

592
00:30:19,630 --> 00:30:23,060
tidak mempunyai fungsi yang
memberitahu kita panjang array,

593
00:30:23,060 --> 00:30:25,790
kita sudah mempunyai
nilai yang menyimpan itu.

594
00:30:25,790 --> 00:30:27,920
Betul?

595
00:30:27,920 --> 00:30:31,010
Satu lagi perkara yang perlu
dalam mind-- dalam array

596
00:30:31,010 --> 00:30:33,940
sembilan nilai, apakah indeks?

597
00:30:33,940 --> 00:30:38,720
Mari kita katakan pelbagai ini adalah 0-3.

598
00:30:38,720 --> 00:30:41,500
Anda melihat bahawa yang terakhir
indeks sebenarnya 3.

599
00:30:41,500 --> 00:30:45,530
Ia bukan 4, walaupun ada
empat nilai dalam tatasusunan.

600
00:30:45,530 --> 00:30:49,866
>> Jadi di sini, kita perlu berhati-hati
apa keadaan kita untuk panjang

601
00:30:49,866 --> 00:30:50,490
akan menjadi.

602
00:30:50,490 --> 00:30:51,948
>> PENONTON: Bukankah lebih n tolak 1?

603
00:30:51,948 --> 00:30:54,440
ANDI PENG: Ia akan
n tolak 1, betul-betul.

604
00:30:54,440 --> 00:30:57,379
Adakah ini masuk akal, mengapa
ia n tolak 1, semua orang?

605
00:30:57,379 --> 00:30:58,920
Ini kerana tatasusunan adalah sifar-diindeks.

606
00:30:58,920 --> 00:31:02,010
Mereka bermula pada 0 dan melarikan diri hingga ke n tolak 1.

607
00:31:02,010 --> 00:31:03,210
Ya, ia agak rumit.

608
00:31:03,210 --> 00:31:03,730
OKAY.

609
00:31:03,730 --> 00:31:05,929
Dan then--

610
00:31:05,929 --> 00:31:08,054
PENONTON: Isnt'1 yang
sudah dijaga walaupun,

611
00:31:08,054 --> 00:31:11,400
dengan hanya tidak mengatakan "kurang daripada atau
sama dengan "dan hanya mengatakan" kurang daripada "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: Itu satu
soalan yang benar-benar baik.

613
00:31:13,108 --> 00:31:13,630
Jadi, ya.

614
00:31:13,630 --> 00:31:17,410
Tetapi juga, cara yang kita berada
melaksanakan hak memeriksa,

615
00:31:17,410 --> 00:31:19,120
anda perlu membandingkan dua nilai.

616
00:31:19,120 --> 00:31:21,009
Jadi, anda benar-benar ingin
meninggalkan "kepada" kosong.

617
00:31:21,009 --> 00:31:23,050
Kerana jika anda membandingkan
satu ini, anda tidak akan

618
00:31:23,050 --> 00:31:25,530
mempunyai apa-apa selepas ia
untuk membandingkan, bukan?

619
00:31:25,530 --> 00:31:27,460
Yeah.

620
00:31:27,460 --> 00:31:29,297
Jadi saya ++.

621
00:31:29,297 --> 00:31:30,380
Mari kita menambah kurungan kami di.

622
00:31:30,380 --> 00:31:30,880
Alamak.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Yang besar.

625
00:31:34,710 --> 00:31:39,117
Jadi kita mempunyai permulaan
gelung luar kami.

626
00:31:39,117 --> 00:31:41,450
Jadi sekarang kita mungkin mahu
mewujudkan pemboleh ubah untuk menjaga

627
00:31:41,450 --> 00:31:43,085
mengesan nilai yang paling kecil, bukan?

628
00:31:43,085 --> 00:31:45,751
Adakah sesiapa yang mahu memberi saya
baris kod yang akan berbuat demikian?

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
Apa yang kita perlukan jika kita akan
mahu menyimpan sesuatu?

631
00:31:53,570 --> 00:31:55,047
>> Betul.

632
00:31:55,047 --> 00:31:57,630
Mungkin nama yang lebih baik untuk
akan adalah- "temp" benar-benar works--

633
00:31:57,630 --> 00:32:00,655
mungkin yang lebih tepat dinamakan akan menjadi,
jika kita mahu value-- yang paling kecil

634
00:32:00,655 --> 00:32:01,624
>> PENONTON: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI PENG: min, ada kita pergi.

636
00:32:02,790 --> 00:32:05,230
min akan menjadi baik.

637
00:32:05,230 --> 00:32:08,340
Dan sebagainya di sini, apa yang kita
mahu untuk memulakan ke?

638
00:32:08,340 --> 00:32:09,620
Ini adalah agak sukar.

639
00:32:09,620 --> 00:32:13,580
Kerana sekarang di
permulaan pelbagai ini,

640
00:32:13,580 --> 00:32:15,730
anda belum melihat apa-apa, kan?

641
00:32:15,730 --> 00:32:19,200
Jadi apa, secara automatik, jika
kita berada pada i sama dengan 0,

642
00:32:19,200 --> 00:32:22,302
apa yang kita mahu untuk memulakan
nilai minimum pertama kami ke?

643
00:32:22,302 --> 00:32:22,802
PENONTON: i.

644
00:32:22,802 --> 00:32:24,790
ANDI PENG: i, betul-betul.

645
00:32:24,790 --> 00:32:27,040
Christabel, mengapa kita mahu
untuk memulakan kepada i?

646
00:32:27,040 --> 00:32:28,510
>> PENONTON: Kerana, baik,
kita bermula dengan 0.

647
00:32:28,510 --> 00:32:31,660
Jadi kerana kita mempunyai apa-apa untuk membandingkan
kepada, sekurang-kurangnya akan berakhir menjadi 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI PENG: Tepat sekali.

649
00:32:32,451 --> 00:32:34,400
Jadi dia betul-betul betul.

650
00:32:34,400 --> 00:32:36,780
Oleh kerana kita tidak benar-benar
melihat apa-apa lagi,

651
00:32:36,780 --> 00:32:38,680
kita tidak tahu apa nilai minimum kita.

652
00:32:38,680 --> 00:32:41,960
Kami mahu hanya memulakan ia ke
i, yang, pada masa ini, adalah di sini.

653
00:32:41,960 --> 00:32:44,750
Dan seperti yang kita terus
bergerak ke bawah pelbagai ini,

654
00:32:44,750 --> 00:32:48,122
kita akan melihat bahawa, dengan setiap
pas tambahan, i kenaikan.

655
00:32:48,122 --> 00:32:49,830
Dan sebagainya pada ketika itu,
i mungkin akan

656
00:32:49,830 --> 00:32:52,329
mahu menjadi minimum,
kerana ia akan menjadi apa sahaja

657
00:32:52,329 --> 00:32:54,520
adalah permulaan array terisih.

658
00:32:54,520 --> 00:32:55,270
Sejuk.

659
00:32:55,270 --> 00:32:58,720
>> Jadi sekarang kita mahu menambah
untuk gelung di sini bahawa

660
00:32:58,720 --> 00:33:03,225
akan melelar melalui
terisih, atau seluruh pelbagai ini.

661
00:33:03,225 --> 00:33:05,808
Adakah sesiapa yang mahu memberikan saya
baris kod yang akan berbuat demikian?

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- apa yang kita perlu turun di sini?

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
Apa yang akan pergi dalam ini untuk gelung?

666
00:33:18,820 --> 00:33:19,465
Yeah.

667
00:33:19,465 --> 00:33:21,590
PENONTON: Oleh itu, kita akan mahu
mempunyai integer yang berbeza,

668
00:33:21,590 --> 00:33:25,080
kerana kita berjalan melalui yang lain
array bukannya i, jadi mungkin

669
00:33:25,080 --> 00:33:25,760
j.

670
00:33:25,760 --> 00:33:27,301
>> ANDI PENG: Ya, j bunyi yang baik kepada saya.

671
00:33:27,301 --> 00:33:27,850
Sama?

672
00:33:27,850 --> 00:33:33,930
>> PENONTON: Jadi akan i campur 1, kerana
anda bermula pada nilai yang seterusnya.

673
00:33:33,930 --> 00:33:40,395
Dan kemudian untuk end-- apa lagi, j adalah
kurang daripada n tolak 1, dan kemudian j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI PENG: Great.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> Dan kemudian di sini, kami akan mahu
untuk memeriksa untuk melihat jika keadaan kita dipenuhi,

677
00:33:52,750 --> 00:33:53,250
bukan?

678
00:33:53,250 --> 00:33:55,740
Kerana anda mahu
menukar nilai minimum

679
00:33:55,740 --> 00:33:58,700
jika ia sebenarnya lebih kecil daripada apa yang
anda membandingkannya dengan, bukan?

680
00:33:58,700 --> 00:34:01,146
Jadi apa yang kita akan mahu di sini?

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Semak untuk melihat.

683
00:34:04,897 --> 00:34:06,730
Apa jenis penyataan
kita mungkin akan

684
00:34:06,730 --> 00:34:08,389
ti mahu menggunakan jika kita
mahu untuk memeriksa sesuatu?

685
00:34:08,389 --> 00:34:09,360
>> PENONTON: An jika kenyataan.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: Seorang jika kenyataan.

687
00:34:10,485 --> 00:34:13,155
Jadi jika- dan apa yang akan menjadi
syarat kita mahu di dalam

688
00:34:13,155 --> 00:34:13,988
daripada jika kenyataan kami?

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> PENONTON: Jika nilai j
adalah kurang daripada nilai Saya--

691
00:34:22,960 --> 00:34:24,600
>> ANDI PENG: Tepat sekali.

692
00:34:24,600 --> 00:34:27,480
Jadi jika- supaya pelbagai ini dipanggil "pelbagai."

693
00:34:27,480 --> 00:34:27,980
Yang besar.

694
00:34:27,980 --> 00:34:30,465
Jadi, jika array-- apa tu?

695
00:34:30,465 --> 00:34:31,090
Cakap sekali lagi.

696
00:34:31,090 --> 00:34:39,590
>> PENONTON: Jika lokasi benar-j adalah kurang daripada
lokasi benar-i, maka kita akan mengubah min.

697
00:34:39,590 --> 00:34:41,590
Jadi min itu akan menjadi j.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI PENG: Adakah ini masuk akal?

700
00:34:47,249 --> 00:34:48,670
OKAY.

701
00:34:48,670 --> 00:34:52,929
Dan kini turun di sini, kita benar-benar
mahu melaksanakan swap, bukan?

702
00:34:52,929 --> 00:34:58,285
Jadi ingat, dalam kuliah, yang Daud, ketika
dia cuba untuk menukar the-- apa yang

703
00:34:58,285 --> 00:34:59,996
jus oren kitab itu dan milk--

704
00:34:59,996 --> 00:35:01,150
>> PENONTON: Itu adalah kasar.

705
00:35:01,150 --> 00:35:02,816
>> ANDI PENG: Ya, itu adalah jenis kasar.

706
00:35:02,816 --> 00:35:05,310
Tetapi ia adalah baik cukup
konsep menunjukkan masa.

707
00:35:05,310 --> 00:35:08,430
Jadi berfikir nilai-nilai anda di sini.

708
00:35:08,430 --> 00:35:10,794
Anda telah mendapat array
min, pelbagai i,

709
00:35:10,794 --> 00:35:12,460
atau apa sahaja yang kita sedang berusaha untuk menukar sini.

710
00:35:12,460 --> 00:35:15,310
Dan anda mungkin tidak boleh menuangkannya ke dalam
antara satu sama lain pada masa yang sama, bukan?

711
00:35:15,310 --> 00:35:17,180
Jadi apa yang kita akan
untuk perlu membuat di sini

712
00:35:17,180 --> 00:35:19,126
untuk menukar nilai-nilai yang betul?

713
00:35:19,126 --> 00:35:19,820
>> PENONTON: Pemboleh ubah sementara.

714
00:35:19,820 --> 00:35:21,370
>> ANDI PENG: Pemboleh ubah sementara.

715
00:35:21,370 --> 00:35:22,570
Jadi mari kita buat int temp.

716
00:35:22,570 --> 00:35:25,681
Lihat, ini akan menjadi yang lebih baik
masa supaya- wah, apa tu?

717
00:35:25,681 --> 00:35:26,180
OKAY.

718
00:35:26,180 --> 00:35:29,800
Jadi ini akan menjadi yang lebih baik
masa untuk menamakan "temp." berubah-ubah

719
00:35:29,800 --> 00:35:30,730
Jadi mari kita buat int temp.

720
00:35:30,730 --> 00:35:32,563
Apa yang kita akan
menetapkan temp sama ke sini?

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
PENONTON: Min?

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
ANDI PENG: Ia agak rumit.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
Ia sebenarnya tidak penting pada akhirnya.

727
00:35:44,880 --> 00:35:47,690
Tidak kira apa
perintah yang anda pilih untuk menukar dalam

728
00:35:47,690 --> 00:35:50,862
selagi anda membuat pasti anda berada
mengesan apa yang anda bertukar-tukar.

729
00:35:50,862 --> 00:35:52,250
>> PENONTON: Ia boleh menjadi lokasi benar-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI PENG: Ya, mari kita buat pelbagai-i.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
Dan kemudian apa yang baris seterusnya
kod kita mahu ada di sini?

733
00:35:59,305 --> 00:36:00,680
PENONTON: lokasi benar-i sama pelbagai-j.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI PENG: Dan akhir sekali?

736
00:36:08,070 --> 00:36:12,070
PENONTON: lokasi benar-j sama dengan lokasi-i.

737
00:36:12,070 --> 00:36:14,525
PENONTON: Atau lokasi benar-j setaraf
lokasi benar-temp-- atau, temp.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI PENG: OK.

740
00:36:19,430 --> 00:36:21,510
Jadi mari kita berjalan ini dan melihat
jika ia akan bekerja.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
Di mana yang berlaku?

743
00:36:39,335 --> 00:36:40,210
Oh, itu masalah.

744
00:36:40,210 --> 00:36:44,320
Lihat, di laluan 40, kami
cuba menggunakan pelbagai-j?

745
00:36:44,320 --> 00:36:47,022
Tetapi di mana j hanya wujud di dalam?

746
00:36:47,022 --> 00:36:48,402
>> PENONTON: Pada untuk gelung.

747
00:36:48,402 --> 00:36:49,110
ANDI PENG: Betul.

748
00:36:49,110 --> 00:36:51,730
Jadi apa yang kita akan perlu lakukan?

749
00:36:51,730 --> 00:36:53,170
>> PENONTON: Tentukan di luar the--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
PENONTON: Ya, saya rasa anda perlu
untuk menggunakan satu lagi jika kenyataan, bukan?

752
00:37:00,610 --> 00:37:05,230
Jadi seperti, jika minimum-- yang
baiklah, saya fikir.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI PENG: Guys, cuba
untuk mengambil lihat Mari

755
00:37:09,990 --> 00:37:11,270
lihat, apa yang sesuatu yang kita boleh lakukan di sini?

756
00:37:11,270 --> 00:37:11,811
>> PENONTON: OK.

757
00:37:11,811 --> 00:37:15,900
Jadi, jika minimum yang tidak sama
j-- jadi jika minimum masih Saya--

758
00:37:15,900 --> 00:37:17,570
maka kita tidak akan mempunyai untuk menukar.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI PENG: Adakah yang sama i?

761
00:37:24,712 --> 00:37:25,920
Apa yang anda ingin katakan di sini?

762
00:37:25,920 --> 00:37:30,494
>> PENONTON: Atau yeah, jika
minimum tidak sama i, yeah.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI PENG: OK.

765
00:37:40,210 --> 00:37:42,040
Baik yang menyelesaikan, jenis, masalah kita.

766
00:37:42,040 --> 00:37:47,265
Tetapi itu masih tidak menyelesaikan
masalah apa yang berlaku jika j-- sejak j

767
00:37:47,265 --> 00:37:49,890
tidak wujud di luar daripadanya dan apa
adakah anda yang kami mahu lakukan dengannya?

768
00:37:49,890 --> 00:37:50,698
Mengisytiharkan ia di luar?

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Mari kita cuba berjalan ini.

771
00:38:02,730 --> 00:38:04,435
Uh-oh.

772
00:38:04,435 --> 00:38:06,200
Semacam kita tidak berfungsi.

773
00:38:06,200 --> 00:38:10,060
>> Seperti yang anda lihat, awal kami
lokasi benar mempunyai nilai-nilai.

774
00:38:10,060 --> 00:38:14,800
Dan selepas itu ia perlu mempunyai
berada dalam 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Ia tidak berfungsi.

776
00:38:15,530 --> 00:38:16,030
Ahh.

777
00:38:16,030 --> 00:38:17,184
Apa yang kita lakukan?

778
00:38:17,184 --> 00:38:17,850
PENONTON: Debug.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI PENG: Baiklah, kita boleh cuba itu.

781
00:38:23,370 --> 00:38:25,030
Kami boleh debug.

782
00:38:25,030 --> 00:38:26,042
Zum keluar sedikit.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Mari kita menetapkan titik putus kami.

785
00:38:33,656 --> 00:38:37,280
Mari kita pergi OK like--.

786
00:38:37,280 --> 00:38:40,444
>> Demikian kerana kita sudah tahu bahawa
ayat-ayat ini, 15 hingga 22,

787
00:38:40,444 --> 00:38:43,610
sedang working-- kerana semua yang saya lakukan adalah
hanya iterating melalui dan printing--

788
00:38:43,610 --> 00:38:45,406
Saya boleh pergi ke hadapan dan skip itu.

789
00:38:45,406 --> 00:38:47,280
Mari kita mulakan di talian 25.

790
00:38:47,280 --> 00:38:48,712
Oop, biarlah saya menghilangkan itu.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> PENONTON: Jadi titik putus ini
mana debugging bermula?

793
00:38:54,057 --> 00:38:54,890
ANDI PENG: Atau berhenti.

794
00:38:54,890 --> 00:38:55,670
PENONTON: Atau berhenti.

795
00:38:55,670 --> 00:38:55,930
ANDI PENG: Ya.

796
00:38:55,930 --> 00:38:58,640
Anda boleh menetapkan beberapa titik putus dan
ia hanya boleh melompat dari satu kepada yang lain.

797
00:38:58,640 --> 00:39:01,590
Tetapi dalam kes ini kita tidak tahu
di mana kesilapan yang berlaku.

798
00:39:01,590 --> 00:39:03,780
Oleh itu, kita hanya mahu
bermula dari atas ke bawah.

799
00:39:03,780 --> 00:39:05,020
Ya.

800
00:39:05,020 --> 00:39:05,550
OKAY.

801
00:39:05,550 --> 00:39:08,460
>> Jadi garis ini di sini, kita boleh campur tangan.

802
00:39:08,460 --> 00:39:11,499
Anda boleh lihat di bawah ini,
kami mempunyai array.

803
00:39:11,499 --> 00:39:13,290
Mereka adalah nilai-nilai
yang berada di dalam array.

804
00:39:13,290 --> 00:39:16,360
Adakah anda melihat bahawa, bagaimana indeks 0, ia
sepadan dengan value-- oh,

805
00:39:16,360 --> 00:39:17,526
Saya akan cuba untuk zum masuk.

806
00:39:17,526 --> 00:39:20,650
Maaf, ia benar-benar keras
untuk see-- di pelbagai indeks 0,

807
00:39:20,650 --> 00:39:24,090
kita mempunyai nilai 4 dan
kemudian sebagainya dan sebagainya.

808
00:39:24,090 --> 00:39:25,670
Kami mempunyai pembolehubah tempatan.

809
00:39:25,670 --> 00:39:28,570
Sekarang i adalah sama dengan
0, yang kita mahu ia menjadi.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> Dan begitu mari kita melangkah.

812
00:39:33,690 --> 00:39:36,850
Minimum kami adalah sama dengan 0,
yang kita juga mahu ia menjadi.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
Dan kemudian kita masukkan kedua kami untuk
gelung, jika lokasi benar-j kurang daripada lokasi benar-i,

815
00:39:45,560 --> 00:39:46,380
yang ia tidak.

816
00:39:46,380 --> 00:39:48,130
Jadi adakah anda melihat bagaimana
yang dilangkau lebih itu?

817
00:39:48,130 --> 00:39:52,430
>> PENONTON: Jadi sekiranya jika
minimum, semua bahawa- tidak sepatutnya yang

818
00:39:52,430 --> 00:39:55,424
berada di dalam yang pertama untuk gelung?

819
00:39:55,424 --> 00:39:57,340
ANDI PENG: Tidak, kerana
anda masih mahu menguji.

820
00:39:57,340 --> 00:40:00,329
Anda mahu melakukan perbandingan setiap
masa, walaupun selepas anda menjalankan melaluinya.

821
00:40:00,329 --> 00:40:02,620
Anda tidak hanya mahu melakukannya
pada pertama lulus-melalui.

822
00:40:02,620 --> 00:40:05,240
Anda mahu melakukannya dengan
setiap laluan tambahan lagi.

823
00:40:05,240 --> 00:40:07,198
Jadi, anda mahu untuk memeriksa
keadaan anda di dalam.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Oleh itu, kita hanya akan
terus berjalan melalui sini.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Saya akan memberikan anda semua petunjuk.

828
00:40:18,420 --> 00:40:23,910
Ia mempunyai kaitan dengan hakikat bahawa apabila
anda memeriksa bersyarat anda,

829
00:40:23,910 --> 00:40:26,600
anda tidak mendaftar
indeks yang betul.

830
00:40:26,600 --> 00:40:32,510
Jadi sekarang anda memeriksa
indeks pelbagai j kurang daripada lokasi

831
00:40:32,510 --> 00:40:33,970
indeks i.

832
00:40:33,970 --> 00:40:36,580
Tetapi apa yang anda lakukan ke arah
permulaan untuk gelung?

833
00:40:36,580 --> 00:40:38,260
Adakah anda tidak menetapkan j sama dengan i?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Ya, jadi kita boleh sebenarnya
keluar penyahpepijat sini.

836
00:40:45,415 --> 00:40:47,040
Oleh itu, mari kita lihat pada kod pseudo kami.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
Bagi- kita akan
bermula dari i sama dengan 0.

839
00:40:52,580 --> 00:40:54,760
Kami akan pergi sehingga n tolak 1.

840
00:40:54,760 --> 00:40:58,040
Mari kita lihat, adakah kita mempunyai hak itu?

841
00:40:58,040 --> 00:40:59,580
Ya, itu adalah betul.

842
00:40:59,580 --> 00:41:02,080
>> Sebab itu di dalam sini, kami
akan mewujudkan nilai minimum

843
00:41:02,080 --> 00:41:03,630
dan menetapkan yang sama dengan i.

844
00:41:03,630 --> 00:41:04,950
Adakah kita berbuat demikian?

845
00:41:04,950 --> 00:41:06,270
Ya, melakukannya.

846
00:41:06,270 --> 00:41:10,430
Sekarang di dalam untuk gelung kami, kami
akan melakukan j sama i n tolak 1.

847
00:41:10,430 --> 00:41:11,950
Adakah kita berbuat demikian?

848
00:41:11,950 --> 00:41:15,540
Sesungguhnya, kita lakukan itu.

849
00:41:15,540 --> 00:41:19,922
>> Jadi bagaimanapun, apa yang kita membandingkan di sini?

850
00:41:19,922 --> 00:41:20,925
>> PENONTON: j plus 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Tepat sekali.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
Dan kemudian anda akan mahu untuk menetapkan
minimum anda sama dengan j plus 1 juga.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Jadi saya pergi melalui itu benar-benar cepat.

856
00:41:32,640 --> 00:41:36,190
Adakah anda semua faham
mengapa ia j plus 1?

857
00:41:36,190 --> 00:41:36,890
OKAY.

858
00:41:36,890 --> 00:41:40,700
>> Jadi dalam lokasi anda, dalam
pas pertama anda melalui,

859
00:41:40,700 --> 00:41:44,850
anda untuk gelung, untuk int
i sama dengan 0, mari kita

860
00:41:44,850 --> 00:41:46,740
menganggap ini tidak berubah lagi.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Kami mempunyai pelbagai, benar-benar,
hanya empat unsur terisih, bukan?

863
00:41:56,760 --> 00:42:00,760
Oleh itu, kita mahu untuk memulakan i sama dengan 0.

864
00:42:00,760 --> 00:42:03,650
Dan saya akan hanya
berjalan melalui gelung ini.

865
00:42:03,650 --> 00:42:08,560
Dan sebagainya dalam laluan pertama, kita akan
untuk memulakan pembolehubah yang dipanggil "min"

866
00:42:08,560 --> 00:42:11,245
yang juga sama dengan i, kerana
kita tidak mempunyai nilai minimum.

867
00:42:11,245 --> 00:42:12,870
Jadi itu kini sama dengan 0 juga.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
Dan kemudian kita akan melalui.

870
00:42:17,640 --> 00:42:19,270
Dan kita mahu untuk melelar lagi.

871
00:42:19,270 --> 00:42:22,900
Sekarang kita telah dapati apa yang minimum kami
adalah, kita mahu untuk melelar melalui

872
00:42:22,900 --> 00:42:25,190
sekali lagi untuk melihat jika ia membandingkan, bukan?

873
00:42:25,190 --> 00:42:40,440
Jadi j, di sini, akan
untuk sama i, yang adalah 0.

874
00:42:40,440 --> 00:42:46,320
Dan kemudian jika pelbagai j plus i, yang
adalah satu yang akan datang ke atas, sebagai kurang

875
00:42:46,320 --> 00:42:49,270
daripada apa yang minimum semasa anda
nilai adalah, anda mahu untuk menukar.

876
00:42:49,270 --> 00:42:56,850
>> Jadi mari kita hanya mengatakan kami telah
mendapat, seperti, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Buat masa ini, i adalah sama dengan
0 dan j adalah sama dengan 0.

878
00:43:01,610 --> 00:43:05,210
Dan itulah nilai minimum kami.

879
00:43:05,210 --> 00:43:09,950
Jika lokasi benar-j plus Saya-- supaya jika yang
itulah selepas yang kita sedang melihat

880
00:43:09,950 --> 00:43:13,450
adalah lebih besar daripada yang di hadapannya,
ia akan menjadi minimum.

881
00:43:13,450 --> 00:43:18,120
>> Jadi di sini kita melihat bahawa 5
tidak kurang daripada itu.

882
00:43:18,120 --> 00:43:19,730
Jadi ia akan tidak 5.

883
00:43:19,730 --> 00:43:23,580
Kita lihat bahawa 1 adalah kurang daripada 2, bukan?

884
00:43:23,580 --> 00:43:32,970
Jadi sekarang kita tahu bahawa kita adalah minimum
akan menjadi nilai indeks pada 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Ya?

886
00:43:34,030 --> 00:43:39,170
Dan kemudian apabila anda turun di sini,
anda boleh menukar nilai yang betul.

887
00:43:39,170 --> 00:43:42,610
>> Oleh itu, apabila kamu telah hanya mempunyai j
sebelum ini, anda tidak melihat apa-apa yang

888
00:43:42,610 --> 00:43:43,260
selepas itu.

889
00:43:43,260 --> 00:43:44,520
Anda telah melihat
nilai sama, yang

890
00:43:44,520 --> 00:43:46,290
sebabnya ia hanya tidak melakukan apa-apa.

891
00:43:46,290 --> 00:43:49,721
Adakah ini masuk akal untuk semua orang,
mengapa kita memerlukan bahawa campur 1 di sana?

892
00:43:49,721 --> 00:43:50,220
OKAY.

893
00:43:50,220 --> 00:43:53,345
Sekarang mari kita berjalan melalui untuk membuat
memastikan seluruh kod adalah betul.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Mengapa yang berlaku?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ah, ia adalah min di sini.

898
00:44:16,364 --> 00:44:17,780
Kami membandingkan nilai yang salah.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Oh tidak.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Oh yeah, turun di sini kita
bertukar-tukar nilai yang salah juga.

903
00:44:33,482 --> 00:44:34,940
Oleh kerana kita telah melihat i dan j.

904
00:44:34,940 --> 00:44:36,440
Mereka adalah orang-orang kita telah memeriksa.

905
00:44:36,440 --> 00:44:39,160
Kami benar-benar mahu menukar
minimum, minimum semasa,

906
00:44:39,160 --> 00:44:40,550
dengan apa sahaja yang seseorang di luar itu.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
Dan seperti yang anda semua boleh melihat ke bawah
di sini, kami mempunyai pelbagai disusun.

909
00:45:05,402 --> 00:45:07,110
Ia hanya mempunyai kaitan dengan
hakikat bahawa apabila

910
00:45:07,110 --> 00:45:09,350
kita telah memeriksa
nilai yang kita telah membandingkan,

911
00:45:09,350 --> 00:45:11,226
kami tidak melihat nilai-nilai yang betul.

912
00:45:11,226 --> 00:45:13,850
Kita telah melihat satu yang sama
di sini, tidak sebenarnya bertukar-tukar ia.

913
00:45:13,850 --> 00:45:17,135
Anda perlu melihat yang seterusnya
kepadanya dan kemudian anda boleh menukar.

914
00:45:17,135 --> 00:45:19,260
Jadi itulah yang adalah jenis
bugging kod kami sebelum ini.

915
00:45:19,260 --> 00:45:22,460
Dan apa yang saya lakukan di sini adalah segala-galanya
penyahpepijat boleh dilakukan untuk anda

916
00:45:22,460 --> 00:45:23,810
Saya hanya melakukannya pada
kapal, kerana lebih mudah

917
00:45:23,810 --> 00:45:26,320
untuk melihat dan bukannya cuba
untuk mengezum masuk pada penyahpepijat.

918
00:45:26,320 --> 00:45:29,391
Adakah ini masuk akal untuk semua orang?

919
00:45:29,391 --> 00:45:29,890
Sejuk.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Baiklah.

922
00:45:35,410 --> 00:45:41,070
Kami boleh bergerak untuk bercakap tentang
notasi asimptot, yang

923
00:45:41,070 --> 00:45:44,580
hanya cara mewah untuk mengatakan yang
runtimes semua macam ini.

924
00:45:44,580 --> 00:45:47,650
Jadi saya tahu Daud, dalam kuliah,
menyentuh runtimes.

925
00:45:47,650 --> 00:45:52,124
Dan dia pergi melalui seluruh formula
bagaimana untuk mengira runtimes.

926
00:45:52,124 --> 00:45:53,040
Tidak perlu risau tentang itu.

927
00:45:53,040 --> 00:45:54,660
Jika anda benar-benar ingin tahu
bagaimana yang bekerja,

928
00:45:54,660 --> 00:45:55,810
berasa bebas untuk bercakap dengan saya selepas seksyen.

929
00:45:55,810 --> 00:45:57,560
Kita boleh berjalan melalui
formula bersama-sama.

930
00:45:57,560 --> 00:46:00,689
Tetapi semua anda semua mempunyai untuk benar-benar
tahu ialah n kuasa lebih 2

931
00:46:00,689 --> 00:46:01,980
adalah perkara yang sama seperti n kuasa dua.

932
00:46:01,980 --> 00:46:04,710
Oleh kerana bilangan yang terbesar,
eksponen, tumbuh yang paling.

933
00:46:04,710 --> 00:46:06,590
Dan sebagainya untuk tujuan kita,
semua kita mengambil berat tentang

934
00:46:06,590 --> 00:46:09,470
ialah bilangan gergasi yang semakin berkembang.

935
00:46:09,470 --> 00:46:13,340
>> Jadi apa kes yang terbaik
runtime daripada jenis pemilihan?

936
00:46:13,340 --> 00:46:15,830
Jika anda akan mempunyai
untuk melelar melalui senarai

937
00:46:15,830 --> 00:46:18,712
dan kemudian melelar melalui
yang lain dalam senarai itu,

938
00:46:18,712 --> 00:46:20,420
berapa kali yang
anda akan mungkin,

939
00:46:20,420 --> 00:46:24,612
dalam case-- yang paling teruk dalam
kes terbaik, sorry-- berjalan melalui?

940
00:46:24,612 --> 00:46:27,070
Mungkin soalan yang lebih baik adalah
bertanya, apakah kes yang paling teruk

941
00:46:27,070 --> 00:46:28,153
runtime seumpama pemilihan.

942
00:46:28,153 --> 00:46:29,366
PENONTON: n kuasa dua.

943
00:46:29,366 --> 00:46:30,740
ANDI PENG: Ia n kuasa, betul.

944
00:46:30,740 --> 00:46:36,986
Jadi cara yang mudah untuk berfikir ini adalah seperti,
bila-bila masa anda mempunyai dua bersarang untuk gelung,

945
00:46:36,986 --> 00:46:38,110
ia akan dapat n kuasa dua.

946
00:46:38,110 --> 00:46:40,386
Kerana bukan sahaja anda
berjalan melalui sekali lagi,

947
00:46:40,386 --> 00:46:42,260
anda perlu kembali
dan berlari melaluinya

948
00:46:42,260 --> 00:46:44,980
sekali lagi dalam untuk setiap nilai.

949
00:46:44,980 --> 00:46:48,640
Jadi, dalam kes itu, anda menjalankan n
kali n kuasa, yang is-- maaf,

950
00:46:48,640 --> 00:46:50,505
n kali n, yang bersamaan n kuasa dua.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> Dan jenis juga sedikit
unik dalam erti kata

953
00:46:56,360 --> 00:46:59,774
bahawa ia tidak kira jika ini
nilai-nilai yang sudah teratur.

954
00:46:59,774 --> 00:47:01,440
Ia masih akan berjalan melalui anyways.

955
00:47:01,440 --> 00:47:03,872
Mari kita katakan ini adalah 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Tidak kira sama ada atau tidak ia adalah pada
perintah, ia masih akan berlari melalui

957
00:47:07,080 --> 00:47:08,620
dan masih diperiksa nilai minimum.

958
00:47:08,620 --> 00:47:10,100
Ia akan menjadikan
Bilangan yang sama cek

959
00:47:10,100 --> 00:47:12,780
setiap kali, walaupun ia
sebenarnya tidak menyentuh apa-apa.

960
00:47:12,780 --> 00:47:16,940
>> Jadi, dalam kes seperti itu, yang terbaik dan paling teruk
runtimes sebenarnya setara.

961
00:47:16,940 --> 00:47:19,160
Jadi runtime yang dijangka
daripada jenis pemilihan,

962
00:47:19,160 --> 00:47:23,790
mana kita menetapkan dengan simbol
theta, theta, dalam kes ini,

963
00:47:23,790 --> 00:47:24,790
juga akan n kuasa dua.

964
00:47:24,790 --> 00:47:26,480
Ketiga-tiga akan n kuasa dua.

965
00:47:26,480 --> 00:47:29,653
Adakah semua orang jelas mengapa
masa pengeluaran adalah n kuasa?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Baiklah.

968
00:47:33,980 --> 00:47:39,120
Jadi, saya hanya akan cepat berjalan
melalui seluruh macam.

969
00:47:39,120 --> 00:47:41,137
Algoritma bagi
gelembung sort-- ingat,

970
00:47:41,137 --> 00:47:43,220
ini adalah yang pertama
Daud pergi ke sana dalam kuliah.

971
00:47:43,220 --> 00:47:46,000
Pada asasnya, anda langkah
melalui seluruh senarai

972
00:47:46,000 --> 00:47:48,950
dan anda swap-- anda hanya
membandingkan dua pada satu masa.

973
00:47:48,950 --> 00:47:51,350
Dan jika seseorang yang lebih besar,
daripada anda hanya menukar mereka.

974
00:47:51,350 --> 00:47:53,590
Jadi, jika ini adalah lebih besar, anda akan menukar.

975
00:47:53,590 --> 00:47:56,180
Saya ada rasmi di sini.

976
00:47:56,180 --> 00:47:59,100
>> Jadi mari kita hanya mengatakan anda mempunyai 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Anda akan membandingkan 8 dan 6.

978
00:48:00,571 --> 00:48:01,570
Anda akan perlu untuk menukar mereka.

979
00:48:01,570 --> 00:48:02,610
Anda akan membandingkan 8 dan 4.

980
00:48:02,610 --> 00:48:03,609
Anda akan perlu untuk menukar mereka.

981
00:48:03,609 --> 00:48:07,000
Jika anda perlu menukar 8 dan
2, menukar mereka juga.

982
00:48:07,000 --> 00:48:10,760
Jadi dalam apa-apa segi, yang anda lihat,
dimainkan dalam tempoh masa yang panjang,

983
00:48:10,760 --> 00:48:13,730
bagaimana jenis nilai-nilai yang gelembung untuk
hujung, yang adalah mengapa kita panggil

984
00:48:13,730 --> 00:48:15,320
semacam gelembung.

985
00:48:15,320 --> 00:48:19,950
>> Kami hanya akan berjalan melalui sekali lagi pada
pas kedua kami, dan pas ketiga kami,

986
00:48:19,950 --> 00:48:21,150
dan pas keempat kami.

987
00:48:21,150 --> 00:48:25,820
Pada dasarnya, gelembung semacam hanya berjalan
sehingga anda tidak membuat apa-apa lagi swap.

988
00:48:25,820 --> 00:48:31,109
Jadi dalam erti kata itu, ini adalah hanya
yang pseudokod umum untuk itu.

989
00:48:31,109 --> 00:48:32,650
Jangan bimbang, ini semua akan berada dalam talian.

990
00:48:32,650 --> 00:48:34,990
Kami tidak mempunyai untuk benar-benar pergi ke ini.

991
00:48:34,990 --> 00:48:38,134
>> Kami hanya memulakan kaunter
pembolehubah yang bermula pada 0.

992
00:48:38,134 --> 00:48:39,800
Dan kita melelar melalui pelbagai keseluruhan.

993
00:48:39,800 --> 00:48:43,420
Dan jika satu nilai is-- jika ini
nilai adalah lebih besar daripada nilai itu,

994
00:48:43,420 --> 00:48:44,610
anda akan menukar mereka.

995
00:48:44,610 --> 00:48:46,860
Dan kemudian anda hanya
akan terus pergi.

996
00:48:46,860 --> 00:48:47,970
Dan anda akan dapat dihitung.

997
00:48:47,970 --> 00:48:50,845
Dan anda hanya akan terus melakukan
ini manakala kaunter adalah lebih besar

998
00:48:50,845 --> 00:48:53,345
daripada 0, yang bermaksud bahawa
setiap kali anda mempunyai untuk menukar,

999
00:48:53,345 --> 00:48:55,220
anda tahu anda mahu pergi
belakang dan semak sekali lagi.

1000
00:48:55,220 --> 00:48:59,510
Anda mahu menyimpan semakan sehingga anda tahu
bahawa anda tidak perlu untuk menukar lagi.

1001
00:48:59,510 --> 00:49:05,570
>> Jadi apa yang adalah yang terbaik dan paling teruk
kes runtimes untuk jenis gelembung?

1002
00:49:05,570 --> 00:49:09,300
Dan hint-- ini sebenarnya berbeza
dari jenis pemilihan dalam erti kata

1003
00:49:09,300 --> 00:49:11,810
bahawa kedua-dua jawapan tidak sama.

1004
00:49:11,810 --> 00:49:14,709
Fikirkan tentang apa yang akan berlaku dalam
kes jika ia sudah disusun.

1005
00:49:14,709 --> 00:49:16,500
Dan berfikir tentang apa
yang akan berlaku jika ia

1006
00:49:16,500 --> 00:49:18,372
dalam kes di mana ia tidak disusun.

1007
00:49:18,372 --> 00:49:20,580
Dan anda jenis boleh menjalankan
melalui mengapa yang berlaku.

1008
00:49:20,580 --> 00:49:22,954
Saya akan memberikan anda semua, seperti, 30
saat untuk berfikir tentang itu.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> OKAY.

1011
00:49:53,540 --> 00:49:57,462
Adakah sesiapa yang mempunyai meneka apa yang
kes terburuk runtime semacam gelembung?

1012
00:49:57,462 --> 00:49:57,962
Yeah.

1013
00:49:57,962 --> 00:50:07,810
>> PENONTON: ia akan menjadi, seperti, n kali
n tolak 1 atau sesuatu seperti itu?

1014
00:50:07,810 --> 00:50:10,650
Seperti, setiap kali ia berjalan,
ia hanya, seperti, satu swap kurang

1015
00:50:10,650 --> 00:50:10,960
bahawa apa sahaja yang ia adalah.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI PENG: Ya, jadi
anda benar-benar betul.

1017
00:50:12,668 --> 00:50:15,940
Dan ini adalah satu kes di mana anda
jawapan sebenarnya lebih kompleks

1018
00:50:15,940 --> 00:50:17,240
daripada apa yang kita perlu memberi.

1019
00:50:17,240 --> 00:50:19,772
Jadi ia akan run-- Saya
akan memadamkan semua ini di sini.

1020
00:50:19,772 --> 00:50:20,480
Adakah semua orang yang baik?

1021
00:50:20,480 --> 00:50:21,869
Bolehkah saya memadam ini?

1022
00:50:21,869 --> 00:50:22,368
OKAY.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Anda akan berjalan melalui n
kali kali pertama, bukan?

1025
00:50:30,320 --> 00:50:33,200
Dan mereka akan berjalan melalui
n tolak 1 kali kedua, bukan?

1026
00:50:33,200 --> 00:50:37,130
Dan kemudian anda akan menyimpan
pergi, n saya 2, dan sebagainya.

1027
00:50:37,130 --> 00:50:40,210
David melakukan ini di dalam satu ceramah, di mana,
jika anda tambah semua nilai-nilai,

1028
00:50:40,210 --> 00:50:48,080
anda mendapat sesuatu yang like-- yeah--
lebih 2, yang pada dasarnya hanya mengurangkan

1029
00:50:48,080 --> 00:50:49,784
turun ke n kuasa dua.

1030
00:50:49,784 --> 00:50:51,700
Anda akan mendapat
pecahan pelik di sana.

1031
00:50:51,700 --> 00:50:53,892
Dan sebagainya hanya tahu bahawa
n kuasa dua sentiasa

1032
00:50:53,892 --> 00:50:55,350
diberi keutamaan berbanding pecahan tersebut.

1033
00:50:55,350 --> 00:50:58,450
Dan jadi dalam kes ini, yang paling teruk
runtime akan n kuasa dua.

1034
00:50:58,450 --> 00:51:00,210
Jika ia ada turun
perintah, berfikir, anda

1035
00:51:00,210 --> 00:51:02,530
perlu membuat pertukaran setiap kali.

1036
00:51:02,530 --> 00:51:05,170
>> Apa yang akan menjadi, berpotensi,
mana yang terbaik runtime?

1037
00:51:05,170 --> 00:51:08,580
Mari kita katakan, jika senarai itu sudah
teratur, apa yang akan runtime menjadi?

1038
00:51:08,580 --> 00:51:09,565
>> PENONTON: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI PENG: Ia n, betul-betul.

1040
00:51:10,690 --> 00:51:11,600
Dan mengapa ia n?

1041
00:51:11,600 --> 00:51:13,850
PENONTON: Kerana anda hanya
perlu menyemak pada setiap sekali.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Tepat sekali.

1043
00:51:14,770 --> 00:51:17,150
Jadi, dalam masa jalan yang terbaik,
jika senarai ini sudah

1044
00:51:17,150 --> 00:51:20,270
sorted-- katakan 1, 2, 3, 4-- anda
hanya akan melalui, anda akan memeriksa,

1045
00:51:20,270 --> 00:51:21,720
anda akan melihat, oh, mereka semua berjalan baik.

1046
00:51:21,720 --> 00:51:22,636
Saya tidak mempunyai untuk menukar.

1047
00:51:22,636 --> 00:51:23,370
Aku selesai.

1048
00:51:23,370 --> 00:51:26,500
Jadi, dalam kes itu, ia hanya n
atau bilangan langkah anda hanya

1049
00:51:26,500 --> 00:51:29,870
terpaksa memeriksa dalam senarai pertama.

1050
00:51:29,870 --> 00:51:33,990
>> Dan selepas itu, kita kini melanda
jenis kemasukan, di mana

1051
00:51:33,990 --> 00:51:39,260
algoritma pada dasarnya untuk jurang
ke dalam bahagian yang disusun dan terisih.

1052
00:51:39,260 --> 00:51:42,810
Dan kemudian satu demi satu,
nilai-nilai yang terisih

1053
00:51:42,810 --> 00:51:46,880
dimasukkan ke dalam yang sesuai mereka
jawatan di awal senarai.

1054
00:51:46,880 --> 00:51:52,120
>> Jadi, sebagai contoh, kita mempunyai
senarai 3, 5, 2, 6, 4 lagi.

1055
00:51:52,120 --> 00:51:54,750
Kita tahu bahawa ia kini
Unsorted kerana kita baru sahaja

1056
00:51:54,750 --> 00:51:57,030
mula melihat ia.

1057
00:51:57,030 --> 00:52:00,610
Kita lihat dan kita tahu bahawa
nilai pertama disusun, bukan?

1058
00:52:00,610 --> 00:52:04,190
Jika anda hanya melihat pelbagai
saiz satu, anda tahu bahawa ia disusun.

1059
00:52:04,190 --> 00:52:08,230
>> Sebab itu kita tahu bahawa
empat yang terisih.

1060
00:52:08,230 --> 00:52:10,980
Kita melalui dan kita melihat nilai itu.

1061
00:52:10,980 --> 00:52:11,730
Mari kita kembali.

1062
00:52:11,730 --> 00:52:13,130
Melihat bahawa nilai 5?

1063
00:52:13,130 --> 00:52:14,110
Kami mengambil melihat pada ia.

1064
00:52:14,110 --> 00:52:15,204
Kami membandingkannya dengan 3.

1065
00:52:15,204 --> 00:52:17,870
Kita tahu bahawa itu lebih besar daripada
3, jadi kita tahu bahawa yang yang disusun.

1066
00:52:17,870 --> 00:52:22,940
Oleh itu, kita kini tahu bahawa kedua-dua pertama
disusun dan tiga lepas tidak.

1067
00:52:22,940 --> 00:52:24,270
>> Kita lihat pada 2.

1068
00:52:24,270 --> 00:52:25,720
Kami periksa dengan 5.

1069
00:52:25,720 --> 00:52:26,700
Adakah kurang daripada 5?

1070
00:52:26,700 --> 00:52:27,240
Bukan.

1071
00:52:27,240 --> 00:52:29,510
Oleh itu, kita perlu terus melihat ke bawah.

1072
00:52:29,510 --> 00:52:30,940
Kemudian anda menyemak 2 luar 3.

1073
00:52:30,940 --> 00:52:31,850
Adakah kurang daripada?

1074
00:52:31,850 --> 00:52:32,350
No.

1075
00:52:32,350 --> 00:52:35,430
Jadi, anda tahu yang 2 perlu dimasukkan
ke hadapan dan 3 dan 5

1076
00:52:35,430 --> 00:52:38,200
kedua-duanya mempunyai peluang untuk diketengahkan.

1077
00:52:38,200 --> 00:52:42,190
Adakah ini sekali lagi dengan 6 dan 4.

1078
00:52:42,190 --> 00:52:48,962
Dan kita hanya terus mendaftar pada dasarnya,
di mana kita hanya menyemak, cek, cek.

1079
00:52:48,962 --> 00:52:51,170
Dan sehingga ia di pihak yang benar
kedudukan, kita jenis hanya

1080
00:52:51,170 --> 00:52:54,890
masukkannya ke dalam kedudukan yang betul,
yang mana nama asalnya.

1081
00:52:54,890 --> 00:52:59,830
>> Jadi itu hanya algoritma,
pseudokod per se, jenis,

1082
00:52:59,830 --> 00:53:04,990
bagaimana kita akan melaksanakan
satu jenis kemasukan.

1083
00:53:04,990 --> 00:53:05,954
Pseudokod ada di sini.

1084
00:53:05,954 --> 00:53:06,620
Ia adalah semua dalam talian.

1085
00:53:06,620 --> 00:53:10,720
Jangan bimbang jika anda semua
cuba untuk menyalin ini ke bawah.

1086
00:53:10,720 --> 00:53:14,500
Jadi sekali lagi, sama question-- apa
akan menjadi yang terbaik dan paling teruk runtimes

1087
00:53:14,500 --> 00:53:16,120
untuk jenis kemasukan?

1088
00:53:16,120 --> 00:53:17,750
Ia hampir sama dengan soalan yang terakhir.

1089
00:53:17,750 --> 00:53:20,479
Saya akan memberikan anda semua, seperti, 30
saat untuk berfikir tentang perkara ini juga.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> OK Adakah sesiapa yang mahu
memberi saya masa jalan yang paling teruk?

1092
00:53:50,071 --> 00:53:50,570
Yeah.

1093
00:53:50,570 --> 00:53:51,490
>> PENONTON: n kuasa dua.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI PENG: Ia n kuasa dua.

1095
00:53:52,573 --> 00:53:53,730
Dan mengapa ia n kuasa?

1096
00:53:53,730 --> 00:53:57,562
>> PENONTON: Kerana dalam
secara terbalik, anda perlu

1097
00:53:57,562 --> 00:54:02,619
melalui n kali n, yang is--

1098
00:54:02,619 --> 00:54:03,660
ANDI PENG: Ya, betul-betul.

1099
00:54:03,660 --> 00:54:06,610
Perkara Jadi sama seperti dalam bentuk gelembung.

1100
00:54:06,610 --> 00:54:08,720
Jika senarai ini adalah dalam
urutan, anda

1101
00:54:08,720 --> 00:54:11,240
akan mempunyai untuk memeriksa sekali pertama.

1102
00:54:11,240 --> 00:54:13,470
Dan kemudian dengan setiap
nilai tambahan, anda

1103
00:54:13,470 --> 00:54:16,390
akan mempunyai untuk memeriksa terhadap
setiap nilai tunggal, bukan?

1104
00:54:16,390 --> 00:54:20,290
Dan sebagainya sama sekali, anda akan membuat
yang kali n pas lain n lulus, yang

1105
00:54:20,290 --> 00:54:21,750
adalah n kuasa dua.

1106
00:54:21,750 --> 00:54:22,860
Bagaimana pula dengan kes ini?

1107
00:54:22,860 --> 00:54:24,360
Yeah.

1108
00:54:24,360 --> 00:54:28,840
>> PENONTON: n tolak 1, kerana
Yang pertama sudah kuasa dua.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI PENG: Jadi, dekat.

1110
00:54:30,270 --> 00:54:31,850
Jawapannya adalah sebenarnya n.

1111
00:54:31,850 --> 00:54:37,189
Kerana manakala yang pertama adalah
disusun, ia mungkin tidak actually-- ia

1112
00:54:37,189 --> 00:54:38,980
kita hanya lucked keluar,
contoh tersebut, yang 2

1113
00:54:38,980 --> 00:54:40,930
berlaku untuk menjadi nombor yang paling kecil.

1114
00:54:40,930 --> 00:54:43,680
Tetapi itu tidak akan sentiasa menjadi kes itu.

1115
00:54:43,680 --> 00:54:48,040
Jika 2 sudah disusun pada mulanya
tetapi anda kelihatan dan ada 1 di sini,

1116
00:54:48,040 --> 00:54:49,144
1 akan bertemu ia.

1117
00:54:49,144 --> 00:54:51,060
Dan ia akan berakhir
sehingga yang terserempak anyways.

1118
00:54:51,060 --> 00:54:56,250
>> Jadi dalam kes senario yang terbaik,
ia sebenarnya hanya akan menjadi n.

1119
00:54:56,250 --> 00:54:59,090
Jika anda mempunyai 1, 2, 3,
4, 5, 6, 7, 8, anda

1120
00:54:59,090 --> 00:55:00,940
akan berjalan melalui
bahawa seluruh senarai sekali

1121
00:55:00,940 --> 00:55:03,430
untuk memeriksa untuk melihat jika kuatir.

1122
00:55:03,430 --> 00:55:07,390
Adakah semua orang jelas mengenai berjalan
kali pemilihan juga?

1123
00:55:07,390 --> 00:55:09,960
Saya tahu saya akan melalui
ini benar-benar cepat.

1124
00:55:09,960 --> 00:55:13,330
Tetapi hanya tahu bahawa jika anda tahu
konsep umum, anda perlu baik.

1125
00:55:13,330 --> 00:55:16,070
OKAY.

1126
00:55:16,070 --> 00:55:19,790
Jadi saya hanya akan memberikan anda semua mungkin, seperti,
satu minit untuk bercakap dengan jiran-jiran anda

1127
00:55:19,790 --> 00:55:21,890
kepada apa yang hanya beberapa
daripada perbezaan utama

1128
00:55:21,890 --> 00:55:23,540
antara jenis kejayaannya.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Kami akan pergi tidak lama lagi.

1131
00:56:25,570 --> 00:56:26,444
PENONTON: Oh, OK.

1132
00:56:26,444 --> 00:56:27,320
ANDI PENG: Ya.

1133
00:56:27,320 --> 00:56:28,380
OKAY.

1134
00:56:28,380 --> 00:56:33,420
Cool, mari kita bergabung semula sebagai kelas.

1135
00:56:33,420 --> 00:56:34,330
OKAY.

1136
00:56:34,330 --> 00:56:37,579
Jadi ini adalah jenis yang
soalan terbuka dalam erti kata

1137
00:56:37,579 --> 00:56:39,120
bahawa ada banyak jawapan kepada mereka.

1138
00:56:39,120 --> 00:56:40,746
Dan kita akan pergi ke beberapa daripada mereka secara ringkas.

1139
00:56:40,746 --> 00:56:43,411
Saya hanya mahu untuk mendapatkan anda semua
berfikir tentang apa yang dibezakan

1140
00:56:43,411 --> 00:56:44,530
ketiga-tiga jenis kejayaannya.

1141
00:56:44,530 --> 00:56:47,440
Dan aku mendengar, juga, yang besar
question-- apakah bergabung jenis lakukan?

1142
00:56:47,440 --> 00:56:50,110
Soalan yang besar, kerana itulah
apa yang kita meliputi akan datang.

1143
00:56:50,110 --> 00:56:52,850
>> Jadi bergabung apapun adalah
satu jenis yang berfungsi

1144
00:56:52,850 --> 00:56:56,100
sangat berbeza daripada jenis lain.

1145
00:56:56,100 --> 00:56:58,180
Seperti yang anda semua boleh see--
Nabi Daud melakukan demo yang

1146
00:56:58,180 --> 00:57:01,130
di mana beliau mempunyai semua sejuk
bunyi melihat bagaimana bergabung

1147
00:57:01,130 --> 00:57:04,010
semacam berlari, seperti, tak terhingga
lebih cepat daripada dua jenis yang lain?

1148
00:57:04,010 --> 00:57:04,510
OKAY.

1149
00:57:04,510 --> 00:57:07,580
Jadi itu kerana merge
semacam melaksanakan jurang yang

1150
00:57:07,580 --> 00:57:11,020
dan menakluk konsep yang kami telah
bercakap tentang banyak dalam kuliah.

1151
00:57:11,020 --> 00:57:14,550
Dalam pengertian itu yang kita suka bekerja
lebih bijak, bukan lebih keras, apabila anda membahagikan

1152
00:57:14,550 --> 00:57:18,120
dan menakluk masalah, dan memecahkan mereka
ke bawah, dan kemudian meletakkan mereka bersama-sama,

1153
00:57:18,120 --> 00:57:19,930
yang baik-baik selalu berlaku.

1154
00:57:19,930 --> 00:57:21,960
>> Jadi cara yang bergabung
jenis dasarnya berfungsi

1155
00:57:21,960 --> 00:57:24,660
ialah ia membahagikan satu
lokasi terisih pada separuh.

1156
00:57:24,660 --> 00:57:26,500
Dan kemudian ia mendapat dua bahagian tatasusunan.

1157
00:57:26,500 --> 00:57:28,220
Dan ia hanya menyusun kedua-dua bahagian.

1158
00:57:28,220 --> 00:57:31,750
Ia hanya menyimpan membahagikan dua, dalam
separuh, pada separuh sehingga semuanya disusun

1159
00:57:31,750 --> 00:57:33,680
dan kemudian secara rekursif
meletakkan semua bersama-sama.

1160
00:57:33,680 --> 00:57:36,550
>> Jadi, itu benar-benar abstrak.

1161
00:57:36,550 --> 00:57:38,750
Jadi ini adalah hanya sedikit kod pseudo.

1162
00:57:38,750 --> 00:57:41,040
Adakah ini masuk akal dalam
cara ia berjalan?

1163
00:57:41,040 --> 00:57:43,870
Jadi mari kita hanya mengatakan anda mempunyai yang
pelbagai n unsur, bukan?

1164
00:57:43,870 --> 00:57:45,450
Jika n adalah kurang daripada 2, anda boleh kembali.

1165
00:57:45,450 --> 00:57:49,040
Kerana anda tahu bahawa jika ada
hanya satu perkara, ia mesti disusun.

1166
00:57:49,040 --> 00:57:52,600
Lain, anda menyusun separuh kiri,
dan kemudian anda menyusun separuh yang betul,

1167
00:57:52,600 --> 00:57:54,140
dan kemudian anda bergabung.

1168
00:57:54,140 --> 00:57:56,979
>> Oleh itu, sambil yang kelihatan benar-benar mudah,
pada hakikatnya, berfikir tentang ia

1169
00:57:56,979 --> 00:58:00,270
jenis sukar. Kerana anda seperti,
baik, itu adalah jenis yang berjalan pada dirinya.

1170
00:58:00,270 --> 00:58:00,769
Betul?

1171
00:58:00,769 --> 00:58:02,430
Ia berjalan ke atas dirinya.

1172
00:58:02,430 --> 00:58:05,479
Jadi dalam erti kata itu, David menyentuh
kepada rekursi di dalam kelas.

1173
00:58:05,479 --> 00:58:07,270
Dan itulah konsep yang
kita akan bercakap tentang banyak lagi.

1174
00:58:07,270 --> 00:58:11,430
Ia yang ini, kedua-dua baris
di sini, sebenarnya hanya program ini

1175
00:58:11,430 --> 00:58:13,860
memberitahu ia berjalan sendiri
dengan input yang berbeza.

1176
00:58:13,860 --> 00:58:17,230
Jadi, daripada berjalan sendiri dengan
keseluruhan daripada n elemen,

1177
00:58:17,230 --> 00:58:20,530
anda boleh memecahkan ia turun ke dalam
separuh kiri dan separuh yang betul

1178
00:58:20,530 --> 00:58:22,680
dan kemudian berjalan lagi.

1179
00:58:22,680 --> 00:58:26,050
>> Dan kemudian kita akan melihat ia secara visual,
kerana saya seorang pelajar visual.

1180
00:58:26,050 --> 00:58:27,270
Ia berfungsi lebih baik untuk saya.

1181
00:58:27,270 --> 00:58:29,890
Oleh itu, kita akan melihat satu contoh visual di sini.

1182
00:58:29,890 --> 00:58:36,237
>> Katakan kita mempunyai array, enam
elemen, 3, 5, 2, 6, 4, 1, tidak disusun.

1183
00:58:36,237 --> 00:58:37,820
Baiklah, ada banyak di laman ini.

1184
00:58:37,820 --> 00:58:43,179
Jadi jika anda semua boleh melihat
langkah pertama di sini, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
anda boleh berpecah kepada dua bahagian.

1186
00:58:44,220 --> 00:58:45,976
Anda mempunyai 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Anda tahu bahawa ini aren't-- anda
tidak tahu jika mereka disusun atau tidak,

1188
00:58:48,850 --> 00:58:52,517
supaya anda terus pecahkan ke bawah, pada separuh,
pada separuh, pada separuh, sehingga akhirnya,

1189
00:58:52,517 --> 00:58:53,600
anda hanya mempunyai satu elemen.

1190
00:58:53,600 --> 00:58:56,790
Dan salah satu elemen sentiasa disusun, bukan?

1191
00:58:56,790 --> 00:59:01,560
>> Jadi kita tahu bahawa 3, 5, 2, 4, 6,
1, dengan diri mereka sendiri, sedang disusun.

1192
00:59:01,560 --> 00:59:05,870
Dan sekarang kita boleh meletakkan mereka kembali bersama-sama.

1193
00:59:05,870 --> 00:59:07,510
Jadi kita tahu 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Kami meletakkan mereka bersama-sama.

1195
00:59:08,510 --> 00:59:09,617
Kita tahu bahawa yang disusun.

1196
00:59:09,617 --> 00:59:10,450
2 ini masih ada.

1197
00:59:10,450 --> 00:59:11,830
Kita boleh meletakkan 4 dan 6 bersama-sama.

1198
00:59:11,830 --> 00:59:13,996
Kita tahu bahawa yang yang disusun,
jadi kami meletakkan bahawa bersama-sama.

1199
00:59:13,996 --> 00:59:14,940
Dan 1 ada.

1200
00:59:14,940 --> 00:59:18,720
>> Dan kemudian anda hanya melihat
kedua-dua bahagian di sini.

1201
00:59:18,720 --> 00:59:21,300
Anda mempunyai 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Anda hanya boleh membandingkan
bermula segala-galanya.

1203
00:59:23,465 --> 00:59:26,340
Kerana anda tahu bahawa ini disusun
dan anda tahu bahawa yang yang disusun.

1204
00:59:26,340 --> 00:59:29,360
Oleh itu, maka anda tidak perlu
membandingkan 5, anda hanya bandingkan 3.

1205
00:59:29,360 --> 00:59:32,070
Dan 2 adalah kurang dari 3, maka
anda tahu 2 mesti pergi pada akhirnya.

1206
00:59:32,070 --> 00:59:33,120
>> Perkara yang sama di sana.

1207
00:59:33,120 --> 00:59:34,740
1 mesti pergi sini.

1208
00:59:34,740 --> 00:59:37,330
Dan kemudian apabila anda pergi untuk meletakkan
kedua-dua nilai-nilai bersama-sama,

1209
00:59:37,330 --> 00:59:39,950
anda tahu bahawa ini adalah disusun dan
anda tahu bahawa yang disusun.

1210
00:59:39,950 --> 00:59:43,240
Sebab itu 1 dan
2, 1 adalah kurang dari 2.

1211
00:59:43,240 --> 00:59:45,570
Yang memberitahu anda bahawa 1
perlu pergi pada akhir ini

1212
00:59:45,570 --> 00:59:47,480
tanpa melihat 3 atau 5.

1213
00:59:47,480 --> 00:59:50,100
Dan kemudian 4, anda boleh hanya
menyemak, ia pergi betul-betul di sini.

1214
00:59:50,100 --> 00:59:51,480
Anda tidak perlu melihat 5.

1215
00:59:51,480 --> 00:59:52,570
Perkara yang sama dengan 6.

1216
00:59:52,570 --> 00:59:55,860
Anda tahu bahawa ia hanya 6--
tidak perlu diberi perhatian.

1217
00:59:55,860 --> 00:59:57,870
>> Dan supaya dengan cara itu, anda
hanya menyelamatkan diri

1218
00:59:57,870 --> 00:59:59,526
banyak langkah-langkah apabila anda membandingkan.

1219
00:59:59,526 --> 01:00:02,150
Anda tidak perlu membandingkan setiap
elemen terhadap unsur-unsur lain.

1220
01:00:02,150 --> 01:00:05,230
Anda hanya membandingkan terhadap orang-orang yang
yang anda perlu membandingkan ia menentang.

1221
01:00:05,230 --> 01:00:06,870
Jadi itulah jenis konsep abstrak.

1222
01:00:06,870 --> 01:00:10,540
Jangan bimbang jika ia tidak
agak memukul anda betul-betul lagi.

1223
01:00:10,540 --> 01:00:14,740
Tetapi secara umumnya, ini adalah
bagaimana merge berfungsi.

1224
01:00:14,740 --> 01:00:17,750
Soalan, soalan yang cepat,
sebelum saya bergerak?

1225
01:00:17,750 --> 01:00:18,550
Yeah.

1226
01:00:18,550 --> 01:00:22,230
>> PENONTON: Jadi, anda berkata bahawa anda mengambil
1, dan kemudian 4, dan 6

1227
01:00:22,230 --> 01:00:23,860
dan memasukkannya ke dalam.

1228
01:00:23,860 --> 01:00:26,800
Jadi tidak those-- tidak
anda melihat mereka

1229
01:00:26,800 --> 01:00:28,544
unsur-unsur berasingan, tidak secara keseluruhannya ini?

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Ya.

1231
01:00:29,210 --> 01:00:32,020
Jadi apa yang berlaku
adalah bahawa anda pada dasarnya

1232
01:00:32,020 --> 01:00:33,650
mencipta pelbagai jenama baru.

1233
01:00:33,650 --> 01:00:36,690
Jadi, anda tahu bahawa, di sini, saya mempunyai
dua tatasusunan saiz 3, bukan?

1234
01:00:36,690 --> 01:00:39,600
Jadi, anda tahu bahawa pelbagai disusun saya
perlu mempunyai enam elemen.

1235
01:00:39,600 --> 01:00:42,270
Jadi anda hanya membuat
kadar baru ingatan.

1236
01:00:42,270 --> 01:00:44,270
Jadi anda jenis seperti
membazir ingatan,

1237
01:00:44,270 --> 01:00:46,186
tetapi itu tidak penting
kerana ia adalah sangat kecil.

1238
01:00:46,186 --> 01:00:48,590
Jadi, anda melihat 1
dan anda melihat 2.

1239
01:00:48,590 --> 01:00:50,770
Dan anda tahu bahawa 1 adalah kurang dari 2.

1240
01:00:50,770 --> 01:00:53,840
Jadi, anda tahu bahawa 1 perlu pergi dalam
permulaan semua daripada mereka.

1241
01:00:53,840 --> 01:00:55,850
>> Anda tidak perlu
melihat 3 dan 5.

1242
01:00:55,850 --> 01:00:57,400
Jadi, anda tahu 1 pergi ke sana.

1243
01:00:57,400 --> 01:00:59,300
Kemudian anda pada dasarnya memenggal 1.

1244
01:00:59,300 --> 01:01:00,370
Ia adalah, seperti, mati kepada kami.

1245
01:01:00,370 --> 01:01:03,690
Maka kita hanya perlu 2,
3, 5, dan kemudian 4 dan 6.

1246
01:01:03,690 --> 01:01:06,270
Dan kemudian anda tahu itu, anda
membandingkan 4 dan 2,

1247
01:01:06,270 --> 01:01:07,560
oh, yang 2 perlu pergi di sana.

1248
01:01:07,560 --> 01:01:09,685
Jadi, anda mencebur 2 bawah, anda mencincang off.

1249
01:01:09,685 --> 01:01:12,060
Sebab itu anda hanya perlu 3
dan 5 dalam 4 dan 6.

1250
01:01:12,060 --> 01:01:14,650
Dan anda hanya menyimpan mencincang ia di luar
sehingga memasukkannya ke dalam array.

1251
01:01:14,650 --> 01:01:17,110
>> PENONTON: Jadi anda hanya sentiasa
membandingkan [didengar]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Tepat sekali.

1253
01:01:17,710 --> 01:01:19,590
Jadi dalam erti kata itu, anda berada
hanya membandingkan, pada dasarnya,

1254
01:01:19,590 --> 01:01:21,240
satu nombor terhadap nombor yang lain.

1255
01:01:21,240 --> 01:01:22,990
Dan kerana anda tahu
bahawa ia disusun, anda

1256
01:01:22,990 --> 01:01:24,350
tidak perlu melihat melalui
semua nombor.

1257
01:01:24,350 --> 01:01:25,870
Anda hanya perlu untuk melihat yang pertama.

1258
01:01:25,870 --> 01:01:27,582
Dan kemudian anda hanya boleh mencebur
mereka ke bawah, kerana anda tahu

1259
01:01:27,582 --> 01:01:29,640
mereka tergolong di mana mereka perlu tergolong.

1260
01:01:29,640 --> 01:01:31,030
Yeah.

1261
01:01:31,030 --> 01:01:32,920
Soalan yang baik.

1262
01:01:32,920 --> 01:01:35,290
>> Dan kemudian sesiapa di antara kamu
agak bercita-cita tinggi,

1263
01:01:35,290 --> 01:01:38,660
berasa bebas untuk melihat kod ini.

1264
01:01:38,660 --> 01:01:40,680
Ini sebenarnya adalah
pelaksanaan fizikal

1265
01:01:40,680 --> 01:01:42,150
bagaimana kita akan menulis merge.

1266
01:01:42,150 --> 01:01:44,070
Dan anda boleh lihat, ia adalah sangat singkat.

1267
01:01:44,070 --> 01:01:46,310
Tetapi idea-idea di sebalik
ia adalah agak kompleks.

1268
01:01:46,310 --> 01:01:50,865
Jadi, jika anda merasa seperti lukisan ini keluar
di malam ini kerja rumah anda, jangan ragu untuk.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> OKAY.

1271
01:01:54,740 --> 01:01:58,070
Lalu Daud juga telah pergi lebih ini dalam kuliah.

1272
01:01:58,070 --> 01:02:00,660
Apakah kes ini
runtimes, runtimes kes paling teruk,

1273
01:02:00,660 --> 01:02:05,680
dan runtimes diharapkan daripada jenis merge?

1274
01:02:05,680 --> 01:02:07,260
Beberapa saat untuk berfikir.

1275
01:02:07,260 --> 01:02:11,198
Ini adalah agak sukar, tetapi jenis
intuitif jika anda berfikir mengenainya.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Baiklah.

1278
01:02:23,054 --> 01:02:25,269
>> PENONTON: Apakah yang paling teruk kes n log n?

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Tepat sekali.

1280
01:02:26,060 --> 01:02:29,380
Dan mengapa ia n log n.

1281
01:02:29,380 --> 01:02:32,230
>> PENONTON: tidak Adakah kerana ia
menjadi pesat lebih cepat,

1282
01:02:32,230 --> 01:02:35,390
jadi ia seperti satu fungsi yang
bukan hanya sekadar menjadi n

1283
01:02:35,390 --> 01:02:37,529
kuasa dua atau sesuatu?

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Tepat sekali.

1285
01:02:38,320 --> 01:02:40,750
Jadi sebab mengapa
runtime mengenai perkara ini ialah n log

1286
01:02:40,750 --> 01:02:44,310
n adalah because-- apakah anda
lakukan dalam semua langkah-langkah ini?

1287
01:02:44,310 --> 01:02:46,190
Anda hanya memotong ia pada separuh, bukan?

1288
01:02:46,190 --> 01:02:48,750
Dan supaya apabila kita melakukan
log, semua yang ia lakukan

1289
01:02:48,750 --> 01:02:53,150
membahagikan masalah pada separuh,
pada separuh, pada separuh, lebih banyak bahagian.

1290
01:02:53,150 --> 01:02:56,430
Dan dalam erti kata itu, anda boleh jenis
untuk menghapuskan model linear

1291
01:02:56,430 --> 01:02:57,510
yang kita telah menggunakan.

1292
01:02:57,510 --> 01:03:00,254
Kerana apabila anda mencincang
perkara yang pada separuh, ia log.

1293
01:03:00,254 --> 01:03:02,420
Itu hanya matematik
cara yang mewakili mereka.

1294
01:03:02,420 --> 01:03:06,310
>> Dan kemudian akhirnya, pada akhirnya, anda berada
hanya membuat satu pas lepas melalui

1295
01:03:06,310 --> 01:03:07,930
untuk meletakkan semua daripada mereka untuk, bukan?

1296
01:03:07,930 --> 01:03:10,330
Dan jadi jika anda hanya perlu
menyemak satu perkara, itu n.

1297
01:03:10,330 --> 01:03:13,420
Dan supaya anda jenis
mendarabkan bersama-sama kedua-dua.

1298
01:03:13,420 --> 01:03:17,660
Jadi ia adalah seperti anda telah mendapat yang akhir
periksa n down sini dengan log n

1299
01:03:17,660 --> 01:03:18,390
di sini.

1300
01:03:18,390 --> 01:03:21,060
Dan jika anda membiak
mereka, itu n log n.

1301
01:03:21,060 --> 01:03:26,100
>> Dan supaya kes dan paling teruk yang terbaik
kes dan dijangka semua n log n.

1302
01:03:26,100 --> 01:03:27,943
Ia juga seperti jenis lain.

1303
01:03:27,943 --> 01:03:30,090
Ia seperti jenis pemilihan
dalam erti kata bahawa ia

1304
01:03:30,090 --> 01:03:32,131
Tidak kira apa yang anda
senarai adalah, ia hanya akan

1305
01:03:32,131 --> 01:03:34,801
untuk melakukan perkara yang sama setiap kali tunggal.

1306
01:03:34,801 --> 01:03:35,300
OKAY.

1307
01:03:35,300 --> 01:03:39,950
Jadi seperti yang anda semua boleh lihat, walaupun
macam yang kita telah pergi through-- n

1308
01:03:39,950 --> 01:03:41,660
kuasa dua, ia tidak sangat cekap.

1309
01:03:41,660 --> 01:03:47,060
Dan juga ini n log n adalah
bukan yang paling cekap.

1310
01:03:47,060 --> 01:03:49,720
Jika anda semua ingin tahu,
ada mekanisme jenis

1311
01:03:49,720 --> 01:03:54,310
yang begitu berkesan bahawa mereka
hampir dasarnya rata dalam masa jalanan.

1312
01:03:54,310 --> 01:03:55,420
>> Anda telah mendapat beberapa log n.

1313
01:03:55,420 --> 01:03:58,190
Anda telah mendapat beberapa log log n.

1314
01:03:58,190 --> 01:04:00,330
Kami tidak menyentuh mereka
dalam kelas ini buat masa ini.

1315
01:04:00,330 --> 01:04:02,663
Tetapi jika anda semua ingin tahu,
sila google, apa yang

1316
01:04:02,663 --> 01:04:04,392
mekanisme menyusun paling berkesan.

1317
01:04:04,392 --> 01:04:06,350
Saya tidak tahu, terdapat
beberapa yang benar-benar lucu,

1318
01:04:06,350 --> 01:04:09,860
like-- ada beberapa benar-benar
yang lucu yang orang membuat.

1319
01:04:09,860 --> 01:04:12,210
Dan anda tertanya-tanya bagaimana mereka
pernah terfikir untuk itu.

1320
01:04:12,210 --> 01:04:15,730
Jadi google, jika anda mempunyai beberapa lapang
semasa, atas, apa yang adalah beberapa cara lucu

1321
01:04:15,730 --> 01:04:17,730
yang dan kaum serta
orang ways-- cekap

1322
01:04:17,730 --> 01:04:20,371
telah dapat melaksanakan pelbagai.

1323
01:04:20,371 --> 01:04:20,870
OKAY.

1324
01:04:20,870 --> 01:04:22,880
Dan di sini hanya satu carta sedikit berguna.

1325
01:04:22,880 --> 01:04:26,850
Saya tahu anda semua, sebelum itu kuiz 0,
akan berada di dalam bilik anda mungkin cuba

1326
01:04:26,850 --> 01:04:27,960
menghafal itu.

1327
01:04:27,960 --> 01:04:30,940
Jadi itulah yang bagus di sana untuk anda semua.

1328
01:04:30,940 --> 01:04:37,120
Hanya jangan lupa logik yang dibuat-
mengapa nombor-nombor tersebut telah berlaku.

1329
01:04:37,120 --> 01:04:39,870
Jika anda selalu hilang, hanya membuat
pasti anda tahu apa yang macam berada.

1330
01:04:39,870 --> 01:04:40,820
Dan anda boleh berjalan melalui
mereka dalam fikiran anda

1331
01:04:40,820 --> 01:04:42,903
untuk memahami mengapa mereka
jawapan jawapan-jawapan tersebut.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Baiklah.

1334
01:04:47,600 --> 01:04:49,680
Oleh itu, kita akan bergerak
pada, akhirnya, untuk pencarian.

1335
01:04:49,680 --> 01:04:51,638
Kerana sebagai Pelawat
yang telah membaca pset,

1336
01:04:51,638 --> 01:04:55,175
pencarian juga merupakan sebahagian daripada
masalah ini minggu ini menetapkan.

1337
01:04:55,175 --> 01:04:57,300
Anda akan diminta untuk melaksanakan
dua jenis carian.

1338
01:04:57,300 --> 01:05:00,070
Satu adalah carian linear dan
satu adalah carian binari.

1339
01:05:00,070 --> 01:05:01,760
>> Jadi carian linear adalah agak mudah.

1340
01:05:01,760 --> 01:05:04,070
Anda hanya ingin mencari elemen
dalam senarai untuk melihat jika anda mendapatkannya.

1341
01:05:04,070 --> 01:05:05,444
Anda hanya perlu untuk melelar melalui.

1342
01:05:05,444 --> 01:05:08,170
Dan jika ia sama dengan sesuatu,
anda hanya boleh kembali itu, bukan?

1343
01:05:08,170 --> 01:05:10,890
Tetapi satu yang kita paling
berminat untuk bercakap tentang

1344
01:05:10,890 --> 01:05:14,550
adalah carian binari, kanan, yang merupakan
membahagi dan menakluk mekanisme yang

1345
01:05:14,550 --> 01:05:18,190
Daud menunjukkan dalam kuliah.

1346
01:05:18,190 --> 01:05:20,810
>> Ingat contoh buku telefon
yang dia terus membesarkan,

1347
01:05:20,810 --> 01:05:23,960
salah satu yang dia jenis bergelut
sedikit pada tahun lalu,

1348
01:05:23,960 --> 01:05:27,530
di mana anda membahagikan masalah pada separuh,
pada separuh, pada separuh, lagi dan lagi,

1349
01:05:27,530 --> 01:05:30,730
sehingga anda mencari apa yang anda cari?

1350
01:05:30,730 --> 01:05:33,727
Dan anda telah mendapat
runtime daripada itu juga.

1351
01:05:33,727 --> 01:05:35,810
Dan anda boleh lihat, ia
ketara lebih berkesan

1352
01:05:35,810 --> 01:05:39,080
daripada apa-apa jenis carian.

1353
01:05:39,080 --> 01:05:41,880
>> Jadi cara yang kita akan pergi tentang
melaksanakan carian binari

1354
01:05:41,880 --> 01:05:46,510
adalah, jika kita mempunyai array,
indeks 0-6, tujuh elemen,

1355
01:05:46,510 --> 01:05:49,790
kita boleh melihat di tengah-tengah, right--
maaf, jika soalan kami first--

1356
01:05:49,790 --> 01:05:53,840
jika kita ingin bertanya soalan, adakah
array mengandungi elemen 7,

1357
01:05:53,840 --> 01:05:56,840
jelas, menjadi manusia, dan mempunyai
seperti pelbagai kecil, ia adalah mudah bagi kita

1358
01:05:56,840 --> 01:05:58,210
untuk mengatakan ya.

1359
01:05:58,210 --> 01:06:05,750
Tetapi cara untuk melaksanakan binari
carian adalah untuk melihat di tengah-tengah.

1360
01:06:05,750 --> 01:06:08,020
>> Kita tahu bahawa indeks 3 adalah
tengah-tengah, kerana kita

1361
01:06:08,020 --> 01:06:09,270
tahu terdapat tujuh elemen.

1362
01:06:09,270 --> 01:06:10,670
Apa 7 dibahagikan dengan 2?

1363
01:06:10,670 --> 01:06:12,850
Anda boleh meneka bahawa tambahan 1.

1364
01:06:12,850 --> 01:06:14,850
Anda telah mendapat 3 di tengah-tengah.

1365
01:06:14,850 --> 01:06:17,590
Begitu juga dengan pelbagai 3 sama dengan 7?

1366
01:06:17,590 --> 01:06:18,900
Ia tidak, bukan?

1367
01:06:18,900 --> 01:06:21,050
Tetapi kita boleh melakukan beberapa cek.

1368
01:06:21,050 --> 01:06:25,380
Adalah pelbagai daripada 3 kurang daripada 7 atau
adalah pelbagai daripada 3 lebih besar daripada 7?

1369
01:06:25,380 --> 01:06:27,240
>> Dan kita tahu bahawa ia adalah kurang daripada 7.

1370
01:06:27,240 --> 01:06:30,259
Oleh itu, kita tahu bahawa, oh, ia mesti
tidak berada dalam separuh kiri.

1371
01:06:30,259 --> 01:06:32,300
Kita tahu bahawa ia mesti
pada separuh yang betul, bukan?

1372
01:06:32,300 --> 01:06:34,662
Oleh itu, kita hanya boleh meneka separuh array.

1373
01:06:34,662 --> 01:06:36,370
Kita tidak perlu
melihat lagi.

1374
01:06:36,370 --> 01:06:38,711
Kerana kita tahu bahawa
separuh daripada problem-- kami

1375
01:06:38,711 --> 01:06:41,210
kita tahu bahawa jawapan itu adalah dalam
separuh kanan masalah kita.

1376
01:06:41,210 --> 01:06:42,580
Oleh itu, kita hanya melihat bahawa sekarang.

1377
01:06:42,580 --> 01:06:44,860
>> Jadi sekarang kita melihat
pertengahan apa yang tinggal.

1378
01:06:44,860 --> 01:06:46,880
Bahawa indeks 5.

1379
01:06:46,880 --> 01:06:50,200
Kami melakukan pemeriksaan yang sama sekali lagi
dan kita melihat bahawa ia adalah lebih kecil.

1380
01:06:50,200 --> 01:06:52,050
Oleh itu, kita melihat di sebelah kiri itu.

1381
01:06:52,050 --> 01:06:53,430
Dan kemudian kita melihat daftar itu.

1382
01:06:53,430 --> 01:06:57,600
Apakah nilai keselesaan dan kemudahan di
Indeks 4 sama dengan 7?

1383
01:06:57,600 --> 01:06:58,260
Ia adalah.

1384
01:06:58,260 --> 01:07:03,580
Oleh itu, kita boleh kembali benar, kerana
kami mendapati nilai dalam senarai kami.

1385
01:07:03,580 --> 01:07:06,738
Adakah cara yang saya lalui
yang masuk akal untuk semua orang?

1386
01:07:06,738 --> 01:07:08,760
OKAY.

1387
01:07:08,760 --> 01:07:11,670
Saya akan memberikan anda semua mungkin, seperti,
tiga, empat minit untuk memikirkan

1388
01:07:11,670 --> 01:07:13,270
bagaimana untuk pseudokod ini.

1389
01:07:13,270 --> 01:07:18,070
>> Jadi bayangkan Saya bertanya kepada anda untuk menulis
fungsi dipanggil carian () yang pulang

1390
01:07:18,070 --> 01:07:20,640
nilai, nilai Boolean,
itu adalah benar atau false-- seperti,

1391
01:07:20,640 --> 01:07:22,970
benar jika anda mendapati
nilai, palsu jika anda tidak.

1392
01:07:22,970 --> 01:07:25,230
Dan kemudian anda adalah
diluluskan pada nilai yang anda

1393
01:07:25,230 --> 01:07:28,410
cari ke dalam nilai-nilai, yang
adalah array-- oh, saya pasti meletakkan

1394
01:07:28,410 --> 01:07:29,410
bahawa di tempat yang salah.

1395
01:07:29,410 --> 01:07:29,580
OKAY.

1396
01:07:29,580 --> 01:07:31,829
Anyways, yang sepatutnya
pernah ke kanan nilai.

1397
01:07:31,829 --> 01:07:36,280
Dan kemudian int n ialah bilangan
elemen dalam array itu.

1398
01:07:36,280 --> 01:07:39,430
Bagaimana anda pergi tentang mencuba
kepada kod pseudo bahawa masalah dalam?

1399
01:07:39,430 --> 01:07:41,630
Saya akan memberikan anda semua suka
tiga minit untuk berbuat demikian.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Tidak, saya fikir ada only--
yeah, ada satu betul di sini.

1402
01:08:02,595 --> 01:08:03,261
PENONTON: Bolehkah saya?

1403
01:08:03,261 --> 01:08:04,388
ANDI PENG: Ya, saya mendapat anda.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Adakah kerja itu?

1406
01:08:11,050 --> 01:08:12,290
OK, sejuk.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> OKAY.

1409
01:10:44,720 --> 01:10:47,630
Semua lelaki betul, kita berada
akan mengekang dalam.

1410
01:10:47,630 --> 01:10:49,730
OKAY.

1411
01:10:49,730 --> 01:10:54,020
Jadi menganggap kita telah mendapat ini indah
sedikit pelbagai dengan nilai-nilai n di dalamnya.

1412
01:10:54,020 --> 01:10:55,170
Saya tidak menarik garis.

1413
01:10:55,170 --> 01:10:58,649
Tetapi bagaimana kita akan pergi tentang
cuba untuk menulis ini?

1414
01:10:58,649 --> 01:11:00,440
Adakah sesiapa yang mahu
memberi saya baris pertama?

1415
01:11:00,440 --> 01:11:02,814
Jika anda ingin memberi saya
Baris pertama pseudokod ini.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> PENONTON: [didengar]

1418
01:11:08,430 --> 01:11:10,138
PENONTON: Anda akan mahu
untuk melelar through--

1419
01:11:10,138 --> 01:11:11,094
PENONTON: Hanya satu lagi untuk gelung?

1420
01:11:11,094 --> 01:11:11,760
PENONTON: --Untuk.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Jadi yang ini agak rumit.

1423
01:11:17,780 --> 01:11:23,130
Fikirkan about-- anda mahu
terus berjalan gelung ini

1424
01:11:23,130 --> 01:11:27,950
lagi dan lagi sehingga bila?

1425
01:11:27,950 --> 01:11:30,819
>> PENONTON: Sehingga [didengar]
nilainya sama dengan nilai itu.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Tepat sekali.

1427
01:11:31,610 --> 01:11:33,900
Jadi, anda boleh sebenarnya hanya write--
kita juga boleh memudahkan lebih.

1428
01:11:33,900 --> 01:11:35,630
Kami hanya boleh melakukan gelung sementara, bukan?

1429
01:11:35,630 --> 01:11:39,380
Jadi anda hanya boleh mempunyai loop--
kita tahu bahawa itu seketika.

1430
01:11:39,380 --> 01:11:42,850
Tetapi untuk sekarang, saya akan
untuk mengatakan "gelung" - melalui apa?

1431
01:11:42,850 --> 01:11:46,640
Loop until-- apa yang
keadaan berakhir kita?

1432
01:11:46,640 --> 01:11:47,510
Saya rasa saya mendengarnya.

1433
01:11:47,510 --> 01:11:48,530
Saya mendengar seseorang mengatakan ia.

1434
01:11:48,530 --> 01:11:51,255
>> PENONTON: Nilai-nilai sama tengah.

1435
01:11:51,255 --> 01:11:52,255
ANDI PENG: Katakan sekali lagi.

1436
01:11:52,255 --> 01:11:54,470
PENONTON: Atau, sehingga
nilai yang anda sedang mencari

1437
01:11:54,470 --> 01:11:58,470
adalah sama dengan nilai tengah.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI PENG: Bagaimana jika ia tidak di sana?

1439
01:12:00,280 --> 01:12:03,113
Bagaimana jika nilai yang anda sedang mencari
untuk tidak sebenarnya dalam pelbagai ini?

1440
01:12:03,113 --> 01:12:05,890
PENONTON: Anda kembali 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI PENG: Tetapi apa yang kita mahu
gelung sehingga jika kita mempunyai keadaan?

1442
01:12:08,850 --> 01:12:09,350
Yeah.

1443
01:12:09,350 --> 01:12:11,239
>> PENONTON: Sehingga terdapat hanya satu nilai?

1444
01:12:11,239 --> 01:12:13,530
ANDI PENG: Anda boleh gelung
until-- supaya anda tahu bahawa anda

1445
01:12:13,530 --> 01:12:15,714
akan mempunyai nilai max, bukan?

1446
01:12:15,714 --> 01:12:18,130
Dan anda tahu bahawa anda akan
mempunyai nilai min, bukan?

1447
01:12:18,130 --> 01:12:20,379
Kerana juga, itu sesuatu
Saya terlupa untuk mengatakan sebelum ini,

1448
01:12:20,379 --> 01:12:22,640
bahawa sesuatu yang
kritikal mengenai carian binari

1449
01:12:22,640 --> 01:12:24,182
adalah bahawa pelbagai anda sudah disusun.

1450
01:12:24,182 --> 01:12:26,973
Oleh kerana tidak ada cara untuk berbuat
ini jika mereka nilai-nilai hanya secara rawak.

1451
01:12:26,973 --> 01:12:29,190
Anda tidak tahu jika seseorang itu
lebih besar dari yang lain, bukan?

1452
01:12:29,190 --> 01:12:32,720
>> Jadi, anda tahu yang anda dan max
minit anda berada di sini, bukan?

1453
01:12:32,720 --> 01:12:35,590
Jika anda akan dapat menyesuaikan diri
max anda dalam minit anda dan mid--

1454
01:12:35,590 --> 01:12:38,470
mari kita hanya menganggap anda
nilai pertengahan adalah sini-- betul

1455
01:12:38,470 --> 01:12:43,910
anda akan pada dasarnya
gelung sehingga minimum anda

1456
01:12:43,910 --> 01:12:47,510
lebih kurang sama dengan maks anda, kanan, atau
jika maks anda tidak sama seperti min anda.

1457
01:12:47,510 --> 01:12:48,040
Betul?

1458
01:12:48,040 --> 01:12:51,340
Kerana apabila itu berlaku, anda tahu bahawa
anda telah akhirnya mencecah nilai yang sama.

1459
01:12:51,340 --> 01:12:59,135
Jadi, anda mahu gelung sehingga min anda
adalah kurang daripada atau sama supaya- oops,

1460
01:12:59,135 --> 01:13:01,510
tidak kurang daripada atau sama dengan,
dengan cara yang lain around-- max.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Adakah ini masuk akal?

1463
01:13:16,160 --> 01:13:18,810
Saya mengambil beberapa cuba untuk mendapatkan hak itu.

1464
01:13:18,810 --> 01:13:21,869
Tetapi gelung sehingga nilai maksimum anda
pada dasarnya hampir kurang

1465
01:13:21,869 --> 01:13:23,410
daripada atau sama dengan minimum anda, bukan?

1466
01:13:23,410 --> 01:13:25,201
Itulah apabila anda tahu
yang anda telah berkumpul.

1467
01:13:25,201 --> 01:13:29,290
PENONTON: Apabila akan maksimum anda
nilai kurang daripada minimum?

1468
01:13:29,290 --> 01:13:31,040
ANDI PENG: Jika anda menyimpan
menyesuaikan ia, yang

1469
01:13:31,040 --> 01:13:32,380
adalah apa yang kita akan
untuk melakukan dalam hal ini.

1470
01:13:32,380 --> 01:13:33,460
Adakah ini masuk akal?

1471
01:13:33,460 --> 01:13:35,750
Minimum dan maksimum hanya
integer yang kita mungkin

1472
01:13:35,750 --> 01:13:39,260
akan mahu untuk mencipta untuk menjaga
mengesan di mana kita cari.

1473
01:13:39,260 --> 01:13:41,790
Kerana array wujud
tidak kira apa yang kita lakukan.

1474
01:13:41,790 --> 01:13:45,030
Seperti, kita tidak benar-benar secara fizikal
pancung array, bukan?

1475
01:13:45,030 --> 01:13:47,261
Kami hanya menyesuaikan
di mana kita cari.

1476
01:13:47,261 --> 01:13:48,136
Adakah ini masuk akal?

1477
01:13:48,136 --> 01:13:48,472
>> PENONTON: Ya.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI PENG: OK.

1479
01:13:49,110 --> 01:13:57,090
Jadi jika itu syarat untuk gelung kami,
apa yang kita mahu di dalam gelung ini?

1480
01:13:57,090 --> 01:13:58,700
Apa yang kita akan mahu lakukan?

1481
01:13:58,700 --> 01:14:02,390
Jadi sekarang, kita telah mendapat
max dan min, betul,

1482
01:14:02,390 --> 01:14:04,962
mungkin dicipta di sini suatu tempat.

1483
01:14:04,962 --> 01:14:07,170
Kami akan mungkin mahu
untuk mencari yang pertengahan, bukan?

1484
01:14:07,170 --> 01:14:08,450
Bagaimana kita akan menjadi
dapat mencari tengah-tengah?

1485
01:14:08,450 --> 01:14:09,491
Apa yang mathematical-- yang

1486
01:14:09,491 --> 01:14:11,079
PENONTON: Max ditambah min dibahagikan dengan 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Tepat sekali.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Adakah ini masuk akal?

1490
01:14:21,620 --> 01:14:25,780
Dan yang anda semua nampak mengapa kita
tidak hanya use-- mengapa kita lakukan ini

1491
01:14:25,780 --> 01:14:27,850
daripada melakukan hanya n dibahagikan dengan 2?

1492
01:14:27,850 --> 01:14:30,310
Ini kerana n adalah nilai yang
yang akan tetap sama.

1493
01:14:30,310 --> 01:14:30,979
Betul?

1494
01:14:30,979 --> 01:14:34,020
Tetapi seperti yang kita menyesuaikan minimum dan
nilai maksimum, mereka akan berubah.

1495
01:14:34,020 --> 01:14:36,040
Dan hasilnya, tengah kami
akan berubah.

1496
01:14:36,040 --> 01:14:37,873
Jadi itulah sebabnya kita mahu
untuk berbuat baik ini di sini.

1497
01:14:37,873 --> 01:14:38,510
OKAY.

1498
01:14:38,510 --> 01:14:41,600
>> Dan kemudian, sekarang
kami telah mendapati our-- yeah.

1499
01:14:41,600 --> 01:14:44,270
>> PENONTON: Hanya question-- cepat
apabila anda mengatakan min dan max,

1500
01:14:44,270 --> 01:14:46,410
kita menganggap bahawa
ia sudah disusun?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI PENG: Ya, itu sebenarnya satu
pra-syarat untuk carian binari,

1502
01:14:48,400 --> 01:14:49,816
yang perlu anda tahu ia disusun.

1503
01:14:49,816 --> 01:14:53,660
Itulah sebabnya jenis, anda menulis dalam anda
masalah set sebelum carian binari anda.

1504
01:14:53,660 --> 01:14:55,910
OKAY.

1505
01:14:55,910 --> 01:14:58,876
Jadi sekarang kita tahu di mana titik tengah kami
ini, apa yang anda mahu lakukan di sini?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> PENONTON: Kami mahu membandingkan
yang kepada orang lain.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Tepat sekali.

1509
01:15:05,110 --> 01:15:12,280
Jadi, anda akan membandingkan
pertengahan kepada nilai, bukan?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
Dan apa yang memberitahu
kita apabila kita bandingkan?

1512
01:15:18,670 --> 01:15:22,226
Apa yang kami mahu lakukan selepas itu?

1513
01:15:22,226 --> 01:15:25,389
>> PENONTON: Jika nilai adalah lebih besar
daripada pertengahan, kami mahu potong.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Tepat sekali.

1515
01:15:26,180 --> 01:15:33,940
Jadi, jika nilai yang lebih besar
daripada pertengahan, kami

1516
01:15:33,940 --> 01:15:36,550
akan mahu untuk mengubah
minimum dan maxes, bukan?

1517
01:15:36,550 --> 01:15:38,980
Apa yang kita mahu berubah?

1518
01:15:38,980 --> 01:15:42,145
Jadi, jika kita tahu nilai adalah suatu tempat
di sini, apa yang anda kita berubah?

1519
01:15:42,145 --> 01:15:44,758
Kami mahu mengubah kami
minimum untuk menjadi pertengahan, bukan?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
Kemudian lagi, jika ia dalam ini
setengah, apa yang kita mahu berubah?

1522
01:15:54,292 --> 01:15:55,306
>> PENONTON: maksimum anda.

1523
01:15:55,306 --> 01:15:55,972
ANDI PENG: Ya.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
Dan kemudian anda hanya akan
untuk menjaga menggelung, bukan?

1526
01:16:04,680 --> 01:16:08,920
Kerana sekarang, selepas satu lelaran
melalui, anda telah mendapat max di sini.

1527
01:16:08,920 --> 01:16:10,760
Dan kemudian anda boleh mengira semula pertengahan a.

1528
01:16:10,760 --> 01:16:11,990
Dan kemudian anda boleh membuat perbandingan.

1529
01:16:11,990 --> 01:16:14,766
Dan anda akan terus pergi
sehingga minit dan maxes

1530
01:16:14,766 --> 01:16:15,890
telah pada dasarnya bertumpu.

1531
01:16:15,890 --> 01:16:17,890
Dan itulah apabila anda tahu bahawa
anda telah melanda akhir itu.

1532
01:16:17,890 --> 01:16:20,280
Dan sama ada anda telah mendapati ia
atau anda tidak mempunyai pada ketika itu.

1533
01:16:20,280 --> 01:16:23,170
>> Adakah ini masuk akal untuk semua orang?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
OKAY.

1536
01:16:26,770 --> 01:16:27,900
Ini adalah cukup penting,
kerana anda akan mempunyai

1537
01:16:27,900 --> 01:16:29,760
untuk menulis ini di malam ini kod anda.

1538
01:16:29,760 --> 01:16:32,660
Tetapi anda semua mempunyai yang cukup baik
rasa apa yang anda perlu lakukan,

1539
01:16:32,660 --> 01:16:34,051
yang baik.

1540
01:16:34,051 --> 01:16:34,550
OKAY.

1541
01:16:34,550 --> 01:16:38,840
Jadi kami mempunyai kira-kira tujuh
minit kiri bahagian.

1542
01:16:38,840 --> 01:16:43,170
Jadi, kita akan bercakap tentang
Serangga ini yang kita akan lakukan.

1543
01:16:43,170 --> 01:16:46,410
Jadi Serangga dibahagikan kepada dua bahagian.

1544
01:16:46,410 --> 01:16:50,230
Separuh pertama melibatkan
melaksanakan find a

1545
01:16:50,230 --> 01:16:54,210
di mana anda menulis carian linear,
carian binari, dan algoritma yang sorting.

1546
01:16:54,210 --> 01:16:56,690
>> Jadi ini adalah yang pertama
masa dalam pset mana

1547
01:16:56,690 --> 01:17:00,050
kami akan memberikan anda semua apa yang dipanggil
kod pengedaran, yang merupakan kod

1548
01:17:00,050 --> 01:17:02,740
bahawa kita mempunyai pra-bertulis,
tetapi hanya meninggalkan beberapa keping off

1549
01:17:02,740 --> 01:17:04,635
untuk anda untuk menyelesaikan secara bertulis.

1550
01:17:04,635 --> 01:17:07,510
Jadi anda semua, apabila anda melihat ini
kod, anda mungkin akan benar-benar takut.

1551
01:17:07,510 --> 01:17:08,630
Jika anda hanya suka, ahh, saya
tidak tahu apa yang yang demikian,

1552
01:17:08,630 --> 01:17:11,670
Saya tidak tahu, seperti, yang seolah-olah
begitu rumit, ahh, berehat.

1553
01:17:11,670 --> 01:17:12,170
Tidak mengapa.

1554
01:17:12,170 --> 01:17:12,930
Baca spesifikasi.

1555
01:17:12,930 --> 01:17:16,920
Spec akan menerangkan kepada anda dengan tepat
apa semua program-program ini lakukan.

1556
01:17:16,920 --> 01:17:20,560
>> Sebagai contoh, generate.c adalah program yang
yang akan datang dengan pset anda.

1557
01:17:20,560 --> 01:17:24,060
Anda sebenarnya tidak perlu menyentuh, tetapi
anda perlu memahami apa yang ia lakukan.

1558
01:17:24,060 --> 01:17:28,550
Dan generate.c, semua yang ia lakukan adalah
memuat menjana nombor rawak

1559
01:17:28,550 --> 01:17:32,400
atau anda boleh memberikan keturunan, seperti
nombor yg telah diatur sebelumnya bahawa ia mengambil masa,

1560
01:17:32,400 --> 01:17:34,140
dan ia menjana lebih nombor.

1561
01:17:34,140 --> 01:17:37,170
Jadi ada cara yang khusus untuk
melaksanakan generate.c di mana

1562
01:17:37,170 --> 01:17:42,760
anda hanya boleh membuat sekumpulan nombor
untuk anda untuk menguji kaedah anda yang lain pada.

1563
01:17:42,760 --> 01:17:45,900
>> Jadi, jika anda mahu, untuk
Sebagai contoh, menguji find anda,

1564
01:17:45,900 --> 01:17:48,970
anda akan mahu menjalankan generate.c,
menjana sekumpulan nombor,

1565
01:17:48,970 --> 01:17:50,880
dan kemudian berjalan fungsi pembantu anda.

1566
01:17:50,880 --> 01:17:53,930
Fungsi pembantu anda adalah di mana anda berada
sebenarnya fizikal menulis kod.

1567
01:17:53,930 --> 01:17:59,330
Dan memikirkan pembantu sebagai fail perpustakaan
anda menulis find yang memanggil.

1568
01:17:59,330 --> 01:18:02,950
Dan demikian dalam helpers.c, anda akan
melakukan mencari dan menyusun.

1569
01:18:02,950 --> 01:18:06,500
>> Dan kemudian anda akan pada dasarnya
hanya meletakkan mereka semua bersama-sama.

1570
01:18:06,500 --> 01:18:10,350
Spec ini akan memberitahu anda bagaimana untuk
meletakkan bahawa pada baris arahan.

1571
01:18:10,350 --> 01:18:14,880
Dan anda akan dapat untuk menguji sama ada atau
tidak menyusun dan carian anda bekerja.

1572
01:18:14,880 --> 01:18:15,870
Sejuk.

1573
01:18:15,870 --> 01:18:18,720
Adakah sesiapa pun bermula dan
masalah yang dihadapi atau soalan

1574
01:18:18,720 --> 01:18:20,520
mereka mempunyai sekarang dengan ini?

1575
01:18:20,520 --> 01:18:21,020
OKAY.

1576
01:18:21,020 --> 01:18:21,476
>> PENONTON: Tunggu.

1577
01:18:21,476 --> 01:18:21,932
Saya ada satu soalan.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Ya.

1579
01:18:22,844 --> 01:18:28,390
>> PENONTON: Jadi saya mula melakukan
carian linear dalam helpers.c

1580
01:18:28,390 --> 01:18:29,670
dan ia tidak benar-benar bekerja.

1581
01:18:29,670 --> 01:18:34,590
Tetapi kemudian, saya mendapat tahu kita hanya
perlu memadamnya dan melakukan carian binari.

1582
01:18:34,590 --> 01:18:36,991
Jadi adakah ia perkara jika ia tidak berfungsi?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI PENG: Jawapan pendek tidak.

1585
01:18:41,510 --> 01:18:42,642
Tetapi oleh kerana kita tidak--

1586
01:18:42,642 --> 01:18:44,350
PENONTON: Tetapi tidak ada yang
sebenarnya memeriksa.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: Kami tidak pernah
akan melihat bahawa.

1588
01:18:46,058 --> 01:18:49,590
Tetapi anda mungkin ingin
memastikan carian anda berfungsi.

1589
01:18:49,590 --> 01:18:51,700
Kerana jika anda linear
carian tidak berfungsi,

1590
01:18:51,700 --> 01:18:54,410
maka kemungkinan binari anda
carian tidak akan berfungsi dengan baik.

1591
01:18:54,410 --> 01:18:56,646
Kerana anda perlu sama
logik dalam kedua-dua mereka.

1592
01:18:56,646 --> 01:18:58,020
Dan tidak, ia tidak benar-benar perkara itu.

1593
01:18:58,020 --> 01:19:01,300
Jadi satu-satunya anda akan bertukar
dalam adalah jenis dan carian binari.

1594
01:19:01,300 --> 01:19:02,490
Yeah.

1595
01:19:02,490 --> 01:19:06,610
>> Dan juga, banyak anak-anak adalah
cuba untuk menyusun helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Anda sebenarnya tidak dibenarkan
untuk berbuat demikian, kerana helpers.c

1597
01:19:09,550 --> 01:19:11,200
tidak mempunyai fungsi utama.

1598
01:19:11,200 --> 01:19:13,550
Dan supaya anda hanya boleh
menjadi benar-benar menyusun

1599
01:19:13,550 --> 01:19:18,670
menjana dan mencari, kerana mencari panggilan
helpers.c dan fungsi-fungsi di dalamnya.

1600
01:19:18,670 --> 01:19:20,790
Supaya membuat debugging
sakit di punggung itu.

1601
01:19:20,790 --> 01:19:22,422
Tetapi itulah yang perlu kita lakukan.

1602
01:19:22,422 --> 01:19:23,880
PENONTON: Anda hanya membuat semua, bukan?

1603
01:19:23,880 --> 01:19:27,290
ANDI PENG: Anda boleh hanya
membuat semua juga, ya.

1604
01:19:27,290 --> 01:19:28,060
OKAY.

1605
01:19:28,060 --> 01:19:32,570
Jadi itu sahaja dari segi apa yang
pset meminta anda semua lakukan.

1606
01:19:32,570 --> 01:19:35,160
Jika anda mempunyai sebarang pertanyaan, sila
untuk bertanya kepada saya selepas seksyen.

1607
01:19:35,160 --> 01:19:37,580
Saya akan berada di sini untuk, seperti, 20 minit.

1608
01:19:37,580 --> 01:19:40,500
>> Dan yeah, yang pset ini
benar-benar tidak yang buruk.

1609
01:19:40,500 --> 01:19:41,680
Kalian harus OK.

1610
01:19:41,680 --> 01:19:43,250
Ini, ikuti garis panduan.

1611
01:19:43,250 --> 01:19:47,840
Jenis mempunyai rasa, secara logiknya, apa
sepatutnya berlaku dan anda akan selamat.

1612
01:19:47,840 --> 01:19:48,690
Jangan terlalu takut.

1613
01:19:48,690 --> 01:19:50,220
Ada banyak kod
lagi menulis di sana.

1614
01:19:50,220 --> 01:19:53,011
Jangan terlalu takut jika tidak
memahami apa yang semua yang bermakna.

1615
01:19:53,011 --> 01:19:54,749
Jika ia banyak, ia benar-benar baik.

1616
01:19:54,749 --> 01:19:55,790
Dan datang ke waktu pejabat.

1617
01:19:55,790 --> 01:19:57,520
Kami akan membantu anda membaca.

1618
01:19:57,520 --> 01:20:00,810
>> PENONTON: Dengan tambahan
fungsi, kita melihat mereka sehingga?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI PENG: Ya, mereka adalah dalam kod.

1620
01:20:03,417 --> 01:20:05,750
Dalam permainan 15, separuh daripada
ia telah ditulis untuk anda.

1621
01:20:05,750 --> 01:20:09,310
Maka orang-orang fungsi adalah
sudah dalam kod.

1622
01:20:09,310 --> 01:20:12,020
Ya.

1623
01:20:12,020 --> 01:20:12,520
Baiklah.

1624
01:20:12,520 --> 01:20:14,000
Nah, selamat mencuba.

1625
01:20:14,000 --> 01:20:15,180
Ia adalah hari yang menjijikkan.

1626
01:20:15,180 --> 01:20:19,370
Jadi diharapkan anda semua tidak akan merasa begitu
susah tinggal di dalam dan pengkodan.

1627
01:20:19,370 --> 01:20:22,133