>> [Музички]
>> ПРОФЕСОРОТ: Во ред.
Ова е CS50 и ова е на крајот од три недела.
Значи ние сме денес овде, не во Сандерс Театар, наместо во Вајднер библиотека.
Во внатрешноста на кој е студиото познат како Хаузер студио,
или ќе кажеме Студио Н, или ќе ние say-- Ако уживаше дека е шега,
тоа е всушност од соученик, Марко, на интернет,
кој предложи колку преку Твитер.
Сега што е кул за да се биде овде во студио
е дека јас сум опкружен со овие зелени ѕидови, зелен екран или chromakey,
така да се каже, што значи дека е CS50 производство тим, непознат за мене
во моментов, може да се стави најмногу ме било каде во светот,
за подобро или за полошо.
>> Сега она што се наоѓа напред, проблем во собата две е во ваши раце за оваа недела,
но со проблем во собата три овој следната недела,
ќе се соочат со предизвикот со таканаречената игра на 15,
стара партија корист што може да се сети прима
како дете дека има цел куп на бројки кои може да се лизга нагоре, надолу,
лево и десно, и има една празнина во рамките на загатка, во која ќе
всушност може да слајд оние мозаик парчиња.
Во крајна линија ќе го добиете ова загатка во некои полу случаен редослед,
и целта е да се го средиме, врвот до дното,
лево кон десно, од една по целиот пат до преку 15.
>> За жал, на имплементација ќе имате при рака
ќе биде на софтвер врз основа, а не физички.
Сте навистина се случува да мора да пишува код со кои студент или корисникот може да
се игра на 15.
И всушност, во хакер издание на играта од 15,
ќе биде предизвик да се спроведе, не само на играње на оваа старата школа
игра, туку за решавање на од него, спроведувањето бог на владата,
така да се каже, дека, всушност, решава загатка за човекот,
преку обезбедување на нив со навестување, по совет, по совет.
Толку повеќе за тоа следната недела.
Но, тоа е она што се наоѓа напред.
>> За сега се потсетиме дека на почетокот на оваа недела имавме ова cliffhanger, ако сакате,
при што најдобро го правевте сортирање мудар е горна граница на Биг О на n
квадрат.
Со други зборови, меур вид, селекција вид, вметнување вид,
сите од нив, додека различни во нивното спроведување,
се сведе на еден n квадрат трчање време, во најлош случај.
И ние обично се претпостави дека најлош случај за подредување
е оној кој вашата влезови се целосно наназад.
И навистина, тоа беше сосема неколку чекори за спроведување на секоја од овие алгоритми.
>> Сега на самиот крај на класа потсетиме, ние во споредба меур вид
против селекцијата еден против друг вид кои ги повика спојат вид во тоа време,
и јас предлагам дека тоа е преземање Предноста на лекција од недела
нула, поделба и освојување.
И некако постигнување некаков логаритамски трчање време на крајот,
наместо на нешто тоа е чисто квадратна.
И тоа не е сосема логаритамска, тоа е малку повеќе од тоа.
Но, ако се потсетиме од класа, тоа е многу, многу побрзо.
Ајде да ги разгледаме во местото каде што застанавте.
>> Меур вид наспроти избор вид наспроти спојат вид.
Сега тие се сите работи, во теорија, во исто време.
Процесорот е трчање со иста брзина.
Но, можете да се чувствуваат како здодевен ова е многу брзо ќе стане,
и колку брзо, кога ќе се инјектираат малку недела нула е алгоритми,
можеме да ги забрзаат работите.
>> Значи марка вид изгледа неверојатно.
Како можеме да го потпора, со цел да се најде решение броеви побрзо.
Па ајде да се сетам да состојка која ние
имале нула врати во недела, што од во потрага за некој на телефон книга,
и да се потсетиме дека на pseudocode кои ги предлага,
преку кој може да се најде некој како Мајкл Смит,
изгледаше малку нешто како ова.
>> Сега погледнете особено во линија на 7 и 8, и 10 и 11,
кои предизвикаа дека јамка, преку кое се чува да се вратам на линијата 3, повторно, и повторно,
и повторно.
Но, се покажа дека можеме да ја видите овој алгоритам, овде во pseudocode,
малку повеќе акција.
Всушност, она што јас барам при тука на екранот,
е алгоритам за наоѓање Мајк Смит меѓу некои сет од страници.
И, навистина, ние би можеле да се поедностави овој алгоритам во оние линии 7 и 8,
и 10 и 11 само да се каже ова, што сум презентирани овде во жолта боја.
Со други зборови, ако Мајк Смит е во почетокот на книгата,
ние не треба да го одредите чекор по чекор, сега како да се оди да го најде.
Ние не треба да се определи да се вратам на линијата 3,
Зошто не можеме да само наместо тоа, да речеме, поопшто,
пребарувате за Мајк во левата половина од книгата.
>> И обратно, ако Мајк е всушност подоцна во книгата,
зошто да не само цитат unquote пребарување Мајк на десната половина од книгата.
Со други зборови, зошто да не се само вид на залог да се велејќи:
пребарувате за Мајк во овој подмножество на книгата,
и да го оставам на нашите постоечки алгоритам за да ни каже
како да пребарувате за Мајк во дека левата половина од книгата.
Со други зборови, нашите алгоритам работи без разлика дали тоа е
телефон книга на оваа дебелина, на овој дебелина, или било која дебелина она.
За да можеме да рекурзивно дефинира овој алгоритам.
Со други зборови, на екран тука, е алгоритам
за пребарување на Мајк Смит меѓу страниците на телефонот книга.
Па од алинеја 7 и 10, ајде само да кажам токму тоа.
И јас го користам овој термин момент Пред, и навистина, рекурзија
е buzzword за сега, и тоа е овој процес
за правење на нешто циклични некако користење на кодот кој веќе го имате,
и нарекувајќи го уште еднаш, и повторно, и повторно.
Сега тоа се случува да биде важно дека ние некако дното
надвор, и не го сторат тоа бескрајно долго.
Во спротивно ние ќе треба да имаат навистина бесконечна јамка.
Но, ајде да видиме дали можеме да ги позајмите, оваа идеја на рекурзија, прави нешто повторно
и повторно и повторно, да се реши сортирање проблем преку спојување
вид, сите поефикасно.
>> Па јас да ви даде спојат вид.
Ајде да ги разгледаме.
Па тука е pseudocode, со кои би можеле да излеземе сортирање,
со користење на овој алгоритам наречен спојување вид.
И тоа е сосема едноставно ова.
За внесување на n елементи, со други зборови, ако сте
дадена n елементи и бројки и писма или што влезот е,
ако ти си дава n елементи, ако n е помалку од 2, само се вратат.
Нели?
Бидејќи, ако n е помалку од 2, кои значи дека мојата листа на елементи
е или на големината на 0 или 1, и во двете од овие тривијални случаи,
листата е веќе сортирана.
Ако не постои листа, тоа е се подредени.
И ако има листа со должина 1, тоа е очигледно подредени.
Па алгоритам треба да само навистина нешто интересно,
ако имаме два или повеќе елементи што ни се дава.
Па ајде да погледнеме во магичното тогаш.
На друго место се најде решение на левата половина од елементите, потоа вид на десната половина на елементи,
потоа ја спои подредени половини.
И, што е вид на умот свиткување тука, е во тоа што јас навистина не
се чини дека имаат ви кажал само уште нешто, нели?
Сите што рековме е, со оглед на листа на n елементи, сортирање на левата половина,
потоа на десната половина, а потоа ги спои подредени половини,
но каде е вистинската тајна сос?
Каде е алгоритам?
Па излегува дека тие две линии прво, сортирање остави половина на елементи,
вид и десната половина на елементи, се рекурзивните повици, така да се каже.
>> Впрочем, во овој момент во времето, не морам
алгоритам со кој да се средиме целиот куп на елементи?
Да.
Тоа е право тука.
Тоа е токму тука на екранот, и за да можам да ја користат таа истата сет на чекори
да се најде решение на левата половина, што можам десната половина.
И навистина, повторно, и повторно.
Така некако или други, и ние наскоро ќе види ова, магијата на спојување вид
е вграден во таа многу финалето линија, спојување сортирани половини.
А тоа изгледа прилично интуитивна.
Ве однесе на две половини, и на тебе, некако, ги спои заедно,
и ќе го видите овој конкретно во еден момент.
>> Но, ова е комплетен алгоритам.
И ајде да видиме точно зошто.
Па претпоставувам дека ние сме со оглед на овие исти осум елементи тука на екранот, еден
низ осум, но тие се во навидум случаен редослед.
А целта е на дофат на раката за да се најде решение за сите овие елементи.
Па како можам да се обратите за тоа го прават со користење, повторно,
спојат вид, како на овој pseudocode?
И повторно, пропит ова во вашиот ум, за само еден миг.
Првиот случај е прилично тривијални, и ако тоа е помалку од 2,
само се вратат, нема да се работи.
Значи, навистина, има само три чекори за да навистина да се чуваат во умот.
Повторно, и повторно, јас сум ќе сакаат да имаат
да се најде решение на левата половина, сортирање на десната половина,
а потоа, откако нивните две половини се подредени,
Сакам да ги спои заедно во една Подредена листа.
Па задржи дека во умот.
>> Значи тука е оригиналната листа.
Ајде да се третираат ова како низа, како што почнавме да
во две недела, што е соседни блок од меморија.
Во овој случај, кој содржи осум броеви, да се врати назад кон назад.
И ајде сега да аплицираат спојат вид.
Па јас прв пат сакаат да се најде решение на левата половина од оваа листа,
и нека е, според тоа, се фокусира на 4, 8, 6, и 2.
>> Сега како можам да се обратите за Сортирање листа на големина од 4?
Па морам да разгледаме сега Сортирање лево на левата половина.
Повторно, да ја премотам касетата за само еден миг.
Ако pseudocode е ова, и јас сум се дадени осум елементи,
8 е очигледно поголема од или еднакво на 2.
Така е и со првиот случај не се применува.
Така да се најде решение за осум елементи, јас прв пат сортирање на левата половина од елементи,
Јас тогаш се најде решение за десната половина, тогаш јас се логирате на две подредени половини, секоја од големината 4.
ВО РЕД.
>> Но ако сте само сте ми кажа, сортирате левата половина, кој сега е со големина 4,
како можам да се најде решение за левата половина?
И ако имам внесување на четири елементи,
Јас прв пат се најде решение за левата две, потоа десното две,
и тогаш ќе ги спои заедно.
Значи, повторно, станува малку на умот свиткување игра тука,
затоа што, вид, мора да се сеќавам каде се наоѓате во приказна,
но на крајот на денот, даде било број на елементи,
прво сакаат да ги сортирате левата половина, а потоа на десната половина,
потоа ги спои заедно.
Ајде да почнеме да го стори токму тоа.
Еве го влезот на осум елементи.
Сега ние сме во потрага на левата половина овде.
Како можам да се најде решение за четири елементи?
И јас прв пат се најде решение за левата половина.
Сега како можам да се најде решение за левата половина?
Па јас сум бил даден два елементи.
Значи, да се најде решение за овие два елементи.
2 е поголемо од или еднакво на 2, на курсот.
Така што првиот случај не се применува.
>> Па јас сега треба да се најде решение за левата половина од овие два елементи.
Левата половина, се разбира, е само 4.
Па како можам да ги сортирате листа од еден елемент?
Па сега, таа посебна база случај до врвот, така да се каже, се однесува.
1 е помалку од 2, и мојот Листата е навистина на големина 1.
Па јас само се вратат.
Јас не го правам ништо.
И, навистина, да погледнеме во она што сум направено, 4 е веќе сортирана.
Како и јас сум веќе делумно успешен овде.
>> Сега, кога се чини глупаво да се тврди, но тоа е вистина.
4 е листа на големина 1.
Тоа е веќе сортирана.
Тоа е левата половина.
Јас сега се најде решение за десната половина.
Мојот влез е еден елемент, 8 Слично на тоа, веќе се подредени.
Глупави, исто така, но, повторно, овој основен принцип
ќе ни овозможи да се изгради сега згора на тоа успешно.
4 подредени, 8 е сортирана, сега она што беше тој последен чекор?
Па третиот и последен чекор, било пат кога сте сортирање листа, да се потсетиме,
беше да се логирате на две половини, левата и десната страна.
Значи, да се направи токму тоа.
Мојата лева половина е, се разбира, 4.
Мојата десна половина е 8.
>> Па ајде да го направите тоа.
Прво јас ќе одам да се распределат некои дополнителни меморија,
дека ќе претставуваат тука, како само средно низа,
што е доволно голем да ги собере ова.
Но може да се замисли проширување дека правоаголникот целата должина,
ако ние треба повеќе подоцна.
Како можам да се земе 4 и 8, и се спојуваат овие две листи на големина 1 заедно?
Овде, исто така, прилично едноставна.
4 е на прво место, а потоа доаѓа 8.
Затоа што ако јас сакам да ги сортирате левата половина, а потоа на десната половина,
а потоа се спојат овие две половини заедно, по некаков ред,
4 е на прво место, а потоа доаѓа 8.
>> Значи ние се чини дека се прави напредок, дури и иако не сум сторил било вистински работа.
Но, се сеќавам, каде што сме во приказната.
Ние првично биле потребни осум елементи.
Ние подредени левата половина, што е 4.
Тогаш ние подредени левата половина на левата половина, што е 2.
И тука ќе одиме.
Ние сме направиле со тој чекор.
>> Значи, ако ние сме подредени остави половина на 2, сега ние
мора да се најде на десната половина на 2.
Па на десната половина на 2 е овие две вредности тука, 6 и 2.
Па ајде сега да преземе влезни големина 2, и да најде решение на левата половина, а потоа
десната половина, а потоа ги спои заедно.
И како можам да ги сортирате листа на големина 1, кој содржи само бројот 6?
Јас сум веќе направено.
Таа листа на големина 1 се подредени.
>> Како можам да се најде решение за уште една листа на големина 1, т.н. десната половина.
Добро, тоа, исто така, веќе се подредени.
Бројот 2 е сам.
Па сега имам две половини, лево и право, јас треба да ги спои заедно.
Дозволете ми да се даде некои екстра простор.
2 и го стави во таму, потоа 6 во таму, а со тоа
Сортирање таа листа, лево и десно, и тоа се спојуваат заедно, во крајна линија.
Па јас сум во нешто подобра форма.
Јас не сум се направи, бидејќи јасно 4, 8, 2, 6 не е конечниот нарачување што сакам.
Но јас сега имаат две листи на големина 2, кој имаат и, соодветно, се подредени.
Па сега ако ја премотам касетата на ум ти око, од каде што ни остави?
Почнав со осум елементи, тогаш јас тоа намалено сведува на левата половина од 4,
потоа на левата половина од 2, и потоа на десната половина на 2,
Го завршив, според тоа, сортирање лево половина од 2, и на десно половина од 2,
па што е третиот и последен чекор во оваа ситуација?
Морам да се спојат заедно две листи на големината 2.
Па ајде да одиме напред.
И на екранот тука, даде мене некои дополнителни меморија,
иако технички, забележите дека јас сум добив еден куп на празно место до врвот
таму.
Ако сакам да биде особено ефикасен простор мудар,
Јас само може да почне да се врти на елементи напред и назад, горе и долу.
Но, само за визуелна јасност, Одам да го стави долу,
да се задржи нешта убаво и чисто.
>> Па имам две листи на големината 2.
Првиот список има 4 и 8.
Втората листа има 2 и 6.
Ајде да се спојат овие заедно по некаков ред.
2, се разбира, е на прво место, а потоа 4, а потоа 6, а потоа 8.
И сега ние се чини дека се добива некаде интересно.
Сега сум подредени половина од листа, и случајно, тоа е
сите дури и броеви, но тоа е, всушност, само случајност.
И јас сега се решат од лево половина, така што тоа е 2, 4, 6, и 8.
Ништо не е на ред.
Дека се чувствува како напредок.
>> Сега ми се чини како да сум Разговараме засекогаш сега,
па што останува да се види дали ова алгоритам е, навистина, поефикасно.
Но, ние се случува преку тоа супер методично.
А компјутерот, се разбира, ќе го стори тоа како што.
Па каде сме?
Почнавме со осум елементи.
Јас подредени на левата половина од 4.
Ми се чини дека треба да се направи со тоа.
Па сега, следниот чекор е да се сортирање на десната половина на 4.
И овој дел можеме да одиме преку малку повеќе
брзо, иако сте добредојдени да ја премотам касетата или да се откажеш, само
мислам дека преку него на свој темпо, но она што
што го имаме сега е можност да се стори истото алгоритам на четири
различни броеви.
>> Па ајде да одиме напред, а се фокусира на десната половина, што ние сме тука.
На левата половина од кои десната половина, а сега
левата половина од лево половина од тоа право на половина,
и како можам да ги сортирате листа на големина 1 содржи смо број 1?
Тоа е веќе направено.
Како можам да го стори истото за листа големина 1 содржи само 7?
Тоа е веќе направено.
Чекор три за оваа половина тогаш е да се спојат овие два елементи
во нова листа на големина од 2, 1 и 7.
Се чини дека не го направиле сите дека многу интересна работа.
Ајде да видиме што се случува понатаму.
Јас само се подредени на левата половина од десната половина на мојот оригинален придонес.
Сега ајде да се најде решение за правото половина, кој содржи 5 и 3.
Ајде повторно се погледне на лево половина, подредени, десната половина, подредени,
и се спојат овие две заедно, во некои дополнителни простор,
3 е на прво место, а потоа доаѓа 5.
И така сега, ние се подредени левата половина од десната половина
на оригиналниот проблем, и на десната половина на десната половина
на оригиналниот проблем.
Што е третиот и последен чекор?
И да се спојат овие две половини заедно.
Па дозволете ми да се добијат некои екстра простор, но, повторно, јас
би можело да биде со користење дека резервни простор до врвот.
Но, ние ќе треба да се задржи едноставно визуелно.
Дозволете ми да се спојат во сега 1, и потоа 3, а потоа и 5, а потоа и 7.
А со тоа оставајќи ме сега со десната половина на оригиналниот проблем
тоа е совршено подредени.
>> Значи она што останува?
Се чувствувам како да го чуваат велејќи дека исти работи повторно, и повторно,
но тоа е одраз на Фактот дека ние сме со користење на рекурзијата.
Процесот на користење на алгоритам повторно, и повторно,
на помали подгрупи оригиналниот проблем.
Па јас сега имаат левата сортирани половина од оригиналната проблем.
Имам право сортирани половина на оригиналниот проблем.
Што е третиот и последен чекор?
Ох, тоа е спојување.
Па ајде да го направите тоа.
Ајде да се доделат дополнителни меморија, но мојот Бог,
тоа би можело да се стави било каде во моментов.
Имаме толку многу простор на располагање за нас, но ќе биде едноставно.
Наместо да одат назад и натаму со нашата изворна меморија,
ајде да го направи тоа визуелно овде долу под,
да завршам спојување на левата половина и десната половина.
>> Па со спојување, што треба да направам?
Сакам да се земе на елементи во ред.
Па гледајќи левата половина, Гледам првиот број е 2.
Гледам во десната половина, Гледам првиот број
е 1, па очигледно е кој број сакам да се извади,
и го стави на прво место во мојата конечна листа?
Се разбира, 1.
Сега сакам да прашам дека истото прашање.
На левата половина, јас сум сепак се искачи на број 2.
На десната половина, Имам број 3.
Кои Еден Дали сакам да се избере?
Се разбира, број 2 и сега се забележи на кандидатите
4 од левата страна, 3 од десно.
Ајде, се разбира, изберете 3.
Сега кандидатите се 4 на лево, 5 на десната страна.
Ние, се разбира, да одберат 4.
6 на левата, 5 на десната страна.
Ние, се разбира, да изберат 5.
6 од левата страна, 7 за правото.
Ние го избере 6, а потоа ние изберете 7, и тогаш изберете 8.
Voila.
>> Па голем број на зборови подоцна, ние се решат оваа листа на осум елементи
во листа на еден низ осум, кој се зголемува со секој чекор,
но колку време тоа не однесе да го направите тоа.
Па јас сум намерно поставени работите надвор сликовито
тука, така што можеме да вид на види или ценат поделбата
во освојувањето и тоа е се случува.
>> Навистина, ако се погледне назад во пресрет, Јас го напуштив сите овие точки линии
во променливи, можеш, вид, да се види, во обратен редослед,
ако вид на се погледне назад во историја сега, мојот првичен список
е, се разбира, на големина 8.
А потоа и претходно, јас бев кои се занимаваат со двете листи на големина 4,
а потоа четири листи на големина 2, а потоа осум листи на големина 1.
>> Значи она што го прави ова, вид, да ве потсетам на?
Па, всушност, секој од алгоритми имаме
погледна досега, каде што јаз, и поделба, а поделбата,
задржи има работи повторно, и повторно, резултира во оваа општа идеја.
И така, има нешто логаритамски случува тука.
И тоа не е сосема најавите на n, но тука е логаритамска компонента
за она што ние сме само направено.
>> Сега ајде да се разгледа како што навистина е.
Така да се логирате на n, повторно беше голем трчање време,
кога сме направиле нешто како бинарни пребарување, како што ние сега го нарекуваат,
стратегијата за поделба и освојување преку кој го најдовме Мајк Смит.
Сега технички.
Тоа е логаритам со основа 2 од n, па дури и иако во повеќето часови по математика,
10 е обично на база, која ќе ја преземе.
Но, компјутерски научници речиси секогаш размислуваме и зборуваме во однос на база 2,
па ние обично само велат дека најавите на n, наместо да се најавите база 2 од n,
но тие се точно една и истите во светот на компјутерските
науката, и како настрана, има постојана фактор
Разликата меѓу двете, така што е симулација онака, за повеќе формални причини.
>> Но, за сега, она што ни е гајле за е овој пример.
Значи, да не се докаже од пример, но во Најмалку користите пример на броеви
при рака, како разумност провери, ако сакате.
Така претходно формулата беше најавите база 2 од n, но она што е n во овој случај.
Имав n оригиналниот број, или 8 од оригиналниот број конкретно.
Сега тоа е малку време, но јас сум прилично
Осигурајте се дека најавите база 2 од вредноста 8 е 3,
и навистина, она што е убаво за што е 3 не е точно дека бројот на пати
дека може да се подели листа на должина 8 повторно, и повторно,
и повторно, се додека не си замина со списоци на само големината 1.
Нели?
8 оди до 4, оди до 2, оди до 1, а тоа е
рефлектира токму тоа слика имавме пред само еден миг.
Па малку здрав разум да се провери за тоа каде логаритам е, всушност, се вклучени.
>> Па сега, што друго е вклучена во оваа ситуација? n.
Така да се забележи дека секој време јас се подели на листата,
иако во обратен редослед во историјата тука, јас се уште се прави n работи.
Тој чекор, кој бара спојување Да допрам секој еден од броевите,
со цел да го слајд во соодветна локација.
Значи иако висината на овој дијаграм е со големина n најавите на n или 3,
конкретно, со други зборови, Го направив три дивизии тука.
Колку работа направив хоризонтално по должината на оваа шема секое време?
>> Па, јас не n чекори работат, затоа што ако јас сум
доби четири елементи и четири елементи, и јас треба да ги спои заедно.
Јас треба да поминат низ овие четири и овие четири,
конечно да ги спои назад во осум елементи.
Спротивно на тоа, ако имам осум прсти овде, што јас не се направи, и осум
fingers-- sorry-- Ако сум доби четири прсти овде,
што да правам, четири прсти овде, што да правам,
тогаш тоа е исто пример како и порано, ако го направам
имаат осум прсти иако во вкупно, што можам да, вид, се направи.
Можам да го направи токму тука, тогаш јас може секако
ги спои сите од овие листи големина 1 заедно.
Но јас сигурно мора да се погледне во секој елемент само еднаш.
Па на висината на овој процес е да се најавите n, ширината на овој процес, така да се каже,
е n, па она што се чини дека ние да има, во крајна линија, е
во времетраење од четири големина n log n пати.
>> Со други зборови, ние поделени листата, најавите n пати,
но секој пат кога ние го сторивме тоа, имавме за да допре секој еден од елементите
со цел да ги спои сите заедно, што
беше n чекор, па ние имаме n пати се најавите n, или како компјутерски инженер би рекол,
асимптоматично, која ќе биде голем збор
за да се опише на горниот врзани за време на работа,
ние се работи во голем о на log n време, така да се каже.
>> Сега ова е значајна, бидејќи потсетиме што трчање пати беа
со балон вид, и селекција вид, и вметнување вид,
па дури и неколку други кои постојат, n квадрат беше местото каде што бевме.
И можете да, вид, видете го тоа овде.
Ако n квадрат е очигледно n пати n, но тука имаме n пати се најавите n,
и ние веќе знаеме од недела нула, дека најавите n, логаритамски,
е подобар од нешто линеарна.
Впрочем, да се потсетиме на слика со црвена и жолта
и зелени линии кои ги привлече, на зелени логаритамски линија беше многу пониска.
И затоа, многу подобро и побрзо отколку директно жолти и црвени линии,
n пати се најавите n е, всушност, подобро од n-пати, n, или n квадрат.
>> Значи ние се чини дека имаат идентификувани алгоритам спојување
вид која работи во многу побрзо време, и навистина,
тоа е зошто, претходно оваа недела, кога видовме дека натпреварот помеѓу меур
вид, селекција вид, и се спојуваат вид, се спојат вид навистина, навистина победи.
И навистина, ние дури и не чекаат балон за сортирање и селекција вид
да заврши.
>> Сега да го земеме еден друг пас на ова, од малку повеќе
формална гледна точка, само во случај, ова одекнува подобро
повисока од онаа дискусија ниво.
Значи тука е алгоритам повторно.
Ајде да се запрашаме, она трчање време
е од овој алгоритми различни чекори?
Ајде да го поделат во првата случај и вториот случај.
АКО и на друго место во случај ако, Ако n е помалку од 2, само се вратат.
Се чувствува како временска константа.
Тоа е тоа, вид, како и два чекори, Ако n е помалку од 2, потоа да се вратат.
Но, како што рековме, во понеделникот, постојана време, или Биг О од 1,
може да биде два чекори, три чекори, дури 1.000 чекори.
Она што е важно е дека тоа е константен број на чекори.
Па жолтата истакна pseudocode тука тече во, ние ќе го наречеме,
временска константа.
Толку повеќе формално, и ние ќе to-- ова
ќе биде степенот до кој формализира ова право now-- Т од n,
трчање време на проблем кој ги зема n somethings како влез,
еднакво голем o на една, Ако n е помалку од 2.
Така, тоа е условено со тоа.
Така да биде јасно, ако n е помал од 2, имаме една многу кратка листа, тогаш
трчање време, T на n, каде што n е 1 или 0, во овој многу специфичен случај,
тоа е само ќе да биде константна време.
Тоа се случува да се земе една чекор, два чекори, сеедно.
Тоа е фиксен број на чекори.
>> Па сочно дел сигурно мора да биде во другиот случај во pseudocode.
Случај на друго место.
Сортирај левата половина од елементите, сортирање право половина на елементи, се спојат сортирани половини.
Колку време е секој од овие чекори се земе?
Па, ако водењето време да се најде решение за n елементи
е, ајде да го наречеме многу генерички, T на n,
тогаш сортирање лево половина на елементи
е, вид на, како да кажеш, T на n поделено со 2,
и слично, сортирање десната половина на елементи е, вид на, како да кажеш,
T на n поделена 2, а потоа спојување на подредени половини.
Па ако имам некои број на елементи тука,
како четири, а некои број на елементи овде, како четири,
и морам да се логирате секој од овие четири во, и секоја од овие четири, еден
по други, така што конечно имам осум елементи.
Таа се чувствува како тоа е голема о од n чекори?
Ако имам n прстите и секој од нив треба да се спојат во место,
тоа е како уште еден n чекори.
>> Така навистина formulaically, можеме да го изразат тоа,
иако малку scarily на прв поглед, но тоа е нешто
што ја доловува токму тоа логика.
Трчање време, Т на n, ако n е поголемо од или еднакво на 2.
Во овој случај, случајот што друго, е Т на n поделен со 2, плус на Т Н поделено со 2,
плус голем о на n, некои линеарни бројот на чекори,
можеби точно n, можеби 2 пати n, но тоа е грубо, цел на n.
Така што, исто така, е како можеме да изразат оваа formulaically.
Сега вие не би знаеле ова, освен сте го снимиле во твојот ум,
или да го гледам нагоре во задниот дел на еден учебник, дека
би можеле да имаат малку измамник лист на крајот,
но ова е, всушност, ќе се ни даде голема о од n log n,
бидејќи повторувањето дека што го гледате тука на екранот,
ако навистина го направив тоа надвор, со бесконечен број на примери,
или си го направила formulaically, ќе се види дека ова, затоа што таа формула
само по себе е рекурзивен, со т n над нешто по десната страна,
и t на N, по левата страна, ова може всушност, да се изрази, во крајна линија,
како голем движење на n log n.
Ако не е убеден, тоа е парична казна за сега, само
преземе за вера, дека тоа е, навистина, она што доведува до повторување,
но ова е само малку повеќе од една математички пристап да барате
во моментот работи на спојување вид само врз основа на нејзините pseudocode.
>> Сега ајде да ги малку издише од сето тоа,
и да ги разгледаме во некој одредени поранешниот сенатор, кој
Може да се погледне малку познати, кој разговараше со Ерик на Google
Шмит, пред некое време, за интервју на сцената, во предниот дел на целиот куп
на луѓето, зборува за тоа на крајот тема, тоа е прилично сега познато.
Ајде да ги разгледаме.
>> Ерик Шмит: Сега сенатор ти си тука во Google,
и сакам да мислам на претседателството на интервју за работа.
Сега е тешко да се добие работа како претседател.
Претседателот Обама: Токму така.
Ерик Шмит: А ти си случува да се направи [Беззвучен] сега.
Тоа е исто така тешко да се добие работа во Google.
Претседателот Обама: Токму така.
>> Ерик Шмит: Имаме прашања, и ги замолуваме нашите кандидати прашања,
и овој е од Лари Швимер.
>> Претседателот Обама: Во ред.
>> Ерик Шмит: Што?
Вие момци мислам дека сум шегуваш?
Тоа е право тука.
Што е најефикасен начин да се средиме милион 32 битни цели броеви?
>> Претседателот Обама: Well--
Ерик Шмит: Понекогаш, можеби и жал ми е, maybe--
Претседателот Обама: Не, не, не, не, не, јас think--
Ерик Шмит: Тоа не е it--
Претседателот Обама: јас мислам, мислам меурот
вид би бил погрешен начин да се оди.
Ерик Шмит: Ајде.
Кој го кажа тоа?
ВО РЕД.
Јас не науката компјутер on--
>> Претседателот Обама: Ние сме Влеговме нашите шпиони во таму.
ПРОФЕСОРОТ: Во ред.
Ајде да го оставиме зад нас сега теоретски свет на алгоритми
во асимптотска анализа од него, како и да се вратат некои теми
од недела нула и еден, и да почне да се отстранат некои помошни тркала,
ако сакате.
Така што навистина се разбере на крајот од земјата нагоре, што е
случува под хаубата, кога ќе пишувам, состави, како и извршување на програми.
Потсетиме особено, дека ова е првата програма С ние погледна,
канонски, едноставна програма на сорти, условно кажано,
назначено со тоа, отпечатоци, Здраво светот.
И да се потсетиме дека реков, процесот дека изворниот код оди преку
е токму ова.
Ве однесе вашиот изворен код, да помине тоа преку компајлер, како ѕвекот,
и надвор доаѓа објектниот код, што може да изгледа вака, нули и единици
дека процесорот на компјутерот, централно единица за обработка или мозокот,
во крајна линија го разбира.
>> Излегува дека тоа е малку на симплификација,
дека сега сме во позиција да ги разграничат
за да се разбере она што е навистина се случува под хаубата
секој пат кога ќе се кандидира Ѕвекот, или поопшто,
секој пат кога ќе се направи програма, Направете користење и CF 50 ИРО.
Особено, работи како Ова е прво се создава,
кога за прв пат се состави својата програма.
Со други зборови, кога ќе да направиш тест на изворниот код
и состави, што е прв се емитираат од ѕвекот
е нешто познат како асемблерски код.
И всушност, изгледа токму вака.
>> Истрчав команда во командната линија порано.
Ѕвекот цртичка капитал ОК hello.c, и тоа создаде датотека
за ме повика hello.s, во внатрешноста на кој беа баш
овие содржини, и малку повеќе погоре и малку повеќе подолу,
но јас сум се стави на juiciest информации тука на екранот.
И ако погледнете внимателно, ќе видите барем неколку познати зборови.
Имаме главните на врвот.
Имаме printf надолу во средината.
И ние исто така имаат здраво светот обратна коса црта n во наводници долу.
>> И сè друго во тука инструкции е на многу ниско ниво
дека процесорот на компјутерот го разбира.
Инструкции процесорот, кои се движат меморија околу себе, дека товарот низи од меморијата,
и на крајот, за печатење работите на екранот.
Сега што се случува иако по оваа асемблерски код е генерирана?
На крајот на краиштата, тоа го правите, навистина, сеуште генерира објектниот код.
Но чекорите кои имаат навистина се случува под хаубата
изгледа малку повеќе се допаѓа ова.
Изворниот код станува асемблерски код, кој потоа станува објектниот код,
и оперативни зборови тука се дека, кога ќе компајлирате вашиот изворен код,
да излезе надвор код собранието, а потоа кога ќе се соберат вашиот асемблерски код,
да излезе надвор објектниот код.
>> Сега ѕвекот е супер софистицирани, како многу компајлери,
и тоа го прави сите овие чекори заедно, и тоа не мора да значи
излез меѓувремени додадени фајлови: дека дури и може да се види.
Тоа само ги собира нешта, кој е општ термин кој
го опишува целиот процес.
Но, ако навистина сакаат да се биде конкретен, има
многу повеќе се случува таму, како и.
>> Но, ајде да исто така, сметаат дека дури и сега тоа супер едноставна програма, hello.c,
нарече функција.
Го нарече printf.
Но, јас не пишувам printf, навистина, кој доаѓа со в, така да се каже.
Тоа е функција која е се потсетиме прогласена во стандард io.h, која
е насловот датотека, која е тема ќе всушност
нурне во повеќе длабочина пред долго.
Но хедер датотека е обично придружени
од страна на фајл код, изворниот код датотека, па слично како што постои стандарден io.h.
>> Пред некое време, некој, или нечија, исто така, пишува
фајл наречен стандард io.c, во која вистинските дефиниции,
или имплементации на printf, и гроздовете на други функции,
се всушност напишана.
Па со оглед на тоа, ако се има предвид да се има тука на левата, hello.c, дека кога
состави, ни дава hello.s, дури и ако Ѕвекот не се интересира за заштеда на место
можеме да го видиме, и дека асемблерски код добива собраа во hello.o, која
е, навистина, стандардно име со оглед кога и да собере извор
код во објектниот код, но не се сосема подготвен да го изврши уште,
бидејќи уште еден чекор мора да се случи, и има
се случува во последните неколку недели, можеби непознат за вас.
>> Конкретно некаде во CS50 ИРО, а тоа,
исто така, ќе биде малку на симплификација за момент,
постои, или тоа беше многу одамна, фајл наречен стандард io.c,
дека некој компајлирана во стандард io.s или еквивалент,
дека некој потоа составуваат во стандарден io.o,
или што излезе во малку поинаков датотека
формат, кој може да има различни екстензија целосно,
но во теоријата и концептуално, точно тие чекори мора да се случи во некоја форма.
А тоа е да се каже, дека сега кога сум пишување програма,
hello.c, дека едноставно вели: Здраво светот, и јас сум со користење на кодот на некој друг
како printf, кој некогаш беше врз основа на време, во датотека наречена стандард io.c,
тогаш некако морам да земам објектниот код, мојата нули и единици,
и објектот на тоа лице кодот, или нули и единици,
и некако ги поврзат заедно во една конечна датотека, наречен здраво, дека
има сите од нули и единици оние од мојата главна функција,
и сите на нули и оние за printf.
>> И навистина, дека минатата процес е нарекува, поврзување на вашиот објектниот код.
На излез од кои е извршна датотека.
Па во праведноста, во крајот на денот, ништо
е сменета од една недела, кога ќе прв пат започна составувањето на програмите.
Навистина, сето ова е случува под хаубата,
но сега сме во позиција секаде каде што можеме, всушност,
разграничат овие различни чекори.
И навистина, на крајот на ден, ние сме се уште
остави со нули и единици, кои е, всушност, голема segue сега
на друга способност на C, дека ние не сме морале да се потпора најверојатно
до денес, познат како bitwise оператори.
Со други зборови, досега, во секое време имаме занимаваа со податоци во C или променливи во C,
ние сме имале вакви работи знаци и плови и in-
и копнее и двојки и слично, но сите оние кои се најмалку осум бита.
Ние се уште не сум бил во можност да манипулира со индивидуални битови,
и покрај тоа што еден поединец малку, ние знаеме, може да претставуваат на 0 и 1.
Сега излегува дека во C, можете може да се добие пристап до индивидуалните битови,
ако знаеш синтаксата, со која треба да допреме до нив.
>> Па ајде да ги разгледаме во bitwise оператори.
Па сликата тука се и неколку симболи кои ние сме, вид, на некој начин, видел.
Гледам симболот, вертикална бар, а некои други, како и,
и да се потсетиме дека симболот со симболот е нешто што го видел.
Логички и оператор, каде што треба двајца од нив заедно, или логичката или
оператор, каде што имаат две вертикални линии.
Bitwise оператори, кои ние ќе види работат на битови поединечно,
само да се користи еден симболот, односно една вертикална лента, на каре симбол
следува потоа, малку тилда, а потоа замина
Држач остави држач или десната заграда десната заграда.
Секој од овие имаат различни значења.
>> Всушност, ајде да ги разгледаме.
Ајде да одиме старата школа и денес, и употреба екран на допир од недалечното минато,
познат како бела табла.
И ова бела табла ќе ни овозможи
да искажат некое прилично едноставна симболи, или подобро кажано, некои прилично едноставни формули,
што можеме потоа на крајот потпора, со цел
за пристап до индивидуални битови во програмата C.
Со други зборови, да го направиме тоа.
Ајде прво да се зборува за момент за симболот,
кој е bitwise И оператор.
Со други зборови, ова е оператор кој им овозможува на
мене да има променлива a Лево Типично, променлива и десната страна,
или индивидуална вредност, дека ако ние и нив заедно, ми дава конечниот резултат.
Значи она што сакам да кажам?
Ако во една програма, ќе имаат променлива кој продавници еден од овие вредности,
или ајде да ја задржиш едноставен, и само пишувам од нули и единици поединечно,
Еве како функционира операторот на симболот.
0 0 симболот ќе изнесува 0.
А зошто е тоа така?
>> Тоа е многу сличен на Булова изрази,
дека сме разговараа досега.
Ако мислите дека на крајот на краиштата, на 0 е лажни, 0 е лажна, неточни и лажни
е, како што сме разговараа логично, исто така, неточно.
Па да добиеме 0 и тука.
Ако се земе 0 симболот 1, и тоа, исто така,
ќе биде 0, бидејќи за тоа изразување на левата страна за да биде вистина или 1,
за тоа ќе треба да биде вистина и точно.
Но, тука имаме лажна и точно, или 0 и 1.
Сега повторно, ако имаме 1 симболот 0, тоа, исто така, се случува да биде 0,
и ако имаме 1 симболот 1, конечно имаме 1 бит.
Значи со други зборови, да не правиш ништо интересно со овој оператор
само уште, ова го симболот оператор.
Тоа е bitwise и оператор.
Но, ова се состојки преку кои можеме да направиме
интересни работи, како што наскоро ќе се види.
>> Сега да ги погледнеме во само еден вертикалната лента овде на десната страна.
Ако имам 0 малку и јас Или тоа со, bitwise
ИЛИ оператор, друга 0 бит, кој ќе ми даде 0.
Ако јас земам 0 бит и или тоа со 1 бит, а потоа јас ќе одам да се добие 1.
И всушност, само за јасност, дозволете ми да се вратам,
така што мојот вертикални решетки не се помешаат со 1 е.
Дозволете ми да го преработи уште еднаш на сите мојот 1 е малку повеќе
јасно, така што можеме да видиме следната, ако можам имаат 1 или 0, што се случува да биде 1,
и ако имам 1 или 1, кој, исто така, се случува да биде 1.
Па можете да видите дека логично ИЛИ оператор се однесува на различен начин.
Ова ми дава 0 или 0 ми дава 0, но секоја друга комбинација ми дава 1.
Толку долго како што јас имам еден 1 во формула, резултатот ќе биде 1.
>> Од друга страна со И оператор, симболот,
само ако имам две 1 во равенка, можам да всушност се добие 1 надвор.
Сега има неколку други оператори, како и.
Еден од нив е малку повеќе вклучени.
Па дозволете ми да оди напред и да се избрише ова за да се ослободи некои простор.
И ајде да ги разгледаме во карет симбол, за само еден миг.
Ова е типично карактер може да се тип
на тастатурата за држење Shift и а потоа еден од броевите на врвот на вашата САД
тастатура.
>> Значи ова е ексклузивен ИЛИ оператор, ексклузивни или.
Па ние само видов на операторот или.
Ова е ексклузивна или оператор.
Што е всушност разликата?
Па ајде да погледнеме во формула, и да го користи ова како состојки во крајна линија.
0 XOR 0.
Јас ќе одам да се каже е секогаш 0.
Тоа е дефиницијата на XOR.
0 XOR 1 ќе биде 1.
1 XOR 0 ќе биде 1, и 1 XOR 1 ќе биде?
Во ред?
Или десно?
Не знам.
0.
Сега што се случува овде?
И се размислува за Името на овој оператор.
Ексклузивни или, па како име, вид, сугерира,
одговорот е само нема да биде 1 ако влезови се ексклузивни,
исклучиво поинаква.
Па еве инпутите се исти, па излез е 0.
Тука инпутите се исти, па излез е 0.
Еве ги резултатите се различни, тие се ексклузивни, така и на излез е 1.
Па тоа е многу сличен на И, тоа е многу сличен,
или подобро кажано, тоа е многу сличен на ИЛИ, но само во ексклузивното начин.
Оваа не е повеќе од 1, бидејќи имаме две 1 е,
а не исклучиво, само еден од нив.
Во ред.
Што е со другите?
Добро тилда, пак, е всушност, убав и едноставен, за среќа.
И ова е унарен оператор, што значи
тоа е се применува на само еден влез, еден операнд, така да се каже.
Да не се од левата и десната страна.
Со други зборови, ако се земе тилда на 0, одговорот ќе биде спротивното.
И ако се земе тилда од 1, Одговорот ќе има спротивен.
Па тилда оператор е начин на негирањето малку,
или гледаме малку од 0 до 1, или 1 до 0.
>> И тоа ни остава конечно со само две финалето оператори,
т.н. лево смена, и т.н. право оператор смена.
Ајде да ги разгледаме во тоа како тие работат.
Операторот на лево смена, напишана со два аглести загради, како што,
работи како што следи.
Ако мојот влез, или мојот операнд, на лево оператор смена е сосема едноставно, од 1.
И јас потоа да му кажете на компјутерот лево смена дека 1, велат седум места,
резултатот е како да сум земе дека 1, и да ја преместите
седум места во текот на лево, и по дифолт,
ние ќе треба да се претпостави дека просторот на правото
ќе биде поместена со нули.
Со други зборови, 1 лево смена 7 се случува да ми даде дека 1, проследено со 1, 2, 3,
4, 5, 6, 7 нули.
Значи на некој начин, тоа ви овозможува да се земе мал број како 1,
и јасно да се направи тоа многу многу, многу поголема во овој начин,
но ние сме, всушност, се случува да се види повеќе умен пристапи за тоа
наместо тоа, како и,
>> Во ред.
Тоа е тоа за три недели.
Ние ќе се видиме следниот пат.
Ова беше CS50.
>> [Музички]
>> ЗВУЧНИЦИ 1: Тој беше на снек бар јаде топла празни епови мелба.
Тој сето тоа имаше на неговото лице.
Тој е облечен дека чоколадата како брада
ЗВУЧНИЦИ 2: Што правиш?
ЗВУЧНИЦИ 3: Хммм?
Што?
>> ЗВУЧНИЦИ 2: Дали само двоен натопи?
Сте двојно натопи чип.
ЗВУЧНИЦИ 3: Се извинувам.
ЗВУЧНИЦИ 2: натопи чип, вие каснав малку, и ќе натопи повторно.
ЗВУЧНИЦИ 3:
ЗВУЧНИЦИ 2: Значи тоа е како ставање целото ваше право устата во натопи.
Следниот пат кога ќе се земе еден чип, само да го натопи одеднаш, и стави крај на тоа.
>> ЗВУЧНИЦИ 3: Знаеш што, Дан?
Ви натопи на начинот на кој сакате да се натопи.
Јас ќе се натопи на начинот на кој сакам да се натопи.