1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [3 savaitė, Tęsinys]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Harvardo universiteto]

3
00:00:04,110 --> 00:00:07,130
>> [Tai CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Gerai. Sveiki sugrįžę. Tai CS50 ir tai yra 3 savaitės pabaigos.

5
00:00:11,010 --> 00:00:14,680
>> Tad tiems, nepažįstamas, praėjusiais metais Harvardo pradėjo tai, kas vadinama inovacijų laboratorijos,

6
00:00:14,680 --> 00:00:18,530
arba i-laboratorija, kuris yra puikus pastatas per upę HBS miesteliu

7
00:00:18,530 --> 00:00:22,640
, kuri yra atvira studentai, GP moksleiviams, studentams iš visos miesteliu,

8
00:00:22,640 --> 00:00:27,000
įskaitant fakultetą, ir tai vieta ateiti kartu dirbti dėl novatoriškų dalykų,

9
00:00:27,000 --> 00:00:29,180
ypač verslumo dalykų

10
00:00:29,180 --> 00:00:33,410
jei jūs ir 0 arba daugiau draugų galvoja apie darai kažką, verslumo

11
00:00:33,410 --> 00:00:37,080
arba per šią klasę, po šios klasės, ar už jos ribų.

12
00:00:37,080 --> 00:00:41,540
>> Taigi vienas iš dalykų, jie daro per J laikotarpiu yra šių kelionių,

13
00:00:41,540 --> 00:00:44,510
iš kurių vienas yra į Niujorką, iš kurių vienas yra Silicio slėnyje.

14
00:00:44,510 --> 00:00:47,530
Erdvė yra labai ribotas, bet tai galimybė RUB pečių su magistrų

15
00:00:47,530 --> 00:00:52,200
ir antrosios pakopos studijų studentų visoje miesteliu ir iš tikrųjų praleisti laiką tose atitinkamose srityse

16
00:00:52,200 --> 00:00:55,500
kalbasi pradedantiesiems, kalbasi verslininkus ir pan.

17
00:00:55,500 --> 00:00:57,870
Taigi, jei domina, check out šį URL adresą čia.

18
00:00:57,870 --> 00:01:01,220
Jis taip pat yra skaidrių internete.

19
00:01:01,220 --> 00:01:04,610
>> Mes galėtume sušvelninti namo garsą tik šiek tiek?

20
00:01:04,610 --> 00:01:08,640
Jei norėtumėte prisijungti prie mūsų pietums šį penktadienį, 13:15 Fire & Ice, prašome Nukeliavę ten.

21
00:01:08,640 --> 00:01:11,390
Atsiprašome, jei jau užpildyta forma iki tol, kol jūs ten.

22
00:01:11,390 --> 00:01:13,750
Bet mes toliau šią tradiciją pirmyn.

23
00:01:13,750 --> 00:01:17,350
>> Šiandien mes ir toliau aukštesnio lygio diskusiją įvairių problemų, kad mes galime išspręsti,

24
00:01:17,350 --> 00:01:21,330
sutelkiant dėmesį daug mažiau, šiandien bent jau kodą ir daug daugiau idėjų.

25
00:01:21,330 --> 00:01:24,720
Todėl manau, kad atgal į savaitę 0, kai mes sudraskė Telefonų knygos pusėje,

26
00:01:24,720 --> 00:01:28,260
kurių tikslas buvo padaryti ką nors, tiesa, šiek tiek dramatiškas

27
00:01:28,260 --> 00:01:32,360
bet nusiųsti tašką, kad ieško ne turite būti, būtinai

28
00:01:32,360 --> 00:01:35,100
kaip akivaizdu iš pirmo žvilgsnio, kaip jūs manote.

29
00:01:35,100 --> 00:01:40,200
Ir problemų sprendimo apskritai gali ne visada būti geriausias -

30
00:01:40,200 --> 00:01:44,130
Akivaizdžiausias sprendimas nebūtinai gali būti geriausias.

31
00:01:44,130 --> 00:01:47,300
Taigi mes turėjome šio telefono knygą ir, tiesą sakant, visiems mums šiame kambaryje turėjo instinktus,

32
00:01:47,300 --> 00:01:51,470
Labiausiai tikėtina, kad pradėti viduryje, kai ieškote Mike Smith ir tada eiti į kairę arba į dešinę

33
00:01:51,470 --> 00:01:54,280
remiantis kokia abėcėlės raidė mes atsitiko, kad galų gale.

34
00:01:54,280 --> 00:01:57,560
>> Bet tai paprasta idėja, kad mes, žmonės ėmėsi suteikta taip ilgai

35
00:01:57,560 --> 00:02:00,670
tikrai turėtų pradėti atvykti į savo proto priešakyje

36
00:02:00,670 --> 00:02:03,900
nes problemos gauti daug sudėtingesnis nei telefonų knygos,

37
00:02:03,900 --> 00:02:07,420
tie patys paprasti, puikus įžvalgos yra tai, ką ketinate leidžia mums

38
00:02:07,420 --> 00:02:10,259
išspręsti daug sudėtingiau ir įdomiau problemas,

39
00:02:10,259 --> 00:02:12,930
tarp jų keletas dalykų, mes priimame kaip savaime jau šių dienų.

40
00:02:12,930 --> 00:02:15,720
Milijardus tinklalapių ten, ir dar "Google" ir "Bing" ir panašūs

41
00:02:15,720 --> 00:02:17,660
gali rasti dalykų už mus, kaip kad.

42
00:02:17,660 --> 00:02:22,300
Kad manimi ne vyksta naudojant linijinį paiešką, ieškoti visomis įmanomomis tinklalapių.

43
00:02:22,300 --> 00:02:25,290
"Facebook" gali pasakyti, kas visi jūsų draugai arba draugų draugai,

44
00:02:25,290 --> 00:02:28,250
ir kad taip pat gali būti padaryta atrodo akimirksniu šių dienų

45
00:02:28,250 --> 00:02:30,820
nors jie turi milijonus vartotojų.

46
00:02:30,820 --> 00:02:34,250
>> Ir taip, kaip mes iš tikrųjų spręsti problemas minėtos skalės galiausiai sumažinti

47
00:02:34,250 --> 00:02:37,830
idėjas mes pažvelgė į savaitę 0 ir šiek tiek daugiau šiandien.

48
00:02:37,830 --> 00:02:42,320
Mes ne iš naujo atlikti šį algoritmą, bet prisiminti, mes taip pat atliko šį pratimą savaitę 0

49
00:02:42,320 --> 00:02:44,780
kur mes visi atsistoti, imtis skaičiumi 1,

50
00:02:44,780 --> 00:02:48,720
ir tada mes turėjo visus skaičiavimo Kergimas išjungti kartu pridedant savo numerius,

51
00:02:48,720 --> 00:02:51,930
tada pusė gaujos atsisėdo ant kiekvieno iteracijos.

52
00:02:51,930 --> 00:02:56,750
Pasakyta iš 500 studentų 250-125 ir kt.

53
00:02:56,750 --> 00:03:00,080
Bet kaip mes pirmadienį sakė, galinga idėja yra

54
00:03:00,080 --> 00:03:02,460
buvo, kad jei mes dvigubai šios problemos dydį

55
00:03:02,460 --> 00:03:06,480
ir visi vaikai iš Teisingumo Teismo arba EB 10 grįžo į kambarį ir prisijungė prie mūsų,

56
00:03:06,480 --> 00:03:09,510
gerai, mes turbūt galėtų tikėtis, kad visą bendrą grupę

57
00:03:09,510 --> 00:03:13,380
tik 1 didelis pasikartojančių kilpą, nes jie tik gal dvigubai dydį

58
00:03:13,380 --> 00:03:15,630
ar EB 10 atveju šiek tiek daugiau nei dvigubai dydžio.

59
00:03:15,630 --> 00:03:18,440
Ir todėl mes turėtume praleisti šiek tiek daugiau laiko,

60
00:03:18,440 --> 00:03:22,000
bet mes nebūtume išleisti 400 ar 700 daugiau žingsnių.

61
00:03:22,000 --> 00:03:26,550
>> Tik dažų šią nuotrauką taip, kad yra šiek tiek ne tokia abstrakti, tegul ne turėti visus atsistoti.

62
00:03:26,550 --> 00:03:31,100
Bet jei tiems iš jūsų, kurie nusprendė posėdžiauti orkestro šiandien nebūtų proto atsistojus,

63
00:03:31,100 --> 00:03:34,580
galime pamatyti, jei mes galime suprasti iš tavęs kas aukščiausias asmuo

64
00:03:34,580 --> 00:03:36,730
lyginamosios algoritmas daro tos pačios rūšies.

65
00:03:36,730 --> 00:03:41,830
Taigi, jei esate sėdi orkestro, mano Atsiprašome, tačiau 1 žingsnis, atsistoti;

66
00:03:41,830 --> 00:03:44,650
2 etapas, pora su kuo nors šalia jūsų,

67
00:03:44,650 --> 00:03:49,360
išsiaiškinti, kas yra aukštesni, ir sėdėti, jei yra trumpesnis.

68
00:03:49,360 --> 00:03:51,360
Tada pakartokite.

69
00:03:51,360 --> 00:03:56,280
[Studentai murmantys]

70
00:04:13,450 --> 00:04:15,320
>> Gerai.

71
00:04:15,320 --> 00:04:19,010
Gerai. Vienas liko stovėti. Koks tavo vardas? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, esate aukščiausias asmuo skyriuje orkestro šiandien.

73
00:04:21,959 --> 00:04:28,100
>> Sveikiname. [Plojimai ir visaip kitaip] Gerai. Patarti. Todėl mes radome Andrew.

74
00:04:28,100 --> 00:04:30,870
Bet kaip ilgai jis ėmėsi mane, pavyzdžiui, rasti Andrew

75
00:04:30,870 --> 00:04:33,740
Šis orkestras skyriuje 50 + arba tiek žmonių?

76
00:04:33,740 --> 00:04:36,900
Aš galėjo gana paprastą požiūrį ir pradėti čia.

77
00:04:36,900 --> 00:04:39,270
Ir aš 2 žmonės atsistoti ir aš tiesiog palyginti juos,

78
00:04:39,270 --> 00:04:42,120
ir tada aš sakau, kas yra šiek tiek trumpesnis, "Gerai, jūs susėsti"

79
00:04:42,120 --> 00:04:44,380
ir aš prisiminti, kas aukštesni asmuo buvo.

80
00:04:44,380 --> 00:04:49,030
Tada aš kartoju, kartoju, kartoju, ir aš pakabinti aukščiausias asmens

81
00:04:49,030 --> 00:04:51,920
kol aš rasti ką nors šiek tiek aukštesni nei jų, o tada

82
00:04:51,920 --> 00:04:54,950
šiek tiek trumpesnis asmuo turi tada atsisėsti.

83
00:04:54,950 --> 00:04:57,690
Bet tame skyriuje Šis orkestras algoritmas, jei n jums,

84
00:04:57,690 --> 00:05:00,480
kiek žingsnių yra kad algoritmas ketina imtis? >> [Studentas] N.

85
00:05:00,480 --> 00:05:03,580
>> Ji ketina imtis n, teisūs, nes blogiausiu atveju, taip sakant,

86
00:05:03,580 --> 00:05:09,090
aukščiausias žmogus yra labai paskutinis žmogus, kad man tiesiog atsitiktinių nesėkme.

87
00:05:09,090 --> 00:05:14,260
Taigi, blogiausiu atveju, šio algoritmo veikimo laikas yra tiesinė, tai n

88
00:05:14,260 --> 00:05:18,070
kur n yra bendras skaičius žmonių erdvėje, problemos dydis.

89
00:05:18,070 --> 00:05:19,600
Ką apie šį algoritmą?

90
00:05:19,600 --> 00:05:22,080
Tas faktas, kad jūs visi atsistojo ir vėl pusė iš jūsų atsisėdo,

91
00:05:22,080 --> 00:05:23,950
pusė iš jūsų atsisėdo, pusė iš jūsų atsisėdo.

92
00:05:23,950 --> 00:05:26,070
Kiek žingsnių, kurie, jei yra n jums čia?

93
00:05:26,070 --> 00:05:30,200
[Studentas] n log n. >> Tai būtų blogiau. Log n.

94
00:05:30,200 --> 00:05:32,930
>> Taigi log n, net jei jūs neturite pakankamai prisiminti, ką logaritmas yra,

95
00:05:32,930 --> 00:05:38,410
dabar, tiesiog vertinu tai, kad jis yra susijęs kažkaip tai perpus sumažinti ir perpus sumažinti ir perpus sumažinti.

96
00:05:38,410 --> 00:05:41,000
Ji neturi būti veiksnys 2. Tai gali būti 3 kartus.

97
00:05:41,000 --> 00:05:46,560
Bet tai tik tos pačios rūšies faktoriaus toks atkartojimas to, problemos dydis prasideda čia

98
00:05:46,560 --> 00:05:49,620
bet tada iš karto eina čia, tai čia, tai čia, tai čia.

99
00:05:49,620 --> 00:05:53,580
Jūs nesate vartojate mažas įkandimų apie problemą, jūs tikrai kapojimo toli

100
00:05:53,580 --> 00:05:56,160
didelis ypu kiekvieną kartą.

101
00:05:56,160 --> 00:06:00,810
Taigi mes turėjome 50 žmonių, tuomet 25, tada 12 ½ arba 13 žmonės stovi,

102
00:06:00,810 --> 00:06:05,370
6 ½ ir tt kol pagaliau tiesiog Andrių neliko.

103
00:06:05,370 --> 00:06:08,710
Taigi, mes ketiname skambinti, kad n log, ir galite įsivaizduoti, tai taip.

104
00:06:08,710 --> 00:06:12,570
Prisiminkite šią nuotrauką čia, kur linijinis algoritmas yra tarsi raudona linija,

105
00:06:12,570 --> 00:06:17,520
geltona linija skaičiavimas 2s algoritmą, kad mes naudojamas skaičiavimo studentams

106
00:06:17,520 --> 00:06:22,300
praeityje, tačiau šiandien Gralis ketina likti tai žalia linija

107
00:06:22,300 --> 00:06:25,470
kur, jei mes dvigubai orkestro skyriuje žmonių skaičių ar ką tik pasakė,

108
00:06:25,470 --> 00:06:29,170
po velnių, tegul turi visą kambarį visiems atsistoti, ne tokia baisi

109
00:06:29,170 --> 00:06:31,560
nes mes maždaug dvigubai, kiek žmonių yra čia,

110
00:06:31,560 --> 00:06:33,500
1 iteracija, ne problema.

111
00:06:33,500 --> 00:06:36,200
>> Mes pastebėjome, Andrew ar kas atsitinka būti aukštesni nei Andrew

112
00:06:36,200 --> 00:06:38,770
antresolėje arba balkonas.

113
00:06:38,770 --> 00:06:42,140
Todėl šį paprastą idėją, kad mes priėmėme labai daug dalyku, telefonų knygos,

114
00:06:42,140 --> 00:06:46,170
suprasti, kad yra tiek daug įvairių vietų, kurioje mes galime taikyti jį.

115
00:06:46,170 --> 00:06:50,810
Tik slap šiek tiek žargono - iš tiesų, o ne žargonu pirma,

116
00:06:50,810 --> 00:06:52,750
leiskite man eiti į šioje nuotraukoje.

117
00:06:52,750 --> 00:06:56,970
Dabar mes kalbėjome apie n ir n / 2 ir tada prisijunkite n,

118
00:06:56,970 --> 00:07:00,500
bet mes tikrai gali sugalvoti, kaip mes per semestro metu,

119
00:07:00,500 --> 00:07:05,130
kitos rūšies matematines formules apibūdinti šį bendrą sąvoką važiavimo laikas.

120
00:07:05,130 --> 00:07:07,580
Tai yra iš kontekste dabar, nes mes iki kol

121
00:07:07,580 --> 00:07:09,900
algoritmai, kuriuos jie iš tikrųjų atstovauja.

122
00:07:09,900 --> 00:07:17,990
>> Bet pastebėsite čia, tiesinė linija n, tiesi linija, yra iš tikrųjų labai mažas nukreipta dabar.

123
00:07:17,990 --> 00:07:22,950
Tai tarsi tik optinė iliuzija, kad mes tiesiog pakeisti tai, kas x ašis rodo

124
00:07:22,950 --> 00:07:26,130
ir y ašis, ir mes galime padaryti tiesios linijos tašką bet kuria kryptimi norime.

125
00:07:26,130 --> 00:07:30,350
Bet priežastis, kad jis toks iš pažiūros butas dabar

126
00:07:30,350 --> 00:07:35,690
nes mums reikia, kad paliktume vietos šioje diagramoje daug lėčiau veikia laikais.

127
00:07:35,690 --> 00:07:39,030
Dabar, žinau, kad yra keletas gana blogi gyvenime algoritmai,

128
00:07:39,030 --> 00:07:43,790
kai kurie iš jų neturi imtis n veiksmus arba, dar geriau, log n veiksmus, bet daugiau.

129
00:07:43,790 --> 00:07:48,820
Taigi virš linijos n čia apačioje pranešimas yra log n n kartų,

130
00:07:48,820 --> 00:07:51,410
ir mes pamatyti, ką tai reiškia iki kol.

131
00:07:51,410 --> 00:07:56,010
Svarbiausia, kad yra n langeliais, ir mes nematėme jokių n kvadratu algoritmai dar, bet mes apie tai.

132
00:07:56,010 --> 00:07:57,660
Ir, kad atrodo tikrai neblogai.

133
00:07:57,660 --> 00:08:01,610
Yra 2 n kažkas eksponentinis, kuris jaučiasi dar blogiau.

134
00:08:01,610 --> 00:08:05,760
Ir vis dėlto, kaip bebūtų keista, ten n Cubed, kuri, jei esate tarsi galvoti į priekį,

135
00:08:05,760 --> 00:08:10,000
jei jūs tipo padaryti matematikos, 2 n faktiškai tampa daug tiesesni,

136
00:08:10,000 --> 00:08:15,930
daug didesnis nei n kubeliais, jei peržvelgsite ašių pakankamai toli iš.

137
00:08:15,930 --> 00:08:19,890
Taigi pastebėti dabar Šios ašys yra savavališkai 2 10 x ašyje.

138
00:08:19,890 --> 00:08:21,770
>> Ir ką tai reiškia?

139
00:08:21,770 --> 00:08:23,890
Tai reiškia, kad 2 žmonėms iki 10 žmonių kambaryje.

140
00:08:23,890 --> 00:08:27,200
Štai ir viskas x reiškia: problemos dydis, bet kontekstas.

141
00:08:27,200 --> 00:08:30,420
Ir dabar yra vertikali ašis skaičius sekundžių ar pakopų skaičius -

142
00:08:30,420 --> 00:08:31,840
kai laiko vienetas.

143
00:08:31,840 --> 00:08:34,740
, Bet pastebėsite, kad tai 0 iki 60 ir 0-10.

144
00:08:34,740 --> 00:08:38,549
Bet jei mes tipo zoom out, kaip jums gali "Excel" arba kai grafikas programinės įrangos,

145
00:08:38,549 --> 00:08:43,370
ir mes einame iki 200.000, pastebėsite, kad kažkas kaip 2 iki n

146
00:08:43,370 --> 00:08:47,520
vyksta visiškai sukrėsti n kvadrato rodymo laikus,

147
00:08:47,520 --> 00:08:50,960
n kubeliais, n log n - viskas, mes kalbėjome apie iki šiol.

148
00:08:50,960 --> 00:08:54,190
Ir dar laimikis, kai pradėsite kalbėti apie tokius dalykus kaip "Facebook"

149
00:08:54,190 --> 00:08:57,150
kur jūs visi tarpusavyje susiję, daug, daug, daug žmonių

150
00:08:57,150 --> 00:09:00,650
jūs n žmonių, iš kurių kiekvienas gali turėti tiek, kiek n draugams

151
00:09:00,650 --> 00:09:02,860
jei visi tarsi Buddy Buddy pasaulyje,

152
00:09:02,860 --> 00:09:08,100
gerai, kad n kartų jau taip, kad n kvadratu galimus draugystę,

153
00:09:08,100 --> 00:09:10,950
bent 1 kryptimi, n kvadratu galimų draugystę.

154
00:09:10,950 --> 00:09:15,330
Taigi, tai jau rodo, kad ieško "Facebook" socialinį grafiką, taip sakant,

155
00:09:15,330 --> 00:09:18,090
galite pradėti, turi būti išreikštas šių formulių rūšių.

156
00:09:18,090 --> 00:09:19,820
>> Mes grįžti ir padaryti tai daug konkretesni,

157
00:09:19,820 --> 00:09:23,280
bet dabar, per ateinančius daugelį savaičių tikslas

158
00:09:23,280 --> 00:09:27,170
bus tikrai ne eiti apie įgyvendinimo algoritmų arba kodą

159
00:09:27,170 --> 00:09:29,870
kad galų gale tiek pat laiko, kaip kažką panašaus į tai.

160
00:09:29,870 --> 00:09:33,110
Bet Įspūdingiausias dalykas apie kompiuterių mokslo, jei ir toliau šioje srityje

161
00:09:33,110 --> 00:09:38,320
atsižvelgiant klases, pavyzdžiui, CS121, CS124, kurie abu yra teorija kursai,

162
00:09:38,320 --> 00:09:41,300
yra tai, kad ten iš tikrųjų yra šiame pasaulyje egzistuoja tam tikros problemos,

163
00:09:41,300 --> 00:09:45,710
, kad iš esmės, kiek mes žinome, negali būti išspręsta bet greičiau

164
00:09:45,710 --> 00:09:48,880
ne blogiausias šių grafikų tikrai rodo.

165
00:09:48,880 --> 00:09:53,660
Taigi čia daug atvirų problemų šiame pasaulyje, tai padaryti kur kas geriau nei žmonės iki šiol.

166
00:09:53,660 --> 00:09:56,130
>> Taigi, pradėkime tada su šiuo pavyzdžiu.

167
00:09:56,130 --> 00:09:59,650
Mes matėme, Sean kovą su šio fotoaparato, visi per nerangiai ant vaizdo.

168
00:09:59,650 --> 00:10:05,270
Tačiau realybė buvo, kai Sean buvo pavesta rasti ant lentos, kaip šis numeris 7

169
00:10:05,270 --> 00:10:10,300
priminti, kad aš sakė, kad "yra kažkur už šių popieriaus vienetų ar baltos durys

170
00:10:10,300 --> 00:10:12,570
Skaičius 7. Sean, rasti tai už mus. "

171
00:10:12,570 --> 00:10:14,200
Ir ji buvo nuostabiai nepatogu žiūrėti

172
00:10:14,200 --> 00:10:15,790
, nes jis buvo tikrai kovoja su šia problema.

173
00:10:15,790 --> 00:10:19,720
Tačiau realybė buvo Sean taip pat gerai, kaip galėjo padaryti kas nors į kambarį.

174
00:10:19,720 --> 00:10:21,890
Jis užtruko šiek tiek ilgiau nei tipiškas asmuo gali turėti

175
00:10:21,890 --> 00:10:24,760
bet jis manė, kad buvo tam tikras triukas su šia problema,

176
00:10:24,760 --> 00:10:26,590
jis manė, kad jis kažko trūksta.

177
00:10:26,590 --> 00:10:29,320
Ir tai nepadėjo, kad šimtai akis turint ant jo.

178
00:10:29,320 --> 00:10:34,250
>> Tačiau realybė buvo, jei įėjimo į problemą yra atsitiktinių skaičių krūva

179
00:10:34,250 --> 00:10:37,120
ir jūs paprašė rasti 1 toks,

180
00:10:37,120 --> 00:10:39,770
geriausia, ką galite padaryti, yra tiesinė paieška ".

181
00:10:39,770 --> 00:10:44,060
Pradėti kairėje, pasislinks į dešinę, arba pradėti dešinę, judėti į kairę.

182
00:10:44,060 --> 00:10:48,300
Atgaline data, gali būti mąstymas, "Sean, kodėl ne jūs tiesiog pradėkite iš kitos pusės?

183
00:10:48,300 --> 00:10:52,120
Na, 7 galėjo taip pat lengvai buvo čia atsitiktinai,

184
00:10:52,120 --> 00:10:54,980
bet aš sąmoningai jį ten, nes aš raštuotas, kad jis nesiruošia pradėti pabaigoje.

185
00:10:54,980 --> 00:10:59,320
Taigi I rūšies manipuliavo situaciją, bet atsitiktine atsitiktinai 7 galėjo būti bet kur.

186
00:10:59,320 --> 00:11:02,380
Taigi pradedant nuo dešiniajame krašte galėjo geriau tada,

187
00:11:02,380 --> 00:11:04,320
bet kas, jei kitais metais aš perkelti 7 kitur?

188
00:11:04,320 --> 00:11:06,830
Tai nėra iš esmės naujas problemos sprendimas -

189
00:11:06,830 --> 00:11:10,520
nuo 1 dalies pabaigoje ar kita - kai jums suteikta jokių kitų prielaidas.

190
00:11:10,520 --> 00:11:13,620
Taigi Sean pradėjau ieškoti per skaičių ir jis tarė: "5. Štai čia nėra".

191
00:11:13,620 --> 00:11:17,280
Tada jis nuėjo čia ir pamačiau 19, tada jis stabtelėjo apie 20 sekundžių,

192
00:11:17,280 --> 00:11:22,330
tada jis pradėjo tai 13, o tada tapo aišku,

193
00:11:22,330 --> 00:11:24,270
, kad neatrodo, kad būti modelis.

194
00:11:24,270 --> 00:11:28,090
Tai buvo ne 1, 2, 3, 4 arba panašūs. Nebuvo spragų skaičių, nepadėjo.

195
00:11:28,090 --> 00:11:32,320
Ir taip pat tai, kad aš naudojamas šių pigių popieriaus lapų padengti skaičius

196
00:11:32,320 --> 00:11:35,270
iš tiesų yra sąmoningas, nes, jei aš pašalinti visus šiuos popieriaus likučių,

197
00:11:35,270 --> 00:11:38,760
dauguma iš mūsų, Sean vietoje, tikriausiai pažiūrėjau tarsi makroskopiškai

198
00:11:38,760 --> 00:11:43,410
lentos ir sako: "O, 7, žinoma, teisę ten." Mes tai padarė akimirksniu.

199
00:11:43,410 --> 00:11:46,460
>> Ir tai gali būti žmogaus smegenys veikia tam tikru mastu,

200
00:11:46,460 --> 00:11:50,730
bet iš tikrųjų, jo akys ar protas tikriausiai nuovirų skaičius iš dešinės į kairę,

201
00:11:50,730 --> 00:11:55,190
kairės į dešinę, iš vidutinio, kad kažkas fiziologiškai

202
00:11:55,190 --> 00:11:57,640
tokia, kad ji pajuto, kaip ji vyksta akimirksniu,

203
00:11:57,640 --> 00:12:01,360
tačiau šansai yra net viduje buvo kai metodikos natūra rasti 7.

204
00:12:01,360 --> 00:12:05,160
Ir iš tiesų, dabar, kad mes kalbame apie matricas ir duomenų struktūros

205
00:12:05,160 --> 00:12:08,780
ir atminties viduje kompiuterio, vienintelis dalykas, mes, žmonės gali padaryti

206
00:12:08,780 --> 00:12:13,070
, tai pažvelgti į atskirų atminties vietas 1 metu.

207
00:12:13,070 --> 00:12:16,600
>> Taigi, kas kita vieta taip pat gali būti taikoma kai popieriaus lapo

208
00:12:16,600 --> 00:12:21,170
nes mes negalime matyti jį vistiek. Mes galime padaryti tik 1 dalyką vienu metu.

209
00:12:21,170 --> 00:12:25,030
Taigi šiuo atveju, Sean atveju, mes nuėjome čia ir tada mes Eime čia

210
00:12:25,030 --> 00:12:31,040
ir tada mes Eime čia, čia, čia, čia, gavo protingas pabaigos

211
00:12:31,040 --> 00:12:34,450
ir tiesiog rūšies praleisti šį vieną savavališkai ir rasti 7 ten.

212
00:12:34,450 --> 00:12:37,470
Tai vienas nebuvo ypač ypatinga. Jis taip pat buvo ne iš eilės.

213
00:12:37,470 --> 00:12:39,530
Bet jis pagaliau rado 7.

214
00:12:39,530 --> 00:12:45,360
Bet dabar išsinešimui tikrai, kad geriausia, ką galite padaryti, kai jokios informacijos

215
00:12:45,360 --> 00:12:50,400
išskyrus atsitiktinai surūšiuoti numerių yra pradėti iš kairės arba pradėti iš dešinės.

216
00:12:50,400 --> 00:12:54,950
Ar gi, galite atsitiktinai atverti duris, tačiau net ir tada, ką tai reiškia būti atsitiktinai?

217
00:12:54,950 --> 00:12:57,220
Na, mes norime kažkaip formalizuoti, ką reiškia pradėti čia,

218
00:12:57,220 --> 00:13:01,150
tada eikite čia, tada eikite čia. Sean padarė puikus, ir tai buvo tiesiog smagu žiūrėti.

219
00:13:01,150 --> 00:13:06,340
Ką daryti, jei vietoj mes pakeisime šią problemą šiek tiek ir auklėti šių metų Sean, jei bus?

220
00:13:06,340 --> 00:13:09,460
Ar kas nors ateina ant scenos ir spręsti kiek kitokia problema

221
00:13:09,460 --> 00:13:12,330
ir ant fotoaparato?

222
00:13:12,330 --> 00:13:15,720
>> Eikime ne tik orkestro, nes jūs, vaikinai buvo gana dalyvauja jau šiandien.

223
00:13:15,720 --> 00:13:21,430
Kaip apie rožinės spalvos, skrybėlę? Nagi žemyn. Koks yra tavo vardas? >> Alex. >> Alex. Gerai.

224
00:13:21,430 --> 00:13:24,580
Taigi Alex bus šiemet Sean ir pasirodys per artimiausius kelerius metus

225
00:13:24,580 --> 00:13:27,770
verta CS50 paskaitų.

226
00:13:27,770 --> 00:13:30,340
Alex, nice to meet you. >> Nice to meet you too.

227
00:13:30,340 --> 00:13:33,470
Po ranka jums iššūkis yra tai, kad jūs turite jį šiek tiek lengviau

228
00:13:33,470 --> 00:13:38,950
aš sakau tuos pačius numerius čia, bet dabar jie yra rūšiuojami.

229
00:13:38,950 --> 00:13:41,800
Taigi dabar, jūsų tikslas yra rasti skaičių 7.

230
00:13:41,800 --> 00:13:45,370
Ir iš tikrųjų, mes turime tikrai padaryti tai - sukčiavimo! Galite rūšies, kaip kompiuteris,

231
00:13:45,370 --> 00:13:47,990
žiūri, ką buvo metu senumo.

232
00:13:47,990 --> 00:13:50,360
Su kreida tai tikrai nesiruošia padėti visiems, kad daug,

233
00:13:50,360 --> 00:13:52,810
bet galime apsimesti, kad jūs nežinote, kokios originalaus masyvas.

234
00:13:52,810 --> 00:13:56,600
Visi žinote, dabar, kad jūs turite surūšiuoti skaičių masyvas

235
00:13:56,600 --> 00:14:00,360
tai gali turėti tarpus tarp jų, ir jūsų tikslas yra rasti skaičių 7.

236
00:14:00,360 --> 00:14:05,080
Kaip jūs, protingas žmogus, eikite rasti 7?

237
00:14:05,080 --> 00:14:07,770
>> Pereiti nuo mažo iki didelio? >> Gerai. Eiti mažo iki didelio.

238
00:14:07,770 --> 00:14:10,990
Ir ne ašara juos išjungti. Tegul tik juos panaikinti, todėl mes galime juos pakartotinai.

239
00:14:10,990 --> 00:14:14,730
Gerai, kad 1. Palaukti. Kas žinotina prieš nesustoti, kad buvo 1, akivaizdžiai neteisinga.

240
00:14:14,730 --> 00:14:17,270
Taigi, kas vyksta per savo proto toliau? , Kas yra jūsų kitą žingsnį?

241
00:14:17,270 --> 00:14:23,250
Kitą. >> Gerai. Kitą. Geras. 3, toks netinkamas. , Kas yra jūsų kitą žingsnį?

242
00:14:23,250 --> 00:14:27,670
Laikyti vyksta. >> Gerai. Laikyti vyksta. 5.

243
00:14:27,670 --> 00:14:31,110
Todėl nuolat vyksta, ir leiskite man perduoti jums tai ateinančioms kartoms.

244
00:14:31,110 --> 00:14:35,720
7. >> Excellent. Labai geras. Rasta skaičių 7. [Plojimai]

245
00:14:35,720 --> 00:14:39,720
Kad buvo geras, bet per Sean rado 7.

246
00:14:39,720 --> 00:14:44,490
Ir esu įsitikinęs, kad jūs ne iš tikrųjų panaudojo šią informacijos dalį,

247
00:14:44,490 --> 00:14:47,780
yra tai, kad šie skaičiai yra rūšiuojamos.

248
00:14:47,780 --> 00:14:51,520
Taigi galime padaryti geriau? Bet kokie pasiūlymai čia? Taip, atgal.

249
00:14:51,520 --> 00:14:54,710
[Studentas] Dvejetainis paieška. >> Aš neįsivaizduoju, kas dvejetainis paieškos.

250
00:14:54,710 --> 00:14:58,030
>> [Studentas] Pradėti viduryje. >> Pradžia viduryje. Gerai. Taigi pažiūrėkime, jei mes galime gauti ten.

251
00:14:58,030 --> 00:15:02,580
Taigi, jei vietoj jums liepė pradėti nuo vidurio, eiti į priekį ir atidaryti vidurinių durų.

252
00:15:02,580 --> 00:15:04,580
Yra 8 iš jų, kad jūs ketinate turi savavališkai pasirinkti vieną

253
00:15:04,580 --> 00:15:09,800
šiek tiek į kairę arba į dešinę. Gerai. 7! [Plojimai] Very nice.

254
00:15:09,800 --> 00:15:11,410
Gerai, bet kur buvo mes su tuo?

255
00:15:11,410 --> 00:15:14,990
Sakykime, tiesiog nutraukti lygiąsias jums čia buvo pradėta

256
00:15:14,990 --> 00:15:16,670
nes tai taip pat galėjo atsitikti, taip pat.

257
00:15:16,670 --> 00:15:19,540
Mes tiesiog atsitiko žinoti, kad 7 ten buvo. Taigi, tai yra 13.

258
00:15:19,540 --> 00:15:21,980
Taigi, jei jie rūšiuojami ir mes ką tik pradėjo per vidurį,

259
00:15:21,980 --> 00:15:24,600
kas būtų optimalus Kitas žingsnis buvo?

260
00:15:24,600 --> 00:15:27,740
Eiti į kairę. Ir todėl čia ateina telefonų knygos pavyzdys dar kartą.

261
00:15:27,740 --> 00:15:30,130
Jei 13 yra čia, ir mes žinome, sąrašas surūšiuotas,

262
00:15:30,130 --> 00:15:33,900
tada visi iš šių popieriaus vienetų neįdomu mums dabar

263
00:15:33,900 --> 00:15:37,400
nes mes jau žinome, kad 7 turi būti į kairę

264
00:15:37,400 --> 00:15:39,510
jei šie skaičiai yra rūšiuojamos ir mes nustatėme 13.

265
00:15:39,510 --> 00:15:42,500
>> Taigi, kas yra jūsų kitą žingsnį čia? >> Eikite į kairę. >> Gerai, gerai.

266
00:15:42,500 --> 00:15:45,080
Taigi, eikite į kairę, ir - laukti, ei, ei, ei. Kad sukčiauja.

267
00:15:47,140 --> 00:15:51,350
Taigi jums rasti 7, bet tai, ką mes tiesiog taikomas algoritmas?

268
00:15:51,350 --> 00:15:56,450
Pradėti viduryje. >> Gerai. Taigi, kas yra logiška tą pačią sąvoką?

269
00:15:56,450 --> 00:15:58,970
Oh, tik jie. >> Būtent. >> Ir aš pradėti čia. >> Gerai.

270
00:15:58,970 --> 00:16:02,020
Taigi dabar mes nuėjome šiek tiek į kairę dar kartą. Tai 3.

271
00:16:02,020 --> 00:16:05,310
Tačiau įdomu išsinešimui, kuris iš jų padaryti, jūs neturite rūpintis?

272
00:16:05,310 --> 00:16:08,040
Tai 2. >> Tai 2. Taigi, dabar tai galima eiti toli, tai galima eiti šalin.

273
00:16:08,040 --> 00:16:12,330
Dabar problema, kad buvo 8 tada dydis 4 dydis 2.

274
00:16:12,330 --> 00:16:16,430
Mes gauname gana arti. Vėl eiti iš šių 2 elementų viduryje.

275
00:16:16,430 --> 00:16:20,430
>> Gerai. Taigi, tai tarsi gaila, kad dabar mes visada bus paliktas, nes mes apvalinimas iki mažesnio skaičiaus.

276
00:16:20,430 --> 00:16:25,150
Bet tai gerai, nes dabar mes išmetame šį toli ir visa kita, o mums vos 7.

277
00:16:25,150 --> 00:16:30,490
Leiskite duoti plojimų. Mes radome 7 dar kartą. [Plojimai] Gerai. Tikrai.

278
00:16:30,490 --> 00:16:32,220
Pakabinti ant tik 1 sekundę.

279
00:16:32,220 --> 00:16:36,630
Net jei tai kita proceso rūšies užtruko šiek tiek ilgiau, nei mes manėme, kad būtų

280
00:16:36,630 --> 00:16:40,150
tiesą sakant, jūsų instinktai buvo geriausias, tiesa? Mes radome 7 akimirksniu.

281
00:16:40,150 --> 00:16:46,740
Bet mes radome 7 greičiau, nesvarbu ką, šiame pavyzdyje, palyginti su šį vieną

282
00:16:46,740 --> 00:16:50,100
nes jei skaičiai yra rūšiuojami, panašiai kaip telefonų knygos puslapiuose,

283
00:16:50,100 --> 00:16:54,580
jūs iš tiesų gali pjaustyti pusę problemos vėl ir vėl ir vėl.

284
00:16:54,580 --> 00:16:56,740
Ir tai nėra taip paprasta, tai tik su 8 numeriais

285
00:16:56,740 --> 00:17:00,100
, palyginti su 1000 puslapių telefonų knygoje, kur jūs tikrai matyti vizualiai,

286
00:17:00,100 --> 00:17:03,120
bet šiuo atveju čia Sean ieškojau 7

287
00:17:03,120 --> 00:17:06,020
kiek žingsnių blogiausiu atveju ji ėmėsi jį? >> [Studentas] 7.

288
00:17:06,020 --> 00:17:11,670
7 blogiausiu atveju. Na, blogiausiu atveju, ne 7, jei yra čia 8 durys.

289
00:17:11,670 --> 00:17:13,440
Ji ėmėsi jam 8 žingsnių.

290
00:17:13,440 --> 00:17:18,170
>> Taigi, jei ten n durys, jis gali Sean prieš porą metų n veiksmus.

291
00:17:18,170 --> 00:17:21,520
Dabar, jūsų atveju, Alex, atsižvelgiant į tai, kad šie skaičiai yra rūšiuojamos -

292
00:17:21,520 --> 00:17:25,130
ir mes galime kildina šio tipo iš kur mes buvome iki šiol šioje istorijoje -

293
00:17:25,130 --> 00:17:28,300
kas Alex racionalesnį algoritmo veikimo laikas

294
00:17:28,300 --> 00:17:30,770
pradedant nuo vidurio ir tada kartoti?

295
00:17:30,770 --> 00:17:36,490
[Studentas] 3. >> Taigi tai bus 3, maždaug, jei jūs einate 8-4 2-1.

296
00:17:36,490 --> 00:17:40,660
Taigi 3 žingsnius arba, apskritai, tai log n vėl.

297
00:17:40,660 --> 00:17:43,380
Kiekvieną kartą, kai perpus sumažinti perpus sumažinti ir perpus sumažinti ir perpus sumažinti,

298
00:17:43,380 --> 00:17:45,290
kad išraiška šio log n idėjos.

299
00:17:45,290 --> 00:17:48,140
Ir kad būtų imamasi tik 3 žingsniai, ir ji tai padarė

300
00:17:48,140 --> 00:17:50,890
kai mes atidarėme durys perpus sumažinti ir perpus sumažinti

301
00:17:50,890 --> 00:17:53,770
kadangi dėl to ėmėsi Sean apie 7 ar 8 veiksmus.

302
00:17:53,770 --> 00:17:56,330
Tad ačiū už tai, kad pas mus šiais metais. >> Ačiū. Malonu buvo susipažinti.

303
00:17:56,330 --> 00:18:00,170
Dėkojame, Alex. >> Taip pat. [Plojimai]

304
00:18:00,170 --> 00:18:02,150
>> Tai, kas tikra potekstė?

305
00:18:02,150 --> 00:18:06,050
Dabar įsivaizduokite, kad tai ne 8 durys, kurios, tiesą sakant, visi iš mūsų galėtų rasti kažką

306
00:18:06,050 --> 00:18:10,430
atsilieka 8 durys gana greitai, tik popieriaus likučių ašarojimas ir vyksta su savo instinktus.

307
00:18:10,430 --> 00:18:14,430
Bet kas, jei tai milijono durys? Kas, jei tai 4 mlrd. Durys?

308
00:18:14,430 --> 00:18:19,630
4 mlrd durų, jūs tikrai ketinate nori eiti su Alex algoritmas,

309
00:18:19,630 --> 00:18:23,150
dvejetainis paieškos, nes mes pradėsime vadiname tai, skaldyk ir valdyk, apskritai,

310
00:18:23,150 --> 00:18:25,220
kur norite išsaugoti perpus sumažinti ir perpus sumažinti šią problemą,

311
00:18:25,220 --> 00:18:30,510
nes jei turite 4 mlrd. Durys, kiek kartų galite pjaustyti 4 milijardus 1/2?

312
00:18:30,510 --> 00:18:33,870
[Studentas] 32. >> Iš tikrųjų 32. Galite dirbti tai ant popieriaus lapo ar savo galva.

313
00:18:33,870 --> 00:18:38,490
Jūs einate, kad 4 mlrd. Iki 2 mlrd. Iki 1 mlrd. Pusė milijardo iki 250 milijonų eurų, DOT, DOT, taškas.

314
00:18:38,490 --> 00:18:41,620
Ir jei jūs matematikos, jūs ketinate iš tikrųjų gauti 32,

315
00:18:41,620 --> 00:18:44,950
ir kad iš tikrųjų susijęs su kompiuterių mokslo, nes mes paprastai skaičiuoja galių 2.

316
00:18:44,950 --> 00:18:47,600
2 iki 32 atsitinka, yra 4 mlrd.

317
00:18:47,600 --> 00:18:51,440
Taigi yra daug reikšmės šių galių 2 rūšių kompiuterių mokslo.

318
00:18:51,440 --> 00:18:55,120
>> Bet tai, ką apie 8 mlrd.? Kiek žingsnių, kad ketina imtis, jei yra 8 mlrd durys?

319
00:18:55,120 --> 00:19:00,350
[Studentas] 33. >> Taigi 33. Ką daryti, jei 16 mlrd durys? Kiek žingsnių yra tai, kad ketinate imtis?

320
00:19:00,350 --> 00:19:05,020
[Studentas] 34. >> 34. Mes galime rūšies šį znudzenia. Bet tai galingas dalykas.

321
00:19:05,020 --> 00:19:09,430
Galite įvesti daugiau duomenų milijardus į savo problemą, bet, ne big deal,

322
00:19:09,430 --> 00:19:14,140
jūs tiesiog gerti po 1 papildomą Užkandote iš jo ir tokiu būdu suteikia mums kažką panašaus dvejetainis paieškos

323
00:19:14,140 --> 00:19:15,920
arba skaldyk ir valdyk apskritai.

324
00:19:15,920 --> 00:19:17,990
Bet aš natūra apgaulės čia, tiesa?

325
00:19:17,990 --> 00:19:22,410
Alex algoritmo atveju, ji turėjo prieš Sean pranašumą.

326
00:19:22,410 --> 00:19:27,780
Ji žinojo, kad šie skaičiai buvo rūšiuojamos, tačiau Aleksas neturėjo juos surūšiuoti save.

327
00:19:27,780 --> 00:19:30,520
Aš priėjo prie lentos ir rūšis pasirūpino iš anksto

328
00:19:30,520 --> 00:19:33,670
, kad aš atkreipė juos visus iš rūšiuotų tvarka, tada aš, kuriems juos su popieriumi.

329
00:19:33,670 --> 00:19:35,850
Bet, kiek darbo, kad mane suprantate?

330
00:19:35,850 --> 00:19:40,110
Jei būtume prasidėjo nuo šių kai iš pažiūros atsitiktine tvarka numerių

331
00:19:40,110 --> 00:19:43,320
šiuo atveju tie paprastesni numeriai, 1 iki 8 čia -

332
00:19:43,320 --> 00:19:46,090
kaip mes eiti apie rūšiavimo šias vertybes?

333
00:19:46,090 --> 00:19:52,530
Jei buvo žmogus, nes ši užduotis, kokios intuityvaus požiūrio imtumėtės

334
00:19:52,530 --> 00:19:54,800
rūšiavimas visa krūva skaičių?

335
00:19:54,800 --> 00:19:57,050
Šie dalykai buvo išdėstyti kaip puzzle. Taip.

336
00:19:57,050 --> 00:19:59,950
>> [Studentas] Norėčiau imtis kiekvieną skaičių ir palyginkite jį į kiekvieną iš jų

337
00:19:59,950 --> 00:20:03,180
ir nesustoti į kairę. >> Gerai, gerai.

338
00:20:03,180 --> 00:20:05,720
Taigi, prieš priimdami kiekvieną numerį, palyginti ją su šalia jo,

339
00:20:05,720 --> 00:20:09,610
ir tada tiesiog nuolat juda kartu sąrašą, rūšies rejiggering dalykų, kaip jūs einate.

340
00:20:09,610 --> 00:20:13,800
Taigi čia mes turime gal keli žmonės galimybę įsitraukti.

341
00:20:13,800 --> 00:20:16,290
Ar mes turime 8 daugiau savanorių, kurie mėgsta sugalvoti?

342
00:20:16,290 --> 00:20:23,950
Šiek tiek mažiau slėgis, nes jūs ne vienintelis. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Nagi žemyn. Jus vaikinai bus numeriai nuo 1 iki 8.

344
00:20:28,190 --> 00:20:36,050
Pažiūrėkime, jei mes negalime padaryti šį rūšiavimą Alex daug tokiu pačiu būdu, aš padariau jį iš anksto.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Eiti į priekį ir, jei galėtumėte, linija ant scenos tarp muzikos stovas ir man čia

347
00:20:40,760 --> 00:20:44,960
ta pačia tvarka, kaip ekrane skaidrės.

348
00:20:47,910 --> 00:20:49,680
Uh-oh.

349
00:20:50,370 --> 00:20:53,230
Mes padėsime jums į Kitame pavyzdyje. Oi, palauk, palauk. Čia mes einame. Palaukti.

350
00:20:53,230 --> 00:20:57,570
Kitas pavyzdys yra dabar. Here you go. Numeris 8. Ateiti iki.

351
00:20:57,570 --> 00:21:00,270
Gerai. Rūšiuoti patys pagal.

352
00:21:00,270 --> 00:21:03,620
Tik šiek tiek pastumkite į muzikos pusės čia stovėti.

353
00:21:03,620 --> 00:21:12,310
Taigi, mes turime 4, 2, 6 - gauti ten, čia, tiesiai ten - 3.

354
00:21:12,310 --> 00:21:17,570
Taip. Gerai. Jūs eikite čia. Ne, jūs ten pasilikti.

355
00:21:17,570 --> 00:21:21,840
Taip, teisingai. Ne, aš neteisus. Teisę ten. Gerai, labai gerai. Gerai.

356
00:21:21,840 --> 00:21:24,930
Taigi dabar galime juos surūšiuoti didėjimo tvarka.

357
00:21:24,930 --> 00:21:26,210
>> Kaip aš galiu eiti apie tai daryti?

358
00:21:26,210 --> 00:21:28,630
Algoritmas, kuris buvo pasiūlyta prieš akimirką buvo, kodėl gi ne, mes tiesiog palyginti

359
00:21:28,630 --> 00:21:31,970
rūšies žmonės, kurie yra šalia vienas kito, ir tada nustatyti klaidas,

360
00:21:31,970 --> 00:21:33,540
juda iš kairės į dešinę.

361
00:21:33,540 --> 00:21:36,580
Taigi čia mes turime 4 ir 2, žinoma, ne iš eilės. Tegul apsikeitimo jums. Gerai.

362
00:21:36,580 --> 00:21:40,760
Taigi, dabar aš ruošiuosi judėti žemyn linija. 4 ir 6, nope. [Juokas]

363
00:21:40,760 --> 00:21:45,010
6 ir 8, gana gera. 8 ir 1, leiskite man apsikeitimo jums vaikinai. Gerai.

364
00:21:45,010 --> 00:21:48,030
Taigi 8 ir 3, apsikeitimo jus vaikinai.

365
00:21:48,030 --> 00:21:52,280
8 ir 7, leiskite man apsikeitimo jums vaikinai. 5 ir 8, puikus.

366
00:21:52,280 --> 00:21:54,820
Aš duosiu jums surūšiuoti sąrašą.

367
00:21:54,820 --> 00:21:56,860
Gerai. Taigi, ne gana.

368
00:21:56,860 --> 00:22:01,180
Bet tai geriau, nes didesni numeriai - case 8 punkte -

369
00:22:01,180 --> 00:22:04,030
buvo rūšies burbuliukų iš kairės į dešinę.

370
00:22:04,030 --> 00:22:08,010
Kad aš gavau iš jų 1 teisus, bet jis jaučiasi ne visiškai išspręsti šią problemą.

371
00:22:08,010 --> 00:22:11,150
>> Taigi, ką siūlytumėte mes darome toliau? >> [Studentas] Laikyti tai daro. >> Mes nuolat tai daryti.

372
00:22:11,150 --> 00:22:13,740
Ir suprasti, ir vėl, mes nustatyti dalykus tiesiog visus žmones

373
00:22:13,740 --> 00:22:17,180
tarsi protingai pasirūpinti, kad vaizdas,

374
00:22:17,180 --> 00:22:19,040
bet dabar mes turime būti daug daugiau metodinis.

375
00:22:19,040 --> 00:22:21,510
Mes turime Algorithmic apie tai, bet mes rašyti kodą -

376
00:22:21,510 --> 00:22:23,520
į Šiuo atveju žodinis pseudocode.

377
00:22:23,520 --> 00:22:26,040
Taigi, leiskite man tiesiog pabandyti, kad vėl. Kad dirbo gana gerai. Jis nebuvo išspręsti.

378
00:22:26,040 --> 00:22:30,400
Bet kai jis abejoju, tiesiog pabandykite ir bandykite dar kartą. SO 2 ir 4, nebėra nepadėjo.

379
00:22:30,400 --> 00:22:33,200
4 ir 6. Ah! 6 ir 1, šiek tiek geriau dabar.

380
00:22:33,200 --> 00:22:39,740
6 ir 3, geras. 6 ir 7, 7, 5, 7 ir 8, gerai.

381
00:22:39,740 --> 00:22:44,060
Ir žinote, aš galiu tikriausiai ignoruoti 8, nes dabar jis yra sąrašo pabaigoje.

382
00:22:44,060 --> 00:22:47,250
Gal mes neturime nerimauti, kas nors vyksta pro jį.

383
00:22:47,250 --> 00:22:49,240
Bet pažiūrėkime, jei tai saugi prielaida.

384
00:22:49,240 --> 00:22:52,340
Dabar sąrašas - Damn - nėra rūšiuojamos. Pabandykime tai vėl.

385
00:22:52,340 --> 00:22:56,440
SO 2 ir 4, 4 ir 1, 4 ir 3.

386
00:22:56,440 --> 00:22:59,230
4 ir 6, gerai. 6 ir 5, gerai.

387
00:22:59,230 --> 00:23:04,890
6, 7, 8, gerai. Tačiau pastebėkite, galiu tiesiog nustoti čia dabar ir čia sustoti dabar?

388
00:23:04,890 --> 00:23:07,770
[Studentas] Taip. >> Taip?

389
00:23:07,770 --> 00:23:11,160
Ką daryti, jei vienas iš jūsų buvo numeris 9 visą kelią ten?

390
00:23:11,160 --> 00:23:13,640
Jis buvo išrūšiuotos. >> Gerai. Jis būtų buvęs rūšiuotas pirmą kartą aplink.

391
00:23:13,640 --> 00:23:16,050
Geras. Taigi eikime atgal. Mes beveik ten.

392
00:23:16,050 --> 00:23:22,800
1 ir 2, 2 ir 3, 3 ir 4, 4 ir 5, 5 ir 6, 6 ir 7, 7 ir 8.

393
00:23:22,800 --> 00:23:26,640
>> Aš padaryti, bet dabar, dar kartą, aš tikiu, kompiuteris, kuris gali padaryti tik tai, ką aš negausite,

394
00:23:26,640 --> 00:23:30,120
ir mano tik prisiminimas dabar yra tai, kad aš iš tikrųjų tiesiog padarė šiek tiek darbo.

395
00:23:30,120 --> 00:23:31,700
Čia kažkas pasikeitė.

396
00:23:31,700 --> 00:23:37,100
Todėl aš ne techniškai patvirtino vizualiai ar algoritmiškai kad šis sąrašas būtų iš tikrųjų surūšiuoti.

397
00:23:37,100 --> 00:23:40,720
Taigi, tiesiog gera priemonė, tiesiog, kad būtų analinis apie tai, leiskite tai padaryti 1 daugiau laiko.

398
00:23:40,720 --> 00:23:44,040
Taigi 1 ir 2, 2 ir 3, 3 ir 4. Ir žinote ką?

399
00:23:44,040 --> 00:23:46,190
Tiesiog gera priemonė, aš sekti mano ranka šį kartą

400
00:23:46,190 --> 00:23:51,110
kiek apsikeitimo sandoriai aš, kad tik todėl, kad aš žinau, kiek daug darbo aš iš tikrųjų padaryta.

401
00:23:51,110 --> 00:23:56,930
3 ir 4 dalis, 4 ir 5, 5 ir 6, 6 ir 7, 7 ir 8. Nėra apsikeitimo sandoriai.

402
00:23:56,930 --> 00:24:00,800
Taigi dabar norėčiau teisėtai idiotas tai padaryti ir vėl,

403
00:24:00,800 --> 00:24:03,330
nes jei aš jokio darbo per šio žmonėms praeiti,

404
00:24:03,330 --> 00:24:06,710
tada aiškiai, kad nutiks dar kartą, jei nė vienas iš jų yra tarsi atsitiktinai

405
00:24:06,710 --> 00:24:10,410
adversarially juda aplink. Taigi, dabar galiu sustoti.

406
00:24:10,410 --> 00:24:15,120
Dabar galime užduoti klausimą, kiek daug darbo tai iš tikrųjų imasi domėjosi?

407
00:24:15,120 --> 00:24:18,260
Kiek žingsnių imtis? >> N kvadratu.

408
00:24:18,260 --> 00:24:20,400
Taip, kad n kvadratu. Kur jūs gaunate n kvadrato?

409
00:24:20,400 --> 00:24:22,660
Jūs turite patikrinti kiekvieną num

410
00:24:22,660 --> 00:24:26,530
Yra n numeriai, ir jūs turite patikrinti kiekvieną su kitomis n skaičių.

411
00:24:26,530 --> 00:24:29,030
Geras. >> Taigi tai n kvadratu. >> Gerai.

412
00:24:29,030 --> 00:24:31,060
>> Todėl mano, kad jis galėtų labai gerai būti n kvadrato, tiesa?

413
00:24:31,060 --> 00:24:33,820
Ten n iš šių vaikinai, 8 konkrečiai šiuo atveju,

414
00:24:33,820 --> 00:24:37,590
bet kiekvieną kartą, kai aš per šį sąrašą buvo lyginant pirmasis asmuo prieš antrąjį,

415
00:24:37,590 --> 00:24:39,650
prieš apdraustą trečiąjį asmenį vėl ir vėl ir vėl,

416
00:24:39,650 --> 00:24:42,450
ir kai aš iki galo, ką aš galiu padaryti? Aš redid.

417
00:24:42,450 --> 00:24:46,280
Taigi, jei mes apibendrinti šį paaiškinimą, mes n žmonėms

418
00:24:46,280 --> 00:24:51,090
ir aš padaryti, be abejo, 8 žingsnių, n žingsnius, kiekvieną kartą, kai aš einu per šio algoritmo.

419
00:24:51,090 --> 00:24:56,070
Bet kiek kartų blogiausiu atveju aš turiu eiti per šį sąrašą žmonių?

420
00:24:56,070 --> 00:24:59,370
[Studentas] N kartų. >> Tikriausiai n teisūs, nes blogiausiu atveju,

421
00:24:59,370 --> 00:25:03,410
kas tikriausiai blogiausiu atveju susitarimas iš šių vaikinai nuo get-go?

422
00:25:03,410 --> 00:25:06,520
Jei jie visiškai priešinga tvarka

423
00:25:06,520 --> 00:25:09,310
nes tik tarkime protiškai, let's - Koks tavo vardas? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Gerai. Taigi, Bowen, atėjo čia dėl vos akimirką.

425
00:25:12,510 --> 00:25:16,150
>> Tarkime, kad Bowen algoritmo pradžioje čia buvo,

426
00:25:16,150 --> 00:25:19,790
ir mes negalime žinoti, ką visi kiti, bet Bowen čia, pagal šio algoritmo

427
00:25:19,790 --> 00:25:23,820
ir, jei norite, tiesiog pasivaikščioti su manimi vyksta burbulas iki, kaip jis pirmą kartą aplink,

428
00:25:23,820 --> 00:25:25,740
visą kelią iki pabaigos.

429
00:25:25,740 --> 00:25:29,400
Tačiau tarkime, kad asmuo šalia Bowen buvo numeris 7.

430
00:25:29,400 --> 00:25:33,450
Turiu grįžti ir gauti 7 skaičių, o tai reiškia, aš turiu eiti visą kelią atgal čia.

431
00:25:33,450 --> 00:25:36,980
Dabar turiu turėti tą patį pasivaikščioti su asmeniu, kuris yra numeris 7.

432
00:25:36,980 --> 00:25:40,140
Bet kas, jei tada 6 numeris buvo šalia jo, taip pat?

433
00:25:40,140 --> 00:25:42,180
Tada aš turiu grįžti ir gauti 6.

434
00:25:42,180 --> 00:25:46,490
Taigi dar kartą, aš kalbu apie kiekvieną šio ciklo iteracijos n žmonių,

435
00:25:46,490 --> 00:25:50,090
ir aš galėjo padaryti N šių pasivaikščiojimo įsitikinkite, kad Aš traukiant

436
00:25:50,090 --> 00:25:53,760
visų didžiausių elementų atgal ir atgal ir grįžti prie sąrašo galo.

437
00:25:53,760 --> 00:25:58,230
Taigi n dalykų n kartų yra tik n kartų, n arba n langeliais.

438
00:25:58,230 --> 00:26:02,050
>> Taigi čia jau mes turime algoritmą, kuris nebėra n, tai nebėra log n,

439
00:26:02,050 --> 00:26:04,820
tai tikrai blogiau nei ką mes padarėme anksčiau.

440
00:26:04,820 --> 00:26:09,840
Taigi Alex rūšies pasisekė, kad aš darbo, matyt, iš anksto jai,

441
00:26:09,840 --> 00:26:14,690
visi brangaus darbo, kad ji galėtų mėgautis šio dvejetainis paieškos algoritmas,

442
00:26:14,690 --> 00:26:16,420
log n.

443
00:26:16,420 --> 00:26:18,240
Bet tai yra atitikti pirmadienio tema.

444
00:26:18,240 --> 00:26:23,260
Mes davėme šiek tiek daugiau vietos, daugiau bitų, siekiant paspartinti mūsų veikimo laiką.

445
00:26:23,260 --> 00:26:26,170
Tiek daug, kaip ten tai kompromisas tarp laiko ir erdvės,

446
00:26:26,170 --> 00:26:31,060
taip pat gali būti tiesiog nušviečia kompromisus tarp laiko praleisto priekyje rūšiuoti gauti dalykų pasiruošęs eiti

447
00:26:31,060 --> 00:26:35,000
ir faktiškai vykdyti, pavyzdžiui paieškos algoritmas. Pabandykime dar vieną.

448
00:26:35,000 --> 00:26:39,050
Jei jus vaikinai nebūtų proto, tiesiog greitai pertvarkyti save, kad atitiktų, kad vėl,

449
00:26:39,050 --> 00:26:42,240
galime pabandyti kažką šiek tiek kitokį, kur jis yra ne visai taip paprasta

450
00:26:42,240 --> 00:26:45,760
kaip tik išspręsti visas Poromis klaidų, kurios yra super intuityvus.

451
00:26:45,760 --> 00:26:48,150
Tegul vietoj to turi būti šiek tiek labiau apgalvotas ir tai padaryti.

452
00:26:48,150 --> 00:26:51,010
Tai irgi norėčiau pasiūlyti yra tikriausiai gana intuityvus.

453
00:26:51,010 --> 00:26:55,070
>> Leiskite pasirinkti mažiausią asmenį iš sąrašo, vėl ir vėl. Taigi čia mes einame.

454
00:26:55,070 --> 00:26:57,350
4, jums yra mažiausias asmuo, todėl aš mačiau iki šiol,

455
00:26:57,350 --> 00:27:00,520
todėl aš protiškai prisiminti, kad tik nukreipta į jus dabar.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Pamirškite apie skaičių 4. Aš ką tik nustatė naują mažiausią elementą šiame sąraše.

457
00:27:05,020 --> 00:27:07,410
Aš ruošiuosi rūšies prisiminti, kad. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Viso gero. Taigi, dabar aš ruošiuosi prisiminti skaičių 1.

459
00:27:11,190 --> 00:27:14,790
Mes žinome, kad 1 yra mažiausias, bet aš tikiu, kad kompiuteris. Ką daryti, jei ten 0?

460
00:27:14,790 --> 00:27:17,140
Ką daryti, jei -1? Turiu nesustoti.

461
00:27:17,140 --> 00:27:20,990
Taigi, 3, 7, 5, nope. Gerai. Taigi buvo mažiausias skaičius 1.

462
00:27:20,990 --> 00:27:23,640
Leiskite man pasirinkti iš sąrašo - we'll eiti šiuo keliu -

463
00:27:23,640 --> 00:27:27,760
ir padėti jums savavališkai sąrašo pradžioje.

464
00:27:27,760 --> 00:27:29,740
Dabar, palauk. I rūšies apgavo.

465
00:27:29,740 --> 00:27:34,010
Jei šie vaikinai atstovauja ne 8 žmonių sąrašą, tačiau masyvo,

466
00:27:34,010 --> 00:27:37,050
8 gabaliukus vientisos atminties - jūs tai trauktis atgal vos akimirką?

467
00:27:37,050 --> 00:27:39,060
Yra tikrai ne jums erdvė čia.

468
00:27:39,060 --> 00:27:41,840
Taip, kaip mes padaryti vietos - koks tavo vardas? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Kaip mes vietos Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Mes einame n, kurie yra prieš mane. >> Gerai.

471
00:27:46,760 --> 00:27:48,850
Taigi, mes galime perkelti n žmonių, kurie yra prieš jį,

472
00:27:48,850 --> 00:27:52,400
todėl, jei jus vaikinai nori imtis 1 apgalvotą, dramatiškas žingsnis į kairę.

473
00:27:52,400 --> 00:27:57,000
Jie visi sutartinai, bet paskutinį kartą aš parašiau tam tikrą kodą,

474
00:27:57,000 --> 00:27:59,740
Jūs negalite rūšiuoti perkelti daug dalykų vienu metu.

475
00:27:59,740 --> 00:28:02,450
Mes galime tai padaryti kilpą, juda visiems, vieną kartą.

476
00:28:02,450 --> 00:28:04,340
Taigi, jei jus vaikinai nebūtų proto, trauktis atgal į dešinę,

477
00:28:04,340 --> 00:28:07,230
ir Sammy, jei galima žengti žingsnį atgal, nes ten dar ne jums,

478
00:28:07,230 --> 00:28:11,420
dabar galime tai padaryti. Kur buvo Sammy prieš akimirką? Teisę ten.

479
00:28:11,420 --> 00:28:16,140
Taigi čia yra atotrūkis. Kad galėtumėte perkelti į Sammy savo vietoje.

480
00:28:16,140 --> 00:28:20,580
Dabar kitas asmuo ir dabar kitas asmuo, o kitas asmuo. Dabar mes turime kambarį Sammy.

481
00:28:20,580 --> 00:28:23,490
Dabar kas nors iš auditorijos - tai buvo geras, tai buvo teisingas,

482
00:28:23,490 --> 00:28:27,070
ji jautėsi šiek tiek daug laiko - kas greičiau? Taip.

483
00:28:27,070 --> 00:28:29,440
[Studentas] nauja matrica? >> Kas tai? >> [Studentas] nauja matrica? >> Gerai, gerai.

484
00:28:29,440 --> 00:28:33,200
>> Taip nuosekliai šio tik kompromisų tema, kodėl ne aš tiesiog padaryti naują masyvą,

485
00:28:33,200 --> 00:28:36,570
 ir tada Sammy bus plaukiojimas erdvėje priešais šių žmonių, pavyzdžiui,

486
00:28:36,570 --> 00:28:39,600
ir mes galime tiesiog pradėti pildyti naują masyvą, apskritai. Kad per daug dirbtų.

487
00:28:39,600 --> 00:28:42,450
Bet aš ne domina išleisti daugiau vietos šiandien. Kas kitas požiūris?

488
00:28:42,450 --> 00:28:46,630
[Studentas] swap. >> Gerai. Galėtume tiesiog apsikeitimo šių 2 vaikinai. Koks tavo vardas?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Taigi, Mario, šiuo metu čia.

490
00:28:49,390 --> 00:28:52,480
Sammy, galite kurti atsargines kopijas vos akimirką? Mario buvo čia.

491
00:28:52,480 --> 00:28:55,830
Mes neturime jums kambarį nebėra, todėl, jei tai būtų ne tai vyksta kur Sammy,

492
00:28:55,830 --> 00:29:02,430
mes įdėti Sammy čia, ir dabar aš teigia, kad Sammy apsikeitimo operacija buvo daug greitesnis.

493
00:29:02,430 --> 00:29:06,370
Mes padarėme 1 operaciją apsikeitimo šie vaikinai, o gal 2 apsikeitimo šie vaikinai,

494
00:29:06,370 --> 00:29:11,210
bet mes ne padaryti 1, 2, 3, 4, kad jaučiasi geriau. Dabar, palauk.

495
00:29:11,210 --> 00:29:14,660
I rūšies problema dar blogiau, nes numeris 4 buvo natūra arti pradžioje.

496
00:29:14,660 --> 00:29:19,470
Numeris 4 yra šiek tiek priartėti prie šio tikslo, bet aš tikrai nežino, ar rūpi tai.

497
00:29:19,470 --> 00:29:23,330
Taigi tai yra tiesiog nesėkme, kad numeris 4 yra šiek tiek toliau nuo jos lemta vietoje.

498
00:29:23,330 --> 00:29:25,110
Taigi tegul dabar pakartoti šį algoritmą.

499
00:29:25,110 --> 00:29:28,410
>> Apibendrinant galima pasakyti, kaip ilgai, kaip kad istorija buvo, visi mes darė, buvo eiti per sąrašą

500
00:29:28,410 --> 00:29:31,130
ieško mažiausio numeruojama asmens.

501
00:29:31,130 --> 00:29:34,530
Taigi dabar galime tai padaryti dar kartą. Mes neturime nerimauti dėl Sammy nebėra.

502
00:29:34,530 --> 00:29:37,590
Mes galime tiesiog eikite čia. Ooh! Numeris 2. Tai yra gana nedaug.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Gerai, gerai.

504
00:29:41,180 --> 00:29:43,770
Ir, laimei, sutapimas, aš neturiu judėti - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie, nes jis dabar jo tinkamą vietą.

506
00:29:45,910 --> 00:29:48,110
Leiskite tai padaryti ir vėl, ir nekreipti dėmesio į šiuos 2 vaikinai.

507
00:29:48,110 --> 00:29:50,460
6. Tai yra gana nedaug. Ooh! 8 yra tikrai didesnis.

508
00:29:50,460 --> 00:29:53,410
4. Leiskite sutelkti dėmesį į 4. Ooh! 3 yra net geriau.

509
00:29:53,410 --> 00:29:58,290
7 ir 5. Taigi, ką mes darome dabar - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Tegul sukeisti jį su skaičiumi 6.

511
00:30:00,250 --> 00:30:03,570
Taigi, jei 6 ir 3 norėtų sukeisti,

512
00:30:03,570 --> 00:30:07,320
dabar mes tipo Dotarłeś pasisekė, kad 6 yra arčiau, kur ji turėtų būti,

513
00:30:07,320 --> 00:30:10,300
bet tai tik sutapimas čia. Taigi, tegul dabar eikite čia.

514
00:30:10,300 --> 00:30:13,430
8 yra gana mažas skaičius. Ooh! 4 yra mažesnis.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Ką dabar daryti? >> Sukeisti. >> Būtent.

516
00:30:17,130 --> 00:30:19,010
Taigi dabar galime tai padaryti greičiau rūšiuoti.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Kur gi 5 eiti? Geras. Gerai.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 gali likti ten, kur ji yra. Koks tavo vardas? >> Rozali.

519
00:30:28,380 --> 00:30:31,770
Rozali gali likti ten, kur ji yra. 7 gauna į Pažiūrėkime. 7, 8. Gerai.

520
00:30:31,770 --> 00:30:35,100
Taigi 7 gali likti ten, kur ji yra. Koks tavo vardas? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Taigi Amna gali likti ten, kur ji yra, ir skaičius 8 jau yra, kur jis dabar turėtų būti.

522
00:30:39,670 --> 00:30:43,960
Gerai, gerai. Jaučiasi kaip mes tiesiog sukurti sau darbą čia, nors.

523
00:30:43,960 --> 00:30:47,440
Tai, kas galiausiai šio algoritmo veikimo laikas?

524
00:30:47,440 --> 00:30:51,900
Jei mes galvojame apie žmonių, ne kaip 8, bet kaip n? >> Tai n.

525
00:30:51,900 --> 00:30:55,440
Tai n žingsniai, bet mes patikrinti kiekvieną kartą.

526
00:30:55,440 --> 00:30:57,570
Gerai. N, bet jūs patikrinti kiekvieną kartą?

527
00:30:57,570 --> 00:31:03,450
Gerai, bet jei jis n veiksmus, turėtų ne aš buvo galima rūšiuoti jums tiesiog 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Gerai, kad yra didelis skirtumas.

529
00:31:05,590 --> 00:31:08,050
Taigi n kvadrato kodėl? Kas iš tikrųjų vyksta?

530
00:31:08,050 --> 00:31:12,130
Yra n žmonių šiame sąraše, bet rasti mažiausią asmuo sąraše

531
00:31:12,130 --> 00:31:16,200
blogiausiu atveju, kiek žingsnių turiu imtis? >> N.

532
00:31:16,200 --> 00:31:19,160
>> N, teisė, nes blogiausiu atveju, numeris 1 yra ten būdas,

533
00:31:19,160 --> 00:31:20,990
taip, aš turiu eiti gauti jam ar jai.

534
00:31:20,990 --> 00:31:25,500
Ir tada, kai aš pagaliau suvoks, 1 buvo mažiausias, tada ji gana greitai apsikeitimo juos.

535
00:31:25,500 --> 00:31:28,450
Bet dabar aš turiu pradėti nuo pradžių ir ieškoti, kas?

536
00:31:28,450 --> 00:31:31,980
Kitas mažiausias asmuo, kuris yra 2. Jeigu blogiausiu atveju yra 2?

537
00:31:31,980 --> 00:31:34,320
O, Dieve. Tai visi čia būdas pabaigoje.

538
00:31:34,320 --> 00:31:37,000
Todėl dabar aš tiesiog padaryti dar n žingsnių, dar n žingsnių.

539
00:31:37,000 --> 00:31:41,200
Ir jei mes turime n žmonių, o blogiausiu atveju mažiausias asmuo n žingsniai,

540
00:31:41,200 --> 00:31:45,230
tai vėl n times n, tad vėl buvo n kvadrato.

541
00:31:45,230 --> 00:31:47,280
Tai nėra jausmas toks geras.

542
00:31:47,280 --> 00:31:52,150
Ir iš tiesų, net ir geriausiu atveju - manyti, kad jie pradėti nuo surūšiuoti -

543
00:31:52,150 --> 00:31:59,080
kiek žingsnių užtruks mane, naudojant šį algoritmą norite surūšiuoti šių n žmonių?

544
00:31:59,080 --> 00:32:01,010
N kvadratu. >> Aš girdėjau n kvadratu. Kodėl kvadrato n?

545
00:32:01,010 --> 00:32:05,240
Nes jūs vis dar turi patikrinti kiekvieną kartą. >> Taip.

546
00:32:05,240 --> 00:32:08,060
Ir jūs turite apsikeitimo juos. >> Nors mes, žmonės, rūšies visažinis

547
00:32:08,060 --> 00:32:10,770
ta prasme, vizualiai, kad mes galime tiesiog rūšies matyti, kad tai yra rūšiuojamos,

548
00:32:10,770 --> 00:32:12,140
kompiuteris yra ne tai, kad protingas.

549
00:32:12,140 --> 00:32:14,040
Ji ketina rasite čia ir čia ir čia,

550
00:32:14,040 --> 00:32:16,610
bet jei tai, ką jis ieško yra mažiausias elementas,

551
00:32:16,610 --> 00:32:22,110
žinote tik, kad jums rasti mažiausią elementą, ką taškas? Kai esate pabaigoje.

552
00:32:22,110 --> 00:32:25,880
Bet tuo momentu jūs tik šiuo metu mažiausią elementą.

553
00:32:25,880 --> 00:32:28,810
Jūs nebūtinai žinoti dar ką nors apie pasaulio būklę.

554
00:32:28,810 --> 00:32:30,880
Taigi jūs turite eiti vėl ir vėl ir vėl.

555
00:32:30,880 --> 00:32:34,880
>> Todėl šį kartą aš tikrai atrodo kvailas, nes aš patikrinti, gerai, 2, jūs mažiausias,

556
00:32:34,880 --> 00:32:37,530
bet aš nemanau, žino, kad iš viso dar.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Gerai, gerai. 2 iš tikrųjų buvo mažiausias.

558
00:32:41,090 --> 00:32:43,150
Dabar galime rasti kitas mažiausias. Gerai.

559
00:32:43,150 --> 00:32:48,350
3, jūs šiuo metu mažiausias. Pažiūrėkime. 4, 5, 6, 7, 8. Gerai, vėl pasisekė.

560
00:32:48,350 --> 00:32:53,170
3 buvo tikrai tinkamoje vietoje. Bet aš ruošiuosi išlaikyti tai daryti vėl ir vėl ir vėl.

561
00:32:53,170 --> 00:32:55,990
Kaip mes galime padaryti, vis tiek šiek tiek geriau?

562
00:32:55,990 --> 00:33:00,120
Vietoj to, kad žmonės burbulas poravimas nuo mažiausio iki didžiausio

563
00:33:00,120 --> 00:33:04,350
ir vietoj vyksta pirmyn ir atgal per sąrašo pasirinkdami tada mažiausias asmuo,

564
00:33:04,350 --> 00:33:09,780
kodėl ne mes, o ne įterpti šiuos žmones į naują sąrašą žingsnis po žingsnio?

565
00:33:09,780 --> 00:33:13,080
Pabandykime tai. Dabar leiskite man skambinti šis dalykas įterpimo rūšiuoti.

566
00:33:13,080 --> 00:33:17,250
Taigi čia mes esame čia. Numeris 1. Man nerūpi niekam šiame sąraše.

567
00:33:17,250 --> 00:33:21,310
Mano tikslas dabar yra 1 rūšiuotų sąrašą pradžioje.

568
00:33:21,310 --> 00:33:23,910
Ir aš norėčiau pasiūlyti, nes turiu tik 8 gabaliukus atminties,

569
00:33:23,910 --> 00:33:28,670
savavališkai dabar aš esu siena tarp mano tariamai nerūšiuotų sąrašą,

570
00:33:28,670 --> 00:33:32,740
ir tiems, kurie yra už mane, aš ruošiuosi teigti, surūšiuoti.

571
00:33:32,740 --> 00:33:34,680
Taigi dabar mes turime 1.

572
00:33:34,680 --> 00:33:39,240
Norite įterpti jį į mano rūšiuotų sąrašą, todėl aš tik ketina perkelti savo sieną čia,

573
00:33:39,240 --> 00:33:43,930
ir dabar aš tvirtina, šis sąrašas surūšiuotas, šis sąrašas nerūšiuotų - bent jau kiek aš žinau.

574
00:33:43,930 --> 00:33:46,070
Aš negaliu pamatyti visus numerius iš karto.

575
00:33:46,070 --> 00:33:49,000
>> Dabar aš atsitiktų susidurti skaičių 2. Ką man daryti su juo?

576
00:33:49,000 --> 00:33:54,380
Įterpti į rūšiuotų sąrašą. , Bet pastebėsite, kaip lengvai, kad buvo.

577
00:33:54,380 --> 00:33:59,650
Aš tiesiog ieškoti. Numeris 1 yra. O, be abejo, 2 numeriu 1 pusėje.

578
00:33:59,650 --> 00:34:03,700
Dabar ką man daryti su 3? Aš įtraukti jus į išrūšiuotų sąrašą. Bet tai buvo super lengva.

579
00:34:03,700 --> 00:34:07,250
Tai super lengva, tai yra super lengva, tai yra super lengva, super lengva, super lengva.

580
00:34:07,250 --> 00:34:12,790
Ir dabar viskas yra rūšiuojama už mane, ir kiek žingsnių, kad imtis?

581
00:34:12,790 --> 00:34:15,620
[Mokiniai] N. >> Taigi, tai tik n. Mes pasisekė.

582
00:34:15,620 --> 00:34:18,860
Tai buvo tik n kodėl? >> [Studentas] Kadangi šis sąrašas buvo išrūšiuotos.

583
00:34:18,860 --> 00:34:21,630
Sąrašas jau yra rūšiuojamos. Taigi, mes pasisekė.

584
00:34:21,630 --> 00:34:25,639
Bet mes sukūrėme algoritmą, šį kartą,, kuri panaudoja sėkmės natūra,

585
00:34:25,639 --> 00:34:29,420
kad geriausio atvejo scenarijus, ne eikvoti nereikalingo laiko.

586
00:34:29,420 --> 00:34:31,750
Taigi dabar mes turime tai, ką mes vadiname burbulas rūšių

587
00:34:31,750 --> 00:34:33,949
kur žmonės rūšies burbulas iki Porinis.

588
00:34:33,949 --> 00:34:38,100
Dabar mes turime pasirinkimo rūšiuoti, kur mes Wyłupać mažiausias asmuo, vėl ir vėl.

589
00:34:38,100 --> 00:34:42,350
Ir dabar mes turime įterpimo rūšiuoti, kur mes tarsi aktyviai įdėti žmonių, kur jie priklauso

590
00:34:42,350 --> 00:34:45,000
vis rūšiuotų sąrašą.

591
00:34:45,000 --> 00:34:49,679
Šių vaikinai čia jei galėtume, ar plojimų. [Plojimai]

592
00:34:49,679 --> 00:34:52,310
Paimkime mūsų 5-minučių pertrauką.

593
00:34:52,310 --> 00:34:55,139
Ir kai mes einame atgal, mes bus smūgis iš vandens visų šių algoritmų

594
00:34:55,139 --> 00:35:00,260
kažką geresnio. Gerai. Labai ačiū. Jūs galite laikyti, kaip suvenyrus.

595
00:35:01,710 --> 00:35:04,330
Gerai. Mes atgal.

596
00:35:04,330 --> 00:35:08,420
>> Ir Priminti labai greitai, mes turėjome šias 3 skirtingus požiūrius rūšiavimo,

597
00:35:08,420 --> 00:35:13,000
esmė, iš kurių buvo gauti iki taško, kur kažkas panašaus Alex

598
00:35:13,000 --> 00:35:16,930
galite ieškoti numerių greičiau nei kažkas panašaus Sean galėtų sąrašą.

599
00:35:16,930 --> 00:35:19,830
Ir nors mes turime tokių paprastų pavyzdžių su 8 numeriais,

600
00:35:19,830 --> 00:35:24,000
jums gali ekstrapoliuoti lengvai 8 tinklalapius, 8 milijardų puslapių,

601
00:35:24,000 --> 00:35:26,680
arba 800 mln. draugus į "Facebook".

602
00:35:26,680 --> 00:35:30,090
Taigi šie algoritmai tikrai gali prisiderinti prie tų vertybių rūšių,

603
00:35:30,090 --> 00:35:32,300
ir idėjos yra galų gale tas pats.

604
00:35:32,300 --> 00:35:36,140
Taigi burbulas tarsi buvo pirmoji, kur mes tipo burbuliukais sudaro didžiausią asmuo

605
00:35:36,140 --> 00:35:39,110
visą kelią į dešinę, keičiant žmonių poravimas.

606
00:35:39,110 --> 00:35:42,040
Tada mes turėjome tai, ką mes vadiname atrankos rūšiuoti ten, kur aš šiek tiek daugiau sąmoningai

607
00:35:42,040 --> 00:35:46,480
nuolat ieško per sąrašą, pasirenkant mažiausią skaičių vėl ir vėl ir vėl,

608
00:35:46,480 --> 00:35:49,530
logiškai mąstant, yra tai, kad šis sąrašas būtų galiausiai surūšiuoti.

609
00:35:49,530 --> 00:35:53,780
Tada trečiojoje dalyje, Aš įtraukė žmones į savo tinkamoje vietoje,

610
00:35:53,780 --> 00:35:57,720
ir mes padarėme labai nenatūralu pavyzdį, kad šis sąrašas jau buvo surūšiuoti,

611
00:35:57,720 --> 00:36:01,100
bet tai buvo siųsti prane ¹ im ±, kad įterpimo Rūšiuoti atveju,

612
00:36:01,100 --> 00:36:02,670
galite gauti pasisekė.

613
00:36:02,670 --> 00:36:07,930
Jei skaičiai jau surūšiuoti, tai tik jus n veiksmų tai patvirtinti, kiek,

614
00:36:07,930 --> 00:36:10,870
o atrankos rūšiuoti esate šiek tiek daugiau Tunnel Vision

615
00:36:10,870 --> 00:36:14,360
ir jūs neturite kada nors suprasti, kad sąrašas jau yra rūšiuojamos.

616
00:36:14,360 --> 00:36:16,830
Taigi pažiūrėkime, burbulas rūšiuoti metu čia.

617
00:36:16,830 --> 00:36:19,590
Toliau pateiktame pavyzdyje, mes apie norėdami pamatyti vertikalios juostos

618
00:36:19,590 --> 00:36:23,030
, kurių aukštis sudaro numerius, kad galėtume rūšiuoti Vizualizuoti rūšiavimas atsitikti.

619
00:36:23,030 --> 00:36:26,630
Kuo mažesnis baras, Kuo šis skaičius mažesnis, tuo didesnė juosta, tuo didesnis skaičius.

620
00:36:26,630 --> 00:36:28,860
>> Ir mes jį žaisti nutylėjimą greičiu.

621
00:36:28,860 --> 00:36:33,460
Ji ketina perkelti truputį per greitai dabar, bet raudona, ką rodo 2 barai

622
00:36:33,460 --> 00:36:35,480
yra lyginami vienas šalia kito.

623
00:36:35,480 --> 00:36:39,520
Ir jei jūs atidžiai stebėti, kas atsitinka, yra ta, kad, jei juostos yra ne iš eilės,

624
00:36:39,520 --> 00:36:42,300
mažesnioji bus perkeltas į kairę, didesnį vienas į dešinę,

625
00:36:42,300 --> 00:36:44,360
ir tada jūs nuolat didėja.

626
00:36:44,360 --> 00:36:48,520
Taigi, jei mes vėl ir vėl, pastebėsite, kad mažiausi barai

627
00:36:48,520 --> 00:36:51,090
ketinate laikyti pamažu virsta savo kelią į kairę

628
00:36:51,090 --> 00:36:54,130
ir didžiausi barai ketinate laikyti pamažu virsta savo kelią į dešinę.

629
00:36:54,130 --> 00:36:58,490
Ir iš tiesų, mes pradedame modeliui, kad matytumėte visą kelią dešinėje

630
00:36:58,490 --> 00:37:04,790
tik kaip matėme 8 ir 7 ilgainiui burbuliuoja iki mūsų žmogiškosios sąrašą toli pabaigos.

631
00:37:04,790 --> 00:37:08,750
Taigi, tai vyksta labai greitai gauti šiek tiek varginantis, todėl leiskite man sustabdyti tai minutėlę.

632
00:37:08,750 --> 00:37:10,980
Leiskite man pakeisti greitį bus daug spartesnis.

633
00:37:10,980 --> 00:37:15,380
Aš ne pakeisti algoritmą, aš tiesiog padaryti animacija įvykti greičiau.

634
00:37:15,380 --> 00:37:18,410
Dar burbulas rūšiuoti, pats algoritmas,

635
00:37:18,410 --> 00:37:21,910
tačiau dabar jūs galite pamatyti daug greičiau nei mūsų žodinio demonstravimo

636
00:37:21,910 --> 00:37:25,900
kad didžiausi elementai iš tiesų yra burbuliuoja iki viršaus.

637
00:37:25,900 --> 00:37:29,860
>> Kaip panaikinti apačioje, kairėje pusėje, šių mažai kvadratų ir apatiniame dešiniajame

638
00:37:29,860 --> 00:37:33,520
yra tik šiek tiek priminimus kiek palyginimai jūs darote.

639
00:37:33,520 --> 00:37:37,620
Bet dabar, mes galime sutelkti dėmesį į piramidės, kuri įgauna formą, ir ten eina.

640
00:37:37,620 --> 00:37:41,510
Mažiausias elementas yra kairėje, dešinėje didžiausių ir visa kita tarp.

641
00:37:41,510 --> 00:37:44,470
Dabar tegul vietoj imtis atrankoje rūšiuoti išvaizdą.

642
00:37:44,470 --> 00:37:47,260
Aš ruošiuosi eiti į priekį ir paspauskite Stabdyti. Mes ketiname gauti naują atsitiktinį rinkinį barų.

643
00:37:47,260 --> 00:37:50,930
Pasirinkimas rūšiuoti, išėmimą iš apyvartos, eina per sąrašą vėl ir vėl ir vėl,

644
00:37:50,930 --> 00:37:54,900
skynimas mažiausias elementas. Taigi čia yra pasirinkimas rūšiuoti.

645
00:37:54,900 --> 00:37:58,390
Atrodo, kad ten mažiau darbo, vyksta dabar, nes mes ne lyginant poromis

646
00:37:58,390 --> 00:38:02,590
bet mes tiesiog tarsi vyšnių skynimas ir smulkiausi elementai iš dešinės į kairę.

647
00:38:02,590 --> 00:38:06,890
Tai buvo labai mažai laiko, todėl dichotomija jau.

648
00:38:06,890 --> 00:38:11,820
Tiesiog todėl, kad algoritmas yra nurodyta, jog n kvadratu laiko, kaip burbulas rūšiuoti

649
00:38:11,820 --> 00:38:16,100
ir kaip atrankos rūšiuoti, jie yra tikrai blogiausias veikia kartus.

650
00:38:16,100 --> 00:38:21,790
Pavyzdžiui, tuo atveju, tarkim, atrankos rūšiuoti,

651
00:38:21,790 --> 00:38:27,240
Aš iš tikrųjų esu pasirenkant mažiausią asmuo ir pradėti jį arba ją čia,

652
00:38:27,240 --> 00:38:29,620
tada aš vėl tai daro, tada aš darau jį dar kartą,

653
00:38:29,620 --> 00:38:32,070
bet ten buvo šiek tiek optimizavimas galėčiau padaryti.

654
00:38:32,070 --> 00:38:35,040
>> Kaip tik aš persikėlė numeris čia 1 - Sammy šiuo atveju -

655
00:38:35,040 --> 00:38:38,630
ką man reikia daryti su juo po to? >> [Studentas] Palik jį.

656
00:38:38,630 --> 00:38:40,140
Palik jį, tiesa? Nieko.

657
00:38:40,140 --> 00:38:44,310
Man nereikia, kad kada nors vėl pasikalbėti su Sammy, nes jei aš buvo pasirinktas mažiausias elementas

658
00:38:44,310 --> 00:38:48,580
ir įdėti jį čia, kodėl gaišti laiką vyksta į mano visą sąrašą?

659
00:38:48,580 --> 00:38:54,590
Kitą iteracijos leiskite man iš tikrųjų judėti tik skaičius "2", tik numeris 3.

660
00:38:54,590 --> 00:38:57,640
Taigi iš tikrųjų, aš buvo ne daro n daiktus n kartų.

661
00:38:57,640 --> 00:39:05,380
Darau n dalykų, tada "n - 1 dalykai, tada n - 2 dalykų, tada n - 3 Things

662
00:39:05,380 --> 00:39:07,080
tada "n" - 4, taškas, taškas, taškas.

663
00:39:07,080 --> 00:39:09,470
Mes turime geometrine progresija, kuris tiesiog reiškia, kad tiek

664
00:39:09,470 --> 00:39:11,450
norite pridėti palaipsniui mažesniais skaičiais.

665
00:39:11,450 --> 00:39:17,940
Ne n + n + n + n, bet n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
Ir kas, kad paprastai dirba esąs -

667
00:39:21,380 --> 00:39:24,280
Aš ruošiuosi bałagan mano lenta čia tik akimirką -

668
00:39:24,280 --> 00:39:28,990
kad vyksta dirbti, turi būti kažkas panašaus n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
jei mes tiesiog pažvelgti rūšies matematikos knygą, kur jūs turite visas Ruošinukai atgal

670
00:39:31,930 --> 00:39:33,410
formules.

671
00:39:33,410 --> 00:39:37,760
Jei jūs tiesiog pridedant kažką n + n - 1 + n - 2, jis veikia esąs kažkas panašaus į tai.

672
00:39:37,760 --> 00:39:42,320
Ir jei mes tiesiog rūšies dauginti this out, tai n kvadrato atėmus n / 2.

673
00:39:42,320 --> 00:39:46,400
Aš nuolat sako n kvadrato, nors, ir tai todėl, kad buvau rūšies psichikos nuorodą

674
00:39:46,400 --> 00:39:51,950
nes iš tikrųjų, n kvadrato atėmus n padalinti iš 2 yra iš tikrųjų tiesa pakopų skaičius

675
00:39:51,950 --> 00:39:55,510
, kad kaip atrankos rūšiuoti algoritmas užtruktų, jei mes tikrai paskaičiavo

676
00:39:55,510 --> 00:39:58,800
visi šie palyginimai ir visi šiek tiek užimtas darbo, mes darome.

677
00:39:58,800 --> 00:40:03,210
Bet atvirai, kai n gali būti kaip milijono ar milijardo eurų, kas gi rūpi

678
00:40:03,210 --> 00:40:07,160
jei jūs darote mlrd kvadratu minus milijardą padalinti iš 2?

679
00:40:07,160 --> 00:40:09,320
Mlrd kvadratu yra labai daug.

680
00:40:09,320 --> 00:40:13,580
Jūs galite pasiimti kitą mlrd off - n. Tai ne tokia baisi.

681
00:40:13,580 --> 00:40:18,770
Taigi didesnis skaičiai gauti, mažiau svarbūs šios mažesnės išplanuotomis sąlygos.

682
00:40:18,770 --> 00:40:24,230
Who cares, jei reikia padalinti iš 2, jei jūs kalbate apie quadrillions pakopų skaičių?

683
00:40:24,230 --> 00:40:29,710
>> Taigi apskritai kompiuterių mokslininkai linkę išmesti viską, bet didžiausią santykiai,

684
00:40:29,710 --> 00:40:33,140
ir mes tiesiog rūšies supaprastinti pasaulį ir pasakyti, kad šis algoritmas

685
00:40:33,140 --> 00:40:38,130
paėmė maždaug n kvadrato veiksmus. Štai algoritmu veikimo laikas.

686
00:40:38,130 --> 00:40:40,760
Taigi, mes grįžti į šį vos akimirką su kai kuriais konkrečiais pavyzdžiais,

687
00:40:40,760 --> 00:40:45,940
bet dabar, tai tarsi intuityvi motyvacija už tiesiog supaprastinti mūsų pasaulį

688
00:40:45,940 --> 00:40:51,170
ir kalbėti apie svarbiausių terminų, o ne patekti į visų šių išgalvotas formules.

689
00:40:51,170 --> 00:40:53,540
Kad buvo atrankos rūšiuoti, ir mes turime šiek tiek pasisekė.

690
00:40:53,540 --> 00:40:57,360
Pažvelkime įterpimo rūšiuoti. Leiskite man eiti į priekį ir pradėti šį vieną, taip pat.

691
00:40:57,360 --> 00:41:00,330
Dabar pastebėsite modelį, kuris manimi vyksta, yra šiek tiek kitoks,

692
00:41:00,330 --> 00:41:03,410
ir mes pradėjome su atsitiktinių skaičių,

693
00:41:03,410 --> 00:41:06,890
bet jei mes iš tikrųjų skaičiuoti žingsnių, blogiausiu atveju,

694
00:41:06,890 --> 00:41:11,070
jei sąrašas prasidėjo visiškai teisinga tvarka,

695
00:41:11,070 --> 00:41:13,380
mes tik imtis n veiksmus suvokti, kiek.

696
00:41:13,380 --> 00:41:18,240
>> Bet jei sąrašas buvo faktiškai atgal - pavyzdžiui, šiuo atveju čia -

697
00:41:18,240 --> 00:41:23,860
tada pastebėsite, mes iš tikrųjų turime padaryti daug daugiau darbo, šiuo atveju.

698
00:41:23,860 --> 00:41:27,080
Ir ji turėtų rūšies manai, kaip tai vienas natūra dirbti sunkiau

699
00:41:27,080 --> 00:41:30,900
gauti tuos mažesnius elementus į kairę, ir tai, nes mes turime nelaimingas.

700
00:41:30,900 --> 00:41:34,210
Sąrašas buvo surūšiuoti netyčia atbuline eiga.

701
00:41:34,210 --> 00:41:38,110
Priešingai, su prierašu rūšiuoti, jei mes imituoti tai, ką mes padarėme su mūsų žmonėms čia

702
00:41:38,110 --> 00:41:42,670
rūšiuotas visiems pradedant ir tada pradėti, tai gana geras algoritmas, tiesa?

703
00:41:42,670 --> 00:41:45,010
Tai jau, tiesą sakant, surūšiuoti.

704
00:41:45,010 --> 00:41:48,670
Taigi, pabandykime apibendrinti, tiksliai, kiek laiko šie dalykai mums

705
00:41:48,670 --> 00:41:52,360
įvedant tik šiek tiek žargono ar notacija, kas iš tikrųjų daug paprasčiau

706
00:41:52,360 --> 00:41:54,320
nei fanciness tarsi rodo.

707
00:41:54,320 --> 00:41:59,030
Tai, ką čia, tai didelis O ekrane yra tai, ką kompiuteris mokslininkas paprastai naudoja

708
00:41:59,030 --> 00:42:03,640
apibūdinti blogiausio atvejo veikimo laikas algoritmą.

709
00:42:03,640 --> 00:42:07,360
>> Dar kartą, blogiausiu atveju, tai visiškai priklauso nuo konteksto.

710
00:42:07,360 --> 00:42:10,890
Ką mes vadiname blogiausiu atveju visiškai skiriasi priklausomai nuo problemos, mes kalbame apie.

711
00:42:10,890 --> 00:42:14,550
Bet, rūšiavimo, kas yra blogiausias galimas scenarijus?

712
00:42:14,550 --> 00:42:17,860
Viskas yra atgal, nes jis tiesiog mano, kaip tai reiškia, kad mums daug darbo.

713
00:42:17,860 --> 00:42:21,330
Aš jotted keli algoritmai, kad mes matėme iki šiol:

714
00:42:21,330 --> 00:42:24,930
linijinis paieška, dvejetainis paieškos kaip su telefonų knygoje arba popieriaus likučių,

715
00:42:24,930 --> 00:42:28,960
burbulas rūšiuoti, atranka rūšiuoti ir įterpimo Rūšiuoti, kaip matėme su mūsų žmonėms,

716
00:42:28,960 --> 00:42:31,770
ir tada 1 kita, kad galiausiai bus vadinamas sujungti rūšiuoti.

717
00:42:31,770 --> 00:42:37,710
Taigi, tiesinio paiešką blogiausiu atveju, kiek žingsnių reikia, rasti skaičių 7

718
00:42:37,710 --> 00:42:40,690
jei yra n durys, pavyzdžiui, Sean, su kuriomis susiduria? >> [Studentas] N.

719
00:42:40,690 --> 00:42:44,180
N. Taigi, mes ketiname rašyti Big O n.

720
00:42:44,180 --> 00:42:47,010
Aš tik ketina užpildyti kai kurių ruošiniai. Tai tik ruošiniai tinklelis.

721
00:42:47,010 --> 00:42:52,990
Tačiau geriausiu atveju su linijiniu paieškos, 7 galėjo pačioje sąrašo pradžioje,

722
00:42:52,990 --> 00:42:55,520
ir Sean galėjo pradėti žiūri sąrašo pradžioje.

723
00:42:55,520 --> 00:42:58,940
Taigi, jei jūs tiesinio paieškos ir tiesiog patikrinti iš kairės į dešinę, o gal ir iš dešinės į kairę -

724
00:42:58,940 --> 00:43:02,650
jie atitinka - geriausiu atveju, kiek žingsnių gali linijinis paieška

725
00:43:02,650 --> 00:43:05,550
kaip Sean algoritmas imtis? Tik 1 žingsnis.

726
00:43:05,550 --> 00:43:09,450
>> Taigi, aš ketina pasakyti, kad omega notacijos.

727
00:43:09,450 --> 00:43:11,570
Tai tik kapitalas omega.

728
00:43:11,570 --> 00:43:15,000
Omega yra tik seksualus būdas pasakyti, geriausiu atveju važiavimo laikas.

729
00:43:15,000 --> 00:43:18,900
Taigi, geriausiu atveju veikimo laikas yra vienas žingsnis, ar nuolatinis pakopų skaičius -

730
00:43:18,900 --> 00:43:24,270
Šiuo atveju 1 - bet blogiausiu atveju, Big O, tai tikrai n žingsnių.

731
00:43:24,270 --> 00:43:28,110
Ir tai vienas čia, teta, mes iš tikrųjų nesiruošia ieškoti ne dabar.

732
00:43:28,110 --> 00:43:30,090
Tai nėra susiję su šiuo konkrečiu pavyzdžiu.

733
00:43:30,090 --> 00:43:31,990
Bet dabar pabandykime Dvejetainė paieška.

734
00:43:31,990 --> 00:43:35,990
Blogiausiu atveju dvejetainis paieškos, kiek žingsnių jis ketina imtis, kad būtų rasti 7

735
00:43:35,990 --> 00:43:38,340
bet mes ieškome? >> [Studentas] Prisijungti n.

736
00:43:38,340 --> 00:43:40,980
Vis dar ketina imtis log n, nes kaip ir Alex gavo nelaimingas

737
00:43:40,980 --> 00:43:44,030
kai mes iš tikrųjų dirbo per problema metodiškai

738
00:43:44,030 --> 00:43:48,220
, ir ji neturėjo iki pat paskutinio duris, ji pažvelgė į skaičių 7,

739
00:43:48,220 --> 00:43:51,720
nors, tiesą sakant, ji gavo išmesti tam tikras duris pakeliui,

740
00:43:51,720 --> 00:43:56,920
blogiausiu atveju dvejetainis paieškos log n veikimo laiką.

741
00:43:56,920 --> 00:43:59,230
Ir vėl, kad kalba tai dalijant ir užkariauti.

742
00:43:59,230 --> 00:44:01,140
Bet kas apie geriausiu atveju?

743
00:44:01,140 --> 00:44:04,790
Ir Alex iš tikrųjų patyrė, kad geriausiu atveju, kai ji atėjo į sceną.

744
00:44:04,790 --> 00:44:07,290
Kiek žingsnių imtis dvejetainis paieškos? >> [Studentas] 1.

745
00:44:07,290 --> 00:44:09,380
1, tik todėl, kad ji pasisekė.

746
00:44:09,380 --> 00:44:12,520
Bet tai gerai, nes omega reiškia geriausią scenarijų,

747
00:44:12,520 --> 00:44:15,770
geriausiu atveju sąnaudos, net jei tai tik atsitiktinis kvailas sėkmės.

748
00:44:15,770 --> 00:44:18,900
>> Dabar tai taip pat mes ketiname tik rūšies palikite tuščią dabar.

749
00:44:18,900 --> 00:44:21,010
Kaip apie dabar burbulas rūšiuoti?

750
00:44:21,010 --> 00:44:24,290
Burbulas rūšiuoti, blogiausiu atveju, kiekvienas yra atvirkštine tvarka,

751
00:44:24,290 --> 00:44:26,380
todėl mes turime padaryti, burbuliuoja daug.

752
00:44:26,380 --> 00:44:30,190
Bet kiek žingsnių yra tai, kad ketina imtis blogiausiu atveju? >> [Studentas] N kvadratu.

753
00:44:30,190 --> 00:44:32,550
Tai buvo n kvadrato, nes jei jūs manote apie tai,

754
00:44:32,550 --> 00:44:36,410
jei sąrašas yra visiškai atgal - 8 yra čia, 1 per čia -

755
00:44:36,410 --> 00:44:40,530
kaip dalykas pradeda burbuliuoti, numeris 8 ketina perkelti šį kelią, tokiu būdu,

756
00:44:40,530 --> 00:44:44,540
tokiu būdu, tokiu būdu, bet kur yra numeris 7 blogiausiu atveju?

757
00:44:44,540 --> 00:44:47,720
Čia ji vis dar ten. Taigi, mes turime tai daryti vėl ir vėl.

758
00:44:47,720 --> 00:44:53,190
Ir tai, kai mes gauname n žingsnių, tada "n - 1 etapai, tada n - 2 žingsniai.

759
00:44:53,190 --> 00:44:55,960
Ir jei jūs imtis savo žodį, kad jei jūs rūšies padauginkite jį iš,

760
00:44:55,960 --> 00:45:00,110
Apytiksliai tai n kvadrato galų gale su kai kuriomis kitomis sąlygomis, kad mes tiesiog ignoruoti dabar -

761
00:45:00,110 --> 00:45:06,890
tada blogiausiu atveju burbulas rūšiuoti yra n kvadrato, duoti ar priimti.

762
00:45:06,890 --> 00:45:09,490
Bet kas apie geriausiu atveju su burbulas rūšiuoti?

763
00:45:09,490 --> 00:45:13,050
Koks yra geriausias scenarijus? Visus numerius yra rūšiuojamos jau.

764
00:45:13,050 --> 00:45:15,920
Ir kas buvo aš naudojamas, triukas, aš naudojamas euristinis,

765
00:45:15,920 --> 00:45:20,110
suprasti, kad aš nepadarė nieko darbą ir gali nutraukti anksti?

766
00:45:20,110 --> 00:45:23,590
[Studentas] Patikrinkite jį vieną kartą. >> Patikrinkite jo dar kartą. Bet ką darau pakeliui?

767
00:45:23,590 --> 00:45:26,130
Sekti kiek apsikeitimo sandoriai aš padariau.

768
00:45:26,130 --> 00:45:30,650
Ir aš supratau, jei aš nėra skaičiuojami apsikeitimo sandorius mano pirštus, tada aš padariau jokio darbo.

769
00:45:30,650 --> 00:45:34,300
Aš tikrai neturėtų bandyti vėl ir nedirbsite jokio darbo, todėl galiu tiesiog sustoti.

770
00:45:34,300 --> 00:45:37,830
>> Taigi, geriausiu atveju Bubble rūšiuoti, kai šis sąrašas jau rūšiuojamos,

771
00:45:37,830 --> 00:45:41,530
ką jūs pasakytumėte, omega notacijos, geriausiu atveju veikia gyvenimą?

772
00:45:41,530 --> 00:45:48,040
Tai tiesiog n. Mes turime padaryti tam tikrą darbą, bet turime tik tai padaryti 1 klaidžioti verta darbo.

773
00:45:48,040 --> 00:45:50,490
Ir čia aš ruošiuosi palikite tuščią.

774
00:45:50,490 --> 00:45:52,430
Ir dabar pasirinkimas rūšiuoti.

775
00:45:52,430 --> 00:45:56,010
Pasirinkimas man buvo tarsi skynimas mažiausias asmuo vėl ir vėl.

776
00:45:56,010 --> 00:45:58,380
Ir ką mes sakome, veikimo laikas, kad buvo?

777
00:45:58,380 --> 00:46:00,590
Tai buvo n kvadrato blogiausiu atveju.

778
00:46:00,590 --> 00:46:05,220
Ir, deja, geriausiu atveju jis taip pat n kvadrato

779
00:46:05,220 --> 00:46:08,840
nes aš neturiu visažinis nuomone viso pasaulio Rūšiuoti pagal

780
00:46:08,840 --> 00:46:13,140
Aš tik žinau, nuo visiško iteracijos, kad aš iš tikrųjų rado mažiausią asmuo.

781
00:46:13,140 --> 00:46:15,860
Taigi pasirinkimas rūšiuoti rūšies sucks ta prasme,

782
00:46:15,860 --> 00:46:17,920
bet aukštyn, tai tipo intuityvus.

783
00:46:17,920 --> 00:46:21,470
Tai gana lengva kodą, nes viskas, ką jums reikia padaryti yra rašyti lizdinė už kilpos pora,

784
00:46:21,470 --> 00:46:24,620
paprastai, kad eina per ieško mažiausio elemento

785
00:46:24,620 --> 00:46:27,840
ir tada kelia mažiausią elementą, kur jis priklauso sąrašo pabaigoje.

786
00:46:27,840 --> 00:46:29,900
Taigi čia taip pat bus kompromisas.

787
00:46:29,900 --> 00:46:34,440
, Kiek laiko užtrunka jums galvoti ir sukurti kažką rašyti kodą

788
00:46:34,440 --> 00:46:39,460
galėtų labai gerai daugiau laiko, jei norite geriau algoritmas ir geresnį efektyvumą.

789
00:46:39,460 --> 00:46:41,780
>> Tačiau Jums tiesiog malonu kodas kažkas ne greitas ir purvinas

790
00:46:41,780 --> 00:46:45,000
ir tiesiog rūšies stupidest idėją, jūs galite galvoti,

791
00:46:45,000 --> 00:46:47,580
, kuris gali užtrukti keletą minučių kodą, tačiau su didelių duomenų rinkinių

792
00:46:47,580 --> 00:46:49,580
Jūsų algoritmas gali imtis valandų paleisti.

793
00:46:49,580 --> 00:46:51,690
Ir net aš kartais, kad šios aukštosios mokyklos kompromisus.

794
00:46:51,690 --> 00:46:55,660
Būtų 03:00, aš bandžiau analizuoti kai kurių labai didelių duomenų rinkinį

795
00:46:55,660 --> 00:46:59,650
susiję su saugumo mokslinių tyrimų, aš darau, ir jis buvo arba praleisti 5 minutes

796
00:46:59,650 --> 00:47:03,210
truputį keisdami savo programą, analizuoti duomenis ir eiti miegoti

797
00:47:03,210 --> 00:47:08,420
arba praleisti 8 valandas gauti tik teisę, kad jis eina iš karto, o ne eiti miegoti.

798
00:47:08,420 --> 00:47:10,530
Ir taip yra per daug tai tipo sąmoningo sprendimo.

799
00:47:10,530 --> 00:47:12,740
Mažiau kūrimo laikas, daugiau miego.

800
00:47:12,740 --> 00:47:14,780
Žvelgiant atgal, aš tikriausiai neturėtų skatinti, kad

801
00:47:14,780 --> 00:47:19,120
kai tikslas čia yra optimizuoti kodo kokybę,

802
00:47:19,120 --> 00:47:21,280
tačiau per realiame pasaulyje yra labai priimtiną kompromisą.

803
00:47:21,280 --> 00:47:25,130
Mažiau laiko, mažiau atlikimas arba atvirkščiai.

804
00:47:25,130 --> 00:47:28,110
Taigi čia mes pagaliau gauti galimybę pasikalbėti apie teta.

805
00:47:28,110 --> 00:47:32,830
Teta notacijos yra kažkas, kompiuterių mokslininkai gali auklėti pokalbis

806
00:47:32,830 --> 00:47:36,160
kai didelis O ir omega atsitiktų būti tas pats.

807
00:47:36,160 --> 00:47:40,160
Jūs sakote, kad teta tikrai pasiųs signalą, kad tai rūšies stora privalo.

808
00:47:40,160 --> 00:47:43,340
Nesvarbu, ar scenarijus yra geras, ar blogas, tai n kvadratu.

809
00:47:43,340 --> 00:47:46,510
Todėl tiesiog nėra svarbus šių istorijų čia.

810
00:47:46,510 --> 00:47:48,560
Įterpimo rūšiuoti naujausia, mes pažvelgė,

811
00:47:48,560 --> 00:47:50,830
kai man buvo tiesiog įterpiant visiems į tinkamą vietą.

812
00:47:50,830 --> 00:47:54,930
Geriausiu atveju, tai, kas buvo įterpimo Rūšiuoti veikimo laikas kaip matėme čia?

813
00:47:54,930 --> 00:47:57,250
[Studentas] geriausiu atveju? >> Geriausiu atveju.

814
00:47:57,250 --> 00:48:00,100
>> N, nes geriausiu atveju visi rūšiuojami,

815
00:48:00,100 --> 00:48:02,580
ir Sammy ir niekas tikrai turėjo perkelti ne visi.

816
00:48:02,580 --> 00:48:04,610
Jie jau savo tinkamoje vietoje.

817
00:48:04,610 --> 00:48:08,570
Taigi įterpimas rūšiuoti geriausiu atveju, šiuo atveju, n.

818
00:48:08,570 --> 00:48:12,770
Bet blogiausiu atveju tai tipo n kvadrato. Kodėl?

819
00:48:12,770 --> 00:48:16,230
Jei mano žmonių sąrašas yra atvirkštine tvarka,

820
00:48:16,230 --> 00:48:21,260
Aš pirmą kartą pradėti su skaičiumi 8 ir įterpti jį arba ją į dešinę poziciją, kuri čia.

821
00:48:21,260 --> 00:48:25,270
I rūšies judėti į šoną. Šie vaikinai yra neišrūšiuoti, jis ar ji yra rūšiuojama.

822
00:48:25,270 --> 00:48:28,970
Bet dabar aš atsitikti, surasti, kas kitas? >> [Studentas] 7.

823
00:48:28,970 --> 00:48:31,250
7 blogiausiu atveju, nes tai atvirkštine tvarka.

824
00:48:31,250 --> 00:48:34,920
>> Taigi čia yra 7. Kur gi 7 priklauso? Tikrai už mane.

825
00:48:34,920 --> 00:48:39,460
Bet dabar 7 iš tikrųjų priklauso ne iš karto už manęs, bet už 8 skaičius,

826
00:48:39,460 --> 00:48:41,880
taip, aš turiu pasakyti: "Atsiprašau, numeris 8, galite perkelti šį kelią

827
00:48:41,880 --> 00:48:44,640
"Kambarys 7? Dabar aš susiduria su 6.

828
00:48:44,640 --> 00:48:48,530
"O, atsiprašau, skaičių 8 ir 7 numeris, galite perkelti, kad būtų vietos 6?"

829
00:48:48,530 --> 00:48:52,360
Taigi, kitaip tariant, su įterpimo rūšiuoti, nors aš ne daryti daug judėti,

830
00:48:52,360 --> 00:48:56,330
už manęs žmonės daro daug daugiau darbo, ir tai turi kainuoti kažkas laiką.

831
00:48:56,330 --> 00:48:58,000
Tai kainuos kompiuterio laiką.

832
00:48:58,000 --> 00:49:01,450
Įterpimo Rūšiuoti Taigi mes vis dar kenčia.

833
00:49:01,450 --> 00:49:06,260
Jei jums pradėti pridedant bendrą žingsnių skaičių, mes galų gale pradeda maždaug n kvadrato

834
00:49:06,260 --> 00:49:11,160
, nes šie vaikinai turi, kad paliktume vietos žmonių, kuriuos reikia įtraukti į tą sąrašą.

835
00:49:11,160 --> 00:49:15,960
Ir todėl šiuo atveju teta yra tik ne į ypatingą istoriją po ranka.

836
00:49:15,960 --> 00:49:21,100
Štai ir viskas nice and good. Mes turime šiuos 3 skirtingus būdus, kaip kalbėti apie veikimo laiką.

837
00:49:21,100 --> 00:49:26,370
Bet ką tai iš tikrųjų reiškia realiai, jei mes iš tikrųjų bando koduoti algoritmą?

838
00:49:26,370 --> 00:49:31,620
>> Leiskite man pasiūlyti, kad ten dar geriau algoritmas ten

839
00:49:31,620 --> 00:49:33,740
, kuri pati turi tam tikrą kompromisus.

840
00:49:33,740 --> 00:49:36,890
Mes ketiname jį vadiname sujungti rūšiuoti, ir tai tarsi šio stebuklingo algoritmo

841
00:49:36,890 --> 00:49:42,840
kad tik veikia greičiau kažkokiu būdu, ir tai taip lengva išreikšti, bent jau pseudocode.

842
00:49:42,840 --> 00:49:46,900
Merge sort šio algoritmo įgyvendinimą bus taip.

843
00:49:46,900 --> 00:49:50,860
Kai jums suteikta N elementų - N numerius, n žmonių, nesvarbu - pirmiausia normalumas patikrinimas.

844
00:49:50,860 --> 00:49:56,340
Jei n yra mažesnis negu 2, sujungti rūšiuoti tiesiog sustoja. Jis grįžta, taip sakant.

845
00:49:56,340 --> 00:50:00,830
Kodėl gi jūs sustabdyti, jei n yra mažiau nei 2? >> [Nesigirdi studentas atsakas]

846
00:50:00,830 --> 00:50:04,480
Į dešinę. Ir vėl, n nėra sąraše, n sąrašo dydis.

847
00:50:04,480 --> 00:50:07,660
Jei n yra mažesnis negu 2, tai reiškia, kad jūsų sąrašas arba 1,

848
00:50:07,660 --> 00:50:09,640
kur jūs akivaizdžiai rūšiuojamos, jei tai numeris 1,

849
00:50:09,640 --> 00:50:11,710
arba 0, tokiu atveju nieko rūšiuoti,

850
00:50:11,710 --> 00:50:13,570
todėl mes turime šį bazine rūšiuoti.

851
00:50:13,570 --> 00:50:20,350
Jei sąrašas yra toks trumpas, kad ten tiesiog nieko daryti, tiesiog nereikia daryti nieko. Grįžti.

852
00:50:20,350 --> 00:50:25,090
Kitaip rūšiuoti elementų yra kairėje pusėje, tada rūšiuoti elementų, dešinėje pusėje,

853
00:50:25,090 --> 00:50:27,410
tada sujungti 2 surūšiuotas puses.

854
00:50:27,410 --> 00:50:32,130
>> Šios rūšies atrodo šiek tiek apgauti, pagal kurį aš prašau jus, kaip rūšiuoti elementus

855
00:50:32,130 --> 00:50:34,900
ir jūs man sako, "Rūšiuoti kairėje pusėje, rūšiuoti dešinėje pusėje."

856
00:50:34,900 --> 00:50:37,240
Aš, pavyzdžiui, "Gerai. Kaip jūs rūšiuoti kairę pusę?"

857
00:50:37,240 --> 00:50:40,670
"Rūšiuoti kairėje pusėje, kairėje pusėje, rūšiuoti kairę pusę dešinėje pusėje, ir tada padaryti."

858
00:50:40,670 --> 00:50:44,060
Esate natūra pagal ciklą apibrėžti, ką tai reiškia, rūšiuoti,

859
00:50:44,060 --> 00:50:46,790
tačiau paaiškėja, kad šiuo atveju tikrai puikus.

860
00:50:46,790 --> 00:50:50,230
Tai nėra tikrai tai užburtas ratas, kuris niekada nesibaigia

861
00:50:50,230 --> 00:50:52,550
, nes jis baigiasi, kai? >> [Studentas] Kai pasieksite 1 dalykas.

862
00:50:52,550 --> 00:50:54,220
Kai jūs pasieksite 1 dalykas.

863
00:50:54,220 --> 00:50:57,850
Taigi, nors jūs galite pradėti su 8 žmonių, ir aš sakau, "Rūšiuoti kairę pusę šių žmonių,

864
00:50:57,850 --> 00:51:00,480
šie 4 žmonės ", tada aš sakau," Kaip jūs rūšiuoti kairę pusę? "

865
00:51:00,480 --> 00:51:03,450
"Na, rūšiuoti 2 žmonės čia". Ir tada jūs, pavyzdžiui, "Gerai, puiku."

866
00:51:03,450 --> 00:51:05,520
"Kaip jūs rūšiuoti kairę pusę tų žmonių?"

867
00:51:05,520 --> 00:51:09,040
"Tiesiog rūšiuoti Šis 1 asmuo čia." , Kas yra puikus apreiškimas dabar?

868
00:51:09,040 --> 00:51:13,050
Aš turiu rūšiuoti 1 asmeniui. Atlikta. Aš neturiu daryti bet kokį darbą.

869
00:51:13,050 --> 00:51:16,580
Bet dabar aš turiu sutvarkyti šį asmenį, bet jie vienas žmogus, nieko.

870
00:51:16,580 --> 00:51:21,490
>> Taigi magija, matyt, yra Šis trečiasis etapas: sujungti surūšiuoti puses.

871
00:51:21,490 --> 00:51:25,770
Taigi sujungti rūšiuoti šią puikią įžvalgą, kad, jei pertraukos didelė problema žemyn

872
00:51:25,770 --> 00:51:28,650
į 2 mažesnius, identiškai dydžio problemų

873
00:51:28,650 --> 00:51:32,710
ir tada tiesiog rūšies klijais mažesnių sprendimai kartu pabaigoje,

874
00:51:32,710 --> 00:51:34,720
Aš siūlau, kad mes galime padaryti daug, daug geriau [įsriegimo garso]

875
00:51:34,720 --> 00:51:38,050
nei bet kuri atrankos rūšiuoti ar įterpimo rūšiuoti.

876
00:51:38,050 --> 00:51:40,690
Aš iš tikrųjų buvo ignoruojant, kad pusvalandį, bet aš tikrai nežinau, kas vyksta

877
00:51:40,690 --> 00:51:45,040
ne šiandien. [Whirring garsas] [juokas]

878
00:51:45,040 --> 00:51:49,660
Taigi pažiūrėkime, jei mes galime pamatyti tai su nedidele pagalba iš mūsų draugui Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Merge sort proceso Yra 2 dideli žingsniai.

880
00:51:52,810 --> 00:51:56,400
Pirma, nuolat į dvi dalis padalinti puodelių sąrašą

881
00:51:56,400 --> 00:51:59,610
kol mes sąrašų krūva tik su 1 puodelis jais.

882
00:51:59,610 --> 00:52:02,150
Nesijaudinkite, jei sąraše yra nelyginis skaičius

883
00:52:02,150 --> 00:52:04,830
ir jūs negalite padaryti visiškai nupjauti tarp jų.

884
00:52:04,830 --> 00:52:08,740
Tiesiog savavališkai pasiimti, kurių sąrašas įtraukti papildomos puodelio in

885
00:52:08,740 --> 00:52:11,320
Todėl galime padalinti šiuos sąrašus.

886
00:52:12,420 --> 00:52:14,570
Dabar mes turime 2 sąrašus.

887
00:52:18,930 --> 00:52:20,930
Dabar mes turime 4 sąrašus.

888
00:52:25,730 --> 00:52:28,740
Dabar mes turime 8 sąrašus su vienu puodelio kiekvieno sąrašo.

889
00:52:28,740 --> 00:52:31,520
Taip, kad jį atlikdami 1 veiksmą.

890
00:52:31,520 --> 00:52:37,280
Atlikdami 2 veiksmą pakartotinai sujungti poros suliejimo algoritmas mes sužinojome prieš naudojant sąrašų.

891
00:52:37,280 --> 00:52:44,320
Sujungimas 108 ir 15 mes galų gale su sąraše 15, 108.

892
00:52:45,240 --> 00:52:51,330
Sujungimas 50 ir 4 mes galų gale su 4, 50.

893
00:52:51,330 --> 00:52:56,950
Sujungimas 8 ir 42 mes galų gale su 8, 42.

894
00:52:57,790 --> 00:53:04,360
Ir sujungti 23 ir 16 mes galų gale su 16, 23.

895
00:53:04,360 --> 00:53:08,030
Dabar visi mūsų sąrašai dydis 2.

896
00:53:08,030 --> 00:53:10,980
Atkreipkite dėmesį, kad kiekvienas iš 4 sąrašų yra rūšiuojamos,

897
00:53:10,980 --> 00:53:14,230
, kad galėtume pradėti vėl sujungti poros sąrašų.

898
00:53:14,230 --> 00:53:22,150
Sujungimas 15 ir 108 ir 4 ir 50 mes pirmiausia imasi 4, 15,

899
00:53:22,150 --> 00:53:26,250
tada 50, tada 108.

900
00:53:26,250 --> 00:53:33,020
Sujungimas 8, 42 ir 16, 23, mes pirmiausia reikia 8, tada 16,

901
00:53:33,020 --> 00:53:37,170
tada 23, tada 42.

902
00:53:37,170 --> 00:53:42,490
Taigi dabar mes turime tik 2 sąrašus dydis 4, iš kurių kiekviena yra rūšiuojama.

903
00:53:42,490 --> 00:53:45,940
Taigi dabar mes sujungti šias 2 sąrašus.

904
00:53:45,940 --> 00:53:54,230
Pirmiausia mes 4, tada mes 8, tada mes priimsime 15

905
00:53:54,230 --> 00:54:05,280
ir 16 ir 23 ir 42 ir 50 ir 108.

906
00:54:05,280 --> 00:54:09,020
Ir baigsime. Dabar mes turime surūšiuoti sąrašą.

907
00:54:09,020 --> 00:54:13,740
>> Robas buvo natūra pasinaudoti kažkas, kad mes dar to nepadarėte.

908
00:54:13,740 --> 00:54:16,540
Buvo pasiūlyta, bet mes ne iš tikrųjų tai padaryti.

909
00:54:16,540 --> 00:54:19,230
Jis daro kažką fiziškai puodeliai, tai sudaro prielaidas

910
00:54:19,230 --> 00:54:23,680
jis buvo išleisti šiek tiek išteklių be laiko. >> [Studentas] erdvė. >> Tai buvo erdvė.

911
00:54:23,680 --> 00:54:27,360
Tai, kad jis neturėjo šį dviejų lygių lentelę rūšiuoti, kur jis turėjo erdvę čia

912
00:54:27,360 --> 00:54:31,960
ir platybių čia iš tikrųjų buvo, o tai reiškia, kad jis naudoja dvigubai daugiau erdvės,

913
00:54:31,960 --> 00:54:36,390
bet mūsų algoritmų iki šiol - įterpimo rūšiuoti, burbulas rūšiuoti, ar atranka rūšiuoti

914
00:54:36,390 --> 00:54:40,780
bet jis buvo sverto šį papildomą erdvę rūšies perkelti daiktus į priekį ir atgal

915
00:54:40,780 --> 00:54:42,600
išlaikant dalykų, kad.

916
00:54:42,600 --> 00:54:47,540
Ir nors ji mano, kaip mes turime rūšiuotų sąrašą, kad jaučiau, jis paėmė šiek tiek laiko.

917
00:54:47,540 --> 00:54:51,060
Iš tikrųjų tai, ką Rob darė būtent šis algoritmas.

918
00:54:51,060 --> 00:54:56,780
Jis pirmą kartą paėmė n dydžio problemą, yra padalintas į kairę pusę, ir dešinėje pusėje.

919
00:54:56,780 --> 00:54:59,380
Tai, kai jis persikėlė puodeliai. Tada jis pakartojo šį procesą.

920
00:54:59,380 --> 00:55:03,390
Jis padalintas 4 į 2 komplektai 2 čia ir štai čia.

921
00:55:03,390 --> 00:55:08,520
Tada jis pakartojo šį procesą ir 2 padalintas į 2 komplektai 1 kiekvieno šių skirtingų puodelių.

922
00:55:08,520 --> 00:55:11,000
Ir tai, kai atsiranda puiki galimybė.

923
00:55:11,000 --> 00:55:15,840
Tuo pasakojimo taško, Rob turėjo 8 sąrašus 1 dydžio,

924
00:55:15,840 --> 00:55:18,860
visi, kurie buvo surūšiuoti jau.

925
00:55:18,860 --> 00:55:20,630
>> Taip, tada ką jis pradėti daryti?

926
00:55:20,630 --> 00:55:25,260
Porinis paėmė šį surūšiuoti sąrašą ir šį surūšiuoti sąrašą ir sujungti juos.

927
00:55:25,260 --> 00:55:28,200
Tada jis paėmė šį vieną ir sujungti juos, tada tai vienas ir sujungti juos,

928
00:55:28,200 --> 00:55:30,670
tai jo ir sujungti juos.

929
00:55:30,670 --> 00:55:32,390
Ir tada ką jis daryti toliau?

930
00:55:32,390 --> 00:55:36,580
Tada jis vėl susijungė didesnes sąrašus ir tada vėl sujungė didesnių sąrašus.

931
00:55:36,580 --> 00:55:41,170
Ir jei jūs manote apie tai tiesiog intuityviai dabar, ką jis iš tikrųjų daro?

932
00:55:41,170 --> 00:55:45,450
Jis pasidalijo problemą per pusę, per pusę, per pusę, per pusę

933
00:55:45,450 --> 00:55:47,600
siekiant gauti šiuos super mažų lapų.

934
00:55:47,600 --> 00:55:51,290
Tada jis buvo natūra derinant dviviečiai, dviviečiai, dviviečiai, dviviečiai.

935
00:55:51,290 --> 00:55:54,120
Taigi jis daro du kartus, kaip daug darbo, kaip mes matėme iki šiol

936
00:55:54,120 --> 00:55:56,930
nieko su Skaldyk ir valdyk, bet ne big deal.

937
00:55:56,930 --> 00:55:59,630
Dvigubai tiek, kiek darbas yra ne tokia baisi. Tai tik pastovus koeficientas.

938
00:55:59,630 --> 00:56:03,920
Ir panašiai kaip mūsų aritmetinio išraiškos prieš, aš tik ketina kirsti pastovius veiksnius

939
00:56:03,920 --> 00:56:10,170
kaip kartus 2. Who cares? , Jei tai 2 milijardai 2 kartus, kad vis dar daug žingsnių.

940
00:56:10,170 --> 00:56:13,160
Taigi tai sujungti žingsnis atrodo yra pagrindinė įžvalga.

941
00:56:13,160 --> 00:56:17,000
Leiskite eiti per tai tik skaitmeniniu būdu, prieš - O, tai nereiškia būti tęsiamas dar.

942
00:56:17,000 --> 00:56:22,890
Leiskite eiti per šį skaitmeniškai tik iš tikrųjų pamatyti, kaip ši atlieka dėmesį.

943
00:56:22,890 --> 00:56:25,940
Tai daugiausia tik šiek tiek vargšų animacija.

944
00:56:25,940 --> 00:56:27,750
Leiskite pasiūlyti šią.

945
00:56:27,750 --> 00:56:31,480
Veikimo laikas sujungti rūšiuoti - mes tiesiog reikia būdas kalbėti apie tai.

946
00:56:31,480 --> 00:56:34,380
Tai ne matematika, tai tiesiog rūšies trumpas būdu išreikšti save.

947
00:56:34,380 --> 00:56:39,080
Taigi T yra laiko ir n yra kas? >> [Studentas] dydis -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] problemos dydis, žmonių skaičius.

949
00:56:41,400 --> 00:56:45,470
Taigi, aš teigdamas, kad laikas rūšiuoti n žmonių bus 0 suma laiko

950
00:56:45,470 --> 00:56:50,290
Jei n yra mažesnis nei 2, nes jei turite 1 puodelis arba neturi puodeliai, jūs neturite ką rūšiuoti.

951
00:56:50,290 --> 00:56:55,160
Bet apskritai, aš norėčiau pasiūlyti, kad važiavimo laikas rūšiuoti n elementų

952
00:56:55,160 --> 00:56:59,350
bus laiko reikia rūšiuoti kairę pusę, plius Dešinė pusė

953
00:56:59,350 --> 00:57:03,110
plius - kas tai yra papildomas + n? >> [Studentas] suliejimas rūšiuoti.

954
00:57:03,110 --> 00:57:07,260
[Malan] Tai tikrai sujungti, nes jei n / 2 elementus čia

955
00:57:07,260 --> 00:57:11,500
ir turite n / 2 elementai čia, kiek laiko tai užtruks juos sujungti?

956
00:57:11,500 --> 00:57:15,050
Tiesiog kaip ir Rob, turite skinti šį vieną čia, gal skinti čia,

957
00:57:15,050 --> 00:57:17,120
skinti čia, skinti čia, skinti čia.

958
00:57:17,120 --> 00:57:19,400
Turite paliesti kiekvieną kaušelių kartą.

959
00:57:19,400 --> 00:57:22,030
Ir jei yra 4 puodeliai plius 4 puodeliai, 8 puodeliai

960
00:57:22,030 --> 00:57:25,200
arba apskritai, 8 n puodeliai.

961
00:57:25,200 --> 00:57:28,470
Taigi sujungus žingsnis galime išreikšti kaip n

962
00:57:28,470 --> 00:57:31,330
ir, kad pažodžiui reiškia, kiek kartų skaičių Rob fiziškai palietė

963
00:57:31,330 --> 00:57:33,410
vienas iš tų polistirolas puodeliai.

964
00:57:33,410 --> 00:57:35,850
Taigi tegul dabar daryti savavališkai pavyzdį.

965
00:57:35,850 --> 00:57:41,850
Jei yra 16 puodeliai, kas veikimo laikas rūšiavimo, Rob algoritmą, 16 puodelio?

966
00:57:41,850 --> 00:57:44,710
Tai 2 kartus laiko užtrunka rūšiuoti 8 puodelius

967
00:57:44,710 --> 00:57:46,920
nes mes turime 8 puodelius, 8 puodeliai čia.

968
00:57:46,920 --> 00:57:51,520
Aš nežinau, kaip ilgai, kad mano, todėl mes apibendrinant kaip T šiuo metu.

969
00:57:51,520 --> 00:57:53,320
Kas žino, kas tai yra?

970
00:57:53,320 --> 00:57:58,990
Bet dabar galiu rūšiuoti rekursyviai arba pakartotinai užduoti tą patį klausimą.

971
00:57:58,990 --> 00:58:01,920
Kiek laiko užtrunka rūšiuoti 8 puodelius?

972
00:58:01,920 --> 00:58:07,030
8 puodeliai, aš ruošiuosi pasakyti mano, kiek laiko užtrunka rūšiuoti 4 puodeliai plius 4 puodeliai,

973
00:58:07,030 --> 00:58:08,880
tada sujungti juos kartu.

974
00:58:08,880 --> 00:58:13,080
Bauda. Mes vis ciklo dalyje jau. Kiek tai užtruks rūšiuoti 4 puodelius?

975
00:58:13,080 --> 00:58:19,150
Laiko užtrunka rūšiuoti 4 puodelius 2 puodeliai plius 2 puodeliai rūšiavimo plius jungimosi procesą.

976
00:58:19,150 --> 00:58:21,440
Bauda. Kiek tai užtruks 2 puodeliai rūšiuoti?

977
00:58:21,440 --> 00:58:26,290
2 puodeliai yra laiko užtrunka rūšiuoti 1 puodelis plius laiko užtrunka rūšiuoti kitą puodelį

978
00:58:26,290 --> 00:58:29,040
plius kiek laiko reikia, kad sujungti, kuris yra vos už 2.

979
00:58:29,040 --> 00:58:33,340
>> Bauda. Paskutinis klausimas. Kiek tai užtruks rūšiuoti 1 puodelis?

980
00:58:33,340 --> 00:58:37,260
Čia yra pagrindas, kad mes prognozavo, mes norime paspausti anksčiau.

981
00:58:37,260 --> 00:58:42,250
Tas faktas, kad ji nežino kokia rūšiuoti mažiausia iš problemų

982
00:58:42,250 --> 00:58:44,120
reiškia, kad dabar, tarsi laipsnio mokyklos stiliumi,

983
00:58:44,120 --> 00:58:46,460
mes galime tiesiog eiti pradėti prijungti šiuos numerius atgal.

984
00:58:46,460 --> 00:58:50,630
Mes dabar žinome, kas T 1, kad galėčiau prijungti 0 T iš 1.

985
00:58:50,630 --> 00:58:54,420
Kad duos man atsakymą į T 2, kurį aš tada gali prijungti aukščiau.

986
00:58:54,420 --> 00:58:56,930
Kad duos man T iš 4, kurį galiu prijungti aukščiau.

987
00:58:56,930 --> 00:58:58,920
Kad duos man T 8, kurį galiu prijungti aukščiau.

988
00:58:58,920 --> 00:59:04,330
Ir jei aš iš tikrųjų, kad matematika įjungdami šių atsakymų,

989
00:59:04,330 --> 00:59:08,590
Tada aš gauti T 16 yra 64.

990
00:59:08,590 --> 00:59:12,090
Ir ką 64?

991
00:59:12,090 --> 00:59:15,700
Jei T yra 16, taip, tai 16 kartų 4.

992
00:59:15,700 --> 00:59:20,120
Taigi galiu reikalauti, kad dabar šis dalykas, vadinamas veikimo laikas sujungti rūšiuoti -

993
00:59:20,120 --> 00:59:22,590
ir tai bus, ką mes matėme iki šiol fanciest

994
00:59:22,590 --> 00:59:26,160
bus vadinama n log n

995
00:59:26,160 --> 00:59:31,140
nes kiek kartų gali Rob padalinti visa krūva puodelių per pusę? Log n.

996
00:59:31,140 --> 00:59:34,370
Tai tas pats, kaip telefonų knygos, pavyzdžiui, tai tas pats kaip savarankiškai skaičiavimo pavyzdys.

997
00:59:34,370 --> 00:59:36,380
>> Kiek kartų jūs galite kažką per pusę padalinti?

998
00:59:36,380 --> 00:59:38,410
Tačiau yra tai sujungti žingsnis.

999
00:59:38,410 --> 00:59:42,920
Jums gali tekti padalinti puodeliai į pusę, vėl ir vėl ir vėl,

1000
00:59:42,920 --> 00:59:45,640
bet kiekvieną kartą, jūs ketinate reikia sujungti.

1001
00:59:45,640 --> 00:59:48,270
Ir mes anksčiau sakė, kad sujungti n puodeliai trunka n veiksmus

1002
00:59:48,270 --> 00:59:52,060
nes jūs turite skinti puodelį, skinti taurę, ir turite paliesti kiekvieną puodelį kartą,

1003
00:59:52,060 --> 00:59:53,510
kaip ir Rob padarė.

1004
00:59:53,510 --> 00:59:59,430
Taigi, jei mes darome kažką log n kartų ir ką mes darome, n dalykus apie kiekvieną iš tų iteracijų,

1005
00:59:59,430 --> 01:00:03,090
kiekviena iš tų halvings turime n kartų log n.

1006
01:00:03,090 --> 01:00:07,220
Taigi, jei mes prijungti 16 šiame pavyzdyje 16 kartų prisijungti 16 -

1007
01:00:07,220 --> 01:00:10,600
nereikia nerimauti, kodėl taip yra ir dabar, nes aš ne atkreipė bazę

1008
01:00:10,600 --> 01:00:16,100
bet žurnalo 16 2 pagrindo yra 4, 16 kartų 4 yra 64.

1009
01:00:16,100 --> 01:00:22,350
Tačiau priešingai,, jei būtume naudojamas burbulas rūšiavimo arba atrankos rūšiavimo arba įterpimo Rūšiuoti su 16 numerių,

1010
01:00:22,350 --> 01:00:26,420
kas būtų buvę, jei veikimo laikas n 16?

1011
01:00:26,420 --> 01:00:33,310
Būtų 16 kvadrato, kuris yra 256, kuris, net jei jūs ne visai visą matematikos

1012
01:00:33,310 --> 01:00:38,390
256 yra didesnis nei 64. Kad tikrai stebuklinga išsinešimui čia.

1013
01:00:38,390 --> 01:00:41,990
Ir suprasti, kad per šį mažesnių pavyzdžių, kaip jums ant pset

1014
01:00:41,990 --> 01:00:44,260
tampa daug paprastesnis.

1015
01:00:44,260 --> 01:00:49,070
Bet, ką tai iš tikrųjų reiškia, kalbant apie šio algoritmo jaustis yra tokia:

1016
01:00:49,070 --> 01:00:54,520
Jei mes iš tikrųjų pažvelgti Merge sort čia - leiskite man traukti ją šiame lange -

1017
01:00:54,520 --> 01:00:58,560
tai yra šiek tiek kitoks pavyzdys, kuriuo mes turime 3 visų šių algoritmų -

1018
01:00:58,560 --> 01:01:01,440
burbulas, atranka, ir sujungti - tik vienas šalia kito.

1019
01:01:01,440 --> 01:01:03,740
>> Jie visi pradėjo su atsitiktinių barų, ir tai gerai.

1020
01:01:03,740 --> 01:01:06,240
Niekas neturi pagrindinio pranašumo prieš kitą.

1021
01:01:06,240 --> 01:01:09,500
Aš ruošiuosi po akimirkos spustelėkite kiekvieną iš šių animacija - Pradėti, Pradėti, Pradėti

1022
01:01:09,500 --> 01:01:13,270
taip greitai, kaip aš galiu, kad, grubiai, jie visi tuo pačiu metu pradžios,

1023
01:01:13,270 --> 01:01:17,450
ir tegul mano, kad burbulas Rūšiuoti Blogiau atvejis važiavimo laikas yra tai, ką? >> [Studentas] N kvadratu.

1024
01:01:17,450 --> 01:01:21,560
N kvadratu. Atrankos Rūšiuoti blogiausiu atveju važiavimo laikas? N kvadratu.

1025
01:01:21,560 --> 01:01:25,150
Ir sujungti rūšiuoti, matyt, - net jei ne visiškai laikytis visų matematikos dabar

1026
01:01:25,150 --> 01:01:30,610
tapsite daug paprastesnis laikui bėgant - tai mes tvirtiname, kad n kartų log n.

1027
01:01:30,610 --> 01:01:35,210
Ir todėl, kad log n yra griežtai mažiau nei n kai turime didelius numerius,

1028
01:01:35,210 --> 01:01:40,230
n kartų log n yra mažesnis nei n kartų (n) arba n kvadrato.

1029
01:01:40,230 --> 01:01:44,410
Taigi, kas ji jaučiasi, kad iš tikrųjų būtų geriau algoritmas veikimo laiką,

1030
01:01:44,410 --> 01:01:50,380
n kartų log n, o ne n kvadrato? Čia mes einame. Spustelėkite, spustelėkite, spustelėkite.

1031
01:01:55,690 --> 01:01:58,650
>> Štai, ką reiškia naudoti kažką panašaus Merge sort.

1032
01:01:58,650 --> 01:02:01,680
Mes turime labai mažai laiko. Leiskite pamatyti, kas vyksta čia.

1033
01:02:09,440 --> 01:02:12,440
[Chuckles], kurių pinigai yra burbulas rūšiuoti?

1034
01:02:14,960 --> 01:02:16,730
Tai labiau priklauso nuo įėjimo kartais.

1035
01:02:16,730 --> 01:02:18,120
Pažiūrėkime.

1036
01:02:18,120 --> 01:02:23,320
Come on. Jis jaučiasi, kaip jis vejasi. >> [Studentas], burbulas rūšiuoti!

1037
01:02:23,320 --> 01:02:27,370
[Studentai murmantys]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Taip, taip.

1039
01:02:29,120 --> 01:02:34,520
[Studentai murmantys] Eik, eik, eik!

1040
01:02:37,210 --> 01:02:40,450
[Visos Dopingowanie] [plojimais]

1041
01:02:40,450 --> 01:02:46,240
Taigi, dabar su 1 Paskutinis, galutinio demo, jei tai šiek tiek sudėtinga wrap savo mintis apie matematika

1042
01:02:46,240 --> 01:02:49,280
ar tarsi vizualizacija ten, jūs iš tikrųjų galite išgirsti greičius

1043
01:02:49,280 --> 01:02:51,000
skirtingų algoritmų skirtingai.

1044
01:02:51,000 --> 01:02:53,900
Tai animacija kažkas, kad faktiškai susieja skamba

1045
01:02:53,900 --> 01:02:56,980
keičiant proceso ir iš barų aukštį.

1046
01:02:56,980 --> 01:03:00,440
Kaip matysime, yra keli rūšiavimo algoritmai ten, kad žmonės galvojo apie.

1047
01:03:00,440 --> 01:03:03,660
Tai pirmasis bus įterpimas rūšiuoti, ir tai bus skristi per

1048
01:03:03,660 --> 01:03:07,090
ir duoti jums, kaip šie įvairius algoritmus darbui garsinį jausmą.

1049
01:03:07,090 --> 01:03:09,080
Čia yra įterpimo rūšiuoti.

1050
01:03:09,080 --> 01:03:18,410
[Elektroninis pypsėjimas]

1051
01:03:18,410 --> 01:03:20,730
[Malan] burbulas rūšiuoti.

1052
01:03:20,730 --> 01:03:46,850
[Greičiau elektroninis pypsėjimas]

1053
01:03:46,850 --> 01:03:48,950
[Malan] parinkimas rūšiuoti.

1054
01:03:48,950 --> 01:04:03,580
[Greičiau elektroninis pypsėjimas]

1055
01:04:03,580 --> 01:04:05,770
[Malan] suliejimas rūšiuoti.

1056
01:04:05,770 --> 01:04:17,270
[Elektroninis pypsėjimas]

1057
01:04:17,270 --> 01:04:20,180
[Pypsėjimas lėtina] [Juokas]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome rūšiuoti.

1059
01:04:22,590 --> 01:04:38,580
[Elektroninis pypsėjimas]

1060
01:04:39,740 --> 01:04:46,150
>> Tai CS50. Mes Pasimatysime kitą savaitę. [Plojimai ir visaip kitaip]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]