>> DOUG LLOYD: Svo í CS50 við lærðum um a fjölbreytni af flokkun og leita
reiknirit.
Og stundum getur það verið a lítill erfiður til að halda
utan um hvað reiknirit gerir hvað.
Við höfum í raun aðeins undanrennu á yfirborðið líka,
það eru margir aðrir leita og flokkun reiknirit.
Þannig að í þessu myndbandi við skulum bara taka nokkrar mínútur
til að reyna að distill hvert reiknirit niður á meginþáttum hennar
svo þú getur muna mest mikilvægar upplýsingar um þá
og vera fær um að gera grein fyrir þeim munur, ef þörf krefur.
>> Í fyrsta lagi er val tegund.
Grunnhugmyndin á bak við val tagi er að finna minnstu óflokkuðu þáttur
í fjölda og skipta um það með Fyrsta Óflokkaður þáttur þessi fylking.
Við sögðum að versta hlaupa tími sem var n veldi.
Og ef þú vilt að muna hvers vegna, taka a líta á val röðun vídeó.
Besta falli hlaupa tími er einnig N veldi.
>> Kúla tegund, hugmyndin á bak við það einn er að skipta aðliggjandi pör.
Svo er það lykillinn sem hjálpar þér muna muninn hér.
Val tagi, svo langt, finna smallest-- kúla
tegund er Víxla aðliggjandi pör.
Við skipta samliggjandi pör staka ef þeir
eru í ólagi, sem í raun kúla stærri þætti til hægri,
og á sama tíma sem það tekur líka að færa smærri þætti til vinstri.
Versta tilfelli hlaupa tími af kúla tagi er n veldi.
Besta falli hlaupa tími af kúla tegund er n.
Vegna þess að í því ástandi við actually-- ekki
við gætum ekki að gera neinar skiptasamninga á öllum.
Við þurfum aðeins að gera eitt fara yfir öll n þáttum.
>> Í Innsetningarröðun er Grunnhugmyndin hér er að breytast.
Það er leitarorðið til innsetningu tagi.
Við erum að fara að stíga einu sinni í gegnum array frá vinstri til hægri.
Og eins og við gerum, við erum fara að skipta þætti
við höfum þegar séð að gera pláss fyrir minni sjálfur sem þarf að passa einhversstaðar
aftur í þeirri flokkað hluta.
Þannig að við að byggja raðaða array einn þáttur í einu, vinstri til hægri,
og við skipta hluti til að gera herbergi.
Versta hlaupa tími innsetning tegund er n veldi.
Besta falli hlaupa tími er n.
>> Sameina sort-- leitarorðinu hér er hættu og sameinast.
Við hættu fullt array, hvort það er sex þætti, átta þætti,
10.000 elements-- við hættu það niður um helming, um helming, um helming,
þar til við höfum undir array af n einn þáttur fylki.
A setja af n einn þáttur fylki.
Þannig að við byrjuðum með einn 1000-þáttur array,
og við fá til the benda hvar við hafa 1.000 eitt frumefni fylki.
Þá erum við að byrja að sameina þær undir fylki aftur saman í réttri röð.
Svo við tökum tvær eitt frumefni fylki og búa til tveggja-þáttur fylkisins.
Við taka tvær tveggja frumefni fylki og búa til fjögurra þátturinn array
og svo framvegis og svo framvegis þar til að við höfum aftur endurreist einn n þátturinn array.
>> Versta hlaupa tími sameinast tagi n sinnum log n.
Við höfum n þætti, en þetta recombining ferli
tekur log n skref til að fá baka að fullu fylki.
Besta ræða hlaupa tími er einnig n log n vegna þess að þetta ferli er í raun ekki
sama hvort array var raðað eða ekki til að byrja með.
Ferlið er það sama, það er engin leið að stuttum hlutum hringrás.
Svo n log n í versta tilfelli, n log n í besta tilfelli.
>> Við ræddum um tvo leita reiknirit.
Svo er línuleg leit um iterating.
Við halda áfram yfir í fylkinu einu sinni, frá vinstri til hægri,
reyna að finna fjölda sem við erum að leita að.
Versta hlaupa tími er stór O á n.
Það gæti tekið okkur iterating yfir hverjum einasta þætti
að finna þáttur sem við erum að leita fyrir, annað hvort í neðstu stöðu,
eða alls ekki.
En við getum ekki staðfest að fyrr við höfum litið á allt.
m besta falli, finnum við strax.
Besta falli hlaupa tími línuleg leit er omega af 1.
>> Loks var tvöfaldur leit, sem krefst blandað fylkisins.
Mundu það er mjög mikilvægt huga
þegar unnið er með tvöfaldur leit.
Það er forsenda þess að nota it-- array sem þú ert að leita í gegnum
verður flokkaður.
Annars leitarorðið er gjá og sigra.
Skipta array í tvennt og útrýma helmingur af þeim þáttum
í hvert skipti sem þú halda áfram í gegnum.
Vegna þessa skipta og sigra og skerandi hlutir í hálfa nálgun,
versta hlaupa tími af tvöfaldur leit er
log n, sem er að mestu leyti betri en n línuleg leit er.
Besta falli hlaupa tími er enn einn.
>> Við gætum fundið það strax fyrsta skipti sem við tökum deild, en
aftur, muna að þó tvöfaldur leit er
talsvert betri en línuleg leit í krafti þess að vera log n móti n,
þú gætir þurft að fara í gegnum vinnu að flokka array fyrst, sem
gæti gert það árangri minna eftir á stærð iterating flokkað.
>> Ég er Doug Lloyd, þetta er CS50.