DOUG LLOYD: Així que en CS50 vam aprendre sobre una varietat de classificació i recerca algoritmes. I de vegades pot ser una mica difícil de mantenir la pista del algoritme fa què. Tenim realment només fregat la superfície també, hi ha moltes altres cerca i algoritmes d'ordenació. Així que en aquest vídeo anem a simplement prendre un parell de minuts per intentar destil·lar cada algoritme fins en els seus elements bàsics perquè pugui recordar més informació important sobre ells i ser capaç d'articular el diferències, si cal. 

La primera és l'ordenació per selecció. La idea bàsica d'ordenació per selecció es troba l'element més petit sense classificar en una matriu i canviar amb el primer element sense classificar d'aquesta matriu. Hem dit que el pitjor dels casos temps d'execució que es n al quadrat. I si vols recordar per què, pren un cop d'ull al vídeo ordenació per selecció. El temps d'execució millor dels casos També està n al quadrat. 

Bombolla espècie, la idea darrere d'aquesta un és per intercanviar parells adjacents. Així que aquesta és la clau que l'ajuda recordar la diferència aquí. Selecció espècie, és a dir, fins al moment, trobar la bombolla smallest-- és un gènere intercanviar parells adjacents. Vam intercanviar parells adjacents d'elements si estan fora de servei, el que efectivament bombolles elements més grans a la dreta, i, al mateix temps, també comença per moure elements més petits a l'esquerra. El pitjor dels casos el temps d'execució cas d'ordenament de bombolla està n al quadrat. El temps d'execució millor dels casos d'ordenament de bombolla és n. Perquè en aquesta situació no actually-- pot ser que no hagi de fer els bescanvis en absolut. Només hem de fer-ne un passar a través de tots els elements n. 

En l'ordenació per inserció, la idea bàsica que aquí s'està desplaçant. Aquesta és la paraula clau per l'ordenació per inserció. Anem a entrar una vegada a través la matriu d'esquerra a dreta. I mentre ho fem, estem canviarà els elements ja hem vist per fer espai per més petits que necessiten per encaixar en algun lloc de tornada a aquesta porció ordenats. Així construïm la matriu ordenada d'un element a la vegada, d'esquerra a dreta, i canviem les coses per fer espai. El temps d'execució del pitjor cas de ordenació per inserció està n al quadrat. El temps millor dels casos de gestió és n. 

Combinar sort-- la paraula clau aquí és dividir i combinar. Dividim la gamma, ja sigui és de sis elements, vuit elements, 10000 elements-- ho dividim pel mig, pel mig, pel mig, fins que tinguem sota array de n conjunts d'elements d'un. Un conjunt de n 1 conjunts d'elements. Així que vam començar amb un sol 1000-element de la matriu, i arribem al punt en què té 1.000 matrius d'un element. Llavors vam començar a combinar aquestes matrius sub de nou junts en l'ordre correcte. Així que prenem dos conjunts d'un sol element i crear una matriu de dos elements. Prenem dues matrius de dos elements i crear una matriu de quatre elements i així successivament i així successivament fins que haguem novament reconstruït una matriu n element. 

El temps d'execució del pitjor cas de fusionen espècie és n vegades log n. Tenim n elements, però aquest procés recombinació pren log n passos per arribar còpia d'un arsenal complet. El millor dels casos el temps d'execució és també n log n perquè aquest procés en realitat no importa si la matriu era ordenats o no, per començar. El procés és el mateix, no hi ha no hi ha manera de coses de curtcircuit. Així n log n en el pitjor dels casos, n log n en el millor dels casos. 

Parlem de dos buscar algoritmes. Així que la recerca lineal és sobre la iteració. Procedim a través de la matriu una vegada, d'esquerra a dreta, tractant de trobar el nombre que estem buscant. El temps en el pitjor cas és executar gran O de n. Ens podria prendre la iteració a través de cada element per trobar l'element que estem buscant per, ja sigui en l'última posició, o res en absolut. Però no podem confirmar que fins hem vist tot. sóc el millor dels casos, ens trobem immediatament. El temps d'execució millor dels casos de cerca lineal és l'omega d'1. 

Finalment, va haver de recerca binària, que requereix gamma variada. Recordeu que és una molt consideració important quan es treballa amb recerca binària. És un requisit previ per a l'ús de it-- la matriu que està mirant a través de han de ser ordenats. Altrament, la paraula clau és divideix i venceràs. Dividir la matriu en la meitat i eliminar la meitat dels elements cada vegada que a mesura que avanci a través. A causa d'això divideix i venceràs i les coses de divisió en mig enfocament, el temps d'execució del pitjor cas de recerca binària és log n, que és substancialment millor que la recerca lineal n. El temps millor dels casos de gestió segueix sent un. 

Podríem trobar immediatament el primera vegada que fem una divisió, però, de nou, recordar que tot i que la recerca binària és substancialment millor que la recerca lineal en virtut de ser log n enfront de n, és possible que hagi de passar per la feina d'ordenar la matriu primera, que podria fer que sigui menys eficaç depenent en la mida de la iteració ordenats. 

Sóc Doug Lloyd, això és CS50.