[Powered by Google Translate] [Java 3, vazhdoi] 

[David J. Malan - Universiteti i Harvardit] 

[Kjo është CS50. - CS50.TV] 

Dakord. Mirëpritur mbrapa. Kjo është CS50 dhe ky është fundi i javës 3. 

Pra, për ata që vitin e kaluar të panjohur, Harvard nisur atë që është quajtur Innovation Lab, ose I-laborator, e cila është një ndërtesë mrekullueshme nëpër lumi në kampus hbs së që është e hapur për studentët kolegj, studentët GSAS, studentë nga e gjithë kampus të gjithë, përfshirë fakultet, dhe kjo është një vend që do të vijnë së bashku për të punuar në gjëra të reja, gjërat veçanërisht sipërmarrëse në qoftë se ju dhe 0 apo më shumë miq janë duke menduar për të bërë diçka sipërmarrëse ose gjatë kësaj klase, pas kësaj klase, apo më tej. 

Pra, një nga gjërat që ata bëjnë gjatë afatit J është këto udhëtime, një nga të cilat është tek New York, njëra prej të cilave është tek Silicon Valley. Hapësirë ​​është shumë e kufizuar, por kjo është një mundësi për të fshij supet me MBAs dhe studentë të diplomuar nëpër kampus dhe në fakt kalojnë kohë në ato zona përkatëse biseduar deri startups, të biseduar deri sipërmarrësit dhe si. Pra, nëse të interesuar, të kontrolluar këtë URL këtu. Ajo është gjithashtu në dispozicion në slides online. 

Mund të kemi ton poshtë audio shtëpi vetëm pak? Nëse ju do të donte të bashkohen me ne për drekë të premten, 1:15 pm Fire & Ice në, ju lutem kreu atje. Apologies nëse formulari është plotësuar tashmë nga koha që ju të merrni atje. Por ne do të vazhdojmë këtë traditë tutje. 

Sot ne vazhdojmë diskutimin nivel më të lartë të problemeve të ndryshme që ne mund të zgjidhur, duke u përqendruar shumë më pak, sot të paktën, në kodin dhe shumë më tepër për idetë. Pra, mendoni përsëri në javën 0 kur ne grisi një libër telefoni në gjysmë, objektivi i të cilit ishte për të bërë diçka, pa dyshim, pak dramatike por për të dërguar në pikën që kërkoni nuk duhet të jetë, domosdo, aq e qartë në shikim të parë si ju mund të mendoni. Dhe zgjidhjen e problemeve në përgjithësi nuk mund domosdoshmërisht të jetë gjithmonë më i mirë - Zgjidhja më e qartë nuk mund të jetë domosdoshmërisht më të mirë. Pra, kemi pasur këtë libër telefoni dhe, sinqerisht, të gjithë ne në këtë sallë kishte instinktet, më shumë gjasa, do të fillojë në mes kur të kërkoni për Mike Smith dhe pastaj të shkoni majtas ose djathtas bazuar në çfarëdo shkronja të alfabetit, ne ka ndodhur të përfundojë deri në. 

Por kjo ide e thjeshtë që ne njerëzit kemi marrë për të dhënë për kaq shumë kohë me të vërtetë duhet të fillojnë të vijnë në ballë e mendjen tuaj sepse si problemet merrni shumë më komplekse se një libër telefoni, ato thjeshtë, të njëjtat njohuri të shkëlqyer janë ato që janë do të lejojë na për të zgjidhur problemet më të ndërlikuara dhe më interesante, në mesin e tyre disa nga gjërat që ne kemi marrë për të dhënë tashmë këto ditë. Miliarda e faqeve web atje, dhe ende Google dhe Bing dhe si janë në gjendje për të gjetur gjëra për ne si kjo. Kjo nuk po ndodh duke përdorur një kërkim linear, duke kërkuar nëpër të gjitha faqet web të mundshme. Facebook është në gjendje të ju them që të gjithë miqtë tuaj janë ose miqtë e miqve, dhe se shumë mund të bëhet në dukje në një çast këto ditë edhe pse ata kanë miliona e përdoruesve. 

Dhe kështu si ne fakt zgjidhin problemet në atë shkallë në fund do të zvogëlojë me idetë kemi shikuar në në javën 0 dhe pak më sot. Ne nuk do të ri-ekzekutuar këtë algorithm, por kujtoj ne gjithashtu bëri në javën 0 këtë ushtrim ku ne kishim të gjithë të qëndrojë lart, të marrë numrin 1, dhe pastaj kemi pasur të gjithë vetë-akuzë nga pairing jashtë, duke shtuar numrat tuaj së bashku, atëherë gjysma e bandës u ul në çdo përsëritje. Pra, ne shkoi nga 500 studentë të 250-125 dhe kështu me radhë. Por siç kemi thënë të hënën, idenë e fuqishme aty ishte se në qoftë se ne dyfishuar madhësinë e këtij problemi dhe të gjithë fëmijët e Drejtësisë ose nga KE 10 u kthye në dhomë dhe u bashkua me ne, mirë, ne ndoshta mund të llogarisë atë grup të tërë përgjithshme vetëm me përsëritje më e madhe e 1 lak, sepse ata vetëm do të ndoshta të dyfishtë madhësinë e ose në rastin e KE-së 10 pak më shumë se dyfishi i madhësisë. Dhe kështu që ne do të duhet të kalojnë pak më shumë kohë, por ne nuk do të duhet të shpenzojë 400 ose 700 hapa më shumë. 

Vetëm për të pikturuar këtë foto në një mënyrë që është më pak abstrakte, le të mos kemi të gjithë të qëndrojë deri. Por në qoftë se ato prej jush që zgjodhi për t'u ulur në orkestër sot nuk do mend këmbë, le të shohim nëse ne mund të kuptoj se midis jush që personi është i lartë duke bërë të njëjtin lloj algorithm krahasuese. Kështu që nëse ju jeni ulur në orkestër, keqardhjet e mia, por Hapi 1, të qëndrojë lart; Hapi 2, palë me askënd jashtë aty pranë ju, kuptoj se kush është shtatlartë, dhe të ulen, nëse ju jeni të shkurtër. Pastaj të përsëritur. [Students gumëzhimë] 

Rregull. Rregull. Njëra është lënë në këmbë. Çfarë është emri juaj? Andrew >>. 

Andrew, ju jeni personi i lartë në seksionin e orkestër sot. 

Urime. [Duartrokitje dhe brohoritje] Okay. Kanë një vend. Pra, kemi gjetur Andrew. Por sa kohë do të kanë marrë mua, për shembull, për të gjetur Andrew në këtë seksion orkestër prej 50 + apo më shumë njerëz? Unë mund të ketë marrë një qasje mjaft të thjeshtë dhe të filloni këtu. Dhe unë kam 2 persona të qëndrojë deri dhe unë vetëm krahasimin e tyre, dhe atëherë unë them kush është pak më i shkurtër, "Mirë, ju të ulen" dhe unë jam duke shkuar për të kujtuar që personi ishte shtatlartë. Pastaj unë e përsëris, e përsëris, të përsëritur, dhe unë rri tek personi e lartë derisa të gjej dikë pak më shtatlartë se ata, në të cilën pikë Personi pak shkurtër ka për të pastaj ulen. Por në atë algorithm në këtë seksion orkestër, në qoftë se ka n prej jush, sa hapa është se algoritmi do të marrë? >> [Student] N. 

Ajo do të marrë n, e drejtë, sepse në rastin më të keq, në mënyrë që të flasin, personi i lartë është person shumë i fundit që kam marrë për të vetëm nga fat i keq rastit. Pra, në rastin më të keq, koha drejtimin e këtij algoritmi është lineare, është n, ku n është numri i përgjithshëm i njerëzve në hapësirë, madhësia e problemit. Çka në lidhje me këtë algorithm? Fakti që të gjithë ju u ngrit dhe pastaj përsëri gjysma prej jush u ul, gjysma prej jush u ul, gjysma prej jush u ul. Sa hapa duhet që kanë marrë në qoftë se ka n prej jush këtu? [Student] N log n. Kjo do të jetë >> keq. Identifikohu n. 

Pra hyni n, edhe në qoftë se ju nuk mbani mend mjaft çfarë është logaritmi, tani për tani, vetëm të vlerësojmë se ajo lidhet disi me këtë përgjysmuar dhe të përgjysmuar dhe të përgjysmuar. Ajo nuk duhet të jetë një faktor i 2. Kjo mund të jetë një faktor i 3. Por kjo është kjo përsëritje e të njëjtit lloj e faktorit të tillë që madhësia e problemit fillon këtu por pastaj menjëherë shkon këtu, atëherë këtu, atëherë këtu, atëherë këtu. Ju nuk jeni duke marrë kafshon vogla nga problem, ju jeni me të vërtetë shëndoshë larg në atë me e madhe ra bie poshtë çdo kohë. Pra, kemi pasur 50 njerëz, pastaj 25, pastaj 12 ½ ose 13 njerëz në këmbë, pastaj 6 ½ dhe kështu me radhë deri në fund të rrinte vetëm Andrew u la. Pra, ne jemi duke shkuar për të thirrur atë log e n, dhe ju mund të parashikoj këtë si më poshtë. Kujtojnë këtë foto këtu, ku një algoritmi linear është si linjë e kuqe atje, vijës së verdhë ishte numërimi me 2s algoritmi që kemi përdorur për studentët e numërimit në të kaluarën, por sot Grail shenjtë do të mbetet kjo linjë e gjelbër ku në qoftë se kemi dyfishuar numrin e njerëzve në pjesën orkestër apo thjesht thënë, ferr, le të kemi të gjithë në dhomën e tërë ngrihen jo, një marrëveshje e madhe sepse ne pothuajse dyfish sa njerëz janë këtu poshtë, 1 përsëritje më shumë, nuk është një problem. 

Ne kemi gjetur Andrew ose kushdo që ndodh të jetë shtatlartë se Andrew në lozhë poshtme ose në ballkon. Pra, këtë ide e thjeshtë se ne e mori aq shumë për të dhënë në një libër telefoni, kuptojnë se ka aq shumë vende të ndryshme në të cilat ne mund të aplikojnë atë. Vetëm për të mu disa zhargon - në fakt, jo zhargon të parë, më lejoni të shkoj në këtë foto këtu. Tani për tani kemi biseduar për n dhe n / 2 dhe pastaj hyni nga n, por ne me siguri mund të dalë me, si ne do të gjatë të semestrit, lloj tjetër të formulave matematikore për të përshkruar këtë nocion të përgjithshëm për drejtimin e kohës. Këto janë jashtë kontekstit për tani, sepse ne do të shohim para se të gjatë Algoritme se këto në fakt përfaqësojnë. 

Por vini re këtu n linear linjë, vijë e drejtë, në fakt është shumë e ulët treguar tani. Kjo është lloj i një iluzioni optik në atë që ne vetëm të ndryshojë atë që boshti x paraqet dhe boshti y, dhe ne mund të bëjë një pikë lineare në çdo drejtim ne duam. Por arsyeja që ajo është aq sa duket tani banesë është për shkak se ne kemi nevojë për të bërë vend në këtë grafik për herë shumë të ngadalshme running. Tani për tani, e di se ka disa algoritme mjaft të këqija në jetë, disa prej të cilave nuk do të marrë hapa n ose, më mirë akoma, hyni hapa n, por më shumë. Pra, mbi vijën n këtu në njoftimin e poshtme ka n log n herë, dhe ne do të shohim se çfarë kjo do të thotë para se të gjatë. Më lart se është n katror, ​​dhe ne nuk kemi parë ndonjë algoritme n katror ende, por ne jemi gati për të. Dhe kjo duket me të vërtetë e keqe. Ka 2 te n, diçka eksponenciale, gjë që ndihet edhe më keq. Dhe akoma, interesant, atëherë nuk ka n Cubed, i cili në qoftë se ju jeni lloj i të menduarit përpara, në qoftë se ju lloj i bëni matematikë, 2 në n fakt bëhet shumë straighter, shumë më e lartë se sa deri n Cubed në qoftë se ju shikoni në akset mjaft larg jashtë. Pra vëreni tani këto akse janë arbitrare 2-10 në boshtin x. 

Dhe çfarë do të thotë kjo? Kjo do të thotë që njerëzit të 2 10 njerëz në dhomë. Kjo është e gjitha mjetet x: madhësia e problemit, çfarëdo konteksti është. Dhe një aks vertikal tani është numri i sekondave apo numri i hapave - disa njësi të kohës. Por vini re se kjo është 0-60 dhe 0-10. Por nëse ne lloj zoom jashtë, si ju mund të në Excel ose disa software charting, dhe ne do të shkojmë deri në 200.000, vëreni se diçka si 2 deri n është duke shkuar për të krejtësisht trullos herë drejtimin e n katror, Cubed n, n log n - çdo gjë që ne kemi biseduar rreth deri tani. Dhe ende është kapur kur ju filloni duke folur për gjëra të tilla si Facebook ku ju keni shumë, shumë, shumë njerëz të ndërlidhur të gjitha, ju keni n popullin, secili prej të cilëve mund të kenë sa më shumë miq n nëse të gjithë është lloj i buddy-buddy në botë, mirë, kjo është herë n n tashmë, kështu që është n miqësi katror mundshme, të paktën në 1 drejtim, n miqësi katrore mundshme. Kështu që sugjeron se tashmë kërkim grafik social Facebook, në mënyrë që të flasin, mund të fillojë të shprehet në këto lloje të formulave. 

Ne do të kthehen dhe të bëjë këtë shumë më konkrete, por tani për tani, objektivi për javët e ardhshme many do të jetë i sigurt që të mos shkojë në lidhje me zbatimin e algoritme ose kod që deri në fund të marrë kohë sa më shumë si diçka si kjo. Por gjëja interesante në lidhje me shkenca kompjuterike në qoftë se ju të vazhdojë më në këtë fushë marrë klasat si CS121, CS124, dy prej të cilave janë kurse teoria, është se nuk janë në fakt disa probleme që ekzistojnë në këtë botë që në thelb, me sa dimë, nuk mund të zgjidhet ndonjë të shpejtë se e keqja e këtyre grafikët fakt sugjeron. Kështu që nuk ka shumë probleme të hapura në këtë botë për të bërë shumë më mirë se njerëzit kanë deri tani. 

Pra, le të fillojë atëherë me këtë shembull. Ne pamë luftë Sean me këtë aparat për të, të gjithë shumë awkwardly në video. Por realiteti ishte kur Sean u ngarkua me gjetjen në një bord si ky numri 7, kujtoj se kam thënë se, "Nuk është diku pas këtyre copa letre apo dyerve të bardhë "Numri 7. Sean, të gjeni atë për ne." Dhe kjo ishte mrekullisht vështirë për të parë sepse ai ishte me të vërtetë duke luftuar me këtë problem. Por realiteti ishte Sean bëri si dikush në dhomë mund të ketë bërë. Ai mori një pak më shumë se një person tipik mund të ketë, por ai supozohet se ka pasur disa mashtrim për këtë problem, ai supozohet se ai ishte humbur diçka. Dhe kjo nuk ka ndihmuar që të qindra e syve duke u poshtë mbi të. 

Por realiteti ishte në qoftë se input për problemin është një bandë e numrave të rastit dhe ju jeni duke kërkuar për të gjetur numrin 1 të tillë, mirë që ju mund të bëni është të kërkoni lineare. Të fillojë në të majtë, të shkojë në të djathtë, ose të fillojnë në të djathtë, të shkojë në të majtë. Mënyrë retroaktive, ne mund të jetë duke menduar, "Sean, pse nuk ju vetëm të fillojë nga fund të tjera?" Well, 7 mund të ketë po aq e lehtë qenë këtu rastësisht, por unë qëllimisht e vënë atë atje, sepse unë i realizuar artistikisht se ai nuk do të fillojë në fund. Kështu që unë lloj i manipuluar situatën, por rastësisht 7 mund të ketë qenë kudo. Pra, duke filluar nga fundi djathtë mund të kishte qenë më mirë atëherë, por çka nëse vitin e ardhshëm unë të lëvizin diku tjetër 7? Kjo nuk është një zgjidhje krejtësisht të re ndaj problemit - duke filluar nga 1 fund apo tjetër - kur ju jeni dhënë asnjë supozime të tjera. Pra Sean filluar duke kërkuar përmes numrave dhe ai tha: "5. Kjo nuk është këtu." Pastaj ai shkoi këtu dhe pa 19, atëherë ai heshti për rreth 20 sekonda, atëherë ai hapi këtë për 13, dhe pastaj u bë e qartë se nuk duket të jetë një model këtu. Ajo nuk ishte 1, 2, 3, 4 ose si. Ka pasur mangësi në numra, të cilat nuk ndihmojnë. Dhe gjithashtu, fakti që kam përdorur këto copa letre të lirë për të mbuluar numrat në fakt është e qëllimshme, sepse në qoftë se unë hequr të gjitha këto copa letre, shumica prej nesh, Sean përfshirë, ndoshta do të kishte lëshoi ​​lloj macroscopically në dërrasën e zezë dhe tha: "Oh, 7 është padyshim e drejtë atje." Ne e bëmë atë çast. 

Dhe kjo mund të jetë mënyra se si truri i njeriut punon në një farë mase, por në realitet, sytë e tij apo mendje ishte ndoshta skimming numrat nga e djathta në të majtë, majta në të djathtë, të mesëm në jashtë - diçka po ndodhte fiziologjikisht tillë që ai ndjehet si ajo që po ndodhte në çast, por shanset janë edhe brenda vendit ka pasur një lloj i metodologjisë për të gjetur 7. Dhe me të vërtetë, tani që ne jemi duke folur për vargjeve dhe të dhënat e strukturave dhe brenda kujtesën e një kompjuteri, e vetmja gjë që ne njerëzit mund të bëni është të shikoni në vende të kujtesës individuale 1 në një kohë. 

Pra, çdo vend tjetër mund edhe të mbulohen me disa copë letër sepse ne nuk mund të shohim atë anyway. Ne vetëm mund të bëjmë gjë 1 në një kohë. Pra, në këtë rast, në rastin e Sean, ne kemi shkuar këtu dhe pastaj kemi shkuar këtu dhe pastaj kemi shkuar këtu, këtu, këtu, këtu, mori zgjuar deri në fund dhe vetëm lloji i skipped këtë një mënyrë arbitrare dhe e gjeti atje 7. Kjo nuk ishte veçanërisht e veçantë. Kjo shumë ishte jashtë rendit. Por ai më në fund gjeti 7. Por tani takeaway është me të vërtetë mirë që ju mund të bëni kur të jepet asnjë informacion përveç numrave të renditura rastësisht do të fillojë nga e majta apo të fillojë nga e djathta. Apo dreq, ju mund të hapur dyert rastësisht, por edhe atëherë çfarë do të thotë të jetë e rastit? E pra, ne do të duhet të disi formalizuar çfarë do të thotë për të filluar këtu, pastaj shkoni këtu, pastaj shkoni këtu. Sean bëri të madh, dhe kjo ishte vetëm argëtim për të shikojnë. Çfarë ndodh nëse ne ndryshojmë në vend problemin pak dhe të sjellin deri Sean këtij viti, në qoftë se ju do? Dikush do të jenë të rehatshme vijnë në skenë dhe zgjidhjen e një problemi paksa të ndryshme dhe shfaqeshin në kamera? 

Le të shkojnë përtej orkestër, sepse ju djema kanë qenë të përfshirë mjaft sot tashmë. Si rreth në rozë, në kapelë? Vijnë më poshtë. Cili është emri juaj? Alex >>. Alex >>. Rregull. Pra, Alex do të jetë Sean këtë vit dhe do të shfaqet në disa vitet e ardhshme vlerë të CS50 ligjëratave. Alex, nice to meet you. >> Nice to meet you too. Sfida në dorë për ju është se ju keni atë një pak më e lehtë në se unë jam i thënë ju numrat njëjtat janë këtu, por ata janë të renditura tani. Kështu që tani qëllimi juaj është për të gjetur numrin 7. Dhe në të vërtetë, ne duhet të vërtetë e bëjnë këtë - you're lloj të mashtrimit, si një kompjuter nuk do, duke shikuar në atë që numrat ishin një moment më parë. Me shkumës kjo në fakt nuk do të ndihmojë të gjithë se shumë, por le të pretendojë se ju nuk e dini se çfarë array origjinal është. Të gjithë ju e dini tani është se ju keni një rrjet të numrave të renditura që mund të ketë boshllëqe në mes tyre, dhe qëllimi juaj është për të gjetur numrin 7. Si do të ju, një njeri i arsyeshëm që, të shkojnë për të gjetur numrin 7? 

Shkojnë nga të ulët të lartë? Mirë >>. Shkojnë të ulët të lartë. Dhe mos heq tyre. Le të heqë ato në mënyrë që ne mund të ripërdorimin e tyre. Mirë, kështu që 1. Prisni. Para se ju mbani duke shkuar, që ishte 1, qartësisht të gabuar. Pra, çfarë po ndodh me mendjen tuaj të ardhshëm? Çfarë është veprim tuaj të ardhshëm? Një tjetër. Mirë >>. Një tjetër. Mirë. 3, në mënyrë korrekte. Çfarë është veprim tuaj të ardhshëm? Mbani në vazhdim e sipër. >> All drejtë. Mbani në vazhdim e sipër. 5. Pra, të mbajtur në vazhdim e sipër, dhe më lejoni t'ju dorëzojë këtë për brezat. 7. Excellent >>. Shumë mirë. Gjetur numrin 7. [Duartrokitje] Kështu që ishte e mirë, por shumë e Sean gjetur numrin 7. Dhe unë argumentojnë se ju nuk e keni shfrytëzuar të vërtetë këtë pjesë shtesë të informacionit, e cila është se këto numra janë të renditura. Pra, mund të bëjmë më mirë? Any suggestions këtu? Po, në prapa. [Student] Kërko Binary. >> Kam asnjë ide se çfarë kërkoni binar është. 

[Student] Filloni në mes. Fillimi >> në mes. Rregull. Pra, le të shohim nëse ne mund të merrni atje. Pra, nëse ju jeni duke thënë në vend të fillojë nga mesi, të shkojnë përpara dhe të hapë derën e mesme. Ka 8 prej tyre, kështu që ju jeni do të duhet të zgjedhin në mënyrë arbitrare një paksa në të majtë ose në të djathtë. Rregull. 7! [Duartrokitje] Very nice. Mirë, por ku ishin ne duke shkuar me këtë? Le të supozojmë vetëm për të thyer kravatë ju kishte filluar këtu për shkak se në mënyrë të barabartë mund të ketë ndodhur si. Ne vetëm ka ndodhur të dini se 7 ishte atje. Pra, kjo është 13. Pra, nëse ata janë të renditura dhe ne sapo ka filluar në mes, çfarë do veprim optimal tjetër kanë qenë? Shkoni e majta. Dhe kështu këtu vjen shembull librin e telefonit përsëri. Nëse 13 është këtu dhe ne e dimë lista është e renditura, atëherë të gjitha këto copa letre janë jointeresant për ne tani sepse ne tashmë e dimë se 7 duhet të jetë e majta në qoftë se këto numra janë të renditura dhe kemi gjetur 13. 

Pra, çfarë është veprim tuaj të ardhshëm këtu? Go >> në të majtë. Mirë >>, mirë. Pra shkoni në të majtë, dhe - të presin, hej, hej, hej. Kjo është cheating. Pra keni gjetur 7, por ajo ishte algorithm ne vetëm aplikuar? Fillojnë në mes. Mirë >>. Pra, çfarë është shtrirja logjik i kësaj ideje të njëjtë? Oh, për vetëm këto. Pikërisht >>. Kështu që unë >> filloni këtu. Mirë >>. Kështu që tani ne kemi shkuar pak në të majtë përsëri. Kjo është 3. Por takeaway interesante tani është që një të bëjë që ju nuk keni për të cilët brengoseni? Këto 2. Këto >> 2. Deri tani kjo mund të shkojë larg, kjo mund të shkojë larg. Tani problemi që ishte 8 më pas ishte 4 Madhësia tani është madhësia 2. Ne jemi duke marrë shumë të ngushtë. Përsëri, të shkojnë në mes të këtyre 2 elementeve. 

Rregull. Pra, kjo është lloj i pafat që tani ne jemi gjithmonë do largua sepse ne jemi arrestimi poshtë. Por kjo është në rregull, sepse tani kemi hedhur këtë larg dhe çdo gjë tjetër, duke i lënë të na me vetëm 7. Le të japim një raund të duartrokitje. Ne kemi gjetur 7 përsëri. [Duartrokitje] Okay. Sigurt. Hang on vetëm për 1 sekondë më tepër. Edhe pse kjo lloj tjetër procesi i mori një pak më shumë se e kemi ndjerë se do, sinqerisht, instinktet tuaja të para ishin më të mirë, e drejtë? Ne kemi gjetur 7 menjëherë. Por ne do të kemi gjetur 7 më të shpejtë, pa marrë parasysh se çfarë, në këtë shembull kundrejt ky sepse në qoftë se numrat janë të renditura të gjitha, ashtu si faqet në një libër telefoni, ju mund të vërtetë pres gjysmën e problemit përsëri dhe përsëri dhe përsëri. Dhe kjo nuk është fare aq e lehtë për të parë këtë me vetëm 8 numra në krahasim me një libër 1,000 faqesh telefonit ku ju shoh me të vërtetë atë vizualisht, por në këtë rast këtu, kur ishte në kërkim për Sean 7, sa hapa në rastin më të keq do të ketë marrë atë? >> [Student] 7. 7 në rastin më të keq. E pra, në rastin më të keq nuk e 7 nëse ka 8 dyer këtu. Ajo do të marrë atë 8 hapa. 

Pra, nëse ka dyert n, ajo mund të ketë marrë Sean nja dy vjet më parë n hapa. Tani, në rastin tuaj, Alex, duke pasur parasysh se këto numra janë të renditura - dhe ne mund të lloj këtë konkludoj nga ku ne kemi qenë deri më tani në këtë histori - çfarë është koha drejtimin e algorithm më inteligjente e Aleksit e filluar nga mesi dhe pastaj përsëritur? [Student] 3. Pra, ajo >> do të jetë 3, përafërsisht, në qoftë se ju shkoni 8-4 me 2 për 1. Pra 3 hapa ose, më në përgjithësi, kjo është log n përsëri. Çdo herë që ju jeni duke përgjysmuar dhe të përgjysmuar dhe të përgjysmuar dhe të përgjysmuar, kjo është një shprehje e kësaj ideje të log n. Dhe kështu që do të keni marrë ju vetëm 3 hapa, dhe në të vërtetë ai e bëri sapo hapëm dyert e përgjysmuar dhe përgjysmimi, ndërsa kjo do të marrë disa Sean 7 ose 8 hapa. Pra, ju falënderoj për të qenë me ne gjatë këtij viti. >> Faleminderit. Bukur takimit ju. Faleminderit për Alex. Gjithashtu >>. [Duartrokitje] 

Çfarë është atëherë implikimi i vërtetë i kësaj? Tani imagjinoni se kjo nuk është 8 dyer, të cilat, sinqerisht, të gjithë ne mund të gjeni diçka pas 8 dyert shumë shpejt vetëm duke marramendës copa e letrës dhe shkon me instinktet tona. Por, çka nëse kjo është një milion dyert? Çka nëse kjo është 4 miliard dyert? Në rastin e 4 miliardë dyerve, ju jeni të vërtetë do të duan të shkojnë me algorithm e Aleksit, binar kërkimit si ne do të fillojnë duke e quajtur atë, ose përça dhe sundo, më në përgjithësi, ku ju mbani pergjysmimin dhe përgjysmimin e problemit, sepse në qoftë se ju keni 4 miliard dyert, sa herë mund të ju pres 4000000000 në gjysmë? [Student] 32. Është fakt >> 32. Ju mund të punojnë këtë jashtë në një copë letër apo në kokën tuaj. Ju shkoni 4000000000-2000000000 to 1 miliard gjysmë miliardë, në 250 milionë euro, dot, DOT, DOT. Dhe në qoftë se ju bëni matematikë jashtë, ju do të jeni me të vërtetë të marrë 32, dhe që në fakt ka të bëjë me shkencën kompjuterike, sepse ne zakonisht llogariten në kompetencat e 2. 2 në 32 ndodh tek jenë 4 miliard. Kështu që nuk ka shumë rëndësi për këto lloje të pushteteve të 2 në shkenca kompjuterike. 

Por ajo që për 8 miliard? Sa hapa është se do të marrë nëse ka 8 miliardë dyert? [Student] 33. Kështu >> 33. Çka nëse nuk ka 16 miliard dyert? Sa hapa është se do të marrë? [Student] 34. 34 >>. Ne mund të vazhdojmë këtë lloj të ndotë ad. Por kjo është një gjë e fuqishme. Ju mund të futur miliarda inputeve më shumë për problemin tuaj, por, jo e madhe, ju vetëm të marrë 1 pickim shtesë nga ajo dhe në këtë mënyrë na jep diçka si kërkim binar ose përça dhe sundo, më në përgjithësi. Por unë jam lloj i mashtrimit këtu, apo jo? Në rastin e algorithm e Aleksit, ajo kishte një avantazh mbi Sean. Ajo e dinte se këto numra janë të renditura, por Alex nuk kanë për të zgjidhur ato veten. Unë paraprakisht erdhi deri në dërrasë e zezë dhe llojin e bëri të sigurt se unë tërhoqi të gjithë ata në mënyrë renditura, atëherë unë i mbuluar ato me letër. Por sa shumë punë ka që marrin mua? Po të kishim filloi me këto numra në një farë mënyrë në dukje të rastit - në këtë rast këto shifra të thjeshta, 1 deri 8 këtu - si do të shkojmë në lidhje me klasifikimin e këtyre vlerave? Nëse keni qenë një njeri i dhënë këtë detyrë, çfarë lloj i qasjes intuitive do të merrni në klasifikim një bandë e tërë e numrave? Këto gjëra ishin hedhur jashtë si puzzle copë. Po. 

[Student] Unë do të marrë çdo numër dhe të krahasojnë atë me çdo një dhe do të mbajë në të majtë. Mirë >>, mirë. Pra, të marrë çdo numër, krahasuar atë me një tjetër me të, dhe pastaj vetëm i mbajnë duke lëvizur së bashku, lloj listën e rejiggering gjëra si ju shkoni. Pra, këtu kemi një shans për ndoshta një pak më shumë njerëz për të marrë të përfshira. A kemi 8 vullnetarë të tjerë të cilët do të duan për të dalë? Një presion më pak që ju nuk jeni i vetmi. 1, 2, 3, 4, 5, 6, 7, 8. Vijnë më poshtë. Ju djema do të jetë numri 1 deri 8. Le të shohim nëse ne nuk mund ta bëjë këtë klasifikim për Alex shumë në të njëjtën mënyrë kam bërë atë më parë. 1, 2, 3, 4. Të shkojnë përpara dhe në qoftë se ju do, vijë deri në skenë në mes të muzikës dhe qëndrimin mua këtu në të njëjtën mënyrë si rrëshqitje në ekran. Uh-oh. Ne do të punojmë me ju në shembull tjetër. Oh, prisni, prisni. Këtu ne do të shkojmë. Prisni. Shembulli tjetër është tani. Këtu ju shkoni. Numri 8. Come on up. Dakord. Rendit sipas veten për këtë. Rrëshqitje vetëm pak në anën e muzikës të qëndrojë këtu. Pra, ne kemi 4, 2, 6 - të marrë në atje, mbi këtu, ka të drejtë - 3. Po. Rregull. Ju shkoni mbi këtu. Jo, ju qëndroni atje. Po, të drejtë atje. Jo unë jam gabim. Drejtë atje. Mirë, shumë mirë. Rregull. Pra, tani le të zgjidhur ato në një mënyrë rritje. 

Si mund të shkojë për të bërë këtë? Algoritmi që u propozua një moment më parë ishte pse nuk kemi vetëm të krahasuar folks të cilët janë lloj tjetër për njëri-tjetrin dhe pastaj të rregullojmë gabime, duke lëvizur nga e majta në të djathtë. Pra, këtu kemi 4 dhe 2, natyrisht jashtë rendit. Le të bie në ujdi me ju. Rregull. Pra, tani unë jam duke shkuar për të lëvizur poshtë vijës. 4 dhe 6, Jo. [Qeshura] 6 dhe 8, shumë e mirë. 8 dhe 1, më lejoni të ju djema swap. Dakord. Pra, 8 dhe 3, shkëmbim ju djema. 8 dhe 7, më lejoni të ju djema swap. 5 dhe 8, të shkëlqyera. Unë ju jap një listë të renditura. Dakord. Pra, jo mjaft. Por kjo është më mirë për shkak se numrat e mëdhenj - Rasti në pikën 8 - kam lloj bubbled deri nga e majta në të djathtë. Kështu që unë kam 1 prej tyre e drejtë, por ai ndjehet si ky nuk mjaft të zgjidhur problemin. 

Pra, çfarë do të propozojë të bëjmë tjetër? >> [Student] Vazhdojmë të bëjmë atë. Ne mbajmë >> bërë atë. Dhe të kuptojë, përsëri, ne kemi vendosur gjërat vetëm nga të paturit e gjithë njerëzit lloj inteligjente organizoni veten bazuar në atë foto, por tani ne duhet të jetë shumë më metodike. Ne duhet të jenë të algorithmic në lidhje me atë sikur ne jemi duke shkruar kodin - në këtë rast pseudokod verbale. Pra më lejoni të vetëm të provoni këtë përsëri. Që ka punuar mjaft mirë. Ajo nuk ka zgjidhur atë. Por kur ajo dyshim, vetëm të përpiqet dhe të provoni përsëri. Pra, 2 dhe 4, nuk ndihmojnë më. 4 dhe 6. Ah! 6 dhe 1, pak më mirë tani. 6 dhe 3, të mirë. 6 dhe 7, 7 dhe 5, 7 dhe 8, i mirë. Dhe ju e dini, unë ndoshta mund të injorojë 8 tani sepse ai është në fund të listës. Ndoshta ne nuk duhet të shqetësohen për dikë duke shkuar kaluara tij. Por le të shohim nëse kjo është një supozim i sigurt. Tani listë është - mallkuar - nuk zgjidhet. Le të provoni këtë përsëri. Kështu 2 dhe 4, 4 dhe 1, 4 dhe 3. 4 dhe 6, të mirë. 6 dhe 5, mirë. 6, 7, dhe 8, mirë. Por njoftim, unë mund të ndalet vetëm këtu tani dhe të ndaluar këtu tani? [Student] Po. Po >>? Çfarë ndodh nëse njëri prej jush ka qenë numri 9 të gjithë rrugën atje? Ajo do të kishte qenë të renditura. Mirë >>. Ajo do të kishte qenë të renditura herë të parë përreth. Mirë. Pra, le të kthehemi përsëri. Ne jemi gati atje. 1 dhe 2, 2 dhe 3, 3 dhe 4, 4 dhe 5, 5 dhe 6, 6 dhe 7, 7 dhe 8. 

Unë jam bërë tani, por, përsëri, unë jam një kompjuter që mund të bëni vetëm atë që unë jam duke thënë për të bërë, dhe kujtesë ime e vetme tani është se unë në fakt e bëri vetëm një grimë e punës. Diçka ndryshoi këtu. Kështu që unë nuk e kanë konfirmuar teknikisht vizualisht ose algorithmically se kjo listë është renditur vërtetë. Pra, vetëm për masë të mirë, vetëm të jetë anal në lidhje me këtë, le ta bëjmë këtë kohë 1 më shumë. Kështu 1 dhe 2, 2 dhe 3, 3 dhe 4. Dhe ju e dini se çfarë? Vetëm për masë të mirë, unë jam duke shkuar për të mbajtur gjurmët në dorën time këtë kohë sa këmbime kam bërë vetëm kështu që unë e di se sa shumë punë që unë kam bërë në të vërtetë. 3 dhe 4, 4 dhe 5, 5 dhe 6, 6 dhe 7, 7 dhe 8. Asnjë këmbime. Pra, tani unë do të jetë ligjërisht një idiot për të bërë këtë përsëri sepse nëse kam bërë asnjë punë nëpërmjet kësaj kalojnë të njerëzve, atëherë qartë se do të ndodhë përsëri, nëse asnjëri prej tyre nuk është lloj i rastësisht adversarially lëvizur veten përreth. Deri tani unë mund të ndalet. Tani le të bëjmë pyetjen, se sa shumë punë ka këtë të vërtetë të marrë mua? Sa hapa bëri që të marrë? N >> katror. Yeah, kështu që n katror. Ku ju merrni n katror nga? Ju duhet të kontrolloni çdo num - Nuk ka numrat n, dhe ju duhet të kontrolloni çdo numër me numrat n tjerë. Mirë. Pra, ajo >> n katror. Mirë >>. 

Pra, ai ndjehet si ajo mund të jetë shumë mirë n katror, ​​e drejtë? Ka n prej këtyre djemve, 8 të veçantë në këtë rast, por çdo herë që unë shkova me këtë listë unë u krahasuar personin e parë kundër të dytë, e dytë kundër tretë përsëri dhe përsëri dhe përsëri, dhe kur kam marrë deri në fund, çfarë të bëj? Unë redid atë. Pra, nëse ne përgjithësoj këtë shpjegim, ne kemi n njerëzve dhe unë jam duke e bërë, natyrisht, 8 hapa, n hapa, çdo herë që unë shkoj përmes këtij algoritmi. Por sa herë në rastin më të keq mund të duhet të kalojnë nëpër këtë listë të njerëzve? [Student] N herë. Ndoshta >> n, e drejtë, sepse në rastin më të keq, çfarë është ndoshta marrëveshja rastin më të keq nga këta njerëz nga get-go? Nëse ata janë plotësisht të kundërt urdhër sepse ashtu mendoj mentalisht, let's - Si e keni emrin? Bowen >>. Bowen. Rregull. Pra Bowen, eja mbi këtu për vetëm një moment. 

Mendoj se Bowen ishte këtu në fillim të algorithm, dhe ne nuk e dimë se çfarë të gjithë të tjerët është, por Bowen këtu, në bazë të këtij algoritmi - dhe në qoftë se ju doni të vetëm shëtitje me mua - do të flluskë lart, ashtu siç bëri herën e parë rreth, gjatë gjithë rrugës deri në fund. Por mendoj se personi tjetër për Bowen ishte numri 7. Unë kam për të shkuar mbrapa dhe për të marrë numrin 7, që do të thotë unë kam për të shkuar gjatë gjithë rrugës prapa këtu. Tani unë duhet të ketë atë shëtitje të njëjtë me personin i cili është numri 7. Por çka nëse atëherë numri 6 ishte pranë tij si? Pastaj unë kam për të shkuar mbrapa dhe për të marrë 6. Pra, përsëri, në çdo përsëritje të këtij lak unë jam duke folur për secilin prej popullit n, dhe unë mund të ketë të bëjë n nga këto shëtitjet për t'u siguruar që unë jam tërhequr të gjitha elementet më të mëdha mbrapa dhe mbrapa dhe përsëri në fund të listës. Gjëra aq n n herë është vetëm herë n n ose n katror. 

Kështu që këtu tashmë kemi një algoritmi që është nuk n, që nuk është më log n, kjo është në fakt më e keqe se çdo gjë që ne kemi bërë më parë. Kështu lloj Alex e mori me fat në atë që kam bërë të gjithë punën me sa duket deri përpara për të, të gjithë punën e shtrenjtë, kështu që ajo mund të gëzojnë në këtë algorithm e kërkimit binar, cila është log e n. Por kjo është në përputhje me temë hënës. Ne i patëm dhënë pak më shumë hapësirë, ne kemi përdorur bit më shumë, në mënyrë që të përshpejtojë kohën tonë running. Pra, ashtu si ka kjo tregti-off mes kohës dhe hapësirës, nuk mund të jetë vetëm trade-offs midis koha e kaluar deri lloj para për të marrë gjërat gati për të shkuar dhe në fakt ekzekutimin e një algoritmi si kërkim. Le të provoni një tjetër. Në qoftë se ju djema nuk do mend vetëm shpejt rearranging vetë që të shkojë përsëri, le të provoni diçka pak të ndryshme ku ajo nuk është mjaft e thjeshtë si vetëm të rregulluar të gjitha gabimet pairwise, e cila është super intuitiv. Le të jetë një vend pak më shumë të qëllimshme dhe të bëjë këtë. Kjo një shumë që unë do të propozojë ndoshta është shumë intuitiv. 

Le të zgjidhni personin më të vogël nga lista përsëri dhe përsëri. Pra, këtu ne do të shkojmë. 4, ju jeni personi më i vogël kështu që unë kam parë deri tani, kështu që unë jam duke shkuar për mendërisht kujtojmë se vetëm duke vënë në ju tani për tani. 2. Ooh! Harrojeni për numrin 4. Unë vetëm gjetur element të ri të vogël në këtë listë. Unë jam duke shkuar për lloj të mbani mend se. 6, 8. Ooh! 1. Mirupafshim. Pra, tani unë jam duke shkuar për të kujtuar numrin 1. Ne e dimë se 1 është më i vogël, por unë jam kompjuter. Çka nëse nuk ka një 0? Çka nëse nuk ka një -1? Unë kam për të mbajtur vazhdim e sipër. Kështu 3, 7, 5, nope. Rregull. Pra, numri 1 ishte e vogël. Më lejoni të ju zgjidhni nga lista - we'll shkoni në këtë mënyrë - dhe ju vë në mënyrë arbitrare në fillim të listës. Tani, prisni një minutë. Unë lloj i mashtruar. Nëse këta njerëz përfaqësojnë jo një listë prej 8 njerëz, por një koleksion, 8 chunks e kujtesës puqur - keni mendje shkelën përsëri për vetëm një moment? Nuk ka në fakt asnjë hapësirë ​​për ju të drejtë këtu. Pra, si nuk kemi hapësirë ​​për të bërë - si e ke emrin? Sammy >>. Sammy >>. Si nuk kemi bërë hapësirë ​​për Sammy? 

Ne lëvizur n që janë para meje. Mirë >>. Kështu që ne mund të lëvizin njerëzit që janë n para tij, kështu që nëse ju djema doni të merrni 1 qëllimshme hap dramatik, në të majtë. Ata të gjithë bënë që në unison, por hera e fundit kam shkruar një kod, ju nuk mund të lloj të lëvizin shumë gjëra përnjëherë. Ne mund të bëjmë atë në një lak, duke lëvizur të gjithë një herë në një kohë. Pra, nëse ju djema nuk do mend shkelën kthehet në të djathtë, dhe Sammy, në qoftë se ju mund të hap prapa, sepse ka ende ka vend për ju, tani le ta bëjmë këtë. Ku ishte Sammy një moment më parë? Drejtë atje. Kështu që nuk ka një hendek atje. Kështu që ju mund të hyni në vendin Sammy-së. Tani personi tjetër dhe tani personi tjetër, tani personi tjetër. Tani ne kemi vend për Sammy. Tani, dikush nga publiku - që ishte e mirë, se ishte e saktë, ai ndjeu një pak kohë - çfarë është më të shpejtë? Po. [Student] Një koleksion të re? >> Çfarë është ajo? >> [Student] Një koleksion të re? Mirë >>, mirë. 

Pra, në përputhje me këtë temë të vetëm të tregtisë të humbura, pse nuk e kam vetëm të bëjë një koleksion të ri  dhe pastaj Sammy do të notit në hapësirë ​​në frontin e këtyre njerëzve, për shembull, dhe ne vetëm mund të fillojë të plotësojë një koleksion të ri krejt. Kjo shumë do të punojë. Por unë nuk jam i interesuar në shpenzimin e më shumë hapësirë ​​sot. Çfarë është një tjetër metodë? [Student] Swap. Mirë >>. Ne vetëm mund të bie në ujdi këto 2 guys. Çfarë është emri juaj? Mario. Mario >>. Pra Mario, ju ishit aktualisht këtu. Sammy, ju mund të kthehet për vetëm një moment? Mario ishte këtu. Ne nuk kemi vend për ty më, kështu që nëse ju nuk do mend se ku do të Sammy është, ne do të vënë Sammy këtu, dhe tani unë do të argumentojnë se operacioni shkëmbejnë Sammy ishte shumë më të shpejtë. Ne e bëmë 1 operacion të bie në ujdi këta njerëz, ose ndoshta 2 të bie në ujdi këta njerëz, por ne nuk e ka bërë 1, 2, 3, 4, kështu që ndjehet mirë. Tani, prisni një minutë. Unë lloj i bërë keq, sepse problemi numër 4 ishte lloj i afërt me fillim. Tani numri 4 është pak më afër për këtë qëllim, por unë vërtetë nuk e di ose kujdesen për këtë. Pra, kjo është vetëm fat i keq se numri 4 është pak më larg nga vendi i tij i destinuar. Pra, le të tani përsëris këtë algoritëm. 

Për radhitje, për sa kohë që historia ishte, të gjithë ne nuk u ecin nëpër lista kërkoni për personin e vogël numëruar. Deri tani, le të bëjmë atë përsëri. Ne nuk duhet të shqetësohen për Sammy më. Ne vetëm mund të shkoni këtu. Ooh! Numri 2. Kjo është një numër mjaft të vogël. 6, 8, 4, 3, 7, 5. Mirë, mirë. Dhe fatmirësisht, rastësisht, unë nuk kam për të lëvizur - >> Willie. Willie sepse ai është në vendin e tij të djathtë tani. Le ta bëjmë këtë përsëri dhe injorojnë këto 2 guys. 6. Kjo është një numër mjaft të vogël. Ooh! 8 është definitivisht më e madhe. 4. Le të përqëndrohet në 4. Ooh! 3 është edhe më mirë. 7 dhe 5. Pra, çfarë bëjmë ne tani me - >> Roger. Roger >>? Le të bie në ujdi atë me numër 6. Pra, nëse 6 dhe 3 do të donte të bie në ujdi, tani ne kemi lloj të marrë me fat në atë 6 është më afër se ku ajo duhet të jetë, por kjo është vetëm rastësi këtu. Pra, le të shkojë tani këtu. 8 është një numër shumë i vogël. Ooh! 4 është më i vogël. 6, 7, 5. Çfarë bëjmë ne tani të bëjmë? Swap. >> Pikërisht >>. Pra, tani le të bëjmë këtë lloj të shpejtë. 8, 6, 7, 5. Ku do të shkojnë 5? Mirë. Rregull. 6, 7, 8. 6 merr për të qëndruar aty ku është ajo. Çfarë është emri juaj? Rosalie >>. Rosalie merr për të qëndruar aty ku është ajo. 7 merr - Le të shohim. 7, 8. Rregull. Pra 7 merr për të qëndruar aty ku është ajo. Çfarë është emri juaj? Amna >>. Amna >>. 

Pra, Amna merr për të qëndruar aty ku është ajo, dhe numri 8 është tashmë aty ku ai tani duhet të jetë. Mirë, mirë. Ndihet si ne jemi vetëm duke krijuar punë për veten këtu, pse. Çfarë është në fund të fundit koha drejtimin e këtij algoritmi? Nëse ne mendojmë për këta njerëz jo si 8 por si n? Është n >>. Është n hapa, por ne jemi duke kontrolluar çdo herë të vetme. Rregull. N por ju jeni duke kontrolluar çdo herë të vetme? Në rregull, por nëse kjo është n hapa, nuk duhet të kam qenë në gjendje për të zgjidhur nga ju vetëm do 1, 2, 3, 4? Oh! Mirë, kjo është një ndryshim i madh. Pra, n katror pse? Çfarë po ndodh realisht? Ka njerëz n në këtë listë, por për të gjetur personin e vogël në lista në rastin më të keq, se sa hapa mund të keni për të marrë? N. >> 

N, e drejtë, sepse në rastin më të keq, numri 1 është gjithë rrugën atje, kështu që unë kam për të shkuar të marrë atë apo të saj. Dhe atëherë kur më në fund e kuptojnë 1 ishte e vogël, atëherë kjo është goxha e shpejtë të bie në ujdi tyre. Por tani unë kam për të filluar nga fillimi dhe të kërkoni për kush? Personi tjetër të vogël, e cila është 2. Ku në rastin më të keq është 2? Oh, Zoti im. Kjo është e gjitha mënyra gjatë këtu në fund. Deri tani unë kam bërë vetëm një hapa n, edhe hapat n. Dhe në qoftë se ne kemi marrë njerëz n dhe në rastin më të keq se personi më i vogël është n hapa larg, që është përsëri n herë n, dhe kështu ne përsëri kemi n katror. Kjo nuk është ndjenjë aq të mirë. Dhe në fakt, edhe në rastin më të mirë - mendoj se ata të fillojnë të renditura jashtë - sa hapa nuk është marrë për mua për të përdorur këtë algoritëm për të zgjidhur këta njerëz n? N katror. Kam dëgjuar >> n katror. Pse n katror? Sepse ju ende duhet të kontrolloni çdo herë të vetme. Po >>. Dhe ju duhet të bie në ujdi tyre. Edhe pse >> ne njerëzit janë lloj i gjithëdijshëm në kuptimin vizualisht që ne mund vetëm lloj të shihni se kjo është renditura, një kompjuter që nuk është zgjuar. Ajo do të shikoni këtu dhe këtu dhe këtu, por në qoftë se ajo është në kërkim për të është elementi më i vogël, ju vetëm e di se keni gjetur elementin më të vogël nga ajo pikë? Pasi ju jeni në fund. Por në atë moment ju keni gjetur vetëm elementin aktualisht vogël. Ju nuk domosdoshmërisht dinë asgjë tjetër në lidhje me gjendjen e botës. Kështu që ju duhet të shkoni përsëri dhe përsëri dhe përsëri. 

Pra, këtë herë unë me të vërtetë e shohin memecët sepse unë jam kontrolluar, në rregull, 2, ju jeni më të vogël, por unë nuk e di se në total ende. 3, 4, 5, 6, 7, 8. Mirë, mirë. 2 ishte me të vërtetë i vogël. Tani le të gjeni të vogël ardhshëm. Rregull. 3, ju jeni aktualisht vogël. Le të shohim. 4, 5, 6, 7, 8. Mirë, mori me fat përsëri. 3 ishte me të vërtetë në vendin e duhur. Por unë jam duke shkuar për të mbajtur të bërë këtë përsëri dhe përsëri dhe përsëri. Si mund të bëjmë ndonjëherë kaq pak më të mirë? Në vend të që njerëzit flluskë deri pairwise nga më i vogli tek më i madh dhe në vend të shkuar mbrapa dhe me radhë nëpër lista zgjedhjen e personit, atëherë më të vogël, pse nuk kemi vend futur këta njerëz në një listë të re hap pas hapi? Le të provoni këtë. Tani më lejoni të quajmë këtë lloj futje gjë. Kështu që këtu ne jemi këtu. Numri 1. Unë nuk e kujdesit për askënd tjetër në këtë listë. Qëllimi im tani është për të vënë numrin 1 në fillim të një liste renditura. Dhe unë jam duke shkuar për të propozojë që unë vetëm 8 chunks e kujtesës, arbitrarisht tani unë jam në mes të mur listën time gjoja Unsorted, dhe kushdo që është pas meje që unë jam duke shkuar për të kërkuar të zgjidhet. Deri tani ne kemi numër 1. Unë dua të futur atë në listën time renditura, kështu që unë jam vetëm duke shkuar për të lëvizur murin tim gjatë këtu, dhe tani unë pretendojnë kjo listë është renditur, kjo listë është unsorted - të paktën për aq sa unë e di. Unë nuk mund të shihni të gjitha numrat në të njëjtën kohë. 

Tani unë të ndodhë që të takohem numër 2. Çfarë të bëj me të? I futur ju tani në listën e renditura. Por vini re se sa e lehtë që ishte. Unë vetëm duhet të shikoni. Numri 1 është atje. Oh, padyshim 2 shkon në anën e numrit 1. Tani çfarë të bëj me 3? Unë ju futur në listën e renditura. Por që ishte super lehtë. Kjo është super i lehtë, kjo është super i lehtë, kjo është super i lehtë, super të lehtë, të lehtë super. Dhe tani çdo gjë është renditur pas meje, dhe sa hapa bëri që të marrë? [Studentët] N. >> Pra, kjo është vetëm n. Kemi marrë me fat. Ajo ishte vetëm n pse? >> [Student] Për shkak se lista u renditura. Lista është renditur tashmë. Pra, kemi marrë me fat. Por ne kemi projektuar një algoritmi këtë kohë që pajimet atë lloj të fatit, se skenari më i mirë, duke mos humbur kohë të panevojshme. Pra, tani ne kemi atë që ne do të thërrasë llojet flluskë ku njerëzit lloj flluskë deri pairwise. Ne tani kemi lloj përzgjedhjes ku kemi nxirre nga personi i vogël përsëri dhe përsëri. Dhe tani ne kemi lloj futje ku ne lloj aktive vënë njerëzit ku ata i përkasin në një listë të renditura gjithnjë. Nëse ne mund të, një raund i duartrokitje për këta njerëz këtu. [Duartrokitje] Le të marrin 5-minutësh pushim tonë këtu. Dhe kur kemi ardhur përsëri, ne do të fryj të gjitha këto algoritme nga uji me diçka më të mirë. Dakord. Faleminderit shumë. Ju mund të mbani ato si suvenire. Dakord. Ne jemi mbrapa. 

Dhe për radhitje të shpejtë të vërtetë, kemi pasur këto qasje të ndryshme për klasifikim 3, pika e tërë e cila ishte për të marrë në pikën ku dikush si Alex mund të kërkoni një listë të numrave të shpejtë se dikush si Sean mund. Dhe edhe pse ne kemi shembuj të tillë të thjeshtë me 8 numra, ju mund të ekstrapoloj lehtë për 8 web pages, 8 miliardë faqet e internetit, ose 800 milion miq në Facebook. Kështu që këto algoritme siguri mund të shkallë me ato llojet e vlerave, dhe idetë janë përfundimisht të njëjta. Kështu renditjes flluskë ishte i pari ku ne lloj bubbled deri personin më të madhe të gjitha mënyra për të drejtën duke shkëmbejnë njerëzit pairwise. Pastaj kemi pasur atë që ne do të thërrasë lloj përzgjedhje, ku kam pak më shumë qëllimisht mbajtur në kërkim nëpër lista, zgjedhjen numrin më të vogël përsëri dhe përsëri dhe përsëri, rezultati logjik i të cilave është që lista është renditur përfundimisht. Pastaj në një të tretë, unë futur njerëzit në vendin e tyre të duhur, dhe ne e bëmë një shembull shumë të ndërtuar në se lista u renditur tashmë, por që ishte për ta dërguar mesazhin që në rast lloj futje e, ju mund të merrni me fat. Nëse numrat janë të renditura tashmë, ajo vetëm do të ju merr n hapat për të konfirmuar sa më shumë, ndërsa ju jeni lloj përzgjedhjes vizion pak më shumë tunel dhe ju kurrë nuk e kuptojnë se lista është renditur tashmë. Pra, le të shohim lloj flluskë në veprim këtu. Në shembullin e mëposhtëm, ne jemi gati për të parë bare vertikale lartësitë e të cilëve paraqesin numrat në mënyrë që ne mund të lloj të parashikoj klasifikim ndodhë. Të vogla bar, aq më i vogël numri, aq më e madhe bar, madhe numri. 

Dhe ne do të luajnë atë në këtë shpejtësi default. Ajo do të lëvizë një agjërim pak tani për tani, por e kuqe është ajo që është duke treguar 2 bare duke u krahasuar krah për krah. Dhe në qoftë se keni shikuar nga afër, se çfarë ndodh është se nëse bare janë jashtë funksionit, të vogla e merr lëvizur në të majtë, një të madhe në të djathtë, dhe pastaj ju mbani avancimin. Pra, nëse ne e bëjmë këtë përsëri dhe përsëri, vëreni se bare të vogla do të mbajnë inching rrugën e tyre në të majtë dhe baret më të mëdha do të mbajnë inching rrugën e tyre në të djathtë. Dhe vërtet, ne jemi duke filluar për të parë një model të gjithë rrugën në anën e djathtë ashtu si e pamë 8 dhe pastaj përfundimisht 7 bubbling deri në fund deri të listës sonë njerëzore. Pra, kjo do të marrë shumë shpejt një pak i lodhshëm, kështu që më lejoni të ndaluar këtë për një moment. Më lejoni të ndryshojë me shpejtësi që të jetë shumë më të shpejtë. Unë nuk jam duke ndryshuar algorithm, unë jam vetëm duke e bërë animacion ndodhë shpejt. Ende lloj flluskë, algorithm njëjtë, por tani ju mund të shihni shumë më shpejt se sa demonstrim tonë verbale se elementet më të mëdha janë me të vërtetë bubbling deri në krye. 

Si një mënjanë, këto sheshe pak në të majtë e poshtme dhe në fund të drejtë janë vetëm pak kujtojnë se si shumë krahasime jeni duke bërë. Por tani për tani, ne mund të përqëndrohen në të piramidës që është duke marrë formë, dhe nuk shkon. Elementi më i vogël është në të majtë, më i madhi në të djathtë, dhe çdo gjë tjetër në mes. Tani le të marrin një vështrim në vend në lloj përzgjedhjes. Unë jam duke shkuar për të shkuar përpara dhe e goditi të ndalet. Ne jemi duke shkuar për të marrë një seri të re të rastit të hekurave. Lloj përzgjedhje, risjell, shkon nëpër lista përsëri dhe përsëri dhe përsëri, plucking jashtë elementin më të vogël. Kështu që këtu është lloj përzgjedhje. Ajo duket sikur nuk ka punë më pak ndodh tani, sepse ne nuk jemi të krahasuar pairwise por ne jemi vetëm lloj i cherry picking elementet më të vogël nga e djathta në të majtë. Që mori shumë pak kohë, kështu që nuk ka një ndarje tashmë. Vetëm për shkak se një algoritmi është thënë për të të marrë kohë n katror, ​​si lloj flluskë dhe si lloj përzgjedhjes, ata janë me të vërtetë kohët keq running. Për shembull, në rastin e, le të themi, lloj përzgjedhjes, Unë në fakt jam zgjedhur personin më të vogël dhe të vënë atë apo të saj këtu, atëherë unë jam duke bërë atë përsëri, atëherë unë jam duke bërë atë përsëri, por ka pasur një optimization vogël unë mund të bëjë. 

Sa më shpejt që unë u zhvendos numrin 1 këtu - Sammy në këtë rast - ajo që nuk kam nevojë për të bërë me të më pas? >> [Student] Lini atë. Lënë atë, e drejtë? Asgjë. Unë nuk duhet të flasin me kurrë Sammy sërish, sepse nëse unë kam zgjedhur elementin më të vogël dhe vënë atë këtu, pse të humbim kohë duke shkuar deri në fund të listës sime të tërë? Në përsëritje tjetër më lejoni të lëvizë në fakt vetëm për numër 2, vetëm për numër 3. Pra, në realitet, unë nuk ishte duke bërë gjëra N n herë. Unë kam qenë duke bërë gjëra N, pastaj n - 1 gjërave, pastaj n - 2 gjëra, atëherë N - 3 gjëra, pastaj n - 4, dot, dot, dot. Ne kemi një grimë e një seri gjeometrike, që thjesht do të thotë ju jeni duke shtuar deri numrat në mënyrë progresive të vogla. Jo n + n + n + n por n + 7 + 6 + 5 + 4 + 3 + 2 + 1. Dhe çfarë punon që në përgjithësi të jetë - Unë jam duke shkuar për të bela deri bordin tim këtu vetëm për një moment - që do të punojnë jashtë të jetë diçka si n (n - 1) / 2 nëse ne vetëm lloji i shikoni në pasme të një libri matematikë ku ju keni të gjitha fletët e mashtrojnë për formulat. Në qoftë se ju jeni vetëm duke shtuar diçka n + n - 1 + n - 2, ai punon jashtë të jetë diçka si kjo. Dhe nëse ne vetëm lloji i shumohen this out, që është n katror minus n / 2. I mbajtur duke thënë n katror, ​​edhe pse, dhe kjo është për shkak se unë kam qenë lloj të marrë një shkurtore mendore sepse në realitet, n katror minus n ndarë nga 2 është me të vërtetë numri i vërtetë i hapave se një algoritmi si lloj përzgjedhjes do të marrë në qoftë se ne të vërtetë numëruara deri të gjitha këto krahasime dhe të gjithë punën e zënë pak ne ishim duke bërë. Por sinqerisht, pasi n i bie të jetë si një milion apo një miliardë, i cili dreq kujdeset në qoftë se ju jeni duke bërë një miliard minus katror një miliard ndarë nga 2? Një miliard squared është një numër i madh. Ju mund të marrin një miliardë off e saj me - n. Kjo nuk është e tillë një punë e madhe. Pra, sa më i madh numri i merrni, aq më pak të rëndësishme këto terma janë të ulëta urdhëruar. Kush kujdeset nëse ju ndani me 2 në qoftë se ju jeni duke folur në lidhje me quadrillions e numrit të hapave? 

Pra, në përgjithësi, shkencëtarët kompjuter priren për të hedhur larg çdo gjë por termi më i madh, dhe ne vetëm lloji i thjeshtojë botën dhe thonë se kjo algoritmi ndërmori hapa afërsisht n katror. Kjo është hera e drejtimin e një algoritmi. Pra, ne do të vijnë përsëri në këtë vetëm në një moment me disa shembuj konkretë, por tani për tani, kjo është lloj i motivimit intuitive pas vetëm thjeshtimin botën tonë dhe duke folur në lidhje me kushtet më të rëndësishme sesa të hyrë në të gjitha këto formula dashuroj. Kështu që ishte lloj përzgjedhje, dhe kemi marrë pak fat atje. Le të shikojmë në lloj futje. Më lejoni të shkojnë përpara dhe të fillojnë këtë një si. Tani njoftim model që po ndodh është pak më ndryshe, dhe kemi filluar me numra të rastit, por në qoftë se ne fakt numërimin deri në numrin e hapave në rastin më të keq, nëse lista nisur plotësisht në mënyrë të drejtë, ne vetëm do të marrë hapa për të realizuar n sa më shumë. 

Por në qoftë se lista ishin në fakt prapa - për shembull, në këtë rast këtu - atëherë vëreni ne fakt kemi të bëjmë punë shumë më tepër në këtë rast. Dhe kjo duhet të lloj të ndjehen për ju si kjo është lloj i vështirë pune për të marrë ato elemente të vogla në të majtë, dhe kjo është për shkak se kemi marrë pafat. Lista u renditura rastësisht në të kundërt. Nga ana tjetër, me lloj futje në qoftë se ne të imitoj atë që ne e bëmë me njerëzit tanë këtu duke filluar me të gjithë renditura dhe pastaj të fillojë, kjo është një algoritmi goxha e mirë, e drejtë? Është tashmë, në fakt, të renditura. Pra, le të përpiqemi të përmbledhim saktësisht se sa kohë këto gjëra po na duke futur vetëm pak të zhargonin apo simbol që është në fakt shumë më e thjeshtë se lloj fanciness i sugjeron. Kjo gjë këtu, kjo o madh në ekran, është ajo që një shkencëtar kompjuteri në përgjithësi do të përdorë për të përshkruar kohën e keq drejtimin e një algoritmi. 

Përsëri, me rastin më të keq, kjo është krejtësisht kontekstin varur. Ajo që ne kuptojmë me rastin më të keq krejtësisht ndryshon bazuar në problemin ne jemi duke folur rreth. Por në rastin e ndarjes, çfarë është skenari më i keq mundur? Gjithçka është prapa, sepse ajo vetëm ndjehet si që do të thotë një punë shumë e për ne. Unë kam jotted poshtë disa nga algoritme që kemi parë deri më tani: kërko lineare, kërko binar si me librin e telefonit apo copa të letrës, pastaj lloj flluskë, lloj përzgjedhje, dhe futje lloj si ne pamë me njerëzit tanë, dhe pastaj 1 tjetër që është përfundimisht do të quhet bashkojë lloj. Pra, në kërkim linear në rastin më të keq, sa hapa nuk është marrë për të gjetur numrin 7 nëse ka dyert n si Sean ballafaqohen? >> [Student] N. N. Pra, ne jemi duke shkuar për të shkruar madh o n. Unë jam vetëm duke shkuar për të mbushur boshllëqet në disa. Kjo është vetëm një rrjet i boshllëqet. Por në rastin më të mirë me kërkim linear, 7 mund të ketë qenë në fillim të listës, dhe Sean mund të ketë filluar në kërkim në fillim të listës. Pra, nëse ju jeni duke përdorur search lineare dhe vetëm kontrolluar majta në të djathtë ose ndoshta djathta në të majtë - ata janë ekuivalenti - në rastin më të mirë se sa hapa mund të kërkoni lineare, si algorithm Sean, të marrë? Vetëm 1 hap. 

Kështu që unë jam duke shkuar për të thonë se është simbol omega. Kjo është vetëm kryeqyteti omega. Omega është vetëm mënyrë për të thënë sexy rastin më të mirë running kohë. Pra, në rastin më të mirë koha running është një hap i vetëm ose numrin e vazhdueshme e hapa - 1 në këtë rast - por në rastin më të keq, i madh o, ajo është në të vërtetë hapa n. Dhe kjo këtu, Theta, ne nuk jeni të vërtetë do të shikojmë në të drejtë tani. Kjo nuk është e rëndësishme për këtë shembull të veçantë. Por tani le të përpiqemi kërkimin binar. Në rastin më të keq me kërkimin binar, sa hapa është ajo do të marrë për të gjetur numrin 7 ose çdo gjë që ne jemi duke kërkuar për? >> [Student] Identifikohu n. Ende do të marrë n log, sepse vetëm si Alex mori pafat Kur ne me të vërtetë ka punuar me këtë problem në mënyrë metodike dhe ajo nuk e gjeni numrin 7 deri në derën e fundit ajo e shikoi, edhe pse, në drejtësi, ajo mori për të hedhur larg dyerve të caktuara së bashku rrugën, kërko binar në rastin më të keq ka një kohë drejtimin e log n. Dhe përsëri, që flet për këtë ndarjes dhe pushtues. Por ajo që për në rastin më të mirë? Dhe Alex fakt përjetuar atë rast më të mirë të drejtë kur ajo doli në skenë. Sa hapa bëri që marrin në kërkim binar? >> [Student] 1. 1, vetëm për shkak se ajo mori me fat. Por kjo është në rregull, sepse omega referohet skenarë më të mirë të rasteve, inputeve të mira rast, edhe në qoftë se ajo është vetëm fat i rastit memec. 

Tani, kjo shumë ne jemi duke shkuar për të vetëm lloji i lënë bosh për momentin. Si në lidhje me tani lloj flluskë sapuni? Në rastin më të keq me lloj flluskë, gjithkush është në rregull të kundërt, kështu që ne kemi për të bërë një shumë të bubbling. Por sa hapa është se do të marrë në rastin më të keq? >> [Student] N katror. Kjo ishte n katror, ​​sepse në qoftë se ju mendoni rreth saj, nëse lista është plotësisht prapa - 8 është mbi këtu, 1 është mbi këtu - si gjë të fillojë të flluskoj, numri 8 është duke shkuar për të lëvizur në këtë mënyrë, në këtë mënyrë, në këtë mënyrë, në këtë mënyrë, por ku është numri 7 në rastin më të keq? Këtu ajo është ende atje. Pra, ne duhet të bëjmë atë përsëri dhe përsëri. Dhe kjo është ajo ku ne kemi marrë hapa n, pastaj n - 1 hapa, pastaj n - 2 hapa. Dhe në qoftë se ju merrni fjalën time për atë - se në qoftë se ju lloj i shumohen atë nga, ajo n afërsisht katror në fund me disa kushte të tjera që ne vetëm do të injorojnë për tani - pastaj në lloj flluskë keq rast është n katror, ​​të japë ose të marrë. Por ajo që për rastin më të mirë me lloj flluskë? Çfarë është skenari më i mirë? Të gjithë numrat janë të renditura tashmë. Dhe çfarë ishte orientues kam përdorur, mashtrim kam përdorur, të kuptojnë se unë kam bërë asnjë punë dhe për këtë arsye mund të ndalet herët? [Student] Kontrolloni atë një herë. Kontrolloni >> atë një herë. Por çfarë u kam bërë së bashku rrugën? Unë kam qenë mbajtja e sa këmbime kam bërë. Dhe kuptova në qoftë se unë nuk kam asnjë të numëruara këmbime në gishtat e mi, atëherë unë kam bërë asnjë punë. Unë me siguri nuk duhet të përpiqet të bëjë asnjë punë përsëri, kështu që unë mund të ndalet vetëm. 

Pra, në rastin më të mirë të lloj flluskë kur lista është renditur tashmë, çfarë do të thonë se simbol omega është rasti më i mirë running kohë? Është n vetëm. Ne kemi për të bërë disa punë, por ne vetëm duhet të bëjmë me vlerë 1 shëtitje e punës. Dhe këtu edhe unë jam duke shkuar për të lënë bosh këtë pjesë. Dhe tani lloj përzgjedhje. Lloj përzgjedhje kishte mua plucking personin më të vogël përsëri dhe përsëri. Dhe çfarë u themi koha drejtimin e që ishte? Kjo ishte n katror në rastin më të keq. Dhe për fat të keq, në rastin më të mirë ajo gjithashtu n katror sepse unë nuk kam parë lloj i gjithëdijshëm e gjithë botës; Unë di vetëm mbi një përsëritje të plotë që unë kam gjetur personin e vërtetë të vogël. Pra, zgjedhja lloj lloj sucks në këtë kuptim, por kjo kokë është lloj i intuitiv. Kjo është goxha e lehtë për kodin lart, sepse të gjithë ju duhet të bëni është të shkruani një çift të mbivendosur për sythe, tipike, që shkon përmes kërkuar për elementin më të vogël dhe pastaj e vë elementin më të vogël ku ajo i takon në fund të listës. Pra, edhe këtu nuk do të jetë një tregti-off. Sasia e kohës që duhet për ju për të menduar dhe për të zhvilluar diçka të vërtetë duke shkruar kodin shumë mirë mund të marrë më shumë kohë në qoftë se ju doni një performancë më të mirë dhe më të shpejtë algorithm. 

Por nëse ju me të vërtetë vetëm diçka lloj i kodit lart të shpejtë dhe të pista dhe vetëm lloji i marrë idenë stupidest mundshme që ju mund të mendoni, që mund të ju merr disa minuta për të kodit, por me grupe të mëdha të të dhënave algorithm juaj mund të marrë orë për të kandiduar. Dhe, edhe unë në shkollë diplomuar ndonjëherë do të bëjë këto tregtisë humbura. Ajo do të jetë 03:00, unë kam qenë duke u përpjekur për të analizuar disa shumë të madhe të të dhënave set lidhur me kërkimin e sigurisë isha bërë, dhe kjo ishte as shpenzojnë 5 minuta tweaking programin tim për të analizuar të dhënat dhe shkoni për të fjetur ose shpenzojnë 8 orë marrë atë vetëm të drejtë kështu që ajo shkon në çast dhe të mos shkoj të fle. Dhe kështu që nuk ka shumë që është lloj i një vendimi të ndërgjegjshëm. Pak kohë zhvillimin, fle shumë. Në retrospektivë, unë ndoshta nuk duhet të nxisë që kur qëllimi këtu është që të zgjedh cilësinë e kodit, por që edhe në botën reale është një shumë të arsyeshme tregtare-off. Pak kohë, performanca më pak ose anasjelltas. Kështu që këtu ne fund merrni një shans për të folur për theta. Theta simbol është diçka shkencëtarët kompjuter mund të sjellë deri në bisedë kur madh o dhe omega ndodhë që të jetë e njëjtë. Ju thoni theta me të vërtetë të dërguar mesazhin që kjo është lloj i një të lidhur ngushtë. Nuk ka rëndësi nëse skenari është i mirë apo i keq, kjo është n katror. Pra, kjo është jo vetëm e rëndësishme në këto histori këtu. Lloj futje është e fundit kemi shikuar në, ku kam qenë vetëm futur të gjithë në vendin e duhur. Në rastin më të mirë ajo ishte koha drejtimin e lloj futje siç e pamë këtu? [Student] rastin më të mirë? Rasti >> mirë. 

Ajo ishte n sepse në rastin më të mirë të gjithë të renditura, dhe Sammy dhe askush tjetër me të vërtetë kishte për të lëvizur në të gjitha. Ata ishin tashmë në vendin e tyre të drejtë. Pra lloj futje në rastin më të mirë është, në këtë rast, n. Por në rastin më të keq kjo është lloj i n katror. Pse? Nëse lista ime e njerëzve është në mënyrë të kundërt, Unë së pari të fillojë me numrin 8 dhe unë futur atë apo të saj në pozitën e drejtë, e cila është e drejtë këtu. Unë lloj i lëvizjes në anën. Këta njerëz janë unsorted, ai ose ajo është i renditur. Por tani unë të ndodhë për të gjetur kush tjetër? >> [Student] 7. 7 në rastin më të keq, sepse kjo është në mënyrë të kundërt. 

Kështu që këtu është 7. Ku ka 7 i përkasin? Definitivisht pas meje. 7 Por tani në fakt nuk i takon menjëherë pas meje, por pas numrit 8, kështu që unë duhet të them, "Më falni, numri 8, mund të ju lutem lëvizin në këtë mënyrë "Të bëjë vend për 7?" Tani unë hasni 6. "Oh, më falni, numër 8 dhe numrin 7, ju mund të lëvizin për të bërë vend për 6?" Pra, me fjalë të tjera, me lloj futje, edhe pse unë nuk jam duke bërë lëvizje shumë, njerëzit pas meje janë duke bërë punë shumë më shumë, dhe që e mori të kushtojë kohë dikush. Ajo do të kushtojë kohën e kompjuterit. Pra, në rastin e lloj futje ne ende vuajnë. Nëse ju filloni duke shtuar deri në numrin e përgjithshëm të hapave, deri ne fund goditur afërsisht n katror sepse këta njerëz duhet të bëjë vend për të njeriut për t'u futur përsëri në atë listë. Dhe kështu në këtë rast nuk është vetëm theta zbatueshme për histori të veçantë në dorë. Kjo është e gjitha e bukur dhe e mirë. Ne kemi këto mënyra të ndryshme 3 folur në lidhje me kohën që kalon. Por çfarë e bën këtë të vërtetë do të thotë në terma realë në qoftë se ne të vërtetë përpiqen për kodin e një algoritmi? 

Më lejoni të propozojë që ka një algoritmi edhe më të mirë atje që në vetvete ka disa tregtisë humbura. Ne jemi duke shkuar për të thirrur të bashkojë lloj, dhe kjo është lloj i këtij algoritmi magjike që vetëm punon më shpejt disi, dhe kjo është aq e lehtë për të shprehur, të paktën në pseudokod. Zbatimi i këtij lloji bashkojë algorithm do të jetë si më poshtë. Kur ju jeni të dhënë n elemente - numrat N, N njerëzit, çdo gjë - të parë ka një kontroll mendje e shëndoshë. Nëse n është më pak se 2, shkrihen lloj vetëm ndalesa. Ajo kthehet, në mënyrë që të flasin. Pse do të ju ndalet nëse n është më pak se 2? >> [Përgjigja e padëgjueshme Student] Drejtë. Dhe përsëri, n nuk është numër në listë, n është madhësia e listës. Nëse n është më pak se 2, që do të thotë lista juaj është ose 1, ku ju jeni të renditura qartë nëse kjo është numër 1, ose 0, në të cilin rast ka asgjë tek lloj, kështu që ne kemi nevojë për këtë lloj të rastit bazë. Nëse lista është aq e shkurtër që ka vetëm asgjë për të bërë, fjalë për fjalë nuk bëni asgjë. Kthehen. Përndryshe lloj gjysmën e majtë të elementeve, atëherë lloj gjysmën e duhur të elementeve, pastaj bashkojë 2 gjysmave renditen. 

Ky lloj i duket si një mashtrojnë pak ku unë jam duke kërkuar se si për të zgjidhur elementet dhe ju jeni thënë mua, "Renditur gjysmën e majtë, lloj gjysmën e duhur." Unë jam si, "të gjithë të drejtë. Si ju lloj gjysmën e majtë?" "Renditur gjysmën e majtë të pjesës së majtë, lloj gjysmën e djathtë të pjesës së majtë, dhe pastaj të bëhet." Ju jeni lloj i ciklikisht përcaktimit se çfarë do të thotë për të zgjidhur, por kjo rezulton se në të vërtetë i shkëlqyer në këtë rast. Kjo nuk është me të vërtetë ky cikël vicioz që kurrë nuk përfundon sepse ajo ka fund kur? >> [Student] Kur të keni arritur 1 gjë. Kur të keni arritur 1 gjë. Pra, edhe pse ju mund të filloni me 8 njerëz dhe unë them, "Renditur gjysmën e majtë të këtyre njerëzve, këta 4 persona ", atëherë unë them," Si mund të zgjidhur gjysmën e majtë? " "E pra, lloj 2 persona këtu." Dhe pastaj ju jeni si, "Të gjithë, gjobë drejtë." "Si mund të zgjidhur gjysmën e majtë të atyre njerëzve?" "Vetëm të zgjidhur këtë person 1 këtu." Çfarë është shpallja e shkëlqyer tani? Unë kam për të zgjidhur 1 person. Bërë. Unë nuk kam për të bërë ndonjë punë. Por tani unë kam për të zgjidhur këtë person, por ata janë një person i vetëm, asgjë për të bërë. 

Pra, me sa duket është magjike në këtë hap të tretë: bashkojë gjysmave renditen. Kështu renditjes bashkojë merr këtë pasqyrë të shkëlqyer se në qoftë se ju thyhet një problem i madh poshtë në 2 të vogla, të mesme problemeve identike dhe vetëm pastaj lloj zam zgjidhjet më të vogla së bashku në fund, Unë propozoj që ne mund të bëjmë shumë, [tingull përgjimi] shumë më të mirë se çdo lloj i përzgjedhjes ose lloj futje. Unë kam qenë në fakt duke injoruar se për gjysmë ore, por unë me të vërtetë nuk e di se çfarë po ndodh jashtë sot. [Zë gumëzhitës] [qeshura] Pra, le të shohim nëse ne mund të shohim këtë me një ndihmë të vogël nga miku Rob tonë Bowden. Ka 2 hapa të mëdha në procesin e lloj bashkohen. Së pari, vazhdimisht ndarë listën e gota në gjysmave deri sa ne kemi një bandë e listave me vetëm 1 filxhan në to. Mos u shqetësoni nëse një listë përmban një numër të rastësishëm dhe ju nuk mund të bëjë një prerje të përkryer të pastër në mes tyre. Vetëm arbitrare të vini të cilën listë të përfshijë kupën ekstra in Pra, le të ndahet këto lista. Tani ne kemi 2 listat. Tani ne kemi 4 listat. Tani ne kemi 8 listat me një filxhan të vetëm në çdo listë. Pra, kjo është ajo për hapin 1. Për hapin e 2, ne vazhdimisht bashkojë palë e listave duke përdorur algoritmin bashkojë kemi mësuar më parë. Bashkimi i 108 dhe 15 ne fund me listën e 15, 108. Bashkimi 50 dhe 4 ne fund me 4, 50. Bashkimi 8 dhe 42 ne fund me 8, 42. Dhe bashkimin 23 dhe 16 ne fund me 16, 23. Tani të gjitha listat tona janë të madhësisë 2. Njoftim që secili prej 4 listave është renditura, kështu që ne mund të fillojë bashkimin palë e listave përsëri. Bashkimi 15 dhe 108 dhe 4 dhe 50 ne së pari të marrë 4, pastaj 15, pastaj 50, pastaj 108. Bashkimin 8, 42 dhe 16, 23 ne së pari të marrë 8, pastaj 16, pastaj 23, pastaj 42. Deri tani ne kemi vetëm 2 listat e madhësisë 4, secila prej të cilave është renditura. Deri tani ne bashkojë këto 2 listat. Së pari ne kemi marrë 4, pastaj ne kemi marrë 8, atëherë ne do të marrim 15 dhe 16 dhe 23 dhe 42 dhe 50 dhe 108. Dhe ne jemi duke bërë. Ne tani kemi një listë të renditura. 

Rob ishte lloj i duke përfituar nga diçka që ne nuk e kemi bërë ende. Ajo ishte sugjeruar, por ne fakt nuk bëni atë. Ai ishte duke bërë diçka fizikisht me gota që sugjeron ai ishte duke shpenzuar disa burimeve, përveç kohës. >> [Student] Hapësirë. Ajo ishte >> hapësirë. Fakti se ai kishte këtë lloj të bi-nivel tryezë, ku ai kishte hapësirë ​​deri këtu dhe hapësirë ​​këtu poshtë është në fakt duke lënë të kuptohet se ai është duke përdorur hapësirë ​​dy herë më shumë si ndonjë nga algoritme tonë deri tani - lloj futje, lloj flluskë, ose të përzgjedhjes lloj - por ai u leveraging këtë hapësirë ​​shtesë për llojin e gjërave të shkuar mbrapa dhe me radhë duke i mbajtur gjërat në rregull. Dhe, edhe pse ai ndjehet si ne e mori në një listë të renditura, që ndjehet si ajo mori një kohë. Në realitet, ajo Rob ishte bërë ishte pikërisht këtë algoritëm. Ai së pari mori problemin e madhësisë n, ndarë atë në gjysmën e majtë dhe një gjysmë të drejtë. Kjo është kur ai shkoi në gota. Pastaj ai përsëriti këtë proces. Ai ndahet në 4 grupe të 2 2 mbi këtu dhe mbi këtu. Pastaj ai përsëriti se procesi dhe të ndarë në 2 grupe 2 e 1 për secilin nga këto gota të ndryshme. Dhe kjo është ajo ku lind mundësi e shkëlqyer. Në atë moment në histori, Rob kishte 8 listat e madhësisë 1, të gjitha të cilat janë të renditura tashmë. 

Pra, atëherë çfarë bëri ai të vazhdojë të bëjë? Pairwise ai mori këtë listë të renditura dhe kjo listë të renditura dhe të bashkohen ato. Pastaj ai mori këtë një dhe të bashkohen ato, atëherë këtë një dhe të bashkohen ato, atëherë kjo dhe u bashkua tyre. Dhe pastaj çfarë bëri ai të bëjë tjetër? Ai pastaj ri-bashkua listat më të mëdha dhe pastaj ri-bashkua listat më të mëdha. Dhe në qoftë se ju mendoni për këtë vetëm intuitive për tani, çfarë është ai me të vërtetë duke bërë? Ai u ndarë problemin në gjysmë, në gjysmë, në gjysmë, në gjysmën në mënyrë që të marrë këto lista super të vogla. Pastaj ai ishte lloj i kombinuar dyfishtë, të dyfishtë, të dyfishtë, të dyfishtë. Kështu që ai kishte bërë dy herë më shumë punë siç kemi parë deri më tani me çdo gjë që përfshin përça dhe sundo, por jo punë e madhe. Puna dy herë më shumë nuk është e tillë një punë e madhe. Kjo është vetëm një faktor konstant. Dhe shumë si shprehjes sonë aritmetike para, unë jam vetëm duke shkuar për të kaluar nga faktorë të vazhdueshme si kohë 2. Kush kujdeset? Nëse kjo është miliarda herë 2 2, që është ende shumë hapa. Pra, ky hap shkrirjen duket të jetë pasqyrë kyç. Le të ecin nëpër këtë vetëm numerikisht më parë - Oh, kjo nuk është për të vazhduar ende. Le të ecin nëpër këtë numerikisht vetëm për të vërtetë shohim se si kjo luan jashtë. Kjo është kryesisht vetëm një njeri i vogël animacion varfër. Le të propozojë këtë. Ora drejtimin e lloj bashkojë - ne duhet vetëm një mënyrë për të folur në lidhje me këtë. Kjo nuk është matematikë, kjo është vetëm një lloj mënyrë për të shprehur veten ngjeshur. Pra, T përfaqëson kohën dhe n paraqet çfarë? >> [Student] Madhësia e - 

[Malan] Madhësia e problemit, numri i njerëzve. Kështu që unë jam duke pretenduar se koha kandidon për të zgjidhur njerëz n do të jetë sasia e kohës 0 nëse n është më pak se 2, sepse në qoftë se ju keni 1 filxhan ose jo gota, ju keni asgjë për të zgjidhur. Por në përgjithësi, unë jam duke shkuar për të propozojë që koha kandidon për të zgjidhur elementet n do të jetë koha që duhet për të zgjidhur gjysmën e majtë plus gjysma e djathtë plus - çfarë është kjo shtesë + n? >> [Student] lloj Merge. [Malan] Është e vërtetë bashkimin, sepse në qoftë se ju keni n / 2 elemente këtu dhe ju keni n / 2 elemente këtu, sa kohë nuk është marrë për të bashkojë ato? Ashtu si Rob, ju duhet të këpusin këtë një mbi këtu, ndoshta këpusin gjatë këtu, shpuploj gjatë këtu, nxirre gjatë këtu, nxirre mbi këtu. Ju duhet të prekë secilin nga gota dikur. Dhe në qoftë se ka 4 gota plus 4 gota, që është 8 gota ose, më në përgjithësi, 8 gota n. Pra, hapi bashkimi ne mund të shprehim si n, dhe që fjalë për fjalë përfshin numrin e herë Robi prekur fizikisht një nga ato gota polisterol. Pra, le të bëjmë tani një shembull arbitrar. Nëse ka 16 gota, çfarë është koha drejtimin e klasifikim, duke përdorur algoritmin e Rob, 16 gota? Kjo është 2 herë sasia e kohës që duhet për të zgjidhur 8 gota Sepse ne kemi 8 gota këtu, 8 gota këtu. Unë nuk e di se sa kohë që merr, kështu që ne jemi duke përgjithësuar atë si T për momentin. Kush e di se çfarë është ajo? Por tani unë mund të lloj nga Recursively ose të përsëritur të kërkojë të njëjtën pyetje. Sa kohë nuk është marrë për të zgjidhur 8 gota? 8 gota Unë jam duke shkuar për të thonë merr sasinë e kohës që duhet për të zgjidhur 4 gota plus 4 gota, pastaj bashkimi i tyre së bashku. Gjobë. Ne jemi duke hyrë në një cikël tashmë. Sa kohë duhet të marrë për të zgjidhur 4 gota? Koha që duhet për të zgjidhur 4 gota është 2 gota plus 2 gota klasifikim plus procesi bashkimi. Gjobë. Sa kohë duhet të marrë për të zgjidhur 2 gota? 2 gota është sasia e kohës që duhet për të zgjidhur 1 filxhan plus koha që i duhet për të zgjidhur një filxhan plus sasinë e kohës që duhet për të bashkojë, e cila është vetëm 2. 

Gjobë. Pyetja e fundit. Sa kohë duhet të marrë për të zgjidhur 1 filxhan? Këtu është rasti bazë që kemi parashikuar ne do të goditur më herët. Fakti se ajo merr asnjë punë të lloj lloj më të vogël të problemeve do të thotë se tani, lloj i stilit klasën e shkollës, ne mund të shkoni vetëm të fillojë mbylljen këto numra back in Ne tani e dimë se çfarë T e 1 është, kështu që unë mund të vihet në prizë për T 0 i 1. Kjo do të jepni përgjigje të T e 2, që unë pastaj mund të prizë në UP lartë. Kjo do të më jepni T e 4, të cilat unë mund të vihet në prizë më lart. Kjo do të më jepni T e 8, të cilat unë mund të vihet në prizë më lart. Dhe në qoftë se unë të bëjë në fakt në dukje se me mbylljen e matematikës në këto përgjigje, Unë pastaj merrni T e 16 është 64. Dhe çfarë do të përfaqësojnë 64? Nëse T është 16, vërtet, ajo është 16 herë 4. Kështu që unë pretendojnë tani se koha drejtimin e këtë gjë të quajtur bashkojë lloj - dhe kjo do të jetë fanciest nga ato që kemi parë deri më tani - do të quhet n log n për shkak se sa herë mund të vjedh ndarë një bandë e tërë e gota në gjysmë? Identifikohu n. Është e njëjtë si shembull librin e telefonit, ajo është e njëjtë si shembull vetë-numërimit. 

Sa herë mund të ju ndajë diçka në gjysmën e? Megjithatë, ka ky hap bashkimin. Ju mund të keni për të ndarë gota në gjysmën përsëri dhe përsëri dhe përsëri, por çdo herë ju jeni do të duhet të bashkohen. Dhe kemi thënë më parë se shkrirja gota n merr hapa n sepse ju keni për të këpus nga një filxhan, nxirre nga një filxhan, dhe ju duhet të prekë çdo filxhan herë, ashtu si Rob bëri. Pra, nëse ne jemi duke bërë diçka log n herë dhe ne jemi duke bërë gjëra n në secilën prej këtyre përsëritjeve, secili prej këtyre halvings, ne kemi n log n herë. Pra, nëse ne prizë në 16 në këtë shembull, 16 herë hyni e 16 - mos u bëni merak se pse ky është rasti tani për tani, sepse unë nuk e kam tërhequr bazën - por log i bazës 2 të 16 është 4, 16 herë 4 është 64. Por nga ana tjetër, në qoftë se ne e kishte përdorur lloj flluskë apo renditjes apo futje e përzgjedhjes lloj me 16 numra, çfarë do kohë kanë qenë running nëse n është 16? Ajo do të jetë 16 katror, ​​e cila është 256, i cili edhe në qoftë se ju nuk e keni ndjekur mjaft gjitha matematikë e, 256 është më e madhe se 64. Kjo është me të vërtetë magjike takeaway këtu. Dhe të kuptojë se puna me këtë në shembujt më të vogla si ju do në një pset bën të gjitha shumë më intuitive. Por ajo që me të vërtetë do të thotë në aspektin e të ndjehen të këtij algoritmi është kjo: Nëse ne shikojmë në të vërtetë lloj shkrihen këtu - më lejoni të tërhequr atë deri në këtë dritare këtu - ky është një shembull paksa e ndryshme ku ne kemi të gjitha 3 e këtyre algoritmeve - flluskë, përzgjedhja, dhe të shkrihej - vetëm krah për krah. 

Ata kanë filluar të gjithë me bare të rastit, dhe kjo është e mirë. Askush nuk ka një përparësi themelore mbi tjetrin. Unë jam duke shkuar për në një moment klikoni secilin nga këto animacione - Start, Start, Start - aq shpejt sa unë mund të në mënyrë që, përafërsisht, të gjithë ata fillojnë në të njëjtën kohë, dhe le të konsiderojnë se rasti më i keq Rendit Bubble së running kohë është ajo? >> [Student] N katror. N katror. Rasti më i keq Rendit përzgjedhës drejtimin kohë është? N katror. Dhe lloj bashkojë është me sa duket - edhe në qoftë se ju nuk e keni mjaft të ndjekur të gjitha matematikë e tani, ajo do të bëhet shumë më i kuptueshëm me kalimin e kohës - është, ne pretendojnë, n log n herë. Dhe për shkak se log n është rreptësisht pak se n pasi ne kemi një numër të madh, n log n herë është më i vogël se sa herë n n ose n katror. Pra, çfarë e bën atë të ndjehen të jetë në fakt një algoritmi të mirë në aspektin e kohës që kalon, n log n herë në krahasim me n katror? Këtu ne do të shkojmë. Kliko, click, click. 

Kjo është ajo që do të thotë që të përdorin diçka si lloj bashkohen. Ne kemi një moment. Le të shohim se çfarë ndodh këtu. [Chuckles] kujt paratë është në lloj flluskë? Ai në vend të varet nga të dhëna ndonjëherë. Le të shohim. Come on. Ajo ndjehet si ai është zënë hapin. >> [Student] Shko lloj flluskë! [Students gumëzhimë] [Malan] Yeah, yeah. [Studentët gumëzhimë] Shko, shko, shko! [Gjithë brohorisnin duartrokitje] [] Deri tani me 1 demo e fundit, përfundimtar, nëse kjo është një ndërlikuar pak për të përfunduar mendjen tuaj rreth matematikë ose lloj i vizualizimi atje, ju në fakt mund të dëgjoni shpejtesi e algoritme të ndryshme të ndryshme. Kjo është një animacion i bërë dikush që në fakt tingëllon bashkëpunëtorët me procesin e shkëmbejnë dhe lartesia e bare. Ndërsa ne do të shohim këtu, ka një pak më shumë algoritme zgjidhja atje që folks kanë menduar. Kjo e para do të jetë lloj futje, dhe kjo do të fluturojnë me anë të dhe do t'ju japë një ndjenjë audible se si këto punë të ndryshme algoritme. Këtu është lloj futje. [Beeping elektronike] [Malan] Bubble lloj. [Shpejt beeping elektronike] [Malan] Përzgjedhja lloj. [Shpejt beeping elektronike] [Malan] lloj Merge. [Beeping elektronike] [Beeping ngadalëson] [qeshur] [Malan] lloj Gnome. [Beeping elektronike] 

Kjo është CS50. Ne do të shohim se javën e ardhshme. [Duartrokitje dhe brohoritje] 

[CS50.TV]