1
00:00:00,000 --> 00:00:11,100

2
00:00:11,100 --> 00:00:12,300
>> GŁOŚNIK 1: Hej wszystkim!

3
00:00:12,300 --> 00:00:13,890
Witamy z powrotem do sekcji.

4
00:00:13,890 --> 00:00:17,480
Więc cieszę się, że tak wielu z was, zarówno tutaj,
i każdy kto ogląda w Internecie.

5
00:00:17,480 --> 00:00:18,760

6
00:00:18,760 --> 00:00:20,920
Tak, jak zwykle Witamy z powrotem.

7
00:00:20,920 --> 00:00:24,360
Mam nadzieję, że wszystko było piękne
weekend, pełen odpoczynek, relaks.

8
00:00:24,360 --> 00:00:26,026
To było piękne wczoraj.

9
00:00:26,026 --> 00:00:27,525
Więc mam nadzieję, że cieszył się na zewnątrz.

10
00:00:27,525 --> 00:00:28,840

11
00:00:28,840 --> 00:00:30,610
>> Więc najpierw kilka ogłoszeń.

12
00:00:30,610 --> 00:00:31,920

13
00:00:31,920 --> 00:00:32,700
Klasyfikacja.

14
00:00:32,700 --> 00:00:37,350
Tak, większość z was powinna zdobyć
napisz mi o swoim Scratch Pset,

15
00:00:37,350 --> 00:00:39,920
jak również klasyfikacji dla Pset 1.

16
00:00:39,920 --> 00:00:41,000

17
00:00:41,000 --> 00:00:42,220
Tak, tylko kilka rzeczy.

18
00:00:42,220 --> 00:00:45,150
Należy używać check50 w style50.

19
00:00:45,150 --> 00:00:47,250
Te mają być
Zasoby dla was,

20
00:00:47,250 --> 00:00:50,660
aby upewnić się, że dostajesz
jak najwięcej punktów, jak to możliwe

21
00:00:50,660 --> 00:00:52,390
bez niepotrzebnie ich utraty.

22
00:00:52,390 --> 00:00:54,407
Tak, takie rzeczy jak styl
są bardzo ważne.

23
00:00:54,407 --> 00:00:55,740
Mamy zamiar startu do niego.

24
00:00:55,740 --> 00:00:58,115
Niektórzy z was mogą już
Zauważyłem, że od Pset.

25
00:00:58,115 --> 00:00:58,920

26
00:00:58,920 --> 00:01:01,450
I check50 tylko
bardzo łatwy sposób, aby upewnić się,

27
00:01:01,450 --> 00:01:05,050
że jesteśmy rzeczywiście powrocie co
należy zwrócić się do użytkownika,

28
00:01:05,050 --> 00:01:06,690
i, że wszystko działa prawidłowo.

29
00:01:06,690 --> 00:01:08,690

30
00:01:08,690 --> 00:01:12,040
>> Na drugim notatki, upewnij się, że
przesyłania rzeczy do odpowiedniego folderu.

31
00:01:12,040 --> 00:01:14,470
To sprawia, że ​​moje życie tylko
Trochę trudniej

32
00:01:14,470 --> 00:01:18,836
jeśli przesłać Pset 2 do Pset 1
bo kiedy pobrać rzeczy,

33
00:01:18,836 --> 00:01:20,085
nie ściągnąć poprawnie.

34
00:01:20,085 --> 00:01:21,690

35
00:01:21,690 --> 00:01:24,560
I wiem, że to trochę słaby
w systemie, aby przyzwyczaić się do,

36
00:01:24,560 --> 00:01:26,950
ale po prostu super
Uważaj, jeśli tylko dla mnie,

37
00:01:26,950 --> 00:01:30,080
tak, że kiedy dostajesz e-maile
na jak 2 A.M. i jestem klasyfikacji.

38
00:01:30,080 --> 00:01:33,710
Jeśli nie powodować mam szukać
dookoła dla Pset.

39
00:01:33,710 --> 00:01:34,440
Fajne.

40
00:01:34,440 --> 00:01:37,270
>> Wiem, że to wcześnie, ale
całkowicie dostał podjąć tropu

41
00:01:37,270 --> 00:01:40,800
w eseju, który jest piątek, z powodu tego, że
moi profesorowie byli tak jak, oh yeah.

42
00:01:40,800 --> 00:01:42,550
Pamiętaj, że masz
Esej ze względu na piątek.

43
00:01:42,550 --> 00:01:45,780
Tak, wiem, że nikt nie lubi
myśleć o midterms,

44
00:01:45,780 --> 00:01:50,620
ale twój pierwszy quiz jest na 15 października
które października rozpoczyna w tym tygodniu.

45
00:01:50,620 --> 00:01:53,290
Tak, to może być wcześniej
niż oczekiwano wszystko.

46
00:01:53,290 --> 00:01:57,510
Tak, że nie jesteś wyrzucony z tropu, kiedy
Wspominam przyszłym tygodniu odcinek że oh,

47
00:01:57,510 --> 00:02:00,560
quiz w przyszłym tygodniu, myślałem
Chciałbym dać trochę więcej

48
00:02:00,560 --> 00:02:01,500
od głowy do góry teraz.

49
00:02:01,500 --> 00:02:02,970

50
00:02:02,970 --> 00:02:04,660
>> Tak, ustaw problem, numer trzy.

51
00:02:04,660 --> 00:02:07,070
Jak ludzie mają czytać
wg planu z ciekawości?

52
00:02:07,070 --> 00:02:08,560

53
00:02:08,560 --> 00:02:09,199
OK.

54
00:02:09,199 --> 00:02:10,229
Mamy kilka.

55
00:02:10,229 --> 00:02:12,320
Niby się z ostatnim
tydzień, ale to jest OK.

56
00:02:12,320 --> 00:02:13,650
Wiem, że to było piękne na zewnątrz.

57
00:02:13,650 --> 00:02:15,120

58
00:02:15,120 --> 00:02:16,660
Więc Break Out.

59
00:02:16,660 --> 00:02:21,010
Zdecydowanie po zrobienia
dziś przeczytać specyfikację co najmniej

60
00:02:21,010 --> 00:02:25,240
spróbować jak pobieranie
Kod dystrybucji i prowadzenie

61
00:02:25,240 --> 00:02:27,430
jak pierwszy inicjał
rzeczą, że poprosi.

62
00:02:27,430 --> 00:02:28,681

63
00:02:28,681 --> 00:02:32,590
Ponieważ używamy
Kod dystrybucji i biblioteki

64
00:02:32,590 --> 00:02:36,790
że mamy jedynie using-- --It tylko
drugi raz zrobiliśmy to Pset,

65
00:02:36,790 --> 00:02:38,650
szalone rzeczy mogą się zdarzyć
z urządzenia,

66
00:02:38,650 --> 00:02:41,370
i chcesz, aby stwierdzić, że
się teraz w stosunku później.

67
00:02:41,370 --> 00:02:45,570
>> Bo jeśli jest to w czwartek wieczorem lub to
Środę i z jakiegoś powodu

68
00:02:45,570 --> 00:02:48,912
twoje urządzenie po prostu nie robi
chce uruchomić z biblioteką

69
00:02:48,912 --> 00:02:50,620
lub rozkładu
Kod, że środki

70
00:02:50,620 --> 00:02:52,309
nie można nawet zacząć robić kodowanie.

71
00:02:52,309 --> 00:02:54,100
Ponieważ nie można sprawdzić
aby sprawdzić, czy to działa.

72
00:02:54,100 --> 00:02:55,975
Twoja nie będzie w stanie
aby sprawdzić, czy kompiluje.

73
00:02:55,975 --> 00:03:00,500
Chcesz zadbać o tych, na początku
tydzień, kiedy można jeszcze napisz do mnie

74
00:03:00,500 --> 00:03:03,100
lub jeden z pozostałych TFS
i możemy dostać te stałe.

75
00:03:03,100 --> 00:03:05,410
Ponieważ są to kwestie
że zamierzamy się zatrzymać

76
00:03:05,410 --> 00:03:07,120
z podjęciem prawdziwy postęp.

77
00:03:07,120 --> 00:03:10,055
To nie tak, jeden błąd, że
można po prostu rodzaj pominąć.

78
00:03:10,055 --> 00:03:10,712

79
00:03:10,712 --> 00:03:13,420
Jeśli masz problemy ze swoim
urządzenie lub kod dystrybucji,

80
00:03:13,420 --> 00:03:16,211
Naprawdę chcesz się, że podjęte
dbać o raczej wcześniej niż później.

81
00:03:16,211 --> 00:03:20,410
Więc nawet jeśli w rzeczywistości nie spodoba
zacząć pisać, należy pobrać dystrybucję

82
00:03:20,410 --> 00:03:24,040
Kod, przeczytaj specyfikację, upewnij się,
wszystko działa tam.

83
00:03:24,040 --> 00:03:25,134
OK?

84
00:03:25,134 --> 00:03:27,675
Jeśli można tak zrobić, ja
Obiecujemy wam życie będzie łatwiejsze.

85
00:03:27,675 --> 00:03:28,800

86
00:03:28,800 --> 00:03:31,410
I tak pewnie będzie
zrobić to teraz dobrze?

87
00:03:31,410 --> 00:03:32,100
OK.

88
00:03:32,100 --> 00:03:33,950
Tak, jakieś pytania?

89
00:03:33,950 --> 00:03:35,850
Wszelkie sprawy logistyczne?

90
00:03:35,850 --> 00:03:36,910
Każdy jest dobry?

91
00:03:36,910 --> 00:03:38,270
OK.

92
00:03:38,270 --> 00:03:41,700
>> Zastrzeżone dla tych
jesteś w pokoju i online.

93
00:03:41,700 --> 00:03:45,437
Będę się starał, aby przełączyć
między PowerPoint w urządzeniu

94
00:03:45,437 --> 00:03:47,270
ponieważ będziemy
się jakiejś kodowanie

95
00:03:47,270 --> 00:03:53,630
dziś popularnej żądanie anonimowy
Sugestia ankieta wysłałem w zeszłym tygodniu.

96
00:03:53,630 --> 00:03:55,480
Tak, będziemy robić niektóre kodowania.

97
00:03:55,480 --> 00:03:57,800
Tak więc, jeśli macie też chcą
Do uruchomienia urządzenia,

98
00:03:57,800 --> 00:04:02,910
i powinny masz e-mail
ode mnie, z przykładowego pliku.

99
00:04:02,910 --> 00:04:04,310
Prosimy, aby to zrobić.

100
00:04:04,310 --> 00:04:07,340
>> Tak, będziemy mówić o
GDB, który jest debugger.

101
00:04:07,340 --> 00:04:09,970
To pomoże ci
rodzaj dowiedzieć się, gdzie

102
00:04:09,970 --> 00:04:11,860
wszystko idzie nie tak w kodzie.

103
00:04:11,860 --> 00:04:15,370
To naprawdę tylko sposób na krok
przez kod, jak to się dzieje,

104
00:04:15,370 --> 00:04:19,100
i być w stanie wydrukować zmienne
lub zobaczyć, co się rzeczywiście dzieje

105
00:04:19,100 --> 00:04:22,980
Pod maską wersety program
tak działa, to jak uskoki,

106
00:04:22,980 --> 00:04:25,030
i jesteś jak, bez pomysłu
co się stało tutaj.

107
00:04:25,030 --> 00:04:26,730
Nie wiem, co to nie na linii.

108
00:04:26,730 --> 00:04:29,040
Nie wiem, gdzie to się stało.

109
00:04:29,040 --> 00:04:31,280
Tak, GDB pomoże Ci w tym.

110
00:04:31,280 --> 00:04:35,240
Ponadto, jeśli zdecydujesz się na
nadal tak, i wziąć 61,

111
00:04:35,240 --> 00:04:38,430
to będzie naprawdę być twój
najlepszym przyjacielem, bo mogę powiedzieć,

112
00:04:38,430 --> 00:04:40,840
bo mam zamiar przez tej klasy.

113
00:04:40,840 --> 00:04:43,620
>> Mamy zamiar spojrzeć na binarny
wyszukiwarka, która jeśli faceci pamiętają

114
00:04:43,620 --> 00:04:47,540
świetny przykład książki telefonicznej
Spektakl z klasy.

115
00:04:47,540 --> 00:04:50,620
Będziemy wykonawcze, że i
przechodząc przez które trochę więcej,

116
00:04:50,620 --> 00:04:54,650
a następnie jedziemy przez cztery
różne rodzaje, które są Bańka,

117
00:04:54,650 --> 00:04:56,285
Wybór, Wejścia i Merge.

118
00:04:56,285 --> 00:04:57,830

119
00:04:57,830 --> 00:04:58,330
Fajne.

120
00:04:58,330 --> 00:05:00,390
Tak, GDB jak wspomniałem, jest debugger.

121
00:05:00,390 --> 00:05:01,400

122
00:05:01,400 --> 00:05:09,370
I to są niby duże
rzeczy, wielkie funkcje i polecenia

123
00:05:09,370 --> 00:05:13,240
że używasz w ciągu GDB i będę chodzić
można przez nią demo w sekundę.

124
00:05:13,240 --> 00:05:15,360
>> Tak więc, nie jest to
Zostanę streszczenie.

125
00:05:15,360 --> 00:05:18,000
Postaram się zrobić to jak beton
jak to możliwe dla was.

126
00:05:18,000 --> 00:05:19,870
Więc złamać.

127
00:05:19,870 --> 00:05:22,200
To będzie być albo przerwa
jak niektóre liczby, które

128
00:05:22,200 --> 00:05:26,900
oznacza linię w programie,
czy można wymienić funkcję.

129
00:05:26,900 --> 00:05:30,150
Więc, jeśli powiesz, że łamać głównym,
zatrzyma się w głównym,

130
00:05:30,150 --> 00:05:32,400
i pozwala chodzić po tej funkcji.

131
00:05:32,400 --> 00:05:36,350
>> Podobnie, jeśli masz jakiś zewnętrzny
Zamiana lub działać jak Cube,

132
00:05:36,350 --> 00:05:38,450
że spojrzał na ostatni tydzień.

133
00:05:38,450 --> 00:05:41,780
Jeśli powiesz złamać jeden z tych,
gdy program trafia, że

134
00:05:41,780 --> 00:05:44,290
będzie ona czekać na ciebie
powiedz to, co zrobić.

135
00:05:44,290 --> 00:05:47,860
Zanim będzie to po prostu wykonać tak ci
może rzeczywiście krok wewnątrz funkcji

136
00:05:47,860 --> 00:05:49,020
i zobaczyć, co się dzieje.

137
00:05:49,020 --> 00:05:50,370

138
00:05:50,370 --> 00:05:53,515
Więc Następnie, po prostu pomija
Następna linia, podchodzi funkcji.

139
00:05:53,515 --> 00:05:54,730

140
00:05:54,730 --> 00:05:55,560
Krok.

141
00:05:55,560 --> 00:05:56,810
Są to trochę abstrakcyjne.

142
00:05:56,810 --> 00:06:00,530
Tak, jestem po prostu będzie działać przez nich,
ale można je zobaczyć w użyciu w sekundę.

143
00:06:00,530 --> 00:06:01,810
>> Krok do funkcji.

144
00:06:01,810 --> 00:06:04,170
Tak jak mówiłem,
jak z wymiany, to będzie

145
00:06:04,170 --> 00:06:07,110
pozwalają właściwie jakbyś
jak fizycznie wyjście wewnątrz,

146
00:06:07,110 --> 00:06:10,990
możesz zadzierać z tych zmiennych, druk
się, czym one są, zobaczyć, co się dzieje.

147
00:06:10,990 --> 00:06:12,140

148
00:06:12,140 --> 00:06:14,830
Lista będzie dosłownie wydrukować
z otaczającego kodu.

149
00:06:14,830 --> 00:06:17,570
Tak więc, jeśli rodzaj zapomnieć
gdzie jesteś w programie,

150
00:06:17,570 --> 00:06:19,880
lub zastanawiasz
co się dzieje wokół niego,

151
00:06:19,880 --> 00:06:23,790
to będzie po prostu wydrukować segment
od jak pięć lub sześć linie wokół niego.

152
00:06:23,790 --> 00:06:26,080
Tak, można oswoić
o tym, gdzie jesteś.

153
00:06:26,080 --> 00:06:27,230

154
00:06:27,230 --> 00:06:28,650
>> Drukuj trochę zmienną.

155
00:06:28,650 --> 00:06:34,590
Tak więc, jeśli masz klucz jak
w Cezara, że ​​przyjrzymy się.

156
00:06:34,590 --> 00:06:36,220
Można powiedzieć, że klucz Drukuj w dowolnym momencie.

157
00:06:36,220 --> 00:06:40,070
To będzie powiedzieć, co to jest wartość
że może być gdzieś wzdłuż drogi,

158
00:06:40,070 --> 00:06:42,070
zastąpiłeś klucz.

159
00:06:42,070 --> 00:06:45,495
Rzeczywiście można powiedzieć, że z powodu
rzeczywiście można zauważyć, że wartość.

160
00:06:45,495 --> 00:06:46,500

161
00:06:46,500 --> 00:06:48,780
>> W miejscowych, tylko odbitki
z lokalnych zmiennych.

162
00:06:48,780 --> 00:06:53,120
Tak, w każdej chwili jesteś w pętli,
i po prostu chcesz zobaczyć, jak, och.

163
00:06:53,120 --> 00:06:54,270
Jakie jest moje ja?

164
00:06:54,270 --> 00:06:57,020
Jaka jest wartość tego klucza
że zainicjować tutaj?

165
00:06:57,020 --> 00:06:58,537
Co to jest wiadomość w tym momencie?

166
00:06:58,537 --> 00:07:00,370
To po prostu wydrukować wszystkie
z nich, tak, że ty

167
00:07:00,370 --> 00:07:04,330
nie muszą indywidualnie
powiedzieć, Drukuj I. Drukuj wiadomość.

168
00:07:04,330 --> 00:07:04,970
Przycisk Print.

169
00:07:04,970 --> 00:07:06,190

170
00:07:06,190 --> 00:07:07,700
A następnie wyświetlić.

171
00:07:07,700 --> 00:07:10,370
Co to robi, jest jak ty
krok po kroku program,

172
00:07:10,370 --> 00:07:13,980
będzie to po prostu upewnij się, że jest to
wyświetlając jakąś pewną zmienną

173
00:07:13,980 --> 00:07:14,780
w każdym punkcie.

174
00:07:14,780 --> 00:07:17,160
Tak że also-- --it jest
rodzaj skrótu gdzie

175
00:07:17,160 --> 00:07:19,530
nie trzeba iść dalej jak, och.

176
00:07:19,530 --> 00:07:23,150
Klucz do druku lub Drukuj I. To właśnie
automatycznie zrobi to za Ciebie.

177
00:07:23,150 --> 00:07:25,959
>> Tak, z tym, będziemy
aby zobaczyć jak to działa.

178
00:07:25,959 --> 00:07:28,000
Zamierzam spróbować i przełącznik
do mojego urządzenia.

179
00:07:28,000 --> 00:07:30,200

180
00:07:30,200 --> 00:07:31,271
Zobacz, czy mogę to zrobić.

181
00:07:31,271 --> 00:07:31,770
Wszystko.

182
00:07:31,770 --> 00:07:40,970

183
00:07:40,970 --> 00:07:42,370
Jesteśmy po prostu będzie to odzwierciedlać.

184
00:07:42,370 --> 00:07:44,530
Nie ma nic do szaleństwa
na moim laptopie i tak.

185
00:07:44,530 --> 00:07:49,600

186
00:07:49,600 --> 00:07:50,100
OK.

187
00:07:50,100 --> 00:07:57,030

188
00:07:57,030 --> 00:08:01,054
To musi być ten.

189
00:08:01,054 --> 00:08:01,795
To takie małe.

190
00:08:01,795 --> 00:08:03,730

191
00:08:03,730 --> 00:08:05,120
Zobaczymy, czy uda nam się to zrobić.

192
00:08:05,120 --> 00:08:09,970

193
00:08:09,970 --> 00:08:10,940
>> OK.

194
00:08:10,940 --> 00:08:15,305
Alicja jest oczywiście walczy
tutaj tylko trochę,

195
00:08:15,305 --> 00:08:17,995
ale dostaniemy go w momento.

196
00:08:17,995 --> 00:08:20,810

197
00:08:20,810 --> 00:08:22,020
OK.

198
00:08:22,020 --> 00:08:25,900
Jesteśmy po prostu się do zwiększenia tego.

199
00:08:25,900 --> 00:08:28,770

200
00:08:28,770 --> 00:08:29,380
OK.

201
00:08:29,380 --> 00:08:31,679
Czy każdy rodzaj zobaczyć?

202
00:08:31,679 --> 00:08:32,470
Może trochę?

203
00:08:32,470 --> 00:08:33,594
Wiem, że to trochę małe.

204
00:08:33,594 --> 00:08:34,570

205
00:08:34,570 --> 00:08:37,530
Nie dość rysunek się
jak zrobić to większe.

206
00:08:37,530 --> 00:08:38,350
Jeśli ktoś wie.

207
00:08:38,350 --> 00:08:40,309
Czy ktoś wie jak zrobić to większe?

208
00:08:40,309 --> 00:08:40,932
OK.

209
00:08:40,932 --> 00:08:42,140
Mamy zamiar rzucić się z nim.

210
00:08:42,140 --> 00:08:45,801
Nie ma znaczenia, tak czy inaczej, bo to jest po prostu
jest to kod, który chłopaki powinni

211
00:08:45,801 --> 00:08:46,300
mają.

212
00:08:46,300 --> 00:08:48,310
>> Co ważne
Zacisk jest tutaj.

213
00:08:48,310 --> 00:08:52,840

214
00:08:52,840 --> 00:08:58,690
I mamy tutaj Dlaczego jest tak mała?

215
00:08:58,690 --> 00:09:02,325

216
00:09:02,325 --> 00:09:02,825
Ustawienia.

217
00:09:02,825 --> 00:09:07,920

218
00:09:07,920 --> 00:09:08,420
Och.

219
00:09:08,420 --> 00:09:09,500
Prawdziwa Ike.

220
00:09:09,500 --> 00:09:10,880
Jak to jest?

221
00:09:10,880 --> 00:09:11,770
Stamtąd.

222
00:09:11,770 --> 00:09:19,370

223
00:09:19,370 --> 00:09:21,810
Jest to, że lepiej dla wszystkich?

224
00:09:21,810 --> 00:09:22,525
OK ,.

225
00:09:22,525 --> 00:09:23,025
Fajne.

226
00:09:23,025 --> 00:09:25,830

227
00:09:25,830 --> 00:09:28,220
>> Wiesz, kiedy jesteś w CS
klasy trudności techniczne

228
00:09:28,220 --> 00:09:32,971
są swego rodzaju częścią the--
Tak, niech usunąć ten.

229
00:09:32,971 --> 00:09:33,470
OK.

230
00:09:33,470 --> 00:09:38,060
Tak, właśnie tutaj, w dziale,
które mieliśmy tutaj.

231
00:09:38,060 --> 00:09:40,830
Cezar jest plik wykonywalny.

232
00:09:40,830 --> 00:09:41,800
Więc zrobiłem to.

233
00:09:41,800 --> 00:09:46,370
Tak, aby zrealizować jedno z GDB jest
że to działa tylko na pliki wykonywalne.

234
00:09:46,370 --> 00:09:48,040
Tak więc, nie można go uruchomić na dotsy.

235
00:09:48,040 --> 00:09:50,532
Trzeba rzeczywiście zrobić
upewnić się, że kod kompiluje,

236
00:09:50,532 --> 00:09:51,865
oraz, że w rzeczywistości może być uruchomiony.

237
00:09:51,865 --> 00:09:52,970

238
00:09:52,970 --> 00:09:56,186
>> Więc upewnij się, że jeśli nie
kompilacji, zmusić go do kompilacji,

239
00:09:56,186 --> 00:09:57,810
tak, że można rodzaj uruchomienia przez nią.

240
00:09:57,810 --> 00:10:04,590
Tak, aby uruchomić GDB, wszystko co robisz,
Typ Gloria GDB, a potem po prostu

241
00:10:04,590 --> 00:10:06,250
plik, który chcesz.

242
00:10:06,250 --> 00:10:08,240
Ja zawsze błędnie Cezara.

243
00:10:08,240 --> 00:10:11,730
Ale chcesz się upewnić,
ponieważ jest to plik wykonywalny,

244
00:10:11,730 --> 00:10:14,210
kropka błysku, tak aby TI
Oznacza idziesz

245
00:10:14,210 --> 00:10:19,240
uruchomić CSI masz zamiar wykonać
to pliki albo z debuggera.

246
00:10:19,240 --> 00:10:19,910
OK.

247
00:10:19,910 --> 00:10:22,885
Tak, to zrobisz, otrzymasz
tego rodzaju bełkotem.

248
00:10:22,885 --> 00:10:24,250

249
00:10:24,250 --> 00:10:25,750
To tylko wszystkie rzeczy o debugger.

250
00:10:25,750 --> 00:10:28,200
Tak naprawdę nie trzeba
martwić się teraz o tym.

251
00:10:28,200 --> 00:10:31,460
I jak widać, to mamy
otwarte nawiasy, PKB, blisko nawiasy,

252
00:10:31,460 --> 00:10:34,690
i po prostu rodzaj wygląda
nasza linia poleceń, prawda?

253
00:10:34,690 --> 00:10:37,010
>> Więc, co chcemy do--
-SO, Pierwszą rzeczą,

254
00:10:37,010 --> 00:10:39,570
to chcemy wybrać
miejsce, aby go złamać.

255
00:10:39,570 --> 00:10:42,332
Tak, jest jeden błąd
w tym programie Caesar

256
00:10:42,332 --> 00:10:44,290
że mogę przedstawić, że
mamy zamiar się dowiedzieć.

257
00:10:44,290 --> 00:10:45,330

258
00:10:45,330 --> 00:10:56,350
To co robi jest potrzeba wejścia
Barfoo we wszystkich czapki, iz jakiegoś powodu

259
00:10:56,350 --> 00:11:01,950
Nie zmienia A. To po prostu pozostawia
on sam, Czy wszystko poprawne,

260
00:11:01,950 --> 00:11:03,980
ale drugi list
Pozostaje niezmieniona.

261
00:11:03,980 --> 00:11:07,120
Tak, mamy zamiar spróbować
dowiedzieć się, dlaczego tak jest.

262
00:11:07,120 --> 00:11:10,440
Więc pierwszą rzeczą, którą zwykle
chcemy robić przy każdym uruchomieniu na GDB

263
00:11:10,440 --> 00:11:12,010
jest dowiedzieć się, gdzie go złamać.

264
00:11:12,010 --> 00:11:14,956
>> Więc Cezar jest dość krótki program.

265
00:11:14,956 --> 00:11:16,330
Mamy tylko jedną funkcję, prawda?

266
00:11:16,330 --> 00:11:18,520
Jaka była nasza funkcja w Cezara?

267
00:11:18,520 --> 00:11:19,590

268
00:11:19,590 --> 00:11:24,350
Jest tylko jedna funkcja, główna prawda?

269
00:11:24,350 --> 00:11:26,490
Główną funkcją jest
dla wszystkich programów.

270
00:11:26,490 --> 00:11:29,230
Jeśli nie masz Main, mógłbym
być trochę martwi teraz,

271
00:11:29,230 --> 00:11:31,000
ale mam nadzieję, że wszyscy mieli Main tam.

272
00:11:31,000 --> 00:11:34,150
Tak więc, co możemy zrobić, to możemy
po prostu złamać Main, tak po prostu.

273
00:11:34,150 --> 00:11:35,190
Tak, to mówi, OK.

274
00:11:35,190 --> 00:11:37,430
Wyznaczamy punkt przerwania jeden tam.

275
00:11:37,430 --> 00:11:42,870
>> Tak, teraz jest, aby pamiętać Cezar
trwa jeden argument wiersza poleceń prawo

276
00:11:42,870 --> 00:11:45,150
i nie zrobiliśmy, że jeszcze nigdzie.

277
00:11:45,150 --> 00:11:47,560
Więc, co można zrobić, to kiedy
rzeczywiście iść do pracy

278
00:11:47,560 --> 00:11:51,540
programu, każdy program, który jesteś
działa w GDB, który potrzebuje wiersza poleceń

279
00:11:51,540 --> 00:11:55,010
argumenty, masz zamiar wejścia
gdy po raz pierwszy rozpocząć prowadzenie go.

280
00:11:55,010 --> 00:11:59,280
Tak więc, w tym przypadku zrobić
Uruchom z kluczem trzech.

281
00:11:59,280 --> 00:12:00,770

282
00:12:00,770 --> 00:12:02,040
I będzie zacząć.

283
00:12:02,040 --> 00:12:08,480
>> Tak więc, jeśli widzisz, tutaj mamy
Jeśli RC nie jest równy 2.

284
00:12:08,480 --> 00:12:12,210
Więc jeśli faceci mają
że plik, który wysłałem do

285
00:12:12,210 --> 00:12:15,100
zobaczysz, że to jak
Pierwsza linia naszym głównym zadaniem, prawda?

286
00:12:15,100 --> 00:12:17,890
To się sprawdza, jeśli mamy
poprawna liczba argumentów.

287
00:12:17,890 --> 00:12:20,620
Więc jeśli zastanawiasz
czy RC jest prawidłowe,

288
00:12:20,620 --> 00:12:23,250
można zrobić coś tak jak Drukuj RC.

289
00:12:23,250 --> 00:12:24,380

290
00:12:24,380 --> 00:12:28,640
RC jest dwa, co jest
to, czego oczekuje, prawda?

291
00:12:28,640 --> 00:12:32,010
>> Tak, możemy iść dalej,
i dalej przez.

292
00:12:32,010 --> 00:12:33,200
Tak, mamy tam jakiś klucz.

293
00:12:33,200 --> 00:12:34,260

294
00:12:34,260 --> 00:12:37,090
I możemy wydrukować nasz klucz
aby upewnić się, że jest prawidłowe.

295
00:12:37,090 --> 00:12:38,380

296
00:12:38,380 --> 00:12:39,500
Ciekawe.

297
00:12:39,500 --> 00:12:41,210
Nie całkiem to, czego oczekiwaliśmy.

298
00:12:41,210 --> 00:12:44,810
Tak więc, jedno do realizacji
z GDB też jest

299
00:12:44,810 --> 00:12:49,000
że to nie jest aż faktycznie hit
Następnie, że wiersz, który właśnie zobaczył

300
00:12:49,000 --> 00:12:50,720
jest faktycznie wykonywana.

301
00:12:50,720 --> 00:12:53,870
Tak więc, w tym przypadku kluczem
jeszcze nie został przydzielony.

302
00:12:53,870 --> 00:12:57,050
Więc kluczem jest jakaś wartość śmieci
które widzisz na tam na dole.

303
00:12:57,050 --> 00:13:03,680
Negatywny $ 120-- --It na miliard
i coś dziwne rzeczy prawda?

304
00:13:03,680 --> 00:13:05,340
To nie jest klucz, że spodziewaliśmy.

305
00:13:05,340 --> 00:13:10,720
Ale jeśli uderzymy Dalej, a następnie
spróbować i klucz Drukuj, to trzy.

306
00:13:10,720 --> 00:13:11,710
>> Każdy widzi?

307
00:13:11,710 --> 00:13:13,780
Tak więc, jeśli coś
że jesteś jak, poczekaj.

308
00:13:13,780 --> 00:13:15,540
Jest to zupełnie
tak, i nie wiem,

309
00:13:15,540 --> 00:13:20,150
w jaki sposób to się stało, bo wszystko, co chcę
zrobić, to przypisać numer, zmienna,

310
00:13:20,150 --> 00:13:22,900
spróbować uderzając Dalej, spróbuj drukować
to jeszcze raz, i zobaczyć, czy zadziała.

311
00:13:22,900 --> 00:13:27,830
Bo to będzie tylko do wykonania i
rzeczywiście przypisać coś po tobie

312
00:13:27,830 --> 00:13:29,340
uderzył Dalej.

313
00:13:29,340 --> 00:13:30,336
Sens dla wszystkich?

314
00:13:30,336 --> 00:13:30,836
Uh huh?

315
00:13:30,836 --> 00:13:33,220
>> GŁOŚNIK 2: Kiedy losowo
numery co to oznacza?

316
00:13:33,220 --> 00:13:34,790
>> GŁOŚNIK 1: To jest po prostu losowo.

317
00:13:34,790 --> 00:13:35,710
To jest po prostu śmieci.

318
00:13:35,710 --> 00:13:38,320
To jest po prostu coś, że twój
Komputer losowo przypisać.

319
00:13:38,320 --> 00:13:39,721

320
00:13:39,721 --> 00:13:40,220
Fajne.

321
00:13:40,220 --> 00:13:45,760
Tak, teraz możemy przejść przez i tak
teraz mamy to zwykły getString tekstu.

322
00:13:45,760 --> 00:13:48,600
Więc, pozwól mi tylko przedstawić to, co
będzie się działo, kiedy uderzył Dalej tutaj.

323
00:13:48,600 --> 00:13:51,320
Nasza GDB rodzaju znika, prawda?

324
00:13:51,320 --> 00:13:55,720
To dlatego, że getString
Obecnie wykonanie, prawda?

325
00:13:55,720 --> 00:14:01,460
Tak więc, kiedy widzieliśmy zwykły tekst jest równa
GetString, otwarte nawiasy i nawiasy,

326
00:14:01,460 --> 00:14:04,380
i trafiliśmy Dalej, że ma
faktycznie wykonywane teraz.

327
00:14:04,380 --> 00:14:06,580
Tak, to czeka na
nam coś wejściowego.

328
00:14:06,580 --> 00:14:13,560
>> Tak, mamy zamiar wprowadzić nasze jedzenie
to co to braku jak już mówiłem

329
00:14:13,560 --> 00:14:18,020
i że po prostu mówi, że jest to
zakończeniu wykonywania, że ​​zamknięte

330
00:14:18,020 --> 00:14:19,980
Oznacza to wspornik
wyjściu z tej pętli.

331
00:14:19,980 --> 00:14:21,170

332
00:14:21,170 --> 00:14:25,420
Tak więc, możemy trafić Dalej, a teraz, jak jestem
się, że jesteś zaznajomieni z Cezara,

333
00:14:25,420 --> 00:14:27,260
to, co to jest linia zrobić.

334
00:14:27,260 --> 00:14:32,030
To dla int i jest równa 0, N równa
Strlen, zwykły tekst, a następnie

335
00:14:32,030 --> 00:14:33,960
I jest mniejsze od n, I, plus, oraz.

336
00:14:33,960 --> 00:14:35,210
Co to jest pętla zrobić?

337
00:14:35,210 --> 00:14:37,900

338
00:14:37,900 --> 00:14:39,160
Otwórz wiadomość.

339
00:14:39,160 --> 00:14:39,770
Fajne.

340
00:14:39,770 --> 00:14:41,330
Więc zacznijmy robić.

341
00:14:41,330 --> 00:14:47,210
>> Tak więc, należy ten warunek
pasuje dla naszego pierwszego?

342
00:14:47,210 --> 00:14:52,250
Jeśli jest to B, to jest zwykły tekst I. Mamy
można uzyskać informacje na temat naszych mieszkańców.

343
00:14:52,250 --> 00:14:53,610

344
00:14:53,610 --> 00:14:57,970
Tak więc, jest zero, a jeżeli sześć, co
oczekujemy, i nasz klucz jest trzy.

345
00:14:57,970 --> 00:14:59,227
Wszystko to ma sens, prawda?

346
00:14:59,227 --> 00:15:01,310
Liczby te są
dokładnie to, co powinno być.

347
00:15:01,310 --> 00:15:02,590

348
00:15:02,590 --> 00:15:03,870
Tak, nucić?

349
00:15:03,870 --> 00:15:05,620
GŁOŚNIK 3: mam
liczb losowych dla kopalni.

350
00:15:05,620 --> 00:15:09,156

351
00:15:09,156 --> 00:15:12,030
GŁOŚNIK 1: Cóż, możemy check-- --we
mogą rozmawiać o tym za chwilę.

352
00:15:12,030 --> 00:15:14,110

353
00:15:14,110 --> 00:15:15,750
Ale powinno być coraz to.

354
00:15:15,750 --> 00:15:17,700

355
00:15:17,700 --> 00:15:20,130
Tak więc, jeśli mamy kapitał
B dla naszej pierwszej,

356
00:15:20,130 --> 00:15:22,080
warunek ten powinien go złapać, prawda?

357
00:15:22,080 --> 00:15:27,120
Tak więc, jeśli uderzymy Dalej widzimy
Jeśli rzeczywiście, że to wykonuje.

358
00:15:27,120 --> 00:15:29,220
Bo jeśli po
razem w kodzie,

359
00:15:29,220 --> 00:15:33,460
ta linia tutaj, gdzie ja zwykły tekst
otrzymuje się z tego arytmetyki

360
00:15:33,460 --> 00:15:35,720
wykonywana tylko wówczas, kiedy
Warunkiem jest prawidłowe prawo?

361
00:15:35,720 --> 00:15:36,905

362
00:15:36,905 --> 00:15:40,240
>> GDB będzie tylko pokazać,
rzeczy, które są faktycznie wykonującego.

363
00:15:40,240 --> 00:15:45,140
Więc jeśli ten warunek nie został spełniony, to
po prostu się przejść do następnej linii.

364
00:15:45,140 --> 00:15:46,540
OK?

365
00:15:46,540 --> 00:15:48,510
Tak, mamy to.

366
00:15:48,510 --> 00:15:51,171
To oznacza, że ​​to wspornik
zamknięte z tej pętli teraz.

367
00:15:51,171 --> 00:15:52,420
Tak, to będzie zacząć od nowa.

368
00:15:52,420 --> 00:15:54,760

369
00:15:54,760 --> 00:15:56,280
Tak po prostu.

370
00:15:56,280 --> 00:15:59,120
Tak, że możemy uzyskać informacje
o naszych mieszkańców tutaj,

371
00:15:59,120 --> 00:16:02,575
i widzimy, że nasz pierwszy
List nie zmieniło, prawda?

372
00:16:02,575 --> 00:16:05,150
To teraz E, tak jak powinno być.

373
00:16:05,150 --> 00:16:07,360
Tak, możemy kontynuować.

374
00:16:07,360 --> 00:16:08,500
>> I mamy to sprawdzić.

375
00:16:08,500 --> 00:16:09,916
I ta kontrola powinna działać, prawda?

376
00:16:09,916 --> 00:16:12,570
To A. powinien być zmieniony
trzy litery do przodu.

377
00:16:12,570 --> 00:16:14,320

378
00:16:14,320 --> 00:16:16,530
Ale jeśli zauważysz, my
dostać coś innego.

379
00:16:16,530 --> 00:16:17,580

380
00:16:17,580 --> 00:16:22,860
Tak więc w tym przypadku aż tutaj, to złapać
to i tak ta linia wykonana,

381
00:16:22,860 --> 00:16:28,620
które zmodyfikowano naszą B.
Jednak w tym przypadku, tutaj

382
00:16:28,620 --> 00:16:32,860
mamy, że to po prostu pominąć go,
i udał się do [? L Siff. ?]

383
00:16:32,860 --> 00:16:34,660
Więc coś się tam dzieje.

384
00:16:34,660 --> 00:16:37,780
Co to się mówi, jest to, że
wiemy, że powinna nadrobić tutaj,

385
00:16:37,780 --> 00:16:39,200
ale to nie jest.

386
00:16:39,200 --> 00:16:42,210
Czy ktoś może zobaczyć, co nasze
Problem jest w tym wierszu?

387
00:16:42,210 --> 00:16:45,380

388
00:16:45,380 --> 00:16:46,969
To bardzo minut rzeczą.

389
00:16:46,969 --> 00:16:48,510
I można też spojrzeć na kodzie.

390
00:16:48,510 --> 00:16:49,980

391
00:16:49,980 --> 00:16:54,940
Jest line-- również zapomnieć, co to jest linia
w there-- ale w [niesłyszalne].

392
00:16:54,940 --> 00:16:55,480
Tak?

393
00:16:55,480 --> 00:16:58,639
>> GŁOŚNIK 4: Jest na większe niż
strona jeśli czytasz go w książce.

394
00:16:58,639 --> 00:16:59,430
GŁOŚNIK 1: Dokładnie.

395
00:16:59,430 --> 00:17:02,620
Tak więc, nie można powiedzieć, debugger
ty, ale debugger

396
00:17:02,620 --> 00:17:05,880
może dostać się do linii
że wiesz, nie działa.

397
00:17:05,880 --> 00:17:09,319
A czasem, kiedy szczególnie
później w semestrze, kiedy

398
00:17:09,319 --> 00:17:12,910
masz do czynienia z setek,
sto kilka linii kodu, a ty

399
00:17:12,910 --> 00:17:16,190
nie wiem gdzie to jest w przypadku braku,
jest to świetny sposób, aby to zrobić.

400
00:17:16,190 --> 00:17:17,900

401
00:17:17,900 --> 00:17:18,989
Tak, uważamy, że nasz błąd.

402
00:17:18,989 --> 00:17:21,530
Można to naprawić w pliku,
a następnie można go uruchomić ponownie,

403
00:17:21,530 --> 00:17:23,029
i wszystko będzie działać idealnie.

404
00:17:23,029 --> 00:17:24,970

405
00:17:24,970 --> 00:17:30,590
A najważniejszą rzeczą jest
może się to wydawać, OK.

406
00:17:30,590 --> 00:17:31,090
Tak.

407
00:17:31,090 --> 00:17:31,370
Fajne.

408
00:17:31,370 --> 00:17:32,744
Wiedziałeś, co szukasz.

409
00:17:32,744 --> 00:17:34,910
Więc wiedziałem, co robić.

410
00:17:34,910 --> 00:17:39,021
>> GDB może być bardzo pomocne, ponieważ Ciebie
Można wydrukować wszystkie te rzeczy, które

411
00:17:39,021 --> 00:17:39,520
nie.

412
00:17:39,520 --> 00:17:41,160
To o wiele bardziej przydatne niż printf.

413
00:17:41,160 --> 00:17:43,440
Ilu z korzystania
jak sprawozdania printf

414
00:17:43,440 --> 00:17:46,200
dowiedzieć się, gdzie błąd był, prawda?

415
00:17:46,200 --> 00:17:48,450
Tak, z tego, że nie robić
trzeba wracać,

416
00:17:48,450 --> 00:17:51,139
i jak komentując w
Printf lub komentując na zewnątrz,

417
00:17:51,139 --> 00:17:52,930
i dowiedzieć się, co
powinno być drukowane.

418
00:17:52,930 --> 00:17:55,670
To właściwie tylko pozwala na
krok po kroku, wydrukować rzeczy

419
00:17:55,670 --> 00:18:00,000
jak idziesz przez, tak, można
obserwować, jak zmieniają się w czasie rzeczywistym,

420
00:18:00,000 --> 00:18:02,190
w programie jest uruchomiony.

421
00:18:02,190 --> 00:18:04,390
>> I zajmuje to trochę
trochę przyzwyczaić.

422
00:18:04,390 --> 00:18:07,850
Gorąco polecam po prostu rodzaj
bycia z nim trochę sfrustrowany

423
00:18:07,850 --> 00:18:08,930
do teraz.

424
00:18:08,930 --> 00:18:13,450
Jeśli spędzasz godziny na
w przyszłym tygodniu nauczenie GDB,

425
00:18:13,450 --> 00:18:16,140
można się zapisać
tyle czasu później.

426
00:18:16,140 --> 00:18:18,750
I dosłownie. powiedzieć
to ludzi rocznie,

427
00:18:18,750 --> 00:18:23,890
i pamiętam, kiedy wziąłem
klasa, ja na to będę w porządku.

428
00:18:23,890 --> 00:18:24,700
Nie.

429
00:18:24,700 --> 00:18:27,030
Pset 6 przyszedł na i byłem
jak, mam zamiar uczyć się

430
00:18:27,030 --> 00:18:29,500
jak używać GDB, bo nie
wiedzieć, co się tu dzieje.

431
00:18:29,500 --> 00:18:32,940
>> Więc jeśli masz trochę czasu, więc
używać go na mniejszych programów

432
00:18:32,940 --> 00:18:35,697
że masz zamiar być
w pracy, jak praca

433
00:18:35,697 --> 00:18:37,530
przez coś podobnego
Visionare, tak.

434
00:18:37,530 --> 00:18:38,800

435
00:18:38,800 --> 00:18:42,850
Albo jeśli chcesz dodatkowej praktyki, jestem pewien,
Mógłbym wymyślić programów buggy,

436
00:18:42,850 --> 00:18:45,300
Ci debugowania, jeśli chcesz.

437
00:18:45,300 --> 00:18:49,300
>> Ale jeśli tylko trochę czasu, aby dostać się
do niego, po prostu bawić się z nim,

438
00:18:49,300 --> 00:18:50,550
to będzie naprawdę dobrze służyć.

439
00:18:50,550 --> 00:18:52,591
I to jest naprawdę jeden z
te rzeczy, które po prostu

440
00:18:52,591 --> 00:18:57,340
spróbować i ubrudzić sobie ręce
się, zanim naprawdę go zrozumieć.

441
00:18:57,340 --> 00:19:02,090
I tak naprawdę tylko raz zrozumiałem
Musiałem rzeczy debugowania z nim

442
00:19:02,090 --> 00:19:08,170
i to jest o wiele ładniejsza, aby mieć pomysł
jak debugować raczej wcześniej niż później.

443
00:19:08,170 --> 00:19:08,850
OK.

444
00:19:08,850 --> 00:19:09,625
Fajne.

445
00:19:09,625 --> 00:19:12,960
Wiem, że to trochę jak
Crash Course w GDB,

446
00:19:12,960 --> 00:19:16,400
i na pewno działa na coraz
nich patrzeć większe następnym razem.

447
00:19:16,400 --> 00:19:17,590

448
00:19:17,590 --> 00:19:18,280
Fajne.

449
00:19:18,280 --> 00:19:20,390
>> Tak więc, jeśli wrócimy do naszego programu PowerPoint.

450
00:19:20,390 --> 00:19:27,194

451
00:19:27,194 --> 00:19:28,110
Czy to będzie działać?

452
00:19:28,110 --> 00:19:29,711

453
00:19:29,711 --> 00:19:30,210
Awh.

454
00:19:30,210 --> 00:19:31,101
Tak.

455
00:19:31,101 --> 00:19:31,600
OK.

456
00:19:31,600 --> 00:19:35,480
Tak więc, jeśli kiedykolwiek potrzeba żadnej z
tych, ponownie, jest lista.

457
00:19:35,480 --> 00:19:37,160

458
00:19:37,160 --> 00:19:40,830
Więc Binary Search, które każdy
Pamięta wielkie widowisko Dawida

459
00:19:40,830 --> 00:19:42,259
zgrywania książek telefonicznych w połowie.

460
00:19:42,259 --> 00:19:44,050
I naprawdę nie dostać
książki telefoniczne więcej,

461
00:19:44,050 --> 00:19:46,530
bo jak Skąd
dostać książki telefoniczne w tych dniach?

462
00:19:46,530 --> 00:19:48,220
I naprawdę nie wiem.

463
00:19:48,220 --> 00:19:49,840

464
00:19:49,840 --> 00:19:50,590
Binary Search.

465
00:19:50,590 --> 00:19:52,464
Czy ktoś pamięta
Jak działa wyszukiwanie? binarny

466
00:19:52,464 --> 00:19:54,380

467
00:19:54,380 --> 00:19:55,220
Każdy, kto w ogóle?

468
00:19:55,220 --> 00:19:56,325
Tak?

469
00:19:56,325 --> 00:19:58,283
GŁOŚNIK 5: Wiesz, kiedy
patrzysz na których połowa

470
00:19:58,283 --> 00:20:01,146
byłoby to w, podstawie, że
i pozbyć się druga połowa.

471
00:20:01,146 --> 00:20:01,896
>> GŁOŚNIK 1 Dokładnie.

472
00:20:01,896 --> 00:20:06,290
Tak, Binary Search, to rodzaj A--
--we lubię nazywać go podzielić i podbić.

473
00:20:06,290 --> 00:20:09,170
Więc, co musisz zrobić, to
będziesz wyglądać w środku,

474
00:20:09,170 --> 00:20:11,990
i zobaczysz czy pasuje
czego szukasz.

475
00:20:11,990 --> 00:20:15,420
A jeśli nie, to spróbuj
dowiedzieć się, czy to będzie w lewo

476
00:20:15,420 --> 00:20:16,450
połowa lub prawa połowa.

477
00:20:16,450 --> 00:20:19,325
Tak, to może być, jeśli szukasz
na coś, co jest alfabetycznie,

478
00:20:19,325 --> 00:20:20,720
widzisz, och.

479
00:20:20,720 --> 00:20:22,750
Czy Allison się przed M?

480
00:20:22,750 --> 00:20:23,250
Tak.

481
00:20:23,250 --> 00:20:25,030
Tak, mamy zamiar
spojrzeć na pierwsze półrocze.

482
00:20:25,030 --> 00:20:26,450
>> Albo może to być jak z liczbami.

483
00:20:26,450 --> 00:20:28,830
Wszystko, co można
porównania, może być sortowane.

484
00:20:28,830 --> 00:20:29,920

485
00:20:29,920 --> 00:20:31,260
Możesz użyć wyszukiwania binarnego na.

486
00:20:31,260 --> 00:20:32,340

487
00:20:32,340 --> 00:20:37,455
Tak, ktoś pamięta to
Wykres lub co to jest?

488
00:20:37,455 --> 00:20:39,520
To Asymptotic złożoności.

489
00:20:39,520 --> 00:20:42,830
Tak, to właśnie wykres
opisuje, jak długo

490
00:20:42,830 --> 00:20:46,230
zabierze Cię do rozwiązania problemu, jak
zwiększyć liczbę rzeczy

491
00:20:46,230 --> 00:20:47,090
że używasz.

492
00:20:47,090 --> 00:20:51,260
>> Tak więc, mamy N, która jest czas liniowy.

493
00:20:51,260 --> 00:20:54,560
Jeśli n ponad dwie, nieco
lepiej, wciąż rośnie bardzo szybko.

494
00:20:54,560 --> 00:20:58,360
A potem mamy Zaloguj, która jest
co uważamy za Binary Search.

495
00:20:58,360 --> 00:21:03,630
Jeśli zauważymy, jako problemu
dostaje dużo i znacznie większy,

496
00:21:03,630 --> 00:21:06,600
Czas potrzebny Ci go rozwiązać
tak naprawdę nie zwiększy to znacznie.

497
00:21:06,600 --> 00:21:09,010
To jak porównać
tutaj na początku.

498
00:21:09,010 --> 00:21:10,060
Jesteś jak, OK.

499
00:21:10,060 --> 00:21:13,000
Wszystko, co tu naprawdę nie ma
względu na to, który z nich korzystamy,

500
00:21:13,000 --> 00:21:16,220
ale można dostać się do miliona, miliarda.

501
00:21:16,220 --> 00:21:20,010
Próbujesz znaleźć some-- --you're
próbuje znaleźć igłę w stogu siana.

502
00:21:20,010 --> 00:21:21,550
>> Myślę, że chcesz ten problem.

503
00:21:21,550 --> 00:21:25,850
Chcesz tej złożoności, a nie
liniowy, bo za wszystko

504
00:21:25,850 --> 00:21:30,049
wiedzieć gonna być przeszukiwania
każdy igły, co siana,

505
00:21:30,049 --> 00:21:31,340
próbuje szukać swojej igły.

506
00:21:31,340 --> 00:21:34,730
I to nie jest zbyt zabawne, moim zdaniem.

507
00:21:34,730 --> 00:21:35,500
Lubię szybko.

508
00:21:35,500 --> 00:21:36,620
Lubię wydajne.

509
00:21:36,620 --> 00:21:40,450
I jako pracowici uczniowie You
faceci są, wiesz pracować mądrzej,

510
00:21:40,450 --> 00:21:43,010
nie trudniej typu rzecz, jak ci
może uzupełnić te algorytmy.

511
00:21:43,010 --> 00:21:45,110

512
00:21:45,110 --> 00:21:47,910
>> Więc idziemy na spacer
przez tylko szybki przykład.

513
00:21:47,910 --> 00:21:51,090
Myślę, że chłopaki powinni mieć
ręka na Binary Search,

514
00:21:51,090 --> 00:21:54,352
ale w przypadku gdy ktoś jest mało
rozmyte, chcę go wzmocnić,

515
00:21:54,352 --> 00:21:56,310
będziemy po prostu pójść
poprzez przykład.

516
00:21:56,310 --> 00:21:59,490
Tak więc, jeśli szukasz
Tablica zawiera siedem.

517
00:21:59,490 --> 00:22:00,540

518
00:22:00,540 --> 00:22:06,010
>> Więc, po pierwsze, co robimy jest
wygląda w środku, prawda?

519
00:22:06,010 --> 00:22:09,340
A także masz zamiar być kodowanie
Binary Szukaj w ciągu sekundy.

520
00:22:09,340 --> 00:22:11,310
Tak, to będzie zabawa.

521
00:22:11,310 --> 00:22:13,710
Więc patrzymy w
średnie małe tablice 3.

522
00:22:13,710 --> 00:22:15,501
Czy 3 równe 7?

523
00:22:15,501 --> 00:22:16,000
Nie.

524
00:22:16,000 --> 00:22:18,670

525
00:22:18,670 --> 00:22:19,550
To sześć.

526
00:22:19,550 --> 00:22:21,480
Tak, to jest mniej niż
lub większe niż siedem?

527
00:22:21,480 --> 00:22:23,080

528
00:22:23,080 --> 00:22:23,960
Mniej niż.

529
00:22:23,960 --> 00:22:24,570
Tak.

530
00:22:24,570 --> 00:22:25,170
Nice guys pracy.

531
00:22:25,170 --> 00:22:25,569

532
00:22:25,569 --> 00:22:27,360
Czuję, jak powinienem
cukierki, bo mają

533
00:22:27,360 --> 00:22:29,460
chcą ją wyrzucić do stoczni.

534
00:22:29,460 --> 00:22:30,270
To, co mam zamiar zrobić w przyszłym tygodniu.

535
00:22:30,270 --> 00:22:31,436
Będzie na bieżąco was ostre.

536
00:22:31,436 --> 00:22:32,560

537
00:22:32,560 --> 00:22:34,690
>> Tak, że wyrzucamy
Pierwsza połowa, prawda?

538
00:22:34,690 --> 00:22:35,670
był on mniej niż.

539
00:22:35,670 --> 00:22:39,325
Wiemy, że wszystko,
po tej stronie lewej

540
00:22:39,325 --> 00:22:41,700
będzie mniejsza niż
my rzeczywiście szukają.

541
00:22:41,700 --> 00:22:43,491
Tak więc, nie ma potrzeby, aby
zwracać uwagę na to.

542
00:22:43,491 --> 00:22:45,120
Zapomnij o tym.

543
00:22:45,120 --> 00:22:48,720
Tak, teraz patrzymy na naszej prawej stronie,
i patrzymy na środku tam,

544
00:22:48,720 --> 00:22:50,510
a teraz jest dziewięć.

545
00:22:50,510 --> 00:22:55,510
Tak, 9 is-- --Everyone?

546
00:22:55,510 --> 00:22:57,470
Większe niż to, co my
szuka, prawda?

547
00:22:57,470 --> 00:22:59,860
Tak, mamy zamiar rzucić
się wszystko prawo.

548
00:22:59,860 --> 00:23:00,970

549
00:23:00,970 --> 00:23:01,940
Tak.

550
00:23:01,940 --> 00:23:03,700
Teraz wszyscy jesteśmy z lewej jest jeden.

551
00:23:03,700 --> 00:23:07,760
Więc sprawdzić, co jest w tym jeden
szukamy? to jest.

552
00:23:07,760 --> 00:23:08,970
Znaleźliśmy to, co chcieliśmy.

553
00:23:08,970 --> 00:23:10,440

554
00:23:10,440 --> 00:23:11,690
Tak skończymy.

555
00:23:11,690 --> 00:23:12,550
Dwuliniowy Szukaj.

556
00:23:12,550 --> 00:23:15,740
>> A jeśli zauważysz, my
miał siedem wejść tam.

557
00:23:15,740 --> 00:23:24,320
To tylko nas jak trzy razy,
ale jeśli robisz jak miliard,

558
00:23:24,320 --> 00:23:28,190
Wiecie ile kroków miałoby to
podjąć, jeśli mieliśmy cztery miliardy rzeczy?

559
00:23:28,190 --> 00:23:29,940

560
00:23:29,940 --> 00:23:30,455
Wszelkie domysły?

561
00:23:30,455 --> 00:23:32,286

562
00:23:32,286 --> 00:23:33,960
To 32.

563
00:23:33,960 --> 00:23:37,110
32 kroków, aby znaleźć coś,
w czterech miliardów

564
00:23:37,110 --> 00:23:39,650
element tablicy z powodu potęgi dwójki.

565
00:23:39,650 --> 00:23:43,550
Więc dwa jest do 32, jest do czterech miliardów.

566
00:23:43,550 --> 00:23:50,430
>> Więc dość szalony jak jesteś nadal w
jak stosunkowo niewielkiej liczbie etapów

567
00:23:50,430 --> 00:23:52,650
znaleźć coś w
cztery miliardy elementów.

568
00:23:52,650 --> 00:23:55,730
Więc na tej notatce, że jesteśmy
Ten kod będzie

569
00:23:55,730 --> 00:23:58,950
więc wy może rzeczywiście
rodzaj zobaczyć jak to działa.

570
00:23:58,950 --> 00:24:01,520
W porządku, więc chłopaki mogą kodować.

571
00:24:01,520 --> 00:24:04,100
Zamierzam niech chłopaki
rozmawiać na trochę.

572
00:24:04,100 --> 00:24:07,970
Poznaj ludzi wokół ciebie, co jest
co ktoś chciał z ostatniego odcinka.

573
00:24:07,970 --> 00:24:10,280
>> Więc poznać ludzi wokół ciebie.

574
00:24:10,280 --> 00:24:11,305
Dyskusja na trochę.

575
00:24:11,305 --> 00:24:12,580

576
00:24:12,580 --> 00:24:15,730
A wszystko czego chcę od ciebie
faceci to teraz tylko

577
00:24:15,730 --> 00:24:17,575
spróbować stworzyć zarys Pseudokod.

578
00:24:17,575 --> 00:24:18,075
OK?

579
00:24:18,075 --> 00:24:20,825

580
00:24:20,825 --> 00:24:21,325
Whoa.

581
00:24:21,325 --> 00:24:23,320

582
00:24:23,320 --> 00:24:29,520
Wszystko, czego chcę od was to, że jesteś
po prostu się wypełnić ten czas sprawy.

583
00:24:29,520 --> 00:24:32,170
Więc postawiłem to górna
i dolne granice, które

584
00:24:32,170 --> 00:24:35,250
stanowią początek
i koniec naszej tablicy.

585
00:24:35,250 --> 00:24:40,440
I masz zamiar faktycznie
pętli i dowiedzieć się,

586
00:24:40,440 --> 00:24:42,470
co robimy w tej pętli while.

587
00:24:42,470 --> 00:24:45,810
>> Więc jeśli można dowiedzieć out-- mam
wskazówka there-- jakie są przypadki

588
00:24:45,810 --> 00:24:46,640
że my tu mamy?

589
00:24:46,640 --> 00:24:48,100

590
00:24:48,100 --> 00:24:51,560
Tak więc, jeśli chcesz dowiedzieć się,
przypadki, będziemy pseudokod tych

591
00:24:51,560 --> 00:24:53,350
a potem będziemy rzeczywiście kodować je.

592
00:24:53,350 --> 00:24:55,330
I to będzie, ja
myślę, mam nadzieję, że będziesz

593
00:24:55,330 --> 00:24:56,788
być trochę łatwiej niż można się spodziewać.

594
00:24:56,788 --> 00:24:57,554

595
00:24:57,554 --> 00:25:00,220
Bo to nie jest tak dużo kodu,
w rzeczywistości, co jest naprawdę fajne.

596
00:25:00,220 --> 00:25:34,110

597
00:25:34,110 --> 00:25:35,018
>> Mm-hm?

598
00:25:35,018 --> 00:25:35,893
>> STUDENT: [niesłyszalne]?

599
00:25:35,893 --> 00:25:36,984

600
00:25:36,984 --> 00:25:37,650
INSTRUKTOR: Tak.

601
00:25:37,650 --> 00:25:38,595
Było coś
znaleźć się w środku.

602
00:25:38,595 --> 00:25:39,552
>> Uczeń: Tak więc możemy użyć.

603
00:25:39,552 --> 00:25:39,770
OK.

604
00:25:39,770 --> 00:25:40,603
>> INSTRUKTOR: Idealny.

605
00:25:40,603 --> 00:25:42,950
Więc to jest pierwsza rzecz, którą trzeba zrobić.

606
00:25:42,950 --> 00:25:44,330
Więc znaleźć pola.

607
00:25:44,330 --> 00:25:45,415

608
00:25:45,415 --> 00:25:45,915
Świetne.

609
00:25:45,915 --> 00:25:47,770

610
00:25:47,770 --> 00:25:55,010
Więc masz pomysł, jak moglibyśmy
rzeczywiście znaleźć środek z kodem?

611
00:25:55,010 --> 00:25:55,980
>> UCZEŃ: Tak.

612
00:25:55,980 --> 00:25:57,000
n na 2?

613
00:25:57,000 --> 00:25:58,500

614
00:25:58,500 --> 00:25:59,500
INSTRUKTOR: Tak n nad 2.

615
00:25:59,500 --> 00:26:05,170
Więc jedną rzeczą do zapamiętania jest to, że
twoje górne i dolne granice zmienić.

616
00:26:05,170 --> 00:26:08,110
Wciąż zwężenie części
tablicy szukamy się.

617
00:26:08,110 --> 00:26:11,970
Tak n ponad 2 działa tylko
dla pierwszej rzeczy robimy.

618
00:26:11,970 --> 00:26:17,810
Więc przy górnej i dolnej pod uwagę,
w jaki sposób możemy uzyskać tego środkowego elementu?

619
00:26:17,810 --> 00:26:20,640
Ponieważ chcemy środku
pomiędzy górną i dolną, prawda?

620
00:26:20,640 --> 00:26:21,730

621
00:26:21,730 --> 00:26:22,494
Mm-hm?

622
00:26:22,494 --> 00:26:23,369
>> STUDENT: [niesłyszalne].

623
00:26:23,369 --> 00:26:26,170

624
00:26:26,170 --> 00:26:28,080
>> INSTRUKTOR: Więc mamy trochę pola.

625
00:26:28,080 --> 00:26:32,730
I to będzie górna oraz dolna ponad dwa.

626
00:26:32,730 --> 00:26:34,740

627
00:26:34,740 --> 00:26:35,690
Niesamowite.

628
00:26:35,690 --> 00:26:36,570
Nie idziemy.

629
00:26:36,570 --> 00:26:37,280
Jeden wiersz w dół.

630
00:26:37,280 --> 00:26:38,560
Jesteście na najlepszej drodze.

631
00:26:38,560 --> 00:26:41,400
Więc teraz, że mamy
średnim, co chcemy zrobić?

632
00:26:41,400 --> 00:26:45,050

633
00:26:45,050 --> 00:26:45,900
Po prostu w ogóle.

634
00:26:45,900 --> 00:26:47,734
Nie trzeba go zakodować.

635
00:26:47,734 --> 00:26:48,335
Tak.

636
00:26:48,335 --> 00:26:49,210
STUDENT: [niesłyszalne]?

637
00:26:49,210 --> 00:27:00,310

638
00:27:00,310 --> 00:27:10,310
INSTRUKTOR: Więc to dlatego, że jesteś oraz
znalezienie średnio pomiędzy dwa

639
00:27:10,310 --> 00:27:10,810
nimi.

640
00:27:10,810 --> 00:27:11,890

641
00:27:11,890 --> 00:27:17,370
Więc jeśli myślisz o nich jako rodzaj
zwiększania się ze stron

642
00:27:17,370 --> 00:27:21,640
myśleć o tym, jak podejście
środkowy, chcesz tak.

643
00:27:21,640 --> 00:27:27,150
Więc jeśli były po obu stronach
środek i mamy jak 5 i 7.

644
00:27:27,150 --> 00:27:31,440
Po dodaniu ich razem ci
dostać 12, podzielić przez 2, to 6.

645
00:27:31,440 --> 00:27:33,726
>> Czasami trudno
wyjaśnić, dlaczego to działa,

646
00:27:33,726 --> 00:27:35,600
ale jeśli pracujesz przez
przykład czasem,

647
00:27:35,600 --> 00:27:37,962
to pomoże Ci dowiedzieć się, czy
powinno być plus lub minus.

648
00:27:37,962 --> 00:27:38,846
Tak.

649
00:27:38,846 --> 00:27:40,830
>> STUDENT: [niesłyszalne]
dokładnie w środku

650
00:27:40,830 --> 00:27:43,950
gdyby mieli przypadku, gdy
jest dużo mniejszych liczbach

651
00:27:43,950 --> 00:27:45,860
i jak jeden wielu?

652
00:27:45,860 --> 00:27:49,750
>> INSTRUKTOR: Więc wszystko, czego potrzebujesz
jest środek tablicy.

653
00:27:49,750 --> 00:27:53,010
Więc jeśli miał kilka małych ilościach
i wtedy naprawdę duża liczba

654
00:27:53,010 --> 00:27:54,799
na końcu, to nie ma znaczenia.

655
00:27:54,799 --> 00:27:56,840
Ważne jest to, że
są one klasyfikowane, po prostu

656
00:27:56,840 --> 00:27:59,339
zajrzeć do środka
Tablica bo nadal jesteś

657
00:27:59,339 --> 00:28:00,700
krojenie problemu w połowie.

658
00:28:00,700 --> 00:28:03,020

659
00:28:03,020 --> 00:28:03,680
Fajne.

660
00:28:03,680 --> 00:28:06,430
Więc teraz, że mamy
średnim, co robimy dalej?

661
00:28:06,430 --> 00:28:07,150
>> STUDENT: Porównaj.

662
00:28:07,150 --> 00:28:08,150
INSTRUKTOR: porównanie.

663
00:28:08,150 --> 00:28:11,670
Więc porównanie środek do value_wanted.

664
00:28:11,670 --> 00:28:14,300

665
00:28:14,300 --> 00:28:15,160
Fajne.

666
00:28:15,160 --> 00:28:17,950
Więc widać tutaj mamy
ta wartość chcemy się tutaj.

667
00:28:17,950 --> 00:28:22,012

668
00:28:22,012 --> 00:28:23,095
Pamiętaj, to jest tablica.

669
00:28:23,095 --> 00:28:24,100

670
00:28:24,100 --> 00:28:26,970
Tak więc środkowa odnosi się do indeksu.

671
00:28:26,970 --> 00:28:29,785
Dlatego chcemy, aby zrobić wartości środku.

672
00:28:29,785 --> 00:28:32,380

673
00:28:32,380 --> 00:28:35,650
Nie zapomnij, jeśli chcesz
porównać, dwu równych.

674
00:28:35,650 --> 00:28:38,250
Ty jesteś pojedynczy równa
po prostu się go przypisać,

675
00:28:38,250 --> 00:28:41,090
a następnie, oczywiście, jest to
będzie wartość, którą chcesz.

676
00:28:41,090 --> 00:28:42,300
Więc nie rób tego.

677
00:28:42,300 --> 00:28:44,350
>> Więc mamy zamiar sprawdzić, czy
wartości w środku

678
00:28:44,350 --> 00:28:46,460
jest równa wartości chcemy.

679
00:28:46,460 --> 00:28:47,749

680
00:28:47,749 --> 00:28:48,790
Nie zapomnij szelki.

681
00:28:48,790 --> 00:28:50,520

682
00:28:50,520 --> 00:28:52,235
Dropbox powinien odejść.

683
00:28:52,235 --> 00:28:54,140

684
00:28:54,140 --> 00:28:56,200
Więc co mamy zrobić w tym przypadku?

685
00:28:56,200 --> 00:28:59,360
Jeśli to, co chcemy wrócić?

686
00:28:59,360 --> 00:29:01,510

687
00:29:01,510 --> 00:29:02,626
Próbujemy powiedzieć.

688
00:29:02,626 --> 00:29:03,440
>> STUDENT: wydrukować.

689
00:29:03,440 --> 00:29:05,314
>> INSTRUKTOR: Cóż,
nie chce wydrukować.

690
00:29:05,314 --> 00:29:08,220
Więc to jest bool tutaj, więc
Aby powrócić prawdziwe lub fałszywe.

691
00:29:08,220 --> 00:29:12,280
Mówimy, jest to liczba
[? RRA? ?] Więc jeśli tak jest,

692
00:29:12,280 --> 00:29:13,788
po prostu wrócić to prawda.

693
00:29:13,788 --> 00:29:16,780

694
00:29:16,780 --> 00:29:17,760
Jeśli mogę przeliterować prawda.

695
00:29:17,760 --> 00:29:18,830

696
00:29:18,830 --> 00:29:20,805
>> STUDENT: Dlaczego nie wrócisz do zera?

697
00:29:20,805 --> 00:29:22,930
INSTRUKTOR: tak można
powrócić do zera, jeśli chciał.

698
00:29:22,930 --> 00:29:26,780
Ale w tym przypadku, ponieważ
nasza funkcja zwraca bool,

699
00:29:26,780 --> 00:29:28,962
musimy wrócić albo prawdziwe, albo fałszywe.

700
00:29:28,962 --> 00:29:30,920
STUDENT: Kiedy jesteś
mówiąc logiczną wyrażenia,

701
00:29:30,920 --> 00:29:33,450
Można ustawić go równa fałszywe?

702
00:29:33,450 --> 00:29:39,860
Podobnie jak w przypadku chcę powiedzieć, jeśli ten warunek
nie jest spełniony, jak jest górna równa false.

703
00:29:39,860 --> 00:29:42,332
Będzie to zrozumieć, jeśli tylko
umieścić fałszywy po drugiej stronie?

704
00:29:42,332 --> 00:29:43,040
INSTRUKTOR: Tak.

705
00:29:43,040 --> 00:29:44,820
Tak naprawdę, jeśli jesteś
zawsze robi coś

706
00:29:44,820 --> 00:29:49,600
jak jest górna lub jest niższa,
która zwraca true lub false

707
00:29:49,600 --> 00:29:53,850
i to jest rzeczywiście zły styl
powiedzmy równa jest równa true lub równych

708
00:29:53,850 --> 00:29:54,840
równa się fałszywe.

709
00:29:54,840 --> 00:30:00,210
Chcesz używać tego wyniku
tak samo jak czeku.

710
00:30:00,210 --> 00:30:04,720

711
00:30:04,720 --> 00:30:05,860
Nie to, co chciałem.

712
00:30:05,860 --> 00:30:08,150

713
00:30:08,150 --> 00:30:09,240
To jest to, co chciałem.

714
00:30:09,240 --> 00:30:13,205
Tak więc w przypadku prosisz
o czymś, jak zapisać to w c.

715
00:30:13,205 --> 00:30:16,320

716
00:30:16,320 --> 00:30:25,150
>> Więc jeśli mamy int main (void)
i coś w tym rodzaju.

717
00:30:25,150 --> 00:30:31,922
I masz, jeśli jest górna
jakiegoś wejścia i jesteś

718
00:30:31,922 --> 00:30:33,630
z pytaniem, czy można zrobić
coś w tym rodzaju?

719
00:30:33,630 --> 00:30:35,010

720
00:30:35,010 --> 00:30:35,679
Prawda?

721
00:30:35,679 --> 00:30:37,470
STUDENT: Starałem
to zrobić [niesłyszalne].

722
00:30:37,470 --> 00:30:38,450
Bo jeśli it's--

723
00:30:38,450 --> 00:30:39,200
INSTRUKTOR: Zgadza się.

724
00:30:39,200 --> 00:30:41,197
Więc chcesz to być fałszywe, prawda?

725
00:30:41,197 --> 00:30:41,780
UCZEŃ: Tak.

726
00:30:41,780 --> 00:30:45,960
INSTRUKTOR: Więc w tym przypadku
chcesz go wykonać, jeśli to nie jest prawda.

727
00:30:45,960 --> 00:30:50,510
Tak fajne robisz nie jest to.

728
00:30:50,510 --> 00:30:52,900

729
00:30:52,900 --> 00:30:55,650
Więc pamiętaj okrzyk
punkt neguje rzeczy?

730
00:30:55,650 --> 00:30:58,270
Mówi ona [niesłyszalne] nie oznacza.

731
00:30:58,270 --> 00:31:03,590
Więc jeśli spojrzymy na tak
ta część tu, że

732
00:31:03,590 --> 00:31:05,740
ocenia się, że
fałszywe, jak chcesz go.

733
00:31:05,740 --> 00:31:06,790

734
00:31:06,790 --> 00:31:09,880
Nie jest prawdą, która fałszywie
oznacza to, by wykonać.

735
00:31:09,880 --> 00:31:11,037
Czy to ma sens?

736
00:31:11,037 --> 00:31:11,620
UCZEŃ: Tak.

737
00:31:11,620 --> 00:31:12,453
INSTRUKTOR: Awesome.

738
00:31:12,453 --> 00:31:13,800

739
00:31:13,800 --> 00:31:14,300
OK.

740
00:31:14,300 --> 00:31:16,330
Więc może po prostu wrócić
prawda w tym przypadku.

741
00:31:16,330 --> 00:31:20,357
Więc teraz mamy dwie inne
przypadków w tym przypadku.

742
00:31:20,357 --> 00:31:21,565
Jakie są nasze dwa inne przypadki?

743
00:31:21,565 --> 00:31:31,610

744
00:31:31,610 --> 00:31:32,900
Zróbmy to w ten sposób.

745
00:31:32,900 --> 00:31:40,660
Więc zacznijmy od innego
jeśli wartości w środku

746
00:31:40,660 --> 00:31:43,230
jest mniejsza niż wartość chcemy.

747
00:31:43,230 --> 00:31:47,200

748
00:31:47,200 --> 00:31:52,020
Więc nasza wartość w środku jest mniej
od wartości, które szukasz.

749
00:31:52,020 --> 00:31:53,765

750
00:31:53,765 --> 00:31:56,720
>> Więc który związany prawda
że chcemy zaktualizować?

751
00:31:56,720 --> 00:31:57,870

752
00:31:57,870 --> 00:31:58,780
Górnej lub dolnej?

753
00:31:58,780 --> 00:32:01,440

754
00:32:01,440 --> 00:32:01,940
Górna?

755
00:32:01,940 --> 00:32:03,230

756
00:32:03,230 --> 00:32:06,470
Tak więc, po której stronie matrycy
będziemy się patrzysz?

757
00:32:06,470 --> 00:32:07,500
>> STUDENT: niższe.

758
00:32:07,500 --> 00:32:09,750
>> INSTRUKTOR: My idziemy
się patrząc na lewo.

759
00:32:09,750 --> 00:32:11,120
Więc jeśli jeszcze trochę wartość jest mniejsza.

760
00:32:11,120 --> 00:32:14,730
Więc swojej wartości średniej tutaj
jest mniejsza niż to, co chcemy.

761
00:32:14,730 --> 00:32:17,202
Dlatego chcemy, aby wziąć
prawa strona naszej tablicy.

762
00:32:17,202 --> 00:32:18,910
Więc mamy zamiar
aktualizować nasze dolnej granicy.

763
00:32:18,910 --> 00:32:20,210

764
00:32:20,210 --> 00:32:23,020
Przydzielimy więc nasze niższe.

765
00:32:23,020 --> 00:32:25,221
A co sądzisz niższa powinna być?

766
00:32:25,221 --> 00:32:26,304
STUDENT: wartość środkowa?

767
00:32:26,304 --> 00:32:27,446

768
00:32:27,446 --> 00:32:28,820
INSTRUKTOR: Więc środkowy value--

769
00:32:28,820 --> 00:32:30,136
STUDENT: Plus 1.

770
00:32:30,136 --> 00:32:31,010
INSTRUKTOR: --plus 1.

771
00:32:31,010 --> 00:32:32,300

772
00:32:32,300 --> 00:32:34,380
Czy ktoś może mi powiedzieć, dlaczego
mamy, że plus 1?

773
00:32:34,380 --> 00:32:35,730
>> STUDENT: [? Nie wartość?]
więcej równym.

774
00:32:35,730 --> 00:32:36,120
>> INSTRUKTOR: Zgadza się.

775
00:32:36,120 --> 00:32:38,661
Ponieważ wiemy już, że
nasza wartość środkowa nie jest równa

776
00:32:38,661 --> 00:32:42,750
to i chcemy wykluczyć
od wszystkich kolejnych poszukiwań.

777
00:32:42,750 --> 00:32:46,360
Jeśli zapomnisz, że plus 1, to
spodoba pętlę bez końca.

778
00:32:46,360 --> 00:32:49,620
I będziesz po prostu złapany w
nieskończonej pętli i wtedy wysypać

779
00:32:49,620 --> 00:32:50,370
i coś pójdzie źle.

780
00:32:50,370 --> 00:32:54,780
Więc zawsze upewnić się, że nie jesteś
w tym wartość, że po prostu

781
00:32:54,780 --> 00:32:55,380
spojrzał na.

782
00:32:55,380 --> 00:32:58,530
Więc zadbać o to z plusem 1.

783
00:32:58,530 --> 00:33:04,840
>> Więc teraz mamy ostatni warunek
które zawsze ze względów bezpieczeństwa

784
00:33:04,840 --> 00:33:12,664
można sprawdzić tutaj, w przeciwnym wypadku, jeśli wartość w
środkowy jest większy niż wartość

785
00:33:12,664 --> 00:33:13,163
chcemy.

786
00:33:13,163 --> 00:33:16,260

787
00:33:16,260 --> 00:33:20,230
Oznacza to, że chcemy
połowa lewa.

788
00:33:20,230 --> 00:33:21,350

789
00:33:21,350 --> 00:33:23,260
Więc który z nich będziemy aktualizować?

790
00:33:23,260 --> 00:33:23,760
Górna.

791
00:33:23,760 --> 00:33:25,470

792
00:33:25,470 --> 00:33:26,970
A co to jest ten jeden będzie równy?

793
00:33:26,970 --> 00:33:31,630

794
00:33:31,630 --> 00:33:33,690
Bliski minus 1, ponieważ,
Oczywiście, chcemy

795
00:33:33,690 --> 00:33:38,370
aby upewnić się, że nie jesteśmy
patrząc na tej wartości średniej ponownie.

796
00:33:38,370 --> 00:33:41,830

797
00:33:41,830 --> 00:33:45,110
A potem mamy to.

798
00:33:45,110 --> 00:33:45,610
To wszystko.

799
00:33:45,610 --> 00:33:46,820
To wszystko, przeszukiwanie binarne jest.

800
00:33:46,820 --> 00:33:48,190
To nie jest tak źle, prawda?

801
00:33:48,190 --> 00:33:51,590
To jak 10 linii
Kod z białej przestrzeni.

802
00:33:51,590 --> 00:33:57,510
Tak bardzo silny, bardzo przydatne, to będzie
być używając go w jednym ze swoich późniejszych psets.

803
00:33:57,510 --> 00:33:59,360
Może nie ten, ale później.

804
00:33:59,360 --> 00:34:00,670
Więc się go nauczyć.

805
00:34:00,670 --> 00:34:01,510
Uwielbiam go.

806
00:34:01,510 --> 00:34:02,980
Będzie traktować cię dobrze.

807
00:34:02,980 --> 00:34:05,370
Więc czy ktoś ma jakiekolwiek
pytania o poszukiwanie binarne?

808
00:34:05,370 --> 00:34:06,196
Tak.

809
00:34:06,196 --> 00:34:09,840
>> STUDENT: Czy to ważne
czy n jest parzyste, czy nieparzyste?

810
00:34:09,840 --> 00:34:10,750
>> INSTRUKTOR: Nie

811
00:34:10,750 --> 00:34:18,150
Dlatego, że rzucił ją na środku, jak
int, to po prostu obciąć go.

812
00:34:18,150 --> 00:34:21,600
Więc będzie zatrzymać liczbę całkowitą i będzie
ostatecznie uporządkować wszystko.

813
00:34:21,600 --> 00:34:23,909
Więc nie musisz się o to martwić.

814
00:34:23,909 --> 00:34:24,580
Każdy dobry?

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
Niesamowite.

817
00:34:26,850 --> 00:34:27,919
Fajne.

818
00:34:27,919 --> 00:34:30,836
Tak, wy się tym.

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
Pokaz slajdów.

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
Tak jak mówiliśmy, wiem
David wspomniał czasy pracy złożoności.

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> Tak więc w najlepszym przypadku, to tylko
jeden, który nazywamy stałą czasu.

825
00:34:50,340 --> 00:34:51,909
Czy ktoś może mi powiedzieć, dlaczego to może być?

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
Jaki rodzaj scenariusza, który pociąga za sobą?

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
Mm-hm.

830
00:34:58,760 --> 00:34:59,926
>> STUDENT: [niesłyszalne] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
INSTRUKTOR: Więc będąc w średnim
Pierwszym elementem, który przyszedł do nas, prawda?

833
00:35:03,830 --> 00:35:08,167
Więc albo tablica z jednego lub
co szukamy tylko

834
00:35:08,167 --> 00:35:09,750
dzieje się zimnica w środku.

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
Więc to jest nasz najlepszy przypadek.

837
00:35:13,380 --> 00:35:17,540
Dostać się do rzeczywistych problemów, prawdopodobnie nie
zamierza osiągnąć [niesłyszalne], że często.

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
Co z naszym najgorszym przypadku?

840
00:35:19,750 --> 00:35:21,270
Nasz najgorszy jest log n.

841
00:35:21,270 --> 00:35:25,360
I że ma do czynienia z całością
Uprawnienia dwie rzeczy, że rozmawialiśmy.

842
00:35:25,360 --> 00:35:30,930
>> Więc w najgorszym przypadku oznaczałoby to,
że musieliśmy posiekać tablicę w dół

843
00:35:30,930 --> 00:35:33,270
aż do uzyskania elementem drugim.

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
Więc musieliśmy posiekać go na pół
tyle razy, jak to było możliwe.

846
00:35:38,930 --> 00:35:41,430
To dlatego, że to dlatego, że dziennik n
po prostu zachować dzieląc przez dwa.

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
Tak więc założenia, rzeczy,
trzeba wiedzieć, jeśli kiedykolwiek

849
00:35:45,830 --> 00:35:48,050
zamiar użyć wyszukiwania binarnego.

850
00:35:48,050 --> 00:35:50,680
Twoje elementy muszą być sortowane.

851
00:35:50,680 --> 00:35:53,890
Muszą być klasyfikowane ze względu
to jedyny sposób, w jaki

852
00:35:53,890 --> 00:35:57,060
Można wiedzieć, czy jesteś w stanie
wyrzucić połowę.

853
00:35:57,060 --> 00:36:00,260
>> Jeśli miał to pogmatwany torbę
numerów, a mówisz,

854
00:36:00,260 --> 00:36:05,380
OK, mam zamiar sprawdzić w środku
liczba i liczba Szukam

855
00:36:05,380 --> 00:36:08,510
jest mniejsza niż, że jestem po prostu
arbitralnie wyrzucić połowę.

856
00:36:08,510 --> 00:36:11,130
Nie wiem, czy twój
Liczby w tej drugiej połowie.

857
00:36:11,130 --> 00:36:12,655
Twoja lista ma być sortowana.

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
Jak również może to być
posuwają się naprzód trochę,

860
00:36:16,560 --> 00:36:18,360
ale musisz mieć swobodny dostęp.

861
00:36:18,360 --> 00:36:21,940
Musisz być w stanie po prostu
Do tego środkowego elementu.

862
00:36:21,940 --> 00:36:25,110
Jeśli masz przemierzać
przez coś

863
00:36:25,110 --> 00:36:28,630
czy to ma się dodatkowe kroki
aby dostać się do tego elementu środkowego,

864
00:36:28,630 --> 00:36:31,750
nie jest to już, bo log n
dodajesz więcej pracy w to.

865
00:36:31,750 --> 00:36:34,800
I to będzie trochę
więcej sensu w ciągu dwóch tygodni,

866
00:36:34,800 --> 00:36:37,950
ale po prostu rodzaj chciał poprzedzić,
Ci faceci się zorientować, co jest

867
00:36:37,950 --> 00:36:38,999
przyjść.

868
00:36:38,999 --> 00:36:40,790
Ale to są dwie
ważne założenia

869
00:36:40,790 --> 00:36:44,804
że trzeba do listy binarnym.

870
00:36:44,804 --> 00:36:45,720
Upewnij się, że nie jest to klasyfikowane.

871
00:36:45,720 --> 00:36:47,920
To wielki jeden dla
wy teraz.

872
00:36:47,920 --> 00:36:52,170
I że możemy iść do
Reszta naszych rodzaju.

873
00:36:52,170 --> 00:36:56,444
Tak więc cztery sorts-- Bańka,
wstawiania, wybór i seryjnej.

874
00:36:56,444 --> 00:36:57,485
Oni wszyscy niby chłodny.

875
00:36:57,485 --> 00:37:02,860
Jeśli faceci decydują się CS 124,
dowiesz się o różnego rodzaju rodzaju.

876
00:37:02,860 --> 00:37:07,575
A jeśli jesteś fanem XKCD istnieje
jest naprawdę fajny komiks o

877
00:37:07,575 --> 00:37:11,530
jak bardzo nieskuteczne rodzaju, które
Polecam Ci będzie patrzeć.

878
00:37:11,530 --> 00:37:16,170
Jednym z nich jest jak panika rodzaju, który
to jak, o nie, powrócić losową tablicę.

879
00:37:16,170 --> 00:37:16,991
Zamknij system.

880
00:37:16,991 --> 00:37:17,490
Zostaw.

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
Więc naukowy humor jest zawsze dobra.

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> Więc ma ktoś pamięta rodzaju
jakby tylko ogólny pomysł

885
00:37:25,750 --> 00:37:27,810
jak działa sortowanie bąbelkowe.

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
Pamiętasz?

888
00:37:32,155 --> 00:37:32,755
>> UCZEŃ: Tak.

889
00:37:32,755 --> 00:37:33,970
>> INSTRUKTOR: Idź do niego.

890
00:37:33,970 --> 00:37:38,980
>> STUDENT: Więc idziesz przez i
jeśli jest większa, to zamienić dwa.

891
00:37:38,980 --> 00:37:39,820
>> INSTRUKTOR: Mm-hm.

892
00:37:39,820 --> 00:37:40,564
Dokładnie.

893
00:37:40,564 --> 00:37:41,730
Więc po prostu iterację.

894
00:37:41,730 --> 00:37:43,050
Sprawdź czy dwa numery.

895
00:37:43,050 --> 00:37:46,510
Jeśli jeden jest większy przed
niż później,

896
00:37:46,510 --> 00:37:50,230
po prostu zamienić je tak, aby w
W ten sposób wszystkie wyższych liczbach

897
00:37:50,230 --> 00:37:54,990
propagacji w kierunku końca listy
i wszystkie niższe numery bańka dół.

898
00:37:54,990 --> 00:37:59,355
>> Czy on pokazać wam fajne
dźwięk efekt sortowania wideo?

899
00:37:59,355 --> 00:38:00,480
To trochę chłodu.

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
Tak jak Robert po prostu powiedział, algorytmu
że po prostu przejść przez liście,

902
00:38:05,200 --> 00:38:07,930
zamiana sąsiednich wartości
jeśli nie są w porządku.

903
00:38:07,930 --> 00:38:10,975
A potem po prostu powtarzać
dopóki nie sprawiają żadnych swapów.

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
Tak więc nie jest źle, prawda?

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
Więc po prostu tutaj szybki przykład.

908
00:38:16,319 --> 00:38:18,360
Więc to będzie sortować
je w kolejności rosnącej.

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
Kiedy więc przejść przez pierwszy
razem, patrzymy przez osiem

911
00:38:23,470 --> 00:38:26,880
sześć nie są oczywiście
w porządku, możemy zamienić je.

912
00:38:26,880 --> 00:38:27,985
>> Więc spójrz na następny.

913
00:38:27,985 --> 00:38:29,430
Osiem i cztery nie w porządku.

914
00:38:29,430 --> 00:38:30,450
Zamień je.

915
00:38:30,450 --> 00:38:32,530
A potem osiem i dwa, zamienić je.

916
00:38:32,530 --> 00:38:33,470
Nie idziemy.

917
00:38:33,470 --> 00:38:39,519
Więc po pierwszym przejeździe, można
wiesz, że największa liczba

918
00:38:39,519 --> 00:38:41,810
będzie na drodze
na górze, bo to jest po prostu

919
00:38:41,810 --> 00:38:44,210
będzie stale
większy niż wszystko inne

920
00:38:44,210 --> 00:38:46,810
i to po prostu się do bańki
w górę, aż do tam koniec.

921
00:38:46,810 --> 00:38:48,226
Czy to ma sens dla każdego?

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
Fajne.

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> Tak więc patrzymy na naszego drugiego przebiegu.

926
00:38:53,920 --> 00:38:54,980
Sześć i cztery, przełącznik.

927
00:38:54,980 --> 00:38:55,920
Sześć, a dwa, przełącznik.

928
00:38:55,920 --> 00:38:58,700
I teraz mamy kilka rzeczy w porządku.

929
00:38:58,700 --> 00:39:02,240
Więc na każdym przejściu, że
aby przez cały naszej liście,

930
00:39:02,240 --> 00:39:06,320
wiemy, że podobnie jak wielu numerów
Na koniec zostaną posortowane.

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
Więc robimy trzecią przepustkę,
który jest jednym wymiany.

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
A następnie na nasz czwarty
przekazać, mamy zerowe szczelin.

935
00:39:15,910 --> 00:39:18,570
I tak wiemy, że nasze
Tablica została posortowana.

936
00:39:18,570 --> 00:39:20,900
>> I to jest wielki
sprawa z bańki rodzaju.

937
00:39:20,900 --> 00:39:23,720
Wiemy, że kiedy
mieć zero swapy, że

938
00:39:23,720 --> 00:39:26,497
oznacza, że ​​wszystko,
Jest całkowicie kolejności.

939
00:39:26,497 --> 00:39:27,580
To trochę jak sprawdzić.

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
Więc my też będziemy kodować bańki
rodzaju, które także nie jest tak źle.

942
00:39:36,480 --> 00:39:38,120
Żaden z nich nie jest tak źle.

943
00:39:38,120 --> 00:39:40,210
Wiem, że mogą one wydawać się trochę przerażające.

944
00:39:40,210 --> 00:39:42,124
Wiem, że kiedy wziąłem
klasa, nawet gdy

945
00:39:42,124 --> 00:39:44,290
uczył klasę dla
po raz pierwszy w ubiegłym roku,

946
00:39:44,290 --> 00:39:46,165
Byłem jak, jak mogę to zrobić?

947
00:39:46,165 --> 00:39:48,540
To ma sens w teorii, ale
w jaki sposób rzeczywiście to zrobić?

948
00:39:48,540 --> 00:39:51,420
I dlatego ja też chcę chodzić
poprzez kod z was tutaj facetów.

949
00:39:51,420 --> 00:39:54,915
Więc mam Pseudokod
dla chłopaki tym razem.

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
Więc po prostu pamiętać o tym, jak
jesteśmy o przejście na drugą.

952
00:39:58,970 --> 00:40:04,210
Więc mamy trochę licznik, który
śledzi naszych swapy,

953
00:40:04,210 --> 00:40:08,370
ponieważ musimy upewnić się,
że mamy do sprawdzenia tego.

954
00:40:08,370 --> 00:40:11,830
A my cały szereg iteracji
tak właśnie zrobił z tego przykładu.

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
Jeśli element jest większa niż przed
Element po których jesteśmy w,

957
00:40:17,325 --> 00:40:20,760
możemy zamienić je i zwiększamy NASZEGO
licznik, bo jak tylko zamienić,

958
00:40:20,760 --> 00:40:23,850
chcemy, aby nasze przeciw wiedzieć.

959
00:40:23,850 --> 00:40:26,247
Jakieś pytania?

960
00:40:26,247 --> 00:40:27,580
Coś wydaje zabawne tutaj.

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
STUDENT: Czy ustawić licznik na zero
za każdym razem przejść przez pętlę?

963
00:40:32,350 --> 00:40:34,339
Nie można poddawać się
z powrotem do zera za każdym razem?

964
00:40:34,339 --> 00:40:35,505
INSTRUKTOR: Niekoniecznie.

965
00:40:35,505 --> 00:40:39,710
Więc co się dzieje, to przechodzimy tutaj.

966
00:40:39,710 --> 00:40:43,830
Więc podczas, pamiętaj, to
wykona raz bez przerwy.

967
00:40:43,830 --> 00:40:46,480
Więc to będzie ustawiony
licznik na zero,

968
00:40:46,480 --> 00:40:48,070
wtedy to będzie iterację.

969
00:40:48,070 --> 00:40:50,590
Jak to, przechodzi przez,
będzie aktualizować licznik.

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
Jak się aktualizuje licznik, kiedy to zrobić,
kiedy to dotarł do końca tablicy,

972
00:40:56,900 --> 00:41:00,830
jeśli nasza lista została posortowana,
Licznik zostały zaktualizowane.

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> Więc to sprawdzanie stanu i
mówi, OK, jest licznik większy od zera.

975
00:41:07,150 --> 00:41:09,290
Jeśli tak, to jeszcze raz.

976
00:41:09,290 --> 00:41:14,340
Chcesz przywrócić, tak aby po
przejść, licznik jest równy zero.

977
00:41:14,340 --> 00:41:18,240
Jeśli przejdziesz przez sortowane
tablica, nic się nie zmieni,

978
00:41:18,240 --> 00:41:21,355
to się nie powiedzie, a ty
powrót posortowana lista.

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
Czy to ma sens?

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
STUDENT: Może w trochę.

983
00:41:26,356 --> 00:41:27,147
INSTRUKTOR: OK.

984
00:41:27,147 --> 00:41:28,980
Jeśli istnieje jakikolwiek inny
Pytanie, które pojawia się.

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
Tak.

987
00:41:30,680 --> 00:41:33,760
>> Student: Co by funkcja
się do ciężkich elementów?

988
00:41:33,760 --> 00:41:36,900
>> INSTRUKTOR: Tak naprawdę możemy napisać
że jeśli mamy zamiar teraz.

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
Fajne.

991
00:41:38,300 --> 00:41:42,155
Więc na tej notatce, Alison będzie
aby przełączyć się z powrotem do urządzenia.

992
00:41:42,155 --> 00:41:43,080
To będzie zabawa.

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
I mamy ładne
sortowanie bąbelkowe, co tutaj.

995
00:41:47,390 --> 00:41:50,800
Więc już nie na rowerze
przez tablicę.

996
00:41:50,800 --> 00:41:53,030
Mamy swapy, że
są równe zero.

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
Dlatego chcemy, aby zamienić w sąsiedztwie
elementy jeśli są w porządku.

999
00:41:58,440 --> 00:42:03,020
Tak więc pierwszą rzeczą, musimy
nie jest iterację naszej tablicy.

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> Więc jak myślisz, moglibyśmy
iterację naszej tablicy?

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
Mamy dla i ja równa 0.

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
Chcemy i być mniej
niż n minus jeden minus k.

1006
00:42:22,454 --> 00:42:23,870
I wyjaśnię, że w drugim.

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
Więc to jest tutaj, gdzie optymalizacja,
pamiętam, jak powiedziałem, po każdym przejściu

1009
00:42:32,830 --> 00:42:36,655
przez my tablicy
wiedzieć, że bez względu na to on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> Więc mamy po jednym przejściu
wiem, że to jest posortowana.

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
Po dwóch przejściach wiemy
że to wszystko jest posortowana.

1014
00:42:50,060 --> 00:42:52,750
Po trzech przejściach mamy
wiem, że jest klasyfikowane.

1015
00:42:52,750 --> 00:42:55,620
Tak więc sposób mam iteracji
tędy tablicy,

1016
00:42:55,620 --> 00:43:01,090
jest to upewniając się tylko iść
przez to, co wiemy, jest nieposortowane.

1017
00:43:01,090 --> 00:43:01,644
OK?

1018
00:43:01,644 --> 00:43:02,810
To tylko optymalizacja.

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
Można go napisać naiwnie tylko
iteracja wszystko

1021
00:43:08,210 --> 00:43:09,970
to po prostu dłużej.

1022
00:43:09,970 --> 00:43:12,470
Z tym czterech pętli to
po prostu ładny optymalizacja

1023
00:43:12,470 --> 00:43:18,460
ponieważ wiemy, że po każdym pełnym
iteracja przez tablicę tutaj,

1024
00:43:18,460 --> 00:43:24,050
jak każdej pełnej pętli tutaj, wiemy,
że jedna z tych pierwiastków

1025
00:43:24,050 --> 00:43:25,760
są sortowane na końcu.

1026
00:43:25,760 --> 00:43:28,294
>> Tak więc nie musisz się martwić o te.

1027
00:43:28,294 --> 00:43:29,710
Czy to ma sens dla każdego?

1028
00:43:29,710 --> 00:43:30,950
To fajny mały trick?

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
A więc w tym przypadku, jeżeli
mamy iteracji,

1031
00:43:37,270 --> 00:43:50,590
wiemy, że chcemy, aby sprawdzić, czy
Tablica n i n plus 1 są w porządku.

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
OK.

1034
00:43:53,559 --> 00:43:54,600
Więc oto pseudokod.

1035
00:43:54,600 --> 00:43:57,540
Chcemy sprawdzić, czy tablica n
i n plus 1 są w porządku.

1036
00:43:57,540 --> 00:43:59,520
Więc co możemy mieć tam?

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
To będzie część warunkowa.

1039
00:44:03,120 --> 00:44:04,220
To będzie, jeśli.

1040
00:44:04,220 --> 00:44:07,066
>> STUDENT: Jeśli tablica n
mniej niż tablicy n plus 1.

1041
00:44:07,066 --> 00:44:07,816
INSTRUKTOR: Mm-hm.

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
Również mniejszą lub większą niż.

1044
00:44:10,699 --> 00:44:11,615
STUDENT: Większy niż.

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
Następnie chcemy, aby zamienić je.

1047
00:44:17,620 --> 00:44:18,570
Dokładnie.

1048
00:44:18,570 --> 00:44:23,570
Teraz przejdziemy do tego, co jest
Mechanizm ich zamiana?

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
Więc poszliśmy przez to krótko,
rodzaj funkcji wymiany w zeszłym tygodniu.

1051
00:44:28,137 --> 00:44:29,595
Czy ktoś pamięta, jak to działa?

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
Tak więc nie można po prostu przypisać je, prawda?

1054
00:44:34,950 --> 00:44:36,640
Ponieważ jeden z nich zgubisz.

1055
00:44:36,640 --> 00:44:41,696
Jeśli powiedział, jest równe B i B
jest równa A, wszystko nagle oboje

1056
00:44:41,696 --> 00:44:43,150
są po prostu równe B.

1057
00:44:43,150 --> 00:44:45,720
>> Więc co mamy zrobić, to my
mają tymczasową zmienną, która jest

1058
00:44:45,720 --> 00:44:49,055
będzie posiadać jeden z naszych chwilę
jesteśmy w trakcie procesu zamiany.

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
Więc to, co mamy, to będziemy mieć jakieś int
temperatura jest równa to-- można go przypisać

1061
00:44:56,464 --> 00:44:59,130
na rzecz tego, który chcesz, po prostu
upewnij się śledzić it--

1062
00:44:59,130 --> 00:45:01,840
więc w tym przypadku, będę
przypisać do tablicy n plus 1.

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
Tak, że będzie posiadać co
wartość jest w tym drugim bloku

1065
00:45:07,674 --> 00:45:08,590
że patrzymy.

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> A potem możemy zrobić, to możemy iść
do przodu i Przypisz ponownie tablica n plus 1,

1068
00:45:13,240 --> 00:45:14,990
ponieważ wiemy, że
mają tę wartość przechowywaną.

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
Jest to również jeden z wielkim
things-- Nie wiem czy ktoś z was

1071
00:45:19,270 --> 00:45:23,780
miał problemy gdzie jeśli przełączyć dwa
linii kodu nagle wszystko się udało.

1072
00:45:23,780 --> 00:45:25,880
Zamówienie jest bardzo ważne w CS.

1073
00:45:25,880 --> 00:45:29,450
Więc upewnij się, że diagram
rzeczy, jeśli to możliwe

1074
00:45:29,450 --> 00:45:31,230
co do tego, co się rzeczywiście dzieje.

1075
00:45:31,230 --> 00:45:34,256
Więc teraz jedziemy do
przypisać tablicy n plus 1,

1076
00:45:34,256 --> 00:45:36,005
ponieważ wiemy, że
mają tę wartość przechowywaną.

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> I możemy przypisać, że do tablicy
n lub w tym przypadku tablicy i.

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
Zbyt wiele zmiennych.

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
OK.

1083
00:45:55,470 --> 00:46:01,500
Więc teraz mamy przypisane tablica I
plus 1 równa co jest w tablicy i.

1084
00:46:01,500 --> 00:46:08,240
A teraz możemy wrócić i
przypisać tablicę I do czego?

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
Każdy, kto?

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> STUDENT: 10.

1089
00:46:14,010 --> 00:46:14,680
>> INSTRUKTOR: 10.

1090
00:46:14,680 --> 00:46:15,180
Dokładnie.

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
I ostatnia rzecz.

1093
00:46:18,640 --> 00:46:21,840
Jeśli nie zamieniłem go teraz,
co musimy zrobić?

1094
00:46:21,840 --> 00:46:23,740
Jaka jest jedna rzecz,
że będzie nam powiedzieć,

1095
00:46:23,740 --> 00:46:27,542
jeśli kiedykolwiek zakończyć ten program?

1096
00:46:27,542 --> 00:46:29,250
Co mówi nam, że my
mają posortowana lista?

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
Jeśli nie będziemy wykonywać żadnych swapów, prawda?

1099
00:46:33,750 --> 00:46:36,900
Jeśli swap jest równa
zera na końcu tego produktu.

1100
00:46:36,900 --> 00:46:42,975
Jeśli więc wykonać swap, jak my
tylko nie tutaj, chcemy zaktualizować swapy.

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
I wiem, że nie było
Pytanie o możesz wcześniej

1103
00:46:47,210 --> 00:46:49,689
używać zero lub jeden, zamiast
true lub false.

1104
00:46:49,689 --> 00:46:50,980
A to co to robi tutaj.

1105
00:46:50,980 --> 00:46:52,750
Więc to mówi, jeśli nie swapy.

1106
00:46:52,750 --> 00:47:01,310
Więc jeśli swap wynosi zero, co is-- zawsze
dostać moje prawdy i moje falses pomieszane.

1107
00:47:01,310 --> 00:47:03,960
Chcemy nam ocenić
true, a tak nie jest.

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
Więc jeśli jest to zera, to jest fałszywe.

1110
00:47:09,630 --> 00:47:12,560
Jeśli go negować
[? walić?] staje się prawdą.

1111
00:47:12,560 --> 00:47:13,975
Tak więc ta linia wykonuje.

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> Prawdy i fałszu i
zer i jedynek dostać szału.

1114
00:47:17,370 --> 00:47:20,690
Wystarczy, jeśli wolno chodzić
przez to będzie to sensu.

1115
00:47:20,690 --> 00:47:23,320
Ale to właśnie ten mały
fragment kodu tutaj robi.

1116
00:47:23,320 --> 00:47:26,490
Więc to sprawdza
zrobiliśmy żadnych swapów.

1117
00:47:26,490 --> 00:47:30,054
Więc jeśli jest to coś poza
zero, to będzie fałszywa

1118
00:47:30,054 --> 00:47:31,970
i wszystko jest
będzie ponowne uruchomienie.

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
Cool?

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> Student: Co przerwa robi?

1123
00:47:36,000 --> 00:47:38,990
>> INSTRUKTOR: Break tylko
łamie cię z pętli.

1124
00:47:38,990 --> 00:47:41,570
Tak więc w tym przypadku byłoby
tak jak zakończyć program

1125
00:47:41,570 --> 00:47:43,828
a ty po prostu
mieć posortowaną listę.

1126
00:47:43,828 --> 00:47:44,536
STUDENT: Niesamowite.

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
INSTRUKTOR: Przepraszam?

1129
00:47:49,010 --> 00:47:52,110
STUDENT: Ponieważ wcześniej mamy
używane napisał jeden nad napisane zera

1130
00:47:52,110 --> 00:47:54,170
przedstawić, że jeśli
który będzie działał czy nie.

1131
00:47:54,170 --> 00:47:54,878
>> INSTRUKTOR: Tak.

1132
00:47:54,878 --> 00:47:56,410
Więc można wrócić zero lub jeden.

1133
00:47:56,410 --> 00:47:58,950
W tym przypadku, ponieważ nie jesteśmy w rzeczywistości
cokolwiek z tej funkcji,

1134
00:47:58,950 --> 00:48:00,150
po prostu chcę to przerwać.

1135
00:48:00,150 --> 00:48:02,680
Tak naprawdę nie dbam o to.

1136
00:48:02,680 --> 00:48:06,960
Hamulec jest również dobre, jeśli
jest używany do rozbijania się

1137
00:48:06,960 --> 00:48:10,710
cztery pętle lub warunków, które
nie chcesz, aby utrzymać wykonywania.

1138
00:48:10,710 --> 00:48:12,110
To po prostu ma cię z nich.

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
Jest trochę rzeczy nuance.

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
Czuję, że nie ma
Wiele skinieniem ręki,

1143
00:48:18,445 --> 00:48:19,740
jak dowiesz się o tym wkrótce.

1144
00:48:19,740 --> 00:48:20,955
>> Ale dowiesz się o tym wkrótce.

1145
00:48:20,955 --> 00:48:21,500
Obiecuję.

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
OK.

1148
00:48:23,170 --> 00:48:24,840
Więc nie każdy się pęcherzyków rodzaju?

1149
00:48:24,840 --> 00:48:25,550
Nie jest tak źle.

1150
00:48:25,550 --> 00:48:31,910
Iterację, używając typu swap rzeczy
Zmienna temperatura, a my wszystko ustawione tam?

1151
00:48:31,910 --> 00:48:32,960
Fajne.

1152
00:48:32,960 --> 00:48:34,080
Niesamowite.

1153
00:48:34,080 --> 00:48:34,807
OK.

1154
00:48:34,807 --> 00:48:35,765
Powrót do programu PowerPoint.

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
Wszelkie pytania w ogóle
o nich do tej pory?

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
Fajne.

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
Mm-hm.

1161
00:48:43,695 --> 00:48:45,279
>> STUDENT: [niesłyszalne] int main zwykle.

1162
00:48:45,279 --> 00:48:46,695
Czy trzeba mieć, że do tego?

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> INSTRUKTOR: Więc po prostu patrząc
tylko na rzeczywistej Sortowanie.

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
Gdybyś miał go w
jak większego programu,

1167
00:48:56,350 --> 00:48:57,891
to masz int main gdzieś.

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
W zależności od miejsca
korzystać z tego algorytmu,

1170
00:49:02,880 --> 00:49:05,860
byłoby określić, co jest
są zwracane przez nią.

1171
00:49:05,860 --> 00:49:09,960
Ale dla naszej sprawy, że jesteśmy ściśle
patrząc na to, jak robi to w rzeczywistości

1172
00:49:09,960 --> 00:49:11,300
iterację tablicy.

1173
00:49:11,300 --> 00:49:12,570
Więc nie martw się o to.

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> Więc rozmawialiśmy o najlepszą sprawę i
najgorszym z możliwych scenariuszy dla wyszukiwania binarnego.

1176
00:49:19,830 --> 00:49:22,470
Więc to jest również ważne, aby zrobić
że dla każdego rodzaju.

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
Więc to, co myślisz, że jest najgorszy
przypadku czas pracy sortowanie bąbelkowe?

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
Wy pamiętacie?

1181
00:49:30,700 --> 00:49:31,784
>> STUDENT: N minus 1.

1182
00:49:31,784 --> 00:49:32,700
INSTRUKTOR: N minus 1.

1183
00:49:32,700 --> 00:49:35,070
Więc to oznacza, że ​​są
n minus 1 porównań.

1184
00:49:35,070 --> 00:49:40,060
Więc jedna rzecz zdaje sobie sprawy,
że w pierwszej iteracji

1185
00:49:40,060 --> 00:49:43,360
przechodzimy, porównamy
te two-- więc to 1.

1186
00:49:43,360 --> 00:49:46,685
Te dwa, trzy, cztery.

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
Więc mamy po jednej iteracji
już cztery porównań.

1189
00:49:55,050 --> 00:49:58,230
Kiedy mówię o czasie pracy i n.

1190
00:49:58,230 --> 00:50:04,680
N oznacza liczbę porównań
jako funkcję jak wiele elementów

1191
00:50:04,680 --> 00:50:05,570
mamy.

1192
00:50:05,570 --> 00:50:06,430
OK?

1193
00:50:06,430 --> 00:50:08,860
>> Więc przechodzimy, mamy cztery.

1194
00:50:08,860 --> 00:50:11,780
Następnym razem, kiedy wiemy, że nie
trzeba dbać o to.

1195
00:50:11,780 --> 00:50:15,140
Porównując te dwa,
te dwa, te dwie,

1196
00:50:15,140 --> 00:50:20,050
a jeśli nie mamy, że optymalizacja
z czterech pętli, które napisałem,

1197
00:50:20,050 --> 00:50:22,750
można byłoby porównanie tu i tak.

1198
00:50:22,750 --> 00:50:26,170
Więc trzeba by
prowadzony przez tablicę

1199
00:50:26,170 --> 00:50:34,380
i dokonać porównań n n
razy, ponieważ za każdym razem,

1200
00:50:34,380 --> 00:50:36,670
prowadzony przez to sortujemy jedno.

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> I za każdym razem uruchomić poprzez
Tablica wykonujemy n porównań.

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
Tak więc nasz czas pracy jest to,
faktycznie n do kwadratu, który

1205
00:50:46,330 --> 00:50:48,400
jest znacznie gorsza w naszym
koniec, ponieważ zalogować

1206
00:50:48,400 --> 00:50:51,965
oznacza, gdybyśmy mieli cztery
miliard elementów, to

1207
00:50:51,965 --> 00:50:55,260
zajmie nam cztery miliardy
kwadratu zamiast 32.

1208
00:50:55,260 --> 00:51:01,240
Więc nie jest to najlepszy czas pracy,
ale dla niektórych rzeczy,

1209
00:51:01,240 --> 00:51:04,610
wiesz, czy jesteś w zasięgu
pewna gama elementów

1210
00:51:04,610 --> 00:51:06,540
sortowanie bąbelkowe może być dobrze używać.

1211
00:51:06,540 --> 00:51:07,530
>> OK.

1212
00:51:07,530 --> 00:51:12,290
Więc teraz to, co jest najlepszym przypadku czas pracy?

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
STUDENT: Zero?

1215
00:51:14,940 --> 00:51:16,420
Lub 1?

1216
00:51:16,420 --> 00:51:18,140
>> INSTRUKTOR: 1 będzie więc
jeden porównanie.

1217
00:51:18,140 --> 00:51:19,114
Prawo.

1218
00:51:19,114 --> 00:51:20,002
>> STUDENT: N minus 1?

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> INSTRUKTOR: Tak, tak.

1221
00:51:22,320 --> 00:51:22,990
Tak n minus 1.

1222
00:51:22,990 --> 00:51:26,510
Gdy masz pojęcie jak n
minus 1, mamy tendencję do po prostu upuść go

1223
00:51:26,510 --> 00:51:31,680
i po prostu powiedzieć, n, bo trzeba
porównać każdy z these-- każdej pary.

1224
00:51:31,680 --> 00:51:36,470
Więc byłoby n minus 1, które
chcemy tylko powiedzieć, jest w przybliżeniu n.

1225
00:51:36,470 --> 00:51:39,280
Kiedy masz do czynienia z wykonywania,
wszystko jest w przybliżeniu.

1226
00:51:39,280 --> 00:51:43,860
Tak długo, jak jest wykładnik
poprawne, jesteś bardzo dobry.

1227
00:51:43,860 --> 00:51:45,700
>> To, jak sobie z tym poradzić.

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
Więc, że najlepszym przypadku jest n, która
oznacza, że ​​lista jest już posortowana,

1230
00:51:51,780 --> 00:51:54,320
i wszystko, co robimy jest prowadzony przez
i sprawdzić, czy to jest klasyfikowane.

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
Fajne.

1233
00:51:56,855 --> 00:51:57,355
Dobrze.

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
Więc, jak widać tutaj, że
Wystarczy jeszcze kilka wykresów.

1236
00:52:01,920 --> 00:52:02,660
Tak n do kwadratu.

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
Zabawa.

1239
00:52:05,120 --> 00:52:09,730
Znacznie gorzej niż n, jak widzimy, i
dużo, dużo gorzej niż log 2n.

1240
00:52:09,730 --> 00:52:12,060
A potem można również uzyskać w dziennikach logów.

1241
00:52:12,060 --> 00:52:18,020
I wziąć 124, można dostać się do
jak gwiazda dziennika, który jest jak szalony.

1242
00:52:18,020 --> 00:52:20,172
Więc jeśli jesteś zainteresowany,
wyszukiwanie gwiazda dziennika.

1243
00:52:20,172 --> 00:52:20,880
Jest to rodzaj zabawy.

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
Mamy więc ten wielki wykres.

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
Zaledwie główek, to
Wykres mieć wspaniały

1248
00:52:28,720 --> 00:52:31,350
do połowy kadencji, ponieważ
długo, aby zadać te rozrzedza.

1249
00:52:31,350 --> 00:52:36,090
Więc tylko główek, masz to na swoim
średniookresowy na ładnym ściągawki

1250
00:52:36,090 --> 00:52:36,616
tam.

1251
00:52:36,616 --> 00:52:37,990
Więc po prostu spojrzał na bubble rodzaju.

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
Najgorszy przypadek, n ​​do kwadratu, najlepszy przypadek, n.

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
I będziemy patrzeć na innych.

1256
00:52:44,950 --> 00:52:47,940
>> I jak widać, tylko
jeden, który naprawdę dobrze

1257
00:52:47,940 --> 00:52:50,910
jest scalanie sortowanie, które dostaniemy do dlaczego.

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
Tak więc mamy zamiar udać się do
następny here-- wybór rodzaju.

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
Czy ktoś pamięta, jak
Wybór rodzaju pracował?

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
Idź do niego.

1264
00:53:05,700 --> 00:53:08,210
>> STUDENT: Zasadniczo przejść
Porządek i utworzyć nową listę.

1265
00:53:08,210 --> 00:53:11,001
I tak jak ty elementy wprowadzenie
w, umieścić je w odpowiednim miejscu

1266
00:53:11,001 --> 00:53:11,750
na nowej liście.

1267
00:53:11,750 --> 00:53:14,040
>> INSTRUKTOR: Tak, że dźwięki
bardziej jak Sortowanie przez wstawianie.

1268
00:53:14,040 --> 00:53:15,040
Ale jesteś naprawdę blisko.

1269
00:53:15,040 --> 00:53:15,915
Są one bardzo podobne.

1270
00:53:15,915 --> 00:53:17,440
Nawet ja się im mieszać się czasami.

1271
00:53:17,440 --> 00:53:18,981
Przed tym dziale ja na to czekać.

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
OK.

1274
00:53:20,630 --> 00:53:24,141
Więc to, co chcesz
to jest wybór rodzaju,

1275
00:53:24,141 --> 00:53:25,890
sposób można myśleć
o nim i sposób

1276
00:53:25,890 --> 00:53:30,140
I upewnij się, że nie starają się
je mieszać, to przechodzi przez

1277
00:53:30,140 --> 00:53:33,280
i wybiera
Najmniejsza liczba i

1278
00:53:33,280 --> 00:53:36,070
stawia, że ​​na początku listy.

1279
00:53:36,070 --> 00:53:37,730
To zamienia go z tym pierwszym miejscu.

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
Oni faktycznie mają być przykładem dla mnie.

1282
00:53:45,370 --> 00:53:46,540
Niesamowite.

1283
00:53:46,540 --> 00:53:50,130
Więc po prostu sposób, aby myśleć o it-- wyboru
sortowania, wybierz najmniejszą wartość.

1284
00:53:50,130 --> 00:53:51,940
I mamy zamiar
prowadzony na przykładzie

1285
00:53:51,940 --> 00:53:55,320
Myślę, że pomoże, bo
Myślę, że efekty wizualne zawsze pomaga.

1286
00:53:55,320 --> 00:53:58,510
Więc zaczynamy z czymś
że jest całkowicie nieposortowane.

1287
00:53:58,510 --> 00:54:00,730
Czerwony będzie nieposortowane,
zielone zostaną posortowane.

1288
00:54:00,730 --> 00:54:02,190
To wszystko ma sens w drugim.

1289
00:54:02,190 --> 00:54:08,950
>> Więc przechodzimy i iteracji
od początku do końca.

1290
00:54:08,950 --> 00:54:12,320
I możemy powiedzieć, OK, 2
nasza najmniejsza liczba.

1291
00:54:12,320 --> 00:54:15,680
Więc mamy zamiar wziąć dwa i będziemy
aby przesunąć go do przodu naszej tablicy

1292
00:54:15,680 --> 00:54:17,734
bo to
Najmniej mamy.

1293
00:54:17,734 --> 00:54:19,150
Więc to, co ten robi się tutaj.

1294
00:54:19,150 --> 00:54:20,820
To po prostu się do wymiany tych dwóch.

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
Więc teraz mamy klasyfikowane
części i nieposortowane część.

1297
00:54:25,450 --> 00:54:27,810
A co jest dobre do zapamiętania
o wybór rodzaju

1298
00:54:27,810 --> 00:54:30,690
to mamy do wyboru tylko
z niesegregowanych części.

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> Posortowane część po prostu zostawić w spokoju.

1301
00:54:34,527 --> 00:54:35,660
Mm-hm?

1302
00:54:35,660 --> 00:54:38,452
>> STUDENT: Jak to wiedzieć, co jest
Najmniejszy bez porównania go

1303
00:54:38,452 --> 00:54:39,868
do wszystkich innych wartości w tablicy.

1304
00:54:39,868 --> 00:54:41,250
INSTRUKTOR: To nie porównać.

1305
00:54:41,250 --> 00:54:42,041
Lubimy pominąć go.

1306
00:54:42,041 --> 00:54:43,850
To tylko ogólny ogólny.

1307
00:54:43,850 --> 00:54:44,831
Tak.

1308
00:54:44,831 --> 00:54:47,205
Kiedy piszemy kod jestem
pewien, że będziesz bardziej zadowolony.

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
Ale ten pierwszy przechowywanie
Element jak najmniejsze.

1311
00:54:53,030 --> 00:54:56,110
Porównać i ty
powiedzieć, OK, to jest mniejsza?

1312
00:54:56,110 --> 00:54:56,660
Tak.

1313
00:54:56,660 --> 00:54:57,460
Trzymaj go.

1314
00:54:57,460 --> 00:54:58,640
Oto jest mniejsza?

1315
00:54:58,640 --> 00:54:59,660
Nie?

1316
00:54:59,660 --> 00:55:02,510
>> To jest twój najmniejszy,
przypisać je do wartości.

1317
00:55:02,510 --> 00:55:06,340
I będziesz o wiele szczęśliwszy
gdy idziemy poprzez kod.

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
Więc przejść, możemy zamienić go, tak to
patrzymy na ten niesegregowanych części.

1320
00:55:13,970 --> 00:55:15,810
Więc mamy zamiar wybrać trzy out.

1321
00:55:15,810 --> 00:55:18,890
Mamy zamiar umieścić go na co
koniec naszej uporządkowanej części.

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
A my po prostu będziemy robić
, że robi to, i robi to.

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
Więc to jest nasz rodzaj Pseudokod tutaj.

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
Będziemy tu kodować go w sekundę.

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
Ale coś się chodzić
poprzez na wysokim poziomie.

1330
00:55:37,270 --> 00:55:40,275
Masz zamiar przejść z
i wynosi od 0 do n minus 2.

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
To kolejna optymalizacja.

1333
00:55:43,530 --> 00:55:45,020
Nie przejmuj się zbytnio o tym.

1334
00:55:45,020 --> 00:55:46,620
Tak jak mówiłeś.

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
Jak Jakub mówił, w jaki sposób
śledzić, co nasze minimum to?

1337
00:55:54,406 --> 00:55:55,030
Skąd wiemy?

1338
00:55:55,030 --> 00:55:57,060
Musimy porównać
wszystko, co w naszej liście.

1339
00:55:57,060 --> 00:55:59,600
>> Tak więc minimalna równa i.

1340
00:55:59,600 --> 00:56:03,870
To tylko, że w tym przypadku
Indeks naszych wartości minimalnej.

1341
00:56:03,870 --> 00:56:07,660
Więc to będzie iterację
i to idzie z j równa i plus 1.

1342
00:56:07,660 --> 00:56:11,420
Tak więc wiemy już, że
to nasz pierwszy element.

1343
00:56:11,420 --> 00:56:13,240
Nie musimy porównać go do siebie.

1344
00:56:13,240 --> 00:56:16,970
Więc zaczynamy porównując ją do następnego
jeden, dlatego, że to ja plus 1 do n

1345
00:56:16,970 --> 00:56:20,110
minus 1, który jest
koniec tam tablicy.

1346
00:56:20,110 --> 00:56:25,090
I powiedział, że jeśli w tablicy
j wynosi mniej niż tablicy minut,

1347
00:56:25,090 --> 00:56:29,200
następnie przypisać gdzie
nasze indeksy jest minimalne.

1348
00:56:29,200 --> 00:56:37,470
>> Min, a jeśli nie jest równa I,
w których byliśmy z powrotem tutaj.

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
Tak jak wtedy, gdy pierwszy raz zrobił tego.

1351
00:56:41,790 --> 00:56:49,310
W tym przypadku, będzie ona uruchamiana
zero, to w końcu jest dwóch.

1352
00:56:49,310 --> 00:56:53,010
Więc nie będzie równa min i w końcu.

1353
00:56:53,010 --> 00:56:55,720
To mówi nam, że
musimy zamienić je.

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
Czuję, że konkretny przykład
przyczyni się znacznie więcej niż to.

1356
00:57:00,470 --> 00:57:04,970
Więc ja ten kod się z wami
teraz i myślę, że będzie lepiej.

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> Rodzaju zazwyczaj działa w ten sposób, że w
często lepiej po prostu je zobaczyć.

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
Więc to, co chcemy zrobić, to
najpierw chcą najmniejsza

1361
00:57:17,280 --> 00:57:19,890
element w pozycji w macierzy.

1362
00:57:19,890 --> 00:57:21,280
Dokładnie to, co Jacob mówi.

1363
00:57:21,280 --> 00:57:23,090
Musisz zapisać, że w jakiś sposób.

1364
00:57:23,090 --> 00:57:25,900
Więc mamy zamiar rozpocząć tutaj
iteracji po tablicy.

1365
00:57:25,900 --> 00:57:28,970
Mamy zamiar powiedzieć, że to nasz
Pierwszy z nich po prostu zacząć.

1366
00:57:28,970 --> 00:57:38,308
Więc będziemy mieć int
Najmniejsza jest równa w tablicy i.

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> Więc jedna rzecz zauważyć, co
Czas to pętla wykonuje,

1369
00:57:45,050 --> 00:57:48,550
zaczynamy o krok dalej.

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
Kiedy zaczynamy patrzymy na to.

1372
00:57:57,440 --> 00:58:00,840
Następnym razem iteracji,
zaczynamy w tym jeden

1373
00:58:00,840 --> 00:58:02,680
i przypisanie to nasza najmniejsza wartość.

1374
00:58:02,680 --> 00:58:10,450
Więc to jest bardzo podobny do typu bubble
gdzie wiemy, że po jednym przejściu,

1375
00:58:10,450 --> 00:58:11,700
Ten ostatni element jest posortowana.

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
Z wyboru rodzaju,
to jest po prostu przeciwieństwem.

1378
00:58:15,120 --> 00:58:18,950
>> Na każdym przejściu, wiemy, że
Pierwszy jest posortowana.

1379
00:58:18,950 --> 00:58:21,360
Po drugim przebiegu,
Drugi zostaną posortowane.

1380
00:58:21,360 --> 00:58:26,470
A jak zobaczyłem z przykładami slajdów,
tylko część naszej klasyfikowane rośnie.

1381
00:58:26,470 --> 00:58:34,020
Więc ustawiając nasz najmniejszy
do tablic i wszystko to robi

1382
00:58:34,020 --> 00:58:37,340
co jest zwężenie
patrzymy na tak

1383
00:58:37,340 --> 00:58:40,164
zminimalizowanie liczby
porównań robimy.

1384
00:58:40,164 --> 00:58:41,770
Czy to ma sens dla każdego?

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
Czy mnie trzeba uruchomić przez to
raz wolniej lub innymi słowami?

1387
00:58:46,380 --> 00:58:47,180
Jestem szczęśliwy.

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
OK.

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> Więc jesteśmy przechowywania
wartość w tym momencie,

1392
00:58:55,540 --> 00:58:57,840
ale chcemy również do przechowywania indeksu.

1393
00:58:57,840 --> 00:59:01,010
Więc idziemy do przechowywania
Stanowisko najmniejsza

1394
00:59:01,010 --> 00:59:02,770
jeden, który jest po prostu będzie i.

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
Więc teraz Jakub jest zadowolony.

1397
00:59:05,440 --> 00:59:06,870
Mamy wszystko zapisane.

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
A teraz musimy patrzeć przez
nieposortowane część tablicy.

1400
00:59:11,870 --> 00:59:18,170
Tak więc w tym przypadku
będzie naszym nieposortowane.

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
To jest: i.

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
OK.

1405
00:59:26,210 --> 00:59:30,040
>> Więc to, co mamy zamiar zrobić
będzie dla pętli.

1406
00:59:30,040 --> 00:59:32,066
Gdy trzeba
iterację tablicy,

1407
00:59:32,066 --> 00:59:33,440
Twój umysł może pójść do do pętli.

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
Więc przez jakiś int k
equals-- co myślimy

1410
00:59:38,090 --> 00:59:39,700
k będzie wynosić na początek?

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
To jest to, co możemy ustawić jak nasza najmniejsza
wartość i chcemy go porównać.

1413
00:59:44,766 --> 00:59:47,090
Co chcemy, aby porównać go do?

1414
00:59:47,090 --> 00:59:48,730
To będzie ten następny, prawda?

1415
00:59:48,730 --> 00:59:53,200
Dlatego chcemy, aby być inicjowane k
do i plus 1, aby rozpocząć.

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> I chcemy k w tym przypadku
już rozmiar przechowywane tutaj,

1418
01:00:02,800 --> 01:00:03,930
więc możemy po prostu użyć rozmiaru.

1419
01:00:03,930 --> 01:00:06,240
Wielkość jest rozmiar tablicy.

1420
01:00:06,240 --> 01:00:09,620
A my po prostu chcemy
aktualną k jeden za każdym razem.

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
Fajne.

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
Więc teraz musimy znaleźć
najmniejszy element tutaj.

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
Jeśli więc iterację, mamy
chcesz powiedzieć, jeśli tablica na k

1427
01:00:31,380 --> 01:00:37,080
jest mniejsza niż naszego najmniejszego value--
to gdzie my właściwie

1428
01:00:37,080 --> 01:00:42,950
śledzenie co
Najmniejszy here--

1429
01:00:42,950 --> 01:00:47,740
następnie chcemy przypisać
co nasza najmniejsza wartość.

1430
01:00:47,740 --> 01:00:50,645
>> Oznacza to, że, och, my jesteśmy
iteracja tutaj.

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
Cokolwiek tu jest wartość
nie nasza najmniejsza rzecz.

1433
01:00:53,740 --> 01:00:54,448
Nie chcemy go.

1434
01:00:54,448 --> 01:00:56,100
Chcemy to zmienić.

1435
01:00:56,100 --> 01:01:02,050
Więc jeśli mamy przesunięcia go, co robić
myślisz, że może być w tym kodzie tutaj?

1436
01:01:02,050 --> 01:01:04,160
Chcemy, aby przypisać
Najmniejszy i pozycja.

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
Tak więc to, co jest teraz najmniejszy?

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
STUDENT: Array k.

1441
01:01:09,130 --> 01:01:09,963
INSTRUKTOR: Array k.

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
I to, co jest teraz pozycja?

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
Co indeksy
nasza najmniejsza wartość?

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
To jest po prostu k.

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
Więc tablicy k, k, to zgadzają.

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
Więc chcemy przypisać, że.

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
A potem okazało się nasz najmniejszy,
tak na końcu tego dla pętli

1454
01:01:39,950 --> 01:01:45,100
tutaj znaleźliśmy, co nasza najmniejsza
wartość, więc po prostu zamienić.

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
W tym przypadku, jak mówią nasi
Najmniejsza wartość jest tutaj.

1457
01:01:50,816 --> 01:01:51,940
To jest nasza najmniejsza wartość.

1458
01:01:51,940 --> 01:01:57,690
>> Chcemy tylko, aby go wymienić tutaj, co jest
co to funkcję zamiany na dnie

1459
01:01:57,690 --> 01:02:01,270
zrobił, co właśnie napisałem
razem kilka minut temu.

1460
01:02:01,270 --> 01:02:02,775
Tak powinno to wyglądać znajomo.

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
A potem będzie tylko iteracji
aż do osiągnięcia przez całą drogę

1463
01:02:08,030 --> 01:02:13,100
do końca, co oznacza, że
mieć zero elementów, które są nieposortowane

1464
01:02:13,100 --> 01:02:14,800
i wszystko inne jest klasyfikowane.

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
Ma sens?

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
Trochę bardziej konkretnie?

1469
01:02:19,280 --> 01:02:19,990
Pomocy kodu?

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> STUDENT: Dla wielkości, nigdy nie
naprawdę zdefiniować lub zmienić,

1472
01:02:26,410 --> 01:02:27,340
jak to wiedzieć?

1473
01:02:27,340 --> 01:02:32,380
>> INSTRUKTOR: Więc jedna rzecz
zauważyć tutaj jest int rozmiar.

1474
01:02:32,380 --> 01:02:35,680
Więc mówimy w tym sort-- rodzaju
Funkcja ta jest w tym case-- to

1475
01:02:35,680 --> 01:02:40,770
Wybór rodzaju, to minęło
się z tej funkcji.

1476
01:02:40,770 --> 01:02:43,460
Tak więc, jeżeli nie zostało przekazane
się, że można zrobić coś

1477
01:02:43,460 --> 01:02:47,840
jak z długością tablicy
lub chcesz iterację

1478
01:02:47,840 --> 01:02:49,390
znaleźć długości.

1479
01:02:49,390 --> 01:02:52,680
Ale ponieważ jest przekazywana
w, możemy po prostu użyj go.

1480
01:02:52,680 --> 01:02:55,720
Po prostu zakładamy, że użytkownik
dał wam poprawny rozmiar, który

1481
01:02:55,720 --> 01:02:57,698
faktycznie reprezentuje
rozmiar macierzy.

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
Cool?

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> Jeśli macie jakieś problemy z nich
lub chcesz więcej praktyki kodowania rodzaju

1486
01:03:05,870 --> 01:03:08,050
na własną rękę, należy
Do study.cs50.

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
To narzędzie.

1489
01:03:12,670 --> 01:03:15,040
Mają sprawdzania, że
rzeczywiście można napisać.

1490
01:03:15,040 --> 01:03:16,180
Robią Pseudokod.

1491
01:03:16,180 --> 01:03:19,310
Mają więcej filmów i slajdów
w tym tych, które używam tutaj.

1492
01:03:19,310 --> 01:03:23,150
Więc jeśli nadal czujesz
trochę rozmyte, spróbuj się.

1493
01:03:23,150 --> 01:03:25,670
Jak zawsze, chodź ze mną rozmawiać, też.

1494
01:03:25,670 --> 01:03:26,320
Pytanie?

1495
01:03:26,320 --> 01:03:28,611
>> Uczeń: Czy mówisz,
rozmiar jest zdefiniowane wcześniej?

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
INSTRUKTOR: Tak.

1498
01:03:29,900 --> 01:03:35,570
Rozmiar jest zdefiniowane wcześniej w górę
tutaj w deklaracji funkcji.

1499
01:03:35,570 --> 01:03:39,060
Więc założyć, że to było przekazywane w
przez użytkownika oraz dla uproszczenia,

1500
01:03:39,060 --> 01:03:41,896
będziemy zakładać, że
użytkownik dał nam odpowiedni rozmiar.

1501
01:03:41,896 --> 01:03:43,240
Fajne.

1502
01:03:43,240 --> 01:03:44,390
Więc to jest wybór rodzaju.

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
Chłopaki, wiem, że uczysz dużo dzisiaj.

1505
01:03:47,640 --> 01:03:49,710
To gęste dane dla sekcji.

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
Więc z tym, będziemy
aby przejść do wstawiania rodzaju.

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> OK.

1510
01:04:02,510 --> 01:04:06,100
Więc wcześniej musimy zrobić
nasza analiza tutaj czas pracy.

1511
01:04:06,100 --> 01:04:10,190
Tak więc w najlepszym przypadku,
przyznawana od pokazałem

1512
01:04:10,190 --> 01:04:11,960
Stół już mam
rodzaj dał ją.

1513
01:04:11,960 --> 01:04:15,430
Ale najlepszym przypadku czas pracy, co myślimy?

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
Wszystko sortowane.

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
N kwadratu.

1518
01:04:22,070 --> 01:04:24,780
Ktoś ma wyjaśnienie
dlaczego uważasz, że?

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> STUDENT: Jesteś porównując through--

1521
01:04:30,519 --> 01:04:31,268
INSTRUKTOR: Zgadza się.

1522
01:04:31,268 --> 01:04:32,540
Masz porównanie przez.

1523
01:04:32,540 --> 01:04:35,630
W każdej iteracji, chociaż
jesteśmy zmniejszanie tego jednego,

1524
01:04:35,630 --> 01:04:38,950
nadal jesteś przeszukiwania
wszystko, aby znaleźć najmniejszy.

1525
01:04:38,950 --> 01:04:42,390
Więc nawet, jeśli najmniejszą wartość
Jest tu na początku

1526
01:04:42,390 --> 01:04:44,710
nadal jesteś porównując ją
przeciwko wszystkim innym

1527
01:04:44,710 --> 01:04:46,550
aby upewnić się, że najmniejsza rzecz.

1528
01:04:46,550 --> 01:04:49,820
Więc w końcu uruchomiony przez
około n do kwadratu razy.

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
Dobrze.

1531
01:04:51,590 --> 01:04:52,785
A co w najgorszym przypadku?

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
Również n do kwadratu, ponieważ masz zamiar
robić tę samą procedurę.

1534
01:04:57,980 --> 01:05:01,670
Więc w tym przypadku, wybór
jakby coś

1535
01:05:01,670 --> 01:05:04,010
że również zadzwonić oczekiwany czas pracy.

1536
01:05:04,010 --> 01:05:07,400
Tak w innych, po prostu wiem,
górne i dolne granice.

1537
01:05:07,400 --> 01:05:11,180
W zależności od tego jak szalony nasz
Lista jest i jak nieposortowane jest,

1538
01:05:11,180 --> 01:05:15,350
różnią się one między n lub n kwadratu.

1539
01:05:15,350 --> 01:05:16,550
Nie wiemy.

1540
01:05:16,550 --> 01:05:22,820
>> Ale ponieważ wybór rodzaju ma to samo
najgorszy i najlepszy przypadek, który mówi nam, że

1541
01:05:22,820 --> 01:05:25,880
bez względu na to, jaki typ wejścia mamy
mają, czy to całkowicie

1542
01:05:25,880 --> 01:05:29,130
sortowane lub całkowicie
odwrócić klasyfikowane, to

1543
01:05:29,130 --> 01:05:30,740
będzie mieć taką samą ilość czasu.

1544
01:05:30,740 --> 01:05:33,760
Więc w tym przypadku, jeśli
pamiętam z naszej tabeli,

1545
01:05:33,760 --> 01:05:38,610
faktycznie miał wartość
te dwa gatunki nie mają,

1546
01:05:38,610 --> 01:05:40,390
co jest z oczekiwaniami środowiska wykonawczego.

1547
01:05:40,390 --> 01:05:43,350
Wiemy, że gdy
prowadzimy wyboru rodzaju,

1548
01:05:43,350 --> 01:05:45,380
to na pewno
uruchomić n do kwadratu czasu.

1549
01:05:45,380 --> 01:05:46,630
Tam nie ma zmienność.

1550
01:05:46,630 --> 01:05:47,630
To jest po prostu oczekuje.

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
I znowu, jeśli chcesz dowiedzieć się
więcej, wziąć CS 124 na wiosnę.

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
Dobrze.

1555
01:05:56,712 --> 01:05:57,545
Widzieliśmy ten jeden.

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
Fajne.

1558
01:05:59,030 --> 01:06:00,930
Więc Sortowanie przez wstawianie.

1559
01:06:00,930 --> 01:06:03,330
A ja prawdopodobnie będzie
zaciosać przez to.

1560
01:06:03,330 --> 01:06:05,440
Nie masz chłopaki kodować go.

1561
01:06:05,440 --> 01:06:06,580
Będziemy po prostu przejść przez to.

1562
01:06:06,580 --> 01:06:10,500
Więc Sortowanie przez wstawianie jest rodzajem
z podobna do wyboru rodzaju

1563
01:06:10,500 --> 01:06:14,460
się, że mamy zarówno nieposortowane
i sortowane część tablicy.

1564
01:06:14,460 --> 01:06:20,260
>> Ale co innego jest to, że
jak przejść przez jeden po drugim,

1565
01:06:20,260 --> 01:06:24,210
po prostu wziąć cokolwiek numer
jest następny w naszym nieposortowane,

1566
01:06:24,210 --> 01:06:28,507
sortować je i poprawnie
do naszego posortowanej tablicy.

1567
01:06:28,507 --> 01:06:30,090
To będzie bardziej sensowne przykładzie.

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
Tak więc wszystko zaczyna jako nieposortowane,
Podobnie jak w przypadku wyboru rodzaju.

1570
01:06:35,430 --> 01:06:38,740
I mamy zamiar to rozwiązać w
porządku rosnącym, jak byliśmy.

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
Tak więc na naszym pierwszym przejściu
bierzemy pierwszą wartość

1573
01:06:43,340 --> 01:06:46,700
i powiedzieć, OK, jesteś
Teraz na liście przez siebie.

1574
01:06:46,700 --> 01:06:49,150
>> Ponieważ jesteś na liście
przez siebie, są klasyfikowane.

1575
01:06:49,150 --> 01:06:52,460
Gratulacje dla bycia
Pierwszy element w tej tablicy.

1576
01:06:52,460 --> 01:06:54,800
Jesteś już sortowane wszystko na własną rękę.

1577
01:06:54,800 --> 01:06:58,900
Więc teraz mamy klasyfikowane
i nieposortowane tablica.

1578
01:06:58,900 --> 01:07:01,760
Teraz bierzemy pierwszy.

1579
01:07:01,760 --> 01:07:05,600
Co się dzieje między tutaj
i tutaj jest to, że możemy powiedzieć,

1580
01:07:05,600 --> 01:07:08,890
OK, mamy zamiar spojrzeć na
Pierwsza wartość naszego niesegregowanych tablicy

1581
01:07:08,890 --> 01:07:13,270
i mamy zamiar wprowadzić go w jego
właściwe miejsce w posortowanej tablicy.

1582
01:07:13,270 --> 01:07:21,460
>> Więc co robimy jest bierzemy 5 i
powiedzieć, OK, 5 jest większa niż 3,

1583
01:07:21,460 --> 01:07:24,630
więc po prostu włóż go w prawo
na prawo od tego.

1584
01:07:24,630 --> 01:07:25,130
Jesteśmy dobrzy.

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
Więc idziemy do naszego następnego.

1587
01:07:28,420 --> 01:07:29,720
I bierzemy dwa.

1588
01:07:29,720 --> 01:07:34,330
Możemy powiedzieć, OK, 2 jest mniej
niż 3, więc wiemy, że to

1589
01:07:34,330 --> 01:07:36,220
musi być
Przód naszej liście teraz.

1590
01:07:36,220 --> 01:07:41,800
Więc co możemy zrobić, to możemy wcisnąć 3 i 5 w dół
i ruszamy 2 do tego pierwszego gniazda.

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
Więc po prostu wkładając ją do
prawidłowe miejsce powinno być.

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> Następnie patrzymy na nasze
następny, i mówimy 6.

1595
01:07:49,470 --> 01:07:53,620
OK 6 jest większa niż
wszystko, co w naszej posortowanej tablicy,

1596
01:07:53,620 --> 01:07:56,000
więc po prostu oznaczyć go do końca.

1597
01:07:56,000 --> 01:07:56,960
A potem spojrzeć na cztery.

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
4 jest mniejsza niż 6, to jest mniej
niż 5, ale jest większy niż 3.

1600
01:08:03,020 --> 01:08:06,270
Więc po prostu włożyć ją w prawo w
środkowy między 3 i 5.

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
Tak więc, aby to trochę
nieco bardziej konkretne,

1603
01:08:10,530 --> 01:08:12,280
tutaj jest trochę
pomysł, co się stało.

1604
01:08:12,280 --> 01:08:16,430
Więc dla każdego elementu niesegregowanych, mamy
określić, gdzie w części posortowanej

1605
01:08:16,430 --> 01:08:17,090
to jest.

1606
01:08:17,090 --> 01:08:20,680
>> Tak więc mając na uwadze
sortowane i niesortowane,

1607
01:08:20,680 --> 01:08:26,080
musimy przechodzić przez i rysunek
tam, gdzie to pasuje w posortowanej tablicy.

1608
01:08:26,080 --> 01:08:31,460
I wstawiamy go przez przesunięcie
elementy, na prawo od niej w dół.

1609
01:08:31,460 --> 01:08:34,910
A potem po prostu zachować
iteracja Dopóki

1610
01:08:34,910 --> 01:08:39,270
mają zupełnie posortowana lista
gdzie jest teraz zerową niesortowana

1611
01:08:39,270 --> 01:08:41,720
i zajmuje sortowych
Całość naszej liście.

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
Więc jeszcze raz, żeby było
bardziej konkretne, mamy Pseudokod.

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> I tak jest w zasadzie dla
równą 0 do n minus 1

1616
01:08:52,410 --> 01:08:54,790
to tylko długość naszej tablicy.

1617
01:08:54,790 --> 01:09:00,979
Mamy pewną element, który jest równy
Pierwsza tablica lub pierwsze indeksy.

1618
01:09:00,979 --> 01:09:03,200
Stawiamy j równą.

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
Tak więc, j jest większa niż
zero i tablica, j minus 1

1621
01:09:09,210 --> 01:09:11,660
jest większa niż
elementem, więc wszystko, co robi

1622
01:09:11,660 --> 01:09:17,479
upewniając się, że jest
Twój j naprawdę reprezentuje

1623
01:09:17,479 --> 01:09:20,010
nieposortowane część tablicy.

1624
01:09:20,010 --> 01:09:30,745
>> Więc póki nie jest jeszcze rzeczy
sortowanie i jeden minus is-- co j

1625
01:09:30,745 --> 01:09:31,840
jest elementem jej?

1626
01:09:31,840 --> 01:09:34,760
J nie został zdefiniowany tutaj.

1627
01:09:34,760 --> 01:09:35,677
To trochę denerwujące.

1628
01:09:35,677 --> 01:09:36,176
OK.

1629
01:09:36,176 --> 01:09:36,689
Tak czy inaczej.

1630
01:09:36,689 --> 01:09:39,899
Więc j minus 1, jesteś sprawdzanie
element przed nim.

1631
01:09:39,899 --> 01:09:46,460
Mówisz, OK, jest elementem
zanim gdziekolwiek am-- I niech

1632
01:09:46,460 --> 01:09:47,540
rzeczywiście zwrócić na to uwagę.

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
Więc powiedzmy, że jest to
jak w naszym drugim przejściu.

1635
01:09:56,830 --> 01:09:59,525
Tak i będzie równa
1, która jest tutaj.

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> I tak będzie równy 1.

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
To byłoby 2, 4, 5, 6, 7.

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
Dobrze.

1642
01:10:16,750 --> 01:10:20,945
Więc nasza elementem w tym przypadku
będzie równa cztery.

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
I mamy trochę j, który jest
będzie równe 1.

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
Och, j jest zmniejszanie.

1647
01:10:30,971 --> 01:10:31,720
To co to jest.

1648
01:10:31,720 --> 01:10:35,680
Więc j jest równa i, więc co to jest
powiedzenie, że jak iść naprzód,

1649
01:10:35,680 --> 01:10:37,530
jesteśmy po prostu upewniając
że nie jesteśmy na

1650
01:10:37,530 --> 01:10:43,520
indeksowanie w ten sposób, gdy próbujemy
włożyć rzeczy do naszego posortowanej listy.

1651
01:10:43,520 --> 01:10:49,850
>> Tak więc, gdy j wynosi 1, i w tym przypadku
Tablica j minus jedno- tak tablica j minus jeden

1652
01:10:49,850 --> 01:10:54,610
jest 2 w tym case-- jeśli to
większy niż element

1653
01:10:54,610 --> 01:10:57,700
potem to wszystko robi
przenosi rzeczy w dół.

1654
01:10:57,700 --> 01:11:04,790
Więc w tym przypadku, jedna tablica j minus
będzie tablica zero, czyli 2.

1655
01:11:04,790 --> 01:11:08,430
2 nie jest większa niż 4,
więc to nie wykonuje.

1656
01:11:08,430 --> 01:11:11,460
Tak więc zmiana nie rusza się.

1657
01:11:11,460 --> 01:11:18,790
Co to robi jest tu po prostu
przesuwając posortowaną tablicę w dół.

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
W tym przypadku, w rzeczywistości, to
może do-- zróbmy to 3.

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
Więc jeśli mamy przejść przez z
ten przykład, że jesteśmy teraz tutaj.

1662
01:11:31,970 --> 01:11:32,740
To jest posortowana.

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
To nieposortowane.

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
Cool?

1667
01:11:39,860 --> 01:11:46,620
I tak jest równe 2, tak
Nasz elementem jest równa 3.

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
I naszym j wynosi 2.

1670
01:11:52,270 --> 01:12:00,620
Tak więc i my patrzeć przez
powiedzieć, OK, to jedna tablica j minus

1671
01:12:00,620 --> 01:12:03,470
większy niż element
że patrzymy?

1672
01:12:03,470 --> 01:12:05,540
A odpowiedź brzmi: tak, prawda?

1673
01:12:05,540 --> 01:12:11,275
4 jest większa niż 3 i j
wynosi 2, więc ten kod jest wykonywany.

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> Więc co teraz robimy tablicę na
2, tak, właśnie tutaj, możemy zamienić je.

1676
01:12:18,550 --> 01:12:25,620
Więc po prostu powiedzieć, OK, tablica
Obecnie w dwóch będzie trzech.

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
I j będzie wynosić
j minus 1, czyli 1.

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
To straszne, ale
wy pomysł.

1681
01:12:37,200 --> 01:12:38,360
J jest teraz równa jeden.

1682
01:12:38,360 --> 01:12:44,360
I tablica j jest tylko będzie
równej naszej elementu, która wynosiła 4.

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
I usunięte coś nie powinienem
mają lub miswrote coś,

1685
01:12:48,570 --> 01:12:49,910
ale chłopaki pomysł.

1686
01:12:49,910 --> 01:12:50,640
>> To przenieść na n.

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
A potem, jeśli były, to by pętla
ponownie i to powiedzieć, OK, j wynosi 1 teraz.

1689
01:12:57,960 --> 01:13:00,665
I tablica j minus 1 jest teraz 2.

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
Czy 2 mniej niż naszym elementu?

1692
01:13:03,760 --> 01:13:04,540
Nie?

1693
01:13:04,540 --> 01:13:07,970
To oznacza, że ​​mamy
ten element włożony

1694
01:13:07,970 --> 01:13:10,110
w odpowiednim miejscu w naszym sortowanej tablicy.

1695
01:13:10,110 --> 01:13:14,400
Wtedy możemy wziąć to i powiedzieć,
OK, nasz posortowana tablica jest tutaj.

1696
01:13:14,400 --> 01:13:19,940
I zajęłoby to numer 6 i być
jak, dobrze, jest 6 mniej niż ten numer?

1697
01:13:19,940 --> 01:13:20,480
Nie?

1698
01:13:20,480 --> 01:13:21,080
Fajne.

1699
01:13:21,080 --> 01:13:22,680
Jesteśmy dobrze.

1700
01:13:22,680 --> 01:13:23,530
>> Zrób to jeszcze raz.

1701
01:13:23,530 --> 01:13:24,740
Mówimy 7.

1702
01:13:24,740 --> 01:13:29,010
7 jest mniejsza niż pod koniec
naszego posortowanej tablicy?

1703
01:13:29,010 --> 01:13:29,520
Nie.

1704
01:13:29,520 --> 01:13:30,430
Więc jesteśmy w porządku.

1705
01:13:30,430 --> 01:13:32,760
Więc to będzie klasyfikowane.

1706
01:13:32,760 --> 01:13:38,610
W zasadzie to wszystko działa
jest to mówiąc zabiorą

1707
01:13:38,610 --> 01:13:42,060
Pierwszy element
Twój nieposortowane tablica,

1708
01:13:42,060 --> 01:13:46,010
dowiedzieć się, gdzie to idzie
w posortowanej tablicy.

1709
01:13:46,010 --> 01:13:48,780
I to właśnie dba
swapów, aby to zrobić.

1710
01:13:48,780 --> 01:13:51,300
Jesteś w zasadzie tylko zamiana
dopóki nie jest w odpowiednim miejscu.

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
Wizualny obraz jest, że jesteś
porusza wszystko przez to robić.

1713
01:13:56,990 --> 01:13:59,420
>> Tak to jest jak pół bańki sort-owskiej.

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
Zapoznaj się badania 50.

1716
01:14:03,420 --> 01:14:06,000
Gorąco polecam spróbować
kodować to na własną rękę.

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
Jeśli masz jakiekolwiek problemy lub chcesz
zobacz przykładowy kod dla typu wstawiania

1719
01:14:12,450 --> 01:14:13,750
proszę dać mi znać.

1720
01:14:13,750 --> 01:14:14,500
Jestem zawsze w pobliżu.

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
Więc w najgorszym przypadku czas pracy
i najlepszym przypadku środowiska wykonawczego.

1723
01:14:20,200 --> 01:14:30,700
Jak facet widział od stołu już
pokazałem, to zarówno n do kwadratu i n.

1724
01:14:30,700 --> 01:14:35,590
>> Więc niby schodzili z tego, co mówił
o naszych poprzednich rodzaju, najgorsze

1725
01:14:35,590 --> 01:14:38,760
Sprawa jest, że jeśli czas pracy
to całkowicie nieposortowane,

1726
01:14:38,760 --> 01:14:42,530
mamy do porównania wszystkich tych n razy.

1727
01:14:42,530 --> 01:14:47,020
Mamy mnóstwo porównań robić
bo jeśli jest to w odwrotnej kolejności,

1728
01:14:47,020 --> 01:14:50,360
mamy zamiar powiedzieć, OK, to
jest taki sam, to jest dobre

1729
01:14:50,360 --> 01:14:54,650
i ten będzie musiał być porównywane
przed pierwszym mają być przeniesione z powrotem.

1730
01:14:54,650 --> 01:14:56,710
A ponieważ mamy ku
koniec ogona, mamy

1731
01:14:56,710 --> 01:14:59,440
porównanie, porównaj,
porównać przeciwko wszystkiemu.

1732
01:14:59,440 --> 01:15:03,030
>> Tak więc kończy się na tym, że
około n do kwadratu.

1733
01:15:03,030 --> 01:15:09,510
Jeśli jest poprawne wtedy
powiedzieć, OK, 2, jesteś dobry.

1734
01:15:09,510 --> 01:15:11,330
3, jesteś w porównaniu do dwóch.

1735
01:15:11,330 --> 01:15:12,310
Jesteś dobry.

1736
01:15:12,310 --> 01:15:14,150
4, po prostu porównać do ogona.

1737
01:15:14,150 --> 01:15:14,990
Jesteś dobry.

1738
01:15:14,990 --> 01:15:17,140
6, w porównaniu do ogona, jesteś w porządku.

1739
01:15:17,140 --> 01:15:20,870
Więc dla każdego miejsca, czy to już
sortowane, robisz jedno porównanie.

1740
01:15:20,870 --> 01:15:22,320
Więc to jest po prostu brak.

1741
01:15:22,320 --> 01:15:26,840
A ponieważ mamy najlepszym przypadku czas pracy
n i najgorszym starcie n

1742
01:15:26,840 --> 01:15:28,680
kwadratu, nie mamy spodziewany czas pracy.

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> To po prostu zależy od
Chaos naszej liście tam.

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
I znowu, inny
wykres i inny stolik.

1747
01:15:39,530 --> 01:15:41,170
Więc różnic pomiędzy rodzajami.

1748
01:15:41,170 --> 01:15:44,180
Jestem po prostu będzie wiatr przez, ja
poczuć się jak rozmawialiśmy szeroko

1749
01:15:44,180 --> 01:15:46,570
o tym, jak wszelkiego rodzaju
od zmieniać i łączyć.

1750
01:15:46,570 --> 01:15:50,564
Więc Sortowanie przez scalanie jest ostatni
Będę nosił was z.

1751
01:15:50,564 --> 01:15:52,105
Mamy dość barwny obraz.

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
Więc połączyć algorytm sortowania jest rekurencyjny.

1754
01:15:56,040 --> 01:15:59,910
Więc nie wiem, co wy
rekurencyjna funkcja?

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> Każdy, kto chce powiedzieć?

1757
01:16:03,320 --> 01:16:04,739
Chcesz spróbować?

1758
01:16:04,739 --> 01:16:07,280
Tak jest po prostu funkcja rekurencyjna
funkcja, która nazywa siebie.

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
Więc jeśli jesteście zaznajomieni
z ciągu Fibonacciego,

1761
01:16:11,590 --> 01:16:15,670
który jest uznany rekurencyjne, ponieważ
wziąć dwie poprzednie

1762
01:16:15,670 --> 01:16:17,530
i dodać je razem
aby uzyskać następny.

1763
01:16:17,530 --> 01:16:21,440
Tak rekurencyjne, zawsze myślę
rekursji co jak spirali

1764
01:16:21,440 --> 01:16:24,430
tak, jesteś jak rosną w dół do niego.

1765
01:16:24,430 --> 01:16:27,150
Ale to tylko funkcja
że nazywa się.

1766
01:16:27,150 --> 01:16:32,660
>> I, rzeczywiście, bardzo szybko I
może pokazać, co to wygląda.

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
Więc tutaj rekurencyjne, jeśli spojrzymy, to jest
rekurencyjny sposób podsumować na tablicę.

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
Więc wszystko, co możemy zrobić, to
mamy sumę funkcji

1771
01:16:47,880 --> 01:16:52,210
Suma, która ma rozmiar i tablicę.

1772
01:16:52,210 --> 01:16:55,210
A jeśli zauważysz, rozmiar
ubytki o jeden za każdym razem.

1773
01:16:55,210 --> 01:17:00,365
A wszystko to nie jest wtedy, gdy x jest równa
zero-- więc jeśli rozmiar tablicy

1774
01:17:00,365 --> 01:17:02,710
jest równa zero-- powraca do zera.

1775
01:17:02,710 --> 01:17:10,440
>> W przeciwnym razie jest to streszcza
ostatni element tablicy,

1776
01:17:10,440 --> 01:17:14,790
a następnie wykonuje sumę
Reszta tablicy.

1777
01:17:14,790 --> 01:17:17,555
Więc to jest po prostu łamanie go
do coraz mniejszych problemów.

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
Krótko mówiąc, rekurencja,
funkcja, która nazywa siebie.

1780
01:17:21,890 --> 01:17:25,740
Jeśli to wszystko masz z tego,
to, co jest funkcja rekurencyjna.

1781
01:17:25,740 --> 01:17:29,870
Jeśli wziąć 51, otrzymasz bardzo,
bardzo wygodne z rekursji.

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
To jest naprawdę fajne.

1784
01:17:32,370 --> 01:17:34,660
To miało sens w jak
3 AM jedną noc.

1785
01:17:34,660 --> 01:17:37,900
A ja na to, dlaczego
nigdy tego używać?

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> Więc dla scalania rodzaju, w zasadzie
co to będzie zrobić, to jest to

1788
01:17:42,430 --> 01:17:45,620
będzie rozbicie go i złamać
aż to tylko pojedyncze elementy.

1789
01:17:45,620 --> 01:17:47,570
Poszczególne elementy są łatwe do sortowania.

1790
01:17:47,570 --> 01:17:48,070
Widzimy, że.

1791
01:17:48,070 --> 01:17:50,760
Jeśli masz jeden element, to
już za sortowane.

1792
01:17:50,760 --> 01:17:53,800
Tak więc na wejściu elementów n,
gdy n jest mniejsze niż 2,

1793
01:17:53,800 --> 01:17:58,120
po prostu wrócić, bo tej pomocy
to 0 lub 1, jak widzieliśmy.

1794
01:17:58,120 --> 01:18:00,050
Ci, są uważane za elementy posortowane.

1795
01:18:00,050 --> 01:18:02,170
>> Inaczej przerwać ją na połowę.

1796
01:18:02,170 --> 01:18:06,336
Sortuj pierwszą połowę, drugą sortowania
na pół, a następnie połączyć je razem.

1797
01:18:06,336 --> 01:18:07,460
Dlaczego to się nazywa Sortowanie przez scalanie.

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
Mamy więc tutaj będziemy sortować je.

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
Więc trzymamy ich posiadania
dopóki rozmiar tablicy to 1.

1802
01:18:17,210 --> 01:18:20,790
Więc kiedy jest jeden, po prostu wrócić
bo to jest posortowana tablica,

1803
01:18:20,790 --> 01:18:23,940
i to jest posortowanej tablicy, i to
posortowanej tablicy, wszyscy jesteśmy klasyfikowane.

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
Tak więc, co możemy zrobić, to my
rozpocząć łączenie ich ze sobą.

1806
01:18:29,420 --> 01:18:31,820
>> Tak więc sposób można
Łączenie jest myśleć o

1807
01:18:31,820 --> 01:18:36,240
po prostu usunąć mniejsze
Ilość każdej z tablic podrzędnych

1808
01:18:36,240 --> 01:18:38,330
i po prostu dodać go do wyłonił tablicy.

1809
01:18:38,330 --> 01:18:44,290
Więc jeśli spojrzeć tutaj, kiedy mamy
te zestawy mamy 4, 6 i 1.

1810
01:18:44,290 --> 01:18:47,280
Kiedy chcemy połączyć te,
patrzymy na tych dwóch pierwszych

1811
01:18:47,280 --> 01:18:50,730
i powiedzieć, OK, 1 jest mniejszy,
to idzie do przodu.

1812
01:18:50,730 --> 01:18:54,330
4 i 6, nie ma nic do porównania
go tylko oznaczyć je do końca.

1813
01:18:54,330 --> 01:18:58,020
>> Gdy połączymy te dwa, po prostu
wziąć mniejszy jeden z tych dwóch,

1814
01:18:58,020 --> 01:18:59,310
więc jest to jeden.

1815
01:18:59,310 --> 01:19:01,690
A teraz bierzemy
mniejszy z tych dwóch, SO2.

1816
01:19:01,690 --> 01:19:03,330
Mniejszy z tymi dwoma, 3.

1817
01:19:03,330 --> 01:19:06,260
Mniejszy z tych dwóch, 4, 5, 6.

1818
01:19:06,260 --> 01:19:08,630
Więc po prostu ściągając je.

1819
01:19:08,630 --> 01:19:11,210
A ponieważ mam
posortowane wcześniej,

1820
01:19:11,210 --> 01:19:14,300
wystarczy jeden
Porównanie każdym razem.

1821
01:19:14,300 --> 01:19:19,610
Więc więcej kodu, po prostu reprezentacja.

1822
01:19:19,610 --> 01:19:24,410
Więc gdy w środku i
sortowania po lewej i prawej

1823
01:19:24,410 --> 01:19:26,180
a potem po prostu połączyć te.

1824
01:19:26,180 --> 01:19:30,080
>> I nie mamy kodu
do scalenia tutaj.

1825
01:19:30,080 --> 01:19:34,110
Ale znowu, jeśli pójdziesz na
studia 50, to będzie tam.

1826
01:19:34,110 --> 01:19:36,860
Inaczej przyjść do mnie porozmawiać
jeśli nadal mylić.

1827
01:19:36,860 --> 01:19:42,340
Tak fajne jest to, że najlepszym przypadku,
w najgorszym przypadku, a oczekiwano czas pracy

1828
01:19:42,340 --> 01:19:46,250
są w dzienniku n, która
Jest o wiele lepiej niż mamy

1829
01:19:46,250 --> 01:19:48,000
widoczna dla reszty naszego rodzaju.

1830
01:19:48,000 --> 01:19:51,840
Widzieliśmy n do kwadratu
i to, co w rzeczywistości

1831
01:19:51,840 --> 01:19:54,380
się tu n log n, który jest świetny.

1832
01:19:54,380 --> 01:19:55,830
>> Spójrz, jak wiele lepiej, że jest.

1833
01:19:55,830 --> 01:19:56,780
Takie ładne krzywej.

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
O wiele bardziej efektywne.

1836
01:20:00,120 --> 01:20:03,510
Jeśli kiedykolwiek możliwe, stosowanie scalania sortowania.

1837
01:20:03,510 --> 01:20:04,810
Pozwala zaoszczędzić czas.

1838
01:20:04,810 --> 01:20:07,670
Potem znowu, jak już powiedzieliśmy, jeśli
jesteś w tej dolnej części,

1839
01:20:07,670 --> 01:20:09,480
to nie robi, że
dużej różnicy.

1840
01:20:09,480 --> 01:20:11,360
Dostać się do tysięcy
i tysiące wejść,

1841
01:20:11,360 --> 01:20:13,318
na pewno chcesz
bardziej efektywny algorytm.

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
I znowu, nasz piękny stół wszystkim
rodzaju, że chłopaki nauczyli dziś.

1844
01:20:19,400 --> 01:20:21,157
>> Tak wiem, to było gęste dzień.

1845
01:20:21,157 --> 01:20:23,490
Nie jest to koniecznie dzieje
aby pomóc w Pset.

1846
01:20:23,490 --> 01:20:28,250
Ale ja po prostu chcę, aby zastrzeżenie
że sekcja nie tylko psets.

1847
01:20:28,250 --> 01:20:31,240
Wszystko to materiał jest sprawiedliwe
Gra dla midterms.

1848
01:20:31,240 --> 01:20:35,430
A także, jeśli nie dalej z CS,
to są naprawdę ważne fundamenty

1849
01:20:35,430 --> 01:20:37,870
które musisz znać.

1850
01:20:37,870 --> 01:20:41,700
Więc kilka dni będzie
trochę więcej pset pomocy,

1851
01:20:41,700 --> 01:20:44,600
ale kilka tygodni będzie
znacznie bardziej rzeczywista zawartość

1852
01:20:44,600 --> 01:20:46,600
że nie może wydawać się super,
przydatne dla Ciebie w tej chwili,

1853
01:20:46,600 --> 01:20:51,215
ale obiecuję, jeśli nadal
na będzie bardzo, bardzo przydatna.

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> Więc to dla sekcji.

1856
01:20:54,250 --> 01:20:55,250
W dół do drutu.

1857
01:20:55,250 --> 01:20:56,570
Zrobiłem to w ciągu jednej minuty.

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
Ale nie jesteś.

1860
01:20:58,970 --> 01:21:01,240
I będę miał pączki i cukierki.

1861
01:21:01,240 --> 01:21:03,464
Czy ktoś jest uczulony na
coś, na drodze?

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
Jajka i mleko.

1864
01:21:05,890 --> 01:21:08,120
Więc pączki są nie?

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
OK.

1867
01:21:10,160 --> 01:21:10,770
Dobrze.

1868
01:21:10,770 --> 01:21:12,120
Czekolada nie?

1869
01:21:12,120 --> 01:21:12,620
Gwiazda.

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
Starbursts są dobre.

1872
01:21:14,670 --> 01:21:15,170
OK.

1873
01:21:15,170 --> 01:21:17,045
Mamy zamiar mieć
Gwiazda w przyszłym tygodniu to.

1874
01:21:17,045 --> 01:21:18,240
To, co dostanę.

1875
01:21:18,240 --> 01:21:19,690
Chłopaki mają wielki tydzień.

1876
01:21:19,690 --> 01:21:20,460
Przeczytać specyfikację.

1877
01:21:20,460 --> 01:21:22,130
>> Daj mi znać, jeśli masz jakiekolwiek pytania.

1878
01:21:22,130 --> 01:21:25,300
Pset powinny być dwa stopnie
do ciebie do czwartku.

1879
01:21:25,300 --> 01:21:28,320
Jeśli masz jakieś pytania
o tym, jak coś mi klasyfikowane

1880
01:21:28,320 --> 01:21:32,250
lub dlaczego klasyfikowane coś jak ja
nie, napisz do mnie, chodź ze mną rozmawiać.

1881
01:21:32,250 --> 01:21:34,210
Jestem trochę szalony to
tydzień, ale obiecuję

1882
01:21:34,210 --> 01:21:36,340
Będę jeszcze odpowiedzieć w ciągu 24 godzin.

1883
01:21:36,340 --> 01:21:38,240
Więc mają wielki tydzień, każdego.

1884
01:21:38,240 --> 01:21:40,090
Powodzenia w Pset.

1885
01:21:40,090 --> 01:21:41,248