1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] [Seminar: Texniki Müsahibələr]

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

3
00:00:04,630 --> 00:00:08,910
[Bu CS50 edir.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
Salam hər kəs, mən Kenny edirəm. Hal-hazırda kiçik öyrənilməsi kompüter edirəm.

5
00:00:12,420 --> 00:00:17,310
, Mən keçmiş CS TF oldum və mən bir underclassman olanda mən bu idi arzulayıram

6
00:00:17,310 --> 00:00:19,380
Mən bu seminar verirəm niyə və ki.

7
00:00:19,380 --> 00:00:21,370
Belə ki, mən onu zövq ümid edirik.

8
00:00:21,370 --> 00:00:23,470
Bu seminar, texniki müsahibələr haqqında

9
00:00:23,470 --> 00:00:26,650
və bütün resursları, bu link əldə edə bilərsiniz

10
00:00:26,650 --> 00:00:32,350
Burada bu link, ehtiyatların bir neçə.

11
00:00:32,350 --> 00:00:36,550
Mən bir neçə problemlər, əslində, problemlərin bir siyahısını etdi.

12
00:00:36,550 --> 00:00:40,800
Biz ipuçları tapa bilərsiniz Həmçinin ümumi ehtiyatları səhifə

13
00:00:40,800 --> 00:00:42,870
müsahibə üçün hazırlamaq üçün necə,

14
00:00:42,870 --> 00:00:46,470
Əgər faktiki müsahibə zamanı nə etməlidir haqqında məsləhətlər,

15
00:00:46,470 --> 00:00:51,910
həmçinin gələcək sened üçün problemləri və ehtiyatları yaxınlaşmaq necə.

16
00:00:51,910 --> 00:00:53,980
Bu, bütün online.

17
00:00:53,980 --> 00:00:58,290
Və yalnız bu seminar, bir disclaimer, giriş üçün

18
00:00:58,290 --> 00:01:00,690
bu kimi lazımdır - Sizin müsahibə hazırlıq

19
00:01:00,690 --> 00:01:02,800
bu siyahı ilə məhdudlaşmır bilməz.

20
00:01:02,800 --> 00:01:04,750
Bu yalnız bir guide deməkdir

21
00:01:04,750 --> 00:01:08,890
və siz mütləq, mən duz bir taxıl ilə demək hər şey almaq lazımdır

22
00:01:08,890 --> 00:01:14,620
həm də mən sizin müsahibə hazırlanmasında sizə kömək etmək üçün istifadə hər şey istifadə edin.

23
00:01:14,620 --> 00:01:16,400
>> I növbəti bir neçə slaydlar vasitəsilə sürətləndirmək üçün gedirəm

24
00:01:16,400 --> 00:01:18,650
biz faktiki Case əldə edə bilərsiniz.

25
00:01:18,650 --> 00:01:23,630
Bir proqram engineering postion üçün müsahibə strukturu,

26
00:01:23,630 --> 00:01:26,320
adətən 30 dən 45 dəqiqə,

27
00:01:26,320 --> 00:01:29,810
şirkət olaraq çox el.

28
00:01:29,810 --> 00:01:33,090
Tez-tez bir ağ board kodlaşdırma olacaq.

29
00:01:33,090 --> 00:01:35,960
Belə ki, bu kimi, lakin tez-tez kiçik miqyaslı bir ağ board.

30
00:01:35,960 --> 00:01:38,540
Bir telefon müsahibəsi qarşılaşdıqda, siz yəqin ki, istifadə edəcəyik

31
00:01:38,540 --> 00:01:44,030
collabedit və ya Google Doc ya onlar sizin kodlaşdırma canlı görə bilərsiniz

32
00:01:44,030 --> 00:01:46,500
Siz telefon müsahibə keçirilir etdiyiniz zaman.

33
00:01:46,500 --> 00:01:48,490
Müsahibə özü adətən 2 və ya 3 problemləri

34
00:01:48,490 --> 00:01:50,620
kompüter elm bilik test.

35
00:01:50,620 --> 00:01:54,490
Və demək olar ki, mütləq kodlaşdırma iştirak edəcək.

36
00:01:54,490 --> 00:01:59,540
Görürsünüz ki, sualların növləri adətən data strukturları və alqoritmlər var.

37
00:01:59,540 --> 00:02:02,210
Və problemlər bu cür etməklə,

38
00:02:02,210 --> 00:02:07,830
onlar kimi, xahiş edirik ki, nə zaman və məkan mürəkkəbliyi, böyük O nədir?

39
00:02:07,830 --> 00:02:09,800
Tez-tez onlar da yüksək səviyyəli suallar,

40
00:02:09,800 --> 00:02:12,530
belə bir sistem layihələndirilməsi

41
00:02:12,530 --> 00:02:14,770
necə sizin kodu salınması olardı?

42
00:02:14,770 --> 00:02:18,370
Nə interfeys, nə dərsləri, sizin sistem nə modulları var,

43
00:02:18,370 --> 00:02:20,900
və bu necə birlikdə qarşılıqlı edirsiniz?

44
00:02:20,900 --> 00:02:26,130
Belə data strukturları və alqoritmlər, həmçinin dizayn sistemi.

45
00:02:26,130 --> 00:02:29,180
>> Biz Case üçün dalış əvvəl bəzi ümumi ipuçları.

46
00:02:29,180 --> 00:02:32,300
Mən ən əhəmiyyətli qayda həmişə yüksək səslə düşünür ola düşünürəm.

47
00:02:32,300 --> 00:02:36,980
Müsahibə sizin düşüncə prosesi off göstərmək üçün şans olması ehtimal edilir.

48
00:02:36,980 --> 00:02:39,820
Müsahib ölçmek üçün müsahibə nöqtəsi

49
00:02:39,820 --> 00:02:42,660
necə düşünürsünüz və necə bir problem keçir.

50
00:02:42,660 --> 00:02:45,210
Edə bilərsiniz ən pis şey, bütün müsahibə boyunca ola səssiz edir.

51
00:02:45,210 --> 00:02:50,090
Bu yalnız heç bir yaxşı.

52
00:02:50,090 --> 00:02:53,230
Bir sual verilir, siz həmçinin sual başa əmin etmək istəyirəm.

53
00:02:53,230 --> 00:02:55,350
Belə ki, öz sözləri ilə geri sual təkrar

54
00:02:55,350 --> 00:02:58,920
və cəhd hərtərəfli bir neçə sadə test hallarda iş

55
00:02:58,920 --> 00:03:01,530
Siz sual başa əmin etmək.

56
00:03:01,530 --> 00:03:05,510
Bir neçə test hallarda vasitəsilə iş də bu problemi həll etmək üçün necə bir intuisiya verəcək.

57
00:03:05,510 --> 00:03:11,210
Siz hətta bir neçə nümunələri siz bu problemi həll kömək tapmaq bilər.

58
00:03:11,210 --> 00:03:14,500
Onların böyük tip incidir əldə edir.

59
00:03:14,500 --> 00:03:17,060
Incidir almaq etməyin.

60
00:03:17,060 --> 00:03:19,060
Müsahibələr çətin, lakin siz edə bilərsiniz ən pis şey,

61
00:03:19,060 --> 00:03:23,330
səssiz olmaqla yanaşı, aşkar incidir edilir.

62
00:03:23,330 --> 00:03:27,410
Siz Müsahib ki, təəssürat vermək istəmirəm.

63
00:03:27,410 --> 00:03:33,960
Bir şey ki, - belə ki, bir çox insanlar, onlar müsahibə getmək zaman,

64
00:03:33,960 --> 00:03:37,150
onlar, ilk ən yaxşı həll tapmağa cəhd

65
00:03:37,150 --> 00:03:39,950
zaman, həqiqətən, bir glaringly Aşkar həll adətən var.

66
00:03:39,950 --> 00:03:43,500
Bu yavaş ola bilər, bu səmərəsiz ola bilər, lakin yalnız göstərməlidir

67
00:03:43,500 --> 00:03:46,210
yalnız belə daha yaxşı işləmək üçün bir başlanğıc nöqtəsi var.

68
00:03:46,210 --> 00:03:48,270
Həmçinin, həll işarə baxımından yavaş

69
00:03:48,270 --> 00:03:52,160
böyük O zaman mürəkkəbliyi və ya kosmik mürəkkəbliyi,

70
00:03:52,160 --> 00:03:54,450
siz anlamaq ki, Müsahib nümayiş olunacaq

71
00:03:54,450 --> 00:03:57,510
bu məsələlər kodu yazarkən.

72
00:03:57,510 --> 00:04:01,440
Belə ki, ilk sadə alqoritmi ilə gəlmək qorxma

73
00:04:01,440 --> 00:04:04,950
və sonra orada daha yaxşı işləyir.

74
00:04:04,950 --> 00:04:09,810
Hər hansı sual, bu günə qədər? Okay.

75
00:04:09,810 --> 00:04:11,650
>> Belə edək ilk problem dalış.

76
00:04:11,650 --> 00:04:14,790
"N integers bir sıra nəzərə alaraq, array shuffles bir funksiya yazmaq

77
00:04:14,790 --> 00:04:20,209
n integers bütün permutations bərabər güman ki, belə yerdə. "

78
00:04:20,209 --> 00:04:23,470
Və mövcud bir təsadüfi tam generator var güman

79
00:04:23,470 --> 00:04:30,980
yarısı üçündür, 0-dan i bir sıra bir tamsayı yaradır.

80
00:04:30,980 --> 00:04:32,970
Hər kəs bu suala anlamaq varmı?

81
00:04:32,970 --> 00:04:39,660
Mən sizə n integers bir sıra vermək, sizə shuffle onu istəyirik.

82
00:04:39,660 --> 00:04:46,050
Mənim kataloqu, mən nə demək nümayiş bir neçə proqramları yazdı.

83
00:04:46,050 --> 00:04:48,910
Mən, shuffle 20 elementlər bir sıra gedirəm

84
00:04:48,910 --> 00:04:52,490
-10 ildən +9 üçün

85
00:04:52,490 --> 00:04:57,050
və sizə bu kimi bir siyahı çıxış etmək istəyirəm.

86
00:04:57,050 --> 00:05:02,890
Belə ki, bu mənim sıralanır giriş array və mən sizə shuffle onu istəyirik.

87
00:05:02,890 --> 00:05:07,070
Biz bunu edəcəyik.

88
00:05:07,070 --> 00:05:13,780
Hər kəs sual anlamaq varmı? Okay.

89
00:05:13,780 --> 00:05:16,730
Belə ki, siz qalmışdır.

90
00:05:16,730 --> 00:05:21,220
Bəzi fikirlər var? Siz n ^ 2, n log n, n kimi bunu edə bilərəmmi?

91
00:05:21,220 --> 00:05:34,400
Təklif açın.

92
00:05:34,400 --> 00:05:37,730
Okay. Emmy təklif Belə bir fikir,

93
00:05:37,730 --> 00:05:45,300
ilk 0-dan 20-a təsadüfi sayı, təsadüfi tam, bir sıra hesablamaq edir.

94
00:05:45,300 --> 00:05:49,840
Belə ki, bizim array 20 uzunluğu daşımır.

95
00:05:49,840 --> 00:05:54,800
20 elementlər bizim sxemdə,

96
00:05:54,800 --> 00:05:58,560
bu giriş array edir.

97
00:05:58,560 --> 00:06:04,590
Və indi, onun təklif, yeni bir sıra yaratmaq

98
00:06:04,590 --> 00:06:08,440
Bu çıxış array olacaq.

99
00:06:08,440 --> 00:06:12,880
Və i Rand ilə geri əsasında -

100
00:06:12,880 --> 00:06:17,580
i idi ki,, 17, deyək

101
00:06:17,580 --> 00:06:25,640
ilk mövqeyi 17-ci element surəti.

102
00:06:25,640 --> 00:06:30,300
İndi silmək lazımdır - biz burada bütün elementləri keçmək lazımdır

103
00:06:30,300 --> 00:06:36,920
artıq biz sonunda bir boşluq və ortada heç bir deşik var.

104
00:06:36,920 --> 00:06:39,860
İndi biz prosesi təkrar edin.

105
00:06:39,860 --> 00:06:46,360
İndi 0 və 19 arasında yeni bir təsadüfi tam seçin.

106
00:06:46,360 --> 00:06:52,510
Biz burada yeni bir i var və biz bu mövqeyi bu element surəti.

107
00:06:52,510 --> 00:07:00,960
Sonra biz artıq maddələr keçmək və biz tam yeni array qədər biz prosesi təkrar edin.

108
00:07:00,960 --> 00:07:05,890
Bu alqoritm run zaman nədir?

109
00:07:05,890 --> 00:07:08,110
Yaxşı, bu təsiri hesab edək.

110
00:07:08,110 --> 00:07:10,380
Biz hər bir element dəyişir.

111
00:07:10,380 --> 00:07:16,800
Biz bu i aradan qaldırılması zaman, biz sola sonra bütün elementlər dəyişir.

112
00:07:16,800 --> 00:07:21,600
Və bir O (n) dəyəri

113
00:07:21,600 --> 00:07:26,100
çünki biz ilk element aradan əgər?

114
00:07:26,100 --> 00:07:29,670
Belə ki, hər bir aradan qaldırılması üçün, biz aradan qaldırılması -

115
00:07:29,670 --> 00:07:32,170
hər qaldırılması, bir O (n) əməliyyat götürür

116
00:07:32,170 --> 00:07:41,520
biz kaldırma n yana, bu O (n ^ 2) shuffle gətirib çıxarır.

117
00:07:41,520 --> 00:07:49,550
Okay. Belə ki, yaxşı bir başlanğıc. Yaxşı başlanğıc.

118
00:07:49,550 --> 00:07:55,290
>> Digər bir təklif isə Knuth shuffle kimi tanınan bir şey istifadə etmək

119
00:07:55,290 --> 00:07:57,540
və ya Fisher-Yates shuffle.

120
00:07:57,540 --> 00:07:59,630
Və həqiqətən xətti vaxt shuffle var.

121
00:07:59,630 --> 00:08:02,200
Və fikir çox oxşardır.

122
00:08:02,200 --> 00:08:05,160
Yenə biz daxil array var

123
00:08:05,160 --> 00:08:08,580
amma yerinə giriş / çıxış üçün iki seriallarda istifadə,

124
00:08:08,580 --> 00:08:13,590
biz qarışdırılmış hissəsi takip serialın ilk hissəsi istifadə

125
00:08:13,590 --> 00:08:18,400
və biz takip, sonra biz unshuffled hissəsi bizim serialın istirahət buraxın.

126
00:08:18,400 --> 00:08:24,330
Belə ki, burada nə demək deyil. Biz başlamaq - biz bir i seçin

127
00:08:24,330 --> 00:08:30,910
0-dan 20-bir sıra.

128
00:08:30,910 --> 00:08:36,150
Bizim cari göstərici birinci index işarə edir.

129
00:08:36,150 --> 00:08:39,590
Biz bəzi i burada seçmək

130
00:08:39,590 --> 00:08:42,740
və indi dəyişdirmək.

131
00:08:42,740 --> 00:08:47,690
Bu 5 idi və bu 4 Belə ki, əgər

132
00:08:47,690 --> 00:08:57,150
nəticəsində array burada 5 burada və 4 olacaq.

133
00:08:57,150 --> 00:09:00,390
İndi biz burada bir marker unutmayın.

134
00:09:00,390 --> 00:09:05,770
Sol hər şey qarışdırılmış olunur

135
00:09:05,770 --> 00:09:15,160
və sağ hər şeyi unshuffled olunur.

136
00:09:15,160 --> 00:09:17,260
İndi biz prosesi təkrar edə bilərsiniz.

137
00:09:17,260 --> 00:09:25,210
Biz indi 1 və 20 arasında bir təsadüfi index seçin.

138
00:09:25,210 --> 00:09:30,650
Belə ki, i burada yeni güman edirlər.

139
00:09:30,650 --> 00:09:39,370
İndi biz burada cari yeni mövqe ilə bu i dəyişdirmək.

140
00:09:39,370 --> 00:09:44,790
Beləliklə, biz bu kimi geri və irəli dəyişdirmə yoxdur.

141
00:09:44,790 --> 00:09:51,630
Mənə daha konkret etmək kodu getirsin.

142
00:09:51,630 --> 00:09:55,290
Biz i bizim seçimi ilə başlamaq -

143
00:09:55,290 --> 00:09:58,370
i 0 bərabər biz başlamaq, biz təsadüfi yeri j seçin

144
00:09:58,370 --> 00:10:02,420
bu serialın unshuffled hissəsi, i, n-1.

145
00:10:02,420 --> 00:10:07,280
Mən burada oldum Belə ki, burada və array qalan arasında təsadüfi index seçmək

146
00:10:07,280 --> 00:10:12,410
və biz dəyişdirmək.

147
00:10:12,410 --> 00:10:17,550
Bu shuffle sizin array üçün lazım olan bütün kodu.

148
00:10:17,550 --> 00:10:21,670
Hər hansı sual?

149
00:10:21,670 --> 00:10:25,530
>> Yaxşı, bir sual lazım, niyə bu doğru deyil?

150
00:10:25,530 --> 00:10:28,360
Niyə hər permutation bərabər güman edir?

151
00:10:28,360 --> 00:10:30,410
Və mən, bu sübut ilə getməyəcək

152
00:10:30,410 --> 00:10:35,970
lakin kompüter çox problemləri induksiya vasitəsilə sübut edilə bilər.

153
00:10:35,970 --> 00:10:38,520
Necə bir çox induksiya ilə tanış var?

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

155
00:10:40,590 --> 00:10:43,610
Belə ki, sadə induksiya bu alqoritm düzgünlüyünü sübut edə bilər

156
00:10:43,610 --> 00:10:49,540
Sizin induksiya fərziyyə ola bilər yerləşir, güman

157
00:10:49,540 --> 00:10:53,290
mənim shuffle hər permutation bərabər ehtimal qaytarır

158
00:10:53,290 --> 00:10:56,120
qədər ilk i elementləri.

159
00:10:56,120 --> 00:10:58,300
İndi, i + 1 düşünün.

160
00:10:58,300 --> 00:11:02,550
Biz index j dəyişdirmək üçün seçin yolu ilə,

161
00:11:02,550 --> 00:11:05,230
, sonra ətraflı işləmək - bu səbəb

162
00:11:05,230 --> 00:11:07,390
Bu alqoritm qaytarır niyə ən azı bir tam sübut

163
00:11:07,390 --> 00:11:12,800
bərabər ehtimal ehtimal hər permutation.

164
00:11:12,800 --> 00:11:15,940
>> Bütün hüquqlar, növbəti problem.

165
00:11:15,940 --> 00:11:19,170
Belə ki, "mənfi sıfır, postive integers bir sıra verilir

166
00:11:19,170 --> 00:11:21,290
maksimum məbləği hesablayır bir funksiya yazmaq

167
00:11:21,290 --> 00:11:24,720
daxil array hər hansı continueous subarray edir. "

168
00:11:24,720 --> 00:11:28,370
Burada, məsələn, bütün nömrələri müsbət olduğu zaman,

169
00:11:28,370 --> 00:11:31,320
sonra hazırda ən yaxşı seçim bütün array etməkdir.

170
00:11:31,320 --> 00:11:34,690
1, 2, 3, 4, 10 bərabərdir.

171
00:11:34,690 --> 00:11:36,780
Orada bəzi neqativ zaman,

172
00:11:36,780 --> 00:11:38,690
Bu halda biz yalnız ilk iki istəyirəm

173
00:11:38,690 --> 00:11:44,590
-1 və / və ya -3 seçilməsi bizim məbləğin aşağı gətirmək olacaq.

174
00:11:44,590 --> 00:11:48,120
Bəzən biz serialın ortasında başlamaq ola bilər.

175
00:11:48,120 --> 00:11:53,500
Bəzən biz heç bir şey seçə istəyirəm bir şey deyil yaxşı deyil.

176
00:11:53,500 --> 00:11:56,490
Və bəzən, payız etmək daha yaxşıdır

177
00:11:56,490 --> 00:12:07,510
sonra şey super böyük deyil. Belə ki, hər hansı bir fikir?

178
00:12:07,510 --> 00:12:10,970
(Tələbə, anlaşılmaz) >> Bəli.

179
00:12:10,970 --> 00:12:13,560
Mən -1 etmirlər düşünək.

180
00:12:13,560 --> 00:12:16,170
Sonra da mən 1000 və 20,000 seçin

181
00:12:16,170 --> 00:12:18,630
və ya yalnız 3 milyard seçin.

182
00:12:18,630 --> 00:12:20,760
Yaxşı, ən yaxşı seçim bütün nömrələri iştirak edir.

183
00:12:20,760 --> 00:12:24,350
Bu -1, mənfi olmasına baxmayaraq,

184
00:12:24,350 --> 00:12:31,340
bütün məbləğ mən -1 etmək deyil, daha yaxşıdır.

185
00:12:31,340 --> 00:12:36,460
Mən əvvəl qeyd ipuçlarını biri aydın aşkar etmək idi

186
00:12:36,460 --> 00:12:40,540
ilk və brute force həlli.

187
00:12:40,540 --> 00:12:44,340
Bu problem də brute force həlli nədir? Evet?

188
00:12:44,340 --> 00:12:46,890
[Jane] Bəli, mən brute force həll edirəm

189
00:12:46,890 --> 00:12:52,600
bütün mümkün birləşməsi (anlaşılmaz) əlavə olardı.

190
00:12:52,600 --> 00:12:58,250
[Yu] Okay. Belə ki, Jane ideyası hər cür iştirak edir -

191
00:12:58,250 --> 00:13:01,470
Mən paraphrasing Ben - hər mümkün davamlı subarray almaq üçün,

192
00:13:01,470 --> 00:13:07,840
onun məbləği hesablamaq, sonra bütün mümkün davamlı subarrays maksimum edirlər.

193
00:13:07,840 --> 00:13:13,310
Nə benzersiz mənim giriş array bir subarray müəyyən?

194
00:13:13,310 --> 00:13:17,380
Nə iki şey lazımdır, kimi? Evet?

195
00:13:17,380 --> 00:13:19,970
(Tələbə, anlaşılmaz) >> hüququ.

196
00:13:19,970 --> 00:13:22,130
A aşağı göstərici və üst bound indeksi bağlı

197
00:13:22,130 --> 00:13:28,300
benzersiz davamlı subarray müəyyənləşdirir.

198
00:13:28,300 --> 00:13:31,400
[Qadın tələbə] Biz bu unikal ədəd bir sıra var qiymətləndirilməsi edirmi?

199
00:13:31,400 --> 00:13:34,280
[Yu] No ona sual Beləliklə, biz array fərz edilir -

200
00:13:34,280 --> 00:13:39,000
bizim array bütün unikal nömrə və cavab yoxdur.

201
00:13:39,000 --> 00:13:43,390
>> Biz sonra brute force həlli, başlanğıc / son göstəriciləri istifadə edin

202
00:13:43,390 --> 00:13:47,200
benzersiz bizim davamlı subarray müəyyənləşdirir.

203
00:13:47,200 --> 00:13:51,680
Biz bütün mümkün start entries üçün təkrarlamaq Beləliklə, əgər,

204
00:13:51,680 --> 00:13:58,320
və bütün son entries üçün> və ya = başlamaq və <n

205
00:13:58,320 --> 00:14:05,570
siz məbləği hesablamaq, sonra biz bu günə qədər gördüm maksimum məbləği alır.

206
00:14:05,570 --> 00:14:07,880
Bu aydın deyilmi?

207
00:14:07,880 --> 00:14:12,230
Bu həll böyük O nədir?

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

209
00:14:16,660 --> 00:14:18,860
Olduqca ^ 2 n deyil.

210
00:14:18,860 --> 00:14:25,250
Biz 0-dan n təkrarlamaq Qeyd edək ki,

211
00:14:25,250 --> 00:14:27,520
ki loop üçün biri.

212
00:14:27,520 --> 00:14:35,120
Biz loop üçün demək olar ki, başdan başa başqa bir təkrarlamaq.

213
00:14:35,120 --> 00:14:37,640
İndi ki, ərzində, biz, hər giriş yekunlaşdırmaq üçün

214
00:14:37,640 --> 00:14:43,810
ki loop üçün bir var. Beləliklə, biz üç loops üçün iç içə, n ^ 3 var.

215
00:14:43,810 --> 00:14:46,560
Okay. Bu başlanğıc nöqtəsi kimi gedir.

216
00:14:46,560 --> 00:14:53,180
Bizim həll n ^ 3 daha pisdir.

217
00:14:53,180 --> 00:14:55,480
Hər kəs brute force həll anlamaq varmı?

218
00:14:55,480 --> 00:14:59,950
>> Okay. Daha yaxşı həll dinamik proqramlaşdırma adlı fikir istifadə edir.

219
00:14:59,950 --> 00:15:03,040
Siz CS124 alsaq, bu, alqoritm və Data strukturu deyil

220
00:15:03,040 --> 00:15:05,680
Bu texnika ilə çox tanış olacaq.

221
00:15:05,680 --> 00:15:12,190
Və fikir, ilk kiçik problemlərin həlli yaratmaq üçün cəhd edir.

222
00:15:12,190 --> 00:15:17,990
Başlanğıc ve bitiş: bu ilə nə demək, hazırda iki şey barədə narahat yoxdur.

223
00:15:17,990 --> 00:15:29,340
Və bu annoying var. Biz bu parametrlərdən biri xilas ola bilər nə?

224
00:15:29,340 --> 00:15:32,650
We're bizim orijinal problem alsaq, - bir fikir etmək

225
00:15:32,650 --> 00:15:37,470
bir sıra hər hansı subarray maksimum məbləğ [O, n-1] tapa bilərsiniz.

226
00:15:37,470 --> 00:15:47,400
Və indi biz cari index i, biz bilirik bir yeni subproblem var

227
00:15:47,400 --> 00:15:52,520
biz orada bağlamaq lazımdır bilirik. Bizim subarray cari index da başa olmalıdır.

228
00:15:52,520 --> 00:15:57,640
Qalan problem Belə ki, burada biz subarray başlamaq lazımdır?

229
00:15:57,640 --> 00:16:05,160
Bu mənada edirmi? Okay.

230
00:16:05,160 --> 00:16:12,030
Mən bu qədər kodlu etdik və nə deməkdir baxmaq edək.

231
00:16:12,030 --> 00:16:16,230
Bu codirectory ildə subarray adlı proqram var

232
00:16:16,230 --> 00:16:19,470
və bu maddələrin sıra edir

233
00:16:19,470 --> 00:16:25,550
və mənim qarışdırılmış siyahısına maksimal subarray məbləğ qaytarılır.

234
00:16:25,550 --> 00:16:29,920
Belə ki, bu halda, bizim maksimum subarray 3.

235
00:16:29,920 --> 00:16:34,850
Və yalnız 2 və 1 istifadə edərək qəbul edir.

236
00:16:34,850 --> 00:16:38,050
Nin yenidən run edək. Bu da 3 var.

237
00:16:38,050 --> 00:16:40,950
Lakin bu dəfə biz 3 almışdır necə qeyd.

238
00:16:40,950 --> 00:16:46,690
Biz etdi - biz yalnız 3 özü almaq

239
00:16:46,690 --> 00:16:49,980
hər iki tərəfdən neqativ əhatə edir, çünki

240
00:16:49,980 --> 00:16:55,080
məbləğində <3 getirecek.

241
00:16:55,080 --> 00:16:57,820
10 maddələr üzrə run edək.

242
00:16:57,820 --> 00:17:03,200
7 var Bu dəfə biz aparıcı 3 və 4 edirlər.

243
00:17:03,200 --> 00:17:09,450
Bu dəfə 8, və biz 1, 4 və 3 alaraq ki almaq.

244
00:17:09,450 --> 00:17:16,310
Belə ki, necə bir intuisiya vermək biz bu transformasiya problemi həll edə bilər,

245
00:17:16,310 --> 00:17:18,890
bu subarray nəzər salaq.

246
00:17:18,890 --> 00:17:23,460
Biz bu giriş array verilmiş və biz cavab 8 bilirik edirik.

247
00:17:23,460 --> 00:17:26,359
Biz 1, 4, və 3 edirlər.

248
00:17:26,359 --> 00:17:29,090
Amma biz həqiqətən ki, cavab var necə baxaq.

249
00:17:29,090 --> 00:17:34,160
Nin bu göstəricilərin hər biri başa maksimal subarray baxaq.

250
00:17:34,160 --> 00:17:40,780
Ilk mövqedə sona ki maksimal subarray nədir?

251
00:17:40,780 --> 00:17:46,310
[Tələbə] Zero. >> Zero. Yalnız -5 etmirlər.

252
00:17:46,310 --> 00:17:50,210
Burada həmçinin 0 olacaq. Evet?

253
00:17:50,210 --> 00:17:56,470
(Tələbə, anlaşılmaz)

254
00:17:56,470 --> 00:17:58,960
[Yu] Oh, sorry, bu -3 edir.

255
00:17:58,960 --> 00:18:03,220
Bu 2-dir, belə ki, bu -3 edir.

256
00:18:03,220 --> 00:18:08,690
Okay. Belə -4 ki, mövqe bitirmək üçün maksimal subarray nə

257
00:18:08,690 --> 00:18:12,910
-4 olduğu? Zero.

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

259
00:18:22,570 --> 00:18:28,060
İndi -2 olduğu yer üzrə son olmalıdır.

260
00:18:28,060 --> 00:18:39,330
Belə ki, 6, 5, 7, və son bir 4.

261
00:18:39,330 --> 00:18:43,480
Bu mənim entries ki, hər şeyi

262
00:18:43,480 --> 00:18:48,130
Mən bu göstəricilərin hər bitmelidir olduğu transformasiya problem üçün,

263
00:18:48,130 --> 00:18:51,410
sonra mənim final cavab yalnız, arasında sweep almaq

264
00:18:51,410 --> 00:18:53,580
və maksimum edirlər.

265
00:18:53,580 --> 00:18:55,620
Belə ki, bu halda 8 deyil.

266
00:18:55,620 --> 00:19:00,010
Bu, maksimal subarray bu göstərici bitir o deməkdir ki,

267
00:19:00,010 --> 00:19:04,970
və əvvəl bir yerdə başladı.

268
00:19:04,970 --> 00:19:09,630
Hər kəs bu transformasiya subarray anlamaq varmı?

269
00:19:09,630 --> 00:19:22,160
>> Okay. Yaxşı, bu üçün təkrar həyata rəqəm imkan verir.

270
00:19:22,160 --> 00:19:27,990
Nin yalnız ilk bir neçə entries hesab edək.

271
00:19:27,990 --> 00:19:35,930
Belə ki, burada, 8 0, 0, 0, 1, 5 idi.

272
00:19:35,930 --> 00:19:39,790
Və sonra burada bir -2 idi ki, 6 yerə gətirdi.

273
00:19:39,790 --> 00:19:50,800
Mən vəziyyəti giriş zəng əgər i subproblem (i)

274
00:19:50,800 --> 00:19:54,910
necə bir əvvəlki subproblem cavab istifadə edə bilərsiniz

275
00:19:54,910 --> 00:19:59,360
bu subproblem cavab?

276
00:19:59,360 --> 00:20:04,550
Mən baxsaq, bu giriş, deyək.

277
00:20:04,550 --> 00:20:09,190
Necə baxaraq cavab 6 hesablamaq olar

278
00:20:09,190 --> 00:20:18,780
Bu array və bu serialın əvvəlki subproblems cavab birləşməsi? Bəli?

279
00:20:18,780 --> 00:20:22,800
[Qadın tələbə] Siz xərclər array almaq

280
00:20:22,800 --> 00:20:25,430
mövqeyi sağ əvvəl, 8 belə

281
00:20:25,430 --> 00:20:32,170
və sonra cari subproblem əlavə edin.

282
00:20:32,170 --> 00:20:36,460
[Yu], onun təklif bu iki ədəd baxmaq edir

283
00:20:36,460 --> 00:20:40,090
Bu sayı və bu nömrəsini.

284
00:20:40,090 --> 00:20:50,130
Beləliklə, bu 8 subproblem üçün cavab (1 - i) aiddir.

285
00:20:50,130 --> 00:20:57,300
Və beni daxil array A. zəng edək

286
00:20:57,300 --> 00:21:01,470
Mövqe i başa çatır ki, maksimal subarray tapmaq üçün,

287
00:21:01,470 --> 00:21:03,980
Mən iki seçim var: mən ya subarray davam edə bilər

288
00:21:03,980 --> 00:21:09,790
ki əvvəlki index başa çatıb, ya yeni bir sıra başlayın.

289
00:21:09,790 --> 00:21:14,190
Mən əvvəlki göstərici ilə başlayan subarray davam olsaydı

290
00:21:14,190 --> 00:21:19,260
sonra mən nail maksimum məbləği əvvəlki subproblem üçün cavab

291
00:21:19,260 --> 00:21:24,120
üstəgəl cari array giriş.

292
00:21:24,120 --> 00:21:27,550
Amma, mən də, yeni subarray başlayan seçim

293
00:21:27,550 --> 00:21:30,830
bu halda məbləğ 0 deyil.

294
00:21:30,830 --> 00:21:42,860
1, üstəgəl cari array giriş - Belə cavab 0 max, subproblem i edir.

295
00:21:42,860 --> 00:21:46,150
Bu residiv mənada edirmi?

296
00:21:46,150 --> 00:21:50,840
Bizim təkrar, biz yalnız aşkar kimi, subproblem i deyil

297
00:21:50,840 --> 00:21:54,740
ki, əvvəlki subproblem maksimum plus mənim cari array giriş bərabərdir

298
00:21:54,740 --> 00:22:01,490
olan əvvəlki subarray davam deməkdir

299
00:22:01,490 --> 00:22:07,250
və ya 0, mənim cari index yeni subarray başlamaq.

300
00:22:07,250 --> 00:22:10,060
Və bir dəfə biz final cavab sonra, həllər bu cədvəl tikilib,

301
00:22:10,060 --> 00:22:13,950
yalnız subproblem array arasında xətti sweep etmək

302
00:22:13,950 --> 00:22:19,890
və maksimum edirlər.

303
00:22:19,890 --> 00:22:23,330
Bu yalnız nə dəqiq təzahürüdür.

304
00:22:23,330 --> 00:22:27,320
Yəni biz yeni bir subproblem dizi, subproblems yaradır.

305
00:22:27,320 --> 00:22:32,330
İlk giriş 0 və ya ilk giriş, bu iki maksimum ya edir.

306
00:22:32,330 --> 00:22:35,670
Və subproblems qalan

307
00:22:35,670 --> 00:22:39,810
biz yalnız aşkar dəqiq təkrar istifadə edin.

308
00:22:39,810 --> 00:22:49,960
İndi bizim subproblems array maksimum hesablamaq və son cavab var.

309
00:22:49,960 --> 00:22:54,130
>> Belə ki, necə çox yer biz bu alqoritm istifadə edir?

310
00:22:54,130 --> 00:23:01,470
Yalnız CS50 qəbul etdik, onda çox yer müzakirə ola bilər.

311
00:23:01,470 --> 00:23:07,750
Bəli, qeyd üçün bir şey ölçüsü n burada malloc adlı edir.

312
00:23:07,750 --> 00:23:13,590
Ki, siz nə təklif edir?

313
00:23:13,590 --> 00:23:17,450
Bu alqoritm linear space istifadə edir.

314
00:23:17,450 --> 00:23:21,030
Biz daha yaxşı edə bilərəmmi?

315
00:23:21,030 --> 00:23:30,780
Siz yekun cavab hesablamaq üçün lazımsız olduğunu qeyd edən bir şey var mı?

316
00:23:30,780 --> 00:23:33,290
Hərhalda daha yaxşı sual olunur, nə məlumat

317
00:23:33,290 --> 00:23:40,680
biz sonuna bütün yol keçirmək lazım deyil?

318
00:23:40,680 --> 00:23:44,280
İndi biz bu iki xətləri baxsaq,

319
00:23:44,280 --> 00:23:47,720
biz yalnız, əvvəlki subproblem qayğı

320
00:23:47,720 --> 00:23:50,910
və biz yalnız biz heç belə uzaq gördüm maksimum qayğı.

321
00:23:50,910 --> 00:23:53,610
Son cavab hesablamaq üçün biz bütün array ehtiyac yoxdur.

322
00:23:53,610 --> 00:23:57,450
Biz son sayı, keçən iki ədəd yalnız lazımdır.

323
00:23:57,450 --> 00:24:02,630
Maksimum üçün subproblem dizi, və son sayı üçün son sayı.

324
00:24:02,630 --> 00:24:07,380
Belə ki, əslində, biz birlikdə bu loops fitil bilər

325
00:24:07,380 --> 00:24:10,460
və xətti kosmosdan daimi yer gedin.

326
00:24:10,460 --> 00:24:15,830
Kömək edib, bu günə qədər burada subproblem, bizim subproblem array rolu əvəz edir.

327
00:24:15,830 --> 00:24:20,020
Belə ki, cari məbləği, bu günə qədər, əvvəlki subproblem cavab deyil.

328
00:24:20,020 --> 00:24:23,450
Və edib, bu günə qədər bizim maks yer tutur.

329
00:24:23,450 --> 00:24:28,100
Biz boyunca getmək kimi Biz maksimum hesablamaq.

330
00:24:28,100 --> 00:24:30,890
Və biz, daimi məkanına linear space getmək

331
00:24:30,890 --> 00:24:36,650
və biz subarray problemin həll xətti var.

332
00:24:36,650 --> 00:24:40,740
>> Suallara bu cür bir müsahibə zamanı əldə edəcək.

333
00:24:40,740 --> 00:24:44,450
Vaxt mürəkkəblik nədir; yer mürəkkəblik nədir?

334
00:24:44,450 --> 00:24:50,600
Daha yaxşı edə bilərəmmi? Ətrafında saxlamaq lazımsız olan şeylər var?

335
00:24:50,600 --> 00:24:55,270
Mən sizə öz almaq lazımdır ki, təhlillərini ön plana keçirmək bunu

336
00:24:55,270 --> 00:24:57,400
Bu problemləri çalışırıq kimi.

337
00:24:57,400 --> 00:25:01,710
Həmişə "Mən daha yaxşı edə bilərəmmi?", Özünüz xahiş edilə

338
00:25:01,710 --> 00:25:07,800
Əslində, biz bu daha yaxşı edə bilər?

339
00:25:07,800 --> 00:25:10,730
Bir oyun sual Sort. Sizə lazımdır, çünki Siz bilməz

340
00:25:10,730 --> 00:25:13,590
ən azı problemin daxil oxuyun.

341
00:25:13,590 --> 00:25:15,570
Lazımdır ki, ən azı problem üçün giriş oxumaq Beləliklə

342
00:25:15,570 --> 00:25:19,580
siz, xətti zaman daha yaxşı edə bilməz deməkdir ki,

343
00:25:19,580 --> 00:25:22,870
və daimi yer daha yaxşı edə bilməz.

344
00:25:22,870 --> 00:25:27,060
Belə ki, bu, əslində, bu problemin ən yaxşı həlli.

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

346
00:25:33,040 --> 00:25:35,190
>> Fond bazarı problemi:

347
00:25:35,190 --> 00:25:38,350
"Müsbət, sıfır və ya mənfi n integers, bir sıra nəzərə alaraq,

348
00:25:38,350 --> 00:25:41,680
ki, n gün ərzində fond qiyməti təmsil

349
00:25:41,680 --> 00:25:44,080
Siz edə bilərsiniz maksimum mənfəət hesablamaq üçün bir funksiyası yazmaq

350
00:25:44,080 --> 00:25:49,350
Bu n gün ərzində düz 1 fond alış-satış ki, verilmiş. "

351
00:25:49,350 --> 00:25:51,690
Əslində, biz, aşağı almaq yüksək satış istəyirəm.

352
00:25:51,690 --> 00:25:58,580
Və biz edə bilər yaxşı gəlir anlamaq istəyirəm.

353
00:25:58,580 --> 00:26:11,500
Mənim tip geri gedir, nə dərhal aydın, sadə cavab, ancaq yavaş var?

354
00:26:11,500 --> 00:26:17,690
Bəli? (Tələbə, anlaşılmaz) >> Bəli.

355
00:26:17,690 --> 00:26:21,470
>> Beləliklə, siz yalnız baxmayaraq getmək və fond qiymətləri görünür

356
00:26:21,470 --> 00:26:30,550
zaman hər bir nöqtəsi, (anlaşılmaz).

357
00:26:30,550 --> 00:26:33,990
[Yu] Okay, belə ki, onun həlli - kompüter öz təklif

358
00:26:33,990 --> 00:26:37,380
ən aşağı və ən yüksək hesablanması mütləq iş deyil

359
00:26:37,380 --> 00:26:42,470
ən yüksək və ən aşağı əvvəl baş bilər, çünki.

360
00:26:42,470 --> 00:26:47,340
Belə ki, bu problemin brute force həlli nədir?

361
00:26:47,340 --> 00:26:53,150
Mən benzersiz mən etmək mənfəət müəyyən etmək üçün lazım olan iki şey var? Sağ.

362
00:26:53,150 --> 00:26:59,410
The brute force həlli - oh, belə ki, Corc təklifini biz yalnız iki gün lazımdır

363
00:26:59,410 --> 00:27:02,880
benzersiz bu iki gün mənfəəti birbaşa müəyyən etmək.

364
00:27:02,880 --> 00:27:06,660
Belə ki, biz almaq / satmaq istədiyiniz hər cüt hesablamaq

365
00:27:06,660 --> 00:27:12,850
mənfi və ya müsbət və ya sıfır ola biləcək mənfəət, hesablamaq.

366
00:27:12,850 --> 00:27:18,000
Biz gün bütün cüt üzərində iterating sonra olun ki, maksimum mənfəət hesablamaq.

367
00:27:18,000 --> 00:27:20,330
Yəni bizim final cavab olacaq.

368
00:27:20,330 --> 00:27:25,730
Və həlli yoxdur, çünki, O (n ^ 2) olmaq n iki cüt seçmək olacaq -

369
00:27:25,730 --> 00:27:30,270
siz son gün arasında seçə bilərsiniz ki, gün.

370
00:27:30,270 --> 00:27:32,580
OK, belə ki, mən burada brute force həlli getmək niyyətində deyiləm.

371
00:27:32,580 --> 00:27:37,420
Mən n log n həll olduğunu demək gedirəm.

372
00:27:37,420 --> 00:27:45,550
Hal-hazırda n log n nə alqoritm bilirik?

373
00:27:45,550 --> 00:27:50,730
Bu oyun sual deyil.

374
00:27:50,730 --> 00:27:54,790
>> Sort Birleştirme. Birleştirme sort, n log n

375
00:27:54,790 --> 00:27:57,760
və əslində, bu problemin həlli yollarından biri istifadə

376
00:27:57,760 --> 00:28:04,400
adlı fikir birləşmə sort cür, ümumiyyətlə, bölmək və qalib.

377
00:28:04,400 --> 00:28:07,570
Aşağıdakı kimi Və fikirdir.

378
00:28:07,570 --> 00:28:12,400
Siz yaxşı alış hesablamaq / sol yarısında cüt satmaq istəyirik.

379
00:28:12,400 --> 00:28:16,480
Yalnız iki gün ərzində ilk n, edə bilərsiniz ən yaxşı mənfəət tapın.

380
00:28:16,480 --> 00:28:19,780
Sonra, ən yaxşı alış oompute / sağ yarısında cüt satmaq istəyirəm

381
00:28:19,780 --> 00:28:23,930
iki gün ərzində belə son n.

382
00:28:23,930 --> 00:28:32,400
İndi isə sual necə geri birlikdə bu həllərin birləşməsi yoxdur, var?

383
00:28:32,400 --> 00:28:36,320
Bəli? (Tələbə, anlaşılmaz)

384
00:28:36,320 --> 00:28:49,890
Okay. >> Mənə bir şəkil çəkmək imkan verir.

385
00:28:49,890 --> 00:29:03,870
Bəli? (George, anlaşılmaz)

386
00:29:03,870 --> 00:29:06,450
Məhz >>. George həll dəqiq hüququdur.

387
00:29:06,450 --> 00:29:10,040
Onun təklif edir, birinci, ən yaxşı alış / satış cüt hesablamaq

388
00:29:10,040 --> 00:29:16,050
və sol yarım baş ki, sol, sol zəng edək.

389
00:29:16,050 --> 00:29:20,790
Best hüququ yarısında baş verir ki, cüt almaq / satmaq.

390
00:29:20,790 --> 00:29:25,180
Biz yalnız bu iki ədəd müqayisədə Lakin biz işin itkin etdiyiniz

391
00:29:25,180 --> 00:29:30,460
Burada almaq və sağ yarısında yerdə satmaq yerləşir.

392
00:29:30,460 --> 00:29:33,810
Biz sol yarısında almaq, sağ yarısında satmaq.

393
00:29:33,810 --> 00:29:38,490
Və həm yarıya indirir yayılır ki, ən yaxşı alış / satış cüt hesablamaq üçün ən yaxşı yol

394
00:29:38,490 --> 00:29:43,480
burada minimum hesablamaq və burada maksimum hesablamaq üçün

395
00:29:43,480 --> 00:29:45,580
və fərq edir.

396
00:29:45,580 --> 00:29:50,850
Alış / satış cüt yalnız burada olduğu iki hallarda Belə ki,

397
00:29:50,850 --> 00:30:01,910
yalnız burada, və ya hər iki yarıya indirir bu üç ədəd tərəfindən müəyyən edilir.

398
00:30:01,910 --> 00:30:06,450
, Geri birlikdə bizim həllərin daxil etmək üçün bizim alqoritm Beləliklə

399
00:30:06,450 --> 00:30:08,350
biz yaxşı alış / satış cüt hesablamaq istəyirəm

400
00:30:08,350 --> 00:30:13,120
biz sol yarım almaq və sağ yarım satmaq yerləşir.

401
00:30:13,120 --> 00:30:16,740
Və bunu ən yaxşı yolu, ilk yarısında ən aşağı qiymət hesablamaq üçün

402
00:30:16,740 --> 00:30:20,360
ən doğru yarısında qiymət və fərq edir.

403
00:30:20,360 --> 00:30:25,390
Ortaya çıxan üç mənfəət, bu üç ədəd, siz üç maksimum almaq

404
00:30:25,390 --> 00:30:32,720
və bu ilk və son gün ərzində edə bilərsiniz ən yaxşı mənfəət var.

405
00:30:32,720 --> 00:30:36,940
Burada mühüm xətləri qırmızı yerləşirsiniz.

406
00:30:36,940 --> 00:30:41,160
Bu sol yarısında cavab hesablamaq üçün rekursiv çağırışdır.

407
00:30:41,160 --> 00:30:44,760
Bu hüququ yarısında cavab hesablamaq üçün rekursiv çağırışdır.

408
00:30:44,760 --> 00:30:50,720
Bu iki loops müvafiq olaraq, sol və sağ yarım üzrə min və max hesablamaq.

409
00:30:50,720 --> 00:30:54,970
İndi mən, həm də yarıya indirir əhatə edən mənfəət hesablamaq

410
00:30:54,970 --> 00:31:00,530
və yekun cavab bu üç maksimum deyil.

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

412
00:31:04,120 --> 00:31:06,420
>> Belə ki, əmin, biz bir alqoritm var, amma daha böyük sual

413
00:31:06,420 --> 00:31:08,290
Bu zaman mürəkkəblik nədir?

414
00:31:08,290 --> 00:31:16,190
Mən birləşmə cür qeyd səbəbi bu formada cavab bölmək ki,

415
00:31:16,190 --> 00:31:19,200
iki və daha sonra geri birlikdə bizim həllərin birləşmə

416
00:31:19,200 --> 00:31:23,580
dəqiq birləşməsi növ formasıdır.

417
00:31:23,580 --> 00:31:33,360
Mənə müddəti ilə gedək.

418
00:31:33,360 --> 00:31:41,340
Biz addımların sayı bir funksiyası t (n) müəyyən edin

419
00:31:41,340 --> 00:31:50,010
n gün,

420
00:31:50,010 --> 00:31:54,350
iki recursive zənglər

421
00:31:54,350 --> 00:32:00,460
hər t (n / 2), başa gedir

422
00:32:00,460 --> 00:32:03,540
və bu zənglər iki var.

423
00:32:03,540 --> 00:32:10,020
İndi, sol yarısının minimum hesablamaq lazımdır

424
00:32:10,020 --> 00:32:17,050
Mən n / 2 dəfə, üstəgəl sağ yarım maksimum nə bilər.

425
00:32:17,050 --> 00:32:20,820
Belə ki, bu yalnız n.

426
00:32:20,820 --> 00:32:25,050
Və sonra bir daimi iş plus.

427
00:32:25,050 --> 00:32:27,770
Bu təkrarlanma tənliklər

428
00:32:27,770 --> 00:32:35,560
dəqiq birləşməsi sort üçün təkrarlanma tənliklər edir.

429
00:32:35,560 --> 00:32:39,170
Və biz bütün növ birləşmə n log n zaman bilirik.

430
00:32:39,170 --> 00:32:46,880
Buna görə də, bizim alqoritmi də log n vaxt n.

431
00:32:46,880 --> 00:32:52,220
Bu iteration mənada edirmi?

432
00:32:52,220 --> 00:32:55,780
Bu yalnız qısa bir recap:

433
00:32:55,780 --> 00:32:59,170
T (n) maksimum mənfəət hesablamaq üçün addımlar sayı

434
00:32:59,170 --> 00:33:02,750
n gün ərzində.

435
00:33:02,750 --> 00:33:06,010
Biz recursive zəng parçalanması yolu

436
00:33:06,010 --> 00:33:11,980
, ilk n / 2 gün bizim həll zəng edir

437
00:33:11,980 --> 00:33:14,490
ki, bir zəng, var

438
00:33:14,490 --> 00:33:16,940
və sonra ikinci yarısında yenidən zəng.

439
00:33:16,940 --> 00:33:20,440
Belə ki, iki zəng var.

440
00:33:20,440 --> 00:33:25,310
Və sonra biz xətti vaxt edə bilərsiniz ki, sol yarısında bir minimum tapmaq

441
00:33:25,310 --> 00:33:29,010
biz xətti vaxt edə bilərsiniz olan sağ yarısı maksimum tapa bilərsiniz.

442
00:33:29,010 --> 00:33:31,570
Belə ki, n / 2 + n / 2 yalnız n.

443
00:33:31,570 --> 00:33:36,020
Sonra biz hesab edirik kimi bəzi daimi iş var.

444
00:33:36,020 --> 00:33:39,860
Bu təkrarlanma tənliklər dəqiq birləşməsi sort üçün təkrarlanma tənliklər edir.

445
00:33:39,860 --> 00:33:55,490
Beləliklə, bizim shuffle alqoritm da n n daxil edin.

446
00:33:55,490 --> 00:33:58,520
Belə ki, necə çox yer biz istifadə olunur?

447
00:33:58,520 --> 00:34:04,910
Nin kodu geri edək.

448
00:34:04,910 --> 00:34:09,420
>> Daha yaxşı bir sual, nə çox yığını çərçivəsində biz heç bir anda var olunur?

449
00:34:09,420 --> 00:34:11,449
Biz recursion istifadə etdiyiniz ildən,

450
00:34:11,449 --> 00:34:23,530
yığını çərçivəsində sayı bizim kosmik istifadə müəyyənləşdirir.

451
00:34:23,530 --> 00:34:29,440
Nin n = 8 hesab edək.

452
00:34:29,440 --> 00:34:36,889
Biz, 8 shuffle zəng

453
00:34:36,889 --> 00:34:41,580
ilk dörd entries haqqında shuffle zəng edəcək

454
00:34:41,580 --> 00:34:46,250
ilk iki entries bir shuffle zəng edəcək.

455
00:34:46,250 --> 00:34:51,550
Belə ki, bizim yığını deyil - bu, bizim yığını deyil.

456
00:34:51,550 --> 00:34:54,980
Və sonra biz, 1 təkrar shuffle zəng

457
00:34:54,980 --> 00:34:58,070
və bizim əsas işi nədir, biz dərhal qayıtmaq.

458
00:34:58,070 --> 00:35:04,700
Biz heç bu çox yığını çərçivəsində daha çox var?

459
00:35:04,700 --> 00:35:08,880
No biz bir sehr etmək hər zaman olduğundan,

460
00:35:08,880 --> 00:35:10,770
shuffle bir recursive sehr,

461
00:35:10,770 --> 00:35:13,950
biz yarısında bizim ölçüsü bölmək.

462
00:35:13,950 --> 00:35:17,020
Biz heç bir anda var yığını çərçivəsində maksimum sayı Beləliklə

463
00:35:17,020 --> 00:35:28,460
log n yığını çərçivəsində əmri edir.

464
00:35:28,460 --> 00:35:42,460
Hər bir yığını çərçivəsində daimi yer var

465
00:35:42,460 --> 00:35:44,410
alan və buna görə də ümumi məbləği

466
00:35:44,410 --> 00:35:49,240
biz heç istifadə sahəsi maksimum O (Giriş n) sahibidir

467
00:35:49,240 --> 00:36:03,040
Ü n gün sayı.

468
00:36:03,040 --> 00:36:07,230
>> İndi, həmişə özünüzü xahiş, "biz daha yaxşı edə bilərəmmi?"

469
00:36:07,230 --> 00:36:12,390
Və xüsusilə də, biz artıq həll etdik bir problem bu azalda bilər?

470
00:36:12,390 --> 00:36:20,040
A ipucu: yalnız əvvəl iki digər problemləri müzakirə, və shuffle olacaq deyil.

471
00:36:20,040 --> 00:36:26,200
Biz maksimal subarray problem bu fond bazarında problem çevirə bilərsiniz.

472
00:36:26,200 --> 00:36:40,100
Biz bunu edə bilər?

473
00:36:40,100 --> 00:36:42,570
Əgər biri? Emmy?

474
00:36:42,570 --> 00:36:47,680
(Emmy, anlaşılmaz)

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

476
00:36:53,860 --> 00:36:59,940
Maksimal subarray problem Belə ki,

477
00:36:59,940 --> 00:37:10,610
biz davamlı subarray bir məbləğ üçün arıyorsanız.

478
00:37:10,610 --> 00:37:16,230
Və səhmlərinin problem üçün Emmy təklifi,

479
00:37:16,230 --> 00:37:30,720
dəyişikliklər və ya deltalar hesab edir.

480
00:37:30,720 --> 00:37:37,440
Bu bir şəkil - Bu fond qiymət,

481
00:37:37,440 --> 00:37:42,610
lakin biz hər ardıcıl gün arasında fərq etdi olduqda -

482
00:37:42,610 --> 00:37:45,200
biz maksimum qiyməti maksimum mənfəət biz edə bilər ki

483
00:37:45,200 --> 00:37:50,070
Burada almaq və burada satmaq əgər.

484
00:37:50,070 --> 00:37:54,240
Amma nin davamlı baxaq - nin subarray problem baxaq.

485
00:37:54,240 --> 00:38:02,510
Odur ki, biz edə bilər - burada burada gedən,

486
00:38:02,510 --> 00:38:08,410
biz bir müsbət dəyişiklik var və sonra burada buradan gedən bir mənfi dəyişiklik yoxdur.

487
00:38:08,410 --> 00:38:14,220
Amma sonra biz böyük bir müsbət dəyişiklik buradan burada gedir.

488
00:38:14,220 --> 00:38:20,930
Bu bizim son mənfəət əldə etmək yekunlaşdırmaq istəyirəm ki, dəyişikliklər var.

489
00:38:20,930 --> 00:38:25,160
Sonra daha çox mənfi dəyişikliklər burada var.

490
00:38:25,160 --> 00:38:29,990
Bizim maksimal subarray problem bizim fond problem azaldılması üçün əsas

491
00:38:29,990 --> 00:38:36,630
gün arasında deltalar hesab edir.

492
00:38:36,630 --> 00:38:40,630
Belə ki, biz, deltalar adlı yeni array yaratmaq

493
00:38:40,630 --> 00:38:43,000
, 0 olmaq üçün ilk giriş başlamaq

494
00:38:43,000 --> 00:38:46,380
və sonra hər delta (i), fərq ki, qoy

495
00:38:46,380 --> 00:38:52,830
mənim giriş array (i) və array (i - 1).

496
00:38:52,830 --> 00:38:55,530
Sonra biz maksimal subarray üçün adi prosedur zəng

497
00:38:55,530 --> 00:39:01,500
bir delta-nin array keçən.

498
00:39:01,500 --> 00:39:06,440
Və maksimal subarray xətti vaxt, çünki

499
00:39:06,440 --> 00:39:09,370
və bu azalma, bu delta array yaradılması bu prosesi,

500
00:39:09,370 --> 00:39:11,780
da xətti dəfə

501
00:39:11,780 --> 00:39:19,060
sonra səhmlər üçün yekun həlli O (n) iş plus O (n) iş hələ də O (n) əsəridir.

502
00:39:19,060 --> 00:39:23,900
Belə ki, biz problemin xətti vaxt həll var.

503
00:39:23,900 --> 00:39:29,610
Hər kəs bu transformasiya anlamaq varmı?

504
00:39:29,610 --> 00:39:32,140
>> Həmişə var ki, ümumiyyətlə, yaxşı bir fikir

505
00:39:32,140 --> 00:39:34,290
siz gördükdə yeni bir problem azaltmaq üçün cəhd edir.

506
00:39:34,290 --> 00:39:37,700
Bir köhnə problem tanış görünür,

507
00:39:37,700 --> 00:39:39,590
köhnə problem onu ​​azaldılması çalışırıq.

508
00:39:39,590 --> 00:39:41,950
Və siz köhnə problem istifadə etdiyiniz bütün vasitələrdən istifadə edə bilər, əgər

509
00:39:41,950 --> 00:39:46,450
yeni problem həll etsin.

510
00:39:46,450 --> 00:39:49,010
Belə ki, bükmək üçün texniki müsahibələr çətin olunur.

511
00:39:49,010 --> 00:39:52,280
Bu problemlər yəqin ki, daha çətin problemlər bəzi

512
00:39:52,280 --> 00:39:54,700
Bir müsahibəsində görə bilərsiniz ki,

513
00:39:54,700 --> 00:39:57,690
Mən yalnız əhatə edən bütün problemləri başa düşmürəm, əgər ki, tamam.

514
00:39:57,690 --> 00:40:01,080
Bu daha çətin problemlər bəzi.

515
00:40:01,080 --> 00:40:03,050
Təcrübə, təcrübə, təcrübə.

516
00:40:03,050 --> 00:40:08,170
Mən sədəqə problemlər bir çox verdi, belə ki, mütləq o oldu.

517
00:40:08,170 --> 00:40:11,690
Və müsahibələr uğurlar. Bütün ehtiyatları, bu link yerləşdirilir

518
00:40:11,690 --> 00:40:15,220
və mənim böyük dostlarından biri, istehza texniki müsahibələr bunu təklif etdi

519
00:40:15,220 --> 00:40:22,050
siz maraqlı etdiyiniz əgər, e-poçt e-poçt ünvanı Yao Will.

520
00:40:22,050 --> 00:40:26,070
Bir sualınız varsa, mənə verə bilərsiniz.

521
00:40:26,070 --> 00:40:28,780
Uşaqlar texniki müsahibələr bağlı konkret sual yoxdur

522
00:40:28,780 --> 00:40:38,440
və ya biz bu günə qədər gördüm hər hansı bir problem?

523
00:40:38,440 --> 00:40:49,910
Okay. Bəli, müsahibələr uğurlar.

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