[Музика свира] 

Давид Ј. Малан: У реду. Дакле, добродошли назад. То је ЦС50, а није крај три недеље. 

Тако се сећате у последњих неколико недеља, смо проводи доста Време на Ц, на програмирање, на синтакси. И то је сасвим нормално, ако си и даље бори са проблемом Сет 2, да буде лупа главом о зид. То је криптичан изгледају поруке о грешци и бубе које не могу да стигнем. Зато, будите уверени, да је само у време неколико недеља ћете осврнем на ствари као Цезара, и [? В-генаир,]? можда чак Црацк, и схватити колико далеко сте дошли у кратком временском периоду. Дакле, ако је то нека утеха, Дрзи се за сада. 

Данас, међутим, ми смо почели да транзиција у ствари виши ниво. И почнемо да узимамо здраво за готово да је ви знате како да програмирате, или на Цене су почеци да ниво удобности. И ми ћемо почети да се размотри како можемо се о дизајнирању програма више ефикасно. Како можемо да идемо о оптимизацији Ефикасност наших алгоритама, а генерално решавање више интересантне проблеме. И почиње да се узима здраво за готово да је, ако бисмо желели да, можемо да се било који кодирају од примера имамо у виду. Тако данас, ми не додирнете тастатуру за било који облик кода. То ће бити много виши ниво, а на крају, о решавању проблема. 

Тако да се у том тренутку, да предложи да у наредних седам правоугаоници представљају седам врата, иза које су гомила бројева, међу којима је број 50. Дозволите ми да напустим ово на ово екран и овде. И предлажу да ми треба добровољац за помогну у проналажењу ми броја испред Интернет овде да видите. Дођи горе, у розе. У реду. Како се зовеш? 

ЈЕННИФЕР: [ИНАУДИБЛЕ] 

Давид Ј. Малан: Молим? 

ЈЕННИФЕР: Џенифер. 

Давид Ј. Малан: Џенифер. У реду, Џенифер. Драго ми је што смо се упознали. Хајде горе. Дакле, ово овде су седам врата, а шта Волео бих да радим за нас овде, пред свим својим друговима, се налазимо, број 50. Да бисте пронашли број, можете да провире било који од ових врата једноставним додиром на једној од врата, и ће открити свој број. И хајде да видимо колико брзо да нас нађете број 50,. 

15. 16. 50. Лепо урађено. У реду. Аплауз за Џенифер. 

[Апплаусе] 

У реду. Дакле, шта је Ваша стратегија за проналажење броја, 50? 

ЈЕННИФЕР: Хм, ако сам мислио - [ИНАУДИБЛЕ] 

Давид Ј. Малан: О. Дајте јој један секунд. Да ли је твој стратегија проналажење броја, 50? 

ЈЕННИФЕР: Тако да сам се крећу од почиње да се види шта је први број је, а онда сам помислио, можда ако они сортирани, ја ћу држати прислушкивање вишље? 

Давид Ј. Малан: У реду. А изгледа да смо нашли да је то случај. Мада, хајде да одлепите слојева само мало, а желите да одете напред и открије друге врата могли сте изабрали? 

ЈЕННИФЕР: О, драга. 

Давид Ј. Малан: Ах. 

ЈЕННИФЕР: Па управо сам среће. 

Давид Ј. Малан: Па ти се посрећило. У реду. Зато није лоше. Али, то је занимљиво увид, зар не? Ако сте претпоставили, а ви се, заиста, мало среће тамо. Али, ако се претпоставља да су цифре сортирају, могу ли бити прецизнији како је то утицало ваше понашање? 

ЈЕННИФЕР: Дакле, ако су били поредани, ја Мислио сам најмањег до највећег. 

Давид Ј. Малан: У реду. 

ЈЕННИФЕР: Или ако је ово заврсило се заиста велики, онда највећи до најмањег. 

Давид Ј. Малан: У реду. Дакле, највећи до најмањег, или најмањег до највећег. Али, дозволите ми да предложи, претпостављам да је стечен среће, а претпостављам да су они нису, у ствари, сортирају, колико та врата можда сте морали да вирим иза у том најгорем слуцају? 

ЈЕННИФЕР: Сви они. 

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

ЈЕННИФЕР: Да. 

Давид Ј. Малан: Па, да видим да ли ваш Стратегија промене ако пређем на нас Наш други пример овде са 7 различитих врата. Исти бројеви, али ово време они су сортирани. Која је ваша стратегија овде бити, покушава да стави ван памети што остали бројеви су били - 

ЈЕННИФЕР: У реду. 

Давид Ј. Малан: - раније? 

ЈЕННИФЕР: Почнимо са првом. 

Давид Ј. Малан: У реду. Почните са првом. 4.. А где ћеш да идеш, и зашто? 

ЈЕННИФЕР: 4 заиста мали. Дакле, ако су врста можда најмањи до највеће, што би требало бити два пута већа, и -. 

Давид Ј. Малан: У реду. Да видимо, што ти мислиш? 

ЈЕННИФЕР: Покушајте последњи. Лепо. 

Давид Ј. Малан: Веома лепо урађено. У реду. 

[Апплаусе] 

Давид Ј. Малан: У реду. Дакле, ви у ствари радите ово страшно, јер си то раде веома добро. Што оставља неспособним да извршити одређене тачке. Дакле, хајде да покушамо да се врати овде. 

ЈЕННИФЕР: У реду. 

Давид Ј. Малан: Веома добро урађено, ипак. Тако сте почели на почетку, видели сте да је 4, онда помера за крај. Али, претпостављам да ниси посрећи тамо, и претпостављам 50 био негде другде. Шта ваш Трећи корак био? 

ЈЕННИФЕР: Вратите се на почетак. 

Давид Ј. Малан: Врати на почетак. У реду, тако да би сте дотакли ова врата, што је 8. У реду. Дакле, то није 50. Где би сте гледали следећи? 

ЈЕННИФЕР: Да нисам Знам да сортирају. 

Давид Ј. Малан: Тачно. Па, ако си знао они су сортирани - 

ЈЕННИФЕР: О, нисам знао, да. 

Давид Ј. Малан: - али ви не Знам где је 50 било још? 

ЈЕННИФЕР: Само настави. 

Давид Ј. Малан: У реду. ОК. Настави. У реду, да ја могу да радим са. 

ЈЕННИФЕР: У реду. 

Давид Ј. Малан: Сада, ако сте само ће да иде, шта је твој алгоритам подршку у преношењу. 

ЈЕННИФЕР: линеарна -. 

Давид Ј. Малан: То је некако линеарно. Али, дозволите ми да предложи, да ме на лицу места. Дозволите ми да освежите страницу. исти број, исти аранжман, Исти врата. Али сетите се да тог првог дана у класа када поцепао телефонски именик у пола, некако, и оно што је било Наша стратегија тамо? 

ЈЕННИФЕР: Почните у средини. 

Давид Ј. Малан: У реду. Дакле, почните на средини. Дакле, идемо напред и да симулира. Почните у средини откривајући та врата. Дакле, број 16. Дакле, шта би јак момак урадио, који је поцепао телефонског именика на пола, да се до следећег нагађања? 

ЈЕННИФЕР: Идите у овој половини. 

Давид Ј. Малан: А зашто у десно? 

ЈЕННИФЕР: Ако су некако најмање до највеће, онда би требало да буде 50 у том крају. 

Давид Ј. Малан: Добро. Потпуно разумно. Дакле, као телефонски именик, идете на право за разлику од леве стране, али овде је кључ за понети. Сада можете бацити, или отцепи, половина овог проблема, те не оставља са 7 врата, али стварно са само 3. Што је отприлике половина Величина проблема. У реду. Дакле, сада оно што би урадити након десно? 

ЈЕННИФЕР: Дакле, 16 је и даље веома мали, у односу на 50, па можда ћу пробати, као што је, овај. 

Давид Ј. Малан: У реду. 42. У реду, па сад шта је твој инстинкт ти? 

ЈЕННИФЕР: Ја могу да бацим то и онда само - 

Давид Ј. Малан: У реду. Добро, можете да баците Лева половина тамо. 

ЈЕННИФЕР: - изаберите ово. 

Давид Ј. Малан: И у праву. 

ЈЕННИФЕР: Да. 

Давид Ј. Малан: Дакле, иако је то тешко можда да види, само кад постоји 7 врата, размислите, сада, конзистентност алгоритам само применити. У претходном случају, јеси посрећи, што је сјајно. Али сте користили хеуристички, Ја бих рекао. Можете користити врсту своје инстинкте, и знајући то сам средио, ако је лепа мала у почетку, наравно, ми смо Морам да идем више у десно. Али, у извесном смислу, имаш среће, Можда је то зато што је број 100, а можда и 50 био више у средини. 50 Можда је чак овамо. 

Али, оно што си урадио мало другачије овај пут је било, ти урадио исту ствар изнова и изнова. И ја бих рекла да је оно што сте управо је, иако под утицајем телефона Књига пример, нешто много више алгоритамски, и много мање посебан покриваннуу. Много мање инстинктивна. Дакле, на крају дана, како би описујете ефикасност Први алгоритам, где сте отишли лева на десно, у односу Други алгоритам овде? 

ЈЕННИФЕР: ово би требало, као, можда преполовити време, или чак и више, да. 

Давид Ј. Малан: У реду, можда чак и више. Хајде да се мало јаче притиснути на то. Шта заиста, ако наставимо ово логика, ми смо дефинитивно преполовљен трчање време са овом другом алгоритма бацањем даље половину бројеве, али шта смо радили на следећи итерација, када је Џенифер открио други број? 

Ми преполовио поново бројеве врата. И шта смо урадили после тога, ако било више врата да се игра са? Ми би их преполовити, и опет, и опет, и опет. А то је било баш као и ви сви стоји горе у првој недељи класа, половина ли седиш, половина од ви седите, половина вас седе, док један усамљени душа је стајао. А ми смо рекли да време ради да, број корака Било је потребно по налогу чега? 

СПИКЕР 1: [ИНАУДИБЛЕ] 

Давид Ј. Малан: Па дневник база од 2 н, или једноставно само више, пријавите се за н. Тако нешто логаритамске. И граф није права линија да управо сам горе и горе, било је ово интересантно да није крива толико лоше током времена. Па хајде да држите на ову идеју. Хајде да се захвалим Џенифер. Хвала много за долазак на горе. И, један сек. Нема лампе деск данас, али ми немате ЦС50 стрес лоптице. 

ЈЕННИФЕР: Ура. 

Давид Ј. Малан: У реду, овде. Хвала вам за настајање стрес овде. У реду. Па да видимо да ли можемо сада не формализовати то мало. Па опет, шта смо урадили је у суштини иста ствар као и ми у првој недељи. Али, уместо да крај са само линеарно алгоритам, који се приказао као раније ове правој линији, при чему, ако ставимо једну на врата екран, онда би Џенифер су морали да изгледају, потенцијално, иза врата још једном. Ако ставимо још два врата, она може имати погледати иза два врата. 

И тако, било је то линеарно однос између величине проблем на, рецимо, к-осе, и количина времена које је потребно да решити на и. Али слика коју је алудирајући раније је то зелена линија. Зелена намерно, јер то је само осећао боље. У теорији, алгоритам, када смо то урадили у телефонском именику, када смо то урадили са бројањем ви једни друге, и у другом случају, када је Џенифер само да ли је овде, то је на неки фундаментално боље. Зато што то није био само два пута брже. Није било чак четири пута брже. То је у потпуности зависи од тога шта величина улаза је, о томе колико је кораке које је на крају узео. 

И тако ова једноставна идеја да смо сви узели за готово у телефонском именику, Слично се може применити на овако нешто. И ово може да буде више узгред познат као, као што сте могли замислите, завади па владај. Не личи на оно што смо урадили, наравно, у телефонском именику. 

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

Али у овом случају, Џенифер сами могу фундаментално побољшање на извођење њеног првог алгоритма по, опет, само мислим мало теже. И сада, када дође време за спровођење ове ствари, фигуринг шта линија кода можете да напишете што су да можете да их поновите, и опет, и опет, на неки начин у лоопинг начин. Зато што нећеш имати луксуз, као што је Џенифер је у почетку, да се Само имам гомилу ИФС и рећи, Хмм, ако је ово први број је 4, дозволите ми да скочи све до краја. Оох, ако тај број је превелика, да пређемо произвољно назад до другог елемента. Видећете да ће то бити много теже да се формализује оно што ми људи узимају здраво за готово, као врло разумна хеуристике, али компјутер је само урадити оно што не кажете да уради. 

Сада ово је веома интересантно импликације. Овај граф је врста значило да некако затрпати визуелно, али обавештење, где је права линија у овом графикону? Где је линеарни граф да зовемо н? Па, то је нека врста према дну ове слике, зар не? Дакле, све што смо урадили јесте да смо на неки начин умањен за к-осе и И-оса да покуша да добије осећај шта друге врсте кривих изгледа. 

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

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

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

У реду. Дакле Јенниферин успех у тој секунди алгоритам, искрено, она је невероватно и први пут, али да пише како је среће да смо може да ову тачку. У другом случају, она је искористио алгоритам који понавља опет и поново, али она је за готово сигурно претпоставка да смо дозволили њу, али она је експлоатисана неке детаље други пут да она није имала први пут. А то је? 

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

Претпоставимо да си имала сирове податке сет и да је остало да се вама, или да Џенифер да то сређивање? То је, уместо тога, захтева да ми одговорите питање, па, колико времена би узели Џенифер, или чак да, за сортирање те бројеве унапред тако да је она могла искористити то? Зар не? Јер импликација, наравно, није ако ми треба доста времена да сортирате бројеви, који се сад стало да вас можете наћи број као 50 тако брзо, као у Јенниферин случају, ако се више од преплављени количину укупног времена то је тако сортирање ствари унапред? 

Па да видимо, ако не можемо бојите овде слику. Имам гомилу више стреса кугле, ако то помаже пробије лед овде. А ако немате ништа против, ми смо Треба седам добровољац - , ОК. Вау. Тако да не морате да потрошите на стоне лампе, изгледа. У реду. Па како ти двоје испред. Како би било да двојица позади. Дакле, то је четири. Како би било да пред пет, шест и седам. Тамо. Ваш пријатељ те истичући, тако да добијете награду. 

У реду. Хајде горе. И зашто не бисмо ли Додјите овамо. Ја ћу да вам дам сваки број. И само напред и организује себе идентично ономе што је приказан на екрану. 

[Изнео ВОИЦЕС] 

Давид Ј. Малан: ООП, извини. Буг. У реду. Па, идемо. Број пет. Број шест. Један, два, три, четири, пет, шест, седам. Ох, ово је непријатно. 

СПИКЕР 2: Само да узмем -. 

Давид Ј. Малан: Добар посао. У реду. Хвала вам на учешћу. 

[Апплаусе] 

ОК. У реду. Дакле, имамо четири, два, шест, један, три, седам, пет. Савршена тако да имамо седам волонтера овде који су једнаки у ширини до низа да играмо са раније. И ја сам изабрао седам разлога то ће бити само погодан за мало. И ја ћу предложити да прво можемо сложити седам волонтера. Ако желите, прво, да те поздравим ипак. Пошто ће ово бити незгодна неколико минута. Представите се. 

ГРАЦЕ: Здраво, ја сам Грејс. Ја сам студент друге године у Дому Леверетт. 

Брансон: Здраво. Ја сам Брансон. Ја сам бруцош у вара. 

Габе: Здраво. Ја сам Гејб. Ја сам млађи у Кабот. 

СКАНДАЛ: Ја сам Нил. Ја сам бруцош у Маттхевс. 

Јасон: Ја сам Јасон. Ја сам бруцош у Грееноугх. 

МИКЕ: Ја сам Мике. Ја сам бруцош у Граис. 

Јесс: Ја сам Џес. Ја сам студент друге у Леверетт. 

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

ОК. Добро. То је заиста проклето брзо. Сада је неко овде, шта је алгоритам да ови момци примењује? 

СПИКЕР 1: најмање до највеће. 

Давид Ј. Малан: У реду. Најмање да је највећи заиста некако објективан, али нисам сигуран да је то Стварно алгоритам. Најмање се највећи не говори ми корак по корак шта да радим. Да? 

СПИКЕР 1: [ИНАУДИБЛЕ] 

Давид Ј. Малан: У реду. Дакле, ако видите лице мањи од ваш број, а затим прећи на право на њих. Тако да је сада све израженије, више као алгоритма, јер сте могу да кажем, ако је то, онда да. Дакле, имамо неку врсту условни конструкт. А ови момци изгледа да се то уради неколико времена, јер неки од вас преселили мало из даљине. Тако да је вероватно нека врста лоопинг дешава у њиховим главама. 

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

Дакле, вас двојица су и два четири. Или сте тачно или нетачно како? Очигледно нетачна. Тако смо се заменили. Сада ћу да се креће у страну овде и кажем, четири до шест. Да ли сте тачно или нетачно? 

Габе: Тачно. 

Давид Ј. Малан: Тачно. Шест и један? Јок. Свап. Дакле, то су два свопови. Шест и три? Јок. Свап. Шест и седам? Изгледа добро. Седам и пет? 

Јесс: [ИНАУДИБЛЕ] 

Давид Ј. Малан: У реду, замените. И сортирају. У реду. Очигледно не, зар не? Дакле, било је више дешава. Али, заиста, ови момци, чак баш инстинктивно. стално креће. Нису само зауставити, када су исправио један проблем. Тако. Заиста, ја ћу имати да уради исту ствар. Ја ћу морати да некако премотавање леђа до почетка овог проблема, или почетак овог низа људи, хајде да почнемо да их зове. 

И шта сада треба мој алгоритам на другом пролазу бити? 

СПИКЕР 1: Иста ствар. 

Давид Ј. Малан: Иста ствар. И ово, ја почињем да се свиђа, зар не? Чим можете да нађете раде иста ствар изнова и изнова, то је све више као алгоритма, а мање људски инстинкт. 

Дакле, сада, ево нас опет. Два и четири? Не. Четири и један? Ах, заиста је било неких ради тога да се уради. За и три? Добро. Четири и шест? Шест и пет? Шест и седам? У реду, сада, урађено. ОК, нема. Морам да се вратим. 

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

Два и један. Два и три. Три и четири. Четири и пет. Пет и шест. Шест и седам. Готово? И ја сам, али дозволите ми да играм ђавољег адвоката. Да ли ми, врста рачунара који само направио пролаз кроз овај низ људи, знам да сам урадио? 

СПИКЕР 1: Не. 

Давид Ј. Малан: Зашто? Оно што бих ја морао да урадим да би децидно закључити да сам урадио? Вероватно још један пролаз. Зар не? Јер ја знам да од претходна центаршут је да сам исправио грешку. А то значи, можда постоји још један грешка да треба да се исправи. Тако да можете бити сигурни само по премотавања, и онда проверу, један до два, два и три, три и четири, четири и пет, пет и шест, шест и седам. У реду, сада сам без посла. 

Свакако могу да се сетим да сам не ради са нечим као променљиве, као инт. Назовите то свопови, а ако је свопови 0 Једном сам Овде се, а она је почела на 0, онда Само би било глупо да наставим и назад, проверу поново, и опет, и опет, зар не? Зато што се заглави у неким врсту бесконачне петље. Дакле, чим има 0 свопови, можемо тврдити да је ово алгоритам је заиста потпун. 

Сада, хајде да стави име на то. Алгоритам који сам предлажемо управо спроводи се нешто што се зове Буббле врста, као што је познато, у смислу да бројеви који су већи врста Буббле свој пут до врха, или се до краја низа бројева. Али како је ово ефикасан алгоритам? Колико корака сам физички да Узмимо, на пример, да се сложити седам људи? 

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

Сада, колико корака сам морао да се, када сам поново ранити? Па, ми смо у ствари могао да се удвостручи уколико то ми смо заиста желели да, али за сада, ја сам Само ћу рећи, у реду, још један минус 1 н. Тако Н минус 1 ће добити непријатно да пратите, па хајде да само око навише. Дакле 2н корака. Дакле 14 корака, узми или остави. 

Колико пута сам узети корак следећи пут? Па, то је 3н. стварно. А сада, у најгорем случају, за пример, колико пута ћу морати отишао напред и назад, напред и назад, реализацији овог алгоритма, замене људи на сваком пролазу, отприлике? То је у ствари н на квадрат, зар не? 

Зато што у најгорем случају, можете да некако од мисли о овоме интуитивно, иако можда ће бити потребно мало мало времена да тоне унутра У најгорем случају, шта би ови седам људи је изгледало, у услови споразума њиховог броја? Потпуно уназад, зар не? И само да симулира да је, Како се оно зовеш? 

МИКЕ: Мајк. 

Давид Ј. Малан: Мајк? ОК, Мајк, да ли можете да ми се придружите у овде на секунд? Заправо, не. Жао нам је Мајк, хајде да уназад. Како се зовеш? 

СКАНДАЛ: Неил. 

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

Дакле, ако Нил помера један корак максимално сваки време, и да се крећу Неил један корак, Морам да ово стварно досадан пас и назад, то је отприлике При томе, н корака, укупно н пута, јер ће ме одвести да су многи кораци да се Нил све начин да се тамо где припада. А камоли сви остали, ако сте Сви су погрешно наредио као добро. 

Дакле, назовимо врсту балон н квадрат. Време извршавања овог алгоритма, Перформансе овог алгоритма, Ефикасност овог алгоритма, овде ћемо описати више углавном као н на квадрат. Што је лепо, јер сам могао да урадим исти пример са осам, девет људи људи, а милион људи и да Одговор се неће променити. 

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

Па да видимо. Четири је прилично мали број, тако да сам ће вас оставити тамо тренутак. Оох, број два је још боље. Дакле, можете ли само корак напред за тренутак? Ово је сада моја најмања нумерисана кандидат, а ја ћу да се сетим да са, рецимо, променљиву. Али, ја ћу да провере. Да ли постоји неко ко је број је мањи? Шест, бр. Ох, има Нил поново. 

Дакле, ја ћу да вас одгурне врста концептуално. Нил ће напред доћи. А сада, променљиве које ја користим да пратити ко има најмањи број се ажурира да садржи Неил је локација. Па, хајде да видимо. Три, седам, пет. ОК, знам Нил био најмањи. Шта је најједноставније ми сада да радимо? Нећу да трошим време само бистрим Нил за једно место улево. Зашто не бих ставио Нила, где је припада, што је, наравно, где? 

Скроз на почетку. Дакле Неил, пођи са мном. А шта је зовеш? 

МИЛОСТ: Грејс. 

Давид Ј. Малан: Грејс. ОК. Дакле Грејс, нажалост, ти си врста на путу. Дакле, како да решим овај проблем? Зар не? Ако је низ, ту је Само седам локација. Подсетимо се да је, са Робом, разговарали смо о декларисање доба, а ми смо имали само коначан број векова? Иста идеја овде. Имамо само коначан број интс. Милост је врста у нашој начин, па како да поправим? 

Најједноставнији начин је да, Грејс, извини. Ти ћеш морати да иде преко тамо тако да можемо направити собу. Сада, ако мислите о томе, можда ми смо само направили проблем још горим. А можда смо, јер шта ако Грејс су били на правом месту? Али ми знамо да није, јер у супротном, она би била напред стоји уместо Нил у то време, зар не? Већ смо проверили њен број напоље. 

У реду. Тако да сада, Нил је на правом месту, и Ја могу да урадим благи оптимизацију. У следећем минуту, ја ћу игнорисати Нил сви заједно, тако да не губи време, или случајно свап га на погрешно место. Па сад, како да надјем следећи елемент који је најмањи? Два. То је прилично добар број, ако желите да иступи и Ја ћу те се. Шест, није добро. Четири, три, седам, пет, није добро. Дакле, да пређемо на ти Ваше право место. И управо смо среће овај пут. 

Сада, ја ћу игнорисати ово два момка, а сада још један пролазе кроз ово. Шест, то прилично мали број. Идемо напред. Ох, извините. Граце број је боље, тако корак даље напред. Четири. Извини, Грејс. Врати се поново. Број три је боље. Седам. Пет. И шта сада зовеш? 

Јасон: Јасон. 

Давид Ј. Малан: Јасон. Дакле, Џејсон је сада најмањи Елемент сам изабрао. Где ли он да иде? Дакле, где је шест. И твоје име је опет? 

Габе: Гејб. 

Давид Ј. Малан: Гејб. Гејб је на путу. Шта је најлакше да уради? Свап ова два момка и даље. Сада да видимо. Ко је најмањи? Четири. Само да некако варају. Пет ће бити најмањи. Мислим да следећи, ако, желите да корак напред, шта ја треба да урадим са ови момци, са Габе? Свап поново. Тако да сада, још увек мало у квару. Нашао сам Гејб да буде најмања, тако Ја га поп, померите се момци изнад. И урадио. 

Дакле, одговор је исти. Крајњи резултат је исти. Који од ова два алгоритма је бољи? Други, чуо сам. Зашто? 

ПРЕДСЕДНИК 3: То је н корака [ИНАУДИБЛЕ]. 

Давид Ј. Малан: То је н корака највише. Занимљиво. Тако да је, иако? Па како да нађем Најмањи елемент? Колико корака сам морао да се наћи најмањи елемент? Ја сам изгледа скроз на крају, зар не? Јер у том најгорем случају, шта ако је Нил био овде? Дакле, само налаз најмањи елемент Потребно ми н корака, или Н минус 1. Али, у реду. Тако поправити Нила. Не заборавите да, минут или тако. 

Али, како сам наћи следећи Најмањи елемент? То је минус н 1, н или минус 2 заиста, од броја корака. Дакле, у реду. Тако сам и урадио н минус 2. У реду. Дакле, да се осећа мало боље. У реду. Колико корака следећи пут да пронађе број три? Дакле н минус 4. Тако да је смањује, један мање корак на свакој итерацији. Дакле, то не осећа боље, зар не? Ако последњи пут је то било отприлике н пута Н, овај пут је н минус 1, плус Н минус 2, Н плус минус 3, плус н минус 4, тачка, тачка, тачка. Али, ако се сећате из средње школе уџбеници, мало подвалити лист на леђима који има формуле, ако додате ову серију бројева, што је укупан број корака Биће да сам овде узети? 

Ово је један од оних који, као, н минус 1, н пута, подељено са 2. Па да видим да ли могу да се повуче ово за тренутак. А опет, некако сам заокруживања неке Бројеви само да би наш живот једноставан, али колико се сећам, то је нешто као кад Ја н минус 1 ствари, онда н минус 2, затим н минус 3, она има овако нешто више од 2, а ако ја помножите ово, то је заправо н квадрат. То се не осећа добро. н н минус преко 2. 

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

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

Уместо да иде напред и назад и изабрати најмањи елемент, ја сам само да се осврнем на сваки од њих момци као што сам их срести, и убаците их у своје одговарајуће место. Дакле, ја ћу само да се почне са Граце, и ја видим да је она број четири. Где се број четири припада? Нисам почео сортирање ништа, Грејс добија тако да остане тамо. А сада ћу да тврдим, ако би могао предузме неки корак у десно, ово мој сортирана листа, ово је мој некласификовани остатак листе. Сада ћу наставити следећи, и како ти је име? 

Брансон: Бренсон. 

Давид Ј. Малан: Бренсон. Дакле, Бренсон је број два. Дакле, ја ћу вас одвести се за тренутак. А сада, где припадате у овом низу? Дакле, десно од благодати. Па опет, ми смо некако доношења Грејс до овде много посла. Где да те ставим? Дакле, ми ћемо да вам да померите лево, и ту убаците Брансон. Али сада ја тврдим да момци су урадили. Али, погледајте, ја не користим додатни простор. Још увек је 2 елемента овде, 5. овамо. Укупно је ред величине 7, тако да сам не варају, у реду? 

Тако да сада имамо, са Габе овде, број шест, где си ти? Имаш среће поново. Тако добијате да остану тамо. Само се благо корак десно Само да буде јасно да сте сортирају. А сада имамо опет Нила, број један, где идете? А сада је место где ћемо почети да видимо да Овај алгоритам, иако на први поглед, осећа прилично паметан, гледати шта ће се десити. Ако можете да иступи. 

Где желимо да стави Нила? Дакле, очигледно овде, па како да стигнемо тамо Нила? Хајде да урадимо ово корак по корак. Гејб, где треба да идете? Да, тако се један велики корак, или два пола-корака да направи један корак тамо. Грејс, где идете? Добро. Дакле, још један корак. И на крају, Бренсон? Још један корак. И сада можемо да ставимо Неил на своје место. 

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

Тако тужна ствар сада је све ово алгоритми су н на квадрат. Идемо напред и захваљујући оваквим момци, а замислите ове мало другачије. Врло добро урађено. 

[Апплаусе] 

У реду. Изволи. Хвала за - 

Брансон: [ИНАУДИБЛЕ] задржати бројеве. 

Давид Ј. Малан: Не, можете задржати бројеве као добро. У реду. Лепо урађено. У реду. Па да видимо да ли можемо сада резимирам брже, и више визуелно, управо оно што се догодило овде на следећи начин. Ја ћу да наставим и попните се Фирефок. Ми ћемо повезати ову демонстрацију на интернет страници курса. Јава је мало непријатно да се ради у неким прегледачима ових дана. Дакле, ако се играте са овим код куће, схватите да ћете морати да користите Фирефок да се то ради. И шта ћу да урадим са овим демонстрација је следећи. 

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

Дакле, ја тврдим да је ово визуелизација првог алгоритма ови момци урадили, Буббле сорт, при чему смо се заменили људе пар-мудре. Кључни увид у ову визуелизацију је да висина пруга представља величину броја. Дакле, виша трака, већи број. Краћи бар, мањи број. И ако сте приметили, ми идемо кроз првој итерацији овог алгоритма, замене велике и мале бројеве, тако да се мали број првом и велики број одлази у десно. 

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

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

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

Дакле, ово је избор врста. Дакле, опет, мисле о ономе што смо урадио са људима овде. Ишли смо кроз низ и изабраних Најмањи елемент поново, и опет, и опет. Сада тврде да је и даље прилично лоше. Она је и даље н на квадрат, узми или остави, али је, у стварном свету, мало брже, јер сам заиста узимао нешто мање корака сваки пут. Али, ми само говоримо шта? Можда 40-ак бара овде? Ми не говоримо 40 милиона. Дакле, то није потпуно јасно ми је да је заиста значајан добитак. 

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

Па да видимо, ако не можемо да резимирамо ово на следећи начин. Ја ћу ићи напред и само да дају нас нека врста заједничког начин да се говори о тим стварима, дозволите ми да представим само мало нотацији овде. Ви ћете видети нешто што се зове велико О, јер буквално је велика О. И то је начин на који рачунар научник или математичар чак користи да опише време рада неког алгоритма. Колико корака то заправо траје? 

Сада ћу да се осрамотити са мој рукопис овде за који тренутак. Али, дозволите ми да иде напред и рећи да Ово ће бити велики О овде. И дозволите ми да представим један други симбол, главни Омега. Омега ће бити супротно, у суштини, од великог О. док је Биг О значи, у најгорем случају, колико времена Можда неки алгоритам узети у Услови н, омега ће бити колико времена да би могло узети у најбољем случају. Па да видимо шта се подразумева под Најбољи случај за који тренутак. 

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

Шта је у најбољем случају, ако се заиста срећан? Само ће један корак, или исти број корака. Тако ћемо описати то као 1. Дакле, ово је прилично добар. Сада, шта ако смо негде као бинарну претрагу? Дакле бинарно претраживање, у најгорем случај, узео колико времена? 

[Изнео ВОИЦЕС] 

Давид Ј. Малан: Па у ствари, ја Чуо је за неколико места. Дакле, то је заправо лог н, узми или остави, зато што делимо листу на пола опет, и опет, и опет, ми смо у стању да пронађе, на крају, вредност, ако постоји, али постоји цака. Шта је претпоставка да морамо да узети здраво за готово за бинарну претрагу? Она мора да се сортирају. То се не сортира, можете поделити ствар у пола поново и поново, и ви може да иде лево, а можете ићи десно, и можете ићи лево и десно, али ти си неће пронаћи елеменат ако листа се не сортира, јер можда га пропустити. Зато што ваш хеуристике, за одлазак лево или право ће бити погрешна ако је то заиста не сортира. Дакле, постоји нека врста скривених трошкова да користи овако нешто. 

Сада, хајде да идемо у наш сортирање алгоритми не тражи - Ох, у ствари идемо у празно. Бинарни тражи у најбољем случају? Такође је 1 само ако се деси да буде у самом центру низа, или средина именика. Хајде да урадимо Буббле сорт. Дакле, опет, сад улазимо врсте, а не претраге. 

У најгорем случају, колико корака смо урадили Буббле сорт тврде да ће трајати? н на квадрат. Зато ћу извући то. Оох, мој рукопис изгледа још горе када је пројектован тако велика. У реду. Дакле, то је н квадрат. И у најбољем случају буббле врсте, колико корака ће то трајати? 1, чуо сам. 

СПИКЕР 1: н. 

Давид Ј. Малан: н, чуо сам. 

СПИКЕР 1: 2. 

Давид Ј. Малан: 2, чуо сам. Чујем 3? У реду. Чуо сам 1, н, 2, али хајде да изаберемо размаку од најмање први од оних сугестије, 1. То није лоша инстинкт, јер је врста следи образац овде. Али, ако је потребно само 1 корак, како у свет би могао да тврдим да је списак је сортиран, јер ако ми је дозвољено да се 1 корак, колико елемената могао сам стварно проверите да ли? Па, само 1, што значи да је н минус 1 елемената који би могли бити од поредак, а ја ћу само на вери након гледајући 1 елемент који ствар је сортиран. Дакле, 1 није тачно овде. Па минимално, колико морам да погледам? 

[Изнео ВОИЦЕС] 

Давид Ј. Малан: Н минус 1, или стварно, н, јер морам да погледам сваки елеменат да се уверите да то није у квару. Али опет, средицемо таласа нашег руке у мањем броју и Претпостављам да, као н добија велики, они су ионако незанимљива. Дакле, то је балон врста. А сада, хајде да ове последње две. Избор врста, а онда ћемо до сорт уметања. А онда ћемо разнети умове у нешто много бољи од свих њих. У реду. 

Који је најгори случај покренут време избора врсте? 

ПРЕДСЕДНИК 4: н на квадрат. 

Давид Ј. Малан: н квадрат, чујем. Али зашто н на квадрат, интуитивно? 

ПРЕДСЕДНИК 4: Зато што смо управо то урадили. 

Давид Ј. Малан: Зато што смо управо то урадили. ОК. Добар одговор. Али интуитивно, због чега је избор Сортирај н на квадрат? Шта морамо да урадимо опет и опет? Морали смо да кроз скенирање, су ти најмањи, ти си Најмањи, ти си најмањи. И готово, ми смо били у стању да се н кораци, а затим н минус 1, а затим н минус 2. Али, ако се некако додати оне све горе, или да га на основу обећања које сам додао их унапред, ми смо отприлике се н квадрат минус неким мањим бројевима. Дакле, ја ћу да позовем овај број на квадрат. Али са врстом селекције у најбољи случај, колико корака је ће да ме води? 

ПРЕДСЕДНИК 5: [ИНАУДИБЛЕ] 

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

Ја само могу да суде коректност у Избор врста избором Најмањи број. Али, чак и ако је број један прво, ако ја не знам ништа више о томе други бројеви, што ја не, све сам Знам да сам дао низ или скуп врата иза којих су бројеви, једини начин који знам да је један била најмања? Ако добијем скроз овде и остваре, Проклетство, један заиста био најмањи. 

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

Зато мислим да за себе оно што уметање Сортирај ће бити. Па, то није драматично, јер ја сам једини који је видео промену. Вау. ОК. Дакле, овде имамо нешто Различити демонстрациони. Ако сам зумирати овде, видећете да на Са леве стране имамо буббле сорт, у средњи имамо избор врсту, а на крајње деснице, имамо нешто што није погледао још назвао обједињавање сорт. Али размислите шта смо овде до сада данас. Када је Џенифер први пут дошао на сцену, смо прошли кроз низ бројева опет, и опет, са линеарним претрагу, и имамо линеарно време рада, Биг О од н, да тако кажем. 

Када сада размотрити прву недељу класа, када смо завади па владај, па смо именик цепање, и Џенифер, и ми смо колективно искористио да кључни увид, који је требало да понављам себе опет и опет од некако баците, баците, бацања, половина проблема, или генерално, проблем поделе на пола, а затим третира мањи комад проблем као и концептуално еквивалент на другом, ми смо некако урадили фундаментално боље. Али са мехурићима врстом, уз избор врста, са убацивања врсте, ми смо можда такви увиди да је Џенифер урадио. Управо смо прилично се врати и даље гомила времена, и ми смо намештена ствари мало, замене у том циљу, можда уметања или избором. Али на крају дана, ја сам много непријатно ходању и назад. Нисмо баш нешто полуга паметан попут Џенифер допала дељењем и освајање. 

Дакле обједињавање врсту, насупрот томе, ми који неће видети до следеће недеље, то ће да искористи кључна идеја да се дељењем унос, а затим преполовити, а затим преполови, а затим преполовити. И на свакој итерацији те петље, сортирање леву половину, као и право пола, онда Лева половина левој половини, и десна половина леве стране, а затим Лева половина десној половини, а десна половина десној половини. И понавља изнова и изнова. 

Тако ћете видети визуелно овај, али овај је оно што нас чека следеће недеље. И уопште, кад мислимо мало мало теже у сваком таквом проблему. Ми смо н квадрат са леве стране, н квадрат у средини, и н лог н са десне стране. Тако да ти је право Цлиффхангер. Видимо се у понедељак. 

[Апплаусе]