1
00:00:00,000 --> 00:00:02,280
[Powered by Google Translate] [Wythnos 3, Parhad]

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

3
00:00:04,110 --> 00:00:07,130
>> [Mae hyn yn CS50. - CS50.TV]

4
00:00:07,130 --> 00:00:11,010
>> Mae pob hawl. Croeso yn ôl. Mae hyn yn CS50, a dyma'r diwedd wythnos 3.

5
00:00:11,010 --> 00:00:14,680
>> Felly, ar gyfer rhai sy'n anghyfarwydd, y llynedd lansiodd Harvard hyn a elwir y Labordy Arloesi,

6
00:00:14,680 --> 00:00:18,530
neu i-lab, sydd yn adeilad gwych ar draws yr afon ar HBS gampws

7
00:00:18,530 --> 00:00:22,640
sy'n agored i fyfyrwyr y coleg, myfyrwyr GSAS, myfyrwyr o bob campws ar draws,

8
00:00:22,640 --> 00:00:27,000
gan gynnwys gyfadran, ac mae'n lle i ddod at ei gilydd i weithio ar bethau arloesol,

9
00:00:27,000 --> 00:00:29,180
pethau arbennig entrepreneuraidd

10
00:00:29,180 --> 00:00:33,410
os ydych chi a 0 neu fwy o ffrindiau yn meddwl am wneud rhywbeth entrepreneuraidd

11
00:00:33,410 --> 00:00:37,080
naill ai yn ystod y dosbarth hwn, ar ôl y dosbarth, neu'r tu hwnt.

12
00:00:37,080 --> 00:00:41,540
>> Felly un o'r pethau y maent yn ei wneud dros J tymor yn y tripiau hyn,

13
00:00:41,540 --> 00:00:44,510
un ohonynt yw i New York, ac un ohonynt yw i Silicon Valley.

14
00:00:44,510 --> 00:00:47,530
Gofod yn gyfyngedig iawn, ond ei fod yn gyfle i ochr yn ochr â MBA

15
00:00:47,530 --> 00:00:52,200
a myfyrwyr graddedig ar draws y campws ac mewn gwirionedd yn treulio amser yn y meysydd perthnasol

16
00:00:52,200 --> 00:00:55,500
sgwrsio i fyny startups, sgwrsio i fyny entrepreneuriaid ac yn y blaen.

17
00:00:55,500 --> 00:00:57,870
Felly os oes gennych ddiddordeb, edrychwch ar y URL yma.

18
00:00:57,870 --> 00:01:01,220
Mae hefyd ar gael ar y sleidiau ar-lein.

19
00:01:01,220 --> 00:01:04,610
>> Oni allem tôn i lawr y sain tŷ dim ond ychydig bach?

20
00:01:04,610 --> 00:01:08,640
Os hoffech chi ymuno â ni am ginio dydd Gwener yma, 1:15 pm Tân ac Iâ, os gwelwch yn dda ben yno.

21
00:01:08,640 --> 00:01:11,390
Ymddiheuriadau os yw'r ffurflen wedi ei llenwi eisoes gan i chi gyrraedd yno.

22
00:01:11,390 --> 00:01:13,750
Ond byddwn yn parhau â'r traddodiad ymlaen.

23
00:01:13,750 --> 00:01:17,350
>> Heddiw, rydym yn parhau â'r drafodaeth ar lefel uwch o broblemau amrywiol y gallwn eu datrys,

24
00:01:17,350 --> 00:01:21,330
canolbwyntio llawer llai, heddiw o leiaf, ar cod a llawer mwy ar syniadau.

25
00:01:21,330 --> 00:01:24,720
Felly meddyliwch yn ôl i'r wythnos 0 pan fyddwn yn rhwygodd llyfr ffôn yn ei hanner,

26
00:01:24,720 --> 00:01:28,260
amcan a oedd i wneud rhywbeth, rhaid cyfaddef, ychydig yn ddramatig

27
00:01:28,260 --> 00:01:32,360
ond i anfon y pwynt nad yw chwilio oes raid iddo fod, o reidrwydd,

28
00:01:32,360 --> 00:01:35,100
mor amlwg ar yr olwg gyntaf fel y byddech yn ei feddwl.

29
00:01:35,100 --> 00:01:40,200
Ac efallai na fydd datrys problemau yn gyffredinol o reidrwydd bob amser y gorau -

30
00:01:40,200 --> 00:01:44,130
Efallai na fydd yr ateb mwyaf amlwg o reidrwydd fod y gorau.

31
00:01:44,130 --> 00:01:47,300
Felly, rydym yn cael y llyfr ffôn a dweud y gwir, mae pob un ohonom yn yr ystafell hon wedi cael y greddfau,

32
00:01:47,300 --> 00:01:51,470
fwyaf tebygol, i ddechrau yn y canol wrth chwilio am Mike Smith ac yna ewch i'r chwith neu i'r dde

33
00:01:51,470 --> 00:01:54,280
yn seiliedig ar beth bynnag llythyren o'r wyddor rydym yn digwydd yn y pen draw ar.

34
00:01:54,280 --> 00:01:57,560
>> Ond y syniad syml bod ein pobl wedi cymryd yn ganiataol am gyfnod mor hir

35
00:01:57,560 --> 00:02:00,670
Dylai wir yn dechrau dod i'r amlwg yn eich meddwl

36
00:02:00,670 --> 00:02:03,900
oherwydd fel y problemau yn cael llawer mwy cymhleth nag y llyfr ffôn,

37
00:02:03,900 --> 00:02:07,420
rhai un peth syml, mewnwelediad gwych yn yr hyn yn mynd i ganiatáu i ni

38
00:02:07,420 --> 00:02:10,259
i ddatrys problemau yn llawer mwy cymhleth ac yn fwy diddorol,

39
00:02:10,259 --> 00:02:12,930
yn eu plith rai o'r pethau yr ydym yn eu cymryd yn ganiataol y dyddiau hyn yn barod.

40
00:02:12,930 --> 00:02:15,720
Mae biliynau o dudalennau gwe allan yna, ac eto Google a Bing ac yn y blaen

41
00:02:15,720 --> 00:02:17,660
yn gallu dod o hyd i bethau i ni fel 'na.

42
00:02:17,660 --> 00:02:22,300
Nid yw hynny'n digwydd drwy ddefnyddio chwiliad llinol, chwilio drwy'r holl dudalennau gwe posibl.

43
00:02:22,300 --> 00:02:25,290
Facebook yn gallu dweud wrthych pwy eich holl ffrindiau yn neu ffrindiau o ffrindiau,

44
00:02:25,290 --> 00:02:28,250
ac y gellir hefyd ei wneud yn ôl pob golwg mewn amrantiad dyddiau hyn

45
00:02:28,250 --> 00:02:30,820
er bod ganddynt miliynau o ddefnyddwyr.

46
00:02:30,820 --> 00:02:34,250
>> Ac felly sut y byddwn mewn gwirionedd yn datrys problemau ar y raddfa honno yn y pen draw lleihau

47
00:02:34,250 --> 00:02:37,830
at syniadau rydym yn edrych arnynt yn wythnos 0 ac ychydig mwy o bobl heddiw.

48
00:02:37,830 --> 00:02:42,320
Ni fyddwn yn ail-weithredu y algorithm, ond rydym yn cofio hefyd a wneuthum yn wythnos 0 ymarfer hwn

49
00:02:42,320 --> 00:02:44,780
lle'r oeddem wedi bawb sefyll i fyny, yn cymryd ar y rhif 1,

50
00:02:44,780 --> 00:02:48,720
ac yna cawsom bawb hunan-gyfrif drwy baru i ffwrdd, gan ychwanegu eich rhifau gyda'i gilydd,

51
00:02:48,720 --> 00:02:51,930
yna hanner y criw yn eistedd i lawr ar bob iteriad.

52
00:02:51,930 --> 00:02:56,750
Felly, rydym yn mynd o 500 o fyfyrwyr i 250-125 ac yn y blaen.

53
00:02:56,750 --> 00:03:00,080
Ond fel y dywedasom ar ddydd Llun, y syniad grymus yn awr

54
00:03:00,080 --> 00:03:02,460
oedd os ydym yn dyblu maint y broblem

55
00:03:02,460 --> 00:03:06,480
a'r holl blant o'r Adran Cyfiawnder neu CE 10 daeth yn ôl i mewn i'r ystafell ac yn ymuno â ni,

56
00:03:06,480 --> 00:03:09,510
yn dda, gallem yn ôl pob tebyg yn cyfrif y grŵp cyfan agregau

57
00:03:09,510 --> 00:03:13,380
gyda dim ond 1 yn fwy fersiwn mawr o'r ddolen oherwydd y byddent yn unig efallai yn dyblu maint

58
00:03:13,380 --> 00:03:15,630
neu mewn CE 10 oed achos ychydig yn fwy na dwbl y maint.

59
00:03:15,630 --> 00:03:18,440
Ac felly byddai'n rhaid i ni dreulio ychydig mwy o amser,

60
00:03:18,440 --> 00:03:22,000
ond ni fyddem yn gorfod treulio 400 neu 700 mwy o gamau.

61
00:03:22,000 --> 00:03:26,550
>> Dim ond i baentio darlun hwn mewn ffordd sy'n ychydig yn llai haniaethol, gadewch i ni wedi i bawb sefyll i fyny.

62
00:03:26,550 --> 00:03:31,100
Ond os na fyddai rhai ohonoch sy'n dewis i eistedd yn y gerddorfa heddiw yn meddwl sefyll i fyny,

63
00:03:31,100 --> 00:03:34,580
gadewch i ni weld os allwn chyfrif i maes eich plith a oedd y person talaf yn

64
00:03:34,580 --> 00:03:36,730
drwy wneud yr un math o algorithm cymharol.

65
00:03:36,730 --> 00:03:41,830
Felly, os ydych yn eistedd yn y gerddorfa, fy ymddiheuriadau, ond cam 1, safant i fyny;

66
00:03:41,830 --> 00:03:44,650
cam 2, pâr i ffwrdd ag unrhyw un gerllaw chi,

67
00:03:44,650 --> 00:03:49,360
chyfrif i maes sydd yn dalach, ac eistedd i lawr os ydych yn fyrrach.

68
00:03:49,360 --> 00:03:51,360
Yna ailadrodd.

69
00:03:51,360 --> 00:03:56,280
[Fyfyrwyr grwgnach]

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

71
00:04:15,320 --> 00:04:19,010
Iawn. Mae un yn cael ei adael yn sefyll. Beth yw eich enw? >> Andrew.

72
00:04:19,010 --> 00:04:21,959
>> Andrew, chi yw'r person talaf yn yr adran gerddorfa heddiw.

73
00:04:21,959 --> 00:04:28,100
>> Llongyfarchiadau. [Gymeradwyaeth a bloeddio] Iawn. Cael sedd. Felly, rydym yn dod o hyd Andrew.

74
00:04:28,100 --> 00:04:30,870
Ond faint o amser wedi cymryd i mi, er enghraifft, i ddod o hyd i Andrew

75
00:04:30,870 --> 00:04:33,740
yn yr adran hon gerddorfa o 50 + neu fwy o bobl?

76
00:04:33,740 --> 00:04:36,900
Gallwn i fod wedi cymryd yn ddull syml a dechrau yma.

77
00:04:36,900 --> 00:04:39,270
Ac yr wyf wedi 2 o bobl yn sefyll i fyny ac roeddwn i yn eu cymharu,

78
00:04:39,270 --> 00:04:42,120
ac yna yr wyf yn dweud i bwy bynnag ychydig yn fyrrach, "Iawn, chi eistedd i lawr,"

79
00:04:42,120 --> 00:04:44,380
ac yr wyf i'n mynd i gofio pwy oedd y person talach oedd.

80
00:04:44,380 --> 00:04:49,030
Yna mi ailadrodd, ailadrodd, ailadrodd, ac yr wyf yn hongian ar y person talaf

81
00:04:49,030 --> 00:04:51,920
nes i mi ffeindio rhywun ychydig yn dalach na nhw, ac ar y pwynt

82
00:04:51,920 --> 00:04:54,950
y person sydd ychydig yn fyrrach rhaid i yna yn eistedd i lawr.

83
00:04:54,950 --> 00:04:57,690
Ond yn y algorithm yn yr adran hon gerddorfa, os oes n ohonoch,

84
00:04:57,690 --> 00:05:00,480
faint o gamau yn y algorithm yn mynd i gymryd? >> [Myfyrwyr] N.

85
00:05:00,480 --> 00:05:03,580
>> Mae'n mynd i gymryd n, iawn, oherwydd yn yr achos gwaethaf, fel petai,

86
00:05:03,580 --> 00:05:09,090
y person talaf yn y person olaf un fy mod yn cael dim ond drwy lwc ddrwg ar hap.

87
00:05:09,090 --> 00:05:14,260
Felly, yn yr achos gwaethaf, yr amser yn rhedeg y algorithm yn llinol, mae'n n,

88
00:05:14,260 --> 00:05:18,070
lle mae n yn y cyfanswm o bobl yn y gofod, maint y broblem.

89
00:05:18,070 --> 00:05:19,600
Beth am y algorithm?

90
00:05:19,600 --> 00:05:22,080
Mae'r ffaith eich bod i gyd yn sefyll i fyny ac yna unwaith eto hanner chi eistedd i lawr,

91
00:05:22,080 --> 00:05:23,950
hanner ohonoch eistedd i lawr, hanner chi eistedd i lawr.

92
00:05:23,950 --> 00:05:26,070
Sawl cam sydd wedi cymryd os oes n ohonoch chi yma?

93
00:05:26,070 --> 00:05:30,200
[Myfyrwyr] N log n. >> Byddai hynny'n waeth. Mewngofnodi n.

94
00:05:30,200 --> 00:05:32,930
>> Felly logio n, hyd yn oed os nad ydych yn cofio'r beth yw logarithm yw,

95
00:05:32,930 --> 00:05:38,410
ar hyn o bryd, dim ond gwerthfawrogi ei fod yn ymwneud rywsut i hyn haneru a haneru a haneru.

96
00:05:38,410 --> 00:05:41,000
Nid oes rhaid iddo fod yn ffactor o 2. Gallai fod yn ffactor o 3.

97
00:05:41,000 --> 00:05:46,560
Ond mae'n ydyn nhw ailadrodd yr un math o ffactor fel bod maint y broblem yn cychwyn yma:

98
00:05:46,560 --> 00:05:49,620
ond yna yn syth yn mynd yma, yna yma, yna yma, yna yma.

99
00:05:49,620 --> 00:05:53,580
Nid ydych yn cymryd brathiadau bach allan o'r broblem, ydych wirioneddol yn torri i ffwrdd yn ei

100
00:05:53,580 --> 00:05:56,160
gyda mawr dyrnod bob tro.

101
00:05:56,160 --> 00:06:00,810
Felly, roedd gennym 50 o bobl, yna 25, yna 12 ½ neu 13 o bobl yn sefyll,

102
00:06:00,810 --> 00:06:05,370
yna 6 ½ ac yn y blaen hyd nes sefyll yn olaf yn unig Andrew oedd ar ôl.

103
00:06:05,370 --> 00:06:08,710
Felly, rydym yn mynd i alw y log o n, a gallwch ddychmygu hyn fel a ganlyn.

104
00:06:08,710 --> 00:06:12,570
Dwyn i gof y llun yma lle mae algorithm llinol yn debyg i'r llinell goch yno,

105
00:06:12,570 --> 00:06:17,520
y llinell felen yn y cyfrif gan 2s algorithm a ddefnyddiwyd gennym ar gyfer myfyrwyr cyfrif

106
00:06:17,520 --> 00:06:22,300
yn y gorffennol, ond erbyn heddiw mae'r greal sanctaidd yn mynd i aros yn y llinell werdd

107
00:06:22,300 --> 00:06:25,470
lle os ydym yn dyblu nifer y bobl yn yr adran cerddorfa neu newydd ei ddweud,

108
00:06:25,470 --> 00:06:29,170
uffern, gadewch i ni gael pawb yn yr ystafell gyfan na sefyll i fyny, mor bwysig â hynny

109
00:06:29,170 --> 00:06:31,560
oherwydd ein bod yn fras yn dyblu faint o bobl i lawr yma,

110
00:06:31,560 --> 00:06:33,500
1 iteriad heb fod yn fwy, yn broblem.

111
00:06:33,500 --> 00:06:36,200
>> Rydym wedi dod o hyd Andrew neu bwy bynnag fydd yn digwydd i fod yn dalach nag Andrew

112
00:06:36,200 --> 00:06:38,770
yn y mesanîn neu yn y balconi.

113
00:06:38,770 --> 00:06:42,140
Felly, mae hyn syniad syml ein bod yn cymryd cymaint yn ganiataol mewn llyfr ffôn,

114
00:06:42,140 --> 00:06:46,170
sylweddoli bod llawer o leoedd cymaint o wahanol y gallwn wneud cais amdano.

115
00:06:46,170 --> 00:06:50,810
Dim ond i slap rhywfaint o jargon - mewn gwirionedd, yn hytrach na jargon gyntaf,

116
00:06:50,810 --> 00:06:52,750
gadewch i mi fynd at y darlun hwn yma.

117
00:06:52,750 --> 00:06:56,970
Ar hyn o bryd rydym yn siarad am n a n / 2, ac yna logio n,

118
00:06:56,970 --> 00:07:00,500
ond gallwn yn sicr yn dod o hyd i, fel y gwnawn yn ystod y semester,

119
00:07:00,500 --> 00:07:05,130
fath arall o fformiwlâu mathemategol i ddisgrifio y syniad cyffredinol o redeg amser.

120
00:07:05,130 --> 00:07:07,580
Mae'r rhain yn allan o'u cyd-destun ar hyn o bryd oherwydd y byddwn yn gweld cyn bo hir

121
00:07:07,580 --> 00:07:09,900
algorithmau bod y rhain eu cynrychioli mewn gwirionedd.

122
00:07:09,900 --> 00:07:17,990
>> Ond sylwi yma y llinell llinol n, y llinell syth, mewn gwirionedd yn isel iawn pwyntio ar hyn o bryd.

123
00:07:17,990 --> 00:07:22,950
Dyna fath o rhith optegol yn yr ydym yn unig yn newid yr hyn yr echelin x yn cynrychioli

124
00:07:22,950 --> 00:07:26,130
a'r echelin y, a gallwn wneud pwynt llinell syth mewn unrhyw gyfeiriad yr ydym ei eisiau.

125
00:07:26,130 --> 00:07:30,350
Ond y rheswm pam y mae mor ymddangos yn fflat erbyn hyn

126
00:07:30,350 --> 00:07:35,690
oherwydd ein bod angen i wneud lle ar y graff ar gyfer amseroedd rhedeg yn arafach o lawer.

127
00:07:35,690 --> 00:07:39,030
Am y tro, yn gwybod bod yna rai algorithmau eithaf gwael mewn bywyd,

128
00:07:39,030 --> 00:07:43,790
Nid yw rhai ohonynt yn cymryd camau n neu, yn well fyth, ewch camau n ond yn fwy.

129
00:07:43,790 --> 00:07:48,820
Felly, uwchben y llinell n yma yn yr hysbysiad gwaelod mae n amser log o n,

130
00:07:48,820 --> 00:07:51,410
a gawn ni weld beth mae hyn yn golygu cyn bo hir.

131
00:07:51,410 --> 00:07:56,010
Yn fwy na hynny yn n sgwâr, ac nid ydym wedi gweld unrhyw algorithmau n sgwâr eto ond rydym am i.

132
00:07:56,010 --> 00:07:57,660
A bod yn edrych yn ddrwg iawn.

133
00:07:57,660 --> 00:08:01,610
Mae 2 i'r n, rhywbeth esbonyddol, sy'n teimlo hyd yn oed yn waeth.

134
00:08:01,610 --> 00:08:05,760
Ac eto, yn rhyfedd ddigon, yna mae n dorri'n giwbiau, ac os ydych yn fath o feddwl ymlaen,

135
00:08:05,760 --> 00:08:10,000
os ydych yn fath o wneud y math, 2 i'r n mewn gwirionedd yn dod yn llawer sythach,

136
00:08:10,000 --> 00:08:15,930
llawer yn uwch i fyny na n torri'n giwbiau os ydych yn edrych ar yr echelinau yn ddigon pell allan.

137
00:08:15,930 --> 00:08:19,890
Felly sylwi ar hyn o bryd yr echelau yn fympwyol 2-10 ar yr echelin x.

138
00:08:19,890 --> 00:08:21,770
>> A beth mae hynny'n ei olygu?

139
00:08:21,770 --> 00:08:23,890
Mae hynny'n golygu 2 o bobl at 10 o bobl yn yr ystafell.

140
00:08:23,890 --> 00:08:27,200
Dyna pob dull x: maint y broblem, beth bynnag fo'r cyd-destun yn.

141
00:08:27,200 --> 00:08:30,420
A echelin fertigol ar hyn o bryd yn nifer o eiliadau neu nifer o gamau -

142
00:08:30,420 --> 00:08:31,840
rhywfaint o uned o amser.

143
00:08:31,840 --> 00:08:34,740
Ond sylwi ei bod yn 0-60 a 0 i 10.

144
00:08:34,740 --> 00:08:38,549
Ond os ydym yn fath o chwyddo allan, fel y gellid yn yr Excel neu ryw feddalwedd siartio,

145
00:08:38,549 --> 00:08:43,370
ac rydym yn mynd i fyny i 200,000, sylwi bod rhywbeth fel 2 i n

146
00:08:43,370 --> 00:08:47,520
yn mynd yn llwyr gorlethu amseroedd rhedeg n sgwâr,

147
00:08:47,520 --> 00:08:50,960
wedi'i dorri'n giwbiau n, n log n - popeth yr ydym wedi siarad am hyd yn hyn.

148
00:08:50,960 --> 00:08:54,190
Ac eto dal yw pan fyddwch yn dechrau siarad am bethau fel Facebook

149
00:08:54,190 --> 00:08:57,150
lle'r ydych wedi llawer, llawer, llawer o bobl yn gysylltiedig â'i gilydd i gyd,

150
00:08:57,150 --> 00:09:00,650
gennych n pobl, y gallai pob un ohonynt gymaint â ffrindiau n

151
00:09:00,650 --> 00:09:02,860
os yw pawb yn fath o buddy-buddy yn y byd,

152
00:09:02,860 --> 00:09:08,100
wel, dyna amseroedd n n barod, felly mae hynny'n n cyfeillgarwch posibl sgwâr,

153
00:09:08,100 --> 00:09:10,950
o leiaf mewn 1 cyfeiriad, n cyfeillgarwch posibl sgwâr.

154
00:09:10,950 --> 00:09:15,330
Felly, sydd eisoes yn awgrymu bod chwilio Facebook yn graff cymdeithasol, fel petai,

155
00:09:15,330 --> 00:09:18,090
Gellir dechrau cael ei fynegi yn y mathau hyn o fformiwlâu.

156
00:09:18,090 --> 00:09:19,820
>> Byddwn yn dod yn ôl a gwneud hyn yn llawer mwy cadarn,

157
00:09:19,820 --> 00:09:23,280
ond ar hyn o bryd, y nod ar gyfer yr wythnosau nesaf mae llawer o

158
00:09:23,280 --> 00:09:27,170
yn mynd i fod yn sicr i beidio â mynd am algorithmau gweithredu neu god

159
00:09:27,170 --> 00:09:29,870
y pen draw gymryd amser gymaint â rhywbeth fel hyn.

160
00:09:29,870 --> 00:09:33,110
Ond y peth diddorol am wyddoniaeth gyfrifiadurol os ydych yn parhau ymlaen yn y maes hwn

161
00:09:33,110 --> 00:09:38,320
gymryd dosbarthiadau fel CS121, CS124, y ddau ohonynt yn gyrsiau theori,

162
00:09:38,320 --> 00:09:41,300
yw bod yna mewn gwirionedd rhai problemau sy'n bodoli yn y byd hwn

163
00:09:41,300 --> 00:09:45,710
yn sylfaenol, cyn belled ag y gwyddom, ni ellir eu datrys yn gyflymach

164
00:09:45,710 --> 00:09:48,880
nag y gwaethaf o'r graffiau hyn mewn gwirionedd yn awgrymu.

165
00:09:48,880 --> 00:09:53,660
Felly, mae llawer o broblemau agored yn y byd i wneud llawer yn well na bodau dynol yn cael hyd yn hyn.

166
00:09:53,660 --> 00:09:56,130
>> Felly, gadewch i ni ddechrau, yna â'r enghraifft hon.

167
00:09:56,130 --> 00:09:59,650
Gwelsom Sean cael trafferth gyda hyn camera, i gyd yn rhy lletchwith ar fideo.

168
00:09:59,650 --> 00:10:05,270
Ond y gwir amdani oedd pan Sean y dasg o ddod o hyd ar fwrdd fel hyn y rhif 7,

169
00:10:05,270 --> 00:10:10,300
yn cofio fy mod wedi dweud hynny, "Mae yna rhywle y tu ôl i'r darnau o bapur neu ddrysau gwyn

170
00:10:10,300 --> 00:10:12,570
"Y rhif 7. Sean, dod o hyd i ni."

171
00:10:12,570 --> 00:10:14,200
Ac yn rhyfeddol o anodd i wylio

172
00:10:14,200 --> 00:10:15,790
oherwydd ei fod yn wir yn cael trafferth â'r broblem hon.

173
00:10:15,790 --> 00:10:19,720
Ond y realiti oedd Sean gwnaeth yn ogystal ag y gallai unrhyw un yn yr ystafell yn cael ei wneud.

174
00:10:19,720 --> 00:10:21,890
Cymerodd ychydig yn hirach na pherson nodweddiadol a allai fod wedi

175
00:10:21,890 --> 00:10:24,760
ond cymryd yn ganiataol bod rhywfaint o tric i'r broblem hon,

176
00:10:24,760 --> 00:10:26,590
roedd cymryd yn ganiataol ei fod yn colli rhywbeth.

177
00:10:26,590 --> 00:10:29,320
Ac nid oedd yn helpu cannoedd o lygaid yn dwyn i lawr arno.

178
00:10:29,320 --> 00:10:34,250
>> Ond y gwirionedd oedd petai'r mewnbwn i'r broblem yw criw o rifau ar hap

179
00:10:34,250 --> 00:10:37,120
ac rydych yn cael eu gofyn i ddod o hyd i rhif 1 o'r fath,

180
00:10:37,120 --> 00:10:39,770
y gorau y gallwch ei wneud yw chwiliad llinol.

181
00:10:39,770 --> 00:10:44,060
Dechreuwch ar y chwith, yn symud i'r dde, neu ddechrau ar y dde, yn symud i'r chwith.

182
00:10:44,060 --> 00:10:48,300
Retroactively, efallai y byddwn yn meddwl, "Sean, pam na wnaethoch chi yn unig cychwyn o'r pen arall?"

183
00:10:48,300 --> 00:10:52,120
Wel, gallai 7 ohonynt wedi un mor hawdd bod yma ar hap,

184
00:10:52,120 --> 00:10:54,980
ond yr wyf yn fwriadol roi yno oherwydd fy mod cyfrifedig nad oedd yn mynd i ddechrau ar y diwedd.

185
00:10:54,980 --> 00:10:59,320
Felly, yr wyf yn fath o drin y sefyllfa, ond gallai drwy hap a damwain ar hap 7 wedi bod yn unrhyw le.

186
00:10:59,320 --> 00:11:02,380
Efallai felly mae dechrau o'r pen cywir wedi bod yn well, yna,

187
00:11:02,380 --> 00:11:04,320
ond beth os yw'r flwyddyn nesaf byddaf yn symud 7 rhywle arall?

188
00:11:04,320 --> 00:11:06,830
Nid yw hynny'n ateb sylfaenol newydd i'r broblem -

189
00:11:06,830 --> 00:11:10,520
gan ddechrau o 1 ben neu'r llall - pan fyddwch yn cael unrhyw ragdybiaethau eraill.

190
00:11:10,520 --> 00:11:13,620
Felly, Sean dechrau edrych drwy'r rhifau a dywedodd, "5. Dyw hynny ddim yn fan hyn."

191
00:11:13,620 --> 00:11:17,280
Yna aeth yma a gweld 19, yna mae'n seibio am tua 20 eiliad,

192
00:11:17,280 --> 00:11:22,330
yna agorodd hyn ar gyfer 13, ac yna daeth yn amlwg

193
00:11:22,330 --> 00:11:24,270
nad yw'n ymddangos i fod yn batrwm yma.

194
00:11:24,270 --> 00:11:28,090
Nid oedd 1, 2, 3, 4 neu debyg. Roedd bylchau yn y niferoedd, nad oedd yn helpu.

195
00:11:28,090 --> 00:11:32,320
Ac hefyd, y ffaith fy mod defnyddio darnau hyn o bapur rhad i dalu am hyd y niferoedd

196
00:11:32,320 --> 00:11:35,270
mewn gwirionedd yn fwriadol, oherwydd os wyf yn dileu yr holl ddarnau o bapur,

197
00:11:35,270 --> 00:11:38,760
rhan fwyaf ohonom, Sean cynnwys, mae'n debyg y byddai wedi bwrw golwg math o macroscopically

198
00:11:38,760 --> 00:11:43,410
dweud ar y bwrdd du, ac, "O, 7 yn amlwg iawn yno." Rydym yn gwneud hynny ar unwaith.

199
00:11:43,410 --> 00:11:46,460
>> A allai fod yn y ffordd y mae'r ymennydd dynol yn gweithio i ryw raddau,

200
00:11:46,460 --> 00:11:50,730
ond mewn gwirionedd, ei llygaid neu feddwl, mae'n debyg, sgimio y niferoedd o'r dde i'r chwith,

201
00:11:50,730 --> 00:11:55,190
o'r chwith i'r dde, canol y tu allan i - rhywbeth oedd yn digwydd ffisiolegol

202
00:11:55,190 --> 00:11:57,640
fel ei fod yn teimlo fel ei fod yn digwydd ar unwaith,

203
00:11:57,640 --> 00:12:01,360
ond groes hyd yn oed yn fewnol roedd rhyw fath o fethodoleg i ddod o hyd i 7.

204
00:12:01,360 --> 00:12:05,160
Ac yn wir, yn awr ein bod yn sôn am araeau a strwythurau data

205
00:12:05,160 --> 00:12:08,780
ac y tu mewn cof cyfrifiadur, gall yr unig beth rydym yn bodau dynol yn ei wneud

206
00:12:08,780 --> 00:12:13,070
yw edrych ar leoliadau cof unigol 1 ar y tro.

207
00:12:13,070 --> 00:12:16,600
>> Felly, gallai pob lleoliad arall yn ogystal yn cael eu cynnwys i fyny gyda rhywfaint o ddarn o bapur

208
00:12:16,600 --> 00:12:21,170
oherwydd ni allwn weld beth bynnag. Gallwn ond wneud 1 peth ar y tro.

209
00:12:21,170 --> 00:12:25,030
Felly, yn yr achos hwn, yn Sean achos, rydym yn mynd yma ac yna aethom yma

210
00:12:25,030 --> 00:12:31,040
ac yna aethom yma, yma, yma, yma, got glyfar erbyn diwedd

211
00:12:31,040 --> 00:12:34,450
a dim ond math o hepgor yr un yma yn fympwyol ac yn dod o hyd 7 yno.

212
00:12:34,450 --> 00:12:37,470
Nid yw'r un yn arbennig iawn. Roedd hon hefyd yn allan o drefn.

213
00:12:37,470 --> 00:12:39,530
Ond o'r diwedd dod o hyd 7.

214
00:12:39,530 --> 00:12:45,360
Ond yn awr mae'r parod mewn gwirionedd yw bod y gorau y gallwch ei wneud pan roddir unrhyw wybodaeth

215
00:12:45,360 --> 00:12:50,400
heblaw nifer didoli ar hap yn dechrau o'r chwith neu ddechrau o'r dde.

216
00:12:50,400 --> 00:12:54,950
Neu Heck, gallwch hap agor drysau, ond hyd yn oed wedyn beth mae'n ei olygu i fod ar hap?

217
00:12:54,950 --> 00:12:57,220
Wel, byddai'n rhaid i ni rywsut ffurfioli'r hyn mae'n ei olygu i ddechrau yma,

218
00:12:57,220 --> 00:13:01,150
wedyn yn mynd yma, yna ewch yma. Sean wnaeth wych, ac roedd yn hwyl i wylio.

219
00:13:01,150 --> 00:13:06,340
Beth os yn lle hynny rydym yn newid y broblem ychydig ac yn dod i fyny Sean eleni, os mynnwch?

220
00:13:06,340 --> 00:13:09,460
A fyddai unrhyw un fod yn gyfforddus yn dod i fyny ar y llwyfan ac yn datrys problem ychydig yn wahanol

221
00:13:09,460 --> 00:13:12,330
ac yn ymddangos o flaen y camera?

222
00:13:12,330 --> 00:13:15,720
>> Gadewch i ni fynd y tu hwnt i'r gerddorfa oherwydd eich bod guys wedi cymryd rhan yn eithaf heddiw yn barod.

223
00:13:15,720 --> 00:13:21,430
Beth am mewn pinc, yn yr het? Dewch i lawr. Beth yw eich enw? >> Alex. >> Alex. Iawn.

224
00:13:21,430 --> 00:13:24,580
Felly, bydd Alex yn Sean eleni a bydd yn ymddangos yn y blynyddoedd nesaf

225
00:13:24,580 --> 00:13:27,770
gwerth CS50 darlithoedd.

226
00:13:27,770 --> 00:13:30,340
Alex, neis i gwrdd â chi. >> Neis i gwrdd â chi hefyd.

227
00:13:30,340 --> 00:13:33,470
Yr her wrth law i chi yw eich bod yn ei chael ychydig yn haws

228
00:13:33,470 --> 00:13:38,950
yn yr Rwy'n dweud wrthych yr un rhifau yma, ond maent yn cael eu datrys erbyn hyn.

229
00:13:38,950 --> 00:13:41,800
Felly nawr eich nod yw dod o hyd i'r rhif 7.

230
00:13:41,800 --> 00:13:45,370
Ac mewn gwirionedd, dylem wneud gwir hyn - nid math you're o dwyllo, fel cyfrifiadur fyddai,

231
00:13:45,370 --> 00:13:47,990
drwy edrych ar yr hyn y niferoedd yn funud yn ôl.

232
00:13:47,990 --> 00:13:50,360
Gyda sialc hyn mewn gwirionedd yn mynd i helpu'r holl cymaint â hynny,

233
00:13:50,360 --> 00:13:52,810
ond gadewch i esgus nad ydych yn gwybod beth yr amrywiaeth gwreiddiol yn.

234
00:13:52,810 --> 00:13:56,600
Mae pob eich bod yn gwybod yn awr yw bod gennych amrywiaeth o rifau didoli

235
00:13:56,600 --> 00:14:00,360
allai fod wedi bylchau rhyngddynt, a bod eich nod yw dod o hyd i'r rhif 7.

236
00:14:00,360 --> 00:14:05,080
Sut fyddech chi, bod dynol rhesymol fod yn, mynd ati i ddod o hyd i'r rhif 7?

237
00:14:05,080 --> 00:14:07,770
>> Ewch o isel i uchel? >> Iawn. Ewch isel i uchel.

238
00:14:07,770 --> 00:14:10,990
A pheidiwch rhwygo i ffwrdd. Gadewch i 'jyst eu codi i fyny fel y gallwn eu hailddefnyddio.

239
00:14:10,990 --> 00:14:14,730
Iawn, felly 1. Arhoswch. Cyn i chi gadw i fynd, a oedd yn 1, yn amlwg yn anghywir.

240
00:14:14,730 --> 00:14:17,270
Felly beth sy'n mynd trwy dy feddwl nesaf? Beth yw eich cam nesaf?

241
00:14:17,270 --> 00:14:23,250
Yr un nesaf. >> Iawn. Yr un nesaf. Da. 3, felly yn anghywir. Beth yw eich cam nesaf?

242
00:14:23,250 --> 00:14:27,670
Cadwch ar fynd. >> Mae pob hawl. Cadwch ar fynd. 5.

243
00:14:27,670 --> 00:14:31,110
Felly, dal i fynd, a gadewch i mi llaw hwn i chi ar gyfer y dyfodol.

244
00:14:31,110 --> 00:14:35,720
7. >> Ardderchog. Da iawn. Wedi dod o hyd i'r rhif 7. [Cymeradwyaeth]

245
00:14:35,720 --> 00:14:39,720
Felly, a oedd yn dda, ond mae Sean hefyd dod o hyd i'r rhif 7.

246
00:14:39,720 --> 00:14:44,490
Ac yr wyf yn dadlau nad ydych wedi eu hecsbloetio mewn gwirionedd y darn ychwanegol o wybodaeth,

247
00:14:44,490 --> 00:14:47,780
sef bod y niferoedd yn cael eu datrys.

248
00:14:47,780 --> 00:14:51,520
Gall Felly, rydym yn gwneud yn well? Unrhyw awgrymiadau yma? Yeah, yn ôl.

249
00:14:51,520 --> 00:14:54,710
[Myfyrwyr] search deuaidd. >> Nid oes gennyf unrhyw syniad beth yw chwiliad deuaidd.

250
00:14:54,710 --> 00:14:58,030
>> [Myfyrwyr] Dechreuwch yn y canol. >> Dechreuwch yn y canol. Iawn. Felly, gadewch i ni weld os allwn ni gyrraedd yno.

251
00:14:58,030 --> 00:15:02,580
Felly os ydych yn hytrach na dweud wrth gychwyn o'r canol, yn mynd yn ei flaen ac yn agor y drws canol.

252
00:15:02,580 --> 00:15:04,580
Mae 8 ohonynt, felly rydych chi'n mynd i gael ato ar hap dewis yr un

253
00:15:04,580 --> 00:15:09,800
ychydig i'r chwith neu i'r dde. Iawn. 7! [Gymeradwyaeth] Iawn 'n glws.

254
00:15:09,800 --> 00:15:11,410
Iawn, ond lle'r oedd ydym yn mynd â hyn?

255
00:15:11,410 --> 00:15:14,990
Gadewch i ni Mae'n debyg dim ond er mwyn torri'r ddadl rydych wedi dechrau yma

256
00:15:14,990 --> 00:15:16,670
oherwydd y gallai un mor wedi digwydd yn ogystal.

257
00:15:16,670 --> 00:15:19,540
Rydym yn unig yn digwydd gwybod bod 7 oedd yno. Felly, mae hyn yn 13.

258
00:15:19,540 --> 00:15:21,980
Felly, os ydynt yn trefnu ac rydym newydd ddechrau yn y canol,

259
00:15:21,980 --> 00:15:24,600
beth fyddai'r cam nesaf gorau posibl wedi bod?

260
00:15:24,600 --> 00:15:27,740
Ewch i'r chwith. Ac felly dyma daw y ffôn enghraifft llyfr eto.

261
00:15:27,740 --> 00:15:30,130
Os yw 13 yma ac rydym yn gwybod y rhestr yn cael ei datrys,

262
00:15:30,130 --> 00:15:33,900
yna pob un o'r darnau o bapur yn anniddorol i ni nawr

263
00:15:33,900 --> 00:15:37,400
gan ein bod eisoes yn gwybod bod yn rhaid i 7 yn y chwith

264
00:15:37,400 --> 00:15:39,510
os bydd y niferoedd yn cael eu didoli ac rydym yn dod o hyd 13.

265
00:15:39,510 --> 00:15:42,500
>> Felly beth yw eich cam nesaf yma? >> Ewch i'r chwith. >> Iawn, yn dda.

266
00:15:42,500 --> 00:15:45,080
Felly, ewch i'r chwith, a - aros, hey, hey, hey. Dyna dwyllo.

267
00:15:47,140 --> 00:15:51,350
Felly rydych yn dod o hyd 7, ond beth oedd y algorithm rydym yn unig gwneud cais?

268
00:15:51,350 --> 00:15:56,450
Dechreuwch yn y canol. >> Da. Felly beth yw'r estyniad rhesymegol i'r un syniad?

269
00:15:56,450 --> 00:15:58,970
O, am ddim ond y rhain. >> Yn union. >> Felly, yr wyf yn dechrau yma. >> Da.

270
00:15:58,970 --> 00:16:02,020
Felly, nawr rydym yn mynd ychydig i'r chwith eto. Mae'n 3.

271
00:16:02,020 --> 00:16:05,310
Ond mae'r prydau parod diddorol yn awr yw pa un onid ydych yn rhaid i chi ofalu am?

272
00:16:05,310 --> 00:16:08,040
Mae'r rhain yn 2. Mae'r rhain yn >> 2. Felly, erbyn hyn gall yr un yma fynd i ffwrdd, gall hyn un fynd i ffwrdd.

273
00:16:08,040 --> 00:16:12,330
Nawr bod y broblem a oedd yn 8 wedyn oedd 4 maint yn awr yw maint 2.

274
00:16:12,330 --> 00:16:16,430
Rydym yn mynd yn eithaf agos. Unwaith eto, ewch i ganol y 2 elfen.

275
00:16:16,430 --> 00:16:20,430
>> Iawn. Felly, mae'n fath o anffodus bod yn awr rydym bob amser yn mynd adael oherwydd ein bod yn talgrynnu i lawr.

276
00:16:20,430 --> 00:16:25,150
Ond mae hynny'n iawn oherwydd erbyn hyn rydyn ni'n ei daflu i ffwrdd hyn a phopeth arall, gan ein gadael gyda dim ond 7.

277
00:16:25,150 --> 00:16:30,490
Gadewch i ni roi rownd o gymeradwyaeth. Gwelsom 7 eto. [Cymeradwyaeth] Iawn. Cadarn.

278
00:16:30,490 --> 00:16:32,220
Arhoswch am dim ond 1 mwy o ail.

279
00:16:32,220 --> 00:16:36,630
Er bod y math hwnnw o broses nesaf yn cymryd ychydig yn hwy nag yr oeddem yn teimlo y byddai,

280
00:16:36,630 --> 00:16:40,150
dweud y gwir, eich greddf cyntaf oedd y gorau, dde? Gwelsom 7 yn syth.

281
00:16:40,150 --> 00:16:46,740
Ond byddem wedi dod o hyd 7 yn gyflymach, ni waeth beth, yn yr enghraifft hon yn erbyn yr un yma

282
00:16:46,740 --> 00:16:50,100
oherwydd os bydd y niferoedd yn cael eu datrys i gyd, yn debyg iawn i'r tudalennau mewn llyfr ffôn,

283
00:16:50,100 --> 00:16:54,580
gallwch chi wir torri hanner y broblem allan eto ac eto ac eto.

284
00:16:54,580 --> 00:16:56,740
Ac nid yw mor hawdd gweld hyn gyda dim ond 8 rhif

285
00:16:56,740 --> 00:17:00,100
yn hytrach na llyfr ffôn 1,000 dudalen lle rydych yn gweld yn weledol,

286
00:17:00,100 --> 00:17:03,120
ond yn yr achos yma pan Sean yn chwilio am 7,

287
00:17:03,120 --> 00:17:06,020
faint o gamau yn yr achos gwaethaf wedi mynd ag ef? >> [Myfyrwyr] 7.

288
00:17:06,020 --> 00:17:11,670
7 yn yr achos gwaethaf. Wel, yn yr achos gwaethaf na 7 os oes sef 8 drysau yma.

289
00:17:11,670 --> 00:17:13,440
Byddai wedi mynd ag ef 8 Y camau.

290
00:17:13,440 --> 00:17:18,170
>> Felly, os oes ddrysau n, gallai fod wedi cymryd Sean cwpl o flynyddoedd yn ôl camau n.

291
00:17:18,170 --> 00:17:21,520
Yn awr, yn eich achos chi, Alex, o ystyried bod y niferoedd yn cael eu datrys -

292
00:17:21,520 --> 00:17:25,130
a gallwn fath o chasglu hyn o ble rydym wedi bod hyd yn hyn yn y stori hon -

293
00:17:25,130 --> 00:17:28,300
beth amser yn rhedeg o Alex algorithm mwy deallus

294
00:17:28,300 --> 00:17:30,770
o ddechrau o'r canol ac yna ailadrodd?

295
00:17:30,770 --> 00:17:36,490
[Myfyrwyr] 3. >> Felly, mae'n mynd i fod yn 3, yn fras, os byddwch yn mynd 8-4 i 2 i 1.

296
00:17:36,490 --> 00:17:40,660
Felly 3 cham neu, yn fwy cyffredinol, dyna log n eto.

297
00:17:40,660 --> 00:17:43,380
Unrhyw bryd y byddwch chi'n haneru a haneru a haneru a haneru,

298
00:17:43,380 --> 00:17:45,290
sy'n fynegiant o syniad hwn o log n.

299
00:17:45,290 --> 00:17:48,140
Ac felly y byddem wedi cymryd dim ond 3 cham, ac yn wir y gwnaeth

300
00:17:48,140 --> 00:17:50,890
ar ôl i ni agor y drysau haneru a haneru,

301
00:17:50,890 --> 00:17:53,770
tra byddai hyn wedi cymryd Sean tua 7 neu 8 cam.

302
00:17:53,770 --> 00:17:56,330
Felly diolch ichwi am fod gyda ni eleni. >> Diolch yn fawr. Braf eich cyfarfod chi.

303
00:17:56,330 --> 00:18:00,170
Diolch i Alex. Yn yr un modd >>. [Cymeradwyaeth]

304
00:18:00,170 --> 00:18:02,150
>> Beth yna bydd y goblygiadau go iawn o hyn?

305
00:18:02,150 --> 00:18:06,050
Nawr dychmygwch nad yw'n sef 8 drysau, sydd, a dweud y gwir, gallai pob un ohonom ddod o hyd i rywbeth

306
00:18:06,050 --> 00:18:10,430
y tu ôl i ddrysau 8 yn weddol gyflym yn unig gan rwygo y darnau o bapur a mynd gyda ein greddf.

307
00:18:10,430 --> 00:18:14,430
Ond beth os yw'n miliwn o ddrysau? Beth os yw'n 4000000000 drysau?

308
00:18:14,430 --> 00:18:19,630
Yn achos 4000000000 drysau, ydych wirioneddol yn mynd i eisiau i fynd gyda Alex algorithm,

309
00:18:19,630 --> 00:18:23,150
deuaidd chwilio gan y byddwn yn dechrau ei alw'n neu rannu a goncro, yn fwy cyffredinol,

310
00:18:23,150 --> 00:18:25,220
lle rydych yn cadw haneru a haneru y broblem,

311
00:18:25,220 --> 00:18:30,510
oherwydd os oes gennych 4000000000 drysau, gall sawl gwaith y byddwch yn Torrwch 4 biliwn mewn hanner?

312
00:18:30,510 --> 00:18:33,870
[Myfyrwyr] 32. >> Mae'n mewn gwirionedd yn 32. Gallwch weithio hyn allan ar ddarn o bapur neu yn eich pen.

313
00:18:33,870 --> 00:18:38,490
Rydych yn mynd 4000000000-2000000000 to 1 biliwn i hanner biliwn, i 250 miliwn, dot, dot, dot.

314
00:18:38,490 --> 00:18:41,620
Ac os ydych yn gwneud allan y cwestiwn, rydych chi'n mynd i wir, yn cael 32,

315
00:18:41,620 --> 00:18:44,950
ac sydd mewn gwirionedd yn ymwneud â gwyddoniaeth gyfrifiadurol oherwydd ein bod fel arfer yn cyfrif mewn pwerau o 2.

316
00:18:44,950 --> 00:18:47,600
2 i 32 yn digwydd i fod yn 4 biliwn.

317
00:18:47,600 --> 00:18:51,440
Felly, mae llawer o berthnasol i'r math yma o bwerau 2 mewn gwyddoniaeth gyfrifiadurol.

318
00:18:51,440 --> 00:18:55,120
>> Ond beth tua 8 biliwn? Faint o gamau yw bod mynd i'w cymryd os oes 8000000000 drysau?

319
00:18:55,120 --> 00:19:00,350
[Myfyrwyr] 33. Felly >> 33. Beth os oes 16000000000 drysau? Faint o gamau yw bod mynd i gymryd?

320
00:19:00,350 --> 00:19:05,020
[Myfyrwyr] 34. >> 34. Gallem fath o barhau â'r syrffed ad. Ond mae hynny'n beth pwerus.

321
00:19:05,020 --> 00:19:09,430
Gallwch gyflwyno biliynau o fewnbynnau yn fwy at eich problem, ond, nid oes llawer mawr,

322
00:19:09,430 --> 00:19:14,140
'ch jyst yn cymryd 1 brathiad ychwanegol y tu allan ohono ac felly yn rhoi rhywbeth i ni fel chwiliad deuaidd

323
00:19:14,140 --> 00:19:15,920
neu rannu a goncro, yn fwy cyffredinol.

324
00:19:15,920 --> 00:19:17,990
Ond rwy'n fath o dwyllo yma, dde?

325
00:19:17,990 --> 00:19:22,410
Yn achos Alex algorithm, roedd ganddi fantais dros Sean.

326
00:19:22,410 --> 00:19:27,780
Roedd hi'n gwybod bod y niferoedd hyn yn cael eu datrys, ond nid Alex oedd yn rhaid i'w datrys ei hun.

327
00:19:27,780 --> 00:19:30,520
I ymlaen llaw yn dod i fyny at y bwrdd du a math o gwneud yn siŵr

328
00:19:30,520 --> 00:19:33,670
y tynnais nhw i gyd allan er mwyn datrys, yna rwyf yn gorchuddio gyda phapur.

329
00:19:33,670 --> 00:19:35,850
Ond faint o waith oedd yn cymryd i mi?

330
00:19:35,850 --> 00:19:40,110
Os ydym wedi dechrau i ffwrdd gyda rhifau hyn mewn rhyw fath o drefn sy'n ymddangos ar hap -

331
00:19:40,110 --> 00:19:43,320
yn yr achos hwn y niferoedd hyn symlach, 1 drwy 8 yma -

332
00:19:43,320 --> 00:19:46,090
sut ydym yn mynd ati i drefnu gwerthoedd hyn?

333
00:19:46,090 --> 00:19:52,530
Os oeddech yn ddynol roddir y dasg hon, pa fath o ddull sythweledol eich bod yn cymryd

334
00:19:52,530 --> 00:19:54,800
i roi trefn criw cyfan o rifau?

335
00:19:54,800 --> 00:19:57,050
Mae'r pethau hyn yn cael eu gosod allan fel darnau pos. Yeah.

336
00:19:57,050 --> 00:19:59,950
>> [Myfyrwyr] byddwn yn cymryd pob rhif ac yn ei gymharu i bob un

337
00:19:59,950 --> 00:20:03,180
a dal i fynd i'r chwith. >> Iawn, yn dda.

338
00:20:03,180 --> 00:20:05,720
Felly, yn cymryd pob rhif, ei gymharu i'r un nesaf ato,

339
00:20:05,720 --> 00:20:09,610
ac yna dim ond yn dal i symud ar hyd y math rhestr o rejiggering pethau wrth i chi fynd.

340
00:20:09,610 --> 00:20:13,800
Felly dyma ni yn cael cyfle i efallai ychydig mwy o Folks i gymryd rhan.

341
00:20:13,800 --> 00:20:16,290
A oes gennym 8 o wirfoddolwyr byddai mwy sydd wrth eu bodd i ddod o hyd?

342
00:20:16,290 --> 00:20:23,950
Nid yw pwysau ychydig yn llai ers i chi yw'r unig un. 1, 2, 3, 4, 5, 6, 7, 8.

343
00:20:23,950 --> 00:20:28,190
Dewch i lawr. Rydych guys yn mynd i fod y rhifau 1 drwy 8.

344
00:20:28,190 --> 00:20:36,050
Gawn ni weld os na allwn wneud hyn didoli gyfer Alex lawer yn yr un modd yr wyf yn gwneud hynny o flaen llaw.

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

346
00:20:37,640 --> 00:20:40,760
Mynd yn ei flaen ac os hoffech, llinell i fyny ar y llwyfan rhwng y stand cerddoriaeth a mi yma

347
00:20:40,760 --> 00:20:44,960
yn yr un drefn ag y sleid ar y sgrin.

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

349
00:20:50,370 --> 00:20:53,230
Byddwn yn gweithio i chi yn yr enghraifft nesaf. O, aros, aros. Yma rydym yn mynd. Arhoswch.

350
00:20:53,230 --> 00:20:57,570
Mae'r enghraifft nesaf yn awr. Dyma chi fynd. Rhif 8. Dewch ar i fyny.

351
00:20:57,570 --> 00:21:00,270
Mae pob hawl. Trefnu eich hunain yn ôl i hyn.

352
00:21:00,270 --> 00:21:03,620
Llithro ychydig bach ar ochr y gerddoriaeth yn sefyll yma.

353
00:21:03,620 --> 00:21:12,310
Felly mae gennym 4, 2, 6 - mynd i mewn yno, dros yma, iawn yno - 3.

354
00:21:12,310 --> 00:21:17,570
Yeah. Iawn. Rydych yn mynd dros yma. Na, byddwch yn aros yno.

355
00:21:17,570 --> 00:21:21,840
Yeah, iawn yno. Rhif dwi'n anghywir. Iawn yno. Iawn, da iawn. Iawn.

356
00:21:21,840 --> 00:21:24,930
Felly nawr gadewch i ni eu didoli mewn gorchymyn cynyddol.

357
00:21:24,930 --> 00:21:26,210
>> Sut alla i fynd ati i wneud hyn?

358
00:21:26,210 --> 00:21:28,630
Mae'r algorithm a gynigiwyd funud yn ôl yn pam nad ydym yn unig yn cymharu

359
00:21:28,630 --> 00:21:31,970
y Folks sydd yn fath o nesaf at ei gilydd ac yna ddatrys unrhyw gamgymeriadau,

360
00:21:31,970 --> 00:21:33,540
symud o'r chwith i'r dde.

361
00:21:33,540 --> 00:21:36,580
Felly yma mae gennym 4 a 2, yn amlwg allan o drefn. Gadewch i ni gyfnewid chi. Iawn.

362
00:21:36,580 --> 00:21:40,760
Felly nawr rwy'n mynd i symud i lawr y llinell. 4 a 6, Na. [Chwerthin]

363
00:21:40,760 --> 00:21:45,010
6 ac 8, 'n bert da. 8 a 1, gadewch i mi gyfnewid i chi guys. Mae pob hawl.

364
00:21:45,010 --> 00:21:48,030
Felly, 8 a 3, cyfnewid i chi guys.

365
00:21:48,030 --> 00:21:52,280
8 a 7, gadewch i mi gyfnewid i chi guys. 5 ac 8, yn rhagorol.

366
00:21:52,280 --> 00:21:54,820
Wyf yn rhoi rhestr i chi datrys.

367
00:21:54,820 --> 00:21:56,860
Mae pob hawl. Felly, nid yn eithaf.

368
00:21:56,860 --> 00:22:01,180
Ond mae'n well oherwydd y niferoedd mwy - achos ym mhwynt 8 -

369
00:22:01,180 --> 00:22:04,030
wedi math o bubbled i fyny o'r chwith draw i'r dde.

370
00:22:04,030 --> 00:22:08,010
Felly cefais 1 o yn iawn, ond mae'n teimlo fel hyn nid oedd yn datrys y broblem.

371
00:22:08,010 --> 00:22:11,150
>> Felly byddai hyn yr ydych yn bwriadu rydym yn ei wneud nesaf? >> [Myfyrwyr] Cadwch wneud hynny. >> Rydym yn cadw wneud hynny.

372
00:22:11,150 --> 00:22:13,740
Ac yn sylweddoli, unwaith eto, rydym yn gosod pethau i fyny at jyst yn cael yr holl bobl

373
00:22:13,740 --> 00:22:17,180
math o ddeallus trefnu eu hunain yn seiliedig ar y llun,

374
00:22:17,180 --> 00:22:19,040
ond erbyn hyn mae'n rhaid i ni fod yn llawer mwy trefnus.

375
00:22:19,040 --> 00:22:21,510
Mae'n rhaid i ni fod yn algorithmig yn ei gylch fel pe rydym yn ysgrifennu cod -

376
00:22:21,510 --> 00:22:23,520
yn yr achos hwn pseudocode lafar.

377
00:22:23,520 --> 00:22:26,040
Felly, gadewch i mi jyst yn ceisio hynny eto. Oedd yn gweithio'n eithaf da. Nid oedd yn datrys.

378
00:22:26,040 --> 00:22:30,400
Ond pan fydd yn amau, dim ond ceisiwch a cheisiwch eto. Felly, 2 a 4, nid oedd yn helpu anymore.

379
00:22:30,400 --> 00:22:33,200
4 a 6. Ah! 6 a 1, ychydig yn well yn awr.

380
00:22:33,200 --> 00:22:39,740
6 a 3, yn dda. 6 a 7, 7 a 5, 7 ac 8, yn dda.

381
00:22:39,740 --> 00:22:44,060
A ydych yn gwybod, mae'n debyg y gallaf anwybyddu 8 yn awr oherwydd ei fod ar ddiwedd y rhestr.

382
00:22:44,060 --> 00:22:47,250
Efallai nad ydym yn rhaid i chi boeni am rywun yn mynd heibio iddo.

383
00:22:47,250 --> 00:22:49,240
Ond gadewch i ni weld os bydd hynny'n dybiaeth ddiogel.

384
00:22:49,240 --> 00:22:52,340
Nawr rhestr yw - damn - nid didoli. Gadewch i ni geisio hyn eto.

385
00:22:52,340 --> 00:22:56,440
Felly, 2 a 4, 4 ac 1, 4 a 3.

386
00:22:56,440 --> 00:22:59,230
4 a 6, yn dda. 6 a 5, yn dda.

387
00:22:59,230 --> 00:23:04,890
6, 7, ac 8, yn dda. Ond rhybudd y gall, Fi jyst aros yma yn awr ac yn stopio yma nawr?

388
00:23:04,890 --> 00:23:07,770
[Myfyrwyr] Ydy. >> Yeah?

389
00:23:07,770 --> 00:23:11,160
Beth os oes un ohonoch wedi bod yn rhif 9 yr holl ffordd dros yno?

390
00:23:11,160 --> 00:23:13,640
Byddai wedi cael ei datrys. >> Da. Byddai wedi cael ei datrys y tro cyntaf o gwmpas.

391
00:23:13,640 --> 00:23:16,050
Da. Felly, gadewch i ni fynd yn ôl eto. Rydym bron yno.

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

393
00:23:22,800 --> 00:23:26,640
>> Yr wyf yn ei wneud yn awr ond, unwaith eto, rwy'n cyfrifiadur sydd ond yn gallu gwneud yr hyn rwy'n gwybod ei wneud,

394
00:23:26,640 --> 00:23:30,120
ac a gofiaf yn unig nawr yw fy mod mewn gwirionedd yn unig wnes i dipyn o waith.

395
00:23:30,120 --> 00:23:31,700
Rhywbeth newid yma.

396
00:23:31,700 --> 00:23:37,100
Felly, nid wyf wedi cadarnhau technegol weledol neu algorithmically bod y rhestr hon yn cael ei ddatrys yn wir.

397
00:23:37,100 --> 00:23:40,720
Felly, dim ond ar gyfer mesur da, dim ond i fod rhefrol am hyn, gadewch i ni wneud y tro hwn 1 yn fwy.

398
00:23:40,720 --> 00:23:44,040
Felly, 1 a 2, 2 a 3, 3 a 4. A ydych yn gwybod beth?

399
00:23:44,040 --> 00:23:46,190
Dim ond ar gyfer mesur da, dw i'n mynd i gadw trac ar fy llaw y tro hwn

400
00:23:46,190 --> 00:23:51,110
faint o gyfnewid wyf yn gwneud yn union fel fy mod yn gwybod faint o waith wyf wedi ei wneud mewn gwirionedd.

401
00:23:51,110 --> 00:23:56,930
3 a 4, 4 a 5, 5 a 6, 6 a 7, 7 ac 8. Dim cyfnewid.

402
00:23:56,930 --> 00:24:00,800
Felly nawr byddwn yn gyfreithlon yn idiot i wneud hyn eto

403
00:24:00,800 --> 00:24:03,330
oherwydd os wyf yn gwneud dim gwaith drwy y bwlch hwn y bodau dynol,

404
00:24:03,330 --> 00:24:06,710
yna mae'n amlwg y mae hynny'n mynd i ddigwydd eto os nad oes un sy'n fath o hap

405
00:24:06,710 --> 00:24:10,410
adversarially symud eu hunain o gwmpas. Felly nawr gallaf stopio.

406
00:24:10,410 --> 00:24:15,120
Nawr gadewch i ni ofyn y cwestiwn, faint o waith oedd hyn mewn gwirionedd yn cymryd i mi?

407
00:24:15,120 --> 00:24:18,260
Faint o gamau oedd hynny'n ei gymryd? >> N sgwâr.

408
00:24:18,260 --> 00:24:20,400
Yeah, felly n sgwâr. Ble ydych chi'n cael n sgwâr o?

409
00:24:20,400 --> 00:24:22,660
Mae'n rhaid i chi wirio pob NUM -

410
00:24:22,660 --> 00:24:26,530
Mae rhifau n, ac mae'n rhaid i chi wirio bob rhif gyda rhifau n arall.

411
00:24:26,530 --> 00:24:29,030
Da. >> Felly, mae n sgwâr. >> Da.

412
00:24:29,030 --> 00:24:31,060
>> Felly, mae'n teimlo fel y gallai fod yn dda iawn yn n sgwâr, dde?

413
00:24:31,060 --> 00:24:33,820
Mae wedi n o'r rhain guys, 8 yn benodol yn yr achos hwn,

414
00:24:33,820 --> 00:24:37,590
ond bob tro rwy'n mynd drwy'r rhestr hon yr wyf yn cymharu y person cyntaf yn erbyn yr ail,

415
00:24:37,590 --> 00:24:39,650
yr ail yn erbyn y trydydd eto ac eto ac eto,

416
00:24:39,650 --> 00:24:42,450
a phan gefais hyd y diwedd, beth wnes i? Rwy'n redid hynny.

417
00:24:42,450 --> 00:24:46,280
Felly, os ydym yn cyffredinoli esboniad hwn, rydym wedi n pobl

418
00:24:46,280 --> 00:24:51,090
ac fy mod yn gwneud, yn amlwg, 8 cam, n grisiau, bob tro y byddaf yn mynd drwy hyn algorithm.

419
00:24:51,090 --> 00:24:56,070
Ond faint o weithiau yn yr achos gwaethaf oes rhaid i mi fynd drwy'r rhestr yma o bobl?

420
00:24:56,070 --> 00:24:59,370
[Myfyrwyr] N amser. >> Mae'n debyg n, iawn, oherwydd yn yr achos gwaethaf,

421
00:24:59,370 --> 00:25:03,410
beth mae'n debyg y trefniant achos gwaethaf o'r rhain guys o gael-fynd?

422
00:25:03,410 --> 00:25:06,520
Os ydynt yn gwrthdroi yn gyfan gwbl er mwyn

423
00:25:06,520 --> 00:25:09,310
oherwydd dim ond mae'n debyg feddyliol, let's - Beth yw eich enw? >> Bowen.

424
00:25:09,310 --> 00:25:12,510
Bowen. Iawn. Felly Bowen, dewch draw yma am ychydig funudau'n.

425
00:25:12,510 --> 00:25:16,150
>> Gadewch i ni dybio bod Bowen oedd yma ar ddechrau'r algorithm,

426
00:25:16,150 --> 00:25:19,790
ac nid ydym yn gwybod beth mae pawb arall yn gwneud, ond Bowen yma, yn ôl yr algorithm -

427
00:25:19,790 --> 00:25:23,820
ac os ydych am i ychydig dro gyda mi - yn mynd i swigen i fyny, fel y gwnaeth y tro cyntaf o gwmpas,

428
00:25:23,820 --> 00:25:25,740
yr holl ffordd hyd y diwedd.

429
00:25:25,740 --> 00:25:29,400
Ond mae'n debyg bod y person nesaf i Bowen oedd y rhif 7.

430
00:25:29,400 --> 00:25:33,450
Rhaid i mi fynd yn ôl a chael rhif 7, sy'n golygu rhaid i mi fynd yr holl ffordd yn ôl yma.

431
00:25:33,450 --> 00:25:36,980
Nawr rhaid i mi gael bod cerdded yr un gyda'r person sydd yn rhif 7.

432
00:25:36,980 --> 00:25:40,140
Ond beth os hynny rhif 6 yn nesaf iddo hefyd?

433
00:25:40,140 --> 00:25:42,180
Yna rhaid i mi fynd yn ôl a chael 6.

434
00:25:42,180 --> 00:25:46,490
Felly, unwaith eto, ar bob fersiwn o hwn yn ddolen rwy'n siarad â phob un o'r bobl n,

435
00:25:46,490 --> 00:25:50,090
ac efallai y bydd rhaid i mi wneud n o'r teithiau cerdded hamddenol i wneud yn siwr fy mod yn tynnu

436
00:25:50,090 --> 00:25:53,760
pob un o'r elfennau mwyaf ôl ac yn ôl ac yn ôl i'r ddiwedd y rhestr.

437
00:25:53,760 --> 00:25:58,230
Pethau Felly n n amser yn unig yw gwaith n n n neu sgwâr.

438
00:25:58,230 --> 00:26:02,050
>> Felly dyma eisoes gennym algorithm sy'n mwyach n, dyw hynny ddim yn bellach n log,

439
00:26:02,050 --> 00:26:04,820
mewn gwirionedd mae'n waeth nag unrhyw beth rydym wedi ei wneud o'r blaen.

440
00:26:04,820 --> 00:26:09,840
Felly, Alex math o got 'n ffodus fy mod yn gwneud yr holl waith pob golwg o flaen llaw ar gyfer ei,

441
00:26:09,840 --> 00:26:14,690
yr holl waith drud, er mwyn iddi allu eu mwynhau yn y algorithm chwiliad deuaidd,

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

443
00:26:16,420 --> 00:26:18,240
Ond mae hyn yn gyson â dydd Llun thema.

444
00:26:18,240 --> 00:26:23,260
Rydym yn rhoi ychydig mwy o le, rydym yn defnyddio darnau mwy, er mwyn cyflymu ein amser yn rhedeg.

445
00:26:23,260 --> 00:26:26,170
Mae cymaint fel mae y fasnach-off rhwng amser a gofod,

446
00:26:26,170 --> 00:26:31,060
gallai hefyd newydd fod yn cyfaddawdu rhwng amser a dreuliwyd i fyny math flaen o gael pethau'n barod i fynd

447
00:26:31,060 --> 00:26:35,000
ac mewn gwirionedd yn gweithredu fel algorithm chwilio. Gadewch i ni geisio un arall.

448
00:26:35,000 --> 00:26:39,050
Os na fyddech guys meddwl dim ond yn gyflym ad-drefnu eich hunain i gyd-fynd hynny eto,

449
00:26:39,050 --> 00:26:42,240
gadewch i ni roi cynnig ar rywbeth ychydig yn wahanol os nad yw'n mor syml

450
00:26:42,240 --> 00:26:45,760
fel dim ond atgyweiria holl gamgymeriadau pairwise, sydd yn super 'n athrylithgar.

451
00:26:45,760 --> 00:26:48,150
Gadewch i ni yn lle hynny fod ychydig yn fwy bwriadol a gwneud hyn.

452
00:26:48,150 --> 00:26:51,010
Mae hyn yn un rhy byddwn yn cynnig yn ôl pob tebyg 'n bert' n athrylithgar.

453
00:26:51,010 --> 00:26:55,070
>> Gadewch i ni ddewis y person lleiaf o'r rhestr eto ac eto. Felly, yma rydym yn mynd.

454
00:26:55,070 --> 00:26:57,350
4, chi yw'r person lleiaf rwyf wedi weld hyd hyd yn hyn,

455
00:26:57,350 --> 00:27:00,520
felly dwi'n mynd i feddyliol gofio bod at jyst yn pwyntio ar chi ar hyn o bryd.

456
00:27:00,520 --> 00:27:05,020
2. Ooh! Anghofiwch am rif 4. Fi jyst dod o hyd i'r elfen newydd lleiaf yn y rhestr hon.

457
00:27:05,020 --> 00:27:07,410
Rydw i'n mynd i fath o gofio hynny. 6, 8.

458
00:27:07,410 --> 00:27:11,190
Ooh! 1. Hwyl fawr. Felly nawr rwy'n mynd i gofio rhif 1.

459
00:27:11,190 --> 00:27:14,790
Rydym yn gwybod bod 1 yw'r lleiaf, ond yr wyf fi yw'r cyfrifiadur. Beth os oes 0?

460
00:27:14,790 --> 00:27:17,140
Beth os oes -1? Rhaid i mi ddal ati.

461
00:27:17,140 --> 00:27:20,990
Felly 3, 7, 5, Na. Iawn. Felly, rhif 1 oedd y lleiaf.

462
00:27:20,990 --> 00:27:23,640
Gadewch i mi eich dewis o'r rhestr - we'll dilyn y ffordd hon -

463
00:27:23,640 --> 00:27:27,760
ac yn eich rhoi fympwyol ar ddechrau'r rhestr.

464
00:27:27,760 --> 00:27:29,740
Yn awr, arhoswch funud. Yr wyf yn fath o twyllo.

465
00:27:29,740 --> 00:27:34,010
Os yw'r rhain yn guys yn cynrychioli nid yw'n rhestr o 8 o bobl ond yn hytrach yn array,

466
00:27:34,010 --> 00:27:37,050
8 darnau o gof cyffiniol - ydych chi'n meddwl camu yn ôl am ychydig funudau'n?

467
00:27:37,050 --> 00:27:39,060
Does dim mewn gwirionedd lle i chi hawl yma.

468
00:27:39,060 --> 00:27:41,840
Felly sut rydym yn gwneud lle ar gyfer - beth yw eich enw? >> Sammy. >> Sammy.

469
00:27:41,840 --> 00:27:43,710
Sut rydym yn gwneud lle ar gyfer Sammy?

470
00:27:43,710 --> 00:27:46,760
>> Rydym yn symud y n sydd ger fy mron. >> Iawn.

471
00:27:46,760 --> 00:27:48,850
Felly, gallem symud y bobl n sydd o'i flaen ef,

472
00:27:48,850 --> 00:27:52,400
felly os ydych guys am cymryd 1 bwriadol, cam dramatig ar y chwith.

473
00:27:52,400 --> 00:27:57,000
Maent i gyd yn gwneud hynny ar y cyd, ond y tro diwethaf i mi ysgrifennodd rhai cod,

474
00:27:57,000 --> 00:27:59,740
nad ydych yn gallu datrys o symud llawer o bethau i gyd ar unwaith.

475
00:27:59,740 --> 00:28:02,450
Gallem wneud hynny mewn dolen, symud pawb unwaith ar y tro.

476
00:28:02,450 --> 00:28:04,340
Felly, os na fyddech yn meddwl guys camu yn ôl i'r dde,

477
00:28:04,340 --> 00:28:07,230
a Sammy, pe baech yn gallu camu yn ôl oherwydd mae dal oes lle i chi,

478
00:28:07,230 --> 00:28:11,420
nawr gadewch i wneud hyn. Lle'r oedd Sammy funud yn ôl? Iawn yno.

479
00:28:11,420 --> 00:28:16,140
Felly, mae yna fwlch yno. Felly, gallech symud i mewn i Sammy yn fan a'r lle.

480
00:28:16,140 --> 00:28:20,580
Nawr person nesaf i fyny ac yn awr person nesaf, sydd bellach person nesaf. Nawr mae gennym le i Sammy.

481
00:28:20,580 --> 00:28:23,490
Yn awr, mae rhywun o'r gynulleidfa - a oedd yn dda, a oedd yn gywir,

482
00:28:23,490 --> 00:28:27,070
yn teimlo ychydig o amser - beth gyflymach? Yeah.

483
00:28:27,070 --> 00:28:29,440
[Myfyrwyr] Mae amrywiaeth newydd? >> Beth sy'n bod? >> [Myfyrwyr] Mae amrywiaeth newydd? >> Iawn, yn dda.

484
00:28:29,440 --> 00:28:33,200
>> Felly, yn gyson â'r thema hon o ddim ond masnach-offs, pam nad ydw i'n jyst yn gwneud casgliad newydd

485
00:28:33,200 --> 00:28:36,570
 ac yna bydd yn cael ei Sammy nofio yn y gofod o flaen y bobl, er enghraifft,

486
00:28:36,570 --> 00:28:39,600
a gallwn dim ond dechrau llenwi casgliad newydd yn gyfan gwbl. Byddai hefyd yn gweithio.

487
00:28:39,600 --> 00:28:42,450
Ond dydw i ddim ddiddordeb yn ei wario mwy o le heddiw. Beth yw ymagwedd arall?

488
00:28:42,450 --> 00:28:46,630
[Myfyrwyr] Cyfnewid. >> Iawn. Gallai Rydym yn unig cyfnewid y 2 guys. Beth yw eich enw?

489
00:28:46,630 --> 00:28:49,390
Mario. >> Mario. Felly Mario, oeddech ar hyn o bryd yma.

490
00:28:49,390 --> 00:28:52,480
Sammy, a allwch chi yn ôl i fyny am ychydig o bryd? Mario yma.

491
00:28:52,480 --> 00:28:55,830
Nid oes gennym le i chi anymore, felly os na fyddech yn meddwl mynd i'r lle Sammy yw,

492
00:28:55,830 --> 00:29:02,430
byddwn yn rhoi Sammy yma, ac yn awr byddwn i'n dadlau bod Sammy gweithrediad cyfnewid yn llawer cyflymach.

493
00:29:02,430 --> 00:29:06,370
Gwnaethom 1 llawdriniaeth i gyfnewid hyn guys, neu efallai 2 i gyfnewid hyn guys,

494
00:29:06,370 --> 00:29:11,210
ond doedden ni ddim yn ei wneud 1, 2, 3, 4, fel bod yn teimlo'n well. Yn awr, arhoswch funud.

495
00:29:11,210 --> 00:29:14,660
Yr wyf yn fath o wneud y broblem yn waeth oherwydd rhif 4 yn fath o agos at y dechrau.

496
00:29:14,660 --> 00:29:19,470
Nawr rhif 4 yn ychydig yn agosach i'r perwyl hwn, ond doeddwn i ddim wir yn gwybod nac yn poeni am hynny.

497
00:29:19,470 --> 00:29:23,330
Felly, mae hyn yn unig yw lwc ddrwg bod rhif 4 yn ychydig ymhellach i ffwrdd oddi wrth ei le tynghedu.

498
00:29:23,330 --> 00:29:25,110
Felly, gadewch i ni bellach yn ailadrodd y algorithm.

499
00:29:25,110 --> 00:29:28,410
>> I grynhoi, cyn belled ag y stori oedd, i gyd wnaethom oedd cerdded drwy'r rhestr

500
00:29:28,410 --> 00:29:31,130
chwilio am y person lleiaf rhifo.

501
00:29:31,130 --> 00:29:34,530
Felly nawr gadewch i ni wneud hynny eto. Nid ydym yn rhaid i chi boeni am Sammy anymore.

502
00:29:34,530 --> 00:29:37,590
Gallwn jyst yn mynd yma. Ooh! Rhif 2. Dyna nifer eithaf bach.

503
00:29:37,590 --> 00:29:41,180
6, 8, 4, 3, 7, 5. Iawn, yn dda.

504
00:29:41,180 --> 00:29:43,770
A diolch byth, drwy gyd-ddigwyddiad, nid oes gennyf i symud - >> Willie.

505
00:29:43,770 --> 00:29:45,910
Willie oherwydd ei fod yn yn ei le ar hyn o bryd.

506
00:29:45,910 --> 00:29:48,110
Gadewch i ni wneud hyn eto ac yn anwybyddu y 2 guys.

507
00:29:48,110 --> 00:29:50,460
6. Dyna nifer eithaf bach. Ooh! 8 yn bendant yn fwy.

508
00:29:50,460 --> 00:29:53,410
4. Gadewch i ni ganolbwyntio ar 4. Ooh! 3 yn hyd yn oed yn well.

509
00:29:53,410 --> 00:29:58,290
7 a 5. Felly, beth ydym yn ei wneud yn awr - >> Roger. >> Roger?

510
00:29:58,290 --> 00:30:00,250
Gadewch i ni gyfnewid ag ef gyda rhif 6.

511
00:30:00,250 --> 00:30:03,570
Felly os byddai 6 a 3 yn hoffi cyfnewid,

512
00:30:03,570 --> 00:30:07,320
rydym wedi awr yn fath o gotten ffodus bod 6 yn agosach at lle y dylai hi fod,

513
00:30:07,320 --> 00:30:10,300
ond mae'r un cyd-ddigwyddiad yma. Felly, gadewch i ni yn awr yn mynd yma.

514
00:30:10,300 --> 00:30:13,430
8 yn nifer eithaf bach. Ooh! 4 yn llai.

515
00:30:13,430 --> 00:30:17,130
6, 7, 5. Beth ydyn ni'n wneud yn awr? Swap >>. >> Yn union.

516
00:30:17,130 --> 00:30:19,010
Felly nawr gadewch i ni wneud y math hwn o gyflymach.

517
00:30:19,010 --> 00:30:24,460
8, 6, 7, 5. Ble mae 5 yn mynd? Da. Iawn.

518
00:30:24,460 --> 00:30:28,380
6, 7, 8. 6 yn cael i aros ble mae hi. Beth yw eich enw? >> Rosalie.

519
00:30:28,380 --> 00:30:31,770
Rosalie yn cael i aros ble mae hi. 7 yn dod i - Gadewch i ni weld. 7, 8. Iawn.

520
00:30:31,770 --> 00:30:35,100
Hynny 7 yn dod i aros ble mae hi. Beth yw eich enw? >> Amna. >> Amna.

521
00:30:35,100 --> 00:30:39,670
>> Felly, Amna yn cael i aros lle mae hi, a rhif 8 yn barod lle y dylai bellach fod.

522
00:30:39,670 --> 00:30:43,960
Iawn, yn dda. Mae'n teimlo fel ein bod dim ond creu gwaith ar gyfer ein hunain yma, er.

523
00:30:43,960 --> 00:30:47,440
Beth yn y pen draw yr amser yn rhedeg y algorithm?

524
00:30:47,440 --> 00:30:51,900
Os ydym yn meddwl am y bobl hyn nid fel 8 ond fel n? >> Mae'n n.

525
00:30:51,900 --> 00:30:55,440
Mae'n n camau, ond rydym yn gwirio bob tro.

526
00:30:55,440 --> 00:30:57,570
Iawn. N ond eich bod yn gwirio bob tro?

527
00:30:57,570 --> 00:31:03,450
Iawn, ond os yw'n n gamau na ddylai, yr wyf wedi gallu datrys chi gan jyst yn mynd 1, 2, 3, 4?

528
00:31:03,450 --> 00:31:05,590
Oh! Iawn, mae hynny'n wahaniaeth mawr.

529
00:31:05,590 --> 00:31:08,050
Felly n sgwariodd pam? Beth sy'n digwydd mewn gwirionedd?

530
00:31:08,050 --> 00:31:12,130
Mae pobl n yn y rhestr hon, ond i ddod o hyd i'r person lleiaf yn y rhestr

531
00:31:12,130 --> 00:31:16,200
yn yr achos gwaethaf, faint o gamau oes rhaid i mi gymryd? N. >>

532
00:31:16,200 --> 00:31:19,160
>> N, iawn, oherwydd yn yr achos gwaethaf, rhif 1 yn yr holl ffordd dros yno,

533
00:31:19,160 --> 00:31:20,990
felly rhaid i mi fynd i gael ef neu hi.

534
00:31:20,990 --> 00:31:25,500
Ac yna pan oeddwn yn olaf sylweddoli 1 oedd y lleiaf, yna mae'n eithaf cyflym i gyfnewid eu cyfer.

535
00:31:25,500 --> 00:31:28,450
Ond yn awr rhaid i mi ddechrau o'r dechrau ac yn edrych i bwy?

536
00:31:28,450 --> 00:31:31,980
Mae'r person nesaf lleiaf, sef 2. Ble yn yr achos gwaethaf yw 2?

537
00:31:31,980 --> 00:31:34,320
O, fy Nuw. Mae'n holl ffordd dros yma ar y diwedd.

538
00:31:34,320 --> 00:31:37,000
Felly, yn awr yr wyf wedi gwneud un arall camau n, un arall camau n.

539
00:31:37,000 --> 00:31:41,200
Ac os ydym wedi cael pobl n ac yn yr achos gwaethaf y person lleiaf yw n camau i ffwrdd,

540
00:31:41,200 --> 00:31:45,230
dyna unwaith eto n n gwaith, ac felly rydym unwaith eto wedi n sgwâr.

541
00:31:45,230 --> 00:31:47,280
Nid yw hyn yn teimlo mor dda.

542
00:31:47,280 --> 00:31:52,150
Ac yn wir, hyd yn oed yn yr achos gorau - mae'n debyg eu bod yn dechrau didoli oddi ar -

543
00:31:52,150 --> 00:31:59,080
faint o gamau mae'n ei gymryd i mi ddefnyddio'r algorithm rhoi trefn ar y bobl n?

544
00:31:59,080 --> 00:32:01,010
N sgwâr. >> Clywais n sgwâr. Pam n sgwâr?

545
00:32:01,010 --> 00:32:05,240
Oherwydd bod yn rhaid i chi wirio bob tro. >> Yeah.

546
00:32:05,240 --> 00:32:08,060
Ac mae'n rhaid i chi eu cyfnewid. >> Er ein bod bodau dynol yn fath o omniscient

547
00:32:08,060 --> 00:32:10,770
yn yr ystyr weledol y gallwn dim ond math o weld bod hyn yn didoli,

548
00:32:10,770 --> 00:32:12,140
Nid yw cyfrifiadur yw bod smart.

549
00:32:12,140 --> 00:32:14,040
Mae'n mynd i edrych yma ac yma ac yma,

550
00:32:14,040 --> 00:32:16,610
ond os bydd yr hyn mae'n chwilio amdano yw'r elfen leiaf,

551
00:32:16,610 --> 00:32:22,110
chi ond yn gwybod eich bod yn dod o hyd i'r elfen lleiaf gan yr hyn pwynt? Unwaith y byddwch chi yn y diwedd.

552
00:32:22,110 --> 00:32:25,880
Ond ar y pwynt hwnnw rydych wedi dod o hyd dim ond yr elfen ar hyn o bryd lleiaf.

553
00:32:25,880 --> 00:32:28,810
Dydych chi ddim o reidrwydd yn gwybod unrhyw beth arall am gyflwr y byd.

554
00:32:28,810 --> 00:32:30,880
Felly, rhaid i chi fynd eto ac eto ac eto.

555
00:32:30,880 --> 00:32:34,880
>> Felly, y tro hwn Fi 'n sylweddol yn edrych yn fud gan fy mod yn gwirio, iawn, 2, chi yw'r lleiaf,

556
00:32:34,880 --> 00:32:37,530
ond nid wyf yn gwybod bod cyfanswm eto.

557
00:32:37,530 --> 00:32:41,090
3, 4, 5, 6, 7, 8. Iawn, yn dda. 2 oedd yn wir y lleiaf.

558
00:32:41,090 --> 00:32:43,150
Nawr, gadewch i ddod o hyd i'r lleiaf nesaf. Iawn.

559
00:32:43,150 --> 00:32:48,350
3, rydych ar hyn o bryd y lleiaf. Gadewch i ni weld. 4, 5, 6, 7, 8. Iawn, got 'n ffodus eto.

560
00:32:48,350 --> 00:32:53,170
3 yn wir yn y lle iawn. Ond dw i'n mynd i ddal i wneud hyn eto ac eto ac eto.

561
00:32:53,170 --> 00:32:55,990
Sut allwn ni wneud erioed mor ychydig yn well?

562
00:32:55,990 --> 00:33:00,120
Yn hytrach na chael pobl yn swigen i fyny pairwise o'r lleiaf i'r mwyaf

563
00:33:00,120 --> 00:33:04,350
ac yn hytrach na mynd yn ôl ac ymlaen drwy'r rhestr dewis y person yna lleiaf,

564
00:33:04,350 --> 00:33:09,780
pam nad ydym yn hytrach gwthiwch y bobl i mewn i gam restr newydd wrth gam?

565
00:33:09,780 --> 00:33:13,080
Gadewch i ni geisio hyn. Nawr, gadewch i mi alw hyn yn peth fath gosod.

566
00:33:13,080 --> 00:33:17,250
Felly dyma ni yma. Rhif 1. Nid wyf yn poeni am unrhyw un arall yn y rhestr hon.

567
00:33:17,250 --> 00:33:21,310
Fy nod ar hyn o bryd yw rhoi rhif 1 ar ddechrau'r rhestr datrys.

568
00:33:21,310 --> 00:33:23,910
Ac yr wyf i'n mynd i gynnig ers i mi yn unig yn cael 8 darnau o gof,

569
00:33:23,910 --> 00:33:28,670
fympwyol ar hyn o bryd rwy'n y wal rhwng fy rhestr i fod heb eu didoli,

570
00:33:28,670 --> 00:33:32,740
ac unrhyw un sydd tu ôl i mi yr wyf i'n mynd i hawlio yn cael ei datrys.

571
00:33:32,740 --> 00:33:34,680
Felly, yn awr mae gennym rhif 1.

572
00:33:34,680 --> 00:33:39,240
Wyf i am osod ef yn fy rhestr datrys, felly dwi jyst yn mynd i symud fy wal dros yma,

573
00:33:39,240 --> 00:33:43,930
ac yn awr y gallaf hawlio y rhestr hon yn cael ei datrys, y rhestr hon yn cael ei heb eu didoli - o leiaf cyn belled ag y gwn i.

574
00:33:43,930 --> 00:33:46,070
Ni allaf weld yr holl rifau ar unwaith.

575
00:33:46,070 --> 00:33:49,000
>> Nawr Yr wyf yn digwydd i ddod ar draws rhif 2. Beth ddylwn i ei wneud ag ef?

576
00:33:49,000 --> 00:33:54,380
I fewnosod chi nawr yn y rhestr datrys. Ond sylwch pa mor hawdd oedd hynny.

577
00:33:54,380 --> 00:33:59,650
Fi jyst yn rhaid i edrych. Rhif 1 yno. O, yn amlwg 2 yn mynd ar ochr y rhif 1.

578
00:33:59,650 --> 00:34:03,700
Nawr beth ddylwn i ei wneud gyda 3? I fewnosod i chi yn y rhestr datrys. Ond a oedd yn hynod hawdd.

579
00:34:03,700 --> 00:34:07,250
Mae hyn yn super hawdd, mae hyn yn super hawdd, mae hyn yn super hawdd, super hawdd, hawdd super.

580
00:34:07,250 --> 00:34:12,790
Ac yn awr mae popeth yn datrys y tu ôl i mi, a faint o gamau oedd hynny'n ei gymryd?

581
00:34:12,790 --> 00:34:15,620
[Myfyrwyr] N. >> Felly, mae n yn unig. Rydym yn got 'n ffodus.

582
00:34:15,620 --> 00:34:18,860
Dim ond n pham? >> [Myfyrwyr] Oherwydd bod y rhestr gael ei ddatrys.

583
00:34:18,860 --> 00:34:21,630
Mae'r rhestr yn cael ei datrys eisoes. Felly, rydym yn got 'n ffodus.

584
00:34:21,630 --> 00:34:25,639
Ond rydym yn cynllunio algorithm y tro hwn sy'n manteisio ar y math hwnnw o lwc,

585
00:34:25,639 --> 00:34:29,420
y senario achos gorau, drwy beidio â gwastraffu amser diangen.

586
00:34:29,420 --> 00:34:31,750
Felly, mae gennym yn awr yr hyn y byddwn yn galw math swigen

587
00:34:31,750 --> 00:34:33,949
lle mae pobl yn fath o swigen i fyny pairwise.

588
00:34:33,949 --> 00:34:38,100
Erbyn hyn mae gennym fath dethol lle rydym yn dynnaf y person lleiaf eto ac eto.

589
00:34:38,100 --> 00:34:42,350
Ac yn awr mae gennym fath mewnosod lle rydym yn fath o rhagweithiol rhoi pobl lle maent yn perthyn

590
00:34:42,350 --> 00:34:45,000
mewn rhestr didoli gynyddol.

591
00:34:45,000 --> 00:34:49,679
Os gallem, rownd o gymeradwyaeth ar gyfer y guys yma. [Cymeradwyaeth]

592
00:34:49,679 --> 00:34:52,310
Gadewch i ni gymryd ein 5-munud egwyl yma.

593
00:34:52,310 --> 00:34:55,139
A phan fyddwn yn dod yn ôl, byddwn yn chwythu pob un o'r algorithmau allan o'r dŵr

594
00:34:55,139 --> 00:35:00,260
gyda rhywbeth gwell. Mae pob hawl. Diolch yn fawr iawn. Gallwch gadw rhai fel cofroddion.

595
00:35:01,710 --> 00:35:04,330
Mae pob hawl. Rydym yn ôl.

596
00:35:04,330 --> 00:35:08,420
>> Ac i ailadrodd gyflym go iawn, cawsom ymagweddau hyn 3 gwahanol didoli,

597
00:35:08,420 --> 00:35:13,000
holl bwynt oedd i gyrraedd y pwynt lle mae rhywun fel Alex

598
00:35:13,000 --> 00:35:16,930
Gallai chwilio rhestr o rifau gyflymach na rhywun fel Sean gallai.

599
00:35:16,930 --> 00:35:19,830
Ac er bod gennym enghreifftiau syml o'r fath gyda 8 rhif,

600
00:35:19,830 --> 00:35:24,000
gallech allosod yn hawdd i 8 tudalen ar y we, 8000000000 tudalennau gwe,

601
00:35:24,000 --> 00:35:26,680
neu 800,000,000 ffrindiau ar Facebook.

602
00:35:26,680 --> 00:35:30,090
Felly, gall y algorithmau yn sicr raddfa i'r mathau hynny o werthoedd,

603
00:35:30,090 --> 00:35:32,300
a'r syniadau yn y pen draw yr un fath.

604
00:35:32,300 --> 00:35:36,140
Fath swigen Felly oedd y cyntaf lle rydym yn fath o swigod i fyny y person mwyaf

605
00:35:36,140 --> 00:35:39,110
yr holl ffordd i'r dde drwy gyfnewid pobl pairwise.

606
00:35:39,110 --> 00:35:42,040
Yna cawsom yr hyn y byddwn yn galw fath dewis lle yr wyf yn ychydig yn fwy bwriadol

607
00:35:42,040 --> 00:35:46,480
yn cadw yn edrych drwy'r rhestr, dewis y nifer lleiaf eto ac eto ac eto,

608
00:35:46,480 --> 00:35:49,530
y canlyniad rhesymegol o'r rhain yw bod y rhestr yn cael ei datrys yn y pen draw.

609
00:35:49,530 --> 00:35:53,780
Yna yn y trydydd, yr wyf mewnosod pobl yn eu lle priodol,

610
00:35:53,780 --> 00:35:57,720
ac rydym yn gwneud yn enghraifft contrived o ran bod y rhestr yn cael ei datrys yn barod,

611
00:35:57,720 --> 00:36:01,100
ond a oedd i anfon y neges bod yn achos fath mewnosod, yn

612
00:36:01,100 --> 00:36:02,670
gallwch gael lwcus.

613
00:36:02,670 --> 00:36:07,930
Os yw'r rhifau yn cael eu datrys yn barod, mae'n dim ond yn mynd i fynd â chi n camau i gadarnhau cymaint,

614
00:36:07,930 --> 00:36:10,870
tra fath dethol ydych weledigaeth twnnel ychydig yn fwy

615
00:36:10,870 --> 00:36:14,360
ac nad ydych byth yn sylweddoli bod y rhestr yn cael ei datrys eisoes.

616
00:36:14,360 --> 00:36:16,830
Felly, gadewch i ni weld math swigen ar waith yma.

617
00:36:16,830 --> 00:36:19,590
Yn yr enghraifft ganlynol, rydym chi ar fin i weld bariau fertigol

618
00:36:19,590 --> 00:36:23,030
y mae ei uchder yn cynrychioli rhifau fel y gallwn ddatrys o delweddu didoli digwydd.

619
00:36:23,030 --> 00:36:26,630
Po leiaf y bar, y lleiaf yw'r rhif, y mwyaf y bar, y mwyaf fydd y rhif.

620
00:36:26,630 --> 00:36:28,860
>> A byddwn yn ei chwarae yn y cyflymder ddiofyn.

621
00:36:28,860 --> 00:36:33,460
Mae'n mynd i symud yn gyflym ychydig ar hyn o bryd, ond mae coch yn beth sy'n dangos 2 far

622
00:36:33,460 --> 00:36:35,480
cael eu cymharu ochr yn ochr.

623
00:36:35,480 --> 00:36:39,520
Ac os ydych yn gwylio yn agos, beth fydd yn digwydd os bydd y bariau yn allan o drefn,

624
00:36:39,520 --> 00:36:42,300
yr un llai yn cael ei symud i'r chwith, yr un mwyaf i'r dde,

625
00:36:42,300 --> 00:36:44,360
ac yna eich bod yn cadw hyrwyddo.

626
00:36:44,360 --> 00:36:48,520
Felly, os ydym yn gwneud hyn dro ar ôl tro, yn sylwi bod y bariau lleiaf

627
00:36:48,520 --> 00:36:51,090
yn mynd i gadw inching eu ffordd i'r chwith

628
00:36:51,090 --> 00:36:54,130
a'r bariau mwyaf yn mynd i gadw inching eu ffordd i'r dde.

629
00:36:54,130 --> 00:36:58,490
Ac yn wir, rydym yn dechrau gweld patrwm yr holl ffordd ar yr ochr dde-law

630
00:36:58,490 --> 00:37:04,790
yn union fel rydym yn gweld 8 a yna 7 yn y pen draw yn byrlymu i fyny i ben pellaf ein rhestr dynol.

631
00:37:04,790 --> 00:37:08,750
Felly, mae hyn yn mynd i yn gyflym iawn cael braidd yn ddiflas, felly gadewch i mi roi'r gorau i hyn am eiliad.

632
00:37:08,750 --> 00:37:10,980
Gadewch i mi newid y cyflymder i fod yn llawer cyflymach.

633
00:37:10,980 --> 00:37:15,380
Dydw i ddim yn newid y algorithm, Im 'jyst yn gwneud y animeiddio yn digwydd yn gyflymach.

634
00:37:15,380 --> 00:37:18,410
Fath swigod Still, algorithm un,

635
00:37:18,410 --> 00:37:21,910
ond erbyn hyn gallwch weld llawer cyflymach na'r arddangos ar lafar

636
00:37:21,910 --> 00:37:25,900
bod yr elfennau mwyaf yn wir yn byrlymu i fyny i'r brig.

637
00:37:25,900 --> 00:37:29,860
>> Fel o'r neilltu, mae'r sgwariau bach yn y gwaelod ar y chwith a gwaelod dde

638
00:37:29,860 --> 00:37:33,520
yn unig atgoffa ychydig o ran faint o cymariaethau rydych chi'n ei wneud.

639
00:37:33,520 --> 00:37:37,620
Ond am nawr, gallwn ganolbwyntio ar y pyramid sydd wedi cymryd siâp, ac yno y mae'n mynd.

640
00:37:37,620 --> 00:37:41,510
Mae'r elfen lleiaf ar y chwith, y mwyaf ar y dde, a phopeth arall yn y canol.

641
00:37:41,510 --> 00:37:44,470
Nawr gadewch i ni yn hytrach yn edrych ar fath dethol.

642
00:37:44,470 --> 00:37:47,260
Rydw i'n mynd i fynd yn ei flaen a tharo Stop. Rydym yn mynd i gael set ar hap newydd o fariau.

643
00:37:47,260 --> 00:37:50,930
, Didoli Dewis galw i gof, yn mynd drwy'r rhestr eto ac eto ac eto,

644
00:37:50,930 --> 00:37:54,900
plicio allan yr elfen lleiaf. Felly dyma fath dethol.

645
00:37:54,900 --> 00:37:58,390
Mae'n edrych fel mae 'na llai o waith yn digwydd yn awr oherwydd nad ydym yn cymharu pairwise

646
00:37:58,390 --> 00:38:02,590
ond rydym yn unig didoli o geirios dewis yr elfennau lleiaf o'r dde i'r chwith.

647
00:38:02,590 --> 00:38:06,890
Hynny'n cymryd ychydig iawn o amser, felly mae deuoliaeth yn barod.

648
00:38:06,890 --> 00:38:11,820
Nid yw'r ffaith bod algorithm yn dweud i gymryd n amser sgwâr, fel math swigen

649
00:38:11,820 --> 00:38:16,100
ac fel math dethol, y rhai yn wir yn amseroedd gwaethaf rhedeg.

650
00:38:16,100 --> 00:38:21,790
Er enghraifft, yn achos, gadewch i ni ddweud, didoli dewis,

651
00:38:21,790 --> 00:38:27,240
Fi 'n weithredol mod yn dewis y person lleiaf a rhoi iddo ef neu hi yma,

652
00:38:27,240 --> 00:38:29,620
yna rwy'n ei wneud eto, yna rwy'n ei wneud eto,

653
00:38:29,620 --> 00:38:32,070
ond roedd optimization bach y gallwn i wneud.

654
00:38:32,070 --> 00:38:35,040
>> Cyn gynted ag y mi symud rhif 1 yma - Sammy yn yr achos hwnnw -

655
00:38:35,040 --> 00:38:38,630
beth oedd angen i mi ei wneud gydag ef ar ôl hynny? >> [Myfyrwyr] Gadewch iddo.

656
00:38:38,630 --> 00:38:40,140
Gadewch iddo, dde? Dim byd.

657
00:38:40,140 --> 00:38:44,310
Nid oedd rhaid i mi erioed siarad â Sammy eto oherwydd os wyf wedi dewis yr elfen lleiaf

658
00:38:44,310 --> 00:38:48,580
ac a'i rhoddodd ef yma, pam gwastraffu amser yn mynd i ddiwedd fy rhestr gyfan?

659
00:38:48,580 --> 00:38:54,590
Ar y fersiwn nesaf gadewch i mi mewn gwirionedd yn symud yn unig i rhif 2, dim ond i rif 3.

660
00:38:54,590 --> 00:38:57,640
Felly, mewn gwirionedd, nid oeddwn yn gwneud pethau n n amser.

661
00:38:57,640 --> 00:39:05,380
Mod yn gwneud pethau n, yna n - 1 pethau, yna n - 2 beth, yna n - 3 pheth,

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

663
00:39:07,080 --> 00:39:09,470
Mae gennym dipyn o gyfres geometrig, a dim ond yn golygu

664
00:39:09,470 --> 00:39:11,450
rydych yn adio rhifau yn gynyddol llai.

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

666
00:39:17,940 --> 00:39:21,380
A beth sy'n gyffredinol yn gweithio allan i fod -

667
00:39:21,380 --> 00:39:24,280
Rydw i'n mynd i llanast i fyny fy mwrdd yma am ychydig funudau'n -

668
00:39:24,280 --> 00:39:28,990
mae hynny'n mynd i weithio allan i fod yn rhywbeth fel n (n - 1) / 2

669
00:39:28,990 --> 00:39:31,930
os ydym yn unig fath o edrych yng nghefn y llyfr mathemateg lle mae gennych yr holl daflenni twyllo

670
00:39:31,930 --> 00:39:33,410
ar gyfer y fformiwlâu.

671
00:39:33,410 --> 00:39:37,760
Os ydych ond yn ychwanegu rhywbeth n + n - 1 + n - 2, mae'n gweithio allan i fod yn rhywbeth fel hyn.

672
00:39:37,760 --> 00:39:42,320
Ac os ydym yn unig fath o lluosi hyn, mae hynny'n n sgwâr minws n / 2.

673
00:39:42,320 --> 00:39:46,400
Yr wyf yn cadw ei ddweud n sgwâr, fodd bynnag, a dyna oherwydd fy mod yn fath o gymryd llwybr byr meddwl

674
00:39:46,400 --> 00:39:51,950
oherwydd mewn gwirionedd, n sgwâr minws n rhannu â 2 yn wir y gwir nifer o gamau

675
00:39:51,950 --> 00:39:55,510
y byddai algorithm fel math dewis cymryd os ydym yn wir yn cyfrif i fyny

676
00:39:55,510 --> 00:39:58,800
pob un o'r cymariaethau hynny a'r holl waith prysur bach oeddem yn ei wneud.

677
00:39:58,800 --> 00:40:03,210
Ond dweud y gwir, unwaith n cael i fod fel miliwn neu biliwn, pwy yw'r heck gofalu

678
00:40:03,210 --> 00:40:07,160
os ydych chi'n gwneud biliwn o minws sgwâr biliwn wedi'i rannu â 2?

679
00:40:07,160 --> 00:40:09,320
Mae biliwn sgwâr yn nifer enfawr.

680
00:40:09,320 --> 00:40:13,580
Gallwch gymryd arall biliwn oddi ar 'i ag - n. Nid yw'n mor bwysig â hynny.

681
00:40:13,580 --> 00:40:18,770
Felly, y mwyaf fydd y niferoedd yn cael, y llai pwysig y telerau hyn yn is trefnus yn cael eu.

682
00:40:18,770 --> 00:40:24,230
Pwy sy'n gofalu os ydych yn rhannu â 2 os ydych yn siarad am quadrillions nifer o gamau?

683
00:40:24,230 --> 00:40:29,710
>> Felly, yn gyffredinol, gwyddonwyr cyfrifiadurol yn tueddu i daflu i ffwrdd popeth ond y term mwyaf,

684
00:40:29,710 --> 00:40:33,140
ac rydym yn unig fath o symleiddio'r byd a dweud bod algorithm

685
00:40:33,140 --> 00:40:38,130
wedi cymryd camau bras n sgwâr. Dyna'r tro yn rhedeg o algorithm.

686
00:40:38,130 --> 00:40:40,760
Felly, byddwn yn dod yn ôl at hyn mewn dim ond hyn o bryd gyda rhai enghreifftiau pendant,

687
00:40:40,760 --> 00:40:45,940
ond ar hyn o bryd, mae hynny'n rhyw fath o gymhelliant sythweledol y tu ôl dim ond symleiddio ein byd

688
00:40:45,940 --> 00:40:51,170
a siarad am y termau mwyaf pwysig yn hytrach na mynd i mewn i hyn i gyd fformiwlâu ffansi.

689
00:40:51,170 --> 00:40:53,540
Felly roedd hynny'n fath dethol, ac rydym yn cael ychydig yn ffodus yno.

690
00:40:53,540 --> 00:40:57,360
Gadewch i ni edrych ar fath gosod. Gadewch i mi fynd yn ei flaen ac yn dechrau yr un yma yn ogystal.

691
00:40:57,360 --> 00:41:00,330
Nawr yn sylwi ar y patrwm sy'n digwydd ychydig yn wahanol,

692
00:41:00,330 --> 00:41:03,410
ac rydym yn dechrau gyda rhifau ar hap,

693
00:41:03,410 --> 00:41:06,890
ond os ydym mewn gwirionedd yn cyfrif y nifer o gamau yn yr achos gwaethaf,

694
00:41:06,890 --> 00:41:11,070
os bydd y rhestr ddechrau yn gyfan gwbl yn y drefn gywir,

695
00:41:11,070 --> 00:41:13,380
ni fyddem ond yn cymryd camau n i sylweddoli cymaint.

696
00:41:13,380 --> 00:41:18,240
>> Ond os bydd y rhestr oedd mewn gwirionedd yn ôl - er enghraifft, yn yr achos yma -

697
00:41:18,240 --> 00:41:23,860
yna sylwi ydym mewn gwirionedd yn rhaid i ni wneud llawer mwy o waith yn yr achos hwn.

698
00:41:23,860 --> 00:41:27,080
Ac fe ddylai fath o teimlo i chi fel yr un yma yn fath o weithio galetach

699
00:41:27,080 --> 00:41:30,900
i gael y elfennau llai ar y chwith, a dyna oherwydd ein bod yn cael anlwcus.

700
00:41:30,900 --> 00:41:34,210
Cafodd y rhestr ei datrys yn ddamweiniol o chwith.

701
00:41:34,210 --> 00:41:38,110
Ar y llaw arall, gyda math fewnosod os ydym yn dynwared yr hyn a wnaethom gyda'n pobl yma

702
00:41:38,110 --> 00:41:42,670
drwy ddechrau gyda phawb didoli ac yna'n dechrau, mae'n algorithm 'n bert da, dde?

703
00:41:42,670 --> 00:41:45,010
Mae'n eisoes, mewn gwirionedd, didoli.

704
00:41:45,010 --> 00:41:48,670
Felly, gadewch i ni geisio crynhoi yn union faint o amser y pethau hyn yn mynd â ni

705
00:41:48,670 --> 00:41:52,360
drwy gyflwyno dim ond ychydig o jargon neu nodiant sydd mewn gwirionedd yn llawer symlach

706
00:41:52,360 --> 00:41:54,320
na'r math o fanciness awgrymu.

707
00:41:54,320 --> 00:41:59,030
Mae hyn yn beth yma, mae hyn yn O fawr ar y sgrin, yn yr hyn y bydd yn wyddonydd cyfrifiadur fel arfer yn defnyddio

708
00:41:59,030 --> 00:42:03,640
i ddisgrifio yr amser yn rhedeg achos gwaethaf o algorithm.

709
00:42:03,640 --> 00:42:07,360
>> Unwaith eto, fesul achos gwaethaf, mae'n hollol cyd-destun-ddibynnol.

710
00:42:07,360 --> 00:42:10,890
Beth a olygwn wrth achos gwaethaf llwyr yn amrywio yn seiliedig ar y broblem, rydym yn sôn amdano.

711
00:42:10,890 --> 00:42:14,550
Ond yn yr achos didoli, beth yw'r sefyllfa waethaf posibl?

712
00:42:14,550 --> 00:42:17,860
Mae popeth yn ôl oherwydd mae'n teimlo fel bod yn golygu llawer o waith i ni.

713
00:42:17,860 --> 00:42:21,330
Rydw i wedi jotted i lawr rhai o'r algorithmau yr ydym wedi gweld hyd yn hyn:

714
00:42:21,330 --> 00:42:24,930
chwiliad llinol, chwiliad deuaidd fel y llyfr ffôn neu ddarnau o bapur,

715
00:42:24,930 --> 00:42:28,960
Yna, math swigen didoli dewis, a gosod didoli fel y gwelsom yn achos ein pobl,

716
00:42:28,960 --> 00:42:31,770
ac yna 1 arall sydd yn y pen draw yn mynd i gael eu galw uno fath.

717
00:42:31,770 --> 00:42:37,710
Felly, mewn chwiliad llinol yn yr achos gwaethaf, faint o gamau mae'n ei gymryd i ddod o hyd i'r rhif 7

718
00:42:37,710 --> 00:42:40,690
os oes drysau n fel Sean wynebu? >> [Myfyrwyr] N.

719
00:42:40,690 --> 00:42:44,180
N. Felly, rydym yn mynd i ysgrifennu mawr O o n.

720
00:42:44,180 --> 00:42:47,010
Im 'jyst yn mynd i chi lenwi rhai bylchau. Mae hyn yn unig yw grid o bylchau.

721
00:42:47,010 --> 00:42:52,990
Ond yn yr achos gorau gyda chwiliad llinol, efallai 7 wedi bod ar gychwyn cyntaf y rhestr,

722
00:42:52,990 --> 00:42:55,520
ac efallai y Sean wedi dechrau edrych ar ddechrau'r rhestr.

723
00:42:55,520 --> 00:42:58,940
Felly, os ydych yn defnyddio chwiliad llinol a dim ond gwirio chwith i'r dde neu efallai dde i'r chwith -

724
00:42:58,940 --> 00:43:02,650
eu bod yn gyfwerth - yn yr achos gorau faint o gamau y gallai chwiliad llinol,

725
00:43:02,650 --> 00:43:05,550
fel Sean algorithm, cymryd? Dim ond 1 cam.

726
00:43:05,550 --> 00:43:09,450
>> Felly, yr wyf i'n mynd i ddweud bod yn y nodiant omega.

727
00:43:09,450 --> 00:43:11,570
Mae hyn yn unig omega cyfalaf.

728
00:43:11,570 --> 00:43:15,000
Omega yn unig yw ffordd o ddweud sexy achos gorau yn rhedeg amser.

729
00:43:15,000 --> 00:43:18,900
Felly, yn yr achos gorau yr amser yn rhedeg yn gam un neu nifer cyson o gamau -

730
00:43:18,900 --> 00:43:24,270
1 mewn yr achos hwn - ond yn yr achos gwaethaf, mawr O, mae'n mewn gwirionedd camau n.

731
00:43:24,270 --> 00:43:28,110
Ac mae hyn un yma, theta, nid ydym yn wir yn mynd i edrych ar hyn o bryd.

732
00:43:28,110 --> 00:43:30,090
Nid yw'n berthnasol i'r enghraifft benodol.

733
00:43:30,090 --> 00:43:31,990
Ond yn awr, gadewch i ni geisio chwiliad deuaidd.

734
00:43:31,990 --> 00:43:35,990
Yn yr achos gwaethaf gyda chwiliad deuaidd, faint o gamau y mae'n mynd i'w cymryd i ddod o hyd i'r rhif 7

735
00:43:35,990 --> 00:43:38,340
neu beth bynnag yr ydym yn chwilio amdano? >> [Myfyrwyr] Log n.

736
00:43:38,340 --> 00:43:40,980
Dal yn mynd i gymryd n log oherwydd yn union fel Alex got anlwcus

737
00:43:40,980 --> 00:43:44,030
pan mae arnom wir yn gweithio trwy'r broblem yn drefnus

738
00:43:44,030 --> 00:43:48,220
ac nad oedd yn dod o hyd i'r rhif 7 tan y drws olaf mae hi'n edrych ar,

739
00:43:48,220 --> 00:43:51,720
hyd yn oed er, yn deg, mae hi'n mynd i daflu i ffwrdd drysau penodol ar hyd y ffordd,

740
00:43:51,720 --> 00:43:56,920
chwiliad deuaidd yn yr achos gwaethaf yn cael amser yn rhedeg o log n.

741
00:43:56,920 --> 00:43:59,230
Ac eto, sydd yn siarad i hyn rannu a goncro.

742
00:43:59,230 --> 00:44:01,140
Ond beth am yn yr achos gorau?

743
00:44:01,140 --> 00:44:04,790
Ac Alex mewn gwirionedd yn profi bod achos gorau iawn pan ddaeth hi i fyny ar y llwyfan.

744
00:44:04,790 --> 00:44:07,290
Faint o gamau a gymerodd hyn mewn chwiliad deuaidd? >> [Myfyrwyr] 1.

745
00:44:07,290 --> 00:44:09,380
1, dim ond oherwydd ei got 'n ffodus.

746
00:44:09,380 --> 00:44:12,520
Ond mae hynny'n iawn oherwydd omega yn cyfeirio at sefyllfaoedd achos gorau,

747
00:44:12,520 --> 00:44:15,770
mewnbynnau achos gorau, hyd yn oed os mai dim ond ar hap lwc fud.

748
00:44:15,770 --> 00:44:18,900
>> Yn awr, mae hyn hefyd rydym yn mynd i jyst fath o absenoldeb wag ar hyn o bryd.

749
00:44:18,900 --> 00:44:21,010
Fath swigod Beth am nawr?

750
00:44:21,010 --> 00:44:24,290
Yn yr achos gwaethaf gyda math swigen, mae pawb yn am yn ôl,

751
00:44:24,290 --> 00:44:26,380
felly mae'n rhaid i ni wneud llawer o byrlymu.

752
00:44:26,380 --> 00:44:30,190
Ond faint o gamau yw bod mynd i gymryd yn yr achos gwaethaf? >> [Myfyrwyr] N sgwâr.

753
00:44:30,190 --> 00:44:32,550
Hwn oedd y n sgwâr, oherwydd os ydych yn meddwl am y peth,

754
00:44:32,550 --> 00:44:36,410
os bydd y rhestr yn hollol yn ôl - 8 yn dros yma, mae 1 yn dros yma -

755
00:44:36,410 --> 00:44:40,530
fel peth ddechrau swigen, y rhif 8 yn mynd i symud y ffordd hon, y modd hwn,

756
00:44:40,530 --> 00:44:44,540
y ffordd hon, y modd hwn, ond ble mae'r rhif 7 yn yr achos gwaethaf?

757
00:44:44,540 --> 00:44:47,720
Dyma hi dal i fod dros yno. Felly, mae'n rhaid i ni wneud hynny eto ac eto.

758
00:44:47,720 --> 00:44:53,190
A dyna lle'r ydym yn cael gamau n, yna n - 1 gamau, yna n - 2 cam.

759
00:44:53,190 --> 00:44:55,960
Ac os byddwch yn cymryd fy ngair i am hynny - os ydych yn fath o luosi allan,

760
00:44:55,960 --> 00:45:00,110
mae'n n fras sgwâr yn y diwedd gyda rhai termau eraill y byddwn yn ei hanwybyddu ar hyn o bryd -

761
00:45:00,110 --> 00:45:06,890
Yna, yn y math swigen achos gwaethaf yn n sgwâr, rhoi neu gymryd.

762
00:45:06,890 --> 00:45:09,490
Ond beth am yr achos gorau gyda math swigen?

763
00:45:09,490 --> 00:45:13,050
Beth yw'r senario achos gorau? Mae pob un o'r rhifau yn cael eu datrys eisoes.

764
00:45:13,050 --> 00:45:15,920
A beth oedd y hewristig wyf yn ei ddefnyddio, y gamp wyf yn ei ddefnyddio,

765
00:45:15,920 --> 00:45:20,110
i sylweddoli fy mod wedi gwneud dim gwaith a allai felly roi taw ar gynnar?

766
00:45:20,110 --> 00:45:23,590
[Myfyrwyr] Edrychwch ar unwaith. Gwiriwch >> unwaith. Ond beth oedd yr wyf yn ei wneud ar hyd y ffordd?

767
00:45:23,590 --> 00:45:26,130
Roeddwn yn cadw golwg ar faint o gyfnewid a wneuthum.

768
00:45:26,130 --> 00:45:30,650
Ac yr wyf yn sylweddoli os nad wyf wedi cyfrif unrhyw cyfnewid ar fy mysedd, hynny, rwyf wedi gwneud dim gwaith.

769
00:45:30,650 --> 00:45:34,300
Rwy'n sicr na ddylai geisio gwneud dim gwaith eto, felly gallaf stopio.

770
00:45:34,300 --> 00:45:37,830
>> Felly, yn yr achos gorau o fath swigod pan oedd y rhestr yn cael ei datrys eisoes,

771
00:45:37,830 --> 00:45:41,530
beth fyddech chi'n dweud bod y nodiant omega yw, yr achos gorau yn rhedeg amser?

772
00:45:41,530 --> 00:45:48,040
Mae n unig. Mae'n rhaid i ni wneud rhywfaint o waith, ond dim ond rhaid i ni wneud werth 1 dro o waith.

773
00:45:48,040 --> 00:45:50,490
Ac yma hefyd rwy'n mynd i adael hwn yn wag rhan.

774
00:45:50,490 --> 00:45:52,430
Ac yn awr fath dethol.

775
00:45:52,430 --> 00:45:56,010
Dewis fath wedi i mi plicio y person lleiaf eto ac eto.

776
00:45:56,010 --> 00:45:58,380
A beth oedd yr ydym yn dweud yr amser yn rhedeg o hynny oedd?

777
00:45:58,380 --> 00:46:00,590
Dyna oedd n sgwario yn yr achos gwaethaf.

778
00:46:00,590 --> 00:46:05,220
Ac yn anffodus, yn yr achos gorau mae'n n hefyd yn sgwâr

779
00:46:05,220 --> 00:46:08,840
oherwydd nid wyf yn cael y math o olygfa omniscient y byd i gyd;

780
00:46:08,840 --> 00:46:13,140
Dim ond yn gwybod ar y fersiwn llawn fy mod wedi dod o hyd yn wir y person lleiaf.

781
00:46:13,140 --> 00:46:15,860
Felly, dewis math fath o sugno yn yr ystyr honno,

782
00:46:15,860 --> 00:46:17,920
ond yr ochr orau yw ei fod yn fath o 'n athrylithgar.

783
00:46:17,920 --> 00:46:21,470
Mae'n eithaf hawdd i cod i fyny gan fod yr holl rhaid i chi ei wneud yw ysgrifennu ychydig o nythu ar gyfer dolenni,

784
00:46:21,470 --> 00:46:24,620
fel arfer, sy'n mynd drwy edrych ar gyfer yr elfen lleiaf

785
00:46:24,620 --> 00:46:27,840
ac yna rhoi'r elfen lleiaf lle mae'n perthyn ar ddiwedd y rhestr.

786
00:46:27,840 --> 00:46:29,900
Felly, yma hefyd mae mynd i fod yn fasnach-off.

787
00:46:29,900 --> 00:46:34,440
Mae faint o amser mae'n ei gymryd i chi i feddwl ac i ddatblygu rhywbeth mewn gwirionedd drwy ysgrifennu cod

788
00:46:34,440 --> 00:46:39,460
Gallai yn dda iawn yn cymryd mwy o amser os ydych am gael perfformiad gwell algorithm ac yn gyflymach.

789
00:46:39,460 --> 00:46:41,780
>> Ond os ydych yn wir yn unig fath o rywbeth cod i fyny yn gyflym ac yn fudr

790
00:46:41,780 --> 00:46:45,000
a dim ond math o gymryd y syniad stupidest posibl y gallwch feddwl,

791
00:46:45,000 --> 00:46:47,580
a allai fynd â chi ychydig o funudau i cod, ond gyda setiau data mawr

792
00:46:47,580 --> 00:46:49,580
gallai eich algorithm yn cymryd awr a hanner.

793
00:46:49,580 --> 00:46:51,690
A byddai hyd yn oed yr wyf yn yr ysgol i raddedigion weithiau yn gwneud y cyfaddawdau hyn.

794
00:46:51,690 --> 00:46:55,660
Byddai'n 3am, yr oeddwn yn ceisio dadansoddi rhai set ddata fawr iawn

795
00:46:55,660 --> 00:46:59,650
gysylltiedig â'r ymchwil diogelwch oeddwn yn ei wneud, ac yr oedd naill ai yn treulio 5 munud

796
00:46:59,650 --> 00:47:03,210
tweaking fy rhaglen i ddadansoddi'r data a mynd i gysgu

797
00:47:03,210 --> 00:47:08,420
neu dreulio 8 awr yn cael y peth yn iawn fel ei fod yn rhedeg yn syth a pheidio â mynd i gysgu.

798
00:47:08,420 --> 00:47:10,530
Ac felly yno hefyd mae'n fath o benderfyniad ymwybodol.

799
00:47:10,530 --> 00:47:12,740
Llai o amser datblygu, mwy o gwsg.

800
00:47:12,740 --> 00:47:14,780
Wrth edrych yn ôl, yr wyf debyg na ddylai annog y

801
00:47:14,780 --> 00:47:19,120
pan fydd y nod yma yw gwneud y gorau ansawdd y cod,

802
00:47:19,120 --> 00:47:21,280
ond hefyd yn y byd go iawn yn rhesymol iawn fasnach-off.

803
00:47:21,280 --> 00:47:25,130
Llai o amser, perfformiad llai neu i'r gwrthwyneb.

804
00:47:25,130 --> 00:47:28,110
Felly dyma ni o'r diwedd yn cael y cyfle i siarad am theta.

805
00:47:28,110 --> 00:47:32,830
Theta nodiant yn rhywbeth y gall gwyddonwyr cyfrifiadurol yn dod i fyny mewn sgwrs

806
00:47:32,830 --> 00:47:36,160
pan fydd fawr O ac omega yn digwydd bod yr un fath.

807
00:47:36,160 --> 00:47:40,160
Rydych yn dweud theta i wir anfon y neges bod hwn yn fath o rhwymo dynn.

808
00:47:40,160 --> 00:47:43,340
Ni waeth a yw'r senario yn dda neu'n ddrwg, mae'n n sgwâr.

809
00:47:43,340 --> 00:47:46,510
Felly, nid dim ond yn berthnasol yn y straeon yma.

810
00:47:46,510 --> 00:47:48,560
Mewnosod fath yw'r un olaf buom yn edrych ar,

811
00:47:48,560 --> 00:47:50,830
lle yr oeddwn yn gosod pawb i mewn i'r lle iawn.

812
00:47:50,830 --> 00:47:54,930
Yn yr achos gorau beth oedd yr amser yn rhedeg o fath fewnosod fel y gwelsom yma?

813
00:47:54,930 --> 00:47:57,250
[Myfyrwyr] Yr achos gorau? >> Yr achos gorau.

814
00:47:57,250 --> 00:48:00,100
>> Fe'i n oherwydd yn yr achos gorau pawb didoli,

815
00:48:00,100 --> 00:48:02,580
a Sammy a neb arall mewn gwirionedd wedi gorfod symud o gwbl.

816
00:48:02,580 --> 00:48:04,610
Roeddent eisoes yn eu lle cywir.

817
00:48:04,610 --> 00:48:08,570
Fath gosod Felly, yn yr achos gorau yw, yn yr achos hwn, n.

818
00:48:08,570 --> 00:48:12,770
Ond yn yr achos gwaethaf mae'n fath o n sgwâr. Pam?

819
00:48:12,770 --> 00:48:16,230
Os yw fy rhestr o bobl mewn cyflwr cefn,

820
00:48:16,230 --> 00:48:21,260
Tro cyntaf i mi dechrau gyda'r rhif 8 ac rwy'n rhowch ef neu hi i mewn i'r safle cywir, sydd ar gael yma.

821
00:48:21,260 --> 00:48:25,270
Yr wyf yn fath o symudiad ar yr ochr. Mae'r rhain guys yn cael eu heb eu didoli, ef neu hi ei drefnu.

822
00:48:25,270 --> 00:48:28,970
Ond yn awr yr wyf yn digwydd i ddod o hyd pwy nesaf? >> [Myfyrwyr] 7.

823
00:48:28,970 --> 00:48:31,250
7 yn yr achos gwaethaf oherwydd ei fod yn ôl.

824
00:48:31,250 --> 00:48:34,920
>> Felly dyma yw 7. Ble mae 7 yn perthyn? Yn bendant tu ôl i mi.

825
00:48:34,920 --> 00:48:39,460
Ond yn awr 7 Nid mewn gwirionedd yn perthyn union y tu ôl i mi, ond y tu ôl i rif 8,

826
00:48:39,460 --> 00:48:41,880
felly rhaid i mi ddweud, "Esgusodwch fi, rhif 8, a fyddech cystal symud y ffordd hon

827
00:48:41,880 --> 00:48:44,640
"I wneud lle ar gyfer 7?" Nawr rwy'n dod ar draws 6.

828
00:48:44,640 --> 00:48:48,530
"O, esgus i mi, rhif 8 a rhif 7 yn gallu, byddwch yn symud i wneud lle i 6?"

829
00:48:48,530 --> 00:48:52,360
Felly, mewn geiriau eraill, gyda math mewnosod, er nad wyf yn gwneud llawer o symud,

830
00:48:52,360 --> 00:48:56,330
bobl y tu ôl i mi yn gwneud llawer mwy o waith, ac mae'n rhaid bod cost amser rhywun.

831
00:48:56,330 --> 00:48:58,000
Mae'n mynd i gostio amser cyfrifiadur.

832
00:48:58,000 --> 00:49:01,450
Felly, yn achos math mewnosod rydym yn dal i ddioddef.

833
00:49:01,450 --> 00:49:06,260
Os ydych yn dechrau ychwanegu i fyny 'r cyfanswm nifer o gamau, rydym yn y pen draw taro fras n sgwâr

834
00:49:06,260 --> 00:49:11,160
oherwydd bod y rhain guys angen i wneud lle am y dynol i'w fewnosod yn ôl i mewn i'r rhestr.

835
00:49:11,160 --> 00:49:15,960
Ac felly yn yr achos hwn theta nid yn unig yn berthnasol i'r stori arbennig wrth law.

836
00:49:15,960 --> 00:49:21,100
Thats 'pawb' n glws ac yn dda. Mae gennym ffyrdd hyn 3 gwahanol o siarad am yr amser yn rhedeg.

837
00:49:21,100 --> 00:49:26,370
Ond beth mae hyn yn ei olygu mewn termau go iawn os ydym mewn gwirionedd yn ceisio cod sefydlu algorithm?

838
00:49:26,370 --> 00:49:31,620
>> Gadewch i mi yn cynnig y mae 'na hyd yn oed yn well algorithm i maes' na

839
00:49:31,620 --> 00:49:33,740
bod ei hun rhywfaint o fasnach-offs.

840
00:49:33,740 --> 00:49:36,890
Rydym yn mynd i alw yn uno fath, ac mae'n fath o algorithm hwn yn hudol

841
00:49:36,890 --> 00:49:42,840
mai dim ond yn gweithio yn gyflymach rhywsut, ac mae mor hawdd i fynegi, o leiaf yn pseudocode.

842
00:49:42,840 --> 00:49:46,900
Mae gweithrediad y uno algorithm fath yn mynd i fod fel a ganlyn.

843
00:49:46,900 --> 00:49:50,860
Pan fyddwch chi'n rhoi n elfennau - rhifau n, n pobl, beth bynnag - yn gyntaf mae 'na gwiriad bwyll.

844
00:49:50,860 --> 00:49:56,340
Os n yn llai na 2, uno fath dim ond yn dod i ben. Mae'n dychwelyd, felly, i siarad.

845
00:49:56,340 --> 00:50:00,830
Pam y byddech yn dod i ben os n yn llai na 2? >> [Anghlywadwy ymateb y myfyrwyr]

846
00:50:00,830 --> 00:50:04,480
Hawl. Ac eto, nid yw n yw rhif yn y rhestr, n yw maint y rhestr.

847
00:50:04,480 --> 00:50:07,660
Os n yn llai na 2, mae hynny'n golygu eich rhestr naill ai 1,

848
00:50:07,660 --> 00:50:09,640
lle rydych chi'n trefnu yn amlwg os yw'n 1 rhif,

849
00:50:09,640 --> 00:50:11,710
neu 0, ac os felly does dim byd i drefnu,

850
00:50:11,710 --> 00:50:13,570
felly mae angen y math hwn o achos sylfaenol.

851
00:50:13,570 --> 00:50:20,350
Os yw'r rhestr mor fyr nad oes dim ond dim byd i wneud, nid yn llythrennol yn gwneud unrhyw beth. Dychwelyd.

852
00:50:20,350 --> 00:50:25,090
Fel arall ddatrys hanner chwith y elfennau, ac yna ddatrys yr hanner dde yr elfennau,

853
00:50:25,090 --> 00:50:27,410
yna cyfuno'r 2 hanner didoli.

854
00:50:27,410 --> 00:50:32,130
>> Mae'r math hwn o ymddangos fel twyllo ychydig o lle rwy'n gofyn i chi sut i roi trefn ar elfennau

855
00:50:32,130 --> 00:50:34,900
ac rydych yn dweud wrthyf, "Trefnwch yr hanner chwith, didoli yr hanner cywir."

856
00:50:34,900 --> 00:50:37,240
Rydw i'n hoffi, "Mae pob hawl. Sut ydych chi'n datrys yr hanner chwith?"

857
00:50:37,240 --> 00:50:40,670
"Trefnwch y hanner chwith yr hanner chwith, didoli hanner dde yr hanner chwith, ac yna ei wneud."

858
00:50:40,670 --> 00:50:44,060
Rydych yn fath o gylchol diffinio beth mae'n ei olygu i drefnu,

859
00:50:44,060 --> 00:50:46,790
ond mae'n troi allan bod mewn gwirionedd wych yn yr achos hwn.

860
00:50:46,790 --> 00:50:50,230
Nid yw'n wir y cylch dieflig nad yw byth yn dod i ben

861
00:50:50,230 --> 00:50:52,550
oherwydd ei fod yn dod i ben pryd? >> [Myfyrwyr] Pan fyddwch yn cyrraedd 1 peth.

862
00:50:52,550 --> 00:50:54,220
Pan fyddwch yn cyrraedd 1 peth.

863
00:50:54,220 --> 00:50:57,850
Felly, hyd yn oed er efallai y byddwch yn dechrau gydag 8 o bobl ac yr wyf yn dweud, "Trefnwch y hanner chwith o'r bobl hyn,

864
00:50:57,850 --> 00:51:00,480
y 4 o bobl, "yna yr wyf yn dweud," Sut ydych chi'n datrys yr hanner chwith? "

865
00:51:00,480 --> 00:51:03,450
"Wel, didoli'r 2 o bobl yma." Ac yna ydych chi fel, "Mae pob hawl, dirwy."

866
00:51:03,450 --> 00:51:05,520
"Sut ydych chi'n datrys hanner chwith bobl hynny?"

867
00:51:05,520 --> 00:51:09,040
"Dim ond ddatrys hyn person 1 yma." Beth yw'r datguddiad wych nawr?

868
00:51:09,040 --> 00:51:13,050
Rhaid i mi ddatrys 1 person. Done. Nid oes gennyf i wneud unrhyw waith.

869
00:51:13,050 --> 00:51:16,580
Ond yn awr rhaid i mi ddatrys y person hwn, ond maent chi'n berson sengl, dim byd i'w wneud.

870
00:51:16,580 --> 00:51:21,490
>> Felly, y mae'n debyg hud a lledrith sydd yn y trydydd cam: uno yr haneri didoli.

871
00:51:21,490 --> 00:51:25,770
Fath Felly uno yn cymryd y mewnwelediad gwych, os byddwch yn torri yn broblem fawr i lawr

872
00:51:25,770 --> 00:51:28,650
yn 2 llai, yn union-maint problemau

873
00:51:28,650 --> 00:51:32,710
ac yna dim ond math o lud atebion llai at ei gilydd ar y diwedd,

874
00:51:32,710 --> 00:51:34,720
Yr wyf yn cynnig y gallwn wneud llawer, [sain tapio] llawer gwell

875
00:51:34,720 --> 00:51:38,050
nag unrhyw fath o ddethol neu'n didoli gosod.

876
00:51:38,050 --> 00:51:40,690
Rwyf wedi gwirionedd bod yn anwybyddu hynny am hanner awr, ond i ddim wir yn gwybod beth sy'n mynd ymlaen

877
00:51:40,690 --> 00:51:45,040
y tu allan heddiw. [Sain whirring] [chwerthin]

878
00:51:45,040 --> 00:51:49,660
Felly, gadewch i ni weld os allwn ni weld hyn gydag ychydig o help gan ein ffrind Rob Bowden.

879
00:51:49,660 --> 00:51:52,810
Mae 2 cam mawr yn y broses o uno fath.

880
00:51:52,810 --> 00:51:56,400
Yn gyntaf, yn barhaus rhannu rhestr o gwpanau mewn i haneri

881
00:51:56,400 --> 00:51:59,610
nes bydd gennym griw o restrau gyda dim ond 1 cwpan ynddynt.

882
00:51:59,610 --> 00:52:02,150
Peidiwch â phoeni os bydd rhestr yn cynnwys odrif

883
00:52:02,150 --> 00:52:04,830
ac ni allwch wneud toriad yn berffaith lân rhyngddynt.

884
00:52:04,830 --> 00:52:08,740
Dim ond fympwyol ddewis pa rhestr i gynnwys y cwpan ychwanegol i mewn

885
00:52:08,740 --> 00:52:11,320
Felly, gadewch i ni rannu'r rhestrau hyn.

886
00:52:12,420 --> 00:52:14,570
Nawr rydym yn cael 2 rhestrau.

887
00:52:18,930 --> 00:52:20,930
Nawr rydym wedi 4 rhestrau.

888
00:52:25,730 --> 00:52:28,740
Nawr mae gennym 8 rhestri gyda phaned un ym mhob rhestr.

889
00:52:28,740 --> 00:52:31,520
Felly dyna ni ar gyfer cam 1.

890
00:52:31,520 --> 00:52:37,280
Am cam 2, rydym dro ar ôl tro uno parau o restrau defnyddio'r algorithm uno a ddysgwyd o'r blaen.

891
00:52:37,280 --> 00:52:44,320
Cyfuno 108 a 15 yn y pen i fyny â'r rhestr 15, 108.

892
00:52:45,240 --> 00:52:51,330
Cyfuno 50 a 4, yn y pen draw gyda 4, 50.

893
00:52:51,330 --> 00:52:56,950
Cyfuno 8 a 42 rydym yn darfod i fyny ag 8, 42.

894
00:52:57,790 --> 00:53:04,360
Ac uno 23 a 16 yn y pen draw 16, 23.

895
00:53:04,360 --> 00:53:08,030
Nawr ein holl restrau o faint 2.

896
00:53:08,030 --> 00:53:10,980
Sylwch fod pob un o'r 4 rhestrau yn cael ei datrys,

897
00:53:10,980 --> 00:53:14,230
fel y gallwn ddechrau cyfuno parau o restrau eto.

898
00:53:14,230 --> 00:53:22,150
Cyfuno 15 a 108 a 4 a 50 yn gyntaf yn cymryd y 4, yna bydd y 15,

899
00:53:22,150 --> 00:53:26,250
yna y 50, yna bydd y 108.

900
00:53:26,250 --> 00:53:33,020
Cyfuno 8, 42 a 16, 23 i ni yn gyntaf gymryd y 8, yna yr 16,

901
00:53:33,020 --> 00:53:37,170
yna y 23, ac yna 42.

902
00:53:37,170 --> 00:53:42,490
Felly, nawr rydym wedi dim ond 2 restr o faint 4, pob un ohonynt yn cael ei ddidoli.

903
00:53:42,490 --> 00:53:45,940
Felly, nawr rydym cyfuno'r 2 restr.

904
00:53:45,940 --> 00:53:54,230
Yn gyntaf rydym yn cymryd y 4, yna rydym yn cymryd y 8, yna rydym yn cymryd y 15

905
00:53:54,230 --> 00:54:05,280
a 16 a 23 a 42 a 50 a 108.

906
00:54:05,280 --> 00:54:09,020
Ac rydym ni'n ei wneud. Erbyn hyn mae gennym restr datrys.

907
00:54:09,020 --> 00:54:13,740
>> Rob yn fath o gymryd mantais o rywbeth nad ydym wedi gwneud hynny eto.

908
00:54:13,740 --> 00:54:16,540
Awgrymwyd, ond doedden ni ddim yn gwneud hynny mewn gwirionedd.

909
00:54:16,540 --> 00:54:19,230
Roedd yn gwneud rhywbeth yn gorfforol gyda'r cwpanau sy'n awgrymu

910
00:54:19,230 --> 00:54:23,680
ei fod yn treulio rhywfaint o adnoddau ar wahân amser. >> [Myfyrwyr] Space. >> Roedd gofod.

911
00:54:23,680 --> 00:54:27,360
Mae'r ffaith ei fod yn cael y math hwn o bi-lefel tabl lle y cafodd le i fyny yma

912
00:54:27,360 --> 00:54:31,960
a gofod i lawr yma oedd mewn gwirionedd yn awgrymu ei fod wedi defnyddio gofod ddwywaith cymaint

913
00:54:31,960 --> 00:54:36,390
ag unrhyw un o'n algorithmau hyd yn hyn -, math mewnosod fath swigen, neu ddewis math -

914
00:54:36,390 --> 00:54:40,780
ond yr oedd yn ddylanwad busnes y gofod ychwanegol i fath o bethau symud yn ôl ac ymlaen

915
00:54:40,780 --> 00:54:42,600
tra'n cadw pethau mewn trefn.

916
00:54:42,600 --> 00:54:47,540
A hyd yn oed er ei fod yn teimlo fel ni gyrraedd at restr datrys, a oedd yn teimlo fel ei fod yn cymryd amser.

917
00:54:47,540 --> 00:54:51,060
Mewn gwirionedd, yr hyn Rob yn ei wneud yn union y algorithm.

918
00:54:51,060 --> 00:54:56,780
Yn gyntaf yn cymryd y broblem o n maint, wedi'i rannu i mewn i hanner chwith a hanner i'r dde.

919
00:54:56,780 --> 00:54:59,380
Dyna pryd y symudodd y cwpanau. Yna mae'n ailadrodd y broses honno.

920
00:54:59,380 --> 00:55:03,390
Mae'n rhannu 4 i 2 set o 2 dros yma a dros yma.

921
00:55:03,390 --> 00:55:08,520
Yna mae'n ailadrodd y broses honno ac yn rhannu 2 i 2 set o 1 ar gyfer pob un o'r cwpanau gwahanol.

922
00:55:08,520 --> 00:55:11,000
A dyna lle y cyfle gwych yn codi.

923
00:55:11,000 --> 00:55:15,840
Ar yr adeg honno yn y stori, roedd Rob 8 rhestrau o faint 1,

924
00:55:15,840 --> 00:55:18,860
pob un ohonynt eu datrys eisoes.

925
00:55:18,860 --> 00:55:20,630
>> Felly, yna beth oedd yn mynd ati i wneud?

926
00:55:20,630 --> 00:55:25,260
Pairwise cymerodd y rhestr hon didoli ac mae'r rhestr hon didoli a'u cyfuno nhw.

927
00:55:25,260 --> 00:55:28,200
Yna cymerodd yr un yma a'u cyfuno nhw, yna mae hyn yn un a cyfuno nhw,

928
00:55:28,200 --> 00:55:30,670
yna mae hyn un a unodd nhw.

929
00:55:30,670 --> 00:55:32,390
Ac yna beth wnaeth e ei wneud nesaf?

930
00:55:32,390 --> 00:55:36,580
Yna ail-uno y rhestrau yn fwy ac yna ail-uno y rhestrau yn fwy.

931
00:55:36,580 --> 00:55:41,170
Ac os ydych yn meddwl am hyn yn unig yn reddfol am y tro, beth oedd yn ei wneud mewn gwirionedd?

932
00:55:41,170 --> 00:55:45,450
Roedd yn rhannu'r broblem yn ei hanner, yn ei hanner, yn ei hanner, yn hanner

933
00:55:45,450 --> 00:55:47,600
er mwyn cael y rhestri hyn super bach.

934
00:55:47,600 --> 00:55:51,290
Yna efe a oedd yn fath o gyfuno dwbl, dwbl, dwbl, dwbl.

935
00:55:51,290 --> 00:55:54,120
Felly roedd yn gwneud dwywaith cymaint o waith ag yr ydym wedi gweld hyd yn hyn

936
00:55:54,120 --> 00:55:56,930
gydag unrhyw beth sy'n ymwneud â rhannu a gorchfygu, ond dim llawer mawr.

937
00:55:56,930 --> 00:55:59,630
Nad yw gwaith dwywaith cymaint yn mor bwysig â hynny. Dim ond yn ffactor cyson.

938
00:55:59,630 --> 00:56:03,920
A llawer fel ein mynegiant rhifyddeg o'r blaen, Im 'jyst yn mynd i groesi allan ffactorau cyson

939
00:56:03,920 --> 00:56:10,170
fel amser 2. Pwy sy'n poeni? Os yw'n 2 biliynau amser 2, mae hynny'n dal i fod llawer o gamau.

940
00:56:10,170 --> 00:56:13,160
Felly y cam hwn uno yn ymddangos i fod yn mewnwelediad allweddol.

941
00:56:13,160 --> 00:56:17,000
Gadewch i ni gerdded drwy hyn yn union niferoedd o'r blaen - O, nid yw hynny'n cael ei barhau eto.

942
00:56:17,000 --> 00:56:22,890
Gadewch i ni gerdded drwy hyn rhifol yn unig i mewn gwirionedd yn gweld sut mae hyn yn chwarae allan.

943
00:56:22,890 --> 00:56:25,940
Mae hyn yn bennaf yn unig animeiddio dyn tlawd bach.

944
00:56:25,940 --> 00:56:27,750
Gadewch i ni gynnig hyn.

945
00:56:27,750 --> 00:56:31,480
Mae'r amser yn rhedeg o uno fath - ni jyst angen ffordd o siarad am hyn.

946
00:56:31,480 --> 00:56:34,380
Nid yw hyn yn mathemateg, mae hyn yn unig fath o ffordd gryno o fynegi ein hunain.

947
00:56:34,380 --> 00:56:39,080
Felly T yn cynrychioli amser ac n yn cynrychioli beth? >> [Myfyrwyr] Mae maint y -

948
00:56:39,080 --> 00:56:41,400
>> [Malan] Mae maint y broblem, mae nifer o bobl.

949
00:56:41,400 --> 00:56:45,470
Felly rwy'n hawlio bod yr amser yn rhedeg i ddidoli pobl n yn mynd i fod yn 0 faint o amser

950
00:56:45,470 --> 00:56:50,290
os yw n yn llai na 2, oherwydd os ydych wedi 1 cwpan neu ddim cwpanau, oes gennych ddim i'w ddatrys.

951
00:56:50,290 --> 00:56:55,160
Ond yn fwy cyffredinol, yr wyf i'n mynd i gynnig bod yr amser yn rhedeg i ddatrys elfennau n

952
00:56:55,160 --> 00:56:59,350
yn mynd i fod yr amser mae'n ei gymryd i ddatrys yr hanner chwith plws hanner cywir

953
00:56:59,350 --> 00:57:03,110
plus - beth ydyn nhw ychwanegol + n? >> [Myfyrwyr] fath Cyfuno.

954
00:57:03,110 --> 00:57:07,260
[Malan] Mae'n mewn gwirionedd yn uno, oherwydd os oes gennych n / 2 elfen yma

955
00:57:07,260 --> 00:57:11,500
ac mae gennych n / 2 elfen yma, faint o amser mae'n ei gymryd i uno nhw?

956
00:57:11,500 --> 00:57:15,050
Yn union fel Rob, rhaid i chi tyn hwn dros yma, efallai tyn dros yma,

957
00:57:15,050 --> 00:57:17,120
tyn dros yma, tyn dros yma, tyn dros yma.

958
00:57:17,120 --> 00:57:19,400
Mae'n rhaid i chi gyffwrdd pob un o'r cwpanau unwaith.

959
00:57:19,400 --> 00:57:22,030
Ac os oes 4 cwpan a 4 cwpan, sef 8 cwpan

960
00:57:22,030 --> 00:57:25,200
neu, yn fwy cyffredinol, 8 cwpan n.

961
00:57:25,200 --> 00:57:28,470
Felly, y cam uno gallwn fynegi fel n,

962
00:57:28,470 --> 00:57:31,330
a bod yn llythrennol yn golygu y nifer o weithiau Rob cyffwrdd yn gorfforol

963
00:57:31,330 --> 00:57:33,410
un o'r rhai cwpanau Styrofoam.

964
00:57:33,410 --> 00:57:35,850
Felly, gadewch i ni ei wneud yn awr yn enghraifft mympwyol.

965
00:57:35,850 --> 00:57:41,850
Os oes 16 cwpanau, beth yw'r amser rhedeg didoli, gan ddefnyddio Rob algorithm, 16 cwpanau?

966
00:57:41,850 --> 00:57:44,710
Mae'n 2 gwaith y swm o amser mae'n ei gymryd i ddatrys 8 cwpan

967
00:57:44,710 --> 00:57:46,920
oherwydd mae gennym 8 cwpan yma, 8 cwpan yma.

968
00:57:46,920 --> 00:57:51,520
Nid wyf yn gwybod pa mor hir sy'n cymryd, felly rydym yn generalizing fel T am y tro.

969
00:57:51,520 --> 00:57:53,320
Pwy a ŵyr beth yw e?

970
00:57:53,320 --> 00:57:58,990
Ond yn awr y gallaf ddidoli o recursively neu dro ar ôl tro yn gofyn yr un cwestiwn.

971
00:57:58,990 --> 00:58:01,920
Faint o amser mae'n ei gymryd i ddatrys 8 cwpan?

972
00:58:01,920 --> 00:58:07,030
8 cwpan yr wyf i'n mynd i ddweud yn cymryd yr amser mae'n ei gymryd i ddatrys 4 cwpan a 4 cwpan,

973
00:58:07,030 --> 00:58:08,880
yna gyfuno nhw at ei gilydd.

974
00:58:08,880 --> 00:58:13,080
Fine. Rydym yn mynd i mewn i gylch eisoes. Pa mor hir mae'n ei gymryd i ddatrys 4 cwpan?

975
00:58:13,080 --> 00:58:19,150
Mae'r amser mae'n ei gymryd i ddatrys 4 cwpan cwpan yw 2 plws 2 cwpanau didoli yn ogystal â'r broses uno.

976
00:58:19,150 --> 00:58:21,440
Fine. Pa mor hir mae'n ei gymryd i ddatrys 2 cwpan?

977
00:58:21,440 --> 00:58:26,290
2 gwpanaid yw faint o amser mae'n ei gymryd i ddatrys 1 cwpan yn ogystal â'r amser mae'n ei gymryd i ddatrys arall cwpan

978
00:58:26,290 --> 00:58:29,040
yn ogystal â faint o amser mae'n ei gymryd i uno, sef dim ond 2.

979
00:58:29,040 --> 00:58:33,340
>> Fine. Cwestiwn olaf. Pa mor hir mae'n ei gymryd i ddatrys 1 cwpan?

980
00:58:33,340 --> 00:58:37,260
Dyma yr achos sylfaenol yr ydym yn rhagweld byddem yn cyrraedd yn gynharach.

981
00:58:37,260 --> 00:58:42,250
Mae'r ffaith ei bod yn cymryd dim gwaith o gwbl i ddatrys y lleiaf o'r problemau

982
00:58:42,250 --> 00:58:44,120
yn golygu bod yn awr, math o arddull ysgol radd,

983
00:58:44,120 --> 00:58:46,460
gallwn fynd dechrau llenwi rhifau hyn yn ôl i mewn

984
00:58:46,460 --> 00:58:50,630
Rydym bellach yn gwybod pa T o 1 yw, fel y gallaf plwg yn 0 ar gyfer T o 1.

985
00:58:50,630 --> 00:58:54,420
Bydd hynny'n rhoi 'm' r ateb i T o 2, yr wyf yn gall wedyn plwg yn uwch i fyny.

986
00:58:54,420 --> 00:58:56,930
Bydd hynny'n rhoi i mi T o 4, y gallaf plwg yn uwch i fyny.

987
00:58:56,930 --> 00:58:58,920
Bydd hynny'n rhoi i mi T o 8, a gallaf plwg yn uwch i fyny.

988
00:58:58,920 --> 00:59:04,330
Ac os wyf mewn gwirionedd yn gwneud allan y math drwy plygio i mewn atebion hyn,

989
00:59:04,330 --> 00:59:08,590
Byddaf wedyn yn cael T o 16 yn 64.

990
00:59:08,590 --> 00:59:12,090
A beth mae 64 ei gynrychioli?

991
00:59:12,090 --> 00:59:15,700
Os T yn 16, yeah, mae'n 16 gwaith 4.

992
00:59:15,700 --> 00:59:20,120
Felly yr wyf yn honni yn awr bod yr amser yn rhedeg y peth hyn a elwir yn uno fath -

993
00:59:20,120 --> 00:59:22,590
ac mae hyn yn mynd i fod yn fanciest y rhai yr ydym wedi ei weld hyd yn hyn -

994
00:59:22,590 --> 00:59:26,160
yn mynd i gael ei alw n log n

995
00:59:26,160 --> 00:59:31,140
oherwydd gall sawl gwaith Rob rhannu criw cyfan o gwpanau yn eu hanner? Mewngofnodi n.

996
00:59:31,140 --> 00:59:34,370
Mae yr un fath ag y llyfr ffôn enghraifft, mae'n yr un fath ag yr enghraifft hunan-gyfrif.

997
00:59:34,370 --> 00:59:36,380
>> Sawl gwaith yr ydych yn rhannu rhywbeth yn ei hanner?

998
00:59:36,380 --> 00:59:38,410
Fodd bynnag, mae hyn yn gam uno.

999
00:59:38,410 --> 00:59:42,920
Efallai y bydd rhaid i chi rannu'r cwpanau i mewn i hanner eto ac eto ac eto,

1000
00:59:42,920 --> 00:59:45,640
ond bob tro y byddwch chi'n mynd i gael i uno.

1001
00:59:45,640 --> 00:59:48,270
Ac rydym yn dweud yn gynharach mai uno cwpanau n cymryd camau n

1002
00:59:48,270 --> 00:59:52,060
oherwydd bod yn rhaid i chi dynnaf cwpan rwystra, tyn allan cwpan, ac mae'n rhaid i chi gyffwrdd pob cwpan unwaith,

1003
00:59:52,060 --> 00:59:53,510
yn union fel y gwnaeth Rob.

1004
00:59:53,510 --> 00:59:59,430
Felly, os ydym yn gwneud rhywbeth log n gwaith ac rydym yn gwneud pethau n ar bob un o'r iteriadau,

1005
00:59:59,430 --> 01:00:03,090
pob un o'r halvings, rydym wedi n amser log n.

1006
01:00:03,090 --> 01:00:07,220
Felly, os gallwn gau mewn 16 yn yr enghraifft hon, 16 gwaith log o 16 -

1007
01:00:07,220 --> 01:00:10,600
peidiwch â phoeni ynghylch pam mae hyn yn wir ar hyn o bryd gan nad wyf wedi tynnu y sylfaen -

1008
01:00:10,600 --> 01:00:16,100
ond cofnod o sylfaen 2 o 16 yw 4, 16 gwaith 4 yn 64.

1009
01:00:16,100 --> 01:00:22,350
Ond ar y llaw arall, pe baem wedi defnyddio math swigod neu ddewis didoli neu fewnosod fath gyda 16 rhifau,

1010
01:00:22,350 --> 01:00:26,420
beth fyddai yr amser yn rhedeg wedi bod pe n yn 16 oed?

1011
01:00:26,420 --> 01:00:33,310
Byddai'n fod yn 16 sgwâr, sef 256, a hyd yn oed os nad ydych wedi dilyn yn eithaf yr holl math,

1012
01:00:33,310 --> 01:00:38,390
256 yn fwy na 64. Hynny'n wir yn y lle prydau parod hudolus yma.

1013
01:00:38,390 --> 01:00:41,990
Ac yn sylweddoli bod gweithio drwy hyn mewn enghreifftiau llai wrth i chi y bydd ar pset

1014
01:00:41,990 --> 01:00:44,260
yn ei gwneud yn llawer mwy 'n athrylithgar.

1015
01:00:44,260 --> 01:00:49,070
Ond beth sydd wir yn ei olygu o ran y teimlad yr algorithm yw hyn:

1016
01:00:49,070 --> 01:00:54,520
Os ydym mewn gwirionedd yn edrych ar uno fath yma - gadewch i mi dynnu i fyny yn y ffenestr hon yma -

1017
01:00:54,520 --> 01:00:58,560
mae hyn yn enghraifft ychydig yn wahanol lle mae gennym pob un o'r 3 o'r algorithmau -

1018
01:00:58,560 --> 01:01:01,440
swigen, dethol, ac yn uno - dim ond ochr yn ochr.

1019
01:01:01,440 --> 01:01:03,740
>> Maent i gyd wedi cychwyn gyda bariau ar hap, ac mae hynny'n dda.

1020
01:01:03,740 --> 01:01:06,240
Nid oes unrhyw un fantais sylfaenol dros y llall.

1021
01:01:06,240 --> 01:01:09,500
Dw i'n mynd i mewn eiliad cliciwch ar bob un o'r animeiddiadau - Start, Dechrau, Dechrau -

1022
01:01:09,500 --> 01:01:13,270
mor gyflym ag y gallaf er mwyn i, yn fras, maent i gyd yn cychwyn ar yr un pryd,

1023
01:01:13,270 --> 01:01:17,450
a gadewch i ni ystyried yr achos fath swigen yn waeth rhedeg amser yn beth? >> [Myfyrwyr] N sgwâr.

1024
01:01:17,450 --> 01:01:21,560
N sgwâr. Achos fath Dewis gwaethaf rhedeg amser? N sgwâr.

1025
01:01:21,560 --> 01:01:25,150
Ac uno fath yn ôl pob golwg - hyd yn oed os nad oeddech yn eithaf ddilyn yr holl math yn awr,

1026
01:01:25,150 --> 01:01:30,610
bydd yn dod yn llawer mwy 'n athrylithgar dros gyfnod o amser - yw, yr ydym yn hawlio, n amser log n.

1027
01:01:30,610 --> 01:01:35,210
Ac oherwydd log n yn gwbl llai nag n ôl i ni gael rhifau mawr,

1028
01:01:35,210 --> 01:01:40,230
n gwaith log n yn llai nag amseroedd n n n neu sgwâr.

1029
01:01:40,230 --> 01:01:44,410
Felly, beth mae'n ei deimlo mewn gwirionedd fod yn algorithm yn well o ran amser yn rhedeg,

1030
01:01:44,410 --> 01:01:50,380
n amser log n yn hytrach na n sgwâr? Yma rydym yn mynd. Cliciwch, cliciwch, cliciwch.

1031
01:01:55,690 --> 01:01:58,650
>> Dyna beth mae'n ei olygu i ddefnyddio rhywbeth fel uno fath.

1032
01:01:58,650 --> 01:02:01,680
Mae gennym hyn o bryd. Gadewch i ni weld beth sy'n digwydd yma.

1033
01:02:09,440 --> 01:02:12,440
[Chuckles] pwy arian ar fath swigen?

1034
01:02:14,960 --> 01:02:16,730
Mae yn hytrach yn dibynnu ar y mewnbwn weithiau.

1035
01:02:16,730 --> 01:02:18,120
Gadewch i ni weld.

1036
01:02:18,120 --> 01:02:23,320
Dewch ar. Mae'n teimlo fel ei fod yn dal i fyny. >> [Myfyrwyr] Ewch, math swigen!

1037
01:02:23,320 --> 01:02:27,370
[Fyfyrwyr grwgnach]

1038
01:02:27,370 --> 01:02:29,120
[Malan] Yeah, yeah.

1039
01:02:29,120 --> 01:02:34,520
[Fyfyrwyr grwgnach] Ewch, ewch, ewch!

1040
01:02:37,210 --> 01:02:40,450
[Holl bloeddio] [gymeradwyaeth]

1041
01:02:40,450 --> 01:02:46,240
Felly, yn awr gyda 1 y llynedd, demo terfynol, os yw'n ychydig yn anodd i lapio eich meddwl o amgylch y math

1042
01:02:46,240 --> 01:02:49,280
neu rhyw fath o ddelweddu yno, alli 'n weithredol glywed y cyflymder

1043
01:02:49,280 --> 01:02:51,000
o algorithmau gwahanol yn wahanol.

1044
01:02:51,000 --> 01:02:53,900
Mae hwn yn rhywun animeiddio a wnaed sydd mewn gwirionedd yn swnio'n cyswllt

1045
01:02:53,900 --> 01:02:56,980
gyda'r broses o gyfnewid ac uchder y bariau.

1046
01:02:56,980 --> 01:03:00,440
Fel gawn ni weld yma, mae 'na algorithmau didoli ychydig mwy allan yna sy'n Folks wedi meddwl amdanynt.

1047
01:03:00,440 --> 01:03:03,660
Mae'r un cyntaf yn mynd i fod yn fath mewnosod, a bydd hyn yn hedfan drwy

1048
01:03:03,660 --> 01:03:07,090
ac yn rhoi ymdeimlad clywadwy o sut mae hyn yn gweithio algorithmau amrywiol.

1049
01:03:07,090 --> 01:03:09,080
Dyma fath gosod.

1050
01:03:09,080 --> 01:03:18,410
[Beeping microform]

1051
01:03:18,410 --> 01:03:20,730
[Malan] fath Bubble.

1052
01:03:20,730 --> 01:03:46,850
[Gyflymach beeping microform]

1053
01:03:46,850 --> 01:03:48,950
[Malan] fath Dethol.

1054
01:03:48,950 --> 01:04:03,580
[Gyflymach beeping microform]

1055
01:04:03,580 --> 01:04:05,770
[Malan] fath Cyfuno.

1056
01:04:05,770 --> 01:04:17,270
[Beeping microform]

1057
01:04:17,270 --> 01:04:20,180
[Beeping yn arafu i lawr] [chwerthin]

1058
01:04:20,180 --> 01:04:22,590
[Malan] fath Gnome.

1059
01:04:22,590 --> 01:04:38,580
[Beeping microform]

1060
01:04:39,740 --> 01:04:46,150
>> Mae hyn yn CS50. Gwelwn ni chi wythnos nesaf. [Gymeradwyaeth a bloeddio]

1061
01:04:46,150 --> 01:04:48,000
>> [CS50.TV]