[Powered by Google Translate] [3 недеља, наставак] 

[Давид Ј. Малан - Универзитет Харвард] 

[Ово је ЦС50. - ЦС50.ТВ] 

У реду. Добродошли назад. Ово је ЦС50 и то је крај недеље 3. 

Дакле, за оне који нису упознати, прошле године Харварда покренуо оно што назива иновације Лаб, или и-лабораторија, која је дивна зграда преко реке на кампусу ХБС-а који је отворен за студенте, ученике, студенте ГСАС из целе кампуса, укључујући факултет, и то је место да заједно раде на иновативним стварима, посебно предузетничке ствари ако ти и 0 или више пријатељи мисле да раде нешто предузетнички или током ове класе, после ове класе, или шире. 

Дакле, једна од ствари које они раде преко Ј термина је та путовања, од којих је један у Њујорку, један од којих је Силиконске долине. Простор је веома ограничена, али то је прилика да трљајте рамена са МБАс и дипломирани студенти широм кампуса и заправо проводе време у тим појединачним областима ћаскање до стартупс, ћаскајући уп предузетнике и слично. Дакле, ако заинтересовани, погледајте ово овде УРЛ. Такође је доступан на слајдовима онлајн. 

Можемо Укротити кућу звук само мало? Уколико желите да нам се придружите на ручку у петак, 1:15 ам у Фире & Ице, молимо главу тамо. Извињење ако је образац већ попуњен у време када стигнемо. Али ми ћемо наставити ову традицију напред. 

Данас настављамо виши ниво дискусије о различитим проблемима које можемо решити, фокусирајући се много мање, данас барем на коду и много више на идејама. Дакле, мислим да врати у недељу 0 када смо цепали телефонски именик на пола, чији је циљ био да уради нешто, додуше, мало драматична али да пошаље тачку која тражење не мора да буде нужно, као очигледна на први поглед, као што мислите. И решавање проблема у целини не мора увек да буде најбољи - Најочигледнија решење не мора нужно да буде најбољи. Дакле, имали смо тај телефонски именик и, искрено, све нас у овој соби имали инстинкте, највероватније, за почетак у средини када тражите Мајк Смит и онда идите лево или десно на основу год слово азбуке смо се десило да заврши он. 

Али то једноставна идеја које су ми људи узимају здраво за готово тако дуго Стварно би требало да почне да дођу у први план вашег ума јер као што су проблеми бити много сложенији него телефонском именику, ти исти једноставни, сјајне увиди шта ће нам омогућити да реши много компликованије и занимљивије проблема, међу њима неке од ствари које узимамо здраво за готово већ ових дана. Милијарде страницама тамо, и још увек Гоогле и Бинг и као су у стању да пронађе ствари за нас тако. То не дешава помоћу линеарне претрагу, претражују кроз све могуће веб страницама. Фацебоок је у стању да вам кажем ко је све од ваших пријатеља су или пријатељи пријатеља, и да превише може наизглед урадити у тренутку ових дана иако они имају милионе корисника. 

И тако како смо у ствари решавају проблеме на тој скали ће на крају смањити идејама смо гледали у недељу 0 и још мало данас. Нећемо поново изврше овај алгоритам, али сећам се такође радили у недељи 0 овој вежби где смо сви устати, узети на броју 1, и онда смо сви само бројање до упаривања искључена, додајући заједно своје бројеве, од половине банде сео на свакој итерацији. Тако смо ишли од 500 студената на 250 до 125 и тако даље. Али, као што смо рекли у понедељак, моћна идеја постоји је да ако удвостручио величину тог проблема а сва деца из правосуђа или ЕЦ 10 вратио у собу и придружио нам се, добро, вероватно би могли да рачунају да целу групу агрегатну са само још 1 велики итерације петље, јер би можда само удвостручи величину или у ЕК 10 слуцају мало више него дупло од величине. И тако смо морали да проведу мало више времена, али ми не би морали да потроше 400 или 700 више корака. 

Само да сликам ову слику на начин који је мало мање апстрактно, да нису сви устану. Али, ако они од вас који су изабрали да седи у оркестру данас не би сметало стојећи, Хајде да видимо да ли можемо да схватимо међу вама ко је највиша особа тако раде исту врсту компаративне алгоритма. Дакле, ако сте седели у оркестру, извињавам, али корак 1, устани; корак 2, пар офф са ким сте у близини, схватим ко је виши, и седите ако сте краће. Затим поновите. [Студенти мрмља] 

Ок. Ок. Један је остало стоји. Које је твоје име? >> Андрев. 

Ендрју, ти си највиша особа у оркестру одељку данас. 

Честитам. [Аплауз и навијање] Ок. Седите. Дакле, нашли смо Андрева. Али, колико дуго би ме узети, на пример, да бисте пронашли Андрев У овом оркестру делу 50 + или тако људи? Могао сам узети прилично једноставан приступ и почети овде. И ја сам 2 особе устане и само сам их упоредите, и онда кажем ко је нешто краћи, "Ок, ти седи" и ја ћу да се сетим ко виши човек био. Онда сам, понављам, понављам, понављам, и ја се ослањам на највиши лицу док не надјем неко мало виши од њих, након чега нешто краће особа има онда седнем. Али у том алгоритма у овом делу оркестра, ако постоји н тебе, колико корака је да алгоритам ће трајати? >> [Ученик] Н. 

То ће да се н, зар не, јер у најгорем случају, да тако кажем, највиши човек је последња особа коју сам се да само случајним лоше среће. Дакле, у најгорем случају, време рада тог алгоритма је линеарно, то је н где је н укупан број људи у простору, величина проблема. Шта о овом алгоритму? Чињеница да сте сви устали, а затим опет половина вас седе, пола од вас седе, половина од вас сео. Колико корака треба да су предузети ако овде има н тебе? [Ученик] Н лог н. >> То би било још горе. Лог н. 

Дакле лог н, чак и ако не баш сећам се шта је логаритам, за сада, само ценим да је некако односи на то преполови и преполовљавање и преполовити. То не мора да буде фактор 2. То би могао да буде фактор 3. Али то је то понављање исте врсте фактора такав да је величина проблема почиње овде али одмах затим иде овде, онда овде, па овде, па овде. Нећеш узимајући мале залогаје из проблема, ви стварно сецкања далеко на њу са велики налету сваки пут. Дакле, имали смо 50 људи, па 25, па 12 ½ или 13 људи стоје, онда 6 ½ и тако даље све док коначно само Ендрју је остало стоји. Дакле, ми ћемо звати тај дневник н, и можете замислити ово на следећи начин. Подсетимо ову слику овде где линеарни алгоритам је као црвене линије, жута линија је пребројавање од алгоритма 2С који смо користили за бројање студенте у прошлости, али данас је свети грал ће остати ова зелена линија где ако се удвостручио број људи у одељку оркестар или само рекао, пакао, хајде да сви у целој просторији устане, не тако страшно јер смо отприлике дупло колико људи овде доле, 1 више итерација, а не проблем. 

Нашли смо Ендрју или ко се дешава да се виша од Андреја у међуспрату, или на балкону. Дакле, овом једноставном идејом да смо ми толико здраво за готово у телефонском именику, схвате да постоји толико много различитих места у којима можемо да га примењују. Први Заправо, него жаргону - Само да ошамарим неки жаргон пусти ме да одем на овој слици овде. Сада смо причали о н и н / 2, а затим се пријавите н, али сигурно можемо доћи до, како ћемо током семестра, Друга врста математичких формула да опишем овај општи појам приказују време. Ово су ван контекста за сада, јер ћемо видети ускоро алгоритми који ово заправо представљају. 

Али приметите овде линеарна линија н, права линија, је заправо веома ниска указујући сада. То је нека врста оптичке илузије у које смо управо променити оно к оса представља и и оси, и можемо да направимо праву линију поинт у било ком правцу желимо. Али разлог што је тако очигледно равна сада је зато што је потребно да би се направио простор на овом графикону за много споријим раде пута. За сада, знам да постоје неке прилично лоши алгоритми у животу, од којих неке не предузме кораке н или, још боље, пријавите н кораке, али још много тога. Дакле, изнад линије н овде у доњем обавештења има н пута лог н, па ћемо видети шта то значи пре дуго. Изнад да је н квадрат, а ми још нисмо видели никакве н квадрат алгоритме али ми смо о томе да. И то изгледа заиста лоше. Има 2 до н, нешто експоненцијална, што се осећа још горе. А ипак, зачудо, онда постоји н кубу, која ако си врста размишљања напред, Ако некако урадите математику, 2 до н заправо постаје много равнији, много већи него од н куб, ако се осврнемо на осама довољно далеко напоље. Дакле, приметите сада ове линије су самовољно 2 до 10 на к оси. 

А шта то значи? То значи да људи 2 10 људи у просторији. То је све к значи: величина проблема, шта год контекст. И вертикална оса сада је број секунди или број корака - нека јединица времена. Али приметите да је од 0 до 60 и 0 до 10. Али ако мало умањили, као што сте можда у Екцелу или неком графикона софтвера, и идемо до 200.000, приметити да се нешто као 2 до н ће у потпуности порази трчање пута од н квадрата, н куб, н лог н - све смо причали о до сада. А ипак цака је када почнете да говорите о стварима као што су Фацебоок где сте много, много, много људи све међусобно повезани, сте н људи, од којих сваки може имати колико н пријатељима ако су сви некако ортак у свету, добро, то је н пута н већ, тако да је н квадрат могуће пријатељства, барем у 1 правцу, н квадрат могуће пријатељствима. Тако да је већ сугерише да тражи Фацебоок-социјалног граф, да тако кажем, може да почне да се изражава у оваквим формулама. 

Ми ћемо се вратити и учинити то много конкретнији, али за сада, циљ за наредних неколико недеља ће бити сигурни да не иде о имплементацији алгоритама или кодекса који завршавају узимајући као много времена као нешто овако. Али фасцинантно ствар информатике, ако настави у овом пољу узимајући часове као ЦС121, ЦС124, оба од којих су теорија курсеви, је да заправо постоје неки проблеми који постоје на овом свету која у основи, колико ми знамо, не може бити решен брже него најгори ових графова заправо сугерише. Дакле, постоји много отворених проблема у овом свету да ураде много боље него што људи имају до сада. 

Па почнимо онда са овом примеру. Видели смо Шон борбу са овом камером, сувише неспретно на видеу. Али, реалност је била када је Шон је био задужен за проналажење на броду овако је број 7, сећам се да сам то рекао, "негде постоји иза тих комада папира или бела врата "Број 7 Шон, наћи га за нас.". И то је било дивно непријатно гледати јер је стварно бори са овим проблемом. Али, реалност је Шон је као и свако ко у просторији може да уради. Он је мало дуже од типичног лица могу имати, али је претпоставио да постоји нека трик за овај проблем, Он претпоставља да је нешто недостаје. И то није помогло да су стотине очију имајући доле на њега. 

Али реалност је да улаз на проблем је гомила случајних бројева а ви се тражи да пронађу 1 такав број, Најбоље што можете да урадите је линеарно претраживање. Почните са леве стране, померите удесно, или се крећу удесно, померите у лево. Ретроактивно, можемо да размишља ", Шон, зашто не почнете са другог краја?" Па, 7 могао исто тако лако био овде случајно, али сам намерно ставио тамо, јер сам схватио да неће почети крајем. Тако сам некако манипулисао ситуацију, али до случајног случајно 7 могао нигде било. Дакле, почевши од десног краја можда било боље онда, али шта ако се следеће године креће 7 другде? То није суштински ново решење проблема - почевши од 1 до краја, или други - када си дао никакве друге претпоставке. Дакле, Шон почео гледајући кроз бројеве, а он је рекао: "5 То није овде.". Онда је овде отишао и видео 19 година, онда је застао за око 20 секунди, онда је отворио ово за 13, а онда је постало јасно да не изгледа да буде овде образац. То није било 1, 2, 3, 4 или слично. Било је празнине у броју који не помажу. И такође, чињеница да сам користио ове јефтине комада папира да прикрије бројеве је заправо намерно, јер ако сам уклонио све те папире, већина нас, Шон укључен, вероватно би погледао врста макроскопски на табли и рекао: "О, 7 је очигледно тамо." Ми смо то урадили одмах. 

И то може бити начин на који људски мозак ради у извесној мери, али у стварности, његове очи или ум је вероватно скимминг бројеве са десна на лево, лева на десно, средње напоље - да се нешто дешава физиолошки таква да се осећао као да је одмах дешава, али шансе су чак интерно постоји нека врста методологије за проналажење 7. И заиста, сада када говоримо о низовима и структура података и сећање унутар рачунара, једино ми људи могу да ураде се осврнемо на појединачним меморијским локацијама 1 у исто време. 

Дакле, свака друга локација можда и бити покривени са неким комадом папира јер не можемо да га видим. Можемо само до 1 ствар у једном тренутку. Дакле, у овом случају, у случају Шон, ми овде отишао и онда смо отишли ​​овде а онда смо отишли ​​овде, овде, овде, овде, имам паметан до краја и некако прескочили ову произвољно и нашао 7 тамо. Ово није била посебно посебна. То је такође био у квару. Али он је коначно нашао 7. Али сада ПОНЕТИ заиста то најбоље што можете да урадите када се дају никакве информације осим случајно разврстаних бројева је да се почне са леве стране, или почети са десне стране. Или врага, можете случајно да отвори врата, али чак и онда шта то значи бити случајно? Па, ми смо морали некако да се формализује оно што значи да овде почне, онда идите овде, онда идите овде. Шон је одлично, и то је био само забавно гледати. Шта ако, уместо да променимо тај проблем мало и довести до Шона овогодишњи, ако хоћете? Да ли би ико буде удобно стиже на сцену и решавање мало другачији проблем и појављује пред камерама? 

Идемо даље оркестра, јер ви сте били прилично укључени данас већ. Како би у розе, у шеширу? Хајде доле. Како се зовеш? >> Алекс. >> Алекс. Ок. Дакле, Алекс ће бити овогодишњи Шон и појавиће се у наредних неколико година вреди ЦС50 предавања. Алекс, драго ми је. >> Драго превише. Изазов при руци за вас је да сте га мало лакше у да вам говорим исте бројеве овде, али они су сада поредани. Дакле, сада је ваш циљ је да се пронађе број 7. И заиста, заиста би требало да ово - ти си врста преваре, као компјутер не би, гледајући шта су бројеви били пре тренутак. Са кредом то заправо неће помоћи све то много, али хајде да се претварамо да не знамо шта је оригинални низ је. Све што сада знамо је да имате низ бројева сортираних да можда има празнине између њих, а ваш циљ је да се пронађе број 7. Како би ти, разуман човек, иде о проналажењу број 7? 

Идите од ниског до високог? >> Реду. Иди ниске до високе. И немојте их скинемо. Хајде да их подигне, тако да можемо да их поново. Ок, 1. Чекај. Пре него што наставимо, то је 1, јасно погрешно. Дакле, шта се дешава кроз главу следеци? Који је ваш следећи потез? Следећи један. >> Реду. Следећи један. Добро. 3, тако нетачно. Који је ваш следећи потез? Настави даље. >> Реду. Настави даље. 5. Зато наставите даље, и дозволите ми да вам дам ово за потомство. 7. >> Одлично. Врло добро. Пронађено број 7. [Аплауз] Тако да је била добра, али је Шон такође нашао број 7. И тврде да нисте заиста експлоатисана ову додатну информацију, а то је да су ови бројеви сортирају. Дакле, можемо да урадимо боље? Свака сугестија овде? Да, у назад. [Ученик] Бинарна претрага. >> Немам појма шта је бинарна претрага. 

[Ученик] Старт у средини. >> Почетак у средини. Ок. Дакле, хајде да видимо да ли можемо да стигнемо тамо. Дакле, ако сте већ рекли старт на средини, само напред и отворите средњи врата. Има 8 од њих, тако да ћете морати да произвољно изабере онај мало лево или десно. Ок. 7! [Аплауз] Веома лепо. Ок, али где смо били иде са овим? Претпоставимо само да раскине везу сте овде почела јер то исто могло да се деси, као добро. Ми смо се управо догодило да знамо да је 7 био тамо. Дакле, ово је 13. Дакле, ако они сортирају и само смо почели у средини, шта би оптимално следећи потез био? Идите лево. И тако ево опет именику пример. Ако 13 је овде и знамо листа сортирана, онда све ове папирица су незанимљиви да нас сада јер већ знамо да мора да буде 7 лево ако су ови бројеви се сортирају и пронашли смо 13 година. 

Дакле, шта је ваш следећи потез овде? >> Иди на лево. >> Добро, добро. Па иди на лево, и - чекај, хеј, хеј, хеј. То је варање. Тако сте нашли 7, али шта је алгоритам смо управо примењује? Почетак у средини. >> Добро. Дакле, шта је логичан наставак те исте идеје? Ох, само ово. >> Тачно. >> Дакле, ја сам овде почети. >> Добро. Дакле, сада смо мало отишли ​​на лево поново. То је 3. Али је интересантно ПОНЕТИ сада је која може учинити да не морамо да бринемо о? Ове 2. >> Ове 2. Дакле, сада је то не може отићи, то може отићи. Сада је проблем који је тада био 8 величине 4 сада је величине 2. Ми смо веома близу. Опет, идите на средини ова 2 елемената. 

Ок. Дакле, то је некако несрећна да сада смо увек идемо отишли ​​јер смо заокруживање наниже. Али то је у реду, јер сада баци то далеко и све остало, остављајући нас са само 7 година. Дајмо аплауз. Нашли смо 7 поново. [Аплауз] Ок. Наравно. Држи се за само 1 секунду више. Иако да ће идуће процес врста трајало мало дуже него што смо сматрали да би, Искрено, ваш први инстинкт били најбољи, зар не? Нашли смо 7 тренутно. Али, ми бисмо нашли 7 брже, без обзира шта, у овом примеру наспрам овога јер ако су ти бројеви су сви сортирају, налик на страницама у телефонском именику, ви заиста можете исецкати половину проблема поново и поново и поново. И то није баш тако лако да види ово са само 8 бројева насупрот 1.000 странице именику где заиста види визуелно, али у овом случају, када овде Шон је тражио 7, колико корака у најгорем случају би га узео? >> [Ученик] 7. 7 у најгорем случају. Па, у најгорем случају не 7 ако овде има 8 врата. То би му узети 8 корака. 

Дакле, ако постоји н врата, можда су се Шон пре пар година н корака. Сада, у вашем случају, Алекс, с обзиром да су ови бројеви сортирају - и можемо закључити врста овог одакле смо били до сада у овој причи - Шта је време рада више интелигентног алгоритма Алексово покретања од средине и онда понавља? [Ученик] 3. >> Дакле то ће бити 3, отприлике, ако идете од 8 до 4 на 2 до 1. Дакле, 3 корака или, генерално, то је лог н опет. Сваки пут када се преполови и преполовљавање и преполовљавање и преполовити, То је израз ове идеје лог н. И то би вам узети само 3 корака, и заиста јесте када смо отворили врата преполови и преполовити, док би узели неке Шон 7 или 8 корака. Дакле хвала вам што сте били са нама у овој години. >> Хвала. Лепо смо се упознали. Хвала Алек. >> Исто тако. [Аплауз] 

Шта је онда прави импликација овога? Сада замислите да то није 8 врата, која, искрено, сви од нас могао наћи нешто иза врата 8 прилично брзо само по кидање комада папира и одлазак са нашим инстинктима. Али шта ако је милион врата? Шта ако је 4 милијарде врата? У случају 4 милијарде врата, стварно ћеш желети да иде са алгоритмом Алексово, Бинарна претрага као ћемо почети називајући га или завади па владај, генерално, где држиш преполови и преполовљавање проблем, јер ако имате 4 милијарде врата, колико пута можете исецкати 4 милијарде на пола? [Ученик] 32. >> То је заправо 32. Можете да радите ово се на парчету папира или у вашој глави. Ти иди 4 милијарде до 2 милијарде до 1 милијарде пола милијарде долара, на 250 милиона евра, тачка, тачка, тачка. А ако ти се у математику, ти ћеш заиста добити 32, и да заправо односи на рачунарске науке, јер се обично рачунају у надлежности 2. 2 до 32 деси да буде 4 милијарде. Дакле, постоји много значаја за ове врсте овлашћења 2 у рачунарству. 

Али шта је са 8 милијарди? Колико корака је да ће се предузети ако постоје 8 милијарди врата? [Ученик] 33. >> Дакле 33. Шта ако има 16 милијарди врата? Колико корака је да ће то трајати? [Ученик] 34. >> 34. Могли врста наставимо ову наусеам огласа. Али то је моћна ствар. Можете увести милијарде више улаза за ваш проблем, али ништа страшно, само узмете 1 додатни залогај од њега и тако нам пружа нешто као бинарни претрагу или завади па владај, више уопштено. Али ја сам некако вара, зар не? У случају алгоритма Алекс, она је имала предност над Сеан. Знала је да су ови бројеви сортирани, али Алекс није морала да их сортирате себе. Ја се унапред дошао до табле и врсте побринуо да сам нацртао их све у сортираном поретку, онда сам их покривене са папиром. Али, колико је то посао ме? Да смо кренули са овим бројевима у неком наизглед случајним редоследом - у овом случају ови бројеви једноставније, 1 до 8 овде - како ми иде о сортирању ове вредности? Ако сте људско дат овај задатак, какав интуитиван приступ би узмете да сортирање гомилу бројева? Ове ствари су постављени као слагалица комада. Да. 

[Ученик] ја би сваки број и упоредите га са сваком и наставите са леве стране. >> Добро, добро. Дакле, узмите сваки број, упоредите га на један поред њега, и онда само наставите да се креће на листи, врсте рејиггеринг ствари као ти. Дакле, овде имамо шансу за можда неколико више људи да се укључе. Да ли имамо још 8 волонтера који би волео да дође горе? Мало мање притиска јер вас нисмо једини. 1, 2, 3, 4, 5, 6, 7, 8. Хајде доле. Ви момци ће бити бројеви 1 до 8 година. Хајде да видимо, ако не можемо учинити ово сортирање за Алекс много на исти начин на који сам то урадио унапред. 1, 2, 3, 4. Само напред и ако би, построје на сцени између музичког штанда и мене овде у истом редоследу као слајд на екрану. Ух-ох. Ми ћемо вас радити у следећем примеру. Ох, чекај, чекај. Идемо. Чекај. Следећи пример је сада. Изволи. Број 8. Хајде горе. У реду. Сортирање себе према овоме. Померите само мало са стране музике стоје овде. Тако имамо 4, 2, 6 - иди тамо, овамо, тамо - 3. Да. Ок. Ти иди овамо. Не, остани тамо. Да, баш ту. Не, ја сам погрешио. Тамо. Добро, веома добро. Ок. Па хајде да их сортирати у растућем редоследу. 

Како да идем око радиш ово? Алгоритам који је предложен пре тренутак је био разлог зашто не бисмо упоредили су људи који су некако једни поред других, а затим исправите евентуалне грешке, креће с лева на десно. Дакле, овде имамо 4 и 2, очигледно не ради. Хајде да те замене. Ок. Дакле, сада ћу да се креће низ линију. 4 и 6, нопе. [Смех] 6 и 8, прилично добро. 8 и 1, дозволите ми да вам замене момци. У реду. Дакле, 8 и 3, замените момци. 8 и 7, дозволите ми да вам замене момци. 5 и 8, одлично. Ја вам сортиране листе. У реду. Дакле, не сасвим. Али то је боље, јер су веће бројеве - Случај у тачки 8 - су врста бубблед се из леве у десно. Тако сам у праву 1 од њих, али се осећа као да се то није сасвим реши проблем. 

Дакле, шта би ти предлажем да урадите следеће? >> [Ученик] Нека то раде. >> Смо да радиш. И схвати, опет, ми смо поставили ствари које само што све људе некако интелигентно се организују на основу тог слику, али сада морамо да будемо много методичан. Морамо да будемо алгоритамски о томе као да смо писања кода - у овом случају вербална Псеудокод. Дакле, дозволите ми да покушам поново. То је радила прилично добро. Није га реши. Али када се сумња, само покушајте и покушајте поново. Дакле, 2 и 4, није помогло више. 4 и 6. Ах! 6 и 1, благо боље. 6 и 3, добро. 6 и 7, 7 и 5, 7 и 8, добро. И знате, ја вероватно могу игнорисати 8 сада, јер је он на крају листе. Можда не морамо да бринемо о томе ће неко поред њега. Али, хајде да видимо да ли је то безбедно претпоставка. Сада је листа - проклето - не сортирају. Хајде да покушамо поново. Дакле, 2 и 4, 4 и 1, 4 и 3. 4 и 6, добро. 6 и 5, добро. 6, 7 и 8, добро. Али обавештење, могу само зауставити овде и зауставити овде? [Ученик] Да. >> Да? Шта ако неко од вас био број 9 скроз тамо? То би било сређено. >> Добро. То би било поређано по први пут около. Добро. Дакле, хајде да се вратимо поново. Скоро смо стигли. 1 и 2, 2 и 3, 3 и 4, 4 и 5, 5 и 6, 6 и 7, 7 и 8. 

Сада сам урадио, али опет, ја сам рачунар који може само оно што ми је речено да урадим, и мој једини сећам јесте да сам заиста урадио мало рада. Нешто променило овде. Дакле, нисам технички потврдила визуелно или алгоритамски да је ова листа заиста сортирају. Дакле, само за добру меру, само да се анални о томе, хајде да урадимо ово 1 више времена. Дакле 1 и 2, 2 и 3, 3 и 4. И знате шта? Само за добру меру, ја ћу да пратите на мојој руци овај пут колико свопови направим, само да знам колико посла да сам заиста урадио. 3 и 4, 4 и 5, 5 и 6, 6 и 7, 7 и 8. Нема свопови. Дакле, сада сам легитимно бити идиот да то поново јер ако сам без посла кроз овај пролаз од људи, онда је јасно да ће се опет десити ако ниједан од њих је некако случајно адверсариалли се креће. Тако да сада могу зауставити. Сада идемо поставим питање, колико је то заправо посао ме? Колико корака је то трајати? >> Н квадрат. Да, тако н квадрат. Одакле ти н квадрат из? Ви морате да проверите сваки цилиндра - Ту је н број, а ви морате да проверите сваки број са другим н бројева. Добро. >> Дакле, то је н квадрат. >> Добро. 

Тако се осећа као да би то могло врло добро бити н квадрат, зар не? Ту је н од ових момака, 8 конкретно у овом случају, али сваки пут када сам прошао кроз ову листу сам поредећи прву особу против другог, други против трећег опет и опет и опет, и када сам дошао до краја, шта сам урадио? Ја га редид. Дакле, ако генерализујемо ово објашњење, ми смо н људи и ја правим, очигледно, 8 корака, Н кораке, сваки пут кад идем кроз овај алгоритам. Али колико пута у најгорем слуцају морам да прођем кроз ову листу људи? [Ученик] Н пута. Вероватно >> н, десно, јер у најгорем случају, шта је вероватно најгори случај аранжман од ових момака из добити-ићи? Ако они потпуно обрнут редослед јер само претпоставимо ментално, хајде - Како се зовеш? >> Бовен. Боуен. Ок. Дакле Бовен, дођи овамо на тренутак. 

Претпоставимо да Боуен је овде на почетку алгоритма, а ми не знамо шта сви остали, али Боуен овде, у складу са овим алгоритмом - и ако желите да само шетају са мном - ће испливати, као што је учинио први пут, све до краја. Али претпоставимо да је особа поред Боуен је број 7. Морам да се вратим број 7, што значи да морам да идем скроз назад. Сада морам да имам ту исту шетњу са особом која је број 7. Али шта ако је онда број 6 је био поред њега, као и? Онда морам да се вратим 6. Па опет, на свакој итерацији ове петље причам на сваки од н људи, и ја ћу можда морати да н ових шетње да будем сигуран да сам повлачењем сви највећих елемената леђа и назад и назад до самог краја листе. Дакле, н ствари н пута је само н пута н или н квадрат. 

Дакле, овде већ имамо алгоритам који се више не н, које се више не лог н, то је заправо гора од свега што смо урадили раније. Дакле, Алекс врста посрећило у који сам урадио сав посао очигледно напред за њу, све скупе рада, тако да би могла да ужива у овом бинарном претрагу алгоритам, што је дневник н. Али, то је у складу са темом у понедељак. Дали смо мало више простора, користили смо више бита, како би се убрзао наше време рада. Толико као да је ово траде-офф између времена и простора, Такође би могло да буде само компромиси између времена проведеног до предњег врсту добијање ствари спремна да иде и заправо извршава алгоритам као претрази. Хајде да пробамо још један. Ако ви не би сметало само брзо преуређивање себе да одговара опет, хајде да пробамо нешто мало другачији, где то није баш тако једноставно као поправити само све Паирвисе грешке, што је супер интуитиван. Хајде да, уместо да буде мало више намерна и урадили. Ово такође бих предложио је вероватно прилично интуитиван. 

Хајде да изаберете најмање особу са листе поново и поново. Дакле, идемо. 4, ви сте најмањи особа Тако сам видела до сада, па ћу да се психички запамтите да је управо указујући на тебе сада. 2. Оох! Заборави број 4. Управо сам нашао нови најмањи елемент у овој листи. Идем врсте запамтите то. 6, 8. Оох! 1. Довиђења. Дакле, сада ћу да се сетим броја 1. Знамо да је 1 најмањи, али ја сам рачунар. Шта ако постоји 0? Шта ако постоји -1? Морам да наставим. Дакле 3, 7, 5, нопе. Ок. Дакле, број 1 је био најмањи. Дозволите ми да вас изаберите са листе - ве'лл иде овако - и ставио вас самовољно на почетку листе. Сада, чекај мало. Некако преварени. Ако ови момци представљају не списак од 8 особа, већ низ, 8 комади целовите меморије - да ли ти смета изађе на тренутак? Заправо нема простора за тебе овде. Па како ћемо направити простор за - како се зовеш? >> Самми. >> Самми. Како правимо простор за Самми? 

Крећемо се н који су пре мене. >> Реду. Тако смо могли да преместите н људе који су пре њега, па ако ви желите да узме 1 намерно, драматичан корак са леве стране. Сви су то урадили у глас, али последњи пут сам написао нешто кода, Ви не можете некако креће много ствари одједном. Могли би то урадити у петљи, крећући се свима једном на време. Дакле, ако ви не би сметало корачање назад десно, и Самми, ако би могао да се повуче, јер још увек нема места за тебе, хајде сада да урадимо ово. Где је Семи пре тренутак? Тамо. Дакле, постоји јаз тамо. Дакле, можете да преместите на место Семи. Сада следећа особа горе и сада следећа особа, сад особу. Сада имамо простора за Самми. Сада, неко из публике - то је добро, то је тачно, осећала сам мало времена - шта је брже? Да. [Ученик] Нови низ? >> Шта је то? >> [Ученик] Нови низ? >> Добро, добро. 

Дакле, у складу са овом темом праведног компромиса, зашто не бих само да нови низ  и онда Семи ће купање у простору испред тих људи, на пример, а ми само можемо почети пуњење потпуно нови низ. И то ће радити. Али ја не интересује троши више простора данас. Шта је друго приступ? [Ученик] Замени. >> Реду. Ми смо само могли разменити ове 2 момке. Које је твоје име? Марио. >> Марио. Тако Марио, били сте тренутно овде. Самми, можете резервну копију за тренутак? Марио је био овде. Ми немамо више простора за вас, па ако ти не би сметало иде тамо где Семи је, ставицемо овде Самми, и сада бих тврде да Семи замене операција била много бржа. Урадили смо 1 операцију замене ове момке, или можда 2 до замене ове момке али ми нисмо урадили 1, 2, 3, 4, тако да се осећа боље. Сада, чекај мало. Некако се погоршава проблем, јер број 4 је некако близу почетка. Сада број 4 је мало ближе том циљу, али нисам баш знао или брига за то. Дакле, ово је само лоша срећа да је број 4 је мало даље од свог предодређеног места. Па хајде сад поновите овај алгоритам. 

Да подсетимо, докле год та прича је, све што смо урадили је проћи кроз листу у потрази за најмањом нумерисане особе. Дакле, хајде да то урадимо поново. Ми не треба да бринете о Семи више. Ми само овде могу да идем. Оох! Број 2. То је прилично мали број. 6, 8, 4, 3, 7, 5. Добро, добро. И срећом, случајно, не морам да се креће - >> Вили. Вили, јер он је у свом правом месту сада. Хајде да то урадимо поново и игноришу ове 2 момке. 6. То је прилично мали број. Оох! 8 је дефинитивно већи. 4. Хајде да се фокусирамо на 4. Оох! 3 је чак и боље. 7 и 5. Па шта ћемо сада да радимо са - >> Роџер. >> Роџер? Хајде да га замените са бројем 6. Дакле, ако 6 и 3 желели да замени, Сада смо некако стекли среће у том 6 ближи где она треба да буде, али то је само случајност овде. Дакле, хајде да сада овде. 8 је прилично мали број. Оох! 4 је мањи. 6, 7, 5. Шта ћемо сада да радимо? >> Замени. >> Тачно. Дакле, хајде да урадимо ову врсту брже. 8, 6, 7, 5. Где 5 иде? Добро. Ок. 6, 7, 8. 6 добија да остане где је. Које је твоје име? >> Росалие. Розали добија да остане где је. 7 добија се - Хајде да видимо. 7, 8. Ок. Дакле, 7 добија да остане где је. Које је твоје име? >> Амна. >> Амна. 

Дакле, Амна добија да остане где је и број 8 је већ где је сада требало да буде. Добро, добро. Осећа се само правите овде посла за себе, ипак. Шта је на крају време рада овог алгоритма? Ако мислимо о тим људима не као 8 али н? >> То је н. То је н кораке, али ми провере сваки пут. Ок. Н али ти провери сваки пут? У реду, али ако је н корака, не би требало да сам био у стању да вам сортирате само иде 1, 2, 3, 4? Ох! Ок, то је велика разлика. Па н квадрат зашто? Шта се стварно дешава? Има н људи у овој листи, али да пронађу најмањи особу на листи У најгорем случају, колико корака морам да узмем? >> Н. 

Н, зар не, јер у најгорем случају, број 1 је скроз тамо, па морам да идем да га или њу. И онда кад сам коначно схвате 1 је био најмањи, онда је прилично брзо да их замене. Али сада морам почети од почетка и тражити кога? Следећи Најмањи човек, што је за 2. Где у најгорем случају је 2? Ох, мој Боже. То је све овде на крају. Дакле, сада сам урадио још н корака, још н корака. И ако имамо н људе и, у најгорем случају најмања особа н корака, То је опет н пута н, па поново смо н квадрат. Ово се не осећа добро. А у ствари, чак иу најбољем случају - Претпостављам да су они кренути поредани - колико корака је потребно за мене користећи овај алгоритам за сортирање ове н људе? Н квадрат. >> Чуо сам н квадрат. Зашто н квадрат? Пошто још увек имате да проверите сваки пут. >> Да. И мораш да их замене. >> Иако ми људи смо некако свезнајућег у смислу визуелно да можемо некако види да је ово сортирају, рачунар није толико паметан. То ће изгледати овде и овде и овде, али ако оно што тражи јесте најмањи елемент, Ви само знате да сте нашли најмањи елемент по ком тренутку? Када сте на крају. Али, у том тренутку сте само нашли тренутно најмањи елемент. Не нужно знати нешто о стању у свету. Дакле, морате да идете опет и опет и опет. 

Дакле, овај пут сам стварно изгледају глупо, јер сам проверу, ок, 2, ти си најмања, али ја не знам да је укупно још. 3, 4, 5, 6, 7, 8. Добро, добро. 2 је заиста најмањи. Сада хајде да следећи најмањи. Ок. 3, ти си тренутно најмањи. Хајде да видимо. 4, 5, 6, 7, 8. Ок, имам среће поново. 3 је заиста на правом месту. Али ја ћу да наставим да радим ово опет и опет и опет. Како можемо учинити икада тако нешто боље? Уместо да људи испливати Појава удвојених од најмањег до највећег и уместо да иду напред и назад кроз листу избором онда најмањи лице, Зашто не бисмо уместо убацили ове људе у новој листи корак по корак? Хајде да пробамо ово. Сада пусти ме зову ову врсту ствар уметања. Дакле, овде смо овде. Број 1. Не занима ко други у овој листи. Мој циљ сада је да се стави број 1 на почетку сортиране листе. И ја ћу да предложим, јер ја имам само 8 комаде меморије, произвољно сада сам зид између моје наводно некласификовани листи, и свако ко је иза мене ја ћу да тврдим је сортиран. Дакле, сада имамо број 1. Желим да га убаците у свој сортирани списак, па ћу само да померим зид овде, и сада тврдим ова листа је сортирана, ова листа се унсортед - барем колико ја знам. Ја не могу да видим све бројеве одједном. 

Сада сам се десити да наиђете број 2. Шта да радим са њим? Ја убаците вас сада у сортиране листе. Али приметите како је лако је то било. Морам да погледам. Број 1 је тамо. О, очигледно 2 иде на страни број 1. Шта сад да радим са 3? Ја убаците вас у сортиране листе. Али то је супер лако. Ово је супер једноставан, ово је супер лако, ово је супер лако, супер лако, супер лако. А сада је све поређано иза мене, и колико корака се то трајати? [Студенти] Н. >> Дакле, то је само н. Имамо среће. То је био само н зашто? >> [Ученик] Зато је листа сортирана. Списак је већ сређено. Дакле, имамо среће. Али смо дизајнирали алгоритам овај пут да користи предности такве среће, да најбољи сценарио, што не троши непотребно време. Дакле, сада имамо шта ћемо назвати врсте Буббле где људи некако испливати Паирвисе. Ми сада имамо избор врста где смо извади најмањи особу поново и поново. И сада имамо уметања какву где смо некако проактивно ставити људе где им је и место у све сортиране листе. Ако смо могли, аплауз за ове момке овде. [Аплауз] Узмимо овде 5-минутни одмор. А када се вратимо, ми ћемо разнети све ове алгоритама из воде са нечим бољим. У реду. Хвала пуно. Можете задржати их као сувенире. У реду. Вратили смо се. 

И да поновимо веома брзо, ми смо имали те 3 различите приступе сортирање, поента која је доћи до тачке у којој неко попут Алек може претраживати списак бројева брже него некога као Шон могао. И иако имамо такве једноставне примере са 8 бројева, могли екстраполирати лако до 8 веб странице, 8 милијарди веб страница, или 800 милиона пријатеља на Фацебооку. Дакле, ови алгоритми свакако може скалирати на оне врсте вредности, и идеје су на крају исти. Дакле, балон некако био први где смо некако бубблед до највеће особу све до десне стране замене људе Појава удвојених. Онда смо имали шта ћемо назвати врсту селекције, где сам мало намерно Гледала кроз листе, изабрати најмањи број опет и опет и опет, логичан резултат тога је да је листа сортирана крају. Затим, у трећем, ја убаци људе у њихове одговарајуће место, и ми смо радили врло вештачки пример у томе да је списак већ сортиран, али то је да пошаље поруку да у случају Инсертион сорт а, можете добити среће. Ако су бројеви су већ сортиран, само ће вас одвести н кораке да потврди колико, а избор врсте си мало више тунел визије и ви никада не схватају да је списак већ сортирана. Па хајде да видимо какве мехур у акцији. У следећем примеру, ми смо о томе да видимо вертикалне линије чије висине представљају бројеве, тако да можемо некако визуелизовати сортирање десити. Што је мања бар, мањи број, већи је бар већи број. 

А ми ћемо га играти на овом дефаулт брзини. То ће да се креће мало брзо за сада, али црвени је оно што се показује 2 бара пореде раме уз раме. А ако пажљиво гледати, шта се дешава је да ако су барови су у реду, мањи једна бити померен улево, већи онај са десне стране, и онда држати напредују. Дакле, ако то урадимо поново и поново, приметићете да су најмање шипке ће да полако свој пут на лево и највеће шипке ће задржати свој пут полако са десне стране. И заиста, ми почињемо да видимо шаблон скроз на десној страни баш као што смо видели 8 и онда на крају бистрим 7 до далеког краја нашег људског листе. Дакле, ово ће врло брзо добити мало досадан, па ћу ово зауставити на тренутак. Дозволите ми да промените брзину да буде много брже. Ја не мења алгоритам, ја само правим анимације десити брже. Ипак балон врста, исто алгоритам, али сада можете видети много брже него што је наш вербални демонстрација да су највеће елементи су заиста бистрим до врха. 

Као на страну, ови мали тргови у доњем левом и доњем десном су само мали подсетници, као да колико поређења радиш. Али за сада, можемо се фокусирати на пирамиди да је узимање облик, и тамо иде. Најмањи елемент је на левој, највеће на десној, а све остало између. Сада ћемо, уместо да погледамо избор врсте. Идем да иде напред и ударио Стоп. Ми ћемо добити нови случајан скуп решетака. Избор врста, опозив, пролази кроз листу опет и опет и опет, чупање из најмањи елемент. Дакле, овде је избор врста. Изгледа као да је мање посла дешава сада, јер ми не поредећи Паирвисе али ми смо некако трешња брање најситније елементе из здесна налево. То је врло мало времена, па је већ ту дихотомију. Само зато што алгоритам се каже да н правоугаону време, као мехур врста и као избор врсте, оне су стварно најгори случај раде пута. На пример, у случају, рецимо, сортирање избор, Ја стварно сам изабрати најмањи особу и стављање њега или њу овде, онда то радим поново, онда сам то поново, али је мало оптимизације сам могао направити. 

Чим сам се преселио овде број 1 - Самми у том случају - шта треба да урадим са њим након тога? >> [Ученик] Остави га. Остави га, зар не? Ништа. Нисам имао потребе да икада разговарали са Семи поново, јер ако сам изабрао најмању елемент и ставио га овде, зашто губити време иде до краја мог целу листу? На следећој итерацији дозволите ми заправо крећу само до броја 2, само на број 3. Дакле, у стварности, нисам радила н ствари н пута. Ја сам радио н ствари, онда н - 1 ствари, онда н - 2 ствари, онда н - 3 ствари, затим н - 4, тачка, тачка, тачка. Имамо мало геометријског низа, што само значи ви се додаје постепено мањих бројева. Није н + н + н + н, али н + 7 + 6 + 5 + 4 + 3 + 2 + 1. И шта то уопште успева да буде - Идем да поквари моје плоче овде за само један тренутак - која ће разрадити да буде нешто попут н (н - 1) / 2 ако смо некако изгледа на полеђини књиге из математике, где имате све варања листове за формуле. Ако сте тек додајући нешто н + н - 1 + н - 2, ради се да се нешто овако. И ако ми некако умножавају ово, то је н квадрат минус н / 2. Наставио сам да говорим н квадрат, међутим, и то је зато што сам био некако узимања менталну пречицу јер у стварности, н квадрат минус н подељено са 2 је заиста прави број корака да алгоритам попут одабира врсте би предузети ако заиста пребројали свих тих поређења и све мало заузет радом смо радили. Али искрено, кад н добија се као милиона или милијарди, који врага брине ако радите милијарду квадрат минус милијарду подељених 2? Милијарди квадрат је огроман број. Можете узети још једну милијарду офф то са - н. То и није тако страшно. Дакле, већи бројеви се, мање важни ови нижи наредио термини. Кога брига ако поделите са 2, ако говоримо о куадриллионс од броја корака? 

Дакле, у целини, компјутерски научници настоје да баците све осим највећи рок, а ми смо некако поједноставити свет и кажу да је то алгоритам узео приближно н квадрат кораке. То је време рада алгоритма. Тако ћемо се вратити на то у само једном тренутку са неким конкретним примерима, али за сада, то је нека врста интуитивног мотивације иза само поједностављивање наш свет и говори о најважнијим условима него улазим свих ових фенси формуле. Дакле, то је био избор врста, а ми смо добили мало среће тамо. Погледајмо уметања врсте. Дозволите ми да иде напред и почети ово као добро. Сада приметите образац који се дешава је мало другачија, и ми смо почели са случајним бројевима, али ако ми заправо броји до броја корака у најгорем случају, Ако је листа почела потпуно у правом редоследу, само би предузети кораке да оствари н толико. 

Али ако листа заправо били уназад - на пример, у овом случају овде - онда приметили смо заиста да се уради много више посла у овом случају. И то би требало некако осећам да ти овако једна је врста радне теже да се оне мање елементе на лево, а то је зато што смо среће. Листа је случајно сортирана у рикверц. Насупрот томе, код убацивања врстом ако имитирају оно што смо урадили са нашим људима овде започевши са свима сортираног и онда почети, то је прилично добар алгоритам, зар не? Већ је, у ствари, сортирају. Дакле, хајде да покушамо да резимирамо тачно колико времена су ове ствари нам узимајући увођењем само мало жаргону или нотацију која је заправо много једноставније него фанцинесс врста сугерише. Ова ствар овде, ова велика О на екрану, оно што компјутерски научник ће генерално користе описати најгори могући време рада неког алгоритма. 

Опет, по најгорем случају, то је тотално контекста зависи. Оно што подразумевамо под најгорем случају потпуно варира у зависности од проблема смо говорили. Али у случају сортирања, што је најгори могући сценарио? Све је наопако, само зато што се осећа као да значи много посла за нас. Сам записао сам доле неколико алгоритама које смо видели до сада: линеарно претраживање, бинарна претрага као и са телефонског именика или комадића папира, онда балон сортирање, селекција некако, као и убацивање врста као што смо видели са нашим људима, и онда још 1 који је на крају ће да се зове обједињавање врсту. Дакле, у линеарном потрази у најгорем случају, колико корака је потребно да се пронађе број 7 ако постоје н врата попут Шона Суочени? >> [Ученик] Н. Н. Дакле, ми ћемо писати велики Ø н. Ја ћу само да попуните неке празнине. Ово је само мрежа од празнине. Али, у најбољем случају са линеарном претрагом, 7 можда била на самом почетку листе, и Шон можда почела да тражи на почетку листе. Дакле, ако користите линеарну претрагу и само проверавам лева на десно или можда с десна на лево - они еквивалент - у најбољем случају колико корака могао линеарно претрагу, као алгоритам Сеан, водите? Само 1 корак. 

Зато ћу да кажем да је то омега нотација. Ово је само капитал омега. Омега је само секси начин да се каже најбољи случај покренут време. Дакле, у најбољем случају ради време је један корак или исти број корака - 1 у овом случају - али у најгорем случају, велики О, то је заправо н корака. А ово овде, тета, ми заправо нећемо да погледамо сада. То није релевантно овом конкретном примеру. Али сада хајде да пробамо бинарну претрагу. У најгорем случају са бинарном претрагом, колико корака ће то потребно да се пронађе број 7 или шта тражимо? >> [Ученик] лог н. Ипак ћу узети н лог, јер баш као и Алекс добио среће када смо заиста радили кроз проблем методично а она није пронашли број 7 до последњег врата она гледали, иако, у праведности, она мора да баци неке врата на путу, бинарни претрага у најгорем случају има покренут време дневник н. И опет, то говори да ова подела и освајање. Али шта је у најбољем случају? И Алекс заиста доживели тај најбољем случају у праву када је дошао на сцени. Колико корака је да узме у бинарном претрагу? >> [Ученик] 1. 1, само зато што је имао среће. Али то је у реду, јер се односи на омега најбољих сценарија, најбољем случају улаза, чак и ако је то само случајни глупа срећа. 

Сада, ово је такође ћемо некако остави празно за сада. А сад мехур врста? У најгорем случају са мехурићима врсте, сви су у обрнутом редоследу, тако да морамо да урадимо много клокоће. Али колико корака је да ће узети у најгорем случају? >> [Ученик] Н квадрат. Ово је н квадрат, јер ако мислите о томе, Ако је листа потпуно уназад - 8 је овамо, 1 је овде - као што почну да мехура, број 8 је прећи на овај начин, на овај начин, овако, на овај начин, али где је број 7 у најгорем случају? Овде је још увек тамо. Дакле, морамо да то урадимо поново и поново. И то је где смо добили н корака, а затим н - 1 корака, а затим н - 2 корака. И ако узмете моју реч за то - да ако некако да га умножавају се, је отприлике то н квадрат на крају са неким другим појмовима који ћемо само игнорисати за сада - затим у најгорем случају врсти мехурићима је н квадрат, дати или узети. Али шта је у најбољем случају са мехурићима врсте? Који је најбољи сценарио? Сви бројеви су већ сортиране. А шта је хеуристички сам користио, трик сам користио, да схвати да сам ја учинио никакав посао и стога може зауставити рано? [Ученик] Долазак једном. >> Проверите једном. Али шта сам радио на том путу? Ја сам праћење колико свопови сам направио. И схватио сам да нисам бројао никакве свопови на мојим прстима, а онда сам урадио нема посла. Ја свакако не би требало да покушамо поново да урадим без посла, тако да могу да престанем. 

Дакле, у најбољем случају балон врсте, када је листа већ сортиран, Шта би сте рекли омега нотација је најбољи случај покренут време? То је само н. Морамо да урадимо неки посао, али ми само треба да урадите вреди 1 Прошетајте се од рада. И овде ћу оставити празно део. А сада нека селекција. Избор врста је моје черупање најмању особу поново и поново. А шта да кажемо вођењу време је то било? То је н квадрат у најгорем случају. И нажалост, у најбољем случају то је такође н квадрат јер ја немам неку врсту свезнајућег поглед целог света; Знам само на пуном итерацији да сам заиста пронашао најмању особу. Дакле, избор врста врста срање у том смислу, али наопако је да је некако интуитивно. То је прилично лако да кодира се јер све што треба да урадите је да напише неколико угнежђена за петље, обично, да пролази кроз потрази за најмањи елемент а затим ставља најмањи елемент где припада на крају листе. Дакле, и овде ће бити компромис. Износ времена је потребно да мисле и да се заиста развије нешто од писања кода могао врло добро бити потребно више времена ако желите бољи алгоритам и брже перформансе. 

Али ако стварно само нека врста кода нешто горе брзо и прљаво и некако узети најглупљи могући идеју можете да замислите, да би вам потребно неколико минута да се кодом, али са великим скуповима података Ваш алгоритам може потрајати сатима да ради. А чак сам на постдипломским студијама би понекад чине ове компромисе. Било би 3ам, покушавао сам да анализира неке веома велики скуп података у вези са безбедносном истраживању сам радио, а било је провести 5 минута прилагођавати свој програм за анализу података и идемо на спавање или провести 8 сати добија се само право, тако да тренутно ради и да не иду на спавање. И тако тамо је нека врста свесне одлуке. Мање време развоја, више сна. У ретроспективи, вероватно не би требало да подстакне да када је циљ је да се оптимизује квалитет кодекса, али и то у стварном свету је веома разуман компромис. Мање времена, мање перформансе или обрнуто. Дакле, овде смо најзад добили прилику да разговарају о тета. Тета нотација је нешто рачунарски научници могу довести у разговору када велики О и омега деси да буде иста. Кажете тета да заиста пошаље поруку да је то врста чврсто везан. Без обзира на то да ли је сценарио је добар или лош, то је н квадрат. Дакле, то једноставно није релевантно у овим причама овде. Инсертион сорт је последњи који смо гледали, где сам био убацивања све на правом месту. У најбољем случају оно што је био покренут време убацивања врсте као што смо то видели овде? [Ученик] најбољем случају? >> Најбољи случај. 

Године н је зато што у најбољем случају свако сортирају, и Семи и нико други заиста морали да крећу на све. Они су већ били у њиховом правом месту. Тако некако убацивање у најбољем случају, у овом случају, н. Али, у најгорем случају то је некако н квадрат. Зашто? Ако мој списак људи је у обрнутом редоследу, Прво почети са бројем 8, а ја сам га убаците, или јој на правом месту, што је управо овде. Некако потез на страни. Ови момци су несортиран, он или она се сортирају. Али сада сам се десити да пронађе ко следећи? >> [Ученик] 7. 7 у најгорем случају, јер је то у обрнутом редоследу. 

Дакле, овде је 7. Одакле 7 припада? Дефинитивно иза мене. Али сада 7 заправо не припада одмах иза мене, али иза броја 8, па морам да кажем, "Извините, број 8, молим вас да померите на овај начин "Да би се направио простор за 7?" Сада сам сусрет 6. "Ох, извините, број 8 и број 7, можете преместити како би направили места за 6?" Другим речима, са убацивања врсте, иако ја не радим много покрета, људи иза мене раде много више рада, а то мора да кошта времена некога. То ће коштати време рачунара. Дакле, у случају убацивања врсте још увек пате. Ако почнете додавањем укупан број корака, завршавамо ударање грубо н квадрат јер ови момци треба да би се направио простор за људски да се убаци назад у тој листи. И тако се у овом случају тета једноставно није примењиво на одређену причу у руци. То је све лепо и добро. Ми имамо ове 3 различите начине говоре о трајању. Али шта то заправо значи у реалним условима, ако смо заиста покушавамо да кодирају се алгоритам? 

Дозволите ми предлажемо да постоји још бољи алгоритам тамо који сам по себи има неку компромисе. Идемо да га зову обједињавање врсте, и то је некако ове магичне алгоритма то само ради брже, некако, и то је тако лако да изрази, бар у Псеудокод. Спровођење ове врсте алгоритма стапања ће бити као што следи. Када сте дали н елемената - н бројева, Н људе, без обзира - прво ту је разум чек. Ако је н мање од 2, споји некако само зауставља. Она се враћа, да тако кажем. Зашто би зауставити ако је н мање од 2? >> [Нечујан ученик одговор] Тачно. И опет, н није број у листи, н је величина листе. Ако је н мање од 2, то значи да је Ваша листа или 1, где сте очигледно сортирају ако је 1 број, или 0, у ком случају нема ништа да сортирате, тако да морамо ту врсту основном случају. Ако је листа тако кратка да само ту ништа да урадим, буквално не ради ништа. Повратак. Иначе сортирати леву половину елемената, а затим сортирати десној половини елемената, затим се стапа 2 сортиране половине. 

Ова врста изгледа као мало варају где ја вас питам како да сортирате елементе а ви ми кажете, "Сортирање леву половину, сортирати десној половини." Ја сам као, "У реду Како сортирати левој половини.?" "Сортирање леву половину левој половини, сортирати десну половину леве половине, а онда урадити." Ти си некако циклично дефинише шта то значи да сортирате, али се испоставило да је то заиста сјајна у овом случају. То није стварно ово зачарани круг који се никад не завршава јер не завршава када? >> [Ученик] Када стигнете 1 ствар. Када стигнете до 1 ствар. Дакле, иако можда почети са 8 особа, а ја кажем, "Сортирање леву половину тих људи, ова 4 људи ", онда кажем:" Како сортирати левој половини? " "Па, сортирати овде 2 особе." И онда сте као, "У реду, у реду." "Како сортирати леву половину тих људи?" "Само сортирали ово овде 1 особу." Шта је бриљантна откриће сада? Морам да сортирате 1 особу. Готово. Не морам да радим било који посао. Али сада морам да сортирате ову особу, али они су једна особа, ништа да уради. 

Дакле, магија очигледно је у овом трећем кораку: обједините сортиране половине. Дакле споји некако узима овај сјајан увид да ако пробије велики проблем доле у 2 мање, идентично величине проблема и онда само нека врста лепка заједно су мање решења на крају, Ја предлажем да можемо учинити много, много боље [тапкања звук] него било који од избора врсте или уметања раси. Ја стварно нисам игнорисала да за пола сата, али ја стварно не знам шта се дешава напољу данас. [Зујање звук] [смех] Дакле, хајде да видимо да ли можемо да видимо, уз малу помоћ пријатеља из наше Роб Бовден. Постоје 2 велике кораке у процесу стапања врсте. Прво, стално поделити листу куповима у пола док имамо гомилу листа са само 1 шоља у њима. Не брините ако листа садржи непаран број и не може да направи савршено чист рез између њих. Само произвољно одабрати која листа да укључи додатну шољу унутра Дакле, хајде да поделите ове листе. Сада имамо 2 листа. Сада имамо 4 листа. Сада имамо 8 листе са једним купу у свакој листи. Дакле, то је то за корак 1. За корак смо у више наврата 2 обједињавање пара листа помоћу стапања алгоритам смо научили раније. Спајање 108 и 15 ми завршити са листе 15, 108. Спајање 50 и 4 ми завршити са 4, 50. Спајање 8 и 42 завршимо са 8, 42. И спајањем 23 и 16 ми завршити са 16, 23. Сада сви наши спискови су величине 2. Приметите да сваки од 4 листа је сортирана, тако да можемо да почнемо поново спајање парова листама. Спајање 15 и 108 и 4 и 50 прво узети 4, онда је 15, затим 50, затим 108. Спајање 8, 42 и 16, 23 смо први узме 8, затим 16, затим 23, затим 42. Дакле, сада имамо само 2 листе величине 4, од којих је сваки сортирају. Дакле, сада смо споји ове 2 листе. Прво узмемо 4, онда узми 8, онда узмемо 15 и 16 и 23 и 42 и 50 и 108. И ми смо урадили. Ми сада имамо сортиран списак. 

Роб је некако искористи за нешто што још нисмо урадили. Предложено је, али нисмо стварно то урадио. Он је радио нешто физички са шоље које сугерише Он је трошио мало ресурс поред времена. >> [Ученик] Простор. >> То је био простор. Чињеница да је он имао ту врсту ла нивоа стола, где је имао простор овде и простор овде је заправо подразумева да он користи два пута онолико простора као и било који од наших алгоритама до сада - убацивање врста, балон сортирање, или избор врста - али је усклађивање ове додатне простор врсте покренути ствари напред и назад задржавајући ствари у ред. И иако се осећа као да смо на сортиране листе, која је звучала као да је мало. У стварности, оно што Роб је радио био је управо овај алгоритам. Он је прво узео проблем величине н, подељена је у левој половини и десна половина. То је када се преселио у чаше. Онда је поновио тај процес. Он је подељен на 4 2 сета 2 овамо и овде. Онда је поновио тај процес и подељен 2 у 2 сета 1 за сваку од тих разних пехара. И то је место где бриљантна укаже прилика. У том тренутку у причи, Роб је имао 8 листе величине 1, сви који су већ сортиране. 

Па шта онда је он настави да уради? Паирвисе узео ову сортирани списак и ову сортирана листа и спојио их. Онда је узео овај један и спојио их, онда овај један и спојио их, онда је ово један и да их споје. И онда шта је следеће? Затим је поново спојио веће листе, а затим поново спојио веће листе. А ако мислите о томе само интуитивно за сада, шта је он заправо ради? Он је дељењем проблем на пола, у половини, у половини, у пола како би се ове супер мале листе. Онда је била нека врста комбиновања дупли, дупли, дупло, дупло. Дакле, он је два пута радио онолико рада, као што смо видели до сада са чим укључује завади па владај, али ништа страшно. Дупло рад није таква велика ствар. То је само стални фактор. И слично нашем аритметичког израза пре, ја ћу само да пређе из сталне факторе као доба 2. Кога је брига? Ако је 2 милијарде пута 2, то је још увек много корака. Дакле, ово спајање корак чини се да је кључни увид. Прошетајмо кроз ово само бројчано пре - Ох, то је да не буде увек наставља. Прошетајмо кроз ово бројно само да виде како се то одиграва. Ово је углавном само мало сиромашан човек је анимација. Хајде да предложи ово. Вођењу време стапања врсте - само треба начин говори о томе. Ово није математика, то је само нека врста сажетом начину изражавања себе. Дакле, Т представља време и н представља шта? >> [Ученик] Величина од - 

[Малан] Величина проблема, број људи. Дакле, ја тврдим да је покренут време да сортирате н људи ће бити 0 количина времена ако је н мање од 2, јер ако имате 1 шољу или не купа, немате шта да сортирате. Али генерално, ја ћу предложити да ради време да сортирате н елемената ће бити време које је потребно да сортирате леву половину плус десна половина плус - шта је ово додатни + н? >> [Ученик] Обједињавање врста. [Малан] То заправо је спајање, јер ако имате н / 2 елемената овде и имате н / 2 елемената овде, колико времена је потребно да их објединим? Баш као Роб, морате да уберу овај овде, можда ишчупати овамо, ископај овде, ископај овде, ископај овде. Морате да дотакне сваки чаша једном. И ако постоји 4 шоље плус 4 шоље, то је 8 чаша или, уопштеније, 8 н шоље. Дакле, спајањем корак можемо да изразимо као н, и да буквално подразумева број пута Роб физички додирнуо један од оних стиропора пехара. Па хајде сада да радимо произвољан пример. Ако има 16 чаше, шта раде време сортирање, користећи Робов алгоритам, 16 чаша? То је 2 пута количина времена које је потребно да сортирате 8 шоље јер овде имамо 8 шоље, чаше 8 овде. Ја не знам колико дуго да траје, па смо га уопштавања као Т за тренутак. Ко зна шта је то? Али сада могу некако рекурзивно или више пута поставим исто питање. Колико времена је потребно да сортирате 8 шоље? 8 шоље ћу да кажем узима количину времена које је потребно да сортирате 4 шоље плус 4 чаше, затим их спајају заједно. Добро. Ми улазимо у циклус већ. Колико времена је потребно да сортирате 4 шоље? Време које је потребно да сортирате 4 шољице је 2 шоље плус 2 шоље сортирање плус спајање процеса. Добро. Колико времена је потребно да сортирате 2 шоље? 2 шоље је количина времена које је потребно да сортирате 1 шољу, плус време које је потребно да сортирате једну шољу плус износ времена је потребно да се споје, што је само 2. 

Добро. Последње питање. Колико времена је потребно да сортирате 1 шољу? Овде је основни случај који смо предвидели да ћемо ударити раније. Чињеница да је потребно без посла уопште да сортирате најмања проблема значи да је сада, на неки начин разреда школе стила, можемо само да идемо почети прикључивање ове бројеве бацк ин Ми сада знамо шта Т од 1 је, тако да могу прикључити 0 за т 1. То ће ми дати одговор на Т од 2, коју сам тада можете прикључити вишем. То ће ми дати т 4, који могу попунити у вишем. То ће ми дати т 8, који могу попунити у вишем. И ако сам у ствари раде из тог математику прикључивањем у овим одговорима, И онда се т 16 је 64. А шта 64 представља? Ако Т ​​је 16, да, то је 16 пута 4. Дакле, ја тврдим да је сада време рада ове ствари зове обједињавање врсту - и то ће бити фанциест од оних које смо видели до сада - ће се звати н лог н јер колико пута могу поделити Роб гомилу чаше на пола? Лог н. То је исто као пример телефонског именика, то је исто као и само-бројање пример. 

Колико пута можете поделити нешто на пола? Међутим, ту је ово спајање корак. Можда ћете морати да поделе пехаре на полувремену опет и опет и опет, али сваки пут када ћеш морати да се споје. И ми смо раније рекли да је спајање н шоље потребно н корака јер морате да извади шољу, извади чашу, и морате да једном додирнути сваки пехар, баш као Роб урадио. Дакле, ако радимо нешто лог н пута и радимо н ствари на сваком од тих итерација, сваки од тих халвингс, имамо н пута лог н. Дакле, ако укључите у 16 ​​у овом примеру, 16 пута улогујете од 16 - Не брините о томе зашто је то тако, за сада, јер нисам сам нацртана базу - али дневник основом 2 од 16 је 4, 16 пута 4 је 64. Али са друге стране, ако смо користили балон врсте или избор сортирања или уметања сортирање са 16 бројева, шта би се приказују време су били да је н 16? Било би 16 квадрата, што је 256, што чак и ако нисте сасвим пратили све математику, 256 је већи од 64. То је заиста магична ПОНЕТИ овде. И схватите да раде кроз ово у мањим примерима, као што ће у псет чини све много више интуитивно. Али шта то заиста значи у погледу осећају овог алгоритма је ово: Ако смо заиста погледамо стапања сортирај овде - дозволите ми да га повуку у овом прозору овде - ово је мало другачији пример где имамо све 3 од ових алгоритама - мехур, селекција и обједињавање - само једни поред других. 

Сви су они почели са случајним решетака, и то је добро. Нико нема основна предност над другим. Идем у тренутку кликните на сваку од ових анимација - Старт Старт Старт - најбрже што могу, тако да, отприлике, све почетак у исто време, и размотримо која гори случај Буббле сорт је покренут време је шта? >> [Ученик] Н квадрат. Н квадрат. Најгори случај Изборне Сортирај је покренут време је? Н квадрат. И обједињавање врста је очигледно - чак и ако нисте сасвим пратимо све математику сада, то ће бити много више интуитивно током времена - јесте, ми тврдимо, н пута лог н. И зато лог н је строго мање од н једном имамо велике бројеве, н пута лог н је мањи од н пута н или н квадрат. Дакле, шта је то осећај заправо бити бољи алгоритам у смислу истеклог времена, н пута лог н насупрот н квадрат? Идемо. Клик, клик, клик. 

То је оно што значи да користите нешто попут стапања врсте. Имамо тренутак. Хајде да видимо шта се дешава овде. [Цхуцклес] Чији новац је на мехур врсте? То је пре зависи од улаза понекад. Хајде да видимо. Хајде. То се осећа као да је сустиже. >> [Ученик] Иди, сортирање балон! [Студенти мрмља] [Малан] Да, да. [Студенти мрмља] Иди, иди, иди! [Сви навијају] [аплауз] Дакле, сада са 1 последњег, коначног демо, ако је то мало незгодно да заврши свој ум око математике или нека врста визуализације тамо, ви у ствари можете чути брзине различитих алгоритама другачије. Ово је анимација је неко направио да заправо сарадници звучи са процесом замене и висине од барова. Као што ћете видети, постоји још неколико алгоритама за сортирање тамо да људи су мислили. Ова прва ће бити уметање врста, а то ће летети преко и дати вам чујни осећај како ови разних рада алгоритама. Овде је убацивање врста. [Електронски беепинг] [Малан] Буббле сорт. [Брже електронски беепинг] [Малан] Избор врста. [Брже електронски беепинг] [Малан] Обједињавање врста. [Електронски беепинг] [Бееп успорава] [смех] [Малан] Гноме врста. [Електронски беепинг] 

Ово је ЦС50. Видимо следеће недеље. [Аплауз и навијање] 

[ЦС50.ТВ]