1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [Odtwarzanie muzyki]

3
00:00:10,800 --> 00:00:13,500
DAVID MALAN: W porządku.

4
00:00:13,500 --> 00:00:14,670
Dobrze, witamy z powrotem.

5
00:00:14,670 --> 00:00:18,120
Więc to jest Tydzień 4, początek
nich, już.

6
00:00:18,120 --> 00:00:21,320
A przypomnijmy sobie, że w zeszłym tygodniu, stawiamy
kod na bok tylko trochę

7
00:00:21,320 --> 00:00:24,240
i zaczęliśmy rozmawiać trochę więcej
wysokim poziomie, o rzeczy, jak

8
00:00:24,240 --> 00:00:28,130
wyszukiwanie i sortowanie, które choć
dość proste pomysły, są

9
00:00:28,130 --> 00:00:31,840
reprezentatywne klasy problemów
zaczniesz rozwiązywać szczególnie

10
00:00:31,840 --> 00:00:34,820
jak zacząć myśleć o final
projekty i ciekawe rozwiązania można

11
00:00:34,820 --> 00:00:36,760
może mieć do rzeczywistych problemów.

12
00:00:36,760 --> 00:00:39,490
Teraz sortowanie bąbelkowe był jednym z najprostszych
takie algorytmy, i to

13
00:00:39,490 --> 00:00:42,900
pracował poprzez te małe liczby
na liście lub w rodzaju tablicy z

14
00:00:42,900 --> 00:00:46,530
bubble drogę do góry i
duże cyfry przejść swoją drogę w dół do

15
00:00:46,530 --> 00:00:47,930
koniec tej listy.

16
00:00:47,930 --> 00:00:50,650
>> I pamiętam, że możemy wizualizować
Sortowanie bąbelkowe mało

17
00:00:50,650 --> 00:00:52,310
coś takiego.

18
00:00:52,310 --> 00:00:53,640
Więc pozwól mi iść dalej i kliknij przycisk Start.

19
00:00:53,640 --> 00:00:55,350
Ja wstępnie rodzaju bańki.

20
00:00:55,350 --> 00:00:58,920
A jeśli przypomnieć, że wyższy blue
linie reprezentują duże cyfry, małe

21
00:00:58,920 --> 00:01:03,300
niebieskie linie oznaczają małe liczby, jak
możemy przejść przez to jeszcze raz i jeszcze raz i

22
00:01:03,300 --> 00:01:07,680
ponownie, porównywanie dwóch prętów obok siebie
inne w kolorze czerwonym, jedziemy do wymiany

23
00:01:07,680 --> 00:01:11,010
Największy i najmniejszy jeśli
są one w porządku.

24
00:01:11,010 --> 00:01:14,150
>> Więc to będzie iść i iść i iść
dalej, a zobaczysz, że większe

25
00:01:14,150 --> 00:01:16,700
elementy są torują sobie drogę do
prawo, a mniejsze elementy są

26
00:01:16,700 --> 00:01:17,900
torują sobie drogę do lewej.

27
00:01:17,900 --> 00:01:21,380
Ale zaczęliśmy ilościowo
wydajność,

28
00:01:21,380 --> 00:01:22,970
Jakość tego algorytmu.

29
00:01:22,970 --> 00:01:25,200
A my powiedzieliśmy, że w najgorszym
przypadku, algorytm ten wziął

30
00:01:25,200 --> 00:01:27,940
w przybliżeniu, ile kroków?

31
00:01:27,940 --> 00:01:28,980
>> Więc n do kwadratu.

32
00:01:28,980 --> 00:01:30,402
A co było n?

33
00:01:30,402 --> 00:01:31,650
>> PUBLICZNOŚCI: Ilość elementów.

34
00:01:31,650 --> 00:01:32,790
>> DAVID MALAN: Tak n było
Ilość elementów.

35
00:01:32,790 --> 00:01:33,730
I tak będziemy robić to częściej.

36
00:01:33,730 --> 00:01:36,650
Za każdym razem chcemy rozmawiać o wielkości
problemu lub rozmiar

37
00:01:36,650 --> 00:01:39,140
input, lub czas potrzebny
do standardu, my będziemy po prostu

38
00:01:39,140 --> 00:01:41,610
co uogólnione
wejście jest jako n.

39
00:01:41,610 --> 00:01:45,970
Więc z powrotem w tygodniu 0, liczba stron
w książce telefonicznej był n.

40
00:01:45,970 --> 00:01:47,550
Liczba studentów
w pomieszczeniu się N.

41
00:01:47,550 --> 00:01:49,630
Więc i tu mamy po
że wzór.

42
00:01:49,630 --> 00:01:52,800
>> Teraz n do kwadratu nie jest szczególnie
szybko, więc staraliśmy się zrobić lepiej.

43
00:01:52,800 --> 00:01:55,970
I tak patrzyliśmy na kilka
inne algorytmy, z których

44
00:01:55,970 --> 00:01:57,690
były rodzaju wybór.

45
00:01:57,690 --> 00:01:59,180
Wybór był więc sort
trochę inaczej.

46
00:01:59,180 --> 00:02:03,130
To było prawie prostsze, ośmielę się powiedzieć,
zgodnie z którą zacząłem na początku

47
00:02:03,130 --> 00:02:06,740
Lista naszych wolontariuszy i po prostu ponownie
i znowu i znowu przeszedł

48
00:02:06,740 --> 00:02:10,060
lista, wyrywanie najmniejsza
elementem w czasie i oddanie go lub

49
00:02:10,060 --> 00:02:13,040
jej na początku listy.

50
00:02:13,040 --> 00:02:16,410
>> Ale to też kiedyś zaczynaliśmy myśleć
przez matematykę i większe

51
00:02:16,410 --> 00:02:19,860
obraz, myślałem o tym, jak wiele razy
Byłem tam iz powrotem iz powrotem

52
00:02:19,860 --> 00:02:24,090
i do przodu, my powiedzieliśmy, w najgorszym przypadku,
sort wybór też był, co?

53
00:02:24,090 --> 00:02:24,960
n do kwadratu.

54
00:02:24,960 --> 00:02:27,490
Teraz w świecie rzeczywistym, to może
rzeczywiście być nieznacznie szybciej.

55
00:02:27,490 --> 00:02:30,620
Bo znowu, nie mam do utrzymania
Cofając się raz miałem posortowane

56
00:02:30,620 --> 00:02:31,880
najmniejsze elementy.

57
00:02:31,880 --> 00:02:35,090
Ale jeśli myślimy o bardzo dużych n, a
jeśli rodzaj zrobić z matematyki jako

58
00:02:35,090 --> 00:02:39,170
I tak na pokładzie, z n do kwadratu
minus coś, wszystko inne

59
00:02:39,170 --> 00:02:41,850
oprócz n do kwadratu, raz n
robi się naprawdę duża, nie

60
00:02:41,850 --> 00:02:42,850
naprawdę aż tak istotne.

61
00:02:42,850 --> 00:02:45,470
Więc jak informatyków, mamy coś w rodzaju
przymknąć oko na mniejsze

62
00:02:45,470 --> 00:02:49,220
czynniki i skupić się tylko na czynnik
Wyrażenie, które zamierza dokonać

63
00:02:49,220 --> 00:02:50,330
Największa różnica.

64
00:02:50,330 --> 00:02:52,840
>> No, wreszcie spojrzał
w rodzaju wstawiania.

65
00:02:52,840 --> 00:02:56,620
I to było podobne w duchu, ale
zamiast przejść iteracyjnie i

66
00:02:56,620 --> 00:03:01,250
wybierz najmniejszy element o
razem, a nie wziął rękę, że

67
00:03:01,250 --> 00:03:04,070
została rozpatrzona, i postanowiłem, wszystko
Dobrze, że należysz tutaj.

68
00:03:04,070 --> 00:03:06,160
Potem przeniósł się do następnego elementu
i postanowił, że on lub

69
00:03:06,160 --> 00:03:07,470
należała tutaj.

70
00:03:07,470 --> 00:03:08,810
A potem przeniosłem się na i na.

71
00:03:08,810 --> 00:03:11,780
I może się, po drodze,
przeniesienie tych ludzi w celu

72
00:03:11,780 --> 00:03:13,030
zrobić miejsce dla nich.

73
00:03:13,030 --> 00:03:16,880
Więc to było coś w rodzaju psychicznego odwrócenia
z rodzaju selekcji, że

74
00:03:16,880 --> 00:03:18,630
nazywa rodzaj wstawiania.

75
00:03:18,630 --> 00:03:20,810
>> Więc te tematy, które pojawiają
w świecie rzeczywistym.

76
00:03:20,810 --> 00:03:23,640
Jeszcze kilka lat temu, gdy pewien
senator został na prezydenta,

77
00:03:23,640 --> 00:03:27,160
Eric Schmidt, w czasie CEO
Google, rzeczywiście miał okazję

78
00:03:27,160 --> 00:03:28,040
przeprowadzić z nim wywiad.

79
00:03:28,040 --> 00:03:32,010
I myśleliśmy, że będziemy dzielić tę YouTube
przypiąć na Ciebie, czy możemy włączyć się

80
00:03:32,010 --> 00:03:32,950
objętość.

81
00:03:32,950 --> 00:03:39,360
>> [PLAYBACK VIDEO]

82
00:03:39,360 --> 00:03:44,620
>> -Teraz, Senator, jesteś tutaj w Google,
a ja lubię myśleć o prezydenturę

83
00:03:44,620 --> 00:03:46,042
jak rozmowy kwalifikacyjnej.

84
00:03:46,042 --> 00:03:47,770
>> [Śmiech]

85
00:03:47,770 --> 00:03:50,800
>> -Teraz trudno dostać
zadaniem jako prezydenta.

86
00:03:50,800 --> 00:03:52,480
I idziesz przez
rygory teraz.

87
00:03:52,480 --> 00:03:54,330
Trudno też, aby dostać pracę w Google.

88
00:03:54,330 --> 00:03:59,610
Mamy pytania i prosić
nasi kandydaci pytania.

89
00:03:59,610 --> 00:04:02,250
A ten jest z Larry Schwimmer.

90
00:04:02,250 --> 00:04:05,325
>> [Śmiech]

91
00:04:05,325 --> 00:04:06,400
-Myślicie, że żartuję?

92
00:04:06,400 --> 00:04:08,750
Jest tutaj.

93
00:04:08,750 --> 00:04:12,110
Co to jest najbardziej skuteczny sposób
sortować milion dwa-bitowe liczby całkowite?

94
00:04:12,110 --> 00:04:15,810
>> [Śmiech]

95
00:04:15,810 --> 00:04:18,260
>> -No cóż, uh -

96
00:04:18,260 --> 00:04:19,029
>> -Przepraszam.

97
00:04:19,029 --> 00:04:19,745
Może powinniśmy -

98
00:04:19,745 --> 00:04:21,000
>> -Nie, nie, nie, nie, nie.

99
00:04:21,000 --> 00:04:21,470
>> -To nie jest -

100
00:04:21,470 --> 00:04:22,185
OK.

101
00:04:22,185 --> 00:04:25,328
>> -Myślę, że byłoby bubble sort
być nie tak droga.

102
00:04:25,328 --> 00:04:26,792
>> [Śmiech]

103
00:04:26,792 --> 00:04:28,510
>> [CHEERING i oklaski]

104
00:04:28,510 --> 00:04:31,211
>> -Chodź, który powiedział mu to?

105
00:04:31,211 --> 00:04:32,155
OK.

106
00:04:32,155 --> 00:04:33,350
>> [END PLAYBACK VIDEO]

107
00:04:33,350 --> 00:04:35,070
>> DAVID MALAN: Więc nie masz.

108
00:04:35,070 --> 00:04:39,600
Więc zaczęliśmy ilościowego nich działa
razy, że tak powiem, z czymś

109
00:04:39,600 --> 00:04:43,480
nazywa asymptotycznej notacji, która jest
tylko w odniesieniu do naszego rodzaju toczenia

110
00:04:43,480 --> 00:04:47,420
przymknąć oko na te czynniki i mniejsze
tylko patrząc w czasie jazdy,

111
00:04:47,420 --> 00:04:51,250
Wydajność tych algorytmów,
jak n ma naprawdę duży w czasie.

112
00:04:51,250 --> 00:04:55,110
A więc wprowadziliśmy duże O. i Big O
reprezentował coś, co myśleliśmy,

113
00:04:55,110 --> 00:04:57,000
jako górna granica.

114
00:04:57,000 --> 00:04:59,570
I rzeczywiście, Barry, możemy obniżyć
niż mikrofon nieco mało?

115
00:04:59,570 --> 00:05:01,040
>> Myśleliśmy, że to jest górna granica.

116
00:05:01,040 --> 00:05:04,710
Tak duże O z n do kwadratu oznacza, że ​​w
w najgorszym przypadku, coś jak

117
00:05:04,710 --> 00:05:07,780
Wybór odbędzie sort
n kwadratu kroki.

118
00:05:07,780 --> 00:05:10,310
Albo coś w rodzaju wstawiania
by n kwadratu kroki.

119
00:05:10,310 --> 00:05:15,150
Teraz coś wstawiania
sort, co było najgorszym przypadku?

120
00:05:15,150 --> 00:05:18,200
Biorąc pod uwagę, array, co jest najgorsze
możliwy scenariusz, który może się okazać,

121
00:05:18,200 --> 00:05:20,650
się w obliczu?

122
00:05:20,650 --> 00:05:21,860
>> Jest to całkowicie do tyłu, prawda?

123
00:05:21,860 --> 00:05:24,530
Bo jeśli jest to całkowicie do tyłu,
co musisz zrobić dużo pracy.

124
00:05:24,530 --> 00:05:26,420
Bo jeśli jesteś całkowicie do tyłu,
masz zamiar znaleźć

125
00:05:26,420 --> 00:05:28,840
Największym elementem tutaj, choć
należy, tam na dole.

126
00:05:28,840 --> 00:05:31,140
Więc masz zamiar powiedzieć, dobrze, co
ten moment w czasie, tutaj mają miejsce,

127
00:05:31,140 --> 00:05:32,310
więc zostawić ją w spokoju.

128
00:05:32,310 --> 00:05:35,425
>> Wtedy zdajesz sobie sprawę, oh, cholera, muszę
przenieść ten nieco mniejszy element, do

129
00:05:35,425 --> 00:05:36,470
lewo od Ciebie.

130
00:05:36,470 --> 00:05:38,770
Potem muszę zrobić to jeszcze raz
i znowu i znowu.

131
00:05:38,770 --> 00:05:41,410
I gdybym chodził w tę iz powrotem, można
to coś w rodzaju czuć wydajność

132
00:05:41,410 --> 00:05:45,540
że algorytm, ponieważ ciągle jestem
tasowanie wszyscy w

133
00:05:45,540 --> 00:05:46,510
array, aby zrobić miejsce dla niego.

134
00:05:46,510 --> 00:05:47,750
Więc to jest najgorszy przypadek.

135
00:05:47,750 --> 00:05:48,570
>> Natomiast -

136
00:05:48,570 --> 00:05:50,320
i to był cliffhanger ostatnio -

137
00:05:50,320 --> 00:05:54,065
możemy powiedzieć, że rodzaj wstawiania
była omega z czego?

138
00:05:54,065 --> 00:05:57,530
Jaki jest najlepszy-case running
czas sortowania wstawiania?

139
00:05:57,530 --> 00:05:58,520
Więc to faktycznie n.

140
00:05:58,520 --> 00:06:00,980
To było puste, że wyszliśmy
na pokładzie ostatni raz.

141
00:06:00,980 --> 00:06:03,160
>> I to jest omega n bo dlaczego?

142
00:06:03,160 --> 00:06:06,630
No, w najlepszym przypadku, co jest
sort wstawiania będzie przekazany?

143
00:06:06,630 --> 00:06:09,830
Cóż, lista, która jest całkowicie posortowane
już, minimal do zrobienia.

144
00:06:09,830 --> 00:06:12,460
Ale to, co jest miłe o rodzaju wstawiania
jest to, że dlatego, że zaczyna się tutaj i

145
00:06:12,460 --> 00:06:15,340
decyduje, oh, jesteś numer
jeden, należysz tutaj.

146
00:06:15,340 --> 00:06:16,970
Och, co za szczęście.

147
00:06:16,970 --> 00:06:17,740
>> Jesteś numer dwa.

148
00:06:17,740 --> 00:06:19,030
Ty również tutaj.

149
00:06:19,030 --> 00:06:21,010
Numer trzy, a nawet lepiej,
należysz tutaj.

150
00:06:21,010 --> 00:06:25,210
Tak szybko, jak to robi się do końca
liście, od sortowania wstawiania w pseudokod

151
00:06:25,210 --> 00:06:28,010
że szliśmy przez ustnie
Ostatni raz, to się robi.

152
00:06:28,010 --> 00:06:32,790
Ale selekcji Ilość natomiast,
robiłem co?

153
00:06:32,790 --> 00:06:35,260
>> Ruszyłem listę
znowu i znowu i znowu.

154
00:06:35,260 --> 00:06:39,160
Ponieważ klucz insight był tylko
kiedy już spojrzał na drodze do

155
00:06:39,160 --> 00:06:42,500
koniec listy możesz być pewien,
że element był wybrany

156
00:06:42,500 --> 00:06:45,560
rzeczywiście obecnie najmniejszy element.

157
00:06:45,560 --> 00:06:48,920
Więc te różne modele mentalne end
up uzyskując pewne bardzo realne-świat

158
00:06:48,920 --> 00:06:53,130
Różnice dla nas, jak i te
teoretyczne asymptotyczne różnice.

159
00:06:53,130 --> 00:06:56,910
>> Przypomnę więc tylko, to, big O n
kwadratu, widzieliśmy kilka takich

160
00:06:56,910 --> 00:06:58,350
algorytmy do tej pory.

161
00:06:58,350 --> 00:06:59,580
Big O n?

162
00:06:59,580 --> 00:07:02,870
Co to jest algorytm, który może
uznać big O n?

163
00:07:02,870 --> 00:07:06,930
W najgorszym przypadku, trwa
liniowa ilość etapów.

164
00:07:06,930 --> 00:07:07,810
>> OK, linear search.

165
00:07:07,810 --> 00:07:10,470
, A w najgorszym przypadku, w którym jest
Element szukasz kiedy

166
00:07:10,470 --> 00:07:12,950
stosując liniowy wyszukiwania?

167
00:07:12,950 --> 00:07:14,680
>> OK, w najgorszym przypadku,
to nie jest nawet tam.

168
00:07:14,680 --> 00:07:17,000
A w drugim przypadku najgorszego, to
aż w końcu, co jest

169
00:07:17,000 --> 00:07:18,880
Plus-czy-minus jeden etap różnica.

170
00:07:18,880 --> 00:07:21,180
Tak więc na koniec dnia,
możemy powiedzieć, że jest liniowa.

171
00:07:21,180 --> 00:07:23,910
Big O n będzie liniowa search,
gdyż w najgorszym przypadku,

172
00:07:23,910 --> 00:07:26,610
element nie jest nawet tam lub to
aż w końcu.

173
00:07:26,610 --> 00:07:29,370
>> Cóż, big O log n.

174
00:07:29,370 --> 00:07:32,760
Nie rozmawialiśmy szczegółowo o
tego, ale widziałem go wcześniej.

175
00:07:32,760 --> 00:07:36,840
, Co prowadzi w logarytmicznej tzw
czas, w najgorszym przypadku?

176
00:07:36,840 --> 00:07:38,500
>> Tak, tak, binary search.

177
00:07:38,500 --> 00:07:42,930
I binary search w najgorszym przypadku
może posiadać element gdzieś

178
00:07:42,930 --> 00:07:45,640
średnim, czy gdzieś
wewnątrz tablicy.

179
00:07:45,640 --> 00:07:48,040
Ale znaleźć tylko raz Ciebie
podzielić listę na pół, w

180
00:07:48,040 --> 00:07:48,940
pół, na pół, na pół.

181
00:07:48,940 --> 00:07:50,200
I wtedy voila, że ​​tam jest.

182
00:07:50,200 --> 00:07:52,500
Albo znowu, w najgorszym przypadku,
to nie jest nawet tam.

183
00:07:52,500 --> 00:07:56,770
Ale nie wiesz, że to nie istnieje
aż rodzaju osiągnięcia, które ostatnio

184
00:07:56,770 --> 00:08:00,470
bottom-większość elementów przez połowę
i zmniejszenie o połowę i połowę.

185
00:08:00,470 --> 00:08:01,400
>> Big O 1.

186
00:08:01,400 --> 00:08:03,540
Więc mogliśmy duże O z 2, Big O 3 lat.

187
00:08:03,540 --> 00:08:06,260
Anytime chcesz tylko stałą liczbę,
my tak jakby po prostu uproszczenia

188
00:08:06,260 --> 00:08:07,280
że jak Big O z 1.

189
00:08:07,280 --> 00:08:10,440
Nawet jeśli realistycznie, trwa
2 lub nawet 100 kroków, jeśli jest to

190
00:08:10,440 --> 00:08:13,680
stałą liczbę kroków,
po prostu powiedzieć, big O 1.

191
00:08:13,680 --> 00:08:15,930
Co to jest algorytm
w Big O z dnia 1?

192
00:08:15,930 --> 00:08:18,350
>> PUBLICZNOŚCI: Znajdowanie długości
zmiennej.

193
00:08:18,350 --> 00:08:21,090
>> DAVID MALAN: Znalezienie
długość zmiennej?

194
00:08:21,090 --> 00:08:23,870
>> PUBLICZNOŚCI: No, długość
jeśli jest już posortowane.

195
00:08:23,870 --> 00:08:24,160
>> DAVID MALAN: Dobry.

196
00:08:24,160 --> 00:08:27,850
OK, więc znalezienie długości coś
jeżeli długość tego czegoś, podobnie jak

197
00:08:27,850 --> 00:08:30,020
tablicy, są przechowywane w jakimś zmiennej.

198
00:08:30,020 --> 00:08:33,380
Bo może po prostu czytać zmienną,
lub wydrukować zmienną, lub

199
00:08:33,380 --> 00:08:34,960
tylko ogólnie dostęp do tej zmiennej.

200
00:08:34,960 --> 00:08:37,299
I voila, że ​​ma stały czas.

201
00:08:37,299 --> 00:08:38,909
>> Natomiast, że z powrotem do zera.

202
00:08:38,909 --> 00:08:42,460
Pomyśl pierwszym tygodniu C,
dzwoni tylko printf i drukowanie

203
00:08:42,460 --> 00:08:46,240
coś na ekranie jest zapewne
stały czas, bo to po prostu trwa

204
00:08:46,240 --> 00:08:50,880
niektóre liczba cykli procesora, aby pokazać
że tekst na ekranie.

205
00:08:50,880 --> 00:08:52,720
Albo czekać - to robi?

206
00:08:52,720 --> 00:08:56,430
Jak inaczej możemy modelować
wydajność printf?

207
00:08:56,430 --> 00:09:00,420
Czy ktoś jak się nie zgadzam, że
może to nie naprawdę stały czas jest?

208
00:09:00,420 --> 00:09:03,600
W jakim sensie może printf ucieka
czas, rzeczywiście drukuje ciąg na

209
00:09:03,600 --> 00:09:05,580
ekran, być czymś
inne niż stałe.

210
00:09:05,580 --> 00:09:07,860
>> PUBLICZNOŚCI: [niesłyszalne].

211
00:09:07,860 --> 00:09:08,230
>> DAVID MALAN: Tak.

212
00:09:08,230 --> 00:09:09,300
Więc to zależy od naszego punktu widzenia.

213
00:09:09,300 --> 00:09:13,390
Jeśli rzeczywiście myśleć o wejściu do
printf jako ciąg znaków, a

214
00:09:13,390 --> 00:09:16,380
Dlatego pomiaru wielkości, które
wejście od jej długości - tak nazwijmy

215
00:09:16,380 --> 00:09:17,780
że długość n, jak również -

216
00:09:17,780 --> 00:09:21,990
zapewne, printf jest sama wielka O n
bo to będzie cię n kroków

217
00:09:21,990 --> 00:09:24,750
wydrukować każdy z tych n
znaków, najprawdopodobniej.

218
00:09:24,750 --> 00:09:27,730
Co najmniej w takim zakresie, że zakładamy
że być może jest za pomocą pętli for

219
00:09:27,730 --> 00:09:28,560
pod maską.

220
00:09:28,560 --> 00:09:30,860
>> Ale my musimy patrzeć na to
Kod do zrozumienia, że ​​lepiej.

221
00:09:30,860 --> 00:09:33,650
I rzeczywiście, gdy chłopaki zaczynają
analizowania własnych algorytmów, będziesz

222
00:09:33,650 --> 00:09:34,900
dosłownie nie tylko to.

223
00:09:34,900 --> 00:09:37,765
Sortuj gałki ocznej kod i myśleć
o - wszystko w porządku, mam tej pętli

224
00:09:37,765 --> 00:09:41,870
tutaj lub mam pętli zagnieżdżonych tutaj,
że zrobi wszystko n n razy,

225
00:09:41,870 --> 00:09:46,050
i można sortować rozumu drogę
za pośrednictwem kodu, nawet jeśli jest to

226
00:09:46,050 --> 00:09:47,980
pseudokod, a nie rzeczywisty kod.

227
00:09:47,980 --> 00:09:49,730
>> Więc co z omega n do kwadratu?

228
00:09:49,730 --> 00:09:53,582
Jaki był algorytm, który w najlepszy
Sprawa nadal trwało n kwadratu kroki?

229
00:09:53,582 --> 00:09:54,014
Tak?

230
00:09:54,014 --> 00:09:54,880
>> PUBLICZNOŚCI: [niesłyszalne].

231
00:09:54,880 --> 00:09:55,900
>> DAVID MALAN: Więc rodzaj selekcji.

232
00:09:55,900 --> 00:09:59,150
Ponieważ w tym problemu naprawdę zmniejszona
na to, że znowu nie wiem

233
00:09:59,150 --> 00:10:02,600
Znalazłem prąd najmniejszy, aż
I zostały sprawdzone wszystkie elementy cerować.

234
00:10:02,600 --> 00:10:08,050
Tak, Omega, powiedzmy, n,
po prostu przyszedł z jednym.

235
00:10:08,050 --> 00:10:09,300
Sort Insertion.

236
00:10:09,300 --> 00:10:12,370
Jeśli lista stanie się być sortowane
już, w najlepszym przypadku mamy tylko

237
00:10:12,370 --> 00:10:15,090
do jednego przejścia przez nią,
w którym momencie jesteśmy pewni.

238
00:10:15,090 --> 00:10:17,890
A następnie, że można powiedzieć, że
jest liniowa, na pewno.

239
00:10:17,890 --> 00:10:20,570
>> Co omega 1?

240
00:10:20,570 --> 00:10:23,790
Co, w najlepszym przypadku, może podjąć
stała liczba kroków?

241
00:10:23,790 --> 00:10:27,220
Więc linear search, jeśli po prostu miał szczęście
i element szukasz

242
00:10:27,220 --> 00:10:31,000
jest na samym początku listy,
jeśli to gdzie jesteś rozpoczęciem

243
00:10:31,000 --> 00:10:33,070
liniowe przechodzenie tej listy.

244
00:10:33,070 --> 00:10:35,180
>> I to jest prawda
wiele rzeczy.

245
00:10:35,180 --> 00:10:37,660
Na przykład, nawet binarny
wyszukiwanie jest omega z 1.

246
00:10:37,660 --> 00:10:40,310
Bo co, jeśli się naprawdę cholernie
szczęście i klaskać-zimnica w środku

247
00:10:40,310 --> 00:10:42,950
Twoja tablica jest liczba
szukasz?

248
00:10:42,950 --> 00:10:45,730
Więc można mieć szczęście tam, jak dobrze.

249
00:10:45,730 --> 00:10:49,190
>> Ten wreszcie omega n log n.

250
00:10:49,190 --> 00:10:52,573
Więc n log n, tak naprawdę nie
mówić o jeszcze, ale -

251
00:10:52,573 --> 00:10:53,300
>> PUBLICZNOŚCI: Scalanie rodzaju?

252
00:10:53,300 --> 00:10:53,960
>> DAVID MALAN: sort Merge.

253
00:10:53,960 --> 00:10:56,920
To był cliffhanger ostatniej chwili
gdzie zaproponowano, i pokazaliśmy

254
00:10:56,920 --> 00:10:58,600
wizualnie, że są algorytmy.

255
00:10:58,600 --> 00:11:02,470
I połączyć rodzaj tylko jeden taki
algorytm, który jest zasadniczo szybciej

256
00:11:02,470 --> 00:11:03,450
niż niektóre z tych innych facetów.

257
00:11:03,450 --> 00:11:07,800
Faktycznie, połączenie jest układ nie tylko w
najlepszym przypadku n n dziennika, w najgorszym

258
00:11:07,800 --> 00:11:09,460
Przypadek n n dziennika.

259
00:11:09,460 --> 00:11:14,540
A kiedy masz ten zbieżność
omega a big O jest to samo?

260
00:11:14,540 --> 00:11:17,310
Możemy właściwie opisać, że jak to, co jest
nazywa theta, choć to

261
00:11:17,310 --> 00:11:18,220
nieco mniej powszechne.

262
00:11:18,220 --> 00:11:21,730
Ale to po prostu oznacza, dwie granice,
w tym przypadku, są takie same.

263
00:11:21,730 --> 00:11:25,770
>> Więc połączyć rodzaju, co to
naprawdę sprowadzają się do nas?

264
00:11:25,770 --> 00:11:27,000
Cóż, pamiętam motywację.

265
00:11:27,000 --> 00:11:30,340
Pozwól mi wyciągnąć kolejną animację
nie patrzeć na ostatni raz.

266
00:11:30,340 --> 00:11:33,390
Ten jeden, ten sam pomysł, ale
jest trochę większy.

267
00:11:33,390 --> 00:11:36,160
I zamierzam iść do przodu i podkreślić
pierwsze - mamy coś w rodzaju wstawiania na

268
00:11:36,160 --> 00:11:39,410
w lewym górnym rogu, a następnie rodzaj selekcji,
sortowanie bąbelkowe, kilka innych rodzajów -

269
00:11:39,410 --> 00:11:42,670
shell i szybkie - że nie rozmawiał
o, i sterty i scalić rodzaju.

270
00:11:42,670 --> 00:11:47,090
>> Tak przynajmniej spróbować skupić wzrok na
trójce na lewo, a następnie

271
00:11:47,090 --> 00:11:49,120
scalić sortowanie po kliknięciu
ta zielona strzałka.

272
00:11:49,120 --> 00:11:51,900
Ale dam wszystkie z nich uruchomić, po prostu
daje poczucie różnorodności

273
00:11:51,900 --> 00:11:53,980
algorytmy, które istnieją w świecie.

274
00:11:53,980 --> 00:11:56,180
Mam zamiar dać ten bieg
w ciągu kilku sekund.

275
00:11:56,180 --> 00:11:59,640
A jeśli skupić oczy - pick
Algorytm, skupić się na nim przez zaledwie

276
00:11:59,640 --> 00:12:02,970
sekunda - zaczniesz widzieć
wzór, że to wdrożenie.

277
00:12:02,970 --> 00:12:04,530
>> Merge sort, zawiadomienia, jest wykonywana.

278
00:12:04,530 --> 00:12:06,430
Sort Heap, szybkie sortowanie, shell -

279
00:12:06,430 --> 00:12:09,480
więc wydaje się, wprowadziliśmy trzy
Najgorsze algorytmy w zeszłym tygodniu.

280
00:12:09,480 --> 00:12:12,960
Ale to dobrze, że jesteśmy tu dzisiaj, aby
zajrzeć rodzaju łączenia, który jest jednym z

281
00:12:12,960 --> 00:12:16,500
tym łatwiej ci jest patrzeć, nawet
choć pewnie będą stawać zdanie

282
00:12:16,500 --> 00:12:17,490
tylko trochę.

283
00:12:17,490 --> 00:12:21,130
Tutaj widzimy, jak wiele
sort wybór jest do bani.

284
00:12:21,130 --> 00:12:24,600
>> Ale w odwrotną stronę, to
bardzo łatwe do wdrożenia.

285
00:12:24,600 --> 00:12:28,160
A może za komplet P 3, to jeden z
Algorytmy wybrałeś do wdrożenia

286
00:12:28,160 --> 00:12:28,960
w standardowej wersji.

287
00:12:28,960 --> 00:12:30,970
Perfekcyjnie, idealnie poprawne.

288
00:12:30,970 --> 00:12:35,210
>> Ale znowu, jak n ma duże, jeśli
Decydując się na zastosowanie szybszego algorytmu

289
00:12:35,210 --> 00:12:39,020
jak połączyć rodzaju, kursy są w większe i
większe nakłady, kod jest tylko

290
00:12:39,020 --> 00:12:39,800
będzie działać szybciej.

291
00:12:39,800 --> 00:12:41,090
Twoja strona będzie działać lepiej.

292
00:12:41,090 --> 00:12:42,650
Użytkownicy będą szczęśliwsi.

293
00:12:42,650 --> 00:12:45,280
A więc są te efekty
faktycznie daje

294
00:12:45,280 --> 00:12:47,350
nam pewne głębsze myśli.

295
00:12:47,350 --> 00:12:49,990
>> Warto więc przyjrzeć się, co łączyć
sort faktycznie chodzi.

296
00:12:49,990 --> 00:12:52,992
Fajne jest to, że scalanie
sortowania jest właśnie to.

297
00:12:52,992 --> 00:12:56,300
To jest znowu to, co nazwaliśmy
pseudokod, pseudokod byt

298
00:12:56,300 --> 00:12:57,720
English-like składni.

299
00:12:57,720 --> 00:12:59,890
A prostota jest
rodzaju fascynujące.

300
00:12:59,890 --> 00:13:02,840
>> Tak więc na wejściu elementów n - tak, że
oznacza po prostu, tutaj jest tablica.

301
00:13:02,840 --> 00:13:04,000
Ma n rzeczy w nim.

302
00:13:04,000 --> 00:13:05,370
To wszystko, co mówimy nie.

303
00:13:05,370 --> 00:13:07,560
>> Jeśli n wynosi mniej niż 2, powrót.

304
00:13:07,560 --> 00:13:08,640
Więc to jest po prostu banalna sprawa.

305
00:13:08,640 --> 00:13:12,580
Jeśli n wynosi mniej niż 2, to oczywiście jest
1 lub 0, w tym przypadku rzeczą

306
00:13:12,580 --> 00:13:14,780
jest już posortowane lub nie istnieje,
tak po prostu wrócić.

307
00:13:14,780 --> 00:13:15,900
Nie ma nic do zrobienia.

308
00:13:15,900 --> 00:13:18,360
Więc to jest prosta sprawa, aby wyrwać się.

309
00:13:18,360 --> 00:13:20,110
>> Else, mamy trzy etapy.

310
00:13:20,110 --> 00:13:23,650
Sortowanie lewą połowę elementów, sortowania
Prawa połowa elementów,

311
00:13:23,650 --> 00:13:26,650
a następnie scalić posortowane połówki.

312
00:13:26,650 --> 00:13:29,400
Co ciekawe jest to, że
Jestem trochę punting, prawda?

313
00:13:29,400 --> 00:13:32,300
Jest to rodzaj okrągłego definicji
do tego algorytmu.

314
00:13:32,300 --> 00:13:35,986
W jakim sensie jest to algorytm tych
okólnik definicja?

315
00:13:35,986 --> 00:13:37,850
>> PUBLICZNOŚCI: [niesłyszalne].

316
00:13:37,850 --> 00:13:41,670
>> DAVID MALAN: Tak, mój algorytm sortowania,
dwa z jego etapów są "sort

317
00:13:41,670 --> 00:13:44,640
coś. "I tak, że błaga
pytanie, dobrze, co mam zamiar użyć

318
00:13:44,640 --> 00:13:46,460
sortować lewą połowę
i prawa połowa?

319
00:13:46,460 --> 00:13:49,600
A piękno jest to, że nawet jeśli
ponownie, to jest umysł-gięcie

320
00:13:49,600 --> 00:13:54,030
część potencjalnie można użyć tego samego
Algorytm sortowania lewą połowę.

321
00:13:54,030 --> 00:13:54,700
>> Ale chwileczkę.

322
00:13:54,700 --> 00:13:57,070
Kiedy powiedziałem, aby posortować
lewa połowa, jakie są dwa

323
00:13:57,070 --> 00:13:58,240
kroków będzie następny?

324
00:13:58,240 --> 00:14:00,550
Będziemy sortować lewą połowę
Lewa połowa i prawa

325
00:14:00,550 --> 00:14:01,420
połowa lewej połowie.

326
00:14:01,420 --> 00:14:04,430
Cholera, jak mam rozwiązać te dwa
połówki lub ćwiartki, a teraz?

327
00:14:04,430 --> 00:14:05,260
>> Ale to jest OK.

328
00:14:05,260 --> 00:14:07,830
Mamy algorytm sortowania tutaj.

329
00:14:07,830 --> 00:14:10,660
I choć może się martwić o
Najpierw jest to rodzaj infinite

330
00:14:10,660 --> 00:14:12,780
pętla, to cykl, który nigdy nie jest
się skończy - to będzie

331
00:14:12,780 --> 00:14:15,770
końca po co się dzieje?

332
00:14:15,770 --> 00:14:16,970
Gdy N jest mniejsze niż 2.

333
00:14:16,970 --> 00:14:19,180
Które w końcu się stanie,
bo jeśli trzymać połowę i

334
00:14:19,180 --> 00:14:23,020
zmniejszenie o połowę w połowę tych połówek, z pewnością
w końcu masz zamiar do końca

335
00:14:23,020 --> 00:14:25,350
up z zaledwie 1 lub 0 elementów.

336
00:14:25,350 --> 00:14:28,500
W tym momencie, ten algorytm
mówi gotowe.

337
00:14:28,500 --> 00:14:31,020
>> Więc prawdziwa magia w tym
Algorytm wydaje się być w

338
00:14:31,020 --> 00:14:33,470
że ostatni krok, łączenie.

339
00:14:33,470 --> 00:14:37,190
To prosty pomysł, po prostu połączenie dwóch
rzeczy, to jest to, co ostatecznie będzie

340
00:14:37,190 --> 00:14:40,920
co pozwala nam posortować tablicę,
powiedzmy, osiem elementów.

341
00:14:40,920 --> 00:14:44,410
Więc mam osiem więcej piłeczki antystresowe się
tutaj, osiem kawałków papieru, a jeden

342
00:14:44,410 --> 00:14:45,500
Google Glass -

343
00:14:45,500 --> 00:14:46,140
co mam zachować.

344
00:14:46,140 --> 00:14:46,960
>> [Śmiech]

345
00:14:46,960 --> 00:14:48,970
>> DAVID MALAN: Jeśli moglibyśmy się osiem
wolontariuszy, a zobaczymy, czy możemy

346
00:14:48,970 --> 00:14:51,430
grać to się, więc.

347
00:14:51,430 --> 00:14:52,500
Wow, OK.

348
00:14:52,500 --> 00:14:53,565
Informatyka jest miejsce zabawy.

349
00:14:53,565 --> 00:14:54,320
Dobrze.

350
00:14:54,320 --> 00:14:57,770
Więc jak można trzy,
Największy ręcznie tam.

351
00:14:57,770 --> 00:14:58,580
Cztery z tyłu.

352
00:14:58,580 --> 00:15:02,220
A co zrobimy ci
trzy w tym wierszu?

353
00:15:02,220 --> 00:15:03,390
I cztery z przodu.

354
00:15:03,390 --> 00:15:04,920
Więc osiem, dalej w górę.

355
00:15:04,920 --> 00:15:12,060
>> [Śmiech]

356
00:15:12,060 --> 00:15:13,450
>> DAVID MALAN: Jestem rzeczywiście
nie wiem co to jest.

357
00:15:13,450 --> 00:15:14,810
Czy kulki stres?

358
00:15:14,810 --> 00:15:16,510
Lampy biurko?

359
00:15:16,510 --> 00:15:18,650
Materiał?

360
00:15:18,650 --> 00:15:19,680
Internet?

361
00:15:19,680 --> 00:15:20,160
>> OK.

362
00:15:20,160 --> 00:15:21,310
Więc chodź na górę.

363
00:15:21,310 --> 00:15:22,310
Kto chce -

364
00:15:22,310 --> 00:15:23,570
zachować wymyślanie.

365
00:15:23,570 --> 00:15:24,240
Zobaczymy.

366
00:15:24,240 --> 00:15:26,460
A to stawia się w miejscu -

367
00:15:26,460 --> 00:15:27,940
jesteś w miejsce jednego.

368
00:15:27,940 --> 00:15:28,670
Uh-oh, poczekaj chwilę.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - oh, dobrze.

370
00:15:30,760 --> 00:15:31,310
Dobra, jesteśmy dobrzy.

371
00:15:31,310 --> 00:15:35,130
W porządku, więc wszyscy mają siedzibę,
ale nie na szybie Google.

372
00:15:35,130 --> 00:15:36,475
Pozwól mi stać w kolejce te góry.

373
00:15:36,475 --> 00:15:37,115
Jak masz na imię?

374
00:15:37,115 --> 00:15:37,440
>> Michelle: Michelle.

375
00:15:37,440 --> 00:15:38,090
>> DAVID MALAN: Michelle?

376
00:15:38,090 --> 00:15:42,000
Dobra, masz wyglądać
geek, czy to jest OK.

377
00:15:42,000 --> 00:15:44,625
Cóż, ja też, jak sądzę,
na chwilę.

378
00:15:44,625 --> 00:15:45,875
Dobrze, standby.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
Próbujemy wymyślić
przypadek użycia dla Google Glass, a my

381
00:15:50,950 --> 00:15:53,750
pomyślałem, że fajnie będzie po prostu zrobić
tego, kiedy ludzie są na scenie.

382
00:15:53,750 --> 00:15:57,120
Będziemy nagrywać świat
z ich perspektywy.

383
00:15:57,120 --> 00:15:58,410
Dobrze.

384
00:15:58,410 --> 00:15:59,830
Chyba nie, co Google przeznaczone.

385
00:15:59,830 --> 00:16:02,260
W porządku, jeśli nie masz nic przeciwko sobie
ta przez następne minuty niewygodnych,

386
00:16:02,260 --> 00:16:03,150
to byłoby wspaniałe.

387
00:16:03,150 --> 00:16:08,620
>> Dobrze, więc mamy tu tablicę
elementów, a tej tablicy, jak na

388
00:16:08,620 --> 00:16:11,480
kawałki papieru w tych ludzi "
ręce, jest obecnie bez sortowania.

389
00:16:11,480 --> 00:16:12,050
>> Michelle: Och, to takie dziwne.

390
00:16:12,050 --> 00:16:12,810
>> DAVID MALAN: To dość dużo losowo.

391
00:16:12,810 --> 00:16:15,760
A za chwilę, będziemy próbować
do wdrożenia seryjnej rodzaju razem

392
00:16:15,760 --> 00:16:17,950
i zobaczyć, gdzie ten klucz wgląd jest.

393
00:16:17,950 --> 00:16:21,970
I tu z rodzaju sztuczka seryjnej jest
coś, czego jeszcze nie przyjęły.

394
00:16:21,970 --> 00:16:24,030
My rzeczywiście potrzebują
dodatkowa przestrzeń.

395
00:16:24,030 --> 00:16:26,650
Więc co będzie szczególnie
Ciekawe jest to, że te

396
00:16:26,650 --> 00:16:29,270
Chłopaki będą się poruszać trochę
nieco, bo mam zamiar założyć, że

397
00:16:29,270 --> 00:16:31,880
jest dodatkowa tablica z miejsca,
powiedzieć, tuż za nimi.

398
00:16:31,880 --> 00:16:34,570
>> Więc jeśli są za ich fotelu,
to średnie array.

399
00:16:34,570 --> 00:16:36,960
Jeśli są one osadzone tutaj, to
Podstawowym array.

400
00:16:36,960 --> 00:16:40,170
Ale to jest zasób, który mamy
nie wykorzystała dotąd z bańki

401
00:16:40,170 --> 00:16:42,040
sort, z rodzaju selekcji,
z rodzaju wstawiania.

402
00:16:42,040 --> 00:16:44,600
Przypomnijmy, w ubiegłym tygodniu, wszyscy po prostu
rodzaj tasuje w miejscu.

403
00:16:44,600 --> 00:16:46,840
Nie używać żadnych dodatkowych pamięci.

404
00:16:46,840 --> 00:16:49,310
Zrobiliśmy miejsce dla ludzi,
ruchu ludzi wokół.

405
00:16:49,310 --> 00:16:50,580
>> Więc to jest klucz insight, too.

406
00:16:50,580 --> 00:16:53,410
Jest to kompromis, w ogóle w
informatyka, zasobów.

407
00:16:53,410 --> 00:16:55,800
Jeśli chcesz przyspieszyć coś
jak czas, będziesz

408
00:16:55,800 --> 00:16:56,900
zapłacić cenę.

409
00:16:56,900 --> 00:17:00,750
I jeden z tych cen jest bardzo często
przestrzeń, ilość pamięci lub twarde

410
00:17:00,750 --> 00:17:01,700
miejsca na dysku, które używasz.

411
00:17:01,700 --> 00:17:03,640
Albo, mówiąc, kwota
czasu programista.

412
00:17:03,640 --> 00:17:06,700
Ile czasu zajmuje Ci, ludzką,
faktycznie realizować kilka

413
00:17:06,700 --> 00:17:07,829
skomplikowany algorytm.

414
00:17:07,829 --> 00:17:09,760
Ale na dzisiaj, trade-off
jest czas i przestrzeń.

415
00:17:09,760 --> 00:17:11,930
>> Jeśli więc wy chłopaki możecie trzymać swoje
numerów, dzięki czemu możemy zobaczyć, że jesteś

416
00:17:11,930 --> 00:17:15,839
Rzeczywiście dopasowanie 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
Excellent.

418
00:17:16,599 --> 00:17:19,520
Więc mam zamiar spróbować zgrać
rzeczy, jeśli faceci mogą tylko

419
00:17:19,520 --> 00:17:21,800
za mną tutaj.

420
00:17:21,800 --> 00:17:26,650
>> Więc idę do realizacji w pierwszej kolejności,
Pierwszy etap Pseudokod, który jest

421
00:17:26,650 --> 00:17:29,440
na wejściu n elementów, jeśli n jest
mniej niż 2, a następnie wrócić.

422
00:17:29,440 --> 00:17:31,370
Oczywiście, że nie
apply, więc ruszamy dalej.

423
00:17:31,370 --> 00:17:33,340
Więc sortować lewą połowę elementów.

424
00:17:33,340 --> 00:17:36,220
To znaczy, mam zamiar skupić się moje
uwaga na chwilę na nich

425
00:17:36,220 --> 00:17:37,310
czterech facetów tutaj.

426
00:17:37,310 --> 00:17:39,774
Dobra, co mam dalej robić?

427
00:17:39,774 --> 00:17:40,570
>> PUBLICZNOŚCI: Sortowanie lewą połowę.

428
00:17:40,570 --> 00:17:42,780
>> DAVID MALAN: Więc teraz mam do sortowania
Lewa połowa tych facetów.

429
00:17:42,780 --> 00:17:45,580
Bo znowu, zakładają na siebie w
Celem jest, aby posortować lewą połowę.

430
00:17:45,580 --> 00:17:46,440
Jak ty to robisz?

431
00:17:46,440 --> 00:17:49,140
Wystarczy postępować zgodnie z instrukcjami, a nawet
choć robimy to ponownie.

432
00:17:49,140 --> 00:17:50,160
Więc sortować lewą połowę.

433
00:17:50,160 --> 00:17:52,030
Teraz jestem sortowania tych dwóch facetów.

434
00:17:52,030 --> 00:17:53,563
Co będzie dalej?

435
00:17:53,563 --> 00:17:54,510
>> PUBLICZNOŚCI: Sortowanie lewą połowę.

436
00:17:54,510 --> 00:17:55,460
>> DAVID MALAN: Sortowanie lewą połowę.

437
00:17:55,460 --> 00:18:00,680
Więc teraz to, to miejsce jest tutaj,
Jest to lista wielkości 1.

438
00:18:00,680 --> 00:18:01,365
A jakie jest twoje imię?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY: Księżna Daisy.

440
00:18:02,390 --> 00:18:03,690
>> DAVID MALAN: Księżna Daisy jest tutaj.

441
00:18:03,690 --> 00:18:07,470
A więc ona jest już posortowane, bo
Lista jest wielkości 1.

442
00:18:07,470 --> 00:18:09,490
Co mam dalej robić?

443
00:18:09,490 --> 00:18:13,680
OK, powrót, bo lista jest
Wielkość 1, która jest mniejsza niż 2.

444
00:18:13,680 --> 00:18:14,320
Więc jaki jest następny krok?

445
00:18:14,320 --> 00:18:17,490
A teraz masz do rodzaju
backtrack w swoim umyśle.

446
00:18:17,490 --> 00:18:19,340
>> Sortowanie prawą połowę, co jest -

447
00:18:19,340 --> 00:18:19,570
jak masz na imię?

448
00:18:19,570 --> 00:18:20,220
>> LINDA: Linda.

449
00:18:20,220 --> 00:18:20,980
>> DAVID MALAN: Linda.

450
00:18:20,980 --> 00:18:23,210
A więc co robimy teraz, że
mamy listę wielkości 1?

451
00:18:23,210 --> 00:18:24,440
>> PUBLICZNOŚCI: Powrót.

452
00:18:24,440 --> 00:18:24,760
>> DAVID MALAN: Ostrożnie.

453
00:18:24,760 --> 00:18:29,540
Wracamy po pierwsze, a teraz trzeci
step - rodzaj i gdybym od przedstawiają go

454
00:18:29,540 --> 00:18:33,490
obejmując dwa miejsca teraz, teraz ja
trzeba połączyć te dwa elementy.

455
00:18:33,490 --> 00:18:35,530
Więc teraz, niestety, elementy
są w porządku.

456
00:18:35,530 --> 00:18:39,920
Ale to jest, gdy proces scalania
zaczyna się przekonujące.

457
00:18:39,920 --> 00:18:42,410
>> Jeśli więc wy może bronić tylko
chwila, będę potrzebny, w

458
00:18:42,410 --> 00:18:44,170
chwila, krok za swoim krześle.

459
00:18:44,170 --> 00:18:46,480
A jeśli Linda, ponieważ 2 jest
mniejsza niż 4, to dlaczego nie zrobić

460
00:18:46,480 --> 00:18:48,130
przychodzisz pierwszy?

461
00:18:48,130 --> 00:18:48,690
Zostań tam.

462
00:18:48,690 --> 00:18:50,520
Więc Linda, przyjdziesz po pierwsze.

463
00:18:50,520 --> 00:18:53,820
>> Teraz w rzeczywistości, czy jest to po prostu tablica
może po prostu przesunąć ją w czasie rzeczywistym

464
00:18:53,820 --> 00:18:55,360
z tego krzesła do tego miejsca.

465
00:18:55,360 --> 00:18:57,770
Więc wyobraź sobie, że miała pewne stałe
Liczba kroków 1.

466
00:18:57,770 --> 00:18:58,480
A teraz -

467
00:18:58,480 --> 00:19:01,490
ale musimy umieścić w
Pierwsza lokalizacja tutaj.

468
00:19:01,490 --> 00:19:03,930
>> A teraz, jeśli można się wokół,
jak dobrze, idziemy do

469
00:19:03,930 --> 00:19:06,300
znajdować się w miejscu dwóch.

470
00:19:06,300 --> 00:19:09,120
I mimo, że to jest jak jest
biorąc chwilę, co jest ładne to

471
00:19:09,120 --> 00:19:14,710
że lewa połowa
Lewa połowa jest teraz posortowana.

472
00:19:14,710 --> 00:19:18,010
Tak więc to, co było kolejnym krokiem, jeśli teraz
przewinąć dalej w tej historii?

473
00:19:18,010 --> 00:19:18,980
>> PUBLICZNOŚCI: Right pół.

474
00:19:18,980 --> 00:19:19,900
>> DAVID MALAN: Sortowanie prawą połowę.

475
00:19:19,900 --> 00:19:21,320
Więc macie to zrobić, jak również.

476
00:19:21,320 --> 00:19:23,510
Więc jeśli można wstać
na chwilę?

477
00:19:23,510 --> 00:19:25,192
A jak masz na imię?

478
00:19:25,192 --> 00:19:25,540
>> JESS: Jess.

479
00:19:25,540 --> 00:19:25,870
>> DAVID MALAN: Jess.

480
00:19:25,870 --> 00:19:29,720
OK, więc Jess jest teraz w lewo
połowę prawą połowę.

481
00:19:29,720 --> 00:19:31,400
A więc ona jest lista wielkości 1.

482
00:19:31,400 --> 00:19:32,380
Ona oczywiście posortowane.

483
00:19:32,380 --> 00:19:33,070
A masz na imię?

484
00:19:33,070 --> 00:19:33,630
>> Michelle: Michelle.

485
00:19:33,630 --> 00:19:35,340
>> DAVID MALAN: Michelle jest oczywiście
lista wielkości 1.

486
00:19:35,340 --> 00:19:36,050
Ona już posortowane.

487
00:19:36,050 --> 00:19:38,690
Więc teraz dzieje się magia,
Proces scalania.

488
00:19:38,690 --> 00:19:39,790
Więc kto będzie na pierwszym miejscu?

489
00:19:39,790 --> 00:19:41,560
Oczywiście Michelle.

490
00:19:41,560 --> 00:19:43,280
Więc jeśli można podjechać z powrotem.

491
00:19:43,280 --> 00:19:47,090
Miejsca mamy do dyspozycji dla niej teraz
jest tuż za tym krześle tutaj.

492
00:19:47,090 --> 00:19:51,580
A teraz, jeśli można wrócić, jak również,
mamy teraz, aby być jasne, dwa

493
00:19:51,580 --> 00:19:53,810
połówek, każda o wymiarach 2 -

494
00:19:53,810 --> 00:19:57,090
i tylko obraz nędzy, jeśli
może zrobić trochę miejsca -

495
00:19:57,090 --> 00:19:59,780
jeden lewy pół tutaj, jeden
prawa połowa tutaj.

496
00:19:59,780 --> 00:20:01,160
>> Przewiń dalej w historii.

497
00:20:01,160 --> 00:20:02,270
Co krok to dalej?

498
00:20:02,270 --> 00:20:03,030
>> PUBLICZNOŚCI: Merge.

499
00:20:03,030 --> 00:20:04,160
>> DAVID MALAN: Więc teraz musimy połączyć.

500
00:20:04,160 --> 00:20:07,490
Więc OK, więc teraz, na szczęście, mamy
tylko uwolnił się cztery krzesła.

501
00:20:07,490 --> 00:20:11,480
Użyliśmy więc dwa razy więcej pamięci, ale
możemy dać klapać między

502
00:20:11,480 --> 00:20:12,330
dwie tablice.

503
00:20:12,330 --> 00:20:14,190
Więc jaki numer jest na pierwszym miejscu?

504
00:20:14,190 --> 00:20:14,850
Więc Michelle, oczywiście.

505
00:20:14,850 --> 00:20:16,680
Więc się wokół i podjąć
twoje miejsce tu.

506
00:20:16,680 --> 00:20:19,120
A potem numer 2 jest oczywiście
następny, więc tu przyjść.

507
00:20:19,120 --> 00:20:21,520
Numer 4, numer 6.

508
00:20:21,520 --> 00:20:23,390
I znów, choć jest
Trochę spaceru zaangażowany,

509
00:20:23,390 --> 00:20:26,010
naprawdę, to może się zdarzyć, natychmiast,
przesuwając jeden -

510
00:20:26,010 --> 00:20:26,880
OK, dobrze zagrane.

511
00:20:26,880 --> 00:20:28,350
>> [Śmiech]

512
00:20:28,350 --> 00:20:29,680
>> DAVID MALAN: I teraz jesteśmy
w bardzo dobrej formie.

513
00:20:29,680 --> 00:20:34,910
Lewa połowa całego
Wejście została posortowana.

514
00:20:34,910 --> 00:20:37,370
W porządku, więc ci ludzie mieli
Zaletą mojej -

515
00:20:37,370 --> 00:20:40,340
jak to w końcu wszystkie dziewczyny na
w lewo i wszyscy chłopcy na prawo?

516
00:20:40,340 --> 00:20:42,450
>> OK, więc chłopaki 'kolej.

517
00:20:42,450 --> 00:20:44,680
Więc nie będę Cię przez
kroki.

518
00:20:44,680 --> 00:20:46,550
Zobaczymy, czy możemy zastosować ponownie
same pseudokod.

519
00:20:46,550 --> 00:20:50,050
Jeśli chcesz iść do przodu i wstać,
a wy, pozwól mi dać mikrofon.

520
00:20:50,050 --> 00:20:52,990
Zobacz, czy nie można powtórzyć to, co
właśnie zrobiliśmy tu na

521
00:20:52,990 --> 00:20:53,880
Drugi koniec listy.

522
00:20:53,880 --> 00:20:59,530
Kto musi mówić pierwszy,
w oparciu o algorytm?

523
00:20:59,530 --> 00:21:03,210
Tak więc wyjaśnić, co robisz przed
Wprowadzenie jakichkolwiek ruchów stopy.

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1: Dobra, więc od
Jestem lewa połowa

525
00:21:05,930 --> 00:21:07,790
lewa połowa, wracam.

526
00:21:07,790 --> 00:21:08,730
Prawda?

527
00:21:08,730 --> 00:21:09,250
>> DAVID MALAN: Dobry.

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1: A potem -

529
00:21:10,350 --> 00:21:11,800
>> DAVID MALAN: Kto robi
mic przejść do następnego?

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1: Następny numer.

531
00:21:12,920 --> 00:21:14,720
>> Głośnik 2: Jestem więc prawa połowa
z lewej połowie

532
00:21:14,720 --> 00:21:17,830
lewa połowa, i wrócę.

533
00:21:17,830 --> 00:21:18,050
>> DAVID MALAN: Dobry.

534
00:21:18,050 --> 00:21:18,550
Powrót.

535
00:21:18,550 --> 00:21:21,855
Więc teraz, co dalej się z wami?

536
00:21:21,855 --> 00:21:23,740
>> Głośnik 2: Chcemy zobaczyć, kto jest mniejszy.

537
00:21:23,740 --> 00:21:24,200
>> DAVID MALAN: Dokładnie.

538
00:21:24,200 --> 00:21:24,940
Chcemy połączyć.

539
00:21:24,940 --> 00:21:27,590
Przestrzeń będziemy używać do łączenia
ty do, chociaż jest to

540
00:21:27,590 --> 00:21:30,250
oczywiście posortowane już, idziemy
się według tego samego algorytmu.

541
00:21:30,250 --> 00:21:31,560
Więc kto idzie z powrotem w pierwszej kolejności?

542
00:21:31,560 --> 00:21:35,720
3 Tak więc, a następnie 7.

543
00:21:35,720 --> 00:21:38,570
A teraz mic idzie
do tych facetów, OK?

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3: Jestem więc prawa połowa
lewa połowa, a mój n jest mniejsza niż

545
00:21:43,590 --> 00:21:45,048
1, więc mam zamiar przejść -

546
00:21:45,048 --> 00:21:46,380
>> DAVID MALAN: Dobry.

547
00:21:46,380 --> 00:21:49,450
>> GŁOŚNIK 4: Jestem prawa połowa
Prawa połowa prawej połowie, a ja jestem

548
00:21:49,450 --> 00:21:51,740
także jedna osoba, więc jestem
zamiar wrócić.

549
00:21:51,740 --> 00:21:52,990
Więc teraz możemy scalania.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3: Więc wracamy.

552
00:21:56,150 --> 00:21:57,160
>> DAVID MALAN: Więc idziesz do tyłu.

553
00:21:57,160 --> 00:21:59,200
Tak więc 5 idzie pierwszy, a następnie 8.

554
00:21:59,200 --> 00:22:01,240
A teraz publiczność, która jest
kroku musimy teraz przewinąć

555
00:22:01,240 --> 00:22:02,200
tyłu, aby w naszych umysłach?

556
00:22:02,200 --> 00:22:02,940
>> PUBLICZNOŚCI: Merge.

557
00:22:02,940 --> 00:22:07,270
>> DAVID MALAN: Połączenie lewej i prawej połowy
połowy początkowej lewej połowie.

558
00:22:07,270 --> 00:22:08,840
Więc teraz -

559
00:22:08,840 --> 00:22:10,520
i po prostu zrobić to jasne,
zrobić trochę miejsca

560
00:22:10,520 --> 00:22:11,690
między wami chłopaki.

561
00:22:11,690 --> 00:22:13,800
Więc teraz, że to dwie listy,
w lewo i prawo.

562
00:22:13,800 --> 00:22:18,320
Więc jak teraz połączyć Ci faceci w
przedni rząd siedzeń ponownie?

563
00:22:18,320 --> 00:22:19,600
>> 3 pierwszy.

564
00:22:19,600 --> 00:22:20,850
Następnie 5, oczywiście.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
Następnie 7, a teraz 8.

567
00:22:27,330 --> 00:22:28,710
OK, a teraz jesteśmy?

568
00:22:28,710 --> 00:22:29,650
>> PUBLICZNOŚCI: Nie wykonano.

569
00:22:29,650 --> 00:22:32,440
>> DAVID MALAN: Nie wykonano, ponieważ
oczywiście, jest jeszcze jeden krok pozostały.

570
00:22:32,440 --> 00:22:35,720
Ale znowu, powód używam tego
żargon jak "do tyłu w swoim umyśle,"

571
00:22:35,720 --> 00:22:37,160
to dlatego, że naprawdę
co się dzieje.

572
00:22:37,160 --> 00:22:39,610
Jedziemy przez te wszystkie etapy,
ale jesteśmy jakby zatrzymując

573
00:22:39,610 --> 00:22:42,480
Moment, nurkowanie w głąb
Algorytm, zatrzymując się na chwilę,

574
00:22:42,480 --> 00:22:45,840
nurkować głębiej w algorytmie, a
teraz musimy posortować od przewijania w naszym

575
00:22:45,840 --> 00:22:49,430
umysły i cofnąć wszystkie z tych warstw
że mamy jakby zawieszone.

576
00:22:49,430 --> 00:22:51,790
>> Więc teraz mamy dwie listy wielkości 4.

577
00:22:51,790 --> 00:22:54,790
Jeśli ludzie mogą stać się po raz ostatni
i zrobić trochę miejsca, żeby

578
00:22:54,790 --> 00:22:57,230
jasno, że jest to w lewo
połowa z oryginału,

579
00:22:57,230 --> 00:22:58,620
Prawa połowa oryginału.

580
00:22:58,620 --> 00:23:01,060
Kto jest pierwszy numer, że
trzeba pociągnąć do tyłu?

581
00:23:01,060 --> 00:23:01,870
Michelle, oczywiście.

582
00:23:01,870 --> 00:23:03,230
>> Więc stawiamy Michelle tutaj.

583
00:23:03,230 --> 00:23:05,080
A kto ma numer 2?

584
00:23:05,080 --> 00:23:06,440
Numer 2 jest on z powrotem także.

585
00:23:06,440 --> 00:23:07,800
Numer 3?

586
00:23:07,800 --> 00:23:08,510
Excellent.

587
00:23:08,510 --> 00:23:16,570
Numer 4, nr 5, nr 6,
numer 7 i nr 8.

588
00:23:16,570 --> 00:23:18,850
>> OK, więc czułem się dużo
kroków, na pewno.

589
00:23:18,850 --> 00:23:22,390
Ale teraz zobaczymy, jeśli nie możemy potwierdzić
jakby intuicyjnie, że to

590
00:23:22,390 --> 00:23:26,190
Algorytm gruntu, zwłaszcza
n ma naprawdę duże, jak widzieliśmy

591
00:23:26,190 --> 00:23:29,170
z animacjami, jest
zasadniczo szybciej.

592
00:23:29,170 --> 00:23:33,400
Więc mam prawo tego algorytmu, w najgorszym
przypadku, a nawet w najlepszym przypadku,

593
00:23:33,400 --> 00:23:36,160
jest duże O n razy log n.

594
00:23:36,160 --> 00:23:39,160
Oznacza to, że istnieje jakiś aspekt tego
algorytm, który podejmuje działania w N, ale

595
00:23:39,160 --> 00:23:43,110
jest jeszcze jeden aspekt gdzieś w
że iteracja, że ​​pętli, które

596
00:23:43,110 --> 00:23:44,410
podejmuje działania n log.

597
00:23:44,410 --> 00:23:49,154
Możemy umieścić nasz palec na co te
dwa numery na myśli?

598
00:23:49,154 --> 00:23:51,320
Cóż, w którym -

599
00:23:51,320 --> 00:23:54,160
Gdzie mic iść?

600
00:23:54,160 --> 00:23:58,660
>> SPEAKER 1: Jak zarejestrować n być
Podaje nam się na dwie -

601
00:23:58,660 --> 00:23:59,630
dzielenia przez dwa, zasadniczo.

602
00:23:59,630 --> 00:24:00,120
>> DAVID MALAN: Dokładnie.

603
00:24:00,120 --> 00:24:03,000
Za każdym razem, widzimy w każdym algorytmie tym samym
dotąd, nie był to wzór

604
00:24:03,000 --> 00:24:04,200
podziału, podziału, podziału.

605
00:24:04,200 --> 00:24:05,700
I to zazwyczaj zmniejszona
do czegoś, co jest

606
00:24:05,700 --> 00:24:07,100
logarytmiczne, logarytm o podstawie 2.

607
00:24:07,100 --> 00:24:10,180
Ale tak naprawdę to może być wszystko,
ale zarejestrować bazę 2.

608
00:24:10,180 --> 00:24:11,330
>> Teraz co z n?

609
00:24:11,330 --> 00:24:14,550
Widzę, że my niby dzieli cię
Chłopaki - dzieli się, dzieli się,

610
00:24:14,550 --> 00:24:15,910
dzieli się, dzieli Cię.

611
00:24:15,910 --> 00:24:18,760
Gdzie koniec pochodzi?

612
00:24:18,760 --> 00:24:19,810
>> Więc jest to połączenie.

613
00:24:19,810 --> 00:24:20,610
Bo o tym myśleć.

614
00:24:20,610 --> 00:24:25,420
Podczas scalania osiem osób razem,
przy czym połowa z nich to zestaw czterech

615
00:24:25,420 --> 00:24:27,770
a druga połowa jest inna
zestaw czterech, jak go

616
00:24:27,770 --> 00:24:28,820
o zrobieniu połączenia?

617
00:24:28,820 --> 00:24:30,830
Cóż, to zrobiliście
dość intuicyjnie.

618
00:24:30,830 --> 00:24:34,140
>> Ale jeśli zamiast tego zrobił to trochę więcej
metodycznie, mógłbym wskazać na

619
00:24:34,140 --> 00:24:38,090
lewej osoba najpierw moja lewa
strony, wskazał na osoby najbardziej na lewo

620
00:24:38,090 --> 00:24:42,080
z tego połowa z mojej prawej strony, a
tylko następnie przeszedł przez

621
00:24:42,080 --> 00:24:46,990
list, wskazując na najmniejszy element
za każdym razem, przesuwając palcem nad i

622
00:24:46,990 --> 00:24:48,970
W razie potrzeby na całej listy.

623
00:24:48,970 --> 00:24:51,890
Ale to, co jest kluczem o tym połączeniu
Proces jest mi porównanie tych par

624
00:24:51,890 --> 00:24:53,460
elementów.

625
00:24:53,460 --> 00:24:57,270
Z prawej połowy i z lewej
pół, nigdy nie jestem po wycofywania.

626
00:24:57,270 --> 00:25:00,570
>> Tak samo jest przy merge
nie więcej niż n kroków.

627
00:25:00,570 --> 00:25:03,250
A ile razy nie mam
zrobić to połączenie?

628
00:25:03,250 --> 00:25:07,150
Cóż, nie więcej niż n, a my po prostu
zobaczył, że z ostatecznego scalenia.

629
00:25:07,150 --> 00:25:13,120
I tak, jeśli zrobisz coś, że trwa
zaloguj kroki n n razy, lub odwrotnie,

630
00:25:13,120 --> 00:25:15,210
to będzie nam n razy log n.

631
00:25:15,210 --> 00:25:16,310
>> I dlaczego jest to lepsze?

632
00:25:16,310 --> 00:25:19,600
Cóż, jeśli już wiemy, że dziennik
n jest lepszy niż n - prawda?

633
00:25:19,600 --> 00:25:22,590
Widzieliśmy w poszukiwania binarnego, książkę telefoniczną
Przykładem, log n był zdecydowanie

634
00:25:22,590 --> 00:25:23,760
lepszy niż liniowy.

635
00:25:23,760 --> 00:25:28,420
To znaczy, n razy log n jest
zdecydowanie lepiej niż n razy inny

636
00:25:28,420 --> 00:25:30,390
n, AKA n do kwadratu.

637
00:25:30,390 --> 00:25:32,400
I to jest to, co w końcu poczuć.

638
00:25:32,400 --> 00:25:34,928
>> Więc wielkie brawa, jeśli
mogliśmy, dla tych facetów.

639
00:25:34,928 --> 00:25:38,920
>> [APPLAUSE]

640
00:25:38,920 --> 00:25:41,550
>> DAVID MALAN: A twoje prezenty rozstanie -
można zachować numery,

641
00:25:41,550 --> 00:25:44,010
jeśli chcesz.

642
00:25:44,010 --> 00:25:45,620
A prezent rozstanie, jak zwykle.

643
00:25:45,620 --> 00:25:47,290
Oh, a my wyślemy ci
footage, Michelle.

644
00:25:47,290 --> 00:25:48,343
Dziękuję.

645
00:25:48,343 --> 00:25:49,250
Dobrze.

646
00:25:49,250 --> 00:25:50,400
Pomóż sobie w piłkę na stres.

647
00:25:50,400 --> 00:25:54,110
>> I pozwól mi wyciągnąć, w międzyczasie,
nasz przyjaciel Rob Bowden do zaoferowania

648
00:25:54,110 --> 00:25:59,520
nieco inne spojrzenie na to,
ponieważ można myśleć o nich

649
00:25:59,520 --> 00:26:01,280
kroków dzieje się w nieco
inny sposób.

650
00:26:01,280 --> 00:26:04,750
W rzeczywistości, set-up na co Rob jest o
aby pokazać nam, zakłada, że ​​mamy

651
00:26:04,750 --> 00:26:09,030
już zrobione podzielenie się
big list do ośmiu małych list,

652
00:26:09,030 --> 00:26:10,570
każda z wielkości 1.

653
00:26:10,570 --> 00:26:13,350
>> Liczymy więc, zmieniając pseudokod
Trochę tylko do rodzaju dostać w

654
00:26:13,350 --> 00:26:15,320
Istotą sposobu łączenia prac.

655
00:26:15,320 --> 00:26:17,600
Ale czas pracy co
on o to, aby zrobić to jeszcze

656
00:26:17,600 --> 00:26:19,110
będzie taki sam.

657
00:26:19,110 --> 00:26:23,540
I znowu, set-up jest to, że on jest
rozpoczęła z ośmioma listami wielkości 1.

658
00:26:23,540 --> 00:26:27,730
Więc brakowało części, gdzie znajduje się
faktycznie wykonane dziennika n, log n, log n

659
00:26:27,730 --> 00:26:31,205
podzielenie wejścia.

660
00:26:31,205 --> 00:26:32,120
>> [PLAYBACK VIDEO]

661
00:26:32,120 --> 00:26:33,615
>> -To jest to na etapie pierwszym.

662
00:26:33,615 --> 00:26:38,270
W etapie drugim, wielokrotnie
łączy pary list.

663
00:26:38,270 --> 00:26:39,210
>> DAVID MALAN: Hm.

664
00:26:39,210 --> 00:26:41,270
Tylko dźwięk nadchodzi
z mojego komputera.

665
00:26:41,270 --> 00:26:42,520
Spróbujmy jeszcze raz.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> -Just dowolnie wybrać, które -
teraz mamy cztery listy.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
Dowiedz się wcześniej.

670
00:26:52,120 --> 00:26:53,040
>> DAVID MALAN: Nie pójdziemy.

671
00:26:53,040 --> 00:27:00,510
>> -Połączenie 108 i 15, to w końcu
się z listy 15, 108.

672
00:27:00,510 --> 00:27:07,170
Połączenie 50 i 4, ale
kończy się z 4, 50.

673
00:27:07,170 --> 00:27:12,990
Połączenie 8 i 42, to
kończy się z 8, 42.

674
00:27:12,990 --> 00:27:19,970
A połączenie 23 i 16, to
kończy się z 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> Teraz wszystkie nasze listy są wielkości 2.

676
00:27:23,270 --> 00:27:26,690
Należy zauważyć, że każdy z
cztery listy są sortowane.

677
00:27:26,690 --> 00:27:29,450
Tak więc możemy rozpocząć scalanie
par list ponownie.

678
00:27:29,450 --> 00:27:38,420
Połączenie 15 i 108, 4 i 50, to
najpierw wziąć 4, potem 15, a następnie

679
00:27:38,420 --> 00:27:41,500
50, a następnie 108.

680
00:27:41,500 --> 00:27:50,610
Połączenie 8, 42 i 16, 23, musimy najpierw podjąć
8, potem 16, potem 23,

681
00:27:50,610 --> 00:27:52,700
następnie 42.

682
00:27:52,700 --> 00:27:57,600
>> Więc teraz mamy tylko dwa wykazy wielkości
4, z których każdy jest sortowany.

683
00:27:57,600 --> 00:28:01,170
Więc teraz możemy połączyć te dwie listy.

684
00:28:01,170 --> 00:28:11,835
Po pierwsze, bierzemy 4, to bierzemy
8, a następnie weźmiemy 15, potem 16, a następnie

685
00:28:11,835 --> 00:28:19,456
23, potem 42, potem 50, a potem 108.

686
00:28:19,456 --> 00:28:19,872
>> [END PLAYBACK VIDEO]

687
00:28:19,872 --> 00:28:23,430
>> DAVID MALAN: Ponownie, zawiadomienie, że nigdy
dotknął dany filiżankę więcej niż jeden raz

688
00:28:23,430 --> 00:28:24,860
po pogłębianie poza nim.

689
00:28:24,860 --> 00:28:26,200
Tak że nigdy nie powtarza.

690
00:28:26,200 --> 00:28:29,850
Więc on jest zawsze w ruchu w bok,
i tam dostaliśmy n.

691
00:28:29,850 --> 00:28:33,290
>> Dlaczego nie pozwolił mi wyciągnąć jedną animację
że widzieliśmy już wcześniej, ale tym razem

692
00:28:33,290 --> 00:28:35,110
koncentrując się tylko na sortowanie korespondencji seryjnej.

693
00:28:35,110 --> 00:28:38,030
Pozwólcie mi iść do przodu i powiększyć
w to tutaj.

694
00:28:38,030 --> 00:28:42,530
Najpierw pozwól mi wybrać losową wejście,
powiększ to i można sortować of zobaczyć

695
00:28:42,530 --> 00:28:46,600
co braliśmy za pewnik, wcześniej,
scalić sort faktycznie robi.

696
00:28:46,600 --> 00:28:50,330
>> Tak więc zauważysz, że masz te połówki lub
te czwarte lub te ósmych

697
00:28:50,330 --> 00:28:53,140
Problem, który się nagle
zacząć brać dobrą formę.

698
00:28:53,140 --> 00:28:57,070
I w końcu, można zobaczyć na
bardzo end że bam,

699
00:28:57,070 --> 00:28:58,860
wszystko jest połączone ze sobą.

700
00:28:58,860 --> 00:29:01,690
>> To są tylko trzy różne
trwa na tej samej idei.

701
00:29:01,690 --> 00:29:05,980
Ale klucz wgląd, jak przepaści
i przejęcie w klasie pierwszej,

702
00:29:05,980 --> 00:29:10,640
było to, że zdecydowaliśmy się jakoś podzielić
Problem w coś wielkiego, w

703
00:29:10,640 --> 00:29:14,760
sort coś identyczne w duchu,
, ale mniejsze i mniejsze i mniejsze

704
00:29:14,760 --> 00:29:15,660
i mniejsze.

705
00:29:15,660 --> 00:29:18,420
>> Teraz kolejny świetny sposób, aby sortować z myślą
o nich, nawet jeśli nie jest to

706
00:29:18,420 --> 00:29:20,520
zamiar dać same intuicyjne
zrozumienie, jest

707
00:29:20,520 --> 00:29:21,640
Poniższa animacja.

708
00:29:21,640 --> 00:29:25,400
Więc to jest ktoś video ułożyła
że wiąże się inna

709
00:29:25,400 --> 00:29:29,970
dźwięków o różnych operacji na
sort wstawiania na sortowanie korespondencji seryjnej, a

710
00:29:29,970 --> 00:29:31,150
na kilka innych.

711
00:29:31,150 --> 00:29:32,330
Tak więc w chwili, mam zamiar uderzyć Odtwórz.

712
00:29:32,330 --> 00:29:33,600
To około minuty długości.

713
00:29:33,600 --> 00:29:37,410
I choć wciąż można zobaczyć
wzory dzieje, tym razem co możliwe

714
00:29:37,410 --> 00:29:41,420
również usłyszeć, jak te algorytmy są
wykonywania inaczej i

715
00:29:41,420 --> 00:29:43,950
nieco inne wzory.

716
00:29:43,950 --> 00:29:45,830
>> To jest swego rodzaju wprowadzenie.

717
00:29:45,830 --> 00:29:50,400
>> [TONES GRA]

718
00:29:50,400 --> 00:29:52,400
>> DAVID MALAN: To znowu próbuje
wstawić każdy element

719
00:29:52,400 --> 00:29:52,900
do których należy.

720
00:29:52,900 --> 00:29:54,628
To jest swego rodzaju bańki.

721
00:29:54,628 --> 00:30:10,097
>> [TONES GRA]

722
00:30:10,097 --> 00:30:13,630
>> DAVID MALAN: A można sortować z wyczuciem
jak stosunkowo mało pracy to robi

723
00:30:13,630 --> 00:30:15,834
na każdym etapie.

724
00:30:15,834 --> 00:30:20,470
To jest to, co tediousness brzmi.

725
00:30:20,470 --> 00:30:21,472
>> [TONES GRA]

726
00:30:21,472 --> 00:30:25,222
>> DAVID MALAN: To jest rodzaj selekcji,
gdzie wybrać element, który chcemy by

727
00:30:25,222 --> 00:30:28,845
przechodzi znowu i znowu i znowu
i umieszczenie go na początku.

728
00:30:28,845 --> 00:30:37,674
>> [TONES GRA]

729
00:30:37,674 --> 00:30:43,970
>> DAVID MALAN: To jest scalanie sort, które
można naprawdę zacząć czuć.

730
00:30:43,970 --> 00:30:51,810
>> [TONES GRA]

731
00:30:51,810 --> 00:30:54,770
>> [Śmiech]

732
00:30:54,770 --> 00:30:58,395
>> DAVID MALAN: Coś o nazwie gnome
sort, który nie patrzeli.

733
00:30:58,395 --> 00:31:13,630
>> [TONES GRA]

734
00:31:13,630 --> 00:31:17,910
>> DAVID MALAN: Więc pokaż mi, a teraz,
rozproszony, jak mam nadzieję, że to przez

735
00:31:17,910 --> 00:31:21,110
muzyka, czy mogę trochę poślizgu
Trochę matematyki tutaj.

736
00:31:21,110 --> 00:31:24,850
Więc jest czwarty sposób, że możemy
myśleć o tym, co to znaczy, to

737
00:31:24,850 --> 00:31:29,210
funkcje, aby być szybciej niż te, które
, które widzieliśmy wcześniej.

738
00:31:29,210 --> 00:31:32,470
A jeśli jesteś w trakcie z
background matematyki, można

739
00:31:32,470 --> 00:31:36,030
rzeczywiście wie, że może już
może uderzyć termin na tej techniki -

740
00:31:36,030 --> 00:31:40,400
mianowicie rekurencja, funkcja
że w jakiś sposób zwraca się.

741
00:31:40,400 --> 00:31:44,780
>> I znowu przypomnieć, że rodzaj scalania
pseudokod było cykliczne w sensie

742
00:31:44,780 --> 00:31:48,460
że jeden z sortowania Merge w krokach
było zadzwonić rodzaju -

743
00:31:48,460 --> 00:31:49,740
to jest sama.

744
00:31:49,740 --> 00:31:52,480
Ale na szczęście, bo mieliśmy
dzwoniąc rodzaju, lub połączyć rodzaju,

745
00:31:52,480 --> 00:31:55,880
specjalnie na mniejsze i mniejsze
i mniejszych list, w końcu

746
00:31:55,880 --> 00:32:00,005
dno dzięki czemu będziemy nazywać
wariant podstawowy, zakodowane tak, że

747
00:32:00,005 --> 00:32:04,270
powiedział, że jeśli lista jest mała, mniejsza niż 2
w tym przypadku, po prostu wrócić natychmiast.

748
00:32:04,270 --> 00:32:07,550
Jeśli nie ma tego szczególnego przypadku,
Algorytm nigdy by bottom out,

749
00:32:07,550 --> 00:32:11,010
i może rzeczywiście dostać się do
nieskończonej pętli naprawdę zawsze.

750
00:32:11,010 --> 00:32:14,330
>> Ale załóżmy, że chcemy teraz szuka
niektóre numery na to, ponownie, stosując n

751
00:32:14,330 --> 00:32:15,660
jako wielkości wejściowych.

752
00:32:15,660 --> 00:32:18,680
A ja chciałem zapytać, co jest
Całkowity czas zaangażowany w

753
00:32:18,680 --> 00:32:19,800
działa sortowanie korespondencji seryjnej?

754
00:32:19,800 --> 00:32:22,960
Lub, bardziej ogólnie, co jest
Koszt to w czasie?

755
00:32:22,960 --> 00:32:24,730
>> Cóż to jest dość łatwe do ustalenia, że.

756
00:32:24,730 --> 00:32:29,010
Jeśli n jest mniejsze niż 2, czas zaangażowany
w sortowania n elementów,

757
00:32:29,010 --> 00:32:30,480
w którym n oznacza 2, 0..

758
00:32:30,480 --> 00:32:31,410
Bo po prostu wrócić.

759
00:32:31,410 --> 00:32:32,510
Nie ma wiele do zrobienia.

760
00:32:32,510 --> 00:32:35,660
Teraz prawdopodobnie, być może jest to jeden krok lub dwa
kroki, aby dowiedzieć się ilość

761
00:32:35,660 --> 00:32:38,420
działa, ale na tyle blisko 0, że
Mam zamiar powiedzieć nie praca jest

762
00:32:38,420 --> 00:32:40,940
wymagane, jeśli lista jest tak mała,
być nieciekawe.

763
00:32:40,940 --> 00:32:42,580
>> Ale ta sprawa jest interesująca.

764
00:32:42,580 --> 00:32:47,320
Cykliczne sprawa była gałąź
pseudokod, który powiedział jeszcze, sort

765
00:32:47,320 --> 00:32:52,000
lewa połowa, uporządkować prawo
pół, połączyć dwie połówki.

766
00:32:52,000 --> 00:32:55,530
Teraz dlaczego to wyrażenie
stanowią, że koszty?

767
00:32:55,530 --> 00:32:58,690
Cóż, T n oznacza po prostu
czas, aby posortować n elementów.

768
00:32:58,690 --> 00:33:03,070
I wtedy na prawej stronie
znak równości tam, T n podzielona

769
00:33:03,070 --> 00:33:06,600
przez 2 odnosi się do kosztów co?

770
00:33:06,600 --> 00:33:07,570
Sortowanie lewą połowę.

771
00:33:07,570 --> 00:33:10,990
Inne T n dzieli się przez 2 jest
prawdopodobnie odnosi się do kosztów

772
00:33:10,990 --> 00:33:12,390
sortować prawą połowę.

773
00:33:12,390 --> 00:33:14,590
>> A potem n Plus?

774
00:33:14,590 --> 00:33:15,420
Czy połączenie.

775
00:33:15,420 --> 00:33:19,120
Bo jeśli masz dwie listy, jedna z
n rozmiar ponad 2, a drugi od wielkości n

776
00:33:19,120 --> 00:33:22,580
ponad 2, trzeba przede wszystkim dotykać
każdy z tych elementów, tak jak Rob

777
00:33:22,580 --> 00:33:24,990
dotknęła każdego z kubków, a tylko
Jak wskazaliśmy w każdym z

778
00:33:24,990 --> 00:33:26,310
Wolontariusze na scenie.

779
00:33:26,310 --> 00:33:28,790
Więc n jest koszt połączenia.

780
00:33:28,790 --> 00:33:31,780
>> Teraz, niestety, ta formuła
jest również sama cykliczne.

781
00:33:31,780 --> 00:33:36,390
Więc jeśli zadał pytanie, czy n jest, powiedzmy,
16, jeżeli jest 16 osób na scenie

782
00:33:36,390 --> 00:33:40,670
lub 16 kubków w filmie, jak wiele razem
kroki trzeba zrobić, aby posortować je

783
00:33:40,670 --> 00:33:41,550
z rodzaju korespondencji seryjnej?

784
00:33:41,550 --> 00:33:45,790
To nie jest właściwie oczywista odpowiedź,
bo teraz masz do rodzaju

785
00:33:45,790 --> 00:33:48,500
rekurencyjnie odebrać tę formułę.

786
00:33:48,500 --> 00:33:51,190
>> Ale to jest OK, bo chciałbym zaproponować
które należy wykonać następujące czynności.

787
00:33:51,190 --> 00:33:56,670
Czas zaangażowany do sortowania 16 osób lub
16 filiżanek będzie reprezentowany

788
00:33:56,670 --> 00:33:58,020
ogólnie T z dnia 16.

789
00:33:58,020 --> 00:34:01,400
Ale równa według naszych
Poprzedni wzór, 2 razy więcej niż

790
00:34:01,400 --> 00:34:04,780
Czas potrzebny do sortowania
8 filiżanek i 16.

791
00:34:04,780 --> 00:34:08,590
I znowu plus 16 jest czas, aby połączyć,
i dwa razy T z 8 jest

792
00:34:08,590 --> 00:34:10,790
czas, aby uporządkować lewą połowę i prawo pół.

793
00:34:10,790 --> 00:34:11,989
>> Ale znowu, to nie wystarczy.

794
00:34:11,989 --> 00:34:13,210
Mamy nurkować głębiej.

795
00:34:13,210 --> 00:34:16,409
To oznacza, że ​​musimy odpowiedzieć
pytanie, co to jest T z 8?

796
00:34:16,409 --> 00:34:19,610
Cóż T z 8 jest tylko 2
razy T z 4 plus 8.

797
00:34:19,610 --> 00:34:20,520
No i co w T 4?

798
00:34:20,520 --> 00:34:23,780
T 4 jest zaledwie 2 razy T z 2 plus 4.

799
00:34:23,780 --> 00:34:25,489
Cóż, co T z 2?

800
00:34:25,489 --> 00:34:29,030
T z 2 znajduje się zaledwie 2 razy T 1 plus 2.

801
00:34:29,030 --> 00:34:31,940
>> I znowu jesteśmy trochę się
tkwi w tym cyklu.

802
00:34:31,940 --> 00:34:34,790
Ale to jest o trafienie, które
tzw. wariant podstawowy.

803
00:34:34,790 --> 00:34:37,310
Bo co to T 1, nie twierdzimy?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
Więc teraz w końcu możemy działać wstecz.

806
00:34:39,730 --> 00:34:44,290
>> Jeśli T 1 jest 0, mogę teraz wrócić do jednego
wiersz do tego gościa tutaj, i ja mogę

807
00:34:44,290 --> 00:34:46,330
wtyczka w 0 dla T 1.

808
00:34:46,330 --> 00:34:51,770
Więc to znaczy, że jest równy 2 razy zero,
zwie 0 oraz 2.

809
00:34:51,770 --> 00:34:53,739
I tak, że całe wyrażenie jest 2.

810
00:34:53,739 --> 00:34:58,740
>> Teraz, jeśli biorę T z 2, którego odpowiedź
wynosi 2, podłącz go do środkowej linii, T

811
00:34:58,740 --> 00:35:02,740
4, że daje mi 2 razy
2 oraz 4, 8, tak.

812
00:35:02,740 --> 00:35:07,080
Jeśli następnie podłączyć 8 do poprzedniego
Linia, która daje mi 2 razy 8, 16.

813
00:35:07,080 --> 00:35:12,470
A jeśli to nadal, że z
24, dodając w 16, to w końcu się

814
00:35:12,470 --> 00:35:13,820
wartość 64.

815
00:35:13,820 --> 00:35:18,480
>> Teraz tego rodzaju w sobie od mówi
nic do notacji n,

816
00:35:18,480 --> 00:35:20,700
duże O, omega, że ​​mamy
mówił o.

817
00:35:20,700 --> 00:35:24,890
Ale okazuje się, że 64 jest w istocie
16, wielkości wejściowych,

818
00:35:24,890 --> 00:35:27,110
zaloguj bazy 2 z 16.

819
00:35:27,110 --> 00:35:30,200
A jeśli jest to trochę zna, tylko
wracam, i będzie ona wrócić

820
00:35:30,200 --> 00:35:30,700
do Ciebie w końcu.

821
00:35:30,700 --> 00:35:33,775
Jeśli jest to podstawa log 2, to jak 2
podniesiony do co daje 16?

822
00:35:33,775 --> 00:35:36,380
Och, to jest 4, więc jest 16 razy 4.

823
00:35:36,380 --> 00:35:39,380
>> I znowu, nie jest to wielka sprawa, jeśli to
jest jakby zamglony pamięci teraz.

824
00:35:39,380 --> 00:35:43,720
Ale na razie się na wierze
że 16 log 16 jest 64.

825
00:35:43,720 --> 00:35:46,590
I tak naprawdę, z tego prostego rozsądku
sprawdzić, mamy potwierdzone -

826
00:35:46,590 --> 00:35:48,250
ale nie udowodnione formalnie -

827
00:35:48,250 --> 00:35:52,800
, że czas pracy seryjnej
sort jest rzeczywiście n log n.

828
00:35:52,800 --> 00:35:53,790
>> Więc nie jest źle.

829
00:35:53,790 --> 00:35:57,260
To zdecydowanie lepiej niż
Algorytmy, które widzieliśmy do tej pory, i

830
00:35:57,260 --> 00:36:00,710
to dlatego, że mamy wykorzystała jeden,
technika zwana rekurencji.

831
00:36:00,710 --> 00:36:03,880
Ale bardziej interesujące niż to, że
Pojęcie Dziel i rządź.

832
00:36:03,880 --> 00:36:07,460
Ponownie, naprawdę tydzień 0 rzeczy, które
nawet teraz jest powtarzające się w

833
00:36:07,460 --> 00:36:08,740
bardziej przekonujące sposób.

834
00:36:08,740 --> 00:36:11,750
>> Teraz trochę zabawnych ćwiczeń, jeśli masz
nigdy nie zrobił tego - i prawdopodobnie

835
00:36:11,750 --> 00:36:14,660
nie ma, bo jakby normalny
ludzie nie sądzę, aby to zrobić.

836
00:36:14,660 --> 00:36:20,650
Ale jeśli pójdę do google.com i jeśli
Chcę dowiedzieć się czegoś o

837
00:36:20,650 --> 00:36:22,356
rekurencja, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [Śmiech]

840
00:36:29,058 --> 00:36:32,030
[Śmiech]

841
00:36:32,030 --> 00:36:33,385
DAVID MALAN: Bad żart powoli rozprzestrzenia.

842
00:36:33,385 --> 00:36:34,450
[Śmiech]

843
00:36:34,450 --> 00:36:36,970
DAVID MALAN: wypadek, to tam.

844
00:36:36,970 --> 00:36:38,710
I nie pisze to źle,
i jest żart.

845
00:36:38,710 --> 00:36:40,810
Dobrze.

846
00:36:40,810 --> 00:36:42,950
Wyjaśnij ludzie obok ciebie, jeśli
nie dość kliknął jeszcze.

847
00:36:42,950 --> 00:36:47,650
Ale rekursji, bardziej ogólnie, odnosi
w procesie funkcji wywołującej

848
00:36:47,650 --> 00:36:51,430
sama, lub bardziej ogólnie, dzieląc
Problem w coś, co może być

849
00:36:51,430 --> 00:36:56,220
rozwiązany fragmentaryczne rozwiązując identyczne
Problemy reprezentatywne.

850
00:36:56,220 --> 00:36:58,400
>> Cóż, zmiana biegów
na chwilę.

851
00:36:58,400 --> 00:37:00,840
Chcemy do końca niektórych Cliffhangers,
więc zacznijmy ustawić

852
00:37:00,840 --> 00:37:05,870
etap, przez kilka minut,
na bardzo prosty pomysł -

853
00:37:05,870 --> 00:37:07,620
że wymiany dwóch elementów, prawda?

854
00:37:07,620 --> 00:37:10,040
Wszystkie te algorytmy byliśmy
mówi o ostatnich kilku

855
00:37:10,040 --> 00:37:12,420
Wykłady obejmują niektóre
rodzaj wymiany.

856
00:37:12,420 --> 00:37:14,630
Dzisiaj to uwidoczniono przez nich coraz
się z krzeseł i

857
00:37:14,630 --> 00:37:18,570
chodzą, ale w kodzie, chcielibyśmy
po prostu wziąć element z jednej tablicy

858
00:37:18,570 --> 00:37:20,370
i plusk do innego.

859
00:37:20,370 --> 00:37:21,880
>> Więc jak to zabrać?

860
00:37:21,880 --> 00:37:24,850
Cóż, pozwól mi pójść dalej i napisać
szybkie Program tutaj.

861
00:37:24,850 --> 00:37:31,600
Mam zamiar iść do przodu i robić
To, co poniżej.

862
00:37:31,600 --> 00:37:33,910
Nazwijmy to -

863
00:37:33,910 --> 00:37:38,070
Co chcemy nazwać ten jeden?

864
00:37:38,070 --> 00:37:38,650
>> W rzeczywistości, nie ma.

865
00:37:38,650 --> 00:37:39,420
Pozwól mi cofnąć.

866
00:37:39,420 --> 00:37:41,220
Nie chcę, aby to zrobić
cliffhanger jeszcze.

867
00:37:41,220 --> 00:37:42,270
Będzie psuć zabawy.

868
00:37:42,270 --> 00:37:43,600
Zróbmy to w zamian.

869
00:37:43,600 --> 00:37:47,430
>> Załóżmy, że chcę napisać trochę
Program, a teraz obejmuje to

870
00:37:47,430 --> 00:37:48,700
Pomysł rekursji.

871
00:37:48,700 --> 00:37:50,370
I niby ma przed siebie tam.

872
00:37:50,370 --> 00:37:51,420
Zamierzam wykonać następujące czynności.

873
00:37:51,420 --> 00:38:00,220
>> Po pierwsze, szybkie m.in. standardowej io.h,
jak również warte wymienienia są z cs50.h.

874
00:38:00,220 --> 00:38:03,200
A potem mam zamiar iść do przodu
i stwierdzenie nieważności główny int

875
00:38:03,200 --> 00:38:04,360
w zwykły sposób.

876
00:38:04,360 --> 00:38:07,920
Zdałem sobie sprawę, jakie misnamed plik, tak
Pozwólcie mi dodać rozszerzenie. c tutaj tak

877
00:38:07,920 --> 00:38:09,510
że możemy go skompilować poprawnie.

878
00:38:09,510 --> 00:38:10,970
Uruchom tę funkcję.

879
00:38:10,970 --> 00:38:13,290
>> A funkcja chcę napisać, dość
po prostu, to taki, który zwraca

880
00:38:13,290 --> 00:38:16,210
Użytkownik w szeregu, a następnie dodaje się
wszystkie numery między który

881
00:38:16,210 --> 00:38:19,920
liczba i, powiedzmy, 0.

882
00:38:19,920 --> 00:38:22,510
Więc najpierw mam zamiar iść do przodu
i zadeklarować int n.

883
00:38:22,510 --> 00:38:24,760
Następnie skopiować kod, który
używaliśmy przez jakiś czas.

884
00:38:24,760 --> 00:38:26,660
Podczas gdy coś jest prawdą.

885
00:38:26,660 --> 00:38:28,000
Wrócę do tego za chwilę.

886
00:38:28,000 --> 00:38:29,010
>> Co chcę zrobić?

887
00:38:29,010 --> 00:38:33,460
Chcę powiedzieć printf pozytywne
całkowita proszę.

888
00:38:33,460 --> 00:38:36,130
A potem mam zamiar
powiedzieć n ma dostać int.

889
00:38:36,130 --> 00:38:38,800
Więc znowu, jakiś kod boilerplate
które używaliśmy wcześniej.

890
00:38:38,800 --> 00:38:40,810
I zamierzam to zrobić
gdy n jest mniejsze niż 1.

891
00:38:40,810 --> 00:38:44,120
Tak więc będzie to zapewnić, że użytkownik
daje mi całkowitą dodatnią.

892
00:38:44,120 --> 00:38:45,490
>> A teraz mam zamiar wykonać następujące czynności.

893
00:38:45,490 --> 00:38:51,020
Chcę dodać wszystkie numery
między 1 a i n, lub 0, a n,

894
00:38:51,020 --> 00:38:52,570
równoważnie, aby uzyskać całkowitą sumę.

895
00:38:52,570 --> 00:38:55,100
Tak duży symbol sigma
że można przypomnieć.

896
00:38:55,100 --> 00:38:59,050
Więc mam zamiar to zrobić pierwszego powołania
Funkcja o nazwie Sigma,

897
00:38:59,050 --> 00:39:06,030
przechodzącej w n, a następnie zamierzam
powiedzieć, printf, odpowiedź jest tuż, tuż.

898
00:39:06,030 --> 00:39:08,180
>> Tak w skrócie, mam i
int od użytkownika.

899
00:39:08,180 --> 00:39:09,280
I zapewniają, że to pozytywne.

900
00:39:09,280 --> 00:39:12,700
Oświadczam zmienną odpowiedź
int typ i przechowywać w nim powrót

901
00:39:12,700 --> 00:39:15,610
wartość sigma, przekazując n jako wejście.

902
00:39:15,610 --> 00:39:17,060
A potem wydrukować tę odpowiedź.

903
00:39:17,060 --> 00:39:19,550
>> Niestety, choć brzmi sigma
jak coś, co może być w

904
00:39:19,550 --> 00:39:24,040
plik math.h, jego oświadczenie,
to nie jest w rzeczywistości.

905
00:39:24,040 --> 00:39:24,690
Więc to jest OK.

906
00:39:24,690 --> 00:39:26,170
Można zaimplementować ten sam.

907
00:39:26,170 --> 00:39:29,160
Idę do realizacji funkcji o nazwie
sigma, a to zajmie

908
00:39:29,160 --> 00:39:29,900
parametr -

909
00:39:29,900 --> 00:39:32,100
niech po prostu nazwać to m, po prostu
tak jest inaczej.

910
00:39:32,100 --> 00:39:35,910
A potem się tutaj, mam zamiar powiedzieć,
oraz, jeżeli m jest mniejsze niż 1 - jest to

911
00:39:35,910 --> 00:39:38,180
bardzo nieciekawy program.

912
00:39:38,180 --> 00:39:41,700
Więc mam zamiar iść do przodu i
natychmiast powrócić 0.

913
00:39:41,700 --> 00:39:45,920
To po prostu nie ma sensu, aby dodać wszystkie
numery od 1 do m, jeżeli m

914
00:39:45,920 --> 00:39:48,470
to samo 0 lub ujemna.

915
00:39:48,470 --> 00:39:50,900
>> A potem mam zamiar iść do przodu
i zrobić to bardzo iteracyjnie.

916
00:39:50,900 --> 00:39:53,090
Mam zamiar zrobić ten rodzaj starej szkoły,
i mam zamiar iść do przodu

917
00:39:53,090 --> 00:39:57,150
i powiedzieć, że będę
deklarowania kwoty do 0.

918
00:39:57,150 --> 00:39:59,630
Wtedy będę mieć
dla pętli int -

919
00:39:59,630 --> 00:40:02,820
i pozwól mi zrobić, to dopasować nasze
Kod dystrybucji, więc masz kopię

920
00:40:02,820 --> 00:40:07,500
w domu. int i dostaje 1 na maksymalnie
I jest mniejsza lub równa m.

921
00:40:07,500 --> 00:40:09,430
i Plus Plus.

922
00:40:09,430 --> 00:40:11,430
A następnie wewnątrz tego pętli for -

923
00:40:11,430 --> 00:40:12,440
Jesteśmy prawie na miejscu -

924
00:40:12,440 --> 00:40:15,810
suma dostaje sumę plus 1.

925
00:40:15,810 --> 00:40:17,670
A potem mam zamiar powrócić sumę.

926
00:40:17,670 --> 00:40:19,420
>> Więc zrobiłem to szybko,
całkiem prawda.

927
00:40:19,420 --> 00:40:22,775
Ale znowu, główną funkcją jest dość
proste, oparte na kodzie mamy

928
00:40:22,775 --> 00:40:23,190
napisane do tej pory.

929
00:40:23,190 --> 00:40:25,610
Używa podwójną pętlę, aby uzyskać pozytywne
int od użytkownika.

930
00:40:25,610 --> 00:40:29,870
I następnie przekazać tę int do nowej funkcji
nazywane sigma, wzywając go, ponownie, n.

931
00:40:29,870 --> 00:40:33,100
I przechowywania wartości zwracanej, odpowiedź
z czarnej skrzynki obecnie

932
00:40:33,100 --> 00:40:35,460
Wiadomo jak Sigma, w zmiennym
nazywa odpowiedź.

933
00:40:35,460 --> 00:40:36,580
Następnie wydrukować go.

934
00:40:36,580 --> 00:40:39,090
>> Jeśli teraz kontynuować historię,
jak jest sigma realizowane?

935
00:40:39,090 --> 00:40:40,840
Proponuję wprowadzić w następujący sposób.

936
00:40:40,840 --> 00:40:43,560
Po pierwsze, trochę kontroli błędów
, aby upewnić się, że użytkownik nie jest

937
00:40:43,560 --> 00:40:46,480
bawić się ze mną i przekazując
niektóre negatywne lub 0 wartość.

938
00:40:46,480 --> 00:40:49,710
Potem deklaruje zmienną o nazwie
Podsumowując i ustawić ją na 0.

939
00:40:49,710 --> 00:40:55,910
>> I teraz zaczynają się poruszać z i równa
1, aż do i włącznie m,

940
00:40:55,910 --> 00:41:00,130
bo chcę to wszystko
numery od jednego do m włącznie.

941
00:41:00,130 --> 00:41:04,350
A w środku tego dla pętli, po prostu zrobić
suma dostaje cokolwiek to jest teraz, oraz

942
00:41:04,350 --> 00:41:08,900
wartość i.

943
00:41:08,900 --> 00:41:10,370
Plus wartość i.

944
00:41:10,370 --> 00:41:14,090
>> Tak na marginesie, jeśli nie widziałem tego
wcześniej, istnieje pewne syntaktyczne cukru

945
00:41:14,090 --> 00:41:14,870
W przypadku tej linii.

946
00:41:14,870 --> 00:41:21,120
Mogę przepisać to jako Plus równa i,
tylko zapisać sobie kilka klawiszy

947
00:41:21,120 --> 00:41:22,570
i spojrzeć trochę chłodniej.

948
00:41:22,570 --> 00:41:23,140
Ale to wszystko.

949
00:41:23,140 --> 00:41:24,660
To funkcjonalnie samo.

950
00:41:24,660 --> 00:41:26,710
>> Niestety, ten kod-tych
nie zamierza skompilować jeszcze.

951
00:41:26,710 --> 00:41:31,600
Jeśli uruchomić make sigma 0, jak am
I będzie się krzyknął?

952
00:41:31,600 --> 00:41:33,473
Co to będzie nie podoba?

953
00:41:33,473 --> 00:41:35,740
>> PUBLICZNOŚCI: [niesłyszalne].

954
00:41:35,740 --> 00:41:37,800
>> DAVID MALAN: Tak, nie ogłoszono
Funkcja do góry, tak?

955
00:41:37,800 --> 00:41:40,590
C jest głupie, w to, że tylko
robi to, co możesz powiedzieć to zrobić, a ty

956
00:41:40,590 --> 00:41:41,880
trzeba to zrobić w tej kolejności.

957
00:41:41,880 --> 00:41:45,910
I tak, jeśli uderzę Wpisz tutaj, będę
dostać ostrzeżenie o sigma niejawny

958
00:41:45,910 --> 00:41:46,860
deklaracja.

959
00:41:46,860 --> 00:41:48,120
>> Oh nie, to problem.

960
00:41:48,120 --> 00:41:50,370
Mogę iść do góry, a ja mogę
powiedzieć, wszystko w porządku, poczekaj.

961
00:41:50,370 --> 00:41:54,240
Sigma jest funkcja, która zwraca
int i oczekuje

962
00:41:54,240 --> 00:41:56,620
int jako wejścia, średnikiem.

963
00:41:56,620 --> 00:41:59,550
Albo może umieścić całą funkcję
nad głównym, ale w ogóle, ja bym

964
00:41:59,550 --> 00:42:02,260
odradzam, że ponieważ jest to
miło zawsze głównym na górze, aby

965
00:42:02,260 --> 00:42:06,310
można nurkować w prawo i wie, co
Program robi czytając główny pierwszy.

966
00:42:06,310 --> 00:42:07,930
>> Więc teraz pozwól mi wyczyścić ekran.

967
00:42:07,930 --> 00:42:09,330
Sigma 0 Remake.

968
00:42:09,330 --> 00:42:10,340
Wszystko wydaje się sprawdzić.

969
00:42:10,340 --> 00:42:11,970
Pozwólcie mi biegać sigma 0.

970
00:42:11,970 --> 00:42:12,770
Pozytywna inter.

971
00:42:12,770 --> 00:42:15,580
Dam mu numer
3 keep it simple.

972
00:42:15,580 --> 00:42:18,710
Tak, że powinna dać mi 3
Plus 2 plus 1, czyli 6.

973
00:42:18,710 --> 00:42:20,750
Wejdź i rzeczywiście mam 6.

974
00:42:20,750 --> 00:42:21,820
>> Mogę zrobić coś większego -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
Podobnie jak stycznej, mam zamiar zrobić
coś absurdalnego jak naprawdę duży

977
00:42:27,690 --> 00:42:30,375
liczba, Oh, że faktycznie udało -

978
00:42:30,375 --> 00:42:31,600
eh, nie sądzę, że to prawda.

979
00:42:31,600 --> 00:42:32,810
Zobaczymy.

980
00:42:32,810 --> 00:42:34,060
Niech naprawdę zadzieraj z nim.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> To jest problem.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
Co się dzieje?

985
00:42:44,970 --> 00:42:46,050
Kod nie jest tak źle.

986
00:42:46,050 --> 00:42:48,470
To wciąż liniowa.

987
00:42:48,470 --> 00:42:50,810
Gwizd jest dobry efekt, choć.

988
00:42:50,810 --> 00:42:52,060
Co się dzieje?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> Nie wiem, czy to usłyszałem.

991
00:42:55,620 --> 00:42:57,620
Okazuje się - i
to jest tak na bok.

992
00:42:57,620 --> 00:42:59,400
To nie jest kluczowy dla
Pomysł rekursji.

993
00:42:59,400 --> 00:43:02,480
Okazuje się, bo staram się
stanowią tak dużą ilość, najbardziej

994
00:43:02,480 --> 00:43:06,980
może to być błędnie
przez C, jak wielu nie pozytywnego,

995
00:43:06,980 --> 00:43:09,980
ale liczba ujemna.

996
00:43:09,980 --> 00:43:12,690
>> Nie rozmawialiśmy o tym, ale to
Okazuje się, że są liczby ujemne

997
00:43:12,690 --> 00:43:14,210
W świecie oprócz
do liczb dodatnich.

998
00:43:14,210 --> 00:43:16,290
A sposób, w którym można
reprezentują liczbę ujemną

999
00:43:16,290 --> 00:43:19,530
w istocie jest, można użyć jednego
specjalny bit do wskazania

1000
00:43:19,530 --> 00:43:20,400
pozytywne nad negatywnymi.

1001
00:43:20,400 --> 00:43:22,950
To jest trochę bardziej skomplikowane niż to,
ale to jest podstawowa idea.

1002
00:43:22,950 --> 00:43:26,740
>> Więc niestety, jeśli C jest mylące jednego
z tych bitów, jak w rzeczywistości oznacza,

1003
00:43:26,740 --> 00:43:30,790
oh, to jest liczba ujemna, moja pętla
tu, na przykład, nie jest w rzeczywistości

1004
00:43:30,790 --> 00:43:31,740
zamierza wypowiedzieć.

1005
00:43:31,740 --> 00:43:33,850
Więc jeśli coś faktycznie drukowania
znowu i znowu, chcielibyśmy

1006
00:43:33,850 --> 00:43:34,650
zobacz dużo.

1007
00:43:34,650 --> 00:43:36,220
Jednak ponownie, to obok punktu.

1008
00:43:36,220 --> 00:43:38,590
To jest naprawdę tylko rodzaj
dociekliwość, że uda nam się

1009
00:43:38,590 --> 00:43:39,550
tyłu, aby ostatecznie.

1010
00:43:39,550 --> 00:43:43,400
Ale teraz, to jest poprawna
Realizacja jeśli założymy, że

1011
00:43:43,400 --> 00:43:45,970
Użytkownik zapewni ints
że dopasowanie ciągu liczb całkowitych.

1012
00:43:45,970 --> 00:43:49,370
>> Ale twierdzą, że ten kod, szczerze mówiąc,
można zrobić o wiele więcej po prostu.

1013
00:43:49,370 --> 00:43:54,060
Jeśli cel w kasie jest podjąć szereg
jak m i dodać wszystkie

1014
00:43:54,060 --> 00:43:59,510
numery między nim a 1 lub odwrotnie
między 1 a, I twierdzą

1015
00:43:59,510 --> 00:44:03,380
że mogę pożyczyć ten pomysł, który łączy
sort miał, który brał problem

1016
00:44:03,380 --> 00:44:05,660
tej wielkości podzielonej
na coś mniejszego.

1017
00:44:05,660 --> 00:44:09,875
Może nie pół, ale mniejszy, ale
reprezentatywnie same.

1018
00:44:09,875 --> 00:44:12,130
Sam pomysł, ale mniejszy problem.

1019
00:44:12,130 --> 00:44:15,470
>> Więc jestem w rzeczywistości - pozwól mi zapisać ten plik
z innym numerem wersji.

1020
00:44:15,470 --> 00:44:17,670
Nazwijmy tę wersję
1 zamiast 0.

1021
00:44:17,670 --> 00:44:20,790
I twierdzą, że w rzeczywistości może
reimplement to w tego rodzaju

1022
00:44:20,790 --> 00:44:22,160
umysłów sposób.

1023
00:44:22,160 --> 00:44:23,710
>> Mam zamiar zostawić część to sam.

1024
00:44:23,710 --> 00:44:27,710
I powiem, jeśli m jest mniejsza
niż lub nawet równa 0 -

1025
00:44:27,710 --> 00:44:29,280
Jestem po prostu będzie trochę
Tym razem bardziej anal

1026
00:44:29,280 --> 00:44:30,520
z mojego sprawdzania błędów -

1027
00:44:30,520 --> 00:44:33,190
Mam zamiar iść do przodu i zwraca 0.

1028
00:44:33,190 --> 00:44:34,490
To jest arbitralne.

1029
00:44:34,490 --> 00:44:37,500
Jestem po prostu podejmowaniu decyzji, czy użytkownik
daje mi liczbę ujemną, jestem

1030
00:44:37,500 --> 00:44:41,490
powrocie 0, a powinni byli przeczytać
Dokumentacja bliżej.

1031
00:44:41,490 --> 00:44:42,170
>> Else -

1032
00:44:42,170 --> 00:44:44,070
zauważyć, co mam zamiar zrobić.

1033
00:44:44,070 --> 00:44:49,260
Else I zamierzam wrócić m powiększonej -

1034
00:44:49,260 --> 00:44:51,010
co jest sigma z m?

1035
00:44:51,010 --> 00:44:56,710
Cóż, sigma m powiększonej m minus 1,
oraz m minus 2 plus m minus 3.

1036
00:44:56,710 --> 00:44:58,030
Nie chcę pisać wszystko to.

1037
00:44:58,030 --> 00:44:59,120
Dlaczego nie mogę po prostu punt?

1038
00:44:59,120 --> 00:45:05,080
Rekursywnie nazywają siebie z lekko
mniejszy problem, średnik,

1039
00:45:05,080 --> 00:45:06,840
i nazywają to dzień?

1040
00:45:06,840 --> 00:45:07,040
>> Prawda?

1041
00:45:07,040 --> 00:45:10,980
Teraz i tu można czuć lub martwić
że jest to pętla nieskończona, że ​​jestem

1042
00:45:10,980 --> 00:45:15,450
wywołujących, przy czym jestem realizacji
sigma poprzez wywołanie sigma.

1043
00:45:15,450 --> 00:45:20,342
Ale to jest zupełnie OK, bo
że przed dodane, które linie?

1044
00:45:20,342 --> 00:45:22,600
>> PUBLICZNOŚCI: [niesłyszalne].

1045
00:45:22,600 --> 00:45:25,430
>> DAVID MALAN: 23 do 26, która
jest mój, jeśli warunek.

1046
00:45:25,430 --> 00:45:28,390
Bo to, co jest ładne o
odejmowanie tutaj, bo trzymam

1047
00:45:28,390 --> 00:45:31,180
oddaniem sigma mniejsze problemy, mniejsze
problemy, mniejsze - to nie jest

1048
00:45:31,180 --> 00:45:31,870
połowę mniejsza.

1049
00:45:31,870 --> 00:45:34,380
To tylko krok dziecko mniejsze,
ale to jest OK.

1050
00:45:34,380 --> 00:45:38,050
Bo w końcu, będziemy pracować
nasza droga w dół do 1 lub 0.

1051
00:45:38,050 --> 00:45:41,630
I po raz trafiliśmy 0, sigma nie
zacznie nazywać siebie więcej.

1052
00:45:41,630 --> 00:45:43,590
To będzie natychmiast wrócić 0.

1053
00:45:43,590 --> 00:45:47,960
>> Więc efekt, jeśli rodzaj wiatru to
się w głowie, jest dodanie M oraz

1054
00:45:47,960 --> 00:45:52,740
m minus 1 plus m minus 2 plus m minus
3 plus kropka, kropka, kropka, m minus

1055
00:45:52,740 --> 00:45:57,820
m, w końcu daje 0, a
Efekt jest ostatecznie dodać wszystkie

1056
00:45:57,820 --> 00:45:59,070
te rzeczy razem.

1057
00:45:59,070 --> 00:46:02,380
Więc nie mamy z rekurencji,
rozwiązać problem, że

1058
00:46:02,380 --> 00:46:03,470
nie można rozwiązać przed.

1059
00:46:03,470 --> 00:46:06,840
Rzeczywiście, 0 wersja tego, a każdy
Problem do tej pory, nie było rozwiązywalne

1060
00:46:06,840 --> 00:46:09,980
się tylko za pomocą pętli for lub podczas
pętle lub podobnych konstrukcji.

1061
00:46:09,980 --> 00:46:13,150
>> Ale rekurencja, śmiem twierdzić, daje nam
inny sposób myślenia o

1062
00:46:13,150 --> 00:46:17,010
problemów, przy czym jeśli możemy
Problem, podzielić go z czegoś

1063
00:46:17,010 --> 00:46:22,340
dość duża w coś cierpkawym
mniejsze, I twierdzą, że możemy go rozwiązać

1064
00:46:22,340 --> 00:46:26,040
może trochę bardziej elegancko w kategoriach
konstrukcji, z mniejszą ilością kodu

1065
00:46:26,040 --> 00:46:30,980
a może nawet rozwiązać problemy, które
być trudniejsze, a my będziemy w końcu

1066
00:46:30,980 --> 00:46:33,280
zobacz, rozwiązywaniu czysto iteracyjnie.

1067
00:46:33,280 --> 00:46:35,980
>> Ale cliffhanger, że zrobiłem
chce zostawić nas na to było.

1068
00:46:35,980 --> 00:46:40,720
Pozwólcie mi iść do przodu i otworzyć
się plik z -

1069
00:46:40,720 --> 00:46:44,300
faktycznie, pozwól mi odejść i
zrobić to naprawdę szybko.

1070
00:46:44,300 --> 00:46:46,875
Pozwólcie mi iść dalej i zaproponować
dodaje.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
Wśród dzisiejszych kod jest ten plik tutaj.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
Ten tutaj, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> Więc to jest głupie mały program, który
I bita się, że roszczenia do zrobienia

1076
00:47:06,260 --> 00:47:06,940
dodaje.

1077
00:47:06,940 --> 00:47:10,140
W głównym, najpierw deklaruje
int o nazwie x i przypisuje go

1078
00:47:10,140 --> 00:47:11,100
wartość 1.

1079
00:47:11,100 --> 00:47:13,520
Następnie oświadcza, int y, a
przypisuje jej wartość 2.

1080
00:47:13,520 --> 00:47:15,310
Następnie wypisuje co x i y jest.

1081
00:47:15,310 --> 00:47:17,781
Potem mówi, zamiana, dot dot dot.

1082
00:47:17,781 --> 00:47:21,670
>> Następnie twierdzi, że jest wywołanie funkcji
nazywa swapa, przekazując xi

1083
00:47:21,670 --> 00:47:24,290
y, którego idea jest taka, że ​​mam nadzieję, że
x i y będą wracać

1084
00:47:24,290 --> 00:47:25,620
inna, przeciwnie.

1085
00:47:25,620 --> 00:47:27,110
Następnie twierdzą zamienione!

1086
00:47:27,110 --> 00:47:28,420
z wykrzyknikiem.

1087
00:47:28,420 --> 00:47:30,190
Następnie wypisuje x i y.

1088
00:47:30,190 --> 00:47:33,480
>> Ale okazuje się, że to bardzo
prosta demonstracja w dół

1089
00:47:33,480 --> 00:47:35,570
tutaj jest rzeczywiście buggy.

1090
00:47:35,570 --> 00:47:38,870
Mimo, że jestem oświadczając chwilowy
zmienna i tymczasowo wprowadzenie w

1091
00:47:38,870 --> 00:47:42,010
to, czym jestem realokacja
Wartość B -

1092
00:47:42,010 --> 00:47:45,080
który czuje się uzasadnione, ponieważ nie mam
zapisywane kopie w temp..

1093
00:47:45,080 --> 00:47:48,410
Następnie zaktualizować b, aby równe
co było w temp..

1094
00:47:48,410 --> 00:47:51,610
Ten rodzaj gry powłoki ruchomych
do b i b do za pomocą tego

1095
00:47:51,610 --> 00:47:54,360
middle-temp czuje człowiek, który nazywał
całkowicie uzasadnione.

1096
00:47:54,360 --> 00:47:57,270
>> Ale twierdzą, że gdy ten
Kod, jak zrobię teraz -

1097
00:47:57,270 --> 00:47:59,490
pozwól mi iść do przodu i wklej go tutaj.

1098
00:47:59,490 --> 00:48:01,995
Zadzwonię do tego noswap.c.

1099
00:48:01,995 --> 00:48:05,630
I jak sama nazwa wskazuje, nie jest to
będzie właściwy program.

1100
00:48:05,630 --> 00:48:09,460
Marka noswap. / Nie wymiany.

1101
00:48:09,460 --> 00:48:12,110
x oznacza 1, y oznacza 2, zamianę, zamienione.

1102
00:48:12,110 --> 00:48:14,220
x oznacza 1, y oznacza 2.

1103
00:48:14,220 --> 00:48:16,920
To jest z gruntu fałszywe, nawet
choć wydaje się to doskonale

1104
00:48:16,920 --> 00:48:17,730
rozsądne do mnie.

1105
00:48:17,730 --> 00:48:21,330
I nie ma powodu, ale nie jesteśmy
zamierza ujawnić powód jeszcze.

1106
00:48:21,330 --> 00:48:24,610
>> Na razie drugiej cliffhanger chciałem
pozostawić Państwu to,

1107
00:48:24,610 --> 00:48:27,120
Ogłoszenie rodzaju na kupon kody.

1108
00:48:27,120 --> 00:48:31,590
Nasze innowacje w tym roku pod koniec dni
wywołał numer nietrywialne

1109
00:48:31,590 --> 00:48:33,830
pytań, które było
Nie jest naszym zamiarem.

1110
00:48:33,830 --> 00:48:36,590
Intencją tych kupon kody,
przy czym, jeśli nie część problemu

1111
00:48:36,590 --> 00:48:39,850
ustawiony na początku, tym samym uzyskanie dodatkowych dni,
było naprawdę pomóc wam pomóc

1112
00:48:39,850 --> 00:48:42,420
się rozpocząć na początku, sortowanie
z przez incentivizing ciebie.

1113
00:48:42,420 --> 00:48:44,880
Pomaga nam w dystrybucji obciążenia na
godziny pracy tak, aby lepiej

1114
00:48:44,880 --> 00:48:45,740
To coś w rodzaju win-win.

1115
00:48:45,740 --> 00:48:48,860
>> Niestety, myślę, że moje instrukcje
nie były do ​​tej pory, bardzo jasne, więc

1116
00:48:48,860 --> 00:48:52,230
Wróciłem w ten weekend i aktualizowane
spec większy, tekst odważniejsze do

1117
00:48:52,230 --> 00:48:53,600
wyjaśnić kul jak te.

1118
00:48:53,600 --> 00:48:56,900
I właśnie to powiedzieć bardziej ogólnie, przez
domyślnych, zestawy zadań są spowodowane czwartek

1119
00:48:56,900 --> 00:48:58,400
w południe, na programie nauczania.

1120
00:48:58,400 --> 00:49:02,030
Jeśli zaczynasz wcześnie, kończąc część
Problem ustawić się w środę o 12:00

1121
00:49:02,030 --> 00:49:05,170
PM, część, która dotyczy kuponu
Kod, idea jest taka, że ​​można rozszerzyć

1122
00:49:05,170 --> 00:49:07,710
Twój termin
P zestaw do piątku.

1123
00:49:07,710 --> 00:49:10,890
Oznacza to, że nieco off malutkiej części P
ustawiony w stosunku do tego, co zazwyczaj jest

1124
00:49:10,890 --> 00:49:13,200
większy problem, a kupisz
się dodatkowy dzień.

1125
00:49:13,200 --> 00:49:15,190
Ponownie, to dostaje się myśleć o
zestaw problemem, dostaje do

1126
00:49:15,190 --> 00:49:16,380
godziny pracy wcześniej.

1127
00:49:16,380 --> 00:49:20,670
Ale problem kupon jest nadal
konieczne, nawet jeśli nie przedstawia go.

1128
00:49:20,670 --> 00:49:23,340
>> Ale bardziej nieodparcie to.

1129
00:49:23,340 --> 00:49:26,520
(Scenicznym szeptem) I ci ludzie, pozostawiając
Już to będzie żałował.

1130
00:49:26,520 --> 00:49:28,620
Jak są ludzie, na balkonie.

1131
00:49:28,620 --> 00:49:32,510
Przepraszam z góry do ludzi na
balkon z powodów, które będą

1132
00:49:32,510 --> 00:49:33,920
wyczyścić za chwilę.

1133
00:49:33,920 --> 00:49:37,050
>> Więc mamy to szczęście, że jeden z
Dawni towarzysze CS50 łeb na nauczanie

1134
00:49:37,050 --> 00:49:39,302
Firma o nazwie dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
Mają bardzo hojnie podarowane
kod kuponu tutaj to dużo miejsca,

1136
00:49:45,500 --> 00:49:48,180
która jest od góry
Zwykłe 2 gigabajty.

1137
00:49:48,180 --> 00:49:51,740
Więc to, co myślałem, że robimy w tej sprawie
Ostatnia uwaga jest zrobić trochę gratisów,

1138
00:49:51,740 --> 00:49:55,380
przy czym za chwilę, będziemy ujawniać
Zwycięzca i kto ma kupon

1139
00:49:55,380 --> 00:49:57,980
kod, który następnie można przejść do ich
strona www, wpisz ją i voila, uzyskać

1140
00:49:57,980 --> 00:50:01,370
dużo więcej miejsca Dropbox dla swojego
Urządzenie i plików osobistych.

1141
00:50:01,370 --> 00:50:05,690
>> I pierwsza, którzy chcieliby wziąć udział
na tym rysunku?

1142
00:50:05,690 --> 00:50:09,630
OK, teraz sprawia, że ​​jeszcze bardziej zabawne.

1143
00:50:09,630 --> 00:50:14,010
Osoba, która otrzymuje ten 25-gigabajt
kupon - co jest o wiele

1144
00:50:14,010 --> 00:50:16,150
bardziej przekonujące niż późno
dzień teraz, być może -

1145
00:50:16,150 --> 00:50:20,620
jest tym, który siedzi na szczycie
siedzisko pod którym jest

1146
00:50:20,620 --> 00:50:21,620
że kupon.

1147
00:50:21,620 --> 00:50:23,480
Możesz teraz spojrzeć pod
Twój siedzisko.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [PLAYBACK VIDEO]

1150
00:50:29,680 --> 00:50:31,620
>> -Raz, dwa, trzy.

1151
00:50:31,620 --> 00:50:35,015
>> [SCREAMING]

1152
00:50:35,015 --> 00:50:35,985
>> -Masz samochód!

1153
00:50:35,985 --> 00:50:36,670
Masz samochód!

1154
00:50:36,670 --> 00:50:37,970
>> DAVID MALAN: Zobaczymy
Ci w środę.

1155
00:50:37,970 --> 00:50:38,904
>> -Masz samochód!

1156
00:50:38,904 --> 00:50:39,371
Masz samochód!

1157
00:50:39,371 --> 00:50:40,305
Masz samochód!

1158
00:50:40,305 --> 00:50:41,706
Masz samochód!

1159
00:50:41,706 --> 00:50:43,107
Masz samochód!

1160
00:50:43,107 --> 00:50:45,530
>> DAVID MALAN: ludzie balkon, chodź
tu do przodu,

1161
00:50:45,530 --> 00:50:46,866
gdzie mamy dodatki.

1162
00:50:46,866 --> 00:50:50,282
>> -Każdy ma samochód!

1163
00:50:50,282 --> 00:50:52,234
Każdy ma samochód!

1164
00:50:52,234 --> 00:50:52,722
>> [END PLAYBACK VIDEO]

1165
00:50:52,722 --> 00:50:54,590
>> Narrator: Na następnym CS50 -

1166
00:50:54,590 --> 00:51:00,374
>> Głośnik 5: O mój Boże gosh gosh gosh
jejku jejku jejku jejku jejku jejku -

1167
00:51:00,374 --> 00:51:02,106
>> [SZTUKI UKELELE]