>> [Zenelejátszási]
DOUG LLOYD: Lineáris keresés egy algoritmus
Használhatja találni egy elem a tömbben.
Egy algoritmus visszahívás egy lépésről-lépésre sor
Az utasítások egy feladat elvégzéséhez.
>> A lineáris keresés algoritmus a következőképpen működik.
Ismételget az egész tömb balról Rendben, keres egy megadott elem.
>> A pszeudokód, amely egy több desztillált változata ez a mondat,
ha az első elem az, amit keres, akkor megáll.
Ellenkező esetben, lépjen a következő elem és folyamatosan megy újra és újra, amíg meg nem találja
az elem, vagy nem.
Így tudjuk használni a lineáris keresési algoritmus, például,
hogy megtalálják a célérték Kilenc ebben a tömbben.
Hát kezdjük az elején.
Ha ez az, amit mi keresnek, meg tudjuk állítani.
Ez nem, mi nem keres 11.
Szóval különben lépjen a következő elem.
>> Szóval nézzük 23.
23 amit keresett?
Hát nem, így haladunk tovább a következő elemet, és a következő elem,
és mi folyamatosan megy keresztül ezt a folyamatot újra és újra
és újra, amíg leszállunk egy ilyen helyzetben.
>> Kilenc, amit keresünk, és ez az elem a tömb
az, hogy ez az érték kilenc.
És így találtunk mi vagyunk keresnek, és meg tudjuk állítani.
A lineáris keresés rendelkezik befejezett, sikeresen.
>> De mi a helyzet, ha keresünk olyan elem, amely nem a tömbben.
Vajon lineáris keresés mindig működik?
Nos, az biztos.
Tehát megismételni ezt a folyamatot kezdve az első elemet.
Ha ez az, amit mi keresnek, meg tudjuk állítani.
Ez nem.
Ellenkező esetben, lépjen a következő elem.
>> De mi is folyamatosan ismétlődő ezt a folyamatot, vizsgálata minden elem viszont,
remélve, hogy megtaláljuk a szám 50.
De nem fogunk tudni, ha találtunk száma 50
vagy ha nem, amíg meg nem lépett alatt minden egyes eleme a tömb.
>> Csak egyszer tettünk ezt, és jön létre, rövid,
tudjuk következtetni, hogy 50 nem a tömbben.
És így a lineáris keresés algoritmust, valamint elmulasztotta, önmagában.
De nem abban az értelemben, hogy ez sikertelen volt mit csinál
kértük, hogy igen.
>> Ez sikertelen volt, mint sokat, mert nem találtam 50,
de 50 nem volt a tömbben.
De mi kimerítően keresett keresztül minden egyes elem
és így, míg nem találtunk semmit, lineáris keresés mindig
sikerül is, ha a elem nincs a tömbben.
>> Szóval mi a legrosszabb esetben forgatókönyv lineáris keresést?
Nos, át kell néznünk Minden egyes eleme,
vagy azért, mert a cél elem az utolsó elem a tömb,
vagy az elem keresünk nem valóban létezik a tömb egyáltalán.
Mi a legjobb esetben?
Hát talán megtaláljuk a elem azonnal.
És hány elem teszünk utána kell nézni
A legjobb esetben, ha keresünk meg
és azt látjuk, hogy a kezdet kezdetén?
Mi lehet azonnal leáll.
>> Mit mond ez a komplexitása lineáris keresés?
Nos, a legrosszabb esetben van nézni minden egyes elem.
És ez így fut O N, a legrosszabb esetben.
>> A legjobb esetben, fogunk megtalálni az elem azonnal.
És így fut omegája 1.
>> Én Doug Lloyd.
Ez CS50.