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

2
00:00:05,830 --> 00:00:07,910
>> W porządku, więc, złożoność obliczeniowa.

3
00:00:07,910 --> 00:00:10,430
Wystarczy trochę ostrzeżenia
Zanim zabierzesz się za far--

4
00:00:10,430 --> 00:00:13,070
Prawdopodobnie będzie to m.in.
rzeczy najbardziej matematyczne ciężki

5
00:00:13,070 --> 00:00:14,200
mówimy w CS50.

6
00:00:14,200 --> 00:00:16,950
Mam nadzieję, że nie będzie to zbyt przytłaczające
a my postaramy i Cię

7
00:00:16,950 --> 00:00:19,200
w procesie, ale
tylko trochę uczciwego ostrzeżenia.

8
00:00:19,200 --> 00:00:21,282
Jest trochę
matematyki zaangażowanych tutaj.

9
00:00:21,282 --> 00:00:23,990
W porządku, więc w celu dokonania
Korzystanie z naszych zasobów obliczeniowych

10
00:00:23,990 --> 00:00:28,170
w prawdziwym world-- to naprawdę
ważne, aby zrozumieć algorytmy

11
00:00:28,170 --> 00:00:30,750
i jak przetwarzać dane.

12
00:00:30,750 --> 00:00:32,810
Jeśli mamy naprawdę
efektywny algorytm, mamy

13
00:00:32,810 --> 00:00:36,292
Można zmniejszyć ilość zasobów
mamy do dyspozycji, aby sobie z tym poradzić.

14
00:00:36,292 --> 00:00:38,750
Jeśli mamy algorytm, który
zajmie dużo pracy

15
00:00:38,750 --> 00:00:41,210
przetwarzać naprawdę
duży zestaw danych, to

16
00:00:41,210 --> 00:00:44,030
będzie wymagać więcej
i więcej zasobów, które

17
00:00:44,030 --> 00:00:47,980
to pieniądze, pamięci RAM, wszystkie tego rodzaju rzeczy.

18
00:00:47,980 --> 00:00:52,090
>> Tak, jest w stanie przeanalizować
Algorytm za pomocą tego zestaw narzędzi,

19
00:00:52,090 --> 00:00:56,110
w zasadzie, prosi question--
w jaki sposób ten skalę algorytmu

20
00:00:56,110 --> 00:00:59,020
jak rzucić więcej i więcej danych na nim?

21
00:00:59,020 --> 00:01:02,220
W CS50, ilość danych jesteśmy
pracy z jest dość mały.

22
00:01:02,220 --> 00:01:05,140
Ogólnie rzecz biorąc, nasze programy będą
uruchomić w drugim lub less--

23
00:01:05,140 --> 00:01:07,830
prawdopodobnie o wiele mniej
zwłaszcza na początku.

24
00:01:07,830 --> 00:01:12,250
>> Ale pomyśl o firmą, która zajmuje
z setkami milionów klientów.

25
00:01:12,250 --> 00:01:14,970
I muszą przetwarzać
że dane klienta.

26
00:01:14,970 --> 00:01:18,260
W miarę wzrostu liczby użytkowników, że
mają coraz większe,

27
00:01:18,260 --> 00:01:21,230
to będzie wymagało
coraz więcej zasobów.

28
00:01:21,230 --> 00:01:22,926
Jak wiele innych zasobów?

29
00:01:22,926 --> 00:01:25,050
Cóż, to zależy od tego jak
analizujemy algorytmu,

30
00:01:25,050 --> 00:01:28,097
za pomocą narzędzi w przyborniku.

31
00:01:28,097 --> 00:01:31,180
Kiedy mówimy o złożoności
algorithm-- które czasem będziesz

32
00:01:31,180 --> 00:01:34,040
usłyszeć to dalej czas
Złożoność lub miejsca Złożoność

33
00:01:34,040 --> 00:01:36,190
ale my po prostu się
zadzwonić complexity--

34
00:01:36,190 --> 00:01:38,770
jesteśmy ogólnie mówić o
scenariusz pesymistyczny.

35
00:01:38,770 --> 00:01:42,640
Biorąc pod uwagę najgorszego stos
Dane że możemy być rzucając na niego,

36
00:01:42,640 --> 00:01:46,440
jak to jest algorytm będzie
przetwarzać lub radzić sobie z tymi danymi?

37
00:01:46,440 --> 00:01:51,450
Zazwyczaj zadzwonić Najgorszy
czas pracy algorytmu big-O.

38
00:01:51,450 --> 00:01:56,770
Więc algorytm można powiedzieć, aby
uruchomić w O. N lub O n do kwadratu.

39
00:01:56,770 --> 00:01:59,110
I o tym, co
te myśli w drugim.

40
00:01:59,110 --> 00:02:01,620
>> Czasem jednak, robimy opieki
o najlepszym wypadku.

41
00:02:01,620 --> 00:02:05,400
Jeśli dane jest wszystko, co chcieliśmy
że jest i to było absolutnie doskonałe

42
00:02:05,400 --> 00:02:09,630
i byliśmy wysłanie tego idealne
zestaw danych za pośrednictwem naszego algorytmu.

43
00:02:09,630 --> 00:02:11,470
Jak radzi sobie w tej sytuacji?

44
00:02:11,470 --> 00:02:15,050
Czasami odnosi się do tego, jak
big-Omega, więc w przeciwieństwie do big-O,

45
00:02:15,050 --> 00:02:16,530
mamy big-Omega.

46
00:02:16,530 --> 00:02:18,880
Big-Omega w najlepszym wypadku.

47
00:02:18,880 --> 00:02:21,319
Big-O w najgorszym scenariuszu.

48
00:02:21,319 --> 00:02:23,860
Ogólnie, gdy mówimy o
złożoność algorytmu,

49
00:02:23,860 --> 00:02:26,370
mówimy o
Najgorszy scenariusz.

50
00:02:26,370 --> 00:02:28,100
Miejcie to na uwadze.

51
00:02:28,100 --> 00:02:31,510
>> I w tej klasie, mamy na ogół dzieje
opuścić rygorystyczną analizę bok.

52
00:02:31,510 --> 00:02:35,350
Istnieje nauki i pola
poświęcony tego rodzaju rzeczy.

53
00:02:35,350 --> 00:02:37,610
Kiedy mówimy o rozumowaniu
przez algorytmy,

54
00:02:37,610 --> 00:02:41,822
które zrobimy kawał-po-sztuki dla wielu
Algorytmy mówimy w klasie.

55
00:02:41,822 --> 00:02:44,780
Jesteśmy naprawdę tylko o
rozumowanie przez niego ze zdrowym rozsądkiem,

56
00:02:44,780 --> 00:02:47,070
nie z wzorami lub dowodów,
lub coś podobnego.

57
00:02:47,070 --> 00:02:51,600
Więc nie martw się, nie będziemy
zamienia się w wielki lekcji matematyki.

58
00:02:51,600 --> 00:02:55,920
>> Powiedziałem więc dbamy o złożoności
dlatego, że zadaje pytanie, w jaki sposób

59
00:02:55,920 --> 00:03:00,160
Czy nasze algorytmy obsłużyć większe i
Większe zestawy danych są wyrzucane na nich.

60
00:03:00,160 --> 00:03:01,960
Cóż, to, co jest zestaw danych?

61
00:03:01,960 --> 00:03:03,910
Co mam na myśli, kiedy powiedział, że?

62
00:03:03,910 --> 00:03:07,600
Oznacza to, co sprawia, że ​​większość
sensu kontekście, aby być uczciwym.

63
00:03:07,600 --> 00:03:11,160
Jeśli mamy algorytm, na
Procesy Strings-- jesteśmy prawdopodobnie

64
00:03:11,160 --> 00:03:13,440
mówi o wielkości napisu.

65
00:03:13,440 --> 00:03:15,190
To dane set--
wielkość, liczba

66
00:03:15,190 --> 00:03:17,050
znaków, które tworzą łańcuch.

67
00:03:17,050 --> 00:03:20,090
Jeśli mówimy o
Algorytm, który przetwarza pliki,

68
00:03:20,090 --> 00:03:23,930
możemy mówić o tym, jak
wiele kilobajtów zawierają ten plik.

69
00:03:23,930 --> 00:03:25,710
I to jest zbiór danych.

70
00:03:25,710 --> 00:03:28,870
Jeśli mówimy o algorytmie
który obsługuje macierze bardziej ogólnie,

71
00:03:28,870 --> 00:03:31,510
takie jak algorytmy sortowania
lub wyszukiwanie algorytmów,

72
00:03:31,510 --> 00:03:36,690
jesteśmy chyba mówić o liczbie
Elementy, które zawierają tablicę.

73
00:03:36,690 --> 00:03:39,272
>> Teraz możemy zmierzyć
algorithm-- w szczególności

74
00:03:39,272 --> 00:03:40,980
kiedy mówię, możemy
pomiaru algorytm, ja

75
00:03:40,980 --> 00:03:43,840
oznacza, że ​​możemy zmierzyć jak
wiele zasobów zajmuje.

76
00:03:43,840 --> 00:03:48,990
Czy te zasoby są, jak wiele
bajtów RAM-- lub megabajtów pamięci RAM

77
00:03:48,990 --> 00:03:49,790
używa.

78
00:03:49,790 --> 00:03:52,320
Albo ile czasu potrzeba, aby uruchomić.

79
00:03:52,320 --> 00:03:56,200
I możemy nazwać
pomiaru, arbitralnie, f n.

80
00:03:56,200 --> 00:03:59,420
Gdzie n oznacza liczbę
elementy zestawu danych.

81
00:03:59,420 --> 00:04:02,640
F n jest to, jak wiele latków.

82
00:04:02,640 --> 00:04:07,530
Ile jednostek zasobów robi
wymagać, aby przetwarzać te dane.

83
00:04:07,530 --> 00:04:10,030
>> Teraz, tak naprawdę to nie obchodzi
o tym, co f n jest dokładnie.

84
00:04:10,030 --> 00:04:13,700
W rzeczywistości bardzo rzadko will--
Z pewnością nigdy nie będzie w tym class-- I

85
00:04:13,700 --> 00:04:18,709
nurkować w dowolnym naprawdę głębokie
analiza tego, co f n.

86
00:04:18,709 --> 00:04:23,510
My tylko będziemy rozmawiać o tym, co f
n jest w przybliżeniu lub co ma tendencję do.

87
00:04:23,510 --> 00:04:27,600
Tendencja algorytmu jest
podyktowane najwyższym terminu zamówienia.

88
00:04:27,600 --> 00:04:29,440
I widzimy, co ja
myśli, że biorąc

89
00:04:29,440 --> 00:04:31,910
Spojrzenie na bardziej konkretny przykład.

90
00:04:31,910 --> 00:04:34,620
>> Więc powiedzmy, że mamy
trzy różne algorytmy.

91
00:04:34,620 --> 00:04:39,350
Z których pierwszy ma n
pokrojone w kostkę, niektóre jednostki zasobów

92
00:04:39,350 --> 00:04:42,880
do przetwarzania zbioru danych o rozmiarze n.

93
00:04:42,880 --> 00:04:47,000
Mamy drugiego algorytmu, który
n kostkę oraz n kwadratu zasobów

94
00:04:47,000 --> 00:04:49,350
do przetwarzania zbioru danych o rozmiarze n.

95
00:04:49,350 --> 00:04:52,030
I mamy trzeci
algorytm, który działa in--, że

96
00:04:52,030 --> 00:04:58,300
zajmuje n kostkę minus 8n kwadratu
plus 20 n jednostek zasobów

97
00:04:58,300 --> 00:05:02,370
do przetwarzania algorytmu
z danymi zawartymi w rozmiarze n.

98
00:05:02,370 --> 00:05:05,594
>> Teraz znowu, tak naprawdę nie będzie
dostać się do tego poziomu szczegółowości.

99
00:05:05,594 --> 00:05:08,260
Jestem naprawdę po prostu to się
tutaj jako ilustracja punktu

100
00:05:08,260 --> 00:05:10,176
że będę
co na sekundę, co

101
00:05:10,176 --> 00:05:12,980
jest to, że tylko naprawdę obchodzi
o tendencji rzeczy

102
00:05:12,980 --> 00:05:14,870
jako zbiory danych stają się coraz większe.

103
00:05:14,870 --> 00:05:18,220
Więc jeśli zestaw danych jest niewielka, nie ma
rzeczywiście dość duża różnica

104
00:05:18,220 --> 00:05:19,870
W tych algorytmów.

105
00:05:19,870 --> 00:05:23,000
Trzeci algorytm istnieje
trwa 13 razy dłużej,

106
00:05:23,000 --> 00:05:27,980
13 razy ilość zasobów
uruchomić w stosunku do pierwszego.

107
00:05:27,980 --> 00:05:31,659
>> Jeśli nasz zestaw danych jest rozmiar 10, które
jest większa, ale niekoniecznie duże,

108
00:05:31,659 --> 00:05:33,950
widzimy, że istnieje
faktycznie trochę różnicy.

109
00:05:33,950 --> 00:05:36,620
W trzecim algorytmem
staje się bardziej efektywny.

110
00:05:36,620 --> 00:05:40,120
Chodzi o to faktycznie 40% -
lub 60% bardziej wydajne.

111
00:05:40,120 --> 00:05:41,580
To zajmuje 40% ilości czasu.

112
00:05:41,580 --> 00:05:45,250
To może run-- może potrwać
400 jednostek zasobów

113
00:05:45,250 --> 00:05:47,570
do przetwarzania zbioru danych o wielkości 10.

114
00:05:47,570 --> 00:05:49,410
Podczas gdy pierwsza
Algorytm, przeciwnie,

115
00:05:49,410 --> 00:05:54,520
zajmuje 1000 jednostek zasobów
do przetwarzania zbioru danych o wielkości 10.

116
00:05:54,520 --> 00:05:57,240
Ale zobacz, co się stanie, jak
nasza liczba się jeszcze większe.

117
00:05:57,240 --> 00:05:59,500
>> Teraz różnica
od tych algorytmów

118
00:05:59,500 --> 00:06:01,420
zaczynają się trochę mniej widoczne.

119
00:06:01,420 --> 00:06:04,560
A fakt, że istnieją
niższego rzędu terms-- czy raczej,

120
00:06:04,560 --> 00:06:09,390
Terminy o niższym exponents--
zaczynają się nieistotne.

121
00:06:09,390 --> 00:06:12,290
Jeśli zestaw danych jest wielkości
1000 i pierwszy algorytm

122
00:06:12,290 --> 00:06:14,170
przebiega w ciągu miliardów stopni.

123
00:06:14,170 --> 00:06:17,880
A drugi algorytm działa w
miliard i milion kroki.

124
00:06:17,880 --> 00:06:20,870
I trzeci algorytm działa
w po prostu nieśmiały miliard kroków.

125
00:06:20,870 --> 00:06:22,620
To prawie miliard kroków.

126
00:06:22,620 --> 00:06:25,640
Warunki te niższego rzędu zacząć
aby stać się naprawdę bez znaczenia.

127
00:06:25,640 --> 00:06:27,390
I tak naprawdę
Młot do domu point--

128
00:06:27,390 --> 00:06:31,240
jeśli dane wejściowe jest Rozmiar A
million-- wszystkie trzy z nich dość dużo

129
00:06:31,240 --> 00:06:34,960
przyjmować jedną quintillion-- jeśli
moja matematyka jest correct-- kroki

130
00:06:34,960 --> 00:06:37,260
przetwarzać dane wejściowe
wielkości miliona.

131
00:06:37,260 --> 00:06:38,250
To jest dużo schodów.

132
00:06:38,250 --> 00:06:42,092
A fakt, że jeden z nich może
potrwać kilka 100,000 lub kilka 100

133
00:06:42,092 --> 00:06:44,650
jeszcze mniej, gdy mln
mówimy o wielu

134
00:06:44,650 --> 00:06:46,990
że big-- to trochę bez znaczenia.

135
00:06:46,990 --> 00:06:50,006
Wszystkie one mają tendencję do
około n pokrojone w kostkę,

136
00:06:50,006 --> 00:06:52,380
i tak byśmy rzeczywiście odnoszą
wszystkich tych algorytmów

137
00:06:52,380 --> 00:06:59,520
jako na zlecenie n
pokrojone w kostkę lub w big-O n sześcienny.

138
00:06:59,520 --> 00:07:03,220
>> Oto lista niektórych z bardziej
Wspólne zajęcia złożoność obliczeniowa

139
00:07:03,220 --> 00:07:05,820
że uda nam się spotkać w
algorytmy, na ogół.

140
00:07:05,820 --> 00:07:07,970
A także w szczególności w CS50.

141
00:07:07,970 --> 00:07:11,410
Są one uporządkowane od
ogólnie najszybciej w górze

142
00:07:11,410 --> 00:07:13,940
ogólnie najwolniej na dole.

143
00:07:13,940 --> 00:07:16,920
Tak więc algorytmy stałym czasie tendencję
być najszybszy, bez względu

144
00:07:16,920 --> 00:07:19,110
wielkości z
wprowadzanie danych można przejść w.

145
00:07:19,110 --> 00:07:23,760
Oni zawsze mają jedną operację lub
jedna jednostka zasobów do czynienia.

146
00:07:23,760 --> 00:07:25,730
To może być 2, to może
za 3, może to być 4.

147
00:07:25,730 --> 00:07:26,910
Ale to stała liczba.

148
00:07:26,910 --> 00:07:28,400
Nie ulega zmianie.

149
00:07:28,400 --> 00:07:31,390
>> Algorytmy logarytmiczne czas
są nieco lepsze.

150
00:07:31,390 --> 00:07:33,950
I naprawdę dobry przykład
algorytm czasu logarytmiczna

151
00:07:33,950 --> 00:07:37,420
z pewnością widział pan już jest
rozdzieranie książki telefonicznej

152
00:07:37,420 --> 00:07:39,480
znaleźć Mike Smith w książce telefonicznej.

153
00:07:39,480 --> 00:07:40,980
Tniemy problem w połowie.

154
00:07:40,980 --> 00:07:43,580
I tak jak n staje się większy
oraz większe i larger--

155
00:07:43,580 --> 00:07:47,290
w rzeczywistości, za każdym razem dwukrotnie
n, to zajmuje tylko jeden krok.

156
00:07:47,290 --> 00:07:49,770
Więc to jest o wiele lepiej
niż, powiedzmy, czas liniowy.

157
00:07:49,770 --> 00:07:53,030
Który jest, jeśli podwoi n, to
ma podwójną liczbę kroków.

158
00:07:53,030 --> 00:07:55,980
Jeśli trzykrotnie n, trwa
potroić liczbę kroków.

159
00:07:55,980 --> 00:07:58,580
Jeden krok za sztukę.

160
00:07:58,580 --> 00:08:01,790
>> Potem robi się trochę more--
trochę mniej wielkie stamtąd.

161
00:08:01,790 --> 00:08:06,622
Masz czas liniowy rytmiczne, czasem
zwany dziennik czas liniowy lub po prostu n log n.

162
00:08:06,622 --> 00:08:08,330
A my przykładem
o algorytm

163
00:08:08,330 --> 00:08:13,370
przebiega w n log n, która jest jeszcze lepiej
niż kwadratowa time-- n do kwadratu.

164
00:08:13,370 --> 00:08:17,320
Albo wielomian czasu, n dwa
każda liczba większa od dwóch.

165
00:08:17,320 --> 00:08:20,810
Albo wykładnicza czasu, który
Jeszcze worse-- C do n.

166
00:08:20,810 --> 00:08:24,670
Tak więc niektóre stała liczba podniesiona do
moc wielkości wejściowych.

167
00:08:24,670 --> 00:08:28,990
Tak więc jeśli jest 1,000-- jeśli
Wprowadzanie danych jest wielkości 1000,

168
00:08:28,990 --> 00:08:31,310
zajęłoby C do 1,000th władzy.

169
00:08:31,310 --> 00:08:33,559
To dużo gorsze niż czasie wielomianowym.

170
00:08:33,559 --> 00:08:35,030
>> Silnia czas jest jeszcze gorzej.

171
00:08:35,030 --> 00:08:37,760
A w rzeczywistości, tak naprawdę nie
istnieje nieskończona algorytmy czasowe,

172
00:08:37,760 --> 00:08:43,740
takie jak, tak zwane głupie sort-- którego
zadaniem jest losowo przetasować tablicę

173
00:08:43,740 --> 00:08:45,490
a następnie sprawdzić,
czy to klasyfikowane.

174
00:08:45,490 --> 00:08:47,589
A jeśli nie, losowo
ponownie shuffle tablicę

175
00:08:47,589 --> 00:08:49,130
i sprawdzić, czy to jest klasyfikowane.

176
00:08:49,130 --> 00:08:51,671
I jak można prawdopodobnie imagine--
można wyobrazić sobie sytuację,

177
00:08:51,671 --> 00:08:55,200
gdzie w najgorszym przypadku, że wola
nigdy nie zaczynają się od tablicy.

178
00:08:55,200 --> 00:08:57,150
Że algorytm będzie działać wiecznie.

179
00:08:57,150 --> 00:08:59,349
I tak, byłoby
Algorytm nieskończony czas.

180
00:08:59,349 --> 00:09:01,890
Mam nadzieję, że nie będzie można pisać
dowolny silnia lub nieskończony czas

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

182
00:09:04,510 --> 00:09:09,150
>> Więc weźmy trochę więcej
betonu spojrzenie na niektóre prostsze

183
00:09:09,150 --> 00:09:11,154
obliczeniowe klasy złożoności.

184
00:09:11,154 --> 00:09:13,070
Mamy więc example--
lub dwa przykłady here--

185
00:09:13,070 --> 00:09:15,590
stałych algorytmów czasowych,
które zawsze

186
00:09:15,590 --> 00:09:17,980
jednej operacji w najgorszym przypadku.

187
00:09:17,980 --> 00:09:20,050
Tak więc pierwszym example--
mamy funkcję

188
00:09:20,050 --> 00:09:23,952
nazywa 4 dla Ciebie, które
ma tablicę wielkości 1,000.

189
00:09:23,952 --> 00:09:25,660
Ale najwidoczniej
faktycznie nie wyglądają

190
00:09:25,660 --> 00:09:29,000
w it-- naprawdę nie obchodzi mnie, co jest
wewnątrz niego, z tej tablicy.

191
00:09:29,000 --> 00:09:30,820
Zawsze po prostu zwraca cztery.

192
00:09:30,820 --> 00:09:32,940
Tak, że algorytm,
Pomimo faktu, że

193
00:09:32,940 --> 00:09:35,840
zajmuje 1000 elementów nie
zrobić coś z nimi.

194
00:09:35,840 --> 00:09:36,590
Po prostu zwraca cztery.

195
00:09:36,590 --> 00:09:38,240
To jest zawsze jeden krok.

196
00:09:38,240 --> 00:09:41,600
>> W rzeczywistości, dodać 2 nums-- które
widzieliśmy wcześniej jako well--

197
00:09:41,600 --> 00:09:43,680
tylko przetwarza dwie liczby całkowite.

198
00:09:43,680 --> 00:09:44,692
To nie jest jeden krok.

199
00:09:44,692 --> 00:09:45,900
Jest to tak naprawdę kilka kroków.

200
00:09:45,900 --> 00:09:50,780
Dostaniesz, masz b, można je dodać
razem i jest drukowanie wyników.

201
00:09:50,780 --> 00:09:53,270
Więc to jest 84 kroków.

202
00:09:53,270 --> 00:09:55,510
Ale to jest zawsze stała,
niezależnie od A lub B.

203
00:09:55,510 --> 00:09:59,240
Musisz dostać, dostać b, dodać
je ze sobą, wyjście wynik.

204
00:09:59,240 --> 00:10:02,900
Więc to jest algorytm stała czasu.

205
00:10:02,900 --> 00:10:05,170
>> Oto przykład
liniowa algorithm-- czas

206
00:10:05,170 --> 00:10:08,740
algorytm, który gets--, że trwa
jeden dodatkowy krok, ewentualnie

207
00:10:08,740 --> 00:10:10,740
jako twój wkład rośnie o 1.

208
00:10:10,740 --> 00:10:14,190
Więc powiedzmy, że szukamy
numer 5 w środku tablicy.

209
00:10:14,190 --> 00:10:16,774
Możesz mieć sytuację, w której
może okazać się dość wcześnie.

210
00:10:16,774 --> 00:10:18,606
Ale może mieć również
sytuacja, w której to

211
00:10:18,606 --> 00:10:20,450
może być ostatnim elementem tablicy.

212
00:10:20,450 --> 00:10:23,780
W tablicy 5, jeżeli rozmiar
szukamy liczby 5.

213
00:10:23,780 --> 00:10:25,930
Zajmie to 5 kroków.

214
00:10:25,930 --> 00:10:29,180
A w rzeczywistości, wyobraź sobie, że nie ma
nie 5 gdziekolwiek w tej tablicy.

215
00:10:29,180 --> 00:10:32,820
Nadal właściwie spojrzeć na
każdy element tablicy

216
00:10:32,820 --> 00:10:35,550
W celu określenia
czy 5 jest tam.

217
00:10:35,550 --> 00:10:39,840
>> Tak więc w najgorszym przypadku, który jest, że
element jest ostatnia w tablicy

218
00:10:39,840 --> 00:10:41,700
lub nie istnieje w ogóle.

219
00:10:41,700 --> 00:10:44,690
Mamy jeszcze spojrzeć na
wszystkie z n elementów.

220
00:10:44,690 --> 00:10:47,120
I tak ten algorytm
działa w czasie liniowym.

221
00:10:47,120 --> 00:10:50,340
Możesz potwierdzić, że
ekstrapolacji trochę, mówiąc:

222
00:10:50,340 --> 00:10:53,080
gdybyśmy mieli tablicę 6-elementów i
szukaliśmy numerem 5,

223
00:10:53,080 --> 00:10:54,890
może to potrwać 6 kroków.

224
00:10:54,890 --> 00:10:57,620
Jeśli mamy tablicę 7-elementów i
szukamy liczby 5.

225
00:10:57,620 --> 00:10:59,160
To może potrwać 7 kroków.

226
00:10:59,160 --> 00:11:02,920
Jak dodać jeden element do naszego
tablica, to ma jeszcze jeden krok.

227
00:11:02,920 --> 00:11:06,750
To algorytm liniowy
w najgorszym przypadku.

228
00:11:06,750 --> 00:11:08,270
>> Kilka szybkich pytań do Ciebie.

229
00:11:08,270 --> 00:11:11,170
Co się runtime-- co
Najgorszy czas pracy

230
00:11:11,170 --> 00:11:13,700
tego konkretnego fragmentu kodu?

231
00:11:13,700 --> 00:11:17,420
Więc mam 4 pętlę tutaj, który działa
z j jest równa 0, aż do góry do m.

232
00:11:17,420 --> 00:11:21,980
I co tu widzę, jest to, że
Ciało pętli działa w stałym czasie.

233
00:11:21,980 --> 00:11:24,730
Tak więc używając terminologii
mamy już rozmawialiśmy about-- co

234
00:11:24,730 --> 00:11:29,390
byłby najgorszy
czas pracy tego algorytmu?

235
00:11:29,390 --> 00:11:31,050
Weź drugi.

236
00:11:31,050 --> 00:11:34,270
Wewnętrzna część pętli
działa w stałym czasie.

237
00:11:34,270 --> 00:11:37,510
I zewnętrzną częścią
Pętla ma zamiar uruchomić razy m.

238
00:11:37,510 --> 00:11:40,260
Więc co jest najgorszy czas pracy tutaj?

239
00:11:40,260 --> 00:11:43,210
Czy domyślasz big-O w m?

240
00:11:43,210 --> 00:11:44,686
Byłbyś w prawo.

241
00:11:44,686 --> 00:11:46,230
>> Jak o innym?

242
00:11:46,230 --> 00:11:48,590
Tym razem mamy
pętli wewnątrz pętli.

243
00:11:48,590 --> 00:11:50,905
Mamy zewnętrzną pętlę
który działa od zera do p.

244
00:11:50,905 --> 00:11:54,630
I mamy wewnętrzną pętlę, która działa
od zera do P, jak i wewnątrz, że

245
00:11:54,630 --> 00:11:57,890
Oświadczam, że ciało
Pętla działa w stałym czasie.

246
00:11:57,890 --> 00:12:02,330
Więc co jest najgorszy czas pracy
tego konkretnego fragmentu kodu?

247
00:12:02,330 --> 00:12:06,140
Cóż, znowu mamy
Zewnętrzna pętla, która prowadzi razy p.

248
00:12:06,140 --> 00:12:09,660
I każdy time-- iteracji
z tej pętli, a.

249
00:12:09,660 --> 00:12:13,170
Mamy wewnętrzną pętlę
które również prowadzi razy p.

250
00:12:13,170 --> 00:12:16,900
A następnie wewnątrz, że nie jest
stała time-- mały urywek tam.

251
00:12:16,900 --> 00:12:19,890
>> Więc jeśli mamy zewnętrzna pętla
prowadzi razy p wnętrze, które jest

252
00:12:19,890 --> 00:12:22,880
wewnętrzna pętla
prowadzi p times-- to, co jest

253
00:12:22,880 --> 00:12:26,480
Najgorszy czas pracy
tego fragmentu kodu?

254
00:12:26,480 --> 00:12:30,730
Czy domyślasz big-O p do kwadratu?

255
00:12:30,730 --> 00:12:31,690
>> Jestem Doug Lloyd.

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

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