>> [Reproducció de música]
>> DAVID J. Malan: Molt bé.
Així que benvinguda.
Això és CS50 i el és Al final de la tercera setmana.
>> Així que recorda, en les últimes setmanes, hem passat una mica de
vegada en C, en la programació, a la sintaxi.
I és molt normal, si encara lluitant amb Problemes de 2, per ser
colpejar el cap contra la paret.
És missatges d'error críptic d'aspecte i els errors que
no puc perseguir.
Perquè, pot estar segur, que en tan sols un temps d'algunes setmanes de mirar cap enrere en
coses com César, [? V-Genair,?] fins i tot crack, i
compte de fins on ha arribat en un curt període de temps.
Així que si et serveix de consol, s'aguanta per ara.
>> Avui, però, vam començar la transició a les coses d'alt nivell.
I vam començar a donar per fet que Vostès saben com programar, o
menys els començaments de la aquest nivell de comoditat.
I anem a començar a considerar com podem anar sobre el disseny de programes més
efectivament.
Com es pot anar sobre l'optimització de la eficiència dels algoritmes i
generalment la solució més problemes interessants.
I començant a donar per fet que, Si volguéssim, podríem codificar qualsevol
dels exemples que tenim en ment.
Així que avui, no toquem el teclat per a qualsevol tipus de codi.
Serà nivell molt més alt, i en última instància, sobre la resolució de problemes.
>> Així que per arribar a aquest punt, permetin-me proposar que els següents set
rectangles representen set portes, darrere que són un munt de
nombres, entre els quals és el número 50.
Permetin-me en aquest projecte tan pantalla d'aquí també.
I proposem que necessitem un voluntari que ajudar-me a trobar un nombre davant de
l'Internet per veure.
Anem amunt, a la rosa.
Està bé.
Com et dius?
>> JENNIFER: [inaudible]
>> DAVID J. Malan: Com?
>> JENNIFER: Jennifer.
>> DAVID J. Malan: Jennifer.
D'acord, Jennifer.
Gust a conèixer-lo.
Anem amunt.
Així que ets aquí hi ha set portes, i el que M'agradaria que facis per nosaltres aquí,
davant de tots els seus companys de classe, nosaltres es troba el número 50.
Per trobar un nombre, vostè pot mirar darrere qualsevol d'aquestes portes amb un simple toc
en una de les portes, i es revelarà el seu nombre.
I anem a veure la rapidesa amb què ens pot trobar al número 50.
>> 15.
16.
50.
Molt ben fet.
Està bé.
Ronda d'aplaudiments per Jennifer.
>> [Aplaudiments]
>> Està bé.
Llavors, quin va ser la seva estratègia per trobar el nombre, 50?
>> JENNIFER: Um, vaig pensar que potser si -
[Inaudible]
>> DAVID J. Malan: Oh.
Doni-li un segon.
Així va ser la seva estratègia per trobar el nombre, 50?
>> JENNIFER: Així que em poso al començant a veure el que el primer número
era, i llavors vaig pensar, potser si que estan ordenats, que seguiré
tocant més amunt?
>> DAVID J. Malan: OK.
I sembla que hem trobat de ser el cas.
Encara que, anem a pelar les capes només una mica, i vol anar
endavant i revelar les altres portes que podria haver triat?
>> JENNIFER: Oh, estimat.
>> DAVID J. Malan: Ah.
>> JENNIFER: Així que vaig tenir sort.
>> DAVID J. Malan: Així que tens sort.
Està bé.
Així que no està malament.
Però això és una interessant idea, oi?
Si vostè va assumir, i ho va fer arribar, de fet, una mica de sort allà.
Però si se suposa que les xifres eren ordenada, pot ser més precís
com a la forma en què influenciats seu comportament?
>> JENNIFER: Així que si que estaven ordenats, em vaig pensar que potser menys a més.
>> DAVID J. Malan: OK.
>> JENNIFER: O si això va acabar sent molt gran, llavors major a menor.
>> DAVID J. Malan: OK.
Així major a menor, o més petit al més gran.
Però permetin-me proposar, suposi que té obtingut de mala sort, i suposem que
no van ser, de fet, ordenats, com molts aquestes portes que podrien haver hagut de mirar
darrere en que pitjor dels casos?
>> JENNIFER: Tots ells.
>> DAVID J. Malan: Tots ells.
Així que anem a generalitzar que com a n.
Passa que hi ha 7, però anem a més generalment diuen que hi ha n portes al
pantalla aquí.
Així que en el pitjor dels casos, vostè hauria de per mirar cap enrere 7 portes, o portes núm.
I pel que això és, que és una mica de sort avui, però en realitat és una relació lineal
algoritme de classes, tot i que eren una cosa que salta voltant.
És això just?
>> JENNIFER: Si.
>> DAVID J. Malan: Bé, deixa veure si el seu canvis d'estratègia si ens moguem
el nostre segon exemple aquí amb 7 portes diferents.
Mateixos números, però això moment en què s'ordenen.
Quina és la seva estratègia d'aquí serà, tractant de posar fora de la seva ment el que
els altres números eren -
>> JENNIFER: OK.
>> DAVID J. Malan: - abans?
>> JENNIFER: Anem a començar amb el primer.
>> DAVID J. Malan: Molt bé.
Comenceu amb la primera.
4.
Ara, a on aniràs, i per què?
>> JENNIFER: 4 és realment petit.
Així que si tenen sort potser més petit a més gran, el que hauria
ser el doble que, i -.
>> DAVID J. Malan: OK.
Anem a veure, que et sembla?
>> JENNIFER: Proveu l'última.
Niça.
>> DAVID J. Malan: Molt ben fet.
Està bé.
>> [Aplaudiments]
>> DAVID J. Malan: OK.
Així que en realitat estàs fent això horrible, perquè ets
fent molt bé.
Què ens deixa incapaços de fer que alguns punts.
Així que anem a tractar de fer retrocedir aquí.
>> JENNIFER: OK.
>> DAVID J. Malan: Molt bé fet, però.
Així que va començar a principis, vas veure que era 4, llavors
mogut fins al final.
Però suposem que no tingui sort allà, i suposo que 50
estava en una altra part.
El que el seu tercer pas ha estat?
>> JENNIFER: Torna al principi.
>> DAVID J. Malan: Tornar al principi.
Acceptar, pel que li ha tocat aquesta porta, que era agost.
Està bé.
Així que això no és 50.
On t'has mirat al costat?
>> JENNIFER: Si no ho fes saben el van arreglar.
>> DAVID J. Malan: Correcte.
Bé, si ho va fer saber van ser ordenats -
>> JENNIFER: Oh, sabia, sí.
>> DAVID J. Malan: - Però no ho vas fer saber que el 50 estava encara?
>> JENNIFER: Segueix endavant.
>> DAVID J. Malan: Molt bé.
D'acord.
Segueix endavant.
Bé, que puc treballar.
>> JENNIFER: OK.
>> DAVID J. Malan: Ara, si ets seguirà endavant, quin és el teu
algoritme que incumbeixen retrocedir fins.
>> JENNIFER: El lineal -.
>> DAVID J. Malan: És una mica lineal.
Però permetin-me proposar, i molt em poso en el lloc.
Deixa que et refresqui la pàgina.
mateix número, mateixa disposició, mateixes portes.
Però pensar en tornar a aquest primer dia en classe quan vam trencar una guia telefònica en
mitjà, més o menys, i el que era nostra estratègia allà?
>> JENNIFER: Comenceu en el centre.
>> DAVID J. Malan: OK.
Així que comença al centre.
Així que seguirem endavant i simular.
Comenceu al centre de revelant aquesta porta.
Així el nombre 16.
Llavors, quin seria l'home fort ha fet, que va arrencar el llibre de telèfon a la meitat,
per arribar a la següent conjectura?
>> JENNIFER: Anar en aquest mitjà.
>> DAVID J. Malan: I per què a la dreta?
>> JENNIFER: Si fossin una mena de petit a més gran, a continuació, 50 ha de ser
en aquest extrem.
>> DAVID J. Malan: Good.
Totalment raonable.
Així com un directori telefònic, vostè va a la dret en oposició a l'esquerra, però aquí
és el punt clau.
Ara pot tirar, o arrencar, mitjà d'aquest problema, no la deixa
amb 7 portes, però en realitat amb només 3.
Que és aproximadament la meitat de la mida del problema.
Està bé.
Així que ara el que hauria realitzat després d'anar a la dreta?
>> JENNIFER: Llavors 16 és encara molt petita, en relació amb el 50, així que potser vaig a tractar,
com, aquest.
>> DAVID J. Malan: Molt bé.
42.
Molt bé, així que ara el que és seu instint que li diu?
>> JENNIFER: Puc llençar això i després simplement -
>> DAVID J. Malan: OK.
Bé, vostè pot tirar la meitat esquerra allà.
>> JENNIFER: - escollir aquest.
>> DAVID J. Malan: I de la dreta.
>> JENNIFER: Si.
>> DAVID J. Malan: Així que, encara que és difícil per veure potser, quan només hi ha
7 portes, pensar, ara, la consistència de la
Algorisme que acaba d'aplicar.
En el cas anterior, que va fer que tingui sort, que era genial.
Però ho vas fer servir una heurística, Diria jo.
Utilitzar espècie dels seus instints, i saber el resolt, si és prou
petita al principi, òbviament, hem ha d'anar més a la dreta.
Però en cert sentit, tens sort, perquè potser aquest va ser el número 100,
i potser 50 era més en el medi.
Potser 50 va ser encara més aquí.
>> Però el que va fer una mica diferent aquesta vegada va ser, que va fer el mateix
una i altra vegada.
I jo diria que el que acabes de va fer, encara que influït pel telèfon
exemple de llibre, és una cosa molt més algorítmica, i molt
menys especial revestit.
Molt menys instintiu.
Així que al final del dia, com que descriu l'eficàcia de la
primer algorisme, en què es esquerra a dreta, enfront de la
segon algorisme aquí?
>> JENNIFER: Aquest ha, igual que, potser reduir a la meitat el temps, o fins i tot més, si.
>> DAVID J. Malan: OK, potser encara més.
Anem a empènyer una mica més en això.
El que, si seguim aquest lògica, que sens dubte redueix a la meitat el
temps de funcionament amb aquest segon algorisme deixant de banda la meitat de la
números, però el que vam fer a la següent iteració, quan Jennifer va revelar
el segon número?
>> Hem reduït a la meitat el nombre de portes.
I llavors què vam fer després d'això, si hi havia més portes per jugar?
Volem reduir a la meitat, i de nou, i una altra, i una altra.
I això era com vosaltres tots de peu a la primera setmana de
classe, la meitat de vostès assegut, mig de vostès asseguts, la meitat de vostès
seure, fins que un solitari ànima estava dempeus.
I vam dir que el temps d'execució de que, el nombre de passos que va prendre era
en l'ordre del que?
>> ALTAVEU 1: [inaudible]
>> DAVID J. Malan: Així logaritme en base 2 de n, o simplement més simplement, iniciar de n.
Així que alguna cosa logarítmica.
I la gràfica no era una línia recta que acaba d'arribar en pitjor, que era
interessant aquesta corba que no ho va fer estar tan malament amb el temps.
Així que anem a aferrar-se a aquesta idea.
Donem gràcies a Jennifer.
Gràcies per venir a endavant.
I, un segon.
No hi ha llums d'escriptori avui, però Què tenen CS50 boles de la tensió.
>> JENNIFER: Yay.
>> DAVID J. Malan: Molt bé, aquí.
Gràcies per incórrer en la tensió aquí.
Està bé.
Així que anem a veure si no podem ara formalitzar aquest una mica més.
Així que de nou, el que vam fer va ser essencialment el mateix que vam fer
en la primera setmana.
Però en comptes d'acabar amb només un lineal algorisme, que és representat
anteriorment com la línia recta, pel que, si col · loquem una porta més a
la pantalla, a continuació, Jennifer faria han hagut de buscar, en potència,
darrere d'una porta més.
Si posem dues portes més, ella podria tenir per mirar darrere de dues portes més.
>> I així, hi havia un lineal relació entre la mida de la
problema en, per exemple, l'eix x, i la quantitat de temps que es necessita per
resoldre a la i.
Però la imatge que s'estava referint a abans era la línia verda.
Verd deliberadament, perquè se sentia millor.
En teoria, l'algorisme, quan ho vam fer amb la guia telefònica, quan ho vam fer
amb vostès comptant entre si, i en el segon cas, quan Jennifer acaba
ho va fer aquí, que era una mena de fonamentalment millor.
A causa que no era només el doble de ràpid.
No va ser fins a quatre vegades més ràpid.
Era totalment dependent del que l' mida de l'entrada era, quant a quants
mesures que en última instància va.
>> I així, aquest simple idea que tot el que vam fer per descomptat amb la guia telefònica,
de manera similar pot ser aplicat a alguna cosa com això.
I això podria ser més informal coneguda com, com pot ser que
imaginar, divideix i venceràs.
No gaire diferent del que vam fer, per descomptat, amb la guia telefònica.
>> Però el pseudocodi, record, era això.
Així que no farem això de nou, però recorda la primera setmana, tots es van posar drets
i després la meitat de vostès es van asseure, la meitat que es va asseure, la meitat de vostès es va asseure.
Això algorisme va ser implementat en un mica d'una manera fer trampa en això,
No va ser només una de les em comptant, fonamentalment, de manera més eficient.
En aquest cas, em Aprofitant un recurs secundari.
Més o menys, diverses CPU, múltiples cervells, moltes persones intel ligents en el
habitació estaven ajudant a aconseguir a partir d'alguna cosa lineal a alguna cosa
logarítmica, d'alguna cosa vermell amb una mica verd.
>> Però en aquest cas, Jennifer solament pot fonamentalment, millorar la
el rendiment del seu primer algorisme per, altra vegada, pensant una mica més difícil.
I ara, quan arriba el moment de posar en pràctica aquestes coses, esbrinar
quines línies de codi es pot escriure com que es pot repetir una vegada més, i
una altra vegada, i una altra, una mena de d'una forma de bucle.
Com que vostè no va a tenir la de luxe, igual que Jennifer va fer al principi,
només hi ha un munt de sís i dir: hmm, si aquest primer número és 4,
m'ho dius a mi saltar tot el camí fins al final.
Oh, si aquest nombre és massa gran, Permetin-me passar arbitràriament de nou
per al segon element.
Trobareu que això serà molt més difícil de formalitzar el que els éssers humans
donar per fet com molt raonable heurística, però un ordinador és només
farem el que vostè li digui que fer.
>> Ara bé, això té molt interessant implicacions.
Aquesta gràfica és una espècie de dir que tipus de saturar visualment, però avís, quan
és la línia recta en el gràfic?
On és la gràfica lineal que anomenem n?
Bé, és una espècie de cap a la part inferior d'aquesta imatge, oi?
Així que tot el que hem fet és que hem mena de ampliada a l'eix x i el
eix per intentar tenir una idea del que altres tipus de corbes semblen.
>> I els detalls de la matemàtica expressions avui no importa el
molt, però noten que hi ha una gran quantitat de algoritmes que són molt pitjors que
cosa que és lineal.
En efecte, n cubs es veu molt malament.
2 a la núm es veu molt malament. n quadrat es veu molt malament.
I anem a veure el que alguns dels podria ser en realitat avui en dia.
I log n no se sent tan malament, però millor que n és log base 2 de n.
Però ja saps, hauria estat encara més sorprenent si Jennifer, o si,
la primera setmana, s'havia arribat amb una cosa que és registre de log de n.
>> En altres paraules, hi ha un conjunt gamma de possibles solucions als
problemes, però fins i tot en aquest cas, l'avís el que va a succeir.
En allunyar la imatge, quina d'aquestes corbes arribarà a ser l'absoluta
pitjor dels que estan a la pantalla ara?
Llavors n cubs es veu molt malament en aquest moment.
Però si allunyar i veure més de la x i l'eix i, qui va a
dominant en última instància?
Per tant, en realitat resulta que 2 a la n, i es pot resoldre això amb només
endollant algun cada vegada més gran números i veureu que 2 a l'
n, de fet, es fa més gran molt més ràpid.
Si realment allunyar la imatge, un 2 a la algoritme n absolutament horrible.
Vull dir que això va a prendre una mica de temps perquè la
equip per batre través.
>> Però veurà amb el temps, especialment amb els futurs butlletins de problemes i fins i tot
projectes fi de carrera, és les seves dades conjunt es fa gran, d'acord?
Fins i tot en la primera versió de Facebook, com el nombre d'amics, i la
nombre d'usuaris registrats té gran, es pot ordenar de telèfon dins i
implementar alguna cosa amb recerca lineal, o una classificació molt simple
algorisme, com veurem avui.
Has de començar a pensar més i més sobre aquests problemes.
I els tipus de problemes de llocs com Facebook i Google, i Microsoft,
i altres treballen és exactament tipus de dades de gran classe de preguntes
cada vegada més en aquests dies.
>> Està bé.
Així que l'èxit de Jennifer en aquest segon algorisme, francament, ho va fer increïblement
bé la primera vegada, però anem a escriure la sort perquè puguem
pot aclarir aquest punt.
En el segon cas, s'ha mobilitzat algoritme que repeteix una i altra
una altra vegada, però ella va donar per fet 1 certa suposició que hem permès
, Però ella explota cert detall el segona vegada que ella no tenia la
primera vegada.
Què va ser què?
>> Això es va solucionar la llista.
Així que tan aviat com s'ordena la llista, afirmen que Jennifer era capaç de fer
fonamentalment millor.
7 portes, si, no és tan interessant, però suposem que estem 7000000 portes.
Bitàcola de n és, sens dubte va per dur a terme molt, molt
més ràpid en el llarg termini.
Però ella havia de tenir la portes ordenats per ella.
Ara, em vaig prendre la llibertat de fer això per avançat en la pantalla de l'ordinador
aquí, però suposo que Jennifer havia de fer ella mateixa?
Suposem que les portes en qüestió dades representades en una base de dades, o
amics registrats a Facebook, o qualsevol de les pàgines web a Internet que
diversos llocs web podrien necessitar l'índex o buscar de nou.
>> Suposem que vostè acaba de tenir una base de dades en brut estableix i es va deixar a vostè, o per
Jennifer fer que la classificació?
Això, més aviat, requereix que responguem la pregunta, bé, quant de temps
hauria pres Jennifer, o fins i tot jo, per ordenar els nombres per endavant per
que podia prendre avantatge d'això?
Cert?
A causa de la implicació, per descomptat, és si em porta bastant temps per ordenar
els números, qui diables li importa que pot trobar un nombre com 50 tan ràpid,
com en el cas de Jennifer, si més d' aclaparat la quantitat de temps total
que va prendre d'ordenar les coses per endavant?
>> Així que anem a veure si no podem l' pintar el quadre aquí.
Tinc un munt més estrès boles, si això ajuda
trencar el gel aquí.
I si no t'importa, ens necessitarà 07:00 voluntaris -
a, OK.
Wow.
Així que no hem de gastar en els llums d'escriptori, el que sembla.
Està bé.
Així que hi ha de vosaltres dos al front.
Què hi ha de vosaltres dos a l'esquena.
Així que això és quatre.
I tu per davant cinc, sis-set.
Aquí mateix.
El teu amic t'està assenyalant, perquè pugui obtenir el premi.
>> Està bé.
Anem amunt.
I per què no hem de nois vénen per aquí.
Jo et vaig a donar a cadascun un nombre.
I seguir endavant i organitzar a si mateixos idèntica al que és
es mostra a la pantalla.
>> [Interrompent VEUS]
>> DAVID J. Malan: OOP, ho sento.
Bug.
Està bé.
Bé, aquí anem.
El número cinc.
El número sis.
Un, dos, tres, quatre, cinc, sis, set.
Oh, això és incòmode.
>> ALTAVEU 2: Vaig a buscar -.
>> DAVID J. Malan: Good deal.
Està bé.
Gràcies per participar.
>> [Aplaudiments]
>> D'acord.
Està bé.
Així que tenim quatre, dos, sis, un, tres, set, cinc.
Perfecciona així que tenim 7 voluntaris aquí, que són iguals en amplada a la
matriu que estem jugant amb l'anterior.
I vaig triar set per raons que serà només
convenient en una mica.
I jo vaig a proposar que la primera que resolguem aquests set voluntaris.
Si ho desitja, en primer lloc, per saludar però.
Atès que això serà un incòmodes diversos minuts.
Presenteu-vos.
>> GRACE: Hola, sóc la Gràcia.
Sóc un estudiant de segon any a Leverett House.
>> BRANSON: Hi.
Estic Branson.
Sóc un estudiant de primer any a la soldadura.
>> GABE: Hi.
Sóc Gabe.
Sóc un jove a Cabot.
>> NEIL: Sóc Neil.
Sóc un estudiant de primer any a Matthews.
>> JASON: Sóc Jason.
Sóc un estudiant de primer any a Greenough.
>> MIKE: Sóc Mike.
Sóc un estudiant de primer any a Grays.
>> JESS: Sóc Jess.
Sóc un estudiant de segon any a Leverett.
>> DAVID J. Malan: Excel · lent.
Està bé.
Bé, gràcies a tots els nostres voluntaris aquí fins ara.
I el desafiament a la mà ara es va estar a la classe d'aquests nois, però després
anem a haver de pensar una mica estès sobre l'eficiència amb que en realitat
ells ordenats.
Així que anem a provar primer això.
Vostès poden veure els números de cadascun amb només posar al voltant de les cantonades.
Seguiu endavant i feu una segons i Ordenar vosaltres mateixos des del més petit al
esquerra a la més gran de la dreta.
Vaya.
>> D'acord.
Bé.
Això va ser realment maleït ràpid.
Ara algú aquí, quin va ser l'algoritme de que aquests tipus aplicats?
>> ALTAVEU 1: De menys a més.
>> DAVID J. Malan: OK.
De menys a més és realment una espècie de objectiu, però no estic segur que és
realment un algorisme.
De menys a més no diu Em pas a pas què fer.
Sí?
>> ALTAVEU 1: [inaudible]
>> DAVID J. Malan: OK.
Així que si veus una persona menor d' seu nombre, a continuació, passar a
la dreta d'ells.
Així que ara és cada vegada més expressiva, més com un algorisme, ja que
pot dir, si això, llavors això.
Així que tenim algun tipus de constructor condicional.
I aquests nois semblaven fer que uns pocs vegades, a causa que alguns de vostès es va moure una mica
de la distància.
Així que havia presumiblement algun tipus de bucle passant en les seves ments.
>> Però anem a tractar de formalitzar això.
Si vostès poguessin restablir de nou amb aquesta disposició.
Anem a veure si podem formalitzar aquest 1 poc, i després fer la pregunta, simplement
què tan eficient és això?
Per descomptat, quan fem això més lentament, es va a sentir tan bé
un algorisme, però veurem si podem posar els dits en els passos precisos.
>> Així que vostès dos són quatre-dos.
O vostè ordre correcte o incorrecte?
Evidentment falsos.
Així que canviem.
Ara em vaig a moure a un costat aquí i dir, quatre a sis.
Està correcte o incorrecte?
>> GABE: Correcte.
>> DAVID J. Malan: Correcte.
Sis i un?
Nope.
Intercanviar.
Així que per dos swaps.
Sis-tres?
Nope.
Intercanviar.
Sis-set?
Es veu bé.
Set-cinc?
>> JESS: [inaudible]
>> DAVID J. Malan: OK, intercanviar.
I ordenats.
Està bé.
Així que, òbviament, no, oi?
Així que no hi havia més que fer.
Però, de fet, aquests nois, fins i tot instintivament.
seguia avançant.
No es van limitar a parar, un cop corregit un problema.
Així.
De fet, jo vaig a tenir a fer el mateix.
Vaig a haver d'ordenar de rebobinat de nou al principi d'aquest problema,
o el començament d'aquesta sèrie de gent, anem a començar a trucar a ells.
>> I ara, què hauria de dir al meu algorisme en el segon passi de ser?
>> ALTAVEU 1: És el mateix.
>> DAVID J. Malan: És el mateix.
I això, estic començant a agradar, oi?
Tan aviat com vostè pot trobar fent la mateixa cosa una i altra vegada, això és
cada vegada més com un algoritme, i menys instint humà.
>> Així que ara, aquí anem de nou.
Dues-quatre?
No
Quatre i un?
Ah, havia fet algunes treball que queda per fer.
A favor i tres?
Bé.
Quatre-sis?
Sis-cinc?
Sis-set?
Bé, ara, fet.
Bé, no.
He de tornar.
>> Així que ara, un cop més, estem fent això una mica més de forma deliberada.
I ara, no hi ha un sol cervell l'execució d'aquest algorisme.
Una CPU, si es vol.
I, francament, aquest és l'únic recurs tindrem accés.
I una vegada que ens fa tornar a un teclat i tenir una mica com C en la nostra
disposició, només estem escrivint un programa que pot fer una cosa alhora.
Atès que, aquests nois fa un moment, apalancat seva capacitat intel · lectual col · lectiva
com vostès van fer a la setmana zero.
Així que seguirem fent això.
>> Dos i un.
Dues-tres.
Tres-quatre.
Quatre-cinc.
Cinc-sis.
Sis-set.
Fet?
Així que jo, però em deixa jugar advocat del diable.
Tinc el tipus d'equip que acaba de va fer un passi a través d'aquesta sèrie de
gent, saben que he acabat?
>> ALTAVEU 1: No
>> DAVID J. Malan: Per què?
Què he de fer per tal de Concloc amb decisió que he fet?
Probablement un pas més.
Cert?
Perquè tot el que sé d'aquest anterior passi és que he corregit un error.
I això vol dir, tal vegada hagi Encara un altre error
que he de corregir.
Així que només puc estar segur de rebobinat i a continuació, comprovar, un a dos, i 2
3, tres i quatre, quatre i cinc, 05:06, sis i set.
Bé, ara jo no treballo.
>> Certament, puc recordar que vaig fer no treballar amb alguna cosa semblant a una variable,
com un int.
Llámelo swaps, swaps i si és 0, un cop arribar fins aquí, i va començar a 0, llavors
Només vull ser estúpid per seguir endavant d'anada i tornada, comprovant de nou, i
una altra vegada, i una altra, oi?
Perquè et quedes encallat en algun tipus de bucle infinit.
Així que quan hi ha 0 swaps, podem afirmar que aquesta
algorisme és, en efecte complet.
>> Ara, anem a posar un nom a això.
L'algorisme que proposo ens es va implementar una cosa que es diu bombolla
tipus, coneguda com a tal en el sentit que els nombres que són més grans tipus de
bombolla del seu camí al cim, o fins al final de la matriu dels nombres.
Però què tan eficient va ser aquest algorisme?
Quants passos vaig físicament he de Prenguem, per exemple, per ordenar aquests
07:00 éssers humans?
>> Quatre o cinc?
Bé, també molts és en última instància, serà la resposta.
Però fins i tot llavors, el nombre específic no és tan interessant.
Anem a generalitzar com a n.
Així que si jo hagués n la gent aquí, i eren, més o menys, en un ordre aleatori en la
començant, en aquest ordre original.
Bé, quants passos vaig haver prendre el primer pas?
Va ser un, dos, tres, quatre, cinc, 06:00, i són set persones, pel que
això és set, sis -, pel que és n menys un passos que la primera vegada.
>> Ara, quants passos vaig haver prendre quan Rebobine?
Bé, en realitat podria doblar que si que realment volia, però per ara, estic
només vaig a dir, està bé, un altre n almenys 1.
Així que el n almenys 1 es posarà molest per no perdre de vista, així que anem a
a la tornada una mica.
Així 2n passos.
Així que 14 passos, més o menys.
>> Quantes vegades em prenc un pas la propera vegada?
Bé, és 3n.
realitat.
I ara, en el pitjor dels casos, per exemple, quantes vegades hauré
anat cap enrere i endavant, enrere i endavant, l'execució d'aquest algorisme, l'intercanvi
persones en cada pas, més o menys?
De fet, és n al quadrat, oi?
>> A causa que en el pitjor dels casos, pot tipus de pensar en això intuïtivament,
tot i que pot ser que prengui una mica de poc de temps per assimilar
En el pitjor dels casos, el que faria aquestes set persones han vist com, en
termes de l'acord dels seus números?
Completament a l'inrevés, no?
I per simular que, Quin era el seu nom?
>> MIKE: Mike.
>> DAVID J. Malan: Mike?
Bé, Mike, ¿pots venir amb mi sobre aquí només per un segon?
En realitat, no.
Ho sentim Mike, anem a retrocedir.
Quin és el teu nom?
>> NEIL: Neil.
>> DAVID J. Malan: Neil.
Acceptar, Neil, que vénen amb jo, si no m'importa.
Així que vaig a proposar, només per simplicitat, que Neil es troba ara en el seu
pitjor dels casos possibles.
Però recordo com he implementat el meu algorisme.
Estic comparant, comparar, comparar, comparar, comparar, oh.
Ara aquests nois són fora de l'ordre, així que arreglar.
Així que vostès swap.
Però considerem ara, quant més lluny Neil no ha d'anar?
És més o menys n.
Ja saps, no és en realitat n.
És com n menys 1, però m'estic posant molest pista custòdia de la petita
nombre, pel que anem a cridar n.
>> Així que si Neil fa un pas al màxim cada temps, i per moure Neil un pas,
He de fer aquest pas realment tediós anada i tornada, això és més o menys
D'aquesta manera, n passos, un total de n vegades, perquè va a portar
que molts passos per arribar Neil tots el camí a on pertany.
Per no parlar de tots els altres si vostès estaven tots mal ordenat també.
>> Així que anem a trucar a la ordenació de bombolla n al quadrat.
El temps d'execució d'aquest algorisme, el funcionament d'aquest algorisme, la
l'eficiència d'aquest algorisme, ens acaba de descriure amb major
generalment com a n al quadrat.
La qual cosa és bo, perquè jo podria fer el mateix exemple amb vuit persones, nou
persones, un milió de persones, i que resposta no canviarà.
>> Així que si vostès no li importa, anem a de reajustar al punt de sortida.
I tractarem dos enfocaments i si no podem fer-ho fonamentalment
millor que això.
Així que aquesta vegada, vaig a proposar una mena d'algorisme diferent.
Això va ser molt intel · ligent de nosaltres l'última vegada, i vostès tenien raó perquè el
instints correctes de només una mica d'intercanvi de parelles.
Però si realment volia abordar aquest simplement, i la meva meta és moure
tots els petits números d'aquesta manera, i impulsar totes les grans xifres que
Així, per què no acaba de fer això al més ingènua manera possible i veure si
pot fer-ho millor que el que era un bastant complex algoritme?
>> Així que anem a veure.
Quatre és un nombre bastant petit, així que estic sortirà d'allà ara.
Ooh, el número dos és encara millor.
Així es pot simplement fer un pas endavant per un moment?
Aquesta és actualment el meu petit numerat candidat, i jo vaig a recordar
que amb, com, una variable.
Però jo vaig a seguir buscant.
Hi ha algú la nombre és menor?
Sis, no.
Oh, hi ha Neil de nou.
>> Així que vaig a empènyer de nou tipus de vista conceptual.
Neil serà presentat.
I ara, la variable que estic fent servir per realitzar un seguiment de qui té el més petit
nombre s'actualitza per contenir La ubicació de Neil.
Bé, anem a veure.
Tres, set, cinc.
Bé, sé que Neil era el més petit.
Quina és la cosa més simple per a mi fer ara?
Jo no vaig a perdre el meu temps amb només bombolles Neil 1 lloc a l'esquerra.
Per què no acaba de posar Neil on pertany, que és, per descomptat, on?
>> Tot el camí des del principi.
Així que Neil, vine amb mi.
¿I quin era el seu nom?
>> GRACE: Gràcia.
>> DAVID J. Malan: Gràcia.
D'acord.
Així també la gràcia, per desgràcia, està una mica en el camí.
Llavors, com podem resoldre aquest problema?
Cert?
Si es tracta d'una matriu, no hi ha només set llocs.
Recordem que, amb Rob, parlem de declarant les edats, i que només tenia un
nombre finit d'edats?
La mateixa idea aquí.
Només tenim un nombre finit d'enters.
La gràcia és una mica en la nostra manera, així que com ho arreglem?
>> La forma més senzilla és com, La gràcia, ho sento.
Vas a haver d'anar allà, així que pot donar lloc.
Ara, si es pensa en això, potser que acaba de fer el problema pitjor.
I potser ho vam fer, perquè el que si La gràcia era al lloc correcte?
Però sabem que no ho és, perquè en cas contrari, hauria estat
peu cap endavant en lloc de Neil en aquest moment, no?
Ja hem comprovat el seu nombre fos.
>> Està bé.
Així que ara, Neil està en el lloc correcte, i Jo puc fer una lleugera optimització.
Durant la següent hora, vaig a ignorar Neil tots junts, a fi de no
perdre el temps, o accidentalment li canviï al lloc equivocat.
Així que ara, com puc trobar la següent element que és més petit?
Dos.
Això és un nombre força bo, si vol donar un pas endavant i
Jo et recordaré.
Sis, no és bo.
Quatre, tres, set, cinc, no és bo.
Així que anem a moure a seu lloc correcte.
I vam tenir sort aquesta vegada.
>> Ara, jo faré cas omís d'aquests dos nois, i ara fer una més
passar a través d'això.
Six que un nombre molt petit.
Anem cap endavant.
Oh, ho sento.
Nombre de Grace és millor, per trepitjar cap endavant.
Quatre.
Ho sentim, Grace.
Torna una altra vegada.
El número tres és millor.
Seven.
Cinc.
I ara, ¿quin és el teu nom?
>> JASON: Jason.
>> DAVID J. Malan: Jason.
Així que Jason és ara el més petit element que he seleccionat.
A on va a anar?
Així què sis és.
I el seu nom és nou?
>> GABE: Gabe.
>> DAVID J. Malan: Gabe.
Gabe està en el camí.
Quina és la cosa més fàcil de fer?
Canvieu aquests dos nois i continuar.
Així que ara veurem.
Qui és el més petit?
Quatre.
Déjame només una mica de trampa.
Cinc serà el més petit.
Em sembla pròxim, si vostè vol fer un pas cap endavant, què tinc a veure amb
aquests nois, amb Gabe?
Canvia de nou.
Així que ara, encara una mica fora de lloc.
Vaig trobar Gabe sigui el més petit, pel que Ho fan esclatar cap a fora, vostè es mou nois més.
I fet.
>> Així que la resposta és la mateixa.
El resultat final és el mateix.
Quin d'aquests dos algorismes és millor?
El segon, vaig sentir.
Per què?
>> ALTAVEU 3: És N passos [inaudible].
>> DAVID J. Malan: És n passos com a màxim.
Interessant.
Així és que, encara?
Llavors, com puc trobar la element més petit?
Quants passos vaig haver de prendre en trobar l'element més petit?
Tenia una mirada tot el camí al final, no?
Perquè en aquest cas més desfavorable, el que si Neil estaven per aquí?
Així que trobar l'element més petit em n passos, o núm menys 1 presa.
Però, a D'acord.
Així fixar Neil.
Recordeu que, un minut o així ho fa.
>> Però, com trobar la següent element més petit?
És n menys 1 o n almenys 2 realment, a partir del nombre de passos.
Així que bé.
Així que em vaig N almenys 2.
Està bé.
Així se sent una mica millor.
Està bé.
Quants passos la propera vegada per trobar el número tres?
Per tant n almenys 4.
Així que és decreixent, un menys pas en cada iteració.
Així que això se sent millor, oi?
Si l'última vegada que va ser més o menys n vegades n, aquesta vegada és n menys 1, més n menys
2, més n menys 3, més n menys 4, punt, punt, punt.
Però si vostè recorda de la seva escola secundària llibres de text, la petita trucs
full a la part del darrere que té les fórmules, si realitzar la suma d'aquesta sèrie de nombres,
el que és el nombre total de passos sigui que em prenc aquí?
>> Aquest és un dels, com, n menys 1, n vegades, dividit per 2.
Així que permetin-me veure si puc treure això per un moment.
I de nou, estic una mica d'arrodoniment alguns números només per mantenir la nostra vida simple,
però pel que recordo, és com si Faig n almenys 1 coses, llavors n menys
2, llavors n menys 3, és més o menys una cosa així més de 2, i si
multipliqui això, això és realitat plaça núm.
Que no se sent molt bé. n menys n sobre 2.
>> Però aquí està la cosa.
En ciències de la computació, quan els problemes començar a posar-se interessant és quan n
es posa molt gran.
I quan n es fa molt gran, que d' aquests valors es van a dominar tota
dels altres?
És una mica el n al quadrat, oi?
Sí, dividir per 2 és bastant bo.
Però si vostè està parlant de milers de milions de peces de dades, o trilions de
peces de dades, OK, pel que vostè és el doble de ràpid.
Però a qui li importa si és molt gran el nombre, si aquest factor és el que fa
més i més gran.
I sens dubte, té més de una diferència d'aquest tipus.
Així que tot i que vostès estan bé, el segon algorisme, l'anomenarem
ordenació per selecció, és a dir, en el món real, un poc més ràpid en potència, perquè sóc
tenint cada vegada menys passos cada vegada.
>> En realitat no és fonamentalment més ràpid.
Perquè si en realitat ens juguem això per grans valors de n, al final de
del dia, durant el temps suficient n gran, és encara va a sentir bastant lent.
Bé, deixa prendre una últim pas en això.
Això és el que jo anomenaria ordenació per selecció.
Poden vostès restablir mateixos per última vegada?
I en aquest últim cas, vaig proposar alguna cosa
anomenada ordenació per inserció.
L'ordenació per inserció és, conceptualment, una mica diferent.
>> En lloc d'anar i venir i seleccionar l'element més petit, estic
només anem a tractar cada un d'aquests nois que em trobo, i inserit
ells en el seu lloc correcte.
Així que vaig a començar amb la Gràcia, i veig que ella és el número quatre.
A on pertany el número quatre?
Encara no he començat la classificació res, Així que la gràcia arriba a quedar-s'hi.
I ara vaig a reclamar, si pogués donar un pas a la dreta, aquesta
meva llista ordenada, aquest és el meu llista restant Unsorted.
Així que ara vaig a procedir a continuació, i quin és el teu nom?
>> Branson:.
>> DAVID J. Malan: Branson.
Així Branson és el número dos.
Així que vaig a haver de per un moment.
I ara, ¿a on pertanys en aquesta sèrie?
Així que a la dreta de la Gràcia.
Així que de nou, estem com el La gràcia fer un munt de treball aquí.
A on et posem?
Així que anem per lliscar a la a l'esquerra, i introduïu Branson allà.
Però ara afirmo que vostès fan.
Però cal notar, no vaig a utilitzar l'espai addicional.
Segueix sent 2 elements aquí, maig aquí.
Mida total de la matriu és de 7, així que estic No fer trampa, d'acord?
>> Així que ara tenim, amb Gabe aquí, el número sis, on pertany vostè?
Vas tenir sort de nou.
Així que vostè pot quedar-s'hi.
Només cal fer un lleuger pas a la dreta només per deixar en clar que està ordenada.
I ara tenim a Neil de nou, el nombre de un, ¿a on vas?
I ara és quan anem a començar a veure que aquest algorisme, encara que en la primera
mirada, se sent molt intel · ligent, cura el que està a punt de succeir.
Si pogués fer un pas endavant.
>> On volem posar Neil?
Així que, òbviament, aquí, així que com Com aconseguim Neil allà?
Farem això pas a pas.
Gabe, on ha d'anar?
Sí, a fi de prendre un gran pas, o dues mitges passos per fer
un pas més enllà.
Gràcia, on vas?
Bé.
Així que un altre pas.
I, finalment, Branson?
Un pas més.
I ara podem posar Neil al seu lloc.
>> Així que ara, segueixen aquesta lògica.
Tot i que no estem canviant Neil altra, i una altra, i una altra, per posar-
on va, en el pitjor dels casos, la següent nombre, podríem trobar-nos podria
sigui el nombre, per exemple, hi va haver un nombre zero, llavors canviarem tots
aquests nois.
Suposem que hi ha un nombre negatiu un, llavors hem de canviar
tots aquests nois.
Així que estem realment només una mica de moure d'una tirada el problema de la volta, de manera que estem
la transferència de la costa de l' procés de selecció pel que la inserció
procés, de manera que vostès acabaven de per moure més o menys n almenys alguna cosa
nombre de passos.
I aquest nombre de passos només es va augmentant a mesura que selecciono més números,
si he de seguir empenyent a vostès esquena, i l'esquena, i l'esquena.
>> Així ho trist ara és tot això algoritmes són n al quadrat.
Seguirem endavant i gràcies a ells nois, i visualitzar aquestes una mica
diferent.
Molt ben fet.
>> [Aplaudiments]
>> Està bé.
Aquí el tens.
Gràcies per -
>> Branson: [Inaudible] mantenir els números.
>> DAVID J. Malan: No, vostè pot mantenir els números també.
Està bé.
Molt ben fet.
Està bé.
Així que anem a veure si ara no podem resumir més ràpidament, i més visualment,
exactament el que ha passat aquí com segueix.
Vaig a seguir endavant i tiri cap amunt Firefox.
Ens vinculem aquesta demostració a la pàgina web del curs.
Java és una mica molest per aconseguir feina en alguns navegadors en aquests dies.
Així que si no jugues amb això a casa, s'adona que podria haver de fer servir Firefox
perquè funcioni.
I què faré amb aquesta demostració és la següent.
>> A la part inferior, tinc un munt de opcions del menú, incloent un inici i un
botó d'aturar.
A més, en un apart, sembla que hi ha una error en aquests programes, per la qual cosa
no pot veure realment l'inici o aturar botó llevat que mantingui Comando o Alt
més i zoom in, que curiosament que mostra més botons.
Així que ho dic si jugues amb això a casa.
Ara vaig a fer clic a Inici, en un Actualment, després d'especificar un retard de,
com, a 200 mil · lèsimes de segon aquí, molt perquè puguem veure el que passa.
>> Per això afirmo que es tracta d'una visualització de la primera algorisme
aquests nois han fet, una mena de bombolla, en què intercanviem persones per parells.
La idea clau d'aquesta visualització és que l'altura de les barres
representa la mida del nombre.
Així que la més alta és la barra, més gran sigui el nombre.
Shorter la barra, més petit és el nombre.
I si et dones compte, que estem passant la primera iteració d'aquest algorisme,
intercanvi de nombres grans i petits, de manera que el nombre petit ve primer i
el nombre gran va a la dreta.
>> I tan aviat com arribem al final de la matriu de molts més números de set, estem
va a anar de nou al principi.
I anticipar això.
A l'extrem esquerre, que poc home va per intercanviar a un costat, i aquest
procés es repeteix.
Ara aquesta visualització ràpidament es avorrit, així que seguirem endavant i deixar de
, Canvieu el retard alguna cosa molt més ràpid només per ara, una idea de
aquest algorisme.
>> Així que, encara que he accelerar cap amunt, això és com actualitzar el meu processador, la compra d'
un equip nou.
No he canviat fonamentalment el meu algorisme, però de fet pot veure més
clarament que amb els éssers humans, que el gran números estan sortint al cim,
i els números petits estan sortint cap avall a la part inferior.
I ara aquesta cosa ordenada.
I en un a part, a les places, no hi ha només algunes comptabilitat allà per
l'ajuden a explicar la quantitat de comparacions, o quants swaps tenen
en realitat s'ha fet.
>> Bé, anem a provar una de els altres que vam veure.
Permetin-me clic a mena de bombolla aquí, i permetre triar, i aquesta pàgina web sencera
està lliure d'errors.
Acceptem el risc i lo de nou.
Això és.
Així que farem una mena de selecció.
No sé per què el menú apareix per allà.
Anem a apropar a arreglar això bug, canviar-ho a 50.
Ah, farem realitat que molt més ràpid.
Cinc mil · lisegons o menys, i Start.
>> Així que aquesta és la selecció de gènere.
Així que de nou, pensar en el que va fer amb els éssers humans fins aquí.
Vam anar a través de la matriu i seleccionem l'element més petit de nou,
i una altra, i una altra.
Ara afirmo que encara era bastant dolent.
Seguia n al quadrat, més o menys, però era, en el món real, una mica
més ràpid, perquè estava prenent de fet poc menys passos cada vegada.
Però només estem parlant de què?
Potser 40 o més barres d'aquí?
No estem parlant de 40 milions.
Així que no és totalment clar per a mi que era de fet un guany significativa.
>> Permetin-me ara tornar enrere i canviar al nostre tercer algoritme, el qual va ser seleccionar
ordenació per inserció.
I ara és realment errors perquè el menú realment no hauria d'estar allà.
Així que ara anem a retrocedir aquí i començar aquest algorisme.
Whoop, iniciar i aturar.
Així que aquest tipus de compte amb un model bonic a ella, amb el que estem de nou
la inserció dels éssers humans, o en aquest cas, les barres en
la seva ubicació adequada.
I ja ho ha fet abans Em vaig donar la volta.
Però això, també, en teoria, encara és N quadrat.
>> Així que anem a veure si podem resumir aquests com segueix.
Vaig a seguir endavant i només per donar nosaltres una espècie d'una manera comuna de parlar
sobre aquestes coses, permetin-me presentar només una mica de notació aquí.
Estàs a punt de veure una cosa anomenada gran O, ja que és, literalment, un gran
O. I aquesta és una manera de que un equip científic o un matemàtic, fins i tot utilitza
per descriure el temps d'execució d'algun algoritme.
Quants passos que realment necessita?
>> Ara em vaig a avergonyir a mi mateix amb la meva lletra aquí a un moment.
Però m'ho dius seguir endavant i dir que això va a ser gran O per aquí.
I permetin-me presentar a un altre símbol, un omega capital.
Omega serà l'oposada, en essència, de la gran O. Considerant que la gran O
mitjans, en el pitjor dels casos, la quantitat de temps Podria prendre algun algorisme, en
termes de n, omega va a serà la quantitat de temps que podria
tenir en el millor dels casos.
I veurem el que entenem per millor dels casos, en un moment.
>> Així que anem a començar una cosa simple.
Permetin-me començar amb una recerca lineal.
Per tant no classificació.
Anomenarem a aquesta cerca lineal.
I ara, fer una mica de taula de sortir d'això.
I ara, en el cas de cerca lineal, en el pitjor dels casos, la quantitat de passos és
que em portarà a trobar una nombre d'elecció arbitrària?
I hi ha n portes totals o n el nombre total.
Pitjor dels casos.
Quants passos que vaig a haver de prendre per trobar el número 50 en una sèrie
de n portes?
¿I per què?
A causa que pot ser tot el camí cap al final.
Així que igual que Jennifer es va trobar amb el nombre 50 va ser tot el camí, pel que en
el pitjor dels casos cerca lineal és gran O de n, direm.
>> I el millor dels casos, si vostè aconsegueix realment afortunat?
No només va a fer un pas, o un nombre constant de passos.
Així que anem a descriure això com 1.
Així que això és bastant bo.
Ara el que si hem fet alguna cosa com a recerca binària?
Cerca binària Així, en el pitjor dels casos cas, es va emportar la quantitat de temps?
>> [Interrompent VEUS]
>> DAVID J. Malan: Així que en realitat, escoltat en un parell de llocs.
Així que en realitat log n, més o menys, perquè com es divideix la llista en mitja
una altra vegada, i una altra, i una altra, som capaços de per trobar, en última instància, el valor,
si hi és, però hi ha una trampa.
Quina és la suposició que hem de donar per fet de cerca binària?
Ha de ser resolt.
No està resolt, es pot dividir la cosa la meitat una altra vegada i una altra, i vostè
pot anar a l'esquerra, i es pot anar a la dreta, i vostè pot anar a l'esquerra i la dreta, però vostè és
No va a trobar l'element si la llista no està ordenada, perquè
potser et perdis.
Com que la seva heurística, per anar a l'esquerra o cap a la dreta serà defectuós si és
de fet no ordenats.
Així que hi ha una mena de cost ocult per a l'ús d'alguna cosa com això.
>> Ara, anirem a la nostra selecció algoritmes no buscar -
oh, realment anirem en aquest espai en blanc.
Cerca binària en el millor dels casos?
També és 1 si només passa a ser en ple centre de la matriu, o
el mitjà de la guia telefònica.
Ara farem una mena de bombolla.
Així que de nou, ara que estem entrant al tipus, no les recerques.
>> En el pitjor dels casos, la quantitat de passos que van fer reclamació mena de bombolla va a prendre?
n al quadrat.
Així que vaig a dibuixar això.
Oh, la meva lletra es veu encara pitjor quan es preveu que tan gran.
Està bé.
Així que això és n al quadrat.
I en el millor dels casos de l'espècie de bombolla, quants passos es va a prendre?
1, ho vaig sentir.
>> ALTAVEU 1: n.
>> DAVID J. Malan: n, vaig escoltar.
>> ALTAVEU 1: 2.
>> DAVID J. Malan: 2, vaig escoltar.
Escolte 3?
Està bé.
Això he sentit 1, n, 2, però anem a recollir a més, almenys, el primer dels
suggeriments, 1.
No és un mal instint, perquè tipus de segueix un patró aquí.
Però si només es necessiten 1 pas, com en el món podria jo afirmar que la llista
està ordenada, perquè si només es em permet prendre 1 pas, quants elements
vaig poder comprovar realment estar segur?
Bé, només 1, el que significa que hi ha n almenys 1 elements que podrien estar fora de
ordre, i em vaig a la fe després d' mirant que l'element 1
cosa està ordenada.
Així que 1 no és correcte aquí.
Així mínimament, quants Què he de mirar?
>> [Interrompent VEUS]
>> DAVID J. Malan: n menys 1, o en realitat, n, perquè he de mirar cada
joc, assegurant que no és fora de servei.
Però una vegada més, anem a resoldre d'ona nostre mans en els números més petits i
suposen que, quan n es fa gran, són sense interès de totes maneres.
Així que és una mena de bombolla.
I ara, farem aquestes dues últimes.
Selecció de tipus i, a continuació anem a fer l'ordenació per inserció.
I després anem a volar la teva ments amb alguna cosa molt
millor que tots aquests.
Està bé.
>> Quin és el pitjor dels casos s'executa moment de l'ordenació per selecció?
>> ALTAVEU 4: n al quadrat.
>> DAVID J. Malan: plaça n, estic escoltant.
Però per què n al quadrat, intuïtivament?
>> ALTAVEU 4: Perquè ens vam fer.
>> DAVID J. Malan: Perquè ens vam fer.
D'acord.
Bona resposta.
Però, intuïtivament, per què és la selecció tipus n al quadrat?
Què havíem de fer una i altra vegada?
Vam haver mantenir l'exploració a través, són que els més petits, és vostè el
més petit, ets el més petit.
I concedeix, hem estat capaços de prendre n passos, llavors n menys 1, llavors n menys 2.
Però si que tipus de agrega els tot, o emporta-te'l amb tu en la fe que he afegit
ells per endavant, tenim més o menys n quadrat menys alguns números més petits.
Així que vaig a trucar a aquest n al quadrat.
Però amb l'ordenació per selecció de la millor cas, la quantitat de passos és
em portarà?
>> ALTAVEU 5: [inaudible]
>> DAVID J. Malan: És lamentablement sent n al quadrat, oi?
Perquè si estic seleccionant els més petits element, i vam tenir set persones aquí,
L'únic que sé, un cop arribi a la mateixa fi, que he trobat el més petit
nombre, allà on ella va poder haver estat.
Però, com puc trobar la següent nombre més petit?
He de fer una altra passada.
Així que en el millor dels casos, quin és el d'entrada a la selecció de tipus?
És una llista ia tipus, número u, número dos, nombre tres, número quatre.
Però jo sóc un ordinador.
Només puc mirar 01:00 cosa alhora.
No puc ordenar de fer un pas nou com un ésser humà i dir:
ooh, això sembla correcte.
>> Només puc jutjar la correcció de ordenació per selecció, seleccionant el
nombre més petit.
Però fins i tot si trobo el número u en primer lloc, si jo no sé res més sobre
els altres nombres, que no ho faig, tot el que Sé que m'han donat una sèrie
o un conjunt de portes de darrere de la qual estan números, l'única manera que sé que un
era la més petita?
Si aconsegueixo fins aquí i m'adono, maleïda sigui, un era de fet el més petit.
>> Però com llavors determinar que dos és el costat més petit?
En fer la mateixa ineficiència una i altra vegada.
Així que finalment, amb l'ordenació per inserció, com, en el pitjor dels casos,
vam dir que realitza?
Això també és n al quadrat.
¿I què hi ha amb el millor dels casos?
Anem a deixar això com un cliffhanger.
Ens omplirem que la propera vegada en blanc, però primer m'ho dius proposo que
fonamentalment fer millor que tot això, d'acord?
>> Així que pensar per tu mateix el que la inserció tipus serà.
Bé, això no va ser molt dramàtica, perquè jo sóc l'únic
que va veure el canvi.
Wow.
D'acord.
Així que aquí tenim una mica diferent demostració.
Si puc ampliar aquí, veureu que per l'esquerra tenim una mena de bombolla, al
centre tenim ordenació per selecció, i en l'extrema dreta, que tenim alguna cosa
no han mirat encara anomenada fusionar espècie.
Però pensem què hem estat fent aquí fins al moment actual.
Quan Jennifer va arribar per primera vegada a un escenari, ens vam anar a través de la matriu de nombres
una altra vegada, i una altra, amb recerca lineal, i tenim temps de funcionament lineal, big O
de n, per dir-ho.
>> Quan considerem ara la primera setmana de classe, quan havíem divideix i venceràs,
i teníem la guia telefònica llagrimeig, i Jennifer, i col · lectivament
aprofitat aquest coneixement fonamental, que havia repetir-se una vegada i una altra
d'alguna manera tirar, tirar, llençar, la meitat del problema, o
en general, la divisió d'un problema en un mitjà, i després el tractament de la peça més petita de
el problema com conceptualment equivalent a l'altra, que d'alguna manera vam
fonamentalment millor.
Però amb l'ordenació de bombolla, amb la selecció espècie, amb l'ordenació per inserció, hem podrà
hi ha tals idees que Jennifer va fer.
Ens pràcticament només caminem de tornada i successivament un munt de vegades, i
coses pessigat una mica, canviant en aquest ordre, potser
inserir o seleccionar.
Però al final del dia, vaig fer un munt de caminar maldestre d'anada i tornada.
Nosaltres realment no aprofitar alguna cosa intel · ligent com Jennifer li agradava dividir
i la conquesta.
>> Així fusionar espècie, per contra, el que ens no veurà fins a la setmana, que va
aprofitar aquesta idea clau dividint l'entrada, i després reduir a la meitat, i després
reduir a la meitat, i després reduir a la meitat.
I en cada iteració del bucle que, la classificació de la meitat esquerra i la dreta
mitjà, llavors la meitat esquerra de la meitat esquerra, i la meitat dreta de l'esquerra, a continuació,
la meitat esquerra de la part dreta, i la meitat dreta de la meitat dreta.
I repetint una i altra vegada.
>> Així veuràs això visualment, però això és el que ens espera la setmana que ve.
I, en general, quan pensem en un petit mica més difícil de qualsevol problema.
Tenim n al quadrat de l'esquerra, n quadrat al mig, i n
log n a la dreta.
Així que el seu melodrama real.
Ens veiem el dilluns.
>> [Aplaudiments]