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.