[Powered by Google Translate] [Semajno 3, daŭrigis] 

[Davido J. Malan - Universitato Harvard] 

[Jen CS50. - CS50.TV] 

Bone. Bonvenon dorso. Ĉi tiu estas CS50 kaj ĉi tiu estas la fino de semajno 3. 

Do por tiuj nekonataj, lasta jaro Harvard ĵetis kion nomas la Novigo Lab, aŭ i-laboratorio, kiu estas mirinda konstruaĵo trans la riveron sur HBS la kampuso kiu estas malfermita al la universitato studentoj, GSAS lernantoj, studentoj el tuta kampuso, inkludante fakultato, kaj ĝi estas loko por kunveni por labori en pioniraj aĵoj, aparte emprendedor aĵoj se vi kaj 0 aŭ pli amikoj pensas fari ion emprendedor ĉu dum ĉi tiu klaso, post ĉi tiu klaso, aŭ tie. 

Do unu el la aferoj oni faras sur J termino estas tiuj vojaĝoj, unu el kiuj estas al Nov-Jorko, unu el kiuj estas Silicia Valo. Spaco estas tre limigita, sed estas ŝanco froti ŝultroj kun MBAs kaj postdiploma studentoj trans campus kaj reale pasigas tempon en tiuj respektivaj areoj babili ĝis startups, babilante ĉe entreprenistoj kaj similaj. Do, se interesas, kontrolu ĉi URL tie. Ankaŭ estas disponebla en la diapozitivoj ensalutintaj. 

Ĉu ni tono malsupren la domo audio malmulta? Se vi ŝatus aliĝi por tagmanĝi ĉi vendredo, 1:15 pm en Fajro & Glacio, bonvolu direkti tie. Apologies se la formo estas jam plenigis per la tempo vi alvenos. Sed ni daŭrigu tiun tradicion antaŭen. 

Hodiaŭ ni daŭrigos la altan nivelon diskuto de diversaj problemoj kiuj povas solvi, enfokusigante multe malpli, hodiaŭ almenaŭ, en kodo kaj multe pli en ideoj. Do pensas reen al semajno 0 kiam ni disŝiris telefono libro en duono, la objektivo de kiuj estis fari ion, Certe, iom drama sed sendi la punkto kiu traserĉado ne devas esti, nepre, kiel evidenta al unua vido, kiel vi povus pensi. Kaj problemon solvi ĝenerale eble ne nepre ĉiam estas la plej bona - La plej evidenta solvo por ne nepre estas la plej bona. Do ni havis ĉi telefonon libron kaj, sincere, ni ĉiuj en tiu ĉambro havis la instinktoj, plej verŝajne, por komenci en la mezo kiam serĉis Mike Smith kaj tiam iru maldekstren aŭ dekstren surbaze de kion ajn litero de la alfabeto ni okazis por fini plu. 

Sed tio simpla ideo, ke ni homoj memkompreneble tiel longe vere devus komenci veni al la avangardo de via menso ĉar kiel la problemoj akiri multe pli kompleksa ol telefono libro, tiuj samaj simpla, brila komprenoj estas kio tuj permesos nin solvi multe pli komplika kaj pli interesaj problemoj, inter ili iuj el la aĵoj oni prenas por donita jam tiuj tagoj. Miliardoj da retpaĝoj tie, kaj tamen Google kaj Bing kaj similaj kapablas trovi tion por ni tiel. Tio ne okazas per la uzo de lineara serĉo, serĉante tra ĉiuj eblaj retpaĝoj. Facebook povas diri al vi kiu ĉiuj viaj amikoj estas aux amikoj de amikoj, kaj tio ankaŭ povas esti farita ŝajne post momenteto tiujn tagojn kvankam ili havas milionojn da uzantoj. 

Kaj do kiel ni efektive solvi problemojn en tiu skalo finfine redukti al la ideoj, ni rigardis en semajno 0 kaj iom pli hodiaŭ. Ni ne denove ekzekuti ĉi algoritmon, sed memori ni ankaŭ faris en semajno 0 ĉi ekzerco kie ni estis ĉiuj ekstari, alpreni la numeron 1, kaj poste ni havis cxiu mem-grafo de emparejamiento for, aldonante viajn nombroj kune, tiam duono el la bando sidiĝis sur ĉiun ripeto. Do ni iris de 500 lernantoj al 250 al 125 ks. Sed kiel ni diris lundon, la potenca ideo tie estis, ke se ni dublis la grandeco de tiu problemo kaj ĉiuj infanoj de Justeco aŭ Ec 10 revenis en la ĉambron kaj aliĝis al ni, bone, ni povus probable kalkulu ke tutaj aldonita grupo kun nur 1 pli granda ripeto de la ciklo, ĉar ili nur eble duoble la grandeco aŭ en Ec 10 kazo de iom pli ol duobla la grandeco. Kaj tiel ni devus elspezi iom pli da tempo, sed ni ne devus elspezi 400 aŭ 700 pli paŝoj. 

Nur por pentri tiun bildon en maniero kiu estas iom malpli abstrakta, ni ne ĉiuj ekstari. Sed se tiuj el vi, kiuj elektis por sidi en la orkestro hodiaŭ ne gravas piedo, ni vidu, se ni povas kalkuli inter vi, kiuj la plej alta homo estas farante la saman specon de kompara algoritmo. Do se vi sidas en la orkestro, mia pardonpeti, sed paŝo 1, ekstari; paŝo 2, paro for kun iu apuda vi, elŝeligi kiu estas pli alta, kaj sidigxu, se vi estas pli mallonga. Tiam ripeti. [Studentoj murmurado] 

Okay. Okay. Unu estas lasi ĝin stari. Kio estas via nomo? >> Andreo. 

Andreo, vi estas la plej alta persono en la orkestro sekcio hodiaŭ. 

Gratulojn. [Aplaŭdoj kaj huraoj] Okay. Havi sidejon. Do ni trovis Andreon. Sed kiel longe estus ĝin portinta min, ekzemple, por trovi Andrew en ĉi tiu orkestro sekcio de 50 + aŭ tiom popolo? Mi povus esti prenita sufiĉe simpla alproksimiĝon kaj komenci tie. Kaj mi 2 personoj ekstari kaj mi simple kompari ilin, kaj tiam mi diros al kiu ajn estas iomete pli mallonga, "Okay, vi sidiĝu," kaj mi tuj memoras kiu la alta persono estis. Tiam mi ripetas, ripeti, ripeti, kaj mi pendas sur la plej alta persono ĝis mi trovos iun iomete pli alta ol ili, je kiu punkto la iomete pli mallongaj persono devas tiam sidiĝi. Sed en tiu algoritmo en ĉi tiu orkestro sekcio, se estas n pri vi, kiom da paŝoj estas tiu algoritmo tuj prenos? >> [Studento] N. 

Ĝi tuj preni n, vero, ĉar en la plej malbona kazo, por tiel diri, la plej alta homo estas la lasta persono kiu alvenis al nur hazarda malbonan sorton. Do, en la plej malbona kazo, la rula tempo de tiu algoritmo estas lineara, estas n, kie n estas la nombro de personoj en la spaco, la grandeco de la problemo. Kio pri ĉi tiu algoritmo? La fakto ke vi cxiuj ekstaris kaj tiam denove duono el vi sidiĝis, duono el vi sidiĝis, duono el vi sidigxis. Kiom da ŝtupoj oni kiuj prenis se estas n de vi ĉi tie? [Studento] N log n. >> Tio estus malbona. Ensalutu n. 

Do ensaluti n, eĉ se vi ne sufiĉe memoras kia logaritmo estas, nuntempe, ĝuste estimi kiu rilatigas iel al ĉi _halving_ kaj _halving_ kaj _halving_. Ĝi ne devas esti faktoro de 2. Ĝi povus esti faktoro de 3. Sed temas pri tiu ĉi ripetado de la sama speco de faktoro tia ke la grandeco de la problemo komenciĝas tie sed tiam tuj iras tie, tiam tie, tiam tie, tiam tie. Vi ne prenante malgrandan mordas el la problemon, vi vere batante sin al ĝi kun granda falis plonĝo ĉiufoje. Do ni havis 50 personoj, tiam 25, do 12 ½ aŭ 13 homoj starantaj, tiam 6 ½ kaj tiel plu ĝis fine nur Andreon restis staranta. Do ni iras por voki ke log n, kaj vi povas bildigi tion kiel sekvas. Memori tiun bildon tie kie lineara algoritmo estas kiel la ruĝa linio tie, la flava linio estis la kalkula per 2s algoritmo kiu ni uzis por rakonti studentoj en la pasinteco, sed hodiaŭ la Holy Grail tuj resti ĉi verda linio kie se ni duobliĝis la nombro de homoj en la orkestro sekcio aŭ nur diris, infero, ni havas ĉiuj en la tuta ĉambro ekstari, ne tiom granda interkonsento ĉar ni malafable duobligi kiom da homoj estas cxi tie, 1 pli ripeta, ne estas problemo. 

Ni trovis Andrew aŭ kiu ajn okazas al esti pli alta ol Andrew en la interetaĝo aŭ en la balkono. Do ĉi tiu simpla ideo, ke ni prenis tiom da por donita en telefono libro, rimarkas ke ekzistas tiom multaj malsamaj lokoj, en kiu ni povas apliki ĝin. Nur por abofetear iuj Slango - fakte, pli ol ĵargono unua, lasu min iri al tiu bildo ĉi tie. Ĝuste nun ni parolis pri n kaj n / 2 kaj poste ensaluti de n, sed ni povas certe supreniru kun, kiel ni faros en la kurso de la semestro, aliaj speco de matematika formulo por priskribi ĉi tiun ĝeneralan nocion de rula tempo. Tio estas ekster la kunteksto por nun cxar ni vidos post nelonge algoritmoj kiuj tiuj reale reprezentas. 

Sed rimarki tie la lineara lineo n, la rekto, estas fakte tre malalta montrante nun. Tio estas speco de optika iluzio en tiu ni nur ŝanĝi kion la x akso reprezentas kaj la y akso, kaj ni povas fari rekto punkto en ajna direkto ni volas. Sed la kaŭzo, ke ĝi estas tiel ŝajne ebena nun estas ĉar ni bezonas por fari lokon sur ĉi grafikaĵo por multe pli malrapida kurante foje. Cxar nun, sciu ke ekzistas iuj sufiĉe malbone algoritmoj en la vivo, iuj de kiuj ne prenas n paŝoj aŭ, pli bone ankoraŭ, log n paŝoj sed pli. Do supre la linio n tie malsupre avizo ekzistas n fojoj log de n, kaj ni vidos kion ĉi tio signifas antaŭ longe. Super tiu estas n kvadratoj, kaj ni ne vidis neniun n kvadrataj algoritmoj ankoraŭ sed ni baldaŭ. Kaj tio aspektas vere malbona. Estas 2 al la n, iu eksponenta funkcio, kiu sentas eĉ pli malbone. Kaj tamen, kurioze, tiam ekzistas n potenco de, kiu se vi estas ia pensante antaŭen, se vi ia fari la math, 2 al la n fakte revenas multe pli rekta, multe pli alte ol n potenco de se vi rigardas la hakiloj suficxe eksteren. Do rimarki nun tiuj aksoj estas arbitre 2 al 10 en la x akso. 

Kaj kion tio signifas? Tio signifas 2 personoj al 10 personoj en la salono. Tio estas ĉiuj x signifas: grandeco de problemo, sendepende de la kunteksto estas. Kaj vertikala akso nun estas la numero de duaj aŭ nombro de paŝoj - iuj unuo de tempo. Sed rimarki ke ĝi estas 0 al 60 kaj 0 al 10. Sed se ni ia zoom out, kiel vi povus en Excel aŭ iu cartografía programaro, kaj ni supreniras al 200.000, rimarki ke iu kiel 2 ĝis la n tuj tute Colmar la kuranta tempoj de n kvadratoj, n potenco de, n logo n - ĉio ni parolis pri tiel for. Kaj tamen la kaptita estas kiam oni komencas paroli pri aĵoj kiel Facebook kie vi multaj, multaj, multaj personoj ĉiuj interkonektitaj, Vi n personoj, ĉiu el kiuj povas havi tiom da kiel n amikoj se ĉiuj estas speco de buddy-buddy en la mondo, bone, tio estas n × n jam, do ke tio n kvadrataj eblaj amikecoj, almenaŭ en 1 direkto, n kvadratoj eblaj amikecojn. Por ke jam sugestas, ke serĉado de Facebook socia grafeo, por tiel diri, povas komenci esti esprimita en tiuj specoj de formuloj. 

Ni revenos kaj fari ĉi multe pli konkreta, sed nuntempe, la objektiva por la sekvanta multaj semajnoj tuj estos certa ne iri sur apliki algoritmoj aŭ kodo kiuj finas prenante tiel tempo kiel io tiamaniere. Sed la fascina afero pri komputiko se vi daŭrigas en ĉi tiu kampo prenante klasoj kiel CS121, CS124, ambaŭ el kiuj estas teorio kursoj, estas kiu estas vere iuj problemoj kiuj ekzistas en la mondo ke fundamente, gxis ni scias, ne povas esti solvita ajna pli rapida ol la plej malbona el tiuj grafikaĵoj fakte sugestas. Do tie estas multe da malfermitaj problemoj en tiu ĉi mondo fari multe pli bone ol homoj havas tiel multe. 

Do ni komencu do per tiu ekzemplo. Ni vidis Estu lukto kun ĉi en kamero, ĉiuj tro mallerte en video. Sed la realo estis, kiam Estu komisiis kun trovi sur tabulo kiel tiu de la numero 7, memori, ke mi diris tion, "Ne estas ie malantaŭ tiuj pecoj de papero aŭ blankaj pordoj "La numero 7. Sean, trovu ĝin por ni." Kaj estis mirinde mallerta rigardi ĉar li vere luktas kun tiu problemo. Sed la realo estis Sean faris tiel kiel neniu en la ĉambro povus havi farita. Li prenis iom pli longa ol tipa persono povus havi, sed li supozis, ke estis iu lertaĵo por ĉi tiu problemo, Li supozis, ke li mankis io. Kaj tio ne helpis, ke centoj da okuloj portantaj sur li. 

Sed la realo estis, se la enigo al la problemo estas fasko de hazardaj nombroj kaj vi petante por trovi 1 tia nombro, la plej bona vi povas fari estas lineara serĉo. Starti je la maldekstra, movi al la dekstra, aŭ komenci ĉe la dekstra, movi al la maldekstra. Retroaktive, ni povus pensi, "Estu, kial vi ne komencu la alia fino?" Nu, 7 povus esti same facile estis tie hazarde, sed mi intence metis ĝin tie ĉar mi kalkulis ke li ne tuj komencos je la fino. Do mi specon de manipulita la situacio, sed per hazarda ŝanco 7 povus esti ie ajn. Do ekde la dekstra fino povus esti pli bone tiam, sed kio se la venonta jaro mi movi 7 aliloke? Tio ne estas fundamente nova solvo al la problemo - ekde 1 fino aŭ la alia - kiam vi donis al neniu alia supozo. Do Estu komencis rigardi tra la numeroj kaj li diris: "5. Tio ne tie." Poste li iris tie kaj vidis 19, tiam li pauxzis por proksimume 20 sekundoj, poste li malfermis ĝin por 13, kaj poste ĝi fariĝis evidenta ke ne ŝajnas esti mastro ĉi tie. Ne estis 1, 2, 3, 4 aŭ similaj. Esas breĉoj en la nombroj, kiu ne helpis. Kaj ankaŭ, la fakto ke mi uzis tiujn malmultekostaj pecoj de papero por kovri la numeroj Estas vere intenca, ĉar se mi forigis cxiujn tiujn pecojn de papero, la plimulto de ni, Estu inkludis, probable estus ekrigardis ia macroscopically ĉe la skribtabulo, kaj diris: "Ho, 7 estas evidente prava." Ni faris tion tuj. 

Kaj tio estu la maniero la homa cerbo laboras por iu punkto, sed fakte, liaj okuloj aŭ menso estis probable skimming la numeroj de dekstra al maldekstra, maldekstre al dekstre, meze sur eksteren - io okazis fisiológicamente tia, ke ĝi sentis ĝin okazis tuj, sed malakordo eĉ interne estis iu speco de metodiko por trovi 7. Kaj efektive, nun ke ni parolas pri tabeloj kaj datumstrukturoj kaj memoro ene de komputilo, la sola afero, kiun ni homoj povas fari estas rigardi al individua memoro lokoj 1 samtempe. 

Do ĉiu alia loko povus tiel esti kovrita kun iu peco de papero ĉar ni ne povas vidi ĝin iel. Ni nur povas fari 1 afero je tempo. Do ĉi-kaze, en Estu la kazo, ni iris tie kaj tiam ni iris tien kaj poste ni iris tien, jen, jen, jen, ili alvenis ruza fine kaj nur speco de saltis ĉi tiu arbitre kaj trovis 7 tie. Ĉi tiu ne estis aparte speciala. Ĝi tro iris el ordo. Sed li fine trovis 7. Sed nun la takeaway vere estas la plej bona vi povas fari kiam donita neniu informo alia ol hazardo ordo nombroj estas por komenci el la maldekstra aŭ komenci de dekstre. Aŭ heck, vi povas hazarde malfermi pordojn, sed eĉ tiam kion tio signifas esti hazarda? Nu, ni devus iel formaligi kion signifas komenci ĉi tie, tiam iru tien, tiam iru tien. Estu faris grandajn, kaj estis nur amuze spekti. Kio se anstataŭe ni ŝanĝas la problemon iom, kaj elvoku ĉijara Sean, se vi volas? Ĉu iu ajn esti komforta venas sur scenejo kaj solvanta iomete malsama problemo kaj aperante en kamero? 

Ni iru trans la orkestro ĉar vi infanoj estis sufiĉe implikita hodiaŭ jam. Kion pri en rozkolora, en la ĉapelo? Venu malsupren. Kio estas via nomo? >> Alex. >> Alex. Okay. Do Alex estos ĉijara Estu kaj aperos en la sekvaj jaroj valoro de CS50 prelegoj. Alex, nice to meet you. >> Nice to meet you too. La defio de la mano por vi estas, ke vi havas ĝin iom pli facile en tiu mi diras al vi la samaj numeroj estas tie, sed ili nun ordo. Do nun, via celo estas trovi la numero 7. Kaj efektive, ni devus vere fari ĉi - you're speco de kaptiloj, kiel komputilo estus ne, rigardante, kion la numeroj estis antaŭ momento. Per kreto ĉi fakte ne tuj helpi al ĉiuj, ke multe, sed ni ŝajnigi ke vi ne scias, kion la originala tabelo estas. Vi nun scias, ke vi havas aron da ordo nombroj kiuj povus havi distancon inter ili, kaj via celo estas trovi la numero 7. Kiel vi, racian homo, iru pri trovi la numeron 7? 

Iru el malaltaj al altaj? >> Bone. Iru malaltaj al altaj. Kaj ne disŝiros ilin. Ni nur levi ilin do ni povas reuzi ilin. Okay, do 1. Atendu. Antaŭ vi observos iras, kiu estis 1, klare erara. Do kio okazas tra via menso poste? Kio estas via sekva movo? La proksima. >> Bone. La proksima. Bona. 3, tiel malĝusta. Kio estas via sekva movo? Pluiru. >> Bone. Pluiru. 5. Do daŭre iras, kaj lasu min transdoni al vi por la estonteco. 7. >> Bonega. Tre bona. Trovis la numero 7. [Aplaŭdo] Do, kio estis bona, sed Sean tro trovis la numero 7. Kaj mi argumentas ke vi ne vere ekspluatis tiun plian pecon de informo, kiu estas kiu ĉi tiuj nombroj estas ordo. Do ni povas fari pli bone? Ajna sugestojn ĉi tie? Yeah, en dorso. [Studento] Duuma serĉo. >> Mi tute ne scias kion duuma serĉo estas. 

[Studento] Komenci en la mezo. >> Start en la mezo. Okay. Do ni vidu se ni povas tien veni. Do, se anstataŭ vi diris komenco de la meza, iru antaŭen kaj malfermu la mezo pordo. Estas 8 el ili, do vi tuj devas arbitre elekti la iomete al la maldekstra aŭ la dekstra. Okay. 7! [Aplaŭdo] Tre bela. Konsentite, sed kie estis ni iras kun tio? Ni supozu nur rompi la egaleco vi komencis tie ĉar tio egale povus esti okazinta tiel. Ni nur okazis scii ke 7 estis tie. Do ĉi tiu estas 13. Do, se ili estas ordo kaj ni ĵus komencis en la mezo, kio estus la optimuma proksima movado estis? Iru maldekstren. Kaj tiel tie venas la telefono libro ekzemple denove. Se 13 estas tie kaj ni konas la listo estas ordigita, tiam ĉiuj el ĉi tiuj pecoj de papero estas seninteresa al ni nun ĉar ni jam scias ke 7 devas esti al la maldekstra se ĉi tiuj nombroj estas ordo kaj ni trovis 13. 

Do kio estas via proksima movado tie? >> Iru al la maldekstra. >> Konsentite, bona. Do iru al la maldekstra, kaj - atendu, hey, hey, hey. Tio cheating. Do vi trovis 7, sed kio estis la algoritmo ni ĵus aplikita? Start en la mezo. >> Bona. Do kio estas la logika etendo de tiu sama ideo? Ho, por nur tiuj. >> Ekzakte. >> Do mi komencas ĉi tie. >> Bona. Do nun ni iris iomete al la maldekstra denove. Estas 3. Sed la interesaj takeaway nun estas kion oni faru al vi ne devas maltrankviligi? Tiuj 2. >> Tiuj 2. Do nun ĉi tiu povas iri, ĉi tiu povas iri. Nun la problemo kiu estis 8 tiam estis grandeco 4 nun estas grandeco 2. Ni nun estas belaj proksima. Denove, iru al la mezo de tiuj 2 eroj. 

Okay. Do ĝi estas speco de malfeliĉa ke nun ni ĉiam tuj forlasis ĉar ni rondigas sube. Sed tio estas bone ĉar nun ni ĵetu for kaj ĉion alian, lasante nin per nur 7. Ni donu ĉirkaŭvojon de aplaŭdoj. Ni trovis 7 denove. [Aplaŭdo] Okay. Certe. Hang on por ĝuste ankoraŭ 1 sekundo. Kvankam ke apud procezo ia prenis iom pli longa ol ni sentis ĝin volis, sincere, via unua instinktoj estis la plej bona, ĉu ne? Ni trovis 7 instantáneamente. Sed ni estus trovita 7 rapidaj, ne gravas, en ĉi tiu ekzemplo kontre ĉi tiu ĉar se la nombroj estas ĉiuj ordo, multe kiel la paĝoj en telefono libro, vi povas ja haku duono de la problemo denove kaj denove kaj denove. Kaj ne tiom facila al vidi ĉi tion kun nur 8 nombroj kontraste al 1.000-paĝa telefono libro kie vi vere vidas vide, sed en ĉi tiu kazo tie kiam Estu serĉis 7, kiom da paŝoj en la plej malbona kazo estus ĝin portinta lin? >> [Studento] 7. 7 en la plej malbona kazo. Nu, en la plej malbona kazo ne 7 se estas 8 pordoj tie. Ĝi estus preninta lin 8 paŝoj. 

Do se ekzistas la n pordoj, ĝi povus esti prenita Estu paro jarojn n paŝoj. Nun, en via kazo, Alex, pro tio ke tiuj numeroj estas ordo - kaj ni povas ia inferir ĉi de kie ni estis tiel malproksime en tiu rakonto - kio estas la rula tempo de Alex pli inteligentaj algoritmo de ekde la mezo kaj tiam ripeti? [Studento] 3. >> Do tuj estos 3, malglate, se vi iros de 8 al 4 al 2 al 1. Do 3 paŝoj aŭ, pli ĝenerale, jen logo n denove. Ajn vi _halving_ kaj _halving_ kaj _halving_ kaj _halving_, jen esprimo de ĉi tiu ideo de logo n. Kaj por ke estus preninta vi nur 3 paŝoj, kaj ĝi efektive faris iam ni malfermis la pordojn _halving_ kaj _halving_, dum ĉi tiu estus preninta Estu iu 7 aŭ 8 paŝoj. Do dankon por esti kun ni ĉi tiun jaron. >> Dankon. Nice kunveno vi. Dankon al Alex. >> Same. [Aplaŭdo] 

Kio estas tiam la reala implikaĵo de tiu? Nun imagu ke ĝi ne estas 8 pordoj, kiuj, sincere, ĉiuj el ni povus trovi ion malantaŭ 8 pordoj bela rapide kun nur disŝiri la pecoj de papero kaj tuj kun niaj instinktoj. Sed kion se estas miliono pordoj? Kio se estas 4 miliardoj pordoj? En la kazo de 4 miliardoj pordojn, vi vere tuj volas iri kun Alex algoritmo, duuma serĉo al ni komencu nomi ĝin aŭ dividi kaj venki, pli ĝenerale, kie vi observos _halving_ kaj _halving_ la problemo, ĉar se vi havas 4 miliardoj pordoj, kiom da fojoj vi povas haku 4 miliardoj en duono? [Studento] 32. >> Fakte 32. Vi povas labori ĉi sur peco de papero aŭ en via kapo. Vi iru 4 miliardoj al 2 miliardoj al 1 miliardo al duona miliardo, al 250 milionoj, pentras, pentras, punkto. Kaj se vi faras ekster la math, vi tuj ja akiri 32, kaj tio efektive rilatas al komputiko, ĉar ni kutime rakontas en potencoj de 2. 2 al la 32 hazarde estas 4 miliardoj. Do tie estas multe da graveco al tiuj specoj de potencoj de 2 en komputiko. 

Sed kio pri 8 miliardoj? Kiom da paŝoj estas ke tuj prenos se estas 8 miliardojn da pordoj? [Studento] 33. >> Do 33. Kio se estas 16 miliardoj pordoj? Kiom da paŝoj estas ke tuj prenos? [Studento] 34. >> 34. Ni povus ia daŭrigu tiun ad nauseam. Sed tio estas potenca afero. Vi povas enkonduki miliardoj da pli enigoj al via problemo sed, neniu granda interkonsenton, vi simple prenu 1 plia mordo el ĝi kaj tiel donas al ni iun kiel duuma serĉo aŭ dividi kaj venki, pli ĝenerale. Sed mi estas speco de cheating tie, ĉu ne? En la kazo de Alex algoritmo, ŝi havis avantaĝon super Sean. Ŝi sciis, ke tiuj nombroj estis ordo, sed Alex ne devis ordigi ilin mem. Mi anticipe venis supren al la nigra tabulo kaj tipon de certigis ke mi tiris ilin ĉiujn ekster en ordo ordo, tiam mi kovris ilin per papero. Sed kiom laboro faris ke kapti min? Se ni dividis kun tiuj nombroj en iu kvazaŭe hazarda ordo - en ĉi tiu kazo tiuj simplaj numeroj 1 ĝis 8 tie - kiel ni iru sur ordigi tiujn valorojn? Se vi estus homo donis tiun taskon, kian intuicia proksimigo vi prenu al ordiga tuta amaso de nombroj? Tion ili aranĝiĝas tiel puzlo pecojn. Yeah. 

[Studento] mi prenus ĉiun numeron kaj kompari ĝin al ĉiu kaj observu tuj maldekstren. >> Konsentite, bona. Do prenu ĉiu nombro, kompari ĝin al la flanko de ŝi, kaj tiam simple observu movas laŭ la listo, ia rejiggering aĵoj kiel vi iros. Do jen ni havas ŝancon por eble kelkaj pli ulojn por implikiĝi. Ĉu ni havas ankoraŭ 8 volontuloj kiuj ravus sin levas? Iom malpli premo ĉar vi ne estas la sola. 1, 2, 3, 4, 5, 6, 7, 8. Venu malsupren. You guys tuj estos la numeroj 1 ĝis 8. Ni vidu se ni ne povas fari ĉi ordigado de Alex tiel en la sama maniero mi faris ĝin anticipe. 1, 2, 3, 4. Iru antaŭen kaj se vi volus, linio sur etapo inter la muziko stand kaj mi cxi tie en la sama ordo kiel la glito sur la ekrano. Uh-oh. Ni laboras vin en la sekva ekzemplo. Ho, atendu, atendu. Ĉi tie ni iru. Atendu. La sekva ekzemplo estas nun. Ĉi tie vi iros. Numero 8. Venu supren. Bone. Ordigi mem laŭ ĉi. Gliti malmulta al la flanko de la muziko staras tie. Do ni havas 4, 2, 6 - eniri tie, tie, dekstre tie - 3. Yeah. Okay. Vi iros tien. Ne, vi restu tie. Yeah, prava. Ne ke mi malpravas. Ĝuste tie. Konsentite, tre bona. Okay. Do nun ni ordigi ilin en kreskanta ordo. 

Kiel mi povas iri faras tion? La algoritmo kiu estis proponita antaŭ momento estis kial ni ne nur komparu la ulojn, kiuj estas speco de apud la alia kaj tiam fiksi ajnan erarojn, movi de maldekstre al dekstre. Do jen ni havas 4 kaj 2, evidente el ordo. Ni interŝanĝas vi. Okay. Do nun mi iros por movi tra la linio. 4 kaj 6, nope. [Ridado] 6 kaj 8, sufiĉe bone. 8 kaj 1, lasu min interŝanĝi you guys. Bone. Do 8 kaj 3, interŝanĝi you guys. 8 kaj 7, lasu min interŝanĝi you guys. 5 kaj 8, bonega. Mi donas al vi ordo listo. Bone. Do ne tute. Sed estas pli bone ĉar la grandaj nombroj - kazo en punkto 8 - esti speco de bobelis el la maldekstra sur la dekstran. Do mi atingis 1 el ili rajton, sed sentas kiel ĉi tio ne sufiĉe solvi la problemon. 

Do kion vi proponas ke ni faru? >> [Studento] Konservu fari ĝin. >> Ni observu fari ĝin. Kaj realigi, denove, ni starigis aĵojn por nur havi ĉiuj homoj speco de inteligente aranĝi sin bazas sur tiu foto, sed nun ni devas esti multe pli metoda. Ni devas esti algoritma pri ĝi kvazaŭ ni skribas kodo - en ĉi tiu kazo parola _pseudocode_. Do mi simple provi tion denove. Kiu funkciis sufiĉe bone. Ĝi ne solvis ĝin. Sed kiam dubas, nur provu kaj reprovu. Do 2 kaj 4, ne helpis plu. 4 kaj 6. Ah! 6 kaj 1, iomete pli bone nun. 6 kaj 3, bona. 6 kaj 7, 7 kaj 5, 7 kaj 8, bona. Kaj vi scias, mi probable povas ignori 8 nun ĉar li estas ĉe la fino de la listo. Eble ni ne devas zorgi pri iu iras preter li. Sed ni vidu se tio estas sekura supozo. Nun listo estas - malbenita - ne ordo. Ni provu ĉi denove. Do 2 kaj 4, 4 kaj 1, 4 kaj 3. 4 kaj 6, bona. 6 kaj 5, bona. 6, 7, kaj 8, bona. Sed rimarki, mi povas nur halti ĉi tie kaj nun haltos tie nun? [Studento] Jes. >> Jes? Kio se unu el vi estus la numero 9 tuta vojo tien? Ĝi estus ordo. >> Bona. Ĝi estus ordo la unua fojo ĉirkaŭe. Bona. Do ni iru returne. Ni estas preskaŭ tie. 1 kaj 2, 2 kaj 3, 3 kaj 4, 4 kaj 5, 5 kaj 6, 6 kaj 7, 7 kaj 8. 

Mi faris nun sed, denove, mi estas komputilo kiu povas nur faras kion mi diras al li, kaj mia sola rememoro nun estas, ke mi fakte ĝuste faris iom da laboro. Io ŝanĝis tie. Do mi ne teknike konfirmis vide aŭ Algoritma ke ĉi listo estas ja ordo. Do nur por bona mezuro, nur por esti anal pri tio, ni faru ĉi ankoraŭ 1 tempo. Do 1 kaj 2, 2 kaj 3, 3 kaj 4. Kaj vi scias kion? Nur por bonan mezuron, mi iros al konservi trako sur mia mano ĉi tiun fojon kiom da svopoj Mi faras ĝuste tiom ke mi scios kiom labori mi efektive faris. 3 kaj 4, 4 kaj 5, 5 kaj 6, 6 kaj 7, 7 kaj 8. Neniu svopoj. Do nun mi laŭleĝe esti idioto por fari ĉi denove ĉar se mi faris nenian laboron tra tiu paŝo de la homoj, tiam klare ke okazos denove se neniu el ili estas ia hazarde adversarially movi sin ĉirkaŭe. Do nun mi povas halti. Nun ni petas la demando, kiom da laboro tio ĉi reale preni min? Kiom da ŝtupoj ne ke preni? >> N kvadrato. Yeah, do n kvadratoj. Kie do vi ricevis n kvadratoj de? Vi devas kontroli ĉiun num - Tie estas n nombroj, kaj vi devas kontroli ĉiun numeron kun la aliaj n nombroj. Bona. >> Do ĝi estas n kvadratoj. >> Bona. 

Do sentas ĝin tre bone povus esti n kvadratoj, ĉu ne? Okazis n de tiuj infanoj, 8 specife en ĉi tiu kazo, sed ĉiufoje mi iris tra tiu listo mi komparas la unua persono kontraŭ la dua, la dua kontraŭ la tria denove kaj denove kaj denove, kaj kiam mi alvenis al la fino, kion mi faru? Mi redid ĝin. Do, se ni ĝeneraligi ĉi klarigo, ni n homoj kaj mi faras, evidente, 8 ŝtupoj, n paŝoj, ĉiufoje mi iras tra ĉi tiu algoritmo. Sed kiom da fojoj en la plej malbona kazo mi devas iri tra tiu listo de homoj? [Studento] N-foje. >> Probable n, vero, ĉar en la plej malbona kazo, kio estas probable la plej malbona kazo ordigo de tiuj infanoj de la get-go? Se ili estas tute renversita ordo ĉar ĝuste supozi mense, let's - Kio estas via nomo? >> Bowen. Bowen. Okay. Do Bowen, venu ĉi tien por nur momento. 

Supozu ke Bowen estis tie komence de la algoritmo, kaj ni ne scias, kion ĉiuj aliaj estas, sed Bowen tie, laŭ ĉi tiu algoritmo - kaj se vi volas nur promenas kun mi - tuj bobelo supren, kiel li faris la unuan fojon ĉirkaŭe, tuta vojo al la fino. Sed supozu ke la persono apud Bowen estis la numero 7. Mi devas reiri kaj akiri numero 7, kio signifas mi devas iri la tutan vojon reveni ĉi tien. Nun mi devas havi tiun saman promenadon kun la persono kiu estas numero 7. Sed kion se tiam numero 6 estis apud li tiel? Tiam mi devas reiri kaj akiri 6. Do denove, sur ĉiu ripeto de ĉi buklo mi parolas al ĉiu de la n personojn, kaj mi povus havi por fari n de tiuj promenadojn por certigi min tirante ĉiuj el la plej grandaj elementoj reen kaj reen kaj reen al la fino de la listo. Do n aĵoj n fojoj estas nur n × n aŭ n kvadratoj. 

Do jen jam ni havas algoritmon kiu ne plu n, jen ne plu log n, ĝi estas fakte malbona ol io ni faris antaŭe. Do Alex ia atingis bonŝanca en kiun Mi faris ĉion de la verko ŝajne supren fronto por ŝi, ĉiuj peniga laboro, por ke ŝi povis ĝui en ĉi duuma serĉo algoritmo, kiu estas log de n. Sed ĉi tiu estas konsekvenca kun lundo temo. Ni donis iom pli da spaco, oni uzas pli bitoj, por akceli nian rula tempo. Tiel kiel tie estas tio komerco-off inter tempo kaj spaco, tie povus ankaŭ esti nur komerco-offs inter tempo pasis supren antaŭa ia atingi aĵojn preta iri kaj fakte ekzekuti algoritmon kiel serĉo. Ni provu alian. Se vi infanoj ne gravas nur rapide reordigante vin egali ke denove, ni provu ion iomete malsama kie ĝi ne estas tiom simpla kiel simple ripari ĉiujn duoplarĝa erarojn, kiu estas super intuicia. Ni anstataŭ esti iom pli intenca kaj fari ĉi tion. Ĉi tiu tro Mi proponus estas probable bela intuicia. 

Ni elektu la plej malgranda persono el la listo denove kaj denove. Do jen ni iru. 4, vi estas la plej malgranda persono mi tiel vidas ĝis nun, do mi tuj mense memori ke por nur montrante vin nun. 2. Ooh! Forgesu pri numero 4. Mi nur trovis la novan malgranda elemento en tiu listo. Mi tuj ia memoras tion. 6, 8. Ooh! 1. Adiaŭ. Do nun mi iros al memori numero 1. Ni scias ke 1 estas la plej malgranda, sed mi estas la komputilo. Kio se estas 0? Kio se estas -1? Mi devas teni tuj. Do 3, 7, 5, nope. Okay. Do la numero 1 estis la plej malgranda. Lasu min elekti vin de la listo - we'll iri tiun vojon - kaj metis vin arbitre komence de la listo. Nun, atendu momenton. Mi ia trompis. Se ĉi tiuj infanoj reprezentas ne liston de 8 personoj sed tabelo, 8 pecoj de apudaj memoro - vi ĝenas tretante reen por momento? Estas vere ne spaco por vi ĉi tie. Nu do kiel ni faras spaco por - kio estas via nomo? >> Sammy. >> Sammy. Kiel ni faru spacon por Sammy? 

Ni movi la n kiuj estas antaŭ mi. >> Bone. Do ni povus kopii la n popolo, kiu estas antaŭ Li, do se vi infanoj volis preni 1 intenca, drama paŝo al la maldekstra. Ili ĉiuj faris ke en unisono, sed lastfoje mi skribis iom da kodo, vi ne povas ordigi de movi multajn aferojn samtempe. Ni povis fari ĝin en buklo, movante ĉiuj iam samtempe. Do se vi infanoj ne gravas tretante al la dekstra, kaj Sammy, se vi povus retropaŝon ĉar tie estas ankoraŭ loko por vi, nun ni faros. Kie estis Sammy antaŭ momento? Ĝuste tie. Do tie estas breĉo tie. Do vi povus movi en Sammy la makulo. Nun sekva persono supren kaj nun sekva persono, nun sekva persono. Nun ni havas ĉambron por Sammy. Nun, iu el la publiko - tio estis bona, kiu estis ĝentila, ĝi sentis iom temporaba - kio estas pli rapida? Yeah. [Studento] nova tabelo? >> Kio estas tio? >> [Studento] nova tabelo? >> Konsentite, bona. 

Do kohera kun tiu temo nur komerco-offs, kial ne mi simple fari novan tabelo  kaj tiam Sammy estos naĝante en la spaco antaŭ tiuj homoj, ekzemple, kaj ni povas nur komencas plenigi nova tabelo aro. Tio tro laborus. Sed mi ne interesiĝas pri elspezi pli spaco nuntempe. Kio estas alia alproksimiĝo? [Studento] Swap. >> Bone. Ni povus simple interŝanĝi tiuj 2 infanoj. Kio estas via nomo? Mario. >> Mario. Do Mario, vi estis aktuale tie. Sammy, vi povas subteni por nur momenta? Mario estis tie. Ni ne havas lokon por vi plu, do se vi ne gravas iri al kie Sammy estas, ni metos Sammy tie, kaj nun mi argumentas ke Sammy la interŝanĝante operacio estis multe pli rapida. Ni faris 1 operacio por interŝanĝi tiujn infanoj, aŭ eble 2 ĝis interŝanĝi tiujn knaboj, sed ni ne faris 1, 2, 3, 4, por ke sentu bone. Nun, atendu momenton. Mi ia faris la problemo malbona ĉar numero 4 estis speco de proksime al la komenco. Nun numero 4 estas iom pli proksima al tio, sed mi ne vere scias aŭ zorgas pri tio. Do ĉi tiu estas nur malbona sorto tiu numero 4 estas iom pli for de lia destinita loko. Do ni nun ripeti ĉi tiu algoritmo. 

Por recap, dum tiu rakonto estis, ĉiuj ni ne estis trairu la listo serĉas la plej malgranda kalkulitaj persono. Do nun ni faru ĝin denove. Ni ne devas maltrankviligi Sammy plu. Ni povas nur iru tien. Ooh! Numero 2. Tio estas bela malgranda nombro. 6, 8, 4, 3, 7, 5. Konsentite, bona. Kaj dankeme, per hazardo, mi ne devas movi - >> Willie. Willie ĉar li estas en sia ĝusta loko nun. Ni faru ĉi denove kaj ignori tiujn 2 infanoj. 6. Tio estas bela malgranda nombro. Ooh! 8 estas definitive pli granda. 4. Ni enfokusigi 4. Ooh! 3 estas eĉ pli bona. 7 kaj 5. Do kion ni faru nun kun - >> Roger. >> Roger? Ni interŝanĝas ĝin kun numero 6. Do se 6 kaj 3 ŝatus interŝanĝi, ni nun speco de alveninta bonŝanca en tiu 6 estas pli proksima al kie devus esti, sed estas nur koincido tie. Do ni nun iru tien. 8 estas bela malgranda nombro. Ooh! 4 estas pli malgranda. 6, 7, 5. Kion ni nun faru? >> Swap. >> Ekzakte. Do nun ni faros ĉi tia rapida. 8, 6, 7, 5. Kie 5 iri? Bona. Okay. 6, 7, 8. 6 gets resti kie ŝi estas. Kio estas via nomo? >> Rosalie. Rosalie gets resti kie ŝi estas. 7 alvenas al - Ni vidos. 7, 8. Okay. Do 7 ricevas resti kie ŝi estas. Kio estas via nomo? >> Amna. >> Amna. 

Do Amna gets resti kie ŝi estas, kaj la numero 8 estas jam kie li nun devus esti. Konsentite, bona. Sentas kiel ni ĵus kreis verkon por ni mem tie, though. Kio estas finfine la rula tempo de ĉi tiu algoritmo? Se ni pensas pri tiuj homoj ne 8 sed kiel n? >> Estas n. Ĝi estas n paŝoj, sed ni kontrolanta ĉiu unuopa tempo. Okay. N sed vi kontrolanta ĉiu unuopa tempo? Konsentite, sed se ĝi estas n paŝoj, cxu Mi povus ne povis ordigi vi per nur irante 1, 2, 3, 4? Ho! Konsentite, ke estas granda diferenco. Do n kvadrata kial? Kio vere okazas? Estas n homoj en tiu listo, sed por trovi la plej malgranda persono en la listo en la plej malbona kazo, kiom da ŝtupoj mi devas preni? >> N. 

N, dekstra, ĉar en la plej malbona kazo, nombro 1 estas la tuta vojo tien, do mi devas iri preni lin aŭ ŝin. Kaj poste, kiam mi fine realigi 1 estis la plej malgranda, tiam ĝi estas bela rapide interŝanĝi ilin. Sed nun mi devas komenci de la komenco kaj serĉi kiu? La sekva pli malgranda persono, kiu estas 2. Kie en la plej malbona kazo estas 2? Ho, mia Dio. Estas tuta vojo super tie je la fino. Do nun mi ĵus faris alian n paŝoj, alia n paŝoj. Kaj se ni havas n homo kaj en la plej malbona kazo la plej malgranda persono estas n paŝojn for, jen denove n × n, kaj do ni denove havas n kvadratoj. Ĉi tio ne sentante tiel bona. Kaj fakte, ecx en la plej bona kazo - supozi ke ili dividi ordo - kiom da paŝoj necesas por mi uzas tiun ĉi algoritmon por ordigi tiujn n popolo? N akordita. >> Mi aŭdis n kvadratoj. Kial n akordita? Ĉar vi ankoraŭ devas kontroli ĉiun solan fojon. >> Jes. Kaj vi devas interŝanĝi ilin. >> Kvankam ni homoj estas speco de ĉioscia en la senco vide ke ni povas nur ia vidi ke tiu estas ordo, komputilo ne estas tiu inteligenta. Ĝi tuj rigardi tie kaj tie kaj tie, sed se kio ĝi estas serĉi estas la plej malgranda ero, vi nur scias, ke vi trovis la plej malgranda ero de kiu punkto? Iam vi estas je la fino. Sed en tiu punkto vi nur trovis la nuntempe plej malgranda ero. Vi ne nepre scias ion ajn pri la stato de la mondo. Do vi devas iri denove kaj denove kaj denove. 

Do ĉi tiu tempo Mi vere aspektas muta ĉar mi kontrolas, bone, 2, vi estas la plej malgranda, sed mi ne scias, ke en tuta ankoraŭ. 3, 4, 5, 6, 7, 8. Konsentite, bona. 2 estis ja la plej malgranda. Nun ni trovi la sekva pli malgranda. Okay. 3, vi estas nuntempe la plej malgranda. Ni vidu. 4, 5, 6, 7, 8. Konsentite, atingis bonŝanca denove. 3 estis ĝuste en la ĝusta loko. Sed mi iros por subteni fari ĉi denove kaj denove kaj denove. Kiel ni povas fari nur milde bona? Anstataŭ havi homojn bobelo supren duoplarĝa de malgranda al granda kaj anstataŭ iri tien kaj reen tra la listo elekti la tiam malgranda persono, kial ni ne anstataŭ enmeti tiujn homojn en nova listo paŝo post paŝo? Ni provu tion. Nun mi nomas tion inserción varon. Do jen ni estas ĉi tie. Numero 1. Mi ne zorgas pri iu ajn en cxi tiu listo. Mia celo nun estas meti numero 1 al la komenco de ordo listo. Kaj mi tuj proponi kiam mi nur havas 8 pecoj de memoro, arbitre nun mi estas la muron inter mia supozeble unsorted listo, kaj cxiu, kiu estas malantaŭ mi, mi iros al postuli estas ordo. Do nun ni havas numeron 1. Mi volas enmeti lin en mian ordo listo, do mi simple tuj movi mian muron super ĉi tie, kaj nun mi diras ĉi listo estas ordo, ĉi listo estas Unsorted - almenaŭ kiom mi scias. Mi ne povas vidi ĉiujn numerojn samtempe. 

Nun mi hazarde renkontas numero 2. Kion mi faros kun li? Mi enigi vin nun en la ordo listo. Sed rimarki kiom facila ol estis. Mi nur devas serĉi. Nombro 1 estas tie. Ho, evidente 2 iras al la flanko de la numero 1. Nun kion mi faru kun 3? Mi enigi vin en la ordo listo. Sed tio estis super facila. Ĉi tiu estas super facila, ĉi tiu estas super facila, ĉi tiu estas super facila, super facila, super facila. Kaj nun ĉio estas ordo malantaŭ mi, kaj kiom da paŝoj ne ke preni? [Studentoj] N. >> Do ĝi estas nur n. Ni atingis bonŝanca. Estis nur n kial? >> [Studento] Ĉar la listo estis ordo. La listo estas jam ordo. Do ni havas bonŝanca. Sed ni desegnis algoritmo tiu tempo arneses tian sorton, ke bona kazo scenaron, por ne malŝpari nenecesajn tempo. Do ni nun havas, kion ni vokos bobelo specoj kie homoj ia bobelo supren duoplarĝa. Ni nun havas elekton speco kie ni deŝiri el la plej malgranda persono denove kaj denove. Kaj nun ni havas inserción speco kie ni ia proactivamente metis personoj kie ili apartenas en ĉiufoje ordo listo. Se ni povus, ronda de aplaŭdoj por tiuj infanoj tie. [Aplaŭdo] Ni prenu nian 5-minuta paŭzo tie. Kaj kiam ni revenos, ni estos blovi ĉiuj tiuj algoritmoj el la akvo kun io pli bona. Bone. Grandan antaŭdankon. Vi povas konservi tiujn kiel memoraĵojn. Bone. Ni estas dorso. 

Kaj recap reala rapida, ni havis tiujn 3 malsamaj aliroj al ordigado, la tuta punkto de kiu devis alveni al la punkto kie iu kiel Alex povus sercxi listo de nombroj rapide ol iu kiel Sean povis. Kaj eĉ se ni havas tian simplaj ekzemploj kun 8 nombroj, vi povus extrapolar facile al 8 paĝoj, 8 miliardoj retpaĝojn, aŭ 800 milionoj de amikoj en Facebook. Do tiuj algoritmoj povas certe grimpi al tiuj specoj de valoroj, kaj la ideoj estas finfine la sama. Do bobelo varo estis la unua, kie ni ia bobelis ĝis la plej granda persono tuta vojo al la rajto de homoj interŝanĝi duoplarĝa. Tiam ni havis kion ni vokos selektado speco kie mi iom pli intence tenis rigardante tra la listo, elektu la plej malgranda nombro denove kaj denove kaj denove, la logika rezulto de kiu estas, ke la listo estas eventuale ordo. Tiam en la tria, mi insertos popolon en ilia taŭga loko, kaj ni faris tre elpensita ekzemplo en kiu la listo jam ordo, sed tio estis por sendi la mesaĝon, ke en inserción speco de kazo, vi povas akiri bonŝanca. Se la nombroj estas jam ordo, ĝi estas nur tuj prenos vin n paŝojn por konfirmi tiel, dum elekto speco vi estas iom pli tunelan vidmanieron kaj vi ne iam rimarkas ke la listo estas jam ordo. Do ni vidu bobelo varo en agado tie. En jena ekzemplo, ni baldaŭ vidos vertikalajn liniojn kies altecojn reprezentas numerojn tiel ke ni povas ordigi de bildigi ordigi okazos. La pli malgranda la trinkejo, la plej malgranda de la numero, la pli granda la trinkejo, la pli granda la nombro. 

Kaj ni ludos ĝin en ĉi defaŭlta rapido. Ĝi okazas movi iom rapida por nun, sed ruĝaj estas kio montrante 2 stangoj esti komparitaj apud la alia. Kaj se vi rigardas zorge, kio okazas estas ke se la stangoj estas el ordo, la plej malgranda unu gets movis al la maldekstra, la granda unu al la dekstra, kaj tiam vi observos antaŭis. Do, se ni tion denove kaj denove, rimarki ke la plej malgranda stangoj tuj observu inching sian vojon al la maldekstra kaj la plej granda stangoj tuj observu inching lia vojo al la rajto. Kaj efektive, ni komencas vidi mastro tuta vojo sur la dekstra flanko samkiel ni vidis 8 kaj tiam 7 eventuale bobelis ĝis la fino de nia homa listo. Do ĉi tiu tuj tre rapide akiri iom teda, do lasu min deteni ĉi momente. Lasu min ŝanĝi la rapido esti multe pli rapida. Mi ne ŝanĝas la algoritmo, mi nur fari la kuraĝigo okazi pli rapide. Ankoraŭ bobelo varo, sama algoritmo, sed nun vi povas vidi multe pli rapide ol nia parola pruvo ke la plej granda eroj estas ja bobelis ĝis la supro. 

Kiel flanken, tiuj malgranduloj kvadratoj ĉe la malsupro maldekstro kaj malsupro dekstra estas nur iom recordatorios pri kiom da komparoj vi faras. Sed nuntempe, ni povas enfokusigi la piramido ke tio prenas formon, kaj tie iras. La plej malgranda ero estas en la maldekstra, la plej granda en la dekstra, kaj ĉio alia inter ili. Nun ni anstataŭ rigardu selektado varon. Mi tuj iros antaŭen kaj batis Alta. Ni tuj akiri novajn hazarda aro de stangoj. Selektado varo, revokon, iras tra la listo denove kaj denove kaj denove, plukinte el la plej malgranda ero. Do jen estas elekto varon. Ŝajnas ke la malpli da laboro okazas nun ĉar ni ne komparas duoplarĝa sed ni nur ordigi de ĉerizo prenante la plej malgranda eroj de dekstre maldekstren. Kiu portis tre malmulta tempo, tiel ke estas dicotomía jam. Nur ĉar algoritmo estas dirita al preni n kvadrata tempo, kiel bobelo speco kaj kiel selektado varo, tiuj estas vere plej malbona kazo kurante foje. Ekzemple, en la kazo de, ni diru, selektado varo, Mi vere estas elekti la plej malgranda persono kaj metante lin aŭ ŝin tie, tiam mi faras ĝin denove, tiam mi faras ĝin denove, sed ne estis malpeza optimumigo mi povus fari. 

Kiam mi kopiis la numero 1 here - Sammy en tiu kazo - Kion mi devas fari kun li post tio? >> [Studento] Lasu lin. Lasu lin, ĉu ne? Nenio. Mi ne bezonas cxiam parolas al Sammy denove ĉar se mi selektis la plej malgranda ero kaj metis lin tie, kial malŝparo tempo iras al la fino de mia tuta listo? La sekvan ripeto lasu min reale movi nur al la numero 2, nur al la numero 3. Do fakte, mi ne faris n aĵoj n fojojn. Mi faris n aĵoj, tiam n - 1 aĵoj, tiam n - 2 aĵojn, tiam n - 3 aferojn, tiam n - 4, pentras, pentras, punkto. Ni havas iom de geometria serio, kiu ĵus signifas vi adicianta supren progresive pli malgrandaj nombroj. Ne n + n + n + n sed n + 7 + 6 + 5 + 4 + 3 + 2 + 1. Kaj kion tio ĝenerale funkcias esti - Mi tuj salaton ĉe mia tablo tie por momento - ke tuj labori esti io kiel n (n - 1) / 2 se ni nur speco de rigardo al la dorso de math libro, kie vi havas ĉiujn cheat folioj por la formuloj. Se vi ĝuste aldonante ion n + n - 1 + n - 2, ĝi funkcias esti io kiel tio. Kaj se ni nur speco de multipliki ĉi eksteren, ke tio n kvadrataj minus n / 2. Mi konservis dirante n kvadratoj, tamen, kaj tio estas ĉar mi estis speco de prenante mensa ligilo ĉar fakte, n kvadratoj minus n dividita per 2 estas ja la vera nombro de paŝoj ke algoritmo kiel selektado speco prenus, se ni vere rakontis ĝis ĉiuj el tiuj komparoj kaj ĉiuj de la eta okupita laboro ni faris. Sed sincere, fojo n alvenas al esti kiel milionoj aŭ miliardoj, kiujn la heck cares se vi faras miliardo kvadrato minus unu miliardo dividita per 2? Al miliardoj kvadrato estas grandega nombro. Vi povas preni alian miliardoj ekstere de ĝi kun - n. Ne tia granda interkonsento. Do la pli granda la nombro atingas, la malpli grava tiuj malaltaj ordigita terminoj estas. Kiu zorgas se vi dividos 2 se vi parolas pri quadrillions de nombroj de paŝoj? 

Do ĝenerale, komputilaj sciencistoj emas forĵeti ĉion krom la plej grandaj termino, kaj ni nur speco de simpligi la mondo kaj diri ke tiu algoritmo prenis proksimume n kvadrataj paŝoj. Tio estas la rula tempo de algoritmo. Do ni revenos al tio en nur momento kun iu konkretaj ekzemploj, sed por nun, jen speco de la intuicia motivado malantaŭ nur simplificadora nia mondo kaj parolante pri la plej gravaj terminoj anstataŭ akiri en ĉiujn tiujn fancy formuloj. Por ke estis elekto varo, kaj ni ricevis iom bonŝanca tie. Ni rigardu inserción varon. Lasu min kaj komenci ĉi tiu siavice. Nun rimarki la mastro kiu okazas estas iom malsamaj, kaj ni komencis kun hazardaj nombroj, sed se ni vere rakonti ĝis la nombro de paŝoj en la plej malbona kazo, se la listo komencis tute en la dekstran ordo, ni nur preni n paŝoj por realigi tiel. 

Sed se la listo estis vere malantaŭen - ekzemple, en ĉi tiu kazo tie - tiam rimarkos ni efektive devas fari multe pli laboron en ĉi tiu kazo. Kaj ĝi devus ia sentas vin kiel ĉi tiu estas speco de laboro malfacila akiri tiujn plej malgrandaj elementoj al la maldekstra, kaj tio estas ĉar ni ricevis malfeliĉa. La listo estis ordo hazarde en inversa. Kontraste, kun inserción speco se ni imitas kion ni faris kun niaj homoj tie per startanta kun ĉiuj ordo kaj poste komenci, estas sufiĉe bona algoritmo, ĉu ne? Oni jam, fakte, ordo. Do ni provu resumi ekzakte kiom da tempo tio prenas ni per prezentanta nur iom de slango aŭ skribmaniero, ke fakte multe pli simpla ol la fanciness ia sugestas. Tion ĉi tie, ĉi granda a sur la ekrano, estas kion komputilo sciencisto estos ĝenerale uzi por priskribi la plej malbona kazo rula tempo de algoritmo. 

Denove, por plej malbona kazo, ĝi estas tute kunteksto-dependa. Kion ni celas diri per plej malbona kazo tute varias bazita sur la problemo ni parolas. Sed en la kazo de ordigado, kio estas la plej malbona ebla scenaro? Ĉiu estas malantaŭen ĉar nur sentas ke signifas multon da laboro por ni. Mi skribis tuj kelkajn el la algoritmoj kiuj ni vidis ĝis nun: lineara serĉo, duuma serĉo kiel kun la telefono libro aŭ la pecoj de papero, tiam bobelo varo, selektado varo, kaj inserción varo kiel ni vidis per niaj homoj, kaj tiam 1 aliaj ke tio eventuale tuj nomos kunfandi varon. Do en lineara serĉo en la plej malbona kazo, kiom da paŝoj necesas por trovi la nombro 7 se estas n pordoj kiel Sean alfrontis? >> [Studento] N. N. Do ni tuj skribos granda a de n. Mi nur tuj plenigi iuj spacoj. Tiu estas nur krado de spacoj. Sed en la plej bona kazo kun lineara serĉo, 7 povus esti ĉe la komenco de la listo, Kaj Estu eble komencis rigardi la komenco de la listo. Do se vi uzas lineara serĉo kaj ĝuste kontrolanta maldekstre dekstren aŭ eble dekstra al maldekstra - ili estas ekvivalentaj - en la plej bona kazo, kiom da ŝtupoj povus lineara serĉo, kiel Sean algoritmo, prenu? Nur 1 paŝo. 

Do mi intencis diri ke estas la omega skribmaniero. Tiu estas nur ĉefurbo omega. Omega estas nur la sexy maniero diri bona kazo rula tempo. Do, en la plej bona kazo la rula tempo estas sola paŝo aŭ konstanta nombro de paŝoj - 1 en ĉi tiu kazo - sed en la plej malbona kazo, granda O, estas reale n paŝoj. Kaj ĉi tiu tie, theta, ni fakte ne tuj rigardi ĝuste nun. Ne konvenas al ĉi tiu aparta ekzemplo. Sed nun ni provu duuma serĉo. En la plej malbona kazo kun duuma serĉo, kiom da ŝtupoj oni ĝin tuj prenos por trovi la nombro 7 aŭ kion ajn ni serĉas? >> [Studento] Log n. Ankoraŭ tuj prenos logo n ĉar ĝuste kiel Alex havas malfeliĉa kiam ni vere laboris tra la problemon metode kaj sxi ne trovis la numero 7 ĝis la lasta pordo ŝi rigardis, kvankam, en justeco, ŝi alvenis al forĵeti iujn pordojn survoje, duuma serĉo en la plej malbona kazo havas rula tempo de logo n. Kaj denove, kiu parolas al ĉi dividanta kaj konkerante. Sed kio pri la plej bona kazo? Kaj Alex efektive spertis ke plej bona kazo ĝuste kiam sxi venadis sur la scenejo. Kiom da ŝtupoj ne kiun portas en duuma serĉo? >> [Studento] 1. 1, nur ĉar ŝi atingis bonŝanca. Sed tio estas bone ĉar omega referencas al pli bona kazo scenejoj, bona kazo enigoj, eĉ se estas nur hazarda muta sorton. 

Nun, ĉi tro ni iras al nur ia permeso vakua por nun. Kion pri nun bobelo speco? En la plej malbona kazo bobelo varo, ĉiuj estas en inversa ordo, do ni devas fari multajn bobelanta. Sed kiom da paŝoj estas ke tuj prenos en la plej malbona kazo? >> [Studento] N kvadrato. Ĉi tiu estis la n kvadratoj, ĉar se vi opinias pri tio, se la listo estas tute malantaŭen - 8 estas tie, 1 estas super tie - kiel afero komencas bobelo, la numero 8 estas tuj movi tiel, tiamaniere, tiamaniere, tiel, sed kie estas la nombro 7 en la plej malbona kazo? Jen ŝi estas ankoraŭ tie. Do ni devas fari tion denove kaj denove. Kaj tie estas kie ni preni n paŝoj, tiam n - 1 paŝoj, tiam n - 2 paŝoj. Kaj se vi prenos mian vorton por tio - ke se vi ia multigos gxin, ĝi estas proksimume n kvadrataj en la fino kun iuj aliaj terminoj kiuj ni simple ignori ĉar nun - tiam en la plej malbona kazo bobelo varo n kvadratoj, donu aŭ preni. Sed kio pri la plej bona kazo bobelo speco? Kio estas la plej bona kazo scenaro? Ĉiuj nombroj estas ordo jam. Kaj kio estis la heŭristiko mi uzis, la lertaĵon mi uzis, kompreni ke mi faris nenian laboron kaj povis do halti frue? [Studento] Kontrolu ĝin unufoje. >> Kontrolu ĝin unufoje. Sed kio mi faras laŭ la vojo? Mi estis konservanta trako de kiom svopoj mi faris. Kaj mi komprenis, se mi ne kalkulis ajna svopoj sur miaj fingroj, tiam mi faris nenian laboron. Mi certe ne devas provi fari nenian laboron denove, do mi povas simple ĉesas. 

Do, en la plej bona kazo de bobelo speco kiam la listo estas jam ordo, kion vi dirus la omega skribmaniero, la plej bona kazo rula tempo? Ĝi simple n. Ni devas fari iun laboron, sed ni nur devas vidi 1 promenadon la valoro de laboro. Kaj ankaux cxi tie mi foriros ĉi tiun parton malplena. Kaj nun selektado varon. Selektado speco estis mi plukinte la plej malgranda persono denove kaj denove. Kaj kion ni diras la rula tempo de tiu estis? Tio estis n akordita en la plej malbona kazo. Kaj bedaŭrinde, en la plej bona kazo ĝi estas ankaŭ n kvadratoj ĉar mi ne havas la varon de ĉioscia vido de la tuta mondo; Mi nur scias pri plena ripeto ke mi ja trovis la plej malgranda persono. Do selektado speco ia sucks en tiu senso, sed la kapo estas la speco de intuicia. Estas bela facile kodi supren ĉar ĉiuj vi devas fari estas skribi paron de nestitaj por cikloj, tipe, kiu iras tra serĉas la plej malgranda ero kaj poste metas la plej malgranda ero kie ĝi apartenas al la fino de la listo. Do ankaŭ ĉi tie okazas esti komerco-off. La kvanto de tempo prenas vin pensi kaj efektive disvolvi iun por skribi kodo povus tre bone preni pli da tempo, se vi volas pli bonan algoritmon kaj rapida agado. 

Sed se vi vere nur ia kodo ion ĝis rapida kaj malpura kaj ĝuste ia prenu la stupidest ebla ideo vi povas pensi, kiuj povus fari al vi kelkajn minutojn al kodo, sed kun grandaj datenaroj vian algoritmo povas preni horoj por kuri. Kaj eĉ mi en postdiploma lernejo foje fari tiujn komerco-offs. Estus 3am, mi provis analizi iuj tre grandaj aro de datumoj rilataj al la sekureco esplorado mi faris, kaj tio estis bone elspezi 5 minutoj tweaking mia programo por analizi la datumojn, kaj iru dormi aŭ elspezi 8 horoj atingi ĝin nur rajtas tiel kuras tuj kaj ne iri dormi. Kaj do tro estas speco de konscia decido. Malpli disvolviĝo tempo, pli dormo. Retrospektive mi probable ne devus kuraĝigi ke kiam la celo tie estas optimizar kvalito de la kodo, sed tio tro en la reala mondo estas tre racia komerco-off. Malpli da tempo, malpli agadon aŭ inverse. Do jen ni fine trovos eblecon por paroli pri theta. Theta skribmaniero estas io komputilo scienculoj povas venigi en konversacio kiam granda a kaj omega hazarde estas la sama. Vi diras theta por vere sendi la mesaĝon ke ĉi tio estas speco de strikta baro. Ne gravas ĉu la scenejo estas bona aŭ malbona, ĝi estas n kvadratoj. Do estas nur ne grava en tiuj historioj tie. Inserción varo estas la lasta ni rigardis, kie mi ĵus enmeto ĉiuj en la ĝustan lokon. En la plej bona kazo kio estis la rula tempo de inserción varo kiel ni vidis tie? [Studento] La plej bona kazo? >> La plej bona kazo. 

Estis n ĉar en la plej bona kazo ĉiuj ordo, kaj Sammy kaj neniu alia vere devis movi ajn. Ili estis jam en siaj ĝusta loko. Do inserción varo en la plej bona okazo estas, en ĉi tiu kazo, n. Sed en la plej malbona kazo estas speco de n kvadratoj. Kial? Se mia listo de homoj estas en inversa ordo, Mi unue komencu per la nombro 8 kaj Mi enigi lin aŭ ŝin en la dekstra pozicio, kio estas korekta ĉi tie. Mi ia movado al la flanko. Tiuj infanoj estas Unsorted, li aŭ ŝi estas ordo. Sed nun mi hazarde trovos kiuj poste? >> [Studento] 7. 7 en la plej malbona kazo ĉar ĝi estas en inversa ordo. 

Do jen estas 7. Kie 7 apartenas? Definitive malantaŭ mi. Sed nun 7 fakte apartenas ne tuj malantaŭ mi, sed malantaŭ la numero 8, do mi devas diri, "Pardonu min, numero 8, vi povas bv movi ĉi vojo "Fari spacon por 7?" Nun mi renkontas 6. "Ho, pardonu min, numero 8 kaj numero 7, vi povas movi por fari lokon al 6?" Do alivorte, kun inserción varo, kvankam mi ne faras multe movado, la homo malantaŭ mi faras multe pli da laboro, kaj tio alvenis al kostis iu tempo. Ĝi tuj kostis la komputila tempo. Do, en la kazo de inserción speco ni ankoraŭ suferas. Se oni komencas aldoni ĝis la tuta nombro de paŝoj, ni finos bati krude n kvadratoj ĉar ĉi tiuj infanoj bezonas fari lokon por la homa esti insertos denove en tiu listo. Kaj tiel en tiu ĉi kazo theta estas simple ne aplikeblas al la aparta rakonto proksima. Tio estas ĉio bela kaj bona. Ni havas tiuj 3 malsamaj manieroj paroli pri la rula tempo. Sed kion signifas ĉi reale signifas en reala terminoj se oni vere provas kodi supren algoritmon? 

Lasu min proponi ke ekzistas eĉ pli bona algoritmo tie ke mem havas iujn komercajn-offs. Ni tuj nomas ĝin kunfandi varo, kaj ĝi estas speco de ĉi tiu magia algoritmo ke ĝuste funkcias pli rapide iel, kaj estas tiel facile esprimi, almenaŭ en _pseudocode_. La efektivigo de ĉi tiu algoritmo merge speco tuj estos kiel sekvas. Kiam vi donita n elementoj - n nombroj, n homoj, kia ajn - unua tie estas prudento ĉeko. Se n estas malpli ol 2, kunfandi speco nur haltas. Denove, por tiel diri. Kial vi haltas se n estas malpli ol 2? >> [Inaudible studento respondon] Ĝuste. Kaj denove, n estas ne la nombro en la listo, n estas la grandeco de la listo. Se n estas malpli ol 2, kiu signifas via lerta estas ĉu 1, kie vi evidente ordo se estas 1 numeron, aŭ 0, en kiu kazo ne estas nenio por ordigi, do ni bezonas tiun specon de bazo kazo. Se la listo estas tiom mallonga, ke estas nur nenio por fari, laŭvorte ne faras nenion. Reveni. Alie ordigi la maldekstra duono de la eroj, tiam ordigi la dekstra duono de la elementoj, tiam kunfandi la 2 ordo duonoj. 

Ĉi tiu speco de similas iom cheat per mi petas al vi kiel ordigi elementoj kaj vi diras al mi, "ordigi la maldekstra duono, ordigi la dekstra duono." Mi estas kiel, "Bone. Kiel vi ordigi la maldekstra duono?" "Ordigu la maldekstra duono de la maldekstra duono, ordigi la dekstra duono de la maldekstra duono, kaj tiam faris." Vi estas speco de cikle difini kion signifas ordigi, sed ĝi rezultas ke fakte brila en ĉi tiu kazo. Ne vere ĉi vicioso kiu neniam finas ĉar ĝi finos kiam? >> [Studento] Kiam vi atingos 1 afero. Kiam vi atingos 1 afero. Do eĉ se vi povus komenci kun 8 personoj kaj mi diras, "ordigi la maldekstra duono de tiuj homoj, tiuj 4 personoj, "tiam mi diras," Kiel vi ordigi la maldekstra duono? " "Nu, ordigi la 2 personoj ĉi tie." Kaj tiam vi estas kiel, "Bone, bone." "Kiel vi ordigi la maldekstra duono de tiuj homoj?" "Nur ordigi ĉi 1 persono ĉi tie." Kio estas la brila revelacio nun? Mi devas ordigi 1 persono. Faris. Mi ne devas fari ian laboron. Sed nun mi devas ordigi tiun personon, sed ili estas fraŭlo, nenio farinda. 

Do la magio ŝajne estas en ĉi tiu tria paŝo: kunfandi la ordo duonoj. Do kunfandi speco prenas ĉi brila kompreno, ke se vi rompas granda problemo malsupren en 2 pli malgranda, idente grandeco problemoj kaj tiam nur speco de gluo la plej malgranda solvoj kune je la fino, Mi proponas ke ni povas fari multe, multe pli bone [frapetante sono] ol la elekto varo aŭ inserción varon. Mi vere estis ignorante ke por duonhoro, sed mi vere ne scias kio okazas ekstere hodiaŭ. [Zumantaj sono] [ridado] Do ni vidu se ni povas vidi ĉi tion kun iom helpo de nia amiko Rob Bowden. Estas 2 grandaj paŝoj en la procezo de merge varon. Unue, senĉese fendi la listo de tasojn en duonoj gxis ni havas amason da listoj kun nur 1 taso en ili. Ne maltrankviliĝu, se listo enhavas nepara nombro kaj vi ne povas fari perfekte pura kortego inter ili. Nur arbitre elekti kio listo por inkludi la ekstra tason in Do ni fendi tiuj listoj. Nun ni havas 2 listojn. Nun ni havas 4 listoj. Nun ni havas 8 lertaj kun sola tason en ĉiu listo. Do jen ĝi por paŝo 1. Por paŝo 2 ni ree kunfandi paroj de lertaj uzanta la merge algoritmo ni lernis antaŭe. Kunfandi 108 kaj 15 ni finos kun la listo 15, 108. Kunfandi 50 kaj 4 ni finos kun 4, 50. Kunfandi 8 kaj 42 ni finos kun 8, 42. Kaj kunfandi 23 kaj 16 ni finos kun 16, 23. Nun ĉiuj niaj listoj estas de amplekso 2. Rimarki, ke ĉiu el la 4 listoj estas ordigitaj, do ni povas komenci kunfandi paroj de lertaj denove. Kunfandi 15 kaj 108 kaj 4 kaj 50 ni unue prenas la 4, tiam la 15- tiam la 50, tiam la 108. Kunfandi 8, 42 kaj 16, 23 ni unue prenas la 8, tiam la 16- tiam la 23, tiam la 42. Do nun ni havas nur 2 listojn de grandeco 4, ĉiu el kiuj estas ordo. Do nun ni kunfandi tiuj 2 listojn. Unue ni prenas la 4, tiam ni prenos la 8, tiam ni prenos la 15 kaj 16 kaj 23 kaj 42 kaj 50 kaj 108. Kaj ni faris. Ni nun havas ordo listo. 

Rob estis speco de utiligante iu kiun ni ankoraŭ ne faris. Oni sugestis, sed ni ne vere faras. Li faras ion fizike kun la tasojn sugestante li pasigis kelkajn rimedo krom tempo. >> [Studento] Spaco. >> Estis spaco. La fakto ke li havis tiun specon de bi-nivelo tablo kie li havis spacon ĉi tien kaj spaco cxi tie estis efektive implicante ke li uzas duoble pli da spaco kiel iu el niaj algoritmoj ĝis nun - inserción varo, bobelo varo, aŭ selektado speco - sed li utiligante tiun plian spacon al ia movado aĵoj tien kaj reen konservante aĵojn en ordo. Kaj eĉ se li sentas kiel ni poste ricevis al ordo listo, kiun sentis ĝin prenis iom da tempo. En realo, kion Rob faris estis ĝuste tiu algoritmo. Li unue prenis la problemon de amplekso n, dividita ĝin en maldekstra duono kaj dekstra duono. Tio estas, kiam li movis la tasoj. Tiam li ripetis tiun procezon. Li dividis 4 en 2 aroj de 2 pli tie kaj ĉi tie. Tiam li ripetis tiun procezon kaj dividita 2 en 2 aroj de 1 por ĉiu el tiuj diversaj tasoj. Kaj tie estas kie la brila ŝancon ekestas. En tiu punkto en la historio, Rob havis 8 listoj de grandeco 1, ĉiuj kiuj estis ordo jam. 

Tial kion li procedi fari? Duoplarĝa li prenis tiun ordo listo kaj tiu ordo listo kaj kunfandis ilin. Tiam li prenis ĉi tiu kaj kunfandis ilin, tiam ĉi tiu kaj kunfandis ilin, tiam ĉi tiu kaj kunfandis ilin. Kaj tiam kion li faros? Li tiam re-kuniĝis la granda lertaj kaj tiam re-kuniĝis la granda listoj. Kaj se vi pensas pri ĉi tiu nur intuicie por nun, kio li vere faras? Li dividis la problemo en duono, meze, meze, meze por atingi tiujn super malgrandaj listoj. Tiam li estis ia kombinante duobla, duopa, duobla, double. Do li faris duoble da laboro kiel ni vidis ĝis nun kun nenio engaĝante dividu kaj regu, sed neniu granda interkonsento. Duoble da laboro ne estas tiom granda interkonsento. Estas nur konstanta faktoro. Kaj kiel niaj aritmetiko esprimo antaŭe, mi nur tuj transiri el konstantaj faktoroj kiel fojojn 2. Kiu zorgas? Se ĝi estas 2 miliardoj fojoj 2, kiu estas ankoraŭ multe da ŝtupoj. Do ĉi kunfandi paŝo ŝajnas esti la ŝlosilo _insight_. Ni marŝas tra ĉi nur numere antaŭe - Ho, tio ne daŭrigi ankoraŭ. Ni marŝas tra ĉi numere nur por efektive vidi kiel ĉi ludas ekstere. Tio estas plejparte nur iom malriĉa viro kuraĝigo. Ni proponas tion. La rula tempo de merge speco - ni nur bezonas manieron paroli pri tio. Tio ne estas matematika; ĉi estas nur speco de konciza maniero de esprimi nin. Do T prezentas tempon kaj n reprezentas kio? >> [Studento] La grandeco de la - 

[Malan] La grandeco de la problemo, la nombro da personoj. Do mi asertas ke la rula tempo por ordigi n personojn tuj esti 0 kvanto de tempo se n estas malpli ol 2, ĉar se vi havas 1 taso aŭ neniu tasojn, vi havas nenion por ordigi. Sed pli ĝenerale, mi tuj proponi ke la rula tempo por ordigi n eroj tuj estos la tempo necesa por ordigi la maldekstra duono plus la dekstra duono plus - kio estas tio plian + n? >> [Studento] Merge varon. [Malan] Oni efektive kunfandi, ĉar se vi havas n / 2 eroj ĉi tie kaj vi havas n / 2 eroj ĉi tie, kiom da tempo estas bezonata por kunfandi ilin? Ĝuste kiel Rob, vi devas deŝiri ĉi tiu super ĉi tie, eble deŝiri super ĉi tie, deŝiri super tie, elsxiru super tie, elsxiru super tie. Vi devas tuŝi ĉiu el la tasoj unufoje. Kaj se estas 4 tasojn plus 4 tasoj, jen 8 tasojn aŭ, pli ĝenerale, 8 n tasoj. Do la fandado paŝo ni povas esprimi kiel n, kaj kiu laŭvorte engaĝas la nombro da fojoj Rob fizike tuŝis unu el tiuj Styrofoam tasoj. Do ni nun faru arbitra ekzemplo. Se tie estas 16 tasojn, kio estas la rula tempo de ordigi, uzante Rob algoritmo, 16 tasojn? Estas 2 fojoj la kvanto de tempo necesa por ordigi 8 tasojn ĉar ni havas 8 tasojn tie, 8 tasojn tie. Mi ne scias kiom longe tiu prenas, do ni komunigante ĝin kiel T por la momento. Kiu scias kio ĝi estas? Sed nun mi povas ordigi de rekursie aŭ ree demandi al la sama demando. Kiom da tempo estas bezonata por ordigi 8 tasojn? 8 tasojn Mi intencis diri prenas la kvanton de tempo necesa por ordigi 4 tasojn plus 4 tasojn, tiam kunfandi ilin kune. Fajna. Ni nun estas en ciklo jam. Kiom da tempo necesas por ordigi 4 tasojn? La tempo necesa por ordigi 4 tasoj estas 2 tasojn plus 2 tasoj ordigi pli la fandado procezo. Fajna. Kiom da tempo necesas por ordigi 2 tasojn? 2 tasoj estas la kvanto de tempo necesa por ordigi 1 taso plus la tempo necesa por ordigi alian tason plus la kvanto de tempo necesa por kunfandi, kiu estas nur 2. 

Fajna. Lasta demando. Kiom da tempo necesas por ordigi 1 taso? Jen estas la bazo kazo ke ni antaŭdiris ni volas bati antaŭe. La fakto ke ĝi prenas ne laboro ajn ordigi la plej malgranda el la problemoj signifas ke nun, ia grado lernejo stilo, ni povas simple iru komenci ŝtopanta tiuj nombroj reen in Ni nun scias, kion T de 1 estas, do mi povas ŝtopi en 0 por T de 1. Kiu donos al mi la respondon al T de 2, kiun mi tiam povas ŝtopi en pli supren. Kiu donos al mi T de 4, kiun mi povas ŝtopi en pli supren. Kiu donos al mi T de 8, kiun mi povas ŝtopi en pli supren. Kaj se mi efektive faros ke math ŝtopanta en tiuj respondoj, Mi poste atingi T de 16 estas 64. Kaj kion tio 64 reprezenti? Se T estas la 16, yeah, estas 16 fojoj 4. Do mi diras nun ke la rula tempo de ĉi tiu afero nomata kunfandi speco - kaj ĉi tiu tuj estos la fanciest de tiuj ni vidis ĝis nun - tuj estos nomata n logo n ĉar kiom da fojoj povas Rob fendi tuta amaso de tasojn en duono? Ensalutu n. Ĝi estas la sama kiel la telefono libro ekzemple, estas la sama kiel la aŭto-kalkula ekzemplo. 

Kiom da fojoj vi povas dividi ion en duono? Tamen, estas tio kunfandi paŝo. Vi eble devas dividi la tasoj en duono denove kaj denove kaj denove, sed ĉiufoje kiam vi iras al devas mem kunfandi. Kaj ni diris antaŭe ke kunfandi n tasojn prenas n paŝoj ĉar vi devas deŝiri el taso, elsxiru el taso, kaj vi devas tuŝi ĉiun pokalon fojo, nur kiel Rob faris. Do, se ni faras ion log n fojoj kaj ni faras n aĵoj sur ĉiu el tiuj iteraciones, ĉiu el tiuj halvings, ni havas n fojoj logo n. Do, se ni konektas en 16 en ĉi tiu ekzemplo, 16 fojojn ensaluti de 16 - Ne zorgu pri tio ĉi estas la kazo por nun ĉar mi ne desegnis la bazo - sed log'o da bazo 2 de 16 estas 4, 16 fojojn 4 estas 64. Sed kontraste, se ni uzas bobelo varo aŭ selektado varo aŭ inserción speco kun 16 ciferoj, kio estus la rula tempo estis se n estas 16? Estus 16 kvadratoj, kiu estas 256, kiuj eĉ se vi ne sufiĉe sekvis la tutan matematikon, 256 estas pli granda ol 64. Tio estas vere la magia takeaway tie. Kaj rimarki ke laborante tra tiu en plej malgrandaj ekzemploj kiel vi deziras en pset faras ĉion multe pli intuicia. Sed kion tio vere signifas en terminoj de la sento de ĉi tiu algoritmo estas la jena: Se ni vere rigardas merge speco tie - lasu min eltiri ĝin en tiu ĉi fenestro tie - ĉi tiu estas iomete malsamaj ekzemple per kiu ni devas ĉiuj 3 de tiuj algoritmoj - bobelo, selektado, kaj kunfandi - ĝuste apud la alia. 

Ili ĉiuj komencis kun hazarda trinkejoj, kaj tio estas bona. Neniu havas fundamentan avantaĝon super la aliaj. Mi tuj post momento klaki ĉiu el tiuj kuraĝigoj - Komenci, Komencu, Komencu - tiel rapide kiel mi povas tiel ke, krude, ili ĉiuj komenco samtempe, kaj ni konsideras ke bobelo speco de malbona kazo rula tempo estas kio? >> [Studento] N kvadrato. N akordita. Selektado speco plej malbona kazo rultempo estas? N akordita. Kaj merge varo estas ŝajne - eĉ se vi ne sufiĉe sekvi ĉiujn math nun, ĝi devos esti multe pli intuicia tra tempo - estas, ni asertas, n fojoj logo n. Kaj ĉar log n estas severe malpli ol n iam ni havas grandajn numerojn, n fojoj logo n estas pli malgranda ol n × n aŭ n kvadratoj. Do kion oni sentas reale esti pli bona algoritmo en terminoj de rula tempo, n fojoj logo n kontraste al n kvadratoj? Ĉi tie ni iru. Klaku, klaku, klako. 

Tion signifas uzi iun kiel merge varon. Ni havas momenton. Ni vidu kio okazas tie. [Chuckles] Kies mono estas ĉe bobelo speco? Ĝi prefere dependas de la enigo kelkfoje. Ni vidu. Venu. Sentas li reatingas. >> [Studento] Iru, bobelo speco! [Studentoj murmurado] [Malan] Jes, jes. [Studentoj murmurado] Iru, iru, iru! [Ĉiuj huraado] [aplaŭdo] Do nun kun 1 lasta, fina demo, se estas iom malfacila por kovri vian menson ĉirkaŭ la matematiko aŭ speco de la videbligo tie, vi povas efektive aŭdi la rapidoj de malsamaj algoritmoj malsame. Ĉi tiu estas kuraĝigo iu faris ke en la praktiko asociitaj sonas kun la procezo de interŝanĝante kaj la alteco de la stangoj. Kiel ni vidos tie, tie estas kelkaj pli ordigado algoritmoj tie ke homoj elpensis. Tiu unua tuj estos inserción varo, kaj ĉi flugos tra kaj donu al vi aŭdebla senco de kiel tiuj diversaj algoritmoj laboro. Jen inserción varon. [Elektronika beeping] [Malan] Bobelo varon. [Rapida elektronika beeping] [Malan] Elekto varon. [Rapida elektronika beeping] [Malan] Merge varon. [Elektronika beeping] [Beeping paŭzo] [ridado] [Malan] Gnome varon. [Elektronika beeping] 

Ĉi tiu estas CS50. Ni vidos vin proksima semajno. [Aplaŭdoj kaj huraoj] 

[CS50.TV]