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

2
00:00:05,830 --> 00:00:07,910
>> Pekala, yani, hesaplama karmaşıklığı.

3
00:00:07,910 --> 00:00:10,430
Bir uyarı Sadece biraz
biz de far-- dalış önce

4
00:00:10,430 --> 00:00:13,070
bu muhtemelen arasında olacak
En matematik ağır şeyler

5
00:00:13,070 --> 00:00:14,200
Biz CS50 hakkında konuşmak.

6
00:00:14,200 --> 00:00:16,950
Umarım çok bunaltıcı olmayacak
ve biz denemek ve size rehberlik edeceğiz

7
00:00:16,950 --> 00:00:19,200
süreç boyunca, ancak
adil bir uyarı sadece biraz.

8
00:00:19,200 --> 00:00:21,282
Biraz var
matematik Burada yer.

9
00:00:21,282 --> 00:00:23,990
Pekala, sipariş, böylece yapmak
Bizim hesaplama kaynaklarının kullanımı

10
00:00:23,990 --> 00:00:28,170
Gerçek --daha dünya o gerçekten
algoritmaları anlamak önemlidir

11
00:00:28,170 --> 00:00:30,750
ve nasıl verileri işlemek.

12
00:00:30,750 --> 00:00:32,810
Biz varsa gerçekten
verimli bir algoritma, biz

13
00:00:32,810 --> 00:00:36,292
kaynak miktarını en aza indirebilir
biz onunla başa çıkmak için kullanılabilir olması.

14
00:00:36,292 --> 00:00:38,750
Biz bir algoritma varsa o
bir sürü iş almaya gidiyor

15
00:00:38,750 --> 00:00:41,210
Gerçekten işlemek için
verilerin büyük seti, bu kadar

16
00:00:41,210 --> 00:00:44,030
Daha fazla ihtiyaç olacak
daha fazla kaynak ve hangi

17
00:00:44,030 --> 00:00:47,980
şeyler para, RAM, tüm bu türüdür.

18
00:00:47,980 --> 00:00:52,090
>> Yani, edememek bir analiz
algoritması, bu araç seti kullanılarak

19
00:00:52,090 --> 00:00:56,110
Temel olarak, sorum sorar
Bu algoritma ölçeği nasıl yaptığını

20
00:00:56,110 --> 00:00:59,020
biz ona daha fazla veri atmak gibi?

21
00:00:59,020 --> 00:01:02,220
CS50 olarak, veri miktarını konum
ile çalışan oldukça küçük.

22
00:01:02,220 --> 00:01:05,140
Genellikle, bizim programlar gidiyor
ikinci veya less-- çalıştırmak için

23
00:01:05,140 --> 00:01:07,830
Muhtemelen çok daha az
Özellikle erken.

24
00:01:07,830 --> 00:01:12,250
>> Ama bu fırsatlar bir şirket hakkında düşünmek
müşterilerinin milyonlarca yüzlerce.

25
00:01:12,250 --> 00:01:14,970
Ve onlar işlemek gerekiyor
müşteri verileri.

26
00:01:14,970 --> 00:01:18,260
Müşteri sayısı arttıkça onlar
var, büyük ve daha büyük olur

27
00:01:18,260 --> 00:01:21,230
o gerektirecek gidiyor
Daha fazla ve daha fazla kaynak.

28
00:01:21,230 --> 00:01:22,926
Daha kaç kaynaklar?

29
00:01:22,926 --> 00:01:25,050
Peki, bu nasıl bağlıdır
Biz algoritma analiz,

30
00:01:25,050 --> 00:01:28,097
Bu araç kutusunda araçları kullanarak.

31
00:01:28,097 --> 00:01:31,180
Biz karmaşıklığı hakkında konuşmak
Bir algorithm-- hangi bazen olacak

32
00:01:31,180 --> 00:01:34,040
Bu zaman olarak ifade duymak
karmaşıklığı ya da uzay karmaşıklığı

33
00:01:34,040 --> 00:01:36,190
ama biz sadece gidiyoruz
complexity-- dönmesini

34
00:01:36,190 --> 00:01:38,770
genellikle bahsediyoruz
En kötü senaryo.

35
00:01:38,770 --> 00:01:42,640
Mutlak kötü kazık Verilen
biz ona atma olabilir veri,

36
00:01:42,640 --> 00:01:46,440
bu nasıl algoritma gidiyor
işlemek veya bu verilerle başa?

37
00:01:46,440 --> 00:01:51,450
Biz genellikle en kötü durum çağrı
bir algoritma büyük O zamanı.

38
00:01:51,450 --> 00:01:56,770
Yani bir algoritma söylenebilir
squared n ya n O O çalıştırın.

39
00:01:56,770 --> 00:01:59,110
Hakkında ve ne daha
Bu bir saniye demek.

40
00:01:59,110 --> 00:02:01,620
>> Bazen, ama, biz bakım yapmak
en iyi senaryo hakkında.

41
00:02:01,620 --> 00:02:05,400
Veri herşey ise istediğimiz
olması ve kesinlikle mükemmel oldu

42
00:02:05,400 --> 00:02:09,630
ve biz bu mükemmel gönderiyorlardı
Bizim algoritma sayesinde veri ayarlayın.

43
00:02:09,630 --> 00:02:11,470
Nasıl bu durumda ele alabileceğinizi?

44
00:02:11,470 --> 00:02:15,050
Biz bazen bu bakın
Büyük Omega, büyük-O tersine, bu yüzden

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

46
00:02:16,530 --> 00:02:18,880
En iyi senaryo için büyük-Omega.

47
00:02:18,880 --> 00:02:21,319
En kötü durum senaryosu için Büyük-O.

48
00:02:21,319 --> 00:02:23,860
Genellikle, biz yaklaşık ne zaman konuşmak
bir algoritma karmaşıklığı,

49
00:02:23,860 --> 00:02:26,370
Biz bahsediyoruz
En kötü durum senaryosu.

50
00:02:26,370 --> 00:02:28,100
Yani akılda tutmak.

51
00:02:28,100 --> 00:02:31,510
>> Ve bu sınıfta, genellikle gidiyoruz
bir kenara titiz analizler bırakmak.

52
00:02:31,510 --> 00:02:35,350
Bilimler ve alanlar vardır
bu tür şeylerle adamıştır.

53
00:02:35,350 --> 00:02:37,610
Biz akıl hakkında konuşmak
algoritmalar sayesinde,

54
00:02:37,610 --> 00:02:41,822
Biz birçok parça-by-parça yapacağım ki
algoritmalar Sınıfta hakkında konuşmak.

55
00:02:41,822 --> 00:02:44,780
Biz gerçekten sadece bahsediyoruz
sağduyu ile bu kadar akıl,

56
00:02:44,780 --> 00:02:47,070
değil formüller veya delillerle,
ya da böyle bir şey.

57
00:02:47,070 --> 00:02:51,600
Yani merak etmeyin, biz olmayacak
Büyük bir matematik dersinde dönüşüyor.

58
00:02:51,600 --> 00:02:55,920
>> Yani biz karmaşıklık umurumda dedi
o soruyu nasıl sorar çünkü

59
00:02:55,920 --> 00:03:00,160
Bizim algoritmaları büyük yapmalıyım ve
Büyük veri kümeleri onlara atılan.

60
00:03:00,160 --> 00:03:01,960
Peki, bir veri kümesi nedir?

61
00:03:01,960 --> 00:03:03,910
Bunu derken ne demek istedi?

62
00:03:03,910 --> 00:03:07,600
En yapar ne demektir
bağlamda duygusu, dürüst olmak gerekirse.

63
00:03:07,600 --> 00:03:11,160
Biz bir algoritma varsa
Süreçler Strings-- muhtemelen konum

64
00:03:11,160 --> 00:03:13,440
dize boyutu bahsediyoruz.

65
00:03:13,440 --> 00:03:15,190
Bu veriler bu set--
boyutu, sayısı

66
00:03:15,190 --> 00:03:17,050
dize oluşturan karakterlerin.

67
00:03:17,050 --> 00:03:20,090
Biz hakkında konuşuyor
dosyaları işleyen algoritması,

68
00:03:20,090 --> 00:03:23,930
Biz nasıl bahsediyoruz olabilir
Birçok kilobayt bu dosyayı içermektedir.

69
00:03:23,930 --> 00:03:25,710
Ve bu veri seti var.

70
00:03:25,710 --> 00:03:28,870
Biz bir algoritma hakkında konuşuyor
Bu, daha genel diziler kolları

71
00:03:28,870 --> 00:03:31,510
Böyle sıralama algoritmaları olarak
veya algoritmaları arıyor,

72
00:03:31,510 --> 00:03:36,690
biz muhtemelen sayı bahsediyoruz
bir dizi ihtiva elemanları.

73
00:03:36,690 --> 00:03:39,272
>> Şimdi, bir ölçebilirsiniz
algorithm-- özellikle

74
00:03:39,272 --> 00:03:40,980
Diyorum zaman biz
Ben, bir algoritma ölçmek

75
00:03:40,980 --> 00:03:43,840
Biz nasıl ölçebilirsiniz demek
Birçok kaynak bu kadar sürer.

76
00:03:43,840 --> 00:03:48,990
Bu kaynaklar olsun, kaç
RAM-- bayt veya RAM megabayt

77
00:03:48,990 --> 00:03:49,790
Kullandığı.

78
00:03:49,790 --> 00:03:52,320
Ya da ne kadar zaman çalıştırmak için alır.

79
00:03:52,320 --> 00:03:56,200
Ve biz bu çağırabilirsiniz
n f, keyfi, ölçmek.

80
00:03:56,200 --> 00:03:59,420
Burada, n, sayısıdır
veri kümesindeki elemanları.

81
00:03:59,420 --> 00:04:02,640
Ve n f kaç birşeyler olduğunu.

82
00:04:02,640 --> 00:04:07,530
Kaç kaynakların birimleri yapar
bu verilerin işlenmesi için gereklidir.

83
00:04:07,530 --> 00:04:10,030
>> Şimdi, biz aslında umurumda değil
Tam n f ne olduğu hakkında.

84
00:04:10,030 --> 00:04:13,700
Aslında, çok nadiren will--
Kesinlikle asla bu class-- I

85
00:04:13,700 --> 00:04:18,709
Herhangi gerçekten derin dalmak
f n ne analizi.

86
00:04:18,709 --> 00:04:23,510
Biz sadece ne f hakkında konuşmak için gidiyoruz
n yaklaşık ya da ne o eğilimi olduğunu.

87
00:04:23,510 --> 00:04:27,600
Ve bir algoritma eğilimidir
en yüksek sipariş dönemi tarafından dikte.

88
00:04:27,600 --> 00:04:29,440
Ve biz ne görebiliyorum ben
alarak bu demek

89
00:04:29,440 --> 00:04:31,910
Bir daha somut bir örneği inceleyelim.

90
00:04:31,910 --> 00:04:34,620
>> Yani biz diyelim
Üç farklı algoritmalar.

91
00:04:34,620 --> 00:04:39,350
Ilki n alır
Kaynakların küp, bazı birimler

92
00:04:39,350 --> 00:04:42,880
n büyüklüğünde bir veri kümesi işlem.

93
00:04:42,880 --> 00:04:47,000
Biz götüren ikinci bir algoritma var
kuşbaşı artı n karesi kaynaklar n

94
00:04:47,000 --> 00:04:49,350
n büyüklüğünde bir veri kümesi işlem.

95
00:04:49,350 --> 00:04:52,030
Ve biz üçüncü var
Bu açmayız çalışan algoritma

96
00:04:52,030 --> 00:04:58,300
kadar sürer n kuşbaşı eksi 8n karesi
Kaynakların artı 20 n ünite

97
00:04:58,300 --> 00:05:02,370
bir algoritma işlemek
n büyüklüğünde veri kümesi ile.

98
00:05:02,370 --> 00:05:05,594
>> Şimdi yine, biz gerçekten gitmiyor
ayrıntı bu seviyede içine alır.

99
00:05:05,594 --> 00:05:08,260
Ben sadece bu kadar var gerçekten değilim
Burada bir noktanın bir örnek olarak

100
00:05:08,260 --> 00:05:10,176
Ben olmak için gidiyorum
Bir saniye içinde yapma hangi

101
00:05:10,176 --> 00:05:12,980
biz sadece gerçekten umurumda olduğunu
şeylerin eğilimi hakkında

102
00:05:12,980 --> 00:05:14,870
veri setleri büyük olsun.

103
00:05:14,870 --> 00:05:18,220
Veri seti küçük Yani, orada
aslında oldukça büyük bir fark

104
00:05:18,220 --> 00:05:19,870
Bu algoritmalar.

105
00:05:19,870 --> 00:05:23,000
Orada üçüncü algoritma
13 kat daha uzun sürer

106
00:05:23,000 --> 00:05:27,980
Kaynak 13 katıdır
İlki göre çalıştırın.

107
00:05:27,980 --> 00:05:31,659
>> Bizim veri seti büyüklüğü 10 ise, hangi
daha büyük, ama mutlaka büyük değil

108
00:05:31,659 --> 00:05:33,950
Biz var olduğunu görebiliyorum
aslında bir fark biraz.

109
00:05:33,950 --> 00:05:36,620
Üçüncü algoritma
daha verimli hale gelir.

110
00:05:36,620 --> 00:05:40,120
Aslında yaklaşık% 40 var -
veya% 60 daha etkili.

111
00:05:40,120 --> 00:05:41,580
Bu% 40 zamanın miktarı alır.

112
00:05:41,580 --> 00:05:45,250
O alabilir run-- edebilirsiniz
Kaynak 400 tane

113
00:05:45,250 --> 00:05:47,570
büyüklüğü 10 bir veri kümesi işlem.

114
00:05:47,570 --> 00:05:49,410
İlk Oysa
algoritma, aksine,

115
00:05:49,410 --> 00:05:54,520
Kaynakların 1000 birimleri alır
büyüklüğü 10 bir veri kümesi işlem.

116
00:05:54,520 --> 00:05:57,240
Ama ne olur bak
Bizim sayılar daha da büyük olsun.

117
00:05:57,240 --> 00:05:59,500
>> Şimdi fark
Bu algoritmalar arasındaki

118
00:05:59,500 --> 00:06:01,420
biraz daha az belirgin hale başlar.

119
00:06:01,420 --> 00:06:04,560
Olduğunu ve aslında
düşük dereceli terms-- doğrusu

120
00:06:04,560 --> 00:06:09,390
Alt exponents-- ile terimler
ilgisiz olmaya başlar.

121
00:06:09,390 --> 00:06:12,290
Bir veri kümesi boyutu ise
1000 ve birinci algoritma

122
00:06:12,290 --> 00:06:14,170
milyar adımda çalışır.

123
00:06:14,170 --> 00:06:17,880
Ve ikinci algoritma çalışır
Bir milyar ve bir milyon adımlar.

124
00:06:17,880 --> 00:06:20,870
Ve üçüncü algoritma çalışır
Bir milyar adımlar sadece utangaç içinde.

125
00:06:20,870 --> 00:06:22,620
Oldukça fazla bir milyar adımlar var.

126
00:06:22,620 --> 00:06:25,640
Bu alt-mertebeden terimler başlar
Gerçekten önemsiz olmak.

127
00:06:25,640 --> 00:06:27,390
Ve sadece gerçekten
eve çekiç point--

128
00:06:27,390 --> 00:06:31,240
veri giriş boyutu a ise
million-- tüm bu üç hemen hemen

129
00:06:31,240 --> 00:06:34,960
tek quintillion-- eğer almak
benim matematik correct-- adım

130
00:06:34,960 --> 00:06:37,260
Bir veri giriş işlemek için
boyut, bir milyon.

131
00:06:37,260 --> 00:06:38,250
Bu adımların bir sürü.

132
00:06:38,250 --> 00:06:42,092
Ve gerçeği onlardan biri olabilir
Birkaç 100.000 ya da bir çift almak 100

133
00:06:42,092 --> 00:06:44,650
milyon daha az zaman
Biz bir sayı bahsediyoruz

134
00:06:44,650 --> 00:06:46,990
o tür alakasız big--.

135
00:06:46,990 --> 00:06:50,006
Hepsi almak eğilimindedir
Yaklaşık n kuşbaşı,

136
00:06:50,006 --> 00:06:52,380
ve bu yüzden biz aslında bakın istiyorsunuz
bu algoritmaların tüm

137
00:06:52,380 --> 00:06:59,520
n sırasına olarak
kuşbaşı veya n kuşbaşı büyük-O.

138
00:06:59,520 --> 00:07:03,220
>> İşte daha bazılarının bir listesi
Ortak hesaplama karmaşıklığı sınıfları

139
00:07:03,220 --> 00:07:05,820
Biz karşılaşacağınız o
algoritmalar, genellikle,.

140
00:07:05,820 --> 00:07:07,970
Ayrıca spesifik olarak CS50 bölgesindeki.

141
00:07:07,970 --> 00:07:11,410
Bunlar sipariş edilir
genellikle üst kısmında hızlı,

142
00:07:11,410 --> 00:07:13,940
altta genellikle yavaş etmek.

143
00:07:13,940 --> 00:07:16,920
Yani zaman sabiti algoritmaları eğilimindedir
ne olursa olsun, en hızlı olmak için

144
00:07:16,920 --> 00:07:19,110
büyüklüğünün
Veri girişi geçmek.

145
00:07:19,110 --> 00:07:23,760
Onlar her zaman bir işlem almak veya
başa kaynakların bir birim.

146
00:07:23,760 --> 00:07:25,730
Bu 2 olabilir, bu olabilir
3 olmak, bu 4 olabilir.

147
00:07:25,730 --> 00:07:26,910
Ama sürekli bir numara.

148
00:07:26,910 --> 00:07:28,400
Bu değişmez.

149
00:07:28,400 --> 00:07:31,390
>> Logaritmik zaman algoritmaları
biraz daha iyidir.

150
00:07:31,390 --> 00:07:33,950
Ve gerçekten iyi bir örnek
logaritmik zaman algoritması

151
00:07:33,950 --> 00:07:37,420
mutlaka artık görülür ettik
Telefon defterinin bölüyor

152
00:07:37,420 --> 00:07:39,480
telefon rehberinde Mike Smith'i bulmak için.

153
00:07:39,480 --> 00:07:40,980
Biz yarım sorunu kesti.

154
00:07:40,980 --> 00:07:43,580
N büyüdükçe böylece
daha büyük ve larger--

155
00:07:43,580 --> 00:07:47,290
Aslında, her zaman çift
n, sadece bir adım daha sürer.

156
00:07:47,290 --> 00:07:49,770
Bu çok daha iyi yani
daha, diyelim ki, lineer zaman.

157
00:07:49,770 --> 00:07:53,030
Eğer n çift ise Hangisi olduğunu
adımlarla çift sayısını alır.

158
00:07:53,030 --> 00:07:55,980
Eğer n üçlü varsa, onu alır
adımların sayısını üç katına.

159
00:07:55,980 --> 00:07:58,580
Birimin başına bir adım.

160
00:07:58,580 --> 00:08:01,790
>> Sonra işler biraz more-- olsun
az harika oradan.

161
00:08:01,790 --> 00:08:06,622
Bazen, lineer ritmik zaman var
Günlük doğrusal zaman denir ya sadece n log n.

162
00:08:06,622 --> 00:08:08,330
Ve biz bir örnek olacak
bir algoritma bu

163
00:08:08,330 --> 00:08:13,370
hala iyidir n günlük n içinde çalışır
daha karesel seferinde-- n karesi.

164
00:08:13,370 --> 00:08:17,320
Veya polinom zaman, n, ikidir
ikiden daha büyük bir sayı.

165
00:08:17,320 --> 00:08:20,810
Veya üstel zamanı, burada
Hatta worse-- Cı n etmektir.

166
00:08:20,810 --> 00:08:24,670
Bu yüzden bazı sabit sayı yükseldi
giriş büyüklüğü gücü.

167
00:08:24,670 --> 00:08:28,990
Yani eğer 1,000-- varsa
Veri giriş boyutu 1.000 taşımaktadır

168
00:08:28,990 --> 00:08:31,310
o 1000 iktidara C alacaktı.

169
00:08:31,310 --> 00:08:33,559
Bu polinom zaman çok daha kötü.

170
00:08:33,559 --> 00:08:35,030
>> Faktöriyel zaman daha da kötü.

171
00:08:35,030 --> 00:08:37,760
Ve aslında, gerçekten orada yapmak
Sonsuz zaman algoritmalar var,

172
00:08:37,760 --> 00:08:43,740
olan, sözde, aptal sort--
iş rastgele bir dizi shuffle için

173
00:08:43,740 --> 00:08:45,490
ve sonra görmek için kontrol
ister o tür var.

174
00:08:45,490 --> 00:08:47,589
Ve bu rastgele değilse
Yine dizi shuffle

175
00:08:47,589 --> 00:08:49,130
ve olarak sıralanmış olup olmadığını kontrol edin.

176
00:08:49,130 --> 00:08:51,671
Ve muhtemelen imagine-- edebilirsiniz
Eğer bir durum hayal edebiliyorum

177
00:08:51,671 --> 00:08:55,200
nerede kötü durumda, bu irade
Aslında dizi ile başlar asla.

178
00:08:55,200 --> 00:08:57,150
Bu algoritma sonsuza çalışır.

179
00:08:57,150 --> 00:08:59,349
Ve böylece bir olurdu
Sonsuz zaman algoritması.

180
00:08:59,349 --> 00:09:01,890
Umarım yazmaya olmayacak
Herhangi bir faktöryel ya da sonsuz bir zaman

181
00:09:01,890 --> 00:09:04,510
CS50 algoritmalar.

182
00:09:04,510 --> 00:09:09,150
>> Yani, alalım biraz daha
Bazı basit beton görünüm

183
00:09:09,150 --> 00:09:11,154
hesaplama karmaşıklığı sınıfları.

184
00:09:11,154 --> 00:09:13,070
Bu yüzden bir example-- var
ya da iki örnek burada--

185
00:09:13,070 --> 00:09:15,590
sabit zaman algoritmaları,
hangi zaman alır

186
00:09:15,590 --> 00:09:17,980
kötü durumda bir tek çalışma.

187
00:09:17,980 --> 00:09:20,050
İlk example-- Yani
Biz bir işlevi var

188
00:09:20,050 --> 00:09:23,952
Sizin için 4 adlandırılan hangi
büyüklüğü 1000 bir dizi alır.

189
00:09:23,952 --> 00:09:25,660
Ama sonra anlaşılan
Aslında görünmüyor

190
00:09:25,660 --> 00:09:29,000
bu-- gerçekten ne umursamıyor de
, bunun içinde o dizinin.

191
00:09:29,000 --> 00:09:30,820
Her zaman sadece dört döndürür.

192
00:09:30,820 --> 00:09:32,940
Yani, bu algoritma,
buna rağmen

193
00:09:32,940 --> 00:09:35,840
1000 elemanları etmez alır
Onlarla her şeyi yaparım.

194
00:09:35,840 --> 00:09:36,590
Sadece dört döndürür.

195
00:09:36,590 --> 00:09:38,240
Her zaman tek bir adımdır.

196
00:09:38,240 --> 00:09:41,600
>> Aslında, 2 nums-- katan
biz Eee-- önce gördüm

197
00:09:41,600 --> 00:09:43,680
Sadece iki tamsayı işler.

198
00:09:43,680 --> 00:09:44,692
Tek bir adım değil.

199
00:09:44,692 --> 00:09:45,900
Aslında bir kaç adım var.

200
00:09:45,900 --> 00:09:50,780
Sen olsun, sen b olsun, bunları eklemek
Birlikte ve çıkış sonuçlar.

201
00:09:50,780 --> 00:09:53,270
Yani 84 adımları var.

202
00:09:53,270 --> 00:09:55,510
Ancak bu her zaman sabittir
ne olursa olsun, bir veya b.

203
00:09:55,510 --> 00:09:59,240
Bir almak zorunda, b, olsun, eklemek
Birlikte onları çıkış sonucu.

204
00:09:59,240 --> 00:10:02,900
Yani sabit bir zaman algoritma var.

205
00:10:02,900 --> 00:10:05,170
>> İşte bir örnek
Doğrusal zaman algorithm--

206
00:10:05,170 --> 00:10:08,740
bu alan gets-- bir algoritma
Bir ilave aşama, muhtemelen,

207
00:10:08,740 --> 00:10:10,740
senin girişi 1 ile büyüdükçe.

208
00:10:10,740 --> 00:10:14,190
Yani, biz arıyoruz diyelim
Bir dizinin sayısı 5 iç.

209
00:10:14,190 --> 00:10:16,774
Bir durum nerede olabilir
Eğer oldukça erken bulabilirsiniz.

210
00:10:16,774 --> 00:10:18,606
Ama aynı zamanda olabilir
Bir durum nerede

211
00:10:18,606 --> 00:10:20,450
dizinin son elemanı olabilir.

212
00:10:20,450 --> 00:10:23,780
Büyüklüğü 5 bir dizi, eğer içinde
Biz numara 5 arıyoruz.

213
00:10:23,780 --> 00:10:25,930
Bu 5 adım alacaktı.

214
00:10:25,930 --> 00:10:29,180
Ve aslında, var olduğunu hayal
Bu dizide değil 5 her yerde.

215
00:10:29,180 --> 00:10:32,820
Biz hala aslında bakmak zorunda
Dizinin her elemanı

216
00:10:32,820 --> 00:10:35,550
belirlemek amacıyla
olsun ya da 5 vardır.

217
00:10:35,550 --> 00:10:39,840
>> Böylece en kötü-durumunda,
eleman dizideki son olduğunu

218
00:10:39,840 --> 00:10:41,700
ya da hiç yok.

219
00:10:41,700 --> 00:10:44,690
Biz hala bakmak zorunda
n bütün elemanları.

220
00:10:44,690 --> 00:10:47,120
Ve böylece bu algoritma
Doğrusal zamanla çalışır.

221
00:10:47,120 --> 00:10:50,340
Sen tarafından teyit edebilirsiniz
diyerek biraz extrapolating,

222
00:10:50,340 --> 00:10:53,080
Biz 6-element dizi olsaydı ve
Biz numara 5 için aradılar

223
00:10:53,080 --> 00:10:54,890
o 6 adımları sürebilir.

224
00:10:54,890 --> 00:10:57,620
Biz 7 elemanlı dizi varsa ve
Biz numara 5 arıyoruz.

225
00:10:57,620 --> 00:10:59,160
Bu 7 adımlar olabilir.

226
00:10:59,160 --> 00:11:02,920
Biz bir daha eleman eklemek gibi bizim
Dizi, bir daha adım attı.

227
00:11:02,920 --> 00:11:06,750
Bu doğrusal bir algoritma var
kötü durumda.

228
00:11:06,750 --> 00:11:08,270
>> Çift sizin için hızlı soru.

229
00:11:08,270 --> 00:11:11,170
Ne runtime-- neler var
en kötü durum zamanı

230
00:11:11,170 --> 00:11:13,700
Bu kod belirli snippet'in?

231
00:11:13,700 --> 00:11:17,420
Yani çalışan Burada 4 döngü var
j 0, m'ye kadar tüm yol eşittir dan.

232
00:11:17,420 --> 00:11:21,980
Ve ben burada görüyorum olduğunu
döngünün gövdesi sabit zamanda çalışır.

233
00:11:21,980 --> 00:11:24,730
Yani terminoloji bu kullanarak
biz zaten ne hakkında konuştuk ettik

234
00:11:24,730 --> 00:11:29,390
En kötü durumda olurdu
Bu algoritmanın çalışma zamanı?

235
00:11:29,390 --> 00:11:31,050
Bir saniye sürer.

236
00:11:31,050 --> 00:11:34,270
Döngüsünün iç kısmında
sabit zamanda çalışır.

237
00:11:34,270 --> 00:11:37,510
Ve dış kısmı
loop m kez çalıştırmak için gidiyor.

238
00:11:37,510 --> 00:11:40,260
Yani en kötü durum çalışma zamanı burada ne var?

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

240
00:11:43,210 --> 00:11:44,686
Sen haklı olurdunuz.

241
00:11:44,686 --> 00:11:46,230
>> Nasıl başka bir dersin?

242
00:11:46,230 --> 00:11:48,590
Biz var bu kez
Bir döngü içinde döngü.

243
00:11:48,590 --> 00:11:50,905
Biz bir dış döngü var
Bu sıfırdan p çalışır.

244
00:11:50,905 --> 00:11:54,630
Ve biz çalışan bir iç döngü var
sıfırdan p ve bunun içinde

245
00:11:54,630 --> 00:11:57,890
Ben devlet vücut o
loop sabit zamanda çalışır.

246
00:11:57,890 --> 00:12:02,330
Yani en kötü durum zamanı ne
Bu kod belirli snippet'in?

247
00:12:02,330 --> 00:12:06,140
Peki, yine, biz bir var
p kez çalışır dış döngü.

248
00:12:06,140 --> 00:12:09,660
Ve her defasında bir yineleme
Bu döngü, daha çok.

249
00:12:09,660 --> 00:12:13,170
Biz bir iç döngü var
bu da p kez çalışır.

250
00:12:13,170 --> 00:12:16,900
Bunun içinde Ve sonra, orada
Orada sürekli seferinde-- küçük pasajı.

251
00:12:16,900 --> 00:12:19,890
>> Biz bir dış döngü varsa Böylece
hangi bir iç p kez çalışır

252
00:12:19,890 --> 00:12:22,880
Bir iç döngü bu
ne times-- p çalışır

253
00:12:22,880 --> 00:12:26,480
en kötü durum zamanı
Bu kod parçacığını?

254
00:12:26,480 --> 00:12:30,730
Eğer p büyük-O karesi tahmin mı?

255
00:12:30,730 --> 00:12:31,690
>> Ben Doug Lloyd değilim.

256
00:12:31,690 --> 00:12:33,880
Bu CS50 olduğunu.

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