[REPRODUCCIÓ DE MÚSICA] 

PROFESSOR: Molt bé. Això és CS50 i això és Al final de la tercera setmana. Així que estem aquí avui, no en Sanders Teatre, en lloc de Weidner Biblioteca. A l'interior dels quals és un estudi conegut com Hauser d'estudi, o millor dit Estudi H, o aniran que dir-- si et va agradar la broma, en realitat és de company, Mark, en línia, qui va suggerir tant a través de Twitter. Ara el bo de ser aquí en un estudi és que estic envoltat d'aquests de verd parets, una pantalla verda o chromakey, per així dir-ho, el que significa que CS50 de equip de producció, sense jo saber-ho en aquest moment, podria ser posar més em qualsevol part del món, per bé o per mal. 

Ara el que s'acosta, estableix problema 2 és a les seves mans per a aquesta setmana, però amb el problema d'establir de tres aquesta setmana que ve, seràs reptat amb l'anomenat joc de 15, un vell partit a favor que es pot recordar que rep com un nen que té un munt de nombres que es poden lliscar cap amunt, avall, esquerra i dreta, i hi ha una bretxa dins del trencaclosques, en què pot lliscar en realitat aquestes peces del trencaclosques. En última instància rep aquest trencaclosques en algun ordre semi aleatòria, i l'objectiu és ordenar-la, de dalt a baix, esquerra a dreta, d'un tot el camí a través de 15. 

Desafortunadament, la implementació tindràs a la mà serà el programari basat, no físicament. Vostè està en realitat va a haver d'escriure codi amb el qual un estudiant o usuari llauna jugar el joc dels 15. I de fet, en el hacker edició del joc de 15, vostè serà un desafiament per posar en pràctica, no només el joc d'aquesta vella escola joc, sinó més aviat la resolució d'això, l'aplicació de manera de déu, per així dir-ho, que de fet resol el trencaclosques per a l'ésser humà, posant a la seva pista, després de pista, a continuació, toqueu. Així que més que la setmana que ve. Però això és el que ens espera. 

Per ara recordar que a principis d'aquesta setmana hem tingut aquest melodrama, si es vol, de manera que el millor que estàvem fent la classificació sàvia era una fita superior de gran o de n al quadrat. En altres paraules, ordenament de bombolla, ordenació per selecció, ordenació per inserció, tots ells, mentre diferent en la seva aplicació, degenerat en un quadrat n corrent temps en el pitjor dels casos. I en general, suposem que el pitjor dels casos per a la classificació és un que les seves entrades són completament a l'inrevés. I, de fet, li va prendre uns quants passos per posar en pràctica cada un dels algoritmes. 

Ara al final de la classe revocatori, comparem ordenament de bombolla contra l'ordenació per selecció contra un altre que anomenem de combinació de classe en el moment, i jo proposo que està prenent avantatge d'una lliçó de la setmana zero, divideix i venceràs. I d'alguna manera aconseguir algun tipus de logarítmica temps de funcionament en última instància, en lloc d'alguna cosa això és purament quadràtica. I no és prou logarítmica, que és una mica més que això. Però si vostè recorda de la classe, era molt, molt més ràpid. Fem una ullada a on ho vam deixar. 

Bombolla tipus contra la selecció tipus de combinació front espècie. Ara estan tots corrent, en teoria, al mateix temps. La CPU està funcionant a la mateixa velocitat. Però es pot sentir el avorrit això va molt ràpidament per convertir-se, i la rapidesa, quan injectem una mica d'algoritmes setmana de zero, podem accelerar les coses. 

Així espècie marca es veu increïble. Com podem aprofitar que, per tal per ordenar els nombres més ràpidament. Bé anem a pensar en tornar a un ingredient que tenia de tornada en setmanes zero, el de buscant a algú en una guia telefònica, i recordar que el pseudo-codi que vam proposar, a través del qual podem trobar algú com Mike Smith, semblava una mica alguna cosa com això. 

Ara fa una ullada en particular, en la línia 7 i 8, i 10 i 11, que indueixen aquest bucle, en el qual vam mantenir que es remunta a la línia 3 de nou, i una altra, i una altra. Però resulta que podem veure aquest algoritme, aquí a pseudocodi, una mica més de manera integral. De fet, el que estic buscant pel que aquí a la pantalla, és un algoritme per a la recerca de Mike Smith, entre un conjunt de pàgines. I de fet, podríem simplificar aquest algoritme en aquestes línies 7 i 8, i 10 i 11 a només dir això, que he presentat aquí en groc. En altres paraules, si Mike Smith és anterior en el llibre, no necessitem especificar pas a pas ara com anar a buscar. No hem d'especificar per tornar a la línia 3, Per què no simplement en el seu lloc, per exemple, més en general, buscar Mike en el mitjana esquerra del llibre. 

Al revés, si Mike és en realitat més endavant en el llibre, ¿Per què no acabem de citar recerca cap de la cita Mike en la meitat dreta del llibre. En altres paraules, per què no ho fem només espècie de batea a nosaltres mateixos dient: buscar Mike en aquest subconjunt del llibre, i deixar que els nostres actuals algoritme que ens digui com buscar Mike en que la meitat esquerra del llibre. En altres paraules, la nostra algoritme funciona ja sigui una llibreta de telèfons d'aquest gruix, d'aquesta gruix, o qualsevol espessor que sigui. Així que el que puguem de manera recursiva definir aquest algorisme. En altres paraules, en el pantalla d'aquí, és un algoritme per a la recerca de Mike Smith entre les pàgines d'un llibre de telèfon. Així, en la línia 7 i 10, anem a a dir exactament això. I utilitzo aquest terme un moment Fa, i de fet, la recursió és la paraula de moda, per ara, i és aquest procés de fer alguna cosa cíclic d'alguna manera utilitzant el codi que ja té, i dir que és nou, i una altra, i una altra. Ara que va a ser important que d'alguna manera inferior fora, i no facis això infinitament llarg. Altrament, anem a tenen de fet un bucle infinit. Però anem a veure si podem demanar prestada aquesta idea d'un recursivitat, fer alguna cosa nova i una vegada i una altra, per resoldre el problema de classificació a través de combinació Ordena, tota la manera més eficient. 

Així que li dono combinar tipus. Anem a fer una ullada. Així que aquí és pseudocodi, amb que podríem aplicar la classificació, l'ús d'aquest algorisme anomenat fusió tipus. I és simplement això. A l'entrada de n elements, en altres paraules, si vostè és donada n elements i nombres i cartes o el que la entrada és, si et donen n elements, si n és menor que 2, simplement tornar. Oi? Perquè si n és menor que 2, que vol dir que la meva llista d'elements és qualsevol de mida 0 o 1, i en tots dos casos trivials, la llista ja està ordenat. Si no hi ha una llista, és ordenada. I si hi ha una llista de longitud 1, és òbviament ordenat. Així que l'algoritme només necessita realment fer alguna cosa interessant, si tenim dos o més elements donats a nosaltres. Així que donem una ullada a la màgia llavors. Else ordenar la meitat esquerra dels elements, a continuació, ordenar la meitat dreta dels elements, després fusionar les meitats ordenats. I el que és classe de ment flexió aquí, és que realment no em semblen que han dit res encara, oi? Tot el que he dit és, donada una llista de n elements, ordenar la meitat esquerra, llavors la meitat dreta, a continuació, fusionar les meitats ordenats, però on és l'ingredient secret real? On és l'algoritme? Doncs resulta que aquestes dues línies primer, ordenar l'esquerra de la meitat dels elements, i tipus adequat mitjà d'elements, són crides recursives, per així dir-ho. 

Després de tot, en aquest punt en el temps, he un algoritme amb el qual ordenar un munt d'elements? Sí. És just aquí. És aquí a la pantalla, i així que puc utilitzar aquest mateix conjunt de mesures per ordenar la meitat esquerra, com puc la meitat dreta. I, en efecte, de nou, una vegada i una altra. Així que d'alguna manera o altra, i que aviat veure això, la màgia de la combinació de tipus està incrustat en aquest mateix definitiva línia, la fusió de les meitats ordenades. I això sembla bastant intuïtiu. Vostè pren dues meitats, i tu, d'alguna manera, unir-los, i anem a veure això concretament en un moment. 

Però aquest és un algoritme complet. I anem a veure exactament per què. Bé suposem que ens donen aquests mateixos 08:00 elements aquí a la pantalla, un a través de vuit, però són per tal aparentment a l'atzar. I l'objectiu que ens ocupa és per ordenar aquests elements. Bé, com puc anar sobre Ho podeu, de nou, ordenament per barreja, segons aquest pseudocodi? I de nou, arrelar això en la seva ment, només per un moment. El primer cas és força trivial, si és menys de 2, simplement tornar, no hi ha feina per fer. Així que en realitat hi ha només tres mesures per mantenir molt en compte. Un cop més, i una altra vegada, estic voldrà tenir per ordenar la meitat esquerra, ordenar la meitat dreta, i després una vegada la seva dues meitats estan ordenats, Vull unir-los en una llista ordenada. Així que tingues-ho en compte. 

Així que aquí està la llista original. Anem a tractar això com una matriu, com vam començar a en la segona setmana, que és un bloc contigu de memòria. En aquest cas, que conté vuit números, esquena amb esquena amb esquena. I ara anem a aplicar fusió tipus. Així que primer vull ordenar la meitat esquerra d'aquesta llista, i deixar de, per tant, centrar-se en 4, 8, 6, i 2. 

Ara, com faig per ordenar una llista de grandària de 4? Bé he de considerar ara la classificació de l'esquerra de la meitat esquerra. Un cop més, anem a retrocedir per un moment. Si el pseudocodi és això, i em donen 8 elements, 8 és òbviament major que o igual a 2. Així que amb el primer cas no s'aplica. Així que per classificar 08:00 elements, jo primer ordenar la meitat esquerra d'elements, llavors puc ordenar la meitat dreta, després em fusiono les dues meitats ordenades, cadascuna de la mida de 4. D'ACORD. 

Però si el que m'has dit, ordenar la meitat esquerra, que ara és de mida 4, Com puc ordenar el medi queda? Bé, si tinc una d'entrada de quatre elements, Jo primer ordenar l'esquerra dos, i després tots dos a la dreta, i després unir-los. Així que de nou, es torna una mica d'una ment de flexió joc aquí, perquè, classe de, que recordar on vostè està en la història, però al final del dia, donat qualsevol nombre d'elements, que primer vol ordenar la mitjà esquerre, després la meitat dreta, després unir-los. Anem a començar a fer exactament això. Aquí hi ha l'entrada de vuit elements. Ara estem veient la meitat esquerra aquí. Com puc ordenar quatre elements? Bé, jo primer ordenar el medi esquerra. Ara, com puc ordenar el medi queda? Bé m'han donat dos elements. Així que anem a ordenar aquests dos elements. 2 és major o igual a 2, és clar. Així que el primer cas no s'aplica. 

Així que ara he de ordenar l'esquerra mitjà d'aquests dos elements. La meitat esquerra, per descomptat, és a 4. Llavors, com puc ordenar una llista d'un element? Ara bé, aquest cas base especial a la part alta, per així dir-ho, s'aplica. 1 és menor que 2, i el meu llista és precisament de mida 1. Així que em torno. Jo no faig res. I de fet, mira el que tinc fet, 4 ja està ordenat. Igual que ja estic parcialment reeixit aquí. 

Ara que sembla una mica estúpid a reclamar, però és cert. 4 és una llista de tamany 1. Ja està solucionat. Això és la meitat esquerra. Ara puc ordenar la meitat dreta. El meu entrada és un element, 8 De la mateixa manera, ja ordenats. Estúpid, també, però de nou, aquest principi bàsic va a permetre que construïm ara a la part superior d'aquest èxit. 4 ordenats, 8 s'ordena, ara ¿Quin va ser l'últim pas? Així que el tercer i últim pas, qualsevol temps estàs ordenar una llista, el record, era fusionar les dues meitats, l'esquerra i la dreta. Així que farem exactament això. El meu mitjana esquerra és, per descomptat, 4. El meu meitat dreta és 8. 

Així que anem a fer això. En primer lloc vaig a assignar una mica de memòria addicional, que vaig a represento aquí, com s'acaba d'una matriu secundària, això és prou gran per a això. Però es pot imaginar que s'estén aquest rectangle tota la longitud, si necessitem més tard. Com prenc 4 i 8, i es fusionen aquestes dues llistes de tamany 1 en conjunt? Aquí, també, bastant simple. 4 ve primer, després ve 8. Perquè si vull ordenar la mitjà esquerre, després la meitat dreta, i després fusionar aquestes dues meitats junts, en forma ordenada, 4 ve primer, després ve 8. 

Així que sembla que estem fent progressos, fins i tot encara que no he fet cap treball real. Però recorda on som en la història. Originalment fa vuit elements. Classifiquem la meitat esquerra, que és 4. Llavors ens ho van solucionar la meitat esquerra de la meitat esquerra, que era 2. I aquí anem. Hem acabat amb aquest pas. 

Així que si hem van solucionar el mitjana de 2 vam ser, ara nosaltres ha d'ordenar la meitat dreta de 2. Així que la meitat dreta de 2 és aquests dos valors aquí, 6 i 2. Així que anem a prendre ara una entrada de grandària 2, i ordenar la meitat esquerra, i després la meitat dreta, i després unir-los. Bé, com puc ordenar una llista de mida 1, que conté només el número 6? Jo ja he acabat. S'ordena aquesta llista de tamany 1. 

Com puc ordenar una altra llista de mida 1, l'anomenada mitjana dreta. Bé, també, ja està solucionat. El número 2 és l'únic. Així que ara tinc dues meitats, esquerra i bé, he de unir-los. Permetin-me dono una mica d'espai extra. I posar 2 en allà, a continuació, 6 de allà, d'aquesta manera ordenar la llista, esquerra i dreta, i la fusió junts, en última instància. Així que estic en una mica millor forma. No he acabat, perquè és evident 4, 8, 2, 6 no és l'ordenament final que vull. Però ara tinc dues llistes de mida 2, que haver-hi dos, respectivament, estat ordenats. Així que ara si es rebobina en la seva ment de ull, ¿on ens deixa això? Vaig començar amb vuit elements, llavors jo retallat cap avall a la meitat esquerra de 4, a continuació, la meitat esquerra de 2, i llavors la meitat dreta de 2, Vaig acabar, per tant, la classificació de l'esquerra mitjana de 2, i la meitat dreta de 2, ¿Quin és el tercer i últim pas aquí? He de fusionar dues llistes de mida 2. Així que seguirem endavant. I a la pantalla aquí, donar em una mica de memòria addicional, encara que tècnicament, noto que tinc té un munt d'espai en blanc sobre de la tapa allà. Si vull ser especialment espai eficient savi, Jo només podia començar a moure els elements endavant i enrere, amunt i avall. Però només per la claredat visual, Vaig a posar-ho baix, per mantenir les coses agradables i netes. 

Així que tinc dues llistes de mida 2. La primera llista té 4 i 8. La segona llista té 2 i 6. Anem a fusionar els junts en forma ordenada. 2, per descomptat, és el primer, després 4, després 6, llavors 8. I ara sembla que estem aconseguint en algun lloc interessant. Medi Ara he ordenada de la llista, i casualment, és tots els nombres parells, però això és, de fet, només una coincidència. I ara he ordenat l'esquerra mitjà, per la qual cosa és 2, 4, 6 i 8. Res està fora d'ordre. Que se sent com el progrés. 

Ara se sent com si hagués estat parlant sempre ara, així que el que queda per veure si això algoritme és, de fet, més eficient. Però anem a través super metòdicament. Un ordinador, per descomptat, ho faria així. Llavors, ¿on som? Comencem amb vuit elements. Em vaig classificar la meitat esquerra de 4. Em sembla que fer amb això. Així que ara el següent pas és ordenar la meitat dreta de 4. I aquesta part podem anar a través d'una mica més de ràpidament, encara que vostè és benvinguts a rebobinar o pausar, just pensar a través d'ell en el seu propi ritme, però el que tenim ara és una oportunitat per fer el mateix algoritme exacte de les quatre nombres diferents. 

Així que seguirem endavant, i se centren en la meitat dreta, el que estem aquí. La meitat esquerra d'aquest mig dret, i ara el meitat esquerra de l'esquerra la meitat d'aquesta meitat dreta, i com puc ordenar una llista de mida 1 que conté només el número 1? Ja està fet. Com puc fer el mateix per a una llista de tamany 1 que conté només 7? Ja està fet. El tercer pas d'aquest mitjà a continuació, és fusionar aquests dos elements en una nova llista de mida 2, 1 i 7. No semblen haver fet tot que molta feina interessant. Anem a veure què passa després. Acabo van solucionar la meitat esquerra de la meitat dreta de la meva entrada original. Ara anem a ordenar la dreta mitjà, que conté 5 i 3. Anem a tornar a veure a l'esquerra mitjà, ordenats, mig dret, ordenats, i fusionar els dos junts, en una mica d'espai addicional, 3 ve primer, després ve 5. I ara, hem classificat el mitjana esquerra de la meitat dreta del problema original, i la meitat dreta de la meitat dreta del problema original. Quina és la tercera i última etapa? Bé per fusionar aquestes dues meitats. Així que permetin-me a mi mateix una mica espai extra, però, de nou, podria ser l'ús d'aquest espai fins recanvi superior. Però nosaltres seguirem simple visualment. Permetin-me ara es fonen en 1, i a continuació, 3, 5 i, a continuació, i després 7. D'aquesta manera deixant-me ara amb la meitat dreta del problema original Això és perfectament ordenats. 

Llavors, què queda? Sento que segueixo dient que el mateixes coses una i altra vegada, però això és un reflex de la fet que estem utilitzant recursivitat. El procés d'usar una algoritme de nou, i de nou, en subconjunts més petits de el problema original. Així que ara tenim una esquerra ordenats mitjà del problema original. Tinc un mitjà ordenat dret del problema original. Quina és la tercera i última etapa? Oh, és la fusió. Així que anem a fer això. Anem a assignar alguns addicionals memòria, però el meu Déu, ens podria posar en qualsevol lloc ara. Tenim molt espai disponible per a nosaltres, però anem a mantenir les coses simples. En lloc d'anar cap enrere i endavant amb la nostra memòria original, anem fes-ho visualment per aquí baix, per acabar la fusió de la meitat esquerra i la meitat dreta. 

Així que mitjançant la fusió, què he de fer? Vull aprofitar els elements en ordre. Així que mirant a la meitat esquerra, Veig el primer número és 2. Miro a la meitat dreta, Veig el primer número és 1, així que òbviament que nombre Què vull arrencar, i posar primer a la meva llista final? Per descomptat, 1. Ara vull fer aquesta mateixa pregunta. A la meitat esquerra, tinc encara té el número 2. A la meitat dreta, Tinc el número 3. Quina he vull triar? Per descomptat, el número 2 I Ara notar els candidats són 4 a l'esquerra, 3 a la dreta. Anem, per descomptat, triar 3. Ara els candidats són 4 en l'esquerra, 5 a la dreta. Nosaltres, per descomptat, vam triar 4. 6 a l'esquerra, 5 a la dreta. Nosaltres, per descomptat, vam triar maig. 6 a l'esquerra, 7 a la dreta. Triem 6, i després triar 7, i després vam triar agost. Voila. 

Així que un gran nombre de paraules més tard, s'han classificat aquesta llista de vuit elements en una llista d'un a vuit, això està augmentant amb cada pas, però quant de temps ho va fer que ens porta a fer això. Bé, jo he deliberadament coses establertes il·lustrat aquí, així que podem tipus de veure o apreciar la divisió en la conquesta que està passant. 

De fet, si un mira cap enrere en el vetlla, He deixat totes aquestes línies de punts en marcadors de posició, vostè pot, classe de, vegi, en ordre invers, si vostè espècie de mirar cap enrere en la història ara, la meva llista original és, per descomptat, de grandària 8. I a continuació, prèviament, estava es tracta de dues llistes de mida 4, i després quatre llistes de mida 2, i després 8 llistes de tamany 1. 

Llavors, què fa això, classe de, recordar-? Bé, de fet, qualsevol de els algoritmes que hem mirat fins al moment en què dividir i dividir i dividir, seguir tenint les coses de nou, i Novament, els resultats en aquesta idea general. I així hi ha alguna cosa logarítmica passant aquí. I no és prou registre de n, però hi ha un component logarítmica al que acabem de fer. 

Ara anem a considerar la forma en que realment és. Així que ingressi de n, de nou va ser un gran temps de funcionament, quan vam fer una cosa semblant recerca binària, ja que ara anomenem, l'estratègia de divideix i venceràs a través del qual ens trobem Mike Smith. Ara tècnicament. Això és log base 2 de n, fins i tot encara que en la majoria de les classes de matemàtiques, 10 és en general la base que vostè assumeix. Però científics de la computació gairebé sempre pensar i parlar en termes de base 2, així que en general, només diem registre de n, en lloc de logaritme en base 2 de n, però són exactament una i la mateix en el món de l'ordinador ciència, i com un a part, hi ha un factor constant diferència entre els dos, pel que és discutible de totes maneres, per raons més formals. 

Però per ara, el que ens importa sobre és aquest exemple. Així que anem a no prova amb l'exemple, però al menys usar un exemple dels nombres a la mà com una comprovació de validesa, si es vol. Així que amb anterioritat la fórmula era la base de registre 2 de n, però el que és n en aquest cas. Vaig tenir n nombres originals, o agost del nombre original específicament. Ara que ha estat una mica temps, però estic bastant Segur que log base 2 del valor 8 és 3, i de fet, el que és bo d'això és que el 3 és exactament el nombre de vegades que es pot dividir una llista de longitud 8 una altra vegada, i una altra, i una altra, fins que un es queda amb llistes de tot just el tamany 1. Oi? 8 va a 4, passa a 2, passa a 1, i això és reflecteix exactament això imatge que teníem fa un moment. Així que una mica de seny comprovar d'on el logaritme està realment involucrat. 

Així que ara, què més està involucrat aquí? n. Així notar que cada temps jo ens vam dividir la llista, encara que en ordre invers a la història aquí, encara estava fent n coses. Aquest pas fusió requeria que Toco cadascun dels nombres, per tal de lliscar en la seva ubicació adequada. Així que, encara que l'altura d'aquesta diagrama és de la mida del registre n de n o 3, específicament, en altres paraules, Vaig fer tres divisions aquí. Quant treball vaig fer horitzontalment al llarg d'aquest gràfic cada vegada? 

Bé, ho vaig fer n passos de treballar, perquè si tinc té quatre elements i quatre elements, i necessito unir-los. He d'anar a través de aquests quatre i aquests quatre, en última instància, per a fondre de nou en vuit elements. Si per contra tinc vuit dits per aquí, que no ho faig, i de vuit fingers-- sorry-- Si tinc té quatre dits per aquí, que faré, quatre dits aquí, que jo faig, llavors això és la mateixa exemple, com abans, si ho faig té vuit dits encara que en total, que puc classe de, fer ,. Exactament el que puc fer aquí, llavors jo sap fusionar totes aquestes llistes de tamany 1 junts. Però sens dubte he de mirar en cada element d'exactament una vegada. Per tant l'altura d'aquest procés és log n, l'amplada d'aquest procés, per així dir-ho, és N, així que el que sembla tenir, en última instància, és una durada de mida n vegades log n. 

En altres paraules, hem dividit la llista, registre n vegades, però cada vegada que ho vam fer, vam tenir tocar cada un dels elements per tal de fusionar- tots junts, que va ser n pas, de manera que tenim n vegades log n, o com un científic de la computació diria, asimptòticament, que seria la paraula gran per descriure la part superior amb destinació en un temps de funcionament, ens estem quedant en una gran o de log n temps, per així dir-ho. 

Ara bé, això és important, perquè recorden el que van ser els temps de funcionament amb la bombolla de gènere, i la selecció ordenar i ordenació per inserció, i fins i tot alguns altres que existeixen, n al quadrat era on estàvem. I vostè pot, una mica, veure això aquí. Si n al quadrat és òbviament n vegades n, però aquí tenim n vegades log n, i ja sabem per setmana zero, que log n, la logarítmica, és millor que alguna cosa lineal. Després de tot, recordar la imatge amb el vermell i el groc i les línies verdes que Drew, el línia logarítmica verda era molt menor. I per tant, molt millor i més ràpid que les línies grogues i vermelles rectes, n vegades log n és, de fet, millor de n vegades n o n al quadrat. 

Així que sembla que tenim identificat una combinació d'algorisme espècie que s'executa en molt temps més ràpid, i de fet, per això, a principis d'aquesta setmana, quan vam veure que contesa entre bombolles Ordena, ordenació per selecció, i fusionar Ordena, ordenament per barreja molt, molt bestiar. I, en efecte, que ni tan sols esperar d'ordenament de bombolla i ordenació per selecció acabar. 

Ara anem a prendre un altre pas en aquest, des d'una mica més punt de vista formal, per si cas, això ressona millor que l'alt nivell de discussió. Així que aquí està l'algoritme de nou. Preguntem-nos, el que el temps d'execució és d'aquest algoritmes diferents passos? Anem a dividir a la primera cas i el segon cas. L'IF i ELSE En el cas SI, Si N és menor que 2, simplement tornar. Se sent com a constant de temps. És, alguna cosa així, com dos passos, Si n és inferior a 2, i després tornar. Però com hem dit el dilluns constant de temps, o de l'o 1, poden ser dos passos, tres passos, fins i tot 1.000 passos. El que importa és que és un nombre constant de passos. Així que el groc ressaltat pseudocodi aquí s'executa en, ho anem a trucar, constant de temps. Així que de manera més formal, i anem A-- aquest serà el grau en què ens formalitzar aquest dret ara-- T de n, el temps d'execució d'un problema que pren n tants com a entrada, és igual a gran o d'un, Si N és inferior a 2. Així que és condicionat a això. Així que per ser clars, si n és menor que 2, tenim una llista molt curta, a continuació, el temps d'execució, T de n, on n és 1 o 0, en aquest cas molt específic, és només serà la constant de temps. Es va a prendre 1 pas, dos passos, el que sigui. És un nombre fix de passos. 

Així que la part sucosa segurament ha d'estar en l'altre cas en el pseudocodi. El cas ELSE. Ordenar meitat esquerra dels elements, tipus adequat mitjà d'elements, combinar meitats ordenades. Quant de temps dura cada un d'aquests passos prendre? Bé, si el funcionament temps per ordenar n elements És a dir, anem a cridar molt genèricament, T de n, a continuació, la classificació de l'esquerra mitjà dels elements és a dir, una mena de, com dir, T de n dividit per 2, i de la mateixa manera la classificació de la meitat dreta d'elements és, alguna cosa així, com dient: T de n divideix 2, i després la fusió de les meitats ordenats. Bé, si tinc alguna nombre d'elements aquí, com quatre, i un nombre d'elements que aquí, igual que 4, i he de combinar cada un d'aquests quatre a, i cadascuna d'aquestes quatre a, un després de l'altra, de manera que en última instància, tinc 8 elements. Se sent com que és gran o de n passos? Si tinc n dits i cadascuna de ells ha de ser fusionat al seu lloc, això és com un altre n passos. 

Així que de fet formulaically, podem expressar això, encara que una mica espantadís al principi vista, però és una cosa que captura exactament aquesta lògica. El temps d'execució, T de n, si n és més gran que o igual a 2. En aquest cas, el cas ELSE, és T de n dividit per 2, a més de T de N dividit per 2, més gran o de n, alguns nombre de passos lineal, potser exactament n, potser 2 cops n, però és més o menys, l'ordre de n. Així que, també, és la forma en què pot expressar aquesta formulaically. Ara no vas a saber això a menys que ha gravat en la seva ment, o busqueu-les al llom d'un llibre de text, que podria tenir una mica full de trucs al final, però això és, de fet, va ens donen una gran o de n log n, perquè la recurrència que que estem veient aquí a la pantalla, si realment ho va fer a terme, amb un nombre infinit d'exemples, o ho vas fer formulaically, ho faria veure que això, perquè aquesta fórmula si mateix és recursiu amb t de n per alguna cosa a la dreta, i t de n per l'esquerra, això pot en realitat ser expressada, en última instància, tan gran de costat n log n. Si no està convençut, això és bé per ara, només pren en la fe, que és, de fet, el que condueix a la recurrència, però això és només una mica més d'un enfocament matemàtic a la recerca en el moment d'execució de la fusió espècie basat en el seu pseudocodi sol. 

Ara anem a fer una mica d'un respir de tot això, i fer una ullada a una certa exsenador, qui podria semblar una mica familiar, qui es va asseure amb Eric de Google Schmidt, fa algun temps, per a una entrevista a l'escenari, davant d'un munt de les persones, parlar en última instància sobre un tema, que és bastant ja familiar. Anem a fer una ullada. 

Eric Schmidt: Ara el senador, vostè està aquí a Google, i m'agrada pensar en el presidència com una entrevista de treball. Ara és difícil aconseguir una feina com a president. PRESIDENT OBAMA: Correcte. Eric Schmidt: I tu ets va a fer [inaudible] ara. També és difícil d'aconseguir una feina a Google. PRESIDENT OBAMA: Correcte. 

Eric Schmidt: Tenim preguntes, i li demanem a les nostres preguntes dels candidats, i aquest és de Larry Schwimmer. 

PRESIDENT OBAMA: OK. 

Eric Schmidt: Què? Vostès pensen que estic fent broma? És just aquí. Quina és la forma més eficient de ordenar un milió 32 bits sencers? 

PRESIDENT OBAMA: Bueno-- Eric Schmidt: En ocasions, potser em sento, maybe-- PRESIDENT OBAMA: No, no, no, no, no, jo think-- Eric Schmidt: Això no és it-- PRESIDENT OBAMA: I pensar, crec que la bombolla tipus seria el camí equivocat. Eric Schmidt: Anem. Qui li va dir això? D'ACORD. Jo no vaig fer la informàtica en-- 

PRESIDENT OBAMA: Tenim van donar els nostres espies en aquest país. PROFESSOR: Molt bé. Anem a deixar darrere de nosaltres ara món teòric d'algoritmes en l'anàlisi asimptòtic dels mateixos, i tornar a alguns temes des de la setmana zero i un, i inici per eliminar algunes rodes d'entrenament, si es vol. Així que vostè realment entén en última instància, a partir de zero, el que és passant per sota de la campana, quan escriure, compilar i executar programes. Recordem, en particular, que es tractava de el primer programa en C miràvem, un programa canònica, simple de tipus, en termes relatius, on, imprimeix, Hello World. I recordo que li vaig dir, el procés que el codi font passa a través de és exactament això. Vostè pren el seu codi font, passa a través d'un compilador, com Clang, i fora ve codi objecte, que podria tenir aquest aspecte, zeros i uns que la CPU de l'ordinador, el centre unitat de processament o el cervell, en última instància, entén. 

Resulta que aquesta és una mica d'una simplificació excessiva, que ara estem en un posició de separar per entendre el que realment ha estat passant per sota de la campana cada vegada que s'executa Clang, o més generalment, cada vegada que realitzi un programa, utilitzant Marca i CF 50 IDE. En particular, coses per l'estil aquest es genera primer, la primera vegada que compila el programa. En altres paraules, quan es portar al seu codi font i compilar-lo, ¿què és primer sent enviada per Clang és alguna cosa conegut com codi assemblador. I, de fet, es veu exactament com aquest. 

Vaig córrer una ordre al línia d'ordres anterior. Hola.c Clang capitals tauler s, i això crea un arxiu per a mi anomenats hello.s, dins dels quals eren exactament aquests continguts, i una mica més dalt i una mica més avall, però m'he posat la més sucosa informació aquí, a la pantalla. I si et fixes bé, veuràs almenys un parell de paraules clau familiars. Tenim principal a la part superior. Hem printf al centre. I també tenim hola món barra invertida n entre cometes baix baix. 

I tota la resta aquí és molt instruccions de baix nivell que la CPU de l'ordinador entén. Instruccions de CPU que es mouen de memòria voltant, que les cadenes de càrrega de la memòria, i en última instància, d'impressió coses a la pantalla. Ara el que passa encara que després es genera el codi de muntatge? En última instància, ho fa, de fet, Encara generar codi objecte. Però els passos que tenen realment estat succeint sota de la campana mirar una mica de la mateixa família. El codi font es converteix en codi assemblador, que després es converteix en codi objecte, i les paraules clau aquí és que, en compilar el codi font, terme ve codi assemblador, i després al col·locar el seu codi en assemblador, terme ve codi objecte. 

Ara Clang és super sofisticat, com molts dels compiladors, i ho fa de tots aquests passos junts, i no necessàriament sortida de qualsevol intermedi arxius que encara es poden veure. Simplement compila les coses, que és el terme general que descriu tot aquest procés. Però si realment vols per ser concret, no hi ha molt més que fer allà també. 

Però també considerarem ara que fins i tot aquest programa super simple, hello.c, anomenat una funció. Va demanar printf. Però jo no vaig escriure printf, de fet, que ve amb c, per així dir-ho. És un recordatori que la funció és declarada en io.h estàndard, que és un arxiu de capçalera, que és un tema que va en realitat submergir-se en més profunditat en poc temps. No obstant això, un arxiu de capçalera és normalment acompanyats per un arxiu de codi, arxiu de codi font, per la qual de la mateixa manera que hi ha io.h. estàndard 

Fa algun temps, algú, o d'algú, també va escriure un arxiu anomenat io.c norma, en que les definicions reals, o implementacions de printf, i raïms d'altres funcions, són en realitat escrit. Així que tenint en compte que, si tenim en compte que té aquí a l'esquerra, hello.c, que quan compilat, ens dóna hello.s, fins i tot si Clang no molesta estalvi en un lloc podem veure-ho, i que el codi de muntatge obté acoblament en hello.o, que és, de fet, el nom per defecte donat cada vegada que es compila la font codificar en codi objecte, però no són a punt per executar-però, perquè un altre pas ha de succeir, i té vingut succeint en els últims setmana, potser sense saber-ho tu. 

Específicament en algun lloc en CS50 IDE, i això, també, serà una mica d'un simplificació excessiva per un moment, hi ha, o va ser en un altre temps, un arxiu anomenat io.c estàndard, que algú compilat en io.s estàndard o l'equivalent, que algú acobla llavors en io.o estàndard, o resulta en una lleugerament diferent arxiu format que pot tenir un diferent extensió d'arxiu per complet, però en teoria i conceptualment, exactament aquests passos van haver de passar en alguna forma. És a dir, que ara quan estic escrivint un programa, hello.c, que amb prou feines diu, hola món, i estic fent servir el codi d'una altra persona com printf, que era una vegada un temps, en un arxiu anomenat io.c estàndard, llavors d'alguna manera he de portar al meu codi objecte, les meves zeros i uns, i l'objecte d'aquesta persona codi, o zeros i uns, i d'alguna manera enllaçar junts en un arxiu final, anomenada hola, que té tots els zeros i els de la meva funció principal, i tots els zeros i els de printf. 

I, en efecte, que el passat procés és trucada, la vinculació del seu codi objecte. La sortida dels quals és un arxiu executable. Així que per ser justos, al final del dia, res ha canviat des de la setmana un, quan primer va començar compilar programes. De fet, tot això ha estat passant per sota de la caputxa, però ara estem en una posició on puguem realment esmicolar aquests diversos passos. I, de fet, al final del dia, encara estem esquerra amb zeros i uns, que és en realitat un gran segue ara a una altra capacitat de C, que nosaltres no hem hagut d'aprofitar més probable fins a la data, coneguda com a operadors bit a bit. En altres paraules, fins al moment, en qualsevol moment ens hem tractat amb dades en C o variables en C, hem tingut coses com caràcters i carrosses i complements i anhela i dobles i similars, però tots aquests són almenys vuit bits. Hem això mai ser capaços de manipular bits individuals, tot i que un bit individual, ens saben, pot representar un 0 i un 1. Ara resulta que en C, pot obtenir accés als bits individuals, si coneix la sintaxi, amb la qual per arribar-hi. 

Així que anem a fer una ullada a operadors bit a bit. Així fotografiats aquí hi ha alguns símbols que hem, classe de, classe de, vist abans. Veig una i comercial, vertical bar, i alguns altres també, i recordar que signe ampersand és una cosa que hem vist abans. L'operador lògic AND, on has dos d'ells junts, o la lògica OR operador, en la qual tenir dues barres verticals. Operadors bit a bit, que anem a veure operar en bits de forma individual, només ha d'utilitzar un sol signe, un barra vertical única, el símbol d'intercalació que ve a continuació, la petita accent i, després a l'esquerra suport deixar suport o claudàtor dret escaire dret. Cadascun d'ells tenen diferents significats. 

De fet, anem a fer una ullada. Anem a la vella escola d'avui, i l'ús una pantalla tàctil d'antany, conegut com un tauler blanc. I aquest tauler blanc ens va a permetre per expressar alguns símbols bastant simples, o més aviat algunes fórmules bastant simples, que podem llavors en última instància, palanquejament, per tal accedir a la persona bits dins d'un programa C. En altres paraules, farem això. Primer parlem de moment en signe, que és l'operador AND. En altres paraules, això és un operador que permet que jo tingui una variable de l'esquerra Típicament, i una variable de la dreta, o un valor individual, que si I junts, em dóna un resultat final. Llavors, què puc dir? Si en un programa, que té una variable que emmagatzema un d'aquests valors, o anem a mantenir simple, i just escrigui zeros i uns de forma individual, així és com funciona l'operador de signe. 0 0 I comercial serà igual a 0. Ara per què és això? 

És molt similar a Expressions booleanes, que hem discutit fins ara. Si vostè pensa que després de tot, el 0 és falsa, 0 és falsa, falsa i fals és, com hem discutit lògicament, també falsa. Així obtenim 0 aquí també. Si vostè pren 0 ampersand 1, així que, també, serà 0, perquè per això l'expressió de l'esquerra per ser veritat o 1, que hauria de ser veritable i cert. Però aquí tenim falsa i veritable, o 0 i 1. Ara, de nou, si tenim 1 ampersand 0, això també serà 0, i si tenim 1 ampersand 1, finalment tenim un 1 bit. En altres paraules, no estem fent alguna cosa interessant amb aquest operador de moment, aquest operador signe. És l'operador AND. Però aquests són els ingredients a través del qual podem fer coses interessants, com aviat veurem. 

Ara anem a veure només l'única barra vertical per aquí a la dreta. Si tinc un bit 0 i jo O amb el bit a bit Operador OR, un altre bit 0, això va a donar-me 0. Si prenc un bit 0 i O amb un bit 1, a continuació, vaig a aconseguir 1. I, de fet, només per claredat, em va deixar anar cap enrere, de manera que els meus barres verticals no es confonen amb 1 de. Permetin-me reescriure tots mi 1 és una mica més clarament, de manera que ens veiem la propera, si han gener 1 o 0, això serà un 1, i si tinc un 1 O 1, que, també, va ser un 1. Així es pot veure, lògicament, que l'O operador es comporta de manera molt diferent. Això em dóna 0 O 0 0 em dóna, però qualsevol altra combinació em dóna 1. Sempre que tinc un 1 al fórmula, el resultat serà 1. 

En contrast amb la I operador, el signe, només si tinc dos d'1 en la equació, puc realment aconseguir 1 gen. Ara hi ha alguns altres operadors també. Un d'ells és una mica més complicat. Així que permetin-me anar endavant i esborrar això per alliberar espai. I anem a fer una ullada a la símbol d'intercalació, per un moment. Això és típicament un caràcter que es pugui escriure en la seva celebració de teclat Maj i llavors un dels números sobre de la dels EUA teclat. 

Així que aquesta és l'exclusiva Operador OR, OR exclusiva. Així que acabem de veure l'operador OR. Aquest és l'exclusiu operador OR. Què és realment la diferència? Bé anem a veure a la fórmula, i utilitzar això com a ingredients en última instància. 0 0 XOR. Vaig a dir és sempre 0. Aquesta és la definició de XOR. 0 XOR 1 serà 1. 1 XOR 0 serà 1, i 1 XOR 1 serà? ¿Mal? O no? No ho sé. 0. Ara, què està passant aquí? Bé pensar en el nom d'aquest operador. Exclusiva O, de manera que el nom, tipus de, suggereix, la resposta només serà un 1 si les entrades són exclusius, exclusivament diferent. Així que aquí les entrades són els mateix, de manera que la sortida és 0. Aquí les entrades són la mateix, de manera que la sortida és 0. Aquí hi ha les sortides són diferents, són exclusius, de manera que la sortida es 1. Així que és molt similar a la I, és molt similar, o millor dit, que és molt similar a la O, però només de manera exclusiva. Aquest ja no és un 1, perquè tenim dos d'1, i no exclusivament, només un d'ells. Tot bé. ¿I els altres? Bé, la titlla, per la seva banda, és realment agradable i senzilla, gràcies a Déu. I aquest és un unari operador, el que significa que s'aplica a una sola entrada, 1 operant, per així dir-ho. No a una esquerra i una dreta. En altres paraules, si vostè pren titlla de 0, la resposta serà l'oposada. I si es pren titlla d'1, el resposta allà serà l'oposat. Així que l'operador accent és una forma de negar una mica, o voltejar una mica de 0 a 1, o de 1 a 0. 

I això ens deixa finalment amb només dos operadors finals, L'anomenat desviació a l'esquerra, i la l'anomenat operador de desplaçament a la dreta. Fem una ullada a com els treballs. L'operador de desplaçament a l'esquerra, per escrit amb dues esquadres per l'estil, funciona com segueix. Si la meva entrada, o el meu operant, a l'esquerra operador de desplaçament és, senzillament, un 1. I llavors dic que l'ordinador desviació a l'esquerra que 1, diuen 07:00 llocs, el resultat és com si prendre aquest 1, i moure- 07:00 llocs més a la esquerra, i per defecte, anem a suposar que l'espai a la dreta va ser emplenat amb zeros. En altres paraules, 1 esquerra torn juliol va que em donés que 1, seguit d'1, 2, 3, 4, 5, 6, 7 zeros. Així que en certa manera, li permet prendre un nombre petit com 1, i clarament que sigui molt molt, molt més gran d'aquesta manera, però en realitat estem anant a veure enfocaments més intel·ligents perquè en el seu lloc, així, 

Tot bé. Això és tot per a la setmana tres. Ens veiem la propera vegada. Aquest va ser CS50. 

[REPRODUCCIÓ DE MÚSICA] 

ALTAVEU 1: Estava en el berenar bar menjant un gelat amb xocolata calenta. Ho tenia tot a la cara. Porta que la xocolata com una barba ALTAVEU 2: Què estàs fent? ALTAVEU 3: Hmmm? Què? 

ALTAVEU 2: Acabes de doble immersió? Fa doble submergit el xip. ALTAVEU 3: Perdoni. ALTAVEU 2: Vostè submergit el xip, que va prendre un mos, i submergit de nou. ALTAVEU 3: ALTAVEU 2: Així que això és com posar a la seva dreta la boca sencera en el dip. La propera vegada que vostè pren un xip, simplement submergir una vegada, i acabar amb ella. 

ALTAVEU 3: Saps què, Dan? Vostè submergeix la forma en què desitja que recórrer. Vaig a mullar la manera que jo vull que recórrer.