Doug LLOYD: Torej, v CS50 smo se naučili o različne sortiranje in iskanje algoritmi. Včasih je lahko malo zapleteno, da Spremljajte kaj algoritem počne kaj. Smo v resnici le posneto površino preveč, Obstaja veliko drugih Iskanje in algoritmov. Torej, v tem videu pa si vzemite nekaj minut poskusiti in destilirati vsak algoritem navzdol, da njenih ključnih elementov tako da se lahko spomnite najbolj pomembne informacije o njih in biti sposoben artikulirati razlike, če je potrebno. 

Prvi je izbira vrste. Osnovna ideja za izbor vrste je najti najmanjšo neurejen element v niz in ga zamenjali z prvi neprebrani element te matrike. Rekli smo, da je najslabši teči čas, da je n kvadrat. In če želite, da se spomni, zakaj bi poglej na izbor sort video. Čas teče najboljšem primeru tudi n kvadrat. 

Bubble razvrščanje, ideja, ki ena je, da swap sosednjih parov. Tako, da je ključno, da vam pomaga spomnite razliko tukaj. Izbor vrste je, doslej, najti smallest-- mehurček razvrščanja je swap sosednjih parov. Mi swap sosednjih parov elementov, če jih so v okvari, ki dejansko mehurčki večje elemente v desno, in hkrati pa tudi začne premakniti manjših elementov v levo. Najslabši čas v primeru run mehurčkov vrste je n kvadrat. Čas teče najboljšem primeru od balona je nekako n. Ker je v tej situaciji ne bomo actually-- ne bomo morda morali kakršno koli zamenjavo sploh. Imamo le narediti eno mimo vseh n elementov. 

V vstavitve vrste je Osnovna ideja tu se premikajo. To je ključna beseda za vstavljanje vrste. Bomo enkrat korak skozi array od leve proti desni. In kot mi, mi smo tekoč premik elementov smo že videli, da bi naredili prostor za manjših, ki jih je nekje fit nazaj v tej razvrščeni delu. Tako gradimo urejen paleto ena element naenkrat, od leve proti desni, in smo premik stvari, da bi naredili prostor. Čas najslabšem primeru tek Vstavitev vrsta je n kvadrat. Čas najboljšem primeru teči n. 

Spoji sort-- ključno besedo tukaj se razdeli in združiti. Razdelili smo celotno paleto, ali to je šest elementov, osem elementov, 10.000 elements-- smo ga razdelili navzdol za polovico, za polovico, za polovico, dokler ne bomo imeli pod paleto n ene nizi elementov. Niz n enim nizi elementov. Tako smo začeli z eno 1000-element matrika, in smo prišli do točke, kjer smo imajo 1.000 nizi eno sestavljeno. Potem smo začeli spajanje teh sub nize spet skupaj v pravilnem zaporedju. Tako smo vzeli dva nizi eno sestavljeno in ustvariti niz dveh elementov. Peljemo dva nizi dvodelne in ustvariti niz štiri-element in tako naprej in tako naprej, dokler smo jih spet obnovili eno n element array. 

Čas najslabšem primeru tek zlivanjem je n krat log n. Imamo n elementov, vendar ta proces rekombinacija traja log n korakih, da bi dobili nazaj na polno paleto. Najboljši primer teči čas je tudi n log n ker je ta proces v resnici ne skrbi, ali je bil niz razporejene ali ne, za začetek. Postopek je enak, tam noben način kratkega stika stvari. Torej n log n v najslabšem primeru, n log n v najboljšem primeru. 

Pogovarjali smo se o dveh iskanje algoritmov. Torej linearno iskanje je približno ponavljanjem. Bomo nadaljevali čez polja enkrat, od leve proti desni, poskuša najti številko da iščemo. Najslabši primer teči čas je velik O n. Morda nas bo ponavljanjem po vsakem posameznem elementu poiščite element, ki ga iščemo za bodisi v zadnjem položaju, ali pa sploh ne. Vendar ne moremo potrditi, da dokler smo pogledal vse. sem v najboljšem primeru, najdemo takoj. Čas najboljšem primeru tek linearna iskanje je omega 1. 

Nazadnje je bilo binarno iskanje, ki zahteva urejene paleto. Ne pozabite, da je zelo pomemben dejavnik Pri delu z binarno iskanje. To je predpogoj za uporabo it-- matrika, ki jo iščete s pomočjo morajo biti razporejene. Sicer pa je ključna beseda je deli in vladaj. Razdeli niz na pol in odpravo polovica elementov vsakič, ko se nadaljuje skozi. Zaradi tega Deli in vladaj in delitve stvari v pol pristopa, čas delovanja najslabšem primeru z binarno iskanje je log n, ki je v bistvu bolje kot linearne Iskanje je n. Čas najboljšem primeru teče še ena. 

Lahko bi ga takoj našli prvič naredimo delitev, vendar, še enkrat, ne pozabite, da čeprav binarno iskanje je bistveno bolje kot linearni iskanju ki jih zaradi tega, ker log n versus n, boste morda morali iti skozi delo sortiranja svojo paleto prvi, ki Morda bi bilo manj učinkovito, odvisno o velikosti ponavljanjem razvrščeni. 

Sem Doug Lloyd, to je CS50.