Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Linear Tafuta]
[Patrick Schmid, Chuo Kikuu cha Harvard]
[Hii Ni CS50.] [CS50.TV]
Kutafuta ni kitu ambacho pengine kufanya mara nyingi zaidi kuliko kufikiri.
Ni wazi, kila wakati kufungua kivinjari
na kutafuta ukurasa wa mtandao -
au tafuta kwa rafiki yako kwenye tovuti yako favorite mitandao ya kijamii -
wewe ni kutafuta.
Lakini hiyo ni sehemu ndogo tu ya kutafuta kwamba kufanya juu ya kila siku.
Wakati unataka kupata kwamba moja ya bluu shati katika chooni,
au kwamba kamili nyekundu blouse ajili ya tukio,
wewe ni kutafuta.
Wakati wewe kwenda dukani kwamba ve kamwe kuwa kabla,
na wewe ni kuangalia kwa brokoli katika aisle mazao
wewe ni kutafuta.
Nini unaweza kuanza kwa taarifa
ni kwamba kulingana na kile wewe ni kuangalia kwa
au jinsi vitu ni kupangwa wakati wewe ni kuangalia kwa ajili yao
ina athari juu ya jinsi ya kutafuta.
Kwa mfano, kama mashati yako ni kunyongwa katika chooni,
pengine unaweza tu kuchukua ni nje bila ya kutafuta sana.
Kama wewe ni kuchukua una kutembea chini aisle
kupata broccoli, pengine kuangalia mboga nyingine zote
kabla ya kupata kwamba brokoli.
Tafuta linear ni mfano wa njia moja vile kutafuta - au algorithm.
Kama jina linavyoashiria,
njia hii huchunguza kwa kipengele katika mtindo linear, moja baada ya nyingine.
Hivyo, wakati wewe kuangalia matokeo kutoka injini yako favorite search
na wewe kusoma chini orodha ya matokeo,
unatumia tafuta linear.
Sawa. Hebu tuangalie mfano.
Sema sisi kuwa na orodha ya idadi - 2, 4, 0, 5, 3, 7, 8, na 1 -
na sisi ni kuangalia kwa 0 idadi.
Ni wazi, unaweza tu kuona kwamba 0 ni katika nafasi ya tatu.
Lakini, mpango kompyuta si kwamba bahati.
Unaweza tu "kuona" namba moja kwa wakati.
Hivyo, kuanzia mwanzoni mwa orodha,
tu "anaona" 2.
mpango kisha hundi - ni sawa na 0 2?
Wazi si. Hivyo unaendelea kwa namba inayofuata, 4.
Je, 4 0 sawa? Nope.
moja ijayo, 0. Ah! Zero ni sawa na 0.
Kuna sisi kuwa nayo! Ni katika nafasi ya tatu.
Sawa. Hebu tuangalie baadhi pseudocode.
Ni michache tu ya mistari ya muda mrefu, lakini hebu tuangalie ni line moja kwa wakati.
Kwanza, hebu define kazi - na sisi ni kwenda kumwita linear search -
na inachukua hoja mbili - ufunguo na safu.
muhimu ni kwamba thamani ya kwamba sisi ni kuangalia kwa,
hivyo katika mfano uliopita, kwamba ilikuwa sifuri.
safu ni orodha ya namba
ambayo ina maadili yote ya kwamba sisi ni kwenda kutafuta.
Hivyo, nini tunataka kufanya ni sisi unataka kuangalia -
kutoka nafasi zote, hivyo kuanzia mwanzoni kabisa mwa safu
til mwisho kabisa wa safu - hivyo urefu wa safu -
kuangalia nafasi ya kila moja na kuangalia kila moja.
Hivyo kwamba ni nini kwamba "kwa" kitanzi ni kufanya.
Na katika kila nafasi, sisi ni kwenda kusema
"Ni kwamba thamani katika msimamo kwamba sasa sawa na muhimu kwamba sisi ni kuangalia kwa?"
Hivyo - katika mfano uliopita tena, muhimu ilikuwa 0 -
hivyo sisi ni kusema "Je safu katika nafasi i sawa na sifuri?"
Kama ni, sisi ni kwenda na kurudi 'i' kwa sababu hiyo ni nafasi ya sasa sisi ni saa.
Hivyo, katika mfano uliopita,
kwamba ilikuwa ni nafasi ya tatu.
Kama tumeenda kupitia safu nzima
na sisi sikuona kitu chochote -
hivyo hebu sema tulikuwa kuangalia kwa idadi 500
ambayo ni wazi si katika mfano kwamba -
tuna kurudi kitu,
na sisi ni kwenda na kurudi -1.
Na sisi ni tu kurudi -1 sababu hiyo ni nafasi ya
kwamba haipo katika safu.
Na hivyo kwamba maana wakati wewe kupata nyuma kutokana na kazi
anasema "Hmm, sawa. Mimi nadhani hawakuona kitu chochote.
Hivyo kwamba 500 kamwe alikuwa huko. "
Jambo zuri tafuta linear ni kwamba
itabidi kazi yoyote orodha ya vitu,
bila kujali jinsi vitu amrishwa.
Haijalishi ambapo brokoli ni katika aisle mazao.
Muda mrefu kama wewe kutembea chini aisle kuanzia mwanzo hadi mwisho,
wewe amefungwa na kupata hiyo,
kuchukua kuhifadhi imekuwa si kukimbia nje ya brokoli, bila shaka.
Lakini kubwa zaidi ni nguvu pia ni kubwa zaidi udhaifu.
Sema una orodha ya namba mia mbili
kwamba ni sorted 1-200.
Kama wewe ni kuangalia kwa idadi 198,
una kutafuta karibu orodha nzima ya idadi
kabla ya kupata moja wewe ni kuangalia kwa.
Lazima kuna njia bora zaidi!
Mapumziko uhakika kuna.
Lakini, hiyo ni mada kwa ajili ya video nyingine.
Pia, je, si fret!
Kwa sababu tu tafuta linear si suluhisho bora katika mazingira yote,
haina maana kwamba haina kuja katika Handy.
Vinginevyo, jinsi gani unaweza kupata kwamba brokoli katika aisle mazao?
Jina langu ni Patrick Schmid, na hii ni CS50.
[CS50.TV]