1
00:00:00,000 --> 00:00:11,904
>> [MUZYKI]

2
00:00:11,904 --> 00:00:12,910
>> PROFESOR: Wszystko w porządku.

3
00:00:12,910 --> 00:00:16,730
Jest CS50 i jest
po trzech tygodnia.

4
00:00:16,730 --> 00:00:20,230
Więc jesteśmy tu dzisiaj, nie w Sanders
Teatr, a nie w Weidner Biblioteki.

5
00:00:20,230 --> 00:00:23,170
Wewnątrz której znajduje się studio
znany jako Hauser Studio,

6
00:00:23,170 --> 00:00:28,310
lub powiemy Studio H, lub powinien
mamy say-- Jeśli korzystają ten dowcip,

7
00:00:28,310 --> 00:00:30,540
to faktycznie od
kolega, Mark, on-line,

8
00:00:30,540 --> 00:00:32,420
który zasugerował nawet za pośrednictwem Twittera.

9
00:00:32,420 --> 00:00:34,270
Teraz to, co jest fajnego
będąc tutaj w studio

10
00:00:34,270 --> 00:00:38,410
jest to, że jestem otoczony przez te zielone
ściany, zielony ekran lub chromakey,

11
00:00:38,410 --> 00:00:43,290
że tak powiem, co oznacza, że ​​CS50 na
zespół produkcyjny, nie wiemy o mnie

12
00:00:43,290 --> 00:00:47,380
teraz, może być wprowadzenie
mnie najbardziej na całym świecie,

13
00:00:47,380 --> 00:00:48,660
na lepsze lub na gorsze.

14
00:00:48,660 --> 00:00:51,800
>> Teraz to, co jest przed nami, ustawić problemem
dwóch jest w Twoich rękach w tym tygodniu,

15
00:00:51,800 --> 00:00:53,830
ale z problemu ustawić
trzy w nadchodzącym tygodniu

16
00:00:53,830 --> 00:00:56,600
będzie prowokacji
tak zwana gra 15,

17
00:00:56,600 --> 00:00:58,960
stary partia łaska, że
Może pamiętacie odbioru

18
00:00:58,960 --> 00:01:02,030
jako dziecko, że ma całą masę
wartości, które mogą przesuwać się w górę, w dół,

19
00:01:02,030 --> 00:01:05,790
w lewo i prawo, a jest jedna szczelina
w układanki, do którego

20
00:01:05,790 --> 00:01:07,840
może rzeczywiście przesunąć tych puzzli.

21
00:01:07,840 --> 00:01:11,150
Ostatecznie otrzymasz ten list
puzzle w jakimś pół kolejności losowej,

22
00:01:11,150 --> 00:01:12,940
a celem jest
rozwiązać to, od góry do dołu,

23
00:01:12,940 --> 00:01:16,310
od lewej do prawej, z jednego
aż do góry do 15.

24
00:01:16,310 --> 00:01:19,360
>> Niestety, realizacja
będziesz miał pod ręką

25
00:01:19,360 --> 00:01:21,590
będzie oprogramowanie
opiera, nie fizycznie.

26
00:01:21,590 --> 00:01:25,280
Jesteś rzeczywiście będzie musiał napisać
Kod z którymi student lub użytkownik może

27
00:01:25,280 --> 00:01:26,760
gry w 15.

28
00:01:26,760 --> 00:01:29,030
I rzeczywiście, w hakera
edycja gry 15,

29
00:01:29,030 --> 00:01:32,155
musisz być wyzwaniem do realizacji,
nie tylko gry z tej starej szkoły

30
00:01:32,155 --> 00:01:35,010
gry, ale raczej rozwiązywanie
o tym, wdrażanie God Mode,

31
00:01:35,010 --> 00:01:38,280
że tak powiem, że rzeczywiście
rozwiązuje zagadkę dla człowieka,

32
00:01:38,280 --> 00:01:41,080
poprzez zapewnienie im wskazówkę,
po nutą, po podpowiedź.

33
00:01:41,080 --> 00:01:42,280
Więc więcej o tym następnym tygodniu.

34
00:01:42,280 --> 00:01:43,720
Ale to, co nas czeka.

35
00:01:43,720 --> 00:01:47,610
>> Na razie przypomnieć, że wcześniej w tym tygodniu
mieliśmy ten cliffhanger, jeśli chcesz,

36
00:01:47,610 --> 00:01:52,560
przy czym najlepiej robiliśmy sortowania
Mądry był górnej granicy Big O n

37
00:01:52,560 --> 00:01:53,210
do kwadratu.

38
00:01:53,210 --> 00:01:56,520
Innymi słowy, sortowanie bąbelkowe,
Wybór rodzaju, Sortowanie przez wstawianie,

39
00:01:56,520 --> 00:01:59,120
wszystkie z nich, podczas gdy inna
w ich realizacji,

40
00:01:59,120 --> 00:02:03,480
przekazane do n do kwadratu działa
czas, w najgorszym przypadku.

41
00:02:03,480 --> 00:02:06,010
I na ogół zakładamy, że
najgorszym przypadku sortowania

42
00:02:06,010 --> 00:02:08,814
to taki, który swoje wejścia
są całkowicie do tyłu.

43
00:02:08,814 --> 00:02:11,980
I rzeczywiście, zajęło sporo kroki
do realizacji każdego z tych algorytmów.

44
00:02:11,980 --> 00:02:15,110
>> Teraz na samym końcu klasy
Przypomnijmy, że w porównaniu z bąbelkami rodzaju

45
00:02:15,110 --> 00:02:19,390
wobec wyboru rodzaju wobec siebie nawzajem
które nazwaliśmy sortowanie przez scalanie w czasie,

46
00:02:19,390 --> 00:02:22,120
i proponuję, to biorąc
Zaletą lekcji z tygodnia

47
00:02:22,120 --> 00:02:24,060
zero, dziel i rządź.

48
00:02:24,060 --> 00:02:28,810
I jakoś osiągnięcia pewnego rodzaju
logarytmiczna czas pracy ostatecznie

49
00:02:28,810 --> 00:02:31,024
a nie coś
to czysto kwadratowa.

50
00:02:31,024 --> 00:02:33,440
I to nie dość, logarytmiczna,
to trochę więcej.

51
00:02:33,440 --> 00:02:36,520
Ale jeśli pamiętam z lekcji,
jest to o wiele szybciej.

52
00:02:36,520 --> 00:02:38,210
Rzućmy okiem na którym skończyliśmy.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> Sortowanie bąbelkowe kontra wyboru
Sortuj kontra sortowanie przez scalanie.

55
00:02:45,370 --> 00:02:47,700
Teraz oni wszyscy działa w
teorią, w tym samym czasie.

56
00:02:47,700 --> 00:02:50,510
CPU obraca się z tą samą prędkością.

57
00:02:50,510 --> 00:02:54,990
Ale możesz czuć się jak nudne to
jest bardzo szybko stanie się,

58
00:02:54,990 --> 00:02:58,790
i jak szybko, kiedy wstrzyknąć
nieco algorytmów tygodniu Zero,

59
00:02:58,790 --> 00:03:00,080
możemy przyspieszyć.

60
00:03:00,080 --> 00:03:01,630
>> Więc znak swego wygląda niesamowicie.

61
00:03:01,630 --> 00:03:05,220
Jak możemy wykorzystać go w celu
szybciej sortować numery.

62
00:03:05,220 --> 00:03:07,140
No pomyślmy powrotem
do substancji, które

63
00:03:07,140 --> 00:03:10,380
miał z powrotem w tygodniu zerowym, że od
szukając kogoś w książce telefonicznej,

64
00:03:10,380 --> 00:03:12,380
i przypomnieć, że
pseudokod, który zaproponowaliśmy,

65
00:03:12,380 --> 00:03:14,560
za pomocą której można znaleźć
ktoś taki jak Mike Smith,

66
00:03:14,560 --> 00:03:16,310
wyglądał na trochę coś takiego.

67
00:03:16,310 --> 00:03:20,820
>> Teraz spójrz w szczególności
w linii 7 i 8 oraz 10 i 11,

68
00:03:20,820 --> 00:03:25,240
które wywołują tę pętlę, w której trzymaliśmy
powrót do linii 3 znowu, i znowu,

69
00:03:25,240 --> 00:03:26,520
i jeszcze raz.

70
00:03:26,520 --> 00:03:31,790
Ale okazuje się, że możemy zobaczyć
ten algorytm, tu w Pseudokod,

71
00:03:31,790 --> 00:03:33,620
trochę bardziej całościowo.

72
00:03:33,620 --> 00:03:35,960
W rzeczywistości, czego szukam
w tutaj na ekranie

73
00:03:35,960 --> 00:03:41,180
jest algorytm poszukiwania
Mike Smith wśród jakiegoś zestawu stron.

74
00:03:41,180 --> 00:03:45,520
I rzeczywiście, możemy uprościć ten
Algorytm w tych liniach 7 i 8,

75
00:03:45,520 --> 00:03:49,860
oraz 10 i 11, aby po prostu powiedzieć, że to,
które prezentowane tutaj mam na żółto.

76
00:03:49,860 --> 00:03:52,210
Innymi słowy, jeśli Mike
Smith jest wcześniej w książce,

77
00:03:52,210 --> 00:03:55,004
nie musimy określić krok
po kroku, teraz jak go poszukać.

78
00:03:55,004 --> 00:03:56,920
Nie mamy do określenia
aby wrócić do linii 3,

79
00:03:56,920 --> 00:03:58,960
Dlaczego nie możemy po prostu, a nie,
powiedzieć, ogólnie,

80
00:03:58,960 --> 00:04:01,500
szukaj Mike w
Lewa połowa książki.

81
00:04:01,500 --> 00:04:03,960
>> I odwrotnie, jeśli Mike
faktycznie później w książce,

82
00:04:03,960 --> 00:04:07,540
dlaczego nie możemy po prostu cytatu wyszukiwanie
Mike'a w prawej połowie książki.

83
00:04:07,540 --> 00:04:11,030
Innymi słowy, dlaczego nie możemy po prostu
rodzaj punt do siebie, mówiąc:

84
00:04:11,030 --> 00:04:13,130
szukaj Mike to
podzbiorem książki,

85
00:04:13,130 --> 00:04:16,279
i pozostawić do naszych obecnych
Algorytm nam powiedzieć

86
00:04:16,279 --> 00:04:18,750
jak szukać Mike
że lewa połowa książki.

87
00:04:18,750 --> 00:04:20,750
Innymi słowy, nasze
Algorytm działa, czy jest to

88
00:04:20,750 --> 00:04:24,670
książki telefonicznej tej grubości, to
Grubość lub dowolnej grubości ogóle.

89
00:04:24,670 --> 00:04:27,826
Więc możemy rekursywnie
zdefiniowanie tego algorytmu.

90
00:04:27,826 --> 00:04:29,950
Innymi słowy, na
Ekran tutaj, jest algorytmem

91
00:04:29,950 --> 00:04:33,130
do poszukiwania Mike Smith
wśród stronach książki telefonicznej.

92
00:04:33,130 --> 00:04:37,410
Tak więc w linii 7 i 10, niech
tylko powiedzieć dokładnie to.

93
00:04:37,410 --> 00:04:40,250
I używam tego określenia chwilę
temu, i rzeczywiście, rekurencja

94
00:04:40,250 --> 00:04:42,450
jest modne teraz,
i to jest ten proces

95
00:04:42,450 --> 00:04:47,210
zrobić coś cyklicznego przez jakiś
za pomocą kodu, który już masz,

96
00:04:47,210 --> 00:04:49,722
i nazywając go ponownie,
i znowu, i znowu.

97
00:04:49,722 --> 00:04:51,930
Teraz to będzie ważne
że jakoś na dole

98
00:04:51,930 --> 00:04:53,821
, i nie rób tego nieskończenie długo.

99
00:04:53,821 --> 00:04:56,070
W przeciwnym razie będziemy
mają rzeczywiście nieskończoną pętlę.

100
00:04:56,070 --> 00:04:59,810
Ale zobaczymy, czy możemy pożyczyć ten pomysł
z rekurencji, znów robi coś

101
00:04:59,810 --> 00:05:03,600
i znowu i znowu, aby rozwiązać
Problem sortowania przez scalanie

102
00:05:03,600 --> 00:05:05,900
sortowania, bardziej efektywnie.

103
00:05:05,900 --> 00:05:06,970
>> Więc dam ci sortowanie przez scalanie.

104
00:05:06,970 --> 00:05:07,920
Spójrzmy.

105
00:05:07,920 --> 00:05:10,850
Więc tutaj jest pseudokod, z
które moglibyśmy wdrożyć sortowania,

106
00:05:10,850 --> 00:05:12,640
za pomocą tego algorytmu o nazwie sortowanie przez scalanie.

107
00:05:12,640 --> 00:05:13,880
I jest to po prostu to.

108
00:05:13,880 --> 00:05:15,940
Na wejściu elementów n,
innymi słowy, jeśli jesteś

109
00:05:15,940 --> 00:05:18,830
podane n elementów i numerów oraz
litery lub cokolwiek pomiarowej,

110
00:05:18,830 --> 00:05:22,430
jeśli podane elementy n, jeśli
n jest mniejsze niż 2, po prostu wrócić.

111
00:05:22,430 --> 00:05:22,930
Dobrze?

112
00:05:22,930 --> 00:05:26,430
Dlatego, gdy n jest mniejsze niż 2, który
Oznacza to, że moja lista elementów

113
00:05:26,430 --> 00:05:30,446
albo o rozmiarze 0 i 1, a
W obu tych trywialne przypadkach

114
00:05:30,446 --> 00:05:31,570
lista jest już posortowana.

115
00:05:31,570 --> 00:05:32,810
Jeśli nie ma listy, jest klasyfikowane.

116
00:05:32,810 --> 00:05:35,185
A jeśli istnieje lista długości
1, jest to oczywiście klasyfikowane.

117
00:05:35,185 --> 00:05:38,280
Tak algorytm musi jedynie
Naprawdę coś ciekawego,

118
00:05:38,280 --> 00:05:40,870
jeśli mamy dwa lub więcej
Elementy nam dany.

119
00:05:40,870 --> 00:05:42,440
Więc spójrzmy na magii wtedy.

120
00:05:42,440 --> 00:05:47,500
Jeszcze uporządkować lewą połowę elementów,
następnie posortować prawą połowę elementów,

121
00:05:47,500 --> 00:05:49,640
następnie scalić posortowane połówki.

122
00:05:49,640 --> 00:05:52,440
A co to za umysłu gięcia
tutaj jest to, że tak naprawdę nie

123
00:05:52,440 --> 00:05:56,190
Wydaje się, że mówiłem
coś jeszcze, prawda?

124
00:05:56,190 --> 00:05:59,560
Wszystko, co powiedziałem jest, biorąc pod uwagę listę
n elementów, posortować lewą połowę,

125
00:05:59,560 --> 00:06:01,800
a następnie w prawo w połowie, a następnie
scalić posortowane połówki,

126
00:06:01,800 --> 00:06:03,840
ale gdzie jest rzeczywista tajne sos?

127
00:06:03,840 --> 00:06:05,260
Gdzie jest algorytm?

128
00:06:05,260 --> 00:06:09,150
Cóż okazuje się, że tych dwóch linii
Pierwszy, jakby opuścił połowę elementów,

129
00:06:09,150 --> 00:06:13,970
i prawa połowa sortowania elementów,
są wywołania rekurencyjne, że tak powiem.

130
00:06:13,970 --> 00:06:16,120
>> Po tym wszystkim, w tym
punkt w czasie, mam

131
00:06:16,120 --> 00:06:18,950
algorytm, z którymi się
sortować całą masę elementów?

132
00:06:18,950 --> 00:06:19,450
Tak.

133
00:06:19,450 --> 00:06:20,620
To właśnie tutaj.

134
00:06:20,620 --> 00:06:25,180
To tutaj, na ekranie, a
więc mogę korzystać z tego samego zestawu kroków

135
00:06:25,180 --> 00:06:28,500
sortowanie lewą połowę,
jak mogę prawa połowa.

136
00:06:28,500 --> 00:06:30,420
I rzeczywiście, jeszcze raz, i jeszcze raz.

137
00:06:30,420 --> 00:06:34,210
Więc tak czy inaczej, a my wkrótce
zobaczyć, magię sortowanie przez scalanie

138
00:06:34,210 --> 00:06:37,967
jest osadzony w które bardzo ostateczna
linii, łączących posortowane połówki.

139
00:06:37,967 --> 00:06:39,300
I to wydaje się dość intuicyjne.

140
00:06:39,300 --> 00:06:41,050
Weź dwie połówki, a ci,
jakoś połączyć je ze sobą,

141
00:06:41,050 --> 00:06:43,260
i zobaczymy to
konkretnie w jednej chwili.

142
00:06:43,260 --> 00:06:45,080
>> Ale to jest kompletny algorytm.

143
00:06:45,080 --> 00:06:46,640
I zobaczmy, dlaczego.

144
00:06:46,640 --> 00:06:50,912
Przypuszczać, że dostaniemy te same
Tutaj osiem elementów na ekranie, jeden

145
00:06:50,912 --> 00:06:53,120
przez osiem lat, ale są
w celu pozornie losowej.

146
00:06:53,120 --> 00:06:55,320
A cel w zasięgu ręki jest
posortować te elementy.

147
00:06:55,320 --> 00:06:58,280
Cóż, jak można przejść o
robi to za pomocą znowu

148
00:06:58,280 --> 00:07:00,407
sortowanie przez scalanie, jak na tym Pseudokod?

149
00:07:00,407 --> 00:07:02,740
I znowu, zakorzeniony w tym w
twój umysł, na chwilę.

150
00:07:02,740 --> 00:07:05,270
Pierwszy przypadek jest dość
trywialne, jeśli jest mniejsza niż 2,

151
00:07:05,270 --> 00:07:07,060
po prostu wrócić, nie ma do zrobienia.

152
00:07:07,060 --> 00:07:09,290
Tak naprawdę istnieje tylko trzy
Kroki, aby naprawdę mieć na uwadze.

153
00:07:09,290 --> 00:07:11,081
Znowu, i znowu, jestem
będzie chciał mieć

154
00:07:11,081 --> 00:07:13,980
sortowanie lewą połowę,
sortować prawą połowę,

155
00:07:13,980 --> 00:07:15,890
a następnie po ich
dwie połówki są klasyfikowane,

156
00:07:15,890 --> 00:07:18,710
Chcę połączyć je razem
w jednym posortowanej listy.

157
00:07:18,710 --> 00:07:19,940
Miejcie to na uwadze.

158
00:07:19,940 --> 00:07:21,310
>> Więc tutaj jest oryginalna lista.

159
00:07:21,310 --> 00:07:23,510
Miejmy traktują to jako
tablica, jak zaczęliśmy

160
00:07:23,510 --> 00:07:25,800
W każdym tygodniu, co jest
ciągły blok pamięci.

161
00:07:25,800 --> 00:07:28,480
W tym przypadku, zawiera osiem
numery, z powrotem do tyłu na plecach.

162
00:07:28,480 --> 00:07:30,700
I niech teraz zastosować sortowanie przez scalanie.

163
00:07:30,700 --> 00:07:33,300
Więc najpierw chcesz sortować
lewa połowa z tej listy,

164
00:07:33,300 --> 00:07:37,370
i niech zatem
koncentrują się na 4, 8, 6, i 2.

165
00:07:37,370 --> 00:07:41,000
>> Teraz jak mam go o
Sortowanie listy wielkości 4?

166
00:07:41,000 --> 00:07:45,990
Cóż mam teraz rozważyć
sortowanie lewej strony lewej połowie.

167
00:07:45,990 --> 00:07:47,720
Ponownie, niech tyłu na chwilę.

168
00:07:47,720 --> 00:07:51,010
Jeśli pseudokod jest to,
i mam podane osiem elementów,

169
00:07:51,010 --> 00:07:53,230
8 jest oczywiście większa
niż lub równą 2.

170
00:07:53,230 --> 00:07:54,980
Więc w pierwszym przypadku nie ma zastosowania.

171
00:07:54,980 --> 00:07:58,120
Więc do sortowania osiem elementów, po raz pierwszy
sortować lewą połowę elementów,

172
00:07:58,120 --> 00:08:01,930
następnie sortować prawą połowę, a następnie scalić
dwa posortowane połówki, każda o wielkości 4.

173
00:08:01,930 --> 00:08:02,470
OK.

174
00:08:02,470 --> 00:08:07,480
>> Ale jeśli właśnie powiedział mi, posortować
Lewa połowa, która jest wielkości 4,

175
00:08:07,480 --> 00:08:09,350
Jak sortować lewą połowę?

176
00:08:09,350 --> 00:08:11,430
Cóż, jeśli mam mieć
Wejście czterech elementów

177
00:08:11,430 --> 00:08:14,590
Pierwszy raz posortować lewo
dwa, a następnie w prawo dwa,

178
00:08:14,590 --> 00:08:16,210
a potem połączyć je razem.

179
00:08:16,210 --> 00:08:18,700
Więc jeszcze raz, staje się nieco
z umysłu gięcia gra tutaj

180
00:08:18,700 --> 00:08:21,450
bo ty, rodzaju, muszą
pamiętaj, gdzie jesteś w tej historii,

181
00:08:21,450 --> 00:08:23,620
a na koniec dnia
podano żadnej liczby elementów

182
00:08:23,620 --> 00:08:25,620
najpierw chcesz posortować
Lewa połowa, a następnie w prawo w połowie,

183
00:08:25,620 --> 00:08:26,661
następnie połączyć je razem.

184
00:08:26,661 --> 00:08:28,630
Zacznijmy zrobić dokładnie to.

185
00:08:28,630 --> 00:08:30,170
Oto wejście z ośmiu elementów.

186
00:08:30,170 --> 00:08:31,910
Teraz patrzymy na lewej połowie tutaj.

187
00:08:31,910 --> 00:08:33,720
Jak sortować cztery elementy?

188
00:08:33,720 --> 00:08:35,610
Cóż najpierw uporządkować lewą połowę.

189
00:08:35,610 --> 00:08:37,720
Teraz jak mam rozwiązać lewą połowę?

190
00:08:37,720 --> 00:08:39,419
Cóż Dostałem dwa elementy.

191
00:08:39,419 --> 00:08:41,240
Warto więc uporządkować te dwa elementy.

192
00:08:41,240 --> 00:08:44,540
2 jest większa niż lub
równa 2, oczywiście.

193
00:08:44,540 --> 00:08:46,170
Tak, że pierwsza sprawa nie dotyczy.

194
00:08:46,170 --> 00:08:49,010
>> Więc teraz mam do sortowania lewo
połowa z tych dwóch elementów.

195
00:08:49,010 --> 00:08:50,870
Lewa połowa, oczywiście, jest tylko 4.

196
00:08:50,870 --> 00:08:54,020
Więc jak mam sortować listy jednego elementu?

197
00:08:54,020 --> 00:08:57,960
No to teraz, to szczególny przypadek bazowy
do góry, że tak powiem, ma zastosowanie.

198
00:08:57,960 --> 00:09:01,470
1 jest mniejsza niż 2, a mój
Lista jest rzeczywiście wielkości 1.

199
00:09:01,470 --> 00:09:02,747
Więc po prostu wrócić.

200
00:09:02,747 --> 00:09:03,580
Ja nic nie robię.

201
00:09:03,580 --> 00:09:06,770
I rzeczywiście, spójrz na to, co mam
zrobione, 4 jest już posortowana.

202
00:09:06,770 --> 00:09:09,220
Jak ja już jestem
częściowym sukcesem tutaj.

203
00:09:09,220 --> 00:09:11,750
>> Teraz to wydaje się głupie
zastrzeżenia, ale to prawda.

204
00:09:11,750 --> 00:09:13,700
4 znajduje się lista wielkości 1.

205
00:09:13,700 --> 00:09:15,090
To już klasyfikowane.

206
00:09:15,090 --> 00:09:16,270
To jest lewa połowa.

207
00:09:16,270 --> 00:09:18,010
Teraz sortować prawą połowę.

208
00:09:18,010 --> 00:09:22,310
Mój wkład jest jednym z elementów, 8
podobnie, już klasyfikowane.

209
00:09:22,310 --> 00:09:25,170
Głupi, zbyt, ale znowu,
Ta podstawowa zasada

210
00:09:25,170 --> 00:09:28,310
ma pozwolić nam teraz budować
na wierzchu tego pomyślnie.

211
00:09:28,310 --> 00:09:32,260
4 klasyfikowane, 8 jest posortowana, teraz
co to było ostatni krok?

212
00:09:32,260 --> 00:09:35,330
Więc trzeci i ostatni krok, każda
Czas jesteś sortowania listy, wycofanie,

213
00:09:35,330 --> 00:09:38,310
było połączenie dwóch połówek,
lewa i prawa.

214
00:09:38,310 --> 00:09:39,900
Warto więc zrobić dokładnie to.

215
00:09:39,900 --> 00:09:41,940
Moja lewa połowa jest, oczywiście, 4.

216
00:09:41,940 --> 00:09:43,310
Moja prawa połowa jest 8.

217
00:09:43,310 --> 00:09:44,100
>> Więc zróbmy to.

218
00:09:44,100 --> 00:09:46,410
Po pierwsze mam zamiar przeznaczyć
niektóre dodatkowa pamięć,

219
00:09:46,410 --> 00:09:48,680
że będę reprezentować tutaj,
jak tylko wtórnym tablicy,

220
00:09:48,680 --> 00:09:49,660
to jest wystarczająco duży, aby zmieścić to.

221
00:09:49,660 --> 00:09:52,243
Ale można sobie wyobrazić rozszerzenia
że prostokąt na całej długości,

222
00:09:52,243 --> 00:09:53,290
jeśli potrzebujesz więcej później.

223
00:09:53,290 --> 00:09:58,440
Jak zrobić 4 i 8, i połączyć
te dwie listy wielkości 1 razem?

224
00:09:58,440 --> 00:10:00,270
Tutaj również bardzo proste.

225
00:10:00,270 --> 00:10:03,300
4 jest na pierwszym miejscu, to jest 8.

226
00:10:03,300 --> 00:10:07,130
Bo jeśli chcę, aby posortować
Lewa połowa, a następnie w prawo w połowie,

227
00:10:07,130 --> 00:10:09,900
a następnie połączyć te dwie połówki
razem, w uporządkowanej kolejności,

228
00:10:09,900 --> 00:10:11,940
4 jest na pierwszym miejscu, to jest 8.

229
00:10:11,940 --> 00:10:15,810
>> Tak więc wydaje się, że robi postępy, nawet
choć nie robiłem żadnej pracy.

230
00:10:15,810 --> 00:10:17,800
Ale pamiętaj, gdzie jesteśmy w tej historii.

231
00:10:17,800 --> 00:10:19,360
Początkowo wziął ośmiu elementów.

232
00:10:19,360 --> 00:10:21,480
Mamy klasyfikowane lewą połowę, czyli 4.

233
00:10:21,480 --> 00:10:24,450
Potem klasyfikowane lewą połowę
w lewej części, która była 2.

234
00:10:24,450 --> 00:10:25,270
I jedziemy.

235
00:10:25,270 --> 00:10:26,920
Skończyliśmy z tego kroku.

236
00:10:26,920 --> 00:10:29,930
>> Więc jeśli mamy posortowane
lewa połówka 2, teraz my

237
00:10:29,930 --> 00:10:32,130
trzeba posortować prawą połowę 2.

238
00:10:32,130 --> 00:10:35,710
Tak więc prawo połowa 2 jest
te dwie wartości tutaj, 6 i 2.

239
00:10:35,710 --> 00:10:40,620
Więc teraz trzeba wejście wielkości
2 i sortować lewą połowę, a następnie

240
00:10:40,620 --> 00:10:42,610
prawa połowa, a następnie
połączyć je razem.

241
00:10:42,610 --> 00:10:45,722
Cóż, jak posortować listę rozmiarów
1, zawierający tylko numer 6?

242
00:10:45,722 --> 00:10:46,430
Mam już zrobione.

243
00:10:46,430 --> 00:10:48,680
Wykaz wielkości 1 jest posortowana.

244
00:10:48,680 --> 00:10:52,140
>> Jak sortować kolejną listę
rozmiar 1, tak zwane prawa połowa.

245
00:10:52,140 --> 00:10:54,690
No cóż, to też jest już posortowana.

246
00:10:54,690 --> 00:10:56,190
Numer 2 jest sam.

247
00:10:56,190 --> 00:11:00,160
Więc teraz mam dwie połowy, w lewo i
Dobra, muszę połączyć je razem.

248
00:11:00,160 --> 00:11:01,800
Pozwól mi dać sobie trochę wolnego miejsca.

249
00:11:01,800 --> 00:11:05,580
2 i umieścić tam,
następnie 6 w nie, a tym samym

250
00:11:05,580 --> 00:11:10,740
sortowania tej listy, w lewo i prawo,
i połączenie go razem ostatecznie.

251
00:11:10,740 --> 00:11:12,160
Więc jestem w nieco lepszej formie.

252
00:11:12,160 --> 00:11:16,250
Jeszcze nie skończyłem, bo wyraźnie 4, 8, 2,
6 nie jest ostateczna kolejność, że chcę.

253
00:11:16,250 --> 00:11:20,640
Ale teraz mam dwie listy wielkości 2, które
oba odpowiednio posortowane.

254
00:11:20,640 --> 00:11:24,580
Więc teraz, jeśli do tyłu w wyobraźni
oko, skąd nam pozostaje?

255
00:11:24,580 --> 00:11:28,520
Zacząłem z ośmiu elementów, to ja
stopniała go do lewej połowie 4,

256
00:11:28,520 --> 00:11:31,386
to lewa połowa 2 oraz
następnie w prawo połowa 2,

257
00:11:31,386 --> 00:11:34,510
I zakończona, zatem sortowanie lewej
połowa 2, a prawa połowa 2,

258
00:11:34,510 --> 00:11:37,800
więc co jest trzecim i ostatnim etapem tutaj?

259
00:11:37,800 --> 00:11:41,290
Muszę połączyć razem
dwie listy wielkości 2.

260
00:11:41,290 --> 00:11:42,040
Więc śmiało.

261
00:11:42,040 --> 00:11:43,940
A na ekranie tutaj, dają
mi trochę dodatkowej pamięci,

262
00:11:43,940 --> 00:11:47,170
choć technicznie, zauważysz, że mam
dostałem całą masę pustej przestrzeni do góry

263
00:11:47,170 --> 00:11:47,670
nie.

264
00:11:47,670 --> 00:11:50,044
Jeśli chcę być szczególnie
wydajne miejsca mądry,

265
00:11:50,044 --> 00:11:52,960
Może po prostu ruszyć elementy
w przód iw tył, góra i dół.

266
00:11:52,960 --> 00:11:55,460
Ale dla jasności wizualnej,
Mam zamiar umieścić go w dół poniżej,

267
00:11:55,460 --> 00:11:56,800
do przechowywania rzeczy ładne i czyste.

268
00:11:56,800 --> 00:11:58,150
>> Więc mam dwie listy wielkości 2.

269
00:11:58,150 --> 00:11:59,770
Pierwsza lista ma 4 i 8.

270
00:11:59,770 --> 00:12:01,500
Druga lista ma 2 i 6.

271
00:12:01,500 --> 00:12:03,950
Miejmy połączyć te
razem w uporządkowanej kolejności.

272
00:12:03,950 --> 00:12:09,910
2, oczywiście, jest na pierwszym,
potem 4, potem 6, a następnie 8.

273
00:12:09,910 --> 00:12:12,560
A teraz wydaje się być coraz
gdzieś interesujące.

274
00:12:12,560 --> 00:12:15,720
Teraz już klasyfikowane połowa
listy, i przypadkowo, to

275
00:12:15,720 --> 00:12:18,650
wszystkie parzyste, lecz
jest rzeczywiście tylko zbieg okoliczności.

276
00:12:18,650 --> 00:12:22,220
I teraz nie klasyfikowane w lewo
pół tak, że znajdują się 2, 4, 6 i 8.

277
00:12:22,220 --> 00:12:23,430
Nic nie jest w porządku.

278
00:12:23,430 --> 00:12:24,620
Że czuje się jak postępy.

279
00:12:24,620 --> 00:12:26,650
>> Teraz czuje się jak mam
Rozmawiałem na zawsze teraz

280
00:12:26,650 --> 00:12:29,850
więc to, co okaże się, czy to
Algorytm jest rzeczywiście bardziej skuteczne.

281
00:12:29,850 --> 00:12:31,766
Ale jedziemy przez
to bardzo metodycznie.

282
00:12:31,766 --> 00:12:34,060
Komputer oczywiście
zrobi to tak.

283
00:12:34,060 --> 00:12:34,840
Więc gdzie jesteśmy?

284
00:12:34,840 --> 00:12:36,180
Zaczęliśmy z ośmiu elementów.

285
00:12:36,180 --> 00:12:37,840
I klasyfikowane lewą połowę 4.

286
00:12:37,840 --> 00:12:39,290
Wydaje mi się zrobić z tym.

287
00:12:39,290 --> 00:12:42,535
Teraz kolejnym krokiem jest
sortować prawą połowę 4.

288
00:12:42,535 --> 00:12:44,410
I ta część możemy iść
przez trochę więcej

289
00:12:44,410 --> 00:12:47,140
szybko, choć jesteś
Zapraszamy do tyłu lub pauzy, po prostu

290
00:12:47,140 --> 00:12:49,910
przez to, że w
swoim własnym tempie, ale to, co

291
00:12:49,910 --> 00:12:53,290
mamy teraz jest okazją do
to dokładnie ten sam algorytm na czterech

292
00:12:53,290 --> 00:12:54,380
różne numery.

293
00:12:54,380 --> 00:12:57,740
>> Więc śmiało, a skupić się na
prawa połowa, co tu jesteśmy.

294
00:12:57,740 --> 00:13:01,260
Lewa połowa, że
prawa połowa, a teraz

295
00:13:01,260 --> 00:13:04,560
Lewa połowa z lewej
połowa tej prawej połowie,

296
00:13:04,560 --> 00:13:08,030
i jak mogę sortować listy rozmiarów
1 zawierające tylko numer 1?

297
00:13:08,030 --> 00:13:09,030
To już zrobione.

298
00:13:09,030 --> 00:13:11,830
Jak mogę zrobić to samo dla listy
wielkości 1 zawierającym tylko 7?

299
00:13:11,830 --> 00:13:12,840
To już zrobione.

300
00:13:12,840 --> 00:13:16,790
Krok trzeci w tym połowa to
jest, aby połączyć te dwa elementy

301
00:13:16,790 --> 00:13:20,889
do nowej listy wielkości 2, 1 i 7.

302
00:13:20,889 --> 00:13:23,180
Nie wydaje się, że zrobiłeś wszystko
że wiele interesująca praca.

303
00:13:23,180 --> 00:13:24,346
Zobaczymy, co będzie dalej.

304
00:13:24,346 --> 00:13:29,210
Właśnie klasyfikowane w lewej połowie
Prawa połowa mojego pierwotnego wejścia.

305
00:13:29,210 --> 00:13:32,360
Teraz uporządkować prawo
pół, który zawiera 5 i 3.

306
00:13:32,360 --> 00:13:35,740
Chodźmy znów spojrzeć na lewo
połowa, sortowane, prawa połowa, sortowane,

307
00:13:35,740 --> 00:13:39,120
i połączyć te dwa razem,
do jakiegoś dodatkowego miejsca,

308
00:13:39,120 --> 00:13:41,670
3 jest na pierwszym miejscu, to jest 5.

309
00:13:41,670 --> 00:13:46,190
A więc teraz, mamy posortowane
Lewa połowa prawej połowy

310
00:13:46,190 --> 00:13:49,420
pierwotnego problemu i
prawo połowa prawej połowie

311
00:13:49,420 --> 00:13:50,800
pierwotnego problemu.

312
00:13:50,800 --> 00:13:52,480
Co znajduje się trzeci i ostatni etap?

313
00:13:52,480 --> 00:13:54,854
Dobrze, aby połączyć te dwie połówki.

314
00:13:54,854 --> 00:13:57,020
Więc pozwól mi sobie niektóre
dodatkowe miejsce, ale, znowu,

315
00:13:57,020 --> 00:13:58,699
może być wolną przestrzeń przy użyciu tego się szczyt.

316
00:13:58,699 --> 00:14:00,490
Ale mamy zamiar utrzymać
to proste wizualnie.

317
00:14:00,490 --> 00:14:07,070
Pozwólcie mi połączyć się teraz, 1, oraz
Następnie 3, a następnie 5 i 7.

318
00:14:07,070 --> 00:14:10,740
Tym samym zostawiając mnie teraz z
Prawa połowa oryginalnego problemu

319
00:14:10,740 --> 00:14:12,840
który jest doskonale klasyfikowane.

320
00:14:12,840 --> 00:14:13,662
>> Co więc pozostaje?

321
00:14:13,662 --> 00:14:16,120
Czuję się jak zachować mówiąc
same rzeczy znowu, i znowu,

322
00:14:16,120 --> 00:14:18,700
ale to odblaskowe z
Fakt, że używamy rekursji.

323
00:14:18,700 --> 00:14:21,050
Proces stosując
Algorytm znowu, i znowu,

324
00:14:21,050 --> 00:14:23,940
mniejszych podgrup
oryginalny problemem.

325
00:14:23,940 --> 00:14:27,580
Więc teraz mam lewy klasyfikowane
połowy pierwotnej problemu.

326
00:14:27,580 --> 00:14:30,847
Mam prawo posortowaną połowę
pierwotnego problemu.

327
00:14:30,847 --> 00:14:32,180
Co znajduje się w trzecim i ostatnim krokiem?

328
00:14:32,180 --> 00:14:33,590
Och, to połączenie.

329
00:14:33,590 --> 00:14:34,480
Więc zróbmy to.

330
00:14:34,480 --> 00:14:36,420
Miejmy przeznaczyć pewne dodatkowe
pamięci, ale mój Boże,

331
00:14:36,420 --> 00:14:37,503
może go umieścić w dowolnym miejscu teraz.

332
00:14:37,503 --> 00:14:40,356
Mamy tak wiele miejsca dostępne
do nas, ale my keep it simple.

333
00:14:40,356 --> 00:14:42,730
Zamiast iść do tyłu i
dalej z naszym oryginalnym pamięci,

334
00:14:42,730 --> 00:14:44,480
Zróbmy to
wizualnie dół poniżej,

335
00:14:44,480 --> 00:14:47,240
aby zakończyć się scalanie
Lewa połowa i prawa połowa.

336
00:14:47,240 --> 00:14:49,279
>> Tak więc w wyniku połączenia, co muszę zrobić?

337
00:14:49,279 --> 00:14:50,820
Chcę zabrać elementy w porządku.

338
00:14:50,820 --> 00:14:53,230
Więc patrząc na lewej połowie,
Widzę, że pierwsza liczba to 2.

339
00:14:53,230 --> 00:14:55,230
Patrzę na prawej połowie,
Widzę pierwszy numer

340
00:14:55,230 --> 00:14:58,290
wynosi 1, więc oczywiście, które
Numer chcę się wyrwać,

341
00:14:58,290 --> 00:15:00,430
i umieścić pierwszy w moim ostatnim liście?

342
00:15:00,430 --> 00:15:01,449
Oczywiście, 1.

343
00:15:01,449 --> 00:15:02,990
Teraz chcę zadać to samo pytanie.

344
00:15:02,990 --> 00:15:05,040
Na lewej połowie, mam
wciąż mam numer 2.

345
00:15:05,040 --> 00:15:07,490
Na prawej połowie
Mam numer 3.

346
00:15:07,490 --> 00:15:08,930
Który z nich chcę wybrać?

347
00:15:08,930 --> 00:15:11,760
Oczywiście, numer 2 A
teraz zauważyć kandydatów

348
00:15:11,760 --> 00:15:13,620
są 4 po lewej stronie, 3 po prawej stronie.

349
00:15:13,620 --> 00:15:15,020
Powiedzmy, oczywiście, wybrać 3.

350
00:15:15,020 --> 00:15:18,020
Teraz kandydaci są 4 na
lewa, 5 po prawej stronie.

351
00:15:18,020 --> 00:15:19,460
My, oczywiście, wybrać 4.

352
00:15:19,460 --> 00:15:21,240
6 w lewo, 5 po prawej stronie.

353
00:15:21,240 --> 00:15:22,730
My, oczywiście, wybrać 5.

354
00:15:22,730 --> 00:15:25,020
6 w lewo, 7 na prawo.

355
00:15:25,020 --> 00:15:29,320
Wybieramy 6, a potem
wybrać 7, a następnie wybieramy 8.

356
00:15:29,320 --> 00:15:30,100
Voila.

357
00:15:30,100 --> 00:15:34,370
>> Tak ogromna ilość słów później,
są klasyfikowane do tej listy ośmiu elementów

358
00:15:34,370 --> 00:15:38,450
w liście od jeden do osiem,
który jest zwiększenie z każdym krokiem,

359
00:15:38,450 --> 00:15:40,850
ale ile czasu tak
zajmie nam to zrobić.

360
00:15:40,850 --> 00:15:43,190
Cóż mam celowo
ułożone rzeczy z obrazowo

361
00:15:43,190 --> 00:15:46,330
tutaj, tak, że możemy rodzaju
zobaczyć i docenić podział

362
00:15:46,330 --> 00:15:49,060
w zdobywaniu, że się działo.

363
00:15:49,060 --> 00:15:52,830
>> Rzeczywiście, jeśli spojrzeć na ślad,
Zostawiłam wszystkie z tych linii przerywanych

364
00:15:52,830 --> 00:15:55,660
w posiadaczy miejsce, można,
rodzaj, zobaczyć, w odwrotnej kolejności,

365
00:15:55,660 --> 00:15:58,800
jeśli rodzaj spojrzeć w
Historia teraz, moja oryginalna lista

366
00:15:58,800 --> 00:16:00,250
Jest, oczywiście, od wielkości 8.

367
00:16:00,250 --> 00:16:03,480
A następnie wcześniej, byłem
do czynienia z dwoma listami wielkości 4,

368
00:16:03,480 --> 00:16:08,400
a następnie cztery listy wielkości 2,
a następnie osiem list wielkości 1.

369
00:16:08,400 --> 00:16:10,151
>> Więc co to robi,
rodzaj, przypomina?

370
00:16:10,151 --> 00:16:11,858
Cóż, rzeczywiście, każdy z
algorytmy mamy

371
00:16:11,858 --> 00:16:14,430
spojrzał na tak daleko, gdzie
dzielenie i dzielenie i dzielenie,

372
00:16:14,430 --> 00:16:19,500
zachować o rzeczy jeszcze raz, i
znowu, skutkuje tym ogólnej idei.

373
00:16:19,500 --> 00:16:23,100
I tak jest coś
logarytmiczna tutaj dzieje.

374
00:16:23,100 --> 00:16:26,790
I to nie dość log n, ale
jest składnikiem logarytmiczna

375
00:16:26,790 --> 00:16:28,280
do tego, co właśnie zrobił.

376
00:16:28,280 --> 00:16:31,570
>> Rozważmy teraz, jak to jest w rzeczywistości.

377
00:16:31,570 --> 00:16:34,481
Więc zalogować n, znowu
wielki czas pracy,

378
00:16:34,481 --> 00:16:36,980
gdy zrobiliśmy coś jak
przeszukiwanie binarne, jak teraz nazywają,

379
00:16:36,980 --> 00:16:40,090
strategia dziel i rządź
poprzez które znaleźliśmy Mike Smith.

380
00:16:40,090 --> 00:16:41,020
Teraz technicznie.

381
00:16:41,020 --> 00:16:43,640
To baza log 2 n, nawet
choć w większości klas matematycznych,

382
00:16:43,640 --> 00:16:45,770
10 jest zazwyczaj baza, że ​​można zakładać.

383
00:16:45,770 --> 00:16:48,940
Ale informatycy prawie zawsze
myśleć i mówić w kategoriach podstawy 2,

384
00:16:48,940 --> 00:16:52,569
tak na ogół po prostu powiedzieć dziennik
n, zamiast bazy log2 n

385
00:16:52,569 --> 00:16:55,110
ale są dokładnie jeden i ten
same w świecie komputera

386
00:16:55,110 --> 00:16:57,234
nauki, a na marginesie,
jest stałym czynnikiem

387
00:16:57,234 --> 00:17:01,070
Różnica między nimi, dlatego
Moot tak, więcej powodów formalnych.

388
00:17:01,070 --> 00:17:04,520
>> Ale teraz, co dbamy
o to w tym przykładzie.

389
00:17:04,520 --> 00:17:08,520
Więc niech nie udowodnienia przez przykład, ale w
przynajmniej używać przykład numerów

390
00:17:08,520 --> 00:17:10,730
pod ręką jako test dla pewności, jeśli będzie.

391
00:17:10,730 --> 00:17:14,510
Więc wcześniej formuła była baza dziennika
2 n, n, ale to, co jest w tym przypadku.

392
00:17:14,510 --> 00:17:18,526
Miałem n oryginalne numery, lub 8
od liczby oryginalnym specjalnie.

393
00:17:18,526 --> 00:17:20,359
Teraz to już trochę
jednocześnie, ale jestem

394
00:17:20,359 --> 00:17:25,300
upewnić się, że baza log 2
wartości 8 wynosi 3,

395
00:17:25,300 --> 00:17:29,630
i rzeczywiście, co jest miłe o tym jest
3, który jest dokładnie szereg razy

396
00:17:29,630 --> 00:17:33,320
które można podzielić listę
o długości 8 znowu, i znowu,

397
00:17:33,320 --> 00:17:36,160
i znowu, dopóki jesteś w lewo
z listami tylko wielkości 1.

398
00:17:36,160 --> 00:17:36,660
Dobrze?

399
00:17:36,660 --> 00:17:40,790
8 przechodzi do 4, przechodzi do 2,
idzie do 1, a to

400
00:17:40,790 --> 00:17:43,470
odzwierciedla dokładnie to
obraz mieliśmy przed chwilą.

401
00:17:43,470 --> 00:17:47,160
Więc trochę zdrowego rozsądku, aby sprawdzić, gdzie
logarytm jest rzeczywiście zaangażowana.

402
00:17:47,160 --> 00:17:50,180
>> Więc teraz, co jeszcze jest zaangażowany tutaj? n.

403
00:17:50,180 --> 00:17:53,440
Tak więc zauważyć, że każdy
Czas podzielić listę,

404
00:17:53,440 --> 00:17:58,260
choć w odwrotnej kolejności w historii
tutaj, ja wciąż robi n rzeczy.

405
00:17:58,260 --> 00:18:02,320
To połączenie krokiem wymagane,
I dotknąć każdego z numerów,

406
00:18:02,320 --> 00:18:05,060
aby wsunąć ją na
jego właściwe miejsce.

407
00:18:05,060 --> 00:18:10,760
Dlatego, mimo że wysokość tego
Schemat jest od wielkości dziennika n n lub 3,

408
00:18:10,760 --> 00:18:13,860
W szczególności, innymi słowy
Zrobiłem trzy dywizje tutaj.

409
00:18:13,860 --> 00:18:18,800
Ile pracy zrobiłem poziomo
wzdłuż tej tabeli za każdym razem?

410
00:18:18,800 --> 00:18:21,110
>> Cóż, ja n kroki
pracować, bo jeśli mam

411
00:18:21,110 --> 00:18:24,080
dostał cztery żywioły i cztery żywioły,
i muszę połączyć je razem.

412
00:18:24,080 --> 00:18:26,040
Muszę przejść przez
te cztery, a te cztery,

413
00:18:26,040 --> 00:18:28,123
ostatecznie je połączyć
z powrotem do ośmiu elementów.

414
00:18:28,123 --> 00:18:32,182
Jeśli przeciwnie mam osiem palców
tu, czego nie robić, a osiem

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- Jeśli mam
ma cztery palce tutaj,

416
00:18:34,390 --> 00:18:37,380
które robię, cztery palce
tu, co robię,

417
00:18:37,380 --> 00:18:40,590
to jest to samo
Przykładem, jak wcześniej, jeśli to zrobię

418
00:18:40,590 --> 00:18:44,010
osiem palców choć w
Łączna, które mogą, rodzaj, zrobić.

419
00:18:44,010 --> 00:18:47,950
Mogę dokładnie zrobić tutaj,
to mogę z pewnością

420
00:18:47,950 --> 00:18:50,370
połączyć wszystkie z tych list
wielkości 1 razem.

421
00:18:50,370 --> 00:18:54,050
Ale na pewno trzeba szukać
na każdy element dokładnie raz.

422
00:18:54,050 --> 00:18:59,640
Tak więc wysokość tego procesu jest log n,
szerokość tego procesu, by tak rzec,

423
00:18:59,640 --> 00:19:02,490
jest n, więc to, co wydaje się
aby ostatecznie jest

424
00:19:02,490 --> 00:19:06,470
czas działa od wielkości n razy log n.

425
00:19:06,470 --> 00:19:08,977
>> Innymi słowy, podzielone
lista, log n razy,

426
00:19:08,977 --> 00:19:11,810
ale za każdym razem, gdy to zrobił, mieliśmy
dotknąć każdego z elementów

427
00:19:11,810 --> 00:19:13,560
aby je połączyć
razem, co

428
00:19:13,560 --> 00:19:18,120
został n krok, więc mamy n razy log n,
lub jako informatyk powie,

429
00:19:18,120 --> 00:19:20,380
asymptotycznie, które
byłoby wielkie słowo

430
00:19:20,380 --> 00:19:22,810
opisać górny
zobowiązany na czas pracy,

431
00:19:22,810 --> 00:19:28,010
prowadzimy w Big O
log n czas, że tak powiem.

432
00:19:28,010 --> 00:19:31,510
>> Obecnie jest to istotne, ponieważ
przypomnieć sobie czasy uruchomione były

433
00:19:31,510 --> 00:19:34,120
z bańki sortowania i selekcji
sortowanie i Sortowanie przez wstawianie,

434
00:19:34,120 --> 00:19:38,200
i jeszcze kilka innych, które istnieją,
n do kwadratu było gdzie byliśmy.

435
00:19:38,200 --> 00:19:39,990
I może, rodzaj, zobaczyć tutaj.

436
00:19:39,990 --> 00:19:45,720
Jeśli n do kwadratu jest oczywiście n razy
n, ale tutaj mamy n razy log n,

437
00:19:45,720 --> 00:19:48,770
i wiemy już od tygodnia
zero, że log n, logarytmiczna,

438
00:19:48,770 --> 00:19:50,550
jest lepsze niż coś liniowych.

439
00:19:50,550 --> 00:19:52,930
Po tym wszystkim, przywołać obraz
z czerwonym i żółtym

440
00:19:52,930 --> 00:19:56,500
i zielone linie, które sporządziły, tym
Zielona linia logarytmiczna była znacznie niższa.

441
00:19:56,500 --> 00:20:00,920
I w związku z tym, o wiele lepiej i szybciej
od prostych linii żółtych i czerwonych,

442
00:20:00,920 --> 00:20:05,900
n razy log n jest rzeczywiście lepsza
niż n razy n lub n do kwadratu.

443
00:20:05,900 --> 00:20:09,110
>> Tak więc wydaje się, że
zidentyfikowali seryjnej algorytmu

444
00:20:09,110 --> 00:20:11,870
sortowania, który działa w znacznie
krótszy czas, i rzeczywiście,

445
00:20:11,870 --> 00:20:16,560
dlatego, na początku tego tygodnia, kiedy
Widzieliśmy, że konkurs między bańki

446
00:20:16,560 --> 00:20:20,750
sortowanie, wybór rodzaju i połączyć
sortowania, sortowanie przez scalanie naprawdę wygrał.

447
00:20:20,750 --> 00:20:23,660
I rzeczywiście, my nawet nie czekaj
dla bubble rodzaju i wyboru rodzaju

448
00:20:23,660 --> 00:20:24,790
skończyć.

449
00:20:24,790 --> 00:20:27,410
>> Teraz rzućmy jeszcze jedną przepustkę
na to, z nieco bardziej

450
00:20:27,410 --> 00:20:31,030
formalnego punktu widzenia, tylko w
Sprawa ta rezonuje lepiej

451
00:20:31,030 --> 00:20:33,380
od tej wyższej dyskusji na poziomie.

452
00:20:33,380 --> 00:20:34,880
Więc oto kolejny algorytm.

453
00:20:34,880 --> 00:20:36,770
Zapytajmy siebie,
co czas pracy

454
00:20:36,770 --> 00:20:39,287
jest to algorytmy różne kroki?

455
00:20:39,287 --> 00:20:41,620
Załóżmy, podzielić go na pierwszym
sprawa, a druga sprawa.

456
00:20:41,620 --> 00:20:46,280
IF, a inny w przypadku, gdy,
Jeśli n jest mniejsza niż 2, po prostu wrócić.

457
00:20:46,280 --> 00:20:47,580
Czuję się jak w czasie stałym.

458
00:20:47,580 --> 00:20:50,970
To, rodzaj, podobnie jak w dwóch etapach,
Jeśli n jest mniejsza niż 2, a następnie powrót.

459
00:20:50,970 --> 00:20:54,580
Ale jak powiedział w poniedziałek,
stałą czasową, lub duże o 1,

460
00:20:54,580 --> 00:20:57,130
może być dwa kroki, trzy
kroki, a nawet 1000 kroków.

461
00:20:57,130 --> 00:20:59,870
Liczy się to, że jest to
stałą liczbę kroków.

462
00:20:59,870 --> 00:21:03,240
Więc żółte podświetlone Pseudokod
tutaj przebiega, będziemy go nazywać,

463
00:21:03,240 --> 00:21:04,490
Stała czasowa.

464
00:21:04,490 --> 00:21:06,780
Więc bardziej formalnie, a
jedziemy to-- to

465
00:21:06,780 --> 00:21:09,910
będzie zakres, w którym
sformalizowanie tego prawo now-- T n,

466
00:21:09,910 --> 00:21:15,030
czas pracy na problem
że bierze n latków jako wejście,

467
00:21:15,030 --> 00:21:19,150
równa się duża o jednej,
Gdy n jest mniejsze niż 2.

468
00:21:19,150 --> 00:21:20,640
Więc jest to uzależnione od tego.

469
00:21:20,640 --> 00:21:24,150
Więc być jasne, jeśli N jest mniejsza niż
2, mamy bardzo krótką listę, a następnie

470
00:21:24,150 --> 00:21:29,151
czas pracy, T n, gdzie n jest
1 lub 0, w tym konkretnym przypadku,

471
00:21:29,151 --> 00:21:30,650
to jest po prostu będzie stała czasowa.

472
00:21:30,650 --> 00:21:32,691
To zajmie jeden
krok, dwa kroki, cokolwiek.

473
00:21:32,691 --> 00:21:33,950
Jest to stała liczba kroków.

474
00:21:33,950 --> 00:21:38,840
>> Więc soczyste część na pewno musi być w
drugi przypadek w Pseudokod.

475
00:21:38,840 --> 00:21:40,220
W przypadku innego.

476
00:21:40,220 --> 00:21:44,870
Sortuj lewa połowa elementów, sortowanie prawo
połowa elementów, łączenia połówek posortowane.

477
00:21:44,870 --> 00:21:46,800
Jak długo każdy z tych etapów ma?

478
00:21:46,800 --> 00:21:49,780
Cóż, jeśli działa
czas, aby uporządkować elementy n

479
00:21:49,780 --> 00:21:53,010
jest, nazwijmy to bardzo
ogólnie, T n,

480
00:21:53,010 --> 00:21:55,500
następnie sortowanie lewo
połowa elementów

481
00:21:55,500 --> 00:21:59,720
to, rodzaj, jak mówi,
T n dzieli się przez 2,

482
00:21:59,720 --> 00:22:03,000
i podobnie sortowania prawą połowę
elementów jest trochę, jakby powiedzieć,

483
00:22:03,000 --> 00:22:06,974
T n dzieli 2, a następnie
scalenie posortowane połówki.

484
00:22:06,974 --> 00:22:08,890
Cóż, jeśli mam niektóre
Liczba elementów tutaj

485
00:22:08,890 --> 00:22:11,230
jak cztery, a niektóre liczby
elementów tutaj, podobnie jak cztery,

486
00:22:11,230 --> 00:22:14,650
i muszę połączyć każdy z tych czterech
W, a każdy z tych czterech, jedna

487
00:22:14,650 --> 00:22:17,160
Po drugie, dzięki czemu
ostatecznie mam osiem elementów.

488
00:22:17,160 --> 00:22:20,230
Czuje się jak to jest duże o n krokach?

489
00:22:20,230 --> 00:22:23,500
Jeśli mam n palce i każdy z
im ma być połączone w miejscu,

490
00:22:23,500 --> 00:22:25,270
to jak kolejne etapy n.

491
00:22:25,270 --> 00:22:27,360
>> Więc rzeczywiście formulaically,
możemy wyrazić to,

492
00:22:27,360 --> 00:22:29,960
choć trochę przerażająco w pierwszym
rzut oka, ale to jest coś

493
00:22:29,960 --> 00:22:31,600
która rejestruje dokładnie tę logikę.

494
00:22:31,600 --> 00:22:35,710
Czas pracy, T n, gdy n
jest większa niż lub równa 2.

495
00:22:35,710 --> 00:22:42,500
W tym przypadku, w przypadku innego, T n
podzielić przez 2, oraz T n dzieli się przez 2,

496
00:22:42,500 --> 00:22:45,320
oraz Big O n, niektóre
numer liniowy kroki,

497
00:22:45,320 --> 00:22:51,630
być może dokładnie n, może 2 razy
n, ale jest to mniej więcej, kolejność n.

498
00:22:51,630 --> 00:22:54,060
Więc to też jest, jak się da
wyrazić formulaically.

499
00:22:54,060 --> 00:22:56,809
Teraz nie wiem, to chyba
już nagrał ją w swoim umyśle,

500
00:22:56,809 --> 00:22:58,710
lub wyszukać go w
z tyłu podręcznika, które

501
00:22:58,710 --> 00:23:00,501
może mieć trochę
Ściągawka na końcu,

502
00:23:00,501 --> 00:23:03,940
ale to jest rzeczywiście będzie
dają nam duży o n log n,

503
00:23:03,940 --> 00:23:06,620
ponieważ nawroty, że
widzisz tu na ekranie,

504
00:23:06,620 --> 00:23:09,550
jeśli faktycznie go z
nieskończenie wiele przykładów,

505
00:23:09,550 --> 00:23:13,000
czy to zrobiłeś formulaically, byś
zobaczyć, że to, bo tego wzoru

506
00:23:13,000 --> 00:23:17,100
Sam jest rekurencyjne, z t
n na coś po prawej stronie,

507
00:23:17,100 --> 00:23:21,680
a t n na po lewej stronie, może to
rzeczywiście być wyrażona, w ostatecznym rozrachunku,

508
00:23:21,680 --> 00:23:24,339
tak duża, przejdź n log n.

509
00:23:24,339 --> 00:23:26,130
Jeśli nie przekonany, że to
dobrze teraz, po prostu

510
00:23:26,130 --> 00:23:28,960
przyjąć na wiarę, że to, w istocie,
co powoduje, że nawroty,

511
00:23:28,960 --> 00:23:31,780
ale jest to tylko nieco więcej
matematyczne podejście do patrzenia

512
00:23:31,780 --> 00:23:36,520
w czasie trwania sortowanie przez scalanie
oparciu o Pseudokod sam.

513
00:23:36,520 --> 00:23:39,030
>> Teraz rzućmy trochę
odpowietrznik od wszystkich, że,

514
00:23:39,030 --> 00:23:41,710
i spojrzeć na
pewne, były senator, który

515
00:23:41,710 --> 00:23:44,260
może wyglądać trochę znajomo,
który usiadł z Google Eric

516
00:23:44,260 --> 00:23:48,410
Schmidt, jakiś czas temu, w jednym z wywiadów
na scenie, przed całym gronem

517
00:23:48,410 --> 00:23:53,710
ludzi, rozmawiając ostatecznie o
to temat, który dość już znane.

518
00:23:53,710 --> 00:23:54,575
Spójrzmy.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> Eric Schmidt: Teraz senator,
jesteś tutaj w Google,

521
00:24:03,890 --> 00:24:09,490
i lubię myśleć o
Prezydencja w rozmowie kwalifikacyjnej.

522
00:24:09,490 --> 00:24:11,712
Teraz trudno jest dostać pracę jako prezydenta.

523
00:24:11,712 --> 00:24:12,670
Prezydent Obama: Racja.

524
00:24:12,670 --> 00:24:13,940
Eric Schmidt: A ty jesteś
zrobi [niesłyszalne] teraz.

525
00:24:13,940 --> 00:24:15,523
Trudno też, aby dostać pracę w Google.

526
00:24:15,523 --> 00:24:17,700
Prezydent Obama: Racja.

527
00:24:17,700 --> 00:24:21,330
>> Eric Schmidt: Mamy pytania,
i prosi swoich kandydatów pytania,

528
00:24:21,330 --> 00:24:24,310
a ten jest z Larrym Schwimmer.

529
00:24:24,310 --> 00:24:25,890
>> Prezydent Obama: OK.

530
00:24:25,890 --> 00:24:27,005
>> Eric Schmidt: Co?

531
00:24:27,005 --> 00:24:28,130
Myślicie, że żartuję?

532
00:24:28,130 --> 00:24:30,590
To właśnie tutaj.

533
00:24:30,590 --> 00:24:33,490
Jaki jest najbardziej efektywny sposób
sortować milion 32-bitowe liczby całkowite?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> Prezydent Obama: Well--

536
00:24:38,979 --> 00:24:41,020
Eric Schmidt: Czasami,
Może mi przykro, maybe--

537
00:24:41,020 --> 00:24:42,750
Prezydent Obama: Nie, nie,
nie, nie, nie, ja think--

538
00:24:42,750 --> 00:24:43,240
Eric Schmidt: To nie it--

539
00:24:43,240 --> 00:24:45,430
Prezydent Obama: I
myślę, myślę, że bańki

540
00:24:45,430 --> 00:24:46,875
Sortuj byłoby złym rozwiązaniem.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
Eric Schmidt: Chodź.

543
00:24:50,535 --> 00:24:52,200
Kto powiedział mu to?

544
00:24:52,200 --> 00:24:54,020
OK.

545
00:24:54,020 --> 00:24:55,590
Nie zrobił informatyka on--

546
00:24:55,590 --> 00:24:58,986
>> Prezydent Obama: Mamy
Dostaliśmy nasze szpiegów tam.

547
00:24:58,986 --> 00:24:59,860
PROFESOR: Wszystko w porządku.

548
00:24:59,860 --> 00:25:03,370
Zostawmy za nami teraz
teoretyczna świecie algorytmów

549
00:25:03,370 --> 00:25:06,520
w asymptotycznej analizy
jego, i powrócić do niektórych tematów

550
00:25:06,520 --> 00:25:09,940
od tygodnia zera do jedności, a początek
usunąć niektóre koła szkolenia,

551
00:25:09,940 --> 00:25:10,450
Jeśli będziesz.

552
00:25:10,450 --> 00:25:13,241
Tak, że naprawdę można zrozumieć
ostatecznie od podstaw, co jest

553
00:25:13,241 --> 00:25:16,805
dzieje się pod maską, kiedy
Napisać, kompilacji i uruchamiania programów.

554
00:25:16,805 --> 00:25:19,680
Przypomnijmy, w szczególności, że było to
pierwszy program w C przyjrzeliśmy się,

555
00:25:19,680 --> 00:25:22,840
kanoniczna, prosty program
rodzajów, relatywnie rzecz biorąc,

556
00:25:22,840 --> 00:25:24,620
w którym, drukuje, Hello World.

557
00:25:24,620 --> 00:25:27,610
I przypominam, że powiedziałem, proces
że kod źródłowy przechodzi

558
00:25:27,610 --> 00:25:28,430
jest dokładnie to.

559
00:25:28,430 --> 00:25:31,180
Bierzesz kodu źródłowego, przechodzą
to przez kompilator, jak Clang,

560
00:25:31,180 --> 00:25:34,650
i obecnie jest kod obiektu, który
może wyglądać tak, zer i jedynek

561
00:25:34,650 --> 00:25:37,880
że procesor komputera, centralne
Jednostka przetwarzania lub mózgu,

562
00:25:37,880 --> 00:25:39,760
w końcu zrozumie.

563
00:25:39,760 --> 00:25:42,460
>> Okazuje się, że to jest
trochę w uproszczeniu,

564
00:25:42,460 --> 00:25:44,480
że jesteśmy teraz w sposób
Pozycja na celu wyodrębnienie

565
00:25:44,480 --> 00:25:46,720
aby zrozumieć, co tak naprawdę było
dzieje się pod maską

566
00:25:46,720 --> 00:25:48,600
przy każdym uruchomieniu
Szczęk, albo bardziej ogólnie

567
00:25:48,600 --> 00:25:53,040
za każdym razem zrobić program,
przy użyciu Marka i CF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
W szczególności, takie rzeczy
Jest to pierwszy generowane

569
00:25:56,760 --> 00:25:58,684
kiedy po raz pierwszy skompilować program.

570
00:25:58,684 --> 00:26:00,600
Innymi słowy, kiedy
wziąć swój kod źródłowy

571
00:26:00,600 --> 00:26:04,390
i skompilować go, co jest pierwszym
jest przesyłany przez Clang

572
00:26:04,390 --> 00:26:06,370
jest coś, znany jako kod montażowej.

573
00:26:06,370 --> 00:26:08,990
I rzeczywiście, wygląda dokładnie tak jak ten.

574
00:26:08,990 --> 00:26:11,170
>> Pobiegłem polecenie w
wiersz poleceń wcześniej.

575
00:26:11,170 --> 00:26:16,260
Clang Dash stolicy s hello.c,
i to utworzony plik

576
00:26:16,260 --> 00:26:19,490
dla mnie zwanych hello.s,
wewnątrz którego były dokładnie

577
00:26:19,490 --> 00:26:22,290
te treści, a trochę więcej
wyżej i trochę więcej poniżej,

578
00:26:22,290 --> 00:26:25,080
ale ja umieścić juiciest
Informacje tu na ekranie.

579
00:26:25,080 --> 00:26:29,190
A jeśli przyjrzeć się bliżej, zobaczysz
co najmniej kilka znanych słów kluczowych.

580
00:26:29,190 --> 00:26:31,330
Mamy głównym na górze.

581
00:26:31,330 --> 00:26:35,140
Mamy printf w środku.

582
00:26:35,140 --> 00:26:38,670
I mamy też hello world
odwrotny ukośnik n w cudzysłowie dół poniżej.

583
00:26:38,670 --> 00:26:42,450
>> I wszystko inne tutaj
Instrukcja jest na bardzo niskim poziomie

584
00:26:42,450 --> 00:26:45,500
że procesor komputera rozumie.

585
00:26:45,500 --> 00:26:50,090
Instrukcje CPU, które poruszają pamięci
się, że struny obciążeń w pamięci,

586
00:26:50,090 --> 00:26:52,750
i ostatecznie, do druku
rzeczy na ekranie.

587
00:26:52,750 --> 00:26:56,780
Teraz to, co się stanie, jeśli po
Zespół ten kod generowany jest?

588
00:26:56,780 --> 00:26:59,964
Ostatecznie możesz zrobić, rzeczywiście,
nadal generować kod wynikowy.

589
00:26:59,964 --> 00:27:02,630
Ale kroki, które mają naprawdę
toczy się pod maską

590
00:27:02,630 --> 00:27:04,180
wygląda trochę bardziej tak.

591
00:27:04,180 --> 00:27:08,390
Kod źródłowy staje się kod montaż,
Kod, który staje się przedmiotem,

592
00:27:08,390 --> 00:27:11,930
i zeby słowa są tu, że
podczas kompilacji kodu źródłowego,

593
00:27:11,930 --> 00:27:16,300
obecnie jest kod montaż, a następnie
podczas montażu kod montażu,

594
00:27:16,300 --> 00:27:17,800
obecnie jest kod wynikowy.

595
00:27:17,800 --> 00:27:20,360
>> Teraz Clang jest super zaawansowany,
jak wiele kompilatorów,

596
00:27:20,360 --> 00:27:23,151
i to nie wszystkie z tych etapów
razem, a niekoniecznie

597
00:27:23,151 --> 00:27:25,360
Wyjście pośredniego
pliki, które można nawet zobaczyć.

598
00:27:25,360 --> 00:27:28,400
To po prostu kompiluje rzeczy,
który jest ogólny termin

599
00:27:28,400 --> 00:27:30,000
opisuje cały ten proces.

600
00:27:30,000 --> 00:27:32,000
Ale jeśli naprawdę chcesz
być szczególnie tam

601
00:27:32,000 --> 00:27:34,330
o wiele więcej dzieje się również tam.

602
00:27:34,330 --> 00:27:38,860
>> Ale niech też uważają teraz, że nawet
że bardzo prosty program, hello.c,

603
00:27:38,860 --> 00:27:40,540
nazywa się funkcją.

604
00:27:40,540 --> 00:27:41,870
To nazywa się printf.

605
00:27:41,870 --> 00:27:46,900
Ale ja nie napisałem printf, rzeczywiście,
że pochodzi z, c, że tak powiem.

606
00:27:46,900 --> 00:27:51,139
To wycofanie funkcja to
zadeklarowane w standardowym io.h, które

607
00:27:51,139 --> 00:27:53,180
plik jest nagłówek, który
Jest to temat, będziemy rzeczywiście

608
00:27:53,180 --> 00:27:55,780
zanurzyć się głębiej niebawem.

609
00:27:55,780 --> 00:27:58,000
Ale plik nagłówka jest
zwykle towarzyszy

610
00:27:58,000 --> 00:28:02,920
przez plik kodu źródłowego, pliku kodu, tak
podobnie jak istnieje standardowy io.h.

611
00:28:02,920 --> 00:28:05,930
>> Jakiś czas temu ktoś,
lub czyjąś, napisał

612
00:28:05,930 --> 00:28:11,040
plik o nazwie Standard io.c, w
które opiszemy,

613
00:28:11,040 --> 00:28:15,220
lub implementacje printf,
i kiście innych funkcji,

614
00:28:15,220 --> 00:28:16,870
nie zostaną zapisane.

615
00:28:16,870 --> 00:28:22,140
Tak więc biorąc pod uwagę, że, jeśli weźmiemy pod uwagę konieczności
tu w lewo, hello.c, że kiedy

616
00:28:22,140 --> 00:28:26,250
kompilowane, daje nam hello.s, nawet jeśli
Clang nie przeszkadza oszczędności w miejscu

617
00:28:26,250 --> 00:28:31,360
możemy ją zobaczyć, i że kod montaż
zostanie złożone w hello.o, które

618
00:28:31,360 --> 00:28:34,630
jest, rzeczywiście, domyślna nazwa
biorąc pod uwagę, kiedy tylko skompilować źródła

619
00:28:34,630 --> 00:28:39,350
kod na kod obiektu, ale nie są
dość gotowy do wykonania tego jeszcze,

620
00:28:39,350 --> 00:28:41,460
bo innego kroku
musi się wydarzyć, i ma

621
00:28:41,460 --> 00:28:44,440
wydarzyło się w ciągu ostatnich kilku
tygodnie, być może nie wiemy o was.

622
00:28:44,440 --> 00:28:47,290
>> Konkretnie gdzieś
w CS50 IDE, i to,

623
00:28:47,290 --> 00:28:49,870
też będzie trochę w
uproszczenie na chwilę,

624
00:28:49,870 --> 00:28:54,670
nie jest, lub był, dawno temu,
plik o nazwie Standard io.c,

625
00:28:54,670 --> 00:28:58,440
że ktoś kompilowane do
Standardowe io.s lub równoważne,

626
00:28:58,440 --> 00:29:02,010
że ktoś to zmontowane
do standardowego io.o,

627
00:29:02,010 --> 00:29:04,600
lub okaże się w
nieco inny plik

628
00:29:04,600 --> 00:29:07,220
format, który może mieć różny
rozszerzenie pliku w ogóle,

629
00:29:07,220 --> 00:29:11,720
ale w teorii i koncepcyjnie, dokładnie
te kroki, musiało się zdarzyć w jakiejś formie.

630
00:29:11,720 --> 00:29:14,060
To znaczy, że teraz
kiedy piszę program,

631
00:29:14,060 --> 00:29:17,870
hello.c, że po prostu mówi, hello world,
i używam kod cudzego

632
00:29:17,870 --> 00:29:22,480
jak printf, która była kiedyś na Dzikim
Czas, w pliku o nazwie Standard io.c,

633
00:29:22,480 --> 00:29:26,390
potem jakoś muszę wziąć moje
Kod obiektu, moje zer i jedynek,

634
00:29:26,390 --> 00:29:29,260
i przedmiot tej osoby
kodu lub zer i jedynek,

635
00:29:29,260 --> 00:29:34,970
i jakoś połączyć je ze sobą w
jeden końcowy plik o nazwie hello, że

636
00:29:34,970 --> 00:29:38,070
ma wszystkie zera i
te z mojej podstawowej funkcji,

637
00:29:38,070 --> 00:29:40,830
i wszystkie zera
i te, dla printf.

638
00:29:40,830 --> 00:29:44,900
>> I rzeczywiście, ten ostatni proces jest
nazywa, łącząc swój kod wynikowy.

639
00:29:44,900 --> 00:29:47,490
Którego wyjście
jest to plik wykonywalny.

640
00:29:47,490 --> 00:29:49,780
Więc w sprawiedliwości, u
koniec dnia, nic

641
00:29:49,780 --> 00:29:52,660
zmieniła się od jednego tygodnia, kiedy
Pierwszy rozpoczął kompilacji programów.

642
00:29:52,660 --> 00:29:55,200
W istocie, wszystko to jest
dzieje się pod maską,

643
00:29:55,200 --> 00:29:57,241
ale teraz jesteśmy w stanie
gdzie możemy rzeczywiście

644
00:29:57,241 --> 00:29:58,794
odciąć te różne kroki.

645
00:29:58,794 --> 00:30:00,710
I rzeczywiście, w celu
dnia, wciąż jesteśmy

646
00:30:00,710 --> 00:30:04,480
lewo z zer i jedynek, które
jest rzeczywiście wielki segue teraz

647
00:30:04,480 --> 00:30:08,620
z inną możliwością C, to
nie miałem wykorzystać najbardziej prawdopodobne

648
00:30:08,620 --> 00:30:11,250
do tej pory znany jako operatory bitowe.

649
00:30:11,250 --> 00:30:15,220
Innymi słowy, jak dotąd, w każdej chwili mamy
do czynienia z danymi w C lub zmiennych w C,

650
00:30:15,220 --> 00:30:17,660
mieliśmy takie rzeczy jak
znaków i pływaki oraz ins

651
00:30:17,660 --> 00:30:21,990
i tęskni i dwuosobowe i tym podobne, ale
wszystkie te są co najmniej osiem bitów.

652
00:30:21,990 --> 00:30:25,550
Nigdy nie jeszcze w stanie
manipulować poszczególnych bitów,

653
00:30:25,550 --> 00:30:28,970
chociaż pojedynczego bitu, że
wie, może reprezentować 0 i 1.

654
00:30:28,970 --> 00:30:32,640
Teraz okazuje się, że w C, to
Można uzyskać dostęp do poszczególnych bitów,

655
00:30:32,640 --> 00:30:35,530
jeśli wiesz, składni,
z którym, aby dostać się do nich.

656
00:30:35,530 --> 00:30:38,010
>> Warto więc spojrzeć
na operatorów bitowe.

657
00:30:38,010 --> 00:30:41,700
Więc na zdjęciu kilka symbole
my, rodzaj, rodzaj, widział.

658
00:30:41,700 --> 00:30:45,580
Widzę ampersanda pionowa
bar, a inne, jak również,

659
00:30:45,580 --> 00:30:49,430
i przypomnieć, że ampersand ampersanda
jest coś, czego nie widział.

660
00:30:49,430 --> 00:30:54,060
Logiczne i operatora, gdzie trzeba
dwa z nich razem, czy logiczny OR

661
00:30:54,060 --> 00:30:56,300
Operator, w którym
mają dwa pionowe pasy.

662
00:30:56,300 --> 00:31:00,550
Operatory bitowe, które będziemy
zobacz działają na bitach indywidualnie,

663
00:31:00,550 --> 00:31:03,810
wystarczy użyć jednego znaku handlowego, A
pojedynczy pionowy pasek, daszek symbolem

664
00:31:03,810 --> 00:31:06,620
będzie dalej, mały
tyldy, a następnie w lewo

665
00:31:06,620 --> 00:31:08,990
Wspornik lewy wspornik, lub
prawy nawias prawy nawias.

666
00:31:08,990 --> 00:31:10,770
Każdy z nich ma różne znaczenia.

667
00:31:10,770 --> 00:31:11,950
>> W rzeczywistości, rzućmy okiem.

668
00:31:11,950 --> 00:31:16,560
Chodźmy stara szkoła dzisiaj i wykorzystanie
ekran dotykowy z przeszłości,

669
00:31:16,560 --> 00:31:18,002
znany jako tablicy.

670
00:31:18,002 --> 00:31:19,710
I to tablicy
ma umożliwić nam

671
00:31:19,710 --> 00:31:27,360
wyrazić kilka dość prostych symboli,
czy raczej niektóre dość proste wzory,

672
00:31:27,360 --> 00:31:29,560
że możemy następnie ostatecznie
dźwigni finansowej, w celu

673
00:31:29,560 --> 00:31:33,230
aby uzyskać dostęp do poszczególnych
bity w programie C.

674
00:31:33,230 --> 00:31:34,480
Innymi słowy, zróbmy to.

675
00:31:34,480 --> 00:31:37,080
Niech najpierw porozmawiać przez
Moment o ampersand,

676
00:31:37,080 --> 00:31:39,560
co jest logicznym i operatora.

677
00:31:39,560 --> 00:31:42,130
Innymi słowy, jest to
operator, który pozwala

678
00:31:42,130 --> 00:31:45,930
mnie mieć zmienną po lewej stronie
zazwyczaj, a zmienna z prawej strony,

679
00:31:45,930 --> 00:31:50,640
lub indywidualna wartość, że jeśli I
je razem, daje mi wynik końcowy.

680
00:31:50,640 --> 00:31:51,560
Więc co mam na myśli?

681
00:31:51,560 --> 00:31:54,840
Jeśli w programie, masz zmienną
która przechowuje jeden z tych wartości,

682
00:31:54,840 --> 00:31:58,000
albo niech keep it simple, i po prostu
pisać zer i jedynek indywidualnie,

683
00:31:58,000 --> 00:32:00,940
Oto jak działa operator znaku &.

684
00:32:00,940 --> 00:32:06,400
0 handlowe i 0 będzie równa 0.

685
00:32:06,400 --> 00:32:07,210
Teraz to dlaczego?

686
00:32:07,210 --> 00:32:09,291
>> Jest bardzo podobna do
Wyrażeń logicznych,

687
00:32:09,291 --> 00:32:10,540
że mamy omówione do tej pory.

688
00:32:10,540 --> 00:32:15,800
Jeśli uważasz, że po tym wszystkim, 0 jest
fałszywe, 0 false false false

689
00:32:15,800 --> 00:32:18,720
jest, jak już omówione
logicznie, również fałszywe.

690
00:32:18,720 --> 00:32:20,270
Więc mamy 0 również tutaj.

691
00:32:20,270 --> 00:32:24,390
Jeśli wziąć 0 ampersanda
1, oraz, że również

692
00:32:24,390 --> 00:32:29,890
ma wartość 0, gdyż w tym
Wyrażenie po lewej stronie, aby mogło być prawdziwe lub 1,

693
00:32:29,890 --> 00:32:32,360
to muszą być prawdziwe i prawdziwe.

694
00:32:32,360 --> 00:32:36,320
Ale tutaj mamy fałszywe
i prawdziwe, lub 0 i 1.

695
00:32:36,320 --> 00:32:42,000
Teraz znowu, jeśli mamy 1 ampersanda
0, to też będzie 0,

696
00:32:42,000 --> 00:32:47,240
a jeśli mamy 1 ampersanda 1,
w końcu mamy do 1 bit.

697
00:32:47,240 --> 00:32:50,340
Więc innymi słowy, nie robimy
coś ciekawego z tego operatora

698
00:32:50,340 --> 00:32:51,850
jeszcze, operator znaku &.

699
00:32:51,850 --> 00:32:53,780
To bitowe i operatora.

700
00:32:53,780 --> 00:32:57,290
Ale to są składniki
poprzez które możemy zrobić

701
00:32:57,290 --> 00:32:59,240
ciekawe rzeczy, jak to już wkrótce.

702
00:32:59,240 --> 00:33:02,790
>> Teraz przyjrzyjmy się tylko pojedynczy
tu pionowy pasek po prawej stronie.

703
00:33:02,790 --> 00:33:06,710
Jeśli mam 0 trochę i ja
ALBO to z, logicznym

704
00:33:06,710 --> 00:33:11,030
Operator OR, inny bit 0,
że będzie mi dać 0.

705
00:33:11,030 --> 00:33:17,540
Jeśli wezmę 0 trochę i OR go z
1-bitowe, a potem mam zamiar dostać 1.

706
00:33:17,540 --> 00:33:19,830
W rzeczywistości, tylko
jasność, pozwól mi wrócić,

707
00:33:19,830 --> 00:33:23,380
tak, że moje pionowe pasy
Nie pomylić z 1-ki.

708
00:33:23,380 --> 00:33:26,560
Pozwól mi przepisać wszystko
mój 1 trochę więcej

709
00:33:26,560 --> 00:33:32,700
wyraźnie, tak, że w przyszłym zobaczyć, jeśli
posiada 1 lub 0, że to będzie 1,

710
00:33:32,700 --> 00:33:39,060
a jeśli mam 1 lub 1, że,
także ma być 1.

711
00:33:39,060 --> 00:33:42,900
Tak więc widać, że logicznie LUB
Operator zachowuje się zupełnie inaczej.

712
00:33:42,900 --> 00:33:48,070
To daje mi 0 LUB 0 daje mi 0, ale
każda inna kombinacja daje mi 1.

713
00:33:48,070 --> 00:33:52,480
Tak długo, jak mam jeden 1 w
Wzór wynik będzie 1.

714
00:33:52,480 --> 00:33:55,580
>> Natomiast z AND
Operator, Ampersand,

715
00:33:55,580 --> 00:34:00,940
tylko wtedy, gdy mam dwie 1 jest w
Równanie, mogę rzeczywiście dostać 1.

716
00:34:00,940 --> 00:34:02,850
Teraz istnieje kilka innych
operatorzy, jak również.

717
00:34:02,850 --> 00:34:04,810
Jednym z nich jest trochę bardziej zaangażować.

718
00:34:04,810 --> 00:34:07,980
Więc pozwól mi iść do przodu i usunąć
tego, aby zwolnić trochę miejsca.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
I rzućmy okiem na
Daszek symbolem, na chwilę.

721
00:34:16,460 --> 00:34:18,210
Jest to typowo
znaków można wpisać

722
00:34:18,210 --> 00:34:21,420
na klawiaturze, przytrzymanie klawisza Shift i
to jeden z numerów na szczycie swojej USA

723
00:34:21,420 --> 00:34:22,250
klawiatura.

724
00:34:22,250 --> 00:34:26,190
>> Więc to jest wyłącznym
Operator OR, XOR.

725
00:34:26,190 --> 00:34:27,790
Więc po prostu zobaczył operatora OR.

726
00:34:27,790 --> 00:34:29,348
To jest wyłącznym operatorem OR.

727
00:34:29,348 --> 00:34:30,639
Co znajduje się w rzeczywistości różnica?

728
00:34:30,639 --> 00:34:34,570
Dobrze niech wystarczy spojrzeć na wzór,
i używać tego jako składników ostatecznie.

729
00:34:34,570 --> 00:34:37,690
0 XOR 0.

730
00:34:37,690 --> 00:34:39,650
Mam zamiar powiedzieć to zawsze 0.

731
00:34:39,650 --> 00:34:41,400
To definicja XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 będzie 1.

733
00:34:47,104 --> 00:34:58,810
1 XOR 0 będzie 1,
i 1 XOR 1 będzie?

734
00:34:58,810 --> 00:34:59,890
Nie tak?

735
00:34:59,890 --> 00:35:00,520
Lub prawo?

736
00:35:00,520 --> 00:35:01,860
Nie wiem.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
Teraz to, co się tu dzieje?

739
00:35:04,700 --> 00:35:06,630
Dobrze, że o
Nazwa tego operatora.

740
00:35:06,630 --> 00:35:09,980
Exclusive OR, tak jak
nazwa, rodzaj, sugeruje,

741
00:35:09,980 --> 00:35:13,940
Odpowiedź jest tylko będzie
1, jeśli dane wejściowe są cenami,

742
00:35:13,940 --> 00:35:15,560
wyłącznie inna.

743
00:35:15,560 --> 00:35:18,170
Więc tutaj wejścia są
same, więc wyjście 0.

744
00:35:18,170 --> 00:35:20,700
Tutaj wejścia są
same, więc wyjście 0.

745
00:35:20,700 --> 00:35:25,640
Oto wyjścia są różne,
są cenami, a więc wyjście to 1.

746
00:35:25,640 --> 00:35:28,190
Więc to jest bardzo podobne do
I jest to bardzo podobne,

747
00:35:28,190 --> 00:35:32,760
czy raczej jest to bardzo podobne do
OR, ale tylko w sposób wyłączny.

748
00:35:32,760 --> 00:35:36,210
Ten nie jest 1,
bo mamy dwa 1-tych,

749
00:35:36,210 --> 00:35:38,621
i nie tylko, tylko jeden z nich.

750
00:35:38,621 --> 00:35:39,120
W porządku.

751
00:35:39,120 --> 00:35:40,080
A co z innymi?

752
00:35:40,080 --> 00:35:44,220
Cóż tyldy, w międzyczasie,
naprawdę ładne i proste, na szczęście.

753
00:35:44,220 --> 00:35:46,410
I jest to jednoskładnikowa
Operator, który oznacza

754
00:35:46,410 --> 00:35:50,400
Jest ono stosowane tylko do jednego wejścia,
jeden argument, że tak powiem.

755
00:35:50,400 --> 00:35:51,800
Nie w lewo i prawo.

756
00:35:51,800 --> 00:35:56,050
Innymi słowy, jeśli wziąć tyldy z
0, odpowiedź będzie przeciwny.

757
00:35:56,050 --> 00:35:59,710
A jeśli wziąć tyldy od 1,
Odpowiedź nie będzie przeciwny.

758
00:35:59,710 --> 00:36:02,570
Więc operator tyldy jest
sposób negując trochę,

759
00:36:02,570 --> 00:36:06,000
lub odwrócenie się nieco od
0 do 1 lub 1 do 0 ° C.

760
00:36:06,000 --> 00:36:09,820
>> I że pozostawia nas w końcu
z zaledwie dwóch operatorów końcowych,

761
00:36:09,820 --> 00:36:13,840
tak zwane przesunięcie w lewo, a
tak zwane prawo operatora przesunięcia.

762
00:36:13,840 --> 00:36:16,620
Rzućmy okiem na jak te prace.

763
00:36:16,620 --> 00:36:20,780
Operatora przesunięcia w lewo, napisane
z dwoma nawiasami ostrymi jak to,

764
00:36:20,780 --> 00:36:22,110
działa w następujący sposób.

765
00:36:22,110 --> 00:36:27,390
Jeśli mój wkład, albo mój argument, z lewej
Operator przesunięcia jest po prostu 1.

766
00:36:27,390 --> 00:36:33,750
I powiedz komputer do
Lewy Shift, że 1, powiedzieć, siedem miejsc,

767
00:36:33,750 --> 00:36:37,150
wynik jest tak, jakbym
przyjąć, że 1 i przenieść go

768
00:36:37,150 --> 00:36:40,160
ponad siedem miejsc do
lewa i domyślnie,

769
00:36:40,160 --> 00:36:42,270
będziemy zakładać, że
przestrzeń na prawo

770
00:36:42,270 --> 00:36:44,080
ma być wypełniane zerami.

771
00:36:44,080 --> 00:36:50,316
Innymi słowy, 1 lewy shift 7 będzie
dać mi, 1, a następnie 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 zerami.

773
00:36:54,060 --> 00:36:57,380
Więc w taki sposób, że pozwala na
wziąć małą liczbę jak 1,

774
00:36:57,380 --> 00:37:00,740
i wyraźnie, aby go dużo
o wiele większa w taki sposób,

775
00:37:00,740 --> 00:37:06,460
ale my naprawdę zobaczymy
więcej mądrych podejścia do niego

776
00:37:06,460 --> 00:37:08,080
zamiast, jak również,

777
00:37:08,080 --> 00:37:08,720
>> W porządku.

778
00:37:08,720 --> 00:37:10,060
To wszystko na trzech tygodniu.

779
00:37:10,060 --> 00:37:11,400
Będziemy zobaczenia następnym razem.

780
00:37:11,400 --> 00:37:12,770
To był CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [MUZYKI]

783
00:37:22,243 --> 00:37:25,766
>> Głośnik 1: Był na przekąskę
bar jedzenia hot krówki lody.

784
00:37:25,766 --> 00:37:28,090
Miał go na całej twarzy.

785
00:37:28,090 --> 00:37:30,506
Ma na sobie, że czekolada jak brodą

786
00:37:30,506 --> 00:37:31,756
GŁOŚNIK 2: Co ty robisz?

787
00:37:31,756 --> 00:37:32,422
GŁOŚNIK 3: Hmmm?

788
00:37:32,422 --> 00:37:33,500
Co?

789
00:37:33,500 --> 00:37:36,800
>> GŁOŚNIK 2: Czy wystarczy dwukrotnie dip?

790
00:37:36,800 --> 00:37:38,585
Dwukrotne świateł chip.

791
00:37:38,585 --> 00:37:39,460
GŁOŚNIK 3: Przepraszam.

792
00:37:39,460 --> 00:37:44,440
GŁOŚNIK 2: świateł chip, można
ugryzł i ponownie zanurzył.

793
00:37:44,440 --> 00:37:44,940
GŁOŚNIK 3:

794
00:37:44,940 --> 00:37:48,440
GŁOŚNIK 2: Więc to jest jak stawianie
cała prawda usta w kąpieli.

795
00:37:48,440 --> 00:37:52,400
Następnym razem wybrać się na układ,
po prostu zanurzyć go raz, a zakończyć go.

796
00:37:52,400 --> 00:37:53,890
>> GŁOŚNIK 3: Wiesz co, Dan?

797
00:37:53,890 --> 00:37:58,006
Zanurzyć drogę, którą chcesz zanurzyć.

798
00:37:58,006 --> 00:38:01,900
Będę zanurzyć tak, że chcę, aby zanurzyć.

799
00:38:01,900 --> 00:38:03,194