1
00:00:00,000 --> 00:00:02,640
[Powered by Google Translate] سمینار: مصاحبه فنی]

2
00:00:02,640 --> 00:00:04,630
[کنی یو، دانشگاه هاروارد]

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
من سابق TF CS، و من آرزو می کنم که تا به حال زمانی که من شاگرد سالهای اول بود،

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
آنها در تلاش برای سعی کنید بهترین راه حل برای پیدا کردن 1،

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
"با توجه به آرایه ای از اعداد صحیح N، نوشتن یک تابع است که shuffles آرایه

77
00:04:14,790 --> 00:04:20,209
در چنین مکانی است که تمام جایگشت از اعداد صحیح N هستند به همان اندازه احتمال دارد. "

78
00:04:20,209 --> 00:04:23,470
و فرض شما در دسترس ژنراتور عدد صحیح تصادفی

79
00:04:23,470 --> 00:04:30,980
که با تولید یک عدد صحیح در یک محدوده از 0 تا من، در محدوده 1/2 است.

80
00:04:30,980 --> 00:04:32,970
آیا هر کس درک این سوال؟

81
00:04:32,970 --> 00:04:39,660
من به شما یک آرایه از اعداد صحیح N را، و من می خواهم شما را به این سو و ان سو حرکت کردن آن است.

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
برخی از ایده ها چه هستند؟ آیا می توانم آن را به شما به عنوان N ^ 2، N ورود N، N؟

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
محاسبه عدد تصادفی، عدد صحیح تصادفی در یک محدوده از 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 (n) است

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
این سو و ان سو حرکت کردن فیشر یاتس است.

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 از آرایه، من تا n-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
باشه. دانلود.

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
آرایه ورودی است. هر subarray 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 و 20،000،

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
من تکرار گفتار هستم - را به هر subarray ممکن است مداوم،

192
00:13:01,470 --> 00:13:07,840
محاسبه مجموع آن، و سپس حداکثر از همه subarrays مداوم.

193
00:13:07,840 --> 00:13:13,310
شناسایی منحصر به فرد subarray در آرایه ورودی من؟

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
منحصر به فرد تعیین مداوم subarray.

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
منحصر به فرد تعیین subarray مداوم ما است.

203
00:13:47,200 --> 00:13:51,680
بنابراین اگر ما در تمام نوشته های آغاز ممکن است تکرار،

204
00:13:51,680 --> 00:13:58,320
و برای تمام نوشته های پایان> یا = برای شروع، و <N،

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
O بزرگ از این راه حل چیست؟

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

209
00:14:16,660 --> 00:14:18,860
نه کاملا ^ 2 نفر شده است.

210
00:14:18,860 --> 00:14:25,250
توجه داشته باشید که ما از 0 تا n تکرار،

211
00:14:25,250 --> 00:14:27,520
به طوری که یک حلقه for است.

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
به طوری که یکی دیگر از حلقه. بنابراین ما باید تو در تو حلقه for، N ^ 3.

215
00:14:43,810 --> 00:14:46,560
باشه. این می رود به عنوان یک نقطه شروع است.

216
00:14:46,560 --> 00:14:53,180
راه حل ما این است که هیچ بدتر از N ^ 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
پیدا کردن مجموع حداکثر هر subarray در محدوده [O، N-1].

226
00:15:37,470 --> 00:15:47,400
و در حال حاضر ما زیر مسئله جدید، جایی که ما می دانیم، در شاخص فعلی ما،

227
00:15:47,400 --> 00:15:52,520
ما می دانیم که ما باید نتیجه بگیریم. subarray ما باید در فهرست جاری به پایان برسد.

228
00:15:52,520 --> 00:15:57,640
بنابراین مشکل باقی مانده است، که در آن باید subarray ما شروع کنیم؟

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، برنامه ای به نام subarray وجود دارد،

232
00:16:16,230 --> 00:16:19,470
و آن طول می کشد تعدادی از آیتم ها،

233
00:16:19,470 --> 00:16:25,550
آن را می گرداند و حداکثر مجموع subarray در فهرست خورده است.

234
00:16:25,550 --> 00:16:29,920
بنابراین در این حالت، حداکثر subarray ما 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
اجازه دهید نگاهی به این subarray.

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
اجازه دهید نگاهی به subarray حداکثر است که در هر یک از این شاخص ها به پایان رسید.

250
00:17:34,160 --> 00:17:40,780
چه خبر، حداکثر subarray است که در مقام اول تا؟

251
00:17:40,780 --> 00:17:46,310
[دانشجو] صفر. >> صفر. فقط -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، چه subarray حداکثر برای پایان دادن به آن موقعیت

257
00:18:08,690 --> 00:18:12,910
که در آن -4 است؟ صفر.

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
این حاکی از آن است که subarray حداکثر به پایان می رسد در این شاخص،

267
00:19:00,010 --> 00:19:04,970
و در جایی قبل از آن آغاز شده است.

268
00:19:04,970 --> 00:19:09,630
آیا هر کس درک این subarray تبدیل شده؟

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
بنابراین اگر من به ورود در موقعیت زیر مسئله (من)،

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 اشاره به پاسخ برای زیر مسئله (I - 1).

285
00:20:50,130 --> 00:20:57,300
و اجازه دهید با ورودی آرایه A. من تماس بگیرید

286
00:20:57,300 --> 00:21:01,470
به منظور پیدا کردن subarray حداکثر که در موقعیت من به پایان می رسد،

287
00:21:01,470 --> 00:21:03,980
من دو انتخاب است: من هم می تواند ادامه subarray

288
00:21:03,980 --> 00:21:09,790
که در شاخص های قبلی به پایان رسید، و یا شروع یک آرایه جدید.

289
00:21:09,790 --> 00:21:14,190
اگر من به ادامه subarray آغاز شده است که در شاخص های قبلی،

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
اما، من نیز انتخاب شروع subarray جدید،

293
00:21:27,550 --> 00:21:30,830
که در این صورت مجموع 0 است.

294
00:21:30,830 --> 00:21:42,860
1، به علاوه ورود آرایه - پس از پاسخ، من در زیر مسئله حداکثر از 0 است.

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
که به معنی ادامه subarray قبلی،

299
00:22:01,490 --> 00:22:07,250
0 یا شروع یک subarray جدید در شاخص فعلی من است.

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
خب، یک چیز را به یاد داشته باشید این است که من به نام malloc در اینجا با N اندازه.

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
و ما نیز راه حل خطی مشکل subarray ما.

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
"با توجه به آرایه ای از اعداد صحیح N، مثبت، صفر یا منفی،

348
00:25:38,350 --> 00:25:41,680
است که نشان دهنده قیمت سهام در طول روز N

349
00:25:41,680 --> 00:25:44,080
ارسال یک تابع حداکثر سود شما می توانید برای محاسبه

350
00:25:44,080 --> 00:25:49,350
با توجه به این که شما در خرید و فروش دقیقا 1 سهام در این روزها N است. "

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)، به دلیل وجود دارد N را انتخاب کنید از دو جفت -

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
من قصد دارم به شما بگویم که ورود N N راه حل وجود دارد.

372
00:27:37,420 --> 00:27:45,550
چه الگوریتم آیا شما در حال حاضر می دانیم که N ورود N؟

373
00:27:45,550 --> 00:27:50,730
این ترفند نیست.

374
00:27:50,730 --> 00:27:54,790
>> ادغام مرتب سازی بر اساس. ادغام مرتب کردن بر اساس n log n استفاده شده است،

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
یافتن بهترین سود شما می توانید فقط با N برای اولین بار بیش از دو روز است.

380
00:28:16,480 --> 00:28:19,780
سپس شما می خواهید به oompute بهترین خرید / فروش جفت در نیمه سمت راست،

381
00:28:19,780 --> 00:28:23,930
به طوری که N گذشته به بیش از دو روز است.

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
سه نتیجه سود، این سه عدد، شما را حداکثر از سه،

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
برای روز N،

420
00:31:50,010 --> 00:31:54,350
ما دو بازگشتی تماس

421
00:31:54,350 --> 00:32:00,460
هر رفتن به هزینه T (n / 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
که من می توانم در N / 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
و همه ما می دانیم که مرتب سازی بر اساس ادغام ورود N N زمان است.

430
00:32:39,170 --> 00:32:46,880
بنابراین، الگوریتم ما این است که n log n استفاده زمان.

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
T (n) تعداد مراحل به محاسبه حداکثر سود است

434
00:32:59,170 --> 00:33:02,750
در طول این دوره از روز N.

435
00:33:02,750 --> 00:33:06,010
راه ما تقسیم کردن تماس های بازگشتی ما

436
00:33:06,010 --> 00:33:11,980
خواستار راه حل ما بر روی N / 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
بنابراین N / 2 + N / 2 فقط N است.

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
از این رو، الگوریتم این سو و ان سو حرکت کردن ما نیز n log n استفاده است.

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 (log n است) فضا است

467
00:35:49,240 --> 00:36:03,040
که در آن N تعداد روز است.

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
ما می توانیم از این مشکل بازار سهام را به حداکثر مشکل subarray تبدیل کنید.

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
(امی، ناخوانا)

475
00:36:47,680 --> 00:36:53,860
[یو] دقیقا.

476
00:36:53,860 --> 00:36:59,940
پس مشکل حداکثر subarray،

477
00:36:59,940 --> 00:37:10,610
ما به دنبال مجموع بیش از یک subarray پیوسته است.

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
اما اجازه دهید نگاهی مداوم - اجازه دهید نگاهی به مشکل subarray.

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
کلیدی برای کاهش مشکل سهام ما را به مشکل subarray ما حداکثر

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
سپس ما فراخوانی روال معمول خود را برای subarray حداکثر

497
00:38:55,530 --> 00:39:01,500
عبور در آرایه دلتا.

498
00:39:01,500 --> 00:39:06,440
و چون subarray حداکثر زمان خطی است،

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 (N) کار علاوه O (N) کار است، هنوز هم O (N) کار است.

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]