1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Bagian 3 - Lebih Nyaman]

2
00:00:02,570 --> 00:00:05,070
[Rob Bowden - Harvard University]

3
00:00:05,070 --> 00:00:07,310
>> [Ini adalah CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Jadi pertanyaan pertama anehnya worded.

5
00:00:12,700 --> 00:00:17,480
GDB memungkinkan Anda "debug" program, tetapi, lebih khusus, apa yang membiarkan Anda lakukan?

6
00:00:17,480 --> 00:00:22,590
Saya akan menjawab pertanyaan itu, dan aku tidak tahu apa yang sebenarnya diharapkan,

7
00:00:22,590 --> 00:00:27,910
jadi aku menebak itu sesuatu sepanjang garis itu memungkinkan Anda langkah demi langkah

8
00:00:27,910 --> 00:00:31,540
berjalan melalui program ini, berinteraksi dengan itu, variabel perubahan, melakukan semua hal ini -

9
00:00:31,540 --> 00:00:34,270
pada dasarnya benar-benar mengontrol pelaksanaan program

10
00:00:34,270 --> 00:00:38,410
dan memeriksa setiap bagian tertentu dari pelaksanaan program.

11
00:00:38,410 --> 00:00:43,030
Jadi fitur tersebut memungkinkan Anda men-debug hal.

12
00:00:43,030 --> 00:00:44,830
Oke.

13
00:00:44,830 --> 00:00:50,520
Kenapa pencarian biner mengharuskan array akan diurutkan?

14
00:00:50,520 --> 00:00:53,360
Siapa yang ingin menjawab itu?

15
00:00:56,120 --> 00:01:00,070
[Mahasiswa] Karena tidak bekerja jika tidak diurutkan. >> Ya. [Tertawa]

16
00:01:00,070 --> 00:01:04,910
Jika tidak diurutkan, maka itu tidak mungkin untuk membagi menjadi dua

17
00:01:04,910 --> 00:01:07,850
dan tahu bahwa segala sesuatu ke kiri kurang dan segala sesuatu ke kanan

18
00:01:07,850 --> 00:01:10,490
lebih besar dari nilai tengah.

19
00:01:10,490 --> 00:01:12,790
Jadi perlu diurutkan.

20
00:01:12,790 --> 00:01:14,170
Oke.

21
00:01:14,170 --> 00:01:17,570
Mengapa gelembung semacam di O n kuadrat?

22
00:01:17,570 --> 00:01:23,230
Apakah ada yang pertama ingin memberikan gambaran tingkat tinggi yang sangat cepat seperti apa gelembung?

23
00:01:25,950 --> 00:01:33,020
[Mahasiswa] Anda pada dasarnya pergi melalui setiap elemen dan Anda memeriksa beberapa elemen pertama.

24
00:01:33,020 --> 00:01:37,150
Jika mereka keluar dari mana Anda menukar mereka, maka Anda memeriksa beberapa elemen berikutnya dan seterusnya.

25
00:01:37,150 --> 00:01:40,770
Ketika Anda mencapai akhir, maka Anda tahu bahwa elemen terbesar ditempatkan di akhir,

26
00:01:40,770 --> 00:01:42,750
sehingga Anda mengabaikan yang satu maka Anda terus berjalan melalui,

27
00:01:42,750 --> 00:01:48,490
dan setiap kali Anda harus memeriksa satu elemen kurang sampai Anda membuat tidak ada perubahan. >> Ya.

28
00:01:48,490 --> 00:01:58,470
Ini disebut bubble sort karena jika Anda membalik array pada sisinya jadi naik dan turun, vertikal,

29
00:01:58,470 --> 00:02:03,100
maka nilai-nilai yang besar akan tenggelam ke dasar dan nilai-nilai kecil akan menggelembung ke atas.

30
00:02:03,100 --> 00:02:05,210
Begitulah mendapat namanya.

31
00:02:05,210 --> 00:02:08,220
Dan ya, Anda hanya pergi melalui.

32
00:02:08,220 --> 00:02:11,190
Anda terus melalui array, swapping nilai yang lebih besar

33
00:02:11,190 --> 00:02:14,040
untuk mendapatkan nilai terbesar ke bawah.

34
00:02:14,040 --> 00:02:17,500
>> Mengapa O n kuadrat?

35
00:02:18,690 --> 00:02:24,620
Pertama, apakah ada yang ingin mengatakan mengapa O n kuadrat?

36
00:02:24,620 --> 00:02:28,760
[Mahasiswa] Karena untuk menjalankan setiap ia pergi n kali.

37
00:02:28,760 --> 00:02:32,100
Anda hanya dapat yakin bahwa Anda telah mengambil elemen terbesar semua jalan ke bawah,

38
00:02:32,100 --> 00:02:35,230
maka Anda harus mengulangi bahwa untuk sebagai banyak unsur. >> Ya.

39
00:02:35,230 --> 00:02:41,800
Jadi ingat apa big O berarti dan apa artinya Omega besar.

40
00:02:41,800 --> 00:02:50,560
The O besar adalah seperti batas atas seberapa lambat itu benar-benar dapat dijalankan.

41
00:02:50,560 --> 00:02:58,990
Jadi dengan mengatakan itu O n kuadrat, tidak O dari n atau yang lain itu akan dapat menjalankan

42
00:02:58,990 --> 00:03:02,640
dalam waktu linier, tetapi O n potong dadu

43
00:03:02,640 --> 00:03:06,390
karena dibatasi oleh O n potong dadu.

44
00:03:06,390 --> 00:03:12,300
Jika itu dibatasi oleh O n kuadrat, maka itu dibatasi juga oleh n potong dadu.

45
00:03:12,300 --> 00:03:20,280
Jadi adalah n kuadrat, dan dalam kasus terburuk mutlak tidak dapat berbuat lebih baik dari n kuadrat,

46
00:03:20,280 --> 00:03:22,830
itulah sebabnya mengapa itu O n kuadrat.

47
00:03:22,830 --> 00:03:31,200
Jadi untuk melihat matematika sedikit pada bagaimana keluar menjadi n kuadrat,

48
00:03:31,200 --> 00:03:40,530
jika kita memiliki lima hal di daftar kami, pertama kalinya berapa banyak swap bisa kita berpotensi perlu membuat

49
00:03:40,530 --> 00:03:47,170
dalam rangka untuk mendapatkan ini? Mari kita sebenarnya hanya -

50
00:03:47,170 --> 00:03:52,040
Berapa banyak swap yang kita akan harus membuat dalam jangka pertama bubble sort melalui array?

51
00:03:52,040 --> 00:03:53,540
[Mahasiswa] n - 1. >> Ya.

52
00:03:53,540 --> 00:03:58,340
>> Jika ada 5 elemen, kita akan perlu membuat n - 1.

53
00:03:58,340 --> 00:04:01,100
Kemudian pada kedua berapa banyak swap yang akan kita harus membuat?

54
00:04:01,100 --> 00:04:03,440
[Mahasiswa] n - 2. >> Ya.

55
00:04:03,440 --> 00:04:11,640
Dan yang ketiga akan menjadi n - 3, dan kemudian untuk kenyamanan saya akan menulis dua terakhir

56
00:04:11,640 --> 00:04:15,270
sebagai maka kita akan perlu untuk membuat 2 swap dan 1 swap.

57
00:04:15,270 --> 00:04:19,899
Saya kira yang terakhir mungkin atau mungkin tidak benar-benar perlu terjadi.

58
00:04:19,899 --> 00:04:22,820
Apakah swap? Saya tidak tahu.

59
00:04:22,820 --> 00:04:26,490
Jadi ini adalah jumlah total swap atau setidaknya perbandingan Anda harus membuat.

60
00:04:26,490 --> 00:04:29,910
Bahkan jika Anda tidak swap, Anda masih perlu untuk membandingkan nilai.

61
00:04:29,910 --> 00:04:33,910
Jadi ada n - 1 perbandingan dalam jangka pertama melalui array.

62
00:04:33,910 --> 00:04:42,050
Jika Anda mengatur ulang hal-hal ini, mari kita benar-benar membuatnya enam hal sehingga hal-hal menumpuk dengan baik,

63
00:04:42,050 --> 00:04:44,790
dan kemudian saya akan melakukan 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Jadi hanya menata ulang jumlah ini, kita ingin melihat berapa banyak perbandingan kita buat

65
00:04:49,910 --> 00:04:52,700
dalam algoritma keseluruhan.

66
00:04:52,700 --> 00:04:56,550
Jadi jika kita membawa orang-orang ini ke sini,

67
00:04:56,550 --> 00:05:07,470
maka kita masih hanya menjumlahkan perbandingan namun banyak ada.

68
00:05:07,470 --> 00:05:13,280
Tetapi jika kita jumlah ini dan kami jumlah ini dan kami jumlah tersebut,

69
00:05:13,280 --> 00:05:18,130
itu masih masalah yang sama. Kami hanya jumlah kelompok-kelompok tertentu.

70
00:05:18,130 --> 00:05:22,400
>> Jadi sekarang kita menjumlahkan 3 s n. Ini bukan hanya 3 s n.

71
00:05:22,400 --> 00:05:27,650
Ini selalu akan menjadi n / 2 n.

72
00:05:27,650 --> 00:05:29,430
Jadi di sini kita kebetulan memiliki 6.

73
00:05:29,430 --> 00:05:34,830
Jika kita memiliki 10 hal, maka kita bisa melakukan pengelompokan ini untuk 5 pasang yang berbeda dari hal-hal

74
00:05:34,830 --> 00:05:37,180
dan berakhir dengan n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
Jadi Anda akan selalu mendapatkan n / 2 n, dan jadi ini kita akan menuliskan itu keluar ke n kuadrat / 2.

76
00:05:45,840 --> 00:05:48,890
Dan jadi meskipun itu faktor setengah, yang kebetulan datang di

77
00:05:48,890 --> 00:05:54,190
karena dari fakta bahwa melalui setiap iterasi atas array kita membandingkan 1 kurang

78
00:05:54,190 --> 00:05:58,040
jadi itu bagaimana kita mendapatkan lebih dari 2, tetapi masih n kuadrat.

79
00:05:58,040 --> 00:06:01,650
Kami tidak peduli tentang faktor konstan setengah.

80
00:06:01,650 --> 00:06:07,760
Jadi banyak hal O besar seperti ini bergantung pada hanya semacam melakukan semacam ini matematika,

81
00:06:07,760 --> 00:06:12,260
berhitung aritmatika dan barang-barang seri geometris,

82
00:06:12,260 --> 00:06:17,750
tapi kebanyakan dari mereka dalam kursus ini adalah cukup sederhana.

83
00:06:17,750 --> 00:06:19,290
Oke.

84
00:06:19,290 --> 00:06:24,430
Mengapa insertion sort di Omega n? Apa omega artinya?

85
00:06:24,430 --> 00:06:27,730
[Dua siswa berbicara sekaligus - dimengerti] Ya >>.

86
00:06:27,730 --> 00:06:30,630
Omega Anda bisa memikirkan sebagai batas bawah.

87
00:06:30,630 --> 00:06:36,550
>> Jadi tidak peduli seberapa efisien penyisipan algoritma semacam Anda,

88
00:06:36,550 --> 00:06:41,810
terlepas dari daftar yang disahkan pada, selalu memiliki untuk membandingkan setidaknya n hal

89
00:06:41,810 --> 00:06:44,620
atau harus iterate atas hal-hal n.

90
00:06:44,620 --> 00:06:47,280
Mengapa demikian?

91
00:06:47,280 --> 00:06:51,190
[Mahasiswa] Karena jika daftar tersebut sudah diurutkan, kemudian melalui iterasi pertama

92
00:06:51,190 --> 00:06:54,080
Anda hanya dapat menjamin bahwa elemen pertama adalah yang paling,

93
00:06:54,080 --> 00:06:56,490
dan iterasi kedua Anda hanya dapat menjamin dua yang pertama adalah

94
00:06:56,490 --> 00:07:00,010
karena Anda tidak tahu bahwa sisa daftar diurutkan. >> Ya.

95
00:07:00,010 --> 00:07:08,910
Jika Anda lulus dalam daftar benar-benar diurutkan, setidaknya Anda harus pergi ke semua elemen

96
00:07:08,910 --> 00:07:12,180
untuk melihat bahwa tidak ada yang perlu dipindahkan sekitar.

97
00:07:12,180 --> 00:07:14,720
Jadi melewati daftar dan mengatakan oh, ini sudah diurutkan,

98
00:07:14,720 --> 00:07:18,240
tidak mungkin bagi Anda untuk tahu itu diurutkan sampai Anda memeriksa setiap elemen

99
00:07:18,240 --> 00:07:20,660
untuk melihat bahwa mereka berada di urutan diurutkan.

100
00:07:20,660 --> 00:07:25,290
Jadi batas bawah pada insertion sort adalah Omega dari n.

101
00:07:25,290 --> 00:07:28,210
Apa kasus terburuk waktu berjalan semacam gabungan,

102
00:07:28,210 --> 00:07:31,390
kasus terburuk O menjadi besar lagi?

103
00:07:31,390 --> 00:07:37,660
Jadi dalam skenario terburuk, bagaimana gabungan semacam dijalankan?

104
00:07:42,170 --> 00:07:43,690
[Mahasiswa] N log n. >> Ya.

105
00:07:43,690 --> 00:07:49,990
Algoritma tercepat pemilahan umum n log n. Anda tidak bisa berbuat lebih baik.

106
00:07:51,930 --> 00:07:55,130
>> Ada kasus-kasus khusus, dan jika kita punya waktu hari ini - tapi kami mungkin won't -

107
00:07:55,130 --> 00:07:59,330
kita bisa melihat salah satu yang tidak lebih baik dari n log n.

108
00:07:59,330 --> 00:08:04,050
Tetapi dalam kasus umum, Anda tidak dapat melakukan lebih baik daripada n log n.

109
00:08:04,050 --> 00:08:09,680
Dan menggabungkan semacam kebetulan yang Anda harus tahu untuk kursus yang n log n.

110
00:08:09,680 --> 00:08:13,260
Dan jadi kita benar-benar akan menerapkan hari ini.

111
00:08:13,260 --> 00:08:18,070
Dan akhirnya, dalam waktu tidak lebih dari tiga kalimat, bagaimana cara kerja semacam seleksi?

112
00:08:18,070 --> 00:08:20,370
Apakah seseorang ingin menjawabnya, dan saya akan menghitung kalimat Anda

113
00:08:20,370 --> 00:08:22,390
karena jika Anda pergi lebih dari 3 -

114
00:08:25,530 --> 00:08:28,330
Apakah ada yang ingat semacam seleksi?

115
00:08:31,280 --> 00:08:37,809
Seleksi semacam ini biasanya cukup mudah diingat hanya dari nama.

116
00:08:37,809 --> 00:08:45,350
Anda hanya iterate atas array, menemukan apa nilai terbesar adalah atau terkecil -

117
00:08:45,350 --> 00:08:47,290
urutan apapun yang Anda menyortir masuk

118
00:08:47,290 --> 00:08:50,750
Jadi katakanlah kita sedang disortir dari terkecil sampai terbesar.

119
00:08:50,750 --> 00:08:55,250
Anda iterate atas array, mencari apa pun elemen minimum,

120
00:08:55,250 --> 00:08:59,750
pilih, dan kemudian hanya swap apa yang ada di tempat pertama.

121
00:08:59,750 --> 00:09:04,090
Dan kemudian pada lulus kedua atas array, mencari elemen minimum lagi,

122
00:09:04,090 --> 00:09:07,490
pilih, dan kemudian swap dengan apa yang ada di posisi kedua.

123
00:09:07,490 --> 00:09:10,650
Jadi kita hanya memilih dan memilih nilai minimum

124
00:09:10,650 --> 00:09:16,050
dan memasukkan mereka ke depan array sampai itu diurutkan.

125
00:09:19,210 --> 00:09:21,560
Pertanyaan itu?

126
00:09:21,560 --> 00:09:25,710
>> Ini pasti muncul dalam bentuk Anda harus mengisi ketika Anda mengirimkan pset tersebut.

127
00:09:29,010 --> 00:09:32,360
Mereka pada dasarnya jawaban kepada mereka.

128
00:09:32,360 --> 00:09:34,230
Oke, jadi sekarang masalah coding.

129
00:09:34,230 --> 00:09:40,140
Saya sudah dikirim keluar melalui email - Apakah ada yang tidak mendapatkan email itu? Oke.

130
00:09:40,140 --> 00:09:46,630
Saya sudah dikirim keluar melalui email ruang yang kita akan menggunakan,

131
00:09:46,630 --> 00:09:52,120
dan jika Anda klik pada nama saya - jadi saya pikir saya akan berada di bagian bawah

132
00:09:52,120 --> 00:09:57,170
karena r mundur - tetapi jika Anda klik pada nama saya Anda akan melihat 2 revisi.

133
00:09:57,170 --> 00:10:02,650
Revisi 1 ini akan saya sudah disalin dan disisipkan kode ke Spaces

134
00:10:02,650 --> 00:10:06,900
untuk hal pencarian Anda akan harus melaksanakan.

135
00:10:06,900 --> 00:10:10,540
Dan Revisi 2 akan menjadi hal semacam itu kami menerapkan setelah itu.

136
00:10:10,540 --> 00:10:15,770
Jadi, Anda dapat mengklik Revisi saya 1 dan bekerja dari sana.

137
00:10:17,350 --> 00:10:22,060
Dan sekarang kita ingin menerapkan pencarian biner.

138
00:10:22,060 --> 00:10:26,470
>> Apakah ada yang ingin hanya memberikan penjelasan tingkat tinggi pseudocode

139
00:10:26,470 --> 00:10:31,440
dari apa yang kita akan lakukan untuk pencarian? Ya.

140
00:10:31,440 --> 00:10:36,170
[Mahasiswa] Anda hanya mengambil bagian tengah dari array dan melihat apakah apa yang Anda cari

141
00:10:36,170 --> 00:10:38,650
kurang dari itu atau lebih dari itu.

142
00:10:38,650 --> 00:10:41,080
Dan jika itu kurang, Anda pergi ke babak yang kurang,

143
00:10:41,080 --> 00:10:44,750
dan jika lebih, Anda pergi ke babak yang lebih dan anda ulangi sampai Anda hanya mendapatkan satu hal.

144
00:10:44,750 --> 00:10:46,570
[Bowden] Ya.

145
00:10:46,570 --> 00:10:51,320
Perhatikan bahwa nomor array kita sudah diurutkan,

146
00:10:51,320 --> 00:10:57,190
dan sehingga berarti bahwa kita dapat mengambil keuntungan dari itu dan pertama-tama kita bisa memeriksa,

147
00:10:57,190 --> 00:11:00,390
oke, saya sedang mencari nomor 50.

148
00:11:00,390 --> 00:11:03,720
Jadi aku bisa pergi ke tengah.

149
00:11:03,720 --> 00:11:07,380
Tengah sulit untuk menentukan ketika itu bahkan jumlah hal,

150
00:11:07,380 --> 00:11:10,820
tapi mari kita katakan saja kita akan selalu memotong ke tengah.

151
00:11:10,820 --> 00:11:14,420
Jadi di sini kita memiliki 8 hal, sehingga tengah akan menjadi 16.

152
00:11:14,420 --> 00:11:17,330
Saya sedang mencari 50, jadi 50 lebih besar dari 16.

153
00:11:17,330 --> 00:11:21,310
Jadi sekarang saya pada dasarnya dapat memperlakukan array saya sebagai elemen-elemen ini.

154
00:11:21,310 --> 00:11:23,450
Aku bisa membuang segala sesuatu dari 16 lebih.

155
00:11:23,450 --> 00:11:27,440
Sekarang array saya hanya ini 4 elemen, dan saya ulangi.

156
00:11:27,440 --> 00:11:31,910
Jadi saya ingin mencari tengah lagi, yang akan menjadi 42.

157
00:11:31,910 --> 00:11:34,730
42 kurang dari 50, sehingga saya dapat membuang dua elemen.

158
00:11:34,730 --> 00:11:36,890
Ini adalah array tersisa saya.

159
00:11:36,890 --> 00:11:38,430
Aku akan menemukan tengah lagi.

160
00:11:38,430 --> 00:11:42,100
Saya kira 50 adalah contoh buruk karena saya selalu membuang hal-hal ke kiri,

161
00:11:42,100 --> 00:11:48,280
tetapi dengan ukuran yang sama, jika saya sedang mencari sesuatu

162
00:11:48,280 --> 00:11:52,100
dan itu kurang dari elemen Saat ini saya melihat,

163
00:11:52,100 --> 00:11:55,080
maka aku akan membuang segala sesuatu ke kanan.

164
00:11:55,080 --> 00:11:58,150
Jadi sekarang kita perlu untuk mengimplementasikan itu.

165
00:11:58,150 --> 00:12:02,310
Perhatikan bahwa kita harus lulus dalam ukuran.

166
00:12:02,310 --> 00:12:06,730
Kita juga bisa tidak perlu keras-kode ukuran.

167
00:12:06,730 --> 00:12:11,640
Jadi jika kita menyingkirkan # define -

168
00:12:19,630 --> 00:12:21,430
Oke.

169
00:12:21,430 --> 00:12:27,180
Bagaimana saya bisa baik mencari tahu apa ukuran dari array angka saat ini?

170
00:12:27,180 --> 00:12:30,950
>> Berapa banyak elemen dalam array nomor?

171
00:12:30,950 --> 00:12:33,630
[Mahasiswa] Bilangan, kurung,. Panjang?

172
00:12:33,630 --> 00:12:36,600
[Bowden] Itu tidak ada di C.

173
00:12:36,600 --> 00:12:38,580
Perlu. Panjang.

174
00:12:38,580 --> 00:12:42,010
Array tidak memiliki sifat, sehingga tidak ada properti panjang array

175
00:12:42,010 --> 00:12:45,650
yang hanya akan memberi Anda namun lama akan terjadi.

176
00:12:48,180 --> 00:12:51,620
[Mahasiswa] Lihat berapa banyak memori yang dimilikinya dan dibagi dengan berapa banyak - Yeah >>.

177
00:12:51,620 --> 00:12:55,810
Jadi bagaimana kita bisa melihat berapa banyak memori yang dimilikinya? >> [Mahasiswa] sizeof. >> Ya, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof adalah operator yang akan mengembalikan ukuran dari array angka.

179
00:13:01,680 --> 00:13:10,060
Dan itu akan menjadi bilangan bulat namun banyak ada kali ukuran integer

180
00:13:10,060 --> 00:13:14,050
karena itulah berapa banyak memori itu benar-benar mengambil.

181
00:13:14,050 --> 00:13:17,630
Jadi jika saya ingin beberapa hal dalam array,

182
00:13:17,630 --> 00:13:20,560
maka aku akan ingin membagi dengan ukuran integer.

183
00:13:22,820 --> 00:13:26,010
Oke. Jadi yang memungkinkan saya lulus dalam ukuran sini.

184
00:13:26,010 --> 00:13:29,430
Mengapa saya harus lulus dalam ukuran sama sekali?

185
00:13:29,430 --> 00:13:38,570
Kenapa aku tidak bisa hanya melakukan di sini ukuran int = sizeof (tumpukan jerami) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
Mengapa hal ini tidak bekerja?

187
00:13:41,490 --> 00:13:44,470
[Mahasiswa] Ini bukan variabel global.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack ada dan kami sedang lewat di angka sebagai tumpukan jerami,

189
00:13:51,540 --> 00:13:54,700
dan ini adalah semacam bayangan apa yang akan datang. Ya.

190
00:13:54,700 --> 00:14:00,170
[Mahasiswa] Haystack hanyalah referensi untuk itu, sehingga akan kembali seberapa besar referensi yang.

191
00:14:00,170 --> 00:14:02,150
Ya.

192
00:14:02,150 --> 00:14:09,000
Saya ragu dalam kuliah bahwa Anda telah melihat tumpukan belum benar-benar, benar?

193
00:14:09,000 --> 00:14:11,270
Kami baru saja berbicara tentang hal itu.

194
00:14:11,270 --> 00:14:16,090
Jadi tumpukan adalah di mana semua variabel Anda akan disimpan.

195
00:14:16,090 --> 00:14:19,960
>> Setiap memori yang dialokasikan untuk variabel lokal akan di stack,

196
00:14:19,960 --> 00:14:24,790
dan fungsi masing-masing mendapat ruang sendiri di tumpukan, stack frame sendiri adalah apa namanya.

197
00:14:24,790 --> 00:14:31,590
Jadi utama memiliki stack frame, dan di dalamnya akan ada array angka,

198
00:14:31,590 --> 00:14:34,270
dan itu akan menjadi ukuran sizeof (angka).

199
00:14:34,270 --> 00:14:38,180
Ini akan memiliki ukuran angka dibagi dengan ukuran elemen,

200
00:14:38,180 --> 00:14:42,010
tapi itu semua hidup dalam bingkai tumpukan utama itu.

201
00:14:42,010 --> 00:14:45,190
Ketika kita sebut pencarian, pencarian akan stack frame sendiri,

202
00:14:45,190 --> 00:14:48,840
ruang sendiri untuk menyimpan semua variabel lokal.

203
00:14:48,840 --> 00:14:56,420
Tapi argumen ini - sehingga tumpukan jerami bukanlah salinan dari seluruh array.

204
00:14:56,420 --> 00:15:00,990
Kami tidak lulus dalam seluruh array sebagai copy ke dalam pencarian.

205
00:15:00,990 --> 00:15:04,030
Itu hanya melewati referensi ke array.

206
00:15:04,030 --> 00:15:11,470
Jadi pencarian dapat mengakses nomor melalui referensi ini.

207
00:15:11,470 --> 00:15:17,100
Ini masih mengakses hal-hal yang hidup dalam stack frame utama itu,

208
00:15:17,100 --> 00:15:22,990
tetapi pada dasarnya, ketika kita sampai ke pointer, yang harus segera,

209
00:15:22,990 --> 00:15:24,980
ini adalah apa pointer.

210
00:15:24,980 --> 00:15:29,400
Pointer hanya referensi untuk hal-hal, dan Anda dapat menggunakan pointer untuk mengakses hal-hal

211
00:15:29,400 --> 00:15:32,030
yang berada dalam bingkai tumpukan hal-hal lain '.

212
00:15:32,030 --> 00:15:37,660
Jadi meskipun angka adalah lokal untuk main, kita masih dapat mengaksesnya melalui pointer ini.

213
00:15:37,660 --> 00:15:41,770
Tapi karena itu hanya pointer dan itu hanya referensi,

214
00:15:41,770 --> 00:15:45,040
sizeof (tumpukan jerami) hanya mengembalikan ukuran dari referensi itu sendiri.

215
00:15:45,040 --> 00:15:47,950
Ini tidak mengembalikan ukuran hal itu menunjuk ke.

216
00:15:47,950 --> 00:15:51,110
Ini tidak mengembalikan ukuran sebenarnya angka.

217
00:15:51,110 --> 00:15:55,660
Dan jadi ini tidak akan bekerja seperti yang kita inginkan.

218
00:15:55,660 --> 00:15:57,320
>> Pertanyaan itu?

219
00:15:57,320 --> 00:16:03,250
Pointer akan pergi ke detail signifikan lebih berdarah dalam beberapa pekan yang akan datang.

220
00:16:06,750 --> 00:16:13,740
Dan inilah mengapa banyak hal yang Anda lihat, hal pencarian sebagian besar atau hal-hal semacam,

221
00:16:13,740 --> 00:16:16,990
mereka hampir semua akan perlu mengambil ukuran sebenarnya dari array,

222
00:16:16,990 --> 00:16:20,440
karena dalam C, kita tidak tahu apa ukuran array.

223
00:16:20,440 --> 00:16:22,720
Anda perlu secara manual lulus masuk

224
00:16:22,720 --> 00:16:27,190
Dan Anda tidak dapat secara manual lulus dalam seluruh array karena Anda hanya lewat dalam referensi

225
00:16:27,190 --> 00:16:30,390
dan itu tidak bisa mendapatkan ukuran dari referensi.

226
00:16:30,390 --> 00:16:32,300
Oke.

227
00:16:32,300 --> 00:16:38,160
Jadi sekarang kita ingin menerapkan apa yang telah dijelaskan sebelumnya.

228
00:16:38,160 --> 00:16:41,530
Anda dapat bekerja di dalamnya selama satu menit,

229
00:16:41,530 --> 00:16:45,250
dan Anda tidak perlu khawatir tentang mendapatkan segalanya dengan sempurna 100% bekerja.

230
00:16:45,250 --> 00:16:51,410
Hanya menulis dengan pseudocode setengah untuk bagaimana Anda pikir itu harus bekerja.

231
00:16:52,000 --> 00:16:53,630
Oke.

232
00:16:53,630 --> 00:16:56,350
Tidak perlu harus benar-benar dilakukan dengan ini.

233
00:16:56,350 --> 00:17:02,380
Tapi tidak ada yang merasa nyaman dengan apa yang mereka miliki sejauh ini,

234
00:17:02,380 --> 00:17:05,599
seperti sesuatu yang kita dapat bekerja dengan bersama-sama?

235
00:17:05,599 --> 00:17:09,690
Apakah ada yang ingin menjadi sukarelawan? Atau aku akan memilih secara acak.

236
00:17:12,680 --> 00:17:18,599
Ini tidak harus menjadi benar dengan setiap tindakan, tetapi sesuatu yang kita dapat memodifikasi ke dalam keadaan bekerja.

237
00:17:18,599 --> 00:17:20,720
[Mahasiswa] Tentu. Oke >>.

238
00:17:20,720 --> 00:17:27,220
Jadi bisa Anda menyimpan revisi dengan mengklik ikon Simpan kecil.

239
00:17:27,220 --> 00:17:29,950
Kau Ramya, kan? >> [Mahasiswa] Ya. >> [Bowden] Oke.

240
00:17:29,950 --> 00:17:35,140
Jadi sekarang saya dapat melihat revisi Anda dan semua orang dapat menarik revisi.

241
00:17:35,140 --> 00:17:38,600
Dan di sini kita memiliki - Oke.

242
00:17:38,600 --> 00:17:43,160
Jadi Ramya pergi dengan solusi rekursif, yang pasti solusi yang valid.

243
00:17:43,160 --> 00:17:44,970
Ada dua cara yang dapat Anda lakukan masalah ini.

244
00:17:44,970 --> 00:17:48,060
Anda dapat melakukannya iteratif atau rekursif.

245
00:17:48,060 --> 00:17:53,860
Sebagian besar masalah yang Anda temui yang bisa dilakukan secara rekursif juga bisa dilakukan secara iteratif.

246
00:17:53,860 --> 00:17:58,510
Jadi di sini kita sudah melakukannya secara rekursif.

247
00:17:58,510 --> 00:18:03,730
>> Apakah seseorang ingin mendefinisikan apa artinya untuk membuat fungsi rekursif?

248
00:18:07,210 --> 00:18:08,920
[Mahasiswa] Bila Anda memiliki fungsi panggilan sendiri

249
00:18:08,920 --> 00:18:13,470
dan kemudian menyebut dirinya sampai keluar dengan benar dan benar. >> Ya.

250
00:18:13,470 --> 00:18:17,680
Sebuah fungsi rekursif hanya fungsi yang memanggil dirinya sendiri.

251
00:18:17,680 --> 00:18:24,140
Ada tiga hal besar yang fungsi rekursif harus memiliki.

252
00:18:24,140 --> 00:18:27,310
Yang pertama adalah jelas, itu menyebut dirinya.

253
00:18:27,310 --> 00:18:29,650
Yang kedua adalah kasus dasar.

254
00:18:29,650 --> 00:18:33,390
Jadi di beberapa titik fungsi perlu berhenti menyebut dirinya,

255
00:18:33,390 --> 00:18:35,610
dan itulah yang kasus dasar adalah untuk.

256
00:18:35,610 --> 00:18:43,860
Jadi di sini kita tahu bahwa kita harus berhenti, kita harus menyerah dalam pencarian kami

257
00:18:43,860 --> 00:18:48,150
saat start sama end - dan kami akan pergi ke apa artinya.

258
00:18:48,150 --> 00:18:52,130
Tapi akhirnya, hal terakhir yang penting untuk fungsi rekursif:

259
00:18:52,130 --> 00:18:59,250
fungsi entah bagaimana harus mendekati kasus dasar.

260
00:18:59,250 --> 00:19:04,140
Seperti jika Anda tidak benar-benar memperbarui apa-apa ketika Anda membuat panggilan rekursif kedua,

261
00:19:04,140 --> 00:19:07,880
jika Anda benar-benar hanya memanggil fungsi lagi dengan argumen yang sama

262
00:19:07,880 --> 00:19:10,130
dan tidak ada variabel global telah berubah atau apa,

263
00:19:10,130 --> 00:19:14,430
Anda tidak akan pernah mencapai kasus dasar, dalam hal yang buruk.

264
00:19:14,430 --> 00:19:17,950
Ini akan menjadi rekursi tak terbatas dan stack overflow.

265
00:19:17,950 --> 00:19:24,330
Tapi di sini kita melihat bahwa pembaruan yang terjadi karena kita mulai memperbarui + end / 2,

266
00:19:24,330 --> 00:19:28,180
kami meng-update argumen akhir di sini, kami meng-update argumen start di sini.

267
00:19:28,180 --> 00:19:32,860
Jadi dalam semua panggilan rekursif kita memperbarui sesuatu. Oke.

268
00:19:32,860 --> 00:19:38,110
Apakah Anda ingin berjalan kita melalui solusi Anda? Tentu >>.

269
00:19:38,110 --> 00:19:44,270
Saya menggunakan SearchHelp sehingga setiap kali saya membuat panggilan fungsi

270
00:19:44,270 --> 00:19:47,910
Saya memiliki awal di mana saya sedang mencari dalam array dan akhir

271
00:19:47,910 --> 00:19:49,380
di mana saya sedang mencari array.

272
00:19:49,380 --> 00:19:55,330
>> Pada setiap langkah di mana itu mengatakan itu adalah elemen tengah, yang merupakan awal + akhir / 2,

273
00:19:55,330 --> 00:19:58,850
adalah bahwa sama dengan apa yang kita cari?

274
00:19:58,850 --> 00:20:04,650
Dan jika sudah, maka kami menemukan itu, dan saya rasa itu akan diteruskan sampai tingkat rekursi.

275
00:20:04,650 --> 00:20:12,540
Dan jika itu tidak benar, kemudian kita cek apakah nilai tengah dari array terlalu besar,

276
00:20:12,540 --> 00:20:19,320
dalam hal ini kita melihat kiri setengah dari array dengan pergi dari awal sampai indeks tengah.

277
00:20:19,320 --> 00:20:22,710
Dan jika kita melakukan setengah akhir.

278
00:20:22,710 --> 00:20:24,740
[Bowden] Oke.

279
00:20:24,740 --> 00:20:27,730
Boleh juga.

280
00:20:27,730 --> 00:20:36,640
Oke, jadi beberapa hal, dan benar-benar, ini adalah hal yang sangat tinggi tingkat

281
00:20:36,640 --> 00:20:41,270
bahwa Anda tidak akan pernah perlu tahu untuk kursus ini, tapi itu benar.

282
00:20:41,270 --> 00:20:46,080
Fungsi rekursif, Anda selalu mendengar bahwa mereka transaksi yang buruk

283
00:20:46,080 --> 00:20:51,160
karena jika Anda rekursif menyebut dirimu kali terlalu banyak, Anda mendapatkan stack overflow

284
00:20:51,160 --> 00:20:54,990
karena, seperti yang saya katakan sebelumnya, setiap fungsi mendapat tumpukan bingkai sendiri.

285
00:20:54,990 --> 00:20:59,500
Jadi setiap panggilan dari fungsi rekursif mendapat tumpukan bingkai sendiri.

286
00:20:59,500 --> 00:21:04,140
Jadi jika Anda membuat panggilan rekursif 1.000, Anda mendapatkan 1.000 frame stack,

287
00:21:04,140 --> 00:21:08,390
dan cepat Anda memimpin untuk memiliki frame tumpukan terlalu banyak dan hal-hal hanya istirahat.

288
00:21:08,390 --> 00:21:13,480
Jadi itulah mengapa fungsi rekursif umumnya buruk.

289
00:21:13,480 --> 00:21:19,370
Tapi ada subset bagus fungsi rekursif disebut ekor-rekursif fungsi,

290
00:21:19,370 --> 00:21:26,120
dan ini terjadi untuk menjadi salah satu contoh di mana jika kompilator pemberitahuan ini

291
00:21:26,120 --> 00:21:29,920
dan seharusnya, saya pikir - di dentang jika Anda lulus dengan O2-flag

292
00:21:29,920 --> 00:21:33,250
maka akan melihat ini adalah ekor rekursif dan membuat hal-hal yang baik.

293
00:21:33,250 --> 00:21:40,050
>> Ini akan menggunakan kembali stack frame yang sama berulang-ulang untuk setiap panggilan rekursif.

294
00:21:40,050 --> 00:21:47,010
Dan jadi karena Anda menggunakan stack frame yang sama, Anda tidak perlu khawatir tentang

295
00:21:47,010 --> 00:21:51,690
pernah menumpuk meluap, dan pada saat yang sama, seperti Anda katakan sebelumnya,

296
00:21:51,690 --> 00:21:56,380
di mana setelah Anda kembali benar, maka harus kembali sampai semua frame tumpukan

297
00:21:56,380 --> 00:22:01,740
dan panggilan 10 untuk SearchHelp harus kembali ke 9, harus kembali ke 8.

298
00:22:01,740 --> 00:22:05,360
Sehingga tidak perlu terjadi bila fungsi rekursif ekor.

299
00:22:05,360 --> 00:22:13,740
Dan jadi apa yang membuat ekor fungsi rekursif adalah pemberitahuan bahwa untuk setiap panggilan yang diberikan kepada searchHelp

300
00:22:13,740 --> 00:22:18,470
panggilan rekursif bahwa itu adalah apa yang membuat itu kembali.

301
00:22:18,470 --> 00:22:25,290
Jadi dalam panggilan pertama untuk SearchHelp, kita baik segera kembali palsu,

302
00:22:25,290 --> 00:22:29,590
segera kembali benar, atau kita membuat panggilan rekursif untuk SearchHelp

303
00:22:29,590 --> 00:22:33,810
di mana apa yang kita kembali adalah apa panggilan yang kembali.

304
00:22:33,810 --> 00:22:51,560
Dan kita tidak bisa melakukan ini jika kita melakukan sesuatu seperti int x = SearchHelp, kembali x * 2,

305
00:22:51,560 --> 00:22:55,440
hanya beberapa perubahan acak.

306
00:22:55,440 --> 00:23:01,470
>> Jadi sekarang ini panggilan rekursif, int ini x = SearchHelp panggilan rekursif,

307
00:23:01,470 --> 00:23:05,740
tidak lagi ekor rekursif karena sebenarnya tidak harus kembali

308
00:23:05,740 --> 00:23:10,400
kembali ke stack frame sebelumnya sehingga bahwa panggilan sebelumnya untuk fungsi

309
00:23:10,400 --> 00:23:13,040
kemudian dapat melakukan sesuatu dengan nilai kembali.

310
00:23:13,040 --> 00:23:22,190
Jadi ini bukan ekor rekursif, tapi apa yang kita miliki sebelum yang baik ekor rekursif. Ya.

311
00:23:22,190 --> 00:23:27,000
[Mahasiswa] Bukankah kasus dasar kedua diperiksa terlebih dahulu

312
00:23:27,000 --> 00:23:30,640
karena mungkin ada situasi di mana ketika Anda lulus argumen

313
00:23:30,640 --> 00:23:35,770
Anda telah mulai akhir =, tetapi mereka nilai jarum.

314
00:23:35,770 --> 00:23:47,310
Pertanyaan itu tidak bisa kita lari ke kasus di mana akhirnya adalah nilai jarum

315
00:23:47,310 --> 00:23:52,000
atau mulai akhir =, tepat, mulai akhir =

316
00:23:52,000 --> 00:23:59,480
dan Anda belum benar-benar memeriksa nilai tersebut belum,

317
00:23:59,480 --> 00:24:03,910
kemudian mulai + end / 2 hanya akan menjadi nilai yang sama.

318
00:24:03,910 --> 00:24:07,890
Tapi kami sudah kembali palsu dan kami tidak pernah benar-benar memeriksa nilai.

319
00:24:07,890 --> 00:24:14,240
Jadi setidaknya, pada panggilan pertama, jika ukuran 0, maka kita ingin kembali palsu.

320
00:24:14,240 --> 00:24:17,710
Tetapi jika ukuran 1, maka awal tidak akan berakhir sama,

321
00:24:17,710 --> 00:24:19,820
dan kami setidaknya akan memeriksa satu unsur.

322
00:24:19,820 --> 00:24:26,750
Tapi saya pikir Anda benar dalam bahwa kita bisa berakhir dalam kasus di mana mulai akhir + / 2,

323
00:24:26,750 --> 00:24:31,190
start akhirnya menjadi sama dengan start + end / 2,

324
00:24:31,190 --> 00:24:35,350
tapi kami tidak pernah benar-benar memeriksa elemen.

325
00:24:35,350 --> 00:24:44,740
>> Jadi jika kita periksa dulu adalah elemen tengah nilai yang kita cari,

326
00:24:44,740 --> 00:24:47,110
maka kita segera bisa kembali benar.

327
00:24:47,110 --> 00:24:50,740
Lain jika mereka sama, maka tidak ada gunanya melanjutkan

328
00:24:50,740 --> 00:24:58,440
karena kita hanya akan update ke kasus di mana kita berada pada array tunggal-elemen.

329
00:24:58,440 --> 00:25:01,110
Jika elemen tunggal bukanlah satu yang kita cari,

330
00:25:01,110 --> 00:25:03,530
maka semuanya salah. Ya.

331
00:25:03,530 --> 00:25:08,900
[Mahasiswa] Masalahnya adalah bahwa karena ukuran sebenarnya lebih besar dari jumlah elemen dalam array,

332
00:25:08,900 --> 00:25:13,070
sudah ada offset ke - >> Jadi akan ukuran -

333
00:25:13,070 --> 00:25:19,380
[Mahasiswa] Katakanlah jika array adalah ukuran 0, maka SearchHelp sebenarnya akan memeriksa tumpukan jerami dari 0

334
00:25:19,380 --> 00:25:21,490
pada panggilan pertama.

335
00:25:21,490 --> 00:25:25,300
Array memiliki ukuran 0, sehingga 0 adalah - >> Ya.

336
00:25:25,300 --> 00:25:30,750
Ada hal lain yang - mungkin baik. Mari kita pikirkan.

337
00:25:30,750 --> 00:25:40,120
Jadi jika array memiliki 10 elemen dan yang tengah kita akan memeriksa adalah indeks 5,

338
00:25:40,120 --> 00:25:45,700
jadi kita memeriksa 5, dan mari kita mengatakan bahwa nilai kurang.

339
00:25:45,700 --> 00:25:50,720
Jadi kita membuang segalanya dari 5 dan seterusnya.

340
00:25:50,720 --> 00:25:54,030
Jadi mulailah + end / 2 akan menjadi akhir baru kami,

341
00:25:54,030 --> 00:25:57,450
sehingga yeah, itu selalu akan tinggal di luar akhir array.

342
00:25:57,450 --> 00:26:03,570
Jika itu terjadi jika itu genap atau ganjil, maka kita akan memeriksa, katakanlah, 4,

343
00:26:03,570 --> 00:26:05,770
tapi kami masih membuang -

344
00:26:05,770 --> 00:26:13,500
Jadi ya, akhirnya selalu akan berada di luar akhir yang sebenarnya dari array.

345
00:26:13,500 --> 00:26:18,350
Jadi unsur-unsur yang kita berfokus pada, akhir selalu akan menjadi satu setelah itu.

346
00:26:18,350 --> 00:26:24,270
Dan jadi jika awal tidak pernah berakhir yang sama, kita berada dalam berbagai ukuran 0.

347
00:26:24,270 --> 00:26:35,600
>> Hal lain yang saya berpikir adalah kita memperbarui start untuk start + end / 2,

348
00:26:35,600 --> 00:26:44,020
jadi ini adalah kasus yang Saya mengalami kesulitan dengan, di mana mulai + end / 2

349
00:26:44,020 --> 00:26:46,820
adalah elemen kita memeriksa.

350
00:26:46,820 --> 00:26:58,150
Katakanlah kita memiliki array 10-elemen. Apapun.

351
00:26:58,150 --> 00:27:03,250
Jadi mulailah + end / 2 akan menjadi sesuatu seperti ini,

352
00:27:03,250 --> 00:27:07,060
dan kalau itu tidak nilai, katakanlah kita ingin mengupdate.

353
00:27:07,060 --> 00:27:10,060
Nilai lebih besar, jadi kami ingin melihat ini setengah dari array.

354
00:27:10,060 --> 00:27:15,910
Jadi bagaimana kita meng-update start, kami meng-update mulai sekarang menjadi elemen ini.

355
00:27:15,910 --> 00:27:23,790
Tapi ini masih dapat bekerja, atau setidaknya, Anda bisa melakukan start + end / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Mahasiswa] Anda tidak perlu mulai akhir + [tak terdengar] >> Ya.

357
00:27:27,850 --> 00:27:33,240
Kami telah memeriksa elemen ini dan tahu itu bukan satu yang kita cari.

358
00:27:33,240 --> 00:27:36,800
Jadi kita tidak perlu memperbarui mulai menjadi elemen ini.

359
00:27:36,800 --> 00:27:39,560
Kami hanya bisa melewati itu dan memperbarui mulai menjadi elemen ini.

360
00:27:39,560 --> 00:27:46,060
Dan apakah ada yang pernah kasus, katakanlah, bahwa ini adalah akhir,

361
00:27:46,060 --> 00:27:53,140
sehingga kemudian mulai akan hal ini, mulailah + end / 2 akan hal ini,

362
00:27:53,140 --> 00:28:00,580
mulai akhir + - Ya, saya pikir itu bisa berakhir di rekursi tak terbatas.

363
00:28:00,580 --> 00:28:12,690
Mari kita mengatakan itu hanya sebuah array ukuran 2 atau array ukuran 1. Saya pikir ini akan bekerja.

364
00:28:12,690 --> 00:28:19,490
Jadi saat ini, awal adalah bahwa elemen dan akhir adalah 1 melampauinya.

365
00:28:19,490 --> 00:28:24,110
Jadi elemen yang kita akan memeriksa satu ini,

366
00:28:24,110 --> 00:28:29,400
dan kemudian ketika kita update awal, kami meng-update mulai menjadi 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
yang akan berakhir kita kembali dengan mulai menjadi elemen ini.

368
00:28:33,160 --> 00:28:36,210
>> Jadi kita memeriksa unsur yang sama berulang-ulang.

369
00:28:36,210 --> 00:28:43,310
Jadi ini adalah kasus di mana setiap panggilan rekursif harus benar-benar memperbarui sesuatu.

370
00:28:43,310 --> 00:28:48,370
Jadi kita perlu melakukan start + end / 2 + 1, atau yang lain ada kasus

371
00:28:48,370 --> 00:28:50,710
di mana kita tidak benar-benar memperbarui awal.

372
00:28:50,710 --> 00:28:53,820
Semua orang melihat itu?

373
00:28:53,820 --> 00:28:56,310
Oke.

374
00:28:56,310 --> 00:29:03,860
Apakah ada yang memiliki pertanyaan tentang ini solusi atau komentar lagi?

375
00:29:05,220 --> 00:29:10,280
Oke. Apakah ada yang telah berulang-ulang solusi yang kita semua dapat melihat?

376
00:29:17,400 --> 00:29:20,940
Apakah kita semua melakukannya secara rekursif?

377
00:29:20,940 --> 00:29:25,950
Atau juga saya kira jika Anda membuka miliknya, maka Anda mungkin memiliki diganti sebelumnya Anda.

378
00:29:25,950 --> 00:29:28,810
Apakah itu secara otomatis menyimpan? Aku tidak positif.

379
00:29:35,090 --> 00:29:39,130
Apakah ada yang telah berulang?

380
00:29:39,130 --> 00:29:42,430
Kita bisa berjalan melalui bersama-sama jika tidak.

381
00:29:46,080 --> 00:29:48,100
Idenya akan menjadi sama.

382
00:30:00,260 --> 00:30:02,830
Iterative solusi.

383
00:30:02,830 --> 00:30:07,140
Kita akan ingin pada dasarnya melakukan ide yang sama

384
00:30:07,140 --> 00:30:16,530
di mana kita ingin melacak akhir baru array dan awal baru dari array

385
00:30:16,530 --> 00:30:18,510
dan melakukannya berulang-ulang.

386
00:30:18,510 --> 00:30:22,430
Dan jika apa yang kita melacak sebagai awal dan akhir yang pernah berpotongan,

387
00:30:22,430 --> 00:30:29,020
maka kita tidak menemukan itu dan kita bisa kembali palsu.

388
00:30:29,020 --> 00:30:37,540
Jadi bagaimana saya melakukan itu? Ada yang punya saran atau kode bagi saya untuk menarik?

389
00:30:42,190 --> 00:30:47,450
[Mahasiswa] Lakukan loop sementara. >> Ya.

390
00:30:47,450 --> 00:30:49,450
Anda akan ingin melakukan loop.

391
00:30:49,450 --> 00:30:51,830
>> Apakah Anda memiliki kode saya bisa menarik, atau apa yang akan Anda sarankan?

392
00:30:51,830 --> 00:30:56,340
[Mahasiswa] Saya kira begitu. >> Baiklah. Hal ini membuat segalanya lebih mudah. Siapa nama Anda?

393
00:30:56,340 --> 00:30:57,890
[Mahasiswa] Lucas.

394
00:31:00,140 --> 00:31:04,190
Revisi 1. Oke.

395
00:31:04,190 --> 00:31:13,200
Rendah adalah apa yang kita disebut mulai sebelum.

396
00:31:13,200 --> 00:31:17,080
Up adalah tidak cukup apa yang kita disebut akhir sebelum.

397
00:31:17,080 --> 00:31:22,750
Sebenarnya, akhirnya sekarang dalam array. Ini adalah elemen yang harus kita pertimbangkan.

398
00:31:22,750 --> 00:31:26,890
Jadi rendah adalah 0, naik adalah ukuran array - 1,

399
00:31:26,890 --> 00:31:34,780
dan sekarang kita looping, dan kami memeriksa -

400
00:31:34,780 --> 00:31:37,340
Saya kira Anda bisa berjalan melalui itu.

401
00:31:37,340 --> 00:31:41,420
Apa yang dipikirkan Anda melalui ini? Berjalan kami melalui kode Anda.

402
00:31:41,420 --> 00:31:49,940
[Mahasiswa] Tentu. Lihatlah nilai tumpukan jerami di tengah dan membandingkannya dengan jarum.

403
00:31:49,940 --> 00:31:58,520
Jadi jika itu lebih besar dari jarum Anda, maka Anda ingin - oh, sebenarnya, yang harus mundur.

404
00:31:58,520 --> 00:32:05,180
Anda akan ingin membuang bagian kanan, dan begitu ya, yang harus jalan.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Jadi ini harus kurang? Adalah bahwa apa yang Anda katakan? >> [Mahasiswa] Ya.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Oke. Kurangi sedikit.

407
00:32:10,390 --> 00:32:15,700
Jadi jika apa yang kita sedang melihat lebih kecil dari apa yang kita inginkan,

408
00:32:15,700 --> 00:32:19,410
maka yeah, kami ingin membuang kiri setengah,

409
00:32:19,410 --> 00:32:22,210
yang berarti kita memperbarui segala sesuatu yang kita sedang mempertimbangkan

410
00:32:22,210 --> 00:32:26,610
dengan memindahkan rendah di sebelah kanan array.

411
00:32:26,610 --> 00:32:30,130
Ini terlihat bagus.

412
00:32:30,130 --> 00:32:34,550
Saya pikir itu memiliki masalah yang sama bahwa kita mengatakan pada yang sebelumnya,

413
00:32:34,550 --> 00:32:49,760
di mana jika rendah adalah 0 dan up adalah 1, kemudian rendah up + / 2 akan dibentuk menjadi hal yang sama lagi.

414
00:32:49,760 --> 00:32:53,860
>> Dan bahkan jika itu tidak terjadi, itu masih lebih efisien setidaknya

415
00:32:53,860 --> 00:32:57,630
hanya membuang elemen kita hanya melihat yang kita tahu adalah salah.

416
00:32:57,630 --> 00:33:03,240
Begitu rendah + up / 2 + 1 - >> [mahasiswa] Itu harus menjadi cara lainnya.

417
00:33:03,240 --> 00:33:05,900
[Bowden] Atau ini harus - 1 dan yang lainnya harus + 1.

418
00:33:05,900 --> 00:33:09,580
[Mahasiswa] Dan harus ada ganda tanda sama. >> [Bowden] Ya.

419
00:33:09,580 --> 00:33:11,340
[Mahasiswa] Ya.

420
00:33:14,540 --> 00:33:15,910
Oke.

421
00:33:15,910 --> 00:33:21,280
Dan akhirnya, sekarang kita memiliki + 1 - 1 hal,

422
00:33:21,280 --> 00:33:31,520
itu - itu tidak mungkin - itu pernah mungkin untuk rendah berakhir dengan nilai yang lebih besar dari atas?

423
00:33:35,710 --> 00:33:40,320
Saya pikir satu-satunya cara yang bisa terjadi - Apakah mungkin? >> [Mahasiswa] Saya tidak tahu.

424
00:33:40,320 --> 00:33:45,220
Tetapi jika mendapat dipotong dan kemudian mendapat minus yang 1 dan kemudian - >> Ya.

425
00:33:45,220 --> 00:33:47,480
[Mahasiswa] Ini mungkin akan mendapatkan kacau.

426
00:33:49,700 --> 00:33:53,940
Saya pikir itu harus baik hanya karena

427
00:33:53,940 --> 00:33:58,800
untuk itu berakhir lebih rendah mereka akan harus sama, saya pikir.

428
00:33:58,800 --> 00:34:03,070
Tetapi jika mereka adalah sama, maka kita tidak akan melakukan loop sementara untuk memulai dengan

429
00:34:03,070 --> 00:34:06,670
dan kami hanya akan kembali nilai. Jadi saya pikir kita baik sekarang.

430
00:34:06,670 --> 00:34:11,530
Perhatikan bahwa meskipun masalah ini tidak lagi rekursif,

431
00:34:11,530 --> 00:34:17,400
yang sama berlaku apabila ide kita bisa melihat bagaimana hal ini begitu mudah cocok

432
00:34:17,400 --> 00:34:23,659
untuk solusi rekursif oleh fakta bahwa kami hanya memperbarui indeks berulang-ulang,

433
00:34:23,659 --> 00:34:29,960
kita membuat masalah yang lebih kecil dan lebih kecil, kami berfokus pada subset dari array.

434
00:34:29,960 --> 00:34:40,860
[Mahasiswa] Jika rendah adalah 0 dan sampai 1, mereka berdua akan menjadi 0 + 1/2, yang akan pergi ke 0,

435
00:34:40,860 --> 00:34:44,429
dan kemudian satu akan + 1, satu akan menjadi - 1.

436
00:34:47,000 --> 00:34:50,870
[Mahasiswa] mana kita memeriksa kesetaraan?

437
00:34:50,870 --> 00:34:55,100
Seperti jika yang sebenarnya tengah jarum?

438
00:34:55,100 --> 00:34:58,590
Kami saat ini tidak melakukan hal itu? Oh!

439
00:35:00,610 --> 00:35:02,460
Jika ini kan -

440
00:35:05,340 --> 00:35:13,740
Ya. Kita tidak bisa hanya melakukan tes di sini karena katakanlah tengah pertama -

441
00:35:13,740 --> 00:35:16,430
[Mahasiswa] Ini benar-benar seperti tidak membuang terikat.

442
00:35:16,430 --> 00:35:20,220
Jadi jika Anda membuang terikat, Anda harus dicek dulu atau apa pun.

443
00:35:20,220 --> 00:35:23,350
Ah. Ya. >> [Mahasiswa] Ya.

444
00:35:23,350 --> 00:35:29,650
Jadi sekarang kita telah dibuang yang saat ini kami melihat,

445
00:35:29,650 --> 00:35:33,260
yang berarti kita sekarang harus juga memiliki

446
00:35:33,260 --> 00:35:44,810
if (tumpukan jerami [(low + up) / 2] == jarum), maka kita bisa kembali benar.

447
00:35:44,810 --> 00:35:52,070
Dan apakah saya menempatkan lain atau hanya jika, itu berarti harfiah hal yang sama

448
00:35:52,070 --> 00:35:57,110
karena ini akan kembali benar.

449
00:35:57,110 --> 00:36:01,450
Jadi saya akan menaruh lain jika, tapi itu tidak masalah.

450
00:36:01,450 --> 00:36:10,440
>> Jadi lain jika hal ini, lagi ini, dan ini adalah hal yang umum saya lakukan

451
00:36:10,440 --> 00:36:14,340
mana bahkan jika itu adalah kasus di mana segala sesuatu baik di sini,

452
00:36:14,340 --> 00:36:22,780
seperti rendah tidak dapat lebih besar dari atas, itu bukan alasan layak tentang apakah itu benar.

453
00:36:22,780 --> 00:36:28,010
Jadi Anda mungkin juga mengatakan sementara rendah kurang dari atau sama dengan

454
00:36:28,010 --> 00:36:30,720
atau sementara rendah kurang dari

455
00:36:30,720 --> 00:36:35,300
jadi jika mereka pernah sama atau rendah terjadi untuk dilewatkan,

456
00:36:35,300 --> 00:36:40,130
maka kita bisa keluar dari lingkaran ini.

457
00:36:41,410 --> 00:36:44,630
Pertanyaan, kekhawatiran, komentar?

458
00:36:47,080 --> 00:36:49,270
Oke. Ini terlihat bagus.

459
00:36:49,270 --> 00:36:52,230
Sekarang kita ingin melakukan semacam.

460
00:36:52,230 --> 00:37:04,030
Jika kita pergi ke revisi kedua saya, kita melihat angka-angka yang sama,

461
00:37:04,030 --> 00:37:07,550
tapi sekarang mereka tidak lagi dalam rangka diurutkan.

462
00:37:07,550 --> 00:37:12,840
Dan kita ingin menerapkan semacam menggunakan algoritma di O n log n.

463
00:37:12,840 --> 00:37:17,240
Jadi mana algoritma yang Anda pikir kita harus melaksanakan sini? >> [Mahasiswa] Merge sort.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Ya. Merge sort adalah O (n log n), sehingga itulah yang akan kita lakukan.

465
00:37:23,810 --> 00:37:26,680
Dan masalahnya akan menjadi sangat mirip,

466
00:37:26,680 --> 00:37:31,920
mana dengan mudah cocok untuk solusi rekursif.

467
00:37:31,920 --> 00:37:35,580
Kita juga bisa datang dengan solusi berulang jika kita ingin,

468
00:37:35,580 --> 00:37:42,540
tapi rekursi akan lebih mudah di sini dan kami harus melakukan rekursi.

469
00:37:45,120 --> 00:37:49,530
Saya kira kita akan berjalan melalui gabungan semacam pertama,

470
00:37:49,530 --> 00:37:54,280
meskipun ada video indah di gabungan semacam sudah. [Tertawa]

471
00:37:54,280 --> 00:37:59,780
Jadi menggabungkan semacam ada - Saya membuang-buang begitu banyak makalah ini.

472
00:37:59,780 --> 00:38:02,080
Oh, hanya ada satu kiri.

473
00:38:02,080 --> 00:38:03,630
Jadi bergabung.

474
00:38:08,190 --> 00:38:12,470
Oh, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Oke.

476
00:38:29,910 --> 00:38:33,460
Merge mengambil dua array terpisah.

477
00:38:33,460 --> 00:38:36,780
Individual kedua array keduanya diurutkan.

478
00:38:36,780 --> 00:38:40,970
Jadi ini array, 1, 3, 5, diurutkan. Ini array, 0, 2, 4, diurutkan.

479
00:38:40,970 --> 00:38:46,710
Sekarang apa yang harus Anda lakukan adalah menggabungkan menggabungkan mereka ke dalam sebuah array tunggal yang diurutkan itu sendiri.

480
00:38:46,710 --> 00:38:57,130
Jadi kami ingin sebuah array ukuran 6 yang akan memiliki unsur-unsur di dalamnya

481
00:38:57,130 --> 00:38:59,390
dalam rangka diurutkan.

482
00:38:59,390 --> 00:39:03,390
>> Dan jadi kita bisa mengambil keuntungan dari fakta bahwa dua array diurutkan

483
00:39:03,390 --> 00:39:06,800
untuk melakukan hal ini dalam waktu linier,

484
00:39:06,800 --> 00:39:13,510
berarti waktu linier jika array ini adalah x ukuran dan ini adalah ukuran y,

485
00:39:13,510 --> 00:39:20,970
maka algoritma total harus O (x + y). Oke.

486
00:39:20,970 --> 00:39:23,150
Jadi saran.

487
00:39:23,150 --> 00:39:26,030
[Mahasiswa] Bisakah kita mulai dari kiri?

488
00:39:26,030 --> 00:39:30,150
Jadi Anda akan menempatkan 0 turun pertama dan kemudian 1 dan maka di sini Anda berada di 2.

489
00:39:30,150 --> 00:39:33,320
Jadi itu seperti Anda memiliki tab yang bergerak ke kanan. >> [Bowden] Ya.

490
00:39:33,320 --> 00:39:41,070
Untuk kedua array jika kita hanya fokus pada elemen paling kiri.

491
00:39:41,070 --> 00:39:43,530
Karena kedua array diurutkan, kita tahu bahwa elemen 2

492
00:39:43,530 --> 00:39:46,920
adalah elemen terkecil dalam array baik.

493
00:39:46,920 --> 00:39:53,500
Jadi itu berarti bahwa 1 dari mereka 2 elemen harus menjadi elemen terkecil dalam array gabungan kami.

494
00:39:53,500 --> 00:39:58,190
Kebetulan bahwa terkecil adalah satu di waktu yang tepat ini.

495
00:39:58,190 --> 00:40:02,580
Jadi kita ambil 0, masukkan di sebelah kiri karena 0 adalah kurang dari 1,

496
00:40:02,580 --> 00:40:08,210
sehingga mengambil 0, masukkan ke posisi pertama kami, dan kemudian kami memperbarui ini

497
00:40:08,210 --> 00:40:12,070
sekarang fokus pada elemen pertama.

498
00:40:12,070 --> 00:40:14,570
Dan sekarang kita ulangi.

499
00:40:14,570 --> 00:40:20,670
Jadi sekarang kita bandingkan 2 dan 1. 1 lebih kecil, jadi kita akan memasukkan 1.

500
00:40:20,670 --> 00:40:25,300
Kami memperbarui pointer ini untuk menunjuk ke orang ini.

501
00:40:25,300 --> 00:40:33,160
Sekarang kita melakukannya lagi, sehingga 2. Ini akan memperbarui, membandingkan 2, 3.

502
00:40:33,160 --> 00:40:37,770
Ini update, kemudian 4 dan 5.

503
00:40:37,770 --> 00:40:42,110
Jadi itu adalah gabungan.

504
00:40:42,110 --> 00:40:49,010
>> Ini harus cukup jelas bahwa itu adalah waktu linier karena kita hanya pergi di setiap elemen sekali.

505
00:40:49,010 --> 00:40:55,980
Dan itu adalah langkah terbesar untuk menerapkan semacam gabungan yang melakukan hal ini.

506
00:40:55,980 --> 00:40:59,330
Dan itu tidak sulit.

507
00:40:59,330 --> 00:41:15,020
Beberapa hal yang perlu dikhawatirkan adalah mari kita mengatakan kami penggabungan 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Dalam hal ini kita berakhir di skenario di mana yang satu ini akan menjadi lebih kecil,

509
00:41:30,930 --> 00:41:36,160
maka kami memperbarui pointer ini, yang satu ini akan menjadi lebih kecil, update ini,

510
00:41:36,160 --> 00:41:41,280
yang satu ini lebih kecil, dan sekarang Anda harus mengenali

511
00:41:41,280 --> 00:41:44,220
ketika Anda sudah benar-benar kehabisan elemen untuk membandingkan dengan.

512
00:41:44,220 --> 00:41:49,400
Karena kita telah menggunakan ini seluruh array,

513
00:41:49,400 --> 00:41:55,190
segala sesuatu dalam array ini sekarang hanya dimasukkan ke sini.

514
00:41:55,190 --> 00:42:02,040
Jadi jika kita pernah mengalami titik di mana salah satu dari array kita benar-benar bergabung sudah,

515
00:42:02,040 --> 00:42:06,510
maka kita hanya mengambil semua elemen dari array lain dan memasukkan mereka ke akhir array.

516
00:42:06,510 --> 00:42:13,630
Jadi kami hanya bisa memasukkan 4, 5, 6. Oke.

517
00:42:13,630 --> 00:42:18,070
Itulah salah satu hal yang harus diperhatikan.

518
00:42:22,080 --> 00:42:26,120
Menerapkan langkah yang harus 1.

519
00:42:26,120 --> 00:42:32,600
Gabung mengurutkan maka berdasarkan itu, itu 2 langkah, 2 langkah konyol.

520
00:42:38,800 --> 00:42:42,090
Mari kita beri array ini.

521
00:42:57,920 --> 00:43:05,680
Jadi menggabungkan semacam, langkah 1 adalah untuk rekursif memecah array menjadi dua bagian.

522
00:43:05,680 --> 00:43:09,350
Jadi membagi array ini menjadi dua bagian.

523
00:43:09,350 --> 00:43:22,920
Kami sekarang memiliki 4, 15, 16, 50 dan 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
Dan sekarang kita melakukannya lagi dan kami berpisah ini menjadi dua bagian.

525
00:43:25,800 --> 00:43:27,530
Aku hanya akan melakukannya di sisi ini.

526
00:43:27,530 --> 00:43:34,790
Jadi 4, 15 dan 16, 50.

527
00:43:34,790 --> 00:43:37,440
Kami akan melakukan hal yang sama di sini.

528
00:43:37,440 --> 00:43:40,340
Dan sekarang kita membaginya menjadi dua bagian lagi.

529
00:43:40,340 --> 00:43:51,080
Dan kami memiliki 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Jadi itu adalah kasus dasar kami.

531
00:43:53,170 --> 00:44:00,540
Setelah array ukuran 1, maka kita berhenti dengan membelah menjadi dua bagian.

532
00:44:00,540 --> 00:44:03,190
>> Sekarang apa yang kita lakukan dengan ini?

533
00:44:03,190 --> 00:44:15,730
Kami akhirnya ini juga akan terurai menjadi 8, 23, 42, dan 108.

534
00:44:15,730 --> 00:44:24,000
Jadi sekarang kita berada di titik ini, sekarang langkah kedua dari gabungan semacam hanya penggabungan pasangan untuk daftar.

535
00:44:24,000 --> 00:44:27,610
Jadi kami ingin menggabungkan semua. Kami hanya memanggil bergabung.

536
00:44:27,610 --> 00:44:31,410
Kita tahu merge akan kembali ini dalam rangka diurutkan.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Sekarang kita ingin menggabungkan ini, dan itu akan kembali daftar dengan mereka dalam rangka diurutkan,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Kami menggabungkan mereka - saya tidak bisa menulis - 8, 23 dan 42, 108.

541
00:44:57,380 --> 00:45:02,890
Jadi kita memiliki pasangan gabungan sekali.

542
00:45:02,890 --> 00:45:05,140
Sekarang kita hanya bergabung lagi.

543
00:45:05,140 --> 00:45:10,130
Perhatikan bahwa masing-masing daftar yang diurutkan dalam dirinya sendiri,

544
00:45:10,130 --> 00:45:15,220
dan kemudian kami hanya dapat menggabungkan daftar ini untuk mendapatkan daftar ukuran 4 yang diurutkan

545
00:45:15,220 --> 00:45:19,990
dan menggabungkan kedua daftar untuk mendapatkan daftar ukuran 4 yang diurutkan.

546
00:45:19,990 --> 00:45:25,710
Dan akhirnya, kita dapat menggabungkan dua daftar ukuran 4 untuk mendapatkan salah satu daftar ukuran 8 yang diurutkan.

547
00:45:25,710 --> 00:45:34,030
Jadi untuk melihat bahwa ini adalah keseluruhan n log n, kita sudah melihat bahwa merge adalah linear,

548
00:45:34,030 --> 00:45:40,390
jadi ketika kita sedang berhadapan dengan penggabungan ini, sehingga seperti biaya keseluruhan merge

549
00:45:40,390 --> 00:45:43,410
untuk kedua daftar hanya 2 karena -

550
00:45:43,410 --> 00:45:49,610
Atau juga, itu O n, namun n disini hanya 2 elemen tersebut, sehingga 2.

551
00:45:49,610 --> 00:45:52,850
Dan ini akan menjadi 2 2 2 dan ini akan menjadi 2 dan ini akan menjadi 2 2,

552
00:45:52,850 --> 00:45:58,820
sehingga di semua gabungan yang perlu kita lakukan, kita akhirnya mengerjakan n.

553
00:45:58,820 --> 00:46:03,210
Seperti 2 + 2 + 2 + 2 adalah 8, yang adalah n,

554
00:46:03,210 --> 00:46:08,060
sehingga biaya penggabungan di set ini adalah n.

555
00:46:08,060 --> 00:46:10,810
Dan kemudian hal yang sama di sini.

556
00:46:10,810 --> 00:46:16,980
Kita akan menggabungkan semua 2, maka 2, dan individual gabungan ini akan mengambil empat operasi,

557
00:46:16,980 --> 00:46:23,610
ini merge akan mengambil empat operasi, tetapi sekali lagi, antara semua ini,

558
00:46:23,610 --> 00:46:29,030
kita akhirnya penggabungan n hal total, sehingga langkah ini membutuhkan n.

559
00:46:29,030 --> 00:46:33,670
Dan sehingga setiap tingkat membutuhkan n elemen yang bergabung.

560
00:46:33,670 --> 00:46:36,110
>> Dan berapa banyak tingkat yang ada?

561
00:46:36,110 --> 00:46:40,160
Pada setiap tingkat, array kita tumbuh dengan ukuran 2.

562
00:46:40,160 --> 00:46:44,590
Berikut array kami adalah ukuran 1, di sini mereka ukuran 2, di sini mereka ukuran 4,

563
00:46:44,590 --> 00:46:46,470
dan akhirnya, mereka ukuran 8.

564
00:46:46,470 --> 00:46:56,450
Jadi karena itu adalah dua kali lipat, ada yang akan menjadi total log n tingkat ini.

565
00:46:56,450 --> 00:47:02,090
Jadi dengan log n tingkat, masing-masing tingkat individu mengambil n operasi total,

566
00:47:02,090 --> 00:47:05,720
kita mendapatkan log n n algoritma.

567
00:47:05,720 --> 00:47:07,790
Pertanyaan?

568
00:47:08,940 --> 00:47:13,320
Apakah orang-orang sudah membuat kemajuan tentang bagaimana menerapkan ini?

569
00:47:13,320 --> 00:47:18,260
Apakah ada yang sudah dalam keadaan di mana saya hanya dapat menarik kode mereka?

570
00:47:20,320 --> 00:47:22,260
Aku bisa memberikan satu menit.

571
00:47:24,770 --> 00:47:27,470
Yang satu ini akan menjadi lebih lama.

572
00:47:27,470 --> 00:47:28,730
Saya sangat merekomendasikan kambuh -

573
00:47:28,730 --> 00:47:30,510
Anda tidak perlu melakukan rekursi untuk penggabungan

574
00:47:30,510 --> 00:47:33,750
karena untuk melakukan rekursi untuk menggabungkan, Anda akan harus melewati sekelompok ukuran yang berbeda.

575
00:47:33,750 --> 00:47:37,150
Anda dapat, tapi menjengkelkan.

576
00:47:37,150 --> 00:47:43,720
Tapi rekursi untuk semacam itu sendiri cukup mudah.

577
00:47:43,720 --> 00:47:49,190
Anda hanya benar-benar memanggil semacam di kiri setengah, seperti pada bagian kanan. Oke.

578
00:47:51,770 --> 00:47:54,860
Ada yang punya apa-apa aku bisa menarik belum?

579
00:47:54,860 --> 00:47:57,540
Atau aku akan memberikan satu menit.

580
00:47:58,210 --> 00:47:59,900
Oke.

581
00:47:59,900 --> 00:48:02,970
Ada yang punya sesuatu yang kita dapat bekerja dengan?

582
00:48:05,450 --> 00:48:09,680
Atau kita hanya akan bekerja dengan ini dan kemudian berkembang dari sana.

583
00:48:09,680 --> 00:48:14,050
>> Ada yang punya lebih dari ini bahwa saya bisa menarik?

584
00:48:14,050 --> 00:48:17,770
[Mahasiswa] Ya. Anda dapat menarik tambang. >> Baiklah.

585
00:48:17,770 --> 00:48:19,730
Ya!

586
00:48:22,170 --> 00:48:25,280
[Mahasiswa] Ada banyak kondisi. >> Oh, menembak. Dapatkah Anda -

587
00:48:25,280 --> 00:48:28,110
[Mahasiswa] Saya harus menyimpannya. >> Ya.

588
00:48:32,420 --> 00:48:35,730
Jadi kita lakukan penggabungan secara terpisah.

589
00:48:35,730 --> 00:48:38,570
Oh, tapi itu tidak terlalu buruk.

590
00:48:39,790 --> 00:48:41,650
Oke.

591
00:48:41,650 --> 00:48:47,080
Jadi semacam itu sendiri hanya menelepon mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Jelaskan kepada kami apa mergeSortHelp tidak.

593
00:48:49,530 --> 00:48:55,700
[Mahasiswa] MergeSortHelp cukup banyak melakukan dua langkah utama,

594
00:48:55,700 --> 00:49:01,270
yaitu untuk mengurutkan masing-masing setengah dari array dan kemudian untuk menggabungkan keduanya.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Oke, jadi beri aku detik.

596
00:49:10,850 --> 00:49:13,210
Saya pikir ini - >> [mahasiswa] saya perlu -

597
00:49:17,100 --> 00:49:19,400
Ya. Aku kehilangan sesuatu.

598
00:49:19,400 --> 00:49:23,100
Pada menggabungkan, saya menyadari bahwa saya perlu membuat sebuah array baru

599
00:49:23,100 --> 00:49:26,530
karena saya tidak bisa melakukannya di tempat. >> Ya. Anda tidak bisa. Benar.

600
00:49:26,530 --> 00:49:28,170
[Mahasiswa] Jadi saya membuat sebuah array baru.

601
00:49:28,170 --> 00:49:31,510
Aku lupa pada akhir bergabung untuk re-ubah.

602
00:49:31,510 --> 00:49:34,490
Oke. Kita perlu sebuah array baru.

603
00:49:34,490 --> 00:49:41,000
Dalam gabungan semacam, ini hampir selalu benar.

604
00:49:41,000 --> 00:49:44,340
Bagian dari biaya algoritma yang lebih baik waktu-bijaksana

605
00:49:44,340 --> 00:49:47,310
hampir selalu perlu untuk menggunakan memori sedikit lebih.

606
00:49:47,310 --> 00:49:51,570
Jadi di sini, tidak peduli bagaimana Anda lakukan menggabungkan semacam,

607
00:49:51,570 --> 00:49:54,780
Anda pasti akan perlu menggunakan beberapa memori tambahan.

608
00:49:54,780 --> 00:49:58,240
Dia menciptakan sebuah array baru.

609
00:49:58,240 --> 00:50:03,400
Dan kemudian Anda katakan pada akhirnya kita hanya perlu menyalin array baru ke array yang asli.

610
00:50:03,400 --> 00:50:04,830
[Mahasiswa] Saya kira begitu, ya.

611
00:50:04,830 --> 00:50:08,210
Saya tidak tahu apakah yang bekerja dalam hal menghitung dengan referensi atau apa pun -

612
00:50:08,210 --> 00:50:11,650
Ya, ia akan bekerja. >> [Mahasiswa] Oke.

613
00:50:20,620 --> 00:50:24,480
Apakah Anda mencoba menjalankan ini? >> [Mahasiswa] Tidak, belum. Oke >>.

614
00:50:24,480 --> 00:50:28,880
Coba jalankan itu, dan kemudian saya akan berbicara tentang hal ini untuk kedua.

615
00:50:28,880 --> 00:50:35,200
[Mahasiswa] Saya perlu memiliki semua prototipe fungsi dan segalanya, meskipun, kan?

616
00:50:37,640 --> 00:50:40,840
Prototipe fungsi. Oh, maksudmu seperti - Ya.

617
00:50:40,840 --> 00:50:43,040
Urutkan memanggil mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Jadi agar semacam untuk memanggil mergeSortHelp, mergeSortHelp baik harus telah didefinisikan

619
00:50:47,390 --> 00:50:56,370
sebelum semacam atau kita hanya perlu prototipe. Cukup copy dan paste.

620
00:50:56,370 --> 00:50:59,490
Dan sama, mergeSortHelp memanggil bergabung,

621
00:50:59,490 --> 00:51:03,830
namun menggabungkan belum ditetapkan belum, jadi kami hanya bisa membiarkan mergeSortHelp tahu

622
00:51:03,830 --> 00:51:08,700
bahwa itulah yang menggabungkan akan terlihat seperti, dan itulah yang.

623
00:51:09,950 --> 00:51:15,730
Jadi mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
Kami memiliki masalah di sini di mana kita tidak memiliki kasus dasar.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp adalah rekursif, sehingga setiap fungsi rekursif

626
00:51:38,110 --> 00:51:42,610
akan memerlukan beberapa jenis kasus dasar untuk mengetahui kapan harus berhenti menyebut dirinya secara rekursif.

627
00:51:42,610 --> 00:51:45,590
Apa yang kasus dasar kami akan di sini? Ya.

628
00:51:45,590 --> 00:51:49,110
[Mahasiswa] Jika ukurannya 1? >> [Bowden] Ya.

629
00:51:49,110 --> 00:51:56,220
Jadi seperti yang kita lihat di sana, kami berhenti membelah array

630
00:51:56,220 --> 00:52:01,850
setelah kami masuk ke array ukuran 1, yang pasti akan diurutkan sendiri.

631
00:52:01,850 --> 00:52:09,530
Jadi jika ukuran sama dengan 1, kita tahu array sudah diurutkan,

632
00:52:09,530 --> 00:52:12,970
jadi kami hanya bisa kembali.

633
00:52:12,970 --> 00:52:16,880
>> Perhatikan itu batal, sehingga kita tidak kembali sesuatu yang khusus, kita hanya kembali.

634
00:52:16,880 --> 00:52:19,580
Oke. Jadi itu yang terjadi dasar kami.

635
00:52:19,580 --> 00:52:27,440
Saya kira kasus dasar kami juga bisa jika kita kebetulan penggabungan array ukuran 0,

636
00:52:27,440 --> 00:52:30,030
kita mungkin ingin berhenti di beberapa titik,

637
00:52:30,030 --> 00:52:33,610
jadi kami hanya dapat mengatakan ukuran kurang dari 2 atau kurang dari atau sama dengan 1

638
00:52:33,610 --> 00:52:37,150
sehingga ini akan bekerja untuk array setiap saat.

639
00:52:37,150 --> 00:52:38,870
Oke.

640
00:52:38,870 --> 00:52:42,740
Jadi itu yang terjadi dasar kami.

641
00:52:42,740 --> 00:52:45,950
Sekarang Anda ingin berjalan kita melalui penggabungan?

642
00:52:45,950 --> 00:52:49,140
Apa semua kasus itu?

643
00:52:49,140 --> 00:52:54,480
Sampai di sini, kita hanya melakukan ide yang sama, -

644
00:52:56,970 --> 00:53:02,470
[Mahasiswa] Saya harus melewati ukuran dengan semua panggilan mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Saya menambahkan ukuran sebagai primer tambahan dan itu tidak ada, seperti ukuran / 2.

646
00:53:10,080 --> 00:53:16,210
[Bowden] Oh, ukuran / 2, ukuran / 2. >> [Mahasiswa] Ya, dan juga dalam fungsi di atas juga.

647
00:53:16,210 --> 00:53:21,320
[Bowden] Di sini? >> [Mahasiswa] Hanya ukuran. >> [Bowden] Oh. Ukuran, ukuran? >> [Mahasiswa] Ya.

648
00:53:21,320 --> 00:53:23,010
[Bowden] Oke.

649
00:53:23,010 --> 00:53:26,580
Biarkan aku berpikir untuk kedua.

650
00:53:26,580 --> 00:53:28,780
Apakah kita mengalami masalah?

651
00:53:28,780 --> 00:53:33,690
Kami selalu memperlakukan kiri sebagai 0. >> [Mahasiswa] No

652
00:53:33,690 --> 00:53:36,340
Itu salah juga. Maaf. Ini harus menjadi awal. Ya.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Oke. Aku seperti itu lebih baik.

654
00:53:39,230 --> 00:53:43,880
Dan akhir. Oke.

655
00:53:43,880 --> 00:53:47,200
Jadi sekarang Anda ingin berjalan kita melalui penggabungan? >> [Mahasiswa] Oke.

656
00:53:47,200 --> 00:53:52,150
Aku hanya berjalan melalui array baru yang saya buat.

657
00:53:52,150 --> 00:53:57,420
Ukurannya adalah ukuran porsi array yang kita ingin diurutkan

658
00:53:57,420 --> 00:54:03,460
dan mencoba untuk menemukan elemen yang saya harus dimasukkan ke dalam langkah array baru.

659
00:54:03,460 --> 00:54:10,140
Jadi untuk melakukan itu, pertama aku memeriksa apakah kiri setengah dari array terus memiliki unsur lagi,

660
00:54:10,140 --> 00:54:14,260
dan jika tidak, maka Anda pergi ke kondisi yang lain, yang hanya mengatakan

661
00:54:14,260 --> 00:54:20,180
oke, itu harus dalam array yang tepat, dan kami akan menempatkan bahwa dalam indeks saat newArray.

662
00:54:20,180 --> 00:54:27,620
>> Dan kemudian jika tidak, aku memeriksa apakah sisi kanan dari array juga selesai,

663
00:54:27,620 --> 00:54:30,630
dalam hal ini saya hanya dimasukkan ke dalam sebelah kiri.

664
00:54:30,630 --> 00:54:34,180
Itu tidak mungkin benar-benar diperlukan. Saya tidak yakin.

665
00:54:34,180 --> 00:54:40,970
Tapi bagaimanapun, cek dua lainnya yang dari dua lebih kecil di kiri atau kanan.

666
00:54:40,970 --> 00:54:49,770
Dan juga dalam setiap kasus, aku incrementing mana placeholder I kenaikan.

667
00:54:49,770 --> 00:54:52,040
[Bowden] Oke.

668
00:54:52,040 --> 00:54:53,840
Itu terlihat baik.

669
00:54:53,840 --> 00:54:58,800
Apakah ada yang punya komentar atau masalah atau pertanyaan?

670
00:55:00,660 --> 00:55:07,720
Jadi empat kasus yang kita harus membawa hal-hal menjadi hanya menjadi - atau sepertinya lima -

671
00:55:07,720 --> 00:55:13,100
tapi kita harus mempertimbangkan apakah array kiri telah kehabisan hal yang kita butuhkan untuk menggabungkan,

672
00:55:13,100 --> 00:55:16,390
apakah array yang benar telah kehabisan hal yang kita butuhkan untuk menggabungkan -

673
00:55:16,390 --> 00:55:18,400
Saya menunjuk pada apa-apa.

674
00:55:18,400 --> 00:55:21,730
Jadi apakah array kiri telah kehabisan hal-hal atau array yang benar telah kehabisan hal.

675
00:55:21,730 --> 00:55:24,320
Mereka adalah dua kasus.

676
00:55:24,320 --> 00:55:30,920
Kita juga perlu kasus sepele apakah hal kiri kurang dari hal yang benar.

677
00:55:30,920 --> 00:55:33,910
Kemudian kita ingin memilih hal kiri.

678
00:55:33,910 --> 00:55:37,630
Mereka adalah kasus.

679
00:55:37,630 --> 00:55:40,990
Jadi ini benar, jadi itu yang.

680
00:55:40,990 --> 00:55:46,760
Array kiri. Ini 1, 2, 3. Oke. Jadi ya, mereka adalah empat hal yang kita mungkin ingin lakukan.

681
00:55:50,350 --> 00:55:54,510
Dan kami tidak akan pergi ke iteratif solusi.

682
00:55:54,510 --> 00:55:55,980
Saya tidak akan merekomendasikan -

683
00:55:55,980 --> 00:56:03,070
Merge sort adalah contoh dari sebuah fungsi yang bersifat tidak rekursif ekor,

684
00:56:03,070 --> 00:56:07,040
itu tidak mudah untuk membuat ekor rekursif,

685
00:56:07,040 --> 00:56:13,450
tetapi juga tidak sangat mudah untuk membuatnya berulang.

686
00:56:13,450 --> 00:56:16,910
Ini sangat mudah.

687
00:56:16,910 --> 00:56:19,170
Ini implementasi gabungan semacam,

688
00:56:19,170 --> 00:56:22,140
menggabungkan, tidak peduli apa yang Anda lakukan, Anda akan membangun penggabungan.

689
00:56:22,140 --> 00:56:29,170
>> Jadi menggabungkan semacam dibangun di atas merge rekursif hanya tiga baris.

690
00:56:29,170 --> 00:56:34,700
Iteratif, itu lebih mengganggu dan lebih sulit untuk dipikirkan.

691
00:56:34,700 --> 00:56:41,860
Tapi melihat bahwa itu bukan ekor rekursif sejak mergeSortHelp - saat itu menyebut dirinya -

692
00:56:41,860 --> 00:56:46,590
masih perlu melakukan hal-hal ini kembali setelah panggilan rekursif.

693
00:56:46,590 --> 00:56:50,830
Jadi ini stack frame harus terus ada bahkan setelah panggilan ini.

694
00:56:50,830 --> 00:56:54,170
Dan kemudian ketika Anda menyebutnya, stack frame harus terus ada

695
00:56:54,170 --> 00:56:57,780
karena bahkan setelah panggilan itu, kita masih perlu untuk menggabungkan.

696
00:56:57,780 --> 00:57:01,920
Dan itu adalah trivial untuk membuat ekor ini rekursif.

697
00:57:04,070 --> 00:57:06,270
Pertanyaan?

698
00:57:08,300 --> 00:57:09,860
Baiklah.

699
00:57:09,860 --> 00:57:13,400
Jadi akan kembali untuk memilah - oh, ada dua hal yang saya ingin menunjukkan. Oke.

700
00:57:13,400 --> 00:57:17,840
Akan kembali untuk menyortir, kita akan melakukan ini dengan cepat.

701
00:57:17,840 --> 00:57:21,030
Atau cari. Urutkan? Sort. Ya.

702
00:57:21,030 --> 00:57:22,730
Kembali ke awal semacam.

703
00:57:22,730 --> 00:57:29,870
Kami ingin menciptakan suatu algoritma yang macam array menggunakan algoritma setiap

704
00:57:29,870 --> 00:57:33,660
di O n.

705
00:57:33,660 --> 00:57:40,860
Jadi bagaimana ini mungkin? Apakah ada yang punya semacam -

706
00:57:40,860 --> 00:57:44,300
Aku mengisyaratkan sebelumnya di -

707
00:57:44,300 --> 00:57:48,300
Jika kita akan meningkatkan dari n log n untuk n O,

708
00:57:48,300 --> 00:57:51,450
kami telah memperbaiki algoritma kami waktu-bijaksana,

709
00:57:51,450 --> 00:57:55,250
yang berarti apa yang akan kita lakukan untuk membuat untuk itu?

710
00:57:55,250 --> 00:57:59,520
[Mahasiswa] Space. >> Ya. Kita akan menggunakan lebih banyak ruang.

711
00:57:59,520 --> 00:58:04,490
Dan bahkan tidak hanya lebih banyak ruang, itu ruang eksponensial lebih.

712
00:58:04,490 --> 00:58:14,320
Jadi saya pikir ini jenis algoritma adalah sesuatu yang semu, pseudo polynom -

713
00:58:14,320 --> 00:58:18,980
pseudo - Saya tidak ingat. Pseudo sesuatu.

714
00:58:18,980 --> 00:58:22,210
Tapi itu karena kita perlu menggunakan begitu banyak ruang

715
00:58:22,210 --> 00:58:28,610
bahwa hal ini dapat dicapai, tetapi tidak realistis.

716
00:58:28,610 --> 00:58:31,220
>> Dan bagaimana kita mencapai hal ini?

717
00:58:31,220 --> 00:58:36,810
Kita bisa mencapai hal ini jika kita menjamin bahwa setiap elemen tertentu dalam array

718
00:58:36,810 --> 00:58:39,600
berada di bawah ukuran tertentu.

719
00:58:42,070 --> 00:58:44,500
Jadi mari kita hanya mengatakan bahwa ukuran adalah 200,

720
00:58:44,500 --> 00:58:48,130
setiap elemen dalam array di bawah ukuran 200.

721
00:58:48,130 --> 00:58:51,080
Dan ini sebenarnya sangat realistis.

722
00:58:51,080 --> 00:58:58,660
Anda dapat dengan mudah memiliki sebuah array yang Anda tahu segala sesuatu di dalamnya

723
00:58:58,660 --> 00:59:00,570
akan menjadi kurang dari beberapa nomor.

724
00:59:00,570 --> 00:59:07,400
Seperti jika Anda memiliki beberapa vektor benar-benar besar atau sesuatu

725
00:59:07,400 --> 00:59:11,810
tapi kau tahu semuanya akan menjadi antara 0 dan 5,

726
00:59:11,810 --> 00:59:14,790
maka itu akan secara signifikan lebih cepat untuk melakukan hal ini.

727
00:59:14,790 --> 00:59:17,930
Dan terikat pada salah satu elemen adalah 5,

728
00:59:17,930 --> 00:59:21,980
jadi ini terikat, yaitu berapa banyak memori yang Anda akan menggunakan.

729
00:59:21,980 --> 00:59:26,300
Jadi terikat adalah 200.

730
00:59:26,300 --> 00:59:32,960
Dalam teori selalu ada terikat karena integer hanya bisa sampai 4 miliar,

731
00:59:32,960 --> 00:59:40,600
tapi itu tidak realistis sejak itu kita akan menggunakan ruang

732
00:59:40,600 --> 00:59:44,400
pada urutan 4 miliar. Jadi itu tidak realistis.

733
00:59:44,400 --> 00:59:47,060
Tapi di sini kita akan mengatakan terikat kami adalah 200.

734
00:59:47,060 --> 00:59:59,570
Trik untuk melakukannya di O n adalah kita membuat array lain yang disebut jumlah ukuran TERIKAT.

735
00:59:59,570 --> 01:00:10,470
Jadi sebenarnya, ini adalah jalan pintas untuk - saya benar-benar tidak tahu apakah dentang melakukan hal ini.

736
01:00:11,150 --> 01:00:15,330
Tapi di GCC paling tidak - dengan asumsi dentang 'm tidak terlalu -

737
01:00:15,330 --> 01:00:18,180
ini hanya akan menginisialisasi seluruh array menjadi 0s.

738
01:00:18,180 --> 01:00:25,320
Jadi jika saya tidak ingin melakukan itu, maka saya secara terpisah bisa lakukan untuk (int i = 0;

739
01:00:25,320 --> 01:00:31,500
i <TERIKAT, i + +) dan jumlah [i] = 0;

740
01:00:31,500 --> 01:00:35,260
Jadi sekarang semuanya diinisialisasi ke 0.

741
01:00:35,260 --> 01:00:39,570
Aku iterate atas array saya,

742
01:00:39,570 --> 01:00:51,920
dan apa yang saya lakukan adalah saya sedang menghitung jumlah masing-masing - Mari kita turun di sini.

743
01:00:51,920 --> 01:00:55,480
Kami memiliki 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Yang saya menghitung adalah jumlah kejadian dari masing-masing elemen.

745
01:01:00,010 --> 01:01:03,470
Mari kita benar-benar menambahkan beberapa lebih di sini dengan beberapa mengulangi.

746
01:01:03,470 --> 01:01:11,070
Jadi nilai yang kita miliki di sini, nilai yang akan menjadi array [i].

747
01:01:11,070 --> 01:01:14,850
Jadi val bisa 4 atau 8 atau apa pun.

748
01:01:14,850 --> 01:01:18,870
Dan sekarang saya sedang menghitung berapa banyak nilai yang pernah saya lihat,

749
01:01:18,870 --> 01:01:21,230
sehingga jumlah [val] + +;

750
01:01:21,230 --> 01:01:29,430
Setelah ini dilakukan, jumlah ini akan terlihat seperti 0001.

751
01:01:29,430 --> 01:01:42,190
Mari kita melakukan penghitungan [val] - TERIKAT + 1.

752
01:01:42,190 --> 01:01:48,230
>> Nah, itu hanya untuk menjelaskan fakta bahwa kita mulai dari 0.

753
01:01:48,230 --> 01:01:50,850
Jadi, jika 200 akan menjadi nomor kami terbesar,

754
01:01:50,850 --> 01:01:54,720
kemudian 0 sampai 200 adalah 201 hal.

755
01:01:54,720 --> 01:02:01,540
Jadi penting, itu akan terlihat seperti 00001 karena kita memiliki satu 4.

756
01:02:01,540 --> 01:02:10,210
Kemudian kita akan memiliki 0001 di mana kita akan memiliki 1 dalam indeks 8 hitungan.

757
01:02:10,210 --> 01:02:14,560
Kami akan memiliki 2 dalam indeks 23 hitungan.

758
01:02:14,560 --> 01:02:17,630
Kami akan memiliki 2 dalam indeks ke-42 hitungan.

759
01:02:17,630 --> 01:02:21,670
Jadi kita bisa menggunakan hitungan.

760
01:02:34,270 --> 01:02:44,920
Jadi num_of_item = jumlah [i].

761
01:02:44,920 --> 01:02:52,540
Dan jadi jika num_of_item adalah 2, itu berarti kita ingin memasukkan 2 dari nomor i

762
01:02:52,540 --> 01:02:55,290
ke dalam array kami diurutkan.

763
01:02:55,290 --> 01:03:02,000
Jadi kita perlu melacak seberapa jauh kita ke array.

764
01:03:02,000 --> 01:03:05,470
Jadi = indeks 0.

765
01:03:05,470 --> 01:03:09,910
Array - Aku hanya akan menulisnya.

766
01:03:16,660 --> 01:03:18,020
Hitungan -

767
01:03:19,990 --> 01:03:28,580
array [index + +] = i;

768
01:03:28,580 --> 01:03:32,490
Adalah bahwa apa yang saya inginkan? Saya pikir itulah yang saya inginkan.

769
01:03:35,100 --> 01:03:38,290
Ya, ini tampak bagus. Oke.

770
01:03:38,290 --> 01:03:43,050
Jadi tidak semua orang mengerti apa tujuan array jumlah saya?

771
01:03:43,050 --> 01:03:48,140
Hal ini menghitung jumlah kejadian dari masing-masing nomor.

772
01:03:48,140 --> 01:03:51,780
Kemudian saya iterasi bahwa array penting,

773
01:03:51,780 --> 01:03:57,190
dan posisi i di array jumlah

774
01:03:57,190 --> 01:04:01,930
adalah jumlah i itu yang harus muncul dalam array saya diurutkan.

775
01:04:01,930 --> 01:04:06,840
Itulah mengapa penting dari 4 akan menjadi 1

776
01:04:06,840 --> 01:04:11,840
dan jumlah dari 8 akan menjadi 1, jumlah dari 23 akan menjadi 2.

777
01:04:11,840 --> 01:04:16,900
Jadi itulah berapa banyak dari mereka saya ingin memasukkan ke dalam array saya diurutkan.

778
01:04:16,900 --> 01:04:19,200
Lalu aku hanya melakukan itu.

779
01:04:19,200 --> 01:04:28,960
Saya memasukkan num_of_item i s ke array saya diurutkan.

780
01:04:28,960 --> 01:04:31,670
>> Pertanyaan?

781
01:04:32,460 --> 01:04:43,100
Dan jadi sekali lagi, ini adalah waktu linier karena kita hanya iterasi sekali ini,

782
01:04:43,100 --> 01:04:47,470
tetapi juga linier dalam apa nomor ini akan terjadi,

783
01:04:47,470 --> 01:04:50,730
dan sehingga sangat tergantung pada apa yang Anda terikat.

784
01:04:50,730 --> 01:04:53,290
Dengan terikat dari 200, itu tidak seburuk itu.

785
01:04:53,290 --> 01:04:58,330
Jika Anda terikat akan menjadi 10.000, maka itu sedikit lebih buruk,

786
01:04:58,330 --> 01:05:01,360
tetapi jika Anda terikat akan menjadi 4 miliar, itu benar-benar realistis

787
01:05:01,360 --> 01:05:07,720
dan array ini akan harus ukuran 4 miliar, yang tidak realistis.

788
01:05:07,720 --> 01:05:10,860
Jadi itulah yang. Pertanyaan?

789
01:05:10,860 --> 01:05:13,270
[Respon siswa terdengar] >> Oke.

790
01:05:13,270 --> 01:05:15,710
Aku menyadari satu hal lain ketika kita akan melalui.

791
01:05:17,980 --> 01:05:23,720
Saya pikir masalahnya adalah di kawasan Lucas dan mungkin setiap satu kita lihat.

792
01:05:23,720 --> 01:05:26,330
Saya benar-benar lupa.

793
01:05:26,330 --> 01:05:31,040
Satu-satunya hal yang ingin saya mengomentari adalah bahwa ketika Anda sedang berhadapan dengan hal-hal seperti indeks,

794
01:05:31,040 --> 01:05:38,320
Anda tidak pernah benar-benar melihat ini ketika Anda sedang menulis untuk loop,

795
01:05:38,320 --> 01:05:41,120
tetapi secara teknis, setiap kali Anda sedang berhadapan dengan indeks,

796
01:05:41,120 --> 01:05:45,950
Anda harus cukup banyak selalu berurusan dengan unsigned integer.

797
01:05:45,950 --> 01:05:53,850
Alasan untuk ini adalah ketika Anda sedang berhadapan dengan bilangan bulat ditandatangani,

798
01:05:53,850 --> 01:05:56,090
jadi jika Anda memiliki 2 bilangan bulat ditandatangani dan Anda menambahkan mereka bersama-sama

799
01:05:56,090 --> 01:06:00,640
dan mereka akhirnya terlalu besar, maka Anda berakhir dengan angka negatif.

800
01:06:00,640 --> 01:06:03,410
Jadi itulah integer overflow yang.

801
01:06:03,410 --> 01:06:10,500
>> Jika saya tambahkan 2 miliar dan 1 miliar, saya berakhir dengan negatif 1 miliar.

802
01:06:10,500 --> 01:06:15,480
Begitulah bilangan bulat bekerja pada komputer.

803
01:06:15,480 --> 01:06:17,510
Jadi masalah dengan menggunakan -

804
01:06:17,510 --> 01:06:23,500
Itu baik kecuali jika rendah terjadi menjadi 2 miliar dan sampai terjadi menjadi 1 miliar,

805
01:06:23,500 --> 01:06:27,120
maka ini akan menjadi negatif 1 miliar dan kemudian kita akan membagi bahwa dengan 2

806
01:06:27,120 --> 01:06:29,730
dan berakhir dengan negatif 500 juta.

807
01:06:29,730 --> 01:06:33,760
Jadi ini hanya masalah jika Anda kebetulan akan mencari melalui array

808
01:06:33,760 --> 01:06:38,070
miliaran hal.

809
01:06:38,070 --> 01:06:44,050
Tapi jika + rendah sampai terjadi meluap, maka itu masalah.

810
01:06:44,050 --> 01:06:47,750
Segera setelah kami membuat mereka unsigned, kemudian 2 miliar ditambah 1 miliar adalah 3 miliar.

811
01:06:47,750 --> 01:06:51,960
3 miliar dibagi dengan 2 adalah 1,5 miliar.

812
01:06:51,960 --> 01:06:55,670
Jadi, segera setelah mereka unsigned, semuanya sempurna.

813
01:06:55,670 --> 01:06:59,900
Dan jadi itu juga masalah ketika Anda sedang menulis Anda untuk loop,

814
01:06:59,900 --> 01:07:03,940
dan benar-benar, mungkin tidak secara otomatis.

815
01:07:09,130 --> 01:07:12,330
Ini akan benar-benar hanya berteriak pada Anda.

816
01:07:12,330 --> 01:07:21,610
Jadi jika nomor ini terlalu besar untuk menjadi hanya dalam integer tetapi akan cocok di unsigned integer,

817
01:07:21,610 --> 01:07:24,970
itu akan berteriak pada Anda, jadi itulah mengapa Anda tidak pernah benar-benar mengalami masalah ini.

818
01:07:29,150 --> 01:07:34,820
Anda dapat melihat bahwa indeks tidak pernah akan menjadi negatif,

819
01:07:34,820 --> 01:07:39,220
dan jadi ketika Anda iterasi array,

820
01:07:39,220 --> 01:07:43,970
Anda dapat hampir selalu mengatakan unsigned int i, tetapi Anda tidak benar-benar harus.

821
01:07:43,970 --> 01:07:47,110
Hal-hal yang akan bekerja cukup banyak sama dengan baik.

822
01:07:48,740 --> 01:07:50,090
Oke. [Berbisik] Apa waktu itu?

823
01:07:50,090 --> 01:07:54,020
Hal terakhir yang saya ingin menunjukkan - dan aku hanya akan melakukannya benar-benar cepat.

824
01:07:54,020 --> 01:08:03,190
Kau tahu bagaimana kita mendefinisikan # # sehingga kita dapat mendefinisikan sebagai MAX 5 atau sesuatu?

825
01:08:03,190 --> 01:08:05,940
Mari kita tidak melakukan MAX. # Define TERIKAT sebagai 200. Itulah yang kami lakukan sebelumnya.

826
01:08:05,940 --> 01:08:10,380
Yang mendefinisikan sebuah konstanta, yang hanya akan disalin dan disisipkan

827
01:08:10,380 --> 01:08:13,010
dimanapun kita terjadi untuk menulis TERIKAT.

828
01:08:13,010 --> 01:08:18,189
>> Jadi kita benar-benar bisa berbuat lebih banyak dengan # mendefinisikan.

829
01:08:18,189 --> 01:08:21,170
Kita dapat mendefinisikan fungsi #.

830
01:08:21,170 --> 01:08:23,410
Mereka tidak benar-benar fungsi, tapi kami akan memanggil mereka fungsi.

831
01:08:23,410 --> 01:08:36,000
Sebuah contoh akan menjadi sesuatu seperti MAX (x, y) didefinisikan sebagai (x <y y:? X). Oke.

832
01:08:36,000 --> 01:08:40,660
Jadi, Anda harus terbiasa dengan sintaks terner operator,

833
01:08:40,660 --> 01:08:49,029
tapi x kurang dari y? Kembali y, x lain kembali.

834
01:08:49,029 --> 01:08:54,390
Sehingga Anda dapat melihat Anda dapat membuat fungsi ini terpisah,

835
01:08:54,390 --> 01:09:01,399
dan fungsi bisa seperti bool MAX mengambil 2 argumen, kembali ini.

836
01:09:01,399 --> 01:09:08,340
Ini adalah salah satu yang paling sering saya lihat dilakukan seperti ini. Kami menyebutnya macro.

837
01:09:08,340 --> 01:09:11,790
Ini adalah makro.

838
01:09:11,790 --> 01:09:15,859
Ini hanya sintaks untuk itu.

839
01:09:15,859 --> 01:09:18,740
Anda dapat menulis makro untuk melakukan apapun yang Anda inginkan.

840
01:09:18,740 --> 01:09:22,649
Anda sering melihat macro untuk debugging printfs dan barang-barang.

841
01:09:22,649 --> 01:09:29,410
Jadi jenis printf, terdapat konstanta khusus dalam C seperti menggarisbawahi GARIS garis bawah,

842
01:09:29,410 --> 01:09:31,710
2 menggarisbawahi GARIS underscore,

843
01:09:31,710 --> 01:09:37,550
dan ada juga saya pikir 2 menggarisbawahi FUNC. Yang mungkin itu. Sesuatu seperti itu.

844
01:09:37,550 --> 01:09:40,880
Hal-hal akan diganti dengan nama fungsi

845
01:09:40,880 --> 01:09:42,930
atau jumlah baris yang Anda berada di.

846
01:09:42,930 --> 01:09:48,630
Sering, Anda menulis printfs debugging bahwa di sini saya kemudian bisa hanya menulis

847
01:09:48,630 --> 01:09:54,260
DEBUG dan akan mencetak nomor baris dan fungsi yang saya kebetulan berada di

848
01:09:54,260 --> 01:09:57,020
itu ditemui bahwa pernyataan DEBUG.

849
01:09:57,020 --> 01:09:59,550
Dan Anda juga dapat mencetak hal-hal lain.

850
01:09:59,550 --> 01:10:05,990
Jadi satu hal yang harus diwaspadai adalah jika saya kebetulan # define DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
sebagai sesuatu seperti 2 * y dan 2 * x.

852
01:10:11,380 --> 01:10:14,310
Jadi untuk alasan apapun, Anda kebetulan melakukan itu banyak.

853
01:10:14,310 --> 01:10:16,650
Jadi membuat makro.

854
01:10:16,650 --> 01:10:18,680
Hal ini benar-benar rusak.

855
01:10:18,680 --> 01:10:23,050
Saya akan menyebutnya dengan melakukan sesuatu seperti DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Jadi apa yang harus dikembalikan?

857
01:10:28,840 --> 01:10:30,580
[Mahasiswa] 12.

858
01:10:30,580 --> 01:10:34,800
Ya, 12 harus dikembalikan, dan 12 dikembalikan.

859
01:10:34,800 --> 01:10:43,350
3 akan diganti untuk x, 6 akan diganti untuk y, dan kita kembali 2 * 6, yaitu 12.

860
01:10:43,350 --> 01:10:47,710
Sekarang bagaimana dengan ini? Apa yang harus dikembalikan?

861
01:10:47,710 --> 01:10:50,330
[Mahasiswa] 14. >> Idealnya, 14.

862
01:10:50,330 --> 01:10:55,290
Masalahnya adalah bahwa bagaimana hash mendefinisikan pekerjaan, ingat itu copy dan paste literal

863
01:10:55,290 --> 01:11:00,160
dari segala sesuatu cukup banyak, jadi apa ini akan ditafsirkan sebagai

864
01:11:00,160 --> 01:11:11,270
adalah kurang dari 3 1, ditambah 6 2 1 kali ditambah 6, 2 kali 3.

865
01:11:11,270 --> 01:11:19,780
>> Jadi untuk alasan ini Anda hampir selalu membungkus semuanya dalam tanda kurung.

866
01:11:22,180 --> 01:11:25,050
Setiap variabel yang hampir selalu membungkus dalam tanda kurung.

867
01:11:25,050 --> 01:11:29,570
Ada kasus-kasus di mana Anda tidak perlu, seperti saya tahu bahwa saya tidak perlu melakukannya di sini

868
01:11:29,570 --> 01:11:32,110
karena kurang dari cukup banyak selalu hanya akan bekerja,

869
01:11:32,110 --> 01:11:34,330
meskipun itu mungkin tidak benar.

870
01:11:34,330 --> 01:11:41,870
Jika ada sesuatu yang konyol seperti DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
maka itu akan mendapatkan diganti dengan 3 kurang dari 1 sama sama 2,

872
01:11:49,760 --> 01:11:53,460
dan sebagainya maka itu akan melakukan 3 kurang dari 1, apakah itu sama 2,

873
01:11:53,460 --> 01:11:55,620
yang tidak apa yang kita inginkan.

874
01:11:55,620 --> 01:12:00,730
Jadi untuk mencegah Operator masalah didahulukan,

875
01:12:00,730 --> 01:12:02,870
selalu membungkus dalam tanda kurung.

876
01:12:03,290 --> 01:12:07,700
Oke. Dan hanya itu, 5:30.

877
01:12:08,140 --> 01:12:12,470
Jika Anda memiliki pertanyaan tentang pset tersebut, beritahu kami.

878
01:12:12,470 --> 01:12:18,010
Ini harus menyenangkan, dan edisi hacker juga jauh lebih realistis

879
01:12:18,010 --> 01:12:22,980
dari edisi hacker tahun lalu, jadi kami berharap bahwa banyak dari Anda mencobanya.

880
01:12:22,980 --> 01:12:26,460
Tahun lalu itu sangat luar biasa.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]