[Музика свира] Малан ДАВИД: У реду. У реду, добро нам дошли. Дакле, ово је недеља 4, почетак томе, већ. А ви се сећате да је прошле недеље, ми смо ставили кодирају страну за само мало и почели смо да причамо мало више на високом нивоу, о стварима као што су претраживање и сортирање, које иако донекле су једноставне идеје, представник класе проблема да ће почети да решава посебно што почнете да размишљате о финале пројекти и занимљивих решења што Можда ћете морати да реалним проблемима. Сада мехур врста била је једна од најједноставнијих такви алгоритми, и радио тако што ове мале бројеве на листи или у низу врсту Буббле свој пут до врха, а велики број преместите свој пут до крај тог списка. 

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

Дакле, ово ће ићи даље и даље и иди на, и видећете да је већи елементи праве свој пут до право, а мањи елементи пробијајући се на лево. Али, ми смо почели да се квантификује ефикасност, Квалитет овог алгоритма. А ми смо рекли да у најгорем случају, овај алгоритам је отприлике колико корака? 

Дакле, н на квадрат. А шта је н? 

ПУБЛИКА: Број елемената. 

Малан ДАВИД: Тако је н број елемената. И тако ћемо и ово често. Сваки пут када желимо да говоримо о величини проблем или величину улаз, односно количина времена које је потребно да произведе излаз, само ћемо генерализована год улаз је као н. Дакле, назад на Недељи 0, број страница у телефонском именику је н. Број студената у соби је н. Дакле, овде, такође, пратимо Тај образац. 

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

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

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

Дакле, ове теме се јављају у стварном свету. Само пре неколико година, када је одређени Сенатор је кандидовао за председника, Ерик Шмит, у то време директор Гоогле, заправо имао прилику да га интервјуише. А мислили смо да деле овај ИоуТубе цлип за вас овде, ако би могли искрснути обим. 

[ВИДЕО РЕПРОДУКЦИЈА] 

-Сада, сенатор, овде си на Гоогле-у, и ја волим да мислим председништва као разговора за посао. 

[Смех] 

-Сада је тешко добити посао као председника. И ти ћеш кроз суровости сада. Такође је тешко добити посао у Гоогле-у. Имамо питања и тражимо Наши кандидати питања. А ово је од Лари Швимер. 

[Смех] -Ви мислите да се шалим? То је овде. Који је најефикаснији начин да се сортирати милион-два битна цела броја? 

[Смех] 

-Па, ух - 

-Жао ми је. Можда би требало - 

-Не, не, не, не, не. 

-То није - ОК. 

-Мислим да би балон врста бити погрешан пут којим треба ићи. 

[Смех] 

[ЦХЕЕРИНГ и аплауз] 

-Хајде, ко му је рекао ово? ОК. 

[ЕНД ВИДЕО РЕПРОДУКЦИЈА] 

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

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

То је потпуно уназад, зар не? Јер ако је потпуно уназад, морате да урадите много посла. Јер ако сте потпуно уназад, да ћеш наћи Највећи елемент овде, иако она припада тамо. Тако ћеш рећи, у реду, у овај тренутак у времену, ви овде припадате, тако да га остави на миру. 

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

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

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

Ти си број два. Такође припада овде. Број три, још боље, ви овде припадате. Чим се стигне до краја Списак Инсертион сорт, Пер је Псеудокод да смо пролазили кроз усмено последњи пут, готово је. Али, избор врста, насупрот томе, задржао шта ради? 

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

Само да подсетимо, тада, Биг О од н квадрат, видели смо неколико таквих алгоритми до сада. Велико О од н? Шта је алгоритам који би могли се рећи да је Биг О од н? У најгорем случају, потребно је линеарна број корака. 

Ок, линеарно претраживање. А у најгорем случају, где је елеменат тражите када применом линеарне претрагу? 

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

Па, велики о лог н. Нисмо разговарали у детаље о то, али смо видели раније. Шта ради у тзв логаритамске време, у најгорем случају? 

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

Велико О 1. Тако смо могли Биг О од 2, Биг О од 3.. Кад год желите само константан број, Само некако ми само поједностављују да што већи од 1 О. Иако реално ако је потребно 2 или чак 100 корака, ако је то константан број корака, Ми само кажемо Биг О 1. Шта је алгоритам који је у великој О од 1? 

ПУБЛИКА: Проналажење дужину променљиве. 

ДАВИД Малан: Финдинг дужина променљиве? 

ПУБЛИКА: Не, дужина ако је већ сортирају. 

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

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

ПУБЛИКА: [ИНАУДИБЛЕ]. 

Малан ДАВИД: Да. Дакле, то зависи од наше перспективе. Ако заиста мислите да се од улаза у принтф као стринг, и Зато смо мерење величине које улаз по дужини - па назовимо које дужине н, као и - вероватно, иф сама Биг О од н јер то ће вас одвести н корака одштампати сваку од тих н карактера, највероватније. Барем до те мере да претпоставимо да можда је то користи за петљу испод хаубе. 

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

Дакле, шта је омега н на квадрат? Шта је алгоритам који на најбољи случај, још увек је н квадрат кораци? Да? 

ПУБЛИКА: [ИНАУДИБЛЕ]. 

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

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

И то је истина број ствари. На пример, чак бинарни претрага је омега 1. Јер шта ако се стварно проклето среће и цмок-ДАБ у средини Ваша низ је број што тражите? Дакле, можете добити срећан тамо, као добро. 

Ова, на крају, омега н лог н. Дакле н лог н, нисмо баш говори о још, али - 

ПУБЛИКА: Мерге сорт? 

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

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

Тако барем покушати да се фокусира на очи прва три на лево, а затим обједињавање врсту када кликнем Ова зелена стрелица. Али, ја ћу их све води, само да дати вам осећај различитости алгоритми који постоје у свету. Ја ћу пустити ову серију за само неколико секунди. А ако се фокусирате очи - изаберите алгоритам, фокус на њему за само секунди - ви ћете почети да видите образац који се то спроводи. 

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

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

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

Дакле, хајде да погледамо шта спојити врста је заправо све о томе. Кул ствар је да споји врста је управо то. То је, опет, оно што смо се зове Псеудокод, биће Псеудокод Енглески-лике синтаксу. А једноставност је некако фасцинантно. 

Дакле, на улазу од н елемената - тако да само значи, ту је низ. Има н ствари у њему. То је све што ми је рекао. 

Ако је н мање од 2, вратити. Дакле, то је само безначајна ствар. Ако је н мање од 2, онда је очигледно да је 1 или 0, у том случају ствар већ сортира или непостојеће, па се вратим. Нема шта да се уради. Дакле, то је једноставан случај да се уберу искључен. 

Иначе, имамо три корака. Сортирај леву половину елемената, сортирање десна половина елемената, а затим се стапа сортиране половине. Оно што је интересантно овде је да Некако сам пунтинг, зар не? Постоји нека врста кружне дефиниције овом алгоритму. У ком смислу је овај алгоритам је кружна дефиниција? 

ПУБЛИКА: [ИНАУДИБЛЕ]. 

Малан ДАВИД: Да, мој алгоритам за сортирање, двојица његових корака су "врста нешто "И тако. да моли питање, добро, шта ћу користити да сортирате левој половини и десна половина? А лепота је у томе да, иако опет, то је ум-савијање потенцијално део, можете користити исти алгоритам за сортирање леву половину. 

Али, чекај мало. Када сте рекли да сортирате Лева половина, који су два кораци ће бити следећи? Средицемо левој половини лево и десно пола половина леве половине. Проклетство, како да сортирате та два половине, или четврти, сада? 

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

Дакле, права магија у ово алгоритам изгледа у да финални корак, спајање. Та једноставна идеја само спајање ствари, то је оно што се дешава на крају да нам омогући да сортирате низ, рецимо, осам елемената. Дакле, имам још осам лопти до стреса овде, осам комада папира, и један Гоогле стакла - који могу да задржим. 

[Смех] 

Малан ДАВИД: Ако бисмо могли да осам волонтера, и хајде да видимо да ли можемо игра ово, тако. Вау, ОК. Информатика је све забавно. У реду. Па како сте о три, Највећа рука горе. Четири у леђа. А како би било да ти урадим три у овом реду? И четири у напред. Дакле, осам, хајде горе. 

[Смех] 

Малан ДАВИД: Ја сам у ствари не знам шта је то. Да ли је стрес лоптице? Столу лампе? Материјал? Интернет? 

ОК. Па хајде горе. Ко би хтео - даље се појављују. Да видимо. И то вас ставља на локацији - ти си у једној локацији. Ух, чекај мало. 1, 2, 3, 4, 5, 6, 7 - ох, добро. У реду, добро смо. У реду, тако да сви седите, али не и на Гоогле стакла. Дозволите ми да ред ове горе. Како се зовеш? 

МИЦХЕЛЛЕ: Мишел. 

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

У реду, тако да овде имамо низ елемената, и да је низ, по комада папира у овим људима ' руке, тренутно несортиран. 

МИЦХЕЛЛЕ: О, то је тако чудно. 

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

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

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

Дакле, ако сте могли да подигнете свој бројеве тако да можемо да видимо да сте заиста одговара 4, 2, 6, 1, 3, 7, 8. Одлично. Зато ћу покушати да организује ствари, ако ви можете само следите ме. 

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

ПУБЛИКА: Сортирај левој половини. 

Малан ДАВИД: Тако да сада морам да сортирате Лева половина ових момака. Јер опет, претпостављам да у себи Циљ је да се сортира леву половину. Како се то ради? Само пратите упутства, чак и иако ми да радим поново. Дакле, сортирање левој половини. Сада сам сортирање ова два момка. Шта је следеће? 

ПУБЛИКА: Сортирај левој половини. 

ДАВИД Малан: Сортирај левој половини. Па сад ово, ово место овде, је листа величине 1. А како се ти зовеш? 

ДАИСИ ПРИНЦЕЗА: Принцеза Дејзи. 

ДАВИД Малан: Принцеза Дејзи се овде. И тако је већ сортиран, јер списак је величине 1. Шта да урадим следећи? У реду, врати, јер је списак од величина 1, који је мањи од 2. Онда шта је следећи корак? И сада морате да некако Вратите се у вашем уму. 

Сортирај десној половини, што је - како ти је име? 

ЛИНДА: Линда. 

ДАВИД Малан: Линда. И шта сад да радимо имамо листу величине 1? 

ПУБЛИКА: Повратак. 

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

Дакле, ако сте могли устати за само тренутак, ја ћу да вам је потребно, у тренутак, на корак иза столице. А ако Линда, јер је 2 мањи од 4, зашто не око вас на првом месту? Остани тамо. Дакле Линда, око вас на првом месту. 

Сада у стварности је то само низ можемо само да јој се креће у реалном времену из ове столице до овог места. Дакле, замислите да је узео неке константе број корака 1.. А сада - али морамо да вас стави у Прво место овде. 

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

ПУБЛИКА: Десна половина. 

ДАВИД Малан: Сортирај десној половини. Дакле, ви треба да урадите ово, као добро. Дакле, ако можете да устанете за тренутак? А како се ти зовеш? 

Јесс: Јесс. 

ДАВИД Малан: Јесс. У реду, тако да је сада Џес лево половина десној половини. И тако она је листа величине 1. Она је очигледно сортирају. И зовеш? 

МИЦХЕЛЛЕ: Мишел. 

ДАВИД Малан: Мишел је очигледно листа величине 1. Већ је сортиран. Дакле, сада магија се дешава, спајање процеса. Дакле, ко ће прво доћи? Очигледно Мишел. Дакле, ако можете да се позади. Простор имамо на располагању за њу сада је одмах иза ове столице овде. А сада, ако бисте могли да се врате, као и, ми сада имамо, да буде јасно, два половине, а сваки од величине 2 - и само због приказивања, ако сте могао да направи мало простора - једна половина оставила овде, један Десна половина овде. 

Премотавање даље у причи. Шта је следећи корак? 

ПУБЛИКА: Мерге. 

Малан ДАВИД: Тако да сада имамо да се споје. Па добро, тако да сада, на срећу, ми смо само ослободио четири столице. Дакле, ми смо два пута користи више меморије, али можемо дати флип-централна банка између у два потеза. Дакле, који број је на првом месту? Дакле Мицхелле, очигледно. Дакле, доћи до њега и узети Ваше седиште овде. А онда број 2 је очигледно следећи, па си дошао овде. Број 4, број 6. И опет, иако постоји Мало шетње укључени, Заиста, то могу да се тренутно, померањем једног - У реду, добро играо. 

[Смех] 

ДАВИД Малан: И сад смо у прилично добром стању. Лева половина цео улаз је сада сортирају. У реду, ти момци су били користи мог - Како је на крају све девојке на напустио и сви момци на десно? 

У реду, тако да момци "сада окренути. Дакле, ја не ће вас провести кроз ове кораке. Видећемо да ли можемо да поново исти Псеудокод. Ако желите да иде напред и да устане, и ви, да вам дам микрофон. Види ако не могу да понове шта смо урадили овде на Други крај листе. Ко треба да говори први, на основу алгоритма? Па објасните шта радите пре што направите било какве покрете стопала. 

СПИКЕР 1: Добро, па пошто Ја сам Лева половина Лева половина, ја вратити. Зар не? 

ДАВИД Малан: Добро. 

СПИКЕР 1: И онда - 

ДАВИД Малан: Ко ради микрофон иде даље? 

СПИКЕР 1: Следећи број. 

СПИКЕР 2: Ја сам десна половина на левој половини Лева половина, па се вратим. 

ДАВИД Малан: Добро. Вратићете. Па сад шта је следећи за вас двоје? 

СПИКЕР 2: Желимо да видимо ко је мањи. 

ДАВИД Малан: Управо тако. Желимо да се споје. Простор ћемо користити да се споје ви у, иако су очигледно сортирају већ, идемо да прате исти алгоритам. Дакле, ко иде у назад прво? Дакле 3, а затим 7.. А сада иде миц са овим момцима, у реду? 

ПРЕДСЕДНИК 3: Ја сам десна половина Лева половина, а мој је н мање од 1, па ћу само да прође - 

ДАВИД Малан: Добро. 

ПРЕДСЕДНИК 4: Ја сам десна половина десна половина десној половини, а ја сам Такође једна особа, тако да сам ће се вратити. Дакле, сада смо спојити. 

ПРЕДСЕДНИК 3: Дакле да се вратимо. 

Малан ДАВИД: Па ти иди у ледја. Дакле, прво иде 5, онда 8. А сада публика, која је корак морамо сада уназад враћа се у нашим главама? 

ПУБЛИКА: Мерге. 

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

3. иде први. 5. Затим, очигледно. Затим 7, 8 и сада. У реду, а сада смо? 

ПУБЛИКА: Није учињено. 

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

Дакле, сада имамо две листе величине 4. Ако сте могли да устане још једном и да мало простора овде да јасно да је то лева половина оригинала, десна половина оригинала. Ко је први број који смо треба да се повуку у леђа? Мишел, наравно. 

Зато смо ставили Мицхелле овде. А ко има број 2? Број 2 долази на леђа као добро. Број 3? Одлично. Број 4, број 5, број 6, број 7, 8. и број. 

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

СПИКЕР 1: Да ли је н лог разбијање нас у два - дељењем са два, у суштини. 

ДАВИД Малан: Управо тако. Сваки пут смо видели у било ком алгоритму тиме сада, било је то образац поделе, поделе, поделе. И то је обично смањена на нешто што је логаритамске, дневник база 2. Али то заиста може бити било шта, али лог базе 2. 

А шта је са н? Видим да смо некако те подељена момци - подељена вам, подељена, подељена вас, те подељена. Одакле долази крај? 

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

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

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

А зашто је то боље? Па, ако већ знамо тај дневник н је бољи од н - зар не? Видели смо у бинарном претрагом, телефонског именика пример, лог н је дефинитивно боље него линеарно. Значи н пута лог н дефинитивно боље од н пута други н, ака Н на квадрат. И то је оно што смо на крају осећамо. 

Дакле, велики аплауз, ако смо могли, за ове момке. 

[Апплаусе] 

Малан ДАВИД: А твоји поклонима - Можете сачувати бројеве, Ако желите. А твој опроштајни поклон, као и обично. Ох, и ми ћемо вам послати снимак, Мишел. Хвала. У реду. Послужите се стрес лопту. 

И дозволите ми да попните се, у међувремену, наш пријатељ Роб Боуден да понуди мало другачији поглед на ово, јер можете да мислите о овим кораци нешто дешава у другачији начин. У ствари, подешавање за оно Роб се о претпоставља да нам покаже да смо ми већ урадио поделу на велики списак у осам мале листе, сваки од величине 1. 

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

[ВИДЕО РЕПРОДУКЦИЈА] 

-То је то за један корак. За други корак, у више наврата спојити парове листе. 

ДАВИД Малан: Хм. Само звук долази из мог рачунара. Хајде да покушамо поново. 

-Само произвољно пицк који - Сада имамо четири листе. Сазнајте раније. 

Малан ДАВИД: Тако је. 

Спајање-108 и 15, завршавамо са листе 15, 108. Спајање 50 и 4, ми завршити са 4, 50. Спајање 8 и 42, што завршити са 8, 42. И спајање 23 и 16, што завршити са 16, 23. 

Сада све наше листе су величине 2. Приметимо да је сваки од четири листа је сортирана. Дакле, можемо да почнемо спајање пара листа поново. Спајање 15 и 108 и 4 и 50 година, ми смо Прво узми 4, затим 15, па 50, затим 108. Спајање 8, 42 и 16, 23, прво предузети 8, затим 16, па 23, тада 42. 

Тако да сада имамо само две листе величине 4, од којих је сортиран. Дакле, сада ћемо спојити ове две листе. Прво, узмемо 4, онда узимамо 8, онда ћемо узети 15, па 16, па 23, па 42, па 50, па 108. 

[ЕНД ВИДЕО РЕПРОДУКЦИЈА] 

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

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

Дакле, приметите да сте добили ове или половине ове четврти или они осмина проблем да одједном почети да се добар облик. И на крају, можете видети у на самом крају да бам, све се споје заједно. 

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

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

То је убацивање врста. 

[ТОНЕС ПЛАИИНГ] 

ДАВИД Малан: Опет се покушава да убаците сваки елемент у где и припада. То је врста мехур. 

[ТОНЕС ПЛАИИНГ] 

Малан ДАВИД: А можете некако осећају релативно мало раде како се то ради на сваком кораку. То је оно што тедиоуснесс звучи. 

[ТОНЕС ПЛАИИНГ] 

ДАВИД Малан: Ово је избор врста, где смо изабрали елемент желимо од пролази кроз изнова и изнова и изнова и стављајући га на почетку. 

[ТОНЕС ПЛАИИНГ] 

ДАВИД Малан: Ово је обједињавање врста, које заиста можете почети да се осећају. 

[ТОНЕС ПЛАИИНГ] 

[Смех] 

ДАВИД Малан: Нешто што се зове ГНОМЕ врста, које нисмо гледали. 

[ТОНЕС ПЛАИИНГ] 

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

И опет, сећате тог стапања врсту Псеудокод је рекурзивни у смислу да је један од корака Мерге сорт-а да позовете врсту - који је, сам по себи. Али срећом, јер смо задржали врсту позива, односно спајање врсту, конкретно, на мањи и мањи и мањи листа, ми смо на крају извукле са најниже тачке захваљујући ономе што ћемо назвати базни случај, фиксно кодиран случај да је рекао да ако је листа мали, мањи од 2 у том случају, само се врати одмах. Ако нисте имали посебан случај, алгоритам никада не би дно напоље, и заиста би се у Инфините Лооп заиста заувек. 

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

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

Али овај случај је интересантан. Рекурзивни случај је био огранак Псеудокод то рекао друго, врста Лева половина, сортирање право пола, спојити две половине. Дакле, зашто се овај израз представља тај трошак? Па, Т од н само значи Време за сортирање н елемената. И онда на десној страни знак једнакости тамо, Т од н подељено по 2 се односи на цену чега? Сортирање леву половину. Други Т од н подељено са 2 је вероватно се односи на трошкове за сортирате десној половини. 

А онда плус н? Да ли је спајање. Јер, ако имате два листа, један од величина н преко 2 и још један од величине н преко 2, морате да суштински додир сваки од тих елемената, баш као Роб додирну сваки од чаше, а само као што смо указали на сваком од Волонтери на сцени. Тако је н трошак спајања. 

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

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

Али опет, то није довољно. Морамо да зароните дубље. То значи да би се на питање, шта је Т од 8? Па од 8 Т је само 2 Т пута од 4 плус 8. Па, шта је Т од 4? Т од 4 је само 2 пута Т од 2 плус 4. Па, шта је Т од 2? Т од 2 је само 2 пута Т 1 плус 2. 

И опет, ми смо некако све заглављени у овом циклусу. Али, то је о погодити да такозвани основни случај. Јер шта је Т од 1, то тврдимо? 0. Сада коначно можемо уназад. 

Ако је Т 1 је 0, ја сад могу да се вратим још један линија до овог момка овде, и могу прикључите 0 за т 1. Дакле, то значи да она износи 2 пута нула, иначе познат као 0, плус 2. И тако да је цео израз 2. 

Сада ако узмем т 2, чији одговор је 2, прикључите га у средњој линији, Т од 4, то ми даје 2 пута 2 плус 4, 8 тако. Ако сам тада прикључите у 8 на претходну линија, то ми даје 2 пута 8, 16. И ако онда наставите да са 24, додајући у 16, коначно се добија вредност 64. 

Сада је сама по себи врста говори ништа се н нотацији, Велико О, Омега које смо говорили. Али, испоставља се да је 64 заиста 16, величина улаза, лог базе 2 од 16. А ако је ово мало непознато, само сетите се, и вратиће се назад да вас на крају. Ако је ово дневник база 2, то је као 2 подигнут на оно што даје вам 16? Ох, то је 4, тако да је 16 пута 4. 

И опет, то није велика ствар ако то је сада нека врста магловита сећања. Али за сада, да на вери да је 16 лог 16 64. И заиста, са овом једноставном разума проверити, ми смо потврдили - али није доказано формално - да приказују време стапања врста је заиста н лог н. 

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

Сада забавно мало вежбе, ако сте никада урадили - и вероватно не би, јер је некако нормално људи не мисле да се то уради. Али, ако ја идем на гоогле.цом и ако Желим да научим нешто о рекурзије, Ентер. 

[Смех] [Више СМЕХ] ДАВИД Малан: Лош виц полако шири. [Смех] ДАВИД Малан: За сваки случај, ту је. Нисам спелујем погрешно, а ту је и шала. У реду. Објасни људи поред вас ако није то баш увек само кликне. Али рекурзије, уопште, односи процесу позивања функције сама, или уопште, делећи Проблем у нешто што се може решавају појединачни решавањем идентични репрезентативних проблема. 

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

Па како да идемо о радиш ово? Па, дозволите ми да иде напред и написати брзо програму овде. Ја ћу ићи напред и радити ово као следеће. Назовимо овај - шта желимо да позовете ову? 

Заправо, не. Пусти ме уназад. Не желим то да урадим Цлиффхангер још. То ће покварити забаву. Хајде да то урадимо уместо тога. 

Претпоставимо да ја желим да пишем мало програм и да сада обухвата овај Идеја рекурзије. Ја некако имам испред себе тамо. Ја ћу да урадим следеће. 

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

А функција желим да пишем, сасвим Једноставно, то је једна пита упутство за број, а затим се додаје сви бројеви који између број и, рецимо, 0. Дакле, прво ћу да наставим и прогласи инт н. Онда сам неки код да копирате Употребили смо неко време. Док је нешто тачно. Вратићу се на то за који тренутак. 

Шта желите да урадите? Хоћу да кажем принтф позитиван цео молим. А онда ћу да кажу н добија се инт. Па опет, неки општенаменским код које смо користили. И ја ћу да урадим ово док је н мање од 1. Дакле, ово ће обезбедити да корисник ми даје позитиван цео број. 

А сада ћу да урадим следеће. Желим да саберете све бројеве између 1 и н и, или 0 и н, еквивалентно, да се укупан збир. Дакле, велики симбол Сигма Можда се сећате да сте. Дакле, ја ћу да урадим ово први позивом функција се зове сигма, пролази га у Н, а онда ћу да принтф кажу, одговор је ту. 

Дакле укратко, ја се и инт од корисника. Ја би да је то позитивно. Изјављујем променљиву зове одговор типа инт и продавница у њему повратка Вредност СИГМА, пролази у н као улаз. И онда штампају тај одговор. 

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

А онда ћу да наставим и урадили веома итеративно. Ја ћу да урадим овакве старе школе, а ја ћу да наставим и кажем да ћу да прогласи суму да буде 0. Онда ћу имати за петљи инт - и пусти ме да радим да поклапају са нашом код дистрибуција, тако да имате копију код куће. инт добија на 1 до И мањи или једнак м. И плус плус. И онда унутар петље за то - скоро смо стигли - Збир добија суму плус 1. А онда ћу да врати суму. 

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

Ако сада наставити причу, како се спроводи сигма? Ја предлажем да се спроведе на следећи начин. Прво, мало испитивање грешака бити сигурни да корисник не зеза са мном и пролази у нека негативна или 0 вредности. Онда сам декларишете променљиву под именом сумирамо и поставите га на 0. 

А сада почињу да се крећу од и једнако 1 све до и укључујући м, јер желим да укључи све бројевима од један кроз М, инклузиван. И унутар петље за ово, само радим Збир добија све што је сада, плус вредност и. Плус вредност и. 

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

Нажалост, ово је код неће још саставити. Ако ми направите сигма 0, како ћу Ја ћу се драо на? Шта ће то не свиђа? 

ПУБЛИКА: [ИНАУДИБЛЕ]. 

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

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

Тако да сада дозволите ми да обришете екран. Римејк сигма 0. Све се чини да проверите. Дозволите ми да покренете Сигма 0. Позитиван Интер. Ја ћу му дати број 3. да га једноставно. Тако да би требало да ми дате 3 плус 2 плус 1, 6 тако. Ентер, и заиста сам се 6. 

Ја могу да урадим нешто веће - 50, 12, 75. Баш као тангенте, ја ћу да урадим нешто смешно као заиста велики број, Ох, то заправо испало - ех, ја не мислим да је у праву. Да видимо. Да заиста дирајте је. 

То је проблем. Шта се дешава? Код није тако лоше. Још увек је линеаран. Звиждање је добар ефекат, мада. Шта се дешава? 

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

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

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

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

Дакле, ја сам заправо - дозволите ми да сачувате овај фајл са различитим бројем верзије. Позваћемо ову верзију 1 уместо 0. А ја тврдим да сам у ствари могу реимплемент то у овој врсти ум-савијање начин. 

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

Друго - приметити шта ћу да урадим. Иначе ћу вратити М плус - шта је сигма од м? Па, сигма м од плус минус 1 м, плус минус 2 м, плус минус 3 м. Не желим да пишем све то. Зашто не само Пунт? Рекурзивно позив себе са благо мањи проблем, зарез, и за данас? 

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

ПУБЛИКА: [ИНАУДИБЛЕ]. 

ДАВИД Малан: 23 до 26, који ако је мој услов. Јер оно што је лепо у вези одузимање овде, јер сам задржати дистрибуирањем сигма мањи проблеми, мањи проблеми, мањи - то није пола величине. То је само корак беба мања, али то је у реду. Јер на крају, ми ћемо радити наш пут до 1 или 0. И када смо погодили 0, сигма није ће да се зовем. То ће се одмах вратити 0.. 

Дакле ефекат, ако некако ветра ово у вашем уму, јесте да додате М Плус минус 1 м, плус минус 2 м, м плус минус 3, плус тачка, тачка, тачка, м минус м, на крају вам даје 0, а Ефекат је на крају да додате све ове ствари заједно. Дакле, ми нисмо, са рекурзије, решила проблем који смо није могао да реши пре. Заиста, 0 верзија овога, и сваки Проблем до сада, је растворљив са само користи за петље или док петље или сличних схватања. 

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

Али, то сам урадио Цлиффхангер Желим да нас оставите на било ово. Пусти ме да идем напред и отвори се датотека из - заправо, пусти ме и урадите веома брзо. Пусти ме да идем напред и предложити следеће. Међу кода данас је овде овај фајл. Овај овде, носвап. 

Дакле, ово је мало глупо програм који Ја шлаг који се тврди да следеће. У главни, то прво изјављује инт к позвао и додељује га вредност 1. Онда искаже инт и и додељује му вредност 2. Онда се исписује шта кии је. Онда каже, замене, Дот Дот Дот. 

Затим тврди да се позивање функција зове замену, пролази у к и г, идеја која се надамо да кии ће се вратити другачије, супротно. Онда тврде заменили! са знаком узвика. Онда се исписује к и и. 

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

Али ја тврдим да када сам покренути ово кода, као што ћу ја сада - дозволите ми да иде напред и налепите га овде. Зваћу ову носвап.ц. И као што име сугерише, ово није ће бити одговарајући програми. Направите носвап / бр свап.. к је 1, и 2, замене, заменили. к је 1, и 2. Ово је фундаментално погрешно, чак и Иако ово изгледа савршено разумно мене. И постоји разлог, али ми нисмо ће да открије разлог још увек. 

За сада други Цлиффхангер сам желела да вас оставим са је ово, Најава врста на купон кодови. Наше иновације у касним данима ове године изазвао је не-тривијалан број питања, што је било није наша намера. Намера ових купон кодови, при чему, ако ти део проблема сет рано, чиме се добија још један дан, је заиста да помогне ви помоћи сами почети рано, сорт од стране инцентивизинг вас. Помаже нам да дистрибуирају оптерећење преко Радно време боље, тако да у питању је врста добитку. 

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

Али, ово је више убедљив. (ФАЗА ВХИСПЕР) И ти људи одлазе рано це зажалити. Пошто су људи на балкону. Извињавам се унапред на људе на балкон из разлога који ће бити јасно за који тренутак. 

Дакле, имамо среће да има један од ЦС50 је бивши шеф наставних момци на фирма се зове дропбок.цом. Они су великодушно поклонио купон код овде за оволико простора, што је горе од Уобичајене 2 гигабајта. Дакле, оно што сам мислио да ће то учинити на коначна напомена је да мало одавање, при чему у само једном тренутку, ми ћемо открити победник и ко има купон код који можете да посетите њихове сајт, упишите га у, и воила, добити много више простора за своје Дропбок апарата и за ваше личне датотеке. 

И први, који би желели да учествују на овом цртежу? У реду, сада да чини још забавнијим. Особа која прима овај 25-гигабајт купон код - што је далеко више убедљив него касно дана сада, можда - је онај који седи на врху седиште јастук испод које се налази да купон код. Сада можете погледати испод Ваш јастук седишта. 

[ВИДЕО РЕПРОДУКЦИЈА] 

-Један, два, три. 

[СЦРЕАМИНГ] 

-Имате ауто! Добијете ауто! 

ДАВИД Малан: Видећемо ти у среду. 

-Имате ауто! Добијете ауто! Добијете ауто! Добијете ауто! Добијете ауто! 

ДАВИД Малан: Балкон људи, долазе доле на фронт, где имамо екстра. 

-Сви добијају свој ауто! Свако добије ауто! 

[ЕНД ВИДЕО РЕПРОДУКЦИЈА] 

НАРАТОР: На следећем ЦС50 - 

ПРЕДСЕДНИК 5: О боже боже боже боже бозе бозе бозе бозе бозе бозе - 

[Укелеле плаис]