>> [Музички]
Дејвид MALAN: Во ред.
Сите во право, добредојде назад.
Па ова е недела 4, на почетокот од него, веќе.
И ќе се потсетиме дека минатата недела, ќе стави кодот резервирани за само малку
и почнавме да зборуваме малку повеќе високо ниво, за нешта како
пребарување и подредување, кои иако малку едноставни идеи, се
претставник на класа на проблеми ќе почнат да се реши особено
како што ќе почнете да размислувам за конечниот проекти и интересни решенија можете
можеби ќе треба да реалниот свет проблеми.
Сега меур вид беше една од наједноставните како алгоритми, и тоа
работел по тоа што имаат овие мали броеви во листата или во низа вид на
меур својот пат до врвот, и големи броеви се движат својот пат надолу за да
На крајот на таа листа.
>> И се сети дека би можеле да се визуелизира меур вид малку
нешто како ова.
Па дозволете ми да оди напред и да кликнете на Start.
Сум селектирал меур вид.
И ако се сетиме дека повисоки сина линии претставуваат големи броеви, мали
сини линии претставуваат мали броеви, како одиме низ ова повторно и повторно и
повторно, се споредуваат два такта до секоја други во црвено, ние ќе да се разменуваат со
Најголемиот и најмалиот ако тие се надвор од употреба.
>> Па ова ќе одат и да си одат и да си одат на, и ќе видите дека поголемите
елементи се прави свој начин на право, и помалите елементи се
правејќи нивниот пат кон лево.
Но почнавме да се измери на ефикасност,
квалитетот на овој алгоритам.
И ние рече дека во најлоша случај, овој алгоритам се
приближно колку чекори?
>> Значи n квадрат.
И она што беше n?
>> ПУБЛИКАТА: Број на елементи.
>> Дејвид MALAN: Значи n беше број на елементи.
И така ние ќе го правиме ова често.
Секое време сакаме да зборуваме за големината на проблем или големината на
влез, или износот на времето потребно за да се произведе излез, ние ќе само
генерализирана што влезот е како n.
Па назад во недела 0, бројот страници во телефонот книга беше n.
Бројот на студенти во собата е n.
Значи тука, исто така, ние сме по тој образец.
>> Сега n квадрат не е особено брза, па се обидовме да направиме подобро.
И така ние погледна неколку други алгоритми, меѓу кои
беа селекција вид.
Па селекција вид беше малку различен.
Тоа беше речиси поедноставно, јас се осмелувам да кажам, при што почнав на почетокот на
листа на нашите волонтери и јас само еднаш и повторно и повторно помина низ
листата, кубење надвор најмалите елемент во време и ставање него или
со неа во почетокот на листата.
>> Но, ова, исто така, еднаш почнавме да размислуваме преку математика и поголеми
слика, размислувале за тоа како многу пати Јас требаше напред и назад и назад
и назад, што се вели во најлош случај, селекција вид, исто така, беше она?
n квадрат.
Сега во реалниот свет, тоа би можело да всушност ќе биде маргинално побрзо.
Затоа што, повторно, јас не треба да се чува повлекува во однос еднаш имав сортирани на
Најмалата елементи.
Но, ако мислиме за многу големи n и ако вид на прават математика како
Го направив на табла, со n квадрат минус нешто, сè друго
покрај n квадрат, еднаш n станува навистина голем, не
навистина важно колку.
Така што компјутерски научници, ние сортирање на се прават слепи на помалите
фактори и да се фокусира само врз фактор во израз кој се случува да направи
најголемата разлика.
>> Па, на крај, ние погледна на вметнување вид.
И ова е слична по дух, но наместо да одат преку iteratively и
изберете најмалиот елемент една по една време, јас наместо зеде раката што јас
беше се занимаваа, и решив, сите право, ти припаѓам овде.
Тогаш јас се пресели на следниот елемент и одлучи дека тој или
таа припаѓале тука.
А потоа се преселив и натаму.
И јас би можел да, на патот, префрлат овие момци со цел да се
направи место за нив.
Така што е вид на ментална пресврт на селекција вид дека ние
наречен вметнување вид.
>> Па овие теми да се случи во реалниот свет.
Само пред неколку години, кога некоја сенатор се кандидираше за претседател,
Ерик Шмит, во времето на извршниот директор на Гугл, всушност, имаа можност
да го интервју.
И ние сме мислеле дека би го делат тоа на YouTube Клип за вас тука, ако би можеле да се обратат до
јачината на звукот.
>> [Видео репродукција]
>> -Сега, сенаторот, тука си во Google, и сакам да мислам на претседателството
како на интервју за работа.
>> [Смеа]
>> -Сега тоа е тешко да се добие работа како претседател.
А ти си минува низ на строги мерки сега.
Тоа е исто така тешко да се добие работа во Google.
Имаме прашања и бараме нашите кандидати прашања.
И овој е од Лари Швимер.
>> [Смеа]
-Вие момци мислам дека сум шегуваш?
Тоа е право тука.
Што е најефикасен начин да се сортирање еден милион две-битни цели броеви?
>> [Смеа]
>> -Па, ух -
>> -I'm sorry.
Можеби и ние треба -
>> -Не, не, не, не, не.
>> -Тоа не е -
OK.
>> -Мислам дека балонот вид би биде погрешен начин да се оди.
>> [Смеа]
>> [Навива и аплауз]
>> -Ајде, кој му рекол ова?
OK.
>> [Крај видео репродукција]
>> Дејвид MALAN: Па таму ќе ја имаат.
Па почнавме да се измери овие работи пати, така да се каже, со нешто
наречен асимптотска нотација, која е само се однесуваат на нашата вид на вртење
се прават слепи за оние помали фактори и само гледајќи во трчање време,
ефикасноста на овие алгоритми, како n станува навистина голем со текот на времето.
И така ние се воведе големи О И големо O претставен нешто што мислевме
на како горна граница.
И всушност, Бери, ние може да ја намали од микрофон малку?
>> Мислевме на ова е горна граница.
Толку голема О од n квадрат значи дека во најлош случај, нешто како
селекција кој вид ќе бидат потребни n квадрат чекори.
Или нешто слично вметнување вид би N квадрат чекори.
Сега за нешто како вметнување вид, она што беше најлош случај?
Дадени низа, што е најлошото можно сценарио кое може да се најде
се соочуваат со?
>> Тоа е сосема наназад, нели?
Бидејќи ако тоа е целосно наназад, што треба да направите во целина многу работа.
Бидејќи ако сте целосно наназад, ви се случува да се најде на
Најголемиот елемент тука, иако таа им припаѓа таму долу.
Па ви се случува да се каже, во ред, во овој момент во времето, ти припаѓам овде,
така да го остават на мира.
>> Тогаш сфаќаш, ох, проклето, морам да помести ова малку помали елемент за
од лево на вас.
Тогаш морам да го направи тоа повторно и повторно и повторно.
И ако одев напред и назад, можете ќе подредување на чувствувате вршење на
дека алгоритам, бидејќи постојано сум јас довлечкаа сите други надолу во
низа да се направи простор за тоа.
Па тоа е најлош случај.
>> Спротивно на -
и тоа беше cliffhanger последен пат -
рековме дека вметнување вид беше омега на што?
Кој е најдобар случај водење време на внесената вид?
Па тоа е, всушност, n.
Тоа беше празно дека ние ја напушти на табла последен пат.
>> И тоа е омега на n, бидејќи зошто?
Па, во најдобар случај, она што е вметнување вид ќе им бидат предадени?
Па, на листата што е целосно подредени веќе, минимална работа да се направи.
Но она што е уредни за вметнување вид е дека поради тоа започнува тука и
одлучува, о, вие сте број еден, ти припаѓам овде.
Ох, што е добра среќа.
>> Ти си број два.
Можете исто така припаѓаат тука.
Број три, па дури и подобро, припаѓаш овде.
Штом тоа ќе добива на крајот на листа, по вметнување вид на pseudocode
кој што одеше преку вербално последен пат, тоа е направено.
Но изборот кој вид, пак, Продолжив да го правам она што?
>> Ќе се чуваат низ листата повторно и повторно и повторно.
Бидејќи клучот увид имаше само некогаш сте погледна сите на патот до
крајот на листата можете да бидете сигурни дека елемент сте ја избрале беше
навистина во моментов најмалиот елемент.
Па овие различни ментални модели крај до дава некои многу реалниот свет
разлики за нас, како и овие теоретски асимптотска разлики.
>> Значи само да повториме, а потоа, големо O на n квадрат, видовме неколку такви
алгоритми досега.
Биг О од n?
Што е алгоритам што може да да се каже дека голем О од n?
Во најлош случај, тоа трае линеарна број на чекори.
>> Добро, линеарно пребарување.
И во најлош случај, каде е елемент што го барате кога
примена на линеарна пребарување?
>> Добро, во најлош случај, тоа не е дури и таму.
Или во вториот најлош случај, тоа е сите на патот, на крајот, што е
плус или минус еден чекор разлика.
Па на крајот на денот, можеме да кажеме дека е линеарна.
Биг О од n ќе биде линеарно пребарување, затоа што во најлош случај,
елемент не е дури и таму или тоа е по целиот пат на крајот.
>> Па, големо O на најавите на n.
Ние не се зборува во голема детали за ова, но ние сме виделе досега.
Што работи во т.н. логаритамска време, во најлош случај?
>> Да, така бинарни пребарување.
И бинарни барај во најлош случај би можеле да имаат елемент некаде во
средината, или некаде внатре во низа.
Но, вие само го најдете кога еднаш ќе ве подели на листата на половина, во
половина, за половина, на половина.
А потоа Voila, тоа е таму.
Или повторно, најлош случај, тоа не е дури и таму.
Но, вие не знаете дека тоа не е таму додека не вид на достигне дека минатата
дното-повеќето елементи од преполовување и преполовување и преполовување.
>> Биг О од 1.
Па ние би можеле големо O од 2, големо O на 3.
Во секое време сакате само постојана број, ние само вид на само се поедностави
дека како голема О од 1.
Иако, ако реално, тоа трае 2 или дури 100 чекори, ако тоа е
константен број на чекори, ние само да кажам големо O на 1.
Што е алгоритам што е во голема О на 1?
>> ПУБЛИКАТА: Наоѓање на должината на променливата.
>> Дејвид MALAN: Наоѓање на должина на променливата?
>> ПУБЛИКАТА: Не, должина ако тоа е веќе подредени.
>> Дејвид MALAN: Добро.
Добро, па наоѓање на должината на нешто ако должината на тоа нешто, како
низа, се чуваат во некои променлива.
Затоа што само може да се прочита на променливата, или да ги печатите на променливата, или
само генерално пристапите таа променлива.
И Voila, кој ги зема постојана време.
>> Спротивно на тоа, мислам назад до нула.
Сетам на првата недела на C, повикувајќи само printf и печатење
нешто на екранот е веројатно постојана време, бидејќи тоа само ги зема
некои бројот на процесорот циклуси да се покаже дека текстот на екранот.
Или чекајте - го прави тоа?
Како инаку би можеле да моделира перформанси на printf?
Некој би сакал да не се согласуваат, дека можеби тоа не е навистина постојано време?
Во која смисла би можеле да printf е водење време, всушност печатење во низа на
на екранот, да биде нешто освен константа.
>> ПУБЛИКАТА: [нечујни].
>> Дејвид MALAN: Да.
Па тоа зависи од нашата перспектива.
Ако ние всушност мислам на влез на printf, како да бидат стринг, и
па затоа ние се измери големината на таа внесени од неговата должина - така да ја наречеме
таа должина n, како и -
веројатно, printf е самата големо O на n затоа што тоа се случува да ве однесе n чекори
за печатење на секоја од овие n карактери, најверојатно.
Барем до степен до кој ние се претпостави дека можеби тоа е со користење на за јамка
под хауба.
>> Но, ние ќе треба да погледне во тоа код за да се разбере тоа подобро.
И навистина, штом вие ќе почнете да анализирање на вашиот сопствени алгоритми, ќе
буквално го прават токму тоа.
Вид на окото вашиот код и мислам за - сите во право, јас ја имаат оваа јамка
тука или јас имам вгнездени јамки тука, што се случува да се направи N нештата n пати,
и можете да ги подредите на разумот вашиот начин преку код, дури и ако тоа е
pseudocode, а не реалните код.
>> Значи она што за омега на n квадрат?
Она што беше алгоритам кој во најдобар случај, сепак зеде n квадрат чекори?
Да?
>> ПУБЛИКАТА: [нечујни].
>> Дејвид MALAN: Значи селекција вид.
Затоа што во тој проблем навистина намалени на фактот дека повторно, јас не знам
Сум го нашол на тековната најмалите до Сум проверил сите ебам елементи.
Па омега на, да речеме, n, ние само излезе со еден.
Вметнување вид.
Ако на листата се случува да се решат веќе, во најдобар случај ние само треба
да се направи една помине низ него, на која точка ние сме сигурни.
И тогаш тоа би можело да се рече да биде линеарна, за сигурен.
>> Што е со омега на 1?
Што, во најдобар случај, може да потрае постојан број на чекори?
Така линеарно пребарување, ако само ќе имаат среќа и елемент сте во потрага
е правото на почетокот на листата, ако тоа е каде сте почнуваат вашите
линеарна traversal на таа листа.
>> И ова е точно на број на работи.
На пример, дури и бинарни пребарување е омега на 1.
Затоа што ако ви се навистина ебам среќа и мирис-бучица во средината на
Вашиот низа е бројот ви го барате?
Така можете да добиете среќа таму, како и.
>> Овој, на крај, омега на n најавите n.
Значи n најавите n, ние не сме навистина зборува за уште, но -
>> ПУБЛИКАТА: Спојување вид?
>> Дејвид MALAN: Спои вид.
Тоа беше cliffhanger на последниот пат, каде што предложи, а ние покажа
визуелно, дека постојат алгоритми.
И се спојат вид на само еден таков алгоритам кој е фундаментално побрзо
од некои од овие други момци.
Всушност, се спојат краток е не само во најдобар случај n најавите n, во најлош
случај n најавите n.
И кога ќе ја имаат оваа коинциденција на омега и големи О биде иста работа?
Ние, всушност, може да се опише дека како што е наречен тета, иако тоа е
малку поретки.
Но, тоа само значи дека двете граници, во овој случај, се исти.
>> Па се спојат вид, што значи овој навистина се сведуваат на за нас?
Па, да се потсетиме на мотивација.
Дозволете ми да се повлече до друг анимација која ние не гледаше во последно време.
Оваа една, иста идеја, но тоа е малку поголем.
И јас одам да се оди напред и да се истакне Првиот - имаме вметнување вид на
горниот лев агол, а потоа селекција вид, меур вид, неколку други видови -
школка и брзо - тоа не сме разговарале за, и грамада и се спојат вид.
>> Па барем да се обидат да се фокусира твоите очи на на првите три на левата страна, а потоа
се спојат вид кога ќе кликнете на оваа зелена стрелка.
Но јас ќе ги споделите со сите од нив работат, само за да ви даде чувство на разновидноста на
алгоритми кои постојат во светот.
Одам да ги споделите со овој рок за само неколку секунди.
И ако се фокусираат на очите - ги собереш на алгоритам, се фокусира на тоа за само
секунди - ќе започне да ја видите шема дека тоа е спроведување.
>> Се спојат вид, информации, е завршена.
Грамада вид, брзо вид, школка -
па се чини дека ние воведе три Најлошото алгоритми минатата недела.
Но тоа е добро дека ние сме тука денес да погледнете спојат вид, кој е еден од
толку полесно оние е да се погледне, па дури и иако тоа веројатно ќе се наведнуваат вашиот ум
само малку.
Тука можеме да видиме само колку селекција вид смрди.
>> Но, од друга страна, тоа е навистина лесно да се имплементира.
А можеби и за P Постави 3, тоа е еден од алгоритми сте одбрале да го спроведе
за стандардна верзија.
Совршено чисто, совршено точни.
>> Но, повторно, како n добива голем, ако изберете да се спроведе побрз алгоритам
како спојат вид, шансите се во поголеми и поголеми влезови, вашиот код е само
ќе трчаат побрзо.
Вашиот веб-сајт се случува да работат подобро.
Вашите корисници ќе бидат посреќни.
И така постојат овие ефекти на всушност даваат
ни некои подлабоки мисла.
>> Па ајде да ги разгледаме во она што се спојуваат вид е всушност за сите.
Кул работа е тоа што се спојуваат вид е токму тоа.
Ова е, пак, она што го нарекува pseudocode, pseudocode суштество
Англиски како синтаксата.
И едноставноста е вид на фасцинантен.
>> Така, на влез од n елементи - така што само значи, тука е низа.
Тоа е се здобија n нешта во неа.
Тоа е се што си ти што зборуваш таму.
>> Ако n е помалку од 2, да се вратите.
Па тоа е само тривијални случај.
Ако n е помалку од 2, тогаш очигледно тоа е 1 или 0, во кој случај нешто
е веќе сортирани или не постои, па само се вратат.
Нема ништо да се направи.
Така што е едноставен случај да се извади надвор.
>> Друго, ние имаме три чекори.
Сортирање на левата половина од елементите, сортирање на десната половина на елементите,
и потоа се спојуваат на подредени половини.
Она што е интересно овде е дека Јас сум вид на punting, нели?
Таму е вид на кружни дефиниција на овој алгоритам.
Во која смисла е овој алгоритам е дефиниција кружни?
>> ПУБЛИКАТА: [нечујни].
>> Дејвид MALAN: Да, мојата сортирање алгоритам, две од неговите чекори се "вид
нешто. "И така, кој моли на прашање, добро, она што сум јас ќе го користат
за сортирање на левата половина и десната половина?
И убавината тука е дека иако повторно, ова е потребен ум-свиткување
дел потенцијално, можете да го користите истата алгоритам за сортирање на левата половина.
>> Но, чекајте.
Кога сте изјави за сортирање на левата половина, што се две
чекори ќе биде следно?
Ние ќе сортирање на левата половина од левата половина и правото
половина од левата половина.
Проклето, како можам да сортирање овие две половини, или четвртини, сега?
>> Но тоа е во ред.
Имаме сортирање алгоритам тука.
И иако може да се грижиме на Првиот ова е вид на бесконечен
јамка, тоа е циклус кој никогаш не е ќе заврши - тоа се случува да се
заврши еднаш што се случува?
Откако n е помалку од 2.
Кој на крајот ќе се случи, бидејќи ако продолжиш преполовување и
преполовување во преполовување на овие половини, сигурно на крајот ви се случува да се стави крај
со само 1 или 0 елементи.
На која точка, овој алгоритам вели ќе завршиш.
>> Па вистинска магија во овој алгоритам се чини дека е во
дека последниот чекор, спојување.
Тоа е толку едноставно идеја само спојување на две работи, тоа е она што во крајна линија ќе
за да ни овозможи да го решите низа на, да речеме, осум елементи.
Значи имам уште осум стрес топки до тука, осум парчиња хартија и еден
Google стакло -
која јас да се задржи.
>> [Смеа]
>> Дејвид MALAN: Ако би можеле да ги преземат осум волонтери, и да видиме дали можеме да
игра оваа надвор, па.
Леле, ОК.
Компјутерски науки е добивање на забава.
Сите во право.
Па како за тебе три, најголемиот рака до таму.
Четири во задниот дел.
И како за ние ќе ви направи три во овој ред?
И четири во предниот дел.
Така што осум, ајде нагоре.
>> [Смеа]
>> Дејвид MALAN: Јас сум, всушност, не се сигурни што е тоа.
Тоа е стресот топки?
На биро светилки?
Материјалот?
Интернет?
>> OK.
Па ајде нагоре.
Кои би сакале -
задржи доаѓа.
Ајде да видиме.
И ова ве става во место -
ти си во место една.
Ух-ах, почекајте една минута.
1, 2, 3, 4, 5, 6, 7 - ох, добро.
Сите во право, ние сме добро.
Сите во право, па секој има седиште, но не е на стакло на Google.
Дозволете ми да задача овие Регистрација.
Што е вашето име?
>> MICHELLE: Мишел.
>> Дејвид MALAN: Мишел?
Сите во право, ќе добиете за да изгледаат како на geek, ако тоа е во ред.
Па, јас не премногу, претпоставувам, за само еден миг.
Сите во право, режим на подготвеност.
Ние се обидува да излезе со го користите случај за Google стакло, а ние
мислев дека ќе биде забавно да се само не ова кога луѓето се на сцената.
Ние ќе ги сними светот од нивната перспектива.
Сите во право.
Веројатно не она што Google наменети.
Сите во право, ако не ти пречи носењето ова за следната непријатно минути,
дека би било прекрасно.
>> Сите права, па ние имаме тука низа на елементи, и дека низа, како за на
парчиња на хартија во овие луѓе ' раце, во моментов е вон едиции.
>> MICHELLE: О, тоа е толку чудно.
>> Дејвид MALAN: Тоа е доста случаен избор.
И во само еден момент, ние ќе се обидеме да се спроведе спојат вид заедно
и да видиме каде што клучните увид е.
И трик тука со спојат вид е нешто што не сме претпоставува уште.
Ние всушност треба некои дополнителен простор.
Значи она што се случува да биде особено интересна врска со ова е дека овие
момци се случува да се движат наоколу малку малку, затоа што ќе одам да се претпостави дека
има екстра низа на просторот, каже, веднаш зад нив.
>> Значи, ако тие се зад нивните стол, тоа е средно низа.
Ако тие се седи овде, тоа е основните низа.
Но, ова е ресурс кој го имаме не балон досега со балон
вид, со избор на вид, со вметнување вид.
Потсетиме минатата недела, сите само вид на мешаат во место.
Тие не се користи било дополнителна меморија.
Ние направивме просторија за луѓе од страна на движење на луѓе околу.
>> Значи ова е клучен увид, исто така.
Има оваа трампа, во целина во компјутерски науки, на ресурсите.
Ако сакате да се забрза нешто како време, си оди за да
мора да ја плати цената.
А една од тие цени е многу често простор, количината на меморија или хард
простор на дискот дека сте користење.
Или, искрено, износот на програмер време.
Колку време тоа ќе ве однесе, човечкото, да ги спроведе некои повеќе
комплициран алгоритам.
Но, за денес, трампа е времето и просторот.
>> Значи, ако вие момци може само да се одржи до вашиот броеви, па можеме да видиме дека ти си
навистина појавување на 4, 2, 6, 1, 3, 7, 8.
Одличен.
Па ќе одам да се обиде да диригира работи, ако вие момци можат само
ги следам моите олово тука.
>> Па јас идам да се спроведе, прво, Првиот чекор на pseudocode, што е
на влез од n елементи, ако n е помалку од 2, потоа да се вратат.
Очигледно, тоа не применуваат, па ние да продолжат понатаму.
Па ги сортирате левата половина од елементите.
Па тоа значи дека јас ќе одам да се фокусирам внимание за само еден миг на овие
четири момци тука.
Добро, она што можам следната направам?
>> ПУБЛИКАТА: вид на левата половина.
>> Дејвид MALAN: Па сега јас треба да расчистувам на левата половина од овие момци.
Затоа што, повторно, се претпостави да се на Целта е да се подреди на левата половина.
Како го правиш тоа?
Само следете ги инструкциите, дури и иако ние сме го прави тоа повторно.
Па ги сортирате левата половина.
Сега сум сортирање овие две момчиња.
Што доаѓа следно?
>> ПУБЛИКАТА: вид на левата половина.
>> Дејвид MALAN: вид на левата половина.
Па сега овие, ова место тука, Ова е листа на големина 1.
И она што е вашето име повторно?
>> ПРИНЦЕЗАТА DAISY: Принцезата Дејзи.
>> Дејвид MALAN: Принцезата Дејзи е тука.
И така таа е веќе сортирани, бидејќи листата е со големина од 1.
Што ми е следната направам?
Добро, врати, бидејќи таа листа е на големина 1, што е помалку од 2.
Тогаш што е следниот чекор?
И сега треба да се вид на одјавување во вашиот ум.
>> Сортирање на десната половина, што е -
Што е вашето име?
>> LINDA: Линда.
>> Дејвид MALAN: Линда.
И така што ќе правиме сега дека ние имаме листа на големина 1?
>> ПУБЛИКАТА: Враќање.
>> Дејвид MALAN: Внимателно.
Се враќаме прво, и сега третиот чекор - и ако јас вид на тоа го отслика од
прифаќање на две места сега, сега мора да се спојат овие два елементи.
Па сега, за жал, елементите се надвор од употреба.
Но тоа е каде што се спојуваат процес почнува да се добие релевантни.
>> Значи, ако вие момци може да застане за само еден миг, јас ќе одам да ви треба, во
моментот, да застанат зад вашиот стол.
И ако Линда, бидејќи 2 е помал од 4, зошто да не прават
ќе дојде околу првиот?
Остане таму.
Па Линда, ќе дојде околу во прв план.
>> Сега во реалноста, ако тоа е само низа ние може само да ја преместите во реално време
од овој стол да ова место.
Значи замислете што се некои постојана број на чекори 1.
И сега -
но ние треба да се стави во првата локација.
>> И сега дали можеш да дојдеш наоколу, како и, ние ќе
да биде во место два.
И иако ова се чувствува како да е земајќи некое време, она што е убаво сега е
дека левата половина од левата половина сега е подредени.
Значи она што беше следниот чекор, ако ние сега премотам касетата понатаму во приказната?
>> ПУБЛИКАТА: Право половина.
>> Дејвид MALAN: вид на десната половина.
Па вие момци треба да го направите ова, како и.
Па ако може да застане за само еден миг?
И она што е вашето име?
>> JESS: Џес.
>> Дејвид MALAN: Џес.
Добро, така што Џес е сега на левата половина на десната половина.
И така таа е листа на големина 1.
Таа е очигледно подредени.
И вашето име повторно?
>> MICHELLE: Мишел.
>> Дејвид MALAN: Мишел е очигледно листа на големина 1.
Таа е веќе подредени.
Па сега на магија се случува, спојување процес.
Па кој се случува да дојде прв?
Очигледно Мишел.
Па ако може да дојде околу назад.
Простор имаме на располагање за неа сега е веднаш зад оваа столица тука.
И сега, ако може да се врати, како и, сега имаме, да биде јасно, две
половини, секоја со големина од 2 -
и само за доброто опис, доколку сте може да се направи малку простор -
еден замина пред половина тука, десната половина тука.
>> Премотам касетата понатаму во приказната.
Што чекор е следно?
>> ПУБЛИКАТА: Спојување.
>> Дејвид MALAN: Па сега ние треба да се логирате.
Па Добро, па сега, за среќа, ние само ослободува четири столчиња.
Па ние сме се користи двојно повеќе меморија, но можеме да му дадеме флип-flopping помеѓу
двете низи.
Така што број е да доаѓаат во прв план?
Па Мишел, очигледно.
Па дојде околу и да ги преземат вашето место тука.
А потоа бројот 2 е очигледно следната, така што ќе дојде тука.
Број 4, број 6.
И повторно, иако постои малку одење се вклучени,
навистина, овие може да се случи веднаш, со поместување еден -
Добро, добро играше.
>> [Смеа]
>> Дејвид MALAN: И сега ние сме во прилично добра форма.
На левата половина од целиот внесување сега е подредени.
Сите во право, па се овие момци предност на мојот -
како тоа заврши сите девојки на лево и сите момчиња на десната?
>> Добро, па момци 'се сврти сега.
Па јас не ќе ви прошетка низ овие чекори.
Ќе видиме дали можеме да Додадете исто pseudocode.
Ако сакате да се оди напред и да застане, а вие момци, дозволете ми да ви даде микрофон.
Види ако не можете да реплицираат она што ние само не овде на
другиот крај на листата.
Кој треба да зборува прв, врз основа на алгоритам?
Па се објасни она што го правиш пред да направите било какви нога движења.
>> ЗВУЧНИК 1: Добро, па од Јас сум левата половина од
левата половина, јас се вратат.
Нели?
>> Дејвид MALAN: Добро.
>> ЗВУЧНИК 1: И тогаш -
>> Дејвид MALAN: Кој го прави на микрофон да одат во следната?
>> ЗВУЧНИК 1: Следна број.
>> ЗВУЧНИК 2: Па јас сум десната половина на левата половина од
левата половина, а ќе се вратам.
>> Дејвид MALAN: Добро.
Ќе се вратат.
Па сега што е следниот за вас двајца?
>> ЗВУЧНИК 2: Ние сакаме да видиме кој е помал.
>> Дејвид MALAN: Токму така.
Ние сакаме да се логирате.
Просторот што сте ќе се користи за да се логирате сте во, иако тие се
очигледно сортирани веќе, ние ќе да го следат истиот алгоритам.
Па кој оди во задниот првиот?
Значи 3, а потоа и 7.
И сега на микрофон оди на овие момци, во ред?
>> ЗВУЧНИК 3: Па јас сум десната половина на левата половина, и мојот n е помалку од
1, па јас сум само ќе помине -
>> Дејвид MALAN: Добро.
>> ЗВУЧНИК 4: Јас сум десната половина на десната половина на десната половина, и јас сум
исто така, една личност, па јас сум ќе се вратат.
Па сега ние се спојат.
>> ЗВУЧНИК 3: Па ние одиме назад.
>> Дејвид MALAN: Значи ќе одам во грбот.
Па 5 оди прв, а потоа 8.
И сега публика, која е чекор, ние сега мора да ја премотам касетата
се врати во нашите умови?
>> ПУБЛИКАТА: Спојување.
>> Дејвид MALAN: Спојување на левата половина и десно половина од оригиналната левата половина.
Па сега -
и само да се направи овој јасен, се направи малку на просторот
помеѓу вас двајца момци.
Па сега тоа е две листи, лево и десно.
Така како ние сега се спојат вие момци во предниот ред на седишта повторно?
>> 3 оди прв.
А потоа 5, очигледно.
Тогаш 7, а сега 8.
Добро, а сега сме ние?
>> ПУБЛИКАТА: Не е направено.
>> Дејвид MALAN: Не направи, бидејќи очигледно, има еден чекор останатите.
Но, повторно, причина јас сум со користење на овој жаргон како "премотам касетата во твојот ум,"
тоа е затоа што тоа е навистина што се случува.
Ние сме минува низ сите овие чекори, но ние сме вид на задржувањето за
момент, нуркање подлабоко во алгоритам, паузирање за миг,
нуркање подлабоко во алгоритам, и сега ние треба да се најде на премотам касетата во нашата
умови и го вратите сите на овие слоеви дека ние сме вид на се стави во мирување.
>> Така, сега имаме две листи на големината 4.
Ако вие момци може да застане за последен пат и да се направи малку простор тука за да
го направи јасно дека ова е од левата половина од оригиналот,
десната половина на оригиналот.
Кој е првиот број што ние треба да се повлече во грбот?
Мишел, се разбира.
>> Значи ќе стави Мишел тука.
И кој има бројот 2?
Број 2 доаѓа на грбот, како и.
Број 3?
Одличен.
Број 4, број 5, број 6, број 7, и бројот 8.
>> Добро, па се чувствував како да многу на чекори, за сигурен.
Но сега да видиме ако не можеме да се потврди вид на интуитивно дека овој
алгоритам во основа, особено како n станува навистина голем, како што видовме
со анимации, е фундаментално побрзо.
Па јас тврдат дека овој алгоритам, во најлош случај, па дури и во најдобар случај,
е голема О на n пати најавите n.
Тоа е се, има некои аспект на овој алгоритам кој ги зема n чекори, но
има уште еден аспект некаде во дека повторување, дека looping, која
се најавите n чекори.
Ние може да се стави нашите прстот врз она што тие два броја се однесуваат на?
Па, каде -
Каде на микрофон оди?
>> ЗВУЧНИК 1: Дали се логирате N биде кршење нас на два -
делење со две, во суштина.
>> Дејвид MALAN: Токму така.
Секое време можеме да видиме во секој алгоритам на тој начин До сега, има е овој модел на
поделба, поделба, поделба.
И тоа е обично намален на нешто што е
логаритамска, влези основа 2.
Но тоа навистина може да биде ништо, но се најавите основа 2.
>> Сега, она што за n?
Јас може да се види дека ние вид од вас поделени момци - поделени вас, поделени,
поделени вас, поделени.
Каде што го прави на крајот доаѓаат од?
>> Па тоа е спојување.
Затоа што мислам за тоа.
Кога ќе се спојат осум лица заедно, при што половина од нив се сет од четири
а другата половина се уште сет од четири, како да одите
за вршење на спојување?
Па, вие момци тоа го правеше прилично интуитивно.
>> Но, ако јас наместо тоа го правеше малку повеќе методично, јас ке се вперени во
најлева лице прво со мојата лева страна, укажа на најлева лице
на тој половина со мојата десна рака, и само потоа шеташе низ
листа, посочувајќи на најмалиот елемент секој пат, движејќи мојот прст над и
над колку што е потребно во текот на листа.
Но она што е клучен за ова спојување Процесот е јас сум споредување на овие парови
на елементи.
Од десната половина и од левата половина, јас никогаш не сум еднаш повлекува.
>> Па се спојат себе е преземање нема n повеќе од чекори.
И колку пати го имам да го направите тоа спојување?
Па, не повеќе од n, а ние само видов дека со финалниот спојат.
И така, ако го направите нешто што е потребно логирате n чекори n пати, или обратно,
тоа се случува да ни даде n пати најавите n.
>> И зошто е ова подобро?
Па, ако ние веќе знаеме дека дневникот n е подобро од n - нели?
Видовме во бинарна пребарување, телефонот книга пример, влези n беше дефинитивно
подобро од линеарна.
Па тоа значи n пати најавите n е дефинитивно подобро од n пати друг
n, АКА n квадрат.
И тоа е она што ние на крајот се чувствуваат.
>> Толку голем аплауз, ако ние би можеле, за овие момци.
>> [Аплауз]
>> Дејвид MALAN: И вашата разделба подароци - може да се задржи на броеви,
ако би сакал.
И вашата разделба подарок, како и обично.
Ох, и ние ќе ви испратиме на снимката, Мишел.
Ви благодарам.
Сите во право.
Помош за себе си со стрес топче.
>> И дозволете ми да се повлече нагоре, во меѓувреме, нашиот пријател Роб Бауден да понудат
поинаква перспектива на тоа, бидејќи може да се размислува за овие
чекори случува во малку поинаков начин.
Всушност, сет-ап за она што Роб е за да ни покаже претпоставува дека ние сме
веќе направено поделиш на голема листа во осум мали листи,
секоја од големината 1.
>> Па ние сме менување на pseudocode на малку само да се најде на добиете на
Суштинската идеја за тоа како се спојуваат дела.
Но трчање време на она што тој е за да се направи уште
ќе бидат исти.
И повторно, поставување тука е дека тој е започна со осум листи на големина 1.
Значи сте пропуштени делот каде што тој е всушност е направено на дневникот n, влези n, влези n
поделба на влез.
>> [Видео репродукција]
>> -Тоа е тоа за еден чекор.
За две чекор, постојано се спојат пара листи.
>> Дејвид MALAN: Хм.
Само аудио доаѓа надвор од мојот компјутер.
Ајде да се обидеме повторно.
>> -Само произволно да избере кој - сега имаме четири листи.
Научат пред.
>> Дејвид MALAN: Има одиме.
>> -Спојување 108 и 15, на крајот ќе со листата од 15, 108.
Спојување 50 и 4, ние заврши со 4, 50.
Спојување 8 и 42, ќе заврши со 8, 42.
И спојување 23 и 16, што заврши со 16, 23.
>> Сега сите наши листи се на големината 2.
Забележете дека секоја од четири листи се подредени.
За да можеме да започнете спојување пара на листи повторно.
Спојување 15 и 108 и 4 и 50, ние прв преземе 4, а потоа на 15, а потоа
на 50, а потоа на 108.
Спојување 8, 42 и 16, 23, ние прво се 8, а потоа на 16, а потоа на 23,
тогаш 42.
>> Така, сега имаме само две листи на големина 4, од кои секоја е сортирана.
Па сега ние се спојат овие две листи.
Прво, ние се 4, а потоа го земеме 8, а потоа го земеме 15, потоа 16, потоа
23, потоа 42, потоа 50, потоа 108.
>> [Крај видео репродукција]
>> Дејвид MALAN: Повторно, известување, тој никогаш не допре дадена чашата повеќе од едно време
По унапредувањето подалеку од него.
Па тој никогаш не се повторува.
Па тој е секогаш во движење на страна, а тоа е каде добивме нашите n.
>> Зошто да не нека ме повлече до една анимација што сме го виделе претходно, но овој пат
фокусирајќи се само на спојување вид.
Дозволете ми да оди напред и да зумирате во оваа тука.
Прво дозволете ми да изберете случаен влез, зголемиле ова, и може да се вид видите
она што ние го зеде здраво за готово, порано, се спојат вид е всушност прави.
>> Па забележите дека ви се добијат овие половини или овие четвртини или овие осмини од
проблем кој одеднаш започне да се земе добра форма.
А потоа, конечно, ќе видиме во На самиот крај дека бам,
сè е се спои заедно.
>> Значи овие се само три различни нафрла врз истата идеја.
Но клучот увид, исто како и поделба и освојување во првиот час,
беше дека ние одлучивме да некако се делат проблемот во нешто големо, во
нешто вид на идентични во дух, но помали и помали и помали
и помала.
>> Сега уште еден забавен начин да се најде на тинк за овие, иако тоа не е
ќе ви даде истиот интуитивен разбирање, е
следниве анимација.
Значи ова е видео некој стави заедно кои се поврзани различни
звуци со различни операции за вметнување вид, за спојување вид, и
за неколку други.
Така што во еден момент, јас ќе одам да ја погоди Плеј.
Тоа е околу една минута долго.
И иако сеуште можете да ја видите моделите случува, овој пат можете да
исто така слушам како овие алгоритми се вршење поинаку и со
малку различни дезени.
>> Ова е вметнување вид.
>> [Тонови РЕПРОДУКЦИЈА]
>> Дејвид MALAN: Тоа повторно се обидува за да вметнете секој елемент
во, каде што припаѓа.
Ова е балон вид.
>> [Тонови РЕПРОДУКЦИЈА]
>> Дејвид MALAN: И можете да ги подредите на чувство како релативно малку работа таа го прави
на секој чекор.
Тоа е она што tediousness звучи како.
>> [Тонови РЕПРОДУКЦИЈА]
>> Дејвид MALAN: Ова е избор кој вид, каде што ние изберете елемент сакаме со
минува низ повторно и повторно и повторно и тоа ставање на почетокот.
>> [Тонови РЕПРОДУКЦИЈА]
>> Дејвид MALAN: Ова е спојат вид, која навистина може да почнете да се чувствувате.
>> [Тонови РЕПРОДУКЦИЈА]
>> [Смеа]
>> Дејвид MALAN: нешто што се нарекува GNOME вид, која не сме ја погледна.
>> [Тонови РЕПРОДУКЦИЈА]
>> Дејвид MALAN: Значи, да ме види, сега, расејува како што се надевам дека се од страна на
музика, ако можам да се лизга малку малку математика тука.
Па постои четвртиот начин дека можеме да мислам за она што тоа значи дека овие
функции да бидат побрзи од оние дека ние сме виделе порано.
И ако доаѓате на курсот од математика позадина,
всушност знаеме можеби веќе дека може да шамар мандат на оваа техника -
имено рекурзија, функција дека некако се нарекува себеси.
>> И повторно, да се потсетиме дека вид спој pseudocode беше рекурзивен во смисла
дека еден од чекорите спојат вид на беше да се јавам вид -
што е, сам по себе.
Но, за среќа, бидејќи ние се чуваат повикувајќи вид, или спои вид,
конкретно, на помали и помали и помали листа, ние на крајот
дно надвор благодарение на она што ќе го наречеме база случај, хард-кодирани случај дека
изјави дека ако листата е мала, помалку од 2 во тој случај, само се врати веднаш.
Ако ние не имаат тој посебен случај, алгоритам никогаш не би дното,
а вие навистина ќе влезе во бесконечна јамка навистина засекогаш.
>> Но, да претпоставиме дека сакаме да сега стави некои броеви на ова, повторно, со користење н
како и големината на влез.
И сакав да ве прашам, што е вкупното време се вклучени во
водење спојат вид?
Или поопшто, она што е цената на тоа во времето?
>> Па тоа е прилично лесно да се измери тоа.
Ако n е помалку од 2, времето се вклучени во сортирање n елементи,
каде n е 2, е 0.
Бидејќи ние само се вратат.
Нема работа да се направи.
Сега веројатно, можеби тоа е еден чекор или два чекори за да дознаам износот на
работи, но тоа е доволно блиску до 0, кој Јас сум само ќе кажам нема работа е
потребна ако листата е толку мал да се неинтересни.
>> Но овој случај е интересно.
На рекурзивен случај беше филијалата на на pseudocode тоа, вели друг, сортирање
на левата половина, сортирање право половина, ги спои двете половини.
Сега, зошто го прави ова изразување претставуваат трошок?
Па, Т од n само значи време да го решите n елементи.
А потоа на десната страна од еднаквите знаци таму, Т од n поделени
за 2 се однесува на цената на што?
Сортирање на левата половина.
На други Т од n поделено со 2 е се претпоставува дека се однесуваат на трошоци за
сортирање на десната половина.
>> И тогаш n плус?
Се спојуваат.
Затоа што ако имаш две листи, една од големина n над 2 и уште еден на големина n
над 2, мора да суштина допир секој од овие елементи, исто како и Роб
допрена секоја од чашите, и само Како што напоменавме во секоја од
волонтери на сцената.
Значи n е на сметка на спојување.
>> Сега, за жал, оваа формула е исто така, се рекурзивен.
Значи, ако поставува прашањето, ако n е, да речеме, 16, ако има 16 луѓе на сцената
или 16 чаши во видеото, колку вкупно чекори што е потребно за да ги сортира
со спојување вид?
Тоа е всушност не очигледен одговор, затоа што сега треба да се најде на
рекурзивно одговори на оваа формула.
>> Но тоа е во ред, затоа што дозволете ми да предложат дека ние го направите следново.
Времето се вклучени за сортирање 16 лица или 16 чаши се случува да бидат претставени
главно како Т од 16.
Но, тоа е еднакво, според нашите претходната формула, 2 пати повеќе од износот
на времето потребно да се најде решение 8 чаши плус 16.
И повторно, плус 16 е време за да се логирате, и два пати T, на 8 е
време да се најде решение левата половина и десната половина.
>> Но, повторно, ова не е доволно.
Ние треба да се нурне во подлабок.
Ова значи дека ние треба да одговориме на прашањето, што е Т од 8?
Па Т од 8 е само 2 пати Т од 4 плус 8.
Па, она што е Т од 4?
Т од 4 е само 2 пати Т од 2 плус 4.
Па, она што е Т од 2?
Т од 2 е само 2 пати T, на 1 плус 2.
>> И повторно, ние сме вид на добивање на заглавени во овој циклус.
Но, тоа е за да се погоди дека т.н. база случај.
Бидејќи она што е Т од 1, го тврдиме?
0.
Па сега конечно, можеме да работиме наназад.
>> Ако Т ​​од 1 е 0, јас сега може да оди назад до еден линија за да овој човек тука, и можам да
приклучок во 0 за Т од 1.
Па тоа значи дека тоа е еднакво на 2 пати нула, инаку позната како 0, плус 2.
И така што целиот израз е 2.
>> Сега, ако јас земам на Т од 2, чиј одговор е 2, приклучете го во средната линија, Т
од 4, што ми дава 2 пати 2 плус 4, па 8.
Ако јас потоа да го приклучиш во 8 до претходната линија, што ми дава 2 пати 8, 16.
И ако ние потоа продолжи дека со 24, додавајќи во 16, ние конечно да добие
вредноста на 64.
>> Сега дека во себе и за себе вид на говори ништо на нотација n,
голема О, омега дека ние сме се зборува.
Но излегува дека 64 е навистина 16, на големината на влез,
логирате база 2 од 16.
И ако ова е малку непознат, само сетам, и тоа ќе се врати
да ти на крајот.
Ако ова е најавите база 2, тоа е како 2 издигнат на она што ви дава 16?
О, тоа е 4, така што е 16 пати 4.
>> И повторно, тоа не е голема работа, ако тоа е вид на маглива меморија сега.
Но, за сега, се на верата дека 16 лог 16 е 64.
И така навистина, со овој едноставен разумност проверете, ние сме потврдено -
но не се покажа како формално -
дека трчање време на спојување вид е навистина n се најавите n.
>> Па не е лошо.
Тоа е дефинитивно подобро од алгоритми што сум го видел досега, и
тоа е затоа што ние сме балон, еден, техника наречена рекурзија.
Но поинтересно од тоа, дека идејата за поделба и освојување.
Повторно, навистина недела 0 нешта кои дури и сега се повторуваат во
повеќе привлечни начин.
>> Сега е забавно малку вежбање, ако сте никогаш не сторил тоа - а вие најверојатно
не ќе има, затоа што вид на нормална луѓе не мислат да го направите тоа.
Но, ако одам на google.com и ако Сакам да научат нешто за
рекурзија, Enter.
>> [Смеа]
[ПОВЕЌЕ Смеа]
Дејвид MALAN: Лош шега полека се шири.
[Смеа]
Дејвид MALAN: Само во случај, тоа е таму.
Јас не се пишува тоа во ред, и тука е шега.
Сите во право.
Објасни на луѓето до вас, ако тоа не е сосема кликна само уште.
Но рекурзија, поопшто, се однесува на процесот на функција повикувајќи
себе, или поопшто, делење на проблем во нешто што може да биде
реши дробни со решавање идентични претставник проблеми.
>> Добро, ајде да промени брзини за само еден миг.
Ние сакаме да се стави крај на одредени cliffhangers, па да почнеме да го поставите
на сцената, за неколку минути, на многу едноставна идеја -
дека од Замена два елементи, нели?
Сите од овие алгоритми ние сме биле зборуваме за изминатите неколку
предавања вклучи некои вид на Замена на.
Денес е визуелизира од нив добивање -up од нивните столици и
шетаат наоколу, но во кодот, ние би само преземе елемент од една низа
и одеднаш го во друг.
>> Така како ние да се обратите за тоа?
Па, дозволете ми да оди напред и да пишува брз програмата тука.
Одам да се оди напред и да прават ова како следново.
Ајде да ги наречеме ова -
што сакаме да го повикате оваа?
>> Всушност, бр.
Дозволете ми да ја премотам касетата.
Не сакам да го стори тоа cliffhanger уште.
Тоа ќе ја расипам забава.
Ајде да го направите ова, наместо.
>> Да претпоставиме дека сакам да пишувам малку програма и дека сега прифаќа овој
Идејата за рекурзија.
Јас вид на доби пред себе таму.
Одам да го направите следново.
>> Прво, брз вклучуваат стандардни io.h, како и вклучуваат на cs50.h.
А потоа јас ќе одам да се оди напред и изјавува int главната празнина
на вообичаениот начин.
Сфатив Сум misnamed на датотека, па дозволете ми само додадете. в продолжување тука, па
дека можеме да го компајлирате правилно.
Започне оваа функција исклучени.
>> И функцијата Сакам да пишувам, сосема едноставно, е оној кој прашува
корисникот за голем број, а потоа додава до сите броеви помеѓу кои
број и, да речеме, 0.
Значи прво јас ќе одам да се оди напред и изјавува int n.
Потоа го копирам некој код кој ние сме се користи за некое време.
Додека нешто не е точно.
Јас ќе се вратам на тоа во еден момент.
>> Што сакам да направам?
Сакам да кажам printf позитивни број ве молам.
А потоа јас ќе одам да велат n добива добие Инт.
Значи, повторно, некои boilerplate код дека ние сме користи пред.
И јас одам да го направите ова додека n е помалку од 1.
Па ова ќе осигура дека корисникот ми дава позитивен цел број.
>> И сега ќе одам да го направите следново.
Сакам да додадете до сите на броеви помеѓу 1 и и n, или 0 и n,
еквивалентно, да се добие вкупно сума.
Така големите сигма симбол кои може да се сети.
Па јас ќе одам да направите ова од прва повик функција наречена сигма,
поминува во N, а потоа јас ќе одам да велат printf, одговорот е во право таму.
>> Значи во кратки, да се добие и int од корисникот.
Јас се обезбеди тоа е позитивно.
Јас декларирате променлива наречена одговор на тип int и продавница во неа на враќање
вредноста на сигма, минувајќи во n како влез.
А потоа јас печати од тој одговор.
>> За жал, иако сигма звучи како нешто што може да биде во
на math.h датотека, нејзината декларација, тоа не е всушност.
Па тоа е во ред.
Јас може да се спроведе оваа себе.
Одам да се спроведе некоја функција наречена Сигма, и тоа се случува да се земе
параметар -
ајде да го наречеме метри, само па тоа е различно.
А потоа до тука, јас ќе одам да се каже, добро, ако m е помалку од 1 - ова е
многу неинтересен програма.
Па јас ќе одам да се оди напред и да веднаш да се врати 0.
Тоа едноставно не дава никаква смисла да додадете сите на броеви помеѓу 1 и М ако м
и самата е 0 или негативен.
>> А потоа јас ќе одам да се оди напред и го правиме ова многу iteratively.
Одам да се направи овој вид на старата школа, и јас одам да се оди напред
и да кажам дека јас ќе одам да декларирате Збирот да биде 0.
Тогаш јас ќе одам да имаат А за јамка на int -
и дозволете ми да го направи тоа да одговара на нашата дистрибуција код, па имате копија
дома. int i добива 1 на до i е помала или еднаква на м.
i плус плус.
А потоа во внатрешноста на оваа за телефонска линија -
ние сме речиси таму -
Збирот добива сума плус 1.
А потоа јас ќе одам да се вратат сумата.
>> Па јас направив ова брзо, сосема очигледно.
Но, повторно, главната функција е прилично јасна, врз основа на код ние сме
напишано досега.
Користи двојна јамка за да добие позитивен int од корисникот.
Јас тогаш го положат дека int на нова функција наречен сигма, нарекувајќи го, повторно, n.
И јас чување на повратната вредност, одговорот од црната кутија во моментов
познат како сигма, во променливата наречен одговор.
Тогаш јас го испечатите.
>> Ако ние сега продолжи приказната, како е сигма спроведува?
Јас предложи да се спроведе како што следи.
Прво, малку грешка-проверка да бидете сигурни дека корисникот не е
Месинг со мене и поминува во некои негативни или 0 вредност.
Тогаш јас декларирате променлива наречена сумира и го постави на 0.
>> И сега јас почнувам да се движат од i изнесува 1 целиот пат до и вклучувајќи метри,
затоа што сакам да се вклучат сите броеви од еден преку метри, инклузивна.
И во внатрешноста на оваа за телефонска линија, јас само го прават Збирот добива она што таа е сега, плус
вредноста на i.
Плус вредноста на i.
>> Како настрана, ако не го видел ова пред се, има некои синтаксички шеќер
за оваа линија.
Можам да ја преработи оваа како плус i изнесува, само да си ја спаси неколку кратенки
и да се погледне малку поладна.
Но тоа е се.
Тоа е функционално истото.
>> За жал, овој код е нема да ги собере уште.
Ако јас се кандидира направи сигма 0, колку сум Јас ќе се викна на?
Што е тоа случува да не ви се допаѓа?
>> ПУБЛИКАТА: [нечујни].
>> Дејвид MALAN: Да, јас не ја декларирале функцијата до врвот, нели?
Ц е вид на глупави, со тоа што само го прави она што ви кажам тоа да се направи, и вие
мора да го прават по тој редослед.
И така ако јас хит Внесете тука, јас ќе одам да добие предупредување околу сигма имплицитни
декларација.
>> Ох, не е проблем.
Јас може да оди до врвот, и можам да се каже, во ред, почекајте една минута.
Сигма е функција која враќа на int и дека очекува на
int како влез, точка-запирка.
Или би можел да го стави целиот функција над главната, но во целина, јас би
Препорачувам против тоа, бидејќи тоа е убаво секогаш да имаат главна на врвот, па
може да се нурне во право и да знаете што е Програмата го прави со читање главниот прв план.
>> Па сега дозволете ми да го исчистите екранот.
Римејк сигма 0.
Сето тоа изгледа до одјавување.
Дозволете ми да се кандидира сигма 0.
Позитивни интер.
Јас ќе го даде на број 3 да се биде едноставно.
Така што треба да ми даде 3 плус 2 плус 1, така 6.
Внесете, и навистина можам да добијам 6.
>> Што можам да направам нешто поголемо -
50, 12, 75.
Само како тангента, јас ќе одам да направите нешто смешно како навистина голем
број, О, што всушност работел надвор -
еј, јас не мислам дека е во право.
Ајде да видиме.
Ајде да навистина се плеткаш со него.
>> Тоа е проблемот.
Што се случува?
Кодот не е толку лош.
Тоа е уште линеарна.
Свирка е добар ефект, иако.
Што се случува?
>> Не се сигурни дали јас го слушнав.
Така што се испоставува - и ова е како настрана.
Ова не е суштината на Идејата за рекурзија.
Што се испоставува, бидејќи јас се обидувам да претставуваат толку голем број, повеќето
веројатно тоа е се погрешно интерпретирани од страна на C како не позитивен број,
но негативен број.
>> Ние не се зборуваше за ова, но тоа Излегува постојат негативни броеви
во светот во прилог на позитивни броеви.
И средствата со кои можете да претставуваат негативен број
во суштина е, можете да користите една специјални малку да се покаже
позитивните над негативните.
Тоа е малку посложена од тоа, но тоа е основната идеја.
>> Така, за жал, ако C е збунувачки еден на оние делови што всушност значи,
ох, ова е негативен број, моето јамка тука, на пример, е всушност никогаш не
случува да се прекине.
Значи, ако јас всушност биле печатење нешто повторно и повторно, би
види во целина многу.
Но, повторно, ова е покрај точка.
Ова е навистина само еден вид на интелектуална љубопитност дека ќе дојде
се врати за да на крајот.
Но, за сега, ова е точно имплементација, ако ние се претпостави дека
корисникот ќе обезбеди ints кои се вклопуваат во рамките ints.
>> Но тврдам дека овој код, искрено, може да се направи толку многу повеќе едноставно.
Ако целта на дофат на раката е да се преземат голем број како м и додадете до сите на
броеви помеѓу него и 1, или обратно помеѓу 1 и тоа, тврдам
дека јас може да позајми оваа идеја кои се спојуваат вид имале, која беше со земање на проблемот
на оваа големина и поделба на тоа во нешто помала.
Можеби не половина, но помали, но репрезентативно исти.
Истата идеја, но помала проблем.
>> Па јас сум всушност - дозволете ми да ја зачувате оваа датотека со различен број на верзија.
Ние ќе го наречеме оваа верзија 1 0 наместо.
И тврдам дека можам всушност reimplement ова во овој вид на
ум-свиткување начин.
>> Одам да ја напушти дел од неа сам.
Одам да се каже ако m е помалку од или дури и еднакви на 0 -
Јас сум само ќе биде малку повеќе анален ова време
со мојата грешка проверка -
Одам да се оди напред и да се вратат 0.
Ова е произволен.
Јас сум само едноставно да одлучат дали на корисникот ми дава негативен број, јас сум
се врати 0, и тие треба да се прочита документацијата повнимателно.
>> Друго -
забележи она што јас ќе одам да направите.
На друго место јас идам да се вратат m, плус -
она што е сигма од м?
Па, сигма од m, плус м минус 1, плус м минус 2, плус м минус 3.
Не сакам да пишувам сето тоа надвор.
Зошто не можам само залог?
Рекурзивно мене повик со малку помал проблем, запирка,
и го нарекуваат еден ден?
>> Нели?
Сега тука, исто така, може да се чувствуваат или се грижите дека ова е бесконечна јамка дека јас сум
поттикнување, при што јас сум спроведување на сигма со повик сигма.
Но тоа е совршено во ред, затоа што мислев пред додадена која линии?
>> ПУБЛИКАТА: [нечујни].
>> Дејвид MALAN: 23-26, која е мојот ако состојба.
Затоа што она што е убаво за одземање тука, бидејќи јас се задржи
предавање сигма помали проблеми, помали проблеми, помали - тоа не е
половина од големината.
Тоа е само бебе чекор помали, но тоа е во ред.
Бидејќи на крајот, ние ќе работиме нашите патот надолу на 1 или 0.
И еднаш ние хит 0, СИГМА не ќе се нарекува веќе.
Тоа се случува веднаш да се вратат 0.
>> Па ефектот, ако вид на ветер овој во твојот ум, е да го додадете m, плус
м минус 1, плус м минус 2, плус м минус 3, плус точка, точка, точка, м минус
м, на крајот ви даваат 0, и ефект е во крајна линија да ги додадете сите
овие работи заедно.
Значи ние не треба, со рекурзија, реши проблемот што ние
не може да го реши порано.
Всушност, верзија 0 од овој, и секој проблемот до денес, е решлив
со само користење на јамки или додека јамки или слични конструкции.
>> Но рекурзија, јас daresay, ни дава поинаков начин на размислување за
проблеми, при што доколку ние може да потрае проблем, ја делат од нешто
малку голема во нешто малку помали, тврдам дека ние може да го реши
можеби малку повеќе елегантно во однос на дизајнот, со помалку код,
а можеби дури и да ги реши проблемите кои би биде потешко, како што ќе на крајот
види, решавање чисто iteratively.
>> Но cliffhanger што го направив сакаат да ни остави на беше ова.
Дозволете ми да оди напред и да се отвори до датотека од -
всушност, дозволете ми да одат и го направите тоа вистински пост.
Дозволете ми да оди напред и да предложи следниве.
Меѓу кодот денес е оваа датотека тука.
Овој овде, noswap.
>> Значи ова е глупав малку програма која Јас шлаг до која тврди дека да се направи
следниве.
Во главната, таа прво изјавува еден int наречен x и доделува
вредноста на 1.
Тогаш тоа изјавува еден int y и тој ја доделува вредноста 2.
Тогаш тоа отпечатоци од она што x и y е.
Тогаш тоа вели, Замена, точка точка точка.
>> Тогаш таа тврди дека да се повикува функција наречен, swap, поминува во х и
y, идејата за што е тоа што се надевам дека x и y ќе се врати
различни, токму спротивното.
Тогаш тоа тврдат заменети!
со извичник.
Тогаш тоа отпечатоци од x и y.
>> Но излегува дека ова многу едноставна демонстрација надолу
тука е всушност кабриолет.
Иако јас сум за прогласување на привремените променлива и привремено ставање на во
тоа, тогаш јас сум прераспределување на вредноста на б -
која се чувствува разумно, бидејќи јас сум спаси копија од во Temp.
Тогаш јас обновете b за да се еднакви она што беше во Temp.
Овој вид на школка игра на движење на во Б и Б во со користење на оваа
среден човек наречен температура се чувствува совршено разумни.
>> Но тврдам дека кога ќе ја извршите оваа код, што ќе правам сега -
дозволете ми да оди напред и ставете го тука.
Ќе му се јавам овој noswap.c.
И како што сугерира името, ова не е ќе биде правилна програма.
Направи noswap. / Не трампа.
x е 1, y е 2, Замена, заменети.
x е 1, y е 2.
Ова е фундаментално погрешно, дури и иако ова се чини совршено
разумно да се мене.
И постои причина, но ние не сме ќе се открие причината само уште.
>> За сега вториот cliffhanger Сакав да те оставам со е ова,
објавувањето на видови на забава кодови.
Нашите иновации со доцна дена оваа година предизвика не-тривијални број
на прашања, што беше не е наша намера.
Намерата на овие забава кодови, при што, ако го направите дел од проблемот
постави почетокот, а со тоа добивање екстра ден, беше навистина да ви помогне да момци помогне
се започне рано, сортирање од страна на мотивиране вас.
Ни помага да се дистрибуираат товарот низ работното време подобро, така што
тоа е вид на победи-победи.
>> За жал, мислам дека моите инструкции не е, до денес, многу јасно, па
Се вратив овој викенд и нема на спец во поголеми, посмели текст, за да
објасни куршуми како овие.
И само да се каже повеќе јавно, од страна на Стандардно, проблемот множества се должи четврток
на пладне, на наставната програма.
Ако почнете рано, завршувајќи дел од проблемот поставени од страна среда во 12:00
Премиерот, во делот кој се однесува на купон код, идејата е дека можете да се прошири
Вашиот краен рок за P постави до петок.
Што е, малку исклучи еден мал дел од P постави во однос на она што обично е
поголем проблем, и да ја купите себе дополнителен ден.
Повторно, тоа ви добива размислување за проблемот сет, добива да
канцеларија часа порано.
Но на забава кодот проблемот е сè уште потребно, дури и ако не го достави.
>> Но повеќе убедливо е ова.
(Фаза шепот) И оние луѓе оставајќи рано се ќе го жалам.
Како што се луѓе на балконот.
Јас се извинувам однапред да на луѓе на на балконот од причини кои ќе бидат
јасно во само еден миг.
>> Па ние сме среќни да имаат еден од Поранешен шеф CS50 е наставата соработници на
компанија наречена dropbox.com.
Тие имаат многу великодушно донираше забава кодот тука за оваа многу простор,
што е зголемување од вообичаените 2 гигабајти.
Значи она што мислев дека ние би го направил на овој финалниот забелешка е да се направи малку на поклон,
при што во само еден миг, ние ќе се открие на победникот и за кој има забава
код кој потоа може да отидете на нивната веб-сајт, напишете, и Voila, да добијат
Цела многу повеќе Dropbox простор за вашите апаратот и за вашите лични датотеки.
>> И првата, кои би сакале да учествуваат во овој цртеж?
Добро, сега што го прави дури и повеќе забава.
Лицето кое добива оваа 25-GIGABYTE забава кодот - што е далеку
повеќе привлечна отколку кон крајот на дена сега, можеби -
е оној кој седи на врвот на седиште перница под кои постои
тој купонот код.
Сега може да се погледне под Вашиот седалото.
>> [Видео репродукција]
>> -Еден, два, три.
>> [Вреска]
>> -Ќе добиете автомобил!
Ќе добие автомобил!
>> Дејвид MALAN: Ќе видиме сте во средата.
>> -Ќе добиете автомобил!
Ќе добие автомобил!
>> Дејвид MALAN: Балкон луѓе, доаѓаат овде долу на предната страна,
каде што имаме статисти.
>> -Секој си зема автомобил!
Секој добива автомобил!
>> [Крај видео репродукција]
>> Наратор: На следниот CS50 -
>> ЗВУЧНИК 5: Ох, господе боже боже боже боже боже боже боже боже боже -
>> [UKELELE игра]