1
00:00:00,000 --> 00:00:05,760

2
00:00:05,760 --> 00:00:08,900
>> DOUG LLOYD: Felly, yn CS50 rydym yn dysgu am
amrywiaeth o didoli a chwilio

3
00:00:08,900 --> 00:00:09,442
algorithmau.

4
00:00:09,442 --> 00:00:11,400
Ac weithiau gall fod yn
ychydig yn anodd i gadw

5
00:00:11,400 --> 00:00:14,161
golwg ar yr hyn algorithm sy'n gwneud beth.

6
00:00:14,161 --> 00:00:15,910
Rydym wedi gwirionedd dim ond
sgim yr wyneb hefyd,

7
00:00:15,910 --> 00:00:18,740
mae yna lawer o chwilio eraill
a didoli algorithmau.

8
00:00:18,740 --> 00:00:21,780
Felly, yn y fideo hwn gadewch i ni
dim ond yn cymryd ychydig funudau

9
00:00:21,780 --> 00:00:24,980
i geisio distill pob algorithm
i lawr at ei elfennau craidd

10
00:00:24,980 --> 00:00:27,810
er mwyn i chi gofio y mwyaf
gwybodaeth bwysig am iddynt

11
00:00:27,810 --> 00:00:31,970
a gallu mynegi'r
gwahaniaethau, os oes angen.

12
00:00:31,970 --> 00:00:34,220
>> Y cyntaf yw math dethol.

13
00:00:34,220 --> 00:00:38,210
Y syniad sylfaenol y tu ôl i fath dethol
yn dod o hyd i'r elfen heb eu didoli lleiaf

14
00:00:38,210 --> 00:00:42,890
mewn amrywiaeth ac yn cyfnewid gyda'r
Elfen heb ei ddidoli cyntaf y rhesi.

15
00:00:42,890 --> 00:00:46,620
Rydym yn dweud bod y gwaethaf-achos
amser rhedeg o hynny oedd sgwâr n.

16
00:00:46,620 --> 00:00:50,060
Ac os ydych chi am i gofio pam, cymryd
a edrych ar y fideo didoli dewis.

17
00:00:50,060 --> 00:00:54,560
Mae'r amser yn rhedeg orau-achos
hefyd yn cael ei sgwâr n.

18
00:00:54,560 --> 00:00:58,910
>> Didoli Bubble, y syniad y tu ôl i hynny
un yw cyfnewid parau cyfagos.

19
00:00:58,910 --> 00:01:01,730
Felly dyna allwedd sy'n eich helpu
cofiwch y gwahaniaeth yma.

20
00:01:01,730 --> 00:01:04,920
Dewis math yw, hyd yn hyn,
ddod o hyd i'r swigen smallest--

21
00:01:04,920 --> 00:01:06,790
didoli yw cyfnewid parau cyfagos.

22
00:01:06,790 --> 00:01:08,710
Rydym yn gyfnewid parau cyfagos
o elfennau os ydynt yn

23
00:01:08,710 --> 00:01:12,530
allan o drefn, a oedd yn effeithiol
swigod elfennau mwy i'r dde,

24
00:01:12,530 --> 00:01:17,060
ac ar yr un pryd mae hefyd yn dechrau
i symud elfennau llai ar y chwith.

25
00:01:17,060 --> 00:01:20,180
Y gwaethaf-achos amser yn rhedeg achos
o'r math swigen yn sgwâr n.

26
00:01:20,180 --> 00:01:23,476
Mae'r amser yn rhedeg orau-achos
o swigen fath yn n.

27
00:01:23,476 --> 00:01:25,350
Oherwydd yn y sefyllfa honno
nid ydym yn actually--

28
00:01:25,350 --> 00:01:27,141
Efallai na fydd angen i i ni
wneud unrhyw gyfnewidiadau o gwbl.

29
00:01:27,141 --> 00:01:31,026
Dim ond rhaid i ni wneud un
pasio ar draws pob elfen n.

30
00:01:31,026 --> 00:01:34,600
>> Yn y math mewnosod, mae'r
syniad sylfaenol yma yn newid.

31
00:01:34,600 --> 00:01:36,630
Dyna y gair allweddol ar gyfer y math gosod.

32
00:01:36,630 --> 00:01:39,630
Rydym yn mynd i gamu unwaith drwy
yr amrywiaeth o'r chwith i'r dde.

33
00:01:39,630 --> 00:01:41,670
Ac wrth i ni ei wneud, rydym yn
mynd i newid elfennau

34
00:01:41,670 --> 00:01:46,260
rydym wedi gweld yn barod i wneud lle i
rhai llai y mae angen i gyd-fynd rhywle

35
00:01:46,260 --> 00:01:48,080
yn ôl yn y gyfran didoli.

36
00:01:48,080 --> 00:01:51,600
Felly, rydym yn adeiladu yr amrywiaeth ddidoli un
elfen ar y tro, o'r chwith i'r dde,

37
00:01:51,600 --> 00:01:54,740
ac yr ydym yn symud pethau i wneud lle.

38
00:01:54,740 --> 00:01:58,650
Mae'r amser yn rhedeg gwaethaf-achos
didoli gosod yn sgwâr n.

39
00:01:58,650 --> 00:02:02,380
Yr amser gorau-achos yn rhedeg yn n.

40
00:02:02,380 --> 00:02:05,380
>> Cyfuno sort-- y gair allweddol
yma ei rannu ac uno.

41
00:02:05,380 --> 00:02:08,949
Rydym yn rhannu yr amrywiaeth lawn, p'un
'i' chwe elfen, wyth elfen,

42
00:02:08,949 --> 00:02:13,790
10,000 elements-- rydym yn rhannu ei
i lawr i'w hanner, hanner, hanner,

43
00:02:13,790 --> 00:02:17,720
nes gennym o dan amrywiaeth
o n un elfen araeau.

44
00:02:17,720 --> 00:02:19,470
Mae set o n un elfen araeau.

45
00:02:19,470 --> 00:02:22,640
Felly, rydym yn dechrau gyda un
1,000-elfen array,

46
00:02:22,640 --> 00:02:26,550
ac yr ydym yn cyrraedd y pwynt lle rydym yn
rhaid i 1,000 un-elfen araeau.

47
00:02:26,550 --> 00:02:30,990
Yna, rydym yn dechrau i uno is araeau rhai
ôl at ei gilydd yn y drefn gywir.

48
00:02:30,990 --> 00:02:34,860
Felly, rydym yn cymryd ddau arae un-elfen
a chreu dwy elfen array.

49
00:02:34,860 --> 00:02:38,180
Rydym yn cymryd ddau arae dwy elfen
a chreu pedwar-elfen array

50
00:02:38,180 --> 00:02:43,900
ac yn y blaen ac yn y blaen hyd nes y byddwn i wedi
eto ailadeiladwyd un elfen n array.

51
00:02:43,900 --> 00:02:48,410
>> Mae'r amser yn rhedeg gwaethaf-achos
uno fath yw n amserau log n.

52
00:02:48,410 --> 00:02:52,390
Mae gennym elfennau n, ond
broses hailgyfuno hon

53
00:02:52,390 --> 00:02:56,960
cymryd log n camau i fynd
yn ôl i amrywiaeth lawn.

54
00:02:56,960 --> 00:03:01,160
Yr achos gorau rhedeg amser hefyd yn n log
n gan nad yw y broses hon yn wir

55
00:03:01,160 --> 00:03:04,090
gofal a oedd y casgliad oedd
didoli neu beidio i ddechrau.

56
00:03:04,090 --> 00:03:07,590
Mae'r broses yr un fath, mae '
unrhyw ffordd i bethau cylched byr.

57
00:03:07,590 --> 00:03:11,610
Felly n log n yn yr achos gwaethaf,
n log n yn yr achos gorau.

58
00:03:11,610 --> 00:03:13,960
>> Buom yn siarad am ddwy
chwilio algorithmau.

59
00:03:13,960 --> 00:03:16,230
Felly chwiliad llinol yn ymwneud ailadrodd.

60
00:03:16,230 --> 00:03:19,500
Awn ymlaen ar draws yr amrywiaeth
unwaith, o'r chwith i'r dde,

61
00:03:19,500 --> 00:03:21,950
ceisio dod o hyd i'r rhif
ein bod yn chwilio am.

62
00:03:21,950 --> 00:03:24,550
Yr amser gwaethaf-achos yn rhedeg yn O fawr o n.

63
00:03:24,550 --> 00:03:27,610
Gallai fod yn mynd â ni ailadrodd
ar draws pob elfen unigol

64
00:03:27,610 --> 00:03:30,660
i ddod o hyd i'r elfen rydym yn chwilio
ar gyfer, naill ai yn y swydd ddiwethaf,

65
00:03:30,660 --> 00:03:31,630
neu ddim o gwbl.

66
00:03:31,630 --> 00:03:34,720
Ond ni allwn gadarnhau bod hyd nes
rydym wedi edrych ar bopeth.

67
00:03:34,720 --> 00:03:36,730
my-achos gorau, rydym yn dod o hyd ar unwaith.

68
00:03:36,730 --> 00:03:41,060
Mae'r amser yn rhedeg orau-achos
Chwilio llinol yw omega o 1.

69
00:03:41,060 --> 00:03:43,689
>> Yn olaf, yr oedd chwilio deuaidd,
sy'n gofyn am amrywiaeth amrywiol.

70
00:03:43,689 --> 00:03:45,605
Cofiwch fod 'na iawn
ystyriaeth bwysig

71
00:03:45,605 --> 00:03:47,155
wrth weithio gyda chwiliad deuaidd.

72
00:03:47,155 --> 00:03:50,180
Mae'n rhagofyniad i ddefnyddio iddo--
yr amrywiaeth eich bod yn chwilio trwy

73
00:03:50,180 --> 00:03:52,160
Mae'n rhaid eu datrys.

74
00:03:52,160 --> 00:03:54,500
Fel arall, yr allweddair
yn rhaniad a gorchfygu.

75
00:03:54,500 --> 00:03:58,310
Rhannwch yr amrywiaeth mewn i hanner a
gwared ar hanner yr elfennau

76
00:03:58,310 --> 00:04:00,780
bob tro wrth i chi symud ymlaen trwy'r.

77
00:04:00,780 --> 00:04:04,330
Oherwydd rhaniad hwn a gorchfygu
a hollti pethau yn hanner ffordd,

78
00:04:04,330 --> 00:04:07,450
yr amser yn rhedeg waethaf
chwilio deuaidd yw

79
00:04:07,450 --> 00:04:11,730
log n, sy'n sylweddol
yn well na n chwilio llinellol yn.

80
00:04:11,730 --> 00:04:13,570
Yr amser gorau-achos yn rhedeg yn dal yn un.

81
00:04:13,570 --> 00:04:17,010
>> Efallai y byddwn yn ei chael yn syth i'r
tro cyntaf i ni wneud is-adran, ond,

82
00:04:17,010 --> 00:04:19,339
unwaith eto, cofiwch fod
er bod y chwiliad deuaidd yn

83
00:04:19,339 --> 00:04:24,030
sylweddol well na'r chwilio llinellol
yn rhinwedd bod log n erbyn n,

84
00:04:24,030 --> 00:04:27,110
Efallai y bydd rhaid i chi fynd drwy'r gwaith
o ddatrys eich array cyntaf, a

85
00:04:27,110 --> 00:04:32,010
gallai ei wneud yn llai effeithiol yn dibynnu
ar faint y ailadrodd didoli.

86
00:04:32,010 --> 00:04:35,250
>> Rwy'n Doug Lloyd, mae hyn yn CS50.

87
00:04:35,250 --> 00:04:36,757