[MUZIKO ludi] 

DAVID J. Malan: Bone. Do bonvenigas dorso. Ĉi tiu estas CS50, kaj la estas la finon de semajno tri. 

Do memoras en la lastaj semajnoj, ni estis pasi sufiĉe da tempo sur C, en programado, en sintakso. Kaj estas tute normala, se vi ankoraŭ baraktante kun Problemo Serio 2, esti banging vian kapon kontraŭ la muro. Ĝi estas kamufla-aspekta erarmesaĝojn kaj bugs kiu vi ne povas sufiĉe persekuti malsupren. Ĉar, ripozi certigis, ke en nur kelkaj semajnoj tempo vi retrorigardas la aĵoj kiel Cezaro, kaj [? V-genair,?] eble eĉ Crack, kaj rimarki kiom multe vi venis en mallonga periodo de tempo. Do se tiu estas ajna konsolo, pendigi tien nun. 

Hodiaŭ, tamen, ni komencos transiro al aĵoj pli alta nivelo. Kaj ni komencas preni por koncedis ke you guys scipovas plani, aŭ Almenaŭ la komencoj de ke komforto nivelo. Kaj ni komencas konsideri kiel ni povas irad desegni programoj pli efike. Kiel ni povas iri optimizando la efikeco de nia algoritmoj, kaj ĝenerale solvanta pli interesaj problemoj. Kaj komencante preni por koncedis ke, se ni volis, ni povus programi ĉe ajna el la ekzemploj havas en menso. Do hodiaŭ, ni ne tuŝas la klavaro por ajna formo de kodo. Estos multe pli alta nivelo, kaj fine, pri problemo-solvado. 

Do por atingi tiun punkton, mi proponas ke la sekvaj sep ortanguloj reprezentas sep pordoj, malantaŭ kio estas tuta aro da nombroj, inter kiuj estas la nombro 50. Lasu min projekti tion en ĉi tiu ekrano tie ankaŭ. Kaj proponas ke ni bezonas volontulon por helpi min trovi nombro antaŭ la interreto tie vidi. Venu supren, en la rozkoloraj. Ĉio bone. Kio estas via nomo? 

Jennifer: [inaudibles] 

DAVID J. Malan: Pardonu? 

Jennifer: Jennifer. 

DAVID J. Malan: Jennifer. Bone, Jennifer. Nice to meet you. Venu supren. Tiuj ĉi tie estas sep pordoj, kaj kio Mi ŝatus ke vi faru por ni ĉi tie, antaŭ ĉiuj de viaj samklasanoj, estas trovi nin la numero, 50. Por trovi numeron, vi povas peek malantaŭ iu el tiuj pordoj per simple tapping sur unu el la pordoj, kaj ĝi malkaŝos lian numeron. Kaj ni vidos kiel rapide vi povas trovi nin la numero, 50. 

15. 16. 50. Bele farita. Ĉio bone. Ronda de aplaŭdo por Jennifer. 

[Aplaŭdo] 

Ĉio bone. Do kio estis via strategio por trovi la numero, 50? 

Jennifer: Um, mi pensis ke eble se - [Inaudibles] 

DAVID J. Malan: Ho. Donu ĝin unu sekundo. Do estis via strategio por trovi la numero, 50? 

Jennifer: Do mi simple komencu ĉe la komencas vidi, kion la unua numero estis, kaj tiam mi pensis, eble se ili estas ordo, mi nur konservi tapping pli alte? 

DAVID J. Malan: okej. Kaj ni ŝajnas esti trovita ke por esti la kazo. Kvankam, ni ŝelo redonas la manteloj malmulta, kaj vi volas iri antaŭeniris kaj malkaŝi la alia pordo vi povus esti elektita? 

Jennifer: Ho, kara. 

DAVID J. Malan: Ah. 

Jennifer: Mi ĵus bonŝanca. 

DAVID J. Malan: Do vi havas sorton. Ĉio bone. Do ne estas malbona. Sed tio estas interesa komprenon, ĉu ne? Se vi supozis, kaj vi faris alveni, ja, iom bonŝanca tie. Sed se vi supozas ke la numeroj estis ordo, vi povas esti pli preciza pri kiel kiu influis via konduto? 

Jennifer: Do se ili ordo, mi pensis eble plej malgranda ĝis granda. 

DAVID J. Malan: okej. 

Jennifer: Aŭ se tio finis estante vere granda, tiam granda ol plej malgranda. 

DAVID J. Malan: okej. Tiel granda ol plej malgranda, aŭ plej malgranda ĝis granda. Sed mi proponas, supozu ke vi havis alveninta malfeliĉa, kaj supozu ke ili ne estis, fakte, ordo, kiom da tiuj pordoj eble vi devis peek malantaŭ en tiu plej malbona kazo? 

Jennifer: Ĉiuj el ili. 

DAVID J. Malan: Ĉiuj el ili. Do ni ĝeneraligi ke kiel n. Tie okazas al esti 7, sed ni pli ĝenerale diras, ke la n pordojn en la ekrano tie. Do, en la plej malbona kazo, vi havus rigardi malantaŭen 7 pordojn, aŭ n pordoj. Kaj tiel ĉi vere estas, estas iom da sorto hodiaŭ, sed estas vere lineara Algoritmo de varoj, kvankam vi Estis speco de salti ĉirkaŭe. Ĉu tio estas justa? 

Jennifer: Jes. 

DAVID J. Malan: Nu, mi volas vidi se via strategio ŝanĝojn se mi movi nin nia dua ekzemplo ĉi tie kun 7 malsamaj pordoj. Sama nombroj, sed ĉi tiu tempo estas ordo. Kio estas via strategio tie tuj estos, provante meti el via menso, kion la aliaj numeroj estis - 

Jennifer: okej. 

DAVID J. Malan: - pli frue? 

Jennifer: Ni komencu kun la unua. 

DAVID J. Malan: Bone. Komencu kun la unua. 4. Sed kie vi intencas iri, kaj kial? 

Jennifer: 4 estas vere malgranda. Do, se ili estas speco eble plej malgranda al pli granda, ĝi devus esti duoble, kaj -. 

DAVID J. Malan: okej. Ni vidu, kion vi opinias? 

Jennifer: Provu la lasta. Nice. 

DAVID J. Malan: Tre bele farita. Ĉio bone. 

[Aplaŭdo] 

DAVID J. Malan: okej. Do vi fakte faras ĉi terure, ĉar vi fari ĝin tre bone. Kiu lasas nin nekapablaj fari kelkajn punktojn. Do ni provu ruliĝi reveni ĉi tien. 

Jennifer: okej. 

DAVID J. Malan: Tre bone farita, tamen. Do vi komencis en la komenco, Vi vidis, ke estis 4, tiam vi movis al la fino. Sed supozas ke vi ne ricevis bonŝanca tie, kaj supozu 50 estis aliloke. Kio via tria paŝo estis? 

Jennifer: Reiru al la komenco. 

DAVID J. Malan: Reiru al la komenco. Bone, do vi devus jam tuŝis ĉi pordo, kiu estis 8. Ĉio bone. Do tio ne estas 50. Kie vi aspektis poste? 

Jennifer: Se mi ne konas ili ordo. 

DAVID J. Malan: Correct. Nu, se vi efektive scias ili ordo - 

Jennifer: Ho, ne scias, yeah. 

DAVID J. Malan: - sed vi ne scias, kie 50 estis ankoraux? 

Jennifer: Just plu iri. 

DAVID J. Malan: Bone. Akcepti. Konservu iras. Bone, ke mi povas labori kun ili. 

Jennifer: okej. 

DAVID J. Malan: Nun, se vi estas nur iri plu iri, kio estas via algoritmo devolving apogita en. 

Jennifer: La lineara -. 

DAVID J. Malan: Estas speco de lineara. Sed mi proponas, estu Mi surmetis la makulo. Lasu min refreŝigi la paĝon. sama nombro, sama aranĝo, sama pordoj. Sed pensu reen al tiu unua tago klaso kiam oni ŝiris telefono libro en duono, speco de, kaj kio estis nia strategio tie? 

Jennifer: Komencdato en la mezo. 

DAVID J. Malan: okej. Do starti je la mezo. Do ni iru antaŭen kaj simuli tion. Komenci je la mezo de malkaŝi tiun pordon. Do la nombro 16. Do kio estus la forta viro faris, kiuj disŝiris la telefonon libro en duono, por atingi la najbaran konjekton? 

Jennifer: Iru kun cxi tiu duono. 

DAVID J. Malan: Kaj kial al la dekstra? 

Jennifer: Se ili estus speco de malgranda al pli granda, tiam 50 devus esti en tiu fino. 

DAVID J. Malan: Bonan. Plene racia. Do kiel telefono libro, vi iras al la dekstra kontraste al maldekstre, sed ĉi tie estas la ŝlosilo takeaway. Vi nun povas forĵeti, aŭ ŝiras for, duono de ĉi tiu problemo, lasante vin ne kun 7 pordoj, sed vere kun nur 3. Kiu estas proksimume la duono de la grandeco de la problemo. Ĉio bone. Do nun tio, kion vi havus farita post vi ĝuste iros? 

Jennifer: Do 16 estas ankoraŭ sufiĉe malgrandaj, relativa al 50, do eble mi provos, kiel, ĉi tiu. 

DAVID J. Malan: Bone. 42. Bone, do kion estas via instinkto diras al vi? 

Jennifer: Mi povas forĵeti ĉi tio kaj tiam simple - 

DAVID J. Malan: okej. Bone, vi povas forĵeti la maldekstra duono tie. 

Jennifer: - elektu ĉi tiu. 

DAVID J. Malan: Kaj la dekstran. 

Jennifer: Jes. 

DAVID J. Malan: Do kvankam estas malfacile vidi eble, kiam ekzistas nur 7 pordoj, pensi, nun, la konsekvenco de la Algoritmo vi ĵus aplikita. En la antaŭa kazo, vi faris akiri bonŝanca, kiu estis granda. Sed vi faris uzi heŭristiko, Mi dirus. Vi uzis specon de via instinktoj, kaj scii ĝin ordo, se ĝi estas sufiĉe malgrandaj komence, evidente, ni devas iri pli dekstre. Sed en iu senco, vi havas sorton, ĉar eble tio estis la nombro 100, kaj eble 50 estis pli en la mezo. Eble 50 estis eĉ pli tie. 

Sed kion vi faris iom alie tiu tempo estis, vi faris la samon denove kaj denove. Kaj mi dirus ke kion vi ĵus ne, kvankam influita de la telefono libro ekzemple, estas io multe pli algoritma, kaj multe malpli speciala cased. Multe malpli instinkta. Do, en la fino de la tago, kiel farus vi priskribas la efikeco de la unua algoritmo, kien vi venis maldekstre dekstren, kontraý la dua algoritmon ĉi tie? 

Jennifer: Ĉi tiu devus, kiel, eble Halve la tempo, aŭ eĉ pli, jes. 

DAVID J. Malan: Bone, eble eĉ pli. Ni puŝi iom pli malfacila en tiu. Kio vere, se ni daŭrigas tiun logiko, ni definitive redukti al la duono de la rula tempo kun ĉi tiu dua algoritmo ĵetante sin duonon de la nombroj, sed kion ni faru la sekvantan ripeta, kiam Jennifer malkaŝis la dua numero? 

Ni redukti al la duono de la numeroj de pordoj denove. Kaj poste kion ni faros post tio, se estis pli pordojn por ludi kun? Ni estus Halve ilin, kaj denove, kaj denove, kaj denove. Kaj tio estis ĝuste kiel vi knaboj ĉiuj piedo en la unua semajno de klaso, duono el vi sidas duono vi sidas meze de vi sidiĝi, ĝis unu sola animo staris. Kaj ni diris ke la rula tempo de tio, la nombro da paŝoj prenis estis en la ordo de kio? 

Parolanto 1: [inaudibles] 

DAVID J. Malan: Do log bazo 2 de n, aŭ simple pli simple, ensaluti de n. Do io logaritma. Kaj la grafeo ne estis rekta linio ke nur plimalbonigis kaj malbona, estis tiu interesa kurbo kiu ne akiri tiel malbona tempo. Do ni tenas al tiu ideo. Ni dankas al Jennifer. Danke tiel por veni supren. Kaj, unu sek. Neniu skribtablo lampoj hodiaŭ, sed ni ja havas CS50 streso pilkojn. 

Jennifer: Yay. 

DAVID J. Malan: Bone, ĉi tie. Dankon por fali la streĉo ĝis ĉi tie. Ĉio bone. Do ni vidu, se ni ne povas nun formaligi tiun iom pli. Do denove, kion ni ĵus faris estis esence la sama afero kiel ni faris en tiu unua semajno. Sed anstataŭ fino kun nur linearaj algoritmo, kiun ni reprezentas antaŭe kiel tiu rekta linio, per kio, se ni metis pli pordon la ekrano, kaj poste Jennifer farus ili devis rigardi, potenciale, malantaŭ pli pordo. Se ni metas du pordojn, ŝi povus havi rigardi malantaŭ du pordoj. 

Kaj do, tie estis jena lineara rilato inter la amplekso de la problemo en, ekzemple, la x-akso, kaj la kvanton de tempo necesa por solvi sur la y. Sed la foto mi aludante pli frua estis tiu verda linio. Verda intence, ĉar ĝi simple sentis pli bone. En teorio, la algoritmo, kiam ni faris kun la telefono libro, kiam ni faris kun vi infanoj rakonti reciproke, kaj en la dua kazo, kiam Jennifer nur faris ĝin ĉi tie, estis speco de fundamente bona. Ĉar ĝi estis ne nur duoble pli rapide. Ne estis eĉ kvaroble pli rapida. Ĝi estis tute dependa de kion la grandeco de la eniga estis, kiel al kiom paŝojn ĝi finfine prenis. 

Kaj tial tiu simpla ideo, ke ni ĉiuj portis por sentado kun la telefono libro, povas simile esti aplikita al io kiel tio. Kaj ĉi tiu povus esti pli hazarde konata kiel, kiel vi povus imagi, dividi kaj venki. Ne kontraste kion ni faris, kompreneble, kun la telefono libro. 

Sed la _pseudocode_, revokon, estis jena. Do ni ne faros ĉi denove, sed memoras tiu unua semajno, ni ĉiuj ekstaris kaj tiam duono el vi sidiĝis, la duono de vi sidiĝis, duono el vi eksidis. Tiu algoritmo estis implementado en bito de kaptiloj maniero, en tio, Ne estis nur unu el min rakonti, fundamente, pli efike. En tiu kazo, mi estis utiligante malĉefan rimedo. Ordigi de, multnombraj CPU, multnombraj cerbon, multnombraj inteligenta homo en la ĉambro helpis min preni de io lineara ion logaritma, de io ruĝa al io verda. 

Sed en tiu kazo, Jennifer sole povas funde plibonigi sur la agado de ŝia unua algoritmo de, denove, nur pensante iom pli malfacila. Kaj nun, kiam venas tempo por apliki tion, elŝeligi kio linioj de kodo povas skribi tiajn ke vi povas ripeti ilin denove, kaj denove, kaj denove, ia en looping modo. Ĉar vi ne tuj havos la lukso, kiel Jennifer faris unue, al nur havi tutan aron da oj kaj diru: hmm, se tiu unua nombro estas 4, lasu min salti tuta vojo al la fino. Ooh, se tiu numero estas tro granda, lasu min movi arbitre reen al la dua elemento. Vi trovos ke ĝi tuj estos multe malfacile formaligi kion ni homoj preni por donita kiel tre racia heurísticas, sed komputilo estas nur faros kion vi sciigus tion fari. 

Nun ĉi havas tre interesan implikaĵoj. Ĉi tiu grafikaĵo estas speco de intencis ordigi de Colmar vide, sed rimarki, kie estas la rekta linio en ĉi tiu grafikaĵo? Kie estas la lineara grafikaĵo ke ni nomas n? Nu, estas speco de cele la fundon de tiu bildo, ĉu ne? Do ĉiuj ni faris estas ni ia zomita al la x-akso kaj la y-akso por provi akiri senton de kio aliaj specoj de kurboj aspekti. 

Kaj la specifaj detaloj de la matematika esprimoj hodiaŭ ne gravas tiom da, sed rimarkas ke estas multe da algoritmoj kiuj estas multe pli malbone ol iu kiu estas lineara. Ja, n cubed aspektas sufiĉe malbone. 2 al la n aspektas sufiĉe malbone. n kvadrata aspektas sufiĉe malbone. Kaj ni vidos kion iuj el tiuj povus esti en la realo nuntempe. Kaj log n ne sentas tiel malbone, sed pli bona ol n estas log bazo 2 de n. Sed vi scias, estus estinta inkluzive pli mirinda se Jennifer, aŭ se ni, tiu unua semajno, venis kun iu kiu estas log de logo de n. 

Do alivorte, ne estas tio tutajn gamo de eblaj solvaĵoj al problemoj, sed eĉ tie, avizo kio okazos. Kiam mi malzomi, kiu el tiuj kurboj tuj pruvi al esti la absoluta plej malbonajn el la sur la ekrano nun? Do la n cubed aspektas bela malbona nuntempe. Sed se ni malzomi kaj vidi pli de la x kaj la y-akso, kiu tuj regi finfine? Do fakte rezultas ke 2 al la n, kaj vi povas kompreni tion ĉi nur ŝtopanta en iu pli granda nombroj, kaj vi vidos ke 2 al la n, ja, ricevas pli multe rapida. Se ni vere malzomi, a 2 al la n algoritmo absolute sucks. Mi volas diri tuj preni sufiĉe da tempo por la komputilo Mazar tra. 

Sed vi vidos la tempo, speciale kun estonteco problemo aroj kaj eĉ fina projektoj, estas via datumoj aro ricevas grandajn, ĉiuj rajtas? Eĉ en la unua versio de Facebook, kiel la nombro de amikoj, kaj la nombro de registritaj uzantoj atingis grandan, vi povas ordigi de telefono en kaj apliki iun kun lineara serĉo, aŭ tre simpla ordigado algoritmo, kiel ni vidos hodiaŭ. Vi devos komenci pensi pli malfacila kaj pli malfacile pri tiuj problemoj. Kaj la tipoj de problemoj lokoj kiel Facebook, kaj Google kaj Microsoft, kaj aliaj laboras sur estas ĝuste tiuj speco de granda datumoj ia demandoj ĉiufoje tiuj tagoj. 

Ĉio bone. Do Jennifer sukceso en tiu dua algoritmo, sincere, ŝi faris mirinde bone la unuan fojon, sed ni skribi ĝin kiel sorto tiel ke ni povas fari ĉi tiu punkto. En la dua kazo, ŝi leveraged an algoritmo kiu ripetis denove kaj denove, sed ŝi prenis por koncedis certa supozo, ke ni permesis ŝi, sed ŝi eksplodis detale al la duan fojon, ke sxi ne havis la unua fojo. Kiu estis kio? 

Ke la listo estis ordo. Tuj, kiam la listo estis ordo, ni asertas ke Jennifer povis fari fundamente bona. 7 pordoj, jes, ne estas tiel interesa, sed supozas ke ni estas 7 milionoj pordoj. Ensalutu de n estas definitive irante plenumi multe, multe rapida en la longa. Sed ŝi devis havi la pordojn ordo por ŝi. Nun, mi prenis la liberecon fari tion anticipe sur la komputila ekrano ĉi tie, sed supozas ke Jennifer devis fari tion mem? Supozu ke la pordoj en demando reprezentis datumoj en la datumbazo, aŭ amikoj registrita Facebook, aŭ neniu retpaĝoj en interreto ke diversaj retejoj povus bezoni al indekso aŭ serĉo finiĝis. 

Supozu ke vi ĵus havis krudaj datumoj aro kaj estis lasita al vi, aŭ al Jennifer fari tion ordigado? Tio, pli ĝuste, postulas, ke ni respondu la demando, nu, kiom da tempo estus preninta Jennifer, aŭ eĉ mi, ordigi tiujn numerojn anticipe tiel ke ŝi povis utiligi tiun? Ĝuste? Pro la implico, kompreneble, estas se ĝi prenas min sufiĉe tempo por ordigi la ciferoj, kiujn la heck zorgas ke vi povas trovi nombro kiel 50 tiel rapide, kiel en Jennifer la kazo, se ni pli ol premita la kvanto de tuta tempo ĝin prenis por ordigi aferojn anticipe? 

Do ni vidu, se ni ne povas la pentri la bildon tie. Mi havas tutan faskon pli streso pilkoj, se tio helpas rompi la glacion tie. Kaj se vi ne atentas, ni bezonas sep volontulon - on, OK. Wow. Do ni ne devas elspezi sur tablo lucernojn similas. Ĉio bone. Do kiel pri vi du en fronto. Kion pri vi du infanoj en dorso. Do jen kvar. Kion pri vi en fronto kvin, ses kaj sep. Ĝuste tie. Via amiko estas montrante vin, tial vi ricevos la premion. 

Ĉio bone. Venu supren. Kaj kial ni ne havas vin infanoj venu ĉi tien. Mi tuj donos al vi ĉiu numero. Kaj iru antaŭen kaj aranĝi mem idente al kio bildigita sur la ekrano. 

[Intermetante voĉoj] 

DAVID J. Malan: OOP, sorry. Insekto. Ĉio bone. Nu, jen ni iru. Numero kvin. Numero ses. Unu, du, tri, kvar, kvin, ses, sep. Ho, tio estas mallerta. 

Speaker 2: mi nur ricevas -. 

DAVID J. Malan: Bona traktadon. Ĉio bone. Dankon por partopreni. 

[Aplaŭdo] 

Akcepti. Ĉio bone. Do ni havas kvar, du, ses, unu, tri, sep, kvin. Perfektigi tiel ni havas sep volontuloj ĉi tie, kiuj estas egalaj je larĝeco al la tabelo, ke ni ludas kun la antaŭaj. Kaj mi elektis sep por kialoj ke estos ĝuste oportuna en iomete. Kaj mi tuj proponi unua kiu ni ordigi tiujn sep volontuloj. Se vi ŝatus, unue, por diri saluton kvankam. Ekde ĉi tiu tuj estos mallerta pluraj minutoj. Enkonduki vin. 

GRACIA: Saluton, mi estas Grace. Mi estas sophomore en Leverett Domo. 

Branson: Hi. Mi Branson. Mi estas novulo en Veldo. 

Gabe: Hi. Mi Gabe. Mi estas juna en Cabot. 

Neil: Mi estas Neil. Mi estas novulo en Matthews. 

JASON: Mi Jason. Mi estas novulo en Greenough. 

MIKE: Mi Mike. Mi estas novulo en Grays. 

Jess: Mi Jess. Mi estas sophomore en Leverett. 

DAVID J. Malan: Bonega. Ĉio bone. Nu, dankon al ĉiuj niaj volontuloj tie tiom. Kaj la defio al la mano nun tuj esti ordigi de ĉi tiuj infanoj, sed tiam ni tuj devos pensi iom malmola pri kiel kompetente ni efektive ordo ilin. Do ni unue provu tion. Vi infanoj povas vidi reciprokajn nombroj nur metante ĉirkaŭ la anguloj. Antaŭen kaj preni kelkajn sekundojn, kaj speco vin el malgranda en la lasis al plej dekstre. Iru. 

Akcepti. Bona. Tio estis vere Darn rapida. Nun iu tie, kiu estis la algoritmo ke tiuj infanoj aplikita? 

Parolanto 1: Malplej al la plej granda. 

DAVID J. Malan: okej. Almenaŭ al la plej granda estas vere ordigi de la objektiva, sed mi ne certas ke estas vere algoritmo. Almenaŭ al la plej granda ne diri Mi iom post paŝo, kion fari. Jes? 

Parolanto 1: [inaudibles] 

DAVID J. Malan: okej. Do se vi vidas personon pli malgranda ol via numero, tiam kopii al dekstre de ili. Por ke estas nun ricevas pli esprima, pli kiel algoritmo, ĉar vi povas diri, se tio, tiam tiu. Do ni havas ian kondiĉa konstruo. Kaj ĉi tiuj infanoj ŝajnis fari ke en kelkaj tempoj, ĉar kelkaj el vi kopiis iom de malproksime. Kaj estis supozeble ian looping okazas en iliaj mensoj. 

Sed ni provu formaligi tio. Se vi infanoj povis nuligi reen al ĉi aranĝo. Ni vidu se ni ne povas formaligi tiun oni iom, kaj poste demandi la demandon, nur kiom efikaj estas tio? Kompreneble, kiam ni devas fari tion pli malrapide, ĝi tuj sentas kiel bono de algoritmo, sed ni vidu, se ni povas meti niajn fingrojn sur la preciza paŝoj. 

Do vi du infanoj estas kvar kaj du. Aŭ vi ĝentila aŭ malĝusta ordo? Evidente malĝusta. Do ni interŝanĝis. Nun mi iros por movi flanken ĉi tie kaj diru, kvar al ses. Ĉu vi estas ĝentila aŭ malĝusta? 

Gabe: Correct. 

DAVID J. Malan: Correct. Ses kaj unu? Nope. Interŝanĝi. Do jen du svopoj. Ses kaj tri? Nope. Interŝanĝi. Ses kaj sep? Aspektas bone. Sep kaj kvin? 

Jess: [inaudibles] 

DAVID J. Malan: OK, interŝanĝi. Kaj ordo. Ĉio bone. Do evidente ne, ĉu ne? Do tie estis pli okazas. Sed ja, tiuj knaboj, eĉ nur instinkte. tenis moviĝas. Ili ne nur ĉesas, kiam ili korektis unu problemo. Tiel. Ja, mi tuj devos fari la samon. Mi tuj devos ordigi de rebobinado reen al la komenco de ĉi tiu problemo, aŭ la komenco de ĉi tiu tabelo de popolo, ni komencu nomante ilin. 

Kaj nun kio devus mia algoritmo en la dua paŝo estu? 

Parolanto 1: Sama afero. 

DAVID J. Malan: Sama afero. Kaj jen, Mi komencas ŝatas, ĉu ne? Tuj kiam vi povos trovi vin mem fari la sama afero denove kaj denove, tio estas igante pli kiel algoritmo, kaj malpli homa instinkto. 

Do nun, ni tie iri denove. Du kaj kvar? No Kvar kaj unu? Ha, tie ja estis kelkaj labori ankoraŭ farenda. Por kaj tri? Bona. Kvar kaj ses? Ses kaj kvin? Ses kaj sep? OK, nun faris. OK, ne. Mi devas iri reen. 

Do nun, denove, ni faras ĉi iom pli intence. Kaj nun, estas nur unu cerbon ekzekuti tiu algoritmo. CPU, se vi volas. Kaj sincere, ke estas la sola rimedo Ni tuj havas aliron al. Kaj unufoje ni reiru al klavaro kaj havi iun kiel C en nia dispozicio, ni nur skribi programon kiu povas fari unu afero je tempo. Dum ĉi tiuj infanoj antaŭ momento, ni leveraged ilia kolektiva cerbostreĉa kiel vi infanoj faris en semajno nulo. Do ni daŭre fari tion. 

Du kaj unu. Du kaj tri. Tri kaj kvar. Kvar kaj kvin. Kvin ses. Ses kaj sep. Faris? Do mi estas, sed lasu min ludi advokato de la diablo. Ĉu Mi, la speco de komputilo kiu ĵus faris pasas tra ĉi tiu tabelo de homoj, sciu ke mi faris? 

Parolanto 1: N-ro 

DAVID J. Malan: Do kial? Kion mi devas fari por konkludi decide, ke mi faris? Probable pli pasas. Ĝuste? Pro ĉio mi scias el kiu antaŭaj pass estas ke mi korektas eraron. Kaj tio signifas, eble tie estas ankoraŭ alia eraro ke mi bezonas korekti. Do mi nur povas esti certa per rebobinado, kaj tiam kontrolanta, unu al du, du kaj tri, tri kaj kvar, kvar kaj kvin, kvin kaj ses, ses kaj sep. OK, nun mi faris nenian laboron. 

Mi povas certe memoras, ke mi ja ne faris labori kun iu kiel variablon, ŝatas al int. Nomu ĝin svopoj, kaj se svopoj estas 0 kiam mi tien, kaj gxi komencis je 0, tiam Mi estus nur stulta plu iri tien kaj reen, kontrolanta denove, kaj denove, kaj denove, ĉu ne? Ĉar vi get ŝtopita en kelkaj speco de senfina iteracio. Tuj, kiam ekzistas 0 svopoj, ni povas aserti, ke tiu algoritmo estas ja kompleta. 

Nun, ni metis nomon sur tiu ĉi. La algoritmo, kiun Mi proponas ke ni nur implementado estas iu nomita bobelo varon, konata kiel tiaj en la senco ke la numeroj kiuj estas pli grandaj speco de bobelo sian vojon sur la supron, aŭ supren al la fino de la tabelo de nombroj. Sed kiom efika estis jena algoritmo? Kiom da ŝtupoj ĉu mi fizike devas prenu, ekzemple, ordigi tiujn sep homoj? 

Kvar al kvin? OK, tro multaj estas finfine tuj estos la respondo. Sed eĉ tiam, la specifa nombro ne estas tiom interesa. Ni ĝeneraligi ĝin kiel n. Do, se mi n popolon tien, kaj ili estis, ia, en hazarda ordo en la komencante, en tiu originala ordo. Nu, kiom da ŝtupoj ĉu mi devas preni sur la unua paŝo? Ĝi estis unu, du, tri, kvar, kvin, ses, kaj ili estas sep personoj, tiel jen sep, ses -, do tio n minus unu paŝas la unua fojo. 

Nun, kiom da ŝtupoj ĉu mi devas preni kiam mi rewound? Nu, ni povus efektive duobligi ke se Ni vere volis, sed por nun mi estas nur intencas diri, ĉiuj pravas, alia n minus 1. Do la n minus 1 tuj akiri ĝena por sekvigi, do ni nur rastas iomete. Do 2n paŝoj. Do 14 paŝoj, donos nek preni. 

Multfoje prenis mi paŝo la venonta tempo? Nu, estas 3n. vere. Kaj nun, en la plej malbona kazo, Ekzemple, kiom da fojoj mi volis havi iris tien kaj reen, tien kaj reen, ekzekuti tiu algoritmo, interŝanĝante homoj sur ĉiu paŝo, proksimume? Ĝi estas fakte n kvadratoj, ĉu ne? 

Ĉar en la plej malbona kazo, vi povas speco de opinias pri tiu intuicie, kvankam ĝi povus preni iom iom da tempo por enprofundigi in En la plej malbona kazo, kio estus tiuj sep homoj aspektis kiel, en kondiĉoj de la aranĝo de siaj ciferoj? Tute malantaŭen, ĉu ne? Kaj ĝuste por simuli tion, kio estas via nomo denove? 

MIKE: Mike. 

DAVID J. Malan: Mike? OK, Mike, vi povas simple aliĝi min super ĉi tie dum nur unu dua? Efektive, ne. Pardonu Mike, ni rebobinado. Kio estas via nomo denove? 

Neil: Neil. 

DAVID J. Malan: Neil. OK, Neil, vi venos kun min, se vi ne gravas. Do mi tuj proponi, nur por simpleco, ke Neil estas nun en siaj plej malbona ebla kazo. Sed memoru, kiel mi implementado mia algoritmo. Mi komparas, komparante, komparante, komparante, komparante, oh. Nun tiuj infanoj estas ekstere de ordo, do mi ripari. Do you guys interŝanĝi. Sed pripensu nun, kiom pli malproksima tio Neil devas iri? Ĝi estas proksimume n. Vi scias, ĝi estas ne reale n. Estas kiel, n minus 1, sed mi ricevas tedita konservanta trako de la eta nombro, do ni nur nomas ĝin n. 

Do se Neil movas unu paŝon maksimume ĉiu tempo, kaj movi unu paŝon Neil, Mi devas fari ĉi vere teda pass tien kaj reen, ĉi tiu estas krude faranta tion, n paŝoj, entute n fojoj, ĉar ĝi estas tuj portos min ke multaj ŝtupoj por atingi Neil ĉiuj la vojo, kie li apartenas. Lasu ĉiuj aliaj se vi infanoj ĉiuj estis mis-ordigita tiel. 

Do ni nomas bobelo speco n kvadratoj. La rula tempo de ĉi tiu algoritmo, la okupas de ĉi tiu algoritmo, la efikeco de ĉi tiu algoritmo, ni estos ĝuste priskribi pli ĝenerale kiel n akordis. Kiu estas bela, ĉar mi povis fari la sama ekzemplo kun ok personoj, naŭ popolo, miliono da homoj, kaj ke respondo ne tuj ŝanĝos. 

Do se vi infanoj ne gravas, ni reset vi kie vi komencis. Kaj ni provu du aliaj aliroj kaj ĉu ni ne povas fari funde pli bona ol ĉi tio. Do ĉi tiu fojo, mi tuj proponi speco de malsamaj algoritmo. Tio estis tre saĝa el ni lasta fojo, kaj vi infanoj pravis havi la dekstra instinktoj de nur speco de swapping duoplarĝa. Sed se mi vere volis alproksimigi tiun simple, kaj mia celo estas movi ĉiuj iom nombroj ĉi vojo kaj puŝi ĉiuj el la grandaj numeroj kiu maniero, kial ne mi nur faras tion en la plej naiva maniero ebla kaj vidu se mi povas fari pli bone ol kio estis sufiĉe kompleksa algoritmo? 

Do ni vidu. Kvar estas sufiĉe malgranda nombro, do mi estas tuj forlasos vin tie momento. Ooh, numero du estas eĉ pli bona. Do vi povas simple paŝas antaŭen nur momenta? Ĉi tio estas nuntempe mia malgranda prikalkulis kandidato, kaj mi iros por memori ke kun, kiel, variablo. Sed mi tuj subteni kontrolanta. Ĉu estas iu kies nombro estas malgranda? Ses, ne. Ho, tie estas Neil denove. 

Do mi tuj peli vin speco de koncepte. Neil venos plue. Kaj nun, la variablo kiu Mi uzas por sekvigi kiu havas la plej malgrandan nombro estas ĝisdatigita enhavi Neil loko. Nu, vidu. Tri, sep, kvin. Bone, mi scias Neil estis la plej malgranda. Kio estas la plej simpla afero al mi, fari nun? Mi ne tuj malŝparos mian tempon por nur bobelis Neil unu loko al la maldekstra. Kial ne Mi nur metis Neil kie li apartenas, kiu estas kompreneble kie? 

Tuta vojo al la komenco. Do Neil, venu kun mi. Kaj kio estis via nomo denove? 

GRACIA: Graco. 

DAVID J. Malan: Graco. Akcepti. Do Graco, bedaŭrinde, vi estas speco de la vojo. Nu do kiel ni solvi tiun problemon? Ĝuste? Se tio estas tabelo, ekzistas nur sep lokoj. Memoru ke, kun Rob, ni parolis pri deklarante aĝoj, kaj ni nur havis finia nombro de aĝoj? Sama ideo tie. Ni havas nur finia nombro de ints. Graco estas speco de en nia maniero, tiel kiel ni ripari? 

La plej simpla maniero estas kiel, Graco, sorry. Vi tuj devas iri super tie do ni povas fari ĉambro. Nun, se vi opinias pri tio, eble Ni ĵus faris la problemo malbona. Kaj eble ni faris, ĉar kion se Graco estis en la gxusta loko? Sed ni scias, ŝi ne, ĉar alie, estus estinta staras antaŭen anstataŭ Neil tiun fojon, ĉu ne? Ni jam kontrolis sian numeron eksteren. 

Ĉio bone. Do nun, Neil estas en la ĝusta loko, kaj Mi povas fari etan optimumigo. Por la sekvan minuton, mi tuj ignori Neil ĉiuj kune, por ne malŝpari sian tempon, aŭ hazarde interŝanĝi lin al la malĝusta loko. Do nun, kiel mi trovos la sekvanta elemento kiu estas plej malgranda? Du. Tio estas sufiĉe bona numero, se vi volas treti antaŭen kaj Mi memoras vin. Ses, neniu bona. Kvar, tri, sep, kvin, ne bona. Do lasu min movi vin via ĝusta loko. Kaj ni ĵus bonŝanca ĉi tiu tempo. 

Nu, mi tuj ignori tiujn du infanoj, kaj nun faras pli trapasi ĉi. Ses, ke bela malgranda nombro. Venu antaŭen. Ho, pardonu. Grace nombro estas pli bone, do tretas antaŭen. Kvar. Pardonu, Grace. Iru returne. Numero tri estas bona. Sep. Kvin. Kaj nun kio estas via nomo denove? 

JASON: Jason. 

DAVID J. Malan: Jason. Do Jason estas nun la plej malgranda elemento mi elektitaj. Kie estas tiu tuj iros? Do kie ses estas. Kaj via nomo estas denove? 

Gabe: Gabe. 

DAVID J. Malan: Gabe. Gabe estas en la vojo. Kio estas la plej facila afero por fari? Interŝanĝi tiujn du infanoj kaj daŭrigi. Do nun ni vidu. Kiu estas la plej malgranda? Kvar. Lasu min nur speco de cheat. Kvin tuj estos la plej malgranda. Mi trovas proksima, se vi volas treti antaŭen, kion mi devas fari kun ĉi tiuj infanoj, kun Gabe? Interŝanĝi denove. Do nun, ankoraŭ iomete el ordo. Mi trovis Gabe esti la plej malgranda, tiel Mi pop lin eksteren, movi vin infanoj super. Kaj faris. 

Do respondo estas la sama. La fina rezulto estas la sama. Kiu el tiuj du algoritmoj estas pli bona? La dua, mi aŭdis. Kial? 

Parolanto 3: Oni n paŝoj [inaudibles]. 

DAVID J. Malan: Estas n paŝojn maksimume. Interesa. Do ĉu kvankam? Do kiamaniere mi trovas la plej malgranda elemento? Kiom da ŝtupoj ĉu mi devas preni la trovos la plej malgranda ero? Mi havis rigardi la tuta vojo fine, ĉu ne? Ĉar en tiu plej malbona kazo, kion se Neil estis super ĉi tie? Do ĝuste trovi la plej malgranda ero prenas min n paŝoj, aŭ n minus 1. Sed, OK. Do ripari Neil. Memoru ke, unu minuton antaŭe. 

Sed kiel mi trovos la sekvanta plej malgranda elemento? Estas n minus 1, aŭ n minus 2 vere, de la nombro de paŝoj. Do okej. Do mi n minus 2. Ĉio bone. Do kiu sentas iom pli bone. Ĉio bone. Kiom da paŝoj la proksima fojo trovi numero tri? Do la n minus 4. Do ĝi estas malkreskanta, unu malpli treti ĉiu ripeto. Do tio ne senti pli bona, ĉu ne? Se lasta tempo estis krude n × n, ĉi tiu tempo estas n minus 1, plus n minus 2, plus n minus 3, plus n minus 4, punkto, ĝi pentras, ĝi pentras. Sed se vi memoras el via alta lernejo lernolibroj, la eta cheat folion en la fono kiu havas formuloj, se vi aldonas tiun serio de nombroj, kio estas la tuteca kvanto de paŝoj tuj estos ke mi prenu ĉi tie? 

Tiu estas unu el tiuj, kiel, n minus 1, tempoj n, dividita per 2. Do lasu min vidi se mi povas tiri ĉi supre por nur momento. Kaj denove, mi estas speco de rondigo iuj nombroj nur por teni nian vivon simpla, sed kiel mi memoras, estas io kiel se Mi faras n minus 1 aĵojn, tiam n minus 2, tiam n minus 3, estas krude iu kiel tiu super 2, kaj se mi multipliki ĉi tiu ekster, jen fakte n kvadrata. Tio ne sentante tro bona. n minus n super 2. 

Sed jen la afero. En komputiko, kiam la problemoj komencu akiri interesa estas kiam n ricevas vere granda. Kaj kiam n ricevas vere granda, kiu el ĉi tiuj valoroj tuj regi ĉiujn de la aliaj? Ĝi estas speco de la n kvadratoj, ĉu ne? Jes, dividanta per 2 estas sufiĉe bonaj. Sed se vi parolas pri miliardoj de pecoj de datumoj, aŭ bilionoj de pecoj de datumo, okej, do vi estas duoble pli rapide. Sed kiu vere zorgas se tiu granda nombro, se tiu faktoro estas kion ricevas pli kaj pli granda. Kaj certe, faras pli diferenco ol tiu ulo. Do kvankam vi infanoj pravas, la dua algoritmo, ni nomas ĝin selektado varon, estas, en la reala mondo, iom pli rapide potenciale, ĉar mi estas preni malpli kaj malpli paŝas ĉiufoje. 

Ĝi estas ne vere funde rapida. Ĉar se ni reale ludi ĉi eliris por grandaj valoroj de n, fine de la tago, por sufiĉe granda n, ĝi estas ankoraŭ tuj sentos sufiĉe malrapidaj. Nu, mi prenas unu lasta paŝo en tiu. Tion mi nomus selektado varo. Can you guys retrovu vin unu lastan fojon? Kaj en ĉi tiu lasta kazo, mi tuj proponi ion vokis inserción varo. Insertion speco esti, koncepte, iom malsama. 

Anstataŭ iri tien kaj reen kaj elektante la plej malgranda ero, mi estas nur tuj trakti kun ĉiu de ĉi tiuj infanoj kiel mi renkontas ilin, kaj enmeti ilin en ilia ĝusta loko. Do mi simple tuj komenci kun Grace, kaj mi vidas ke ŝi estas la numero kvar. Kie numero kvar apartenas? Mi ne komencis ordigi nenion, tial Grace ricevas resti rajton tie. Kaj nun mi iras al postuli, se vi povus paŝon al via dekstra, ĉi mia ordo listo, ĉi tiu estas mia unsorted ceteraj listo. Do nun mi iros al procedi proksima, kaj kio estas via nomo denove? 

Branson: Branson. 

DAVID J. Malan: Branson. Do Branson estas numero du. Do mi tuj prenos vin dum momento. Kaj nun, kie vi apartenas en ĉi tiu tabelo? Do por la rajto de Graco. Do denove, ni estas speco de fari Graco faras multan laboron tie. Kie ni metos vin? Do ni iras gliti vin al la restis, kaj enigi Branson tie. Sed nun mi asertas ke you guys estas farita. Sed avizo, mi ne uzas ekstra spaco. Ĝi estas ankoraŭ 2 eroj ĉi tie, 5 pli ol ĉi tie. Sumo tabelo grandeco estas 7, do mi estas ne trompas, ĉiuj rajtas? 

Do nun ni havas, kun Gabe tie, la numero ses, kie vi apartenas? You got bonŝanca denove. Do vi ricevas resti rajton tie. Nur prenu malpeza paŝo al la ĝusta nur por klarigi ke vi ordo. Kaj nun ni havas Neil denove, numero unu, kie vi iras? Kaj nun estas kie ni komencos vidi ke ĉi tiu algoritmo, kvankam en la unua rigardo, sentas sufiĉe inteligenta, rigardi kio estas okazonta. Se vi povus treti antaŭen. 

Kie ni volas meti Neil? Do evidente ĉi tie, do kiel do ni preni Neil tie? Ni faras tiun paŝon post iom. Gabe, kie vi devas iri? Yep, do prenu unu granda paŝo, aŭ du duon-ŝtupoj por fari unu paŝon tie. Graco, kie vi iras? Bona. Do alia paŝo. Kaj fine, Branson? Alia paŝo. Kaj nun ni povas meti Neil en loko. 

Do nun, daŭrigu tiun logikon. Eĉ se ni ne sxangxigxantaj Neil plus, plus plus metu lin kie li iras, en la plej malbona kazo, la sekva numero ni povus renkonti povis estu la numero, diras, estis numero nulo, tiam ni tuj ŝanĝi ĉiujn ĉi tiuj infanoj. Supozu ke estas kelkaj, negativa unu, tiam ni devas ŝanĝi ĉiuj de ĉi tiuj infanoj. Do ni estas vere nur speco de klakanta la problemo ĉirkaŭe, tia, ke ni estas trapasante la elspezo de la procezo de selektado por la inserción procezo, tia ke vi infanoj ĵus havis movi malglate n minus ion nombro da paŝoj. Kaj tiu numero de paŝoj nur tuj pliigi kiel mi elektu pli nombroj, se mi devas gardi shoving you guys dorso, kaj reen, kaj reen. 

Do la malĝoja afero nun estas ĉiuj de ĉi tiuj algoritmoj n kvadratoj. Ni iru antaŭen kaj dankon al tiuj knaboj, kaj bildigi tiujn iom malsame. Tre bone farita. 

[Aplaŭdo] 

Ĉio bone. Tie vi iros. Dankon por - 

Branson: [inaudibles] konservi la numeroj. 

DAVID J. Malan: Ne, vi rajtas observos la numerojn tiel. Ĉio bone. Bele farita. Ĉio bone. Do ni vidu se ni ne povas nun resumi pli rapide, kaj pli vide, ĝuste kio ĵus okazis tie kiel sekvas. Mi tuj iros antaŭen kaj elsxiros Firefox. Ni ligi tiu pruvo en la kurso de afiŝinto. Java estas iom ĝena to get laborante en iuj retumiloj tiuj tagoj. Do se vi ludos kun ĉi hejme, realigi vi eble bezonas uzi Firefox akiri ĝin funkcii. Kaj kion mi faros kun ĉi pruvo estas la jena. 

Funde, mi havas tutan faskon da menuo ebloj, inkludante komenco kaj halti butonon. Ankaŭ, kiel flanken, ne ŝajnas esti cimo en tiuj programoj, per kiu vi ne povas vere vidi la komenco aŭ ĉesi butono krom se vi tenas Ordonu aŭ Alt pli kaj zomi, kiu scivoleme montras al vi pli da butonoj. Do ĝuste FYI se vi ludas kun tiu en la hejmo. Nun mi iros al klaku Komenco en nur momento, post preciziganta malfruo de, kiel, 200 milisekundoj tien, simple tiel ni povas vidi kio okazas. 

Do mi asertas ke ĉi tiu estas videbligo de la unua algoritmo ĉi tiuj infanoj faris, bobelo varon, per kiu Ni interŝanĝis homoj paro-saĝa. La ŝlosilo enrigardo al ĉi videbligo estas ke la alteco de la stangoj reprezentas la grandeco de la nombro. Do la altkreska la trinkejo, la pli granda la nombro. Shorter la trinkejo, pli malgranda la nombro. Kaj se vi rimarkas, ni iras tra la unua ripeto de ĉi tiu algoritmo, swapping grandaj kaj malgrandaj nombroj, por ke la malgranda nombro venas unue kaj la granda nombro iras dekstre. 

Kaj tuj kiam ni atingas la finon de tabelo de multaj pli nombroj ol sep, ni estas tuj reiros al la komenco. Kaj anticipi tion. Sur la malantaŭa maldekstra, ke iom ulo tuj por interŝanĝi al la flanko, kaj ĉi procezo ripetas. Nun ĉi videbligo rapide akiras enuiga, tiel lasu min antaŭeniri kaj halti ĝin, ŝanĝi la malfruo io multe rapida nur por akiri nun, emo al tiu algoritmo. 

Do eĉ se mi rapidis ĝin, tio estas kiel ĝisdatigo mia procesoro, aĉetante nova komputilo. Mi ne funde ŝanĝiĝis mia algoritmo, sed vi povas ja vidi pli klare, ol kun homoj, ke la granda nombroj estas bobelis ĝis la supro, kaj la malgrandaj nombroj estas bobelis malsupren al la fundo. Kaj nun tiu afero ĉi tie ordo. Kaj kiel flanken, sur la placoj, estas nur iuj librotenado tie helpi vin kalkulu kiom da komparoj, aŭ kiom da svopoj havas fakte estis farita. 

Nu, ni provu unu el la aliaj ni vidis. Lasu min alklaku bobelo speco ĉi tie, kaj lasu min elekti, kaj ĉi tiu tuta retpaĝo estas iom kalesxo. Ni akceptas la riskon kaj ruli ĝin denove. Tie ni iru. Do ni faru selektado varo. Mi ne scias kial la menuo aperas tie. Ni zomi ripari ke cimon, ŝanĝi ĉi tion al 50. Ha, ni vere faras ke multe pli rapida. Kvin milisekundoj aŭ tiel, kaj Starto. 

Do tiu estas elekto varo. Do denove, pensi kion ni faris kun la homoj tie supre. Ni trapasis la tabelo kaj selektita la plej malgranda ero denove, kaj denove, kaj denove. Nun mi asertas, ke estis ankoraŭ sufiĉe malbone. Estis ankoraŭ n kvadrataj, donos nek prenos, sed ĝi estis, en la reala mondo, iom pli rapida, ĉar mi ja prenante iomete malpli paŝojn ĉiufoje. Sed ni nur parolas kio? Eble 40 aŭ tiel trinkejoj tie? Ni ne parolas 40 milionoj. Do ĝi ne estas tute klara al mi ke estis ja signifa gajno. 

Permesu al mi iri tien kaj ŝanĝi nian tria algoritmo, kiu estis elekti inserción varo. Kaj nun estas vere kalesxon ĉar la menuo vere ne devus esti tie. Do nun ni rulumi reen tien kaj komenci tiun algoritmon. Whoop, komenci kaj ĉesi. Do ĉi tiu speco de havas belan desegnon al ĝi, per kiu ni estas denove enmeto de la homoj, aŭ en tiu kazo, la riglilojn en ilia taŭga loko. Kaj ĝi estas jam faris antaŭe Mi turniĝis. Sed ĉi tiu ankaŭ, en teorio, ankoraŭ n kvadratoj. 

Do ni vidu se ni ne povas resumi tiujn kiel sekvas. Mi tuj iros antaŭen kaj justa por doni ni speco de komuna maniero paroli pri tiuj aferoj, lasu min enkonduki nur iom de skribmaniero tie. Vi estas por vidi iun nomita granda Ho, ĉar ĝi estas laŭvorte granda O. Kaj tio estas maniero, ke komputilo sciencisto aŭ matematikisto eĉ uzas por priskribi la rula tempo de iu algoritmo. Kiom da paŝoj reale preni? 

Nun mi iros al hontigi min per mia skribo tie en nur momento. Sed lasu min antaŭeniri kaj diri ke tio estos granda a super tie. Kaj lasu min enkonduki unu alia simbolo, majuskla omega. Omega tuj estos la malon, esence, de granda O. Dum granda O rimedoj, en la plej malbona kazo, kiom da tempo eble iu algoritmo prenas, en terminoj de n, omega tuj estu kiom da tempo povus ĝin preni en la plej bona kazo. Kaj ni vidos kion ni celas diri per bona kazo en nur momento. 

Do ni komencu ion simpla. Permesu min komenci per lineara serĉo. Do ne imitu. Ni nomas tiun lineara serĉo. Kaj nun, fari iom tablo el ĉi. Kaj nun, en la kazo de linearaj serĉo, en la plej malbona kazo, kiom da paŝoj estas ĝi tuj portos min trovi numeron de arbitra elekto? Kaj tie estas n tuta pordoj aŭ n tuta nombroj. Plej malbona kazo. Kiom da paŝoj mi tuj devos preni por trovi la numero 50 en tabelo de n pordoj? Kaj kial? Ĉar ĝi povus esti la tuta vojo super sur la fino. Tiel kiel Jennifer renkontis, la numero 50 estis la tuta vojo finiĝis, tiel en la plej malbona kazo lineara serĉo estas granda O de n, ni diras. 

Kio pri la plej bona kazo, se vi ricevas vere bonŝanca? Ĝi simple tuj prenos unu paŝon, aŭ konstanta nombro da paŝoj. Do ni devos priskribi ke kiel 1. Do ĉi tiu estas sufiĉe bonaj. Nun kio se ni faris ion kiel duuma serĉo? Do duuma serĉo, en la plej malbona kazo, prenis kiom da tempo? 

[Intermetante voĉoj] 

DAVID J. Malan: Do fakte, mi aŭdis ĝin en paro lokoj. Do ĝi estas reale log n, doni aŭ forpreni de ĉar kiel ni dividos la listo en duono denove, kaj denove, kaj denove, ni povis trovi, finfine, la valoro, se ĝi estas tie, sed ekzistas kaptaĵo. Kio estas la supozo, ke ni devas preni por donita por duuma serĉo? Ĝi devas esti ordo. Tio ne ordo, vi povas fendi la afero en duono denove kaj denove, kaj vi povas iri forlasis, kaj vi povas iri dekstren, kaj vi povas iri maldekstren kaj dekstren, sed vi estas ne tuj trovos la elemento se la listo estas ne ordigita, ĉar vi povus perdi ĝin. Ĉar via heŭristiko, por iri maldekstren aŭ dekstra tuj estos misa se estas ja ne ordo. Do tie estas ia kaŝita kosto uzi iun kiel ĉi tio. 

Nun, ni eniru nian ordigado algoritmoj ne serĉado - oh, fakte ni iru en ĉi tiu celo. Duuma serĉo en la plej bona kazo? Ĝi estas ankaŭ 1 se ĝi nur hazarde estas en la mezo de la tabelo, aŭ Meze de la telefono libro. Nun ni faru bobelo varo. Do denove, nun ni eniri la varojn, ne la serĉojn. 

En la plej malbona kazo, kiom da paŝoj faris nin aserto bobelo speco tuj preni? n akordis. Do mi tuj, por cxerpi tio. Ooh, mia skribo aspektas eĉ pli malbona kiam ĝi projektis ke granda. Ĉio bone. Por ke estas n kvadratoj. Kaj en la plej bona kazo de bobelo varon, kiom da paŝoj estas ĝi tuj preni? 1, Mi aŭdis. 

Parolanto 1: n. 

DAVID J. Malan: n, mi aŭdis. 

Parolanto 1: 2. 

DAVID J. Malan: 2, mi aŭdis. Ĉu mi aŭdas 3? Ĉio bone. Do mi aŭdis 1, n, 2, sed ni pick aparte almenaŭ la unua de tiuj sugestojn, 1. Ĝi ne estas malbona instinkto, ĉar ĝi ia sekvas mastro ĉi tie. Sed se ĝi nur prenas 1 paŝo, kiel en la mondo mi povus aserti, ke la listo estas ordo, ĉar se mi nur permesis preni 1 paŝo, kiom da elementoj mi povus efektive kontroli por certiĝi? Nu, nur 1, kiu signifas ke estas n minus 1 elementoj kiuj povus esti el ordo, kaj mi simple okazas fido post rigardas 1 elemento kiu la afero ordo. Do 1 Ne korekti ĉi tie. Do minimume, kiom da Mi devas rigardi? 

[Intermetante voĉoj] 

DAVID J. Malan: n minus 1, aŭ vere, n, ĉar mi bezonas rigardi ĉiun elemento por certigi ke ĝi ne estas el ordo. Sed denove, ni ordigi de ondo nia manoj al la pli malgrandaj nombroj kaj supozi ke, kiel n prenas grandaj, ili estas neinteresa ĉiuokaze. Do jen bobelo varo. Kaj nun, ni faras cxi du lastaj. Selektado varo, kaj tiam ni instruos vin fari inserción varo. Kaj tiam ni blovu via mensoj per io multe pli bona ol ĉiuj tiuj. Ĉio bone. 

Kio estas la plej malbona kazo kurante tempo de selektado speco? 

Parolanto 4: n kvadratoj. 

DAVID J. Malan: n kvadrata, mi aŭdi. Sed kial n akordis, intuicie? 

Parolanto 4: Ĉar ni ĵus faris. 

DAVID J. Malan: Ĉar ni ĵus faris. Akcepti. Bona respondo. Sed intuicie, kial estas elekto speco n kvadratoj? Kion ni devas fari denove kaj denove? Ni devis konservi balaita tra, estas vi la plej malgranda, vi estas la plej malgranda, vi estas la plej malgranda. Kaj koncedis, ni povis preni n paŝoj, tiam n minus 1, tiam n minus 2. Sed se vi speco de aldonu tiuj tuton, aŭ preni ĝin sur fido kiun mi aldonis ilin anticipe, ni preni malglate n kvadrato minus iuj pli malgrandaj nombroj. Do mi tuj nomas tiun n kvadratoj. Sed kun selektado varo en la plej bona kazo, kiom da paŝoj estas tuj kapti min? 

Parolanto 5: [inaudibles] 

DAVID J. Malan: Estas bedaŭrinde ankoraŭ n kvadratoj, ĉu ne? Ĉar se mi elektante la plej malgranda elemento, kaj ni havis sep personoj ĉi tie, Mi nur scias, iam mi alvenas al la tre fino, ke mi trovis la plej malgranda nombro, kien ajn li aŭ ŝi eble estis. Sed kiel mi trovos la sekvanta plej malgranda nombro? Mi devas fari alian pasas. Do, en la plej bona kazo, kio estas la eniro al selektado speco? Ĝi estas jam speco listo, numero unu, numero du, numero tri, la numero kvar. Sed mi estas komputilo. Mi povas nur rigardi unu afero je tempo. Mi ne povas ordigi de paŝon reen kiel homo, kaj diru: ooh, ĉi aspektas korekta. 

Mi povas nur ajudiki korekteco en selektado varo por selekti la plej malgranda nombro. Sed eĉ se mi trovos numeron oni unue, se mi ne konas ion alian pri la aliaj nombroj, kiujn mi faras ne, ĉio mi scias, ke mi estis transdonita tabelo aŭ aro de pordoj malantaŭ kiuj estas nombroj, la sola maniero mi scias, ke unu estis la plej malgranda? Se mi ricevas la tutan vojon tie kaj realigi, malbenita, oni ja estis la plej malgranda. 

Sed kiel mi povas tiam difini, ke du estas la sekva pli malgranda? Por fari la saman senefikeco denove kaj denove. Do fine, kun inserción varon, kiel, en la plej malbona kazo, ni diru ĝin plenumas? Ĝi tro estas n kvadratoj. Kaj kiel pri la plej bona kazo? Ni lasos ke kiel cliffhanger. Ni plenigu en tiu celo venontfoje, sed unue permesu al mi proponas ke ni fundamente fari pli bone ol ĉiuj de ĉi tiuj, ĉiuj rajtas? 

Do pensu mem kion inserción speco tuj estos. Nu, tio ne estis tre drama, ĉar mi estas la sola kiu vidis la ŝanĝon. Wow. Akcepti. Do jen ni havas iom malsama pruvo. Se mi zomi tien, vi vidos, ke sur la maldekstra havas bobelo varon, en la mezo ni havas elekton varo, kaj sur la ekstremdekstro, ni havas ion ni ne rigardis ankoraŭ vokis kunfandi varo. Sed rigardu, kion ni estis faras ĉi tie tiel multe hodiaŭ. Kiam Jennifer unua supreniris sur la scenejo, Ni trapasis la tabelo de nombroj denove, kaj denove, kun lineara serĉo, kaj ni akiris lineara rultempo, granda O de n, por tiel diri. 

Kiam ni nun konsideras la unua semajno de klaso, kiam ni dividu kaj venkos, kaj ni estis la telefonon libro ŝiri, kaj Jennifer, kaj ni kolektive leveraged tiu ŝlosilo komprenon, kiu estis ripeti mem denove kaj denove por iel ĵeti for, ĵetante for, ĵeti for, duono de la problemo, aŭ ĝenerale, dividanta problemo en duono, kaj poste trakti la plej malgranda peco de la problemo kiel koncepte ekvivalenta al la aliaj, ni iel faris fundamente bona. Sed kun bobelo varo, kun elekto varo, kun inserción varon, ni povas ne tia komprenojn kiu Jennifer faris. Ni preskaux nur marsxis tien kaj devenos tutan faskon da fojoj, kaj ni tweaked aferojn iomete, interŝanĝante en ĉi tiu ordo, eble enmeto aŭ selektante. Sed je la fino de la tago, mi faris multajn de talpoj marŝi tien kaj reen. Ni faris ne vere influo ion inteligenta kiel Jennifer faris kiel dividanta kaj konkerante. 

Do kunfandi varon, per kontrasto, kiun ni ne vidos ĝis la proksima semajno, ĝi okazas de utiligi tiu ŝlosilo ideo per dividanta la enigo, kaj poste _halving_, kaj poste _halving_, kaj poste _halving_. Kaj en ĉiu ripeto de tiu ciklo, ordigi la maldekstra duono, kaj la dekstran duono, poste la maldekstran duonon de la maldekstra duono, kaj la dekstra duono de la maldekstra, tiam la maldekstra duono de la dekstra duono, kaj la dekstra duono de la dekstra duono. Kaj ripetante denove kaj denove. 

Tiel vi vidos ĉi vide, sed ĉi tiu estas kio atendas nin la proksima semajno. Kaj ĝenerale, kiam ni pensas iom iom pli en tia problemo. Ni n kvadrato maldekstre, n kvadrato en la mezo, kaj n log n dekstre. Do tie estas via reala cliffhanger. Ni vidos vin lunde. 

[Aplaŭdo]