1
00:00:00,000 --> 00:00:02,892
>> [Musika jotzen]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: lineala
bilaketa algoritmo dugu bat da

4
00:00:07,180 --> 00:00:09,840
array batean elementu bat aurkitzeko erabil daiteke.

5
00:00:09,840 --> 00:00:11,990
Algoritmo abisuaren An
Urrats-urrats multzo bat da

6
00:00:11,990 --> 00:00:15,030
zeregin bat betetzeko argibideak ere.

7
00:00:15,030 --> 00:00:17,480
>> Bilaketa lineala
Algoritmo honela funtzionatzen.

8
00:00:17,480 --> 00:00:22,200
Array zehar batetik bestera joateko ezkerretik
eskubidea, zehaztu elementu baten bila.

9
00:00:22,200 --> 00:00:26,380
>> Pseudocode, zein da gehiago bat
distilatu sententzia honen bertsio,

10
00:00:26,380 --> 00:00:29,840
lehen elementua bada zer
Zuretzat, gelditu ahal izango duzu ari zaren.

11
00:00:29,840 --> 00:00:33,930
Bestela, hurrengo elementua mugitu eta
mantentzeko eta gehiago baino gehiago joan aurkitu arte

12
00:00:33,930 --> 00:00:36,389
elementua, edo ez duzu.

13
00:00:36,389 --> 00:00:38,680
Beraz lineala erabili ahal izango dugu
bilaketa algoritmo, adibidez,

14
00:00:38,680 --> 00:00:42,330
helburu balioa aurkitu
array honetan bederatzi.

15
00:00:42,330 --> 00:00:43,870
Beno, hasteko hasieran dugu.

16
00:00:43,870 --> 00:00:45,970
Da zer egingo diogu!
bila, gelditu ahal izango dugu.

17
00:00:45,970 --> 00:00:47,890
Ez da, ez gara 11 bila.

18
00:00:47,890 --> 00:00:50,220
Beraz, bestela, hurrengo elementua mugitu.

19
00:00:50,220 --> 00:00:51,510
>> Beraz, begiratu at 23 dugu.

20
00:00:51,510 --> 00:00:52,730
23 zer bilatzen ari gara?

21
00:00:52,730 --> 00:00:55,614
Beno ez, beraz, aurrera egin dugu hurrengo
elementu, eta hurrengo elementua,

22
00:00:55,614 --> 00:00:57,780
eta, bidez jarraitzeko dugu
Prozesu hau eta gehiagoko

23
00:00:57,780 --> 00:01:01,030
eta berriz, ez dugu lur arte
honen antzeko egoera batean.

24
00:01:01,030 --> 00:01:03,910
>> Bederatzi zer bilatzen ari gara da,
eta array elementu hau

25
00:01:03,910 --> 00:01:05,787
da, bere balio bederatzi da.

26
00:01:05,787 --> 00:01:08,120
Eta beraz, zer ari gara aurkitu dugu
bila, eta gelditu ahal izango dugu.

27
00:01:08,120 --> 00:01:11,910
Bilaketa lineala du
amaitu, arrakastaz.

28
00:01:11,910 --> 00:01:15,370
>> Baina zer gertatzen da buruz ari gara bila
Hori ez da gure array elementu bat.

29
00:01:15,370 --> 00:01:17,040
Ez du bilaketa lineala oraindik lan?

30
00:01:17,040 --> 00:01:17,540
Beno, ziur.

31
00:01:17,540 --> 00:01:19,947
Beraz, prozesu hau errepikatu dugu
lehen elementutik hasita.

32
00:01:19,947 --> 00:01:21,780
Da zer egingo diogu!
bila, gelditu ahal izango dugu.

33
00:01:21,780 --> 00:01:22,800
Ez da.

34
00:01:22,800 --> 00:01:25,020
Bestela, hurrengo elementua mugitu dugu.

35
00:01:25,020 --> 00:01:29,050
>> Baina prozesu hau errepikatuz mantendu ahal izango dugu,
elementu bakoitzaren azterketa, aldi berean,

36
00:01:29,050 --> 00:01:31,720
50 zenbakia aurkitu dugun mesederako.

37
00:01:31,720 --> 00:01:33,750
Baina gu ez baldin badakizu
Nik kopurua 50 aurkitu dugu

38
00:01:33,750 --> 00:01:38,290
edo egin ez badugu, zapaldu genuen arte Nik
array elementu bakar behin baino gehiagotan.

39
00:01:38,290 --> 00:01:40,440
>> Egin dugu behin bakarrik
hori eta etorri laburrak,

40
00:01:40,440 --> 00:01:43,040
ahal amaitzen
50 ez da array.

41
00:01:43,040 --> 00:01:46,410
Eta beraz, bilaketa lineala
bildu, baita huts, per se.

42
00:01:46,410 --> 00:01:49,181
Baina ez zentzuan dela
egitean porrot egin du zer

43
00:01:49,181 --> 00:01:49,930
da galdetu diogu.

44
00:01:49,930 --> 00:01:52,390
>> Da onartu bezala da
Askoz ez, ez, aurkitu 50,

45
00:01:52,390 --> 00:01:54,070
baina 50 ez zen array.

46
00:01:54,070 --> 00:01:57,310
Baina izan sakon bilatuko dugu
elementu bakoitza bitartez

47
00:01:57,310 --> 00:02:00,550
eta beraz, ez genuen aurkitu bitartean
ezer, bilaketa lineala oraindik

48
00:02:00,550 --> 00:02:05,230
arrakastasua bada ere
elementua ez da array.

49
00:02:05,230 --> 00:02:07,507
>> Beraz, zein da kasu txarrena
Bilaketa lineala egoera?

50
00:02:07,507 --> 00:02:09,590
Beno bidez begiratu behar dugu
elementu bakar behin,

51
00:02:09,590 --> 00:02:14,590
bai delako helburu elementua
array azken elementua da,

52
00:02:14,590 --> 00:02:18,510
edo ez du elementua bilatzen ari gara
benetan array existitzen guztietan.

53
00:02:18,510 --> 00:02:19,760
Zer da kasurik onenean?

54
00:02:19,760 --> 00:02:22,430
Beno, agian aurkituko dugu
elementua berehala.

55
00:02:22,430 --> 00:02:24,360
Nola eta beste hainbat elementu
ez orduan dugun begiratu

56
00:02:24,360 --> 00:02:26,859
Kasu onena at,
da guk nahi izanez gero

57
00:02:26,859 --> 00:02:28,400
eta aurkituko dugu hasieran oso?

58
00:02:28,400 --> 00:02:29,850
Berehala eten ahal izango dugu.

59
00:02:29,850 --> 00:02:32,984
>> Zer esan nahi du buruz esan
Bilaketa lineala konplexutasuna?

60
00:02:32,984 --> 00:02:35,650
Beno, kasurik okerrenean ere, ez dugu
den elementu bakoitza begiratu.

61
00:02:35,650 --> 00:02:38,930
Eta orain exekutatzen O da
n, kasurik okerrenean ere.

62
00:02:38,930 --> 00:02:41,540
>> Kasurik onenean ere, botako dugu
elementua berehala aurkitu.

63
00:02:41,540 --> 00:02:44,750
Eta hain 1 omega exekutatzen.

64
00:02:44,750 --> 00:02:45,780
>> Naiz Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Hau CS50 da.

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