>> [Daqq tal-mużika]
Doug LLOYD: Linear tfittxija hija algoritmu aħna
jistgħu jużaw biex isibu element fil-firxa.
An irtirar algoritmu huwa sett pass-pass
ta 'struzzjonijiet għal kompletar ta' dmir.
>> It-tfittxija lineari algoritmu xogħlijiet kif ġej.
Jtenni madwar l-array mix-xellug għal dritt, tfittex għal element speċifikat.
>> Fil pseudocode, li hija aktar Verżjoni distillat ta 'din is-sentenza,
jekk l-ewwel element huwa dak inti qed tfittex, inti tista 'twaqqaf.
Inkella, jimxu lejn l-element li jmiss u jibqgħu għaddejjin fuq u aktar sakemm issib
l-element, jew inti ma.
Allura nistgħu nużaw l lineari tfittxija algoritmu, per eżempju,
biex isibu l-valur immirat disa f'dan array.
Well we tibda fil-bidu.
Jekk huwa dak li aħna qed tfittex, nistgħu stop.
Mhuwiex, aħna mhux qed infittxu 11.
Allura mod ieħor, jimxu lejn l-element li jmiss.
>> Allura aħna nħarsu lejn 23.
Hija ta '23 dak li aħna qed tfittex?
Ukoll ebda, hekk aħna jimxu fuq il-li jmiss element, u l-element li jmiss,
u aħna jibqgħu għaddejjin permezz dan il-proċess aktar u aktar
u aktar, sakemm aħna art fuq sitwazzjoni bħal din.
>> Disa huwa dak li aħna qed tfittex, u dan l-element ta 'l-array
huwa, il-valur huwa huwa disgħa.
U hekk sibna dak li aħna qed tfittex għal, u nistgħu tieqaf.
It-tfittxija lineari għandha mimlija, b'suċċess.
>> Imma xi ngħidu dwar jekk aħna qed infittxu element li mhux fil-firxa tagħna.
Does tfittxija lineari għadhom jaħdmu?
Well żgur.
Allura aħna irrepeti dan il-proċess jibda mill-ewwel element.
Jekk huwa dak li aħna qed tfittex, nistgħu stop.
Mhuwiex.
Inkella, nimxu għall-element li jmiss.
>> Iżda aħna nkunu nistgħu nżommu tirrepeti dan il-proċess, jeżamina kull element min-naħa,
bit-tama li nsibu n-numru 50.
Iżda aħna mhux se tkun taf jekk aħna ħadthom misjuba-numru 50
jew jekk aħna ma, sakemm konna intensifikati fuq kull element wieħed ta 'l-array.
>> Biss ladarba aħna ghamilt li u toħroġ qasir,
nistgħu nikkonkludu li 50 ma tkunx fil-firxa.
U għalhekk l-tfittxija lineari algoritmu, sew hija naqset, per se.
Iżda mhux fis-sens li ma rnexxiex fil tagħmel dak
staqsejna li tagħmel.
>> Li ma rnexxilhiex bħala kemm hija ma ssib 50,
iżda 50 ma kienx fil-firxa.
Iżda aħna mfittxija b'mod eżawrjenti permezz ta 'kull element wieħed
u għalhekk, filwaqt li aħna ma sabx xejn, tfittxija lineari xorta
jirnexxilu anki jekk il- element mhuwiex fil-firxa.
>> Allura x'inhu l-agħar każ Sitwazzjoni ta 'tfittxija lineari?
Well irridu nħarsu permezz kull element wieħed,
jew għaliex l-element mira hija l-aħħar element tal-firxa,
jew l-element aħna qed tfittex ma attwalment jeżistu fl-array fil-livelli kollha.
X'inhu l-aħjar xenarju?
Well we tista 'ssib l- element immedjatament.
U kemm elementi għandna mbagħad nħarsu
fil fl-aħjar każ, jekk aħna qed tfittex għaliha
u aħna jsibuha fil-bidu nett?
Aħna tista 'twaqqaf immedjatament.
>> Xi jfisser dan jgħidu dwar il- kumplessità tat-tfittxija lineari?
Ukoll fl-agħar każ, għandna li tħares lejn kull element wieħed.
U għalhekk tmur fil O ta n, fl-agħar każ.
>> Fl-aħjar każ, aħna qed gonna isibu l-element immedjatament.
U hekk tmur fil omega-1 ta '.
>> Jien Doug Lloyd.
Dan huwa CS50.