1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminar: Temubual Teknikal]

2
00:00:02,640 --> 00:00:04,630
[Kenny Yu, Universiti Harvard]

3
00:00:04,630 --> 00:00:08,910
[Ini adalah CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Hi semua, Saya Kenny. Saya kini komputer junior belajar sains.

5
00:00:12,420 --> 00:00:17,310
Saya seorang bekas CS TF, dan saya berharap saya mempunyai ini apabila saya adalah seorang underclassman,

6
00:00:17,310 --> 00:00:19,380
dan itulah sebabnya saya memberi seminar ini.

7
00:00:19,380 --> 00:00:21,370
Jadi saya berharap anda menikmati ia.

8
00:00:21,370 --> 00:00:23,470
Seminar ini adalah mengenai wawancara teknikal,

9
00:00:23,470 --> 00:00:26,650
dan semua sumber saya boleh didapati di pautan ini,

10
00:00:26,650 --> 00:00:32,350
pautan ini di sini, beberapa sumber.

11
00:00:32,350 --> 00:00:36,550
Jadi saya membuat senarai masalah, sebenarnya, agak beberapa masalah.

12
00:00:36,550 --> 00:00:40,800
Juga sumber halaman umum di mana kita boleh mencari tips

13
00:00:40,800 --> 00:00:42,870
mengenai cara untuk menyediakan untuk temuduga,

14
00:00:42,870 --> 00:00:46,470
tips mengenai apa yang perlu anda lakukan semasa temu bual sebenar,

15
00:00:46,470 --> 00:00:51,910
serta bagaimana untuk mendekati masalah dan sumber untuk rujukan masa depan.

16
00:00:51,910 --> 00:00:53,980
Ia adalah semua talian.

17
00:00:53,980 --> 00:00:58,290
Dan hanya kepada kata pengantar seminar ini, penafian,

18
00:00:58,290 --> 00:01:00,690
seperti ini tidak sepatutnya - penyediaan temuduga anda

19
00:01:00,690 --> 00:01:02,800
tidak harus terhad kepada senarai ini.

20
00:01:02,800 --> 00:01:04,750
Ini hanya bertujuan untuk menjadi panduan,

21
00:01:04,750 --> 00:01:08,890
dan anda pasti harus mengambil segala-galanya yang saya katakan dengan sebutir garam,

22
00:01:08,890 --> 00:01:14,620
tetapi juga menggunakan segala-galanya yang saya digunakan untuk membantu anda dalam persediaan temuduga anda.

23
00:01:14,620 --> 00:01:16,400
>> Saya akan mempercepatkan melalui beberapa slaid seterusnya

24
00:01:16,400 --> 00:01:18,650
supaya kita boleh sampai ke kajian kes sebenar.

25
00:01:18,650 --> 00:01:23,630
Struktur temu bual untuk postion kejuruteraan perisian,

26
00:01:23,630 --> 00:01:26,320
biasanya ia adalah 30 hingga 45 minit,

27
00:01:26,320 --> 00:01:29,810
pusingan berganda, bergantung kepada syarikat itu.

28
00:01:29,810 --> 00:01:33,090
Selalunya anda akan kod di atas papan putih.

29
00:01:33,090 --> 00:01:35,960
Jadi lembaga putih seperti ini, tetapi selalunya pada skala yang lebih kecil.

30
00:01:35,960 --> 00:01:38,540
Jika anda mempunyai temu bual telefon, anda mungkin akan menggunakan

31
00:01:38,540 --> 00:01:44,030
sama ada collabedit atau Google Doc supaya mereka boleh melihat anda hidup pengekodan

32
00:01:44,030 --> 00:01:46,500
semasa anda sedang ditemuramah melalui telefon.

33
00:01:46,500 --> 00:01:48,490
Temu bual itu sendiri adalah biasanya 2 atau 3 masalah

34
00:01:48,490 --> 00:01:50,620
menguji pengetahuan sains komputer anda.

35
00:01:50,620 --> 00:01:54,490
Dan ia hampir pasti akan melibatkan pengekodan.

36
00:01:54,490 --> 00:01:59,540
Jenis-jenis soalan yang anda akan melihat biasanya struktur data dan algoritma.

37
00:01:59,540 --> 00:02:02,210
Dan dalam melakukan ini jenis masalah,

38
00:02:02,210 --> 00:02:07,830
mereka akan meminta anda, seperti, apakah masa dan kerumitan ruang, O besar?

39
00:02:07,830 --> 00:02:09,800
Selalunya mereka juga bertanya soalan tahap tinggi,

40
00:02:09,800 --> 00:02:12,530
begitu, mereka bentuk sistem,

41
00:02:12,530 --> 00:02:14,770
bagaimana anda akan meletakkan kod anda?

42
00:02:14,770 --> 00:02:18,370
Apakah antara muka, apa kelas, apa modul adakah anda mempunyai dalam sistem anda,

43
00:02:18,370 --> 00:02:20,900
dan bagaimana ini berinteraksi bersama-sama?

44
00:02:20,900 --> 00:02:26,130
Jadi struktur data dan algoritma serta merekabentuk sistem.

45
00:02:26,130 --> 00:02:29,180
>> Beberapa tip umum sebelum kita menyelam ke dalam kajian kes kami.

46
00:02:29,180 --> 00:02:32,300
Saya fikir peraturan yang paling penting sentiasa berfikir dengan kuat.

47
00:02:32,300 --> 00:02:36,980
Temuduga sepatutnya menjadi peluang anda untuk menunjuk-nunjuk proses pemikiran anda.

48
00:02:36,980 --> 00:02:39,820
Titik temuduga adalah untuk penemuduga untuk mengukur

49
00:02:39,820 --> 00:02:42,660
bagaimana anda berfikir dan bagaimana anda pergi melalui masalah.

50
00:02:42,660 --> 00:02:45,210
Perkara yang paling teruk anda boleh lakukan ialah menjadi senyap seluruh temuduga.

51
00:02:45,210 --> 00:02:50,090
Itu hanya tidak baik.

52
00:02:50,090 --> 00:02:53,230
Apabila anda diberi soalan, anda juga mahu pastikan anda memahami soalan.

53
00:02:53,230 --> 00:02:55,350
Jadi mengulangi soalan kembali dalam perkataan anda sendiri

54
00:02:55,350 --> 00:02:58,920
dan cuba untuk bekerja teliti kes-kes ujian beberapa mudah

55
00:02:58,920 --> 00:03:01,530
pastikan anda memahami soalan.

56
00:03:01,530 --> 00:03:05,510
Bekerja melalui beberapa kes-kes ujian juga akan memberi anda intuisi bagaimana untuk menyelesaikan masalah ini.

57
00:03:05,510 --> 00:03:11,210
Anda juga mungkin menemui beberapa corak untuk membantu anda menyelesaikan masalah.

58
00:03:11,210 --> 00:03:14,500
Hujung besar mereka adalah untuk tidak berasa kecewa.

59
00:03:14,500 --> 00:03:17,060
Jangan berasa kecewa.

60
00:03:17,060 --> 00:03:19,060
Temubual adalah mencabar, tetapi perkara yang paling buruk yang boleh anda lakukan,

61
00:03:19,060 --> 00:03:23,330
di samping untuk menjadi senyap, akan kelihatan kecewa.

62
00:03:23,330 --> 00:03:27,410
Anda tidak mahu untuk memberi gambaran bahawa penemuduga.

63
00:03:27,410 --> 00:03:33,960
Satu perkara yang anda - jadi, ramai orang, apabila mereka pergi ke dalam satu temu bual,

64
00:03:33,960 --> 00:03:37,150
mereka cuba untuk cuba mencari penyelesaian terbaik pertama,

65
00:03:37,150 --> 00:03:39,950
apabila benar-benar, terdapat biasanya penyelesaian dgn berkilau jelas.

66
00:03:39,950 --> 00:03:43,500
Ia mungkin menjadi perlahan, ia mungkin tidak cekap, tetapi anda hanya perlu menyatakan,

67
00:03:43,500 --> 00:03:46,210
hanya supaya anda mempunyai titik permulaan dari mana untuk bekerja lebih baik.

68
00:03:46,210 --> 00:03:48,270
Juga, menunjukkan penyelesaian adalah perlahan, dari segi

69
00:03:48,270 --> 00:03:52,160
O besar masa kerumitan atau kerumitan ruang,

70
00:03:52,160 --> 00:03:54,450
akan menunjukkan kepada penemuduga bahawa anda memahami

71
00:03:54,450 --> 00:03:57,510
isu-isu ini apabila menulis kod.

72
00:03:57,510 --> 00:04:01,440
Jadi jangan takut untuk tampil dengan algoritma mudah pertama

73
00:04:01,440 --> 00:04:04,950
dan kemudian bekerja lebih baik dari sana.

74
00:04:04,950 --> 00:04:09,810
Sebarang soalan setakat ini? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Jadi mari menyelam ke dalam masalah pertama kami.

76
00:04:11,650 --> 00:04:14,790
"Memandangkan pelbagai integer n, menulis fungsi yang shuffles array

77
00:04:14,790 --> 00:04:20,209
di tempat seperti yang semua pilih atur n integer adalah sama mungkin. "

78
00:04:20,209 --> 00:04:23,470
Dan andaikan anda mempunyai penjana integer rawak

79
00:04:23,470 --> 00:04:30,980
yang menjana integer dalam julat dari 0 ke i, separuh julat.

80
00:04:30,980 --> 00:04:32,970
Adakah semua orang memahami soalan ini?

81
00:04:32,970 --> 00:04:39,660
Saya memberi anda pelbagai integer n, dan saya mahu anda shuffle ia.

82
00:04:39,660 --> 00:04:46,050
Dalam direktori saya, saya menulis beberapa program untuk menunjukkan apa yang saya maksudkan.

83
00:04:46,050 --> 00:04:48,910
Saya akan shuffle pelbagai 20 elemen,

84
00:04:48,910 --> 00:04:52,490
dari -10 ke 9,

85
00:04:52,490 --> 00:04:57,050
dan saya mahu anda untuk menayangkan senarai seperti ini.

86
00:04:57,050 --> 00:05:02,890
Jadi ini adalah input pelbagai saya disusun, dan saya mahu anda shuffle ia.

87
00:05:02,890 --> 00:05:07,070
Kami akan melakukannya sekali lagi.

88
00:05:07,070 --> 00:05:13,780
Adakah semua orang memahami soalan? Okay.

89
00:05:13,780 --> 00:05:16,730
Jadi ia terpulang kepada anda.

90
00:05:16,730 --> 00:05:21,220
Apa adalah beberapa idea? Anda boleh melakukannya sebagai n ^ 2, n log n, n?

91
00:05:21,220 --> 00:05:34,400
Terbuka kepada cadangan.

92
00:05:34,400 --> 00:05:37,730
Okay. Jadi, satu idea, yang dicadangkan oleh Emmy,

93
00:05:37,730 --> 00:05:45,300
adalah pertama mengira nombor rawak, integer rawak, dalam pelbagai 0-20.

94
00:05:45,300 --> 00:05:49,840
Jadi menganggap pelbagai kami mempunyai panjang 20.

95
00:05:49,840 --> 00:05:54,800
Dalam rajah 20 elemen,

96
00:05:54,800 --> 00:05:58,560
ini adalah pelbagai input kami.

97
00:05:58,560 --> 00:06:04,590
Dan kini, cadangan beliau ialah untuk mewujudkan pelbagai baru,

98
00:06:04,590 --> 00:06:08,440
jadi ini akan menjadi pelbagai output.

99
00:06:08,440 --> 00:06:12,880
Dan berdasarkan i kembali oleh rand -

100
00:06:12,880 --> 00:06:17,580
jadi jika i adalah, katakan, 17,

101
00:06:17,580 --> 00:06:25,640
menyalin elemen ke-17 ke kedudukan pertama.

102
00:06:25,640 --> 00:06:30,300
Sekarang kita perlu memadam - kita perlu beralih semua unsur-unsur di sini

103
00:06:30,300 --> 00:06:36,920
supaya kita mempunyai jurang di hujung dan tiada lubang di tengah-tengah.

104
00:06:36,920 --> 00:06:39,860
Dan sekarang kita mengulangi proses tersebut.

105
00:06:39,860 --> 00:06:46,360
Sekarang kita memilih integer baru rawak antara 0 dan 19.

106
00:06:46,360 --> 00:06:52,510
Kami mempunyai i baru di sini, dan kami menyalin elemen ini ke dalam kedudukan ini.

107
00:06:52,510 --> 00:07:00,960
Kemudian kita beralih barangan lebih dan kita mengulangi proses tersebut sehingga kita mempunyai pelbagai penuh kami baru.

108
00:07:00,960 --> 00:07:05,890
Apakah masa tayangan algoritma ini?

109
00:07:05,890 --> 00:07:08,110
Nah, mari kita mempertimbangkan kesan ini.

110
00:07:08,110 --> 00:07:10,380
Kami beralih setiap elemen.

111
00:07:10,380 --> 00:07:16,800
Apabila kita keluarkan ini i, kita beralih semua unsur-unsur selepas ia ke kiri.

112
00:07:16,800 --> 00:07:21,600
Dan itu adalah kos O (n)

113
00:07:21,600 --> 00:07:26,100
kerana apa jika kita membuang elemen pertama?

114
00:07:26,100 --> 00:07:29,670
Jadi, untuk setiap penghapusan, kita mengeluarkan -

115
00:07:29,670 --> 00:07:32,170
penyingkiran setiap menanggung operasi O (n),

116
00:07:32,170 --> 00:07:41,520
dan kerana kita telah n penarikan balik, ini membawa kepada shuffle O (n ^ 2).

117
00:07:41,520 --> 00:07:49,550
Okay. Jadi permulaan yang baik. Permulaan yang baik.

118
00:07:49,550 --> 00:07:55,290
>> Satu lagi cadangan adalah untuk menggunakan sesuatu yang dikenali sebagai shuffle Knuth,

119
00:07:55,290 --> 00:07:57,540
atau shuffle Fisher-Yates.

120
00:07:57,540 --> 00:07:59,630
Dan ia sebenarnya shuffle masa linear.

121
00:07:59,630 --> 00:08:02,200
Dan idea adalah sangat serupa.

122
00:08:02,200 --> 00:08:05,160
Sekali lagi, kita mempunyai pelbagai input kami,

123
00:08:05,160 --> 00:08:08,580
tetapi sebaliknya menggunakan dua tatasusunan untuk input / output kita,

124
00:08:08,580 --> 00:08:13,590
kita menggunakan bahagian pertama array menjejaki bahagian dikocok kami,

125
00:08:13,590 --> 00:08:18,400
dan kita menjejaki, dan kemudian kami meninggalkan seluruh array kami untuk bahagian unshuffled.

126
00:08:18,400 --> 00:08:24,330
Jadi di sini adalah apa yang saya maksudkan. Kita mulakan dengan - kita memilih i,

127
00:08:24,330 --> 00:08:30,910
pelbagai 0-20.

128
00:08:30,910 --> 00:08:36,150
Penunjuk semasa kami menunjuk kepada indeks pertama.

129
00:08:36,150 --> 00:08:39,590
Kami memilih beberapa di sini saya

130
00:08:39,590 --> 00:08:42,740
dan sekarang kita swap.

131
00:08:42,740 --> 00:08:47,690
Jadi, jika ini adalah 5 dan ini adalah 4,

132
00:08:47,690 --> 00:08:57,150
array yang terhasil akan mempunyai 5 di sini dan 4 di sini.

133
00:08:57,150 --> 00:09:00,390
Dan sekarang kita perhatikan penanda di sini.

134
00:09:00,390 --> 00:09:05,770
Semua ke kiri dikocok,

135
00:09:05,770 --> 00:09:15,160
dan segala-galanya ke kanan unshuffled.

136
00:09:15,160 --> 00:09:17,260
Dan kini kita boleh mengulangi proses tersebut.

137
00:09:17,260 --> 00:09:25,210
Kami memilih indeks rawak antara 1 dan 20 sekarang.

138
00:09:25,210 --> 00:09:30,650
Jadi andaikan baru i di sini.

139
00:09:30,650 --> 00:09:39,370
Sekarang kita menukar i ini dengan kedudukan semasa baru kami di sini.

140
00:09:39,370 --> 00:09:44,790
Jadi kita bertukar-tukar belakang dan sebagainya seperti ini.

141
00:09:44,790 --> 00:09:51,630
Izinkan saya membawa sehingga kod untuk membuat ia lebih konkrit.

142
00:09:51,630 --> 00:09:55,290
Kita mulakan dengan pilihan kami i -

143
00:09:55,290 --> 00:09:58,370
kita mulakan dengan i sama kepada 0, kita memilih j lokasi rawak

144
00:09:58,370 --> 00:10:02,420
di bahagian unshuffled array, i n-1.

145
00:10:02,420 --> 00:10:07,280
Jadi, jika saya di sini, memilih indeks rawak antara di sini dan seluruh array,

146
00:10:07,280 --> 00:10:12,410
dan kita swap.

147
00:10:12,410 --> 00:10:17,550
Ini adalah semua kod yang diperlukan ke shuffle pelbagai anda.

148
00:10:17,550 --> 00:10:21,670
Apa-apa soalan?

149
00:10:21,670 --> 00:10:25,530
>> Nah, salah satu yang diperlukan soalan ini, mengapa ini betul?

150
00:10:25,530 --> 00:10:28,360
Mengapa setiap pilihatur sama mungkin?

151
00:10:28,360 --> 00:10:30,410
Dan aku tidak akan pergi melalui bukti ini,

152
00:10:30,410 --> 00:10:35,970
tetapi banyak masalah dalam bidang sains komputer boleh dibuktikan melalui induksi.

153
00:10:35,970 --> 00:10:38,520
Berapa ramai daripada anda biasa dengan induksi?

154
00:10:38,520 --> 00:10:40,590
Okay. Sejuk.

155
00:10:40,590 --> 00:10:43,610
Jadi, anda boleh membuktikan kesahihan algoritma ini secara aruhan mudah,

156
00:10:43,610 --> 00:10:49,540
mana hipotesis induksi anda akan, menganggap bahawa

157
00:10:49,540 --> 00:10:53,290
shuffle saya mengembalikan setiap pilihatur sama berkemungkinan

158
00:10:53,290 --> 00:10:56,120
sehingga unsur-unsur i pertama.

159
00:10:56,120 --> 00:10:58,300
Sekarang, pertimbangkan i + 1.

160
00:10:58,300 --> 00:11:02,550
Dan dengan cara itu kita memilih j indeks kami untuk menukar,

161
00:11:02,550 --> 00:11:05,230
ini membawa kepada - dan kemudian anda bekerja keluar butiran,

162
00:11:05,230 --> 00:11:07,390
sekurang-kurangnya satu bukti penuh mengapa algoritma ini kembali

163
00:11:07,390 --> 00:11:12,800
setiap pilihatur dengan kebarangkalian yang sama mungkin.

164
00:11:12,800 --> 00:11:15,940
>> Baiklah, masalah seterusnya.

165
00:11:15,940 --> 00:11:19,170
Jadi "diberi pelbagai integer, postive, sifar, negatif,

166
00:11:19,170 --> 00:11:21,290
menulis fungsi yang mengira jumlah maksimum

167
00:11:21,290 --> 00:11:24,720
daripada subarray sebarang continueous pelbagai input. "

168
00:11:24,720 --> 00:11:28,370
Satu contoh di sini adalah, dalam kes di mana semua nombor adalah positif,

169
00:11:28,370 --> 00:11:31,320
maka kini pilihan terbaik adalah untuk mengambil pelbagai keseluruhan.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, bersamaan 10.

171
00:11:34,690 --> 00:11:36,780
Apabila anda mempunyai beberapa negatif di sana,

172
00:11:36,780 --> 00:11:38,690
dalam kes ini, kita hanya mahu dua yang pertama

173
00:11:38,690 --> 00:11:44,590
kerana memilih -1 dan / atau -3 akan membawa jumlah kita ke bawah.

174
00:11:44,590 --> 00:11:48,120
Kadang-kadang kita mungkin mempunyai bermula pada pertengahan array.

175
00:11:48,120 --> 00:11:53,500
Kadang-kadang kita mahu untuk memilih apa-apa pada semua, ia adalah yang terbaik untuk tidak mengambil apa-apa.

176
00:11:53,500 --> 00:11:56,490
Dan kadang-kadang ia adalah lebih baik untuk mengambil kejatuhan,

177
00:11:56,490 --> 00:12:07,510
kerana perkara selepas ia adalah super besar. Jadi apa-apa idea?

178
00:12:07,510 --> 00:12:10,970
(Pelajar, difahami) >> Yeah.

179
00:12:10,970 --> 00:12:13,560
Katakan saya tidak mengambil -1.

180
00:12:13,560 --> 00:12:16,170
Kemudian sama ada saya memilih 1,000 dan 20,000,

181
00:12:16,170 --> 00:12:18,630
atau saya hanya memilih 3 bilion.

182
00:12:18,630 --> 00:12:20,760
Nah, pilihan terbaik adalah untuk mengambil semua nombor.

183
00:12:20,760 --> 00:12:24,350
Ini -1, walaupun negatif,

184
00:12:24,350 --> 00:12:31,340
jumlah keseluruhan adalah lebih baik daripada saya tidak mengambil -1.

185
00:12:31,340 --> 00:12:36,460
Jadi salah satu tip yang saya sebutkan tadi adalah untuk menyatakan yang jelas jelas

186
00:12:36,460 --> 00:12:40,540
dan daya penyelesaian kasar terlebih dahulu.

187
00:12:40,540 --> 00:12:44,340
Apakah penyelesaian kekerasan dalam masalah ini? Yeah?

188
00:12:44,340 --> 00:12:46,890
[Jane] Nah, saya fikir penyelesaian kekerasan

189
00:12:46,890 --> 00:12:52,600
akan menambah sehingga semua kemungkinan kombinasi (difahami).

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Jadi idea Jane adalah untuk mengambil setiap mungkin -

191
00:12:58,250 --> 00:13:01,470
Saya parafrasa - adalah untuk mengambil setiap subarray berterusan mungkin,

192
00:13:01,470 --> 00:13:07,840
mengira jumlah, dan kemudian mengambil maksimum semua subarrays mungkin berterusan.

193
00:13:07,840 --> 00:13:13,310
Apa yang unik mengenal pasti subarray dalam pelbagai input saya?

194
00:13:13,310 --> 00:13:17,380
Seperti, apa dua perkara yang saya perlukan? Yeah?

195
00:13:17,380 --> 00:13:19,970
(Pelajar, difahami) Hak. >>

196
00:13:19,970 --> 00:13:22,130
A lebih rendah terikat pada indeks dan indeks terikat atas

197
00:13:22,130 --> 00:13:28,300
unik menentukan subarray berterusan.

198
00:13:28,300 --> 00:13:31,400
[Pelajar Perempuan] Adakah kita menganggarkan ia adalah pelbagai nombor yang unik?

199
00:13:31,400 --> 00:13:34,280
[Yu] No Jadi persoalannya beliau, kita menganggap pelbagai kami -

200
00:13:34,280 --> 00:13:39,000
adalah pelbagai kami semua nombor yang unik, dan jawapannya tidak.

201
00:13:39,000 --> 00:13:43,390
>> Jika kita menggunakan penyelesaian kekerasan kami, maka indeks permulaan / akhir

202
00:13:43,390 --> 00:13:47,200
unik menentukan subarray berterusan kami.

203
00:13:47,200 --> 00:13:51,680
Jadi, jika kita melelar untuk semua catatan permulaan yang mungkin,

204
00:13:51,680 --> 00:13:58,320
dan untuk semua catatan akhir> atau = untuk memulakan, dan <n,

205
00:13:58,320 --> 00:14:05,570
anda mengira jumlah, dan kemudian kita mengambil jumlah maksimum yang telah kita lihat setakat.

206
00:14:05,570 --> 00:14:07,880
Adakah ini jelas?

207
00:14:07,880 --> 00:14:12,230
Apakah O besar daripada penyelesaian ini?

208
00:14:12,230 --> 00:14:16,660
TimeWise.

209
00:14:16,660 --> 00:14:18,860
Tidak cukup n ^ 2.

210
00:14:18,860 --> 00:14:25,250
Perhatikan bahawa kita melelar dari 0 hingga n,

211
00:14:25,250 --> 00:14:27,520
supaya satu untuk gelung.

212
00:14:27,520 --> 00:14:35,120
Kami melelar lagi dari hampir awal hingga akhir, satu lagi untuk gelung.

213
00:14:35,120 --> 00:14:37,640
Dan kini, dalam tempoh itu, kita perlu kepada jumlah kemasukan setiap,

214
00:14:37,640 --> 00:14:43,810
jadi itulah satu lagi untuk gelung. Jadi, kita mempunyai tiga bersarang gelung, n ^ 3.

215
00:14:43,810 --> 00:14:46,560
Okay. Ini berlaku sebagai titik permulaan.

216
00:14:46,560 --> 00:14:53,180
Penyelesaian kami adalah tidak lebih buruk daripada n ^ 3.

217
00:14:53,180 --> 00:14:55,480
Adakah semua orang memahami penyelesaian kekerasan?

218
00:14:55,480 --> 00:14:59,950
>> Okay. Satu penyelesaian yang lebih baik menggunakan idea yang dipanggil pengaturcaraan dinamik.

219
00:14:59,950 --> 00:15:03,040
Jika anda mengambil CS124, yang merupakan Algoritma dan Struktur Data,

220
00:15:03,040 --> 00:15:05,680
anda akan menjadi sangat biasa dengan teknik ini.

221
00:15:05,680 --> 00:15:12,190
Dan idea, cuba untuk membina penyelesaian kepada masalah yang lebih kecil pertama.

222
00:15:12,190 --> 00:15:17,990
Apa yang saya maksudkan dengan ini ialah, kita kini perlu bimbang tentang dua perkara: mula dan akhir.

223
00:15:17,990 --> 00:15:29,340
Dan itulah menjengkelkan. Bagaimana jika kita boleh menghilangkan salah mereka parameter?

224
00:15:29,340 --> 00:15:32,650
Satu idea adalah untuk - Sign In Register New diberikan masalah asal kita,

225
00:15:32,650 --> 00:15:37,470
mencari jumlah maksimum subarray mana-mana dalam pelbagai [O, n-1].

226
00:15:37,470 --> 00:15:47,400
Dan sekarang kita mempunyai subproblem baru, di mana kita tahu, dalam indeks semasa kami i,

227
00:15:47,400 --> 00:15:52,520
kita tahu kita mesti menyimpulkan di sana. Subarray kita mesti berakhir pada indeks semasa.

228
00:15:52,520 --> 00:15:57,640
Jadi baki masalah, di mana kita harus memulakan subarray kami?

229
00:15:57,640 --> 00:16:05,160
Adakah ini masuk akal? Okay.

230
00:16:05,160 --> 00:16:12,030
Jadi saya telah dikodkan sehingga ini, dan mari kita melihat apa yang bermakna ini.

231
00:16:12,030 --> 00:16:16,230
Dalam codirectory, terdapat program yang dipanggil subarray,

232
00:16:16,230 --> 00:16:19,470
dan ia mengambil beberapa barangan,

233
00:16:19,470 --> 00:16:25,550
dan ia kembali jumlah maksimum subarray dalam senarai dikocok saya.

234
00:16:25,550 --> 00:16:29,920
Jadi dalam kes ini, subarray maksimum kami adalah 3.

235
00:16:29,920 --> 00:16:34,850
Dan itu diambil dengan hanya menggunakan 2 dan 1.

236
00:16:34,850 --> 00:16:38,050
Mari kita berjalan lagi. Ia juga 3.

237
00:16:38,050 --> 00:16:40,950
Tetapi kali ini, perhatikan bagaimana kita mendapat 3.

238
00:16:40,950 --> 00:16:46,690
Kami mengambil - kita hanya mengambil 3 sendiri

239
00:16:46,690 --> 00:16:49,980
kerana ia dikelilingi oleh negatif di kedua-dua belah pihak,

240
00:16:49,980 --> 00:16:55,080
yang akan membawa jumlah <3.

241
00:16:55,080 --> 00:16:57,820
Mari kita berjalan di 10 item.

242
00:16:57,820 --> 00:17:03,200
Kali ini ia adalah 7, kita ambil 3 terkemuka dan 4.

243
00:17:03,200 --> 00:17:09,450
Kali ini ia adalah 8, dan kita mendapatkan bahawa dengan mengambil 1, 4 dan 3.

244
00:17:09,450 --> 00:17:16,310
Jadi, untuk memberi anda intuisi tentang bagaimana kita boleh menyelesaikan masalah ini yang berubah,

245
00:17:16,310 --> 00:17:18,890
mari kita melihat subarray ini.

246
00:17:18,890 --> 00:17:23,460
Kami diberikan ini pelbagai input, dan kita tahu jawapannya ialah 8.

247
00:17:23,460 --> 00:17:26,359
Kami mengambil 1, 4, dan 3.

248
00:17:26,359 --> 00:17:29,090
Tetapi biarlah kita melihat bagaimana kita sebenarnya mendapat jawapan yang.

249
00:17:29,090 --> 00:17:34,160
Mari kita melihat subarray maksimum yang berakhir pada setiap indeks ini.

250
00:17:34,160 --> 00:17:40,780
Apa subarray maksimum yang telah berakhir pada kedudukan pertama?

251
00:17:40,780 --> 00:17:46,310
[Pelajar] Sifar. >> Zero. Hanya tidak mengambil -5.

252
00:17:46,310 --> 00:17:50,210
Di sini ia akan menjadi 0 serta. Yeah?

253
00:17:50,210 --> 00:17:56,470
(Pelajar, tidak bijaksana yang)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, maaf, ia adalah -3.

255
00:17:58,960 --> 00:18:03,220
Jadi ini adalah 2, ini adalah -3.

256
00:18:03,220 --> 00:18:08,690
Okay. Jadi -4, apa yang subarray maksimum untuk menamatkan kedudukan itu

257
00:18:08,690 --> 00:18:12,910
mana -4 adalah pada? Sifar.

258
00:18:12,910 --> 00:18:22,570
Satu? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
Sekarang, saya mesti berakhir di lokasi mana -2 adalah pada.

260
00:18:28,060 --> 00:18:39,330
Jadi 6, 5, 7, dan yang terakhir ialah 4.

261
00:18:39,330 --> 00:18:43,480
Mengetahui bahawa ini adalah entri saya

262
00:18:43,480 --> 00:18:48,130
untuk masalah berubah di mana saya mesti berakhir pada setiap indeks ini,

263
00:18:48,130 --> 00:18:51,410
maka jawapan akhir saya hanya mengambil sapu di seluruh,

264
00:18:51,410 --> 00:18:53,580
dan mengambil bilangan maksimum.

265
00:18:53,580 --> 00:18:55,620
Jadi dalam kes ini ia adalah 8.

266
00:18:55,620 --> 00:19:00,010
Ini menunjukkan bahawa subarray maksimum berakhir pada indeks ini,

267
00:19:00,010 --> 00:19:04,970
dan bermula di suatu tempat sebelum ia.

268
00:19:04,970 --> 00:19:09,630
Adakah semua orang faham ini subarray berubah?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Nah, mari kita memikirkan berulang untuk ini.

270
00:19:22,160 --> 00:19:27,990
Mari kita pertimbangkan hanya beberapa entri pertama.

271
00:19:27,990 --> 00:19:35,930
Jadi di sini ia adalah 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
Dan kemudian ada -2 di sini, dan yang dibawa ke 6.

273
00:19:39,790 --> 00:19:50,800
Jadi, jika saya panggil kemasukan pada kedudukan i subproblem (i),

274
00:19:50,800 --> 00:19:54,910
bagaimana saya boleh menggunakan jawapan kepada subproblem sebelumnya

275
00:19:54,910 --> 00:19:59,360
untuk menjawab subproblem ini?

276
00:19:59,360 --> 00:20:04,550
Jika saya melihat, katakan, kemasukan ini.

277
00:20:04,550 --> 00:20:09,190
Bagaimana saya boleh mengira jawapan 6 dengan melihat

278
00:20:09,190 --> 00:20:18,780
gabungan pelbagai ini dan jawapan kepada subproblems sebelumnya dalam pelbagai ini? Ya?

279
00:20:18,780 --> 00:20:22,800
[Pelajar Perempuan] Anda mengambil pelbagai jumlah wang

280
00:20:22,800 --> 00:20:25,430
dalam kedudukan yang betul sebelum ia, jadi 8,

281
00:20:25,430 --> 00:20:32,170
dan kemudian anda menambah subproblem semasa.

282
00:20:32,170 --> 00:20:36,460
[Yu] Jadi cadangan beliau adalah untuk melihat kedua-dua nombor,

283
00:20:36,460 --> 00:20:40,090
nombor ini dan bilangan ini.

284
00:20:40,090 --> 00:20:50,130
Jadi ini 8 merujuk kepada jawapan untuk subproblem (i - 1).

285
00:20:50,130 --> 00:20:57,300
Dan mari kita memanggil A. pelbagai input saya

286
00:20:57,300 --> 00:21:01,470
Dalam usaha untuk mencari subarray maksimum yang berakhir pada kedudukan i,

287
00:21:01,470 --> 00:21:03,980
Saya mempunyai dua pilihan: saya sama ada boleh terus subarray

288
00:21:03,980 --> 00:21:09,790
yang berakhir pada indeks sebelumnya, atau memulakan pelbagai baru.

289
00:21:09,790 --> 00:21:14,190
Jika saya adalah untuk meneruskan subarray yang bermula pada indeks sebelumnya,

290
00:21:14,190 --> 00:21:19,260
maka jumlah maksimum yang saya boleh mencapai adalah jawapan kepada subproblem sebelumnya

291
00:21:19,260 --> 00:21:24,120
ditambah kemasukan array semasa.

292
00:21:24,120 --> 00:21:27,550
Tetapi, saya juga mempunyai pilihan memulakan subarray baru,

293
00:21:27,550 --> 00:21:30,830
di mana jumlah adalah 0.

294
00:21:30,830 --> 00:21:42,860
Jadi jawapannya adalah max 0, subproblem i - 1, ditambah kemasukan array semasa.

295
00:21:42,860 --> 00:21:46,150
Adakah berulangnya ini masuk akal?

296
00:21:46,150 --> 00:21:50,840
Berulangnya kami, kerana kami hanya ditemui, adalah subproblem i

297
00:21:50,840 --> 00:21:54,740
adalah bersamaan dengan maksimum subproblem sebelumnya ditambah kemasukan pelbagai semasa saya,

298
00:21:54,740 --> 00:22:01,490
yang bermaksud meneruskan subarray sebelumnya,

299
00:22:01,490 --> 00:22:07,250
atau 0, memulakan satu subarray pada indeks semasa saya baru.

300
00:22:07,250 --> 00:22:10,060
Dan apabila kita telah membina jadual ini penyelesaian, maka jawapan akhir kita,

301
00:22:10,060 --> 00:22:13,950
hanya melakukan menyapu linear merentasi pelbagai subproblem

302
00:22:13,950 --> 00:22:19,890
dan mengambil bilangan maksimum.

303
00:22:19,890 --> 00:22:23,330
Ini adalah pelaksanaan sebenar apa yang saya katakan.

304
00:22:23,330 --> 00:22:27,320
Jadi kita mewujudkan pelbagai subproblem baru, subproblems.

305
00:22:27,320 --> 00:22:32,330
Kemasukan pertama adalah sama ada 0 atau kemasukan pertama, maksimum kedua-dua.

306
00:22:32,330 --> 00:22:35,670
Dan untuk rehat daripada subproblems

307
00:22:35,670 --> 00:22:39,810
kita gunakan berulangnya sebenar kita hanya mendapati.

308
00:22:39,810 --> 00:22:49,960
Sekarang kita mengira maksimum pelbagai subproblems kami, dan itulah jawapan akhir kami.

309
00:22:49,960 --> 00:22:54,130
>> Jadi berapa banyak ruang yang kita gunakan dalam algoritma ini?

310
00:22:54,130 --> 00:23:01,470
Jika anda hanya diambil CS50, maka anda tidak mungkin telah dibincangkan ruang yang sangat banyak.

311
00:23:01,470 --> 00:23:07,750
Nah, salah satu perkara yang perlu diambil perhatian adalah bahawa saya dipanggil malloc sini dengan n saiz.

312
00:23:07,750 --> 00:23:13,590
Apakah yang mencadangkan kepada anda?

313
00:23:13,590 --> 00:23:17,450
Algoritma ini menggunakan ruang linear.

314
00:23:17,450 --> 00:23:21,030
Bolehkah kita melakukan yang lebih baik?

315
00:23:21,030 --> 00:23:30,780
Adakah terdapat apa-apa yang anda notis yang perlu untuk mengira jawapan akhir?

316
00:23:30,780 --> 00:23:33,290
Saya rasa soalan yang lebih baik, apa maklumat

317
00:23:33,290 --> 00:23:40,680
adakah kita tidak perlu untuk menjalankan sepanjang jalan hingga ke hujung?

318
00:23:40,680 --> 00:23:44,280
Sekarang, jika kita melihat kedua-dua baris,

319
00:23:44,280 --> 00:23:47,720
kita hanya menjaga tentang subproblem sebelumnya,

320
00:23:47,720 --> 00:23:50,910
dan kita hanya mengambil berat tentang maksimum kita pernah dilihat setakat ini.

321
00:23:50,910 --> 00:23:53,610
Untuk mengira jawapan akhir kita, kita tidak memerlukan pelbagai keseluruhan.

322
00:23:53,610 --> 00:23:57,450
Kami hanya memerlukan nombor terakhir, dua nombor terakhir.

323
00:23:57,450 --> 00:24:02,630
Nombor terakhir untuk pelbagai subproblem, dan nombor terakhir untuk maksimum.

324
00:24:02,630 --> 00:24:07,380
Jadi, pada hakikatnya, kita boleh menggabungkan gelung ini bersama

325
00:24:07,380 --> 00:24:10,460
dan pergi dari ruang linear ke angkasa malar.

326
00:24:10,460 --> 00:24:15,830
Jumlah semasa setakat ini, di sini, menggantikan peranan subproblem, pelbagai subproblem kami.

327
00:24:15,830 --> 00:24:20,020
Jumlah Jadi semasa, setakat ini, adalah jawapan kepada subproblem sebelumnya.

328
00:24:20,020 --> 00:24:23,450
Dan jumlah wang itu, setakat ini, mengambil tempat max kami.

329
00:24:23,450 --> 00:24:28,100
Kita mengira maksimum seperti yang kita pergi bersama-sama.

330
00:24:28,100 --> 00:24:30,890
Dan supaya kita pergi dari ruang linear kepada ruang yang berterusan,

331
00:24:30,890 --> 00:24:36,650
dan kami juga mempunyai penyelesaian linear kepada masalah subarray kami.

332
00:24:36,650 --> 00:24:40,740
>> Ini jenis soalan yang anda akan mendapat dalam satu temu bual.

333
00:24:40,740 --> 00:24:44,450
Apakah kerumitan masa; apakah kerumitan ruang?

334
00:24:44,450 --> 00:24:50,600
Anda boleh melakukan lebih baik? Adakah terdapat perkara-perkara yang tidak perlu untuk menjaga sekitar?

335
00:24:50,600 --> 00:24:55,270
Saya melakukan ini untuk menyerlahkan analisis yang anda perlu mengambil sendiri

336
00:24:55,270 --> 00:24:57,400
kerana anda bekerja melalui masalah-masalah ini.

337
00:24:57,400 --> 00:25:01,710
Sentiasa bertanya diri anda sendiri, "Bolehkah saya melakukan yang lebih baik?"

338
00:25:01,710 --> 00:25:07,800
Malah, kita boleh melakukan lebih baik daripada ini?

339
00:25:07,800 --> 00:25:10,730
Susun soalan helah. Anda tidak boleh, kerana anda perlu

340
00:25:10,730 --> 00:25:13,590
sekurang-kurangnya membaca input kepada masalah ini.

341
00:25:13,590 --> 00:25:15,570
Jadi hakikat bahawa anda perlu sekurang-kurangnya membaca input kepada masalah

342
00:25:15,570 --> 00:25:19,580
bermakna bahawa anda tidak boleh melakukan yang lebih baik daripada masa linear,

343
00:25:19,580 --> 00:25:22,870
dan anda tidak boleh melakukan lebih baik daripada ruang malar.

344
00:25:22,870 --> 00:25:27,060
Jadi ini adalah, pada hakikatnya, penyelesaian terbaik untuk masalah ini.

345
00:25:27,060 --> 00:25:33,040
Soalan? Okay.

346
00:25:33,040 --> 00:25:35,190
>> Masalah pasaran saham:

347
00:25:35,190 --> 00:25:38,350
"Memandangkan pelbagai integer n, positif, sifar, atau negatif,

348
00:25:38,350 --> 00:25:41,680
yang mewakili harga saham sepanjang hari n,

349
00:25:41,680 --> 00:25:44,080
menulis fungsi untuk mengira keuntungan maksimum anda boleh membuat

350
00:25:44,080 --> 00:25:49,350
diberikan bahawa anda membeli dan menjual tepat 1 saham dalam hari ini n. "

351
00:25:49,350 --> 00:25:51,690
Pada asasnya, kita mahu membeli rendah, menjual tinggi.

352
00:25:51,690 --> 00:25:58,580
Dan kita mahu memikirkan keuntungan yang terbaik kita boleh membuat.

353
00:25:58,580 --> 00:26:11,500
Akan kembali ke hujung saya, apa yang serta-merta jelas, jawapan yang paling mudah, tetapi ia perlahan?

354
00:26:11,500 --> 00:26:17,690
Ya? (Pelajar, difahami) >> Ya.

355
00:26:17,690 --> 00:26:21,470
>> Jadi anda hanya akan pergi walaupun dan melihat harga saham

356
00:26:21,470 --> 00:26:30,550
pada setiap titik dalam masa (difahami).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okay, so penyelesaiannya - cadangan beliau pengkomputeran

358
00:26:33,990 --> 00:26:37,380
terendah dan pengiraan tertinggi tidak semestinya bekerja

359
00:26:37,380 --> 00:26:42,470
kerana tertinggi mungkin berlaku sebelum terendah.

360
00:26:42,470 --> 00:26:47,340
Jadi apakah penyelesaian kekerasan kepada masalah ini?

361
00:26:47,340 --> 00:26:53,150
Apakah dua perkara yang saya perlu unik menentukan keuntungan yang saya buat? Betul.

362
00:26:53,150 --> 00:26:59,410
Penyelesaian kekerasan - oh, jadi, cadangan George adalah kita hanya perlu dua hari

363
00:26:59,410 --> 00:27:02,880
untuk unik menentukan keuntungan kedua-dua hari.

364
00:27:02,880 --> 00:27:06,660
Jadi kita mengira setiap pasangan, seperti membeli / menjual,

365
00:27:06,660 --> 00:27:12,850
mengira keuntungan, yang boleh menjadi positif atau negatif atau sifar.

366
00:27:12,850 --> 00:27:18,000
Kirakan keuntungan maksimum yang kita buat selepas iterating atas semua pasang hari.

367
00:27:18,000 --> 00:27:20,330
Yang akan menjadi jawapan muktamad kita.

368
00:27:20,330 --> 00:27:25,730
Dan penyelesaian yang akan O (n ^ 2), kerana terdapat n memilih dua pasang -

369
00:27:25,730 --> 00:27:30,270
hari yang anda boleh memilih antara hari akhir.

370
00:27:30,270 --> 00:27:32,580
Okay, jadi saya tidak akan pergi lebih penyelesaian tenaga kasar di sini.

371
00:27:32,580 --> 00:27:37,420
Saya akan memberitahu anda bahawa terdapat penyelesaian n log n.

372
00:27:37,420 --> 00:27:45,550
Apa algoritma tidak anda kini tahu bahawa n log n?

373
00:27:45,550 --> 00:27:50,730
Ia bukan satu soalan helah.

374
00:27:50,730 --> 00:27:54,790
>> Gabung apapun. Gabung apapun n log n,

375
00:27:54,790 --> 00:27:57,760
dan pada hakikatnya, salah satu cara untuk menyelesaikan masalah ini adalah dengan menggunakan

376
00:27:57,760 --> 00:28:04,400
jenis apapun bergabung idea yang dipanggil, secara umum, membahagi dan menakluk.

377
00:28:04,400 --> 00:28:07,570
Dan idea adalah seperti berikut.

378
00:28:07,570 --> 00:28:12,400
Anda mahu untuk mengira belian terbaik / menjual sepasang dalam separuh kiri.

379
00:28:12,400 --> 00:28:16,480
Cari keuntungan terbaik anda boleh membuat, hanya dengan n pertama selama dua hari.

380
00:28:16,480 --> 00:28:19,780
Maka anda mahu oompute belian terbaik / menjual sepasang pada separuh kanan,

381
00:28:19,780 --> 00:28:23,930
jadi n lepas selama dua hari.

382
00:28:23,930 --> 00:28:32,400
Dan kini persoalannya ialah, bagaimana kita menggabungkan penyelesaian ini kembali bersama-sama?

383
00:28:32,400 --> 00:28:36,320
Ya? (Pelajar, tidak bijaksana yang)

384
00:28:36,320 --> 00:28:49,890
>> Okay. Jadi biarlah saya melukis.

385
00:28:49,890 --> 00:29:03,870
Ya? (George, difahami)

386
00:29:03,870 --> 00:29:06,450
>> Tepat sekali. Penyelesaian George adalah betul-betul betul.

387
00:29:06,450 --> 00:29:10,040
Jadi cadangan beliau ialah, pertama mengira terbaik membeli / menjual sepasang,

388
00:29:10,040 --> 00:29:16,050
dan yang berlaku dalam separuh kiri, jadi mari kita panggil yang kiri, kiri.

389
00:29:16,050 --> 00:29:20,790
Best membeli / menjual pasangan yang berlaku dalam separuh betul.

390
00:29:20,790 --> 00:29:25,180
Tetapi jika kita hanya berbanding kedua-dua nombor, kita hilang kes

391
00:29:25,180 --> 00:29:30,460
di mana kita membeli di sini dan menjual suatu tempat di separuh betul.

392
00:29:30,460 --> 00:29:33,810
Kami membeli dalam separuh kiri, menjual pada separuh yang betul.

393
00:29:33,810 --> 00:29:38,490
Dan cara terbaik untuk mengira terbaik membeli / menjual pasangan yang menjangkau kedua-dua bahagian

394
00:29:38,490 --> 00:29:43,480
adalah untuk mengira sekurang-kurangnya di sini dan mengira maksimum di sini

395
00:29:43,480 --> 00:29:45,580
dan mengambil perbezaan mereka.

396
00:29:45,580 --> 00:29:50,850
Jadi kedua-dua kes di mana pasangan membeli / menjual berlaku hanya di sini,

397
00:29:50,850 --> 00:30:01,910
hanya di sini, atau di kedua-dua bahagian ditakrifkan oleh tiga nombor.

398
00:30:01,910 --> 00:30:06,450
Jadi algoritma kami untuk menggabungkan penyelesaian kami kembali bersama-sama,

399
00:30:06,450 --> 00:30:08,350
kita mahu untuk mengira terbaik membeli / menjual sepasang

400
00:30:08,350 --> 00:30:13,120
di mana kita membeli di separuh kiri dan menjual pada separuh betul.

401
00:30:13,120 --> 00:30:16,740
Dan cara terbaik untuk berbuat demikian adalah untuk mengira harga terendah pada separuh pertama,

402
00:30:16,740 --> 00:30:20,360
harga tertinggi dalam separuh betul, dan mengambil perbezaan mereka.

403
00:30:20,360 --> 00:30:25,390
Yang terhasil tiga keuntungan, ketiga-tiga nombor, anda mengambil maksimum tiga,

404
00:30:25,390 --> 00:30:32,720
dan itulah keuntungan terbaik anda boleh membuat ke atas hari ini pertama dan akhir.

405
00:30:32,720 --> 00:30:36,940
Berikut garis penting adalah merah.

406
00:30:36,940 --> 00:30:41,160
Ini adalah panggilan rekursi untuk mengira jawapan dalam separuh kiri.

407
00:30:41,160 --> 00:30:44,760
Ini adalah panggilan rekursi untuk mengira jawapan dalam separuh betul.

408
00:30:44,760 --> 00:30:50,720
Kedua-dua untuk gelung mengira min dan maks pada separuh kiri dan kanan, masing-masing.

409
00:30:50,720 --> 00:30:54,970
Sekarang saya mengira keuntungan yang menjangkau kedua-dua bahagian,

410
00:30:54,970 --> 00:31:00,530
dan jawapan akhir adalah maksimum ketiga-tiga.

411
00:31:00,530 --> 00:31:04,120
Okay.

412
00:31:04,120 --> 00:31:06,420
>> Jadi, pasti, kita mempunyai algoritma, tetapi soalan yang lebih besar,

413
00:31:06,420 --> 00:31:08,290
apakah kerumitan masa ini?

414
00:31:08,290 --> 00:31:16,190
Dan sebab mengapa saya sebutkan apapun merge adalah bahawa ini bentuk membahagikan jawapannya

415
00:31:16,190 --> 00:31:19,200
kepada dua dan kemudian bergabung penyelesaian kami kembali bersama-sama

416
00:31:19,200 --> 00:31:23,580
sebenarnya bentuk apapun merge.

417
00:31:23,580 --> 00:31:33,360
Jadi biarlah saya pergi melalui tempoh.

418
00:31:33,360 --> 00:31:41,340
Jika kita ditakrifkan fungsi t (n) untuk menjadi nombor langkah

419
00:31:41,340 --> 00:31:50,010
untuk hari n,

420
00:31:50,010 --> 00:31:54,350
2 panggilan rekursi kami

421
00:31:54,350 --> 00:32:00,460
masing-masing akan kos t (n / 2),

422
00:32:00,460 --> 00:32:03,540
dan terdapat dua panggilan ini.

423
00:32:03,540 --> 00:32:10,020
Sekarang saya perlu untuk mengira sekurang-kurangnya separuh kiri,

424
00:32:10,020 --> 00:32:17,050
yang boleh saya lakukan di n / 2 masa, ditambah dengan maksimum separuh betul.

425
00:32:17,050 --> 00:32:20,820
Jadi ini hanya n.

426
00:32:20,820 --> 00:32:25,050
Dan kemudian ditambah dengan beberapa pekerjaan tetap.

427
00:32:25,050 --> 00:32:27,770
Dan persamaan ini berulang

428
00:32:27,770 --> 00:32:35,560
tepat persamaan apapun merge untuk berulang.

429
00:32:35,560 --> 00:32:39,170
Dan kita semua tahu bahawa apapun merge n log n masa.

430
00:32:39,170 --> 00:32:46,880
Oleh itu, algoritma kami juga n log n masa.

431
00:32:46,880 --> 00:32:52,220
Adakah lelaran ini masuk akal?

432
00:32:52,220 --> 00:32:55,780
Hanya recap ringkas ini:

433
00:32:55,780 --> 00:32:59,170
T (n) adalah beberapa langkah untuk mengira keuntungan maksimum

434
00:32:59,170 --> 00:33:02,750
sepanjang hari n.

435
00:33:02,750 --> 00:33:06,010
Cara kita berpecah panggilan rekursi kami

436
00:33:06,010 --> 00:33:11,980
adalah dengan memanggil penyelesaian kami pada hari pertama n / 2,

437
00:33:11,980 --> 00:33:14,490
supaya satu panggilan,

438
00:33:14,490 --> 00:33:16,940
dan kemudian kita panggil sekali lagi pada separuh kedua.

439
00:33:16,940 --> 00:33:20,440
Jadi itulah dua panggilan.

440
00:33:20,440 --> 00:33:25,310
Dan kemudian kita dapati minimum di separuh kiri, yang boleh kita lakukan dalam masa linear,

441
00:33:25,310 --> 00:33:29,010
mencari maksimum separuh betul, yang boleh kita lakukan dalam masa linear.

442
00:33:29,010 --> 00:33:31,570
Jadi n / 2 + n / 2 adalah hanya n.

443
00:33:31,570 --> 00:33:36,020
Kemudian kita mempunyai beberapa kerja yang berterusan, yang adalah seperti melakukan aritmetik.

444
00:33:36,020 --> 00:33:39,860
Persamaan ini perulangan adalah tepat persamaan apapun merge untuk berulang.

445
00:33:39,860 --> 00:33:55,490
Oleh itu, algoritma shuffle kami juga n log n.

446
00:33:55,490 --> 00:33:58,520
Jadi berapa banyak ruang yang kita gunakan?

447
00:33:58,520 --> 00:34:04,910
Mari kita kembali kepada kod.

448
00:34:04,910 --> 00:34:09,420
>> Satu soalan yang lebih baik, berapa banyak bingkai tindanan yang kita pernah mempunyai pada bila-bila masa yang diberikan?

449
00:34:09,420 --> 00:34:11,449
Sejak kita menggunakan rekursi,

450
00:34:11,449 --> 00:34:23,530
bilangan bingkai tindanan menentukan penggunaan ruang kami.

451
00:34:23,530 --> 00:34:29,440
Mari kita pertimbangkan n = 8.

452
00:34:29,440 --> 00:34:36,889
Kami menyeru shuffle pada 8,

453
00:34:36,889 --> 00:34:41,580
yang akan memanggil shuffle di empat penyertaan pertama,

454
00:34:41,580 --> 00:34:46,250
yang akan memanggil shuffle pada dua penyertaan pertama.

455
00:34:46,250 --> 00:34:51,550
Jadi timbunan kami - ini adalah timbunan kita.

456
00:34:51,550 --> 00:34:54,980
Dan kemudian kita panggil shuffle lagi pada 1,

457
00:34:54,980 --> 00:34:58,070
dan bahawa apa kes asas kami, jadi kita kembali dengan segera.

458
00:34:58,070 --> 00:35:04,700
Adakah kita pernah mempunyai lebih daripada ini bingkai tindanan banyak?

459
00:35:04,700 --> 00:35:08,880
No Kerana setiap kali kita lakukan doa,

460
00:35:08,880 --> 00:35:10,770
doa rekursi shuffle,

461
00:35:10,770 --> 00:35:13,950
kita bahagikan saiz kami pada separuh.

462
00:35:13,950 --> 00:35:17,020
Jadi bilangan maksimum bingkai tindanan kita pernah pada bila-bila masa yang diberikan

463
00:35:17,020 --> 00:35:28,460
adalah atas perintah bingkai log n timbunan.

464
00:35:28,460 --> 00:35:42,460
Setiap bingkai tindanan mempunyai ruang yang berterusan,

465
00:35:42,460 --> 00:35:44,410
dan oleh itu jumlah ruang,

466
00:35:44,410 --> 00:35:49,240
jumlah maksimum ruang kita pernah menggunakan O (log n) ruang

467
00:35:49,240 --> 00:36:03,040
di mana n adalah bilangan hari.

468
00:36:03,040 --> 00:36:07,230
>> Sekarang, sentiasa bertanya kepada diri sendiri, "Bolehkah kita melakukan yang lebih baik?"

469
00:36:07,230 --> 00:36:12,390
Dan khususnya, kita boleh mengurangkan ini kepada masalah kita sudah diselesaikan?

470
00:36:12,390 --> 00:36:20,040
Bayangan A: kita hanya membincangkan dua masalah lain sebelum ini, dan ia tidak akan menjadi shuffle.

471
00:36:20,040 --> 00:36:26,200
Kita boleh menukar ini masalah pasaran saham ke dalam masalah subarray yang maksimum.

472
00:36:26,200 --> 00:36:40,100
Bagaimana kita boleh melakukan ini?

473
00:36:40,100 --> 00:36:42,570
Salah satu anda? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, difahami)

475
00:36:47,680 --> 00:36:53,860
[Yu] Tepat sekali.

476
00:36:53,860 --> 00:36:59,940
Jadi masalah subarray yang maksimum,

477
00:36:59,940 --> 00:37:10,610
kita sedang mencari sejumlah atas subarray berterusan.

478
00:37:10,610 --> 00:37:16,230
Dan cadangan Emmy untuk masalah stok,

479
00:37:16,230 --> 00:37:30,720
mempertimbangkan perubahan, atau delta.

480
00:37:30,720 --> 00:37:37,440
Dan gambar ini - ini adalah harga saham,

481
00:37:37,440 --> 00:37:42,610
tetapi jika kita mengambil perbezaan antara setiap hari berturut-turut -

482
00:37:42,610 --> 00:37:45,200
jadi kita lihat bahawa harga maksimum, keuntungan maksimum kita boleh membuat

483
00:37:45,200 --> 00:37:50,070
adalah jika kita membeli di sini dan menjual di sini.

484
00:37:50,070 --> 00:37:54,240
Tetapi mari kita lihat di berterusan - mari kita melihat masalah subarray.

485
00:37:54,240 --> 00:38:02,510
Jadi di sini, kita boleh membuat - pergi dari sini ke sini,

486
00:38:02,510 --> 00:38:08,410
kita mempunyai perubahan positif, dan kemudian pergi dari sini ke sini, kita mempunyai perubahan negatif.

487
00:38:08,410 --> 00:38:14,220
Tetapi kemudian, pergi dari sini ke sini kita mempunyai perubahan positif yang besar.

488
00:38:14,220 --> 00:38:20,930
Dan ini adalah perubahan yang kita mahu untuk meringkaskannya untuk mendapatkan keuntungan akhir kami.

489
00:38:20,930 --> 00:38:25,160
Kemudian kita mempunyai perubahan yang lebih negatif di sini.

490
00:38:25,160 --> 00:38:29,990
Kunci untuk mengurangkan masalah saham kita ke masalah subarray maksimum kami

491
00:38:29,990 --> 00:38:36,630
adalah untuk mempertimbangkan delta antara hari.

492
00:38:36,630 --> 00:38:40,630
Jadi kita mewujudkan barisan baru yang dipanggil delta,

493
00:38:40,630 --> 00:38:43,000
memulakan kemasukan pertama untuk menjadi 0,

494
00:38:43,000 --> 00:38:46,380
dan kemudian untuk setiap delta (i), membiarkan yang menjadi perbezaan

495
00:38:46,380 --> 00:38:52,830
pelbagai input saya (i), dan pelbagai (i - 1).

496
00:38:52,830 --> 00:38:55,530
Kemudian kita panggil prosedur rutin kami untuk subarray satu maksimum

497
00:38:55,530 --> 00:39:01,500
lulus dalam pelbagai delta.

498
00:39:01,500 --> 00:39:06,440
Dan kerana subarray maksimum adalah masa yang linear,

499
00:39:06,440 --> 00:39:09,370
dan pengurangan ini, proses ini mewujudkan pelbagai delta,

500
00:39:09,370 --> 00:39:11,780
juga masa linear,

501
00:39:11,780 --> 00:39:19,060
maka penyelesaian akhir bagi saham adalah O (n) kerja kerja ditambah O (n), adalah masih O (n) kerja.

502
00:39:19,060 --> 00:39:23,900
Jadi kita mempunyai penyelesaian masa linear kepada masalah kita.

503
00:39:23,900 --> 00:39:29,610
Adakah semua orang memahami transformasi ini?

504
00:39:29,610 --> 00:39:32,140
>> Secara umum, idea yang baik yang anda perlu sentiasa ada

505
00:39:32,140 --> 00:39:34,290
cuba untuk mengurangkan masalah baru yang anda lihat.

506
00:39:34,290 --> 00:39:37,700
Jika ia kelihatan biasa kepada masalah yang lama,

507
00:39:37,700 --> 00:39:39,590
cuba mengurangkan masalah lama.

508
00:39:39,590 --> 00:39:41,950
Dan jika anda boleh menggunakan semua alat-alat yang anda telah digunakan pada masalah lama

509
00:39:41,950 --> 00:39:46,450
untuk menyelesaikan masalah baru.

510
00:39:46,450 --> 00:39:49,010
Jadi untuk membalut, temuduga teknikal yang mencabar.

511
00:39:49,010 --> 00:39:52,280
Masalah-masalah ini mungkin beberapa masalah yang lebih sukar

512
00:39:52,280 --> 00:39:54,700
yang anda mungkin lihat dalam satu temu bual,

513
00:39:54,700 --> 00:39:57,690
jadi jika anda tidak memahami semua masalah yang saya hanya dilindungi, ia adalah okay.

514
00:39:57,690 --> 00:40:01,080
Ini adalah beberapa masalah yang lebih mencabar.

515
00:40:01,080 --> 00:40:03,050
Amalan, amalan, amalan.

516
00:40:03,050 --> 00:40:08,170
Saya memberikan banyak masalah dalam nota, jadi pasti memeriksa mereka keluar.

517
00:40:08,170 --> 00:40:11,690
Dan nasib baik temuduga anda. Semua sumber saya Hantar pada pautan ini,

518
00:40:11,690 --> 00:40:15,220
dan salah satu daripada rakan-rakan kanan saya telah ditawarkan untuk melakukan wawancara teknikal olok-olok,

519
00:40:15,220 --> 00:40:22,050
jadi jika anda berminat, e-mel Will Yao di alamat e-mel.

520
00:40:22,050 --> 00:40:26,070
Jika anda mempunyai beberapa soalan, anda boleh bertanya kepada saya.

521
00:40:26,070 --> 00:40:28,780
Adakah anda semua mempunyai soalan-soalan khusus yang berkaitan dengan temuduga teknikal

522
00:40:28,780 --> 00:40:38,440
atau mana-mana masalah yang kita telah melihat setakat ini?

523
00:40:38,440 --> 00:40:49,910
Okay. Nah, nasib baik temuduga anda.

524
00:40:49,910 --> 00:40:52,910
[CS50.TV]