1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [3. týždeň, pokračovanie]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Harvard University]

3
00:00:04,110 --> 00:00:07,130
>> [To je CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Dobrá. Vitajte späť. To je CS50, a to je koniec týždňa 3.

5
00:00:11,010 --> 00:00:14,680
>> Takže pre tých, ktorí neznámom, v minulom roku začala Harvard, čo sa nazýva Innovation Lab,

6
00:00:14,680 --> 00:00:18,530
alebo i-lab, ktorý je nádherný objekt cez rieku na akademickej pôde HBS tieto

7
00:00:18,530 --> 00:00:22,640
, Ktorá je otvorená pre vysokoškolákov, GSA študentov, študentov z celého areálu,

8
00:00:22,640 --> 00:00:27,000
vrátane fakulty, a to je miesto, kde sa spojili, aby práce na inovatívne veci,

9
00:00:27,000 --> 00:00:29,180
najmä podnikateľské veci

10
00:00:29,180 --> 00:00:33,410
Ak a 0 alebo viac priateľov uvažujete o tom niečo podnikateľského

11
00:00:33,410 --> 00:00:37,080
buď v priebehu tejto triedy, po tejto triedy, alebo mimo.

12
00:00:37,080 --> 00:00:41,540
>> Takže jedna z vecí, ktoré robia cez obdobie J je tieto výlety,

13
00:00:41,540 --> 00:00:44,510
z ktorých jedna je New York, z ktorých jeden je Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
Priestor je veľmi obmedzená, ale je to príležitosť k ramenám s MBA

15
00:00:47,530 --> 00:00:52,200
a postgraduálne študenti z celého areálu a skutočne tráviť čas v týchto jednotlivých oblastiach

16
00:00:52,200 --> 00:00:55,500
chatovanie up rozjazd, chatovanie up podnikatelia a podobne.

17
00:00:55,500 --> 00:00:57,870
Takže v prípade záujmu, pozrite sa na túto adresu tu.

18
00:00:57,870 --> 00:01:01,220
Je tiež k dispozícii na snímkach on-line.

19
00:01:01,220 --> 00:01:04,610
>> Mohli by sme zmierniť domu audio len trochu?

20
00:01:04,610 --> 00:01:08,640
Ak by ste sa k nám pripojiť na obed tento piatok, 13:15 ohňa a ľadu, prosím zamierte tam.

21
00:01:08,640 --> 00:01:11,390
Ospravedlňujem sa, ak je formulár vyplnený už v čase, keď sa tam dostanem.

22
00:01:11,390 --> 00:01:13,750
Ale budeme pokračovať v tejto tradícii ďalej.

23
00:01:13,750 --> 00:01:17,350
>> Dnes budeme pokračovať vyššej úrovne diskusiu o rôznych problémoch, ktoré môžeme riešiť,

24
00:01:17,350 --> 00:01:21,330
zameraním oveľa menej, prinajmenšom dnes, na kóde a oveľa viac na nápady.

25
00:01:21,330 --> 00:01:24,720
Takže myslíte, že späť do týždňa 0, keď sme vytrhol telefónny zoznam v polovici,

26
00:01:24,720 --> 00:01:28,260
ktorého cieľom bolo urobiť niečo, síce trochu dramatické

27
00:01:28,260 --> 00:01:32,360
ale poslať myšlienku, že hľadanie nemusí byť nutne,

28
00:01:32,360 --> 00:01:35,100
ako je zrejmé na prvý pohľad, ako si možno myslíte.

29
00:01:35,100 --> 00:01:40,200
A riešenie problémov všeobecne nemusí vždy nutne byť najlepší -

30
00:01:40,200 --> 00:01:44,130
Najviditeľnejšie riešenie nemusí byť nutne najlepší.

31
00:01:44,130 --> 00:01:47,300
Takže sme mali telefónny zoznam, a úprimne povedané, my všetci v tejto miestnosti mal inštinkty,

32
00:01:47,300 --> 00:01:51,470
s najväčšou pravdepodobnosťou, kto v stredu pri hľadaní Mike Smith a potom ísť vľavo alebo vpravo

33
00:01:51,470 --> 00:01:54,280
zakladať na akékoľvek písmeno abecedy sme náhodou skončiť na.

34
00:01:54,280 --> 00:01:57,560
>> Ale to jednoduchá myšlienka, že my ľudia vzali za samozrejmé tak dlho

35
00:01:57,560 --> 00:02:00,670
Naozaj by sa mal začať do popredia svojej mysle

36
00:02:00,670 --> 00:02:03,900
pretože, ako problémy dostať oveľa zložitejšie, ako telefónny zoznam,

37
00:02:03,900 --> 00:02:07,420
tie isté jednoduché, brilantné postrehy sú, čo sa deje, aby nám

38
00:02:07,420 --> 00:02:10,259
riešiť oveľa zložitejšie a zaujímavejšie problémy,

39
00:02:10,259 --> 00:02:12,930
medzi nimi niektoré veci berieme ako samozrejmosť už v týchto dňoch.

40
00:02:12,930 --> 00:02:15,720
Miliardy webových stránok tam, a napriek tomu Google a Bing a podobne

41
00:02:15,720 --> 00:02:17,660
sú schopní nájsť veci pre nás takto.

42
00:02:17,660 --> 00:02:22,300
To sa nestane pomocou lineárnej hľadanie, prehľadávať všetky možné webových stránok.

43
00:02:22,300 --> 00:02:25,290
Facebook je schopný povedať, kto všetko z vašich priateľov sú alebo priatelia priateľov,

44
00:02:25,290 --> 00:02:28,250
a že tiež môže byť vykonané zdanlivo v okamihu v týchto dňoch

45
00:02:28,250 --> 00:02:30,820
aj keď majú milióny užívateľov.

46
00:02:30,820 --> 00:02:34,250
>> A tak, ako sme vlastne riešiť problémy na tej váhe sa nakoniec zníži

47
00:02:34,250 --> 00:02:37,830
k myšlienkam sme sa zamerali na v týždni 0 a trochu viac dnes.

48
00:02:37,830 --> 00:02:42,320
Nebudeme znova spustiť tento algoritmus, ale spomínam si tiež robil v týždni 0 tomto cvičení

49
00:02:42,320 --> 00:02:44,780
kde sme sa všetci postaviť, vziať na číslo 1,

50
00:02:44,780 --> 00:02:48,720
a potom sme mali všetci self-počítanie škárovaním off, pridaním čísla dohromady,

51
00:02:48,720 --> 00:02:51,930
potom polovica z gangu sa posadil na každej iterácii.

52
00:02:51,930 --> 00:02:56,750
Tak sme išli od 500 študentov 250 - 125 a tak ďalej.

53
00:02:56,750 --> 00:03:00,080
Ale ako sme povedali v pondelok, silná myšlienka, že

54
00:03:00,080 --> 00:03:02,460
bolo, že keď sa zdvojnásobil veľkosť tohto problému

55
00:03:02,460 --> 00:03:06,480
a všetky deti z dvora alebo EC 10 sa vrátil do izby a pripojil sa k nám,

56
00:03:06,480 --> 00:03:09,510
dobre, mohli by sme pravdepodobne počítať, že celý celkovú skupinu

57
00:03:09,510 --> 00:03:13,380
iba s 1 viac veľkom opakovaní slučky, pretože by len možno zdvojnásobiť veľkosť

58
00:03:13,380 --> 00:03:15,630
alebo v EC 10 je prípad trochu viac ako dvojnásobok veľkosti.

59
00:03:15,630 --> 00:03:18,440
A tak by sme museli stráviť trochu viac času,

60
00:03:18,440 --> 00:03:22,000
ale my by sme nemali míňať 400 alebo 700 ďalšie kroky.

61
00:03:22,000 --> 00:03:26,550
>> Len maľovať tento obrázok spôsobom, ktorý je trochu menej abstraktné, nech to nie je už všetci vstať.

62
00:03:26,550 --> 00:03:31,100
Ale ak ti z vás, ktorí sa rozhodli sedieť v orchestri dnes by mi nevadilo postojačky,

63
00:03:31,100 --> 00:03:34,580
uvidíme, či sa nám podarí zistiť z vás, ktorí najvyššej osoba

64
00:03:34,580 --> 00:03:36,730
tým, že robí rovnaký druh porovnávacej algoritmus.

65
00:03:36,730 --> 00:03:41,830
Takže ak sedíte v orchestri, ospravedlňujem sa, ale krok 1, vstať;

66
00:03:41,830 --> 00:03:44,650
krok 2, pár off s nikým blízkosti vás,

67
00:03:44,650 --> 00:03:49,360
zistiť, kto je vyššie, a sadnúť ak ste kratšie.

68
00:03:49,360 --> 00:03:51,360
Potom opakujte.

69
00:03:51,360 --> 00:03:56,280
[Študenti reptania]

70
00:04:13,450 --> 00:04:15,320
>> Dobre.

71
00:04:15,320 --> 00:04:19,010
Dobre. Jeden zostane stáť. Ako sa voláte? Andrew >>.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, si najvyšší osoba v sekcii orchestra dnes.

73
00:04:21,959 --> 00:04:28,100
>> Gratulujeme. [Potlesk a jasot] Dobre. Posaďte sa. Tak sme našli Andrew.

74
00:04:28,100 --> 00:04:30,870
Ako dlho by trvalo mi, napríklad, nájsť Andrew

75
00:04:30,870 --> 00:04:33,740
v tomto orchestri časti 50 + alebo tak ľudí?

76
00:04:33,740 --> 00:04:36,900
Mohol som zobrať pomerne jednoduchý prístup a začať tu.

77
00:04:36,900 --> 00:04:39,270
A ja som 2 ľudia vstať a ja som porovnať ich,

78
00:04:39,270 --> 00:04:42,120
a potom som povedal na toho, kto je o niečo kratšia, "Dobre, si sadnete,"

79
00:04:42,120 --> 00:04:44,380
a budem si pamätať, kto vyššia osoba.

80
00:04:44,380 --> 00:04:49,030
Potom som opakovať, opakovať, opakovať, a ja zavesiť na najvyššej osobe

81
00:04:49,030 --> 00:04:51,920
až nájdem niekoho, o niečo vyššie ako oni, na ktorom mieste

82
00:04:51,920 --> 00:04:54,950
mierne kratšie osoba musí sadnúť.

83
00:04:54,950 --> 00:04:57,690
Ale v tomto algoritmu v tejto časti orchestra, či je n vás,

84
00:04:57,690 --> 00:05:00,480
koľko krokov je to, že algoritmus bude trvať? >> [Študent] N.

85
00:05:00,480 --> 00:05:03,580
>> Bude to trvať n, P, pretože v najhoršom prípade, tak povediac,

86
00:05:03,580 --> 00:05:09,090
najvyššia osoba je úplne posledný človek, ktorého som si len náhodným smolu.

87
00:05:09,090 --> 00:05:14,260
Takže v najhoršom prípade, doba chodu tohto algoritmu je lineárna, je to n,

88
00:05:14,260 --> 00:05:18,070
kde n je celkový počet osôb v priestore, veľkosť problému.

89
00:05:18,070 --> 00:05:19,600
Čo o tomto algoritmu?

90
00:05:19,600 --> 00:05:22,080
Skutočnosť, že ste všetci vstali a potom zase polovica z vás posadil,

91
00:05:22,080 --> 00:05:23,950
polovica z vás sa posadil, polovica z vás posadil.

92
00:05:23,950 --> 00:05:26,070
Koľko krokov by malo, ku ktorým v prípade, že je n z vás?

93
00:05:26,070 --> 00:05:30,200
[Študent] N log n To >> by bolo ešte horšie. Prihlásiť n

94
00:05:30,200 --> 00:05:32,930
>> Takže log n, aj keď nie celkom si spomenúť, čo logaritmus je,

95
00:05:32,930 --> 00:05:38,410
teraz, len oceniť, že sa týka nejako to znížiť a znížiť na polovicu a

96
00:05:38,410 --> 00:05:41,000
Nemusí to byť faktor 2. Mohlo by to byť faktor 3.

97
00:05:41,000 --> 00:05:46,560
Ale to je to opakovanie rovnakého druhu faktora tak, že veľkosť problému začína tu

98
00:05:46,560 --> 00:05:49,620
ale potom okamžite prejde tu, potom tu, potom tu, potom tu.

99
00:05:49,620 --> 00:05:53,580
Nie ste pričom malé uhryznutie z problému, ste naozaj sekanie ďaleko na to

100
00:05:53,580 --> 00:05:56,160
s veľkou ranou zakaždým.

101
00:05:56,160 --> 00:06:00,810
Takže sme mali 50 ľudí, potom 25, potom 12 ½ alebo 13 ľudí stojí,

102
00:06:00,810 --> 00:06:05,370
potom 6 ½ a tak ďalej, až nakoniec len Andrew zostala stáť.

103
00:06:05,370 --> 00:06:08,710
Takže budeme hovoriť, že záznam o n, a môžete si to predstaviť takto.

104
00:06:08,710 --> 00:06:12,570
Pripomeňme tento obrázok tu, kde lineárny algoritmus je ako červenú čiaru tam,

105
00:06:12,570 --> 00:06:17,520
žltá linka bola počítanie 2s algoritmu, ktorý sme použili pre počítanie študentov

106
00:06:17,520 --> 00:06:22,300
v minulosti, ale dnes svätý grál bude aj naďalej táto zelená linka

107
00:06:22,300 --> 00:06:25,470
kde, ak sme zdvojnásobili počet ľudí v orchestri oddielu alebo práve povedal,

108
00:06:25,470 --> 00:06:29,170
sakra, poďme si všetci v celej miestnosti postaviť, nie je tak veľký problém

109
00:06:29,170 --> 00:06:31,560
pretože sme zhruba zdvojnásobí, koľko ľudí je tu dole,

110
00:06:31,560 --> 00:06:33,500
1 ďalšie iterácie, nie je problém.

111
00:06:33,500 --> 00:06:36,200
>> Zistili sme, že Andrew alebo ten, kto sa stane byť vyššia ako Andrew

112
00:06:36,200 --> 00:06:38,770
v medziposchodí alebo na balkón.

113
00:06:38,770 --> 00:06:42,140
Takže tento jednoduchý nápad, že sme sa za niečo tak samozrejmé v telefónnom zozname,

114
00:06:42,140 --> 00:06:46,170
si uvedomiť, že existuje toľko rôznych miest, na ktorých môžeme uplatniť.

115
00:06:46,170 --> 00:06:50,810
Len dať facku nejaký žargón - v skutočnosti skôr než žargón prvý,

116
00:06:50,810 --> 00:06:52,750
nechaj ma ísť na obrázku tu.

117
00:06:52,750 --> 00:06:56,970
Práve teraz sme hovorili o n a n / 2 a potom sa prihláste n,

118
00:06:56,970 --> 00:07:00,500
ale určite prísť, ako budeme v priebehu semestra,

119
00:07:00,500 --> 00:07:05,130
iný druh matematických vzorcov popísať túto všeobecnú predstavu jazdné doby.

120
00:07:05,130 --> 00:07:07,580
Jedná sa mimo kontext pre teraz, pretože uvidíme onedlho

121
00:07:07,580 --> 00:07:09,900
algoritmy, ktoré tieto skutočnosti predstavujú.

122
00:07:09,900 --> 00:07:17,990
>> Ale všimnite si tu lineárne vedenie n, priamka, je v skutočnosti veľmi nízka ukázal práve teraz.

123
00:07:17,990 --> 00:07:22,950
To je niečo ako optické ilúzie, že sme len zmeniť to, čo os x predstavuje

124
00:07:22,950 --> 00:07:26,130
a osi y, a môžeme priamku bod v ktoromkoľvek smere chceme.

125
00:07:26,130 --> 00:07:30,350
Ale dôvod, prečo je to tak zdanlivo byt teraz

126
00:07:30,350 --> 00:07:35,690
je, pretože sme potrebovali, aby sa priestor na tomto grafe oveľa pomalší časoch prevádzky.

127
00:07:35,690 --> 00:07:39,030
Pre túto chvíľu, viem, že tam sú niektoré docela zlé algoritmy v živote,

128
00:07:39,030 --> 00:07:43,790
z ktorých niektoré neberú n kroky, alebo ešte lepšie, log n kroky, ale viac.

129
00:07:43,790 --> 00:07:48,820
Tak nad líniu n tu dole oznámenia je tu n-krát log n,

130
00:07:48,820 --> 00:07:51,410
a uvidíme, čo to znamená onedlho.

131
00:07:51,410 --> 00:07:56,010
Nad tým je n na druhú, a my sme nevideli žiadne n štvorcov algoritmy, ale zatiaľ sa chystáme.

132
00:07:56,010 --> 00:07:57,660
A to vyzerá naozaj zle.

133
00:07:57,660 --> 00:08:01,610
Je tu 2 na n, niečo exponenciálny, ktoré sa cítia ešte horšie.

134
00:08:01,610 --> 00:08:05,760
A napriek tomu, zvedavo, potom je tu n kocky, ktoré, ak ste trochu myslieť dopredu,

135
00:08:05,760 --> 00:08:10,000
Ak typ si to spočítajte, 2 na n skutočne stane veľa rovnejšie,

136
00:08:10,000 --> 00:08:15,930
oveľa vyššie ako n kocky, keď sa pozriete na osiach dosť ďaleko von.

137
00:08:15,930 --> 00:08:19,890
Takže všimnete hneď tieto osi sú ľubovoľne 2-10 na osi x.

138
00:08:19,890 --> 00:08:21,770
>> A čo to znamená?

139
00:08:21,770 --> 00:08:23,890
To znamená, že 2 osoby do 10 ľudí v miestnosti.

140
00:08:23,890 --> 00:08:27,200
To je všetko znamená x: veľkosť problému, bez ohľadu na kontext.

141
00:08:27,200 --> 00:08:30,420
A vertikálna os práve teraz je počet sekúnd, alebo počet krokov -

142
00:08:30,420 --> 00:08:31,840
niektoré jednotku času.

143
00:08:31,840 --> 00:08:34,740
Ale si všimnúť, že je to 0-60 a 0-10.

144
00:08:34,740 --> 00:08:38,549
Ale ak sme trochu vzdialite, ako by ste si mohli v programe Excel alebo nejaké mapovať softvér,

145
00:08:38,549 --> 00:08:43,370
a my sme ísť až na 200.000, zistíte, že niečo ako 2 na n

146
00:08:43,370 --> 00:08:47,520
bude úplne premôcť prevádzkové časy n na druhú,

147
00:08:47,520 --> 00:08:50,960
n kocky, n log n - všetko, čo sme hovorili o tom tak ďaleko.

148
00:08:50,960 --> 00:08:54,190
A napriek tomu úlovok je, keď začnete hovoriť o veciach, ako je Facebook

149
00:08:54,190 --> 00:08:57,150
kde ste veľa, veľa, veľa ľudí všetko je prepojené,

150
00:08:57,150 --> 00:09:00,650
ste n ľudí, môže každý z nich má toľko ako priatelia n

151
00:09:00,650 --> 00:09:02,860
ak všetci je trochu buddy-buddy na svete,

152
00:09:02,860 --> 00:09:08,100
dobre, že to n krát n už tak, že je n štvorcov možné priateľstvo,

153
00:09:08,100 --> 00:09:10,950
aspoň v 1 smere, n mocnín možných priateľstvom.

154
00:09:10,950 --> 00:09:15,330
Takže už naznačuje, že hľadá Facebook je sociálna graf, aby som tak povedal,

155
00:09:15,330 --> 00:09:18,090
môže začať byť vyjadrená v týchto typoch vzorcov.

156
00:09:18,090 --> 00:09:19,820
>> Vrátime sa a robiť to oveľa konkrétnejšie,

157
00:09:19,820 --> 00:09:23,280
ale teraz, cieľ pre budúci mnoho týždňov

158
00:09:23,280 --> 00:09:27,170
bude nesmiete ísť o vykonávacích algoritmov alebo kód

159
00:09:27,170 --> 00:09:29,870
že skončí užívaním toľko času ako niečo ako toto.

160
00:09:29,870 --> 00:09:33,110
Ale fascinujúce vec, o informatike, ak budete pokračovať na v tejto oblasti

161
00:09:33,110 --> 00:09:38,320
pričom triedy ako CS121, CS124, z ktorých oba sú teórie kurzy,

162
00:09:38,320 --> 00:09:41,300
je to, že tam sú vlastne niektoré problémy, ktoré existujú v tomto svete

163
00:09:41,300 --> 00:09:45,710
ktoré zásadným spôsobom, ako ďaleko ako my vieme, nemôže byť vyriešený rýchlejšie

164
00:09:45,710 --> 00:09:48,880
ako najhoršie z týchto grafov skutočne naznačuje.

165
00:09:48,880 --> 00:09:53,660
Takže tam je veľa otvorených problémov v tomto svete, ako to urobiť oveľa lepšie, než ľudia majú tak ďaleko.

166
00:09:53,660 --> 00:09:56,130
>> Tak začnime potom s týmto príkladom.

167
00:09:56,130 --> 00:09:59,650
Videli sme Sean boj s touto kamerou, až príliš nemotorne na videu.

168
00:09:59,650 --> 00:10:05,270
Ale realita bola, keď bol Sean úlohu nájsť na palube takhle číslo 7,

169
00:10:05,270 --> 00:10:10,300
pripomenúť, že som povedal, že "tam je niekde za týmito kúskami papiera alebo biele dvere

170
00:10:10,300 --> 00:10:12,570
"Číslo 7. Sean, nájsť pre nás."

171
00:10:12,570 --> 00:10:14,200
A bolo to úžasne trápne sledovať

172
00:10:14,200 --> 00:10:15,790
pretože on bol naozaj snaží s týmto problémom.

173
00:10:15,790 --> 00:10:19,720
Ale realita bola Sean urobil rovnako ako niekto v miestnosti mohol urobiť.

174
00:10:19,720 --> 00:10:21,890
Vzal niečo dlhšie ako typického človeka môže mať,

175
00:10:21,890 --> 00:10:24,760
ale on predpokladal, že tam bol nejaký trik, aby sa tomuto problému,

176
00:10:24,760 --> 00:10:26,590
on predpokladal, že niečo chýba.

177
00:10:26,590 --> 00:10:29,320
A to nepomáhalo, že stovky očí sa rúti na neho.

178
00:10:29,320 --> 00:10:34,250
>> Ale realita bola, ak vstup do problému, je banda náhodných čísel

179
00:10:34,250 --> 00:10:37,120
a vy ste bol žiadal, aby našiel 1 také číslo,

180
00:10:37,120 --> 00:10:39,770
najlepšie, čo môžete urobiť, je lineárna hľadanie.

181
00:10:39,770 --> 00:10:44,060
Začnite na ľavej strane, presuňte vpravo, alebo začať vpravo, presuňte doľava.

182
00:10:44,060 --> 00:10:48,300
Spätne, môžeme myslieť, "Sean, prečo si jednoducho začať z druhého konca?"

183
00:10:48,300 --> 00:10:52,120
No, mohla 7 sa rovnako ľahko tu náhodne,

184
00:10:52,120 --> 00:10:54,980
ale zámerne som to tam dal, lebo som usúdil, že to nebude začať na konci.

185
00:10:54,980 --> 00:10:59,320
Tak som trochu manipulovať situáciu, ale náhody 7 by mohol byť kdekoľvek.

186
00:10:59,320 --> 00:11:02,380
Takže od pravého konca by mohol byť lepší ako,

187
00:11:02,380 --> 00:11:04,320
ale čo keď budúci rok som sa presunúť 7 inde?

188
00:11:04,320 --> 00:11:06,830
To nie je úplne nové riešenie problému -

189
00:11:06,830 --> 00:11:10,520
od 1 konci, alebo iné - keď ste rovnako žiadne iné predpoklady.

190
00:11:10,520 --> 00:11:13,620
Takže Sean začal hľadať prostredníctvom čísla a on povedal: "5. To tu nie je."

191
00:11:13,620 --> 00:11:17,280
Potom išiel sem a videl 19, potom sa zastavil asi na 20 sekúnd,

192
00:11:17,280 --> 00:11:22,330
potom otvoril to pre 13, a potom sa ukázalo,

193
00:11:22,330 --> 00:11:24,270
že sa nezdá byť vzorec.

194
00:11:24,270 --> 00:11:28,090
Nebolo 1, 2, 3, 4 alebo podobne. Tam boli medzery v číslach, ktoré nepomohlo.

195
00:11:28,090 --> 00:11:32,320
A tiež skutočnosť, že som použil tieto lacné kúsky papiera, aby zakryli čísla

196
00:11:32,320 --> 00:11:35,270
je vlastne úmyselné, pretože keď som odstránil všetky tieto kúsky papiera,

197
00:11:35,270 --> 00:11:38,760
väčšina z nás, Sean vrátane, pravdepodobne by sa pozrel trochu makroskopicky

198
00:11:38,760 --> 00:11:43,410
na tabuľu a povedal: "Ach, 7 je samozrejme tu." Urobili sme to okamžite.

199
00:11:43,410 --> 00:11:46,460
>> A to môže byť spôsob, ako ľudský mozog funguje do istej miery,

200
00:11:46,460 --> 00:11:50,730
ale v skutočnosti, jeho oči alebo myseľ bola pravdepodobne skimming čísla sprava doľava,

201
00:11:50,730 --> 00:11:55,190
zľava doprava, stredné na von - niečo sa deje fyziologicky

202
00:11:55,190 --> 00:11:57,640
také, že pocit, že sa deje okamžite,

203
00:11:57,640 --> 00:12:01,360
ale štatistiky sú ešte vnútorne tam bol nejaký druh metodiky k nájdeniu 7.

204
00:12:01,360 --> 00:12:05,160
A skutočne, teraz hovoríme o poliach a dátových štruktúr

205
00:12:05,160 --> 00:12:08,780
a pamäť vo vnútri počítača, môže jediná vec, my ľudia robia

206
00:12:08,780 --> 00:12:13,070
, Je pozrieť sa na jednotlivé pamäťových miest 1 naraz.

207
00:12:13,070 --> 00:12:16,600
>> Takže každý iné umiestnenie by bolo dobré byť poistený s nejakým kusom papiera

208
00:12:16,600 --> 00:12:21,170
pretože nemôžeme vidieť rovnako. Môžeme robiť len 1 vec naraz.

209
00:12:21,170 --> 00:12:25,030
Takže v tomto prípade, v prípade Seana, išli sme tu a potom sme išli sem

210
00:12:25,030 --> 00:12:31,040
a potom sme išli sem, tu, tu, tu, dostal šikovný do konca

211
00:12:31,040 --> 00:12:34,450
a tak nejako preskočil túto svojvoľne a našiel 7 tam.

212
00:12:34,450 --> 00:12:37,470
Tahle nebola nijako zvlášť výnimočná. To taky bola mimo prevádzky.

213
00:12:37,470 --> 00:12:39,530
Ale nakoniec našiel 7.

214
00:12:39,530 --> 00:12:45,360
Ale teraz takeaway je naozaj to najlepšie, čo môžete urobiť, keď rovnako žiadne informácie

215
00:12:45,360 --> 00:12:50,400
iné ako náhodne zoradená čísel je začať zľava alebo začať sprava.

216
00:12:50,400 --> 00:12:54,950
Alebo sakra, môžete náhodne otvoriť dvere, ale aj potom to, čo to znamená byť náhodné?

217
00:12:54,950 --> 00:12:57,220
No, museli by sme nejako formalizovať, čo to znamená začať tu,

218
00:12:57,220 --> 00:13:01,150
potom kliknite tu, potom kliknite tu. Sean si skvele, a to bolo len zábavné sledovať.

219
00:13:01,150 --> 00:13:06,340
Čo keď namiesto toho budeme meniť je problém trochu a vychovávať tohtoročné Seana, ak chcete?

220
00:13:06,340 --> 00:13:09,460
By niekto byť pohodlné prísť na pódium a riešenie trochu iný problém

221
00:13:09,460 --> 00:13:12,330
a objaviť sa pred kamerou?

222
00:13:12,330 --> 00:13:15,720
>> Poďme za orchestra vy boli docela zapojení už dnes.

223
00:13:15,720 --> 00:13:21,430
Ako asi v ružovej, v klobúku? Poď dole. Aké je vaše meno? >> Alex. >> Alex. Dobre.

224
00:13:21,430 --> 00:13:24,580
Takže Alex bude tohtoročná Sean a objaví sa v najbližších niekoľkých rokoch

225
00:13:24,580 --> 00:13:27,770
hodnote CS50 prednášok.

226
00:13:27,770 --> 00:13:30,340
Alex, rád vás spoznávam. >> Teší ma taky.

227
00:13:30,340 --> 00:13:33,470
Výzva na ruky pre vás je, že ste to trochu jednoduchšie

228
00:13:33,470 --> 00:13:38,950
v tom, že som ti hovorím rovnaké čísla sú tu, ale oni sú teraz zoradené.

229
00:13:38,950 --> 00:13:41,800
Takže teraz vaším cieľom je nájsť číslo 7.

230
00:13:41,800 --> 00:13:45,370
A skutočne, mali by sme naozaj, aby to - Si druh podvádzanie, ako počítač, že nie,

231
00:13:45,370 --> 00:13:47,990
pri pohľade na to, čo tieto čísla bola pred chvíľou.

232
00:13:47,990 --> 00:13:50,360
S kriedou to vlastne je nepomôže tak moc,

233
00:13:50,360 --> 00:13:52,810
ale poďme predstierať, že neviete, čo je pôvodný poľa je.

234
00:13:52,810 --> 00:13:56,600
Všetko, čo viem teraz, je, že máte celý rad zoradená čísel

235
00:13:56,600 --> 00:14:00,360
ktoré by mohli mať medzery medzi nimi, a vaším cieľom je nájsť číslo 7.

236
00:14:00,360 --> 00:14:05,080
Ako by ste, rozumný človek, ísť o zistenie, že počet 7?

237
00:14:05,080 --> 00:14:07,770
>> Prejsť od najnižšej k najvyššej? Dobre >>. Prejsť nízkej na vysokú.

238
00:14:07,770 --> 00:14:10,990
A to netrhá je preč. Poďme zdvihnúť tak môžeme znovu použiť.

239
00:14:10,990 --> 00:14:14,730
Dobre, tak 1. Počkajte. Pred ďalej, to bolo 1, zjavne nesprávne.

240
00:14:14,730 --> 00:14:17,270
Tak čo sa deje skrze svoju myseľ ďalej? Aký je váš ďalší krok?

241
00:14:17,270 --> 00:14:23,250
Ten budúci. Dobre >>. Ten budúci. Dobré. 3, takže nesprávne. Aký je váš ďalší krok?

242
00:14:23,250 --> 00:14:27,670
Pokračovať ďalej. >> Dobre. Pokračovať ďalej. 5.

243
00:14:27,670 --> 00:14:31,110
Takže pokračuj v ceste, a dovoľte mi, aby som vám to odovzdať potomkom.

244
00:14:31,110 --> 00:14:35,720
7. Vynikajúci >>. Veľmi dobrá. Nájdených číslo 7. [Potlesk]

245
00:14:35,720 --> 00:14:39,720
Takže to bolo dobré, ale Sean tiež našiel číslo 7.

246
00:14:39,720 --> 00:14:44,490
A tvrdím, že ste naozaj zneužil túto dodatočnú informáciu,

247
00:14:44,490 --> 00:14:47,780
čo je skutočnosť, že tieto čísla sú zoradené.

248
00:14:47,780 --> 00:14:51,520
Takže môžeme urobiť lepšie? Nejaké návrhy tu? Jo, vzadu.

249
00:14:51,520 --> 00:14:54,710
[Študent] Binárne vyhľadávanie. >> Nemám potuchy, čo binárne hľadanie je.

250
00:14:54,710 --> 00:14:58,030
>> [Študent] Dátum v stredu. Začnite >> v stredu. Dobre. Tak uvidíme, či sa tam môžeme dostať.

251
00:14:58,030 --> 00:15:02,580
Takže ak namiesto toho ste povedal, štart z polovice, choďte do toho a otvoriť prostredné dvere.

252
00:15:02,580 --> 00:15:04,580
Tam je 8 z nich, takže budete mať ľubovoľne vybrať ten

253
00:15:04,580 --> 00:15:09,800
mierne vľavo alebo vpravo. Dobre. 7! [Potlesk] Very nice.

254
00:15:09,800 --> 00:15:11,410
Dobre, ale kde sme ísť s tým?

255
00:15:11,410 --> 00:15:14,990
Predpokladajme, že len preto, aby pretrhnúť ste začali tu

256
00:15:14,990 --> 00:15:16,670
preto, že rovnako by sa stalo tiež.

257
00:15:16,670 --> 00:15:19,540
Práve sme sa náhodou vedieť, že 7 je tam. Tak toto je 13.

258
00:15:19,540 --> 00:15:21,980
Takže ak sú zoradené a začali sme v strede,

259
00:15:21,980 --> 00:15:24,600
čo by optimálne ďalší krok boli?

260
00:15:24,600 --> 00:15:27,740
Prejsť na ľavej. A tak tu je telefónneho zoznamu príklad znovu.

261
00:15:27,740 --> 00:15:30,130
Ak 13 je tu a my vieme, že zoznam je zoradený,

262
00:15:30,130 --> 00:15:33,900
potom všetky tieto kúsky papiera sa nezaujíma nás teraz

263
00:15:33,900 --> 00:15:37,400
pretože už vieme, že 7 musí byť vľavo

264
00:15:37,400 --> 00:15:39,510
ak sú tieto čísla sú zoradené a našli sme 13.

265
00:15:39,510 --> 00:15:42,500
>> Takže aký je tvoj ďalší ťah tu? >> Choďte vľavo. >> Dobre, dobre.

266
00:15:42,500 --> 00:15:45,080
Takže choďte doľava, a - počkajte, hej, hej, hej. To je podvod.

267
00:15:47,140 --> 00:15:51,350
Takže ste našli 7, ale to, čo bolo algoritmus sme práve žiada?

268
00:15:51,350 --> 00:15:56,450
Začnite v stredu. Dobrý >>. Takže to, čo je logickým pokračovaním toho istého nápadu?

269
00:15:56,450 --> 00:15:58,970
Oh, len toto. Presne >>. >> Tak som začať tu. Dobrý >>.

270
00:15:58,970 --> 00:16:02,020
Takže teraz sme išli mierne naľavo znova. Je to 3.

271
00:16:02,020 --> 00:16:05,310
Ale zaujímavé takeaway teraz je, ktorý z nich to nemusíte starať o?

272
00:16:05,310 --> 00:16:08,040
Tieto 2. Tieto 2 >>. Takže teraz to môžeme ísť preč, môže človek ísť preč.

273
00:16:08,040 --> 00:16:12,330
Teraz je problém, že je 8 potom bol veľkosť 4 je teraz veľkosť 2.

274
00:16:12,330 --> 00:16:16,430
Dostávame sa veľmi blízko. Opäť, choďte do stredu týchto 2 prvkov.

275
00:16:16,430 --> 00:16:20,430
>> Dobre. Takže je to trochu škoda, že teraz sme vždy odišiel, pretože sme zaokrúhľovanie smerom nadol.

276
00:16:20,430 --> 00:16:25,150
Ale to je v poriadku, pretože teraz budeme hádzať to preč a všetko ostatné, takže nás len 7.

277
00:16:25,150 --> 00:16:30,490
Dajme potlesk. Našli sme 7 znova. [Potlesk] Dobre. Iste.

278
00:16:30,490 --> 00:16:32,220
Vydrž len 1 sekundu.

279
00:16:32,220 --> 00:16:36,630
Aj napriek tomu, že ďalší proces druh trvalo trochu dlhšie, než sme cítili, že by,

280
00:16:36,630 --> 00:16:40,150
úprimne povedané, vaše prvé inštinkty boli najlepšie, nie? Našli sme 7 okamžite.

281
00:16:40,150 --> 00:16:46,740
Ale my by sme našli 7 rýchlejšie, bez ohľadu na to, čo je v tomto prípade oproti tento jeden

282
00:16:46,740 --> 00:16:50,100
pretože ak sú čísla zoradené všetky, rovnako ako stránky v telefónnom zozname,

283
00:16:50,100 --> 00:16:54,580
môžete naozaj kosiť polovicu problému znovu a znovu a znovu.

284
00:16:54,580 --> 00:16:56,740
A to nie je zďaleka tak jednoduché, aby tento sa len 8 čísiel

285
00:16:56,740 --> 00:17:00,100
na rozdiel od 1000-stránkové telefónny zoznam, kde naozaj vidíte to vizuálne,

286
00:17:00,100 --> 00:17:03,120
ale v tomto prípade, kedy tu Sean hľadal 7,

287
00:17:03,120 --> 00:17:06,020
koľko krokov v najhoršom prípade by to vzali ho? >> [Študent] 7.

288
00:17:06,020 --> 00:17:11,670
7 v najhoršom prípade. No, v najhoršom prípade nie je 7 v prípade, že je to 8 dvere tu.

289
00:17:11,670 --> 00:17:13,440
To by trvalo mu 8 krokov.

290
00:17:13,440 --> 00:17:18,170
>> Takže ak je n dvere, to by mohlo vziať Seana pred pár rokmi n krokov.

291
00:17:18,170 --> 00:17:21,520
Teraz, vo vašom prípade, Alex, pretože tieto čísla sú zoradené -

292
00:17:21,520 --> 00:17:25,130
a môžeme trochu vyvodzujú tohto odkiaľ sme boli tak ďaleko v tomto príbehu -

293
00:17:25,130 --> 00:17:28,300
Čo je doba chodu viac inteligentný algoritmus Alešova

294
00:17:28,300 --> 00:17:30,770
z od stredu a potom zopakovaním?

295
00:17:30,770 --> 00:17:36,490
[Študent] 3. >> Tak to bude 3, hrubo, keď idete 8-4 na 2 až 1.

296
00:17:36,490 --> 00:17:40,660
Takže 3 krokoch, alebo všeobecnejšie, že je log n znovu.

297
00:17:40,660 --> 00:17:43,380
Kedykoľvek ste na polovicu a znížiť na polovicu a a znížiť,

298
00:17:43,380 --> 00:17:45,290
že je vyjadrením tejto myšlienky log n

299
00:17:45,290 --> 00:17:48,140
A tak to by zabralo vám iba 3 kroky, a naozaj to urobil

300
00:17:48,140 --> 00:17:50,890
akonáhle sme otvorili dvere polovicu a znížiť,

301
00:17:50,890 --> 00:17:53,770
vzhľadom k tomu, by to vzali Sean asi 7 alebo 8 krokov.

302
00:17:53,770 --> 00:17:56,330
Takže ďakujem za to, že s nami v tomto roku. >> Ďakujem. Tešilo ma.

303
00:17:56,330 --> 00:18:00,170
Ďakujem Alex. Podobne >>. [Potlesk]

304
00:18:00,170 --> 00:18:02,150
>> Čo je potom skutočný dôsledok toho?

305
00:18:02,150 --> 00:18:06,050
A teraz si predstavte, že to nie je 8 dvere, ktoré, úprimne povedané, to všetko by mohlo z nás nájsť niečo

306
00:18:06,050 --> 00:18:10,430
za 8 dvere docela rýchlo len tým, trhať kusy papiera a ísť s našimi inštinkty.

307
00:18:10,430 --> 00:18:14,430
Ale čo keď je to jeden milión dvere? Čo keď je to 4000000000 dvere?

308
00:18:14,430 --> 00:18:19,630
V prípade 4000000000 dverí, ste naozaj bude chcieť ísť s algoritmom Alešova,

309
00:18:19,630 --> 00:18:23,150
binárne vyhľadávanie podľa začneme volať, alebo rozdeľ a panuj, všeobecnejšie,

310
00:18:23,150 --> 00:18:25,220
kde budete mať polovicu a znížiť problém,

311
00:18:25,220 --> 00:18:30,510
pretože ak máte 4000000000 dvere, môžete koľkokrát ste nakrájame 4000000000 v polovici?

312
00:18:30,510 --> 00:18:33,870
[Študent] 32. >> Je to vlastne 32. Môžete pracovať sa na to na kus papiera alebo vo vašej hlave.

313
00:18:33,870 --> 00:18:38,490
Idete 4 miliardy až 2 miliardy to 1 miliarda pol miliardy, na 250000000, bodka, bodka, bodka.

314
00:18:38,490 --> 00:18:41,620
A ak si z spočítajte, budete skutočne dostať 32,

315
00:18:41,620 --> 00:18:44,950
a že sa v skutočnosti týka informatiky, pretože sme väčšinou počítajú v právomoci 2.

316
00:18:44,950 --> 00:18:47,600
2 k 32 sa stane, že 4 miliardy.

317
00:18:47,600 --> 00:18:51,440
Takže tam je veľa význam pre tieto druhy právomocí 2 v informatike.

318
00:18:51,440 --> 00:18:55,120
>> Ale čo asi 8 miliárd? Koľko krokov je to, že bude trvať, pokiaľ existujú 8000000000 dvere?

319
00:18:55,120 --> 00:19:00,350
[Študent] 33. Tak >> 33. Čo keď tam 16000000000 dvere? Koľko krokov je to, že bude trvať?

320
00:19:00,350 --> 00:19:05,020
[Študent] 34. >> 34. Mohli by sme trochu pokračovať do omrzenia. Ale to je mocná vec.

321
00:19:05,020 --> 00:19:09,430
Môžete zaviesť miliardy viac vstupov na váš problém, ale žiadny veľký problém,

322
00:19:09,430 --> 00:19:14,140
stačí vziať 1 ďalšie sústo z nej, a tak nám dáva niečo ako binárne vyhľadávanie

323
00:19:14,140 --> 00:19:15,920
alebo rozdeľ a panuj, všeobecnejšie.

324
00:19:15,920 --> 00:19:17,990
Ale ja som trochu podvádzal, že jo?

325
00:19:17,990 --> 00:19:22,410
V prípade algoritmu Alex, mala výhodu oproti Seanovi.

326
00:19:22,410 --> 00:19:27,780
Vedela, že tieto čísla boli zoradené, ale Alex nemusel radiť im sama.

327
00:19:27,780 --> 00:19:30,520
Aj v predstihu prišiel k tabuli a druhu sa uistiť,

328
00:19:30,520 --> 00:19:33,670
že som kreslil je všetko v zoradené poradí, potom som doľahla je papierom.

329
00:19:33,670 --> 00:19:35,850
Ale koľko práce to trvalo ma?

330
00:19:35,850 --> 00:19:40,110
Keby sme vyrazili s týmito číslami v niektorých zdanlivo náhodnom poradí -

331
00:19:40,110 --> 00:19:43,320
V tomto prípade táto jednoduchšie čísla, 1 až 8 tu -

332
00:19:43,320 --> 00:19:46,090
ako sme sa ísť o triedení týchto hodnôt?

333
00:19:46,090 --> 00:19:52,530
Ak ste boli človek, rovnako túto úlohu, čo by druh intuitívny prístup budete mať

334
00:19:52,530 --> 00:19:54,800
na triedenie veľa čísel?

335
00:19:54,800 --> 00:19:57,050
Tieto veci boli vyložené ako dieliky puzzle. Jo.

336
00:19:57,050 --> 00:19:59,950
>> [Študent] Ja by som sa jednotlivé čísla a porovnať ho každému

337
00:19:59,950 --> 00:20:03,180
a ďalej doľava. >> Dobre, dobre.

338
00:20:03,180 --> 00:20:05,720
Tak sa každé číslo, prirovnávať to k tej vedľa nej,

339
00:20:05,720 --> 00:20:09,610
a potom už len ďalej pozdĺž zoznamu, typu rejiggering veci tak, ako to je.

340
00:20:09,610 --> 00:20:13,800
Takže tu máme šancu na možno niekoľko viac ľudí zapojiť sa.

341
00:20:13,800 --> 00:20:16,290
Máme 8 ďalšie dobrovoľníkov, ktorí by radi, aby prišli?

342
00:20:16,290 --> 00:20:23,950
Trochu menší tlak, pretože ty nie si jediná. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Poď dole. Vy sa chystáte byť čísla 1 až 8.

344
00:20:28,190 --> 00:20:36,050
Poďme sa pozrieť, či nemôžeme urobiť triedenie pre Alexa veľa rovnakým spôsobom som to urobil v predstihu.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Nehanbite sa a keby ste, line up na javisku medzi hudobným stánku a ja tu

347
00:20:40,760 --> 00:20:44,960
v rovnakom poradí ako na snímke na obrazovke.

348
00:20:47,910 --> 00:20:49,680
Uh-oh.

349
00:20:50,370 --> 00:20:53,230
Budeme s vami pracovať na ďalšom príklade. Oh, počkať, počkať. Ideme na to. Počkajte.

350
00:20:53,230 --> 00:20:57,570
Ďalší príklad je teraz. Tu to máš. Číslo 8. Poď hore.

351
00:20:57,570 --> 00:21:00,270
Dobrá. Triediť sami podľa toho.

352
00:21:00,270 --> 00:21:03,620
Posunutím len malý kúsok na stranu hudby stojí tu.

353
00:21:03,620 --> 00:21:12,310
Takže máme 4, 2, 6 - sa tam dostať, tu, tu - 3.

354
00:21:12,310 --> 00:21:17,570
Jo. Dobre. Môžete ísť sem. Nie, zostaň tam.

355
00:21:17,570 --> 00:21:21,840
Jo, tu. Nie, som v poriadku. Presne tam. Dobre, veľmi dobre. Dobre.

356
00:21:21,840 --> 00:21:24,930
Tak teraz poďme triediť ich do vzostupnom poradí.

357
00:21:24,930 --> 00:21:26,210
>> Ako môžem ísť asi robí?

358
00:21:26,210 --> 00:21:28,630
Algoritmus, ktorý bol navrhnutý pred chvíľou bol dôvod, prečo sa jednoducho tieto

359
00:21:28,630 --> 00:21:31,970
že ľudia, ktorí sú trochu vedľa seba a potom opraviť prípadné chyby,

360
00:21:31,970 --> 00:21:33,540
pohybujúce sa zľava doprava.

361
00:21:33,540 --> 00:21:36,580
Takže tu máme 4 a 2, zrejme mimo prevádzky. Poďme vymeniť vás. Dobre.

362
00:21:36,580 --> 00:21:40,760
Takže teraz budem pohybovať dole riadok. 4 a 6, uzlíkom. [Smiech]

363
00:21:40,760 --> 00:21:45,010
6 a 8, celkom dobre. 8 a 1, dovoľte mi, aby som vám vymenia chlapci. Dobrá.

364
00:21:45,010 --> 00:21:48,030
Takže 8 a 3, vymeniť chlapi.

365
00:21:48,030 --> 00:21:52,280
8 a 7, dovoľte mi, aby som vám vymenia chlapci. 5 a 8, výborná.

366
00:21:52,280 --> 00:21:54,820
Dám vám zoradený zoznam.

367
00:21:54,820 --> 00:21:56,860
Dobrá. Takže nie tak celkom.

368
00:21:56,860 --> 00:22:01,180
Ale je to lepšie, pretože väčší počet - prípadové v bode 8 -

369
00:22:01,180 --> 00:22:04,030
sa druh bublala hore zľava cez doprava.

370
00:22:04,030 --> 00:22:08,010
Tak som dostal 1 z nich pravdu, ale je to pocit, ako že to nie je úplne vyriešiť problém.

371
00:22:08,010 --> 00:22:11,150
>> Takže to, čo by ste navrhol budeme robiť ďalej? >> [Študent] Majte robí. >> Držíme to robí.

372
00:22:11,150 --> 00:22:13,740
A uvedomiť si, opäť, sme sa vydali veci tým, že len majú všetkých ľudí

373
00:22:13,740 --> 00:22:17,180
druh inteligentne dohovoriť sa na základe tohto obrázku,

374
00:22:17,180 --> 00:22:19,040
ale teraz musíme byť oveľa metodicky.

375
00:22:19,040 --> 00:22:21,510
Musíme byť algoritmické o tom, ako by sme písať kód -

376
00:22:21,510 --> 00:22:23,520
v tomto prípade slovnej pseudokódu.

377
00:22:23,520 --> 00:22:26,040
Dovoľte mi teda jednoducho skúste to znova. To fungovalo celkom dobre. Nebolo to vyrieši.

378
00:22:26,040 --> 00:22:30,400
Ale keď to pochybujem, skús a skúste to znova. Takže 2 a 4, nepomohlo už.

379
00:22:30,400 --> 00:22:33,200
4 a 6. Ah! 6 a 1, mierne lepšie.

380
00:22:33,200 --> 00:22:39,740
6 a 3, dobrá. 6 a 7, 7 a 5, 7 a 8, dobrá.

381
00:22:39,740 --> 00:22:44,060
A viete, som asi ignorovať 8 teraz, pretože je na konci zoznamu.

382
00:22:44,060 --> 00:22:47,250
Možno nemáme starať o niekoho, ísť okolo neho.

383
00:22:47,250 --> 00:22:49,240
Ale uvidíme, či je to bezpečný predpoklad.

384
00:22:49,240 --> 00:22:52,340
Teraz je zoznam - sakramentsky - nie je zoradená. Skúsme to znovu.

385
00:22:52,340 --> 00:22:56,440
Takže 2 a 4, 4 a 1, 4 a 3.

386
00:22:56,440 --> 00:22:59,230
4 a 6, dobrý. 6 a 5, dobrá.

387
00:22:59,230 --> 00:23:04,890
6, 7 a 8, dobrá. Ale upozornenie, môžem len zastaviť tu a tu zastaviť teraz?

388
00:23:04,890 --> 00:23:07,770
[Študent] Áno. Jo >>?

389
00:23:07,770 --> 00:23:11,160
Čo ak jeden z vás bol číslo 9 po celú cestu tam?

390
00:23:11,160 --> 00:23:13,640
To by boli roztriedené. Dobrý >>. To by boli roztriedené na prvýkrát.

391
00:23:13,640 --> 00:23:16,050
Dobré. Tak poďme späť. Už tam skoro sme.

392
00:23:16,050 --> 00:23:22,800
1 a 2, 2 a 3, 3 a 4, 4 a 5, 5 a 6, 6 a 7, 7 a 8.

393
00:23:22,800 --> 00:23:26,640
>> Ja som urobil, ale teraz, opäť som počítač, ktorý môže robiť len to, čo som povedal na to,

394
00:23:26,640 --> 00:23:30,120
a moja jediná spomienka je, že teraz som vlastne len urobil trochu práce.

395
00:23:30,120 --> 00:23:31,700
Niečo zmenilo tu.

396
00:23:31,700 --> 00:23:37,100
Tak som sa technicky potvrdené vizuálne alebo algoritmické, že tento zoznam je naozaj zoradené.

397
00:23:37,100 --> 00:23:40,720
Takže len pre istotu, len preto, aby sa análny o tom, poďme urobiť 1 viac času.

398
00:23:40,720 --> 00:23:44,040
Tak 1 a 2, 2 a 3, 3 a 4. A viete čo?

399
00:23:44,040 --> 00:23:46,190
Len pre istotu, budem sledovať na ruke tentoraz

400
00:23:46,190 --> 00:23:51,110
koľko swapy urobím len preto, že viem, koľko práce som vlastne urobil.

401
00:23:51,110 --> 00:23:56,930
3 a 4, 4 a 5, 5 a 6, 6 a 7, 7 a 8. Žiadne swapy.

402
00:23:56,930 --> 00:24:00,800
Takže teraz by som oprávnene idiot to urobiť znovu

403
00:24:00,800 --> 00:24:03,330
pretože keď som žiadnu prácu prostredníctvom tejto priechodu ľuďmi,

404
00:24:03,330 --> 00:24:06,710
potom jasne, že sa to stane znova, ak žiadny z nich nie je nejako náhodne

405
00:24:06,710 --> 00:24:10,410
adversarially pohybujúce sa okolo. Takže teraz môžem zastaviť.

406
00:24:10,410 --> 00:24:15,120
Teraz poďme položiť otázku, koľko práce sa to vlastne so mnou?

407
00:24:15,120 --> 00:24:18,260
Koľko krokov to trvalo? >> N druhú.

408
00:24:18,260 --> 00:24:20,400
Jo, tak n na druhú. Kde beriete n na druhú z?

409
00:24:20,400 --> 00:24:22,660
Musíte sa kontrolovať každý num -

410
00:24:22,660 --> 00:24:26,530
K dispozícii je n čísel, a budete musieť skontrolovať jednotlivé čísla s ostatnými n čísel.

411
00:24:26,530 --> 00:24:29,030
Dobré. Takže >> je to n na druhú. Dobrý >>.

412
00:24:29,030 --> 00:24:31,060
>> Takže to vyzerá, že by mohla byť veľmi dobre n na druhú, nie?

413
00:24:31,060 --> 00:24:33,820
Tam je n z týchto chlapci, 8 konkrétne v tomto prípade,

414
00:24:33,820 --> 00:24:37,590
ale zakaždým, keď som prechádzal tohto zoznamu som bol porovnaním prvej osobe, proti druhej,

415
00:24:37,590 --> 00:24:39,650
jednak proti tretej znovu a znovu a znovu,

416
00:24:39,650 --> 00:24:42,450
a keď som sa dostal na koniec, čo som urobil? Aj prerobil ho.

417
00:24:42,450 --> 00:24:46,280
Takže ak budeme zovšeobecňovať toto vysvetlenie, sme n ľuďom

418
00:24:46,280 --> 00:24:51,090
a ja robím, samozrejme, 8 krokov, n kroky, zakaždým som sa prejsť tohto algoritmu.

419
00:24:51,090 --> 00:24:56,070
Ale koľkokrát v najhoršom prípade musím prejsť tento zoznam ľudí?

420
00:24:56,070 --> 00:24:59,370
[Študent] N krát. Pravdepodobne >> n, P, pretože v najhoršom prípade,

421
00:24:59,370 --> 00:25:03,410
Čo je asi najhorší prípad usporiadania týchto chalanov z get-go?

422
00:25:03,410 --> 00:25:06,520
Ak sa to úplne obrátenom poradí

423
00:25:06,520 --> 00:25:09,310
pretože práve Predpokladám duševne, let 's - Ako sa voláte? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Dobre. Tak Bowen, poď sem na chvíľu.

425
00:25:12,510 --> 00:25:16,150
>> Predpokladajme, že Bowen bol tu na začiatku algoritmu,

426
00:25:16,150 --> 00:25:19,790
a my nevieme, čo všetci ostatní, ale Bowen tu, podľa tohto algoritmu -

427
00:25:19,790 --> 00:25:23,820
a ak chcete len prechádzať so mnou - bude bubliny hore, ako to urobil na prvýkrát,

428
00:25:23,820 --> 00:25:25,740
celú cestu až do konca.

429
00:25:25,740 --> 00:25:29,400
Ale predpokladám, že osoba vedľa Bowen bol číslo 7.

430
00:25:29,400 --> 00:25:33,450
Musím sa vrátiť a dostať číslo 7, čo znamená, že budem musieť ísť celú cestu sem.

431
00:25:33,450 --> 00:25:36,980
Teraz musím mať rovnaký prechádzku s osobou, ktorá je číslo 7.

432
00:25:36,980 --> 00:25:40,140
Ale čo keď bude číslo 6 bol vedľa neho rovnako?

433
00:25:40,140 --> 00:25:42,180
Potom som sa vrátiť a získať 6.

434
00:25:42,180 --> 00:25:46,490
Takže znovu, na každej iterácii tohto cyklu som hovoriť s každým z n ľudí,

435
00:25:46,490 --> 00:25:50,090
a budem musieť urobiť n týchto prechádzky, aby sa ubezpečil som ťahanie

436
00:25:50,090 --> 00:25:53,760
všetky z najväčších prvkov zadnej a späť a späť na samom konci zoznamu.

437
00:25:53,760 --> 00:25:58,230
Takže n vecí n krát, je len n krát n alebo n na druhú.

438
00:25:58,230 --> 00:26:02,050
>> Tak tu už máme algoritmus, ktorý je už n, to je už log n,

439
00:26:02,050 --> 00:26:04,820
je to vlastne ešte horšie, ako čokoľvek, čo sme robili predtým.

440
00:26:04,820 --> 00:26:09,840
Takže Alex druh šťastie v tom, že som všetky práce zrejme do prednej pre ňu,

441
00:26:09,840 --> 00:26:14,690
všetky drahé práce, tak, že sa môže užiť v tomto binárnom algoritmu,

442
00:26:14,690 --> 00:26:16,420
ktorý je log n

443
00:26:16,420 --> 00:26:18,240
Ale to je v súlade s témou pondelkového.

444
00:26:18,240 --> 00:26:23,260
Dali sme o trochu viac priestoru, sme použili viac bitov, s cieľom urýchliť náš hrací čas.

445
00:26:23,260 --> 00:26:26,170
Toľko, ako by ich to kompromis medzi časom a priestorom,

446
00:26:26,170 --> 00:26:31,060
tu môže tiež byť len kompromisy medzi čas strávený sa predné druh na získanie veci pripravený ísť

447
00:26:31,060 --> 00:26:35,000
a skutočne behu algoritmu, ako je vyhľadávanie. Skúsme iný.

448
00:26:35,000 --> 00:26:39,050
Ak ste to nevadilo len rýchlo preskupiť sami tak, aby zodpovedala znovu,

449
00:26:39,050 --> 00:26:42,240
Poďme skúsiť niečo trochu iné, ak to nie je tak jednoduché,

450
00:26:42,240 --> 00:26:45,760
ako len opraviť všetky párové chyby, čo je výborný intuitívne.

451
00:26:45,760 --> 00:26:48,150
Poďme namiesto toho byť trochu viac úmyselné a urobiť to.

452
00:26:48,150 --> 00:26:51,010
To tiež by som navrhnúť, je asi dosť intuitívne.

453
00:26:51,010 --> 00:26:55,070
>> Poďme vyberte najmenší osobu zo zoznamu znovu a znovu. Tak ideme na to.

454
00:26:55,070 --> 00:26:57,350
4, vy ste najmenší človek, ktorého som tak videl tak ďaleko,

455
00:26:57,350 --> 00:27:00,520
takže budem psychicky si uvedomiť, že tým, že len ukazuje na teba teraz.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Zabudnite na číslo 4. Našiel som nový najmenší prvok v tomto zozname.

457
00:27:05,020 --> 00:27:07,410
Idem na druhu pamäti, že. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Dovidenia. Takže teraz budem pamätať číslo 1.

459
00:27:11,190 --> 00:27:14,790
Vieme, že 1 je najmenší, ale ja som počítač. Čo keď tam 0?

460
00:27:14,790 --> 00:27:17,140
Čo keď tam -1? Musím ísť ďalej.

461
00:27:17,140 --> 00:27:20,990
Takže 3, 7, 5, uzlíkom. Dobre. Takže číslo 1 bol najmenší.

462
00:27:20,990 --> 00:27:23,640
Dovoľte mi, aby som vás vybrať zo zoznamu - Dáme ísť touto cestou -

463
00:27:23,640 --> 00:27:27,760
a ťa ľubovoľne na začiatku zoznamu.

464
00:27:27,760 --> 00:27:29,740
Teraz, počkaj. Tak nejako som podvedený.

465
00:27:29,740 --> 00:27:34,010
Ak títo ľudia predstavujú nie zoznam 8 ľudí, ale pole,

466
00:27:34,010 --> 00:27:37,050
8 kusy súvislé pamäte - nevadí vám ustúpil len na chvíľu?

467
00:27:37,050 --> 00:27:39,060
Je tu vlastne žiadny priestor pre vás tu.

468
00:27:39,060 --> 00:27:41,840
Tak ako sme sa vytvoriť priestor pre - Ako sa voláte? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Ako sme tak priestor pre Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Sťahujeme sa n, ktoré sú predo mnou. Dobre >>.

471
00:27:46,760 --> 00:27:48,850
Takže by sme mohli presunúť n ľudí, ktorí sú pred ním,

472
00:27:48,850 --> 00:27:52,400
takže ak ste chcieť vziať 1 úmyselné, dramatický krok doľava.

473
00:27:52,400 --> 00:27:57,000
Všetci robili, že v súzvuku, ale minule som písal nejaký kód,

474
00:27:57,000 --> 00:27:59,740
nemôžete nejako pohnúť veľa vecí naraz.

475
00:27:59,740 --> 00:28:02,450
Mohli by sme to urobiť v slučke, pohybujúce sa každý raz za čas.

476
00:28:02,450 --> 00:28:04,340
Takže ak ste to nevadilo ustúpil doprava,

477
00:28:04,340 --> 00:28:07,230
a Sammy, ak by ste mohli krok späť, pretože je tu ešte žiadny priestor pre vás,

478
00:28:07,230 --> 00:28:11,420
Teraz ideme na to. Ak bol Sammy pred chvíľou? Presne tam.

479
00:28:11,420 --> 00:28:16,140
Takže tam je medzera tam. Takže by ste mohli presunúť do miesta Sammyho.

480
00:28:16,140 --> 00:28:20,580
Teraz ďalšia osoba a teraz ďalší človek, teraz ďalšia osoba. Teraz máme priestor pre Sammyho.

481
00:28:20,580 --> 00:28:23,490
Teraz, niekto z publika - to bolo dobré, že bolo správne,

482
00:28:23,490 --> 00:28:27,070
bolo to trochu časovo náročné - to, čo je rýchlejšie? Jo.

483
00:28:27,070 --> 00:28:29,440
[Študent] nové pole? >> Čo je to? >> [Študent] nové pole? >> Dobre, dobre.

484
00:28:29,440 --> 00:28:33,200
>> Takže v súlade s touto tematikou len kompromisy, prečo jednoducho nemôžem urobiť nové pole

485
00:28:33,200 --> 00:28:36,570
 a potom Sammy bude plávať v priestore pred týmito ľuďmi, napríklad,

486
00:28:36,570 --> 00:28:39,600
a my môžeme len začať vyplnením nové pole úplne. To taky bude fungovať.

487
00:28:39,600 --> 00:28:42,450
Ale ja nemám záujem tráviť viac priestoru dnes. Čo je to iný prístup?

488
00:28:42,450 --> 00:28:46,630
[Študent] Swap. Dobre >>. Mohli by sme vymeniť tieto 2 ľudí. Ako sa voláte?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Takže Mario, si práve tu.

490
00:28:49,390 --> 00:28:52,480
Sammy, môžete zálohovať len na chvíľu? Mario je tu.

491
00:28:52,480 --> 00:28:55,830
Nemáme priestor pre vás už, takže ak by vám nevadilo ísť na miesto, kde Sammy je,

492
00:28:55,830 --> 00:29:02,430
dáme Sammy tu, a teraz by som tvrdiť, že Sammy je vymieňať operácia bola oveľa rýchlejšia.

493
00:29:02,430 --> 00:29:06,370
Urobili sme 1 operáciu vymeniť týchto ľudí, alebo možno 2 vymeniť týchto ľudí,

494
00:29:06,370 --> 00:29:11,210
ale my sme to neurobili 1, 2, 3, 4, takže sa cítia lepšie. Teraz, počkaj.

495
00:29:11,210 --> 00:29:14,660
Tak nejako som robil problém ešte horšie, pretože číslo 4 bolo celkom blízko k začiatku.

496
00:29:14,660 --> 00:29:19,470
Teraz číslo 4 je o niečo bližšie k tomuto cieľu, ale ja som naozaj nevedel, alebo sa starať o to.

497
00:29:19,470 --> 00:29:23,330
Takže je to len smola, že číslo 4 je o kúsok ďalej od svojho určeného miesta.

498
00:29:23,330 --> 00:29:25,110
Takže poďme sa teraz opakovať tento algoritmus.

499
00:29:25,110 --> 00:29:28,410
>> Zhrnúť, tak dlho, ako ten príbeh bol, všetko, čo sme urobili, bolo prejsť zoznam

500
00:29:28,410 --> 00:29:31,130
hľadá pre najmenších číslované osoby.

501
00:29:31,130 --> 00:29:34,530
Tak teraz poďme urobiť to znova. Nemáme sa báť Sammy už.

502
00:29:34,530 --> 00:29:37,590
Môžeme len ísť sem. Ooh! Číslo 2. To je dosť malé číslo.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Dobre, dobre.

504
00:29:41,180 --> 00:29:43,770
A našťastie, zhodou okolností, nemám sa pohybovať - ​​>> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie preto, že je na jeho pravé miesto teraz.

506
00:29:45,910 --> 00:29:48,110
Poďme to urobiť znovu a ignorovať tieto 2 ľudí.

507
00:29:48,110 --> 00:29:50,460
6. To je dosť malé číslo. Ooh! 8 je určite väčšia.

508
00:29:50,460 --> 00:29:53,410
4. Zamerajme sa na 4. Ooh! 3 je ešte lepší.

509
00:29:53,410 --> 00:29:58,290
7 a 5. Tak čo teraz budeme robiť s - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Poďme vymeniť ho s číslom 6.

511
00:30:00,250 --> 00:30:03,570
Takže ak 6 a 3 by chceli vymeniť,

512
00:30:03,570 --> 00:30:07,320
sme teraz trochu dostal šťastie v tom 6 je bližšie k miestu, kde by mal byť,

513
00:30:07,320 --> 00:30:10,300
ale je to len náhoda tu. Takže poďme sa teraz ísť sem.

514
00:30:10,300 --> 00:30:13,430
8 je dosť malé číslo. Ooh! 4 je menšie.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Čo budeme teraz robiť? >> Swap. Presne >>.

516
00:30:17,130 --> 00:30:19,010
Tak teraz poďme urobiť tento druh rýchlejšie.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Kam 5 ísť? Dobré. Dobre.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 dostane zostať, kde je. Ako sa voláte? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie dostane zostať, kde je. 7 dostane - Poďme sa pozrieť,. 7, 8. Dobre.

520
00:30:31,770 --> 00:30:35,100
Takže 7 dostane zostať, kde je. Ako sa voláte? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Takže Amna dostane zostať, kde je, a číslo 8 je už tam, kde sa teraz malo byť.

522
00:30:39,670 --> 00:30:43,960
Dobre, dobre. Pocit, ako sme len vytvárať prácu pre seba tu, hoci.

523
00:30:43,960 --> 00:30:47,440
Čo je to nakoniec doba chodu tohto algoritmu?

524
00:30:47,440 --> 00:30:51,900
Ak budeme uvažovať o týchto ľuďoch nie ako 8, ale ako n? >> Je to n

525
00:30:51,900 --> 00:30:55,440
Je to n krokov, ale my sme kontrolu zakaždým.

526
00:30:55,440 --> 00:30:57,570
Dobre. N, ale máte kontrolu zakaždým?

527
00:30:57,570 --> 00:31:03,450
Dobre, ale ak je to n krokov, nemal som bol schopný triediť vás len tak 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Dobre, to je veľký rozdiel.

529
00:31:05,590 --> 00:31:08,050
Tak n štvorcový prečo? Čo sa vlastne deje?

530
00:31:08,050 --> 00:31:12,130
Tam je n ľudí v tomto zozname, ale nájsť najmenší osobu v zozname

531
00:31:12,130 --> 00:31:16,200
v najhoršom prípade, koľko krokov musím vziať? N. >>

532
00:31:16,200 --> 00:31:19,160
>> N, P, pretože v najhoršom prípade, číslo 1 je úplne tam,

533
00:31:19,160 --> 00:31:20,990
takže musím ísť ho alebo ju.

534
00:31:20,990 --> 00:31:25,500
A potom, keď som sa konečne uvedomiť, 1 bol najmenší, potom je to celkom rýchlo vymeniť je.

535
00:31:25,500 --> 00:31:28,450
Ale teraz musím začať od začiatku a pozrieť sa na koho?

536
00:31:28,450 --> 00:31:31,980
Ďalšie Najmenší človek, ktorý je 2. Ak sa v najhoršom prípade je 2?

537
00:31:31,980 --> 00:31:34,320
Ach, môj Bože. Je to všetko tak tu na konci.

538
00:31:34,320 --> 00:31:37,000
Takže teraz som práve urobil ďalší n krokov, ďalšie n kroky.

539
00:31:37,000 --> 00:31:41,200
A ak máme n ľudí a v najhoršom prípade najmenšie osoba n krokov,

540
00:31:41,200 --> 00:31:45,230
to je zase n-krát n, a tak sme opäť sa n na druhú.

541
00:31:45,230 --> 00:31:47,280
To nie je pocit tak dobre.

542
00:31:47,280 --> 00:31:52,150
A v skutočnosti, dokonca v najlepšom prípade - predpokladám, že začať zoradené -

543
00:31:52,150 --> 00:31:59,080
koľko krokov to trvať pre mňa použitie tohto algoritmu pre triedenie týchto n ľudí?

544
00:31:59,080 --> 00:32:01,010
N vzpriamil. >> Počul som n na druhú. Prečo n štvorcový?

545
00:32:01,010 --> 00:32:05,240
Pretože stále máte skontrolovať zakaždým. Jo >>.

546
00:32:05,240 --> 00:32:08,060
A vy budete musieť vymeniť je. >> Aj keď my, ľudia sú trochu vševediaci

547
00:32:08,060 --> 00:32:10,770
v tom zmysle, vizuálne, že môžeme len tak vidieť, že je to zoradená,

548
00:32:10,770 --> 00:32:12,140
počítač nie je tak šikovný.

549
00:32:12,140 --> 00:32:14,040
Bude to vyzerať tu a tu a tu,

550
00:32:14,040 --> 00:32:16,610
ale ak to, čo hľadá, je najmenší prvok,

551
00:32:16,610 --> 00:32:22,110
si len, že ste našiel najmenší prvok tým, čo ide? Akonáhle ste na konci.

552
00:32:22,110 --> 00:32:25,880
Ale v tomto bode ste len našli práve najmenší prvok.

553
00:32:25,880 --> 00:32:28,810
Nemusíte nutne vedieť niečo o stave sveta.

554
00:32:28,810 --> 00:32:30,880
Takže budete musieť ísť znova a znova a znova.

555
00:32:30,880 --> 00:32:34,880
>> Takže tentoraz som naozaj vyzerať hlúpy, pretože som kontrolu, v poriadku, 2, si najmenší,

556
00:32:34,880 --> 00:32:37,530
ale ja neviem, že celkom zatiaľ.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Dobre, dobre. 2 bol naozaj najmenší.

558
00:32:41,090 --> 00:32:43,150
Teraz poďme nájsť ďalšie najmenší. Dobre.

559
00:32:43,150 --> 00:32:48,350
3, ste v súčasnej dobe najmenší. Poďme sa pozrieť,. 4, 5, 6, 7, 8. Dobre, mám šťastie znova.

560
00:32:48,350 --> 00:32:53,170
3 bol naozaj na správnom mieste. Ale budem to robiť znova a znova a znova.

561
00:32:53,170 --> 00:32:55,990
Ako môžeme urobiť niekedy tak trochu lepšie?

562
00:32:55,990 --> 00:33:00,120
Namiesto toho, aby ľudia vyvierajú po dvoch od najmenšej k najväčšej

563
00:33:00,120 --> 00:33:04,350
a namiesto toho tam a späť v zozname výberu vtedy najmenší osobu,

564
00:33:04,350 --> 00:33:09,780
prečo sa namiesto toho vložiť tých ľudí do nového zoznamu krok za krokom?

565
00:33:09,780 --> 00:33:13,080
Skúsme to. Teraz mi dovoľte volať túto vec vloženie radenie.

566
00:33:13,080 --> 00:33:17,250
Tak tu sme tu. Číslo 1. Ja sa nestarám o nikoho iného v tomto zozname.

567
00:33:17,250 --> 00:33:21,310
Mojím cieľom teraz je, aby číslo 1 na začiatku triedeného zoznamu.

568
00:33:21,310 --> 00:33:23,910
A ja budem navrhovať, pretože mám iba 8 kusy pamäti,

569
00:33:23,910 --> 00:33:28,670
ľubovoľne teraz som múr medzi moje údajne netriedeného zoznamu,

570
00:33:28,670 --> 00:33:32,740
a každý, kto je za mnou budem tvrdiť, je zoradená.

571
00:33:32,740 --> 00:33:34,680
Takže teraz máme číslo 1.

572
00:33:34,680 --> 00:33:39,240
Chcem vložiť ho do môjho zoznamu zoradené, takže som len tak pohnúť múru tu,

573
00:33:39,240 --> 00:33:43,930
a teraz tvrdím, tento zoznam je triedený, je tento zoznam netriedené - aspoň pokiaľ viem.

574
00:33:43,930 --> 00:33:46,070
Nevidím všetky čísla naraz.

575
00:33:46,070 --> 00:33:49,000
>> Teraz som náhodou stretnúť číslo 2. Čo mám robiť s ním?

576
00:33:49,000 --> 00:33:54,380
Aj vložiť ťa teraz do triedeného zoznamu. Ale všimnite si, ako jednoduché to bolo.

577
00:33:54,380 --> 00:33:59,650
Len som sa pozrieť. Číslo 1 je tam. Jo, samozrejme 2 ide na stranu číslo 1.

578
00:33:59,650 --> 00:34:03,700
Teraz, čo mám robiť s 3? Aj vložiť ťa do triedeného zoznamu. Ale to bolo super ľahké.

579
00:34:03,700 --> 00:34:07,250
To je super ľahké, to je super ľahké, to je super ľahké, super ľahké, super ľahké.

580
00:34:07,250 --> 00:34:12,790
A teraz všetko je vyriešené za mnou, a koľko krokov to trvalo?

581
00:34:12,790 --> 00:34:15,620
[Študenti] N. >> Tak je to len n Mali sme šťastie.

582
00:34:15,620 --> 00:34:18,860
To bolo len n prečo? >> [Študent] Vzhľadom k tomu, že bol zoznam zoradené.

583
00:34:18,860 --> 00:34:21,630
Zoznam už je zoradený. Takže sme mali šťastie.

584
00:34:21,630 --> 00:34:25,639
Ale sme navrhli algoritmus, tentoraz ktorá využíva tento druh šťastia,

585
00:34:25,639 --> 00:34:29,420
že najlepším prípade tým, že strácať zbytočne čas.

586
00:34:29,420 --> 00:34:31,750
Takže teraz máme, čo budeme hovoriť bublina druhy

587
00:34:31,750 --> 00:34:33,949
kde ľudia druh bubliny do párových.

588
00:34:33,949 --> 00:34:38,100
Teraz máme výber druhu, kde sme vytrhnúť najmenší osoba znovu a znovu.

589
00:34:38,100 --> 00:34:42,350
A teraz máme textový druh, kde sme trochu aktívne dať ľuďom tam, kam patrí

590
00:34:42,350 --> 00:34:45,000
v stále triedenom zozname.

591
00:34:45,000 --> 00:34:49,679
Ak by sme mohli, potlesk pre týchto ľudí tu. [Potlesk]

592
00:34:49,679 --> 00:34:52,310
Poďme vziať našu 5-minút prestávku tu.

593
00:34:52,310 --> 00:34:55,139
A keď sa vráti, budeme fúkať všetky tieto algoritmy z vody

594
00:34:55,139 --> 00:35:00,260
s niečím lepším. Dobrá. Díky moc. Môžete udržať tie ako suveníry.

595
00:35:01,710 --> 00:35:04,330
Dobrá. Sme späť.

596
00:35:04,330 --> 00:35:08,420
>> A zhrnúť veľmi rýchlo, museli sme tieto 3 rôzne prístupy k triedenia,

597
00:35:08,420 --> 00:35:13,000
celý bod, ktorý bol sa dostať do bodu, kedy niekto ako Alex

598
00:35:13,000 --> 00:35:16,930
mohol vyhľadávať zoznam čísel rýchlejšie ako niekoho, ako je Sean mohol.

599
00:35:16,930 --> 00:35:19,830
A aj keď máme také jednoduché príklady s číslami 8,

600
00:35:19,830 --> 00:35:24,000
môžete extrapolovať ľahko až 8 webových stránok, 8 miliárd webových stránok,

601
00:35:24,000 --> 00:35:26,680
alebo 800000000 priateľov na Facebooku.

602
00:35:26,680 --> 00:35:30,090
Takže tieto algoritmy možno určite škálovať až na tie druhy hodnôt,

603
00:35:30,090 --> 00:35:32,300
a myšlienky sú nakoniec rovnaký.

604
00:35:32,300 --> 00:35:36,140
Takže bublina sort bola prvá, kde sme trochu bublala do najvyššej osobu

605
00:35:36,140 --> 00:35:39,110
úplne vpravo tým, že vymení ľudí po dvoch.

606
00:35:39,110 --> 00:35:42,040
Potom sme mali, čo budeme hovoriť výber druhu, kde som trochu viac úmyselne

607
00:35:42,040 --> 00:35:46,480
stále hľadá v zozname, výberom najmenšie číslo znovu a znovu a znovu,

608
00:35:46,480 --> 00:35:49,530
logickým výsledkom je, že zoznam je nakoniec zoradené.

609
00:35:49,530 --> 00:35:53,780
Potom v tretej, vložil som ľudí do ich vhodnom mieste,

610
00:35:53,780 --> 00:35:57,720
a sme veľmi vymyslel príklad v tom, že zoznam bol už je zoradený,

611
00:35:57,720 --> 00:36:01,100
ale to bolo pre odoslanie správy, že v vkladacieho radiť tieto veci,

612
00:36:01,100 --> 00:36:02,670
môžete mať šťastie.

613
00:36:02,670 --> 00:36:07,930
Ak sú čísla už je zoradený, je to len bude vás n kroky na potvrdenie toľko,

614
00:36:07,930 --> 00:36:10,870
vzhľadom k tomu, výberu radiť ste trochu tunelové videnie

615
00:36:10,870 --> 00:36:14,360
a nemusíte vôbec uvedomiť, že zoznam už je zoradený.

616
00:36:14,360 --> 00:36:16,830
Tak uvidíme, bublina radenie v akcii tu.

617
00:36:16,830 --> 00:36:19,590
V nasledujúcom príklade, chystáme sa objaviť zvislé pruhy

618
00:36:19,590 --> 00:36:23,030
ktorých výška predstavujú čísla, takže môžeme nejako Vizualizácia triedenia sa stalo.

619
00:36:23,030 --> 00:36:26,630
Čím menší bar, tým menšie je číslo, tým väčšia bar, tým väčší počet.

620
00:36:26,630 --> 00:36:28,860
>> A budeme hrať v tomto implicitné rýchlosť.

621
00:36:28,860 --> 00:36:33,460
Bude to presunúť trochu rýchlo pre túto chvíľu, ale červená je to, čo sa ukazuje 2 tyče

622
00:36:33,460 --> 00:36:35,480
je v porovnaní vedľa seba.

623
00:36:35,480 --> 00:36:39,520
A keď sa budete pozerať pozorne, čo sa stane, je, že ak bary sú mimo prevádzky,

624
00:36:39,520 --> 00:36:42,300
menší z nich sa presunie doľava, ten väčší vpravo,

625
00:36:42,300 --> 00:36:44,360
a potom budete mať postupujúci.

626
00:36:44,360 --> 00:36:48,520
Takže keď sme to znova a znova, zistili, že najmenšie tyče

627
00:36:48,520 --> 00:36:51,090
sa bude držať tipovacej svoju cestu doľava

628
00:36:51,090 --> 00:36:54,130
a najväčšie tyče budú držať tipovacej svoju cestu vpravo.

629
00:36:54,130 --> 00:36:58,490
A skutočne, začíname vidieť vzor celú cestu na pravej strane

630
00:36:58,490 --> 00:37:04,790
rovnako ako sme videli 8 a potom 7 nakoniec vyviera až na koniec nášho ľudského zoznamu.

631
00:37:04,790 --> 00:37:08,750
Takže to bude veľmi rýchlo dostať trochu únavné, tak nech mi to zastaviť na chvíľu.

632
00:37:08,750 --> 00:37:10,980
Dovoľte mi, aby som meniť rýchlosť je oveľa rýchlejší.

633
00:37:10,980 --> 00:37:15,380
Nie som zmenu algoritmu, ja len robiť animácie stalo rýchlejšie.

634
00:37:15,380 --> 00:37:18,410
Napriek tomu bublina sort, rovnaký algoritmus,

635
00:37:18,410 --> 00:37:21,910
ale teraz môžete vidieť oveľa rýchlejšie ako naša slovná demonštrácie

636
00:37:21,910 --> 00:37:25,900
že najväčší prvky sú naozaj bublať až na vrchol.

637
00:37:25,900 --> 00:37:29,860
>> Ako stranou, tieto malé štvorčeky v ľavom dolnom rohu a pravom dolnom

638
00:37:29,860 --> 00:37:33,520
sú len malé pripomenutie ako na to, koľko porovnaní robíte.

639
00:37:33,520 --> 00:37:37,620
Ale teraz, môžeme sa sústrediť na pyramídy, ktorý je formuje, a tam to ide.

640
00:37:37,620 --> 00:37:41,510
Najmenší prvok je na ľavej strane, najväčší na pravej strane, a všetko ostatné medzi tým.

641
00:37:41,510 --> 00:37:44,470
Teraz poďme miesto sa pozrieť na výber druhu.

642
00:37:44,470 --> 00:37:47,260
Chystám sa ísť dopredu a udrel Stop. Budeme si novú náhodnú sadu tyčí.

643
00:37:47,260 --> 00:37:50,930
Výber druhu, odvolanie, prechádza v zozname znovu a znovu a znovu,

644
00:37:50,930 --> 00:37:54,900
šklbanie sa na najmenší prvok. Takže tu je výber sort.

645
00:37:54,900 --> 00:37:58,390
Vyzerá to, že tam je menej práce sa deje teraz, pretože nie sme nákupný párovaný

646
00:37:58,390 --> 00:38:02,590
ale my sme tak nejako zneužité najmenšie prvky sprava doľava.

647
00:38:02,590 --> 00:38:06,890
To trvalo veľmi málo času, takže je dichotómia už.

648
00:38:06,890 --> 00:38:11,820
Len preto, že algoritmus je povedal, aby n štvorcový čas, rovnako ako bubliny radiť

649
00:38:11,820 --> 00:38:16,100
a ako výber druhu, ktoré sú naozaj najhorší prípad doby chodu.

650
00:38:16,100 --> 00:38:21,790
Napríklad, v prípade, povedzme, výber druhu,

651
00:38:21,790 --> 00:38:27,240
Vlastne som som výber najmenšie osobu a dávať ho alebo ju sem,

652
00:38:27,240 --> 00:38:29,620
potom som to zase robíš, potom som to zase robíš,

653
00:38:29,620 --> 00:38:32,070
ale došlo k miernemu optimalizácia som mohol robiť.

654
00:38:32,070 --> 00:38:35,040
>> Akonáhle som sa presťahoval číslo 1 tu - Sammy v tomto prípade -

655
00:38:35,040 --> 00:38:38,630
čo som potrebné urobiť s ním potom? >> [Študent] Nechajte ho.

656
00:38:38,630 --> 00:38:40,140
Nechajte ho, že jo? Nič.

657
00:38:40,140 --> 00:38:44,310
Nepotreboval som, aby niekedy hovoriť s Sammyho znova, pretože keď som vybrala najmenší prvok

658
00:38:44,310 --> 00:38:48,580
a dal ho sem, prečo strácať čas ísť na koniec celom mojom zozname?

659
00:38:48,580 --> 00:38:54,590
Na ďalšej iterácii dovoľte mi, aby som skutočne pohybovať len číslo 2, iba čísla 3.

660
00:38:54,590 --> 00:38:57,640
Takže v skutočnosti, som nerobil n veci n časy.

661
00:38:57,640 --> 00:39:05,380
Robil som n vecí, potom n - 1 veci, potom n - 2 veci, potom n - 3 veci,

662
00:39:05,380 --> 00:39:07,080
potom n - 4, bodka, bodka, bodka.

663
00:39:07,080 --> 00:39:09,470
Máme trochu geometrickom rade, ktorá práve znamená

664
00:39:09,470 --> 00:39:11,450
pridávate do postupne menší počet.

665
00:39:11,450 --> 00:39:17,940
Nie n + n + n + n, ale n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
A čo, že všeobecne funguje ako -

667
00:39:21,380 --> 00:39:24,280
Idem pokaziť mojej doske tu len na chvíľu -

668
00:39:24,280 --> 00:39:28,990
že to bude fungovať, že je niečo ako n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
keby sme tak nejako pohľad na zadnej časti učebnice matematiky, kde máte všetky ťaháky

670
00:39:31,930 --> 00:39:33,410
Ku vzorcom.

671
00:39:33,410 --> 00:39:37,760
Ak ste práve pridaním niečo n + n - 1 + n - 2, to vyjde za niečo také.

672
00:39:37,760 --> 00:39:42,320
A ak by sme to proste množia na to, že je n na druhú mínus n / 2.

673
00:39:42,320 --> 00:39:46,400
Stále som hovoril n na druhú, aj keď, a to preto, že som bol trochu pri duševnej skratky

674
00:39:46,400 --> 00:39:51,950
pretože v skutočnosti, n na druhú mínus n deleno 2 je naozaj skutočný počet krokov

675
00:39:51,950 --> 00:39:55,510
že algoritmus ako výber druhu by sa, ak naozaj sčítajú

676
00:39:55,510 --> 00:39:58,800
Zo všetkých týchto porovnaní a všetky malé rušné prácu, ktorú sme robili.

677
00:39:58,800 --> 00:40:03,210
Ale úprimne povedané, akonáhle sa dostane n byť ako milión alebo miliardu, kto to sakra zaujíma

678
00:40:03,210 --> 00:40:07,160
ak robíte miliardu na druhú mínus miliardy rozdelenej 2?

679
00:40:07,160 --> 00:40:09,320
Miliardy na druhú je obrovské množstvo.

680
00:40:09,320 --> 00:40:13,580
Môžete si vziať ďalšie miliardy z nej s - n Nie je to tak veľký problém.

681
00:40:13,580 --> 00:40:18,770
Takže čím väčšie čísla sa, že menej dôležité tieto nižšie objednané termíny sú.

682
00:40:18,770 --> 00:40:24,230
Koho zaujíma, či ste deliť 2, ak hovoríte o kvadriliony o počte krokov?

683
00:40:24,230 --> 00:40:29,710
>> Takže všeobecne, počítačoví odborníci majú tendenciu vyhadzovať všetko, ale najväčšie termín,

684
00:40:29,710 --> 00:40:33,140
a my sme tak nejako zjednodušiť svet a povedať, že algoritmus

685
00:40:33,140 --> 00:40:38,130
sa zhruba n druhú kroky. To je doba chodu algoritmu.

686
00:40:38,130 --> 00:40:40,760
Takže sa vrátime k tomu za chvíľu s niektorými konkrétnymi príkladmi,

687
00:40:40,760 --> 00:40:45,940
ale teraz, že je to niečo ako intuitívne motivácie za práve zjednodušenie náš svet

688
00:40:45,940 --> 00:40:51,170
a hovorí o najdôležitejších pojmov, skôr než dostať sa do všetkých týchto fantázie vzorcov.

689
00:40:51,170 --> 00:40:53,540
Takže to bol výber triedenia, a máme trochu šťastia tam.

690
00:40:53,540 --> 00:40:57,360
Poďme sa pozrieť na vloženie radiť. Nechaj ma ísť napred a začať túto rovnako.

691
00:40:57,360 --> 00:41:00,330
Teraz si všimnite vzor, ​​ktorý sa deje, je trochu iný,

692
00:41:00,330 --> 00:41:03,410
a začali sme s náhodnými číslami,

693
00:41:03,410 --> 00:41:06,890
ale ak sme skutočne počítať počet krokov v najhoršom prípade,

694
00:41:06,890 --> 00:41:11,070
v prípade, že zoznam začal úplne v správnom poradí,

695
00:41:11,070 --> 00:41:13,380
by sme trvať len n kroky k realizácii toľko.

696
00:41:13,380 --> 00:41:18,240
>> Ale v prípade, že sú v skutočnosti zoznam dozadu - napríklad, v tomto prípade sa tu -

697
00:41:18,240 --> 00:41:23,860
potom všimnete skutočnosti máme urobiť oveľa viac práce v tomto prípade.

698
00:41:23,860 --> 00:41:27,080
A to by malo trochu pocit, pre Vás, ako toto je druh pracovať usilovnejšie

699
00:41:27,080 --> 00:41:30,900
dostať tie menšie prvky vľavo, a to preto, že sme sa dostali smolu.

700
00:41:30,900 --> 00:41:34,210
Zoznam bol zoradené náhodne opačne.

701
00:41:34,210 --> 00:41:38,110
Naopak, s vloženie radiť keby sme napodobňovať to, čo sme urobili s našimi ľuďmi tu

702
00:41:38,110 --> 00:41:42,670
tým, že začína s každým zoradené a potom začať, je to celkom dobrý algoritmus, nie?

703
00:41:42,670 --> 00:41:45,010
Je to už v skutočnosti, sú zoradené.

704
00:41:45,010 --> 00:41:48,670
Takže poďme sa pokúsiť zhrnúť, koľko času tieto veci berú nám

705
00:41:48,670 --> 00:41:52,360
zavedením len trochu žargónu alebo notácie, ktorá je v skutočnosti oveľa jednoduchšie,

706
00:41:52,360 --> 00:41:54,320
ako fanciness druh naznačuje.

707
00:41:54,320 --> 00:41:59,030
To, čo tu, tento veľký O na obrazovke, je to, čo počítačový vedec bude všeobecne používať

708
00:41:59,030 --> 00:42:03,640
popísať najhoršie čas behu algoritmu.

709
00:42:03,640 --> 00:42:07,360
>> Opäť, v najhoršom prípade, je to úplne závislé na kontexte.

710
00:42:07,360 --> 00:42:10,890
Čo máme na mysli najhoršom prípade úplne sa líši v závislosti na probléme hovoríme o

711
00:42:10,890 --> 00:42:14,550
Ale v prípade triedenia, čo je najhorší možný scenár?

712
00:42:14,550 --> 00:42:17,860
Všetko je pospiatky, pretože to jednoducho pripadá ako to znamená veľa práce za nás.

713
00:42:17,860 --> 00:42:21,330
Ja som poznačil niekoľko algoritmov, ktoré sme videli doteraz:

714
00:42:21,330 --> 00:42:24,930
lineárne vyhľadávanie, binárne vyhľadávanie ako s telefónnom zozname alebo kúsky papiera,

715
00:42:24,930 --> 00:42:28,960
potom bublina sort, výber sort, a vloženie sort, ako sme videli s našimi ľuďmi,

716
00:42:28,960 --> 00:42:31,770
a potom 1 oznámi, že to nakoniec bude nazývaný zlúčenie radenie.

717
00:42:31,770 --> 00:42:37,710
Takže v lineárne hľadanie v najhoršom prípade, koľko krokov to trvať nájsť číslo 7

718
00:42:37,710 --> 00:42:40,690
ak existujú n dvere ako Sean Tvárou v tvár? >> [Študent] N.

719
00:42:40,690 --> 00:42:44,180
N. Takže budeme písať veľkú O n.

720
00:42:44,180 --> 00:42:47,010
Idem len vyplniť v niektorých medzier. To je len mriežka polotovarov.

721
00:42:47,010 --> 00:42:52,990
Ale v najlepšom prípade s lineárnou hľadanie, možno 7 boli na samom začiatku zoznamu,

722
00:42:52,990 --> 00:42:55,520
a Sean mohol začať pozerať na začiatku zoznamu.

723
00:42:55,520 --> 00:42:58,940
Takže ak používate lineárne vyhľadávanie a len kontrolovať zľava doprava alebo možno sprava doľava -

724
00:42:58,940 --> 00:43:02,650
sú rovnocenné - v najlepšom prípade, koľko krokov by mohol lineárne vyhľadávanie,

725
00:43:02,650 --> 00:43:05,550
ako algoritmus Seana, vziať? Len 1 krok.

726
00:43:05,550 --> 00:43:09,450
>> Tak som chcel povedať, že je to omega notácie.

727
00:43:09,450 --> 00:43:11,570
To je len hlavné omega.

728
00:43:11,570 --> 00:43:15,000
Omega je len sexy spôsob, ako povedať najlepšom prípade jazdnej doby.

729
00:43:15,000 --> 00:43:18,900
Takže v najlepšom prípade hrací čas je jeden krok, alebo konštantný počet krokov -

730
00:43:18,900 --> 00:43:24,270
1 v tomto prípade - ale v najhoršom prípade, veľký O, to je vlastne n krokov.

731
00:43:24,270 --> 00:43:28,110
A tento tu, theta, my vlastne ani pozerať na práve teraz.

732
00:43:28,110 --> 00:43:30,090
To nie je relevantné pre tento konkrétny príklad.

733
00:43:30,090 --> 00:43:31,990
Ale teraz skúsme binárne vyhľadávanie.

734
00:43:31,990 --> 00:43:35,990
V najhoršom prípade sa binárne vyhľadávanie, koľko krokov je to bude trvať nájsť číslo 7

735
00:43:35,990 --> 00:43:38,340
alebo čokoľvek, čo ste hľadali? >> [Študent] Log n

736
00:43:38,340 --> 00:43:40,980
Stále bude trvať log n, pretože rovnako ako Alex dostal smolu

737
00:43:40,980 --> 00:43:44,030
keď sme naozaj pracovali cez problému metodicky

738
00:43:44,030 --> 00:43:48,220
a ona nenašla číslo 7 až do poslednej dverí sa pozrel na,

739
00:43:48,220 --> 00:43:51,720
aj keď, v spravodlivosť, dostala vyhodiť niektoré dvere pozdĺž cesty,

740
00:43:51,720 --> 00:43:56,920
binárne hľadanie v najhoršom prípade má hrací čas log n

741
00:43:56,920 --> 00:43:59,230
A opäť, že hovorí k tomuto deleniu a dobývania.

742
00:43:59,230 --> 00:44:01,140
Ale čo v najlepšom prípade?

743
00:44:01,140 --> 00:44:04,790
A Alex vlastne zažil, že najlepšia vec pravdu, keď prišla na pódium.

744
00:44:04,790 --> 00:44:07,290
Koľko krokov to trvalo v binárnom vyhľadávaní? >> [Študent] 1.

745
00:44:07,290 --> 00:44:09,380
1, len preto, že mali šťastie.

746
00:44:09,380 --> 00:44:12,520
Ale to je v poriadku, pretože omega sa týka najlepších scenárov,

747
00:44:12,520 --> 00:44:15,770
najlepšom prípade vstupov, aj keď je to len náhodný nemé šťastie.

748
00:44:15,770 --> 00:44:18,900
>> Teraz, toto príliš budeme len druh Ponechajte prázdne pre teraz.

749
00:44:18,900 --> 00:44:21,010
Ako teraz bublina trochu?

750
00:44:21,010 --> 00:44:24,290
V najhoršom prípade sa bubliny radiť, každý je v opačnom poradí,

751
00:44:24,290 --> 00:44:26,380
takže musíme urobiť veľa bublín.

752
00:44:26,380 --> 00:44:30,190
Ale koľko krokov je to, že bude trvať v najhoršom prípade? >> [Študent] N druhú.

753
00:44:30,190 --> 00:44:32,550
To bolo n na druhú, pretože ak si myslíte, že o tom,

754
00:44:32,550 --> 00:44:36,410
ak je zoznam úplne dozadu - 8 je tu, 1 je tu -

755
00:44:36,410 --> 00:44:40,530
ako vec, začnú bubliny, číslo 8 sa bude pohybovať takto, takto,

756
00:44:40,530 --> 00:44:44,540
Týmto spôsobom, týmto spôsobom, ale kde je číslo 7 v najhoršom prípade?

757
00:44:44,540 --> 00:44:47,720
Tu je stále tam. Tak sme to urobiť znovu a znovu.

758
00:44:47,720 --> 00:44:53,190
A to je miesto, kde sme si n krokov, potom n - 1 krokov, potom n - 2 stupne.

759
00:44:53,190 --> 00:44:55,960
A ak budete mať svoje slovo pre to - že ak druh množiť to,

760
00:44:55,960 --> 00:45:00,110
je to zhruba n opracované na konci s niektorými ďalšími podmienkami, ktoré budeme jednoducho ignorovať zatiaľ -

761
00:45:00,110 --> 00:45:06,890
potom v najhoršom prípade druhu bublinkové je n na druhú, dávať alebo brať.

762
00:45:06,890 --> 00:45:09,490
Ale čo najlepšom prípade s bublinou radiť?

763
00:45:09,490 --> 00:45:13,050
Aký je najlepší možný scenár? Všetky čísel sú zoradené už.

764
00:45:13,050 --> 00:45:15,920
A čo bolo heuristický som, trik som použil,

765
00:45:15,920 --> 00:45:20,110
uvedomiť si, že som urobil žiadnu prácu, a mohol preto zastaviť skôr?

766
00:45:20,110 --> 00:45:23,590
[Študent] Skontrolujte raz. Skontrolujte >> raz. Ale čo som robil na ceste?

767
00:45:23,590 --> 00:45:26,130
Bol som sledovanie, koľko swapy som.

768
00:45:26,130 --> 00:45:30,650
A uvedomil som si, či som nepočítal žiadne swapy na prstoch, potom som urobil žiadnu prácu.

769
00:45:30,650 --> 00:45:34,300
Určite by sa nemala snažiť robiť žiadnu prácu znova, tak som si jednoducho prestať.

770
00:45:34,300 --> 00:45:37,830
>> Takže v najlepšom prípade bublín druhu, ak je už zoznam zoradené,

771
00:45:37,830 --> 00:45:41,530
čo by ste povedali zápis omega je, v najlepšom prípade beží čas?

772
00:45:41,530 --> 00:45:48,040
Je to len n Musíme urobiť nejakú prácu, ale máme len urobiť 1 prechádzku stojí za prácu.

773
00:45:48,040 --> 00:45:50,490
A tu taky budem dovolenky v tejto časti prázdne.

774
00:45:50,490 --> 00:45:52,430
A teraz výber sort.

775
00:45:52,430 --> 00:45:56,010
Výber radenie sa mi, že zahrá na najmenšie osoba znovu a znovu.

776
00:45:56,010 --> 00:45:58,380
A čo na to hovoríme, že doba chodu to bolo?

777
00:45:58,380 --> 00:46:00,590
To bolo n narovnal v najhoršom prípade.

778
00:46:00,590 --> 00:46:05,220
A bohužiaľ, v najlepšom prípade je to tiež n na druhú

779
00:46:05,220 --> 00:46:08,840
pretože nemám ten typ vševedúci pohľadu celého sveta;

780
00:46:08,840 --> 00:46:13,140
Ja len viem, na úplné opakovanie, že som skutočne našiel najmenší osobu.

781
00:46:13,140 --> 00:46:15,860
Takže výber druh druh nasáva v tomto zmysle,

782
00:46:15,860 --> 00:46:17,920
ale Výhodou je je to trochu intuitívne.

783
00:46:17,920 --> 00:46:21,470
Je to celkom jednoduché kód, pretože všetko, čo musíte urobiť, je napísať pár vnorených slučiek pre,

784
00:46:21,470 --> 00:46:24,620
typicky, ktorá prechádza hľadá najmenší prvok

785
00:46:24,620 --> 00:46:27,840
a umiestni najmenší prvok kam patrí na konci zoznamu.

786
00:46:27,840 --> 00:46:29,900
Takže aj tu to bude trade-off.

787
00:46:29,900 --> 00:46:34,440
Množstvo času to trvá vám premýšľať a skutočne vyvinúť niečo o písaní kódu

788
00:46:34,440 --> 00:46:39,460
môže veľmi dobre mať viac času, ak chcete lepšie algoritmus a rýchlejší výkon.

789
00:46:39,460 --> 00:46:41,780
>> Ale ak ste naozaj len trochu kódu niečo do rýchle a špinavé

790
00:46:41,780 --> 00:46:45,000
a tak nejako sa tá najhlúpejší možnú predstavu si môžete myslieť,

791
00:46:45,000 --> 00:46:47,580
, Ktoré by mohli trvať aj niekoľko minút kódu, ale s veľkými súbormi dát

792
00:46:47,580 --> 00:46:49,580
Vaša algoritmus môže trvať niekoľko hodín bežať.

793
00:46:49,580 --> 00:46:51,690
A dokonca som v postgraduálnom štúdiu by niekedy robiť tieto kompromisy.

794
00:46:51,690 --> 00:46:55,660
Bolo by 3am, som sa snažil analyzovať niektoré veľmi veľké dátové sady

795
00:46:55,660 --> 00:46:59,650
vzťahujúce sa k výskumu bezpečnosti som robil, a to bol jeden stráviť 5 minút

796
00:46:59,650 --> 00:47:03,210
ladením svoj program analyzovať dáta a ísť spať

797
00:47:03,210 --> 00:47:08,420
alebo stráviť 8 hodín ako sa to práve preto, že beží okamžite a ísť spať.

798
00:47:08,420 --> 00:47:10,530
A tak tam taky je to trochu z vedomého rozhodnutia.

799
00:47:10,530 --> 00:47:12,740
Menej doba vývoja, viac spánku.

800
00:47:12,740 --> 00:47:14,780
V spätnom pohľade, by som asi nemala podporovať, aby

801
00:47:14,780 --> 00:47:19,120
keď cieľom je optimalizovať kvalitu kódu,

802
00:47:19,120 --> 00:47:21,280
ale aj to v reálnom svete, je veľmi rozumné trade-off.

803
00:47:21,280 --> 00:47:25,130
Menej času, menej výkonu alebo naopak.

804
00:47:25,130 --> 00:47:28,110
Takže tu máme konečne šancu hovoriť o theta.

805
00:47:28,110 --> 00:47:32,830
Theta notácie je niečo, čo počítačoví experti môžu priniesť v rozhovore

806
00:47:32,830 --> 00:47:36,160
keď veľké O a omega náhodou rovnaké.

807
00:47:36,160 --> 00:47:40,160
Hovoríte, že theta naozaj poslať správu, že toto je pevne viazaný.

808
00:47:40,160 --> 00:47:43,340
Bez ohľadu na to, či scenár je dobré alebo zlé, je to n na druhú.

809
00:47:43,340 --> 00:47:46,510
Tak to jednoducho nie je relevantné v týchto príbehoch tu.

810
00:47:46,510 --> 00:47:48,560
Vloženie druh je posledný sme sa na,

811
00:47:48,560 --> 00:47:50,830
kde som bol jednoduchým vložením každého na správnom mieste.

812
00:47:50,830 --> 00:47:54,930
V najlepšom prípade to, čo bolo doba chodu inzercia druhu, ako sme to videli tu?

813
00:47:54,930 --> 00:47:57,250
[Študent] Najlepší prípad? >> Najlepší prípad.

814
00:47:57,250 --> 00:48:00,100
>> To bolo n preto, že v najlepšom prípade všetci sú zoradené,

815
00:48:00,100 --> 00:48:02,580
a Sammy a nikto iný naozaj musel pohybovať vôbec.

816
00:48:02,580 --> 00:48:04,610
Boli už v ich správnom mieste.

817
00:48:04,610 --> 00:48:08,570
Takže vloženie radenie v najlepšom prípade je v tomto prípade, n

818
00:48:08,570 --> 00:48:12,770
Ale v najhoršom prípade je to trochu n na druhú. Prečo?

819
00:48:12,770 --> 00:48:16,230
Ak môj zoznam ľudí je v opačnom poradí,

820
00:48:16,230 --> 00:48:21,260
Prvýkrát som začať s číslom 8 a vložím ho alebo ju do správnej polohy, čo je tu.

821
00:48:21,260 --> 00:48:25,270
Aj druh pohybu do strany. Títo chalani sú netriedené, že on alebo ona je zoradený.

822
00:48:25,270 --> 00:48:28,970
Ale teraz som sa náhodou zistiť, kto ďalší? >> [Študent] 7.

823
00:48:28,970 --> 00:48:31,250
7 v najhoršom prípade, pretože je to v opačnom poradí.

824
00:48:31,250 --> 00:48:34,920
>> Takže tu je 7. Kde 7 patrí? Určite za mnou.

825
00:48:34,920 --> 00:48:39,460
Ale teraz 7 vlastne patrí nie je bezprostredne za mnou, ale za číslom 8,

826
00:48:39,460 --> 00:48:41,880
tak musím povedať: "Prepáčte, číslo 8, môžete mi prosím presunúť túto cestu

827
00:48:41,880 --> 00:48:44,640
"Aby sa vytvoril priestor pre 7?" Teraz som stretávajú 6.

828
00:48:44,640 --> 00:48:48,530
"Ach, prepáčte, číslo 8 a číslo 7, môžete prejsť, aby sa priestor pre 6?"

829
00:48:48,530 --> 00:48:52,360
Takže inými slovami, s vloženie radiť, aj keď nerobím moc pohybu,

830
00:48:52,360 --> 00:48:56,330
ľudia za mnou robia oveľa viac práce, a to má stáť niekoho čas.

831
00:48:56,330 --> 00:48:58,000
Bude to stať sa počítačového času.

832
00:48:58,000 --> 00:49:01,450
Takže v prípade vloženia radiť stále trpí.

833
00:49:01,450 --> 00:49:06,260
Ak začnete pridávať do celkového počtu krokov, sme skončiť biť nahrubo opracované n

834
00:49:06,260 --> 00:49:11,160
pretože títo ľudia potrebujú, aby sa priestor pre človeka byť vložený späť do tohto zoznamu.

835
00:49:11,160 --> 00:49:15,960
A tak je v tomto prípade theta jednoducho nie je použiteľná pre konkrétneho príbehu po ruke.

836
00:49:15,960 --> 00:49:21,100
To je všetko pekné a dobré. Máme tieto 3 rôzne spôsoby hovoril o dobe chodu.

837
00:49:21,100 --> 00:49:26,370
Ale čo to vlastne znamená v reálnych podmienkach, ak sa skutočne snaží, aby kód sa algoritmus?

838
00:49:26,370 --> 00:49:31,620
>> Dovoľte mi, aby som navrhla, že tam je to ešte lepšie algoritmus tam

839
00:49:31,620 --> 00:49:33,740
, Ktorý sám má nejaké kompromisy.

840
00:49:33,740 --> 00:49:36,890
Budeme hovoriť, že zlúčenie druh, a to trochu tohto čarovného algoritmu

841
00:49:36,890 --> 00:49:42,840
že práve pracuje rýchlejšie nejako, a je to tak jednoduché vyjadriť, aspoň v pseudokódu.

842
00:49:42,840 --> 00:49:46,900
Vykonávanie tohto druhu algoritmu merge bude takto.

843
00:49:46,900 --> 00:49:50,860
Keď ste rovnako n prvkov - N čísla, n ľudí, bez ohľadu na - prvý je tu zdravý rozum kontrola.

844
00:49:50,860 --> 00:49:56,340
Ak je n menšie ako 2, zlúčiť už len zastaví. To sa vráti, aby som tak povedal.

845
00:49:56,340 --> 00:50:00,830
Prečo by ste zastaviť, ak n je menší ako 2? >> [Nepočuteľné Študent odpoveď]

846
00:50:00,830 --> 00:50:04,480
Právo. A opäť, n nie je číslo v zozname, n je veľkosť zoznamu.

847
00:50:04,480 --> 00:50:07,660
Ak je n je menší ako 2, to znamená, že je zoznam buď 1,

848
00:50:07,660 --> 00:50:09,640
kde ste zrejme zoradená, ak je to 1 číslo,

849
00:50:09,640 --> 00:50:11,710
alebo 0, v tom prípade nie je čo triediť,

850
00:50:11,710 --> 00:50:13,570
takže potrebujeme tento druh základné veci.

851
00:50:13,570 --> 00:50:20,350
Ak je zoznam je tak krátka, že tam je jednoducho nič robiť, doslova sa nič robiť. Návrat.

852
00:50:20,350 --> 00:50:25,090
Inak radiť ľavú polovicu prvkov, potom triediť pravú polovicu prvkov,

853
00:50:25,090 --> 00:50:27,410
potom zlúčiť 2 zoradené polovice.

854
00:50:27,410 --> 00:50:32,130
>> Tento druh sa javí ako malý podvod, kedy som sa ťa pýtam, ako radiť prvky

855
00:50:32,130 --> 00:50:34,900
a vy mi hovoríte, "Zoradiť ľavú polovicu, triediť pravú polovicu."

856
00:50:34,900 --> 00:50:37,240
Som rád, "v poriadku. Ako triediť ľavú polovicu?"

857
00:50:37,240 --> 00:50:40,670
"Zoraďte ľavú polovicu ľavej polovici, triediť pravú polovicu ľavej polovice, a potom urobil."

858
00:50:40,670 --> 00:50:44,060
Ste typ cyklicky definovať, čo to znamená triediť,

859
00:50:44,060 --> 00:50:46,790
ale ukazuje sa, že je to skutočne geniálny v tomto prípade.

860
00:50:46,790 --> 00:50:50,230
To nie je naozaj to začarovaný kruh, ktorý nikdy nekončí

861
00:50:50,230 --> 00:50:52,550
pretože to končí, keď? >> [Študent] Keď sa dostanete 1 vec.

862
00:50:52,550 --> 00:50:54,220
Keď sa dostanete 1 vec.

863
00:50:54,220 --> 00:50:57,850
Takže aj keď ste možno začať s 8 ľudí a ja som povedal, "Zoradiť ľavú polovicu týchto ľudí,

864
00:50:57,850 --> 00:51:00,480
tieto 4 ľudí, "potom hovorím," Ako môžete triediť ľavú polovicu? "

865
00:51:00,480 --> 00:51:03,450
"No, triediť 2 ľudí tu." A potom si ako: "Dobre, dobre."

866
00:51:03,450 --> 00:51:05,520
"Ako môžete triediť ľavú polovicu z tých ľudí?"

867
00:51:05,520 --> 00:51:09,040
"Len triediť tento 1 osobu tu." Čo je to brilantný odhalenie teraz?

868
00:51:09,040 --> 00:51:13,050
Musím triediť 1 osobu. Hotovo. Nemám k tomu žiadnu prácu.

869
00:51:13,050 --> 00:51:16,580
Ale teraz musím vyriešiť túto osobu, ale sú jedna osoba, čo robiť.

870
00:51:16,580 --> 00:51:21,490
>> Takže mágia je zrejme v tomto treťom kroku: zlúčiť zoradené polovice.

871
00:51:21,490 --> 00:51:25,770
Takže zlúčiť druh má túto výnimočnú možnosť nahliadnuť, že ak porušíte veľký problém sa

872
00:51:25,770 --> 00:51:28,650
do 2 menších, rovnako veľkých problémov

873
00:51:28,650 --> 00:51:32,710
a potom sa len druh lepidla menšie riešenie spoločne na konci,

874
00:51:32,710 --> 00:51:34,720
Navrhujem, že môžeme urobiť oveľa, oveľa lepší [odposluch zvuk]

875
00:51:34,720 --> 00:51:38,050
ako ktorýkoľvek z výberového druhu alebo vloženie zoradiť.

876
00:51:38,050 --> 00:51:40,690
Ja som skutočne ignorovať, že za pol hodiny, ale ja naozaj neviem, čo sa deje

877
00:51:40,690 --> 00:51:45,040
mimo dnes. [Vrčanie zvuku] [smiech]

878
00:51:45,040 --> 00:51:49,660
Tak uvidíme, či môžeme vidieť to s trochou pomoci od nášho kamaráta Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
K dispozícii sú 2 veľké kroky v procese druhu korešpondencie.

880
00:51:52,810 --> 00:51:56,400
Po prvé, neustále rozdelí zoznam šálok do polovice

881
00:51:56,400 --> 00:51:59,610
kým nebudeme mať veľa zoznamov iba s 1 šálkou v nich.

882
00:51:59,610 --> 00:52:02,150
Nebojte sa, ak zoznam obsahuje nepárny počet

883
00:52:02,150 --> 00:52:04,830
a nemôžete urobiť dokonale čistý rez medzi nimi.

884
00:52:04,830 --> 00:52:08,740
Len ľubovoľne vybrať, ktoré uvádzajú, aby zahŕňala ďalšie šálku dovnútra

885
00:52:08,740 --> 00:52:11,320
Takže poďme rozdeliť tieto zoznamy.

886
00:52:12,420 --> 00:52:14,570
Teraz máme 2 zoznamy.

887
00:52:18,930 --> 00:52:20,930
Teraz máme 4 zoznamy.

888
00:52:25,730 --> 00:52:28,740
Teraz máme 8 zoznamov s jedným šálkou v každom zozname.

889
00:52:28,740 --> 00:52:31,520
Tak to je to v 1. kroku.

890
00:52:31,520 --> 00:52:37,280
Pre kroku 2 sme opakovane spojí dva zoznamy algoritmom zlúčenie sme sa naučili predtým.

891
00:52:37,280 --> 00:52:44,320
Zlúčenie 108 a 15 sme nakoniec s prehľadom 15, 108.

892
00:52:45,240 --> 00:52:51,330
Zlúčenie 50 a 4 skončíme s 4, 50.

893
00:52:51,330 --> 00:52:56,950
Zlúčenie 8 a 42 sme skončili s 8, 42.

894
00:52:57,790 --> 00:53:04,360
A zlúčenie 23 a 16 sme skončili s 16, 23.

895
00:53:04,360 --> 00:53:08,030
Teraz sú všetky naše zoznamy sú veľkosti 2.

896
00:53:08,030 --> 00:53:10,980
Všimnite si, že každý z 4 zoznamoch zoradené,

897
00:53:10,980 --> 00:53:14,230
takže môžeme začať zlúčením dvojice zoznamov znova.

898
00:53:14,230 --> 00:53:22,150
Zlúčenie 15 a 108 a 4 a 50 sme prvýkrát zobrať 4, potom 15,

899
00:53:22,150 --> 00:53:26,250
potom 50, potom 108.

900
00:53:26,250 --> 00:53:33,020
Zlúčenie 8, 42 a 16, 23 sme prvýkrát vziať 8, potom 16,

901
00:53:33,020 --> 00:53:37,170
potom 23, potom 42.

902
00:53:37,170 --> 00:53:42,490
Takže teraz máme len 2 zoznamy veľkosti 4, je zoradená z ktorých každý.

903
00:53:42,490 --> 00:53:45,940
Takže teraz sme zlúčiť tieto 2 zoznamy.

904
00:53:45,940 --> 00:53:54,230
Najprv vezmeme 4, potom vezmeme 8, potom vezmeme 15

905
00:53:54,230 --> 00:54:05,280
a 16 a 23 a 42 a 50 a 108.

906
00:54:05,280 --> 00:54:09,020
A sme hotoví. Teraz máme zoradený zoznam.

907
00:54:09,020 --> 00:54:13,740
>> Rob bol druh využitie niečoho, čo sme ešte neurobili.

908
00:54:13,740 --> 00:54:16,540
To bolo navrhol, ale my sme sa vlastne robiť to.

909
00:54:16,540 --> 00:54:19,230
Robil niečo fyzicky s poháre, ktoré naznačuje,

910
00:54:19,230 --> 00:54:23,680
trávil nejaký zdroj vedľa času. >> [Študent] Space. >> To bol priestor.

911
00:54:23,680 --> 00:54:27,360
Skutočnosť, že mal tento druh bi-úrovni stola, kde mal priestor až sem

912
00:54:27,360 --> 00:54:31,960
a priestor sa tu skutočne znamenať, že on je použitie dvakrát toľko miesta

913
00:54:31,960 --> 00:54:36,390
ako niektorý z našich algoritmov tak ďaleko - vloženie sort, bubble sort, alebo výber sort -

914
00:54:36,390 --> 00:54:40,780
ale on bol využitia tohto dodatočného priestoru pre druh sa veci pohli dopredu a dozadu

915
00:54:40,780 --> 00:54:42,600
pri zachovaní veci do poriadku.

916
00:54:42,600 --> 00:54:47,540
A aj keď je to pocit, ako by sme sa dostali na zoradený zoznam, ktorý cítil, ako by to trvalo dlho.

917
00:54:47,540 --> 00:54:51,060
V skutočnosti to, čo Rob robil, bolo presne to algoritmus.

918
00:54:51,060 --> 00:54:56,780
On najprv vzal problém veľkosti n, delí ju na ľavej polovici a pravej polovice.

919
00:54:56,780 --> 00:54:59,380
To je, keď sa presťahoval do šálok. Potom sa opakoval tento proces.

920
00:54:59,380 --> 00:55:03,390
Rozdelil 4 do 2 sady 2 tu a tu.

921
00:55:03,390 --> 00:55:08,520
Potom sa opakoval, že proces a delí 2 do 2 sady 1 pre každú z týchto rôznych pohárov.

922
00:55:08,520 --> 00:55:11,000
A to je miesto, kde geniálny naskytne príležitosť.

923
00:55:11,000 --> 00:55:15,840
V tomto bode príbehu, Rob mal 8 zoznamov veľkosti 1,

924
00:55:15,840 --> 00:55:18,860
z ktorých všetky boli zoradené už.

925
00:55:18,860 --> 00:55:20,630
>> Takže to, čo urobil pokračovať robiť?

926
00:55:20,630 --> 00:55:25,260
Pairwise vzal túto zoradený zoznam a túto zoradené zoznam a spojil ich.

927
00:55:25,260 --> 00:55:28,200
Potom vzal to a spojil ich, potom si to a spojil ich,

928
00:55:28,200 --> 00:55:30,670
potom jeden a spojil ich.

929
00:55:30,670 --> 00:55:32,390
A čo potom urobil ďalší?

930
00:55:32,390 --> 00:55:36,580
On potom re-sa spojil s väčšou zoznamy a potom re-sa spojil s väčšou zoznamy.

931
00:55:36,580 --> 00:55:41,170
A ak si myslíte, že o tom len intuitívne teraz, čo sa naozaj robí?

932
00:55:41,170 --> 00:55:45,450
Bol rozdelenie problému na polovicu, v polovici, na polovicu, v polovici

933
00:55:45,450 --> 00:55:47,600
aby sa tieto mimoriadne malý zoznamov.

934
00:55:47,600 --> 00:55:51,290
Potom bol láskavý kombinácia double, double, double, double.

935
00:55:51,290 --> 00:55:54,120
Takže on bol robil dvakrát toľko práce, ako sme videli doteraz

936
00:55:54,120 --> 00:55:56,930
s ničím zahŕňajúce rozdeľ a panuj, ale žiadny veľký problém.

937
00:55:56,930 --> 00:55:59,630
Dvakrát toľko práce nie je tak veľký problém. Je to len konštantný faktor.

938
00:55:59,630 --> 00:56:03,920
A podobne ako náš aritmetický výraz pred, ja len tak vyškrtnúť konštantné faktory

939
00:56:03,920 --> 00:56:10,170
ako vždy 2. Koho to zaujíma? Ak je to 2 miliardy krát 2, to je ešte veľa krokov.

940
00:56:10,170 --> 00:56:13,160
Takže to zlúčenie krok sa zdá byť kľúčový vhľad.

941
00:56:13,160 --> 00:56:17,000
Prejdime to len číselne pred - Oh, to nie je potrebné pokračovať ešte.

942
00:56:17,000 --> 00:56:22,890
Prejdime toto číselne, len aby skutočne vidieť, ako to dopadne.

943
00:56:22,890 --> 00:56:25,940
To je väčšinou len trochu chudáka animácie.

944
00:56:25,940 --> 00:56:27,750
Poďme navrhnúť túto.

945
00:56:27,750 --> 00:56:31,480
Doba chodu radiť zlúčenie - len je potrebné spôsob, ako hovoriť o tom.

946
00:56:31,480 --> 00:56:34,380
To nie je matematika, to je len trochu stručného spôsobu vyjadrovania.

947
00:56:34,380 --> 00:56:39,080
Takže T predstavuje čas a n predstavuje čo? >> [Študent] veľkosť -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] veľkosť problému, počet ľudí.

949
00:56:41,400 --> 00:56:45,470
Takže som tvrdil, že beží čas triediť n ľudí bude 0 množstvo času

950
00:56:45,470 --> 00:56:50,290
ak n je menší ako 2, pretože ak máte 1 šálku alebo šálky žiadne, budete mať čo triediť.

951
00:56:50,290 --> 00:56:55,160
Ale všeobecne, budem navrhovať, aby doba chodu triediť n prvkov

952
00:56:55,160 --> 00:56:59,350
bude čas to trvá radiť ľavú polovicu plus pravá polovica

953
00:56:59,350 --> 00:57:03,110
plus - Čo je to ďalší + n? >> [Študent] Merge sort.

954
00:57:03,110 --> 00:57:07,260
[Malan] Je to vlastne prelínajú, pretože ak máte n / 2 prvkov tu

955
00:57:07,260 --> 00:57:11,500
a máte n / 2 prvkov tu, koľko času trvá zlúčiť?

956
00:57:11,500 --> 00:57:15,050
Rovnako ako Rob, musíte trhať tento tu, možno trhať tu,

957
00:57:15,050 --> 00:57:17,120
trhať tu, trhať tu, trhať tu.

958
00:57:17,120 --> 00:57:19,400
Tie majú dotknúť každého z téglikov raz.

959
00:57:19,400 --> 00:57:22,030
A ak je 4 šálky plus 4 šálky, že je to 8 šálok

960
00:57:22,030 --> 00:57:25,200
alebo, všeobecnejšie, 8 n šálok.

961
00:57:25,200 --> 00:57:28,470
Takže zlúčenie krok, ktorý môžeme vyjadriť ako n,

962
00:57:28,470 --> 00:57:31,330
a že doslova zahŕňa koľkokrát Robert fyzicky dotkne

963
00:57:31,330 --> 00:57:33,410
jeden z tých polystyrénu pohárov.

964
00:57:33,410 --> 00:57:35,850
Takže poďme sa teraz urobiť ľubovoľný príklad.

965
00:57:35,850 --> 00:57:41,850
Ak je 16 šálok, čo je doba chodu radenia, používanie Robova algoritmus, 16 šálok?

966
00:57:41,850 --> 00:57:44,710
Je to 2 krát množstvo času, ktoré trvá triediť 8 šálok

967
00:57:44,710 --> 00:57:46,920
pretože máme 8 šálok tu, 8 šálok tu.

968
00:57:46,920 --> 00:57:51,520
Neviem, ako dlho to trvá, takže sme zobecňující ako T pre túto chvíľu.

969
00:57:51,520 --> 00:57:53,320
Kto vie, čo to je?

970
00:57:53,320 --> 00:57:58,990
Ale teraz môžem nejako rekurzívne alebo opakovane položiť rovnakú otázku.

971
00:57:58,990 --> 00:58:01,920
Koľko času zaberie triediť 8 šálok?

972
00:58:01,920 --> 00:58:07,030
8 šálok budem hovoriť trvá množstvo času to berie triediť 4 šálky plus 4 čaše,

973
00:58:07,030 --> 00:58:08,880
potom zlúči dohromady.

974
00:58:08,880 --> 00:58:13,080
Fine. Sme stále v cykle už. Ako dlho trvá, než si vybrať 4 šálky?

975
00:58:13,080 --> 00:58:19,150
Čas potrebný k radeniu 4 šálky je 2 šálky plus 2 šálky radenie plus zlúčenie procesu.

976
00:58:19,150 --> 00:58:21,440
Fine. Ako dlho trvá, než si vybrať 2 šálky?

977
00:58:21,440 --> 00:58:26,290
2 šálky je množstvo času, ktoré trvá triediť 1 šálka plus čas potrebný na radenie jeden šálka

978
00:58:26,290 --> 00:58:29,040
a množstvo času, ktoré trvá zlúčiť, čo je len 2.

979
00:58:29,040 --> 00:58:33,340
>> Fine. Posledná otázka. Ako dlho trvá, než si vybrať 1 šálku?

980
00:58:33,340 --> 00:58:37,260
Tu je základná pravda, že sme predpokladali by sme hit skôr.

981
00:58:37,260 --> 00:58:42,250
Skutočnosť, že to trvá žiadnu prácu vôbec triediť najmenší z problémov

982
00:58:42,250 --> 00:58:44,120
znamená, že teraz, druh škole štýlu,

983
00:58:44,120 --> 00:58:46,460
môžeme len tak začať zapojenie týchto čísel späť dovnútra

984
00:58:46,460 --> 00:58:50,630
Teraz vieme, čo T 1 je, a tak som si zapojiť 0 pre T z 1.

985
00:58:50,630 --> 00:58:54,420
To mi dá odpoveď na T 2, ktorý som potom môžete pripojiť vo vyšších poschodiach.

986
00:58:54,420 --> 00:58:56,930
To mi dá T 4, ktorý som si plug in vo vyšších poschodiach.

987
00:58:56,930 --> 00:58:58,920
To mi dá T 8, ktoré môžem pripájať aj vo väčšom up.

988
00:58:58,920 --> 00:59:04,330
A keď som vlastne robiť na to, že matematiku zapojením týchto odpovedí,

989
00:59:04,330 --> 00:59:08,590
Potom som si T z 16 je 64.

990
00:59:08,590 --> 00:59:12,090
A čo 64 predstavuje?

991
00:59:12,090 --> 00:59:15,700
Ak T je 16, jo, to je 16 krát 4.

992
00:59:15,700 --> 00:59:20,120
Tak som teraz tvrdí, že doba chodu tejto veci tzv zlúčenie druhu -

993
00:59:20,120 --> 00:59:22,590
a to sa bude najmódnejšie z tých, ktoré sme videli doteraz -

994
00:59:22,590 --> 00:59:26,160
sa bude nazývaný n log n

995
00:59:26,160 --> 00:59:31,140
pretože koľkokrát môže Rob rozdeliť veľa pohárov v polčase? Prihlásiť n

996
00:59:31,140 --> 00:59:34,370
Je to rovnaké, ako napríklad v telefónnom zozname, je to rovnaké ako self-počítanie napríklad.

997
00:59:34,370 --> 00:59:36,380
>> Koľkokrát môžete rozdeliť niečo na polovicu?

998
00:59:36,380 --> 00:59:38,410
Avšak, tam je to zlúčenie krok.

999
00:59:38,410 --> 00:59:42,920
Možno budete musieť rozdeliť šálky do polovice znovu a znovu a znovu,

1000
00:59:42,920 --> 00:59:45,640
ale zakaždým, keď budete musieť zlúčiť.

1001
00:59:45,640 --> 00:59:48,270
A my sme povedali už skôr, že zlúčenie n šálky berie n kroky

1002
00:59:48,270 --> 00:59:52,060
pretože budete musieť vytrhnúť šálka, vytrhnúť šálka, a vy budete musieť dotknúť každej šálky raz,

1003
00:59:52,060 --> 00:59:53,510
rovnako ako Rob urobil.

1004
00:59:53,510 --> 00:59:59,430
Takže ak robíme niečo protokol n krát a robíme n veci na každom z týchto iterácií,

1005
00:59:59,430 --> 01:00:03,090
každej z týchto halvings, máme n krát log n

1006
01:00:03,090 --> 01:00:07,220
Takže ak zapojíme do 16 v tomto príklade, 16 krát protokol o 16 -

1007
01:00:07,220 --> 01:00:10,600
nebojte sa o tom, prečo tomu tak je pre túto chvíľu, pretože som to nakreslil základňu -

1008
01:00:10,600 --> 01:00:16,100
ale log základu 2 16 je 4, 16 krát 4 je 64.

1009
01:00:16,100 --> 01:00:22,350
Ale naopak, ak sme použili bublina radenie alebo výber radenie alebo vloženie radenie s 16 číslami,

1010
01:00:22,350 --> 01:00:26,420
čo by sa tým doba chodu bolo, keby n je 16?

1011
01:00:26,420 --> 01:00:33,310
Bolo by 16 na druhú, čo je 256, ktorý aj keď sa úplne nasledovali všetky spočítal,

1012
01:00:33,310 --> 01:00:38,390
256 je väčší než 64. To je naozaj čarovný takeaway tu.

1013
01:00:38,390 --> 01:00:41,990
A uvedomiť si, že práca cez to v menších príkladoch, ako budete na PSet

1014
01:00:41,990 --> 01:00:44,260
je to všetko oveľa intuitívnejšie.

1015
01:00:44,260 --> 01:00:49,070
To však v skutočnosti znamená, pokiaľ ide o vzhľad tohto algoritmu je tento:

1016
01:00:49,070 --> 01:00:54,520
Ak sa skutočne pozrieť na druhu korešpondencie tu - dovoľte mi, aby som vytiahnite ju v tomto okne tu -

1017
01:00:54,520 --> 01:00:58,560
To je trochu iný príklad, keď máme všetky 3 z týchto algoritmov -

1018
01:00:58,560 --> 01:01:01,440
bublina, výber, a zlúčiť - len vedľa seba.

1019
01:01:01,440 --> 01:01:03,740
>> Majú všetko začalo s náhodnými bary, a to je dobre.

1020
01:01:03,740 --> 01:01:06,240
Nikto nemá zásadnú výhodu nad ostatnými.

1021
01:01:06,240 --> 01:01:09,500
Idem za chvíľu kliknite na každú z týchto animácií - Štart, Spustiť, Spustiť -

1022
01:01:09,500 --> 01:01:13,270
tak rýchlo, ako je to, aby si, hrubo, všetci začínajú na rovnakú dobu,

1023
01:01:13,270 --> 01:01:17,450
a uvažujme, že bublina radiť tieto horší prípad beží čas je to, čo? >> [Študent] N druhú.

1024
01:01:17,450 --> 01:01:21,560
N vzpriamil. Výberom Triediť najhorší prípad doby prevádzky je? N vzpriamil.

1025
01:01:21,560 --> 01:01:25,150
A merge sort je zrejme - aj keď nie úplne sledovať všetky matematiku teraz,

1026
01:01:25,150 --> 01:01:30,610
to bude stáť oveľa intuitívnejšie priebehu času - je, že sme tvrdí, n-krát log n

1027
01:01:30,610 --> 01:01:35,210
A pretože log n je ostro menší ako n, akonáhle budeme mať veľké množstvo,

1028
01:01:35,210 --> 01:01:40,230
n-krát log n je menšie ako časoch n n alebo n na druhú.

1029
01:01:40,230 --> 01:01:44,410
Takže to, čo to je, keď skutočne lepší algoritmus, pokiaľ ide o dobu prevádzky,

1030
01:01:44,410 --> 01:01:50,380
n-krát log n ako protichodný k n na druhú? Ideme na to. Kliknite na tlačidlo, cvak, cvak.

1031
01:01:55,690 --> 01:01:58,650
>> To je to, čo to znamená použiť niečo ako druh hromadnej korešpondencie.

1032
01:01:58,650 --> 01:02:01,680
Máme chvíľku. Poďme sa pozrieť, čo sa deje tu.

1033
01:02:09,440 --> 01:02:12,440
[Smiech] Čí peniaze na bubliny radiť?

1034
01:02:14,960 --> 01:02:16,730
To, závisí na vstupe niekedy.

1035
01:02:16,730 --> 01:02:18,120
Poďme sa pozrieť,.

1036
01:02:18,120 --> 01:02:23,320
Poď. Pripadá mi to ako, že to doháňa. >> [Študent] Choď, bublinková druh!

1037
01:02:23,320 --> 01:02:27,370
[Študenti reptania]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Jo, jo.

1039
01:02:29,120 --> 01:02:34,520
[Študenti reptania] Bež, bež, bež!

1040
01:02:37,210 --> 01:02:40,450
[Všetky jásající] [potlesk]

1041
01:02:40,450 --> 01:02:46,240
Takže teraz s 1 posledným, záverečnom demo, či je to trochu zložitejšie zabaliť svoju myseľ okolo matematiky

1042
01:02:46,240 --> 01:02:49,280
alebo druh vizualizácie tam, môžete skutočne počuť rýchlosti

1043
01:02:49,280 --> 01:02:51,000
rôznych algoritmov odlišne.

1044
01:02:51,000 --> 01:02:53,900
To je animácia niekto urobil, že skutočne združuje znie

1045
01:02:53,900 --> 01:02:56,980
s procesom odkladanie a výška stĺpcov.

1046
01:02:56,980 --> 01:03:00,440
Ako uvidíme, je tu ešte pár triedenia algoritmy, ktoré tam ľudia si mysleli.

1047
01:03:00,440 --> 01:03:03,660
To prvé, kto sa bude vloženie triediť, a to bude lietať

1048
01:03:03,660 --> 01:03:07,090
a dá vám počuteľné pocit ako tieto rôzne algoritmy pracujú.

1049
01:03:07,090 --> 01:03:09,080
Tu je vloženie sort.

1050
01:03:09,080 --> 01:03:18,410
[Elektronický pípanie]

1051
01:03:18,410 --> 01:03:20,730
[Malan] Bubble sort.

1052
01:03:20,730 --> 01:03:46,850
[Rýchlejšie elektronické pípanie]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Výber sort.

1054
01:03:48,950 --> 01:04:03,580
[Rýchlejšie elektronické pípanie]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Merge sort.

1056
01:04:05,770 --> 01:04:17,270
[Elektronický pípanie]

1057
01:04:17,270 --> 01:04:20,180
[Pípanie spomaľuje] [smiech]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome sort.

1059
01:04:22,590 --> 01:04:38,580
[Elektronický pípanie]

1060
01:04:39,740 --> 01:04:46,150
>> To je CS50. Uvidíme sa budúci týždeň. [Potlesk a jasot]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]