[Powered by Google Translate] [Tarkvaraprojekteerimise]
[Rob Bowden - Harvardi Ülikool]
[See on CS50. - CS50.TV]
Räägime ühendamise omamoodi.
Siiani olete näinud mull sorteerida, sisestamise sorteerida ning valik omamoodi.
Kuigi ma tulen mingi laine mu kätt, mida ma mõtlen parem,
liita omamoodi üldiselt toimib paremini kui ükski neist 3 kehvasti.
>> Aga enne räägi ühendamise sorteerida, räägime ühineva 2 järjestatud loendid.
Me helistame käigus võetakse 2 järjestatud loendid, nagu need,
ja teeb ühe järjestatud nimekirja läbi neist - ühineva nimekirju.
Kuidas me saame seda teha?
Noh, üks idee on lihtsalt kinni ühes nimekirjas koridori lõpus muu nimekiri
ja seejärel sortida saadud nimekirja.
>> Kuigi see toimib, see on palju asjatut tööd.
Me ei saa teha seda kiiremini kui lihtsalt sorteerimine.
Pange tähele, et üks vale idee on lihtsalt võtta vaheldumisi tassi igast loetelust.
Kuigi see võib tunduda, et tööde alguses,
teeme, et me lõpetame 4, 8, 15, 23, 16 - teade, et 16 ja 23 on kohatu.
Seda seetõttu, et 2 elementi, mis peaks ilmuma järjestikusel aastal ühinenud nimekiri
on samas esialgsest nimekirjast.
Mõlemad 15 ja 16 on vasakul olevast nimekirjast.
Trikk on ära asjaolu, et mõlemad nimekirjad on juba järjestatud.
See tähendab, et kui me lihtsalt vaatame esimest elementi mõlemad nimekirjad -
siin, 4 ja 8 - üks neist peab olema ka esimene osa ühinenud nimekirja.
Noh, miks see nii on?
Mõlemad nimekirjad on juba sorteeritud,
ja seda kas 4 või 8 peab olema väikseim element, kui me ühendame 2 on loetletud.
Sel juhul väikseim 4,
et saaksime välja 4 ja teha see esimene osa meie ühinenud nimekirja.
Nüüd jätkame ühinevad ülejäänud 3 elemendid esimese nimekirja
ja 4 elementi teise nimekirja.
>> Veelkord, meil on vaja ainult vaadata esimene osa mõlemas nimekirjas.
Väiksem 2 peab olema teine ​​osa meie ühinenud nimekirja.
Seekord vahemikus 8 ja 15. väikseim on 8, ja nii me lisada, et
kui teine ​​osa meie järjestatud nimekirja.
Me ei saa jätkata võrdle esimest elementi mõlema nimekirja
ja eemaldades väiksem 2.
Võrreldes 15 ja 23, 15 on väiksem ja et see on meie kolmas element.
Nüüd võrreldi 16 ja 23, 16 on väiksem.
Nii et neljas element.
>> Pange tähele, et 2 elementi tuli samas nimekirjas järjest.
See on põhjus, miks ühinenud nimekiri ei saa lihtsalt asendusliikme elemente 2 on loetletud.
Võrreldes 50 ja 23, 23 on väiksem, nii et me valime seda.
50 kuni 42, 42 on väiksem.
Vahemikus 50 ja 108, 50 on väiksem.
Ja lõpuks, me lihtsalt peame 108, nii et see peab minema lõpuni meie nimekirjas.
Pange tähele, et meil on kena, järjestatud nimekirja.
Iga kord, kui me võrreldes esimese 2 elemendid 2 on loetletud
suutsime kindlaks järgmise elemendi ühinemisel tekkinud nimekirja.
See tähendab, et kui lõplik nimekiri sisaldab n numbrid, kus n on siin 8,
siis peame ülimalt n võrdlusi saada kõik need numbrid õigesse kohta.
Selline algoritm on öelnud, et sõidetud lineaarset aega
kuid ärge muretsege, et siin.
>> Kasutades meie algoritm ühinevad, saame teha kiire ühendamise omamoodi algoritm.
Niisiis, oletame, reset meie nimekirju.
Seal on 2 suurt sammu protsessis ühendamise omamoodi.
Esiteks, pidevalt jagada nimekirja tassi pooleks
kuni meil on hunnik nimekirjad vaid 1 tass neid.
Ärge muretsege, kui loend sisaldab paaritu arv
ja te ei saa teha täiesti selgepiiriline nende vahel.
Lihtsalt suvaliselt valida, millist nimekirja lisada pildi tassi sisse
Niisiis, oletame, jagada neid nimekirju.
Nüüd meil on 2 nimekirju.
Nüüd on 4 nimekirju.
>> Ja nüüd meil on 8 nimekirjad ühe tassi iga nimekirja.
Nii et see on mu 1. etapp.
Sest 2.etapp, me korduvalt ühendada paari nimekirjad kasutades ühendamise algoritm oleme õppinud varem.
Ühinevad 108 ja 15, me lõpetame nimekiri 15, 108.
Ühinevad 50 ja 4, me lõpetame 4, 50.
Ühinevad 8 ja 42, me lõpetame 8, 42.
Ja ühineva 23 ja 16, me lõpetame 16, 23.
Nüüd kõik meie nimekirjad on suurusega 2.
Pange tähele, et iga 4 nimekirjad on sorteeritud.
>> Nii saame alustada ühinevad paari nimekirjad uuesti.
Ühinevad 15 ja 108 ja 4 ja 50 -
kõigepealt 4, siis 15, siis 50, siis 108.
Ühinevad 8, 42 ja 16, 23,
me esimest korda võtma 8, siis 16, siis 23, siis 42.
Nii et nüüd on meil vaid 2 nimekirjad suurus 4, millest igaüks on järjestatud.
Nii et nüüd me koondada need 2 on loetletud.
Esiteks võtame 4.
Siis võtame 8.
Siis võtame 15 ja 16, siis 23, siis 42, siis 50, siis 108.
Ja me oleme valmis.
Meil on nüüd järjestatud nimekirja.
Nii et kui kiiresti oli see täpselt?
Tehnilises mõttes ühendamise sorteerida on O (n log n),
arvestades, et kogu mull sorteerida, sisestamise sorteerida ning valik omamoodi on O (n ²).
Tegelikult, nagu te õpite kiiresti, sa ei saa tulla mingi
mis täidab paremini kui O (n log n) üldiselt juhul.
Jällegi, ärge muretsege see suur O notatsiooni kui sa ei ole näinud seda veel.
>> Lihtsalt tean, et see tähendab, kui me tahtsime sortida tõesti suur nimekiri
mull sorteerida, sisestamise sorteerida ning valik omamoodi võiks võtta
oluliselt pikem kui liita omamoodi.
See ei tähenda, et ühendamise omamoodi muutub kiiremaks kõigi nimekirjad
või isegi mõni üksik nimekirja teatud suurusest.
Näiteks sisestamise omamoodi olla kiireim omamoodi kõigi nimekirjade väiksem kui 5 elementi.
Praktikas ühendamise sorteerida on tavaliselt kiirem nimekirjad nii väike kui 50 elementi.
>> Aga see ekstra kiirust ei tule ilma hinnaga.
Erinevalt meie teistest kehvasti, mis võtavad nimekiri ja loetelu muutmiseks paigas
kuni saame järjestatud nimekirja, liita omamoodi vajab lisaruumi
ühendada 2 loetletakse koos.
Me ei saa kohe kasutada nimekirjad on ühendada salvestada ühinenud nimekiri
kuna me võiksime alistada elemente, mis tuleb veel liita.
See ala on natuke hind, kuid tavaliselt ei ole mõistlik.
Ja ongi kõik MERGE omamoodi.
>> Minu nimi on Rob Bowden, ja see on CS50.
[CS50.TV]
- Ja valik omamoodi.
[Naerab]
Oh, sain võtta, et liiga, sest ma vahetasin kuidas ma selle esitamine.
Nimekiri vasakul. See oli kirjaviga.
[Misspoke] Ma silmamunad -
[Naerab]
Ma ei tea, mida -