1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Семінар: Тэхнічныя Інтэрв'ю]

2
00:00:02,640 --> 00:00:04,630
[Kenny Ю., Гарвардскі універсітэт]

3
00:00:04,630 --> 00:00:08,910
[Гэта CS50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Прывітанне ўсім, я Кені. У цяперашні час я малодшы, якія вывучаюць інфарматыку.

5
00:00:12,420 --> 00:00:17,310
Я былы CS TF, і я б хацеў гэтага, калі я быў студэнт першага або другога курсу,

6
00:00:17,310 --> 00:00:19,380
і менавіта таму я даю гэты семінар.

7
00:00:19,380 --> 00:00:21,370
Так што я спадзяюся, вам спадабаецца.

8
00:00:21,370 --> 00:00:23,470
Гэты семінар аб тэхнічных інтэрв'ю,

9
00:00:23,470 --> 00:00:26,650
і ўсе мае рэсурсы можна знайсці па гэтай спасылцы,

10
00:00:26,650 --> 00:00:32,350
спасылку прама тут, пару рэсурсаў.

11
00:00:32,350 --> 00:00:36,550
Таму я склаў спіс праблем, на самай справе, даволі шмат праблем.

12
00:00:36,550 --> 00:00:40,800
Акрамя таго, агульнае старонкі рэсурсаў, дзе можна знайсці парады

13
00:00:40,800 --> 00:00:42,870
пра тое, як падрыхтавацца да сумоўя,

14
00:00:42,870 --> 00:00:46,470
парады аб тым, што вы павінны зрабіць на працягу фактычнага інтэрв'ю,

15
00:00:46,470 --> 00:00:51,910
а таксама, як падыходзіць да праблем і рэсурсы для далейшага выкарыстання.

16
00:00:51,910 --> 00:00:53,980
Гэта ўсё он-лайн.

17
00:00:53,980 --> 00:00:58,290
І каб апярэдзіць гэты семінар, адмова,

18
00:00:58,290 --> 00:01:00,690
як гэта не варта - ваша падрыхтоўка да інтэрв'ю

19
00:01:00,690 --> 00:01:02,800
не павінны быць абмежаваныя ў гэты спіс.

20
00:01:02,800 --> 00:01:04,750
Гэта толькі азначае, што кіраўніцтва,

21
00:01:04,750 --> 00:01:08,890
і вы павінны абавязкова ўзяць усё, што я кажу з збожжам солі,

22
00:01:08,890 --> 00:01:14,620
але і выкарыстоўваць усе, што я выкарыстаў, каб дапамагчы вам у вашай падрыхтоўцы да інтэрв'ю.

23
00:01:14,620 --> 00:01:16,400
>> Я хачу, каб паскорыць працягу наступных некалькіх слайдах

24
00:01:16,400 --> 00:01:18,650
так што мы можам дабрацца да фактычнага даследаванняў.

25
00:01:18,650 --> 00:01:23,630
Структура інтэрв'ю постион распрацоўкі праграмнага забеспячэння,

26
00:01:23,630 --> 00:01:26,320
Звычайна яна складае ад 30 да 45 хвілін,

27
00:01:26,320 --> 00:01:29,810
некалькі раўндаў, у залежнасці ад кампаніі.

28
00:01:29,810 --> 00:01:33,090
Часта вы будзеце кадавання на белай дошцы.

29
00:01:33,090 --> 00:01:35,960
Такім чынам, белая дошка, як гэта, але часта і ў меншых маштабах.

30
00:01:35,960 --> 00:01:38,540
Калі ў вас інтэрв'ю па тэлефоне, вы будзеце, верагодна, выкарыстоўваць

31
00:01:38,540 --> 00:01:44,030
альбо collabedit або Google Doc каб яны маглі бачыць вы жывяце кадавання

32
00:01:44,030 --> 00:01:46,500
а вы ў час інтэрв'ю па тэлефоне.

33
00:01:46,500 --> 00:01:48,490
Інтэрв'ю сабе, як правіла, 2 ці 3 праблемы

34
00:01:48,490 --> 00:01:50,620
тэставанне кампутара навуковых ведаў.

35
00:01:50,620 --> 00:01:54,490
І гэта будзе амаль дакладна звязаны з кадаваньне.

36
00:01:54,490 --> 00:01:59,540
Тыпы пытанняў, якія вы ўбачыце, як правіла, структуры дадзеных і алгарытмы.

37
00:01:59,540 --> 00:02:02,210
І пры гэтым гэтыя віды праблем,

38
00:02:02,210 --> 00:02:07,830
яны будуць прасіць вас, быццам бы, колькі часу і прасторы складанасць, вялікія O?

39
00:02:07,830 --> 00:02:09,800
Часта яны таксама просяць больш высокім узроўні пытанні,

40
00:02:09,800 --> 00:02:12,530
Такім чынам, праектаванне сістэмы,

41
00:02:12,530 --> 00:02:14,770
Як бы вы выкласці код?

42
00:02:14,770 --> 00:02:18,370
Якія інтэрфейсы, якія класы, якія модулі ў вас ёсць у вашай сістэме,

43
00:02:18,370 --> 00:02:20,900
і як яны ўзаемадзейнічаюць адзін з адным?

44
00:02:20,900 --> 00:02:26,130
Такім чынам, структуры дадзеных і алгарытмы, а таксама праектаванне сістэм.

45
00:02:26,130 --> 00:02:29,180
>> Некаторыя агульныя парады Перш чым мы паглыбімся ў нашы тэматычныя даследаванні.

46
00:02:29,180 --> 00:02:32,300
Я думаю, што самае важнае правіла заўсёды думаць услых.

47
00:02:32,300 --> 00:02:36,980
Інтэрв'ю павінна быць ваш шанец паказаць свой разумовы працэс.

48
00:02:36,980 --> 00:02:39,820
Справа ў інтэрв'ю для інтэрв'юера, каб вымераць

49
00:02:39,820 --> 00:02:42,660
як вы думаеце, і як вы ідзяце праз праблеме.

50
00:02:42,660 --> 00:02:45,210
Горшае, што вы можаце зрабіць, гэта маўчаць на працягу ўсяго інтэрв'ю.

51
00:02:45,210 --> 00:02:50,090
Вось толькі нічога добрага.

52
00:02:50,090 --> 00:02:53,230
Калі вы атрымліваеце пытанне, вы таксама хочаце, каб пераканацца, што вы зразумелі пытанне.

53
00:02:53,230 --> 00:02:55,350
Так што паўтару пытанне яшчэ ў свае словы

54
00:02:55,350 --> 00:02:58,920
і спроба працаваць дбайнай некалькі простых тэстаў

55
00:02:58,920 --> 00:03:01,530
пераканайцеся, што вы зразумелі пытанне.

56
00:03:01,530 --> 00:03:05,510
Праца праз некалькі тэстаў таксама дасць вам інтуіцыя аб тым, як вырашыць гэтую праблему.

57
00:03:05,510 --> 00:03:11,210
Вы нават можаце адкрыць для сябе некалькі мадэляў, каб дапамагчы вам вырашыць гэтую праблему.

58
00:03:11,210 --> 00:03:14,500
Іх вялікія чаявыя, каб не хвалявацца.

59
00:03:14,500 --> 00:03:17,060
Не хвалюйцеся.

60
00:03:17,060 --> 00:03:19,060
Інтэрв'ю з'яўляюцца складанымі, але горшае, што вы можаце зрабіць,

61
00:03:19,060 --> 00:03:23,330
У дадатак да таго, маўчыць, павінна быць відавочна расчараваныя.

62
00:03:23,330 --> 00:03:27,410
Вы ж не хочаце, каб даць ўражанне, што інтэрв'юер.

63
00:03:27,410 --> 00:03:33,960
Адна рэч, якую вы - так, многія людзі, калі яны ідуць у інтэрв'ю,

64
00:03:33,960 --> 00:03:37,150
яны спрабуюць, каб паспрабаваць знайсці лепшае рашэнне першай,

65
00:03:37,150 --> 00:03:39,950
калі на самай справе, там звычайна відавочныя рашэнне.

66
00:03:39,950 --> 00:03:43,500
Гэта можа быць павольным, яно можа быць неэфектыўным, але вы павінны проста канстатаваць гэта,

67
00:03:43,500 --> 00:03:46,210
проста так у вас ёсць адпраўная кропка, з якой можна працаваць лепш.

68
00:03:46,210 --> 00:03:48,270
Акрамя таго, паказваючы на ​​рашэнне павольна, з пункту гледжання

69
00:03:48,270 --> 00:03:52,160
вялікі час O складанасці або прастору складанасці,

70
00:03:52,160 --> 00:03:54,450
будзе прадэманстраваць інтэрв'юеру, што вы разумееце,

71
00:03:54,450 --> 00:03:57,510
гэтыя пытанні пры напісанні кода.

72
00:03:57,510 --> 00:04:01,440
Так што не бойцеся прыдумаць найпросты алгарытм спачатку

73
00:04:01,440 --> 00:04:04,950
, А затым працаваць лепш адтуль.

74
00:04:04,950 --> 00:04:09,810
Любыя пытанні да гэтага часу? Добра.

75
00:04:09,810 --> 00:04:11,650
>> Так што давайце пагрузіцца ў нашу першую задачу.

76
00:04:11,650 --> 00:04:14,790
"Улічваючы масіў цэлых лікаў п, напісаць функцыю, якая тасуе масіва

77
00:04:14,790 --> 00:04:20,209
на месца так, што ўсе перастаноўкі лікаў п аднолькава верагодныя. "

78
00:04:20,209 --> 00:04:23,470
І выкажам здагадку, у вас маецца генератар выпадковых цэлых

79
00:04:23,470 --> 00:04:30,980
, Які генеруе цэлы лік у дыяпазоне ад 0 да я, палову дыяпазону.

80
00:04:30,980 --> 00:04:32,970
Ці ўсё разумеюць гэтае пытанне?

81
00:04:32,970 --> 00:04:39,660
Я даю вам масіў цэлых лікаў п, і я хачу, каб змяшаць.

82
00:04:39,660 --> 00:04:46,050
У маім каталогу, я напісаў некалькі праграм, каб прадэманстраваць, што я маю на ўвазе.

83
00:04:46,050 --> 00:04:48,910
Я збіраюся змяшаць масіў з 20 элементаў,

84
00:04:48,910 --> 00:04:52,490
ад -10 да 9,

85
00:04:52,490 --> 00:04:57,050
і я хачу, каб вы вывесці спіс, як гэта.

86
00:04:57,050 --> 00:05:02,890
Так што гэта мой адсартаваны масіў зыходных дадзеных, і я хачу, каб ты змяшаць.

87
00:05:02,890 --> 00:05:07,070
Мы зробім гэта зноў.

88
00:05:07,070 --> 00:05:13,780
Ці ўсё разумеюць, у чым пытанне? Добра.

89
00:05:13,780 --> 00:05:16,730
Так што гэта залежыць ад вас.

90
00:05:16,730 --> 00:05:21,220
Якія ідэі? Вы можаце зрабіць гэта пры п ^ 2, п § п, п?

91
00:05:21,220 --> 00:05:34,400
Адкрыты для прапаноў.

92
00:05:34,400 --> 00:05:37,730
Добра. Так што ідэя, прапанаваная Эмі,

93
00:05:37,730 --> 00:05:45,300
1. вылічыць выпадковае лік, выпадковае лік, у дыяпазоне ад 0 да 20.

94
00:05:45,300 --> 00:05:49,840
Такім чынам, выкажам здагадку, наш масіў мае даўжыню 20.

95
00:05:49,840 --> 00:05:54,800
У нашай схеме 20 элементаў,

96
00:05:54,800 --> 00:05:58,560
гэта наш ўваходны масіў.

97
00:05:58,560 --> 00:06:04,590
І цяпер, яе прапанова з'яўляецца стварэнне новага масіва,

98
00:06:04,590 --> 00:06:08,440
так што гэта будзе выхадны масіў.

99
00:06:08,440 --> 00:06:12,880
І на аснове я вярнуўся на рандаў -

100
00:06:12,880 --> 00:06:17,580
так што калі б я быў, скажам, 17,

101
00:06:17,580 --> 00:06:25,640
скапіяваць 17 элементаў у першай пазіцыі.

102
00:06:25,640 --> 00:06:30,300
Цяпер нам трэба выдаліць - мы павінны перакласці ўсе элементы тут

103
00:06:30,300 --> 00:06:36,920
над тым, што ў нас ёсць прабел у канцы і без адтулін у сярэдзіне.

104
00:06:36,920 --> 00:06:39,860
І зараз мы паўтараем працэс.

105
00:06:39,860 --> 00:06:46,360
Цяпер мы выбіраем новае выпадковы лік паміж 0 і 19.

106
00:06:46,360 --> 00:06:52,510
У нас ёсць новая я тут, і мы капіяваны гэты элемент у гэтай пазіцыі.

107
00:06:52,510 --> 00:07:00,960
Затым мы пераходзім элементы зноў і паўтарыць працэс, пакуль у нас ёсць поўны новага масіва.

108
00:07:00,960 --> 00:07:05,890
Што такое час выканання гэтага алгарытму?

109
00:07:05,890 --> 00:07:08,110
Ну, давайце разгледзім наступствы гэтага.

110
00:07:08,110 --> 00:07:10,380
Мы пераходзім кожнага элемента.

111
00:07:10,380 --> 00:07:16,800
Калі мы выдаляем гэта я, мы пераходзім ўсе элементы пасля яго налева.

112
00:07:16,800 --> 00:07:21,600
І гэта O (п) кошт

113
00:07:21,600 --> 00:07:26,100
таму што, калі мы выдаляем першы элемент?

114
00:07:26,100 --> 00:07:29,670
Такім чынам, для кожнага выдалення, мы выдаляем -

115
00:07:29,670 --> 00:07:32,170
кожнае выдаленне нясе O (N) аперацый,

116
00:07:32,170 --> 00:07:41,520
і так як мы маем п абсорбцыі, гэта прыводзіць да O (N ^ 2) змяшаць.

117
00:07:41,520 --> 00:07:49,550
Добра. Так што добры пачатак. Добры пачатак.

118
00:07:49,550 --> 00:07:55,290
>> Іншая прапанова заключаецца ў выкарыстанні нешта, вядомае як пустую Кнута,

119
00:07:55,290 --> 00:07:57,540
або Fisher-Yates Shuffle.

120
00:07:57,540 --> 00:07:59,630
І гэта на самай справе лінейнага мяшання часу.

121
00:07:59,630 --> 00:08:02,200
А ідэя вельмі падобная.

122
00:08:02,200 --> 00:08:05,160
Зноў жа, у нас ёсць ўваходны масіў,

123
00:08:05,160 --> 00:08:08,580
але замест двух масіваў для нашых ўводу / вываду,

124
00:08:08,580 --> 00:08:13,590
мы выкарыстоўваем першую частку масіва сачыць за нашымі ператасаваць частка,

125
00:08:13,590 --> 00:08:18,400
і мы адсочваем, і тады мы пакінуць астатнюю частку нашага масіва для unshuffled частку.

126
00:08:18,400 --> 00:08:24,330
Такім чынам, вось што я маю на ўвазе. Мы пачынаем з - мы выбіраем я,

127
00:08:24,330 --> 00:08:30,910
масіў ад 0 да 20.

128
00:08:30,910 --> 00:08:36,150
Наш бягучы паказальнік паказвае на першы індэкс.

129
00:08:36,150 --> 00:08:39,590
Абярэм некаторы я тут

130
00:08:39,590 --> 00:08:42,740
і зараз мы перастаўляць.

131
00:08:42,740 --> 00:08:47,690
Так што, калі гэта было 5, і гэта было 4,

132
00:08:47,690 --> 00:08:57,150
выніковы масіў будзе мець 5 Тут і 4 тут.

133
00:08:57,150 --> 00:09:00,390
А зараз звярніце ўвагу маркерам тут.

134
00:09:00,390 --> 00:09:05,770
Усе злева тасуецца,

135
00:09:05,770 --> 00:09:15,160
і ўсё, што права unshuffled.

136
00:09:15,160 --> 00:09:17,260
І зараз мы можам паўтарыць працэс.

137
00:09:17,260 --> 00:09:25,210
Мы абярэм выпадковым індэксам ад 1 да 20 у цяперашні час.

138
00:09:25,210 --> 00:09:30,650
Такім чынам, хай наш новы я тут.

139
00:09:30,650 --> 00:09:39,370
Цяпер мы перастаўляць гэтым я з нашым бягучых новае палажэнне тут.

140
00:09:39,370 --> 00:09:44,790
Таму мы перапампоўкі наперад і назад, як гэта.

141
00:09:44,790 --> 00:09:51,630
Дазвольце мне падняць код, каб зрабіць яго больш канкрэтным.

142
00:09:51,630 --> 00:09:55,290
Пачнем з нашым выбарам я -

143
00:09:55,290 --> 00:09:58,370
Мы пачынаем з я роўная 0, мы выбіраем выпадковае размяшчэнне J

144
00:09:58,370 --> 00:10:02,420
У unshuffled частка масіва, я да п-1.

145
00:10:02,420 --> 00:10:07,280
Так што, калі я тут, абраць выпадковы індэкс паміж тут і астатняя частка масіва,

146
00:10:07,280 --> 00:10:12,410
і мы перастаўляць.

147
00:10:12,410 --> 00:10:17,550
Гэта ўвесь код, неабходны для мяшання масіва.

148
00:10:17,550 --> 00:10:21,670
Ёсць пытанні?

149
00:10:21,670 --> 00:10:25,530
>> Ну, адзін неабходны пытанне, чаму гэта правільна?

150
00:10:25,530 --> 00:10:28,360
Чаму ўсе перастаноўкі равновероятны?

151
00:10:28,360 --> 00:10:30,410
І я не буду доказ гэтага,

152
00:10:30,410 --> 00:10:35,970
але шматлікія праблемы ў галіне кампутарных навук можа быць даказана шляхам індукцыі.

153
00:10:35,970 --> 00:10:38,520
Як многія з вас ужо знаёмыя з індукцыяй?

154
00:10:38,520 --> 00:10:40,590
Добра. Cool.

155
00:10:40,590 --> 00:10:43,610
Такім чынам, вы можаце даказаць правільнасць гэтага алгарытму просты індукцыі,

156
00:10:43,610 --> 00:10:49,540
дзе ваша індукцыі бы, выкажам здагадку, што

157
00:10:49,540 --> 00:10:53,290
мой выпадковым парадку вяртае ўсе перастаноўкі равновероятны

158
00:10:53,290 --> 00:10:56,120
да першага элемента я.

159
00:10:56,120 --> 00:10:58,300
Зараз разгледзім + 1.

160
00:10:58,300 --> 00:11:02,550
І, дарэчы, мы выбіраем нашых індэксаў J, каб памяняць,

161
00:11:02,550 --> 00:11:05,230
гэта прыводзіць да - і тады вы прапрацаваць дэталі,

162
00:11:05,230 --> 00:11:07,390
па крайняй меры, поўнае доказ таго, чаму гэты алгарытм вяртаецца

163
00:11:07,390 --> 00:11:12,800
кожная перастаноўка з роўнай верагоднасцю верагоднасці.

164
00:11:12,800 --> 00:11:15,940
>> Добра, наступная праблема.

165
00:11:15,940 --> 00:11:19,170
Так што "гэты масіў цэлых лікаў, Postive, нулявы, адмоўны,

166
00:11:19,170 --> 00:11:21,290
напісаць функцыю, якая вылічае максімальную суму

167
00:11:21,290 --> 00:11:24,720
любой continueous подмассива ўваходны масіў ".

168
00:11:24,720 --> 00:11:28,370
Напрыклад вось, у выпадку, калі ўсе лікі станоўчыя,

169
00:11:28,370 --> 00:11:31,320
то ў цяперашні час лепшы выбар гэта ўзяць увесь масіў.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, роўна 10.

171
00:11:34,690 --> 00:11:36,780
Калі ў вас ёсць некаторыя негатывы там,

172
00:11:36,780 --> 00:11:38,690
У гэтым выпадку мы проста хочам першых двух

173
00:11:38,690 --> 00:11:44,590
таму што выбар -1 і / або -3 прынясе нашым сума ўніз.

174
00:11:44,590 --> 00:11:48,120
Часам мы, магчыма, прыйдзецца пачаць у сярэдзіне масіва.

175
00:11:48,120 --> 00:11:53,500
Часам мы хочам выбраць наогул нічога, то лепш не браць.

176
00:11:53,500 --> 00:11:56,490
І часам лепш прыняць восенню,

177
00:11:56,490 --> 00:12:07,510
таму што рэч пасля таго, як гэта супер вялікі. Такім чынам, любыя ідэі?

178
00:12:07,510 --> 00:12:10,970
(Студэнт, незразумелыя) >> Так.

179
00:12:10,970 --> 00:12:13,560
Няхай я не бяру -1.

180
00:12:13,560 --> 00:12:16,170
Тады альбо я выбіраю 1000 і 20000,

181
00:12:16,170 --> 00:12:18,630
ці я проста абраць 3 млрд. даляраў.

182
00:12:18,630 --> 00:12:20,760
Ну, лепшым выбарам будзе прымаць усе лічбы.

183
00:12:20,760 --> 00:12:24,350
Гэта -1, нягледзячы на ​​тое адмоўнае,

184
00:12:24,350 --> 00:12:31,340
Уся сума лепш, чым калі б я не прымаць -1.

185
00:12:31,340 --> 00:12:36,460
Такім чынам, адзін з саветаў я згадваў раней быў заявіць ясна відавочна,

186
00:12:36,460 --> 00:12:40,540
і грубай сіле рашэнне першай.

187
00:12:40,540 --> 00:12:44,340
Што такое грубай сілы ў вырашэнні гэтай праблемы? Да?

188
00:12:44,340 --> 00:12:46,890
[Джэйн] Ну, я думаю, што грубай сіле рашэнне

189
00:12:46,890 --> 00:12:52,600
можна было б дадаць ўсе магчымыя камбінацыі (неразборліва).

190
00:12:52,600 --> 00:12:58,250
[П] Добра. Такім чынам, ідэя Джэйн прыняць усе магчымыя -

191
00:12:58,250 --> 00:13:01,470
Я Перафразую - гэта прыняць усе магчымыя бесперапыннай подмассива,

192
00:13:01,470 --> 00:13:07,840
вылічыць яго суму, а затым ўзяць максімальнае з усіх магчымых бесперапынных подмассивов.

193
00:13:07,840 --> 00:13:13,310
Што адназначна ідэнтыфікуе подмассива ў маёй ўваходны масіў?

194
00:13:13,310 --> 00:13:17,380
Як і тое, што дзве рэчы мне патрэбныя? Да?

195
00:13:17,380 --> 00:13:19,970
(Студэнт, незразумелыя) >> праве.

196
00:13:19,970 --> 00:13:22,130
Ніжняя мяжа індэксаў і верхняя мяжа індэкса

197
00:13:22,130 --> 00:13:28,300
адназначна вызначае бесперапынную подмассива.

198
00:13:28,300 --> 00:13:31,400
[Студэнтка] Ці мы ацаніць гэта масіў унікальных нумароў?

199
00:13:31,400 --> 00:13:34,280
[П] Няма Таму яе пытанне, мы мяркуючы, наш масіў -

200
00:13:34,280 --> 00:13:39,000
Наша масіва ўсе унікальныя нумары, а адказу няма.

201
00:13:39,000 --> 00:13:43,390
>> Калі мы выкарыстоўваем нашу грубую сілу рашэнне, то пачатак / канец індэксаў

202
00:13:43,390 --> 00:13:47,200
адназначна вызначае нашы пастаянныя подмассива.

203
00:13:47,200 --> 00:13:51,680
Таму, калі мы перабору ўсіх магчымых запісаў пачатку,

204
00:13:51,680 --> 00:13:58,320
і для ўсіх канчатковых элементаў> ці =, каб пачаць, і <п,

205
00:13:58,320 --> 00:14:05,570
Вы можаце вылічыць суму, а затым ўзяць максімальную суму, што мы бачылі да гэтага часу.

206
00:14:05,570 --> 00:14:07,880
Гэта зразумела?

207
00:14:07,880 --> 00:14:12,230
Што такое вялікае Аб ад гэтага рашэння?

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

209
00:14:16,660 --> 00:14:18,860
Не зусім N ^ 2.

210
00:14:18,860 --> 00:14:25,250
Звярніце ўвагу, што мы ітэрацыі ад 0 да п,

211
00:14:25,250 --> 00:14:27,520
так што адна цыклу.

212
00:14:27,520 --> 00:14:35,120
Мы зноў паўтараць практычна з пачатку і да канца, іншага цыклу.

213
00:14:35,120 --> 00:14:37,640
І зараз, у тым, што мы павінны падвесці вынікі кожнага ўваходу,

214
00:14:37,640 --> 00:14:43,810
так што гэта яшчэ адзін цыкл. Такім чынам, мы маем тры укладзеныя цыклы, п ^ 3.

215
00:14:43,810 --> 00:14:46,560
Добра. Гэта ідзе ў якасці адпраўной кропкі.

216
00:14:46,560 --> 00:14:53,180
Наша рашэнне не горш, чым п ^ 3.

217
00:14:53,180 --> 00:14:55,480
Ці ўсё разумеюць грубую сілу рашэнне?

218
00:14:55,480 --> 00:14:59,950
>> Добра. Лепшым рашэннем з'яўляецца выкарыстанне ідэі называюць дынамічным праграмаваннем.

219
00:14:59,950 --> 00:15:03,040
Калі ўзяць CS124, якая алгарытмы і структуры дадзеных,

220
00:15:03,040 --> 00:15:05,680
Вы станеце вельмі добра знаёмыя з гэтай тэхнікай.

221
00:15:05,680 --> 00:15:12,190
І ідэя, паспрабаваць стварыць рашэнні для меншых праблем у першую чаргу.

222
00:15:12,190 --> 00:15:17,990
Што я маю на ўвазе, мы ў цяперашні час не прыйдзецца турбавацца пра дзве рэчы: пачатак і канец.

223
00:15:17,990 --> 00:15:29,340
І гэта раздражняе. Што калі б мы маглі пазбавіцца ад аднаго з гэтых параметраў?

224
00:15:29,340 --> 00:15:32,650
Адна з ідэй складаецца - we're улічваючы нашу зыходную задачу,

225
00:15:32,650 --> 00:15:37,470
знайсці максімальную суму любых подмассива ў дыяпазоне [О, N-1].

226
00:15:37,470 --> 00:15:47,400
І зараз у нас ёсць новы подзадачи, дзе мы ведаем, у нашай бягучай індэкс г,

227
00:15:47,400 --> 00:15:52,520
Мы ведаем, што мы павінны заключыць там. Нашы подмассива павінны заканчвацца на бягучы індэкс.

228
00:15:52,520 --> 00:15:57,640
Такім чынам, што засталася, праблема ў тым, дзе мы павінны пачаць наш подмассива?

229
00:15:57,640 --> 00:16:05,160
Ці мае гэта сэнс? Добра.

230
00:16:05,160 --> 00:16:12,030
Так што я закадаваны ад гэтага, і давайце паглядзім, што гэта азначае.

231
00:16:12,030 --> 00:16:16,230
У codirectory, ёсць праграма пад назвай подмассива,

232
00:16:16,230 --> 00:16:19,470
і ён прымае лік элементаў,

233
00:16:19,470 --> 00:16:25,550
і вяртае максімальную суму подмассива ў маім спісе змешваюцца.

234
00:16:25,550 --> 00:16:29,920
Такім чынам, у гэтым выпадку, наш максімальны подмассива роўны 3.

235
00:16:29,920 --> 00:16:34,850
І гэта прымаць толькі з дапамогай 2 і 1.

236
00:16:34,850 --> 00:16:38,050
Давайце запусцім яго зноў. Гэта таксама 3.

237
00:16:38,050 --> 00:16:40,950
Але на гэты раз, звярніце ўвагу, як мы атрымалі 3.

238
00:16:40,950 --> 00:16:46,690
Мы ўзялі - мы проста возьмем 3-сам

239
00:16:46,690 --> 00:16:49,980
таму што ён акружаны негатываў з абодвух бакоў,

240
00:16:49,980 --> 00:16:55,080
які прынясе суму <3.

241
00:16:55,080 --> 00:16:57,820
Давайце працаваць на 10 пунктаў.

242
00:16:57,820 --> 00:17:03,200
На гэты раз гэта 7, заняць лідзіруючыя 3 і 4.

243
00:17:03,200 --> 00:17:09,450
На гэты раз гэта 8, і мы атрымліваем, што, прымаючы 1, 4 і 3.

244
00:17:09,450 --> 00:17:16,310
Такім чынам, каб даць вам інтуіцыя аб тым, як мы можам вырашыць гэтую ператвараецца праблемы,

245
00:17:16,310 --> 00:17:18,890
Давайце зірнем на гэтую подмассива.

246
00:17:18,890 --> 00:17:23,460
Мы дадзена гэта ўваходны масіў, і мы ведаем адказ на гэтае пытанне 8.

247
00:17:23,460 --> 00:17:26,359
Мы бярэм 1, 4 і 3.

248
00:17:26,359 --> 00:17:29,090
Але давайце паглядзім на тое, як мы на самай справе ёсць, што адказаць.

249
00:17:29,090 --> 00:17:34,160
Давайце паглядзім на максімальнай подмассива, які скончыўся на кожны з гэтых паказчыкаў.

250
00:17:34,160 --> 00:17:40,780
Які максімальны подмассива, які павінен скончыцца на першай пазіцыі?

251
00:17:40,780 --> 00:17:46,310
[Студэнт] Zero. >> Zero. Толькі не прымайце -5.

252
00:17:46,310 --> 00:17:50,210
Вось гэта будзе мець значэнне 0, а таксама. Да?

253
00:17:50,210 --> 00:17:56,470
(Студэнт, незразумелыя)

254
00:17:56,470 --> 00:17:58,960
[П] Эх, шкада, што гэта -3.

255
00:17:58,960 --> 00:18:03,220
Такім чынам, гэта 2, гэта -3.

256
00:18:03,220 --> 00:18:08,690
Добра. Такім чынам, -4, што максімальная подмассива да канца, што становішча

257
00:18:08,690 --> 00:18:12,910
-4, Дзе знаходзіцца? Zero.

258
00:18:12,910 --> 00:18:22,570
Адзін? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
Цяпер, я павінен заканчвацца ў тым месцы, дзе -2 знаходзіцца.

260
00:18:28,060 --> 00:18:39,330
Такім чынам, 6, 5, 7, а апошні роўны 4.

261
00:18:39,330 --> 00:18:43,480
Ведаючы, што гэтыя мае запісы

262
00:18:43,480 --> 00:18:48,130
для ператворанай задачы, дзе я павінен заканчвацца на кожны з гэтых паказчыкаў,

263
00:18:48,130 --> 00:18:51,410
Затым мой канчатковы адказ проста, узяць разгорткі па гарызанталі,

264
00:18:51,410 --> 00:18:53,580
і ўзяць максімальнае колькасць.

265
00:18:53,580 --> 00:18:55,620
Такім чынам, у дадзеным выпадку гэта 8.

266
00:18:55,620 --> 00:19:00,010
Гэта азначае, што максімальная подмассива заканчваецца ў гэтым індэксе,

267
00:19:00,010 --> 00:19:04,970
і пачаў дзесьці перад ім.

268
00:19:04,970 --> 00:19:09,630
Ці ўсё разумеюць гэта ператвараецца подмассива?

269
00:19:09,630 --> 00:19:22,160
>> Добра. Ну, давайце высвятляць паўтарэння гэтага.

270
00:19:22,160 --> 00:19:27,990
Давайце разгледзім толькі першыя некалькі запісаў.

271
00:19:27,990 --> 00:19:35,930
Дык вось гэта была 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
А потым было -2 тут, і якія прывялі яго да 6.

273
00:19:39,790 --> 00:19:50,800
Так што, калі я называю ўступлення ў пасаду я подзадача (I),

274
00:19:50,800 --> 00:19:54,910
як я магу выкарыстоўваць адказе на папярэдні подзадачи

275
00:19:54,910 --> 00:19:59,360
Для адказу на гэтае подзадачи?

276
00:19:59,360 --> 00:20:04,550
Калі я гляджу на, скажам, гэты запіс.

277
00:20:04,550 --> 00:20:09,190
Як я магу вылічыць адказ 6, гледзячы на

278
00:20:09,190 --> 00:20:18,780
Спалучэнне гэтага масіва і адказаў на папярэднія подзадач ў гэтым масіве? Да?

279
00:20:18,780 --> 00:20:22,800
[Студэнтка] Ты масіве сум

280
00:20:22,800 --> 00:20:25,430
у становішча прама перад ёй, так што 8,

281
00:20:25,430 --> 00:20:32,170
а затым дадаць бягучую подзадачи.

282
00:20:32,170 --> 00:20:36,460
[П] Так ёй прапанову паглядзець на гэтыя два ліку,

283
00:20:36,460 --> 00:20:40,090
гэты лік, і гэта лік.

284
00:20:40,090 --> 00:20:50,130
Такім чынам, гэта 8 ставіцца да адказам на подзадачи (я - 1).

285
00:20:50,130 --> 00:20:57,300
І давайце называць майго уваходнага масіва A.

286
00:20:57,300 --> 00:21:01,470
Для таго каб знайсці максімальны подмассива, які заканчваецца ў пазіцыі I,

287
00:21:01,470 --> 00:21:03,980
У мяне ёсць два варыянты: я магу альбо працягнуць подмассива

288
00:21:03,980 --> 00:21:09,790
, Якая скончылася ў папярэдні індэкс, або пачаць новую масіва.

289
00:21:09,790 --> 00:21:14,190
Калі б я быў працягнуць подмассива, які пачаўся ў папярэдні індэкс,

290
00:21:14,190 --> 00:21:19,260
Затым максімальную суму я магу дасягнуць, гэта адказ на папярэдні подзадачи

291
00:21:19,260 --> 00:21:24,120
плюс бягучы элемент масіва.

292
00:21:24,120 --> 00:21:27,550
Але, у мяне ёсць выбар, пачынаючы новы подмассива,

293
00:21:27,550 --> 00:21:30,830
У гэтым выпадку сума роўная 0.

294
00:21:30,830 --> 00:21:42,860
Так што адказ макс 0, подзадача - 1, а таксама бягучы элемент масіва.

295
00:21:42,860 --> 00:21:46,150
Ці азначае гэта паўтор сэнсу?

296
00:21:46,150 --> 00:21:50,840
Нашы рэцыдыву, як мы толькі што выявілі, гэта я подзадача

297
00:21:50,840 --> 00:21:54,740
роўны максімуме папярэдняга подзадачи плюс мой бягучы элемент масіва,

298
00:21:54,740 --> 00:22:01,490
што азначае працяг папярэдняй подмассива,

299
00:22:01,490 --> 00:22:07,250
або 0, стварыць новую подмассива на мой бягучы індэкс.

300
00:22:07,250 --> 00:22:10,060
І як толькі мы стварылі гэтую табліцу рашэнняў, то наш канчатковы адказ,

301
00:22:10,060 --> 00:22:13,950
проста рабіць лінейныя разгорткі праз подзадачи масіва

302
00:22:13,950 --> 00:22:19,890
і ўзяць максімальнае колькасць.

303
00:22:19,890 --> 00:22:23,330
Гэта дакладная рэалізацыя таго, што я толькі што сказаў.

304
00:22:23,330 --> 00:22:27,320
Такім чынам, мы ствараем новы масіў подзадачи, подзадачи.

305
00:22:27,320 --> 00:22:32,330
Першая запіс альбо 0, альбо першы запіс, максімальнае з гэтых двух.

306
00:22:32,330 --> 00:22:35,670
А для астатніх подзадач

307
00:22:35,670 --> 00:22:39,810
мы выкарыстоўваем дакладнае паўтарэнне Мы толькі што выявілі.

308
00:22:39,810 --> 00:22:49,960
Цяпер вылічым максімальную нашага масіва подзадач, і гэта наш канчатковы адказ.

309
00:22:49,960 --> 00:22:54,130
>> Так колькі месца мы выкарыстоўваем у гэтым алгарытме?

310
00:22:54,130 --> 00:23:01,470
Калі вы толькі прымаць CS50, то вы не маглі б абмяркоўвацца прасторы вельмі шмат.

311
00:23:01,470 --> 00:23:07,750
Ну, адно варта адзначыць, што я назваў таНос тут з памерам п.

312
00:23:07,750 --> 00:23:13,590
Што гэта прапанаваць вам?

313
00:23:13,590 --> 00:23:17,450
Гэты алгарытм выкарыстоўвае лінейнае прастору.

314
00:23:17,450 --> 00:23:21,030
Ці можам мы зрабіць лепш?

315
00:23:21,030 --> 00:23:30,780
Ёсць што-небудзь, што вы заўважыце, што з'яўляецца неабходным для вылічэнні канчатковы адказ?

316
00:23:30,780 --> 00:23:33,290
Я думаю, лепш Пытанне ў тым, якая інфармацыя

317
00:23:33,290 --> 00:23:40,680
мы не павінны несці ўвесь шлях да канца?

318
00:23:40,680 --> 00:23:44,280
Цяпер, калі мы паглядзім на гэтыя дзве лініі,

319
00:23:44,280 --> 00:23:47,720
мы клапоцімся толькі пра папярэднюю подзадачи,

320
00:23:47,720 --> 00:23:50,910
і мы клапоцімся толькі пра максімальнай якія мы калі-небудзь бачылі да гэтага часу.

321
00:23:50,910 --> 00:23:53,610
Каб вылічыць наш канчатковы адказ, нам не трэба ўвесь масіў.

322
00:23:53,610 --> 00:23:57,450
Нам трэба толькі апошні нумар, дзве апошнія лічбы.

323
00:23:57,450 --> 00:24:02,630
Апошні нумар подзадачи масіва, а апошні нумар максімуму.

324
00:24:02,630 --> 00:24:07,380
Так, на самай справе, мы можам злучыць гэтыя завесы разам

325
00:24:07,380 --> 00:24:10,460
і перайсці ад лінейнага прасторы пастаяннай прасторы.

326
00:24:10,460 --> 00:24:15,830
Дадзенай сумы да гэтага часу, тут замяняе ролю подзадачи, нашы подзадачи масіва.

327
00:24:15,830 --> 00:24:20,020
Такім чынам, бягучая сума, да гэтага часу, з'яўляецца адказам на папярэдні подзадачи.

328
00:24:20,020 --> 00:24:23,450
І гэтая сума да гэтага часу займае месца нашага макс.

329
00:24:23,450 --> 00:24:28,100
Мы вылічым максімальную, як мы ідзем разам.

330
00:24:28,100 --> 00:24:30,890
І вось мы ідзём ад лінейнага прасторы пастаяннай прасторы,

331
00:24:30,890 --> 00:24:36,650
і мы таксама маем лінейнае рашэнне нашых подмассива праблемы.

332
00:24:36,650 --> 00:24:40,740
>> Гэтыя пытанні вы атрымаеце падчас інтэрв'ю.

333
00:24:40,740 --> 00:24:44,450
Якая часовая складанасць, што прастора складанасці?

334
00:24:44,450 --> 00:24:50,600
Ці можаце вы зрабіць лепш? Ёсць рэчы, якія не з'яўляюцца неабходнымі, каб трымаць вакол?

335
00:24:50,600 --> 00:24:55,270
Я зрабіў гэта, каб вылучыць аналізаў, якія вы павінны прыняць на свой уласны

336
00:24:55,270 --> 00:24:57,400
як вы працуеце праз гэтыя праблемы.

337
00:24:57,400 --> 00:25:01,710
Заўсёды можна спытаць сябе: "Ці магу я зрабіць лепш?"

338
00:25:01,710 --> 00:25:07,800
На самай справе, мы можам зрабіць лепш, чым гэта?

339
00:25:07,800 --> 00:25:10,730
Сартаваць пытанне з падвохам. Вы не можаце, таму што вы павінны

340
00:25:10,730 --> 00:25:13,590
па крайняй меры чытаць ўклад у праблему.

341
00:25:13,590 --> 00:25:15,570
Таму той факт, што вам трэба па крайняй меры чытаць ўклад у праблемы

342
00:25:15,570 --> 00:25:19,580
азначае, што вы не можаце зрабіць лепш, чым лінейнае час,

343
00:25:19,580 --> 00:25:22,870
і вы не можаце зрабіць лепш, чым пастаяннае месца.

344
00:25:22,870 --> 00:25:27,060
Так што гэта, на самой справе, лепшае рашэнне гэтай праблемы.

345
00:25:27,060 --> 00:25:33,040
Пытанні? Добра.

346
00:25:33,040 --> 00:25:35,190
>> Праблема Фондавы рынак:

347
00:25:35,190 --> 00:25:38,350
"Улічваючы масіў цэлых лікаў п, станоўчай, нулявы або адмоўнай,

348
00:25:38,350 --> 00:25:41,680
, Якія ўяўляюць сабой цану акцыі на працягу некалькіх дзён п,

349
00:25:41,680 --> 00:25:44,080
напісаць функцыю для вылічэння максімальнай прыбытку вы можаце зрабіць

350
00:25:44,080 --> 00:25:49,350
пры ўмове, што вы купляеце і прадаеце роўна 1 акцыя ў рамках гэтых п дзён ".

351
00:25:49,350 --> 00:25:51,690
Па сутнасці, мы хочам купіць танна, прадавай дорага.

352
00:25:51,690 --> 00:25:58,580
І мы хочам, каб высветліць, лепшы прыбытку мы можам зрабіць.

353
00:25:58,580 --> 00:26:11,500
Вяртаючыся да маёй наканечнікам, што адразу ясна, просты адказ, але гэта павольна?

354
00:26:11,500 --> 00:26:17,690
Да? (Студэнт, незразумелыя) >> Так.

355
00:26:17,690 --> 00:26:21,470
>> Так вы б проста пайсці, хоць і паглядзіце на цэны акцый

356
00:26:21,470 --> 00:26:30,550
у кожны момант часу, (неразборліва).

357
00:26:30,550 --> 00:26:33,990
[П] Добра, так што яе рашэнне - яе прапанову вылічальных

358
00:26:33,990 --> 00:26:37,380
самыя нізкія і самыя высокія вылічэнні не абавязкова працаваць

359
00:26:37,380 --> 00:26:42,470
таму што высокая можа адбыцца да самых нізкіх.

360
00:26:42,470 --> 00:26:47,340
Так што гэта грубая сіла рашэння гэтай праблемы?

361
00:26:47,340 --> 00:26:53,150
Якія дзве рэчы, якія мне трэба, каб адназначна вызначыць прыбытак я магу зрабіць? Права.

362
00:26:53,150 --> 00:26:59,410
Рашэнне грубай сілы - о, так, прапанова Джорджа гэта нам трэба толькі два дні

363
00:26:59,410 --> 00:27:02,880
для адназначнага вызначэння прыбытку гэтыя два дні.

364
00:27:02,880 --> 00:27:06,660
Такім чынам, мы вылічым кожнай пары, як купля / продаж,

365
00:27:06,660 --> 00:27:12,850
вылічыць прыбытак, якая можа быць станоўчым або адмоўным або нулявым.

366
00:27:12,850 --> 00:27:18,000
Вылічыць максімальны прыбытак, што мы робім пасля перабірае ўсе пары дзён.

367
00:27:18,000 --> 00:27:20,330
Гэта будзе наш канчатковы адказ.

368
00:27:20,330 --> 00:27:25,730
І гэтае рашэнне будзе O (N ^ 2), таму што існуе п выбраць дзве пары -

369
00:27:25,730 --> 00:27:30,270
дзён, якія вы можаце выбіраць паміж канца дня.

370
00:27:30,270 --> 00:27:32,580
Добра, так што я не збіраюся перайсці на грубай сіле рашэнне тут.

371
00:27:32,580 --> 00:27:37,420
Я збіраюся расказаць вам, што ёсць п § п рашэнне.

372
00:27:37,420 --> 00:27:45,550
Які алгарытм ў цяперашні час вы ведаеце, што гэта п § п?

373
00:27:45,550 --> 00:27:50,730
Гэта не пытанне з падвохам.

374
00:27:50,730 --> 00:27:54,790
>> Зліццё роду. Зліццё роду п § п,

375
00:27:54,790 --> 00:27:57,760
і на самай справе, адным з спосабаў вырашэння гэтай праблемы з'яўляецца выкарыстанне

376
00:27:57,760 --> 00:28:04,400
свайго роду зліццё роду ідэя называецца, у агульным, падзяляй і ўладар.

377
00:28:04,400 --> 00:28:07,570
А ідэя заключаецца ў наступным.

378
00:28:07,570 --> 00:28:12,400
Вы хочаце, каб вылічыць аптымальную куплі / продажу пары ў левай палове.

379
00:28:12,400 --> 00:28:16,480
Знайсці лепшы прыбытку вы можаце зрабіць, толькі з першай рускай працягу двух дзён.

380
00:28:16,480 --> 00:28:19,780
Затым вы хочаце oompute лепшыя куплі / продажу пары на правай палове,

381
00:28:19,780 --> 00:28:23,930
так што апошнія п працягу двух дзён.

382
00:28:23,930 --> 00:28:32,400
А зараз пытанне ў тым, як мы можам аб'яднаць гэтыя рашэнні разам?

383
00:28:32,400 --> 00:28:36,320
Да? (Студэнт, незразумелыя)

384
00:28:36,320 --> 00:28:49,890
>> Добра. Такім чынам, дазвольце мне намаляваць карцінку.

385
00:28:49,890 --> 00:29:03,870
Да? (Джордж, незразумелыя)

386
00:29:03,870 --> 00:29:06,450
>> Менавіта так. Рашэнне Джорджа гэта зусім дакладна.

387
00:29:06,450 --> 00:29:10,040
Так што яго прапанова з'яўляецца, у першую вылічыць аптымальную куплю / продаж пары,

388
00:29:10,040 --> 00:29:16,050
і што адбываецца ў левай палове, так што давайце называць гэта левы, левы.

389
00:29:16,050 --> 00:29:20,790
Лепшая купля / продаж пара, якая адбываецца ў правай палове.

390
00:29:20,790 --> 00:29:25,180
Але калі мы толькі па параўнанні гэтых двух лікаў, мы прапусцілі выпадак

391
00:29:25,180 --> 00:29:30,460
дзе купіць тут і прадаць дзесьці ў правай палове.

392
00:29:30,460 --> 00:29:33,810
Мы купляем у левай палове, продажу ў правай палове.

393
00:29:33,810 --> 00:29:38,490
І лепшы спосаб вылічыць аптымальную купіць / прадаць пару, якая ахоплівае абедзве палоўкі

394
00:29:38,490 --> 00:29:43,480
з'яўляецца вылічэнне мінімальнага тут і вылічыць максімальнае тут

395
00:29:43,480 --> 00:29:45,580
і ўзяць іх рознасць.

396
00:29:45,580 --> 00:29:50,850
Такім чынам, два выпадкі, калі куплі / продажу пары адбываецца толькі тут,

397
00:29:50,850 --> 00:30:01,910
Толькі тут, ці на абедзвюх палавінах вызначаецца гэтымі трыма лікамі.

398
00:30:01,910 --> 00:30:06,450
Такім чынам, наш алгарытм аб'яднаць нашы рашэнні разам,

399
00:30:06,450 --> 00:30:08,350
Мы хочам вылічыць аптымальную куплю / продаж пары

400
00:30:08,350 --> 00:30:13,120
дзе мы купляем на левай палове і прадаваць на правай палове.

401
00:30:13,120 --> 00:30:16,740
І лепшы спосаб зрабіць гэта складаецца ў вылічэнні самай нізкай цане ў першай палове,

402
00:30:16,740 --> 00:30:20,360
самая высокая цана ў правай палове, і ўзяць іх рознасць.

403
00:30:20,360 --> 00:30:25,390
Атрыманыя 3 прыбытак, гэтыя тры лічбы, вы бераце максімум тры,

404
00:30:25,390 --> 00:30:32,720
і гэта лепшая прыбытак вы можаце зрабіць за гэтыя першыя і канца дзён.

405
00:30:32,720 --> 00:30:36,940
Тут важныя лініі чырвонага колеру.

406
00:30:36,940 --> 00:30:41,160
Гэта рэкурсіўны выклік для вылічэнні адказу ў левай палове.

407
00:30:41,160 --> 00:30:44,760
Гэта рэкурсіўны выклік для вылічэнні адказу ў правай палове.

408
00:30:44,760 --> 00:30:50,720
Гэтыя дзве завесы для вылічэнні мін і макс на левую і правую паловы, адпаведна.

409
00:30:50,720 --> 00:30:54,970
Цяпер я вылічыць прыбытак, якая ахоплівае абедзве палоўкі,

410
00:30:54,970 --> 00:31:00,530
і канчатковы адказ максімальная з гэтых трох.

411
00:31:00,530 --> 00:31:04,120
Добра.

412
00:31:04,120 --> 00:31:06,420
>> Так што, упэўнены, у нас ёсць алгарытм, але больш за пытанне ў тым,

413
00:31:06,420 --> 00:31:08,290
што часовая складанасць гэтага?

414
00:31:08,290 --> 00:31:16,190
І прычына, чаму я згадаў, сартаванне зліццём у тым, што гэтая форма падзяліць адказ

415
00:31:16,190 --> 00:31:19,200
на два, а затым аб'ядноўваць нашы рашэнні разам

416
00:31:19,200 --> 00:31:23,580
Менавіта выгляд сартавання зліццём.

417
00:31:23,580 --> 00:31:33,360
Такім чынам, дазвольце мне прайсці працягласці.

418
00:31:33,360 --> 00:31:41,340
Калі мы вызначылі функцыю T (N), што колькасць крокаў

419
00:31:41,340 --> 00:31:50,010
для п дзён,

420
00:31:50,010 --> 00:31:54,350
нашы рэкурсіўнага выклікі

421
00:31:54,350 --> 00:32:00,460
кожны будзе каштаваць т (п / 2),

422
00:32:00,460 --> 00:32:03,540
і ёсць два з гэтых выклікаў.

423
00:32:03,540 --> 00:32:10,020
Цяпер мне трэба вылічыць мінімум левай палове,

424
00:32:10,020 --> 00:32:17,050
які я магу зрабіць у п / 2, плюс максімум у правай палове.

425
00:32:17,050 --> 00:32:20,820
Так што гэта проста п.

426
00:32:20,820 --> 00:32:25,050
А потым плюс некаторая пастаянная праца.

427
00:32:25,050 --> 00:32:27,770
І гэта рэкурэнтнага раўнанне

428
00:32:27,770 --> 00:32:35,560
Менавіта рэкурэнтнага раўнанне для сартавання зліццём.

429
00:32:35,560 --> 00:32:39,170
І ўсе мы ведаем, што сартаванне зліццём п § п часу.

430
00:32:39,170 --> 00:32:46,880
Такім чынам, наш алгарытм таксама п § п часу.

431
00:32:46,880 --> 00:32:52,220
Ці значыць гэта, ітэрацыі сэнс?

432
00:32:52,220 --> 00:32:55,780
Толькі кароткае рэзюмэ гэтага:

433
00:32:55,780 --> 00:32:59,170
Т (п) з'яўляецца шэраг крокаў, каб вылічыць максімальны прыбытак

434
00:32:59,170 --> 00:33:02,750
на працягу сутак з.

435
00:33:02,750 --> 00:33:06,010
Тое, як мы падзяліліся нашы рэкурсіўнага выклікі

436
00:33:06,010 --> 00:33:11,980
з'яўляецца выклікам нашага рашэння ў першыя дні п / 2,

437
00:33:11,980 --> 00:33:14,490
так што гэта адзін выклік,

438
00:33:14,490 --> 00:33:16,940
а потым мы зноў заклікаем другой паловы.

439
00:33:16,940 --> 00:33:20,440
Дык вось двума выклікамі.

440
00:33:20,440 --> 00:33:25,310
І тады мы знаходзім мінімум на левай палове, якую мы можам зрабіць у лінейным часу,

441
00:33:25,310 --> 00:33:29,010
знайсці максімум у правай палове, якую мы можам зрабіць у лінейным часу.

442
00:33:29,010 --> 00:33:31,570
Такім чынам, п / 2 + п / 2 знаходзіцца за ўсё ў с.

443
00:33:31,570 --> 00:33:36,020
Тады ў нас ёсць пастаянная праца, якая, як рабіць арыфметыку.

444
00:33:36,020 --> 00:33:39,860
Гэта рэкурэнтнага раўнанне ў дакладнасці паўтарэння раўнанні для сартавання зліццём.

445
00:33:39,860 --> 00:33:55,490
Такім чынам, наш алгарытм мяшання таксама п п ўвайсці.

446
00:33:55,490 --> 00:33:58,520
Так колькі месца мы выкарыстоўваем?

447
00:33:58,520 --> 00:34:04,910
Давайце вернемся да коду.

448
00:34:04,910 --> 00:34:09,420
>> Лепшы пытанне, колькі кадраў стэка мы калі-небудзь у любы момант?

449
00:34:09,420 --> 00:34:11,449
Так як мы выкарыстоўваем рэкурсіі,

450
00:34:11,449 --> 00:34:23,530
колькасць кадраў стэка вызначае наша выкарыстанне прасторы.

451
00:34:23,530 --> 00:34:29,440
Разгледзім N = 8.

452
00:34:29,440 --> 00:34:36,889
Мы заклікаем змяшаць 8,

453
00:34:36,889 --> 00:34:41,580
, Які будзе выклікаць выпадковым парадку на першых чатырох запісаў,

454
00:34:41,580 --> 00:34:46,250
, Які будзе выклікаць перамешванне на першых двух запісаў.

455
00:34:46,250 --> 00:34:51,550
Такім чынам, наш стэк - гэта наш стэк.

456
00:34:51,550 --> 00:34:54,980
І тады мы называем змяшаць яшчэ раз на 1,

457
00:34:54,980 --> 00:34:58,070
і гэта тое, што наша база выпадак, таму мы неадкладна вярнуцца.

458
00:34:58,070 --> 00:35:04,700
Ці ёсць у нас калі-небудзь больш, чым гэта колькасць кадраў стэка?

459
00:35:04,700 --> 00:35:08,880
Не, таму што кожны раз, калі мы робім выклік,

460
00:35:08,880 --> 00:35:10,770
рэкурсіўны выклік для мяшання,

461
00:35:10,770 --> 00:35:13,950
мы дзелім нашу памерам у палову.

462
00:35:13,950 --> 00:35:17,020
Такім чынам, максімальны лік кадраў стэка мы калі-небудзь у любы момант

463
00:35:17,020 --> 00:35:28,460
парадку часопіса N кадраў стэка.

464
00:35:28,460 --> 00:35:42,460
Кожны кадр стэка мае пастаяннае месца,

465
00:35:42,460 --> 00:35:44,410
і, такім чынам, агульны аб'ём прасторы,

466
00:35:44,410 --> 00:35:49,240
максімальны аб'ём прасторы, мы калі-небудзь выкарыстоўваць гэта O (часопіс N) прасторы

467
00:35:49,240 --> 00:36:03,040
дзе п-колькасць дзён.

468
00:36:03,040 --> 00:36:07,230
>> Цяпер, заўсёды пытайце сябе: "Ці можам мы зрабіць лепш?"

469
00:36:07,230 --> 00:36:12,390
І ў прыватнасці, мы можам скараціць гэтую праблему мы ўжо вырашылі?

470
00:36:12,390 --> 00:36:20,040
Падказка: мы толькі абмяркоўвалі два іншых праблем да гэтага, і ён не збіраецца быць змяшаць.

471
00:36:20,040 --> 00:36:26,200
Мы можам пераўтварыць гэтую праблему фондавага рынку ў максімальнай праблемы подмассива.

472
00:36:26,200 --> 00:36:40,100
Як мы можам гэта зрабіць?

473
00:36:40,100 --> 00:36:42,570
Адзін з вас? Эмі?

474
00:36:42,570 --> 00:36:47,680
(Emmy, незразумелыя)

475
00:36:47,680 --> 00:36:53,860
[П] Менавіта так.

476
00:36:53,860 --> 00:36:59,940
Такім чынам, максімальная подмассива праблемы,

477
00:36:59,940 --> 00:37:10,610
Мы шукаем сума па бесперапыннай подмассива.

478
00:37:10,610 --> 00:37:16,230
І прапанова Эмі задачы акцыі,

479
00:37:16,230 --> 00:37:30,720
Разгледзім змены, або дэльты.

480
00:37:30,720 --> 00:37:37,440
І карціна гэтая ёсць - гэта кошт акцыі,

481
00:37:37,440 --> 00:37:42,610
але калі б мы ўзялі розніцу паміж кожным дзень запар -

482
00:37:42,610 --> 00:37:45,200
Такім чынам, мы бачым, што максімальная цана, максімальная прыбытак мы маглі б зрабіць

483
00:37:45,200 --> 00:37:50,070
, Калі мы купляем і прадаем тут тут.

484
00:37:50,070 --> 00:37:54,240
Але давайце паглядзім на бесперапыннае - давайце паглядзім на подмассива праблемы.

485
00:37:54,240 --> 00:38:02,510
Дык вось, мы можам зрабіць - адбываецца ад гэтага да гэтага,

486
00:38:02,510 --> 00:38:08,410
у нас ёсць пазітыўныя змены, а затым збіраецца адсюль тут мы маем адмоўнае змена.

487
00:38:08,410 --> 00:38:14,220
Але тады, пераходзячы ад сюды, каб тут мы маем велізарнае станоўчае змяненне.

488
00:38:14,220 --> 00:38:20,930
І гэтыя змены, якія мы хочам падвесці вынікі, каб атрымаць нашу канчатковую прыбытак.

489
00:38:20,930 --> 00:38:25,160
Тады ў нас больш негатыўных зменаў тут.

490
00:38:25,160 --> 00:38:29,990
Ключ да зніжэння нашым складзе праблемай у нашай максімальнай праблемы подмассива

491
00:38:29,990 --> 00:38:36,630
з'яўляецца разгляд дэльты паміж дзён.

492
00:38:36,630 --> 00:38:40,630
Такім чынам, мы ствараем новы масіў з імем дэльты,

493
00:38:40,630 --> 00:38:43,000
ініцыялізацыя першага элемента роўным 0,

494
00:38:43,000 --> 00:38:46,380
а затым для кожнай дэльты (I), няхай гэта будзе розніца

495
00:38:46,380 --> 00:38:52,830
маёй ўваходны масіў (I), і масіў (я - 1).

496
00:38:52,830 --> 00:38:55,530
Тады мы называем нашай руціннай працэдурай для максімальнага подмассива

497
00:38:55,530 --> 00:39:01,500
якая праходзіць у масіве дэльты.

498
00:39:01,500 --> 00:39:06,440
І таму, што максімальная подмассива з'яўляецца лінейным часам,

499
00:39:06,440 --> 00:39:09,370
і гэта скарачэнне, гэты працэс стварэння гэтай дэльты масіва,

500
00:39:09,370 --> 00:39:11,780
Таксама лінейнага часу,

501
00:39:11,780 --> 00:39:19,060
то канчатковае рашэнне запасаў O (п) плюс праца O (п) работы, па-ранейшаму O (п) працы.

502
00:39:19,060 --> 00:39:23,900
Таму ў нас ёсць лінейнае час вырашэння нашай праблемы.

503
00:39:23,900 --> 00:39:29,610
Ці ўсё разумеюць гэта пераўтварэнне?

504
00:39:29,610 --> 00:39:32,140
>> Увогуле, добрая ідэя, што вы заўсёды павінны мець

505
00:39:32,140 --> 00:39:34,290
гэта паспрабаваць паменшыць новая праблема, што вы бачыце.

506
00:39:34,290 --> 00:39:37,700
Калі яно выглядае знаёма старая праблема,

507
00:39:37,700 --> 00:39:39,590
паспрабуйце паменшыць яго старая праблема.

508
00:39:39,590 --> 00:39:41,950
І калі вы можаце выкарыстоўваць усе інструменты, якія вы выкарыстоўвалі на старыя праблемы

509
00:39:41,950 --> 00:39:46,450
для вырашэння новай праблемы.

510
00:39:46,450 --> 00:39:49,010
Такім чынам, каб падводзіць вынікі, тэхнічнае інтэрв'ю складанай задачай.

511
00:39:49,010 --> 00:39:52,280
Гэтыя праблемы, верагодна, некаторыя з найбольш складаных праблем

512
00:39:52,280 --> 00:39:54,700
што вы можаце ўбачыць у адным з інтэрв'ю,

513
00:39:54,700 --> 00:39:57,690
так што калі вы не разумееце, усе праблемы, якія я толькі пакрытыя, гэта нармальна.

514
00:39:57,690 --> 00:40:01,080
Вось некаторыя з найбольш складаных праблем.

515
00:40:01,080 --> 00:40:03,050
Практыка, практыка, практыка.

516
00:40:03,050 --> 00:40:08,170
Я дала шмат праблем у раздатачны матэрыял, так вызначана праверыць гэтыя.

517
00:40:08,170 --> 00:40:11,690
І поспеху на інтэрв'ю. Усе мае рэсурсы, размешчаныя на гэтую спасылку,

518
00:40:11,690 --> 00:40:15,220
і адзін з маіх старэйшых сяброў прапанаваў зрабіць макет тэхнічнае інтэрв'ю,

519
00:40:15,220 --> 00:40:22,050
так што калі вы зацікавіліся, ліст будзе Яо, што адрас электроннай пошты.

520
00:40:22,050 --> 00:40:26,070
Калі ў вас ёсць пытанні, вы можаце спытаць мяне.

521
00:40:26,070 --> 00:40:28,780
Як вы, хлопцы, ёсць канкрэтныя пытанні, звязаныя з тэхнічнымі інтэрв'ю

522
00:40:28,780 --> 00:40:38,440
або любыя праблемы, якія мы бачылі да гэтага часу?

523
00:40:38,440 --> 00:40:49,910
Добра. Ну, поспеху на інтэрв'ю.

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