[REPRODUCCIÓ DE MÚSICA] 

DAVID J. Malan: Aquest és CS50. I aquest és el començament de la tercera setmana. Així que tenim un munt d'emocionants coses que cobreixen l'actualitat. Una gran quantitat d'oportunitats per els voluntaris a l'escenari. I en última instància, en l'actualitat és No es tracta de codi. Però es tracta d'idees i es tracta d'algoritmes, i de fet portar de tornada alguns les lliçons apreses de la setmana zero, on record, ens introduït aquesta monstruositat. I l'endeutament inspiració que, per començar per resoldre cada vegada més sofisticada problemes algorítmicament. Però primer, un parell d'anuncis. Així que un, si vol unir-se El personal i els companys de classe de CS50 en el dinar aquest divendres, tant aquí com a Cambridge, ia New Haven, si us plau visiti el curs de lloc web, on un URL es pot trobar. Conferència d'aquest dimecres serà no ser aquí a Sanders. Serà només en línia, de manera que sintonitzar al lloc web de l'CS50, ja sigui aquí a Cambridge o New Haven també. 

I llavors un problema fixar dos ja és a les teves mans. Si no ha bussejat en el, però, permetin-me per oferir el suggeriment enèrgica que, sobretot ara, quan el problema estableix per avançat, vostè realment vol començar ara, si no incursionar una mica en el cap de setmana o abans la primera vegada que surten a Divendres, perquè vas a troben que no són necessàriament cada vegada més llargs o més desafiant per es. Crec que trobareu que, en en general, tendeixen a tenir més o menys voltant mateixa quantitat de temps. Però certament depèn en l'estudiant, i depèn de la mentalitat amb la qual t'acostes a ella. Però invariablement, vas córrer contra alguna paret, i vas a colpejar alguns errors, i no ets més que no serà capaç de superar-ho en algun moment. I és enormement valuosa per poder allunyar-se, tornar al dia següent, anar a les hores d'oficina, missatge l'CS50 Discutiu o similar, per aconseguir realment desbloquejat. Així que tingues-ho en compte. Començant d'hora com sigui possible és la millor cosa que pots fer. Així que aquí és on vam començar la classe, al llarg de la setmana zero. I podem aconseguir un voluntari aquí per ajudar-me a trobar els micròfons? D'ACORD. Dempeus ja. Anem cap amunt. Suposo que això és el que va a treballar. Com et dius? ALAN ESTRADA: Alan Estrada. DAVID J. Malan: Alan Estrada. Anem cap amunt. Encantat de conéixer-te. ALAN ESTRADA: Encantat de conèixer-te. DAVID J. Malan: I vostè estigués aquí amb nosaltres en la setmana zero, és clar. ALAN ESTRADA: jo. Jo era. 

DAVID J. Malan: Així podria anar endavant i trobar per a nosaltres Mike Smith, tan ràpid com sigui possible? Tan ràpid com puguis. Literalment estripar el problema a la meitat del que necessita. 

ALAN ESTRADA: Um. DAVID J. Malan: Literalment esquinçant el problema al mig. 

ALAN ESTRADA: Oh. Mm. Molt bé. 

DAVID J. Malan: OK. Bé. Gràcies. ALAN ESTRADA: Molt bona. D'ACORD. 

DAVID J. Malan: I pel que ara, que ha retallat cap avall a la meitat de la mida del problema. Ara, estem a una quarta part. Vostè està prestant atenció a de quin costat estem mantenint? 

[El] 

ALAN ESTRADA: Sí, jo think-- 

DAVID J. Malan: Quina secció estem? ALAN ESTRADA: Mofles, així. 

DAVID J. Malan: OK. Però Mike Smith va a ser després de Mofles. Tan-- 

[El] 

Tot bé. ALAN ESTRADA: On estem buscant? DAVID J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. Malan: Ara, estem en quirúrgic. Ara, els metges. Ara-- 

ALAN ESTRADA: Let's- anem amb real. Real. 

DAVID J. Malan: Real. D'ACORD. Si necessita Real. Ara, quin camí és Mike Smith? 

ALAN ESTRADA: D'aquesta forma. 

DAVID J. Malan: Quina manera? ALAN ESTRADA: Espera. Dret M és--? Comencem con-- 

DAVID J. Malan: Sí. Estan a l'esquerra. El seu dret. 

ALAN ESTRADA: Sí. 

DAVID J. Malan: Així que Mike aquí. ALAN ESTRADA: Què? 

[El] 

Mal exemple, nois. Ho sento. DAVID J. Malan: Això li ensenyarà a saltar de la cadira. 

ALAN ESTRADA: Oh. Oh. Et tinc. Et tinc. Oh. Oh. Aquesta és-- Bé, et tinc. Smith aquí? 

DAVID J. Malan: Smith, gràcies. Així que seguiré mirant cap amunt Smith? 

ALAN ESTRADA: Oh, sí. No no No. Oh no. Això és meu. 

DAVID J. Malan: Oh, tens Smith. D'ACORD. 

ALAN ESTRADA: Sí, Smith va aconseguir aquí. Ho sento, nois. Vaig pensar que Michael-- estaves buscant Michael. Ho sento. 

DAVID J. Malan: Està bé. Molt bé, ara estem en Paccini and Sons. 

ALAN ESTRADA: Paccini i fills. DAVID J. Malan: Només vostè i jo estem en això. D'ACORD. Trobeu-nos Mike Smith. Smith. 

ALAN ESTRADA: Smith. 

DAVID J. Malan: Smith. Estem en R per a escombraries. ALAN ESTRADA: Malo. Oh. Això va a prendre un temps. 

[El] DAVID J. Malan: Sabates. Estem en les sabates. 

ALAN ESTRADA: Ara estem gonna-- 

DAVID J. Malan: Niça. ALAN ESTRADA: Which-- [El] Oh, això és genial. [El] 

DAVID J. Malan: Està bé. 

ALAN ESTRADA: Oh, això és bo. No crec que em vaig a tenir amics PSAT després d'això. DAVID J. Malan: Good. Sporting. ALAN ESTRADA: Sporting. Um, L, M, N, O, P. DAVID J. Malan: OK. Així que anem a llàgrima això enmig. Està bé. Això acaba malament de totes maneres, perquè Mike Smith no estarà a les pàgines grogues. 

ALAN ESTRADA: Aw. 

DAVID J. Malan: No, està bé. Però anem a suposar com ell està en aquesta pàgina. Així que ara, vostè ha retallat el problema baix d'una pàgina, i ens trobem amb Mike Smith. 

[ANIMA] D'acord, gràcies. D'ACORD. Això va ser extraordinari. Però va ser encara més ràpid de recerca lineal, en què vam començar a a partir del llibre, i ens movem la nostra forma d'esquerra a dreta, finalment, a la recerca de Mike Smith. I així, si la guia telefònica tenia potser 1.000 pàgines, potser hauria pres ens 10 o més pàgines llàgrimes. 

Però és possible que hagi aprofitat tocat una suposició durant tot això, el que és a dir, que la guia de telèfons per endavant era què? AUDIÈNCIA: Ordenat. DAVID J. Malan: Ha solucionat. Oi? S'ordena alfabèticament, per la qual que tots aquests noms i números estan ordenades pels Atlètics a la Z, i en ordre alfabètic en el medi. Però avui en dia, ens preguntem ara la pregunta, bé, Com Verizon o el telèfon empresa posar-lo en aquest estat? 

A causa que és una cosa d'aprofitar aquesta suposició, i per tant, resoldre un problema amb un algoritme més eficient. Però en realitat mai demanat a la setmana zero, bé, Quant costa Verizon o algú més per aconseguir que la llibreta de telèfons en forma ordenada? 

Oi? No importa si mirant cap amunt Mike Smith és súper ràpid, si vostè pren un any per ordenar les pàgines inicialment. Oi? Vostè pot ser que també acaba de tamisar a través d'un llibre de telèfon a l'atzar, si va a ser súper cara a solucionar el problema. Així que si podem tenir un altre voluntari. Anem a fer una ullada aquí a com might-- Anem up-- com podríem anar sobre la classificació dels mateixos. 

I si Jordan podia realitat uneix-te a nosaltres aquí a l'escenari. Anem cap amunt per un moment. Com et dius? CAROLINE: Caroline. DAVID J. Malan: Caroline, anem cap amunt. I es et vas unir per mi i Jordània aquí. Caroline, gràcies. Tot bé. Així que el que tenim aquí Caroline té 26 llibres blaus que FAS utilitza per administrar certs exàmens finals. Aquests són cada vegada difícil de trobar, però el que hem fet amb antelació és que ens hem posat el nom d'algú a la part frontal de cada un d'aquests, però ens hem mantingut simple a continuació, posar els noms complets. Així que ens agradaria posar a la persona amb el nom A, C, J, B, fins al final de l'A a la Z, però estan en ordre aleatori. I pel que si ho faria, parlant de la seva camí a través dels problemes i se li fes-ho, pot seguir endavant i ordenar aquests per a nosaltres, de la A a la Z. 

AUDIÈNCIA: OK, llavors L és com, el medi. C està començant. B. J abans de L. B, Q. 

DAVID J. Malan: Mantingui aquesta pensat per un segon. Perquè en cas contrari, això és només interessant per a vostè, jo, i Jordània. Cal anar. AUDIÈNCIA: [inaudible]. R. DAVID J. Malan: OK. Què fas? 

CAROLINE: M es produeix després d'O 

DAVID J. Malan: OK. 

CAROLINE: O. DAVID J. Malan: O, bo. 

CAROLINE: E. 

DAVID J. Malan: I, F. Sí. 

CAROLINE: T, U, V. 

DAVID J. Malan: V, T, U, V. Per tant, Sembla que ets making-- seguir endavant. Sembla que estàs fent una pica gran aquí, i la classe d'una gran pila d'allà. Així que la primera meitat de l'alfabet, segona meitat de l'alfabet. D'ACORD. Bé. Tipus de dividir el problema en dues. M, N, X. Sí. CAROLINE: K. DAVID J. Malan: OK. K. Així que estàs tipus de selecció un darrere l'altre, posant-ho a l'esquerra oa la dreta, o Z va a terra. D'ACORD. 

CAROLINE: Z va a terra. 

DAVID J. Malan: OK. I va a terra. Ara podem posar X. 

CAROLINE: G. DAVID J. Malan: G va a l'esquerra. S va bé. Tot dret, A va tot el camí de l'esquerra. 

CAROLINE: A, B, C, D. 

DAVID J. Malan: Ara, bé. Tenim A, B, C. W d'anar-hi. Molt bé, T. 

CAROLINE: H, I, J. DAVID J. Malan: H, I, J. Bueno. CAROLINE: Al centre, estic gonna-- DAVID J. Malan: OK. Així que ara, anem a classe de combinar aquests diversos munts. Així la A a C, llavors veig D, i E i F, i G, i H i I. Niça. J, K. I després, aquesta pila és a l'inrevés, però això està bé. És clar. Podem tallar algunes cantonades. D'ACORD. I llavors hem de W, X, Y, Z. 

CAROLINE: Sí. 

DAVID J. Malan: Excel·lent. Així que un gran agraïment a Caroline per a la classificació d'aquests. 

[ANIMA] 

Gràcies. Moltes gràcies. Així que ara considerarem per un moment com Caroline va estar fent això, i què és exactament el que van ser capaços A-- com van ser capaços de resoldre aquest problema quan estàvem donat un munt d'entrades aleatòries. 

Bé, sembla que hi ha era una mica d'un sistema allà? Dreta. Així que les cartes anteriors en l'alfabet, ella era posar a l'esquerra, i el últimes cartes en l'alfabet, que estava posant en la dreta. I tan aviat com es va assabentar algunes cartes proximals, uns que van un al costat de l'altre, posaria els d'ordre. I pel que d'alguna manera tenia aquests petits munts de entrades ordenades ocorren. 

I això és molt semblant al que la majoria de nosaltres els humans farien. Ens tipus de tamisar a través d'ell, i ens agradaria tipus de disposar d'un mecanisme. Però podria ser difícil escriure cap avall en una fórmula per se. Se sentia una mica més orgànic que això. Així que anem a veure si podem ara lligat el problema amb menys recursos. 

En lloc de 26, anem a fer alguna cosa molt menys amb només dir, set, darrere aquestes portes, per així dir-ho. Hi ha només set números? I si l'objectiu ara en mà és trobar un valor, anem a veure com de manera eficient podem anar fent això. I anem a veure si podem ara començar a aplicar alguns números, o algunes fórmules amb les que descriuen l'eficiència del nostre directori telefònic algoritme, el nostre algoritme llibre examen, i més en general, la recerca d'informació. 

Així que per això, deixar-me anar per davant, i a la pantalla tàctil per aquí, posar un navegador web que té exactament aquestes set portes. I si poguéssim aconseguir un altre voluntaris per venir per aquí, He posat aquestes mateixes portes aquí. Voluntari ràpida. 

Aquest un-- donem van a un més ràpid i més ràpid ara. Anem cap avall. Com et dius? TREVOR: Trevor. 

DAVID J. Malan: Trevor? Molt bé, Trevor, anem cap avall. Així que Trevor s'ha ofert aquí per fer un problema similar, però un que és més estret en el seu abast, i això va que ens permeti tractar de formalitzar ara el procés per a la classificació d'aquests nombres. 

Així Trevor, encantat de conèixer-te. Així que aquí és una matriu, de manera que parlar, una llista de set portes. Vagi per davant i ens trobarà al número 50. I a continuació, després del fet, nos saber com ho vas trobar. En cas de ser-- bé. Sí, aquest és el que aquí? UH oh. D'ACORD. Va fer clic en aquesta. Bé. 

I bé. Ara ha fet clic en aquest. I et donaré el micròfon, de manera que vostè ho té en un moment. Seguiu endavant i feu clic al al costat que té la intenció. Sí, bé. TREVOR: Puc desmarca una porta? DAVID J. Malan: No, no pots desmarcatge. TREVOR: OK. Aquest. DAVID J. Malan: On vols anar? Quin? 

TREVOR: Que un. 

DAVID J. Malan: No. 

TREVOR: OK. Aquest. 

DAVID J. Malan: Sí. Això era bo. Tot bé. Llavors, quin era el seu algoritme o procediment per fer això, Trevor? 

TREVOR: M'acaba de passar per portes fins que van trobar un 50. DAVID J. Malan: OK. Excel·lent algoritme. Així que això està bé. Perquè, de fet, si revelo el que és darrere d'aquestes altres dues portes, el que trobarem aquí és que només tenim entrada aleatòria. Així que va ser realment com bo com es pot aconseguir. I de fet, tens millor que exhaustivament buscant tot el conjunt, perquè hauria estat molt mala sort si s'hagués colpejat el nombre 50 en l'últim costat. Però ¿i si en lloc et va donar una suposició. Suposem que en certa manera em tots aquestes portes de tot, quedant amb la números ordenats en aquesta ocasió, però aquesta vegada és en realitat 1 diferent-- aquest temps, en realitat està ordenada per a vostè. I ara el perill a la mà és per colpejar el nombre 50. 

TREVOR: OK. 

DAVID J. Malan: Quin és l'algoritme serà? 

TREVOR: Bé, si és ordenats, és ben va a ser-- si major a major, descendent, va ser el primer, o si és tot el contrari, serà l'última. Així que vaig a tocar a la porta, i a continuació, només tocar l'última porta. DAVID J. Malan: Excel·lent. Tot bé. Així que trobem el número 50. Així que tan aviat com vostè sabia van ser ordenats, ens van ser capaços d'aprofitar aquesta suposició. Així que són massa semblant l'exemple guia telefònica. Tan aviat com vostè té, fins i tot amb un petit problema com aquest, les seves entrades pre-ordenats, podem en realitat trobar el valor discutible de manera més eficient. 

I jo no dic que si era ordenats petit a gran o gran a petit, i pel que era molt raonable per començar en un extrem o l'altre trobar realment aquest valor objectiu. Així que gràcies a Trevor també. I vaig a propose-- molt ben fet. Tenim un petit clip, en realitat, que és un dels nostres moments favorits en CS50, pel que de vegades aquestes donem no tot vagi segons el planejat. I de fet ara mateix, va aturar la interfície equivocada amb la qual utilitzar la pantalla tàctil. Així que va ser culpa meva no. 

Així que això farà per Clip de l'any que com de per què estava fent clic en la meva pròpia pantalla. Però donem una ullada ràpida al que va succeir l'any passat amb Jay, que es va acostar, i molt com Trevor aquí, voluntàriament, i en aquest breu clip, veuràs com aquesta mateixa demostració no va fer prou revelar les mateixes lliçons apreses. [REPRODUCCIÓ DE VÍDEO] -tots Els que vull que facis ara és de trobar per a mi, i per a nosaltres, en realitat, el nombre 50 un pas a la vegada. 

-El Nombre 50? 

-El Nombre 50. I vostè pot revelar el que és darrere de cadascuna d'aquestes portes amb només tocar amb un dit. Maleït sigui. 

[El] 

[FI DE REPRODUCCIÓ] DAVID J. Malan: Així que va ser molt bé. Aquestes van ser les portes sense classificar. I Jay, per descomptat, trobat amb massa rapidesa. Trevor va fer un treball molt millor en termes d'un moment d'aprenentatge, per així dir-ho, aquest any en prenent més temps per trobar-lo. Per descomptat, llavors ens vam Jay una segona oportunitat, pel que ens ho van solucionar les portes, tal com ho vam fer per Trevor, i Trevor va fer molt bé aquesta vegada. Però Jay va fer un mitjà tan ràpid. [REPRODUCCIÓ DE VÍDEO] -El Objectiu ara és també nosaltres trobar el número 50, però fer-ho algorítmicament, i dir-nos com va en això. 

-D'ACORD. 

-I Si el troba, es manté la pel·lícula. Si no el troba, li dones l'esquena. 

-Home. 

-Oh! 

- [Inaudible] a D'acord. Així que vaig a comprovar els extrems primer per determinar si there's-- Oh. 

[Aplaudiments] 

[FI DE REPRODUCCIÓ] DAVID J. Malan: OK. Així classificació portes clarament condueix a una major eficiència. I així, dues vegades més ràpid és el que vaig voler dir no. I així Jay va tenir sort en les dues ocasions. I també va tenir sort en aquest últim any, vaig demanar alguns discos Blu-ray per donar a conèixer realment. Ho sento d'aquest any, no va tenir la mateixa, Trevor. Però millor encara era fa uns anys. I alguns de vostès podrien saber això company, Sean, que quan estava al CS50, va ser impugnada amb l'exacta mateix problema, encara que en SD, com aviat veuràs, de tornada al dia. I trobareu que no només que prengui una mica més de Jay, una mica més de Trevor, va ser En realitat aquesta meravellosa oportunitat a participar gairebé tots al gent a la Price is Right, fomentant ell per trobar el nombre que estàvem buscant. Anem. fer una ullada ràpida. 

[REPRODUCCIÓ DE VÍDEO] 

-D'ACORD. Així que la seva tasca aquí, Sean, és la següent. He amagat darrere d'aquests portes el número set. Però amagat en alguna d'aquestes portes així són altres números negatius. I el seu objectiu és pensar d'aquesta fila superior dels nombres com s'acaba d'una matriu, o simplement seqüència dels fulls de paper amb números darrere d'ells. I el seu objectiu és, només amb la part superior varietat aquí, em trobar el número set. I estem a continuació, anem a criticar com vostè va sobre fer-ho. -Tot bé. Ens -Buscar el número set, per favor. No. Cinc, 19, 13. 

[El] 

No és una pregunta amb trampa. Un. 

[El] En aquest punt, la seva puntuació no és molt bo, de manera que així podria seguir endavant. Tres. 

[El] 

Continuar. Francament, no puc evitar preguntar- el que estàs tan sols pensar, així que-- 

[El] Només la fila superior, de manera que vostè té de tres esquerra. Així que trobar 7. 

[El] 17. Set. 

[Aplaudiments] 

Tot bé. 

[FI DE REPRODUCCIÓ] 

DAVID J. Malan: Així que vam poder veure a aquests durant tot el dia. I, per descomptat, alguns demostracions d'aquest any potser ara acabar en el pròxim vídeo de l'any també. Així que ara anem a realitat centrar-se en els algoritmes aquí, i veure si no podem Ara començar a formalitzar com podem anar sobre com obtenir les nostres dades en aquest estat que està ordenada, pel que en última instància, podem realitat buscar-la en el diccionari de manera més eficient. I tot i que anem utilitzar conjunts de dades bastant petits, com el que vuit nombres tenim aquí al tauler, en última instància, podrien aplicar aquestes mateixes idees 1.000 entrades, un milió d'entrades, 4000000000 d'entrades, ja que els algoritmes seran fonamentalment els mateixos. 

I el que aquesta és la nostra última oportunitat perquè els voluntaris avui en dia, però potser el més complicat, per a això necessitem vuit voluntaris per arribar i ens caminar pel procés de classificar el que aviat estar en aquests faristols aquí. Permetin-me començar de nou aquí. 

Així que un al verd turquoise-- és? Estàs cometent? Dos. Anem cap avall. D'ACORD. Tres. Quatre. Deixi mi-- OK, cinc. Vostè està sent nominat pel seu amic. Sis, set-vuit. Anem cap amunt. Tot bé. Moltes gràcies. Anem cap amunt. Anem cap amunt. 

Tot bé. Així que el que tenim aquí-- i això és un dels més difícils, ja que això requerirà que l'humor mi per una mica de temps. Vostè serà el número u. Com et dius? 

ANNAN: Annan. 

DAVID J. Malan: Annan. En David. Com et dius? 

JOSEPH: Joseph. 

DAVID J. Malan: Josep, vostè és el número dos. 

SERENA: Serena, número tres. Stefan, el número quatre. CYNTHIA: Cynthia. DAVID J. Malan: Cynthia, número cinc. [Inaudible] DAVID J. Malan: [inaudible]. David, el número sis. MATT: Matt. DAVID J. Malan: Nombre de Matt 07:00. ¿I? 

WAVERLY: Waverly. 

DAVID J. Malan: Waverly, número vuit. Tot bé. Si could-- crits. Si tots vostès, com el seu primer desafiament, hi ha són vuit faristols aquí davant l'audiència. Si poguessis posar els seus números en aquests suports de música de tal manera que s'alineen amb el mateixos números en el tauler. Així que vostès veuen com que per posar els números en aquesta música es troba aquí. Excel·lent fins al moment. 

Excel·lent. D'ACORD. Així que ara, demanarem a la pregunta de diverses maneres diferents. Com podem anar sobre la classificació aquesta gent aquí? Perquè teníem un parell d'enfocaments anterior, pel qual van ser tipus de presa de dos cubs diferents. I llavors estàvem general recompondre les coses junts. Tan aviat com vam veure dos nombres que pertanyien junts, els posem junts. Dues lletres que van de la mà. 

Però anem a veure si ens no pot formalitzar aquest, perquè en última instància, tenim alguns pseudo-codi es vol, amb el que pot resoldre aquests problemes. Així que ara, estic mirant aquests números aquí. I veig un munt d'errors. Al final, vull un al a l'esquerra i vuit a la dreta. 

I pel que estic veient aquests dos, quatre-dos. ¿I quin és el problema, és obvi? Sí. So. Dos òbviament ve abans 4, així que vostè sap el que? Permetin-me primer prenc un enfocament cobdiciosos, si es vol, tant problema com establir un-- si recorden des del Edició Estàndard de de problemes Un, on només a nivell local a resoldre el problema això és just aquí al davant de mi i veure a on em porta. 

D'ACORD. Així que dos i quatre, me n'aniré endavant i només et intercanviar dues. Si vostè pot moure físicament vostès mateixos i del seu paper, Sembla que he aconseguit el llistar en millor estat. 

Ara, són bons. Vaig a seguir endavant, 04:06, es veu bé. Cap problema. Sis i vuit, a D'acord. Vuit i un, un altre problema. Perquè el que és cert això de les 08:01? Un ve abans de les vuit, i així ¿què hem de fer? Anem intercanviï aquests dos. Un i vuit. I ara, seguiré endavant. Jo seguiré mirant cap endavant. I anem a veure què passa. Vuit-tres, de Per descomptat, fora d'ordre. D'intercanvi Let. Vuit-set, és clar. No funciona. D'intercanvi Let. Vuit-cinc, per descomptat, anem a swap. Tot bé. Llista està ordenada. sí? 

OK, òbviament no. Però és una mica millor, no? A causa avís del que va passar. Cada vegada que realitza un intercanvi, una més petita nombre de tipus de percolado d'aquesta manera, i un nombre més gran percolado d'aquesta manera, o anem a començar dient bombollejar a la bombolleig esquerra o cap a la dreta. 

Ara, no és suficient, perquè en el millor d'un nombre podria han mogut un sol lloc cap endavant, o en el pitjor, un nombre podria tenir mogut un punt més. Així que ja saps el que, aquest tipus de funcionat prou bé fins ara. Déjame intentar-ho de nou. Dos i quatre, que estan bé. Quatre i sis, que estan bé. Sis i un, fora d'ordre. Així que anem a vostès dos swap. I ara, observi el problema de començant a aconseguir una mica millor de nou. Sis-tres, fora d'ordre. Anem a vosaltres dos swap. Sis-set, ja està bo. Set-cinc, per descomptat, fora d'ordre. Set-vuit, en ordre. I ara, pot ser que hagi de fer això unes quantes vegades més. I de fet, pensar per si mateixos potser quantes vegades màxim podria jo haver de caminar d'anada i tornada? 

Tornarem a això. Així que dos i quatre continuen en D'acord. Quatre i un, doncs no. Així, intercanvi de deixar. I de nou, observi visualment un és tipus de bombolleig a l'esquerra, on ha d'estar. Quatre i tres d'intercanvi. Quatre i sis. Sis-cinc anys d'intercanvi. Sis-set. Set i vuit són bons. 

Bé. Estem rebent encara millor. Així que anem a veure. Ara, tenim dos i un. Per descomptat, canviar. Dues i tres, tres i quatre, quatre i 5, sis i set, set-vuit. Bé. ¿I saps què? Perquè vaig fer un canvi allà, m'ho dius a mi fer un xec seny. Déjame anar tot el camí de nou al principi. D'ACORD. Un, dos-- yup, veus? Alguna cosa estava malament. Tres, quatre, cinc, sis, set, vuit. I en aquest últim pas, són Se sent còmode amb el meu ara al·legant que s'ordena? D'ACORD. Visualment, això és absolutament cert. Però funcionalment, el va fer també acaba de succeir en aquesta última passada que li permet per confirmar que aquesta llista és de fet ordenats? 

Què vaig fer o no fer això últim passi? AUDIÈNCIA: No hi va haver canvis. DAVID J. Malan: Ho sento? AUDIÈNCIA: No hi ha canvis. DAVID J. Malan: No hi va haver canvis. Així que seria estúpid de la meva part fer això mateix algoritme de nou si jo no vaig fer cap canvia la primera vegada. I l'estat no ha canviat. Certament, jo no faré Qualsevol canvi del segon temps. I així, és segur ara dir, la llista està ordenada. 

I, de fet, això és ara cosa que anem a general anomenada d'ordenament de bombolla, en què per parelles, corregir errors de nou, i una altra, i una altra, i vostè seguir endavant cap enrere i endavant, i d'anada i tornada, fins que no fer aquest tipus de swaps, i en aquest moment vostè pot estar segur, si, acabat de fixar tots els errors. Anem a restablir i jugar diferent. Si vostès podrien tornar a l'ordre en què van ser fa un moment, que es veia així. Ara, anem a fer un enfocament una poc més com el llibre de l'examen, pel qual estàvem constantment la selecció de la lletra de l'alfabet quin tipus de volíem per fer front a la propera. Potser va ser una gran carta, com A, o una lletra Z. baixa 

Així que tothom està de tornada en aquest ordre. I ara m'ho dius a mi fer això. Vegem sé que tinc vuit nombres aquí. Vaig a seguir endavant i simplement deliberadament seleccioneu els elements més petits. Oi? Això sembla intuïtiva també. Per què no em sembla el més petit element, el va posar on pertany, a continuació, obtenir el següent element més petit, ja on pertany, i simplement repetiu. 

A causa de que de manera intuïtiva, que hauria de funcionar també. Així que 4, que és un nombre molt petit. Vaig a recordar d'on és. Espera un minut. Dos és més petit. Permetin-me ara recordo què dos és, i oblidar-se de quatre. Ens ocuparem d'això més tard. Sis, no m'interessa. Vuit, no estic interessat. Un d'ells és el meu nou número petit. Així que vaig a recordar on un és. Tres, no li interessa. Set, no li interessa. Cinc, no li interessa. 

Així que sense caure l'etapa d'aquest any, Vaig a agafar nombre un-- i el que era el teu nom? 

ANNAN: Annan. 

DAVID J. Malan: Annan. I si vostè pot unir-se a mi en el principi de la llista, anem et desanimi a on pertanys. Unfortunately-- ¿com et dius? 

STEFAN: Stefan. 

DAVID J. Malan: Stefan es troba en el camí. Així que abans de Stefan resol aquest problema, què hem de fer? Què fem amb Stefan? 

AUDIÈNCIA: [inaudible]. DAVID J. Malan: OK. Així que podríem fer això. Podríem espècie de prendre Stefan i la seva 4, i només cal posar en una variable i aferrar-se a ella per una certa quantitat de temps, fent així espai per al número u. I això no és dolent. Que podria suggerir, per què no fer només cal posar Stefan aquí? Per què podria això violaria un sol de les idees que vam començar parlant de l'última vegada, la setmana passada? Sí? 

AUDIÈNCIA: [inaudible]. 

DAVID J. Malan: No hi ha índex per a això. Si vostè pensa en això, de fet, com un matriu, això és com una cosa negativa, així que no hi ha memòria realitat aquí si aquesta és de fet una matriu, com hem declarat la setmana passada a la conferència. Així que no hem de fer això. Podríem emmagatzemar-lo en una variable. 

O saps què? Vaig sentir que algú suggereixi que. Quina altra cosa podíem fer amb Stefan? Per què no acaba de desallotjar i el va posar sobre on era el número u. Així que si vols anar-hi. I de fet, aquesta és una bastant bona solució. Ara, per una banda, no tinc classe de fet el problema pitjor. Quatre és ara més lluny des d'on ha d'estar. Ha de ser cap a aquest mitjà. 

Però saps què? Això podria haver estat mala sort. Potser el número vuit era aquí. I per això, potser ho faria han tingut sort, i empès de vuit més a prop del final. Així que al final del dia, En certa manera tots mitjana. No necessitem que es preocupen per quatre. Tot el que m'importa en aquest moment és seleccionar l'element més petit. 

I ara, què vaig a fer és oblidar-se de número u de forma permanent, perquè sé que el llista darrere meu ara ordenades. Així que la meva llista era prèviament mida 8. Ara, és de la mida de set. Així que el meu problema és aconseguir més petit, encara linealment. Així que ara, vaig a seleccionar el actual element més petit, dues. Sis, vuit, quatre, tres, set, cinc. Aquest va ser l'element més petit. Llavors, què faré con-- ¿Quin era el seu nom? 

JOSEPH: Joseph. 

DAVID J. Malan: Josep? Anem a deixar a Josep al seu lloc. Ara, vaig a fingir que aquests nois són-- així, Sé que aquests dos ja estan ordenats. Ara ens centrarem en la resta de la llista. Sis és el corrent més petita. Vuit és més gran. Quatre és ara el corrent més petita. Tres és ara el corrent més petita. I ara, vaig a seleccionar tres, que és-- quin és el teu nom? SERENA: Serena. DAVID J. Malan: Serena, si poguessis gravar el vostre número i d'intercanvi con-- Kalsang: Kalsang. DAVID J. Malan: Kalsang. Anem cap enrere, i estem canviarà aquests dos. I ara, anem a posar això en pilot automàtic. Vaig a anar i deixar a vostès per seleccionar els següents elements més petits. Dun, dun, dun, dun. Número quatre, ¿què ha de fer? Excel·lent. Ara, jo faré un altre passi. Dun, dun, dun, dun. Veig cinc és el immediatament inferior. Ara, vaig fer un altre pas. Dun, dun, dun, dun. Sis és el més petit. Bé. Set és el més petit. Sense canvis. Vuit és el més petit. Fet. 

Així que el que acabem de fer de forma iterativa seleccionar un element després de l'altra és posar en pràctica una cosa que estem va formalitzar com a ordenació per selecció. I és potser fins i tot més simple d'explicar, en què, literalment, tot el vull fer és mantenir que van i vénen a través de la llista la selecció, el següent element més petit, fins que hagi acabat. 

Pel que és encara més simple, potser intuïtivament, que el passat. Provem última. Si vostès podrien restablir mateixos en les següents posicions per última vegada, anem a veure si no podem ara formalitzar un altre enfocament. De fet, ho faria algú per aquí agradaria proposar ¿De quina altra podríem anar fent això? Sense llançant paraules de moda o tipus de les respostes que ja es coneixen, simplement intuïtivament, què podíem fer? 

AUDIÈNCIA: [inaudible]. DAVID J. Malan: Sí. Així que hi ha alguna cosa de gran intuïció allà. Les bones coses semblen succeir fins al moment en ciències de la computació quan dividim i conquerir el problema de dividir per la meitat i meitat i meitat. I així, de fet, ens podria començar a fer això. I de fet, que serà, anem a veure, una de les nostres millors solucions encara. Però tornem a la qual en poc temps. De fet, farem que una mica més tard aquesta setmana. Què més podríem fer per solucionar això? Així que aquí tothom està en ordre aparentment aleatori. Tu saps que? En lloc d'anar i venir, anada i tornada, d'anada i tornada cada vegada, això se sent com Estic fent un munt de peu. Per què no acaba de començar a el principi de la llista, i només cal posar de quatre que li correspon? Així que permetin-me assumeixo de moment que la cistella és només aquest primer element. És de quatre ordenats en aquest moment en el temps, si tot el que m'importa és tot aquí? Aquesta és una espècie de trivialment cert, ¿no? Igual que la llista que conté un nombre, i que el número quatre és, òbviament, ordenades. 

Així que permetin-me estipulo que aquesta llista està ordenada. Però ara tinc la resta d'aquesta llista. Així que ara, em trobo amb dos. D'on ve de dos, òbviament, pertànyer respecte a quatre? Abans de quatre. Llavors, què puc fer aquí? Quin és el teu nom? 

JOSEPH: Joseph. 

DAVID J. Malan: Josep, si es pogués fer un pas enrere per un moment amb el seu número. I ara el que ha de Stefan fer aquí? Anem a canviar de lloc Stefan aquí. I ara, anem a Joseph entrar aquí. I ara, deixa pretenc que tot el que aquí s'ordena. Per tant, resultat similar, però una enfocament fonamentalment diferent. Ni tan sols he mirat el que hi ha allà baix. Segueixo tenint els elements com se'ls van lliurar a mi, i tractar amb ells. 

Així que ara, veig el número sis. A on pertany número sis? Tenim dos, quatre, sis. Exactament on és ara. Així que deixarem que per si sola, i ara afirmar que aquesta part de la llista ara està ordenada. I així, això se sent fonamentalment diferent, ja que només sóc movent-se a través de la llista aquí linealment, i estic Mai doblegar l'esquena. Sí. Tot bé. Així huit, on pertany vostè? Aquí mateix. Perfecte. Així que ara, un. UH oh. Això se sent com si fos serà car. Ara, en l'algoritme anterior, Jo només vaig canviar persones. Així que jo li posi tot el camí en al principi, però després es va traslladar a Josep. Però si em mut Joseph, ara el que va a estar malament? 

Ara, tinc una mena de undone-- tinc fet un pas cap endavant i després un pas enrere, perquè ara Joseph estaria fora d'ordre. Així que anem a fer això. Si vostè podria prendre el número u i un pas enrere per un moment. Com podem put-- el era el teu nom? 

ANNAN: Annan. 

DAVID J. Malan: Annan en el seu lloc? Què ha de passar pel que fa a dos, quatre, 06:08? Tots ells necessiten canviar. Així que si les huit li agradaria canviar primer, després sis, després quatre, després dos. I llavors Annan, si ho agradaria venir aquí, bé. Però aquí, acabem de tipus de pagat un preu en un punt diferent en l'algoritme. Mentre que l'última vegada amb la selecció espècie, i fins i tot una mena de bombolla, Estic caminant cap enrere i endavant, enrere i endavant, que sens dubte és la suma de pel que fa a temps, i, literalment, pas a pas. 

L'ordenació per inserció, en un primer moment vista, sembla que és súper intel·ligent, perquè jo només sóc fer, el progrés gradual lent, però jo no vaig aquesta anada i tornada. Però si algú és de fet fora d'ordre, notificació tota la feina que havia de fer. Vaig haver de moure la meitat de la llista només per fer espai per al número u. Així que és la mateixa quantitat de treball fins al moment es sent, simplement un tipus diferent de treball. 

Continuem. Així que ara que sabem que tothom entre un i vuit són ordenats. Aquí, no tinc el número tres. Si t'agrada per recollir número tres, un pas enrere un. ¿I què és el que vostès necessiten fer? Sí. Així que aquesta és una altra d'una, dues, tres passos. Tres unitats de temps que només costen mi, així que 3 ara puc encaixar. Finalment, set. 

Seguirem endavant i tenir vostè pren un pas enrere. Això només ens costarà una unitat de temps, però això està bé. I ara, cinc d'anar a ser una mica més car. Si voleu fer un pas enrere. Hem de passar vuit, i 7, i sis. I llavors tothom està ara ordenades. Així que una gran part dels nostres voluntaris aquí. Moltes gràcies. 

[Aplaudiments] 

Gràcies a tots. Gràcies a tots. Així que anem a veure ara com costosa tot això era. Anem a considerar potser la més simple d'aquests, ordenament de bombolla. I dic més simple, només perquè es pot resoldre amb avidesa per només solucionar el problema per parelles aquí. Solucionar el problema de parells aquí, una i altra vegada i de nou, repetint com molts vegades que realment necessiten. 

Així resulta que amb una mena de bombolla, bé, quants passos he d'assumir la primera passada d'aquest algorisme? Podria take-- anem a veure- un, dos, tres, quatre, cinc, sis, set. I hi ha vuit elements aquí. Així que és com n menys passos d'1 a arribar des del principi de la llista fins al final de la llista. 

Però amb la selecció espècie, recordo que sóc la selecció dels elements d'una i altra vegada i una altra que és més petit, Estic posant en el seu lloc, però llavors jo no sóc mirant darrere meu una altra vegada. Així que crec que és una mica més clara a continuació, que la primera vegada, jo podria ha de prendre tot n menys passos d'1 per trobar l'element més petit. Llavors els vaig posar al seu lloc, i jo desallotjar tot el que estava aquí abans. 

Però llavors jo no he de seguir buscant en aquest element, perquè jo sé que és i als més petits. Així que ara, puc mirar a només set elements, llavors sis elements, a continuació, cinc elements, després quatre elements. I així, matemàticament, si n és el nombre d'elements o números que vam començar amb, es pot imaginar que aquest és el mateix que n menys 1, més n menys 2 passos, més n menys 3 passos, més n menys 4 passos, tot el fins arribar a un sol pas. I estic en la meva última persona. 

I si vostè recorda que una gran quantitat Estadístiques de llibres o llibres de matemàtiques tenir aquestes fórmules en el tapa dura enrere o davant d'ells, resulta que aquesta sèrie pot expressar-se més senzillament com n vegades n almenys 1 sobre 2. I està bé si això no és a l'avantguarda de la seva ment. Però això és cert. Això és només una manera més senzilla d'escriure. I llavors si vostè pensa de nou a l'escola primària, quan acaba de començar a multiplicar coses fora, això, per descomptat, és simplement n al quadrat almenys n dividit per 2. L'únic que he fet és ampliar les expressions allà. I així anem a reescriure aquesta una mica diferent. Això n al quadrat dividit per 2 menys n / 2. 

Així que de nou, jo sóc només una mica de l'aplicació una mica d'aritmètica governa allà. Però noti ara que el major termini En aquesta expressió, per així dir-ho, és que n al quadrat. Així que sí, és n al quadrat dividit per 2, menys n / 2. 

Però, en general, si n és serà un gran valor, Vaig a dir que n al quadrat va ser el factor dominant. És només serà un contribuent més gran amb el nombre de passos que n / 2. Llavors, què vull dir amb això? Provem un exemple senzill, fins i tot tot i que les matemàtiques aconsegueix una mica gran. 

Així que suposem que tenim 1 milió de persones a l'escenari, o 1 milió de coses que volem ordenar. Anem a endoll d'un milió exactament en aquesta fórmula per veure la quantitat de passos que pren total de per ordenar un milió d'elements mitjançant per exemple, ordenació per selecció. 

Així tindríem la mateixa fórmula que abans. Em connecto un milió, pel que tinc un milió al quadrat dividit per 2, menys d'un milió dividit per 2. Si faig això matemàtiques per endavant aquí, tenim 500.000.000.000 menys 500.000, que ens dóna 499999500000, que és bastant maleït gran. 

De fet, si es compara ara 499000000000, 999.000.000, 500.000 contra el nostre valor original, 500.000.000.000, és tan condemnadament prop. Oi? n al quadrat dividit per 2 dóna nosaltres-- o més aviat, n al quadrat dividit per 2 ens donar 500 mil milions. Això és bastant maleït prop a 499999500000, és a dir, restant off 500000, o, més generalment, restant off n al quadrat, no és realment un gran problema. El major al quadrat fa que aquests nombres creixen molt ràpid. 

Ara, això és important només en la mesura com nosaltres, com els informàtics, generalment no es va a importar molt sobre els matisos d'aquestes fórmules i exactament el que el respostes precises. Ens preocupem només això, saps què? Al final del dia, aquesta fórmula és de l'ordre de n al quadrat. 

Sí, estem dividint per 2 en aquest país. Sí, estem restant fora n almenys 2. Però al final del dia, el terme que realment ens fa mal i ens costa un munt de passos és aquest terme quadrat. I així el que un científic de la computació es va a fer en general és ignorar tots els termes d'ordre més petits, i només cal veure què contribueix més al cost. 

I això és bo, perquè podem ara parlar en molt major generalitat sobre algoritmes, i pot comparar-los. I el fet que sóc l'ús d'aquesta O és deliberat. Quan dic que en l'ordre de, estic específicament es refereix a alguna cosa anomenat gran O. I gran O és una notació que un ordinador científic utilitza per descriure un límit superior en alguna cosa. 

Així que si vostè diu que un algoritme és en gran O de n al quadrat, com he proposat només un Fa moment, que els mitjans que en termes del seu funcionament temps o la seva eficiència, que es necessita en l'ordre de n quadrat passos. Potser més, potser menys. Però és de l'ordre de n al quadrat. I aquest és el límit superior. No serà més dolorós que això. No serà n en cubs o 2 a la n, o alguna cosa molt més gran. Aquesta és una fita superior en el que el cost és. Així que tenint en compte que, anem a considerar només alguns exemples. I això és només una llista finita temps d'execució dels molt comuns per als algoritmes que està destinat a ser il·lustratiu d'algunes coses que hem ja s'ha vist. 

Així, per exemple, en el cas de ordenació per selecció, el que estic dient aquí és en execució que la selecció d'espècie el temps és de l'ordre de n al quadrat. En el pitjor dels casos, tindré un munt de nombres aleatoris aquí. I com hem vist matemàticament, si segueixo caminant a través de la llista, a través de la llista, seleccionant l'immediatament inferior element i una altra, si jo realitat anoti tots els passos Estic prenent com vaig proposar formulaically abans, és de l'ordre de n al quadrat mesures que estic prenent. 

I resulta que la bombolla classificació i ordenació per inserció són tan lent en el pitjor dels casos. Considerem, per exemple, l'ordenació per inserció, l'últim algoritme amb el qual tractem, que tenien ens fixem en l'element, i després inserir on pertany. I després ens fixem en el següent element, i s'insereix on pertany. 

Així que considera el millor escenari possible. Suposem que jo tenia els meus voluntaris alinear literalment així, un al vuit, ja ordenats. Quants passos és l'ordenació per inserció va a prendre per ordenar a vuit persones, si arriben a l'escenari buscant d'aquesta manera? 

Vuit persones ja ordenats. I ús ordenació per inserció. L'últim dels algoritmes. Bé, anem a recrear ràpid real. Així que si em poso aquí, ho veig. Per on pertanyen? Pertany aquí. Veig dues. D'on ve dos pertanyen? Aquí mateix. Veig 03:00. D'on ve tres pertanyen? Aquí mateix. 

Veig 04:00. Aquí mateix. Cinc, sis, set, vuit. No hi ha raó per repetir a mi mateix. I així, el nombre de passos és que en termes de n? És de l'ordre de n passos, oi? n almenys 1. Però vaig prendre una sèrie lineal de passos, i ara he acabat. Així que aquest és el millor dels casos, però. I el pitjor dels casos? El que vuit eren d'allà, i set eren allà baix, i un i dos eren d'aquí, de manera que que la llista s'invertís en veritat? 

Bé, el que passa de fet si aquest és el nombre? I farem només un parell d'exemples. Què passaria si, de fet, el número vuit és aquí, i els crits number--. ¿I què si, de fet, el nombre vuit és tot el camí fins aquí, i estic fent servir l'ordenació per inserció? 

D'ACORD. Reclam en aquest moment està al seu lloc. Però ara, seven-- on van set anys? Per descomptat, no cal aquí. Així que he de moure i vuit més d'un lloc. Ara 6:00, cap a on va? Bé, està bé. Ara, he de moure i vuit més un lloc i 7 més d'un lloc, i després em deixo caure 6. 

Així que la primera vegada, el cost mi un pas d'arreglar les coses, llavors em va costar dos passos per arreglar les coses. Quants passos és va a prendre per solucionar coses per posar cinc en el lloc correcte? Tres. Perquè ara he de moure un, dos, tres. Quants passos es prendrà posar quatre en el lloc correcte? 4 i 5, a més de 6, més 7. 

I el que és matemàticament idèntica a el que hem descrit per a la selecció de gènere. Tenim aquesta sèrie això és només l'augment. 1 més 2 més 3 més 4, o per contra, 7 més 6 més 5 més 4 afegeix avui de efectes a l'ordre de n al quadrat. 

Així que permetin-me estipulo també que ordenament de bombolla és també n al quadrat. Perquè amb ordenament de bombolla, cada vegada que vaig per la llista, Estic prenent més o menys quants passos? Cada vegada que, literalment, caminar des d'allà fins allà? Al voltant de n passos. Però quantes vegades pot ocórrer de passar per la llista? 

Bé, més o menys n temps. Potser n menys 1, però més o menys n vegades. Bé, per què és això? Bé, amb la bombolla del tipus, si partim d'ordenament de bombolla, amb la llista en la pitjor possible situació, que de nou és completament al revés, el que passarà? Vaig a través de la llista, i el nombre de un pertany tot el camí per allà. 

Però amb la bombolla del tipus, fins on pot un passar el meu primer pas a través de la llista? Quants punts és el que obté més a prop de el lloc correcte? Només un. Així que si vostè tipus de raó a través d'aquest, cada vegada que a través d'aquest algoritme, Tenint aproximadament n passos de David. Però, quants passis a través de la llista és que va a prendre perquè un de bombolles a l'esquerra on pertany? 

Ell ha de moure com, n espais d'aquesta manera. Així que per fer la classificació de la llista, He d'anar i venir n vegades. I cada vegada, estic mirant a n elements. El mateix passa amb les coses n n vegades en de l'ordre de n al quadrat. 

Ara, anem a veure d'alguna dels curts que s'incrusten en el següent problema de CS50 establir, un altre enfocament a aquests, però per ara, considerarem altres vegades s'executen, especialment si els prenen de classificació una mica de temps per a enfonsar-se en. Què és un algorisme que hem vist ja que porta l'ordre de n passos? 

Què s'ha de prendre una sèrie lineal dels passos que hem vist fins ara? Què és això? La recerca en el directori telefònic. El primer algorisme. Oi? On som linealment la recerca de Mike Smith? En efecte. Des de la setmana zero, quan vaig començar convertir una pàgina alhora, i fins i tot li vaig dir que era una espècie d'un algoritme sensació lineal, i vam tenir aquesta foto a la tauler amb la línia vermella directa i el groc recta línia, aquests eren de fet algoritmes que són en gran O de n. 

Perquè per trobar Mike Smith en un telèfon llibre de n pàgines, en el pitjor dels casos, me n mesures podria prendre. Què hi ha de prendre assistència? Un, dos, tres, quatre, cinc, sis. Què és el temps d'execució de la present algoritme per a la presa d'assistència? O gran de n, ja que en teoria em has de apuntar tots a la sala. 

Ara com un a part, què passa amb la una altra optimització de setmana zero? Dos, quatre, sis, vuit, 10, 12. Un científic de la computació ho faria adonar-se'n, esperi un minut, això és de l'ordre de n dividit per dos passos. Oi? A causa de que estic fent dues persones alhora. Però anem a ignorar els termes d'ordre inferior, i nosaltres només anem a llençar la divideix per 2, i dir, gran O de n perquè l'algoritme també. 

Què tal aquest? Ens saltarem sobre alguns d'ells, però el que era un algoritme que era log de n? Que va tenir més o menys log n passos? El divideix i venceràs. Exactament. Igual que l'exemple de llibre de telèfon en setmana zero i el dia d'avui, on ens vam dividir el problema una i altra vegada i una altra. Dibuixem a la pissarra a la setmana zero com una línia verda corbat, i ens va dir aquell dia que era un algoritme logarítmic. 

I de fet, el nombre de passos que porta a terme divideix i venceràs, o recerca binària com començarem cridant, com en la guia telefònica, és de l'ordre de registre i passos. I això és una mica d'un ésser estrany. 

El que dóna un pas, o més específicament un nombre constant de passos? Potser sigui de dos, potser és tres, però un informàtic sol simplifica tan gran O d'1, un nombre constant de passos. Què és una cosa que podria fer que pren un nombre constant de passos? 

Quin és el temps d'execució d'aplaudir? Constant de temps. Oi? Igual que, quin és el temps de funcionament del fer qualsevol cosa que pren només una operació, com imprimir F Hello World. Això podria dir-se que la constant de temps, menys que menys cas cantonada amb la impressió M, el que podria el temps d'execució d'impressió F realitat sigui? I per què? Què és la n de mesurament en aquest cas? 

AUDIÈNCIA: [inaudible]. DAVID J. Malan: Exactament. El nombre de caràcters volem imprimir. Així que és molt sensible al context. Avui, ens hem centrat molt en les lletres i els números aquí al tauler. Però també podria ser personatges d'una cadena real. Així que resulta que hi ha un altre mesura que començarà a preocupar-se, i això és tot el contrari de gran O, per dir-ho així. 

Aquesta és la notació omega. Mentre que gran O significa el que és, la límit superior del seu temps de funcionament? Com a màxim, la quantitat de temps podria prendre alguna cosa? Omega-- sento això segueix arribant up-- és el contrari d'això, mitjançant el qual es tracta d'un límit inferior en el quantitat de temps que alguna cosa podria prendre. 

So. per exemple, què és un algoritme que prengui mesures sempre n al quadrat? Bé, un dels algoritmes que he vist Avui en dia, de fet, podria ser que també. Selecció tipus. Selecció espècie és bastant estúpid. Fins i tot si la sento algorithm--, tot i si la matriu ja està ordenat, ordenació per selecció va seguir caminant per la llista per assegurar-se que compta amb el més petit element d'una i altra i una altra. I tot i que els éssers humans en el públic sàpiga que, espera un minut, que ja va passar el element més petit, l'ordinador no sap que fins que es vegi tot el camí a través de la llista. De la mateixa manera, una cota inferior que també pot ser tingut en compte podria ser el moment lineal. 

Quant de temps es triga a ordenar n elements en la millor cas usant una mena com una mena de bombolla? Suposem que la llista ja està ordenat. Vam dir bombolla espècie adquireix de l'ordre de n al quadrat passos. Però el que si ja està ordenada? ¿I si et dones compte després un pas a través de la matriu que vostè ha fet no hi ha permutes? És necessari seguir fent més passades? 

No. Així que un límit inferior en l'ordenament de bombolla podria dir-se que és lineal. Omega de n. I podem veure altres d'aquests també. Així que anem a fer una ullada ràpida en tot just una visualització aquí per veure com aquestes es distingeixen. Vaig a anar per aquí a aquesta pàgina que està disponible a la pàgina web de C50, però va ser un mal per aconseguir feina, ja que utilitza una tecnologia anomenada Els applets de Java, que és un en gran mesura sense suport en aquests dies, almenys per crom i alguns altres. 

I me n'aniré endavant i accelerar aquest i explicar el que està passant. Aquesta és una demostració de la bombolla espècie, el primer algoritme ens va mirar. I és una visualització en què cada d'aquestes barres representa un nombre. Com més gran sigui la barra, com més gran sigui el nombre. Com més baix sigui la barra, com menor sigui el nombre. ¿I què es pot veure visualment, fins i tot encara que això va molt ràpid, és que la barra vermella és com jo, caminant cap enrere i fixar successivament problemes. Es pot veure que els elements més grans són de fet bombollejant cap a la dreta, i els elements més petits estan bombollejant cap a l'esquerra. I aquí, si realment mirar més de prop, realment podem comptar el nombre de comparacions i swaps que s'estaven fent. 

Però en lloc, donem una ullada en el segon algoritme hem vist abans amb la nostra voluntaris, selecció d'ordenar. Visualment, té una molt diferent efecte. Però és, de nou, molt intuïtiva, en que guardem la selecció de la pròxima més petita element, i ens van donar una mica de sort. Això es va sentir fonamentalment més ràpid. Però si ens trobem una i altra vegada i una altra vegada amb una gran quantitat d'entrades, veuríem que és de fet encara en gran O de n al quadrat. 

Anem a fer un últim d'un aquí, l'ordenació per inserció, que va ser el tercer algoritme ens vam mirar, i el record que aquest s'ocupa de la elements, ja que els troba, Però llavors potser torns les coses per a fer lloc, la inserció d'elements que pertanyen. 

I això també acaba donant la resultat final. Ara els tres dels vaig sentir bastant ràpid. I, de fet, jo els vaig trobar a un ritme bastant bo. Però fonamentalment, són tots bastant horrible, per ser honest. Tots aquests algoritmes fins ara que s'executen en gran O de n al quadrat prendre una mica de temps per córrer al final. 

I de fet, podem veure i sentir aquest últim si m'aixeco aquesta tercera i última demostració. Aquest és un altre visualització que va per mostrar ordenament de bombolla en l'esquerra, ordenació per selecció en el medi, i una cosa que, com un del nostre mà planteja suggerir anteriorment, ordenament per barreja a la dreta. Un divideix i venceràs l'estratègia de la dreta. I això és, de fet, el que estem anar a veure dimecres. Però el temps aquests s'executi en paral·lel anem. És més o menys el mateix nombre de elements, tots funcionant al mateix temps. Bombolla espècie vs selecció espècie vs fusió tipus. 

Ara, tots estan corrent en teoria al mateix temps. La CPU està funcionant a la mateixa velocitat, però pot sentir el avorrit que és va molt ràpidament per convertir-se, i com de ràpid quan injectem una mica de setmana algoritmes de zero pot que accelerar les coses. 

I ara anem a comparar aquests en una última forma. Vaig a seguir endavant el lloc web del CS50, on tenim aquest última baula per avui, on algú a Internet amablement armar un vídeo que capta la diferència classificació algoritmes sonen. Aquesta és l'ordenació per inserció. 

[SO] 

Pel qual vostè està demanant una freqüència basat en l'altura de la barra de bar. Es tracta d'ordenament de bombolla. 

[SO Warped] 

Que fins a la pròxima és-- venir al costat és-- ordenació per selecció, on de nou, estem seleccionant el següent element més petit, i podem veure que cada vegada més d'esquerra a dreta. 

Combinar espècie, pel que el nostre guanyador la data d'avui. Observi com està dividint coses en [inaudible] mitjana i els quarts. Tipus Gnome, que no tenim parlat, i crea visualment i audally una mica d'un diferent forma i so. L'anar i venir, la neteja de les coses. També pots veure heapsort a la pàgina web d'aquest tipus. 

I això és tot. Ens veiem la propera vegada. 

[Whooshing I MÚSICA]