DOUG LLOYD: Deci, în CS50 am aflat despre o varietate de sortare și căutare algoritmi. Și, uneori, poate fi un pic cam complicat pentru a menține evidența a ceea ce algoritm ce face. Avem într-adevăr numai degresat suprafața le Există multe alte cautare și sortare algoritmi. Deci, în acest film să doar să ia câteva minute pentru a încerca și distila fiecare algoritm până la elementele sale de bază astfel încât să puteți aminti cel mai mult informații importante despre ele și să fie capabil de a articula diferențe, dacă este necesar. 

Primul este de selectare fel. Ideea de bază de selecție fel este găsi cel mai mic element nesortat într-o matrice și schimb cu prim element nesortate din matrice. Am spus că cel mai rău caz timp a alerga de care a fost n pătrat. Și dacă vrei să amintim de ce, ia o privire la video de selecție de sortare. Timpul de functionare mai bun caz este, de asemenea, n pătrat. 

Bubble sort, ideea din spatele care unul este de a schimba perechile adiacente. Deci, asta e cheia care vă ajută amintiți-vă diferența aici. Selecție fel este, până în prezent, găsi bubble smallest-- fel de swap este de perechi adiacente. Am schimba perechi adiacente de elemente în cazul în care sunt în afara de ordine, care în mod eficient bule elemente mai mari la dreapta, și, în același timp, începe de asemenea a muta elementele mici spre stânga. Timpul de caz run cel mai rău caz de bule fel este n pătrat. Timpul de functionare mai bun caz de bule fel este n. Pentru că în această situație noi nu actually-- nu poate fi necesar să face orice swap-uri, la toate. Trebuie doar pentru a face o treci peste toate elementele N. 

În sortare prin inserție, The idee de bază aici este schimbarea. Asta e cuvântul cheie pentru introducerea fel. Vom pas dată prin matrice de la stânga la dreapta. Și cum facem, suntem va schimba elemente am văzut deja pentru a face loc cele mai mici care au nevoie de a se potrivi undeva înapoi în acea parte sortate. Așa că am construi matrice sortate unul element de la un moment dat, la stânga la dreapta, și trecem lucruri pentru a face loc. Timpul de functionare cel mai rău caz de sortare prin inserție este n pătrat. Timpul cel mai bun caz a alerga este n. 

Merge sort-- cuvântul cheie aici este împărțit și îmbinare. Ne-am despartit matrice complet, dacă e șase elemente, opt elemente, 10.000 elements-- am împărțit jos cu jumătate, la jumătate, la jumătate, până când vom avea în gamă de n unul matrice de elemente. Un set de n o matrice de elemente. Așa că am început cu o Matrice de 1.000 elemente, si ajungem la punctul în care ne-am au 1.000 de matrice-un element. Apoi vom începe să fuzioneze aceste sub matrice din nou împreună în ordinea corectă. Deci, vom lua două rețele-un element și de a crea o gamă de două elemente. Luăm două matrici cu elemente de doi și de a crea o gamă de patru elemente și așa mai departe și așa mai departe, până când ne-am din nou reconstruit o matrice n elemente. 

Timpul de functionare cel mai rău caz de merge sort este de n ori log n. Avem n elemente, dar acest proces recombinarea ia log n pasi pentru a obține înapoi la o gamă completă. Cel mai bun caz de timp a alerga, de asemenea, n log n pentru că acest proces nu prea de îngrijire dacă matrice a fost sortate sau nu pentru a începe cu. Procesul este la fel, nu e nici o modalitate de a lucruri scurtcircuit. Deci n log n în cel mai rău caz, n log n în cel mai bun caz. 

Am vorbit despre doi căutare algoritmi. Deci căutare liniară este de aproximativ iterarea. Vom proceda în întreaga matrice o dată, de la stânga la dreapta, încercarea de a găsi numărul pe care le căutați. Timpul cel mai rău caz rula este O mare de n. Aceasta ne-ar putea lua iterarea peste fiecare singur element pentru a găsi elementul căutăm pentru, fie în ultima poziție, sau deloc. Dar nu putem confirma că până ne-am uitat la tot. m cel mai bun-caz, găsim imediat. Timpul de functionare cel mai bun caz de căutare liniară este omega 1. 

În cele din urmă, nu a fost de căutare binară, care necesită matrice asortate. Amintiți-vă că este un foarte element important atunci când se lucrează cu căutare binară. Este o condiție de a utiliza it-- matrice pe care o căutați prin trebuie să fie sortate. În caz contrar, cuvântul cheie este divide și cuceri. Împărțit matrice în jumătatea și elimina jumătate din elementele de fiecare dată așa cum ați proceda prin. Datorită acestui decalaj și cucerire și lucruri de despicare în jumătate de abordare, timpul de functionare cel mai rău caz de căutare binare este log n, care este în mod substanțial mai bine decât n căutare liniar. Timpul cel mai bun caz a alerga este încă una. 

S-ar putea găsi imediat prima dată am face o divizare, dar, din nou, amintiți-vă că deși căutare binară este substanțial mai bine decât căutarea liniară în virtutea faptului că log n față n, ar putea să aibă de a merge prin munca de sortare matrice întâi, care s-ar putea face mai puțin eficient, în funcție pe dimensiunea iterating sortate. 

Sunt Doug Lloyd, aceasta este CS50.