1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [3 nedēļas, Turpinājums]

2
00:00:02,280 --> 00:00:04,110
>> [David J. Malan - Hārvarda]

3
00:00:04,110 --> 00:00:07,130
>> [Tas ir CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Labi. Laipni lūdzam atpakaļ. Tas ir CS50 un tas ir beigu 3 nedēļas.

5
00:00:11,010 --> 00:00:14,680
>> Tātad tiem svešs, pagājušā gada Hārvardas uzsāka ko sauc Inovāciju Lab,

6
00:00:14,680 --> 00:00:18,530
vai i-lab, kas ir brīnišķīga ēka pāri upei uz HBS pilsētiņas

7
00:00:18,530 --> 00:00:22,640
kas ir atvērta koledžu studentiem, ĢAA studentiem, studenti no visas pilsētiņas,

8
00:00:22,640 --> 00:00:27,000
ieskaitot fakultāte, un tā ir vieta, kur sanākt kopā, lai strādātu pie inovatīviem lietām,

9
00:00:27,000 --> 00:00:29,180
īpaši uzņēmējdarbības lietas

10
00:00:29,180 --> 00:00:33,410
ja un 0 vai vairāk draugu domā par kaut ko dara uzņēmējdarbības

11
00:00:33,410 --> 00:00:37,080
nu šajā klasē, pēc šīs klases, vai ārpus tās.

12
00:00:37,080 --> 00:00:41,540
>> Tātad viena no lietām, ko viņi dara pāri J termiņā ir šie braucieni,

13
00:00:41,540 --> 00:00:44,510
no kuriem viens ir New York, viens no kuriem ir Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
Telpa ir ļoti ierobežota, bet tas ir iespēja berzēt pleciem ar MBA

15
00:00:47,530 --> 00:00:52,200
un pēcdiploma studentiem pāri Campus un faktiski tērēt laiku šajās attiecīgajās jomās

16
00:00:52,200 --> 00:00:55,500
čatā augšu jaunizveidotiem, čatā augšu uzņēmējus un tamlīdzīgi.

17
00:00:55,500 --> 00:00:57,870
Tātad, ja interese, pārbaudiet šo URL šeit.

18
00:00:57,870 --> 00:01:01,220
Tas ir pieejams arī uz slaidiem tiešsaistē.

19
00:01:01,220 --> 00:01:04,610
>> Vai mēs pieklusināt māju audio tikai mazliet?

20
00:01:04,610 --> 00:01:08,640
Ja jūs vēlētos, lai pievienoties mums pusdienās šo piektdien, 13:15 jo Fire & Ice, lūdzu galvu tur.

21
00:01:08,640 --> 00:01:11,390
Atvainojos, ja veidlapa ir jau aizpildīta ar laiku jums tur.

22
00:01:11,390 --> 00:01:13,750
Taču mēs turpināsim šo tradīciju vēlāk.

23
00:01:13,750 --> 00:01:17,350
>> Šodien mēs turpinām augstāka līmeņa diskusiju par dažādām problēmām, ka mēs varam atrisināt,

24
00:01:17,350 --> 00:01:21,330
koncentrējoties daudz mazāk, šodien vismaz uz kodu un vēl daudz vairāk par idejām.

25
00:01:21,330 --> 00:01:24,720
Tāpēc domāju, ka atpakaļ līdz 0 nedēļā, kad mēs saplēsa tālruņa grāmatu pusē,

26
00:01:24,720 --> 00:01:28,260
gada kura mērķis bija kaut ko darīt, protams, mazliet dramatisks

27
00:01:28,260 --> 00:01:32,360
bet nosūtīt punktu, ka meklēšana nav jābūt, obligāti,

28
00:01:32,360 --> 00:01:35,100
kā skaidrs pēc pirmā acu uzmetiena, kā jūs varētu domāt.

29
00:01:35,100 --> 00:01:40,200
Un problēmu risināšana vispār varētu nebūt vienmēr būs labākā -

30
00:01:40,200 --> 00:01:44,130
Pašsaprotama risinājums varētu nebūt labākais.

31
00:01:44,130 --> 00:01:47,300
Tāpēc mums bija šī tālruņa grāmatu un, godīgi sakot, mums visiem šajā telpā bija instinktiem,

32
00:01:47,300 --> 00:01:51,470
visticamāk, lai sāktu vidū, meklējot Mike Smith un tad iet pa kreisi vai pa labi

33
00:01:51,470 --> 00:01:54,280
pamatojoties uz neatkarīgi alfabēta burts mums gadījās nonākt.

34
00:01:54,280 --> 00:01:57,560
>> Bet ka vienkārša ideja, ka mēs cilvēkiem ir pašsaprotama tik ilgi

35
00:01:57,560 --> 00:02:00,670
tiešām vajadzētu sākt nākt uz priekšgalā jūsu prātā

36
00:02:00,670 --> 00:02:03,900
jo, kā problēmas iegūt daudz sarežģītāka nekā tālruņa grāmatu,

37
00:02:03,900 --> 00:02:07,420
šie paši vienkārši, izcili atklāsmes ir tas, ko gatavojas ļauj mums

38
00:02:07,420 --> 00:02:10,259
atrisināt daudz sarežģītāka un interesantāka problēmas,

39
00:02:10,259 --> 00:02:12,930
Starp tām dažas no lietām, ko mēs uzskatām par pašsaprotamu jau šajās dienās.

40
00:02:12,930 --> 00:02:15,720
Miljardiem tīmekļa lapas, kas tur, un vēl Google un Bing un tamlīdzīgi

41
00:02:15,720 --> 00:02:17,660
ir iespēja atrast lietas mums tāpat.

42
00:02:17,660 --> 00:02:22,300
Tas nav noticis, izmantojot lineāro meklēšanu, meklējot visos iespējamos interneta lapas.

43
00:02:22,300 --> 00:02:25,290
Facebook ir spējīgs pateikt, kas visiem saviem draugiem ir vai draugu draugi,

44
00:02:25,290 --> 00:02:28,250
un ka pārāk var izdarīt šķietami vienā mirklī šajās dienās

45
00:02:28,250 --> 00:02:30,820
pat ja tie ir miljoniem lietotāju.

46
00:02:30,820 --> 00:02:34,250
>> Un tā kā mēs patiesībā risināt problēmas šajā mērogā galu galā samazinās

47
00:02:34,250 --> 00:02:37,830
uz idejām mēs paskatījās pieejama 0 nedēļā un mazliet vairāk šodien.

48
00:02:37,830 --> 00:02:42,320
Mēs ne atkārtoti izpildīt šo algoritmu, bet atgādināt mēs arī darījām nedēļā 0 šī uzdevuma

49
00:02:42,320 --> 00:02:44,780
kur mums bija visi piecelties, uzņemties numuru 1,

50
00:02:44,780 --> 00:02:48,720
un tad mums bija ikvienam sevi skaitīšanas ko pārī off, pievienojot savu telefona numurus,

51
00:02:48,720 --> 00:02:51,930
tad puse no bandas apsēdās uz katra atkārtojuma.

52
00:02:51,930 --> 00:02:56,750
Tātad, mēs devāmies no 500 skolēniem uz 250-125 un tā tālāk.

53
00:02:56,750 --> 00:03:00,080
Bet kā mēs pirmdien paziņoja, spēcīgs ideja tur

54
00:03:00,080 --> 00:03:02,460
bija tas, ka, ja mēs dubultojies lielumu šo problēmu

55
00:03:02,460 --> 00:03:06,480
un visi no Tieslietu vai EK 10 bērni nāca atpakaļ istabā un pievienojies mums,

56
00:03:06,480 --> 00:03:09,510
labi, mēs varētu droši rēķināties, ka viss kopējais grupu

57
00:03:09,510 --> 00:03:13,380
tikai ar vēl 1 liels atkārtojuma no cilpas, jo viņi tikai varbūt divtik

58
00:03:13,380 --> 00:03:15,630
vai EK 10 lietu nedaudz vairāk nekā divas reizes izmēru.

59
00:03:15,630 --> 00:03:18,440
Un tā mēs būtu tērēt mazliet vairāk laika,

60
00:03:18,440 --> 00:03:22,000
bet mēs nebūtu jātērē 400 vai 700 vairāk soļus.

61
00:03:22,000 --> 00:03:26,550
>> Tikai, lai krāsu šo attēlu tādā veidā, kas ir nedaudz mazāk abstrakta, pieņemsim, nav visi piecelties.

62
00:03:26,550 --> 00:03:31,100
Bet, ja tie no jums, kas izvēlējās sēdēt orķestra šodien nebūtu prāta stāvus,

63
00:03:31,100 --> 00:03:34,580
pieņemsim redzēt, ja mēs varam izdomāt starp jums, kas ir augstākā persona ir

64
00:03:34,580 --> 00:03:36,730
darot to pašu veida salīdzinošo algoritmu.

65
00:03:36,730 --> 00:03:41,830
Tātad, ja jūs sēžat orķestrī, manu atvainošanos, bet soli 1, piecelties;

66
00:03:41,830 --> 00:03:44,650
soli 2, pāris off ar Ikviens tuvumā tu,

67
00:03:44,650 --> 00:03:49,360
skaitlis, kurš ir garāks, un apsēsties, ja Jums ir īsāks.

68
00:03:49,360 --> 00:03:51,360
Tad atkārtot.

69
00:03:51,360 --> 00:03:56,280
[Studenti murmuring]

70
00:04:13,450 --> 00:04:15,320
>> Labi.

71
00:04:15,320 --> 00:04:19,010
Labi. Viens ir palicis stāvot. Kāds ir Jūsu vārds? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, jums ir garākais cilvēks orķestris sadaļā šodien.

73
00:04:21,959 --> 00:04:28,100
>> Apsveicu. [Aplausi un uzmundrinoša] Labi. Ir vieta. Tāpēc mēs atradām Andrejam.

74
00:04:28,100 --> 00:04:30,870
Bet cik ilgi tas tā ir veikusi mani, piemēram, lai atrastu Andrejam

75
00:04:30,870 --> 00:04:33,740
Šajā orķestrim sadaļā 50 + vai lai cilvēki?

76
00:04:33,740 --> 00:04:36,900
Es varētu būt veikusi diezgan vienkāršu pieeju un sākt šeit.

77
00:04:36,900 --> 00:04:39,270
Un man ir 2 cilvēki piecelties un es tikko salīdzināt tos,

78
00:04:39,270 --> 00:04:42,120
un tad es saku, lai kurš ir nedaudz īsāks, "Labi, tu apsēdies,"

79
00:04:42,120 --> 00:04:44,380
un es esmu gatavojas atcerēties, kas garāki persona.

80
00:04:44,380 --> 00:04:49,030
Tad es atkārtoju, atkārtoju, atkārtoju, un es pakārt uz garākais personai

81
00:04:49,030 --> 00:04:51,920
līdz es atrast kādu nedaudz garāks nekā tiem, kurā brīdī

82
00:04:51,920 --> 00:04:54,950
nedaudz īsāks personai ir tad sēdēt.

83
00:04:54,950 --> 00:04:57,690
Bet šajā algoritma šajā orķestrī sadaļā, ja tur ir n no jums,

84
00:04:57,690 --> 00:05:00,480
cik soļus ir tas, ka algoritms gatavojas veikt? >> [Students] N.

85
00:05:00,480 --> 00:05:03,580
>> Tas notiek, lai n, pa labi, jo sliktākajā gadījumā, tā teikt,

86
00:05:03,580 --> 00:05:09,090
garākais cilvēks ir ļoti pēdējā persona, kas man vienkārši izlases neveiksmēm.

87
00:05:09,090 --> 00:05:14,260
Tātad sliktākajā gadījumā, darbības laiks šīs algoritms ir lineāra, tas ir n,

88
00:05:14,260 --> 00:05:18,070
kur n ir kopējais cilvēku skaits telpā, lielumu problēmu.

89
00:05:18,070 --> 00:05:19,600
Ko par šo algoritmu?

90
00:05:19,600 --> 00:05:22,080
Fakts, ka jūs visi piecēlās un tad atkal puse no jums apsēdās,

91
00:05:22,080 --> 00:05:23,950
puse no jums apsēdās, puse no jums apsēdās.

92
00:05:23,950 --> 00:05:26,070
Cik soļus, kas jāveic, ja tur ir n no jums šeit?

93
00:05:26,070 --> 00:05:30,200
[Students] N log n. >> Tas būtu sliktāk. Log n.

94
00:05:30,200 --> 00:05:32,930
>> Tātad log n, pat ja jums nav gluži atcerēties, ko logaritms ir,

95
00:05:32,930 --> 00:05:38,410
tagad, tikai saprotu, ka tas attiecas kaut uz šo pusi un pusi un pusi.

96
00:05:38,410 --> 00:05:41,000
Tai nav jābūt koeficientu 2. Tas varētu būt faktors gada 3.

97
00:05:41,000 --> 00:05:46,560
Bet tas ir tas atkārtošanās paša veida faktoru šāda ka problēmas lielums sākas šeit

98
00:05:46,560 --> 00:05:49,620
bet tad uzreiz iet šeit, tad šeit, tad šeit, tad šeit.

99
00:05:49,620 --> 00:05:53,580
Jūs neesat lietojat nelielu kodumi no problēmas, jūs tiešām kapāšanas prom pie tā

100
00:05:53,580 --> 00:05:56,160
ar lielu samazinājās sagrābt katru reizi.

101
00:05:56,160 --> 00:06:00,810
Tāpēc mums bija 50 cilvēki, tad 25, tad 12 ½ vai 13 cilvēki stāv,

102
00:06:00,810 --> 00:06:05,370
tad 6 ½ un tā tālāk, līdz beidzot tikai Endrjū palika stāvot.

103
00:06:05,370 --> 00:06:08,710
Tāpēc mēs esam gatavojas aicināt ka žurnālu n, un jūs varat iztēloties šo šādi.

104
00:06:08,710 --> 00:06:12,570
Atceros šo bildi šeit, kur lineāra algoritms ir kā sarkanās līnijas tur,

105
00:06:12,570 --> 00:06:17,520
dzeltenā līnija bija skaitīšanas par 2s algoritmu, ka mēs izmantojām, lai uzskaitītu studentiem

106
00:06:17,520 --> 00:06:22,300
pagātnē, bet šodien Svētais Grāls gatavojas saglabāt šo zaļo līniju

107
00:06:22,300 --> 00:06:25,470
kur, ja mēs dubultojies to cilvēku skaits, kas orķestra sadaļā vai vienkārši teica,

108
00:06:25,470 --> 00:06:29,170
ellē, pieņemsim ir ikvienam visā telpā piecelties, nav tik liels darījumu

109
00:06:29,170 --> 00:06:31,560
jo mēs rupji dubultot, cik daudz cilvēku ir uz leju šeit,

110
00:06:31,560 --> 00:06:33,500
1 vairāk atkārtojumu, nevis problēma.

111
00:06:33,500 --> 00:06:36,200
>> Mēs esam noskaidrojuši, Andrejs vai kurš notiek, ir garāks nekā Andrew

112
00:06:36,200 --> 00:06:38,770
ar mezzanine vai uz balkona.

113
00:06:38,770 --> 00:06:42,140
Tāpēc šo vienkāršo domu, ka mums bija tik daudz par pašsaprotamu telefona grāmatā,

114
00:06:42,140 --> 00:06:46,170
apzināties, ka ir tik daudz dažādās vietās, kā mēs varam piemērot.

115
00:06:46,170 --> 00:06:50,810
Tikai, lai iepļaukāt daži žargons - patiesībā, nevis žargona pirmkārt,

116
00:06:50,810 --> 00:06:52,750
ļaujiet man iet uz šo attēlu šeit.

117
00:06:52,750 --> 00:06:56,970
Tieši tagad mēs runājām par un n / 2 un tad log n,

118
00:06:56,970 --> 00:07:00,500
bet mēs noteikti var nākt klajā ar, kā mēs gaitā semestra,

119
00:07:00,500 --> 00:07:05,130
cita veida matemātisku formulu, lai aprakstītu šo vispārējo jēdzienu darba laika.

120
00:07:05,130 --> 00:07:07,580
Tie ir ārpus kontekstā tagad, jo mēs redzēsim pirms ilgi

121
00:07:07,580 --> 00:07:09,900
algoritmus, ka tie faktiski pārstāv.

122
00:07:09,900 --> 00:07:17,990
>> Bet pamanīt šeit lineāro līniju N, taisni, tiešām ir ļoti zems norādot tiesības tagad.

123
00:07:17,990 --> 00:07:22,950
Tas ir sava veida ilūziju, ka mēs vienkārši mainīt to, ko x ass pārstāv

124
00:07:22,950 --> 00:07:26,130
un y asi, un mēs varam darīt taisnu līniju punktu jebkurā virzienā mēs vēlamies.

125
00:07:26,130 --> 00:07:30,350
Bet tāpēc, ka tas ir tik šķietami dzīvoklis tagad

126
00:07:30,350 --> 00:07:35,690
ir tāpēc, ka mums vajadzēja, lai padarītu telpu par šo grafikā par daudz lēnāk darbojas reizes.

127
00:07:35,690 --> 00:07:39,030
Tagad zinu, ka ir dažas diezgan slikti algoritmus dzīvē,

128
00:07:39,030 --> 00:07:43,790
no kuriem daži nav veikt n pasākumus vai, vēl labāk, log n pasākumus, bet vairāk.

129
00:07:43,790 --> 00:07:48,820
Tātad virs līnijas n šeit apakšā paziņojuma tur n reizes žurnālu n,

130
00:07:48,820 --> 00:07:51,410
un mēs redzēsim, ko tas nozīmē pirms ilgi.

131
00:07:51,410 --> 00:07:56,010
Virs ka ir n rūtiņām, un mēs neesam redzējuši nevienu n kvadrātā algoritmus vēl, bet mēs esam par to.

132
00:07:56,010 --> 00:07:57,660
Un tas izskatās tiešām slikti.

133
00:07:57,660 --> 00:08:01,610
Tur ir 2 līdz n, kaut eksponenciāls, kas jūtas vēl sliktāk.

134
00:08:01,610 --> 00:08:05,760
Un vēl, savādi, tad tur ir n kubā, kas, ja jūs esat veida domāšana uz priekšu,

135
00:08:05,760 --> 00:08:10,000
ja jūs veida math, 2 līdz n faktiski kļūst daudz taisnāki,

136
00:08:10,000 --> 00:08:15,930
daudz augstāk nekā n kubā, ja paskatās asīm pietiekami tālu.

137
00:08:15,930 --> 00:08:19,890
Tāpēc pamanīt tagad šie virzieni ir patvaļīgi 2-10 uz x ass.

138
00:08:19,890 --> 00:08:21,770
>> Un ko tas nozīmē?

139
00:08:21,770 --> 00:08:23,890
Tas nozīmē, 2 cilvēki līdz 10 cilvēkiem istabā.

140
00:08:23,890 --> 00:08:27,200
Tas ir viss x nozīmē: lielums problēmu, neatkarīgi no konteksta ir.

141
00:08:27,200 --> 00:08:30,420
Un vertikālās ass tieši tagad ir sekunžu skaits vai pakāpienu skaits -

142
00:08:30,420 --> 00:08:31,840
Dažas vienības laika.

143
00:08:31,840 --> 00:08:34,740
Bet paziņo, ka tā ir 0-60 un 0 līdz 10.

144
00:08:34,740 --> 00:08:38,549
Bet, ja mēs veida zoom out, kā jūs varētu Excel vai kādu kartēšanas programmatūru,

145
00:08:38,549 --> 00:08:43,370
un mēs ejam līdz 200,000, pamanīt, ka kaut kas līdzīgs 2 līdz n

146
00:08:43,370 --> 00:08:47,520
gatavojas pilnībā pārņemt kārtējās laikus n brusas,

147
00:08:47,520 --> 00:08:50,960
n kubā, n log n - viss, ko mēs esam runājuši par līdz šim.

148
00:08:50,960 --> 00:08:54,190
Un vēl nozveja ir tad, kad jūs sākat runāt par lietām, piemēram, Facebook

149
00:08:54,190 --> 00:08:57,150
kur jums ir daudzi, daudzi, daudzi cilvēki visi savstarpēji saistīti,

150
00:08:57,150 --> 00:09:00,650
Jums ir n cilvēki, no kuriem katrs var būt tik daudz kā n draugiem

151
00:09:00,650 --> 00:09:02,860
ja visi ir sava veida draugs-draugs pasaulē,

152
00:09:02,860 --> 00:09:08,100
labi, ka ir n reizes n jau tā, ka ir n kvadrātā iespējamos draudzību,

153
00:09:08,100 --> 00:09:10,950
vismaz 1 virzienā, n kvadrātā iespējamo draudzību.

154
00:09:10,950 --> 00:09:15,330
Lai jau liecina, ka meklēšana Facebook sociālo grafiku, tā teikt,

155
00:09:15,330 --> 00:09:18,090
var sākt izteikt šajos formulas veidu.

156
00:09:18,090 --> 00:09:19,820
>> Mēs būsim atpakaļ un padarīt šo daudz betona,

157
00:09:19,820 --> 00:09:23,280
bet tagad, mērķis nākamajiem daudziem nedēļas

158
00:09:23,280 --> 00:09:27,170
būs pārliecinieties, nevis iet par īstenojot algoritmiem vai kods

159
00:09:27,170 --> 00:09:29,870
ka galu galā, ņemot tik daudz laika kā kaut kas līdzīgs šim.

160
00:09:29,870 --> 00:09:33,110
Bet aizraujošu lieta par datorzinātņu, ja jūs turpināt šajā jomā

161
00:09:33,110 --> 00:09:38,320
ņemot klasēm, piemēram, CS121, CS124, kas abi ir teorija kursi,

162
00:09:38,320 --> 00:09:41,300
ir, ka faktiski ir dažas problēmas, kas pastāv šajā pasaulē

163
00:09:41,300 --> 00:09:45,710
ka būtiski, cik mēs zinām, nevar atrisināt ātrāk

164
00:09:45,710 --> 00:09:48,880
nekā šo grafiku sliktākajiem patiesībā liecina.

165
00:09:48,880 --> 00:09:53,660
Tāpēc tur atklātu problēmas šajā pasaulē, lai darīt daudz labāk nekā cilvēki ir līdz šim partiju.

166
00:09:53,660 --> 00:09:56,130
>> Tāpēc sāksim tad ar šo piemēru.

167
00:09:56,130 --> 00:09:59,650
Mēs redzējām Šons cīnīties ar šo par kameru, viss ir pārāk neveikli video.

168
00:09:59,650 --> 00:10:05,270
Bet realitāte bija, kad Šons uzdevums bija atrast uz kuģa, piemēram, tas par 7,

169
00:10:05,270 --> 00:10:10,300
atceros, ka es teicu, ka, "Tur ir kaut kur aiz šiem papīra gabalu vai balto durvīm

170
00:10:10,300 --> 00:10:12,570
"Skaits 7 Sean. Atrast to par mums."

171
00:10:12,570 --> 00:10:14,200
Un tas bija lieliski neērti skatīties

172
00:10:14,200 --> 00:10:15,790
jo viņš bija tiešām cīnās ar šo problēmu.

173
00:10:15,790 --> 00:10:19,720
Bet realitāte bija Sean darīja, kā arī ikviens telpā varēja izdarīt.

174
00:10:19,720 --> 00:10:21,890
Viņš paņēma mazliet ilgāk nekā tipisks persona varētu būt,

175
00:10:21,890 --> 00:10:24,760
bet viņš secinājis, ka tur bija daži triks ar šo problēmu,

176
00:10:24,760 --> 00:10:26,590
viņš secinājis, ka viņš bija pazudis kaut.

177
00:10:26,590 --> 00:10:29,320
Un tā nav palīdzība, ka simtiem acis bija nes uz leju uz viņu.

178
00:10:29,320 --> 00:10:34,250
>> Bet realitāte bija ja ieeja uz problēmu, ir ķekars izlases numurus

179
00:10:34,250 --> 00:10:37,120
un jūs to lūdza, lai atrastu 1 tāds numurs,

180
00:10:37,120 --> 00:10:39,770
vislabāk varat darīt, ir lineāra meklēt.

181
00:10:39,770 --> 00:10:44,060
Sākas kreisi, pāriet uz labo, vai sākt labajā, pārvietot pa kreisi.

182
00:10:44,060 --> 00:10:48,300
Atpakaļejošu datumu, mēs varētu domāt, "Sean, kāpēc nav jūs vienkārši sākt no otra gala?"

183
00:10:48,300 --> 00:10:52,120
Nu, 7 varētu būt tikpat viegli ir šeit nejauši,

184
00:10:52,120 --> 00:10:54,980
bet es apzināti likt to tur, jo es sapratu, viņš nav gatavojas sākt beigās.

185
00:10:54,980 --> 00:10:59,320
Tāpēc es veida manipulē situāciju, bet pēc nejaušības 7 varētu būt jebkur.

186
00:10:59,320 --> 00:11:02,380
Tātad sākot no labajā pusē varētu būt labāk tad,

187
00:11:02,380 --> 00:11:04,320
bet ko tad, ja nākamajā gadā es pārvietot 7 citur?

188
00:11:04,320 --> 00:11:06,830
Tas nav principiāli jauna problēmas risinājums -

189
00:11:06,830 --> 00:11:10,520
sākot no 1 gada beigās vai citu - ja jūs esat dota nav citas pieņēmumus.

190
00:11:10,520 --> 00:11:13,620
Tāpēc Šons sāka meklē caur skaitļiem un viņš teica, "5 Tas nav šeit.".

191
00:11:13,620 --> 00:11:17,280
Tad viņš aizgāja šeit un redzēju 19, tad viņš apstājās aptuveni 20 sekundes,

192
00:11:17,280 --> 00:11:22,330
tad viņš atvēra šo par 13, un tad kļuva skaidrs,

193
00:11:22,330 --> 00:11:24,270
ka tur nav, šķiet, ir modelis šeit.

194
00:11:24,270 --> 00:11:28,090
Tas bija nevis 1, 2, 3, 4 vai tamlīdzīgi. Tur bija nepilnības skaitļiem, kas nepalīdzēja.

195
00:11:28,090 --> 00:11:32,320
Un arī, ka es izmantoti šos lētu papīra gabaliem, lai segtu līdz skaitļus

196
00:11:32,320 --> 00:11:35,270
faktiski apzināta, jo, ja es noņemt visus šos papīra gabaliem,

197
00:11:35,270 --> 00:11:38,760
Vairumam no mums, Šons iekļauts, iespējams, būtu paskatījās veida makroskopiski

198
00:11:38,760 --> 00:11:43,410
pie tāfeles un teica: "Ak, 7 ir acīmredzami labi tur." Mēs to uzreiz.

199
00:11:43,410 --> 00:11:46,460
>> Un kas varētu būt veids, kā darbojas cilvēka smadzenes, lai zināmā mērā,

200
00:11:46,460 --> 00:11:50,730
bet patiesībā, viņa acis vai prāta, iespējams, bija apdedžu ciparus no labās uz kreiso,

201
00:11:50,730 --> 00:11:55,190
kreisās uz labo, vidēju uz out - kaut kas notiek fizioloģiski

202
00:11:55,190 --> 00:11:57,640
tāda, ka tā jutos kā tas bija noticis uzreiz,

203
00:11:57,640 --> 00:12:01,360
bet izredzes ir vēl iekšēji tur bija daži no metodoloģijas veida, lai atrastu 7.

204
00:12:01,360 --> 00:12:05,160
Un tiešām, tagad, ka mēs runājam par masīvu un datu struktūras

205
00:12:05,160 --> 00:12:08,780
un atmiņas iekšpusē datoru, vienīgais, ko mēs, cilvēki var darīt

206
00:12:08,780 --> 00:12:13,070
ir apskatīt atsevišķu atmiņas vietās 1 laikā.

207
00:12:13,070 --> 00:12:16,600
>> Tāpēc katru citu vietu varētu arī tikt uz augšu ar kādu papīra

208
00:12:16,600 --> 00:12:21,170
jo mēs nevaram redzēt to anyway. Mēs varam darīt tikai 1 lieta laikā.

209
00:12:21,170 --> 00:12:25,030
Tātad šajā gadījumā, jo Šona gadījumā mēs devāmies šeit un tad mēs devāmies šeit

210
00:12:25,030 --> 00:12:31,040
un tad mēs devāmies šeit, šeit, šeit, šeit, ieguva gudrs beigām

211
00:12:31,040 --> 00:12:34,450
un tikai veida izlaidis šo vienu patvaļīgi un konstatēja 7 Ir.

212
00:12:34,450 --> 00:12:37,470
Tas viens bija ne sevišķi īpašs. Tas arī bija bojātas.

213
00:12:37,470 --> 00:12:39,530
Bet viņš beidzot ir atrasts 7.

214
00:12:39,530 --> 00:12:45,360
Bet tagad takeaway patiešām ir, ka labākais jūs varat darīt, ja sniegta nekāda informācija

215
00:12:45,360 --> 00:12:50,400
izņemot nejauši Šķirotu numuriem ir jāsāk no kreisās vai sākt no labās puses.

216
00:12:50,400 --> 00:12:54,950
Vai heck, jūs varat nejauši atvērt durvis, bet pat tad ko tas nozīmē būt nejauši?

217
00:12:54,950 --> 00:12:57,220
Nu, mēs ir kaut formalizēt to, ko nozīmē sākt šeit,

218
00:12:57,220 --> 00:13:01,150
tad iet šeit, tad iet šeit. Šons bija liels, un tas bija tikai jautri skatīties.

219
00:13:01,150 --> 00:13:06,340
Ko darīt, ja tā vietā mēs mainīt šo problēmu mazliet un audzināt šī gada Šonu, ja jūs?

220
00:13:06,340 --> 00:13:09,460
Vai kāds būtu ērti nāk uz skatuves un risināšanas nedaudz cita problēma

221
00:13:09,460 --> 00:13:12,330
un parādās uz kameru?

222
00:13:12,330 --> 00:13:15,720
>> Iesim tālāk orķestra jo jums puiši ir diezgan, jo jau šodien.

223
00:13:15,720 --> 00:13:21,430
Kā par rozā, jo cepure? Nāciet uz leju. Kāds ir Jūsu vārds? >> Alex. >> Alex. Labi.

224
00:13:21,430 --> 00:13:24,580
Tāpēc Alex būs šī gada Šons un parādīsies tuvāko gadu laikā

225
00:13:24,580 --> 00:13:27,770
vērts CS50 lekcijas.

226
00:13:27,770 --> 00:13:30,340
Alex, nice to meet you. >> Prieks iepazīties pārāk.

227
00:13:30,340 --> 00:13:33,470
Pie rokas jums izaicinājums ir tas, ka jums ir tas mazliet vieglāk

228
00:13:33,470 --> 00:13:38,950
jo es esmu stāsta jums paši numuri ir šeit, bet tagad sakārtots.

229
00:13:38,950 --> 00:13:41,800
Tāpēc tagad jūsu mērķis ir atrast numuru 7.

230
00:13:41,800 --> 00:13:45,370
Un tiešām, mums patiešām vajadzētu darīt to - jūs esat nokļuvis veida krāpšanos, kā dators nav,

231
00:13:45,370 --> 00:13:47,990
pēc tā, ko skaitļi bija pirms brīža.

232
00:13:47,990 --> 00:13:50,360
Ar krītu tas patiesībā nav dodas, lai palīdzētu visiem, ka daudz,

233
00:13:50,360 --> 00:13:52,810
bet pieņemsim izlikties, ka jūs nezināt, ko sākotnējā masīvs ir.

234
00:13:52,810 --> 00:13:56,600
Visi jūs zināt tagad ir tas, ka jums ir masīva sakārtoti numuru

235
00:13:56,600 --> 00:14:00,360
kas varētu būt atšķirības starp tām, un jūsu mērķis ir atrast numuru 7.

236
00:14:00,360 --> 00:14:05,080
Kā Jūs, saprātīgs cilvēks, iet par atrast numuru 7?

237
00:14:05,080 --> 00:14:07,770
>> Aiziet no zemas līdz augstam? >> Labi. Aiziet zemā uz augsto.

238
00:14:07,770 --> 00:14:10,990
Un nav asaru tos off. Pieņemsim tikai pacelt tos, lai mēs varētu tos izmantot.

239
00:14:10,990 --> 00:14:14,730
Labi, tā 1. Pagaidiet. Pirms jūs glabāt notiek, ka bija 1, pilnīgi nepareizi.

240
00:14:14,730 --> 00:14:17,270
Tātad, kas notiek ar jūsu prātā nākamais? Kāds ir jūsu nākamais solis?

241
00:14:17,270 --> 00:14:23,250
Nākamais. >> Labi. Nākamo. Labi. 3, tāpēc nepareizs. Kāds ir jūsu nākamais solis?

242
00:14:23,250 --> 00:14:27,670
Turēt uz iet. >> Visas tiesības. Turēt uz iet. 5.

243
00:14:27,670 --> 00:14:31,110
Tā turēt uz iet, un ļaujiet man nodot jums šo nākamajām paaudzēm.

244
00:14:31,110 --> 00:14:35,720
7. >> Lieliska. Ļoti labi. Atrada numuru 7. [Aplausi]

245
00:14:35,720 --> 00:14:39,720
Tā, ka bija labs, bet Šons pārāk atrada numuru 7.

246
00:14:39,720 --> 00:14:44,490
Un es apgalvo, ka jums nav īsti izmantot šo papildu informācijas vienību,

247
00:14:44,490 --> 00:14:47,780
kas ir tas, ka šie skaitļi ir sakārtoti.

248
00:14:47,780 --> 00:14:51,520
Tātad mēs varam darīt labāk? Kādi ieteikumi šeit? Jā, jo atpakaļ.

249
00:14:51,520 --> 00:14:54,710
[Students] binārā meklēšana. >> Man nav ne jausmas, ko binārā meklēšana ir.

250
00:14:54,710 --> 00:14:58,030
>> [Students] Sākt vidū. >> Sākt vidū. Labi. Tātad, pieņemsim redzēt, ja mēs varam tur nokļūt.

251
00:14:58,030 --> 00:15:02,580
Tātad, ja tā vietā jūs esat teicis sākas no vidus, iet uz priekšu un atvērt vidū durvis.

252
00:15:02,580 --> 00:15:04,580
Ir 8 no tiem, lai jūs nāksies patvaļīgi izvēlēties vienu

253
00:15:04,580 --> 00:15:09,800
nedaudz pa kreisi vai pa labi. Labi. 7! [Aplausi] Ļoti jauka.

254
00:15:09,800 --> 00:15:11,410
Labi, bet kur bija mums iet ar šo?

255
00:15:11,410 --> 00:15:14,990
Pieņemsim tikai, lai izjauktu kaklasaites jums bija sākusies šeit

256
00:15:14,990 --> 00:15:16,670
jo tas vienlīdz varētu būt noticis, kā arī.

257
00:15:16,670 --> 00:15:19,540
Mēs tikko notika zināt, ka 7 bija tur. Tātad šis ir 13.

258
00:15:19,540 --> 00:15:21,980
Tātad, ja viņi šķiro un mēs tikko sāka vidū,

259
00:15:21,980 --> 00:15:24,600
kāds būtu optimālais nākamais solis ir?

260
00:15:24,600 --> 00:15:27,740
Iet pa kreisi. Un tāpēc šeit nāk tālruņu grāmatas piemērs vēlreiz.

261
00:15:27,740 --> 00:15:30,130
Ja 13 ir šeit un mēs zinām saraksts tiek sakārtots,

262
00:15:30,130 --> 00:15:33,900
tad visi no šiem papīra gabalu ir neinteresanti mums tagad

263
00:15:33,900 --> 00:15:37,400
jo mēs jau zinām, ka 7 ir jābūt pa kreisi

264
00:15:37,400 --> 00:15:39,510
ja šie skaitļi ir sakārtoti un mēs konstatējām 13.

265
00:15:39,510 --> 00:15:42,500
>> Tātad, kādi ir jūsu nākamais solis šeit? >> Iet pa kreisi. >> Labi, labi.

266
00:15:42,500 --> 00:15:45,080
Lai iet pa kreisi, un - pagaidiet, hey, hey, hey. Tas ir blēdība.

267
00:15:47,140 --> 00:15:51,350
Tātad jums atrast 7, bet to, kas bija algoritmu mēs tikai piemērots?

268
00:15:51,350 --> 00:15:56,450
Sākt vidū. >> Labi. Tātad, kāda ir loģisks turpinājums šo pašu ideju?

269
00:15:56,450 --> 00:15:58,970
Ak, lai tikai tie. >> Tieši tā. >> Tāpēc es sāktu šeit. >> Labi.

270
00:15:58,970 --> 00:16:02,020
Tāpēc tagad mēs devāmies nedaudz pa kreisi atkal. Tas ir 3.

271
00:16:02,020 --> 00:16:05,310
Bet interesanti takeaway tagad ir, ko viena jums nav jārūpējas par?

272
00:16:05,310 --> 00:16:08,040
Šie 2. >> Šie 2. Tāpēc tagad tas var iet prom, tas var iet prom.

273
00:16:08,040 --> 00:16:12,330
Tagad problēma, ka bija 8, tad bija izmērs 4 tagad ir izmērs 2.

274
00:16:12,330 --> 00:16:16,430
Mēs esam kļūst diezgan tuvu. Atkal iet uz vidu šiem 2 elementiem.

275
00:16:16,430 --> 00:16:20,430
>> Labi. Tātad, tas ir sava veida žēl, ka tagad mēs esam vienmēr iet pa kreisi, jo mēs esam noapaļojot uz leju.

276
00:16:20,430 --> 00:16:25,150
Bet tas ir labi, jo tagad mēs mest šo prom un viss pārējais, atstājot mūs ar 7 tikai.

277
00:16:25,150 --> 00:16:30,490
Dosim kārta aplausi. Esam atraduši 7 vēlreiz. [Aplausi] Labi. Pārliecināts.

278
00:16:30,490 --> 00:16:32,220
Pakārt par tikai 1 vēl sekundi.

279
00:16:32,220 --> 00:16:36,630
Kaut gan, ka nākamais process veida bija nedaudz ilgāk, nekā mēs uzskatījām, tas būtu,

280
00:16:36,630 --> 00:16:40,150
godīgi sakot, jūsu pirmās instinkti bija labākais, vai ne? Esam atraduši 7 uzreiz.

281
00:16:40,150 --> 00:16:46,740
Bet mēs esam atraduši 7 ātrāk, vienalga ko, šajā piemērā versus šo vienu

282
00:16:46,740 --> 00:16:50,100
jo, ja šie numuri ir viss sakārtots, līdzīgi kā ar tālruni grāmatas lappusēm,

283
00:16:50,100 --> 00:16:54,580
Jūs varat patiešām cirst pusi problēmas atkal un atkal un atkal.

284
00:16:54,580 --> 00:16:56,740
Un tas nav tik viegli redzēt to ar tikai 8 numuriem

285
00:16:56,740 --> 00:17:00,100
pretstatā 1000 lappuses telefona grāmatu, kur jūs patiešām redzēt to vizuāli,

286
00:17:00,100 --> 00:17:03,120
bet šajā gadījumā šeit, kad Šons bija meklējot 7,

287
00:17:03,120 --> 00:17:06,020
cik soļus Sliktākajā gadījumā tas tā ir veikusi viņam? >> [Students] 7.

288
00:17:06,020 --> 00:17:11,670
7 sliktākajā gadījumā. Nu, sliktākajā gadījumā nav 7 Ja tur ir 8 durvis šeit.

289
00:17:11,670 --> 00:17:13,440
Tas būtu jāņem viņam 8 soļi.

290
00:17:13,440 --> 00:17:18,170
>> Tātad, ja tur n durvis, tas varētu būt veikusi Šonu pirms pāris gadiem n soļus.

291
00:17:18,170 --> 00:17:21,520
Tagad, jūsu gadījumā, Alekss, ņemot vērā, ka šie skaitļi ir sakārtoti -

292
00:17:21,520 --> 00:17:25,130
un mēs varam veida nesecinot šo no kurienes mēs esam bijuši līdz šim šajā stāstā -

293
00:17:25,130 --> 00:17:28,300
kāda ir darbības laiks Alex vairāk viedo algoritmu

294
00:17:28,300 --> 00:17:30,770
gada sākot no vidus, un pēc tam atkārtojot?

295
00:17:30,770 --> 00:17:36,490
[Students] 3. >> Tātad tas būs 3, rupji, ja jums iet 8-4 2 līdz 1.

296
00:17:36,490 --> 00:17:40,660
Tātad 3 soļi vai, plašākā nozīmē, ka ir log n vēlreiz.

297
00:17:40,660 --> 00:17:43,380
Jebkurā laikā jūs uz pusi un pusi un pusi un pusi,

298
00:17:43,380 --> 00:17:45,290
tas izpaužas šo ideju žurnāla n.

299
00:17:45,290 --> 00:17:48,140
Un lai būtu ņemti jums tikai 3 soļus, un tas notika

300
00:17:48,140 --> 00:17:50,890
kad mēs atvērām durvis uz pusi un pusi,

301
00:17:50,890 --> 00:17:53,770
tā kā tas būtu jāņem Šons par 7 vai 8 soļus.

302
00:17:53,770 --> 00:17:56,330
Tāpēc paldies, ka esat kopā ar mums šajā gadā. >> Paldies. Nice tikšanos ar Jums.

303
00:17:56,330 --> 00:18:00,170
Paldies Alex. >> Tāpat. [Aplausi]

304
00:18:00,170 --> 00:18:02,150
>> Kas tad reālais saistība ar šo?

305
00:18:02,150 --> 00:18:06,050
Tagad iedomājieties, ka tas nav 8 durvis, kuras, godīgi sakot, mums visiem varētu atrast kaut ko

306
00:18:06,050 --> 00:18:10,430
aiz 8 durvis diezgan ātri, vienkārši plīsumi papīra gabaliņus un iet ar mūsu instinktiem.

307
00:18:10,430 --> 00:18:14,430
Bet ko tad, ja tas ir viens miljons durvis? Ko darīt, ja tas ir 4000000000 durvis?

308
00:18:14,430 --> 00:18:19,630
Attiecībā ir 4 miljardi durvju, jūs tiešām gatavojas vēlaties doties ar Alex algoritmu,

309
00:18:19,630 --> 00:18:23,150
binārā meklēšana, kā mēs sāksim aicinot to vai skaldi un valdi, plašāk,

310
00:18:23,150 --> 00:18:25,220
kur jums saglabāt pusi un pusi problēmu,

311
00:18:25,220 --> 00:18:30,510
jo, ja jums ir 4000000000 durvis, cik reizes jūs varat cirst 4 miljardus pusi?

312
00:18:30,510 --> 00:18:33,870
[Students] 32. >> Tas ir tiešām 32. Jūs varat strādāt šo out uz papīra vai savā galvā.

313
00:18:33,870 --> 00:18:38,490
Jūs dodieties 4000000000-2000000000 to 1 miljardu pusmiljardu, līdz 250 miljoniem, dot, dot, dot.

314
00:18:38,490 --> 00:18:41,620
Un, ja jūs, kas to math, jūs gatavojas tiešām saņem 32,

315
00:18:41,620 --> 00:18:44,950
un faktiski attiecas uz datorzinātņu jo mēs parasti rēķināties ar pilnvaru 2.

316
00:18:44,950 --> 00:18:47,600
2-32 no notiek, ir 4 miljardi.

317
00:18:47,600 --> 00:18:51,440
Tātad tur ir sakars ar šiem pilnvaras 2 datorzinātņu veidu daudz.

318
00:18:51,440 --> 00:18:55,120
>> Bet ko 8 miljardu? Cik soļus ir tas, ka gatavojas veikt, ja ir 8000000000 durvis?

319
00:18:55,120 --> 00:19:00,350
[Students] 33. >> Tātad 33. Ko darīt, ja tur 16000000000 durvis? Cik soļus ir tas, ka gatavojas veikt?

320
00:19:00,350 --> 00:19:05,020
[Students] 34. >> 34. Mēs varētu veida turpina šo reklāmu nauseam. Bet tas ir spēcīgs lieta.

321
00:19:05,020 --> 00:19:09,430
Jūs varat ieviest miljardiem vairāk resursu, lai savu problēmu, bet, nav liels galā,

322
00:19:09,430 --> 00:19:14,140
Jūs tikai 1 papildu kodums no tā un tādējādi dod mums kaut kas līdzīgs bināro meklēšanu

323
00:19:14,140 --> 00:19:15,920
vai skaldi un valdi, kopumā.

324
00:19:15,920 --> 00:19:17,990
Bet es esmu veida krāpšanos šeit, vai ne?

325
00:19:17,990 --> 00:19:22,410
Attiecībā uz Alex algoritmu, viņa bija priekšrocības pār Šonu.

326
00:19:22,410 --> 00:19:27,780
Viņa zināja, ka šie skaitļi ir sakārtoti, bet Alekss nebija šķirot tos sev.

327
00:19:27,780 --> 00:19:30,520
Es jau iepriekš nāca klajā ar tāfeles un veidu pārliecināts

328
00:19:30,520 --> 00:19:33,670
ka es vērsa tos visus, kas sakārtoti secībā, tad es uz tiem ar papīru.

329
00:19:33,670 --> 00:19:35,850
Bet cik daudz darba bija, ka mani aizvest?

330
00:19:35,850 --> 00:19:40,110
Ja mēs būtu sākās ar šiem dažiem šķietami nejaušā secībā numuriem -

331
00:19:40,110 --> 00:19:43,320
Šajā gadījumā šie vienkāršāki numurus, 1 līdz 8 šeit -

332
00:19:43,320 --> 00:19:46,090
Kā mēs iet par šķirošanas šīs vērtības?

333
00:19:46,090 --> 00:19:52,530
Ja tu būtu cilvēks dots šis uzdevums, kāda veida intuitīvu pieeju jūs ņemtu

334
00:19:52,530 --> 00:19:54,800
lai šķirošanas visu ķekars numuriem?

335
00:19:54,800 --> 00:19:57,050
Šīs lietas tika izklāstīts, kā puzzle gabaliem. Yeah.

336
00:19:57,050 --> 00:19:59,950
>> [Students] es būtu katru numuru un salīdzināt to ar katru vienu

337
00:19:59,950 --> 00:20:03,180
un tur notiek pa kreisi. >> Labi, labi.

338
00:20:03,180 --> 00:20:05,720
Tātad, ņem katru numuru, salīdziniet to ar vienu blakus tam,

339
00:20:05,720 --> 00:20:09,610
un tad tikai glabāt pārvietojas pa saraksta, kāda veida rejiggering lietas kā jums iet.

340
00:20:09,610 --> 00:20:13,800
Tātad šeit mums ir izredzes uz varbūt vēl dažus ļaudīm iesaistīties.

341
00:20:13,800 --> 00:20:16,290
Vai mums ir vēl 8 brīvprātīgos, kuri labprāt vēlētos nākt klajā?

342
00:20:16,290 --> 00:20:23,950
Nedaudz mazāks spiediens, jo jūs esat ne tikai viens. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Nāciet uz leju. Jūs guys būs numuriem no 1 līdz 8.

344
00:20:28,190 --> 00:20:36,050
Redzēsim, vai mēs nevaram darīt šķirošanu Alex daudz pašā veidā es to darīja iepriekš.

345
00:20:36,050 --> 00:20:37,640
1, 2, 3, 4.

346
00:20:37,640 --> 00:20:40,760
Iet uz priekšu un, ja tu būtu, rindā uz skatuves starp mūzikas stāvēt un man šeit

347
00:20:40,760 --> 00:20:44,960
tādā pašā kārtībā kā slaidu uz ekrāna.

348
00:20:47,910 --> 00:20:49,680
Uh-oh.

349
00:20:50,370 --> 00:20:53,230
Mēs sadarbosimies tevi uz nākamo piemēru. Ak, pagaidiet, pagaidiet. Šeit mēs iet. Pagaidiet.

350
00:20:53,230 --> 00:20:57,570
Nākamais piemērs ir tagad. Šeit jums iet. Numuru 8. Nāciet uz augšu.

351
00:20:57,570 --> 00:21:00,270
Labi. Kārtot paši saskaņā ar šo.

352
00:21:00,270 --> 00:21:03,620
Slaidu tikai mazliet uz pusi mūzikas stāvēt šeit.

353
00:21:03,620 --> 00:21:12,310
Tāpēc mums ir 4, 2, 6 - nokļūt tur, nekā šeit, tieši tur - 3.

354
00:21:12,310 --> 00:21:17,570
Yeah. Labi. Jums iet vairāk nekā šeit. Nē, tu paliec tur.

355
00:21:17,570 --> 00:21:21,840
Jā, tieši tur. Nē, es kļūdos. Labi tur. Labi, ļoti labi. Labi.

356
00:21:21,840 --> 00:21:24,930
Tāpēc tagad pieņemsim šķirot tos arvien kārtībā.

357
00:21:24,930 --> 00:21:26,210
>> Kā es varu iet par to izdarīt?

358
00:21:26,210 --> 00:21:28,630
Algoritms, kas tika ierosināta pirms brīža bija kāpēc nav mēs vienkārši salīdzināt

359
00:21:28,630 --> 00:21:31,970
ļaudīm, kas ir sava veida blakus viens otram un tad noteikt visas kļūdas,

360
00:21:31,970 --> 00:21:33,540
pārvietojas no kreisās uz labo pusi.

361
00:21:33,540 --> 00:21:36,580
Tātad šeit mums ir 4 un 2, protams bojātas. Pieņemsim mijmaiņas jums. Labi.

362
00:21:36,580 --> 00:21:40,760
Tāpēc tagad es esmu gatavojas pārvietot uz leju līniju. 4 un 6, nope. [Smiekli]

363
00:21:40,760 --> 00:21:45,010
6 un 8, diezgan labi. 8 un 1, ļaujiet man swap jums puiši. Labi.

364
00:21:45,010 --> 00:21:48,030
Tātad 8 un 3 mijmaiņas jūs puiši.

365
00:21:48,030 --> 00:21:52,280
8 un 7, ļaujiet man swap jums puiši. 5 un 8, lielisks.

366
00:21:52,280 --> 00:21:54,820
Es jums sakārtoti sarakstu.

367
00:21:54,820 --> 00:21:56,860
Labi. Tātad ne gluži.

368
00:21:56,860 --> 00:22:01,180
Bet tas ir labāk, jo lielāki skaitļi - gadījums paziņojuma 8 -

369
00:22:01,180 --> 00:22:04,030
ir sava veida kūsāja no kreisās pāri uz labo pusi.

370
00:22:04,030 --> 00:22:08,010
Tāpēc es saņēmu 1 no tiem labi, bet tā uzskata, piemēram, tas nav gluži atrisināt problēmu.

371
00:22:08,010 --> 00:22:11,150
>> Tātad, ko jūs ierosināt mums darīt tālāk? >> [Students] Uzglabāt darot to. >> Mēs saglabāt to dara.

372
00:22:11,150 --> 00:22:13,740
Un realizēt, atkal, mēs noteikt lietas izveidota, tikai ar visiem cilvēkiem

373
00:22:13,740 --> 00:22:17,180
kārtot inteliģenti organizēt sevi, pamatojoties uz šo attēlu,

374
00:22:17,180 --> 00:22:19,040
bet tagad mums ir jābūt daudz metodisko.

375
00:22:19,040 --> 00:22:21,510
Mums jābūt algoritmiskas par to, it kā mēs rakstiski kodu -

376
00:22:21,510 --> 00:22:23,520
šajā gadījumā vārdiskais pseudocode.

377
00:22:23,520 --> 00:22:26,040
Tāpēc ļaujiet man tikai mēģināt to vēlreiz. , Kas strādāja diezgan labi. Tas nav to atrisināt.

378
00:22:26,040 --> 00:22:30,400
Bet, kad tas šaubos, vienkārši izmēģināt un mēģiniet vēlreiz. SO 2 un 4, nepalīdzēja vairs.

379
00:22:30,400 --> 00:22:33,200
4 un 6. Ah! 6 un 1, nedaudz labāk tagad.

380
00:22:33,200 --> 00:22:39,740
6 un 3, labi. 6 un 7, 7 un 5, 7 un 8, labi.

381
00:22:39,740 --> 00:22:44,060
Un jūs zināt, es varu droši ignorēt 8 Tagad, jo viņš ir pie saraksta beigās.

382
00:22:44,060 --> 00:22:47,250
Varbūt mums nav jāuztraucas par kāds dodas viņam garām.

383
00:22:47,250 --> 00:22:49,240
Bet pieņemsim redzēt, ja tas ir drošs pieņēmums.

384
00:22:49,240 --> 00:22:52,340
Tagad saraksts ir - nopelt - nav sakārtots. Mēģināsim to atkal.

385
00:22:52,340 --> 00:22:56,440
SO 2 un 4, 4 un 1, 4 un 3.

386
00:22:56,440 --> 00:22:59,230
4 un 6, labi. 6 un 5, labi.

387
00:22:59,230 --> 00:23:04,890
6, 7, 8 un, labi. Bet paziņojums, es varu tikai apstāties šeit tagad apstāties šeit tagad?

388
00:23:04,890 --> 00:23:07,770
[Students] Jā. >> Yeah?

389
00:23:07,770 --> 00:23:11,160
Ko darīt, ja viens no jums būtu bijis numurs 9 līdz galam tur?

390
00:23:11,160 --> 00:23:13,640
Tas būtu sakārtoti. >> Labi. Tas būtu sakārtoti pirmo reizi apkārt.

391
00:23:13,640 --> 00:23:16,050
Labi. Tāpēc iesim atpakaļ. Mēs esam gandrīz tur.

392
00:23:16,050 --> 00:23:22,800
1 un 2, 2 un 3, 3 un 4, 4 un 5, 5 un 6, 6 un 7, 7 un 8.

393
00:23:22,800 --> 00:23:26,640
>> Es esmu darīts tagad, bet, atkal, es esmu dators, kas var darīt tikai to, ko es esmu teicis darīt,

394
00:23:26,640 --> 00:23:30,120
un mans vienīgais atmiņas tagad ir tā, ka es tiešām tikko bija daudz darba.

395
00:23:30,120 --> 00:23:31,700
Kaut mainījies šeit.

396
00:23:31,700 --> 00:23:37,100
Tāpēc man nav tehniski apstiprināts vizuāli vai algoritmiski, ka šis saraksts ir tiešām sakārtots.

397
00:23:37,100 --> 00:23:40,720
Tik vienkārši labs pasākums, tikai lai būtu anālais par šo, pieņemsim do šo 1 vairāk laika.

398
00:23:40,720 --> 00:23:44,040
Tātad 1 un 2, 2 un 3, 3 un 4. Un jūs zināt, ko?

399
00:23:44,040 --> 00:23:46,190
Tikai labs pasākums, es esmu gatavojas, lai sekotu uz manu roku šo laiku

400
00:23:46,190 --> 00:23:51,110
cik mijmaiņas man darīt tikai tāpēc, ka es zinu, cik daudz darba es esmu patiešām izdarīt.

401
00:23:51,110 --> 00:23:56,930
3 un 4, 4 un 5, 5 un 6, 6 un 7, 7 un 8. Nav mijmaiņas.

402
00:23:56,930 --> 00:24:00,800
Tāpēc tagad es būtu likumīgi idiots to darīt atkal

403
00:24:00,800 --> 00:24:03,330
jo, ja es tomēr nav darba caur šo iet uz cilvēkiem,

404
00:24:03,330 --> 00:24:06,710
tad skaidri tas notiks atkal, ja neviena no tām ir sava veida nejauši

405
00:24:06,710 --> 00:24:10,410
adversarially pārvietojas sevi apkārt. Tāpēc tagad es varētu apstāties.

406
00:24:10,410 --> 00:24:15,120
Tagad uzdot jautājumu, cik daudz darba bija tas patiesībā ņem mani?

407
00:24:15,120 --> 00:24:18,260
Cik soļus bija kas ņem? >> N kvadrātā.

408
00:24:18,260 --> 00:24:20,400
Jā, tā N kvadrātā. Ja jūs saņemsiet n rūtiņām no?

409
00:24:20,400 --> 00:24:22,660
Jums ir pārbaudīt katru skaits -

410
00:24:22,660 --> 00:24:26,530
Tur ir n numuri, un jums ir pārbaudīt katru numuru ar citām n numuriem.

411
00:24:26,530 --> 00:24:29,030
Labi. >> Tātad tas ir n rūtiņām. >> Labi.

412
00:24:29,030 --> 00:24:31,060
>> Tāpēc uzskata, ka tas varētu ļoti labi būt n rūtiņām, vai ne?

413
00:24:31,060 --> 00:24:33,820
Tur n no šiem puišiem, 8 īpaši šajā gadījumā,

414
00:24:33,820 --> 00:24:37,590
bet katru reizi, kad es devos caur šo sarakstu es biju salīdzinot pirmo personu pret otro,

415
00:24:37,590 --> 00:24:39,650
otrais pret trešo atkal un atkal un atkal,

416
00:24:39,650 --> 00:24:42,450
un, kad es saņēmu uz beigām, ko es daru? Es redid to.

417
00:24:42,450 --> 00:24:46,280
Tātad, ja mēs vispārināt šo paskaidrojumu, mēs esam n cilvēki

418
00:24:46,280 --> 00:24:51,090
un es esmu padarot, protams, 8 soļi, n pakāpieni, katru reizi, kad es iet caur šo algoritmu.

419
00:24:51,090 --> 00:24:56,070
Bet cik daudz reizes, sliktākajā gadījumā man ir jāiet caur šo sarakstu ar cilvēkiem?

420
00:24:56,070 --> 00:24:59,370
[Students] N reizes. >> Iespējams n, tiesības, jo sliktākajā gadījumā,

421
00:24:59,370 --> 00:25:03,410
kāda ir iespējams, sliktākais gadījums izkārtojums no šiem puišiem no get-go?

422
00:25:03,410 --> 00:25:06,520
Ja viņi pilnīgi pretēja kārtībā

423
00:25:06,520 --> 00:25:09,310
jo tikai pieņemsim garīgi, let's - Kāds ir Jūsu vārds? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Labi. Tātad Bowen, nāk vairāk nekā šeit tikai brīdi.

425
00:25:12,510 --> 00:25:16,150
>> Pieņemsim, ka Bovens bija šeit sākumā algoritmu,

426
00:25:16,150 --> 00:25:19,790
un mēs nezinām, ko ikviens cits ir, bet Bowen šeit, saskaņā ar šo algoritmu -

427
00:25:19,790 --> 00:25:23,820
un, ja jūs vēlaties, lai vienkārši pastaigāties ar mani - gatavojas burbulis up, kā viņš to darīja pirmo reizi apkārt,

428
00:25:23,820 --> 00:25:25,740
visu ceļu līdz beigām.

429
00:25:25,740 --> 00:25:29,400
Bet pieņemsim, ka persona blakus Bowen bija numur 7.

430
00:25:29,400 --> 00:25:33,450
Man ir jāiet atpakaļ un saņemt numuru 7, kas nozīmē, ka man ir iet visu ceļu atpakaļ šeit.

431
00:25:33,450 --> 00:25:36,980
Tagad man ir jābūt, ka pati pastaiga ar personu, kas ir numurs 7.

432
00:25:36,980 --> 00:25:40,140
Bet ko tad, ja tam skaits 6 bija viņam blakus, kā arī?

433
00:25:40,140 --> 00:25:42,180
Tad man ir jāiet atpakaļ un saņemt 6.

434
00:25:42,180 --> 00:25:46,490
Tātad vēlreiz, par katru atkārtojuma šīs cilpas es runāju ar katru no n cilvēkiem,

435
00:25:46,490 --> 00:25:50,090
un es varētu darīt n no šīm pastaigām, lai pārliecinātos, es esmu nostiepes

436
00:25:50,090 --> 00:25:53,760
visi no lielākajiem elementiem atpakaļ un atpakaļ un atpakaļ līdz pašām beigām saraksta.

437
00:25:53,760 --> 00:25:58,230
Tātad n lietas n reizes ir tikai n reizes vai N kvadrātā.

438
00:25:58,230 --> 00:26:02,050
>> Tātad šeit jau mums ir algoritms, kas vairs n, kas vairs log n,

439
00:26:02,050 --> 00:26:04,820
tas patiesībā sliktāk, nekā kaut ko mēs esam darīts iepriekš.

440
00:26:04,820 --> 00:26:09,840
Tāpēc Alekss veida palaimējies, jo es darīju visu darbu acīmredzot līdz priekšējā viņai,

441
00:26:09,840 --> 00:26:14,690
visu dārgu darbu, lai viņa varētu baudīt šajā binārā meklēšanas algoritmu,

442
00:26:14,690 --> 00:26:16,420
kas ir žurnāls n.

443
00:26:16,420 --> 00:26:18,240
Bet tas ir saskaņā ar pirmdien tēmu.

444
00:26:18,240 --> 00:26:23,260
Mēs likām mazliet vairāk vietas, mēs izmantojām vairāk bitu, lai paātrinātu mūsu darba laika.

445
00:26:23,260 --> 00:26:26,170
Tik daudz kā tur tas kompromiss starp laiku un telpu,

446
00:26:26,170 --> 00:26:31,060
tur varētu būt arī vienkārši kompromisi starp laiks līdz priekšējo veida iegūt lietas gatavs doties

447
00:26:31,060 --> 00:26:35,000
un faktiski izpildot algoritmu, piemēram, meklēšanu. Pamēģināsim kādu citu.

448
00:26:35,000 --> 00:26:39,050
Ja jūs puiši nebūtu prāta tikai ātri pārkārtojot sevi, lai atbilstu, ka atkal

449
00:26:39,050 --> 00:26:42,240
pamēģināsim kaut nedaudz atšķirīgs, ja tas nav gluži tik vienkārši

450
00:26:42,240 --> 00:26:45,760
kā tikai noteikt visus pairwise kļūdas, kas ir super intuitīvi.

451
00:26:45,760 --> 00:26:48,150
Pieņemsim vietā būs nedaudz vairāk apzinātu un darīt.

452
00:26:48,150 --> 00:26:51,010
Šis viena arī es ieteiktu, ir iespējams diezgan saprātīgi.

453
00:26:51,010 --> 00:26:55,070
>> Pieņemsim izvēlētos mazāko personu no saraksta atkal un atkal. Tāpēc šeit mēs iet.

454
00:26:55,070 --> 00:26:57,350
4, jums ir mazākais cilvēks es esmu līdz redzējis līdz šim,

455
00:26:57,350 --> 00:27:00,520
tāpēc es esmu gatavojas garīgi atcerēties, ka, tikai norādot uz tevi tagad.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Aizmirstiet par 4 numuru. Es tikko atklāju jaunu mazākais elements šajā sarakstā.

457
00:27:05,020 --> 00:27:07,410
Es esmu gatavojas veida jāatceras, ka. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Uz redzēšanos. Tāpēc tagad es esmu gatavojas atcerēties numuru 1.

459
00:27:11,190 --> 00:27:14,790
Mēs zinām, ka 1 ir mazākais, bet es esmu datoru. Ko darīt, ja tur ir 0?

460
00:27:14,790 --> 00:27:17,140
Ko darīt, ja tur ir -1? Man ir, lai saglabātu turpinās.

461
00:27:17,140 --> 00:27:20,990
Tātad 3, 7, 5, nope. Labi. Tātad skaitlis 1 bija mazākais.

462
00:27:20,990 --> 00:27:23,640
Ļaujiet man izvēlēties jūs no saraksta - we'll iet šādā veidā -

463
00:27:23,640 --> 00:27:27,760
un nodot jums patvaļīgi sākumā sarakstā.

464
00:27:27,760 --> 00:27:29,740
Tagad, pagaidiet minūti. Es veida apkrāpti.

465
00:27:29,740 --> 00:27:34,010
Ja šie puiši pārstāv nevis no 8 cilvēkiem sarakstu, bet masīvs,

466
00:27:34,010 --> 00:27:37,050
8 gabalos pieguļošajā atmiņas - jūs prātā pastiprināšanu atpakaļ tikai brīdi?

467
00:27:37,050 --> 00:27:39,060
Tur tiešām nav par jums telpu šeit.

468
00:27:39,060 --> 00:27:41,840
Tātad, kā mēs atbrīvotu vietu - kāda ir jūsu vārds? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Kā mēs atbrīvotu vietu Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Mēs pārvietot n kas ir pirms manis. >> Labi.

471
00:27:46,760 --> 00:27:48,850
Lai mēs varētu virzīties uz n cilvēkiem, kas ir pirms viņa,

472
00:27:48,850 --> 00:27:52,400
Tātad, ja jūs puiši vēlas veikt 1 apzinātu, dramatisku soli pa kreisi.

473
00:27:52,400 --> 00:27:57,000
Viņi visi bija, ka unisonā, bet pēdējā laikā man rakstīja daži kodu,

474
00:27:57,000 --> 00:27:59,740
Jūs nevarat kārtot no pārvietot daudzas lietas visu uzreiz.

475
00:27:59,740 --> 00:28:02,450
Mēs varētu darīt to cilpu, pārvietojas ikvienam vienu reizi laikā.

476
00:28:02,450 --> 00:28:04,340
Tātad, ja jūs puiši nebūtu prāta pastiprināšanu atpakaļ uz labo pusi,

477
00:28:04,340 --> 00:28:07,230
un Sammy, ja jūs varētu soli atpakaļ, jo tur ir vēl nav par jums telpa,

478
00:28:07,230 --> 00:28:11,420
Tagad pieņemsim darīt. Kur bija Sammy pirms brīža? Labi tur.

479
00:28:11,420 --> 00:28:16,140
Tāpēc tur plaisa tur. Lai jūs varētu pārvietoties Sammy s vietas.

480
00:28:16,140 --> 00:28:20,580
Tagad nākamais cilvēks, un tagad nākamais cilvēks, tagad nākamais cilvēks. Tagad mums ir telpa Sammy.

481
00:28:20,580 --> 00:28:23,490
Tagad, kāds no skatītājiem - kas bija labs, tas bija pareizs,

482
00:28:23,490 --> 00:28:27,070
jutos nedaudz laikietilpīgs - kas ātrāks? Yeah.

483
00:28:27,070 --> 00:28:29,440
[Students] Jaunais masīvs? >> Kas tas ir? >> [Students] Jaunais masīvs? >> Labi, labi.

484
00:28:29,440 --> 00:28:33,200
>> Tātad saskaņā ar šo tēmu tikai kompromisus, kāpēc ne es tikai veikt jaunu masīvu

485
00:28:33,200 --> 00:28:36,570
 un tad Sammy tiks peldēšanas telpā priekšā šiem cilvēkiem, piemēram,

486
00:28:36,570 --> 00:28:39,600
un mēs varam tikai sākt aizpildot jaunu masīvu vispār. Tas arī būtu jāstrādā.

487
00:28:39,600 --> 00:28:42,450
Bet es neesmu ieinteresēts tērēt vairāk vietas šodien. Kas cita pieeja?

488
00:28:42,450 --> 00:28:46,630
[Students] Apmainīt. >> Labi. Mēs varētu tikai swap šos 2 puiši. Kāds ir Jūsu vārds?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Tātad Mario, jums bija pašreiz šeit.

490
00:28:49,390 --> 00:28:52,480
Sammy, jūs varat dublēt tikai brīdi? Mario bija šeit.

491
00:28:52,480 --> 00:28:55,830
Mums nav vietas tevi, tādēļ, ja jūs nebūtu prātā dodas uz vietu, kur Sammy ir,

492
00:28:55,830 --> 00:29:02,430
mēs likts Sammy šeit, un tagad es gribētu apgalvot, ka Sammy s pārnešana darbība bija daudz ātrāk.

493
00:29:02,430 --> 00:29:06,370
Mēs darījām 1 darbību swap šie puiši, vai varbūt 2 swap šos guys,

494
00:29:06,370 --> 00:29:11,210
bet mēs nedarīja 1, 2, 3, 4, lai jūtas labāk. Tagad, pagaidiet minūti.

495
00:29:11,210 --> 00:29:14,660
Es veida izgatavoti problēma sliktāk, jo skaits 4 bija sava veida tuvu sākumam.

496
00:29:14,660 --> 00:29:19,470
Tagad skaitlis 4 ir nedaudz tuvāk šim nolūkam, bet man nav īsti zināt, vai rūp to.

497
00:29:19,470 --> 00:29:23,330
Tātad tas ir tikai nelaime, ka skaitlis 4 ir nedaudz tālāk no tās galamērķis vietas.

498
00:29:23,330 --> 00:29:25,110
Tāpēc pieņemsim tagad atkārtot šo algoritmu.

499
00:29:25,110 --> 00:29:28,410
>> Lai Atgādinājums, kamēr tas stāsts bija viss, kas mums bija bija staigāt pa sarakstu

500
00:29:28,410 --> 00:29:31,130
meklē mazāko numurētā personu.

501
00:29:31,130 --> 00:29:34,530
Tāpēc tagad pieņemsim to darīt vēlreiz. Mums nav jāuztraucas par Sammy vairs.

502
00:29:34,530 --> 00:29:37,590
Mēs varam tikai iet šeit. Ooh! Numurs 2. Tas ir diezgan mazs skaits.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Labi, labi.

504
00:29:41,180 --> 00:29:43,770
Un par laimi, sagadīšanās, man nav, lai pārvietotos - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie jo viņš ir savā īstajā vietā tagad.

506
00:29:45,910 --> 00:29:48,110
Darīsim to atkal un ignorēt šos 2 puiši.

507
00:29:48,110 --> 00:29:50,460
6. Tas ir diezgan mazs skaits. Ooh! 8 ir noteikti lielāks.

508
00:29:50,460 --> 00:29:53,410
4. Pieņemsim koncentrēties uz 4. Ooh! 3 ir pat labāk.

509
00:29:53,410 --> 00:29:58,290
7 un 5. Tātad, ko mēs darām tagad ar - >> Rodžers. >> Rodžers?

510
00:29:58,290 --> 00:30:00,250
Pieņemsim mijmaiņas viņam ar 6 numuru.

511
00:30:00,250 --> 00:30:03,570
Tātad, ja 6 un 3 vēlētos swap,

512
00:30:03,570 --> 00:30:07,320
mēs esam tagad veida gotten laimīgs 6, ka ir tuvāk, kur viņa būtu,

513
00:30:07,320 --> 00:30:10,300
bet tas ir tikai sagadīšanās šeit. Tāpēc pieņemsim tagad iet šeit.

514
00:30:10,300 --> 00:30:13,430
8 ir diezgan mazs skaits. Ooh! 4 ir mazāks.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Ko mēs tagad darām? >> Apmainīt. >> Tieši tā.

516
00:30:17,130 --> 00:30:19,010
Tāpēc tagad pieņemsim darīt šāda veida ātrāk.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Kur paliek 5 aiziet? Labi. Labi.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 izpaužas palikt tur, kur viņa ir. Kāds ir Jūsu vārds? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie izpaužas palikt tur, kur viņa ir. 7 izpaužas - Paskatīsimies. 7, 8. Labi.

520
00:30:31,770 --> 00:30:35,100
Tātad 7 izpaužas palikt tur, kur viņa ir. Kāds ir Jūsu vārds? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Tāpēc Amna izpaužas palikt tur, kur viņa ir, un skaits 8 ir jau kur viņš tagad būtu.

522
00:30:39,670 --> 00:30:43,960
Labi, labi. Jūtas kā mēs esam tikai radīt darbu sev šeit, lai gan.

523
00:30:43,960 --> 00:30:47,440
Kas galu galā darbojas laiks šo algoritmu?

524
00:30:47,440 --> 00:30:51,900
Ja mēs domājam par šīm ne vien 8 bet kā n cilvēkiem? >> Tas ir n.

525
00:30:51,900 --> 00:30:55,440
Tas ir n soļus, bet mēs esam pārbaudot katru reizi.

526
00:30:55,440 --> 00:30:57,570
Labi. N bet jūs pārbaudot katru reizi?

527
00:30:57,570 --> 00:31:03,450
Labi, bet, ja tas ir n pasākumus, nebūtu man ir bijusi iespēja kārtot tevi tikai gatavojas 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Labi, ka ir liela atšķirība.

529
00:31:05,590 --> 00:31:08,050
Tātad n rūtiņām kāpēc? Kas īsti notiek?

530
00:31:08,050 --> 00:31:12,130
Ir n cilvēki šajā sarakstā, bet, lai atrastu mazāko personu sarakstā

531
00:31:12,130 --> 00:31:16,200
sliktākajā gadījumā, cik soļus man jābrauc? >> N.

532
00:31:16,200 --> 00:31:19,160
>> N, tiesības, jo sliktākajā gadījumā, Nr1 ir visu ceļu tur,

533
00:31:19,160 --> 00:31:20,990
tāpēc man ir iet saņemt viņam vai viņai.

534
00:31:20,990 --> 00:31:25,500
Un tad, kad es beidzot saproti 1 bija mazākais, tad tas ir diezgan ātri, lai mijmaiņas tiem.

535
00:31:25,500 --> 00:31:28,450
Bet tagad man ir jāsāk no sākuma un meklēt kas?

536
00:31:28,450 --> 00:31:31,980
Nākamais mazākais cilvēks, kas ir 2. Ja sliktākajā gadījumā ir 2?

537
00:31:31,980 --> 00:31:34,320
Ak, mans Dievs. Tas visu ceļu pāri šeit beigās.

538
00:31:34,320 --> 00:31:37,000
Tāpēc tagad es esmu tikai izdarīt vēl n soļus, vēl n soļiem.

539
00:31:37,000 --> 00:31:41,200
Un, ja mēs esam ieguvuši n cilvēkus un sliktākajā gadījumā mazākais cilvēks ir n soļu attālumā,

540
00:31:41,200 --> 00:31:45,230
tas atkal n reizes n, un tāpēc mēs atkal esam n rūtiņām.

541
00:31:45,230 --> 00:31:47,280
Tas nav slikta tik labi.

542
00:31:47,280 --> 00:31:52,150
Un patiesībā, pat labākajā gadījumā - domāju, ka viņi sāktu sakārtoti -

543
00:31:52,150 --> 00:31:59,080
cik soļus tas veic, lai man, izmantojot šo algoritmu, lai sakārtotu šos n cilvēkus?

544
00:31:59,080 --> 00:32:01,010
N brusas. >> Es dzirdēju n rūtiņām. Kāpēc n rūtiņām?

545
00:32:01,010 --> 00:32:05,240
Jo jums vēl ir jāpārbauda katru reizi. >> Jā.

546
00:32:05,240 --> 00:32:08,060
Un jums ir mijmaiņas tiem. >> Pat ja mēs cilvēki esam sava veida viszinošs

547
00:32:08,060 --> 00:32:10,770
tādā ziņā vizuāli ka mēs varam tikai veida redzēt, ka tas ir sakārtots,

548
00:32:10,770 --> 00:32:12,140
dators nav tik gudrs.

549
00:32:12,140 --> 00:32:14,040
Tas notiek, lai apskatīt šeit un šeit un šeit,

550
00:32:14,040 --> 00:32:16,610
bet, ja kas tas ir meklējat ir mazākais elements,

551
00:32:16,610 --> 00:32:22,110
jūs tikai zināt, ka jums atrast mazāko elementu ar kāda jēga? Kad esat beigās.

552
00:32:22,110 --> 00:32:25,880
Bet tajā brīdī, kad esat tikai atrast šobrīd mazākais elements.

553
00:32:25,880 --> 00:32:28,810
Jums nav obligāti zināt kaut ko citu par stāvokli pasaulē.

554
00:32:28,810 --> 00:32:30,880
Tātad jums ir jāiet atkal un atkal un atkal.

555
00:32:30,880 --> 00:32:34,880
>> Tāpēc šoreiz es tiešām izskatās muļķīgi, jo es esmu pārbaudes, labi, 2, tu esi mazākais,

556
00:32:34,880 --> 00:32:37,530
bet es nezinu, kas kopā vēl.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Labi, labi. 2 bija patiešām mazākais.

558
00:32:41,090 --> 00:32:43,150
Tagad pieņemsim atrast nākamais mazākais. Labi.

559
00:32:43,150 --> 00:32:48,350
3, tu esi šobrīd mazākais. Pieņemsim redzēt. 4, 5, 6, 7, 8. Labi, palaimējies vēlreiz.

560
00:32:48,350 --> 00:32:53,170
3 bija patiešām pareizajā vietā. Bet es esmu gatavojas glabāt to izdarīt atkal un atkal un atkal.

561
00:32:53,170 --> 00:32:55,990
Kā mēs to varam izdarīt kādreiz tik nedaudz labāk?

562
00:32:55,990 --> 00:33:00,120
Tā vietā cilvēki burbulis augšu pairwise no mazākā uz lielāko

563
00:33:00,120 --> 00:33:04,350
un nevis iet uz priekšu un atpakaļ pa sarakstu izvēloties tad mazākais personu,

564
00:33:04,350 --> 00:33:09,780
kāpēc nav mēs nevis ievietot šos cilvēkus jaunā saraksta soli pa solim?

565
00:33:09,780 --> 00:33:13,080
Mēģināsim šo. Tagad ļaujiet man zvanīt šī lieta ievietošanas veida.

566
00:33:13,080 --> 00:33:17,250
Tāpēc šeit mēs esam šeit. Numurs 1. Man vienalga par kāds cits šajā sarakstā.

567
00:33:17,250 --> 00:33:21,310
Mans mērķis tagad ir likt numuru 1 sākumā sakārtoti sarakstu.

568
00:33:21,310 --> 00:33:23,910
Un es esmu gatavojas ierosināt, jo man ir tikai 8 gabalos atmiņas,

569
00:33:23,910 --> 00:33:28,670
patvaļīgi šobrīd es esmu siena starp manu domājams nešķirotu sarakstā,

570
00:33:28,670 --> 00:33:32,740
un ikviens, kurš ir aiz manis es esmu gatavojas pieprasīt tiek sakārtoti.

571
00:33:32,740 --> 00:33:34,680
Tāpēc tagad mums ir numurs 1.

572
00:33:34,680 --> 00:33:39,240
Es gribu, lai ievietotu viņu manā sakārtoti sarakstā, tāpēc es esmu tikai gatavojas pārvietot manu sienas nekā šeit,

573
00:33:39,240 --> 00:33:43,930
un tagad es apgalvo šis saraksts tiek sakārtots, šis saraksts tiek nešķirotu - vismaz tik cik es zinu.

574
00:33:43,930 --> 00:33:46,070
Es nevaru redzēt visus skaitļus uzreiz.

575
00:33:46,070 --> 00:33:49,000
>> Tagad es notikt saskarties numuru 2. Ko man darīt ar viņu?

576
00:33:49,000 --> 00:33:54,380
Es ievietot tevi tagad uz sakārtotās sarakstā. Bet paziņojums, cik viegli tas bija.

577
00:33:54,380 --> 00:33:59,650
Man vienkārši ir meklēt. Numurs 1 ir tur. Ak, protams 2 iet uz pusi 1 numuru.

578
00:33:59,650 --> 00:34:03,700
Tagad ko man darīt ar 3? Es ievietot tevi sakārtotās sarakstā. Bet tas bija super viegli.

579
00:34:03,700 --> 00:34:07,250
Tas ir super viegli, tas ir super viegli, tas ir super viegli, super viegli, super vienkārši.

580
00:34:07,250 --> 00:34:12,790
Un tagad viss ir sakārtots aiz manis, un cik soļus bija kas ņem?

581
00:34:12,790 --> 00:34:15,620
[Studenti] N. >> Tātad tas ir tikai n. Mēs saņēmām laimīgs.

582
00:34:15,620 --> 00:34:18,860
Tas bija tikai n kāpēc? >> [Students] Jo saraksts tika sakārtots.

583
00:34:18,860 --> 00:34:21,630
Saraksts ir jau sakārtots. Tātad mēs saņēmām laimīgs.

584
00:34:21,630 --> 00:34:25,639
Bet mēs paredzēti algoritmu šoreiz ka siksnām šāda veida veiksmi,

585
00:34:25,639 --> 00:34:29,420
ka labākā scenārija, ko cienām nevajadzīgu laiku.

586
00:34:29,420 --> 00:34:31,750
Tāpēc mums tagad ir tas, ko mēs saucam burbulis veidu

587
00:34:31,750 --> 00:34:33,949
kur cilvēki veida burbulis up pairwise.

588
00:34:33,949 --> 00:34:38,100
Mums tagad ir izvēles veida kur mēs raut ārā mazāko persona atkal un atkal.

589
00:34:38,100 --> 00:34:42,350
Un tagad mums ir ievietošanas veida, kur mēs veida aktīvi likt cilvēkiem, kur tie pieder

590
00:34:42,350 --> 00:34:45,000
jo arvien šķiroto sarakstā.

591
00:34:45,000 --> 00:34:49,679
Ja mēs varētu, kārtu aplausi šie puiši šeit. [Aplausi]

592
00:34:49,679 --> 00:34:52,310
Paņemsim mūsu 5 minūšu pārtraukumu šeit.

593
00:34:52,310 --> 00:34:55,139
Un, kad mēs atgriezīsimies, mēs trieciens visu šo algoritmu no ūdens

594
00:34:55,139 --> 00:35:00,260
ar kaut ko labāku. Labi. Pateicoties ļoti daudz. Jūs varat saglabāt tos kā suvenīrus.

595
00:35:01,710 --> 00:35:04,330
Labi. Mēs esam atpakaļ.

596
00:35:04,330 --> 00:35:08,420
>> Un Atgādinājums reālā ātri, mums bija šīs 3 dažādas pieejas šķirošanu,

597
00:35:08,420 --> 00:35:13,000
viss punkts, kas bija nokļūt līdz vietai, kur kāds, piemēram, Alex

598
00:35:13,000 --> 00:35:16,930
varētu meklēt sarakstu numurus ātrāk nekā kāds, piemēram, Šons varētu.

599
00:35:16,930 --> 00:35:19,830
Un, pat ja mums ir tik vienkāršus piemērus ar 8 numuriem,

600
00:35:19,830 --> 00:35:24,000
Jūs varētu ekstrapolēt viegli līdz 8 web lapas, 8 miljardiem tīmekļa lappuses

601
00:35:24,000 --> 00:35:26,680
vai 800,000,000 draugiem par Facebook.

602
00:35:26,680 --> 00:35:30,090
Tāpēc šie algoritmi noteikti var mērogu uz tām vērtībām veidu,

603
00:35:30,090 --> 00:35:32,300
un idejas ir galu galā pats.

604
00:35:32,300 --> 00:35:36,140
Tātad burbulis šķirot bija pirmā, kur mēs veida kūsāja lielāko personu

605
00:35:36,140 --> 00:35:39,110
visu ceļu pa labi, ko pārnešana cilvēkus pairwise.

606
00:35:39,110 --> 00:35:42,040
Tad mums bija ko mēs saucam atlases veida kur es nedaudz vairāk apzināti

607
00:35:42,040 --> 00:35:46,480
tur meklē pa sarakstu, izvēloties mazāko skaitu atkal un atkal un atkal,

608
00:35:46,480 --> 00:35:49,530
loģisks rezultāts, kas ir tas, ka saraksts ir beidzot sakārtoti.

609
00:35:49,530 --> 00:35:53,780
Tad trešais, es ievietota cilvēkus savā piemērotā vietā,

610
00:35:53,780 --> 00:35:57,720
un mums bija ļoti izdomāts piemēru, ka sarakstā jau bija sakārtots,

611
00:35:57,720 --> 00:36:01,100
bet tas bija, lai nosūtītu ziņu, ka ienesto kārtot s gadījumā,

612
00:36:01,100 --> 00:36:02,670
Jūs varat saņemt laimīgs.

613
00:36:02,670 --> 00:36:07,930
Ja skaitļi ir jau sakārtoti, tas ir tikai gatavojas pieņemt jums n pasākumus, lai iegūtu tik daudz,

614
00:36:07,930 --> 00:36:10,870
tā atlases veida tu esi mazliet vairāk tuneļa redze

615
00:36:10,870 --> 00:36:14,360
un jums nav kādreiz saprast, ka saraksts ir jau sakārtots.

616
00:36:14,360 --> 00:36:16,830
Tātad, pieņemsim redzēt burbuli veida darbībā šeit.

617
00:36:16,830 --> 00:36:19,590
Šajā piemērā, mēs esam par to, lai redzētu vertikālas joslas

618
00:36:19,590 --> 00:36:23,030
, kuru augstums skaitļu, lai mēs varētu sakārtot no iztēloties šķirošanas notikt.

619
00:36:23,030 --> 00:36:26,630
Jo mazāks ir josla, jo mazāks skaits, jo lielāka ir josla, jo lielāks skaits.

620
00:36:26,630 --> 00:36:28,860
>> Un mēs spēlēt šajā noklusējuma ātrumu.

621
00:36:28,860 --> 00:36:33,460
Tas notiek, lai pārvietotu nedaudz ātri, lai tagad, bet sarkanā ir tas, ko rāda 2 bāri

622
00:36:33,460 --> 00:36:35,480
ko salīdzina blakus.

623
00:36:35,480 --> 00:36:39,520
Un, ja jums skatīties cieši, kas notiek, ir tas, ka, ja bars ir bojātas,

624
00:36:39,520 --> 00:36:42,300
mazākais viens izpaužas pārvietot pa kreisi, lielāku vienu pa labi,

625
00:36:42,300 --> 00:36:44,360
un tad jūs saglabāt padziļinot.

626
00:36:44,360 --> 00:36:48,520
Tātad, ja mēs atkal un atkal, ievērosiet, ka vismazākais stieņi

627
00:36:48,520 --> 00:36:51,090
gatavojas glabāt inching savu ceļu pa kreisi

628
00:36:51,090 --> 00:36:54,130
un lielākie bāri gatavojas glabāt inching savu ceļu pa labi.

629
00:36:54,130 --> 00:36:58,490
Un tiešām, mēs sākam redzēt modeli visu ceļu uz labajā pusē

630
00:36:58,490 --> 00:37:04,790
tāpat kā mēs redzējām 8 un tad līdz 7 beidzot burbuļošana līdz tālākajā galā mūsu cilvēku sarakstā.

631
00:37:04,790 --> 00:37:08,750
Tātad tas būs ļoti ātri iegūt mazliet garlaicīgs, tāpēc ļaujiet man apstāties tas uz brīdi.

632
00:37:08,750 --> 00:37:10,980
Ļaujiet man mainīt ātrumu, kas ir daudz ātrāk.

633
00:37:10,980 --> 00:37:15,380
Es neesmu mainot algoritmu, es esmu tikai padarot animācijas notikt ātrāk.

634
00:37:15,380 --> 00:37:18,410
Vēl burbulis kārtot, pats algoritms,

635
00:37:18,410 --> 00:37:21,910
bet tagad jūs varat redzēt daudz ātrāk nekā mūsu verbālās demonstrāciju

636
00:37:21,910 --> 00:37:25,900
ka lielākie elementi ir patiešām burbuļo uz augšu.

637
00:37:25,900 --> 00:37:29,860
>> Kā malā, šie maz kvadrātu apakšējā kreisajā un apakšējā labajā

638
00:37:29,860 --> 00:37:33,520
ir tikai maz atgādinājumus par to, cik daudz salīdzinājumi jūs darāt.

639
00:37:33,520 --> 00:37:37,620
Bet tagad, mēs varam koncentrēties uz piramīdas, kas ir ņemot formu, un tur tas notiek.

640
00:37:37,620 --> 00:37:41,510
Mazākais elements ir pa kreisi, lielākā par tiesībām, un viss pārējais pa vidu.

641
00:37:41,510 --> 00:37:44,470
Tagad tā vietā to apskatīt atlases veida.

642
00:37:44,470 --> 00:37:47,260
Es iešu uz priekšu un hit Stop. Mēs ejam, lai saņemtu jaunu izlases kopumu bāriem.

643
00:37:47,260 --> 00:37:50,930
Atlases kārtot, atsaukšana, iet cauri sarakstam atkal un atkal un atkal,

644
00:37:50,930 --> 00:37:54,900
noplūkšanas veic mazāko elementu. Tātad, šeit ir izvēle veida.

645
00:37:54,900 --> 00:37:58,390
Izskatās, tur ir mazāk darba notiek tagad, jo mēs esam ne salīdzinot pairwise

646
00:37:58,390 --> 00:38:02,590
bet mēs esam tikai veida ķiršu picking vismazākās elementus no labās uz kreiso pusi.

647
00:38:02,590 --> 00:38:06,890
Tas bija ļoti maz laika, tāpēc tur ir auglīgs jau.

648
00:38:06,890 --> 00:38:11,820
Tikai tāpēc, ka algoritms ir teikt, lai ņemtu n kvadrātā laiku, tāpat burbulis kārtot

649
00:38:11,820 --> 00:38:16,100
un tāpat atlases veida, tie ir patiešām vissliktākie gaitas reizes.

650
00:38:16,100 --> 00:38:21,790
Piemēram, ja, teiksim, atlases kārtot,

651
00:38:21,790 --> 00:38:27,240
Es tiešām esmu izvēloties mazāko personu un liekot viņam šeit,

652
00:38:27,240 --> 00:38:29,620
tad es esmu dara to vēlreiz, tad es esmu dara to vēlreiz,

653
00:38:29,620 --> 00:38:32,070
bet tur bija neliela optimizācija es varētu darīt.

654
00:38:32,070 --> 00:38:35,040
>> Tiklīdz es pārcēlos numuru 1 šeit - Sammy šajā gadījumā -

655
00:38:35,040 --> 00:38:38,630
Ko es jādara ar viņu pēc tam? >> [Students] viņu atstāt.

656
00:38:38,630 --> 00:38:40,140
Atstāt viņu, vai ne? Nekas.

657
00:38:40,140 --> 00:38:44,310
Man nav nepieciešams, lai kādreiz runāt ar Sammy vēlreiz, jo, ja man bija izvēlēts mazākais elements

658
00:38:44,310 --> 00:38:48,580
un nodot viņu šeit, kāpēc tērēt laiku iet uz beigām visu manu sarakstu?

659
00:38:48,580 --> 00:38:54,590
Par nākamo atkārtojuma ļaujiet man faktiski pārvietoties tikai ar 2 numuru, tikai 3 numuru.

660
00:38:54,590 --> 00:38:57,640
Tātad patiesībā, man nebija darīt n lietas n reizes.

661
00:38:57,640 --> 00:39:05,380
Man bija darīt n lietas, tad n - 1 lietām, tad n - 2 lietas, tad n - 3 lietas,

662
00:39:05,380 --> 00:39:07,080
tad n - 4, dot, dot, dot.

663
00:39:07,080 --> 00:39:09,470
Mums ir mazliet ģeometriskā progresijā, kas nozīmē tikai to,

664
00:39:09,470 --> 00:39:11,450
jūs summējot pakāpeniski mazāku skaitu.

665
00:39:11,450 --> 00:39:17,940
Ne n + n + n + n bet n + 7 + 6 + 5 + 4 + 3 + 2 + 1.

666
00:39:17,940 --> 00:39:21,380
Un ko tas vispār darbojas, lai būtu -

667
00:39:21,380 --> 00:39:24,280
Es esmu gatavojas izjaukt manu kuģa šeit tikai brīdi -

668
00:39:24,280 --> 00:39:28,990
kas notiek uz darbu, lai būtu kaut kas līdzīgs n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
ja mēs tikai veida paskatās atpakaļ uz matemātikas grāmatas, kur jums ir visas apkrāptu loksnes

670
00:39:31,930 --> 00:39:33,410
formulas.

671
00:39:33,410 --> 00:39:37,760
Ja jūs vienkārši pievienojot kaut n n - 1 + n - 2, tā darbojas, lai būtu kaut kas līdzīgs šim.

672
00:39:37,760 --> 00:39:42,320
Un, ja mēs tikai veida reizināt šo out, kas ir n rūtiņām mīnus N / 2.

673
00:39:42,320 --> 00:39:46,400
Es tur saka n rūtiņām, lai gan, un tas ir tāpēc, ka man bija veida ņemot garīgo īsceļu

674
00:39:46,400 --> 00:39:51,950
jo patiesībā, n kvadrātā mīnus n dalīts ar 2 ir patiešām taisnība skaits soļiem

675
00:39:51,950 --> 00:39:55,510
ka līdzīgi atlases veida algoritms būtu nepieciešams, ja mēs patiešām saskaitījām

676
00:39:55,510 --> 00:39:58,800
visus šos salīdzinājumus un visu maz aizņemts darbā mēs darām.

677
00:39:58,800 --> 00:40:03,210
Bet godīgi sakot, kad n izpaužas būt, piemēram, miljonu vai miljardu, kurš heck rūpējas

678
00:40:03,210 --> 00:40:07,160
ja jūs darāt miljardu brusas mīnus miljardu dalīts ar 2?

679
00:40:07,160 --> 00:40:09,320
Miljardus kvadrātā ir milzīgs skaits.

680
00:40:09,320 --> 00:40:13,580
Jūs varat veikt vēl miljardi off no tā ar - n. Tas nav tik liels galā.

681
00:40:13,580 --> 00:40:18,770
Tāpēc jo lielāks skaitļi saņemt, mazāk svarīgas šīs zemākas sakārtotu termini ir.

682
00:40:18,770 --> 00:40:24,230
Who cares, ja jūs sadalīt pa 2, ja jūs runājat par quadrillions skaita pakāpieni?

683
00:40:24,230 --> 00:40:29,710
>> Tātad kopumā, datorzinātnieku mēdz mest prom visu, bet lielāko termiņu,

684
00:40:29,710 --> 00:40:33,140
un mēs tikko veida vienkāršotu pasauli un teikt, ka algoritms

685
00:40:33,140 --> 00:40:38,130
paņēma aptuveni n rūtiņām soļus. Tas ir darbības laiks algoritma.

686
00:40:38,130 --> 00:40:40,760
Tātad mēs būsim atpakaļ uz šo tikai brīdi ar dažiem konkrētiem piemēriem,

687
00:40:40,760 --> 00:40:45,940
bet tagad, ka ir sava veida intuitīvo motivācijas aiz tikai vienkāršotu mūsu pasauli

688
00:40:45,940 --> 00:40:51,170
un runājot par svarīgākajiem nosacījumiem, nevis iegūt visus šos iedomātā formulām.

689
00:40:51,170 --> 00:40:53,540
Tā, ka bija atlase šķirot, un mēs saņēmām mazliet laimīgs tur.

690
00:40:53,540 --> 00:40:57,360
Apskatīsim ievietošanas šķirot. Ļaujiet man iet uz priekšu un sākt šo vienu, kā labi.

691
00:40:57,360 --> 00:41:00,330
Tagad paziņojums modelis, ka notiek ir nedaudz atšķirīgs,

692
00:41:00,330 --> 00:41:03,410
un mēs sākām ar izlases numurus,

693
00:41:03,410 --> 00:41:06,890
bet, ja mēs tiešām saskaitīt pasākumu skaitu sliktākajā gadījumā,

694
00:41:06,890 --> 00:41:11,070
ja sarakstā sākās pilnīgi pareizā secībā,

695
00:41:11,070 --> 00:41:13,380
mēs tikai veikt n pasākumus, lai realizētu tik daudz.

696
00:41:13,380 --> 00:41:18,240
>> Bet ja sarakstā ir faktiski atpakaļ - piemēram, šajā gadījumā šeit -

697
00:41:18,240 --> 00:41:23,860
tad ievērosiet mēs faktiski ir jādara daudz vairāk darbu šajā lietā.

698
00:41:23,860 --> 00:41:27,080
Un tas būtu sava veida justies jums patīk šī ir veida strādā smagāk

699
00:41:27,080 --> 00:41:30,900
lai saņemtu šos mazākus elementus pa kreisi, un tas ir tāpēc, ka mēs saņēmām nelaimīgs.

700
00:41:30,900 --> 00:41:34,210
Saraksts tika sakārtoti nejauši atpakaļgaitā.

701
00:41:34,210 --> 00:41:38,110
Savukārt, ar ienesto kārtot, ja mēs atdarinātu to, ko mēs izdarījām ar mūsu cilvēkiem šeit

702
00:41:38,110 --> 00:41:42,670
, sākot ar šķiroto ikvienam un tad sākt, tas ir diezgan labs algoritms, vai ne?

703
00:41:42,670 --> 00:41:45,010
Tas jau, patiesībā, sakārtoti.

704
00:41:45,010 --> 00:41:48,670
Tāpēc pieņemsim mēģināt apkopot tieši cik daudz laika šīs lietas ir ņemot mums

705
00:41:48,670 --> 00:41:52,360
ieviešot tikai par žargonu bitu vai nošu, kas ir faktiski daudz vienkāršāk

706
00:41:52,360 --> 00:41:54,320
nekā fanciness veida liecina.

707
00:41:54,320 --> 00:41:59,030
Šī lieta šeit, šo lielo O uz ekrāna, ir tas, ko dators zinātnieks parasti izmanto

708
00:41:59,030 --> 00:42:03,640
aprakstīt sliktāko darbības laiku algoritms.

709
00:42:03,640 --> 00:42:07,360
>> Atkal, sliktākajā gadījumā, tas ir pilnīgi atkarīga no konteksta.

710
00:42:07,360 --> 00:42:10,890
Ko mēs saprotam ar sliktākajā gadījumā pilnīgi mainās atkarībā no problēmas, mēs runājam.

711
00:42:10,890 --> 00:42:14,550
Bet attiecībā uz šķirošanu, kas ir sliktākais iespējamais scenārijs?

712
00:42:14,550 --> 00:42:17,860
Viss ir atpakaļ, jo tā vienkārši jūtas kā tas nozīmē, ka daudz darba, lai mums.

713
00:42:17,860 --> 00:42:21,330
Es esmu jotted leju dažas no algoritmiem, ka mēs esam redzējuši līdz šim:

714
00:42:21,330 --> 00:42:24,930
lineārā meklēšana, binārā meklēšana tāpat ar telefonu grāmatā, vai papīra gabaliņi,

715
00:42:24,930 --> 00:42:28,960
tad burbulis kārtot, atlase kārtot un ievietošanas kārtot kā mēs redzējām ar mūsu cilvēkiem,

716
00:42:28,960 --> 00:42:31,770
un tad vēl 1, kas ir beidzot būs sauc apvienot šķirot.

717
00:42:31,770 --> 00:42:37,710
Tātad lineārā meklēšanai sliktākajā gadījumā, cik soļus tas veic, lai atrastu numuru 7

718
00:42:37,710 --> 00:42:40,690
ja ir n durvis piemēram Sean saskārusies? >> [Students] N.

719
00:42:40,690 --> 00:42:44,180
N. Tāpēc mēs esam gatavojas rakstīt Big O n.

720
00:42:44,180 --> 00:42:47,010
Es esmu tikai gatavojas aizpildīt dažas sagataves. Tas ir tikai režģis sagataves.

721
00:42:47,010 --> 00:42:52,990
Bet labākajā gadījumā ar lineāro meklēšanā, 7 varētu būt pašā sākumā saraksta,

722
00:42:52,990 --> 00:42:55,520
un Sean varētu būt sākuši meklē sākumā sarakstā.

723
00:42:55,520 --> 00:42:58,940
Tātad, ja jūs izmantojat lineāro meklēšanu un tikai pārbaudīt kreisās uz labo vai varbūt no labās uz kreiso -

724
00:42:58,940 --> 00:43:02,650
viņi ekvivalents - labākajā gadījumā cik soļus varētu lineāra meklēšanu,

725
00:43:02,650 --> 00:43:05,550
piemēram Šona algoritmu, ņem? Tikai 1 solis.

726
00:43:05,550 --> 00:43:09,450
>> Tāpēc es esmu gatavojas teikt, ka ir omega apzīmējumu.

727
00:43:09,450 --> 00:43:11,570
Tas ir tikai kapitāla omega.

728
00:43:11,570 --> 00:43:15,000
Omega ir tikai seksīgs veids, kā pateikt labākajā gadījumā darba laika.

729
00:43:15,000 --> 00:43:18,900
Tātad labākajā gadījumā darbības laiks ir viens solis vai pastāvīga soļu skaitu -

730
00:43:18,900 --> 00:43:24,270
1 Šajā gadījumā - bet sliktākajā gadījumā, Big O, tas tiešām ir n soļi.

731
00:43:24,270 --> 00:43:28,110
Un šo vienu šeit, Theta, mēs faktiski nav skatīsies tieši tagad.

732
00:43:28,110 --> 00:43:30,090
Tas nav attiecināms uz šo konkrēto piemēru.

733
00:43:30,090 --> 00:43:31,990
Bet tagad pamēģināsim bināro meklēšanu.

734
00:43:31,990 --> 00:43:35,990
Sliktākajā gadījumā ar bināro meklēšanu, cik soļus ir tas gatavojas veikt, lai atrastu numuru 7

735
00:43:35,990 --> 00:43:38,340
vai kāds mēs meklējam? >> [Students] log n.

736
00:43:38,340 --> 00:43:40,980
Joprojām gatavojas veikt log n jo tāpat kā Alekss ieguva nelaimīgs

737
00:43:40,980 --> 00:43:44,030
kad mēs tiešām strādāja ar problēmu metodiski

738
00:43:44,030 --> 00:43:48,220
un viņa nav atrast numuru 7 līdz pēdējam durvīm viņa paskatījās,

739
00:43:48,220 --> 00:43:51,720
kaut gan, taisnīgumu, viņa dabūja mest prom dažas durvis pa ceļu,

740
00:43:51,720 --> 00:43:56,920
bināro meklēšanas sliktākajā gadījumā ir darbības laiku log n.

741
00:43:56,920 --> 00:43:59,230
Un atkal, kas runā uz šo dalot un iekarošana.

742
00:43:59,230 --> 00:44:01,140
Bet ko par labākajā gadījumā?

743
00:44:01,140 --> 00:44:04,790
Un Alex patiešām pieredzējis, ka labākajā gadījumā taisnība, kad viņa ieradās uz skatuves.

744
00:44:04,790 --> 00:44:07,290
Cik soļus bija kas ieņems binārā meklēt? >> [Students] 1.

745
00:44:07,290 --> 00:44:09,380
1, tikai tāpēc, ka viņa ieguva laimīgs.

746
00:44:09,380 --> 00:44:12,520
Bet tas ir labi, jo omega attiecas uz labāko scenāriju,

747
00:44:12,520 --> 00:44:15,770
labākajā gadījumā ieejas, pat ja tas ir tikai izlases mēms luck.

748
00:44:15,770 --> 00:44:18,900
>> Tagad, tas arī mēs esam gatavojas tikko veida atstāt tukšu tagad.

749
00:44:18,900 --> 00:44:21,010
Kā par tagad burbulis šķirot?

750
00:44:21,010 --> 00:44:24,290
Sliktākajā gadījumā ar burbulis šķirot, visi ir apgrieztā secībā,

751
00:44:24,290 --> 00:44:26,380
tāpēc mums ir jādara daudz burbuļošana.

752
00:44:26,380 --> 00:44:30,190
Bet cik soļus ir tas, ka gatavojas veikt sliktākajā gadījumā? >> [Students] N kvadrātā.

753
00:44:30,190 --> 00:44:32,550
Tas bija n kvadrātā, jo, ja jūs domājat par to,

754
00:44:32,550 --> 00:44:36,410
Ja saraksts ir pilnīgi atpakaļ - 8 ir vairāk nekā šeit, 1 ir vairāk nekā šeit -

755
00:44:36,410 --> 00:44:40,530
kā lieta sāk burbuļot, skaits 8 gatavojas pārcelties šādā veidā, šādā veidā,

756
00:44:40,530 --> 00:44:44,540
Tādā veidā, šādā veidā, bet kur ir par 7 sliktākajā gadījumā?

757
00:44:44,540 --> 00:44:47,720
Te viņa vēl joprojām ir tur. Tāpēc mums tas ir jādara atkal un atkal.

758
00:44:47,720 --> 00:44:53,190
Un tur mēs n soļi, tad n - 1 pakāpieni, tad n - 2 pakāpieni.

759
00:44:53,190 --> 00:44:55,960
Un, ja jūs ņemt manu vārdu par to - ka, ja jūs veida reizināt to ārā,

760
00:44:55,960 --> 00:45:00,110
tas rupji n brusas, kas beigās ar dažiem citiem noteikumiem, kas mēs vienkārši ignorēt tagad -

761
00:45:00,110 --> 00:45:06,890
tad sliktākajā gadījumā burbulis šķirot ir n rūtiņām, sniegt vai pieņemt.

762
00:45:06,890 --> 00:45:09,490
Bet ko par labākajā gadījumā ar burbulis šķirot?

763
00:45:09,490 --> 00:45:13,050
Kas ir labākais scenārijs? Visi numuri ir sakārtoti jau.

764
00:45:13,050 --> 00:45:15,920
Un kāda bija heiristiskā es, triks es,

765
00:45:15,920 --> 00:45:20,110
lai saprastu, ka man bija darīts nekādu darbu un tādējādi varētu apturēt agri?

766
00:45:20,110 --> 00:45:23,590
[Students] Pārbaudīt to vienu reizi. >> Pārbaudiet to vienu reizi. Bet ko bija daru pa ceļu?

767
00:45:23,590 --> 00:45:26,130
Man bija sekot tam, cik daudz mijmaiņa es.

768
00:45:26,130 --> 00:45:30,650
Un es sapratu, ja man nav ieskaitīts nevienu mijmaiņa par manu pirkstiem, tad es esmu darījusi nav darba.

769
00:45:30,650 --> 00:45:34,300
Es noteikti nevajadzētu mēģināt darīt nekādu darbu atkal, lai es varētu vienkārši apstāties.

770
00:45:34,300 --> 00:45:37,830
>> Tātad labākajā gadījumā uz burbuļa veida kad saraksts jau ir sakārtots,

771
00:45:37,830 --> 00:45:41,530
Ko jūs teiktu, ka omega notācija ir, labākajā gadījumā darba laika?

772
00:45:41,530 --> 00:45:48,040
Tas ir tikai n. Mums ir darīt kādu darbu, bet mums jādara tikai 1 pastaiga vērts darbu.

773
00:45:48,040 --> 00:45:50,490
Un arī šeit es esmu gatavojas atstāt šo daļu tukšu.

774
00:45:50,490 --> 00:45:52,430
Un tagad izvēle kārtot.

775
00:45:52,430 --> 00:45:56,010
Atlases kārtot bija mani noplūkšanas mazāko persona atkal un atkal.

776
00:45:56,010 --> 00:45:58,380
Un ko mēs sakām darbības laiks, kas bija?

777
00:45:58,380 --> 00:46:00,590
Tas bija n rūtiņām sliktākajā gadījumā.

778
00:46:00,590 --> 00:46:05,220
Un diemžēl, labākajā gadījumā tas ir arī n kvadrātā

779
00:46:05,220 --> 00:46:08,840
jo man nav tāda veida visuzinošajam Ņemot vērā visā pasaulē;

780
00:46:08,840 --> 00:46:13,140
Es tikai zinu, pēc pilna atkārtojuma ka es esmu patiešām konstatēja mazāko personu.

781
00:46:13,140 --> 00:46:15,860
Tātad izvēle veida veida sucks ziņā,

782
00:46:15,860 --> 00:46:17,920
bet otrādi ir tas veida intuitīvi.

783
00:46:17,920 --> 00:46:21,470
Tas ir diezgan viegli kodu augšu, jo viss, kas jums jādara, ir uzrakstīt pāris ligzdotu uz cilpas,

784
00:46:21,470 --> 00:46:24,620
parasti, kas iet cauri meklē mazāko elementu

785
00:46:24,620 --> 00:46:27,840
un tad liek mazāko elementu, ja tā pieder pie saraksta beigās.

786
00:46:27,840 --> 00:46:29,900
Tātad arī šeit būs kompromiss.

787
00:46:29,900 --> 00:46:34,440
Laika daudzums, kas nepieciešams, lai jūs domāt un faktiski attīstīt kaut ko rakstot kodu

788
00:46:34,440 --> 00:46:39,460
varētu ļoti labi aizņemt vairāk laika, ja jūs vēlaties labāku algoritmu un ātrāku veiktspēju.

789
00:46:39,460 --> 00:46:41,780
>> Bet, ja jūs patiešām tikai veida kodu kaut up ātri un netīrās

790
00:46:41,780 --> 00:46:45,000
un tikai veida veikt stupidest iespējamo ideju jūs varat iedomāties,

791
00:46:45,000 --> 00:46:47,580
kas varētu veikt jums dažas minūtes, lai kodu, bet ar lielu datu kopu

792
00:46:47,580 --> 00:46:49,580
Jūsu algoritms varētu aizņemt laiku, lai palaistu.

793
00:46:49,580 --> 00:46:51,690
Un pat es absolvents skolā būtu reizēm šiem kompromisiem.

794
00:46:51,690 --> 00:46:55,660
Tas būtu 03:00, es centos analizēt kādu ļoti lielu datu kopu

795
00:46:55,660 --> 00:46:59,650
saistīti ar drošības pētniecības es daru, un tas bija vai nu pavadīt 5 minūtes

796
00:46:59,650 --> 00:47:03,210
tweaking savu programmu, lai analizētu datus un iet gulēt

797
00:47:03,210 --> 00:47:08,420
vai pavadīt 8 stundas iegūt to tikai tiesības, lai tā darbojas uzreiz, nevis iet gulēt.

798
00:47:08,420 --> 00:47:10,530
Un tāpēc arī tur tas ir sava veida apzināts lēmums.

799
00:47:10,530 --> 00:47:12,740
Mazāk izstrādes laiku, vairāk miega.

800
00:47:12,740 --> 00:47:14,780
Atskatoties pagātnē, es, iespējams, nedrīkst veicināt ka

801
00:47:14,780 --> 00:47:19,120
ja mērķis šeit ir, lai optimizētu kvalitāti no koda,

802
00:47:19,120 --> 00:47:21,280
bet ka pārāk reālajā pasaulē ir ļoti saprātīgs kompromiss.

803
00:47:21,280 --> 00:47:25,130
Mazāk laika, mazāk sniegums vai otrādi.

804
00:47:25,130 --> 00:47:28,110
Tātad šeit mēs beidzot ir iespēja runāt par theta.

805
00:47:28,110 --> 00:47:32,830
Theta notācija ir kaut datorzinātnieku var audzināt sarunā

806
00:47:32,830 --> 00:47:36,160
kad liels O un omega notikt ir tas pats.

807
00:47:36,160 --> 00:47:40,160
Jums teikt Theta patiešām nosūtītu ziņu, ka šis ir sava veida saspringts saistoši.

808
00:47:40,160 --> 00:47:43,340
Nav svarīgi, vai scenārijs ir labi vai slikti, tas ir n rūtiņām.

809
00:47:43,340 --> 00:47:46,510
Tātad, tas vienkārši nav nozīmes šiem stāstiem šeit.

810
00:47:46,510 --> 00:47:48,560
Ievietošanas kārtošanas ir pēdējais mēs paskatījās,

811
00:47:48,560 --> 00:47:50,830
kur man bija tikai ievietojot ikvienu uz pareizā vietā.

812
00:47:50,830 --> 00:47:54,930
Labākajā gadījumā, kāda bija darba laiks ievietošanas veida, kā mēs redzējām to šeit?

813
00:47:54,930 --> 00:47:57,250
[Students] labākajā gadījumā? >> Labākā gadījumā.

814
00:47:57,250 --> 00:48:00,100
>> Tas tika n jo labākajā gadījumā ikvienam sakārtoti,

815
00:48:00,100 --> 00:48:02,580
un Sammy un neviens cits īsti bija pārvietoties vispār.

816
00:48:02,580 --> 00:48:04,610
Viņi bija jau savā īstajā vietā.

817
00:48:04,610 --> 00:48:08,570
Tātad ievietošanas šķirot labākajā gadījumā ir, šajā gadījumā, n.

818
00:48:08,570 --> 00:48:12,770
Bet sliktākajā gadījumā tas ir sava veida n rūtiņām. Kāpēc?

819
00:48:12,770 --> 00:48:16,230
Ja mans saraksts cilvēkam ir apgrieztā kārtībā,

820
00:48:16,230 --> 00:48:21,260
Es vispirms sākt ar numuru 8, un es ievietot viņam vai viņai uz pareizā stāvoklī, kas ir šeit.

821
00:48:21,260 --> 00:48:25,270
Es veida pāreja uz pusi. Šie puiši ir nešķirotu, ka viņš vai viņa ir sakārtots.

822
00:48:25,270 --> 00:48:28,970
Bet tagad es notikt, lai atrastu, kurš nākamais? >> [Students] 7.

823
00:48:28,970 --> 00:48:31,250
7 sliktākajā gadījumā, jo tas ir apgrieztā secībā.

824
00:48:31,250 --> 00:48:34,920
>> Tātad šeit ir 7. Kur tas 7 pieder? Noteikti aiz manis.

825
00:48:34,920 --> 00:48:39,460
Bet tagad 7 patiesībā pieder nevis uzreiz aiz manis, bet aiz numuru 8,

826
00:48:39,460 --> 00:48:41,880
tāpēc man ir jāsaka: "Piedodiet, numuru 8, jūs varat lūdzu pārvietot šo ceļu

827
00:48:41,880 --> 00:48:44,640
", Lai padarītu telpu 7?" Tagad man rodas 6.

828
00:48:44,640 --> 00:48:48,530
"Ak, atvainojiet mani, skaits 8 un numuru 7, jūs varat pārvietot, lai padarītu telpu 6?"

829
00:48:48,530 --> 00:48:52,360
Tātad citiem vārdiem sakot, ar ievietošanas šķirot, lai gan es neesmu dara daudz kustību,

830
00:48:52,360 --> 00:48:56,330
aiz manis cilvēki dara daudz vairāk darba, un tas ir nokļuvis uz izmaksu kāds laiks.

831
00:48:56,330 --> 00:48:58,000
Tas notiek uz izmaksu datora laiku.

832
00:48:58,000 --> 00:49:01,450
Tātad gadījumā, ja ievietošanas veida mēs joprojām cieš.

833
00:49:01,450 --> 00:49:06,260
Ja jūs sākat saskaitot kopējo skaitu soļus, mēs galu galā hitting rupji N brusas

834
00:49:06,260 --> 00:49:11,160
jo šie puiši ir nepieciešams, lai padarītu telpu cilvēka jāievieto atpakaļ šajā sarakstā.

835
00:49:11,160 --> 00:49:15,960
Un tāpēc šajā gadījumā Theta ir vienkārši nav piemērojams ar konkrētu stāstu pie rokas.

836
00:49:15,960 --> 00:49:21,100
Tas ir viss jauki un labi. Mums ir šie 3 dažādas iespējas runāt par braukšanas laiku.

837
00:49:21,100 --> 00:49:26,370
Bet ko tas patiesībā nozīmē reālā izteiksmē, ja mēs faktiski cenšamies koda līdz algoritmu?

838
00:49:26,370 --> 00:49:31,620
>> Ļaujiet man ieteikt, ka tur pat labāk algoritms, kas tur

839
00:49:31,620 --> 00:49:33,740
ka pati ir daži kompromisi.

840
00:49:33,740 --> 00:49:36,890
Mēs ejam, lai izsauktu to apvienot veida, un tas ir sava veida šo burvju algoritma

841
00:49:36,890 --> 00:49:42,840
kas vienkārši darbojas ātrāk kaut kā, un tas ir tik viegli izteikt, vismaz pseudocode.

842
00:49:42,840 --> 00:49:46,900
Šīs algoritma sapludināšanas veida ieviešana būs šādi.

843
00:49:46,900 --> 00:49:50,860
Kad jūs esat dota n elementiem - N ciparus n cilvēki, neatkarīgi - Vispirms tur ir veselība pārbaudītu.

844
00:49:50,860 --> 00:49:56,340
Ja n ir mazāks par 2, apvienot šķirot vienkārši apstājas. Tas atgriežas, lai runāt.

845
00:49:56,340 --> 00:50:00,830
Kāpēc jūs pārtraukt, ja n ir mazāks nekā 2? >> [Dzirdams studentu reaģēšanas]

846
00:50:00,830 --> 00:50:04,480
Tiesības. Un atkal, n nav numurs sarakstā, n ir lielums sarakstā.

847
00:50:04,480 --> 00:50:07,660
Ja n ir mazāks par 2, tas nozīmē, ka jūsu saraksts ir vai nu 1,

848
00:50:07,660 --> 00:50:09,640
kur jūs acīmredzot sakārtoti, ja tas ir 1 numurs,

849
00:50:09,640 --> 00:50:11,710
vai 0, un šajā gadījumā nekas, lai sakārtotu,

850
00:50:11,710 --> 00:50:13,570
tāpēc mums ir nepieciešams šāda veida gadījumu.

851
00:50:13,570 --> 00:50:20,350
Ja saraksts ir tik īss, ka tur ir tikai nekas jādara, burtiski neko nedara. Atgriezties.

852
00:50:20,350 --> 00:50:25,090
Pretējā kārtot kreiso pusi no elementiem, tad šķirot labo pusi elementiem,

853
00:50:25,090 --> 00:50:27,410
pēc tam apvienot 2 sakārtoti pusītes.

854
00:50:27,410 --> 00:50:32,130
>> Šāda veida šķiet maz blēdis kuru es esmu jautā, kā kārtot elementus

855
00:50:32,130 --> 00:50:34,900
un tu man saki, "kārtot kreiso pusi, šķirot labo pusi."

856
00:50:34,900 --> 00:50:37,240
Es, piemēram, "viss kārtībā Kā jūs kārtot kreiso pusi?".

857
00:50:37,240 --> 00:50:40,670
"Kārtošana kreiso pusi kreisajā pusē, šķirot labo pusi kreisajā pusē, un tad jādara."

858
00:50:40,670 --> 00:50:44,060
Tu esi veida cikliski definēt, ko tas nozīmē, lai kārtotu,

859
00:50:44,060 --> 00:50:46,790
bet izrādās, ka patiesībā izcili šajā lietā.

860
00:50:46,790 --> 00:50:50,230
Tas nav patiesi šo apburto loku, kas nekad nebeidzas

861
00:50:50,230 --> 00:50:52,550
jo tas beidzas, kad? >> [Students] Kad jūs sasniedzat 1 lieta.

862
00:50:52,550 --> 00:50:54,220
Kad jūs sasniedzat 1 lieta.

863
00:50:54,220 --> 00:50:57,850
Tātad, pat ja jūs varētu sākt ar 8 cilvēkiem, un es saku, "kārtot kreiso pusi šiem cilvēkiem,

864
00:50:57,850 --> 00:51:00,480
šie 4 cilvēki, "tad es saku:" Kā jūs kārtot kreiso pusi? "

865
00:51:00,480 --> 00:51:03,450
"Nu, šķirot 2 cilvēki šeit." Un tad jūs, piemēram, "Labi, labi."

866
00:51:03,450 --> 00:51:05,520
"Kā jūs kārtot kreiso pusi no tiem cilvēkiem?"

867
00:51:05,520 --> 00:51:09,040
"Vienkārši sakārtot šo 1 personai šeit." Kas izcili atklāsme tagad?

868
00:51:09,040 --> 00:51:13,050
Man ir, lai sakārtotu 1 personu. Darīts. Man nav darīt jebkuru darbu.

869
00:51:13,050 --> 00:51:16,580
Bet tagad man ir, lai sakārtotu šo personu, bet viņi viens cilvēks, neko darīt.

870
00:51:16,580 --> 00:51:21,490
>> Tātad burvju acīmredzot ir šajā Trešais solis: apvienot sakārtoti pusītes.

871
00:51:21,490 --> 00:51:25,770
Tāpēc apvienot kārtot ņem šo izcili ieskatu, ka, ja jūs pauze liela problēma leju

872
00:51:25,770 --> 00:51:28,650
uz 2 mazākos, identiski lieluma problēmas

873
00:51:28,650 --> 00:51:32,710
un tad tikai veida līmi mazākiem risinājumi kopā beigās,

874
00:51:32,710 --> 00:51:34,720
Es ierosinu, ka mēs varam darīt daudz, daudz labāk [pieskaroties skaņu]

875
00:51:34,720 --> 00:51:38,050
nekā jebkura atlases veida vai ievietošanas šķirot.

876
00:51:38,050 --> 00:51:40,690
Es esmu faktiski ignorējot ka pusstundu, bet es tiešām nezinu, kas notiek

877
00:51:40,690 --> 00:51:45,040
ārpus šodien. [Whirring skaņa] [smiekli]

878
00:51:45,040 --> 00:51:49,660
Tātad, pieņemsim redzēt, ja mēs varam redzēt to ar nelielu palīdzību no mūsu drauga Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Ir 2 lieli soļi procesā sapludināšanas kārtošanas.

880
00:51:52,810 --> 00:51:56,400
Pirmkārt, nepārtraukti sadalīt sarakstu tases uz pusēm

881
00:51:56,400 --> 00:51:59,610
līdz mums ir ķekars sarakstos tikai ar 1 glāzi tiem.

882
00:51:59,610 --> 00:52:02,150
Neuztraucieties, ja sarakstā ir nepāra skaits

883
00:52:02,150 --> 00:52:04,830
un jūs nevarat veikt pilnīgi tīru griezumu starp tiem.

884
00:52:04,830 --> 00:52:08,740
Tikai patvaļīgi izvēlēties, kuras sarakstā iekļaut papildu tasi iekšā

885
00:52:08,740 --> 00:52:11,320
Tāpēc pieņemsim sadalīt šos sarakstus.

886
00:52:12,420 --> 00:52:14,570
Tagad mums ir 2 saraksti.

887
00:52:18,930 --> 00:52:20,930
Tagad mums ir 4 sarakstus.

888
00:52:25,730 --> 00:52:28,740
Tagad mums ir 8 saraksti ar vienu tasi katrā sarakstā.

889
00:52:28,740 --> 00:52:31,520
Tā ka tas uz 1 soli.

890
00:52:31,520 --> 00:52:37,280
Par soli 2 Mēs vairākkārt apvienot pārus saraksti, izmantojot sapludināšanas algoritmu mēs uzzinājām pirms tam.

891
00:52:37,280 --> 00:52:44,320
Apvienojot 108 un 15 mēs galu galā ar sarakstu 15, 108.

892
00:52:45,240 --> 00:52:51,330
Apvienojot 50 un 4 Mēs galu galā ar 4, 50.

893
00:52:51,330 --> 00:52:56,950
Apvienojot 8 un 42 mēs galu galā ar 8, 42.

894
00:52:57,790 --> 00:53:04,360
Un apvienojot 23 un 16 Mēs galu galā ar 16, 23.

895
00:53:04,360 --> 00:53:08,030
Tagad visi mūsu saraksti ir 2 izmēru.

896
00:53:08,030 --> 00:53:10,980
Ievērojiet, ka katrā no 4 sarakstiem ir sakārtoti,

897
00:53:10,980 --> 00:53:14,230
lai mēs varētu sākt apvienojot pārus sarakstos atkal.

898
00:53:14,230 --> 00:53:22,150
Apvienojot 15 un 108 un 4 un 50 mēs vispirms veic 4, tad 15,

899
00:53:22,150 --> 00:53:26,250
tad 50, tad 108.

900
00:53:26,250 --> 00:53:33,020
Apvienojas 8, 42 un 16, 23, mēs vispirms veic 8, tad 16,

901
00:53:33,020 --> 00:53:37,170
tad 23, tad 42.

902
00:53:37,170 --> 00:53:42,490
Tāpēc tagad mums ir tikai 2 saraksti 4 izmēra, no kuriem katrs ir sakārtots.

903
00:53:42,490 --> 00:53:45,940
Tāpēc tagad mēs apvienot šos 2 sarakstus.

904
00:53:45,940 --> 00:53:54,230
Vispirms mēs ņemtu 4, tad mēs ņemtu 8, tad mēs ņemtu 15

905
00:53:54,230 --> 00:54:05,280
un 16 un 23 un 42 un 50 un 108.

906
00:54:05,280 --> 00:54:09,020
Un mēs esam darīts. Mums tagad ir sakārtoti sarakstu.

907
00:54:09,020 --> 00:54:13,740
>> Rob bija veida gūst priekšrocības, ko mēs to vēl nav izdarījušas.

908
00:54:13,740 --> 00:54:16,540
Tika ierosināts, bet mēs faktiski nav darīt to.

909
00:54:16,540 --> 00:54:19,230
Viņš dara kaut ko fiziski ar kausiem, kas liecina,

910
00:54:19,230 --> 00:54:23,680
Viņš bija izdevumu dažas resurss bez laika. >> [Students] Kosmosa. >> Tas bija telpa.

911
00:54:23,680 --> 00:54:27,360
Tas, ka viņš bija šāda veida bi līmeņa galda, kur viņš bija telpa līdz šeit

912
00:54:27,360 --> 00:54:31,960
un kosmosa noteikti šeit bija faktiski nozīmē to, ka viņš, izmantojot divreiz tik daudz vietas

913
00:54:31,960 --> 00:54:36,390
kā jebkurš no mūsu algoritmu, kas līdz šim - ievietošana kārtot, burbulis šķirot, vai atlase kārtot -

914
00:54:36,390 --> 00:54:40,780
bet viņš bija piesaistot šo papildu iespējas veida pārvietotu lietas uz priekšu un atpakaļ

915
00:54:40,780 --> 00:54:42,600
vienlaikus saglabājot lietas kārtībā.

916
00:54:42,600 --> 00:54:47,540
Un pat ja tā uzskata, tāpat kā mēs saņēmām uz sakārtoti sarakstu, ka jutos kā tas bija, bet.

917
00:54:47,540 --> 00:54:51,060
Patiesībā tas, ko Robs bija darīt bija tieši šis algoritms.

918
00:54:51,060 --> 00:54:56,780
Viņš pirmo reizi paņēma problēmu izmērs N, sadalīts to par kreiso pusi un labo pusi.

919
00:54:56,780 --> 00:54:59,380
Tas ir, kad viņš pārcēlās kausus. Tad viņš atkārtoja šo procesu.

920
00:54:59,380 --> 00:55:03,390
Viņš sadalīta 4 savos 2 komplekti 2 nekā šeit un vairāk nekā šeit.

921
00:55:03,390 --> 00:55:08,520
Tad viņš atkārtoja šo procesu un sadala 2 komplekti 1 katram no šiem dažādu tases 2.

922
00:55:08,520 --> 00:55:11,000
Un tas ir, ja izcili iespēja rodas.

923
00:55:11,000 --> 00:55:15,840
Tajā brīdī stāstā, Robs bija 8 sarakstus apjomu 1,

924
00:55:15,840 --> 00:55:18,860
kuras visas sakārtoti jau.

925
00:55:18,860 --> 00:55:20,630
>> Tātad tad ko viņš turpinātu to darīt?

926
00:55:20,630 --> 00:55:25,260
Pairwise viņš bija šīs sakārtoti sarakstu un šo sakārtoti sarakstu un apvienoja tos.

927
00:55:25,260 --> 00:55:28,200
Tad viņš paņēma šo vienu un apvienoja tos, tad šo vienu un apvienoja tos,

928
00:55:28,200 --> 00:55:30,670
tad tas viens un apvienoja tos.

929
00:55:30,670 --> 00:55:32,390
Un tad ko viņš dara tālāk?

930
00:55:32,390 --> 00:55:36,580
Pēc tam viņš atkal apvienojās lielākos sarakstus un pēc tam atkal apvienojās lielākos sarakstus.

931
00:55:36,580 --> 00:55:41,170
Un, ja jūs domājat par šo vienkārši intuitīvi tagad, Ko viņš īsti dara?

932
00:55:41,170 --> 00:55:45,450
Viņš bija dalot šo problēmu uz pusi, uz pusēm, uz pusēm, uz pusi

933
00:55:45,450 --> 00:55:47,600
Lai saņemtu šo super mazos sarakstus.

934
00:55:47,600 --> 00:55:51,290
Tad viņš bija veida apvienojot dubultā, dubultā, dubultā, dubultā.

935
00:55:51,290 --> 00:55:54,120
Tāpēc viņš dara divreiz tik daudz strādāt, kā mēs esam redzējuši līdz šim

936
00:55:54,120 --> 00:55:56,930
ar jebko, kas ietver skaldi un valdi, bet nav liels darījumu.

937
00:55:56,930 --> 00:55:59,630
Divreiz tik daudz darba, nav tik liels darījumu. Tas ir tikai nemainīgs faktors.

938
00:55:59,630 --> 00:56:03,920
Un līdzīgi mūsu aritmētisko izteiksmi pirms, es esmu tikai gatavojas izsvītrot konstante faktori

939
00:56:03,920 --> 00:56:10,170
tāpat kā 2 reizes. Who cares? Ja tas ir 2 miljardiem reizes 2, tas joprojām daudz pasākumus.

940
00:56:10,170 --> 00:56:13,160
Tātad šī apvienošana solis šķiet galvenais ieskats.

941
00:56:13,160 --> 00:56:17,000
Apskatīsim šo tikai skaitliski pirms - Ak, tas nav jāturpina vēl.

942
00:56:17,000 --> 00:56:22,890
Apskatīsim šo skaitliski tikai reāli redzēt, kā tas spēlē out.

943
00:56:22,890 --> 00:56:25,940
Tas ir galvenokārt tikai nedaudz nabaga vīra animācijas.

944
00:56:25,940 --> 00:56:27,750
Pieņemsim ierosināt šo.

945
00:56:27,750 --> 00:56:31,480
Darbības laiks sapludināšanas veida - mums vienkārši vajag veidu, kā runāt par to.

946
00:56:31,480 --> 00:56:34,380
Tas nav matemātika, tas ir tikai sava veida īsu veidā izteikt sevi.

947
00:56:34,380 --> 00:56:39,080
Tātad T attēlo laiku un n ir ko? >> [Students] lielums no -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] problēmas apjomu, cilvēku skaits.

949
00:56:41,400 --> 00:56:45,470
Tāpēc es esmu apgalvojot, ka darba laiks, lai sakārtotu n cilvēkus būs 0 daudz laika

950
00:56:45,470 --> 00:56:50,290
ja n ir mazāks par 2, jo, ja jums ir 1 tasi vai nav krūzes, jums nekas nav jākārto.

951
00:56:50,290 --> 00:56:55,160
Bet vispār, es esmu gatavojas ierosināt darba laiks, lai sakārtotu n elementiem

952
00:56:55,160 --> 00:56:59,350
būs laiks, kas nepieciešams, lai sakārtotu kreiso pusi plus labo pusi

953
00:56:59,350 --> 00:57:03,110
plus - kas tas ir papildu + N? >> [Students] sapludināšana kārtošanas.

954
00:57:03,110 --> 00:57:07,260
[Malan] Tas patiesībā apvienojas, jo, ja jums ir n / 2 elementi šeit

955
00:57:07,260 --> 00:57:11,500
un jums ir n / 2 elementus šeit, cik daudz laika tas veic, lai tos apvienot?

956
00:57:11,500 --> 00:57:15,050
Tāpat kā Rob, jums ir apzagt šo vienu vairāk nekā šeit, varbūt iekšas nekā šeit,

957
00:57:15,050 --> 00:57:17,120
apzagt nekā šeit, raut nekā šeit, raut nekā šeit.

958
00:57:17,120 --> 00:57:19,400
Jums ir pieskarties viens no kausiem reizi.

959
00:57:19,400 --> 00:57:22,030
Un, ja tur ir 4 glāzes plus 4 tases, kas ir 8 glāzes

960
00:57:22,030 --> 00:57:25,200
vai vispārīgāk, 8 n tases.

961
00:57:25,200 --> 00:57:28,470
Tāpēc apvienojas solis mēs varam izteikt kā n,

962
00:57:28,470 --> 00:57:31,330
un kas burtiski ietver vairākas reizes Rob fiziski aizskāris

963
00:57:31,330 --> 00:57:33,410
viens no tiem putuplasta tases.

964
00:57:33,410 --> 00:57:35,850
Tāpēc pieņemsim tagad darīt patvaļīgu piemēru.

965
00:57:35,850 --> 00:57:41,850
Ja tur ir 16 kausi, kas ir darbības laiks šķirošanai, izmantojot Rob algoritms, 16 tases?

966
00:57:41,850 --> 00:57:44,710
Tas ir 2 reizes laika daudzums, kas nepieciešams, lai kārtotu 8 glāzes

967
00:57:44,710 --> 00:57:46,920
jo mums ir 8 glāzes šeit, 8 glāzes šeit.

968
00:57:46,920 --> 00:57:51,520
Es nezinu, cik ilgi tas notiek, tāpēc mēs vispārinot to kā T uz šo brīdi.

969
00:57:51,520 --> 00:57:53,320
Kurš zina, kas tas ir?

970
00:57:53,320 --> 00:57:58,990
Bet tagad es varu veida rekursīvi vai atkārtoti uzdot to pašu jautājumu.

971
00:57:58,990 --> 00:58:01,920
Cik daudz laika tas veic, lai sakārtotu 8 glāzes?

972
00:58:01,920 --> 00:58:07,030
8 glāzes es esmu gatavojas teikt aizņem laiku, kas nepieciešams, lai kārtotu 4 tases plus 4 glāzes,

973
00:58:07,030 --> 00:58:08,880
tam apvienojot tos kopā.

974
00:58:08,880 --> 00:58:13,080
Fine. Mēs esam nokļūst ciklā jau. Cik ilgs laiks nepieciešams, lai kārtotu 4 tases?

975
00:58:13,080 --> 00:58:19,150
Laiks, kas nepieciešams, lai sakārtotu 4 tases ir 2 glāzes plus 2 tases šķirošanas plus apvienošanās procesu.

976
00:58:19,150 --> 00:58:21,440
Fine. Cik ilgs laiks nepieciešams, lai sakārtotu 2 tases?

977
00:58:21,440 --> 00:58:26,290
2 glāzes ir laika daudzums, kas nepieciešams, lai kārtotu 1 tase plus laiks, kas nepieciešams, lai sakārtotu vēl vienu tasi

978
00:58:26,290 --> 00:58:29,040
plus laika daudzums, kas nepieciešams apvienoties, kas ir tikai 2.

979
00:58:29,040 --> 00:58:33,340
>> Fine. Pēdējais jautājums. Cik ilgs laiks nepieciešams, lai kārtotu 1 tasi?

980
00:58:33,340 --> 00:58:37,260
Šeit ir bāzes scenārijs, ka mēs prognozēts mēs gribētu hit agrāk.

981
00:58:37,260 --> 00:58:42,250
Fakts, ka tā neuzņemas nekādu darbu nekāda lai sakārtotu mazāko no problēmām

982
00:58:42,250 --> 00:58:44,120
nozīmē, ka tagad, kārtot pamatskolas stilu,

983
00:58:44,120 --> 00:58:46,460
mēs varam tikai iet sākt tapām šos skaitļus atpakaļ iekšā

984
00:58:46,460 --> 00:58:50,630
Mēs tagad zinām, kas T 1 ir, lai es varētu plug 0 par T 1.

985
00:58:50,630 --> 00:58:54,420
Tas dod man atbildi uz T 2, kas es pēc tam var plug augstāk.

986
00:58:54,420 --> 00:58:56,930
Tas dod man T no 4, ko es var spraudni augstāk.

987
00:58:56,930 --> 00:58:58,920
Tas dod man T no 8, ko es var spraudni augstāk.

988
00:58:58,920 --> 00:59:04,330
Un, ja es tiešām, ka math, pieslēdzot šīm atbildēm,

989
00:59:04,330 --> 00:59:08,590
Es pēc tam saņemt T gada 16 ir 64.

990
00:59:08,590 --> 00:59:12,090
Un ko 64 pārstāv?

991
00:59:12,090 --> 00:59:15,700
Ja T ir 16, jā, tas ir 16 reizes 4.

992
00:59:15,700 --> 00:59:20,120
Tāpēc es apgalvo, ka šobrīd darbojas laiks šo lietu sauc apvienot šķirot -

993
00:59:20,120 --> 00:59:22,590
un tas būs Fanciest no tiem mēs esam redzējuši līdz šim -

994
00:59:22,590 --> 00:59:26,160
gatavojas saukt n log n

995
00:59:26,160 --> 00:59:31,140
jo cik reizes var apzagt sadalīt veselu ķekars tases uz pusēm? Log n.

996
00:59:31,140 --> 00:59:34,370
Tas ir tāpat kā telefona grāmatu, piemēram, tas ir tāds pats kā sevis skaitīšanas piemērs.

997
00:59:34,370 --> 00:59:36,380
>> Cik reizes jūs varat sadalīt kaut pusi?

998
00:59:36,380 --> 00:59:38,410
Tomēr, tur ir tas apvienojas solis.

999
00:59:38,410 --> 00:59:42,920
Jums varētu būt sadalīt kausus uz pusi atkal un atkal un atkal,

1000
00:59:42,920 --> 00:59:45,640
bet katru reizi, kad jūs nāksies apvienot.

1001
00:59:45,640 --> 00:59:48,270
Un mēs teicām agrāk, ka apvienošanās n tases aizņem n pasākumus

1002
00:59:48,270 --> 00:59:52,060
jo jums ir raut ārā kausu, raut ārā kausu, un jums ir pieskarties katru kauss vienreiz,

1003
00:59:52,060 --> 00:59:53,510
tāpat kā Rob izdarīja.

1004
00:59:53,510 --> 00:59:59,430
Tātad, ja mēs darām kaut žurnālu n reizes, un mēs darām n lietas, par katru no šiem atkārtojumiem,

1005
00:59:59,430 --> 01:00:03,090
Katrs no šiem halvings, mums ir n reizes log n.

1006
01:00:03,090 --> 01:00:07,220
Tātad, ja mēs plug 16 Šajā piemērā, 16 reizes log 16 -

1007
01:00:07,220 --> 01:00:10,600
nav jāuztraucas par to, kāpēc tas ir gadījums, lai tagad, jo man nav sagatavots bāzi -

1008
01:00:10,600 --> 01:00:16,100
bet žurnāls 16 2 bāzes ir 4, 16 4 reizes ir 64.

1009
01:00:16,100 --> 01:00:22,350
Bet tieši pretēji, ja mēs būtu izmantoti burbuļu šķirot vai selekcijas kārtošanas vai ievietošanas šķirot ar 16 numuriem,

1010
01:00:22,350 --> 01:00:26,420
kāda būtu darbības laiks ir bijis, ja n ir 16?

1011
01:00:26,420 --> 01:00:33,310
Tas būtu 16 brusas, kas ir 256, kas pat tad, ja jums nav gluži sekoja visu math,

1012
01:00:33,310 --> 01:00:38,390
256 ir lielāks nekā 64. Tas ir patiešām maģisks takeaway šeit.

1013
01:00:38,390 --> 01:00:41,990
Un saprast, ka darbs caur šo mazākās piemērus, kā jūs uz PSET

1014
01:00:41,990 --> 01:00:44,260
padara to visu daudz vairāk intuitīvi.

1015
01:00:44,260 --> 01:00:49,070
Bet ko tas īsti nozīmē ziņā noskaņu Šis algoritms ir šāds:

1016
01:00:49,070 --> 01:00:54,520
Ja mēs faktiski apskatīt sapludināšanas kārtot šeit - ļaujiet man vilkt to uz augšu šajā logā šeit -

1017
01:00:54,520 --> 01:00:58,560
Tas ir nedaudz atšķirīgs piemērs, kurā mēs visi esam 3 no šiem algoritmiem -

1018
01:00:58,560 --> 01:01:01,440
burbulis, atlase, un apvienot - tikai blakus.

1019
01:01:01,440 --> 01:01:03,740
>> Viņi visi esam sākuši ar izlases bāri, un tas ir labi.

1020
01:01:03,740 --> 01:01:06,240
Neviens nav būtiska priekšrocība pār otru.

1021
01:01:06,240 --> 01:01:09,500
Es esmu gatavojas uz brīdi uz katra no šīm animācijas - Start, Start, Start -

1022
01:01:09,500 --> 01:01:13,270
tik ātri, kā es varu tā, ka, rupji, viņi visi sāk tajā pašā laikā,

1023
01:01:13,270 --> 01:01:17,450
un pieņemsim uzskata, ka burbulis kārtot s sliktāk lieta darbības laiks ir tas, ko? >> [Students] N kvadrātā.

1024
01:01:17,450 --> 01:01:21,560
N brusas. Atlases kārtot s sliktākajā gadījumā darba laika ir? N brusas.

1025
01:01:21,560 --> 01:01:25,150
Un sapludināšanas kārtošanas ir acīmredzami - pat ja Jums nav gluži ievērot visus math tagad,

1026
01:01:25,150 --> 01:01:30,610
tas būs kļuvis daudz vairāk intuitīvi laika gaitā - ir, mums apgalvo, n reizes log n.

1027
01:01:30,610 --> 01:01:35,210
Un tāpēc žurnālu n ir stingri mazāks nekā n reizi mums ir lielas numurus,

1028
01:01:35,210 --> 01:01:40,230
n reizes žurnāls n ir mazāks nekā n reizes n vai n rūtiņām.

1029
01:01:40,230 --> 01:01:44,410
Tātad, ko tas jūtas, lai faktiski būtu labāks algoritms ziņā darba laika,

1030
01:01:44,410 --> 01:01:50,380
n reizes log n atšķirībā n kvadrātā? Šeit mēs iet. Klikšķis, klikšķis, klikšķis.

1031
01:01:55,690 --> 01:01:58,650
>> Tas, ko tas nozīmē, lai izmantotu kaut ko līdzīgu sapludināšanas kārtošanas.

1032
01:01:58,650 --> 01:02:01,680
Mums ir brīdis. Paskatīsimies, kas notiek šeit.

1033
01:02:09,440 --> 01:02:12,440
[Chuckles] Kuru nauda ir burbulis šķirot?

1034
01:02:14,960 --> 01:02:16,730
Tas drīzāk ir atkarīgs no ieejas dažreiz.

1035
01:02:16,730 --> 01:02:18,120
Pieņemsim redzēt.

1036
01:02:18,120 --> 01:02:23,320
Come on. Tā uzskata, piemēram, viņš tuvojas. >> [Students] Go, burbulis šķirot!

1037
01:02:23,320 --> 01:02:27,370
[Studenti murmuring]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Jā, jā.

1039
01:02:29,120 --> 01:02:34,520
[Studenti murmuring] Iet, iet, iet!

1040
01:02:37,210 --> 01:02:40,450
[Visi gavilēja] [aplausi]

1041
01:02:40,450 --> 01:02:46,240
Tāpēc tagad ar 1 pēdējo, galīgajā demo, ja tas nedaudz grūts, lai wrap savas domas ap math

1042
01:02:46,240 --> 01:02:49,280
vai sava veida vizualizācijas tur, jūs faktiski var dzirdēt ātrumiem

1043
01:02:49,280 --> 01:02:51,000
dažādu algoritmu atšķirīgi.

1044
01:02:51,000 --> 01:02:53,900
Tas ir animācija kāds, kas tiešām saista izklausās

1045
01:02:53,900 --> 01:02:56,980
ar pārnešana procesu un bāriem augstums.

1046
01:02:56,980 --> 01:03:00,440
Kā mēs redzēsim šeit, tur ir vēl dažas šķirošanas algoritmus, kas tur, ka ļaudīm ir doma.

1047
01:03:00,440 --> 01:03:03,660
Šis pirmais būs ievietošanas šķirot, un tas lidot caur

1048
01:03:03,660 --> 01:03:07,090
un jums skaņas izjūtu, kā šie dažādu algoritmu darbu.

1049
01:03:07,090 --> 01:03:09,080
Šeit ir ievietošanas šķirot.

1050
01:03:09,080 --> 01:03:18,410
[Elektroniskās skaņas]

1051
01:03:18,410 --> 01:03:20,730
[Malan] burbulis šķirot.

1052
01:03:20,730 --> 01:03:46,850
[Ātrāk elektroniskās skaņas]

1053
01:03:46,850 --> 01:03:48,950
[Malan] Atlase kārtošanas.

1054
01:03:48,950 --> 01:04:03,580
[Ātrāk elektroniskās skaņas]

1055
01:04:03,580 --> 01:04:05,770
[Malan] sapludināšana kārtošanas.

1056
01:04:05,770 --> 01:04:17,270
[Elektroniskās skaņas]

1057
01:04:17,270 --> 01:04:20,180
[Skaņas palēnina] [smiekli]

1058
01:04:20,180 --> 01:04:22,590
[Malan] Rūķis kārtošanas.

1059
01:04:22,590 --> 01:04:38,580
[Elektroniskās skaņas]

1060
01:04:39,740 --> 01:04:46,150
>> Tas ir CS50. Mēs redzēt jūs nākamajā nedēļā. [Aplausi un uzmundrinoša]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]