>> [Музички]
>> Дејвид Џ MALAN: Во ред.
Па добредојде назад.
Ова е CS50, и е на крајот од третата седмица.
>> Па се потсетиме во последните неколку недели, ние сме биле трошење доста
време на C, на програмирање, на синтакса.
И тоа е сосема нормално, ако сте уште бори со проблемот Постави 2, за да биде
удира главата од ѕидот.
Тоа е криптичната изглед пораки за грешки и грешки кои ви
не може сосема потера надолу.
Бидејќи, остатокот увери, дека во само неколку недели "време ќе се погледне назад на
работи како Цезар, и [? V-genair,?] можеби дури и Crack, и
сфаќаат колку далеку си дојден во краток временски период.
Па ако тоа е некаква утеха, висат во таму сега за сега.
>> Денес, иако, да почнеме да транзиција да работи на повисоко ниво.
И ние почнуваме да се земе здраво за готово дека вие момци знаат како да програма, или во
барем почетоците на дека удобност ниво.
И ќе почнеме да се разгледа како можеме да одат за дизајнирање на програми повеќе
ефективно.
Како можеме да одиме за оптимизирање на ефикасноста на нашите алгоритми, и
генерално решавање на повеќе интересни проблеми.
И почнува да се земе здраво за готово дека, ако сакавме да, би можеле да се код на која било
од примерите што ја имаме во умот.
Така, денес, ние не допирајте ја тастатурата за било каква форма на код.
Тоа ќе биде многу повисоко ниво, а во крајна линија, за решавање на проблемите.
>> Па да се дојде до тој момент, дозволете ми да предложат дека следните седум
правоаголници претставуваат седум врати, зад кои се цел куп
броеви, меѓу кои е бројот 50.
Дозволете ми да проектираат тоа на овој екран и тука.
И предложи дека ние треба волонтер за да ми помогне да најдете голем број пред
на интернет тука за да ја видите.
Ајде горе, во розова.
Сите во право.
Што е вашето име?
>> JENNIFER: [нечујни]
>> Дејвид Џ MALAN: Молам?
>> JENNIFER: Џенифер.
>> Дејвид Џ MALAN: Џенифер.
Сите во право, Џенифер.
Убаво да ви се исполнат.
Ајде горе.
Па овие тука се седум порти, и она што Би сакал да го стори за нас овде,
пред сите на своите соученици, ни се најде бројот, 50.
Да се ​​најдат голем број, можете да ѕиркаат зад било која од овие врати со едноставно прислушување
на една од вратите, и тоа ќе се открие нејзиниот број.
И да видиме колку брзо ќе може да ни се најде бројот, 50.
>> 15.
16.
50.
Убаво направено.
Сите во право.
Аплауз за Џенифер.
>> [Аплауз]
>> Сите во право.
Значи она што беше вашата стратегија за наоѓање на бројот, 50?
>> JENNIFER: Хм, мислев дека можеби ако -
[Нечујни]
>> Дејвид Џ MALAN: О.
Го даде една секунда.
Така беше вашата стратегија за наоѓање на бројот, 50?
>> JENNIFER: Па јас само започне во почнуваат да се види она што го првиот број
беше, и тогаш си помислив, можеби ако тие се подредени, јас само ќе ги задржи
прислушување повисоко?
>> Дејвид Џ MALAN: OK.
И се чини дека го пронашле дека за да биде случај.
Иако, ајде да лупам назад на слоеви само малку, а вие сакате да одите
напред и да открие други врати можете да ја одбрале?
>> JENNIFER: Ох, драга.
>> Дејвид Џ MALAN: Ах.
>> JENNIFER: Па јас само се насмевна.
>> Дејвид Џ MALAN: Значи ли среќа.
Сите во право.
Па не е лошо.
Но тоа е интересна увид, нели?
Ако се претпоставува, а ти не добие, навистина, малку среќа таму.
Но ако се претпостави дека броеви беа сортирани, можете да бидете попрецизни
за тоа како тоа влијаело вашето однесување?
>> JENNIFER: Значи, ако тие беа подредени, јас дека можеби најмалите до најголемите.
>> Дејвид Џ MALAN: OK.
>> JENNIFER: Или ако тоа заврши се навистина голема, а потоа најголемиот до најмалиот.
>> Дејвид Џ MALAN: OK.
Па најголемиот до најмалиот, или најмалите до најголемите.
Но, дозволете ми предложи, да претпоставиме дека имале добивано и несреќен, и претпоставувам дека тие
не беа, всушност, подредени, колку од тие врати може да сте имале да ѕиркаат
зад себе во кој најлош случај?
>> JENNIFER: Сите од нив.
>> Дејвид Џ MALAN: Сите од нив.
Па ајде да се генерализира дека како n.
Таму се случува да биде 7, но ајде повеќе обично велат дека е n врати на
екранот овде.
Па во најлош случај, ќе треба да се погледне зад 7 врати, или n врати.
И така тоа навистина е, тоа е малку среќа денес, но тоа е навистина една линеарна
алгоритам на сорти, дури и ако беа вид на скокнеш наоколу.
Е тоа фер?
>> JENNIFER: Да.
>> Дејвид Џ MALAN: Па, дозволете ми да се види ако вашиот стратегија промени, ако јас се движат од нас да
нашиот втор пример тука со 7 различни врати.
Истите броеви, но ова време тие се подредени.
Која е вашата стратегија тука ќе биде, обидуваат да се стави надвор од вашиот ум она што
другите броеви беа -
>> Џенифер: Добро.
>> Дејвид Џ MALAN: - порано?
>> JENNIFER: Да почнеме со првиот.
>> Дејвид Џ MALAN: Во ред.
Започнете со првиот.
4.
Сега каде ќе одиш, и зошто?
>> JENNIFER: 4 е навистина мал.
Значи, ако тие се вид можеби најмалите до најголемите, што треба
да биде двојно, и -.
>> Дејвид Џ MALAN: OK.
Ајде да видиме, кој мислите?
>> JENNIFER: Обидете последен.
Убаво.
>> Дејвид Џ MALAN: Многу убаво направено.
Сите во право.
>> [Аплауз]
>> Дејвид Џ MALAN: OK.
Па ти си, всушност, го прават тоа ужасно, затоа што ти си
го прават тоа многу добро.
Кои нè остава во состојба да направи одредени точки.
Па ајде да се обидеме да се тркалаат назад тука.
>> Џенифер: Добро.
>> Дејвид Џ MALAN: Многу добро направи, сеедно.
Па ти почна на почетокот, те видов дека тоа беше 4, тогаш
пресели на крајот.
Но да претпоставиме дека не се среќни таму, и да претпоставиме 50
беше некаде на друго место.
Што вашиот Третиот чекор биле?
>> JENNIFER: Врати се на почеток.
>> Дејвид Џ MALAN: Одете назад на почеток.
Добро, така што ќе го допре оваа врата, која беше 8.
Сите во право.
Па тоа не е 50.
Каде што ќе се загледа следно?
>> JENNIFER: Ако јас не знаат дека подредени.
>> Дејвид Џ MALAN: Точни.
Па, ако не знаете тие беа сортирани -
>> JENNIFER: О, знаев, да.
>> Дејвид Џ MALAN: - Но, вие не знаат каде 50 беше уште?
>> JENNIFER: Само продолжувам да одам.
>> Дејвид Џ MALAN: Во ред.
OK.
Продолжувам да одам.
Добро, дека јас може да работи со.
>> Џенифер: Добро.
>> Дејвид Џ MALAN: Сега, ако ти си само случува да Продолжувам да одам, она што е вашиот
алгоритам префрлени поддржани во.
>> JENNIFER: Линеарната -.
>> Дејвид Џ MALAN: Тоа е вид на линеарна.
Но, дозволете ми предложи, ајде да ме стави на самото место.
Дозволете ми да се освежи страница.
истиот број, истиот аранжман, исто врати.
Но се сетам на тој прв ден во класа кога ние раскина телефон книга во
половина, вид на, и она што беше нашата стратегија таму?
>> JENNIFER: Почеток на средината.
>> Дејвид Џ MALAN: OK.
Па почнуваат во средината.
Па ајде да одиме напред и да симулираат тоа.
Започне во средината откривајќи дека вратата.
Така што бројот 16.
Па што би силната дечко го направиле, кој раскина на телефонот книга на половина,
да се стигне до следната претпоставка?
>> JENNIFER: Оди во оваа половина.
>> Дејвид Џ MALAN: И зошто на правото?
>> JENNIFER: Ако тие беа вид на најмалите до најголемите, а потоа 50 треба да биде
во тој крај.
>> Дејвид Џ MALAN: Добро.
Сосема разумни.
Па како телефон книга, ќе се обратите на право, за разлика од левата страна, но тука
е клучот готова брза.
Сега можете да фрлаат, или откине, половина од овој проблем, оставајќи не сте
со 7 врати, но навистина со само 3.
Што е приближно околу половина од големината на проблемот.
Сите во право.
Па сега што ќе треба направи откако ќе одат нели?
>> JENNIFER: Значи 16 се уште е прилично мал, во однос на 50, па можеби и јас ќе се обидам,
како, и оваа.
>> Дејвид Џ MALAN: Во ред.
42.
Добро, па сега она што е вашиот инстинкт ви кажува?
>> JENNIFER: Јас може да се фрлаат ова, а потоа само -
>> Дејвид Џ MALAN: OK.
Добро, може да се фрлаат на левата половина таму.
>> JENNIFER: - Изберете оваа.
>> Дејвид Џ MALAN: И во право.
>> JENNIFER: Да.
>> Дејвид Џ MALAN: Значи, иако тоа е тешко за да го видиш можеби, кога има само
7 врати, се размислува за, сега, конзистентноста на
Алгоритам Вие само применуваат.
Во претходниот случај, ти го направи ќе имаат среќа, која беше одлично.
Но вие не се користи хеуристичка, Јас би рекол.
Сте користеле вид на вашите инстинкти, и знаејќи дека подредени, ако тоа е прилично
мали на почетокот, очигледно, ние сме Мора да одам повеќе на десно.
Но, во извесна смисла, имаш среќа, затоа што можеби ова беше бројот 100,
а можеби и 50 беше повеќе во средината.
Можеби 50 беше дури и овде.
>> Но, она што ти го направи малку поинаку овој пат беше, ти го направи истото
повторно и повторно.
И јас би рекол дека она што сте само се, иако под влијание од страна на телефонот
книга пример, е нешто многу повеќе алгоритамски, и многу
намалена за посебната латински.
Многу помалку инстинктивно.
Па на крајот на денот, како би опишуваат вас на ефикасноста на
првиот алгоритам, каде што ќе отиде лево кон десно, наспроти
вториот алгоритам тука?
>> JENNIFER: Ова треба, како, можеби преполоват време, или дури и повеќе, да.
>> Дејвид Џ MALAN: Добро, можеби дури и повеќе.
Ајде да им помогнам малку потешко за тоа.
Што, навистина, ако продолжиме со ова логика, ние дефинитивно ја преполовиле
трчање време со овој втор алгоритам од фрлањето на половина од
броеви, но она што го правиме на следната повторување, кога Џенифер откри
вториот број?
>> Ние преполовен бројот на врати повторно.
А потоа она што го правиме после тоа, ако имало повеќе врати да си игра со?
Ние ќе ги преполови, и повторно, и повторно, и повторно.
И тоа беше исто како вие момци сите стои во првата недела од
класа, половина од вас седи долу, половина од вас седи долу, половина од вас
седнува, се додека еден осамен душата стоеше.
И ние рече дека трчање време на тоа, бројот на чекори што го зеде беше
од редот на што?
>> ЗВУЧНИК 1: [нечујни]
>> Дејвид Џ MALAN: Значи најавите база 2 од n, или само повеќе, едноставно, се логираат на n.
Па нешто логаритамска.
И графикон не беше права линија дека само што влегов полошо и полошо, тоа беше
овој интересен крива што не добие толку лошо со текот на времето.
Па ајде да се држи до оваа идеја.
Да му заблагодариме на Џенифер.
Благодарение толку многу за доаѓање на до.
И, еден сек.
Нема биро светилки денес, но ние немаат CS50 стрес топки.
>> JENNIFER: Yay.
>> Дејвид Џ MALAN: Добро, тука.
Ви благодариме за incurring на стресот до тука.
Сите во право.
Да видиме дали можеме да го сега формализира ова малку повеќе.
Па уште еднаш, она што ние едноставно го направив беше суштина истото како ние го сторивме
во таа прва недела.
Но, наместо да заврши со само еден линеарен алгоритам, кој ние прикажан
претходно како оваа права линија, при што, ако се стави уште една врата на
на екранот, а потоа Џенифер би имале да се погледне, потенцијално,
зад една врата.
Ако се стави уште две врати, таа може да имаат да се погледне зад две врати.
>> И така, имаше оваа линеарна односот помеѓу големината на
Проблемот на, да речеме, на x-оската, и износот на времето потребно да се
решавање на y.
Но сликата ми беше алудирајќи на порано беше оваа зелена линија.
Зелени намерно, затоа што тоа само се чувствува подобро.
Во теорија, алгоритам, кога ние го сторивме со книгата на телефонот, кога ние го сторивме
со вас момци броење едни со други, и во вториот случај, кога Џенифер само
тоа го правеше до тука, тоа беше вид на фундаментално подобро.
Затоа што тоа не е само два пати побрзо.
Тоа не беше дури четири пати брзо.
Тоа беше целосно зависни од она што големината на влез беше, за тоа како многу
чекори што во крајна линија зеде.
>> И така оваа едноставна идеја дека сите ние се здраво за готово со телефонот книга,
Слично на тоа може да се примени да нешто како ова.
И ова може да биде повеќе патемно познат како, како што може
замисли, поделба и освојување.
Не за разлика од она што го правевме, се разбира, со телефонот книга.
>> Но pseudocode, се потсетиме, беше ова.
Па ние не ќе го направат тоа повторно, но се потсетиме дека првата недела, на сите нас застана
а потоа половина од вас седна, половина од можете седна, половина од вас седна.
Дека алгоритам е реализиран во малку на мамење начин, во тоа,
не беше само една од мене броење, фундаментално, поефикасно.
Во тој случај, јас бев проширува средно ресурс.
На некој начин, повеќе процесори, повеќе мозоци, повеќе паметни луѓе во
соба беа помагање на мене да се добие од нешто линеарно на нешто
логаритамска, од нешто црвена до нешто зелено.
>> Но во овој случај, Џенифер сам може да фундаментално подобрување врз
изведба на нејзиниот прв алгоритам со, повторно, само размислување малку потешко.
И сега, кога станува збор време да се имплементираат овие работи, да пронајдат
она линии на код може да напише како дека можете да ги повтори, и
повторно, и повторно, вид на во looping модата.
Затоа што не си оди за да имаат луксуз, како Џенифер го направи на прво, за да
само имаат целиот куп на IFS и се каже, хм, ако овој прв број е 4,
дозволете ми да скокаат по целиот пат до крај.
Ooh, ако тој број е преголем, дозволете ми да се движат произволно назад
до вториот елемент.
Ќе најдете дека тоа се случува да биде многу потешко да се формализира она што ние, луѓето
земе здраво за готово како многу разумна хеуристичко, но компјутерот е само
случува да направи она што вие го каже да го стори.
>> Сега ова многу интересно импликации.
Овој графикон е вид на замислена за сортирање на победат визуелно, но оглас, каде
е права линија во овој графикон?
Каде е линеарна графикон што ние го нарекуваме N?
Па, тоа е вид на кон дното на оваа слика, нели?
Така што сите ние го направивме е ние сме вид на zoomed надвор на x-оската и
y-оската да се обидат да се добие чувство на она што други видови на криви изгледа.
>> И спецификите на математички изрази денеска не е важно толку
многу, но забележите дека има многу алгоритми кои се далеку полоши од
нешто што е линеарна.
Навистина, n коцки изгледа прилично лошо.
2 до n изгледа прилично лошо. n квадрат изгледа прилично лошо.
И ќе видиме што некои од оние може да биде во денешната реалност.
И да се најавите n не се чувствува како лоша, но подобро отколку n е најавите база 2 од n.
Но, знаете, тоа би биле дури и повеќе зачудувачки ако Џенифер, или, ако ние,
дека првата недела, се дојдени со нешто што е дневник на најавите на n.
>> Значи со други зборови, има целата оваа опсег на можни решенија за
проблеми, но дури и тука, најава што ќе се случи.
Кога јас одзумирате, кој од овие криви се случува да се докаже да биде апсолутна
најлошото од оние на екранот сега?
Значи n коцки изгледа прилично лоша во моментот.
Но ако ние зумирате надвор и види повеќе на x и y-оската, кој ќе
доминираат во крајна линија?
Па тоа всушност излегува дека 2 на n, и можете да дознаам ова со само
приклучување во некои повеќе големи броеви, и ќе видите дека 2 на
n, навистина, станува сè поголемо многу побрзо.
Ако ние навистина одзумирате, 2 до n алгоритам апсолутно смрди.
Мислам ова се случува да се земе доста време за
компјутер за да разпенвам преку.
>> Но ќе видите со текот на времето, особено со идните проблем сетови, па дури и
конечна проекти, вашите податоци сет добива големи, во ред?
Дури и во првата верзија на Фејсбук, како и бројот на пријатели, и
Бројот на регистрирани корисници доби голема, можете да ги подредите на телефонот во и
имплементираат нешто со линеарно пребарување, или многу едноставен сортирање
алгоритам, како што ќе видиме денес.
Што треба да почнам да размислувам потешко и потешко за овие проблеми.
И типови на проблеми места како Фејсбук, и Google и Microsoft,
и други работи на е токму овие вид на големи податоци вид на прашања
повеќе, овие денови.
>> Сите во право.
Значи успехот на Jennifer во таа секунда алгоритам, искрено, таа го направи неверојатно
и прв пат, но ајде напишете го како среќа, така што ние
може да направи оваа точка.
Во вториот случај, таа балон на алгоритам што повторува одново и
повторно, но таа го зеде здраво за готово на извесна претпоставка дека ние дозволено
неа, но таа експлоатираат некои детали втор пат дека таа немала
прв пат.
Кој беше она?
>> Дека листата е подредени.
Па штом листата беше подредени, ние тврдат дека Џенифер беше во можност да го стори
фундаментално подобро.
7 врати, одговорот е да, не е интересно, но тоа претпоставувам ние сме 7.000.000 врати.
Вклучи на n е дефинитивно ќе да се изврши многу, многу
побрзо во долг рок.
Но, таа мораше да имаат врати подредени за неа.
Сега, си зедов слобода тоа да го однапред на екранот на компјутерот
тука, но претпоставувам дека Џенифер мораше да го направи тоа себеси?
Да претпоставиме дека вратите во прашање претставен податоци во базата на податоци, или
пријатели регистрирани за Фејсбук, или било кој веб-страници на интернет што
разни веб-сајтови може да треба да индексира или пребарување завршена.
>> Да претпоставиме дека сте само имаше сурови податоци во собата и беше оставено на вас, или да
Џенифер да го стори тоа сортирање?
Дека, напротив, бара да одговориме на прашањето, добро, колку време
би ги презеле Џенифер, па дури и мене, да го решите тие бројки однапред, така
дека таа може да ги искористат предностите на тоа?
Нели?
Бидејќи импликација, се разбира, е ако тоа ми зема доста време да се најде решение
на броеви, кој е грижам се грижи што ќе може да најдете голем број како 50 толку брзо,
како и во случај на Jennifer, ако ние повеќе од совладан од износот на вкупното време
го зеде од страна на сортирање работите однапред?
>> Да видиме ако не можеме да го наслика слика овде.
Јас имам еден цел куп повеќе стрес топки, ако тоа им помага
се скрши мразот тука.
И ако не би ум, ние треба седум волонтери -
на, ОК.
Wow.
Значи ние не треба да се трошат на биро светилки, се чини.
Сите во право.
Па како за вас две во фронт.
Како за вас две момчиња во грбот.
Па тоа е четири.
Како за вас во пред пет, шест и седум.
Право таму.
Вашиот пријател ќе посочувајќи, па ќе го добиете награда.
>> Сите во право.
Ајде горе.
И зошто да не можеме да си момци дојдат на повеќе тука.
Одам да ви даде на секој број.
И оди напред и да организираме сами идентично на она што е
прикажан на екранот.
>> [INTERPOSING ГЛАСОВИ]
>> Дејвид Џ MALAN: OOP, жалам.
Бубачка.
Сите во право.
Добро, тука ќе одиме.
Број пет.
Бројот шест.
Еден, два, три, четири, пет, шест, седум.
Ох, ова е непријатно.
>> ЗВУЧНИК 2: Јас само ќе добие -.
>> Дејвид Џ MALAN: добра зделка.
Сите во право.
Ви благодариме за учество.
>> [Аплауз]
>> OK.
Сите во право.
Па ние имаме четири, два, шест, еден, три, седум, пет.
Совршен, така имаме седум волонтери тука, кои се еднакви во ширина со
низа што ние навистина свириме со порано.
И јас избра седум причини дека ќе биде само
погодно во малку.
И јас одам да предложи првиот што ние средиме овие седум волонтери.
Ако сакате, прво, да се каже здраво, секако.
Бидејќи ова се случува да биде непријатно неколку минути.
Воведување на себе си.
>> GRACE: Здраво, јас сум Грејс.
Јас сум сафомор во Leverett куќа.
>> BRANSON: Здраво.
Јас сум Бренсон.
Јас сум бруцош во Weld.
>> Gabe: Здраво.
Јас сум Габе.
Јас сум помлад во Кабот.
>> NEIL: Јас сум Нил.
Јас сум бруцош во Метјус.
>> ЈАСОН: Јас сум Џејсон.
Јас сум бруцош во Greenough.
>> МАЈК: Јас сум Мајк.
Јас сум бруцош во сиво.
>> JESS: Јас сум Џес.
Јас сум сафомор во Leverett.
>> Дејвид Џ MALAN: Одлично.
Сите во право.
Па, ти благодарам на сите наши волонтери тука досега.
И предизвикот на дофат на раката сега се случува да биде да се најде на овие момци, но потоа
ние ќе мора да размислуваат малку тешко за тоа како ефикасно ние всушност
сортирани нив.
Па ајде прво се обиде ова.
Вие момци може да се види едни од други броеви само со ставање на околу аглите.
Оди напред и да потрае неколку секунди, а вид себе си од најмалите на
лево кон најголемиот десно.
Одите.
>> OK.
Добар.
Тоа беше навистина ебам брзо.
Сега некој тука, она што беше на алгоритмот дека овие момци се применува?
>> ЗВУЧНИК 1: барем до најголема.
>> Дејвид Џ MALAN: OK.
Барем до најголема е навистина вид на објективен, но не сум сигурен дека тоа е
навистина алгоритам.
Барем до најголема не кажам мене чекор-по-чекор што да прави.
Да?
>> ЗВУЧНИК 1: [нечујни]
>> Дејвид Џ MALAN: OK.
Па ако видите лице помало од вашиот број, а потоа преминете на
правото на нив.
Па тоа е сега се повеќе експресивна, повеќе како алгоритам, затоа што
може да се каже, ако ова, тогаш тоа.
Па ние имаме некој вид на условен конструкција.
И овие момци се чинеше да го стори тоа неколку пати, затоа што некои од вас се пресели малку
на далечина.
Па се претпоставува дека некој вид на looping случува во нивните умови.
>> Но, ајде да се обидеме да го формализира тоа.
Ако вие момци може да ја ресетирате назад на овој аранжман.
Ајде да видиме ако не можеме да го формализира ова малку, а потоа го поставуваме прашањето, само
Како ефикасно е ова?
Се разбира, кога правиме ова повеќе полека, тоа се случува да се чувствуваат како добри на
алгоритам, но ајде да видиме дали можеме да стави нашите прсти на прецизни чекори.
>> Па вие двајца момци се четири и два.
Или можете точни или неточни цел?
Очигледно неточни.
Па ние заменети.
Сега ќе одам да ја тргнам на страна тука и да кажам, 05:56.
Дали сте точни или неточни?
>> Gabe: Точни.
>> Дејвид Џ MALAN: Точни.
Шест и еден?
Не бе.
Разменуваат.
Па тоа е две свопови.
Шест и три?
Не бе.
Разменуваат.
Шест и седум?
Изгледа добро.
Седум и пет?
>> JESS: [нечујни]
>> Дејвид Џ MALAN: Добро, трампа.
И подредени.
Сите во право.
Па очигледно не, нели?
Па таму беше повеќе се случува.
Но, навистина, овие момци, дури и само инстиктивно.
се врткаше.
Тие не само гости, откако тие корегирани еден проблем.
Тоа.
Всушност, јас ќе одам да имаат да го стори истото.
Одам да мора да се најде на премотам касетата назад на почетокот на овој проблем,
или на почетокот од оваа низа на луѓе, да почнеме нарекувајќи ги.
>> И сега што треба да ми алгоритам на вториот помине биде?
>> ЗВУЧНИК 1: истото.
>> Дејвид Џ MALAN: истото.
И ова, јас сум почнуваат да се допаѓа, нели?
Веднаш штом ќе може да се најдат себе си прават истото одново и одново, тоа е
стане повеќе како алгоритам, и помалку човечки инстинкт.
>> Па сега, тука ќе одиме повторно.
Две и четири?
Бр.
Четири и една?
Ах, навистина имало некои уште да се работи да се направи.
За и три?
Добар.
Четири и шест?
Шест и пет?
Шест и седум?
Добро, сега, направено.
Добро, нема.
Морам да се вратам.
>> Па сега, повторно, го правиме ова малку повеќе намерно.
И сега, има само еден мозок извршување на овој алгоритам.
Еден процесор, ако сакате.
И искрено, тоа е единствениот ресурс ние ќе треба да имаат пристап.
И еднаш кога ќе се вратиш на тастатура и да имаат нешто како C во нашата
располагање, ние сме само пишување програма што може да направи една работа во исто време.
Каде што, овие момци пред еден миг, ние балон на нивните колективни интелигенција
дека вие момци го правеше во недела нула.
Па ајде да го задржи тоа.
>> Две и еден.
Два и три.
Три и четири.
Четири и пет.
Пет и шест.
Шест и седум.
Направи?
Па јас сум, но дозволете ми да игра ѓаволот се залагаат.
Дали ми е, вид на компјутер кој само направи помине низ оваа низа на
луѓе, знаат дека јас сум се направи?
>> ЗВУЧНИК 1: Не
>> Дејвид Џ MALAN: Па зошто?
Она што јас ќе треба да направите со цел да се заклучи решително дека јас сум се направи?
Веројатно уште една помине.
Нели?
Затоа сè што знам од кои претходната помине е дека јас коригира грешка.
А тоа значи, можеби има уште една грешка
дека јас треба да се поправи.
Па јас само може да биде сигурен од враќање наназад, и потоа проверка, 01:59, два и
три, три и четири, четири и пет, пет и шест, шест и седум.
Добро, сега го направив без работа.
>> Јас секако може да се сети што го направив не работи со нешто како променлива,
сакал Инт.
Наречи го тоа свопови, и ако свопови е 0 еднаш бев добие тука, а започна на 0, а потоа
Јас само би било глупаво да продолжувам да одам напред и назад, проверка, повторно, и
повторно, и повторно, нели?
Затоа што ви се заглавени во некои вид на бесконечна јамка.
Па штом има 0 свопови, можеме да тврдиме дека оваа
алгоритам е навистина заврши.
>> Сега, ајде да се стави име на ова.
На алгоритам дека јас ќе се предложи само спроведува е нешто што се нарекува меур
вид, познат како такви, во смисла дека на броеви кои се поголеми вид на
меур својот пат до врвот, или до до крајот на низата на броеви.
Но, како ефикасна е овој алгоритам?
Колку чекори никако не можев физички треба да Преземе, на пример, да ги сортирате овие
седум луѓето?
>> Четири до пет?
ОК, премногу е во крајна линија ќе биде одговорот.
Но дури и тогаш, на одреден број не е толку интересно.
Ајде да се генерализира тоа како n.
Значи, ако имав n луѓе до тука, и тие беа, на некој начин, по случаен редослед на
почетокот, во таа оригинална цел.
Па, колку чекори морав да ја преземат првиот помине?
Тоа беше еден, два, три, четири, пет, шест, а тие се седум лица, па
тоа е седум, шест -, па тоа е n минус еден чекори за прв пат.
>> Сега, колку чекори морав да се преземат кога јас собра?
Па, ние всушност би можел двојно дека ако ние навистина сакаше да, но сега за сега, јас сум
само случува да се каже, во ред, Уште еден N минус 1.
Па N минус 1 се случува да се досадни да ги пратите на, па ајде
само зад малку.
Па 2n чекори.
Па 14 чекори, или дава земе.
>> Колку пати си земам чекор, следниот пат?
Па, тоа е 3n.
навистина.
И сега, во најлош случај, на пример, колку пати сум ќе има
качил напред и назад, напред и назад, извршување на овој алгоритам, Замена
луѓе на секоја помине, грубо?
Тоа е всушност n квадрат, нели?
>> Затоа што во најлош случај, може да се вид на мислите за оваа интуитивно,
иако тоа би можело да потрае малку малку време да потоне внатре
Во најлош случај, што би овие седум лица изгледаше како, во
условите на аранжманот на нивните броеви?
Целосно наназад, нели?
И само за да се симулира дека, она што беше вашето име повторно?
>> МАЈК: Мајк.
>> Дејвид Џ MALAN: Мајк?
Добро, Мајк, може да ви само ми се придружат во текот тука за само една секунда?
Всушност, бр.
Жал Мајк, ја премотам касетата, ајде.
Како се викаш повторно?
>> NEIL: Нил.
>> Дејвид Џ MALAN: Нил.
Добро, Нил, ќе дојдеш со мене, ако не ви пречи.
Па ќе одам да предложи, само за едноставност, дека Нил е сега во
најлош можен случај.
Но се потсетиме како се спроведува мојата алгоритам.
Јас сум споредување, споредување, споредување, споредување, споредување, ох.
Сега овие момци се надвор на ред, па јас поправам.
Па вие момци трампа.
Но, сметаат дека сега, колку подалеку не Нил мора да одат?
Тоа е грубо n.
Знаете, тоа не е всушност n.
Тоа е како, н минус 1, но јас сум добивање караше следење на мало
број, па да го наречеме n.
>> Па ако Нил се движи еден чекор максимално секоја време, и да се движат Нил еден чекор,
Морам да се направи ова навистина досадни помине напред и назад, ова е грубо
Правејќи го ова, n чекори, вкупно n пати, затоа што тоа се случува да ме земат
дека многу чекори за да добие Нил сите начинот на кој до каде што припаѓа.
А камоли сите други, ако вие момци сите беа погрешно наредил, како и.
>> Па ајде да ги наречеме меур вид n квадрат.
Трчање време на овој алгоритам, перформансите на овој алгоритам,
ефикасноста на овој алгоритам, ние само ќе го опише повеќе
генерално како n квадрат.
Што е убаво, затоа што не можеше да стори истиот пример со осум луѓе, девет
луѓе, милион луѓе, и дека Одговорот не е ќе се смени.
>> Значи, ако вие момци не би ум, ајде да ресетирање да каде што почна.
И ајде да се обидеме две други пристапи и види дали не можеме да правиме фундаментално
подобро од ова.
Значи ова време, ќе одам да предложи еден вид на различен алгоритам.
Тоа беше многу умен од нас последен пат, а вие момци биле во право да имаат
право инстинкти на само вид на Замена pairwise.
Но, ако јас навистина сакаше да им пријде на ова едноставно, и мојата цел е да се движат
сите на малите броеви на овој начин, и им помогнам на сите од големите броеви кои
начин, зошто да не Јас само го направи тоа во повеќето наивна начин е можно и да видам дали можам
може да го направи подобро од она што беше прилично комплексен алгоритам?
>> Дали ќе видиме.
Четири е прилично мал број, па јас сум ќе те оставам таму момент.
Ooh, број два е дури и подобро.
Па може да ви само чекор напред за момент?
Ова е моментално мојот најмалите нумерирани кандидат, и јас одам да се запамети
дека со, како, една променлива.
Но јас ќе одам да го задржи проверка.
Дали има некој чиј број е помал?
Шест, бр.
Ох, има Нил повторно.
>> Па јас ќе одам да ти помогнам назад вид на концептуално.
Нил ќе дојде напред.
И сега, променливата дека јас сум со користење на ги пратите на кој има најмалата
број се ажурира да содржат Нил локација.
Добро, ајде да видиме.
Три, седум, пет.
ОК, знам дека Нил беше најмалиот.
Што е наједноставниот нешто за мене да направите сега?
Јас не одам да отпад моето време од само жуборот Нил едно место налево.
Зошто да не можам само да ги ставите Нил каде што припаѓа, што е секако каде?
>> Сите на патот на почетокот.
Па Нил, дојдете со мене.
И она што беше вашето име повторно?
>> GRACE: Грејс.
>> Дејвид Џ MALAN: Грејс.
OK.
Па Грејс, за жал, вие сте вид на на патот.
Така како ние да се реши овој проблем?
Нели?
Ако ова е низа, има само седум локации.
Потсетиме дека, со Rob, ние разговаравме за прогласување возрасти, а ние само имаше
конечен број на векови?
Истата идеја тука.
Ние имаме само ограничен број на ints.
Грејс е вид на во нашата начин, па како да се поправи?
>> Наједноставниот начин е како, Благодат, жалам.
Ви се случува да мора да одат преку таму, па ние може да се направи простор.
Сега, ако мислиш за ова, можеби ние само го направи проблем полошо.
А можеби ние го сторивме, бидејќи што ако Грејс беа во право место?
Но ние знаеме дека не е, затоа што во спротивно, таа ќе беше
стои напред, наместо на Нил во ова време, нели?
Ние веќе проверуваат нејзиниот број надвор.
>> Сите во право.
Па сега, Нил е во право место, како и Што можам да направам мала оптимизација.
За следната минута, јас ќе одам да се игнорира Нил, сите заедно, така што нема да
отпад своето време, или случајно разменуваат со него на погрешно место.
Па сега, како можам да се најдат на следниот елемент тоа е најмалиот?
Две.
Тоа е прилично добар број, ако дека сакате да се чекор напред и
Јас ќе ти запамети.
Шест, не е добро.
Четири, три, седум, пет, не е добро.
Па да ми се движат да Вашиот вистинското место.
А ние само што влегов среќа овој пат.
>> Сега, јас ќе одам да ги игнорира овие две момчиња, а сега направи уште еден
поминат низ ова.
Шест години, тоа е прилично мал број.
Ајде напред.
Ох, извинете.
Број на grace е подобро, па чекор врз напред.
Четири.
Жал ми е, Грејс.
Се врати повторно.
Број три е подобро.
Седум.
Пет.
И сега што викаш повторно?
>> ЈАСОН: Џејсон.
>> Дејвид Џ MALAN: Џејсон.
Така Џејсон сега е најмалиот елемент што сум избран.
Каде што е тој ќе оди?
Значи, каде што шест е.
И вашето име е повторно?
>> Gabe: Габе.
>> Дејвид Џ MALAN: Габе.
Габе е во тек.
Што е најлесната работа да се направи?
Разменуваат овие две момчиња и продолжи.
Па сега ајде да видиме.
Кој е најмалиот?
Четири.
Дозволете ми само вид на измамник.
Пет се случува да биде најмалата.
Сметам дека следната, ако сакате да ги интензивираат напред, она што можам да треба да направите со
овие момци, со Габе?
Разменуваат повторно.
Па сега, се уште малку на ред.
Најдов Габе да биде најмалата, па Го појави надвор, ќе се движат момци завршена.
И направено.
>> Значи одговорот е ист.
Крајниот резултат е ист.
Кој од овие два алгоритми е подобар?
Вториот, слушнав.
Зошто?
>> ЗВУЧНИК 3: Тоа е n чекори [нечујни].
>> Дејвид Џ MALAN: Тоа е n чекори во повеќето.
Интересна.
Така е тоа иако?
Па како не можам да најдам на најмалиот елемент?
Колку чекори морав да се земе на најде најмалиот елемент?
Имав изгледа целиот пат на крајот, нели?
Бидејќи во тој најлош случај, она што ако Нил беа над овде?
Па само наоѓање на најмалиот елемент зема me n чекори, или n минус 1.
Но, ОК.
Па поправи Нил.
Се сеќавам дека, од една минута или така одамна.
>> Но како не сум се најдат на следниот најмалиот елемент?
Тоа е n минус 1, или n минус 2, навистина, од бројот на чекори.
Па ред.
Па јас го n минус 2.
Сите во право.
Така што се чувствува малку подобро.
Сите во право.
Колку чекори следниот пат да се најде бројот три?
Значи n минус 4.
Па тоа е намалување, еден помалку чекор на секоја итерација.
Значи ова се чувствува подобро, нели?
Ако последен пат тоа беше грубо n пати n, овој пат тоа е n минус 1, плус n минус
2, плус n минус 3, плус n минус 4, точка, точка, точка.
Но ако се потсетиме од вашиот средно училиште учебници, малку измамник
лист на задната страна која има формули, ако ги додадете оваа серија на броеви,
она што е вкупниот број на чекори ќе биде дека јас земам тука?
>> Ова е еден од оние, како, n минус 1, пати n, поделени со 2.
Па дозволете ми да видам дали можам да се повлече ова за само еден миг.
И повторно, Јас сум вид на заокружување некои броеви само да го задржи нашиот живот едноставен,
но како што се сеќавам, тоа е нешто како ако Јас се направи N минус 1 нешта, тогаш n минус
2, тогаш n минус 3, тоа е грубо нешто како ова над 2, и ако јас
помножиш оваа надвор, тоа е всушност n плоштад.
Дека не се чувствува премногу добро. n минус n над 2.
>> Но, тука е нешто.
Во компјутерската наука, кога проблемите почне да се поинтересно е кога n
станува навистина голем.
И кога n станува навистина голем, што на овие вредности се случува да доминира на сите
на другите?
Тоа е вид на n квадрат, нели?
Да, делење со 2 е прилично добар.
Но ако зборуваме за милијарди парчиња на податоци, или трилиони
делови на податоци, во ред, па ти си двапати побрзо.
Но кој навистина се грижи ако тоа голем број, ако овој фактор е она што добива
поголеми и поголеми.
И сигурно, тоа го прави повеќе од разлика од овој човек.
Па дури иако вие момци се во право, вториот алгоритам, ние ќе го наречеме
селекција вид, е, во реалниот свет, малку побрзо потенцијално, бидејќи јас сум
земање помалку и помалку чекори секој пат.
>> Тоа не е навистина фундаментално побрзо.
Затоа што ако ние всушност игра ова за големи вредности на n, на крајот на
на денот, за доволно голема за n, тоа е уште случува да се чувствуваат прилично бавен.
Па, дозволете ми да земе една последните помине во тоа.
Тоа е она што јас би го нарекол селекција вид.
Вие момци можат самите го ресетирате за последен пат?
И во последниот случај, јас ќе одам да предложи нешто
наречен вметнување вид.
Вметнување вид суштество, концептуално, малку различни.
>> Наместо да оди напред и назад и изборот на најмалиот елемент, јас сум
само ќе се справи со секоја од овие момци како што јас ги сретнуваме, и вметнете
нив во нивните правилната место.
Па јас сум само ќе почнат со Grace, и гледам дека таа е број четири.
Каде број четири припаѓаат?
Јас не почнаа сортирање ништо, па Грејс добива да остане право таму.
И сега ќе одам да се тврди, ако може преземе чекор на вашето право, ова
мојата подредени листата, ова е мојот несортиран преостанати листата.
Па сега јас ќе одам да продолжи следната, и она што е вашето име повторно?
>> BRANSON: Бренсон.
>> Дејвид Џ MALAN: Бренсон.
Па Бренсон е број два.
Па јас ќе одам да ти земе надвор за момент.
А сега, каде ќе припаѓаат во оваа низа?
Па на правото на Грејс.
Па уште еднаш, ние сме вид на правење Благодат направи многу работа овде.
Каде што ние ви го стави?
Па ние ќе да ви слајд на лево, и вметнете Бренсон таму.
Но сега тврдам дека вие момци се направи.
Но известување, јас не сум користење на екстра простор.
Тоа е уште 2 елементи тука, 5 повеќе од тука.
Вкупно низа големина е 7, па јас сум не мамење, во ред?
>> Така, сега имаме, со Габе тука, број шест, каде ќе припаѓаат?
Имаш среќа повторно.
Па ќе го добиете да остане право таму.
Само да потрае мал чекор кон десно само да го направи јасно дека сте подредени.
И сега имаме Нил повторно, број еден, каде и да одите?
И сега е местото каде што ќе почнат да се види дека овој алгоритам, иако на прв
поглед, се чувствува прилично паметни, види она што е за да се случи.
Ако може да се чекор напред.
>> Каде што сакаме да се стави Нил?
Па очигледно тука, па како ние да се Нил таму?
Ајде да го направиме овој чекор-по-чекор.
Габе, каде ќе треба да одат?
Да, така да еден голем чекор, или две полу-чекори за да се направи
еден чекор таму.
Благодат, каде и да одите?
Добар.
Па уште еден чекор.
И, конечно, Бренсон?
Уште еден чекор.
И сега ние може да се стави Нил во место.
>> Па сега, продолжи и оваа логика.
Иако ние не се префрлаат Нил над, и одново, и одново, да го стави
Каде и да оди, во најлош случај, следниот број ќе се судрите би можеле да
биде број, да речеме, имаше голем број нула, тогаш ние ќе треба да се префрлат сите на
овие момци.
Да претпоставиме дека има голем број, негативен еден, тогаш треба да го пренасочиме
сите од овие момци.
Значи ние сме навистина само вид на нервира проблемот околу, така што ние сме
пренос на сметка од процесот на селекција, па вметнување
процес, како што вие момци само имаше да се движи околу n минус нешто
број на чекори.
И дека бројот на чекори е само ќе да се зголеми, како јас изберете повеќе броеви,
ако јас мора да се задржи турканиците вие ​​момци назад, и назад, и назад.
>> Па Тажната работа сега е сите овие алгоритми се n квадрат.
Ајде да одиме напред и благодарение на овие момци, и да се визуелизира овие малку
поинаку.
Многу добро направено.
>> [Аплауз]
>> Сите во право.
Таму да одите.
Ви благодариме за -
>> BRANSON: [нечујни] задржи на броеви.
>> Дејвид Џ MALAN: Не, вие може да задржи на броеви, како и.
Сите во право.
Убаво направено.
Сите во право.
Па ајде да видиме дали можеме сега не може да резимираме побрзо, и повеќе визуелно,
токму она што се случи тука како што следи.
Одам да одите напред и повлечете го Firefox.
Ние ќе ја поврзат оваа демонстрација на веб-страницата на курсот.
Јава е малку досадно да се работи во некои прелистувачи овие денови.
Па ако си играат со ова дома, сфатиш дека можеби ќе треба да го користите на Firefox
да го добие работа.
И она што јас ќе одам да направите со овој демонстрација е следниот.
>> На дното, јас имам цел куп мени опции, вклучувајќи почеток и
Сопри.
Исто така, како настрана, се чини дека да се биде бубачка во овие програми, при што ќе ги
не може да всушност гледаат на проектот или да престане копче, освен ако не се одржи команда или Alt
плус и зумирате, кој љубопитно ви покажува повеќе копчиња.
Па само Материјал цел, ако игра со ова дома.
Сега ќе одам да кликнете на Start за само момент, по специфицирање задоцнување од,
како, 200 милисекунди тука, само за да можеме да видиме што се случува.
>> Така тврдам дека ова е визуелизација на првиот алгоритам
овие момци го, меур вид, при што ние заменети луѓе пар-мудар.
Клучот увид на оваа визуелизација е дека висината на барови
претставува големината на број.
Па повисоки има црти, толку поголем број.
Пократко бар, помал број.
И ако забележите, ние сме минува низ првиот повторување на овој алгоритам,
Замена на големи и мали броеви, така што малиот број доаѓа прво и
големиот број оди на десно.
>> И штом ќе го добиеме на крајот на низа на многу повеќе броеви од седум, ние сме
ќе се вратиме на почеток.
И да се предвиди ова.
На далеку лево, дека малиот човек се случува да се разменуваат на страна, и ова
процесот се повторува.
Сега ова визуелизација брзо добива здодевен, па дозволете ми да оди напред и да престане
, сменете го задоцнување нешто многу побрзо само за да добие сега, чувство за
овој алгоритам.
>> Значи, иако сум го забрза, ова е како надградба на мојата процесор, за купување
на нов компјутер.
Не сум фундаментално се промени мојот алгоритам, но ти навистина може да види повеќе
јасно отколку со луѓето, дека големите броеви се жуборот до врвот,
и мал број се жуборот надолу кон дното.
А сега ова нешто овде подредени.
И како настрана, во плоштади, има само некои книговодство таму да
помогне да брои колку споредби, или колку свопови имаат
всушност е направено.
>> Добро, ајде пробајте едно од другите видовме.
Дозволете ми да кликнете на меурот вид тука, и дозволете ми да изберат, и целата оваа веб страница
е малку кабриолет.
Ајде да го прифати ризикот и тоа кандидира повторно.
Таму ќе одиме.
Па ајде да направиме избор вид.
Јас не знам зошто на менито се појавува таму.
Ајде да зумирате да се утврдат дека бубачка, сменете го ова на 50.
Ах, да всушност прават дека многу побрзо.
Пет милисекунди или така, и да почне.
>> Па ова е избор кој вид.
Значи, повторно, мислам за она што ние го направив со луѓето тука горе.
Отидовме преку низа и избрани најмалиот елемент, повторно,
и повторно, и повторно.
Сега тврдам дека уште беше прилично лош.
Тоа беше уште n квадрат, дава или зема, но тоа беше, во реалниот свет, малку
побрзо, бидејќи бев навистина преземање малку помалку чекори секој пат.
Но ние сме само зборува што?
Можеби 40 или така барови тука?
Ние не зборуваме 40 милиони евра.
Па тоа не е сосема јасно дека беше навистина значителен добивка.
>> А сега допуштете ми се вратиш назад и промени во нашето трети алгоритам, кој беше изберете
вметнување вид.
А сега тоа е навистина кабриолет бидејќи мени навистина не треба да биде таму долу.
Па сега ние ќе дојдете назад до овде и да почне овој алгоритам.
Шиштење, почне и запре.
Значи ова еден вид на има прилично модел на него, при што ние сме повторно
вметнување на луѓето, или во овој случај, барови во
нивната соодветна локација.
И тоа е веќе направено пред Се свртев.
Но ова, исто така, во теорија, се уште n квадрат.
>> Да видиме ако не можеме да резимираме овие како што следи.
Одам да одите напред и само за да даде ни вид на заеднички начин на зборување
за овие работи, дозволете ми да се воведе само малку на нотација тука.
Вие сте за да се види нешто што се нарекува голема О, бидејќи е буквално голем
О И ова е начинот на кој компјутер научник или математичар дури и го користи
за да се опише трчање време на некои алгоритам.
Колку чекори Дали тоа всушност го земам?
>> Сега ќе одам да си се посрамоти со мојот ракопис тука во само еден миг.
Но дозволете ми да оди напред и да се каже дека ова ќе биде големо O овде.
И дозволете ми да се воведе еден друг симбол, главниот град на омега.
Омега ќе биде спротивното, во суштина, на големите О Каде големо O
средства, во најлош случај, колку време некои алгоритам може да потрае, во
условите од n, омега се случува да се биде колку време би можеле да го
земе во најдобар случај.
И ќе видиме што ние подразбираме под најдобар случај во само еден миг.
>> Значи, да почнеме нешто едноставно.
Дозволете ми да започнам со линеарно пребарување.
Па не сортирање.
Ние ќе го наречеме овој линеарно пребарување.
И сега, се направи малку маса надвор од ова.
И сега, во случај на линеарно пребарување, во најлош случај, колку чекори е
тоа ќе ме однесе да Најдете број на произволен избор?
И таму е N Вкупно врати или n вкупниот број.
Најлош случај.
Колку чекори сум јас ќе мора да се се земе да се најде бројот 50 во низа
од n врати?
И зошто?
Бидејќи тоа би можело да биде на сите начин над кон крајот.
Толку многу како Џенифер се среќава, на број 50 беше целиот пат над, така што во
најлош случај линеарно пребарување е голема О од n, ќе речеме.
>> Што е со најдобар случај, ако добиете навистина среќен?
Тоа е само случува да се земе еден чекор, или постојан број на чекори.
Па ние ќе се опише тој како 1.
Значи ова е прилично добар.
Сега што ако ние го сторивме нешто како бинарна пребарување?
Па бинарни пребарување, во најлош случај, зеде колку време?
>> [INTERPOSING ГЛАСОВИ]
>> Дејвид Џ MALAN: Па, всушност, јас Слушнав дека во неколку места.
Па тоа е, всушност, се логирате n, дава или зема, бидејќи, како што ја делиме на листата на половина
повторно, и повторно, и повторно, ние сме во можност да се најде, во крајна линија, вредноста,
ако тоа е таму, но постои фати.
Што е претпоставката дека ние треба да земе здраво за готово за бинарни пребарување?
Тоа мора да се подредени.
Тоа не е сортирани, можете да се подели на работа во половина повторно и повторно, и вие
може да оди лево, а вие може да одат право, и можете да одите лево и десно, но ти си
нема да се најде елемент, ако листата не е сортирана, бидејќи
може да го пропуштите.
Бидејќи вашиот хеуристичка, за одење левата или десно се случува да биде недостатоци, ако тоа е
навистина не подредени.
Па таму е еден вид на скриени трошоци да се користи нешто како ова.
>> Сега, ајде да одиме во нашиот сортирање алгоритми не бараат -
ох, всушност, ајде да одиме во овој празно.
Бинарни барај во најдобар случај?
Тоа е, исто така, 1 ако тоа само се случува да биде во многу средината на низата, или
средината на телефонот книга.
Сега ајде да направиме меур вид.
Па уште еднаш, сега ние сме влегуваат во видови не, пребарувања.
>> Во најлош случај, колку чекори не можеме тврдат меур вид се случува да се земе?
n квадрат.
Па ќе одам да се подготви тоа.
Ooh, мојата ракопис изгледа дури и полошо кога тоа е проектиран дека голема.
Сите во право.
Така што за N квадрат.
И во најдобар случај на меурот вид, колку чекори е тоа ќе потрае?
1, слушнав.
>> ЗВУЧНИК 1: n.
>> Дејвид Џ MALAN: N, слушнав.
>> ЗВУЧНИК 1: 2.
>> Дејвид Џ MALAN: 2, слушнав.
Слушам 3?
Сите во право.
Па јас сум слушнал 1, n, 2, но ајде да ги собереш за разлика барем во првите од оние
предлози, 1.
Тоа не е лоша инстинкт, бидејќи тоа вид на следниов шаблон овде.
Но, ако тоа трае само 1 чекор, како во свет, јас може да се тврди дека листата
е сортирана, бидејќи ако јас сум дозволено само да се земе 1 чекор, колку елементи
може јас всушност проверете, за да бидеме сигурни?
Па, само 1, што значи дека n минус 1 елементи кои би можеле да бидат надвор од
ред, а јас сум само ќе се заснова на верата по во потрага на 1 елемент кој на
нешто се подредени.
Толку 1 не е точно тука.
Така минимално, колку морам да се погледне?
>> [INTERPOSING ГЛАСОВИ]
>> Дејвид Џ MALAN: N минус 1, или навистина, n, затоа што треба да се погледне во секој
елемент да бидете сигурни дека тоа не е на ред.
Но, повторно, ние ќе средиме од бран нашата рацете на помал број и
се претпостави дека, како n добива големи, тие се неинтересен во секој случај.
Па тоа е балон вид.
И сега, ајде да направиме овие последните две.
Селекција вид, а потоа ние ќе направи вметнување вид.
А потоа ние ќе удар вашиот умови со нешто многу
подобро од сите овие.
Сите во право.
>> Што е најлошото работи времето на селекција кој вид?
>> ЗВУЧНИК 4: N квадрат.
>> Дејвид Џ MALAN: N плоштад, ја слушам.
Но, зошто n квадрат, интуитивно?
>> ЗВУЧНИК 4: Бидејќи ние само го направив тоа.
>> Дејвид Џ MALAN: Бидејќи ние само го направив тоа.
OK.
Добар одговор.
Но интуитивно, зошто е избор вид n квадрат?
Она што не ни треба да направите повторно и повторно?
Ние моравме да ги задржи скенирање преку, се ви најмалиот, ти ли си
најмалиот, да не сте најмалите.
И готово, бевме во можност да се земе n чекори, тогаш n минус 1, тогаш n минус 2.
Но ако вид на додадете оние сè, или ја преземат верба дека јас додадов
за нив однапред, ние се добие приближно n квадрат минус некои помали броеви.
Па ќе одам да се јавите оваа n квадрат.
Но со селекција вид во најдобар случај, колку чекори е тоа
ќе ме земе?
>> ЗВУЧНИК 5: [нечујни]
>> Дејвид Џ MALAN: Тоа е за жал уште n квадрат, нели?
Бидејќи ако јас сум изборот на најмалите елемент, и имавме седум луѓе тука,
Знам само, еднаш бев се дојде до многу крајот, дека сум го нашол на најмалите
број, каде што тој или таа може да биде.
Но како можам да се најдат на следниот Најмал број?
Јас треба да направите друга помине.
Значи во најдобар случај, она што е внесување на селекција кој вид?
Тоа е веќе вид листа, број еден, број два, број три, број четири.
Но, јас сум на компјутер.
Можам само да се погледне во едно работа во исто време.
Јас не може да се најде на направиме чекор назад како човечки и да каже,
ooh, ова изгледа точни.
>> Можам само да судат точноста во селекција вид со избирање на
Најмал број.
Но, дури и ако најдам број еден, прво, ако не знам ништо во врска со
другите броеви, кои јас не се направи, сè што можам знам дека сум бил предаден низа
или приврзок на вратите зад кои се броеви, единствениот начин знам дека еден
беше најмалиот?
Ако јас се добие целиот пат тука и се реализира, проклето, еден беше навистина најмалите.
>> Но, како можам потоа да одреди дека две е следниот најмалиот?
Со тоа исто неефикасноста повторно и повторно.
Значи, конечно, со вметнување вид, како, во најлош случај,
Дали ние велиме врши?
Тоа не е премногу е n квадрат.
И како за со најдобар случај?
Ќе им го оставиме тоа како cliffhanger.
Ние ќе се пополни во таа празна следниот пат, но прво нека ми предложи дека ние
фундаментално го направи подобро од сите овие, во ред?
>> Така што мислам за себе она што вметнување вид се случува да биде.
Па, тоа не беше многу драматичен, затоа што јас сум единствениот
што ја видоа промени.
Wow.
OK.
Значи тука имаме малку различни демонстрации.
Ако јас зумирате тука, ќе видите дека на на левата страна имаме меур вид, во
средината имаме избор вид, како и на на екстремната десница, имаме нешто што ние
не погледна уште наречен спојат вид.
Но, сметаат дека она што сте биле правиш тука досега денес.
Кога Џенифер прв дојде на сцената, отидовме преку низа на броеви
повторно, и повторно, со линеарен пребарување, и добивме линеарна трчање време, големо O
на n, така да се каже.
>> Кога ние сега сметаат дека во првата недела од класа, кога имавме поделба и освојување,
и имавме книгата на телефонот кинење, и Џенифер, и ние колективно
балон дека клучните увид, кој требаше да повторете си повторно и повторно
некако фрлаат далеку, фрлаат далеку, фрлање далеку, половина од проблемот, или
генерално, делење на проблемот на половина, и потоа лекувањето на помал дел од
проблемот што е концептуално еквивалентни на другите, ние некако не
фундаментално подобро.
Но со балон вид, со избор вид, со вметнување вид, ние сме може
нема такви сознанија дека Џенифер не.
Ние доста само си се врати и издаде целиот куп на пати, а ние
tweaked работите малку, Замена Во овој редослед, можеби
вметнување или избирање.
Но на крајот на денот, јас навистина многу на непријатно одење напред и назад.
Ние не сме навистина потпора нешто паметни како Џенифер му се допадна делење
и освојување.
>> Па се спојат вид, пак, кои ние нема да видиме до следната недела, тоа се случува
да потпора дека клучната идеја со делење влезот, а потоа преполовување, а потоа
преполовување, а потоа преполовување.
И на секоја итерација на таа јамка, сортирање на левата половина, и правото
половина, а потоа на левата половина од левата половина, и десната половина на левата страна, а потоа
на левата половина на десната половина, и на десната половина на десната половина.
И повторување повторно и повторно.
>> Па ќе видите ова визуелно, но ова е она што не чека следната недела.
И воопшто, кога мислиме малку малку потешко на кој било таков проблем.
Имаме n квадрат на левата страна, н квадрат во средината, и n
логирате n десно.
Така што вашиот вистински cliffhanger.
Ќе се видиме во понеделник.
>> [Аплауз]