1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Săptămâna 3, Continuare]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Universitatea Harvard]

3
00:00:04,110 --> 00:00:07,130
>> [Acest lucru este CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Bine. Bine ai venit înapoi. Acest lucru este CS50 și acesta este sfârșitul săptămânii 3.

5
00:00:11,010 --> 00:00:14,680
>> Deci, pentru cei nefamiliarizați ani, trecut la Harvard a lansat ceea ce se numește Lab Inovare,

6
00:00:14,680 --> 00:00:18,530
sau i-Lab, care este o clădire minunată peste râu în campus CBGC lui

7
00:00:18,530 --> 00:00:22,640
care este deschis pentru studenții de colegiu, studenți SZG, studenți din toată campus peste,

8
00:00:22,640 --> 00:00:27,000
inclusiv facultate, și este un loc să vină împreună pentru a lucra asupra lucrurilor inovatoare,

9
00:00:27,000 --> 00:00:29,180
lucruri deosebit de antreprenoriale

10
00:00:29,180 --> 00:00:33,410
Dacă ați răspuns și 0 sau mai mulți prieteni de gândire de a face ceva antreprenoriale

11
00:00:33,410 --> 00:00:37,080
fie în timpul această clasă, după această clasă, sau dincolo.

12
00:00:37,080 --> 00:00:41,540
>> Deci, unul din lucrurile pe care le fac pe termen lung este J aceste excursii,

13
00:00:41,540 --> 00:00:44,510
dintre care unul este la New York, dintre care unul este de la Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
Spatiul este foarte limitat, dar este o oportunitate de a freca umerii cu MBA

15
00:00:47,530 --> 00:00:52,200
si tinerilor absolventi de facultati din campus și, de fapt petrece timpul în domeniile respective

16
00:00:52,200 --> 00:00:55,500
chat up startup-uri, chat up antreprenorii și place.

17
00:00:55,500 --> 00:00:57,870
Deci, daca te intereseaza, a verifica afară această adresă URL aici.

18
00:00:57,870 --> 00:01:01,220
Acesta este, de asemenea, disponibile pe slide-uri on-line.

19
00:01:01,220 --> 00:01:04,610
>> Am putea tonul jos audio casa doar un pic?

20
00:01:04,610 --> 00:01:08,640
Dacă doriți să vă alăturați nouă pentru masa de prânz de vineri, ora 01:15, în Fire & Ice, vă rugăm să cap acolo.

21
00:01:08,640 --> 00:01:11,390
Ne cerem scuze dacă formularul este deja umplut de dată când ajunge acolo.

22
00:01:11,390 --> 00:01:13,750
Dar vom continua această tradiție mai departe.

23
00:01:13,750 --> 00:01:17,350
>> Astăzi vom continua discuția nivel mai ridicat al diferitelor probleme pe care le putem rezolva,

24
00:01:17,350 --> 00:01:21,330
concentrându-se mult mai puțin, astăzi, cel puțin, pe cod și mult mai mult pe idei.

25
00:01:21,330 --> 00:01:24,720
Deci, cred că înapoi la săptămâna 0 atunci când am rupt-o carte de telefon în jumătate,

26
00:01:24,720 --> 00:01:28,260
al cărei obiectiv a fost de a face ceva, desigur, un pic dramatic

27
00:01:28,260 --> 00:01:32,360
dar pentru a trimite punctul în care căutarea nu trebuie să fie, în mod necesar,

28
00:01:32,360 --> 00:01:35,100
la fel de evident la prima vedere ca ai putea crede.

29
00:01:35,100 --> 00:01:40,200
Și rezolvarea de probleme, în general, nu s-ar putea să fie în mod necesar întotdeauna cel mai bun -

30
00:01:40,200 --> 00:01:44,130
Soluția cea mai evidentă ar putea să nu fie neapărat cel mai bun.

31
00:01:44,130 --> 00:01:47,300
Așa că am avut această carte de telefon și, sincer, noi toți din această cameră au avut instincte,

32
00:01:47,300 --> 00:01:51,470
cel mai probabil, pentru a începe în mijloc atunci când caută pentru Mike Smith și apoi du-te la stânga sau la dreapta

33
00:01:51,470 --> 00:01:54,280
bazată pe orice literă a alfabetului am sa întâmplat să se încheie pe.

34
00:01:54,280 --> 00:01:57,560
>> Dar ideea simplă pe care noi, oamenii, s-au luat de atât de mult timp

35
00:01:57,560 --> 00:02:00,670
într-adevăr ar trebui să înceapă să vină în fruntea mintea ta

36
00:02:00,670 --> 00:02:03,900
pentru că așa cum problemelor obține mult mai complexă decât o carte de telefon,

37
00:02:03,900 --> 00:02:07,420
aceste aceleași perspective strălucite simple, sunt ceea ce sunt de gând să ne permită

38
00:02:07,420 --> 00:02:10,259
pentru a rezolva problemele mult mai complicate și mai interesant,

39
00:02:10,259 --> 00:02:12,930
printre care unele din lucrurile pe care le ia pentru a acordat deja aceste zile.

40
00:02:12,930 --> 00:02:15,720
Miliarde de pagini web acolo, și totuși Google și Bing și cum ar fi

41
00:02:15,720 --> 00:02:17,660
sunt capabili de a găsi lucruri pentru noi așa.

42
00:02:17,660 --> 00:02:22,300
Asta nu se întâmplă prin utilizarea o căutare liniară, căutarea prin toate paginile web posibile.

43
00:02:22,300 --> 00:02:25,290
Facebook este în măsură să-ți spun cine toți prietenii tăi sunt sau prieteni ai prietenilor,

44
00:02:25,290 --> 00:02:28,250
și că prea se poate face aparent într-o clipă aceste zile

45
00:02:28,250 --> 00:02:30,820
chiar dacă acestea au milioane de utilizatori.

46
00:02:30,820 --> 00:02:34,250
>> Și așa cum ne-am rezolvat problemele de fapt, pe care în cele din urmă va reduce la scară

47
00:02:34,250 --> 00:02:37,830
la ideile ne-am uitat la în săptămâna 0 și un pic mai mult astăzi.

48
00:02:37,830 --> 00:02:42,320
Noi nu va re-executa acest algoritm, ci amintesc, de asemenea, am făcut-o în săptămâna 0 acest exercițiu

49
00:02:42,320 --> 00:02:44,780
în cazul în care am toată lumea se ridice, să ia de la numărul 1,

50
00:02:44,780 --> 00:02:48,720
și apoi am avut toată lumea auto-count de asociere off, adăugând numerele voastre impreuna,

51
00:02:48,720 --> 00:02:51,930
apoi jumătate din banda se așeză pe fiecare iterație.

52
00:02:51,930 --> 00:02:56,750
Așa că am trecut de la 500 de elevi la 250 la 125 și așa mai departe.

53
00:02:56,750 --> 00:03:00,080
Dar, așa cum am spus, luni, ideea puternic acolo

54
00:03:00,080 --> 00:03:02,460
a fost că, dacă ne-am dublat dimensiunea acestei probleme

55
00:03:02,460 --> 00:03:06,480
și toți copiii de la Justiție sau CE 10 a intrat înapoi în cameră și ni sa alăturat,

56
00:03:06,480 --> 00:03:09,510
ei bine, am putea număra, probabil, că tot grupul agregat

57
00:03:09,510 --> 00:03:13,380
cu doar 1 repetare mare mai mult de bucla, deoarece acestea nu ar face decât poate dubla dimensiunea

58
00:03:13,380 --> 00:03:15,630
sau în cazul în care CE 10 este un pic mai mult decat dublu marimea.

59
00:03:15,630 --> 00:03:18,440
Și așa ne-ar trebui să-și petreacă un pic mai mult timp,

60
00:03:18,440 --> 00:03:22,000
dar nu ar trebui să-și petreacă 400 sau 700 mai mulți pași.

61
00:03:22,000 --> 00:03:26,550
>> Doar pentru a picta această imagine într-un mod care este un pic mai puțin abstractă, să nu se ridice toată lumea s-au.

62
00:03:26,550 --> 00:03:31,100
Dar, dacă cei dintre voi care au ales să stea în orchestra de astăzi nu s-ar deranja în picioare,

63
00:03:31,100 --> 00:03:34,580
hai sa vedem daca ne putem da seama cine dintre voi este cea mai inalta persoana

64
00:03:34,580 --> 00:03:36,730
de a face același tip de algoritm comparative.

65
00:03:36,730 --> 00:03:41,830
Deci, dacă sunteți ședinței în orchestră, îmi cer scuze, dar pasul 1, se ridice în picioare;

66
00:03:41,830 --> 00:03:44,650
pasul 2, pereche off cu oricine din apropiere,

67
00:03:44,650 --> 00:03:49,360
seama cine este mai inalt, si stai jos, dacă sunt mai scurte.

68
00:03:49,360 --> 00:03:51,360
Apoi repeta.

69
00:03:51,360 --> 00:03:56,280
[Elevi murmurând]

70
00:04:13,450 --> 00:04:15,320
>> Bine.

71
00:04:15,320 --> 00:04:19,010
Bine. Unul este lăsat în picioare. Care e numele tău? Andrew >>.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, esti cea mai inalta persoana din secțiunea orchestra de astăzi.

73
00:04:21,959 --> 00:04:28,100
>> Felicitări. [Aplauze și aplauze] Ok. Au un loc. Așa că am găsit Andrew.

74
00:04:28,100 --> 00:04:30,870
Dar cât timp ar fi luat eu, de exemplu, pentru a găsi Andrew

75
00:04:30,870 --> 00:04:33,740
în această secțiune orchestră de 50 + sau cam asa ceva de oameni?

76
00:04:33,740 --> 00:04:36,900
Aș fi putut să iau o abordare destul de simplă și începe aici.

77
00:04:36,900 --> 00:04:39,270
Și am 2 persoane se ridice și eu doar le compara,

78
00:04:39,270 --> 00:04:42,120
și apoi spun oricui este puțin mai scurt, "Bine, stai jos,"

79
00:04:42,120 --> 00:04:44,380
și am de gând să-mi amintesc cine a fost persoana mai inalt.

80
00:04:44,380 --> 00:04:49,030
Apoi Repet, repet, repet, și am atârnă pe cea mai inalta persoana

81
00:04:49,030 --> 00:04:51,920
până când am găsit pe cineva puțin mai înalt decât ei, moment în care

82
00:04:51,920 --> 00:04:54,950
persoana un pic mai scurt trebuie să stai apoi în jos.

83
00:04:54,950 --> 00:04:57,690
Dar în faptul că algoritmul în această secțiune orchestră, în cazul în care există n de tine,

84
00:04:57,690 --> 00:05:00,480
câți pași este ca algoritmul de gând să ia? >> [Elev] N.

85
00:05:00,480 --> 00:05:03,580
>> Se va lua N, dreapta, pentru că în cel mai rău caz, ca să spunem așa,

86
00:05:03,580 --> 00:05:09,090
cea mai inalta persoana este persoana foarte ultima pe care am ajunge la doar ghinion aleatoare.

87
00:05:09,090 --> 00:05:14,260
Deci, în cel mai rău caz, timpul de rulare a algoritmului este liniar, e N,

88
00:05:14,260 --> 00:05:18,070
unde n este numărul total de persoane în spațiu, dimensiunea problemei.

89
00:05:18,070 --> 00:05:19,600
Ce zici de acest algoritm?

90
00:05:19,600 --> 00:05:22,080
Faptul că toți s-au ridicat și apoi din nou, jumatate din voi se așeză,

91
00:05:22,080 --> 00:05:23,950
jumătate dintre voi se așeză, jumătate dintre voi se așeză.

92
00:05:23,950 --> 00:05:26,070
Câte măsuri ar fi luat ca daca nu e de tine aici n?

93
00:05:26,070 --> 00:05:30,200
[Elev] n log n. >> Asta ar fi mai rău. Log n.

94
00:05:30,200 --> 00:05:32,930
>> Deci log n, chiar daca nu-mi amintesc destul de ceea ce un logaritm este,

95
00:05:32,930 --> 00:05:38,410
de acum, doar aprecia faptul că se referă cumva la acest înjumătățirea și înjumătățirea și înjumătățirea.

96
00:05:38,410 --> 00:05:41,000
Aceasta nu trebuie să fie un factor de 2. Ar putea fi un factor de 3.

97
00:05:41,000 --> 00:05:46,560
Dar e această repetiție de același tip de factor, astfel încât dimensiunea problemei începe aici

98
00:05:46,560 --> 00:05:49,620
dar apoi imediat se duce aici, apoi aici, apoi aici, apoi aici.

99
00:05:49,620 --> 00:05:53,580
Nu te lua inghitituri mici din problema, sunteți cu adevărat tocare departe la ea

100
00:05:53,580 --> 00:05:56,160
cu o mare lovitura de fiecare dată.

101
00:05:56,160 --> 00:06:00,810
Deci, am avut 50 de oameni, apoi 25, apoi 12 ½ sau 13 de oameni în picioare,

102
00:06:00,810 --> 00:06:05,370
apoi 6 ½ și așa mai departe până când în cele din urmă în picioare doar Andrew a fost lăsat.

103
00:06:05,370 --> 00:06:08,710
Deci, vom numi că log n, și puteți vizualiza această după cum urmează.

104
00:06:08,710 --> 00:06:12,570
Amintesc de această imagine aici, unde un algoritm liniar este ca linia roșie acolo,

105
00:06:12,570 --> 00:06:17,520
linia galbenă a fost de numărare prin algoritmul 2s pe care am folosit pentru studenții de numărare

106
00:06:17,520 --> 00:06:22,300
în trecut, dar astăzi Sfântul Graal este de gând să rămână această linie verde

107
00:06:22,300 --> 00:06:25,470
în cazul în care, dacă ne-am dublat numărul de persoane din secțiunea orchestra sau doar a spus,

108
00:06:25,470 --> 00:06:29,170
dracu ', hai să toată lumea din intreaga camera se ridice în picioare, nu, o astfel de afacere de mare

109
00:06:29,170 --> 00:06:31,560
pentru ca am dubla aproximativ cât de mulți oameni sunt aici,

110
00:06:31,560 --> 00:06:33,500
1 iterație mai mult, nu o problemă.

111
00:06:33,500 --> 00:06:36,200
>> Am gasit Andrew sau oricine se întâmplă să fie mai inalt decat Andrew

112
00:06:36,200 --> 00:06:38,770
în mezanin sau în balcon.

113
00:06:38,770 --> 00:06:42,140
Deci, această idee simplă pe care am luat atât de mult pentru a acordat într-o carte de telefon,

114
00:06:42,140 --> 00:06:46,170
dau seama că există atât de multe locuri diferite în care o putem aplica.

115
00:06:46,170 --> 00:06:50,810
Doar pentru a palmă unele jargon - de fapt, mai degrabă decât jargonul în primul rând,

116
00:06:50,810 --> 00:06:52,750
lasă-mă să merg la această imagine aici.

117
00:06:52,750 --> 00:06:56,970
Chiar acum am vorbit despre n și n / 2 și apoi jurnal de n,

118
00:06:56,970 --> 00:07:00,500
dar putem veni cu siguranță, cu, așa cum vom de-a lungul semestrului,

119
00:07:00,500 --> 00:07:05,130
alt fel de formule matematice pentru a descrie această noțiune generală timpului de funcționare.

120
00:07:05,130 --> 00:07:07,580
Acestea sunt scoase din context, pentru acum, pentru că vom vedea în scurt timp

121
00:07:07,580 --> 00:07:09,900
algoritmi că acestea reprezintă, de fapt.

122
00:07:09,900 --> 00:07:17,990
>> Dar observați aici linia N liniar, linia dreaptă, este de fapt foarte scăzută îndreptat acum.

123
00:07:17,990 --> 00:07:22,950
Asta e un fel de iluzie optică, în care ne schimba doar ceea ce reprezintă axa x

124
00:07:22,950 --> 00:07:26,130
și axa y, și putem face un punct de linie dreaptă în orice direcție dorim.

125
00:07:26,130 --> 00:07:30,350
Dar motivul pentru care este atât de aparent plat acum

126
00:07:30,350 --> 00:07:35,690
este pentru că avem nevoie pentru a face loc pe acest grafic pentru ori mult mai lent de funcționare.

127
00:07:35,690 --> 00:07:39,030
Pentru moment, știu că există unele algoritmi destul de rău în viață,

128
00:07:39,030 --> 00:07:43,790
dintre care unele nu iau măsuri N sau, mai bine încă, dar n log pași mai multe.

129
00:07:43,790 --> 00:07:48,820
Deci, deasupra liniei n aici, la partea de jos preaviz nu e log n ori de n,

130
00:07:48,820 --> 00:07:51,410
și vom vedea ce înseamnă înainte de mult timp.

131
00:07:51,410 --> 00:07:56,010
De mai sus, care este n pătrat, și nu am văzut nici un algoritmi n patrate încă, dar suntem pe cale să.

132
00:07:56,010 --> 00:07:57,660
Și care arată foarte rău.

133
00:07:57,660 --> 00:08:01,610
Nu e 2 la N, ceva exponențială, care se simte chiar mai rău.

134
00:08:01,610 --> 00:08:05,760
Și totuși, curios, atunci nu e n cubulete, care, dacă ești un fel de a gândi înainte,

135
00:08:05,760 --> 00:08:10,000
daca faci un fel de matematica, 2 la N de fapt, devine mult mai drept,

136
00:08:10,000 --> 00:08:15,930
mult mai mare decât până n tocata daca te uiti la axele suficient de departe afară.

137
00:08:15,930 --> 00:08:19,890
Deci, observați acum aceste axe sunt arbitrar 2 la 10 pe axa x.

138
00:08:19,890 --> 00:08:21,770
>> Și ce înseamnă asta?

139
00:08:21,770 --> 00:08:23,890
Asta inseamna 2 persoane la 10 de persoane într-o cameră.

140
00:08:23,890 --> 00:08:27,200
Asta e tot ce înseamnă x: dimensiunea problemei, indiferent de context este.

141
00:08:27,200 --> 00:08:30,420
Și o axă verticală acum este numărul de secunde sau numărul de pași -

142
00:08:30,420 --> 00:08:31,840
unele unitate de timp.

143
00:08:31,840 --> 00:08:34,740
Dar observați că este 0 - 60 și 0 la 10.

144
00:08:34,740 --> 00:08:38,549
Dar, dacă ne fel de zoom, astfel cum s-ar putea în Excel sau unele software-ul grafice,

145
00:08:38,549 --> 00:08:43,370
și vom merge până la 200.000, observați că ceva de genul 2 la n

146
00:08:43,370 --> 00:08:47,520
este de gând să copleșească complet ori de funcționare a pătrat n,

147
00:08:47,520 --> 00:08:50,960
n tocata, n log n - tot ceea ce am vorbit până acum despre.

148
00:08:50,960 --> 00:08:54,190
Și totuși, de captură este atunci când începi să vorbești despre lucruri cum ar fi Facebook

149
00:08:54,190 --> 00:08:57,150
în cazul în care aveți mai multe, mulți, mulți oameni toate interconectate,

150
00:08:57,150 --> 00:09:00,650
n-ați persoane, fiecare dintre care ar putea avea cât mai multe ca prieteni n

151
00:09:00,650 --> 00:09:02,860
în cazul în care toată lumea este un fel de amic-amic în lume,

152
00:09:02,860 --> 00:09:08,100
bine, asta e de n ori n deja, așa că e n patrate prietenii posibile,

153
00:09:08,100 --> 00:09:10,950
cel puțin în direcția 1, n prietenii pătrat posibile.

154
00:09:10,950 --> 00:09:15,330
Așa că deja sugerează că căutarea Graficul socială Facebook, ca să spunem așa,

155
00:09:15,330 --> 00:09:18,090
poate începe să fie exprimată în aceste tipuri de formule.

156
00:09:18,090 --> 00:09:19,820
>> Ne vom întoarce și să facă atât de mult mai concret,

157
00:09:19,820 --> 00:09:23,280
dar pentru moment, obiectivul pentru următoarele săptămâni mai multe

158
00:09:23,280 --> 00:09:27,170
va fi sigur de a nu merge despre algoritmi de punere în aplicare sau cod

159
00:09:27,170 --> 00:09:29,870
care sfârșesc prin a lua timp la fel de mult ca pe ceva de genul asta.

160
00:09:29,870 --> 00:09:33,110
Dar lucrul fascinant despre știință de calculator, dacă veți continua in acest domeniu

161
00:09:33,110 --> 00:09:38,320
luând în clase ca CS121, CS124, ambele din care sunt cursuri teorie,

162
00:09:38,320 --> 00:09:41,300
este că există, de fapt unele probleme care există în această lume

163
00:09:41,300 --> 00:09:45,710
că fundamental, în măsura în care știm, nu pot fi rezolvate mai repede

164
00:09:45,710 --> 00:09:48,880
decât cel mai rău dintre aceste grafice de fapt sugereaza.

165
00:09:48,880 --> 00:09:53,660
Deci, există o mulțime de probleme deschise în această lume pentru a face mult mai bine decât oamenii au până în prezent.

166
00:09:53,660 --> 00:09:56,130
>> Așa că hai să începem apoi cu acest exemplu.

167
00:09:56,130 --> 00:09:59,650
Am văzut lupta Sean cu acest aparat foto pe, mult prea neîndemânatic pe video.

168
00:09:59,650 --> 00:10:05,270
Dar realitatea a fost atunci când Sean a fost însărcinat cu găsirea de la o placa ca aceasta numărul 7,

169
00:10:05,270 --> 00:10:10,300
amintesc că am spus că, "Nu este undeva în spatele acestor bucăți de hârtie sau de usi albe

170
00:10:10,300 --> 00:10:12,570
"Sean numărul 7,. Pare pentru noi."

171
00:10:12,570 --> 00:10:14,200
Și a fost minunat ciudat pentru a viziona

172
00:10:14,200 --> 00:10:15,790
pentru că el a fost într-adevăr se luptă cu această problemă.

173
00:10:15,790 --> 00:10:19,720
Dar realitatea a fost Sean a făcut la fel ca oricine în camera ar fi putut face.

174
00:10:19,720 --> 00:10:21,890
El a luat un pic mai mult decât o persoană tipic ar putea avea,

175
00:10:21,890 --> 00:10:24,760
dar el a presupus că au existat unele truc la această problemă,

176
00:10:24,760 --> 00:10:26,590
el a presupus că el lipsea ceva.

177
00:10:26,590 --> 00:10:29,320
Și nu a ajutat faptul că sute de ochi au fost poartă în jos pe el.

178
00:10:29,320 --> 00:10:34,250
>> Dar realitatea a fost în cazul de intrare la problemă este o grămadă de numere aleatoare

179
00:10:34,250 --> 00:10:37,120
și ești rugat să găsească o astfel de număr,

180
00:10:37,120 --> 00:10:39,770
cel mai bun il poti face este căutare liniară.

181
00:10:39,770 --> 00:10:44,060
Start la stânga, trece la dreapta, sau de a începe de la dreapta, trece la stânga.

182
00:10:44,060 --> 00:10:48,300
Retroactiv, am putea fi de gândire, "Sean, de ce nu ai inceput doar de la celălalt capăt?"

183
00:10:48,300 --> 00:10:52,120
Ei bine, 7 ar fi putut la fel de usor a fost aici la întâmplare,

184
00:10:52,120 --> 00:10:54,980
dar am pus-o acolo în mod deliberat pentru că m-am gândit că nu o să înceapă la sfârșitul anului.

185
00:10:54,980 --> 00:10:59,320
Asa ca am un fel de manipulat situația, ci de întâmplare 7 ar putea fi oriunde.

186
00:10:59,320 --> 00:11:02,380
Deci, pornind de la capătul din dreapta ar fi fost mai bine, atunci,

187
00:11:02,380 --> 00:11:04,320
dar ce se întâmplă dacă anul următor am muta în altă parte 7?

188
00:11:04,320 --> 00:11:06,830
Asta nu este o solutie fundamental nouă a problemei -

189
00:11:06,830 --> 00:11:10,520
începând de la 1 capăt sau altul - cand ai de dat nici o alte ipoteze.

190
00:11:10,520 --> 00:11:13,620
Deci, Sean a început să caute prin numerele și el a spus, "5 Asta nu e aici.".

191
00:11:13,620 --> 00:11:17,280
Apoi, el a fost aici și a văzut 19, apoi a făcut o pauză de aproximativ 20 de secunde,

192
00:11:17,280 --> 00:11:22,330
apoi a deschis asta pentru 13, iar apoi a devenit evident

193
00:11:22,330 --> 00:11:24,270
faptul că nu pare a fi un model aici.

194
00:11:24,270 --> 00:11:28,090
Acesta nu a fost de 1, 2, 3, 4 sau similar. Au fost de lacune în privința numere, care nu ajută.

195
00:11:28,090 --> 00:11:32,320
Și de asemenea, faptul că am folosit aceste piese ieftine de hârtie pentru a acoperi numerele

196
00:11:32,320 --> 00:11:35,270
este de fapt deliberată, pentru că dacă am eliminat toate aceste bucăți de hârtie,

197
00:11:35,270 --> 00:11:38,760
cele mai multe dintre noi, Sean inclus, probabil, s-ar fi aruncat o privire fel de macroscopic

198
00:11:38,760 --> 00:11:43,410
la tablă și a spus, "Oh, 7 este, evident, acolo." Am făcut-o instantaneu.

199
00:11:43,410 --> 00:11:46,460
>> Și care ar putea fi modul în care creierul uman funcționează într-o anumită măsură,

200
00:11:46,460 --> 00:11:50,730
dar, în realitate, cu ochii sau mintea a fost, probabil, skimming numerele de la dreapta la stânga,

201
00:11:50,730 --> 00:11:55,190
la stânga la dreapta, de mijloc afară - ceva se întâmplă punct de vedere fiziologic

202
00:11:55,190 --> 00:11:57,640
astfel încât m-am simtit ca aceasta se intampla instantaneu,

203
00:11:57,640 --> 00:12:01,360
dar sansele sunt chiar pe plan intern a existat un fel de metodologii pentru a găsi 7.

204
00:12:01,360 --> 00:12:05,160
Și într-adevăr, acum că vorbim despre tablouri si structuri de date

205
00:12:05,160 --> 00:12:08,780
și în interiorul memoria unui calculator, singurul lucru pe care noi, oamenii, putem face

206
00:12:08,780 --> 00:12:13,070
se uita la locațiile de memorie individuale 1 la un moment dat.

207
00:12:13,070 --> 00:12:16,600
>> Deci, la fiecare altă locație ar putea la fel de bine să fie acoperite cu unele bucată de hârtie

208
00:12:16,600 --> 00:12:21,170
deoarece nu putem vedea oricum. Putem face doar 1 lucru la un moment dat.

209
00:12:21,170 --> 00:12:25,030
Deci, în acest caz, în cazul lui Sean, ne-am dus aici, și apoi ne-am dus aici

210
00:12:25,030 --> 00:12:31,040
și apoi ne-am dus aici, aici, aici, aici, am inteligent până la sfârșitul anului

211
00:12:31,040 --> 00:12:34,450
și doar un fel de omit aceasta arbitrar si a gasit acolo 7.

212
00:12:34,450 --> 00:12:37,470
Acest lucru nu a fost deosebit de specială. Acesta a fost prea în ordine.

213
00:12:37,470 --> 00:12:39,530
Dar el a găsit în cele din urmă 7.

214
00:12:39,530 --> 00:12:45,360
Dar acum livrata acasa este într-adevăr cel mai bun pe care le puteți face atunci când se administrează nici o informație

215
00:12:45,360 --> 00:12:50,400
altele decât numere aleatoriu sortate este de a porni de la stânga sau de dreapta începe de la.

216
00:12:50,400 --> 00:12:54,950
Sau naiba, aveți posibilitatea să deschideți la întâmplare ușile, dar chiar si atunci ce înseamnă să fi aleatoare?

217
00:12:54,950 --> 00:12:57,220
Ei bine, vom avea de a formaliza într-un fel ceea ce înseamnă pentru a începe aici,

218
00:12:57,220 --> 00:13:01,150
apoi du-te aici, du-te atunci aici. Sean a făcut mare, și a fost doar distractiv sa ma uit.

219
00:13:01,150 --> 00:13:06,340
Ce se întâmplă dacă în schimb vom schimba problema un pic și să aducă pe Sean din acest an, daca vrei?

220
00:13:06,340 --> 00:13:09,460
Ar fi cineva confortabil vine pe scenă și rezolvarea unei probleme ușor diferită

221
00:13:09,460 --> 00:13:12,330
și care figurează pe aparat de fotografiat?

222
00:13:12,330 --> 00:13:15,720
>> Să mergem dincolo de orchestră, deoarece voi au fost destul de implicat astăzi deja.

223
00:13:15,720 --> 00:13:21,430
Ce zici de la roz, în pălărie? Vino pe jos. Care este numele tau? Alex >>. Alex >>. Bine.

224
00:13:21,430 --> 00:13:24,580
Deci, Alex va fi Sean acest an și va apărea în următorii câțiva ani

225
00:13:24,580 --> 00:13:27,770
în valoare de CS50 prelegeri.

226
00:13:27,770 --> 00:13:30,340
Alex, mă bucur să te cunosc. >> Bucur să te cunosc prea.

227
00:13:30,340 --> 00:13:33,470
Provocarea la îndemână pentru tine este că aveți un pic mai ușor

228
00:13:33,470 --> 00:13:38,950
în care vă spun aceleași numere, sunt aici, dar sunt sortate acum.

229
00:13:38,950 --> 00:13:41,800
Deci, acum obiectivul dvs. este de a găsi numărul 7.

230
00:13:41,800 --> 00:13:45,370
Și, de fapt, ar trebui să facem cu adevărat acest lucru - Ești un fel de înșelăciune, ca un computer, nu ar fi,

231
00:13:45,370 --> 00:13:47,990
uitandu-se la ceea ce numere erau acum un moment.

232
00:13:47,990 --> 00:13:50,360
Cu creta acest fapt nu este de gând să ajute tot atât de mult,

233
00:13:50,360 --> 00:13:52,810
dar hai să te prefaci că nu știi ce matrice originală este.

234
00:13:52,810 --> 00:13:56,600
Tot ce știu acum este că aveți o serie de numere sunt sortate

235
00:13:56,600 --> 00:14:00,360
care ar putea avea spații între ele, și de obiectivul dvs. este de a găsi numărul 7.

236
00:14:00,360 --> 00:14:05,080
Cum ați, un om rezonabil ființă, du-te despre găsirea numărul 7?

237
00:14:05,080 --> 00:14:07,770
>> Du-te la mic la mare? Bine >>. Du-te la mic la mare.

238
00:14:07,770 --> 00:14:10,990
Și să nu-i smulgă. Să ridica doar le ca să le putem refolosi.

239
00:14:10,990 --> 00:14:14,730
Ok, deci 1. Așteaptă. Înainte de a continua, care a fost de 1, în mod clar greșit.

240
00:14:14,730 --> 00:14:17,270
Deci, ce se întâmplă prin minte următoarea ta? Care e următoarea ta mișcare?

241
00:14:17,270 --> 00:14:23,250
Următoarea. Bine >>. Următoarea. Bine. 3, astfel incorectă. Care e următoarea ta mișcare?

242
00:14:23,250 --> 00:14:27,670
Continuă să mergi. >> Regulă. Continuă să mergi. 5.

243
00:14:27,670 --> 00:14:31,110
Așa că ține în desfășurare, și să-mi dai asta pentru posteritate.

244
00:14:31,110 --> 00:14:35,720
7. Excelent >>. Foarte bine. S-au găsit numărul 7. [Aplauze]

245
00:14:35,720 --> 00:14:39,720
Așa că a fost bun, dar Sean găsit prea numărul 7.

246
00:14:39,720 --> 00:14:44,490
Și eu susțin că nu au exploatat într-adevăr această bucată suplimentară de informații,

247
00:14:44,490 --> 00:14:47,780
care este faptul că aceste numere sunt sortate.

248
00:14:47,780 --> 00:14:51,520
Deci, putem face mai bine? Orice sugestii aici? Da, în spate.

249
00:14:51,520 --> 00:14:54,710
[Elev] binar de căutare. >> Nu am nici o idee despre ceea ce caută binar este.

250
00:14:54,710 --> 00:14:58,030
>> [Elev] Start în mijloc. >> Start în mijloc. Bine. Deci, hai sa vedem daca putem ajunge acolo.

251
00:14:58,030 --> 00:15:02,580
Deci, dacă în loc să ți-am spus de la început de mijloc, mergeți mai departe și să deschidă ușa din mijloc.

252
00:15:02,580 --> 00:15:04,580
Există 8 dintre ei, deci ai de gând să aibă de a alege arbitrar una

253
00:15:04,580 --> 00:15:09,800
ușor la stânga sau la dreapta. Bine. 7! [Aplauze] Foarte frumos.

254
00:15:09,800 --> 00:15:11,410
Bine, dar în cazul în care s-au mergem cu asta?

255
00:15:11,410 --> 00:15:14,990
Să presupunem doar pentru a sparge cravată ați început aici

256
00:15:14,990 --> 00:15:16,670
pentru că la fel ar fi putut întâmpla la fel de bine.

257
00:15:16,670 --> 00:15:19,540
Trebuie doar sa întâmplat să știu că 7 a fost acolo. Deci, aceasta este de 13.

258
00:15:19,540 --> 00:15:21,980
Deci, dacă acestea sunt sortate și ne-am început în mijloc,

259
00:15:21,980 --> 00:15:24,600
ce s-ar mișcare optimă următoare au fost?

260
00:15:24,600 --> 00:15:27,740
Du-te la stânga. Și astfel vine aici, de exemplu cartea de telefon din nou.

261
00:15:27,740 --> 00:15:30,130
Dacă 13 este aici și știm Lista este sortata,

262
00:15:30,130 --> 00:15:33,900
atunci toate aceste bucati de hartie sunt neinteresante pentru noi acum

263
00:15:33,900 --> 00:15:37,400
pentru că știm deja că 7 trebuie să fie la stânga

264
00:15:37,400 --> 00:15:39,510
în cazul în care aceste numere sunt sortate și am găsit 13.

265
00:15:39,510 --> 00:15:42,500
>> Deci, ce e următoarea ta mișcare aici? >> Du-te la stânga. Bine >>, bine.

266
00:15:42,500 --> 00:15:45,080
Deci, du-te la stânga, și - așteaptă, hei, hei, hei. Asta e inselat.

267
00:15:47,140 --> 00:15:51,350
Deci ai gasit 7, dar ceea ce a fost algoritmul care tocmai am aplicat?

268
00:15:51,350 --> 00:15:56,450
Start în mijloc. Bine >>. Deci, ce e extensie logică a acestui aceeași idee?

269
00:15:56,450 --> 00:15:58,970
Oh, doar pentru acestea. Exact >>. Așa că am început >> aici. Bine >>.

270
00:15:58,970 --> 00:16:02,020
Deci, acum ne-am dus ușor la stânga din nou. E 3.

271
00:16:02,020 --> 00:16:05,310
Dar acum este livrata acasa interesant care o faci tu nu trebuie să pasă?

272
00:16:05,310 --> 00:16:08,040
Aceste 2. Aceste >> 2. Deci, acum aceasta se poate merge departe, aceasta se poate merge departe.

273
00:16:08,040 --> 00:16:12,330
Acum, problema care a fost de 8, apoi a fost de 4 marimea acum este dimensiunea 2.

274
00:16:12,330 --> 00:16:16,430
Primim destul de aproape. Din nou, du-te la mijlocul acestor 2 elemente.

275
00:16:16,430 --> 00:16:20,430
>> Bine. Deci e un fel de nefericit ca acum suntem mereu merge plecat pentru că suntem rotunjirea în jos.

276
00:16:20,430 --> 00:16:25,150
Dar asta e bine pentru că acum ne arunca această distanță și orice altceva, lăsându-ne cu doar 7.

277
00:16:25,150 --> 00:16:30,490
Să-i dăm o rundă de aplauze. Am gasit 7 din nou. [Aplauze] Ok. Sigur.

278
00:16:30,490 --> 00:16:32,220
Așteaptă pentru doar 1 secundă.

279
00:16:32,220 --> 00:16:36,630
Chiar dacă acest tip de proces următoarea luat un pic mai mult decât ne-am simtit ca ar fi,

280
00:16:36,630 --> 00:16:40,150
sincer, instinctele tale prima au fost cele mai bune, nu? Am gasit 7 instantaneu.

281
00:16:40,150 --> 00:16:46,740
Dar ne-ar fi gasit 7 mai rapid, indiferent de ceea ce, în acest exemplu față de aceasta

282
00:16:46,740 --> 00:16:50,100
pentru că, dacă numerele sunt toate sortate, la fel ca paginile dintr-o carte de telefon,

283
00:16:50,100 --> 00:16:54,580
aveți posibilitatea să taie într-adevăr, jumătate din problemă din nou și din nou și din nou.

284
00:16:54,580 --> 00:16:56,740
Și nu e chiar atât de ușor pentru a vedea acest lucru cu doar 8 numere

285
00:16:56,740 --> 00:17:00,100
spre deosebire de o carte de telefon de 1000 de pagini în cazul în care veți vedea cu adevărat vizual,

286
00:17:00,100 --> 00:17:03,120
dar, în acest caz, aici, când Sean a fost căutați pentru 7,

287
00:17:03,120 --> 00:17:06,020
câți pași în cel mai rău caz ar fi luat el? >> [Elev] 7.

288
00:17:06,020 --> 00:17:11,670
7 în cel mai rău caz. Ei bine, în cel mai rău caz, nu 7, dacă există 8 usi aici.

289
00:17:11,670 --> 00:17:13,440
Aceasta l-ar fi luat 8 pași.

290
00:17:13,440 --> 00:17:18,170
>> Deci, dacă nu e usi n, s-ar fi luat Sean câțiva ani în urmă pași n.

291
00:17:18,170 --> 00:17:21,520
Acum, în cazul tău, Alex, având în vedere că aceste numere sunt sortate -

292
00:17:21,520 --> 00:17:25,130
și putem deduce un fel de acest lucru de la care am fost până acum în această poveste -

293
00:17:25,130 --> 00:17:28,300
ceea ce este timpul de execuție al algoritmului mai inteligent lui Alex

294
00:17:28,300 --> 00:17:30,770
de a începe de la mijloc si apoi repeta?

295
00:17:30,770 --> 00:17:36,490
[Elev] 3. >> Deci va fi de 3, aproximativ, dacă te duci 8 la 4 la 2 la 1.

296
00:17:36,490 --> 00:17:40,660
Deci, 3 trepte sau, mai general, care este log n din nou.

297
00:17:40,660 --> 00:17:43,380
De fiecare dată când te reducerea la jumătate și înjumătățirea și înjumătățirea și înjumătățirea,

298
00:17:43,380 --> 00:17:45,290
ca o expresie a acestei idei de log n.

299
00:17:45,290 --> 00:17:48,140
Si pentru ca s-ar fi luat doar 3 pasi, și într-adevăr a făcut-o

300
00:17:48,140 --> 00:17:50,890
odată ce am deschis ușile și reducerea la jumătate reducerea la jumătate,

301
00:17:50,890 --> 00:17:53,770
întrucât acest lucru ar fi luat unele Sean 7 sau 8 trepte.

302
00:17:53,770 --> 00:17:56,330
Deci, vă mulțumesc pentru a fi alături de noi în acest an. >> Multumesc. Mă bucur să te cunosc.

303
00:17:56,330 --> 00:18:00,170
Mulțumesc lui Alex. De asemenea >>. [Aplauze]

304
00:18:00,170 --> 00:18:02,150
>> Care este atunci implicarea reală a acestei?

305
00:18:02,150 --> 00:18:06,050
Acum, imaginați că nu e 8 usi, care, sincer, toți dintre noi ar putea găsi ceva

306
00:18:06,050 --> 00:18:10,430
în spatele ușilor 8 destul de repede doar prin ruperea bucățile de hârtie și merge cu instinctele noastre.

307
00:18:10,430 --> 00:18:14,430
Dar dacă e un milion de uși? Ce dacă e 4 miliarde usi?

308
00:18:14,430 --> 00:18:19,630
În cazul de 4 miliarde de usi, sunteți cu adevărat de gând să vreau să merg cu algoritmul lui Alex,

309
00:18:19,630 --> 00:18:23,150
binar de căutare după cum vom începe numindu-l sau dezbina si cucereste, mai general,

310
00:18:23,150 --> 00:18:25,220
în cazul în care vă păstrați înjumătățirea și înjumătățirea problema,

311
00:18:25,220 --> 00:18:30,510
pentru că, dacă aveți 4 miliarde usi, de câte ori poți taie 4 miliarde jumătate?

312
00:18:30,510 --> 00:18:33,870
[Elev] 32. Este de fapt >> 32. Puteți lucra asta pe o bucată de hârtie sau în capul tău.

313
00:18:33,870 --> 00:18:38,490
Tu du-te 4000000000 - 2 miliarde to 1 miliard la o jumătate de miliard, la 250 milioane de euro, dot, dot, dot.

314
00:18:38,490 --> 00:18:41,620
Și dacă faci afară matematica, ai de gând să obțineți într-adevăr 32,

315
00:18:41,620 --> 00:18:44,950
și că, de fapt, se referă la informatică, deoarece ne bazăm, de obicei, în competențele de 2.

316
00:18:44,950 --> 00:18:47,600
2 la 32 se întâmplă să fie de 4 miliarde de euro.

317
00:18:47,600 --> 00:18:51,440
Deci, există o mulțime de relevanță pentru aceste tipuri de competențe de 2 în informatică.

318
00:18:51,440 --> 00:18:55,120
>> Dar ce aproximativ 8 miliarde? Câți pași se că va lua în cazul în care există 8 miliarde usi?

319
00:18:55,120 --> 00:19:00,350
[Elev] 33. Deci, 33 >>. Ce se întâmplă dacă nu există 16 miliarde usi? Câți pași se că va dura?

320
00:19:00,350 --> 00:19:05,020
[Elev] 34. >> 34. Am putea continua acest tip de ad nauseam. Dar asta e un lucru puternic.

321
00:19:05,020 --> 00:19:09,430
Puteți introduce miliarde de mai multe intrari la problema ta, dar, nu e mare lucru,

322
00:19:09,430 --> 00:19:14,140
luați doar 1 muscatura suplimentare din ea și, astfel, ne dă ceva de genul cautare binara

323
00:19:14,140 --> 00:19:15,920
sau dezbina si cucereste, mai general.

324
00:19:15,920 --> 00:19:17,990
Dar eu sunt un fel de inselat aici, nu?

325
00:19:17,990 --> 00:19:22,410
În cazul algoritmului lui Alex, ea a avut un avantaj de peste Sean.

326
00:19:22,410 --> 00:19:27,780
Ea știa că aceste numere au fost sortate, dar Alex nu a trebuit să le sorta ea.

327
00:19:27,780 --> 00:19:30,520
Am venit în avans de până la tablă și tipul de făcut-vă că

328
00:19:30,520 --> 00:19:33,670
că am atras-le pe toate în ordine sortate, apoi le-am acoperit cu hârtie.

329
00:19:33,670 --> 00:19:35,850
Dar cât de mult munca sa, care mă ia?

330
00:19:35,850 --> 00:19:40,110
Dacă am fi pornit la drum cu aceste numere într-o ordine aparent aleatorie -

331
00:19:40,110 --> 00:19:43,320
în acest caz, aceste numere simple, 1 până la 8 aici -

332
00:19:43,320 --> 00:19:46,090
cum putem merge despre sortarea aceste valori?

333
00:19:46,090 --> 00:19:52,530
Dacă ai fi fost un om dat această sarcină, ce fel de abordare intuitivă ar fi luați

334
00:19:52,530 --> 00:19:54,800
pentru sortarea o grămadă de numere?

335
00:19:54,800 --> 00:19:57,050
Aceste lucruri au fost stabilite ca piese de puzzle. Da.

336
00:19:57,050 --> 00:19:59,950
>> [Elev] mi-ar lua fiecare număr și să o compare cu fiecare dintre

337
00:19:59,950 --> 00:20:03,180
și să păstreze merge la stânga. Bine >>, bine.

338
00:20:03,180 --> 00:20:05,720
Deci, ia fiecare număr, comparați-o cu cea de lângă ea,

339
00:20:05,720 --> 00:20:09,610
și apoi să păstreze în mișcare de-a lungul doar lista, un fel de rejiggering lucrurile ca te duci.

340
00:20:09,610 --> 00:20:13,800
Deci, aici avem o șansă, poate pentru cateva mai oameni buni sa se implice.

341
00:20:13,800 --> 00:20:16,290
Avem 8 voluntari care au mai multe ar plăcea să vină?

342
00:20:16,290 --> 00:20:23,950
O presiune mai puțin, deoarece nu ești singura. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Vino pe jos. Voi vor fi numerele de la 1 8.

344
00:20:28,190 --> 00:20:36,050
Să vedem dacă nu putem face acest lucru sortare pentru Alex mult în același fel am făcut-o în prealabil.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Du-te și dacă ar fi, linia de sus pe scenă între suportul pentru muzică și mă aici

347
00:20:40,760 --> 00:20:44,960
în aceeași ordine ca și de diapozitive pe ecran.

348
00:20:47,910 --> 00:20:49,680
Uh-oh.

349
00:20:50,370 --> 00:20:53,230
Vă vom lucra în următorul exemplu. Oh, stai, stai. Aici vom merge. Așteaptă.

350
00:20:53,230 --> 00:20:57,570
Urmatorul exemplu este acum. Aici te duci. Numărul 8. Vino sus.

351
00:20:57,570 --> 00:21:00,270
Bine. Sorteaza înșivă în conformitate cu prezentul.

352
00:21:00,270 --> 00:21:03,620
Glisați doar un pic pe partea de muzica sta aici.

353
00:21:03,620 --> 00:21:12,310
Deci avem 4, 2, 6 - ajunge acolo, aici, chiar acolo - 3.

354
00:21:12,310 --> 00:21:17,570
Da. Bine. Du-te aici. Nu, stai acolo.

355
00:21:17,570 --> 00:21:21,840
Da, chiar acolo. Nu am greșit. Chiar acolo. Bine, foarte bine. Bine.

356
00:21:21,840 --> 00:21:24,930
Deci, acum hai sa le sorta într-o ordine crescătoare.

357
00:21:24,930 --> 00:21:26,210
>> Cum pot merge despre a face acest lucru?

358
00:21:26,210 --> 00:21:28,630
Algoritmul care a fost propus un moment în urmă a fost de ce nu ne compara pur și simplu

359
00:21:28,630 --> 00:21:31,970
oameni buni, care sunt un fel de una lângă alta și apoi repara orice greșeli,

360
00:21:31,970 --> 00:21:33,540
deplasează de la stânga la dreapta.

361
00:21:33,540 --> 00:21:36,580
Deci, aici avem 4 și 2, în mod evident din comanda. Hai să te schimbi. Bine.

362
00:21:36,580 --> 00:21:40,760
Deci, acum am de gând să se mute în jos linie. 4 și 6, nope. [Râsete]

363
00:21:40,760 --> 00:21:45,010
6 și 8, destul de bine. 8 și 1, lasă-mă să schimb voi. Bine.

364
00:21:45,010 --> 00:21:48,030
Deci, 8 și 3, schimb de voi.

365
00:21:48,030 --> 00:21:52,280
8 și 7, lasă-mă să schimb voi. 5 și 8, excelent.

366
00:21:52,280 --> 00:21:54,820
Eu vă dau o listă sortată.

367
00:21:54,820 --> 00:21:56,860
Bine. Deci, nu chiar.

368
00:21:56,860 --> 00:22:01,180
Dar e mai bine, deoarece numerele mai mari - caz în punctul 8 -

369
00:22:01,180 --> 00:22:04,030
au un fel de bule de aer de la stânga la dreapta peste.

370
00:22:04,030 --> 00:22:08,010
Asa ca am luat 1 din ele drept, dar se simte ca și cum acest lucru nu rezolvă problema destul.

371
00:22:08,010 --> 00:22:11,150
>> Deci, ce-ai propune să facem în continuare? >> [Elev] Continuați să faceți asta. Am >> continui să faci asta.

372
00:22:11,150 --> 00:22:13,740
Și dau seama, din nou, ne-am stabilit lucrurile de care au doar toti oamenii

373
00:22:13,740 --> 00:22:17,180
un fel de a aranja inteligent se bazează pe faptul că imaginea,

374
00:22:17,180 --> 00:22:19,040
dar acum trebuie să fim mult mai metodic.

375
00:22:19,040 --> 00:22:21,510
Trebuie să fie algoritmică despre ea ca și cum ne scrierea de cod -

376
00:22:21,510 --> 00:22:23,520
în acest caz, pseudocod verbală.

377
00:22:23,520 --> 00:22:26,040
Asa ca lasa-ma sa incerc din nou doar asta. Care a lucrat destul de bine. Ea nu-l rezolve.

378
00:22:26,040 --> 00:22:30,400
Dar când îndoiesc, încercați doar și încercați din nou. Deci, 2 și 4, nu a ajutat mai.

379
00:22:30,400 --> 00:22:33,200
4 și 6. Ah! 6 și 1, ceva mai bine acum.

380
00:22:33,200 --> 00:22:39,740
6 și 3, bine. 6 și 7, 7 și 5, 7 și 8, bine.

381
00:22:39,740 --> 00:22:44,060
Și tu știi, eu pot ignora, probabil, 8 acum, pentru că el este la sfârșitul listei.

382
00:22:44,060 --> 00:22:47,250
Poate că nu trebuie să vă faceți griji despre cineva merge pe lângă el.

383
00:22:47,250 --> 00:22:49,240
Dar să vedem dacă asta este o presupunere sigură.

384
00:22:49,240 --> 00:22:52,340
Acum lista este - al naibii de - nu este sortată. Să mai încercăm o dată.

385
00:22:52,340 --> 00:22:56,440
Deci, 2 și 4, 4 și 1, 4 și 3.

386
00:22:56,440 --> 00:22:59,230
4 și 6, bine. 6 și 5, bine.

387
00:22:59,230 --> 00:23:04,890
6, 7, și 8, bine. Dar aviz, pot opri doar aici, acum și oprim aici acum?

388
00:23:04,890 --> 00:23:07,770
[Elev] Da. Da >>?

389
00:23:07,770 --> 00:23:11,160
Ce se întâmplă dacă unul dintre voi a fost numărul 9 tot drumul acolo?

390
00:23:11,160 --> 00:23:13,640
Acesta ar fi fost sortate. Bine >>. Acesta ar fi fost sortate prima dată în jurul valorii.

391
00:23:13,640 --> 00:23:16,050
Bine. Așa că hai să ne întoarcem din nou. Suntem aproape acolo.

392
00:23:16,050 --> 00:23:22,800
1 și 2, 2 și 3, 3 și 4, 4 și 5, 5 și 6, 6 și 7, 7 și 8.

393
00:23:22,800 --> 00:23:26,640
>> Am terminat acum, dar, din nou, eu sunt un computer pe care se poate face numai ceea ce mi sa spus să fac,

394
00:23:26,640 --> 00:23:30,120
și amintirea mea abia acum este că am făcut de fapt doar un pic de lucru.

395
00:23:30,120 --> 00:23:31,700
Ceva sa schimbat aici.

396
00:23:31,700 --> 00:23:37,100
Deci, eu nu am confirmat vizual punct de vedere tehnic sau algoritmic că această listă este, într-adevăr sortate.

397
00:23:37,100 --> 00:23:40,720
Deci, doar pentru o bună măsură, doar pentru a fi anal cu privire la acest lucru, hai sa facem asta mai mult timp 1.

398
00:23:40,720 --> 00:23:44,040
Deci, 1 și 2, 2 și 3, 3 și 4. Și știi ce?

399
00:23:44,040 --> 00:23:46,190
Doar pentru o bună măsură, am de gând să păstreze piesa de pe mâna mea de data asta

400
00:23:46,190 --> 00:23:51,110
câte swap-uri fac doar pentru ca stiu cat de mult munca pe care am făcut de fapt.

401
00:23:51,110 --> 00:23:56,930
3 și 4, 4 și 5, 5 și 6, 6 și 7, 7 și 8. Nici un swap.

402
00:23:56,930 --> 00:24:00,800
Așa că acum aș fi în mod legitim un idiot de a face acest lucru din nou

403
00:24:00,800 --> 00:24:03,330
pentru că dacă am făcut nici o lucrare prin acest trecere a oamenilor,

404
00:24:03,330 --> 00:24:06,710
atunci în mod clar că o să se întâmple din nou, în cazul în care nici unul dintre ei este un fel de aleatoriu

405
00:24:06,710 --> 00:24:10,410
adversarially se deplasează în jurul valorii de. Asa ca acum pot opri.

406
00:24:10,410 --> 00:24:15,120
Acum, haideți să punem întrebarea, cât de mult de lucru sa dureze de fapt mine?

407
00:24:15,120 --> 00:24:18,260
Câți pași ai dura asta? N >> pătrat.

408
00:24:18,260 --> 00:24:20,400
Da, așa n pătrat. În cazul în care nu veți obține n pătrat de la?

409
00:24:20,400 --> 00:24:22,660
Trebuie să verifice fiecare cilindrilor -

410
00:24:22,660 --> 00:24:26,530
Există numere n, și va trebui să verifice fiecare număr cu numerele n celelalte.

411
00:24:26,530 --> 00:24:29,030
Bine. Deci, e >> n pătrat. Bine >>.

412
00:24:29,030 --> 00:24:31,060
>> Deci, se simte ca și cum s-ar putea foarte bine să fie n pătrat, nu?

413
00:24:31,060 --> 00:24:33,820
Au n dintre aceste tipi, 8 în mod special în acest caz,

414
00:24:33,820 --> 00:24:37,590
dar de fiecare dată am trecut prin această listă am fost comparat prima persoană împotriva secunde,

415
00:24:37,590 --> 00:24:39,650
doua impotriva treilea din nou și din nou și din nou,

416
00:24:39,650 --> 00:24:42,450
și când am ajuns la final, ceea ce am făcut? L-am refăcut.

417
00:24:42,450 --> 00:24:46,280
Deci, dacă am generaliza această explicație, ne-am n persoane

418
00:24:46,280 --> 00:24:51,090
si eu sunt de luare, în mod evident, 8 etape, n trepte, de fiecare dată când mă duc prin acest algoritm.

419
00:24:51,090 --> 00:24:56,070
Dar de câte ori, în cel mai rău caz nu trebuie să treacă prin această listă de persoane?

420
00:24:56,070 --> 00:24:59,370
[Elev] N ori. Probabil n >>, dreapta, pentru că, în cel mai rău caz,

421
00:24:59,370 --> 00:25:03,410
ceea ce este, probabil, cel mai grav caz de amenajarea acestor tipi de la get-du-te?

422
00:25:03,410 --> 00:25:06,520
În cazul în care acestea sunt complet inversat ordinea

423
00:25:06,520 --> 00:25:09,310
deoarece presupun doar mental, hai - Care e numele tău? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Bine. Deci Bowen, vino aici doar pentru un moment.

425
00:25:12,510 --> 00:25:16,150
>> Să presupunem că Bowen a fost aici la începutul algoritmului,

426
00:25:16,150 --> 00:25:19,790
și nu știm ce toată lumea este, dar aici Bowen, în conformitate cu acest algoritm -

427
00:25:19,790 --> 00:25:23,820
și, dacă doriți să vă plimbați cu mine - este de gând să bubble sus, așa cum a făcut prima dată în jurul valorii de,

428
00:25:23,820 --> 00:25:25,740
tot drumul până la sfârșit.

429
00:25:25,740 --> 00:25:29,400
Dar să presupunem că persoana de lângă Bowen a fost numărul 7.

430
00:25:29,400 --> 00:25:33,450
Trebuie să mă duc înapoi și să obțină numărul 7, ceea ce înseamnă că trebuie să merg tot drumul înapoi aici.

431
00:25:33,450 --> 00:25:36,980
Acum trebuie să aibă ca plimbare același cu persoana care este numărul 7.

432
00:25:36,980 --> 00:25:40,140
Dar ce se întâmplă dacă, atunci numărul 6 a fost alături de el, precum și?

433
00:25:40,140 --> 00:25:42,180
Atunci am să mă întorc și să obțină 6.

434
00:25:42,180 --> 00:25:46,490
Deci, din nou, la fiecare iterație a buclei acestui vorbesc cu fiecare dintre oamenii n,

435
00:25:46,490 --> 00:25:50,090
și am putea avea de a face n dintre aceste plimbări să vă asigurați că mă trăgând

436
00:25:50,090 --> 00:25:53,760
toate dintre cele mai mari elemente din spate și înapoi și înapoi la sfârșitul listei.

437
00:25:53,760 --> 00:25:58,230
Deci, lucrurile n n ori este doar de n ori n sau n pătrat.

438
00:25:58,230 --> 00:26:02,050
>> Deci, aici deja avem un algoritm care nu mai este n, care nu mai este log n,

439
00:26:02,050 --> 00:26:04,820
de fapt e mai rău decât orice am făcut înainte.

440
00:26:04,820 --> 00:26:09,840
Deci, un fel de Alex a avut noroc în care am făcut toate lucrările aparent în față pentru ea,

441
00:26:09,840 --> 00:26:14,690
toate lucrările scumpe, astfel încât ea ar putea bucura în acest algoritm de căutare binară,

442
00:26:14,690 --> 00:26:16,420
care este jurnalul de n.

443
00:26:16,420 --> 00:26:18,240
Dar acest lucru este în concordanță cu tema de luni.

444
00:26:18,240 --> 00:26:23,260
Am dat un pic mai mult spațiu, am folosit mai mulți biți, cu scopul de a accelera timpul nostru de funcționare.

445
00:26:23,260 --> 00:26:26,170
Atât de mult ca nu e asta compromis între timp și spațiu,

446
00:26:26,170 --> 00:26:31,060
s-ar putea, de asemenea, fi doar compromisuri între timpul petrecut la fel fata de a face lucrurile să meargă gata

447
00:26:31,060 --> 00:26:35,000
și de executare de fapt un algoritm de căutare cum ar fi. Să încercăm altul.

448
00:26:35,000 --> 00:26:39,050
Daca voi nu m-ar deranja doar rapid reamenajarea vă că pentru a se potrivi din nou,

449
00:26:39,050 --> 00:26:42,240
hai să încercăm ceva puțin diferit în cazul în care nu e chiar atât de simplu

450
00:26:42,240 --> 00:26:45,760
ca doar repara toate greselile perechi, care este super-intuitiv.

451
00:26:45,760 --> 00:26:48,150
Să fim în schimb, un pic mai mult în mod deliberat și de a face acest lucru.

452
00:26:48,150 --> 00:26:51,010
Aceasta prea aș propune este, probabil, destul de intuitiv.

453
00:26:51,010 --> 00:26:55,070
>> Să selectați cea mai mică persoană din lista din nou și din nou. Deci, aici vom merge.

454
00:26:55,070 --> 00:26:57,350
4, esti cea mai mică persoană pe care am văzut până acum, astfel,

455
00:26:57,350 --> 00:27:00,520
așa că am de gând să-mi amintesc că, prin mental doar arătând la tine pentru acum.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Uită de numărul 4. Am găsit doar elementul cel mai mic nou în această listă.

457
00:27:05,020 --> 00:27:07,410
Am de gând să ne amintim că un fel de. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. La revedere. Deci, acum am de gând să-mi amintesc numărul 1.

459
00:27:11,190 --> 00:27:14,790
Știm că 1 este cel mai mic, dar eu sunt calculatorului. Ce se întâmplă dacă există un 0?

460
00:27:14,790 --> 00:27:17,140
Ce se întâmplă dacă există o -1? Trebuie să continui.

461
00:27:17,140 --> 00:27:20,990
Deci 3, 7, 5, nope. Bine. Deci, numarul 1 a fost mai mic.

462
00:27:20,990 --> 00:27:23,640
Permiteți-mi să vă selectați din listă - Vom merge în acest fel -

463
00:27:23,640 --> 00:27:27,760
și ai pus în mod arbitrar la începutul listei.

464
00:27:27,760 --> 00:27:29,740
Acum, așteptați un minut. Am facut un fel de înșelat.

465
00:27:29,740 --> 00:27:34,010
Dacă aceste baieti nu reprezintă o listă de 8 persoane, ci o matrice,

466
00:27:34,010 --> 00:27:37,050
8 bucati de memorie contiguă - te superi pas înapoi pentru o clipă?

467
00:27:37,050 --> 00:27:39,060
Nu e de fapt nici un spațiu pentru tine chiar aici.

468
00:27:39,060 --> 00:27:41,840
Deci, cum putem face loc pentru - care e numele tău? Sammy >>. Sammy >>.

469
00:27:41,840 --> 00:27:43,710
Cum putem face loc pentru Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Am muta n care sunt înaintea mea. Bine >>.

471
00:27:46,760 --> 00:27:48,850
Deci, am putea muta oamenii n care sunt în fața lui,

472
00:27:48,850 --> 00:27:52,400
așa că, dacă vreți să luați un pas deliberată, dramatic la stânga.

473
00:27:52,400 --> 00:27:57,000
Ei au făcut tot ce la unison, dar ultima dată când am scris unele cod,

474
00:27:57,000 --> 00:27:59,740
nu pot sorta de a muta mai multe lucruri deodată.

475
00:27:59,740 --> 00:28:02,450
Am putea face acest lucru într-o buclă, în mișcare toată lumea o dată la un moment dat.

476
00:28:02,450 --> 00:28:04,340
Deci, dacă voi nu s-ar deranja un pas înapoi spre dreapta,

477
00:28:04,340 --> 00:28:07,230
și Sammy, dacă ai putea să pas înapoi, deoarece nu există încă nici o cameră pentru tine,

478
00:28:07,230 --> 00:28:11,420
acum hai sa facem acest lucru. În cazul în care a fost Sammy un moment în urmă? Chiar acolo.

479
00:28:11,420 --> 00:28:16,140
Deci, există un decalaj de acolo. Deci, ai putea muta în locul lui Sammy.

480
00:28:16,140 --> 00:28:20,580
Acum, următoarea persoană în sus și în prezent următoarea persoană pe care, acum următoarea persoană. Acum avem loc pentru Sammy.

481
00:28:20,580 --> 00:28:23,490
Acum, cineva din public - care a fost bun, că a fost actualizată,

482
00:28:23,490 --> 00:28:27,070
m-am simțit un pic consumatoare de timp - ceea ce e mai rapid? Da.

483
00:28:27,070 --> 00:28:29,440
[Elev] O matrice nouă? >> Ce e asta? >> [Elev] O matrice nouă? Bine >>, bine.

484
00:28:29,440 --> 00:28:33,200
>> Deci, în conformitate cu această temă de doar compromisuri, de ce nu am face doar o matrice nouă

485
00:28:33,200 --> 00:28:36,570
 și apoi Sammy va fi de înot în spațiu în fața acestor oameni, de exemplu,

486
00:28:36,570 --> 00:28:39,600
și putem începe doar completarea unui tablou cu totul nou. Că prea ar merge.

487
00:28:39,600 --> 00:28:42,450
Dar eu nu sunt interesat de a petrece mai mult spațiu de astăzi. Ce e altă abordare?

488
00:28:42,450 --> 00:28:46,630
[Elev] Swap. Bine >>. Am putea schimba doar aceste 2 tipi. Care e numele tău?

489
00:28:46,630 --> 00:28:49,390
Mario. Mario >>. Deci Mario, ai fost prezent aici.

490
00:28:49,390 --> 00:28:52,480
Sammy, puteți copii de rezervă doar pentru o clipă? Mario a fost aici.

491
00:28:52,480 --> 00:28:55,830
Nu avem loc pentru tine, așa că, dacă nu te superi dacă o să Sammy este,

492
00:28:55,830 --> 00:29:02,430
vom pune Sammy aici, și acum aș spune că operațiunea schimbarea lui Sammy a fost mult mai rapid.

493
00:29:02,430 --> 00:29:06,370
Am făcut o operație de schimb de acești tipi, sau poate schimba la 2 la tipii ăștia,

494
00:29:06,370 --> 00:29:11,210
dar nu am făcut 1, 2, 3, 4, astfel că se simte mai bine. Acum, așteptați un minut.

495
00:29:11,210 --> 00:29:14,660
Am facut un fel de problema mai rău, deoarece numărul 4, a fost un fel de aproape de început.

496
00:29:14,660 --> 00:29:19,470
Acum, numărul 4 este un pic mai aproape de acest scop, dar nu știam cu adevărat sau pasă de asta.

497
00:29:19,470 --> 00:29:23,330
Deci, aceasta este doar ghinion că numărul 4 este un pic mai departe de locul său destinat.

498
00:29:23,330 --> 00:29:25,110
Așa că hai să repete acum acest algoritm.

499
00:29:25,110 --> 00:29:28,410
>> Pentru a recapitula, atâta timp cât această poveste a fost, tot ce am facut a fost sa se plimbe prin lista de

500
00:29:28,410 --> 00:29:31,130
In cautare de cea mai mică persoană numerotate.

501
00:29:31,130 --> 00:29:34,530
Deci, acum hai sa o facem din nou. Noi nu trebuie să vă faceți griji despre Sammy mai.

502
00:29:34,530 --> 00:29:37,590
Putem merge doar aici. Ooh! Numarul 2. Asta e un număr destul de mic.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Bine, bine.

504
00:29:41,180 --> 00:29:43,770
Și din fericire, prin coincidenta, eu nu trebuie să se mute - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie pentru că e la locul lui chiar acum.

506
00:29:45,910 --> 00:29:48,110
Să facem acest lucru din nou și să ignore aceste 2 tipi.

507
00:29:48,110 --> 00:29:50,460
6. Asta e un număr destul de mic. Ooh! 8 este cu siguranta mai mare.

508
00:29:50,460 --> 00:29:53,410
4. Să se concentreze pe 4. Ooh! 3 este chiar mai bine.

509
00:29:53,410 --> 00:29:58,290
7 și 5. Deci, ce facem acum cu - >> Roger. Roger >>?

510
00:29:58,290 --> 00:30:00,250
Să-l schimbe cu numărul 6.

511
00:30:00,250 --> 00:30:03,570
Deci, dacă 6 și 3 ar dori să facă schimb,

512
00:30:03,570 --> 00:30:07,320
am ajuns acum un fel de norocos în 6 este mai aproape de cazul în care ea ar trebui să fie,

513
00:30:07,320 --> 00:30:10,300
dar e doar o coincidență aici. Așa că hai să mergem acum aici.

514
00:30:10,300 --> 00:30:13,430
8 este un număr destul de mic. Ooh! 4 este mai mic.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Ce facem acum? Swap >>. Exact >>.

516
00:30:17,130 --> 00:30:19,010
Deci, acum hai sa facem acest gen de repede.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. În cazul în care se merge 5? Bine. Bine.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 ajunge la stea unde este. Care e numele tău? Rosalie >>.

519
00:30:28,380 --> 00:30:31,770
Rosalie ajunge să stea unde este. 7 ajunge la - Hai să vedem. 7, 8. Bine.

520
00:30:31,770 --> 00:30:35,100
Deci, 7 ajunge la stea acolo unde ea este. Care e numele tău? Amna >>. Amna >>.

521
00:30:35,100 --> 00:30:39,670
>> Deci, Amna ajunge să stați în cazul în care ea este, și numărul 8 este deja în cazul în care el acum ar trebui să fie.

522
00:30:39,670 --> 00:30:43,960
Bine, bine. Se simte ca și cum am crea doar locul de muncă pentru noi aici, totuși.

523
00:30:43,960 --> 00:30:47,440
Cât este în cele din urmă timpul de rulare al acestui algoritm?

524
00:30:47,440 --> 00:30:51,900
Dacă ne gândim la acești oameni care nu ar fi 8, dar cum n? >> E nr.

525
00:30:51,900 --> 00:30:55,440
E n pași, dar suntem de verificare de fiecare dată singur.

526
00:30:55,440 --> 00:30:57,570
Bine. N dar tu de verificare de fiecare dată?

527
00:30:57,570 --> 00:31:03,450
Bine, dar dacă e n etape, nu ar trebui să am putut să vă sorta de a merge doar 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Bine, asta e o mare diferenta.

529
00:31:05,590 --> 00:31:08,050
Deci, n pătrat de ce? Ce se întâmplă cu adevărat?

530
00:31:08,050 --> 00:31:12,130
Sunt oameni n în această listă, dar pentru a găsi cea mai mică persoană din lista

531
00:31:12,130 --> 00:31:16,200
în cel mai rău caz, câți pași trebuie sa iau? N. >>

532
00:31:16,200 --> 00:31:19,160
>> N, dreapta, pentru că, în cel mai rău caz, numărul 1 este tot drumul acolo,

533
00:31:19,160 --> 00:31:20,990
așa că trebuie să du-te pe el sau ea.

534
00:31:20,990 --> 00:31:25,500
Și apoi, când am dat seama în cele din urmă 1 a fost mai mic, atunci este destul de rapid pentru a le schimba.

535
00:31:25,500 --> 00:31:28,450
Dar acum trebuie să înceapă de la început și căutați pentru cine?

536
00:31:28,450 --> 00:31:31,980
Persoana imediat mai mică, care este 2. În cazul în care, în cel mai rău caz este 2?

537
00:31:31,980 --> 00:31:34,320
Oh, Doamne. E tot drumul până aici la sfârșitul anului.

538
00:31:34,320 --> 00:31:37,000
Așa că acum am făcut doar un alt pași n, n alte trepte.

539
00:31:37,000 --> 00:31:41,200
Și dacă avem oameni n și, în cel mai rău caz mai mic persoana este n câțiva pași,

540
00:31:41,200 --> 00:31:45,230
asta e din nou de n ori n, și așa am din nou, au n pătrat.

541
00:31:45,230 --> 00:31:47,280
Acest lucru nu se simte prea bine.

542
00:31:47,280 --> 00:31:52,150
Și, de fapt, chiar și în cel mai bun caz - să presupunem că ele încep sortate -

543
00:31:52,150 --> 00:31:59,080
câți pași e nevoie de mine folosirea acestui algoritm pentru a sorta aceste persoane n?

544
00:31:59,080 --> 00:32:01,010
N pătrat. >> Am auzit n pătrat. De ce n pătrat?

545
00:32:01,010 --> 00:32:05,240
Pentru că tot trebuie să verifice de fiecare dată singur. Da >>.

546
00:32:05,240 --> 00:32:08,060
Și trebuie să le schimba. Chiar dacă >> noi, oamenii, sunt un fel de atotștiutor

547
00:32:08,060 --> 00:32:10,770
în sensul vizual ca putem doar un fel de a vedea că acest lucru este sortat,

548
00:32:10,770 --> 00:32:12,140
un computer nu este asa de destept.

549
00:32:12,140 --> 00:32:14,040
O să uite aici și aici și aici,

550
00:32:14,040 --> 00:32:16,610
dar dacă ceea ce se caută este cel mai mic element,

551
00:32:16,610 --> 00:32:22,110
tu doar știi că ai găsit cel mai mic element de ce punct? Odată ce ești la sfârșitul anului.

552
00:32:22,110 --> 00:32:25,880
Dar la acel moment le-ați găsit doar elementul cel mai mic curent.

553
00:32:25,880 --> 00:32:28,810
Tu nu știi neapărat altceva despre starea lumii.

554
00:32:28,810 --> 00:32:30,880
Deci, va trebui să merg din nou și din nou și din nou.

555
00:32:30,880 --> 00:32:34,880
>> Deci, de data asta chiar nu arata prost pentru că eu sunt de verificare, ok, 2, tu ești cel mai mic,

556
00:32:34,880 --> 00:32:37,530
dar nu știu că, în total încă.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Bine, bine. 2 a fost într-adevăr cel mai mic.

558
00:32:41,090 --> 00:32:43,150
Acum, hai să găsim cea mai mică următoare. Bine.

559
00:32:43,150 --> 00:32:48,350
3, sunteți în prezent cel mai mic. Să vedem. 4, 5, 6, 7, 8. Bine, am avut noroc din nou.

560
00:32:48,350 --> 00:32:53,170
3 a fost, într-adevăr, în locul potrivit. Dar am de gând să continui să faci asta din nou și din nou și din nou.

561
00:32:53,170 --> 00:32:55,990
Cum putem face vreodată atât de ușor mai bine?

562
00:32:55,990 --> 00:33:00,120
În loc de a avea oameni bule de până la cel mai mic perechilor cel mai mare la

563
00:33:00,120 --> 00:33:04,350
și în loc de a merge înainte și înapoi prin lista de selectarea persoana cea mai mică, apoi,

564
00:33:04,350 --> 00:33:09,780
de ce nu ne introduce în locul acestor persoane într-o etapă nouă listă cu pas?

565
00:33:09,780 --> 00:33:13,080
Să încercăm asta. Acum, lasă-mă să sun acest fel inserarea lucru.

566
00:33:13,080 --> 00:33:17,250
Deci, iată-ne aici. Numărul 1. Nu-mi pasă de nimeni altcineva în această listă.

567
00:33:17,250 --> 00:33:21,310
Scopul meu acum este de a pune numarul 1 la începutul unei liste sortate.

568
00:33:21,310 --> 00:33:23,910
Și am de gând să propună, deoarece am doar 8 bucăți de memorie,

569
00:33:23,910 --> 00:33:28,670
arbitrar, chiar acum am zidul dintre lista mea presupune nesortate,

570
00:33:28,670 --> 00:33:32,740
și oricine care este în spatele meu am de gând să pretindă este sortat.

571
00:33:32,740 --> 00:33:34,680
Deci, acum avem numărul 1.

572
00:33:34,680 --> 00:33:39,240
Vreau să-l introduceți în lista mea sortate, așa că am de gând să se mute peretele meu aici,

573
00:33:39,240 --> 00:33:43,930
si acum am pretind această listă este sortată, această listă este nesortate - cel puțin măsura în care știu.

574
00:33:43,930 --> 00:33:46,070
Eu nu pot vedea toate numerele dintr-o dată.

575
00:33:46,070 --> 00:33:49,000
>> Acum se întâmplă să întâlnesc numărul 2. Ce fac cu el?

576
00:33:49,000 --> 00:33:54,380
Te-am insera acum în lista sortată. Dar observați cât de ușor a fost.

577
00:33:54,380 --> 00:33:59,650
Trebuie doar să te uiți. Numărul 1 este acolo. Oh, evident 2 merge la partea de numărul 1.

578
00:33:59,650 --> 00:34:03,700
Acum ce fac cu 3? Te-am inserați în lista sortată. Dar asta a fost super usor.

579
00:34:03,700 --> 00:34:07,250
Acest lucru este foarte usor, acest lucru este super usor, acest lucru este super usor, super usor usor, super.

580
00:34:07,250 --> 00:34:12,790
Și acum totul este sortat în spatele meu, și cât de multe măsuri care să ia făcut?

581
00:34:12,790 --> 00:34:15,620
[Elevii] N. >> Deci e doar n. Am avut noroc.

582
00:34:15,620 --> 00:34:18,860
A fost doar n de ce? >> [Elev] Pentru că lista a fost sortate.

583
00:34:18,860 --> 00:34:21,630
Lista este deja sortat. Așa că am avut noroc.

584
00:34:21,630 --> 00:34:25,639
Dar am conceput un algoritm de această dată care beneficiaza acest tip de noroc,

585
00:34:25,639 --> 00:34:29,420
că cel mai bun scenariu, prin faptul că nu mai pierdeti timpul inutil.

586
00:34:29,420 --> 00:34:31,750
Deci, acum avem ceea ce vom numi felul bule

587
00:34:31,750 --> 00:34:33,949
în cazul în care oamenii fel de bule de până perechilor.

588
00:34:33,949 --> 00:34:38,100
Avem acum un fel de selecție în cazul în care ne smulge mai mic persoana din nou și din nou.

589
00:34:38,100 --> 00:34:42,350
Și acum avem un fel de inserare acolo unde am cam pus în mod proactiv persoane care fac parte

590
00:34:42,350 --> 00:34:45,000
într-o listă din ce în ce sortate.

591
00:34:45,000 --> 00:34:49,679
Dacă am putea, o rundă de aplauze pentru tipii ăștia aici. [Aplauze]

592
00:34:49,679 --> 00:34:52,310
Să luăm de 5 minute de pauză aici.

593
00:34:52,310 --> 00:34:55,139
Și când ne vom întoarce, vom sufla toate aceste algoritmi de apă

594
00:34:55,139 --> 00:35:00,260
cu ceva mai bun. Bine. Mulțumesc foarte mult. Aveți posibilitatea să păstrați cei ca suveniruri.

595
00:35:01,710 --> 00:35:04,330
Bine. Ne-am întors.

596
00:35:04,330 --> 00:35:08,420
>> Și trecerea în revistă foarte repede, am avut aceste abordări diferite la 3 sortarea,

597
00:35:08,420 --> 00:35:13,000
Ideea de care a fost pentru a ajunge la punctul în care cineva ca Alex

598
00:35:13,000 --> 00:35:16,930
ar putea căuta o listă de numere mai repede decât ar putea cineva ca Sean.

599
00:35:16,930 --> 00:35:19,830
Și chiar dacă avem astfel de exemple simple, cu 8 numere,

600
00:35:19,830 --> 00:35:24,000
ai putea extrapola cu usurinta la 8 pagini web, 8 miliarde de pagini web,

601
00:35:24,000 --> 00:35:26,680
sau 800 milioane de prieteni pe Facebook.

602
00:35:26,680 --> 00:35:30,090
Deci, acești algoritmi pot fi scalate cu siguranță la acele tipuri de valori,

603
00:35:30,090 --> 00:35:32,300
iar ideile sunt în cele din urmă la fel.

604
00:35:32,300 --> 00:35:36,140
Deci, un fel balon a fost primul care am un fel de bule de aer în sus cea mai mare persoană

605
00:35:36,140 --> 00:35:39,110
tot drumul spre dreapta prin schimbarea perechilor de oameni.

606
00:35:39,110 --> 00:35:42,040
Apoi am avut ceea ce vom numi un fel de selecție în cazul în care am un pic mai mult în mod deliberat

607
00:35:42,040 --> 00:35:46,480
se tot uita prin lista, selectând cel mai mic număr din nou și din nou și din nou,

608
00:35:46,480 --> 00:35:49,530
rezultatul logic al, care este faptul că lista este sortată în cele din urmă.

609
00:35:49,530 --> 00:35:53,780
Apoi, în al treilea, am introdus oameni în locul lor corespunzătoare,

610
00:35:53,780 --> 00:35:57,720
si am facut un exemplu foarte contrived în această listă a fost deja sortate,

611
00:35:57,720 --> 00:36:01,100
dar care a fost pentru a trimite mesajul că, în cazul de sortare inserarea lui,

612
00:36:01,100 --> 00:36:02,670
puteți obține norocos.

613
00:36:02,670 --> 00:36:07,930
În cazul în care numerele sunt deja sortate, se doar de gând să ia măsuri pentru a vă N confirma cât de mult,

614
00:36:07,930 --> 00:36:10,870
întrucât fel de selecție ești viziune tunel un pic mai mult

615
00:36:10,870 --> 00:36:14,360
și nu-și dau seama niciodată că lista este deja sortat.

616
00:36:14,360 --> 00:36:16,830
Deci, hai sa vedem un fel balon în acțiune aici.

617
00:36:16,830 --> 00:36:19,590
În următorul exemplu, suntem pe cale de a vedea bare verticale

618
00:36:19,590 --> 00:36:23,030
înălțimi ale căror numere reprezintă, astfel încât să putem rezolva de sortare vizualizează întâmpla.

619
00:36:23,030 --> 00:36:26,630
Cel mai mic bar, este mai mic numărul, cu atât mai mare bara, cu atât mai mare numărul.

620
00:36:26,630 --> 00:36:28,860
>> Și noi vom juca la această viteză prestabilită.

621
00:36:28,860 --> 00:36:33,460
Se va muta prea repede pentru acum, dar rosu este ceea ce se arată 2 baruri

622
00:36:33,460 --> 00:36:35,480
fiind comparat cot la cot.

623
00:36:35,480 --> 00:36:39,520
Și dacă te uiți cu atenție, ceea ce se întâmplă este că, dacă barele sunt în afara de ordine,

624
00:36:39,520 --> 00:36:42,300
unul mai mic este mutat la stânga, una mai mare la dreapta,

625
00:36:42,300 --> 00:36:44,360
și apoi vă păstrați avansează.

626
00:36:44,360 --> 00:36:48,520
Deci, dacă facem acest lucru din nou și din nou, observați că cele mai mici baruri

627
00:36:48,520 --> 00:36:51,090
sunt de gând să păstreze tarasc drumul lor spre stânga

628
00:36:51,090 --> 00:36:54,130
și cele mai mari barele sunt de gând să păstreze modul lor de a se tarasc dreapta.

629
00:36:54,130 --> 00:36:58,490
Și într-adevăr, suntem de pornire pentru a vedea un model tot drumul pe partea dreaptă

630
00:36:58,490 --> 00:37:04,790
la fel cum am vazut 8 și apoi în cele din urmă barbotare 7 până la capătul listei noastre umane.

631
00:37:04,790 --> 00:37:08,750
Deci, acest lucru se întâmplă pentru a obține foarte rapid un pic plictisitor, asa ca lasa-ma opreasca asta pentru un moment.

632
00:37:08,750 --> 00:37:10,980
Lasă-mă să modificați viteza de a fi mult mai rapid.

633
00:37:10,980 --> 00:37:15,380
Nu mă schimbă algoritmul, eu doar a face animație se întâmple mai repede.

634
00:37:15,380 --> 00:37:18,410
Totusi sortare cu bule, acelasi algoritm,

635
00:37:18,410 --> 00:37:21,910
dar acum puteți vedea mult mai repede decât Demonstrația noastră verbală

636
00:37:21,910 --> 00:37:25,900
faptul că cele mai mari elemente sunt într-adevăr barbotare până la partea de sus.

637
00:37:25,900 --> 00:37:29,860
>> Ca o paranteza, aceste pătrate mici de la stânga jos și dreapta-jos

638
00:37:29,860 --> 00:37:33,520
sunt doar mici reamintiri cu privire la cât de multe comparații faci.

639
00:37:33,520 --> 00:37:37,620
Dar pentru acum, ne putem concentra pe piramida care durează formă, și acolo se duce.

640
00:37:37,620 --> 00:37:41,510
Cel mai mic element este pe partea stângă, cea mai mare pe dreapta, și orice altceva în între.

641
00:37:41,510 --> 00:37:44,470
Acum, haideți să aruncăm o privire la locul de sortare de selecție.

642
00:37:44,470 --> 00:37:47,260
Am de gând să merg mai departe și a lovit Stop. Vom obține un nou set aleator de bare.

643
00:37:47,260 --> 00:37:50,930
Sortare de selecție, rechemare, trece prin lista de nou și din nou și din nou,

644
00:37:50,930 --> 00:37:54,900
plucking în cel mai mic element. Deci, aici este un fel de selecție.

645
00:37:54,900 --> 00:37:58,390
Se pare ca exista lucru mai intampla acum, pentru că nu suntem compararea perechilor

646
00:37:58,390 --> 00:38:02,590
dar suntem rezolva doar de cires alege cele mai mici elemente de la dreapta la stânga.

647
00:38:02,590 --> 00:38:06,890
, Care a avut foarte putin timp, astfel încât există o dihotomie deja.

648
00:38:06,890 --> 00:38:11,820
Doar pentru că un algoritm este declarat a lua n timp pătrat, cum ar fi un fel cu bule

649
00:38:11,820 --> 00:38:16,100
și, ca un fel de selecție, cele mai grave sunt într-adevăr de ori caz de funcționare.

650
00:38:16,100 --> 00:38:21,790
De exemplu, în cazul, să zicem, un fel de selecție,

651
00:38:21,790 --> 00:38:27,240
Eu de fapt, am selectarea mai mic persoana si punerea el sau ea aici,

652
00:38:27,240 --> 00:38:29,620
atunci eu o fac din nou, atunci o fac din nou,

653
00:38:29,620 --> 00:38:32,070
dar a existat o ușoară optimizare-am putea face.

654
00:38:32,070 --> 00:38:35,040
>> De îndată ce m-am mutat aici, numărul 1 - Sammy, în acest caz -

655
00:38:35,040 --> 00:38:38,630
ceea ce am nevoie pentru a face cu el după aceea? >> [Elev] Lasă-l.

656
00:38:38,630 --> 00:38:40,140
Lasă-l, nu? Nimic.

657
00:38:40,140 --> 00:38:44,310
Nu am nevoie să vorbesc niciodată cu Sammy din nou, pentru că dacă aș fi ales cel mai mic element

658
00:38:44,310 --> 00:38:48,580
și pune-l aici, de ce timp de deșeuri care merg la sfarsitul listei întreaga mea?

659
00:38:48,580 --> 00:38:54,590
La urmatoarea iteratie permiteți-mi să se mute de fapt, doar la numărul 2, numai la numărul 3.

660
00:38:54,590 --> 00:38:57,640
Deci, în realitate, nu am fost face lucruri n n ori.

661
00:38:57,640 --> 00:39:05,380
Am fost de a face lucruri n, atunci n - 1 lucrurile, atunci n - 2 lucruri, atunci n - 3 lucruri,

662
00:39:05,380 --> 00:39:07,080
apoi n - 4, punct, punct, punct.

663
00:39:07,080 --> 00:39:09,470
Avem un pic de o serie geometrică, ceea ce înseamnă doar

664
00:39:09,470 --> 00:39:11,450
adăugați numere progresiv mai mici.

665
00:39:11,450 --> 00:39:17,940
Nu este n + n + n + n, dar n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
Și ce, în general, funcționează pentru a fi -

667
00:39:21,380 --> 00:39:24,280
Am de gând să încurce placa mea aici doar pentru o clipă -

668
00:39:24,280 --> 00:39:28,990
care este de gând să lucreze pentru a fi ceva de genul n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
dacă ne doar un fel de privire la partea din spate a unei cărți de matematică în cazul în care aveți toate ieftin foi

670
00:39:31,930 --> 00:39:33,410
pentru formulele.

671
00:39:33,410 --> 00:39:37,760
Dacă adăugați ceva n + n - 1 + n - 2, funcționează pentru a fi ceva de genul asta.

672
00:39:37,760 --> 00:39:42,320
Și dacă ne-am cam înmulțiți asta, care este n pătrat minus n / 2.

673
00:39:42,320 --> 00:39:46,400
Am spunea n pătrat, deși, și asta pentru că am fost un fel de a lua o scurtătură mentală

674
00:39:46,400 --> 00:39:51,950
deoarece, în realitate, n pătrat minus n împărțit la 2 este într-adevăr numărul real de pași

675
00:39:51,950 --> 00:39:55,510
că un algoritm de sortare ca ar avea de selecție, dacă dorim cu adevărat numărate până

676
00:39:55,510 --> 00:39:58,800
toate aceste comparații și toate lucrările ocupat mic făceam.

677
00:39:58,800 --> 00:40:03,210
Dar sincer, o dată n ajunge să fie ca un milion sau un miliard, care naiba îi pasă

678
00:40:03,210 --> 00:40:07,160
daca faci un miliard de minus squared un miliard de împărțit cu 2?

679
00:40:07,160 --> 00:40:09,320
Un miliard de pătrat este un număr foarte mare.

680
00:40:09,320 --> 00:40:13,580
Puteți lua un alt miliard de pe ea cu - n. Nu e o astfel de afacere mare.

681
00:40:13,580 --> 00:40:18,770
Deci, mai mare cu numerele ajunge, în mai puțin importante acești termeni mai mici sunt ordonate.

682
00:40:18,770 --> 00:40:24,230
Cui îi pasă dacă ai împărți la 2, dacă vorbești despre quadrillions de numărul de pași?

683
00:40:24,230 --> 00:40:29,710
>> Deci, în general, oamenii de stiinta de calculator au tendinta de a arunca totul, dar cel mai mare pe termen lung,

684
00:40:29,710 --> 00:40:33,140
si am doar un fel de a simplifica lumea și să spunem că algoritmul

685
00:40:33,140 --> 00:40:38,130
a luat măsuri de aproximativ n pătrat. Asta e timpul de execuție al unui algoritm.

686
00:40:38,130 --> 00:40:40,760
Deci, ne vom întoarce la acest lucru în doar un moment cu câteva exemple concrete,

687
00:40:40,760 --> 00:40:45,940
dar pentru acum, asta e un fel de motivație din spatele intuitivă simplifică doar lumea noastră

688
00:40:45,940 --> 00:40:51,170
și vorbesc despre cei mai importanți termeni, mai degrabă decât a intra în toate aceste formule de lux.

689
00:40:51,170 --> 00:40:53,540
Așa că a fost un fel de selecție, și am luat un pic noroc acolo.

690
00:40:53,540 --> 00:40:57,360
Să ne uităm la fel de inserție. Lasă-mă să mergeți mai departe și a începe aceasta, de asemenea.

691
00:40:57,360 --> 00:41:00,330
Acum, observați modelul care se întâmplă este un pic diferit,

692
00:41:00,330 --> 00:41:03,410
și am început cu numere aleatoare,

693
00:41:03,410 --> 00:41:06,890
dar dacă socotim de fapt, până numărul de pași, în cel mai rău caz,

694
00:41:06,890 --> 00:41:11,070
în cazul în care lista a început totul, în ordinea corectă,

695
00:41:11,070 --> 00:41:13,380
ne-ar lua doar măsuri pentru a realiza n la fel de mult.

696
00:41:13,380 --> 00:41:18,240
>> Dar, dacă lista au fost de fapt invers - de exemplu, în acest caz, aici -

697
00:41:18,240 --> 00:41:23,860
apoi observați avem de fapt de a face munca mult mai mult în acest caz.

698
00:41:23,860 --> 00:41:27,080
Și ar trebui să se simtă un fel de a vă ca aceasta este un fel de a lucra mai greu

699
00:41:27,080 --> 00:41:30,900
pentru a obține aceste elemente mai mici, la stânga, și asta pentru că avem ghinion.

700
00:41:30,900 --> 00:41:34,210
Lista a fost sortată accidental în sens invers.

701
00:41:34,210 --> 00:41:38,110
Prin contrast, cu insertie fel, dacă ne imita ceea ce am făcut cu oamenii noștri aici

702
00:41:38,110 --> 00:41:42,670
prin începând cu toată lumea sortati si apoi de a începe, este un algoritm destul de bine, nu?

703
00:41:42,670 --> 00:41:45,010
E deja, de fapt, sortate.

704
00:41:45,010 --> 00:41:48,670
Deci, haideți să încercăm a rezuma exact cât de mult timp aceste lucruri sunt luați-ne

705
00:41:48,670 --> 00:41:52,360
prin introducerea doar un pic de jargon sau notație care este de fapt mult mai simplă

706
00:41:52,360 --> 00:41:54,320
decât un fel de fanciness sugerează.

707
00:41:54,320 --> 00:41:59,030
Acest lucru aici, acest O mare pe ecran, ceea ce este un om de stiinta de calculator va folosi, în general,

708
00:41:59,030 --> 00:42:03,640
pentru a descrie timpul cel mai grav caz de funcționare al unui algoritm.

709
00:42:03,640 --> 00:42:07,360
>> Din nou, de cel mai rău caz, e total dependentă de context.

710
00:42:07,360 --> 00:42:10,890
Ceea ce vrem să spunem prin cel mai rău caz, în totalitate variază în funcție de problema despre care vorbim.

711
00:42:10,890 --> 00:42:14,550
Dar, în cazul de sortare, ceea ce este cel mai rău scenariu posibil?

712
00:42:14,550 --> 00:42:17,860
Totul este invers, deoarece doar se simte ca și cum ceea ce înseamnă o mulțime de lucru pentru noi.

713
00:42:17,860 --> 00:42:21,330
Am notat câteva dintre algoritmi care le-am văzut până acum:

714
00:42:21,330 --> 00:42:24,930
căutare liniară, cum ar fi binar de căutare cu cartea de telefon sau bucăți de hârtie,

715
00:42:24,930 --> 00:42:28,960
apoi sortați balon, sortare de selecție, precum și inserarea fel cum am văzut cu oamenii noștri,

716
00:42:28,960 --> 00:42:31,770
și apoi o altă natură care se în cele din urmă va fi numit un fel îmbinare.

717
00:42:31,770 --> 00:42:37,710
Deci, în căutarea liniară, în cel mai rău caz, câți pași e nevoie pentru a găsi numărul 7

718
00:42:37,710 --> 00:42:40,690
în cazul în care există uși n ca Sean cu care se confruntă? >> [Elev] N.

719
00:42:40,690 --> 00:42:44,180
N. Deci, vom scrie mare O din nr.

720
00:42:44,180 --> 00:42:47,010
Mă duc să completați în unele spații libere. Aceasta este doar o grilă a matrițelor.

721
00:42:47,010 --> 00:42:52,990
Dar, în cel mai bun caz, cu căutare liniară, 7 ar fi fost la început a listei,

722
00:42:52,990 --> 00:42:55,520
și Sean ar fi inceput sa caute la începutul listei.

723
00:42:55,520 --> 00:42:58,940
Deci, dacă sunteți utilizând căutarea liniară și doar verificare la stânga la dreapta sau de la dreapta la stânga, poate -

724
00:42:58,940 --> 00:43:02,650
sunt echivalente - în cel mai bun caz câți pași ar putea căutare liniară,

725
00:43:02,650 --> 00:43:05,550
cum ar fi algoritmul lui Sean, ia? Doar 1 pas.

726
00:43:05,550 --> 00:43:09,450
>> Așa că am de gând să spun că e notația omega.

727
00:43:09,450 --> 00:43:11,570
Acesta este doar omega de capital.

728
00:43:11,570 --> 00:43:15,000
Omega este doar modul sexy de a spune cel mai bun caz timpul de funcționare.

729
00:43:15,000 --> 00:43:18,900
Deci, în cel mai bun caz timpul de rulare este un singur pas sau un număr constant de pași -

730
00:43:18,900 --> 00:43:24,270
1 în acest caz -, dar, în cel mai rău caz, Big O, aceasta este, de fapt pași n.

731
00:43:24,270 --> 00:43:28,110
Și asta aici, teta, nu suntem de fapt de gând să se uite la dreapta acum.

732
00:43:28,110 --> 00:43:30,090
Nu e relevant pentru acest exemplu particular.

733
00:43:30,090 --> 00:43:31,990
Dar acum să încercăm căutare binară.

734
00:43:31,990 --> 00:43:35,990
În cel mai rău caz, cu binar de căutare, câți pași este ea de gând să ia pentru a găsi numărul 7

735
00:43:35,990 --> 00:43:38,340
sau tot ce ne ce cautati? >> [Elev] n Log.

736
00:43:38,340 --> 00:43:40,980
Încă de gând să ia n log, deoarece la fel ca Alex avut ghinion

737
00:43:40,980 --> 00:43:44,030
când am lucrat cu adevărat, prin problema metodic

738
00:43:44,030 --> 00:43:48,220
și ea nu a găsit numărul 7 până la ușa ultimul se uita la,

739
00:43:48,220 --> 00:43:51,720
chiar dacă, în echitate, ea a ajuns să arunce anumite uși de-a lungul drum,

740
00:43:51,720 --> 00:43:56,920
binar de căutare, în cel mai rău caz are un timp de funcționare a log n.

741
00:43:56,920 --> 00:43:59,230
Și din nou, că vorbește la această divizare și cucerirea.

742
00:43:59,230 --> 00:44:01,140
Dar ce se intampla in cel mai bun caz?

743
00:44:01,140 --> 00:44:04,790
Și Alex experimentat de fapt, că cel mai bun caz drept, atunci când ea a venit pe scenă.

744
00:44:04,790 --> 00:44:07,290
Câți pași au ca ia in cautare binara? >> [Elev] 1.

745
00:44:07,290 --> 00:44:09,380
1, doar pentru că ea a avut noroc.

746
00:44:09,380 --> 00:44:12,520
Dar asta e bine, deoarece omega se referă la scenarii mai bun caz,

747
00:44:12,520 --> 00:44:15,770
cele mai bune intrări de caz, chiar dacă e doar noroc aleatoare prost.

748
00:44:15,770 --> 00:44:18,900
>> Acum, acest lucru prea vom doar un fel de goale concediu pentru acum.

749
00:44:18,900 --> 00:44:21,010
Ce zici acum de sortare cu bule?

750
00:44:21,010 --> 00:44:24,290
În cel mai rău caz, cu bule de sortare, toată lumea este în ordine inversă,

751
00:44:24,290 --> 00:44:26,380
așa că trebuie să facem o mulțime de bule.

752
00:44:26,380 --> 00:44:30,190
Dar câți pași este faptul că va lua în cel mai rău caz? >> [Elev] pătrat N.

753
00:44:30,190 --> 00:44:32,550
Aceasta a fost n pătrat, pentru că, dacă stai să te gândești,

754
00:44:32,550 --> 00:44:36,410
în cazul în care lista este complet invers - 8 este aici, 1 este aici -

755
00:44:36,410 --> 00:44:40,530
ca lucru începe să fiarbă, numărul 8 este de gând să se mute în acest fel, în acest fel,

756
00:44:40,530 --> 00:44:44,540
în acest fel, în acest fel, dar în cazul în care este numărul 7, în cel mai rău caz?

757
00:44:44,540 --> 00:44:47,720
Aici ea este încă acolo. Deci, noi trebuie să o facem din nou și din nou.

758
00:44:47,720 --> 00:44:53,190
Și asta e în cazul în care vom ajunge pași n, atunci n - 1 pași, atunci n - 2 trepte.

759
00:44:53,190 --> 00:44:55,960
Și dacă vă luați cuvântul meu pentru asta - că, dacă astfel de înmulțiți-l afară,

760
00:44:55,960 --> 00:45:00,110
este aproximativ n pătratul în final cu unele alți termeni pe care le vom ignora doar pentru acum -

761
00:45:00,110 --> 00:45:06,890
apoi, în cel mai rău caz, sortare bubble este n pătrat, da sau de a lua.

762
00:45:06,890 --> 00:45:09,490
Dar ceea ce despre cel mai bun caz, cu un fel bule?

763
00:45:09,490 --> 00:45:13,050
Care este cel mai bun caz? Toate numerele sunt sortate deja.

764
00:45:13,050 --> 00:45:15,920
Și ce a fost euristică am folosit, am folosit trucul,

765
00:45:15,920 --> 00:45:20,110
să realizez că am făcut nici o lucrare și, prin urmare, ar putea opri mai devreme?

766
00:45:20,110 --> 00:45:23,590
[Elev] Check-o o dată. Verificați-l >> dată. Dar ceea ce făceam de-a lungul drum?

767
00:45:23,590 --> 00:45:26,130
Am fost urmărirea de cât de multe am facut swap-urilor.

768
00:45:26,130 --> 00:45:30,650
Și am dat seama daca nu am numărat nici un swap pe degetele mele, apoi am făcut nici o lucrare.

769
00:45:30,650 --> 00:45:34,300
Eu cu siguranță nu ar trebui să încerce să nu faceți nicio lucrare din nou, așa că am pot opri pur și simplu.

770
00:45:34,300 --> 00:45:37,830
>> Deci, în cel mai bun caz de sortare cu bule atunci când lista este deja sortate,

771
00:45:37,830 --> 00:45:41,530
ce-ai spune notația omega este, cel mai bun caz de funcționare timp?

772
00:45:41,530 --> 00:45:48,040
E doar n. Trebuie să facem ceva de lucru, dar trebuie doar să facă în valoare de 1 plimbare de muncă.

773
00:45:48,040 --> 00:45:50,490
Și aici am de gând să părăsească această parte necompletată.

774
00:45:50,490 --> 00:45:52,430
Și acum sortare de selecție.

775
00:45:52,430 --> 00:45:56,010
Fel de selecție ma smulgerea mai mic persoana din nou și din nou.

776
00:45:56,010 --> 00:45:58,380
Și ce am spus timpul de execuție din care a fost?

777
00:45:58,380 --> 00:46:00,590
Asta a fost tăiat în n cel mai rău caz.

778
00:46:00,590 --> 00:46:05,220
Și, din păcate, în cel mai bun caz este, de asemenea, n pătrat

779
00:46:05,220 --> 00:46:08,840
pentru că nu am un fel de vedere omniscient din întreaga lume;

780
00:46:08,840 --> 00:46:13,140
Eu știu doar pe o repetare completă pe care l-am găsit într-adevăr, cea mai mică persoană.

781
00:46:13,140 --> 00:46:15,860
Deci, un fel de fel de selecție e de rahat, în acest sens,

782
00:46:15,860 --> 00:46:17,920
dar capul este un fel e de intuitiv.

783
00:46:17,920 --> 00:46:21,470
Este destul de ușor pentru a coda pentru că tot ce trebuie să faceți este să scrie o serie de bucle imbricate pentru,

784
00:46:21,470 --> 00:46:24,620
de obicei, care trece prin căutarea pentru cel mai mic element

785
00:46:24,620 --> 00:46:27,840
și apoi pune cel mai mic element din care face parte, la sfârșitul listei.

786
00:46:27,840 --> 00:46:29,900
Deci și aici va fi un compromis.

787
00:46:29,900 --> 00:46:34,440
Suma de timp este nevoie să te gândești și să dezvolte efectiv ceva de scrierea de cod

788
00:46:34,440 --> 00:46:39,460
ar putea foarte bine să ia mai mult timp, dacă doriți o performanță mai bună și mai rapid algoritm.

789
00:46:39,460 --> 00:46:41,780
>> Dar, dacă într-adevăr doar un fel de cod ceva până rapid și murdar

790
00:46:41,780 --> 00:46:45,000
și doar un fel de ia ideea stupida posibil vă puteți gândi,

791
00:46:45,000 --> 00:46:47,580
care ar putea dura vă câteva minute pentru a codului, dar cu seturi mari de date

792
00:46:47,580 --> 00:46:49,580
Algoritmul dumneavoastră ar putea dura ore pentru a rula.

793
00:46:49,580 --> 00:46:51,690
Și chiar și eu în facultate ar face, uneori, aceste compromisuri.

794
00:46:51,690 --> 00:46:55,660
Ar fi 3am, am fost încercarea de a analiza o parte foarte mare set de date

795
00:46:55,660 --> 00:46:59,650
legate de cercetarea în domeniul securității făceam, și a fost cheltui 5 minute

796
00:46:59,650 --> 00:47:03,210
tweaking programul meu pentru a analiza datele și du-te la culcare

797
00:47:03,210 --> 00:47:08,420
sau petrece 8 oră obtinerea-l doar dreptul, astfel, ruleaza instantaneu, și nu merg la culcare.

798
00:47:08,420 --> 00:47:10,530
Și deci nu prea e un fel de o decizie conștientă.

799
00:47:10,530 --> 00:47:12,740
Timpul de dezvoltare mai puțin, de mai mult somn.

800
00:47:12,740 --> 00:47:14,780
În retrospectivă, probabil că nu ar trebui să încurajeze faptul că

801
00:47:14,780 --> 00:47:19,120
atunci când scopul aici este de a optimiza calitatea codului,

802
00:47:19,120 --> 00:47:21,280
dar că prea în lumea reală este un foarte rezonabil compromis.

803
00:47:21,280 --> 00:47:25,130
Mai puțin timp, performanța mai puțin sau invers.

804
00:47:25,130 --> 00:47:28,110
Deci, aici vom avea în sfârșit o șansă de a vorbi despre teta.

805
00:47:28,110 --> 00:47:32,830
Theta notație este ceva oamenii de stiinta de calculator pot aduce în conversație

806
00:47:32,830 --> 00:47:36,160
Când Big O și omega se întâmplă să fie aceeași.

807
00:47:36,160 --> 00:47:40,160
Tu spui teta pentru a trimite mesajul într-adevăr că aceasta este un fel de strans legat.

808
00:47:40,160 --> 00:47:43,340
Indiferent dacă scenariul este bun sau rău, e n pătrat.

809
00:47:43,340 --> 00:47:46,510
Deci, nu e doar relevantă în aceste povești aici.

810
00:47:46,510 --> 00:47:48,560
Fel de inserare este ultima ne-am uitat la,

811
00:47:48,560 --> 00:47:50,830
unde am fost doar introducerea pe toți în locul potrivit.

812
00:47:50,830 --> 00:47:54,930
În cel mai bun caz ceea ce a fost timp de funcționare de sortare inserare așa cum am văzut-o aici?

813
00:47:54,930 --> 00:47:57,250
[Elev] cel mai bun caz? >> Cel mai bun caz.

814
00:47:57,250 --> 00:48:00,100
>> Acesta a fost n deoarece, în cel mai bun caz toată lumea sortate,

815
00:48:00,100 --> 00:48:02,580
și Sammy și nimeni altcineva într-adevăr a trebuit să se mute la toate.

816
00:48:02,580 --> 00:48:04,610
Ei au fost deja la locul lor.

817
00:48:04,610 --> 00:48:08,570
Deci, un fel de inserție în cel mai bun caz este, în acest caz, nr.

818
00:48:08,570 --> 00:48:12,770
Dar, în cel mai rău caz e un fel de n pătrat. De ce?

819
00:48:12,770 --> 00:48:16,230
În cazul în care lista mea de om este, în ordine inversă,

820
00:48:16,230 --> 00:48:21,260
Prima dată am începe cu numărul 8 și l-am introduce sau de ei în poziția corectă, care este chiar aici.

821
00:48:21,260 --> 00:48:25,270
Am facut un fel de mișcare în lateral. Tipii ăștia sunt sortate, el sau ea este sortat.

822
00:48:25,270 --> 00:48:28,970
Dar acum se întâmplă să găsească cine urmeaza? >> [Elev] 7.

823
00:48:28,970 --> 00:48:31,250
7 în cel mai rău caz, pentru că e în ordine inversă.

824
00:48:31,250 --> 00:48:34,920
>> Deci, aici este de 7. În cazul în care nu aparține 7? Categoric spatele meu.

825
00:48:34,920 --> 00:48:39,460
Dar acum 7 de fapt, nu apartine imediat în spatele meu, dar în spatele numărul 8,

826
00:48:39,460 --> 00:48:41,880
așa că trebuie să spun, "Scuză-mă, numărul 8, poate, te rog muta în acest fel

827
00:48:41,880 --> 00:48:44,640
"Pentru a face loc pentru 7?" Acum am întâlni 6.

828
00:48:44,640 --> 00:48:48,530
"Oh, scuză-mă, numărul 8 și numărul 7, vă puteți muta pentru a face loc pentru 6?"

829
00:48:48,530 --> 00:48:52,360
Deci, cu alte cuvinte, cu insertie de sortare, chiar dacă nu fac multa miscare,

830
00:48:52,360 --> 00:48:56,330
oamenii din spatele meu fac munca mult mai mult, și că are timp sa coste pe cineva.

831
00:48:56,330 --> 00:48:58,000
Se va costa timp de calculator.

832
00:48:58,000 --> 00:49:01,450
Deci, în cazul de sortare inserție avem încă suferim.

833
00:49:01,450 --> 00:49:06,260
Dacă începeți adunarea numărul total de pași, am sfârși prin a lovit aproximativ n pătrat

834
00:49:06,260 --> 00:49:11,160
deoarece aceste tipi au nevoie pentru a face loc oamenilor de a se introduce din nou în acea listă.

835
00:49:11,160 --> 00:49:15,960
Și astfel, în acest caz, teta nu este doar aplicabilă povestea special la mână.

836
00:49:15,960 --> 00:49:21,100
Asta e tot frumos și bun. Avem aceste moduri diferite de a 3 vorbesc despre timpul de execuție.

837
00:49:21,100 --> 00:49:26,370
Dar ce înseamnă, de fapt, în termeni reali, dacă vom încerca de fapt, pentru a coda un algoritm?

838
00:49:26,370 --> 00:49:31,620
>> Permiteți-mi să propună că există un algoritm chiar mai bine acolo

839
00:49:31,620 --> 00:49:33,740
care se are unele compromisuri.

840
00:49:33,740 --> 00:49:36,890
Vom numi fuzioneze sortare, și e un fel de acest algoritm magic

841
00:49:36,890 --> 00:49:42,840
că doar funcționează mai rapid într-un fel, și este atât de ușor să-și exprime, cel puțin în pseudocod.

842
00:49:42,840 --> 00:49:46,900
Punerea în aplicare a acestui tip de îmbinare algoritm va fi, după cum urmează.

843
00:49:46,900 --> 00:49:50,860
Când ai de dat n elemente - numere de N, N, indiferent de oameni - în primul rând acolo e un cec bun-simț.

844
00:49:50,860 --> 00:49:56,340
Dacă n este mai mic de 2, îmbinare fel doar se oprește. Se întoarce, ca să spunem așa.

845
00:49:56,340 --> 00:50:00,830
De ce ai opri daca n este mai mică de 2? >> [Elevului răspunsul neauzit]

846
00:50:00,830 --> 00:50:04,480
Corect. Și din nou, n nu este numărul din lista, n este mărimea listei.

847
00:50:04,480 --> 00:50:07,660
Dacă n este mai mic de 2, înseamnă că lista este fie 1,

848
00:50:07,660 --> 00:50:09,640
în cazul în care sunteți în mod evident sortati dacă e un număr,

849
00:50:09,640 --> 00:50:11,710
sau 0, caz în care nu mai e nimic pentru a sorta,

850
00:50:11,710 --> 00:50:13,570
asa ca am nevoie de acest tip de cazul de bază.

851
00:50:13,570 --> 00:50:20,350
În cazul în care lista este atât de scurtă, încât nu este nimic de a face, pur și simplu nu face nimic. A reveni.

852
00:50:20,350 --> 00:50:25,090
În caz contrar, sorta jumătatea stângă a elementelor, apoi să sortați jumătatea dreaptă a elementelor,

853
00:50:25,090 --> 00:50:27,410
îmbinați, apoi cele 2 jumatati sortate.

854
00:50:27,410 --> 00:50:32,130
>> Acest tip de pare a fi un pic ieftin prin care îți cer cum să sortați elementele

855
00:50:32,130 --> 00:50:34,900
și tu îmi spui, "Sortare jumătatea stângă, sorta jumătatea din dreapta."

856
00:50:34,900 --> 00:50:37,240
Sunt genul, "În regulă Cum sortați jumătatea stângă?".

857
00:50:37,240 --> 00:50:40,670
"Sortarea jumătatea stângă a jumătatea stângă, sorta jumătatea dreaptă a jumătatea stângă, și apoi făcut."

858
00:50:40,670 --> 00:50:44,060
Ești un fel de ciclic definirea a ceea ce înseamnă pentru a sorta,

859
00:50:44,060 --> 00:50:46,790
dar se pare că e de fapt genial în acest caz.

860
00:50:46,790 --> 00:50:50,230
Nu e adevarat acest ciclu vicios care nu se termină niciodată

861
00:50:50,230 --> 00:50:52,550
pentru că atunci când se încheie? >> [Elev] Când ajunge la 1 lucru.

862
00:50:52,550 --> 00:50:54,220
Atunci când ajunge la 1 lucru.

863
00:50:54,220 --> 00:50:57,850
Deci, chiar dacă s-ar putea începe cu 8 persoane, și spun, "Sortare jumătatea stângă a acestor oameni,

864
00:50:57,850 --> 00:51:00,480
aceste 4 persoane, "atunci eu spun," Cum vă sortați jumătatea stângă? "

865
00:51:00,480 --> 00:51:03,450
"Ei bine, a sorta 2 persoane aici." Și apoi ești ca, "totul bine. Bine,"

866
00:51:03,450 --> 00:51:05,520
"Cum sortați jumătatea stângă a acestor oameni?"

867
00:51:05,520 --> 00:51:09,040
"Doar sorta această persoană 1 aici." Care este revelația genial acum?

868
00:51:09,040 --> 00:51:13,050
Trebuie să sorta 1 persoană. Adoptată. Eu nu trebuie să fac nici o lucrare.

869
00:51:13,050 --> 00:51:16,580
Dar acum trebuie să rezolvăm această persoană, dar sunt o singură persoană, nimic de-a face.

870
00:51:16,580 --> 00:51:21,490
>> Deci, magia aparent este, în acest al treilea pas: fuziona jumatati sortate.

871
00:51:21,490 --> 00:51:25,770
Deci, un fel îmbinare ia această perspectivă genial că, dacă te rupe o problemă mare în jos

872
00:51:25,770 --> 00:51:28,650
in 2 mai mici, de dimensiuni identice probleme

873
00:51:28,650 --> 00:51:32,710
și apoi doar un fel de clei soluțiilor mai mici împreună la sfârșitul anului,

874
00:51:32,710 --> 00:51:34,720
Eu propun ca putem face mai mult, [sunet atingând] mult mai bine

875
00:51:34,720 --> 00:51:38,050
decât oricare dintre fel de selecție sau de sortare inserție.

876
00:51:38,050 --> 00:51:40,690
Am fost într-adevăr ignorând că, pentru o jumătate de oră, dar eu chiar nu știu ce se întâmplă pe

877
00:51:40,690 --> 00:51:45,040
în afara de astăzi. [Zbârnâit sunet] [râsete]

878
00:51:45,040 --> 00:51:49,660
Deci, hai sa vedem daca putem vedea acest lucru cu un pic de ajutor de la prietenul nostru Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Există 2 pași mari în procesul de sortare de îmbinare.

880
00:51:52,810 --> 00:51:56,400
În primul rând, divizat continuu lista de cupe în jumatati

881
00:51:56,400 --> 00:51:59,610
până când vom avea o grămadă de liste cu doar 1 ceașcă în ele.

882
00:51:59,610 --> 00:52:02,150
Nu vă faceți griji în cazul în care o listă conține un număr impar

883
00:52:02,150 --> 00:52:04,830
si nu poti face o tăietură perfect curată între ele.

884
00:52:04,830 --> 00:52:08,740
Doar alege arbitrar, care să includă lista cupa suplimentar inch

885
00:52:08,740 --> 00:52:11,320
Deci, haideți să împartă aceste liste.

886
00:52:12,420 --> 00:52:14,570
Acum avem 2 liste.

887
00:52:18,930 --> 00:52:20,930
Acum avem 4 liste.

888
00:52:25,730 --> 00:52:28,740
Acum avem 8 Lista de preturi cu o singură ceașcă în fiecare listă.

889
00:52:28,740 --> 00:52:31,520
Deci asta e tot pentru pasul 1.

890
00:52:31,520 --> 00:52:37,280
Pentru pasul 2 se îmbina în mod repetat perechi de liste utilizând algoritmul de îmbinare am învățat înainte.

891
00:52:37,280 --> 00:52:44,320
Fuzionarea 108 și 15 ajungem cu lista de 15, 108.

892
00:52:45,240 --> 00:52:51,330
Fuzionarea 50 și 4 am termina cu 4, 50.

893
00:52:51,330 --> 00:52:56,950
Fuzionarea 8 și 42 am termina cu 8, 42.

894
00:52:57,790 --> 00:53:04,360
Și fuzionează 23 și 16 ajungem cu 16, 23.

895
00:53:04,360 --> 00:53:08,030
Acum, toate listele noastre sunt de dimensiuni 2.

896
00:53:08,030 --> 00:53:10,980
Observați că fiecare dintre cele 4 liste este sortat,

897
00:53:10,980 --> 00:53:14,230
astfel încât să putem începe fuzionarea perechi de liste din nou.

898
00:53:14,230 --> 00:53:22,150
Fuzionarea 15 și 108 și 4 și 50 vom lua primul 4, apoi 15,

899
00:53:22,150 --> 00:53:26,250
apoi 50, apoi 108.

900
00:53:26,250 --> 00:53:33,020
Fuzionarea 8, 42 și 16, 23 avem prima 8, apoi 16,

901
00:53:33,020 --> 00:53:37,170
apoi 23, apoi 42.

902
00:53:37,170 --> 00:53:42,490
Deci, acum avem doar 2 liste de marimea 4, fiecare dintre care este sortat.

903
00:53:42,490 --> 00:53:45,940
Deci, acum am îmbina aceste două liste.

904
00:53:45,940 --> 00:53:54,230
În primul rând vom lua 4, apoi vom lua 8, atunci vom lua 15

905
00:53:54,230 --> 00:54:05,280
și 16 și 23 și 42 și 50 și 108.

906
00:54:05,280 --> 00:54:09,020
Și am terminat. Avem acum o listă sortată.

907
00:54:09,020 --> 00:54:13,740
>> Rob a fost un fel de a profita de ceva ce nu am făcut-o încă.

908
00:54:13,740 --> 00:54:16,540
A fost sugerat, dar nu ne-am face de fapt.

909
00:54:16,540 --> 00:54:19,230
El a fost a face ceva fizic cu cupe care sugerează

910
00:54:19,230 --> 00:54:23,680
el a fost petrecut ceva timp în afară de resurse. >> [Elev] Space. A fost >> spațiu.

911
00:54:23,680 --> 00:54:27,360
Faptul că el a avut acest tip de bi-nivel de masă în cazul în care el a avut spatiu aici

912
00:54:27,360 --> 00:54:31,960
și spațiu aici a fost de fapt ceea ce înseamnă că el folosește spațiul de două ori la fel de mult

913
00:54:31,960 --> 00:54:36,390
ca oricare dintre algoritmii noștri de până acum - un fel de inserare, sortare cu bule, sau de selecție sortare -

914
00:54:36,390 --> 00:54:40,780
dar el a fost mobilizarea acest spațiu suplimentar pentru genul de lucruri muta înainte și înapoi

915
00:54:40,780 --> 00:54:42,600
păstrând în același timp lucrurile în ordine.

916
00:54:42,600 --> 00:54:47,540
Și chiar dacă se simte ca și cum am ajuns la o listă sortată, că simtit ca a luat un timp.

917
00:54:47,540 --> 00:54:51,060
În realitate, ceea ce Rob a fost făcut a fost exact acest algoritm.

918
00:54:51,060 --> 00:54:56,780
El a luat prima problema de dimensiune n, împărțit în stânga și o jumătate de jumătatea din dreapta.

919
00:54:56,780 --> 00:54:59,380
Asta e, când sa mutat în cupe. Apoi, el a repetat acest proces.

920
00:54:59,380 --> 00:55:03,390
El a împărțit în 4 2 seturi de 2 aici și aici.

921
00:55:03,390 --> 00:55:08,520
Apoi, el a repetat că procesul împărțit și 2 în 2 seturi de 1 pentru fiecare din aceste cupe diferite.

922
00:55:08,520 --> 00:55:11,000
Și asta e în cazul în care posibilitatea de genial apare.

923
00:55:11,000 --> 00:55:15,840
În acel moment, în poveste, Rob a avut 8 liste de dimensiune 1,

924
00:55:15,840 --> 00:55:18,860
toate din care au fost sortate deja.

925
00:55:18,860 --> 00:55:20,630
>> Deci, atunci ce a proceda să facă?

926
00:55:20,630 --> 00:55:25,260
Perechilor el a luat această listă sortată și această listă sortată și care a fuzionat le.

927
00:55:25,260 --> 00:55:28,200
Apoi, el a luat aceasta și care a fuzionat ei, atunci aceasta și le-a fuzionat,

928
00:55:28,200 --> 00:55:30,670
atunci aceasta și le-a fuzionat.

929
00:55:30,670 --> 00:55:32,390
Și apoi ce a făcut în continuare?

930
00:55:32,390 --> 00:55:36,580
El apoi re-unit listele mai mari și apoi re-unit listele mai mari.

931
00:55:36,580 --> 00:55:41,170
Și dacă te gândești la acest lucru doar intuitiv pentru moment, ceea ce a fost el cu adevărat face?

932
00:55:41,170 --> 00:55:45,450
El a fost împărțirea problema în jumătate, în jumătate, în jumătate, în jumătate

933
00:55:45,450 --> 00:55:47,600
, în scopul de a obține aceste liste super-mici.

934
00:55:47,600 --> 00:55:51,290
Apoi, el a fost un fel de a combina dublu, dublu, dublu matrimonial,.

935
00:55:51,290 --> 00:55:54,120
Deci, el a fost de a face de două ori mai multă muncă așa cum am văzut până acum

936
00:55:54,120 --> 00:55:56,930
cu nimic care implică divide et impera, dar nu e mare lucru.

937
00:55:56,930 --> 00:55:59,630
Locul de muncă de două ori la fel de mult, nu este o astfel de afacere mare. E doar un factor constant.

938
00:55:59,630 --> 00:56:03,920
Și la fel ca expresie aritmetica noastră înainte, mă duc să treacă din factorii constanți

939
00:56:03,920 --> 00:56:10,170
ca ori 2. Cui îi pasă? Dacă e 2 miliarde de ori 2, care este încă o mulțime de pași.

940
00:56:10,170 --> 00:56:13,160
Deci, acest pas care fuzionează pare a fi perspectiva cheie.

941
00:56:13,160 --> 00:56:17,000
Să se plimbe prin acest lucru doar numeric înainte - Oh, asta nu e să fie continuată încă.

942
00:56:17,000 --> 00:56:22,890
Să se plimbe prin această numeric doar pentru a vedea de fapt, modul în care această joacă afară.

943
00:56:22,890 --> 00:56:25,940
Aceasta este cea mai mare parte doar un om mic sărac animație.

944
00:56:25,940 --> 00:56:27,750
Să propune acest lucru.

945
00:56:27,750 --> 00:56:31,480
Timpul de execuție al îmbinării fel - avem nevoie doar de o modalitate de a vorbi despre acest lucru.

946
00:56:31,480 --> 00:56:34,380
Acest lucru nu este matematica, acest lucru este doar un fel de mod succint de exprimare noi înșine.

947
00:56:34,380 --> 00:56:39,080
Deci T reprezintă timpul și n reprezintă ce? >> [Elev] Dimensiunea -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] Dimensiunea problemei, numărul de persoane.

949
00:56:41,400 --> 00:56:45,470
Deci, eu sunt susținând că timpul de execuție pentru a sorta oamenii n va fi 0 perioada de timp

950
00:56:45,470 --> 00:56:50,290
dacă n este mai mică de 2, deoarece, dacă aveți 1 ceașcă sau nu cupe, nu ai nimic pentru a sorta.

951
00:56:50,290 --> 00:56:55,160
Dar, mai general, am de gând să propună ca timpul de rulare pentru a sorta n elemente

952
00:56:55,160 --> 00:56:59,350
va fi timpul necesar pentru a sorta jumătatea stângă, plus jumătatea din dreapta

953
00:56:59,350 --> 00:57:03,110
plus - ce e asta suplimentar + n? >> [Elev] Merge sortare.

954
00:57:03,110 --> 00:57:07,260
[Malan] Este de fapt care fuzionează, pentru că în cazul în care aveți n / 2 elemente aici

955
00:57:07,260 --> 00:57:11,500
și aveți n / 2 elemente aici, cât de mult timp este nevoie pentru a le îmbina?

956
00:57:11,500 --> 00:57:15,050
La fel ca Rob, va trebui să smulgă asta de aici, poate smulge pe aici,

957
00:57:15,050 --> 00:57:17,120
smulge aici, trage aici, trage aici.

958
00:57:17,120 --> 00:57:19,400
Trebuie sa atingi fiecare dintre cupe dată.

959
00:57:19,400 --> 00:57:22,030
Și dacă nu e 4 cupe, plus 4 cesti, asta e 8 cesti

960
00:57:22,030 --> 00:57:25,200
sau, mai general, 8 cupe n.

961
00:57:25,200 --> 00:57:28,470
Deci, pas care fuzionează ne putem exprima ca n,

962
00:57:28,470 --> 00:57:31,330
și care implică literalmente numărul de ori Rob fizic atins

963
00:57:31,330 --> 00:57:33,410
unul dintre cei cupe Styrofoam.

964
00:57:33,410 --> 00:57:35,850
Deci, hai sa facem acum un exemplu arbitrar.

965
00:57:35,850 --> 00:57:41,850
Dacă e 16 cupe, ceea ce este timpul de funcționare de sortare, folosind algoritmul lui Rob, 16 cupe?

966
00:57:41,850 --> 00:57:44,710
E de 2 ori cantitatea de timp este nevoie pentru a sorta 8 cesti

967
00:57:44,710 --> 00:57:46,920
Pentru că avem 8 cesti aici, 8 cupe aici.

968
00:57:46,920 --> 00:57:51,520
Nu știu cât timp care ia, așa că îl generalizarea ca T pentru moment.

969
00:57:51,520 --> 00:57:53,320
Cine știe ce este?

970
00:57:53,320 --> 00:57:58,990
Dar acum pot sorta de recursiv sau în mod repetat cere aceeași întrebare.

971
00:57:58,990 --> 00:58:01,920
Cât de mult timp este nevoie pentru a sorta 8 cesti?

972
00:58:01,920 --> 00:58:07,030
8 cesti am de gând să spun ia cantitatea de timp este nevoie pentru a sorta 4 cupe, plus 4 cesti,

973
00:58:07,030 --> 00:58:08,880
apoi le fuzionează împreună.

974
00:58:08,880 --> 00:58:13,080
Amenzii. Primim intr-un ciclu deja. Cât timp este nevoie pentru a sorta 4 cupe?

975
00:58:13,080 --> 00:58:19,150
Timpul necesar pentru a sorta 4 cupe este de 2 cupe plus 2 cupe de sortare, plus procesul de fuziune.

976
00:58:19,150 --> 00:58:21,440
Amenzii. Cât timp este nevoie pentru a sorta 2 cupe?

977
00:58:21,440 --> 00:58:26,290
2 cupe este cantitatea de timp este nevoie pentru a sorta 1 ceasca, plus timpul necesar pentru a sorta o ceașcă

978
00:58:26,290 --> 00:58:29,040
plus cantitatea de timp este nevoie pentru a fuziona, care este la doar 2.

979
00:58:29,040 --> 00:58:33,340
>> Amenzii. Ultima întrebare. Cât timp este nevoie pentru a sorta 1 cană?

980
00:58:33,340 --> 00:58:37,260
Aici este cazul de bază pe care am prezis ne-ar lovi mai devreme.

981
00:58:37,260 --> 00:58:42,250
Faptul că este nevoie de nici o lucrare fel de a sorta mai mic de probleme

982
00:58:42,250 --> 00:58:44,120
înseamnă că, în prezent, un fel de stil școala primară,

983
00:58:44,120 --> 00:58:46,460
putem merge doar începe conectarea acestor numere înapoi inch

984
00:58:46,460 --> 00:58:50,630
Noi știm acum ce T de 1 este, așa că am putea conecta la 0 pentru T de 1.

985
00:58:50,630 --> 00:58:54,420
Asta îmi va da răspunsul la T de 2, pe care apoi am pot conecta până în mai.

986
00:58:54,420 --> 00:58:56,930
Asta va da-mi T de 4, pe care eu pot conecta în sus superior.

987
00:58:56,930 --> 00:58:58,920
Asta va da-mi T de 8, pe care eu pot conecta în sus superior.

988
00:58:58,920 --> 00:59:04,330
Și dacă eu fac de fapt, că matematica prin conectarea la aceste răspunsuri,

989
00:59:04,330 --> 00:59:08,590
I a lua atunci T de 16 este de 64.

990
00:59:08,590 --> 00:59:12,090
Și ce reprezintă 64?

991
00:59:12,090 --> 00:59:15,700
Dacă T este de 16, da, e de 16 ori 4.

992
00:59:15,700 --> 00:59:20,120
Deci, eu pretind acum că timpul de execuție a acestui lucru numit fuzioneze sortare -

993
00:59:20,120 --> 00:59:22,590
și acest lucru va fi fanciest de cele pe care le-am văzut până acum -

994
00:59:22,590 --> 00:59:26,160
va fi numit n log n

995
00:59:26,160 --> 00:59:31,140
pentru că de câte ori se poate împărți Rob o gramada de cupe în jumătate? Log n.

996
00:59:31,140 --> 00:59:34,370
E la fel ca exemplu cartea de telefon, e la fel ca exemplu de auto-numărare.

997
00:59:34,370 --> 00:59:36,380
>> Cât de multe ori puteți împărți ceva în jumătate?

998
00:59:36,380 --> 00:59:38,410
Cu toate acestea, există acest pas fuziune.

999
00:59:38,410 --> 00:59:42,920
S-ar putea să împartă în jumătate cupe din nou și din nou și din nou,

1000
00:59:42,920 --> 00:59:45,640
dar de fiecare dată ai de gând să aibă de a fuziona.

1001
00:59:45,640 --> 00:59:48,270
Iar noi am spus mai devreme că fuzionează cupe n ia măsuri n

1002
00:59:48,270 --> 00:59:52,060
pentru că trebuie să scoată o ceașcă, smulge o ceașcă, și va trebui să atingeți fiecare ceașcă o dată,

1003
00:59:52,060 --> 00:59:53,510
la fel ca Rob făcut-o.

1004
00:59:53,510 --> 00:59:59,430
Deci, dacă facem ceva log n ori și facem lucruri n pe fiecare dintre aceste iterații,

1005
00:59:59,430 --> 01:00:03,090
fiecare dintre aceste halvings, avem n log n ori.

1006
01:00:03,090 --> 01:00:07,220
Deci, dacă am conectați la 16, în acest exemplu, de 16 ori jurnal de 16 -

1007
01:00:07,220 --> 01:00:10,600
nu vă faceți griji cu privire la ce este acest caz, pentru acum, pentru că eu nu am desenat de bază -

1008
01:00:10,600 --> 01:00:16,100
dar jurnalul de baza 2 din 16 este de 4, 16 ori 4 este 64.

1009
01:00:16,100 --> 01:00:22,350
Dar, prin contrast, dacă am fi folosit un fel bule de aer sau de sortare sau inserarea de selecție sortare cu 16 numere,

1010
01:00:22,350 --> 01:00:26,420
ceea ce ar fi fost timpul de funcționare în cazul în care n este de 16?

1011
01:00:26,420 --> 01:00:33,310
Acesta ar fi 16 la pătrat, care este 256, care, chiar dacă nu ați urmat toate destul de matematica,

1012
01:00:33,310 --> 01:00:38,390
256 este mai mare decât 64. Asta e într-adevăr magic Takeaway aici.

1013
01:00:38,390 --> 01:00:41,990
Și dau seama că prin acest lucru, în timp ce exemple mai mici va pe o PSET

1014
01:00:41,990 --> 01:00:44,260
face totul mult mai intuitiv.

1015
01:00:44,260 --> 01:00:49,070
Dar ce înseamnă cu adevărat în ceea ce privește simt al acestui algoritm este aceasta:

1016
01:00:49,070 --> 01:00:54,520
Dacă ne uităm la fel de fapt, merge aici - lasă-mă să-l trage în sus în această fereastră aici -

1017
01:00:54,520 --> 01:00:58,560
acesta este un exemplu ușor diferită, prin care avem toate 3 din acesti algoritmi -

1018
01:00:58,560 --> 01:01:01,440
balon, selecție și îmbinare - doar una lângă alta.

1019
01:01:01,440 --> 01:01:03,740
>> Ei au Totul a început cu bare aleatoare, și asta e bine.

1020
01:01:03,740 --> 01:01:06,240
Nimeni nu are un avantaj fundamental față de celălalt.

1021
01:01:06,240 --> 01:01:09,500
Am de gând să într-un moment faceți clic pe fiecare dintre aceste animații - Start, Start, Start -

1022
01:01:09,500 --> 01:01:13,270
cât de repede pot, astfel încât, în linii mari, toate au început, în același timp,

1023
01:01:13,270 --> 01:01:17,450
și să ia în considerare acest caz, un fel de balon mai rau timp de rulare este ceea ce? >> [Elev] pătrat N.

1024
01:01:17,450 --> 01:01:21,560
N pătrat. Cazul cel mai rău fel de selecție este durata de? N pătrat.

1025
01:01:21,560 --> 01:01:25,150
Și fel de îmbinare este aparent - chiar dacă nu a urmat destul de toată matematica acum,

1026
01:01:25,150 --> 01:01:30,610
acesta va deveni mult mai intuitivă a lungul timpului - este, ne susțin, de n ori log n.

1027
01:01:30,610 --> 01:01:35,210
Si pentru ca log n este strict mai mică decât n, odată ce vom avea numere mari,

1028
01:01:35,210 --> 01:01:40,230
de n ori log n este mai mic decât n ori n sau n pătrat.

1029
01:01:40,230 --> 01:01:44,410
Deci, ce se simte a fi de fapt un algoritm mai bun în ceea ce privește timpul de funcționare,

1030
01:01:44,410 --> 01:01:50,380
n log n ori, spre deosebire de pătrat n? Aici vom merge. Faceți clic pe, faceți clic pe, faceți clic pe.

1031
01:01:55,690 --> 01:01:58,650
>> Asta e ceea ce înseamnă să folosească ceva de genul un fel de îmbinare.

1032
01:01:58,650 --> 01:02:01,680
Avem o clipă. Să vedem ce se întâmplă aici.

1033
01:02:09,440 --> 01:02:12,440
[Chicotește] cui bani se află pe un fel cu bule?

1034
01:02:14,960 --> 01:02:16,730
Aceasta depinde mai degrabă de intrare, uneori.

1035
01:02:16,730 --> 01:02:18,120
Să vedem.

1036
01:02:18,120 --> 01:02:23,320
Haide. Se simte ca și cum ar prinde sus. >> [Elev] Du-te, sortare cu bule!

1037
01:02:23,320 --> 01:02:27,370
[Elevi murmurând]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Da, da.

1039
01:02:29,120 --> 01:02:34,520
[Elevii murmurau] Du-te, du-te, du-te!

1040
01:02:37,210 --> 01:02:40,450
[Totul aplauze] [aplauze]

1041
01:02:40,450 --> 01:02:46,240
Deci, acum, cu 1 demo trecut, finala, daca e un pic complicat să-și încheie în jurul valorii de mintea ta de matematica

1042
01:02:46,240 --> 01:02:49,280
sau un fel de vizualizare acolo, puteți auzi de fapt, vitezele

1043
01:02:49,280 --> 01:02:51,000
de algoritmi diferite în mod diferit.

1044
01:02:51,000 --> 01:02:53,900
Aceasta este o animatie cineva a făcut ca, de fapt asociații suna

1045
01:02:53,900 --> 01:02:56,980
cu procesul de pompare și înălțimea barelor.

1046
01:02:56,980 --> 01:03:00,440
După cum vom vedea aici, nu e un algoritmi de sortare câteva mai multe acolo, care s-au gândit la oameni.

1047
01:03:00,440 --> 01:03:03,660
Aceasta prima se va fi un fel de inserare, iar acest lucru va zbura prin

1048
01:03:03,660 --> 01:03:07,090
și vă va oferi un sentiment de sonor cum functioneaza aceste diferite algoritmi.

1049
01:03:07,090 --> 01:03:09,080
Aici este un fel de inserare.

1050
01:03:09,080 --> 01:03:18,410
[Bip electronice]

1051
01:03:18,410 --> 01:03:20,730
[Malan] sortare Bubble.

1052
01:03:20,730 --> 01:03:46,850
[Mai rapid bip electronice]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Selecție de sortare.

1054
01:03:48,950 --> 01:04:03,580
[Mai rapid bip electronice]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Merge sortare.

1056
01:04:05,770 --> 01:04:17,270
[Bip electronice]

1057
01:04:17,270 --> 01:04:20,180
[Bip încetinește] [râsete]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome de sortare.

1059
01:04:22,590 --> 01:04:38,580
[Bip electronice]

1060
01:04:39,740 --> 01:04:46,150
>> Acest lucru este CS50. Ne vedem săptămâna viitoare. [Aplauze și aplauze]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]