>> ПРЕДСЕДНИК: Добро, ово је ЦС50.
То је крај недеље три, а ако нисте узели већ предност,
знају да ће бити ручак овог петка као и обично, где
можете уживати добар разговор и храна на Фире анд Ице
са неким од ЦС50 је особља и школских другова.
Главе до УРЛ овде.
>> Сада можете да се сећате, или сте могу ускоро бити упознати са,
ове ствари овде, што су дати се на крају
семестра за многе класе.
Такозвани испит блуе књига, у којој пишете своје одговоре на испите.
Сада сам овде 26 су плаве књиге, на сваком од њих
је написано име, од А до Ж заиста имена су тако једноставно,
кроз З. и један од Циљеви при руци данас
ће бити да наставе са оним смо почели у понедељак, што није
толико гледа кода, али стварно гледајући идеје и решавање проблема.
Један од циљева и обећања овог курса
је да вас научи да размишљају више Пажљиво, више методично,
и да ефикасније решава проблеме.
И заиста, можемо то да урадимо стварно чак и без додиривања линију кода.
Тако да имам пар слонова овде данас, наранџаста и плава,
Ако бисмо могли да једног волонтера, можда из даље уназад него обично.
Како би било тамо, хајде доле.
Чији је циљ ће бити да помогне Плус управља овај испит овде.
Како се зовеш?
>> Публика: Мари Бетх.
ПРЕДСЕДНИК: Мари Бетх, хајде горе.
Пусти ме да је микрофон за тебе.
Драго ми је да вас упознам.
>> ПУБЛИКА: Драго ми је.
ПРЕДСЕДНИК: Добро, тако да имам Овде Плава књига до З,
а ја ћу се претварати да Имам једног од ученика,
и они долазе у нешто насумично на крају три сата испита блока,
па они завршавају у неким Полу-Рандом Ордер овако.
Сада је ваш посао у само тренутак иде да бити-- ово је у ствари, како су се
окренуо у крајем класе, највероватније.
Ваш посао сада ће бити, сасвим једноставно, да реши ове плаве књиге за нас
од А до З.
>> Публика: Ох, ово је ће трајати заувек.
>> ПРЕДСЕДНИК: И ми ћемо гледати као што сте то урадили, без притиска.
ПУБЛИКА: Не, нема притиска или ништа.
>> ПРЕДСЕДНИК: А за забаву, хајде да стави до тајмер.
>> ПУБЛИКА: толико забавно, толико забавно.
>> ПРЕДСЕДНИК: Могу држати микрофон за вас.
У реду, управо смо удвостручили нашу брзину.
Дакле, у међувремену, дозволите ми да представљају оно што је ће бити питање за Мари Бетх
је оно што је она ради, како је она иде о решавању ово?
И, у ствари, можда нећете имати икада размишљали о нечему
тако једноставно као када сте изабрали до 26 књига као што је ова,
који немају природни наредио њима.
Шта је процес да сте заправо коришћење?
Да ли је то прилично насумично само брање прву што видите
и стављајући га на свом месту?
Да ли први корак руке око у потрази за онда тражите Б?
Да ли да погледате пар њих раме уз раме
и само да кажем, чекај мало, ово није у реду, а онда замените налог?
Већ смо видели у понедељак да постоји неколико начина
у којем можемо да урадимо ово, а заиста као што смо близу краја овде
Ја бих да обратите пажњу, можда од чега Мари Бетх ради.
Имамо неколико гомиле чини се, већи један, три мање.
>> ПУБЛИКА: Ја их наручивање кад нађем два писма
да ја знам су заједно у низу, Ставио сам их заједно, тако да ја не
морају да брину о одржавању Трацк читавог реда књига.
То је само, ох, је први, Имам тај стек овде.
ГОВОРИ: Дакле, скоро као слагалица комада да
имају право на облик поклапају једни са другима.
Публика: Прилично, да.
ГОВОРИ: У реду, одлично.
А сада сваки од њих гомиле је вероватно сортирано?
>> Публика: Да.
>> ПРЕДСЕДНИК: Добро, кроз З. Алл десно, честитам, успео си.
Имате свој избор.
Плава?
У реду, хвала вам на томе.
Тако Мари Бетх ли предложити оно што је њен приступ је био,
али оно што је још један приступ како сте Можда иде о сортирање те ствари?
Шта би ти урадио?
Рекорд да победи било би један минут и 50 секунди или тако,
плус оне Заборавио сам да бројим.
Шта би ти урадио?
Да?
ПУБЛИКА: Узми стек.
Почети од почетка.
Проверите своје папире.
А ако је неко виши врх него, можда, они су,
дно један је већа, а затим их пребаците.
>> ГОВОРИ: ОК, почевши на врху и дну,
и онда радити свој пут унутра тако их замене?
У реду, тако да мало сличан у духу са буббле врсте,
али избор екстреме нису суседне парове.
Али мање од тога је да постоји сигурно гомила различитих начина
можемо да урадимо ово, а Искрено, мислим да би некако
усвојила неколико приступа, зар не?
Сте направили неку од четири разврстаних шипова, и затим их ефикасно уједине.
И то је, претпостављам, још један техника укупно.
Ниси га третира као једна велика гомила, ви подељен проблем на четири четворки,
ако хоћете, а онда некако спојио их у крају.
>> Па хајде да размотри, на крају, Како другачије бисмо могли урадити.
Формализована смо појам на Буббле методу прошли пут,
и Буббле Сорт опозива је алгоритам да визуелно
са осам својих другова овде, наизглед насумице поредани на први поглед.
И ми смо онда одлучили паровима, ако два елемента су ван реда,
једноставно их замене.
Па четири и два су очигледно не ради,
тако да они два класесбиедру заменио позицију.
А онда смо поновили са четири и шест, затим шест и осам, на сваке итерације,
креће на десно.
>> Па с обзиром осам особа, колико попарно Поређења сам урадио док ходате из
лева на десно у једном таквом итерацији?
Колико Поређења?
Седам, зар не?
Јер ако постоји осам људи, али имате пар
их и ви се креће један хоп са десне стране,
нећеш имати осам поређења, јер не можете да упоредите
елемент против себе, или би само бесмислено, тако да имате седам.
Или уопште, ако је имамо н људи, ми смо
урадите н минус 1 поређења са балон врсте.
>> Дакле, хајде да сада размотрити колико је добар или лоша Буббле Сорт заправо, и покушајте
да себи дам речник са што да критикује алгоритмима као што је овај,
и ускоро наше.
Тако да у првом пролазу кроз Буббле Сорт, први пут
Ишао сам с лева на десно преко фаза, узео ме н минус 1 поређења.
Као и да ће бити мој јединица мере, зар не?
Ја сам некако говорио и шетњу, донекле брзо, спори,
па бројање мој број секунди није посебно говори,
али бројање броја операције да сам у понедељак,
упоређујући двоје људи, то се осећа као леп јединици мере.
>> Па н минус 1 кораке први пут, Али шта се онда десило после тога?
Шта је један наопако од једном пролазу кроз иначе обичан списак?
Шта можете да ми кажете о елементу који је био скроз тамо?
Да?
То је био највећи елемент, зар не?
Број осам, иако је почео овде, сваки пут кад
у односу је против комшија, она је стално
бистрим до десно ханд сиде листе.
И заиста, то је тамо где алгоритам добија своје име.
>> Сада по тој логици, колико поређења Треба ми да се други пут
Правим који пролазе са лева на десно?
н минус 2, зар не?
Управо ће то бити губим време ако ја држати упоређујући осам против некога
друго, јер већ знамо она је била на правом месту.
Тако да је то мало оптимизација, тако да следећи пролаз
ће бити плус Н минус два корака, где је н број људи.
Сада можете да некако екстраполира, чак и ако нисте рачунар научник,
како се то завршава.
На крају овог алгоритма, вероватно имаш само један поређење отишао.
Морате да некако поправити почетак листе у случају да два
и један су од реда и треба да буде један и два,
Дакле, ово се до дна у Плус 1 коначна поређење.
>> Сада тачка, тачка, тачка врста таласа је руке на неке од сочније детаље,
али хајде да само напред и поједноставити.
Ако се сећате из високог Сцхоол, искрено, многи од вас
имали математичке књиге које су имале мало Цхеат схеет
на насловној или Поклопац са задње стране који вам је показао
шта сериес сумирања попут Овај на крају додао до.
У општем случају, ако имате променљива попут н, и заиста ова,
Ако сте гледали на вашем Олд Сцхоол матх боок,
видели бисте да је ово у ствари додаје до ове суме овде
н пута н минус 1 све подељено са 2.
Дакле, за сада само да утврђују То је истина, тако на Леап оф Фаитх,
то је оно што овај сумира до, и ми смо могли
докаже да је у више општем случају.
Али сада хајде да се прошири ово.
Дакле, хајде да се умножавају ово, тако да је н квадрат, минус н, све подељено са 2.
То је стварно н квадрат, подељено са 2, минус н више од 2,
тако да је све лепо и занимљиво.
Али шта се дешава ако сада плуг-ин вредности?
Претпостављам да нисам имао осам људи, али кажу милион.
И милион само зато то је прилично велики број,
хајде да у плуг и види шта се дешава.
Дакле, ако сам утикач милион у ту формулу Идем да милион квадрат,
подељено са 2, минус милиона, подељено са 2.
Сада шта то иде до изједначења?
Тако 500 милијарди, минус 500.000.
И ако ја заправо радим да се математика, то значи
који сортирање милион људи са балон врсте
Можда ме се 499.999.500.000 кораци или поређења на крају,
само смо екстраполацијом.
>> То се осећа прилично споро, али, искрено мерење један посебан улаз
овако, није све то рекли.
Али заиста то не сугерише да је н добија све веће и веће, овај алгоритам
врста осећа лошије и горе, или стварно
почети да осећају бол који степеновање, да је н на квадрат,
која сабира прилично брзо.
А овај детаљ није изгубила на људе, у ствари
Пре неколико година неки сенатор који је био кампање, сео за интервју
са Гоогле Ериц Шмит, извршни директор у то време,
и био је оспорио са питањем личи ми истражујемо данас.
Хајде да погледамо.
>> [ВИДЕО РЕПРОДУКЦИЈА]
>> Сенаторе, ти си овде на Гоогле, и волим
да мислим о председништва као интервју за посао.
Сада је тешко добити посао као председник,
и идете кроз суровости сада.
Такође је тешко добити посао у Гоогле-у.
Имамо питања, а ми питајте наших кандидата питања,
а ово је од Ларри Швимер.
Љта-- ви мислите да сам шалим се, то је овде.
Који је најефикаснији начин да се сортирање милион 32-битне целе бројеве?
>> -Велл--
>> Жао ми је, маибе--
>> Не, не, не.
Мислим да је балон врсту би био погрешан пут којим треба ићи.
>> Хајде, ко му је то рекао?
Нисам видела рачунар Наука у позадини.
>> -Имамо Наше шпијуне тамо.
>> ОК, хајде да питамо другачији Интервју питање.
>> [ЕНД ВИДЕО РЕПРОДУКЦИЈА]
>> ПРЕДСЕДНИК: Тако говори о Конкретни бројеви ипак,
неће бити све то корисно.
То није живот лекција коју балон Сорт, дао милион улаза,
може потрајати чак 500 милијарди корака.
Ви стварно не могу генерализовати такође ефикасно од тога
и доносе добре одлуке дизајна приликом писања програма.
Дакле, хајде да, иако се фокусира на то како можемо да поједноставимо овај резултат.
>> Па сам нагласио у жуто овде резултат н квадрат подељен са 2,
па милион квадрата подељена са 2, а затим
Ја сам нагласио шта крајњи одговор
Када смо одузима Офф н подељен са 2.
А тврдња ћу да сада, који је дођавола брига ако одузмете Офф
мали стари Н преко 2, када први део ове формуле је толико много већи?
Доминира друга израз, н квадрат подељен 2
је много већи, јасно, јер н добија велика као милион,
да постоји заиста велика разлика у крај дана од 500 милијарди
и 499.999.500.000?
Не баш.
Па шта ћемо да уради како компјутерски научници се
игнорисати те ниже услове реда и узети нешто овако и стварно
само поједноставити да израз који ће битно.
Већи Наши скупови података се, већи нашим базама података добију, више веб странице
морамо да тражи, више пријатељи имате на Фацебоок.
>> Као н добија већи, ми стварно ће да брине о величини
термин у сваком таквом анализи наш алгоритми перформансе.
И ја ћу да кажем, знаш шта, Буббле Сортирај је по налогу Биг О,
по налогу Н на квадрат.
То није баш н квадрат као што смо видели,
али који није брига о тим мањим условима,
и искрено, који заиста брига ако поделимо са 2?
То је само стални фактор.
И 500 милијарди долара у односу на 250 милијарди стварно тако велика ствар?
Ја само могу да чекам годину дана, нека мој лаптоп буквално
добити дупло брже у хардверу, и такве разлике
Само одлази природно током времена.
>> Оно што ми је стало је израз, део
израза који ће да варира као наш улаз постаје све већа и већа.
И заиста, у стварном свету, то је оно што све више дешава
то су улази на наше проблеме и алгоритми су све већи.
Па Биг О ће бити нотација, асимптотско нотација, које смо управо
користити као компјутерски научници за описивање перформансе, или трчање време,
алгоритма.
Тако да можемо да упоредимо алгоритме на различитим рачунарима писаним
од стране различитих људи, користећи неки суштински слично метрички
као број поређења си одлука, или можда број свопови
правите.
>> Оно што ми не идемо у Број је количина времена
који пролази на сату на зиду типично.
Оно што нећемо да брине о томе колико је меморије
користите данас у најмању руку, иако је то
Још један ресурс можемо мерити.
Ми ћемо покушати да заснивамо наше анализе на само основне операције, они,
искрено, да можете највише визуелно види.
Дакле, са нечим као Биг О од н квадрат, ја тврдим да је О н квадрат
је горња граница тзв руннинг време балон врсте.
Другим речима, ако је желео да тврде да постоји
Ова горња граница колико кораци алгоритам може потрајати,
то ће бити у великој Ø Н квадрат у овом случају, горњу границу.
>> Шта ако сам уместо тога променити прича да се не ради о буббле врсте,
али о томе горња граница.
Можете ли се сетити алгоритма које смо гледали већ
чији горњу границу, максимална мерење времена, или операција,
би се рећи да је ограничен Н, линеарна функција,
Не квадратни која је закривљена?
Шта је алгоритам који Увек не траје дуже
него као н корака, или 2н кораци, или 3Н кораци?
Да?
>> ПУБЛИКА: Проналажење највећи број на листи?
>> ГОВОРИ: Перфецт, проналажење највећи број на листи.
Ако сам дао листу људи за пример,
сваки који држи број, који је максималан број
корака треба ме, разумно паметан човек,
да пронађе највећи особу на том списку?
Н, зар не?
Јер, у најгорем случају, где је Можда највећа вредност бити?
Добро, све на крају.
Дакле, у најгорем случају горња граница, могао бих
морамо да идемо до краја овде и бити као,
Ох, ево је број осам, или шта год да је вредност.
Сада само би било глупо ако ја стално идем, зар не?
У потрази за више и више елемената Ако последњи од њих је тамо?
Тако да сигурно, н је горњу границу.
Не треба да предузму више корака од тога.
>> Па шта ако уместо тога сам предложио да постоје алгоритми на овом свету који
имају време рада који је омеђена Биг О дневника Н, лог н?
Где смо видели раније?
Да?
>> ПУБЛИКА: У проблему у телефонском именику?
ПРЕДСЕДНИК: Као проблем у именику.
Каква је била мера како много времена или колико сузе ИТ
Требало ми је да нађем неког попут Мике Смитх у именику?
Тврдио смо да је лог н, и чак и ако нису упознати или да је
мало магловито шта логаритхм или експонент је,
Само запамтите да лог н генерално се односи на процес,
у овом случају, поделе нешто на пола опет, и опет,
и опет, и опет, такав да добија све више мали као ти то.
>> Па лог н односи, наравно, у телефонски именик пример,
у бинарни потрази у теорији, када смо имао виртуелна врата на табли,
или када је Сеан у потрази за нечим.
Да је користио бинарну претрагу, лог н би горња граница колико
време које узима.
Али ти алгоритми који се извршавао на лог Н Претпоставља Који кључ детаље?
То је листа сортирана, зар не?
Ваш алгоритам је лоше ако Ваш улаз се не сортира,
а ипак користите нешто као бинарног претраживања
јер би могао скочити право над елементом
без схватајући да је заиста тамо.
>> Сад шта би то значило, Биг О једног?
То не значи да је ваш алгоритам траје један и само један корак,
то само значи да треба исти број корака.
Можда је то 1, можда је 10, можда је 1.000,
али је независна од величина проблема.
Без обзира на то колико је велико н, Цонстант време алгоритам
увек узима исти број корака.
Дакле, шта може бити алгоритам смо говорили о томе или једноставно
интуитивно који долази да ти да Увек ради у такозваном сталном време?
Да?
>> ПУБЛИКА: Додајте два броја.
ПРЕДСЕДНИК: Додајте два броја, 2 плус 2 једнако 4, урађено.
Тако да може да ради, шта друго?
Како би било још стварном свету, зар не?
>> ПУБЛИКА: Проналажење Прва ствар на листи.
ПРЕДСЕДНИК: Проналажење први елемент у листи, сигурно.
Ми смо заправо причали већ око низова,
како добити на први елемент у низу,
Без обзира на то колико дуго низ је у Ц код?
Само користите као носач Зеро нотација, бам, си тамо.
И заиста, као низови страну, нешто Суппорт опште позната
као случајним приступом, са директним приступом Меморија, јер буквално можете
скочи на било ком месту.
Можемо да урадимо ово још више једноставно можемо уназад до недеље нула
када смо нуле.
Колико је времена било потребно за кажу блок у нуле да изврши?
Само Цонстант време, зар не?
Да кажем нешто, кажу нешто, није битно
Колико је велика Огреботине свет, то је увек Биће потребно исту количину времена
да једноставно кажем нешто.
>> Дакле, то је константа време, али оно што је друга страна?
Ако је то горња границе, шта ако желимо
да опише ниже границе наших алгоритама времена рада?
Готово најбољем случају потенцијално, ако хоћете,
мада ови услови може да се примени на најбољи начин сандуци, најгорим случајевима, просек предмета више
генерално, али хајде да се фокусирамо на нижим границе уопште.
Шта је алгоритам који има доње границе н корака,
или 2н корака, или 3Н кораци?
Неки фактор н корака, То је његова доња граница.
Да?
>> ПУБЛИКА: Буббле сорт?
>> ПРЕДСЕДНИК: Буббле сорт узима ви минимално Н кораци, зашто?
Зашто је то тако?
Зашто би то почетак да дођем к вама интуитивно, чак и ако то не само
још?
Да?
>> ПУБЛИКА: [неразумљиво].
ГОВОРИ: Тачно.
У најбољем могућем сценарију Буббле Сорт, а доста алгоритама,
ако ти предати осам људи који су већ сортирају,
било би глупо за вас, алгоритам,
да иде напред и назад више него једном, зар не?
Јер чим ти хода кроз листу једном,
ви треба да схвате, ох, направио сам не свапс, ова листа је сортирана, излаз.
Али то ће вас н кораке предузети.
>> И обрнуто, што је још једна начин размишљања о томе?
Буббле врста је Омега, да тако кажем, Н,
јер ако погледате мање од н елемената, што
постоји фундаментално питање?
Не знам да ли је то сортирају, десно.
Ми људи Можда поглед на осам људи и бити као, Ох, то је сортирано,
да ме није н кораке предузети, али јесте.
Очи, чак и ако сте љубазни из имају велики видно поље,
погледао осам елемената, погледао осам људи,
То је ефикасно осам корака.
И само ако ходам кроз цео Списак ја схватају, да, сортирано.
Ако престанем да размишљам пола, све Добро, то је прилично поредани сада,
какве су шансе да није сортиране?
То алгоритми неће бити тачан.
Можда буду брже, али нетачно.
>> Тако да сада имамо начин описује ниже границе,
А шта је са сталном времену?
Шта је алгоритам који има мањи везани на свом Потребно време једног?
1 корак, 2 корака, 10 корака, али константна, независно од н,
величина улаза?
Да, позади.
>> ПУБЛИКА: принтф?
ПРЕДСЕДНИК: Шта је то?
ПУБЛИКА: принтф?
ПРЕДСЕДНИК: принтф.
У реду, наравно.
Тако да је потребно фиксни број корака.
И ја би требало сада да Сад-- Говоримо о Ц коду
а не Сцратцх, нешто попут рецимо, са принтф,
требало би да почне да се опрезан.
Јер принтф узима улаз, то је ниска,
и гудаче да технички има дужину.
Дакле, ако ми сада желимо да изаберете на вас, ако не смета,
Технички смо могли тврдити да је принтф узима променљиве улаз дужине,
и сигурно то може потрајати више Време је да одштампате стринг тако дуго,
него овако дуго.
>> Па шта ако смо у обзир сортирање и претраживање примере?
Шта је са Мике Смитх на телефону књига, или бинарна претрага уопште?
У најбољем случају, шта би могло да се деси?
Ја отворим телефонског именика и, бам, ту је Мике Смитх је број.
Могу да га позовем одмах.
>> Је један корак, можда два корака, али константан број корака
ако имам среће.
И искрено, видели смо на Мондаи Иоур цлассмате
добити прилично среће два пута узастопно.
И то је било заиста константан пут у нижим границама
на алгоритму у питању за проналажење број 50 стоји иза оних затворена
врата.
>> Сада, као на страну, ако откријете да су Биг О, горња граница,
и Омега, доња граница, су једно у исти, да
је иста формула у заграде, можете такође
кажу, само да буде фенси, да је нешто у тета
Н или тета неког другог вредности.
То само значи да када велики О и омега су исти.
Шта о избору врсти сада?
Хајде да користимо овај нови вокабулар.
У избору врсте, шта смо раде опет, и опет, и опет?
Хтео сам напред и назад кроз листа, у потрази за кога?
Најмањи број.
>> Па колико корака, како многи Поређења зар не
морати да како да схватим ко најмањи елемент у листи био?
н минус 1, зар не?
Јер ако сам почети с једним сам дао и ја почнем њега или њу у односу,
онда њему или њој, он или она, он или она,
могу само да упарите елементе заједно н минус 1 пута.
Тако да избор сорт Слично узима н минус 1 кораке први пут.
>> Колико корака то ме води у наћи други најмањи елемент?
н минус 2, јер сам био глуп ако Стално гледајући истих људи
опет, ако сам већ га је изабрао или ње и да их стави на своје место.
И трећи корак, н минус 3, затим н минус 4.
Видели смо овај образац пре, и заиста
Избор сорт Слично има горњу границу
за Н на квадрат, ако урадимо ону сумирање.
Оно што је његова доња граница, избор врста?
Минимално, колико времена селекција мора Сорт узети, као што смо то дефинисано у понедељак?
Предложити две опције.
Можда је н, као и раније.
Можда је то н квадрат, као што је је сада као горњу границу.
>> Публика: н квадрат.
ПРЕДСЕДНИК: н квадрат.
Зашто?
>> ПУБЛИКА: Зато што имаш дефинисати [неразумљиво].
>> ГОВОРИ: Тачно.
Барем како сам је дефинисано селекције врсту било је прилично наивно, настави,
наћи најмањи елемент.
Иди опет наћи најмањи елемент.
Нема врста оптимизација тамо да
Можда дозволите ми прекинути после само н или тако корака.
Дакле заиста, селекција врста, омега Н на квадрат.
>> Шта је са уметања врсти, где сам узео који сам добио, а онда сам га гурнуо
или је на правом месту?
Онда сам наставио да другом лицу, гурнуо га је на правом месту.
Затим следећа особа, гурнуо њега или ње на правом месту.
Обратите пажњу да је ово веома Линеар, да тако кажем.
Ја сам права линија, ја сам не иде напред и назад,
Никада нисам гледајући уназад стварно, али шта се дешава кад сам га убаците
или она у почетку списак као што смо урадили у понедељак?
Шта се дешава?
Да?
ПУБЛИКА: [неразумљиво].
ГОВОРИ: Да, то био улов, зар не?
Можда се сећате из својим друговима, ако
су правили било какве покрет са ногама, то је операција.
Дакле, ако је било троје људи овде и нова особа припадало пут тамо,
на дугом сцени као што је овај, наравно, он је или она само да оде до самог краја.
Али, ако размишљамо о рачунара и низ меморије,
ови људи иду морати дволичност преко
како би направили места за ту особу.
И тако да је н минус 1 схуффлингс, н минус 2 схуффлингс, н
минус 3 схуффлингс је само врста дешава иза мене, не испред мене
као и раније, у неком смислу.
Сада као страну, и као можда сте видели на мрежи
ако почнете убадањем негде око врсте, има толико различитих оне
тамо, неки од њих боље од других.
Заиста, богосорт је један То је врста забаве да се угледају.
Богосорт узима сет бројеви или кажу шпил карата,
случајно их схуффлес, и проверава да ли они сортирају.
А ако не, то понови.
Ако не, не опет.
Невероватно глупа.
>> И заиста, ако сте прочитали као Википедиа артицле,
његов надимак је глупо Сорт.
То ће на крају радити, надамо се, дати довољно времена,
али да количина времена могао да доста времена.
Дакле, ако бих могао, хајде да убрзамо ствари се из Мари Бетх примеру раније,
тако што још неколико елемената, али још два процесора.
Двоје људи, вама ако Не би ми сметало ме придруживања.
Како око 1 овде, и хајде да иде-- нико тамо?
Нико тамо?
У реду.
Ви са црном мајица, да, хајде доле.
У реду, како се зовеш?
>> Публика: Питер.
>> ПРЕДСЕДНИК: Шта је то?
>> Публика: Питер.
ГОВОРИ: Питер, Дејвид, драго ми је да смо се упознали.
У реду, имамо Питер овде, ако желе да дођу на сто овде.
А како се ти зовеш?
>> Публика: Елена.
ГОВОРИ: Елена.
У реду, драго ми је да смо се упознали.
Елена сусрет Петер.
Питер, Елена.
И ми ћемо морати Андрев овде као добро, молим те.
И ваш изазов иде бити да сортирате шпил карата.
А ако непознатим, Децк картица треба на крају
бити сортирани нешто попут Ово где ћемо урадити клубове, а затим
су спадес, онда срца и Дијаманти, од кеца као један,
све до краља.
>> Картице ћу ти дати ће бити 52 у количини.
Идемо на сличан начин пут када, на тренутак.
Идемо бацити Андрев појави на екрану овде,
тако да гледају како се ово.
И тако да је све ово је све видљивији,
то су картице које сам добио на Амазон.
Тако да већ насумично сортирају, а ми ћемо вас време.
И ми ћемо Кееп Ит Реал овај пут,
па ћемо покушати да вас притисак јер би у супротном то ће добити досадно
брзо.
Ако би могао да настави да сортирате 52 елементи заједно преко неки начин, сада.
>> И опет, као што гледамо ове момци шта ради, на крају
ће производити очигледно Резултат, размислите о стварно
како они то раде једни, како можете да га описати.
Јер опет, су сви процеси, алгоритми
да узимамо здраво за готово као човек.
Али ви сте вероватно дуго интуиција, дуго пре него што чак и
размишљала је о узимању Класа цомпутер сциенце вас
можда имао интуицију са што за решавање проблема као што је овај.
Али када препознајете обрасци и почну
да формализују кораке са којима сте решавање ових проблема,
ћете наћи да можете решити много занимљивији и много сложеније
Проблеми брзо.
Тако да неко из публике, што је најмање један елемент алгоритма
да они користе овде?
>> ПУБЛИКА: [неразумљиво]
ПРЕДСЕДНИК: Шта је то?
Публика: Би одело.
ПРЕДСЕДНИК: По оделу.
Дакле, прво су груписањем све дијаманата заједно
чини, сви срца заједно Чини се,
и тако даље, без поштовања за бројеве на картицама.
А сада се појављују, на пример, да да их сортирате по броју.
Врло добро.
>> У реду, па шта ће бити последњи корак онда овде?
Једном када имамо четири разврстане одела, шта морамо да урадимо за четири гомиле
у циљу постизања један поредани палуби, једноставно?
Тако да морамо да их поново споји.
>> Тако да је занимљива идеја која Опет, претпостављам, је веома интуитиван и
ако никада можда ошамарио та врста етикете на њему.
Овај фундаментални појам поделе Проблем није у пола овом тренутку,
али најмање у четири комада.
Решавање прилично суштински идентичне проблеме
у изолацији сваке друге, и затим спајање резултате.
И, одлично, урађено.
У реду, велики округли аплауз, ако бисмо могли.
>> [АППЛАУСЕ]
>> ПРЕДСЕДНИК: Немам појма шта ћете везе са овим, али ево ти.
Хвала вам пуно.
Па хајде да видимо, два минута и осам секунди,
Ако желите да оспори своје пријатеље.
Шта је онда ће бити одузети од овога
да можемо искористити уопште?
Па, мислим назад на Овај низ бројева,
и мислим се сада на неке од Псеудокод смо написано у прошлости,
и то је за Псеудокод решавање проблема у именику.
При чему у Псеудокод И набројао више методички начин
о описујући како сам урадио веома интуитиван људски алгоритам поделе телефон
књига у пола, поновите, понављам, понављам, док не нађем неког попут Мике Смитх,
Ако је он доиста у именику.
>> Али сам некако користио шта ћу назвати веома итеративан приступ овде,
посебно обавештењу линија 8 и линија 11.
Они су доказ итеративни приступ, Лоопинг приступ,
јер је то управо понашање које изазивају.
Те линије оба кажу иди на Линија три, а можете некако
мислим да је у вашем Еие ума као петља.
Те је говорио да се вратите до корак три и понављам, опет, и опет,
и поново.
>> Али шта ако искористе кључну идеју овде да ми није последњи пут,
и поједноставити линија 8 и линија 11 и њихови суседи
јер управо то, у жуто.
Није суштински скраћење Псеудокод веома много,
али је у основи мења природа мог алгоритма.
Оно што сада говорим у кораку 7, у кораку 10,
је да се тражи за Мике на потпуно исти начин,
али само у левој пола или десна половина.
>> Другим речима, ако је Почнем од корака један,
покупи телефонског именика, отворен до средине из именика, погледај имена,
ако је Смит је међу име је, позовите Мајк, друго
ако је Смит је раније у књизи, Седми корак сеарцх фор Мике ин левој половини књиге.
Али та врста осећа као то ме оставља виси, зар не?
У жутом, јесте упутство, али како радим
сеарцх фор Мике у левој половина именика?
Где имам алгоритам са којима сам
да тражите некога као Мике Смитх?
Па, то је нас буљи у лице.
Ја могу да буквално користите исти Програм ефикасно иде до врха
Поново и поново Трчање исти линија кода.
>> Тако да, иако то треба да се осећа као мало у цикличне дефиниције
где си одговарате неко Питање које некако питам
Опет исто питање, као и зашто, зашто, зашто?
Реалност је, јер смо напорно смо кодирана пар специјалних линија, корак 4,
што је ако, и корак 12, који је ефективно друге гране,
јер ми имамо те изрицање привремених мера, Овај алгоритам ће прекинути ако се
наћи Мике, или ако то не урадимо.
Али у кораку 7 и 10 Сада, имамо оно што ћемо назвати рекурзивни алгоритам.
А Рекурзија је заиста моћан идеја то је мало ум савијање на први поглед,
сада можемо применити на следећи начин.
>> Мерге сорт ће бити последњи врста која гледамо, барем у класи формално.
И то је суштински другачије од оне последње три, а сигурно
последња четири ако се укључити богосорт.
Ево Псеудокод за стапања врсте.
Када је на улазу н елемената, тако да с обзиром низ величине н, ако је н мање од 2,
вратити.
Па зашто морам да Санити прво проверите?
Шта је импликација ако те предати низ чија је дужина је н мање од 2?
То је већ сортирају, очигледно, зар не?
Јер листа или има један елемент, који је тривијално
поредани зато што је једина ствар тамо.
Или, то је од величине нула, што значи нема ништа за сортирање, тако по природи
је сортирана.
Нема баш ништа не ваља.
Тако да је наш такозвани основни случај.
>> То је слично у духу на оно што смо урадили са Мајком.
Ако је Мајк је у телефонском именику, зови га.
Ако он није тамо, одустати.
То је такозвани основни случај, да се уверите Овај алгоритам на крају дана
ће престати да у одређеним околностима.
>> Али овде је Леап оф Фаитх сада, друго, сортирање левој половини елемената,
затим сортирате право половина од елемената,
а затим се стапа сортирани половине.
А овде где се осећа да смо копирала напоље.
Ја сам вас питао да сортирате н елемената, а ја сам
говорећи, ОК, разумем сортирање по лево и сортирање право.
Али ја кажем једну друга ствар, и ово
је Кључна тема изгледа у интуицији до сада,
ту је овај трећи корак спајања.
Који чак иако њега изгледа тако глуп у духу,
Као само спојити ствари заједно, чини
бити кључни корак ка склапање два проблема који
су на крају подељене на пола.
>> Тако спајају врсте, хајде да урадимо ово, ако ћете хумор ми, са још једним демонстрацијама,
само да имамо неке Бројеви за рад.
Да ли могу да размењују осам стрес Лопте за осам људи?
У реду, шта је са тобом три, ви Фоур У овом делу, пет, шест, и да
Не 7, 8, хајде горе.
ОК, да у реду.
Минус 8, тамо идемо, плус 1.
Одлична.
У реду хајде горе, хајдемо брзо вам бројеве.
Број два, број три, број четири, број пет, шест, седам, осам и.
Сам осам добро овај пут.
>> У реду, тако да само напред ако можеш, и хајде да сортирају по оригиналном редоследу
да смо имали јуче што је изгледало овако, ако не би сметало.
И хајде да то урадимо испред стола.
У реду, тако да споје врста.
Ово је место где се иде да се занимљиво,
јер изгледа да даје себе много мање информација данас.
>> Па споји врста, пре свега на улазу од н елемената,
и очигледно не мање од два, то је осам, тако да имам још мало посла.
Дакле, сада смо ментално као класа су сада у другом грани,
што значи три корака.
Прво, морам да сортирате Лева половина елемената.
Па како да идем о томе ово?
Па, ја ћу некако ментално поделити листу овде,
не морате да физички крећу, а ја сам
ће се фокусирати само на Лева половина елемената овде.
Па како да идем о сортирање Листа сада величине четири?
Шта је мој алгоритам?
Први пут сам проверити је н мање од два, не, па сам наставите на другом блоку поново.
Сортирај левој половини елемената.
>> Тако да сада опет, ментално, и ово је где
морате да остварите много ментална историја, ако хоћете.
Сада сам сортирање лево половина левој половини.
У реду, тако да сада зовем свог исто стапање сортирање алгоритма, је н мање од два?
Не, то је два, па морам да сортирате Лева половина, а десна половина.
Па идемо, сортирање левој половини.
Зашто једноставно не узети један корак напред.
Како се зовеш?
>> Публика: Даррен.
>> ГОВОРИ: Дан.
Дан је иступио.
>> Публика: Даррен.
ГОВОРИ: Дарен, урађено.
Да ли сте рекли Дарен или Дан?
>> Публика: Даррен.
>> ГОВОРИ: Даррен.
У реду, Даррен је изашао напред и он је сада сортирана.
А ово је скоро Инане тврдња, зар не?
Ја стварно не изгледа да се постизање ништа, али хајде да наставимо.
Сад ме пусти да сортирате право половина елемената.
Како се зовеш?
>> Публика: Луке.
>> ГОВОРИ: Луке.
Хајде, иступи.
Урађено, ја сам сортирано Луке.
Лева половина је сада сортирају и десна половина сада сортиран,
али опет, ту је кључни корак овде.
Шта даље треба да урадим?
Стопи сортирани половине.
Сада ћемо само сви назад на овај начин,
јер сам некако треба неки Сцратцх простора.
То је скоро као ови момци су на столу,
и треба ми мало места да их се креће даље.
Па ћу да се споје момци би лоокинг
на левој половини и десне половине.
И који очигледно на првом месту, лева половина или десна половина?
Дакле десна половина, па кренимо Луке над овде да првобитну позицију Даррен.
И сада да споји своју леву половину у, Даррен ће да се креће тамо.
>> Тако се осећа као готово ефекат балон врста,
али мој основни алгоритам, другачије овај пут.
Али сада је место где ствари постају мало досадна јер тебе
морају ментално уназад где сам стали.
Управо сам спојио разврстане половине, што значи да сам гдје у мом алгоритму?
Морам да сортирате десној половини, зар не?
>> Ако се уназад, буквално на видео, ти ћеш
видимо да смо на ово тачка Луке и Даррен
сортирање улево за половина левој половини.
Онда смо спојили оне сортирана половине, које
значи следећи корак је врста десна половина леве половине.
У реду, хајде да ово брже.
У реду, шест, ја ћу тврде сада су поредани, хајде напред.
Како се зовеш?
>> Публика: Адриано.
>> ГОВОРИ: Адриано.
Адриано је сада сортирана.
А како се ти зовеш?
>> Публика: Алекс.
>> ПРЕДСЕДНИК: Алекс је сада сортирана.
Лева половина, десна половина, шта је финални корак?
Мерге.
Прилично тривијално, па сам ће да се споји у шест,
узети корак уназад, осам, корак уназад.
И сада приметити да је ово користан Такеаваи, шта
је сада истина о левој половини листу, без обзира на то како смо почели?
Се разврстава га.
>> Сада то није разврстани у Велики шеми ствари,
али је сортирана самостално на другу половину.
Шта сад сам на корак ако наставим премотавање како се прича почела?
Сада морам да сортирате десној половини.
Дакле, сада смо пут назад на почетак приче,
и хајде да урадимо то брже.
Па ћу да сортирате десна половина целе листе.
Шта је следећи корак?
Сортирајте левој половини десној половини.
Сортирајте левој половини Лева половина десној половини.
А како се ти зовеш?
>> Публика: Омар.
>> ГОВОРИ: Омар, корак напред, урађено.
Лева половина је сортиран.
А како се ти зовеш?
>> Публика: Крис.
>> ГОВОРИ: Крис, узети корак напред, ви сте сада сортирају.
Шта је кључни корак сада?
Мерге.
Дакле, један ће спојити своје место овде, ако би могао узети корак уназад,
а три ће се узети корак уназад, спојити.
Па левој половини десна половина, сада сортирана.
Искрено, ово алгоритам изгледа као да се троши много више времена него раније,
Али, ако то урадили у реалном времену, ми ћемо види шта Такеаваис ће бити.
Сада сам овде, зар не половина десној половини,
пусти ме само напред и сортирање левој половини.
Корак напред, како се зовеш?
Публика: Рамсеи.
ПРЕДСЕДНИК: Рамсеи је сада сортирана.
Како се зовеш?
>> Публика: Марина.
>> ПРЕДСЕДНИК: Марина је сада сортирано као Па, ако се узме један корак напред.
Кључни корак овде сада споје, ја сам ће да уберу од мојих две листе,
лево и десно.
Пет ће прво доћи, и седам ће доћи следећи.
И опет, ово је намерно.
Чињеница да они узимање кораци напред и назад
треба да представља да ми не можемо урадите алгоритам на месту лако
као балон врсте и избор врсте, и убацивање Сорт где смо управо
задржао замене људе.
Буквално треба некакву допуном папира у којима
да ове људе док ја радим спајање,
а онда да их врати на место.
И то је кључ, јер ја користим Нови ресурс, простор, не само време.
>> ОК, ово је невероватно.
Лева половина је сортиран, десна половина је сортирају, сада када кључни корак спајање.
Како ћу да се споји ова?
Дакле, ако ћете следити мој лева рука и десна рука,
Идем да истакнем своју леву руку на левој половини, моја десна рука
на десној половини, а сада морам да одлучује корак по корак које се спојили у.
Који очигледно прво долази?
Број један.
Па хајде овамо, Овде је наш Сцратцх Пад.
Тако да сада број један, и обавештење шта ћу да урадим са моје десне стране,
Ја ћу да померим десну једну руку корак више до тачке број три,
а сада морам да се Истом одлуком.
И заправо стоје право у фронт Луке одавде ако би могао,
јер ово је наш Сцратцх Пад.
Дакле, ко следи?
Имамо Луке са бројем два или Крис са бројем три.
Очигледно је Луке, број два, па дођи овамо.
>> Али моја лева рука сада ће се се додавати да се укаже на Даррен,
а овде је кључ однесе са спајања, ја ћу да радим ово,
Очигледно, ако вас љубазни о прати логику.
Али руке су ми никада ићи уназад,
што значи да само икада Селим се отишао са мојим процесом спајања,
и то ће бити кључ за Наша анализа у само тренутак.
>> Дакле, сада да завршимо ово брзо.
Дакле, три следи, од четири следи,
а сада Пет следи, онда шест, и седам, а на крају осам.
Осећа као најспорији алгоритма још, али не ако ми заправо
покрените га на исте врсте брзине такта, тако да
говоре, са истим откуцава сат као и раније.
Зашто?
Па, узмимо погледати на крајњи резултат.
>> Хајде да се вратимо овамо, пусти ме повуците демонстрацију визуелно
шта смо урадили.
Зумирање овде, на овом Страница овде, говорећи Фирефок
да желимо да куеуе у овом пољу, хајдемо
кажу балон врсте, са којим сада смо добро упознати,
Избор врста, што је још један прилично једноставан један,
а сада данашња стапања Сорт, која ће бити наш крај врхунца.
Разлог тако трајало много дуже овде са људима и ја вербално је,
Очигледно, ја објашњавам сваки корак.
Али, ако једноставно извршите ову, много као што смо урадили балон врста и селекција
Сортирај не само визуелно, Ватцх колико много ефикасније
Ова задуживање од подела и освајања
може бити када се примењује на скуп података који ни величине осам, али је чак и много,
много већи.
Дајем ти Сорт стопити, једни поред страна са овим другим алгоритама.
Ово ће добити болно брзо, и крај
није посебно врхунца, они само завршити сортирају.
Али кључ је да одузме Погледај колико брже спојити сорт
је, осим ако ти мислиш да сам некако зезам са тобом.
Ако то урадимо једном последњи пут, нека је Релоад тхис, хајде да се вратимо
и изаберите балон врсте, а за сваки случај,
Бирајмо уметање Сорт, само за добру меру.
И овај пут опет, хајдемо бирају стапања врсте, па да
заправо води ове раме уз раме.
>> И то није, у ствари, случајност.
Оно што сам успешно урадио је да сам подељена мој улаз на пола, опет,
и опет, и опет.
И само толико пута можете да поделите унос у пола, лево
и десно.
Шта је формула која се виђати који описује поделу на пола
опет, и опет, и опет, и опет?
>> Публика: Лог Н.
>> ПРЕДСЕДНИК: Лог Н.
Али онда постоји један кључни корак, Овај алгоритам није лог н корака.
Ако је само да се пријавите н кораци, бисмо били у истом проблему
као и раније, где не можемо да будемо Сигуран је све сортирају.
Морате да минимално погледамо н елемената како би били сигурни н елементи су поредани,
иначе то је скок вере.
>> Тако да је минимално дневник н корака, али је Шта је са овом кључном кораку спајању
где сам спојио моје леве и десне половине пола и ходао по бини?
Колико корака је то да се споје?
То је н, али нисам само спајају крајње време.
На сваком од тих угнежђених позива, на сваки тих угнежђених стапања, још увек сортирају.
Ја спојио ова два типа, онда ова два момци, онда ова два момка и тако даље.
>> Тако сам и урадио спајање опет, и опет.
Колико пута?
Тако да сваки пут кад подељено списак на пола, ја сам стапање.
Поделити листу на пола, уради стапање.
Дакле, ако дели листу може да се уради лог н пута,
и спајање на крају узима Н кораци, оно што је можда сада горња
везан на трчању време нашег алгоритма?
н лог н.
>> И заиста, то је оно смо овде постигли.
Тако осећате да визуелно кад видиш Те три ствари води раме уз раме
је н скуаред против Н квадрат против н лог н.
Што суштински ћемо видети, не само данас, већ у будућности,
је много, много брже.
Аплауз за ове момке, Ја ћу их наградити са стреса лопти.
Хајде да прекинемо са радом данас, и видимо се у понедељак.