1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] איר ווע מיסטאָמע געהערט מענטשן רעדן וועגן אַ פעסט אָדער עפעקטיוו אַלגערידאַם

2
00:00:10,950 --> 00:00:13,090
פֿאַר עקסאַקיוטינג דיין באַזונדער אַרבעט,

3
00:00:13,090 --> 00:00:16,110
אָבער וואָס פּונקט טוט עס מיינען פֿאַר אַ אַלגערידאַם צו זייַן פעסט אָדער עפעקטיוו?

4
00:00:16,110 --> 00:00:18,580
נו, עס ס ניט גערעדט וועגן אַ מעאַסורעמענט אין פאַקטיש צייַט,

5
00:00:18,580 --> 00:00:20,500
ווי סעקונדעס אָדער מינוט.

6
00:00:20,500 --> 00:00:22,220
דאס איז ווייַל קאָמפּיוטער ייַזנוואַרג

7
00:00:22,220 --> 00:00:24,260
און ווייכווארג בייַטן דראַסטיקלי.

8
00:00:24,260 --> 00:00:26,020
מייַן פּראָגראַם זאל לויפן סלאָוער ווי דייַן,

9
00:00:26,020 --> 00:00:28,000
ווייַל איך בין פליסנדיק עס אויף אַ עלטערע קאָמפּיוטער,

10
00:00:28,000 --> 00:00:30,110
אָדער ווייַל איך פּאַסירן צו זייַן פּלייינג אַן אָנליין ווידעא שפּיל

11
00:00:30,110 --> 00:00:32,670
אין דער זעלביקער צייַט, וואָס איז כאָגינג אַלע מיין זכּרון,

12
00:00:32,670 --> 00:00:35,400
אָדער איך זאל זייַן פליסנדיק מיין פּראָגראַם דורך פאַרשידענע ווייכווארג

13
00:00:35,400 --> 00:00:37,550
וואָס קאַמיוניקייץ מיט די מאַשין דיפערענטלי בייַ אַ נידעריק מדרגה.

14
00:00:37,550 --> 00:00:39,650
עס ס ווי קאַמפּערינג apples און אָראַנדזשאַז.

15
00:00:39,650 --> 00:00:41,940
נאָר ווייַל מיין סלאָוער קאָמפּיוטער נעמט מער

16
00:00:41,940 --> 00:00:43,410
ווי דייַן צו געבן צוריק אַן ענטפֿערן

17
00:00:43,410 --> 00:00:45,510
טוט נישט מיינען איר האָבן די מער עפעקטיוו אַלגערידאַם.

18
00:00:45,510 --> 00:00:48,830
>> אַזוי, זינט מיר קענען ניט גלייַך פאַרגלייַכן די רונטימעס פון מגילה

19
00:00:48,830 --> 00:00:50,140
אין סעקונדעס אָדער מינוט,

20
00:00:50,140 --> 00:00:52,310
ווי טאָן מיר פאַרגלייַכן 2 פאַרשידענע אַלגערידאַמז

21
00:00:52,310 --> 00:00:55,030
ראַגאַרדלאַס פון זייער ייַזנוואַרג אָדער ווייכווארג סוויווע?

22
00:00:55,030 --> 00:00:58,000
צו שאַפֿן אַ מער מונדיר וועג פון מעסטן אַלגאָריטהמיק עפעקטיווקייַט,

23
00:00:58,000 --> 00:01:00,360
קאָמפּיוטער סיינטיס און מאַטאַמאַטישאַנז האָבן דיווייזד

24
00:01:00,360 --> 00:01:03,830
קאַנסעפּס פֿאַר מעסטן די אַסימפּטאָטיק קאַמפּלעקסיטי פון אַ פּראָגראַם

25
00:01:03,830 --> 00:01:06,110
און אַ נאָוטיישאַן גערופן 'גרויס אָהנאָטאַטיאָן'

26
00:01:06,110 --> 00:01:08,320
פֿאַר דיסקרייבינג דעם.

27
00:01:08,320 --> 00:01:10,820
די פאָרמאַל דעפֿיניציע איז אַז אַ פֿונקציע F (X)

28
00:01:10,820 --> 00:01:13,390
לויפט אויף די סדר פון ג (X)

29
00:01:13,390 --> 00:01:15,140
אויב עס יגזיסץ עטלעכע (X) ווערט, X ₀ און

30
00:01:15,140 --> 00:01:17,630
עטלעכע קעסיידערדיק, C, פֿאַר וואָס

31
00:01:17,630 --> 00:01:19,340
F (X) איז ווייניקער ווי אָדער גלייַך צו

32
00:01:19,340 --> 00:01:21,230
אַז קעסיידערדיק מאל ג (X)

33
00:01:21,230 --> 00:01:23,190
פֿאַר אַלע X גרעסער ווי X ₀.

34
00:01:23,190 --> 00:01:25,290
>> אבער טאָן נישט זייַן דערשראָקן אַוועק דורך די פאָרמאַל דעפֿיניציע.

35
00:01:25,290 --> 00:01:28,020
וואָס טוט דאָס פאקטיש מיינען אין ווייניקער טעאָרעטיש תּנאָים?

36
00:01:28,020 --> 00:01:30,580
נו, עס ס בייסיקלי אַ וועג פון אַנאַלייזינג

37
00:01:30,580 --> 00:01:33,580
ווי שנעל אַ פּראָגראַם 'ס רונטימע וואקסט אַסימפּטאָטיקאַללי.

38
00:01:33,580 --> 00:01:37,170
וואָס איז, ווי די גרייס פון דיין ינפּוץ ינקריסיז צו ינפיניטי,

39
00:01:37,170 --> 00:01:41,390
זאָגן, איר ניטאָ סאָרטינג אַ מענגע פון ​​גרייס 1000 קאַמפּערד צו אַ מענגע פון ​​גרייס 10.

40
00:01:41,390 --> 00:01:44,950
ווי טוט די רונטימע פון ​​דיין פּראָגראַם וואַקסן?

41
00:01:44,950 --> 00:01:47,390
פֿאַר בייַשפּיל, ימאַדזשאַן קאַונטינג די נומער פון אותיות

42
00:01:47,390 --> 00:01:49,350
אין אַ שטריקל די סימפּלאַסט וועג

43
00:01:49,350 --> 00:01:51,620
 דורך גיין דורך די גאנצע שטריקל

44
00:01:51,620 --> 00:01:54,790
בריוו-דורך-בריוו און אַדינג 1 צו אַ קאָונטער פֿאַר יעדער כאַראַקטער.

45
00:01:55,700 --> 00:01:58,420
דאס אַלגערידאַם איז געזאגט צו לויפן אין לינעאַר צייַט

46
00:01:58,420 --> 00:02:00,460
מיט רעספּעקט צו די נומער פון אותיות,

47
00:02:00,460 --> 00:02:02,670
'N' אין די שטריקל.

48
00:02:02,670 --> 00:02:04,910
אין קורץ, עס לויפט אין אָ (N).

49
00:02:05,570 --> 00:02:07,290
פארוואס איז דאָס?

50
00:02:07,290 --> 00:02:09,539
נו, ניצן דעם צוגאַנג, די צייַט פארלאנגט

51
00:02:09,539 --> 00:02:11,300
צו דורך די גאנצע שטריקל

52
00:02:11,300 --> 00:02:13,920
איז פּראַפּאָרשאַנאַל צו די נומער פון אותיות.

53
00:02:13,920 --> 00:02:16,480
קאַונטינג די נומער פון אותיות אין אַ 20-כאַראַקטער שטריקל

54
00:02:16,480 --> 00:02:18,580
איז געגאנגען צו נעמען צוויי מאָל ווי לאַנג ווי עס נעמט

55
00:02:18,580 --> 00:02:20,330
צו ציילן די אותיות אין אַ 10-כאַראַקטער שטריקל,

56
00:02:20,330 --> 00:02:23,000
ווייַל איר האָבן צו קוקן אין אַלע די אותיות

57
00:02:23,000 --> 00:02:25,740
און יעדער כאַראַקטער נעמט די זעלבע סומע פון ​​צייַט צו קוקן בייַ.

58
00:02:25,740 --> 00:02:28,050
ווי איר פאַרגרעסערן די נומער פון אותיות,

59
00:02:28,050 --> 00:02:30,950
די רונטימע וועט פאַרגרעסערן ליניערלי מיט די אַרייַנשרייַב לענג.

60
00:02:30,950 --> 00:02:33,500
>> איצט, ימאַדזשאַן אויב איר באַשליסן אַז לינעאַר צייַט,

61
00:02:33,500 --> 00:02:36,390
אָ (N), נאָר איז געווען ניט שנעל גענוג פֿאַר איר?

62
00:02:36,390 --> 00:02:38,750
אפֿשר איר ניטאָ סטאָרינג ריזיק סטרינגס,

63
00:02:38,750 --> 00:02:40,450
און איר קענען נישט פאַרגינענ די עקסטרע מאָל עס וואָלט נעמען

64
00:02:40,450 --> 00:02:44,000
צו דורך אַלע פון ​​זייער אותיות קאַונטינג איינער-דורך-איינער.

65
00:02:44,000 --> 00:02:46,650
אַזוי, איר באַשליסן צו פּרובירן עפּעס אַנדערש.

66
00:02:46,650 --> 00:02:49,270
וואָס אויב איר וואָלט פּאַסירן צו שוין קראָם די נומער פון אותיות

67
00:02:49,270 --> 00:02:52,690
אין דעם שטריקל, זאָגן, אין אַ בייַטעוודיק גערופן 'לען,'

68
00:02:52,690 --> 00:02:54,210
פרי אויף אין די פּראָגראַם,

69
00:02:54,210 --> 00:02:57,800
איידער איר אַפֿילו סטאָרד די זייער ערשטער כאַראַקטער אין דיין שטריקל?

70
00:02:57,800 --> 00:02:59,980
דערנאך, אַלע איר 'ד האָבן צו טאָן איצט צו געפֿינען אויס די שטריקל לענג,

71
00:02:59,980 --> 00:03:02,570
איז טשעק וואָס די ווערט פון די בייַטעוודיק איז.

72
00:03:02,570 --> 00:03:05,530
איר וואָלט ניט האָבן צו קוקן בייַ די שטריקל זיך בייַ אַלע,

73
00:03:05,530 --> 00:03:08,160
און אַקסעסינג די ווערט פון אַ בייַטעוודיק ווי לען איז געהאלטן

74
00:03:08,160 --> 00:03:11,100
אַ אַסימפּטאָטיקאַללי קעסיידערדיק צייַט אָפּעראַציע,

75
00:03:11,100 --> 00:03:13,070
אָדער אָ (1).

76
00:03:13,070 --> 00:03:17,110
פארוואס איז דאָס? נו, געדענקען וואָס אַסימפּטאָטיק קאַמפּלעקסיטי מיטל.

77
00:03:17,110 --> 00:03:19,100
ווי טוט די רונטימע טוישן ווי די גרייס

78
00:03:19,100 --> 00:03:21,400
פון דיין ינפּוץ וואקסט?

79
00:03:21,400 --> 00:03:24,630
>> זאָגן איר זענען טריינג צו באַקומען די נומער פון אותיות אין אַ ביגער שטריקל.

80
00:03:24,630 --> 00:03:26,960
נו, עס וואָלט נישט ענין ווי גרויס איר מאַכן דעם שטריקל,

81
00:03:26,960 --> 00:03:28,690
אַפֿילו אַ מיליאָן אותיות לאַנג,

82
00:03:28,690 --> 00:03:31,150
אַלע איר 'ד האָבן צו טאָן צו געפֿינען די שטריקל ס לענג מיט דעם צוגאַנג,

83
00:03:31,150 --> 00:03:33,790
איז צו לייענען אויס די ווערט פון די בייַטעוודיק לען,

84
00:03:33,790 --> 00:03:35,440
וואָס איר שוין געמאכט.

85
00:03:35,440 --> 00:03:38,200
די אַרייַנשרייַב לענג, וואָס איז, די לענג פון די שטריקל איר ניטאָ טריינג צו געפֿינען,

86
00:03:38,200 --> 00:03:41,510
טוט ניט ווירקן אין אַלע ווי שנעל דיין פּראָגראַם לויפט.

87
00:03:41,510 --> 00:03:44,550
דעם טייל פון אייער פּראָגראַם וואָלט לויפן גלייַך פעסט אויף אַ איין-כאַראַקטער שטריקל

88
00:03:44,550 --> 00:03:46,170
און אַ טויזנט-כאַראַקטער שטריקל,

89
00:03:46,170 --> 00:03:49,140
און אַז ס וואָס דעם פּראָגראַם וואָלט זייַן ריפערד צו ווי פליסנדיק אין קעסיידערדיק צייַט

90
00:03:49,140 --> 00:03:51,520
מיט רעספּעקט צו די אַרייַנשרייַב גרייס.

91
00:03:51,520 --> 00:03:53,920
>> פון קורס, דאָרט ס אַ שטערונג.

92
00:03:53,920 --> 00:03:55,710
איר פאַרברענגען עקסטרע זכּרון פּלאַץ אויף דיין קאָמפּיוטער

93
00:03:55,710 --> 00:03:57,380
סטאָרינג די בייַטעוודיק

94
00:03:57,380 --> 00:03:59,270
און די עקסטרע צייַט עס נעמט איר

95
00:03:59,270 --> 00:04:01,490
צו טאָן די פאַקטיש סטאָרידזש פון די בייַטעוודיק,

96
00:04:01,490 --> 00:04:03,390
אָבער די פונט נאָך שטייט,

97
00:04:03,390 --> 00:04:05,060
געפונען אויס ווי לאַנג דיין שטריקל איז געווען

98
00:04:05,060 --> 00:04:07,600
טוט ניט אָפענגען אויף די לענג פון די שטריקל בייַ אַלע.

99
00:04:07,600 --> 00:04:10,720
אַזוי, עס לויפט אין אָ (1) אָדער קעסיידערדיק צייַט.

100
00:04:10,720 --> 00:04:13,070
דאס זיכער טוט ניט האָבן צו מיינען

101
00:04:13,070 --> 00:04:15,610
אַז דיין קאָד לויפט אין 1 שריט,

102
00:04:15,610 --> 00:04:17,470
אָבער קיין ענין ווי פילע טריט עס איז,

103
00:04:17,470 --> 00:04:20,019
אויב עס טוט נישט טוישן מיט די גרייס פון דעם ינפּוץ,

104
00:04:20,019 --> 00:04:23,420
עס ס נאָך אַסימפּטאָטיקאַללי קעסיידערדיק וואָס מיר פאָרשטעלן ווי אָ (1).

105
00:04:23,420 --> 00:04:25,120
>> ווי איר קענען מיסטאָמע טרעפן,

106
00:04:25,120 --> 00:04:27,940
עס זענען פילע פאַרשידענע גרויס אָ רונטימעס צו מאָס אַלגערידאַמז מיט.

107
00:04:27,940 --> 00:04:32,980
אָ (N) ² אַלגערידאַמז זענען אַסימפּטאָטיקאַללי סלאָוער ווי אָ (N) אַלגערידאַמז.

108
00:04:32,980 --> 00:04:35,910
וואָס איז, ווי די נומער פון עלעמענטן (N) וואקסט,

109
00:04:35,910 --> 00:04:39,280
יווענטשאַוואַלי אָ (N) ² אַלגערידאַמז וועט נעמען מער צייַט

110
00:04:39,280 --> 00:04:41,000
ווי אָ (N) אַלגערידאַמז צו לויפן.

111
00:04:41,000 --> 00:04:43,960
דאס טוט נישט מיינען אָ (N) אַלגערידאַמז שטענדיק לויפן פאַסטער

112
00:04:43,960 --> 00:04:46,410
ווי אָ (N) ² אַלגערידאַמז, אַפֿילו אין דער זעלביקער סוויווע,

113
00:04:46,410 --> 00:04:48,080
אויף דער זעלביקער ייַזנוואַרג.

114
00:04:48,080 --> 00:04:50,180
אפֿשר פֿאַר קליין אַרייַנשרייַב סיזעס,

115
00:04:50,180 --> 00:04:52,900
 דער אָ (N) ² אַלגערידאַם זאל פאקטיש אַרבעט פאַסטער,

116
00:04:52,900 --> 00:04:55,450
אָבער, יווענטשאַוואַלי, ווי די אַרייַנשרייַב גרייס ינקריסיז

117
00:04:55,450 --> 00:04:58,760
צו ינפיניטי, די אָ (N) ² אַלגערידאַם ס רונטימע

118
00:04:58,760 --> 00:05:02,000
וועט יווענטשאַוואַלי אַקליפּס די רונטימע פון ​​די אָ (N) אַלגערידאַם.

119
00:05:02,000 --> 00:05:04,230
פּונקט ווי קיין קוואַדראַטיק מאַטאַמאַטיקאַל פֿונקציע

120
00:05:04,230 --> 00:05:06,510
 וועט יווענטשאַוואַלי יבעריאָגן קיין לינעאַר פונקציאָנירן,

121
00:05:06,510 --> 00:05:09,200
קיין ענין ווי פיל פון אַ קאָפּ אָנהייב די לינעאַר פונקציאָנירן סטאַרץ אַוועק מיט.

122
00:05:10,010 --> 00:05:12,000
אויב איר ניטאָ ארבעטן מיט גרויס אַמאַונץ פון דאַטן,

123
00:05:12,000 --> 00:05:15,510
אַלגערידאַמז וואָס לויפן אין אָ (N) ² צייַט קענען טאַקע סוף אַרויף סלאָוינג אַראָפּ דיין פּראָגראַם,

124
00:05:15,510 --> 00:05:17,770
אָבער פֿאַר קליין אַרייַנשרייַב סיזעס,

125
00:05:17,770 --> 00:05:19,420
איר מיסטאָמע וועט נישט אַפֿילו באַמערקן.

126
00:05:19,420 --> 00:05:21,280
>> אן אנדער אַסימפּטאָטיק קאַמפּלעקסיטי איז,

127
00:05:21,280 --> 00:05:24,420
לאַגערידמיק צייַט, אָ (קלאָץ N).

128
00:05:24,420 --> 00:05:26,340
אַ בייַשפּיל פון אַ אַלגערידאַם וואָס לויפט דעם געשווינד

129
00:05:26,340 --> 00:05:29,060
איז דער קלאַסיש ביינערי זוכן אַלגערידאַם,

130
00:05:29,060 --> 00:05:31,850
פֿאַר געפונען אַן עלעמענט אין אַ שוין-אויסגעשטעלט רשימה פון עלעמענטן.

131
00:05:31,850 --> 00:05:33,400
>> אויב איר טאָן ניט וויסן וואָס ביינערי זוכן טוט,

132
00:05:33,400 --> 00:05:35,170
איך וועט דערקלערן עס פֿאַר איר טאַקע געשווינד.

133
00:05:35,170 --> 00:05:37,020
זאל ס זאָגן איר ניטאָ קוקן פֿאַר די נומער 3

134
00:05:37,020 --> 00:05:40,200
אין דעם מענגע פון ​​ינטאַדזשערז.

135
00:05:40,200 --> 00:05:42,140
עס קוקט אין די מיטל עלעמענט פון דער מענגע

136
00:05:42,140 --> 00:05:46,830
און פרעגט, "איז דער עלעמענט איך וועלן גרעסער ווי, גלייַך צו, אָדער ווייניקער ווי דעם?"

137
00:05:46,830 --> 00:05:49,150
אויב עס ס גלייַך, דעמאָלט גרויס. איר געפונען דעם עלעמענט, און איר ניטאָ געטאן.

138
00:05:49,150 --> 00:05:51,300
אויב עס ס גרעסער, דעמאָלט איר וויסן דעם עלעמענט

139
00:05:51,300 --> 00:05:53,440
האט צו זייַן אין די רעכט זייַט פון די מענגע,

140
00:05:53,440 --> 00:05:55,200
און איר קענען נאָר קוק אין אַז אין די צוקונפֿט,

141
00:05:55,200 --> 00:05:57,690
און אויב עס ס קלענערער, ​​דעמאָלט איר וויסן עס האט צו זייַן אין די לינקס זייַט.

142
00:05:57,690 --> 00:06:00,980
דעם פּראָצעס איז דעמאָלט ריפּיטיד מיט דער קלענערער-גרייס מענגע

143
00:06:00,980 --> 00:06:02,870
ביז די ריכטיק עלעמענט איז געפונען.

144
00:06:08,080 --> 00:06:11,670
>> דאס שטאַרק אַלגערידאַם קאַץ די מענגע גרייס אין העלפט מיט יעדער אָפּעראַציע.

145
00:06:11,670 --> 00:06:14,080
אַזוי, צו געפֿינען אַן עלעמענט אין אַ אויסגעשטעלט מענגע פון ​​נומער 8,

146
00:06:14,080 --> 00:06:16,170
בייַ רובֿ (קלאָץ ₂ 8),

147
00:06:16,170 --> 00:06:18,450
אָדער 3 פון די אַפּעריישאַנז,

148
00:06:18,450 --> 00:06:22,260
קאָנטראָלירונג די מיטל עלעמענט, דעמאָלט קאַטינג די מענגע אין האַלב וועט זייַן פארלאנגט,

149
00:06:22,260 --> 00:06:25,670
וועראַז אַ מענגע פון ​​גרייס 16 נעמט (קלאָץ ₂ 16),

150
00:06:25,670 --> 00:06:27,480
אָדער 4 אַפּעריישאַנז.

151
00:06:27,480 --> 00:06:30,570
אַז ס בלויז 1 מער אָפּעראַציע פֿאַר אַ דאַבאַלד-גרייס מענגע.

152
00:06:30,570 --> 00:06:32,220
דאַבלינג די גרייס פון דעם מענגע

153
00:06:32,220 --> 00:06:35,160
ינקריסיז די רונטימע דורך בלויז 1 פּייַדע פון ​​דעם קאָד.

154
00:06:35,160 --> 00:06:37,770
ווידער, קאָנטראָלירונג די מיטל עלעמענט פון דער רשימה, דעמאָלט ספּליטינג.

155
00:06:37,770 --> 00:06:40,440
אַזוי, עס ס 'האט צו אַרבעטן אין לאַגערידמיק צייַט,

156
00:06:40,440 --> 00:06:42,440
אָ (קלאָץ N).

157
00:06:42,440 --> 00:06:44,270
אבער וואַרטן, איר זאָגן,

158
00:06:44,270 --> 00:06:47,510
טוט ניט דעם אָפענגען אויף ווו אין די רשימה די עלעמענט איר ניטאָ קוקן פֿאַר איז?

159
00:06:47,510 --> 00:06:50,090
וואָס אויב דער ערשטער עלעמענט איר קוק בייַ כאַפּאַנז צו זייַן די רעכט איינער?

160
00:06:50,090 --> 00:06:52,040
דעמאָלט, עס נאָר נעמט 1 אָפּעראַציע,

161
00:06:52,040 --> 00:06:54,310
קיין ענין ווי גרויס די רשימה איז.

162
00:06:54,310 --> 00:06:56,310
>> נו, אַז ס וואָס קאָמפּיוטער סיינטיס האָבן מער תּנאָים

163
00:06:56,310 --> 00:06:58,770
פֿאַר אַסימפּטאָטיק קאַמפּלעקסיטי וואָס פאַרטראַכטנ דער בעסטער-פאַל

164
00:06:58,770 --> 00:07:01,050
און ערגסט-פאַל פּערפאָרמאַנסיז פון אַ אַלגערידאַם.

165
00:07:01,050 --> 00:07:03,320
מער רעכט, דער אויבערשטער און נידעריקער גווול

166
00:07:03,320 --> 00:07:05,090
אויף די רונטימע.

167
00:07:05,090 --> 00:07:07,660
אין דער בעסטער פאַל פֿאַר ביינערי זוכן, אונדזער עלעמענט איז

168
00:07:07,660 --> 00:07:09,330
רעכט דאָרט אין דער מיטן,

169
00:07:09,330 --> 00:07:11,770
און איר באַקומען עס אין קעסיידערדיק צייַט,

170
00:07:11,770 --> 00:07:14,240
קיין ענין ווי גרויס די מנוחה פון די מענגע איז.

171
00:07:15,360 --> 00:07:17,650
דער סימבאָל געניצט פֿאַר דעם איז Ω.

172
00:07:17,650 --> 00:07:19,930
אַזוי, דעם אַלגערידאַם איז געזאגט צו לויפן אין Ω (1).

173
00:07:19,930 --> 00:07:21,990
אין דער בעסטער פאַל, עס געפינט די עלעמענט געשווינד,

174
00:07:21,990 --> 00:07:24,200
קיין ענין ווי גרויס די מענגע איז,

175
00:07:24,200 --> 00:07:26,050
אָבער אין די ערגסט פאַל,

176
00:07:26,050 --> 00:07:28,690
עס האט צו דורכפירן (קלאָץ N) שפּאַלטן טשעקס

177
00:07:28,690 --> 00:07:31,030
פון די מענגע צו געפֿינען די רעכט עלעמענט.

178
00:07:31,030 --> 00:07:34,270
ערגסט-פאַל אויבערשטער גווול זענען ריפערד צו מיט די גרויס "אָ" אַז איר שוין וויסן.

179
00:07:34,270 --> 00:07:38,080
אַזוי, עס ס אָ (קלאָץ N), אָבער Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> א לינעאַר זוכן, דורך קאַנטראַסט,

181
00:07:40,680 --> 00:07:43,220
אין וואָס איר גיין דורך יעדער עלעמענט פון דער מענגע

182
00:07:43,220 --> 00:07:45,170
צו געפֿינען די איין איר ווילן,

183
00:07:45,170 --> 00:07:47,420
איז בייַ בעסטער Ω (1).

184
00:07:47,420 --> 00:07:49,430
ווידער, דער ערשטער עלעמענט איר ווילן.

185
00:07:49,430 --> 00:07:51,930
אַזוי, עס טוט נישט ענין ווי גרויס די מענגע איז.

186
00:07:51,930 --> 00:07:54,840
אין די ערגסט פאַל, עס ס די לעצטע עלעמענט אין דער מענגע.

187
00:07:54,840 --> 00:07:58,560
אַזוי, איר האָבן צו גיין דורך אַלע N יסודות אין די מענגע צו געפֿינען עס,

188
00:07:58,560 --> 00:08:02,170
ווי אויב איר זענען קוקן פֿאַר אַ 3.

189
00:08:04,320 --> 00:08:06,030
אַזוי, עס לויפט אין אָ (N) צייַט

190
00:08:06,030 --> 00:08:09,330
ווייַל עס ס פּראַפּאָרשאַנאַל צו די נומער פון עלעמענטן אין דער מענגע.

191
00:08:10,800 --> 00:08:12,830
>> איינער מער סימבאָל געניצט איז Θ.

192
00:08:12,830 --> 00:08:15,820
דאס קען זייַן געניצט צו באַשרייַבן אַלגערידאַמז ווו דער בעסטער און ערגסט פאלן

193
00:08:15,820 --> 00:08:17,440
זענען די זעלבע.

194
00:08:17,440 --> 00:08:20,390
דאס איז דער פאַל אין די שטריקל-לענג אַלגערידאַמז מיר גערעדט וועגן פריער.

195
00:08:20,390 --> 00:08:22,780
וואָס איז, אויב מיר קראָם עס אין אַ בייַטעוודיק איידער

196
00:08:22,780 --> 00:08:25,160
מיר קראָם די שטריקל און צוטריט עס שפּעטער אין קעסיידערדיק צייַט.

197
00:08:25,160 --> 00:08:27,920
ניט קיין ענין וואָס נומער

198
00:08:27,920 --> 00:08:30,130
מיר רע סטאָרינג אין אַז בייַטעוודיק, מיר וועט האָבן צו קוקן בייַ אים.

199
00:08:33,110 --> 00:08:35,110
דער בעסטער פאַל איז, מיר קוקן אין עס

200
00:08:35,110 --> 00:08:37,120
און געפֿינען די לענג פון די שטריקל.

201
00:08:37,120 --> 00:08:39,799
אַזוי Ω (1) אָדער בעסטער-פאַל קעסיידערדיק צייַט.

202
00:08:39,799 --> 00:08:41,059
די ערגסט פאַל איז,

203
00:08:41,059 --> 00:08:43,400
מיר קוקן אין עס און געפֿינען די לענג פון די שטריקל.

204
00:08:43,400 --> 00:08:47,300
אַזוי, אָ (1) אָדער קעסיידערדיק צייַט אין ערגסט פאַל.

205
00:08:47,300 --> 00:08:49,180
אַזוי, זינט דער בעסטער פאַל און ערגסט פאלן זענען די זעלבע,

206
00:08:49,180 --> 00:08:52,520
דעם קענען זייַן האט געזאגט צו לויפן אין Θ (1) מאָל.

207
00:08:54,550 --> 00:08:57,010
>> אין קיצער, מיר האָבן גוט וועגן צו סיבה וועגן קאָודז עפעקטיווקייַט

208
00:08:57,010 --> 00:09:00,110
אָן געוואוסט עפּעס וועגן די פאַקטיש-וועלט צייַט זיי נעמען צו לויפן,

209
00:09:00,110 --> 00:09:02,270
וואָס איז אַפעקטאַד דורך גורל פון אַרויס סיבות,

210
00:09:02,270 --> 00:09:04,190
אַרייַנגערעכנט דיפערינג ייַזנוואַרג, סאָפטווער,

211
00:09:04,190 --> 00:09:06,040
אָדער די ספּיסיפיקס פון דיין קאָד.

212
00:09:06,040 --> 00:09:08,380
אויך, עס אַלאַוז אונדז צו סיבה געזונט וועגן וואָס וועט פּאַסירן

213
00:09:08,380 --> 00:09:10,180
ווען די גרייס פון דעם ינפּוץ ינקריסיז.

214
00:09:10,180 --> 00:09:12,490
>> אויב איר ניטאָ פליסנדיק אין אָ (N) ² אַלגערידאַם,

215
00:09:12,490 --> 00:09:15,240
אָדער ערגער, אַ אָ (2 ⁿ) אַלגערידאַם,

216
00:09:15,240 --> 00:09:17,170
איינער פון די פאַסטאַסט גראָוינג טייפּס,

217
00:09:17,170 --> 00:09:19,140
איר וועט טאַקע אָנהייבן צו באַמערקן די סלאָודאַון

218
00:09:19,140 --> 00:09:21,220
ווען איר אָנהייבן ארבעטן מיט גרעסערע אַמאַונץ פון דאַטן.

219
00:09:21,220 --> 00:09:23,590
>> אַז ס אַסימפּטאָטיק קאַמפּלעקסיטי. דאַנק.