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

2
00:00:05,830 --> 00:00:07,910
>> Bütün hüquqlar, belə ki, hesablama mürəkkəblik.

3
00:00:07,910 --> 00:00:10,430
Bir xəbərdarlıq yalnız bir az
biz də far-- dalış əvvəl

4
00:00:10,430 --> 00:00:13,070
Bu yəqin ki, arasında olacaq
ən math ağır şeylər

5
00:00:13,070 --> 00:00:14,200
biz CS50 haqqında danışmaq.

6
00:00:14,200 --> 00:00:16,950
Ümid edirəm ki, çox böyük olmayacaq
və biz cəhd və sizə yardım olacaq

7
00:00:16,950 --> 00:00:19,200
prosesi, lakin
ədalətli xəbərdarlıq bir bit.

8
00:00:19,200 --> 00:00:21,282
Bir az var
riyaziyyat burada iştirak edir.

9
00:00:21,282 --> 00:00:23,990
Bütün hüquqlar, üçün belə etmək
Bizim hesablama resurslarından istifadə

10
00:00:23,990 --> 00:00:28,170
real dünyada olan bu, həqiqətən var
alqoritmlər anlamaq üçün vacibdir

11
00:00:28,170 --> 00:00:30,750
və necə data emal.

12
00:00:30,750 --> 00:00:32,810
Biz əgər həqiqətən
səmərəli alqoritm, biz

13
00:00:32,810 --> 00:00:36,292
ehtiyatların məbləği minimuma endirmək olar
biz ilə məşğul var.

14
00:00:36,292 --> 00:00:38,750
Biz bir alqoritm varsa ki,
iş bir çox etmək niyyətindədir

15
00:00:38,750 --> 00:00:41,210
həqiqətən emal
məlumatların böyük set, bu

16
00:00:41,210 --> 00:00:44,030
daha tələb edir
daha çox vəsait, və

17
00:00:44,030 --> 00:00:47,980
məhsullarının pul, RAM, bütün növüdür.

18
00:00:47,980 --> 00:00:52,090
>> Belə ki, qadir olan bir analiz etmək
alqoritm, bu alət dəsti istifadə edərək,

19
00:00:52,090 --> 00:00:56,110
əsasən, question-- soruşur
bu alqoritm miqyaslı nə necə

20
00:00:56,110 --> 00:00:59,020
biz bunu daha çox məlumat atmaq kimi?

21
00:00:59,020 --> 00:01:02,220
CS50, biz data məbləği istəyirik
ilə iş olduqca kiçik.

22
00:01:02,220 --> 00:01:05,140
Ümumiyyətlə, bizim proqramları gedir
ikinci və ya less-- run

23
00:01:05,140 --> 00:01:07,830
yəqin ki, çox az
xüsusilə erkən.

24
00:01:07,830 --> 00:01:12,250
>> Amma ki, məşğul olan bir şirkət haqqında düşünmək
müştərilərin milyonlarla yüzlərlə ilə.

25
00:01:12,250 --> 00:01:14,970
Onlar emal etmək lazımdır
ki, müştəri data.

26
00:01:14,970 --> 00:01:18,260
Müştərilərin sayı kimi, onlar
var, böyük və daha böyük olur

27
00:01:18,260 --> 00:01:21,230
Bu tələb olacaq
daha çox resursları.

28
00:01:21,230 --> 00:01:22,926
Necə bir çox resursları?

29
00:01:22,926 --> 00:01:25,050
Yaxşı ki, necə asılıdır
biz alqoritm təhlil

30
00:01:25,050 --> 00:01:28,097
Bu Toolbox vasitələrdən istifadə.

31
00:01:28,097 --> 00:01:31,180
Biz mürəkkəbliyi haqqında danışmaq zaman
bir alqoritm bəzən will

32
00:01:31,180 --> 00:01:34,040
Bu vaxt adlandırılacaq eşitmək
mürəkkəbliyi və ya kosmik mürəkkəbliyi

33
00:01:34,040 --> 00:01:36,190
lakin biz yalnız olacaq
complexity-- zəng etmək üçün

34
00:01:36,190 --> 00:01:38,770
biz ümumiyyətlə söhbət edirik
ən pis ssenari.

35
00:01:38,770 --> 00:01:42,640
Mütləq pis qalaq verilir
biz bunu atma bilər data,

36
00:01:42,640 --> 00:01:46,440
necə bu alqoritm gedir
emal və ya data ilə məşğul?

37
00:01:46,440 --> 00:01:51,450
Biz, ümumiyyətlə, ən pis halda zəng
bir alqoritm böyük O uzunluğu.

38
00:01:51,450 --> 00:01:56,770
Belə ki, bir alqoritm belə bilər
kvadrat n və ya n O O axır.

39
00:01:56,770 --> 00:01:59,110
Haqqında və daha çox nə
o ikinci deməkdir.

40
00:01:59,110 --> 00:02:01,620
>> Bəzən də, biz qayğı yoxdur
yaxşı ssenari haqqında.

41
00:02:01,620 --> 00:02:05,400
Data hər şey, biz istədik
olmaq və tamamilə mükəmməl idi

42
00:02:05,400 --> 00:02:09,630
və biz bu mükəmməl göndərilməsi edildi
Bizim alqoritm vasitəsilə məlumatların seçin.

43
00:02:09,630 --> 00:02:11,470
Necə ki, vəziyyət idarə olardı?

44
00:02:11,470 --> 00:02:15,050
Biz bəzən kimi istinad
böyük Omega, böyük O fərqli olaraq, belə ki,

45
00:02:15,050 --> 00:02:16,530
biz böyük Omega var.

46
00:02:16,530 --> 00:02:18,880
Ən yaxşı ssenariyə Big-Omega.

47
00:02:18,880 --> 00:02:21,319
Ən pis halda ssenari üçün Big-O.

48
00:02:21,319 --> 00:02:23,860
Ümumiyyətlə, biz zaman danışmaq
bir alqoritm mürəkkəbliyi,

49
00:02:23,860 --> 00:02:26,370
bəhs edirik
ən pis ssenari.

50
00:02:26,370 --> 00:02:28,100
Belə ki, nəzərə ki, saxlamaq.

51
00:02:28,100 --> 00:02:31,510
>> Bu sinif, biz ümumiyyətlə olacaq
kənara ciddi təhlili tərk etmək.

52
00:02:31,510 --> 00:02:35,350
Elmlər və sahələri var
Bu cür şeylər həsr olunmuş.

53
00:02:35,350 --> 00:02:37,610
Biz ağıl haqqında danışmaq zaman
alqoritmlər vasitəsilə,

54
00:02:37,610 --> 00:02:41,822
biz çox parça-by-parça edəcəyik ki,
alqoritmlər biz sinif haqqında danışmaq.

55
00:02:41,822 --> 00:02:44,780
Biz, həqiqətən, yalnız söhbət edirik
ümumi mənada vasitəsilə əsaslandırıcı,

56
00:02:44,780 --> 00:02:47,070
Biz düsturlar, və ya dəlillər,
ya kimi bir şey.

57
00:02:47,070 --> 00:02:51,600
Belə ki, narahat olmayın, biz olmayacaq
böyük math sinif çevrilir.

58
00:02:51,600 --> 00:02:55,920
>> Belə ki, biz mürəkkəbliyi qayğı bildirib
Bu sual, necə soruşur, çünki

59
00:02:55,920 --> 00:03:00,160
Bizim alqoritmlər böyük idarə edirsiniz və
böyük data dəstləri onlara atılır.

60
00:03:00,160 --> 00:03:01,960
Yaxşı, bir data set nədir?

61
00:03:01,960 --> 00:03:03,910
Hesab edirəm ki, dedi mən nə demək idi?

62
00:03:03,910 --> 00:03:07,600
Bu ən edir nə deməkdir
kontekstində mənada vicdanlı olmalıdır.

63
00:03:07,600 --> 00:03:11,160
Biz bir alqoritm varsa
Prosesləri Strings-- biz yəqin edirik

64
00:03:11,160 --> 00:03:13,440
simli ölçüsü haqqında söhbət.

65
00:03:13,440 --> 00:03:15,190
Bu data var set--
ölçüsü, sayı

66
00:03:15,190 --> 00:03:17,050
simli etmək simvol.

67
00:03:17,050 --> 00:03:20,090
Biz söhbət edirik, əgər
faylları emal alqoritm,

68
00:03:20,090 --> 00:03:23,930
biz necə söhbət ola bilər
çox kilobayt fayl ibarətdir.

69
00:03:23,930 --> 00:03:25,710
Və data set var.

70
00:03:25,710 --> 00:03:28,870
Biz alqoritm bəhs edirsinizsə
ki, ümumiyyətlə serialların emal

71
00:03:28,870 --> 00:03:31,510
Belə çeşidlənməsi alqoritmlərin kimi
və ya alqoritmlər axtarış

72
00:03:31,510 --> 00:03:36,690
biz yəqin ki, sayı haqqında söhbət edirik
bir sıra təşkil elementləri.

73
00:03:36,690 --> 00:03:39,272
>> İndi biz bir ölçmək bilər
alqoritm, xüsusilə,

74
00:03:39,272 --> 00:03:40,980
Mən deyəndə biz
Mən bir alqoritm ölçmək

75
00:03:40,980 --> 00:03:43,840
Biz necə ölçmək bilər deməkdir
çox resursları onu edir.

76
00:03:43,840 --> 00:03:48,990
Bu resursları olsun, nə qədər
RAM-- bir bayt və ya RAM megabayt

77
00:03:48,990 --> 00:03:49,790
Bu istifadə edir.

78
00:03:49,790 --> 00:03:52,320
Və ya nə qədər vaxt çalıştırmak üçün edir.

79
00:03:52,320 --> 00:03:56,200
Və biz bu zəng edə bilərsiniz
n f, özbaşına, ölçmək.

80
00:03:56,200 --> 00:03:59,420
Harada n sayı
data set elementləri.

81
00:03:59,420 --> 00:04:02,640
Və n f neçə somethings var.

82
00:04:02,640 --> 00:04:07,530
Neçə resurslarının kontur yoxdur
bu məlumatların emal tələb edir.

83
00:04:07,530 --> 00:04:10,030
>> İndi biz, həqiqətən, qayğı yoxdur
dəqiq n f nə haqqında.

84
00:04:10,030 --> 00:04:13,700
Əslində, biz çox nadir hallarda will--
əlbəttə ki, heç vaxt bu sinif I

85
00:04:13,700 --> 00:04:18,709
Hər hansı bir həqiqətən dərin dalış
f n nə təhlili.

86
00:04:18,709 --> 00:04:23,510
Biz yalnız nə f haqqında danışmaq olacaq
n təxminən ya nə üçün çalışır.

87
00:04:23,510 --> 00:04:27,600
Və bir alqoritm meyl edir
yüksək order müddəti ilə diktə.

88
00:04:27,600 --> 00:04:29,440
Və biz nə edə bilərsiniz I
alaraq ki, demək

89
00:04:29,440 --> 00:04:31,910
bir daha konkret misal oldu.

90
00:04:31,910 --> 00:04:34,620
>> Belə ki, biz var ki, deyək
üç müxtəlif alqoritmləri.

91
00:04:34,620 --> 00:04:39,350
olan ilk n edir
resursların kuşbaşı, bəzi bölmələri

92
00:04:39,350 --> 00:04:42,880
ölçüsü n data set emal.

93
00:04:42,880 --> 00:04:47,000
Biz alır ikinci alqoritm var
Cubed plus n kvadrat resursları n

94
00:04:47,000 --> 00:04:49,350
ölçüsü n data set emal.

95
00:04:49,350 --> 00:04:52,030
Və biz bir üçüncü var
ki in-- çalışır alqoritm

96
00:04:52,030 --> 00:04:58,300
tutur n Cubed minus 8n kvadrat
resursların plus 20 n dənə

97
00:04:58,300 --> 00:05:02,370
bir alqoritm emal
ölçüsü n müəyyən məlumatları ilə.

98
00:05:02,370 --> 00:05:05,594
>> İndi yenə, biz, həqiqətən niyyətində deyil
detal bu səviyyəyə almaq.

99
00:05:05,594 --> 00:05:08,260
Mən yalnız bu qədər var həqiqətən alıram
burada bir nöqtəyə bir illüstrasiya kimi

100
00:05:08,260 --> 00:05:10,176
Mən gedirəm ki,
, ikinci edilməsi olan

101
00:05:10,176 --> 00:05:12,980
biz yalnız həqiqətən qayğı ki,
şeyi tendensiya haqqında

102
00:05:12,980 --> 00:05:14,870
data dəstləri daha böyük almaq kimi.

103
00:05:14,870 --> 00:05:18,220
Data set kiçik Belə ki, var
həqiqətən, olduqca böyük fərq

104
00:05:18,220 --> 00:05:19,870
bu alqoritmlər.

105
00:05:19,870 --> 00:05:23,000
orada üçüncü alqoritm
13 dəfə uzun çəkir

106
00:05:23,000 --> 00:05:27,980
Resurslarının 13 dəfə məbləği
ilk bir nisbi çalıştırmak üçün.

107
00:05:27,980 --> 00:05:31,659
>> Bizim data set ölçüsü 10, əgər ki,
, böyük, lakin mütləq böyük deyil

108
00:05:31,659 --> 00:05:33,950
biz orada olduğunu görə bilərsiniz
həqiqətən bir fərq bir az.

109
00:05:33,950 --> 00:05:36,620
Üçüncü alqoritm
daha səmərəli olur.

110
00:05:36,620 --> 00:05:40,120
Bu, həqiqətən, 40% haqqında -
və ya 60% daha səmərəli.

111
00:05:40,120 --> 00:05:41,580
40% vaxt məbləği alır.

112
00:05:41,580 --> 00:05:45,250
Bu bilər run-- bilər
Resursların 400 ədəd

113
00:05:45,250 --> 00:05:47,570
ölçüsü 10 data set emal.

114
00:05:47,570 --> 00:05:49,410
Ilk Halbuki
alqoritm, əksinə,

115
00:05:49,410 --> 00:05:54,520
resursların 1000 ədəd edir
ölçüsü 10 data set emal.

116
00:05:54,520 --> 00:05:57,240
Amma nə baxmaq
Bizim nömrələri daha böyük almaq.

117
00:05:57,240 --> 00:05:59,500
>> İndi fərq
bu alqoritmlər arasında

118
00:05:59,500 --> 00:06:01,420
bir az daha az müəyyən olmağa başlayır.

119
00:06:01,420 --> 00:06:04,560
Var ki, və əslində
aşağı sifariş şərtlərlə daha doğrusu,

120
00:06:04,560 --> 00:06:09,390
aşağı exponents-- ilə şərtləri
qalxsın başlayın.

121
00:06:09,390 --> 00:06:12,290
Bir veri set ölçüsü əgər
1000 və ilk alqoritm

122
00:06:12,290 --> 00:06:14,170
bir milyard addımlar çalışır.

123
00:06:14,170 --> 00:06:17,880
İkinci alqoritm çalışır
bir milyard və bir milyon addımlar.

124
00:06:17,880 --> 00:06:20,870
Və üçüncü alqoritm çalışır
bir milyard addımlar yalnız utancaq olan.

125
00:06:20,870 --> 00:06:22,620
Bu olduqca çox bir milyard addımlar var.

126
00:06:22,620 --> 00:06:25,640
Həmin aşağı sifariş şərtləri başlamaq
həqiqətən yersiz olmaq.

127
00:06:25,640 --> 00:06:27,390
Və yalnız həqiqətən
ev hammer point

128
00:06:27,390 --> 00:06:31,240
data giriş ölçüsü a olduqda
million-- bütün bunlar üç olduqca çox

129
00:06:31,240 --> 00:06:34,960
bir quintillion-- əgər almaq
mənim riyaziyyat correct-- addımlar

130
00:06:34,960 --> 00:06:37,260
bir veri giriş emal
ölçüsü bir milyon.

131
00:06:37,260 --> 00:06:38,250
Bu addımlar bir çox var.

132
00:06:38,250 --> 00:06:42,092
Və əslində onlardan biri bilər
bir neçə 100,000 və ya bir neçə 100

133
00:06:42,092 --> 00:06:44,650
milyon daha az zaman
biz bir sıra bəhs edirik

134
00:06:44,650 --> 00:06:46,990
ki, bu cür yersiz var big--.

135
00:06:46,990 --> 00:06:50,006
Onlar bütün edirlər
təxminən n Cubed,

136
00:06:50,006 --> 00:06:52,380
və biz, həqiqətən, həvalə edirəm
bu alqoritmlərin bütün

137
00:06:52,380 --> 00:06:59,520
n qaydada olaraq
Cubed və ya n Cubed böyük-O.

138
00:06:59,520 --> 00:07:03,220
>> Burada daha çox bəzi bir siyahısı
ümumi hesablama mürəkkəblik dərsləri

139
00:07:03,220 --> 00:07:05,820
biz qarşılaşa bilərsiniz ki,
alqoritmlər, ümumiyyətlə.

140
00:07:05,820 --> 00:07:07,970
Və həmçinin xüsusi CS50.

141
00:07:07,970 --> 00:07:11,410
Bu sifariş olunur
ümumiyyətlə üst sürətli,

142
00:07:11,410 --> 00:07:13,940
altındakı ümumiyyətlə yavaş üçün.

143
00:07:13,940 --> 00:07:16,920
Belə ki, daimi vaxt alqoritmlər edirlər
asılı olmayaraq, sürətli olmaq

144
00:07:16,920 --> 00:07:19,110
ölçüsü
data giriş Siz keçir.

145
00:07:19,110 --> 00:07:23,760
Onlar həmişə bir əməliyyat və ya
ilə məşğul resurslarının bir vahid.

146
00:07:23,760 --> 00:07:25,730
2 ola bilər, güc
3 olmaq, 4 ola bilər.

147
00:07:25,730 --> 00:07:26,910
Amma bu, daimi sıra var.

148
00:07:26,910 --> 00:07:28,400
Bu fərqli deyil.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmik vaxt alqoritmlər
qədər yaxşıdır.

150
00:07:31,390 --> 00:07:33,950
Və həqiqətən yaxşı nümunə
bir logarithmic vaxt alqoritm

151
00:07:33,950 --> 00:07:37,420
siz mütləq artıq görüldü etdik
telefon kitab ayrı qoparmaq

152
00:07:37,420 --> 00:07:39,480
telefon kitab Mike Smith tapmaq üçün.

153
00:07:39,480 --> 00:07:40,980
Biz yarısında problem kəsdi.

154
00:07:40,980 --> 00:07:43,580
Və n daha böyük olur, belə ki,
və daha böyük və larger--

155
00:07:43,580 --> 00:07:47,290
əslində, hər zaman siz ikiqat
n, yalnız daha bir addım atır.

156
00:07:47,290 --> 00:07:49,770
Ki, bir çox daha yaxşıdır, belə ki,
daha demək, xətti vaxt.

157
00:07:49,770 --> 00:07:53,030
Siz n ikiqat əgər Hansı bu,
addımlar sayı iki dəfə edir.

158
00:07:53,030 --> 00:07:55,980
Siz n üçqat, bu, davam edir
addımlar sayı üç dəfə.

159
00:07:55,980 --> 00:07:58,580
Vahidi Bir addım.

160
00:07:58,580 --> 00:08:01,790
>> Sonra hər şeyi bir az more-- almaq
az az böyük oradan.

161
00:08:01,790 --> 00:08:06,622
Siz bəzən xətti bədii vaxt
log xətti vaxt deyilən və ya n log n.

162
00:08:06,622 --> 00:08:08,330
Və biz nümunə lazımdır
bir alqoritm ki,

163
00:08:08,330 --> 00:08:13,370
hələ yaxşıdır n log n, çalışır
daha kvadrat sýrada n kvadrat.

164
00:08:13,370 --> 00:08:17,320
Və ya çoxhədli dəfə, n iki
Iki daha çox hər hansı bir sayı.

165
00:08:17,320 --> 00:08:20,810
Və ya exponential vaxt, hansı
hətta worse-- C n edir.

166
00:08:20,810 --> 00:08:24,670
Belə ki, bəzi sabit sayı qaldırdı
giriş ölçüsü gücü.

167
00:08:24,670 --> 00:08:28,990
Belə ki, əgər 1,000-- var, əgər
data giriş, ölçüsü 1000 edir

168
00:08:28,990 --> 00:08:31,310
Bu 1000-ci hakimiyyətə C edəcək.

169
00:08:31,310 --> 00:08:33,559
Bu çoxhədli dəfə çox pis.

170
00:08:33,559 --> 00:08:35,030
>> Faktöryel vaxt daha pisdir.

171
00:08:35,030 --> 00:08:37,760
Və əslində, həqiqətən, orada nə
sonsuz vaxt alqoritmlər var,

172
00:08:37,760 --> 00:08:43,740
kimin belə qondarma kimi axmaq sort
iş təsadüfi bir sıra shuffle üçün

173
00:08:43,740 --> 00:08:45,490
və sonra kontrol
olub sıralanır.

174
00:08:45,490 --> 00:08:47,589
Və bu təsadüfi deyil, əgər
daha array shuffle

175
00:08:47,589 --> 00:08:49,130
və sıralanır olsun kontrol edin.

176
00:08:49,130 --> 00:08:51,671
Və yəqin ki, imagine-- bilər
Siz bir vəziyyət təsəvvür edə bilərsiniz

177
00:08:51,671 --> 00:08:55,200
burada ən pis halda, bu iradə
həqiqətən sıra ilə başlamaq heç vaxt.

178
00:08:55,200 --> 00:08:57,150
Bu alqoritm əbədi çalışır.

179
00:08:57,150 --> 00:08:59,349
Və belə ki, bir olardı
sonsuz vaxt alqoritm.

180
00:08:59,349 --> 00:09:01,890
İnşallah yazılı olmayacaq
Hər hansı bir faktöryel və ya sonsuz vaxt

181
00:09:01,890 --> 00:09:04,510
CS50 alqoritmləri.

182
00:09:04,510 --> 00:09:09,150
>> Belə ki, götürək bir az daha
Bəzi sadə beton baxmaq

183
00:09:09,150 --> 00:09:11,154
hesablama mürəkkəblik dərsləri.

184
00:09:11,154 --> 00:09:13,070
Beləliklə, biz bir misal var
və ya iki nümunələri burada

185
00:09:13,070 --> 00:09:15,590
daimi vaxt alqoritmlərin,
olan həmişə almaq

186
00:09:15,590 --> 00:09:17,980
ən pis halda bir əməliyyat.

187
00:09:17,980 --> 00:09:20,050
Ilk misal Belə ki,
biz bir funksiyası var

188
00:09:20,050 --> 00:09:23,952
, sizin üçün 4 adlanan
ölçüsü 1000 bir sıra edir.

189
00:09:23,952 --> 00:09:25,660
Amma sonra yəqin
həqiqətən baxmaq deyil

190
00:09:25,660 --> 00:09:29,000
pseudocode həqiqətən nə qayğı deyil at
bunun daxili ki, serialın.

191
00:09:29,000 --> 00:09:30,820
Həmişə yalnız dörd qaytarır.

192
00:09:30,820 --> 00:09:32,940
Belə ki, alqoritm,
bu, baxmayaraq ki,

193
00:09:32,940 --> 00:09:35,840
1000 elementləri deyil edir
onlara bir şey yoxdur.

194
00:09:35,840 --> 00:09:36,590
Yalnız dörd qaytarır.

195
00:09:36,590 --> 00:09:38,240
O, həmişə bir addım var.

196
00:09:38,240 --> 00:09:41,600
>> Əslində, 2 nums-- əlavə olan
biz well-- əvvəl gördüm

197
00:09:41,600 --> 00:09:43,680
yalnız iki integers emal edir.

198
00:09:43,680 --> 00:09:44,692
Bu bir addım deyil.

199
00:09:44,692 --> 00:09:45,900
Bu, həqiqətən bir neçə addımlar var.

200
00:09:45,900 --> 00:09:50,780
Siz almaq, b almaq, onlara əlavə
Birlikdə, siz çıxış nəticələri.

201
00:09:50,780 --> 00:09:53,270
Belə ki, 84 addımlar var.

202
00:09:53,270 --> 00:09:55,510
Lakin bu, həmişə sabit var
asılı olmayaraq və ya b.

203
00:09:55,510 --> 00:09:59,240
Siz almaq lazımdır, b almaq, əlavə
birlikdə onlara çıxış nəticəsidir.

204
00:09:59,240 --> 00:10:02,900
Belə ki, bir daimi vaxt alqoritm var.

205
00:10:02,900 --> 00:10:05,170
>> Burada bir misal var
xətti vaxt alqoritm

206
00:10:05,170 --> 00:10:08,740
ki, edir gets-- alqoritm
bir əlavə addım, bəlkə,

207
00:10:08,740 --> 00:10:10,740
Sizin input 1-artır kimi.

208
00:10:10,740 --> 00:10:14,190
Belə ki, biz aradığınız deyək
bir sıra sayı 5 daxilində.

209
00:10:14,190 --> 00:10:16,774
Siz bir vəziyyət olduğu ola bilər
Siz kifayət qədər erkən tapa bilərsiniz.

210
00:10:16,774 --> 00:10:18,606
Amma siz də ola bilər
bir vəziyyət harada

211
00:10:18,606 --> 00:10:20,450
serialın son element ola bilər.

212
00:10:20,450 --> 00:10:23,780
Ölçüsü 5 bir sıra, əgər
Biz sayı 5 aradığınız.

213
00:10:23,780 --> 00:10:25,930
5 addımlar edəcək.

214
00:10:25,930 --> 00:10:29,180
Və əslində, var ki, təsəvvür
Bu array deyil 5 yerdə.

215
00:10:29,180 --> 00:10:32,820
Biz hələ həqiqətən baxmaq
serialın hər bir element

216
00:10:32,820 --> 00:10:35,550
müəyyən etmək üçün
və ya 5 var.

217
00:10:35,550 --> 00:10:39,840
>> Belə ki, ən pis halda,
element array son

218
00:10:39,840 --> 00:10:41,700
və ya bütün mövcud deyil.

219
00:10:41,700 --> 00:10:44,690
Biz hələ baxmaq lazımdır
n elementləri bütün.

220
00:10:44,690 --> 00:10:47,120
Və bu alqoritm
xətti vaxt çalışır.

221
00:10:47,120 --> 00:10:50,340
Siz ki, təsdiq edə bilər
deyərək bir az apardığımızda,

222
00:10:50,340 --> 00:10:53,080
biz 6 element array idi əgər
biz, sayı 5 aradığınız

223
00:10:53,080 --> 00:10:54,890
6 addımlar bilər.

224
00:10:54,890 --> 00:10:57,620
Biz 7 element array var və
Biz sayı 5 aradığınız.

225
00:10:57,620 --> 00:10:59,160
7 addımlar bilər.

226
00:10:59,160 --> 00:11:02,920
Biz bir daha element əlavə olaraq
array, bu daha bir addım edir.

227
00:11:02,920 --> 00:11:06,750
Ki, bir xətti alqoritm var
ən pis halda.

228
00:11:06,750 --> 00:11:08,270
>> Cütlük üçün tez suallar.

229
00:11:08,270 --> 00:11:11,170
Nə runtime-- nədir
ən pis halda uzunluğu

230
00:11:11,170 --> 00:11:13,700
kodu bu parçasını?

231
00:11:13,700 --> 00:11:17,420
Belə ki, çalışır, burada 4 loop var
j 0, m-ə qədər bütün yol bərabərdir edir.

232
00:11:17,420 --> 00:11:21,980
Və nə mən burada görürəm, ki,
loop bədən daimi vaxt çalışır.

233
00:11:21,980 --> 00:11:24,730
Belə terminologiya istifadə edərək
biz artıq nə about-- söhbət etdik

234
00:11:24,730 --> 00:11:29,390
ən pis halda olardı
Bu alqoritm uzunluğu?

235
00:11:29,390 --> 00:11:31,050
Ikinci edin.

236
00:11:31,050 --> 00:11:34,270
loop daxili
daimi vaxt çalışır.

237
00:11:34,270 --> 00:11:37,510
Və xarici hissəsi
loop m dəfə run gedir.

238
00:11:37,510 --> 00:11:40,260
Belə ki, ən pis halda runtime burada nə var?

239
00:11:40,260 --> 00:11:43,210
Siz m böyük O tahmin mi?

240
00:11:43,210 --> 00:11:44,686
Siz doğru olarıq.

241
00:11:44,686 --> 00:11:46,230
>> Necə başqa biri haqqında?

242
00:11:46,230 --> 00:11:48,590
Biz bu dəfə
bir loop daxilində loop.

243
00:11:48,590 --> 00:11:50,905
Biz xarici loop var
ki, sıfırdan p çalışır.

244
00:11:50,905 --> 00:11:54,630
Və biz çalışır daxili loop var
sıfırdan p ki, daxilində,

245
00:11:54,630 --> 00:11:57,890
Mən dövlət orqanı olduğunu
loop daimi vaxt çalışır.

246
00:11:57,890 --> 00:12:02,330
Belə ki, ən pis halda uzunluğu nə
kodu bu parçasını?

247
00:12:02,330 --> 00:12:06,140
Bəli, yenə, biz var
p dəfə çalışır xarici loop.

248
00:12:06,140 --> 00:12:09,660
Və hər sýrada iteration
ki loop deyil,.

249
00:12:09,660 --> 00:12:13,170
Biz daxili loop var
ki, p dəfə çalışır.

250
00:12:13,170 --> 00:12:16,900
Ki, daxilində Və sonra var
orada daimi sýrada az parçasını.

251
00:12:16,900 --> 00:12:19,890
>> Biz xarici loop varsa Belə ki,
olan daxili p dəfə çalışır

252
00:12:19,890 --> 00:12:22,880
daxili loop ki
nə dəfə təkrar p çalışır

253
00:12:22,880 --> 00:12:26,480
ən pis halda uzunluğu
kodu bu parçasını?

254
00:12:26,480 --> 00:12:30,730
Siz p böyük-O kare tahmin mi?

255
00:12:30,730 --> 00:12:31,690
>> Mən Doug Lloyd edirəm.

256
00:12:31,690 --> 00:12:33,880
Bu CS50 edir.

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