>> DOUG LLOYD: Takže CS50 jsme se dozvěděli o různé třídění a vyhledávání
algoritmy.
A někdy to může být trochu složitější udržet
sledovat, co dělá, co algoritmus.
Máme opravdu jen sušeného povrchu příliš,
existuje mnoho dalších vyhledávání a třídění algoritmy.
Takže v tomto videu pojďme jen trvat několik minut
vyzkoušet a destilovat každý algoritmus až na jeho klíčové prvky
takže si můžete pamatovat nejvíce důležité informace o nich
a být schopen formulovat rozdíly, pokud je to nutné.
>> První z nich je výběr třídit.
Základní myšlenkou výběrem Třídit je najít nejmenší netříděného prvek
v poli a vyměnit je s První netříděný prvek této matice.
Řekli jsme, že nejhorší případ běžet doba, která byla n na druhou.
A pokud si chcete připomenout, proč, přijmout Podívejte se na výběr třídění videu.
Nejlepší-case run time je také n na druhou.
>> Bubble sort, myšlenka, že jeden je swap přilehlých párů.
Tak to je klíč, který vám pomůže vzpomenout na rozdíl zde.
Výběrem Třídit je, tak daleko, najít smallest-- bublinu
Třídění je swap přilehlých párů.
My swap přilehlých párů prvků v případě, že
jsou mimo provoz, který účinně bubliny větší prvky na pravé straně,
a současně také začne pro pohyb menších prvků na levé straně.
Nejhorší případ run time bublinkové druhu je n na druhou.
Nejlepší-case run time Bubble sort je n.
Protože v této situaci nemáme actually--
bychom mohli není potřeba žádné swapy vůbec.
Máme jen udělat jednu projít přes všechny n prvků.
>> V vložení řazení, Základní myšlenkou je zde mění.
To je klíčové slovo pro vkládání druhu.
Budeme krok jednou prostřednictvím pole zleva doprava.
A jako my, my jsme se k posunu prvků
jsme již viděli, aby se prostor pro ty menší, které potřebují, aby se vešly někde
zpět v tomto seřazené části.
Takže jsme budovat seřazené pole jednoho prvek v době, zleva doprava,
a posuneme věci, aby místnost.
Nejhorší run time of insertion sort je n na druhou.
Nejlepší-case běhu n.
>> Sloučit sort-- klíčové slovo Zde je rozdělit a sloučit.
Rozdělili jsme celé palety, zda to je šest prvků, osm elementů,
10000 elements-- jsme to rozdělit dolů o polovinu, na polovinu, na polovinu,
dokud nebudeme mít v poli n jednoho prvku pole.
Sada n jednoho prvku pole.
Tak jsme začali s jedním 1000-prvek pole,
a dostaneme do bodu, kdy jsme mají 1000 jeden prvek pole.
Pak jsme začali sloučit tyto dílčí pole dohromady ve správném pořadí.
Takže vezmeme dva jednoho prvku pole a vytvořit dvě prvek pole.
Bereme dva dva-prvků pole a vytvořit čtyři prvek pole
a tak dále, a tak dále, dokud máme přestavěna jeden n prvku pole.
>> Nejhorší run time of merge sort znamená n-krát log n.
Máme n elementy, ale tento proces rekombinantním
bere log n kroky k získání zpět na plnou pole.
Nejlepší případ běhu je také n log n proto, že tento proces není opravdu
jedno, jestli byl pole řazeny nebo ne začít.
Tento proces je stejný, je tu žádný způsob, jak zkratu věci.
Takže n log n v nejhorším případě, n log n v nejlepším případě.
>> Mluvili jsme o dva vyhledávání algoritmy.
Takže lineární hledání je o iterace.
Pokračujeme přes pole Jednou, zleva doprava,
se snaží najít číslo že hledáme.
Nejhorší běhu je velký O n.
To může trvat nás iterace po každé jednotlivé součásti
najít prvek, co hledáme pro, a to buď na poslední pozici,
nebo vůbec ne.
Ale nemůžeme potvrdit, že dokud Dívali jsme se na všechno.
m nejlepší-případ, najdeme hned.
Nejlepší-case běh čas lineární vyhledávání je omegou 1.
>> A konečně, bylo binární vyhledávání, která vyžaduje rozmanité pole.
Pamatujte si, že je to velmi důležitým aspektem
Při práci s binární vyhledávání.
To je nezbytným předpokladem k používání to-- pole, které hledáte skrz
musí být řazeny.
V opačném případě klíčové slovo je rozděl a panuj.
Rozdělte pole do poloviny a eliminovat polovina z prvků
pokaždé, když, jak budete postupovat přes.
Kvůli této rozděl a panuj a štípání věci v polovině přístupu,
nejhorší případ run time binárních vyhledávání
log n, která je v podstatě lepší než lineární hledání v n.
Nejlepší-case běhu je ještě jeden.
>> Mohli bychom ji okamžitě najít Poprvé děláme divizi, ale,
Znovu si uvědomte, že i když je binární vyhledávání
podstatně lepší než lineární hledání z důvodu, že log n oproti n,
možná budete muset jít přes práci třídění své pole jako první, což
by mohl dělat to méně efektivní v závislosti o velikosti iterace seřazeny.
>> Jsem Doug Lloyd, je to CS50.