1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> Добро, па, компјутерската комплексност.

3
00:00:07,910 --> 00:00:10,430
Само малку на предупредување
Пред да се нурне во премногу far--

4
00:00:10,430 --> 00:00:13,070
ова веројатно ќе биде меѓу
најмногу математика-тешки работи

5
00:00:13,070 --> 00:00:14,200
ние зборуваме во CS50.

6
00:00:14,200 --> 00:00:16,950
Се надевам дека тоа нема да биде премногу големо
и ќе се обидеме и да ви помогнеме

7
00:00:16,950 --> 00:00:19,200
во текот на процесот, но
само малку на фер предупредување.

8
00:00:19,200 --> 00:00:21,282
Таму е малку
на математика вклучени тука.

9
00:00:21,282 --> 00:00:23,990
Добро, па со цел да се направи
употреба на нашите пресметковни ресурси

10
00:00:23,990 --> 00:00:28,170
во реалниот world-- тоа е навистина
важно да се разбере алгоритми

11
00:00:28,170 --> 00:00:30,750
и како тој ги обработува.

12
00:00:30,750 --> 00:00:32,810
Ако имаме навистина
ефикасен алгоритам, ние

13
00:00:32,810 --> 00:00:36,292
може да се намали износот на ресурси
имаме на располагање да се справи со неа.

14
00:00:36,292 --> 00:00:38,750
Ако имаме алгоритам што
се случува да се земе многу на работа

15
00:00:38,750 --> 00:00:41,210
да обработиме навистина
голем сет на податоци, тоа е

16
00:00:41,210 --> 00:00:44,030
случува да бараат повеќе
и повеќе ресурси, кои

17
00:00:44,030 --> 00:00:47,980
е пари, RAM меморија, сите тој вид на работи.

18
00:00:47,980 --> 00:00:52,090
>> Значи, да се биде во можност да се анализира една
алгоритам користење на оваа алатка во собата,

19
00:00:52,090 --> 00:00:56,110
во основа, го прашува question--
како го прави ова алгоритам скала

20
00:00:56,110 --> 00:00:59,020
како што се фрли повеќе и повеќе податоци во неа?

21
00:00:59,020 --> 00:01:02,220
Во CS50, износот на податоци ние сме
работат со е прилично мал.

22
00:01:02,220 --> 00:01:05,140
Општо земено, нашите програми се случува
да се кандидира во една секунда или less--

23
00:01:05,140 --> 00:01:07,830
веројатно многу помалку
особено на почетокот.

24
00:01:07,830 --> 00:01:12,250
>> Но, мислам за една компанија која се занимава
со стотици милиони клиенти.

25
00:01:12,250 --> 00:01:14,970
И тие треба да се процесира
дека податоците за клиентите.

26
00:01:14,970 --> 00:01:18,260
Како и бројот на клиенти тие
имаат добива поголеми и поголеми,

27
00:01:18,260 --> 00:01:21,230
тоа се случува да се бара
се повеќе и повеќе ресурси.

28
00:01:21,230 --> 00:01:22,926
Колку повеќе ресурси?

29
00:01:22,926 --> 00:01:25,050
Па, тоа зависи од тоа колку
ние анализираме алгоритам,

30
00:01:25,050 --> 00:01:28,097
со користење на алатки во овој алатникот.

31
00:01:28,097 --> 00:01:31,180
Кога зборуваме за комплексноста на
една algorithm-- кои понекогаш ќе

32
00:01:31,180 --> 00:01:34,040
чуете дека се нарекува време
комплексност или простор комплексност

33
00:01:34,040 --> 00:01:36,190
но ние сме само ќе
за да го повикате complexity--

34
00:01:36,190 --> 00:01:38,770
ние сме генерално зборувам за
на најлошото сценарио.

35
00:01:38,770 --> 00:01:42,640
Со оглед на апсолутна најлош куп
податоци што би можеле да се фрла во неа,

36
00:01:42,640 --> 00:01:46,440
како е ова се случува да алгоритам
обработува или се занимаваат со тие податоци?

37
00:01:46,440 --> 00:01:51,450
Ние обично го нарекуваме најлош случај
траење на алгоритам големи-О.

38
00:01:51,450 --> 00:01:56,770
Па еден алгоритам може да се рече да
работи во O на n или O од n квадрат.

39
00:01:56,770 --> 00:01:59,110
И повеќе за тоа што
тие значат во една секунда.

40
00:01:59,110 --> 00:02:01,620
>> Понекогаш, сепак, тоа го правиме за нега
сценарио за најдобро сценарио.

41
00:02:01,620 --> 00:02:05,400
Ако податоците се се што сакавме
тоа да биде и тоа беше апсолутно совршен

42
00:02:05,400 --> 00:02:09,630
и ни беше испраќање на оваа совршена
поставени на податоци преку нашиот алгоритам.

43
00:02:09,630 --> 00:02:11,470
Како ќе се справи со неа во таква ситуација?

44
00:02:11,470 --> 00:02:15,050
Ние понекогаш се однесуваат на тоа како
големи Омега, па за разлика од големите-О

45
00:02:15,050 --> 00:02:16,530
имаме големи Омега.

46
00:02:16,530 --> 00:02:18,880
Биг-Омега сценарио за најдобро сценарио.

47
00:02:18,880 --> 00:02:21,319
Биг-O за најлош случај.

48
00:02:21,319 --> 00:02:23,860
Општо земено, кога зборуваме за
сложеноста на алгоритмот,

49
00:02:23,860 --> 00:02:26,370
ние зборуваме за
најлошото сценарио.

50
00:02:26,370 --> 00:02:28,100
Па задржи дека во умот.

51
00:02:28,100 --> 00:02:31,510
>> И во оваа класа, ние обично се случува
да го напушти ригорозни анализа настрана.

52
00:02:31,510 --> 00:02:35,350
Постојат науки и полиња
посветен на овој вид на работи.

53
00:02:35,350 --> 00:02:37,610
Кога зборуваме за размислување
преку алгоритми,

54
00:02:37,610 --> 00:02:41,822
што сега ќе го направиме парче по парче за многу
алгоритми зборуваме за во класата.

55
00:02:41,822 --> 00:02:44,780
Ние сме навистина само зборуваме за
расудување преку неа и со здрав разум,

56
00:02:44,780 --> 00:02:47,070
не со формули, или докази,
или нешто слично.

57
00:02:47,070 --> 00:02:51,600
Затоа, не грижете се, ние не ќе биде
се претвора во голема математика.

58
00:02:51,600 --> 00:02:55,920
>> Па реков ние се грижиме за комплексноста
затоа што тоа го поставува прашањето, колку

59
00:02:55,920 --> 00:03:00,160
се нашите алгоритми се справи со поголеми и
поголеми дата сетови кои се фрлени во нив.

60
00:03:00,160 --> 00:03:01,960
Па, она што е збир на податоци?

61
00:03:01,960 --> 00:03:03,910
Што му мислам кога го рече тоа?

62
00:03:03,910 --> 00:03:07,600
Тоа значи дека она што го прави повеќето
смисла во контекст, да бидам искрен.

63
00:03:07,600 --> 00:03:11,160
Ако имаме алгоритам,
Процеси Strings-- ние сме веројатно

64
00:03:11,160 --> 00:03:13,440
Станува збор за големината на стрингот.

65
00:03:13,440 --> 00:03:15,190
Тоа е податоци set--
големината, бројот

66
00:03:15,190 --> 00:03:17,050
на знаци кои го сочинуваат низа.

67
00:03:17,050 --> 00:03:20,090
Ако зборуваме за една
алгоритам кој ги обработува датотеки,

68
00:03:20,090 --> 00:03:23,930
ние би можеле да се зборува за тоа како
многу килобајти состојат таа датотека.

69
00:03:23,930 --> 00:03:25,710
И тоа е група на податоци.

70
00:03:25,710 --> 00:03:28,870
Ако зборуваме за алгоритам
кој се справува со низи поопшто,

71
00:03:28,870 --> 00:03:31,510
како што се алгоритми за сортирање
или пребарување алгоритми,

72
00:03:31,510 --> 00:03:36,690
ние сме најверојатно станува збор за бројот
на елементите кои го сочинуваат низа.

73
00:03:36,690 --> 00:03:39,272
>> Сега, може да се мери со
algorithm-- особено,

74
00:03:39,272 --> 00:03:40,980
кога велам ние можеме
мерење алгоритам, јас

75
00:03:40,980 --> 00:03:43,840
значи дека ние може да се измери колку
многу ресурси потребни се.

76
00:03:43,840 --> 00:03:48,990
Дали тие ресурси се, колку
бајти на RAM-- или мегабајти RAM меморија

77
00:03:48,990 --> 00:03:49,790
го користи.

78
00:03:49,790 --> 00:03:52,320
Или колку време е потребно за да се кандидира.

79
00:03:52,320 --> 00:03:56,200
И ние може да се јавите на оваа
мерење, произволно, ѓ на n.

80
00:03:56,200 --> 00:03:59,420
Каде што n е бројот на
елементи во група на податоци.

81
00:03:59,420 --> 00:04:02,640
И ѓ на n е колку somethings.

82
00:04:02,640 --> 00:04:07,530
Колку единици на ресурси не
го бара тоа да се процесира податоците.

83
00:04:07,530 --> 00:04:10,030
>> Сега, ние всушност не ми е гајле
за тоа што ѓ на n е точно.

84
00:04:10,030 --> 00:04:13,700
Всушност, ние многу ретко will--
сигурно никогаш нема во овој class-- јас

85
00:04:13,700 --> 00:04:18,709
нурне во било навистина длабоко
анализа на она што ѓ на n е.

86
00:04:18,709 --> 00:04:23,510
Ние сме само ќе да се зборува за она што на F
n е околу или она што се стреми да се.

87
00:04:23,510 --> 00:04:27,600
А трендот на алгоритам е
диктиран од својата највисока цел мандат.

88
00:04:27,600 --> 00:04:29,440
И ние може да се види она што можам
велам тоа со преземање

89
00:04:29,440 --> 00:04:31,910
Еден поглед на поконкретен пример.

90
00:04:31,910 --> 00:04:34,620
>> Па да речеме дека имаме
три различни алгоритми.

91
00:04:34,620 --> 00:04:39,350
Од кои првиот го n
коцки, некои единици на ресурси

92
00:04:39,350 --> 00:04:42,880
за обработка на податоци во собата на големина n.

93
00:04:42,880 --> 00:04:47,000
Имаме втора алгоритам кој што се
n коцки плус n квадрат ресурси

94
00:04:47,000 --> 00:04:49,350
за обработка на податоци во собата на големина n.

95
00:04:49,350 --> 00:04:52,030
И да имаме и трета
алгоритам што работи in-- дека

96
00:04:52,030 --> 00:04:58,300
зазема n коцки минус 8n квадрат
плус 20 n единици на ресурси

97
00:04:58,300 --> 00:05:02,370
за обработка на алгоритам
со збир на податоци за големина n.

98
00:05:02,370 --> 00:05:05,594
>> Сега повторно, ние навистина не се случува
да влезат во оваа ниво на детали.

99
00:05:05,594 --> 00:05:08,260
Јас сум навистина само треба овие горе
овде како илустрација на една точка

100
00:05:08,260 --> 00:05:10,176
дека јас ќе одам да се биде
прават во секунда, што

101
00:05:10,176 --> 00:05:12,980
е дека ние само навистина се грижат
за тенденцијата на нештата

102
00:05:12,980 --> 00:05:14,870
како множества податоци се поголема.

103
00:05:14,870 --> 00:05:18,220
Значи, ако податоците во собата е мала, нема
всушност прилично голема разлика

104
00:05:18,220 --> 00:05:19,870
во овие алгоритми.

105
00:05:19,870 --> 00:05:23,000
Третиот алгоритам постои
зема 13 пати повеќе,

106
00:05:23,000 --> 00:05:27,980
13 пати повеќе од износот на средства
за да работи во однос на првата.

107
00:05:27,980 --> 00:05:31,659
>> Ако нашите податоци е со големина 10, која
е поголем, но не значи огромен,

108
00:05:31,659 --> 00:05:33,950
може да се види дека има
всушност малку разлика.

109
00:05:33,950 --> 00:05:36,620
Третиот алгоритам
станува поефикасна.

110
00:05:36,620 --> 00:05:40,120
Тоа е за да всушност 40% -
или 60% поефикасно.

111
00:05:40,120 --> 00:05:41,580
Таа ги зема 40% од износот на време.

112
00:05:41,580 --> 00:05:45,250
Тоа може run-- тоа може да потрае
400 единици на ресурси

113
00:05:45,250 --> 00:05:47,570
за обработка на податоци во собата на големина 10.

114
00:05:47,570 --> 00:05:49,410
Додека првата
алгоритам, од друга страна,

115
00:05:49,410 --> 00:05:54,520
зема 1.000 единици на ресурси
за обработка на податоци во собата на големина 10.

116
00:05:54,520 --> 00:05:57,240
Но, погледнете што се случува како
нашите бројки се уште поголеми.

117
00:05:57,240 --> 00:05:59,500
>> Сега, разликата
помеѓу овие алгоритми

118
00:05:59,500 --> 00:06:01,420
почнуваат да стануваат малку помалку очигледни.

119
00:06:01,420 --> 00:06:04,560
Како и фактот дека постојат
понизок ред terms-- или подобро,

120
00:06:04,560 --> 00:06:09,390
однос со пониски exponents--
почнуваат да стануваат ирелевантни.

121
00:06:09,390 --> 00:06:12,290
Ако еден сет на податоци е на големината
1000 и првиот алгоритам

122
00:06:12,290 --> 00:06:14,170
работи во една милијарда чекори.

123
00:06:14,170 --> 00:06:17,880
А вториот алгоритам работи во
една милијарда и милиони чекори.

124
00:06:17,880 --> 00:06:20,870
А третиот алгоритам тече
во само срамежливи од една милијарда чекори.

125
00:06:20,870 --> 00:06:22,620
Тоа е доста милијарда чекори.

126
00:06:22,620 --> 00:06:25,640
Тие термини од понизок ред да почне
да стане навистина ирелевантни.

127
00:06:25,640 --> 00:06:27,390
И само навистина да
чекан дома point--

128
00:06:27,390 --> 00:06:31,240
ако внесување на податоци е на големината на
million-- сите три од овие доста

129
00:06:31,240 --> 00:06:34,960
земе една quintillion-- ако
мојата математика е correct-- чекори

130
00:06:34,960 --> 00:06:37,260
за обработка на внесување на податоци
на големината на еден милион.

131
00:06:37,260 --> 00:06:38,250
Тоа е многу чекори.

132
00:06:38,250 --> 00:06:42,092
И фактот дека еден од нив може да
земе неколку 100.000 или неколку 100

133
00:06:42,092 --> 00:06:44,650
милиони уште помалку кога
ние зборуваме за голем број

134
00:06:44,650 --> 00:06:46,990
big-- дека тоа е вид на ирелевантни.

135
00:06:46,990 --> 00:06:50,006
Сите тие имаат тенденција да се земе
приближно n коцки,

136
00:06:50,006 --> 00:06:52,380
и така ние, всушност, ќе се однесуваат
на сите овие алгоритми

137
00:06:52,380 --> 00:06:59,520
како да бидат од редот на n
коцки или големи-О од n коцки.

138
00:06:59,520 --> 00:07:03,220
>> Еве листа на некои од повеќе
заеднички компјутерската комплексност класи

139
00:07:03,220 --> 00:07:05,820
дека ќе се сретне во
алгоритми, генерално.

140
00:07:05,820 --> 00:07:07,970
А исто така и конкретно во CS50.

141
00:07:07,970 --> 00:07:11,410
Овие се нарача од
генерално најбрз на врвот,

142
00:07:11,410 --> 00:07:13,940
да се генерално најспоро на дното.

143
00:07:13,940 --> 00:07:16,920
Па постојано време алгоритми имаат тенденција
да биде најбрз, без оглед

144
00:07:16,920 --> 00:07:19,110
на големината на
внес на податоци да помине во.

145
00:07:19,110 --> 00:07:23,760
Тие секогаш се земе една операција или
една единица на ресурси за да се справи со.

146
00:07:23,760 --> 00:07:25,730
Тоа би можело да биде 2, тоа би можело да
биде 3, тоа би можело да биде 4.

147
00:07:25,730 --> 00:07:26,910
Но, тоа е постојан број.

148
00:07:26,910 --> 00:07:28,400
Тоа не се разликува.

149
00:07:28,400 --> 00:07:31,390
>> Логаритамски алгоритми време
се малку подобро.

150
00:07:31,390 --> 00:07:33,950
И навистина добар пример за
логаритамска алгоритам време

151
00:07:33,950 --> 00:07:37,420
сигурно сте виделе до сега е
распарчување на именик

152
00:07:37,420 --> 00:07:39,480
да се најде Мајк Смит во книгата на телефонот.

153
00:07:39,480 --> 00:07:40,980
Ние се намали проблемот на половина.

154
00:07:40,980 --> 00:07:43,580
И така како n добива поголеми
и поголеми и larger--

155
00:07:43,580 --> 00:07:47,290
Всушност, секој пат кога ќе се удвои
n, тоа трае само уште еден чекор.

156
00:07:47,290 --> 00:07:49,770
Така што е многу подобро
отколку, да речеме, линеарното време.

157
00:07:49,770 --> 00:07:53,030
Што е, ако се зголеми двојно n, тоа
го удвои бројот на чекори.

158
00:07:53,030 --> 00:07:55,980
Ако тројно n, што е потребно
тројно зголемување на бројот на чекори.

159
00:07:55,980 --> 00:07:58,580
Еден чекор по единица.

160
00:07:58,580 --> 00:08:01,790
>> Тогаш работите се малку more--
малку помалку голем од таму.

161
00:08:01,790 --> 00:08:06,622
Имаш линеарни ритмичка време, понекогаш
наречен најавите линеарно време или само n log n.

162
00:08:06,622 --> 00:08:08,330
И ние ќе пример
на алгоритам што

163
00:08:08,330 --> 00:08:13,370
работи во n log n, што е уште подобро
од квадратните time-- n квадрат.

164
00:08:13,370 --> 00:08:17,320
Или полином време, н две
било кој број поголем од два.

165
00:08:17,320 --> 00:08:20,810
Или експоненцијална време, што
е дури worse-- C до n.

166
00:08:20,810 --> 00:08:24,670
Па некои константен број се зголеми на
моќта на големината на инпутот.

167
00:08:24,670 --> 00:08:28,990
Па ако има 1,000-- ако
влезни податоци е со големина од 1.000,

168
00:08:28,990 --> 00:08:31,310
дека ќе бидат потребни C до 1000-та моќ.

169
00:08:31,310 --> 00:08:33,559
Тоа е многу полошо од полином време.

170
00:08:33,559 --> 00:08:35,030
>> Факториел времето е уште полоша.

171
00:08:35,030 --> 00:08:37,760
И всушност, навистина направи
постојат бесконечен алгоритми време,

172
00:08:37,760 --> 00:08:43,740
како на пример, т.н. глупави sort-- чија
работа е да се случајно се влага низа

173
00:08:43,740 --> 00:08:45,490
а потоа се провери да се види
дали тоа се подредени.

174
00:08:45,490 --> 00:08:47,589
А ако тоа не е, по случаен избор
shuffle на низа повторно

175
00:08:47,589 --> 00:08:49,130
и да се провери да се види дали тоа се подредени.

176
00:08:49,130 --> 00:08:51,671
И како што веројатно може да се imagine--
можете да се замисли ситуација

177
00:08:51,671 --> 00:08:55,200
каде што во најлош случај, со кој
всушност никогаш не се започне со низа.

178
00:08:55,200 --> 00:08:57,150
Тој алгоритам ќе работи засекогаш.

179
00:08:57,150 --> 00:08:59,349
И така што ќе биде
бесконечна алгоритам време.

180
00:08:59,349 --> 00:09:01,890
Се надевам дека нема да се пишува
било факториел или бесконечно време

181
00:09:01,890 --> 00:09:04,510
алгоритми во CS50.

182
00:09:04,510 --> 00:09:09,150
>> Значи, ајде да потрае малку повеќе
бетон погледнеме некои поедноставни

183
00:09:09,150 --> 00:09:11,154
пресметковни класи комплексност.

184
00:09:11,154 --> 00:09:13,070
Значи имаме example--
или два примери here--

185
00:09:13,070 --> 00:09:15,590
на постојана алгоритми време,
кој секогаш се

186
00:09:15,590 --> 00:09:17,980
една операција во најлош случај.

187
00:09:17,980 --> 00:09:20,050
Така, првиот example--
имаме функција

188
00:09:20,050 --> 00:09:23,952
наречен 4 за вас, кои
го низа од големината 1.000.

189
00:09:23,952 --> 00:09:25,660
Но, тогаш, очигледно
всушност не ја гледам

190
00:09:25,660 --> 00:09:29,000
во it-- не навистина се грижат што е
во него, на таа низа.

191
00:09:29,000 --> 00:09:30,820
Секогаш се враќа само четири.

192
00:09:30,820 --> 00:09:32,940
Значи, тоа алгоритам,
и покрај фактот дека тоа

193
00:09:32,940 --> 00:09:35,840
зема 1.000 елементи не
направи ништо со нив.

194
00:09:35,840 --> 00:09:36,590
Само четири се враќа.

195
00:09:36,590 --> 00:09:38,240
Тоа е секогаш еден чекор.

196
00:09:38,240 --> 00:09:41,600
>> Всушност, додадете 2 nums-- која
видовме пред како well--

197
00:09:41,600 --> 00:09:43,680
само процеси два цели броја.

198
00:09:43,680 --> 00:09:44,692
Тоа не е еден чекор.

199
00:09:44,692 --> 00:09:45,900
Тоа е всушност неколку чекори.

200
00:09:45,900 --> 00:09:50,780
Ќе добиете, ќе добие б, ќе им додадете
заедно, и излез на резултатите.

201
00:09:50,780 --> 00:09:53,270
Така, тоа е во 84 чекори.

202
00:09:53,270 --> 00:09:55,510
Но тоа е секогаш константна,
без оглед на a или b.

203
00:09:55,510 --> 00:09:59,240
Што треба да се добие, да добијат б, се додаваат
нив заедно, излезен резултат.

204
00:09:59,240 --> 00:10:02,900
Значи тоа е постојана алгоритам време.

205
00:10:02,900 --> 00:10:05,170
>> Еве еден пример на
линеарно време algorithm--

206
00:10:05,170 --> 00:10:08,740
алгоритам што gets-- кој трае
еден дополнителен чекор, можеби,

207
00:10:08,740 --> 00:10:10,740
бидејки вашите расте за 1.

208
00:10:10,740 --> 00:10:14,190
Значи, да речеме дека ние сме во потрага по
бројот 5 во внатрешноста на низа.

209
00:10:14,190 --> 00:10:16,774
Можеби сте во ситуација каде што
можете да го најдете прилично рано.

210
00:10:16,774 --> 00:10:18,606
Но вие исто така може да има
ситуација во која

211
00:10:18,606 --> 00:10:20,450
може да биде последен елемент од низата.

212
00:10:20,450 --> 00:10:23,780
Во низа на големина 5, ако
ние сме во потрага за бројот 5.

213
00:10:23,780 --> 00:10:25,930
Тоа ќе бидат потребни 5 чекори.

214
00:10:25,930 --> 00:10:29,180
И всушност, замисли дека има
5 не било каде во оваа низа.

215
00:10:29,180 --> 00:10:32,820
Ние се уште се всушност треба да се погледне во
секој елемент од низата

216
00:10:32,820 --> 00:10:35,550
со цел да се утврди
дали или не 5 е таму.

217
00:10:35,550 --> 00:10:39,840
>> Значи, во најлош случај, а тоа е дека
елементот е последна во низата

218
00:10:39,840 --> 00:10:41,700
или не постои.

219
00:10:41,700 --> 00:10:44,690
Ние се уште треба да се погледне во
сите од n елементи.

220
00:10:44,690 --> 00:10:47,120
И така овој алгоритам
работи во линеарно време.

221
00:10:47,120 --> 00:10:50,340
Може да се потврди дека со
екстраполација малку со зборовите:

222
00:10:50,340 --> 00:10:53,080
ако имавме 6-елемент низа и
бевме во потрага по бројот 5,

223
00:10:53,080 --> 00:10:54,890
тоа може да потрае 6 чекори.

224
00:10:54,890 --> 00:10:57,620
Ако имаме 7-елемент низа и
ние сме во потрага за бројот 5.

225
00:10:57,620 --> 00:10:59,160
Тоа може да потрае 7 чекори.

226
00:10:59,160 --> 00:11:02,920
Како што додаде уште еден елемент на нашата
низа, што е потребно уште еден чекор.

227
00:11:02,920 --> 00:11:06,750
Тоа е линеарен алгоритам
во најлош случај.

228
00:11:06,750 --> 00:11:08,270
>> Неколку брзи прашања за вас.

229
00:11:08,270 --> 00:11:11,170
Што е runtime-- што е
најлош случај траење

230
00:11:11,170 --> 00:11:13,700
на овој особено програмка на код?

231
00:11:13,700 --> 00:11:17,420
Па имам 4 јамка тука што тече
од ѕ еднакво на 0, по целиот пат до м.

232
00:11:17,420 --> 00:11:21,980
И она што го гледам тука, е во тоа што
органот на јамка работи во временска константа.

233
00:11:21,980 --> 00:11:24,730
Па со користење на терминологија, која
Ние веќе разговаравме about-- што

234
00:11:24,730 --> 00:11:29,390
ќе биде најлош случај
траење на овој алгоритам?

235
00:11:29,390 --> 00:11:31,050
Се земе втора.

236
00:11:31,050 --> 00:11:34,270
Внатрешниот дел од циклусот
работи во временска константа.

237
00:11:34,270 --> 00:11:37,510
И на надворешниот дел на
јамка ќе работи м пати.

238
00:11:37,510 --> 00:11:40,260
Значи, што е најлош случај траење тука?

239
00:11:40,260 --> 00:11:43,210
Ми го погоди голема-О на м?

240
00:11:43,210 --> 00:11:44,686
Ќе бидете во право.

241
00:11:44,686 --> 00:11:46,230
>> Како за уште еден?

242
00:11:46,230 --> 00:11:48,590
Овој пат имаме
јамка внатрешноста на јамка.

243
00:11:48,590 --> 00:11:50,905
Имаме надворешниот циклус
која се протега од нула до стр.

244
00:11:50,905 --> 00:11:54,630
А ние имаме внатрешниот циклус што тече
од нула до p и внатре во тоа,

245
00:11:54,630 --> 00:11:57,890
Изјавувам дека на телото на
јамка работи во временска константа.

246
00:11:57,890 --> 00:12:02,330
Значи, што е најлош случај траење
на овој особено програмка на код?

247
00:12:02,330 --> 00:12:06,140
Па, повторно, имаме
надворешниот циклус што тече стр пати.

248
00:12:06,140 --> 00:12:09,660
И секоја итерација time--
од тој циклус, наместо.

249
00:12:09,660 --> 00:12:13,170
Имаме внатрешниот циклус
кој исто така води стр пати.

250
00:12:13,170 --> 00:12:16,900
А потоа внатре во тоа, тука е и
постојана time-- малку програмка таму.

251
00:12:16,900 --> 00:12:19,890
>> Значи, ако имаме надворешниот циклус кои
тече стр пати во внатрешноста на кој е

252
00:12:19,890 --> 00:12:22,880
внатрешниот циклус кој
тече стр times-- она ​​што е

253
00:12:22,880 --> 00:12:26,480
најлош случај траење
на овој код?

254
00:12:26,480 --> 00:12:30,730
Ми го погоди голема-О на стр квадрат?

255
00:12:30,730 --> 00:12:31,690
>> Јас сум Даг Лојд.

256
00:12:31,690 --> 00:12:33,880
Ова е CS50.

257
00:12:33,880 --> 00:12:35,622