[За възпроизвеждане на музика] 

ПРОФЕСОР: Добре. Това е CS50 и това е края на три седмици. Така че ние сме тук днес, не, в Sanders Theater, вместо в Weidner Library. Inside от които е студио известен като Hauser Studio, или да кажем Studio H, или ще ние say-- ако ви хареса, че е шега, това е действително от съученик, Mark, онлайн, който предложи най-много чрез Twitter. Сега това, което е готино за да съм тук в студио е, че аз съм заобиколен от тях зелено стени, зелен екран или chromakey, така да се каже, което означава, че е CS50 производствен екип, без знанието на мен точно сега, може да бъде извеждането Най-много ме навсякъде по света, за добро или за лошо. 

Сега това, което предстои, определен проблем две е във вашите ръце за тази седмица, но с проблем зададете три идната седмица ще се справи с т.нар игра на 15, стар полза страна, че можете да си спомните, получаващи като дете, че има цял куп от числа, които могат да се плъзгат нагоре, надолу, ляво и дясно, а има и една празнина в рамките на пъзел, в който можете всъщност може да се плъзга тези парчета от пъзел. В крайна сметка се появи това пъзел в някои полу произволен ред, и целта е да се го оправи, горе до долу, ляво на дясно, от една по целия път нагоре през 15. 

За съжаление, прилагането ще имате под ръка ще бъде софтуер базирани, не физически. Вие всъщност ще трябва да напиша код, с които студент или потребителят може да играете играта на 15. И в действителност, в хакер издание на играта на 15, ще бъде предизвикателство за изпълнение, не само свиренето на този стар училище игра, а по-скоро решаването от нея, за прилагане бог на готовност, така да се каже, че всъщност решава пъзела за човека, като им се осигурява с намек, след намек, след намек. Така повече за това следващата седмица. Но това е, което ни предстои. 

За сега си припомним, че по-рано тази седмица имахме тази Катерачът, ако щете, при което най-доброто, което правехме сортиране мъдър е горна граница на големия о на п квадрат. С други думи, метод на мехурчето, избор на сортиране, сортиране чрез вмъкване, всички от тях, докато различен при тяхното изпълнение, прехвърлени в една п квадрат течаща време в много лошия случай. И ние обикновено се предположи, че самото лошия случай за сортиране е този, който ви входове са напълно назад. И наистина, отне доста няколко стъпки за изпълнение на всяко от тези алгоритми. 

Сега в самия край на клас изземване, ние сравнение балон сортиране срещу селекция подредени една срещу друга че ние нарича сливат подреди по това време, и аз предлагам да го отнема Възползвайте се от поука от седмица нула, разделяй и владей. И някак постигане някакъв вид логаритмична времето за работа в крайна сметка, вместо нещо това е чисто квадратно. И това не е съвсем логаритмична, това е малко повече от това. Но ако си спомняте от класа, това е много, много по-бързо. Нека да разгледаме най-къде сме стигнали. 

Bubble подреди срещу селекция подреди срещу сливането на сортиране. Сега всички те са в ход, в теория, в същото време. Процесорът работи със същата скорост. Но вие можете да почувствате как скучно това е много бързо ще стане, и колко бързо, когато се инжектира малко от седмица нула на алгоритми, можем да ускори нещата. 

Така марка сортиране изглежда невероятно. Как можем да го използваме, за да да сортирате номера по-бързо. Ами нека помислим назад за съставка, която ние имаше още през нула седмица, че на търсите някого по време на телефонен указател, и припомни, че Псевдокод, че ние предложихме, чрез която можем да открием някой като Майк Смит, изглеждаше малко нещо като това. 

Сега да разгледаме по-специално по линия 7 и 8, и 10 и 11, които индуцират, че цикъл, при който ние продължавахме връщане назад към ред 3 отново, и отново, и отново. Но се оказва, че ние може да видите този алгоритъм, тук, в Псевдокод, малко по-холистично. В действителност, това, което търся най-тук на екрана, е един алгоритъм за търсене на Майк Смит сред някои набор от страници. И наистина, бихме могли да опрости това алгоритъм в тези линии 7 и 8, и 10 и 11 просто да кажа, че това, която съм представен тук в жълто. С други думи, ако Майк Смит е по-рано в книгата, ние не трябва да се уточни стъпка по стъпка сега как да отида да го намеря. Ние не трябва да се уточни да се върна в ред 3, защо да не направим ние просто вместо това, да речем, по-общо, търси за Mike в лявата половина на книгата. 

И обратното, ако е Mike всъщност по-късно в книгата, защо не просто цитирам цитата търсене за Mike в дясната половина на книгата. С други думи, защо да не направим ние просто сортиране на шута да си кажат: търси за Mike в тази подмножество на книгата, и го оставете да съществуващата ни алгоритъм, за да ни каже как да търсите Mike в че лявата половина на книгата. С други думи, нашата алгоритъм работи, дали е телефонен указател на тази дебелина, на този дебелина, или всякаква дебелина, каквато. Така че ние можем рекурсивно дефинира този алгоритъм. С други думи, на екран тук, е един алгоритъм за търсене на Mike Smith сред страниците на телефонен указател. Така че, в съответствие 7 и 10, нека само да кажа точно това. И аз използвам този термин момент Преди, а всъщност, рекурсия е модерна дума за сега, и това е този процес за правене на нещо циклично по някакъв начин използване на код, който вече имате, и тя се обадите отново, и отново и отново. Сега тя ще бъде важна че ние някак си дъно навън и не направи това безкрайно дълго. В противен случай ние ще има наистина един безкраен цикъл. Но нека да видим дали можем да заеме тази идея на рекурсия, правиш нещо отново и отново и отново, за решаване сортиране проблема чрез сливане сортиране, още по-ефективно. 

Така че аз ви дам сортиране чрез сливане. Нека да разгледаме. Така че тук е Псевдокод, с които бихме могли да приложат сортиране, използване на този алгоритъм, наречен сортиране чрез сливане. И това е съвсем просто това. На входа на наш елементи, с други думи, ако сте дадена п елементи и номера и писма или каквото и входът е, ако даден наш елементи, ако е п е по-малко от 2, просто се върнете. Нали така? Защото ако п е по-малко от 2, че означава, че моя списък от елементи е или размер на 0 или 1, и и в двете от тези тривиални случаи Списъкът е вече сортирани. Ако няма списък, това е сортирани. И ако има списък на дължина 1, това е очевидно сортирани. Така че алгоритъмът трябва да само наистина направи нещо интересно, ако имаме две или повече елементи, дадени ни. Така че нека да погледнем на магията тогава. Else сортирате лявата половина на елементите, След сортирате дясната половина на елементи, След това сливане на сортирани половини. И това, което е вид на ума огъване тук, е, че аз наистина не изглеждат да са Ви казали нищо, просто все още, нали? Всичко, което казах е, като се има списък на п елементи, сортират лявата половина, след това в дясната половина, а след това сливане на сортирани половини, но къде е действителната тайна сос? Къде е алгоритъм? Ами оказва се, че тези две линии Първият, подредени остави половината от елементи, и сортиране дясната половина на елементи, са рекурсивни повиквания, така да се каже. 

В края на краищата, в този точка във времето, трябва да съм, алгоритъм, с което сортирате цял куп елементи? Да. Това е точно тук. Това е точно тук, на екрана, и за да мога да използвам същия набор от стъпки да се справи със лявата половина, колкото мога дясната половина. И наистина, отново и отново. Така че един или друг начин, и ние скоро ще виж това, магията на сортиране чрез сливане е вградена в които много окончателното линия, сливане на сортирани половини. И това изглежда доста интуитивен. Взимаш две половини, и вие, по някакъв начин, да ги обедините заедно, и ще видим това конкретно в един миг. 

Но това е пълен алгоритъм. И нека да видим точно защо. Ами предполагам, че ние сме даде същите тези осем елементи тук на екрана, един чрез осем, но те са и в привидно случаен ред. И целта е под ръка да сортирате тези елементи. Е, как мога да отида за да го прави с помощта, отново, сортиране чрез сливане, както на този Псевдокод? И отново, пропит този в ума си, само за миг. Първият случай е доста тривиално, ако това е по-малко от 2, Просто се върне, няма какво да се направи. Така че наистина има само три стъпки, за да наистина да имате предвид. Отново и отново, аз съм ще искам да имам да се справи със лявата половина, сортирате дясната половина, и след това, след като тяхната две половини са сортирани, Искам да ги обедините заедно в един сортиран списък. Така че имайте това предвид. 

Така че тук е първоначалния списък. Нека да се отнесем към това като масив, като сме започнали да в две седмици, което е съседни блок от памет. В този случай, съдържаща осем номера, обратно към гръб до гръб. И нека сега се прилага сортиране чрез сливане. Така че аз първо искам да сортирате лявата половина на този списък, и нека, следователно, фокусира върху 4, 8, 6, и 2. 

Сега как мога да отида за сортиране на списък с размер 4? Ами аз трябва да се помисли за сега сортиране ляво на лявата половина. Отново, нека да се върнем назад само за миг. Ако Псевдокод е този, и аз съм дал осем елемента, 8 е очевидно по- от или равно на 2. Така че с първия случай не се прилага. Така че, за да сортирате осем елемента, за първи път сортирате лявата половина на елементи, тогава аз сортирате дясната половина, а след това се сливат двете половини, всяка сортирани размер на 4. ДОБРЕ. 

Но ако просто ми каза, сортирате лявата половина, който сега е с размер 4, как мога да сортирате лявата половина? Ами ако имам вход от четири елемента, За първи път се справи със отляво две, после десния двамата, и след това да ги обедините заедно. Така че отново, тя се превръща в битов на ума огъване игра тук, защото, вид, трябва да не забравяйте, къде се намирате в историята, но в края на деня, всеки даден брой елементи, първо искам да се справи със лявата половина, а след това в дясната половина, след това да ги обедините заедно. Нека да започнем да правим точно това. Ето входа на осем елемента. Сега ние не търсим най-лявата половина тук. Как мога да сортирате четири елемента? Ами аз първо сортирате лявата половина. Сега как мога да сортирате лявата половина? Ами аз съм бил дал два елемента. Така че нека да сортирате тези два елемента. 2 е по-голямо от или равно на 2, разбира се. Така че първият случай не се прилага. 

Така че аз сега трябва да се справи в ляво половината от тези два елемента. Лявата половина, разбира се, е само на 4. Така че как мога да сортирате списъка на един елемент? Е, сега, че специална базов модел до върха, така да се каже, се прилага. 1 е по-малко от 2, и ми списък наистина е с размер 1. Така че аз просто се върнете. Аз не правя нищо. И наистина, погледнете какво съм направено, 4 вече сортирани. Подобно Вече съм частичен успех тук. 

Сега, изглежда някак глупаво претенция, но е истина. 4 е даден списък с размер 1. Тя вече е сортиран. Това е в лявата половина. Сега аз сортирате дясната половина. Моят принос е един от елементите, 8 По същия начин, вече сортирани. Stupid, също, но отново, този основен принцип ще ни позволи в момента да се изгради на върха на този успешно. 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. Нищо не е в ред. Това се чувства като напредък. 

Сега тя се чувства като съм говорим вечно сега, И така, какво остава да се види дали това алгоритъм е, наистина, по-ефективно. Но ние, което става чрез тя супер методично. Компютър, разбира се, ще го направя по този начин. Е, къде сме ние? Започнахме с осем елемента. I подредени в лявата половина на 4. Аз като че ли да се направи с това. Така че сега следващата стъпка е да сортирате дясната половина на 4. И тази част можем да отидем чрез малко по- бързо, въпреки че сте Добре дошли в превъртане назад или пауза, просто мисля, че през него със свое собствено темпо, но това, което имаме сега е възможност да направя точно същия алгоритъм на четири различни номера. 

Така че нека да вървим напред, и да се съсредоточи върху дясната половина, които сме тук. Лявата половина на тази дясната половина, а сега лявата половина на ляво половината от които дясната половина, и как мога да сортирате списък на размера 1, съдържащ само номер 1? Това вече е направено. Как мога да направя същото за списък с размер на 1, съдържащ само на 7? Това вече е направено. Стъпка три за това половината после е да се слеят тези два елемента в нов списък с размер 2, 1 и 7. Не изглежда да са направили всичко че много интересна работа. Нека видим какво се случва след това. Аз просто подредени в лявата половина на дясната половина на оригиналната моя вход. Сега нека да сортирате правото половината, която съдържа 5 и 3. Нека отново погледнем в ляво половината, сортирани, дясната половина, сортирани, и да се обединят тези две заедно, в някои допълнително пространство, 3 е на първо място, а след това идва 5. И така, сега, ние сме сортирани по лявата половина на дясната половина на първоначалния проблем, и дясната половина на дясната половина на първоначалния проблем. Какво е третата и последна стъпка? Ами да се слеят тези две половини заедно. Така че позволете ми да се получи някаква допълнително пространство, но, отново, I може да се използва, че свободното пространство до върха. Но ние ще продължим да тя просто визуално. Позволете ми да се слеят в предприятието 1, и след 3, 5 и след това, след 7. По този начин оставяйки ме сега с дясната половина на първоначалния проблем това е перфектно подредени. 

И така, какво остава? Имам чувството, че аз продължавам да изречете същите неща отново и отново, но това е отражение на факт е, че ние сме с помощта на рекурсия. Процесът на използване на алгоритъм отново и отново, по-малки подгрупи първоначалния проблем. Така че аз сега са на левия сортирани половината от първоначалния проблем. Имам право сортиран полувреме на първоначалния проблем. Какво е третата и последна стъпка? О, това е сливане. Така че нека да го направя. Нека да отпусне допълнителна памет, но Боже мой, ние успя да я прати навсякъде сега. Имаме толкова много пространство на разположение за нас, но ние ще го прости. Вместо да ходят назад и излезе с първоначалното ни памет, нека просто го направи визуално тук по-долу, да завърши сливането на лявата половина и дясната половина. 

Така че като се обединят, какво трябва да направя? Искам да се възползвам елементите в ред. Така че търси в лявата половина, Виждам първото число е 2. Аз гледам на дясната половина, Виждам първото число е 1, така очевидно който номер искам да грабне, и постави на първо място в крайното списъка ми? Разбира се, един. Сега искам да попитам, че същия въпрос. От лявата половина, аз съм все още имам номер 2. От дясната половина, Имам 3 броя. Коя от тях искам да избера? Разбира се, номер 2 А Сега забележите кандидатите 4 отляво, 3 отдясно. Да, разбира се, да изберат 3. Сега кандидатите са 4 на отляво, 5 в дясно. Ние, разбира се, изберете 4. 6 в ляво, 5 в дясно. Ние, разбира се, изберете 5. 6 в ляво, 7 за правото. Ние избираме 6, а след това изберете 7, а след това ние избираме 8. Voila. 

Така че огромен брой думи по-късно, ние са подредени в този списък от осем елемента в списък с едно до осем, това е увеличаване с всяка стъпка, но колко време е направил тя ни отнеме да се направи това. Ами аз съм умишлено положени нещата изобразяват тук, така че можем вид виж или оценявам разделението в завладяване, който е бил случва. 

Всъщност, ако погледнем назад към началото, Аз бях оставил всички тези пунктирани линии въведат титулярите, можете, вид, вижте, в обратен ред, ако вид погледнем назад в История на предприятието, моя оригиналния списък е, разбира се, с размер 8. И след това по-рано, аз бях занимаващи се с два списъка с размер 4, и след четири списъци с размер 2, и след осем списъци с размер 1. 

Така че това, което прави това, вид, ви напомня за? Е, наистина, всеки от алгоритмите с които сме се погледна към този момент, когато ние разделяй и разделение, и разделение, запази като нещата отново и отново, в резултат на тази обща идея. И така, има нещо логаритмична става тук. И това не е съвсем дневник на п, но има логаритмична компонент на това, което току-що сте направили. 

Сега нека да разгледаме как това действително е така. Така влезте от п, отново бе голямо тичане време, когато сме направили нещо подобно двоично търсене, тъй като ние вече го наричат, стратегията разделяй и владей чрез които намерихме Майк Смит. Сега е технически. Това е дневник база 2 на п, дори въпреки че в повечето класове по математика, 10 обикновено е основата, която вие поемате. Но компютърни учени почти винаги мисли и говори от гледна точка на база 2, така че ние обикновено просто кажем лог N, вместо Вход основата 2 на N, но те са точно едно и същото в света на компютъра наука и като се отмени, има постоянен коефициент разлика между двете, така че това е спорен, така или иначе, за повече формални причини. 

Но за сега, това, което ни интересува за е този пример. Така че нека да не се докаже като например, но най- поне използват пример на номерата под ръка като проверка здрав разум, ако щете. Така че по-рано формулата беше дневник база 2 от п, но това, което е п в този случай. Имах п оригиналните номера, или 8 на оригиналния номер конкретно. Сега това е било малко по- време, но аз съм сигурен, уверите, че дневник база 2 на стойност 8 е 3, и наистина, това, което е хубаво за това е че 3 е точно колко пъти че можете да разделите списък на разстояние 8 отново и отново, и отново, докато не сте останали със списъци на само един размер. Нали така? 8 отива до 4, отива до 2, отива на 1, и това е отразяват точно това снимка имахме само преди миг. Така че малко здрав разум проверите къде логаритъм всъщност е замесен. 

Така че сега, какво друго се занимава тук? п. Така че забележите, че всеки път I разделя списъка, макар и в обратен ред в историята тук, аз все още се прави п неща. Това сливане стъпка изисква Докосвам всеки един от номерата, за да го плъзнете в целесъобразно неговото местоположение. Така, въпреки че височината на тази диаграми е с размер дневник п п или 3, По-специално, с други думи, Направих три дивизии тук. Колко работа съм направил хоризонтално по тази таблица всеки път? 

Е, аз го направих н стъпки от работи, защото, ако съм имам четири елемента и четири елемента, и аз трябва да ги обедините заедно. Аз трябва да мине през тези четири и тези четири, в крайна сметка да ги обедините обратно в осем елемента. Ако напротив имам осем пръста насам, което аз не правя, а осем fingers-- sorry-- Ако съм имам четири пръста тук, които да направя, четири пръста насам, което правя, тогава това е същото Например, както и преди, ако го направя разполагат с осем пръста макар в Общият брой, което мога да, вид, направете. Мога да направя точно тук, След това мога със сигурност обедините всички тези списъци с размер на 1 заедно. Но аз със сигурност трябва да погледнем на всеки елемент точно веднъж. Така че височината на този процес е дневник п, ширината на този процес, така да се каже, е п, така че това, което ние като че ли да има, в крайна сметка, е а времето за работа на размера н пъти влезте п. 

С други думи, ние разделена на списък, регистър на п времена, но всеки път, ние сме го направили, ние имахме да докосне всеки един от елементите, за да ги обедините всички заедно, които е п стъпка, така че ние имаме п пъти вляза п, или като компютърен специалист бих казал, асимптотично, което ще бъде голяма дума за описване на горния обвързани по време на работа, ние се изпълняват в голяма о на дневника п време, така да се каже. 

Сега това е значителен, защото припомни какво текущите времена бяха с балон сортиране и подбор сортиране и сортиране чрез вмъкване, а дори и няколко други, които съществуват, п квадрат беше там, където бяхме. И вие можете да, вид, виж това тук. Ако п квадрат е очевидно п пъти п, но тук имаме п пъти вляза п, и ние вече знаем от седмица нула, че дневник п, логаритмична, е по-добре, отколкото нещо линейна. В крайна сметка, припомни на снимката с червено и жълто и зелените линии, които ние теглеха г. зелена логаритмична линия е много по-ниска. И следователно, много по-добре и по-бързо отколкото правите жълти и червени линии, п пъти вляза п е, наистина, по-добре N пъти от N, N или квадрат. 

Така че ние като че ли имат идентифицирани алгоритъм се сливат сортиране, която работи в много по- бързо време, а всъщност, Ето защо, по-рано тази седмица, когато видяхме, че състезанието между балон сортиране, избор на сортиране, и се сливат сортиране, сортиране чрез сливане наистина, наистина спечели. И наистина, ние дори не изчакате за балон на сортиране и подбор на сортиране да свърша. 

Сега нека да бъде в една друга пас при това, от малко по- формална гледна точка, само в случай това резонира добре от това по-високо ниво на дискусия. Така че тук е алгоритъмът отново. Нека да се запитаме, това, което времето за изпълнение е от този алгоритми различни стъпки? Нека я разделят на първата случай и втория случай. В МФ и другаде по делото IF, АКО п е по-малко от 2, просто се върнете. Усеща се като константно време. Това е, вид, подобно на два етапа, АКО п е по-малко от 2, а след това се върнете. Но както казахме в понеделник, константно време, или О голям от 1, може да има две, три стъпки стъпки, дори 1000 стъпки. Важното е, че това е постоянна редица стъпки. Така че жълтото подчерта Псевдокод Оттук минава през, ние ще го наричаме, константно време. Така че по-официално, и отиваме to-- това ще бъде степента, в която ние формализира това право now-- T на п, времето за работа на проблем който взема н Нещо като вход, о е равно на един голям, Ако п е по-малко от 2. Така че това е условие за това. Така че да е ясно, ако п е по-малко от 2, ние имаме един много кратък списък, след това времето за работа, Т на N, където N е 1 или 0, в този много специфичен случай, това е просто щеше да бъде константно време. Това ще отнеме една стъпка, две стъпки, независимо. Това е фиксиран брой стъпки. 

Така че сочни част със сигурност трябва да бъде в другия случай в Псевдокод. Делото за друг. Sort лявата половина на елементи, нещо полето половината от елементи, се слеят сортирани половини. Колко време отнема всяка от тези стъпки предприема? Е, ако управлението време, за да сортирате наш елементи е, нека го наречем много общо, Т на N, След сортирането отляво половината от елементите е, вид, като да кажеш, Т на N разделена на две, по същия начин и за сортиране на дясната половина от елементи е, вид, като да кажеш, Т на N разделен 2, и след това сливане на сортирани половини. Ами, ако аз имам някаква брой елементи тук, като четири, а някои номер на елементи тук, като четири, и аз трябва да се слеят всяка от тези четири в, и всяка от тези четири, един след друга, така че в крайна сметка имам осем елемента. Той се чувства като това е голям о от п стъпки? Ако аз имам н пръстите и всеки от тях трябва да се слеят в място, това е все едно още п стъпки. 

Така че наистина formulaically, можем да изразим това, макар и малко плашещо в началото поглед, но това е нещо, който улавя точно тази логика. Времето на работа, T на п, ако п е по-голямо от или равно на 2. В този случай, делото ELSE, е T на п разделена на две, плюс Т N разделена на две, плюс голям от О N, някои линейна поредица от стъпки, може би точно н, може би 2 пъти п, но това е грубо, за да п. Така че това също е как можем изрази тази formulaically. Сега не би знаете това, освен ако сте го записва в ума си, или го гледам в обратно на учебник, че може да има малко по- мамят лист в края, но това е, наистина, ще ни даде голяма о п п дневник, защото повтарянето, че вие виждате тук на екрана, ако действително го е направил, че във безкраен брой примери, или си го направил formulaically, бихте се види, че това, защото тази формула себе си е рекурсивен, с т п над нещо отдясно, и Т на N ляво, това може да всъщност се изразява в крайна сметка, толкова голям, отидете на п дневник п. Ако не е убеден, че това е глоба за сега, просто поеме вяра, че това е, наистина, какво, че повторение води до, но това е само малко повече от един математически подход към търсите в момента работи на сортиране чрез сливане основава единствено на своята Псевдокод. 

Сега нека да отнеме малко по- обезвъздушаване от всичко това, и да погледнем по- някои бивш сенатор, който може да изглежда малко по-запознати, който седна с Eric на Google Schmidt, преди известно време, за интервю на сцената, пред цял куп на хора, в крайна сметка говорим за една тема, която е доста запознат с предприятието. Нека да разгледаме. 

Ерик Шмид: Сега сенатор, ти си тук в Google, и аз обичам да мисля за президентството като интервю за работа. Сега ми е трудно да си намеря работа като президент. Президентът Обама: Точно така. Ерик Шмид: И вие сте ще направя [недоловим] сега. То също е трудно да си намеря работа в Google. Президентът Обама: Точно така. 

Ерик Шмид: Ние имаме въпроси, и ние молим нашите кандидати въпроси, и това е една от Лари Швимер. 

Президентът Обама: OK. 

Ерик Шмид: Какво? Вие, момчета, мисля, че се шегувам? Това е точно тук. Какво е най-ефективният начин да се сортирате един милион 32-битови цели числа? 

Президентът Обама: Well-- Ерик Шмид: Понякога, може би аз съм съжалявам, maybe-- Президентът Обама: Не, не, не, не, не, аз think-- Ерик Шмид: Това не е it-- Президентът Обама: I мисля, мисля, че балонът подреди би било погрешен начин да отида. Ерик Шмид: Хайде. Кой го каза това? ДОБРЕ. Не съм компютърната наука on-- 

Президентът Обама: Имаме имам нашите шпиони там. ПРОФЕСОР: Добре. Нека да оставим зад гърба ни сега на теоретична свят на алгоритми в асимптотичната анализ от него, и се върнете към някои теми от седмица нула и единица, и старт за да се отстранят някои помощни колела, ако щете. Така че наистина разбират в крайна сметка от земята, какво е става под капака на двигателя, когато пише, компилира и изпълнява програми. Припомнете си, по-специално, че това е първата програма C разгледахме, каноничен, проста програма неразположен, относително казано, където той отпечатва, Hello World. И припомни, че казах, процесът че изходния код преминава през е точно това. Взимаш си изходния код, мине то чрез компилатор, като звън, и извън идва обектен код, който може да изглежда така, нули и единици че CPU на компютъра, централно процесор или мозъка, в крайна сметка разбира. 

Оказва се, че това е малко прекалено опростяване, че сега сме в състояние да дразни апарт да се разбере какво всъщност е става под капака всеки път, когато стартирате Трясък, или по-общо, всеки път, когато направи програма, използвайки Марка и CF 50 IDE. В частност, такива неща това е първата генерира, когато за първи път компилирате вашата програма. С други думи, когато вземете изходния код и да го компилирате, какво е първото се извежда от звън е нещо, известно като сглобяване код. И в действителност, тя изглежда точно като този. 

Тичах команда в командния ред рано. Звън пробив капитала hello.c, и това създаде файл за мен, наречени hello.s, вътре от които са точно тези съдържания, и малко по- горе и малко по-долу, но съм постави сочните информация тук на екрана. И ако се вгледате внимателно, ще видите, поне няколко познати ключови думи. Имаме основната отгоре. Ние ФОРМАТ надолу в средата. И ние също имаме здравей свят наклонена черта п в кавички, установени по-долу. 

И всичко останало тук е инструкции много ниско ниво на че CPU на компютъра разбира. Инструкции на процесора, които се движат с памет наоколо, че товарните струни от паметта, и в крайна сметка, за печат неща на екрана. Сега това, което се случва, макар и след тази асамблея код се генерира? В крайна сметка, и да правите, наистина, все още генерира обектен код. Но стъпките, които имат наистина продължава под капака изглежда малко по-така. Изходния код става сглобяване код, който след това се превръща в обектен код, и оперативните думи тук са, че, когато компилирате изходния код, извън идва код събрание, а след това когато се съберат си сглобяване код, извън идва обектен код. 

Сега звън е супер сложна, като много от компилатори, и го прави всички тези стъпки заедно, и то не е задължително изход всеки междинен файлове, които дори може да видите. Тя просто се компилира неща, който е общ термин, който описва целия този процес. Но ако наистина искате да бъде специално, има много повече става там, както добре. 

Но нека да помисли сега, че дори и че супер проста програма, hello.c, нарича функция. Той призова ФОРМАТ. Но аз не съм писал ФОРМАТ, наистина, която идва с с, така да се каже. Това е функция, която е изземване декларирани в стандартната io.h, които е заглавния файл, който е тема, ние всъщност ще потопите в по-голяма дълбочина не след дълго. Но заглавния файл е обикновено придружена от досие код, изходния код на файла, така че много като съществува стандарт io.h. 

Някъде преди, някой, или на някой, също пише файл, наречен стандартен io.c, в които действителните определения, или реализации на ФОРМАТ, и букети от други функции, действително са написани. Така че има предвид, че, ако вземем предвид, като тук, на ляво, hello.c, че когато компилиран, ни дава hello.s, дори ако Звън не притеснява пестене на място можем да го видите, и че сглобяване код получава сглобяване в hello.o, които е, наистина, на име по подразбиране дал, когато компилирате източник код в обектен код, но не са напълно готова да го изпълни, все още, защото още една стъпка трябва да се случи, и има се случва през последните няколко седмици, може би без знанието на вас. 

Конкретно някъде в CS50 IDE, и това, също ще бъде малко на опростяване за миг, съществува, или е бил едно време, файл, наречен стандартен io.c, че някой компилиран в стандартни io.s или еквивалента, че някой след това сглобени в стандартна io.o, или се оказва в малко по-различен файл формат, който може да има различна файлово разширение напълно, но на теория и концептуално, точно тези стъпки трябваше да се случат в някаква форма. Което ще рече, че сега когато пиша програма, hello.c, че просто казва, здравей свят, и аз съм с код на някой друг като ФОРМАТ, който някога е бил върху време, във файл, наречен стандартен io.c, След това по някакъв начин аз трябва да си взема обектен код, моите нули и единици, и обект на това лице код или нули и единици, и някак си ги свързват заедно в един последен файл, наречен здравей, че има всички нули и такива от моята основна функция, и всички нули и такива за ФОРМАТ. 

И наистина, че миналата процес е призовани, свързваща си обектен код. Чийто изход е изпълним файл. Така че в справедливостта, в края на деня, нищо се е променила след една седмица, когато ние за първи път започна съставянето програми. Всъщност, всичко това е случва под капака на двигателя, но сега сме в позиция, където можем действително дразни освен тези различни стъпки. И наистина, в края на деня, все още сме останах с нули и единици, които всъщност е страхотно Segue сега в друга възможност за C, че ние не сме имали да се наберат най-вероятно към днешна дата, известна като побитови оператори. С други думи, до този момент, по всяко време ние сме справиха с данни в C или променливи в C, сме имали такива неща овъгли и плавници и добавки и копнее и двойки и други подобни, но всички от тях са най-малко осем бита. Ние все още не съм бил в състояние да манипулира отделни битове, макар индивидуална малко, ние знам, може да представлява 0 и 1. Сега се оказва, че в C, можете може да получите достъп до отделни битове, ако знаете синтаксиса, с които да се измъкне по тях. 

Така че нека да погледнем при побитовите оператори. Така че на снимката тук са няколко символа, които сме, вид, нещо, виждал преди. Виждам амперсанд, вертикална бар, както и някои други, както и, и припомни, че амперсанд амперсанд е нещо, което не сте виждали преди. Логичното И оператора, където трябва два от тях заедно, или логическото ИЛИ оператор, където можете има две вертикални ленти. Се операция, която ще виж работят на бита индивидуално, просто използвайте единичен амперсанд, а единична вертикална лента, на карета символа идва след това, малкото, Тилда, и после наляво скоба остави скоби или полето скоба дясната скоба. Всяка от тях има различни значения. 

Всъщност, нека да разгледаме. Нека се върнем старата школа и днес, и използването едно докосване на екрана от недалечното минало, известен като бяла дъска. И тази бяла дъска ще ни позволи да изразя някои доста прости символи, или по-скоро някои доста прости формули, че можем след това в крайна сметка ливъридж, с цел за достъп до индивидуална битове в рамките на програма С. С други думи, нека да направим това. Нека първо поговорим за миг за амперсанд, което е побитово И оператора. С други думи, това е оператор, който позволява ми да има променлива лява обикновено, и променлива дясна, или индивидуална стойност, че ако ние И ги заедно, ми дава краен резултат. И така, какво искам да кажа? Ако в една програма, имате променлива че магазините една от тези стойности, или нека да го прости, и просто напишете нули и единици индивидуално, ето как работи операторът на амперсанд. 0 амперсанд 0 ще се равнява на 0. А защо е така? 

Това е много подобен на Булеви изрази, че ние обсъдихме този момент. Ако мислите, че в края на краищата, 0 е невярно, 0 е невярна, лъжлива и невярна е, както говорихме логично, също фалшива. Така получаваме 0, както и тук. Ако сте приели 0 амперсанд 1, и това също ще бъде 0, защото за това изразяване отляво за да е истина, или 1, тя ще трябва да бъде вярна и вярно. Но тук имаме невярна и вярно, или 0 и 1. Сега отново, ако имаме един амперсанд 0, това също ще бъде 0, и ако имаме един амперсанд 1, най-накрая да имаме едно малко. Така че, с други думи, ние не правим нещо интересно с този оператор просто все още, това амперсанд оператор. Това е битуайз И оператора. Но това са съставките чрез което можем да направим, интересни неща, тъй като ние скоро ще видим. 

Сега нека да погледнем само сингъл вертикална лента тук вдясно. Ако имам 0 битов и аз OR го с, битуайз OR оператор, друг 0 ​​битов, че ще ми даде 0. Ако аз взема 0 битова и OR го с 1 битово, тогава аз ще получите 1. И в действителност, само за яснота, нека да се върнем, така че вертикалните си барове не се бърка с 1 на. Позволете ми да пренапише всички ми 1 е малко по- ясно, така че да можем следващия видите, ако аз са с 1 или 0, че ще бъде един, и ако имам 1 или 1, които, също ще бъде 1. Така че можете да видите логично, че НОР Операторът се държи много по-различно. Това ми дава 0 или 0 ми дава 0, но всяка друга комбинация ми дава 1. Докато имам един милион в формула, резултатът ще бъде един. 

За разлика и оператор, амперсанд, само ако имам два 1 има в уравнение, мога да се получи в действителност един 1. Сега вече има няколко други оператори, както добре. Един от тях е малко по-голямо участие. Така че нека да вървим напред и да изтриете това да освободите място. И нека да разгледаме най- карета символ, само за миг. Това обикновено е характера можете да въведете на вашата клавиатура стопанство Shift и След това един от номерата на върха си US клавиатура. 

Така че това е изключителен OR оператор, изключителната OR. Така че ние просто видях оператора OR. Това е изключителна или оператора. Какво всъщност е разликата? Ами нека просто погледнете формулата, и използва това като съставки в крайна сметка. 0 0 XOR. Отивам да кажа, е винаги 0. Това е определението на XOR. 0 XOR 1 ще бъде 1. 1 XOR 0 ще бъде 1, и 1 XOR 1 ще бъде? Wrong? Или нали? Не знам. 0. Сега това, което се случва тук? Ами мисля за Името на този оператор. Exclusive OR, така че на име, вид, предполага, отговорът е само щеше да бъде 1, ако входовете са изключителни, изключително различна. Така че тук входовете са същото, така че на изхода е 0. Тук входовете са същото, така че на изхода е 0. Това са изходите са различни, те са изключителна, и така изходът е един. Така че това е много подобен на И това е много подобна, или по-скоро това е много подобен на OR, но само в един изключителен начин. Това вече не е на 1, защото имаме две 1 е, и не изключително, само един от тях. Всичко е наред. Какво да кажем за останалите? Ами тилда, междувременно, е всъщност хубаво и просто, за щастие. И това е една унарен оператор, което означава, това е приложена само към един вход, един операнд, така да се каже. Не на левия и десен. С други думи, ако сте приели тилда на 0, отговорът ще бъде обратното. И ако вземете тилда на 1 г. Отговорът ще има обратното. Така тилда операторът е начин на отричане малко, или обръщане малко от 0-1 или 1-0. 

И това ни оставя най-сетне само с две крайни оператори, така наречените олевяване, и т.нар полето оператор на смени. Нека да видим как те работят. Операторът на олевяване, написани с две ъглови скоби като тази, работи както следва. Ако моят принос, или ми операнд, наляво Операторът на смени е просто един милион. И аз тогава кажете на компютъра, за да олевяване, че един, казват седем места, резултатът е като че ли вземе, че 1, и да го преместите седем места назад към лявото, и по подразбиране, ние ще приемем, че на пространството дясно ще бъдат подплатени с нули. С други думи, 1 олевяване 7 върви да ми даде, че 1, последвано от 1, 2, 3, 4, 5, 6, 7 нули. Така че в известен смисъл, тя ви позволява да вземе малък брой като 1, и ясно да го направи много по- много, много по-голяма по този начин, но ние всъщност ще видим по-умни подходи за него вместо това, както и, 

Всичко е наред. Това е всичко за три седмици. Ние ще ви видим следващия път. Това беше CS50. 

[За възпроизвеждане на музика] 

SPEAKER 1: Той беше най-закуската бар яде гореща празни приказки мелба. Той имаше всичко по лицето му. Той носи, че шоколадът като брадата SPEAKER 2: Какво правиш? SPEAKER 3: Hmmm? Какво? 

SPEAKER 2: Знаете ли, просто двоен спад? Можете двойно потопени чипа. SPEAKER 3: Извинете ме. SPEAKER 2: Можете къси чипа, вие отхапа, а вие потопи отново. SPEAKER 3: SPEAKER 2: Така че това е като да сложиш целия си прав устата в натопи. Следващия път, когато се вземат с чип, Просто го натопи веднъж, и то свърши. 

SPEAKER 3: Знаеш ли какво, Дан? Можете натопи начинът, по който искате да натопи. Ще натопи начинът, по който искам да натопи.