1
00:00:00,000 --> 00:00:11,100
>> [Redarea muzicii]

2
00:00:11,100 --> 00:00:11,490
>> David J. MALAN: În regulă.

3
00:00:11,490 --> 00:00:12,170
Deci, bun venit înapoi.

4
00:00:12,170 --> 00:00:15,180
Aceasta este CS50, și este
la sfârșitul săptămânii trei.

5
00:00:15,180 --> 00:00:17,770
>> Deci, amintesc în ultimele câteva săptămâni,
Am petrecut destul de un pic de

6
00:00:17,770 --> 00:00:20,820
timp pe C, pe programare, pe sintaxa.

7
00:00:20,820 --> 00:00:24,680
Și e destul de normal, dacă sunteți încă
lupta cu Set Problema 2, pentru a fi

8
00:00:24,680 --> 00:00:25,950
loveste cu capul de perete.

9
00:00:25,950 --> 00:00:28,310
Este mesaje de eroare criptic cu aspect
și bug-uri pe care le

10
00:00:28,310 --> 00:00:29,220
nu pot urmări destul de jos.

11
00:00:29,220 --> 00:00:32,310
Pentru că, fiți siguri, că în doar o
timp câteva săptămâni veți privi înapoi pe

12
00:00:32,310 --> 00:00:35,930
lucruri cum ar fi Cezar, și [? V-genair,?]
poate chiar Crack, și

13
00:00:35,930 --> 00:00:40,050
seama cât de departe ai ajuns
într-o perioadă scurtă de timp.

14
00:00:40,050 --> 00:00:43,670
Deci, dacă e vreo consolare,
atârna acolo pentru acum.

15
00:00:43,670 --> 00:00:46,610
>> Astăzi, însă, vom începe să tranziție
la lucrurile nivel superior.

16
00:00:46,610 --> 00:00:49,820
Și vom începe să ia acordat pentru că
voi ști cum să program, sau la

17
00:00:49,820 --> 00:00:52,090
puțin la începuturile
că nivelul de confort.

18
00:00:52,090 --> 00:00:56,520
Și vom începe să ia în considerare modul în care putem
du-te cu privire la elaborarea de programe mai

19
00:00:56,520 --> 00:00:57,440
în mod eficient.

20
00:00:57,440 --> 00:01:01,090
Cum putem merge cu privire la optimizarea
eficiența algoritmilor noastre, și

21
00:01:01,090 --> 00:01:03,110
în general, rezolvarea mai mult
probleme interesante.

22
00:01:03,110 --> 00:01:06,850
Și începe să ia acordat pentru că,
dacă am vrea, am putea cod la orice

23
00:01:06,850 --> 00:01:08,350
dintre exemplele pe care le avem în minte.

24
00:01:08,350 --> 00:01:11,430
Așa că astăzi, nu atingeți tastatura
pentru orice formă de cod.

25
00:01:11,430 --> 00:01:15,150
Va fi nivel mult mai mare, și
în cele din urmă, cu privire la rezolvarea problemelor.

26
00:01:15,150 --> 00:01:20,490
>> Deci, pentru a ajunge la acest punct, permiteți-mi să propună
că următoarele șapte

27
00:01:20,490 --> 00:01:24,290
dreptunghiuri reprezintă șapte uși, în spatele
care sunt o grămadă de

28
00:01:24,290 --> 00:01:26,340
numere, printre care este numărul 50.

29
00:01:26,340 --> 00:01:30,470
Lasă-mă să proiecteze acest lucru pe această
Ecranul aici, de asemenea.

30
00:01:30,470 --> 00:01:36,770
Și propune ca avem nevoie de un voluntar pentru a
ajuta-mi găsesc un număr în fața

31
00:01:36,770 --> 00:01:38,140
Internet aici pentru a vedea.

32
00:01:38,140 --> 00:01:40,755
Hai sus, în roz.

33
00:01:40,755 --> 00:01:43,050
Bine.

34
00:01:43,050 --> 00:01:43,930
Care e numele tău?

35
00:01:43,930 --> 00:01:44,850
>> JENNIFER: [inaudibil]

36
00:01:44,850 --> 00:01:45,170
>> David J. MALAN: Îmi pare rău?

37
00:01:45,170 --> 00:01:45,860
>> JENNIFER: Jennifer.

38
00:01:45,860 --> 00:01:46,390
>> David J. MALAN: Jennifer.

39
00:01:46,390 --> 00:01:46,980
Bine, Jennifer.

40
00:01:46,980 --> 00:01:47,630
Îmi pare bine.

41
00:01:47,630 --> 00:01:48,370
Hai sus.

42
00:01:48,370 --> 00:01:52,430
Deci, acestea aici sunt șapte uși, și ce
Aș vrea să faci pentru noi aici,

43
00:01:52,430 --> 00:01:56,560
în fața tuturor colegilor dumneavoastră,
ne găsim numărul, 50.

44
00:01:56,560 --> 00:02:00,860
Pentru a găsi un număr, puteți arunca o privire în urmă
oricare dintre aceste uși prin simpla atingere

45
00:02:00,860 --> 00:02:03,030
pe una dintre uși, și ea
va dezvălui numărul său.

46
00:02:03,030 --> 00:02:06,080
Și să vedem cât de repede te
ne pot găsi numărul, 50.

47
00:02:06,080 --> 00:02:09,979

48
00:02:09,979 --> 00:02:11,229
>> 15.

49
00:02:11,229 --> 00:02:13,110

50
00:02:13,110 --> 00:02:14,360
16.

51
00:02:14,360 --> 00:02:16,270

52
00:02:16,270 --> 00:02:16,530
50.

53
00:02:16,530 --> 00:02:17,350
Bine făcut.

54
00:02:17,350 --> 00:02:18,040
Bine.

55
00:02:18,040 --> 00:02:19,906
Rundă de aplauze pentru Jennifer.

56
00:02:19,906 --> 00:02:21,530
>> [Aplauze]

57
00:02:21,530 --> 00:02:22,320
>> Bine.

58
00:02:22,320 --> 00:02:25,254
Deci, ce a fost strategia pentru
Identificarea numărului, 50?

59
00:02:25,254 --> 00:02:27,222
>> JENNIFER: Um, am crezut că poate dacă -

60
00:02:27,222 --> 00:02:27,714
[Inaudibil]

61
00:02:27,714 --> 00:02:28,206
>> David J. MALAN: Oh.

62
00:02:28,206 --> 00:02:29,630
Dă-mi o secundă.

63
00:02:29,630 --> 00:02:32,420
Deci, a fost strategia dvs. pentru
Identificarea numărului, 50?

64
00:02:32,420 --> 00:02:34,760
>> Jennifer: Deci, am începe de la
începutul pentru a vedea ce primul număr

65
00:02:34,760 --> 00:02:38,590
a fost, și apoi m-am gândit, poate, în cazul în care
acestea sunt clasificate în funcție, voi păstra doar

66
00:02:38,590 --> 00:02:39,970
atingând mai sus?

67
00:02:39,970 --> 00:02:40,140
>> David J. MALAN: OK.

68
00:02:40,140 --> 00:02:42,910
Și se pare că am găsit
care să fie cazul.

69
00:02:42,910 --> 00:02:45,670
Deși, să coaja înapoi straturile
doar un pic, și tu vrei să mergi

70
00:02:45,670 --> 00:02:47,640
înainte și dezvăluie celelalte uși
ai fi putut ales?

71
00:02:47,640 --> 00:02:50,400

72
00:02:50,400 --> 00:02:51,712
>> JENNIFER: Oh, dragă.

73
00:02:51,712 --> 00:02:53,128
>> David J. MALAN: Ah.

74
00:02:53,128 --> 00:02:54,280
>> Jennifer: Deci, am avut noroc.

75
00:02:54,280 --> 00:02:55,270
>> David J. MALAN: Deci, ai avut noroc.

76
00:02:55,270 --> 00:02:55,710
Bine.

77
00:02:55,710 --> 00:02:56,795
Deci, nu rău.

78
00:02:56,795 --> 00:02:58,750
Dar asta e un interesant
înțelegere, nu?

79
00:02:58,750 --> 00:03:01,870
Dacă ați asumat, și nu ai luat,
într-adevăr, un pic norocos acolo.

80
00:03:01,870 --> 00:03:05,350
Dar, dacă presupune că numerele au fost
sortate, puteți fi mai precise

81
00:03:05,350 --> 00:03:08,750
privire la modul în care a influențat
comportamentul tău?

82
00:03:08,750 --> 00:03:11,715
>> Jennifer: Deci, dacă ei au fost sortate, I
gândit mai mic poate la cel mai mare.

83
00:03:11,715 --> 00:03:11,970
>> David J. MALAN: OK.

84
00:03:11,970 --> 00:03:15,260
>> JENNIFER: Sau, în cazul în care acest lucru sa dovedit a fi
într-adevăr mare, apoi cel mai mare la cel mai mic.

85
00:03:15,260 --> 00:03:15,540
>> David J. MALAN: OK.

86
00:03:15,540 --> 00:03:18,170
Deci, cel mai mare la cel mai mic, sau
cel mai mic la cel mai mare.

87
00:03:18,170 --> 00:03:21,990
Dar permiteți-mi propun, să presupunem că a avut
ajuns ghinion, și să presupunem că ei

88
00:03:21,990 --> 00:03:26,840
nu au fost, de fapt, sortate, câți dintre
aceste uși ar putea fi trebuit să intrați

89
00:03:26,840 --> 00:03:28,590
în spatele în care cel mai rău caz?

90
00:03:28,590 --> 00:03:29,860
>> JENNIFER: Toate acestea.

91
00:03:29,860 --> 00:03:30,420
>> David J. MALAN: Toți.

92
00:03:30,420 --> 00:03:31,740
Deci, haideți să generalizeze ca, n.

93
00:03:31,740 --> 00:03:34,790
Nu se întâmplă să fie 7, dar hai să mai
în general spune ca exista n uși pe

94
00:03:34,790 --> 00:03:35,650
Ecranul aici.

95
00:03:35,650 --> 00:03:40,110
Deci, în cel mai rău caz, ar trebui
să se uite în spatele ușilor 7, sau n uși.

96
00:03:40,110 --> 00:03:44,140
Și astfel aceasta este într-adevăr, e un pic de
noroc azi, dar este într-adevăr un liniar

97
00:03:44,140 --> 00:03:46,440
Algoritmul de soiuri, chiar dacă
au fost un fel de sărind peste jurul.

98
00:03:46,440 --> 00:03:47,080
Este corect?

99
00:03:47,080 --> 00:03:47,500
>> JENNIFER: Da.

100
00:03:47,500 --> 00:03:50,000
>> David J. MALAN: Ei bine, lasă-mă să văd dacă dumneavoastră
strategia modificări dacă ne miscam

101
00:03:50,000 --> 00:03:52,190
al doilea exemplu aici cu
7 uși diferite.

102
00:03:52,190 --> 00:03:55,240
Aceleași numere, dar acest lucru
timp, ele sunt sortate.

103
00:03:55,240 --> 00:03:58,350
Care este strategia ta aici va fi,
încercarea de a pune din mintea ta ceea ce

104
00:03:58,350 --> 00:03:59,310
celelalte numere erau -

105
00:03:59,310 --> 00:03:59,930
>> JENNIFER: OK.

106
00:03:59,930 --> 00:04:02,290
>> David J. MALAN: - mai devreme?

107
00:04:02,290 --> 00:04:03,180
>> JENNIFER: Să începem
cu prima.

108
00:04:03,180 --> 00:04:03,540
>> David J. MALAN: În regulă.

109
00:04:03,540 --> 00:04:05,190
Începe cu primul.

110
00:04:05,190 --> 00:04:05,960
4.

111
00:04:05,960 --> 00:04:08,810
Acum, în cazul în care ai de gând să mergi, și de ce?

112
00:04:08,810 --> 00:04:10,040
>> JENNIFER: 4 este foarte mic.

113
00:04:10,040 --> 00:04:12,500
Deci, dacă acestea sunt un fel mai mic poate
la cel mai mare, ar trebui

114
00:04:12,500 --> 00:04:13,290
să fie de două ori că, și -.

115
00:04:13,290 --> 00:04:13,670
>> David J. MALAN: OK.

116
00:04:13,670 --> 00:04:15,990
Să vedem, ce crezi?

117
00:04:15,990 --> 00:04:19,050
>> JENNIFER: Încercați ultima.

118
00:04:19,050 --> 00:04:19,500
Frumos.

119
00:04:19,500 --> 00:04:20,880
>> David J. MALAN: Foarte bine făcut.

120
00:04:20,880 --> 00:04:21,860
Bine.

121
00:04:21,860 --> 00:04:23,010
>> [Aplauze]

122
00:04:23,010 --> 00:04:24,310
>> David J. MALAN: OK.

123
00:04:24,310 --> 00:04:26,790
Deci, ce faci de fapt asta
oribil, pentru că ești

124
00:04:26,790 --> 00:04:27,700
face foarte bine.

125
00:04:27,700 --> 00:04:31,150
Ceea ce ne lasă în imposibilitatea de a
face anumite puncte.

126
00:04:31,150 --> 00:04:32,565
Deci, haideți să încercăm să se rostogolească înapoi aici.

127
00:04:32,565 --> 00:04:34,560
>> JENNIFER: OK.

128
00:04:34,560 --> 00:04:35,980
>> David J. MALAN: Foarte bine
face, cu toate acestea.

129
00:04:35,980 --> 00:04:39,060
Deci, ai început de la început,
ai văzut că el a fost de 4, atunci te

130
00:04:39,060 --> 00:04:40,240
mutat la sfârșit.

131
00:04:40,240 --> 00:04:42,320
Dar să presupunem că nu avea noroc
acolo, și să presupunem că 50

132
00:04:42,320 --> 00:04:42,890
era în altă parte.

133
00:04:42,890 --> 00:04:46,190
Ce de-a treia etapă au fost?

134
00:04:46,190 --> 00:04:47,680
>> JENNIFER: Du-te înapoi la început.

135
00:04:47,680 --> 00:04:48,320
>> David J. MALAN: Du-te înapoi
la început.

136
00:04:48,320 --> 00:04:51,320
OK, așa că s-ar fi atins
această ușă, care a fost de 8.

137
00:04:51,320 --> 00:04:51,660
Bine.

138
00:04:51,660 --> 00:04:52,650
Așa că nu e 50.

139
00:04:52,650 --> 00:04:55,380
În cazul în care ați fi căutat viitoare?

140
00:04:55,380 --> 00:04:56,720
>> JENNIFER: Dacă nu am făcut
Știu că sortate.

141
00:04:56,720 --> 00:04:57,005
>> David J. MALAN: Corect.

142
00:04:57,005 --> 00:04:58,490
Ei bine, dacă ai știut
acestea au fost sortate -

143
00:04:58,490 --> 00:04:58,700
>> JENNIFER: Oh, nu știu, da.

144
00:04:58,700 --> 00:05:00,910
>> David J. MALAN: - dar nu
unde 50 era încă?

145
00:05:00,910 --> 00:05:01,785
>> JENNIFER: Doar mergi mai departe.

146
00:05:01,785 --> 00:05:02,130
>> David J. MALAN: În regulă.

147
00:05:02,130 --> 00:05:02,520
OK.

148
00:05:02,520 --> 00:05:03,800
Continuă.

149
00:05:03,800 --> 00:05:05,270
OK, că eu pot lucra cu.

150
00:05:05,270 --> 00:05:05,610
>> JENNIFER: OK.

151
00:05:05,610 --> 00:05:07,210
>> David J. MALAN: Acum, daca esti doar
continua să mergi, care e

152
00:05:07,210 --> 00:05:09,680
Algoritmul revin susținute în.

153
00:05:09,680 --> 00:05:10,740
>> JENNIFER: liniar -.

154
00:05:10,740 --> 00:05:11,820
>> David J. MALAN: Este un fel de liniar.

155
00:05:11,820 --> 00:05:13,480
Dar permiteți-mi propun, să
ma pus pe loc.

156
00:05:13,480 --> 00:05:14,900
Permiteți-mi să încărcarea paginii.

157
00:05:14,900 --> 00:05:17,120
același număr, același aranjament,
aceleași uși.

158
00:05:17,120 --> 00:05:21,350
Dar cred înapoi la acea prima zi în
Clasa de când am rupt-o carte de telefon în

159
00:05:21,350 --> 00:05:25,480
jumătate, un fel de, și ceea ce a fost
Strategia noastră acolo?

160
00:05:25,480 --> 00:05:26,450
>> JENNIFER: Start la mijloc.

161
00:05:26,450 --> 00:05:26,690
>> David J. MALAN: OK.

162
00:05:26,690 --> 00:05:27,610
Deci, începe de la mijloc.

163
00:05:27,610 --> 00:05:28,790
Deci, haideți să mergem mai departe și simula asta.

164
00:05:28,790 --> 00:05:30,720
Începe la mijlocul de
dezvaluind faptul ca usa.

165
00:05:30,720 --> 00:05:31,660
Astfel, numărul 16.

166
00:05:31,660 --> 00:05:35,290
Deci, ceea ce ar fi tipul puternic au făcut,
care a rupt cartea de telefon în jumătate,

167
00:05:35,290 --> 00:05:38,450
pentru a ajunge la ghici următorul?

168
00:05:38,450 --> 00:05:39,400
>> JENNIFER: Du-te în această jumătate.

169
00:05:39,400 --> 00:05:41,700
>> David J. MALAN: Și de ce să nu?

170
00:05:41,700 --> 00:05:43,900
>> JENNIFER: Dacă ar fi fost un fel de mic
la cel mai mare, atunci 50 ar trebui să fie

171
00:05:43,900 --> 00:05:44,720
la acest scop.

172
00:05:44,720 --> 00:05:44,920
>> David J. MALAN: Bine.

173
00:05:44,920 --> 00:05:45,390
Total rezonabil.

174
00:05:45,390 --> 00:05:48,380
Deci, ca o carte de telefon, te duci la
drept spre deosebire de stânga, dar aici

175
00:05:48,380 --> 00:05:49,500
este Takeaway cheie.

176
00:05:49,500 --> 00:05:53,930
Acum se poate arunca, sau rupe,
jumătate din această problemă, nu pleci

177
00:05:53,930 --> 00:05:55,970
cu 7 usi, dar într-adevăr cu doar 3.

178
00:05:55,970 --> 00:05:57,870
Care este de aproximativ jumătate din
dimensiunea problemei.

179
00:05:57,870 --> 00:05:58,350
Bine.

180
00:05:58,350 --> 00:06:01,890
Deci, acum ce ar trebui
făcut după ce te duci dreptate?

181
00:06:01,890 --> 00:06:05,870
>> Jennifer: Deci, 16 este încă destul de mic,
în raport cu 50, așa că poate voi încerca,

182
00:06:05,870 --> 00:06:06,700
ca, aceasta.

183
00:06:06,700 --> 00:06:07,890
>> David J. MALAN: În regulă.

184
00:06:07,890 --> 00:06:08,720
42.

185
00:06:08,720 --> 00:06:10,830
Bine, deci acum care e
instinctul îți spune?

186
00:06:10,830 --> 00:06:12,100
>> JENNIFER: Pot să arunc
acest lucru și apoi pur și simplu -

187
00:06:12,100 --> 00:06:12,360
>> David J. MALAN: OK.

188
00:06:12,360 --> 00:06:14,212
Bun, puteți arunca
jumătate din stânga acolo.

189
00:06:14,212 --> 00:06:14,890
>> JENNIFER: - alege asta.

190
00:06:14,890 --> 00:06:15,530
>> David J. MALAN: și dreptul.

191
00:06:15,530 --> 00:06:15,760
>> JENNIFER: Da.

192
00:06:15,760 --> 00:06:17,820
>> David J. MALAN: Deci, chiar daca e greu
pentru a vedea, probabil, atunci când există doar

193
00:06:17,820 --> 00:06:21,320
7 usi, gândiți-vă, acum,
consistența

194
00:06:21,320 --> 00:06:22,620
algoritmul pe care tocmai ați aplicat.

195
00:06:22,620 --> 00:06:24,510
În cazul precedent, ai făcut
noroc, care a fost mare.

196
00:06:24,510 --> 00:06:26,540
Dar ai folosit o euristică,
Aș spune.

197
00:06:26,540 --> 00:06:29,150
Ai folosit un fel de instinctele tale, și
știind că sortate, dacă e destul de

198
00:06:29,150 --> 00:06:31,600
mici la început, evident, ne-am
Trebuie să mergem mai la dreapta.

199
00:06:31,600 --> 00:06:34,990
Dar într-un sens, ai avut noroc,
pentru că poate acest lucru a fost numărul 100,

200
00:06:34,990 --> 00:06:36,220
și poate că 50 a fost mai mult la mijloc.

201
00:06:36,220 --> 00:06:37,910
Poate 50 a fost chiar aici.

202
00:06:37,910 --> 00:06:40,960
>> Dar ce-ai făcut un pic diferit
de data aceasta a fost, ai făcut același lucru

203
00:06:40,960 --> 00:06:42,150
din nou și din nou.

204
00:06:42,150 --> 00:06:45,310
Și aș spune că ceea ce tocmai
a, deși influențată de telefon

205
00:06:45,310 --> 00:06:48,100
exemplu carte, este ceva mult
mai algoritmică, și mult

206
00:06:48,100 --> 00:06:49,930
mai puțin de construcții casetat.

207
00:06:49,930 --> 00:06:51,620
Mult mai puțin instinctiv.

208
00:06:51,620 --> 00:06:57,160
Deci, la sfârșitul zilei, cum ar fi
ce descrie eficiența

209
00:06:57,160 --> 00:07:00,530
Primul algoritm, unde te-ai dus
la stânga la dreapta, față de

210
00:07:00,530 --> 00:07:03,430
al doilea algoritm aici?

211
00:07:03,430 --> 00:07:06,460
>> JENNIFER: aceasta ar trebui să, cum ar fi, poate
înjumătăți timpul, sau chiar mai mult, da.

212
00:07:06,460 --> 00:07:07,320
>> David J. MALAN: OK, poate chiar mai mult.

213
00:07:07,320 --> 00:07:10,150
Să împinge un pic mai greu la asta.

214
00:07:10,150 --> 00:07:13,030
Ceea ce într-adevăr, dacă vom continua acest
logică, am înjumătățit siguranta

215
00:07:13,030 --> 00:07:15,830
durată de funcționare cu acest al doilea algoritm
aruncând jumătate din

216
00:07:15,830 --> 00:07:18,470
numere, dar ceea ce am făcut la următoarea
repetare, atunci când Jennifer a relevat

217
00:07:18,470 --> 00:07:20,615
al doilea număr?

218
00:07:20,615 --> 00:07:22,830
>> Am înjumătățit numărul de uși din nou.

219
00:07:22,830 --> 00:07:25,270
Și atunci ce am făcut după aceea, în cazul în care
au existat mai multe uși pentru a juca cu?

220
00:07:25,270 --> 00:07:27,520
Noi le-ar reduce la jumătate, și din nou,
și din nou, și din nou.

221
00:07:27,520 --> 00:07:30,420
Și acest lucru a fost la fel ca voi toți
în picioare la prima săptămână de

222
00:07:30,420 --> 00:07:33,000
clasă, jumătate dintre voi sta jos, pe jumătate
de stai jos, jumatate din tine

223
00:07:33,000 --> 00:07:35,440
ședinței în jos, până când unul singur
Sufletul a fost în picioare.

224
00:07:35,440 --> 00:07:39,050
Și am spus că timpul de funcționare a
că, numărul de măsurile pe care le au fost

225
00:07:39,050 --> 00:07:40,430
pe ordinea de ce?

226
00:07:40,430 --> 00:07:41,230
>> SPEAKER 1: [inaudibil]

227
00:07:41,230 --> 00:07:43,970
>> David J. MALAN: Deci baza log 2 n,
sau doar mai simplu, jurnal de n.

228
00:07:43,970 --> 00:07:45,060
Așa ceva logaritmică.

229
00:07:45,060 --> 00:07:48,380
Iar graficul nu a fost o linie dreaptă
care tocmai a devenit mai rău și mai rău, a fost

230
00:07:48,380 --> 00:07:52,490
această curbă interesant, care nu au
obține așa de rău în timp.

231
00:07:52,490 --> 00:07:53,910
Deci, haideți să stai la această idee.

232
00:07:53,910 --> 00:07:54,690
Să-i mulțumim lui Jennifer.

233
00:07:54,690 --> 00:07:56,150
Multumesc mult pentru a veni în sus.

234
00:07:56,150 --> 00:07:57,400
Și, unul sec.

235
00:07:57,400 --> 00:08:00,170

236
00:08:00,170 --> 00:08:02,925
Nu lămpi de birou azi, dar
nu au CS50 bile de stres.

237
00:08:02,925 --> 00:08:03,420
>> JENNIFER: Yay.

238
00:08:03,420 --> 00:08:04,410
>> David J. MALAN: Bine, aici.

239
00:08:04,410 --> 00:08:06,545
Vă mulțumim pentru a suporta
stresul aici.

240
00:08:06,545 --> 00:08:07,350
Bine.

241
00:08:07,350 --> 00:08:10,620
Așa că haideți să vedem dacă nu putem acum
formaliza acest lucru un pic mai mult.

242
00:08:10,620 --> 00:08:14,820
Deci, din nou, ceea ce tocmai am făcut a fost
în esență, același lucru ca și am făcut

243
00:08:14,820 --> 00:08:16,660
în prima săptămână.

244
00:08:16,660 --> 00:08:23,780
Dar, mai degrabă decât se termină cu doar un liniar
algoritm, care este descris

245
00:08:23,780 --> 00:08:27,210
înainte ca această linie dreaptă,
prin care, dacă am pus o ușă mai mult pe

246
00:08:27,210 --> 00:08:29,610
pe ecran, apoi Jennifer ar fi
au trebuit să se uite, potențial,

247
00:08:29,610 --> 00:08:30,600
în urmă o ușă mai mult.

248
00:08:30,600 --> 00:08:33,490
Dacă am pus două uși mai mult, ea ar putea avea
să se uite în spatele două uși mai mult.

249
00:08:33,490 --> 00:08:35,990
>> Și astfel, nu a fost acest liniar
Raportul dintre mărimea

250
00:08:35,990 --> 00:08:39,059
Problema pe, să zicem, axa x, iar
cantitatea de timp este nevoie pentru a

251
00:08:39,059 --> 00:08:40,440
rezolva pe y.

252
00:08:40,440 --> 00:08:43,330
Dar imaginea am fost aluzie la
a fost mai devreme această linie verde.

253
00:08:43,330 --> 00:08:45,970
Verde în mod deliberat, pentru că
doar simțit mai bine.

254
00:08:45,970 --> 00:08:49,790
În teorie, algoritmul, atunci când am făcut-o
cu cartea de telefon, atunci când am făcut-o

255
00:08:49,790 --> 00:08:52,420
cu voi numărare reciproc, și
în al doilea caz, atunci când Jennifer doar

256
00:08:52,420 --> 00:08:55,250
a făcut-o până aici, a fost un fel
de fundamental mai bine.

257
00:08:55,250 --> 00:08:57,180
Pentru că nu a fost doar de două ori la fel de repede.

258
00:08:57,180 --> 00:08:58,870
Nu a fost chiar de patru ori mai repede.

259
00:08:58,870 --> 00:09:03,290
Acesta a fost în întregime dependentă de ceea ce
Mărimea de intrare a fost, după cum a câte

260
00:09:03,290 --> 00:09:05,220
măsurile pe care le în cele din urmă a luat.

261
00:09:05,220 --> 00:09:08,040
>> Și așa această idee simplă, care ne-a luat tot
pentru a acordat cu cartea de telefon,

262
00:09:08,040 --> 00:09:10,200
pot fi aplicate în mod similar
la ceva de genul asta.

263
00:09:10,200 --> 00:09:12,380
Și acest lucru ar putea fi mult mai lejer
cunoscut sub numele de, cum s-ar putea

264
00:09:12,380 --> 00:09:13,940
imagina, dezbina si cucereste.

265
00:09:13,940 --> 00:09:16,390
Nu spre deosebire de ceea ce am făcut, desigur,
cu cartea de telefon.

266
00:09:16,390 --> 00:09:18,300
>> Dar pseudocod, rechemare, a fost aceasta.

267
00:09:18,300 --> 00:09:21,800
Așa că nu va face acest lucru din nou, dar amintesc
că prima săptămână, toți dintre noi s-au ridicat

268
00:09:21,800 --> 00:09:25,140
și apoi jumătate de te-ai așezat jos, jumătate din
ai stat jos, jumătate dintre voi așezat.

269
00:09:25,140 --> 00:09:29,280
Care Algoritmul a fost implementat într-un
bit al unui mod înșelăciune, prin aceea că, ea

270
00:09:29,280 --> 00:09:32,870
nu a fost doar unul din mine numărare,
fundamental, mai eficient.

271
00:09:32,870 --> 00:09:35,830
În acest caz, am fost pârghie
o resursă secundară.

272
00:09:35,830 --> 00:09:39,470
Un fel de, mai multe procesoare, mai multe creiere,
mai multe persoane inteligente

273
00:09:39,470 --> 00:09:42,740
cameră s-au m-ai ajutat obține de la ceva
liniar la ceva

274
00:09:42,740 --> 00:09:45,190
logaritmică, de la ceva
roșu la ceva verde.

275
00:09:45,190 --> 00:09:48,650
>> Dar, în acest caz, Jennifer singura care poate
fundamental îmbunătăți pe

276
00:09:48,650 --> 00:09:52,370
performanța de primul ei algoritm de,
din nou, doar gândesc un pic mai greu.

277
00:09:52,370 --> 00:09:56,650
Și acum, atunci când vine vorba de timp pentru a pune în aplicare
aceste lucruri, imaginind

278
00:09:56,650 --> 00:10:00,670
ce linii de cod puteți scrie astfel de
pe care le puteți repeta din nou, și

279
00:10:00,670 --> 00:10:03,350
din nou, și din nou, un fel de
într-o manieră looping.

280
00:10:03,350 --> 00:10:06,370
Pentru că nu vei avea
de lux, cum ar fi Jennifer a făcut la început, pentru a

281
00:10:06,370 --> 00:10:10,460
au doar o grămadă de FI și spune,
hmm, în cazul în care acest prim număr este de 4,

282
00:10:10,460 --> 00:10:11,800
permiteți-mi să sari tot drumul până la sfârșit.

283
00:10:11,800 --> 00:10:14,180
Ooh, în cazul în care numărul este prea mare,
permiteți-mi să se mute înapoi arbitrar

284
00:10:14,180 --> 00:10:15,220
la al doilea element.

285
00:10:15,220 --> 00:10:18,210
Veți găsi că va fi mult
mai greu pentru a formaliza ceea ce noi, oamenii,

286
00:10:18,210 --> 00:10:21,270
ia acordat pentru ca foarte rezonabil
euristica, dar un calculator este doar

287
00:10:21,270 --> 00:10:23,260
de gând să faci ceea ce-l spun să facă.

288
00:10:23,260 --> 00:10:25,280
>> Acum, acest lucru este foarte interesant
implicații.

289
00:10:25,280 --> 00:10:29,950
Acest grafic este un fel de menit să rezolve de
copleșească vizual, dar notificare, în cazul în care

290
00:10:29,950 --> 00:10:32,230
este linia dreaptă în acest grafic?

291
00:10:32,230 --> 00:10:35,330
În cazul în care este grafic liniar
pe care o numim n?

292
00:10:35,330 --> 00:10:37,580
Ei bine, e un fel de către partea de jos
de această imagine, nu?

293
00:10:37,580 --> 00:10:40,500
Deci, tot ce am făcut e că am un fel de
mărită pentru axa x și

294
00:10:40,500 --> 00:10:44,780
axa y pentru a încerca pentru a obține un sentiment de ceea ce
alte tipuri de curbe arata.

295
00:10:44,780 --> 00:10:47,760
>> Și de specificul matematice
expresii de azi nu vor conta atât de

296
00:10:47,760 --> 00:10:52,440
mult, dar observați că există o mulțime de
algoritmi care sunt mult mai rău decât

297
00:10:52,440 --> 00:10:53,470
ceva care este liniar.

298
00:10:53,470 --> 00:10:55,410
Într-adevăr, n cuburi arată destul de rău.

299
00:10:55,410 --> 00:10:58,400
2 la n arată destul de rău.
n pătrat arată destul de rău.

300
00:10:58,400 --> 00:11:01,630
Și vom vedea ce unii dintre cei
ar putea fi în realitate azi.

301
00:11:01,630 --> 00:11:05,430
Și log n nu se simte la fel de rău, dar
mai bine decât n este 2 log bază de n.

302
00:11:05,430 --> 00:11:08,080
Dar știi, ar fi fost chiar
mai uimitor dacă Jennifer, sau dacă,

303
00:11:08,080 --> 00:11:12,910
că prima săptămână, a venit cu
ceva care e jurnal de jurnal de n.

304
00:11:12,910 --> 00:11:15,880
>> Deci, cu alte cuvinte, nu e asta tot
Gama de soluții posibile

305
00:11:15,880 --> 00:11:18,570
probleme, dar chiar și aici, notificare
ce se va întâmpla.

306
00:11:18,570 --> 00:11:22,910
Când am micșora, care din aceste curbe
se va dovedi a fi absolut

307
00:11:22,910 --> 00:11:26,630
cel mai rău de cele de pe ecran acum?

308
00:11:26,630 --> 00:11:28,680
Deci, n cuburi pare destul de
rău în acest moment.

309
00:11:28,680 --> 00:11:32,470
Dar dacă ne depărta și a vedea mai mult din
x și y-axa, care se va

310
00:11:32,470 --> 00:11:34,550
domina în cele din urmă?

311
00:11:34,550 --> 00:11:37,120
Deci, de fapt dovedește că 2 la
n, și vă puteți da seama de acest lucru doar prin

312
00:11:37,120 --> 00:11:39,990
conectarea în unele ce în ce mai mare
numere, și veți vedea că 2 la

313
00:11:39,990 --> 00:11:42,070
n, într-adevăr, se mărește mult mai rapid.

314
00:11:42,070 --> 00:11:45,530
Dacă vrem cu adevărat micșora, o 2 la
n algoritmul absolut e de rahat.

315
00:11:45,530 --> 00:11:48,170
Vreau să spun acest lucru se întâmplă să ia
destul de un pic de timp pentru

316
00:11:48,170 --> 00:11:49,460
calculator, pentru a prelucra.

317
00:11:49,460 --> 00:11:52,500
>> Dar veți vedea în timp, mai ales
cu viitoarele seturi de probleme și chiar

318
00:11:52,500 --> 00:11:55,600
proiecte finale, este datele dumneavoastră
Set devine mare, bine?

319
00:11:55,600 --> 00:11:58,300
Chiar și în prima versiune a Facebook,
ca numărul de prieteni, și

320
00:11:58,300 --> 00:12:01,840
numărul de utilizatori înregistrați ai mare,
puteti sorta de telefon ea în și

321
00:12:01,840 --> 00:12:05,530
implementa ceva cu căutare liniară,
sau o sortare foarte simplu

322
00:12:05,530 --> 00:12:07,030
algoritm, așa cum vom vedea azi.

323
00:12:07,030 --> 00:12:09,280
Trebuie să începem să gândim mai greu
și mai greu despre aceste probleme.

324
00:12:09,280 --> 00:12:12,070
Și tipurile de probleme de locuri, cum ar fi
Facebook și Google, și Microsoft,

325
00:12:12,070 --> 00:12:16,350
și alții lucrează în exact aceste
fel de mare fel de date de întrebări

326
00:12:16,350 --> 00:12:18,530
din ce în ce în aceste zile.

327
00:12:18,530 --> 00:12:18,900
>> Bine.

328
00:12:18,900 --> 00:12:23,800
Deci, succesul lui Jennifer, în care a doua
algoritm, sincer, ea a făcut uimitor

329
00:12:23,800 --> 00:12:26,110
bine prima dată, dar hai
scrie-l ca noroc, astfel încât să

330
00:12:26,110 --> 00:12:27,000
pot face acest punct.

331
00:12:27,000 --> 00:12:30,970
În al doilea caz, ea indatorare un
algoritm care repetă din nou și

332
00:12:30,970 --> 00:12:34,670
din nou, dar ea a luat pentru a acordat un
sigur presupunerea că am permis

333
00:12:34,670 --> 00:12:39,370
ei, dar ea a exploatat unele detalii
a doua oară că ea nu a avut

334
00:12:39,370 --> 00:12:39,840
prima dată.

335
00:12:39,840 --> 00:12:41,800
Care a fost ce?

336
00:12:41,800 --> 00:12:43,050
>> Că lista a fost sortate.

337
00:12:43,050 --> 00:12:46,350
Asa ca imediat ce lista a fost sortate, ne
susțin că Jennifer a fost în stare să facă

338
00:12:46,350 --> 00:12:47,480
fundamental mai bine.

339
00:12:47,480 --> 00:12:51,450
7 usi, da, nu este interesant,
dar să presupunem că suntem 7 milioane de uși.

340
00:12:51,450 --> 00:12:54,080
Jurnal de n este cu siguranta va
pentru a efectua mult, mult

341
00:12:54,080 --> 00:12:55,610
mai rapidă pe termen lung.

342
00:12:55,610 --> 00:12:58,880
Dar ea trebuia să aibă
usi clasificate în funcție de ea.

343
00:12:58,880 --> 00:13:02,320
Acum, mi-am luat libertatea de a face asta
în prealabil pe ecranul calculatorului

344
00:13:02,320 --> 00:13:05,160
aici, dar să presupunem că Jennifer
a trebuit să facă asta ea?

345
00:13:05,160 --> 00:13:10,120
Să presupunem că ușile în cauză
Datele reprezentate într-o bază de date, sau

346
00:13:10,120 --> 00:13:14,260
Prietenii înregistrate pentru Facebook, sau
orice pagini web pe internet care

347
00:13:14,260 --> 00:13:16,880
diverse site-uri ar putea avea nevoie
să indice sau căutare pe.

348
00:13:16,880 --> 00:13:20,940
>> Să presupunem că tocmai ați avut de date brute
stabilit și a fost lăsat la tine, sau să

349
00:13:20,940 --> 00:13:23,010
Jennifer a face acest lucru sortare?

350
00:13:23,010 --> 00:13:26,950
Că, mai degrabă, ne cere să răspundă
problema, ei bine, cât de mult timp

351
00:13:26,950 --> 00:13:31,080
ar fi luat Jennifer, sau chiar și pe mine,
pentru a sorta aceste numere în avans, astfel încât

352
00:13:31,080 --> 00:13:32,680
că ea ar putea profita de asta?

353
00:13:32,680 --> 00:13:32,880
Dreapta?

354
00:13:32,880 --> 00:13:36,620
Deoarece implicație, desigur, este
în cazul în care este nevoie de mine ceva timp pentru a sorta

355
00:13:36,620 --> 00:13:40,800
numerele, care naiba ii pasa pe care le
Puteți găsi un număr ca 50 atât de repede,

356
00:13:40,800 --> 00:13:44,850
ca și în cazul lui Jennifer, dacă am mai mult
copleșit de cantitatea de timp totală

357
00:13:44,850 --> 00:13:46,920
a luat de sortare lucruri în avans?

358
00:13:46,920 --> 00:13:49,320
>> Așa că haideți să vedem dacă nu putem
picteze imaginea aici.

359
00:13:49,320 --> 00:13:51,370
Am o grămadă mai mult stres
bile, în cazul în care vă ajută

360
00:13:51,370 --> 00:13:52,270
sparge gheata aici.

361
00:13:52,270 --> 00:13:55,690
Și dacă nu te superi, am
nevoie de șapte voluntar -

362
00:13:55,690 --> 00:13:57,060
pe, OK.

363
00:13:57,060 --> 00:13:57,240
Wow.

364
00:13:57,240 --> 00:13:59,250
Deci, noi nu trebuie să-și petreacă
pe lămpi de birou, se pare.

365
00:13:59,250 --> 00:13:59,690
Bine.

366
00:13:59,690 --> 00:14:01,530
Deci, cum despre voi doi in fata.

367
00:14:01,530 --> 00:14:04,160
Cum despre voi doi, în spate.

368
00:14:04,160 --> 00:14:04,870
Așa că e patru.

369
00:14:04,870 --> 00:14:09,890
Cum despre tine in fata
cinci, șase și șapte.

370
00:14:09,890 --> 00:14:10,320
Chiar acolo.

371
00:14:10,320 --> 00:14:13,260
Prietenul tau te-subliniind,
astfel încât să obțineți un premiu.

372
00:14:13,260 --> 00:14:13,700
>> Bine.

373
00:14:13,700 --> 00:14:14,410
Hai sus.

374
00:14:14,410 --> 00:14:17,120
Și de ce nu ne-ai
veniți pe aici.

375
00:14:17,120 --> 00:14:18,960
Am de gând să vă dau fiecare un număr.

376
00:14:18,960 --> 00:14:22,150
Și mergeți mai departe și aranjați-vă
identic cu ceea ce este

377
00:14:22,150 --> 00:14:25,180
reprezentate pe ecran.

378
00:14:25,180 --> 00:14:26,530
>> [Interpune VOCI]

379
00:14:26,530 --> 00:14:28,160
>> David J. MALAN: OOP, îmi pare rău.

380
00:14:28,160 --> 00:14:30,210
Bug.

381
00:14:30,210 --> 00:14:32,180
Bine.

382
00:14:32,180 --> 00:14:32,750
Ei bine, aici vom merge.

383
00:14:32,750 --> 00:14:34,180
Numărul cinci.

384
00:14:34,180 --> 00:14:35,136
Numărul șase.

385
00:14:35,136 --> 00:14:37,770
Unu, doi, trei, patru,
cinci, șase, șapte.

386
00:14:37,770 --> 00:14:39,410
Oh, asta e ciudat.

387
00:14:39,410 --> 00:14:41,210
>> DIFUZOR 2: Voi lua doar o -.

388
00:14:41,210 --> 00:14:41,900
>> David J. MALAN: afacere bună.

389
00:14:41,900 --> 00:14:43,130
Bine.

390
00:14:43,130 --> 00:14:44,611
Va multumim pentru participare.

391
00:14:44,611 --> 00:14:47,200
>> [Aplauze]

392
00:14:47,200 --> 00:14:48,580
>> OK.

393
00:14:48,580 --> 00:14:48,860
Bine.

394
00:14:48,860 --> 00:14:51,970
Deci avem patru, două, șase,
unul, trei, șapte, cinci.

395
00:14:51,970 --> 00:14:56,010
Perfect așa că avem șapte voluntari
aici care sunt egale în lățime cu

396
00:14:56,010 --> 00:14:57,430
matrice care ne jucam
cu mai devreme.

397
00:14:57,430 --> 00:14:59,470
Și am ales șapte motive
care va fi doar

398
00:14:59,470 --> 00:15:00,840
convenabil într-un pic.

399
00:15:00,840 --> 00:15:04,400
Și am de gând să propună mai întâi că
am sorta aceste șapte voluntari.

400
00:15:04,400 --> 00:15:06,786
Dacă doriți, în primul rând,
să-l salut, deși.

401
00:15:06,786 --> 00:15:08,970
Din moment ce acest lucru va fi un
incomode câteva minute.

402
00:15:08,970 --> 00:15:10,370
Introducerea voi.

403
00:15:10,370 --> 00:15:10,980
>> GRACE: Bună, eu sunt Grace.

404
00:15:10,980 --> 00:15:14,190
Sunt un al doilea de studentie la Leverett House.

405
00:15:14,190 --> 00:15:14,620
>> BRANSON: Hi.

406
00:15:14,620 --> 00:15:15,620
Sunt Branson.

407
00:15:15,620 --> 00:15:16,920
Sunt un boboc în Weld.

408
00:15:16,920 --> 00:15:19,755

409
00:15:19,755 --> 00:15:20,230
>> GABE: Hi.

410
00:15:20,230 --> 00:15:21,040
Sunt Gabe.

411
00:15:21,040 --> 00:15:22,300
Sunt un junior în Cabot.

412
00:15:22,300 --> 00:15:24,826

413
00:15:24,826 --> 00:15:25,980
>> NEIL: Eu sunt Neil.

414
00:15:25,980 --> 00:15:29,090
Sunt un boboc în Matthews.

415
00:15:29,090 --> 00:15:29,550
>> JASON: Sunt Jason.

416
00:15:29,550 --> 00:15:32,816
Sunt un boboc în Greenough.

417
00:15:32,816 --> 00:15:33,700
>> MIKE: Sunt Mike.

418
00:15:33,700 --> 00:15:37,360
Sunt un boboc in Grays.

419
00:15:37,360 --> 00:15:37,990
>> JESS: Sunt Jess.

420
00:15:37,990 --> 00:15:40,313
Sunt un al doilea de studentie la Leverett.

421
00:15:40,313 --> 00:15:41,300
>> David J. MALAN: Excelent.

422
00:15:41,300 --> 00:15:41,850
Bine.

423
00:15:41,850 --> 00:15:44,190
Ei bine, vă mulțumesc pentru toate noastre
voluntarii de aici până acum.

424
00:15:44,190 --> 00:15:47,110
Și provocarea la îndemână acum se întâmplă
să fie la un fel de acesti baieti, dar apoi

425
00:15:47,110 --> 00:15:50,250
am de gând să trebuie să se gândească un pic
tare despre cât de eficient ne de fapt

426
00:15:50,250 --> 00:15:51,110
le-am sortat.

427
00:15:51,110 --> 00:15:52,580
Deci, haideți să încercăm mai întâi acest lucru.

428
00:15:52,580 --> 00:15:55,970
Voi putea vedea numere reciproc
doar prin plasarea în jurul colțuri.

429
00:15:55,970 --> 00:15:59,380
Du-te și ia câteva secunde, și
Sorteaza-vă de cea mai mică pe

430
00:15:59,380 --> 00:16:01,240
a plecat la cel mai mare de pe dreapta.

431
00:16:01,240 --> 00:16:02,490
Du-te.

432
00:16:02,490 --> 00:16:07,010

433
00:16:07,010 --> 00:16:07,530
>> OK.

434
00:16:07,530 --> 00:16:08,030
Bun.

435
00:16:08,030 --> 00:16:09,370
Asta a fost rapid chiar darn.

436
00:16:09,370 --> 00:16:14,040
Acum cineva aici, care a fost algoritmul
că tipii ăștia aplicat?

437
00:16:14,040 --> 00:16:14,900
>> SPEAKER 1: cel mai puțin la cel mai mare.

438
00:16:14,900 --> 00:16:15,000
>> David J. MALAN: OK.

439
00:16:15,000 --> 00:16:18,070
Cel puțin pentru cea mai mare este într-adevăr un fel de
obiectiv, dar eu nu sunt sigur că e

440
00:16:18,070 --> 00:16:18,890
într-adevăr un algoritm.

441
00:16:18,890 --> 00:16:21,810
Cel mai mare de a nu spune
mi pas-cu-pas ce să facă.

442
00:16:21,810 --> 00:16:22,833
Da?

443
00:16:22,833 --> 00:16:24,083
>> SPEAKER 1: [inaudibil]

444
00:16:24,083 --> 00:16:26,010

445
00:16:26,010 --> 00:16:26,280
>> David J. MALAN: OK.

446
00:16:26,280 --> 00:16:28,920
Deci, dacă vedeți o persoană mai mică decât
numărul, apoi trece la

447
00:16:28,920 --> 00:16:29,680
dreptul de ei.

448
00:16:29,680 --> 00:16:32,800
Deci, care este acum devine mai expresiv,
mai mult ca un algoritm, pentru că

449
00:16:32,800 --> 00:16:35,410
se poate spune, în cazul în care acest lucru, atunci.

450
00:16:35,410 --> 00:16:37,050
Deci avem un fel de
construct condiționată.

451
00:16:37,050 --> 00:16:39,700
Și tipii ăștia păreau să faci asta câteva
ori, pentru că unii dintre voi s-au mutat un pic

452
00:16:39,700 --> 00:16:40,420
de la distanță.

453
00:16:40,420 --> 00:16:43,410
Deci, nu era probabil un fel de
looping întâmplă în mintea lor.

454
00:16:43,410 --> 00:16:44,610
>> Dar să încercăm să oficializeze acest lucru.

455
00:16:44,610 --> 00:16:47,540
Dacă voi putea reseta înapoi
la acest aranjament.

456
00:16:47,540 --> 00:16:50,650
Să vedem dacă nu putem formaliza acest lucru o
bit, iar apoi pune întrebarea, doar

457
00:16:50,650 --> 00:16:51,580
cat de eficient este acest lucru?

458
00:16:51,580 --> 00:16:54,220
Desigur, atunci când facem acest lucru mai lent,
se va simti la fel de bine de

459
00:16:54,220 --> 00:16:57,210
un algoritm, dar să vedem dacă putem
pune degetele pe treptele precise.

460
00:16:57,210 --> 00:16:58,670
>> Deci, voi doi sunt patru și doi.

461
00:16:58,670 --> 00:17:01,020
Sau te ordinea corectă sau incorectă?

462
00:17:01,020 --> 00:17:01,900
În mod evident incorecte.

463
00:17:01,900 --> 00:17:02,710
Așa că am schimbat.

464
00:17:02,710 --> 00:17:05,170
Acum am de gând să se mute la o parte
aici și spune, patru la șase.

465
00:17:05,170 --> 00:17:06,240
Esti corect sau incorect?

466
00:17:06,240 --> 00:17:06,599
>> GABE: Corect.

467
00:17:06,599 --> 00:17:07,180
>> David J. MALAN: Corect.

468
00:17:07,180 --> 00:17:08,300
Sase si unul?

469
00:17:08,300 --> 00:17:08,609
Nope.

470
00:17:08,609 --> 00:17:09,630
Swap.

471
00:17:09,630 --> 00:17:10,490
Deci asta e două swap.

472
00:17:10,490 --> 00:17:11,710
Șase și trei?

473
00:17:11,710 --> 00:17:11,980
Nope.

474
00:17:11,980 --> 00:17:13,000
Swap.

475
00:17:13,000 --> 00:17:13,930
Șase și șapte?

476
00:17:13,930 --> 00:17:14,630
Arată bine.

477
00:17:14,630 --> 00:17:15,396
Șapte și cinci?

478
00:17:15,396 --> 00:17:16,150
>> JESS: [inaudibil]

479
00:17:16,150 --> 00:17:17,089
>> David J. MALAN: OK, schimba.

480
00:17:17,089 --> 00:17:19,770
Și sortate.

481
00:17:19,770 --> 00:17:19,980
Bine.

482
00:17:19,980 --> 00:17:21,440
Deci, evident, nu, corect?

483
00:17:21,440 --> 00:17:22,470
Deci nu a fost mai întâmplă.

484
00:17:22,470 --> 00:17:24,920
Dar, într-adevăr, acești oameni, chiar
doar instinctiv.

485
00:17:24,920 --> 00:17:25,450
păstrat în mișcare.

486
00:17:25,450 --> 00:17:27,710
Ei nu s-au oprit doar după ce
corectat o problemă.

487
00:17:27,710 --> 00:17:27,839
Deci.

488
00:17:27,839 --> 00:17:29,390
Într-adevăr, am de gând să aibă
să facă același lucru.

489
00:17:29,390 --> 00:17:32,720
Am de gând să aibă de a sorta de derulare înapoi
la începutul acestei probleme,

490
00:17:32,720 --> 00:17:35,630
sau la începutul acestei matrice de
oameni, să începem numindu-le.

491
00:17:35,630 --> 00:17:38,366
>> Și acum ce ar trebui algoritmul meu
pe a doua trecere să fie?

492
00:17:38,366 --> 00:17:39,220
>> SPEAKER 1: Același lucru.

493
00:17:39,220 --> 00:17:39,940
>> David J. MALAN: Același lucru.

494
00:17:39,940 --> 00:17:41,460
Și acest lucru, am început să-mi placă, nu?

495
00:17:41,460 --> 00:17:44,720
De îndată ce puteți găsi te face
același lucru din nou și din nou, că este

496
00:17:44,720 --> 00:17:47,890
ce în ce mai mult ca un algoritm,
și instinct mai puțin umane.

497
00:17:47,890 --> 00:17:48,680
>> Deci, acum, aici vom merge din nou.

498
00:17:48,680 --> 00:17:49,870
Două și patru?

499
00:17:49,870 --> 00:17:50,220
Nu.

500
00:17:50,220 --> 00:17:51,050
Patru și una?

501
00:17:51,050 --> 00:17:53,380
Ah, nu a existat într-adevăr un
sunt încă multe de făcut.

502
00:17:53,380 --> 00:17:53,620
Pentru și trei?

503
00:17:53,620 --> 00:17:54,572
Bun.

504
00:17:54,572 --> 00:17:56,000
Patru și șase?

505
00:17:56,000 --> 00:17:58,380
Șase și cinci?

506
00:17:58,380 --> 00:17:59,470
Șase și șapte?

507
00:17:59,470 --> 00:18:00,970
OK, acum, terminat.

508
00:18:00,970 --> 00:18:01,550
OK, nu.

509
00:18:01,550 --> 00:18:02,710
Trebuie să mă întorc.

510
00:18:02,710 --> 00:18:05,130
>> Deci, acum, din nou, facem asta
un pic mai mult în mod deliberat.

511
00:18:05,130 --> 00:18:08,700
Și acum, nu e doar un creier
executarea acestui algoritm.

512
00:18:08,700 --> 00:18:10,290
Un CPU, dacă vreți.

513
00:18:10,290 --> 00:18:13,090
Și sincer, asta e singura resursă
vom avea acces la.

514
00:18:13,090 --> 00:18:16,280
Și odată ce te duci înapoi la o tastatură
și au ceva de genul C la noastre

515
00:18:16,280 --> 00:18:19,600
eliminarea, suntem doar scris un program de
care pot face un singur lucru la un moment dat.

516
00:18:19,600 --> 00:18:22,900
Întrucât, tipii ăștia acum o clipă, am
efectul de levier mintile colective

517
00:18:22,900 --> 00:18:24,180
cum ați făcut voi în săptămâna zero.

518
00:18:24,180 --> 00:18:24,980
Așa că haideți să continuăm să facem acest lucru.

519
00:18:24,980 --> 00:18:26,260
>> Doi și unul.

520
00:18:26,260 --> 00:18:26,945
Doi și trei.

521
00:18:26,945 --> 00:18:27,460
Trei și patru.

522
00:18:27,460 --> 00:18:28,310
Patru și cinci.

523
00:18:28,310 --> 00:18:28,620
Cinci și șase.

524
00:18:28,620 --> 00:18:30,510
Șase și șapte.

525
00:18:30,510 --> 00:18:31,880
Done?

526
00:18:31,880 --> 00:18:34,560
Deci, eu sunt, dar permiteți-mi să joace
avocatul diavolului.

527
00:18:34,560 --> 00:18:37,950
Eu, un fel de calculator, care tocmai
a făcut o trecere prin această serie de

528
00:18:37,950 --> 00:18:40,225
oameni, știu că am terminat?

529
00:18:40,225 --> 00:18:40,670
>> SPEAKER 1: Nu.

530
00:18:40,670 --> 00:18:41,050
>> David J. MALAN: Deci, de ce?

531
00:18:41,050 --> 00:18:46,900
Ce trebuie să fac pentru a
concluziona în mod decisiv că am terminat?

532
00:18:46,900 --> 00:18:48,230
Probabil o trecere mai.

533
00:18:48,230 --> 00:18:48,430
Dreapta?

534
00:18:48,430 --> 00:18:51,760
Pentru că tot ce știu de la care anterior
trecere este că am corectat o greșeală.

535
00:18:51,760 --> 00:18:53,920
Și asta înseamnă, poate exista
încă o altă greșeală

536
00:18:53,920 --> 00:18:54,840
pe care am nevoie pentru a corecta.

537
00:18:54,840 --> 00:18:58,680
Deci, eu pot fi doar sigur de depanare, și
apoi verificând, unul la doi, doi și

538
00:18:58,680 --> 00:19:00,940
trei, trei și patru, patru și cinci,
cinci și șase, șase și șapte.

539
00:19:00,940 --> 00:19:02,510
OK, acum am făcut nici o lucrare.

540
00:19:02,510 --> 00:19:05,990
>> Îmi amintesc cu siguranță că am făcut nici o
lucreze cu ceva ca o variabilă,

541
00:19:05,990 --> 00:19:06,975
ca un întreg.

542
00:19:06,975 --> 00:19:12,490
Spune-i swap-uri, și în cazul în care swap-uri este 0 după ce am
ajunge aici, și a început la 0, atunci

543
00:19:12,490 --> 00:19:15,520
Mi-ar fi o prostie să continui
înainte și înapoi, verificarea din nou, și

544
00:19:15,520 --> 00:19:16,450
din nou, și din nou, corect?

545
00:19:16,450 --> 00:19:18,450
Pentru că te-ai blocat în unele
un fel de buclă infinită.

546
00:19:18,450 --> 00:19:21,250
Asa ca imediat ce există 0 swap-uri,
putem afirma că această

547
00:19:21,250 --> 00:19:23,810
Algoritmul este într-adevăr complet.

548
00:19:23,810 --> 00:19:25,400
>> Acum, să punem un nume pe aceasta.

549
00:19:25,400 --> 00:19:28,930
Algoritmul pe care eu le propunem doar
implementat este ceva numit bule

550
00:19:28,930 --> 00:19:32,800
sortare, cunoscut ca atare, în sensul că
numerele care sunt un fel mai mari de

551
00:19:32,800 --> 00:19:37,990
bule modul lor de până la partea de sus, sau în sus
la sfârșitul matrice de numere.

552
00:19:37,990 --> 00:19:40,270
Dar cât de eficient a fost acest algoritm?

553
00:19:40,270 --> 00:19:44,600
Câți pași aveam fizic
ia, de exemplu, pentru a sorta aceste

554
00:19:44,600 --> 00:19:45,850
șapte oameni?

555
00:19:45,850 --> 00:19:48,560

556
00:19:48,560 --> 00:19:49,550
>> Patru la cinci?

557
00:19:49,550 --> 00:19:51,420
OK, prea multe este în cele din urmă
va fi răspunsul.

558
00:19:51,420 --> 00:19:54,960
Dar chiar și atunci, numărul specific
nu este atât de interesantă.

559
00:19:54,960 --> 00:19:56,670
Să-l ca n generaliza.

560
00:19:56,670 --> 00:20:00,520
Deci, dacă am fi n oameni aici, și ei
au fost, un fel de, în ordine aleatorie, la

561
00:20:00,520 --> 00:20:02,180
începând, în ordinea inițială.

562
00:20:02,180 --> 00:20:04,910
Ei bine, câți pași am avea
pentru a lua cu privire la prima trecere?

563
00:20:04,910 --> 00:20:09,810
Acesta a fost unul, doi, trei, patru, cinci,
șase, și sunt șapte persoane, astfel

564
00:20:09,810 --> 00:20:13,670
că e șapte, șase -, așa că e n
minus unul pașii pentru prima dată.

565
00:20:13,670 --> 00:20:16,280
>> Acum, câți pași am avea
pentru a lua atunci când am rebobinat?

566
00:20:16,280 --> 00:20:19,310
Ei bine, am putea dubla de fapt, că, dacă
Am vrut sa, dar de acum, eu sunt

567
00:20:19,310 --> 00:20:22,300
doar de gând să spun, bine,
încă n minus 1.

568
00:20:22,300 --> 00:20:25,240
Deci, n minus 1 este mergi la a lua
enervant pentru a urmări, asa ca hai sa

569
00:20:25,240 --> 00:20:26,400
adun ușor.

570
00:20:26,400 --> 00:20:27,770
Deci 2n pași.

571
00:20:27,770 --> 00:20:29,310
Deci 14 etape, da sau ia.

572
00:20:29,310 --> 00:20:31,930
>> De câte ori nu am luat
un pas data viitoare?

573
00:20:31,930 --> 00:20:33,740
Ei bine, e 3N.

574
00:20:33,740 --> 00:20:34,510
într-adevăr.

575
00:20:34,510 --> 00:20:37,920
Și acum, în cel mai rău caz, pentru
exemplu, de câte ori aș avea

576
00:20:37,920 --> 00:20:41,730
plecat înainte și înapoi, înainte și înapoi,
executarea acestui algoritm, schimbarea

577
00:20:41,730 --> 00:20:44,620
oamenii de pe fiecare trecere, aproximativ?

578
00:20:44,620 --> 00:20:47,720

579
00:20:47,720 --> 00:20:50,010
Este de fapt n pătrat, nu?

580
00:20:50,010 --> 00:20:53,000
>> Pentru că în cel mai rău caz, puteți fel
a gândi despre acest lucru intuitiv,

581
00:20:53,000 --> 00:20:54,800
chiar dacă s-ar putea să ia un pic
pic de timp să se scufunde inch

582
00:20:54,800 --> 00:20:57,590
În cel mai rău caz, ceea ce ar fi acestea
sapte persoane s-au uitat ca, în

583
00:20:57,590 --> 00:21:00,230
termenii acordului
de numerele lor?

584
00:21:00,230 --> 00:21:01,460
Complet înapoi, nu?

585
00:21:01,460 --> 00:21:02,815
Și doar pentru a simula că,
ceea ce a fost din nou numele tău?

586
00:21:02,815 --> 00:21:03,360
>> MIKE: Mike.

587
00:21:03,360 --> 00:21:03,640
>> David J. MALAN: Mike?

588
00:21:03,640 --> 00:21:08,100
Bine, Mike, poți să vii cu mine peste
aici pentru o secunda?

589
00:21:08,100 --> 00:21:08,880
De fapt, nu.

590
00:21:08,880 --> 00:21:10,150
Ne pare rău Mike, hai înapoi.

591
00:21:10,150 --> 00:21:10,910
Care e numele tău din nou?

592
00:21:10,910 --> 00:21:11,180
>> NEIL: Neil.

593
00:21:11,180 --> 00:21:11,640
>> David J. MALAN: Neil.

594
00:21:11,640 --> 00:21:13,750
OK, Neil, ai venit cu
ma, daca nu te superi.

595
00:21:13,750 --> 00:21:17,150
Așa că am de gând să propună, doar pentru
simplitate, că Neil este acum în balonul

596
00:21:17,150 --> 00:21:18,510
cel mai rău caz posibil.

597
00:21:18,510 --> 00:21:20,720
Dar amintesc cum am implementat
algoritmul meu.

598
00:21:20,720 --> 00:21:24,530
Am comparat, comparat, comparat,
compararea, compararea, oh.

599
00:21:24,530 --> 00:21:26,640
Acum, acești oameni sunt în afara
de ordine, așa că am rezolva.

600
00:21:26,640 --> 00:21:27,980
Deci, voi schimba.

601
00:21:27,980 --> 00:21:31,630
Dar ia în considerare acum, cât de mult mai departe
are Neil trebuie să te duci?

602
00:21:31,630 --> 00:21:32,690
Este aproximativ n.

603
00:21:32,690 --> 00:21:33,570
Știi, nu e de fapt n.

604
00:21:33,570 --> 00:21:36,040
E ca si cum, n minus 1, dar eu sunt obtinerea
urmări enervat păstrarea mic

605
00:21:36,040 --> 00:21:37,550
numărul, deci hai să spunem n.

606
00:21:37,550 --> 00:21:42,860
>> Deci, dacă Neil se mută cu un pas la maximum fiecare
timp, și pentru a muta Neil un pas,

607
00:21:42,860 --> 00:21:46,580
Trebuie să facă acest pas foarte plictisitor
înainte și înapoi, acest lucru este de aproximativ

608
00:21:46,580 --> 00:21:52,080
face acest lucru, n pași, un total de n ori,
pentru că o să mă ia

609
00:21:52,080 --> 00:21:55,820
că mulți pași pentru a obține Neil toate
modul de unde îi este locul.

610
00:21:55,820 --> 00:21:58,620
Să nu mai vorbim toți ceilalți dacă voi
au fost toate mis-a ordonat, de asemenea.

611
00:21:58,620 --> 00:22:01,100
>> Deci, sa-i spunem un fel bubble n pătrat.

612
00:22:01,100 --> 00:22:04,860
Timpul de funcționare a acestui algoritm,
performanța acestui algoritm,

613
00:22:04,860 --> 00:22:07,120
Eficiența acestui algoritm,
vom descrie doar mai mult

614
00:22:07,120 --> 00:22:08,800
în general, ca pătrat n.

615
00:22:08,800 --> 00:22:11,650
Ceea ce este frumos, pentru că am putea face
același exemplu cu opt oameni, nouă

616
00:22:11,650 --> 00:22:15,450
oameni, un milion de oameni, și că
Răspunsul nu se va schimba.

617
00:22:15,450 --> 00:22:18,870
>> Deci, dacă voi nu m-ar deranja, să
ați resetat de unde ai pornit.

618
00:22:18,870 --> 00:22:22,510
Și să încercăm alte două abordări și
a se vedea dacă nu putem face în mod fundamental

619
00:22:22,510 --> 00:22:23,820
mai bine decât aceasta.

620
00:22:23,820 --> 00:22:27,130
Deci, de data aceasta, am de gând să propună
un fel de algoritm diferit.

621
00:22:27,130 --> 00:22:29,950
Asta a fost foarte inteligent de noi data trecută,
și voi au dreptul de a avea

622
00:22:29,950 --> 00:22:32,470
instinctele corecte de doar un fel
de pompare perechi.

623
00:22:32,470 --> 00:22:36,500
Dar, dacă am vrut să abordeze această
pur și simplu, iar scopul meu este de a muta

624
00:22:36,500 --> 00:22:39,800
toate numerele mici în acest fel, și
împinge toate numerele mari care

625
00:22:39,800 --> 00:22:43,030
fel, de ce nu am face asta, în
cel mai naiv mod posibil și să văd dacă

626
00:22:43,030 --> 00:22:45,730
se poate face mai bine decât ceea ce a fost un
destul de algoritm complex?

627
00:22:45,730 --> 00:22:46,620
>> Deci, haideți să vedem.

628
00:22:46,620 --> 00:22:48,940
Patru este un număr destul de mic, așa că eu sunt
O să te las acolo moment.

629
00:22:48,940 --> 00:22:50,610
Ooh, numărul doi este chiar mai bine.

630
00:22:50,610 --> 00:22:52,230
Deci, poți să pas înainte
pentru o clipă?

631
00:22:52,230 --> 00:22:55,670
Aceasta este în prezent meu mai mic numerotate
candidat, și am de gând să-mi amintesc

632
00:22:55,670 --> 00:22:57,000
că cu, ca, o variabilă.

633
00:22:57,000 --> 00:22:57,930
Dar am de gând să păstreze controlul.

634
00:22:57,930 --> 00:22:59,890
Există cineva a cărui
Numărul este mai mic?

635
00:22:59,890 --> 00:23:00,460
Șase, nu.

636
00:23:00,460 --> 00:23:01,390
Oh, nu e din nou Neil.

637
00:23:01,390 --> 00:23:04,050
>> Așa că am de gând să te împinge înapoi
un fel de punct de vedere conceptual.

638
00:23:04,050 --> 00:23:05,120
Neil va veni înainte.

639
00:23:05,120 --> 00:23:08,440
Și acum, variabila pe care îl folosesc pentru a
ține evidența care are cea mai mică

640
00:23:08,440 --> 00:23:11,390
Numărul este actualizat pentru a conține
Locația lui Neil.

641
00:23:11,390 --> 00:23:12,110
Ei bine, să vedem.

642
00:23:12,110 --> 00:23:13,960
Trei, șapte, cinci.

643
00:23:13,960 --> 00:23:15,590
OK, știu că Neil era cel mai mic.

644
00:23:15,590 --> 00:23:18,110
Care este cel mai simplu lucru
pentru mine să fac acum?

645
00:23:18,110 --> 00:23:21,410
Eu nu am de gând să-mi pierd timpul cu doar
barbotare Neil un loc la stânga.

646
00:23:21,410 --> 00:23:25,350
De ce nu am pus doar Neil, unde a
îi aparține, care este, desigur, în cazul în care?

647
00:23:25,350 --> 00:23:26,160
>> Tot drumul de la început.

648
00:23:26,160 --> 00:23:27,720
Deci, Neil, vino cu mine.

649
00:23:27,720 --> 00:23:28,910
Și ce a fost din nou numele tău?

650
00:23:28,910 --> 00:23:29,310
>> GRACE: Grace.

651
00:23:29,310 --> 00:23:29,710
>> David J. MALAN: Grace.

652
00:23:29,710 --> 00:23:29,920
OK.

653
00:23:29,920 --> 00:23:32,490
Deci Grace, din păcate, tu ești
cam în mod.

654
00:23:32,490 --> 00:23:34,290
Deci, cum putem rezolva această problemă?

655
00:23:34,290 --> 00:23:34,490
Dreapta?

656
00:23:34,490 --> 00:23:37,500
Dacă aceasta este o matrice, există
doar șapte locuri.

657
00:23:37,500 --> 00:23:40,830
Amintiti-va ca, cu Rob, am vorbit despre
declararea vârstele, și am avut doar o

658
00:23:40,830 --> 00:23:41,740
număr finit de varsta?

659
00:23:41,740 --> 00:23:42,535
Aceeași idee aici.

660
00:23:42,535 --> 00:23:44,300
Avem doar un număr finit de int.

661
00:23:44,300 --> 00:23:47,590
Grace este un fel de la noi
Astfel, așa cum am rezolva?

662
00:23:47,590 --> 00:23:49,555
>> Cea mai simplă cale este ca,
Grace, îmi pare rău.

663
00:23:49,555 --> 00:23:51,870
Ai de gând să trebuie să treacă peste
acolo astfel încât să putem face loc.

664
00:23:51,870 --> 00:23:55,290
Acum, dacă te gândești la asta, poate
ne-am facut problema mai rău.

665
00:23:55,290 --> 00:23:58,510
Și poate că am făcut-o, pentru că ceea ce în cazul în care
Grace au fost în locul potrivit?

666
00:23:58,510 --> 00:24:01,730
Dar noi știm că nu e, pentru că
altfel, ar fi fost

667
00:24:01,730 --> 00:24:03,980
în picioare înainte în loc de
Neil la acest moment, nu?

668
00:24:03,980 --> 00:24:05,550
Am verificat deja numărul ei afară.

669
00:24:05,550 --> 00:24:05,770
>> Bine.

670
00:24:05,770 --> 00:24:09,110
Deci, acum, Neil este în locul potrivit, și
Pot face o optimizare ușoară.

671
00:24:09,110 --> 00:24:11,740
Pentru minutul următor, am de gând să ignore
Neil toate împreună, astfel încât să nu

672
00:24:11,740 --> 00:24:15,280
pierde timpul, sau accidental
schimba-l la locul nepotrivit.

673
00:24:15,280 --> 00:24:17,805
Deci, acum, cum pot găsi la următoarea
element care e mai mic?

674
00:24:17,805 --> 00:24:18,480
Două.

675
00:24:18,480 --> 00:24:20,225
Asta e un număr destul de bun, în cazul în care
pe care doriți să pas înainte și

676
00:24:20,225 --> 00:24:21,100
O să vă amintiți.

677
00:24:21,100 --> 00:24:21,980
Șase, nu bine.

678
00:24:21,980 --> 00:24:24,820
Patru, trei, șapte, cinci, nu e bine.

679
00:24:24,820 --> 00:24:26,800
Deci, permiteți-mi să vă mutați la
locul potrivit.

680
00:24:26,800 --> 00:24:28,470
Și am avut noroc de data asta.

681
00:24:28,470 --> 00:24:31,350
>> Acum, am de gând să ignore aceste
doi tipi, iar acum nu o mai

682
00:24:31,350 --> 00:24:32,260
trece prin aceasta.

683
00:24:32,260 --> 00:24:33,490
Șase, că un număr destul de mic.

684
00:24:33,490 --> 00:24:34,300
Haide înainte.

685
00:24:34,300 --> 00:24:35,220
Oh, îmi pare rău.

686
00:24:35,220 --> 00:24:37,640
Numărul harul este mai bine,
așa pas pe mai departe.

687
00:24:37,640 --> 00:24:38,260
Patru.

688
00:24:38,260 --> 00:24:39,120
Îmi pare rău, Grace.

689
00:24:39,120 --> 00:24:39,950
Du-te înapoi din nou.

690
00:24:39,950 --> 00:24:41,550
Numarul trei este mai bine.

691
00:24:41,550 --> 00:24:42,290
Șapte.

692
00:24:42,290 --> 00:24:42,720
Cinci.

693
00:24:42,720 --> 00:24:43,550
Și acum, ce e numele tău din nou?

694
00:24:43,550 --> 00:24:44,000
>> JASON: Jason.

695
00:24:44,000 --> 00:24:44,420
>> David J. MALAN: Jason.

696
00:24:44,420 --> 00:24:47,050
Deci, Jason este acum cel mai mic
Elementul am selectat.

697
00:24:47,050 --> 00:24:49,160
Unde se duc?

698
00:24:49,160 --> 00:24:50,380
Deci, unde șase este.

699
00:24:50,380 --> 00:24:51,210
Si numele tau este din nou?

700
00:24:51,210 --> 00:24:51,710
>> GABE: Gabe.

701
00:24:51,710 --> 00:24:52,340
>> David J. MALAN: Gabe.

702
00:24:52,340 --> 00:24:53,220
Gabe este în mod.

703
00:24:53,220 --> 00:24:54,640
Care este cel mai ușor lucru de făcut?

704
00:24:54,640 --> 00:24:58,390
Swap doi tipi și continuă.

705
00:24:58,390 --> 00:24:59,020
Deci, acum să vedem.

706
00:24:59,020 --> 00:25:00,170
Cine este cel mai mic?

707
00:25:00,170 --> 00:25:01,030
Patru.

708
00:25:01,030 --> 00:25:01,990
Permiteți-mi doar un fel de ieftin.

709
00:25:01,990 --> 00:25:03,090
Cinci va fi mai mic.

710
00:25:03,090 --> 00:25:05,220
Mi se pare viitoare, în cazul în care, vrei să-și intensifice
înainte, ce trebuie să fac cu

711
00:25:05,220 --> 00:25:06,820
acesti baieti, cu Gabe?

712
00:25:06,820 --> 00:25:08,450
Swap din nou.

713
00:25:08,450 --> 00:25:10,740
Deci, acum, încă ușor de ordine.

714
00:25:10,740 --> 00:25:14,140
Am găsit Gabe este cel mai mic, astfel încât
L-am ieși, muta voi peste.

715
00:25:14,140 --> 00:25:15,190
Și făcut.

716
00:25:15,190 --> 00:25:17,200
>> Deci răspunsul este același.

717
00:25:17,200 --> 00:25:18,600
Rezultatul final este același.

718
00:25:18,600 --> 00:25:22,730
Care dintre aceste două algoritmi
este mai bine?

719
00:25:22,730 --> 00:25:23,500
A doua, am auzit.

720
00:25:23,500 --> 00:25:24,252
De ce?

721
00:25:24,252 --> 00:25:25,900
>> SPEAKER 3: Este n pași [inaudibil].

722
00:25:25,900 --> 00:25:27,600
>> David J. MALAN: Este pași n cel mult.

723
00:25:27,600 --> 00:25:28,490
Interesant.

724
00:25:28,490 --> 00:25:30,610
Deci, este totuși?

725
00:25:30,610 --> 00:25:33,630
Deci, cum am găsi
mic element?

726
00:25:33,630 --> 00:25:37,060
Cati pasi a trebuit să ia
găsi cel mai mic element?

727
00:25:37,060 --> 00:25:39,220
Am avut o privire tot drumul
la final, nu?

728
00:25:39,220 --> 00:25:41,530
Deoarece în care cel mai rău caz, ceea ce
dacă Neil s-au terminat aici?

729
00:25:41,530 --> 00:25:45,700
Deci, doar a găsi cel mai mic element
ia-ma n trepte, sau n minus 1.

730
00:25:45,700 --> 00:25:46,100
Dar, OK.

731
00:25:46,100 --> 00:25:46,980
Deci repara Neil.

732
00:25:46,980 --> 00:25:48,740
Amintiți-vă că, un minut sau cam asa ceva în urmă.

733
00:25:48,740 --> 00:25:51,680
>> Dar cum am găsit următoarea
mic element?

734
00:25:51,680 --> 00:25:54,830
Este n minus 1, sau n minus 2 într-adevăr,
din numărul de pași.

735
00:25:54,830 --> 00:25:55,440
Deci OK.

736
00:25:55,440 --> 00:25:57,390
Așa că am făcut n minus 2.

737
00:25:57,390 --> 00:25:57,600
Bine.

738
00:25:57,600 --> 00:25:59,130
Astfel că se simte un pic mai bine.

739
00:25:59,130 --> 00:25:59,730
Bine.

740
00:25:59,730 --> 00:26:03,270
Câți pași data viitoare
pentru a găsi numărul trei?

741
00:26:03,270 --> 00:26:04,420
Deci n minus 4.

742
00:26:04,420 --> 00:26:07,670
Deci, este în scădere, una mai
pas la fiecare iterație.

743
00:26:07,670 --> 00:26:08,740
Deci, acest lucru se simte mai bine, nu?

744
00:26:08,740 --> 00:26:13,450
În cazul în care ultima data a fost de aproximativ n ori n,
de data aceasta n minus 1, plus n minus

745
00:26:13,450 --> 00:26:16,500
2, n plus minus 3, plus n
minus 4, punct, punct, punct.

746
00:26:16,500 --> 00:26:18,750
Dar, dacă vă amintiți de la liceu
manuale, mic cheat

747
00:26:18,750 --> 00:26:24,380
foaie la spate care are formule, dacă
să adăugați la această serie de numere,

748
00:26:24,380 --> 00:26:31,280
ceea ce este numărul total de etape
O să fie ca iau aici?

749
00:26:31,280 --> 00:26:36,580
>> Acesta este unul dintre cei care, ca, n minus
1, ori n, împărțit la 2.

750
00:26:36,580 --> 00:26:39,040
Deci, lasă-mă să văd dacă pot trage
asta doar pentru o clipă.

751
00:26:39,040 --> 00:26:42,230
Și din nou, eu sunt un fel de rotunjire unor
Numerele doar pentru a menține viața noastră simplă,

752
00:26:42,230 --> 00:26:47,830
dar din cate imi amintesc, e ceva de genul dacă
Eu fac n minus 1 lucruri, atunci n minus

753
00:26:47,830 --> 00:26:53,570
2, atunci n minus 3, este aproximativ
ceva de genul asta de peste 2, și dacă am

754
00:26:53,570 --> 00:26:55,510
multiplica acest lucru, că este
de fapt n pătrat.

755
00:26:55,510 --> 00:26:58,940
Asta nu se simte prea bine.
n minus n peste 2.

756
00:26:58,940 --> 00:27:00,350
>> Dar aici e de lucru.

757
00:27:00,350 --> 00:27:03,720
În informatică, atunci când problemele
începe pentru a obține interesant este atunci când n

758
00:27:03,720 --> 00:27:04,700
devine foarte mare.

759
00:27:04,700 --> 00:27:08,110
Și când n devine foarte mare, care a
aceste valori se va domina toate

760
00:27:08,110 --> 00:27:09,750
de ceilalți?

761
00:27:09,750 --> 00:27:10,990
Este un fel de n pătrat, nu?

762
00:27:10,990 --> 00:27:13,340
Da, împărțind cu 2 este destul de bun.

763
00:27:13,340 --> 00:27:16,740
Dar dacă vorbim despre miliarde
de fragmente de date, sau trilioane de

764
00:27:16,740 --> 00:27:18,700
piese de date, OK,
ești de două ori mai repede.

765
00:27:18,700 --> 00:27:22,440
Dar care într-adevăr îi pasă dacă acest număr mare,
dacă acest factor este ceea ce devine

766
00:27:22,440 --> 00:27:23,040
mai mare și mai mare.

767
00:27:23,040 --> 00:27:25,990
Și cu siguranță, face mai mult de
o diferență de acest tip.

768
00:27:25,990 --> 00:27:29,120
Deci, chiar dacă voi dreptate,
algoritm al doilea rând, vom numi

769
00:27:29,120 --> 00:27:32,970
un fel de selecție, este, în lumea reală, o
bit mai repede posibil, pentru că eu sunt

770
00:27:32,970 --> 00:27:35,360
având mai puține și mai puține
pași de fiecare dată.

771
00:27:35,360 --> 00:27:37,340
>> Nu este într-adevăr fundamental mai repede.

772
00:27:37,340 --> 00:27:41,430
Pentru că dacă vom juca de fapt acest lucru pentru
valori mari ale lui n, la sfârșitul

773
00:27:41,430 --> 00:27:44,750
a doua zi, de mare n suficient, este încă
de gând să se simtă destul de lent.

774
00:27:44,750 --> 00:27:46,770
Ei bine, lasă-mă să iau un
trecere trecut la asta.

775
00:27:46,770 --> 00:27:48,920
Asta e ceea ce aș numi
un fel de selecție.

776
00:27:48,920 --> 00:27:51,040
Poate voi putea suporta singuri
pentru ultima oară?

777
00:27:51,040 --> 00:27:53,550
Și în acest ultim caz, am de gând
să propună ceva

778
00:27:53,550 --> 00:27:54,970
numit un fel de inserare.

779
00:27:54,970 --> 00:27:57,470
Un fel de inserare fiind, conceptual,
un pic diferit.

780
00:27:57,470 --> 00:28:00,980
>> Mai degrabă decât a merge înainte și înapoi și
selectarea cel mai mic element, sunt

781
00:28:00,980 --> 00:28:05,030
doar de gând să se ocupe cu fiecare dintre aceste
baieti ca le-am întâlni, și introduceți

782
00:28:05,030 --> 00:28:06,850
le în locul lor corecta.

783
00:28:06,850 --> 00:28:10,160
Deci, eu sunt doar de gând să înceapă cu Grace,
și văd că e numărul patru.

784
00:28:10,160 --> 00:28:11,720
În cazul în care este numărul patru aparține?

785
00:28:11,720 --> 00:28:14,940
Nu am început sortarea nimic,
Deci harul ajunge să stai acolo.

786
00:28:14,940 --> 00:28:18,355
Și acum am de gând să solicite, dacă ai putea
ia un pas la dreapta ta, acest lucru

787
00:28:18,355 --> 00:28:21,650
Lista mea de sortat, acest lucru este meu
lista rămasă nesortate.

788
00:28:21,650 --> 00:28:23,260
Așa că acum am de gând să procedeze viitor,
și ceea ce este numele tau din nou?

789
00:28:23,260 --> 00:28:23,700
>> BRANSON: Branson.

790
00:28:23,700 --> 00:28:24,150
>> David J. MALAN: Branson.

791
00:28:24,150 --> 00:28:25,375
Deci, Branson este numărul doi.

792
00:28:25,375 --> 00:28:27,490
Așa că am de gând să vă luați
pentru o clipă.

793
00:28:27,490 --> 00:28:30,940
Și acum, unde ți-e locul
în acest tablou?

794
00:28:30,940 --> 00:28:32,360
Deci, pentru dreptul de Grace.

795
00:28:32,360 --> 00:28:35,670
Deci, din nou, suntem un fel de a face
Grace face o mulțime de muncă aici.

796
00:28:35,670 --> 00:28:37,290
Unde ne-ai pus?

797
00:28:37,290 --> 00:28:40,120
Așa că am de gând să vă deplasați la
a plecat, și introduceți Branson acolo.

798
00:28:40,120 --> 00:28:41,680
Dar acum eu susțin că
voi terminat.

799
00:28:41,680 --> 00:28:43,240
Dar preaviz, eu nu folosesc spațiu suplimentar.

800
00:28:43,240 --> 00:28:45,130
Este încă 2 elemente
aici, 5 aici.

801
00:28:45,130 --> 00:28:47,910
Dimensiunea totală matrice este 7, așa că eu sunt
nu inseala, bine?

802
00:28:47,910 --> 00:28:51,950
>> Deci, acum avem, cu Gabe aici,
număr de șase, unde ți-e locul?

803
00:28:51,950 --> 00:28:52,650
Ai din nou noroc.

804
00:28:52,650 --> 00:28:53,820
Astfel încât să obțineți pentru a rămâne acolo.

805
00:28:53,820 --> 00:28:57,210
Doar să ia o ușoară pas la dreapta
doar pentru a face clar că ai sortat.

806
00:28:57,210 --> 00:29:00,520
Și acum avem Neil nou, numărul
unul, unde te duci?

807
00:29:00,520 --> 00:29:03,540
Și acum este în cazul în care vom începe să vedem că
acest algoritm, deși la prima

808
00:29:03,540 --> 00:29:05,950
vedere, se simte destul de inteligent, ceas
ce e pe cale să se întâmple.

809
00:29:05,950 --> 00:29:07,370
Dacă ați putea pas înainte.

810
00:29:07,370 --> 00:29:09,260
>> În cazul în care vrem să Neil?

811
00:29:09,260 --> 00:29:11,830
Deci, evident aici, așa cum
ajungem Neil acolo?

812
00:29:11,830 --> 00:29:12,970
Să facem acest pas-cu-pas.

813
00:29:12,970 --> 00:29:15,620
Gabe, în cazul în care aveți nevoie pentru a merge?

814
00:29:15,620 --> 00:29:19,590
Da, astfel încât să ia un pas mare,
sau două jumătăți de măsuri pentru a face

815
00:29:19,590 --> 00:29:20,820
un pas de acolo.

816
00:29:20,820 --> 00:29:21,750
Grace, unde te duci?

817
00:29:21,750 --> 00:29:22,510
Bun.

818
00:29:22,510 --> 00:29:23,500
Deci, un alt pas.

819
00:29:23,500 --> 00:29:24,960
Și, în sfârșit, Branson?

820
00:29:24,960 --> 00:29:25,460
Un alt pas.

821
00:29:25,460 --> 00:29:27,190
Și acum putem pune Neil în loc.

822
00:29:27,190 --> 00:29:28,440
>> Deci, acum, continua această logică.

823
00:29:28,440 --> 00:29:32,420
Chiar dacă nu se schimbă Neil
peste, si peste, si peste, să-l pună

824
00:29:32,420 --> 00:29:36,420
unde se duce, în cel mai rău caz,
Numărul următor am putea întâlni putea

825
00:29:36,420 --> 00:29:42,220
fie numărul, spune, a existat un număr
zero, atunci vom schimba toate

826
00:29:42,220 --> 00:29:42,730
tipii ăștia.

827
00:29:42,730 --> 00:29:44,950
Să presupunem că există un număr, negativ
una, atunci avem de a schimba

828
00:29:44,950 --> 00:29:46,080
toate aceste baieti.

829
00:29:46,080 --> 00:29:48,500
Deci, suntem într-adevăr doar un fel de flipping
problema în jurul, astfel încât suntem

830
00:29:48,500 --> 00:29:52,620
transferarea cheltuiala de
Procesul de selecție astfel inserție

831
00:29:52,620 --> 00:29:56,930
proces, astfel că voi a avut doar
să se mute aproximativ n minus ceva

832
00:29:56,930 --> 00:29:57,940
număr de pași.

833
00:29:57,940 --> 00:30:01,200
Și că numărul de pași este doar de gând
să crească așa cum am selecta mai multe numere,

834
00:30:01,200 --> 00:30:04,730
dacă trebuie să țină împinge voi
înapoi, și înapoi, și înapoi.

835
00:30:04,730 --> 00:30:08,320
>> Deci, lucru trist este acum toate acestea
algoritmi sunt n pătrat.

836
00:30:08,320 --> 00:30:10,570
Să mergem mai departe și datorită acestor
baieti, si sa vizualizeze acestea un pic

837
00:30:10,570 --> 00:30:11,090
diferit.

838
00:30:11,090 --> 00:30:12,312
Foarte bine facut.

839
00:30:12,312 --> 00:30:14,120
>> [Aplauze]

840
00:30:14,120 --> 00:30:15,030
>> Bine.

841
00:30:15,030 --> 00:30:16,280
Acolo te duci.

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
Vă mulțumim pentru -

844
00:30:18,470 --> 00:30:19,190
>> BRANSON: [inaudibil] păstra numerele.

845
00:30:19,190 --> 00:30:21,990
>> David J. MALAN: Nu, s-ar putea
păstra numerele de asemenea.

846
00:30:21,990 --> 00:30:23,440
Bine.

847
00:30:23,440 --> 00:30:24,100
Bine făcut.

848
00:30:24,100 --> 00:30:25,300
Bine.

849
00:30:25,300 --> 00:30:30,510
Așa că haideți să vedem dacă nu putem acum rezuma
mai rapid, și mai vizual,

850
00:30:30,510 --> 00:30:33,410
exact ceea ce sa întâmplat
aici după cum urmează.

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
Am de gând să merg mai departe
și trage Firefox.

853
00:30:38,770 --> 00:30:41,310
Vom lega această demonstrație
pe site-ul cursului.

854
00:30:41,310 --> 00:30:43,870
Java este un pic enervant pentru a obține de lucru
în unele browsere in aceste zile.

855
00:30:43,870 --> 00:30:46,760
Deci, dacă te joci cu acest lucru la domiciliu,
dai seama ca ar putea avea nevoie să utilizați Firefox

856
00:30:46,760 --> 00:30:47,990
să-l de lucru.

857
00:30:47,990 --> 00:30:50,440
Și ceea ce am de gând să fac cu acest
Demonstrația este următoarea.

858
00:30:50,440 --> 00:30:54,875
>> În partea de jos, am o grămadă de
opțiuni de meniu, inclusiv un început și un

859
00:30:54,875 --> 00:30:55,840
butonul de oprire.

860
00:30:55,840 --> 00:30:59,450
De asemenea, ca o parte, se pare că există un
bug în aceste programe, prin care

861
00:30:59,450 --> 00:31:03,720
nu se poate vedea, de fapt, de început sau
Butonul dacă nu vă țineți de comandă sau Alt

862
00:31:03,720 --> 00:31:06,560
plus și zoom in, care curios,
vă arată mai multe butoane.

863
00:31:06,560 --> 00:31:09,090
Deci, doar FYI, dacă joci
cu acest lucru la domiciliu.

864
00:31:09,090 --> 00:31:12,870
Acum am de gând să faceți clic pe Start în doar o
clipă, după care specifică o întârziere de,

865
00:31:12,870 --> 00:31:16,810
cum ar fi, de 200 de milisecunde aici, doar
astfel încât să putem vedea ce se întâmplă.

866
00:31:16,810 --> 00:31:20,180
>> Deci, eu susțin că aceasta este o vizualizare
a primului algoritm

867
00:31:20,180 --> 00:31:23,730
tipii ăștia a făcut, un fel balon, prin care
am schimbat oamenii pe perechi.

868
00:31:23,730 --> 00:31:27,490
Perspectiva cheie în această vizualizare
este că înălțimea barelor

869
00:31:27,490 --> 00:31:30,510
reprezintă mărimea numărului.

870
00:31:30,510 --> 00:31:32,210
Deci, mai inalt bar,
mai mare număr.

871
00:31:32,210 --> 00:31:33,680
Mai scurt bara, mai mic numărul.

872
00:31:33,680 --> 00:31:38,630
Și dacă observați, vom merge prin
prima iterație a acestui algoritm,

873
00:31:38,630 --> 00:31:42,620
schimbarea numerelor mari și mici, astfel încât
numărul mic este pe primul loc și

874
00:31:42,620 --> 00:31:44,280
numărul mare merge spre dreapta.

875
00:31:44,280 --> 00:31:48,770
>> Și, de îndată ce ajungem la sfârșitul anului matrice
de mai multe numere de șapte, suntem

876
00:31:48,770 --> 00:31:49,900
merge înapoi la început.

877
00:31:49,900 --> 00:31:51,140
Și anticipa acest lucru.

878
00:31:51,140 --> 00:31:54,860
Pe extrema stângă, că micuțul va
a schimba la o parte, și această

879
00:31:54,860 --> 00:31:56,010
procesul se repetă.

880
00:31:56,010 --> 00:31:59,450
Acum, această vizualizare devine rapid
plictisitor, asa ca lasa-mă să merg mai departe și se va opri

881
00:31:59,450 --> 00:32:04,170
l, schimba ceva întârziere mult
mai repede doar pentru a obține acum, o simt pentru

882
00:32:04,170 --> 00:32:05,060
acest algoritm.

883
00:32:05,060 --> 00:32:07,840
>> Deci, chiar dacă l-am accelerat, acest lucru este
cum ar fi modernizarea procesor mea, cumpărare

884
00:32:07,840 --> 00:32:08,580
un nou calculator.

885
00:32:08,580 --> 00:32:12,980
Nu m-am schimbat fundamental meu
algoritm, dar puteți vedea într-adevăr mai mult

886
00:32:12,980 --> 00:32:16,800
clar decât cu oamenii, că mare
Numerele sunt bule până la partea de sus,

887
00:32:16,800 --> 00:32:20,900
și cifrele mici sunt barbotarea
până la fund.

888
00:32:20,900 --> 00:32:22,390
Iar acum acest lucru aici sortat.

889
00:32:22,390 --> 00:32:25,260
Și, ca o paranteză, în piețe, există
doar câteva contabilitate acolo pentru a

890
00:32:25,260 --> 00:32:28,010
ajuta să conta cât de multe comparații,
sau cât de multe swap-uri au

891
00:32:28,010 --> 00:32:28,950
de fapt, sa făcut.

892
00:32:28,950 --> 00:32:30,750
>> Ei bine, hai sa incercam unul din
ceilalți am văzut.

893
00:32:30,750 --> 00:32:37,116
Permiteți-mi să faceți clic pe un fel bule aici, și
lasă-mă să aleg, iar aceasta pagina web tot

894
00:32:37,116 --> 00:32:38,936
este un pic buggy.

895
00:32:38,936 --> 00:32:41,155
Să accepte riscul
și executați din nou.

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
Acolo mergem.

898
00:32:45,030 --> 00:32:47,180
Deci, haideți să facem un fel de selecție.

899
00:32:47,180 --> 00:32:49,140
Nu știu de ce meniul
apare acolo.

900
00:32:49,140 --> 00:32:54,070
Să zoom în a stabili care
bug-ul, schimba aceasta la 50.

901
00:32:54,070 --> 00:32:56,020
Ah, hai să facem de fapt
că mult mai rapid.

902
00:32:56,020 --> 00:32:59,160
Cinci milisecunde sau cam asa ceva, și să înceapă.

903
00:32:59,160 --> 00:33:00,470
>> Deci, aceasta este un fel de selecție.

904
00:33:00,470 --> 00:33:03,070
Deci, din nou, cred despre ceea ce am
a făcut cu oamenii de aici.

905
00:33:03,070 --> 00:33:08,490
Am trecut prin matrice și selectat
cel mai mic element din nou,

906
00:33:08,490 --> 00:33:09,250
și din nou, și din nou.

907
00:33:09,250 --> 00:33:11,110
Acum, eu pretind că era încă destul de rău.

908
00:33:11,110 --> 00:33:15,010
Acesta a fost încă n patrat, da sau de a lua,
dar a fost, în lumea reală, un pic

909
00:33:15,010 --> 00:33:18,280
mai repede, pentru că am fost într-adevăr a lua
ușor mai puține etape de fiecare dată.

910
00:33:18,280 --> 00:33:19,800
Dar vorbim doar ce?

911
00:33:19,800 --> 00:33:21,830
Poate 40 sau cam asa ceva baruri aici?

912
00:33:21,830 --> 00:33:23,200
Nu vorbim de 40 de milioane.

913
00:33:23,200 --> 00:33:27,430
Deci, nu este clar în totalitate la mine că
a fost într-adevăr un câștig semnificativ.

914
00:33:27,430 --> 00:33:32,530
>> Lasă-mă să mă întorc și să modificați la noastre
treilea algoritm, care a fost selectați

915
00:33:32,530 --> 00:33:33,180
un fel de inserare.

916
00:33:33,180 --> 00:33:36,380
Și acum este într-adevăr buggy, deoarece
Meniul într-adevăr nu ar trebui să fie acolo.

917
00:33:36,380 --> 00:33:40,840
Deci, acum vom derula înapoi aici
și de a începe acest algoritm.

918
00:33:40,840 --> 00:33:43,270
Tuși, porni și opri.

919
00:33:43,270 --> 00:33:47,160
Deci, aceasta un fel de are un model destul de
să-l, prin care suntem din nou

920
00:33:47,160 --> 00:33:50,240
inserarea om, sau în
acest caz, barele în

921
00:33:50,240 --> 00:33:52,620
locația corespunzătoare a acestora.

922
00:33:52,620 --> 00:33:55,430
Și este deja făcut înainte
M-am întors.

923
00:33:55,430 --> 00:33:58,940
Dar aceasta, de asemenea, în teorie,
este încă n pătrat.

924
00:33:58,940 --> 00:34:01,430
>> Așa că haideți să vedem dacă nu putem rezuma
acestea, după cum urmează.

925
00:34:01,430 --> 00:34:04,750
Am de gând să merg mai departe și doar pentru a da
ne un fel de mod comun de a vorbi

926
00:34:04,750 --> 00:34:08,489
despre aceste lucruri, permiteți-mi să introducă
doar un pic de notație aici.

927
00:34:08,489 --> 00:34:12,480
Esti pe cale de a vedea ceva numit mare
O, pentru că este pur și simplu o mare

928
00:34:12,480 --> 00:34:16,320
O. Și acesta este un mod care un calculator
om de stiinta sau un matematician chiar folosește

929
00:34:16,320 --> 00:34:19,230
pentru a descrie timpul de execuție
de unele algoritm.

930
00:34:19,230 --> 00:34:21,400
Câți pași nu-l ia de fapt?

931
00:34:21,400 --> 00:34:25,080
>> Acum am de gând să mă face de râs cu
scrisul meu aici, în doar o clipă.

932
00:34:25,080 --> 00:34:29,020
Dar lasă-mă să merg mai departe și spune că
acest lucru va fi mare O aici.

933
00:34:29,020 --> 00:34:33,610
Și permiteți-mi să introducă un alt
simbol, un omega de capital.

934
00:34:33,610 --> 00:34:37,080
Omega va fi opusul,
în esență, de mare O. întrucât Big O

935
00:34:37,080 --> 00:34:40,790
înseamnă, în cel mai rău caz, cât de mult timp
ar putea un algoritm ia, în

936
00:34:40,790 --> 00:34:43,480
termeni de n, omega va
fi cât de mult timp s-ar putea

937
00:34:43,480 --> 00:34:45,409
ia, în cel mai bun caz.

938
00:34:45,409 --> 00:34:48,090
Și vom vedea ce se înțelege prin
cel mai bun caz, într-o clipă.

939
00:34:48,090 --> 00:34:49,940
>> Așa că haideți să începem ceva simplu.

940
00:34:49,940 --> 00:34:54,719
Permiteți-mi să încep cu o căutare liniară.

941
00:34:54,719 --> 00:34:55,679
Deci, nu de sortare.

942
00:34:55,679 --> 00:34:58,000
Vom numi această căutare liniară.

943
00:34:58,000 --> 00:35:01,140
Și acum, face un pic
Tabelul din acest.

944
00:35:01,140 --> 00:35:06,600
Și acum, în cazul de căutare liniară,
în cel mai rău caz, cât de multe etape este

945
00:35:06,600 --> 00:35:11,770
merge să mă ia pentru a găsi o
Numărul de alegere arbitrară?

946
00:35:11,770 --> 00:35:14,540
Și există uși Total N
sau n numere totale.

947
00:35:14,540 --> 00:35:15,940
Cel mai rău caz.

948
00:35:15,940 --> 00:35:18,800
Câți pași am de gând să trebuie să
ia de a găsi numărul 50 într-o matrice

949
00:35:18,800 --> 00:35:20,830
de n uși?

950
00:35:20,830 --> 00:35:21,410
Și de ce?

951
00:35:21,410 --> 00:35:23,680
Deoarece ar putea fi tot
mult peste pe final.

952
00:35:23,680 --> 00:35:27,120
Atât de mult ca Jennifer întâlnite,
Numărul 50 a fost tot drumul peste, astfel încât, în

953
00:35:27,120 --> 00:35:30,760
cel mai rău caz de căutare liniară
este mare O, de n, vom spune.

954
00:35:30,760 --> 00:35:33,430
>> Ce despre cel mai bun caz,
dacă aveți într-adevăr norocos?

955
00:35:33,430 --> 00:35:36,200
Este doar de gând să ia un pas,
sau un număr constant de pași.

956
00:35:36,200 --> 00:35:37,830
Deci, vom descrie ca ca 1.

957
00:35:37,830 --> 00:35:39,010
Deci, acest lucru este destul de bun.

958
00:35:39,010 --> 00:35:41,210
Acum, ce dacă am făcut ceva
cum ar fi căutare binar?

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
De căutare, astfel binar, în cel mai rău
caz, a luat cât de mult timp?

961
00:35:47,846 --> 00:35:49,250
>> [Interpune VOCI]

962
00:35:49,250 --> 00:35:51,310
>> David J. MALAN: Deci, de fapt, am
auzit-o în câteva locuri.

963
00:35:51,310 --> 00:35:56,390
Deci, de fapt log n, da sau de a lua,
pentru că așa cum am împărți lista de la jumătate

964
00:35:56,390 --> 00:36:00,730
din nou, și din nou, și din nou, suntem capabili
pentru a găsi, în cele din urmă, valoarea,

965
00:36:00,730 --> 00:36:04,750
daca e acolo, dar există o captură.

966
00:36:04,750 --> 00:36:08,590
Ce-i de la premisa că trebuie să
ia pentru a acordat pentru căutarea binar?

967
00:36:08,590 --> 00:36:09,700
Ea trebuie să fie sortate.

968
00:36:09,700 --> 00:36:12,770
Nu este sortat, puteți împărți lucrul
în jumătate din nou și din nou, și tu

969
00:36:12,770 --> 00:36:15,490
pot merge la stânga, și puteți merge drept, și
poti sa te duci la stânga și la dreapta, dar tu esti

970
00:36:15,490 --> 00:36:18,070
Nu merge pentru a găsi elementul dacă
lista nu este sortată, deoarece

971
00:36:18,070 --> 00:36:18,790
s-ar putea dor de ea.

972
00:36:18,790 --> 00:36:22,120
Deoarece euristică dvs., pentru a merge la stânga
sau drept va fi eronată, dacă este

973
00:36:22,120 --> 00:36:23,420
într-adevăr nu sortat.

974
00:36:23,420 --> 00:36:26,110
Deci, există un fel de cost ascuns
de a folosi ceva de genul asta.

975
00:36:26,110 --> 00:36:29,250
>> Acum, să mergem în sortarea nostru
algoritmi nu caută -

976
00:36:29,250 --> 00:36:31,140
oh, de fapt, să mergem în acest gol.

977
00:36:31,140 --> 00:36:33,190
Binar de căutare în cel mai bun caz?

978
00:36:33,190 --> 00:36:36,290
Este, de asemenea, 1 în cazul în care se întâmplă să fie
în foarte mijlocul matrice, sau

979
00:36:36,290 --> 00:36:37,810
mijlocul de cartea de telefon.

980
00:36:37,810 --> 00:36:39,710
Acum, hai să facem un fel bule.

981
00:36:39,710 --> 00:36:42,570
Deci, din nou, acum intrăm
felul, nu de căutări.

982
00:36:42,570 --> 00:36:47,220
>> În cel mai rău caz, câți pași am făcut
cerere bule de sortare va lua?

983
00:36:47,220 --> 00:36:48,410
n patrat.

984
00:36:48,410 --> 00:36:49,200
Așa că am de gând să atragă asta.

985
00:36:49,200 --> 00:36:51,710
Ooh, scrisul meu arata chiar mai rău
atunci când este proiectat atât de mare.

986
00:36:51,710 --> 00:36:52,510
Bine.

987
00:36:52,510 --> 00:36:53,570
Deci asta este n pătrat.

988
00:36:53,570 --> 00:36:59,460
Și, în cel mai bun caz de fel de bule,
câți pași este de gând să ia?

989
00:36:59,460 --> 00:37:00,980
1, am auzit.

990
00:37:00,980 --> 00:37:01,760
>> SPEAKER 1: n.

991
00:37:01,760 --> 00:37:03,286
>> David J. MALAN: N-am auzit.

992
00:37:03,286 --> 00:37:04,200
>> DIFUZOR 1: 2.

993
00:37:04,200 --> 00:37:05,010
>> David J. MALAN: 2, am auzit.

994
00:37:05,010 --> 00:37:06,670
Am auzit 3?

995
00:37:06,670 --> 00:37:07,080
Bine.

996
00:37:07,080 --> 00:37:11,390
Așa am auzit 1, n, 2, dar să alegeți
în afară cel puțin primul dintre cele

997
00:37:11,390 --> 00:37:12,330
sugestii, 1.

998
00:37:12,330 --> 00:37:15,370
Nu e un instinct rău, pentru că
un fel de urmează un model aici.

999
00:37:15,370 --> 00:37:19,670
Dar dacă este nevoie de doar un pas, cum în
Lumea aș putea pretinde că lista

1000
00:37:19,670 --> 00:37:22,900
este sortat, pentru că dacă eu sunt doar permis
să ia 1 pas, cât de multe elemente

1001
00:37:22,900 --> 00:37:25,230
aș putea chiar verifica pentru a fi sigur?

1002
00:37:25,230 --> 00:37:28,270
Ei bine, doar 1, ceea ce înseamnă că există n
minus 1 elemente care ar putea fi de

1003
00:37:28,270 --> 00:37:31,310
ordine, și Mă duc la credință, după
uită la 1 element care

1004
00:37:31,310 --> 00:37:31,850
lucru este sortat.

1005
00:37:31,850 --> 00:37:33,930
Deci 1 nu este corect aici.

1006
00:37:33,930 --> 00:37:35,710
Deci, minim, câte
trebuie să mă uit la?

1007
00:37:35,710 --> 00:37:36,680
>> [Interpune VOCI]

1008
00:37:36,680 --> 00:37:40,160
>> David J. MALAN: n minus 1, sau într-adevăr,
n, pentru că am nevoie să se uite la fiecare

1009
00:37:40,160 --> 00:37:42,190
Elementul să vă asigurați că
nu este în ordine.

1010
00:37:42,190 --> 00:37:44,750
Dar, din nou, vom rezolva de val nostru
mâinile la numerele mai mici și

1011
00:37:44,750 --> 00:37:47,100
presupune că, așa cum n devine mare, sunt
neinteresante oricum.

1012
00:37:47,100 --> 00:37:48,380
Deci, asta e un fel balon.

1013
00:37:48,380 --> 00:37:49,830
Și acum, hai sa facem aceste ultimele două.

1014
00:37:49,830 --> 00:37:53,520
Un fel de selecție, iar apoi vom
face un fel de inserare.

1015
00:37:53,520 --> 00:37:57,160
Și apoi vom sufla dvs.
mintea cu ceva mult

1016
00:37:57,160 --> 00:37:58,926
mai bine decât toate acestea.

1017
00:37:58,926 --> 00:38:00,410
Bine.

1018
00:38:00,410 --> 00:38:04,700
>> Care este cel mai rau caz de funcționare
timp de fel de selecție?

1019
00:38:04,700 --> 00:38:05,680
>> DIFUZOR 4: N patrat.

1020
00:38:05,680 --> 00:38:06,710
>> David J. MALAN: n pătrat, aud.

1021
00:38:06,710 --> 00:38:09,790
Dar de ce n pătrat, intuitiv?

1022
00:38:09,790 --> 00:38:11,170
>> DIFUZOR 4: Pentru ca ne-am făcut-o.

1023
00:38:11,170 --> 00:38:12,260
>> David J. MALAN: Pentru că ne-am făcut-o.

1024
00:38:12,260 --> 00:38:12,550
OK.

1025
00:38:12,550 --> 00:38:13,380
Bun răspuns.

1026
00:38:13,380 --> 00:38:16,660
Dar intuitiv, ce este selectarea
fel n pătrat?

1027
00:38:16,660 --> 00:38:18,980
Ce am avut de a face
din nou și din nou?

1028
00:38:18,980 --> 00:38:22,570
Am avut de a păstra scanarea prin, sunt
te cel mai mic, tu esti

1029
00:38:22,570 --> 00:38:24,020
mai mici, sunteți cel mai mic.

1030
00:38:24,020 --> 00:38:27,480
Și a acordat, am fost în măsură să ia n
etape, atunci n minus 1, atunci n minus 2.

1031
00:38:27,480 --> 00:38:30,700
Dar, dacă aveți un fel de adăuga celor toate în sus,
sau l ia pe credință care le-am adăugat

1032
00:38:30,700 --> 00:38:34,810
le în avans, avem aproximativ n
pătrat minus câteva numere mai mici.

1033
00:38:34,810 --> 00:38:36,730
Așa că am de gând să numim această n pătrat.

1034
00:38:36,730 --> 00:38:39,530
Dar, cu un fel de selecție, în cel mai bun
caz, câți pași este

1035
00:38:39,530 --> 00:38:40,632
O să mă ia?

1036
00:38:40,632 --> 00:38:41,840
>> DIFUZOR 5: [inaudibil]

1037
00:38:41,840 --> 00:38:44,350
>> David J. MALAN: Este, din păcate,
încă n pătrat, nu?

1038
00:38:44,350 --> 00:38:49,590
Pentru că dacă eu sunt alegerea cea mai mică
elemente, și am avut șapte persoane aici,

1039
00:38:49,590 --> 00:38:53,280
Știu doar, o dată ce am ajunge la foarte
sfârșit, că am găsit cel mai mic

1040
00:38:53,280 --> 00:38:55,670
număr, ori de câte ori el sau
ea ar fi fost.

1041
00:38:55,670 --> 00:38:58,820
Dar cum pot găsi la următoarea
cel mai mic număr?

1042
00:38:58,820 --> 00:39:00,160
Trebuie să fac o altă trecere.

1043
00:39:00,160 --> 00:39:04,810
Deci, în cel mai bun caz, ceea ce este
de intrare la fel de selecție?

1044
00:39:04,810 --> 00:39:07,830
Este o listă deja un fel, numărul unu,
Numărul doi, numarul trei, numărul patru.

1045
00:39:07,830 --> 00:39:08,600
Dar eu sunt un calculator.

1046
00:39:08,600 --> 00:39:10,190
Eu pot uita doar la un singur
lucru la un moment dat.

1047
00:39:10,190 --> 00:39:12,465
Eu nu pot sorta a lua un pas
spate, ca un om și spune,

1048
00:39:12,465 --> 00:39:14,030
ooh, acest lucru pare corect.

1049
00:39:14,030 --> 00:39:17,580
>> Eu pot pronunța doar corectitudinea în
selectare Sortare prin selectarea

1050
00:39:17,580 --> 00:39:18,370
cel mai mic număr.

1051
00:39:18,370 --> 00:39:21,390
Dar chiar dacă am găsi numărul unu în primul rând,
dacă nu știu nimic altceva despre

1052
00:39:21,390 --> 00:39:24,460
cu alte numere, pe care eu nu fac, tot ce am
Știu că am fost înmânat un tablou

1053
00:39:24,460 --> 00:39:27,930
sau un set de uși în spatele cărora sunt
numere, singurul mod in care stiu ca o

1054
00:39:27,930 --> 00:39:28,680
a fost mai mic?

1055
00:39:28,680 --> 00:39:32,440
Dacă am lua tot drumul aici și dau seama,
La naiba, unul a fost într-adevăr cel mai mic.

1056
00:39:32,440 --> 00:39:34,870
>> Dar cum pot apoi să determine care
doi este următoarea cea mai mică?

1057
00:39:34,870 --> 00:39:38,350
Făcând același ineficiența
din nou și din nou.

1058
00:39:38,350 --> 00:39:42,210
Deci, în final, cu un fel de inserție,
cum, în cel mai rău caz,

1059
00:39:42,210 --> 00:39:44,990
am spune că efectuează?

1060
00:39:44,990 --> 00:39:49,100
Acesta este de asemenea n pătrat.

1061
00:39:49,100 --> 00:39:53,020
Și cum despre cu cel mai bun caz?

1062
00:39:53,020 --> 00:39:56,282
Vom lăsa ca pe un Cliffhanger.

1063
00:39:56,282 --> 00:40:00,090
Vom completa acest timp gol viitoare,
dar mai întâi permiteți-mi propun să

1064
00:40:00,090 --> 00:40:02,620
fundamental face mai bine decât
toate acestea, în regulă?

1065
00:40:02,620 --> 00:40:05,220
>> Deci, cred că pentru tine ceea ce inserare
fel va fi.

1066
00:40:05,220 --> 00:40:06,910
Ei bine, că nu a fost foarte dramatic,
pentru că eu sunt singurul

1067
00:40:06,910 --> 00:40:08,970
care a văzut schimbarea.

1068
00:40:08,970 --> 00:40:09,620
Wow.

1069
00:40:09,620 --> 00:40:10,420
OK.

1070
00:40:10,420 --> 00:40:12,615
Deci, aici avem o oarecum
diferite demonstrație.

1071
00:40:12,615 --> 00:40:16,580
Dacă aș apropia aici, veți vedea că pe
stânga avem un fel bule, în

1072
00:40:16,580 --> 00:40:20,740
Orientul Mijlociu, avem un fel de selecție, și pe
în dreapta, avem ceva ce

1073
00:40:20,740 --> 00:40:23,380
nu s-au uitat la încă
numit fuziona fel.

1074
00:40:23,380 --> 00:40:26,080
Dar ia în considerare ceea ce am fost
aici până acum astăzi.

1075
00:40:26,080 --> 00:40:29,200
Când Jennifer venit prima dată pe scenă,
am trecut prin matrice de numere

1076
00:40:29,200 --> 00:40:33,750
din nou, și din nou, cu căutare liniară,
și ne-am timp de funcționare liniară, mare O

1077
00:40:33,750 --> 00:40:35,100
de n, ca să spunem așa.

1078
00:40:35,100 --> 00:40:41,000
>> Când luăm în considerare acum prima săptămână de
clasă, atunci când ne-am dezbina si cucereste,

1079
00:40:41,000 --> 00:40:43,740
și am avut cartea de telefon rupere,
și Jennifer, și am colectiv

1080
00:40:43,740 --> 00:40:47,500
indatorare că perspectiva cheie, care a fost de a
repeta-te din nou și din nou de

1081
00:40:47,500 --> 00:40:50,930
într-un fel aruncați, aruncați,
aruncați, jumătate din problemă, sau

1082
00:40:50,930 --> 00:40:55,320
în general, împărțind o problemă în jumătate,
și apoi tratarea bucată mică de

1083
00:40:55,320 --> 00:40:59,630
problema ca conceptual echivalent
la alții, am făcut într-un fel

1084
00:40:59,630 --> 00:41:00,910
fundamental mai bine.

1085
00:41:00,910 --> 00:41:04,720
Dar cu un fel bule, cu selecție
fel, cu un fel de inserție, ne-am putea

1086
00:41:04,720 --> 00:41:06,560
nici o astfel de perspective pe care Jennifer a făcut.

1087
00:41:06,560 --> 00:41:10,220
Am destul de mult tocmai a intrat înapoi și
mai departe o grămadă de ori, și am

1088
00:41:10,220 --> 00:41:12,650
lucrurile optimizat un pic, schimbarea
în această ordine, poate

1089
00:41:12,650 --> 00:41:13,730
introducerea sau selectarea.

1090
00:41:13,730 --> 00:41:16,950
Dar la sfarsitul zilei, am făcut o mulțime
de mers pe jos de ciudat înainte și înapoi.

1091
00:41:16,950 --> 00:41:21,160
Noi nu într-adevăr ceva de pârghie
inteligent ca Jennifer a făcut ca împărțirea

1092
00:41:21,160 --> 00:41:22,040
și cucerirea.

1093
00:41:22,040 --> 00:41:25,620
>> Deci fuziona fel, prin contrast, noi care
nu va vedea până săptămâna viitoare, se va

1094
00:41:25,620 --> 00:41:29,540
pentru a pârghie ideea cheie prin împărțirea
intrare, și apoi reducerea la jumătate, iar apoi

1095
00:41:29,540 --> 00:41:30,580
reducerea la jumătate, și apoi înjumătățirea.

1096
00:41:30,580 --> 00:41:34,590
Și pe fiecare iterație a buclei,
sortare jumătatea din stânga, și dreapta

1097
00:41:34,590 --> 00:41:38,200
jumătate, apoi jumătatea din stânga a jumătate din stânga,
și jumătatea din dreapta a stânga, apoi

1098
00:41:38,200 --> 00:41:40,990
jumătatea stângă a jumătatea din dreapta, și
jumătatea dreaptă a jumătatea din dreapta.

1099
00:41:40,990 --> 00:41:42,840
Și se repetă din nou și din nou.

1100
00:41:42,840 --> 00:41:46,170
>> Deci, veți vedea acest punct de vedere vizual, dar acest lucru
este ceea ce ne așteaptă săptămâna viitoare.

1101
00:41:46,170 --> 00:41:49,760
Și, în general, atunci când ne gândim un pic
mai greu cu privire la orice astfel de problemă.

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
Am n pătrat pe stânga, n
pătrat la mijloc, și n

1104
00:41:57,970 --> 00:41:59,400
log n pe dreapta.

1105
00:41:59,400 --> 00:42:00,590
Deci, nu e Cliffhanger tau real.

1106
00:42:00,590 --> 00:42:02,040
Ne vedem luni.

1107
00:42:02,040 --> 00:42:05,163
>> [Aplauze]