ALTAVEU: Molt bé, això és CS50. Aquest és el final de la tercera setmana, i si no ha pres avantatge ja, saben que hi haurà dinar aquest divendres, com de costum, on es pot gaudir d'una bona conversa i el menjar en Fire and Ice amb alguns CS50 d' el personal i els companys de classe. Dirigeix-te a aquest URL aquí. 

Ara vostè pot recordar, o vostè aviat pot estar familiaritzat amb, aquestes coses aquí, que es donen al final del semestre per a moltes classes. Llibres blaus L'anomenat examen, en el qual vostè escriu les seves respostes als exàmens. Ara tinc aquí 26 de tal llibres blaus, sobre cadascun d'ells s'escriu un nom, de l'A a la Z. I de fet, els noms són tan simples, A a la Z. I un els objectius a la mà avui serà la de continuar el comencem el dilluns, el que no és tant mirar el codi, però en realitat mirant idees i la resolució de problemes. Una de les metes i promeses d'aquest curs és que li ensenyi a pensar més amb cura, més metòdicament, i per resoldre problemes de manera més eficient. I, de fet, podem fer que realment sense si més no tocar una línia de codi. Així que tinc un parell d'elefants fins avui, taronja i blau, si poguéssim aconseguir un voluntari, potser des de més enrere del que és habitual. Què hi ha aquí, anem cap avall. L'objectiu de la qual serà a ajudar a més administrar aquest examen aquí. Quin és el teu nom? 

AUDIÈNCIA: Mary Beth. ALTAVEU: Mary Beth, anem a dalt. A veure si el micròfon aquí per a vostè. Encantada de conèixer-te. 

AUDIÈNCIA: Molt gust. ALTAVEU: Molt bé, així que tinc aquí els llibres blaus de l'A a la Z, i jo vaig a pretendre que Tinc un dels estudiants, i que vindran en un tant a l'atzar al final d'un bloc d'examen de tres hores pel que estan acabant d'alguna Per semi-aleatori com aquest. Ara el seu treball en un moment va a ser-- això és en realitat la forma en que obtenen convertit en al final d' la classe, més probable. El seu treball ara serà, bastant simplement, per ordenar aquests llibres blaus per a nosaltres de l'A a la Z. 

AUDIÈNCIA: Oh, això és tindrà per sempre. 

ALTAVEU: I veurem en fer això, no hi ha pressió. AUDIÈNCIA: No, no hi ha pressió ni res. 

ALTAVEU: I per a la diversió, posarem un temporitzador. 

AUDIÈNCIA: Molt divertit, molt divertit. 

ALTAVEU: Puc sostenir el micròfon per a vostè. Molt bé, acabem duplicar la nostra velocitat. Així que mentre tant, permetin-me plantejar el que és serà la pregunta per Mary Beth és el que està fent, com és ella va sobre solucionar això? I, de fet, pot ser que no tingui Ha pensat alguna vegada sobre alguna cosa tan simple com quan vostè tria fins a 26 llibres com aquest, que no tenen un producte natural ordenant a ells. Quin és el procés de que en realitat s'utilitza? És bastant aleatori només escollir el primer que es veu i posar-lo en el seu lloc? És primera vegada que mou les seves mans al voltant de a la recerca d'una continuació a la recerca de B? És vostè fes un cop d'ull a una parell al costat de l'altre i dir, espera un minut, aquest no està bé, i després intercanviar l'ordre? Vam veure ja el dilluns que hi ha un nombre de maneres en el qual podem fer això, i de fet, com ens acostem al final aquí, Jo prendria nota potser del que Mary Beth està fent. Tenim uns munts que sembla, un un més gran, tres més petites. 

AUDIÈNCIA: jo els estic ordenant quan em trobo amb dues cartes que sé que estan junts en una seqüència, Els poso junts perquè no ho faig haver de preocupar de mantenir pista de tota una fila de llibres. És només que, oh, A és primer, Tinc aquesta pila aquí. ALTAVEU: Llavors, gairebé com peces d'un trencaclosques que tenir la forma dret a coincidir entre si. AUDIÈNCIA: Més o menys, sí. ALTAVEU: OK, excel.lent. I ara cada un d'aquests piles s'ordenen presumiblement? 

AUDIÈNCIA: Si. 

ALTAVEU: Molt bé, de l'A a la Z. Tots bé, felicitats, ho van fer. Vostè té la seva opció. Blau? Molt bé, gràcies per això. Així que Mary Beth es proposava el que el seu enfocament era, però el que és un altre enfocament de com podria anar sobre classificació d'aquestes coses? Què hauria fet vostè? El rècord a batre hauria estat un minut i 50 segons més o menys, a més dels que més em vaig oblidar d'explicar. Què hauria fet vostè? Sí? AUDIÈNCIA: Prengui la pila. Comenceu des del principi. Reviseu els seus papers. I si el superior és més gran que, tal vegada, que són, l'inferior és més alt, llavors canviï'ls. 

ALTAVEU: OK, així que començar a la part superior i la part inferior, i després la seva forma de treball cap a l'interior d'aquesta manera, el canvi d'ells? OK, així que una mica semblant en esperit l'ordenament de bombolla, però l'elecció dels extrems no els parells adjacents. No obstant això, el curt d'ell és que no sens dubte un munt de diferents maneres podríem fer això, i Francament, jo crec que tipus de adoptat un parell d'aproximacions, oi? Vostè ha fet una mena de quatre munts ordenats, i després fusionat amb eficàcia. I això és, diria, una altra tècnica per complet. No ho tracta com una gran pila, que s'hagi dividit el problema en quatre quads, si es vol, i llavors d'alguna manera les va fusionar al final. 

Així que anem a considerar, en última instància, com més podem fer això. Formalitzem la noció d'ordenament de bombolla última vegada, i ordenament de bombolla revocatori era una algorisme que visualitzem amb vuit dels seus companys de classe fins aquí, aparentment ordenats a l'atzar al principi. I llavors vam decidir per parelles, si dos elements estan fora de servei, simplement intercanviar. Així quatre i dos són evident la seva total improcedència, per la qual cosa aquests dos companys de classe i va canviar de posició. I després repetim amb quatre-sis, a continuació, sis-vuit, en cada iteració, movent-se cap a la dreta. 

Així que donat a vuit persones, quantes parelles comparacions Què vaig fer mentre caminava des esquerra a dreta en un d'aquests iteració? Quantes comparacions? Set, oi? Perquè si hi ha vuit persones, però que tenen la parella ells i que es mantenen en moviment un salt a la dreta, no va a tenir vuit comparacions perquè no es pot comparar un element contra si mateixa, o que ho faria només inútil, pel que té set. O, més generalment, si tenim n persones, que fer N almenys 1 comparacions amb ordenament de bombolla. 

Així que anem a considerar ara el bo o mal ordenament de bombolla en realitat era, i tractar per donar-nos vocabulari amb que als algoritmes de crítica com aquesta, i aviat el nostre propi. Així que el primer pas a través ordenament de bombolla, la primera vegada Vaig caminar d'esquerra a dreta a la etapa, em n almenys 1 comparacions prendre. I això serà la meva unitat de mesura, no? Jo estava una mica parlant i passejant, alguna cosa ràpid, una mica lent, així que comptant el meu número de segons no està particularment revelador, però comptant el nombre de operacions que vaig fer el dilluns, la comparació de dues persones, que se sent com una bona unitat de mesura. 

Així n almenys 1 passos la primera vegada, però llavors, ¿què va passar després? Quina és l'avantatge d'una sola passada a través d'una llista d'una altra manera sense classificar? Què pots dir-me sobre l'element que va ser tot el camí per allà? Sí? Aquest va ser l'element més important, oi? El número vuit, tot i que començat aquí, cada vegada que seva comparació contra un veí, va mantenir bombollejant cap a la dreta costat de la llista. I, en efecte, que és on l'algorisme obté el seu nom. 

Ara per aquesta lògica, el nombre de comparacions Necessito que faig en el segon temps Faig que passi d'esquerra a dreta? n menys 2, oi? Seria simplement estar desaprofitant meu temps si mantenir comparant vuit en contra d'algú més perquè ja sabem ella era al lloc correcte. Així que això és una mica d'una optimització, de manera que el següent pas serà més n menys dos passos, on n és el nombre de persones. Ara vostè pot tipus d'extrapolar, fins i tot si no ets un expert en informàtica, com això acaba. Al final d'aquest algorisme, presumiblement vostè té només una comparació esquerra. Vostè ha de fixar el tipus de a partir de la llista en cas que dos i un són fora de servei i ha de ser un i dos, pel que aquest toqui fons en més 1 comparació final. 

Ara el punt, punt, punt tipus d'ones és mans d'alguns dels detalls més sucosos, però seguirem endavant i simplificar. Si vostè recorda d'alta escola, francament, molts de vostès tingut llibres de matemàtiques que tenien un full de trucs poc a la portada o la contraportada que mostrava sumes això de la sèrie com aquesta última instància, va afegir fent. En el cas general, si té un variable com la n, i de fet aquest, si un mira al seu llibre de matemàtiques de la vella escola, veuries que aquesta realitat se suma a aquesta suma aquí, n vegades n almenys 1 tot dividit per 2. Així que per ara permeteu-me estipulo això és cert, pel que en un acte de fe, això és el que això resumeix fins, i vam poder demostrar que en un cas més general. Però ara anem a ampliar això. Així que anem a multiplicar això, així que això és n al quadrat, menys n, tot dividit per 2. Això és realment n al quadrat, dividit per 2, menys n sobre 2, així que això és tot el agradable i interessant. Però, què passa si ens ara plug-in d'un valor? Suposem que jo no tenia vuit persones, però diuen que un milió. I un milió només perquè que és un nombre bastant gran, anem a connectar que en i veure què passa. Així que si connecto un milió en aquesta fórmula Vaig a aconseguir un milió de quadrat, dividit per 2, almenys una milions, dividit entre 2. Ara ¿què és això serà igual? Així quals 500 mil milions, menys de 500.000. I si faig realment que les matemàtiques, vol dir que que la classificació d'un milió de les persones amb l'ordenament de bombolla em podria prendre 499999500000 passos o comparacions en el final, només estem extrapolant. 

Això se sent bastant lent, però, francament, mesurament d'una entrada particular, així, no és tot el que eloqüent. Però de fet, sí suggereix que a mesura que n es fa més gran i més gran, aquest algorisme tipus de se sent pitjor i pitjor, o que realment començar a sentir el dolor d'aquesta exponenciació, que n al quadrat, que afegeix bastant ràpid. I aquest detall no és perdut en les persones, de fet, Fa alguns anys un cert senador que era campanya, es va asseure per a una entrevista amb Eric de Google Schmidt, CEO de l'època, i va ser posada en dubte amb una pregunta igual que estem explorant avui. Anem a fer una ullada. 

[REPRODUCCIÓ DE VÍDEO] 

-Senador, Ets aquí a Google, i m'agrada pensar en la presidència com una entrevista de treball. Ara, és difícil aconseguir un treball com a president, i vostè va a través dels rigors ara. També és difícil d'aconseguir una feina a Google. Tenim preguntes, i ens demanar a les nostres preguntes dels candidats, i aquest és de Larry Schwimmer. Què-- que vostès pensen que sóc és broma, està just aquí. Quina és la forma més eficient de ordenar un milió d'enters de 32 bits? 

-Well-- 

-Ho Sento, tal vegada-- 

No, no, no. Crec que l'ordenament de bombolla seria el camí equivocat. 

Anem, que li va dir això? No vaig veure ordinador la ciència en el seu fons. 

-Tenim Nostres espies en allà. 

-ok, Anem a demanar una diferent pregunta de l'entrevista. 

[FI REPRODUCCIÓ DE VÍDEO] 

ALTAVEU: Així que parlant de nombres específics tot i que, no serà tan útil. No és una lliçó de vida que la bombolla espècie, donat un milió d'entrades, podria prendre fins a 500.000.000.000 passos. Realment no es pot generalitzar massa eficaçment a partir d'aquest i prendre bones decisions de disseny en escriure programes. Així que anem a centrar-nos encara sobre com podem simplificar aquest resultat. 

Així que he ressaltat en groc aquí el resultat de n al quadrat dividida per 2, per la qual cosa 1.000.000 quadrat dividit per 2, i després He destacat el la resposta final va ser una vegada que restem off n dividit per 2. I l'afirmació que faré ara és, qui diables li importa si es resta de una mica més de 2 n edat quan la primera part d'aquesta fórmula és molt més gran? Domina l'altre termini, n al quadrat dividit per 2 és molt més gran, amb claredat, com n es fa gran com un milió, això és realment una gran diferència en al final de la dia entre 500.000.000.000 i 499.999.500.000? En realitat no. I així ho anem a fer com científics de la computació és ignorar els termes d'ordre inferior i prendre alguna cosa com això i realment només simplificar l' terme que es va a importar. Els més grans de les nostres conjunts de dades aconsegueixen, més gran les nostres bases de dades reben, més pàgines web hem de buscar, més amics que tenen a Facebook. 

Com n es fa més gran, estem molt va a preocupar-se pel més gran termini en qualsevol tipus d'anàlisi de nostre acompliment algoritmes. I jo vaig a dir, saps què, ordenament de bombolla està en l'ordre de la gran O, de l'ordre de n al quadrat. No és exactament n al quadrat, com hem vist, però a qui li importa sobre els terminis més petits, i, francament, que realment li importa si dividim per 2? Això és només un factor constant. I és de 500 mil milions contra 250 milions realment tan gran d'un acord? Jo només podia esperar un any, deixar que el meu portàtil literalment obtenir el doble de ràpid en el maquinari, i aquest tipus de diferència simplement desapareix de forma natural amb el temps. 

El que ens importa és l'expressió, la part de l'expressió que variarà com la nostra entrada es fa més gran i més gran. I de fet, en el món real, això és el que està passant cada vegada més és les entrades als nostres problemes i algoritmes són cada vegada més gran. Tan gran O serà la notació, la notació asimptòtica, que acabem de utilitzar com a científics de la computació per descriure el rendiment, o el temps d'execució, d'un algorisme. Així que podem comparar algorismes en equips diferents escrits per diferents persones, utilitzant alguna mètrica fonamentalment similar com el nombre de comparacions que ets fer, o potser el nombre de swaps vostè està fent. 

El que no anem a recompte és la quantitat de temps que passa al rellotge a la paret normalment. El que no anem a preocupar sobre és la quantitat de memòria està utilitzant avui menys, encara que això és altre recurs que podríem mesurar. Anem a tractar de basar la nostra anàlisi només en les operacions bàsiques, els que, francament, que es pot veure més visualment. Així que amb una mena de gran O de n quadrat, afirmo que O de n al quadrat és un límit superior en l'anomenada moment de la bombolla de tipus corrent. En altres paraules, si vostè volia dir que hi ha aquest límit superior de la quantitat de els passos d'un algorisme pot prendre, que estarà en el gran O de n quadrat en aquest cas, un límit superior. 

Què passa si en comptes canvi el història sigui no es tracta d'una espècie de bombolla, però aquest límit superior. Pots pensar en un algoritme que hem vist en ia el límit superior, màxim mesurar el temps o les operacions, es diu que està fitada per n, una funció lineal, no una quadràtica que és corb? Què és un algorisme que Sempre presa no més que com n passos, o Passos 2n, 3n o passos? Sí? 

AUDIÈNCIA: Trobar el major nombre en una llista? 

ALTAVEU: Perfect, la recerca de el major nombre en una llista. Si em donen una llista de persones, per exemple, cada un que és la celebració d'una sèrie, ¿Quin és el nombre màxim de mesures que hauria portar, una persona raonablement intel · ligent, trobar la persona més gran en aquesta llista? n, oi? Com que en el pitjor dels casos, on podria ser el major valor? És cert, tot el camí al final. Així que en el pitjor dels casos límit superior, que podria haver d'anar tot el camí aquí i ser com, oh, aquí hi ha el número vuit, o el que sigui que el valor és. Ara només seria estúpid si ho seguia fent, oi? Estàs buscant més i més elements si l'últim d'ells és d'allà? Així que sens dubte, n és un límit superior. Jo no necessito prendre més passos que això. 

Llavors, què si en comptes vaig proposar que existeixen algorismes en aquest món que tenen un temps d'execució que és delimitada per gran O de log n, log n? On hem vist això abans? Sí? 

AUDIÈNCIA: Al problema de guia telefònica? ALTAVEU: Igual que el problema de la guia telefònica. Quina va ser la mesura de la molt temps o quantes llàgrimes de TI em va portar a trobar algú com Mike Smith a la guia telefònica? Ens deia que era log n, i fins i tot si desconegut o que és una mica nebulosa què logaritme o exponent va ser, només recorda que log n generalment es refereix al procés, en aquest cas, de dividir alguna cosa a la meitat una altra vegada, i una altra, i una altra, i una altra, de manera que obté cada vegada més petita a mesura que fa això. 

Així que ingressi de n es refereix, és clar, l'exemple de guia telefònica, per a recerca binària en teoria, quan tenia les portes virtuals en el tauler, o quan Siguin era buscant alguna cosa. Si s'hagués utilitzat de recerca binària, log n seria el límit superior de la quantitat temps que pren. Però aquests algoritmes que corrien a log n assumit el detall clau? Que la llista es va solucionar, oi? El seu algorisme és dolent si seva entrada no està ordenada, i no obstant això està utilitzant una mena de recerca binària ja que podria saltar dret sobre l'element sense adonar-se que és de fet allà. 

Ara, què podria significar això, gran O d'un? Això no vol dir que el seu algorisme té una i només una etapa, només significa que es necessita un nombre constant de passos. Potser sigui 1, potser és 10, potser és 1000, però és independent de la mida del problema. No importa què tan gran és n, un algorisme de constant de temps sempre té el mateix nombre de passos. Llavors, què podria ser un algorisme hem parlat o simplement intuïtivament que ve a vostè que sempre s'executa en l'anomenada constant de temps? Sí? 

AUDIÈNCIA: Afegeix dos nombres. ALTAVEU: Afegeix dos nombres, 2 més 2 és igual a 4, fet. Així que podria funcionar, què més? Què tal món més real, no? 

AUDIÈNCIA: Trobar el a primera hora de la llista. ALTAVEU: Trobar a la primera element en una llista, segur. En realitat hem estat parlant sobre les matrius ja, Com s'arriba a la primer element d'una matriu, no importa quant de temps la array és en codi C? Vostè només ha d'utilitzar com el suport notació zero, bam, ets allà. I de fet, matrius, com un part, suport cosa generalment conegut com accés aleatori, d'accés aleatori memòria, perquè vostè pot literalment saltar a qualsevol lloc. Podem fer això encara més simple podem rebobinar fins a la setmana zero quan vam fer les ratllades. Quant de temps es necessita perquè la diuen bloc en Scratch per executar? Només la constant de temps, oi? Parla, di alguna cosa, no importa com grans rascades món és, sempre és va a prendre la mateixa quantitat de temps dir simplement alguna cosa. 

Així que aquesta és la constant de temps, però quina és l'altra cara? Si això era superior límits, el que si volem per descriure els límits inferiors dels nostres algorismes de temps d'execució? Gairebé un millor cas potencialment, si es vol, encara que aquests termes poden aplicar-se a millor casos, els pitjors casos, els casos mitjana més en general, però ens concentrarem en cotes inferiors en termes més generals. Què és un algorisme que té una cota inferior de n passos, o passos 2n, 3n o passos? Alguns factor de n passos, aquest és el seu límit inferior. Sí? 

AUDIÈNCIA: ordenament de bombolla? 

ALTAVEU: ordenament de bombolla presa que mínimament n passos, per què? Perquè és això? Per què aquest començament per anar a vosaltres intuïtivament, fins i tot si ho fa, no només encara? Sí? 

AUDIÈNCIA: [inaudible]. ALTAVEU: Exactament. En el millor escenari possible de ordenament de bombolla, i una gran quantitat d'algorismes, si et lliuro a vuit persones que ja estan ordenats, seria absurd per a vostè, l'algorisme, per anar cap enrere i endavant més d'una vegada, no? Perquè tan aviat com es caminar a través de la llista una vegada, vostè ha de donar compte, oh, no vaig fer cap swaps, aquesta llista està ordenada, sortida. Però això va a prendre vostè n passos. 

I al revés, el que és una altra forma de pensar sobre això? Ordenament de bombolla és un omega, per així dir-ho, de n, perquè si ens fixem en menys de n elements, el que és la qüestió fonamental que hi ha? No saps si és ordenada, correcta. Nosaltres els humans podrien ullada a les vuit persones i ser com, oh, està ordenada, que no em n mesures prendre, però ho van fer. Els seus ulls, tot i que tipus de tenir un gran camp de visió, vas mirar vuit elements, vas mirar a vuit persones, això és vuit passos amb eficàcia. I només si camí a través de tot llista ¿M'adono, sí, ordenats. Si m'aturo a meitat de camí de pensar, tot dret, que és bastant ordenades fins al moment, ¿Quines són les probabilitats que no està ordenada? Això no hi haurà algorismes correctes. Podria ser més ràpid, però incorrecta. 

Així que ara tenim una manera de descrivint una menor grau, i què passa amb la constant de temps? Què és un algorisme que té un menor amb destinació en el seu temps d'execució d'un? 1 etapa, 2 etapes, 10 passos, però constant, independent de n, la mida de l'entrada? Sí, a la part posterior. 

AUDIÈNCIA: printf? ALTAVEU: Què és això? AUDIÈNCIA: printf? ALTAVEU: printf. Bé, segur. Així que es necessita un nombre fix de passos. I hauria ara-- ara que estem parlant de codi C i no Scratch, cosa com per exemple, amb printf, hauríem de començar a anar amb compte. A causa printf això, pren d'entrada, que és una cadena, i les cordes no tenen tècnicament longitud. Així que si ara volem recollir en tu, si no t'importa, tècnicament podríem argumentar que printf no tenir una entrada de longitud variable, i segurament pot ser que prengui més temps per imprimir una cadena d'aquest llarg, d'aquest llarg. 

I què si tenim en compte només el classificació i recerca exemples? Què passa amb Mike Smith al telèfon llibre, o de recerca binària més general? En el millor dels casos, el que podria succeir? Obro la guia telefònica i, bam, hi ha nombre de Mike Smith. Jo li puc dir immediatament. 

Va prendre un pas, potser dos passos, però un nombre constant de passos si vaig tenir sort. I, francament, que vam veure en Dilluns a la seva companya de classe aconseguir bastant sort dues vegades seguides. I això va ser fet constant vegada en uns baixos límits en l'algorisme en qüestió per trobar el nombre 50 darrere de les tancades portes. 

Ara, com un a part, si descobreix que tant la gran O, el límit superior, i l'omega, el límit inferior, són un en el mateix, que és la mateixa fórmula en parèntesi, també pot dir, només per ser de luxe, que hi ha alguna cosa en zeta de n theta o d'algun altre valor. Això només significa que quan gran O i omega són els mateixos. Ara què passa amb la selecció espècie? Anem a utilitzar aquest nou vocabulari. En la selecció de classificació, que eren fent de nou, i una altra, i una altra? Jo anava cap enrere i endavant a través de la llista, a la recerca de qui? El nombre més petit. 

Llavors, com molts passos, com moltes comparacions van fer I haver de fer per tal d'esbrinar qui l'element més petit de la llista era? n menys 1, no? Perquè si acabo de començar amb el qual estic donat i jo li poso a comparar, llavors ell o ella, li o ella, ell o ella, només pot aparellar elements junts n almenys 1 vegades. Així selecció té espècie de manera similar n almenys 1 passos la primera vegada. 

Quants passos que em porti a trobar el segon element més petit? n menys 2, perquè estic sent ximple si segueixo mirant les mateixes persones de nou si he ja ho seleccionat o ella i els va posar en el seu lloc. I el tercer pas, n mínim 3, llavors n almenys 4. Hem vist aquest patró abans, i de fet Selecció de tipus similar té un límit superior de n al quadrat si fem aquesta suma. Quin és el seu límit inferior, la selecció espècie? Com a mínim, la quantitat de temps de selecció ha de ordenar prendre, com el definim dilluns? Proposar dues opcions. Potser és n, com abans. Potser és n al quadrat, ja que és ara com el límit superior. 

AUDIÈNCIA: n al quadrat. ALTAVEU: n al quadrat. Per què? 

AUDIÈNCIA: Com que té per definir [inaudible]. 

ALTAVEU: Exactament. Almenys pel vaig definir ordenament per selecció era bastant ingènua, seguir endavant, trobar l'element més petit. Anar de nou, trobar l'element més petit. Anar de nou, trobar l'element més petit. No hi ha cap mena de optimització motiu podria deixar-me avortar després només n o menys passos. Així que de fet, la selecció tipus, omega de n al quadrat. 

Què passa amb l'ordenació per inserció, on vaig prendre que em van donar, i llavors jo li vaig deixar o ella en el lloc correcte? Llavors vaig procedir a la segona persona, ell o ella es va deixar caure al lloc correcte. Llavors la següent persona, es va deixar ell o ella en el lloc correcte. Tingueu en compte que això és molt lineals, per així dir-ho. Sóc una línia recta, estic no anar i venir, Mai mirar cap enrere en realitat, però el que està succeint quan ho introdueixo o ella en el començament de la llista com ho vam fer dilluns? El que està succeint? Sí? AUDIÈNCIA: [inaudible]. ALTAVEU: Sí, això va ser la captura, oi? Vostè pot recordar de seus companys de classe, si estaven fent cap moviment amb seus peus, que era una operació. Així que si hi havia tres persones aquí i la nova persona pertanyia fins allà, en una llarga etapa com aquesta, és clar, o ella només podia anar fins al final. Però si estem pensant en un ordinador i una matriu de la memòria, aquestes persones van a haver de remenar més per donar cabuda a aquesta persona. I perquè n almenys 1 shufflings, n almenys 2 shufflings, n almenys 3 shufflings és només una mica de passant darrere de mi, no al davant de mi com abans, en algun sentit. Ara com un part, i com que podria haver vist en línia si vostè comença a furgar sobre tipus, hi ha tan molts diversos per aquí, alguns d'ells millor que altres. De fet, és un Bogosort això és bastant divertit per mirar cap amunt. Bogosort pren un conjunt de números o dir una baralla de cartes, les baralla a l'atzar, i comprova si estan ordenats. I si no, ho fa de nou. I si no, ho fa de nou. Si no, ho fa de nou. Increïblement estúpid. 

I de fet, si vostè llegeix igual que l'article de Wikipedia, el seu sobrenom és estúpida espècie. Amb el temps funcionarà, amb sort, donat el temps suficient, però aquesta quantitat de temps podria arribar a alentir. Així que si jo pogués, anem a accelerar les coses des de l'exemple de Mary Beth abans, per tenir alguns elements més, sinó dos processadors més. Dues persones, si no li importaria acompanyar-me. Què hi ha de 1 per aquí, i anem a vaya-- ningú allà? Ningú d'allà? Okay. Vostè amb el negre camisa, sí, anem cap avall. Molt bé, quin és el teu nom? 

AUDIÈNCIA: Peter. 

ALTAVEU: Què és això? 

AUDIÈNCIA: Peter. ALTAVEU: Pedro, David, encantat de conèixer-te. Molt bé, tenim Peter aquí, si volen venir a la taula aquí. I quin és el teu nom? 

AUDIÈNCIA: Elena. ALTAVEU: Elena. Bé, encantat de conèixer-te. Elena compleix amb Peter. Peter, Elena. I necessitarem Andrew aquí també, si us plau. I el seu repte va ser per ordenar una baralla de cartes. I si no familiar, coberta de targetes deu en última instància, ordenar una mica alguna cosa com això on farem els clubs, a continuació, les espases, a continuació, els cors i diamants, des ace com un, tot el camí fins al rei. 

Les targetes que vaig a donar-li seran 52 en quantitat. Anem a similar vegada que, en un moment. Anem a llançar Andrew a la pantalla aquí, per tal de veure com fer això. I perquè tot això és tant més visible, aquestes són les cartes que vaig rebre a Amazon. Així que ja són a l'atzar solucionar, i que anem a mesurar el temps que vostè. I anem a viure en la realitat d'aquest temps, així que tractarem de pressionar perquè si no això serà tediós ràpidament. Si es pogués procedir a ordenar 52 elements junts a través d'alguns mitjans, ara. 

I de nou, quan veiem aquests nois fan el que, al final es produirà una evident resultat, pensa realment com ho estan fent cada un que, com podria descriure-ho. Perquè de nou, aquests són tots els processos, algoritmes que nosaltres donem per fet com un ésser humà. Però vostè ha tingut probablement molt intuïció, molt abans que fins i tot pensat en prendre un classe d'informàtica que podria haver tingut la intuïció amb que per resoldre problemes com aquest. Però una vegada que reconeixen els patrons i començar per formalitzar els passos amb els quals vostè està la solució d'aquests problemes, trobareu que vostè pot solucionar molt més interessant i molt més complex problemes ràpidament. Així que algú del públic, el que és almenys un element de l'algoritme que estan fent servir aquí? 

AUDIÈNCIA: [inaudible] ALTAVEU: Què és això? AUDIÈNCIA: Per exemple. ALTAVEU: Per exemple. Així que primer que s'estan agrupant tots els diamants junts pel que sembla, tot el cors junts el que sembla, i així successivament, sense respecte per als números de les targetes. I ara apareixen, per exemple, ser ordenant-los per nombre. Molt bona. 

Molt bé, així que el que va a ser el pas final, llavors aquí? Un cop tenim quatre pals ordenats, el que Per què hem de fer per a les quatre piles amb la finalitat d'aconseguir-ne un coberta ordenats, simplement? Així que hem de combina una altra vegada. 

Així que hi ha una idea interessant que de nou, diria, és molt intuïtiu fins i tot si vostè mai podria haver bufetejat aquest tipus d'etiqueta. Aquesta noció fonamental de la divisió el problema no a la meitat d'aquest temps, però almenys en quatre peces. Resoldre gairebé problemes fonamentalment idèntics en l'aïllament d'un a l'altre, i després combinar els resultats. I, excel · lent, fet. Molt bé, una gran ronda d'aplaudiments, si poguéssim. 

[Aplaudiments] 

ALTAVEU: No tinc ni idea del que va a fer amb ells, però aquí tens. Moltes gràcies. Així que anem a veure, a dos minuts i vuit segons, de si vol desafiar als teus amics. Llavors, què va a ser una presa de distància d'aquesta que podem aprofitar de forma més general? Bé, pensi de nou a aquest conjunt de nombres, i pensar de nou ara a algunes de les pseudocodi que hem escrit en el passat, i aquest va ser el pseudocodi per resoldre el problema de la guia telefònica. Per la qual cosa en pseudocodi I enumerat una manera més metòdica de descriure la forma en què vaig fer un molt intuïtiu algorisme humana de dividir el telèfon llibre per la meitat, repetir, repetir, repetir, fins que trobi algú com Mike Smith, si és fet a la guia telefònica. 

Però quin tipus de vaig utilitzar el que jo anomeno un enfocament molt iteratiu aquí, en particular notificació línia 8 i la línia 11. Aquests són evidència d'un procés iteratiu enfocament, un enfocament de bucle, perquè això és exactament el comportament que indueixen. Aquestes línies de tots dos diuen anar a línia de tres, i vostè pot tipus de pensar que en el seu l'ull de la ment com un bucle. Li està dient a tornar a pujar al pas 3 i repetir, una i altra vegada, i una altra vegada. 

Però i si aprofitem una idea clau aquí que vam fer no l'última vegada, i simplificar la línia 8 i línia 11 i els seus veïns com acaba això, en groc. No és fonamentalment escurçar el pseudocodi molt, però està canviant fonamentalment la naturalesa del meu algorisme. El que ara estic dient en el pas 7, al pas 10, és la recerca de Mike de la mateixa manera exacta, però només en l'esquerra la meitat o la meitat dreta. 

Així, en altres paraules, si Començo des del pas un, recollir la guia telefònica, obert a mig de guia telefònica, mirar noms, si es troba entre Smith nom d', truqueu a Mike, la resta si Smith és anterior al llibre, pas 7 buscar Mike en la meitat esquerra del llibre. Però aquest tipus de se sent com m'està deixant penjar, oi? En groc, és un instrucció, però com puc buscar Mike a l'esquerra la meitat de la guia telefònica? On tinc un algorisme amb el qual pot buscar a algú com Mike Smith? Bé, ens està mirant a la cara. Literalment, puc utilitzar la mateixa exacta programa va efectivament al cim de nou i tornar a córrer les mateixes línies de codi. 

Així que, tot i que aquest ha de sentir com una mica d'una definició cíclica on vostè està responent a algú és pregunta per només una espècie de demanar la mateixa pregunta de nou, com per què, per què, per què? La realitat és perquè hem codifiquem un parell de línies especials, el pas 4, que és un si, i el pas 12, el qual és efectivament una altra branca, perquè tenim aquestes mesures provisionals, aquest algorisme acabarà si trobar Mike, o si no ho fem. Però en el pas 7 i 10 ara, tenim el que anomenarem un algorisme recursiu. I recursivitat és de fet una idea poderosa això és una mica lucinant al principi, que ara podem aplicar la següent manera. 

Combinar tipus serà l'últim tipus que mirem, almenys en la classe formal. I és fonamentalment diferent dels últims tres, i certament últims quatre si incloem Bogosort. Aquí està el pseudocodi per merge sort. Quan en l'entrada de n elements, de manera que donada una matriu de grandària n, si n és menor que 2, tornar. Llavors, ¿per què he de seny comprovar primer? Quina és la implicació que si et lliuro una matriu la longitud n és menor que 2? Ja està ordenada, òbviament, no? Com que la llista té ja sigui un element, que és trivialment ordenada perquè és l'únic que hi ha. O, és de mida zero, el que significa no hi ha res arreglar, així que per la naturalesa que està ordenada. No hi ha res malament allà. Així que aquest és el nostre anomenat cas base. 

Que és similar en esperit al que vam fer amb Mike. Si Mike en la guia telefònica, li diuen. Si ell no hi és, donar-se per vençut. És un cas base de l'anomenada, per assegurar aquest algorisme al final del dia s'aturarà en certes circumstàncies. 

Però aquí hi ha el salt de fe ara, una altra cosa, ordenar la meitat esquerra dels elements, a continuació, ordenar el dret mitjà dels elements, i després fusionar les meitats ordenats. I aquí és on se sent com que estem Copping terme. T'he demanat per ordenar n elements, i estic dient, bé, no és per la classificació l'esquerra i la classificació de la dreta. El que dic és una una altra cosa, i això és el tema clau sembla en la intuïció fins ara, hi ha aquesta tercera etapa de la fusió. Què encara sembla tan ximple en esperit, com acaba de fusionar coses junts, sembla ser un pas clau cap a la muntatge de dos problemes que es van dividir en última instància per la meitat. 

Així fusionar tipus, farem això, si em humor mi, amb una manifestació més, només perquè tinguem una mica de números per treballar amb. Puc intercanviar 08:00 estrès boles per a vuit persones? Molt bé, i tu tres, quatre en aquesta secció, cinc, sis, i anem a do 7, 8, anem a dalt. Acceptar, sí acord. Minus 8, allà anem, més 1. Excel · lent. Tot ve dret cap amunt, anem a ràpidament li donarà nombres. El número dos, número tres, número quatre, nombre cinc, sis, set-vuit. Vaig 08:00 correctament aquesta vegada. 

OK, així que endavant si es pogués, i anem a ordenar en l'ordre original que vam tenir ahir que semblava així, si no t'importa. I anem a fer-ho davant de la taula. Molt bé, així que fusionar espècie. Aquí és on es va per aconseguir una espècie d'interessant, perquè em sembla que estic donant a mi mateix molt menys informació avui en dia. 

Així fusionar tipus primer de tot a l'entrada de n elements, i és, òbviament, no menys de dos, és 8, així que tenen una mica més de feina a fer. Així que ara estem mentalment com una classe estan ara en la branca else, el que significa tres passos. En primer lloc, he de ordenar la meitat esquerra dels elements. Llavors, com faig per fer això? Bé, vaig a classe de mentalment dividir la llista aquí, vostè no ha de moure físicament, i estic centrarem només en la meitat esquerra dels elements aquí. Llavors, com faig per ordenar una llista ara de la mida de quatre? Quin és el meu algorisme? Primer comprovo és n menys de dos, no, així que em dedico al bloc diferent. Ordenar a l'esquerra de la meitat dels elements. 

Així que ara de nou, mentalment, i aquí és on has acumular una gran quantitat de història mental, si es vol. Ara estic ordenant l'esquerre la meitat de la meitat esquerra. Molt bé, així que ara dic a mi mateixa combinació algoritme d'ordenació, és n menys de dos? No, és de dos, així que he de ordenar la meitat esquerra i la meitat dreta. Així que aquí anem, ordenar la meitat esquerra. Per què no acaba de fer un pas cap endavant. Quin és el teu nom? 

AUDIÈNCIA: Darren. 

ALTAVEU: Dan. Dan ha fet un pas endavant. 

AUDIÈNCIA: Darren. ALTAVEU: Darren, fet. ¿Va dir Darren o Dan? 

AUDIÈNCIA: Darren. 

ALTAVEU: Darren. Acceptar, Darren ha intensificat cap endavant i ara està solucionat. I això és gairebé una afirmació estúpida, oi? Realment no sembla estar assolint res, però anem a procedir. Ara vaig a ordenar la dreta mitjà dels elements. Quin és el teu nom? 

AUDIÈNCIA: Lucas. 

ALTAVEU: Lucas. Anem, un pas endavant. Fet, he classificat Lucas. La meitat esquerra està classificat i la meitat dreta està ordenada, però de nou, hi ha un pas clau aquí. Què he de fer la propera? Combinar les meitats ordenats. Ara tindrem només tots enrere i cap endavant d'aquesta manera, perquè Jo com que necessito una mica d'espai zero. És gairebé com aquests nois estan en una taula, i necessito una mica d'espai per moure'ls a. Així que vaig a fusionar vostès per mirar en la meitat esquerra i la meitat dreta. I que, òbviament, és el primer, la meitat esquerra o la meitat dreta? Així que la meitat dreta, per la qual cosa anem a passar a Luke aquí a la posició original de Darren. I ara fusionar la seva meitat esquerra a, Darren va a moure a la dreta allà. 

Així que se sent com gairebé un efecte bombolla espècie, però el meu algorisme fonamental, molt diferent aquesta vegada. Però ara és on les coses es posen una mica molest perquè vostè haver de rebobinar mentalment on vaig deixar fora. Acabo vaig fondre les meitats ordenades, el que significa que estic en el meu algorisme? He d'ordenar la meitat dreta, no? 

Si rebobina, literalment al vídeo, podràs veiem que arribem a aquest punt de Luke i Darren per la classificació de l'esquerra la meitat de la meitat esquerra. Llavors ens fusionem els meitats ordenades, que significa que el següent pas és ordenar la meitat dreta de la meitat esquerra. Molt bé, així que anem a fer això més ràpidament. Molt bé, sis, vaig a reclamar que ara s'ordenen, anem cap endavant. Quin és el teu nom? 

AUDIÈNCIA: Adriano. 

ALTAVEU: Adriano. Adriano està solucionat. I quin és el teu nom? 

AUDIÈNCIA: Alex. 

ALTAVEU: Alex està ara ordenades. Medi esquerre, mig dret, ¿Quin és el pas final? Combinar. Pretty trivial, així que estic va a fusionar en sis, fer un pas enrere, 8, fer un pas enrere. I ara noti que això és un dinar per emportar útil, el que ara és veritat sobre la meitat esquerra de la llista, independentment de com comencem? S'està ordenada. 

Ara que no està ordenada en el gran esquema de les coses, però està ordenada de forma independent de l'altra meitat. Ara el que pas sóc jo en si segueixo rebobinat de com va començar la història? Ara he de ordenar la meitat dreta. Així que ara estem en el camí de tornada el principi de la història, i farem això amb més rapidesa. Així que vaig a ordenar la meitat dreta de tota la llista. Quin és el següent pas? Ordenar la meitat esquerra de la meitat dreta. Ordenar la meitat esquerra de la meitat esquerra de la meitat dreta. I quin és el teu nom? 

AUDIÈNCIA: Omar. 

ALTAVEU: Omar, un pas endavant, fet. La meitat esquerra està ordenada. I quin és el teu nom? 

AUDIÈNCIA: Chris. 

ALTAVEU: Chris, fer un pas cap endavant, que ara està ordenada. Quin és el pas clau ara? Combinar. Així que un va a fusionar en el seu lloc aquí, si pogués fer un pas enrere, -tres va a fer un pas enrere, es fonen. Així que la meitat esquerra de la meitat dreta, ara està solucionat. Francament, aquest algorisme se sent com que estan perdent molt més temps que abans, però si ho féssim això en temps real, anem a veure el que els robatoris de pilota serà. Ara aquí estic, no la meitat de la meitat dreta, m'ho dius a mi anar endavant i ordenar la meitat esquerra. Pas endavant, com et dius? AUDIÈNCIA: Ramsey. ALTAVEU: Ramsey està solucionat. Quin és el teu nom? 

AUDIÈNCIA: Marina. 

ALTAVEU: Marina està classificat com així, si vostè pren un pas cap endavant. Pas clau és ara fusionar, estic va a arrencar de les meves dues llistes, esquerra i dreta. Cinc serà el primer, -set serà el pròxim. I de nou, això és deliberat. El fet que estan prenent passos cap endavant i cap enrere té la intenció de representar que no podem fer aquest algorisme en el seu lloc amb la mateixa facilitat com a espècie de bombolla, i la selecció de tipus, i tipus d'inserció en el qual només guardat intercanviant persones. Jo, literalment, necessito una espècie de paper esborrany en el qual per posar a aquestes persones mentre faig la fusió, i llavors puc tornar a posar al seu lloc. I això és clau perquè estic utilitzant un nou recurs, l'espai, no només temps. 

OK, això és increïble. La meitat esquerra està ordenada, la meitat dreta és pas ordenat, ara que la fusió de tecla. Com vaig a fusionar això? Així que si vostè segueix el meu la mà esquerra i la mà dreta, Vaig a assenyalar la meva mà esquerra en la meitat esquerra, la mà dreta en la meitat dreta, i ara he de decidir pas a pas a qui es fonen en. Que òbviament és el primer? Número u. Així que vine aquí, aquí està el nostre bloc de notes. Així que ara el número u, i l'avís el que faré amb la meva mà dreta, Vaig a moure la meva mà dreta una passar per sobre al punt número tres, i ara he de fer la mateixa decisió. I en realitat de peu just a davant de Lucas aquí si pogués, perquè aquest és el nostre bloc de notes. Llavors, qui segueix? Tenim Lucas amb el número dos o Chris nombre tres. Òbviament Lucas, nombre dos, pel que vénen aquí. 

Però la meva mà esquerra ara va a s'incrementa per apuntar a Darren, i aquí hi ha la clau de portar amb la fusió, que seguiré fent això, Òbviament, si vostè amable de seguir la lògica. Però les meves mans mai no són anirà cap enrere, el que significa que només alguna vegada vaig a mudar a l'esquerra amb el meu procés de fusió, i això serà clau per la nostra anàlisi en un moment. 

Així que ara anem a acabar això ràpidament. Així que 3 ve a continuació, després quatre ve a continuació, i ara cinc ve a continuació, i després sis, i 7, i, finalment, vuit. Se sent com l'algorisme més lent però, però no si en realitat executar en el mateix tipus de velocitat de rellotge, de manera que parlar, amb el mateix tic-tac del rellotge com abans. Per què? Bé, donem una mirar al resultat final. 

Tornem aquí, deixa tiri cap amunt una demostració visual del que acabem de fer. Apropar aquí, en aquesta pàgina aquí, dient Firefox que volem fer cua en aquesta caixa, anem a dir espècie de bombolla, amb la qual ara estem ben familiaritzats, ordenació per selecció, que és una altra un bastant senzill, i ara d'avui merge sort, el qual serà el nostre final culminant. La raó per la qual va prendre molt més temps aquí amb els éssers humans i em verbalment és, Òbviament, estic explicant cada pas. Però si simplement executa aquest, molt com ho vam fer espècie de bombolla i selecció espècie no només visualment, rellotge quant més eficient Aquest palanquejament divisió i conquesta pot ser quan s'aplica a un conjunt de dades que està ni tan sols mida de vuit, però fins i tot molt, molt més gran. Dono combinar espècie, un al costat de l' costat amb aquests altres algoritmes. Això es posarà dolorosa ràpidament, i el final no és particularment culminant, que només acaben ordenats. Però la clau per dur és que mirar com més ràpid fusionar espècie era, llevat que pensis que sóc només una mica de jugar amb vostè. Si fem això per última vegada, Anem a recarregar això, tornem i triar espècie de bombolla, i només per diversió, anem a triar la inserció espècie, només per si de cas. I aquesta vegada de nou, anem a triï Fusió de classe i anem a de fet executar aquests costat a costat. 

I no és, de fet, un cop de sort. El que he fet és efectivament tinc dividit la meva entrada a la meitat, de nou, i una altra, i una altra. I només hi ha tantes vegades que puguis dividir la seva entrada en meitats, esquerra i la dreta. Quina és la fórmula que ens seguim veient que descriu la divisió per la meitat una altra vegada, i una altra, i una altra, i una altra vegada? 

AUDIÈNCIA: log n. 

ALTAVEU: Inicieu sessió n. Però després hi ha un altre pas clau, aquest algorisme no és log n passos. Si només es log n passos, estaríem en el mateix problema com abans, on no podem estar Segur que tot està ordenat. Cal mirar mínimament en n elements per assegurar-se n elements s'ordenen, en cas contrari és un acte de fe. 

Pel que és registre mínimament n passos, però ¿Què passa amb aquest pas clau fusió on vaig combinar la meva meitat esquerra i dreta mitjà i va caminar per l'escenari? Quants passos és de fusionar? És n, però no ho vaig fer només fusionar el temps final. En cadascuna d'aquestes trucades niades, en cada d'aquestes fusions niats, jo encara ho van solucionar. Combinar aquests dos nois, a continuació, aquests dos nois, llavors aquests dos nois i així successivament. 

Així que em vaig donar la fusió de nou, i una altra. Quantes vegades? Així que cada vegada que divideix la llista a la meitat, em va fer una fusió. Dividiu la llista per la meitat, fer una fusió. Així que si dividint la llista es pot fer log n vegades, i la fusió en última instància porta a n passos, el que podria ser ara la part superior amb destinació en el funcionament temps del nostre algorisme? n log n. 

I de fet, això és el que que hem aconseguit aquí. Així que la sensació que es veu visualment quan aquestes tres coses corren costat a costat està n al quadrat contra n quadrat contra n log n. Què fonamentalment veurem, no només avui sinó en el futur, és molt, molt més ràpid. Un aplaudiment per a aquests nois, Vaig a recompensar amb boles d'estrès. Anem a aixecar la sessió aquí avui, i ens veiem dilluns.