>> [MUSIC Playing]
>> DAVID J. MALAN: Okay.
Så velkommen tilbage.
Dette er CS50 og er slutningen af ​​uge tre.
>> Så huske i de sidste mange uger, vi har tilbragt en hel del af
tid på C, om programmering, om syntaks.
Og det er helt normalt, hvis du stadig kæmper med Problem Set 2, for at være
banke hovedet mod muren.
Det er kryptisk udseende fejlmeddelelser og bugs, som du
kan ikke helt jagte.
Fordi, forvisset, at på bare et nogle få uger vil du se tilbage på
ting som Cæsar, og [? V-genair,?] måske endda Knæk og
indse, hvor langt du er kommet i en kort periode.
Så hvis det er nogen trøst, hænge der for nu.
>> Men i dag begynder vi at overgangen til ting højere niveau.
Og vi begynder at tage for givet, at jer vide hvordan man programmerer, eller i
mindst en begyndende at komfort niveau.
Og vi vil begynde at overveje, hvordan vi kan gå om at designe programmer mere
effektivt.
Hvordan vi kan gå om at optimere effektiviteten af ​​vores algoritmer, og
generelt løse mere interessante problemer.
Og begynder at tage for givet, at Hvis vi ville, kunne vi kode op i ethvert
af de eksempler, vi har i tankerne.
Så i dag, vi ikke rører tastaturet for enhver form for kode.
Det vil være langt højere niveau, og i sidste ende, om problemløsning.
>> Så for at komme til det punkt, så lad mig foreslå at følgende syv
rektangler repræsenterer syv døre, bag der er en hel bunke af
numre, blandt hvilke er tallet 50.
Lad mig projicere dette på dette skærmen her.
Og foreslår, at vi har brug for en frivillig til at hjælpe med at finde mig et tal foran
Internettet her for at se.
Kom op i pink.
Ok.
Hvad er dit navn?
>> JENNIFER: [uhørlig]
>> DAVID J. MALAN: Undskyld?
>> JENNIFER: Jennifer.
>> DAVID J. MALAN: Jennifer.
Okay, Jennifer.
Hyggeligt at møde dig.
Kom op.
Så disse her er syv døre, og hvad Jeg vil gerne have dig til at gøre for os her,
foran alle dine klassekammerater, er at finde os nummeret, 50.
For at finde et nummer, du kan peek bag nogen af ​​disse døre ved blot at trykke
på en af ​​dørene, og det vil afsløre sit nummer.
Og lad os se, hvor hurtigt du kan finde os nummeret, 50.
>> 15..
16..
50..
Pænt gjort.
Ok.
Runde af bifald til Jennifer.
>> [Applaus]
>> Ok.
Så hvad var din strategi for finde nummeret, 50?
>> JENNIFER: Øh, jeg troede måske, hvis -
[Uhørligt]
>> DAVID J. MALAN: Oh.
Giv det et sekund.
Så var din strategi for finde nummeret, 50?
>> JENNIFER: Så jeg bare starte på begynder at se, hvad det første nummer
var og så tænkte jeg, måske hvis de er sorteret, vil jeg bare holde
aflytning højere op?
>> DAVID J. MALAN: OK.
Og vi synes at have fundet at være tilfældet.
Selv, lad os skrælle lagene bare en lille smule, og du ønsker at gå
videre og afsløre de andre døre du kunne have valgt?
>> JENNIFER: Åh, kære.
>> DAVID J. MALAN: Ah.
>> JENNIFER: Så jeg har lige fået heldig.
>> DAVID J. MALAN: Så du fik heldig.
Ok.
Så ikke dårligt.
Men det er et interessant indsigt, right?
Hvis du antaget, og du fik, ja, lidt heldig der.
Men hvis du antages, at de tal var sorteret, kan du være mere præcis
til, hvordan der påvirkede din adfærd?
>> JENNIFER: Så hvis de blev sorteret, jeg tænkte måske mindste til største.
>> DAVID J. MALAN: OK.
>> JENNIFER: Eller hvis det endte med at blive virkelig stor, så største til mindste.
>> DAVID J. MALAN: OK.
Så største til mindste, eller mindste til den største.
Men lad mig foreslå antage, at du havde fået uheldig, og antage, at de
blev ikke i virkeligheden, sorteres, hvor mange af disse døre måske du har haft til peek
bagud i det værste tilfælde?
>> JENNIFER: Alle af dem.
>> DAVID J. MALAN: Alle af dem.
Så lad os generalisere det som n.
Der sker for at være 7, men lad os mere generelt sige at der er n døre på
skærm her.
Så i værste fald ville du have at se bag 7 døre, eller n døre.
Og så dette virkelig er, det er lidt af held i dag, men det er virkelig en lineær
algoritme slags, selvom du blev slags springe rundt.
Er det fair?
>> JENNIFER: Ja.
>> DAVID J. MALAN: Nå, lad mig se, om din strategiændringer, hvis jeg flytter os til
vores andet eksempel her med 7 forskellige døre.
Samme tal, men dette tid, de er sorteret.
Hvad er din strategi her kommer til at være, forsøger at sætte ud af dit sind, hvad
de andre tal blev -
>> JENNIFER: OK.
>> DAVID J. MALAN: - tidligere?
>> JENNIFER: Lad os starte med den første.
>> DAVID J. MALAN: Okay.
Start med den første.
4..
Nu hvor du kommer til at gå, og hvorfor?
>> JENNIFER: 4 er virkelig lille.
Så hvis de er en slags måske mindste til største, skulle det
det dobbelte, og -.
>> DAVID J. MALAN: OK.
Lad os se, hvor du tror?
>> JENNIFER: Prøv den sidste.
Nice.
>> DAVID J. MALAN: Meget pænt gjort.
Ok.
>> [Applaus]
>> DAVID J. MALAN: OK.
Så du rent faktisk gør det grueligt, fordi du er
gør det meget godt.
Hvilket efterlader os i stand til at foretage visse punkter.
Så lad os prøve at rulle tilbage her.
>> JENNIFER: OK.
>> DAVID J. MALAN: Meget godt gjort, alligevel.
Så du startede i starten, du så, at det var 4, så du
flyttes til slutningen.
Men formoder du ikke heldig der, og antag 50
var et andet sted.
Hvad dit tredje skridt have været?
>> JENNIFER: Gå tilbage til begyndelsen.
>> DAVID J. MALAN: Gå tilbage til begyndelsen.
OK, så du ville have rørt denne dør, som var 8.
Ok.
Så det er ikke 50 år.
Hvor ville du have set det næste?
>> JENNIFER: Hvis jeg ikke gjorde kender de sorteret.
>> DAVID J. MALAN: Korrekt.
Tja, hvis du vidste de blev sorteret -
>> JENNIFER: Åh, vidste, ja.
>> DAVID J. MALAN: - men du gjorde ikke vide, hvor 50 blev endnu?
>> JENNIFER: Bare fortsæt.
>> DAVID J. MALAN: Okay.
OK.
Holde ud.
OK, at jeg kan arbejde med.
>> JENNIFER: OK.
>> DAVID J. MALAN: Nu, hvis du bare kommer til at holde ud, hvad er din
algoritme overdraget bakkede ind.
>> JENNIFER: Den lineære -.
>> DAVID J. MALAN: Det er slags lineær.
Men lad mig foreslå, lad mig til at sætte på stedet.
Lad mig opdatere siden.
samme nummer, samme arrangement, samme døre.
Men tænk tilbage til den første dag i klasse, når vi rev en telefonbog i
halvdelen, en slags, og hvad var vores strategi der?
>> JENNIFER: Start ved midten.
>> DAVID J. MALAN: OK.
Så starter i midten.
Så lad os gå videre og simulere det.
Start ved midten afslører, at døren.
Så antallet 16.
Så hvad ville den stærke fyr har gjort, der rev telefonbogen i halve,
for at komme til den næste gæt?
>> JENNIFER: Gå i denne halve.
>> DAVID J. MALAN: Og hvorfor til højre?
>> JENNIFER: Hvis de var slags mindste til den største, 50 så skal være
at enden.
>> DAVID J. MALAN: Godt.
Fuldstændig rimelig.
Så som en telefonbog, går du til ret i modsætning til venstre, men her
er nøglen takeaway.
Du kan nu smide væk eller rive, halvdelen af ​​dette problem, så du ikke
med 7 døre, men rigtig med kun 3.
Hvilket er omtrent halvdelen af problemets omfang.
Ok.
Så nu, hvad du ville have gøres efter du går ret?
>> JENNIFER: So 16 er stadig temmelig små, i forhold til 50, så måske jeg vil prøve,
ligesom, denne ene.
>> DAVID J. MALAN: Okay.
42..
Okay, så nu, hvad er din instinkt fortæller dig?
>> JENNIFER: Jeg kan smide dette og så bare -
>> DAVID J. MALAN: OK.
Godt, du kan smide væk den venstre halvdel der.
>> JENNIFER: - pluk denne ene.
>> David J. MALAN: Og den rigtige.
>> JENNIFER: Ja.
>> DAVID J. MALAN: Så selvom det er svært at se måske når der er kun
7 døre, så tænk nu, sammenhængen i
algoritme netop anvendt.
I den tidligere sag, har du få heldige, som var stor.
Men du gjorde bruge en heuristisk, Jeg ville sige.
Du brugte slags dine instinkter, og vide det sorteres, hvis det er temmelig
lille i begyndelsen, naturligvis, vi har kom til at gå mere til højre.
Men i en vis forstand, du fik heldig, fordi måske dette var nummer 100,
og måske 50 var mere i midten.
Måske 50 var endda herovre.
>> Men hvad du gjorde lidt anderledes denne gang var, du gjorde det samme
igen og igen.
Og jeg vil hævde, at hvad du lige gjorde, omend påvirket af telefonen
bog eksempel, er noget meget mere algoritmisk og meget
mindre specielle hylstre.
Meget mindre instinktive.
Så i slutningen af ​​dagen, hvordan ville du beskrive effektiviteten af
første algoritme, hvor du gik venstre til højre, versus
anden algoritme her?
>> JENNIFER: Denne ene bør ligesom, måske halvere den tid, eller endnu mere, ja.
>> DAVID J. MALAN: OK, måske endda mere.
Lad os skubbe lidt hårdere på det.
Hvad der virkelig, hvis vi fortsætter dette logik, vi helt sikkert halveret
køretid med denne anden algoritme ved at smide halvdelen af
tal, men hvad gjorde vi den næste iteration, når Jennifer afslørede
det andet nummer?
>> Vi halveret antallet af døre igen.
Og hvad gjorde vi efter det, hvis der var flere døre for at lege med?
Vi ville halvere dem, og igen, og igen og igen.
Og dette var ligesom jer alle stående op på den første uge af
klasse, halvdelen af ​​jer sidder ned, halvt af jer sidder ned, halvdelen af ​​dig
sidder ned, indtil en enlig sjæl stod.
Og vi sagde, at køretiden for at antallet af trin tog det var
på rækkefølgen af ​​hvad?
>> SPEAKER 1: [uhørlig]
>> DAVID J. MALAN: So log base 2 n, eller bare mere simpelt, skal du logge på n.
Så noget logaritmisk.
Og grafen var ikke en lige linje der bare blev værre og værre, det var
denne interessante kurve, der ikke komme så slemt over tid.
Så lad os holde fast i denne idé.
Lad os takke Jennifer.
Tak så meget for at komme videre op.
Og en sek.
Ingen bordlamper dag, men vi har CS50 stress bolde.
>> JENNIFER: Yay.
>> DAVID J. MALAN: Okay, her.
Tak for at pådrage stress heroppe.
Ok.
Så lad os se om vi kan ikke nu formalisere det en smule mere.
Så igen, hvad vi lige gjorde var set de samme ting, som vi gjorde
i det første uge.
Men i stedet ende med blot en lineær algoritme, som vi afbildet
tidligere som denne lige linje, hvorved hvis vi sætter endnu en dør på
på skærmen, og Jennifer ville har måttet se, potentielt
bag en mere dør.
Hvis vi sætter to flere døre, kan hun have at se bag to døre.
>> Og så var der denne lineære forholdet mellem størrelsen af ​​den
problem på, siger, x-aksen, og den tid det tager at
løse på y.
Men det billede, jeg hentydede til tidligere var denne grønne linje.
Grøn bevidst, fordi det føltes bare bedre.
I teorien, da algoritmen, vi gjorde det med telefonbogen, vi når gjorde det
med jer tælle hinanden, og i det andet tilfælde, hvor Jennifer bare
gjorde det op her, det var en slags af fundamentalt bedre.
Fordi det ikke kun var dobbelt så hurtigt.
Det var ikke engang fire gange så hurtigt.
Det var helt afhængig af, hvad størrelse af input var, hvor mange
skridt det i sidste ende tog.
>> Og så denne simple idé, at vi alle tog for givet med telefonbogen,
kan ligeledes anvendes til noget som dette.
Og det kan være mere afslappet kendt som som du måske
forestille del og hersk.
Ikke ulig hvad vi gjorde, naturligvis, med telefonbogen.
>> Men pseudokode, tilbagekaldelse, var dette.
Så vi vil ikke gøre det igen, men husker den første uge, vi alle stod op
og derefter halvdelen af ​​du sad halvdelen af du sad halvdelen af ​​du sad.
Denne algoritme blev gennemført på en lidt af en snyd måde, idet det
var ikke blot en af ​​mig optælling, fundamentalt, mere effektivt.
I dette tilfælde var jeg udnytte en sekundær ressource.
Sorter af, flere CPU'er, flere hjerner, flere smarte folk i
værelse var at hjælpe mig med at komme fra noget lineær til noget
logaritmisk, fra noget rød til noget grøn.
>> Men i dette tilfælde, kan Jennifer alene fundamentalt forbedre den
udførelsen af ​​hendes første algoritme ved, igen, bare at tænke lidt hårdere.
Og nu, når det drejer sig tid til at gennemføre disse ting, regne ud,
hvilke linjer kode, kan du skrive sådan at du kan gentage dem igen, og
igen og igen, en slags i en looping måde.
Fordi du ikke kommer til at have den luksus, ligesom Jennifer gjorde i første omgang, at
bare have en hel masse hvis'er og sige, Hmm, hvis det første tal er 4,
lad mig hoppe hele vejen til enden.
Ooh, hvis dette antal er for stort, lad mig gå vilkårligt tilbage
til det andet element.
Du vil opdage, at det kommer til at være en masse sværere at formalisere hvad vi mennesker
tager for givet som meget rimelig heuristik, men en computer er kun
kommer til at gøre, hvad du fortæller det at gøre.
>> Nu har dette meget interessant implikationer.
Denne graf slags beregnet til at sortere i overvælde visuelt, men varsel, hvor
er den lige linje i denne graf?
Hvor er den lineære graf som vi kalder n?
Tja, det er en slags mod bunden af dette billede, right?
Så alt, hvad vi har gjort, er vi har slags zoomet til x-aksen og
y-aksen for at forsøge at få en fornemmelse af, hvad andre typer af kurver ligner.
>> Og detaljerne i den matematiske udtryk i dag, vil ikke så
meget, men bemærke, at der er en masse algoritmer, der er langt værre end
noget, der er lineær.
Faktisk kubik n ser temmelig dårlig.
2 til n ser temmelig dårlig. n kvadreret ser temmelig dårlig.
Og vi vil se, hvad nogle af dem kan være i virkeligheden i dag.
Og log n ikke føler så slemt, men bedre end n er log base 2 n.
Men du ved, det ville have været endnu mere fantastisk, hvis Jennifer, eller hvis vi,
den første uge, var kommet op med noget, der er log af log n.
>> Så med andre ord, er der hele denne vifte af mulige løsninger
problemer, men selv her, varsel hvad der kommer til at ske.
Når jeg zoome ud, hvilke af disse kurver vil vise sig at være den absolutte
værste af dem på skærmen nu?
Så n kubik ser temmelig dårlig i øjeblikket.
Men hvis vi zoome ud og se mere af x og y-aksen, som kommer til at
dominere i sidste ende?
Så det faktisk viser sig, at 2 til n, og du kan finde ud af dette ved blot at
tilslutte nogle stadig større numre, og du vil se, at 2 til
n, faktisk bliver større meget hurtigere.
Hvis vi virkelig zoome ud, en 2 til n algoritme absolut stinker.
Jeg mener, dette kommer til at tage ganske lidt tid til
computer til at kværne igennem.
>> Men du vil se over tid, især med kommende problemområder sæt og endda
afgangsprojekter, er dine data sæt får store, okay?
Selv i den første version af Facebook, som antallet af venner og
Antallet af registrerede brugere fik store, du kan sortere telefon det og
gennemføre noget med lineær søgning, eller en meget simpel sortering
algoritme, som vi skal se i dag.
Du er nødt til at begynde at tænke hårdere og hårdere om disse problemer.
Og de typer af problemer steder som Facebook og Google og Microsoft,
, og andre arbejder på er netop disse slags big data slags spørgsmål
stigende i disse dage.
>> Ok.
Så Jennifers succes i denne anden algoritme, helt ærligt, hun gjorde forbavsende
godt første gang, men lad os skrive det som held, så vi
kan gøre dette punkt.
I det andet tilfælde, gearede hun en algoritme, der gentages igen og
igen, men hun tog for givet en vis antagelse, at vi tillod
hende, men hun udnyttede nogle detaljer anden gang, at hun ikke har den
første gang.
Hvilket var hvad?
>> At listen blev sorteret.
Så så snart listen er sorteret, vi hævder, at Jennifer var i stand til at gøre
fundamentalt bedre.
7 døre, ja, er det ikke interessant, men formoder, det er vi 7 millioner døre.
Log n er helt sikkert vil til at udføre meget, meget
hurtigere i det lange løb.
Men hun skulle have døre sorteret for hende.
Nu tog jeg mig den frihed at gøre det i forvejen på computerskærmen
her, men formoder, at Jennifer havde at gøre det selv?
Antag, at dørene pågældende repræsenterede data i en database, eller
venner registreret for Facebook, eller eventuelle web-sider på internettet, der
forskellige hjemmesider muligvis til indeks eller søge over.
>> Antag, at du lige havde et rådata indstillet, og det blev overladt til dig, eller til at
Jennifer at gøre at sortering?
Det snarere, kræver, at vi besvarer spørgsmålet, ja, hvor meget tid
ville have taget Jennifer, eller endda mig, at sortere disse tal i forvejen, så
at hun kunne drage fordel af det?
Right?
Fordi konsekvenserne, selvfølgelig, er hvis det tager mig lang tid at sortere
numrene, hvem dælen bekymrer, at du kan finde en række lignende 50 så hurtigt,
som i Jennifers tilfælde, hvis vi mere end overvældet af mængden af ​​den samlede tid
det tog ved at sortere ting i forvejen?
>> Så lad os se om vi ikke kan det male billedet her.
Jeg har en hel bunke mere stress bolde, hvis det hjælper
bryde isen her.
Og hvis du ikke har noget imod, vi brug syv frivillige -
på, OK.
Wow.
Så vi behøver ikke at bruge på bordlamper, synes det.
Ok.
Så hvad med jer to i front.
Hvad med dig to fyre i ryggen.
Så det er fire.
Hvad med dig foran fem, seks og syv.
Lige der.
Din vens pege dig ud, så du får præmie.
>> Ok.
Kom op.
Og hvorfor gør vi ikke have dig fyre kom herover.
Jeg har tænkt mig at give dig hver et nummer.
Og gå videre og arrangere jer identisk med, hvad der er
afbildet på skærmen.
>> [Interposing STEMMER]
>> DAVID J. MALAN: Oop, undskyld.
Bug.
Ok.
Nå, her går vi.
Nummer fem.
Nummer seks.
En, to, tre, fire, fem, seks, syv.
Åh, det er akavet.
>> SPEAKER 2: Jeg vil bare få en -.
>> DAVID J. MALAN: Good deal.
Ok.
Tak for din deltagelse.
>> [Applaus]
>> OK.
Ok.
Så vi har fire, to, seks, et, tre, syv, fem.
Perfekt, så vi har syv frivillige her der er lige i bredden til
array, vi spiller med tidligere.
Og jeg valgte syv grunde der vil være lige
praktisk i en lille smule.
Og jeg har tænkt mig at foreslå først at vi sortere disse syv frivillige.
Hvis du gerne vil for det første, at sige hej selv.
Da dette vil være en akavede flere minutter.
Indføre selv.
>> GRACE: Hej, jeg er Grace.
Jeg er sophomore i Leverett House.
>> BRANSON: Hej.
Jeg Branson.
Jeg er freshman i Weld.
>> GABE: Hej.
Jeg er Gabe.
Jeg er junior i Cabot.
>> NEIL: Jeg er Neil.
Jeg er freshman i Matthews.
>> JASON: Jeg er Jason.
Jeg er freshman i Greenough.
>> MIKE: Jeg er Mike.
Jeg er freshman i Grays.
>> JESS: Jeg er Jess.
Jeg er sophomore i Leverett.
>> DAVID J. MALAN: Excellent.
Ok.
Nå, tak til alle vores frivillige her hidtil.
Og udfordringen ved hånden nu går at være at sortere i disse fyre, men så
vi nødt til at tænke lidt hårdt om, hvor effektivt vi faktisk
sorteret dem.
Så lad os først prøve dette.
Du fyre kan se hinandens numre blot ved at placere omkring hjørner.
Gå videre og tage et par sekunder, og sortere jer fra mindste på
overlades til største til højre.
Go.
>> OK.
Godt.
Det var virkelig darn hurtigt.
Nu nogen her, hvad der var den algoritme at disse fyre anvendt?
>> SPEAKER 1: Færrest til størst.
>> DAVID J. MALAN: OK.
Færrest til størst virkelig sortere i mål, men jeg er ikke sikker på det er
virkelig en algoritme.
Færrest til størst fortæller ikke mig trin-for-trin, hvad de skal gøre.
Ja?
>> SPEAKER 1: [uhørlig]
>> DAVID J. MALAN: OK.
Så hvis du ser en person mindre end dit nummer, derefter flytte til
ret af dem.
Så det er nu at få mere udtryksfulde, mere som en algoritme, fordi du
kan sige, hvis dette, så det.
Så vi har en form for betinget konstrukt.
Og disse fyre syntes at gøre, at et par gange, fordi nogle af jer flyttede lidt
af en afstand.
Så der var formentlig en slags looping foregår i deres sind.
>> Men lad os prøve at formalisere det.
Hvis du fyre kunne nulstille tilbage til dette arrangement.
Lad os se om vi ikke kan formalisere en bit, og derefter stille spørgsmålet, bare
hvor effektiv er det?
Selvfølgelig, når vi gør det langsommere det kommer til at føle sig så godt af
en algoritme, men lad os se om vi kan sætte vores fingre på de præcise trin.
>> Så du to fyre er fire og to.
Eller du korrekt eller forkert rækkefølge?
Naturligvis forkert.
Så vi byttes.
Nu vil jeg til at flytte bort her og sige, fire til seks.
Er du korrekt eller ukorrekt?
>> GABE: Korrekt.
>> DAVID J. MALAN: Korrekt.
Seks og en?
Nope.
Swap.
Så det er to swaps.
Seks og tre?
Nope.
Swap.
Seks og syv?
Ser godt ud.
Syv og fem?
>> JESS: [uhørligt]
>> DAVID J. MALAN: OK, swap.
Og sorteres.
Ok.
Så selvfølgelig ikke, vel?
Så der var flere foregår.
Men, ja, disse fyre, selv bare instinktivt.
holdes i bevægelse.
De havde ikke bare stoppe, når de korrigeret et problem.
Så.
Faktisk vil jeg have at gøre det samme.
Jeg nødt til at sortere i spole tilbage til begyndelsen af ​​dette problem,
eller begyndelsen af ​​denne række af mennesker, lad os begynde at kalde dem.
>> Og nu, hvad skal min algoritme på den anden pass være?
>> SPEAKER 1: Samme ting.
>> DAVID J. MALAN: Samme ting.
Og det, jeg begynder at lide, right?
Så snart du kan finde dig selv gøre det samme igen og igen, det er
blive mere som en algoritme, og mindre menneskeligt instinkt.
>> Så nu, her går vi igen.
To og fire?
Nej.
Fire og en?
Ah, var der faktisk nogle arbejde stadig skal gøres.
For og tre?
Godt.
Fire og seks?
Seks og fem?
Seks og syv?
OK, nu færdig.
OK, nej.
Jeg er nødt til at gå tilbage.
>> Så nu, igen, vi gør dette lidt mere bevidst.
Og nu er der kun én hjerne udføre denne algoritme.
Én CPU, hvis du vil.
Og helt ærligt, det er den eneste ressource vi kommer til at have adgang til.
Og når vi går tilbage til et tastatur og har noget som C på vores
bortskaffelse, vi kun skrive et program der kan gøre én ting ad gangen.
Betragtninger, disse fyre et øjeblik siden, vi gearede deres kollektive hjernekraft
ligesom du fyre gjorde i uge nul.
Så lad os holde gøre dette.
>> To og en.
To og tre.
Tre og fire.
Fire og fem.
Fem og seks.
Seks og syv.
Done?
Så jeg er, men lad mig spille djævelens advokat.
Har jeg, den slags computer, der bare gjorde en passerer gennem denne række af
mennesker, ved, at jeg er færdig?
>> SPEAKER 1: Nej
>> DAVID J. MALAN: Så hvorfor?
Hvad ville jeg nødt til at gøre for at konkludere beslutsomt at jeg er færdig?
Sandsynligvis en mere pass.
Right?
Fordi alle jeg kender fra at tidligere pass er, at jeg rettet en fejl.
Og det betyder, måske er der endnu en fejltagelse
at jeg er nødt til at korrigere.
Så jeg kan kun være sikker ved tilbagespoling og derefter kontrollere, 1-2, to og
tre, tre og fire, fire og fem, fem og seks, seks og syv.
OK, nu jeg gjorde intet arbejde.
>> Jeg kan helt sikkert huske, at jeg gjorde noget arbejde med noget som en variabel,
gerne en int.
Kald det swaps, og hvis swaps er 0 når jeg komme her, og det startede ved 0, så
Jeg ville bare være dumt at holde ud frem og tilbage, kontrol igen, og
igen og igen, ikke?
Fordi du sidder fast i nogle slags uendelig løkke.
Så så snart der er 0 swaps, Vi kan hævde, at dette
algoritme er faktisk fuldstændig.
>> Lad os nu sætte et navn på dette.
Den algoritme, jeg foreslår vi bare implementeret er noget der hedder boble
sortere, kendt som sådan i den forstand, at De tal, der er større slags
bubble deres vej op til toppen, eller op til slutningen af ​​rækken af ​​tal.
Men hvor effektiv var denne algoritme?
Hvor mange skridt har jeg rent fysisk at tager for eksempel at sortere disse
syv mennesker?
>> Fire til fem?
OK, for mange er i sidste ende kommer til at være svaret.
Men selv da, det specifikke antal er ikke så interessant.
Lad os generalisere det som n.
Så hvis jeg havde n folk op her, og de var slags, i tilfældig rækkefølge på
begynder i den oprindelige rækkefølge.
Nå, hvor mange skridt, jeg har at tage på den første pass?
Det var en, to, tre, fire, fem, seks, og de er syv personer, så
der er syv, seks -, så det er n minus en trin for første gang.
>> Nu, hvor mange skridt, jeg har tage, når jeg spoles?
Nå, kunne vi faktisk fordoblet, at hvis vi virkelig ønskede at, men for nu, jeg
bare sige, okay, anden n minus 1.
Så n minus 1 vil få irriterende at holde styr på, så lad os
lige rundt lidt op.
Så 2n trin.
Så 14 trin, give eller tage.
>> Hvor mange gange har jeg tager et skridt, næste gang?
Tja, det er 3n.
rigtig.
Og nu, i værste fald, for Eksempelvis ville hvor mange gange jeg har
gået frem og tilbage, frem og tilbage, udføre denne algoritme, bytte
folk på hver pass, groft?
Det er faktisk n kvadreret, right?
>> Fordi der i værste fald kan du slags af tænke over dette intuitivt,
selvom det kan tage lidt lidt tid til at synke i.
I værste fald, hvad ville disse syv mennesker har set ud, i
ordningens vilkår deres antal?
Helt baglæns, right?
Og blot at simulere, hvad var dit navn igen?
>> MIKE: Mike.
>> DAVID J. MALAN: Mike?
OK, Mike, kan du bare slutte mig over her blot én sekund?
Faktisk, nej.
Undskyld Mike, lad os spole tilbage.
Hvad er dit navn igen?
>> NEIL: Neil.
>> DAVID J. MALAN: Neil.
OK, Neil, du kommer med mig, hvis du ikke har noget imod.
Så jeg har tænkt mig at foreslå, bare for enkelhed, at Neil er nu i sin
værst tænkelige tilfælde.
Men huske, hvordan jeg implementeret min algoritme.
Jeg sammenligne, sammenligne, sammenligne, sammenligne, sammenligne, oh.
Nu er disse fyre er ude af orden, så jeg løse.
Så du fyre bytte.
Men nu overveje, hvor meget længere behøver Neil nødt til at gå?
Det er nogenlunde n.
Du ved, det er faktisk ikke n.
Det er ligesom, n minus 1, men jeg får irriteret holde styr på den lille
nummer, så lad os bare kalde det n.
>> Så hvis Neil flytter et skridt maksimalt hver tid, og at flytte Neil ét trin,
Jeg er nødt til at gøre dette virkelig kedelig pass frem og tilbage, dette er groft
at gøre dette, n trin, i alt n gange, fordi det kommer til at tage mig
at mange skridt til at få Neil alle vejen til, hvor han hører til.
Endsige alle andre hvis du fyre blev alle mis-bestilt så godt.
>> Så lad os kalde boble sortere n potens.
Køretiden for denne algoritme, den udførelsen af ​​denne algoritme, den
effektivitet af denne algoritme, Vi skal bare beskrive mere
generelt som n kvadreret.
Hvilket er rart, fordi jeg kunne gøre det samme eksempel med otte personer, ni
mennesker, en million mennesker, og det Svaret er ikke til at ændre.
>> Så hvis du fyre ville huske, lad os nulstille dig til hvor du startede.
Og lad os prøve to andre tilgange og se, om vi ikke kan gøre fundamentalt
bedre end dette.
Så denne gang, vil jeg foreslå en slags anden algoritme.
Det var meget klog af os sidste gang, og du fyre var ret til at få
rigtige instinkter bare lidt at bytte parvis.
Men hvis jeg virkelig ønskede at nærme sig dette simpelthen, og mit mål er at flytte
alle de små numre på denne måde, og skubbe alle de store tal,
måde, hvorfor jeg ikke bare gøre det i mest naive måde som muligt og se om jeg
kan gøre det bedre end det, der var en temmelig kompliceret algoritme?
>> Så lad os se.
Fire er en temmelig lille antal, så jeg er kommer til at forlade dig der øjeblik.
Ooh, nummer to er endnu bedre.
Så kan du bare træde frem et øjeblik?
Dette er i øjeblikket mit mindste nummererede kandidat, og jeg har tænkt mig at huske
at med, ligesom, en variabel.
Men jeg har tænkt mig at holde kontrol.
Er der en person, hvis nummer er mindre?
Seks, nej.
Åh, der er Neil igen.
>> Så jeg har tænkt mig at skubbe dig tilbage slags konceptuelt.
Neil vil komme frem.
Og nu, den variabel, jeg bruger til at holde styr på, hvem der har den mindste
nummer er opdateret til at indeholde Neil placering.
Nå, lad os se.
Tre, syv, fem.
OK, jeg kender Neil var den mindste.
Hvad er den enkleste ting for mig at gøre nu?
Jeg vil ikke spilde min tid ved blot boblende Neil en plet til venstre.
Hvorfor kan jeg ikke bare sætte Neil, hvor han tilhører, hvilket selvfølgelig er hvor?
>> Hele vejen i begyndelsen.
Så Neil, kom med mig.
Og hvad var dit navn igen?
>> GRACE: Grace.
>> DAVID J. MALAN: Grace.
OK.
Så Grace, desværre, du er slags i vejen.
Så hvordan kan vi løse dette problem?
Right?
Hvis dette er et array, der er kun syv placeringer.
Husk på, at med Rob, vi talte om erklære aldre, og vi havde kun en
endeligt antal aldre?
Samme idé her.
Vi har kun et begrænset antal int'er.
Nåde er slags i vores måde, så hvordan vi løser?
>> Den enkleste måde er ligesom, Grace, undskyld.
Du er nødt til at gå over der, så vi kan få mere plads.
Nu, hvis du tænker over det, måske vi bare gjort problemet værre.
Og måske vi gjorde det, fordi det, hvis Grace var på det rigtige sted?
Men vi ved, hun er ikke, fordi ellers ville hun have været
stående fremad i stedet for Neil på dette tidspunkt, right?
Vi har allerede tjekket hendes nummer ud.
>> Ok.
Så nu, Neil er på rette sted, og Jeg kan gøre en lille optimering.
For det næste øjeblik, vil jeg ignorere Neil alle sammen, så der ikke
spilde sin tid, eller ved et uheld bytte ham til det forkerte sted.
Så nu, hvordan finder jeg den næste element, der er mindst?
Two.
Det er en temmelig god del, hvis du ønsker at træde frem og
Jeg vil huske dig.
Six, ikke godt.
Fire, tre, syv, fem, noget godt.
Så lad mig flytte dig til Deres rigtige sted.
Og vi har lige fået heldig denne gang.
>> Nu vil jeg til at ignorere disse to fyre, og nu gør en mere
passere gennem denne.
Six, at en temmelig lille antal.
Kom fremad.
Åh, undskyld.
Grace nummer er bedre, så træde på fremad.
Four.
Beklager, Grace.
Gå tilbage igen.
Nummer tre er bedre.
Syv.
Five.
Og nu, hvad er dit navn igen?
>> JASON: Jason.
>> DAVID J. MALAN: Jason.
Så Jason er nu den mindste element, jeg har valgt.
Hvor skal han hen?
Så hvor seks er.
Og dit navn er igen?
>> GABE: Gabe.
>> DAVID J. MALAN: Gabe.
Gabe er i vejen.
Hvad er den letteste ting at gøre?
Swap disse to fyre og fortsætte.
Så lad os nu se.
Hvem er den mindste?
Four.
Lad mig lige slags snyde.
Fem bliver den mindste.
Jeg finder næste hvis du ønsker at træde frem, hvad jeg har at gøre med
disse fyre, med Gabe?
Swap igen.
Så nu, stadig en smule ude af drift.
Jeg fandt Gabe at være den mindste, så Jeg pop ham ud, flytter jer over.
Og gjort.
>> Så svaret er det samme.
Slutresultatet er det samme.
Hvilken af ​​disse to algoritmer er bedre?
Den anden, jeg hørte.
Hvorfor?
>> SPEAKER 3: Det n trin [uhørlig].
>> DAVID J. MALAN: Det er n trin på de fleste.
Interessant.
Så er det dog?
Så hvordan har jeg finde mindste element?
Hvor mange skridt jeg nødt til at tage Den finder det mindste element?
Jeg havde et kig hele vejen i slutningen, right?
Fordi i det værste tilfælde, hvad hvis Neil var herovre?
Så bare at finde det mindste element tager mig n trin, eller n minus 1.
Men OK.
Så fix Neil.
Husk, et minut eller deromkring siden.
>> Men hvordan finder jeg det næste mindste element?
Det er n minus 1 eller n minus 2 rigtig, fra antallet af trin.
Så OK.
Så jeg gjorde n minus 2.
Ok.
Så det føles lidt bedre.
Ok.
Hvor mange skridt, næste gang at finde nummer tre?
Så n minus 4.
Så det er faldende, én færre trin på hver iteration.
Så det betyder at føle sig bedre, right?
Hvis sidste gang det var nogenlunde n gange n, denne gang er det n minus 1 plus n minus
2, plus n minus 3, plus n minus 4, prik, prik, prik.
Men hvis du husker fra din high school lærebøger, den lille snyde
ark på bagsiden, der har formler, medmindre du tilføje op denne serie af tal,
hvad er det totale antal trin kommer til at være, at jeg tager her?
>> Dette er en af ​​dem, ligesom, n minus 1, gange n, divideret med 2.
Så lad mig se om jeg kan trække dette op for bare et øjeblik.
Og igen, jeg er slags afrunding nogle tal bare for at holde vores liv simpelt,
men så vidt jeg husker, det er noget ligesom hvis Jeg gør n minus 1 ting, så n minus
2, er n minus 3, det er groft noget som dette over 2, og hvis jeg
formere det ud, det er faktisk n square.
Det er ikke føler også godt. n minus n over 2.
>> Men her er de ting.
I datalogi, når problemerne begynder at blive interessant, er, når n
bliver rigtig stort.
Og når n bliver rigtig stort, hvilke af disse værdier kommer til at dominere hele
af de andre?
Det er lidt af n kvadreret, right?
Ja, dividere med 2 er temmelig godt.
Men hvis du taler om milliarder af stykker af data eller trillioner af
stykker af data, OK, så du dobbelt så hurtigt.
Men der virkelig bekymrer sig om hvis det store antal, hvis denne faktor er, hvad får
større og større.
Og sikkert, det gør mere en forskel end denne fyr.
Så selvom du fyre er rigtige, anden algoritme, vi kalder det
udvælgelse sortere, er i den virkelige verden, en smule hurtigere potentielt fordi jeg er
tager færre og færre trin hver gang.
>> Det er egentlig ikke fundamentalt hurtigere.
For hvis vi rent faktisk spiller det ud for store værdier af n, i slutningen af
dag, for store nok n, er det stadig kommer til at føle sig temmelig langsomme.
Nå, lad mig tage et sidste pass på det.
Det er, hvad jeg ville kalde udvælgelse slags.
Kan du fyre nulstille jer en sidste gang?
Og i dette sidste tilfælde, vil jeg at foreslå noget
kaldet indsættelse slags.
Indsættelse slags væsen, begrebsmæssigt, en smule anderledes.
>> Snarere end at gå frem og tilbage, og vælge den mindste element, jeg er
bare at beskæftige sig med hver af disse fyre, som jeg støder på dem, og indsæt
dem ind i deres rette plads.
Så jeg bare kommer til at starte med Grace, og jeg kan se, at hun er nummer fire.
Hvor kommer nummer fire tilhører?
Jeg har ikke startet sortering noget, så Grace får at bo lige der.
Og nu vil jeg påstå, hvis du kunne tage et skridt til højre, dette
min sorteret liste, dette er min usorteret resterende liste.
Så nu har jeg tænkt mig at fortsætte næste, og hvad er dit navn igen?
>> BRANSON: Branson.
>> DAVID J. MALAN: Branson.
Så Branson er nummer to.
Så jeg har tænkt mig at tage dig ud et øjeblik.
Og nu, hvor du hører i dette array?
Så til højre for Grace.
Så igen er vi slags at gøre Grace gøre en masse arbejde her.
Hvor skal vi sætte dig?
Så vi kommer til at skubbe dig til den tilbage, og indsæt Branson der.
Men nu er jeg hævder, at du fyre er færdig.
Men varsel, jeg bruger ikke ekstra plads.
Det er stadig 2 elementer her, 5 herovre.
Samlet array-størrelse er 7, så jeg er ikke snyd, okay?
>> Så nu har vi med Gabe her, de nummer seks, hvor hører du?
Du fik heldig igen.
Så får du til at bo lige der.
Bare tage et lille skridt i den rigtige bare for at gøre det klart, at du er sorteret.
Og nu har vi Neil igen, tal en, hvor vil du hen?
Og nu hvor vi vil begynde at se, at denne algoritme, selvom på første
øjekast føles temmelig smart, se hvad der er ved at ske.
Hvis du kunne træde frem.
>> Hvor vil vi sætte Neil?
Så selvfølgelig her, så hvordan får vi Neil der?
Lad os gøre det trin-for-trin.
Gabe, hvor vil du nødt til at gå?
Jep, så tager et stort skridt, eller to halve skridt til at gøre
et skridt derovre.
Grace, hvor du går?
Godt.
Så endnu et skridt.
Og endelig, Branson?
Et andet skridt.
Og nu kan vi sætte Neil plads.
>> Så nu, fortsætte denne logik.
Selvom vi ikke flytte Neil overstået, og igen, og igen, for at sætte ham
hvor han går, i værste fald næste nummer, vi kan støde kunne
være nummer, siger, at der var en række nul, så vi kommer til at flytte alle
disse fyre.
Antag, at der er et tal, negativ én, så er vi nødt til at flytte
alle disse fyre.
Så vi er egentlig bare slags spejlvende problemet omkring, således at vi er
overføre bekostning fra udvælgelsesprocessen, så indføringen
proces, således at du fyre lige haft at bevæge groft n minus noget
antal trin.
Og at antallet af trin er kun vil at stige som jeg vælger flere numre,
hvis jeg nødt til at holde skubbede jer tilbage, og ryg, og ryg.
>> Så den triste ting er nu alle disse algoritmer er n potens.
Lad os gå videre og tak til dem gutter, og visualisere dem lidt
forskelligt.
Meget godt klaret.
>> [Applaus]
>> Ok.
Værsgo.
Tak for -
>> BRANSON: [uhørlig] holde tallene.
>> DAVID J. MALAN: Nej, du må holde antallet samt.
Ok.
Pænt gjort.
Ok.
Så lad os se, om vi ikke nu kan opsummere hurtigere og mere visuelt,
præcis, hvad der lige er sket her som følger.
Jeg har tænkt mig at gå videre og trække op Firefox.
Vi linker denne demonstration på kursets hjemmeside.
Java er en smule irriterende at få arbejde i nogle browsere disse dage.
Så hvis du leger med det derhjemme, indser du måske nødt til at bruge Firefox
at få det arbejder.
Og hvad jeg har tænkt mig at gøre med dette demonstration er det følgende.
>> Nederst har jeg en hel masse menupunkter, herunder en start-og en
stop knap.
Også, som en sidebemærkning, synes der at være en fejl i disse programmer, hvor du
kan faktisk ikke se start eller stop knappen, medmindre du holder Kommando eller Alt
plus og zoome ind, hvilket mærkeligt nok viser dig flere knapper.
Så bare FYI, hvis du spiller med dette derhjemme.
Nu vil jeg til at klikke på Start på bare et øjeblik, efter angivelse af en forsinkelse på,
ligesom, 200 millisekunder her, bare så vi kan se hvad der sker.
>> Så jeg hævder, at dette er en visualisering Den første algoritme
disse fyre gjorde, boble sortere, hvorved vi byttes folk parvise.
Nøglen indblik i denne visualisering er, at højden af ​​søjlerne
repræsenterer størrelsen af ​​nummeret.
Så højere søjlen er, jo højere tal.
Kortere baren, mindre tal.
Og hvis du bemærker, vi går igennem den første iteration af denne algoritme,
swapping store og små tal, så det lille antal kommer først og
det store antal går til højre.
>> Og så snart vi får i slutningen af ​​matrix mange flere tal end syv, er vi
kommer til at gå tilbage til begyndelsen.
Og forudse dette.
Længst til venstre, er den lille fyr går at bytte til siden, og dette
Processen gentages.
Nu er denne visualisering får hurtigt kedeligt, så lad mig gå videre og stoppe
det, ændre forsinkelsen noget meget hurtigere bare for at komme nu, en fornemmelse for
denne algoritme.
>> Så selvom jeg har drønede den op, det er ligesom opgradering af min processor, køb
en ny computer.
Jeg har ikke fundamentalt ændret min algoritme, men du kan faktisk se mere
tydeligt end med mennesker, at de store tal gennemstrømning op til toppen,
og de små tal boblende ned til bunden.
Og nu denne ting her sorteres.
Og som en sidebemærkning på pladserne, er der blot nogle bogholderi der til
hjælpe dig med at tælle, hvor mange sammenligninger, eller hvor mange swaps har
rent faktisk er blevet gjort.
>> Nå, lad os prøve en af de andre vi så.
Lad mig klikke på boble sortere her og lad mig vælge, og det hele websiden
er en lille buggy.
Lad os acceptere risikoen og køre det igen.
Der går vi.
Så lad os gøre udvælgelsen slags.
Jeg ved ikke, hvorfor menuen vises derovre.
Lad os zoome ind for at fastsætte, at bug, ændre dette til 50 år.
Ah, lad os rent faktisk gør at meget hurtigere.
Fem millisekunder eller deromkring, og Start.
>> Så dette er valg slags.
Så igen tænke over, hvad vi gjorde med mennesker heroppe.
Vi gik gennem rækken, og udvalgte det mindste element igen,
og igen og igen.
Nu er jeg hævder, at stadig var temmelig dårlig.
Det var stadig n kvadreret, give eller tage, men det var i den virkelige verden, en smule
hurtigere, fordi jeg faktisk tog lidt færre trin hver gang.
Men vi kun taler hvad?
Måske 40 eller så barer herinde?
Vi taler ikke 40 mio.
Så det er ikke helt klart for mig, at var en væsentlig gevinst.
>> Lad mig nu gå tilbage og ændre vores tredje algoritme, der blev vælge
indsættelse slags.
Og nu er det virkelig buggy, fordi Menuen burde virkelig ikke være dernede.
Så nu vil vi rulle tilbage op her og starte denne algoritme.
Whoop, start og stop.
Så dette en slags har en smuk mønster til det, vi hvorved er igen
indsætte mennesker, eller i denne sag, søjlerne i
deres passende placering.
Og det er allerede gjort før Jeg vendte mig om.
Men denne ene, også i teorien stadig n potens.
>> Så lad os se om vi ikke kan opsummere disse som følger.
Jeg har tænkt mig at gå videre og bare for at give os en slags fælles måde at tale
om disse ting, så lad mig introducere bare en smule notation her.
Du er ved at se noget, der hedder stort O, fordi det er bogstaveligt talt en stor
O. Og det er en måde, at en computer videnskabsmand eller en matematiker bruger endda
at beskrive køretiden af nogle algoritme.
Hvor mange skridt betyder det egentlig tage?
>> Nu vil jeg genere mig med min håndskrift her i bare et øjeblik.
Men lad mig gå videre og sige, at dette vil være store O herovre.
Og lad mig introducere et andet symbol, et kapital omega.
Omega bliver det modsatte, væsentlige for big O. betragtninger big O
midler, i værste fald, hvor meget tid kan nogle algoritme tage i
form af n er omega vil være, hvor meget tid ville det måske
tager i bedste fald.
Og vi vil se, hvad vi mener med bedste fald på bare et øjeblik.
>> Så lad os starte noget simpelt.
Lad mig starte med en lineær søgning.
Så ikke sortering.
Vi kalder denne lineære søgning.
Og nu, gøre en lille tabel ud af dette.
Og nu, i tilfælde af lineære søgning, i værste fald, er, hvor mange skridt
Det kommer til at tage mig at finde en Antallet af vilkårlige valg?
Og der er n samlede døre eller n samlede antal.
Worst case.
Hvor mange skridt jeg nødt til at tage for at finde nummeret 50 i et array
af n døre?
Og hvorfor?
Fordi det kan være alle de vej over på enden.
Så meget som Jennifer stødt på, at nummer 50 var hele vejen over, så i
worst case lineær søgning er big O n, vil vi sige.
>> Hvad bedste fald hvis du får virkelig heldig?
Det er bare at tage et skridt, eller et konstant antal trin.
Så vi vil beskrive det som 1.
Så dette er temmelig godt.
Hvad nu hvis vi gjorde noget lide binær søgning?
Så binær søgning i værste tilfælde tog, hvor meget tid?
>> [Interposing STEMMER]
>> DAVID J. MALAN: Så egentlig, jeg hørte det i et par steder.
Så det er faktisk logge n, give eller tage, fordi som vi deler listen i halve
igen og igen, og igen, vi er i stand at finde i sidste ende værdi,
hvis det er der, men der er en fangst.
Hvad er den antagelse, at vi er nødt til tager for givet for binær søgning?
Det skal sorteres.
Det er ikke sorteret, kan du opdele ting i halve igen og igen, og du
kan gå til venstre, og du kan gå til højre, og du kan gå til venstre og højre, men du er
ikke kommer til at finde det element, hvis listen er ikke sorteret, fordi
du måske glip af det.
Fordi din heuristisk, for at gå til venstre eller højre vil være behæftet med fejl, hvis det er
faktisk ikke er sorteret.
Så der er en slags skjult omkostning at bruge noget som dette.
>> Nu, lad os gå ind i vores sortering algoritmer ikke søger -
åh, faktisk Lad os gå i denne tomt.
Binær søgning i bedste fald?
Det er også 1, hvis det bare sker for at være i den meget midterste af array, eller
midten af ​​telefonbogen.
Nu lad os gøre boble slags.
Så igen, nu er vi ind i sorterer, ikke de søgninger.
>> I værste fald, hvor mange skridt, vi fordring boble sortere kommer til at tage?
n squared.
Så jeg har tænkt mig at trække det.
Ooh, min håndskrift ser endnu værre når det er forventes, at store.
Ok.
Så det n potens.
Og i bedste tilfælde af boble sortere, hvor mange skridt vil det tage?
1, jeg hørte.
>> SPEAKER 1: n.
>> DAVID J. MALAN: n, jeg hørte.
>> SPEAKER 1: 2.
>> DAVID J. MALAN: 2, jeg hørte.
Må jeg hører 3?
Ok.
Så jeg har hørt 1, n, 2, men lad os samle bortset mindst den første af disse
forslag, 1..
Det er ikke en dårlig instinkt, fordi det slags følger et mønster her.
Men hvis det tager kun 1 trin, hvordan i verden kunne jeg påstå, at listen
sorteres, fordi hvis jeg kun tillades at tage 1 skridt, hvor mange elementer
kunne jeg faktisk tjekke for at være sikker?
Nå, bare 1, hvilket betyder, at der er n minus 1 elementer, der kan være ude af
orden, og jeg bare på tro efter ser på 1 element, at
ting er sorteret.
Så 1 er ikke korrekt her.
Så minimalt, hvor mange skal jeg til at se på?
>> [Interposing STEMMER]
>> DAVID J. MALAN: n minus 1, eller virkelig, n, fordi jeg har brug for at se på alle
element til at sikre, at det er ikke i orden.
Men igen, vil vi sortere i wave vores hænder på de mindre tal og
antage, at n bliver store, de er uinteressant alligevel.
Så det er boble slags.
Og nu, lad os gøre disse to sidste.
Valg sortere, og så vil vi gøre indsættelse slags.
Og så vil vi blæse din sind med noget meget
bedre end alle disse.
Ok.
>> Hvad er det værste tilfælde kører tidspunktet for udvælgelsen slags?
>> SPEAKER 4: n potens.
>> DAVID J. MALAN: n square, jeg hører.
Men hvorfor n kvadreret, intuitivt?
>> SPEAKER 4: Fordi vi gjorde det bare.
>> DAVID J. MALAN: Fordi vi gjorde det bare.
OK.
Godt svar.
Men intuitivt, hvorfor er valg sortere n kvadreret?
Hvad gjorde vi nødt til at gøre igen og igen?
Vi har måttet holde scanning gennem, er dig den mindste, er du den
mindste, er du den mindste.
Og indrømmet, vi var i stand til at tage n trin, så n minus 1, og derefter n minus 2.
Men hvis du slags tilføje dem alle op, eller tage det på tro, som jeg har tilføjet
dem op på forhånd, får vi nogenlunde n kvadreret minus nogle mindre tal.
Så jeg har tænkt mig at kalde denne n potens.
Men med valget slags i den bedste fald hvor mange skridt det er
kommer til at tage mig?
>> SPEAKER 5: [uhørligt]
>> DAVID J. MALAN: Det er desværre stadig n kvadreret, right?
Fordi hvis jeg vælger den mindste element, og vi havde syv personer her,
Jeg kender kun, når jeg kommer til de meget ende, at jeg har fundet den mindste
nummer, hvor han eller hun kan have været.
Men hvordan finder jeg det næste mindste tal?
Jeg er nødt til at gøre en anden pass.
Så i bedste fald, hvad er input til udvælgelse sortere?
Det er en allerede sortere listen, nummer et, nummer to, nummer tre, nummer fire.
Men jeg er en computer.
Jeg kan kun se på en ting ad gangen.
Jeg kan ikke sortere i at tage et skridt tilbage som et menneske og sige,
ooh, det ser korrekt.
>> Jeg kan kun træffe afgørelse korrekthed udvælgelse sortere ved at vælge
mindste tal.
Men selv hvis jeg finder nummer et første, hvis jeg ikke kender noget andet om
de andre numre, som jeg ikke, alt hvad jeg vide, at jeg har været afleveret et array
eller et sæt af døre bag hvilke tal, den eneste måde jeg ved, at en
var den mindste?
Hvis jeg får hele vejen her og indse, damn, den ene var faktisk den mindste.
>> Men hvordan kan jeg så afgøre, at to er den næstmindste?
Ved at gøre det samme ineffektivitet igen og igen.
Så til sidst, med indsættelse slags, hvordan, i værste fald,
vi siger det udfører?
Det er for n potens.
Og hvad med den bedste sag?
Vi vil overlade som en cliffhanger.
Vi vil fylde i den tomme næste gang, men lad mig først foreslå, at vi
fundamentalt gøre det bedre end alle disse, okay?
>> Så tænk selv, hvad indsættelse sortere kommer til at være.
Nå, det var ikke meget dramatisk, fordi jeg er den eneste
der så ændringen.
Wow.
OK.
Så her har vi en noget anderledes demonstration.
Hvis jeg zoome ind her, vil du se, at der på venstre vi har boble sortere, i
midten har vi valg sortere og på længst til højre, vi har noget, vi
har ikke kigget på endnu kaldet fusionere slags.
Men overveje, hvad vi har været gør her hidtil i dag.
Da Jennifer først kom op på scenen, vi gik gennem rækken af ​​numre
igen og igen, med lineær søgning, og vi fik lineær køretid, big O
n, så at sige.
>> Når vi nu overveje den første uge af klasse, da vi havde del og hersk,
og vi havde telefonbogen tåreflåd, og Jennifer, og vi kollektivt
gearede at centrale indsigt, som var at gentage dig selv igen og igen af
en eller anden måde at smide væk, smide, smide halvdelen af ​​problemet, eller
generelt, dividere et problem i halve, og derefter behandle den mindre stykke af
problemet så begrebsmæssigt ækvivalente til den anden, en eller anden måde gjorde vi
fundamentalt bedre.
Men med boble slags, med udvælgelse sortere, med indsættelse sortere, vi har måske
ingen sådanne indsigter, Jennifer gjorde.
Vi temmelig blot gik tilbage og frem en hel masse gange, og vi
sammenknebne tingene lidt, bytte i denne rækkefølge, måske
indsætter eller vælge.
Men i slutningen af ​​dagen, gjorde jeg en masse akavet walking frem og tilbage.
Vi gjorde ikke rigtig udnytte noget Smart ligesom Jennifer gjorde ligesom at dividere
og erobre.
>> Så fusionere sortere, derimod, som vi vil ikke se til næste uge, går det
at udnytte, at centrale idé ved at dividere input, og derefter halvering, og derefter
halvering, og derefter halveret.
Og på hver iteration af denne løkke, sortering af venstre halvdel og højre
halvdel, så den venstre halvdel af venstre halvdel, og den højre halvdel af den venstre, så
den venstre halvdel af den højre halvdel, og den højre halvdel af den højre halvdel.
Og gentage igen og igen.
>> Så du vil se denne visuelt, men dette er, hvad der venter os i næste uge.
Og generelt, når vi tænker lidt lidt hårdere på en sådan problem.
Vi har n kvadreret på venstre side, n kvadreret i midten, og n
log n til højre.
Så der er din rigtige cliffhanger.
Vi vil se dig på mandag.
>> [Applaus]