[Jwe mizik] DAVID J. Malan: Tout dwa. Se konsa, akeyi tounen. Sa a se CS50, epi ki se nan fen semèn twa. Se konsa, sonje nan semèn ki sot pase yo plizyè, nou ve yo te depanse byen yon ti jan nan tan sou C, sou pwogramasyon, sou sentaks. Lè li nan byen nòmal, si w ap toujou goumen ak Set Pwoblèm 2, yo dwe frape tèt ou kont miray la. Li nan skre-kap mesaj erè ak pinèz ke ou pa ka byen kouri dèyè desann. Paske, Rest te asire, ki nan jis yon tan kèk semèn 'ou pral tounen gade dèyè sou bagay sa yo tankou Seza tande kòz, ak [? V-genair,?] petèt menm krak, ak reyalize jis ki jan lwen ou te vini nan yon kout peryòd de tan. Se konsa, si sa a, se nenpòt ankourajman, kwoke nan gen pou kounye a. Jodi a, menm si, nou kòmanse tranzisyon bagay nivo ki pi wo. Epi nou kòmanse pran pou yo akòde ke ou nèg konnen ki jan yo pwogram nan, oswa nan omwen kòmanse yo nan ki konfò nivo. Epitou, n ap kòmanse konsidere ki jan nou kapab ale sou desine pwogram plis efektivman. Ki jan nou ka ale sou optimize a efikasite nan algoritm nou an, epi jeneralman rezoud plis pwoblèm ki enteresan. Lè kòmanse pran pou yo akòde ke, si nou te vle, nou te ka Kòd moute nenpòt ki nan egzanp yo nou gen nan tèt li. Se konsa, jodi a, nou pa manyen klavye a pou nenpòt ki fòm nan kòd. Li pral pi wo nivo, ak finalman, sou rezoud pwoblèm-. Se konsa, pou li ale nan pwen sa, kite m 'pwopoze ki sèt ki anba la a rektang reprezante sèt pòt yo, dèyè ki se yon pakèt antye nan nimewo, nan mitan ki se nimewo a 50. Kite m 'pwojè sa a sou sa a ekran isit la tou. Men, pwopoze ke nou bezwen yon volontè ede jwenn mwen yon nimewo nan devan entènèt la isit la wè. Vini non sou moute, nan woz la. Tout dwa. Ki sa ki nan non ou? JENNIFER: [fèbl] DAVID J. Malan: Padon? JENNIFER: Jennifer. DAVID J. Malan: Jennifer. Tout dwa, Jennifer. Nice al kontre ou. Vini non sou yo. Se konsa, sa yo isit la yo se sèt pòt yo, ak sa ki Mwen ta renmen ou fè pou nou isit la, la devan tout kondisip ou, se jwenn nou nimewo a, 50. Pou w jwenn yon nimewo, ou ka gade vit dèyè nenpòt nan sa yo pòt pa senpleman frapan sou youn nan pòt yo, epi li pral revele nimewo li yo. Li kite yo wè ki jan byen vit ou ka jwenn nou nimewo a, 50. 15. 16. 50. Joliman fè. Tout dwa. Round nan aplodisman pou Jennifer. [Aplodisman] Tout dwa. Se konsa, sa ki te estrateji ou a pou jwenn nimewo a, 50? JENNIFER: um, mwen te panse petèt si - [Fèbl] DAVID J. Malan: O. Ba li yon dezyèm fwa. Se konsa, te estrateji ou a pou pou jwenn kantite a, 50? JENNIFER: Se konsa, mwen jis kòmanse nan la kòmanse wè sa ki nimewo nan premye te, ak Lè sa a, mwen te panse, petèt si yo ap klase, mwen pral jis kenbe frapan ki pi wo a? DAVID J. Malan: OK. Epi nou sanble yo te jwenn ke yo dwe ka-a. Malgre ke, se pou yo kale tounen kouch yo jis yon ti jan, epi ou vle ale pi devan epi revele pòt yo lòt ou ta ka te chwazi? JENNIFER: Oh, mwen renmen anpil. DAVID J. Malan:-Aa. JENNIFER: Se konsa, mwen jis te resevwa chans. DAVID J. Malan: Se konsa, ou gen chans. Tout dwa. Se konsa, pa move. Men, sa a yon enteresan insight, dwa? Si ou sipoze, epi ou te fè jwenn, tout bon, yon ti jan chans la. Men, si ou sipoze ke nimewo yo te Ranje, ou ka gen plis egzak sou fason ki enfliyanse konpòtman ou a? JENNIFER: Se konsa, si yo te klase, mwen te panse petèt pi piti pi gwo. DAVID J. Malan: OK. JENNIFER: Oswa si sa a te fini ke yo te reyèlman gwo, lè sa a pi gwo pi piti a. DAVID J. Malan: OK. Se konsa, pi gwo pi piti, oswa pi piti a pi gwo. Men, kite m 'pwopoze, ann sipoze ou te gen vinn malheureux, ak ta kwè ke yo yo pa te, an reyalite, Ranje, ki jan anpil nan sa yo pòt ta ka ou te gade vit dèyè nan ka sa a pi mal la? JENNIFER: Tout moun nan yo. DAVID J. Malan: Tout moun nan yo. Se konsa, kite a jeneralizasyon ke kòm n. Gen k ap pase yo 7, men kite a plis jeneralman di gen nan n pòt sou la ekran isit la. Se konsa, nan ka ki pi mal, ou ta gen gade dèyè 7 pòt yo, oswa n pòt yo. Se konsa, sa a vrèman se, li la yon ti jan nan chans jodi a, men li la reyèlman yon lineyè algorithm nan kalite, menm si ou yo te kalite sote alantou. Eske se sa ke jis? JENNIFER: Yeah. DAVID J. Malan: Bon, kite m 'wè si ou estrateji chanjman si mwen demenaje nou egzanp dezyèm nou an isit la ak 7 pòt diferan. Nimewo menm, men sa a fwa yo yo Ranje. Ki sa ki nan estrateji ou isit la pral fè, ap eseye mete yo deyò nan tèt ou ki sa nimewo yo lòt yo te - JENNIFER: OK. DAVID J. Malan: - pi bonè? JENNIFER: Ann kòmanse ak yon sèl la an premye. DAVID J. Malan: Tout dwa. Kòmanse ak yon sèl la an premye. 4. Koulye a, ki kote ou pwal ale, e poukisa? JENNIFER: 4 se reyèlman piti. Se konsa, si yo ap sòt petèt pi piti pi gwo, li ta dwe gen de fwa ke, ak -. DAVID J. Malan: OK. Ann wè, ki ou panse? JENNIFER: Eseye yon sèl an dènye. Nice. DAVID J. Malan: Trè joliman fè. Tout dwa. [Aplodisman] DAVID J. Malan: OK. Se konsa, w ap aktyèlman fè sa oribleman, paske w ap fè li trè byen. Ki kite nou kapab fè pwen sèten. Se konsa, kite nan eseye woule tounen isit la. JENNIFER: OK. DAVID J. Malan: Trè byen fè, Alòske. Se konsa, ou te kòmanse nan kòmansman an, ou te wè ke li, se te 4 Lè sa a, ou demenaje ale rete nan fen an. Men, si ou pa t 'jwenn chans la, ak ta kwè 50 te yon lòt kote. Ki sa ki te etap twazyèm ou a te? JENNIFER: Ale tounen nan kòmansman an. DAVID J. Malan: Tounen nan konmansman an. OK, se konsa ou ta te manyen sa a pòt, ki te 8. Tout dwa. Se konsa, sa a pa 50. Ki kote ou ta gen gade kap vini yo? JENNIFER: Si m 'pa t' konnen yo Ranje. DAVID J. Malan: kòrèk. Oke, si ou te fè konnen yo te Ranje - JENNIFER: Oh, t 'konnen, wi. DAVID J. Malan: - men ou pa t ' konnen ki kote 50 te fè ankò? JENNIFER: Jis kenbe prale. DAVID J. Malan: Tout dwa. OK. Kenbe prale. OK, pou m 'ka travay avèk. JENNIFER: OK. DAVID J. Malan: Koulye a, si w ap jis ale nan kenbe prale a, sa ki nan ou algorithm devolu te apiye nan. JENNIFER: lineyè a -. DAVID J. Malan: Li se kalite lineyè. Men, kite m 'pwopoze, se pou m 'mete yo sou tèren an. Kite m 'rafrechi paj an. menm nimewo, se li menm aranjman, pòt menm. Men, panse tounen nan jou sa a an premye nan klas lè nou chire yon liv telefòn nan mwatye, sòt de, ak sa ki te estrateji nou genyen? JENNIFER: Kòmanse nan mitan yo. DAVID J. Malan: OK. Se konsa, kòmanse nan mitan yo. Se konsa, kite a ale pi devan epi simulation sa. Kòmanse nan mitan an pa revele ke pòt. Se konsa, nimewo a 16. Se konsa, sa ta gen nèg la fò fè, ki chire liv telefòn nan mwatye, pou li ale nan devine a kap vini yo? JENNIFER: Ale nan sa a mwatye. DAVID J. Malan: Epi poukisa a dwat a? JENNIFER: Si yo te sòt de pi piti a pi gwo, Lè sa a 50 yo ta dwe nan ki fen. DAVID J. Malan: Bon. Totalman rezonab. Se konsa, tankou yon liv telefòn, ou ale nan nan dwa kòm opoze a bò gòch la, men isit la se Takeaway a kle. Ou kounye a ka jete, oswa detache, mwatye nan pwoblèm sa a, kite ou pa avèk 7 pòt yo, men vrèman ak jis 3. Ki se apeprè mwatye nan la gwosè nan pwoblèm nan. Tout dwa. Se konsa, kounye a ki sa ou ta gen fè apre ou fin ale dwat? JENNIFER: Se konsa, 16 se toujou trè piti, relatif nan 50, Se konsa, petèt m ap eseye, tankou, yon sèl sa a. DAVID J. Malan: Tout dwa. 42. Tout dwa, se konsa kounye a sa ki nan ou ensten di ou? JENNIFER: Mwen ka jete sa a ak Lè sa a, jis - DAVID J. Malan: OK. Bon, ou ka jete mwatye nan bò gòch la. JENNIFER: - chwazi yon sèl sa a. DAVID J. Malan: ak dwa la. JENNIFER: Yeah. DAVID J. Malan: Se konsa, menm si li difisil yo wè petèt, lè gen nan sèlman 7 pòt yo, panse osijè de, kounye a, konsistans nan la algorithm ou jis aplike. Nan ka a anvan yo, ou te fè jwenn chans, sa ki te gwo. Men, ou te fè sèvi ak yon eristik, Mwen ta ka di. Ou te itilize sòt de ensten ou a, ak konnen li klase, si li a trè ti nan kòmansman an, evidamman, nou te te resevwa yo ale pi plis a dwat la. Men, nan kèk sans, ou te resevwa chans, paske petèt sa a te nimewo a 100, e petèt 50 te pi plis nan mitan yo. Petèt 50 te menm sou isit la. Men, sa ou te fè yon ti jan diferan tan sa a te, ou te fè menm bagay la ankò e ankò. Apre sa, mwen ta diskite ke sa ou jis t ', kwake enfliyanse pa telefòn nan liv egzanp, se yon bagay ki pi plis algoritmik, ak anpil mwens espesyal gèn. Anpil mwens entwitif. Se konsa, nan fen jounen an, ki jan ta ou dekri efikasite nan la premye algorithm, kote ou te ale goch a dwat, kont la dezyèm algorithm isit la? JENNIFER: Sa a yon sèl ta dwe, tankou, petèt halve tan an, oswa menm plis, wi. DAVID J. Malan: OK, petèt menm plis. Ann pouse yon ti kras pi rèd sou sa. Ki sa ki reyèlman, si nou kontinye sa a lojik, nou definitivman mwatye a kouri tan ak sa a algorithm dezyèm pa jete mwatye nan la nimewo, men sa ki te fè nou fè sou pwochen an iteration, lè Jennifer devwale nimewo, dezyèm lan? Nou mwatye nimewo yo nan pòt ankò. Lè sa a, nou sa nou te fè apre sa, si , te gen plis pòt yo jwe avèk? Nou ta halve yo, li ankò, ak ankò, li ankò. Lè sa a te jis tankou ou nèg tout kanpe nan premye semèn nan klas, mwatye nan nou chita, mwatye nan nou chita, mwatye nan ou chita, jouk yon sèl Lone nanm te kanpe. Epi nou te di ke tan an kouri nan sa, ki kantite etap li te pran te sou lòd nan ki sa? Oratè 1: [fèbl] DAVID J. Malan: Se konsa, log baz 2 nan n, oswa jis plis tou senpleman, ale nan n. Se konsa, yon bagay logaritmik. Ak chema a pa t 'yon liy dwat ki jis te resevwa vin pi mal ak pi mal, li te sa a koub enteresan ki pa t ' jwenn tèlman mal sou tan. Se konsa, kite a kenbe fèm nan fè lide sa a. Se pou yo di mèsi Jennifer. Mesi anpil pou ap vini sou yo. Epi, yon sèl sec. Pa gen biwo lanp jodi a, men nou gen CS50 voye boul estrès. JENNIFER: ye. DAVID J. Malan: Tout dwa, isit la. Mèsi pou transfere estrès la moute isit la. Tout dwa. Se konsa, kite a wè si nou pa kapab kounye a formalizra sa a yon ti jan plis. Se konsa, ankò, sa nou jis te fè te esansyèlman menm bagay la jan nou te fè nan pandan semèn sa a an premye. Men, olye ke fen ak jis yon lineyè algorithm, ki nou montre deja tankou sa a liy dwat, lese pase ', si nou mete yon sèl plis pòt sou ekran an, Lè sa a, Jennifer ta yo te oblije gade, ki kapab, dèyè yon sèl pòt plis. Si nou mete de plis pòt yo, li ka gen yo gade dèyè de plis pòt yo. Se konsa, te gen sa a lineyè relasyon ki ekziste ant gwosè a nan la pwoblèm ki nan, di, aks-x la, ak kantite tan li pran yo rezoud sou y la. Men, foto a mwen te ou evoke pi bonè te liy sa a vèt. Green fè espre, paske li jis te santi pi bon. Nan teyori, algorithm a, lè nou te fè li ak liv telefòn, lè nou te fè li avèk ou mesye konte chak lòt, epi nan ka, dezyèm lan, lè Jennifer jis te fè li moute isit la, li te sòt nan fondamantalman pi byen. Paske li pa te jis de fwa kòm vit. Li pa t 'menm kat fwa kòm vit. Li te antyèman depann sou sa ki la gwosè nan D 'a te, menm jan nan ki jan anpil etap li finalman te pran yo. Se konsa, ide sa a ki senp ke nou tout te pran pou yo akòde ak liv telefòn, ka Menm jan an tou yo pral aplike nan yon bagay tankou sa a. Lè sa a ka gen plis dekontrakte li te ye kòm, jan ou ta ka imajine, divize ak konkeri. Pa kontrèman ak sa nou te fè, nan kou, ak liv telefòn. Men, pseudocode la, sonje, te sa a. Se konsa, nou pa pral fè sa a ankò, men sonje pandan semèn sa a an premye, tout moun nan nou leve kanpe ak Lè sa a mwatye nan ou chita bò tab la, mwatye nan ou chita bò tab la, mwatye nan ou chita. Sa algorithm te aplike nan yon ti jan nan yon fason ou kapab triche, nan sa, li pa te jis youn nan m 'konte, fondamantalman, pi plis efikasite. Nan ka sa a, mwen te swe yon resous segondè. Sòt de, plizyè proseseur, sèvo miltip, plizyè moun entelijan nan la chanm yo te ede m 'jwenn nan yon bagay lineyè nan yon bagay logaritmik, ki soti nan yon bagay wouj nan vèt yon bagay. Men, nan ka sa a, Jennifer pou kont li kapab fondamantalman amelyore sou la pèfòmans nan algorithm premye li pa, ankò, jis panse yon ti kras pi difisil. Epi, koulye a, lè li rive tan aplike bagay sa yo, n ap kalkile konnen sa ki liy nan Kòd ou ka ekri sa yo ke ou ka repete yo ankò, li ankò, li ankò, sòt de nan yon tan loupin. Paske nou pa ap ale nan gen nan liksye, tankou Jennifer te fè nan premye, nan jis gen yon pakèt tout ifs ak di, hmm, si nimewo sa a se premye 4, kite m 'vole tout wout la nan fen an. Ooh, si ladan nimewo a twò gwo, , kite m 'avanse pou pi abitrèman tounen eleman, dezyèm lan. Ou ap jwenn ke li nan ale nan gen yon bann pi rèd formalizra sa nou moun pran pou yo akòde kòm trè rezonab eristik, men yon òdinatè se sèlman pral fè sa ou di l 'bay fè. Koulye a, sa a gen trè enteresan enplikasyon. Sa a se graf sòt de vle di ke yo sòt nan sitèlman chaj vizyèlman, men avi, kote se liy lan tou dwat nan graf sa a? Kote graf la lineyè ke nou rele n? Oke, li nan sòt de nan direksyon anba a nan foto sa a, dwa? Se konsa, tout sa nou te fè se nou te sòt de agrandi soti nan aks dèz x la nan-yo ak aks-y la pou yo eseye jwenn yon sans nan sa ki lòt kalite koub sanble. Men, spesifik yo nan matematik la ekspresyon jodi a pa pral gen pwoblèm pou anpil, men remake ke gen nan yon anpil nan algoritm ki lwen pi mal pase yon bagay sa a, se lineyè. Vreman vre, n Gleason sanble trè move. 2 a n a sanble trè move. n okib sanble trè move. Epitou, n ap wè sa ki kèk nan moun ta kapab an reyalite jodi a. Epi louvri sesyon n pa santi kòm move, men pi bon pase n se log baz 2 nan n. Men, ou konnen, li ta yo te menm plis etonan si Jennifer, oswa si nou, semèn sa a an premye, te vini ak yon bagay ki boutèy demi lit plen boutèy demi lit plen n. Se konsa, nan lòt mo, gen nan sa a antye seri solisyon posib yo pwoblèm, men menm isit la, avi sa ki pral rive. Lè m 'rale soti, ki nan koub sa yo nan ki pral pwouve ke yo dwe absoli nan pi mal la nan yo menm ki sou ekran an kounye a? Se konsa, n Gleason sanble trè move nan moman an. Men, si nou rale deyò epi yo wè plis nan nan x ak aks aks-y, ki moun ki nan ale nan domine finalman? Se konsa, li aktyèlman sanble ke 2 a nan n, epi ou ka figi sa a soti jis pa rakorde nan kèk gwo de pli zan pli nimewo, epi ou pral wè ke 2 a nan n, tout bon, vin pi gwo pi vit. Si nou vrèman rale soti, yon 2 a nan n algorithm absoliman absorb. Mwen vle di sa a se pral pran byen yon ti jan nan tan pou la òdinatè désabonnement nan. Men, ou pral wè sou tan, espesyalman ak aparèy televisyon HD pwoblèm tan kap vini e menm pwojè final la, a se done ou a seri vin gwo yo, tout dwa? Menm nan vèsyon an premye nan Facebook, kòm nimewo a nan zanmi, ak nimewo nan itilizatè ki anrejistre te resevwa gwo, ou ka sòt nan telefòn li nan ak aplike yon bagay ki gen rechèch lineyè, oswa yon klasman trè senp algorithm, menm jan nou pral wè jodi a. Ou gen yo kòmanse panse pi rèd ak pi rèd sou pwoblèm sa yo. Men, ki kalite pwoblèm kote tankou Facebook, ak Google, ak Microsoft, ak lòt moun travay sou se egzakteman sa yo sòt de sòt gwo done nan kesyon de pli zan pli jou sa yo. Tout dwa. Se konsa, siksè Jennifer a nan ki dezyèm algorithm, franchman, li te fè étonant byen premye fwa a, men an kite ekri li kòm chans pou nou ka fè pwen sa a. Nan ka, dezyèm lan, li exploitées yon algorithm ki repete ankò, li ankò, men li te pran pou yo akòde yon sèten sipozisyon ke nou pèmèt li, men li eksplwate nan kèk detay dezyèm tan ke li pa t 'gen nan premye fwa. Ki te ki sa? Ki te lis la klase. Se konsa, le pli vit ke te lis la klase, nou reklamasyon ke Jennifer te kapab fè fondamantalman pi byen. 7 pòt yo, wi, se pa sa ki enteresan, Men, si li nou ap 7 milyon dola pòt yo. Log n se definitivman pral fè anpil, anpil pi vit nan kouri nan longè. Men, li te gen nan gen nan pòt Ranje pou li. Koulye a, mwen te pran libète a nan fè sa davans sou ekran an òdinatè isit la, men ta kwè se Jennifer te gen nan fè sa tèt li? Sipoze ke pòt yo nan kesyon reprezante done nan yon baz done, oswa zanmi anrejistre pou Facebook, oswa nenpòt ki sit entènèt paj sou entènèt la ki sou sit entènèt divès kalite ta ka bezwen endèks oswa rechèch sou. Sipoze ke ou jis te gen yon done anvan tout koreksyon mete e li te kite nou la a, oswa nan Jennifer fè sa klasman? Sa, olye, mande pou ke nou reponn kesyon an, byen, konbyen tan ki te vle arete Jennifer, oswa menm m ', sòt moun ki nimewo nan avanse konsa ke li te kapab pran avantaj de sa? Dwa? Paske enplikasyon a, nan kou, se si li pran m 'byen yon pandan y ap sòt chif yo, ki moun ki èk la traka ke ou ka jwenn yon kantite tankou 50 tèlman vit, tankou nan ka Jennifer a, si nou plis pase akable kantite tan total li te pran pa klasman bagay sa yo nan avanse, ki? Se konsa, kite a wè si nou kapab a pa penti foto a isit la. Mwen gen yon pakèt tout plis estrès voye boul, si ki ede kraze glas la isit la. Men, si ou pa ta lespri nou, nou bezwen sèt volontè - sou, OK. Wow. Se konsa, nou pa bezwen depanse sou lanp biwo, li sanble. Tout dwa. Se konsa, kouman sou ou de la devan. Kouman sou ou de nèg nan do. Se konsa, sa a, se kat. Kouman sou ou nan devan senk, sis ak sèt. Dwa a. Zanmi ou a montre ou soti, pou ou jwenn pwi an. Tout dwa. Vini non sou yo. Epi poukisa pa nou gen ou mesye vin sou sou isit la. Mwen pral ba ou chak nimewo yon. Men, ale pi devan epi fè aranjman pou nou idantik nan sa a repwezante sou ekran an. [Entèrpozisyon vwa] DAVID J. Malan: op, regrèt. Bug. Tout dwa. Oke, isit la nou ale. Nimewo senk. Nimewo sis. Youn, de, twa, kat, senk, sis, sèt. Oh, sa a se gòch. Oratè 2: Mwen pral jis jwenn yon -. DAVID J. Malan: Bon kontra. Tout dwa. Mèsi pou patisipe. [Aplodisman] OK. Tout dwa. Se konsa, nou gen kat, de, sis, yon sèl, twa, sèt, senk. Pafè pou nou gen sèt volontè isit la ki egal nan lajè a etalaj ke nou ap jwe ak pi bonè a. Apre sa, mwen te chwazi sèt pou rezon ki pral jis pratik nan yon ti kras. Men, mwen pral pwopoze premye ki nou sòt sa yo volontè sèt. Si w ta renmen, an premye, salye-menm si. Depi sa a ki pral yo dwe genyen yon gòch plizyè minit. Entwodwi nou. GRACE: Hi, mwen se favè Bondye a. Mwen se yon sophomore nan LEVERETT House. BRANSON: Hi. Mwen se Branson. Mwen se yon elèv nevyèm ane nan soude. Gabe: Hi. Mwen se Gabe. Mwen se yon jinyò nan Cabot. NEIL: mwen se Neil. Mwen se yon elèv nevyèm ane nan Matthews. JASON: mwen se Jason. Mwen se yon elèv nevyèm ane nan GREENOUGH. MIKE: mwen se Mike. Mwen se yon elèv nevyèm ane nan Grays. Jess: mwen se Jess. Mwen se yon sophomore nan LEVERETT. DAVID J. Malan: ekselan. Tout dwa. Oke, di ou mèsi a tout nou volontè isit la konsa byen lwen. Ak defi a nan men kounye a ki pral yo dwe sòt nan mesye sa yo, men Lè sa a, nou pral bezwen panse yon ti kras difisil sou ki jan avèk efikasite nou aktyèlman Ranje yo. Se konsa, kite a premye a eseye, sa a. Ou mesye ka wè nimewo chak lòt la jis pa mete alantou kwen yo. Ale pi devan epi pran yon kèk segond, ak sòt, nou menm soti nan pi piti sou la kite pi gwo sou bò dwat la. Ale non. OK. Bon. Sa te vrèman reprize vit. Koulye a, yon moun isit la, sa ki te algorithm nan ki mesye sa yo aplike? Oratè 1: Pi piti rive nan pi gran. DAVID J. Malan: OK. Pi piti rive nan pi gran se reyèlman sòt de la objektif, men mwen pa fin sèten sa a, se reyèlman yon algorithm. Pi piti rive nan pi gran pa di m 'etap-pa-etap sa yo dwe fè. Yeah? Oratè 1: [fèbl] DAVID J. Malan: OK. Se konsa, si ou wè yon moun ki pi piti pase nimewo ou, Lè sa a deplase nan dwa nan yo. Se konsa, ki la koulye a ap resevwa pi plis espresif, plis tankou yon algorithm, paske ou ka di, si sa a, lè sa a sa. Se konsa, nou gen kèk kalite kondisyonèl konstwi. Men, mesye sa yo te sanble yo fè sa yon kèk fwa, paske gen kèk nan nou te deplase yon ti jan nan yon distans. Se konsa, te gen prezimableman kèk kalite loupin ap pase nan lespri yo. Men, se pou a eseye formalizra sa. Si ou nèg ta ka Reyajiste tounen sa a aranjman. Ann wè si nou pa ka formalizra sa a yon ti jan, ak Lè sa a mande kesyon an, jis ki jan efikas sa a ye? Natirèlman, lè nou fè sa a pi dousman, li pral santi kòm bon nan yon algorithm, men kite a wè si nou kapab mete dwèt nou sou etap sa yo egzak. Se konsa, ou de nèg se kat ak de. Oswa ou kòrèk oswa enkòrèk lòd? Li evidan kòrèk. Se konsa, nou échanges. Koulye a, mwen pral pou avanse pou pi sou kote isit la ak di, kat a sis. Èske ou kòrèk oswa kòrèk? Gabe: kòrèk. DAVID J. Malan: kòrèk. Sis ak youn? Non. Swap. Se konsa, sa a, se de echanj. Sis ak twa? Non. Swap. Sis ak sèt? Sanble bon. Sèt ak senk? Jess: [fèbl] DAVID J. Malan: OK, swap. Men, Ranje. Tout dwa. Se konsa, evidamman pa, dwa? Se konsa, te gen plis pral sou. Men, tout bon, mesye sa yo, menm jis ensten. kenbe deplase. Yo pa t 'jis sispann, yon fwa yo korije yon pwoblèm. Se konsa,. Vreman vre, mwen pral gen fè menm bagay la. Mwen pral gen sòt nan tounen remonte nan konmansman an nan pwoblèm sa a, oswa nan konmansman an nan sa a seri moun, kite la kòmanse rele yo. Koulye a, kisa yo ta dwe algorithm mwen sou pas nan dezyèm ta dwe ye? Oratè 1: Menm bagay. DAVID J. Malan: Menm bagay. Lè sa a, mwen kòmanse renmen, dwa? Le pli vit ke ou ka jwenn tèt ou fè menm bagay la ankò e ankò, sa se vin pi plis tankou yon algorithm, ak mwens moun ensten. Se konsa, kounye a, isit la nou ale ankò. De ak kat? No Kat ak youn? Ah, te gen tout bon kèk travay toujou gen dwa fè. Pou ak twa? Bon. Kat ak sis? Sis ak senk? Sis ak sèt? OK, kounye a, fè. OK, pa gen. Mwen gen yo ale tounen. Se konsa, koulye a, ankò, nou ap fè sa a yon ti kras plis fè espre. Epi, koulye a, gen nan jis yon sèl nan sèvo egzekite sa a algorithm. Youn CPU, si ou pral. Men, franchman, sa a, se resous la sèlman nou pwal gen aksè a. Men, yon fwa nou tounen nan yon klavye epi yo gen yon bagay tankou C nan nou an jete, nou ap sèlman ekri yon pwogram ki ka fè yon bagay nan yon tan. Lè nou konsidere ke, mesye sa yo yon ti moman de sa, nou exploitées sèrvo kolektif yo tankou ou nèg te fè nan zewo semèn. Se konsa, kite a kontinye ap fè sa. De ak yon sèl. De ak twa. Twa ak kat. Kat ak senk. Senk ak sis. Sis ak sèt. Fè konsa? Se konsa, mwen menm ki, men kite m 'jwe avoka dyab la. Èske mwen, sòt nan nan òdinatè ki moun ki jis te fè yon pase nan sa a seri moun, konnen ke mwen fè konsa? Oratè 1: No DAVID J. Malan: Se konsa, poukisa? Ki sa ki ta mwen gen fè yo nan lòd yo konkli décisif ke mwen fè konsa? Pwobableman yon sèl plis pas la. Dwa? Paske tout mwen konnen ki soti nan ke anvan yo pas se ke mwen korije yon erè. Ak sa vle di, petèt gen nan toujou yon lòt erè ke mwen bezwen korije. Se konsa, mwen ka sèlman asire w ke pa ranbobine, ak Lè sa a, kont kouran, youn a de, de, ak twa, twa ak kat, kat ak senk, senk ak sis, sis ak sèt. OK, koulye a, mwen t 'fè okenn travay. Mwen ka sètènman sonje ke mwen te fè pa gen okenn travay avèk yon bagay tankou yon varyab, renmen yon Int. Rele li echanj, epi si echanj se 0, yon fwa mwen jwenn isit la, epi li te kòmanse nan 0, Lè sa a, Mwen ta jis pou estipid kenbe pral dèyè, yo soti, tcheke ankò, li ankò, epi ankò, dwa? Paske ou jwenn kole nan kèk kalite bouk enfini. Se konsa, le pli vit ke gen nan 0 echanj, nou kapab fè reklamasyon ke sa a algorithm se vre konplè. Koulye a, kite a mete yon Non sou sa. Algorithm nan ke mwen pwopoze nou jis aplike se yon bagay yo rele ti wonn sòt, yo konnen kòm sa yo nan sans ke nimewo yo ki pi gwo kalite jarèt wout yo moute sou tèt la, oswa jiska nan fen a nan etalaj la nan nimewo. Men, ki jan efikas sa a te algorithm? Konbyen etap mwen te fizikman gen pran, pou egzanp, sòt sa yo sèt moun? Kat a senk? OK, twò anpil se finalman yo pral repons lan. Men, menm lè sa a, kantite espesifik se pa konsa pou sa ki enteresan. Se pou yo jeneralizasyon li kòm n. Se konsa, si mwen te n moun Moute bò isit, epi yo te, sòt de, yo nan lòd o aza nan la kòmanse, nan ki lòd orijinal la. Oke, ki jan anpil etap t 'mwen gen pran sou pas an premye? Li te youn, de, twa, kat, senk, sis, e yo ap sèt moun, se konsa sa a, se sèt, sis -, se konsa sa a, se n mwens yon sèl etap premye fwa a. Koulye a, ki jan anpil etap t 'mwen gen yo pran lè m 'rewound? Oke, nou te ka aktyèlman double ke si nou reyèlman te vle, men pou kounye a, mwen se jis ale nan di, tout dwa, yon lòt n mwens 1. Se konsa, mwens la n 1 ki pral jwenn anmèdan kenbe tras nan, se konsa kite a jis wonn moute yon ti kras. Se konsa, 2n etap. Se konsa, 14 etap, bay oswa pran. Konbyen fwa pou mwen pran yon etap tan an kap vini yo? Oke, li nan 3n. vrèman. Epi, koulye a, nan ka ki pi mal la, pou egzanp, konbyen fwa mwen te vle ale dèyè, yo soti, retounen ak lide, egzekite sa a algorithm, échanjé moun sou chak pas, mal? Li nan aktyèlman n okib, dwa? Paske nan ka ki pi mal, ou kapab kalite nan panse sou sa a entwitif, menm si li ta ka pran yon ti kras ti jan nan tan koule pous Nan ka ki pi mal la, Ki sa ki ta sa yo sèt moun te te sanble, nan tèm de aranjman a nan nimewo yo? Konplètman bak, dwa? Epi jis nan simulation sa, sa ki te non ou ankò? MIKE: Mike. DAVID J. Malan: Mike? OK, Mike, yo ka ou jis rantre nan m 'plis pase isit la pou jis dezyèm yon sèl? Aktyèlman, pa gen okenn. Padon Mike, remonte kite a. Ki sa ki nan non ou ankò? NEIL: Neil. DAVID J. Malan: Neil. OK, Neil, ou vini ak m ', si ou pa chonje. Se konsa, mwen pral pwopoze, jis pou senplisite, ki Neil se kounye a nan li pi move ka posib. Men, sonje ki jan mwen aplike algorithm mwen. M ap konpare, konpare, konpare, konpare, konpare, o. Koulye a, mesye sa yo ap soti nan lòd, se konsa mwen ranje. Se konsa, ou nèg swap. Men, konsidere kounye a, konbyen lajan pi lwen Neil gen yo ale? Li nan apeprè n. Ou konnen, li pa nan aktyèlman n. Se tankou, n mwens 1, men mwen ap resevwa énerver tras kenbe nan ti kras nan nimewo, se konsa kite yo jis rele li n. Se konsa, si Neil deplase yon sèl etap omaksimòm chak tan, epi pou avanse pou pi Neil yon sèl etap, Mwen gen fè sa-a pase reyèlman fatigan dèyè, yo soti, sa a se apeprè fè sa, n etap, yon total de n fwa, paske li pral pran m ' ki etap anpil yo ka resevwa Neil tout wout la nan kote li ki dwe. Se pou kont li tout lòt moun si ou mesye tout te misyon te bay lòd yo tou. Se konsa, kite a rele sòt ti wonn n okib. Tan nan kouri sa a algorithm, nan pèfòmans sa a algorithm, nan efikasite nan sa a algorithm, nou pral jis dekri plis jeneralman kòm n Squared. Ki se bèl, paske mwen te kapab fè nan menm egzanp ak wit moun, nèf moun, yon pèp ki milyon dola, epi ki repons a pa pral chanje. Se konsa, si ou nèg pa ta lide, se pou yo Reyajiste ou nan kote ou te kòmanse. Li kite yo eseye de apwòch ak lòt wè si nou pa ka fè fondamantalman pi bon pase sa a. Se konsa, tan sa a, mwen pral pwopoze yon sòt de algorithm diferan. Sa ki te trè entelijan nan nou dènye fwa, epi ou mesye yo te dwa gen nan ensten dwa nan jis kalite nan échanjé pèr. Men, si mwen reyèlman te vle apwòch sa a tou senpleman, ak objektif mwen an se pou avanse pou pi tout nan nimewo ki pi piti yo fason sa a, ak pouse tout nan nimewo ki gwo ki fason sa a, poukisa m pa jis fè sa nan la ki pi nayif fason posib ak wè si mwen ka fè pi bon pase sa ki te yon san patipri konplèks algorithm? Se konsa, kite a wè. Kat se yon nimewo bèl ti, se konsa mwen ale nan kite ou gen ti moman. Ooh, nimewo de a se menm pi bon. Se konsa, ou ka jis etap pou pi devan pou yon moman? Sa a se kounye a nimewote pi piti mwen kandida, ak mwen pral sonje ke ak, tankou, yon varyab. Men, Mwen pral kenbe tcheke. Èske gen yon moun ki gen nimewo a se pi piti a? Sis, pa gen. Oh, gen nan Neil ankò. Se konsa, mwen pral pouse ou tounen sòt de concept. Neil ap vini pi devan. Koulye a, varyab la ke mwen lè l sèvi avèk kenbe tras nan ki gen pi piti a nimewo ki mete ajou a ki genyen Kote Neil la. Oke, kite la wè. Twa, sèt, senk. OK, mwen konnen Neil te pi piti a. Ki sa ki nan bagay la ki pi senp pou mwen pou m fè kounye a? Mwen pa pwal gaspiye tan mwen pa jis bouyònman Neil yon sèl plas sou bò goch la. Poukisa nou pa mwen jis mete Neil kote li fè pati, ki se nan kou ki kote? Tout wout la nan kòmansman an. Se konsa, Neil, vin avè m '. Ak sa ki te non ou ankò? GRACE: Grace. DAVID J. Malan: Grace. OK. Se konsa, Grace, malerezman, w ap kalite nan chemen an. Se konsa, ki jan nou rezoud pwoblèm sa a? Dwa? Si sa a se yon etalaj, gen nan sèlman sèt kote yo ye. Sonje byen,, ak Rob, nou te pale osijè de deklare laj, epi yo nou sèlman te gen yon fini nimewo ki gen laj ki? Menm lide isit la. Nou sèlman gen yon nimewo fini nan antye. Grace se kalite nan nou an fason sa a, Se konsa, kouman nou ranje? Fason pi senp la, se tankou, Grace, regrèt. W ap ale nan gen yo ale sou gen pou nou ka fè chanm. Koulye a, si ou panse sou sa a, petèt nou jis te fè pwoblèm nan vin pi mal. E petèt nou te fè, paske sa si Grace te nan plas la dwa? Men, nou konnen li la pa, paske otreman, li ta yo te kanpe pou pi devan olye pou yo Neil nan moman sa a, dwa? Nou deja tcheke nimewo l 'deyò. Tout dwa. Se konsa, koulye a, Neil a nan plas la dwat, ak Mwen kapab fè yon optimize ti tay. Pou minit kap vini an, mwen pral inyore Neil tout ansanm, se konsa yo pa gaspiye tan l 'yo, oswa aksidantèlman swap l 'nan plas la mal. Se konsa, kounye a, ki jan mwen jwenn pwochen an eleman ki nan pi piti a? De. Sa se yon nimewo trè bon, si ou vle nan etap pi devan ak Mwen pral sonje ou. Sis, pa gen bon. Kat, twa, sèt, senk, pa gen bon. Se konsa, kite m 'deplase ou nan kote dwat ou. E nou jis te resevwa chans tan sa a. Koulye a, mwen pral inyore sa yo de nèg, epi kounye a fè yon sèl plis pase nan sa a. Sis, ki yon kantite trè piti. Vini non sou pi devan. Oh, regrèt. Nimewo Grace a se pi bon, se konsa etap sou pi devan. Kat. Padon, favè Bondye a. Ale tounen ankò. Nimewo twa se pi bon. Gen sèt pen. Senk. Epi, koulye a sa ki nan non ou ankò? JASON: Jason. DAVID J. Malan: Jason. Se konsa, Jason se kounye a pi piti a eleman Mwen te chwazi a. Ki kote li pral yo ale? Se konsa, kote sis se. Men, non ou se ankò? Gabe: Gabe. DAVID J. Malan: Gabe. Gabe a nan chemen an. Ki sa ki nan bagay la pi fasil fè? Swap mesye sa yo de yo e yo kontinye. Se konsa, kounye a kite a wè. Ki moun ki nan pi piti a? Kat. Kite m 'jis kalite tronpe. Senk a pwal pi piti a. Mwen jwenn kap vini an, si, ou vle nan etap pi devan, sa m 'genyen fè ak mesye sa yo, ak Gabe? Swap ankò. Se konsa, koulye a, toujou yon ti kras parèt nan lòd. Mwen te jwenn Gabe yo dwe pi piti a, se konsa Mwen pòp l 'soti, deplase ou nèg sou. Men, fè. Se konsa, repons se menm bagay la. Rezilta a nan fen an se menm bagay la. Kilès nan de sa yo algoritm se pi bon? Yon sèl, dezyèm lan, mwen tande. Poukisa? Oratè 3: Li nan n etap [fèbl]. DAVID J. Malan: Li nan etap n nan ki pi. Enteresan. Se konsa, li menm si? Se konsa, kouman mwen te jwenn nan pi piti a eleman? Konbyen etap t 'mwen gen yo pran jwenn nan eleman ki pi piti a? Mwen te gen yon gade tout wout la nan fen a, dwa? Paske nan ka sa a pi mal la, ki sa ki si Neil yo ki te reskonsab isit la? Se konsa, jis jwenn eleman ki pi piti a pran m 'n etap, oswa n mwens 1. Men,, OK. Se konsa, ranje Neil. Sonje ke, yon minit oswa konsa de sa. Men, ki jan mwen te jwenn pwochen an pi piti a eleman? Li nan n, 1 mwens oswa n mwens 2 reyèlman, soti nan nimewo a nan etap. Se konsa, OK. Se konsa, mwen t 'n mwens 2. Tout dwa. Se konsa, ki santi l yon ti kras pi byen. Tout dwa. Konbyen etap tan kap vini an jwenn kantite twa? Se konsa, n mwens 4. Se konsa, li la diminye, yon sèl mwens etap sou chak iteration. Se konsa, sa a santi yo pi byen, dwa? Si tan sot pase a li te apeprè n fwa n, tan sa a li nan n, 1 mwens plis n mwens 2, plis n mwens 3, plis n 4 mwens, dot, dot, dot. Men, si ou sonje nan lekòl segondè ou a liv lekòl, tronpe a ti kras fèy nan do a ki gen fòmil, si ou ajoute jiska seri sa a nan nimewo, ki sa ki kantite total etap yo pral ke mwen pran isit la? Sa a se youn nan moun ki, tankou, n mwens 1, fwa n, divize pa 2. Se konsa, kite m 'wè si mwen kapab rale sa a moute sèlman pou moman yon. Li di ankò: mwen se kalite awondi kèk nimewo jis kenbe lavi nou ki senp, men jan mwen sonje, li la yon bagay tankou si Mwen fè n mwens 1 bagay sa yo, Lè sa a, n mwens 2, Lè sa a, n mwens 3, li nan apeprè yon bagay tankou sa plis pase 2, ak si mwen fè anpil anpil pitit sa a soti, sa a, se aktyèlman n kare. Sa pa nan santi twò bon. n mwens n plis pase 2. Men, isit la bagay la. Nan syans òdinatè, lè pwoblèm sa yo kòmanse jwenn enteresan an se lè n vin reyèlman gwo. Lè n ap vin vrèman gwo, ki nan valè sa yo ki pral domine tout nan lòt moun yo? Li nan kalite okib n la, dwa? Wi, divize pa 2 se trè bon. Men, si ou ap pale de dè milya nan moso nan done, oswa trillions de moso nan done, OK, se konsa w ap de fwa tankou vit. Men, ki reyèlman sousye si ladan nimewo gwo, si sa a faktè a se sa ki vin pi gwo ak pi gran. Men, siman, li fè plis nan yon diferans pase sa a Guy. Se konsa, menm si ou nèg gen rezon, an dezyèm algorithm, nou pral rele li sòt seleksyon an, se, nan mond reyèl la, yon ti jan pi vit ki kapab, paske mwen menm, pran mwens ak mwens etap chak fwa. Li nan pa reyèlman fondamantalman pi vit. Paske si nou aktyèlman jwe sa a soti pou valè gwo n, nan fen jounen an, pou n gwo ase, li la toujou pral santi trè dousman. Oke, kite m 'pran yon dènye pase nan sa. Sa a ki sa mwen ta rele sòt seleksyon an. Èske ou ka mesye Reyajiste tèt nou yon dènye fwa? Men, nan ka sa a sot pase yo, mwen pral pwopoze yon bagay rele sòt mete l lan. Sòt ensèsyon yo te, concept, yon ti jan diferan. Olye de sa pase pral dèyè, yo soti ak chwazi eleman ki pi piti a, mwen se jis pral fè fas ak chak nan sa yo mesye jan mwen rankontre yo, li mete yo antre nan kòrèk la plas yo. Se konsa, mwen jis ale nan kòmanse ak Grace, ak mwen wè ke li la nimewo kat. Ki kote nimewo kat apatni? Mwen pa gen te kòmanse klasman anyen, se konsa Grace vin rete dwa gen. Epi, koulye a mwen pral reklame, si ou te kapab pran yon etap a dwat ou, sa lis Ranje m 'yo, sa a se mwen klase lis ki rete yo. Se konsa, kounye a mwen pral kontinye kap vini an, ak sa ki nan non ou ankò? BRANSON: Branson. DAVID J. Malan: Branson. Se konsa, Branson se nimewo de. Se konsa, mwen pral pran ou soti pou yon moman. Epi, koulye a, ki kote ou fè pati nan sa a etalaj? Se konsa, sou bò dwat la nan favè Bondye. Se konsa, ankò, nou se kalite fè Grace fè yon anpil nan travay isit la. Ki kote nou mete ou? Se konsa, nou ap ale nan glise ou a kite, ak insert Branson la. Men, koulye a, mwen reklamasyon ke Ou mesye yo ap fè. Men, avi, mwen pa lè l sèvi avèk espas anplis. Li nan toujou 2 eleman isit la, 5 sou isit la. Gwosè yo etalaj se 7, se konsa mwen pa kopye yo, tout dwa? Se konsa, kounye a nou gen la, ak Gabe isit la, nimewo sis, kote ki mèt ou? Ou gen chans ankò. Se konsa, ou jwenn yo rete dwat la. Jis pran yon etap ti tay a dwat a jis fè klè ke w ap Ranje. Epi, koulye a nou gen Neil ankò, nimewo yon sèl, kote ou ale? Epi, koulye a se kote nou pral kòmanse wè ke sa a algorithm, menm si sou premye gade, santi l trè entelijan, gade sa a sou rive. Si ou te kapab etap pi devan. Ki kote nou vle mete Neil? Se konsa, evidamman isit la, Se konsa, kouman nou jwenn Neil a? Se pou yo fè sa etap-pa-etap. Gabe, kote ou bezwen ale? Oui, pou pran yon sèl gwo etap, oswa de mwatye etap sa yo fè yon sèl etap plis pase la. Grace, kote ou ale? Bon. Se konsa, yon lòt etap. E finalman, Branson? Yon lòt etap. Epi, koulye a nou ka mete Neil nan plas li. Se konsa, koulye a, kontinye sa a lojik. Menm si nou pa chanje Neil sou yo, ak sou, ak sou, yo mete l ' kote li ale, nan ka ki pi mal la, nan pwochen nimewo nou ta ka rankontre te kapab gen nimewo a, di, te gen yon nimewo zewo, Lè sa a, nou pral chanjman tout mesye sa yo. Sipoze ke gen yon nimewo, negatif yon sèl, Lè sa a, nou gen chanjman tout mesye sa yo. Se konsa, nou ap reyèlman jis kalite ranvèrsan pwoblèm nan alantou li, sa yo ke nou ap transfere depans lan soti nan la pwosesis seleksyon pou ensèsyon an pwosesis, tankou ke ou nèg jis te gen pou avanse pou pi apeprè n mwens yon bagay kantite etap. Epi ki kantite etap se sèlman pral ogmante jan mwen chwazi plis nimewo, si mwen gen kenbe bourade ou nèg tounen, ak tounen lakay ou, ak tounen lakay ou. Se konsa, bagay la tris kounye a se tout moun sa yo algoritm yo n okib. Se pou yo ale pi devan epi gras a sa yo mesye, ak visualized sa yo yon ti jan yon fason diferan. Trè byen fè. [Aplodisman] Tout dwa. Gen ou ale. Mèsi pou - BRANSON: [fèbl] kenbe nimewo yo. DAVID J. Malan: Non, ou ka kenbe nimewo yo kòm byen. Tout dwa. Joliman fè. Tout dwa. Se konsa, kite a wè si nou pa kapab kounye a rezime pi vit, ak plis ankò vizyèlman, ekzakteman ki sa jis rive isit la jan sa a. Mwen pral ale pi devan ak rale moute Firefox. Nou pral konekte sa a demonstrasyon sou sit entènèt kou a. Java se yon ti jan anmèdan jwenn travay nan kèk navigatè jou sa yo. Se konsa, si ou jwe ak sa a nan kay la, reyalize ou ta ka bezwen sèvi ak Firefox jwenn li ap travay. Ak sa ki mwen pral fè ak sa a demonstrasyon se sa ki annapre yo. Nan pati anba a, mwen gen yon pakèt antye nan meni opsyon, ki gen ladan yon kòmanse ak yon sispann bouton. Epitou, kòm yon sou kote, gen sanble gen yon ensèk nan pwogram sa yo, annakò ak ou pa kapab wè aktyèlman kòmanse nan oswa pou sispann bouton sof si ou kenbe lòd oswa Alt plis ak rale nan, ki kiryozite montre ou plis bouton ki sanble. Se konsa, jis Fyi si ou jwe ak sa a nan kay la. Koulye a, mwen pral klike sou kòmanse nan jis yon moman sa, apre yo fin ki espesifye yon reta nan, tankou, 200 milisgond isit la, jis pou nou ka wè sa ki rive. Se konsa, mwen reklamasyon ke sa a se yon vizyalizasyon nan algorithm nan premye mesye sa yo te fè, sòt ti wonn, kijan nou échanges moun pè-ki gen bon konprann. Insight nan kle sa a vizyalizasyon se ke wotè nan kenbe travès yo reprezante gwosè a nan nimewo a. Se konsa, pi wo a ba a, nan pi gwo nimewo a. Ki pi kout ba a, ki pi piti nimewo a. Men, si ou remake, nou ap ale atravè tout iteration an premye nan sa a algorithm, échanjé nimewo gwo ak piti, pou ke ti kantite moun ki vini anvan ak nimewo nan gwo ale nan bò dwat la. Lè nou jwenn nan fen etalaj nan nimewo anpil plis pase sèt, nou pwal ale tounen nan kòmansman an. Men, antisipe sa a. Sou bò gòch la byen lwen, ke nèg ti kras k ap pase swap bò lanmè a, ak sa a pwosesis repete. Koulye a, sa a vizyalizasyon byen vit vin raz, se konsa, kite m 'ale pi devan epi yo sispann li, chanje yon bagay nan reta anpil pi vit jis jwenn kounye a, yon santi yo pou sa a algorithm. Se konsa, menm si mwen te akselere l ', sa a se tankou amelyore processeur m 'yo, yo ap achte yon òdinatè nouvo. Mwen pa te fondamantalman chanje mwen algorithm, men ou ka tout bon wè plis byen klè pase ak moun, ki gwo a nimewo yo bouyònman moute sou tèt la, ak nimewo yo ti yo bouyònman desann nan pati anba nan. Epi, koulye a bagay sa a isit la klase. Men, kòm yon sou kote, nan kare yo, gen nan sèlman kèk Bookkeeping gen yo ede w konte konbyen konparezon, oswa ki jan anpil echanj gen aktyèlman te fè. Oke, kite la a eseye, youn nan lòt moun yo nou te wè. Kite m 'klike sou sòt ti wonn isit la, ak kite m 'chwazi, ak sa a paj entènèt tout se yon buggy ti kras. Se pou yo aksepte risk pou yo epi kouri l 'ankò. Gen nou ale. Se konsa, kite a fè sòt seleksyon an. Mwen pa konnen poukisa meni an parèt sou la. Se pou yo rale nan ranje ki ensèk, chanje sa a a 50. Ah, se pou yo aktyèlman fè ke anpil pi vit. Senk milisgond oswa konsa, epi yo kòmanse. Se konsa, sa a se sòt seleksyon an. Se konsa, ankò, panse osijè de ki sa nou te fè ak moun yo moute isit la. Nou te ale nan etalaj la ak chwazi eleman ki pi piti a ankò, ak ankò, li ankò. Koulye a, mwen reklamasyon ke te toujou trè move. Li te toujou n okib, bay oswa pran, men li te, nan mond lan reyèl, yon ti jan pi vit, paske mwen te tout bon pran yon ti kras mwens etap chak fwa. Men, nou ap sèlman ap pale ki sa? Petèt 40 oswa konsa ba isit la? Nou pa ap pale 40 milyon dola. Se konsa, li pa nan totalman klè m 'ke te depoze yon genyen enpòtan. Kite m 'tounen ladan l epi chanje nan nou an twazyèm algorithm, ki te chwazi sòt mete l lan. Epi, koulye a li vrèman buggy paske la meni reyèlman pa ta dwe desann a. Se konsa, kounye a nou ap woulo liv tounen moute isit la epi yo kòmanse sa a algorithm. Whoop, kòmanse epi yo sispann. Se konsa, sa a kalite youn nan gen yon modèl bèl nan li, kijan nou ap ankò yo mete moun yo, oswa nan ka sa a, travès yo an kote ki apwopriye yo. Epi li deja fè l 'anvan M 'vire. Men, yon sèl sa a, tou, nan teyori, se toujou n okib. Se konsa, kite a wè si nou pa ka rezime sa yo jan sa a. Mwen pral ale pi devan ak jis bay nou sòt de yon fason komen nan pale sou bagay sa yo, kite m 'prezante jis yon ti jan nan notasyon isit la. Ou se sou yo wè yon bagay yo rele gwo O, paske li se literalman yon gwo O. Lè sa a se yon fason ki yon òdinatè syantis oswa yon matematisyen menm sèvi ak a dekri tan an kouri nan kèk algorithm. Konbyen etap li aktyèlman pran? Koulye a, mwen pral anbarase tèt mwen ak ekriti m 'isit la nan jis moman sa a. Men, kite m 'ale pi devan epi di ke sa a pral gwo O sou isit la. Men, kite m 'prezante yon lòt senbòl, yon Omega kapital la. Omega a pwal opoze a, esansyèlman, nan gwo O. Lè nou konsidere ke gwo O vle di, nan ka ki pi mal la, ki kantite tan ta ka gen kèk algorithm pran, nan tèm de n, Omega ki pral dwe konbyen tan ka li pran nan ka a pi byen. Men, nou pral wè sa nou vle di pa pi bon ka nan jis moman sa a. Se konsa, kite la kòmanse yon bagay ki senp. Kite m 'kòmanse avèk yon rechèch lineyè. Se konsa, pa klasman. Nou pral rele sa rechèch lineyè. Epi, koulye a, fè yon ti kras tab soti nan sa a. Koulye a, nan ka a nan rechèch lineyè, nan ka ki pi mal la, konbyen etap la se li pral pran m 'yo jwenn yon nimewo nan chwa abitrè? Apre sa, nan n pòt total oswa n nimewo total. Pi move ka-a. Konbyen etap 'yo, mwen pral fè yo pran yo jwenn nimewo a 50 nan yon etalaj n pòt? Epi pou kisa? Paske li ta kapab la tout wout sou sou fen an. Se konsa, anpil tankou Jennifer rankontre, nan nimewo 50 te tout wout la sou, se konsa nan ka pi mal la rechèch la lineyè se gwo O n, nou pral di. Ki sa ki sou ka a pi bon, si ou jwenn vrèman chans? Li nan jis pral pran yon sèl etap, oswa yon nimewo konstan nan etap. Se konsa, nou pral dekri ke kòm 1. Se konsa, sa a se trè bon. Kounye a ki sa si nou te fè yon bagay renmen binè rechèch? Se konsa, binè rechèch la, nan pi move a ka, te pran konbyen tan? [Entèrpozisyon vwa] DAVID J. Malan: Se konsa, aktyèlman, mwen tande pawòl sa yo nan yon kote koup. Se konsa, li la aktyèlman ale n, bay oswa pran, paske kòm nou divize lis la nan mwatye ankò, epi ankò, epi ankò, nou kapab jwenn, finalman, valè a, si li nan la, men gen yon peche. Ki sa ki nan sipozisyon an ke nou gen pran pou yo akòde pou rechèch binè? Li te gen yo dwe klase. Li pa nan Ranje, ou ka divize bagay la nan mwatye ankò e ankò, epi ou ka ale kite, epi ou ka ale dwat li, li ou ka ale kite la ak dwa, men w ap pa pral jwenn eleman an si lis la pa klase, paske ou kapab rate li. Paske eristik ou a, pou ale bò gòch oswa dwa yo pral defekte si li nan tout bon pa klase. Se konsa, gen nan sòt de yon pri kache lè l sèvi avèk yon bagay tankou sa. Koulye a, kite a ale nan klasman nou an algoritm pa chache - oh, aktyèlman kite yo ale nan sa a vid. Rechèch binè nan ka a pi bon? Li la tou 1 si li jis k ap pase yo nan mitan la anpil nan etalaj la, oswa la nan mitan liv telefòn. Koulye a, kite a fè sòt ti wonn. Se konsa, ankò, kounye a nou ap antre nan la kalite, pa fouye yo. Nan ka ki pi mal la, konbyen etap te fè nou sòt ti wonn reklamasyon an pral pran? n Squared. Se konsa, mwen pral trase sa. Ooh, ekriti mwen sanble menm vin pi mal lè li projetée ki gwo. Tout dwa. Se konsa, ki la n okib. Men, nan ka ki pi bon an sòt ti wonn, konbyen etap se li pral pran? 1, mwen tande. Oratè 1: n. DAVID J. Malan: n, mwen tande. Oratè 1: 2. DAVID J. Malan: 2, mwen tande. Mwen tande 3? Tout dwa. Se konsa, mwen te konn tande 1, n, 2, men kite a chwazi apa omwen premye a nan tout sa yo sijesyon, 1. Li pa yon ensten move, paske li kalite sa a yon modèl isit la. Men, si li pran sèlman 1 etap, ki jan nan a mond te kapab mwen reklamasyon ke lis la se Klase, paske si mwen sèlman aksepte pran 1 etap, ki jan anpil eleman te kapab mwen aktyèlman tcheke yo dwe asire? Oke, jis 1, ki vle di gen nan n mwens 1 eleman ki ta ka soti nan lòd, epi mwen jis ale sou lafwa apre yo fin gade nan 1 eleman ki nan bagay se Klase. Se konsa, 1 pa nan korije isit la. Se konsa, minim, konbyen Mwen gen fè yon gade nan? [Entèrpozisyon vwa] DAVID J. Malan: n mwens 1, oswa reyèlman, n, paske mwen bezwen gade nan chak eleman a asire w ke li pa parèt nan lòd. Men, ankò, nou pral sòt nan vag nou an men nan nimewo telefòn yo ki pi piti ak asime ke, kòm n ap vin gwo, yo ap entérésan de tout fason. Se konsa, sa a, se sòt ti wonn. Epi, koulye a, se pou yo fè sa yo de sot pase yo. Sòt pou chwazi, ak Lè sa a, nou pral fè sòt mete l lan. Lè sa a, nou pral kònen ou lespri ak yon bagay anpil pi bon pase tout moun sa yo. Tout dwa. Ki sa ki se ka ki pi mal kouri tan nan sòt seleksyon? Oratè 4: n okib. DAVID J. Malan: n kare, mwen tande. Men, poukisa n okib, entwitif? Oratè 4: Paske nou jis te fè li. DAVID J. Malan: Paske nou jis te fè li. OK. Bon repons lan. Men, entwitif, poukisa se seleksyon sòt n okib? Ki sa ki t 'nou dwe fè ankò e ankò? Nou te gen kenbe analysis nan, yo ou pi piti a, se nan ou pi piti a yo, se ou ki pi piti a. Men, yo akòde, nou te kapab pran n etap, Lè sa a n, 1 mwens Lè sa a, n mwens 2. Men, si ou kalite ajoute sa yo tout leve, oswa pran l 'sou konfyans nan Bondye pou m' te ajoute yo moute nan avanse, nou jwenn apeprè n okib mwens kèk nimewo ki pi piti. Se konsa, mwen pral rele sa n okib. Men, avèk sòt seleksyon nan pi bon an ka, konbyen etap se li pral pran m 'konsa? Oratè 5: [fèbl] DAVID J. Malan: Se malerezman toujou n okib, dwa? Paske si mwen chwazi pi piti a eleman yo, epi nou te gen sèt moun isit la, Mwen konnen sèlman, yon fwa mwen jwenn yo trè a fen, ke mwen te jwenn pi piti a nimewo, tout kote li oswa li te kapab. Men, ki jan mwen jwenn pwochen an pi piti a kantite? Mwen gen fè yon lòt pas la. Se konsa, nan ka a pi bon, ki sa ki la D 'sòt seleksyon? Se yon lis sòt deja, nimewo yon sèl, nimewo de, nimewo twa, nimewo kat. Men, mwen se yon òdinatè. Mwen ka sèlman gade nan yon sèl bagay nan yon tan. Mwen pa ka sòt de pran yon etap tounen tankou yon moun ak di, Ooh, sa a sanble kòrèk. Mwen ka sèlman deside Correct nan sòt seleksyon pa chwazi a pi piti kantite. Men, menm si mwen jwenn nimewo yon premye, si mwen pa konnen nenpòt lòt bagay sou chif yo lòt, ki mwen pa fè sa, tout mwen konnen se mwen ve yo te tonbe nan men yon etalaj oswa yon seri nan pòt dèyè ki fè yo nimewo, wout la sèlman mwen konnen ke yon sèl te pi piti a? Si mwen jwenn tout wout la isit la ak reyalize, modi, yon sèl te depoze pi piti a. Men, ki jan mwen Lè sa a, detèmine ke de se pi piti a kap vini yo? Pa fè inefikasite nan menm ankò e ankò. Se konsa, finalman, ak sòt ensèsyon, ki jan, nan ka ki pi mal la, nou t ap di li fè? Li twò se n okib. Ak ki jan sou ak ka-a pi bon? Nou pral kite ke kòm yon cliffhanger. Nou pral ranpli nan tan sa a vid kap vini an, Men, kite m 'pwopoze ke nou fondamantalman fè pi bon pase tout moun sa yo, tout dwa? Se konsa, panse pou tèt ou ki sa ensèsyon sòt k ap pase yo dwe. Oke, sa ki te pa trè dramatik, paske mwen se youn nan sèlman ki te wè chanjman an. Wow. OK. Se konsa, isit la nou gen yon yon ti jan diferan demonstrasyon. Si m 'rale nan isit la, ou ap wè ke sou bò gòch la nou gen kalite ti wonn, nan la mitan nou gen sòt seleksyon, ak sou byen lwen dwa, nou gen yon bagay nou pa gen gade ankò rele rantre sòt. Men, konsidere ki sa nou ve yo te fè la a konsa byen lwen jodi a. Lè Jennifer premye li moute soti deyò sou sèn nan, nou te ale nan etalaj la nan nimewo ankò, li ankò, ak lineyè rechèch la, epi nou te resevwa lineyè tan kouri, gwo O n, se konsa pale. Lè nou kounye a konsidere premye semèn klas, lè nou te separe ak konkeri, epi nou te gen liv telefòn chire, ak Jennifer, epi nou tout ansanm exploitées ki kle insight, ki te repete tèt ou ankò e ankò pa yon jan kanmenm jete, voye ale, jete, mwatye nan pwoblèm nan, oswa jeneralman, divize yon pwoblèm nan mwatye, ak Lè sa a trete moso nan pi piti nan pwoblèm nan kòm concept ekivalan nan lòt la, nou yon jan kanmenm te fè fondamantalman pi byen. Men, avèk sòt ti wonn, ak seleksyon sòt, ak sòt ensèsyon, nou te kapab pa gen okenn Sur sa yo ki Jennifer te fè sa. Nou bèl anpil jis te mache retounen lakay yo epi fè yon pakèt tout de fwa, epi nou bagay sa yo tweaked yon ti jan, échanjé nan lòd sa a, petèt yo mete oswa chwazi. Men, nan fen jounen an, mwen te fè yon anpil nan gòch mache dèyè, yo soti. Nou pa t 'reyèlman yon bagay ogmante entelijan tankou Jennifer te fè tankou divize ak viktwa. Se konsa, rantre sòt, pa kontra, ki nou pa pral wè jouk semèn kap vini yo, li pral ogmante ke kle lide lè yo divize D 'a, ak Lè sa a, halving, ak Lè sa a, halving, ak Lè sa a, halving. Men, sou chak iteration nan ki bouk, klasman mwatye gòch li yo, ak dwa mwatye, Lè sa a, mwatye nan bò gòch nan mwatye gòch li yo, ak mwatye a dwa a goch la, Lè sa a, mwatye nan bò gòch nan mwatye nan dwa, ak mwatye a dwa a mwatye a dwat. Men, repete ankò e ankò. Se konsa, ou pral wè sa a vizyèlman, men sa a se sa ki ap tann nou semèn pwochèn nan. Men, an jeneral, lè nou panse yon ti kras ti jan pi rèd sou nenpòt pwoblèm ki sa yo. Nou te n okib sou bò gòch la, n okib nan mitan an, ak n ale n sou bò dwat la. Se konsa, gen nan cliffhanger reyèl ou. Nou pwal wè ou nan Lendi. [Aplodisman]