>> DOUG LLOYD: Takže CS50 sme sa dozvedeli o rôzne triedenie a vyhľadávanie
algoritmy.
A niekedy to môže byť trochu zložitejšie udržať
sledovať, čo robí, čo algoritmus.
Máme naozaj len sušeného povrchu príliš,
existuje mnoho ďalších vyhľadávanie a triedenie algoritmy.
Takže v tomto videu poďme len trvať niekoľko minút
vyskúšať a destilovať každý algoritmus až na jeho kľúčové prvky
takže si môžete pamätať najviac dôležité informácie o nich
a byť schopný formulovať rozdiely, pokiaľ je to nutné.
>> Prvý z nich je výber triediť.
Základnou myšlienkou výberom Triediť je nájsť najmenší netriedeného prvok
v poli a vymeniť ich s Prvý netriedený prvok tejto matice.
Povedali sme, že najhorší prípad bežať doba, ktorá bola n na druhú.
A ak si chcete pripomenúť, prečo, prijať Pozrite sa na výber triedenie videu.
Najlepšie-case run time je tiež n na druhú.
>> Bubble sort, myšlienka, že jeden je swap priľahlých párov.
Tak to je kľúč, ktorý vám pomôže spomenúť na rozdiel tu.
Výberom Triediť ich, tak ďaleko, nájsť smallest-- bublinu
Triedenie je swap priľahlých párov.
My swap priľahlých párov prvkov v prípade, že
sú mimo prevádzky, ktorý účinne bubliny väčší prvky na pravej strane,
a súčasne tiež začne pre pohyb menších prvkov na ľavej strane.
Najhorší prípad run time bublinkové druhu je n na druhú.
Najlepšie-case run time Bubble sort je n.
Pretože v tejto situácii nemáme actually--
by sme mohli nie je potreba žiadne swapy vôbec.
Máme len urobiť jednu prejsť cez všetky n prvkov.
>> V vloženie radenie, Základnou myšlienkou je tu mení.
To je kľúčové slovo pre vkladanie druhu.
Budeme krok raz prostredníctvom poľa zľava doprava.
A ako my, my sme sa k posunu prvkov
sme už videli, aby sa priestor pre tie menšie, ktoré potrebujú, aby sa zmestili niekde
späť v tomto zoradené časti.
Takže sme budovať zoradené poľa jedného prvok v čase, zľava doprava,
a posunieme veci, aby miestnosť.
Najhoršie run time of insertion sort je n na druhú.
Najlepšie-case spustiť n.
>> Zlúčiť sort-- kľúčové slovo Tu je rozdeliť a zlúčiť.
Rozdelili sme celé palety, či to je šesť prvkov, osem elementov,
10000 elements-- sme to rozdeliť dole o polovicu, na polovicu, na polovicu,
kým nebudeme mať v poli n jedného prvku poľa.
Sada n jedného prvku poľa.
Tak sme začali s jedným 1000-prvok poľa,
a dostaneme do bodu, keď sme majú 1000 jeden prvok poľa.
Potom sme začali zlúčiť tieto čiastkové polia dohromady v správnom poradí.
Takže zoberieme dva jedného prvku poľa a vytvoriť dve prvok poľa.
Berieme dva dva-prvkov poľa a vytvoriť štyri prvok poľa
a tak ďalej, a tak ďalej, až kým máme prestavaná jeden n prvku poľa.
>> Najhoršie run time of merge sort znamená n-krát log n.
Máme n elementy, ale tento proces rekombinantným
berie log n kroky na získanie späť na plnú pole.
Najlepšie prípad behu je tiež n log n preto, že tento proces nie je naozaj
jedno, či bol pole radené alebo nie začať.
Tento proces je rovnaký, je tu žiadny spôsob, ako skratu veci.
Takže n log n v najhoršom prípade, n log n v najlepšom prípade.
>> Hovorili sme o dva vyhľadávanie algoritmy.
Takže lineárne hľadanie je o iterácie.
Pokračujeme cez pole Raz, zľava doprava,
sa snaží nájsť číslo že hľadáme.
Najhoršie behu je veľký O n.
To môže trvať nás iterácie po každej jednotlivé súčasti
nájsť prvok, čo hľadáme pre, a to buď na poslednej pozícii,
alebo vôbec nie.
Ale nemôžeme potvrdiť, že kým Pozerali sme sa na všetko.
m najlepšie-prípad, nájdeme hneď.
Najlepšie-case beh čas lineárne vyhľadávanie je omegou 1.
>> Napokon, bolo binárne vyhľadávanie, ktorá vyžaduje rozmanité polia.
Pamätajte si, že je to veľmi dôležitým aspektom
Pri práci s binárne vyhľadávanie.
To je nevyhnutným predpokladom na používanie to-- pole, ktoré hľadáte skrz
musí byť radené.
V opačnom prípade kľúčové slovo je rozdeľ a panuj.
Rozdeľte pole do polovice a eliminovať polovica z prvkov
zakaždým, keď, ako budete postupovať cez.
Kvôli tejto rozdeľ a panuj a štiepanie veci v polovici prístupe,
najhorší prípad run time binárnych vyhľadávanie
log n, ktorá je v podstate lepšie ako lineárny hľadania v n.
Najlepšie-case behu je ešte jeden.
>> Mohli by sme ju okamžite nájsť Prvýkrát robíme divíziu, ale,
Znovu si uvedomte, že aj keď je binárny vyhľadávanie
podstatne lepší ako lineárny hľadanie z dôvodu, že log n oproti n,
možno budete musieť ísť cez prácu triedenie svoje pole ako prvý, čo
by mohol robiť to menej efektívne v závislosti o veľkosti iterácie zoradené.
>> Som Doug Lloyd, je to CS50.