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
أنا 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
هيكل حديث لبرنامج postion الهندسة،

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 حتى يتمكنوا من أراك يعيش الترميز

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
وسوف يطلب منك، مثل، ما هو الوقت وتعقيد الفضاء، يا كبير؟

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
لذلك لا تخافوا من أجل التوصل إلى أبسط خوارزمية 1

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، اكتب الدالة التي المراوغات الصفيف

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، 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 التكلفة

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 العملية،

116
00:07:32,170 --> 00:07:41,520
وبما أننا قد ن عمليات الإزالة، وهذا يؤدي إلى خلط ورق اللعب (ن ^ 2) O.

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، ونحن ي اختيار موقع عشوائي

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
وبالمناسبة لدينا نختار ي مؤشر لمبادلة،

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
لذلك "نظرا لمجموعة من الأعداد الصحيحة، صالحهم بشكل ايجابي، صفر، سلبية،

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
ثم إما أن أختار 1،000 و 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
A الأدنى على المؤشر ومؤشر الحد الأعلى

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
ونهاية لجميع مداخل> أو = لبدء، ون <،

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
بحيث واحد للحلقة.

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
ذلك أن آخر حلقة لل. لذلك لدينا ثلاث حلقات متداخلة ل، N ^ 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
العثور على مبلغ الحد الأقصى من أي subarray في مجموعة [O، N-1].

226
00:15:37,470 --> 00:15:47,400
والآن لدينا subproblem جديدة، حيث نعلم، في فهرسنا الحالي ط،

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
حتى لقد ترميز I هذا الأمر، ودعونا نلقي نظرة على ما يعنيه هذا.

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
إذا كان الأمر كذلك أسميه الدخول في موقف ط subproblem (ط)،

274
00:19:50,800 --> 00:19:54,910
كيف يمكنني استخدام ردا على subproblem السابقة

275
00:19:54,910 --> 00:19:59,360
للإجابة على هذا subproblem؟

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
ثم قمت بإضافة subproblem الحالي.

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 الجواب لsubproblem (ط - 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
ثم مجموع الحد الأقصى أستطيع تحقيقه هو الجواب على subproblem السابقة

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
وبالتالي فإن الجواب هو أقصى 0، subproblem ط - 1، بالإضافة إلى دخول مجموعة الحالية.

295
00:21:42,860 --> 00:21:46,150
هل هذا تكرار معنى؟

296
00:21:46,150 --> 00:21:50,840
تكرار لدينا، كما اكتشفنا للتو، هو أنا subproblem

297
00:21:50,840 --> 00:21:54,740
يساوي الحد الأقصى للsubproblem السابقة بالإضافة إلى مشاركتي مجموعة الحالية،

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
يفعل الخطية حملة عبر مجموعة subproblem

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
لذلك نحن إنشاء مجموعة جديدة subproblem، المشاكل الثانوية.

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
نحن نهتم فقط عن subproblem السابقة،

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
مشاركة رقم للمجموعة subproblem، وآخر رقم لأقصى حد.

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
مجموع الحالي حتى الآن، وهنا، يحل محل دور subproblem، لدينا مجموعة subproblem.

327
00:24:15,830 --> 00:24:20,020
مجموع الحالي بذلك، حتى الآن، هو الإجابة على subproblem السابقة.

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 ن هذه الأيام. "

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
إذا حددنا ر ظيفة (ن) ليكون عدد من الخطوات

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
T (ن) هو عدد من الخطوات لحساب الربح الأقصى

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
>> A أفضل السؤال هو، كم عدد إطارات المكدس لدينا أي وقت مضى في أي لحظة؟

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
هو بناء على أمر من الأطر سجل ن المكدس.

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 (سجل ن) الفضائية

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
A تلميح: ناقشنا اثنين فقط مشاكل أخرى قبل ذلك، وانها لن تكون المراوغه.

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
ومن ثم لكل الدلتا (ط)، واسمحوا أن يكون الفرق

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 (ن) العمل بالإضافة إلى 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]