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 לשעבר, ולוואי שהיה זה כשהייתי underclassman,

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 או גוגל דוק, כדי שיוכלו לראות אותך חי קידוד

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
אז אל תפחדו לעלות עם אלגוריתם הפשוט 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
במקום כזה שכל התמורות של המספרים השלמים n סבירות באותה מידה. "

78
00:04:20,209 --> 00:04:23,470
ואניח שיש לך זמין במחולל מספר שלם אקראי

79
00:04:23,470 --> 00:04:30,980
שיוצר שלם בטווח שבין 0 ל i, מגוון חצי.

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 log 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
ומאז יש לנו n הסרות, זה מוביל לדשדוש 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 20000,

181
00:12:16,170 --> 00:12:18,630
או פשוט לבחור 3 מליארד דולרים.

182
00:12:18,630 --> 00:12:20,760
ובכן, הבחירה הטובה ביותר היא לקחת את כל המספרים.

183
00:12:20,760 --> 00:12:24,350
זה -1, למרות היותו שלילי,

184
00:12:24,350 --> 00:12:31,340
כל הסכום הוא טוב יותר מאשר היו לי לא לקחת -1.

185
00:12:31,340 --> 00:12:36,460
אז אחת העצות שהזכרתי קודם לכן היה להגדיר בבירור את המובן מאליו

186
00:12:36,460 --> 00:12:40,540
ופתרון בכוח הזרוע הראשונה.

187
00:12:40,540 --> 00:12:44,340
מה הפתרון בכוח הזרוע בבעיה זו? כן?

188
00:12:44,340 --> 00:12:46,890
[ג'יין] ובכן, אני חושב שהפתרון בכוח הזרוע

189
00:12:46,890 --> 00:12:52,600
יהיה לסכם את כל הצירופים האפשריים (לא ברור).

190
00:12:52,600 --> 00:12:58,250
[יו] אוקיי. אז הרעיון של ג'יין הוא לקחת את כל האפשר -

191
00:12:58,250 --> 00:13:01,470
אני פרפרזה - הוא לקחת את כל 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
לא n ^ 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
הפתרון שלנו הוא לא יותר גרוע מ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
רעיון אחד הוא - אנחנו כבר קבלנו הבעיה המקורית שלנו,

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
אז אני מקודד את זה, ובואו אסתכל על מה מדובר.

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
שילוב של מערך זה ואת התשובות לsubproblems הקודם במערך הזה? כן?

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 (i - 1).

285
00:20:50,130 --> 00:20:57,300
ובואו נקראים א מערך הקלט שלי

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 i - 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 חדש, subproblems.

305
00:22:27,320 --> 00:22:32,330
הכניסה הראשונה היא 0 או הערך הראשון, למקסימום של שני אלה.

306
00:22:32,330 --> 00:22:35,670
ועבור שאר subproblems

307
00:22:35,670 --> 00:22:39,810
אנו משתמשים בהישנות המדויקת שרק התגליתי.

308
00:22:39,810 --> 00:22:49,960
כעת אנו מחשבים את המקסימום של מערך subproblems שלנו, וזו התשובה הסופית שלנו.

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 בתוך 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
לחשב את הרווח המקסימאלי שאנחנו עושים אחרי iterating על כל הזוגות של ימים.

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 log n.

372
00:27:37,420 --> 00:27:45,550
מה עושה כיום אלגוריתם אתה יודע שזה n log 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 1 במשך ימים.

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
אז זה פשוט n.

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
וכולנו יודעים שמיון המיזוג הוא log 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 1,

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 (logn)

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
תשקלו את השינויים, או deltas.

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 (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]