>> [Muziek]
>> DAVID J. MALAN: Dit is CS50.
En dit is het begin van week drie.
Dus hebben we een heleboel spannende gekregen dingen te dekken vandaag.
Veel mogelijkheden voor vrijwilligers op het podium.
En uiteindelijk, vandaag de dag is niet om de code op alle.
Maar het gaat over ideeën, en het gaat over algoritmen,
en eigenlijk terugbrengen kennen de lessen van week nul,
waarin recall, we introduceerde dit gedrocht.
En lenen inspiratie van die, te beginnen
oplossen steeds geavanceerdere problemen algoritmisch.
Maar eerst een paar aankondigingen.
Zo een, als je mee wil Personeel en klasgenoten CS50's tijdens de lunch
deze vrijdag, zowel hier als in Cambridge, en in New Haven,
kunt u terecht op de cursus website wanneer een URL te vinden.
Lezing deze woensdag zal hier niet in Sanders.
Het zal alleen online, zodat afstemmen op de website CS50's,
of hier in Cambridge of New Haven ook.
>> En dan probleem set twee is al in uw handen.
Als u nog niet gedoken in nog, laat mij de sterk geformuleerde suggestie bieden
dat, zeker nu, als het probleem stelt voorschot,
je echt wilt nu beginnen, zo niet ploeteren een beetje aan het weekend of voorafgaande
toen ze voor het eerst uit te gaan op Vrijdagen, want je zult
vinden dat ze niet per se steeds langer of meer uitdagende per
se.
Ik denk dat je dat vindt, in algemeen, neigen zij tot ongeveer nemen
rond dezelfde tijd.
Maar het is zeker afhangt de student, en
hangt af van de mentaliteit waarmee je benaderen.
Maar altijd, je gaat te lopen tegen een aantal muur,
en je gaat raken sommige bug, en je bent gewoon
niet van plan om te kunnen krijgen over het op een bepaald punt.
En het is enorm waardevol om te kunnen om weg te stappen, komen de volgende dag terug,
ga naar de kantooruren, post op CS50 Bespreek of iets dergelijks, om daadwerkelijk te krijgen gedeblokkeerd.
Dus hou dat in gedachten.
Beginnend spoedig mogelijk is het beste wat je kunt doen.
Dus hier is waar we begonnen de klasse, meer dan in week nul.
En kunnen we een vrijwilliger hier om me te helpen microfoons vinden?
OK.
Opstaan ​​al.
Kom op maximaal.
Denk dat dat is hoe het gaat werken.
Hoe heet je?
ALAN ESTRADA: Alan Estrada.
DAVID J. MALAN: Alan Estrada.
Kom op maximaal.
Leuk je te ontmoeten.
ALAN ESTRADA: Leuk je te ontmoeten.
DAVID J. MALAN: En u was hier bij ons in week nul, natuurlijk.
ALAN ESTRADA: ik was.
Ik was.
>> DAVID J. MALAN: Dus zou je kunnen gaan vooruit en vind voor ons Mike Smith,
zo snel als je kunt?
Zo snel als je kunt.
Letterlijk scheuren van het probleem in de helft als je nodig hebt om.
>> ALAN ESTRADA: Um.
DAVID J. MALAN: Letterlijk scheuren van het probleem in de helft.
>> ALAN ESTRADA: Oh.
Mm.
Heel goed.
>> DAVID J. MALAN: OK.
Goed.
Dankjewel.
ALAN ESTRADA: Zeer goed.
OK.
>> DAVID J. MALAN: En nu, je hebt het teruggebracht
de helft van de omvang van het probleem.
Nu, we zijn tot een kwartaal.
Bent u aandacht te besteden aan welke kant we houden?
>> [Lacht]
>> ALAN ESTRADA: Ja, ik think--
>> DAVID J. MALAN: Wat sectie zijn we?
ALAN ESTRADA: halsdoeken, zo.
>> DAVID J. MALAN: OK.
Maar Mike Smith gaat om na Uitlaten.
So--
>> [Lacht]
>> Prima.
ALAN ESTRADA: Waar zijn we op zoek?
DAVID J. MALAN: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. MALAN: Nu, we zijn in chirurgische.
Nu, artsen.
Now--
>> ALAN ESTRADA: Let's- laten we gaan met echte.
Real.
>> DAVID J. MALAN: Real.
OK.
Als u nodig hebt Real.
Nu, welke manier is Mike Smith?
>> ALAN ESTRADA: Op deze manier.
>> DAVID J. MALAN: Welke manier?
ALAN ESTRADA: Wacht.
M is-- toch?
We begonnen met--
>> DAVID J. MALAN: Ja.
Ze zijn vertrokken.
Je hebt gelijk.
>> ALAN ESTRADA: Ja.
>> DAVID J. MALAN: Dus Mike's hier.
ALAN ESTRADA: Wat?
>> [Lacht]
>> Slecht voorbeeld, jongens.
Sorry.
DAVID J. MALAN: Dit zal je leren je te springen uit je stoel.
>> ALAN ESTRADA: Oh.
Oh.
Ik heb je.
Oh.
Dit is-- OK, ik heb je.
Smith hier?
>> DAVID J. MALAN: Smith, dank je.
Dus ik zal blijven opzoeken Smith?
>> ALAN ESTRADA: Oh, ja.
Nee nee nee.
O nee.
Dit is van mij.
>> DAVID J. MALAN: Oh, heb je Smith.
OK.
>> ALAN ESTRADA: Ja, ik Smith kreeg hier.
Sorry, jongens.
Ik dacht dat we Michael-- waren op zoek naar Michael.
Sorry.
>> DAVID J. MALAN: Het is OK.
Oké, nu zijn we in Paccini and Sons.
>> ALAN ESTRADA: Paccini en zonen.
DAVID J. MALAN: Alleen jij en ik zijn in deze.
OK.
Vind ons Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> DAVID J. MALAN: Smith.
We zijn in R voor onzin.
ALAN ESTRADA: Onzin.
Oh.
Dit gaat een tijdje duren.
>> [Lacht]
DAVID J. MALAN: Schoenen.
We zitten in de schoenen.
>> ALAN ESTRADA: Nu zijn we gonna--
>> DAVID J. MALAN: Nice.
ALAN ESTRADA: Which--
[Lacht]
Oh, dit is geweldig.
[Lacht]
>> DAVID J. MALAN: Het is OK.
>> ALAN ESTRADA: Oh, dit is goed.
Ik denk niet dat ik ga hebben PSAT vrienden na dit.
DAVID J. MALAN: Goed.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
DAVID J. MALAN: OK.
Dus laten we scheuren dit in de helft.
Het is ok.
Deze eindigt slecht toch, omdat Mike Smith zal niet in de gele pagina's.
>> ALAN ESTRADA: Aw.
>> DAVID J. MALAN: Nee, het is OK.
Maar laten we doen alsof Hij is op deze pagina.
Dus nu, je hebt het probleem teruggebracht op één pagina, en we vonden Mike Smith.
>> [TOEJUICHENDE]
OK, dank je.
OK.
Dat was buitengewoon.
Maar het was nog sneller dan lineair zoeken,
waarin beginnen we bij de begin van het boek,
en we bewegen weg van links naar rechts, uiteindelijk naar Mike Smith.
En dus, als het telefoonboek hadden misschien 1.000 pagina's,
misschien zou hebben genomen ons 10 of zo pagina tranen.
>> Maar je kan hebben leveraged raakte een veronderstelling
Tijdens dat alles, dat wil zeggen dat het telefoonboek van tevoren was wat?
Publiek: Gesorteerd.
DAVID J. MALAN: Het is opgelost.
Rechts?
Het is alfabetisch gesorteerd, zodat dat al die namen en nummers
worden gesorteerd van A tot de Z en alfabetische daartussen.
Maar vandaag, nu vragen we de vraag, goed,
hoe heeft Verizon of de telefoon bedrijf te krijgen in die staat?
>> Want het is één ding om gebruik te maken die veronderstelling, en dus
een probleem met een op te lossen algoritme efficiënter.
Maar we nooit echt vroeg in week nul, goed,
hoeveel heeft het gekost Verizon of iemand anders
dat telefoonboek in gesorteerde volgorde te krijgen?
>> Rechts?
Het maakt niet uit of opzoeken Mike Smith
is super snel, als het neemt je een jaar om de pagina's in eerste instantie afstand.
Rechts?
Je kan net zo goed te ziften door middel van een gerandomiseerde telefoonboek,
Als het gaat super te zijn duur te sorteren.
Dus als we een andere vrijwilliger kan hebben.
Laten we eens een kijk omhoog hier bij hoe we might-- kom op up-- hoe
we kunnen gaan over het sorteren van deze.
>> En als Jordan kon eigenlijk bij ons hier op het podium.
Kom op voor slechts een moment.
Hoe heet je?
CAROLINE: Caroline.
DAVID J. MALAN: Caroline, kom op up.
En je zult worden samengevoegd door mij en Jordanië hier.
Caroline, dank je.
Prima.
Dus wat we hier hebben voor Caroline is 26 blauwe boeken
dat FAS gebruikt te beheren bepaalde eindexamen.
Deze worden steeds moeilijk te vinden, maar wat we hebben gedaan op voorhand
is dat we iemands naam hebt gezet aan de voorzijde van elk van deze,
maar we hebben het simpel gehouden door Vervolgens blussen volledige namen.
Dus zouden we de persoon te zetten met de naam L, D, J, B, helemaal A tot Z,
maar ze zijn in willekeurige volgorde.
En dus als je zou doen, praat je weg door het probleem als je
doe het, kunt u doorgaan en sorteren van deze voor ons, van A tot Z.
>> Publiek: OK, dus L is als het midden.
C begint.
B. J voordat L. B, Q.
>> DAVID J. MALAN: Houd die dacht een seconde.
Want anders is dit slechts interessant voor jou, mij, en Jordanië.
Daar gaan we.
PUBLIEK: [onverstaanbaar].
R.
DAVID J. MALAN: OK.
Wat ben je aan het doen?
>> CAROLINE: M komt na O.
>> DAVID J. MALAN: OK.
>> CAROLINE: O.
DAVID J. MALAN: O, goed.
>> CAROLINE: E.
>> DAVID J. MALAN: E, F. Yeah.
>> CAROLINE: T, U, V.
>> DAVID J. MALAN: V, T, U, V. Zo ziet eruit alsof je making-- blijven gaan.
Het lijkt erop dat je het maken van een grote stapel hier,
en een soort van een grote stapel daar.
Dus de eerste helft van het alfabet, tweede helft van het alfabet.
OK.
Goed.
Soort van het splitsen van het probleem in twee.
M, N, X. Yeah.
CAROLINE: K.
DAVID J. MALAN: OK.
K. Dus je soort selecteren ze een na de ander,
zetten het links of rechts, of Z's gaan op de vloer.
OK.
>> CAROLINE: Z gaat op de vloer.
>> DAVID J. MALAN: OK.
Y gaat op de vloer.
Nu kunnen we X. zetten
>> CAROLINE: G.
DAVID J. MALAN: G's naar links.
S gaat rechts.
Oké, A gaat helemaal naar links.
>> CAROLINE: A, B, C, D.
>> DAVID J. MALAN: Nu, goed.
We hebben gekregen, B, C W's gaan daar beneden.
Oké, T.
>> CAROLINE: H, I, J
DAVID J. MALAN: H, I, J. Good.
CAROLINE: In het centrum, ik gonna--
DAVID J. MALAN: OK.
Dus nu gaan we soort samenvoegen van deze verschillende palen.
Dus A tot en met C, dan zie ik D en E en F, en G en H en I. Nice.
J, K. En dan, deze stapel is ondersteboven, maar dat is OK.
Tuurlijk.
We kunnen snijden sommige bochten.
OK.
En dan moeten we W, X, Y, Z.
>> CAROLINE: Ja.
>> DAVID J. MALAN: Excellent.
Dus een grote dank aan Caroline voor het sorteren daarvan.
>> [TOEJUICHENDE]
>> Dankjewel.
Hartelijk bedankt.
Dus nu laten we eens kijken voor een moment hoe Caroline ging over dat te doen,
en wat precies wij konden to-- hoe we
waren in staat om op te lossen dat probleem toen we waren gewoon
krijgt een hele hoop willekeurige ingangen.
>> Nou, het lijkt erop dat er was een beetje een systeem is er?
Rechts.
Zodat de eerdere brieven in het alfabet, zij
was zetten naar links, en de later letters in het alfabet,
ze was het in de juiste.
En zodra ze gevonden sommige proximale brieven, degenen
die naar naast elkaar Ze zouden die op orde te brengen.
En dus we soort had deze kleine stapels gesorteerde inputs optreedt.
>> En dat is dus heel graag wat de meesten van ons mensen zou doen.
We zouden een soort van ziften doorheen, en we zouden soort hebben een mechanisme.
Maar het zou moeilijk zijn om te schrijven het beneden in een formule per se.
Het voelde een beetje meer organische dan dat.
Dus laten we kijken of we kunnen nu gebonden het probleem met minder inputs.
>> In plaats van 26, laten we iets wat veel minder doen
met alleen maar zeggen, zeven, achter deze deuren, om zo te zeggen.
Zijn er slechts zeven nummers?
En als het doel nu hand om een ​​waarde te vinden,
laten we eens kijken hoe efficiënt we kunnen gaan doen.
En laten we kijken of we kunnen nu beginnen met een aantal nummers passen,
of een formules waarmee beschrijven de efficiëntie van onze telefoonboek
algoritme, onze examen boek algoritme, en meer in het algemeen, het vinden van informatie.
>> Dus voor deze, laat me doorgaan, en op het aanraakscherm hier,
zetten een webbrowser die heeft juist deze zeven deuren.
En als we konden een ander krijgen vrijwilliger te komen op hier,
Ik heb deze zelfde deuren zetten hier.
Quick vrijwilliger.
>> Dit een-- demo gaan een sneller en sneller nu.
Kom maar naar beneden.
Hoe heet je?
TREVOR: Trevor.
>> DAVID J. MALAN: Trevor?
Oké, Trevor, kom naar beneden.
Dus Trevor heeft hier vrijwillig aan doe een soortgelijk probleem, maar een die
beperkter in omvang, en dat gaat om ons in staat om te proberen om nu te formaliseren
de werkwijze voor het sorteren van deze nummers.
>> Dus Trevor, leuk je te ontmoeten.
Dus hier is een array, om zo te spreken, een lijst van zeven deuren.
Ga je gang en vinden ons de nummer 50.
En dan na het feit, vertel ons hoe je het gevonden.
Moet be-- goed.
Ja, dit is het hier?
Oh Oh.
OK.
U hebt geklikt die ene.
Goed.
>> En goed.
Nu u hebt geklikt die ene.
En laat me je de microfoon, zodat je het in slechts een moment.
Ga je gang en klik op de naast de deur die u van plan bent.
Ja goed.
TREVOR: Kan ik unclick een deur?
DAVID J. MALAN: Nee, je kan niet unclick.
TREVOR: OK.
Deze.
DAVID J. MALAN: Waar wil je heen?
Welke?
>> TREVOR: Dat één.
>> DAVID J. MALAN: No.
>> TREVOR: OK.
Deze.
>> DAVID J. MALAN: Ja.
Dat was goed.
Prima.
Dus wat was uw algoritme of procedure om dit te doen, Trevor?
>> TREVOR: Ik ging gewoon door middel van deuren totdat ik vond een 50.
DAVID J. MALAN: OK.
Excellent algoritme.
Dus dat is prima.
Want in feite, als ik onthullen wat is Achter deze twee deuren, wat
we zullen hier is dat we hebben alleen willekeurige ingang.
Dus dat was eigenlijk als goed als je kon krijgen.
En in feite, kun je beter dan kreeg uitputtend zoeken de hele reeks,
omdat het echt zou zijn geweest pech als je het nummer had geraakt
50 op het laatst de deur.
Maar wat als we in plaats daarvan gaf je een veronderstelling.
Stel dat ik een soort van alle deze deuren rond,
zodat u de aantallen naargelang deze tijd,
maar deze keer is het eigenlijk een different-- dit keer,
het is eigenlijk gesorteerd voor u.
En nu het doel bij de hand wordt het nummer 50 geraakt.
>> TREVOR: OK.
>> DAVID J. MALAN: Wat is algoritme gaat worden?
>> TREVOR: Nou, als het naargelang, het is ofwel gaan
om be-- als grootste tot de grootste, afdalen, zal het de eerste te zijn,
of als het is het tegenovergestelde, het zal de laatste zijn.
Dus ik zal gewoon raak deze deur, en dan gewoon tik op de laatste deur.
DAVID J. MALAN: Excellent.
Prima.
Dus vonden we het nummer 50.
Dus zodra je wist zij waren gesorteerd, we
konden deze veronderstelling hefboomwerking.
Zodat ze te veel op het telefoonboek voorbeeld.
Zodra je hebt, zelfs met een klein probleem als dit,
Uw input voorgesorteerd, kunnen we de waarde eigenlijk vinden aantoonbaar
efficiënter.
>> En ik heb je als het niet vertellen naargelang klein tot groot, of groot naar klein,
en dus het was zeer redelijk te beginnen aan één uiteinde of het andere
om daadwerkelijk vinden dat streefwaarde.
Dus dank aan Trevor ook.
En ik zal propose-- mooi gedaan.
We hebben een kleine clip, eigenlijk, dat is een van onze favoriete momenten in CS50,
waarbij soms zijn deze demo's niet helemaal volgens plan.
En inderdaad op dit moment, ik trok de verkeerde-interface
waarmee het aanraakscherm te gebruiken.
Dus dat was mijn schuld daar.
>> Dus zal dit voor volgend jaar de clip als
waarom ik klikken op mijn eigen scherm.
Maar laten we eens een snelle blik wat vorig jaar gebeurde
met Jay, die kwam, veel zoals Trevor hier vrijwillig,
en in deze korte clip, zie je hoe deze zelfde demo niet helemaal
onthullen dezelfde lessen.
[VIDEO AFSPELEN]
-Alle Ik wil dat je nu doen is te vinden voor mij, en voor ons,
echt, het nummer 50 één stap tegelijk.
>> -Het Nummer 50?
>> -Het Nummer 50.
En je kunt laten zien wat er achter elk van deze deuren
simpelweg door aan te raken met een vinger.
Verdomme.
>> [Lacht]
>> [END AFSPELEN]
DAVID J. MALAN: Dus dat heel goed ging.
Dat waren de ongesorteerde deuren.
En Jay, natuurlijk vond het allemaal te snel.
Trevor heeft een veel betere baan in termen van een leermoment,
zo te zeggen, dit jaar duurt langer om het te vinden.
Natuurlijk, dan gaven we Jay een tweede kans,
waarbij wij naargelang de deuren, net zoals we deden voor Trevor,
en Trevor deed super goed deze tijd.
Maar Jay deed het half zo snel.
[VIDEO AFSPELEN]
-het Doel is nu om ook vinden wij het getal 50,
maar doe het algoritmisch, en vertellen ons hoe je gaat over.
>> -OK.
>> -En Als je het te vinden, houdt u de film.
Als u niet vinden, geef je terug.
>> -man.
>> Oh!
>> - [Onverstaanbaar] OK.
Dus ik ga naar de uiteinden controleren eerst of there's-- te bepalen Oh.
>> [Applaus]
>> [END AFSPELEN]
DAVID J. MALAN: OK.
Dus sorteren deuren duidelijk leidt tot meer efficiëntie.
En ja, twee keer zo snel is wat ik daar bedoelde.
En zo Jay geluk kregen beide keren.
En hij kreeg ook geluk dat de laatste jaar, bestelde ik een aantal Blu-ray-schijven
om daadwerkelijk te geven.
Het spijt me dit jaar, we niet dezelfde zijn, Trevor.
Maar beter nog was een paar jaar terug.
En sommigen van jullie misschien weten collega, Sean, die toen hij in CS50 was,
werd uitgedaagd met de exacte hetzelfde probleem, zij het in SD,
als je snel zult zien, terug in de dag.
En je zult zien dat niet alleen hij iets langer duren dan Jay,
iets langer dan Trevor, was eigenlijk dit prachtige kans
bijna iedereen in het betrekken menigte a la Price is Right, het stimuleren
hem naar het nummer dat we op zoek waren te vinden.
Laten we. neem snel een kijkje.
>> [VIDEO AFSPELEN]
>> -OK.
Dus je taak hier Sean, is het volgende.
Ik heb achter deze verborgen deuren van de nummer zeven.
Maar weggestopt in een aantal van deze deuren evenals zijn andere negatieve getallen.
En je doel is om na te denken van de bovenste rij getallen
als onder array of gewoon opeenvolging van stukjes papier
met cijfers achter hen.
En je doel is, alleen met behulp van de top matrix hier, vind ik het getal zeven.
En we vervolgens naar kritiek hoe je het gaan doen.
-Prima.
-Zoek Ons de nummer zeven, alsjeblieft.
Nee.
Vijf, 19, 13.
>> [Lacht]
>> Het is geen strikvraag.
Een.
>> [Lacht]
Op dit punt, je score is niet erg goed, dus je kan net zo goed blijven gaan.
Drie.
>> [Lacht]
>> Ga door.
Eerlijk gezegd, ik kan het niet helpen, maar vraag me af wat je ook denkt over, so--
>> [Lacht]
Alleen de bovenste rij, dus je hebt drie links.
Dus vind ik zeven.
>> [Lacht]
17.
Zeven.
>> [Applaus]
>> Prima.
>> [END AFSPELEN]
>> DAVID J. MALAN: Dus we konden bekijk deze hele dag lang.
En natuurlijk, sommige demo's van dit jaar misschien
Nu zal eindigen in next video jaar ook.
Dus laten we nu eigenlijk focus op de algoritmen
hier, en kijken of we kunnen niet nu beginnen te formaliseren
hoe we kunnen gaan over het krijgen van onze data in deze staat dat het sorteren,
zodat uiteindelijk, kunnen we eigenlijk doorzoeken efficiënter.
En hoewel we gaan tamelijk kleine datasets gebruiken,
net als de acht nummers die we hier hebben op het bord,
uiteindelijk dezelfde ideeën zou kunnen gelden tot 1000 ingangen miljoen ingangen,
4000000000 inputs, omdat de algoritmen zullen in wezen hetzelfde zijn.
>> En dus dit is onze laatste kans voor de vrijwilligers van vandaag,
maar misschien wel het meest betrokken is, waarvoor we nodig acht vrijwilligers
om te komen en lopen ons door de proces van het sorteren van wat zal binnenkort
op deze muziek staat hier.
Laat me hier start.
>> Zodat men in de turquoise-- groen is het?
Bent u begaan?
Twee.
Kom maar naar beneden.
OK.
Drie.
Four.
Laat mij-- OK, vijf.
Je bent door je vriend genomineerd.
Zes, zeven en acht.
Kom op maximaal.
Prima.
Heel erg bedankt.
Kom op maximaal.
>> Prima.
Dus wat we hebben hier-- en dit is een van de lastiger degenen,
aangezien dit humor vereisen dat u me voor slechts een beetje tijd.
Je moet nummer één.
Hoe heet je?
>> Annan: Annan.
>> DAVID J. MALAN: Annan.
David.
Hoe heet je?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph, je bent nummer twee.
>> SERENA: Serena, nummer drie.
Stefan, nummer vier.
CYNTHIA: Cynthia.
DAVID J. MALAN: Cynthia, nummer vijf.
[Onverstaanbaar]
DAVID J. MALAN: [onverstaanbaar].
David, nummer zes.
MATT: Matt.
DAVID J. MALAN: Matt's nummer zeven.
En?
>> WAVERLY: Waverly.
>> DAVID J. MALAN: Waverly, nummer acht.
Prima.
Als u could-- whoops.
Als je al, als je eerste uitdaging, er
zijn acht lessenaars Hier tegenover het publiek.
Als je je nummers op kon zetten Deze lessenaars zodanig
dat zij onmiddellijk boven het dezelfde nummers op het bord.
Dus maak jezelf eruit dat door het zetten van uw nummers op deze muziek
hier staat.
Uitstekende dusver.
>> Excellent.
OK.
Dus nu gaan we naar de vragen vraag in een paar verschillende manieren.
Hoe kunnen we gaan over het sorteren deze mensen hier?
Want we hadden een paar benaderingen eerder, waarbij wij waren
soort die twee emmers.
En dan over het algemeen waren we patchwork dingen samen.
Zodra we zagen twee nummers dat behoorde samen,
We zetten ze samen.
Twee brieven die bij elkaar horen.
>> Maar laten we eens kijken of we kan dit niet formaliseren,
zodat we uiteindelijk sommige pseudo-code die u wilt,
waarmee u deze problemen op te lossen.
Dus nu ben ik op zoek op deze nummers in.
En ik zie een hele hoop fouten.
Uiteindelijk wil ik een op de acht links en rechts.
>> En dus ik ben op zoek naar deze twee, vier en twee.
En wat is het probleem, natuurlijk?
Ja.
So.
Twee natuurlijk komt voor vier, dus weet je wat?
Laat me eerst een hebzuchtige aanpak, als je wil, net als probleem
set een-- als u zich herinneren van de Standard Edition van Probleem Set One,
waar ik alleen lokaal het probleem op te lossen dat is hier voor mij
en zie waar het leidt me.
>> OK.
Dus twee en vier, laat me gaan vooruit en net swap jullie twee.
Als je fysiek kunt bewegen uzelf en uw papieren,
Ik lijken te hebben gekregen van de lijst in een betere staat.
>> Nu, ze zijn goed.
Ik ga om verder te gaan, vier en zes, ziet er goed uit.
Geen probleem.
Zes en acht, OK.
Acht en een ander probleem.
Want wat waar is ongeveer acht en één?
Komt men voor acht, en dus wat moeten we doen?
Laten we wisselen deze twee.
Één en acht.
En nu ga ik om door te gaan.
Ik ga om te blijven kijken vooruit.
En laten we zien wat er gebeurt.
Acht en drie, van Natuurlijk, niet in orde.
Laten we swap.
Acht en zeven, natuurlijk.
Buiten de orde.
Laten we swap.
Acht en vijf, natuurlijk, laten we swap.
Prima.
De lijst wordt gesorteerd.
ja?
>> OK, natuurlijk niet.
Maar het is een beetje beter, toch?
Omdat kennisgeving wat er is gebeurd.
Elke keer uitgevoerd we een swap, een kleiner aantal soort doorgedrongen op die manier,
en een groter aantal doorgesijpeld deze manier, of we zullen
beginnen zeggende geborreld aan de links of naar rechts borrelen.
>> Nu, het is niet genoeg, omdat in het beste geval een aantal zou kunnen
een plek zijn verhuisd vooruit, of in het slechtste geval,
een getal misschien verhuisde één plek verder.
Zodat je weet wat dit soort gewerkte vrij goed tot nu toe.
Laat me proberen het gewoon opnieuw.
Twee en vier, ze zijn OK.
Vier en zes, ze zijn OK.
Zes en één, buiten de orde.
Dus laten we ruilen jullie twee.
En nu, ziet het probleem van de begint weer beter een beetje te krijgen.
Zes en drie, buiten de orde.
Laten we ruilen jullie twee.
Zes en zeven, je goed bent.
Zeven en vijf, natuurlijk, buiten de orde.
Zeven en acht, in orde.
En nu, zou ik moet doe dit een paar keer.
En in feite, denk voor jezelf misschien hoeveel keer maximaal
misschien moet ik heen en weer te lopen?
>> We zullen terug naar die komen.
Dus twee en vier zijn nog steeds OK.
Vier en één, nope.
Dus, laten we swap.
En nogmaals, merken visueel één is een soort van borrelende
aan de linkerkant, waar het zou moeten zijn.
Vier en drie swap.
Vier en zes.
Zes en vijf swap.
Zes en zeven.
Zeven en acht zijn goed.
>> Goed.
We krijgen nog beter.
Dus laten we zien.
Nu hebben we twee en één.
Uiteraard wisselen.
Twee en drie, drie en vier, vier en vijf, zes en zeven, zeven en acht.
Goed.
En weet je wat?
Want ik maakte een verandering daar, Laat mij u een sanity check.
Laat me gaan de hele weg terug naar het begin.
OK.
Eén, two-- yup, zie je?
Er iets mis was.
Drie, vier, vijf, zes, zeven, acht.
En in deze laatste pas, zijn je comfortabel met mijn nu
beweerde dat het wordt gesorteerd?
OK.
Visueel, dat is absoluut waar.
Maar functioneel is, wat heb ook toevallig
in dat laatste pas waarmee je om te bevestigen dat deze lijst is inderdaad
naargelang?
>> Wat heb ik gedaan of dit laatste pas niet doen?
Publiek: Er waren geen veranderingen.
DAVID J. MALAN: Sorry?
Publiek: Geen wijzigingen.
DAVID J. MALAN: Er waren geen wijzigingen.
Dus het zou stom van me te zijn dat doet hetzelfde algoritme weer
als ik geen maakte verandert het eerst.
En de staat is niet veranderd.
Zeker, ik ben niet van plan om te maken elke verandert de tweede keer.
En ja, het is nu veilig om te zeggen, is de lijst sorteren.
>> Inderdaad is dit nu iets dat we in het algemeen
oproep bubble sort, waarbij paarsgewijs, je fouten weer te corrigeren,
en opnieuw, en opnieuw, en u houden heen en weer,
en heen en weer, totdat je maken geen dergelijke swaps, op welk punt
u kunt er zeker van zijn, ja, ik afgewerkt vaststelling van alle fouten.
Laten we het resetten en probeer een andere aanpak.
Als jullie terug kon gaan naar de volgorde waarin u een ogenblik geleden,
die eruit zagen als deze.
Nu, laten we eens een aanpak een weinig meer als het examen boek,
waarbij we voortdurend waren het selecteren van de letter van het alfabet
dat we soort wilden te behandelen volgende.
Misschien was het een grote brief, zoals A, of een lage letter Z.
>> Dus iedereen is terug in deze volgorde.
En nu laat me dit te doen.
Laten we eens kijken ik weet dat ik heb acht nummers hier.
Ik ga om te gaan en gewoon doelbewust selecteren
de kleinste elementen.
Rechts?
Dit lijkt ook intuïtief.
Waarom heb ik niet de kleinste vinden element, het zetten waar het behoort,
krijgen dan de volgende kleinste element, zet waar het behoort, en gewoon herhalen.
>> Omdat intuïtief, dat zou ook moeten werken.
Zo vier, dat is een vrij klein aantal.
Ik ga om te onthouden waar dit is.
Even wachten.
Two kleiner.
Laat me nu herinneren waar twee is, en vergeet vier.
We zullen later gaan met dat.
Zes, ik ben niet geïnteresseerd.
Acht, ik ben niet geïnteresseerd in.
Is mijn nieuwe kleine aantal.
Dus ik ga om te onthouden waar men is.
Drie, niet geïnteresseerd.
Zeven, niet geïnteresseerd.
Vijf, niet geïnteresseerd.
>> Dus zonder te vallen het podium dit jaar,
Ik ga nummer grijpen een-- en wat was je naam ook alweer?
>> Annan: Annan.
>> DAVID J. MALAN: Annan.
En als je zou kunnen samen met mij op het begin van de lijst,
laten we u waar u behoort.
Unfortunately-- wat is uw naam?
>> STEFAN: Stefan.
>> DAVID J. MALAN: Stefan is in de weg.
Dus voordat Stefan lost dit probleem, wat moeten we doen?
Wat doen we met Stefan?
>> PUBLIEK: [onverstaanbaar].
DAVID J. MALAN: OK.
Dus we konden doen.
We konden soort nemen Stefan en zijn vier, en zet ze gewoon in een variabele
en vast te houden voor enige tijd,
waardoor ruimte voor nummer één.
En dat is niet slecht.
Ik kon voorstellen, waarom niet we gewoon Stefan hier?
Waarom zou dit in strijd zijn één van de ideeën die we begonnen
over de vorige keer, afgelopen week?
Ja?
>> PUBLIEK: [onverstaanbaar].
>> DAVID J. MALAN: Er is geen index voor het.
Als u denkt dat dit inderdaad als een array, dit is als negatief,
dus er is geen geheugen eigenlijk hier als dit inderdaad een array,
zoals wij verklaarde vorige week in collegezaal.
Dus we moeten dit niet doen.
We zouden het op te slaan in een variabele.
>> Of weet je wat?
Ik hoorde iemand anders suggereren.
Wat kunnen we doen met Stefan?
Waarom niet we hem gewoon uit te zetten en zet hem dan waar de nummer één was.
Dus als je wilt om daar te gaan.
Inderdaad is dit een vrij goede oplossing.
Nu aan de ene kant, ik heb soort van maakte het probleem nog erger.
Vier is nu verder weg van waar het zou moeten zijn.
Het moet in de richting van deze helft.
>> Maar weet je wat?
Dat zou pech geweest.
Misschien nummer acht was hier.
En ja, misschien zouden we hebben gekregen geluk,
en geduwd acht dichter bij het einde.
Dus in het einde van de dag, het vriendelijk van alle gemiddelden uit.
We hoeven niet over vier schelen.
Alles wat ik zorg over nu is selecteren van het kleinste element.
>> En nu, wat ik ga naar doen is vergeet nummer één
permanent, omdat ik weet dat de lijst achter me is nu opgelost.
Dus mijn lijst was eerder groot acht.
Nu, het is van groot zeven.
Dus mijn probleem is om kleinere, alhoewel lineair.
Dus nu ga ik het selecteren huidige kleinste element, twee.
Zes, acht, vier, drie, zeven, vijf.
Dat was de kleinste element.
Dus wat moet ik doen met-- Wat was je naam ook alweer?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph?
We gaan naar Joseph in de plaats te verlaten.
Nu, ik ga doen alsof dat deze jongens zijn-- goed,
Ik weet dat deze twee zijn al naargelang.
Laten we nu concentreren op de rest van de lijst.
Zes is de kleinste stroom.
Acht is groter.
Vier is nu de huidige kleinste.
Drie is nu de huidige kleinste.
En nu, ga ik drie te selecteren, wie is-- wat is je naam ook alweer?
SERENA: Serena.
DAVID J. MALAN: Serena, als je zou kunnen pak je nummer en swap met--
Kalsang: Kalsang.
DAVID J. MALAN: Kalsang.
Kom terug, en we zijn gaat verwisselen die twee.
En nu, laten we dit op de automatische piloot.
Ik ga om te gaan en laat het aan jullie naar de volgende kleinste elementen te selecteren.
Dun, dun, dun, dun.
Nummer vier, wat moet je doen?
Excellent.
Nu, ik ga nog een keer te maken.
Dun, dun, dun, dun.
Ik zie vijf is de kleinste.
Nu, ga ik neem nog een pass.
Dun, dun, dun, dun.
Zes is het kleinst.
Goed.
Zeven is het kleinst.
Geen verandering.
Acht is het kleinst.
Gedaan.
>> Dus wat we hebben net gedaan door iteratief het selecteren van een element na elkaar
wordt de uitvoering van iets dat we gaan formaliseren als selectie sorteren.
En het is misschien wel eenvoudiger te leggen,
in die letterlijk alles wat je wilt doen is gewoon blijven
heen en weer door de lijst selecteren, de volgende kleinste element,
totdat je klaar bent.
>> Dus het is nog eenvoudiger, misschien intuïtief, dan vorig.
Laten we proberen een laatste.
Als jullie jezelf kunnen resetten in de volgende posities
een laatste keer, laten we eens kijken of we kunnen niet Nu formaliseren een andere aanpak.
In feite, zou iemand daar willen voorstellen
hoe anders zouden we dat doen?
Zonder gooien out buzzwords of sorteren van de antwoorden die reeds bekend zijn,
gewoon intuïtief, wat kunnen we doen?
>> PUBLIEK: [onverstaanbaar].
DAVID J. MALAN: Ja.
Dus er is een aantal grote intuïtie daar.
Goede dingen lijken tot nu toe gebeuren in de informatica als we verdelen
en verover het probleem van de te verdelen het in de helft en half en half.
En zo ja, we kunnen gaan doen.
En in feite, dat gaat worden, zullen we zie, een van onze beste oplossingen nog.
Maar laten we terug naar die vóór lang.
In feite, we gaan doen dat een beetje later deze week.
Wat kunnen we doen om dit op te lossen?
Dus iedereen is hier in schijnbaar willekeurige volgorde.
Weet je wat?
In plaats van heen en weer, heen en weer, heen en weer
elke keer, dit voelt als Ik ben bezig met een veel wandelen.
Waarom heb ik niet alleen beginnen bij het begin van de lijst,
en gewoon vier waar het hoort?
Dus laat ik neem aan dat voor het moment dat mijn lijst is alleen het eerste element.
Wordt vier naargelang op dit moment in de tijd, Als alles wat ik zorg over is alles hier?
Dit is een soort van triviaal waar, toch?
Net als de lijst met één nummer, en dat nummer vier is uiteraard opgelost.
>> Dus laat me gewoon bepalen dat deze lijst wordt gesorteerd.
Maar nu heb ik de rest van deze lijst.
Dus nu, ik tegenkom twee.
Waar doet twee natuurlijk behoren met betrekking tot vier?
Voordat vier.
Dus wat kan ik hier doen?
Wat is je naam ook al weer?
>> JOSEPH: Joseph.
>> DAVID J. MALAN: Joseph, Als je terug kon stappen
voor slechts een moment met uw nummer.
En nu, wat moet Stefan hier doen?
Laten we verschuiven Stefan hier.
En nu, laat Joseph hier komen.
En nu, laat me zeggen dat alles hier is gesorteerd.
Dus, soortgelijk resultaat, maar een fundamenteel andere benadering.
Ik heb niet eens gekeken wat daar beneden.
Ik blijf gewoon het nemen van de elementen als ze overhandigd aan mij,
en omgaan met hen.
>> Dus nu zie ik nummer zes.
Waar komt nummer zes behoort?
We hebben twee, vier, zes.
Precies waar ze nu is.
Dus laten we dat alleen al, en nu beweren dat dit deel van de lijst
is nu opgelost.
En dus, dit voelt fundamenteel anders in dat ik ben gewoon
bewegen door de lijst hier lineair, en ik ben nooit een verdubbeling van terug.
Ja.
Prima.
Dus acht, waar moet je thuis?
Hier.
Perfect.
Dus nu, één.
Oh Oh.
Dit voelt als het is zal duur.
Nu in het vorige algoritme, Ik ruilde mensen.
Dus ik zou hem de hele weg te zetten op het begin, maar dan verplaatst Joseph.
Maar als ik Joseph bewegen, nu wat is er mis zijn?
>> Nu, ik heb een soort van undone-- Ik heb genomen een stap vooruit en dan
een stap terug, want nu Joseph zou zijn buiten de orde.
Dus laten we dit doen.
Als je nummer een zou kunnen nemen en stap terug voor slechts een moment.
Hoe kunnen we put-- wat was je naam ook alweer?
>> Annan: Annan.
>> DAVID J. MALAN: Annan in de plaats?
Wat er moet gebeuren met respect twee, vier, zes en acht?
Ze moeten allemaal te verschuiven.
Dus als acht zou willen verschuiven Eerst dan zes dan vier, dan twee.
En dan Annan, als je wilt zoals hier in te komen, goed.
Maar hier, hebben we net soort betaalde een prijs
op een ander punt in het algoritme.
Overwegende dat de laatste keer met de selectie sorteren en zelfs bubble sort,
Ik ga terug lopen en weer, heen en weer,
die zeker is optelling qua tijd, en letterlijk stapsgewijze.
>> Inbrengen sorteren, op het eerste oogopslag, ziet eruit als het is
super slimmer, dat ik ben gewoon het maken van trage, stapsgewijze vooruitgang,
maar ik ben niet van plan dit heen en weer.
Maar als iemand inderdaad buiten de orde, bericht
al het werk dat ik moest gewoon doen.
Ik moest de helft van de lijst te verplaatsen alleen om ruimte voor nummer één te maken.
Dus het is hetzelfde bedrag van het werk tot nu toe is
voelt, gewoon een ander soort werk.
>> Laten we doorgaan.
Dus nu weten we dat iedereen tussen één en acht zijn gesorteerd.
Hier, ik heb nummer drie.
Als je wilt op te halen nummer drie, één stap terug.
En wat doen jullie doen?
Yep.
Dus dat is een andere één, twee, drie stappen.
Drie eenheden van de tijd die kosten slechts mij, dus dat drie kunnen nu passen.
Tot slot, zeven.
>> Laten we verder gaan en hebben je een stap terug te nemen.
Dit is alleen maar om ons te kosten één eenheid van tijd, maar dat is OK.
En nu, vijf gaat naar een beetje duurder.
Indien u graag een stap terug.
We moeten verhuizen acht, en zeven en zes.
En dan iedereen is nu opgelost.
Dus een grote hand aan onze vrijwilligers hier.
Heel erg bedankt.
>> [Applaus]
>> Bedankt iedereen.
Bedankt iedereen.
Dus laten we zien nu hoe kostbaar dat alles was.
Laten we eens kijken misschien wel de eenvoudigste van deze, bubble sort.
En ik zeg eenvoudigste, alleen omdat je kunt het gretig op te lossen door gewoon
bevestig de paarsgewijs probleem.
Fix de paarsgewijze probleem hier, opnieuw en opnieuw
en weer herhalen zoveel vaak als je echt nodig hebt om.
>> Dus het blijkt dat met een bel soort, goed,
hoeveel stappen moet ik op te nemen de eerste pas van dat algoritme?
Ik zou take-- laten see-- één, twee, drie, vier, vijf, zes, zeven.
En er is hier acht elementen.
Dus het is net n minus 1 stappen krijgen vanaf het begin van de lijst
aan het einde van de lijst.
>> Maar met de selectie sorteren, herinneren dat ik het selecteren van elementen weer
en nogmaals dat is de kleinste, Ik zet het op zijn plaats,
maar dan ben ik niet zoek achter me weer.
Dus ik denk dat het een beetje meer duidelijk dan is dat de eerste keer, zou ik
moeten alle n min 1 stappen te ondernemen het kleinste element te vinden.
Dan zet ik ze op hun plaats, en ik verdrijven wie was hier eerder.
>> Maar dan hoef ik niet te blijven kijken naar dit element,
omdat ik weet dat het reeds de kleinste.
Dus nu kan ik kijken naar slechts zeven elementen dan zes elementen,
dan vijf elementen, toen vier elementen.
Dus mathematisch, als n het aantal elementen of getallen
dat we begonnen met, kun je je voorstellen dat dit hetzelfde is als n minus 1,
n plus minus 2 stappen, n plus minus 3 stappen,
n plus minus 4 stappen, alle weg naar nog maar één stap.
En ik ben op mijn laatste persoon.
>> En als u zich herinneren dat veel van statistieken boeken of wiskunde boeken
hebben die formules op de hardcover achter of voor hen,
het blijkt dat deze serie kan eenvoudiger worden uitgedrukt
zo n keer n minus 1 op 2.
En het is fijn als dat niet in de voorhoede van je geest.
Maar dit is inderdaad waar.
Dat is gewoon een eenvoudigere manier van schrijven.
En dan als je denkt terug naar de lagere school,
als je gewoon beginnen te vermenigvuldigen dingen uit, dit natuurlijk
is gewoon n kwadraat minus n gedeeld door 2.
Alles wat ik heb gedaan is uit te breiden de uitdrukkingen daar.
En dus laten herschrijven deze een beetje anders.
Dat is n kwadraat gedeeld door 2 min n / 2.
>> Dus nogmaals, ik ben gewoon een soort van de toepassing wat rekenkunde regeert daar.
Maar merk nu dat de grootste term in deze uitdrukking, zogezegd,
dat n kwadraat.
Dus ja, het is n kwadraat gedeeld door 2, verminderd met n / 2.
>> Maar over het algemeen, als n gaat een grote waarde,
Ik ga om te beweren dat n kwadraat gaat de dominante factor.
Het is gewoon gaat worden een grotere bijdrage
het aantal stappen dan n / 2.
Dus wat ik bedoel?
Laten we proberen een eenvoudig voorbeeld, zelfs hoewel de wiskunde krijgt een beetje groot.
>> Dus stel dat we hadden 1.000.000 mensen op het podium, of 1.000.000 dingen
dat we willen afstand.
Laten plug miljoen in precies die formule
om te zien hoeveel stappen er nodig is in totaal tot een miljoen elementen te sorteren met behulp van laten we zeggen,
selectie sorteren.
>> Dus zouden we dezelfde formule als voorheen.
Ik zou de stekker een miljoen, zodat ik krijg miljoen kwadraat gedeeld door 2,
minus miljoen gedeeld door 2.
Als ik dat doe wiskunde van tevoren Hier hebben we 500 miljard
minus 500.000, waarvan geeft ons 499.999.500.000,
dat is pretty darn groot.
>> In feite, als je nu vergelijken 499.000.000.000, 999.000.000,
500.000 tegen onze oorspronkelijke waarde, 500 miljard, het is zo verdomd dichtbij.
Rechts? n kwadraat gedeeld door 2 geeft ons-- of liever, n kwadraat gedeeld door 2
gaf ons 500 miljard.
Dat is pretty darn dicht tot 499.999.500.000,
dat wil zeggen het aftrekken af ​​500.000, of meer in het algemeen, af te trekken uit
n kwadraat, niet echt een groot probleem.
De n kwadraat maakt deze aantallen groeien echt snel.
>> Nu is dit alleen van belang in zoverre zoals wij, als informatici,
zijn over het algemeen niet van plan om zo veel schelen de nuances van deze formules
en precies wat de precieze antwoorden zijn.
We zorg alleen dat, weet je wat?
Aan het eind van de dag, deze formule in de orde van n kwadraat.
>> Ja, we delen door 2 in.
Ja, we trekken uit n min 2.
Maar aan het eind van de dag, de term die ons echt pijn doet en kost ons
veel trappen is dat vierkant termijn.
En zo wat een computer wetenschapper gaat meestal doen
is negeren al die kleinere orde termen,
en kijk maar naar degene die draagt ​​het meest bij aan de kosten.
>> En dat is mooi, want we kunnen praten nu in veel grotere algemeenheid
over algoritmen en kunnen ze vergelijken.
En het feit dat ik ben het gebruik van deze O is weloverwogen.
Als ik zeg in de orde van, ik ben speciaal
verwijst iets riep grote O. En grote O
is een notatie die een computer wetenschapper gebruikt om te beschrijven
een bovengrens iets.
>> Dus als je zegt dat een algoritme is in grote O n kwadraat,
zoals ik voorgesteld slechts een daarnet, dat betekent
dat in termen van de lopende tijd of de efficiëntie,
zij neemt de bestelling n kwadraat stappen.
Misschien meer, misschien minder.
Maar het is in de orde van n kwadraat.
En dat is de bovengrens.
Het is niet van plan om pijnlijker dan dat.
Het gaat niet n blokjes gesneden te zijn, of 2 de n of iets veel groter.
Dit is een bovengrens op wat die kosten is.
Dus gezien het feit dat, laten we overwegen slechts een paar voorbeelden.
En dit is slechts een eindige lijst van veel voorkomende looptijden
voor algoritmen die bedoeld is illustratief voor sommige dingen die we hebben
al gezien.
>> Dus bijvoorbeeld in het geval van selectie sorteren, wat ik hier beweren
is lopen dat soort selectie's tijd in de orde van n kwadraat.
In het ergste geval, ga ik heb een hele hoop willekeurige getallen hier.
En zoals we mathematisch gezien, als ik blijven lopen
door de lijst, door de lijst, het selecteren van de kleinste
weer element, als ik eigenlijk opschrijven alle stappen
Ik neem als ik voorgesteld formulaically voor, het is aan de orde van n kwadraat
stappen die ik neem.
>> En het blijkt dat bubble sorteren en insertion sort
zijn zo langzaam in het ergste geval.
Denk bijvoorbeeld, insertion sort, de laatste algoritme waarmee we,
die hadden we eens kijken naar het element, en steek hem vervolgens waar het thuishoort.
En dan hebben we gekeken naar het volgende element, en ingebracht waar het behoort.
>> Dus rekening houden met de best mogelijke scenario.
Stel dat ik had mijn vrijwilligers line-up dit letterlijk als één tot en met acht,
al naargelang.
Hoeveel stappen is insertion sort gaan nemen tot acht mensen te sorteren,
Als ze aankomen op het podium op zoek als dit?
>> Acht mensen al naargelang.
En ik gebruik insertion sort.
Die laatste van de algoritmen.
Nou, laten naspelen echt snel.
Dus als ik hier beginnen, zie ik een.
Waar komt men behoort?
Het behoort hier.
Ik zie twee.
Waar komt twee behoren?
Hier.
Ik zie drie.
Waar komt drie behoren?
Hier.
>> Ik zie vier.
Hier.
Vijf, zes, zeven, acht.
Er is geen reden om mezelf te herhalen.
En ja, hoeveel stappen is dat in termen van n?
Het is aan de orde van n stappen, toch? n minus 1.
Maar ik nam een ​​aantal lineaire stappen, en nu ben ik klaar.
Dus dat is het beste geval, dat wel.
Hoe zit het met het ergste geval?
Wat acht dan waren er, en zeven waren daar beneden,
en één en twee waren hier, dus dat de lijst echt werden teruggedraaid?
>> Nou, wat gebeurt er inderdaad als dit is het nummer?
En we zullen maar een paar voorbeelden te doen.
Wat als, inderdaad, de nummer acht is hier, en de number-- whoops.
Dus wat als, inderdaad, het aantal acht is helemaal hierheen,
en ik ben met behulp van een soort inbrengen?
>> OK.
Ik eis op dit moment is het op zijn plaats.
Maar nu, seven-- waar gaat zeven gaan?
Uiteraard gaat het hier.
Dus ik moet verhuizen acht meer dan één plaats.
Nu zes, waar gaat het heen?
Nou, oke.
Nu, ik moet verhuizen acht meer dan een plaats, en zeven meer dan een plaats,
en toen ik naar beneden plop zes.
>> Dus de eerste keer, het kost me een stap om dingen te repareren,
dan is het kostte me twee stappen om dingen te repareren.
Hoeveel stappen is er gaan nemen om vast te stellen
dingen tot vijf op de juiste plaats te zetten?
Drie.
Want nu moet ik bewegen een, twee, drie.
Hoeveel stappen gaat het te nemen vier op de juiste plaats te zetten?
4 plus 5, plus 6, plus 7.
>> En dus is het mathematisch identiek aan wat wij beschreven voor de selectie soort.
We hebben deze serie Dat is gewoon verhogen.
1 plus 2 plus 3 plus 4, of omgekeerd, 7 plus 6
plus 5 plus 4 voegt voor vandaag doeleinden in de orde van n kwadraat.
>> Dus laat me ook dat bepalen bubble sort is ook in n kwadraat.
Want met bubble sort, elk keer dat ik door de lijst,
Ik ben het nemen van ongeveer hoeveel stappen?
Elke keer dat ik letterlijk lopen vanaf daar naar daar?
Ruwweg n stappen.
Maar hoe vaak zou ik moeten gaan door de lijst?
>> Nou, ruwweg n tijd.
Misschien n min 1, maar ruwweg n keer.
Nou, waarom is dat?
Nou, met bubble sort, indien we beginnen met bubble sort,
de lijst in het slechtste situatie, die weer geheel
achteruit, wat er gaat gebeuren?
Ik ga door de lijst, en het aantal men behoort de hele weg daar.
>> Maar met bubble sort, hoe ver gaat men bewegen op mijn eerste passage door de lijst?
Hoeveel plekken krijgt hij dichter bij de juiste plaats?
Eentje maar.
Dus als je voor reden door dit, telkens via dit algoritme,
David's nemen ongeveer n stappen.
Maar hoeveel passes de lijst is deze
gaan nemen voor een te borrelen naar links waar het hoort?
>> Hij moet bewegen als, n ruimtes op deze manier.
Dus alleen maar om de sortering te doen van de lijst, Ik moet heen en weer te lopen n keer.
En elke keer, ik ben kijken n elementen.
Dus doe n dingen n keer op de volgorde van n kwadraat.
>> Nu, we zullen zien in een aantal van de korte broek die
zijn ingebed in CS50's volgende probleem set, een andere benadering deze,
maar voor nu, laten we maar eens kijken enkele andere looptijden,
vooral als de sortering die nemen een beetje tijd om te bezinken.
Wat is een algoritme dat we hebben al gezien dat neemt in de orde van n stappen?
>> Wat moet een lineaire aantal te nemen van de stappen die we tot nu toe hebben gezien?
Wat is dat?
Het telefoonboek zoeken.
Het eerste algoritme.
Rechts?
Waar we zijn lineair op zoek naar Mike Smith?
Inderdaad.
Vanaf week nul, toen ik begon het draaien van een pagina in een tijd,
en ik zei zelfs dat het was een beetje van een lineaire gevoel algoritme
en we hadden dat beeld op de bord met de rechte rode lijn
en de rechte gele lijn, die inderdaad waren
algoritmen die in grote O n.
>> Omdat Mike Smith vinden in een telefoon boek van n pagina's, in het ergste geval,
zou me n stappen te ondernemen.
Hoe zit het met het nemen van deelname?
Een twee drie vier vijf zes.
Wat is de looptijd van deze algoritme voor het nemen van het bijwonen?
Big O n, omdat in theorie I moet iedereen in de kamer te wijzen.
>> Nu als een terzijde, hoe zit het met de andere optimalisatie van week nul?
Twee, vier, zes, acht, 10, 12.
Een computer wetenschapper zou realiseren, wacht eens even,
dat is in de orde van n gedeeld door twee stappen.
Rechts?
Want ik ben bezig met twee personen tegelijk.
Maar we gaan om te negeren die lagere orde termen,
en we gaan gewoon gooi de kloof rijden met 2,
en gewoon zeggen, grote O n voor dat algoritme ook.
>> Wat dacht je van deze?
We zullen overslaan enkele van deze, maar wat was een algoritme dat log n was?
Dat duurde ongeveer log n stappen?
De verdeel en heers.
Precies.
Net als het telefoonboek voorbeeld week nul en eerder vandaag,
waar we verdeeld het probleem opnieuw en opnieuw en opnieuw.
We trokken het op het bord in de week nul als een gebogen groene lijn,
en we zeiden dat dag was een logaritmische algoritme.
>> Inderdaad, het aantal stappen te neemt om verdeel uit te voeren en te veroveren,
of binaire zoekopdracht als we beginnen noemde het, net als in het telefoonboek,
is in de orde van log en trappen.
En dit is een beetje een rare één.
>> Wat kost een stap, of specifieker
een constant aantal stappen?
Misschien is het twee, misschien is het drie, maar een computer wetenschapper net
vereenvoudigt het als grote O van 1, sommige constant aantal stappen.
Wat is iets wat je zou kunnen doen neemt een constant aantal stappen?
>> Wat is de looptijd van de klappen?
Constante tijd.
Rechts?
Zoals, wat is de looptijd van iets dat slechts één neemt doen
operatie, zoals afdrukken F Hello World.
Die kunnen worden gezegd om een ​​constante tijd, tenzij minder hoek geval met print F,
Wat zou de looptijd print F eigenlijk?
En waarom?
Wat is n meten in dat geval?
>> PUBLIEK: [onverstaanbaar].
DAVID J. MALAN: Precies.
Het aantal tekens we willen afdrukken.
Dus het is zeer context-gevoelig.
Vandaag hebben we ons vooral geconcentreerd veel op letters en cijfers hier op het bord.
Maar het kan ook zijn karakters in een feitelijke string.
Zo blijkt er een andere maatregel die zal beginnen zorgen te maken over,
en dat is het tegenovergestelde van grote O, om zo te zeggen.
>> Dat is omega notatie.
Terwijl grote O betekent wat is, de bovengrens op uw lopende tijd?
Maximaal, hoeveel tijd misschien iets te nemen?
Omega-- jammer dit blijft komen up-- is het tegenovergestelde van dat,
waarbij het een ondergrens aan de hoeveelheid tijd die iets zou kunnen nemen.
>> So. bijvoorbeeld wat een algoritme dat duurt altijd n kwadraat stappen?
Nou, een van de algoritmes die we hebben gezien Vandaag, in feite zou zijn dat ook.
Selectie soort.
Selectie soort is vrij dom.
Zelfs als de algorithm-- sorry, zelfs Als de matrix al gesorteerd,
selectie sorteren gaat blijven lopen door de lijst
om zeker te zijn heeft de kleinste element opnieuw en opnieuw en opnieuw.
En ook al heb je de mens in de publiek weet dat, wacht eens even,
je al voorbij de kleinste element, de computer
weet niet dat totdat het lijkt helemaal door de lijst.
Ook een ondergrens die Ook in aanmerking worden genomen
misschien lineaire tijd.
>> Hoeveel tijd kost het om sort n elementen in het beste
Bij het gebruik van iets als bubble sort?
Stel dat uw lijst is al opgelost.
We zeiden bubble sort neemt de volgorde van de n kwadraat stappen.
Maar wat als het al naargelang?
Wat als je je realiseert na één doorgang door de array
dat je geen swaps hebt gemaakt?
Heb je nodig om te blijven maken meer doorgangen?
>> Nee.
Dus een ondergrens op de bubble sort zou kunnen zeggen lineair.
Omega n.
En we kunnen kijken anderen deze ook.
Dus laten we eens een snelle blik op slechts een visualisatie hier
om te zien hoe deze zich onderscheiden.
Ik ga hier naar beneden gaan in deze pagina die beschikbaar is op de website van C50's,
maar het zal een pijn aan het werken te krijgen, aangezien het gebruik maakt van een techniek genaamd
Java-applets, dat is een grotendeels ondersteund deze dagen,
op zijn minst door Chrome en enkele anderen.
>> En laat me gaan en versnellen dit en uit te leggen wat er gaande is.
Dit is een demonstratie van de zeepbel sorteren, het eerste algoritme hebben we gekeken.
En het is een weergave dat elk Deze staven een getal.
Hoe groter de bar, hoe groter het aantal.
Hoe kleiner de bar, hoe kleiner het getal.
En wat u kunt visueel te zien, zelfs hoewel dit gaat super snel,
is dat de rode balk is net als ik, heen en weer oplossen van problemen.
Je kunt zien dat de grotere elementen inderdaad borrelen naar rechts,
en kleinere elementen borrelen aan de linkerkant.
En hier beneden, als we eigenlijk kijken nauwer,
kunnen we eigenlijk tellen aantal vergelijkingen en swaps
die werden gemaakt.
>> Maar in plaats daarvan, laten we eens kijken bij de tweede algoritme
hebben we gekeken naar eerder met onze vrijwilligers, selectie sorteren.
Visueel, heeft een heel ander effect.
Maar het is, nogmaals, zeer intuïtief, in die houden we het selecteren van de kleinste
element, en we kregen een beetje geluk.
Dat voelde fundamenteel sneller.
Maar als we liepen dit opnieuw en opnieuw en wederom met veel ingangen,
zouden we zien dat het inderdaad nog steeds in grote O n kwadraat.
>> Laten we doen een laatste hier, insertion sort,
waarbij de derde algoritme was keken we naar, en terugroepen
dat deze zich bezighoudt met de elementen zoals het hen tegenkomt,
maar dan is het misschien wel verschuivingen over dingen om ruimte te maken,
invoegen van elementen waar ze thuishoren.
>> En ook dit eindigt het geven van de eindresultaat. Nu drie van die
voelde behoorlijk snel.
En inderdaad, ik liep ze bij een vrij goede clip.
Maar fundamenteel, ze zijn allemaal vrij verschrikkelijk, om eerlijk te zijn.
Al deze algoritmen dusver die worden uitgevoerd in grote O n kwadraat
neem nogal wat tijd om te draaien in het einde.
>> En inderdaad, kunnen we zien en het gevoel dat dit ten slotte
als ik trek dit derde en laatste demo.
Dit is een visualisatie dat gaat
bubbelen sorteren tonen links, selectie sorteren in het midden,
en iets als een van onze kant verhoogt eerder gesuggereerd,
samenvoegen sorteren aan de rechterkant.
Een verdeel en heers strategie aan de rechterkant.
En dat is in feite wat we gaan kijken naar woensdag.
Maar laten we de tijd om deze parallel lopen.
Het is ruwweg evenveel elementen, alle lopende tegelijk.
Bubble sort vs selectie sort vs merge sort.
>> Nu, ze zijn allemaal running in theorie tegelijkertijd.
De CPU draait op dezelfde snelheid, maar u
kan voelen hoe vervelend dit is zeer snel gaan worden,
en hoe snel bij We injecteren een beetje van de week
De zero-algoritmen kunnen we versnellen dingen.
>> En laten we nu vergelijken deze in een laatste vorm.
Ik ga om te gaan naar de website van CS50, waar
hebben we deze laatste schakel voor vandaag, waar iemand op het internet
vriendelijk samen een video, die een vangt wat anders sorteren
algoritmes klinken.
Dit is een soort inbrengen.
>> [Pieptoon]
>> Waarbij je solliciteert een frequentie op basis van de hoogte van de bar bar.
Dit is bubble sort.
>> [Warped piepen]
>> Coming up next is-- komen up next is-- selectie sorteren,
waarbij nogmaals, we selecteren het kleinste element,
en we kunnen zien groeien van links naar rechts.
>> Samenvoegen sorteren, onze winnaar tot nu toe vandaag.
Merk op hoe het verdelen van dingen in [onhoorbaar] helft en kwartalen.
Gnome soort, die we niet hebben over gesproken, en visueel creëert
en audally een beetje een verschillende vorm en geluid.
Heen en weer, schoonmaken dingen.
Lees ook Heapsort op de website van deze kerel.
>> En dat is het.
Wij zullen u de volgende keer.
>> [Suizend EN MUZIEK]