>> [Мусиц плаиинг]
>> ПРОФЕСОР: У реду.
То је ЦС50 а ово је крај недеље три.
Дакле, ми смо овде данас, не Сандерс Позориште, уместо у Веиднер библиотеци.
Унутар чији је студио познат као Хаусер Студио,
или ћемо рећи Студио Х, или ће ми говоре-- Ако сте уживали у онај виц,
то је у ствари од школски друг, Марко, на мрежи,
који је предложио толико преко Твиттер.
Шта је сад супер о што сам овде у студију
је да сам окружен ове зелене зидови, зелени екран или Цхромакеи,
да тако кажем, што значи да је ЦС50 продукцијски тим, без знања за мене
сада би могло бити стављање ме највише било где у свету,
за боље или горе.
>> Шта сад лежи испред, проблема сет два је у вашим рукама за ову недељу,
али са проблемом сет три ове недеље,
бићете изазов са тзв игра 15,
стара странка услугу која можда се сећате пријема
као дете које има гомилу бројева који могу да клизе горе, доле,
лево и десно, и ту је једна празнина у оквиру слагалице, у којој сте
заправо може клизи те делове слагалице.
На крају сте добили ово пуззле у неком полу случајним редоследом,
а циљ је да се Сорт Ит, од врха до дна,
лева на десно, од једног скроз горе до 15.
>> Нажалост, имплементација имаћете при руци
ће бити софтвер заснована, не физички.
Стварно ћеш морати написати Код са којим студент или корисник може
играју игру 15.
И у ствари, у хакер издање игре 15,
ћете бити изазов за имплементацију, не само свирање ове старе школе
игра, већ решавање о томе, спровођење Год Моде,
да тако кажем, који заправо решава слагалицу за човека,
пружајући им хинт, после наговештаја, после наговештаја.
Дакле, више о тој следеће недеље.
Али то је оно што је пред нама.
>> За сада се сетим да је раније ове недеље имали смо Цлиффхангер, ако хоћете,
при чему је најбољи смо радили за сортирање Мудар је био горња граница Биг О од н
квадрат.
Другим речима, балон врста, Избор врста, уметање врста,
сви они, а различити у њиховој реализацији,
пренета у једном н на квадрат руннинг Време у врло најгорем случају.
И генерално претпостављамо да веома најгори случај за сортирање
је онај који ти улази потпуно уназад.
И заиста, то је прилично неколико корака да спроведе сваки од тих алгоритама.
>> Сада на самом крају класе опозив, упоредили смо буббле врсту
против селекције врсте против једног другог да смо звали стапања врсту у то време,
и ја предлажем да се узима Предност лекције из недеље
нула, завади па владај.
И некако постизање неке врсте логаритамске времена рада на крају,
уместо нечега То је чисто квадратна.
И није баш логаритамска, то је мало више од тога.
Али, ако се сећате из класе, било је много, много брже.
Хајде да погледамо где смо стали.
>> Буббле сорт односу на избор Сортирај у односу на стапања врсте.
Сада су сви јуримо у теорију, у исто време.
Процесор ради на истом брзином.
Али можете осетити како ова досадна врло брзо ће постати,
и колико брзо, када смо убризгати мало недеље Зеро алгоритама,
можемо убрзати ствари.
>> Тако ознака врста изгледа невероватно.
Како можемо да искористе, како за сортирање бројева брже.
Па хајде да размислим до састојак који смо
Имао поново у недељу нула, а то је у потрази за некога у телефонском именику,
и сећам се да је Псеудокод да смо предложили,
преко којих можемо да нађемо неко као Мајк Смит,
Погледао нешто овако.
>> Сада погледајте у посебно у линији 7 и 8, и 10 и 11,
који изазивају ту петљу, где смо држали да се вратимо на линији 3 опет, и опет,
и поново.
Али испоставило се да можемо да видите Овај алгоритам, овде у псеудокоду,
мало више холистички.
У ствари, оно што ја тражим у овде на екрану,
је алгоритам за претрагу Мајк Смит међу неког скупа страница.
И заиста, могли смо да поједноставимо алгоритам у тим линијама 7 и 8,
и 10 и 11 да кажем само ово, које сам представио овде у жуто.
Другим речима, ако Мајк Смит је раније у књизи,
не треба да одредите корак по корак сад како да га нађем.
Ми не морамо да одредите да се вратимо на линији 3,
зашто не бисмо уместо тога, рецимо, уопштеније,
сеарцх фор Мике у лева половина књиге.
>> С друге стране, ако је Мајк заправо касније у књизи,
зашто не бисмо под знацима навода претрагу за Мике у десној половини књиге.
Другим речима, зашто не бисмо некако пунт да сами говоре,
сеарцх фор Мике у овом подскуп књиге,
и оставите га да нашим постојећим алгоритам да нам каже
како да тражи у Мике да лева половина књиге.
Другим речима, наш алгоритам ради да ли је
телефонски именик ове дебљине, овога дебљине, или било дебљине уопште.
Тако смо рекурсивно цан дефинишу овај алгоритам.
Другим речима, на Екран овде је алгоритам
за тражење Мике Смитх међу страницама именика.
Дакле, у складу 7. и 10., идемо само реци управо то.
И ја користим овај термин на тренутак пре, и заиста, рекурзије
је крилатица за сада, и то је тај процес
да уради нешто цикличне од некако коришћењем код који сте већ,
и називајући поново, и опет, и опет.
Сада ће бити важно да смо некако дно
напоље, а не да раде бесконачно дуго.
У супротном ћемо имају заиста бесконачну петљу.
Али хајде да видимо да ли можемо да позајмим идеју од рекурзије, опет радим нешто
и опет и опет, да се реши проблем сортирање преко спајања
врста, све ефикасније.
>> Зато сам вам дати врста спојити.
Хајде да погледамо.
Дакле, овде је Псеудокод, са који би могли имплементирати сортирање,
Коришћењем овог алгоритма који се зове спајање врста.
И то је једноставно ово.
На улазу н елемената, Другим речима, ако сте
с обзиром н елемената и бројеви и писма или шта год је унос,
ако ти је дато н елемената, ако н мање од 2, само се врати.
Jel tako?
Јер ако н је мања од 2, то значи да је мој списак елемената
је или величине 0 или 1, и у оба та тривијалним случајевима,
листа је већ сортирају.
Ако нема листа, то је средјено.
И ако постоји списак дужине 1, то је очигледно поредани.
Дакле, алгоритам треба само да Заиста нешто занимљиво,
ако имамо два или више елементи дато нама.
Дакле, хајде да погледамо магију онда.
Друго сортирање левој половини елемената, затим сортирање десне половине елемената,
затим се стапа сортиране половине.
А шта је некако ума савијања овде, да не знам стварно
изгледају да су ти рекао ништа још увек, зар не?
Све што сам рекао је, с обзиром списак н елемената, сортирају левој половини,
онда је десна половина, онда спојити сортиране половине,
али где је стварна тајни сос?
Где је алгоритам?
Па испада да те две линије Прво, врста левој половини елемената,
и некако десна половина елемената, су рекурзивни позиви, да тако кажем.
>> Уосталом, ово тачка у времену, имам
алгоритам са којима се сортирање гомилу елемената?
Да.
То је овде.
То је овде на екрану, и тако да могу да користе тај исти скуп корака
за сортирање левој половини, колико могу десна половина.
И заиста, опет, и опет.
Дакле, на неки начин, и ми ускоро види ово, магију стапања врсте
је уграђен у томе веома финалу линија, спајање разврстане половине.
И то изгледа прилично интуитивно.
Узмеш две половине, и ти, некако, споји их заједно,
па ћемо видети конкретно у овом тренутку.
>> Али ово је комплетан алгоритам.
И да управо зато видимо.
Па претпоставимо да смо дали те исте Осам елемената овде на екрану, један
кроз осам, али они су у наизглед случајним редоследом.
А циљ је на дохват руке за сортирање ове елементе.
Па како да идем о ради се користе, опет,
спајање врста, по овом псеудокоду?
И опет, Окорио ово ваш ум, само на тренутак.
Први случај је прилично тривијална, ако је мање од 2,
само се врати, нема посла да се уради.
Дакле, стварно само три ту кораци да стварно имати на уму.
Опет, и опет, ја сам хтети да има
за сортирање левој половини, сортирање десној половини,
и онда када им Две половине су поредани,
Желим да их споји заједно у један сортирани списак.
Дакле, имајте то на уму.
>> Дакле, овде је оригинална листа.
Хајде да третирамо ово као Арраи, као што смо почели да
у недељу две, што представља суседни блок меморије.
У овом случају, садрже осам Бројеви, бацк то бацк то бацк.
А да се сада примењују стапања врсту.
Дакле, прво желим да средим лева половина ове листе,
И да, стога, фокусирати на 4, 8, 6, и 2.
>> Како сад да идем о сортирање листу величине 4?
Па ја сад морам да размотри сортирање леве левој половини.
Опет, да уназад за тренутак.
Ако је Псеудокод је ово, и ја дао осам елемената,
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.
Воила.
>> Дакле, огроман број речи касније, су поредани ову листу од осам елемената
у листу један кроз осам, који расте са сваком кораку,
али колико времена урадили нам требати за то.
Па ја сам намерно ених ствари сликовито
овде, тако да можемо некако види или ценити поделу
у освајању да се дешава.
>> Заиста, ако се осврнете на трагу, Оставио сам све ове тачкастим линијама
у носиоцима месту, можете, врста, види, обрнутим редоследом,
ако врста лоок бацк у Историја сад, моја првобитна листа
је, наравно, величине 8.
А онда раније, био сам суочавање са две листе величине 4,
а затим четири листа величине 2, затим осам листе величину 1.
>> Дакле, шта ово, врста, да вас подсетим?
Свакако, било који од алгоритми смо
Погледао до сада где смо завади, и поделе, и подела,
даље имам ствари поново, и Опет, резултати у овом општем идеји.
И тако нешто логаритамске се овде дешава.
И није баш дневник н, али ту је логаритамска компонента
да оно што смо управо урадили.
>> Сада ћемо размотрити како то заправо јесте.
Дакле, лог Н, поново био велики трајање,
када смо урадили нешто слично бинарна претрага, као што сада зову,
подела па владај стратегије преко које смо нашли Мике Смитх.
Сада технички.
То је дневник база 2 Н, чак и иако у већини класа математике,
10 је обично основа да претпоставимо.
Али компјутерски научници скоро увек мисле и говоре у смислу основе 2,
тако да смо углавном само рећи дневника н, уместо лог основом 2 од н,
али они су тачно један и Исто у свету рачунара
науке, и као успут, постоји стални фактор
Разлика између та два, тако да је Моот сваком случају, за више формалних разлога.
>> Али за сада, оно што ми је стало о је овај пример.
Дакле, немојмо докаже пример, али у најмање користе пример бројева
при руци као проверу исправности, ако хоћете.
Дакле, претходно је формула била евиденција база 2 од н, али оно што је н у овом случају.
Имао сам н оригиналне бројеве, или 8 оригиналне броја конкретно.
Сада је мало док, али сам прилично
да ли дневник база 2 од вредности 8 је 3,
и заиста, шта је лепо о томе се да 3 је управо број пута
да можете поделити списак дужине 8 опет, и опет,
и опет, све док сте напустили са списковима само величине 1.
Jel tako?
8 иде до 4, иде на 2, иде до 1, и то је
одражава управо то слика коју смо имали пре неколико тренутака.
Дакле, мало разум проверите и где логаритам је заправо укључен.
>> Дакле, сада, шта још је укључен овде? н.
Дакле, приметио да сваки пут када сам поделио списак,
мада у обрнутом редоследу у историји овде, ја сам још увек радиш ствари н.
То спајање корак потребно да Ја тоуцх сваки од бројева,
како би га склизне у њена одговарајућа локација.
Дакле, иако је висина ове дијаграм је величина дневника н од н или 3,
конкретно, другим речима, Ја сам три дивизије овде.
Колико посла сам хоризонтално урадити дуж овог графикону сваки пут?
>> Па, јесам н кораке радити, јер ако имам
Има четири елемента и четири елемента, и морам да их спојити заједно.
Морам да идем кроз ово четворо и њих четири,
на крају спојити их назад у осам елемената.
Ако обрнуто имам осам прстију овамо, што не знам, и осам
фингерс-- је-- Ако сам Има четири прста овде,
што да радим, четири прста овамо, што радим,
онда је то исто пример као и раније, ако то урадим
има осам прсте, иако у укупно, што могу, некако, да.
Ја тачно могу да радим овде, онда свакако да могу
спајање свих ових спискова величине 1 заједно.
Али свакако да погледам у сваком елементу тачно једанпут.
Дакле, висина овог процеса је лог н, ширина овог процеса, да тако кажем,
је н, тако да оно што изгледа да, на крају, је
руннинг време величине н пута лог н.
>> Другим речима, ми подијељени листа, евиденција н пута,
али сваки пут смо то урадили, имали смо да додирне сваки од елемената
како би их спојили сви заједно, што
Вас н корак, тако да имамо н пута лог н или као компјутерски научник би рекли,
асимптотично, која ће бити велика реч
да опише горњи везан на време рада,
трчимо у Биг О од лог н време, да се тако изразим.
>> Ово је значајно, јер сећате шта су руннинг пута били
са буббле сорт, и избор врста, и уметање врста,
па чак и неколико других које постоје, Н квадрат је где смо били у.
И можете, некако, погледајте ово овде.
Ако је н квадрат је очигледно н пута Н, али овде имамо н пута лог н
а ми већ знамо из недеље нула, то лог н, логаритамска,
је боље него нешто линеарно.
Уосталом, сећам се слику са црвеном и жута
и зелене линије које смо изазвале, Тхе зелена логаритамске линија је била много мања.
И зато, много боље и брже од равне жуте и црвене линије,
н пута лог н је, заиста боље, него н пута н, или н квадрат.
>> Дакле, изгледа да имамо идентификовао стопи алгоритам
врста која ради у много бржи пут, и заиста,
Зато, раније ове недеље, када видели смо да је такмичење између буббле
врста, избор врста и спајање врста, спајање врста стварно, стварно победио.
И заиста, нисмо ни чекати за буббле сорт и избор врсте
завршити.
>> Сада узмимо још једну пропусницу ово, са мало више
формалне тачке гледишта, само у случају, то одјекује боље
од тога виши ниво дискусије.
Ево опет алгоритам.
Хајде да се запитамо, шта руннинг тиме
је ово алгоритама различите кораке?
Хајде да га поделимо на први Случај и други случај.
ИФ и друго у случају да, Ако је н мање од 2, само се врати.
Осећа се сталном време.
То је, некако, као два корака, Ако је н мање од 2, а затим се вратите.
Али, као што смо рекли у понедељак, константа време, или Биг О 1,
могу бити два корака, три кораци, чак 1.000 корака.
Оно што је битно је да је исти број корака.
Дакле, жута истакао Псеудокод овде ради у, ми ћемо га назвати,
константа време.
Тако је формално више, и идемо да-- ово
биће у којој мери смо формализују то право сада-- Т Н,
прирастао време проблем да се н Сометхинг као улаз,
једнако Биг О једне, Ако је н мање од 2.
Дакле, то је условљено о томе.
Дакле, да буде јасно, ако је н мање од 2, имамо врло кратак списак, а затим
руннинг тиме, Т. од н, где је н 1 или 0, у овом веома конкретном случају,
само ће бити константна времена.
То ће трајати један корак, два корака, како год.
То је фиксни број корака.
>> Дакле, сочно део сигурно бити у друга случај у псеудокоду.
Елсе случај.
Врста лева половина елемената, некако у реду половина елемената, спајање разврстане половине.
Колико дуго траје сваки од ових корака узети?
Па, ако је трчање Време за сортирање н елемената
је, назовимо то врло генерички, Т. од н,
затим сортирање лево половина елемената
је, некако, као да кажеш, Т од н подељено са 2,
и слично сортирање десне половине елемената је, некако, као да кажеш,
Т од н подељена 2, а затим спајањем сортиране половине.
Па ако Имам неке број елемената овде,
као четири, а неки број елемената овде, као четири,
и ја морати да се повежу сваки од ова четири у, и свака од ових четири у, један
после друге, тако да на крају крајева ја имам осам елемената.
Изгледа као да је Биг О од н корака?
Ако имам н прсте и свака од да мора да се споје у месту,
то је као да још н корака.
>> И заиста формулаицалли, можемо изразити ово,
мада мало сцарили у почетку поглед, али то је нешто
да снима баш ту логику.
Време ради, Т од н, ако је н је већи од или једнако 2.
У овом случају, елсе случају, је Т од н подељено са 2 плус Т од н подељено са 2,
плус Биг О Н, неки линеарна број корака,
можда тачно, можда н 2 пута Н, али је отприлике ред н.
Тако да је, такође, како можемо изразити ово формулаицалли.
Сада не знам, осим ако сте га снимили у вашем уму,
или га потражите у задњи део уџбеника, који
можда има мало Цхеат Схеет на крају,
али ово је, заиста, да дај нам велики О од н лог н,
јер рекурентну која ви овде видите на екрану,
ако га стварно урадили да, са бесконачан број примјера,
или сте то урадили формулаицалли, ти би видим да ово, јер ове формуле
Сама је рекурзивни, са т Н преко нечега на десној страни,
и т н преко са леве стране, ово може заправо може изразити, на крају,
као велики иди од н лог н.
Ако није убеђен, да је Добро за сада, само
преузимају вери, да је то, заиста, шта је то рецидив доводи до,
али ово је само мало више Паге математички приступ у потрази
у покренут време стапања врсте на основу своје псеудокоду сам.
>> Сада узмимо мало бреатхер од свега тога,
те да погледам сигурно бивши сенатор, који је
може изгледати мало познато, који седе са Гоогле Ериц
Шмит, пре извесног времена, за интервју на бини, испред гомила
људи, говори о крају тема, то је прилично сада познато.
Хајде да погледамо.
>> Ерик Шмит: Сада сенатор, да си овде на Гоогле,
и ја волим да мислим да од Предсједништво као интервју за посао.
Сада је тешко добити посао као председника.
Председник Обама: Добро.
Ерик Шмит: А ти си урадити [неразумљиво] сада.
Такође је тешко добити посао у Гоогле-у.
Председник Обама: Добро.
>> Ерик Шмит: Ми имамо питања, и тражимо наших кандидата питања,
а ово је један од Ларри Швимер.
>> Председник Обама: У реду.
>> Ерик Шмит: Шта?
Мислите да се шалим?
То је овде.
Који је најефикаснији начин да се сортирање милиона 32 битне целе бројеве?
>> Председник Обама: Па--
Ерик Шмит: Понекад, Можда Жао ми је, маибе--
Председник Обама: Не, не, Не, не, не, мислим--
Ерик Шмит: То није то--
Председник Обама: Ја Мислим, мислим да је мехур
Сорт би био погрешан пут којим треба ићи.
Ерик Шмит: Хајде.
Ко му је то рекао?
ОК.
Нисам рачунар наука ајде--
>> Председник Обама: Морамо имамо своје шпијуне тамо.
ПРОФЕСОР: У реду.
Оставимо иза нас сада теоријски свет алгоритама
у Асимптотска истих, и вратите се у неким темама
од недеље нула и један, и старт да уклоне неке точкова обуке,
ако хоћете.
Тако да заиста разумеју на крају из темеља, што је
дешава испод хаубе када вас пишу, састављају и извршава програме.
Подсетимо посебно, да је први Ц програм смо гледали,
канонски, једноставан програм нека врста, релативно говорећи,
где, он га штампа, Хелло Ворлд.
И сећам се да сам рекао, процес да изворни код пролази кроз
је управо то.
Узмеш свој изворни код, пролазе се кроз компајлер, као Цланг,
и изађе објецт код, који може изгледати овако, нула и јединица
да процесор рачунара, централно обрада јединица или мозга,
на крају разуме.
>> Испоставило се да је то помало поједностављења,
да смо сада смо у Положај то теасе осим
да разумете шта је заиста био дешава испод хаубе
сваки пут када покренете Кланг, или уопште,
сваки пут када направите програм, користећи Направите и ЦФ 50 САТА.
Посебно, такве ствари ово је прво генерише,
када сте први пут саставити ваш програм.
Другим речима, када вас узети изворни код
и саставити га, шта је прва се имати излаз од Цланг
је нешто познат као склапање кода.
И у ствари, изгледа баш овако.
>> Водио сам командом у командна линија раније.
Цланг Дасх главног града с хелло.ц, и то је створио слику
за мене зову хелло.с, унутар којих се тачно
ови садржаји, и мало више изнад и мало више у наставку,
али сам ставио Јуициест информације овде на екрану.
А ако мало боље погледате, видећете бар неколико познатих кључне речи.
Имамо главни на врху.
Ми смо принтф доле у ​​средини.
Такође имамо Хелло Ворлд обрнута коса црта н у наводницима доле.
>> И све остало овде је инструкције врло низак ниво
да процесор рачунара разуме.
Инструкције које се крећу ЦПУ меморије око, то оптерећење жице из меморије,
и на крају, штампање ствари на екрану.
Шта сад дешава иако је после овај скуп код се генерише?
На крају, ти, заиста, и даље генерише објекат код.
Али кораци који имају заиста се дешава испод хаубе
изгледају мало више овако.
Изворни код постаје скупштина код, који тада постаје објекат код,
и Оперативне речи су овде да када саставити свој изворни код,
изађе склапање шифру, а затим Када саставите свој код монтаже,
изађе објекат код.
>> Сада кланг је супер софистициран, као и много компајлера,
и то не свих ових корака заједно, а не нужно
излаз неки посредник датотеке које можете чак и видети.
Само саставља ствари, што је општи назив који
описује цео овај процес.
Али ако заиста желите да будемо врло конкретан, ено
много више дешава тамо.
>> Али, хајде да размотримо сада и да чак то супер једноставан програм, хелло.ц,
назива функција.
То се зове принтф.
Али ја нисам писао принтф, заиста, који долази са ц, да тако кажем.
То је функција Подсетимо се да је декларисана у стандардном ио.х, који
је заглавље фајл који је тема ми заправо ћемо
зарони у дубину више пре времена.
Али заглавље фајл је обично прати
од датотеци код, Соурце Цоде датотеке, тако слично постоји стандард ио.х.
>> Негде пре, неко, или нечији, такође написао
фајл који се зове стандардни ио.ц, у који су стварни дефиниције,
или имплементације принтф, и гомиле других функција,
заправо написао.
Дакле, с обзиром да, ако узмемо у обзир да овде на лево, хелло.ц, када
састављен, нам даје хелло.с, чак и ако Цланг не смета штедњу у месту
можемо видети, и то код монтажа бива монтира у хелло.о који
је, заиста, подразумевано име с обзиром кад год саставити извор
код у објекту код, али нису потпуно спреман да га изврши још,
јер још један корак мора да се деси, и има
дешавало у последњих неколико недеља, можда без знања вас.
>> Конкретно негде у ЦС50 ИДЕ, и то,
такође, ће бити помало упрошћавање за тренутак,
постоји, или је упон а тиме, фајл који се зове стандардни ио.ц,
да неко саставио у стандардне ио.с или еквивалент,
то онда неко монтира у стандардном ио.о,
или се испостави у један мало другачији фајл
формат који може имати другачији филе укупно продужетак,
али у теорији и концептуално, тачно ти кораци морало да се деси у некој форми.
Што ће рећи, да је сада када пишем програм,
хелло.ц, да само каже, здраво свет, и ја користим код туђем
као принтф, која је Онце Упон А време, у фајлу названом стандардни ио.ц,
онда некако морам да узмем објекат код, моји нуле и јединице,
и објекат те особе код, или нуле и јединице,
и некако их повезују у једна коначна фајл, под називом здраво, да
има све нуле и Они из моје основне функције,
и свако од нула и оне за принтф.
>> И заиста, тај последњи процес назива, повезујући свој код објекта.
Од чега Излаз је извршна датотека.
Дакле, у правичност, на Енд оф тхе даи, ништа
се променило од недеље један, када смо Први је почео изради програма.
Заиста, све ово је било дешава испод хаубе,
али сада смо у позицији где можемо да
задиркивати осим ове различите кораке.
И заиста, на крају дана, и даље смо
остало нула и јединица, које је заправо велики Сегуе сада
на другу способности Ц, која нисмо имали да највероватније искористити
до данас, познат као битовима оператера.
Другим речима, до сада, било кад имамо бавио података у Ц или променљивих у Ц,
имали смо такве ствари знакова и плута и компоненте
и чезне и дубл и слично, али сви они су најмање осам битова.
Никада нисмо увек били у стању да манипулисати појединачне делове,
иако појединачног бита, ми знам, могу представљати 0 и 1.
Сада испада да је у Ц, ви могу добити приступ појединим бита,
ако знате синтаксу, са којом да се на њих.
>> Дакле, хајде да погледамо у битовима оператера.
Дакле, на слици ево неколико симболи који смо, некако, на неки начин, раније.
Видим амперсанд, вертикално бар и неки други, као,
и сећам се тог амперсанд амперсанд је нешто што смо раније видели.
Логично и оператер, где имате њих двојица заједно, или логично ИЛИ
Оператер, где сте имају два вертикалне пруге.
Битовима оператери, који ћемо види раде на битовима појединачно,
само користити једну амперсанд, А једна вертикална бар, Царет симбол
следи, мали Тилде, а затим напустио
носач лево брацкет, или Право носач десно конзола.
Сваки од њих има различита значења.
>> У ствари, хајде да погледамо.
Идемо стара школа данас, и употреба екран осетљив на додир од прошлих,
познат као белу одбор.
А ово бело плоча ће нам дозволити
да изразим неке прилично једноставне симболе, односно неке прилично једноставне формуле,
да онда можемо на крају моћ, како би
индивидуални приступ бита у оквиру Ц програма.
Другим речима, урадимо то.
Хајде да прво попричамо на Тренутак за амперсанд,
која је битовима и оператер.
Другим речима, ово је оператор који омогућава
да има леви променљиву обично, а десна променљива,
или појединачна вредност, да ако И их заједно, ми даје коначан резултат.
Па шта мислим?
Ако у програму, имате променљиву која садржи једну од тих вредности,
или нека буде једноставно и само написати нула и јединица појединачно,
ево како оператор Амперсанд ради.
0 Амперсанд 0 ће једнака 0.
А зашто је то тако?
>> То је врло слично Боолеан изрази,
да смо разговарали до сада.
Ако мислите на крају крајева, 0 је лажна, 0 је лажно, лажно и лажно
је, као што смо разговарали логички, такође лажна.
Тако смо добили 0 и овде.
Ако узмете 0 амперсанд 1, и то, такође,
ће бити 0, јер је за ово леви израз да би било истинито или 1,
то би требало да буде истина и истина.
Али овде имамо лажна и истина, или 0 и 1.
Сада опет, ако имамо 1 амперсанд 0, да, такође, ће бити 0,
и ако имамо 1 амперсанд 1, коначно да имамо 1 бит.
Другим речима, не радимо нешто интересантно са овим оператером
још увек, ово Амперсанд оператер.
То је битовима и оператер.
Али ово су састојци преко којих можемо да урадимо
интересантне ствари, као што ћемо ускоро видети.
>> Сада погледајмо само један Вертикални бар овде на десној страни.
Ако имам 0 мало и Или га са, битовима
Оператор ОР, још мало 0, да ће ми дати 0.
Ако узмем мало и 0 или је са А 1 мало, онда ћу добити 1.
И, у ствари, само јасноћа, пусти ме да се вратим,
тако да ми вертикалне пруге се не варам за 1-а.
Дозволите ми преписати све мој 1 је мало више
јасно, тако да смо следећи пут видели, ако су 1 или 0, то ће бити 1,
и ако имам 1 или 1 да, такође, ће бити 1.
Дакле, можете видети да је логично ИЛИ оператер понаша сасвим другачије.
То ми даје 0 0 ИЛИ ми даје 0, али свака друга комбинација ми даје 1.
Докле год имам једну 1 у формула, резултат ће бити 1.
>> Насупрот АНД оператер, амперсендом,
само ако имам два 1 је у једначина, ја заиста повео са 1 аут.
Сада постоји неколико других оператери као добро.
Један од њих је мало више укључени.
Па нека ми само напред и брисање то ослободили простор.
И хајде да погледају Царет симбол, само на тренутак.
Ово је типично карактер можете уписати
на тастатура холдинг Схифт и онда један од бројева вершине иоур САД
тастатура.
>> Дакле, ово је ексклузивни Оператор ОР, ексклузивно ИЛИ.
Тако смо видели или оператера.
Ово је ексклузивни оператор ОР.
Шта је заправо разлика?
Па хајде да погледамо формулу, и користити као састојци крају.
0 ЛОЛ 0.
Ја ћу рећи је увек 0.
То је дефиниција КСОР.
0 ЛОЛ 1 ће бити 1.
1 ЛОЛ 0 ће бити 1, и 1 ЛОЛ 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,
и јасно је да много много, много већи на овај начин,
али ћемо заправо видети паметнији приступи за то
уместо тога, такође,
>> У реду.
То је то за недељу дана три.
Ми ћемо вас следећи пут.
Ово је ЦС50.
>> [Мусиц плаиинг]
>> СПЕАКЕР 1: Био је у ужину бар једе Хот Фудге сладолед.
Све је имао преко његовог лица.
Он је носио ту чоколаду као брадом
Звучник 2: Шта радиш?
Спеакер 3: Хммм?
Шта?
>> Звучник 2: Да ли сте само Доубле Дип?
Ви дупло оборена чип.
Спеакер 3: Извините.
Звучник 2: пала си чип, ви узео залогај, а ти опет оборена.
Спеакер 3:
Звучник 2: Па то је као стављање Ваш цела десна уста у умак.
Следећи пут када се чип, Само је уроните једном, и завршити га.
>> Спеакер 3: Знаш шта, Дан?
Ви дип начин на који желите да дип.
Ја ћу дип начин на који желим да дип.