DOUG LLOYD: Kwa hiyo katika CS50 sisi kujifunza kuhusu aina ya kuchagua na kutafuta algorithms. Na wakati mwingine inaweza kuwa gumu kidogo kuweka wimbo wa nini algorithm anafanya nini. Tumekuwa kweli tu skimmed uso mno, kuna watu wengi kutafuta wengine na kuchagua algorithms. Hivyo katika video hii hebu tu kuchukua dakika chache kujaribu na distill kila algorithm chini ya mambo yake ya msingi hivyo unaweza kukumbuka zaidi taarifa muhimu kuhusu wao na kuwa na uwezo wa kueleza tofauti, kama ni lazima. 

Kwanza ni uteuzi aina. Wazo msingi nyuma ya uteuzi aina ni kupata ndogo zisizochambuliwa kipengele katika safu na wabadilishane kwa kwanza zisizochambuliwa kipengele cha safu hiyo. Sisi alisema kuwa mbaya zaidi kesi kukimbia wakati wa kwamba alikuwa n squared. Na kama unataka kukumbuka nini, kuchukua a tuangalie uteuzi aina za video. Bora kesi kukimbia wakati Pia n squared. 

Bubble aina, Dhana ya kwamba moja ni wabadilishane jozi karibu. Hivyo hiyo ni muhimu kwamba husaidia kumbuka tofauti hapa. Uteuzi aina ni, hadi sasa, kupata Bubble smallest-- aina ni wabadilishane jozi karibu. Sisi wabadilishane jozi karibu ya mambo kama ni nje ya utaratibu, ambayo kwa ufanisi Bubbles mambo makubwa na haki, na wakati huo huo pia huanza hoja mambo madogo upande wa kushoto. Mbaya zaidi kesi kesi kukimbia wakati ya Bubble aina ni n squared. Bora kesi kukimbia wakati ya Bubble aina ni n. Kwa sababu katika hali hiyo hatuna actually-- tupate haja ya kufanya swaps yoyote wakati wote. Sisi tu kuwa na kufanya moja kupita katika mambo yote n. 

Katika kuingizwa aina, wazo la msingi hapa ni shifting. Hiyo ni neno la kwa kuingizwa aina. Tunakwenda hatua mara moja kupitia safu kutoka kushoto kwenda kulia. Na kama sisi, tuko kwenda kuhama mambo tumekuwa tayari kuona na kufanya nafasi ya ndogo wale wanaohitaji na kifafa mahali fulani nyuma katika kuwa sehemu yamepangwa. Hivyo sisi kujenga safu Iliyopangwa moja kipengele wakati huo, kushoto na kulia, na sisi kuhama mambo ya kufanya chumba. Mbaya zaidi kesi kukimbia wakati wa kuingizwa aina ni n squared. Bora kesi kukimbia wakati ni n. 

Kuunganisha sort-- keyword hapa ni kupasuliwa na kuunganisha. Sisi mgawanyiko safu kamili, iwe ni mambo sita, mambo nane, 10,000 elements-- sisi kupasuliwa chini kwa nusu, kwa nusu, kwa nusu, mpaka tuna chini ya safu ya n moja kipengele arrays. Seti ya n moja kipengele arrays. Hivyo sisi ilianza na moja 1,000 kipengele safu, na sisi kupata kwa uhakika ambapo sisi na 1,000 mmoja kipengele arrays. Kisha tunaanza kuunganisha arrays wale ndogo nyuma pamoja katika mpangilio sahihi. Kwa hiyo sisi kuchukua mbili arrays mmoja kipengele na kujenga mbili kipengele safu. Tunachukua mbili arrays mbili kipengele na kujenga nne kipengele safu na kadhalika na kadhalika mpaka tumekuwa tena upya moja n kipengele safu. 

Mbaya zaidi kesi kukimbia wakati wa kuunganisha aina ipo n mara logi n. Tuna mambo n, lakini mchakato huu recombining inachukua logi n hatua ya kupata nyuma kwa safu kamili. Kesi bora kukimbia wakati ni pia n gogo n kwa sababu mchakato huu haina kweli huduma kama safu alikuwa yamepangwa au si kuanza na. Mchakato ni sawa, kuna hakuna njia ya mambo mzunguko mfupi. Hivyo n logi n katika hali mbaya zaidi, n logi n katika kesi bora. 

Kuongelea mbili kutafuta algorithms. Hivyo tafuta linear ni kuhusu iterating. Sisi kuendelea katika safu mara moja, kutoka kushoto kwenda kulia, kujaribu kupata idadi kwamba sisi ni kuangalia kwa. Wakati mbaya zaidi kesi kukimbia ni O kubwa ya n. Inaweza kuchukua sisi iterating hela kila kipengele moja kupata kipengele sisi ni kuangalia kwa maana, ama katika nafasi ya mwisho, au si wakati wote. Lakini hatuwezi kuthibitisha kwamba mpaka tumekuwa inaonekana katika kila kitu. m bora kesi, tunaona mara moja. Bora kesi kukimbia wakati wa tafuta linear ni omega ya 1. 

Mwisho, kulikuwa na tafuta binary, ambayo inahitaji safu mbalimbali. Kumbuka kwamba sana muhimu kuzingatia wakati wa kufanya kazi na utafutaji mapacha. Ni sharti la kutumia it-- safu kwamba wewe ni kutafuta njia ya Lazima kutatuliwa. Vinginevyo, keyword ni mgawanyiko na kushinda. Kupasuliwa safu katika nusu na kuondoa nusu ya mambo kila wakati kama wewe kuendelea kwa njia ya. Kwa sababu ya mgawanyiko huu na kushinda na kugawanyika mambo katika njia nusu, mbaya zaidi kesi kukimbia wakati ya kutafuta binary ni kuingia n, ambayo ni kikubwa bora kuliko search ya linear n. Bora kesi kukimbia wakati bado ni moja. 

Tunaweza kukuta ni mara moja mara ya kwanza sisi kufanya mgawanyiko, lakini, tena, kumbuka kwamba ingawa search binary ni kikubwa bora kuliko tafuta linear kwa nguvu ya kuwa logi n dhidi n, unaweza kuwa na kwenda kwa njia ya kazi ya kuchagua safu yako ya kwanza, ambayo inaweza kufanya hivyo kutokuwa na ufanisi kulingana na ukubwa wa iterating yamepangwa. 

Mimi nina Doug Lloyd, hii ni CS50.