[Jwe mizik] DAVID Malan: Tout dwa. Tout dwa, akeyi tounen. Se konsa, sa a se Semèn 4, nan konmansman an ladan l ', ki deja. Men, ou pral sonje ke semèn pase a, nou mete Kòd sou kote pou jis yon ti epi nou kòmanse te kòmanse pale yon ti kras plis wo nivo, sou bagay sa yo tankou recherche ak klasman, ki menm si yon ti jan senp lide, yo reprezantan nan yon klas nan pwoblèm ou ap kòmanse rezoud patikilyèman jan ou kòmanse reflechi sou final pwojè ak solisyon ki enteresan ou ka gen yo pwoblèm reyèl lavi. Koulye a, kalite ti wonn se te youn nan pi senp la algoritm sa yo, epi li te travay pa gen nimewo sa yo ti nan yon lis oswa nan yon kalite etalaj de ti wonn nan fè wout yo moute sou tèt la, epi nimewo gwo deplase wout yo desann nan nan fen ke lis. Men, sonje ke nou te kapab visualized sòt ti wonn yon ti kras yon bagay tankou sa. Se konsa, kite m 'ale pi devan epi klike sou kòmanse. Mwen te predetèrmine sòt ti wonn. Men, si ou sonje ki ble a pi wo liy reprezante nonb gwo, ti liy ble reprezante nonb piti, kòm nou ale nan sa a ankò e ankò ak ankò, konpare de ba pwochen nan chak lòt nan wouj, nou pral swap la pi gwo ak pi piti a si yo parèt nan lòd. Se konsa, sa a pral ale sou epi ale sou yo ak sou ale sou li a, epi ou pral wè ke pi gwo a eleman yo ap fè wout yo nan la dwat, ak eleman yo ki pi piti yo fè wout yo sou bò goch la. Men, nou te kòmanse quantifier efikasite a, nan bon jan kalite nan sa a algorithm. Epi nou te di ke nan pi move a ka, sa a algorithm pran apeprè konbyen etap? Se konsa, n okib. Ak sa ki te n? ODYANS: Nimewo nan eleman. DAVID Malan: Se konsa, n te la nimewo nan eleman. Se konsa, nou pral fè sa souvan. Nenpòt ki lè nou vle pale sou gwosè a nan yon pwoblèm oswa gwosè a nan yon D ', oswa kantite lajan an nan tan li pran yo pwodwi pwodiksyon, nou pral jis jeneralize tou sa D 'a se kòm n. Se konsa, li tounen nan Semèn 0, nimewo a nan paj nan anyè telefòn lan te n. Kantite elèv nan chanm nan te n. Se konsa, isit la, tou, nou ap swiv ki modèl. Koulye a, n okib se pa patikilyèman vit, kidonk, nou te eseye fè pi byen. Se konsa, nou te gade yon koup la algoritm lòt, nan mitan ki yo te sòt seleksyon an. Se konsa, sòt seleksyon te yon ti kras diferan. Li te prèske ki pi senp, mwen bay gabèl di, kijan mwen te kòmanse nan kòmansman an lis volontè nou yo ak mwen jis ankò ak ankò e ankò mache ale nan tout lis la, arrache soti pi piti a eleman nan yon lè ak mete l 'oswa li nan kòmansman an nan lis la. Men, sa a, tou, yon fwa nou te kòmanse panse nan matematik la ak pi gwo foto, panse sou konbyen fwa Mwen te ale retounen ak lide ak tounen lakay ou ak lide, nou te di nan ka ki pi mal la, sòt seleksyon, tou, te ki sa? n Squared. Koulye a, nan mond reyèl la, li kapab yon aktyèlman ap très pi vit. Paske ankò, mwen pa t 'gen kenbe rmonte yon fwa mwen te klase nan pi piti a eleman. Men, si nou panse osijè de gwo anpil n, ak si ou sòt de fè soti matematik an kòm Mwen te fè sou tablo a, ak okib a n mwens yon bagay, tout lòt bagay san konte n okib, yon fwa n nan vin reyèlman gwo, pa fè sa reyèlman gen pwoblèm kòm anpil. Se konsa, kòm syantis konpitè, nou sòt de vire yon je avèg bay ki pi piti a faktè epi konsantre sèlman sou faktè a nan yon ekspresyon ki nan pral fè diferans nan pi gwo. Oke, alafen, nou te nan sòt mete l lan. Lè sa a te menm jan an nan lespri, men olye ke ale nan iterativman ak chwazi youn nan eleman pi piti nan yon tan, mwen olye pou pran men a ke mwen te fè fas, epi mwen deside yo, tout dwat, ou fè pati isit la. Apre sa, mwen te deplase sou eleman nan pwochen e te deside ke li oswa li ki te fè pati isit la. Lè sa a, mwen te deplase sou yo ak sou sou. Apre sa, mwen ta ka a, sou wout la, chanjman mesye sa yo nan lòd yo fè plas pou yo. Se konsa, sa ki te sòt de vè a mantal nan sòt seleksyon ke nou rele sòt mete l lan. Se konsa, sijè sa yo rive nan mond lan reyèl. Jis yon kèk ane de sa, lè yon sèten senatè te kouri pou prezidan, Eric Schmidt, nan moman an CEO nan Google, aktyèlman te gen opòtinite fè entèvyou l '. Men, nou te panse nou ta pataje sa a YouTube KLIP pou ou isit la, si nou te ka vire leve volim a. [Lèktur videyo] -Koulye a, Senatè, w ap isit la nan Google, ak mwen renmen panse a la prezidans kòm yon entèvyou travay. [Ri] -Koulye a, li difisil jwenn yon travay tankou yon prezidan. Lè w ap ale atravè tout rigoureux yo kounye a. Li la tou difisil jwenn yon travay nan Google. Nou gen kesyon ak nou mande kesyon kandida nou an. Lè sa a se yon sèl soti nan Larry Schwimmer. [Ri] -Ou mesye panse mwen plèzantri? Li nan dwa isit la. Ki sa ki se fason ki pi efikas sòt yon milyon dola nonm antye de-ti jan? [Ri] -Bon, uh - -I'm regrèt. Petèt nou ta dwe - -Non, non, pa gen okenn, pa gen okenn, pa gen. -Sa se pa yon - OK. -Mwen panse ke sòt nan ti wonn ta gen wout la sa ki mal yo ale. [Ri] [Bat bwavo ak aplodisman] -Vini non sou, ki moun ki te di l 'sa a? OK. [Lèktur videyo END] DAVID Malan: Se konsa, gen ou genyen li. Se konsa, nou te kòmanse quantifier sa yo kouri fwa, se konsa pale, ak yon bagay rele asenptotik notasyon, ki se jis refere li a sòt nou an vire yon je avèg bay moun ki faktè pi piti ak sèlman kap la nan moman kouri, pèfòmans la nan sa yo algoritm, kòm n ap vin vrèman gwo sou tan. Se konsa, nou prezante gwo O. ak gwo O reprezante yon bagay ke nou te panse nan kòm yon mare anwo kay la. Men, aktyèlman, Barry, nou ka pi ba pase MIC la yon ti jan? Nou te panse nan sa a se yon mare anwo kay la. Se konsa, gwo O n vle di okib ki nan ka ki pi mal, yon bagay tankou sòt seleksyon ta pran n etap okib. Oswa yon bagay tankou sòt ensèsyon ta etap n okib. Koulye a, pou yon bagay tankou ensèsyon sòt, sa ki te ka ki pi mal? Bay yon etalaj, sa ki nan pi move a posib senaryo ke ou ta ka jwenn tèt ou fè fas ak? Li nan konplètman bak, dwa? Paske si li nan konplètman bak, sa ou dwe fè yon anpil tout travay la. Paske si ou konplètman bak, w ap ale nan jwenn nan pi gwo eleman isit la, menm si li fè pati desann la. Se konsa, w ap ale nan di, tout dwa, nan moman sa a nan tan, ou fè pati isit la, konsa ou kite li pou kont li. Lè sa a, ou reyalize, o, modi, mwen gen deplase sa a eleman ti kras pi piti bò goch la nan ou. Lè sa a, mwen gen fè sa ankò ak ankò e ankò. Men, si mwen te mache dèyè, yo soti, ou ta sòt de santi pèfòmans nan ki algorithm, paske mwen toujou ap mélanger tout lòt moun desann nan la etalaj pou fè plas pou li. Se konsa, sa a, se ka ki pi mal. Nan kontras - ak sa a te yon cliffhanger dènye fwa - nou te di ke ensèsyon sòt te gen yon Omega nan ki sa? Ki sa ki nan kouri a pi bon-ka tan nan sòt ensèsyon? Se konsa, li la aktyèlman n. Sa ki te vid la ke nou kite sou tablo a dènye fwa. Lè li nan Omega n paske poukisa? Oke, nan ka a trè pi bon, sa ki nan sòt ensèsyon yo pral tonbe nan men? Oke, yon lis ki nan konplètman Ranje deja, minimòm travay fè. Men, sa ki nan pwòp sou sòt ensèsyon se pou sa paske li kòmanse isit la ak deside, o, ou se nimewo a yon sèl, ou fè pati isit la. Oh, ki sa yon fòtin bon. Ou se nimewo a de. Ou menm tou fè pati isit la. Nimewo twa, menm pi bon, ou genyen isit la. Le pli vit ke li vin nan fen a pseudocode lis, pou chak kalite ensèsyon an ke nou te mache nan tout vèbalman dènye fwa, li fè. Men, sòt seleksyon, pa kontra, kenbe fè sa? Kenbe ale atravè tout lis la ankò e ankò epi ankò. Paske insight nan kle te genyen sèlman yon fwa ou te gade tout wout la nan fen nan lis la nou ka fè sèten ki eleman ou chwazi a te tout bon eleman ki kounye a pi piti a. Se konsa, sa yo diferan mantal modèl fen moute ki bay kèk trè mond reyèl la diferans ki genyen pou nou, menm jan tou sa yo teyorik diferans ki genyen asenptotik. Se konsa, jis Rekapitilasyon, Lè sa a, gwo O n okib, nou te wè yon tankou kèk algoritm konsa byen lwen. Big O n? Ki sa ki nan yon algorithm ki te kapab dwe di ke yo dwe gwo O n? Nan ka ki pi mal la, li pran yon nimewo lineyè nan etap. OK, lineyè rechèch la. Men, nan ka ki pi mal la, kote se la eleman ou ap chèche pou lè k ap aplike lineyè rechèch? OK, nan ka ki pi mal la, li pa menm gen. Oswa nan ka, dezyèm lan pi mal la, li nan tout wout la nan fen a, ki se plis-or-mwens yon diferans yon sèl-etap. Se konsa, nan fen jounen an, nou ka di li se lineyè. Big O n ta dwe lineyè rechèch la, paske la nan ka ki pi mal, eleman pa menm gen oswa li nan tout wout la nan fen an. Oke, gwo O nan boutèy demi lit plen n. Nou pa t 'pale an detay sou gwo sa a, men nou te wè sa a anvan. Ki sa ki kouri nan sa yo rele logaritmik tan, nan ka ki pi mal? Yeah, se konsa binè rechèch la. Lè binè rechèch nan ka ki pi mal la ka gen eleman nan yon kote nan mitan an, oubyen yon kote andedan etalaj la. Men, ou sèlman jwenn li yon fwa ou divize lis la nan mwatye, nan mwatye, nan mwatye, nan mwatye. Lè sa a, vwala, li la a. Oswa ankò, pi move ka, li pa menm gen. Men, nou pa konnen ke li la pa gen jiskaske ou sòt de rive jwenn ki sot pase a anba-ki pi eleman pa halving ak halving ak halving. Big O nan 1. Se konsa, nou te kapab gwo O nan 2, gwo O nan 3. Nenpòt ki lè ou vle jis yon nimewo konstan, nou jis sòt de jis senplifye ke kòm gwo O nan 1. Menm si si pli reyèlman, li pran 2 oswa menm 100 etap, si li nan yon konstan kantite etap, nou jis di gwo O nan 1. Ki sa ki nan yon algorithm sa a, se nan gwo O la nan 1? ODYANS: Jwenn longè nan yon varyab. DAVID Malan: Jwenn la longè yon varyab? ODYANS: Non, longè a si li la deja klase. DAVID Malan: Bon. OK, se konsa jwenn longè a nan yon bagay si longè a nan ke yon bagay, tankou yon etalaj, se ki estoke nan kèk varyab. Paske ou ka jis li varyab la, oswa enprime varyab la, oswa jis jeneralman gen aksè a varyab sa a. Epi vwala, ki pran tan konstan. Nan kontras, panse tounen nan grate. Panse tounen nan premye semèn C, rele jis printf ak enprime yon bagay sou ekran an se joui tan konstan, paske li jis pran kèk nimewo nan sik CPU yo montre tèks sa a sou ekran an. Oswa rete tann - fè li? Ki jan lòt bagay yo ka nou modèl la pèfòmans nan printf? Èske yon moun renmen dakò, ki petèt se pa moman vrèman konstan? Nan ki sans ta ka printf ap kouri tan sa a, aktyèlman enprime yon kòd sou ekran an, gen yon bagay lòt pase konstan. ODYANS: [fèbl]. DAVID Malan: Yeah. Se konsa, li depann sou pèspektiv nou yo. Si nou aktyèlman panse a D 'a printf tankou se te fisèl la, ak Se poutèt sa nou mezire gwosè a nan ki D 'pa longè li yo - se konsa kite a rele ki longè n kòm byen - joui, printf se tèt li gwo O n paske li pral pran ou n etap ekri ak lèt ​​detache soti chak nan sa yo n karaktè, gen plis chans. Omwen nan limit ki nou sipoze ke petèt li a lè l sèvi avèk yon pou bouk anba kapo a. Men, nou ta gen fè yon gade nan ki Kòd konprann li pi byen. Ak tout bon, yon fwa ou mesye kòmanse analize algoritm pwòp ou a, ou pral literalman fè sèlman sa. Sòt de grenn je Kòd ou ak panse sou - tout dwa, mwen gen sa a bouk isit la oswa mwen gen yon pasan enbrike isit la, ki nan pral fè n bagay sa yo n fwa, epi ou ka sòt de rezon ki fè wout ou nan kòd la, menm si li nan pseudocode epi yo pa Kòd vrè. Se konsa, sa ki sou Omega nan okib n? Ki sa ki te yon algorithm ki nan pi bon an ka, toujou te pran n etap okib? Yeah? ODYANS: [fèbl]. DAVID Malan: Se konsa, sòt seleksyon an. Paske nan ke pwoblèm reyèlman redwi nan lefèt ke ankò, mwen pa konnen Mwen te jwenn pi piti a kounye a jouk Mwen te tcheke tout eleman ki reprize. Se konsa, Omega nan, di, n, nou jis te vini ak yon sèl. Sòt mete l lan. Si lis la k ap pase yo dwe klase deja, nan ka ki pi bon nou jis gen fè yon sèl pase nan li, nan ki pwen nou ap asire w. Lè sa a, ki te kapab di yo dwe lineyè, pou asire w. Ki sa ki sou Omega nan 1? Ki sa ki, nan ka ki pi bon, ta ka pran yon nimewo konstan nan etap? Se konsa, lineyè rechèch la, si ou jis jwenn chans ak eleman ki w ap chèche se dwa nan kòmansman an nan lis la, si sa a, se ki kote ou kòmanse ou lineyè parcourt nan ki lis. Lè sa a se vre nan yon nimewo de bagay sa yo. Pou egzanp, menm binè rechèch la se Omega nan 1. Paske sa ki si ou jwenn vrèman reprize chans ak santi'w-DAB nan mitan an nan etalaj ou se nimewo a w ap chèche? Se konsa, ou kapab jwenn chans la, kòm byen. Sa a yon sèl, alafen, Omega n boutèy demi lit n. Se konsa, n boutèy demi lit n, nou pa t 'reyèlman pale sou ankò, men - ODYANS: Merge sòt? DAVID Malan: fizyon sòt. Sa ki te cliffhanger a nan tan pase a, kote nou pwopoze, epi nou te montre vizyèlman, ke gen algoritm. Men, rantre sòt de sèlman yon sèl sa yo algorithm ki se fondamantalman pi vit pase kèk nan mesye sa yo ak lòt. An reyalite, fizyone kout se pa sèlman nan la pi bon ka n n boutèy demi lit, nan pi move a ka n n louvri sesyon. Men, lè ou gen sa a konyensidans nan Omega ak gwo O ke yo te menm bagay la? Nou ka aktyèlman dekri ke kòm sa ki nan rele Theta, menm si li nan yon ti kras mwens komen. Men, ki jis vle di limit yo de, nan ka sa a, se menm bagay la. Se konsa, rantre sòt, ki sa ki sa a reyèlman bouyi desann nan pou nou? Oke, sonje motivasyon an. Kite m 'rale moute yon lòt animasyon ki nou pa t 'gade nan tan pase. Sa a yon sèl, lide menm, men li nan yon ti kras pi gwo. Men, mwen pral ale pi devan epi pwen soti premye - nou gen sòt ensèsyon sou bò gòch nan tèt, Lè sa a sòt seleksyon an, sòt ti wonn, yon koup nan kalite lòt - koki ak rapid - ke nou pa te pale sou, ak pil ak rantre sòt. Se konsa, omwen eseye konsantre je ou sou tèt la twa sou bò gòch la ak Lè sa a, rantre sòt lè m 'klike sou sa a flèch vèt. Men, mwen pral kite tout nan yo kouri, jis ba ou yon sans de divèsite nan algoritm ki egziste nan mond lan. Mwen pral kite sa kouri pou jis yon kèk segond. Men, si ou konsantre je ou - chwazi yon algorithm, yo konsantre sou li pou jis yon segonn - ou pral kòmanse wè nan modèl ke li nan mete ann aplikasyon. Se rantre sòt, avi, fè. Sòt pil wòch, rapid sòt, koki - se konsa li sanble nou prezante twa a pi mal la algoritm semèn pase a. Men, sa a bon pou nou isit la jodi a gade nan sòt fizyone, ki se youn nan yo menm ki pi fasil la se fè yon gade nan, menm menm si li pwobableman ap pliye tèt ou jis yon ti kras. Isit la nou kapab wè jis ki jan anpil sòt seleksyon absorb. Men, sou bò la baskile, li nan reyèlman fasil a aplike. E petèt pou Set P 3, ki nan youn nan la algoritm ou te chwazi aplike pou edisyon a estanda. Parfe amann, parfe kòrèk. Men, ankò, kòm n ap vin gwo, si ou chwazi aplike yon algorithm pi vit renmen rantre sòt, chans yo nan pi gwo ak pi gwo entrain, kòd ou se jis pral kouri pi vit. Sit entènèt ou a ale nan travay pi byen. Itilizatè ou yo pral fè pi kontan. Se konsa, gen efè sa yo nan aktyèlman bay nou kèk pi fon te panse. Se konsa, kite a pran yon gade nan sa ki rantre sòt se aktyèlman tout sou yo. Bagay la fre se ke rantre sòt se jis sa a. Sa a se, ankò, sa nou te rele pseudocode, pseudocode ke yo te Angle ki tankou sentaks. Ak senplisite la se sòt de kaptivan. Se konsa, sou opinyon n eleman - se konsa ke jis vle di, isit la nan yon etalaj. Li nan te resevwa bagay sa yo n nan li. Sa a tout nou ap di a. Si n gen mwens pase 2, retounen. Se konsa, sa se sèlman ka a trivial. Si n gen mwens pase 2, Lè sa a, evidamman li nan 1 oswa 0, nan ka sa a bagay la se deja klase oswa inègzistan, Se konsa, jis retounen. Pa gen anyen fè. Se konsa, sa a, se yon ka senp yo rache la. Lòt Bagay, nou gen twa etap. Sòt mwatye nan bò gòch nan eleman yo, sòt mwatye nan dwa nan eleman yo, ak Lè sa a rantre mwatye yo Ranje. Ki sa ki nan enteresan isit la se ke Mwen se kalite punting, dwa? Genyen kalite yon definisyon sikilè sa a algorithm. Nan ki sans sa a nan algorithm sikilè definisyon? ODYANS: [fèbl]. DAVID Malan: Yeah, algorithm klasman m 'yo, de nan etap li yo "sòt yon bagay. "Se konsa, ki amèn la kesyon, byen, sa ki mwen pral sèvi ak sòt mwatye nan bò gòch ak mwatye nan dwa? Ak bote a isit la se ke menm si ankò, sa a se lide-koube nan pati ki kapab, ou ka itilize menm algorithm sòt mwatye gòch la. Men, tann yon minit. Lè w ap di sòt nan bò gòch mwatye, ki de a etap yo pral vini yo? Nou pral sòt mwatye gòch la bò gòch mwatye ak dwa mwatye nan mwatye gòch la. Modi, ki jan mwen sòt sa yo de mwatye, oswa trimès, kounye a? Men, sa a OK. Nou gen yon algorithm klasman isit la. Men, menm si ou ta ka enkyete nan premye sa a se kalite yon enfini bouk, li nan yon sik ki pa janm ale nan fini - li ki pral fini yon fwa sa k ap pase? Yon fwa n se mwens pase 2. Ki evantyèlman ki pral rive, paske si ou kenbe halving ak halving nan halving sa yo mwatye, siman evantyèlman w ap ale nan fen moute ak jis 1 oswa 0 eleman. Nan ki pwen, sa a algorithm di w ap fè. Se konsa, majik a reyèl nan sa a algorithm sanble ap nan ki etap final la, fusion. Sa lide ki senp jis fusion de bagay sa yo, se sa ki nan finalman pral yo ki pèmèt nou sòt yon etalaj de, kite a di, uit eleman. Se konsa, mwen gen uit plis voye boul estrès moute isit la, yuit moso papye yo, ak yon Google Vit - ki pou mwen jwenn kenbe. [Ri] DAVID Malan: Si nou te ka pran uit volontè, e kite yo wè si nou kapab jwe sa a soti, sa. Wow, OK. Syans enfòmatik ap resevwa plezi. Tout dwa. Se konsa, kouman sou ou twa, pi gwo men moute a. Kat nan do an. Ak ki jan sou, n ap fè ou twa nan ranje sa a? Men, kat la devan la. Se konsa, ou uit, tonbe sou yo. [Ri] DAVID Malan: mwen se aktyèlman pa sèten sa li ye. Èske li voye boul yo estrès? Ti lanp yo biwo? Materyèl la? Entènèt la? OK. Se konsa, vini sou yo. Ki moun ki ta renmen - kenbe vini. Ann wè. Lè sa a mete ou nan kote - w ap nan kote yon sèl. Uh-oh, rete tann yon minit. 1, 2, 3, 4, 5, 6, 7 - oh, bon. Tout dwa, nou bon. Tout dwa, se konsa tout moun gen yon chèz, men se pa sou glas la Google. Se pou m 'keu sa yo moute. Ki sa ki nan non ou? MICHELLE: Michelle. DAVID Malan: Michelle? Tout dwa, ou jwenn yo gade tankou geek a, si ke se ok. Bon, mwen fè tou, Mwen ta kwè, sèlman pou moman yon. Tout dwa, ki sibstiti an. Nou te ap eseye vini ak yon sèvi ak ka pou Google Glass, epi nou te panse li ta plezi jis fè sa a. lè moun yo Sur Nou pral anrejistre mond lan nan pèspektiv yo. Tout dwa. Pa pwobableman Google ki gen entansyon. Tout dwa, si ou pa lide pote sa a pou minit kap vini yo gòch, ki ta ka bèl bagay. Tout dwa, se konsa nou gen isit la yon etalaj de eleman, e ke sa etalaj, tankou pou chak nan moso papye nan sa yo jan ' men, se kounye a triye. MICHELLE: O, sa a, se konsa etranj. DAVID Malan: Li nan bèl anpil o aza. Ak nan jis moman sa a, nou pral eseye aplike rantre sòt ansanm epi wè ki kote ki insight kle a se. Men, jwe fent la isit la ak sòt plonje se yon bagay ki nou pa gen sipoze ankò. Nou aktyèlman bezwen kèk plis espas. Se konsa, sa k ap pase yo dwe patikilyèman enteresan sou sa a se ke sa yo mesye yo ale pou avanse pou pi alantou yon ti kras ti jan, paske mwen pral asime ke gen nan yon etalaj siplemantè nan espas, di, dwa dèyè yo. Se konsa, si yo ap dèyè chèz yo, sa a, se etalaj la segondè. Si yo ap chita isit la, sa a, se etalaj nan prensipal. Men, sa a se yon resous ke nou gen pa exploitées konsa byen lwen ak ti wonn sòt, ak sòt seleksyon an, ak sòt mete l lan. Sonje semèn pase a, tout moun jis kalite shuffled an plas. Yo pa t 'sèvi ak nenpòt memwa adisyonèl. Nou te fè plas pou moun ki pa k ap deplase moun alantou. Se konsa, sa a se yon insight kle, tou. Genyen komès sa a-off, an jeneral nan syans òdinatè, nan resous. Si ou vle pi vit yon bagay tankou tan, w ap ale nan gen yo peye yon pri. Ak youn nan moun ki pri a se trè souvan espas, kantite lajan an nan memwa oswa difisil espas ki gen kapasite ke w ap lè l sèvi avèk. Oswa, franchman, kantite lajan an nan tan pwogramè. Konbyen tan li pran ou, moun lan, ki aktyèlman aplike kèk plis konplike algorithm. Men, pou jounen jodi a, komès-off la se tan ak espas. Se konsa, si ou nèg te kapab jis kenbe ou nimewo pou nou ka wè ke w ap tout bon matche 4, 2, 6, 1, 3, 7, 8. Ekselan. Se konsa, mwen pral pou yo eseye enstrumante bagay sa yo, si ou nèg ka jis swiv plon m 'isit la. Se konsa, mwen pral aplike, an premye, an premye etap nan pseudocode a, ki se sou opinyon n eleman, si n se mwens pase 2, lè sa a retounen. Li evidan, ki fè sa ki pa aplike, pou nou deplase sou. Se konsa, sòt mwatye nan bò gòch nan eleman yo. Se konsa, sa vle di mwen pral konsantre mwen atansyon sèlman pou moman yon sou sa yo kat mesye isit la. Tout dwa, ki sa mwen pwochen fè? ODYANS: sòt mwatye gòch la. DAVID Malan: Se konsa, koulye a, mwen gen sòt mwatye nan bò gòch nan mesye sa yo. Paske ankò, sipoze nan tèt ou a objektif la se sòt mwatye gòch la. Ki jan ou fè fè sa? Jis swiv enstriksyon yo, menm si nou ap fè l 'ankò. Se konsa, sòt mwatye gòch la. Koulye a, mwen klasman mesye sa yo de. Ki sa ki vini kap vini yo? ODYANS: sòt mwatye gòch la. DAVID Malan: sòt mwatye gòch la. Se konsa, kounye a sa yo, sa a plas isit la, a se yon lis ki gen yon gwosè 1. Ak sa ki nan non ou ankò? PRINCESS DAISY: Princess Daisy. DAVID Malan: Princess Daisy se isit la. Se konsa, li se deja klase, paske lis la se nan gwosè 1. Ki sa mwen pwochen fè? OK, retounen, paske ke lis se nan gwosè 1, ki se mwens pase 2. Lè sa a, sa ki nan pwochen etap la? Epi, koulye a ou gen kalite rvnir nan tèt ou. Sòt mwatye nan dwa, ki se - sa ki nan non ou? LINDA: Linda. DAVID Malan: Linda. Se konsa, sa nou fè kounye a ke nou gen yon lis ki gen yon gwosè 1? ODYANS: Retounen. DAVID Malan: atansyon. Nou retounen an premye, e kounye a, twazyèm lan etap - epi si mwen kalite dekri li pa anbrase chèz sa yo de kounye a, koulye a, mwen gen fizyone eleman sa yo de. Se konsa, koulye malerezman, eleman yo yo soti nan lòd. Men, sa a kote pwosesis la fusion kòmanse jwenn konvenkan. Se konsa, si ou nèg te kapab leve kanpe pou jis yon moman, mwen pral bezwen ou, nan yon moman, nan etap dèyè chèz ou. Men, si Linda, paske 2 a se pi piti pase 4, poukisa pa fè sa ou vini alantou an premye? Rete la. Se konsa, Linda, ou vin bò kote premye. Koulye a, an reyalite, si li nan jis yon etalaj nou te ka jis deplase li nan tan reyèl sa a soti nan chèz sa a plas. Se konsa, imajine ke te pran kèk konstan kantite etap 1. Epi, koulye a - men nou bezwen mete ou nan kote nan premye isit la. Epi, koulye a si ou te kapab vini alantou li, kòm byen, nou pral dwe nan kote de. Men, menm si sa a santi l tankou li nan pran yon ti tan, sa ki nan bèl kounye a se ke mwatye gòch la ki rete mwatye kounye a klase. Se konsa, sa ki te pwochen etap la, si nou kounye a remonte pli lwen nan istwa a? ODYANS: Dwa mwatye. DAVID Malan: sòt mwatye a dwat. Se konsa, ou nèg dwe fè sa a, menm jan tou. Se konsa, si ou ta ka leve kanpe sèlman pou moman yon? Ak sa ki nan non ou? Jess: Jess. DAVID Malan: Jess. OK, se konsa Jess se kounye a bò gòch la mwatye nan mwatye a dwat. Se konsa, li la yon lis ki gen yon gwosè 1. Li nan evidamman Ranje. Men, non ou ankò? MICHELLE: Michelle. DAVID Malan: Michelle se evidamman yon lis ki gen yon gwosè 1. Li nan deja klase. Se konsa, kounye a majik la rive, pwosesis la fusion. Se konsa, ki moun ki k ap pase vin an premye? Li evidan Michelle. Se konsa, si ou te kapab vini alantou tounen. Espas nan nou gen ki disponib pou l 'koulye a se dwa dèyè sa a chèz isit la. Epi, koulye a si ou te ka tounen vin jwenn kòm byen, nou genyen kounye a, yo dwe klè, de mwatye, chak nan gwosè 2 - ak jis pou dedomajman pou reprezantasyon nan, si ou te kapab fè yon ti kras nan yon espas - yon sèl kite mwatye isit la, yon sèl dwa mwatye isit la. Remonte pli lwen nan istwa a. Ki sa ki etap se kap vini yo? ODYANS: Merge. DAVID Malan: Se konsa, kounye a nou gen nan amalgame. Se konsa, OK, se konsa, koulye a, Erezman, nou jis libere moute kat chèz. Se konsa, nou te itilize de fwa tankou memwa anpil, men nou ka bay baskile-flopping ant ranje yo de. Se konsa, Ki nonb ki se vini an premye? Se konsa, Michelle, evidamman. Se konsa, vin bò kote yo epi pran chèz ou isit la. Lè sa a, nimewo 2 a se evidamman kap vini an, konsa ou vin isit la. Nimewo 4, nimewo 6. Li di ankò, menm si gen yon ti kras ti jan nan mache patisipe, reyèlman, sa yo te ka rive imedyatman, pa deplase yon sèl - OK, byen te jwe. [Ri] DAVID Malan: Koulye a, nou ap nan fòm trè bon. Mwatye nan bò gòch nan tout la D 'gen kounye a te klase. Tout dwa, se konsa mesye sa yo te gen avantaj nan mwen - ki jan li te fini tout ti fi yo sou la kite ak tout ti gason yo sou bò dwat la? OK, se konsa mesye 'pral fè koulye a. Se konsa, mwen pa pral mache ou atravè etap sa yo. Nou pwal wè si nou ka re-aplike pseudocode a menm. Si ou vle ale pi devan epi leve kanpe, epi ou mesye, kite m 'ba ou MIC la. Gade wè si ou pa kapab repwodui sa ki nou jis te fè isit la sou la lòt fen nan lis la. Ki moun ki bezwen pale an premye, ki baze sou algorithm a? Se konsa, eksplike ki sa ou ap fè anvan ou fè nenpòt mouvman pye. Oratè 1: Tout dwa, se konsa depi Se mwen menm ki mwatye nan gòch la bò gòch mwatye, mwen retounen. Dwa? DAVID Malan: Bon. Oratè 1: Lè sa a, - DAVID Malan: Ki moun ki fè sa ki MIC la ale nan kap vini yo? Oratè 1: Next nimewo. Oratè 2: Se konsa, mwen se mwatye nan dwa nan mwatye a gòch la bò gòch mwatye, ak mwen retounen. DAVID Malan: Bon. Ou retounen. Se konsa, kounye a sa ki nan moute nan pwochen pou ou de? Oratè 2: Nou vle wè ki moun ki nan pi piti. DAVID Malan: Egzakteman. Nou vle rantre. Espas nan nou pral pou itilize pou rantre nou antre nan, menm si yo ap evidamman Ranje deja, nou pral yo swiv algorithm a menm. Se konsa, ki moun ki ale nan do an premye? Se konsa, 3, ak Lè sa a, 7. Epi, koulye a MIC la ale mesye sa yo, OK? Oratè 3: Se konsa, mwen se mwatye a dwa a nan mwatye gòch li yo, ak n mwen an se mwens pase 1, se konsa mwen jis ale nan pase - DAVID Malan: Bon. Oratè 4: mwen se mwatye a dwa a nan dwa mwatye nan mwatye ki dwat la, ak mwen se tou yon moun, se konsa mwen ale nan retounen. Se konsa, kounye a nou rantre. Oratè 3: Se konsa, nou tounen. DAVID Malan: Se konsa, ou ale nan do an. Se konsa, 5 ale an premye, lè sa a 8. Epi, koulye a odyans lan, ki se nan etap nou dwe kounye a remonte Retounen nan nan lespri nou? ODYANS: Merge. DAVID Malan: Machin rantre nan mwatye kite la ak dwa mwatye nan mwatye a orijinal la bò gòch. Se konsa, kounye a - ak jis fè sa-a klè, fè yon ti kras nan espas ant ou menm de nèg. Se konsa, koulye sa a, se lis yo de, kite ak dwa. Se konsa, kouman nou koulye a rantre ou nèg nan ranje devan an nan plas ankò? 3 ale an premye. Lè sa a, 5, evidamman. Lè sa a, 7, e kounye a, 8. OK, epi kounye a nou ye? ODYANS: Pa fè. DAVID Malan: Pa fè, paske evidamman, gen nan yon sèl etap chape. Men, ankò, rezon ki fè yo mwen lè l sèvi avèk sa a jagon tankou "nan tèt ou remonte," li nan paske sa ki nan vrèman sa kap pase. Nou pral nan tout nan etap sa yo, men nou ap sòt de poz pou yon moman, plonje pi fon nan la algorithm, poz pou yon moman, plonje pi fon nan algorithm a, ak kounye a nou gen sòt nan remonte nan nou an lespri ak defèt tout moun sa yo kouch ke nou te sòt de mete sou kenbe. Se konsa, kounye a nou gen de lis nan gwosè 4. Si ou mesye t 'ka rete moute yon dènye fwa epi fè yon ti jan nan espas isit la yo fè klè ke sa a se bò gòch la mwatye nan a orijinal la, dwa mwatye nan orijinal la. Ki moun ki nan nimewo nan premye ke nou bezwen rale nan do a? Michelle, nan kou. Se konsa, nou mete Michelle isit la. Men, moun ki gen nimewo 2? Nimewo 2 vini sou do yo tou. Nimewo 3? Ekselan. Nimewo 4, nimewo 5, nimewo 6, nimewo 7, ak nimewo 8. OK, se konsa li te santi tankou yon anpil nan etap sa, pou asire w. Men koulye a, se pou yo wè si nou pa ka konfime sòt de entwitif ke sa a algorithm fondamantalman, patikilyèman kòm n vin reyèlman gwo, jan nou te wè ak Animations yo, se fondamantalman pi vit. Se konsa, mwen fè reklamasyon sa a algorithm, nan pi move a ka yo epi menm nan ka a pi byen, se gwo O n fwa boutèy demi lit n. Sa se, gen kèk aspè de sa a algorithm ki pran n etap, men gen nan yon lòt aspè yon kote nan ki iteration, ki loupin, ki pran boutèy demi lit etap n. Èske nou ka mete dwèt nou sou sa ki sa yo de nonb yo refere li a? Oke, kote - where'd MIC la ale? Oratè 1: Èske ouvri sesyon an n ap kraze nou moute nan de - divize pa de, esansyèlman. DAVID Malan: Egzakteman. Nenpòt ki lè nou wè nan nenpòt algorithm konsa byen lwen, gen a te modèl sa a nan divize, divize, divize. Men, li la anjeneral redwi nan yon bagay ki nan logaritmik, boutèy demi lit baz 2. Men, li te kapab vrèman gen anyen, men louvri sesyon baz 2. Koulye a, sa ki sou n an? Mwen ka wè ke nou kalite divize ou mesye - divize nou la a, divize nou la a, divize nou la a, divize ou. Ki kote fen a soti? Se konsa, li fusion la. Paske panse sou sa. Lè wap rantre uit moun ansanm, kijan mwatye nan yo se yon seri kat epi lòt mwatye a yo se yon lòt mete nan kat, ki jan ou ale sou fè fusion a? Oke, ou nèg te fè li san patipri entwitif. Men, si mwen olye pou te fè l 'yon ti kras plis metodikman, mwen ka gen pwente nan moun nan leftmost premye ak gòch mwen men, pwente nan moun nan leftmost nan ke mwatye ak men dwat mwen an, ak jis imedyatman te mache nan tout la lis, montre nan eleman ki pi piti a chak fwa, k ap deplase dwèt mwen sou yo ak sou jan sa nesesè pandan tout lis la. Men, sa ki nan kle sou sa a fusion pwosesis ki se mwen konpare sa yo pè nan eleman. Soti nan mwatye nan dwa ak soti nan bò gòch la mwatye, mwen pa janm ap yon fwa rmonte. Se konsa, plonje nan tèt li ap pran pa plis pase n etap. Men, konbyen fwa te fè mwen gen fè sa fusion? Oke, pa gen plis pase n yo, epi nou jis wè ak plonje final la. Se konsa, si ou fè yon bagay ki pran ale etap n n fwa, oswa vis vèrsa, li pral ban nou n fwa boutèy demi lit n. Epi poukisa se sa a pi byen? Oke, si nou deja konnen ke boutèy demi lit n se pi bon pase n - dwa? Nou te wè nan rechèch binè, liv telefòn egzanp, n louvri sesyon te definitivman pi bon pase lineyè. Se konsa, sa vle di n fwa n louvri sesyon an se definitivman pi bon pase n fwa yon lòt n, AKA n okib. Epi sa a, ki sa nou finalman santi w. Se konsa, gwo wonn nan aplodisman, si nou te kapab, pou mesye sa yo. [Aplodisman] DAVID Malan: ak kado louvri ou - ou ka kenbe nimewo yo, si ou ta renmen. Men, kado louvri ou a, kòm dabitid. Oh, e nou ap voye ba ou pye a, Michelle. Mèsi poutèt ou. Tout dwa. Ede tèt ou nan yon boul estrès. Men, kite m 'rale moute, nan Antretan la, nou zanmi Rob Bowden yo ofri yon ti jan diferan pèspektiv sou sa a, depi ou ka panse sou sa yo etap k ap pase nan yon yon ti jan diferan fason. An reyalite, mete-up la pou sa Rob a sou yo montre nou sipoze ke nou te deja fè divize moute nan la gwo lis nan uit lis piti, chak nan gwosè 1. Se konsa, nou ap chanje pseudocode nan yon ti kras ti jan jis sòt nan jwenn nan la lide debaz sou fason fusion nan travay. Men, tan an kouri nan sa ki li a sou fè se toujou yo pral menm bagay la. Li di ankò: mete-up a isit la se ke li se kòmanse ak uit li bay lis gwosè 1. Se konsa, ou te rate pati a ki kote li se aktyèlman fè n nan boutèy demi lit, boutèy demi lit n, boutèy demi lit n divize nan opinyon an. [Lèktur videyo] -Sa a li pou etap youn. Pou etap de, repete rantre pè lis. DAVID Malan: Hm. Se sèlman odyo ap vini soti nan òdinatè mwen an. Ann eseye sa a ankò. -Jis abitrèman chwazi ki - kounye a nou gen kat lis. Aprann anvan. DAVID Malan: Gen nou ale. -Machin rantre nan 108 ak 15, nou fini moute ak nan lis 15, 108. Machin rantre nan 50 ak 4, nou fini ak 4 50,. Machin rantre nan 8 ak 42, nou fini ak 8, 42. Men, fusion 23 ak 16, nou fini ak 16, 23. Koulye a, tout lis nou yo nan gwosè 2. Remake chak nan la kat lis ki klase. Se konsa, nou ka kòmanse fusion pè lis ankò. Machin rantre nan 15 ak 108 ak 4 ak 50, nou premye pran 4 a, Lè sa a, 15 an, Lè sa a, 50 an, Lè sa a, 108 la. Machin rantre nan 8, 42 ak 16, 23, nou premye pran 8 la, Lè sa a, 16 an, Lè sa a, 23 an, Lè sa a, 42 la. Se konsa, kounye a nou gen jis de lis nan gwosè 4, chak nan yo ki se Klase. Se konsa, kounye a nou rantre sa yo li bay lis de. Premyèman, nou pran 4 a, Lè sa a, nou pran an 8, Lè sa a, nou pran 15 an, Lè sa a, 16, Lè sa a, 23, Lè sa a, 42, Lè sa a, 50, Lè sa a, 108. [Lèktur videyo END] DAVID Malan: Yon fwa ankò, avi, li pa janm manyen yon tas yo bay plis pase yon sèl fwa apre avanse pi lwen pase li. Se konsa, li pa janm la repete. Se konsa, li te toujou deplase bò lanmè a, e ke sa a kote nou te resevwa n nou an. Poukisa nou pa kite m 'rale moute yon sèl animasyon ke nou te wè pi bonè, men fwa sa a konsantre sèlman sou kalite plonje. Kite m 'ale pi devan epi rale nan sa a sou isit la. Premye kite m 'chwazi yon D' o-aza, gwosi sa a, epi ou ka sòt de wè ki sa nou te pran pou yo akòde, pi bonè, rantre sòt se aktyèlman fè. Se konsa, remake ke ou jwenn sa yo mwatye oswa sa yo ka oswa sa yo uityèm nan la pwoblèm ki tout nan yon toudenkou kòmanse pran bon fòm. Lè sa a, finalman, ou wè nan fen anpil ki bam, tout bagay se fizyone ansanm. Se konsa, sa yo, se jis twa diferan pran sou lide a menm. Men, insight nan kle, jis tankou divize ak konkeri nan klas la trè premye, te ke nou deside yon jan kanmenm divize pwoblèm nan nan yon bagay gwo, nan sòt yon bagay nan idantik nan Lespri Bondye, men ki pi piti ak pi piti ak pi piti ak pi piti. Koulye a, yon lòt fason plezi yo sòt de panse sou sa yo, menm si li pa pral ba ou entwisyon an menm konprann, se animasyon ki anba la a. Se konsa, sa a se yon yon moun videyo mete tèt yo ansanm ki asosye diferan son ak operasyon yo divès kalite pou sòt ensèsyon, pou plonje sòt, ak pou yon koup nan lòt moun. Se konsa, nan yon moman, mwen pral frape Jwe. Se sou yon minit nan longè. Men, menm si ou ka toujou wè nan modèl k ap pase, fwa sa a ou kapab tou tande ki jan sa yo algoritm yo fè yon fason diferan ak yon ti jan diferan modèl. Sa a se sòt mete l lan. [Ton JWE] DAVID Malan: Li ankò ap eseye insert chak eleman nan kote li fè pati. Sa a se sòt ti wonn. [Ton JWE] DAVID Malan: Epi ou ka sòt de santi ki jan relativman ti kras travay li nan fè sou chak etap. Sa a se sa tediousness son tankou. [Ton JWE] DAVID Malan: Sa a se sòt seleksyon an, kote nou chwazi eleman ki nou vle pa ale atravè tout ankò, li ankò e ankò ak mete l 'nan kòmansman an. [Ton JWE] DAVID Malan: Sa a se rantre sòt, ki ou ka reyèlman kòmanse santi. [Ton JWE] [Ri] DAVID Malan: yon bagay yo rele luten sòt, ki nou pa gen gade. [Ton JWE] DAVID Malan: Se konsa, kite m 'wè, kounye a, distrè jan ou èspere ke yo pa nan mizik, si mwen ka glise yon ti kras ti jan nan matematik nan isit la. Se konsa, gen nan yon fason katriyèm ke nou kapab panse osijè de sa li vle di sa yo fonksyon yo dwe pi vit pase moun ke nou te wè anvan. Men, si w ap vini nan kou a soti nan yon background matematik, ou aktyèlman konnen petèt deja ke ou ka kalòt yon tèm sou teknik sa a - savwa rkursyon, yon fonksyon ke yon jan kanmenm rele tèt li. Li di ankò, sonje ki sòt plonje pseudocode te repetitif nan sans ke youn nan etap plonje sòt nan te rele sòt - ki se, tèt li. Men, Erezman, paske nou te kenbe rele sòt, oswa rantre sòt, espesyalman, sou yon pi piti ak pi piti ak pi piti lis, nou evantyèlman fon soti gras a sa nou pral rele yon baz ka-a, ka a difisil-kode ki te di si lis la se piti, mwens pase 2 nan ka sa a, jis retounen imedyatman. Si nou pa t 'gen ka sa a espesyal, nan algorithm ta pa janm anba soti, Se ou ki ta tout bon jwenn nan yon enfini bouk se vre wi: tout tan. Men, si ke nou te vle kounye a mete kèk nimewo sou sa a, ankò, lè l sèvi avèk n kòm gwosè a nan D 'la. Apre sa, mwen te vle mande ou, sa ki nan tan an total ki patisipe nan kouri sòt plonje? Oswa pi plis jeneralman, sa ki nan pri pou peye pou l 'nan tan? Oke li a trè fasil a mezire sa. Si n gen mwens pase 2, tan an patisipe nan klasman n eleman, kote n se 2, se 0. Paske nou jis retounen. Gen nan pa gen travay yo dwe fè. Koulye a, joui, petèt li nan yon sèl etap oswa de etap sa yo konnen kantite lajan an nan travay, men li la ase pre a 0 ki Mwen jis ale nan di pa gen okenn travay se obligatwa si lis la se konsa ti yo dwe entérésan. Men, ka sa a se enteresan. Ka a repetitif la te branch ki nan pseudocode a ki di lòt moun, sòt mwatye gòch li yo, sòt dwa mwatye, fizyone mwatye yo de. Koulye a, poukisa fè ekspresyon sa a reprezante ki depans? Oke, T n jis vle di a tan sòt eleman n. Lè sa a, sou bò men dwat-ou nan egal siy la, T a nan n divize pa 2 se refere li a pri pou peye pou ki sa? Fouye mwatye gòch la. T a lòt kote nan n divize pa 2 a se prezimableman refere li a pri a sòt mwatye a dwat. Lè sa a, n nan plis? Èske fusion la. Paske si ou gen de lis, youn nan n gwosè plis pase 2 ak yon lòt ki gen yon gwosè n plis pase 2, ou gen esansyèlman manyen chak nan sa yo eleman, jis tankou Rob manyen chak nan tas yo, ak jis jan nou pwente nan chak nan volontè sou sèn. Se konsa, n se depans lan nan fusion. Koulye a, malerezman, sa a fòmil tou se tèt li repetitif. Se konsa, si poze kesyon sa a, si n se, di, 16, si gen nan 16 moun sou sèn oswa 16 tas nan videyo a, konbyen manm etap li pran sòt yo ak plonje sòt? Li nan aktyèlman pa yon repons evidan, paske kounye a ou gen sòt nan recursive reponn sa a fòmil. Men, sa a OK, paske, kite m 'pwopoze ke nou fè bagay sa a. Tan la ki enplike sòt 16 moun oswa 16 tas yo pral reprezante jeneralman kòm T nan 16. Men, ki egal, dapre nou anvan yo lèt an poud, 2 fwa kantite a tan li pran sòt 8 tas plis 16. Li di ankò, plis 16 se tan a fizyone, ak T nan de fwa nan 8 a se nan tan sòt bò gòch mwatye mwatye dwat. Men, ankò, sa a se pa ase. Nou dwe plonje nan pi fon. Sa vle di nou bezwen reponn a kesyon, ki sa ki T nan 8? Oke T nan 8 se jis 2 fwa T nan 4 plis 8. Oke, sa ki nan T nan 4? T nan 4 se jis 2 fwa T nan 2 plis 4. Oke, sa ki nan T nan 2? T nan 2 se jis 2 fwa T nan 1 plis 2. Li di ankò, nou kalite ap resevwa kole nan sa a sik. Men, li la sou frape ki sa yo rele ka baz. Paske sa ki nan T nan 1, nou t ap reklame? 0. Se konsa, koulye finalman, nou ka travay bak. Si T nan 1 se 0, mwen kapab kounye a tounen moute yon sèl liy sa a Guy isit la, e mwen ka ploge nan 0 pou T nan 1. Se konsa, sa vle di li egal 2 fwa zewo, otreman li te ye kòm 0, plis 2. Se konsa, ki ekspresyon antye se 2. Koulye a, si m 'pran T a nan 2, ki gen repons se 2, ploge li nan liy nan mitan, T nan 4, ki ban m '2 fwa 2 plis 4, se konsa 8. Si m 'Lè sa a, ploge nan 8 a anvan yo nan liy, ki ban m '2 fwa 8, 16. Men, si nou Lè sa a, kontinye ke ak nan 24, pandan l ajoute nan 16, nou finalman jwenn yon valè de 64. Kounye a ke nan ak tèt li sòt de pale pa gen anyen nan notasyon la n, gwo O, Omega an ke nou te gen te pale de. Men, li sanble ke 64 se vre 16, gwosè a nan D 'a, ale baz 2 nan 16. Men, si sa a se yon ti kras abitye, jis panse tounen, epi li ap tounen ou evantyèlman. Si sa a se louvri sesyon baz 2, se tankou 2 leve soti vivan nan sa a ba ou 16? Oh, sa a, se 4, se konsa li a 16 fwa 4. Li di ankò, li pa yon kontra gwo si sa a se sòt de yon memwa vwale kounye a. Men, pou kounye a, pran sou lafwa ki 16 boutèy demi lit 16 se 64. Se konsa, tout bon, ak sa a saniti senp tcheke, nou te konfime - men se pa pwouve fòmèlman - tan sa a nan kouri nan plonje sòt se vre n ale n. Se konsa, pa move. Li definitivman pi bon pase nan algoritm nou te wè konsa byen lwen, ak li nan paske nou te exploitées, yon sèl, yon teknik yo rele rkursyon. Men, plis enteresan pase sa, ki nosyon nan divize ak konkeri. Yon fwa ankò, se vre wi: semèn 0 bagay ki menm koulye a, se renouvlab nan yon plis irezistib fason. Koulye a, yon plezi fè egzèsis ti kras, si ou te pa janm fè sa a - ak pwobableman ou pa ta gen, paske sòt de nòmal moun ki pa panse fè sa. Men, si mwen ale nan google.com epi si Mwen vle aprann yon bagay sou rkursyon, antre. [Ri] [PLIS ri] DAVID Malan: Move blag tou dousman gaye. [Ri] DAVID Malan: jis nan ka, li la a. Mwen pa t 'eple li sa ki mal, ak gen nan blag la. Tout dwa. Eksplike l 'bay pèp la kap vini jwenn ou si li pa te byen klike jis ankò. Men, rkursyon, plis jeneralman, refere nan pwosesis la nan yon fonksyon rele tèt li, oswa plis jeneralman, divize yon pwoblèm nan yon bagay ki ka rezoud parselèr pa rezoud idantik pwoblèm reprezantan. Angrenaj chanjman Oke, kite la sèlman pou moman yon. Nou renmen fini sou cliffhangers sèten, Se konsa kite la kòmanse yo mete etap la, pou plizyè minit, sou yon ide trè senp - sa yo ki an échanjé de eleman, dwa? Tout moun sa yo algoritm nou te te pale sou koup ki sot pase nan konferans enplike kèk sòt de échanjé. Jodi a li te vizualiz pa yo ap resevwa moute soti nan chèz yo ak ap mache otou, men nan Kòd, nou ta jis pran yon eleman soti nan yon etalaj ak plok l 'nan yon lòt. Se konsa, ki jan nou ale sou fè sa? Oke, kite m 'ale pi devan epi ekri yon pwogram rapid isit la. Mwen pral ale pi devan epi fè sa a kòm sa ki annapre yo. Se pou yo rele sa a - ki sa nou vle yo rele yon sèl sa a? Aktyèlman, pa gen okenn. Kite m 'remonte. Mwen pa vle fè sa cliffhanger ankò. Li pral piye plezi nan. Se pou yo fè sa pito. Sipoze ke mwen vle ekri yon ti kras pwogram yo epi ke kounye a anbwase sa a lide nan rkursyon. Mwen kalite te resevwa devan yo nan tèt mwen la. Mwen pral fè bagay sa a. Premyèman, yon rapid gen ladan nan estanda io.h, kòm byen ke yon enkli nan cs50.h. Lè sa a, mwen pral ale pi devan ak deklare Int anile prensipal nan chemen an dabitid. Mwen reyalize mwen te misnamed dosye a, se konsa kite m 'jis ajoute yon. c ekstansyon isit la se konsa ke nou ka konpile li byen. Kòmanse fonksyon sa a la. Ak fonksyon an mwen vle ekri, byen tou senpleman, se youn ki mande a itilizatè pou yon nimewo ak Lè sa a ajoute moute tout nimewo yo ant ki nimewo ak, di, 0. Se konsa, premye Mwen pral ale pi devan ak deklare n Int. Apre sa, mwen kopye kèk kòd ki nou te itilize pou yon ti tan. Pandan ke yon bagay se vre. Mwen pral tounen vin jwenn ke nan yon ti moman. Ki sa mwen vle? Mwen vle di printf pozitif nonb antye ki pè tanpri. Lè sa a, mwen pral di n vin jwenn Int. Se konsa, ankò, kèk boilerplate Kòd ke nou te itilize anvan. Ak mwen se pral fè sa a pandan y ap n se mwens pase 1. Se konsa, sa a pral asire ke itilizatè a ki ban m 'yon nonm antye ki pozitif. Epi, koulye a mwen pral fè bagay sa a. Mwen vle ajoute jiska tout nan nimewo ki ant 1 ak ak n, oswa 0 ak n, équivalant, yo ka resevwa sòm total la. Se konsa, gwo sigma senbòl la ke ou ta ka sonje. Se konsa, mwen pral fè sa a pa rele premye yon fonksyon rele sigma, pase l 'nan n, ak Lè sa a mwen pral di printf, repons lan se dwa gen. Se konsa, nan kout, pou mwen jwenn ak Int soti nan itilizatè a. Mwen asire li nan pozitif. Mwen deklare yon varyab repons yo rele nan Int di ki kalite ak magazen nan li retounen nan valè de sigma, pase nan n kòm opinyon. Lè sa a, mwen ekri ak lèt ​​detache soti ke repons lan. Malerezman, menm si sigma son tankou yon bagay ki ke sa ta kapab nan math.h dosye a, deklarasyon li yo, li la aktyèlman pa. Se konsa, ke se ok. Mwen ka aplike sa a tèt mwen. Mwen pral aplike yon fonksyon rele sigma, ak li pral pran yon paramèt - kite yo jis rele li m, jis se konsa li a diferan. Lè sa a, moute isit la, mwen pral di, byen, si m se mwens pase 1 - sa a se yon trè entérésan pwogram nan. Se konsa, mwen pral ale pi devan epi imedyatman retounen 0. Li jis pa fè sans yo ajoute moute tout chif yo ant 1 ak m si m se tèt li 0 oswa negatif. Lè sa a, mwen pral ale pi devan ak fè sa trè iterativman. Mwen pral fè sa a sòt de fin vye granmoun lekòl, ak Mwen pral ale pi devan ak di ke mwen pral deklare yon sòm yo dwe 0. Lè sa a, mwen pral gen yon pou bouk nan Int - ak kite m 'fè l' matche ak nou Kòd distribisyon, se konsa ou genyen yon kopi nan kay la. Int mwen vin 1 sou jiska mwen se mwens pase oswa egal a m. mwen plis plis. Lè sa a, andedan sa a pou bouk - nou ap prèske gen - sòm vin sòm plis 1. Lè sa a, mwen pral tounen sòm total la. Se konsa, mwen te fè sa byen vit, byen Byensir. Men, ankò, fonksyon prensipal trè dwat, ki baze sou Kòd nou te ekri nan Liv la konsa byen lwen. Li sèvi ak bouk la doub yo ka resevwa yon pozitif Int soti nan itilizatè a. Mwen Lè sa a, pase ke Int nan yon fonksyon nouvo rele sigma, lè w rele li, ankò, n. Apre sa, mwen sere valè a retounen, repons lan nan bwat la nwa kounye a li te ye kòm sigma, nan yon varyab rele repons lan. Apre sa, mwen enprime li. Si nou kounye a kontinye istwa a, ki jan sigma aplike? Mwen pwopoze aplike jan sa a. Premyèman, yon ti kras nan kont kouran erè- asire w ke itilizatè a pa pitye avè m 'ak pase nan kèk valè negatif oswa 0. Apre sa, mwen deklare yon varyab ki rele sòm yo mete l 'nan 0. Koulye a, mwen kòmanse pou avanse pou pi soti nan mwen egal 1 tout wout la jiska epi ki gen ladan m, paske mwen vle genyen ladan yo nan tout nimewo soti nan yon nan m, enklizif. Ak andedan sa a pou bouk, mwen jis fè sòm vin tou sa li se kounye a, plis la valè de mwen. Plus valè a nan mwen. Kòm yon sou kote, si ou pa te wè sa a anvan, gen nan kèk sik Massachusetts Institute of Technology pou liy sa a. Mwen ka ekri sa a kòm plis egal mwen, jis pou konsève pou tèt mwen yon kèk frap ak gade yon pi fre ti jan. Men, sa a tout moun. Li nan fonksyonèl menm bagay la. Malerezman, sa Kòd la pa ale nan konpile ankò. Si mwen kouri fè, 0 sigma ki jan am Mwen pwal jwenn rele nan? Ki sa ki nan li pral pa renmen? ODYANS: [fèbl]. DAVID Malan: Yeah, mwen pa t 'deklare fonksyon an moute tèt, dwa? C se kalite estipid, nan ke li sèlman fè sa ou di li fè, epi ou dwe fè li nan ki lòd. Se konsa, si mwen frape Antre isit la, mwen pral jwenn yon avètisman sou sigma enplisit deklarasyon an. Oh, pa yon pwoblèm. Mwen ka ale moute sou tèt la, epi mwen kapab di yo, tout dwat, rete tann yon minit. Sigma se yon fonksyon ki retounen yon Int epi li espere yon Int kòm virgules opinyon,. Oswa mwen te kapab mete fonksyon an antye pi wo a prensipal la, men an jeneral, mwen ta rekòmande kont sa, paske li nan janti ak toujou gen prensipal nan tèt la pou ou ka plonje dwat nan ak konnen ki sa yon pwogram nan ap fè nan fè lekti prensipal an premye. Se konsa, kounye a kite m 'klè ekran an. Renouvèlman sigma 0. Tout sanble yo tcheke deyò. Kite m 'kouri sigma 0. Pozitif entè. Mwen pral ba li nimewo a 3 kenbe li senp. Se konsa, ki ta dwe ban m '3 plis 2 plis 1, se konsa 6. Antre, ak tout bon pou mwen jwenn 6. Mwen ka fè yon bagay pi gwo - 50, 12, 75. Menm jan yon tanjant, mwen pral fè yon bagay ridikil tankou yon gwo vrèman nimewo, Oh, ki aktyèlman te travay soti - eh, mwen pa kwè ki bon. Ann wè. Se pou yo vrèman dezòd ak li. Sa se yon pwoblèm. Ki sa ki nan ale sou? Kòd la pa ki move. Li nan toujou lineyè. Sifle se yon efè bon, menm si. Ki sa ki nan ale sou? Pa konnen si m 'te tande l'. Se konsa, li vire soti - ak sa a se kòm yon sou kote. Sa a se pa nwayo a lide nan rkursyon. Li sanble, paske mwen ap eseye reprezante tankou yon nimewo gwo, ki pi gen anpil chans li a ke yo te entèrprete pa C kòm yon kantite pa pozitif, men negatif nimewo. Nou pa t 'te pale osijè de sa a, men li vire soti gen nimewo negatif nan mond lan nan Anplis de sa nan nimewo ki pozitif. Ak mwayen yo pa ki ou kapab reprezante yon chif negatif esansyèlman se, ou itilize yon sèl espesyal ti jan yo endike pozitif sou negatif. Li se yon ti kras pi plis konplèks pase sa, men sa a lide a de baz yo. Se konsa, malerezman, si c konfizyon yon sèl nan tout sa yo Bits kòm aktyèlman vle di, oh, sa a se yon nimewo negatif, bouk mwen isit la, pou egzanp, se aktyèlman pa janm ale nan mete fen nan. Se konsa, si mwen te aktyèlman enprime yon bagay ankò e ankò, nou ta wè yon bann antye. Men, ankò, sa a se san konte pwen an. Sa a se vrèman jis yon sòt de entelektyèl kiryozite ke nou ap vin Retounen nan evantyèlman. Men, pou kounye a, sa a se yon bon aplikasyon si nou sipoze ke nan itilizatè ap bay antye ki anfòm nan antye. Men, mwen reklamasyon ke sa a Kòd, franchman, kapab fèt pou pi plis tou senpleman. Si objektif la nan men se pran yon kantite tankou m ak ajoute jiska tout nan nimewo ant li ak 1, oswa Kontrèman ant 1 ak li, mwen fè reklamasyon ke mwen ka prete ide sa a ki rantre sòt te genyen, ki te pran yon pwoblèm sa a gwosè ak divize l ' nan yon bagay pi piti. Petèt pa mwatye, men ki pi piti, men rprezantativ menm bagay la. Menm lide, men se yon pwoblèm pi piti. Se konsa, mwen aktyèlman - kite m 'sove sa a ranpli ak yon kantite vèsyon diferan. Nou pral rele vèsyon sa-a 1 olye pou yo 0. Apre sa, mwen reklamasyon ke mwen kapab aktyèlman reimplement sa a nan sa a sòt de lide-koube fason. Mwen pral kite pati nan li pou kont li. Mwen pral di si m se mwens pase oswa menm egal a 0 - Mwen jis yo pral yon ti kras plis nan dèyè tan sa a ak kont kouran erè mwen - Mwen pral ale pi devan epi retounen 0. Sa a se abitrè. Mwen senpleman n ap deside si itilizatè a ki ban m 'yon kantite negatif, mwen se retounen 0, epi yo ta dwe te li lòt dokiman an pi byen. Lòt Bagay - remake ki sa mwen pral fè. Lòt Bagay Mwen pral retounen m plis - ki sa ki sigma nan m? Oke, sigma nan m plis m mwens 1, plis m 2 mwens, plis m mwens 3. Mwen pa vle ekri nan tout sa soti. Poukisa pa fè sa mwen jis bote? Recursive rele tèt mwen ak yon yon ti kras ki pi piti pwoblèm, virgules, ak rele li yon jou? Dwa? Koulye a isit la, tou, ou kapab santi ou oswa enkyete ke sa a se yon bouk enfini ki mwen se favorize, kijan mwen mete ann aplikasyon sigma pa rele sigma. Men, sa a parfe OK, paske mwen te panse devan yon te ajoute ki liy? ODYANS: [fèbl]. DAVID Malan: 23 a 26, ki se kondisyon si m 'yo. Paske sa ki nan bèl sou la soustraksyon isit la, paske mwen toujou Distribiye sigma pi piti pwoblèm, ki pi piti pwoblèm, ki pi piti - li a pa mwatye gwosè a. Li se sèlman yon ti bebe etap ki pi piti, men sa a OK. Paske evantyèlman, nou pral travay wout nou desann nan 1 oswa 0. Men, yon fwa nou frape 0, sigma pa ale nan rele tèt li ankò. Li nan ale nan imedyatman retounen 0. Se konsa, efè a, si ou sòt de van sa a moute nan tèt ou, se yo ajoute m plis m 1 mwens, plis m mwens 2, plis m mwens 3, plis dot, dot, dot, m mwens m nan, evantyèlman ban nou 0, epi efè a se finalman ajoute tout bagay sa yo ansanm. Se konsa, nou pa gen, ak rkursyon, rezoud pwoblèm lan ke nou pa t 'kapab rezoud anvan. Vreman vre, vèsyon 0 sa a, ak chak pwoblèm nan dat, ki te soluble ak jis lè l sèvi avèk pou pasan oswa pandan y ap pasan oswa konstwi menm jan an. Men, rkursyon, mwen daresay, ba nou yon fason diferan nan panse sou pwoblèm, kijan, si nou ka pran yon pwoblèm, fann li soti nan yon bagay yon ti jan gwo nan yon bagay yon ti jan ki pi piti, mwen reklamasyon ke nou ka rezoud li petèt yon ti kras pi plis chik an tèm nan desen an, ki gen mwens kòd, ak petèt menm rezoud pwoblèm ki ta pi rèd, kòm n ap pètèt wè la a, pou rezoud piman iterativman. Men, cliffhanger a ke mwen te fè vle kite nou sou te sa a. Kite m 'ale pi devan epi louvri moute yon dosye soti nan - aktyèlman, kite m 'ale ak fè sa-a vit reyèl. Kite m 'ale pi devan epi pwopoze sa ki annapre yo. Pami Kòd jodi a se sa a ranpli isit la. Sa a yon sèl isit la, noswap. Se konsa, sa a se yon pwogram estipid ti kras ki Mwen vide sa ki reklamasyon yo fè sa ki annapre yo. Nan prensipal la, li premye mwen menm yon Int rele x ak fikse li valè a nan 1. Lè sa a, li menm yon y Int ak fikse li valè a 2. Lè sa a, li simagri konnen ki sa ki x ak y se. Lè sa a, li di, échanjé, dot dot dot. Lè sa a, li reklamasyon yo dwe rele yon fonksyon rele swap, pase nan x ak y, lide a nan ki se ki èspere ke x ak y ap tounen diferan, opoze an. Lè sa a, li reklamasyon échanges! ak yon entewogasyon, pwen eksklamasyon. Lè sa a, li simagri soti x ak y. Men, li sanble ke sa a trè senp demonstrasyon desann isit la se aktyèlman buggy. Menm si mwen deklare yon ti tan varyab ak pou yon ti tan mete yon nan li, Lè sa a, mwen reafèktasyon yon valè b - ki santi l rezonab, paske mwen te sove yon kopi yon nan temp. Apre sa, mwen mete b egal tou sa te nan temp. Sa a sòt de jwèt koki nan deplase yon nan b ak b nan yon lè l sèvi avèk sa a mitan-Nonm yo rele temp santi l pafètman rezonab. Men, mwen reklamasyon ke lè mwen kouri sa a Kòd, jan mwen pral fè kounye a - kite m 'ale pi devan epi kole li nan isit la. Mwen pral rele sa noswap.c. Men, kòm non an sijere, sa a se pa pral gen yon pwogram kòrèk la. Fè noswap. / Pa gen swap. x se 1, y se 2, échanjé, échanges. x se 1, y se 2. Sa a se fondamantalman sa ki mal, menm menm si sa a sanble parfe rezonab m '. Apre sa, se yon rezon ki fè, men nou pa pral revele rezon ki fè yo jis ankò. Pou kounye a cliffhanger nan dezyèm mwen te vle yo kite ou ak se sa a, yon anons nan kalite sou kòd koupon. Inovasyon nou ak jou elèv la anreta ane sa a te pwovoke yon nimewo ki pa trivial nan kesyon, sa ki te pa entansyon nou an. Entansyon a nan sa yo kòd koupon, kijan si ou fè yon pati nan pwoblèm nan mete byen bonè, kidonk resevwa yon jou anplis, te vrèman ede ou guys ede tèt ou kòmanse byen bonè, sòt nan pa incentivizing ou. Ede nou distribye chaj atravè biwo èdtan pi bon pou ke li nan sòt de genyen genyen-. Malerezman, mwen panse ke enstriksyon mwen pa te, nan dat, trè klè, se konsa Mwen te ale tounen fen semèn sa a ak mete ajou espèk a nan pi gwo, tèks odasyeu eksplike bal tankou sa yo. Epi jis yo di ke li plis piblikman, pa default, ansanm pwoblèm yo akòz Jedi a midi, pou chak progranm la. Si w kòmanse byen bonè, fini yon pati nan pwoblèm nan mete nan Mèkredi nan 12:00 PM, pati a ki gen rapò ak yon koupon Kòd, lide a se ke ou ka pwolonje dat limit ou pou la P mete jiska Vandredi. Sa se, ti jan sou yon pati ti nan P a mete relatif nan sa ki anjeneral se nan pi gwo pwoblèm, epi ou achte tèt ou yon jou anplis. Fwa ankò, li vin ou panse sou mete nan pwoblèm, vin ou lè biwo pi bonè. Men, pwoblèm nan Kòd koupon se toujou obligatwa, menm si ou pa soumèt li. Men, plis irezistibleman sa a. (Chuichui ETAP) Ak moun ki jan kite byen bonè yo pral regrèt sa. Kòm yo jan yo sou balkon la. Mwen regrete nan avanse yo jan yo sou balkon la pou rezon ke yo pral klè nan jis moman sa a. Se konsa, nou gen chans gen youn nan Zanmi ansyen CS50 nan ansèyman tèt nan yon konpayi yo rele dropbox.com. Yo te trè san gad dèyè bay yon Kòd koupon isit la pou espas sa a anpil, ki se moute soti nan la abityèl 2 jigokte. Se konsa, sa mwen te panse nou ta fè sa a sou nòt final la se fè yon ti jan nan yon kado, kijan nan jis moman sa yon, nou pral revele gayan an ak moun ki gen yon koupon Kòd ke ou ka Lè sa a, ale nan yo sit entènèt, tape l 'nan, ak vwala, jwenn yon antye anpil plis Dropbox espas pou ou aparèy ak pou dosye pèsonèl ou. Ak premye, ki moun ki ta renmen patisipe nan desen sa a? OK, kounye a ki fè li menm plis plezi. Moun nan ki resevwa sa a jigokte 25- Kòd koupon - ki se byen lwen plis irezistib pase an reta a jou kounye a, petèt - se youn nan moun ki chita sou tèt yon kousen chèz anba ki gen ki koupon kòd. Ou kapab kounye a gade anba kousen chèz ou. [Lèktur videyo] -Yon, de, twa. [Kriyan] -Ou jwenn yon machin! Ou jwenn yon machin! DAVID Malan: Nou pral wè ou nan Mèkredi. -Ou jwenn yon machin! Ou jwenn yon machin! Ou jwenn yon machin! Ou jwenn yon machin! Ou jwenn yon machin! DAVID Malan: jan balkon, vini desann isit la, yo kanpe devan an, kote nou gen depans siplemantè. -Tout moun jwenn yon machin! Tout moun jwenn yon machin! [Lèktur videyo END] Konteur: Nan CS50 kap vini an - Oratè 5: papa m, mwen bondye papa m bondye papa m bondye papa m bondye papa m bondye papa m bondye papa m bondye papa m bondye papa m bondye papa m - [Ukèlel jwe]