>> [Reproducció de música]
DAVID Malan: Molt bé.
Bé, benvinguts de nou.
Així que aquesta és la Setmana 4, el començament dels mateixos, ja.
I et recordo que la setmana passada, hem posat codificar a un costat per una mica
i vam començar a parlar una mica més d'alt nivell, sobre coses com
recerca i ordenació, que encara les idees són una mica simples,
representant d'una classe de problemes vostè començarà a resoldre tot
a mesura que comences a pensar en definitiva projectes i solucions interessants que
podria tenir a problemes del món real.
Ara mena de bombolla va ser un dels més senzills aquest tipus d'algorismes, i
treballat per tenir aquests petits nombres en una llista o en un tipus gamma de
bombolla del seu camí al cim, i el grans nombres de moure el seu camí a
al final de la llista.
>> I recordem que vam poder visualitzar mena de bombolla una mica
alguna cosa com això.
Així que permetin-me anar endavant i feu clic a Inicia.
He preseleccionat mena de bombolla.
I si vostè recorda que el blau més alt línies representen nombres grans, petites
línies blaves representen els nombres petits, com passem per això una i altra vegada i
de nou, la comparació de dos bars al costat de cadascun una altra de color vermell, que canviarem la
més gran i la més petita, si que estan fora d'ordre.
>> Així que això va a seguir i seguir i seguir encès, i vostè veurà que la major
elements estan fent el seu camí a la dreta, i els elements més petits són
fer el seu camí a l'esquerra.
Però comencem a quantificar l'eficiència, la
qualitat d'aquest algorisme.
I vam dir que en el pitjor cas, aquest algorisme es
més o menys la quantitat de passos?
>> Per tant n quadrat.
¿I què era n?
>> AUDIÈNCIA: Nombre d'elements.
>> DAVID Malan: Així va ser la n nombre d'elements.
Així que anem a fer això amb freqüència.
Cada vegada que volem parlar sobre la mida d'un problema o la mida d'un
d'entrada, o la quantitat de temps que triga per produir una sortida, només haurem de
generalitzat el l'entrada és com n.
Així que de nou en la setmana 0, el nombre de pàgines a la guia telefònica era n.
El nombre d'estudiants A l'habitació hi havia n.
Així que aquí, també, estem seguint aquest patró.
>> Ara n quadrat no és particularment ràpid, pel que tractem de fer millor.
I així vam veure un parell de altres algoritmes, entre els quals
eren ordenació per selecció.
Així que va ser una mena de selecció una mica diferent.
Gairebé era més simple, m'atreveixo a dir, pel que vaig començar al principi de la
Llista dels nostres voluntaris i jo de nou i una i altra vegada va ser a través de
la llista, arrencar-se el més petit element alhora i el va deixar o
ella al principi de la llista.
>> Però això, també, un cop que vam començar a pensar a través de les matemàtiques i més gran
imatge, va pensar en quantes vegades Jo anava d'anada i tornada i tornada
endavant i cap enrere, vam dir en el pitjor dels casos, ordenació per selecció, també, va ser que?
n al quadrat.
Ara, en el món real, podria en realitat ser marginalment més ràpid.
Perquè de nou, jo no he de seguir fer marxa enrere una vegada que havia ordenat la
elements més petits.
Però si pensem en gran n, i si una espècie de fer la matemàtica com
Ho vaig fer en el tauler, amb el núm quadrat una mica menys, tota la resta
a més de la núm quadrat, un cop n es posa molt gran, no
Realment importa tant.
Així com els informàtics, que tipus de fer els ulls grossos als més petits
factors i se centren només en el factor d' una expressió que es va a fer
la diferència més gran.
>> Bé, finalment, busquem en l'ordenació per inserció.
I aquesta va ser similar en esperit, però en lloc d'anar a través de manera iterativa i
seleccionar l'element més petit d'un en un temps, lloc va prendre la mà que em
va ser tractat, i vaig decidir, tot bé, és el teu lloc.
Després vaig passar a la següent element i va decidir que ell o
pertanyia aquí.
I després em vaig mudar i segueix.
I potser, en el camí, canviar aquests nois per tal de
fer espai per a ells.
Així que va ser una mena de reversió mentals d'ordenació per selecció que
anomenada ordenació per inserció.
>> Així que aquests temes que es produeixi en el món real.
Fa tot just uns anys, quan un determinat senador va ser candidat a la presidència,
Eric Schmidt, en el moment en el director general d' Google, en realitat va tenir l'oportunitat
per entrevistar-lo.
I pensem que seria bona idea compartir aquesta YouTube tallar per a vostè aquí, si poguéssim pujar
el volum.
>> [REPRODUIR VIDEO]
>> -Ara, el senador, ets aquí a Google, i m'agrada pensar en la presidència
com una entrevista de treball.
>> [El]
>> -Ara que és difícil d'aconseguir un treball com a president.
I vostè va a través d' els rigors ara.
També és difícil aconseguir una feina a Google.
Tenim preguntes i li demanem les nostres preguntes dels candidats.
I aquesta és de Larry Schwimmer.
>> [El]
-Vostès pensen que estic fent broma?
Sou aquí mateix.
Quina és la forma més eficient de ordenar un milió d'enters de pacotilla?
>> [El]
>> -Bé, uh -
>> -Ho sento.
Potser hauria -
>> -No, no, no, no, no.
>> -Això no és un -
D'acord.
>> -Crec que l'ordenament de bombolla seria ser el camí equivocat.
>> [El]
>> [Vítores i aplaudiments]
>> -Anem, que li va dir això?
D'acord.
>> [FI REPRODUCCIÓ DE VÍDEO]
>> DAVID Malan: Així que aquí ho tenen.
Així que vam començar a quantificar aquestes corrent vegades, per dir-ho, amb una mica
anomenat notació asimptòtica, que és només es refereix a la nostra espècie de gir
els ulls grossos als factors més petits i només mirar el temps d'execució,
el rendiment d'aquests algoritmes, que n es fa molt gran amb el temps.
I així hem introduït gran O. i Big O representava alguna cosa que pensem
d'com un límit superior.
I, de fet, Barry, podem baixar que el micròfon una mica?
>> Pensem en això és un límit superior.
Així gran O de n mitjans quadrat que en el pitjor dels casos, una mena
ordenació per selecció prendria n passos quadrat.
O alguna cosa així com l'ordenació per inserció faria n passos quadrat.
Ara per a alguna cosa com la inserció espècie, que va ser el pitjor dels casos?
Donat un vector que, quina és la pitjor possible escenari que podria trobar
fet front amb?
>> És totalment al revés, no?
Perquè si és totalment al revés, vostè ha de fer un munt de treball.
Perquè si vostè és completament al revés, vostè va a trobar el
element més important aquí, tot i que pertany allà.
Així que vas a dir, d'acord, en aquest moment en el temps, que és d'aquí,
així que el deixa sol.
>> Llavors t'adones, oh, maleïda sigui, he de moure aquest element una mica més petit que
l'esquerra de vostè.
Llavors he de fer-ho de nou i una i altra vegada.
I si caminava d'anada i tornada, que que classe de sensació l'exercici de
que l'algorisme, perquè constantment estic arrossegant a tots els altres en la
matriu per fer espai per a això.
Així que aquest és el pitjor dels casos.
>> Per contra -
i això va ser un cliffhanger última vegada -
vam dir que l'ordenació per inserció era un omega de què?
Quin és el millor dels casos funcionament moment de l'ordenació per inserció?
Així que en realitat n.
Aquest va ser l'espai en blanc que deixem al tauler de l'última vegada.
>> I és l'omega de n perquè ¿per què?
Doncs bé, en el millor dels casos, el que és ordenació per inserció és entregat?
Bé, una llista que molt ordenada Ja, un mínim de treball que fer.
Però el que és bo d'ordenació per inserció és que, ja que comença aquí i
decideix, oh, ets l' un, pertanyen aquí.
Oh, quina bona fortuna.
>> Vostè és el número dos.
També pertanyo a aquest lloc.
Número tres, millor encara, pertanys aquí.
Tan aviat com s'arriba al final de la pseudocodi llista, per la inserció d'una espècie
que vam entrar per verbalment última vegada, ja està fet.
Però ordenació per selecció, per contra, vaig seguir fent què?
>> Va seguir el seu camí a través de la llista una i altra vegada i una altra.
A causa de que la idea clau que només havia una vegada que has mirat tot el camí a la
final de la llista pot estar segur que l'element seleccionat es
de fet, l'element actualment més petit.
Així que aquests models diferents finals mentals cedint alguna cosa al món real molt
diferències per a nosaltres, així com els diferències teòriques asimptòtiques.
>> Així que per resumir, llavors, gran O de n quadrat, hem vist uns quants,
algoritmes fins ara.
Big O de n?
Què és un algoritme que podria dir que és gran O de n?
En el pitjor dels casos, es necessita una sèrie lineal de passos.
>> Acceptar, cerca lineal.
I en el pitjor dels casos, on és el element que està buscant quan
l'aplicació de cerca lineal?
>> Acceptar, en el pitjor dels casos, que ni tan sols existeix.
O en el segon pitjor dels casos, és tot el camí a l'extrem, que és
de més o menys una diferència d'un sol pas.
Així que al final del dia, podem dir que és lineal.
Big O de n seria recerca lineal, causa que en el pitjor dels casos, la
element ni tan sols existeix o és fins arribar al final.
>> Bé, gran O de registre de n.
No parlem en detall sobre això, però hem vist això abans.
El que s'executa en l'anomenada logarítmica temps, en el pitjor dels casos?
>> Sí, cerca de manera binari.
I recerca binària en el pitjor dels casos podria tenir l'element en algun lloc
el mitjà, o en algun lloc en cas de fallida.
Però només es troba un cop dividir la llista en dues, en
un mitjà, en un medi, en un mitjà.
I voilà, aquí està.
O, de nou, pitjor dels casos, que ni tan sols existeix.
Però vostè no sap que no hi és fins que arribi a aquest tipus de passat
baix majoria dels elements de reduir a la meitat i reduir a la meitat, i reduir a la meitat.
>> Big O d'1.
Així que vam poder gran O de 2, O gran de 3.
Cada vegada que vols és simplement un nombre constant, que només una mena de just simplificar
que, com a gran O d'1.
Encara que si realista, pren 2 o fins i tot 100 passos, si és un
nombre constant de passos, ens limitem a dir gran O d'1.
Què és un algoritme que és en gran O d'1?
>> AUDIÈNCIA: Trobar la longitud d'una variable.
>> DAVID Malan: Trobar el longitud d'una variable?
>> AUDIÈNCIA: No, la longitud si ja està solucionat.
>> DAVID Malan: Good.
Acceptar, de manera que trobar la longitud d'una mica si la longitud d'alguna cosa que, igual
una matriu, s'emmagatzema en una variable.
Com que només pot llegir la variable, o imprimir la variable o
només en general accedir a aquesta variable.
I voila, que porta temps constant.
>> Per contra, pensar de nou a l'altura.
Penseu en la primera setmana de C, cridar simplement printf i impressió
alguna cosa a la pantalla és, sens dubte constant de temps, ja que només es necessita
un nombre de cicles de CPU per mostrar que el text a la pantalla.
O esperar - o sí?
Com si no podríem modelar el exercici de printf?
Algú voldria estar en desacord, que potser no és el temps realment constant?
En quin sentit podria printf s'està executant temps, en realitat la impressió d'una cadena en
la pantalla, sigui alguna cosa que no sigui constant.
>> AUDIÈNCIA: [inaudible].
>> DAVID Malan: Si.
Així que depèn de la nostra perspectiva.
Si realment pensem en l'entrada printf com la cadena, i
per tant, es mesura la grandària d'aquest d'entrada per la seva longitud - així que anem a trucar
que la longitud n, així -
sens dubte, printf és propi Big O de n perquè va a portar n passos
per imprimir cadascun dels n personatges, molt probablement.
Almenys en la mesura que assumim que potser es tracta d'utilitzar un bucle for
sota de la caputxa.
>> Però hauríem de mirar aquest codi per entendre-ho millor.
I, de fet, un cop que vostès comencin a l'anàlisi dels seus propis algoritmes, vostè
literalment fer precisament això.
Una espècie de globus ocular seu codi i pensar Quant a - bé, jo tinc aquest bucle
aquí o que tenen una combinació de bucles niats aquí, que farà les coses n n vegades,
i es pot ordenar de la raó a la seva manera a través del codi, encara que és
pseudocodi i no el codi real.
>> Què passa amb l'omega de n al quadrat?
El que era un algoritme que en el millor cas, encara va trigar n passos quadrat?
Sí?
>> AUDIÈNCIA: [inaudible].
>> DAVID Malan: Així ordenació per selecció.
Perquè en aquest problema realment reduït al fet que una vegada més, no ho sé
He trobat el corrent més petita fins He comprovat tots els elements maleït.
Així omega de, per exemple, n, Acaba d'arribar amb un.
L'ordenació per inserció.
Si la llista passa a ser ordenats Ja, en el millor dels casos només tenim
per fer un passi a través d'ell, moment en què estem segurs.
I a continuació, que es podria dir ser lineal, sens dubte.
>> Què passa amb l'omega d'1?
Quin és, en el millor dels casos, pot trigar un nombre constant de passos?
Recerca de Llavors lineal, si vostè acaba de tenir sort i l'element que està buscant
és just al principi de la llista, si això és on vostè està començant el seu
lineals de recorregut de la llista.
>> I aquest és el cas d'un nombre de coses.
Per exemple, fins i tot binari recerca és l'omega d'1.
Perquè el que si vostè aconsegueix realment maleït sort i just-DAB al centre de
la matriu és el nombre que està buscant?
Així que vostè pot tenir sort allà, també.
>> Aquest, finalment, l'omega de n log n.
Llavors n log n, no ho vam fer realment parlar encara, però -
>> AUDIÈNCIA: Combinar tipus?
>> DAVID Malan: Merge espècie.
Aquest va ser el drama de suspens de l'última vegada, on ens vam proposar, i mostrem
visualment, que hi ha algorismes.
I combinar espècie de només un d'aquests algoritme que és fonamentalment més ràpid
que alguns d'aquests altres tipus.
De fet, combinar curta és no només en el millor dels casos n log n, en el pitjor dels casos
cas n log n.
I quan vostè té aquesta coincidència de omega i grans O és el mateix?
De fet, podem descriure com el que és anomenada theta, encara que és un
poc menys comú.
Però això només significa que els dos límits, en aquest cas, són els mateixos.
>> Així fusionar espècie, el que fa realment es redueixen a per nosaltres?
Bé, recordar la motivació.
Déjame treure a una altra animació que no ens fixem en l'última vegada.
Aquest, mateixa idea, però que és una mica més gran.
I jo seguiré endavant i assenyalar primer - tenim l'ordenació per inserció en
dalt a l'esquerra, a continuació, ordenació per selecció, mena de bombolla, un parell d'altres tipus -
petxina i ràpida - que no hem parlat aproximadament, i el munt i combinar estil.
>> Així, almenys, intentar enfocar els seus ulls en els tres primers de l'esquerra i després
fusionar espècie quan faig clic la fletxa verda.
Però vaig a deixar que tots ells funcionen, només per li donarà una idea de la diversitat de
algoritmes que hi ha al món.
Vaig a deixar que aquest termini per tan sols uns segons.
I si et enfoques els teus ulls - triar una algorisme, se centren en ell només per un
segon - vostè començarà a veure el patró que està aplicació.
>> Combinar classe, avís, es fa.
Pila de classificació, ordenació ràpida, closca -
pel que sembla que presentem els tres pitjors algoritmes de setmana passat.
Però això és bo que estem aquí avui per mira fusió espècie, que és un
els més fàcils és a la vista, fins i tot encara que probablement es doblarà la teva ment
només una mica.
Aquí podem veure fins a quin punt ordenació per selecció és una merda.
>> Però d'altra banda, és molt fàcil d'implementar.
I potser per P 3 setembre, que és una de les algoritmes que va triar per implementar
per a l'edició estàndard.
Perfectament bé, tota la raó.
>> Però una vegada més, a mesura que n es fa gran, si triar aplicar un algoritme més ràpid
com fusionar espècie, les probabilitats són de major i entrades més grans, el seu codi és
va a córrer més ràpid.
El seu lloc web funcionarà millor.
Els usuaris van a ser més feliç.
I així hi ha aquests efectes de la realitat, donant
nosaltres una mica més profund pensament.
>> Així que donem una ullada al que fusionar tipus és realment tot.
El millor és que fusionar tipus és només això.
Això és, un cop més, el que hem anomenat pseudocodi, ser pseudocodi
Sintaxi Anglès-like.
I la simplicitat és mena de fascinant.
>> Així que a l'entrada de n elements - de manera que Només vol dir, això és una matriu.
Té n coses en ella.
Això és tot el que estem dient no.
>> Si n és menor que 2, tornar.
Així que això és només el cas trivial.
Si n és menor que 2, llavors, evidentment, és 1 o 0, en aquest cas la cosa
ja està ordenat o inexistent, així que tornar.
No hi ha res a fer.
Així que això és un cas senzill d'arrencar.
>> Si no, tenim tres passos.
Ordenar la meitat esquerra dels elements, més o menys la meitat dreta dels elements,
i després combinar les meitats ordenades.
El que és interessant aquí és que Sóc una mena de batea, oi?
Hi ha una espècie de definició circular a aquest algorisme.
En quin sentit és l'algoritme de circular definició?
>> AUDIÈNCIA: [inaudible].
>> DAVID Malan: Sí, el meu algorisme de classificació, dues de les seves mesures són "una espècie
alguna cosa ". Així que ens porta a la pregunta, bé, què vaig a utilitzar
per ordenar la meitat esquerra i la meitat dreta?
I la bellesa aquí és que encara que de nou, aquesta és la ment-flexió
part potencialment, pot utilitzar la mateixa algorisme per ordenar la meitat esquerra.
>> Però espereu un minut.
Quan et diuen que ordenar la mitjà esquerre, quins són els dos
mesures seran el següent?
El arreglarem la meitat esquerra de la la meitat esquerra i la dreta
la meitat de la meitat esquerra.
Maleïda sigui, com puc ordenar els dos meitats o quarts, ara?
>> Però això està bé.
Tenim un algorisme de classificació aquí.
I encara que és possible que preocupar-se en primer es tracta d'una espècie d'infinit
bucle, és un cicle que mai és va a acabar - que va a
acabar d'una vegada el que passa?
Un cop n és menor que 2.
Que amb el temps passarà, perquè si segueixes reduir a la meitat i
reduir a la meitat en reduir a la meitat aquestes meitats, segurament finalment va a acabar
amb només 1 o 0 elements.
En aquest moment, aquest algorisme diu que ja està.
>> Així que la veritable màgia d'aquesta algorisme sembla estar en
el pas final, la fusió.
Aquesta simple idea només la fusió de dues coses, això és el que està passant en última instància,
que ens permeti ordenar una matriu de, diguem, vuit elements.
Així que tinc vuit més boles de la tensió de fins a Aquí, vuit fulles de paper, i una
Google Glass -
que he de complir.
>> [El]
>> DAVID Malan: Si poguéssim prendre 08:00 voluntaris, i veurem si podem
jugar a això, així que.
Wow, OK.
La informàtica és cada vegada divertit.
Està bé.
Així que hi ha de vosaltres 3, major part allà.
Quatre a la part posterior.
¿I que farem que tres a la fila?
I quatre a la part davantera.
Així que 8, anem amunt.
>> [El]
>> DAVID Malan: Estic realment no estic segur del que és.
Són les boles de la tensió?
Els llums d'escriptori?
El material?
L'Internet?
>> D'acord.
Així que anem cap amunt.
Qui vol -
segueixen arribant.
Anem a veure.
I això et posa en el lloc -
vostè està en una ubicació.
Uh-oh, espera un minut.
1, 2, 3, 4, 5, 6, 7 - oh, bo.
Bé, estem bé.
Molt bé, així que cada un té un seient, però no en el vidre de Google.
Déjame fer cua aquests.
Com et dius?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle?
Molt bé, s'arriba a semblar- el geek, si això està bé.
Bé, jo també, suposo, només per un moment.
D'acord, espera.
Hem estat tractant d'arribar a un cas d'ús de Google Glass, i
va pensar que seria divertit per fer això quan la gent està a l'escenari.
Anem a gravar el món des de la seva perspectiva.
Està bé.
No és probablement el que pretén Google.
Bé, si no t'importa portar això per als pròxims incòmodes minuts,
això seria meravellós.
>> Molt bé, així que tenim aquí una gran varietat de elements, i que de matriu, com per la
trossos de paper en aquestes persones " mans, està actualment classificat.
>> MICHELLE: Oh, això és molt estrany.
>> DAVID Malan: És més o menys a l'atzar.
I en un moment, tractarem implementar fusionar espècie junts
i veure a on idea clau és.
I el truc aquí és una espècie de combinació cosa que encara no hem assumit.
En realitat necessitem una mica de espai addicional.
Llavors, què va a ser especialment interessant d'això és que aquests
nois van a moure una mica poc, perquè jo vaig a assumir que
hi ha un conjunt addicional d'espai, dir, just darrere d'ells.
>> Així que si estan darrere de la seva cadira, que és la matriu secundària.
Si estan asseguts aquí, això és la matriu primària.
Però aquest és un recurs que tenim no aprofitat fins ara amb la bombolla
espècie, amb la selecció de gènere, amb l'ordenació per inserció.
Recordem la setmana passada, tothom tipus de baralla en el seu lloc.
Ells no fan servir la memòria addicional.
Vam habitació per a persones amb moure a la gent al voltant.
>> Així que aquesta és una idea clau, també.
Hi ha un trade-off, en general, en ciències de la computació, dels recursos.
Per accelerar una mica com el temps, vas a
haver de pagar un preu.
I un d'aquests preus és molt sovint l'espai, la quantitat de memòria o disc
espai de disc que utilitzeu.
O bé, francament, la quantitat de temps del programador.
Quant de temps li pren, l'ésser humà, per realment posar en pràctica una mica més
complicat algorisme.
Però per ara, la compensació és el temps i l'espai.
>> Així que si vostès poguessin acaba de celebrar el números perquè puguem veure que ets
de fet a joc 4, 2, 6, 1, 3, 7, 8.
Excel · lent.
Així que vaig a tractar d'orquestrar coses, si vostès poden simplement
segueix-me aquí.
>> Així que em vaig a posar en pràctica, en primer lloc, la primer pas de la pseudocodi, que és
a l'entrada de n elements, si n és menys de 2, i després tornar.
Òbviament, això no s'apliquen, pel que seguim endavant.
Així ordenar la meitat esquerra dels elements.
Així que això significa que em vaig a centrar la meva atenció per un moment sobre aquestes
quatre nois aquí.
D'acord, què he de fer al costat?
>> AUDIÈNCIA: Ordenar la meitat esquerra.
>> DAVID Malan: Així que ara he de ordenar la meitat esquerra d'aquests nois.
Perquè de nou, suposem que vostè la objectiu és ordenar la meitat esquerra.
Com fer això?
Només has de seguir les instruccions, fins i tot encara que estem fent de nou.
Així ordenar la meitat esquerra.
Ara estic classificar aquests dos nois.
Què ve ara?
>> AUDIÈNCIA: Ordenar la meitat esquerra.
>> DAVID Malan: Ordenar la meitat esquerra.
Així que ara aquests, aquest seient aquí, és una llista de grandària 1.
¿I quin és el teu nom?
>> PRINCESA MARGARITA: Princess Daisy.
>> DAVID Malan: Princess Daisy és aquí.
I pel que ja està ordenat, perquè la llista és de grandària 1.
Què és el pròxim que fer?
Acceptar, tornarà, perquè aquesta llista és de grandària 1, que és menor que 2.
Llavors, quin és el següent pas?
I ara has de tipus de fer marxa enrere en la seva ment.
>> Ordenar la meitat dreta, que és -
Quin és el teu nom?
>> CONFRONTA: Linda.
>> DAVID Malan: Linda.
I què fem ara que tenim una llista de mida d'1?
>> AUDIÈNCIA: Return.
>> DAVID Malan: Cura.
Tornem primer, i ara la tercera pas - i si em mena de representar per
que abasta els dos seients ara, ara haver d'incorporar aquests dos elements.
Així que ara, per desgràcia, els elements estan fora de servei.
Però aquí és on el procés de fusió comença a ser convincent.
>> Així que si vostès poguessin posar-se dempeus per només un moment, vaig a necessitar, en un
Actualment, amb el pas darrere de la cadira.
I si Linda, perquè és 2 inferior a 4, per què no fer
véns per primera vegada?
Queda't aquí.
Així Linda, véns primer.
>> Ara, en realitat, si és només un conjunt que només podia moure en temps real
des d'aquesta cadira a aquest lloc.
Així que imaginin que va tenir una constant nombre de passos 1.
I ara -
però hem de posar en el primer lloc aquí.
>> I ara, si pogués entrar en raó, així, anem a
ser en lloc de dos.
I malgrat això se sent com si fos prendre un temps, el que és bo que ara és
que la meitat esquerra de la meitat esquerra està ordenada.
Llavors, quin era el següent pas, si ara retrocedir encara més en la història?
>> AUDIÈNCIA: Meitat dreta.
>> DAVID Malan: Ordenar la meitat dreta.
Així que vostès han de fer això, també.
Així que si vostè pot posar-se dret per un moment?
I quin és el teu nom?
>> JESS: Jess.
>> DAVID Malan: Jess.
OK, així que Jess és ara l'esquerra la meitat de la meitat dreta.
I el que és una llista de grandària 1.
Ella, òbviament, ordenada.
I el teu nom?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle òbviament una llista de grandària 1.
Ja està solucionat.
Així que ara succeeix la màgia, el procés de fusió.
Llavors, qui vindrà primer?
Òbviament Michelle.
Així que si vostè pot venir a la tornada.
L'espai que tenim disponible per a ella ara és just darrere d'aquesta cadira aquí.
I ara, si pogués tornar, així, ara tenim, per ser clars, dos
meitats, cadascuna de mida 2 -
i simplement per l'amor de la representació, si podria fer una mica d'un espai -
una esquerra mig aquí, un mitjà aquí.
>> Rebobine més en la història.
Quin és el pas següent?
>> AUDIÈNCIA: Combina.
>> DAVID Malan: Així que ara hem de combinar.
Així que bé, així que ara, gràcies a Déu, ens simplement alliberat quatre cadires.
Per això hem utilitzat el doble de memòria, però podem donar flip-tirar-entre
les dues matrius.
Llavors, quin és el nombre de venir primer?
Així que Michelle, òbviament.
Així que veuen al seu voltant i prendre seu seient aquí.
I a continuació, el número 2 és òbviament següent, per la que vénen aquí.
Número 4, número 6.
I de nou, tot i que hi ha una poc de caminar involucrats,
Realment, aquests podrien ocórrer instantàniament, movent un -
Bé, ben jugat.
>> [El]
>> DAVID Malan: I ara estem en molt bona forma.
La meitat esquerra de la totalitat d'entrada ja ha estat solucionat.
Bé, pel que aquests nois tenien l'avantatge de la meva -
Com s'acaben totes les noies a la a l'esquerra i tots els nois de la dreta?
>> OK, així que nois tornen ara.
Així que no vaig a caminar a través d' aquests passos.
Anem a veure si podem tornar a aplicar la mateixa pseudocodi.
Si vols seguir endavant i posar-se dempeus, i vostès, et vaig a donar el micròfon.
A veure si no es pot reproduir el que que acabem de fer aquí a la
altre extrem de la llista.
Qui ha de parlar en primer lloc, basat en l'algoritme?
Així que expliqui el que està fent abans de realitzar qualsevol moviment del peu.
>> ALTAVEU 1: D'acord, ja Jo sóc la meitat esquerra de la
mitjà esquerre, torno.
Cert?
>> DAVID Malan: Good.
>> ALTAVEU 1: I llavors -
>> DAVID Malan: Qui fa el micro passi a la següent?
>> ALTAVEU 1: nombre següent.
>> ALTAVEU 2: Així que estic a la meitat dreta de la meitat esquerra de la
mitjà esquerre, i torni.
>> DAVID Malan: Good.
Tornarà.
¿I ara què és el que segueix per a vostès?
>> ALTAVEU 2: Volem veure qui és més petit.
>> DAVID Malan: Exactament.
Volem combinar.
L'espai que utilitzarem per combinar que en, encara que són
òbviament ordenat ja, anem seguir el mateix algorisme.
Llavors, qui va en primera volta?
Així que 3, i després 7.
I ara el micròfon es a aquests nois, d'acord?
>> ALTAVEU 3: Així que sóc la meitat dreta de la la meitat esquerra, i el meu n és menor que
1, així que només vaig a passar -
>> DAVID Malan: Good.
>> ALTAVEU 4: Jo sóc la meitat dreta de la la meitat dreta de la part dreta, i estic
També una persona, així que estic tornarà.
Així que ara ens fusionem.
>> ALTAVEU 3: Llavors tornem.
>> DAVID Malan: Així que anar a la part posterior.
5 Així va primer, després 8.
I ara públic, que és el un pas que hem de retrocedir ara
una còpia en les nostres ments?
>> AUDIÈNCIA: Combina.
>> DAVID Malan: La fusió de la meitat esquerra i dreta meitat de la meitat esquerra de l'original.
Així que ara -
i només per deixar-ho clar, fer una mica d'espai
entre vosaltres dos.
Així que ara que són les dues llistes, esquerra i dreta.
Llavors, com ara fusionem nois a la primera fila de seients de nou?
>> 3 va primer.
5 Per això, òbviament.
A continuació, 7, 8 i ara.
Bé, i ara que som?
>> AUDIÈNCIA: No realitzat.
>> DAVID Malan: No realitzat, perquè Òbviament, hi ha un pas que queda.
Però, de nou, la raó per la que estic fent servir aquesta l'argot com "rebobinar en la seva ment,"
és perquè això és realment el que està succeint.
Anem a través de tots aquests passos, però som una mena de pausa per a una
Actualment, el busseig profund al algoritme, fent una pausa per un moment,
busseig més profund en l'algorisme, i Ara tenim a una mena de retrocés en la nostra
ment i desfer totes aquestes capes que hem espècie de posada en espera.
>> Així que ara tenim dues llistes de mida 4.
Si vostès poguessin posar-se dempeus un cop més i fer una mica d'espai per
deixar clar que es tracta de l'esquerra la meitat de l'original, la
la meitat dreta de l'original.
Qui és el primer número que hagi de tirar a la part posterior?
Michelle, és clar.
>> Per això, vam posar Michelle aquí.
I qui té el número 2?
Número 2 ve a la part posterior també.
Número 3?
Excel · lent.
Número 4, número 5, número 6, número 7, i el número 8.
>> Bé, així que em vaig sentir com un munt de passos, segur.
Però ara anem a veure si no podem confirmar espècie de intuïtivament que aquest
algorisme fonamentalment, en particular pel que n es fa molt gran, com hem vist
amb les animacions, és fonamentalment més ràpid.
Així que jo pretenc que aquest algorisme, en el pitjor cas i fins i tot en el millor dels casos,
és un gran O de n log n vegades.
És a dir, que hi ha algun aspecte d'aquest algorisme que pren n passos, però
hi ha un altre aspecte en algun lloc aquesta iteració, que bucle, que
porta registre de n passos.
Podem posar el nostre dit en el que els dos nombres es refereixen?
Bé, on -
¿A on va el micròfon?
>> ALTAVEU 1: La sessió núm ser nosaltres trencar en dos -
dividir per dos, essencialment.
>> DAVID Malan: Exactament.
Cada vegada que veiem en qualsevol algoritme així ara, no hi ha hagut aquest patró de
dividir, dividir, dividir.
I es redueix típicament a alguna cosa que és
logarítmica, log base 2.
Però el que realment podria ser qualsevol cosa, però entrar base 2.
>> Ara, què passa amb el núm?
Puc veure que tipus de què dividim nois - es divideix, es divideixen,
que divideix, es divideix.
D'on ve el final de la?
>> Així que és la fusió.
A causa a pensar-hi.
En combinar vuit persones a conjunt, pel que la meitat d'ells són un conjunt de quatre
i l'altra meitat són una altra conjunt de quatre, com anar
de fer la fusió?
Bé, vostès van fer que bastant intuïtiva.
>> Però si per contra el vaig fer una mica més metòdicament, hauria assenyalat a
la persona més a l'esquerra primer amb l'esquerra part, va assenyalar a la persona més a l'esquerra
d'aquest mitjà amb la mà dreta, i només posteriorment va caminar a través de la
llista, assenyalant l'element més petit cada vegada, movent el dit una i
més quan sigui necessari en la llista.
Però el que és clau sobre aquesta fusió procés és que estic comparant aquestes parelles
dels elements.
A partir de la meitat dreta i des de l'esquerra, mitjà, estic fent marxa enrere ni una sola vegada.
>> Així la pròpia fusió està prenent no més de n passos.
I quantes vegades he de fer que la fusió?
Bé, no més de n, i només va veure que amb la fusió final.
I pel que si vostè fa alguna cosa que té log n passos n vegades, o viceversa,
que ens va de vegades n log n donar.
>> ¿I per què és això millor?
Bé, si ja sabem que log n és millor que n - a la dreta?
Vam veure en la recerca binària, l'agenda exemple, log n era definitivament
millor que lineal.
Així que significa n vegades registre n és definitivament millor que n vegades una altra
n, AKA n al quadrat.
I això és el que en última instància sentim.
>> Així que gran aplaudiment, si vam poder, per a aquests nois.
>> [Aplaudiments]
>> DAVID Malan: I els seus regals de comiat - vostè pot mantenir els números,
si vol.
I el teu regal de comiat, com sempre.
Ah, i li enviarem les imatges, Michelle.
Gràcies.
Està bé.
Podrà gaudir d'una pilota antiestrès.
>> I m'ho dius a mi tiri cap amunt, mentrestant, nostre amic Rob Bowden per oferir
alguna cosa diferent perspectiva sobre això, ja que es pot pensar en aquests
passos que ocorren en un cert diferent manera.
De fet, la posada a punt per al que Rob tracta d' per mostrar suposa que hem
ha fet fins a la divisió del gran llista en vuit llistes petites,
cada un tamany 1.
>> Així que estem canviant el pseudocodi 01:00 poc acaba d'ordenar d'arribar a la
idea central de com la fusió d'obres.
Però el temps d'execució del està a punt de fer és encara
serà la mateixa.
I de nou, la posada a punt aquí és que és començat amb vuit llistes de grandària 1.
Així que t'has perdut la part en la qual està realment es fa el registre núm, log n, log n
divisòria de l'entrada.
>> [REPRODUIR VIDEO]
>> -Això és tot pel pas un.
En el segon pas, en diverses ocasions barreja parells de llistes.
>> DAVID Malan: Hm.
Només àudio ve fora del meu ordinador.
Anem a intentar novament.
>> -Només arbitràriament triar què - Ara tenim quatre llistes.
Aprèn abans.
>> DAVID Malan: Això és.
>> -La fusió de 108 i 15, ens trobem amb la llista de 15, 108.
La fusió de 50 i 4, que acabar amb 4, 50.
La fusió de 8 i 42, que acabar amb 8, 42.
I la fusió de 23 i 16, que acabar amb 16, 23.
>> Ara totes les nostres llistes són de mida 2.
Tingueu en compte que cada un dels quatre llistes desplegables s'ordenen.
Així que podem començar a fusionar parells de llistes de nou.
La fusió de 15 i 108 i 4 i 50, que primer prendre la 4, la 15, llavors
el 50, llavors el 108.
La fusió de 8, 42 i 16, 23, primer agafem el 8, a continuació, la 16, a continuació, la 23,
a continuació, la 42.
>> Així que ara tenim només dues llistes de mida 4, cadascun dels quals està ordenada.
Així que ara ens unim aquestes dues llistes.
En primer lloc, prenem el 4, després es pren la 8, i després prenem el 15, i després 16, després
23, a continuació 42, a continuació 50, a continuació, 108.
>> [FI REPRODUCCIÓ DE VÍDEO]
>> DAVID Malan: Novament, avís, mai tocat un got donat més d'una vegada
després d'avançar més enllà d'ella.
Així que mai es repeteix.
Així que sempre s'està movent cap a un costat, i aquí és on tenim el nostre n.
>> Per què no em deixa pujo una animació que hem vist abans, però aquest cop
centrar-se només en una mena de combinació.
Déjame anar per davant i zoom en això aquí.
Primer deixeu-me triar una entrada a l'atzar, magnificar això, i vostè pot ordenar de veure
el que prenem per fet, abans, fusionar espècie està fent.
>> Així que adonar-se que vostè aconsegueix aquestes meitats o aquests quarts oa vuitens d'aquests el
problema que, de sobte, començar a prendre bona forma.
I, finalment, que es veu en el final que bam,
tot es van fusionar.
>> Així que aquests són només tres diferents realitza en la mateixa idea.
Però la idea clau, igual que divideix i vèncer en la primera classe,
va ser que vam decidir dividir d'alguna manera el problema en alguna cosa gran, en
una mica espècie d'idèntic esperit, però més petit i més petits i més petits
i més petits.
>> Ara una altra divertida manera de classificar de pensar d'aquests, tot i que no és
va a donar el mateix intuïtiva comprensió, és
la següent animació.
Així que aquest és un vídeo que algú armar l'associada diferent
sons amb les diverses operacions de ordenació per inserció, per fusió d'ordenació i
per un parell dels altres.
Així que en un moment, em vaig a pegar Play.
Es tracta d'un minut de durada.
I tot i que encara es pot veure la patrons passant, aquest cop es pot
També escoltar com aquests algorismes són realitzar de manera diferent i amb
una mica diferents patrons.
>> Aquesta és l'ordenació per inserció.
>> [TONS QUE JUGUEN]
>> DAVID Malan: Novament està tractant per inserir cada element
a on ha d'estar.
Es tracta d'una mena de bombolla.
>> [TONS QUE JUGUEN]
>> DAVID Malan: I es pot ordenar de sensació el relativament poca feina que està fent
en cada pas.
Això és el que sona com avorriment.
>> [TONS QUE JUGUEN]
>> DAVID Malan: Es tracta d'una espècie de selecció, on seleccionem l'element que volem per
passant una i altra vegada i una altra i posar-lo al principi.
>> [TONS QUE JUGUEN]
>> DAVID Malan: Es tracta de fusionar espècie, que vostè realment pot començar a sentir.
>> [TONS QUE JUGUEN]
>> [El]
>> DAVID Malan: Una mica anomenat GNOME espècie, que no hem mirat.
>> [TONS QUE JUGUEN]
>> DAVID Malan: Així que anem a veure, ara, distret mentre esperem és el
música, si puc ficar una mica mica de matemàtiques aquí.
Així que hi ha una quarta forma que podem pensar en el que significa això
funcions per ser més ràpid que els que hem vist abans.
I si vindràs al llarg de un fons de les matemàtiques, que
realment saben potser ja que pot bufetejar un terme en aquesta tècnica -
a saber, la recursió, una funció que crida alguna manera en si.
>> I un cop més, recordar que tipus de mescla pseudocodi era recursiu, en el sentit
que un dels passos de merge sort va ser cridar a una espècie -
que és, en si.
Però gràcies a Déu, perquè ens mantenien trucar a ordenar o combinar estil,
específicament, en una més petita i més petita i la llista més petita, al final
tocat fons, gràcies al que anomenarem un cas base, el cas no modificable que
va dir que si la llista és petita, menys de 2 en aquest cas, torna immediatament.
Si no tinguéssim aquest cas especial, el algoritme mai tocaria fons,
i vostè realment entrar en un bucle infinit veritablement sempre.
>> Però suposem que volem posar ara alguns números sobre això, de nou, usant n
com la mida de l'entrada.
I jo volia preguntar, quin és el temps total involucrat en
corrent merge tipus?
O en termes més generals, quin és el cost de la mateixa en el temps?
>> Bé, és bastant fàcil de mesurar això.
Si n és menor que 2, el temps involucrat en la classificació de n elements,
on n és 2, és 0.
A causa que acabem de tornar.
No hi ha feina per fer.
Ara podria dir-se que, potser és un pas o dos mesures per esbrinar la quantitat de
funciona, però és prou a prop de 0 que Jo només vaig a dir que no hi ha feina
necessari si la llista és tan petit ser poc interessant.
>> Però aquest cas és interessant.
El cas recurrent va ser la branca de el pseudocodi que va dir una altra cosa, més o menys
la meitat esquerra, ordenar el dret mitjà, unir les dues meitats.
Ara, per què aquesta expressió representa aquesta despesa?
Bé, T de n només significa la temps per ordenar n elements.
I després a la part dreta de la signe igual allà, la T de n divideix
pel 2 es refereix al cost del que?
Classificació de la meitat esquerra.
L'altre T de n dividit per 2 és presumiblement referint-se al cost de
ordenar la meitat dreta.
>> I llavors el més n?
És la fusió.
Perquè si vostè té dues llistes, una de grandària n més de 2 i una altra de grandària n
més de 2, ha de tocar l'essència cadascun d'aquests elements, igual que Rob
tocat cadascuna de les copes, i només com hem assenyalat en cada un dels
voluntaris a l'escenari.
Per tant n és la despesa de fusió.
>> Ara, per desgràcia, aquesta fórmula és també en si recursiva.
Així que si va fer la pregunta, si n és, per exemple, 16, si hi ha 16 persones a l'escenari
o 16 tasses al vídeo, el nombre total de passos es necessiten per ordenar
amb mescla tipus?
En realitat no és una resposta òbvia, perquè ara vostè ha d'ordenar d'
recursivament respondre a aquesta fórmula.
>> Però això està bé, perquè permetin-me proposar que fem el següent.
El temps necessari per ordenar 16 persones o 16 tasses serà representat
generalment com T de 16.
Però això és igual, d'acord amb la nostra fórmula anterior, 2 vegades la quantitat
de temps que es necessita per ordenar 8 tasses de més 16.
I de nou, més 16 és el moment d'unir, i el doble de T de 8 és el
temps per ordenar a meitat esquerra i la meitat dreta.
>> Però de nou, això no és suficient.
Hem de bussejar més profundament.
Això vol dir que hem de respondre a la pregunta, quin és T de 8?
Bé T de 8 és a 2 temps T de 4 i de 8.
Bé, què hi ha de la T 4?
T de 4 està a 2 hores de la T2 més 4.
Bé, quin és T de 2?
T 2 està a només 2 vegades T d'1 més 2.
>> I de nou, estem com aconseguir atrapat en aquest cicle.
Però està a punt d'arribar a aquest anomenat cas base.
Perquè el que és T 1, ens diem?
0.
Així que ara, finalment, es pot treballar cap enrere.
>> Si T 1 és 0, ara puc pujar una alinear aquest tipus aquí, i no puc
endoll 0 per T d'1.
Així que això significa que és igual a 2 vegades zero, també coneguda com 0, més 2.
I tota aquesta expressió és 2.
>> Ara bé, si em prenc el T de 2, la resposta és 2, connecteu-lo a la línia mitjana, T
de 4, això em dóna 2 cops 2 més 4, pel que 8.
Doncs, jo connecto 8 a l'anterior line, que em dóna 2 cops 8, 16.
I si després seguim que amb l' 24, l'addició de 16, per fi tenim un
valor de 64.
>> Ara que en i per si mateixa espècie de parla res a la notació n, la
O gran, els àcids grassos omega que hem estat parlant.
Però resulta que el 64 és de fet 16, la mida de l'entrada,
log base 2 de 16.
I si això és una mica estrany, simplement Penseu de nou, i es tornarà
per al temps.
Si això és log base 2, és com 2 elevat a la que li dóna 16?
Oh, això és 4, pel que és 16 vegades 4.
>> I de nou, no és un gran problema si aquest és una espècie de vague record ara.
Però per ara, assumir la fe que el 16 log 16 és 64.
I així, de fet, amb aquest simple seny comprovar, hem confirmat -
però no demostrat formalment -
que el temps de funcionament de la fusió espècie és de fet n log n.
>> Així que no està malament.
És definitivament millor que el algorismes que hem vist fins ara, i
és perquè hem aprofitat, un, una tècnica anomenada recursió.
Però més interessant que això, que idea de dividir i conquerir.
Un cop més, realment setmanes 0 coses que fins i tot ara es repeteixi en un
manera més convincent.
>> Ara una mica d'exercici divertit, si vostè té mai ha fet això - i és probable que
No hi hauria, doncs una espècie de normalitat la gent no pensa fer-ho.
Però si vaig a google.com i si Vull aprendre alguna cosa sobre
recursivitat, Enter.
>> [El]
[Més rialles]
DAVID Malan: Bad broma estenent lentament.
[El]
DAVID Malan: Per si de cas, que hi és.
Jo no ho lletregi malament, i aquí està la broma.
Està bé.
Explicar a la gent costat de vostè si Però no ha fet clic al moment.
Però recursió, més en general, es refereix per al procés d'una funció de trucada
en si, o més en general, la divisió d'un problema en alguna cosa que pot ser
resolt poc a poc mitjançant la resolució d'idèntic problemes representatius.
>> Bé, anem a canviar els engranatges només per un moment.
Ens agradaria acabar amb certs melodrames, així que anem a començar a configurar
l'escenari, durant diversos minuts, en una idea molt simple -
el d'intercanvi de dos elements, no?
Tots aquests algorismes que hem estat parlant dels últims dos
conferències impliquen algun tipus d'intercanvi.
Avui en dia es va visualitzar per ells aconseguir dalt de les seves cadires i
caminant, però en el codi, ho faríem simplement prendre un element d'un array
i plop en un altre.
>> Llavors, com farem això?
Bé, deixa seguir endavant i escriure un programa ràpid aquí.
Vaig a seguir endavant i fer això com el següent.
Diguem que això -
Què volem cridar aquest?
>> En realitat, no.
Permetin-me rebobinat.
Jo no vull fer això melodrama encara.
Es espatllar la diversió.
Anem a fer-ho al seu lloc.
>> Suposem que vull escriure una mica programa i que ara abasta la
idea de recursivitat.
Jo com que tinc davant de mi mateix allà.
Vaig a fer el següent.
>> Primer, una ràpida inclouen de sèrie io.h, així com un include de cs50.h.
I després vaig a seguir endavant i declarar void main int
en la forma habitual.
Em vaig adonar que he mal anomenat l'arxiu, per la qual cosa permetin-me afegir una extensió c. aquí, així
que podem compilar correctament.
Inicieu aquesta funció.
>> I la funció que vull escriure, bastant simplement, és un que demana al
usuari un número i després s'afegeix tots els números entre els quals
nombre i, per exemple, 0.
Així que primer vaig a seguir endavant i declarar n int.
A continuació copio un codi que hem utilitzat durant algun temps.
Mentre que alguna cosa és cert.
Vaig a tornar a això en un moment.
>> Què vull fer?
Vull dir printf positiu sencer per favor.
I després vaig a dir n es fa arribar int.
Així que de nou, una mica de codi repetitiu que hem utilitzat abans.
I jo faré això mentre que n és menor que 1.
Així que això assegurarà que l'usuari em dóna un nombre enter positiu.
>> I ara vaig a fer el següent.
Vull sumar tots els números entre 1 i i n, o 0 i n,
equivalent, per obtenir la suma total.
Per tant el símbol sigma gran que es pot recordar.
Així que vaig a fer això per primera convocatòria una funció anomenada sigma,
passant a n, i després em vaig a printf dir, la resposta està aquí.
>> Així que en resum, ho entenc i int des de l'usuari.
Em asseguro que és positiu.
Declaro una trucada resposta variable tipus int i emmagatzemar en ella el retorn
valor de sigma, passant núm com a entrada.
I llavors em imprimeixo la resposta.
>> Desafortunadament, tot i que sona sigma com una cosa que podria estar en
l'arxiu math.h, la seva declaració, en realitat no és.
Així que això està bé.
Puc aplicar això a mi mateix.
Vaig a posar en pràctica una funció anomenada sigma, i va a prendre una
paràmetre -
Anem a trucar a que m, just pel que és diferent.
I després aquí, jo vaig a dir, així, si m és menor que 1 - aquesta és una
programa molt interessant.
Així que seguiré endavant i tornar immediatament 0.
Simplement no té sentit sumar tots els números entre 1 i m si m
és en si mateixa 0 o negatiu.
>> I després vaig a seguir endavant i fer-ho molt iterativa.
Vaig a fer aquest tipus de la vella escola, i jo seguiré endavant
i dir que vaig a declarar una suma igual a 0.
Llavors em vaig a tenir un bucle de int -
i m'ho dius a mi fer perquè coincideixi amb la nostra codi de distribució, pel que té una còpia
a la llar. int i s'obté en un màxim d'1 i és menor que o igual a m.
i plus plus.
I dins d'aquest cicle for -
ja gairebé estem allà -
suma s'afegeix més 1.
I després vaig a tornar la suma.
>> Així que vaig fer això ràpidament, molt cert.
Però, de nou, la funció principal és bastant senzill, basat en el codi que hem
escrit fins ara.
Utilitza el llaç dual per aconseguir un resultat positiu int des de l'usuari.
Després pas que int a una nova funció anomenat sigma, cridant, de nou, n.
I guardo el valor de retorn, la resposta en el quadre negre actualment
conegut com sigma, en una variable anomenada resposta.
Després ho imprimeixo.
>> Si ara continuarem la història, com s'implementa sigma?
Em proposo aplicar la següent.
Primer, una mica de comprovació d'errors per assegurar-se que l'usuari no és
jugant amb mi i passant un valor negatiu o 0.
Llavors em declaro una variable anomenada resumir i posar-lo a 0.
>> I ara començo a passar d'i és igual 1 tot el camí fins i incloent m,
perquè vull incloure tota la nombres de l'u al m, ambdós inclosos.
I dins d'aquest bucle for, acabo de fer se suma el que ara és, a més de la
valor de i.
A més, el valor d'i.
>> Com acotació al marge, si no has vist aquesta abans, hi ha una mica de sucre sintàctica
per aquesta línia.
Puc reescriure això com més iguala I, només per salvar-me a mi mateix unes poques tecles
i mirar una mica més fresc.
Però això és tot.
És funcionalment el mateix.
>> Per desgràcia, aquest codi de no va a compilar encara.
Si em quedo fer sigma 0, ho sóc Em va a cridar a?
Què va a li agrada?
>> AUDIÈNCIA: [inaudible].
>> DAVID Malan: Sí, jo no declaro la funció al capdamunt, no?
C és una mica estúpid, només en aquest fa el que vostè li diu que faci, i vostè
cal fer-ho en aquest ordre.
I així, si colpeig Introduïu aquí, jo vaig a rebrà una advertència sobre sigma implícita
declaració.
>> Oh, no és un problema.
Puc pujar al cim, i puc dir, està bé, espera un minut.
Sigma és una funció que retorna un enter i s'espera una
int com a entrada, punt i coma.
O podria posar tota la funció per sobre de principal, però en general, m'agradaria
recomanen contra això, perquè és bo tenir sempre principal a la part superior per
es pot bussejar en dret i saber el que és un programa està fent mitjançant la lectura principal primer.
>> Així que ara anem a netejar la pantalla.
Remake sigma 0.
Tot sembla anar a la sortida.
Déjame córrer sigma 0.
Entre Positiu.
Vaig a donar-li el nombre 3 Per fer-ho simple.
Així que em de donar 3 més 2 més 1, pel que 6.
Entrar, i de fet tinc 6.
>> Puc fer alguna cosa més gran -
50, 12, 75.
Així com una tangent, jo faré alguna cosa ridícul com una molt gran
nombre, Oh, que realment va funcionar -
eh, jo no crec que això sigui correcte.
Anem a veure.
Anem realment et metes amb ella.
>> Això és un problema.
Què està passant?
El codi no és tan dolent.
Segueix sent lineal.
Xiular és un bon efecte, però.
Què està passant?
>> No estic segur si he sentit.
Així que resulta - i això és com un part.
Aquest no és el nucli de la idea de recursivitat.
Resulta, doncs estic intentant representar un nombre tan gran, més
probablement està sent mal interpretat per C com un nombre no positiva,
però el nombre negatiu.
>> No hem parlat d'això, però és Resulta que hi ha números negatius
en el món, a més als números positius.
I els mitjans pels quals es pot representar un nombre negatiu
essencialment, s'utilitza una mica especial per indicar
positiu en negatiu.
És una mica més complex que això, però aquesta és la idea bàsica.
>> Així que, lamentablement, si C és confusa 01:00 d'aquests bits com en realitat vol dir,
oh, aquest és un nombre negatiu, el meu llaç aquí, per exemple, és en realitat mai
va a acabar.
Així que si jo fos realment una mica d'impressió una i altra vegada, sense
veure molt.
Però, de nou, aquest és el punt.
Això és en realitat una mena de curiositat intel · lectual que vindrem
enrere per finalment.
Però per ara, es tracta d'una correcta aplicació si suposem que el
consulta, donarà complerta ints que caben dins d'ints.
>> Però jo sostinc que aquest codi, francament, es podria fer molt més simple.
Si l'objectiu que ens ocupa és prendre un nombre com m i sumar tots els
nombres entre ella i 1, o per contra entre 1 i que, reclam
que puc demanar prestat la idea de fusionar tipus tenia, que estava tenint un problema
d'aquesta mida i dividint en una mica més petit.
Potser no mitjà, però més petit, però de manera representativa del mateix.
La mateixa idea, però un problema menor.
>> Així que estic realment - m'ho dius guardar aquest arxiu amb un nombre de versió diferent.
Anem a trucar a aquesta versió 1 en lloc de 0.
I jo puc dir que en realitat tornar a implementar això en aquest tipus de
endimoniada manera.
>> Vaig a deixar part del seu compte.
Vaig a dir que si m és menor que o fins i tot igual a 0 -
Jo només vaig a ser una mica més anal aquest moment
amb el meu comprovació d'errors -
Vaig a seguir endavant i tornar 0.
Aquest és arbitrària.
Estic simplement decidint si l'usuari em dóna un nombre negatiu, estic
retornant un 0, i que hauria d'haver llegit la documentació de més de prop.
>> Altres vendes -
compte del que faré.
La resta vaig a tornar m plus -
el que és sigma de m?
Bé, sigma de m + d menys 1, més minus m 2, més almenys 3 m.
Jo no vull escriure tot això.
Per què no acaba d'aclarir?
Recurrentment em truqui amb una mica problema més petit, punt i coma,
i en diuen un dia?
>> Cert?
Ara, també, es pot sentir o preocupar que aquest és un bucle infinit que sóc
induir, pel que m'estic posant en pràctica sigma trucant sigma.
Però això és perfectament correcte, perquè pensament per davant un afegit que les línies?
>> AUDIÈNCIA: [inaudible].
>> DAVID Malan: 23 a 26, que si és la meva condició.
Perquè el bo de la resta aquí, perquè he guardat
repartint sigma problemes més petits, més petita problemes, més petit - no és
la meitat de la mida.
És només un petit pas més petit, però això està bé.
Perquè al final, anem a treballar el nostre camí a 1 o 0.
I una vegada que arribem a 0, sigma no és passant a cridar més.
Es va a tornar immediatament 0.
>> Així que l'efecte, si aquest tipus de vent en la seva ment, és afegir m més
m menys 1, més m menys 2, més m menys 3, a més de punt, punt, punt, m menys
m, amb el temps que li dóna 0 i la efecte és en última instància, per afegir tots
aquestes coses juntes.
Així que no tenim, amb la recursivitat, resolt el problema que
no podria resoldre abans.
En efecte, la versió 0 d'aquest, i cada problema fins a la data, ha estat solucionable
amb només l'ús de bucles o mentre bucles o construccions similars.
>> No obstant això, la recursivitat, m'atreveixo a dir, ens dóna una manera diferent de pensar sobre
problemes, pel que si ens poden donar un problema, el divideix d'alguna cosa
alguna cosa gran en una cosa una mica més petita, afirmo que podem solucionar
potser una mica més elegant en termes del disseny, amb menys codi,
i potser resoldre els problemes que ser més difícil, ja que finalment va a
veure, la solució purament iterativament.
>> Però el drama de suspens que vaig fer vol deixar-nos en aquesta era.
Deixin-me seguir endavant i obrir un arxiu des de -
En realitat, em va deixar anar i fer això molt ràpid.
Deixin-me seguir endavant i proposo el següent.
Entri el codi d'avui és l'arxiu aquí.
Aquest d'aquí, noswap.
>> Així que això és una mica estúpid programa que Vaig treure fins que pretén fer
el següent.
En el principal, primer declara una int anomenada X i li assigna
el valor d'1.
Llavors es declara una i int i assigna el valor 2.
Després s'imprimeix el que és x i y.
Després diu, intercanvi, punt punt punt.
>> Llavors es diu que està cridant a una funció anomenada swap, passant x i
i, la idea que és que s'espera que x i i tornaran
diferent, el contrari.
Llavors diuen va canviar!
amb un signe d'exclamació.
Després s'imprimeix x i y.
>> Però resulta que aquesta mateixa simple demostració baix
aquí és en realitat errors.
Encara estic declarant un temporal variable i posar temporalment en una
, Llavors jo estic reassignant 1 el valor de b -
que se sent raonable, perquè he guardat una còpia d'una de temp.
Llavors puc actualitzar b a la igualtat de el que estava en temp.
Aquest tipus de joc de la closca de moure una en b & b en una a través d'aquest
mitjà-home anomenat temp sent perfectament raonable.
>> Però jo sostinc que quan executo aquest codi, ja que vaig a fer ara -
m'ho dius a mi anar endavant i enganxar-lo aquí.
Vaig a trucar a aquest noswap.c.
I com el seu nom indica, no és serà un programa correcte.
Feu noswap. / No swap.
x és 1, i és 2, l'intercanvi, intercanviar.
x és 1, i és 2.
Això és un error fonamental, fins i tot encara que això sembla perfectament
raonable per a mi.
I hi ha una raó, però no estem va a revelar la raó de moment.
>> Per ara el segon melodrama que volia deixar és això, 1:00
anunci de tipus de bons de descompte.
La nostra innovació amb fins de dies aquest any ha provocat un nombre no trivial
de preguntes, la qual cosa era no és la nostra intenció.
La intenció d'aquests bons de descompte, pel que si vostè fa part del problema
establir principis, aconseguint així un dia més, era realment per ajudar a vostès Ajuda
mateix començament d'hora, més o menys de l'incentivar vostè.
Ens ajuda a distribuir la càrrega entre horari d'oficina millor perquè
és una espècie de guanyar-guanyar.
>> Per desgràcia, crec que les meves instruccions no han estat, fins ara, molt clar, pel
Vaig tornar aquest cap de setmana i actualitzat l'especificació en el més gran, més audaç per al text
explicar bales com aquests.
I per dir-ho més públicament, per per defecte, els butlletins de problemes s'han de dijous
al migdia, pel pla d'estudis.
Si comença d'hora, acabant part de el problema plantejat per dimecres a les 12:00
PM, la part que es refereix a un cupó codi, la idea és que es pot estendre
el termini per a la P posat a divendres.
És a dir, poc fos una petita part de la P establir respecte al que normalment és el
problema més gran, i vostè compra mateix un dia més.
Un cop més, s'arriba a pensar en el conjunt de problemes, que
les hores d'oficina abans.
Però el problema segueix sent el codi de cupó necessari, encara que no els posis.
>> Però el més convincent és aquest.
(Xiuxiueig) I aquesta gent deixant d'hora van a penedir.
Com que són les persones al balcó.
Demano disculpes per endavant a les persones en la balconada per raons que seran
esborrar en un moment.
>> Així que tenim la sort de tenir un L'excap d'ensenyament dels becaris en CS50
una companyia anomenada dropbox.com.
Tenen molt generosament donat un codi de cupó aquí per a aquest espai,
que depèn de la habituals a 2 gigabytes.
Així que el que jo pensava que faríem en aquest nota final és fer una mica d'un sorteig,
pel que en un moment, anem a revelar el guanyador i que té un cupó
codi que després es pot anar al seu lloc web, escriure, i voila, obtenir un
molt més espai Dropbox per a la seva aparell i per als seus arxius personals.
>> I en primer lloc, que li agradaria participar en aquest dibuix?
Bé, ara que ho fa encara més divertit.
La persona que rep aquest 25-gigabyte codi de descompte - que és molt
més convincent que el difunt dia ara, potser -
és el que està assegut al cim d'una coixí del seient per sota de la qual hi ha
que el codi de cupó.
Ara pot mirar sota el coixí del seient.
>> [REPRODUIR VIDEO]
>> -Un, dos, tres.
>> [CRIDA]
>> -Tens un cotxe!
Vostè aconsegueix un cotxe!
>> DAVID Malan: Veurem que dimecres.
>> -Tens un cotxe!
Vostè aconsegueix un cotxe!
>> DAVID Malan: gent Balcó, veuen aquí baix a la part davantera,
on tenim extres.
>> -Tothom té un cotxe!
Tothom té un cotxe!
>> [FI REPRODUCCIÓ DE VÍDEO]
>> NARRADOR: En la següent CS50 -
>> ALTAVEU 5: Oh, Déu meu Déu meu Déu meu Déu meu caram caram caram caram caram caram -
>> [JOCS ukelele]