[Duke luajtur muzikë] 

DAVID J. Malan: Të gjitha e drejtë. Pra, të mirëpritur mbrapa. Kjo është CS50, dhe eshte fundi i javës së tre. 

Pra, kujtojnë në disa javëve të fundit, ne kemi qenë të shpenzimeve mjaft e Ora në C, për programimin, në sintaksë. Dhe kjo është krejt normale, në qoftë se ju jeni ende luftuar me Set Problem 2, të jetë banging kokën tuaj kundër murit. Është e fshehtë-looking mesazhet e gabimit dhe të mete që ju të nuk mund të mjaft të ndjekur poshtë. Sepse, pjesa tjetër e siguroi, se në vetëm një Ora javësh 'ju do të shikojnë prapa në gjëra të tilla si Cezarit, dhe [? V-genair,?] ndoshta edhe Crack, dhe të kuptojë se sa larg ju keni ardhur në një periudhë të shkurtër kohe. Pra, nëse kjo është ndonjë ngushëllim, ul receptorin e telefonit në atje tani për tani. 

Sot, edhe pse, ne fillojmë të tranzicionit për gjëra të nivelit të lartë. Dhe ne të fillojë të marrë për të dhënë se ju djema e di se si të programit, ose në pak fillimet e se niveli i rehati. Dhe ne do të fillojnë të marrin në konsideratë se si ne mundemi shkoni në lidhje me dizajnimin e programeve të më shumë në mënyrë efektive. Si ne mund të shkoni në lidhje me optimizmin efikasiteti i algoritmeve tanë, dhe të përgjithësisht zgjidhjen më shumë probleme interesante e. Dhe duke filluar për të marrë për të dhënë që, nëse ne të kërkuar për të, ne mund të kodojnë up çdo nga shembujt që kemi në mendje. Kështu që sot, ne nuk prek tastierën për çdo formë të kodit. Ajo do të jetë niveli shumë më të larta, dhe në fund të fundit, rreth zgjidhja e problemit-. 

Pra, për të marrë në këtë pikë, më lejoni të propozojnë se shtatë vijim rectangles përfaqësojnë shtatë dyer, prapa të cilat janë një bandë e tërë e Numrat, ndër të cilat është numri 50. Më lejoni të projektojë këtë on kjo ekran si edhe këtu. Dhe propozoj që ne kemi nevojë për vullnetar për ndihmojë të gjeni më një numër në frontin e Internet këtu për të parë. Vijnë më lart, në rozë. Dakord. Cili është emri juaj? 

JENNIFER: [e padëgjueshme] 

DAVID J. Malan: Na vjen keq? 

JENNIFER: Jennifer. 

DAVID J. Malan: Jennifer. Të gjithë të drejtë, Jennifer. Gëzohem që u njohëm. Come on up. Pra, këto këtu janë shtatë dyer, dhe çfarë Unë do të doja që ju të bëni për ne këtu, në frontin e të gjithë shokëve të tu, po na gjeni numrin, 50. Për të gjetur një numër, mundeni vjedhurazi prapa ndonjë nga këto dyer nga thjesht përgjimi mbi njërën nga dyert, dhe IT do të zbulojë numrin e saj. Dhe le të shohim se si shpejt ju mund të na gjeni numrin, 50. 

15. 16. 50. Nicely done. Dakord. Raund i duartrokitje për Jennifer. 

[Duartrokitje] 

Dakord. Pra, çfarë ishte e strategjia juaj për të gjetur numrin, 50? 

JENNIFER: Um, mendova se ndoshta në qoftë se - [Padëgjueshme] 

DAVID J. Malan: Oh. Give it një sekondë. Pra, ishte strategjia juaj për të gjetur numrin, 50? 

JENNIFER: Kështu që unë vetëm të fillojë në duke filluar për të parë se çfarë numri i parë ishte, dhe pastaj mendova, ndoshta në qoftë se ata janë të renditura, unë vetëm do të mbajë përgjimi larta deri? 

DAVID J. Malan: OK. Dhe ne duket se kanë gjetur që të jetë rasti. Edhe pse, le të zhvishem përsëri shtresa vetëm pak, dhe ju doni të shkoni përpara dhe të zbulojë dyert e tjera ju mund të keni zgjedhur? 

JENNIFER: Oh, i dashur. 

DAVID J. Malan: Ah. 

JENNIFER: Kështu që unë vetëm mori me fat. 

DAVID J. Malan: Pra, ju mori me fat. Dakord. Pra, jo i keq. Por kjo është një interesante Insajt, e drejtë? Nëse keni supozuar, dhe ju e bëri të marrë, në të vërtetë, pak fat atje. Por nëse ju supozohet se numrat e ishin të renditura, ju mund të jenë më të saktë se si që ndikoi sjellja juaj? 

JENNIFER: Pra, në qoftë se ata ishin të renditura, unë menduar ndoshta më i vogli tek më i madhi. 

DAVID J. Malan: OK. 

JENNIFER: Ose në qoftë se kjo përfundoi duke qenë me të vërtetë e madhe, atëherë më e madhe për të vogël. 

DAVID J. Malan: OK. Pra, më i madh për të vogël, ose vogli tek më i madhi. Por më lejoni të të propozojë, supozoj keni pasur gotten pafat, dhe mendoj se ata nuk ishin, në fakt, të renditura, sa i ato dyert mund të keni pasur për peek prapa në këtë rast më të keq? 

JENNIFER: Të gjitha prej tyre. 

DAVID J. Malan: Të gjitha prej tyre. Pra, le të përgjithësoj se si n. Nuk ndodh të jetë 7, por le të më në përgjithësi thonë se ka dyert n në Ekran këtu. Pra, në rastin më të keq, ju do të keni të shikojmë prapa 7 dyert, ose dyert n. Dhe kështu kjo është me të vërtetë, kjo është pak e fat sot, por kjo është me të vërtetë një lineare algoritmi i terezi, edhe pse ju ishin lloj i skipping rreth. A është kjo e drejtë? 

JENNIFER: Po. 

DAVID J. Malan: E pra, më lejoni të shohim në qoftë se juaj Ndryshimet strategji në qoftë se unë të na për të Shembulli ynë i dytë këtu me 7 dyer të ndryshme. Numrat e njëjtë, por kjo herë që ata janë të renditura. Cila është strategjia juaj këtu do të jetë, duke u përpjekur për të vënë nga mendjen tuaj se çfarë numrat e tjerë ishin - 

JENNIFER: OK. 

DAVID J. Malan: - më herët? 

JENNIFER: Le të fillojë me një të parë. 

DAVID J. Malan: Të gjithë të drejtë. Fillojnë me një të parë. 4. Tani ku ju do të shkoni, dhe pse? 

JENNIFER: 4 është me të vërtetë i vogël. Pra, nëse ata janë lloj ndoshta më të vogël të madhe, ajo duhet jenë dy herë se, dhe -. 

DAVID J. Malan: OK. Le të shohim, të cilat ju mendoni se? 

JENNIFER: Provoni i fundit. Gëzohem. 

DAVID J. Malan: Shumë bukur bërë. Dakord. 

[Duartrokitje] 

DAVID J. Malan: OK. Pra, ju jeni në të vërtetë duke bërë këtë tmerrshëm, sepse ju jeni bërë atë shumë mirë. Cili na lë në gjendje të të bëjë pika të caktuara. Pra, le të përpiqemi të rrokulliset prapa këtu. 

JENNIFER: OK. 

DAVID J. Malan: Shumë mirë bërë, megjithatë. Pra, ju keni filluar në fillim, ju e pa se kjo ishte 4, atëherë ju u zhvendos në fund. Por mendoj që ju nuk e merrni me fat atje, dhe mendoj 50 ishte diku tjetër. Çfarë hapi juaj i tretë kanë qenë? 

JENNIFER: Kthehu në fillim. 

DAVID J. Malan: Kthehu mbrapa te fillimit. OK, kështu që ju do të kemi preku kjo derë, e cila ishte 8. Dakord. Kështu që nuk është 50. Ku do keni shikuar ardhshme? 

JENNIFER: Nëse unë nuk e bëri e di se ata renditura. 

DAVID J. Malan: korrekte. E pra, nëse ju nuk e dini ata ishin të renditura - 

JENNIFER: Oh, nuk e di, vërtet. 

DAVID J. Malan: - por ju nuk e keni e di ku 50 ishte ende? 

JENNIFER: Vetëm mbani shkuar. 

DAVID J. Malan: Të gjithë të drejtë. OK. Mbani shkuar. OK, se unë mund të punojnë me të. 

JENNIFER: OK. 

DAVID J. Malan: Tani, në qoftë se ju jeni vetëm duke shkuar për të do të mbajë, çfarë është tuaj algorithm delegimin mbështetur në. 

JENNIFER: lineare -. 

DAVID J. Malan: Kjo është lloj i linear. Por më lejoni të propozojnë, le të mua vënë në vend. Më lejoni të rifreskoni faqen. numër të njëjtë, rregullim të njëjtë, dyert e njëjta. Por mendoj se prapa në atë ditë të parë në klasë kur ne grisi një libër telefoni në , gjysma lloj, dhe çfarë ishte strategjia jonë atje? 

JENNIFER: Filloni në mes. 

DAVID J. Malan: OK. Pra, fillojë në mes. Pra, le të shkojnë përpara dhe simulojnë se. Të fillojë në mesin e fushës nga zbuluar atë derë. Pra, numri 16. Pra, çfarë do të djalë të fortë kanë bërë, i cili shqeu librin e telefonit në gjysmë, për të shkuar në mend të ardhshëm? 

JENNIFER: Shkoni në këtë gjysmë. 

DAVID J. Malan: Dhe pse në të djathtë? 

JENNIFER: Në qoftë se ata ishin lloj i vogël të madh, atëherë 50 duhet të jetë në atë fund. 

DAVID J. Malan: Mirë. Totally të arsyeshme. Pra, si një libër telefoni, ju shkoni në e drejta në krahasim me të majtë, por këtu eshte takeaway çelësi. Ju tani mund të hedhin larg, ose shkëput, gjysma e këtij problemi, duke mos ju me 7 dyer, por me të vërtetë me vetëm 3. Cili është afërsisht gjysma e madhësia e problemit. Dakord. Kështu që tani se çfarë ju do të keni bëhet pasi ju shkoni e drejtë? 

JENNIFER: Pra, 16 është ende mjaft i vogël, relative në 50, kështu që ndoshta unë do të përpiqemi, si, ky. 

DAVID J. Malan: Të gjithë të drejtë. 42. Të gjithë të drejtë, kështu që tani se çfarë është tuaj Instinkti ju thënë? 

JENNIFER: Unë mund të hedhin larg këtë dhe pastaj vetëm - 

DAVID J. Malan: OK. Mirë, ju mund të hedhin larg gjysma e majtë atje. 

JENNIFER: - marr këtë një të tillë. 

DAVID J. Malan: Dhe drejtë. 

JENNIFER: Po. 

DAVID J. Malan: Pra, edhe pse kjo është e vështirë për të parë ndoshta, kur ka vetëm 7 dyert, mendoni rreth, tani, qëndrueshmëri e algoritëm ju vetëm aplikuar. Në rastin e mëparshëm, ju e bëri merrni me fat, e cila ishte e madhe. Por ju bëri përdorni një orientues, Unë do të thoja. Keni përdorur lloj instinktet tuaja, dhe ditur se renditura, në qoftë se kjo është goxha të vogla në fillim, natyrisht, ne kemi mori për të shkojnë më shumë në të djathtë. Por në një farë mënyre, keni fat, për shkak se ndoshta kjo ishte Numri 100, dhe ndoshta 50 ishte më në mes. Ndoshta 50 ishte madje edhe mbi këtu. 

Por çfarë keni bërë pak ndryshe kjo ishte koha, që ju bëri të njëjtën gjë përsëri dhe përsëri. Dhe unë do të argumentojnë se ajo që ju vetëm ka, megjithëse ndikuar nga telefoni libër shembull, është diçka shumë më e më shumë algorithmic, dhe shumë më pak të veçantë cased. Shumë më pak instiktiv. Pra, në fund të ditës, si do ju përshkruani efikasitetin e algorithm e parë, ku ju shkoi majta në të djathtë, kundrejt Algoritmi i dytë këtu? 

JENNIFER: Kjo duhet, si, ndoshta përgjysmon kohën, ose edhe më shumë, vërtet. 

DAVID J. Malan: OK, ndoshta edhe më shumë. Le të shtyjë një pak më e vështirë në atë. Çfarë me të vërtetë, në qoftë se ne vazhdojmë këtë Logjika, ne patjetër përgjysmuar running kohë me këtë algoritëm të dytë duke hedhur larg gjysmën e Numrat, por çfarë ka të bëjmë më tej përsëritje, kur Jennifer zbuloi numri i dytë? 

Ne përgjysmuar numrin e dyerve përsëri. Dhe pastaj çfarë bëri bëjmë pas kësaj, në qoftë se ka pasur dyert më shumë për të luajtur me? Ne do të përgjysmojë ato, dhe përsëri, dhe përsëri, dhe përsëri. Dhe kjo ishte vetëm si ju djema të gjithë këmbë deri në javë pare te , klasa gjysma e keni ulur poshtë, gjysma i keni ulur poshtë, gjysma prej jush ulur, derisa një i vetmuar shpirti ishte në këmbë. Dhe ne i thamë se koha drejtimin e se, numri i hapave ajo mori ishte me urdhër të kujt? 

Kryetari 1: [padëgjueshme] 

DAVID J. Malan: Pra, baza log 2 n, ose thjesht më thjesht, hyni nga n. Pra, diçka logaritmike. Dhe grafiku nuk ishte një vijë e drejtë që mori vetëm keq e më keq, ajo ishte kjo kurba interesante që nuk e bëri merrni aq keq me kalimin e kohës. Pra, le të mbajë më në këtë ide. Le të thank Jennifer. Thanks so much për të ardhur në dorë. Dhe, një sec. Asnjë llambat tavolinë sot, por ne keni CS50 topa stresit. 

JENNIFER: Yay. 

DAVID J. Malan: Të gjithë të drejtë, këtu. Faleminderit për shkaktohen stresi deri këtu. Dakord. Pra, le të shohim nëse mundemi jo tani formalizojë këtë një pak më shumë. Pra, përsëri, ajo që ne vetëm e bëri ishte në thelb e njëjta gjë si ne e bëmë në atë jave pare. Por në vend se fundi me vetëm një lineare algorithm, të cilat ne përshkruar më parë si këtë vijë të drejtë, ku, në qoftë se ne kemi vënë një derë më shumë në ekran, atëherë Jennifer do kanë pasur të shikojmë, potencialisht, prapa një derë më shumë. Në qoftë se ne kemi vënë dy dyer më shumë, ajo mund të ketë të shikojmë prapa dy dyer më shumë. 

Dhe kështu, nuk ishte ky linear Marrëdhënia ndërmjet madhësisë së Problemi në, të themi, x-aks, dhe sasia e kohës që duhet për të zgjidhet në y. Por fotografia unë isha duke aluduar në më herët ishte kjo linjë e gjelbër. Jeshile qëllimisht, për shkak se ajo vetëm ndjehet më mirë. Në teori, algorithm, kur ne e bëmë atë me librin e telefonit, kur ne e bëmë atë me ju djema numëruar njëri-tjetrin, dhe në rastin e dytë, kur Jennifer vetëm e bëri atë deri këtu, ajo ishte lloj i rrënjësisht të mirë. Për shkak se ajo nuk ishte vetëm dy herë më shpejt. Kjo nuk ishte edhe katër herë më shpejtë. Ajo ishte krejtësisht e varur nga ajo që Madhësia e input ishte, si për sa hapat që përfundimisht e mori. 

Dhe kështu kjo ide e thjeshtë që ne të gjithë e mori për të dhënë me librin e telefonit, mund ngjashme të aplikohet për diçka si kjo. Dhe kjo mund të jetë më rastësisht i njohur si, si ju mund të imagjinoni, përça dhe sundo. Jo ndryshe nga ajo që kemi bërë, natyrisht, me librin e telefonit. 

Por pseudokod, risjell, ishte kjo. Pra, ne nuk do ta bëjë këtë përsëri, por kujtojnë që javën e parë, të gjithë prej nesh u ngrit dhe pastaj gjysma prej jush u ul, gjysma e ju u ul, gjysma prej jush u ul. Se algorithm u zbatua në një të bit prej nje menyre cheating, ne se, ajo nuk ishte vetëm një nga mua numërimit, rrënjësisht, në mënyrë më efikase. Në këtë rast, unë u leveraging një burim sekondar. Lloj, CPU të shumta, truri shumta, njerëzit të shumta i zgjuar në dhomë ishin të duke ndihmuar mua të merrni nga diçka lineare për diçka logaritmike, nga diçka kuqe të gjelbër diçka. 

Por në këtë rast, Jennifer vetmuar mundeni rrënjësisht të përmirësuar mbi Performanca e algorithm e saj të parë nga, përsëri, vetëm duke menduar pak më e vështirë. Dhe tani, kur vjen koha për të zbatuar këto gjëra, duke parafytyruar çfarë rreshta të kodit që ju mund të shkruani të tilla që ju mund të përsërisë ato përsëri, dhe përsëri, dhe përsëri, lloj në një mënyrë looping. Sepse ju nuk jeni do të ketë luks, si Jennifer bëri në fillim, për të të ketë vetëm një bandë e tërë e VJ dhe të thonë, hmm, në qoftë se ky numër parë është 4, më lejoni të kërcejnë gjatë gjithë rrugës deri në fund. Ooh, në qoftë se numri është shumë i madh, më lejoni të lëvizë në mënyrë arbitrare mbrapa në elementin e dytë. Ju do të të gjeni se ai po ndodh të jetë një shumë vështirë të formalizojnë atë që ne njerëzit marrë për të dhënë, si shumë të arsyeshme heuristics, por një kompjuter është vetëm do të bëni atë që ju them se për të bërë. 

Tani kjo e ka shumë të interesante Implikimet. Ky grafik është lloj i menduar të lloj trullos vizualisht, por njoftimi, ku është vijë e drejtë në këtë grafik? Ku është grafik linear që ne e quajmë n? E pra, kjo është lloj i drejt fund e kësaj tabloje, e drejtë? Pra, të gjithë ne kemi bërë është ne kemi lloj i zoomed jashtë boshtit x dhe y-aks për të përpiqen për të marrë një kuptim të asaj lloje të tjera të kthesa të duken si. 

Dhe specifikat e matematike Shprehjet sot nuk do të marrë parasysh në mënyrë shumë, por të vëreni se ka një shumë të Algoritmet që janë shumë më e keqe sesa diçka që është lineare. Në të vërtetë, n cubed duket goxha keq. 2 deri n duket goxha keq. n katror duket goxha keq. Dhe ne do të shohim se çfarë disa nga ata mund të jetë në realitet sot. Dhe log n nuk ndihet si e keqe, por mirë se N është log bazë 2 n. Por ju e dini, kjo do të kishte qenë edhe më më të mahnitshme në qoftë se Jennifer, ose në qoftë se ne, që javën e parë, kishte dalë me diçka që është log log e n. 

Pra, me fjalë të tjera, ekziston kjo tërësi Gama e zgjidhjeve të mundshme për probleme, por edhe këtu, njoftimi çfarë do të ndodhë. Kur unë zoom out, cila nga këto kthesa do të provojë të jetë absolute më e keqja nga ato në ekran tani? Pra, n cubed duket goxha e e keqe në këtë moment. Por nëse ne zoom out dhe të shohim më shumë x dhe y-aks, i cili do të dominojnë në fund të fundit? Pra, ajo në fakt rezulton out se, 2 për të n, dhe ju mund të kuptoj këtë jashtë vetëm nga mbylljen në disa gjithnjë e më i madh numrat, dhe ju do të shihni se 2 për të n, me të vërtetë, merr të mëdha shumë më të shpejtë. Nëse ne me të vërtetë zoom out, një 2 për algorithm n absolutisht sucks. Unë do të thotë kjo është duke shkuar për të marrë fare pak kohe për kompjuter për të dybek përmes. 

Por ju do të shihni kalimin e kohës, veçanërisht me grupe të ardhmen problemore dhe madje Projektet përfundimtare, është të dhënat tuaja set merr të mëdha, të gjithë të drejtë? Edhe në versionin e parë të Facebook, si numri i miqve, dhe të Numri i përdoruesve të regjistruar mori të mëdha, ju mund të lloj i telefonit atë në dhe zbatojë diçka me kërkim linear, ose një klasifikim shumë e thjeshtë algorithm, siç ne do të shohim sot. Ju duhet të filloni të menduarit e vështirë dhe më e vështirë në lidhje me këto probleme. Dhe llojet e problemeve vende të si Facebook, dhe Google, dhe Microsoft, dhe të tjerët punojnë në është pikërisht këto lloj lloj madhe të të dhënave të pyetjeve gjithnjë këto ditë. 

Dakord. Pra, suksesin Jennifer në që të dytë algorithm, sinqerisht, ajo e bëri amazingly edhe hera e parë, por le shkruaj atë si fat kështu që ne mund të bëjë këtë pikë. Në rastin e dytë, ajo leveraged një algorithm se përsëritet përsëri dhe të përsëri, por ajo mori për të dhënë një Supozimi i sigurt se ne të lejuara saj, por ajo shfrytëzuar disa detaje hera e dytë që ajo nuk kishte hera e parë. Cila ishte ajo? 

Kjo listë u renditura. Pra, sa më shpejt që lista u renditura, ne pohojnë se Jennifer ishte në gjendje të bëjë rrënjësisht të mirë. 7 dyer, po, nuk është se e interesante, por mendoj se ne jemi 7 milion dyert. Log n është definitivisht do për të kryer shumë, shumë më të shpejtë në afat të gjatë. Por ajo duhet të kishte Dyert e renditura për të. Tani, unë mora guximin për të bërë që paraprakisht në ekranin e kompjuterit këtu, por mendoj se Jennifer kishte të bënte se veten? Supozoni se dyert në fjalë Të dhënat përfaqësuar në një bazë të dhënash, ose miqtë e regjistruara për Facebook, ose ndonjë web faqe në internet që faqet e internetit të ndryshme mund të kenë nevojë tek indeksi ose kërkoni mbi. 

Supozoni se ju kishte vetëm një të dhënat e papërpunuara vendosur dhe ajo është lënë për ju, ose për të Jennifer për të bërë këtë klasifikim? Kjo, përkundrazi, kërkon që ne të përgjigjem pyetja, mirë, sa kohë do të marrë Jennifer, apo edhe mua, për të zgjidhur ato numra paraprakisht në mënyrë që ajo të mund të përfitojnë nga kjo? E drejta? Sepse implikimi, natyrisht, është në qoftë se ajo merr mua një kohë mjaft për të zgjidhur numrat, të cilët dreq kujdeset që t'ju mund të gjeni një numër si 50 në mënyrë të shpejtë, si në rastin e Jennifer, në qoftë se ne kemi më shumë se përshkuar sasinë e kohës totale ajo mori nga zgjidhja gjërat paraprakisht? 

Pra, le të shohim nëse ne nuk mund të pikturuar foton këtu. Unë kam stres një bandë e tërë më shumë topa, në qoftë se ndihmon thyejnë akullin këtu. Dhe në qoftë se ju nuk do mend, ne nevojë për shtatë vullnetari - on, OK. Wow. Pra, ne nuk kemi për të shpenzuar on llambat tavolinë, ajo duket. Dakord. Pra, si në lidhje me jush dy në frontin. How about ju dy guys në mbrapa. Pra, kjo është katër. Si për ju në frontin pesë, gjashtë dhe shtatë. E drejta atje. Pershendetje ckemi është vënë nga ju, kështu që ju të merrni çmimin. 

Dakord. Come on up. Dhe pse nuk kemi ju djema vijnë më gjatë këtu. Unë jam duke shkuar për të ju jap çdo numër një. Dhe të shkojnë përpara dhe të koordinojë veten identike me atë që është përshkruar në ekran. 

[Mbivendosje VOICES] 

DAVID J. Malan: oop, sorry. Bug. Dakord. E pra, këtu ne do të shkojmë. Numri pesë. Numri gjashtë. Njëri, dy, tre, katër, pesë, gjashtë, shtatë. Oh, kjo është e vështirë. 

KRYETARI 2: Unë do të merrni vetëm një -. 

DAVID J. Malan: marrëveshje të mirë. Dakord. Faleminderit për pjesëmarrjen. 

[Duartrokitje] 

OK. Dakord. Pra, ne kemi katër, dy, gjashtë, një, tre, shtatë, pesë. Perfect kështu që ne kemi shtatë vullnetarë këtu të cilët janë të barabartë në gjerësi të array se ne jemi duke luajtur me herët. Dhe unë zgjodha shtatë për arsye se do të jetë vetëm i përshtatshëm në një grimë pak. Dhe unë jam duke shkuar për të propozojë parë që kemi zgjidhur këto shtatë vullnetarë. Nëse ju do të doja, së pari, për të thënë hello pse. Që nga viti kjo është duke duke shkuar për të jetë një minuta çuditshme disa. Prezantoni veten tuaj. 

Grace: Hi, unë jam i Grace. Unë jam një i paedukuar mjaft në Leverett House. 

Branson: Hi. Unë jam Branson. Unë jam një studente në bashkoj. 

Gabe: Hi. Unë jam Gabe. Unë jam një junior në Cabot. 

Neil: Unë jam Neil. Unë jam një studente në Matthews. 

JASON: Unë jam Jason. Unë jam një studente në Greenough. 

Mike: Unë jam Mike. Unë jam një studente në Grays. 

Jess: Unë jam Jess. Unë jam një i paedukuar mjaft në Leverett. 

DAVID J. Malan: Excellent. Dakord. E pra, ju falenderoj për të gjithë e tona vullnetarët këtu deri tani. Dhe sfida në dorë tani është duke shkuar të jetë për të zgjidhur nga këta njerëz, por pastaj ne jemi duke shkuar për të duhet të mendojnë pak vështirë se sa efikase ne fakt renditura ato. Pra, le të parë të provoni këtë. Ju djema mund të shikoni numrat e njëri-tjetrit vetëm duke e vendosur rreth qoshet. Shkoni përpara dhe për të marrë disa sekonda, dhe lloj veten nga më i vogli në la të madh në të djathtë. Go. 

OK. Good. Kjo ishte e shpejtë me të vërtetë i mallkuar. Tani dikush këtu, çfarë ishte algorithm se këta djema aplikuar? 

Kryetari 1: Pak tek më i madhi. 

DAVID J. Malan: OK. Pak tek më i madh është me të vërtetë lloj i objektive, por unë nuk jam i sigurt se kjo është me të vërtetë një algoritmi. Paktën për të më i madh nuk sexsy do tregoni mua hap-pas-hapi se çfarë të bëni. Po? 

Kryetari 1: [padëgjueshme] 

DAVID J. Malan: OK. Pra, nëse ju shihni një person më i vogël se numrin tuaj, pastaj të shkojë në drejta e tyre. Kështu që tani po bëhet më ekspresive, më shumë si një algoritmi, sepse ju mund të them se, në qoftë se kjo, atëherë kjo. Pra, ne kemi disa lloj konstrukt i kushtëzuar. Dhe këta njerëz dukej për të bërë që disa herë, për shkak se disa prej jush lëvizur një grimë e nje distance. Pra, nuk ishte me sa duket një lloj looping ndodh në mendjet e tyre. 

Por le të përpiqemi për të formalizuar këtë. Nëse ju djema mund të ktheni mbrapa në këtë aranzhman. Le të shohim nëse ne nuk mund të zyrtarizojë këtë një bit, dhe pastaj pyesni pyetje, vetëm sa efikas është kjo? Sigurisht, kur ne e bëjmë këtë më ngadalë, ajo do të ndjehen si të mirë të një algoritëm, por le të shohim nëse ne mund të vënë gishtat tonë në hapat e sakta. 

Pra, ju dy djemtë janë katër dhe dy. Ose ju qëllim të sakta ose të pasakta? Natyrisht pasaktë. Pra, ne swapped. Tani unë jam duke shkuar për të lëvizur anash këtu dhe thonë, katër në gjashtë. Jeni të sakta ose të pasakta? 

Gabe: korrekte. 

DAVID J. Malan: korrekte. Gjashtë dhe një? Nope. Swap. Pra, kjo është dy këmbime. Gjashtë dhe tre? Nope. Swap. Gjashtë dhe shtatë? Duket e mirë. Shtatë dhe pesë? 

Jess: [padëgjueshme] 

DAVID J. Malan: OK, të bie në ujdi. Dhe të renditura. Dakord. Pra, nuk është e qartë, e drejtë? Pra, nuk ishte më shumë në vazhdim e sipër. Por, në të vërtetë, këta njerëz, madje edhe vetëm instinktivisht. mbajtur në lëvizje. Ata nuk ndalet vetëm, pasi ata korrigjuar një problem. Pra. Në të vërtetë, unë jam do të ketë për të bërë të njëjtën gjë. Unë jam do të keni për të zgjidhur e pasme Rewind në fillim të këtij problemi, ose fillimi i këtij grup të njerëzit, le të fillojë duke i quajtur ato. 

Dhe tani çfarë duhet algoritmi im on së pasimi të së dytë jenë? 

Kryetari 1: E njëjta gjë. 

DAVID J. Malan: E njëjta gjë. Dhe kjo, unë jam duke filluar të pëlqen, e drejtë? Sa më shpejt si ju mund të gjeni veten tuaj duke bërë të njëjtën gjë përsëri dhe përsëri, kjo është duke u bërë më shumë si një algoritmi, dhe me pak instinkti njerëzor. 

Deri tani, këtu ne do të shkojmë përsëri. Dy dhe katër? Jo. Katër dhe një? Ah, nuk ishte me të vërtetë disa të punojë ende për t'u bërë. Për dhe tre? Good. Katër dhe gjashtë? Gjashtë dhe pesë? Gjashtë dhe shtatë? OK, tani, bëhet. OK, nr. Unë kam për të shkuar mbrapa. 

Deri tani, përsëri, ne jemi duke e bërë këtë pak më shumë qëllimisht. Dhe tani, atje është vetëm një truri ekzekutimin e këtij algoritmi. Një CPU, nëse ju do. Dhe sinqerisht, kjo është vetmi burim ne jemi duke shkuar për të kenë qasje në. Dhe dikur ne do të shkojnë kthehemi në një tastierë dhe të ketë diçka si C në tonë Shkatërrimi, ne jemi duke vetëm shkruarit e një program të që mund të bëjë një gjë në një kohë. Ndërsa, këta njerëz një moment më parë, ne leveraged brainpower e tyre kolektive si ju djema bëri në zero javë. Pra, le të vazhdojmë të bëjmë këtë. 

Dy dhe një. Dy dhe tre. Tre dhe katër. Katër dhe pesë. Pesë dhe gjashtë. Gjashtë dhe shtatë. Done? Kështu që unë jam, por më lejoni të luajë avokati i djallit. A kam, lloj i kompjuterit i cili vetëm e bëri një pasim nëpërmjet këtij array së njerëzit, e dinë se unë jam bërë? 

Gjuha 1: Jo 

DAVID J. Malan: Pra, pse? Çfarë do që unë duhet të bëni në mënyrë që të konkludojmë decidivisht se unë jam bërë? Ndoshta një të kalojë më shumë. E drejta? Sepse të gjithë unë e di nga se paraardhëse kalojë është se unë korrigjuar një gabim. Që do të thotë, ndoshta ka ende të një tjetër gabim se kam nevojë për të korrigjuar. Kështu që unë mund vetëm të jetë i sigurt nga rewinding, dhe pastaj duke kontrolluar, një në dy, dy dhe tre, tre dhe katër, katër dhe pesë, pesë dhe gjashtë, gjashtë dhe shtatë. OK, tani unë nuk bëri asnjë punë. 

Unë me siguri mund të mbani mend se unë nuk bëri asnjë punojnë me diçka si një variabël, si një int. Quajeni këmbime, dhe në qoftë se këmbime është 0 herë unë merrni këtu, dhe ajo filloi në 0, atëherë Unë vetëm do të jetë i trashë për të mbajtur vazhdim e sipër mbrapa dhe me radhë, duke kontrolluar përsëri, dhe përsëri, dhe përsëri, e drejtë? Sepse ju merrni mbërthyer në disa lloj lak pafund. Pra, sa më shpejt që ka 0 këmbime, ne mund të pretendojnë se kjo Algorithm është me të vërtetë e plotë. 

Tani, le të vënë një emër për këtë. Algoritmi që unë propozoj ne vetëm implementuar është diçka që quhet flluskë lloj, i njohur si i tillë në kuptimin që numrat që janë lloji më i madh i flluskë rrugën e tyre deri në majë, ose deri tek fundi i vektorit të numrave. Por sa efikase ishte kjo algoritmi? Sa hapa kam fizikisht duhet të të marrë, për shembull, për të zgjidhur këto shtatë njerëzit? 

Katër deri në pesë? OK, shumë është në fund të fundit do të jetë përgjigja. Por edhe atëherë, numër specifik nuk është aq interesante. Le të përgjithësojnë atë si n. Pra, nëse unë e kishte n popullin e up këtu, dhe ata ishin, lloj, në mënyrë të rastit në filluar, në atë mënyrë origjinale. E pra, sa hapa nuk kam për të marrë mbi kalimin e parë? Ajo ishte një, dy, tre, katër, pesë, gjashtë, dhe ata janë shtatë njerëz, kështu që kjo është shtatë, gjashtë -, kështu që është n minus një hapa herën e parë. 

Tani, sa hapa nuk kam për të marrë kur unë rewound? E pra, ne në fakt mund të dyfishtë se në qoftë se ne me të vërtetë të kërkuar për të, por tani për tani, unë jam vetëm do të them, të gjithë të drejtë, një tjetër n minus 1. Pra, minus n 1 është duke duke shkuar për të të merrni i bezdisshëm për të mbajtur gjurmët e, kështu që le të vetëm raundin deri pak. Pra 2N hapa. Pra 14 hapa, të japë ose të marrë. 

Sa herë kam marrë një hap herën tjetër? E pra, kjo është 3n. me të vërtetë. Dhe tani, në rastin më të keq, për shembull, sa herë do të kam shkuar mbrapa dhe me radhë, mbrapa dhe me radhë, ekzekutimin e këtij algoritmi, shkëmbejnë njerëzit në çdo të kalojë, afërsisht? Është n fakt katror, ​​e drejtë? 

Sepse në rastin më të keq, ju mund të lloj të mendojnë në lidhje me këtë intuitive, edhe pse ajo mund të marrë pak pak kohë të zhytet in Në rastin më të keq, çfarë do këto shtatë njerëz kanë shikuar si, në Kushtet e marrëveshjes të numrit të tyre? Plotësisht prapa, të drejtë? Dhe vetëm për të simuluar se, çfarë ishte emri juaj përsëri? 

MIKE: Mike. 

DAVID J. Malan: Mike? OK, Mike, ju mund të bashkohen vetëm mbi mua këtu për vetëm një të dytë? Në fakt, nuk ka. Na vjen keq Mike, Rewind le. Cili është emri juaj përsëri? 

Neil: Neil. 

DAVID J. Malan: Neil. OK, Neil, ju vijnë me mua, në qoftë se ju nuk do mend. Kështu që unë jam duke shkuar për të propozojnë, vetëm për Thjeshtësia, se Neil është tani në e tij Rasti më i keq të jetë e mundur. Por kujtojmë se si unë zbatuar algorithm im. Unë jam duke e krahasuar, duke e krahasuar, duke e krahasuar, krahasuar, duke e krahasuar, oh. Tani këta janë jashtë e rendit, kështu që unë të rregulluar. Pra, ju djema bie në ujdi. Por e konsiderojnë tani, sa më larg nuk Neil duhet të shkojnë? Është n afërsisht. Ju e dini, kjo nuk është n fakt. Është si, n minus 1, por unë jam marrë udhë mërzitur mbajtja e pak numër, kështu që le të vetëm e quajti atë n. 

Pra, nëse Neil lëviz një hap maksimalisht çdo kohë, dhe për të lëvizur Neil një hap, Unë kam për të bërë këtë abone të vërtetë të lodhshme mbrapa dhe me radhë, kjo është afërsisht bërë këtë, n hapa, një total prej herë n, sepse ajo do të marrë mua se hapa shumë për të marrë të Neil të gjithë mënyrë për të, ku ai i takon. Le të vetëm të gjithë të tjerët në qoftë se ju djema ishin të gjithë mis-urdhëroi si mirë. 

Pra, le ta quajmë lloj flluskë n squared. Ora drejtimin e këtij algoritmi, Performanca e këtij algoritmi, efikasiteti i këtij algoritmi, ne do të vetëm të përshkruaj më shumë përgjithësisht si n katror. Cila është e bukur, sepse unë mund të bëj Shembulli i njëjtë me tetë njerëzve, nëntë njerëz, një milion njerëz, dhe se Përgjigja nuk do të ndryshojë. 

Pra, nëse ju djema nuk do mend, le të rivendosni ju ku ju keni filluar. Dhe le të përpiqemi dy qasjet e tjera dhe të shohim nëse ne nuk mund të bëjmë rrënjësisht mirë se kjo. Pra, kjo kohë, unë jam duke shkuar për të propozojë një lloj algoritmi të ndryshme. Kjo ishte shumë i zgjuar prej nesh hera e fundit, dhe ju djema ishin të drejtë të ketë Instinktet e pasur të drejtën e vetëm lloji të shkëmbejnë pairwise. Por në qoftë se unë me të vërtetë donte të qasen thjesht, dhe qëllimi im është që të lëvizë të gjithë numrat e vegjël në këtë mënyrë, dhe shtyjë të gjithë numrat e mëdha që mënyrë, pse nuk Unë vetëm të bëjë që në më naive mënyra e mundur dhe të shohim nëse unë mund të bëjë më mirë se ajo ishte një mjaft algorithm komplekse? 

Pra, le të shohim. Katër është një numër shumë i vogël, kështu që unë jam duke shkuar për të largohet nga ju atje moment. Ooh, numri dy është edhe më mirë. Pra, mund të ju vetëm hap përpara për një çast? Kjo është e aktualisht numerimet im më i vogël Kandidati, dhe unë jam duke shkuar për të kujtuar se me, si, një ndryshore. Por unë jam duke shkuar për të mbajtur të checking. A ka dikush të cilit numër është i vogël? Gjashtë, nr. Oh, nuk Neil përsëri. 

Kështu që unë jam duke shkuar për të nxitur ju prapa lloj konceptualisht. Neil do të vijë përpara. Dhe tani, variabli që unë jam duke përdorur për të mbajnë gjurmët e të cilët ka më të vogël numër është përditësuar të përmbajë Vendndodhja Neil. E pra, le të shohim. Tre, shtatë, pesë. OK, unë e di Neil ishte më i vogël. Cila është gjëja më e thjeshtë për mua të bëjmë tani? Unë nuk jam duke shkuar për të humbim kohë e mia me vetëm bubbling Neil vend një të majtë. Pse nuk mundem të vetëm vënë Neil ku ai takon, i cili eshte i kursit ku? 

Të gjitha mënyra në fillim. Pra, Neil, eja me mua. Dhe çfarë ishte emri juaj përsëri? 

GRACE: Grace. 

DAVID J. Malan: Grace. OK. Pra Grace, për fat të keq, ju jeni lloj në rrugë. Deri sa nuk kemi zgjidhur këtë problem? E drejta? Në qoftë se kjo është një koleksion, ka vetëm shtatë vende. Kujtojnë se, me Rob, kemi biseduar rreth shpallja e moshave, dhe kemi pasur vetëm një numër i caktuar i moshave? Ideja e njëjtë këtu. Ne kemi vetëm një numër i caktuar i ints. Grace është lloj i në tonë mënyrë, kështu që si mund ne të rregullojmë? 

Mënyra më e thjeshtë është si, Grace, sorry. Ju jeni do të keni për të shkuar mbi atje kështu që ne mund të bëjë dhomë. Tani, në qoftë se ju mendoni për këtë, ndoshta ne vetëm e bëri problemin edhe më keq. Dhe ndoshta ne e bëmë, sepse çka nëse Grace ishin në vendin e duhur? Por ne e dimë se ajo nuk është, sepse përndryshe, ajo do të kishte qenë këmbë përpara në vend të Neil në këtë kohë, e drejtë? Ne tashmë e kontrolluar numrin e saj jashtë. 

Dakord. Deri tani, Neil është në vendin e duhur, dhe Unë mund të bëjë një optimization lehtë. Për minutë ardhshëm, unë jam duke shkuar për të injorojë Neil gjithë së bashku, në mënyrë që të mos humbim kohën e tij, apo aksidentalisht të bie në ujdi atë në vendin e gabuar. Kështu që tani, si mund unë të gjeni e ardhshëm element që është më i vogël? Dy. Kjo është një numër mjaft të mirë, në qoftë se ju doni të hap përpara dhe Unë do të kujtoj juve. Gjashtë, asnjë të mirë. Katër, tre, shtatë, pesë, asnjë të mirë. Pra më lejoni të lëvizë ju për të vendi juaj drejtë. Dhe ne vetëm mori me fat këtë kohë. 

Tani, unë jam duke shkuar për të injorojë këto dy djemtë, dhe tani të bëjë një më shumë kalojnë nëpër këtë. Gjashtë, se një numër shumë i vogël. Come on përpara. Oh, sorry. Numri i Grace është më e mirë, kështu hap më përpara. Katër. Na vjen keq, Grace. Kthehu mbrapa përsëri. Numri tre është më e mirë. Shtatë. Pesë. Dhe tani çfarë është emri juaj përsëri? 

JASON: Jason. 

DAVID J. Malan: Jason. Pra, Jason është tani më i vogël Elementi i kam zgjedhur. Ku është ai që do të shkojnë? Pra, ku gjashtë është. Dhe emri i yt është përsëri? 

Gabe: Gabe. 

DAVID J. Malan: Gabe. Gabe është në rrugë të drejtë. Cila është gjëja më e lehtë për të bërë? Swap këto dy djem dhe vazhdojnë. Pra, tani le të shohim. Kush është më i vogël? Katër. Më lejoni vetëm lloj të mashtrojnë. Pesë do të jetë më i vogël. Unë gjej ardhshëm, nëse ju doni të hap përpara, çfarë duhet të bëj me këta djema, me Gabe? Swap përsëri. Deri tani, ende pak nga e rendit. Kam gjetur Gabe të jetë më i vogël, kështu që Unë pop atë jashtë, lëvizin you guys gjatë. Dhe bëhet. 

Pra, përgjigja është e njëjtë. Rezultati përfundimtar është i njëjtë. Cila nga këto dy algoritme është më e mirë? E dyta, kam dëgjuar. Pse? 

Kryetari 3: Është n etapat [padëgjueshme]. 

DAVID J. Malan: Është hapa n më së shumti. Interesting. Pra, është ajo edhe pse? Pra, si nuk kam gjetur Elementi më i vogël? Sa shumë Hapat e nuk kam keni për të marrë gjeni elementin më të vogël? Unë kisha një vështrim të gjithë rrugën në fund, e drejtë? Sepse në këtë rast më të keq, çfarë nëse Neil ishin mbi këtu? Pra, vetëm gjetur elementin më të vogël merr mua n hapa, ose N minus 1. Por, OK. Pra, fix Neil. Mos harroni se, një minutë apo të kështu me më parë. 

Por si nuk kam gjetur tjetër Elementi më i vogël? Është n minus 1, ose n minus 2 vërtetë, nga numri i hapave. Pra, OK. Kështu që unë kam n minus 2. Dakord. Kështu që ndihet pak më mirë. Dakord. Sa hapa herën tjetër për të gjetur numrin tre? Pra, n minus 4. Pra, kjo është në rënie, një më pak hap në çdo përsëritje. Pra, kjo do të ndjehen më mirë, e drejtë? Nëse herën e fundit ajo ishte afërsisht n herë n, këtë herë kjo është n minus 1, plus n minus 2, plus n minus 3, plus n minus 4, dot, dot, dot. Por në qoftë se ju kujtohet nga shkolla tuaj të lartë Tekstet, mashtrojnë pak fletë në pjesën e pasme që ka formula, nëse ju të shtoni deri këtë seri të numrave, çfarë është numri total i hapave do të jetë që unë të marrë këtu? 

Kjo është një nga ata, si, n minus 1, herë n, ndarë nga 2. Pra më lejoni të shohim nëse unë mund të tërheqë kjo për vetëm një moment. Dhe përsëri, unë jam natyrë e grumbullimit disa Numrat e vetëm për të mbajtur jetën tonë të thjeshtë, por si unë kujtoj, kjo është diçka si në qoftë se Bëj n minus 1 gjëra, pastaj n minus 2, pastaj n minus 3, kjo është afërsisht diçka si kjo mbi 2, dhe në qoftë se unë shumëfishohen këtë, se është në fakt katror n. Kjo nuk është ndjenjë shumë e mirë. n minus n mbi 2. 

Por këtu është gjë. Në kompjuterike shkencës, kur problemet të fillojë të marrë interesant është kur n merr me të vërtetë e madhe. Dhe kur n merr me të vërtetë e madhe, e cila i këto vlera do të dominojë të gjithë e të tjerëve? Kjo është lloj i n katror, ​​e drejtë? Po, pjestuar me 2 është shumë e mirë. Por nëse ju jeni duke folur për miliarda nga copa të të dhënave, apo triliona pjesë e të dhënave, OK, kështu që ju jeni dy herë më të shpejtë. Por që me të vërtetë kujdeset në qoftë se numri i madh, në qoftë se ky faktor është ajo që merr më të mëdha. Dhe sigurisht, kjo e bën më të një dallim se këtë djalë. Pra, edhe pse ju djema jeni të drejtë, algorithm e dytë, ne do të thërrasë atë lloj përzgjedhjes, eshte, ne te botës reale, nje pak më të shpejtë të mundshme, sepse unë jam duke marrë më pak dhe më pak hapat që secila kohë. 

Kjo nuk është e me të vërtetë rrënjësisht më të shpejtë. Sepse në qoftë se ne të vërtetë të luajë këtë për Vlerat e mëdha të N, në fund të ditë, për n mjaft e madhe, ajo është ende do të ndiheni goxha i ngadalshëm. E pra, më lejoni të marrë një Pasimi fundit në atë. Kjo është ajo që unë do të thërrasë lloj përzgjedhje. Ju Mund të djema ricilësuar veten tuaj për herë të fundit? Dhe në këtë rast të fundit, unë jam duke shkuar të propozojë diçka quajtur lloj futje. Lloj futje të qenit, konceptualisht, pak më ndryshe. 

Në vend se të shkuar mbrapa dhe me radhë dhe zgjedhjen elementin më të vogël, unë jam vetëm do të merret me secilin nga këto djema si unë hasin ata, dhe futur ato në vendin e tyre të saktë. Pra, unë jam vetëm duke shkuar për të filluar me Grace, dhe unë shoh se ajo është numër katër. Ku ka numër katër i përkasin? Unë nuk kanë filluar sorting asgjë, kështu Grace merr për të qëndruar të drejtë atje. Dhe tani unë jam duke shkuar për të kërkuar, në qoftë se ju mund të të marrë një hap për të drejtën tuaj, kjo lista ime e renditura, kjo është e mia Lista unsorted mbetur. Deri tani unë jam duke shkuar për të vazhduar më tej, dhe çfarë është emri juaj përsëri? 

Branson: Branson. 

DAVID J. Malan: Branson. Pra Branson është numri dy. Kështu që unë jam duke shkuar për të marrë ju për një moment. Dhe tani, ku nuk ju përkasin në këtë grup? Pra, për të të drejtën e të Hirit. Pra, përsëri, ne jemi lloj i bërë Grace bëjë shumë punë këtu. Ku nuk kemi vënë ju? Pra, ne jemi duke shkuar për rrëshqitje ju u largua, dhe futur Branson atje. Por tani unë pretendojnë se ju djema janë bërë. Por vini re, unë nuk jam duke përdorur hapësirë ​​ekstra. Është ende e 2 elemente këtu, 5 mbi këtu. Madhësia gjithsej array është 7, kështu që unë jam jo mashtrimit, të gjithë të drejtë? 

Pra, tani ne kemi, me Gabe këtu, numër gjashtë, ku nuk ju takon? Ju mori me fat përsëri. Pra, ju merrni për të qëndruar të drejtë atje. Vetëm të marrë një hap të lehtë për të drejtën vetëm për të bëjë të qartë se ju jeni duke renditura. Dhe tani ne kemi Neil përsëri, numrin e një, ku shkoni? Dhe tani është ajo ku ne do të fillojnë të shohin se ky algoritëm, edhe pse më parë shikim, ndihet goxha i zgjuar, watch çfarë është gati të ndodhë. Nëse ju mund të hap përpara. 

Ku duam të vënë Neil? Pra padyshim këtu, kështu që se si nuk kemi të merrni Neil atje? Le ta bëjmë këtë hap-pas-hapi. Gabe, ku ju duhet të shkoni? Yep, kështu që të marrë një hap të madh, apo dy gjysmë-hapa për të bërë një hap mbi atje. Grace, ku ju shkoni? Good. Pra, një hap tjetër. Dhe së fundi, Branson? Një hap tjetër. Dhe tani ne mund të vënë Neil në vend. 

Deri tani, të vazhdojë këtë logjikë. Edhe pse ne nuk jemi zhvendosur Neil mbi, dhe mbi, dhe mbi, për të vënë atë ku ai shkon, ne rastin keq, numri i ardhshëm ne mund të hasni mund të të jetë numri, të themi, ka pasur një numër zero, atëherë ne jemi duke shkuar për të zhvendosur të gjithë këta djema. Supozoni se ka një numër, negative një, atëherë ne duhet të zhvendoset të gjitha këto guys. Pra, ne jemi me të vërtetë vetëm lloji i Flipping Problemi rreth, të tilla që ne jemi transferimin e shpenzimeve nga Procesi i përzgjedhjes kështu shtënie proces, i tillë që ju djema kishte vetëm për të lëvizur diçka afërsisht n minus Numri i hapave. Dhe se numri i hapave është vetëm do për të rritur si unë zgjidhni më shumë numra, në qoftë se unë kam për të mbajtur shoving ju djema mbrapa, dhe prapa, dhe mbrapa. 

Pra, gjëja e trishtuar tani është të gjitha këto algoritme janë n katror. Le të shkojnë përpara dhe në sajë të këtyre djema, dhe kujtoj këto pak ndryshe. Very well done. 

[Duartrokitje] 

Dakord. Nuk ju shkoni. Faleminderit për - 

Branson: [padëgjueshme] mbajnë numrat. 

DAVID J. Malan: Jo, ju mund të mbajnë numrat si. Dakord. Nicely done. Dakord. Pra, le të shohim nëse ne tani nuk mund të përmblidhni më shpejt dhe më me sy, saktësisht se çfarë ka ndodhur vetëm këtu si më poshtë. Unë jam duke shkuar për të shkuar përpara dhe tërheq lart Firefox. Ne do të lidhin këtë demonstratë në faqen e internetit Kursin së. Java është një pak i bezdisshëm për të marrë të punës në disa shfletues këto ditë. Pra, nëse ju bëni luajë me këtë në shtëpi, kuptojnë që ju mund të kenë nevojë të përdorni Firefox për të marrë atë që punojnë. Dhe çfarë unë jam duke duke shkuar për të bëjë me këtë demonstrim është në vijim. 

Në fund, unë kam një bandë e tërë e options menu, duke përfshirë një fillim dhe një të ndalet button. Gjithashtu, si një mënjanë, nuk duket të jetë një bug në këto programe, ku ju nuk mund të vërtetë shohim fillimin ose të ndaluar button nëse ju mbani Komanda ose ALT plus dhe zoom në, e cila interesant ju tregon butonat më shumë. Pra, vetëm FYI, nëse ju luani me këtë në shtëpi. Tani unë jam duke shkuar për të klikoni Start në vetëm një moment, pasi specifikuar një vonesë prej, si, 200 milisekonda këtu, vetëm kështu që ne mund të shohim se çfarë ndodh. 

Kështu që unë pretendojnë se kjo është një vizualizimi i algoritmin e parë këta bënë, lloj flluskë, ku ne swapped njerëz palë-të mençura. Insajt çelësi për këtë vizualizimi është se lartësia e hekurave paraqet madhësinë e numrit. Pra shtatlartë bar, madhe numrin. Shorter bar, më i vogël numri. Dhe në qoftë se ju të vini re, ne jemi duke shkuar nëpër përsëritje e parë e këtij algoritmi, shkëmbejnë numrat e mëdha dhe të vogla, në mënyrë që numër i vogël vjen e para dhe Numri i madh shkon në të djathtë. 

Dhe sa më shpejt që ne të merrni në fund të array e numrave shumë më shumë se shtatë, ne jemi duke shkuar për të shkuar përsëri në fillim. Dhe parashikojnë këtë. Më shumë majtas, se djalë i vogël po ndodh për të bie në ujdi për të në anën, dhe kjo përsërit proces. Tani kjo vizualizimi shpejt merr mërzitshëm, kështu që më lejoni të shkoj përpara dhe të ndaluar ajo, të ndryshojë diçka shumë vonesë të shpejtë vetëm për të marrë tani, një të ndjehen për ky algoritëm. 

Pra, edhe pse unë kam ankorua atë, kjo është si përmirësimin procesor tim, blerja e një kompjuter të ri. Unë nuk kam ndryshuar rrënjësisht mia algorithm, por ju me të vërtetë mund të shihni më shumë në mënyrë të qartë sesa me njerëzit, se i madh numra janë bubbling deri në majë, dhe numrat e vegjël janë bubbling poshtë në fund. Dhe tani kjo gjë renditura këtu. Dhe siç një mënjanë, në sheshet, nuk ka vetëm disa llogarimbajtje atje për të të ju ndihmojë të llogarisin se sa krahasime, apo sa këmbime kanë në fakt është bërë. 

E pra, le të provoni njërin prej të tjerët e pamë. Më lejoni të klikoni mbi lloj flluskë këtu, dhe më lejoni të zgjedhin, dhe kjo faqe e tërë web është një buggy pak. Le të pranojnë rrezikun dhe drejtuar atë përsëri. Ka të shkojmë. Pra, le të bëjmë lloj përzgjedhjes. Unë nuk e di pse menu duket mbi atje. Le të zoom në për të rregullojmë se bug, të ndryshojë kjo në 50. Ah, le të bëjë në fakt se shumë më të shpejtë. Pesë milliseconds apo më shumë, dhe të fillojnë. 

Pra, kjo është lloj përzgjedhje. Pra, përsëri, mendoj në lidhje me atë që ne bëri me njerëzit këtu. Ne shkuam nëpër rrjet dhe përzgjedhur element më i vogël përsëri, dhe përsëri, dhe përsëri. Tani unë pretendojnë se ishte ende mjaft e keqe. Ajo ishte n ende katror, ​​të japë ose të marrë, por ajo ishte, në botën e vërtetë, pak a më shpejt, sepse isha me të vërtetë duke marrë pak më pak hapat që secila kohë. Por ne jemi vetëm duke folur se çfarë? Ndoshta 40 ose kështu që bare këtu? Ne nuk jemi duke folur 40 milion. Pra, kjo nuk është krejtësisht e qartë për mua se ishte me të vërtetë një fitim të rëndësishëm. 

Më lejoni tani të shkojnë prapa dhe të ndryshojë në tonë algorithm e tretë, e cila ishte zgjedhur lloj futje. Dhe tani ajo është me të vërtetë buggy sepse menu me të vërtetë nuk duhet të jetë atje poshtë. Pra, tani ne do të lëviz mbrapa deri këtu dhe të fillojnë këtë algoritëm. Bërtas, të fillojë dhe të ndaluar. Pra, ky lloj ka një model të bukur për të atë, së cilës ne jeni të përsëri futur humanet, ose ne këtë rast, bare në vendndodhjen e tyre të përshtatshme. Dhe kjo është bërë tashmë para Unë u kthye. Por kjo, gjithashtu, në teori, është n ende katror. 

Pra, le të shohim nëse ne nuk mund të përmbledhim këto si vijon. Unë jam duke shkuar për të shkuar përpara dhe vetëm për të dhënë na lloj i një mënyrë e zakonshme e folur në lidhje me këto gjëra, më lejoni të prezantoj vetëm një grimë e simbol këtu. Ju jeni gati për të parë diçka që quhet e madhe O, sepse ajo është fjalë për fjalë një i madh O. Dhe kjo është një mënyrë që një kompjuter shkencëtar apo një matematikan madje përdor për të përshkruar kohën running e disa algorithm. Sa hapat e bën atë të vërtetë të marrë? 

Tani unë jam duke shkuar për të vë në siklet veten me dorëshkrimit të im këtu në vetëm një moment. Por më lejoni të shkoj përpara dhe të thonë se kjo do të jetë O madh mbi këtu. Dhe më lejoni të prezantoj një tjetër simbol, një omega kapitale. Omega do të jetë e kundërta, në thelb, i madh O. patur parasysh Big O do të thotë, në rastin më të keq, sa kohë mund të disa algorithm të marrë, në termat e n, omega është duke duke shkuar për të të jetë sa kohë mund të të marrë në rastin më të mirë. Dhe ne do të shohim se çfarë ne kuptojmë me Rasti më i mirë në një moment të vetëm. 

Pra, le të fillojë diçka e thjeshtë. Më lejoni të filloj me një kërkim linear. Pra, nuk sorting. Ne do të quajmë këtë kërkim linear. Dhe tani, të bëjë pak Tabela nga kjo. Dhe tani, në rastin e kërkimit lineare, në rastin më të keq, sa hapa është ajo do të marrë mua për të gjetur një Numri i zgjedhjes arbitrare? Dhe nuk ka dyert e n totali i ose n numra totale. Rasti më i keq. Sa hapa jam unë do të duhet të të marrë për të të gjetur numrin 50 në një array i dyerve n? Dhe pse? Për shkak se ajo mund të jetë mbi të gjitha mënyrë mbi onto në fund. Pra, shumë si Jennifer hasur, numër 50 ishte e gjitha rruga e gjatë, kështu që në kërko keq rasti linear është e madhe O n, ne do të themi. 

Po në lidhje me rastin më të mirë, në qoftë se ju merrni të vërtetë me fat? Ajo është vetëm duke shkuar për të të marrë një hap, ose një numër konstant i hapa. Pra, ne do të përshkruaj se si 1. Pra, kjo është shumë e mirë. Tani çfarë nëse ne e bëmë diçka të doja kërkimin binar? Kërko Pra binar, në më të keq rast, mori sa kohë? 

[Mbivendosje VOICES] 

DAVID J. Malan: Pra, në fakt, unë dëgjuar atë në disa vende çift. Pra, kjo është në të vërtetë hyni n, të japë ose të marrë, sepse si ne e ndajnë listën në gjysmën e përsëri, dhe përsëri, dhe përsëri, ne jemi në gjendje për të gjetur, në fund të fundit, vlera, në qoftë se ajo është atje, por ka një kapur. Çfarë është supozimi se ne kemi për të marrë për të dhënë për kërkimin binar? Ajo ka të zgjidhet. Kjo nuk është e renditur, ju mund të ndarë gjë në gjysmën përsëri dhe përsëri, dhe ju mund të shkoni majtas, dhe ju mund të shkoni të drejtë, dhe ju mund të shkoni majtas dhe djathtas, por ju jeni nuk shkojnë për të gjetur elementin nëse lista nuk është e renditura, për shkak se ju mund të humbasë atë. Sepse orientues tënd, për të shkuar majtas ose djathtas do të jetë me të meta në qoftë se është me të vërtetë nuk e renditura. Pra, ka një lloj kosto fshehur për të duke përdorur diçka si kjo. 

Tani, le të shkojë në klasifikim tonë Algoritme jo kërkim - oh, në të vërtetë le të shkojë në këtë bosh. Kërko Binary në rastin më të mirë? Është gjithashtu e 1 nëse kjo ndodh vetëm që të jetë në shumë mes i vektorit, ose mesme e librit të telefonit. Tani le të bëjmë lloj flluskë. Pra, përsëri, tani ne jemi duke hyrë në llojet jo, kërkime. 

Në rastin më të keq, sa hapa bëri ne flluskë pretendimi lloj do të marrë? n katror. Kështu që unë jam duke shkuar për të nxjerrë se. Ooh, lloj shkrimi im duket edhe më keq kur është parashikuar se madhe. Dakord. Pra, kjo është n katror. Dhe në rastin më të mirë të lloj flluskë, sa hapa është ajo do të marrë? 1, I dëgjohet. 

Kryetari 1: n. 

DAVID J. Malan: n, kam dëgjuar. 

Kryetari 1: 2. 

DAVID J. Malan: 2, kam dëgjuar. A kam dëgjuar 3? Dakord. Kështu që unë kam dëgjuar 1, n, 2, por le të marr përveç pakten parë e atyre sugjerime, 1. Kjo nuk është një instinkt i keq, sepse ajo lloj i ndjek një model këtu. Por në qoftë se ajo merr vetëm 1 hap, si në Bota mund të pohoj se lista është e renditura, sepse në qoftë se unë jam i lejuar vetëm për të marrë 1 hap, sa elemente mund të unë në fakt të kontrolloni të jetë i sigurt? E pra, vetëm 1, që do të thotë nuk ka n minus 1 elemente që mund të jetë jashtë mënyrë, dhe unë jam vetëm duke shkuar në besim pas në kërkim at 1 element të se gjë është e renditura. Pra 1 po jo korrigjuar këtu. Pra minimalisht, se sa shumë nuk kam për të shikoni në? 

[Mbivendosje VOICES] 

DAVID J. Malan: n minus 1, ose vërtetë, n, për shkak se kam nevojë për të shikojmë në çdo element të sigurohemi që kjo nuk është jashtë rendit. Por përsëri, ne do lloj i valë tonë Duart në numër më të vogël dhe supozojmë se, si n merr të mëdha, ata janë jointeresant anyway. Pra, kjo është lloj flluskë. Dhe tani, le të bëjë këto dy të fundit. Lloj përzgjedhje, dhe pastaj ne do të të bëni lloj futje. Dhe pastaj ne do të fryj Juaj Mendjet me diçka shumë më mirë se të gjitha këto. Dakord. 

Cila është rasti më i keq running koha e lloj përzgjedhjes? 

Kryetari 4: n katror. 

DAVID J. Malan: n katror, ​​unë jam duke dëgjuar. Por pse n katror, ​​intuitivisht? 

Kryetari 4: Sepse ne vetëm e bëri atë. 

DAVID J. Malan: Sepse ne vetëm e bëri atë. OK. Mirë përgjigje. Por intuitivisht, pse është zgjedhja Lloj n katror? Çfarë kemi të bëjmë përsëri dhe përsëri? Ne kishim për të mbajtur skanim me anë të, janë ju vogli, janë të që ju vogël, jeni më të vogël. Dhe të dhënë, ne ishim në gjendje për të marrë n hapa, pastaj n minus 1, pastaj n minus 2. Por në qoftë se ju lloj i shtoni ato të gjithë lart, ose të marrë atë në besimin që unë kam shtuar ato paraprakisht, ne kemi marrë afërsisht n katror minus disa numra të vogla. Kështu që unë jam duke shkuar për të thirrur këtë n katror. Por me lloj përzgjedhjes në më të mirë rasti, sa hapa është ajo duke shkuar për të marrë mua? 

Kryetari 5: [padëgjueshme] 

DAVID J. Malan: Kjo është për fat të keq ende të n squared, e drejtë? Sepse në qoftë se unë jam zgjedhur më të vogël element, dhe ne kishim shtatë njerëz këtu, Unë vetëm e di, një herë unë të shkoj në shumë fundi, që unë e kam gjetur më i vogël numrin, kudo që ai ose ajo mund të ketë qenë. Por si mund ta gjej e ardhshëm numri më i vogël? Unë duhet të bëni një tjetër abone. Pra, në rastin më të mirë, çfarë është input për lloj përzgjedhjes? Kjo është një tashmë listë lloj, numër një, Numri dy, numri tre, numër katër. Por unë jam një kompjuter. Unë vetëm mund të shohim në një gjë në një kohë. Unë nuk mund të lloj të marrë një hap përsëri si një njeri dhe të thonë, ooh, kjo duket e saktë. 

Unë vetëm mund të gjykojnë korrektësi në lloj përzgjedhje duke përzgjedhur numri më i vogël. Por edhe në qoftë se unë të gjeni një numër të parë, në qoftë se unë nuk di asgjë tjetër në lidhje numrat e tjera, të cilat unë nuk e bëjnë, të gjitha unë e di se unë kam qenë i dorëzoi një sërë ose një grup i dyerve prapa të cilave janë Numrat, e vetmja mënyrë unë e di se një ishte më i vogël? Nëse unë të marrë të gjithë rrugën këtu dhe e kuptojnë, Damn, njëri ishte me të vërtetë i vogël. 

Por si mund unë atëherë të përcaktojë se dy është më i vogël e ardhshme? Duke bërë paefektshmërinë njëjtin përsëri dhe përsëri. Pra, në fund, me lloj futje, se, ne rastin keq, nuk themi kryen atë? Kjo shumë është n katror. Dhe si në lidhje me rastin më të mirë? Ne do të lënë atë si një cliffhanger. Ne do të plotësoni në atë kohë bosh ardhshëm, por së pari më lejoni të propozoj që ne rrënjësisht të bëjë më mirë se të gjitha këto, të gjithë të drejtë? 

Pra, mendoni për veten se çfarë shtënie Rendit do të jetë. E pra, që nuk ishte shumë dramatike, sepse unë jam i vetmi se pa ndryshim. Wow. OK. Pra, këtu kemi një disi demonstrim të ndryshme. Nëse unë zoom në këtu, ju do të shihni se në majtas ne kemi lloj flluskë, në mesme ne kemi lloj përzgjedhje, dhe mbi ekstremit të djathtë, ne kemi diçka që ne nuk e kanë shikuar ende quajtur bashkojë lloj. Por e konsiderojnë atë që ne kemi qenë të duke bërë këtu deri tani sot. Kur Jennifer e parë doli në skenë, shkuam nëpër rrjet të numrave përsëri, dhe përsëri, me kërkim linear, dhe kemi marrë kohën lineare të rrjedhshëm, i madh o i n, në mënyrë që të flet. 

Kur ne tani e konsiderojnë javën e parë të klasë, kur ne kishim përça dhe sundo, dhe ne kishim librin e telefonit marramendës, dhe Jennifer, dhe ne kolektivisht leveraged që pasqyrë e kyç, i cili ishte për të përsëris veten përsëri dhe përsëri nga disi hedhur larg, duke hedhur larg, hedhur larg, gjysma e problemit, ose në përgjithësi, duke e ndarë një problem në gjysmë, dhe pastaj trajtimin copë të vogël të Problemi si konceptualisht ekuivalent për tjetrin, ne disi e bëri rrënjësisht të mirë. Por me lloj flluskë, me përzgjedhje lloj, me lloj futje, ne kemi mund nuk ka njohuri të tilla që Jennifer bëri. Ne pretty much vetëm ecte prapa dhe radhë një bandë e tërë e kohës, dhe ne gjërat tweaked pak, shkëmbejnë në këtë mënyrë, ndoshta futur ose zgjedhjen. Por në fund të ditës, unë e bëri një shumë të ecin vështirë mbrapa dhe me radhë. Ne nuk e bëri me të vërtetë diçka të levave i zgjuar si Jennifer bëri si ndarëse dhe pushtues. 

Pra bashkojë lloj, nga ana tjetër, të cilin ne nuk do të shohin deri javën e ardhshme, ajo do të levave se ideja kryesore duke pjesëtuar input, dhe pastaj të përgjysmuar, dhe pastaj përgjysmuar, dhe pastaj të përgjysmuar. Dhe në çdo përsëritje e asaj lak, sorting gjysmën e majtë, dhe e drejtë gjysma, atëherë gjysma e majtë e gjysmës së majtë, dhe gjysma e djathtë e të majtë, atëherë gjysma e majtë e gjysmës së djathtë, dhe gjysma e drejta e gjysmës së djathtë. Dhe duke përsëritur përsëri dhe përsëri. 

Pra, ju do të shihni këtë vizualisht, por kjo është ajo që na pret javën e ardhshme. Dhe në përgjithësi, kur ne mendojmë pak pak e vështirë për çdo problem të tillë. Ne kemi n katror në të majtë, n në katror në qendër, dhe n hyni N në të djathtë. Pra, nuk ka cliffhanger juaj i vërtetë. Ne do të shohim ju në hënën. 

[Duartrokitje]