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

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

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

4
00:00:07,310 --> 00:00:12,700
>> Jadi soalan pertama pelik worded.

5
00:00:12,700 --> 00:00:17,480
GDB membolehkan anda "debug" program, tetapi, lebih khusus, apakah ia membiarkan anda lakukan?

6
00:00:17,480 --> 00:00:22,590
Saya akan menjawab yang satu, dan saya tidak tahu apa yang sebenarnya dijangka,

7
00:00:22,590 --> 00:00:27,910
jadi saya meneka ia sesuatu yang di sepanjang garisan ia membolehkan anda langkah demi langkah

8
00:00:27,910 --> 00:00:31,540
berjalan melalui program ini, berinteraksi dengan ia, pembolehubah perubahan, melakukan semua perkara ini -

9
00:00:31,540 --> 00:00:34,270
pada dasarnya sepenuhnya mengawal pelaksanaan program

10
00:00:34,270 --> 00:00:38,410
dan memeriksa mana-mana bahagian yang diberikan pelaksanaan program.

11
00:00:38,410 --> 00:00:43,030
Jadi ciri-ciri membolehkan anda debug perkara.

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

13
00:00:44,830 --> 00:00:50,520
Mengapa gelintaran perduaan memerlukan bahawa array perlu diselesaikan?

14
00:00:50,520 --> 00:00:53,360
Siapa yang mahu untuk menjawab bahawa?

15
00:00:56,120 --> 00:01:00,070
[Pelajar] Kerana ia tidak berfungsi jika ia tidak diselesaikan. >> Yeah. [Ketawa]

16
00:01:00,070 --> 00:01:04,910
Jika ia tidak diselesaikan, maka ia adalah mustahil untuk berpecah pada separuh

17
00:01:04,910 --> 00:01:07,850
dan tahu bahawa segala-galanya ke kiri adalah kurang dan segala-galanya ke kanan

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

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

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

21
00:01:14,170 --> 00:01:17,570
Mengapa isih gelembung di O n kuasa dua?

22
00:01:17,570 --> 00:01:23,230
Adakah sesiapa yang mula-mula mahu memberikan gambaran peringkat tinggi yang sangat cepat apa jenis gelembung?

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

24
00:01:33,020 --> 00:01:37,150
Jika mereka berada di luar di mana anda menukar mereka, maka anda memeriksa unsur-unsur yang akan datang dan sebagainya.

25
00:01:37,150 --> 00:01:40,770
Apabila anda sampai akhir, maka anda tahu bahawa elemen terbesar diletakkan di hujung,

26
00:01:40,770 --> 00:01:42,750
jadi anda mengabaikan bahawa salah maka anda terus melalui,

27
00:01:42,750 --> 00:01:48,490
dan setiap kali anda perlu menyemak satu elemen kurang sehingga anda tidak membuat perubahan. >> Yeah.

28
00:01:48,490 --> 00:01:58,470
Ia dipanggil isih gelembung kerana jika anda flip array di sebelah jadi ia terpulang dan ke bawah, menegak,

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

30
00:02:03,100 --> 00:02:05,210
Itulah bagaimana ia mendapat namanya.

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

32
00:02:08,220 --> 00:02:11,190
Anda terus melalui array, bertukar-tukar 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 ia O n kuasa dua?

35
00:02:18,690 --> 00:02:24,620
Pertama, adakah sesiapa yang mahu untuk mengatakan mengapa ia O n kuasa dua?

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

37
00:02:28,760 --> 00:02:32,100
Anda hanya boleh memastikan bahawa anda telah mengambil elemen terbesar sepanjang jalan ke bawah,

38
00:02:32,100 --> 00:02:35,230
maka anda perlu untuk mengulangi bahawa sebagai banyak unsur. >> Yeah.

39
00:02:35,230 --> 00:02:41,800
Jadi ingat apa yang besar O bermakna dan apa cara Omega besar.

40
00:02:41,800 --> 00:02:50,560
O besar adalah seperti atas terikat kepada berapa perlahan ia sebenarnya boleh dijalankan.

41
00:02:50,560 --> 00:02:58,990
Jadi dengan mengatakan O n kuasa dua, ia tidak O n atau lain ia akan dapat menjalankan

42
00:02:58,990 --> 00:03:02,640
dalam masa linear, tetapi ia adalah O n cubed

43
00:03:02,640 --> 00:03:06,390
kerana ia disempadani oleh O n cubed.

44
00:03:06,390 --> 00:03:12,300
Jika ia disempadani oleh O n kuasa dua, maka ia disempadani juga oleh n cubed.

45
00:03:12,300 --> 00:03:20,280
Jadi ia n persegi, dan dalam kes terburuk mutlak, ia tidak boleh melakukan lebih baik daripada n kuasa dua,

46
00:03:20,280 --> 00:03:22,830
itulah sebabnya ia O n kuasa dua.

47
00:03:22,830 --> 00:03:31,200
Jadi untuk melihat matematik sedikit bagaimana ia datang n kuasa dua,

48
00:03:31,200 --> 00:03:40,530
jika kita mempunyai lima perkara dalam senarai kami, kali pertama berapa swap boleh kita berpotensi perlu membuat

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

50
00:03:47,170 --> 00:03:52,040
Berapa ramai swap kita akan perlu membuat dalam jangka pertama apapun gelembung melalui array?

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

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

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

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

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

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 rasa yang terakhir mungkin atau mungkin sebenarnya tidak perlu berlaku.

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

59
00:04:22,820 --> 00:04:26,490
Jadi ini adalah jumlah swap atau sekurang-kurangnya perbandingan anda perlu membuat.

60
00:04:26,490 --> 00:04:29,910
Malah jika anda tidak menukar, anda masih perlu untuk membandingkan nilai.

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

62
00:04:33,910 --> 00:04:42,050
Jika anda menyusun semula perkara-perkara ini, mari kita sebenarnya membuat ia enam perkara supaya timbunan perkara 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 menyusun semula jumlah ini, kita mahu lihat berapa banyak perbandingan kita membuat

65
00:04:49,910 --> 00:04:52,700
di seluruh algoritma.

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

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

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

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

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

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

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

73
00:05:29,430 --> 00:05:34,830
Jika kita mempunyai 10 perkara, maka kita boleh melakukannya kumpulan ini selama 5 pasang perkara yang berbeza

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 sentiasa akan mendapat n / 2 n, dan jadi ini kita akan sedikitpun ia keluar n kuasa dua / 2.

76
00:05:45,840 --> 00:05:48,890
Dan sebagainya walaupun ia adalah faktor separuh, yang berlaku untuk datang dalam

77
00:05:48,890 --> 00:05:54,190
kerana hakikat bahawa melalui setiap lelaran seluruh array kita bandingkan 1 kurang

78
00:05:54,190 --> 00:05:58,040
supaya bagaimana kita mendapat lebih dari 2, tetapi ia masih n kuasa dua.

79
00:05:58,040 --> 00:06:01,650
Kami tidak mengambil berat tentang faktor pemalar setengah.

80
00:06:01,650 --> 00:06:07,760
Jadi banyak barangan O besar seperti ini bergantung pada jenis hanya melakukan ini jenis matematik,

81
00:06:07,760 --> 00:06:12,260
melakukan aritmetik jumlah wang dan barangan siri geometri,

82
00:06:12,260 --> 00:06:17,750
tetapi kebanyakan mereka dalam kursus ini adalah agak mudah.

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

84
00:06:19,290 --> 00:06:24,430
Mengapa adalah jenis kemasukan dalam Omega n? Apakah omega maksudkan?

85
00:06:24,430 --> 00:06:27,730
[Dua pelajar bercakap pada sekali difahami] >> Yeah.

86
00:06:27,730 --> 00:06:30,630
Omega anda boleh berfikir sebagai rendah terikat.

87
00:06:30,630 --> 00:06:36,550
>> Jadi tidak kira bagaimana cekap algoritma apapun kemasukan anda,

88
00:06:36,550 --> 00:06:41,810
tanpa mengira senarai yang diluluskan dalam, ia sentiasa mempunyai untuk membandingkan sekurang-kurangnya n perkara

89
00:06:41,810 --> 00:06:44,620
atau ia mempunyai untuk melelar atas perkara-perkara n.

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

91
00:06:47,280 --> 00:06:51,190
[Pelajar] Kerana jika senarai sudah disusun, kemudian melalui lelaran pertama

92
00:06:51,190 --> 00:06:54,080
anda hanya boleh menjamin bahawa elemen yang sangat pertama adalah sekurang-kurangnya,

93
00:06:54,080 --> 00:06:56,490
dan lelaran kedua anda hanya boleh menjamin dua yang pertama adalah

94
00:06:56,490 --> 00:07:00,010
kerana anda tidak tahu bahawa seluruh senarai diisih. >> Yeah.

95
00:07:00,010 --> 00:07:08,910
Jika anda lulus dalam senarai disusun sepenuhnya, sekurang-kurangnya anda perlu pergi ke atas semua unsur-unsur

96
00:07:08,910 --> 00:07:12,180
untuk melihat bahawa tiada apa yang perlu digerakkan.

97
00:07:12,180 --> 00:07:14,720
Jadi memaafkan senarai dan berkata, oh, ini sudah disusun,

98
00:07:14,720 --> 00:07:18,240
ia adalah mustahil untuk anda tahu ia disusun sehingga anda memeriksa setiap elemen

99
00:07:18,240 --> 00:07:20,660
untuk melihat bahawa mereka berada dalam perintah disusun.

100
00:07:20,660 --> 00:07:25,290
Jadi lebih rendah terikat pada apapun kemasukan adalah Omega n.

101
00:07:25,290 --> 00:07:28,210
Apa kes terburuk berjalan masa apapun bergabung,

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

103
00:07:31,390 --> 00:07:37,660
Jadi dalam senario kes terburuk, bagaimana apapun merge berjalan?

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

105
00:07:43,690 --> 00:07:49,990
Sorting terpantas algoritma am n log n. Anda tidak boleh melakukan yang lebih baik.

106
00:07:51,930 --> 00:07:55,130
>> Terdapat kes-kes khas, dan jika kita mempunyai masa hari ini - tetapi kita mungkin won't -

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

108
00:07:59,330 --> 00:08:04,050
Tetapi dalam kes umum, anda tidak boleh melakukan lebih baik daripada n log n.

109
00:08:04,050 --> 00:08:09,680
Dan bergabung apapun yang berlaku kepada menjadi salah satu yang perlu anda tahu untuk kursus ini yang n log n.

110
00:08:09,680 --> 00:08:13,260
Dan sebagainya kita sebenarnya akan melaksanakan bahawa hari ini.

111
00:08:13,260 --> 00:08:18,070
Dan akhirnya, tidak lebih daripada tiga ayat, bagaimanakah pemilihan kerja apapun?

112
00:08:18,070 --> 00:08:20,370
Adakah seseorang mahu menjawab, dan saya akan mengira ayat anda

113
00:08:20,370 --> 00:08:22,390
kerana jika anda pergi ke 3 -

114
00:08:25,530 --> 00:08:28,330
Adakah sesiapa ingat apapun pemilihan?

115
00:08:31,280 --> 00:08:37,809
Apapun pemilihan adalah biasanya agak mudah untuk ingat hanya dari nama.

116
00:08:37,809 --> 00:08:45,350
Anda hanya melelar lebih array, mendapati apa sahaja nilai terbesar atau terkecil -

117
00:08:45,350 --> 00:08:47,290
apa jua perintah yang anda sedang menyusun masuk

118
00:08:47,290 --> 00:08:50,750
Jadi mari kita mengatakan bahawa kita sedang sorting daripada yang terkecil kepada yang terbesar.

119
00:08:50,750 --> 00:08:55,250
Anda melelar lebih array, mencari apa jua elemen minimum,

120
00:08:55,250 --> 00:08:59,750
pilih ia, dan kemudian hanya menukar apa sahaja yang berada di tempat pertama.

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

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

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

124
00:09:10,650 --> 00:09:16,050
dan memasukkan mereka ke hadapan array sehingga ia disusun.

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

126
00:09:21,560 --> 00:09:25,710
>> Ini tidak dapat dielakkan muncul dalam bentuk yang anda perlu mengisi apabila anda menyerahkan pset.

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

128
00:09:32,360 --> 00:09:34,230
Okay, jadi sekarang pengekodan masalah.

129
00:09:34,230 --> 00:09:40,140
Saya sudah dihantar melalui e-mel - Adakah sesiapa yang tidak mendapat e-mel yang? Okay.

130
00:09:40,140 --> 00:09:46,630
Saya sudah dihantar melalui e-mel ruang bahawa kita akan menggunakan,

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

132
00:09:52,120 --> 00:09:57,170
kerana r ke belakang - tetapi jika anda klik pada nama saya, anda akan melihat 2 semakan.

133
00:09:57,170 --> 00:10:02,650
Ulangkaji 1 akan saya sudah disalin dan ditampal kod ke dalam kawasan

134
00:10:02,650 --> 00:10:06,900
untuk perkara carian anda akan mempunyai untuk melaksanakan.

135
00:10:06,900 --> 00:10:10,540
Dan Semakan 2 akan menjadi perkara apapun yang kita laksanakan selepas itu.

136
00:10:10,540 --> 00:10:15,770
Jadi, anda boleh klik Semakan saya pada 1 dan bekerja dari sana.

137
00:10:17,350 --> 00:10:22,060
Dan sekarang kita mahu untuk melaksanakan carian binari.

138
00:10:22,060 --> 00:10:26,470
>> Adakah sesiapa yang mahu hanya memberi pseudokod peringkat tinggi penjelasan

139
00:10:26,470 --> 00:10:31,440
apa kita akan perlu lakukan untuk carian? Yeah.

140
00:10:31,440 --> 00:10:36,170
[Pelajar] Anda hanya mengambil pertengahan array dan lihat jika apa yang anda sedang mencari

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

142
00:10:38,650 --> 00:10:41,080
Dan jika ia kurang, anda pergi ke separuh yang kurang,

143
00:10:41,080 --> 00:10:44,750
dan jika ia lebih, anda pergi separuh yang lebih dan anda mengulangi bahawa sehingga anda hanya mendapat satu perkara.

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

145
00:10:46,570 --> 00:10:51,320
Perhatikan bahawa pelbagai nombor kita sudah disusun,

146
00:10:51,320 --> 00:10:57,190
dan sebagainya yang bermakna bahawa kita boleh mengambil kesempatan daripada itu dan kita pertama boleh memeriksa,

147
00:10:57,190 --> 00:11:00,390
okay, saya mencari bilangan 50.

148
00:11:00,390 --> 00:11:03,720
Jadi, saya boleh pergi ke tengah-tengah.

149
00:11:03,720 --> 00:11:07,380
Tengah adalah sukar untuk menentukan apabila ia adalah nombor genap perkara,

150
00:11:07,380 --> 00:11:10,820
tetapi mari kita hanya mengatakan kita akan sentiasa menyingkatkan ke tengah.

151
00:11:10,820 --> 00:11:14,420
Jadi di sini kita mempunyai 8 perkara, jadi tengah-tengah akan menjadi 16.

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

153
00:11:17,330 --> 00:11:21,310
Jadi sekarang saya pada dasarnya boleh merawat pelbagai saya sebagai elemen-elemen ini.

154
00:11:21,310 --> 00:11:23,450
Saya boleh buang segala-galanya dari 16 lebih.

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

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

157
00:11:31,910 --> 00:11:34,730
42 adalah kurang daripada 50, jadi saya boleh buang kedua-dua elemen.

158
00:11:34,730 --> 00:11:36,890
Ini adalah pelbagai baki saya.

159
00:11:36,890 --> 00:11:38,430
Saya akan mencari tengah lagi.

160
00:11:38,430 --> 00:11:42,100
Saya rasa 50 adalah satu contoh yang buruk kerana saya sentiasa membuang perkara-perkara ke kiri,

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

162
00:11:48,280 --> 00:11:52,100
dan ia adalah kurang daripada unsur Saya kini melihat,

163
00:11:52,100 --> 00:11:55,080
maka saya akan buang segala-galanya ke kanan.

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

165
00:11:58,150 --> 00:12:02,310
Perhatikan bahawa kita perlu lulus dalam saiz.

166
00:12:02,310 --> 00:12:06,730
Kita boleh juga tidak perlu kepada saiz-kod keras.

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

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

169
00:12:21,430 --> 00:12:27,180
Bagaimana saya boleh baik memikirkan apa saiz array nombor kini?

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

171
00:12:30,950 --> 00:12:33,630
[Pelajar] Nombor, kurungan, panjang?

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

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

174
00:12:38,580 --> 00:12:42,010
Tatasusunan tidak mempunyai sifat, jadi tiada harta panjang tatasusunan

175
00:12:42,010 --> 00:12:45,650
yang hanya akan memberi anda walau bagaimana lama ia berlaku.

176
00:12:48,180 --> 00:12:51,620
[Pelajar] Lihat berapa banyak memori ia mempunyai dan membahagikan oleh berapa banyak - >> Yeah.

177
00:12:51,620 --> 00:12:55,810
Jadi bagaimana kita boleh melihat berapa banyak memori ia mempunyai? >> [Pelajar] Sizeof. >> Yeah, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof adalah pengendali itu akan kembali saiz array nombor.

179
00:13:01,680 --> 00:13:10,060
Dan itu akan menjadi integer bagaimanapun banyak terdapat kali saiz integer

180
00:13:10,060 --> 00:13:14,050
kerana itulah berapa banyak memori ia sebenarnya mengambil.

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

182
00:13:17,630 --> 00:13:20,560
maka saya akan mahu untuk membahagikan oleh saiz integer.

183
00:13:22,820 --> 00:13:26,010
Okay. Jadi yang membolehkan saya lulus dalam saiz di sini.

184
00:13:26,010 --> 00:13:29,430
Mengapa saya perlukan untuk lulus dalam saiz pada semua?

185
00:13:29,430 --> 00:13:38,570
Mengapa saya tidak boleh hanya melakukan di sini saiz int = sizeof (sisa rumput kering) / sizeof (int)?

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

187
00:13:41,490 --> 00:13:44,470
[Pelajar] Ia bukan satu pembolehubah global.

188
00:13:44,470 --> 00:13:51,540
[Bowden] Haystack wujud dan kita lulus dalam nombor sebagai sisa rumput kering,

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

190
00:13:54,700 --> 00:14:00,170
[Pelajar] Haystack adalah hanya merujuk kepada ia, maka ia akan kembali bagaimana besar rujukan yang.

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

192
00:14:02,150 --> 00:14:09,000
Saya ragu-ragu dalam syarahan bahawa anda telah melihat timbunan lagi benar-benar, betul-betul?

193
00:14:09,000 --> 00:14:11,270
Kita baru sahaja bercakap mengenainya.

194
00:14:11,270 --> 00:14:16,090
Jadi tindanan adalah di mana semua pembolehubah anda akan disimpan.

195
00:14:16,090 --> 00:14:19,960
>> Mana-mana memori yang diperuntukkan bagi pembolehubah tempatan akan dalam tindanan,

196
00:14:19,960 --> 00:14:24,790
dan setiap fungsi mendapat ruang sendiri pada timbunan, bingkai tindanan sendiri adalah apa ia dipanggil.

197
00:14:24,790 --> 00:14:31,590
Jadi utama mempunyai bingkai tindanan, dan di dalamnya akan wujud pelbagai nombor,

198
00:14:31,590 --> 00:14:34,270
dan ia akan menjadi sizeof saiz (nombor).

199
00:14:34,270 --> 00:14:38,180
Ia akan mempunyai saiz nombor dibahagikan dengan saiz unsur-unsur,

200
00:14:38,180 --> 00:14:42,010
tetapi yang semua kehidupan dalam bingkai tindanan utama.

201
00:14:42,010 --> 00:14:45,190
Apabila kita panggil carian, search mendapat bingkai tindanan sendiri,

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

203
00:14:48,840 --> 00:14:56,420
Tetapi hujah ini - jadi sisa rumput kering bukan satu salinan seluruh array ini.

204
00:14:56,420 --> 00:15:00,990
Kami tidak lulus dalam pelbagai keseluruhan sebagai salinan ke carian.

205
00:15:00,990 --> 00:15:04,030
Ia hanya pas rujukan kepada pelbagai itu.

206
00:15:04,030 --> 00:15:11,470
Jadi carian boleh mengakses nombor-nombor ini melalui rujukan ini.

207
00:15:11,470 --> 00:15:17,100
Ia masih mengakses perkara yang hidup di dalam bingkai tindanan utama,

208
00:15:17,100 --> 00:15:22,990
tetapi pada dasarnya, apabila kita mendapat petunjuk, yang sepatutnya tidak lama lagi,

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

210
00:15:24,980 --> 00:15:29,400
Penunjuk hanya rujukan kepada perkara-perkara, dan anda boleh menggunakan petunjuk untuk mengakses perkara-perkara

211
00:15:29,400 --> 00:15:32,030
yang dalam bingkai tindanan perkara lain '.

212
00:15:32,030 --> 00:15:37,660
Jadi, walaupun nombor tempatan utama, kita masih boleh mengakses melalui penunjuk ini.

213
00:15:37,660 --> 00:15:41,770
Tetapi oleh kerana ia hanya penunjuk dan ia hanya rujukan,

214
00:15:41,770 --> 00:15:45,040
sizeof (sisa rumput kering) hanya mengembalikan saiz rujukan sendiri.

215
00:15:45,040 --> 00:15:47,950
Ia tidak akan kembali saiz perkara yang ia menunjuk ke.

216
00:15:47,950 --> 00:15:51,110
Ia tidak akan kembali saiz sebenar nombor.

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

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

219
00:15:57,320 --> 00:16:03,250
Penunjuk akan pergi ke terperinci ketara lebih ngeri dalam minggu akan datang.

220
00:16:06,750 --> 00:16:13,740
Dan ini adalah mengapa banyak perkara yang anda lihat, perkara carian yang paling atau perkara apapun,

221
00:16:13,740 --> 00:16:16,990
mereka hampir semua akan perlu mengambil saiz sebenar array,

222
00:16:16,990 --> 00:16:20,440
kerana dalam C, kita tidak mempunyai idea apa saiz array.

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

224
00:16:22,720 --> 00:16:27,190
Dan anda tidak boleh secara manual lulus di seluruh array kerana anda hanya lulus dalam rujukan

225
00:16:27,190 --> 00:16:30,390
dan ia tidak boleh mendapatkan saiz dari rujukan.

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

227
00:16:32,300 --> 00:16:38,160
Jadi sekarang kita mahu melaksanakan apa yang telah dijelaskan sebelum.

228
00:16:38,160 --> 00:16:41,530
Anda boleh bekerja di atasnya selama satu minit,

229
00:16:41,530 --> 00:16:45,250
dan anda tidak perlu bimbang tentang mendapatkan segala-galanya sempurna 100% bekerja.

230
00:16:45,250 --> 00:16:51,410
Hanya menulis pseudokod separuh untuk bagaimana anda berfikir ia harus bekerja.

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

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

233
00:16:56,350 --> 00:17:02,380
Tetapi adakah sesiapa yang berasa selesa dengan apa yang mereka miliki setakat ini,

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

235
00:17:05,599 --> 00:17:09,690
Adakah sesiapa yang mahu untuk sukarelawan? Atau saya secara rawak akan memilih.

236
00:17:12,680 --> 00:17:18,599
Ia tidak perlu untuk menjadi betul-betul oleh apa-apa langkah tetapi sesuatu yang kita boleh mengubah ke dalam keadaan bekerja.

237
00:17:18,599 --> 00:17:20,720
[Pelajar] Pasti. >> Okay.

238
00:17:20,720 --> 00:17:27,220
Jadi, anda boleh menyimpan semakan dengan mengklik pada ikon Simpan sedikit.

239
00:17:27,220 --> 00:17:29,950
Anda Ramya, kan? >> [Pelajar] Yeah. >> [Bowden] Okay.

240
00:17:29,950 --> 00:17:35,140
Jadi sekarang saya boleh melihat semakan anda dan semua orang boleh tarik sehingga semakan.

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

242
00:17:38,600 --> 00:17:43,160
Jadi Ramya pergi dengan penyelesaian rekursi, yang pastinya satu penyelesaian yang sah.

243
00:17:43,160 --> 00:17:44,970
Terdapat dua cara yang boleh anda lakukan masalah ini.

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

245
00:17:48,060 --> 00:17:53,860
Kebanyakan masalah yang anda hadapi yang boleh dilakukan secara rekursif juga boleh dilakukan iterative.

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

247
00:17:58,510 --> 00:18:03,730
>> Adakah seseorang mahu untuk menentukan apa yang ia bermaksud untuk membuat fungsi rekursi?

248
00:18:07,210 --> 00:18:08,920
[Pelajar] Apabila anda mempunyai fungsi panggilan sendiri

249
00:18:08,920 --> 00:18:13,470
dan kemudian memanggil dirinya sehingga ia datang keluar dengan benar dan benar. >> Yeah.

250
00:18:13,470 --> 00:18:17,680
Satu fungsi rekursi hanya fungsi yang menyeru sendiri.

251
00:18:17,680 --> 00:18:24,140
Terdapat tiga perkara yang besar bahawa fungsi rekursi mesti mempunyai.

252
00:18:24,140 --> 00:18:27,310
Yang pertama adalah jelas, ia memerlukan sendiri.

253
00:18:27,310 --> 00:18:29,650
Yang kedua ialah kes asas.

254
00:18:29,650 --> 00:18:33,390
Jadi, pada satu ketika fungsi perlu untuk berhenti memanggil dirinya,

255
00:18:33,390 --> 00:18:35,610
dan itulah apa kes asas adalah untuk.

256
00:18:35,610 --> 00:18:43,860
Jadi di sini kita tahu bahawa kita perlu berhenti, kita harus berputus asa dalam pencarian kami

257
00:18:43,860 --> 00:18:48,150
apabila permulaan bersamaan akhir - dan kami akan pergi ke atas apa yang bermakna.

258
00:18:48,150 --> 00:18:52,130
Tetapi akhirnya, perkara terakhir yang penting untuk fungsi rekursi:

259
00:18:52,130 --> 00:18:59,250
fungsi entah bagaimana mesti mendekati kes asas.

260
00:18:59,250 --> 00:19:04,140
Seperti jika anda sebenarnya tidak mengemaskini apa-apa apabila anda membuat panggilan rekursi kedua,

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

262
00:19:07,880 --> 00:19:10,130
dan tiada pembolehubah global telah berubah atau apa-apa,

263
00:19:10,130 --> 00:19:14,430
anda tidak akan sampai ke kes asas, di mana yang buruk.

264
00:19:14,430 --> 00:19:17,950
Ia akan menjadi satu rekursi tidak terhingga dan limpahan tindanan.

265
00:19:17,950 --> 00:19:24,330
Tetapi di sini kita lihat bahawa kemas kini berlaku kerana kita sedang mengemaskini memulakan + akhir / 2,

266
00:19:24,330 --> 00:19:28,180
kami sedang mengemaskini hujah akhir di sini, kami sedang mengemaskini hujah mula di sini.

267
00:19:28,180 --> 00:19:32,860
Jadi dalam semua panggilan rekursi kita sedang mengemaskini sesuatu. Okay.

268
00:19:32,860 --> 00:19:38,110
Adakah anda ingin untuk berjalan kita melalui penyelesaian anda? >> Pasti.

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

270
00:19:44,270 --> 00:19:47,910
Saya mempunyai permulaan di mana saya mencari dalam pelbagai dan akhir

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

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

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

274
00:19:58,850 --> 00:20:04,650
Dan jika ia, maka kita mendapati ia, dan saya rasa yang mendapat diluluskan sehingga tahap rekursi.

275
00:20:04,650 --> 00:20:12,540
Dan jika itu tidak benar, maka kita memeriksa sama ada yang nilai pertengahan array adalah terlalu besar,

276
00:20:12,540 --> 00:20:19,320
di mana kita melihat separuh kiri array dengan pergi dari awal hingga indeks pertengahan.

277
00:20:19,320 --> 00:20:22,710
Dan sebaliknya kita lakukan separuh akhir.

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

279
00:20:24,740 --> 00:20:27,730
Itulah bunyi yang baik.

280
00:20:27,730 --> 00:20:36,640
Okay, jadi beberapa perkara, dan sebenarnya, ini adalah satu perkara yang sangat peringkat tinggi

281
00:20:36,640 --> 00:20:41,270
bahawa anda tidak akan perlu tahu untuk kursus ini, tetapi ia adalah benar.

282
00:20:41,270 --> 00:20:46,080
Fungsi rekursi, anda sentiasa mendengar bahawa mereka banyak yang buruk

283
00:20:46,080 --> 00:20:51,160
kerana jika anda rekursif memanggil diri anda terlalu banyak kali, anda akan mendapat limpahan timbunan

284
00:20:51,160 --> 00:20:54,990
kerana, seperti yang saya katakan sebelum ini, setiap fungsi mendapat bingkai tindanan sendiri.

285
00:20:54,990 --> 00:20:59,500
Jadi setiap panggilan fungsi rekursi mendapat bingkai tindanan sendiri.

286
00:20:59,500 --> 00:21:04,140
Jadi, jika anda membuat 1,000 panggilan rekursi, anda akan mendapat 1,000 bingkai tindanan,

287
00:21:04,140 --> 00:21:08,390
dan cepat anda membawa untuk mempunyai bingkai tindanan terlalu banyak dan perkara-perkara yang hanya memecahkan.

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

289
00:21:13,480 --> 00:21:19,370
Tetapi terdapat subset bagus fungsi rekursi dipanggil fungsi ekor rekursi,

290
00:21:19,370 --> 00:21:26,120
dan ini berlaku untuk menjadi contoh di mana jika pengkompil notis ini

291
00:21:26,120 --> 00:21:29,920
dan ia sepatutnya, saya fikir dilafaz jika anda lulus-O2 bendera

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

293
00:21:33,250 --> 00:21:40,050
>> Ia akan menggunakan semula bingkai tindanan yang sama berulang-ulang kali untuk setiap panggilan rekursi.

294
00:21:40,050 --> 00:21:47,010
Dan sebagainya kerana anda sedang menggunakan bingkai tindanan yang sama, anda tidak perlu bimbang tentang

295
00:21:47,010 --> 00:21:51,690
pernah timbunan melimpah, dan pada masa yang sama, seperti yang anda katakan sebelum ini,

296
00:21:51,690 --> 00:21:56,380
di mana apabila anda kembali benar, maka ia telah kembali sehingga semua ini bingkai tindanan

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

298
00:22:01,740 --> 00:22:05,360
Jadi yang tidak perlu berlaku apabila fungsi rekursi ekor.

299
00:22:05,360 --> 00:22:13,740
Dan jadi apa membuat ini ekor fungsi rekursi ialah notis bahawa bagi apa-apa panggilan yang diberikan kepada searchHelp

300
00:22:13,740 --> 00:22:18,470
panggilan rekursi bahawa ia membuat apa ia kembali.

301
00:22:18,470 --> 00:22:25,290
Jadi dalam panggilan pertama untuk SearchHelp, sama ada kita dengan serta-merta mengembalikan palsu,

302
00:22:25,290 --> 00:22:29,590
dengan serta-merta mengembalikan benar, atau kita membuat panggilan rekursi untuk SearchHelp

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

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

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

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

307
00:23:01,470 --> 00:23:05,740
tidak lagi ekor rekursi kerana ia sebenarnya tidak perlu untuk kembali

308
00:23:05,740 --> 00:23:10,400
kembali kepada bingkai timbunan sebelumnya supaya bahawa panggilan sebelumnya kepada fungsi

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

310
00:23:13,040 --> 00:23:22,190
Jadi ini tidak rekursi ekor, tetapi apa yang kita telah sebelum ini baik ekor rekursi. Yeah.

311
00:23:22,190 --> 00:23:27,000
[Pelajar] Tidakkah kes asas kedua diperiksa pertama

312
00:23:27,000 --> 00:23:30,640
kerana mungkin ada keadaan di mana apabila anda lulus ia hujah

313
00:23:30,640 --> 00:23:35,770
anda telah memulakan akhir =, tetapi mereka adalah nilai jarum.

314
00:23:35,770 --> 00:23:47,310
Soalan itu tidak boleh kita lari ke dalam kes di mana akhir adalah nilai jarum

315
00:23:47,310 --> 00:23:52,000
atau memulakan akhir = sewajarnya, memulakan akhir =

316
00:23:52,000 --> 00:23:59,480
dan anda telah sebenarnya tidak diperiksa bahawa nilai tertentu lagi,

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

318
00:24:03,910 --> 00:24:07,890
Tetapi kita sudah dikembalikan palsu dan kita tidak pernah benar-benar diperiksa nilai.

319
00:24:07,890 --> 00:24:14,240
Jadi, sekurang-kurangnya, dalam panggilan pertama, jika saiz adalah 0, maka kita mahu untuk kembali palsu.

320
00:24:14,240 --> 00:24:17,710
Tetapi jika saiz adalah 1, maka mula tidak akan ke hujung sama,

321
00:24:17,710 --> 00:24:19,820
dan kita sekurang-kurangnya akan memeriksa elemen satu.

322
00:24:19,820 --> 00:24:26,750
Tetapi saya fikir anda adalah betul bahawa kita boleh berakhir di dalam kes di mana bermula + akhir / 2,

323
00:24:26,750 --> 00:24:31,190
permulaan berakhir sehingga menjadi sama sebagai permulaan + akhir / 2,

324
00:24:31,190 --> 00:24:35,350
tetapi kita tidak pernah benar-benar diperiksa elemen yang.

325
00:24:35,350 --> 00:24:44,740
>> Jadi, jika kita periksa dahulu adalah elemen tengah nilai kita sedang mencari,

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

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

328
00:24:50,740 --> 00:24:58,440
kerana kita hanya akan mengemaskini kepada kes di mana kita berada pada pelbagai unsur tunggal.

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

330
00:25:01,110 --> 00:25:03,530
maka segala-galanya adalah salah. Yeah.

331
00:25:03,530 --> 00:25:08,900
[Pelajar] Masalahnya ialah bahawa sejak saiz sebenarnya adalah lebih besar daripada bilangan elemen dalam array,

332
00:25:08,900 --> 00:25:13,070
sudah terdapat offset - >> Jadi akan saiz -

333
00:25:13,070 --> 00:25:19,380
[Pelajar] Katakanlah (wahai Muhammad) jika array adalah saiz 0, maka SearchHelp sebenarnya akan menyemak sisa rumput kering daripada 0

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

335
00:25:21,490 --> 00:25:25,300
Array mempunyai saiz 0, jadi 0 adalah - >> Yeah.

336
00:25:25,300 --> 00:25:30,750
Ada satu lagi perkara yang - ia mungkin baik. Mari kita berfikir.

337
00:25:30,750 --> 00:25:40,120
Jadi jika array mempunyai 10 elemen dan satu tengah kita pergi untuk memeriksa ialah indeks 5,

338
00:25:40,120 --> 00:25:45,700
jadi kita memeriksa 5, dan katakan bahawa nilainya adalah kurang.

339
00:25:45,700 --> 00:25:50,720
Jadi kita membuang segala-galanya jauh daripada 5 seterusnya.

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

341
00:25:54,030 --> 00:25:57,450
supaya yeah, ia sentiasa akan tinggal di luar akhir array.

342
00:25:57,450 --> 00:26:03,570
Jika ia adalah kes jika ia adalah genap atau ganjil, maka kita akan memeriksa, katakan, 4,

343
00:26:03,570 --> 00:26:05,770
tetapi kita masih membuang -

344
00:26:05,770 --> 00:26:13,500
Jadi yeah, akhir sentiasa akan menjadi luar akhir sebenar array.

345
00:26:13,500 --> 00:26:18,350
Jadi elemen kami memberi tumpuan kepada, akhir sentiasa akan menjadi satu selepas itu.

346
00:26:18,350 --> 00:26:24,270
Dan jadi jika permulaan tidak pernah akhir yang sama, kita berada dalam pelbagai saiz 0.

347
00:26:24,270 --> 00:26:35,600
>> Perkara lain saya memikirkan kita sedang mengemaskini bermula untuk memulakan + akhir / 2,

348
00:26:35,600 --> 00:26:44,020
jadi ini adalah kes bahawa saya mempunyai masalah dengan, di mana bermula + akhir / 2

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

350
00:26:46,820 --> 00:26:58,150
Katakan kita mempunyai pelbagai 10-unsur ini. Apa sahaja.

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

352
00:27:03,250 --> 00:27:07,060
dan jika itu tidak nilai, katakan kita mahu untuk mengemaskini.

353
00:27:07,060 --> 00:27:10,060
Nilai adalah lebih besar, jadi kita mahu melihat setengah ini array.

354
00:27:10,060 --> 00:27:15,910
Jadi bagaimana kita hendak mengemaskini permulaan, kita sedang mengemaskini awal hingga kini menjadi elemen ini.

355
00:27:15,910 --> 00:27:23,790
Tetapi ini masih boleh bekerja, atau sekurang-kurangnya, anda boleh melakukan permulaan + akhir / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Pelajar] Anda tidak perlu memulakan akhir + [didengar] >> Yeah.

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

358
00:27:33,240 --> 00:27:36,800
Jadi kita tidak perlu untuk mengemas kini mula menjadi elemen ini.

359
00:27:36,800 --> 00:27:39,560
Kita hanya boleh melangkau ia dan mengemas kini mula menjadi elemen ini.

360
00:27:39,560 --> 00:27:46,060
Dan ada pernah kes, katakan, bahawa ini adalah akhir,

361
00:27:46,060 --> 00:27:53,140
demikian maka mula akan ini, mulakan + akhir / 2 akan ini,

362
00:27:53,140 --> 00:28:00,580
bermula akhir + - Ya, saya fikir ia boleh berakhir dalam rekursi tidak terhingga.

363
00:28:00,580 --> 00:28:12,690
Katakan ia hanya pelbagai saiz 2 atau pelbagai saiz daripada 1. Saya rasa ini akan bekerja.

364
00:28:12,690 --> 00:28:19,490
Jadi, pada masa ini, permulaan adalah bahawa elemen dan akhir adalah 1 melebihinya.

365
00:28:19,490 --> 00:28:24,110
Jadi elemen yang kita pergi untuk memeriksa adalah salah satu ini,

366
00:28:24,110 --> 00:28:29,400
dan kemudian apabila kita mengemaskini permulaan, kami mengemas kini mula menjadi 0 + 1/2,

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

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

369
00:28:36,210 --> 00:28:43,310
Jadi ini adalah kes di mana setiap panggilan rekursi sebenarnya mesti mengemaskinikan sesuatu.

370
00:28:43,310 --> 00:28:48,370
Jadi yang perlu kita lakukan permulaan + akhir / 2 + 1, atau lain ada kes

371
00:28:48,370 --> 00:28:50,710
di mana kita sebenarnya tidak mengemaskini permulaan.

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

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

374
00:28:56,310 --> 00:29:03,860
Adakah sesiapa yang mempunyai soalan mengenai penyelesaian ini atau apa-apa lebih banyak komen?

375
00:29:05,220 --> 00:29:10,280
Okay. Adakah sesiapa yang telah lelaran penyelesaian yang kita semua boleh melihat?

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

377
00:29:20,940 --> 00:29:25,950
Atau juga saya rasa jika anda membuka perempuan, maka anda mungkin mempunyai diatasi yang sebelumnya.

378
00:29:25,950 --> 00:29:28,810
Adakah ia menyimpan secara automatik? Saya tidak positif.

379
00:29:35,090 --> 00:29:39,130
Adakah sesiapa yang telah lelaran?

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

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

382
00:30:00,260 --> 00:30:02,830
Lelaran penyelesaian.

383
00:30:02,830 --> 00:30:07,140
Kami akan mahu pada dasarnya melakukan idea yang sama

384
00:30:07,140 --> 00:30:16,530
di mana kita mahu menjejaki akhir baru array dan permulaan yang baru array

385
00:30:16,530 --> 00:30:18,510
dan berbuat demikian berulang.

386
00:30:18,510 --> 00:30:22,430
Dan jika apa yang kita sedang mengesan sebagai permulaan dan akhir yang pernah bersilang,

387
00:30:22,430 --> 00:30:29,020
maka kita tidak mendapati ia dan kita boleh kembali palsu.

388
00:30:29,020 --> 00:30:37,540
Jadi bagaimana saya boleh berbuat demikian? Sesiapa yang mempunyai cadangan atau kod bagi saya untuk tarik sehingga?

389
00:30:42,190 --> 00:30:47,450
[Pelajar] Adakah gelung sementara. >> Yeah.

390
00:30:47,450 --> 00:30:49,450
Anda akan mahu untuk melakukan gelung.

391
00:30:49,450 --> 00:30:51,830
>> Adakah anda mempunyai kod saya boleh tarik ke atas, atau apa yang anda akan mencadangkan?

392
00:30:51,830 --> 00:30:56,340
[Pelajar] Saya fikir begitu. >> Baiklah. Ini menjadikan perkara yang mudah. Apa nama anda?

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

394
00:31:00,140 --> 00:31:04,190
Ulangkaji 1. Okay.

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

396
00:31:13,200 --> 00:31:17,080
Sehingga tidak cukup apa yang kita dipanggil akhir sebelum.

397
00:31:17,080 --> 00:31:22,750
Sebenarnya, akhir kini dalam array. Ia merupakan satu elemen kita harus mempertimbangkan.

398
00:31:22,750 --> 00:31:26,890
Begitu rendah adalah 0, sehingga saiz array - 1,

399
00:31:26,890 --> 00:31:34,780
dan sekarang kita sedang gelung, dan kita memeriksa -

400
00:31:34,780 --> 00:31:37,340
Saya rasa anda boleh berjalan melalui.

401
00:31:37,340 --> 00:31:41,420
Apakah pemikiran anda melalui ini? Berjalan kami melalui kod anda.

402
00:31:41,420 --> 00:31:49,940
[Pelajar] Pasti. Lihatlah nilai sisa rumput kering di tengah-tengah dan membandingkannya dengan jarum.

403
00:31:49,940 --> 00:31:58,520
Jadi, jika ia adalah lebih besar daripada jarum anda, maka anda mahu - oh, sebenarnya, yang harus ke belakang.

404
00:31:58,520 --> 00:32:05,180
Anda akan mahu buang separuh yang betul, dan sebagainya yeah, yang sepatutnya menjadi cara.

405
00:32:05,180 --> 00:32:08,830
[Bowden] Jadi ini harus menjadi kurang? Adakah bahawa apa yang anda katakan? >> [Pelajar] Yeah.

406
00:32:08,830 --> 00:32:10,390
[Bowden] Okay. Kurang.

407
00:32:10,390 --> 00:32:15,700
Jadi, jika apa yang kita melihat adalah lebih kecil daripada apa yang kita mahu,

408
00:32:15,700 --> 00:32:19,410
kemudian yeah, kita mahu buang separuh kiri,

409
00:32:19,410 --> 00:32:22,210
yang bermakna kita sedang mengemaskini segala apa yang kita sedang mempertimbangkan

410
00:32:22,210 --> 00:32:26,610
dengan bergerak rendah ke kanan array.

411
00:32:26,610 --> 00:32:30,130
Ini kelihatan baik.

412
00:32:30,130 --> 00:32:34,550
Saya rasa ia mempunyai isu yang sama bahawa kita berkata pada yang sebelumnya,

413
00:32:34,550 --> 00:32:49,760
di mana jika rendah adalah 0 dan adalah 1, maka rendah + up / 2 akan ditubuhkan untuk menjadi perkara yang sama sekali lagi.

414
00:32:49,760 --> 00:32:53,860
>> Dan walaupun itu bukan kes itu, ia masih lebih cekap sekurang-kurangnya

415
00:32:53,860 --> 00:32:57,630
hanya buang elemen kita hanya melihat di mana kita tahu adalah salah.

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

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

418
00:33:05,900 --> 00:33:09,580
[Pelajar] Dan perlu ada double tanda sama. >> [Bowden] Yeah.

419
00:33:09,580 --> 00:33:11,340
[Pelajar] Yeah.

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

421
00:33:15,910 --> 00:33:21,280
Dan akhirnya, sekarang bahawa kita mempunyai ini 1 + - 1 perkara,

422
00:33:21,280 --> 00:33:31,520
ia - ia mungkin tidak - adalah ia pernah mungkin rendah untuk menamatkan dengan nilai yang lebih besar daripada sehingga?

423
00:33:35,710 --> 00:33:40,320
Saya fikir satu-satunya cara yang boleh berlaku - Adakah ia mungkin? >> [Pelajar] saya tidak tahu.

424
00:33:40,320 --> 00:33:45,220
Tetapi jika ia mendapat dipenggal dan kemudian mendapat tolak bahawa 1 dan kemudian - >> Yeah.

425
00:33:45,220 --> 00:33:47,480
[Pelajar] Ia mungkin akan mendapat sehingga merosakkan.

426
00:33:49,700 --> 00:33:53,940
Saya fikir ia harus baik hanya kerana

427
00:33:53,940 --> 00:33:58,800
untuk ia berakhir lebih rendah, mereka akan mempunyai untuk menjadi sama, saya fikir.

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

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

430
00:34:06,670 --> 00:34:11,530
Perhatikan bahawa walaupun masalah ini adalah tidak lagi rekursi,

431
00:34:11,530 --> 00:34:17,400
jenis yang sama idea memohon mana kita boleh melihat bagaimana ini begitu mudah meminjamkan sendiri

432
00:34:17,400 --> 00:34:23,659
kepada penyelesaian rekursi oleh hakikat bahawa kita hanya mengemaskini indeks berulang kali,

433
00:34:23,659 --> 00:34:29,960
kita membuat masalah yang lebih kecil dan lebih kecil, kami memberi tumpuan kepada subset array.

434
00:34:29,960 --> 00:34:40,860
[Pelajar] Jika rendah adalah 0 dan sehingga adalah 1, kedua-dua mereka akan menjadi 0 + 1/2, yang akan pergi kepada 0,

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

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

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

438
00:34:55,100 --> 00:34:58,590
Kami kini tidak berbuat demikian? Oh!

439
00:35:00,610 --> 00:35:02,460
Jika it's -

440
00:35:05,340 --> 00:35:13,740
Ya. Kita tidak boleh hanya melakukan ujian turun di sini kerana katakan pertengahan pertama -

441
00:35:13,740 --> 00:35:16,430
[Pelajar] Ia sebenarnya tidak buang terikat.

442
00:35:16,430 --> 00:35:20,220
Jadi, jika anda buang terikat, anda perlu untuk memeriksa ia mula-mula atau apa sahaja.

443
00:35:20,220 --> 00:35:23,350
Ah. Yeah. >> [Pelajar] Yeah.

444
00:35:23,350 --> 00:35:29,650
Jadi sekarang kita telah dibuang satu kita kini melihat,

445
00:35:29,650 --> 00:35:33,260
yang bererti kita kini perlu juga mempunyai

446
00:35:33,260 --> 00:35:44,810
jika (sisa rumput kering [(rendah + anak) / 2] == jarum), maka kita boleh kembali benar.

447
00:35:44,810 --> 00:35:52,070
Dan sama ada saya meletakkan lain atau hanya jika, ia bermaksud secara literal perkara yang sama

448
00:35:52,070 --> 00:35:57,110
kerana ini akan dikembalikan benar.

449
00:35:57,110 --> 00:36:01,450
Jadi saya akan meletakkan lain jika, tetapi ia tidak mengapa.

450
00:36:01,450 --> 00:36:10,440
>> Jadi lain jika ini, lain ini, dan ini adalah satu perkara yang biasa saya lakukan

451
00:36:10,440 --> 00:36:14,340
di mana walaupun ia adalah kes di mana segala-galanya adalah baik di sini,

452
00:36:14,340 --> 00:36:22,780
seperti rendah tidak boleh lebih dari meningkat naik, ia bukan hujah yang bernilai kira-kira sama ada yang benar.

453
00:36:22,780 --> 00:36:28,010
Jadi anda juga boleh mengatakan manakala yang rendah adalah kurang daripada atau sama dengan

454
00:36:28,010 --> 00:36:30,720
atau semasa rendah adalah kurang daripada

455
00:36:30,720 --> 00:36:35,300
jadi jika mereka yang pernah sama atau rendah berlaku untuk melalukan,

456
00:36:35,300 --> 00:36:40,130
maka kita boleh keluar gelung ini.

457
00:36:41,410 --> 00:36:44,630
Soalan, kebimbangan, komen?

458
00:36:47,080 --> 00:36:49,270
Okay. Ini kelihatan baik.

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

460
00:36:52,230 --> 00:37:04,030
Jika kita pergi ke semakan kedua saya, kita lihat nombor-nombor yang sama,

461
00:37:04,030 --> 00:37:07,550
tetapi kini mereka tidak lagi dalam usaha disusun.

462
00:37:07,550 --> 00:37:12,840
Dan kita mahu untuk melaksanakan apapun menggunakan mana-mana algoritma di O n log n.

463
00:37:12,840 --> 00:37:17,240
Jadi algoritma manakah anda fikir kita perlu melaksanakan di sini? >> [Pelajar] Gabung apapun.

464
00:37:17,240 --> 00:37:23,810
[Bowden] Yeah. Gabung apapun adalah O (n log n), supaya apa yang kita hendak lakukan.

465
00:37:23,810 --> 00:37:26,680
Dan masalah itu akan menjadi cantik serupa,

466
00:37:26,680 --> 00:37:31,920
di mana ia mudah meminjamkan sendiri kepada penyelesaian rekursi.

467
00:37:31,920 --> 00:37:35,580
Kita juga boleh tampil dengan penyelesaian lelaran jika kita mahu,

468
00:37:35,580 --> 00:37:42,540
tetapi rekursi akan menjadi lebih mudah di sini dan kita harus lakukan rekursi.

469
00:37:45,120 --> 00:37:49,530
Saya rasa kita akan berjalan melalui apapun merge pertama,

470
00:37:49,530 --> 00:37:54,280
walaupun terdapat video yang indah di merge apapun sudah. [Ketawa]

471
00:37:54,280 --> 00:37:59,780
Jadi bergabung apapun terdapat - Saya membuang begitu banyak kertas ini.

472
00:37:59,780 --> 00:38:02,080
Oh, hanya terdapat 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
Okay.

476
00:38:29,910 --> 00:38:33,460
Gabung mengambil masa dua tatasusunan yang berasingan.

477
00:38:33,460 --> 00:38:36,780
Individu kedua-dua barisan kedua-duanya disusun.

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

479
00:38:40,970 --> 00:38:46,710
Sekarang apa merge harus lakukan adalah menggabungkan mereka ke dalam pelbagai tunggal yang dirinya disusun.

480
00:38:46,710 --> 00:38:57,130
Jadi kita mahu pelbagai saiz daripada 6 yang akan mempunyai unsur-unsur di dalamnya

481
00:38:57,130 --> 00:38:59,390
dalam perintah disusun.

482
00:38:59,390 --> 00:39:03,390
>> Dan supaya kita boleh mengambil kesempatan daripada hakikat bahawa kedua-dua tatasusunan disusun

483
00:39:03,390 --> 00:39:06,800
untuk melakukan ini dalam masa linear,

484
00:39:06,800 --> 00:39:13,510
masa makna linear jika array ini adalah saiz x dan ini adalah y saiz,

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

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

487
00:39:23,150 --> 00:39:26,030
[Pelajar] Bolehkah kita mula dari kiri?

488
00:39:26,030 --> 00:39:30,150
Jadi, anda akan meletakkan 0, ke pertama dan kemudian 1 dan kemudian di sini anda berada di 2.

489
00:39:30,150 --> 00:39:33,320
Jadi ia adalah jenis seperti anda mempunyai tab yang bergerak ke kanan. >> [Bowden] Yeah.

490
00:39:33,320 --> 00:39:41,070
Bagi kedua-dua tatasusunan ini jika kita hanya memberi tumpuan kepada elemen terkiri.

491
00:39:41,070 --> 00:39:43,530
Kerana kedua-dua tatasusunan disusun, kita tahu bahawa ini 2 elemen

492
00:39:43,530 --> 00:39:46,920
adalah unsur terkecil dalam pelbagai sama ada.

493
00:39:46,920 --> 00:39:53,500
Jadi yang bermaksud bahawa 1 daripada 2 elemen tersebut mesti menjadi elemen terkecil dalam pelbagai digabungkan kami.

494
00:39:53,500 --> 00:39:58,190
Ia hanya kebetulan bahawa terkecil adalah salah pada masa yang betul ini.

495
00:39:58,190 --> 00:40:02,580
Jadi kita mengambil 0, masukkan ia di sebelah kiri kerana 0 adalah kurang daripada 1,

496
00:40:02,580 --> 00:40:08,210
supaya mengambil 0, masukkannya ke dalam kedudukan pertama kita, dan kemudian kita mengemaskinikan

497
00:40:08,210 --> 00:40:12,070
kini memberi tumpuan kepada elemen pertama.

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

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

500
00:40:20,670 --> 00:40:25,300
Kami mengemaskini penunjuk ini menunjukkan lelaki ini.

501
00:40:25,300 --> 00:40:33,160
Sekarang kita melakukannya sekali lagi, jadi 2. Ini akan mengemaskini, bandingkan ini 2, 3.

502
00:40:33,160 --> 00:40:37,770
Ini kemas kini, maka 4 dan 5.

503
00:40:37,770 --> 00:40:42,110
Jadi yang bergabung.

504
00:40:42,110 --> 00:40:49,010
>> Ia perlu cukup jelas bahawa ia adalah masa linear kerana kita hanya pergi di seluruh setiap elemen sekali.

505
00:40:49,010 --> 00:40:55,980
Dan itu adalah langkah terbesar untuk melaksanakan apapun merge melakukan ini.

506
00:40:55,980 --> 00:40:59,330
Dan ia bukan yang keras.

507
00:40:59,330 --> 00:41:15,020
Satu perkara yang pasangan perlu dibimbangkan mari mengatakan kita telah penggabungan 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
Dalam kes ini kita akhirnya dalam senario di mana satu ini akan menjadi lebih kecil,

509
00:41:30,930 --> 00:41:36,160
maka kita mengemaskini penunjuk ini, yang satu ini akan menjadi lebih kecil, mengemaskini ini,

510
00:41:36,160 --> 00:41:41,280
yang satu ini lebih kecil, dan sekarang anda perlu untuk mengiktiraf

511
00:41:41,280 --> 00:41:44,220
apabila anda telah benar-benar kehabisan unsur-unsur untuk membandingkan dengan.

512
00:41:44,220 --> 00:41:49,400
Oleh kerana kita telah menggunakan pelbagai keseluruhan,

513
00:41:49,400 --> 00:41:55,190
segala-galanya dalam pelbagai ini kini hanya dimasukkan ke sini.

514
00:41:55,190 --> 00:42:02,040
Jadi, jika kita pernah berjalan ke titik di mana salah tatasusunan kami sepenuhnya digabungkan sudah,

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

516
00:42:06,510 --> 00:42:13,630
Jadi kita hanya boleh memasukkan 4, 5, 6. Okay.

517
00:42:13,630 --> 00:42:18,070
Itu adalah satu perkara untuk menonton keluar untuk.

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

519
00:42:26,120 --> 00:42:32,600
Gabung menyusun maka berdasarkan itu, ia adalah 2 langkah, 2 langkah bodoh.

520
00:42:38,800 --> 00:42:42,090
Mari kita hanya memberi pelbagai ini.

521
00:42:57,920 --> 00:43:05,680
Jadi bergabung apapun, langkah 1 adalah untuk rekursif memecahkan array ke dalam bahagian.

522
00:43:05,680 --> 00:43:09,350
Jadi berpecah pelbagai ini ke dalam bahagian.

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

524
00:43:22,920 --> 00:43:25,800
Dan sekarang kita lakukan sekali lagi dan kami berpecah ini ke dalam bahagian.

525
00:43:25,800 --> 00:43:27,530
Saya hanya akan melakukannya di sebelah 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 perkara yang sama di sini.

528
00:43:37,440 --> 00:43:40,340
Dan sekarang kita berpecah kepada dua lagi.

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

530
00:43:51,080 --> 00:43:53,170
Jadi yang kes asas kami.

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

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 memecahkan ke 8, 23, 42, dan 108.

534
00:44:15,730 --> 00:44:24,000
Jadi sekarang kita berada di titik ini, kini melangkah dua apapun merge hanya penggabungan berpasangan untuk senarai.

535
00:44:24,000 --> 00:44:27,610
Jadi kita mahu untuk bergabung ini. Kami hanya memanggil bergabung.

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

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

538
00:44:33,920 --> 00:44:41,440
Sekarang kita mahu untuk bergabung ini, dan yang akan kembali senarai dengan mereka dalam usaha disusun,

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

540
00:44:44,160 --> 00:44:57,380
Kami bergabung mereka - Saya tidak boleh menulis - 8, 23 dan 42, 108.

541
00:44:57,380 --> 00:45:02,890
Jadi kita mempunyai pasangan yang digabungkan 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 bahawa setiap senarai ini disusun dalam dirinya,

544
00:45:10,130 --> 00:45:15,220
dan kemudian kita hanya boleh menggabungkan senarai ini untuk mendapatkan senarai saiz 4 yang disusun

545
00:45:15,220 --> 00:45:19,990
dan bergabung kedua-dua senarai untuk mendapatkan senarai saiz 4 yang disusun.

546
00:45:19,990 --> 00:45:25,710
Dan akhirnya, kita boleh menggabungkan kedua-dua senarai saiz 4 untuk mendapatkan satu senarai sebanyak 8 saiz yang disusun.

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

548
00:45:34,030 --> 00:45:40,390
jadi apabila kita berurusan dengan penggabungan ini, jadi seperti kos keseluruhan merge

549
00:45:40,390 --> 00:45:43,410
untuk kedua-dua senarai hanya 2 kerana -

550
00:45:43,410 --> 00:45:49,610
Atau baik, ia O n, tetapi n di sini adalah hanya 2 elemen, jadi ia adalah 2.

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

552
00:45:52,850 --> 00:45:58,820
merentasi semua bergabung yang perlu kita lakukan, kita akhirnya melakukan n.

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

554
00:46:03,210 --> 00:46:08,060
jadi kos penggabungan dalam set ini n.

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

556
00:46:10,810 --> 00:46:16,980
Kami akan menggabungkan ini 2, maka ini 2, dan individu bergabung ini akan mengambil empat operasi,

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

558
00:46:23,610 --> 00:46:29,030
kita akhirnya bergabung n jumlah perkara, dan sebagainya langkah ini mengambil n.

559
00:46:29,030 --> 00:46:33,670
Dan sebagainya setiap peringkat mengambil n unsur yang digabungkan.

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

561
00:46:36,110 --> 00:46:40,160
Di setiap peringkat, pelbagai kami tumbuh dengan 2 saiz.

562
00:46:40,160 --> 00:46:44,590
Berikut tatasusunan kita daripada 1 saiz, di sini mereka berada saiz 2, di sini mereka berada daripada 4 saiz,

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

564
00:46:46,470 --> 00:46:56,450
Jadi kerana ia adalah dua kali ganda, ada akan menjadi jumlah log n tahap ini.

565
00:46:56,450 --> 00:47:02,090
Jadi dengan log n peringkat, setiap peringkat individu mengambil n operasi jumlah,

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

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

568
00:47:08,940 --> 00:47:13,320
Pernahkah orang sudah membuat kemajuan tentang bagaimana untuk melaksanakan ini?

569
00:47:13,320 --> 00:47:18,260
Adakah sesiapa yang sudah dalam keadaan di mana saya hanya boleh tarik sehingga kod mereka?

570
00:47:20,320 --> 00:47:22,260
Saya boleh memberi satu minit.

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 mengesyorkan berulang -

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

574
00:47:30,510 --> 00:47:33,750
kerana untuk melakukan rekursi untuk bergabung, anda akan perlu untuk lulus sekumpulan saiz yang berbeza.

575
00:47:33,750 --> 00:47:37,150
Anda boleh, tetapi ia menjengkelkan.

576
00:47:37,150 --> 00:47:43,720
Tetapi rekursi untuk menyelesaikan sendiri adalah cukup mudah.

577
00:47:43,720 --> 00:47:49,190
Anda hanya benar-benar memanggil apapun pada separuh kiri, jenis pada separuh yang betul. Okay.

578
00:47:51,770 --> 00:47:54,860
Sesiapa yang mempunyai apa-apa yang saya boleh tarik lagi?

579
00:47:54,860 --> 00:47:57,540
Atau lain saya akan memberikan satu minit.

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

581
00:47:59,900 --> 00:48:02,970
Sesiapa yang mempunyai sesuatu yang kita boleh bekerja dengan?

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

583
00:48:09,680 --> 00:48:14,050
>> Sesiapa yang mempunyai lebih daripada ini bahawa saya boleh tarik sehingga?

584
00:48:14,050 --> 00:48:17,770
[Pelajar] Yeah. Anda boleh tarik sehingga lombong. >> Baiklah.

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

586
00:48:22,170 --> 00:48:25,280
[Pelajar] Terdapat banyak keadaan. >> Oh, menembak. Bolehkah anda -

587
00:48:25,280 --> 00:48:28,110
[Pelajar] saya perlu untuk menyimpannya. >> Yeah.

588
00:48:32,420 --> 00:48:35,730
Jadi kami lakukan melakukan merge berasingan.

589
00:48:35,730 --> 00:48:38,570
Oh, tetapi ia bukan yang buruk.

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

591
00:48:41,650 --> 00:48:47,080
Jadi apapun sendiri hanya memanggil mergeSortHelp.

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

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

594
00:48:55,700 --> 00:49:01,270
yang menyusun setiap separuh array dan kemudian untuk menggabungkan kedua-dua mereka.

595
00:49:04,960 --> 00:49:08,050
[Bowden] Okay, jadi memberikan saya sesaat.

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

597
00:49:17,100 --> 00:49:19,400
Yeah. Saya hilang sesuatu.

598
00:49:19,400 --> 00:49:23,100
Di merge, Saya sedar bahawa saya perlu untuk mewujudkan pelbagai baru

599
00:49:23,100 --> 00:49:26,530
kerana saya tidak boleh melakukannya di tempat. >> Ya. Anda tidak boleh. Membetulkan.

600
00:49:26,530 --> 00:49:28,170
[Pelajar] Jadi saya mencipta pelbagai baru.

601
00:49:28,170 --> 00:49:31,510
Saya terlupa pada akhir bergabung semula menukar.

602
00:49:31,510 --> 00:49:34,490
Okay. Kita memerlukan barisan baru.

603
00:49:34,490 --> 00:49:41,000
Dalam apapun merge, ini adalah hampir sentiasa benar.

604
00:49:41,000 --> 00:49:44,340
Sebahagian daripada kos algoritma yang lebih baik masa-bijak

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

606
00:49:47,310 --> 00:49:51,570
Jadi di sini, tidak kira bagaimana anda melakukannya bergabung apapun,

607
00:49:51,570 --> 00:49:54,780
anda pasti akan memerlukan untuk menggunakan beberapa memori tambahan.

608
00:49:54,780 --> 00:49:58,240
Beliau mencipta pelbagai baru.

609
00:49:58,240 --> 00:50:03,400
Dan kemudian anda mengatakan pada akhir kita hanya perlu untuk menyalin pelbagai baru ke dalam pelbagai asal.

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

611
00:50:04,830 --> 00:50:08,210
Saya tidak tahu jika yang berfungsi dari segi pengiraan oleh rujukan atau apa sahaja -

612
00:50:08,210 --> 00:50:11,650
Ya, ia akan berfungsi. >> [Pelajar] Okay.

613
00:50:20,620 --> 00:50:24,480
Adakah anda cuba berjalan ini? >> [Pelajar] Tidak, belum lagi. >> Okay.

614
00:50:24,480 --> 00:50:28,880
Cuba berjalan ia, dan kemudian saya akan bercakap mengenainya untuk kali kedua.

615
00:50:28,880 --> 00:50:35,200
[Pelajar] saya perlukan untuk mempunyai semua fungsi prototaip dan segala-galanya, walaupun, betul-betul?

616
00:50:37,640 --> 00:50:40,840
Fungsi prototaip. Oh, kamu maksudkan seperti - Ya.

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

618
00:50:43,040 --> 00:50:47,390
>> Jadi dalam usaha untuk menyelesaikan untuk memanggil mergeSortHelp, mergeSortHelp mesti sama ada telah ditakrifkan

619
00:50:47,390 --> 00:50:56,370
sebelum apapun atau kita hanya perlu prototaip. Hanya salin dan tampal bahawa.

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

621
00:50:59,490 --> 00:51:03,830
tetapi merge belum ditakrifkan lagi, jadi kita hanya boleh membenarkan mergeSortHelp tahu

622
00:51:03,830 --> 00:51:08,700
bahawa itulah yang bergabung akan kelihatan 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 mempunyai isu di sini di mana kita tidak mempunyai kes asas.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp rekursi, jadi apa-apa fungsi rekursi

626
00:51:38,110 --> 00:51:42,610
akan memerlukan beberapa jenis kes asas untuk tahu bila untuk berhenti rekursif yang menggelarkan diri.

627
00:51:42,610 --> 00:51:45,590
Apa kes asas kami akan di sini? Yeah.

628
00:51:45,590 --> 00:51:49,110
[Pelajar] Jika saiz adalah 1? >> [Bowden] Ya.

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

630
00:51:56,220 --> 00:52:01,850
sebaik sahaja kami mendapat ke dalam tatasusunan 1 saiz, yang tidak dapat dielakkan disusun sendiri.

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

632
00:52:09,530 --> 00:52:12,970
jadi kita hanya boleh kembali.

633
00:52:12,970 --> 00:52:16,880
>> Notis itu tidak sah, jadi kita tidak kembali apa-apa yang tertentu, kita hanya kembali.

634
00:52:16,880 --> 00:52:19,580
Okay. Jadi itulah kes asas kami.

635
00:52:19,580 --> 00:52:27,440
Saya rasa kes asas kami juga boleh jika kita berlaku penggabungan pelbagai 0 saiz,

636
00:52:27,440 --> 00:52:30,030
kita mungkin mahu untuk berhenti pada satu ketika,

637
00:52:30,030 --> 00:52:33,610
jadi kita hanya boleh mengatakan saiz kurang daripada 2 atau kurang daripada atau sama dengan 1

638
00:52:33,610 --> 00:52:37,150
supaya ini akan bekerja untuk pelbagai mana-mana sekarang.

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

640
00:52:38,870 --> 00:52:42,740
Jadi itulah kes asas kami.

641
00:52:42,740 --> 00:52:45,950
Sekarang adakah anda ingin untuk berjalan kita melalui merge?

642
00:52:45,950 --> 00:52:49,140
Apa yang semua kes ini bermakna?

643
00:52:49,140 --> 00:52:54,480
Di sini, kita hanya melakukan idea yang sama, -

644
00:52:56,970 --> 00:53:02,470
[Pelajar] saya perlu lulus saiz dengan semua mergeSortHelp panggilan.

645
00:53:02,470 --> 00:53:10,080
Saya tambah saiz sebagai primer tambahan dan ia bukan di sana, seperti / 2 saiz.

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

647
00:53:16,210 --> 00:53:21,320
[Bowden] Berikut? >> [Pelajar] Hanya saiz. >> [Bowden] Oh. Saiz, saiz? >> [Pelajar] Yeah.

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

649
00:53:23,010 --> 00:53:26,580
Biarkan saya berfikir untuk sesaat.

650
00:53:26,580 --> 00:53:28,780
Adakah kita menghadapi isu?

651
00:53:28,780 --> 00:53:33,690
Kami sentiasa merawat kiri sebagai 0. >> [Pelajar] No

652
00:53:33,690 --> 00:53:36,340
Itulah salah juga. Maaf. Ia harus bermula. Yeah.

653
00:53:36,340 --> 00:53:39,230
[Bowden] Okay. Saya suka yang lebih baik.

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

655
00:53:43,880 --> 00:53:47,200
Jadi sekarang adakah anda mahu untuk berjalan kita melalui merge? >> [Pelajar] Okay.

656
00:53:47,200 --> 00:53:52,150
Saya hanya berjalan melalui pelbagai baru ini bahawa saya telah mencipta.

657
00:53:52,150 --> 00:53:57,420
Saiznya adalah saiz bahagian array yang kita mahu diselesaikan

658
00:53:57,420 --> 00:54:03,460
dan cuba untuk mencari elemen yang saya perlu meletakkan dalam langkah array baru.

659
00:54:03,460 --> 00:54:10,140
Jadi untuk berbuat demikian, pertama saya memeriksa jika separuh kiri array terus mempunyai apa-apa lagi elemen,

660
00:54:10,140 --> 00:54:14,260
dan jika ia tidak, maka anda pergi ke keadaan yang lain, yang hanya berkata

661
00:54:14,260 --> 00:54:20,180
okay, ia mestilah dalam pelbagai yang betul, dan kita akan meletakkan bahawa dalam indeks semasa newArray.

662
00:54:20,180 --> 00:54:27,620
>> Dan kemudian sebaliknya, saya memeriksa jika sebelah kanan array juga selesai,

663
00:54:27,620 --> 00:54:30,630
di mana saya hanya meletakkan di sebelah kiri.

664
00:54:30,630 --> 00:54:34,180
Yang mungkin tidak benar-benar perlu. Saya tidak pasti.

665
00:54:34,180 --> 00:54:40,970
Tetapi bagaimanapun, dua cek yang kedua-dua adalah lebih kecil di kiri atau kanan.

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

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

668
00:54:52,040 --> 00:54:53,840
Yang kelihatan baik.

669
00:54:53,840 --> 00:54:58,800
Adakah sesiapa yang mempunyai komen atau kebimbangan atau soalan?

670
00:55:00,660 --> 00:55:07,720
Jadi empat kes yang kita perlu untuk membawa perkara-perkara ke dalam hanya - atau ia kelihatan seperti lima -

671
00:55:07,720 --> 00:55:13,100
tetapi kita perlu mempertimbangkan sama ada array kiri telah kehabisan perkara yang kita perlu untuk bergabung,

672
00:55:13,100 --> 00:55:16,390
sama ada array yang betul telah kehabisan perkara yang kita perlu untuk bergabung -

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

674
00:55:18,400 --> 00:55:21,730
Jadi sama ada array kiri telah kehabisan perkara atau array yang betul telah kehabisan perkara.

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

676
00:55:24,320 --> 00:55:30,920
Kita juga perlu kes remeh sama ada perkara kiri adalah kurang daripada perkara yang betul.

677
00:55:30,920 --> 00:55:33,910
Kemudian kita mahu untuk memilih perkara kiri.

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

679
00:55:37,630 --> 00:55:40,990
Jadi ini adalah betul, maka itulah.

680
00:55:40,990 --> 00:55:46,760
Array kiri. Ia adalah 1, 2, 3. Okay. Jadi yeah, mereka adalah empat perkara yang kita mungkin mahu lakukan.

681
00:55:50,350 --> 00:55:54,510
Dan kita tidak akan pergi lebih lelaran penyelesaian.

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

683
00:55:55,980 --> 00:56:03,070
Gabung apapun adalah satu contoh fungsi yang kedua-duanya tidak rekursi ekor,

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

685
00:56:07,040 --> 00:56:13,450
tetapi juga ia tidak sangat mudah untuk membuat ia lelaran.

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

687
00:56:16,910 --> 00:56:19,170
Ini pelaksanaan apapun merge,

688
00:56:19,170 --> 00:56:22,140
bergabung, tidak kira apa yang anda lakukan, anda akan membina merge.

689
00:56:22,140 --> 00:56:29,170
>> Jadi bergabung apapun yang dibina di atas merge rekursif hanya ketiga-tiga baris.

690
00:56:29,170 --> 00:56:34,700
Iterative, ia adalah lebih menjengkelkan dan lebih sukar untuk berfikir tentang.

691
00:56:34,700 --> 00:56:41,860
Tetapi notis bahawa ia bukan ekor rekursi sejak mergeSortHelp - apabila ia memerlukan dirinya -

692
00:56:41,860 --> 00:56:46,590
ia masih perlu melakukan perkara-perkara selepas ini pulangan panggilan rekursi.

693
00:56:46,590 --> 00:56:50,830
Jadi ini bingkai tindanan mesti terus wujud walaupun selepas memanggil ini.

694
00:56:50,830 --> 00:56:54,170
Dan kemudian apabila anda memanggil ini, bingkai tindanan mesti terus wujud

695
00:56:54,170 --> 00:56:57,780
kerana walaupun selepas panggilan itu, kita masih perlu untuk bergabung.

696
00:56:57,780 --> 00:57:01,920
Dan ia adalah nontrivial untuk membuat ekor ini rekursi.

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

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

699
00:57:09,860 --> 00:57:13,400
Jadi akan kembali untuk menyusun - oh, ada dua perkara yang saya ingin menunjukkan. Okay.

700
00:57:13,400 --> 00:57:17,840
Melangkah kembali kepada apapun, kami akan melakukan ini dengan cepat.

701
00:57:17,840 --> 00:57:21,030
Atau cari. Susun? Susun. Yeah.

702
00:57:21,030 --> 00:57:22,730
Melangkah kembali ke permulaan apapun.

703
00:57:22,730 --> 00:57:29,870
Kami mahu mewujudkan algoritma yang pelbagai array menggunakan algoritma mana-mana

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

705
00:57:33,660 --> 00:57:40,860
Jadi bagaimana ini boleh terjadi? Adakah sesiapa yang mempunyai apa-apa jenis -

706
00:57:40,860 --> 00:57:44,300
Saya membayangkan sebelum di -

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

708
00:57:48,300 --> 00:57:51,450
kita telah bertambah baik algoritma kami masa bijak,

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

710
00:57:55,250 --> 00:57:59,520
[Pelajar] Angkasa. >> Yeah. Kami akan menggunakan lebih banyak ruang.

711
00:57:59,520 --> 00:58:04,490
Dan tidak hanya lebih banyak ruang, ia adalah ruang yang lebih pesat.

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

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

714
00:58:18,980 --> 00:58:22,210
Tetapi ia adalah kerana kita perlu menggunakan ruang yang begitu banyak

715
00:58:22,210 --> 00:58:28,610
bahawa ini boleh dicapai tetapi tidak realistik.

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

717
00:58:31,220 --> 00:58:36,810
Kita boleh mencapai matlamat ini jika kita menjamin bahawa mana-mana elemen tertentu dalam array

718
00:58:36,810 --> 00:58:39,600
adalah di bawah saiz tertentu.

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

720
00:58:44,500 --> 00:58:48,130
mana-mana elemen dalam array adalah di bawah saiz 200.

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

722
00:58:51,080 --> 00:58:58,660
Anda dengan mudah boleh mempunyai pelbagai bahawa anda tahu segala-galanya di dalamnya

723
00:58:58,660 --> 00:59:00,570
akan menjadi kurang daripada bilangan tertentu.

724
00:59:00,570 --> 00:59:07,400
Seperti jika anda mempunyai beberapa benar-benar besar-besaran vektor atau sesuatu

725
00:59:07,400 --> 00:59:11,810
tetapi anda tahu segala-galanya akan menjadi antara 0 dan 5,

726
00:59:11,810 --> 00:59:14,790
maka ia akan menjadi ketara lebih cepat untuk melakukan ini.

727
00:59:14,790 --> 00:59:17,930
Dan terikat kepada mana-mana unsur-unsur ialah 5,

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

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

730
00:59:26,300 --> 00:59:32,960
Dalam teori sentiasa ada terikat sejak integer hanya boleh sehingga hingga 4 bilion,

731
00:59:32,960 --> 00:59:40,600
tetapi itu tidak realistik sejak maka kita akan menggunakan ruang

732
00:59:40,600 --> 00:59:44,400
atas perintah daripada 4 bilion. Jadi itulah yang tidak realistik.

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

734
00:59:47,060 --> 00:59:59,570
Helah untuk melakukannya di O n kita membuat satu lagi pelbagai dipanggil tuduhan saiz TERIKAT.

735
00:59:59,570 --> 01:00:10,470
Jadi sebenarnya, ini adalah jalan pintas untuk - Saya sebenarnya tidak tahu jika dilafaz melakukan ini.

736
01:00:11,150 --> 01:00:15,330
Tetapi di GCC sekurang-kurangnya - dilafaz: saya menganggap adakah ia terlalu -

737
01:00:15,330 --> 01:00:18,180
ini hanya akan memulakan array keseluruhan untuk menjadi 0.

738
01:00:18,180 --> 01:00:25,320
Jadi jika saya tidak mahu berbuat demikian, maka saya secara berasingan boleh lakukan untuk (int i = 0;

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

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

741
01:00:35,260 --> 01:00:39,570
Saya melelar lebih array saya,

742
01:00:39,570 --> 01:00:51,920
dan apa yang saya lakukan ialah saya mengira bilangan setiap - Mari kita pergi ke sini.

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

744
01:00:55,480 --> 01:01:00,010
Apa yang saya mengira bilangan kejadian setiap unsur-unsur.

745
01:01:00,010 --> 01:01:03,470
Mari kita sebenarnya menambah pasangan lebih di sini dengan beberapa mengulangi.

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

747
01:01:11,070 --> 01:01:14,850
Jadi Val boleh menjadi 4 atau 8 atau apa sahaja.

748
01:01:14,850 --> 01:01:18,870
Dan kini saya mengira berapa banyak nilai yang saya telah melihat,

749
01:01:18,870 --> 01:01:21,230
jadi tuduhan [Val] + +;

750
01:01:21,230 --> 01:01:29,430
Selepas ini dilakukan, tuduhan akan melihat sesuatu seperti 0001.

751
01:01:29,430 --> 01:01:42,190
Mari kita buat tuduhan [Val] - DIIKAT + 1.

752
01:01:42,190 --> 01:01:48,230
>> Sekarang ini hanya untuk mengambil kira hakikat bahawa kita sedang bermula dari 0.

753
01:01:48,230 --> 01:01:50,850
Jadi sekiranya 200 akan menjadi alat nombor satu yang paling kami terbesar,

754
01:01:50,850 --> 01:01:54,720
maka 0-200 adalah 201 perkara.

755
01:01:54,720 --> 01:02:01,540
Jadi tuduhan, ia akan kelihatan seperti 00001 kerana kita mempunyai satu 4.

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

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

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

759
01:02:17,630 --> 01:02:21,670
Jadi kita boleh gunakan kiraan.

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

761
01:02:44,920 --> 01:02:52,540
Dan jadi jika num_of_item ialah 2, yang bermakna kita mahu untuk memasukkan 2 nombor i

762
01:02:52,540 --> 01:02:55,290
ke dalam pelbagai disusun kami.

763
01:02:55,290 --> 01:03:02,000
Jadi kita perlu menjejaki sejauh mana kita ke dalam array.

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

765
01:03:05,470 --> 01:03:09,910
Array - Saya hanya akan menulis.

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

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

768
01:03:28,580 --> 01:03:32,490
Adalah bahawa apa yang saya mahu? Saya fikir itulah apa yang saya mahu.

769
01:03:35,100 --> 01:03:38,290
Ya, ini kelihatan baik. Okay.

770
01:03:38,290 --> 01:03:43,050
Jadi tidak semua orang faham apa tujuan pelbagai tuduhan saya?

771
01:03:43,050 --> 01:03:48,140
Ia mengira bilangan kejadian setiap nombor-nombor ini.

772
01:03:48,140 --> 01:03:51,780
Kemudian saya iterating atas yang pelbagai tuduhan,

773
01:03:51,780 --> 01:03:57,190
dan kedudukan engan dalam pelbagai tuduhan

774
01:03:57,190 --> 01:04:01,930
adalah bilangan i adalah yang sepatutnya muncul dalam pelbagai disusun saya.

775
01:04:01,930 --> 01:04:06,840
Itulah sebabnya tuduhan 4 akan menjadi 1

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

777
01:04:11,840 --> 01:04:16,900
Jadi itulah berapa ramai daripada mereka yang saya mahu untuk memasukkan ke dalam pelbagai disusun saya.

778
01:04:16,900 --> 01:04:19,200
Kemudian saya hanya berbuat demikian.

779
01:04:19,200 --> 01:04:28,960
Saya memasukkan num_of_item i ke dalam pelbagai disusun saya.

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

781
01:04:32,460 --> 01:04:43,100
Dan sebagainya lagi, ini adalah masa linear kerana kita hanya iterating lebih ini sekali,

782
01:04:43,100 --> 01:04:47,470
tetapi ia juga linear dalam apa nombor ini berlaku untuk menjadi,

783
01:04:47,470 --> 01:04:50,730
dan sebagainya ia banyak bergantung kepada apa yang terikat anda.

784
01:04:50,730 --> 01:04:53,290
Dengan terikat daripada 200, itu bukan yang buruk.

785
01:04:53,290 --> 01:04:58,330
Jika terikat anda pergi ke 10,000, maka itulah sedikit teruk,

786
01:04:58,330 --> 01:05:01,360
tetapi jika terikat anda akan menjadi 4 bilion, yang benar-benar tidak realistik

787
01:05:01,360 --> 01:05:07,720
dan pelbagai ini akan mempunyai untuk menjadi saiz 4 bilion, yang adalah tidak realistik.

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

789
01:05:10,860 --> 01:05:13,270
[Sambutan pelajar didengar] >> Okay.

790
01:05:13,270 --> 01:05:15,710
Saya sedar satu perkara lain apabila kita telah melalui.

791
01:05:17,980 --> 01:05:23,720
Saya rasa masalah ini adalah di Lucas dan mungkin setiap satu kita telah melihat.

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

793
01:05:26,330 --> 01:05:31,040
Satu-satunya perkara yang saya mahu mengulas mengenai adalah bahawa apabila anda berurusan dengan perkara-perkara seperti indeks,

794
01:05:31,040 --> 01:05:38,320
anda tidak pernah benar-benar melihat ini apabila anda menulis untuk gelung,

795
01:05:38,320 --> 01:05:41,120
tetapi dari segi teknikal, apabila anda sedang berurusan dengan indeks,

796
01:05:41,120 --> 01:05:45,950
anda cukup banyak perlu sentiasa berurusan dengan integer tak bertanda.

797
01:05:45,950 --> 01:05:53,850
Sebab untuk ini adalah apabila anda sedang berurusan dengan integer ditandatangani,

798
01:05:53,850 --> 01:05:56,090
jadi jika anda mempunyai 2 integer ditandatangani dan anda menambah mereka bersama-sama

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

800
01:06:00,640 --> 01:06:03,410
Jadi itulah apa limpahan integer.

801
01:06:03,410 --> 01:06:10,500
>> Jika saya menambah 2 bilion dan 1 bilion, saya berakhir dengan negatif 1 bilion.

802
01:06:10,500 --> 01:06:15,480
Itulah bagaimana integer 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 denda kecuali jika rendah berlaku untuk menjadi 2 bilion dan sehingga berlaku untuk menjadi 1 bilion,

805
01:06:23,500 --> 01:06:27,120
maka ini akan menjadi negatif 1000000000 dan kemudian kita akan membahagikan bahawa 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 adalah hanya satu isu jika anda berlaku untuk mencari melalui pelbagai

808
01:06:33,760 --> 01:06:38,070
berbilion-bilion perkara.

809
01:06:38,070 --> 01:06:44,050
Tetapi jika + rendah sehingga berlaku melimpah, maka itulah masalah.

810
01:06:44,050 --> 01:06:47,750
Sebaik sahaja kita membuat mereka tidak bertanda, maka 2 bilion ditambah 1 bilion adalah 3 bilion.

811
01:06:47,750 --> 01:06:51,960
3000000000 dibahagikan dengan 2 adalah 1.5 bilion.

812
01:06:51,960 --> 01:06:55,670
Demikian secepat mereka tidak bertanda, segala-galanya adalah sempurna.

813
01:06:55,670 --> 01:06:59,900
Dan supaya juga satu isu apabila anda menulis anda untuk gelung,

814
01:06:59,900 --> 01:07:03,940
dan sebenarnya, ia mungkin tidak secara automatik.

815
01:07:09,130 --> 01:07:12,330
Ia sebenarnya hanya akan menjerit pada anda.

816
01:07:12,330 --> 01:07:21,610
Jadi, jika nombor ini adalah terlalu besar untuk menjadi hanya dalam integer tetapi ia akan dimuatkan dalam integer bertanda,

817
01:07:21,610 --> 01:07:24,970
ia akan menjerit pada anda, jadi itulah sebabnya anda tidak pernah benar-benar menghadapi isu.

818
01:07:29,150 --> 01:07:34,820
Anda boleh melihat bahawa indeks tidak akan menjadi negatif,

819
01:07:34,820 --> 01:07:39,220
dan sebagainya apabila anda iterating lebih array,

820
01:07:39,220 --> 01:07:43,970
anda hampir sentiasa boleh mengatakan tidak bertanda int i, tetapi anda tidak benar-benar perlu.

821
01:07:43,970 --> 01:07:47,110
Perkara yang akan bekerja cukup banyak seperti juga.

822
01:07:48,740 --> 01:07:50,090
Okay. [Bisikan] Apa masa ia?

823
01:07:50,090 --> 01:07:54,020
Perkara terakhir saya mahu menunjukkan - dan saya hanya akan melakukan ia benar-benar cepat.

824
01:07:54,020 --> 01:08:03,190
Anda tahu bagaimana kita telah # menentukan supaya kita # boleh menentukan MAX sebagai 5 atau sesuatu?

825
01:08:03,190 --> 01:08:05,940
Mari kita tidak melakukan MAX. # Define TERIKAT sebagai 200. Itulah apa yang kami lakukan sebelum ini.

826
01:08:05,940 --> 01:08:10,380
Itu mentakrifkan pemalar, yang hanya akan disalin dan ditampal

827
01:08:10,380 --> 01:08:13,010
di mana sahaja kita berlaku untuk menulis TERIKAT.

828
01:08:13,010 --> 01:08:18,189
>> Jadi, kita sebenarnya boleh melakukan lebih # mentakrifkan.

829
01:08:18,189 --> 01:08:21,170
Kita # boleh menentukan fungsi.

830
01:08:21,170 --> 01:08:23,410
Mereka tidak benar-benar fungsi, tetapi kita akan memanggil mereka fungsi.

831
01:08:23,410 --> 01:08:36,000
Satu contoh akan menjadi sesuatu yang seperti MAX (x, y) ditakrifkan sebagai (x <y y: x). Okay.

832
01:08:36,000 --> 01:08:40,660
Jadi anda perlu mendapatkan digunakan untuk sintaks pengendali pertigaan,

833
01:08:40,660 --> 01:08:49,029
tetapi x kurang daripada y? Kembali y, lain kembali x.

834
01:08:49,029 --> 01:08:54,390
Jadi anda boleh melihat anda boleh membuat fungsi ini berasingan,

835
01:08:54,390 --> 01:09:01,399
dan fungsi boleh menjadi seperti bool MAX mengambil masa 2 hujah, kembali ini.

836
01:09:01,399 --> 01:09:08,340
Ini adalah salah satu yang paling biasa saya lihat dilakukan seperti ini. Kami memanggil mereka makro.

837
01:09:08,340 --> 01:09:11,790
Ini adalah makro.

838
01:09:11,790 --> 01:09:15,859
Ini adalah hanya sintaks untuk ia.

839
01:09:15,859 --> 01:09:18,740
Anda boleh menulis makro untuk melakukan apa sahaja yang anda mahu.

840
01:09:18,740 --> 01:09:22,649
Anda sering melihat makro untuk debugging printfs dan barangan.

841
01:09:22,649 --> 01:09:29,410
Jadi jenis printf, terdapat pemalar khas dalam C seperti menekankan LINE menekankan,

842
01:09:29,410 --> 01:09:31,710
2 underscore LINE menekankan,

843
01:09:31,710 --> 01:09:37,550
dan terdapat juga saya fikir 2 underscore func. Yang mungkin. Sesuatu seperti itu.

844
01:09:37,550 --> 01:09:40,880
Mereka perkara yang akan digantikan dengan nama fungsi

845
01:09:40,880 --> 01:09:42,930
atau bilangan baris yang anda berada di.

846
01:09:42,930 --> 01:09:48,630
Kerap, anda menulis debugging printfs yang turun di sini saya boleh kemudian hanya menulis

847
01:09:48,630 --> 01:09:54,260
Debug dan ia akan mencetak nombor barisan dan fungsi bahawa saya berada di

848
01:09:54,260 --> 01:09:57,020
bahawa ia temui bahawa kenyataan DEBUG.

849
01:09:57,020 --> 01:09:59,550
Dan anda juga boleh mencetak perkara-perkara lain.

850
01:09:59,550 --> 01:10:05,990
Jadi satu perkara yang anda harus berhati-hati jika saya berlaku untuk menentukan # 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 apa jua sebab, anda berlaku untuk berbuat demikian banyak.

853
01:10:14,310 --> 01:10:16,650
Jadi ia membuat makro.

854
01:10:16,650 --> 01:10:18,680
Ini sebenarnya dipecahkan.

855
01:10:18,680 --> 01:10:23,050
Saya akan memanggilnya 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
[Pelajar] 12.

858
01:10:30,580 --> 01:10:34,800
Ya, 12 perlu dipulangkan, dan 12 dikembalikan.

859
01:10:34,800 --> 01:10:43,350
3 akan diganti bagi x, 6 mendapat digantikan untuk y, dan kita kembali 2 * 6, iaitu 12.

860
01:10:43,350 --> 01:10:47,710
Sekarang apa tentang perkara ini? Apa yang perlu dikembalikan?

861
01:10:47,710 --> 01:10:50,330
[Pelajar] 14. >> Sebaik-baiknya, 14.

862
01:10:50,330 --> 01:10:55,290
Isunya ialah bahawa bagaimana hash mentakrifkan kerja, ingat ia adalah satu salinan literal dan tampal

863
01:10:55,290 --> 01:11:00,160
segala-galanya cukup banyak, jadi apa ini akan ditafsirkan sebagai

864
01:11:00,160 --> 01:11:11,270
adalah 3 kurang daripada 1 campur 6, 2 kali 1 campur 6, 2 kali 3.

865
01:11:11,270 --> 01:11:19,780
>> Jadi untuk sebab ini, anda hampir sentiasa membalut segala-galanya dalam kurungan.

866
01:11:22,180 --> 01:11:25,050
Mana-mana pembolehubah anda hampir sentiasa membalut di dalam kurungan.

867
01:11:25,050 --> 01:11:29,570
Terdapat kes-kes di mana anda tidak perlu, seperti yang saya tahu bahawa saya tidak perlu untuk berbuat demikian di sini

868
01:11:29,570 --> 01:11:32,110
kerana kurang daripada cukup banyak sentiasa hanya pergi ke tempat kerja,

869
01:11:32,110 --> 01:11:34,330
walaupun yang mungkin tidak menjadi kenyataan.

870
01:11:34,330 --> 01:11:41,870
Jika ada sesuatu yang tidak masuk akal seperti DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
kemudian yang akan digantikan dengan 3 kurang daripada 1 bersamaan bersamaan 2,

872
01:11:49,760 --> 01:11:53,460
dan sebagainya maka ia akan melakukan 3 kurang daripada 1, adakah sama bahawa 2,

873
01:11:53,460 --> 01:11:55,620
yang bukan apa yang kita mahu.

874
01:11:55,620 --> 01:12:00,730
Jadi, untuk mengelakkan sebarang masalah pengendali keutamaan,

875
01:12:00,730 --> 01:12:02,870
sentiasa membalut di dalam kurungan.

876
01:12:03,290 --> 01:12:07,700
Okay. Dan itu, 5:30.

877
01:12:08,140 --> 01:12:12,470
Jika anda mempunyai sebarang soalan pada pset, marilah kita tahu.

878
01:12:12,470 --> 01:12:18,010
Ia seharusnya menyeronokkan, dan edisi penggodam juga adalah lebih realistik

879
01:12:18,010 --> 01:12:22,980
daripada edisi penggodam tahun lepas, jadi kami berharap bahawa banyak anda cuba.

880
01:12:22,980 --> 01:12:26,460
Tahun lepas adalah sangat menggalakkan.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]