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
[דאס איז קס50.] [CS50.TV]

4
00:00:08,910 --> 00:00:12,420
הי אַלעמען, איך בין קעני. איך בין דערווייַל אַ יינגער געלערנט קאָמפּיוטער וויסנשאַפֿט.

5
00:00:12,420 --> 00:00:17,310
איך בין אַ ערשטע קס טף, און איך ווינטשן איך געהאט דעם ווען איך איז געווען אַ ונדערקלאַססמאַן,

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
אָדער קאָללאַבעדיט אָדער אַ גוגל שולדבאַנק אַזוי זיי קענען זען איר לעבן קאָודינג

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
גרויס אָ צייַט קאַמפּלעקסיטי אָדער פּלאַץ קאַמפּלעקסיטי,

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 ינטאַדזשערז, שרייַבן אַ פֿונקציע וואָס שאַפאַלז די מענגע

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
איך געבן איר אַ מענגע פון ​​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 קלאָץ ן, ען?

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
און וואָס איז אַן אָ (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
יעדער באַזייַטיקונג ינקערז אַ אָ (N) אָפּעראַציע,

116
00:07:32,170 --> 00:07:41,520
און זינט מיר האָבן N רימווואַלז, דאָס פירט צו אַן אָ (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
און מיר האַלטן שפּור, און דאַן מיר לאָזן די מנוחה פון אונדזער מענגע פֿאַר די ונשופפלעד חלק.

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
און אַלץ צו די רעכט איז ונשופפלעד.

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
אין די ונשופפלעד חלק פון די מענגע, איך צו 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
פון קיין קאָנטינועאָוס סובאַררייַ פון די אַרייַנשרייַב מענגע. "

168
00:11:24,720 --> 00:11:28,370
אַ בייַשפּיל דאָ איז, אין דעם פאַל ווו אַלע נומערן זענען positive,

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
אָדער איך נאָר קלייַבן די 3000000000.

182
00:12:18,630 --> 00:12:20,760
נו, דער בעסטער ברירה איז צו נעמען אַלע די נומערן.

183
00:12:20,760 --> 00:12:24,350
דאס -1, טראָץ זייַענדיק נעגאַטיוו,

184
00:12:24,350 --> 00:12:31,340
די גאנצע סאַכאַקל איז בעסער ווי זענען איך נישט צו נעמען -1.

185
00:12:31,340 --> 00:12:36,460
אַזוי איינער פון די עצות איך דערמאנט פריער איז געווען צו שטאַט דער קלאר קלאָר ווי דער טאָג

186
00:12:36,460 --> 00:12:40,540
און די ברוט קראַפט לייזונג ערשטער.

187
00:12:40,540 --> 00:12:44,340
וואָס איז די ברוט קראַפט לייזונג אין דעם פּראָבלעם? יאָ?

188
00:12:44,340 --> 00:12:46,890
[דזשיין] גוט, איך טראַכטן די ברוט קראַפט לייזונג

189
00:12:46,890 --> 00:12:52,600
וואָלט זייַן צו לייגן אַרויף אַלע די מעגלעך קאַמבאַניישאַנז (אַנינטעלאַדזשאַבאַל).

190
00:12:52,600 --> 00:12:58,250
[יו] אָוקיי. אַזוי דזשיין ס געדאַנק איז צו נעמען יעדער מעגלעך -

191
00:12:58,250 --> 00:13:01,470
איך בין פּעראַפרייזינג - איז צו נעמען יעדער מעגלעך קעסיידערדיק סובאַררייַ,

192
00:13:01,470 --> 00:13:07,840
צונויפרעכענען זייַן סאַכאַקל, און דאַן נעמען די מאַקסימום פון אַלע די מעגלעך קעסיידערדיק סובאַררייַס.

193
00:13:07,840 --> 00:13:13,310
וואָס יוניקלי יידענטאַפייז אַ סובאַררייַ אין מיין אַרייַנשרייַב מענגע?

194
00:13:13,310 --> 00:13:17,380
ווי, וואָס צוויי זאכן טאָן איך דאַרפֿן? יאָ?

195
00:13:17,380 --> 00:13:19,970
(תּלמיד, אַנינטעלאַדזשאַבאַל) >> רעכט.

196
00:13:19,970 --> 00:13:22,130
א נידעריקער געבונדן אויף די אינדעקס און אַ אויבערשטער געבונדן אינדעקס

197
00:13:22,130 --> 00:13:28,300
יוניקלי דאַטערמאַנז אַ קעסיידערדיק סובאַררייַ.

198
00:13:28,300 --> 00:13:31,400
[ווייַבלעך תּלמיד] ביסט מיר עסטאַמייטינג עס ס אַ מענגע פון ​​יינציק נומערן?

199
00:13:31,400 --> 00:13:34,280
[יו] נומ אזוי איר קשיא איז, זענען מיר אַסומינג אונדזער מענגע -

200
00:13:34,280 --> 00:13:39,000
איז אונדזער מענגע אַלע יינציק נומערן, און דער ענטפער איז ניט.

201
00:13:39,000 --> 00:13:43,390
>> אויב מיר נוצן אונדזער ברוט קראַפט לייזונג, דעמאָלט דער אָנהייב / סוף ינדיסעס

202
00:13:43,390 --> 00:13:47,200
יוניקלי דאַטערמאַנז אונדזער קעסיידערדיק סובאַררייַ.

203
00:13:47,200 --> 00:13:51,680
אַזוי אויב מיר יטעראַטע פֿאַר אַלע מעגלעך אָנהייב איינסן,

204
00:13:51,680 --> 00:13:58,320
און פֿאַר אַלע סוף איינסן> אָדער = צו אָנהייבן, און <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
וואָס איז די גרויס אָ פון דעם לייזונג?

208
00:14:12,230 --> 00:14:16,660
טימעוויסע.

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
אויב איר נעמען קס124, וואָס איז אַלגאָריטהמס און דאַטאַ סטראַקטשערז,

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
געפֿינען די מאַקסימום סאַכאַקל פון קיין סובאַררייַ אין אַ קייט [אָ, N-1].

226
00:15:37,470 --> 00:15:47,400
און איצט מיר האָבן אַ נייַ סובפּראָבלעם, ווו מיר וויסן, אין אונדזער קראַנט אינדעקס איך,

227
00:15:47,400 --> 00:15:52,520
מיר וויסן מיר מוזן פאַרענדיקן דאָרט. אונדזער סובאַררייַ מוזן סוף בייַ די קראַנט אינדעקס.

228
00:15:52,520 --> 00:15:57,640
אַזוי די רוען פּראָבלעם איז, ווו זאָל מיר אָנהייבן אונדזער סובאַררייַ?

229
00:15:57,640 --> 00:16:05,160
טוט דעם מאַכן זינען? אָוקיי.

230
00:16:05,160 --> 00:16:12,030
אַזוי איך ווע קאָדעד דעם אַרויף, און לאָזן ס קוק אין וואָס דעם מיטל.

231
00:16:12,030 --> 00:16:16,230
אין די קאָדירעקטאָרי, דאָרט ס אַ פּראָגראַם גערופן סובאַררייַ,

232
00:16:16,230 --> 00:16:19,470
און עס נעמט נומער פון זאכן,

233
00:16:19,470 --> 00:16:25,550
און עס קערט די מאַקסימאַל סובאַררייַ סאַכאַקל אין מיין שאַפאַלד רשימה.

234
00:16:25,550 --> 00:16:29,920
אַזוי אין דעם פאַל, אונדזער מאַקסימאַל סובאַררייַ איז 3.

235
00:16:29,920 --> 00:16:34,850
און אַז ס גענומען דורך נאָר ניצן 2 און 1.

236
00:16:34,850 --> 00:16:38,050
זאל ס 'לויפן עס ווידער. עס ס אויך 3.

237
00:16:38,050 --> 00:16:40,950
אבער דאָס מאָל, טאָן ווי מיר גאַט די 3.

238
00:16:40,950 --> 00:16:46,690
מיר גענומען די - מיר נאָר נעמען די 3 זיך

239
00:16:46,690 --> 00:16:49,980
ווייַל עס ס סעראַונדאַד דורך נעגאַטיוועס אויף ביידע זייטן,

240
00:16:49,980 --> 00:16:55,080
וואָס וועט ברענגען אַ סאַכאַקל <3.

241
00:16:55,080 --> 00:16:57,820
זאל ס 'לויפן אויף 10 זאכן.

242
00:16:57,820 --> 00:17:03,200
דאס מאָל עס ס 7, מיר נעמען די לידינג 3 און 4.

243
00:17:03,200 --> 00:17:09,450
דאס מאָל עס ס 8, און מיר קריגן אַז דורך גענומען 1, 4 און 3.

244
00:17:09,450 --> 00:17:16,310
אַזוי צו געבן איר אַ ינטוישאַן אויף ווי מיר קענען סאָלווע דעם פארוואנדלען פּראָבלעם,

245
00:17:16,310 --> 00:17:18,890
לאָזן ס נעמען אַ קוק אין דעם סובאַררייַ.

246
00:17:18,890 --> 00:17:23,460
מיר רע געגעבן דעם אַרייַנשרייַב מענגע, און מיר וויסן די ענטפער איז 8.

247
00:17:23,460 --> 00:17:26,359
מיר נעמען די 1, 4, און 3.

248
00:17:26,359 --> 00:17:29,090
אבער לאָזן ס קוק אין ווי מיר פאקטיש גאַט אַז ענטפֿערן.

249
00:17:29,090 --> 00:17:34,160
זאל ס קוק בייַ די מאַקסימאַל סובאַררייַ אַז געענדיקט אין יעדער פון די ינדיסעס.

250
00:17:34,160 --> 00:17:40,780
וואָס ס די מאַקסימאַל סובאַררייַ וואָס האט צו סוף בייַ דער ערשטער שטעלע?

251
00:17:40,780 --> 00:17:46,310
[תּלמיד] זעראָ. >> זעראָ. נאָר טאָן ניט נעמען די -5.

252
00:17:46,310 --> 00:17:50,210
דאָ עס ס געגאנגען צו זייַן 0 ווי געזונט. יאָ?

253
00:17:50,210 --> 00:17:56,470
(תּלמיד, אַנינטעלאַדזשאַבאַל)

254
00:17:56,470 --> 00:17:58,960
[יו] אָה, אנטשולדיגט, עס איז אַ -3.

255
00:17:58,960 --> 00:18:03,220
אַזוי דאָס איז אַ 2, דאָס איז אַ -3.

256
00:18:03,220 --> 00:18:08,690
אָוקיי. אַזוי -4, וואָס ס די מאַקסימאַל סובאַררייַ צו סוף אַז שטעלע

257
00:18:08,690 --> 00:18:12,910
ווו -4 איז בייַ? נול.

258
00:18:12,910 --> 00:18:22,570
איינער? 1, 5, 8.

259
00:18:22,570 --> 00:18:28,060
איצט, איך מוזן סוף בייַ דער אָרט ווו -2 איז בייַ.

260
00:18:28,060 --> 00:18:39,330
אַזוי 6, 5, 7, און די לעצטע איינער איז 4.

261
00:18:39,330 --> 00:18:43,480
געוואוסט אַז די ביסט מיין איינסן

262
00:18:43,480 --> 00:18:48,130
פֿאַר די פארוואנדלען פּראָבלעם ווו איך מוזן סוף אין יעדער פון די ינדיסעס,

263
00:18:48,130 --> 00:18:51,410
דעריבער מיין לעצט ענטפער איז נאָר, נעמען אַ ויסקערן אַריבער,

264
00:18:51,410 --> 00:18:53,580
און נעמען די מאַקסימום נומער.

265
00:18:53,580 --> 00:18:55,620
אַזוי אין דעם פאַל עס ס 8.

266
00:18:55,620 --> 00:19:00,010
דאס ימפּלייז אַז די מאַקסימאַל סובאַררייַ ענדס בייַ דעם אינדעקס,

267
00:19:00,010 --> 00:19:04,970
און אנגעהויבן ערגעץ איידער עס.

268
00:19:04,970 --> 00:19:09,630
טוט אַלעמען פֿאַרשטיין דעם פארוואנדלען סובאַררייַ?

269
00:19:09,630 --> 00:19:22,160
>> אָוקיי. נו, לאָזן ס רעכענען אויס די ריקעראַנס פֿאַר דעם.

270
00:19:22,160 --> 00:19:27,990
זאל ס באַטראַכטן נאָר דער ערשטער ביסל איינסן.

271
00:19:27,990 --> 00:19:35,930
אַזוי דאָ עס איז געווען 0, 0, 0, 1, 5, 8.

272
00:19:35,930 --> 00:19:39,790
און דעמאָלט דאָרט איז געווען אַ -2 דאָ, און אַז געבראכט עס אַראָפּ צו 6.

273
00:19:39,790 --> 00:19:50,800
אַזוי אויב איך רופן די פּאָזיציע אין שטעלע איך סובפּראָבלעם (איך),

274
00:19:50,800 --> 00:19:54,910
ווי קענען איך נוצן דעם ענטפער צו אַ פֿריִערדיקע סובפּראָבלעם

275
00:19:54,910 --> 00:19:59,360
צו ענטפֿערן דעם סובפּראָבלעם?

276
00:19:59,360 --> 00:20:04,550
אויב איך קוק בייַ, לאָזן ס זאָגן, דעם פּאָזיציע.

277
00:20:04,550 --> 00:20:09,190
ווי קענען איך צונויפרעכענען דער ענטפֿערן 6 דורך קוקן בייַ

278
00:20:09,190 --> 00:20:18,780
אַ קאָמבינאַציע פון ​​דעם מענגע און די ענטפֿערס צו פֿריִערדיקע סובפּראָבלעמס אין דעם מענגע? יא?

279
00:20:18,780 --> 00:20:22,800
[ווייַבלעך תּלמיד] איר נעמען די מענגע פון ​​סאַמז

280
00:20:22,800 --> 00:20:25,430
אין די שטעלע רעכט איידער עס, אַזוי די 8,

281
00:20:25,430 --> 00:20:32,170
און דאַן איר לייגן די קראַנט סובפּראָבלעם.

282
00:20:32,170 --> 00:20:36,460
[יו] אזוי איר פאָרשלאָג איז צו קוקן בייַ די צוויי נומערן,

283
00:20:36,460 --> 00:20:40,090
דעם נומער און דעם נומער.

284
00:20:40,090 --> 00:20:50,130
אַזוי דעם 8 רעפערס צו די ענטפער פֿאַר די סובפּראָבלעם (איך - 1).

285
00:20:50,130 --> 00:20:57,300
און לאָזן ס רופן מיין אַרייַנשרייַב מענגע יי

286
00:20:57,300 --> 00:21:01,470
אין סדר צו געפֿינען אַ מאַקסימאַל סובאַררייַ אַז ענדס בייַ שטעלע איך,

287
00:21:01,470 --> 00:21:03,980
איך האב צוויי ברירות: איך קענען אָדער פאָרזעצן דעם סובאַררייַ

288
00:21:03,980 --> 00:21:09,790
אַז געענדיקט אין די פֿריִערדיקע אינדעקס, אָדער אָנהייבן אַ נייַ מענגע.

289
00:21:09,790 --> 00:21:14,190
אויב איך געווען צו פאָרזעצן די סובאַררייַ אַז אנגעהויבן בייַ די פֿריִערדיקע אינדעקס,

290
00:21:14,190 --> 00:21:19,260
דעריבער די מאַקסימום סאַכאַקל איך קענען דערגרייכן איז דער ענטפער צו די פֿריִערדיקע סובפּראָבלעם

291
00:21:19,260 --> 00:21:24,120
פּלוס די קראַנט מענגע פּאָזיציע.

292
00:21:24,120 --> 00:21:27,550
אבער, איך אויך האָבן די ברירה פון סטאַרטינג אַ נייַ סובאַררייַ,

293
00:21:27,550 --> 00:21:30,830
אין וואָס פאַל די סאַכאַקל איז 0.

294
00:21:30,830 --> 00:21:42,860
אַזוי דער ענטפער איז מאַקס פון 0, סובפּראָבלעם איך - 1, פּלוס די קראַנט מענגע פּאָזיציע.

295
00:21:42,860 --> 00:21:46,150
טוט דעם ריקעראַנס מאַכן זינען?

296
00:21:46,150 --> 00:21:50,840
אונדזער ריקעראַנס, ווי מיר נאָר דיסקאַווערד, איז סובפּראָבלעם איך

297
00:21:50,840 --> 00:21:54,740
איז גלייַך צו די מאַקסימום פון די פֿריִערדיקע סובפּראָבלעם פּלוס מיין קראַנט מענגע פּאָזיציע,

298
00:21:54,740 --> 00:22:01,490
וואָס מיטל פאָרזעצן די פֿריִערדיקע סובאַררייַ,

299
00:22:01,490 --> 00:22:07,250
אָדער 0, אָנהייבן אַ נייַ סובאַררייַ בייַ מיין קראַנט אינדעקס.

300
00:22:07,250 --> 00:22:10,060
און אַמאָל מיר האָבן געבויט אַרויף דעם טיש פון סאַלושאַנז, דעמאָלט אונדזער לעצט ענטפֿערן,

301
00:22:10,060 --> 00:22:13,950
נאָר טאָן אַ לינעאַר ויסקערן אַריבער די סובפּראָבלעם מענגע

302
00:22:13,950 --> 00:22:19,890
און נעמען די מאַקסימום נומער.

303
00:22:19,890 --> 00:22:23,330
דאס איז אַן פּינטלעך ימפּלאַמענטיישאַן פון וואָס איך נאָר געזאגט.

304
00:22:23,330 --> 00:22:27,320
אַזוי מיר שאַפֿן אַ נייַ סובפּראָבלעם מענגע, סובפּראָבלעמס.

305
00:22:27,320 --> 00:22:32,330
דער ערשטער פּאָזיציע איז אָדער 0 אָדער דער ערשטער פּאָזיציע, די מאַקסימום פון יענע צוויי.

306
00:22:32,330 --> 00:22:35,670
און פֿאַר די מנוחה פון די סובפּראָבלעמס

307
00:22:35,670 --> 00:22:39,810
מיר נוצן די פּינטלעך ריקעראַנס מיר נאָר דיסקאַווערד.

308
00:22:39,810 --> 00:22:49,960
איצט מיר צונויפרעכענען די מאַקסימום פון אונדזער סובפּראָבלעמס מענגע, און אַז ס אונדזער לעצט ענטפֿערן.

309
00:22:49,960 --> 00:22:54,130
>> אַזוי ווי פיל פּלאַץ זענען מיר ניצן אין דעם אַלגערידאַם?

310
00:22:54,130 --> 00:23:01,470
אויב איר ווע נאָר גענומען קס50, דעמאָלט איר זאל נישט האָבן דיסקאַסט פּלאַץ זייער פיל.

311
00:23:01,470 --> 00:23:07,750
גוט, איין זאַך צו טאָן איז אַז איך גערופן מאַללאָק דאָ מיט גרייס ען.

312
00:23:07,750 --> 00:23:13,590
וואָס טוט אַז פֿאָרשלאָגן צו איר?

313
00:23:13,590 --> 00:23:17,450
דאס אַלגערידאַם ניצט לינעאַר פּלאַץ.

314
00:23:17,450 --> 00:23:21,030
קענען מיר טאָן בעסער?

315
00:23:21,030 --> 00:23:30,780
איז עס עפּעס וואָס איר באַמערקן אַז איז ומנייטיק צו צונויפרעכענען די לעצט ענטפֿערן?

316
00:23:30,780 --> 00:23:33,290
איך טרעפן אַ בעסער קשיא איז, וואָס אינפֿאָרמאַציע

317
00:23:33,290 --> 00:23:40,680
טאָן מיר נישט דאַרפֿן צו פירן אַלע די וועג דורך צו דער סוף?

318
00:23:40,680 --> 00:23:44,280
איצט, אויב מיר קוקן אין די צוויי שורות,

319
00:23:44,280 --> 00:23:47,720
מיר נאָר זאָרגן וועגן די פֿריִערדיקע סובפּראָבלעם,

320
00:23:47,720 --> 00:23:50,910
און מיר נאָר זאָרגן וועגן די מאַקסימום מיר ווע אלץ געזען אַזוי ווייַט.

321
00:23:50,910 --> 00:23:53,610
צו צונויפרעכענען אונדזער לעצט ענטפֿערן, מיר טאָן ניט דאַרפֿן די גאנצע מענגע.

322
00:23:53,610 --> 00:23:57,450
מיר נאָר דאַרפֿן די לעצטע נומער, לעצטע צוויי נומערן.

323
00:23:57,450 --> 00:24:02,630
לעצטע נומער פֿאַר די סובפּראָבלעם מענגע, און לעצטע נומער פֿאַר די מאַקסימום.

324
00:24:02,630 --> 00:24:07,380
אַזוי, אין פאַקט, מיר קענען קאָריק די לופּס צוזאַמען

325
00:24:07,380 --> 00:24:10,460
און גיין פון לינעאַר פּלאַץ צו קעסיידערדיק פּלאַץ.

326
00:24:10,460 --> 00:24:15,830
קראַנט סאַכאַקל אַזוי ווייַט, דאָ, ריפּלייסיז די ראָלע פון ​​סובפּראָבלעם, אונדזער סובפּראָבלעם מענגע.

327
00:24:15,830 --> 00:24:20,020
אַזוי קראַנט סאַכאַקל, אַזוי ווייַט, איז דער ענטפער צו די פֿריִערדיקע סובפּראָבלעם.

328
00:24:20,020 --> 00:24:23,450
און אַז סאַכאַקל, אַזוי ווייַט, נעמט דער פּלאַץ פון אונדזער מאַקס.

329
00:24:23,450 --> 00:24:28,100
מיר צונויפרעכענען די מאַקסימום ווי מיר גיין צוזאמען.

330
00:24:28,100 --> 00:24:30,890
און אַזוי מיר גיין פון לינעאַר פּלאַץ צו קעסיידערדיק פּלאַץ,

331
00:24:30,890 --> 00:24:36,650
און מיר אויך האָבן אַ לינעאַר לייזונג צו אונדזער סובאַררייַ פּראָבלעם.

332
00:24:36,650 --> 00:24:40,740
>> די מינים פון שאלות איר וועט באַקומען בעשאַס אַן אינטערוויו.

333
00:24:40,740 --> 00:24:44,450
וואָס איז די צייַט קאַמפּלעקסיטי; וואָס איז די פּלאַץ קאַמפּלעקסיטי?

334
00:24:44,450 --> 00:24:50,600
קענען איר טאָן בעסער? זענען דאָרט זאכן וואָס זענען ומנייטיק צו האַלטן אַרום?

335
00:24:50,600 --> 00:24:55,270
איך האט דאָס צו הויכפּונקט אַנאַליזעס אַז איר זאָל נעמען אויף דיין אייגן

336
00:24:55,270 --> 00:24:57,400
ווי איר ניטאָ ארבעטן דורך די פראבלעמען.

337
00:24:57,400 --> 00:25:01,710
שטענדיק זייַן אַסקינג זיך ", קען איך טאָן בעסער?"

338
00:25:01,710 --> 00:25:07,800
אין פאַקט, קענען מיר טאָן בעסער ווי דעם?

339
00:25:07,800 --> 00:25:10,730
סאָרט פון אַ קונץ קשיא. איר קענען נישט, ווייַל איר דאַרפֿן צו

340
00:25:10,730 --> 00:25:13,590
בייַ מינדסטער לייענען דעם אַרייַנשרייַב צו די פּראָבלעם.

341
00:25:13,590 --> 00:25:15,570
אַזוי דער פאַקט אַז איר דאַרפֿן צו בייַ מינדסטער לייענען דעם אַרייַנשרייַב צו די פּראָבלעם

342
00:25:15,570 --> 00:25:19,580
מיטל אַז איר קענען נישט טאָן בעסער ווי לינעאַר צייַט,

343
00:25:19,580 --> 00:25:22,870
און איר קענען נישט טאָן בעסער ווי קעסיידערדיק פּלאַץ.

344
00:25:22,870 --> 00:25:27,060
אַזוי דאָס איז, אין פאַקט, די בעסטער לייזונג צו דעם פּראָבלעם.

345
00:25:27,060 --> 00:25:33,040
שאלות? אָוקיי.

346
00:25:33,040 --> 00:25:35,190
>> לאַגער מאַרק פּראָבלעם:

347
00:25:35,190 --> 00:25:38,350
"געגעבן אַ מענגע פון ​​N ינטאַדזשערז, positive, נול, אָדער נעגאַטיוו,

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
צונויפרעכענען די נוץ, וואָס קען זייַן נעגאַטיוו אָדער positive אָדער נול.

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
און אַז לייזונג וועט זייַן אָ (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 קלאָץ ען?

373
00:27:45,550 --> 00:27:50,730
עס ס נישט אַ קונץ קשיא.

374
00:27:50,730 --> 00:27:54,790
>> צונויפגיסן סאָרט. צונויפגיסן סאָרט איז N קלאָץ 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
דעמאָלט איר ווילן צו אָאָמפּוטע דער בעסטער קויפן / פאַרקויפן פּאָר אויף די רעכט האַלב,

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
אויב מיר דיפיינד אַ פֿונקציע ה (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
זענען יעדער געגאנגען צו פּרייַז ה (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 קלאָץ 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
ה (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 איז נאָר ען.

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 קלאָץ ען.

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
די מאַקסימום סומע פון ​​פּלאַץ מיר אלץ נוצן איז אָ (קלאָץ N) פּלאַץ

467
00:35:49,240 --> 00:36:03,040
ווו ען איז די נומער פון טעג.

468
00:36:03,040 --> 00:36:07,230
>> איצט, שטענדיק פרעגן זיך ", קענען מיר טאָן בעסער?"

469
00:36:07,230 --> 00:36:12,390
און אין באַזונדער, קענען מיר רעדוצירן דעם צו אַ פּראָבלעם מיר ווע שוין סאַלווד?

470
00:36:12,390 --> 00:36:20,040
א אָנצוהערעניש: מיר נאָר דיסקאַסט צוויי אנדערע פראבלעמען פאר דעם, און עס ס ניט געגאנגען צו זייַן שאַרן.

471
00:36:20,040 --> 00:36:26,200
מיר קענען בייַטן דעם לאַגער מאַרק פּראָבלעם אין די מאַקסימאַל סובאַררייַ פּראָבלעם.

472
00:36:26,200 --> 00:36:40,100
ווי קענען מיר טאָן דעם?

473
00:36:40,100 --> 00:36:42,570
איינער פון איר? עמי?

474
00:36:42,570 --> 00:36:47,680
(עמי, אַנינטעלאַדזשאַבאַל)

475
00:36:47,680 --> 00:36:53,860
[יו] עקסאַקטלי.

476
00:36:53,860 --> 00:36:59,940
אַזוי די מאַקסימאַל סובאַררייַ פּראָבלעם,

477
00:36:59,940 --> 00:37:10,610
מיר רע קוקן פֿאַר אַ סאַכאַקל איבער אַ קעסיידערדיק סובאַררייַ.

478
00:37:10,610 --> 00:37:16,230
און עמי ס פאָרשלאָג פֿאַר די סטאַקס פּראָבלעם,

479
00:37:16,230 --> 00:37:30,720
באַטראַכטן די ענדערונגען, אָדער די דעלטאַז.

480
00:37:30,720 --> 00:37:37,440
און אַ בילד פון דעם איז - דאָס איז די פּרייַז פון אַ לאַגער,

481
00:37:37,440 --> 00:37:42,610
אָבער אויב מיר גענומען די חילוק צווישן יעדער קאָנסעקוטיווע טאָג -

482
00:37:42,610 --> 00:37:45,200
אַזוי מיר זען אַז די מאַקסימום פּרייַז, מאַקסימום נוץ מיר קען מאַכן

483
00:37:45,200 --> 00:37:50,070
איז אויב מיר קויפן דאָ און פאַרקויפן דאָ.

484
00:37:50,070 --> 00:37:54,240
אבער לאָזן ס קוק בייַ די קעסיידערדיק - לאָזן ס קוק בייַ די סובאַררייַ פּראָבלעם.

485
00:37:54,240 --> 00:38:02,510
אַזוי דאָ, מיר קענען מאַכן - געגאנגען פון דאָ צו דאָ,

486
00:38:02,510 --> 00:38:08,410
מיר האָבן אַ positive טוישן, און דעמאָלט געגאנגען פון דאָ צו דאָ מיר האָבן אַ נעגאַטיוו טוישן.

487
00:38:08,410 --> 00:38:14,220
אבער דעמאָלט, געגאנגען פון דאָ צו דאָ מיר האָבן אַ ריזיק positive טוישן.

488
00:38:14,220 --> 00:38:20,930
און די זענען די ענדערונגען וואָס מיר ווילן צו סאַכאַקל אַרויף צו באַקומען אונדזער לעצט נוץ.

489
00:38:20,930 --> 00:38:25,160
דעמאָלט מיר האָבן מער נעגאַטיוו ענדערונגען דאָ.

490
00:38:25,160 --> 00:38:29,990
דער שליסל צו רידוסינג אונדזער לאַגער פּראָבלעם אין אונדזער מאַקסימאַל סובאַררייַ פּראָבלעם

491
00:38:29,990 --> 00:38:36,630
איז צו באַטראַכטן די דעלטאַז צווישן טעג.

492
00:38:36,630 --> 00:38:40,630
אַזוי מיר שאַפֿן אַ נייַ מענגע גערופן דעלטאַז,

493
00:38:40,630 --> 00:38:43,000
ינישאַלייז דער ערשטער פּאָזיציע צו זייַן 0,

494
00:38:43,000 --> 00:38:46,380
און דעמאָלט פֿאַר יעדער דעלטאַ (איך), לאָזן אַז זייַן דער חילוק

495
00:38:46,380 --> 00:38:52,830
פון מיין אַרייַנשרייַב מענגע (איך), און מענגע (איך - 1).

496
00:38:52,830 --> 00:38:55,530
דעמאָלט מיר רופן אונדזער רוטין פּראָצעדור פֿאַר אַ מאַקסימאַל סובאַררייַ

497
00:38:55,530 --> 00:39:01,500
גייט פארביי אין אַ דעלטאַ ס מענגע.

498
00:39:01,500 --> 00:39:06,440
און ווייַל מאַקסימאַל סובאַררייַ איז לינעאַר צייַט,

499
00:39:06,440 --> 00:39:09,370
און דעם רעדוקציע, דעם פּראָצעס פון שאפן דעם דעלטאַ מענגע,

500
00:39:09,370 --> 00:39:11,780
איז אויך לינעאַר צייַט,

501
00:39:11,780 --> 00:39:19,060
דעריבער די לעצט לייזונג פֿאַר סטאַקס איז אָ (N) אַרבעט פּלוס אָ (N) אַרבעט, איז נאָך אָ (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]