1
00:00:00,000 --> 00:00:02,892
>> [CHWARAE CERDDORIAETH]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Llinol
Chwilio yn rydym algorithm

4
00:00:07,180 --> 00:00:09,840
Gall eu defnyddio i ddod o hyd elfen mewn arae.

5
00:00:09,840 --> 00:00:11,990
Adalw algorithm
yn set cam-wrth-gam

6
00:00:11,990 --> 00:00:15,030
o gyfarwyddiadau am gwblhau tasg.

7
00:00:15,030 --> 00:00:17,480
>> Mae'r chwiliad llinol
algorithm yn gweithio fel a ganlyn.

8
00:00:17,480 --> 00:00:22,200
Ailadrodd ar draws yr amrywiaeth o'r chwith i'r
gywir, yn chwilio am elfen benodol.

9
00:00:22,200 --> 00:00:26,380
>> Yn pseudocode, sydd yn fwy
Fersiwn ddistyllu y frawddeg hon,

10
00:00:26,380 --> 00:00:29,840
os yw'r elfen gyntaf yw'r hyn
rydych chi'n chwilio amdano, gallwch roi'r gorau.

11
00:00:29,840 --> 00:00:33,930
Fel arall, yn symud i'r elfen nesaf ac
dal i fynd drosodd a throsodd nes i chi ddod o hyd

12
00:00:33,930 --> 00:00:36,389
yr elfen, neu os nad ydych yn ei wneud.

13
00:00:36,389 --> 00:00:38,680
Felly, gallwn ddefnyddio'r llinellol
Chwilio algorithm, er enghraifft,

14
00:00:38,680 --> 00:00:42,330
i ddarganfod gwerth targed
naw o amrywiaeth hwn.

15
00:00:42,330 --> 00:00:43,870
Wel, rydym yn dechrau ar y dechrau.

16
00:00:43,870 --> 00:00:45,970
Os yw'n hyn yr ydym ni'n
chwilio am, gallwn roi'r gorau iddi.

17
00:00:45,970 --> 00:00:47,890
Dyw hi ddim yn, rydym yn nad ydynt yn chwilio am 11.

18
00:00:47,890 --> 00:00:50,220
Felly fel arall, symud ymlaen i'r elfen nesaf.

19
00:00:50,220 --> 00:00:51,510
>> Felly, rydym yn edrych ar 23.

20
00:00:51,510 --> 00:00:52,730
A yw 23 yr hyn rydym yn chwilio amdano?

21
00:00:52,730 --> 00:00:55,614
Wel na, felly rydym yn symud ymlaen at y nesaf
elfen, a'r elfen nesaf,

22
00:00:55,614 --> 00:00:57,780
ac rydym yn cadw mynd drwy'r
y broses hon drosodd a throsodd

23
00:00:57,780 --> 00:01:01,030
a throsodd, hyd nes y byddwn tir
ar sefyllfa fel hyn.

24
00:01:01,030 --> 00:01:03,910
>> Naw yw'r hyn yr ydym yn chwilio amdano,
ac yr elfen hon o'r amrywiaeth

25
00:01:03,910 --> 00:01:05,787
yw, 'i' gwerth yn naw.

26
00:01:05,787 --> 00:01:08,120
Ac felly rydym yn dod o hyd i hyn yr ydym ni'n
chwilio am, a gallwn stopio.

27
00:01:08,120 --> 00:01:11,910
Mae'r chwiliad llinol wedi
gwblhau, yn llwyddiannus.

28
00:01:11,910 --> 00:01:15,370
>> Ond beth am os ydym yn chwilio am
elfen sydd ddim sydd yn ein casgliad.

29
00:01:15,370 --> 00:01:17,040
A yw chwilio llinol yn dal i weithio?

30
00:01:17,040 --> 00:01:17,540
Wel yn sicr.

31
00:01:17,540 --> 00:01:19,947
Felly, rydym yn ailadrodd y broses hon
gan ddechrau yn yr elfen gyntaf.

32
00:01:19,947 --> 00:01:21,780
Os yw'n hyn yr ydym ni'n
chwilio am, gallwn roi'r gorau iddi.

33
00:01:21,780 --> 00:01:22,800
Nid yw'n.

34
00:01:22,800 --> 00:01:25,020
Fel arall, byddwn yn symud at yr elfen nesaf.

35
00:01:25,020 --> 00:01:29,050
>> Ond gallwn gadw ailadrodd y broses hon,
archwilio pob elfen yn ei dro,

36
00:01:29,050 --> 00:01:31,720
gan obeithio y byddwn yn dod o hyd i'r rhif 50.

37
00:01:31,720 --> 00:01:33,750
Ond ni fyddwn yn gwybod os
rydym wedi dod o hyd i'r rhif 50

38
00:01:33,750 --> 00:01:38,290
neu os nad ydym yn gwneud, nes ein bod wedi camu
dros bob elfen unigol y rhesi.

39
00:01:38,290 --> 00:01:40,440
>> Dim ond ar ôl i ni wedi ei wneud
hynny ac yn dod i fyny byr,

40
00:01:40,440 --> 00:01:43,040
gallwn ddod i'r casgliad bod
50 Nid yw yn y rhesi.

41
00:01:43,040 --> 00:01:46,410
Ac felly y chwiliad llinol
algorithm, dda y mae'n methu, fel y cyfryw.

42
00:01:46,410 --> 00:01:49,181
Ond nid yn yr ystyr ei fod
yn aflwyddiannus wrth wneud yr hyn y

43
00:01:49,181 --> 00:01:49,930
roeddem wedi gofyn iddo ei wneud.

44
00:01:49,930 --> 00:01:52,390
>> Roedd yn aflwyddiannus mewn fel
gymaint ag nad oedd yn dod o hyd i 50,

45
00:01:52,390 --> 00:01:54,070
ond nid oedd yn 50 y rhesi.

46
00:01:54,070 --> 00:01:57,310
Ond rydym wedi chwilio yn drwyadl
trwy bob elfen unigol

47
00:01:57,310 --> 00:02:00,550
ac felly, er ein bod nid oedd yn dod o hyd
unrhyw beth, chwilio llinol yn dal i

48
00:02:00,550 --> 00:02:05,230
yn llwyddo hyd yn oed os y
Nid yw elfen yn y rhesi.

49
00:02:05,230 --> 00:02:07,507
>> Felly beth yw'r achos gwaethaf
senario gyda chwiliad llinol?

50
00:02:07,507 --> 00:02:09,590
Wel mae'n rhaid i ni edrych drwy
pob un elfen,

51
00:02:09,590 --> 00:02:14,590
naill ai oherwydd yr elfen targed
yw elfen olaf y rhesi,

52
00:02:14,590 --> 00:02:18,510
neu os nad yw'r elfen rydym yn chwilio am ei wneud
yn bodoli mewn gwirionedd yn y rhesi o gwbl.

53
00:02:18,510 --> 00:02:19,760
Beth yw'r senario achos gorau?

54
00:02:19,760 --> 00:02:22,430
Wel efallai y byddwn yn dod o hyd i'r
Elfen ar unwaith.

55
00:02:22,430 --> 00:02:24,360
Sut a elfennau o
ydym wedyn yn rhaid inni edrych

56
00:02:24,360 --> 00:02:26,859
yn yn yr achos gorau,
os ydym yn chwilio amdano

57
00:02:26,859 --> 00:02:28,400
ac yr ydym yn dod o hyd iddo ar y cychwyn cyntaf?

58
00:02:28,400 --> 00:02:29,850
Gallwn roi'r gorau ar unwaith.

59
00:02:29,850 --> 00:02:32,984
>> Beth mae hyn yn ei ddweud am y
cymhlethdod chwilio llinellol?

60
00:02:32,984 --> 00:02:35,650
Wel yn yr achos gwaethaf, mae gennym
i edrych ar bob elfen unigol.

61
00:02:35,650 --> 00:02:38,930
Ac felly mae'n rhedeg yn y O o
n, yn yr achos gwaethaf.

62
00:02:38,930 --> 00:02:41,540
>> Yn yr achos gorau, rydym yn gonna
ddod o hyd i'r elfen ar unwaith.

63
00:02:41,540 --> 00:02:44,750
Ac felly yn rhedeg mewn omega o 1.

64
00:02:44,750 --> 00:02:45,780
>> Rwy'n Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Mae hyn yn CS50.

66
00:02:48,020 --> 00:02:49,876