>> DOUG Lloyd: Niin CS50 me opimme erilaisia ​​lajittelu ja etsiminen
algoritmeja.
Ja joskus se voi olla hieman hankala pitää
kirjaa mitä algoritmin tekee mitä.
Olemme oikeastaan ​​vain rasvaton pinta liian,
on olemassa monia muita etsimistä ja lajittelualgoritmeja.
Joten tässä video nyt vain kestää muutaman minuutin
yrittää polttaa kukin algoritmi alas sen keskeiset osatekijät
joten voit muistaa eniten tärkeää tietoa niistä
ja pystyä ilmaisemaan erot, jos on tarpeen.
>> Ensimmäinen on valinta lajitella.
Perusajatuksena valinta lajitella on löytää pienin lajittelemattomat elementti
array ja vaihtaa sen kanssa ensimmäinen lajittelematon osa tätä array.
Sanoimme, että pahin ajoaika, joka oli n potenssiin.
Ja jos haluat muistaa miksi, ota katso valinta lajitella video.
Parhaassa tapauksessa ajoaika on myös n potenssiin.
>> Kuplalajittelu, ajatuksena että yksi on vaihtaa vieressä paria.
Niin se on avain, jonka avulla voit muistaa ero täällä.
Valinta lajitella on, toistaiseksi, löytää smallest-- kupla
SORT vaihtaa vieressä paria.
Me vaihtaa vieressä paria elementtien jos he
ovat epäkunnossa, joka tehokkaasti kuplia suurempi elementit oikealle,
ja samalla se myös alkaa siirtyä pienempiä osia vasemmalle.
Pahin tapaus ajoaika kupla lajitella on n potenssiin.
Parhaassa tapauksessa ajoaika kupla lajitella on n.
Koska tässä tilanteessa emme actually--
emme ehkä tarvitse tehdä swap ollenkaan.
Meillä on vain tehdä yhden siirtää kaikilla n elementtiä.
>> Vuonna lisäyslajittelun, Perusajatuksena tässä on siirtymässä.
Se avainsanan lisäyslajittelun.
Aiomme vaiheeseen kerran kautta array vasemmalta oikealle.
Ja kuten teemme, olemme menossa siirtää elementtejä
olemme jo nähneet tehdä tilaa pienempiä, jotka täytyy sovittaa jonnekin
takaisin että lajiteltu osaan.
Joten me rakennamme lajitellut array yksi elementti kerrallaan, vasemmalta oikealle,
ja siirrämme asioita tehdä tilaa.
Pahimman tapauksen ajoaika lisäyslajittelun on n potenssiin.
Paras-tapaus ajoaika on n.
>> Yhdistä sort-- avainsanan täällä on jakaa ja yhdistää.
Jaamme täyden valikoiman, onko se on kuusi elementtejä, kahdeksan elementtejä,
10000 elements-- me jakaa sen laskenut puoleen, puoleen, puoleen,
kunnes meillä on alle array n yksi elementti taulukot.
Joukko n yksi elementti taulukot.
Joten aloitimme yksi 1000-elementti array,
ja saamme siihen pisteeseen, jossa meillä on 1000 yksi-elementti paneelit.
Sitten alamme yhdistää niillä osa paneelit takaisin yhteen oikeassa järjestyksessä.
Joten otamme kaksi yhden elementin paneelit ja luoda kaksi-elementti array.
Otamme kaksi kahden alkion taulukot ja luoda neljän alkiotaulukon
ja niin edelleen ja niin edelleen, kunnes olemme taas uudelleen yksi n alkiotaulukko.
>> Pahimman tapauksen ajoaika yhdistää lajitella on n kertaa log n.
Meillä on n alkiota, mutta tämä rekombinaatiovälineen prosessi
panee log n askelta päästä Takaisin täyden valikoiman.
Parhaassa tapauksessa ajoaika on myös n loki n koska tämä prosessi ei oikeastaan
piittaa siitä array oli lajiteltu tai ei aloittaa.
Prosessi on sama, on olemassa mitenkään oikosulku asioita.
Joten n log n pahimmassa tapauksessa, n log n parhaassa tapauksessa.
>> Puhuimme kaksi hakuja algoritmeja.
Joten lineaarinen haku on noin iteroimalla.
Etenemme koko joukko kerran, vasemmalta oikealle,
yrittää löytää numero että etsimme.
Pahimman tapauksen ajoaika on iso O n.
Se voi viedä meidät iteroimalla poikki jokainen elementti
löytää elementti etsimme varten, joko viimeisessä asennossa,
tai ei lainkaan.
Mutta emme voi vahvistaa, että ennen teimme kaiken.
m parhaassa tapauksessa, löydämme heti.
Paras-tapaus ajoaika lineaarinen haku on omega 1.
>> Lopuksi nousi binäärihaku, joka vaatii valikoituja array.
Muista, että on hyvin tärkeä näkökohta
kun työskentelet binäärihakupuu.
Se on edellytys käyttäen it-- array että etsit kautta
pitää lajitella.
Muuten avainsana on hajota ja hallitse.
Jakaa array osaksi puoli ja poistaa puolet elementit
joka kerta kun jatkat kautta.
Tämän vuoksi hajoita ja hallitse ja halkaisu asioita puoli lähestymistapa,
pahimman tapauksen ajoaika binary haku on
log n, joka on olennaisesti parempi kuin lineaarinen haku n n.
Paras-tapaus ajoaika on edelleen yksi.
>> Voisimme löytää sen heti Ensimmäistä kertaa teemme jako, mutta,
jälleen, muista, että vaikka binary haku on
huomattavasti parempi kuin lineaarinen haku sen perusteella, että log n vs. n,
saatat joutua käydä läpi työn lajittelu matriisisi ensimmäinen, joka
voisi tehdä sen vähemmän tehokas riippuen koosta iteroimalla lajiteltu.
>> Olen Doug Lloyd, tämä on CS50.