Лектор: Добре, това е CS50. Това е краят на три седмици, и ако те не са се възползвали вече, Знам, че ще има обяд този петък, както обикновено, когато можете да се насладите на добър разговор и храните на Огън и лед с някои от CS50 е персонал и съученици. Насочете се към този URL тук. 

Сега може би си спомняте, или можете скоро може да се запознае с, тези неща тук, които са дадени в края на семестъра в продължение на много часове. Така наречените изпитни сини книги, в които пишете вашите отговори на изпити. Сега имам тук 26 такива сини книги, за всеки от тях е написано едно име, от А до Z. И наистина имената са толкова просто, A чрез Z. И един от целите на днес ръка ще бъде да продължи това, което сме започнали в понеделник, което не е толкова много гледа код, но наистина търси в идеи и решаване на проблеми. Една от целите и обещания за този курс е да ви научи да мисли повече внимателно, по-методично, и за решаване на проблемите по-ефективно. И наистина, ние можем да направим, че наистина без дори да докосва линията на код. Така че аз имам няколко слонове тук днес, оранжево и синьо, ако можехме да се получи един доброволец, може би от по-назад от обичайното. Какво ще кажете за точно там, хайде надолу. Целта на която ще бъде да помогне плюс администрира този изпит тук. Как ти е името? 

АУДИТОРИЯ: Мери Бет. Лектор: Мери Бет, хайде нагоре. Нека си микрофона тук за вас. Приятно ми е да се запознаем. 

АУДИТОРИЯ: Приятно ми е да се запознаем. Лектор: Добре, така че аз нямам тук синьо книги от А до Z, и аз отивам да се преструвам, че Имам един от студентите, и те идват в известна степен произволно в края на три часа изпит блок, така че те са завършващ в някои полу-случаен ред като този. Сега вашата работа, в един момент ще да е-- това всъщност е как те ще получат беше в края на класа, най-вероятно. Вашата задача сега ще бъде съвсем просто, за да сортирате тези сини книги за нас от А до Z. 

АУДИТОРИЯ: О, това е ще отнеме цяла вечност. 

Лектор: И ние ще гледаме както можете да направите това, няма натиск. АУДИТОРИЯ: Не, никакъв натиск или нещо подобно. 

Лектор: И за забавление, нека да се примири с таймер. 

АУДИТОРИЯ: Толкова много забавно, така че много по-забавно. 

SPEAKER: Мога да държи микрофона ви. Добре, ние току-що удвои скоростта ни. Така че в същото време, нека да представлява това, което е ще бъде въпросът за Mary Beth е това, което прави тя, как е тя става за решаването на този? И в действителност, не може да има някога мисълта за нещо толкова просто, колкото когато вдигнете до 26 книги като тази, което е нужно физическо разпорежда с тях. Какъв е процесът че всъщност използвате? Дали е доста произволно просто бране на първия милион, което виждате и да я постави на негово място? Смятате ли, първо се движи ръцете си около Търсите после търсите B? Смятате ли да погледнем на двойка от тях рамо до рамо и просто да кажа, чакай малко, това Не е правилно, и след това сменяте поръчката? Ние вече видяхме в понеделник че има няколко начина , в който можем да направим това, и наистина, тъй като ние в края тук, Аз ще взема бележка може би от това, което Мери Бет прави. Имаме няколко пилоти изглежда, а по-голям един, три по-малки такива. 

АУДИТОРИЯ: Аз съм ги поръчате когато намеря две писма Знам, че сме заедно в последователност, Сложих ги заедно, така че аз не правя трябва да се притеснявате за запазване песен на цяла поредица от книги. Това е просто, о, А е първата, Имам тази купчина тук. Лектор: Така, почти като пъзел парчета, които имат право форма съвпадат един с друг. АУДИТОРИЯ: Доста, да. Лектор: OK, отлично. И сега всеки от тях купчини вероятно се сортират? 

Публика: Да. 

Лектор: Добре, A чрез Z. All Добре, поздравления, ти си го направил. Вие имате избор. Blue? Добре, благодаря ви за това. Така Мери Бет е предложила какъв подход си беше, но това, което е друг подход как може да отиде за сортиране на тези неща? Какво щеше да направиш? Записът да победи би бил една минута и 50 секунди, или така, плюс тези, които аз забравих да се броят. Какво щеше да направиш? Да? АУДИТОРИЯ: Обърнете стека. Започнете от самото начало. Проверете вашите документи. И ако в началото на един е по-висока от, може би, те са, долната един е по-висока, а след това ги включите. 

Лектор: ОК, така че като се започне в горната и долната част, и след това да работи пътя си навътре така, смяна на тях? ОК, така че малко по подобен в дух на балон вид, но избора на крайностите Не съседните двойки. Но в краткосрочен от него е, че има със сигурност един куп различни начини бихме могли да направим това и Честно казано, мисля, че ти вид прие няколко подхода, нали? Ти направи нещо като четири сортирани пилоти, и след това ефективно да ги слива заедно. И това е, смея да кажа, друг техника напълно. Вие не го третират като една голяма купчина, ви разделя на проблема в четири каре, ако щете, и след това някак си им се сляха в края. 

Така че нека да се разгледа, в крайна сметка, Как иначе бихме могли да направим това. Ние официално понятието на балон вид последен път, и балон вид отзоваване беше алгоритъм, който ние визуализира с осем от съучениците си до тук, привидно случайно подредени на първо време. И ние след това реши по двойки, ако два елемента са в ред, просто да ги сменяте. Така четири и две са очевидно от ред, така че тези две съученици размени мястото. И тогава ние се повтори с четири и шест, След шест и осем, на всяка итерация, движещи се в дясно. 

Така че, като се има предвид осем души, колко двойки сравнения съм направил по време на ходене от от ляво на дясно в едно такова повторение? Колко сравнения? Seven, нали? Защото, ако има осем хора, но те имат двойката тях и те продължават да се движат един хоп надясно, ти няма да има осем сравнения, защото не може да се сравни елемент срещу себе си, или че ще просто да бъде безсмислено, така че имате седем. Или по-общо, ако имаме N хора, ние направи N минус 1 сравнения с балон вид. 

Така че нека да разгледаме сега колко е добър или лошо балон вид всъщност е бил, и опитайте да се даде речник с които да критикуват алгоритми като този, а скоро и нашата собствена. Така че първото преминаване през балон вид, за първи път Вървях от ляво на дясно по етап, взе ме н минус 1 сравнения. И това ще бъде моя единица мярка, нали? Бях вид говори и се разхождат, малко бързо, малко бавен, така да броим моята брой секунди не е особено казвам, но преброяване на броя на операции, които направих в понеделник, сравняване на двама души, който се чувства като хубава единица мярка. 

Така N минус 1, Етап първи път но след това, което се случи след това? Какъв е една посока нагоре на един пас чрез друго несортиран списък? Какво можете да ми кажете за елемента който е бил чак там? Да? Това беше най-големият елемент, нали? Номер осем, макар че тя започна тук, всеки път, когато я сравнява с съсед, тя продължаваше барботиране до право страна на списъка. И наистина, това е, когато алгоритъмът получава името си. 

Сега от тази логика, колко сравнения Трябва ми направи по втори път Аз правя, че пас от ляво на дясно? п минус 2, нали? Той просто ще се губя времето, ако аз запази сравняване осем срещу някого друг, защото ние вече знаем тя беше на точното място. Така че това е по-малко от една оптимизация, така че следващата прохода ще бъде плюс п минус две стъпки, където N е броят на хората. Сега можете да вид екстраполира, дори ако не сте компютърен учен, как ще свърши това. В края на този алгоритъм, вероятно имаш само едно сравнение наляво. Трябва някак да се фиксира началото на списъка, в случай две и едно са в ред и трябва да бъде един и два, така че това дъно при плюс 1 окончателен сравнение. 

Сега точка, точка, точка вид вълни е Ръцете на някои от juicier детайлите, но нека просто да отида напред и да се опрости. Ако си спомняте от висока училище, честно казано, много от вас имаха математика книги, които са имали малко мамят лист на предния капак или заден капак, който ви показах какво серия summations като това в крайна сметка се прибавят към. В общия случай, ако имате променлива като N, и наистина това, ако сте разглеждали си старото училище математика книга, вие ще видите, че това всъщност добавя до тази сума тук, N пъти N минус 1 всички разделени от 2. Така че за сега нека просто да предвиди това е вярно, толкова по скок на вярата, това е, което тази обобщава до, и бихме могли да докаже, че в по-общ случай. Но сега нека да се разшири това. Така че нека да се размножава това, така че това е N на квадрат минус N, всичко разделено на две. Това е наистина N на квадрат, разделени от 2, минус N над 2, така че всичко е хубаво и интересно. Но какво ще стане, ако ние сега плъг-ин на стойност? Предполагам, че не е имал осем хора, но казват, че един милион. И един милион само защото това е доста голям брой, нека да включите, че и да видим какво ще стане. Така че, ако включите милион в тази формула Отивам, за да получите един милион на квадрат, разделени от 2 минус милиона, разделени от 2. Сега това, което е, че ще се равнява? Така че 500 милиарда, минус 500 000. И ако аз всъщност правя че математиката, това означава, че сортирането милион хора с вид на балон може да ме вземе 499 999 500 000 стъпки или сравнения в края на краищата, ние просто екстраполиране. 

Това се чувства доста бавен, но честно казано измерване на един конкретен вход по този начин, не е всичко, което казвам. Но в действителност тя не предполага, че като п получава по-голям и по-голям, този алгоритъм вид се чувства зле и по-лошо, или наистина започнете да се чувствате болката от това степенуване, че п квадрат, която добавя доста бързо. И тази подробност не е загубени на хора, в действителност Преди няколко години определено сенатор, който е бил провеждане на кампании, седнах за интервю с Ерик на Google Шмид, изпълнителен директор по това време, и е обжалван с въпрос много прилича поручваме днес. Нека хвърлим един поглед. 

[VIDEO PLAYBACK] 

-Senator, Че сте тук в Google, и ми харесва да се мисли за президентския пост като интервю за работа. Сега, това е трудно да се получи работа като президент, и ти започваш през трудностите сега. То също е трудно да си намеря работа в Google. Ние имаме въпроси, и ние попитайте нашите кандидати въпроси, и това е един от Лари Швимер. Какво-- ви момчета, че съм Шегувам се, това е точно тук. Какво е най-ефективният начин да се сортирате милион 32-битови цели числа? 

-Well-- 

Съжалявам, би-- 

Не, не, не. Мисля, че подобно на балон би било грешен начин да отида. 

Хайде, кой го каза това? Аз не виждам компютър науката във вашия фон. 

-Имаме Нашите шпиони там. 

-OK, Нека попитаме различен интервю въпрос. 

[END възпроизвеждане на видео] 

SPEAKER: Значи говорим за конкретни цифри все пак, няма да бъде всичко, което полезно. Това не е житейски урок, че балон вид, като се има предвид един милион входа, може да отнеме най-много 500 милиарда стъпки. Вие наистина не може да се генерализира твърде ефективно от тази и да направи добри дизайнерски решения при писане на програми. Така че нека да се съсредоточи макар за това как ние може да се опрости този резултат. 

Така че аз съм подчертано в жълто тук резултат на N квадрат разделен от 2, така един милион на квадрат разделени от 2, и след това Аз бях подчерта какво крайната Отговорът беше след това извадихме от N, разделено на две. А твърдението, аз отивам да се направи сега, кой по дяволите му пука, ако ти се изважда от малко стар N над 2, когато първият част от тази формула е толкова голям? Той доминира на другия Терминът, п квадрат разделен от 2 е толкова много по-голям, ясно, като п получава голяма като един милион, че има наистина голяма разлика в края на деня между 500 милиарда и 499 999 500 000? Не съвсем. И така, това, което ние ще се направете компютърни учени е игнорират тези по-ниски условия ред и предприеме нещо подобно и наистина просто го опрости до термин, който ще има значение. По-големите ни набори от данни да получат, толкова по-големи нашите бази данни, толкова повече уеб страници ние трябва да се търси, толкова повече Приятелите, които си във Фейсбук. 

Както п получава по-голям, ние сме наистина Ще се грижим за най-големите Терминът в такова анализ на нашата работа алгоритми. И аз щях да кажа, знаеш ли какво, балон вид е от порядъка на голям O, от порядъка на N на квадрат. Това не е точно н квадрат, както сме виждали, но кой наистина го е грижа за тези по-малки срокове, и честно казано, който наистина му пука, ако ние разделяме с две? Това е просто един постоянен фактор. И е 500 милиарда в сравнение с 250 милиарда наистина, че голяма сделка? Мога просто да чакам за една година, нека ми лаптоп буквално получи два пъти по-бързо в хардуера, и че нещо разлика просто си отива естествено с течение на времето. 

Какво ни е грижа за е експресията, частта на израза, че няма да се различават като наш принос стане по-голям и по-голям. И наистина, в реалния свят, това е, което се случва все по-често е входовете на нашите проблеми и алгоритми са все по-големи. Така че голяма O ще бъде нотацията, асимптотичната нотация, че ние просто използвате като компютърни специалисти, за да опише изпълнение, или времето за бягане, на алгоритъм. Така че ние може да се сравни алгоритми на различни компютри писмени от различни хора, с помощта на някои фундаментално подобен метричен като броят на сравненията си вземане на решения, или може би на броя на суапове вие правите. 

Това, което ние няма да брой е сумата от време който преминава на часовника на стената обикновено. Това, което ние не започваш да се притесняваш , е колко памет вие използвате днес малко, макар че е друг ресурс можем да се измери. Ние ще се опитаме да основаваме нашите анализи само върху основните операции, онези, честно казано, че можете да видите най-визуално. Така е и с нещо като голяма O на п квадрат, аз твърдя, че O на N на квадрат е горна граница на така наречените времето за работа на балон вид. С други думи, ако сте Исках да се твърди, че има тази горна граница за това колко стъпки алгоритъм може да отнеме, тя ще бъде в големия О от п квадрат в този случай, горна граница. 

Какво става, ако вместо да променя история, за да бъде не за балон вид, но за тази горна граница. Сещате ли се за един алгоритъм , които сме разглеждали вече чиято горна граница, максималната измерване на време или операции, ще се казва, да бъдат ограничени от N, линейна функция, не квадратичен едно, че е извит? Какво е алгоритъм, който винаги отнема не повече отколкото като N стъпки, или 2n стъпки, или 3N стъпки? Да? 

АУДИТОРИЯ: Намирането на Най-големият брой в списък? 

Лектор: Perfect, намирането най-голям брой в списък. Ако аз съм дал списък на хора, например, всеки от които е провеждането на номер, какъв е максималният брой от стъпки, трябва да ме вземе, сравнително интелигентен човек, да се намери най-големият човек в този списък? N, нали? Защото в най-лошия случай, когато може да бъде най-голямата стойност? Точно така, чак в края. Така че в най-лошия случай горна граница, може би Трябва да отидем по целия път тук и ще бъда като, О, тук е номер осем, или каквото и да е стойност. Сега тя просто ще бъде глупаво ако аз продължих, нали? Търсите повече и повече елементи Ако последният от тях е там? Така че със сигурност, п е горна граница. Не трябва да се предприемат повече стъпки от това. 

И какво, ако вместо това предложи има алгоритми, в този свят, който имат течаща време, че е ограничена от голям O на дневник п, влезте н? Къде сме виждали това преди? Да? 

АУДИТОРИЯ: В проблема с телефонния указател? Лектор: Подобно на проблема с телефонния указател. Какво е мярка за това колко много време или колко сълзи ИТ ми отне да се намери някой като Mike Smith в телефонния указател? Ние твърди, че е дневник п и дори ако непознат или да го е малко мъгляво какво логаритъм или експонат е, просто не забравяйте, че дневник п обикновено се отнася до процеса, в този случай на разделяне нещо в половината отново, и отново, и отново, и отново, така че тя получава все по-малък, както правите това. 

Така влезете на п се отнася, разбира се, за пример на телефонен указател, за търсене двоичен на теория, когато ние имаше виртуалните врати на борда, или когато Шон е бил търсене на нещо. Ако той е използвал двоично търсене, влезте п ще бъде горната граница на колко времето, което отнема. Но тези алгоритми, които се стичаха в дневника н предположи какво ключов детайл? Това, че списъкът е подредени, нали? Вашият алгоритъм е лошо, ако вашия вход не се сортират, и все още сте с помощта нещо като двоично търсене защото може да скочи право върху елемент без да осъзнават, че е наистина там. 

Сега какво може да означава това, голяма O на една? Това не означава, че алгоритъма си има една и само една стъпка, това просто означава, че отнема постоянен брой стъпки. Може би това е един, може би това е 10, може би това е 1000, но тя е независима от размера на проблема. Без значение колко е голям н е, постоянна алгоритъм време винаги се същия брой стъпки. Така че това, което може да се окаже един алгоритъм ние говорихме за или просто интуитивно, че идва при вас, че винаги работи в така наречената константа време? Да? 

АУДИТОРИЯ: Добавят се две числа. Лектор: Добавете две числа, 2 плюс 2 е равно на 4, направено. Така, че може да работи, какво друго? Какво ще кажете за по-реалния свят, така ли? 

АУДИТОРИЯ: Намирането на Първото нещо в списъка. Лектор: Намирането на първа елемент в списък, разбира се. Ние сме били действително говори за масиви вече как да получите в първият елемент в масив, без значение колко дълго масив е в C код? Можете просто да използвате като скобата нула нотация, бам, вие сте там. И наистина масиви, като настрана, подкрепа нещо общоизвестно като случаен достъп, с произволен достъп памет, защото можете да буквално скочи до всяко едно място. Можем да го направим още по-просто можем да превъртите до нула седмица когато направихме Scratch. Колко време отне на каже блок в Scratch да изпълни? Просто константно време, нали? Кажи нещо, да речем нещо, то не е от значение колко големи драскотини свят е, че винаги е ще отнеме същото количество време просто да каже нещо. 

Така че това е константно време, но това, което е обратна страна? Ако това е горната границите, какво, ако искаме да се опишат по-ниски граници на нашите алгоритми за време? Почти една-добрия случай потенциално, ако щете, макар че тези условия могат да се прилагат по най-добрия кутии, най-тежките случаи, средно случаи повече като цяло, но нека просто да се съсредоточи на по-ниски граници по-общо. Какво е алгоритъм, който има долна граница на N стъпки, или 2n стъпки, или 3N стъпки? Някои фактор на N стъпки, това е неговата долна граница. Да? 

АУДИТОРИЯ: Bubble вид? 

Лектор: Bubble вид отнема вие минимално N стъпки, защо? Защо е това? Защо трябва това начало да дойда при вас интуитивно, дори ако тя не само Все още? Да? 

АУДИТОРИЯ: [недоловим]. SPEAKER: Точно така. В най-добрия възможен сценарий на балон вид, и много алгоритми, ако ви предам осем души които вече са подредени, би било глупаво за вас, алгоритъмът, да се върна и назад повече от веднъж, нали? Защото веднага след като си преминете през списъка веднъж, вие трябва да осъзнаят, о, аз не направи суапове, този списък се сортират, изход. Но това няма да ти п стъпки предприемат. 

И обратно, това, което е още един начин на мислене за него? Bubble вид е омега, така да се каже, на N, защото, ако се вгледате в по-малко от N елементи, какво е основният въпрос там? Не знам дали това е подредени, нали. Ние, хората, мощ поглед в осем хора, и ще бъда като, о, това е сортиран, това не ме N стъпки се предприемат, но го е направил. Очите ти, макар и да вид на има голямо зрително поле, ви погледна осем елементи, ви погледна осем души, това е ефективно осем стъпала. И само ако ходя през цялото списък направя аз осъзнавам, да, подредени. Ако спра по средата мисля, всички Добре, това е доста подредени досега, Какви са шансовете това не е сортиран? Това не алгоритми ще бъде вярна. Може да бъде по-бързо, но неправилно. 

Така че сега ние имаме начин на описващи долни граници, и какво ще кажете за константно време? Какво е алгоритъм, който има по-ниска граница на времето си бягане на една? Една стъпка, две стъпки, 10 стъпки, но постоянно, независимо от N, размера на входа? Да, в гърба. 

АУДИТОРИЯ: ФОРМАТ? Лектор: Какво е това? АУДИТОРИЯ: ФОРМАТ? Лектор: ФОРМАТ. OK, разбира се. Така се определен брой стъпки. И аз трябва да сега-- сега, че ние не говорим за C код и не Scratch, нещо като да речем, с ФОРМАТ, трябва да започнем да се внимава. Защото ФОРМАТ взема вход, това е низ, и струни да имат технически дължина. Така че, ако ние сега искаме да вземем на вас, ако нямате нищо против, технически бихме могли да твърдим, че ФОРМАТ взема вход променлива дължина, и със сигурност може да отнеме повече Време за отпечатване на низ толкова дълго, от толкова дълго. 

И какво от това, ако вземем предвид само сортиране и търсене примери? Ами Mike Smith в телефона книга, или двоично търсене по-общо? В най-добрия случай, това, което може да се случи? I отворите телефонния указател и, бам, има редица Майк Смит. Мога да му се обадя веднага. 

Взе една стъпка, може би две стъпки, но постоянен брой стъпки ако имам късмет. И честно казано, видяхме на Понеделник си съученик получи доста късмет два пъти подред. И това наистина е постоянна време в ниски граници на алгоритъма въпросната за намиране броя 50 зад тези затворени врати. 

Сега, като се отмени, ако откриете че и двете големи O, горната граница, и Омега, долна граница, са един в същото, че е същата формула в скоби, можете също да се каже, само за да се фантазия, че нещо е в тета п или тета друга стойност. Това просто означава, че когато голям О и омега са еднакви. Сега какво да кажем за избор вид? Нека използваме тази нова лексика. При избор на сортиране, което бяхме прави отново, и отново, и отново? Щях напред и назад през списъка, търсейки кого? Най-малкият номер. 

Е, как много стъпки, как много сравнения направих трябва да се направи, за да разбера кой най-малкия елемент в списъка е? п минус 1, нали? Защото, ако аз просто започнете с едно съм като се има предвид и да започна да го или я сравняват, след него, го или нея, него или нея, да сдвоите само елементи заедно N минус 1 пъти. Така че избор на сортиране по подобен начин се п минус 1 стъпки за първи път. 

Колко стъпки пък ме отведе до намери втория най-малък елемент? п минус 2, защото аз съм като ням ако продължавам да гледам едни и същи хора отново, ако вече съм го избрали или си и ги постави на мястото им. И третата стъпка, п минус 3, тогава п минус 4. Видяхме този модел преди, и наистина избор на сортиране по подобен начин има горна граница п квадрат ако правим нагоре, че сумиране. Каква е неговата долна граница, избор на вид? Минимално, колко селекция път, трябва да подреди вземе, тъй като ние я определя в понеделник? Предлага две възможности. Може би това е N, както и преди. Може би това е п квадрат, тъй като тя сега е на горната граница. 

АУДИТОРИЯ: N на квадрат. SPEAKER: N на квадрат. Защо? 

АУДИТОРИЯ: Защото имате да се определи [недоловим]. 

SPEAKER: Точно така. Най-малко, както аз определено избор сортиране това е доста наивно, продължавай, намерите най-малкия елемент. Отиди отново, да намерите най-малкия елемент. Отиди отново, да намерите най-малкия елемент. Няма по вид оптимизация там, че може да ме прекъснете, след само на N-те стъпки. И наистина, подбор сортиране, омега на п квадрат. 

Какво ще кажете за вмъкване на сортиране, където взех който ми беше даден, и тогава аз го пльосна или си на правилното място? След това пристъпва към втория човек, него или нея се пльосна на правилното място. След това на следващия човек, пльосна него или нея в правилното място. Забележете, че това е много линейна, така да се каже. Аз съм по права линия, аз съм не върви напред и назад, Никога не съм гледам назад наистина, но какво се случва, когато го поставете или я в началото на списъка, както направихме в понеделник? Какво се случва? Да? АУДИТОРИЯ: [недоловим]. Лектор: Да, това е уловката, нали? Може да се припомни, от съучениците си, ако те са били прави всяко движение с краката си, това беше една операция. Така че, ако е имало трима души тук и новото лице принадлежеше начин там, на дълъг етап като това, разбира се, той или тя може просто да отидете до самия край. Но ако си мислите за компютър и масив на памет, тези хора ще трябва да разбъркате над за да направи място за това лице. И така, това, че п минус 1 shufflings, п минус 2 shufflings, н минус 3 shufflings е просто вид случва зад мен, а не пред мен както преди, в известен смисъл. Сега като настрана, и като може да сте онлайн ако започнете да изпълзяват около около видове, има толкова много различни хора там, някои от тях по-добре от други. Всъщност, bogosort е един че е забавно да гледам нагоре. Bogosort се набор от номера или да кажа едно тесте карти, случайно ги разбърква, и проверки, ако те се сортират. И ако не е, го прави отново. И ако не е, го прави отново. Ако не, да го прави отново. Невероятно глупава. 

И наистина, ако четете като статията Wikipedia, му псевдоним е глупав вид. Това в крайна сметка ще работи, Надяваме се, че дадено достатъчно време, но този период от време може да отнеме доста време. Така че, ако можех, нека скоростта неща нагоре от например Мери Бет-рано, от наличието на още няколко елементи, но още два процесора. Двама души, ако сте не би имал нищо против да ми се присъедини. Какво ще кажете за един тук, и нека go-- никой не там? Никой не там? OK. Ти, с черно риза, да, хайде надолу. Добре, какво е вашето име? 

АУДИТОРИЯ: Peter. 

Лектор: Какво е това? 

АУДИТОРИЯ: Peter. Лектор: Петър, Давид, хубаво е да се запознаем. Добре, имаме Peter тук, ако сте искат да дойдат на масата тук. А какво е твоето име? 

АУДИТОРИЯ: Елена. Лектор: Елена. Добре, хубаво е да се запознаем. Елена срещне Питър. Peter, Елена. И ще имаме нужда от Andrew тук, както и, моля те. И си предизвикателство ще да бъде да сортирате тесте карти. И ако непознат, палуба карти трябва в крайна сметка бъдат сортирани малко нещо като това, където ние ще направим клубовете, а след това лопатите, тогава сърцата и диаманти, от асо като един, по целия път до цар. 

Картите аз ще ви дам ще бъде 52 в количество. Отиваме по подобен начин Вашето време, в един момент. Отиваме, за да хвърлят Andrew на екрана тук, , така че да гледате, тъй като правиш това. И така, че цялата е още по-видими, това са картите се качих на Amazon. Така че те вече са на случаен принцип подредени, а ние ще ви време. И ние ще се я държи недвижими този път, така че ние ще се опитаме да ви притисне защото в противен случай това ще получите досаден бързо. Ако можеше да се процедира, за да сортирате 52 елементи заедно чрез някои средства, веднага. 

И отново, както ние гледаме тези момчета правят това, в края на краищата ще се произвежда очевидна резултат, мисля за наистина как те всеки го прави, как бихте могли да го опиша. Защото отново, те са Всички процеси, алгоритми че ние приемаме за даденост, като човек. Но вероятно сте отдавна има интуиция, дълго преди да можете дори мислех за вземане на компютърни науки ви клас може да е имал интуицията с които да решават проблеми като този. Но след като веднъж сте се признае моделите и да започне да се формализира стъпките, с които сте решаване на тези проблеми, ще откриете, че можете да решите много по-интересна и много по-сложна проблеми бързо. Значи някой от публиката, какво е най-малко един елемент на алгоритъма че те използват тук? 

АУДИТОРИЯ: [недоловим] Лектор: Какво е това? АУДИТОРИЯ: С костюм. Лектор: С костюм. Така че първо те са съсредоточени всички от диамантите заедно изглежда, всички от сърца заедно изглежда, и т.н., без отношение за номерата на картите. И сега те се появяват, например, да им сортиране по номер. Много добре. 

Добре, така че какво ще се да бъде последната стъпка, след това тук? След като имаме четири сортирани костюми, какво ние трябва да направим, за да четирите купчини за да се постигне една подредени палубата, съвсем просто? Така че ние трябва да ги слее отново. 

Така че там е интересна идея, която отново, смея да кажа, е много интуитивен дори ако никога не би могъл да зашлеви този вид на етикет върху него. Тази фундаментална идея за разделяне проблемът не в половината от това време, но най-малко на четири парчета. Решаване на почти фундаментално идентични проблеми отделно един от друг, и след това обединяване на резултатите. И, отлично, направи. Добре, един голям кръг аплодисменти, ако можехме. 

[APPLAUSE] 

Лектор: Нямам представа какво ще общо с тях, но тук и да отидете. Благодаря ви толкова много. Така че нека да видим две минути и осем секунди, ако искате да предизвикате приятелите си. Какво тогава се случва да бъде отнеме от тази че можем да се наберат по-общо? Е, мисля, че обратно към този масив от числа, и мисля, че сега обратно към някои от pseudocode сме написали в миналото, и това беше pseudocode за решаване на проблема с телефонния указател. Чрез която в pseudocode I изброените по-методичен начин за описване как съм направил много интуитивен човешки алгоритъм на разделяне на телефона книга на половина, повтарям, повтарям, повтарям, докато не намеря някой като Майк Смит, ако той наистина е в телефонния указател. 

Но аз вид се използва това, което аз ще се обадя много итеративен подход тук, по-специално известие линия 8 и линия 11. Тези, които са доказателство за един повтарящ подход, подход на примка, защото това е точно поведението предизвикват. Тези линии и двете казват, отидете на трета линия, и ще можете да вид мисля, че в окото на ума, че е на линия. Той ти казва да се върнете до стъпка три и се повтаря отново и отново, и отново. 

Но какво, ако ние се наберат ключова идея И ето, че не сме за последен път, и опростяване на линия 8 и ред 11 и техните съседи като само този, в жълто. Това не е фундаментално скъсяване на pseudocode много, но това е фундаментална промяна естеството на алгоритъм ми. Това, което съм сега се казва в стъпка 7, в стъпка 10, е да се търси за Mike в точно същия начин, но само в лявата половината или дясната половина. 

С други думи, ако I започнете от стъпка едно, вдигнеш телефона книга, отворена за средната на телефонния указател, погледнете имената, ако Смит е сред Казва се, обади се Майк, в противен ако Смит е по-рано в книгата, стъпка седем търси за Mike в лявата половина на книгата. Но този вид чувства като това ме остави обесване, нали? В жълто, е инструкция, но как да направя търси за Mike в ляво половината от телефонния указател? Къде мога да имат алгоритъм, с които съм да търсите за някой като Майк Смит? Е, това ни се взираше в лицето. Аз буквално може да използва точно същото програма за ефективно става до върха отново и отново работа същите линии на код. 

Така че, въпреки че това трябва да се чувстват като малко цикличен дефиниция , където можете да отговорите, някой е Актуален въпрос от просто някак пита същия въпрос отново, като защо, защо, защо? Реалността е, защото сме твърди кодирани няколко специални линии, етап 4, което е, ако и 12, които е ефективно друг клон, защото имаме тези мерки StopGAP, този алгоритъм ще бъде прекратен, ако ние намерите Майк, или ако не го правим. Но в стъпка 7 и 10 сега имаме това, което ние ще наричаме рекурсивен алгоритъм. И рекурсия е наистина мощен идея това е малко ума огъване на пръв поглед, че сега можем да се прилага, както следва. 

Обединяване вид ще бъде последният вид, че ние погледнете, най-малко в клас официално. И това е коренно различна от тези, последните три, и със сигурност последните четири ако включим bogosort. Ето pseudocode за сливане вид. Когато на входа на наш елементи, така че като се има предвид масив с размер N, ако п е по-малко от 2, се върне. Така че, защо да имам, че здрав разум проверите първо? Какъв е изводът, ако ви предаде масив с дължина п е по-малко от 2? Той вече подредени, очевидно, нали? Тъй като списъка или има един елемент, който е тривиално подредени, защото това е единственото нещо, което има. Или, това е с размер нула, което означава, няма за какво да се справи, така че по природа тя се сортира. Има само нищо лошо там. Така че това е нашата т.нар базов модел. 

Това е подобна по дух на това, което направихме с Майк. Ако Майк в телефонния указател, обадете се на него. Ако той не е там, да се откажа. Това е така наречения базов модел, за да се уверите този алгоритъм в края на деня ще спре при определени обстоятелства. 

Но тук е скок на вярата сега, друг, сортирате лявата половина на елементите, тогава сортирате правото половината от елементите, и след това се слеят сортирани половини. И тук е мястото, където тя се чувства като сме copping навън. Помолих те да сортирате п елементи, и аз съм казвайки: Добре, не го чрез сортиране Левият и сортиране на правото. Но аз казвам, че един друго нещо, и това е ключовата тема изглежда в интуицията до този момент, там е тази трета стъпка за обединяване. Което, въпреки че изглежда толкова тъпа по дух, като просто се сливат неща заедно, изглежда да бъде ключова стъпка към сглобяване на два проблема, които бяха разделени в крайна сметка на половина. 

Така се сливат вид, нека да направим това, ако вие ще хумор мен, с още една демонстрация, просто така, че ние имаме някаква номера, за да работим. Мога ли да обменят осем стрес топки за осем души? Добре, какво ще кажеш ти три, ти четири в този раздел, пет, шест, и нека са 7, 8, хайде нагоре. OK, да OK. Минус 8, там да отидем, плюс един. Отлично. Добре хайде нагоре, нека бързо ви даде номера. Номер две, номер три, номер четири, номер пет, шест, седем, а осем. Направих осем правилно този път. 

ОК, така че давай напред, ако можеш, и нека да сортирате в първоначалния ред че имахме вчера, която изглеждаше по този начин, ако не би имал нищо против. И нека го направим в предната част на таблицата. Добре, така че се сливат вид. Това е мястото, където става за да получите вид интересно, защото аз като че ли да се даде себе си толкова по-малко информация днес. 

Така се сливат вид на първо място на входа на наш елементи, и очевидно не е по-малко от два, е осем, така че имам още малко работа за вършене. Така че сега ние мислено като клас сега са в бранша друго, което означава три стъпки. Първо, трябва да се справи със лявата половина на елементите. И така, как мога да отида за правиш това? Е, аз отивам да се вид умствено разделят списъка тук, не е нужно да се физически се движат, и аз съм ще се съсредоточи само върху лявата половина на елементи тук. И така, как мога да отида за сортиране списък сега с размер четири? Какво ми алгоритъм? Първо ще се провери, е п-малко от две, не, така че аз се пристъпи към друг блок отново. Sort лявата половина на елементи. 

Така че сега отново, умствено, и това е мястото, където вие трябва да натрупате много психическо история, ако щете. Сега съм сортиране ляво половината от лявата половина. Добре, така че сега аз наричам моя същия сливат сортиране алгоритъм, е п-малко от два? Не, това е две, така че аз трябва да се справи лявата половина и дясната половина. Така че тук ние тръгваме, сортирате лявата половина. Защо просто не вземете една крачка напред. Как ти е името? 

АУДИТОРИЯ: Дарън. 

Лектор: Дан. Дан пристъпи напред. 

АУДИТОРИЯ: Дарън. Лектор: Darren, направено. Знаете ли, казват, Darren или Дан? 

АУДИТОРИЯ: Дарън. 

Лектор: Дарън. OK, Darren активизира напред и той вече е сортиран. И това е почти нелеп твърдение, нали? Аз наистина не изглежда да се постигне нищо, но нека да се процедира. Сега нека да сортирате правото половината от елементите. Как ти е името? 

АУДИТОРИЯ: Люк. 

Лектор: Люк. Хайде, излез напред. Съставено, аз подредени Лука. Лявата половина вече се сортират и дясната половина вече се сортират, но отново, там е ключова стъпка тук. Какво ми следващия трябва да направя? Сливане на сортирани половини. Сега отиваме да просто трябва всички назад и напред по този начин, защото аз вид трябва някои нулата пространство. Това е почти като тези момчета са на една маса, и имам нужда от стая да ги движите нататък. Така че аз отивам да се слеят вие като погледнете в лявата половина и дясната половина. И който очевидно е на първо място, лявата половина или дясната половина? Така че дясната половина, така че нека да се движат Luke над тук на първоначалното място на Дарън. И сега, за да се слеят лявата им половина, Дарън ще се премести там. 

Така че се чувства като почти балон вид ефект, но моят основен алгоритъм, много различно този път. Но сега е, когато нещата стават малко досадно, защото вие Трябва да се върнем назад психически къде си оставих разстояние. Току-що се слива сортираните половинки, което означава, че аз съм къде в алгоритъм ми? Трябва да сортирате дясната половина, нали? 

Ако сте назад, буквално на видео, вие ще се види, че стигнахме до този точка на Люк и Darren от сортирането в ляво половината от лявата половина. Тогава ние се слива тези сортирани половини, които означава, че следващата стъпка е сортирате дясната половина на лявата половина. Добре, така че нека да да направите това по-бързо. Добре, шест, аз отивам да претендира сега са подредени, хайде напред. Как ти е името? 

АУДИТОРИЯ: Адриано. 

Лектор: Адриано. Адриано вече е сортиран. А какво е твоето име? 

АУДИТОРИЯ: Alex. 

SPEAKER: Alex сега се сортира. Лявата половина, дясната половина, това, което е последната стъпка? Merge. Доста тривиално, така че аз съм ще се слеят в шест, да направи крачка назад, осем, да направи крачка назад. И сега забележи това е полезна храна за вкъщи, какво сега е вярно за лявата половина на списък, независимо от начина, по който започна? Той се сортира. 

Сега това не е подредени в голямата схема на нещата, но се сортират независимо на другата половина. Сега какво крачка съм от това, ако аз продължавам пренавиване как историята започна? Сега имам да сортирате дясната половина. Така че сега ние сме начин обратно в началото на историята, и нека да направим това по-бързо. Така че аз отивам да се справи със дясната половина на целия списък. Каква е следващата стъпка? Подреди лявата половина на дясната половина. Подреди по лявата половина на лявата половина на дясната половина. А какво е твоето име? 

АУДИТОРИЯ: Омар. 

Лектор: Omar, стъпка напред, направи. Лявата половина се сортира. А какво е твоето име? 

АУДИТОРИЯ: Chris. 

Лектор: Крис, да вземе една стъпка напред, вие сте сега подредени. Какво е най-важният етап в момента? Merge. Така че едно е да се слеят в място тук, ако бихте могли да се върнем малко назад, и три ще се да направи крачка назад, се слеят. Така че лявата половина на дясната половина, сега се сортира. Честно казано, този алгоритъм се чувства като ние Губиш начин повече време, отколкото преди, но ако сме направили това в реално време, ние ще видим какво храна за вкъщи ще бъде. Сега аз съм тук, нали половината от дясната половина, позволете ми да отида напред и да сортирате лявата половина. Стъпка напред, какво е вашето име? АУДИТОРИЯ: Рамзи. Лектор: Ramsey сега се сортира. Как ти е името? 

АУДИТОРИЯ: Marina. 

Лектор: Marina сега се сортира като добре, ако вземете една крачка напред. Key стъпка тук, сега се слеят, аз съм ще извади от двете ми списъци, наляво и надясно. Five ще дойде първо, и седем ще дойде следващата. И отново, това е умишлено. Фактът, че те са като стъпки напред и назад има за цел да декларирате, че не можем да направи този алгоритъм в място толкова лесно като балон сортиране и подбор на сортиране, и вмъкване на сортиране, където ние просто съхраняват смяна хора. Буквално трябва нещо от нулата хартия, в която да наложи на тези хора докато правя сливането, и тогава мога да ги пуснат обратно на мястото си. И това е ключов, защото аз съм с помощта на нов ресурс, пространство, а не само време. 

ОК, това е невероятно. Лявата половина се сортира, дясната половина е Подредено, сега, че ключов сливане стъпка. Как ще се слеят това? Така че, ако ще следвам лява и дясна ръка, Отивам да се посочи лявата си ръка в лявата половина, дясната ми ръка в дясната половина, и сега ще трябва да реши стъпка по стъпка към кого да се слее инча Кой очевидно е на първо място? Номер едно. Така че, ела тук, тук е нашата бележник. Така че сега номер едно, и обявление какво ще правя с дясната си ръка, Отивам да се движи дясната си ръка една стъпка към точка номер три, и сега трябва да се направи същото решение. И всъщност стои прав в пред Лука тук, ако можех, защото това е нашата бележник. Така че, който идва след това? Имаме Luke с номер две или Chris с номер три. Очевидно Лука, брой две, така ли да дойдеш тук. 

Но лявата ми ръка, сега ще се да бъде увеличен, за да се отбележи в Darren, и тук е ключът отнеме с сливане, аз ще продължа да правя това, Очевидно е, че ако сте вид от следваме логиката. Но ръцете ми никога не са Ще се върнете назад, което означава, че аз съм само някога се премести в наляво с моя процес сливане и това ще бъде от ключово значение, за да нашия анализ в един момент. 

Така че сега нека да довърша това бързо. Така три идва следващия, След четири идва следващия, и сега пет идва следващия, след това шест, и седем, а след това най-накрая осем. Усеща се най-бавният алгоритъм все още, но не и ако ние всъщност тя тече от същия вид на тактова честота, така че да говори, със същите тиктака часовник, както и преди. Защо? Е, нека хвърлим един погледнете крайния резултат. 

Нека да се върнем тук, позволете ми да издърпайте нагоре демонстрация визуално от това, което току-що го направих. Увеличение тук, на тази страница тук, казва Firefox че искаме да си вадя в това поле, нека каже балон вид, с които сега сме добре запознати, избор на сортиране, който е друг сравнително лесно един, и сега днешния сливат вид, който За нас ще бъде кулминационен край. Причината за това отне толкова много по-дълго тук с хората и ми е устно, Очевидно е, че аз съм за обяснение на всяка стъпка. Но ако просто изпълни това, много по- както направихме нещо като балон и избор вид не само визуално, часовник колко по-ефективно това деблокирането на разделяне и завладяване може да бъде, когато се прилага по отношение на набор данни, че е Дори не размер осем, но дори и много, много по-голяма. Давам ви се слеят вид, рамо до страна с тези на други алгоритми. Това ще се получи болезнен бързо, и краят не е особено климатични, те просто свърши подредени. Но ключът отнемат е, че Виж колко много по-бързо се сливат вид е, освен ако не мислиш, че съм просто вид на каша с вас. Ако правим това за последен път, Нека да презареди това, нека се върнем и изберете балон вид, и само за ритници, нека изберем вмъкване вид, само за добра мярка. И този път отново, нека изберете сливат вид и нека всъщност изпълните тези рамо до рамо. 

И това не е, в действителност, една щастлива случайност. Това, което съм направил, е ефективно Имам разделена моя вход в половината, отново, и отново и отново. И има само толкова много пъти може да разделите вашия вход на две половини, наляво и надясно. Каква е формулата, която пазим виждайки който описва разделението на половина отново, и отново, и отново, и отново? 

АУДИТОРИЯ: Влезте п. 

SPEAKER: Влезте п. Но след това има една друга важна стъпка, този алгоритъм не се впишете н стъпки. Ако се впишете само N стъпки, ще бъде в същия проблем както преди, когато не можем да бъдем че всичко е сортиран. Трябва да се минимално погледнете наш елементи да бъде сигурен, п елементи са подредени, в противен случай това е скок на вярата. 

Така че това е минимално дневник N стъпки, но какво да кажем за тази ключова стъпка сливане където се слива лявата си половина и дясната половина и ходи по сцената? Колко стъпки е, че да се слеят? Това е N, но не го направих само слеят последен път. На всяка от тези вложени повиквания, на всеки на тези вложени слива, аз все още подредени. Аз се слива тези две момчета, тогава тези две момчета, тогава тези две момчета, и така нататък. 

Така че аз съм сливане отново, и отново. Колко пъти? Така че всеки път, когато се разделя списък на половина, аз направих сливат. Разделете списъка на половина, направи се сливат. Така че, ако се раздели на списъка може да се направи Вход N пъти, и сливането в крайна сметка се п стъпки, това, което може да бъде А най-горните граница на протичане време на нашия алгоритъм? п влезете п. 

И наистина, това е, което ние сме постигнали тук. Така усещането, че виждате визуално, когато тези три неща работят рамо до рамо п е квадрат срещу N квадрат срещу п дневник п. Което коренно ще видим, не само днес, но в бъдеще е много, много по-бързо. Аплодисменти за тези момчета, Аз ще ги възнагради с стрес топки. Да се ​​отложи днес тук, и ние ще се видим в понеделник.