Gjuha: Në rregull, kjo është CS50. Ky është fundi i javës së tre, dhe në qoftë se ju nuk kanë përfituar tashmë, e di se do të ketë drekë kjo e premte si zakonisht, ku ju mund të gëzojnë bisedë të mirë dhe ushqimit në zjarr dhe akull me disa nga CS50-së Stafi dhe shokët e klasës. Shkojnë në këtë URL këtu. 

Tani ju mund të kujtohet, apo ju së shpejti mund të jenë të njohur me, këto gjëra këtu, të cilat janë dhënë në fund i semestrit për shumë klasa. Libra blu ashtuquajtura provimit, në të cilën ju shkruani përgjigjet tuaja për provimet. Tani unë kam këtu 26 të tilla libra blu, për secilin prej tyre është shkruar një emër, një pasim Z. Dhe në të vërtetë emrat janë aq të thjeshta, Një përmes Z. Dhe një nga qëllimet në dorë sot do të jetë për të vazhduar çfarë kemi filluar të hënën, e cila nuk është aq shumë kërkuar në kodin, por me të vërtetë duke kërkuar në idetë dhe zgjidhjen e problemeve. Një nga qëllimet dhe premtimet e këtij kursi është për të mësuar se për të menduar më shumë me kujdes, më shumë në mënyrë metodike, dhe për të zgjidhur problemet në mënyrë më efikase. Dhe me të vërtetë, ne mund të bëjmë që me të vërtetë edhe pa e prekur një linjë të kodit. Kështu që unë kam një çift të elefantëve këtu sot, portokalli dhe blu, në qoftë se ne mund të marrë një vullnetar, ndoshta nga më larg prapa se zakonisht. Si për të drejtë atje, vijnë më poshtë. Qëllimi i cili do të jenë të ndihmojë plus administruar këtë provim këtu. Si e keni emrin? 

Audienca: Mary Beth. Gjuha: Mary Beth, eja lart. Më lejoni të merrni mikrofonin këtu për ju. Gëzohem që u njohëm. 

Audienca: Gëzohem që u njohëm. Gjuha: Në rregull, kështu që unë kam këtu libra blu Një përmes Z, dhe unë jam duke shkuar për të pretendojë se Unë kam një nga studentët, dhe ata janë të ardhur në disi rastësisht në fund të një tre orë bllok provimit, kështu që ata janë duke i dhënë fund deri në disa mënyrë gjysmë të rastit si kjo. Tani puna juaj në vetëm një moment do të be-- kjo është në të vërtetë se si ata marrin kthyer në në fund të klasës, ka shumë të ngjarë. Puna juaj tani do të jetë, mjaft thjesht, për të zgjidhur këto libra blu për ne nga A nëpërmjet Z. 

Audienca: Oh, kjo është e do të marrë përgjithmonë. 

Gjuha: Dhe ne do të shikojnë si ju bëni këtë, nuk ka presion. Audienca: Jo, nuk ka presion apo ndonjë gjë. 

Gjuha: Dhe për argëtim, le të vënë një orë me zile. 

Audienca: Pra, shumë e bukur, e bukur aq shumë. 

Gjuha: Unë mund të mbajnë mic për ju. Në rregull, ne kemi dyfishuar vetëm shpejtësinë tonë. Pra, në ndërkohë, më lejoni të paraqesin çfarë është do të jetë pyetje për Mary Beth është ajo që është duke bërë ajo, se si është ajo shkon në lidhje me zgjidhjen e kësaj? Dhe në fakt, ju nuk mund të ketë menduar ndonjëherë për diçka aq e thjeshtë sa, kur ju të vini up 26 libra si kjo, të cilat kanë një natyrore urdhëruar atyre. Cili është procesi që ju të vërtetë të përdorni? A është e drejtë të rastit vetëm picking një të parë që ju shihni dhe vënë atë në vendin e saj? A e keni parë të shkojë në duart tuaja rreth Duke kërkuar për një më pas duke kërkuar për B? A keni marrë një sy në një palë ato krah për krah dhe vetëm thonë, prit një minutë, kjo nuk është e drejtë, dhe pastaj të bie në ujdi e rendit? Ne pamë tashmë të hënën se ka një numër mënyrash në të cilën ne mund ta bëjë këtë, dhe me të vërtetë si ne pranë fund këtu, Unë do të vini re ndoshta e çfarë Mary Beth është duke bërë. Ne kemi një shtyllave disa me sa duket, një më të madhen, tre ato më të vogla. 

Audienca: Unë jam urdhëruar t'i kur kam gjetur dy letra që unë e di se janë së bashku në një sekuencë, I vënë ato së bashku në mënyrë që unë të mos bëj duhet të shqetësohen për mbajtjen gjurmët e një rresht të tërë librash. Është vetëm, oh, A është i pari, Unë kam marrë këtë rafte këtu. Gjuha: Pra, pothuajse si një copë mister që kanë formën e duhur për të përputhen me njëri tjetrin. Audienca: Shumë e shumë, vërtet. Gjuha: OK, e shkëlqyer. Dhe tani secili nga këto shtyllave të zgjidhet me sa duket? 

Audienca: Po. 

Gjuha: Në rregull, Një përmes Z. All drejtë, urime, ju e bëri atë. Ju keni zgjedhjen tuaj. Blue? Në rregull, ju falenderoj për këtë. Pra Mary Beth ka propozuar çfarë qasje saj ishte, por ajo që është një tjetër metodë se si ju mund të shkoni në lidhje me klasifikim këto gjëra? Çfarë do të kishit bërë? Rekord të mundë do të kishte qenë një minutë dhe 50 apo më shumë sekonda, plus ato që kam harruar për të numëruar. Çfarë do të kishit bërë? Po? Audienca: Merrni rafte. Fillojnë nga fillimi. Kontrolloni letrat tuaja. Dhe në qoftë se një krye është më e lartë se, ndoshta, ata janë, një fund është më të lartë, pastaj kaloni ato. 

Gjuha: OK, kështu që duke filluar në krye dhe në fund, dhe pastaj të punojnë në rrugën tuaj brendshëm si kjo, shkëmbejnë ato? OK, kështu që pak të ngjashme në frymë të flluskë lloji, por duke zgjedhur ekstremet jo palë ngjitur. Por të shkurtër të tij është se nuk ka me siguri një bandë e mënyra të ndryshme ne mund të bëjmë këtë, dhe sinqerisht, unë mendoj se ju lloj adoptuar një qasje çift, apo jo? Ju bërë lloj të katër shtyllave të renditur, dhe pastaj në mënyrë efektive shkrirë ato së bashku. Dhe kjo është, guxoj të them, një tjetër teknikë krejt. Ju nuk e trajtojnë atë si një grumbull i madh, ju ndarë problemin në katër quads, në qoftë se ju do, dhe pastaj disi shkrirë ato në fund. 

Pra, le të marrin në konsideratë, në fund të fundit, si tjetër ne mund të bëjmë këtë. Ne formalizuar nocionin i flluskë renditjes herë të fundit, dhe kujtojnë flluskë lloj ishte një algorithm që ne visualized me tetë nga shokët e klasës tuaj deri këtu, në dukje të renditura rastësisht në fillim. Dhe ne pastaj vendosi pairwise, nëse dy elemente janë jashtë rendit, thjesht bie në ujdi tyre. Pra, katër dhe dy janë qartë nga e rendit, kështu ata të dy shokët e klasës kaloi pozicionet. Dhe pastaj kemi përsëritur me katër dhe gjashtë, pastaj gjashtë dhe të tetë, në çdo përsëritje, duke lëvizur në të djathtë. 

Pra, duke pasur parasysh tetë njerëz, sa pairwise Krahasimet e bëra unë këtë, ndërsa në këmbë nga majta në të djathtë në një përsëritje të tillë? Sa krahasime? Shtatë, e drejtë? Sepse në qoftë se ka tetë njerëzit por ju keni palë ata dhe ju mbani lëviz një hop në të djathtë, ju nuk jeni do të ketë tetë krahasime, sepse ju nuk mund të krahasohen një element kundër vetvetes, ose ajo do të vetëm të jetë i kotë, kështu që ju keni shtatë. Ose më në përgjithësi, në qoftë se ne kemi n njerëz, ne bëjë n minus 1 krahasime me flluskë lloji. 

Pra, le të konsiderojmë tani se sa e mirë apo flluskë keq lloj të vërtetë ishte, dhe të përpiqemi për të dhënë vetes fjalorin me e cila për të algoritme të kritikuar si kjo, dhe së shpejti tonat. Pra kalimin e parë përmes lloj flluskë, hera e parë Kam ecur nga e majta në të djathtë nëpër fazë, mori me n minus 1 krahasime. Dhe kjo do të jetë e mia njësi të masës, e drejtë? Unë kam qenë lloj i folur dhe shëtitës, disi të shpejtë, disi i ngadaltë, kështu duke numëruar numrin tim të sekonda nuk është veçanërisht e thënë, por numërimi numrin e operacionet që kam bërë të hënën, krahasuar dy njerëz, që ndihet si një njësi e bukur e masës. 

Pra, n minus 1 hapa për herë të parë, por pastaj çfarë ndodhi pas kësaj? Çfarë është një kokë e një të kaluar përmes një listë ndryshe shtëpiake i pa klasifikuar? Çfarë mund të thoni në lidhje me elementin që ishte të gjithë rrugën atje? Po? Kjo ishte elementi më i madh, e drejtë? Numri tetë, edhe pse ajo filluar këtu, çdo herë që unë krahasuar atë kundër një fqinj, ajo mbajti bubbling deri në të djathtë anën e listës. Dhe me të vërtetë, kjo është ajo ku algorithm merr emrin e vet. 

Tani nga kjo logjikë, sa krahasimet duhet ta bëjë në të dytën Unë të bëjë që të kalojë nga e majta në të djathtë? n minus 2, e drejtë? Ajo thjesht do të jetë humbur kohën time nëse unë mbani krahasuar tetë kundër dikujt tjetër, sepse ne tashmë e dimë ajo ishte në vendin e duhur. Pra, kjo është pak e një optimization, kështu që të kalojë e ardhshme do të jetë plus n minus dy hapa, ku n është numri i njerëzve. Tani ju mund të lloj të nxjerrim, madje edhe në qoftë se ju nuk jeni një shkencëtar kompjuteri, se si kjo përfundon. Në fund të këtij algoritmi, me sa duket ju keni marrë vetëm një krahasim i majtë. Ju duhet të lloj të rregulluar fillimi i listës në rastin e dy dhe një janë jashtë rendit dhe duhet të jetë një dhe dy, kështu që kjo fundeve jashtë në plus 1 Krahasimi i formës së prerë. 

Tani dot, dot, dot lloj valëve është duart në disa nga juicier detaje, por le të vetëm të shkojnë përpara dhe të thjeshtojë. Nëse ju kujtohet nga lartë shkollë, sinqerisht, një shumë prej jush kishin libra të matematikës që kishin një mashtrojnë pak fletë për të mbuluar para ose mbuluar mbrapa që ju tregoi summations çfarë seri si kjo në fund të fundit shtuar deri. Në rastin e përgjithshëm, në qoftë se ju keni një variabël si n, dhe në të vërtetë kjo, në qoftë se keni shikuar tuaj Libri i math shkollës së vjetër, ju do të shihni se kjo në të vërtetë shton deri në këtë shumë këtu, n herë n minus 1 të gjitha të ndara nga 2. Kështu që tani për tani më lejoni vetëm të përcaktojnë kjo është e vërtetë, kështu që për një hap të besimit, kjo është ajo që kjo përmbledh deri në, dhe ne mund të të provojë se në një rast më të përgjithshëm. Por tani le të zgjerohet këtë. Pra, le të shumëfishohen këtë, kështu që është e n katror, ​​minus n, të gjithë të ndarë nga 2. Kjo është me të vërtetë katror n, ndarë nga 2, minus n mbi 2, kështu që është e gjitha e bukur dhe interesante. Por çfarë ndodh nëse ne tani plug-në vlerë? Supozoni se unë nuk kanë tetë njerëz, por thonë se një milion. Dhe një milion vetëm për shkak kjo është një numër goxha i madh, le të plug atë in dhe të shikoni se çfarë ndodh. Pra, nëse unë plug një milion në atë formulë Unë jam duke shkuar për të marrë një milion katror, ndarë nga 2, minus një milion, ndarë nga 2. Tani çfarë po që do të barabartë? Pra 500 miliardë, minus 500.000. Dhe në qoftë se unë të bëjë në fakt që matematikë jashtë, që do të thotë se zgjidhja e një milion njerëzit me lloj flluskë mund të marrë më 499.999.500.000 hapa ose krahasimet në fund, ne jemi vetëm nxjerrjen. 

Kjo ndihet shumë e ngadaltë, por sinqerisht matur një kontribut të veçantë si kjo, nuk është e gjitha që domethënëse. Por në të vërtetë ai nuk sugjeron se si n merr më të mëdha dhe më të madhe, ky algoritëm lloj ndihet keq dhe më keq, apo ju me të vërtetë fillojnë të ndjejnë dhimbjen e që exponentiation, se n katror, që përbën deri shumë shpejt. Dhe ky detaj nuk është humbur në njerëz, në fakt disa vjet më parë një senator të caktuar i cili ishte fushata, u ul për një intervistë me Eric Google Schmidt, CEO në atë kohë, dhe u kundërshtua me një pyetje ashtu si ne jemi duke eksploruar sot. Le të bëjmë një vështrim. 

[VIDEO Playback] 

-Senator, Ju jeni këtu në Google, dhe unë si për të menduar e presidencës si një intervistë për punë. Tani, është e vështirë për të marrë një punë si president, dhe ju jeni duke kaluar nëpër masa të rrepta tani. Është gjithashtu e vështirë për të marrë një punë në Google. Ne kemi pyetje, dhe ne bëjnë pyetje kandidatët tanë, dhe kjo është nga Larry Schwimmer. What-- ju djema mendoni se unë jam shaka, ajo është e drejtë këtu. Cila është mënyra më efikase për të zgjidhur një milion numra të plotë 32-bit? 

-Well-- 

-Me Fal, maybe-- 

Jo, jo, jo. Unë mendoj se lloj flluskë do të jetë mënyra e gabuar për të shkuar. 

-Come Në, i cili i tha atij këtë? Unë nuk e shoh kompjuter shkenca në sfond tuaj. 

-We've Mori spiunë tona në atje. 

OK, le të kërkojë një tjetër pyetje intervistë. 

[VIDEO END rishikim] 

Gjuha: Pra, duke folur për numra specifike edhe pse, nuk do të jetë mbi të gjitha që të dobishme. Kjo nuk është një mësim i jetës që flluskë lloj, duke pasur parasysh një milion inputeve, mund të marrin deri në 500 miliardë hapa. Ju nuk mund të vërtetë të përgjithësoj shumë në mënyrë efektive nga se dhe të marrin vendime të mira të projektimit kur shkruani programe. Pra, le të përqëndrohet edhe pse në atë se si ne mund të thjeshtojë këtë rezultat. 

Kështu që unë e kam theksuar në të verdhë këtu rezultat i n katror ndarë nga 2, kështu që një milion katror ndarë me 2, dhe pastaj Unë e kam theksuar se çfarë përgjigje i fundit ishte dikur ne zbritet off ndarë n me 2. Dhe kërkesa unë jam duke shkuar për të bërë tani është, kush kujdeset dreq nëse ju zbres off a n vjetër pak mbi 2 kur i pari pjesë e kësaj formule është aq shumë më e madhe? Ajo dominon tjera Termi, n katror ndarë nga 2 është aq shumë më e madhe, në mënyrë të qartë, si n merr e madhe si një milion, se a ka me të vërtetë një ndryshim të madh në në fund të ditës në mes të 500 miliardë dhe 499.999.500.000? Jo me të vërtetë. Dhe kështu që ajo që ne jemi duke shkuar për bëni si shkencëtarët kompjuter është injorojë ato terma më të ulët e rendit dhe të marrë diçka si kjo dhe të vërtetë vetëm të lehtësuar atë të term që do të rëndësi. Sa më i madh vendos tonë të dhënave të merrni, aq më e madhe Bazat e të dhënave tona të marrë, faqet web më shumë ne kemi për të kërkuar, më të miq keni në Facebook. 

Si n merr më të madhe, ne jemi me të vërtetë do të kujdesen për më të madhe Termi në çdo analizë të tillë të performancës algoritme tonë. Dhe unë jam duke shkuar për të thënë, ju e dini se çfarë, flluskë lloj është në rendin e O të madhe, në mënyrë të n katror. Kjo nuk është saktësisht n katror siç kemi parë, por që me të vërtetë kujdeset për ato terma më të vogla, dhe sinqerisht, që me të vërtetë kujdeset nëse ne ndani me 2? Kjo është vetëm një faktor konstant. Dhe është 500 miliardë kundrejt 250 miliardë vërtetë se i madh i një marrëveshje? Unë mund vetëm të presim një vit, le laptop tim fjalë për fjalë të marrë dy herë më shpejt në hardware, dhe atë gjë e diferencës vetëm shkon larg natyrisht me kalimin e kohës. 

Ajo që ne intereson është shprehja, pjesa e shprehjes që do të ndryshojnë si të dhëna jonë merr më të mëdha. Dhe me të vërtetë, në botën e vërtetë, kjo është ajo që po ndodh gjithnjë e më është inputet për problemet tona dhe të algoritme janë të bëhet më e madhe. Pra, O i madh do të jetë simbol, simbol asymptotic, që ne vetëm përdorin si shkencëtarët kompjuterike për të përshkruar performancës, ose koha drejtimin, e nje algoritmi. Kështu që ne mund të krahasohen algoritme në kompjuterë të ndryshëm shkruara nga njerëz të ndryshëm, duke përdorur disa metrikë krejtësisht të ngjashme si numri i krahasimeve të jeni duke e bërë, ose ndoshta numrin e këmbime ju jeni duke bërë. 

Ajo që ne nuk jemi duke shkuar për akuzë është sasia e kohës që kalon në orën në mur mënyrë tipike. Ajo që ne nuk jemi duke shkuar për t'u shqetësuar rreth është se sa memorie ju jeni duke përdorur sot në paktën, edhe pse kjo është tjetër burim ne mund matur. Ne jemi duke shkuar për të përpiqen për të bazojnë analizat tona në vetëm operacionet themelore, ato, sinqerisht, që ju mund të shihni më me sy. Pra, me diçka si O madh të n katror, ​​unë pretendojnë se o të n katror është një kufi i sipërm në të ashtuquajturat drejtimin kohën e flluskë lloji. Me fjalë të tjera, në qoftë se ju donte të thonë se nuk ka ky kufi i sipërm për sa hapa një algoritmi mund të marrë, ajo do të jetë në O madh të n katror në këtë rast, një kufi i sipërm. 

Çka nëse unë në vend të ndryshojë histori të mos jetë në lidhje flluskë lloji, por për këtë kufi i sipërm. A mund të mendoni për një algoritmi që ne i kemi shikuar tashmë cilit kufirin maksimal, maksimale masë e kohës apo operacioneve, do të thuhet që do të kufizohet nga n, një funksion linear, jo një katror që është lakuar? Çfarë është një algoritmi që gjithmonë merr jo më shumë se si hapat N, ose Hapa 2n, apo hapa 3n? Po? 

Audienca: Gjetja Numri më i madh në një listë? 

Gjuha: Perfect, duke gjetur numri më i madh në një listë. Nëse unë jam duke dhënë një listë të njerëzit për shembull, secili i cili është duke zhvilluar një numër, çfarë është numri maksimal hapash duhet të marrë mua, një person i arsyeshëm i zgjuar, për të gjetur personin më të madhe në këtë listë? n, e drejtë? Sepse në rastin më të keq, kur mund të jetë vlera më e madhe? E drejta, të gjitha rrugën në fund. Pra, në rastin më të keq sipërme të detyruar, unë mund kanë për të shkuar gjatë gjithë rrugës mbi këtu dhe të jetë si, oh, këtu është numri tetë, apo çfarëdo që vlerë të. Tani ajo vetëm do të ishte budallallëk në qoftë se unë do mbajtur, e drejtë? Duke kërkuar për elemente gjithnjë e më shumë në qoftë se i fundit prej tyre është atje? Pra me siguri, n është një kufi i sipërm. Unë nuk kam nevojë për të marrë më shumë hapa se kaq. 

Pra, çfarë nëse në vend të kësaj kam propozuar që ka algoritme në këtë botë që kanë një kohë running që është kufizohet nga O madh të log n, hyni n? Ku kemi parë këtë më parë? Po? 

Audienca: Në problemin librin e telefonit? Gjuha: Ashtu si problemin librin e telefonit. Cili ishte masë e si shumë kohë ose sa lotët e punon mori mua për të gjetur dikë si Mike Smith në librin e telefonit? Ne pretendoi se ishte log n, dhe edhe nëse të panjohur ose ajo është e një mjegullt pak atë që një logaritmi apo eksponent ishte, vetëm mos harroni se log n përgjithësisht referohet procesit, në këtë rast, e ndarë diçka në gjysmë përsëri, dhe përsëri, dhe përsëri, dhe përsëri, të tilla që të merr gjithnjë e më të vogla si ju bëni këtë. 

Pra, hyni i referohet n, i sigurt, për shembull librin e telefonit, për kërkim binar në teori, kur ne kishte dyert virtuale në bord, ose kur Sean ishte kërkoni për diçka. Nëse ai kishte përdorur kërko binar, hyni n do të ishte e sipërme të lidhura nga sa Koha që merr. Por ato algoritme që u zhvillua në Identifikohu n supozohet çfarë detaj kyç? Kjo listë është renditur, e drejtë? Algorithm juaj është e gabuar nëse input juaj nuk zgjidhet, por ju jeni duke përdorur diçka si kërkim binar sepse ju mund të kërcejnë drejtë mbi elementin pa e kuptuar se është me të vërtetë atje. 

Tani çfarë mund të thotë kjo, o të madh të një? Kjo nuk do të thotë se algoritmi tuaj merr një dhe vetëm një hap, ai thjesht do të thotë ajo merr një Numri i vazhdueshëm i hapave. Ndoshta është 1, ndoshta është 10, ndoshta është 1000, por kjo është e pavarur nga madhësia e problemit. Pa marrë parasysh se sa e madhe n është, një algorithm Koha konstante gjithmonë merr numër të njëjtë të hapave. Pra, çfarë mund të jetë një algoritmi kemi folur ose vetëm intuitive që vjen për ju që gjithmonë shkon në të ashtuquajturin kohë të vazhdueshme? Po? 

Audienca: Add dy numra. Gjuha: Add dy numra, 2 plus 2 është e barabartë me 4, bëhet. Kështu që mund të punojnë, çfarë tjetër? Si në lidhje me botën e më reale, vërtet? 

Audienca: Gjetja Gjëja e parë në një listë. Gjuha: Gjetja e parë element në një listë, i sigurt. Ne kemi qenë në të vërtetë duke folur rreth vargjeve tashmë, si mendoni ju merrni në Elementi i parë në një grup, pa marrë parasysh se sa kohë array është në kodin e C? Ju vetëm përdorni si kllapa zero simbol, bam, ju jeni atje. Dhe vërtet vargjeve, si një mënjanë, Mbështetja diçka e njohur përgjithësisht si qasje të rastit, e gjallë kujtesës, sepse ju mund të fjalë për fjalë hidhen në çdo vend një. Ne mund ta bëjmë këtë edhe më thjesht ne mund të Rewind në javë zero kur ne e bëmë Scratch. Sa kohë u desh për thonë bllok në Scratch për të ekzekutuar? Vetëm koha e konstante, e drejtë? Thuaj diçka, thonë diçka, kjo nuk ka rëndësi si Scratches mëdha botërore është, është gjithmonë do të marrë të njëjtën sasi e kohës të thjesht të thonë diçka. 

Pra, kjo është koha konstante, por ajo që është flip side? Nëse kjo ishte e sipërme caqeve, çka nëse ne duam për të përshkruar kufijtë më të ulët e algoritmeve tona running kohë? Pothuajse një rast më të mirë potencialisht, në qoftë se ju do, edhe pse këto terma do të mund të aplikojnë për të mirë raste, raste më të rënda, rastet mesatare më shumë në përgjithësi, por le të vetëm të përqëndrohet më të mëdhenj të ulëta në përgjithësi. Çfarë është një algoritmi që ka një detyruar të ulët i hapa n, apo hapa 2n, apo hapa 3n? Disa faktor hapa n, që është e saj më të ulët i lidhur. Po? 

Audienca: Bubble lloj? 

Gjuha: Bubble lloj merr ju hapa n minimalisht, pse? Pse është se? Pse duhet që të fillojë për të ardhur tek ju intuitive, jo edhe në qoftë se ajo bën vetëm ende? Po? 

Audienca: [padëgjueshme]. Gjuha: Pikërisht. Në skenarin më të mirë të mundshëm të lloj flluskë, dhe një shumë e algoritmeve, në qoftë se unë ju dorë tetë persona të cilët janë të renditura tashmë, kjo do të ishte qesharake për ju, algorithm, për të shkuar mbrapa dhe me radhë më shumë se një herë, drejtë? Sepse sa më shpejt që ju ecin nëpër lista një herë, ju duhet të kuptojnë, oh, kam bërë asnjë këmbime, kjo listë është e renditura, dalje. Por që do të ju merr n hapa. 

Dhe anasjelltas, çfarë është një tjetër mënyrë e të menduarit në lidhje me të? Bubble lloj është një omega, mënyrë që të flasin, e n, sepse në qoftë se ju shikoni në më pak se n elemente, çfarë është çështje themelore atje? Ju nuk e di nëse është e renditura, të drejtë. Ne njerëzit shikim mund të në tetë njerëzit dhe të jetë si, oh, është e renditura, që nuk ka marrë mua n hapa, por ajo e bëri. Sytë tuaj, edhe pse ju lloj e kanë një fushë e madhe e vizionit, ju shikuar në tetë elementeve, ju shikuar në tetë njerëz, që është tetë hapa në mënyrë efektive. Dhe vetëm në qoftë se të ecja gjithë Lista mund ta kuptojnë, po, të renditura. Në qoftë se unë të ndaluar në gjysmë të rrugës duke menduar, të gjithë të drejtë, është e renditura goxha deri tani, çfarë janë shanset nuk është renditur? Kjo nuk algoritme do të jetë e saktë. Mund të jetë më i shpejtë, por të pasakta. 

Deri tani ne kemi një mënyrë për të përshkruar një kufi më të ulët, dhe ajo që për herë të vazhdueshëm? Çfarë është një algoritmi që ka një më të ulët lidhur me kohën e saj drejtimin e një? 1 hap, 2 hapa, 10 hapa, por konstante, të pavarur nga n, Madhësia e input? Po, në shpinë. 

Audienca: printf? Gjuha: Çfarë është ajo? Audienca: printf? Gjuha: printf. OK, i sigurt. Pra, ajo merr një numër të caktuar të hapave. Dhe unë duhet të now-- tani që ne jemi duke folur në lidhje me kodin C dhe nuk Scratch, diçka si të themi, me printf, ne duhet të fillojë të marrë të kujdesshëm. Sepse printf merr input, kjo është një varg, dhe vargjet e teknikisht kanë gjatësi. Pra, në qoftë se ne tani duam të marr për ju, nëse ju nuk do mend, teknikisht ne mund të argumentojnë se printf ka marrë një kontribut ndryshueshme gjatësi, dhe me siguri ajo mund të marrë më shumë koha për të shkruar një varg këtë kohë, se kjo kohë. 

Pra, çfarë po të kemi parasysh vetëm klasifikim dhe kërkoni shembuj? Po në lidhje me Mike Smith në telefon libër, ose kërko binar në përgjithësi? Në rastin më të mirë, çfarë mund të ndodhë? I hapur librin e telefonit dhe, bam, ka numër Mike Smith. Unë mund të telefononi atë menjëherë. 

Mori një hap, ndoshta dy hapa, por një numër të vazhdueshëm të hapave nëse kam fat. Dhe sinqerisht, ne pamë në E hënë shok klase tuaj të merrni mjaft me fat dy herë në një rresht. Dhe kjo ishte me të vërtetë konstante herë në një mëdhenj të ulët në algorithm në fjalë për gjetjen e Numri 50 prapa ato mbyllen dyert. 

Tani, si një mënjanë, në qoftë se ju të zbuloni që të dy O i madh, kufi i sipërm, dhe omega, më të ulët i lidhur, janë një në njëjtë, që është njëjtë formulë në kllapa, ju gjithashtu mund të thonë, vetëm të jetë i zbukuruar, se diçka është në theta e n apo theta e disa vlera të tjera. Kjo thjesht do të thotë kur i madh O dhe omega janë njëjtë. Tani ajo që për përzgjedhjes lloj? Le të përdorim këtë fjalor të ri. Në përzgjedhjes lloj, cilat ishin ne duke bërë përsëri, dhe përsëri, dhe përsëri? Unë kam qenë duke shkuar mbrapa dhe me radhë përmes lista, duke kërkuar për të cilët? Numër më të vogël. 

Pra, si shumë hapa, se si shumë krahasime bëri I duhet të bëni në mënyrë që të kuptoj se kush element vogël në lista ishte? n minus 1, e drejtë? Sepse në qoftë se unë vetëm të fillojë me atë që unë jam dhënë dhe unë të fillojnë të krahasuar atë, pastaj atë apo të saj, atë të ose të saj, atë apo të saj, unë vetëm mund palë elemente bashku n minus 1 herë. Pra, zgjedhja lloj mënyrë të ngjashme merr n minus 1 hapa për herë të parë. 

Sa hapa nuk është marrë mua për të gjeni elementin e dytë më të vogël? n minus 2, sepse unë jam duke u memec në qoftë se unë mbaj duke kërkuar në të njëjtit njerëz përsëri në qoftë se unë e kam zgjedhur tashmë atë apo të saj dhe vënien e tyre në vendin e tyre. Dhe hapi i tretë, n minus 3, atëherë n minus 4. Ne e kemi parë këtë model para, dhe në të vërtetë Zgjedhja lloj të ngjashme ka një lidhje të lartë e n katror nëse ne bëjmë deri atë përmbledhje. Ajo që është më e ulët i detyruar, zgjedhja lloj i saj? Minimalisht, sa kohë duhet përzgjedhje lloj të marrë, si ne definuar atë të hënën? Propozojë dy opsione. Ndoshta është n, si më parë. Ndoshta kjo është katror n, si të tani është si kufi i sipërm. 

Audienca: katror n. Gjuha: n katror. Pse? 

Audienca: Sepse ju keni për të përcaktuar [e padëgjueshme]. 

Gjuha: Pikërisht. Të paktën siç e përcaktuar përzgjedhjes lloj se ishte mjaft naive, do të mbajë, gjeni elementin më të vogël. Shko përsëri, gjeni elementin më të vogël. Shko përsëri, gjeni elementin më të vogël. Nuk ka asnjë lloj optimization në atje që mund të më lejoni të ndërpresin shtatzëninë pas vetëm n apo më shumë hapa. Pra me të vërtetë, zgjedhja lloj, omega e n katror. 

Po në lidhje me llojin e hyrjes, ku unë u që I është dhënë, dhe pastaj unë plopped atë ose të saj në vendin e duhur? Pastaj kam vazhduar për personin e dytë, plopped atë në vendin e duhur. Pastaj personi tjetër, plopped atë apo të saj në vendin e duhur. Vini re se kjo është shumë e lineare, mënyrë që të flasin. Unë jam një vijë e drejtë, unë jam mos shkuar mbrapa dhe me radhë, Unë kurrë nuk kam shikuar prapa të vërtetë, por se çfarë po ndodh, kur kam futur atë ose saj në fillim të lista si ne e bëmë të hënën? Çfarë po ndodh? Po? Audienca: [padëgjueshme]. Gjuha: Po, se ishte kapur, e drejtë? Ju mund të kujtojnë nga shokët e klasës tuaj, nëse ata janë duke bërë çdo lëvizje me këmbët e tyre, që ishte një operacion. Pra, nëse do të kishte tre persona këtu dhe personi i ri i takonte rruga atje, në një fazë të gjatë si kjo, i sigurt, ai ose ajo mund të shkojë vetëm deri në fund. Por në qoftë se ne jemi duke menduar për një kompjuter dhe një koleksion të kujtesës, këta njerëz janë duke shkuar që të ketë për të riorganizimi mbi për të bërë vend për atë person. Dhe kështu që n minus 1 shufflings, n minus 2 shufflings, n minus 3 shufflings është vetëm lloj i ndodh pas meje, nuk para meje si më parë, në një kuptim. Tani si një mënjanë, dhe si ju mund të keni parë në internet në qoftë se ju filloni poking rreth në lidhje me llojet, ka ato kaq shumë të ndryshme atje, disa prej tyre mirë se të tjerët. Në të vërtetë, bogosort është një që është lloj i argëtim të kërkoni. Bogosort merr një sërë numra ose thonë se një kuvertë të kartave, rastësisht lëvizjet e tyre, dhe kontrollon nëse ata janë të renditura. Dhe nëse jo, e bën atë përsëri. Dhe nëse jo, e bën atë përsëri. Nëse jo, e bën atë përsëri. Tepër të trashë. 

Dhe me të vërtetë, në qoftë se ju lexoni si artikull Wikipedia, pseudonimi i tij është lloj budalla. Kjo përfundimisht do të punojë, me shpresë, duke pasur kohë të mjaftueshme, por se sasia e kohës mund të marrë shumë kohë. Pra, nëse unë mund të, le të me shpejtësi të gjërave nga shembull Mary Beth-së më parë, duke pasur disa elemente më shumë, por dy procesorë më shumë. Dy njerëz, nëse ju nuk do mend bashkuar me mua. Si për 1 gjatë këtu, dhe le të go-- askush mbi atje? Askush atje? OK. Ju me të zeza shirt, po, vijnë më poshtë. Në rregull, si e ke emrin? 

Audienca: Peter. 

Gjuha: Çfarë është ajo? 

Audienca: Peter. Gjuha: Peter, David, nice to meet you. Në rregull, ne kemi Pjetër këtu, në qoftë se ju duan të vijnë mbi tryezë mbi këtu. Dhe si e ke emrin? 

Audienca: Elena. Gjuha: Elena. OK, nice to meet you. Elena takuar Pjetrin. Peter, Elena. Dhe ne do të duhet Andrew deri këtu, si edhe, ju lutem. Dhe sfida juaj është duke shkuar të jetë për të zgjidhur një kuvertë të kartave. Dhe në qoftë se të panjohura, kuvertë e kartave të duhet në fund të fundit të zgjidhet një diçka të vogël si kjo ku ne do të bëjmë klubet, atëherë e maç, atëherë zemrat dhe diamante, nga ACE si një, të gjithë rrugën deri te mbreti. 

Kartat Unë jam duke shkuar për të ju jap do të jetë 52 në sasi. Ne jemi duke shkuar për të në mënyrë të ngjashme Ora ju, në vetëm një moment. Ne jemi duke shkuar për të hedhur Andrew deri në ekran këtu, në mënyrë që të shikojnë si ju bëni këtë. Dhe në mënyrë që e gjithë kjo është edhe më e dukshme, këto janë kartat e kam marrë në Amazon. Pra, ata janë tashmë të rastësishme renditura, dhe ne jemi duke shkuar në kohë ju. Dhe ne jemi duke shkuar për mbani atë të vërtetë këtë herë, kështu që ne jemi duke shkuar për të përpiqen për të ju presion sepse përndryshe kjo do të merrni lodhshme shpejt. Nëse ju mund të vazhdojë për të zgjidhur 52 elemente së bashku nëpërmjet disa mjeteve, tani. 

Dhe përsëri, si ne shikojnë këto djema bëni çfarë, në fund do të prodhojë një e qartë rezultat, mendoj se për të vërtetë se si ata po secili duke bërë atë, se si ju mund të përshkruajnë atë. Sepse përsëri, këto janë të gjitha proceseve, algoritme që kemi marrë për të dhënë si një njeri. Por ndoshta ju keni pasur gjatë intuita, shumë kohë para jush edhe menduar për marrjen e një klasë shkenca kompjuterike ju mund të ketë pasur intuitë me e cila për të zgjidhur probleme si kjo. Por sapo ju njohin modelet dhe të fillojnë për të formalizuar hapat me të cilat ju jeni zgjidhjen e këtyre problemeve, ju do të gjeni se ju mund të zgjidhin shumë më interesante dhe shumë më tepër komplekse Problemet shpejt. Pra, dikush nga publiku, çka është të paktën një element i algoritmin se ata janë duke përdorur këtu? 

Audienca: [padëgjueshme] Gjuha: Çfarë është ajo? Audienca: By kostum. Gjuha: By kostum. Pra, së pari ata janë clustering gjithë diamantët bashku me sa duket, të gjithë zemrat së bashku me sa duket, dhe kështu me radhë, pa respekt për numrat në kartat. Dhe tani ata duket, për shembull, që do të zgjidhja e tyre sipas numrit. Shumë mirë. 

Në rregull, kështu që çfarë do të të jetë hapi i fundit pastaj këtu? Pasi ne kemi katër kostume të renditura, ajo që nuk kemi nevojë të bëjmë për të katër shtyllave në mënyrë që të arrihet një renditura kuvertë, mjaft e thjesht? Pra, ne kemi nevojë për të bashkojë ato përsëri. 

Pra, ka një ide interesante që përsëri, guxoj të them, është shumë intuitiv edhe në qoftë se ju nuk mund të keni shuplakë se lloj i etiketës mbi të. Ky nocion themelor i ndarjes problemi jo në gjysmën e kësaj kohe, por të paktën në katër pjesë. Zgjidhja e shumë e shumë Problemet krejtësisht identike ne izolimin e njëri tjetrit, dhe pastaj bashkimi rezultatet. Dhe, e shkëlqyer, bërë. Në rregull, një raund i madh e duartrokitje, në qoftë se ne mund të. 

[Duartrokitje] 

Gjuha: Unë nuk kam asnjë ide se çfarë ju do të bëjnë me këto, por këtu ju shkoni. Thank you so much. Pra, le të shohim, dy minuta dhe tetë sekonda, në qoftë se ju dëshironi për të sfiduar miqtë tuaj. Çfarë atëherë do të të jetë një të marrë larg nga kjo që ne të mund të levave në përgjithësi? E pra, mendoni përsëri në ky grup i numrave, dhe mendoj se mbrapa tani për disa nga pseudokod ne kemi shkruar në të kaluarën, dhe kjo ishte pseudokod për zgjidhjen e problemit libër telefon. Ku në pseudokod I renditura një mënyrë më metodike për të përshkruar se si unë e bëri një shumë intuitiv algorithm njeriut i ndarë në telefon Libri në gjysmë, e përsëris, e përsëris, e përsëris, derisa të gjej dikë si Mike Smith, në qoftë se ai është me të vërtetë në librin e telefonit. 

Por unë lloj përdorur atë që unë do të thërrasë një qasje shumë përsëritës këtu, në njoftimin e veçantë e linjës 8 dhe linjë 11. Këto janë dëshmi të një përsëritës qasje, një qasje looping, sepse kjo është pikërisht sjellje që nxisin. Ato linja të dy thonë se shkojnë në lloj linjë tre, dhe ju mund të mendojnë për se në tuaj sy mendjen e si një lak. Kjo ju është thënë që të kthehen deri në hap tre dhe të përsëritur, përsëri, dhe përsëri, dhe përsëri. 

Por çfarë nëse ne levave një ide kyçe këtu se ne e bëmë jo hera e fundit, dhe do të thjeshtojë linjë 8 dhe Linja 11 dhe fqinjët e tyre pasi vetëm kjo, në të verdhë. Kjo nuk është krejtësisht shkurtimin pseudokod shumë, por është rrënjësisht ndryshon natyra e algorithm time. Ajo që unë jam tani duke thënë në hapin 7, në hapin 10, është për të kërkuar për Mike në të njëjtën mënyrë të saktë, por vetëm në të majtë gjysma apo gjysmë e drejtë. 

Pra, me fjalë të tjera, në qoftë se Unë të fillojë nga një hap, bie në librin e telefonit, e hapur për mes e librin e telefonit, shikoni në emrat, nëse Smith është në mesin Emri-së, thirrje Mike, tjetër nëse Smith është parë në libër, hap shtatë kërkoni për Mike në gjysmën e majtë të librit. Por kjo lloj ndjehet si është e lënë mua varur, e drejtë? Në të verdhë, është një udhëzim, por si mund të kërkoni për Mike në të majtë gjysma e librit të telefonit? Ku mund ta ketë një Algoritmi me të cilin unë mund të kërkoni për dikë si Mike Smith? E pra, kjo është na ndezur në fytyrë. Unë mund të vërtetë të përdorni të njëjtën gjë e saktë Programi në mënyrë efektive duke shkuar deri në krye përsëri dhe ri-running të njëjtën gjë e kodit. 

Pra, edhe pse kjo duhet të ndjehen të si pak e një përkufizimi ciklike ku ju jeni duke iu përgjigjur dikujt pyetje nga vetëm lloj i kërkuar njëjtën pyetje përsëri, si pse, pse, pse? Realiteti është sepse ne kemi koduar vështirë një çift të linjave të veçanta, hap i 4, cila është një nëse, dhe hapi 12, e cila është efektivisht një tjetër degë, sepse ne kemi ato e masave të përkohshme, ky algoritëm do të përfundojë në qoftë se ne gjeni Mike, ose në qoftë se ne nuk bëjmë. Por në hap 7 dhe 10 tani, ne kemi atë që ne do të thërrasë një algoritmi rekursive. Dhe recursion është me të vërtetë një ide e fuqishme që është një mendje pak lakimi në fillim, që ne tani mund të aplikojnë si në vijim. 

Merge lloj do të jetë lloj i fundit që shohim, të paktën në klasë formalisht. Dhe kjo është krejtësisht e ndryshme nga ato tre të fundit, dhe sigurisht katër fundit në qoftë se ne të përfshijë bogosort. Ja pseudokod për merge lloj. Kur në të dhënat e elementeve n, dhënë kështu një grup i madhësisë n, nëse n është më pak se 2, kthehen. Pra, pse nuk kam se mendje e shëndoshë kontrolloni parë? Çfarë është implikimi në qoftë se unë ju dorë një grup gjatësia e të cilit n është më pak se 2? Është renditura tashmë, natyrisht, e drejtë? Sepse lista ose ka një element, që është trivially renditura për shkak se është e vetmja gjë atje. Ose, është e madhësisë zero që do të thotë nuk ka asgjë për të zgjidhur, kështu nga natyra ajo është e renditura. Ka vetëm asgjë të keqe aty. Pra, kjo është i ashtuquajturi rasti ynë bazë. 

Kjo është e ngjashme në frymë me atë që ne e bëmë me Mike. Nëse Mike-së në librin e telefonit, e quajnë atë. Nëse ai nuk është aty, të heqë dorë. Kjo është një të ashtuquajtur rasti bazë, për të siguruar ky algoritmi në fund të ditës do të ndalet në rrethana të caktuara. 

Por këtu është hap i besimit tani, tjetër, lloj gjysmën e majtë të elementeve, pastaj lloj të drejtën gjysma e elementeve, dhe pastaj bashkojë gjysmave të renditura. Dhe këtu është ku ai ndjehet si ne jemi copping jashtë. Unë e kam pyetur ju për të zgjidhur n elemente, dhe unë jam i duke thënë, OK, e atë nga zgjidhja la dhe klasifikim të drejtë. Por unë jam duke thënë një të tillë gjë tjetër, dhe kjo është tema kryesore duket në intuitë deri më tani, ka ky hap i tretë i bashkimit. Të cilat edhe pse të duket kështu memec në shpirt, si vetëm të bashkojë gjëra së bashku, duket të jetë një hap i rëndësishëm drejt reassembly e dy problemeve që u ndanë në fund të fundit në gjysmë. 

Pra shkrihen lloj, le ta bëjmë këtë, në qoftë se ju do të humor mua, me një demonstrim më shumë, vetëm që të kemi disa numrat për të punuar me të. A mund të shkëmbejnë tetë stresin topa për tetë njerëz? Në rregull, si në lidhje me ju tre, ju katër në këtë seksion, pesë, gjashtë, dhe le të e 7, 8, eja lart. OK, po OK. Minus 8, atje ne do të shkojmë, plus 1. Excellent. Të gjitha të vijë të drejtë në dorë, le të shpejt ju jap numrat. Numri dy, numri tre, numër katër, numër pesë, gjashtë, shtatë dhe tetë. Unë e bëri tetë saktë këtë kohë. 

OK, kështu që të shkojnë përpara në qoftë se ju mund të, dhe le të zgjidhur në mënyrë origjinale që kemi pasur dje cila dukej si kjo, në qoftë se ju nuk do mend. Dhe le të bëjë atë para të tabelës. Në rregull, kështu që bashkohen lloj. Kjo është ajo ku ajo do për të marrë lloj i interesante, sepse unë duket të jetë duke i dhënë veten aq shumë më pak informacione sot. 

Pra bashkojë lloj para së gjithash në të dhënat e elementeve n, dhe është padyshim jo më pak se dy, është e tetë, kështu që unë kam disa punë më shumë për të bërë. Deri tani mendërisht ne si një klasë tani janë në tjetër degë, që do të thotë tre hapa. Së pari, unë kam për të zgjidhur gjysma e majtë e elementeve. Pra, si mund të shkojë për të bërë këtë? E pra, unë jam duke shkuar për të lloj mendërisht ndajnë listën këtu, ju nuk keni për të fizikisht të lëvizur, dhe unë jam i do të fokusohet vetëm në gjysma e majtë e elementeve këtu. Pra, si mund të shkoj për klasifikim një listë tani e madhësisë katër? Çfarë është algorithm ime? Së pari unë kontrolloni është n më pak se dy, jo, kështu që unë të vazhdojë në tjetër bllok përsëri. Lloj la gjysmën e elementeve. 

Deri tani përsëri, mendërisht, dhe kjo është ajo ku ju duhet të rritet një shumë të historia mendore, nëse ju do. Tani unë jam zgjidhja e majtë gjysma e pjesës së majtë. Në rregull, kështu që tani unë e quaj të njëjtë bashkohen tim sorting algorithm, është n më pak se dy? Jo, ajo është dy, kështu që unë kam për të zgjidhur gjysma e majtë, dhe gjysmë të drejtë. Pra, këtu ne do të shkojmë, lloj gjysmën e majtë. Pse nuk ju vetëm të marrë një hap përpara. Si e keni emrin? 

Audienca: Darren. 

Gjuha: Dan. Dan ka dha përpara. 

Audienca: Darren. Gjuha: Darren, bërë. A ju thoni Darren apo Dan? 

Audienca: Darren. 

Gjuha: Darren. OK, Darren ka rritur përpara dhe ai është zgjidhet tani. Dhe kjo është pothuajse një pretendim pakuptim, e drejtë? Unë vërtetë nuk duket të jetë arritur asgjë, por le të vazhdojë. Tani më lejoni të lloj të drejtën gjysma e elementeve. Si e keni emrin? 

Audienca: Luka. 

Gjuha: Luka. Eja, hap përpara. Done, kam renditura Luka. Gjysma e majtë është renditur tani dhe gjysma e drejtë është renditur tani, por përsëri, ka një hap kyç këtu. Çfarë tjetër duhet të bëni? Merge gjysmave të renditura. Tani ne jemi duke shkuar për të vetëm të gjithë me radhë dhe në këtë mënyrë, sepse unë lloj nevojë disa hapësirë ​​zeroja. Është pothuajse si këto djema jeni në një tavolinë, dhe kam nevojë për një dhomë për t'i lëvizë më. Kështu që unë jam duke shkuar për të bashkuar ju djema nga në kërkim në gjysmën e majtë dhe pjesën e djathtë. Dhe që padyshim vjen e para, la gjysmë apo gjysmë e drejtë? Pra gjysma e drejtë, kështu që le të lëvizë Luka gjatë këtu për pozicionin origjinal Darren. Dhe tani të bashkojë gjysmën e tyre e majtë në, Darren do të lëvizin drejtë atje. 

Pra ndjehet si pothuajse një efekt flluskë lloj, por algoritmi im themelor, shumë të ndryshme këtë herë. Por tani është ku gjërat marrin një pak i bezdisshëm, sepse ju duhet të Rewind mendërisht ku e kam lënë jashtë. Unë kam bashkuar vetëm gjysmave të renditura, që do të thotë unë jam ku në algorithm time? Unë kam për të zgjidhur gjysmën e duhur, e drejtë? 

Nëse ju rewind, fjalë për fjalë në video, ju do të shohim që kemi marrë për këtë pika e Luka dhe Darren nga zgjidhja e majtë gjysma e pjesës së majtë. Pastaj ne u bashkua ata gjysmave të renditura, të cilat do të thotë hapi tjetër është lloj gjysma e drejtë e pjesës së majtë. Në rregull, kështu që le të bëni këtë shumë shpejt. Në rregull, gjashtë, unë jam duke shkuar për të kërkuar ju janë të renditura tani, vijnë më përpara. Si e keni emrin? 

Audienca: Adriano. 

Gjuha: Adriano. Adriano është zgjidhet tani. Dhe si e ke emrin? 

Audienca: Alex. 

Gjuha: Alex është zgjidhet tani. Gjysma Majtas, gjysmë të drejtë, çfarë është hapi përfundimtar? Merge. Pretty parëndësishme, kështu që unë jam i do të bashkojë në gjashtë, të marrë një hap prapa, tetë, të marrë një hap prapa. Dhe tani vini re kjo është një takeaway të dobishme, çfarë tani është e vërtetë për gjysmën e majtë të listë, pa marrë parasysh se si kemi filluar? Ajo është e renditura. 

Tani ajo nuk është e renditura në Skema e madhe e gjërave, por ajo është e renditura në mënyrë të pavarur e gjysmën tjetër. Tani ajo që hap jam unë në qoftë se unë mbaj rewinding se si filloi historia? Tani unë kam për të zgjidhur gjysmën e duhur. Deri tani ne jemi mënyrë mbrapa në fillimi i tregimit, dhe le ta bëjmë këtë shumë shpejt. Kështu që unë jam duke shkuar për të zgjidhur gjysma e drejtë e të gjithë listën. Cili është hapi tjetër? Sort gjysmën e majtë të pjesës së djathtë. Sort gjysmën e majtë të gjysma e majtë të pjesës së djathtë. Dhe si e ke emrin? 

Audienca: Omar. 

Gjuha: Omar, hap përpara, bëhet. Gjysma e majtë është e renditura. Dhe si e ke emrin? 

Audienca: Chris. 

Gjuha: Chris, të marrë një hap përpara, ju janë të renditura tani. Cili është hapi kyç tani? Merge. Pra, një do të shkrihen në vendin e këtu, në qoftë se ju mund të marrë një hap prapa, dhe tre do të të marrë një hap prapa, të bashkohen. Pra, gjysma e majtë e gjysma e drejtë, është e renditura tani. Sinqerisht, ky algoritëm ndjehet si ne janë humbur mënyrë më shumë kohë se më parë, por në qoftë se ne e bëmë këtë në kohë reale, ne do të parë se çfarë takeaways do të jetë. Tani unë jam këtu, e drejtë gjysma e pjesës së duhur, më lejoni të shkoj përpara dhe të zgjidhur gjysmën e majtë. Hap përpara, si e ke emrin? Audienca: Ramsey. Gjuha: Ramsey është zgjidhet tani. Si e keni emrin? 

Audienca: Marina. 

Gjuha: Marina tani është renditur si mirë, në qoftë se ju të marrë një hap përpara. Hap kyç këtu tani po shkrihen, unë jam duke shkuar për të shembur nga dy listave të mia, majtë dhe të djathtë. Pesë do të vijë më parë, dhe shtatë do të ndodhë më pas. Dhe përsëri, kjo është e qëllimshme. Fakti që ata janë duke marrë hapa përpara dhe mbrapa ka për qëllim të përfaqësojë se ne nuk mund të bëni këtë algorithm në vend aq lehtë si lloj flluskë, dhe përzgjedhjes lloj, dhe futje lloj ku ne vetëm mbajtur shkëmbejnë njerëzit. Unë fjalë për fjalë duhet një lloj letër zeroja në të cilën për të vënë këto folks ndërsa unë bëj bashkimin, dhe pastaj unë mund të vënë ata të kthehen në vend. Dhe kjo është çelësi për shkak se unë jam duke përdorur një burimeve të reja, hapësira, jo vetëm koha. 

OK, kjo është e mahnitshme. Gjysma Majtas është renditur, gjysma e drejtë është Renditur, tani që çelësi bashkimin hap. Si jam unë do të bashkojë këtë? Pra, nëse ju do të ndiqni tim la dorë dhe dora e djathtë, Unë jam duke shkuar për të vënë në dorën e majtë në gjysmën e majtë, dora ime e djathtë në gjysmën e duhur, dhe tani unë duhet të vendosë hap pas hapi që të bashkojë në. Kush padyshim vjen e para? Numri një. Pra, eja këtu, këtu është pad tonë zeroja. Deri tani numër një, dhe njoftim çfarë unë do të bëj me të djathtën time, Unë jam duke shkuar për të lëvizur një e djathtë të dorës hap mbi të theksoj numrin tre, dhe tani unë kam për të bërë njëjtin vendim. Dhe në të vërtetë qëndrojnë të drejtë në përparme e Luka këtu nëse ju mund të, sepse kjo është e pad tonë zeroja. Pra, kush vjen më pas? Ne kemi Luka me numrin dy apo Chris me numrin tre. Natyrisht Luka, numri dy, kështu që ju të vijnë këtu. 

Por dora ime e majtë tani do të të incremented për pikë në Darren, dhe këtu është çelësi heq me bashkimi, unë jam duke shkuar për të mbajtur të bërë këtë, natyrisht, në qoftë se ju lloj të ndjekin logjikën. Por duart e mia nuk janë të do të shkojnë prapa, që do të thotë unë jam vetëm ndonjëherë duke shkuar për të e majta me procesin tim bashkimin, dhe që do të jetë kyç për të Analiza jonë në vetëm një moment. 

Pra, tani le të përfundojë kjo deri me shpejtësi. Pra, tre vjen më pas, pastaj katër vjen më pas, dhe tani pesë vjen më pas, pastaj gjashtë, dhe të shtatë, dhe pastaj në fund të tetë. Ndjehet si algorithm slowest ende, por jo në qoftë se ne të vërtetë drejtuar atë në të njëjtën lloj i shpejtësisë orën, në mënyrë që të flasin, me të njëjtën kurdisur orën si më parë. Pse? E pra, le të marrin një shikoni në rezultat në fund. 

Le të kthehemi gjatë këtu, le të më tërheqë një demonstrim vizualisht e asaj që ne vetëm e bëri. Zooming në këtu, në këtë faqe këtu, duke u thënë Firefox që ne duam të radhë deri në këtë kuti, le të thonë flluskë lloj, me të cilat ne jemi tani edhe të njohur, lloj përzgjedhje, e cila është një tjetër mjaft e hapur, dhe tani lloj sotme bashkojë, të cilat do të jetë fundi ynë klimatik. Arsyeja që u desh kaq shumë më të gjatë këtu me njerëzit dhe mua me gojë është, natyrisht, unë jam duke shpjeguar çdo hap. Por në qoftë se ju thjesht të ekzekutuar këtë, shumë më si ne e bëmë lloj flluskë dhe përzgjedhja lloj jo vetëm vizualisht, watch se sa shumë më efikase kjo leveraging e ndarje dhe pushtues mund të kur zbatohet në një grup të të dhënave që është as madhësia e tetë, por edhe më shumë, shumë më e madhe. Unë ju jap bashkojë lloj, krah për anë me këto algoritme të tjera. Kjo do të merrni të dhimbshme shpejt, dhe duke i dhënë fund nuk është veçanërisht klimatik, ata vetëm të përfundojë renditura. Por kryesore marr me vete është se shikoni se sa shpejt shkrihen lloj ishte, nëse ju mendoni se unë jam vetëm lloj messing me ju. Nëse ne e bëjmë këtë një herë të fundit, Le të rifreskoni këtë, le të kthehemi dhe zgjidhni flluskë lloj, dhe vetëm për shkelma, le të zgjedhin shtënie lloj, vetëm për masë të mirë. Dhe këtë herë përsëri, le të zgjidhni bashkojë lloj dhe të le të në të vërtetë të drejtuar këto krah për krah. 

Dhe kjo nuk është, në fakt, një pikë për shans. Ajo që unë kam bërë në mënyrë efektive është që unë kam ndarë kontributin tim në gjysmë, përsëri, dhe përsëri, dhe përsëri. Dhe nuk ka vetëm kaq shumë herë ju mund ndajnë kontributin tuaj në gjysmave, la dhe të drejtë. Çfarë është formula që do të vazhdojmë të shohim që përshkruan ndarjen në gjysmë përsëri, dhe përsëri, dhe përsëri, dhe përsëri? 

Audienca: Identifikohu n. 

Gjuha: Identifikohu n. Por atëherë nuk është një hap tjetër i rëndësishëm, kjo algorithm nuk është log n hapa. Nëse do të ishte vetëm log n hapa, ne do të jetë në të njëjtin problem si më parë, ku ne nuk mund të jetë që çdo gjë të zgjidhet. Ju duhet të shikoni në minimalisht elementet n të jetë i sigurt n elemente janë të renditura, përndryshe ajo është një hap i besimit. 

Pra, kjo është log minimalisht n hapa, por ajo që për këtë hap të rëndësishëm bashkimin ku unë u bashkua gjysma ime e majtë dhe të djathtë gjysmë dhe eci nëpër skenë? Sa hapa është që të bashkojë? Është n, por nuk e kam vetëm bashkojë kohën përfundimtar. Në secilin prej këtyre thirrjeve mbivendosur, në çdo e atyre shkrirja mbivendosur, unë ende të renditura. I shkrirë këto dy djem, atëherë këto dy djema, atëherë këto dy djem dhe kështu me radhë. 

Kështu që unë kam bashkimin përsëri, dhe përsëri. Sa herë? Kështu që çdo herë që unë të ndarë Lista në gjysmë, kam bërë një bashkim. Ndani listën në gjysmë, të bëjë një bashkim. Pra, nëse e ndarë listën mund të bëhet herë log n, dhe shkrirja në fund të fundit merr n hapa, ajo mund të jetë tani e sipërme lidhur në drejtimin Koha e algorithm tonë? n log n. 

Dhe me të vërtetë, kjo është ajo që ne kemi arritur këtu. Kështu ndjehen që ju shihni me sy kur këto tri gjëra të drejtuar krah për krah është katror n kundër n katror kundër log n n. E cila në thelb ne do të shohim, jo vetëm sot, por në të ardhmen, është shumë, shumë më të shpejtë. Një raund i duartrokitje për këta njerëz, Unë do të shpërblejë ata me topa stresit. Le të shtyjë sot këtu, dhe ne do të shohim të hënën.