[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.