1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Prawdopodobnie słyszeliście ludzie mówią o algorytmu szybkiego lub wydajny

2
00:00:10,950 --> 00:00:13,090
za wykonanie swoją szczególną zadanie,

3
00:00:13,090 --> 00:00:16,110
Ale co to dokładnie zgadza się z to oznaczać, dla algorytmu, aby być szybko lub wydajny?

4
00:00:16,110 --> 00:00:18,580
Cóż, to nie mówi o pomiaru w czasie rzeczywistym,

5
00:00:18,580 --> 00:00:20,500
jak sekundy lub minuty.

6
00:00:20,500 --> 00:00:22,220
Jest to, ponieważ sprzęt komputerowy

7
00:00:22,220 --> 00:00:24,260
i oprogramowanie różnią się w zależności drastycznie.

8
00:00:24,260 --> 00:00:26,020
Mój program może działać wolniej niż twój,

9
00:00:26,020 --> 00:00:28,000
, bo jestem uruchomienie go na starszym komputerze,

10
00:00:28,000 --> 00:00:30,110
lub dlatego, I się zdarzyć, które mają być grając w w trybie online grę wideo

11
00:00:30,110 --> 00:00:32,670
w tym samym czasie,, które jest wyginanie całości mojej pamięci,

12
00:00:32,670 --> 00:00:35,400
lub też mogłoby I być uruchomiony mój program za pośrednictwem różnego oprogramowania

13
00:00:35,400 --> 00:00:37,550
, które komunikuje się z na maszyny w różny sposób się na niskim poziomie.

14
00:00:37,550 --> 00:00:39,650
To jest jak porównując jabłek i pomarańczy.

15
00:00:39,650 --> 00:00:41,940
Po prostu, ponieważ mój wolniejsze komputer trwa dłużej,

16
00:00:41,940 --> 00:00:43,410
niż twoje, aby dać z powrotem odpowiedź,

17
00:00:43,410 --> 00:00:45,510
, nie oznacza, Państwo mają do bardziej wydajnej algorytmu.

18
00:00:45,510 --> 00:00:48,830
>> Tak więc, skoro nie możemy bezpośrednio porównać ich czasy autonomii programów

19
00:00:48,830 --> 00:00:50,140
w sekundach lub minuta,

20
00:00:50,140 --> 00:00:52,310
jak mamy porównaj 2 różne algorytmy,

21
00:00:52,310 --> 00:00:55,030
niezależnie od ich sprzętu lub środowiska oprogramowania?

22
00:00:55,030 --> 00:00:58,000
Aby utworzyć bardziej jednolitego sposób mierzenia algorytmiczny efektywność,

23
00:00:58,000 --> 00:01:00,360
naukowcy komputerowe i matematycy, pozwoliły opracować

24
00:01:00,360 --> 00:01:03,830
koncepcje do pomiaru asymptotyczną złożoność z w programu

25
00:01:03,830 --> 00:01:06,110
i notacja nazywa się 'Big Ohnotation'

26
00:01:06,110 --> 00:01:08,320
dla opisywania to.

27
00:01:08,320 --> 00:01:10,820
Formalna definicja jest to, że funkcja f (x)

28
00:01:10,820 --> 00:01:13,390
jest uruchamiany na Postanowieniem z dnia g (x)

29
00:01:13,390 --> 00:01:15,140
, jeśli istnieje nawet pewien (x) wartość, x ₀ i

30
00:01:15,140 --> 00:01:17,630
niektóre stała, C,, dla których

31
00:01:17,630 --> 00:01:19,340
f (x) jest mniej niż lub równa, aby

32
00:01:19,340 --> 00:01:21,230
, że stała czasy w g (x)

33
00:01:21,230 --> 00:01:23,190
dla wszystkich x większej niż x ₀.

34
00:01:23,190 --> 00:01:25,290
>> Ale nie daj się przestraszony od hotelu przez formalnego definicji.

35
00:01:25,290 --> 00:01:28,020
Co oznacza ten właściwie znaczy w mniej kategoriach teoretycznych?

36
00:01:28,020 --> 00:01:30,580
Cóż, jest to w zasadzie sposobem of analizując

37
00:01:30,580 --> 00:01:33,580
jak szybko programu uruchomieniowa rośnie asymptotycznie.

38
00:01:33,580 --> 00:01:37,170
, Że jest, jak rozmiar z twoich wejściami rośnie w kierunku nieskończoności,

39
00:01:37,170 --> 00:01:41,390
słownie, jesteś sortowaniu tablicę wielkości, 1000 w porównaniu do tablicy wielkości, 10.

40
00:01:41,390 --> 00:01:44,950
Jak zgadza się z uruchomieniowa of Twojego programu rosnąć?

41
00:01:44,950 --> 00:01:47,390
Na przykład, wyobraź sobie, liczenie samym liczbę znaków,

42
00:01:47,390 --> 00:01:49,350
w ciągu znaków Najprostszym sposobem

43
00:01:49,350 --> 00:01:51,620
 w trakcie spaceru przez na całego łańcucha znaków

44
00:01:51,620 --> 00:01:54,790
letter-przez-letter i dodając 1 do licznika dla każdego znaku.

45
00:01:55,700 --> 00:01:58,420
Algorytm ten powiedział do uruchomienia w czasie liniowym

46
00:01:58,420 --> 00:02:00,460
się z w odniesieniu do liczby z znaków,

47
00:02:00,460 --> 00:02:02,670
'N' w ciągu.

48
00:02:02,670 --> 00:02:04,910
W skrócie, to działa w czasie O (n).

49
00:02:05,570 --> 00:02:07,290
Dlaczego tak jest?

50
00:02:07,290 --> 00:02:09,539
Well, przy użyciu to podejście, czas wymagany

51
00:02:09,539 --> 00:02:11,300
przemierzać cały ciąg

52
00:02:11,300 --> 00:02:13,920
jest proporcjonalne do liczby znaków.

53
00:02:13,920 --> 00:02:16,480
Zliczanie znaków w 20-ciąg znaków

54
00:02:16,480 --> 00:02:18,580
jest dzieje do podjęcia dwa razy na tak długo,, jak to ma

55
00:02:18,580 --> 00:02:20,330
, aby policzyć znaków w 10-znakowym ciąg znaków,

56
00:02:20,330 --> 00:02:23,000
, ponieważ masz aby spojrzeć na wszystkich znaków

57
00:02:23,000 --> 00:02:25,740
i każdy znak przyjmuje taką samą ilość czasu, aby przyjrzeć.

58
00:02:25,740 --> 00:02:28,050
Jak zwiększyć liczbę znaków, z,

59
00:02:28,050 --> 00:02:30,950
czas pracy zwiększy się liniowo wraz z długością wejściowego.

60
00:02:30,950 --> 00:02:33,500
>> Teraz, sobie wyobrazić, jeśli Ci się zdecydować, że liniową czas,

61
00:02:33,500 --> 00:02:36,390
O (n), po prostu nie było wystarczająco szybki, dla ciebie?

62
00:02:36,390 --> 00:02:38,750
Może jesteś przechowywania ogromne ciągi znaków,

63
00:02:38,750 --> 00:02:40,450
i nie możesz sobie pozwolić na dodatkowy czas, jaki byłby potrzebny

64
00:02:40,450 --> 00:02:44,000
przechodzenie wszystkich swoich znaków licząc jeden po drugim.

65
00:02:44,000 --> 00:02:46,650
Więc, ty zdecydować się na spróbować czegoś innego.

66
00:02:46,650 --> 00:02:49,270
Co, jeżeli zechciałby Pan się zdarzyć do już przechowuj liczbę znaków, z

67
00:02:49,270 --> 00:02:52,690
w ciąg, powiedzmy, w zmiennej o o nazwie 'len,'

68
00:02:52,690 --> 00:02:54,210
wcześnie na w programie,

69
00:02:54,210 --> 00:02:57,800
, zanim nawet przechowywane na bardzo 1-gi znak w Twojego ciąg?

70
00:02:57,800 --> 00:02:59,980
Potem, wszystko trzeba było zrobić, aby dowiedzieć się długość ciągu,

71
00:02:59,980 --> 00:03:02,570
, to sprawdzić, to, co wartość zmiennej jest.

72
00:03:02,570 --> 00:03:05,530
You nie będzie musiał, aby spojrzeć na sam ciąg na wszystkich,

73
00:03:05,530 --> 00:03:08,160
i dostęp do wartości zmiennej jak len jest uważane

74
00:03:08,160 --> 00:03:11,100
asymptotically stała operacja czas,

75
00:03:11,100 --> 00:03:13,070
lub O (1).

76
00:03:13,070 --> 00:03:17,110
Dlaczego tak jest? Well, pamiętaj, co asymptotyczna złożoność oznacza.

77
00:03:17,110 --> 00:03:19,100
Jak działa uruchomieniowa zmiana jako rozmiar

78
00:03:19,100 --> 00:03:21,400
Of Your Wejścia rośnie?

79
00:03:21,400 --> 00:03:24,630
>> Say Ci się były próby, aby uzyskać liczbę znaków, z, w ramach większego ciąg znaków.

80
00:03:24,630 --> 00:03:26,960
Cóż, to nie miałoby znaczenia, jak duży Ci dokonać ciąg znaków,

81
00:03:26,960 --> 00:03:28,690
nawet milionów znaków długa,

82
00:03:28,690 --> 00:03:31,150
wszystko trzeba było zrobić, aby znaleźć wartość ciągu długości z tego podejścia,

83
00:03:31,150 --> 00:03:33,790
jest odczytać wartość zmiennej len,

84
00:03:33,790 --> 00:03:35,440
, które masz już wykonane.

85
00:03:35,440 --> 00:03:38,200
Długość wejście, to jest długość ciągu próbujesz znaleźć,

86
00:03:38,200 --> 00:03:41,510
, nie wpływa w ogóle, jak szybko Twój program biegnie.

87
00:03:41,510 --> 00:03:44,550
Ta część Twojego programu byłoby uruchamiane równie szybkie na zasadzie jeden-znakowym łańcucha znaków

88
00:03:44,550 --> 00:03:46,170
i tysiąc-character string,

89
00:03:46,170 --> 00:03:49,140
i dlatego ten program będzie dalej działa w czasie stałym

90
00:03:49,140 --> 00:03:51,520
w odniesieniu do na wielkości wejściowego.

91
00:03:51,520 --> 00:03:53,920
>> Of Oczywiście, istnieje znajduje się wadą.

92
00:03:53,920 --> 00:03:55,710
Państwo spędzić dodatkową przestrzeń pamięci, na Twoim komputerze

93
00:03:55,710 --> 00:03:57,380
Przechowując zmienną,

94
00:03:57,380 --> 00:03:59,270
i dodatkowy czas potrzebny

95
00:03:59,270 --> 00:04:01,490
do faktycznego przechowywania zmiennej

96
00:04:01,490 --> 00:04:03,390
ale punkt wciąż stoi,

97
00:04:03,390 --> 00:04:05,060
dowiedzieć się, jak długo Twój ciąg był

98
00:04:05,060 --> 00:04:07,600
, nie zależy od na długości z ciągu znaków, od wszystkie.

99
00:04:07,600 --> 00:04:10,720
Tak więc, że działa on w O (1) lub Stała czasowa.

100
00:04:10,720 --> 00:04:13,070
To z pewnością nie zgadza się z musi oznaczać

101
00:04:13,070 --> 00:04:15,610
, że Twój kod jest uruchamiany w 1 kroku,

102
00:04:15,610 --> 00:04:17,470
ale nie ma znaczenia, ile kroków jest,

103
00:04:17,470 --> 00:04:20,019
jeśli nie zmienia się wielkości wejściowych,

104
00:04:20,019 --> 00:04:23,420
to wciąż asymptotycznie stałą, która reprezentujemy jako O (1).

105
00:04:23,420 --> 00:04:25,120
>> Jak można prawdopodobnie guess,

106
00:04:25,120 --> 00:04:27,940
istnieje wiele różnych Big O czasy autonomii do mierzenia algorytmy, z.

107
00:04:27,940 --> 00:04:32,980
O (n) ² algorytmy są asymptotycznie wolniej niż O (n) algorytmów.

108
00:04:32,980 --> 00:04:35,910
, Że jest, w miarę jak liczba się z elementów (n) rośnie,

109
00:04:35,910 --> 00:04:39,280
ostatecznie O (n) ² algorytmów będzie zająć więcej czasu,

110
00:04:39,280 --> 00:04:41,000
niż O (n) algorytmy do uruchomienia.

111
00:04:41,000 --> 00:04:43,960
To nie znaczy, O (n) algorytmy zawsze uruchamiane szybciej

112
00:04:43,960 --> 00:04:46,410
niż O (N) ² algorytmów, nawet w tym samym środowiska naturalnego,

113
00:04:46,410 --> 00:04:48,080
na tym samym Komputery.

114
00:04:48,080 --> 00:04:50,180
Może dla małych rozmiarach wejściowych,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² algorytm może faktycznie pracować szybciej,

116
00:04:52,900 --> 00:04:55,450
, ale, w końcu,, jak na wielkości wejściowego zwiększa

117
00:04:55,450 --> 00:04:58,760
w kierunku nieskończoności, O (n) algorytm ² jego uruchomieniowa

118
00:04:58,760 --> 00:05:02,000
będzie ostatecznie przyćmi środowisko wykonawcze prac rady (n) O algorytmu.

119
00:05:02,000 --> 00:05:04,230
Tak jak każdy funkcji kwadratowej matematycznej

120
00:05:04,230 --> 00:05:06,510
 będzie ostatecznie wyprzedzić jakąkolwiek liniową funkcję,

121
00:05:06,510 --> 00:05:09,200
nie ważne jak dużo się z głowicy rozpocząć liniową funkcję rozpoczyna się off z.

122
00:05:10,010 --> 00:05:12,000
Jeśli jesteś pracy z dużymi ilości danych,

123
00:05:12,000 --> 00:05:15,510
algorytmy, które są uruchamiane w O (n) Czas ² może naprawdę skończyć się spowalniając Twój program,

124
00:05:15,510 --> 00:05:17,770
ale dla małych rozmiarach wejściowych,

125
00:05:17,770 --> 00:05:19,420
Ci się prawdopodobnie nie będzie nawet zauważy.

126
00:05:19,420 --> 00:05:21,280
>> Another asymptotyczna złożoność jest,

127
00:05:21,280 --> 00:05:24,420
logarytmiczna czas, O (log n).

128
00:05:24,420 --> 00:05:26,340
Przykładem algorytmu, który działa to szybko

129
00:05:26,340 --> 00:05:29,060
jest klasyczny algorytm wyszukiwania binarnego,

130
00:05:29,060 --> 00:05:31,850
do znalezienia elementu w już posortowanej listy elementów.

131
00:05:31,850 --> 00:05:33,400
>> Jeśli nie wiesz, co wyszukiwanie binarne nie,

132
00:05:33,400 --> 00:05:35,170
Wytłumaczę to dla Ciebie bardzo szybko.

133
00:05:35,170 --> 00:05:37,020
Powiedzmy, że szukasz numeru 3

134
00:05:37,020 --> 00:05:40,200
w tej tablicy liczb całkowitych.

135
00:05:40,200 --> 00:05:42,140
Wygląda na środkowym elemencie tablicy

136
00:05:42,140 --> 00:05:46,830
i pyta: "Czy element chcę większa, równa lub mniejsza niż to?"

137
00:05:46,830 --> 00:05:49,150
Jeśli jest równe, to świetnie. Znalazłeś element i gotowe.

138
00:05:49,150 --> 00:05:51,300
Jeśli jest większa, to wiesz, element

139
00:05:51,300 --> 00:05:53,440
musi być w prawej stronie tablicy

140
00:05:53,440 --> 00:05:55,200
i można tylko patrzeć na to w przyszłości,

141
00:05:55,200 --> 00:05:57,690
i jeśli jest mniejsza, to wiesz, że musi być z lewej strony.

142
00:05:57,690 --> 00:06:00,980
Proces ten jest powtarzany przy mniejszym rozmiarze tablicy

143
00:06:00,980 --> 00:06:02,870
aż poprawna element jest znaleziony.

144
00:06:08,080 --> 00:06:11,670
>> Ten potężny algorytm skraca rozmiar tablicy na pół z każdej operacji.

145
00:06:11,670 --> 00:06:14,080
Tak więc, aby znaleźć element w posortowanej tablicy o wielkości 8,

146
00:06:14,080 --> 00:06:16,170
co najwyżej (log ₂ 8),

147
00:06:16,170 --> 00:06:18,450
lub 3 z tych operacji,

148
00:06:18,450 --> 00:06:22,260
sprawdzając środkowy element, a następnie cięcie tablicy w pół będzie wymagane,

149
00:06:22,260 --> 00:06:25,670
podczas gdy tablica ma rozmiar 16 (log ₂ 16),

150
00:06:25,670 --> 00:06:27,480
lub 4 operacje.

151
00:06:27,480 --> 00:06:30,570
To tylko 1 więcej operacji o podwojeniu wielkości tablicy.

152
00:06:30,570 --> 00:06:32,220
Podwojenie rozmiaru tablicy

153
00:06:32,220 --> 00:06:35,160
zwiększa czas pracy tylko o 1 kawałek kodu.

154
00:06:35,160 --> 00:06:37,770
Ponownie, sprawdzając środkowy element z listy, a następnie pęka.

155
00:06:37,770 --> 00:06:40,440
Tak więc, jest to że działanie w logarytmicznej czasu

156
00:06:40,440 --> 00:06:42,440
O (log n).

157
00:06:42,440 --> 00:06:44,270
Ale poczekaj, można powiedzieć,

158
00:06:44,270 --> 00:06:47,510
nie zależy od tego, gdzie na liście Element szukasz jest?

159
00:06:47,510 --> 00:06:50,090
Co jeśli pierwszy element spojrzeć na dzieje się właściwa?

160
00:06:50,090 --> 00:06:52,040
Wtedy, to zajmuje tylko 1 operację,

161
00:06:52,040 --> 00:06:54,310
bez względu na to, jak duża lista.

162
00:06:54,310 --> 00:06:56,310
>> Cóż, dlatego informatycy mają więcej warunków

163
00:06:56,310 --> 00:06:58,770
do asymptotycznej złożoności które odzwierciedlają najlepszą sprawę

164
00:06:58,770 --> 00:07:01,050
i najgorszy występy algorytmu.

165
00:07:01,050 --> 00:07:03,320
Bardziej poprawnie, górne i dolne granice

166
00:07:03,320 --> 00:07:05,090
na starcie.

167
00:07:05,090 --> 00:07:07,660
W najlepszym przypadku dla wyszukiwania binarnego, nasz element jest

168
00:07:07,660 --> 00:07:09,330
tam w środku,

169
00:07:09,330 --> 00:07:11,770
i masz go w stałym czasie,

170
00:07:11,770 --> 00:07:14,240
niezależnie od tego jak duża reszta tablicy jest.

171
00:07:15,360 --> 00:07:17,650
Używa się do tego symbolu jest Ω.

172
00:07:17,650 --> 00:07:19,930
Tak więc, ten algorytm jest powiedziane do uruchomienia w Ω (1).

173
00:07:19,930 --> 00:07:21,990
W najlepszym przypadku, stwierdzi element szybko,

174
00:07:21,990 --> 00:07:24,200
bez względu na to, jak duża jest tablica,

175
00:07:24,200 --> 00:07:26,050
a w najgorszym przypadku,

176
00:07:26,050 --> 00:07:28,690
ma do wykonania (log n) kontrole międzyczasy

177
00:07:28,690 --> 00:07:31,030
macierzy znaleźć odpowiedni element.

178
00:07:31,030 --> 00:07:34,270
Najgorszy górne granice są określone z wielkim "O", które już znasz.

179
00:07:34,270 --> 00:07:38,080
Tak, to O (log n), ale Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> Linear search, natomiast

181
00:07:40,680 --> 00:07:43,220
w którym można przejść przez każdego elementu tablicy

182
00:07:43,220 --> 00:07:45,170
, aby znaleźć taki, który chcesz,

183
00:07:45,170 --> 00:07:47,420
jest w najlepszym Ω (1).

184
00:07:47,420 --> 00:07:49,430
Ponownie, pierwszy element chcesz.

185
00:07:49,430 --> 00:07:51,930
Tak, to nie ma znaczenia, jak duża tablica jest.

186
00:07:51,930 --> 00:07:54,840
W najgorszym przypadku, to ostatni element w tablicy.

187
00:07:54,840 --> 00:07:58,560
Więc, musisz chodzić po wszystkich n elementów w tablicy, aby znaleźć to,

188
00:07:58,560 --> 00:08:02,170
jak jeśli szukaliśmy 3.

189
00:08:04,320 --> 00:08:06,030
Tak, to działa w O (n) czasu

190
00:08:06,030 --> 00:08:09,330
, ponieważ jest proporcjonalna do ilości elementów w tablicy.

191
00:08:10,800 --> 00:08:12,830
>> Jeden używany symbol Θ.

192
00:08:12,830 --> 00:08:15,820
Może to być wykorzystane do opisania algorytmów gdzie najlepszym i najgorszym przypadku

193
00:08:15,820 --> 00:08:17,440
są takie same.

194
00:08:17,440 --> 00:08:20,390
Jest to przypadek w ciągu długości algorytmów rozmawialiśmy o wcześniej.

195
00:08:20,390 --> 00:08:22,780
To jest, jeśli przechowuje się w zmiennej przed

196
00:08:22,780 --> 00:08:25,160
możemy przechowywać ciąg i przejść ją później w czasie stałym.

197
00:08:25,160 --> 00:08:27,920
Bez względu na to, jaka liczba

198
00:08:27,920 --> 00:08:30,130
jesteśmy przechowywania tej zmiennej, musimy na to patrzeć.

199
00:08:33,110 --> 00:08:35,110
Najlepszym przypadkiem jest, patrzymy na niego

200
00:08:35,110 --> 00:08:37,120
i znaleźć długość łańcucha.

201
00:08:37,120 --> 00:08:39,799
Więc Ω (1) lub najlepiej sprawa stała czas.

202
00:08:39,799 --> 00:08:41,059
Najgorszy przypadek jest

203
00:08:41,059 --> 00:08:43,400
patrzymy na nią i znaleźć długość łańcucha.

204
00:08:43,400 --> 00:08:47,300
Tak więc, o (1) lub w stałej czasowej w najgorszym przypadku.

205
00:08:47,300 --> 00:08:49,180
Tak więc, ponieważ najlepsze najgorszych przypadków przypadku i są takie same,

206
00:08:49,180 --> 00:08:52,520
to można powiedzieć, aby uruchomić w Θ (1) czasu.

207
00:08:54,550 --> 00:08:57,010
>> Podsumowując, mamy dobrych sposobów na wymyślenie efektywności kodów

208
00:08:57,010 --> 00:09:00,110
nie wiedząc nic o świecie rzeczywistym czasu ich podjęcia do pracy,

209
00:09:00,110 --> 00:09:02,270
który ma wpływ wiele czynników zewnętrznych,

210
00:09:02,270 --> 00:09:04,190
odmiennego sprzętu, w tym oprogramowania,

211
00:09:04,190 --> 00:09:06,040
lub specyfika kodzie.

212
00:09:06,040 --> 00:09:08,380
Ponadto, pozwala rozumowi oraz o tym, co się wydarzy

213
00:09:08,380 --> 00:09:10,180
gdy rozmiar wejść wzrasta.

214
00:09:10,180 --> 00:09:12,490
>> Jeśli pracujesz w O (n) ² algorytmu,

215
00:09:12,490 --> 00:09:15,240
lub gorzej, O (2 ⁿ) algorytm,

216
00:09:15,240 --> 00:09:17,170
jednym z najszybciej rozwijających się typów,

217
00:09:17,170 --> 00:09:19,140
będziesz naprawdę zacząć zwracać uwagę spowolnienie

218
00:09:19,140 --> 00:09:21,220
po rozpoczęciu pracy z większą ilością danych.

219
00:09:21,220 --> 00:09:23,590
>> To asymptotyczna złożoność. Dzięki.