Говорник: Добро, ова е CS50. Ова е крај на три неделно, а ако не се преземаа предноста веќе, знаете дека ќе има ручек овој петок, како и обично, каде можете да уживате во добар разговор и храна во Fire and Ice со некои од CS50 на вработените и соучениците. Се упатат кон овој URL тука. Сега може да се сети, или наскоро може да биде запознаен со тоа, овие работи тука, што се дадени на крајот на семестарот за многу часови. Т.н. испит сино книги, во кои пишувате вашите одговори на испити. Сега имам тука 26 како сини книги, на секоја од нив е напишано име, преку З И навистина имиња се толку едноставни, А преку З И еден од целите во рака денес ќе биде да продолжи со она што ние започна во понеделникот, што не е толку многу гледање на кодот, но навистина во потрага на идеи и решавање на проблемот. Една од целите и ветувања на овој курс е да се научи да се мисли повеќе внимателно, повеќе методично, и за решавање на проблеми поефикасно. И навистина, ние може да го направи тоа навистина дури и без допирање на линија код. Па имам неколку слонови до денес, портокалова и сина, ако ние би можеле да добијат еден волонтер, можеби од поназад од вообичаеното. Како за право, таму, ајде долу. Чија цел ќе биде да помогне плус управуваат овој испит тука. Што е вашето име? ПУБЛИКАТА: Мери Бет. Говорник: Мери Бет, ајде нагоре. Дозволете ми да го добиете микрофон тука за вас. Убаво да ви се исполнат. ПУБЛИКАТА: Убаво да ви се исполнат. Говорник: Добро, па морам тука сино книги преку Z, и јас одам да се преправам дека Имам еден од учениците, и тие доаѓаат во малку случајно на крајот од три часа испит блок, па тие се завршуваат во некои полу-случаен редослед како оваа. Сега вашата работа за само еден момент се случува да be-- ова е всушност начинот на кој тие се се претвори во на крајот на класата, најверојатно. Вашата работа сега се случува да биде, сосема едноставно, да се најде овие сини книги за нас од А до Ш ПУБЛИКАТА: Ох, ова е случува да се земе засекогаш. Говорник: И ние ќе се види како ќе го направите ова, без притисок. ПУБЛИКАТА: Не, не притисок или ништо. ЗВУЧНИЦИ: И за забава, ајде да се стави тајмер. ПУБЛИКАТА: Толку многу забава, толку многу забавно. ЗВУЧНИЦИ: Јас може да се одржи на микрофон за тебе. Добро, ние сме само двојно нашата брзина. Па во меѓувреме, дозволете ми да претставува она што е ќе биде прашањето за Мери Бет е она што таа го прави, како е таа ќе за решавање на ова? И всушност, не може да има некогаш сте размислувале за нешто толку едноставно како кога ќе ги собереш до 26 книги како оваа, кои немаат природна нарачување на нив. Што е процес кој всушност го користите? Тоа е прилично случаен само подигање првиот гледате и тоа ставање во своето место? Дали прво се движат вашите раце околу Барате потоа во потрага по Б? Фрлите поглед на пар од нив рамо до рамо и само велат, почекајте една минута, овој не е во ред, а потоа трампа на ред? Ние веќе видовме во понеделникот дека има голем број на начини во кој можеме да го направите ова, и навистина како што во близина на крајот тука, Јас би се забележи можеби на она што Мери Бет прави. Имаме неколку купови се чини, на поголеми еден, три помалите. ПУБЛИКАТА: јас сум ги наредил кога ќе се најдат две писма кои ги знам се заедно во низа, Јас ги стави заедно, така што јас не мора да се грижите за чување песна на цела редица книги. Тоа е само, ох, А е прво, Имам оваа оџакот тука. ЗВУЧНИЦИ: Значи, речиси како загатка парчиња кои имаат право облик се совпаѓаат со едни со други. ПУБЛИКАТА: Доста, да. ЗВУЧНИЦИ: Добро, одличен. И сега секоја од овие купови е веројатно подредени? ПУБЛИКАТА: Да. ЗВУЧНИЦИ: Сите во право, а преку З. Сите право, алал да му е, си го направила. Имате вашиот избор. Сино? Добро, ти благодарам за тоа. Така Мери Бет ги предложи што нејзиниот приод е, но она што е уште еден приод како можете може да се обратите за сортирање овие работи? Што би направиле? Рекорд да се победи би биле една минута и 50 секунди или така, плус оние заборавив да брои. Што би направиле? Да? ПУБЛИКАТА: Земете стек. Почне од почеток. Проверете ги вашите документи. И ако на врвот еден е повисока од, можеби, тие се, на дното еден е повисоки, а потоа ги префрлат. Говорник: Добро, така почнуваат на врвот и на дното, а потоа работи на вашиот пат увоз како што, Замена на нив? Добро, па малку слични во духот на меур вид, Но, изборот на крајности не соседните парови. Но помалку од тоа е дека има сигурно еден куп на различни начини ние би можеле да го направите ова, и искрено, мислиш вид на донесе неколку пристапи, нели? Сте го направиле вид на четири сортирани купови, и потоа ефикасно да ги спои заедно. И тоа е, daresay, друг техника заедно. Не сте го третираат како еден голем куп, ќе се подели на проблемот во четири quads, ако сакате, а потоа некако ги спои на крајот. Значи, да се разгледа, во крајна линија, Како инаку би можеле да го направите тоа. Ние формализиран поимот на меурот вид последен пат, и меур вид потсетиме беше алгоритам кој што се визуелизира со осум од соучениците тука, навидум случајно сортирани во прв. А ние потоа одлучи парови, ако два елементи се на ред, едноставно ги трампа. Значи четири и два се очигледно на ред, па овие две соученици вклучен позиции. И тогаш се повторува со четири и шест, потоа шест и осум години, на секоја итерација, се движи кон десно. Па со оглед осум лица, колку парови споредби направив при одење од лево кон десно во една таква повторување? Колку споредби? Седум, нели? Затоа што ако има осум луѓе, но мора пар нив и ќе продолжат еден хоп на правото, вие нема да има осум споредби затоа што не можат да се споредуваат елемент против себе, или што би само да се бесмислени, па имате седум. Или поопшто, ако имаме n луѓе, направи N минус 1 споредби со меурот вид. Па ајде да се разгледа сега како добри или лошо меур вид всушност беше и обидете се да се даде речник со каде што се критикуваа алгоритми вака, и наскоро нашите сопствени. Значи првиот минува низ меур вид, за прв пат Одев од лево кон десно низ фаза, ме N минус 1 споредби зеде. И што се случува да ми биде единица мерка, нели? Бев вид на зборување и шетање, малку брзо, малку бавно, па брои мојата бројот на секунди не е особено кажувам, но пребројување на бројот на операции што го направив во понеделникот, споредување на две лица, која се чувствува како убаво единица мерка. Па N минус 1 чекорите прв пат, но тогаш што се случи после тоа? Што е еден наопаку на еден поминат преку инаку несортиран листа? Што можете да ми кажете за елемент кој беше целиот пат таму? Да? Тоа беше најголемиот елемент, нели? Број осум, иако таа почна тука, секој пат кога нејзиниот споредба против сосед, таа се чува меури на правото страна на листа. И навистина, тоа е каде што алгоритам добила своето име. Сега со таа логика, колку споредби треба да направам за по втор пат Јас го направи тој додавање од лево кон десно? N минус 2, нели? Тоа само ќе се трошат моето време, ако јас задржи споредување осум против некого друг затоа што веќе знаете таа беше во право место. Па тоа е малку на оптимизација, па следниот помине се случува да бидат плус n минус два чекори, каде n е бројот на луѓето. Сега можете вид на може да се екстраполираат, дури и ако не си компјутерски научник, како тоа завршува. На крајот на овој алгоритам, веројатно имаш само една споредба лево. Мора да се вид на поправат почеток на листата во случај две и еден се надвор од и треба да биде еден и два, па ова задници надвор во плус 1 конечниот споредба. Сега точка, точка, точка вид на бранови тоа е раце на некои од juicier детали, но ајде да одиме напред и да се поедностави. Ако се сеќавате од високо училиште, искрено, многу од вас имаше математика книги кои имале малку измамник лист на предниот капак или на задниот капак што покажа она серија summations како Ова, конечно додаде до. Во случај, ако имате променлива како N, и навистина ова, ако сте виделе во вашиот старата школа математика книга, ќе видите дека ова, всушност, додава до оваа сума тука, n пати n 1 минус сите поделено со 2. Па за сега дозволете ми да пропише ова е вистина, па на скок на верата, тоа е она што ова го сумира до, и би можеле да докаже дека во една поопшта случај. Но сега да се прошири ова. Значи, да се мултиплицираат ова, па тоа е N на квадрат, минус n, сите поделено со 2. Тоа е навистина n квадрат, поделен со 2, минус n над 2, па тоа е убаво и интересно. Но, она што се случува ако ние сега plug-in-вредност? Да претпоставиме дека јас не имаат осум луѓе, но велат дека еден милион. И еден милион само затоа тоа е прилично голем број, ајде да го приклучиш дека во и да видиме што се случува. Значи, ако јас го приклучиш на милиони во таа формула Одам да се добие еден милион квадратни, поделен со 2, минус еден милиони, поделени со 2. Сега што е тоа што се случува да се изедначи? Па 500 милијарди долари, минус 500.000. И ако јас всушност не дека математика, дека средствата кои сортирање милион луѓе со меурот вид може да ме земе 499.999.500.000 чекори или споредби на крајот, ние сме само екстраполација. Кој се чувствува прилично бавно, но искрено мерење на еден одреден влез вака, не е на сите дека кажување. Но навистина тоа не укажуваат на тоа дека како n добива поголеми и поголеми, овој алгоритам вид на се чувствува полошо и уште полошо, или навистина почнете да се чувствувате болката на кои степенување, што n квадрат, што се сведува на прилично брзо. И овој детал не е загуби на луѓе, всушност Пред неколку години некој сенатор кој беше кампања, седна на интервју со Eric на Google Шмит, извршниот директор во тоа време, и бил предизвикан со прашање слично како што го истражуваат денес. Ајде да ги разгледаме. [Видео репродукција] -Senator, Ти си тука во Google, и ми се допаѓа да се мисли на претседателството како на интервју за работа. Сега, тоа е тешко да се добие работа како претседател, и си оди преку строги мерки сега. Тоа е исто така тешко да се добие работа во Google. Имаме прашања, а ние прашате нашите кандидати прашања, и овој е од Лари Швимер. What-- вие момци мислам дека сум шегувам, тоа е во право тука. Што е најефикасен начин да се сортирате милиони 32-битна цели броеви? -Well-- -I'm Жал, maybe-- Не, не, не. Мислам дека меурот вид ќе биде погрешен начин да се оди. Дојди на кој го овој кажа? Јас не гледам компјутер науката во позадина. -We've Добивме шпиони во таму. -OK, Ајде да побара друг интервју прашање. [END видео репродукција] ЗВУЧНИЦИ: Значи зборуваме за специфични броеви иако, нема да биде сето тоа корисно. Тоа не е живот лекција која меур вид, со оглед на милиони влезови, може да се земе како многу како 500 милијарди чекори. Вие навистина не може да се генерализира премногу ефикасно од кои и прават добри дизајн одлуки кога пишувате програми. Значи, да се фокусираат иако за тоа како ние може да се поедностави овој резултат. Па јас осветлени во жолто тука резултат на n квадрат поделен со 2, па еден милион квадрат поделено со 2, и потоа Сум Нагласени она што крајниот одговор беше откако ќе одзема исклучите N поделено со 2. И тврдењето јас ќе одам да направите сега е, Кој е грижам се грижи ако одземе исклучување малку стар n над 2, кога првата дел од оваа формула е многу поголема? Доминира со други рок, n квадрат поделен со 2 толку многу поголеми, јасно, како N добива големи како еден милион, тоа е навистина голема разлика на на крајот на денот помеѓу 500 милијарди и 499.999.500.000? Не, навистина. И така што ние ќе треба да направи што се компјутерски научници е игнорираме оние од понизок ред условите и се нешто како ова и навистина само да го поедностави до термин кој се случува да е важно. Поголемите нашите сетови на податоци се, толку поголем нашите бази на податоци да се добие, на повеќе веб страници ние треба да го бара, толку повеќе пријатели имате на Facebook. Како N добива поголема, ние сме навистина ќе се грижат за најголем термин во секоја таква анализа на нашите алгоритми перформанси. И јас одам да се каже, знаеш што, меур вид е од редот на големите О, од редот на N на квадрат. Тоа не е точно n квадрат, како што видовме, но кој навистина се грижи за оние кои се помали термини, и искрено, кои навистина се грижи ако ние подели со 2? Тоа е само постојана фактор. И е 500 милијарди наспроти 250 милијарди навистина толку голем договор? Јас само може да чека една година, нека ми лаптоп буквално добијат два пати побрзо во хардвер, и тој вид на разликата само оди далеку природно со текот на времето. Она што се грижат за е на изразување, дел на изразот што се случува да се разликуваат како наш влез добива поголеми и поголеми. И навистина, во реалниот свет, тоа е она што се случува повеќе е на влезовите на нашите проблеми и алгоритми се добива поголема. Толку голема О ќе биде нотација, на асимптотска нотација, дека ние само користат како компјутерски научници да се опише претставата, или трчање време, на алгоритам. Така што можеме да ги споредиме алгоритми на различни компјутери писмено од различни луѓе, со користење на некои суштински слични метрички како на бројот на споредби сте одлуки, или можеби бројот на свопови сте одлуки. Она што ние нема да Грофот е износот на времето која поминува на часовникот на ѕидот обично. Што ние нема да се грижите за е колку меморија што ја користите денес барем, иако тоа е Друг ресурс што може да се измери. Ние ќе се обиде да ги базираме нашите анализи за само основните операции, од оние, искрено, тоа може да се види поголемиот дел визуелно. Па со нешто како голема О на n квадрат, тврдам дека О од n квадрат е горна граница на т.н. трчање време на меурот вид. Со други зборови, ако сакаше да се тврди дека има оваа горна граница за тоа колку чекори алгоритам може да потрае, тоа се случува да биде во голема О на n квадрат во овој случај, горна граница. Што ако наместо промени Приказната да биде не за меур вид, но за оваа горна граница. Може да се мисли на алгоритам дека ние сме погледна веќе чија горна граница, максимум мерење на време или операции, би се вели дека се граничи од n, линеарна функција, не квадратна оној кој е закривен? Што е алгоритам што секогаш зема не повеќе отколку како n чекори, или 2n чекори, или 3N чекори? Да? ПУБЛИКАТА: Наоѓање на Најголем број во листата? ЗВУЧНИЦИ: Совршена, изнаоѓање најголем број од листата. Ако сум дадена листа на луѓе за пример, секој кој се држи голем број, она што е максималниот број на чекори што треба да ме земат, разумно паметен човек, да се најде најголемиот човек во таа листа? n, нели? Затоа што во најлош случај, каде што можеби најголемата вредност да биде? Добро, начинот на кој на крајот. Па во најлош случај горна граница, би можел да мора да одат сите на патот овде и да биде како, ох, тука е број осум, или што и да е вредност. Сега само би било глупаво ако јас се чуваат, нели? Во потрага по повеќе и повеќе елементи Ако последната од нив е таму? Па сигурно, n е горната граница. Јас не треба да се земе повеќе чекори од тоа. Па што ако, наместо предложив постојат алгоритми во овој свет, имаат трчање време, тоа е граничи со голема О на најавите n, n се најавите? Каде што не сме виделе ова порано? Да? ПУБЛИКАТА: Во книгата на телефонот проблем? ЗВУЧНИЦИ: Како телефонот книга проблем. Што е мерка за тоа колку многу време или колку солзи го ми требаше да се најде некој како Мајк Смит во книгата на телефонот? Ние тврдеше дека најавите n и дури и ако се запознаени или тоа е малку маглива што е логаритам или експонент беше, само се сеќавам дека најавите n генерално се однесува на процесот, во овој случај, на поделба нешто во половина повторно, и повторно, и повторно, и повторно, како што тоа станува се повеќе мали како да го направите тоа. Значи се најавите на n се однесува, да, на телефонот книга пример, на бинарни пребарување во теорија, кога ние имаше на Виртуелна врати на табла, или кога Шон беше во потрага по нешто. Ако имаше бинарни пребарување, влези n ќе биде горната граница на тоа колку времето што е потребно. Но, оние алгоритми кои трчаа во најавите n претпоставува што клучните детали? Дека листата е сортирана, нели? Вашиот алгоритам е во ред, ако вашиот влез не е сортирана, а сепак сте со користење нешто како бинарни пребарување бидејќи може да скокне право над елемент без реализација на тоа е навистина таму. Сега што ова може да значи голема О на еден? Тоа не значи дека вашиот алгоритам трае еден и само еден чекор, тоа само значи тоа трае константен број на чекори. Можеби тоа е 1, можеби е 10, можеби е 1000, но тоа е независно од големината на проблемот. Без разлика колку големи n е, постојана време алгоритам секогаш се ист број на чекори. Значи она што може да биде алгоритам ние разговаравме за или само интуитивно што доаѓа до вас, кои секогаш работи во т.н. постојани време? Да? ПУБЛИКАТА: Додади два броја. ЗВУЧНИЦИ: Додади два броја, 2 плус 2 е еднакво на 4, направено. Така што би можеле да работат, што друго? Како за повеќе реалниот свет, да? ПУБЛИКАТА: Наоѓање на Првото нешто во листа. ЗВУЧНИЦИ: Наоѓање на првиот елемент во листата, секако. Ние сме всушност зборува за низи веќе, како да добиете на Првиот елемент во низа, без разлика колку долго низа е во C код? Само користење како заградата нула нотација бам, ти си таму. И навистина низи, како настрана, поддршка нешто општо познато како случаен пристап, случаен пристап меморија, затоа што можете буквално Скокни на едно место. Можеме да го направите ова, дури и повеќе, едноставно можеме да ја премотам касетата до недела нула кога го правевме на гребење. Колку време не е потребно за велат блок во нула да се изврши? Само постојана време, нели? Се каже нешто, велат нешто, тоа не е важно колку е голема Гребнатинки светот е, секогаш е случува да се земе иста количина на време едноставно да се каже нешто. Па тоа е постојана време, но она што е на друга страна? Ако тоа беше горен граници, што ако сакаме за да се опише пониски граници на нашите алгоритми трчање време? Речиси најдобар случај потенцијално, ако сакате, иако овие термини може да се примени за најдобро случаи, најлошите случаи, просечната случаи повеќе Општо земено, но ајде да се фокусираат на пониски граници поопшто. Што е алгоритам што има пониска врзани на n чекори, или 2n чекори, или 3N чекори? Некои фактор на n чекори, тоа е нејзината долната граница. Да? ПУБЛИКАТА: меур вид? Говорник: меур вид се ќе минимално n чекори, зошто? Зошто е тоа така? Зошто треба дека почетокот да дојдам при вас интуитивно, дури и ако тоа не само уште? Да? ПУБЛИКАТА: [Беззвучен]. Говорник: Токму така. На најдобар можен сценарио на меур вид, и многу алгоритми, ако те предаде осум лица кои веќе се подредени, тоа би било глупаво за вас, алгоритам, да се оди напред и назад повеќе од еднаш, нели? Бидејќи веднаш штом ќе се прошетка низ листата еднаш, треба да сфатат, ох, се направени никакви свопови, оваа листа е сортирана, излез. Но, тоа се случува да ви n чекори земе. И обратно, што е уште еден начин на размислување за тоа? Меур вид е омега, така да се каже, на n, затоа што ако се погледне на помалку од n елементи, што е фундаментален проблем таму? Не знам дали тоа е сортирана, нели. Ние луѓето моќ поглед на осум луѓе и да биде како, ох, тоа е сортирани, тоа не ме n чекори ги преземе, но го направив тоа. Очите, дури и покрај тоа што вид на има големо видно поле, Дали сте го гледаше во осум елементи, Дали сте го гледаше во осум луѓе, тоа е осум чекори ефективно. И само ако чекорам низ целиот листа можам да сфатат, да, подредени. Ако престанам половина пат размислување, сите право, тоа е прилично подредени досега, Кои се шансите тоа не е сортирана? Тоа не алгоритми случува да бидат точни. Може да биде побрзо, но неточни. Така, сега имаме начин на опишувајќи пониски граници, А што е со постојано време? Што е алгоритам што има помал граница на своите работи време на еден? 1 чекор, 2 чекори, 10 чекори, но константна, независно од n, големината на влез? Да, во грбот. ПУБЛИКАТА: printf? Говорник: Што е тоа? ПУБЛИКАТА: printf? Говорник: printf. Добро, сигурно. Така што е потребно фиксен број на чекори. И јас треба да now-- сега дека ние зборуваме за C код и не нула, нешто како да речеме, со printf, ние треба да почне да се внимателни. Затоа што printf ги зема влез, тоа е стринг, и стрингови се технички имаат должина. Значи, ако ние сега сакаме да ги собереш за вас, ако не ти пречи, технички ние може да се тврди дека printf ги зема променлива должина влез, и сигурно тоа може да потрае повеќе време да се печати низа овој долг, од овој долг. Па што ако се има предвид само сортирање и пребарување примери? Што е со Мајк Смит во телефонот книга, или во бинарна пребарување поопшто? Во најдобар случај, она што може да се случи? Јас го отворите телефонот книга и бам, има број Мајк Смит. Јас може да го викаме веднаш. Направи еден чекор, можеби два чекори, туку константен број на чекори ако среќата ми се насмевна. И искрено, видовме на Понеделник вашиот соученик да се добие прилично среќен два пати по ред. И тоа беше навистина постојано Времето во долниот границите на алгоритмот во прашање за изнаоѓање бројот 50 зад тие затворени врати. Сега, како настрана, ако откријат дека двете големи О, горна граница, и омега, пониски врзани, се едно во истата, што е истата формула во загради, можете исто така да каже, само за да бидат фенси, дека нешто не е во тета на n или тета на некои други вредности. Тоа само значи дека кога голем O и омега се исти. Сега, она што за избор вид? Ајде да го користат овој нов речник. Во изборот на вид, што застанавме прави повторно, и повторно, и повторно? Јас требаше напред и назад преку на листата, во потрага за кого? Најмал број. Значи колку чекори, како многу споредби не јас треба да се направи со цел да дознаам кој најмалиот елемент во листата беше? N минус 1, нели? Затоа што ако јас само се започне со еден сум даде и да почнам него или неа споредување, тогаш на него или неа, го или неа, него или неа, јас само да се спарите елементи заедно n минус 1 пати. Па селекција вид на сличен начин се N минус 1 чекорите прв пат. Колку чекори не ме однесе до најдете вториот најмал елемент? N минус 2, затоа што јас сум се неми ако Продолжувам да гледа во истите луѓе повторно ако јас сум веќе го одбрани или неа и ги стави во нивното место. А третиот чекор, н минус 3, тогаш n минус 4. Видовме овој модел пред, и навистина Изборот вид слично има горна граница од n квадрат ако правиме се што збир. Каков е нејзиниот долната граница, селекција вид? Минимално, колку време мора избор вид преземе, како што го дефинира во понеделник? Предложи две опции. Можеби тоа е n, како порано. Можеби тоа е n квадрат, како што е сега како горна граница. ПУБЛИКАТА: N квадрат. ЗВУЧНИЦИ: N квадрат. Зошто? ПУБЛИКАТА: Затоа што имаат да се дефинира [Беззвучен]. Говорник: Токму така. Барем како што е дефинирано избор вид тоа беше прилично наивна, Продолжувам да одам, најде најмалиот елемент. Одиме повторно, се најде најмалиот елемент. Одиме повторно, се најде најмалиот елемент. Нема вид на оптимизација таму дека може да ме прекине по само n или така чекори. Па навистина, избор вид, омега на n квадрат. Што е со вметнување вид, каде што се кои ми беше дадена, а потоа го plopped или неа во право место? Тогаш ќе се продолжи со второ лице, plopped него или неа на вистинското место. Тогаш следниот лице, plopped него или неа на вистинското место. Забележете дека ова е многу линеарни, така да се каже. Јас сум права линија, јас сум не ќе напред и назад, Никогаш не сум гледајќи наназад, навистина, но она што се случува кога ќе го вметнете или неа во почетокот на листата што ние направивме за понеделник? Што се случува? Да? ПУБЛИКАТА: [Беззвучен]. Говорник: Да, тоа беше улов, нели? Може да се сети од соучениците, ако тие се прави движење со нивните нозе, тоа беше операција. Значи, ако имало три лица тука и нова личност припаѓале таму некаде, на долг сцената како оваа, секако, тој или таа може само да оди до самиот крај. Но, ако ние сме размислување за компјутер и низа на меморија, овие луѓе се случува мора да се влага преку да се направи простор за тоа лице. И така што n минус 1 shufflings, n минус 2 shufflings, n минус 3 shufflings е само вид на случува зад мене, а не пред мене како и досега, во некоја смисла. Сега како настрана, а како што може да се гледа на интернет ако почнете ѕиркаа наоколу за видови, има толку многу различни оние таму, некои од нив подобра од другите. Всушност, bogosort е еден тоа е вид на забава да се погледне нагоре. Bogosort зема збир на броеви или велат шпил од карти, по случаен избор ги меша, и проверува дали тие се подредени. А ако не, го прави тоа повторно. А ако не, го прави тоа повторно. Ако не, го прави тоа повторно. Неверојатно глупаво. И, навистина, ако го прочитате како на статијата Википедија, нејзиниот прекар е глупав вид. Тоа на крајот ќе работи, се надевам дека, со оглед на доволно време, но тој износ на време може да потрае подолго време. Значи, ако јас би можел, ајде да ги забрзаат работите за разлика од примерот Мери Бет претходно, со тоа што неколку повеќе елементи, но уште два процесори. Две лица, ако не би ум се приклучи мене. Како за 1, овде, и ајде go-- никој таму? Никој таму? Во ред. Ти со црна кошула, да, ајде долу. Добро, како се викаш? ПУБЛИКАТА: Петар. Говорник: Што е тоа? ПУБЛИКАТА: Петар. ЗВУЧНИЦИ: Питер, Давид, убаво да ви се исполнат. Добро, ние имаме Питер тука, ако сакаат да дојдат врз масата овде. И она што е вашето име? ПУБЛИКАТА: Елена. Говорник: Елена. Добро, убаво да ви се исполнат. Elena исполнуваат Петар. Петар, Елена. И ние ќе треба Ендрју до овде, ве молам. И вашиот предизвик се случува да се да се најде решение шпил карти. И ако се запознаени, палубата карти треба во крајна линија бидат подредени малку нешто како овој каде што ние ќе направиме клубовите, а потоа на лопати, тогаш срцата и дијаманти, од ace како еден, сите на патот до царот. Картички, ќе одам да ви даде се ќе биде 52 во квантитет. Ние ќе се слично Времето вас, за само еден момент. Ние ќе се фрли Ендрју на екранот овде, така што за да се види како ќе го направите тоа. И така што сето ова е сè повеќе и повеќе видливи, овие се карти добив на Амазон. Така што тие се веќе случајно подредени, и ние ќе ви време. И ние си оди за да задржи тоа реално ова време, па ние ќе се обидеме да ви притисок бидејќи во спротивно тоа ќе добиете мачна брзо. Ако може да продолжи да го решите 52 елементи заедно преку некои средства, сега. И повторно, како што ќе се види овие момци го направи она што, на крајот се случува да се произведуваат очигледен резултат на тоа, се размислува за навистина како тие се едни го прават тоа, како може да се опише. Затоа што, повторно, тие се сите процеси, алгоритми кои ги земаме здраво за готово како човек. Но, сте веројатно долго време имаше интуиција, долго дури и пред да мисли за преземање на компјутерски науки класа ќе може да имаат интуицијата со кој да ги реши проблемите вака. Но штом ќе се признае моделите и да започне формализирање на чекори со кои ќе бидете решавање на овие проблеми, ќе најдете дека може да се реши многу повеќе интересни и многу покомплексна проблеми брзо. Па некој од публиката, што е најмалку еден елемент на алгоритам дека тие се користат тука? ПУБЛИКАТА: [Беззвучен] Говорник: Што е тоа? ПУБЛИКАТА: По примерот. ЗВУЧНИЦИ: По примерот. Значи прво се кластерирање сите дијаманти заедно Се чини дека сите срца заедно се чини, и така натаму, без оглед за бројот на картички. И сега тие се појавуваат, на пример, да им се сортирате по број. Многу добар. Добро, така што ќе се биде последниот чекор, тогаш тука? Откако имаме четири сортирани костуми, што ние треба да направите за четири купови со цел да се постигне една подредени палубата, едноставно? Значи ние треба да ги спои повторно. Значи има една интересна идеја која повторно, daresay, е многу интуитивен, дури и ако никогаш не би можеле да удира таков вид на етикета за тоа. Овој основен поим на поделба проблемот не е во половина ова време, но барем во четири парчиња. Решавање доста фундаментално идентични проблеми во изолација еден од друг, а потоа спојување на резултатите. И, одлични, направено. Добро, голем круг на аплаузот, кога би можеле. [Аплауз] Говорник: Јас немам идеја што ќе врска со овие, но тука и да одите. Ви благодарам многу. Да видиме, две минути и осум секунди, ако сакате да ја оспори вашите пријатели. Што тогаш се случува да се да биде се далеку од оваа дека можеме да потпора поопшто? Па, се сетам на оваа низа од броеви, и се сетам сега на некои од pseudocode ние сум напишал во минатото, и тоа беше pseudocode за решавање на телефон книга проблем. При што во pseudocode јас набројани повеќе методичен начин на опишување како што го направив многу интуитивен човечки алгоритам на поделба на телефон книга на половина, повторувам, повторувам, повторувам, додека не се најде некој како Мајк Смит, ако тој е навистина во телефонот книга. Но јас вид на користат она што ќе го наречеме многу итеративен пристап тука, особено известување алинеја 8 и линија 11. Тие се доказ за итеративен пристап, looping пристап, бидејќи тоа е токму однесувањето тие да предизвикаат. Оние линии и каже да одат во вид линија три, и може да се на мислам на тоа во вашиот око ум, како да бидат јамка. Тоа е ти го кажувам да се врати до чекор три и повторувам, повторно, и повторно, и повторно. Но, што ако ние потпора клучна идеја тука дека ние не последен пат, и поедноставување на линија 8 и линија 11 и нивните соседи како само тоа, во жолта боја. Тоа не е фундаментално скратување на pseudocode многу, но тоа е фундаментално менување природата на мојата алгоритам. Она што јас сега велат во чекор 7, во чекор 10, е да се бара за Mike во точно ист начин, но само во левата половина или десната половина. Значи со други зборови, ако Јас се започне од првиот чекор, земам телефонот книга, отворен за средината на телефон книга, погледнете имиња, ако Смит е меѓу име, јавете се на Мајк, друго ако Смит е порано во книгата, чекор седум пребарување за Мајк во левата половина од книгата. Но тој вид на се чувствува како тоа ме остава виси, нели? Во жолта боја, е настава, но како можам пребарување за Мајк во левата половина од книгата на телефонот? Каде можам да имаат алгоритам со кој јас да пребарувате за некој како Мајк Смит? Па, тоа е ни загледан во лицето. Јас буквално може да се користи иста програма за ефикасно ќе до врвот повторно и повторно трчање исто линии на код. Па иако ова треба да се чувствуваат како малку на циклична дефиниција каде што сте одговарање некој е прашање од страна на само еден вид на поставување истото прашање повторно, како зошто, зошто, зошто? Реалноста е затоа што ние сме хард кодирани неколку специјални линии, чекор 4, кој е, ако, и чекор 12, која е ефективно друга гранка, бидејќи имаме оние привремена мерка мерки, овој алгоритам ќе се прекине ако се најдете Мајк, или, ако ние не се направи. Но, во чекор 7 и 10 сега, имаме она што ќе го наречеме рекурзивен алгоритам. И рекурзијата е навистина моќна идеја тоа е малку умот свиткување на прв, дека ние сега можат да аплицираат на следниот начин. Се спојат вид ќе биде последен вид што гледаме, барем во класа формално. И тоа е фундаментално различно од оние последните три, и, секако, последните четири ако ги вклучиме bogosort. Тука е pseudocode за спојување вид. Кога на влез на n елементи, па со оглед на низа на големина n, ако n е помалку од 2, се вратат. Па зошто имам тоа разумност провери прво? Што е импликација ако те предаде низа чија должина n е помалку од 2? Тоа е веќе сортирани, очигледно, нели? Бидејќи на листата или има еден елемент, кој е тривијално подредени, бидејќи тоа е единственото нешто таму. Или, тоа е на големината нула што значи нема ништо да се најде, па по природа тоа се подредени. Има само ништо не е во ред таму. Па тоа е нашата т.н. база случај. Кој е сличен дух на она што го направив со Мајк. Ако Мајк во книгата на телефонот, му се јавам. Ако тој не е таму, да се откаже. Тоа е т.н. база случај, да бидете сигурни дека овој алгоритам на крајот на денот ќе престане во одредени околности. Но, тука е скок на верата сега, друго, сортирате левата половина од елементите, потоа ги сортирате право половина од елементите, а потоа се логирате на подредени половини. И тука е местото каде што таа се чувствува како ние сме copping надвор. Сум те праша да се најде решение n елементи, и јас сум велејќи дека, во ред, го на сортирање лево и сортирање право. Но велам дека еден друга работа, а тоа е клучна тема се чини во интуиција досега, има овој трет чекор на спојување. Кој и покрај тоа што изгледа толку глупава во духот, како само се спојат работи заедно, се чини да биде клучен чекор кон повторно монтирање на два проблеми кои беа поделени на крајот на половина. Па се спојат вид, да го направите ова, дали ќе хумор мене, со уште една демонстрација, само така што ние имаме некои броеви да се работи. Може ли да се разменат осум стрес топки за осум луѓе? Добро, како за тебе три, четири во овој дел, пет, шест, и ајде да се 7, 8, ајде нагоре. Во ред, да во ред. Минус 8, таму ќе одиме, плус 1. Одличен. Добро ајде нагоре, да брзо ви даде бројките. Број два, број три, број четири, број пет, шест, седум, осум и. Го направив осум правилно тоа време. Добро, па оди напред ако може, и ајде да се најде решение во оригиналната ред што имавме вчера која изгледаше вака, ако не би ум. И ајде да го направиме тоа во предниот дел на табелата. Добро, така се спојат вид. Ова е местото каде што се случува да се добие вид на интересни, затоа што се чини дека се даваат себеси толку многу помалку информации денес. Па се спојат вид прво на сите на влез на n елементи, и очигледно не помалку од два, тоа е осум, па имам некои повеќе работа да се направи. Па сега ментално ние како класа сега се во друго колено, што значи три чекори. Прво, морам да ги сортирате левата половина од елементи. Па како можам да се обратите за тоа? Па, јас ќе одам да се вид на ментално делат на листата тука, не мора да се физички да се движи, и јас сум ќе се фокусира само на Левата половина од елементите тука. Па како можам да се обратите за сортирање листа сега на големината четири? Што ми е алгоритам? Прво проверете е n помалку од две, не, па јас продолжи кон друг блок повторно. Вид левата половина од елементи. Па сега повторно, ментално, и ова е местото каде што што треба да се таложи многу ментална историја, ако сакате. Сега сум сортирање левата половина од левата половина. Добро, па сега јас го нарекувам мојот истата спојување сортирање алгоритам, е N помалку од два? Не, тоа е два, па морам да се најде решение на левата половина, а на десната половина. Значи тука ќе одиме, сортирање левата половина. Зошто не само се земе еден чекор напред. Што е вашето име? ПУБЛИКАТА: Дарен. Говорник: Ден. Дан истапи. ПУБЛИКАТА: Дарен. ЗВУЧНИЦИ: Дарен, направено. Рековте Дарен или Дан? ПУБЛИКАТА: Дарен. ЗВУЧНИЦИ: Дарен. Во ред, Дарен ја засили напред и сега подредени. И ова е речиси пуст барање, нели? Јас навистина не чини да се постигне ништо, но, ајде да се продолжи. Сега дозволете ми да го решите право половина на елементи. Што е вашето име? ПУБЛИКАТА: Лука. Говорник: Лука. Ајде, чекор напред. Направено, јас се подредени Лука. Левата половина сега сортирани и десната половина сега подредени, но повторно, има клучен чекор тука. Што ми е следната треба да направите? Спојување на подредени половини. Сега ние ќе едноставно мора сите напред и назад во овој начин, бидејќи јас вид на потребна некои нула простор. Тоа е речиси како овие момци се на маса, и ми треба некоја соба да им се движи околу натаму. Значи, ќе одам да се логирате вие момци со гледање на левата половина и десната половина. И кои очигледно доаѓа прво, остави половина или десната половина? Па десната половина, па ајде да се движат Лука во текот тука во првобитната положба на Darren. И сега да се спојат нивните левата половина, Дарен се случува да се движат во право таму. Така се чувствува како речиси ефект меур вид, но ми основните алгоритам, многу различни овој пат. Но, сега е каде што нештата се малку досадни затоа што треба да ја премотам касетата ментално каде го оставам надвор. Јас сум само се спои со сортирани половини, што значи јас сум каде што во мојот алгоритам? Морам да го решите десната половина, нели? Ако ја премотам касетата, буквално на видеото, ќе види дека стигнавме до ова точка на Лука и Дарен од страна на сортирање од левата половина од левата половина. Тогаш ние се спои оние сортирани половини, кои значи следниот чекор е вид на десната половина на левата половина. Добро, па ајде го направите тоа побрзо. Добро, шест, јас ќе одам да се тврди вие сте сега подредени, ајде напред. Што е вашето име? ПУБЛИКАТА: Адријано. Говорник: Адријано. Адријано сега подредени. И она што е вашето име? ПУБЛИКАТА: Алекс. ЗВУЧНИЦИ: Алекс е сега подредени. Остави половина, десната половина, што е последниот чекор? Логирате. Прилично тривијална, па јас сум ќе се спојат во шест, преземе чекор назад, осум, да направиме чекор назад. А сега го забележуваат тоа е корисна готова брза, што е сега вистина за левата половина од листа, без оглед на тоа како почнавме? Тоа е сортирана. Сега тоа не е сортирана во големата шема на нештата, но тоа е сортирана независно на другата половина. Сега што чекор сум за ако јас ги замотуваат како започна приказната? Сега морам да ги сортирате десната половина. Па сега ние сме начин назад во На почетокот на приказната, и да го направиме тоа побрзо. Па јас ќе одам да ги сортирате десната половина на целата листа. Што е следниот чекор? Сортирате остави половина на десната половина. Сортирате левата половина од левата половина на десната половина. И она што е вашето име? ПУБЛИКАТА: Омар. Говорник: Омар, чекор напред, направено. Левата половина е сортирана. И она што е вашето име? ПУБЛИКАТА: Крис. Говорник: Крис, да направиме чекор напред, вие сте сега подредени. Што е клучен чекор сега? Логирате. Па еден ќе се спојат во место тука, ако може да се преземе чекор назад, и три ќе се да направиме чекор назад, се спојуваат. Значи левата половина од десната половина, сега се подредени. Искрено, овој алгоритам се чувствува како ние се трошат начин повеќе време отколку порано, но ако се направи тоа во реално време, ние ќе да видиме што takeaways и ќе биде. Сега јас сум тука, нели половина на десната половина, дозволете ми да оди напред и да се најде решение на левата половина. Чекор напред, како се викаш? ПУБЛИКАТА: Ремзи. Говорник: Ремзи сега подредени. Што е вашето име? ПУБЛИКАТА: Марина. Говорник: Марина сега подредени како Па, ако се земе еден чекор напред. Клучен чекор тука е сега се спојат, јас сум ќе се извади од моите две листи, лево и десно. Пет се случува да дојде прв, и седум се случува да дојде следната. И повторно, ова е намерно. Фактот дека тие се презема чекори напред и назад е со цел да се претставуваат дека не можеме направи овој алгоритам во место како лесно како меур вид, и селекција вид, и вметнување вид, каде што само чуваат Замена на луѓето. Јас буквално треба еден вид на нула хартија во која да се стави овие луѓе додека јас го направи спојување, а потоа можам да ги стави повторно во место. И тоа е клучен, бидејќи јас сум со користење на нови ресурси, простор, а не само време. Добро, ова е неверојатно. Левата половина е сортирана, десната половина е сортирани, сега дека клучните спојување чекор. Како јас ќе се спојат ова? Значи, ако ќе го следат мојот левата рака и десната рака, Одам да истакнам мојата лева рака на левата половина, мојата десна рака на десната половина, а сега морам да одлучи чекор по чекор кого да се спојат во. Кои очигледно доаѓа прво? Број еден. Па ајде овде, тука е нашата мечокот. Па сега број еден, и известување она што ќе се прави со мојата десна рака, Одам да се движат десната рака еден чекор во текот на точка број три, и сега јас треба да се направи истата одлука. И всушност стојат право во пред Лука тука, ако може, бидејќи тоа е нашата мечокот. Значи, кој доаѓа следно? Имаме Лука со број два или Chris со бројот три. Очигледно Лука, број два, па ќе дојдеш тука. Но мојата лева рака сега ќе се зголемува за да се укаже на Дарен, и тука е клучот земе со спојување, јас ќе одам да се задржи тоа, Очигледно, ако вид на следат логиката. Но моите раце не се ќе одат наназад, што значи јас сум само некогаш се пресели во по лева страна со мојата спојување процес, и дека ќе биде клучот за нашата анализа во само еден миг. Па сега ајде да го завршиме ова брзо. Па три следува, потоа четири следува, а сега пет доаѓа следната, а потоа шест, и седум, а потоа конечно осум. Се чувствува како што е најмал алгоритам уште, но ако не ние, всушност, се кандидира тоа во истиот вид на часовникот брзина, така да зборуваат, со истата темпирана часовник како порано. Зошто? Па, ајде да ги се погледне на крајниот резултат. Да се ​​вратиме тука, дозволете ми да повлече до демонстрација визуелно од она што го направија. Зумирање тука, на оваа страница тука, кажувајќи Firefox дека сакаме да чекаат во оваа кутија, ајде да велат меур вид, со што ние сме сега е добро познато, Изборот вид, што е уште еден прилично јасна една, и сега денес се спојат вид, која ќе биде нашиот climactic крај. Причината зашто беше потребно толку многу подолго тука со луѓето и мене вербално е, очигледно, јас сум објаснувајќи секој чекор. Но, ако едноставно се изврши оваа, многу како што правевме меур вид и избор вид не само визуелно, види колку многу поефикасно овој проширува на поделба и освојување може да се кога се применува на податоци кои е дури и големината осум, но дури и многу, многу поголем. Јас ви даде спојат вид, од страна на страна со овие други алгоритми. Ова се случува да се болни брзо, и на крајот не е особено climactic, тие само се заокружи подредени. Но клучот се земе е во тоа што Види колку многу побрзо се спојат вид беше, освен ако не мислиш дека сум само вид на Месинг со вас. Ако го правиме тоа една конечна време, Ајде да ја превчитате ова, да се вратиме и изберете меур вид, и само за клоци, ајде да се избере вметнување вид, само за добра мерка. И овој пат, да изберете логирате сортирање и ајде да всушност работат овие рамо до рамо. И тоа не е, всушност, среќа. Она што го направи е ефикасно сум поделени мојот влез за половина, повторно, и повторно, и повторно. И има само толку многу пати може да се делам твоето влез во половини, лево и десно. Која е формулата што ние ги гледаме кој го опишува поделба на половина повторно, и повторно, и повторно, и повторно? ПУБЛИКАТА: Логирај n. ЗВУЧНИЦИ: Логирај n. Но тогаш има еден друг клучен чекор, овој алгоритам не е да се најавите n чекори. Ако тоа беа само се најавите n чекори, ние ќе бидеме во истиот проблем како порано, каде што не може да биде сигурни сè е подредени. Мора да се погледне во минимално n елементи за да бидете сигурни n елементи се подредени, инаку тоа е скок на верата. Така, тоа е минимално најавите n чекори, но она што за овој клучен спојување чекор каде што спојува левата половина и десната половина и шеташе на сцената? Колку чекори е дека за да се спојат? Тоа е n, но јас не само што се спојат финалето време. На секоја од овие вгнездени повици, за секоја на оние вгнездени спојувања, јас се уште подредени. Јас спои овие две момчиња, а потоа овие две момци, а потоа овие две момчиња и така натаму. Па јас не се спојуваат повторно и повторно. Колку пати? Така што секој пат кога ќе се подели на листа на половина, јас не се логирате. Подели на листата на половина, се направи спојување. Значи, ако поделба на листа може да се направи најавите n пати, и спојување на крајот се n чекори, што може да биде сега горниот обврзани на водење време на нашиот алгоритам? n најавите n. И навистина, тоа е она што ние го постигнавме тука. Па чувство дека гледате визуелно кога овие три работи се кандидира рамо до рамо е N на квадрат против n квадрат против n најавите n. Која што темелно ќе видиме, не само денес туку и во иднина, е многу, многу побрзо. А аплауз за овие момци, Јас ќе ги наградат со стресот топки. Ајде да го одложи тука денес, и ние ќе се видиме во понеделник.