[Музыка Прайграванне] DAVID малая: Добра. Добра, з вяртаннем. Так што гэта 4-я тыдзень, пачатак яго, ужо. І вы памятаеце, што на мінулым тыдні, мы ставім код адведзеных для толькі трохі і мы пачалі гаварыць трохі больш высокім узроўні, пра такія рэчы пошук і сартаванне, якая хоць і некалькі простых ідэй, з'яўляюцца прадстаўнік класа задач Вы пачнеце вырашаць асабліва як вы пачынаеце думаць аб канчатковым праекты і цікавыя рашэнні, якія вы магчыма, прыйдзецца рэальных праблем. Цяпер пузырьковый сартавання быў адным з самых простых такія алгарытмы, і гэта працаваў пры наяўнасці гэтых невялікіх колькасцях ў выглядзе спісу або ў выглядзе масіва Бурбалка іх шлях да вяршыні, і вялікія колькасці перамясціць свой шлях да Да канца гэтага спісу. І нагадаць, што мы маглі прадстаўляць пузырьковый сартаванне трохі нешта накшталт гэтага. Такім чынам, дазвольце мне ісці наперад і націсніце кнопку Пуск. Я папярэдне пузырьковый сартавання. А калі ўспомніць, што вышэй за сіні лініі ўяўляюць вялікія нумары, невялікія Сінія лініі ўяўляюць сабой невялікія нумары, а мы праходзім праз гэта зноў і зноў і зноў, параўноўваючы два бара побач адзін іншыя ў чырвоным, мы збіраемся, каб памяняць вялікі і мінімальным, калі яны выйшлі з ладу. Так што гэта будзе працягвацца і працягвацца і ісці на, і вы ўбачыце, што чым больш элементы ўносяць свой шлях да направа, а больш дробныя элементы з'яўляюцца прабіраюцца налева. Але мы пачалі колькасна эфектыўнасцю, Якасць гэтага алгарытму. І мы сказалі, што ў горшым выпадку, гэты алгарытм ўзяў прыкладна колькі крокаў? Такім N квадраце. І тое, што было N? АЎДЫТОРЫЯ: колькасць элементаў. DAVID малая: Так было N лік элементаў. І таму мы будзем рабіць гэта часта. Кожны раз, калі мы хочам казаць аб памерах праблема ці памер ўваход, або колькасць часу, неабходнае для атрымання выходных, мы проста абагульненай ўсё ўваход як н. Такім чынам, вернемся да тыдня 0, колькасць старонак У тэлефоннай кнізе была N. Колькасць студэнтаў ў пакоі з. Так і тут, мы ідзём гэтай мадэлі. Цяпер н квадрат не з'яўляецца асабліва хутка, так што мы паспрабавалі зрабіць лепш. І так мы глядзелі на пару іншыя алгарытмы, сярод якіх былі сартаванне выбарам. Так што выбар быў Сартаваць крыху па-іншаму. Гэта было амаль просты, я адважуся сказаць, якога я пачаў у пачатку Спіс нашых валанцёраў, і я проста зноў і зноў і зноў прайшоў праз спісе, выскубанне найменшай элемента за адзін раз і пакласці яго ці яе ў пачатку спісу. Але і гэта, як толькі мы пачалі думаць праз матэматыку і больш карціну, думаў пра тое, колькі разоў Я ішоў назад і наперад і назад і наперад, мы сказалі, у горшым выпадку, Выбар роду таксама было што? N ў квадрат. У цяперашні час у рэальным свеце, яна можа на самай справе быць хутчэй. Таму што зноў жа, у мяне не было трымаць адступае, як толькі я сартаваў драбнюткіх элементаў. Але калі мы думаем пра вельмі вялікіх N, і Калі вы як бы зрабіць з матэматыкі як Я зрабіў на борце, з N квадрат мінус нешта, усё астатняе Акрамя таго, N квадратаў, як толькі N становіцца сапраўды вялікім, ня мае вялікага значэння, як шмат. Так як камп'ютэрныя навукоўцы, мы накшталт як закрываць вочы на ​​меншыя фактары і фокус толькі на фактар Выраз, якое збіраецца зрабіць Самая вялікая розніца. Ну, нарэшце, мы глядзелі на сартаванне ўстаўкамі. І гэта было блізкія па духу, але а не праходзіць праз итеративно і выбраць найменшы элемент па адным час, я замест гэтага узяў руку, што я быў нанесены, і я вырашыла, усё Добра, ты тут застанешся. Затым я перайшоў да наступнага элемента і вырашыў, што ён ці яна належала тут. А потым я пераехаў далей і далей. І я мог бы, каб, па шляху, перайсці гэтыя хлопцы для таго, каб вызваліць месца для іх. Так, каб быў свайго роду ментальны разварот адбору накшталт тых, што мы называецца сартаванне ўстаўкамі. Такім чынам, гэтыя тэмы ўзнікаюць у рэальным свеце. Усяго некалькі гадоў таму, калі пэўныя Сенатар быў балатавацца на пасаду прэзідэнта, Эрык Шміт, у той час генеральны дырэктар Google, на самай справе мелі магчымасць узяць у яго інтэрв'ю. І мы падумалі, што мы падзелім гэтую YouTube Заціск для вас тут, калі б мы маглі павярнуць уверх гучнасці. [Прайграванне відэа] -Зараз, сенатар, вы тут, у Google, і мне падабаецца думаць прэзідэнцтва як сумоўе. [Смяецца] -Зараз гэта цяжка атрымаць праца ў якасці прэзідэнта. І вы праходзіце суровасці цяпер. Гэта таксама цяжка ўладкавацца на працу ў Google. У нас ёсць пытанні, і мы просім нашым кандыдатам пытанні. І на гэты раз ад Лары Швімэр. [Смяецца] -Вы, хлопцы, думаеце, я жартую? Гэта прама тут. Што з'яўляецца найбольш эфектыўным спосабам сартаваць мільён дзвесце-разрадных цэлых лікаў? [Смяецца] -Ну, ну - -Прабач. Можа быць, мы павінны - -Не, не, не, не, не. -Гэта не - ОК. -Я думаю, што пузырьковый сартаванне б быць няправільны шлях. [Смяецца] [Вітаюць і апладысменты] -Давай, які сказаў яму гэта? ОК. [КАНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] DAVID малая: Так што ў вас ёсць. Такім чынам, мы пачалі даць колькасную ацэнку гэтым працуе раз, так бы мовіць, з чым-то называецца асімптатычнага абазначэнне, якое проста спасылаючыся на наш выгляд павароту закрываць вочы на ​​гэтыя фактары і менш Толькі гледзячы на ​​час працы, прадукцыйнасць гэтых алгарытмаў, як н становіцца сапраўды вялікім з цягам часу. І таму мы ўвялі вялікую О. І Big O прадстаўлена тое, што мы думалі, як верхнюю мяжу. А на самай справе, Бары, мы можам знізіць , Чым мікрафон трохі? Мы думалі пра гэта з'яўляецца верхняй мяжой. Так Big O п квадрат азначае, што ў горшым выпадку, нешта накшталт Выбар роду возьме п квадрат крокаў. Ці нешта накшталт сартавання ўстаўкамі б квадрат N крокаў. Зараз за тое, як ўстаўкі , Глядзіце, якое было ў горшым выпадку? Дадзены масіў, што самае горшае магчымыя сцэнары, якія могуць апынуцца апынецеся перад? Гэта цалкам у зваротным кірунку, ці не так? Таму што, калі гэта зусім у зваротным кірунку, што вам трэба зрабіць шмат працы. Таму што, калі вы цалкам у зваротным кірунку, Вы збіраецеся знайсці найбуйнейшым элементам тут, хоць ён належыць там. Так што вы збіраецеся сказаць, усё правільна, па дадзены момант часу, ты тут застанешся, так што вы пакінуць яго ў спакоі. Тады вы разумееце, чорт пабяры, я павінен перамясціць гэты трохі меншы элемент Злева ад вас. Тады я павінен зрабіць гэта зноў і зноў і зноў. І калі б я хадзіў туды-сюды, вы ўладзіць адчуваю прадукцыйнасць , Што алгарытм, таму што я ўвесь час перакартоўка ўсе астатнія ўніз у масіў, каб вызваліць месца для яго. Так што гэта ў горшым выпадку. У адрозненне ад гэтага - і гэта было захапляльным апошні раз - мы казалі, што сартаванне ўстаўкамі быў амега чаго? Які самы лепшы выпадак ход час сартавання ўстаўкамі? Так гэта на самай справе п. Гэта быў пусты, што мы пакінулі на дошцы апошні раз. І гэта амега п, дык чаму? Ну, у самым лепшым выпадку, што сартаванне ўстаўкамі будзе перададзены? Ну, спіс, які ўсё цалкам адсартаваны ўжо, мінімальная праца. Але тое, што чароўнае ў тым, сартавання устаўкай з'яўляецца тое, што, паколькі ён пачынаецца тут і вырашае, О, ты колькасці Адзін з іх, ты тут застанешся. Ах, якое шчасце. Ты нумар два. Вы таксама належаць тут. Нумар тры, яшчэ лепш, Вам варта да нас. Як толькі ён трапляе ў канцы Спіс, на сартаванне ўстаўкамі ў псевдокоде , Што мы ішлі ў вербальна Апошні раз, гэта робіцца. Аднак выбар выгляду, наадварот, працягваў рабіць тое, што? Працягваў ісці па спісе зноў і зноў і зноў. Паколькі ключавое разуменне было толькі Як толькі вы глядзелі ўсе шляхі да канцы спісу вы можаце быць упэўненыя што элемент быў абраны Сапраўды ў цяперашні час найменшы элемент. Такім чынам, гэтыя розныя псіхічныя мадэлях да атрымання некаторых вельмі рэальным адрозненні для нас, а таксама гэтыя тэарэтычныя асімптатычнай адрозненні. Так проста, каб рэзюмаваць, то, Big O п квадрат, мы бачылі некалькі такіх алгарытмаў да гэтага часу. Big O п? Што алгарытм, здольны назваць Big O п? У горшым выпадку, яна займае лінейны лік крокаў. Добра, лінейны пошук. А ў горшым выпадку, калі гэта элемент, які вы шукаеце, калі ўжыванні лінейнага пошуку? Добра, у горшым выпадку, гэта нават не там. Ці ў другім горшым выпадку, гэта ўсё шляху ў рэшце рэшт, які плюс-мінус адзін крок розніцы. Такім чынам, у рэшце рэшт, мы можам сказаць, што гэта лінейная. Big O п будзе лінейны пошук, таму што ў горшым выпадку, Элемент нават не там, ці гэта ўсё шляху ў канцы. Ну, Big O часопіса н. Мы не казалі вельмі падрабязна аб гэта, але мы бачылі гэта раней. Што працуе ў так званы Лагарыфмічны часу, у горшым выпадку? Так, так што бінарны пошук. І бінарнага пошуку ў горшым выпадку можа мець элемент дзесьці сярэдзіне, ці ў іншым ў масіве. Але вы толькі знайсці яго, як толькі вы падзяліць спіс у два разы, у палова, напалам, напалам. А потым вуаля, што яна ёсць. Ці, зноў жа, горшым выпадку, гэта нават не там. Але вы не ведаеце, што гэта не ёсць пакуль накшталт не дасягне, што ў мінулым самы ніжні элементаў ўдвая і скарачэнне ўдвая і ўдвая. Big O 1. Магчыма, мы можам Big O 2, Big O 3. У любы час вы хочаце проста пастаяннае лік, мы проста як быццам проста спрасціць што Big O 1. Хоць, калі рэальна, яна займае 2 ці нават 100 крокаў, калі гэта пастаяннае лік крокаў мы проста скажам Big O 1. Што гэта алгарытм У Big O 1? АЎДЫТОРЫЯ: Вызначэнне даўжыні зменнай. DAVID малая: Пошук Даўжыня зменнай? АЎДЫТОРЫЯ: Не, даўжыня калі ён ужо адсартаваны. DAVID малая: Добра. ОК, так што знайсці нешта даўжыню калі даўжыня што нешта накшталт масіў, захоўваецца ў некаторай зменнай. Таму што вы можаце проста прачытаць зменную, або раздрукаваць зменнай ці проста наогул доступ да гэтай зменнай. І вуаля, што патрабуе пастаяннага часу. У адрозненне ад гэтага, думаю, назад у добрым стане. Успомніце першы тыдзень C, выкліку проста Е і друку нешта на экране, магчыма, пастаянны час, так ён проста прымае некаторы лік цыклаў працэсара, каб паказаць , Што тэкст на экране. Ці чакаць - ці не так? Як яшчэ мы можам мадэляваць прадукцыйнасць Е? Хто-небудзь хацеў бы не пагадзіцца, што Можа быць, гэта не зусім пастаяннае час? У якім сэнсе можа Е бяжыць Час, фактычна выводзячы радок на экране, няхай гэта будзе акрамя сталай. АЎДЫТОРЫЯ: [неразборліва]. DAVID малая: Да. Так што гэта залежыць ад нашага пункту гледжання. Калі мы на самай справе думаем пра ўваход Е як радкі, а Таму мы вымяраем памер гэтага Увод яго даўжыня - таму назавем што даўжыні N, а таксама - Можна сцвярджаць, што Е з'яўляецца самай вялікай O п таму што ён збіраецца распачаць крокі вы н раздрукаваць кожную з гэтых N знакаў, хутчэй за ўсё. Па крайняй меры, у той ступені, што мы мяркуем што, магчыма, ён выкарыстоўвае для завесы пад капотам. Але мы павінны былі б глядзець на гэта код лепш зразумець яго. І сапраўды, як толькі вы хлопцы пачынаюць Аналізуючы ўласныя алгарытмы, вы будзеце літаральна зрабіць менавіта гэта. Сартаваць вочнага яблыка код і думаць Пра нас - усё ў парадку, у мяне ёсць гэтая пятля Тут ці ў мяне ёсць укладзеныя цыклы тут, што будзе рабіць рэчы N N раз, і вы можаце сартаваць розуму свой шлях праз код, нават калі гэта псевдокод, а не рэальная код. Так што пра амега N квадратаў? Тое, што было алгарытм, у лепшым выпадку, усё яшчэ ўзяў квадрат N крокаў? Да? АЎДЫТОРЫЯ: [неразборліва]. DAVID малая: Так Сартаваць выбару. Таму што ў гэтым праблема сапраўды паменшаны да таго, што зноў жа, я не ведаю, Я знайшоў бягучага меншага, пакуль Я праверыў усе праклятыя элементаў. Так амега, скажам, п толькі што прыйшоў з адным. Сартаванне ўстаўкамі. Калі спіс здараецца быць адсартаваныя ўжо, у лепшым выпадку мы проста павінны каб зрабіць адзін праход праз яго, і ў гэты момант мы ўпэўненыя. І затым, што можна сказаць лінейныя, напэўна. Як наконт амега 1? Што, у лепшым выпадку, можа заняць пастаяннае лік крокаў? Так лінейны пошук, калі вы проста шанцуе і элемент, які вы шукаеце знаходзіцца ў самым пачатку спісу, калі гэта тое, дзе вы пачынаеце вашу лінейнага абыходу гэтага спісу. І гэта дакладна для некалькі рэчаў. Напрыклад, нават двайковы пошук амега 1. Таму што, калі вы атрымліваеце сапраўды праклятае пашанцавала, і дотык густу ў сярэдзіне вашага масіва з'яўляецца лік Вы шукаеце? Такім чынам, вы можаце атрымаць пашанцавала там, а таксама. Гэты, нарэшце, амега N § п. Такім N часопіс N, нам, сапраўды, казаць аб пакуль няма, але - АЎДЫТОРЫЯ: Сартаванне зліццём? DAVID малая: сартаванне зліццём. Гэта было захапляльным апошняга часу, дзе мы прапанавалі, і мы паказалі візуальна, то ёсць алгарытмы. І сартаванне зліццём толькі аднаго такога Алгарытм, які прынцыпова хутчэй чым некаторыя з гэтых іншых хлопцаў. На самай справе, зліццё кароткі не толькі ў лепшым выпадку N часопіс N, у горшым Выпадак п § п. І калі ў вас ёсць гэта супадзенне Амега і Big O з'яўляецца адно і тое ж? Мы можам рэальна апісаць гэта як тое, што называюцца тэта, хоць гэта трохі радзей. Але гэта проста азначае, што два скачка У гэтым выпадку тыя ж самыя. Так сартавання зліццём, што ж гэта сапраўды зводзяцца да для нас? Ну, успомніце матывацыі. Дазвольце мне падцягнуць анімацыю, якое Мы не глядзелі на апошні раз. Гэта адно, тая ж ідэя, але гэта крыху больш. І я збіраюся ісці наперад і адзначыць, першае - у нас ёсць на сартаванне ўстаўкамі левым верхнім куце, а затым выбар роду, пузырьковый сартаванне, некалькі іншых відаў - абалонкі і хутка, - што мы яшчэ не казалі о, і кучу і сартаванне зліццём. Так па крайняй меры паспрабаваць засяродзіцца на вашых вачах тройку на левай, а затым сартаванне зліццём, калі я націскаю гэтай зялёнай стрэлкай. Але я дазволю ўсе яны запускаюцца, проста каб даць вам адчуванне разнастайнасці Алгарытмы, якія існуюць у свеце. Я збіраюся дазволіць гэтай перспектыве ўсяго за некалькі секунд. І калі вы засяродзіцца вочы - выбраць Алгарытм, засяродзіцца на ім на працягу ўсяго секунд - вы пачынаеце бачыць карціна, што гэта ажыццяўленне. Сартаванне зліццём, заўважце, робіцца. Кучы сартавання, хуткай сартавання, Shell - так што здаецца, мы ўвялі тры горшых алгарытмаў на мінулым тыдні. Але гэта добра, што мы сёння тут, каб паглядзець на сартавання зліццём, якое з'яўляецца адным з больш лёгкія, каб глядзець на, нават хоць яна, верагодна, будзе выгінацца ваш розум толькі трохі. Тут мы можам бачыць, як шмат Выбар роду смокча. Але, з іншага боку, гэта сапраўды лёгка ажыццявіць. І можа быць, для P набор 3, гэта адна з Алгарытмы вы вырашылі рэалізаваць для стандартнага выдання. Выдатна падыходзіць, зусім правільна. Але зноў жа, як н становіцца вялікім, калі вы выбраць для рэалізацыі больш хуткі алгарытм падабаецца сартавання зліццём, шанцы ў буйных і больш уваходаў, код з'яўляецца проста збіраецца працаваць хутчэй. Ваш сайт будзе працаваць лепш. Вашы карыстальнікі будуць больш шчаслівым. І так ёсць гэтыя эфекты фактычна даючы нам некаторыя глыбокія думкі. Такім чынам, давайце паглядзім, што зліццё Сартаваць самай справе ўсё аб. Самае выдатнае ў тым, што зліццё роду з'яўляецца менавіта гэта. Гэта, зноў жа, тое, што мы назвалі псевдокод, псевдокод істота Англійская-падобны сінтаксіс. І прастата роду займальным. Так на ўваходзе з п элементаў - так, каб проста азначае, вось масіў. У гэтага ёсць N рэчы ў ім. Гэта ўсё, што мы кажам, што там. Калі N менш 2, вярнуцца. Так што гэта проста трывіяльны выпадак. Калі N менш 2, то, відавочна, гэта 1 або 0, у гэтым выпадку рэч ўжо адсартаваны або неіснуючыя, так што проста вярнуцца. Там няма нічога, каб зрабіць. Так што гэта просты выпадак, каб абрываць. У адваротным выпадку, у нас ёсць тры этапы. Сартаваць левую палову элементаў, адсартуйце Правая палова элементаў , А затым аб'яднаць адсартаваны за палову. Што цікава тут тое, што Я накшталт понтировавшего, праўда? Там накшталт кругавой азначэнні для гэтага алгарытму. У якім сэнсе гэтага алгарытму Вызначэнне кругавой? АЎДЫТОРЫЯ: [неразборліва]. DAVID малая: Так, мой алгарытм сартавання, двух сваіх крокаў "выгляд што-то. "І так, што ўзнікае Пытанне, ну, што я збіраюся выкарыстоўваць для сартавання левай паловы а правая палова? І прыгажосць у тым, што нават пры тым, зноў жа, гэта галюцынагенных частка патэнцыйна, вы можаце выкарыстоўваць той жа Алгарытм для сартавання левай палове. Але пачакайце хвіліну. Калі вы сказалі, каб адсартаваць Левая палова, якія дзве крокаў будзе далей? Мы разбярэмся з левай паловы Левая палова і права палова левай паловы. Блін, як мне адсартаваць гэтыя два паловы і чвэрці, у цяперашні час? Але гэта не страшна. У нас ёсць алгарытм сартавання тут. І хоць вы можаце турбавацца першае гэта накшталт бясконцага завесы, гэта цыкл, які ніколі не скончыцца - ён збіраецца спыніцца, як толькі тое, што адбываецца? Пасля п менш 2. Якія ў канчатковым выніку адбудзецца, таму што калі вы працягвайце дзяліць на два і зніжэнне ў два разы скараціць удвая гэтыя паловы, безумоўна, ў рэшце рэшт вы будзеце ў канчатковым толькі з 1 або 0 элементаў. У гэты момант, гэты алгарытм кажа, што вы зрабілі. Такім чынам, сапраўдная магія ў гэтым Алгарытм, здаецца, у гэты апошні крок, зліваючыся. Гэта простая ідэя проста зліцця двух рэчы, гэта тое, што ў канчатковым рахунку будзе , Каб дазволіць нам адсартаваць масіў, скажам, восем элементаў. Так што ў мяне яшчэ восем шароў да стрэсу Тут, восем паперкі, і адзін Google шкла - якія я атрымліваю, каб захаваць. [Смяецца] DAVID малая: Калі б мы маглі прыняць восем добраахвотнікаў, і давайце паглядзім, калі мы можам гуляць у гэтую, такім чынам. Нічога сабе, ОК. Інфарматыка становіцца весела. Добра. Так, як вы трое найбуйнейшых руку там. Чатыры ў спіну. А як наконт зробім Вам тры ў гэтым шэрагу? І чатыры ў пярэдняй часткі. Такім чынам, вы восем, падымайся. [Смяецца] DAVID малая: Я на самой справе не ўпэўнены, што гэта такое. Гэта стрэс шароў? Настольныя лямпы? Матэрыял? У інтэрнэце? ОК. Так што прыязджайце і вышэй. Хто хацеў - працягваюць паступаць. Давайце паглядзім. І гэта ставіць вас у месцы - Вы знаходзіцеся ў адным размяшчэння. Ой, пачакай хвілінку. 1, 2, 3, 4, 5, 6, 7 - о, добра. Добра, што мы добрыя. Добра, ва ўсіх ёсць месца, але не на шкле Google. Дазвольце мне ў чаргу гэтыя ўверх. Як цябе завуць? Мішэль: Мішэль. DAVID малая: Мішэль? Добра, вы атрымліваеце магчымасць выглядаць Гуляйце і выйгравайце, калі гэта нармальна. Ну, я таксама, я мяркую, на імгненне. Усе правы, у рэжыме чакання. Мы спрабуем, каб прыдумаць выпадкі выкарыстання Google шкла, і мы думаў, што гэта было б цікава, каб проста рабіць гэта калі людзі на сцэне. Мы запішам свеце з іх пункту гледжання. Добра. Мала верагодна, што Google прызначана. Добра, калі вы не супраць насіць гэтым на працягу наступнага нязручны хвілін гэта было б вельмі добра. Добра, так што мы маем тут справу з масівам элементамі і масіва, згодна з паперкі ў гэтых людзей " рукі, у цяперашні час адсартаваныя. Мішэль: О, гэта так дзіўна. DAVID малая: Гэта ў значнай ступені выпадковым. І праз хвіліну, мы збіраемся, каб паспрабаваць для рэалізацыі сартавання зліццём разам і паглядзець, дзе, што ключавое разуменне ёсць. І трук тут з сартавання зліццём з'яўляецца тое, што мы пакуль не мяркуецца. Мы на самой справе патрэбна дадатковае прастору. Так што ж адбываецца, што асабліва цікавае ў гэтым тое, што гэтыя хлопцы, збіраецеся перасоўвацца трохі трохі, таму што я буду лічыць, што ёсць дадатковая масіў прасторы, скажам, адразу за імі. Так што калі яны за свае крэслы, гэта другаснае масіва. Калі яны сядзяць тут, гэта першаснага масіва. Але гэта рэсурс, які мы маем не выкарыстоўвала да гэтага часу з бурбалкай сартаванне, з выбарам выгляду, з сартаванне ўстаўкамі. Нагадаем, на мінулым тыдні, усё проста выгляд змешваюцца на месцы. Яны не выкарыстоўвалі любы дадатковай памяці. Мы стварылі месца для людзей перамяшчэнне людзей вакол. Так што гэта ключавое разуменне, таксама. Там ёсць кампраміс, у цэлым у камп'ютэрныя навукі, рэсурсаў. Калі вы хочаце паскорыць нешта як час, вы збіраецеся прыйдзецца заплаціць цану. І адна з гэтых коштаў вельмі часта прасторы, аб'ём памяці або жорсткага дыскавай прасторы, які вы выкарыстоўваеце. Ці, калі шчыра, колькасць праграміст часу. Колькі часу гэта зойме ў вас, чалавека, у мэтах практычнага ажыццяўлення яшчэ некалькі складаны алгарытм. Але на сённяшні дзень, кампраміс час і прастору. Так што, калі вы, хлопцы, маглі б проста падніміце нумары, каб мы маглі бачыць, што Вы Сапраўды адпаведны 4, 2, 6, 1, 3, 7, 8. Выдатна. Так што я збіраюся паспрабаваць, каб арганізаваць рэчы, калі вы, хлопцы, можаце проста ідзі за мной тут. Так што я збіраюся ажыццявіць, па-першае, Першы этап псевдокода, які на ўваходзе элементаў п, калі п менш за 2, то вяртаецца. Відавочна, што не прымяняюцца, таму мы рухацца далей. Так адсартаваць левую палову элементаў. Значыць, я збіраюся засяродзіць сваю увагу на імгненне на гэтых чацвёра хлопцаў тут. Добра, што я наступны рабіць? АЎДЫТОРЫЯ: Сартаваць левую палову. DAVID малая: Так што цяпер у мяне ёсць, каб разабрацца Левая палова гэтых хлопцаў. Таму што зноў жа, выкажам здагадку, да сябе Мэта складаецца ў сартаванні левую палову. Як вы гэта зрабілі? Проста выконвайце інструкцыі, нават хоць мы робім гэта зноў. Так адсартаваць левую палову. Цяпер я сартаванне гэтых двух хлопцаў. Што будзе далей? АЎДЫТОРЫЯ: Сартаваць левую палову. DAVID малая: Сартаваць левую палову. Так што цяпер гэта, гэта месца тут, прыведзены спіс памер 1. І тое, што цябе клічуць? PRINCESS DAISY: Прынцэса Дэйзі. DAVID малая: Прынцэса Дэйзі тут. І вось яна ўжо адсартаваны, так як Спіс мае памер 1. Што мне рабіць наступны? OK, вярнуцца, таму што спіс з памер 1, які складае менш за 2. Тады ў чым жа наступны крок? І цяпер вы павінны выгляд вярнуцца ў вашым розуме. Сартаваць правая палова, якая - Як цябе завуць? Ліндэн: Лінда. DAVID малая: Лінда. І так, што ж нам цяпер рабіць, што у нас ёсць спіс памерам 1? АЎДЫТОРЫЯ: Вяртанне. DAVID малая: Асцярожна. Вернемся першай, і зараз трэці Крок - і калі я як бы адлюстраваць яго ахоплівае два месцы, цяпер я неабходна аб'яднаць гэтыя два элемента. Так што цяпер, на жаль, элементы выйшлі з ладу. Але на гэтым працэс аб'яднання пачынае станавіцца пераканаўчымі. Так што, калі вы, хлопцы, маглі пастаяць за проста момант, я буду мець патрэбу ў вас, у момант, каб крок ззаду крэсла. І калі Лінда, паколькі 2 знаходзіцца менш, чым 4, чаму не Вам прыходзяць у першую чаргу? Заставайцеся там. Так Лінда, вы прыходзіце вакол першай. Зараз на самай справе, калі гэта проста масіў мы маглі б проста перанесьці яе ў рэжыме рэальнага часу гэтай кафедры ў гэтае месца. Такім чынам, уявіце, што запатрабавалася некаторы пастаяннае лік крокаў 1. А цяпер - але мы павінны паставіць вас у першага месца тут. І зараз, калі вы маглі б прыходзіць, таксама, мы збіраемся Размяшчэнне знаходзіцца ў два. І нават калі гэта адчувае, што гэта заняць некаторы час, то, што прыемна зараз што левая палова Левая палова цяпер сартуецца. Так што быў наступны крок, калі мы зараз пераматаць далей у гісторыю? АЎДЫТОРЫЯ: Правая палова. DAVID малая: Сартаваць правую палову. Такім чынам, вы, хлопцы, павінны зрабіць гэта, а таксама. Так што калі вы маглі ўстаць на імгненне? А як цябе завуць? Джэсі: Джэс. DAVID малая: Джэс. Такім чынам, Джэс Цяпер левая палову правай паловы. І так яна спіс Памер 1. Яна, відавочна, сартуюць. І ваша імя? Мішэль: Мішэль. DAVID малая: Мішэль, відавочна, Пералік памер 1. Яна ўжо адсартаваны. Так што цяпер адбываецца чараўніцтва, Працэс зліцця. Так што, хто збіраецца прыйсьці раней? Відавочна Мішэль. Так што, калі вы маглі б прыходзіць назад. Прасторы мы маем у наяўнасці для яе цяпер Прама за гэта крэсла тут. І зараз, калі вы маглі б вярнуцца, а таксама, у нас зараз ёсць, каб быць ясным, два палоў, кожная з памер 2 - і проста дзеля выявай аўтара, калі Вы маглі б зрабіць трохі прасторы - адной левай палове, па адным Правая палова тут. Перамотка далей у гісторыю. Які крок будзе наступным? АЎДЫТОРЫЯ: Merge. DAVID малая: Так што цяпер у нас ёсць для зліцця. Так добра, так што зараз, на шчасце, мы проста вызваліў чатырма крэсламі. Такім чынам, мы выкарыстоўвалі два разы больш памяці, але мы можам даць фліп-флоп паміж два масіва. Так, колькасць якіх на першым месцы? Так Мішэль, гэта відавочна. Так прыходзяць і прымаюць ваша месца тут. А потым нумар 2, відавочна, Далей, так што вы прыйшлі сюды. Нумар 4, нумар 6. І зноў, нягледзячы на ​​тое, што ёсць трохі пешаходных шпацыраў залучанага, сапраўды, гэта можа адбыцца імгненна, шляхам перамяшчэння аднаго - Добра, добра гуляў. [Смяецца] DAVID малая: А зараз мы ў даволі добрай форме. Левая палова ўсяго уваходнага цяпер сартуюцца. Добра, гэтыя хлопцы былі Перавага маёй - як яна ў канчатковым выніку ўсё дзяўчыны на налева і ўсе хлопчыкі справа? Добра, такім чынам хлопцаў чаргу. Таму я не буду ісці Вы праз гэтыя крокі. Мы ўбачым, калі мы можам паўторна ж псевдокод. Калі вы хочаце ісці наперад і ўстаць, і вы, хлопцы, дазвольце мне даць вам мікрафон. Глядзіце, калі вы не можаце паўтарыць тое, што мы толькі што зрабілі тут, на Іншы канец спісу. Хто павінен казаць першым, заснаваны на алгарытме? Так растлумачце, што вы робіце, перш Вы робіце любы назе рухаў. Выступоўца 1: Ну, добра, так як Я левай паловы Левая палова, я вярнуся. Дакладна? DAVID малая: Добра. Выступоўца 1: А потым - DAVID малая: хто MIC перайсці да наступнага? Выступоўца 1: Наступны нумар. Дакладчык 2: Так што я правая палова левай паловы левая палова, і я вярнуся. DAVID малая: Добра. Вы вернецеся. Так што цяпер які наступны за вамі двума? Дакладчык 2: Мы хочам бачыць, хто менш. DAVID малая: Цалкам дакладна. Мы хочам аб'яднаць. Прастора мы збіраемся выкарыстаць для зліцця Вас у, нават калі яны Відавочна, ужо адсартаваныя, мы збіраемся пайсці па тым жа алгарытме. Дык хто ідзе ў спіне ў першую чаргу? Такім 3, а затым 7. А цяпер ідзе мікрафон з гэтымі хлопцамі, добра? Выступоўца 3: Так што я правую палову левую палову, і мой N менш 1, так што я проста хачу, каб прайсці - DAVID малая: Добра. Выступоўца 4: Я правая палова Правая палова правая палова, і я Таксама адзін чалавек, так што я збіраецца вярнуцца. Так што цяпер мы зліваемся. Выступоўца 3: Такім чынам, мы вяртаемся. DAVID малая: Дык вы ідзяце ў заднюю частку. Так 5 ідзе ў першую чаргу, то 8. А цяпер аўдыторыі, які з'яўляецца кроку нам трэба цяпер пераматаць вярнуцца да ў нашым свядомасці? АЎДЫТОРЫЯ: Merge. DAVID малая: аб'яднанне левай і правай паловы палову першапачатковай левую палову. Так што цяпер - і проста, каб было больш зразумела, зрабіць трохі прасторы паміж вамі двума хлопцамі. Так што зараз гэта два спісу, злева і справа. Так як жа нам цяпер зліццё, вы хлопцы ў першы шэраг месцаў зноў? 3 ідзе ў першую чаргу. 5 Тады, відавочна. Затым 7, і цяпер 8. ОК, а зараз мы? АЎДЫТОРЫЯ: не робіцца. DAVID малая: Не за тое, што Відавочна, што тут адзін крок засталося. Але, зноў жа, прычына я выкарыстоўваю гэта жаргону, як "перамотка ў сваім розуме," гэта таму, што на самой справе што адбываецца. Мы праходзім праз усе гэтыя крокі, але мы ж, здаецца, спыняючыся на момант, дайвінг глыбей у Алгарытм, затрымаўшыся на імгненне, апускацца глыбей і глыбей у алгарытм, і Цяпер мы павінны разабрацца перамоткі ў нашай розумы і адмяніць усе гэтыя пласты што мы накшталт прыпынена. Так што цяпер у нас ёсць два спісу памеру 4. Калі вы, хлопцы, маглі ўстаць у апошні раз і зрабіць трохі месцы тут, каб даць зразумець, што гэта левы палову першапачатковай, Правая палова арыгінала. Хто першым нумарам, што мы трэба цягнуць у спіну? Мішэль, вядома. Так мы апранулі Мішэль тут. І хто мае нумар 2? Нумар 2 прыходзіць на спіне, а таксама. Нумар 3? Выдатна. Нумар 4, № 5, № 6, № 7, і № 8. Добра, такім чынам, было падобна на шмат крокаў, гэта дакладна. Але цяпер давайце паглядзім, калі мы не можам пацвердзіць роду інтуітыўна, што гэта Алгарытм прынцыпова, у прыватнасці, N становіцца сапраўды вялікім, як мы бачылі з анімацыяй, з'яўляецца прынцыпова хутчэй. Таму я сцвярджаю, гэты алгарытм, у горшым выпадак і нават у лепшым выпадку, вялікая O п § п раз. Гэта значыць, ёсць некаторыя аспекты гэтага алгарытм, які карыстаецца N крокаў, але ёсць яшчэ адзін аспект дзесьці ў што ітэрацыі цыклу, што, што бярэ часопіс N крокаў. Ці можам мы паказаць на тое, што гэтыя два ліку маюць на ўвазе? Ну, і дзе - Дзе мікрафон ісці? Выступоўца 1: Ці будзе увайсці п парушэнне нас на дзве часткі - падзелу на два, па сутнасці. DAVID малая: Цалкам дакладна. Кожны раз, калі мы бачым у любы алгарытм такім чынам, далёка, там быў гэты ўзор дзяленне, дзялення, дзялення. І гэта звычайна аднаўляюць на тое, што гэта лагарыфмічныя, лагарыфм па падставе 2. Але гэта сапраўды можа быць што заўгодна, але ўвайсці падставы 2. Цяпер тое, што пра рускіх? Я бачу, што мы як бы падзяліла вас Хлопцы - падзяліла вас, падзяліла вас, падзяліла вас, падзелены вас. Дзе рэшце рэшт прыйшлі? Так што гэта зліццё. Таму што думаць пра гэта. Пры аб'яднанні восем чалавек разам, з дапамогай чаго палова з іх ўяўляюць сабой набор з чатырох і іншая палова іншы набор з чатырох, як вы ідзяце аб выкананні зліцця? Ну, вы, хлопцы, зрабілі гэта даволі інтуітыўна. Але калі б я зрабіў гэта, а трохі больш метадычна, я б звярнуў увагу на левы чалавек спачатку з маёй левай боку, паказаў на крайнюю левую чалавека што палова з сваёй правай рукой, і толькі пасля ішлі праз спіс, паказваючы на ​​найменшы элемент кожны раз, рухаючы пальцам па і за якія неабходныя для стварэння спісу. Але тое, што аб гэтай ключавой зліцця працэс я параўноўваю гэтыя пары элементаў. З правай палове і з левай палову, я ніколі не адступае адзін раз. Так зліцца прымае не больш за N крокаў. І колькі раз у мяне ёсць зрабіць гэта зліццё? Ну, не больш, чым N, і мы проста ўбачыў, што з канчатковым зліццём. І так, калі вы робіце тое, што займае увайсці N п крокаў разы, ці наадварот, ён збіраецца даць нам п раз часопіс N. І чаму гэта лепш? Ну, калі мы ўжо ведаем, што часопіс N лепш, чым N - ці не так? Мы бачылі ў бінарны пошук, тэлефонная кніга Напрыклад, часопіс N быў вызначана лепш, чым лінейныя. Значыць, раз часопіс N п вызначана лепш, чым N раз іншае N, N AKA квадраце. І гэта тое, што мы ў канчатковым выніку адчуваюць. Настолькі вялікія апладысменты, калі Мы маглі б, гэтых хлопцаў. [Апладысменты] DAVID малая: І вашы падарункі Растанне - Вы можаце захаваць нумары, Калі вы хацелі б. І ваш развітальны падарунак, як звычайна. О, і мы вышлем Вам кадры, Мішэль. Дзякуй. Добра. Дапамагчы сабе стрэс мяч. І дазвольце мне падцягнуць, у той жа час, наш сябар Роб Боуден прапанаваць Некалькі іншы погляд на гэта, так як вы можаце думаць аб гэтых крокаў адбываецца ў некалькі іншаму. На самай справе, ўстаноўка за тое, што Роб аб каб паказаць нам, мяркуе, што мы ўжо зрабілі дзяльба вялікі спіс на восем невялікіх спісаў, кожная памерам 1. Такім чынам, мы мяняем псевдокод трохі толькі да выгляду атрымаць у Асноўная ідэя, як зліццё работ. Але час працы, што ён збіраецца зрабіць, гэта па-ранейшаму будзе тым жа самым. І зноў, налады тут з'яўляецца тое, што ён пачалося з васьмю спісы памеру 1. Такім чынам, вы прапусцілі частку, дзе ён на самай справе зрабілі часопіс N, N часопіс, часопіс N падзел уваходнага сігналу. [Прайграванне відэа] -Вось і ўсё на першым кроку. Для другога кроку, неаднаразова аб'ядноўвае пару спісаў. DAVID малая: Хм. Толькі гук ідзе з майго кампутара. Давайце паспрабуем яшчэ раз. -Проста адвольна выбраць, які - зараз у нас ёсць чатыры спісу. Даведацца раней. DAVID малая: Там мы ідзем. Зліццё-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. [КАНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] DAVID ня малая: Зноў жа, заўважце, ён ніколі закрануў дадзенай кубкі больш за адзін раз пасля росту за яго межамі. Так ён ніколі не паўтараецца. Значыць, ён заўсёды рухаецца ў бок, а вось дзе мы атрымалі нашу н. Чаму б не дазволіць мне падцягнуць адну анімацыю , Што мы бачылі раней, але на гэты раз арыентуючыся толькі на сартавання зліццём. Дазвольце мне ісці наперад і павелічэння на гэтым тут. Перш за ўсё дазвольце мне выбраць выпадковы ўвод, павялічыць гэта, і вы можаце сартаваць, гл тое, што мы лічылі само сабой якія разумеюцца, раней, сартаванне зліццём на самай справе робіць. Так заўважыце, што вы атрымаеце гэтыя палоўкі або гэтых кварталаў або гэтыя восьмых праблема, якая раптам пачаць прымаць добрай форме. І, нарэшце, вы ўбачыце ў У самым канцы, што БАМ, ўсе аб'яднаныя разам. Так што гэта проста тры розных бярэ на сябе тую ж ідэю. Але ключавое разуменне, як і разрыву і перамагчы ў першым класе, было тое, што мы вырашылі неяк падзяліць Праблема ў нешта большае, у нешта накшталт ідэнтычныя па духу, але менш і менш і менш. Зараз іншы цікавы спосаб сартаваць думаю пра гэта, хоць гэта не збіраюся даць вам тое ж інтуітыўнае разуменні, Наступныя анімацыі. Так што гэта відэа хтосьці паклаў разам , Што звязана розных гукаў з розных аперацый для сартаванне ўстаўкамі, для сартавання зліццём, і на пару іншых. Такім чынам, у дадзены момант, я ўдару Play. Гэта каля хвіліны даўжынёй. І нават калі вы ўсё яшчэ можаце ўбачыць мадэлі адбываецца, гэта час вы можаце таксама пачуць, як гэтыя алгарытмы выкананне па-рознаму і з некалькі розных мадэляў. Гэта сартаванне ўстаўкамі. [TONES кампазіцыя] DAVID малая: Гэта зноў спрабуе ўставіць кожны элемент у якой яна належыць. Гэта пузырьковый сартавання. [TONES кампазіцыя] DAVID малая: І вы можаце сартаваць, пачуццё як адносна мала працаваць, што ён робіць на кожным кроку. Гэта тое, што гучыць як занудства. [TONES кампазіцыя] DAVID малая: Гэта выбар роду, дзе мы выбіраем элемент, які мы фарміруем праходзячы зноў і зноў і зноў і пакласці яго ў самым пачатку. [TONES кампазіцыя] DAVID малая: Гэта сартавання зліццём, якое Вы можаце сапраўды пачынаеш адчуваць. [TONES кампазіцыя] [Смяецца] DAVID малая: Тое, што называецца GNOME сартаванне, якую мы не глядзелі. [TONES кампазіцыя] DAVID малая: Так пакажыце, у цяперашні час, адцягвацца, як вы, спадзяемся, па музыку, калі я магу слізгаць трохі трохі матэматыкі тут. Так што ёсць і чацвёрты шлях, што мы можам думаць пра тое, што гэта азначае, што гэтыя функцый, якія будуць хутчэй, чым тыя, што мы бачылі раней. І, калі вы прыязджаеце на курс ад матэматыка фонам, вы на самай справе можа быць, ужо ведаеце, што вы можа аплявуху тэрмінам на гэтай тэхніцы - а менавіта рэкурсіі, функцыі што так ці інакш выклікае сам сябе. І зноў жа, нагадаць, што сартаванне зліццём псевдокод рэкурсіўнай у тым сэнсе, што адзін з крокаў сартаванне зліццём у было заклікаць роду - гэта значыць непасрэдна. Але, на шчасце, таму што мы працягвалі выкліку сартаванне або сартаванне зліццём, У прыватнасці, на меншыя і меншыя і менш спіс, мы ў канчатковым рахунку дна, дзякуючы чаму мы будзем называць базавы варыянт, жорстка выпадку, сказаў, што калі спіс невялікі, менш за 2 У гэтым выпадку, проста неадкладна вярнуцца. Калі ў нас не было, што асаблівы выпадак, Алгарытм ніколі не будзе ніжняй мяжы, і вы б сапраўды патрапіць у бясконцы цыкл сапраўды назаўжды. Але выкажам здагадку, што мы хацелі зараз пастаўлю некаторыя нумары на гэтым, зноў жа, з выкарыстаннем н як памер ўваходных дадзеных. І я хацеў бы спытаць вас, што агульны час, які затрачваецца на працуе сартаванне зліццём? Або больш агульным сэнсе, што кошт яго ў часе? Ну, гэта даволі лёгка вымераць гэта. Калі N менш 2, час, які затрачваецца У сартаванне N элементаў, дзе п роўна 2, 0. Таму што мы проста вяртаем. Там няма працы, якую трэба будзе зрабіць. Зараз, магчыма, можа быць, гэта адзін крок ці два крокі, каб высветліць колькасць працаваць, але гэта досыць блізка да 0, што Я проста хачу сказаць, няма працы патрабуецца, калі спіс настолькі малая быць нецікавым. Але гэты выпадак цікавы. Рэкурсіўнага выпадак быў філіял псевдокод, сказаў яшчэ, адсартуйце левая палова, сартаваць права палову, аб'яднаць дзве паловы. Цяпер чаму гэта выраз заяўляеце, што рахунак? Ну, T п проста азначае, што час, каб разабрацца N элементаў. А затым на правай баку Знак роўнасці там, T п падзелены 2 Маецца на ўвазе кошт таго, што? Сартаванне левую палову. Іншы T п падзеленае на 2 меркавана са спасылкай на кошт сартаваць правую палову. І тады N Plus? Гэта зліццё. Таму што, калі ў вас ёсць два спісу, адзін з Памер п над 2 і іншым памерам N больш за 2, вы павінны закрануць па сутнасці кожнага з гэтых элементаў, як і Роб дакранулася да кожнай з кубкаў, і толькі як паказвалася ў кожным з добраахвотнікаў на сцэне. Так п за кошт зліцця. Цяпер, на жаль, гэтая формула Таксама сама рэкурсіўнай. Такім чынам, калі зададзены пытанне, калі п, скажам, 16, калі ёсць 16 чалавек на сцэне або 16 кубкаў у відэа, колькі ўсяго крокі трэба для таго, каб адсартаваць іх з сартавання зліццём? Гэта на самай справе не відавочны адказ, таму што зараз у вас ёсць да выгляду рэкурсіўна адказаць на гэтае формуле. Але гэта нармальна, таму што тое дазвольце мне вылучыць што мы робім наступнае. Часу, неабходнага для сартавання або 16 чалавек 16 кубкаў, якія будуць прадстаўлены наогул як Т 16. Але, роўны, па нашых папярэдняй формуле, 2 разы колькасць Час, неабходнае для сартавання 8 кубкаў плюс 16. І зноў жа, плюс 16 самы час аб'ядноўвацца, і два разы Т 8 час, каб разабрацца левая палова і правая палова. Але зноў жа, гэтага недастаткова. Мы павінны пагрузіцца ў больш глыбокіх. Гэта азначае, што мы павінны адказаць пытанне, што такое Т 8? Ну Т 8 знаходзіцца ўсяго ў 2 раз T 4 плюс 8. Ну, што Т 4? Т 4 знаходзіцца ўсяго ў 2 разы Т 2 плюс 4. Ну, што Т 2? Т 2 знаходзіцца ўсяго ў 2 разы Т 1 плюс 2. І зноў жа, мы накшталт атрымання затрымаўся ў гэтым цыкле. Але гаворка ідзе пра ударыць, што так званы базавы варыянт. Таму што тое, Т 1, хіба мы сцвярджаем? 0. Так што цяпер, нарэшце, мы можам працаваць у зваротным кірунку. Калі Т 1 0, цяпер я магу вярнуцца да аднаго лініі Вось гэты хлопец, і я магу падключыце 0 для T 1. Значыць, яна роўная нуля 2 разы, інакш вядомы як 0, а таксама 2. І так, каб усе выраз 2. Цяпер, калі я бяру Т 2, адказ на 2, падключыць яго да сярэдняй лініі, T 4, то гэта дае мне 2 разы 2 плюс 4, таму 8. Калі я пасля гэтага падключыць 8 да папярэдняга лініі, што дае мне 2 разы 8, 16. І калі мы будзем працягваць тое, што з 24, дадаўшы ў 16, мы, нарэшце, атрымаць значэнне 64. Цяпер, калі само па сабе гаворыць роду Нічога абазначэнне N, Big O, амега, якія мы казалі. Але аказваецца, што на самой справе 64 16, памер уваходнага лагарыфм па падставе 2 з 16. І калі гэта крыху незнаёмым, проста ўспамінаю, і вярнуся Вам у рэшце рэшт. Калі гэта лагарыфм па падставе 2, гэта як 2 узведзены ў тое, што дае вам 16? О, гэта 4, так што гэта 16 разоў 4. І зноў жа, гэта не мае вялікага значэння, калі гэта з'яўляецца свайго роду туманны памяці цяпер. Але цяпер, прымаць на веру што 16 часопіс 16 роўна 64. І так сапраўды, з дапамогай гэтага простага разважнасці праверыць, мы пацвердзілі - але фармальна не даказана - што час зліцця Сартаваць сапраўды N N ўвайсці ў сістэму. Так не дрэнна. Гэта вызначана лепш, чым алгарытмы, якія мы бачылі да гэтага часу, і гэта таму, што мы выкарыстала, адзін, методыку, якая называецца рэкурсіі. Але што яшчэ больш цікава, чым тая, што Паняцце дзялення і заваёва. Зноў жа, па-сапраўднаму тыдзень 0 рэчы, якія нават цяпер паўтараецца ў больш пераканаўчым спосабам. Цяпер задавальнення мала практыкаванняў, калі ў Вас ёсць ніколі не рабіў гэтага, - і вы, верагодна, не будзе, так як выгляд нармальнага людзі не думаюць, каб зрабіць гэта. Але калі я іду на google.com і калі Я хачу даведацца што-небудзь пра рэкурсіі, Enter. [Смяецца] [Смех] DAVID малая: дрэнная жарт паступова распаўсюджваецца. [Смяецца] DAVID малая: На ўсялякі выпадак, што яна ёсць. Я не запісаць гэта няправільна, і ёсць жарт. Добра. Растлумачце гэта людзі побач з вамі, калі Гэта не зусім націснутая толькі пакуль. Але рэкурсіі, у цэлым, адносіцца ў працэсе выкліку функцыі сабе, ці ў больш агульным, падзяліўшы Праблема ў тое, што можа быць вырашыць па частках рашэння ідэнтычных Прадстаўнік праблем. Ну, давайце перадач змены на імгненне. Мы б скончыць на пэўных кульмінацый, так што давайце пачнем ўсталёўваць этап, на працягу некалькіх хвілін на вельмі просты ідэі - перапампоўкі, што два элемента, ці не так? Усе гэтыя алгарытмы мы былі Гаворачы аб апошніх некалькіх Лекцыі ўключаюць некаторыя роду замены. Сёння было візуалізавалі іх атрымання уверх са свайго крэсла і ходзяць, але ў кодзе, мы б проста ўзяць элемент з аднаго масіва і ўставіць яго ў іншы. Так як жа нам ісці пра гэта? Ну, дазвольце мне ісці наперад і напісаць хуткі праграму тут. Я збіраюся ісці наперад і рабіць гэта як наступнае. Давайце назавем гэта - Чаго мы хочам назваць гэта адна? Наогул-то, няма. Дазвольце мне перамоткі таму. Я не хачу, каб зрабіць гэта яшчэ захапляльным. Гэта сапсуе задавальненне. Давайце зробім гэта замест гэтага. Выкажам здагадку, што я хачу напісаць трохі праграма і што ў цяперашні час выкарыстоўвае гэтую Ідэя рэкурсіі. Я б атрымаў наперадзе сябе там. Я збіраюся зрабіць наступнае. Па-першае, хутка ўключаць стандартныя io.h, а таксама ўключаць у сябе, cs50.h. А потым я збіраюся ісці наперад і аб'явіць несапраўдным тап_п ў звычайным парадку. Я зразумеў, я няправільна названы файл, так што дазвольце мне дадаць. C пашырэннем вось так што мы можам скампіляваць яго належным чынам. Пачаць гэтую функцыю. А функцыя Я хачу напісаць, даволі Прасцей кажучы, гэта той, які пытаецца карыстальніка лік, а затым складае ўсе лікі паміж гэтым колькасці і, скажам, 0. Такім чынам, спачатку я збіраюся ісці наперад і аб'явіць Int N. Затым я капіюю код, які мы выкарыстоўвалі на некаторы час. Хоць сёе-тое дакладна. Я вярнуся да гэтага крыху пазней. Што я хачу зрабіць? Я хачу сказаць, Е станоўчай цэлае калі ласка. А потым я збіраюся кажуць N атрымлівае атрымаць Int. Такім чынам, яшчэ раз, некаторыя шаблонны код што мы выкарыстоўвалі раней. І я збіраюся гэта зрабіць а п менш за 1. Так што гэта будзе гарантаваць, што карыстач дае мне станоўчае цэлае лік. А цяпер я збіраюся зрабіць наступнае. Я хачу скласці ўсе колькасці ад 1 і N, або ад 0 да N, тое ж самае, каб атрымаць агульную суму. Так што самы вялікі сімвал Sigma што вы маглі б ўспомніць. Так што я збіраюся зрабіць гэта, першага склікання функцыя пад назвай Sigma, перадаючы яго па-руску, а затым я збіраюся Е сказаць, адказ тут жа. Карацей кажучы, я атрымліваю і Int ад карыстальніка. Я магу гарантаваць, што гэта станоўча. Я абвяшчаю зменную адказ цэлага тыпу і захоўваць у яго вяртанне Значэнне сігма, перадаючы N якасці ўваходных дадзеных. І тады я раздрукаваць, што адказаць. На жаль, хоць сігма гучыць як нешта, што можа быць у math.h файла, яго дэкларацыі, гэта на самай справе няма. Так што гэта нармальна. Можна рэалізаваць гэта сам. Я збіраюся рэалізаваць функцыю называюць Sigma, і ён збіраецца ўзяць параметру - Давайце проста называць гэта м, усяго так усё па-іншаму. А потым тут, я збіраюся сказаць, Ну, калі м менш 1 - гэта вельмі нецікавыя праграмы. Так што я збіраюся ісці наперад і неадкладна вярнуць 0. Гэта проста не мае сэнсу скласці ўсе лікі ад 1 м, калі м само 0 або адмоўным. А потым я збіраюся ісці наперад і рабіць гэта вельмі итеративно. Я збіраюся рабіць такога роду старой школы, і я збіраюся ісці наперад і сказаць, што я збіраюся абвясціць суму роўным 0. Тады я буду мець для завесы Int - і дазвольце мне зрабіць гэта ў адпаведнасці з нашымі Размеркаванне кода, таму ў вас ёсць копія дома. INT I атрымлівае 1 на да я менш або роўная м. Я плюс плюс. І тады ўнутры гэтага цыкла - мы амаль на месцы - сума трапляе сума плюс 1. А потым я збіраюся вярнуць суму. Так што я зрабіў гэта хутка, зусім праўда. Але, зноў жа, асноўная функцыя даволі проста на аснове кода, які мы напісана да гэтага часу. Выкарыстоўвае двайную пятлю, каб атрымаць станоўчы Int ад карыстальніка. Я затым перадаць дзесятковага да новай функцыі называецца сігма, назваўшы яго, зноў жа, с. І я захоўвання вяртаецца значэння, адказ ад чорнага скрыні цяперашні час вядомы як сігма, у зменную называюць адказам. Тады я раздрукаваць яго. Калі мы цяпер працягнем аповяд, якім сігма рэалізаваны? Я прапаную рэалізаваць наступным чынам. Па-першае, трохі праверкі памылак каб пераканацца, што карыстальнік не важдацца са мной і перадаўшы некаторыя адмоўныя або значэнне 0. Тады я абвяшчаю зменную суму і ўсталяваць яго ў 0. І цяпер я пачынаю пераходзіць ад Я роўна 1 усе, аж да і уключаючы м, таму што я хачу, каб ўключыць усе лікі ад аднаго да М ўключна. А ўнутры гэтага цыклу, я проста Сума атрымлівае тое, што ён ёсць цяпер, плюс Значэнне я. Акрамя таго значэнне я. Як у баку, калі вы не бачылі гэтага і раней, ёсць некаторыя сінтаксічны цукар для гэтай лініі. Я магу перапісаць гэта як плюс Я роўна, проста каб выратаваць сябе некалькі націскаў клавіш і выглядаць крыху халадней. Але вось і ўсё. Гэта функцыянальна тое ж самае. На жаль, гэтая кода Ці не збіраецеся кампіляваць яшчэ. Калі я запускаю зрабіць сігма 0, як жа я Я збіраюся атрымаць крычаў на? Як гэта будзе, не падабаецца? АЎДЫТОРЫЯ: [неразборліва]. DAVID малая: Так, я не аб'яўляў Функцыя наверсе, ці не так? C збольшага па-дурному, тым, што ён толькі робіць тое, што вы скажаце ёй зрабіць, і вы павінны зрабіць гэта ў такім парадку. І таму, калі я ударыў Калі ласка, увядзіце тут, я збіраюся атрымаць папярэджанне аб Sigma няяўнай дэкларацыі. О, не праблема. Я магу падняцца на самы верх, і я магу кажуць, усё ў парадку, пачакай хвілінку. Sigma з'яўляецца функцыяй, якая вяртае Цэлалікавых і ён чакае ІНТАС ўваходу, кропка з коскі. Ці я мог бы паставіць увесь функцыі над галоўнай, але ў цэлым, я б рэкамендую супраць гэтага, таму што гэта добра, каб заўсёды мець асноўныя наверсе, такім чынам Вы зможаце акунуцца ў іх і ведаю, што Праграма робіць, чытаючы асноўныя першым. Так што цяпер дазвольце мне ачысціць экран. Рымейк сігма 0. Усё, здаецца, каб праверыць. Дазвольце мне запусціць сігма 0. Станоўчае ў тым. Я дам яму колькасць 3 захаваць яго простым. Такім чынам, што павінен даць мне 3 плюс два плюс адзін, так 6. Калі ласка, увядзіце, ды і наогул я атрымліваю 6. Я магу зрабіць нешта большае - 50, 12, 75. Гэтак жа, як датычнай, я збіраюся зрабіць нешта смешнае, як сапраўды вялікі лік, О, гэта фактычна ўдалося - Эх, я не думаю, што гэта правільна. Давайце паглядзім. Давайце ўжо важдацца з ім. Гэта праблема. Што адбываецца? Кода не так ужо дрэнна. Ён па-ранейшаму лінейна. Свіст з'яўляецца добрым эфектам, аднак. Што адбываецца? Не ўпэўнены, што я пачуў яго. Вось і атрымліваецца, - і гэта як у бок. Гэта не стрыжня Ідэя рэкурсіі. Аказваецца, таму, што я спрабую ўяўляюць такая вялікая колькасць, большасць верагодна, гэта няправільнай інтэрпрэтацыі на З, не на станоўчае лік, але адмоўны лік. Мы не казалі пра гэта, але гэта Аказваецца, ёсць адмоўныя лікі ў свеце ў дадатак на станоўчыя ліку. І сродкі, з дапамогай якіх вы можаце ўяўляюць сабой адмоўны лік па сутнасці, з'яўляецца, выкарыстоўваецца адзін спецыяльны біт, каб паказаць, станоўчыя над негатыўнымі. Гэта крыху больш складана, чым, але гэта асноўная ідэя. Таму, на жаль, тады, калі З заблытанай адзін з тых бітаў, на самай справе гэта азначае, о, гэта адмоўнае лік, мой цыкл Тут, напрыклад, няма фактычна ніколі збіраецца спыніць. Так што калі я на самой справе былі надрукаваўшы што-небудзь зноў і зноў, мы, гл. шмат. Але зноў жа, гэта, акрамя кропкі. Гэта сапраўды так, накшталт інтэлектуальнае цікаўнасць, што мы прыедзем вярнуцца да у рэшце рэшт. Але зараз, гэта правільнае рэалізацыю, калі мы мяркуем, што Карыстальнік забяспечыць цэлых , Якія ўпісваюцца ў цэлыя. Але я сцвярджаю, што гэты код, шчыра кажучы, можна было б зрабіць значна больш, проста. Калі мэта пад рукой прыняць шэраг м, як і складзеце ўсе нумары паміж ім і адзін ці, наадварот паміж 1 і гэта, я сцвярджаю, што я магу заняць гэтую ідэю, якія зліваюцца Сартаваць меў, які прымаў праблемы такога памеру і падзяліўшы яе у што-то менш. Можа быць, не палова, але менш, але прадстаўніча тое ж самае. Тая ж самая ідэя, але меншыя праблемы. Так што я на самой справе - дазвольце мне захаваць гэты файл з другога нумар версіі. Мы назавем гэтую версію 1 замест 0. І я сцвярджаю, што я магу рэальна перавызначыць гэтую ў такога роду галюцынагенных шляху. Я збіраюся пакінуць частку яго ў спакоі. Я збіраўся сказаць, калі т менш чым або роўнае 0 - Я проста хачу быць трохі Яшчэ Анальны гэты раз з маёй праверкі памылак - Я збіраюся ісці наперад і вяртае 0. Гэта адвольнае. Я проста Проста вырашыць, калі карыстальнік дае мне адмоўным лікам, я вяртаем 0, і яны павінны былі прачытаць дакументацыі больш уважліва. Астатняе - заўважыць, што я збіраюся рабіць. Астатняе я збіраюся вярнуцца м плюс - што сігма-м? Ну, сігма-м плюс мінус 1 м, м плюс мінус 2, плюс мінус 3 м. Я не хачу пісаць усё гэта. Чаму б мне проста не пласкадонку? Рэкурсіўны называю сябе са злёгку меншая праблема, кропку з коскі і назавіце яго дзень? Дакладна? Цяпер і тут, вы можаце адчуць або турбавацца што гэта бясконцы цыкл, які я якія выклікаюць, у выніку чаго я рэалізую Sigma Sigma па тэлефоне. Але гэта цалкам нармальна, таму што я думаў, наперадзе якой дададзеныя лініі? АЎДЫТОРЫЯ: [неразборліва]. Дэвід малая: ад 23 да 26, якія Калі мой стан. Таму што прыемна пра адніманне тут, таму што я трымаю ўручаць сігма менш праблем менш праблемы, менш - гэта не у два разы менш. Гэта ўсяго толькі крок дзіцяці менш, але гэта нармальна. Таму што ў канчатковым выніку, мы будзем працаваць наш шлях ўніз да 1 або 0. І як толькі мы пабілі 0, Sigma ня збіраюся называць сябе больш. Гэта збіраецца неадкладна вярнуць 0. Такім чынам, эфект, калі вы роду Вецер гэтым ў сваім розуме, з'яўляецца даданне м плюс м мінус 1, плюс мінус 2 м, м плюс мінус 3, а таксама кропка, кропка, кропка, М мінус м, у канчатковым выніку дае вам 0, а эфект у канчатковым рахунку, каб дадаць ўсе гэтыя рэчы разам. Так што мы не маем з рэкурсіі, вырашана праблема, якую мы не маглі вырашыць раней. Сапраўды, версія 0 пра гэта, і кожны Праблема на сённяшні дзень, былі адрозныя толькі з выкарыстаннем для завесы або ў той час як завесы або аналагічных канструкцый. Але рэкурсіі, я мяркую, дае нам іншы спосаб мыслення пра праблемы, згодна з якім, калі мы можам узяць Праблема, падзеліце яго ад чаго-то некалькі вялікім у нешта некалькі менш, я сцвярджаю, што мы можам дазволіць яго магчыма, трохі больш элегантна, з пункту канструкцыі, з меншай колькасцю кода, і можа быць, нават вырашыць праблемы, якія будзе складаней, так як мы ў канчатковым рахунку гл, вырашаючы чыста итеративно. Але захапляльным, што я зрабіў хочаце, каб пакінуць нас было на гэта. Дазвольце мне ісці наперад і адкрыць да файла з - На самай справе, мяне адпусцілі і зрабіць гэта вельмі хутка. Дазвольце мне пайсці далей і прапанаваць наступным. Сярод код сённяшняя гэты файл тут. Вось гэтая вось, noswap. Так што гэта дурная маленькая праграма, якая Я на хуткую руку, што сцвярджае, што рабіць наступным. У асноўным, гэта спачатку заяўляе дзесятковага называюцца X і прысвойвае яго значэнне 1. Тады ён аб'яўляе цэлалікавай Y і прысвойвае ёй значэнне 2. Затым ён выдае якія х і у. Тады ён кажа, замена, кропка кропка кропка. Затым ён сцвярджае, што выклік функцыі называецца своп, пераходзячы ў X і у, ідэя якога ў тым, што, мы спадзяемся, х і ў вернецца іншы, супрацьлеглы. Тады сцвярджаюць памяняліся месцамі! з клічнікам. Тады яна выводзіць х і у. Але аказваецца, што гэта вельмі Простая дэманстрацыя ўніз Тут на самой справе дзіцячая калыска. Нават калі я абвяшчаю часовы зменнай і часова пакласці ў яго, то я перапрызначэння значэнне бы - якая адчувае сябе разумна, таму, што я захаваныя копіі пры тэмп. Тады я б абнаўлення на роўную усё, што было пры тэмп. Такая абалонка гульня перамяшчэння ў В і В у З дапамогай гэтай сярэдняга чалавека па імя Temp адчувае цалкам разумна. Але я сцвярджаю, што калі я запускаю гэтую кода, як я зраблю цяпер - Дазвольце мне ісці наперад і ўстаўце яго тут. Я буду называць гэтую noswap.c. І як вынікае з назвы, гэта не будзе правільнай праграме. Не рабіце noswap. / Няма swap. X = 1, Y = 2, замена, памяняцца месцамі. х роўны 1, у роўны 2. Гэта ў корані няправільна, нават хоць гэта здаецца цалкам разумным мне. І ёсць прычыны, але мы не збіраемся выявіць прычыну толькі пакуль. Пакуль другі захапляльным я хацеў пакіне ў вас ёсць тое, Аб'яву віды на зніжкавы купонаў. Нашы інавацыі з канца дзён у гэтым годзе справакаваў нетрывіяльнае колькасць пытанняў, які быў У нашы намеры не. Мэтай гэтых зніжкавы купонаў, згодна з якім, калі вы частка праблемы ўсталяваць рана, такім чынам атрымліваючы дадатковы дзень, было сапраўды, каб дапамагчы вам, хлопцы, дапамажыце самі пачынаюць рана, адсартуйце пабочных стымулявання вас. Дапамагае нам размеркаваць нагрузку паміж Гадзіны працы лепш, каб гэта свайго роду бяспройгрышная. На жаль, я думаю, што мае інструкцыі не было, на сённяшні дзень, вельмі ясна, так што Я вярнуўся ў гэтыя выхадныя і абнаўляецца У спецыфікацыі больш, смялей тэкст растлумачце кулі, як гэтыя. І проста сказаць, што гэта больш адкрыта, шляхам змаўчанні, наборы праблемы абумоўлены чацвер апоўдні, у вучэбную праграму. Калі вы пачынаеце рана, завяршальная частка пытанне, пастаўлены сераду а 12:00 PM, частка, якая адносіцца да купон код, ідэя ў тым, што вы можаце пашырыць Вашай тэрмін P не ўсталяваная да пятніцы. Гэта значыць, адкусіла малюсенькі частка р ўстаноўлена адносна таго, што звычайна з'яўляецца больш сур'ёзная праблема, і вы купляеце сабе дадатковы дзень. Зноў жа, ён атрымлівае вас думаць аб Пастаўленая задача, атрымлівае вас да Гадзіны працы раней. Але праблема зніжкавы купон па-ранейшаму патрабуецца, нават калі вы нічога не пішыце. Але яшчэ больш пераканаўча гэта. (Шэптам) А тых людзей, пакідаючы рана збіраюцца пашкадуеце. Як тыя людзі, на балконе. Прашу прабачэння загадзя, каб людзі на балкон па прычынах, якія будуць ачысціць праз хвіліну. Так што нам пашанцавала мець адзін з CS50 былы кіраўнік навучання стыпендыятаў Кампанія пад назвай dropbox.com. Яны вельмі шчодра ахвяраваў зніжкавы купон тут для гэтага шмат месца, які ў параўнанні з звычайная 2 гігабайта. Так што тое, што я думаў, што мы маглі б зрабіць на гэтым Апошняе заўвагу зрабіць трохі паддаўкі, пры гэтым у нейкае імгненне мы раскрыем пераможца і хто мае купон кодаў, якія можна затым перайсці да іх Вэб-сайт, увядзiце яго ў, і вуаля, атрымаць нашмат больш прасторы Dropbox для вашага прыбор і для вашых асабістых файлаў. І першы, хто хацеў бы прыняць удзел на гэтым малюнку? Добра, зараз, што робіць яго яшчэ больш займальным. Чалавек, які атрымлівае гэтую 25-гігабайтны код купона - які далёка больш пераканаўчымі, чым позна дзён у цяперашні час, магчыма - гэта той, хто сядзіць на вяршыні падушка сядзення пад якой маецца што код купона. Цяпер вы можаце глядзець пад ваша падушка сядзення. [Прайграванне відэа] -Раз, два, тры. [Крыкі] -Вы атрымліваеце аўтамабіль! Вы атрымліваеце аўтамабіль! DAVID малая: Мы ўбачым Вы ў сераду. -Вы атрымліваеце аўтамабіль! Вы атрымліваеце аўтамабіль! Вы атрымліваеце аўтамабіль! Вы атрымліваеце аўтамабіль! Вы атрымліваеце аўтамабіль! DAVID малая: Гаўбец людзі, прыходзьце тут на пярэдні план, дзе ў нас ёсць дадатковыя паслугі. -Кожны атрымлівае аўтамабіль! Кожны атрымлівае аўтамабіль! [КАНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] Апавядальнік: На наступным CS50 - SPEAKER 5: О божа мой Гоша Гоша Гоша Гоша Гоша Гоша Гоша Гоша Гоша - [Ukelele ГУЛЬНІ]