>> [Musika jotzen]
DOUG LLOYD: lineala bilaketa algoritmo dugu bat da
array batean elementu bat aurkitzeko erabil daiteke.
Algoritmo abisuaren An Urrats-urrats multzo bat da
zeregin bat betetzeko argibideak ere.
>> Bilaketa lineala Algoritmo honela funtzionatzen.
Array zehar batetik bestera joateko ezkerretik eskubidea, zehaztu elementu baten bila.
>> Pseudocode, zein da gehiago bat distilatu sententzia honen bertsio,
lehen elementua bada zer Zuretzat, gelditu ahal izango duzu ari zaren.
Bestela, hurrengo elementua mugitu eta mantentzeko eta gehiago baino gehiago joan aurkitu arte
elementua, edo ez duzu.
Beraz lineala erabili ahal izango dugu bilaketa algoritmo, adibidez,
helburu balioa aurkitu array honetan bederatzi.
Beno, hasteko hasieran dugu.
Da zer egingo diogu! bila, gelditu ahal izango dugu.
Ez da, ez gara 11 bila.
Beraz, bestela, hurrengo elementua mugitu.
>> Beraz, begiratu at 23 dugu.
23 zer bilatzen ari gara?
Beno ez, beraz, aurrera egin dugu hurrengo elementu, eta hurrengo elementua,
eta, bidez jarraitzeko dugu Prozesu hau eta gehiagoko
eta berriz, ez dugu lur arte honen antzeko egoera batean.
>> Bederatzi zer bilatzen ari gara da, eta array elementu hau
da, bere balio bederatzi da.
Eta beraz, zer ari gara aurkitu dugu bila, eta gelditu ahal izango dugu.
Bilaketa lineala du amaitu, arrakastaz.
>> Baina zer gertatzen da buruz ari gara bila Hori ez da gure array elementu bat.
Ez du bilaketa lineala oraindik lan?
Beno, ziur.
Beraz, prozesu hau errepikatu dugu lehen elementutik hasita.
Da zer egingo diogu! bila, gelditu ahal izango dugu.
Ez da.
Bestela, hurrengo elementua mugitu dugu.
>> Baina prozesu hau errepikatuz mantendu ahal izango dugu, elementu bakoitzaren azterketa, aldi berean,
50 zenbakia aurkitu dugun mesederako.
Baina gu ez baldin badakizu Nik kopurua 50 aurkitu dugu
edo egin ez badugu, zapaldu genuen arte Nik array elementu bakar behin baino gehiagotan.
>> Egin dugu behin bakarrik hori eta etorri laburrak,
ahal amaitzen 50 ez da array.
Eta beraz, bilaketa lineala bildu, baita huts, per se.
Baina ez zentzuan dela egitean porrot egin du zer
da galdetu diogu.
>> Da onartu bezala da Askoz ez, ez, aurkitu 50,
baina 50 ez zen array.
Baina izan sakon bilatuko dugu elementu bakoitza bitartez
eta beraz, ez genuen aurkitu bitartean ezer, bilaketa lineala oraindik
arrakastasua bada ere elementua ez da array.
>> Beraz, zein da kasu txarrena Bilaketa lineala egoera?
Beno bidez begiratu behar dugu elementu bakar behin,
bai delako helburu elementua array azken elementua da,
edo ez du elementua bilatzen ari gara benetan array existitzen guztietan.
Zer da kasurik onenean?
Beno, agian aurkituko dugu elementua berehala.
Nola eta beste hainbat elementu ez orduan dugun begiratu
Kasu onena at, da guk nahi izanez gero
eta aurkituko dugu hasieran oso?
Berehala eten ahal izango dugu.
>> Zer esan nahi du buruz esan Bilaketa lineala konplexutasuna?
Beno, kasurik okerrenean ere, ez dugu den elementu bakoitza begiratu.
Eta orain exekutatzen O da n, kasurik okerrenean ere.
>> Kasurik onenean ere, botako dugu elementua berehala aurkitu.
Eta hain 1 omega exekutatzen.
>> Naiz Doug Lloyd.
Hau CS50 da.