1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [3. nädal, Jätkub]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Harvardi Ülikool]

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

4
00:00:07,130 --> 00:00:11,010
>> Hea küll. Tere tulemast tagasi. See on CS50 ja see on lõpuks 3. nädal.

5
00:00:11,010 --> 00:00:14,680
>> Nii neile võõras, eelmisel aastal Harvardi käivitas mida nimetatakse Innovation Lab,

6
00:00:14,680 --> 00:00:18,530
või i-lab, mis on suurepärane hoone üle jõe edasi HBS ülikoolilinnak

7
00:00:18,530 --> 00:00:22,640
mis on avatud kolledži üliõpilased, GAPid õpilased, üliõpilased üle kogu ülikooli,

8
00:00:22,640 --> 00:00:27,000
sealhulgas õppejõud, ja see on koht, kus tulevad koos töötada uuenduslikke asju,

9
00:00:27,000 --> 00:00:29,180
eriti ettevõtliku asjad

10
00:00:29,180 --> 00:00:33,410
kui sina ja 0 või rohkem sõpru mõtled midagi ettevõtliku

11
00:00:33,410 --> 00:00:37,080
kas sel klass, pärast seda klassi või kaugemale.

12
00:00:37,080 --> 00:00:41,540
>> Nii et üks asju, mida nad teha üle J perspektiivis on need reisid,

13
00:00:41,540 --> 00:00:44,510
millest üks on New Yorki, millest üks on Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
Kosmos on väga piiratud, kuid see on võimalus läbi käima magistriõppes

15
00:00:47,530 --> 00:00:52,200
ja kraadiõppurid kogu campus ja tegelikult aega veeta nendes valdkondades

16
00:00:52,200 --> 00:00:55,500
jututoas kuni alustavatel, jututoas kuni ettevõtjaid jms.

17
00:00:55,500 --> 00:00:57,870
Nii et kui huvitatud, vaadake seda link siin.

18
00:00:57,870 --> 00:01:01,220
Samuti on saadaval slaidid internetis.

19
00:01:01,220 --> 00:01:04,610
>> Kas me pehmendama maja heli natuke?

20
00:01:04,610 --> 00:01:08,640
Kui soovid meiega liituda lõuna-sel reedel, 13:15 Fire & Ice, palun pea seal.

21
00:01:08,640 --> 00:01:11,390
Vabandused, kui vorm on juba täis selleks ajaks teil seal.

22
00:01:11,390 --> 00:01:13,750
Aga me jätkame seda traditsiooni edasi.

23
00:01:13,750 --> 00:01:17,350
>> Täna jätkame kõrgem arutelu erinevate probleemide, et saame lahendada,

24
00:01:17,350 --> 00:01:21,330
keskendudes märksa vähem, vähemalt täna edasi kood ja palju ideid.

25
00:01:21,330 --> 00:01:24,720
Nii et arvan, et tagasi nädal 0, kui me rebis telefoniraamatu pooleks,

26
00:01:24,720 --> 00:01:28,260
mille eesmärgiks oli teha midagi küll natuke dramaatiline

27
00:01:28,260 --> 00:01:32,360
kuid saata punkt, et otsing ei pea olema tingimata,

28
00:01:32,360 --> 00:01:35,100
kui selge, esimesel pilgul, kui võite arvata.

29
00:01:35,100 --> 00:01:40,200
Ja probleemide lahendamise üldiselt ei pruugi alati olla parim -

30
00:01:40,200 --> 00:01:44,130
Kõige loogilisem lahendus ei pruugi olla parim.

31
00:01:44,130 --> 00:01:47,300
Nii et meil oli see telefoniraamatust ja ausalt öeldes me kõik siin ruumis oli instinktid,

32
00:01:47,300 --> 00:01:51,470
kõige tõenäolisem, et alustada keskel otsides Mike Smith ja siis minna vasakule või paremale

33
00:01:51,470 --> 00:01:54,280
põhineb iganes täht me sattusin kohta.

34
00:01:54,280 --> 00:01:57,560
>> Aga see lihtne idee, et meie, inimesed on iseenesestmõistetav nii kaua

35
00:01:57,560 --> 00:02:00,670
tõesti peaks hakkama tulema esirinnas meelt

36
00:02:00,670 --> 00:02:03,900
sest probleemid saavad palju keerulisem kui telefoniraamatust

37
00:02:03,900 --> 00:02:07,420
samade lihtne, geniaalne arusaamu on see, mis hakkavad võimaldab meil

38
00:02:07,420 --> 00:02:10,259
lahendada palju keerulisem ja huvitavam probleeme,

39
00:02:10,259 --> 00:02:12,930
seas olid ka mõned asjad, mida me enesestmõistetavaks juba nendel päevadel.

40
00:02:12,930 --> 00:02:15,720
Miljardeid veebilehti seal, ja veel Google ja Bing jms

41
00:02:15,720 --> 00:02:17,660
on võimalik leida asju meile meeldib.

42
00:02:17,660 --> 00:02:22,300
Seda ei juhtu, kasutades lineaarset otsing, otsimine kõigi võimalike veebilehti.

43
00:02:22,300 --> 00:02:25,290
Facebook on võimalus öelda, kes kõik oma sõbrad on või sõprade sõbrad,

44
00:02:25,290 --> 00:02:28,250
ja et liiga saab teha näiliselt hetkega nendel päevadel

45
00:02:28,250 --> 00:02:30,820
kuigi neil on miljoneid kasutajaid.

46
00:02:30,820 --> 00:02:34,250
>> Ja nii kuidas me tegelikult lahendada probleeme, mis ulatus lõppkokkuvõttes vähendada

47
00:02:34,250 --> 00:02:37,830
Ideede me vaatasime nädal 0 ja veidi täna.

48
00:02:37,830 --> 00:02:42,320
Me ei uuesti sooritama seda algoritmi, kuid meenutavad me ka tegime nädal 0 Selle harjutuse

49
00:02:42,320 --> 00:02:44,780
kus olime kõik püsti, võtta number 1,

50
00:02:44,780 --> 00:02:48,720
ja siis me pidime kõik ise kokku sidumist ära, lisades oma arvud kokku,

51
00:02:48,720 --> 00:02:51,930
siis poole jõugu istus iga iteratsiooni.

52
00:02:51,930 --> 00:02:56,750
Nii et me läksime 500 õpilast 250-125 ja nii edasi.

53
00:02:56,750 --> 00:03:00,080
Aga kui me ütles esmaspäeval, võimas idee seal

54
00:03:00,080 --> 00:03:02,460
oli see, et kui me kahekordistunud suurus, et probleem

55
00:03:02,460 --> 00:03:06,480
ja kõik lapsed Kohtu või EÜ 10 tuli tuppa tagasi ja ühines meiega,

56
00:03:06,480 --> 00:03:09,510
Noh, me võiks ilmselt loota, et kogu kokku grupp

57
00:03:09,510 --> 00:03:13,380
vaid veel 1 suur iteratsiooni silmus, kuna need ainult võibolla kahekordistada

58
00:03:13,380 --> 00:03:15,630
või EÜ 10 juhtumit natuke rohkem kui kahekordistada.

59
00:03:15,630 --> 00:03:18,440
Ja nii me oleks kulutada natuke rohkem aega,

60
00:03:18,440 --> 00:03:22,000
kuid me ei pea kulutama 400 või 700 rohkem samme.

61
00:03:22,000 --> 00:03:26,550
>> Lihtsalt, et maalida seda pilti nii, et on natuke vähem abstraktset, ärme on kõik püsti.

62
00:03:26,550 --> 00:03:31,100
Aga kui neile, kes valis istuda orkester täna ei pahanda püsti,

63
00:03:31,100 --> 00:03:34,580
Vaatame, kas me saame aru teie seast, kes kõrgeim isik on

64
00:03:34,580 --> 00:03:36,730
tehes sama tüüpi võrdlev algoritm.

65
00:03:36,730 --> 00:03:41,830
Nii et kui sa istud orkester, minu vabandused, kuid 1. etapp, püsti;

66
00:03:41,830 --> 00:03:44,650
samm 2 paari maha kedagi lähedal teile,

67
00:03:44,650 --> 00:03:49,360
aru saada, kes on pikem ja istuda, kui olete lühem.

68
00:03:49,360 --> 00:03:51,360
Seejärel korrake.

69
00:03:51,360 --> 00:03:56,280
[Õpilased vulisev]

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

71
00:04:15,320 --> 00:04:19,010
Okei. Üks Seismise. Mis su nimi on? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, sa oled kõrgeim isik orkestri osa täna.

73
00:04:21,959 --> 00:04:28,100
>> Palju õnne. [Aplaus ja cheering] Okei. Istet. Nii leidsime Andrew.

74
00:04:28,100 --> 00:04:30,870
Aga kui kaua see on võtnud mind näiteks leida Andrew

75
00:04:30,870 --> 00:04:33,740
Selles orkester osa 50 + või nii inimesi?

76
00:04:33,740 --> 00:04:36,900
Ma oleks võinud üsna lihtne lähenemine ja alustada siin.

77
00:04:36,900 --> 00:04:39,270
Ja ma olen 2 inimest püsti ja ma lihtsalt neid võrrelda,

78
00:04:39,270 --> 00:04:42,120
ja siis ma ütlen kes on veidi lühem, "Olgu, sa istuda,"

79
00:04:42,120 --> 00:04:44,380
ja ma lähen mäleta kes kõrgemaks isik oli.

80
00:04:44,380 --> 00:04:49,030
Siis ma kordan, kordan, kordan, ja ma kinni hoida kõrgeim inimene

81
00:04:49,030 --> 00:04:51,920
kuni leian kellegi veidi pikem kui neid, kus punkt

82
00:04:51,920 --> 00:04:54,950
veidi lühem inimene peab siis istuma.

83
00:04:54,950 --> 00:04:57,690
Aga et algoritm selle orkestri osa, kui seal on n sind,

84
00:04:57,690 --> 00:05:00,480
kui palju samme on, et algoritm aega võtab? >> [Üliõpilane] N.

85
00:05:00,480 --> 00:05:03,580
>> See vőtab n, eks, sest halvimal juhul, kui nii võib öelda,

86
00:05:03,580 --> 00:05:09,090
kõrgeim isik on kõige viimane inimene, et ma saan lihtsalt juhuslik ebaõnn.

87
00:05:09,090 --> 00:05:14,260
Nii et halvimal juhul, sõiduaega, et algoritm on lineaarne, see on n

88
00:05:14,260 --> 00:05:18,070
kus n on inimeste koguarv ruumis, suuruse probleem.

89
00:05:18,070 --> 00:05:19,600
Aga see algoritm?

90
00:05:19,600 --> 00:05:22,080
Asjaolu, et te kõik püsti ja siis jälle pool istusid maha,

91
00:05:22,080 --> 00:05:23,950
pool istusid maha, pool istusid maha.

92
00:05:23,950 --> 00:05:26,070
Mitu sammu peaks, et on võtnud, kas seal on n sa siin oled?

93
00:05:26,070 --> 00:05:30,200
[Üliõpilane] N log n. >> See oleks hullem. Logi n.

94
00:05:30,200 --> 00:05:32,930
>> Nii log n, isegi kui te ei mäleta, mida logaritm on,

95
00:05:32,930 --> 00:05:38,410
Praegu lihtsalt aru, et see on seotud kuidagi selle poole võrra ja vähendada poole võrra ja vähendada poole võrra.

96
00:05:38,410 --> 00:05:41,000
See ei pea olema 2 korda. See võib olla tegur 3.

97
00:05:41,000 --> 00:05:46,560
Aga see on see kordamine samasugune tegur, nii et probleemi ulatust algab siit

98
00:05:46,560 --> 00:05:49,620
aga siis kohe läheb siia, siis siia, siis siia, siis siia.

99
00:05:49,620 --> 00:05:53,580
Sa ei vii väike hammustused välja probleem, sa oled tõesti tükeldamine ära seda

100
00:05:53,580 --> 00:05:56,160
suure hoobiga iga kord.

101
00:05:56,160 --> 00:06:00,810
Seega oli meil 50 inimest, siis 25, siis 12 ½ või 13 seisvat inimest,

102
00:06:00,810 --> 00:06:05,370
siis 6 ½ ja nii edasi kuni lõpuks lihtsalt Andrew jäi seisma.

103
00:06:05,370 --> 00:06:08,710
Nii et me ei kavatse helistada, et samamoodi n, ja saate visualiseerida seda järgmiselt.

104
00:06:08,710 --> 00:06:12,570
Meenuta seda pilti siin, kus lineaarne algoritm on nagu punane joon seal,

105
00:06:12,570 --> 00:06:17,520
kollane joon oli loendamise teel 2s algoritm, mida me kasutada lugedes üliõpilastele

106
00:06:17,520 --> 00:06:22,300
minevikus, kuid täna Püha Graal läheb jätkuvalt see roheline joon

107
00:06:22,300 --> 00:06:25,470
kus kui me kahekordistunud inimeste arv orkester lõik või lihtsalt ütles,

108
00:06:25,470 --> 00:06:29,170
kurat, ajame igaüks kogu tuba püsti, mitte nii suur asi

109
00:06:29,170 --> 00:06:31,560
sest me ligikaudu kahekordistavad kui palju inimesi on siin all,

110
00:06:31,560 --> 00:06:33,500
Veel 1 iteratsiooni, pole probleemi.

111
00:06:33,500 --> 00:06:36,200
>> Leidsime Andrew või kes iganes juhtub olema pikem kui Andrew

112
00:06:36,200 --> 00:06:38,770
aastal mezzanine või rõdu.

113
00:06:38,770 --> 00:06:42,140
Nii et see lihtne idee, et me võtsime nii palju antud telefoniraamatust

114
00:06:42,140 --> 00:06:46,170
aru, et seal on nii palju erinevaid kohti, kus saame rakendada seda.

115
00:06:46,170 --> 00:06:50,810
Lihtsalt laksu mõned kõnepruugis - tegelikult, mitte žargooni esimene,

116
00:06:50,810 --> 00:06:52,750
Lubage mul minna seda pilti siin.

117
00:06:52,750 --> 00:06:56,970
Praegu me rääkisime n ja n / 2 ja seejärel logige n,

118
00:06:56,970 --> 00:07:00,500
kuid me kindlasti tulla, nagu me jooksul semestri

119
00:07:00,500 --> 00:07:05,130
muud sorti matemaatiliste valemite kirjeldamiseks selle üldise mõiste sõiduaega.

120
00:07:05,130 --> 00:07:07,580
Need on kontekstist välja nüüd, sest me näeme varsti

121
00:07:07,580 --> 00:07:09,900
algoritme, et need tegelikult esindavad.

122
00:07:09,900 --> 00:07:17,990
>> Aga märkate siin sirgjoonena n, sirge, on tegelikult väga madal osutades kohe.

123
00:07:17,990 --> 00:07:22,950
See on omamoodi optiline illusioon, et me lihtsalt muuta seda, mis x telg tähistab

124
00:07:22,950 --> 00:07:26,130
ja y-telg, ja saame sirge punkt igas suunas me tahame.

125
00:07:26,130 --> 00:07:30,350
Aga sellepärast, et see on nii näiliselt korter nüüd

126
00:07:30,350 --> 00:07:35,690
sest meil oli vaja teha ruumi selle graafik palju aeglasem töötab korda.

127
00:07:35,690 --> 00:07:39,030
Praegu teame, et seal on päris halb algoritme elu,

128
00:07:39,030 --> 00:07:43,790
millest mõned ei võta n samme või, veel parem, log n samme, kuid rohkem.

129
00:07:43,790 --> 00:07:48,820
Nii rea peal n siin allosas teate seal on n korda log n,

130
00:07:48,820 --> 00:07:51,410
ja me näeme, mida see tähendab enne pikk.

131
00:07:51,410 --> 00:07:56,010
Üle et on n ruudus, ja me ei ole näinud ühtegi n ruudus algoritme, kuid me parasjagu.

132
00:07:56,010 --> 00:07:57,660
Ja see näeb tõesti halb.

133
00:07:57,660 --> 00:08:01,610
Seal on 2 kuni n, midagi kordades, mis tundub isegi hullem.

134
00:08:01,610 --> 00:08:05,760
Ja veel, kummaliselt, siis seal on n kuubis, mis, kui sa oled omamoodi mõtlemine,

135
00:08:05,760 --> 00:08:10,000
kui sa selline ei matemaatikat, 2 n tegelikult muutub palju sirgemalt,

136
00:08:10,000 --> 00:08:15,930
palju kõrgemal kui n kuubis, kui te vaatate kirved piisavalt kaugele.

137
00:08:15,930 --> 00:08:19,890
Nii märkate kohe need teljed on omavoliliselt 2-10 x-teljel.

138
00:08:19,890 --> 00:08:21,770
>> Ja mida see tähendab?

139
00:08:21,770 --> 00:08:23,890
See tähendab, et 2 inimest 10 inimest toas.

140
00:08:23,890 --> 00:08:27,200
See on kõik x tähendab: suurus probleem, mis iganes kontekstis on.

141
00:08:27,200 --> 00:08:30,420
Ja vertikaalteljel praegu on sekundite arvu või sammude arv -

142
00:08:30,420 --> 00:08:31,840
mõned ajaühiku.

143
00:08:31,840 --> 00:08:34,740
Aga teate, et see on 0-60 ja 0-10.

144
00:08:34,740 --> 00:08:38,549
Aga kui me mingi zoom out, nagu te võite Exceli või mõne aktsiagraafikud tarkvara,

145
00:08:38,549 --> 00:08:43,370
ja me läheme kuni 200000, märkate, et midagi 2 n

146
00:08:43,370 --> 00:08:47,520
läheb täiesti uputama töötab korda n ruudus,

147
00:08:47,520 --> 00:08:50,960
n kuubis, n log n - kõik me rääkisime siiani.

148
00:08:50,960 --> 00:08:54,190
Ja veel saak on siis, kui hakkame rääkima asjadest nagu Facebook

149
00:08:54,190 --> 00:08:57,150
kus sul on palju, palju, palju inimesi kõik omavahel seotud,

150
00:08:57,150 --> 00:09:00,650
olete n inimesed, kellest igaüks võib olla nii palju kui n sõbrad

151
00:09:00,650 --> 00:09:02,860
kui kõik on omamoodi semu-semu maailmas,

152
00:09:02,860 --> 00:09:08,100
noh, see on n korda n juba, nii et N-ruuduline võimalik sõprus,

153
00:09:08,100 --> 00:09:10,950
vähemalt 1 suunas, n ruudus võimalik sõprussuhteid.

154
00:09:10,950 --> 00:09:15,330
Nii et juba näitab, et otsida Facebook sotsiaalne graafik, nii et rääkida,

155
00:09:15,330 --> 00:09:18,090
saab alustada tuleb väljendada selliseid valemeid.

156
00:09:18,090 --> 00:09:19,820
>> Me tuleme tagasi ja muuta see palju konkreetsem,

157
00:09:19,820 --> 00:09:23,280
kuid nüüd, eesmärk järgmise mitu nädalat

158
00:09:23,280 --> 00:09:27,170
läheb kindlasti mitte minna rakendamisel algoritme või kood

159
00:09:27,170 --> 00:09:29,870
et lõpuks võtta nii palju aega kui midagi sellist.

160
00:09:29,870 --> 00:09:33,110
Aga põnev asi arvutiteadus, kui te jätkate edasi selles valdkonnas

161
00:09:33,110 --> 00:09:38,320
võttes klasside nagu CS121, CS124, mis mõlemad on teooria kursused,

162
00:09:38,320 --> 00:09:41,300
et tegemist on tegelikult mõningaid probleeme, mis eksisteerivad siin maailmas

163
00:09:41,300 --> 00:09:45,710
et põhimõtteliselt, nii palju kui me teame, mida ei saa lahendada kõik kiiremini

164
00:09:45,710 --> 00:09:48,880
kui halvim neist graafikud tegelikult teeb.

165
00:09:48,880 --> 00:09:53,660
Nii et seal on palju avatud probleemid selles maailmas teha palju parem kui inimestel on siiani.

166
00:09:53,660 --> 00:09:56,130
>> Nii alustame siis selle näite.

167
00:09:56,130 --> 00:09:59,650
Nägime Sean võitlevad selle kaamera, kõik liiga kohmakalt video.

168
00:09:59,650 --> 00:10:05,270
Aga reaalsus oli see, kui Sean ülesanne oli leida lauale nagu see number 7,

169
00:10:05,270 --> 00:10:10,300
meelde tuletada, et ma ütlesin, et "Siin on kusagil taga paberitükke või valge uksed

170
00:10:10,300 --> 00:10:12,570
"Number 7. Sean, leida see meie jaoks."

171
00:10:12,570 --> 00:10:14,200
Ja see oli imeliselt ebamugav vaadata

172
00:10:14,200 --> 00:10:15,790
sest ta oli tõesti hädas selle probleemiga.

173
00:10:15,790 --> 00:10:19,720
Aga tegelikkus oli Sean tegi samuti keegi ruumis oleks võinud teha.

174
00:10:19,720 --> 00:10:21,890
Ta võttis natuke kauem kui tavaline inimene võib olla,

175
00:10:21,890 --> 00:10:24,760
kuid ta oletas, et seal oli mõned trikk seda probleemi,

176
00:10:24,760 --> 00:10:26,590
ta eeldada, et ta oli midagi puudu.

177
00:10:26,590 --> 00:10:29,320
Ja see ei aita, et sajad silmad olid pidades alla teda.

178
00:10:29,320 --> 00:10:34,250
>> Aga tegelikkus oli kui sisendi probleem on hunnik juhusliku numbrite

179
00:10:34,250 --> 00:10:37,120
ja sa palutakse leida 1 selline number,

180
00:10:37,120 --> 00:10:39,770
Parim, mida saate teha on lineaarne otsing.

181
00:10:39,770 --> 00:10:44,060
Start vasakul, liiguta paremale, või alustada õigel, liiguta vasakule.

182
00:10:44,060 --> 00:10:48,300
Tagasiulatuvalt, võiksime mõelda, "Sean, miks sa ei lihtsalt alustada teisest otsast?"

183
00:10:48,300 --> 00:10:52,120
Noh, 7 oleks võinud sama hästi siin olnud juhuslikult,

184
00:10:52,120 --> 00:10:54,980
kuid ma teadlikult selle sinna pani, sest ma arvasin, et ta ei kavatse alustada aasta lõpus.

185
00:10:54,980 --> 00:10:59,320
Nii et ma selline manipuleerida olukorda, vaid juhuslik kokkusattumus 7 oleks võinud kuhugi.

186
00:10:59,320 --> 00:11:02,380
Nii algab õige lõpp oleks võinud olla parem siis,

187
00:11:02,380 --> 00:11:04,320
Aga kui järgmisel aastal ma liikuda 7 mujal?

188
00:11:04,320 --> 00:11:06,830
See ei ole täiesti uus lahendus -

189
00:11:06,830 --> 00:11:10,520
alates 1. lõpus või muu - kui olete andnud mingit muud eeldused.

190
00:11:10,520 --> 00:11:13,620
Nii Sean hakkas otsima läbi numbrid ja ta ütles: "5. See pole siin."

191
00:11:13,620 --> 00:11:17,280
Siis läks ta siin ja nägin 19, siis ta peatus umbes 20 sekundit,

192
00:11:17,280 --> 00:11:22,330
siis ta avas selle eest 13, ja siis selgus,

193
00:11:22,330 --> 00:11:24,270
et seal ei tundu olevat muster siin.

194
00:11:24,270 --> 00:11:28,090
See ei olnud 1, 2, 3, 4 või nagu. Seal olid lüngad numbrid, mis ei aidanud.

195
00:11:28,090 --> 00:11:32,320
Ja ka seda, et olen kasutanud neid odavaid paberitükke varjata numbrid

196
00:11:32,320 --> 00:11:35,270
on tegelikult tahtlik, sest kui ma eemaldada kõik need paberitükid,

197
00:11:35,270 --> 00:11:38,760
Enamikule meist, Sean lisada, oleks arvatavasti vaatas omamoodi makroskoopiliselt

198
00:11:38,760 --> 00:11:43,410
kell tahvli juurde ja ütles: "Oh, 7 on ilmselt seal." Me tegime seda koheselt.

199
00:11:43,410 --> 00:11:46,460
>> Ja mis võiks olla, kuidas inimese aju töötab mingil määral

200
00:11:46,460 --> 00:11:50,730
kuid tegelikkuses ta silmad või mõistus oli ilmselt koorides numbrid paremalt vasakule,

201
00:11:50,730 --> 00:11:55,190
vasakult paremale, keskele kohta välja - midagi toimub füsioloogiliselt

202
00:11:55,190 --> 00:11:57,640
nii et tundus nagu see juhtus koheselt,

203
00:11:57,640 --> 00:12:01,360
kuid koefitsendid on isegi sees oli mingi metoodika leidmisel 7.

204
00:12:01,360 --> 00:12:05,160
Ja tõepoolest, nüüd me räägime massiivid ja andmestruktuurid

205
00:12:05,160 --> 00:12:08,780
ja mälu sees arvuti, ainus asi, mida inimesed saavad teha

206
00:12:08,780 --> 00:12:13,070
on vaadata individuaalse mälu kohale 1 korraga.

207
00:12:13,070 --> 00:12:16,600
>> Nii et iga teine ​​asukoht võib samuti olla kaetud mõne paberitüki

208
00:12:16,600 --> 00:12:21,170
sest me ei näe seda niikuinii. Me teha ainult 1 asi korraga.

209
00:12:21,170 --> 00:12:25,030
Nii et antud juhul on Seani juhtum, käisime siin ja siis läksime siin

210
00:12:25,030 --> 00:12:31,040
ja siis läksime siin, siin, siin, siin, sain targad lõpuks

211
00:12:31,040 --> 00:12:34,450
ja just selline vahele see meelevaldselt ja leidis 7 seal.

212
00:12:34,450 --> 00:12:37,470
See üks ei olnud eriti eriline. See liiga oli rikkis.

213
00:12:37,470 --> 00:12:39,530
Aga ta lõpuks leidis 7.

214
00:12:39,530 --> 00:12:45,360
Aga nüüd Buffee tõesti, et parim, mida saate teha, kui anta teavet

215
00:12:45,360 --> 00:12:50,400
muud kui juhuslikult järjestatud numbrid on alustada vasakult või alustada paremalt.

216
00:12:50,400 --> 00:12:54,950
Või kuradit, te võite juhuslikult avada uksi, kuid isegi siis mida see tähendab olla juhuslik?

217
00:12:54,950 --> 00:12:57,220
Noh, me tahaks olla kuidagi vormistama mida tähendab alustada siin,

218
00:12:57,220 --> 00:13:01,150
siis minna siin, siis minge siia. Sean tegi suur, ja see oli lihtsalt lõbus vaadata.

219
00:13:01,150 --> 00:13:06,340
Mis siis, kui selle asemel muudame probleemi natuke ja avab tänavusel Sean, kui soovite?

220
00:13:06,340 --> 00:13:09,460
Kas keegi on mugav tulevad lavale ja lahendada veidi teistsugune probleem

221
00:13:09,460 --> 00:13:12,330
ja ilmuvad kaamera?

222
00:13:12,330 --> 00:13:15,720
>> Lähme üle orkestri sest kutid on üsna kaasatud täna juba.

223
00:13:15,720 --> 00:13:21,430
Kuidas on roosa, on müts? Tule alla. Mis su nimi on? >> Alex. >> Alex. Okei.

224
00:13:21,430 --> 00:13:24,580
Nii et Alex on tänavuse Sean ja ilmuvad järgmise mitu aastat

225
00:13:24,580 --> 00:13:27,770
väärtuses CS50 loenguid.

226
00:13:27,770 --> 00:13:30,340
Alex, meeldiv tutvuda. >> Meeldiv kohtuda ka.

227
00:13:30,340 --> 00:13:33,470
Väljakutse käepärast teile, et teil on see natuke lihtsam

228
00:13:33,470 --> 00:13:38,950
aastal, et ma ütlen sulle sama numbrid on siin, kuid nad on nüüd järjestatud.

229
00:13:38,950 --> 00:13:41,800
Nii et nüüd teie eesmärgiks on leida number 7.

230
00:13:41,800 --> 00:13:45,370
Ja tegelikult peaksime tõesti tegema seda - sa oled selline petmine, nagu arvuti ei oleks,

231
00:13:45,370 --> 00:13:47,990
vaadates mida numbrid olid hetk tagasi.

232
00:13:47,990 --> 00:13:50,360
Kriidiga see tegelikult ei aita kõik, et palju,

233
00:13:50,360 --> 00:13:52,810
aga oletame, et sa ei tea, mida algne massiiv on.

234
00:13:52,810 --> 00:13:56,600
Kõik te teate nüüd, et teil on hulgaliselt järjestatud numbrite

235
00:13:56,600 --> 00:14:00,360
millel võib olla lünki nende vahel, ja teie eesmärk on leida number 7.

236
00:14:00,360 --> 00:14:05,080
Kuidas te, mõistlik inimene, minna leida number 7?

237
00:14:05,080 --> 00:14:07,770
>> Mine madala kuni kõrge? >> Okei. Mine madal või kõrge.

238
00:14:07,770 --> 00:14:10,990
Ja ärge rebige need ära. Lihtsalt tõstke nad üles, et saaksime neid taaskasutada.

239
00:14:10,990 --> 00:14:14,730
Okei, nii et 1. Oota. Enne kui jätkame, et oli 1, selgelt vale.

240
00:14:14,730 --> 00:14:17,270
Nii, mis toimub teie peast läbi järgmine? Milline on sinu järgmine käik?

241
00:14:17,270 --> 00:14:23,250
Järgmise üks. >> Okei. Järgmise üks. Hea. 3, nii vale. Milline on sinu järgmine käik?

242
00:14:23,250 --> 00:14:27,670
Lase edasi. >> Olgu. Lase edasi. 5.

243
00:14:27,670 --> 00:14:31,110
Nii hoida läheb, ja andke mulle käe see tulevaste põlvede jaoks.

244
00:14:31,110 --> 00:14:35,720
7. >> Suurepärane. Väga hea. Leitud number 7. [Aplaus]

245
00:14:35,720 --> 00:14:39,720
Nii et oli hea, kuid Sean liiga leitud number 7.

246
00:14:39,720 --> 00:14:44,490
Ja ma väita, et sa ei ole tõesti ära selle täiendava osa teabest,

247
00:14:44,490 --> 00:14:47,780
mis on see, et need numbrid on järjestatud.

248
00:14:47,780 --> 00:14:51,520
Nii et me saame teha paremini? Kõik ettepanekud siia? Jah, tagasi.

249
00:14:51,520 --> 00:14:54,710
[Üliõpilane] Binary otsing. >> Ma ei tea, mida Kahendotsingupuu on.

250
00:14:54,710 --> 00:14:58,030
>> [Üliõpilane] Start keskel. >> Alusta keskel. Okei. Nii et vaatame, kas saame seal.

251
00:14:58,030 --> 00:15:02,580
Nii et kui selle asemel sulle öeldakse algus keskelt, edasi minna ja avada keset uks.

252
00:15:02,580 --> 00:15:04,580
Seal on 8 neist, et sa lähed on suvaliselt valida üks

253
00:15:04,580 --> 00:15:09,800
veidi vasakule või paremale. Okei. 7! [Aplaus] Väga kena.

254
00:15:09,800 --> 00:15:11,410
Okei, aga kus me siis seda?

255
00:15:11,410 --> 00:15:14,990
Oletame lihtsalt, et murda viik sa hakkasid siin

256
00:15:14,990 --> 00:15:16,670
sest et võrdselt oleks võinud juhtuda ka.

257
00:15:16,670 --> 00:15:19,540
Me lihtsalt juhtus tean, et 7 oli seal. Nii et see on 13.

258
00:15:19,540 --> 00:15:21,980
Nii et kui nad järjestatud ja me lihtsalt hakkas keset,

259
00:15:21,980 --> 00:15:24,600
milline oleks optimaalne järgmine käik on olnud?

260
00:15:24,600 --> 00:15:27,740
Mine vasakule. Ja nii siin tuleb telefoniraamat näiteks uuesti.

261
00:15:27,740 --> 00:15:30,130
Kui 13 on siin ja me teame nimekirja sorteeritakse,

262
00:15:30,130 --> 00:15:33,900
siis kõik need paberitükid on ebahuvitav meile nüüd

263
00:15:33,900 --> 00:15:37,400
sest me juba teame, et 7 tuleb vasakule

264
00:15:37,400 --> 00:15:39,510
Kui need numbrid on järjestatud ja leidsime 13.

265
00:15:39,510 --> 00:15:42,500
>> Mis su järgmine käik siin? >> Mine vasakule. >> Olgu, hästi.

266
00:15:42,500 --> 00:15:45,080
Nii et mine vasakule, ja - oota, hei, hei, hei. See on petmine.

267
00:15:47,140 --> 00:15:51,350
Nii et sa leidsid 7, kuid mis oli algoritm me lihtsalt rakendada?

268
00:15:51,350 --> 00:15:56,450
Alusta keskel. >> Hea. Mis siis loogiline jätk, et sama mõte?

269
00:15:56,450 --> 00:15:58,970
Oh, just need. >> Täpselt. >> Nii et ma hakkan siin. >> Hea.

270
00:15:58,970 --> 00:16:02,020
Nii et nüüd me läksime veidi vasakule uuesti. See on 3.

271
00:16:02,020 --> 00:16:05,310
Aga huvitav Buffee nüüd on Millist sa ei pea hooli?

272
00:16:05,310 --> 00:16:08,040
Need 2. >> Need 2. Nüüd see võib ära minna, see võib ära minna.

273
00:16:08,040 --> 00:16:12,330
Nüüd probleem, et oli 8 siis oli suurus 4 nüüd on suurus 2.

274
00:16:12,330 --> 00:16:16,430
Me saame üsna lähedal. Jällegi minna keset neid 2 elementi.

275
00:16:16,430 --> 00:16:20,430
>> Okei. Nii et see on omamoodi kahju, et nüüd oleme alati läheb vasakule, sest me oleme allapoole.

276
00:16:20,430 --> 00:16:25,150
Aga sellest pole midagi, sest nüüd me viskame selle ära ja kõik muu, jättes meile vaid 7.

277
00:16:25,150 --> 00:16:30,490
Anname aplausi. Leidsime 7 uuesti. [Aplaus] Okei. Muidugi.

278
00:16:30,490 --> 00:16:32,220
Oota vaid veel 1 sekund.

279
00:16:32,220 --> 00:16:36,630
Isegi kui see järgmise protsessi liiki võttis natuke kauem, kui me arvasin, et see,

280
00:16:36,630 --> 00:16:40,150
ausalt öeldes, teie esimene instinkt oli parim, eks? Leidsime 7 silmapilkselt.

281
00:16:40,150 --> 00:16:46,740
Aga oleksime leidis 7 kiiremini, ükskõik mida, selles näites võrreldes selle ühe

282
00:16:46,740 --> 00:16:50,100
sest kui numbrid on kõik järjestatud meelega lehekülgi telefoniraamatust

283
00:16:50,100 --> 00:16:54,580
saate tõepoolest tükelda pool probleem jälle ja jälle ja jälle.

284
00:16:54,580 --> 00:16:56,740
Ja see ei ole päris nii lihtne, et näha seda vaid 8 numbrid

285
00:16:56,740 --> 00:17:00,100
erinevalt 1000-leheküljeline telefoniraamatust kui sa tõesti seda näha visuaalselt,

286
00:17:00,100 --> 00:17:03,120
kuid sel juhul, kui Sean otsisin 7,

287
00:17:03,120 --> 00:17:06,020
kui palju samme halvimal juhul oleks ta pidanud teda? >> [Üliõpilane] 7.

288
00:17:06,020 --> 00:17:11,670
7 halvimal juhul. Noh, halvimal juhul ei 7, kui seal on 8 uksed siin.

289
00:17:11,670 --> 00:17:13,440
Oleks pidanud teda 8 astet.

290
00:17:13,440 --> 00:17:18,170
>> Nii et kui seal on n uste, see võis võtta Sean paar aastat tagasi n samme.

291
00:17:18,170 --> 00:17:21,520
Nüüd, teie puhul, Alex, arvestades, et need numbrid on järjestatud -

292
00:17:21,520 --> 00:17:25,130
ja me saame mingi järeldavad seda, kust me oleme seni selles loos -

293
00:17:25,130 --> 00:17:28,300
Mis töötamise aega Alexi arukam algoritm

294
00:17:28,300 --> 00:17:30,770
alustades keskelt ja seejärel korrata?

295
00:17:30,770 --> 00:17:36,490
[Üliõpilane] 3. >> Nii et see saab olema 3 umbes nii, kui sa minna 8-4 2-1.

296
00:17:36,490 --> 00:17:40,660
Nii et 3 sammu või üldisemalt, see on log n uuesti.

297
00:17:40,660 --> 00:17:43,380
Iga kord, kui sa poole võrra ja vähendada poole võrra ja vähendada poole võrra ja vähendada poole võrra,

298
00:17:43,380 --> 00:17:45,290
see väljendus see idee log n.

299
00:17:45,290 --> 00:17:48,140
Ja nii, et oleks võtnud sul on ainult 3 astet ning ta tõepoolest tegi

300
00:17:48,140 --> 00:17:50,890
kui avasime uksed vähendamine poole võrra ja vähendada poole võrra,

301
00:17:50,890 --> 00:17:53,770
arvestades, et see oleks võtnud Sean umbes 7 või 8 astet.

302
00:17:53,770 --> 00:17:56,330
Nii et tänan teid, et olete koos meiega sel aastal. >> Tänan teid. Oli meeldiv kohtuda.

303
00:17:56,330 --> 00:18:00,170
Täname Alex. >> Samuti. [Aplaus]

304
00:18:00,170 --> 00:18:02,150
>> Mis on siis tõeline tähendus on?

305
00:18:02,150 --> 00:18:06,050
Nüüd kujutage ette, et see ei ole 8 uksed, mis ausalt öeldes kõik meist võiks leida midagi

306
00:18:06,050 --> 00:18:10,430
taga 8 uksed päris kiiresti lihtsalt rebimine paberitükke ja läheb koos oma instinkte.

307
00:18:10,430 --> 00:18:14,430
Aga kui see on miljonit uksed? Mis siis, kui see on 4000000000 uksed?

308
00:18:14,430 --> 00:18:19,630
Juhul 4 miljardit uksed, sa tõesti tahad minna koos Alexi algoritm,

309
00:18:19,630 --> 00:18:23,150
Kahendotsingupuu kui hakkame nimetades seda või jaga ja valitse üldisemalt

310
00:18:23,150 --> 00:18:25,220
kus hoiate poole võrra ja vähendada poole võrra probleem,

311
00:18:25,220 --> 00:18:30,510
sest kui sul on 4000000000 uksed, mitu korda saate karbonaad 4 miljardi pool?

312
00:18:30,510 --> 00:18:33,870
[Üliõpilane] 32. >> See on tegelikult 32. Võite töötada selle läbi paberilehele või oma peaga.

313
00:18:33,870 --> 00:18:38,490
Lähed 4000000000-2000000000 to 1 miljardi pool miljardit, 250 miljonit eurot, dot, dot, dot.

314
00:18:38,490 --> 00:18:41,620
Ja kui sa läbi matemaatika, sa lähed tõesti saada 32,

315
00:18:41,620 --> 00:18:44,950
ja et tegelikult on seotud arvuti teadust, sest me tavaliselt arvatakse 2 astmed.

316
00:18:44,950 --> 00:18:47,600
2 32 juhtub olema 4 miljardit eurot.

317
00:18:47,600 --> 00:18:51,440
Nii et seal on palju tähtsust selliseid volitusi 2 arvutiteadus.

318
00:18:51,440 --> 00:18:55,120
>> Aga mis umbes 8 miljardit? Mitu sammu on, et aega võtab, kui on 8000000000 uksed?

319
00:18:55,120 --> 00:19:00,350
[Üliõpilane] 33. >> Nii et 33. Mis siis, kui seal on 16000000000 uksed? Mitu sammu on, et aega võtab?

320
00:19:00,350 --> 00:19:05,020
[Üliõpilane] 34. >> 34. Võiksime liiki jätkata seda küllastumise. Aga see on võimas asi.

321
00:19:05,020 --> 00:19:09,430
Võite tutvustada miljardeid rohkem sisendeid oma probleemile, kuid pole hullu,

322
00:19:09,430 --> 00:19:14,140
sa lihtsalt võtta 1 täiendav hammustada välja ja seega annab meile midagi binaarne otsing

323
00:19:14,140 --> 00:19:15,920
või jaga ja valitse üldisemalt.

324
00:19:15,920 --> 00:19:17,990
Aga ma olen selline petmine siin, eks?

325
00:19:17,990 --> 00:19:22,410
Juhul Alexi algoritm, tal oli eelis Sean.

326
00:19:22,410 --> 00:19:27,780
Ta teadis, et need numbrid olid sorteeritud, kuid Alex ei olnud neid sorteerida ise.

327
00:19:27,780 --> 00:19:30,520
Ma ette tulid tahvli ja liik kindlaks teinud,

328
00:19:30,520 --> 00:19:33,670
et ma joonistasin neid kõiki läbi sorteeritud järjekorras, siis ma katmine paberiga.

329
00:19:33,670 --> 00:19:35,850
Aga kui palju tööd teinud, et võta mind?

330
00:19:35,850 --> 00:19:40,110
Kui oleksime alustati need numbrid näiliselt juhuslikus järjekorras -

331
00:19:40,110 --> 00:19:43,320
antud juhul seda lihtsamat numbrid, 1 kuni 8 siin -

332
00:19:43,320 --> 00:19:46,090
Kuidas me minna sorteerimine neid väärtusi?

333
00:19:46,090 --> 00:19:52,530
Kui sa olid inimeste andnud selle ülesande, millist intuitiivne Te sooviksite

334
00:19:52,530 --> 00:19:54,800
sorteeritakse terve hunnik numbreid?

335
00:19:54,800 --> 00:19:57,050
Need asjad pandi välja nagu puzzle tükki. Jah.

336
00:19:57,050 --> 00:19:59,950
>> [Üliõpilane] ma võtaks iga arv ja võrrelda seda igaüks

337
00:19:59,950 --> 00:20:03,180
ja jätkame vasakule. >> Olgu, hästi.

338
00:20:03,180 --> 00:20:05,720
Nii, et võta iga number, võrrelda seda teise peal,

339
00:20:05,720 --> 00:20:09,610
ja siis muudkui liigub piki nimekiri, millist rejiggering asju kui lähete.

340
00:20:09,610 --> 00:20:13,800
Nii et siin on meil võimalus võibolla veel mõned inimesed kaasa lööma.

341
00:20:13,800 --> 00:20:16,290
Kas meil on veel 8 vabatahtlikke, kes oleks tore tulla?

342
00:20:16,290 --> 00:20:23,950
Veidi vähem survet, sest sa pole ainuke. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Tule alla. Te ei kavatse olla numbrid 1 kuni 8.

344
00:20:28,190 --> 00:20:36,050
Vaatame, kas me ei saa seda teha sorteerimise Alex palju samamoodi ma tegin seda varem.

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

346
00:20:37,640 --> 00:20:40,760
Lase käia ja kui sa oleks, rivistama laval vahel muusika kuulamiseks ja mind siia

347
00:20:40,760 --> 00:20:44,960
samas järjekorras nagu slaidi ekraanil.

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

349
00:20:50,370 --> 00:20:53,230
Me töötame su järgmisesse näiteks. Oh, oota, oota. Läheb lahti. Oota.

350
00:20:53,230 --> 00:20:57,570
Järgmine näide on nüüd. Ole lahke. Number 8. Tule üles.

351
00:20:57,570 --> 00:21:00,270
Hea küll. Sorteeri endid vastavalt sellele.

352
00:21:00,270 --> 00:21:03,620
Lükake natuke kõrvale muusika seisan siin.

353
00:21:03,620 --> 00:21:12,310
Nii et meil on 4, 2, 6 - sinna, siin, seal - 3.

354
00:21:12,310 --> 00:21:17,570
Jah. Okei. Lähed siia. Ei, sa seal viibida.

355
00:21:17,570 --> 00:21:21,840
Jah, just seal. No ma eksin. Just seal. Okei, väga hea. Okei.

356
00:21:21,840 --> 00:21:24,930
Nii et nüüd lähme sorteeri need kasvavas järjekorras.

357
00:21:24,930 --> 00:21:26,210
>> Kuidas ma minna seda teed?

358
00:21:26,210 --> 00:21:28,630
Algoritm, mis pakkus hetk tagasi oli, miks me lihtsalt ei võrrelda

359
00:21:28,630 --> 00:21:31,970
inimesed, kes on omamoodi üksteise kõrval ja seejärel määrata vigu,

360
00:21:31,970 --> 00:21:33,540
liikudes vasakult paremale.

361
00:21:33,540 --> 00:21:36,580
Nii et siin on meil 4 ja 2, ilmselt rikkis. Olgem vahetan sinuga. Okei.

362
00:21:36,580 --> 00:21:40,760
Nii et nüüd ma lähen liikuda sätestatakse rida. 4 ja 6, nope. [Naer]

363
00:21:40,760 --> 00:21:45,010
6 ja 8, päris hea. 8 ja 1, las ma vahetan sinuga poisid. Hea küll.

364
00:21:45,010 --> 00:21:48,030
Nii et 8 ja 3, swap kutid.

365
00:21:48,030 --> 00:21:52,280
8 ja 7, las ma vahetan sinuga poisid. 5 ja 8, suurepärane.

366
00:21:52,280 --> 00:21:54,820
Ma annan sulle järjestatud nimekirja.

367
00:21:54,820 --> 00:21:56,860
Hea küll. Nii et mitte päris.

368
00:21:56,860 --> 00:22:01,180
Aga see on parem, sest suuremaid numbreid - näide 8 -

369
00:22:01,180 --> 00:22:04,030
on selline mullidena üles vasakult paremale poole.

370
00:22:04,030 --> 00:22:08,010
Nii et ma sain 1 neist õige, kuid see tunne see ei ole päris lahenda probleemi.

371
00:22:08,010 --> 00:22:11,150
>> Mida Sa välja pakuksid me edasi tegema? >> [Üliõpilane] Hoidke seda teha. >> Hoiame seda teha.

372
00:22:11,150 --> 00:22:13,740
Ja mõistma, jälle, me seada asju, mida lihtsalt millel on kõik inimesed

373
00:22:13,740 --> 00:22:17,180
omamoodi arukalt korraldada ise põhineb sellel pildil,

374
00:22:17,180 --> 00:22:19,040
kuid nüüd peame olema palju rohkem metoodiline.

375
00:22:19,040 --> 00:22:21,510
Me peame olema algoritmilise sellest, nagu oleks me kirjalikult kood -

376
00:22:21,510 --> 00:22:23,520
sel juhul verbaalne pseudokoodi.

377
00:22:23,520 --> 00:22:26,040
Nii et lubage mul lihtsalt proovida seda uuesti. See töötas päris hästi. See ei lahenda seda.

378
00:22:26,040 --> 00:22:30,400
Aga kui see kahtlen, lihtsalt proovida ja proovige uuesti. Nii et 2 ja 4, ei aidanud enam.

379
00:22:30,400 --> 00:22:33,200
4 ja 6. Ah! 6 ja 1 veidi parem nüüd.

380
00:22:33,200 --> 00:22:39,740
6 ja 3, hea. 6 ja 7 7 ja 5, 7 ja 8, hea.

381
00:22:39,740 --> 00:22:44,060
Ja tead, ma ei saa ilmselt ignoreerida 8 nüüd, sest ta on lõpus nimekirja.

382
00:22:44,060 --> 00:22:47,250
Võib-olla me ei pea muretsema keegi läheb mööda.

383
00:22:47,250 --> 00:22:49,240
Aga vaatame, kas see on ohutu eeldusel.

384
00:22:49,240 --> 00:22:52,340
Nüüd nimekiri on - kuradi - ei järjestatud. Proovime seda uuesti.

385
00:22:52,340 --> 00:22:56,440
Nii et 2 ja 4 4 ja 1, 4 ja 3.

386
00:22:56,440 --> 00:22:59,230
4 ja 6, hea. 6 ja 5, hea.

387
00:22:59,230 --> 00:23:04,890
6, 7, ja 8, hea. Aga teate, ma lihtsalt lõpetada siin nüüd ja peatub siin nüüd?

388
00:23:04,890 --> 00:23:07,770
[Üliõpilane] Jah. >> Jah?

389
00:23:07,770 --> 00:23:11,160
Mida teha, kui keegi teie seast oli number 9 kõik teed seal?

390
00:23:11,160 --> 00:23:13,640
See oleks järjestatud. >> Hea. See oleks järjestatud esimest korda ümber.

391
00:23:13,640 --> 00:23:16,050
Hea. Nii et lähme tagasi. Me oleme peaaegu kohal.

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

393
00:23:22,800 --> 00:23:26,640
>> Olen teinud nüüd, kuid jällegi, ma olen arvuti, mida saab ainult seda, mida ma olen rääkinud, mida teha,

394
00:23:26,640 --> 00:23:30,120
ja mu ainus mälestus on see, et ma tegelikult just tegin natuke tööd.

395
00:23:30,120 --> 00:23:31,700
Midagi muutunud siin.

396
00:23:31,700 --> 00:23:37,100
Nii et ma ei ole tehniliselt kinnitas visuaalselt või algoritmiliselt selle nimekirja tõepoolest sorteerida.

397
00:23:37,100 --> 00:23:40,720
Nii lihtsalt hea meede, lihtsalt olla anal sellest, teeme seda veel 1 kord.

398
00:23:40,720 --> 00:23:44,040
Nii et 1 ja 2, 2 ja 3, 3 ja 4. Ja tead mis?

399
00:23:44,040 --> 00:23:46,190
Lihtsalt hea meede, ma lähen jälgida minu poolt seekord

400
00:23:46,190 --> 00:23:51,110
kui palju vahetuslepingud teen lihtsalt nii, et ma tean, kui palju tööd ma olen tegelikult teinud.

401
00:23:51,110 --> 00:23:56,930
3 ja 4, 4 ja 5, 5 ja 6, 6 ja 7, 7 ja 8. Ei vahetustehingud.

402
00:23:56,930 --> 00:24:00,800
Nii et nüüd ma õiguspäraselt olla idioot seda teha ka

403
00:24:00,800 --> 00:24:03,330
sest kui ma ei teinud tööd selle kaudu liigu inimestele,

404
00:24:03,330 --> 00:24:06,710
siis selgelt, et juhtub jälle, kui ükski neist on omamoodi juhuslikult

405
00:24:06,710 --> 00:24:10,410
adversarially liigub ise ümber. Nii et nüüd ma ei peatu.

406
00:24:10,410 --> 00:24:15,120
Vaatame nüüd küsida, kui palju tööd teinud seda tegelikult mind?

407
00:24:15,120 --> 00:24:18,260
Mitu sammu see veel kestab? >> N ruudus.

408
00:24:18,260 --> 00:24:20,400
Jah, nii n ruudus. Kust saab n ruudus?

409
00:24:20,400 --> 00:24:22,660
Sa pead kontrollima iga arv -

410
00:24:22,660 --> 00:24:26,530
On n arv, ja sa pead kontrollima iga numbri teiste n arvu.

411
00:24:26,530 --> 00:24:29,030
Hea. >> Nii et see on n ruudus. >> Hea.

412
00:24:29,030 --> 00:24:31,060
>> Nii tundub see võiks väga hästi olla n ruudus, eks?

413
00:24:31,060 --> 00:24:33,820
Seal on n need kutid, 8 eriti sel juhul,

414
00:24:33,820 --> 00:24:37,590
kuid iga kord kui ma läksin läbi selle nimekirja olin võrrelda esimene inimene vastu teise,

415
00:24:37,590 --> 00:24:39,650
teine ​​vastu kolmandat uuesti ja uuesti ja uuesti,

416
00:24:39,650 --> 00:24:42,450
ja kui ma sain lõpuks, mida ma tegin? Ma redid ta.

417
00:24:42,450 --> 00:24:46,280
Nii et kui me üldistada seda seletust oleme n inimesed

418
00:24:46,280 --> 00:24:51,090
ja ma teen ilmselt 8 samme, n samme, iga kord ma lähen läbi selle algoritmi.

419
00:24:51,090 --> 00:24:56,070
Aga mitu korda halvimal juhul ma pean minema läbi selle nimekirja inimestest?

420
00:24:56,070 --> 00:24:59,370
[Üliõpilane] N korda. >> Ilmselt n, eks, sest halvimal juhul,

421
00:24:59,370 --> 00:25:03,410
Mis on ilmselt kõige mustema paigutus need kutid saada-minna?

422
00:25:03,410 --> 00:25:06,520
Kui nad täiesti vastupidises järjekorras

423
00:25:06,520 --> 00:25:09,310
sest lihtsalt oletame, vaimselt, let's - Mis su nimi on? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Okei. Nii Bowen, tule siia hetkeks.

425
00:25:12,510 --> 00:25:16,150
>> Oletame, et Bowen oli siin alguses algoritm,

426
00:25:16,150 --> 00:25:19,790
ja me ei tea, mida kõik teised on, kuid Bowen siin, vastavalt sellele algoritm -

427
00:25:19,790 --> 00:25:23,820
ja kui sa tahad lihtsalt jalutama minuga - läheb mulksuma, kui ta esimest korda ümber,

428
00:25:23,820 --> 00:25:25,740
kõik viis lõpuks.

429
00:25:25,740 --> 00:25:29,400
Aga oletame, et inimene kõrval Bowen oli number 7.

430
00:25:29,400 --> 00:25:33,450
Ma pean minema tagasi ja saada number 7, mis tähendab, ma pean minema kogu tee tagasi siia.

431
00:25:33,450 --> 00:25:36,980
Nüüd ma pean olema, et sama jalutama isikuga, kes on number 7.

432
00:25:36,980 --> 00:25:40,140
Aga kui siis number 6 oli tema kõrval ka?

433
00:25:40,140 --> 00:25:42,180
Siis ma pean minema tagasi ja saada 6.

434
00:25:42,180 --> 00:25:46,490
Nii et taas, iga iteratsiooni see silmus ma räägin iga n inimesed,

435
00:25:46,490 --> 00:25:50,090
ja ma oleks võinud teha n neid jalutuskäike veendumaks, et ma olen tõmmates

436
00:25:50,090 --> 00:25:53,760
kõiki suuremaid elemente tagasi ja tagasi ja tagasi väga loendi lõppu.

437
00:25:53,760 --> 00:25:58,230
Nii n asjad n korda on lihtsalt n korda n või n ruudus.

438
00:25:58,230 --> 00:26:02,050
>> Nii et siin juba on meil algoritm, mis ei ole enam n, et pole enam log n,

439
00:26:02,050 --> 00:26:04,820
see on tegelikult hullem kui midagi oleme varem teinud.

440
00:26:04,820 --> 00:26:09,840
Nii Alex liiki vedas, et ma tegin kõik tööd ilmselt kuni ees teda,

441
00:26:09,840 --> 00:26:14,690
kõik kallis töö, nii et ta saaks nautida selle binaarne otsing algoritm,

442
00:26:14,690 --> 00:26:16,420
mis on samamoodi n.

443
00:26:16,420 --> 00:26:18,240
Aga see on kooskõlas esmaspäeval teema.

444
00:26:18,240 --> 00:26:23,260
Me andsime natuke rohkem ruumi, me kasutasime rohkem bitte, et kiirendada meie sõiduaega.

445
00:26:23,260 --> 00:26:26,170
Nii palju nagu seal see kompromiss ajas ja ruumis

446
00:26:26,170 --> 00:26:31,060
Samuti võib olla ainult kompromisside aega, kuni ees omamoodi asju valmis minema

447
00:26:31,060 --> 00:26:35,000
ja tegelikult täidesaatva algoritm nagu otsing. Proovime veel ühe.

448
00:26:35,000 --> 00:26:39,050
Kui te ei pahanda, lihtsalt kiiresti ümber tõstes end sobitada, et jälle

449
00:26:39,050 --> 00:26:42,240
Proovime midagi veidi teistsugune, kui see ei ole päris nii lihtne

450
00:26:42,240 --> 00:26:45,760
kui lihtsalt fikseerida kõik paarikaupa vigu, mis on super intuitiivne.

451
00:26:45,760 --> 00:26:48,150
Lähme hoopis natuke rohkem tahtlik ja seda teha.

452
00:26:48,150 --> 00:26:51,010
See üks liiga pakun on ilmselt üsna intuitiivne.

453
00:26:51,010 --> 00:26:55,070
>> Olgem valida väikseim inimene nimekirjast ja jälle. Nii et siin me läheme.

454
00:26:55,070 --> 00:26:57,350
4, sa oled kõige väiksem inimene, keda olen seega näinud nii kaugele,

455
00:26:57,350 --> 00:27:00,520
nii et ma lähen vaimselt meeles pidama, et lihtsalt juhtides sind nüüd.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Unusta number 4. Ma leidsin just uue väikseim element selles loetelus.

457
00:27:05,020 --> 00:27:07,410
Ma lähen omamoodi meeles pidada. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Head aega. Nii et nüüd ma lähen mäleta number 1.

459
00:27:11,190 --> 00:27:14,790
Me teame, et 1 on väikseim, kuid ma olen arvuti. Mis siis, kui seal on 0?

460
00:27:14,790 --> 00:27:17,140
Mis siis, kui seal on -1? Ma pean edasi minema.

461
00:27:17,140 --> 00:27:20,990
Nii 3, 7, 5, nope. Okei. Nii et number 1 oli väikseim.

462
00:27:20,990 --> 00:27:23,640
Lubage mul valida te nimekirjast - we'll minna sel viisil -

463
00:27:23,640 --> 00:27:27,760
ja panna teid omavoliliselt alguses nimekirja.

464
00:27:27,760 --> 00:27:29,740
Nüüd oota natuke. Ma nagu petnud.

465
00:27:29,740 --> 00:27:34,010
Kui need kutid esindama ei nimekirja 8 inimest, kuid massiivi

466
00:27:34,010 --> 00:27:37,050
8 tükkideks sidusmäluplokki - ei te sealt tagasi hetkeks?

467
00:27:37,050 --> 00:27:39,060
Seal on tegelikult üldse ruumi teil siin.

468
00:27:39,060 --> 00:27:41,840
Niisiis, kuidas me ruumi teha - mis su nimi on? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Kuidas me teeme ruumi Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Me liigume n, mis on enne mind. >> Okei.

471
00:27:46,760 --> 00:27:48,850
Nii et me võiks minna n inimesed, kes on enne teda,

472
00:27:48,850 --> 00:27:52,400
nii et kui te tahate võtta 1 tahtlik, dramaatiline samm vasakule.

473
00:27:52,400 --> 00:27:57,000
Nad kõik tegid seda üheskoos, kuid viimane kord, kui ma kirjutasin mõned kood,

474
00:27:57,000 --> 00:27:59,740
sa ei saa omamoodi liikuda palju asju korraga.

475
00:27:59,740 --> 00:28:02,450
Me võiksime seda teha silmus, liigub igaüks üks kord korraga.

476
00:28:02,450 --> 00:28:04,340
Nii et kui te ei oleks midagi suurendades tagasi paremale,

477
00:28:04,340 --> 00:28:07,230
ja Sammy, kui sa saaksid tagasi astuda, sest seal on veel mingit võimalust sa,

478
00:28:07,230 --> 00:28:11,420
nüüd teeme seda. Kus oli Sammy hetk tagasi? Just seal.

479
00:28:11,420 --> 00:28:16,140
Nii et seal on vahe olemas. Nii et sina saaksid minna Sammy kohapeal.

480
00:28:16,140 --> 00:28:20,580
Nüüd järgmine isik üles ja nüüd järgmine inimene, nüüd järgmisele inimesele. Nüüd on meil ruumi Sammy.

481
00:28:20,580 --> 00:28:23,490
Nüüd keegi saalist - see oli hea, et oli õige,

482
00:28:23,490 --> 00:28:27,070
tundus natuke aega - mis on kiirem? Jah.

483
00:28:27,070 --> 00:28:29,440
[Üliõpilane] uue massiivi? >> Mis see on? >> [Üliõpilane] uue massiivi? >> Olgu, hästi.

484
00:28:29,440 --> 00:28:33,200
>> Nii kooskõlas käesoleva teema lihtsalt kompromisse, miks ei ma lihtsalt teha uus massiiv

485
00:28:33,200 --> 00:28:36,570
 ja siis Sammy on ujumine ruumi ees neid inimesi, näiteks

486
00:28:36,570 --> 00:28:39,600
ja me lihtsalt alustada täites uus massiiv kokku. See liiga teeks.

487
00:28:39,600 --> 00:28:42,450
Aga ma ei ole huvitatud kulutusi rohkem ruumi täna. Mis on teine ​​lähenemine?

488
00:28:42,450 --> 00:28:46,630
[Üliõpilane] Vaheta. >> Okei. Me võiksime lihtsalt vahetada need 2 kutid. Mis su nimi on?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Nii Mario, sa olid praegu siin.

490
00:28:49,390 --> 00:28:52,480
Sammy, kas sa varundada hetkeks? Mario oli siin.

491
00:28:52,480 --> 00:28:55,830
Meil ei ole ruumi enam sinuga, nii et kui sa ei pahanda läheb kus Sammy on,

492
00:28:55,830 --> 00:29:02,430
me paneme Sammy siin, ja nüüd ma tahaks väita, et Sammy Vahetatakse operatsioon oli palju kiirem.

493
00:29:02,430 --> 00:29:06,370
Me tegime 1 toimi vahetada need kutid, või äkki 2 vahetada need kutid,

494
00:29:06,370 --> 00:29:11,210
kuid me ei teinud 1, 2, 3, 4, nii et tundub parem. Nüüd oota natuke.

495
00:29:11,210 --> 00:29:14,660
Ma nagu näha probleemi hullemaks, sest number 4 oli selline lähedal alguses.

496
00:29:14,660 --> 00:29:19,470
Nüüd number 4 on veidi lähemale selleks, aga ma ei tea, või hooli sellest.

497
00:29:19,470 --> 00:29:23,330
Nii et see on lihtsalt halb õnn, et number 4 on natuke kaugemal oma määratud kohas.

498
00:29:23,330 --> 00:29:25,110
Nii et olgem nüüd korrata algoritmi.

499
00:29:25,110 --> 00:29:28,410
>> Et veel kord, kui see lugu oli, kõik me ei olnud kõndida läbi nimekirja

500
00:29:28,410 --> 00:29:31,130
otsin väikseim nummerdatud inimene.

501
00:29:31,130 --> 00:29:34,530
Nii et nüüd teeme seda jälle. Me ei pea muretsema Sammy enam.

502
00:29:34,530 --> 00:29:37,590
Me ei saa lihtsalt minema siit. Ooh! Number 2. See on päris väike arv.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Olgu, hästi.

504
00:29:41,180 --> 00:29:43,770
Ja õnneks juhuslikult, ma ei pea liikuma - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie, sest ta on tema õige koht nüüd.

506
00:29:45,910 --> 00:29:48,110
Teeme seda uuesti ja neid eirata 2 kutid.

507
00:29:48,110 --> 00:29:50,460
6. See on päris väike arv. Ooh! 8 on kindlasti suurem.

508
00:29:50,460 --> 00:29:53,410
4. Olgem keskenduda 4. Ooh! 3 on isegi parem.

509
00:29:53,410 --> 00:29:58,290
7 ja 5. Mida me siis nüüd teeme koos - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Lähme vahetame ta number 6.

511
00:30:00,250 --> 00:30:03,570
Nii et kui 6 ja 3 sooviks vahetada,

512
00:30:03,570 --> 00:30:07,320
oleme nüüd mingi saanud õnnelik, et 6 on lähemal, kui ta peaks olema,

513
00:30:07,320 --> 00:30:10,300
aga see on lihtsalt kokkusattumus siin. Nii et olgem nüüd minema siit.

514
00:30:10,300 --> 00:30:13,430
8 on päris väike arv. Ooh! 4 on väiksem.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Mida me nüüd teeme? >> Vaheta. >> Täpselt.

516
00:30:17,130 --> 00:30:19,010
Nii et nüüd teeme seda omamoodi kiiremini.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Kust 5 minna? Hea. Okei.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 saab peatada, kui ta on. Mis su nimi on? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie saab peatada, kui ta on. 7 jõuab - Vaatame. 7, 8. Okei.

520
00:30:31,770 --> 00:30:35,100
Nii et 7 saab peatada, kui ta on. Mis su nimi on? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Nii Amna saab peatada, kui ta on, ja number 8 on juba kus ta nüüd peaks olema.

522
00:30:39,670 --> 00:30:43,960
Olgu, hästi. Tundub nagu me lihtsalt luua töö ise, tõsi küll.

523
00:30:43,960 --> 00:30:47,440
Mis lõppkokkuvõttes sõiduaega Selle algoritmi?

524
00:30:47,440 --> 00:30:51,900
Kui me mõtleme need inimesed ei ole nii 8, kuid kui n? >> See on n.

525
00:30:51,900 --> 00:30:55,440
See on n samme, kuid me uurime iga kord.

526
00:30:55,440 --> 00:30:57,570
Okei. N aga sa kontrollida iga kord?

527
00:30:57,570 --> 00:31:03,450
Okei, aga kui see on n samme, ei tohiks mul on olnud võimalus sorteerida teile lihtsalt läheb 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Okei, see on suur vahe.

529
00:31:05,590 --> 00:31:08,050
Nii n ruudus miks? Mis tegelikult toimub?

530
00:31:08,050 --> 00:31:12,130
Seal on n inimesi selles nimekirjas, kuid leida väikseim isik nimekirja

531
00:31:12,130 --> 00:31:16,200
halvimal juhul, kui palju samme pean võtma? >> N.

532
00:31:16,200 --> 00:31:19,160
>> N, paremale, sest halvimal juhul, number 1 on kõik teed sinna,

533
00:31:19,160 --> 00:31:20,990
nii et ma pean minema saada teda.

534
00:31:20,990 --> 00:31:25,500
Ja siis kui ma lõpuks aru, 1 oli väikseim, siis see on üsna kiire, et vahetada neid.

535
00:31:25,500 --> 00:31:28,450
Aga nüüd pean ma alustama algusest ning otsida kes?

536
00:31:28,450 --> 00:31:31,980
Suuruselt järgmine kahanevas järjekorras isik, mis on 2. Kui halvimal juhul on 2?

537
00:31:31,980 --> 00:31:34,320
Oh, mu jumal. See kõik viis siia lõpus.

538
00:31:34,320 --> 00:31:37,000
Nii et nüüd ma olen lihtsalt teinud teise n samme, teise n samme.

539
00:31:37,000 --> 00:31:41,200
Ja kui meil on n inimesed ja halvimal juhul väikseim inimene on n sammu kaugusel,

540
00:31:41,200 --> 00:31:45,230
see on jälle n korda n, ja nii me jälle on n ruudus.

541
00:31:45,230 --> 00:31:47,280
Seda ei tunne end hästi.

542
00:31:47,280 --> 00:31:52,150
Ja tegelikult, isegi parimal juhul - oletame, et nad alustad järjestatud -

543
00:31:52,150 --> 00:31:59,080
mitu sammu see võtab minu jaoks kasutades seda algoritmi sorteerida neid n inimesed?

544
00:31:59,080 --> 00:32:01,010
N ruudus. >> Kuulsin n ruudus. Miks n ruudus?

545
00:32:01,010 --> 00:32:05,240
Sest sa ikka pead kontrollima iga kord. >> Jah.

546
00:32:05,240 --> 00:32:08,060
Ja sa pead vahetada neid. >> Kuigi me inimestel on mingi kõiketeadja

547
00:32:08,060 --> 00:32:10,770
selles mõttes visuaalselt, et saame lihtsalt selline näen, et see sorteeritakse,

548
00:32:10,770 --> 00:32:12,140
arvuti ei ole nii tark.

549
00:32:12,140 --> 00:32:14,040
See saab vaadata siin ja siin ja siin,

550
00:32:14,040 --> 00:32:16,610
aga kui see, mida ta otsib on väikseim element,

551
00:32:16,610 --> 00:32:22,110
tean vaid, et sa leidsid väikseim element, mida millisel hetkel? Kui oled lõpus.

552
00:32:22,110 --> 00:32:25,880
Aga sel hetkel oled ainult leida praegu väikseim element.

553
00:32:25,880 --> 00:32:28,810
Sa ei pruugi teada midagi olukorra kohta maailmas.

554
00:32:28,810 --> 00:32:30,880
Nii et sa pead minema uuesti ja uuesti ja uuesti.

555
00:32:30,880 --> 00:32:34,880
>> Nii et seekord ma tõesti vaadata loll, sest ma kontrollida, korras, 2, sa oled kõige väiksem,

556
00:32:34,880 --> 00:32:37,530
kuid ma ei tea, et kokku veel.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Olgu, hästi. 2 oli tõepoolest kõige väiksem.

558
00:32:41,090 --> 00:32:43,150
Nüüd otsime järgmine kahanevas järjekorras. Okei.

559
00:32:43,150 --> 00:32:48,350
3, sa oled praegu väikseim. Vaatame. 4, 5, 6, 7, 8. Okei, vedas jälle.

560
00:32:48,350 --> 00:32:53,170
3 oli tõepoolest õiges kohas. Aga ma lähen hoida tehes seda uuesti ja uuesti ja uuesti.

561
00:32:53,170 --> 00:32:55,990
Kuidas me saame kunagi nii veidi paremini?

562
00:32:55,990 --> 00:33:00,120
Selle asemel, et inimesed mulksuma paarikaupa alates väiksemast ja lõpetades suuremaga

563
00:33:00,120 --> 00:33:04,350
ja selle asemel, et minna edasi ja tagasi läbi nimekirja valides seejärel väikseim isik,

564
00:33:04,350 --> 00:33:09,780
miks me ei asemel sisestada need inimesed uude nimekirja samm-sammult?

565
00:33:09,780 --> 00:33:13,080
Proovime seda. Nüüd lubage mul nimetame seda asja sisestamise omamoodi.

566
00:33:13,080 --> 00:33:17,250
Nii et siin me oleme siin. Number 1. Ma ei hooli keegi teine ​​selles loetelus.

567
00:33:17,250 --> 00:33:21,310
Minu eesmärk praegu on panna number 1 alguses järjestatud nimekirja.

568
00:33:21,310 --> 00:33:23,910
Ja ma lähen ettepaneku sest mul on ainult 8 mäluhulka,

569
00:33:23,910 --> 00:33:28,670
omavoliliselt praegu olen seina vahel minu väidetavalt sortimata nimekirja,

570
00:33:28,670 --> 00:33:32,740
ja igaüks, kes on mu selja taga ma väita, sorteeritakse.

571
00:33:32,740 --> 00:33:34,680
Nii et nüüd on meil number 1.

572
00:33:34,680 --> 00:33:39,240
Ma tahan lisada ta minu järjestatud nimekirja, nii et ma olen lihtsalt kavatse minna mu seinal,

573
00:33:39,240 --> 00:33:43,930
ja nüüd ma väidavad, et see nimekiri on sorteeritud, see nimekiri on sorteerimata - vähemalt nii palju kui mina tean.

574
00:33:43,930 --> 00:33:46,070
Ma ei näe kõik numbrid korraga.

575
00:33:46,070 --> 00:33:49,000
>> Nüüd ma juhtun kokku puutuvad number 2. Mida ma temaga tegema?

576
00:33:49,000 --> 00:33:54,380
Ma sisestan sa nüüd sisse järjestatud nimekirja. Aga teate, kui lihtne see oli.

577
00:33:54,380 --> 00:33:59,650
Ma lihtsalt pean vaatama. Number 1 on olemas. Oh, loomulikult 2 läheb pool number 1.

578
00:33:59,650 --> 00:34:03,700
Nüüd mida ma pean tegema 3? Ma sisestan teid järjestatud nimekirja. Aga see oli super lihtne.

579
00:34:03,700 --> 00:34:07,250
See on super lihtne, see on super lihtne, see on super lihtne, väga lihtne, väga lihtne.

580
00:34:07,250 --> 00:34:12,790
Ja nüüd on kõik järjestatud minu taga, ja kui palju samme ei, mis võtavad?

581
00:34:12,790 --> 00:34:15,620
[Õpilased] N. >> Nii et see on ainult n. Meil vedas.

582
00:34:15,620 --> 00:34:18,860
Alles n miks? >> [Üliõpilane] Kuna loetelu on järjestatud.

583
00:34:18,860 --> 00:34:21,630
Nimekiri on juba järjestatud. Nii et meil vedas.

584
00:34:21,630 --> 00:34:25,639
Aga me loodud algoritmi see aeg, et rakmed sellist õnne,

585
00:34:25,639 --> 00:34:29,420
et parimal juhul, mida ei raiska asjatut aja.

586
00:34:29,420 --> 00:34:31,750
Nii et meil on nüüd see, mida me nimetame mull kehvasti

587
00:34:31,750 --> 00:34:33,949
kus inimesed sellist mulksuma paarikaupa.

588
00:34:33,949 --> 00:34:38,100
Meil on nüüd valik omamoodi kus me kisu väikseim isik ikka ja jälle.

589
00:34:38,100 --> 00:34:42,350
Ja nüüd on meil sisestamise omamoodi kus me justkui ennetavalt panna inimesed, kui nad kuuluvad

590
00:34:42,350 --> 00:34:45,000
üha järjestatud nimekirja.

591
00:34:45,000 --> 00:34:49,679
Kui meil õnnestuks, aplaus need kutid siin. [Aplaus]

592
00:34:49,679 --> 00:34:52,310
Võtame meie 5-minutilise vaheaja siin.

593
00:34:52,310 --> 00:34:55,139
Ja kui me tagasi tuleme, me laseme kõik need algoritmid veest välja

594
00:34:55,139 --> 00:35:00,260
midagi paremat. Hea küll. Tänan teid väga. Saate hoida neid nagu suveniire.

595
00:35:01,710 --> 00:35:04,330
Hea küll. Me oleme tagasi.

596
00:35:04,330 --> 00:35:08,420
>> Ja sulgege päris kiire, meil oli neid 3 erinevat lähenemist sorteerimine,

597
00:35:08,420 --> 00:35:13,000
Kogu mõte oli saada kuni punktini, kus keegi nagu Alex

598
00:35:13,000 --> 00:35:16,930
võiks otsida nimekirja numbrid kiiremini kui keegi nagu Sean võiks.

599
00:35:16,930 --> 00:35:19,830
Ja kuigi meil on nii lihtne näiteid 8 numbri,

600
00:35:19,830 --> 00:35:24,000
siis võiks ekstrapoleerida kergesti kuni 8 veebilehti, 8 miljardi veebilehti,

601
00:35:24,000 --> 00:35:26,680
ehk 800 miljonit sõpradega Facebook.

602
00:35:26,680 --> 00:35:30,090
Nii et need algoritmid saab kindlasti skaala seda tüüpi väärtusi,

603
00:35:30,090 --> 00:35:32,300
ja ideed on lõpuks sama.

604
00:35:32,300 --> 00:35:36,140
Nii et mull sorteerida oli esimene, kus me sellist mullidena üles suurim inimene

605
00:35:36,140 --> 00:35:39,110
kogu tee paremale vahetades inimesed paarikaupa.

606
00:35:39,110 --> 00:35:42,040
Siis oli meil mida me kutsume valik omamoodi, kus ma veidi tahtlikult

607
00:35:42,040 --> 00:35:46,480
hoida otsin läbi nimekirja, valides kõige vähem uuesti ja uuesti ja uuesti,

608
00:35:46,480 --> 00:35:49,530
loogiline tulemus, mis on selle nimekirja lõpuks sorteerida.

609
00:35:49,530 --> 00:35:53,780
Siis kolmas, Ma sisestasin inimesi oma sobivas kohas

610
00:35:53,780 --> 00:35:57,720
ja me tegime väga kunstlik näiteks, et nimekiri oli juba sorteeritud,

611
00:35:57,720 --> 00:36:01,100
aga see oli saata sõnum, et sisestamise omamoodi juhtum,

612
00:36:01,100 --> 00:36:02,670
võite saada õnnelik.

613
00:36:02,670 --> 00:36:07,930
Kui numbrid on juba sorteeritud, see on ainult kavatse teid n samme kinnituseks,

614
00:36:07,930 --> 00:36:10,870
arvestades, et valik omamoodi sa oled natuke rohkem tunnel nägemine

615
00:36:10,870 --> 00:36:14,360
ja sa ei ole kunagi aru, et nimekiri on juba järjestatud.

616
00:36:14,360 --> 00:36:16,830
Nii et vaatame, mull sorteerida huviorbiidis siin.

617
00:36:16,830 --> 00:36:19,590
Järgmises näites, me parasjagu näha vertikaaltulpade

618
00:36:19,590 --> 00:36:23,030
kelle kõrgused arvude, et saaksime omamoodi visualiseerida sorteerimine juhtuda.

619
00:36:23,030 --> 00:36:26,630
Mida väiksem on baar, väiksem number; suurem baar, suurem number.

620
00:36:26,630 --> 00:36:28,860
>> Ja me mängida seda default kiirusel.

621
00:36:28,860 --> 00:36:33,460
Läheb veidi liigutada kiire nüüd, aga punane on see, mis näitab, 2 baari

622
00:36:33,460 --> 00:36:35,480
võrreldakse kõrvuti.

623
00:36:35,480 --> 00:36:39,520
Ja kui sa vaatad tähelepanelikult, mis juhtub on see, et kui baarid on rikkis,

624
00:36:39,520 --> 00:36:42,300
väiksemat saab liigutada vasakule, suurem üks paremale,

625
00:36:42,300 --> 00:36:44,360
ja siis hoiavad edeneb.

626
00:36:44,360 --> 00:36:48,520
Nii et kui me teeme seda ikka ja jälle, märkate, et väikseim baarid

627
00:36:48,520 --> 00:36:51,090
ei kavatse hoida inching oma tee vasakule

628
00:36:51,090 --> 00:36:54,130
ja suurim baarid ei kavatse hoida inching oma tee paremale.

629
00:36:54,130 --> 00:36:58,490
Ja tõepoolest, me hakkame nägema muster kogu tee paremas servas

630
00:36:58,490 --> 00:37:04,790
nagu nägime 8 ja seejärel 7 lõpuks vahustamine kuni otsas meie inimeste nimekiri.

631
00:37:04,790 --> 00:37:08,750
Nii et see läheb väga kiiresti natuke tüütu, seega lubage mul lõpetada see hetkeks.

632
00:37:08,750 --> 00:37:10,980
Lubage mul muuta kiirust palju kiirem.

633
00:37:10,980 --> 00:37:15,380
Ma ei vaheta algoritm, ma lihtsalt teha animatsiooni juhtuda kiiremini.

634
00:37:15,380 --> 00:37:18,410
Ikka mull sorteerida, sama algoritmi,

635
00:37:18,410 --> 00:37:21,910
kuid nüüd näete palju kiiremini kui meie verbaalne tutvustamistegevuse

636
00:37:21,910 --> 00:37:25,900
et suurim elemendid on tõepoolest vahustamine kuni tippu.

637
00:37:25,900 --> 00:37:29,860
>> Nagu kõrvale, need väikesed ruudud allosas vasakul ja paremal all

638
00:37:29,860 --> 00:37:33,520
on vaid väike meeldetuletus, kui palju võrdlusi sa teed.

639
00:37:33,520 --> 00:37:37,620
Aga nüüd, saame keskenduda püramiid, mis on kuju võtmas, ja seal ta läheb.

640
00:37:37,620 --> 00:37:41,510
Kõige väiksem osa on vasakul, suurim paremal, ja kõike muud nende vahel.

641
00:37:41,510 --> 00:37:44,470
Nüüd vaatame selle asemel vaatleme valik omamoodi.

642
00:37:44,470 --> 00:37:47,260
Ma lähen edasi minna ja vajuta Stopp. Me ei hakka uut juhuslik kogum baarid.

643
00:37:47,260 --> 00:37:50,930
Valik omamoodi, mäletate, läbib nimekirja uuesti ja uuesti ja uuesti,

644
00:37:50,930 --> 00:37:54,900
noppida välja kõige väiksema osa. Nii et siin on valik omamoodi.

645
00:37:54,900 --> 00:37:58,390
Tundub, et seal on vähem tööd juhtub nüüd, sest me ei võrrelda paarikaupa

646
00:37:58,390 --> 00:38:02,590
aga me lihtsalt omamoodi cherry picking väikseim elemendid paremalt vasakule.

647
00:38:02,590 --> 00:38:06,890
See võttis väga vähe aega, nii et seal on lõhe juba.

648
00:38:06,890 --> 00:38:11,820
Lihtsalt, sest algoritm on öelnud, et võtta n ruudus korda, nagu mull sorteerida

649
00:38:11,820 --> 00:38:16,100
ja nagu valik omamoodi, need on tõesti halvima töötab korda.

650
00:38:16,100 --> 00:38:21,790
Näiteks juhul, oletame, valik omamoodi,

651
00:38:21,790 --> 00:38:27,240
Ma tegelikult olen valides väikseim inimene ja paneb teda siin,

652
00:38:27,240 --> 00:38:29,620
siis ma teen seda uuesti, siis ma teen seda uuesti,

653
00:38:29,620 --> 00:38:32,070
kuid seal oli kerge optimeerimine ma võiksin teha.

654
00:38:32,070 --> 00:38:35,040
>> Niipea, kui ma kolisin number 1 siin - Sammy sel juhul -

655
00:38:35,040 --> 00:38:38,630
mida ma pean tegema temaga hiljem? >> [Üliõpilane] Jätke ta.

656
00:38:38,630 --> 00:38:40,140
Jäta ta, eks? Mitte midagi.

657
00:38:40,140 --> 00:38:44,310
Ma ei pea kunagi rääkima Sammy uuesti, sest kui ma olin välja valinud väikseim element

658
00:38:44,310 --> 00:38:48,580
ja pani ta siin, miks raisata aega läheb lõpuks kogu mu nimekirjas?

659
00:38:48,580 --> 00:38:54,590
Järgmisel iteratsiooni andke mulle tegelikult liikuda ainult number 2, ainult number 3.

660
00:38:54,590 --> 00:38:57,640
Nii et tegelikult ma ei tee n asjad n korda.

661
00:38:57,640 --> 00:39:05,380
Ma tegin n asju, siis n - 1 asja, siis n - 2 asja, siis n - 3 asja,

662
00:39:05,380 --> 00:39:07,080
siis n - 4, dot, dot, dot.

663
00:39:07,080 --> 00:39:09,470
Meil on natuke geomeetrilises jadas, mis tähendab lihtsalt

664
00:39:09,470 --> 00:39:11,450
Sa liidad kokku järjest väiksemaid numbreid.

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

666
00:39:17,940 --> 00:39:21,380
Ja mida see üldiselt töötab välja tuleb -

667
00:39:21,380 --> 00:39:24,280
Ma lähen segi ajama mu laud siin hetkeks -

668
00:39:24,280 --> 00:39:28,990
et läheb töötada välja tuleb midagi n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
kui me lihtsalt selline pilk tagasi matemaatika raamat, kus sul on kõik cheat lehed

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

671
00:39:33,410 --> 00:39:37,760
Kui sa oled lihtsalt lisades midagi n + n - 1 + n - 2, see töötab välja midagi sellist.

672
00:39:37,760 --> 00:39:42,320
Ja kui me lihtsalt selline korrutada see läbi, et N-ruudus miinus n / 2.

673
00:39:42,320 --> 00:39:46,400
Ma kordasin n ruudus, kuigi ja see on, sest ma olin selline võttes vaimne otsetee

674
00:39:46,400 --> 00:39:51,950
sest tegelikult n ruudus miinus n jagatud 2 on tõesti tõsi mitmeid samme

675
00:39:51,950 --> 00:39:55,510
et algoritm nagu valik omamoodi võtaks, kui me tõesti loendatakse

676
00:39:55,510 --> 00:39:58,800
kõik need võrdlused ja kõik vähe hõivatud töö, mida me teeme.

677
00:39:58,800 --> 00:40:03,210
Aga ausalt öeldes, kui n saab olla nagu miljon või miljard, kes kuradit see huvitab

678
00:40:03,210 --> 00:40:07,160
kui sa teed miljardit ruudus miinus miljardit jagatuna 2?

679
00:40:07,160 --> 00:40:09,320
Miljardit ruudus on tohutu hulk.

680
00:40:09,320 --> 00:40:13,580
Te võite võtta teise miljardi pealt ta koos - n. See pole nii suur asi.

681
00:40:13,580 --> 00:40:18,770
Nii et suurem number saada, seda vähem tähtis nende madalama tellitud terminid on.

682
00:40:18,770 --> 00:40:24,230
Keda huvitab, kui sa jagad 2, kui sa räägid quadrillions numbrite sammud?

683
00:40:24,230 --> 00:40:29,710
>> Nii et üldiselt, arvuti teadlased kipuvad visata kõike, kuid suurima perspektiivis

684
00:40:29,710 --> 00:40:33,140
ja me lihtsalt selline lihtsustada maailma ja öelda, et see algoritm

685
00:40:33,140 --> 00:40:38,130
võttis umbes n ruudus samme. See on töötamise aeg algoritm.

686
00:40:38,130 --> 00:40:40,760
Nii et me tuleme selle juurde tagasi just hetk mõned konkreetsed näited,

687
00:40:40,760 --> 00:40:45,940
kuid nüüd, see on omamoodi intuitiivne motivatsioon lihtsalt lihtsustades meie maailma

688
00:40:45,940 --> 00:40:51,170
ja rääkides kõige olulisemaks tingimuste asemel sattumist kõik need väljamõeldud valemeid.

689
00:40:51,170 --> 00:40:53,540
Nii et oli valik omamoodi, ja saime natuke õnnelik seal.

690
00:40:53,540 --> 00:40:57,360
Vaatame sisestamise omamoodi. Lubage mul minna ja hakata selle ühe samuti.

691
00:40:57,360 --> 00:41:00,330
Nüüd pane tähele, muster, mis toimub on natuke erinev,

692
00:41:00,330 --> 00:41:03,410
ja alustasime juhuslikud arvud,

693
00:41:03,410 --> 00:41:06,890
Aga kui me tegelikult kokku lugema mitmeid samme halvimal juhul

694
00:41:06,890 --> 00:41:11,070
Kui loend algas täiesti õiges järjekorras,

695
00:41:11,070 --> 00:41:13,380
me oleks ainult võtta n samme mõista nii palju.

696
00:41:13,380 --> 00:41:18,240
>> Aga kui nimekirjas olid tegelikult tagurpidi - näiteks selles asjas -

697
00:41:18,240 --> 00:41:23,860
siis märkate me tegelikult peame tegema palju rohkem tööd ka käesoleval juhul.

698
00:41:23,860 --> 00:41:27,080
Ja see peaks selline tunne, et sulle meeldib see üks on selline töö raskem

699
00:41:27,080 --> 00:41:30,900
saada väiksematele elemente vasakule ja see on, sest meil on õnnetu.

700
00:41:30,900 --> 00:41:34,210
Loetelu on järjestatud kogemata tagurpidi.

701
00:41:34,210 --> 00:41:38,110
Seevastu järjepunktiga omamoodi kui me jäljendada mida tegime meie inimestel siin

702
00:41:38,110 --> 00:41:42,670
alustades kõigiga sorteeritakse ja seejärel alustada, see on päris hea algoritm, eks?

703
00:41:42,670 --> 00:41:45,010
See on juba tegelikult sorteerida.

704
00:41:45,010 --> 00:41:48,670
Nii et proovime kokku täpselt, kui palju aega need asjad on meid

705
00:41:48,670 --> 00:41:52,360
kehtestades lihtsalt natuke kõnepruuki või märke, mis on tegelikult palju lihtsam

706
00:41:52,360 --> 00:41:54,320
kui fanciness omamoodi soovitab.

707
00:41:54,320 --> 00:41:59,030
See asi siin, see suur O ekraanil on see, mida arvuti teadlane üldjuhul kasutada

708
00:41:59,030 --> 00:42:03,640
kirjeldada halvimal juhul sõiduaega algoritm.

709
00:42:03,640 --> 00:42:07,360
>> Jällegi, mida halvimal juhul on see täiesti kontekstist sõltuv.

710
00:42:07,360 --> 00:42:10,890
Mida tähendab meie jaoks halvimal juhul täiesti erinevad vastavalt probleemi me räägime.

711
00:42:10,890 --> 00:42:14,550
Aga kui tegemist on sorteerimise, mis on kõige hullem võimalik stsenaarium?

712
00:42:14,550 --> 00:42:17,860
Kõik on tagurpidi, sest see lihtsalt tundub, et tähendab palju tööd meie eest.

713
00:42:17,860 --> 00:42:21,330
Olen kirja pannud mõned algoritme, et oleme näinud siiani:

714
00:42:21,330 --> 00:42:24,930
lineaarne otsing, binaarne otsing jms telefoniraamatust või paberitükke,

715
00:42:24,930 --> 00:42:28,960
siis mull sorteerida, valik omamoodi ja sisestamise omamoodi nagu nägime meie inimestele,

716
00:42:28,960 --> 00:42:31,770
ja siis veel 1 inimene, mis on lõpuks nimetama hakatakse ühendada sorteerida.

717
00:42:31,770 --> 00:42:37,710
Nii et lineaarne otsing halvimal juhul, kui palju samme läheb aega, et leida number 7

718
00:42:37,710 --> 00:42:40,690
kui on n uste nagu Sean näoga? >> [Üliõpilane] N.

719
00:42:40,690 --> 00:42:44,180
N. Nii et me kirjutada suur O n.

720
00:42:44,180 --> 00:42:47,010
Ma lihtsalt täita mõned lüngad. See on vaid ruudustik toorikud.

721
00:42:47,010 --> 00:42:52,990
Aga parimal juhul lineaarse otsing, 7 oleks võinud kohe alguses nimekirja,

722
00:42:52,990 --> 00:42:55,520
ja Sean võis hakkasin otsima alguses nimekirja.

723
00:42:55,520 --> 00:42:58,940
Nii et kui te kasutate lineaarset otsing ja lihtsalt kontrollida vasakult paremale või äkki paremalt vasakule -

724
00:42:58,940 --> 00:43:02,650
nad samaväärne - parimal juhul mitu sammu võiks lineaarne otsing,

725
00:43:02,650 --> 00:43:05,550
nagu Sean algoritm, võtma? Just 1 samm.

726
00:43:05,550 --> 00:43:09,450
>> Nii et ma lähen ütlen, et see omega märke.

727
00:43:09,450 --> 00:43:11,570
See on lihtsalt kapitali omega.

728
00:43:11,570 --> 00:43:15,000
Omega on lihtsalt seksikas viis öelda parimal juhul sõiduaega.

729
00:43:15,000 --> 00:43:18,900
Nii et parimal juhul on käigu aeg üheetapiline või pidev sammude arv -

730
00:43:18,900 --> 00:43:24,270
1 Sel juhul - kuid halvimal juhul suur O, see on tegelikult n samme.

731
00:43:24,270 --> 00:43:28,110
Ja see siin, teeta, me tegelikult ei kavatse vaadata kohe.

732
00:43:28,110 --> 00:43:30,090
See ei ole seotud selle konkreetse näite.

733
00:43:30,090 --> 00:43:31,990
Aga nüüd proovime binaarne otsing.

734
00:43:31,990 --> 00:43:35,990
Halvimal juhul koos Kahendotsingupuu, kui palju samme ta kavatseb võtta, et leida number 7

735
00:43:35,990 --> 00:43:38,340
või mis iganes me otsime? >> [Üliõpilane] Logi n.

736
00:43:38,340 --> 00:43:40,980
Ikka läheb samamoodi n sest nagu Alex sai õnnetu

737
00:43:40,980 --> 00:43:44,030
kui me tõesti töötas läbi probleem metoodiliselt

738
00:43:44,030 --> 00:43:48,220
ja ta ei leidnud number 7 kuni viimase ukse vaatas ta,

739
00:43:48,220 --> 00:43:51,720
kuigi, õiglus, sai ära visata teatud uksi mööda teed,

740
00:43:51,720 --> 00:43:56,920
Kahendotsingupuu halvimal juhul on töötamise aeg log n.

741
00:43:56,920 --> 00:43:59,230
Ja veel, mis räägib selle jagamisel ja vallutavad.

742
00:43:59,230 --> 00:44:01,140
Aga kuidas parimal juhul?

743
00:44:01,140 --> 00:44:04,790
Ja Alex tegelikult kogenud, et parimal juhul õigus, kui ta tuli lavale.

744
00:44:04,790 --> 00:44:07,290
Mitu sammu ei et võtta Kahendotsingupuu? >> [Üliõpilane] 1.

745
00:44:07,290 --> 00:44:09,380
1, lihtsalt sellepärast, et ta vedas.

746
00:44:09,380 --> 00:44:12,520
Aga sellest pole midagi, sest omega viitab parimal juhul stsenaariumid,

747
00:44:12,520 --> 00:44:15,770
Parimal juhul sisendid, isegi kui see on lihtsalt juhuslik loll õnne.

748
00:44:15,770 --> 00:44:18,900
>> Nüüd on see liiga läheme lihtsalt selline, jäta tühjaks nüüd.

749
00:44:18,900 --> 00:44:21,010
Kuidas nüüd mull sorteerida?

750
00:44:21,010 --> 00:44:24,290
Halvimal juhul koos mull sorteerida, kõik on vastupidises järjekorras,

751
00:44:24,290 --> 00:44:26,380
nii et me peame tegema palju vahustamine.

752
00:44:26,380 --> 00:44:30,190
Aga kui palju samme on, et aega võtab halvimal juhul? >> [Üliõpilane] N ruudus.

753
00:44:30,190 --> 00:44:32,550
See oli n ruudus, sest kui sa mõtle selle peale,

754
00:44:32,550 --> 00:44:36,410
Kui loend on täiesti tagurpidi - 8 on siin, 1 on siin -

755
00:44:36,410 --> 00:44:40,530
kui asi hakkab mull, number 8 saab liikuda nii, nii,

756
00:44:40,530 --> 00:44:44,540
Nii sel viisil, kuid kus on number 7 halvimal juhul?

757
00:44:44,540 --> 00:44:47,720
Siin ta on ikka seal. Nii et me peame tegema seda ikka ja jälle.

758
00:44:47,720 --> 00:44:53,190
Ja see on koht, kus saame n samme, siis n - 1 samme, siis n - 2 sammu.

759
00:44:53,190 --> 00:44:55,960
Ja kui sa võtke minu sõna see - et kui sa sellist korrutada see läbi,

760
00:44:55,960 --> 00:45:00,110
see on umbes n ruudus lõpuks mõned muud tingimused, et me lihtsalt ignoreerida nüüd -

761
00:45:00,110 --> 00:45:06,890
siis halvimal juhul mull sorteerida on n ruudus, võta või jäta.

762
00:45:06,890 --> 00:45:09,490
Aga kuidas parimal juhul koos mull sorteerida?

763
00:45:09,490 --> 00:45:13,050
Milline on parim stsenaarium? Kõik numbrid on järjestatud juba.

764
00:45:13,050 --> 00:45:15,920
Ja milline oli heuristiline olen kasutanud, trikk Ma kasutasin,

765
00:45:15,920 --> 00:45:20,110
mõistma, et ma olin teinud ühtegi tööd ning seetõttu lõpetage varakult?

766
00:45:20,110 --> 00:45:23,590
[Üliõpilane] Vaata seda üks kord. >> Vaata seda üks kord. Aga mida ma teha mööda teed?

767
00:45:23,590 --> 00:45:26,130
Olin jälgida, kui palju vahetuslepingud tegin.

768
00:45:26,130 --> 00:45:30,650
Ja ma sain aru, kui ma ei ole loendatud tahes vahetuslepingute minu sõrmede, siis ma olen teinud ühtegi tööd.

769
00:45:30,650 --> 00:45:34,300
Ma kindlasti ei tohiks proovida teha mingit tööd jälle, et ma saaks lihtsalt lõpetada.

770
00:45:34,300 --> 00:45:37,830
>> Nii et parimal juhul mull sortida, kui loend on juba sorteeritud,

771
00:45:37,830 --> 00:45:41,530
mida sa ütleksid omega märke on, parimal juhul sõiduaega?

772
00:45:41,530 --> 00:45:48,040
See on lihtsalt n. Me peame tegema mõned tööd, kuid meil on ainult teha 1 jalutuskäiku väärt töö.

773
00:45:48,040 --> 00:45:50,490
Ja ka siin ma jätan selle osa tühjaks.

774
00:45:50,490 --> 00:45:52,430
Ja nüüd valik omamoodi.

775
00:45:52,430 --> 00:45:56,010
Valik omamoodi oli mulle kitkumise väikseim isik ikka ja jälle.

776
00:45:56,010 --> 00:45:58,380
Ja mida me ütleme töötamise aeg see oli?

777
00:45:58,380 --> 00:46:00,590
See oli n ruudus halvimal juhul.

778
00:46:00,590 --> 00:46:05,220
Ja kahjuks, parimal juhul on see ka n ruudus

779
00:46:05,220 --> 00:46:08,840
sest ma ei ole mingi kõiketeadev vaade kogu maailmas;

780
00:46:08,840 --> 00:46:13,140
Ma tean vaid pärast täielikku iteratsiooni, et olen tõepoolest leidnud väikseim inimene.

781
00:46:13,140 --> 00:46:15,860
Nii et valik omamoodi selline nõme selles mõttes,

782
00:46:15,860 --> 00:46:17,920
vaid tagurpidi on see on selline intuitiivne.

783
00:46:17,920 --> 00:46:21,470
See on päris lihtne kodeerida üles, sest kõik mida sa pead tegema, on kirjutada paar nested jaoks silmuseid,

784
00:46:21,470 --> 00:46:24,620
tavaliselt, et läheb läbi otsivad väikseim element

785
00:46:24,620 --> 00:46:27,840
ja siis paneb väikseim element, kui ta kuulub lõpus nimekirja.

786
00:46:27,840 --> 00:46:29,900
Nii et ka siin saab olema kompromiss.

787
00:46:29,900 --> 00:46:34,440
Aega kulub teil mõelda ja tegelikult arendada midagi kirjutada koodi

788
00:46:34,440 --> 00:46:39,460
võiks väga hästi võtab rohkem aega, kui soovite paremat algoritmi ja kiiremini tulemusi.

789
00:46:39,460 --> 00:46:41,780
>> Aga kui sa tõesti just selline kood midagi välja kiire ja räpane

790
00:46:41,780 --> 00:46:45,000
ja just selline võtma lollim võimalik idee saab mõelda,

791
00:46:45,000 --> 00:46:47,580
et võib kuluda paar minutit koodi, kuid suurte andmekogumite

792
00:46:47,580 --> 00:46:49,580
oma algoritm võib kuluda tundi joosta.

793
00:46:49,580 --> 00:46:51,690
Ja isegi mina Magistriõppe oleks mõnikord teevad need kompromissid.

794
00:46:51,690 --> 00:46:55,660
Oleks 03:00, üritasin analüüsida mõningaid väga suure andmekogumi

795
00:46:55,660 --> 00:46:59,650
julgeolekuga seotud teadusuuringud ma tegin, ja see oli kas kulutada 5 minutit

796
00:46:59,650 --> 00:47:03,210
tutistamine minu programm, et analüüsida andmeid ja magama minna

797
00:47:03,210 --> 00:47:08,420
või veeta 8 tundi saada see just nii see töötab koheselt ja ei lähe magama.

798
00:47:08,420 --> 00:47:10,530
Ja nii ka seal see on selline teadlik otsus.

799
00:47:10,530 --> 00:47:12,740
Vähem arengu ajal rohkem magada.

800
00:47:12,740 --> 00:47:14,780
Tagasivaates Ma ilmselt ei peaks julgustama, et

801
00:47:14,780 --> 00:47:19,120
kui eesmärk siin on optimeerida kvaliteedi kood,

802
00:47:19,120 --> 00:47:21,280
kuid liiga reaalses maailmas on väga mõistlik kompromiss.

803
00:47:21,280 --> 00:47:25,130
Vähem aega, jõudlus väiksem või vastupidi.

804
00:47:25,130 --> 00:47:28,110
Nii et siin me lõpuks saada võimalus rääkida teeta.

805
00:47:28,110 --> 00:47:32,830
Theta märke on midagi arvuti teadlased avab vestluses

806
00:47:32,830 --> 00:47:36,160
kui suur O ja omega juhtub olema sama.

807
00:47:36,160 --> 00:47:40,160
Sa ütled teeta tõesti saata sõnum, et see on selline tihe seotud.

808
00:47:40,160 --> 00:47:43,340
Ükskõik, kas stsenaarium on hea või halb, see on n ruudus.

809
00:47:43,340 --> 00:47:46,510
Nii et see lihtsalt ei ole olulised need lood siin.

810
00:47:46,510 --> 00:47:48,560
Insertion sorti on viimane me vaatasime,

811
00:47:48,560 --> 00:47:50,830
kus ma olin lihtsalt lisada kõik õiges kohas.

812
00:47:50,830 --> 00:47:54,930
Parimal juhul milline oli jooksmine on asetatud omamoodi nagu me nägime seda siin?

813
00:47:54,930 --> 00:47:57,250
[Üliõpilane] parimal juhul? >> Parimal juhul.

814
00:47:57,250 --> 00:48:00,100
>> See oli n sest parimal juhul kõigile sorteeritud,

815
00:48:00,100 --> 00:48:02,580
ja Sammy ja keegi tõesti olnud üldse liikuda.

816
00:48:02,580 --> 00:48:04,610
Nad olid juba oma õiges kohas.

817
00:48:04,610 --> 00:48:08,570
Nii sisestamise omamoodi parimal juhul on sellisel juhul n.

818
00:48:08,570 --> 00:48:12,770
Aga halvemal juhul see on selline n ruudus. Miks?

819
00:48:12,770 --> 00:48:16,230
Kui minu nimekirja inimestel on vastupidises järjekorras,

820
00:48:16,230 --> 00:48:21,260
Ma esimest korda alustada number 8 ja ma sisestan teda õigesse asendisse, mis on siinsamas.

821
00:48:21,260 --> 00:48:25,270
Ma nagu liikuda külg. Need kutid sortimata, ta on järjestatud.

822
00:48:25,270 --> 00:48:28,970
Aga nüüd ma juhtun leidma kes järgmine? >> [Üliõpilane] 7.

823
00:48:28,970 --> 00:48:31,250
7 halvim, sest see on vastupidises järjekorras.

824
00:48:31,250 --> 00:48:34,920
>> Nii et siin on 7. Kust 7 kuuluvad? Kindlasti minu taga.

825
00:48:34,920 --> 00:48:39,460
Aga nüüd 7 kuulub tegelikult ei ole kohe minu taga aga taga number 8,

826
00:48:39,460 --> 00:48:41,880
nii et ma pean ütlema, et "Vabandage, nr 8, kas te saaksite liikuda sel viisil

827
00:48:41,880 --> 00:48:44,640
"Et teha ruumi 7?" Nüüd ma esineb 6.

828
00:48:44,640 --> 00:48:48,530
"Oh, vabandage mind, nr 8 ja nr 7, saate liikuda, et teha ruumi 6?"

829
00:48:48,530 --> 00:48:52,360
Nii et teiste sõnadega, koos sisestamise sorteerida, kuigi ma ei tee palju liikumist,

830
00:48:52,360 --> 00:48:56,330
inimesed minu selja taga teevad palju tööd, ja et ju maksma kellegi aega.

831
00:48:56,330 --> 00:48:58,000
See läheb maksma arvuti aega.

832
00:48:58,000 --> 00:49:01,450
Nii et kui tegemist on asetatud omamoodi me veel kannatama.

833
00:49:01,450 --> 00:49:06,260
Kui hakkate lisades kuni koguarvust samme, me lõpuks lööb umbes n ruudus

834
00:49:06,260 --> 00:49:11,160
sest need kutid on vaja teha ruumi inimeselt lisatakse tagasi sellesse nimekirja.

835
00:49:11,160 --> 00:49:15,960
Ja nii sel juhul teeta on lihtsalt ei kohaldata eelkõige lugu käepärast.

836
00:49:15,960 --> 00:49:21,100
See on kõik tore ja hea. Meil on need 3 erinevat võimalust rääkimise sõiduaega.

837
00:49:21,100 --> 00:49:26,370
Kuid mida see tegelikult tähendab reaalselt, kui me tegelikult püüame kood kuni algoritm?

838
00:49:26,370 --> 00:49:31,620
>> Las ma ettepaneku, et seal on isegi parem algoritm seal

839
00:49:31,620 --> 00:49:33,740
et endal on mõned kompromissid.

840
00:49:33,740 --> 00:49:36,890
Me läheme seda kutsuda liita omamoodi, ja see on omamoodi see maagiline algoritm

841
00:49:36,890 --> 00:49:42,840
et lihtsalt toimib kiiremini kuidagi, ja see on nii lihtne väljendada, vähemalt pseudokoodi.

842
00:49:42,840 --> 00:49:46,900
Rakendamise algoritmi Tarkvaraprojekteerimise saab olema järgmine.

843
00:49:46,900 --> 00:49:50,860
Kui olete antud n elementi - n arvu n inimesed, olenemata - esimene seal on terve mõistuse kontrolli all.

844
00:49:50,860 --> 00:49:56,340
Kui n on väiksem kui 2, liita omamoodi lihtsalt peatub. See käib nii rääkida.

845
00:49:56,340 --> 00:50:00,830
Miks te lõpetate kui n on väiksem kui 2? >> [Kuuldamatu õpilase vastus]

846
00:50:00,830 --> 00:50:04,480
Õigus. Ja jälle n ei ole nimestikus numbrit, n on suurus nimekirjast.

847
00:50:04,480 --> 00:50:07,660
Kui n on väiksem kui 2, mis tähendab, et teie loend on kas 1,

848
00:50:07,660 --> 00:50:09,640
kuhu ilmselt järjestatud kui see on 1 number,

849
00:50:09,640 --> 00:50:11,710
või 0, mille puhul pole midagi sorteerida,

850
00:50:11,710 --> 00:50:13,570
seega peame sellist tugipunkti.

851
00:50:13,570 --> 00:50:20,350
Kui loend on nii lühike, et seal on lihtsalt midagi teha, sõna otseses mõttes ei tee midagi. Tagasi.

852
00:50:20,350 --> 00:50:25,090
Vastasel sortida vasakul pool elemendid, seejärel sortida paremal pool elemendid,

853
00:50:25,090 --> 00:50:27,410
siis liita 2 järjestatud pooleks.

854
00:50:27,410 --> 00:50:32,130
>> Selline tundub veidi petavad mille ma küsin sinu käest, kuidas sortida elemendid

855
00:50:32,130 --> 00:50:34,900
ja sa räägid mulle, "Sorteerimine vasakul pool, sorteerida paremal pool."

856
00:50:34,900 --> 00:50:37,240
Ma olen nagu, "Olgu. Kuidas sorteerida vasakul pool?"

857
00:50:37,240 --> 00:50:40,670
"Sorteeri vasakul pool vasakul pool, sorteerida paremal pool vasakul pool, ja siis teinud."

858
00:50:40,670 --> 00:50:44,060
Sa oled selline tsükliliselt määratleda, mida tähendab sorteerida,

859
00:50:44,060 --> 00:50:46,790
aga tuleb välja, et on tegelikult geniaalne käesolevas asjas.

860
00:50:46,790 --> 00:50:50,230
See ei ole tõesti see nõiaring, et kunagi lõpeb

861
00:50:50,230 --> 00:50:52,550
sest see ei lõpe, kui? >> [Üliõpilane] Kui jõuad 1 asi.

862
00:50:52,550 --> 00:50:54,220
Kui jõuad 1 asi.

863
00:50:54,220 --> 00:50:57,850
Nii et kuigi võite alustada 8 inimest ja ma ütlen, "Sorteerimine vasakul pool need inimesed,

864
00:50:57,850 --> 00:51:00,480
need 4 inimest, "siis ma ütlen:" Kuidas sorteerida vasakul pool? "

865
00:51:00,480 --> 00:51:03,450
"Noh, sorteerida 2 inimest siin." Ja siis oled nagu, "Olgu."

866
00:51:03,450 --> 00:51:05,520
"Kuidas sa sortida vasakul pool need inimesed?"

867
00:51:05,520 --> 00:51:09,040
"Just sorteerida seda 1 inimene siin." Mis on geniaalne ilmutus nüüd?

868
00:51:09,040 --> 00:51:13,050
Ma pean sortida 1 inimene. Valmis. Ma ei pea tegema muud tööd.

869
00:51:13,050 --> 00:51:16,580
Aga nüüd on mul sortida see inimene, kuid nad ühele isikule, pole midagi teha.

870
00:51:16,580 --> 00:51:21,490
>> Nii maagiline ilmselt on selles Kolmas samm: ühendada järjestatud pooleks.

871
00:51:21,490 --> 00:51:25,770
Nii et ühendada omamoodi võtab see suurepärane ülevaade, et kui sa murda suur probleem alla

872
00:51:25,770 --> 00:51:28,650
sisse 2 väiksemat, identselt suurusega probleeme

873
00:51:28,650 --> 00:51:32,710
ja siis lihtsalt selline liim väiksem lahendusi koos lõpus,

874
00:51:32,710 --> 00:51:34,720
Pakun, et me saame teha palju, palju parem [koputades heli]

875
00:51:34,720 --> 00:51:38,050
kui mõni valik omamoodi või sisestamise omamoodi.

876
00:51:38,050 --> 00:51:40,690
Ma olen tegelikult unustades, et pool tundi, aga ma tõesti ei tea, mis toimub

877
00:51:40,690 --> 00:51:45,040
väljaspool täna. [Whirring heli] [naer]

878
00:51:45,040 --> 00:51:49,660
Nii et vaatame, kas me näeme seda on vähe abi meie sõber Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Seal on 2 suurt sammu protsessis ühendamise omamoodi.

880
00:51:52,810 --> 00:51:56,400
Esiteks, pidevalt jagada nimekirja tassi pooleks

881
00:51:56,400 --> 00:51:59,610
kuni meil on hunnik nimekirjad vaid 1 tass neid.

882
00:51:59,610 --> 00:52:02,150
Ärge muretsege, kui loend sisaldab paaritu arv

883
00:52:02,150 --> 00:52:04,830
ja te ei saa teha täiesti selgepiiriline nende vahel.

884
00:52:04,830 --> 00:52:08,740
Lihtsalt suvaliselt valida, millist nimekirja lisada pildi tassi sisse

885
00:52:08,740 --> 00:52:11,320
Nii et olgem jagada neid nimekirju.

886
00:52:12,420 --> 00:52:14,570
Nüüd meil on 2 nimekirju.

887
00:52:18,930 --> 00:52:20,930
Nüüd on 4 nimekirju.

888
00:52:25,730 --> 00:52:28,740
Nüüd on meil 8 nimistut, mille ühe tassi iga nimekirja.

889
00:52:28,740 --> 00:52:31,520
Nii et see on mu 1. etapp.

890
00:52:31,520 --> 00:52:37,280
Sest 2.etapp me korduvalt ühendada paari nimekirjad kasutades ühendamise algoritm oleme õppinud varem.

891
00:52:37,280 --> 00:52:44,320
Ühinevad 108 ja 15 on lõpuks nimekiri 15, 108.

892
00:52:45,240 --> 00:52:51,330
Ühinevad 50 ja 4 me lõpetame 4, 50.

893
00:52:51,330 --> 00:52:56,950
Ühinevad 8 ja 42 me lõpetame 8, 42.

894
00:52:57,790 --> 00:53:04,360
Ja ühineva 23 ja 16 me lõpetame 16, 23.

895
00:53:04,360 --> 00:53:08,030
Nüüd kõik meie nimekirjad on suurusega 2.

896
00:53:08,030 --> 00:53:10,980
Pange tähele, et iga 4 nimekirjad on sorteeritud,

897
00:53:10,980 --> 00:53:14,230
nii saame alustada ühinevad paari nimekirjad uuesti.

898
00:53:14,230 --> 00:53:22,150
Ühinevad 15 ja 108 ja 4 ja 50 kõigepealt võtta 4, siis 15,

899
00:53:22,150 --> 00:53:26,250
siis 50, siis 108.

900
00:53:26,250 --> 00:53:33,020
Ühinevad 8, 42 ja 16, 23 me esimest korda võtma 8, siis 16,

901
00:53:33,020 --> 00:53:37,170
siis 23, siis 42.

902
00:53:37,170 --> 00:53:42,490
Nii et nüüd on meil vaid 2 nimekirjad suurus 4, millest igaüks on järjestatud.

903
00:53:42,490 --> 00:53:45,940
Nii et nüüd me koondada need 2 on loetletud.

904
00:53:45,940 --> 00:53:54,230
Esiteks võtame 4, siis võtame 8, siis me võtame 15

905
00:53:54,230 --> 00:54:05,280
ja 16 ja 23 ja 42 ja 50 ja 108.

906
00:54:05,280 --> 00:54:09,020
Ja me oleme valmis. Meil on nüüd järjestatud nimekirja.

907
00:54:09,020 --> 00:54:13,740
>> Rob oli selline ära midagi, mida me veel teinud ei ole.

908
00:54:13,740 --> 00:54:16,540
Arvati, kuid me tegelikult ei tee seda.

909
00:54:16,540 --> 00:54:19,230
Ta tegi midagi füüsiliselt koos tassi, mis viitab

910
00:54:19,230 --> 00:54:23,680
ta oli kulutuste mõnda ressurssi peale aja. >> [Üliõpilane] Space. >> See oli ruumi.

911
00:54:23,680 --> 00:54:27,360
Asjaolu, et ta oli selline bi-taseme tabeli, kus oli ruumi siin

912
00:54:27,360 --> 00:54:31,960
ja ruumi siin all tegelikult tähendab, et ta kasutab kaks korda nii palju ruumi

913
00:54:31,960 --> 00:54:36,390
kui mõni meie algoritmid siiani - sisestamise sorteerida, mull sorteerida, või valik omamoodi -

914
00:54:36,390 --> 00:54:40,780
kuid ta oli võimendades seda lisaruumi selline käik asju edasi ja tagasi

915
00:54:40,780 --> 00:54:42,600
hoides asjad korras.

916
00:54:42,600 --> 00:54:47,540
Ja kuigi see tundub saime järjestatud loetelu, mis tundus see võttis aega.

917
00:54:47,540 --> 00:54:51,060
Tegelikult mida Rob tegin oli täpselt see algoritm.

918
00:54:51,060 --> 00:54:56,780
Ta võttis esimest korda probleemi suurus n, jagas selle vasakul pool ja paremal pool.

919
00:54:56,780 --> 00:54:59,380
Siis ta kolis karikatega. Siis ta kordas, et protsess.

920
00:54:59,380 --> 00:55:03,390
Ta jagas 4 jagatakse 2 seeriat 2 üle siin ja siin.

921
00:55:03,390 --> 00:55:08,520
Siis ta kordas, et protsess ja jagatud 2 arvesse 2 komplekti 1 iga nende eri tassi.

922
00:55:08,520 --> 00:55:11,000
Ja see, kui geniaalne võimalus tekib.

923
00:55:11,000 --> 00:55:15,840
Sel hetkel on lugu, Rob oli 8 nimekirjad suurus 1,

924
00:55:15,840 --> 00:55:18,860
mis kõik on järjestatud juba.

925
00:55:18,860 --> 00:55:20,630
>> Nii siis mida ta edasi teha?

926
00:55:20,630 --> 00:55:25,260
Paarikaupa ta võttis seda järjestatud nimekirja ja seda järjestatud nimekirja ja ühendada neid.

927
00:55:25,260 --> 00:55:28,200
Siis ta võttis selle ühe ja liitis need, siis see üks ja liitis need,

928
00:55:28,200 --> 00:55:30,670
siis see üks ja ühendatakse neid.

929
00:55:30,670 --> 00:55:32,390
Ja siis mida ta järgmisena tegema?

930
00:55:32,390 --> 00:55:36,580
Ta siis uuesti ühendada suuremate nimekirjade ja seejärel uuesti ühendati suurem nimekirju.

931
00:55:36,580 --> 00:55:41,170
Ja kui sina arvad sellest lihtsalt intuitiivselt nüüd, mida ta tegelikult teeb?

932
00:55:41,170 --> 00:55:45,450
Ta oli jagades probleemi pooleks, pooleks, pooleks, pooleks

933
00:55:45,450 --> 00:55:47,600
selleks, et saada need super väike nimekirju.

934
00:55:47,600 --> 00:55:51,290
Siis ta oli selline kombineerimine double, double, double, double.

935
00:55:51,290 --> 00:55:54,120
Nii ta teeb kaks korda nii palju tööd kui oleme näinud seni

936
00:55:54,120 --> 00:55:56,930
koos midagi seotud jaga ja valitse, kuid pole hullu.

937
00:55:56,930 --> 00:55:59,630
Kaks korda nii palju tööd ei ole nii suur asi. See on lihtsalt konstandiks.

938
00:55:59,630 --> 00:56:03,920
Ja palju nagu meie aritmeetiline avaldis enne, ma lihtsalt läheb maha kriipsutama pidev tegurid

939
00:56:03,920 --> 00:56:10,170
nagu korda 2. Keda huvitab? Kui see 2 miljardit korda 2, see on veel palju samme.

940
00:56:10,170 --> 00:56:13,160
Nii et see ühendamine samm tundub olevat Võtmeküsimuseks.

941
00:56:13,160 --> 00:56:17,000
Lähme käime läbi selle lihtsalt arvuliselt enne - Oh, see on mitte jätkata veel.

942
00:56:17,000 --> 00:56:22,890
Lähme käime läbi selle arvuliselt vaid tegelikult näha, kuidas see mängib välja.

943
00:56:22,890 --> 00:56:25,940
See on enamasti natuke vaese mehe animatsioon.

944
00:56:25,940 --> 00:56:27,750
Teeme ettepaneku seda.

945
00:56:27,750 --> 00:56:31,480
Sõiduaega ühendamise omamoodi - me lihtsalt vaja viis räägi sellest.

946
00:56:31,480 --> 00:56:34,380
See ei ole matemaatika, see on lihtsalt selline sisutihe viis väljendada ennast.

947
00:56:34,380 --> 00:56:39,080
Nii T näitab aega ja n on mis? >> [Üliõpilane] suurus -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] Probleemi ulatuse, inimeste arvu.

949
00:56:41,400 --> 00:56:45,470
Nii et ma väidan, et sõiduaega sorteerida n inimesed ei kavatse olla 0 aega

950
00:56:45,470 --> 00:56:50,290
kui n on vähemalt 2, sest kui sul on 1 tass või ei tassi, siis pole midagi sorteerida.

951
00:56:50,290 --> 00:56:55,160
Aga üldiselt ma lähen ettepaneku, et sõiduaega sorteerida n elementi

952
00:56:55,160 --> 00:56:59,350
saab olema aeg, mis kulub, et sorteerida vasakul poolel pluss paremal pool

953
00:56:59,350 --> 00:57:03,110
pluss - mis see veel + n? >> [Üliõpilane] Merge omamoodi.

954
00:57:03,110 --> 00:57:07,260
[Malan] See on tegelikult ühinevad, sest kui sul on n / 2 elementi siia

955
00:57:07,260 --> 00:57:11,500
ja teil on n / 2 elementi siia, kui palju aega läheb aega, et need ühendada?

956
00:57:11,500 --> 00:57:15,050
Just nagu Rob, sa pead sikutama see siin, võibolla sikutama üle siin,

957
00:57:15,050 --> 00:57:17,120
sikutama siia, kisu siia, kisu siin.

958
00:57:17,120 --> 00:57:19,400
Sa pead puudutada iga tassi korraga.

959
00:57:19,400 --> 00:57:22,030
Ja kui seal on 4 tassi pluss 4 tassi, mis on 8 tassi

960
00:57:22,030 --> 00:57:25,200
või üldisemalt, 8 n tassi.

961
00:57:25,200 --> 00:57:28,470
Nii ühineva samm saame väljendada kui n,

962
00:57:28,470 --> 00:57:31,330
ja mis sõna otseses mõttes tähendab seda, mitu korda Rob füüsiliselt puudutada

963
00:57:31,330 --> 00:57:33,410
üks neist vahtpolüstürool cups.

964
00:57:33,410 --> 00:57:35,850
Nii et olgem nüüd teha suvalise näite.

965
00:57:35,850 --> 00:57:41,850
Kui seal on 16 tassi, mis on töötamise aeg sorteerimine, kasutades Rob algoritm, 16 tassi?

966
00:57:41,850 --> 00:57:44,710
See on 2 korda, kui palju aega kulub, et sorteerida 8 tassi

967
00:57:44,710 --> 00:57:46,920
sest meil on 8 tassi siia, 8 tassi siin.

968
00:57:46,920 --> 00:57:51,520
Ma ei tea, kui kaua see võtab, nii et me oleme üldistades seda T hetkel.

969
00:57:51,520 --> 00:57:53,320
Kes teab, mis see on?

970
00:57:53,320 --> 00:57:58,990
Aga nüüd ma saan omamoodi rekursiivselt või korduvalt küsida sama küsimuse.

971
00:57:58,990 --> 00:58:01,920
Kui palju aega läheb aega, et sortida 8 tassi?

972
00:58:01,920 --> 00:58:07,030
8 tassi ma ütlen võtab palju aega kulub, et sorteerida 4 tassi pluss 4 tassi,

973
00:58:07,030 --> 00:58:08,880
siis ühinevad nad kokku.

974
00:58:08,880 --> 00:58:13,080
Olgu. Me sattumist tsükkel juba. Kui kaua läheb aega, et sortida 4 tassi?

975
00:58:13,080 --> 00:58:19,150
Aega kulub sortida 4 tassi on 2 tassi pluss 2 tassi sorteerimine pluss ühinevate protsessi.

976
00:58:19,150 --> 00:58:21,440
Olgu. Kui kaua läheb aega, et sortida 2 tassi?

977
00:58:21,440 --> 00:58:26,290
2 tassi on palju aega kulub, et sortida 1 tass pluss aeg, mis kulub, et järjestada ühe tassi

978
00:58:26,290 --> 00:58:29,040
pluss palju aega kulub, et ühendada, mis on vaid 2.

979
00:58:29,040 --> 00:58:33,340
>> Olgu. Viimane küsimus. Kui kaua läheb aega, et sortida 1 tass?

980
00:58:33,340 --> 00:58:37,260
Siin on aluspõhimõtted, et me ennustasime me tahaks tabas varem.

981
00:58:37,260 --> 00:58:42,250
Asjaolu, et ta ei võta tööle üldse sorteerida väikseim probleeme

982
00:58:42,250 --> 00:58:44,120
tähendab, et nüüd, omamoodi algkool stiil,

983
00:58:44,120 --> 00:58:46,460
saame lihtsalt minema hakata ühendades need numbrid uuesti sisse

984
00:58:46,460 --> 00:58:50,630
Me teame nüüd, mida T 1 on, et ma saaks ühendada 0 T 1.

985
00:58:50,630 --> 00:58:54,420
See annab mulle vastuse T 2, mis ma siis saate ühendada kõrgemal.

986
00:58:54,420 --> 00:58:56,930
See annab mulle T 4, mida ma ei ühendan kõrgemal.

987
00:58:56,930 --> 00:58:58,920
See annab mulle T, 8., mida ma ei ühendan kõrgemal.

988
00:58:58,920 --> 00:59:04,330
Ja kui ma tõesti välja, et matemaatika, ühendades need vastused,

989
00:59:04,330 --> 00:59:08,590
Siis ma saan T 16 on 64.

990
00:59:08,590 --> 00:59:12,090
Ja mida see 64 koosneb?

991
00:59:12,090 --> 00:59:15,700
Kui T on 16, jah, see on 16 korda 4.

992
00:59:15,700 --> 00:59:20,120
Nii ma väita nüüd, et töötamise aeg see asi nimega liita omamoodi -

993
00:59:20,120 --> 00:59:22,590
ja see saab olema fanciest on need, mida me oleme näinud siiani -

994
00:59:22,590 --> 00:59:26,160
läheb nimetatakse n log n

995
00:59:26,160 --> 00:59:31,140
sest kui mitu korda võib röövida jagada terve hunnik tassi poole? Logi n.

996
00:59:31,140 --> 00:59:34,370
See on sama nagu telefoniraamat Näiteks see sama ise loendada näiteks.

997
00:59:34,370 --> 00:59:36,380
>> Mitu korda saab sa jagad midagi pooleks?

998
00:59:36,380 --> 00:59:38,410
Kuid seal on see ühineva samm.

999
00:59:38,410 --> 00:59:42,920
Sa oleks võinud jagada tassi pooleks ja jälle ja jälle,

1000
00:59:42,920 --> 00:59:45,640
kuid iga kord, kui lähed on ühendada.

1001
00:59:45,640 --> 00:59:48,270
Ja me varem öelnud, et ühineva n tassi võtab n samme

1002
00:59:48,270 --> 00:59:52,060
sest sa pead kisu tassi, kisu tassi, ja sa pead puudutada iga tassi üks,

1003
00:59:52,060 --> 00:59:53,510
nagu Rob tegi.

1004
00:59:53,510 --> 00:59:59,430
Nii et kui me teeme midagi log n korda ja me teeme n asju Igal neist iteratsioone

1005
00:59:59,430 --> 01:00:03,090
kõik need halvings, meil on n korda log n.

1006
01:00:03,090 --> 01:00:07,220
Nii et kui me lülitame sisse 16 Selles näites 16 korda logi 16. -

1007
01:00:07,220 --> 01:00:10,600
ärge muretsege, miks see nii on nüüd, sest ma ei ole koostatud põhi -

1008
01:00:10,600 --> 01:00:16,100
kuid samamoodi baasi 2 16 on 4, 16 korda 4 on 64.

1009
01:00:16,100 --> 01:00:22,350
Aga vastupidi, kui me kasutaksime mull sorteerida või valik omamoodi või sisestamise omamoodi 16 numbrid,

1010
01:00:22,350 --> 01:00:26,420
milline oleks sõiduaega olnud, kui n on 16?

1011
01:00:26,420 --> 01:00:33,310
Oleks 16 ruudus, mis on 256, mis isegi kui sa ei ole päris järginud kõiki matemaatika,

1012
01:00:33,310 --> 01:00:38,390
256 on suurem kui 64. See on tõesti maagiline Buffee siin.

1013
01:00:38,390 --> 01:00:41,990
Ja mõistma, et töö kaudu see väiksemates näiteid nagu te edasi pset

1014
01:00:41,990 --> 01:00:44,260
muudab kõik palju selgem.

1015
01:00:44,260 --> 01:00:49,070
Aga mida see tegelikult tähendab nii tunda seda algoritm on selline:

1016
01:00:49,070 --> 01:00:54,520
Kui me tegelikult vaadata ühendamise omamoodi siin - las ma tõmban ta üles selles aknas siin -

1017
01:00:54,520 --> 01:00:58,560
see on veidi teistsugune näide, kus meil on kõik 3 neist algoritme -

1018
01:00:58,560 --> 01:01:01,440
mull, valik ja ühendamine - lihtsalt kõrvuti.

1019
01:01:01,440 --> 01:01:03,740
>> Nad on kõik algas juhuslikult baari, ja see on hea.

1020
01:01:03,740 --> 01:01:06,240
Keegi ei ole oluline eelis teiste üle.

1021
01:01:06,240 --> 01:01:09,500
Ma lähen hetke pärast käsku kõik need animatsioonid - Start Start Start -

1022
01:01:09,500 --> 01:01:13,270
nii kiiresti kui saan, nii et umbes nii, nad kõik algavad samal ajal,

1023
01:01:13,270 --> 01:01:17,450
ja Vaatleme et mull sorteerida on Halvima sõiduaega on mis? >> [Üliõpilane] N ruudus.

1024
01:01:17,450 --> 01:01:21,560
N ruudus. Valik omamoodi halvim juhtum sõiduaega on? N ruudus.

1025
01:01:21,560 --> 01:01:25,150
Ja ühendada sorteerida on ilmselt - isegi kui sa ei ole päris järgima kõiki matemaatika nüüd,

1026
01:01:25,150 --> 01:01:30,610
siis see muutub palju intuitiivsem aja jooksul - on, me väidame, n korda log n.

1027
01:01:30,610 --> 01:01:35,210
Ja kuna log n on rangelt väiksem kui n kui meil on suured numbrid,

1028
01:01:35,210 --> 01:01:40,230
n korda log n on väiksem kui n korda n või n ruudus.

1029
01:01:40,230 --> 01:01:44,410
Mida see tunne on tegelikult olla parem algoritm nii sõiduaega,

1030
01:01:44,410 --> 01:01:50,380
n korda log n erinevalt n ruudus? Läheb lahti. Klõpsake nuppu, käsku.

1031
01:01:55,690 --> 01:01:58,650
>> See on, mida see tähendab kasutada midagi ühendamise omamoodi.

1032
01:01:58,650 --> 01:02:01,680
Meil on praegu. Vaatame, mis juhtub siin.

1033
01:02:09,440 --> 01:02:12,440
[Chuckles] Kelle raha on mull sorteerida?

1034
01:02:14,960 --> 01:02:16,730
See sõltub pigem sisend mõnikord.

1035
01:02:16,730 --> 01:02:18,120
Vaatame.

1036
01:02:18,120 --> 01:02:23,320
Tule. Tundub, nagu ta on järele jõudmas. >> [Üliõpilane] Mine, mull sorteerida!

1037
01:02:23,320 --> 01:02:27,370
[Õpilased vulisev]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Jah, jah.

1039
01:02:29,120 --> 01:02:34,520
[Õpilased vulisev] Mine, mine, mine!

1040
01:02:37,210 --> 01:02:40,450
[Kõik cheering] [aplaus]

1041
01:02:40,450 --> 01:02:46,240
Nii et nüüd vaid 1 viimane, lõplik demo, kui see on natuke keeruline wrap meelt umbes matemaatika

1042
01:02:46,240 --> 01:02:49,280
või omamoodi visualiseerimine seal saab tegelikult kuulata kiirused

1043
01:02:49,280 --> 01:02:51,000
erinevate algoritmide erinevalt.

1044
01:02:51,000 --> 01:02:53,900
See on animatsioon keegi teinud, et tegelikult kaastöötajad kõlab

1045
01:02:53,900 --> 01:02:56,980
protsessiga vahetada ja tulpade kõrgust.

1046
01:02:56,980 --> 01:03:00,440
Nagu me näeme siin, seal on veel mõned sorteerimise algoritme seal, et inimesed on välja mõelnud.

1047
01:03:00,440 --> 01:03:03,660
See esimene saab olema sisestamise järgi, ja see lendab läbi

1048
01:03:03,660 --> 01:03:07,090
ja teile kuuldav tunne kuidas neid erinevaid algoritme töö.

1049
01:03:07,090 --> 01:03:09,080
Siin on sisestamise omamoodi.

1050
01:03:09,080 --> 01:03:18,410
[Elektroonilise piiksumist]

1051
01:03:18,410 --> 01:03:20,730
[Malan] mull sorteerida.

1052
01:03:20,730 --> 01:03:46,850
[Kiiremini elektroonilise piiksumist]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Valik omamoodi.

1054
01:03:48,950 --> 01:04:03,580
[Kiiremini elektroonilise piiksumist]

1055
01:04:03,580 --> 01:04:05,770
[Malan] Merge omamoodi.

1056
01:04:05,770 --> 01:04:17,270
[Elektroonilise piiksumist]

1057
01:04:17,270 --> 01:04:20,180
[Piiksumist aeglustab] [naer]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Gnome omamoodi.

1059
01:04:22,590 --> 01:04:38,580
[Elektroonilise piiksumist]

1060
01:04:39,740 --> 01:04:46,150
>> See on CS50. Näeme järgmisel nädalal. [Aplaus ja cheering]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]