[Гуляе музыка] 

ПРАФЕСАР: Усё правільна. Гэта CS50, і гэта канец тыдня тры. Так што мы тут сёння, а не ў Сандэрс Тэатр, замест гэтага ў Weidner бібліятэкі. Усярэдзіне якога з'яўляецца студыя вядомы як Hauser Studio, або, скажам, студыя H, ці павінны мы say-- калі вам спадабалася, што жарт, гэта на самай справе ад аднакласнік, Марк, онлайн, які прапанаваў столькі з дапамогай Twitter. Цяпер тое, што гэта крута пра быўшы тут у студыі з'яўляецца тое, што я акружаны гэтыя зялёныя сцены, зялёны экран ці каляровасці, так бы мовіць, што азначае, што CS50-х Вытворчасць каманда, без майго ведама Прама зараз, можа быць пакласці мяне больш нідзе ў свеце, да лепшага ці да горшага. 

Цяпер тое, што ляжыць наперадзе, усталяваць праблема двух ў вашых руках на працягу гэтага тыдня, але з праблемай ўсталяваць тры на наступным тыдні, Вы будзеце выклік з так званы гульня 15, стары вечары, што Вы маглі б узгадаць прыёму як дзіця, які мае цэлы букет лікаў, якія могуць слізгаць уверх, уніз, злева і справа, і ёсць адзін прабел у галаваломкі, у якую вы можа на самай справе гэтыя слайд кавалачкі галаваломкі. У канчатковым выніку вы атрымаеце гэты ліст галаваломка, у нейкі падлозе выпадковым парадку, і мэта заключаецца ў сартаваць яго, зверху данізу, злева направа, ад аднаго ўвесь шлях праз 15. 

На жаль, рэалізацыя вы будзеце мець пад рукой будзе забеспячэнне на аснове, ня фізічна. Вы на самой справе прыйдзецца напісаць Код, з якой студэнт або карыстальнік можа, гуляць у гульню 15. І на самай справе, у хакера выданне гульні 15, Вы будзеце выклік для рэалізацыі, не толькі гульня ў гэтай старой школы гульня, але, хутчэй, рашэнне гэта, рэалізацыі рэжыму бога, так бы мовіць, што на самой справе вырашае галаваломкі для чалавека, шляхам прадастаўлення ім намёк, пасля намёку, пасля намёку. Так больш на гэтым на наступным тыдні. Але гэта тое, што ляжыць наперадзе. 

Зараз успамінаю, што раней на гэтым тыдні у нас была гэтая Скалалаз, калі хочаце, у выніку чаго лепш мы рабілі сартавання мудры быў верхняя мяжа Big O п у квадраце. Іншымі словамі, пузырьковый сартавання, Выбар роду, сартаванне ўстаўкамі, ўсе з іх, у той час як іншая у іх рэалізацыі, перададзеныя ў п квадраце працуе час у самым горшым выпадку. І мы, як правіла выказаць здагадку, што вельмі горшым выпадку для сартавання гэта тое, што ваша ўваходы цалкам у зваротным кірунку. І на самай справе, ён узяў даволі шмат крокаў для ажыццяўлення кожнага з гэтых алгарытмаў. 

Цяпер у самым канцы класа Нагадаем, мы параўналі пузырьковый сартавання супраць выбару роду ў дачыненні да аднаго іншы што мы назвалі сартавання зліццём у той час, і я прапаную, каб ён прымае Перавага ўрока ад тыдня нуля, падзяляй і ўладар. І неяк дасягнення нейкай лагарыфмічная час працы, у канчатковым рахунку, замест чагосьці гэта чыста квадратычнай. І гэта не зусім лагарыфмічная, гэта крыху больш, чым гэта. Але калі вы памятаеце з класа, гэта было значна, значна хутчэй. Давайце зірнем на тое, дзе мы спыніліся. 

Бурбалка роду супраць выбару Сартаваць па параўнанні з сартавання зліццём. Цяпер яны ўсё працуе, у Тэорыя, у той жа час. Працэсар працуе з такой жа хуткасцю. Але вы можаце адчуваць сябе як сумна гэта вельмі хутка стане, і толькі, як хутка, калі мы ўводзім трохі алгарытмаў за тыдзень Зеро, мы можам паскорыць. 

Так знак роду выглядае ўзрушаюча. Як мы можам выкарыстоўваць яго для таго, сартаваць лік хутчэй. Ну давайце ўспомнім да інгрэдыента, што быў вярнуцца да нулявой тыдні, што з шукаючы кагосьці ў тэлефоннай кнізе, і ўспомніць, што псевдокод, што мы прапанавалі, з дапамогай якіх мы можам знайсці хто, як Майк Сміт, выглядаў трохі нешта накшталт гэтага. 

Цяпер зірніце у прыватнасці у радку 7 і 8, і 10 і 11, якія індукуюць што цыкл, у якім мы захавалі вяртаючыся да радка 3 зноў, і зноў, і зноў. Але аказваецца, што мы можам глядзець гэты алгарытм, тут, у псевдокоде, трохі больш цэласна. На самай справе, што я шукаю на тут на экране, алгарытм для пошуку Майк Сміт сярод некаторага мноства старонак. І на самай справе, мы маглі б спрасціць гэта Алгарытм ў гэтых радках 7 і 8, і 10, і 11, каб проста сказаць, што гэта, якія я прадставіў тут у жоўты колер. Іншымі словамі, калі Mike Сміт раней у кнізе, мы не павінны паказаць крок за крокам цяпер, як пайсці і знайсці яго. Мы не павінны пазначыць вярнуцца да радка 3, чаму б нам проста не замест, скажам, у больш агульным сэнсе, шукаць Майка ў левая палова кнігі. 

І наадварот, калі Майк на самай справе ў кнізе пазней, чаму б нам проста не працытаваць Unquote пошуку Майка ў правай палове кнігі. Іншымі словамі, чаму б нам проста не накшталт пласкадонку на сябе кажу, шукаць Майка ў гэтым падмноства кнігі, і пакінуць яго для нашых існуючых Алгарытм, каб паведаміць нам як шукаць Майка ў што левая палова кнігі. Іншымі словамі, наш Алгарытм працы няхай гэта будзе тэлефонная кніга гэтай таўшчыні, гэта Таўшчыня або любой таўшчыні наогул. Такім чынам, мы можам рэкурсіўна вызначыць гэты алгарытм. Іншымі словамі, на Экран тут, з'яўляецца алгарытм для пошуку Майк Сміт сярод старонак тэлефоннай кнігі. Такім чынам, у лініі 7 і 10, давайце проста сказаць, што менавіта. І я выкарыстоўваю гэты тэрмін імгненне таму, і, сапраўды, Рэкурсія гэта моднае слова зараз, і гэта гэты працэс рабіць нешта, нейкім цыклічны з дапамогай кода, у вас ужо ёсць, і заклікаючы яго зноў, і зноў, і зноў. Цяпер гэта будзе важна што мы неяк знізу з, і не рабіць, што бясконца доўга. У адваротным выпадку мы будзем ёсць сапраўды бясконцы цыкл. Але давайце паглядзім, калі мы можам пазычаць гэтую ідэю з рэкурсіі, рабіць нешта зноў і зноў, і зноў, каб вырашыць сартаванне праблема з дапамогай зліцця роду, тым больш эфектыўна. 

Так я даю вам аб'яднаць роду. Давайце зірнем. Дык вось псевдокод, з якія мы маглі б рэалізаваць сартаванне, з дапамогай гэтага алгарытму пад назвай сартаванне зліццём. І гэта даволі проста гэта. На ўваходзе п элементаў, Іншымі словамі, калі вы улічваючы п элементаў і колькасці і лісты ці нешта, то ўваход, калі вы далі п элементаў, калі п менш, чым 2, толькі вяртацца. Дакладна? Таму што, калі п менш, чым 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, што менавіта колькасць разоў што вы можаце падзяліць спіс даўжыні 8 разоў, і зноў, і зноў, пакуль вы пакінулі са спісамі толькі памер 1. Дакладна? 8 ідзе на 4, ідзе да 2, ідзе ў 1, і гэта адлюстроўвае менавіта гэта карціна ў нас было ўсяго толькі імгненне таму. Так трохі разважнасці праверыць, куды на самай справе ўдзельнічае лагарыфм. 

Так што цяпер, што яшчэ тут справа? п. Так заўважыць, што кожны раз я падзяліць спіс, хоць і ў адваротным парадку ў гісторыі тут, я ўсё яшчэ раблю п рэчы. Гэта зліццё крок патрабуецца, Я дакранаюся кожны з нумароў, для таго, каб слізгаць яго ў яго прыдатным месцам. Таму, нават калі вышыня гэтага Дыяграма памеру часопіса п п ці 3, У прыватнасці, іншымі словамі, Я зрабіў тры дывізіі тут. Колькі працы я зрабіў па гарызанталі па гэтай схеме кожны раз? 

Ну, я зрабіў п крокаў працаваць, таму што, калі я атрымаў чатыры элемента і чатыры элемента, і мне трэба, каб аб'яднаць іх разам. Мне трэба, каб прайсці праз гэтыя чатыры, і яны чатыры, у канчатковым рахунку, аб'яднаць іх таму ў васьмі элементаў. Калі, наадварот, я атрымаў восем пальцаў тут, што я не раблю, і восем fingers-- sorry-- калі я атрымаў чатыры пальца сюды, што я і раблю, чатыры пальца тут, што я раблю, тое, што тое ж самае, Прыклад, як і раней, калі я восем пальцаў, хоць у Усяго якія я магу, накшталт, зрабіць. Я магу дакладна зрабіць тут, то я, вядома аб'яднаць усе гэтыя спісы памер 1 разам. Але я, вядома, прыйдзецца шукаць кожны элемент роўна адзін раз. Такім чынам, вышыня гэтага працэсу часопіса N, шырыня гэтага працэсу, так бы мовіць, з'яўляецца н, так, што мы, здаецца, каб, у канчатковым рахунку, гэта хто бяжыць час памер п раз увайсці н. 

Іншымі словамі, мы падзялілі спіс, часопіс N раз, але кожны раз мы зрабілі гэта, мы былі закрануць кожнага з элементаў для таго, каб аб'яднаць іх Усе разам, што крок быў п, так што мы павінны п раз увайсці н, ці як вучоны скажа, асімптатычна, што будзе вялікая слова для апісання верхні звязаны на часе працы, мы бяжым у Big O лог н час, так бы мовіць. 

Зараз гэта важна, таму што ўспомніць, што тыя, хто бег часы былі з пузырьковый сартавання, адбору і сартаваць і сартаванне ўстаўкамі, і нават некаторыя іншыя, якія існуюць, п квадраце было, дзе мы былі ў. І вы можаце, выгляд, убачыць гэта тут. Калі п квадраце, відавочна, п раз п, але тут мы маем п раз увайсці н, і мы ўжо ведаем, ад тыдня нуля, што часопіс п, лагарыфмічная, лепш, чым нешта лінейнай. У рэшце рэшт, ўспомніць карціну з чырвоным і жоўтым і зялёныя лініі, якія мы намалявалі, тым зялёны лагарыфмічная лінія была значна ніжэй. І, такім чынам, значна лепш і хутчэй, чым прамой жоўты і чырвоных ліній, п раз увайсці н, сапраўды, лепш чым п разоў п, або н квадраце. 

Такім чынам, мы, здаецца, ёсць вызначылі зліццё алгарытм накшталт тых, што працуе ў значна мінімальны час, і, сапраўды, Вось чаму, у пачатку гэтага тыдня, калі мы ўбачылі, што конкурс паміж бурбалкі сартаваць, выбар сартавання і зліцця сартаваць, сартаванне зліццём сапраўды, сапраўды выйграў. І на самай справе, мы нават не чакаць для пузырьковый сартавання і адбору роду да канца. 

Зараз давайце яшчэ адзін праход Пры гэтым з некалькі больш фармальны перспектыве, толькі ў выпадак, гэты водгук лепш чым гэтага вышэйшага ўзроўню абмеркавання. Дык вось алгарытм зноў. Давайце спытаем сябе, тое, што час працы з'яўляецца гэта алгарытмы розныя крокі? Давайце падзелім яго на першае Корпус і другі выпадак. ПЧ і яшчэ ў тым выпадку, калі, Калі N менш, чым 2, толькі вяртацца. Па адчуваннях сталай часу. Гэта, свайго роду, як два этапы, Калі N менш, чым 2, а затым вярнуцца. Але, як мы сказалі, у панядзелак, пастаянная часу, або Big O 1, можа быць два, тры крокі крокі, нават 1000 крокаў. Важна тое, што гэта пастаяннае лік крокаў. Такім чынам, жоўты выдзелены псевдокод тут працуе ў, мы будзем называць яго, пастаянная часу. Так больш фармальна, і мы збіраемся, мэтай якіх гэта будзе ступень, у якой мы аформіць гэта права now-- Т п, час працы задачы які прымае п нешта ў якасці ўваходных, роўная Big O з аднаго, Калі N менш, чым 2. Так што гэта абумоўлена, што. Такім чынам, каб быць ясным, калі п менш 2, у нас ёсць вельмі кароткі спіс, то час працуе, Т п, дзе п 1 або 0, у гэтым вельмі канкрэтным выпадку, гэта проста будзе пастаянная часу. Гэта зойме адзін крок, два крокі, што заўгодна. Гэта фіксаваны лік крокаў. 

Такім чынам, сакавітая частка павінна быць у безумоўна іншы выпадак у псевдокоде. Справа ў іншым месцы. Сартаваць левая палова элементаў, адсартуйце права палова элементаў, зліцця адсартаваных палоўкі. Як доўга кожны з гэтых крокаў ўзяць? Ну, калі працуе Час сартаваць п элементаў , Давайце называць яго вельмі увогуле, Т п, затым сартавання левай палова элементаў гэта, накшталт, як і казалі: Т п дзеліцца на 2, і аналагічна сартаванні правую палову з элементаў, накшталт, як і казалі: Т п дзеліцца 2, а затым зліцця адсартаваных палоўкі. Ну, калі я атрымаў некаторыя Колькасць элементаў тут, як чатыры, і некаторы колькасць элементаў тут, як чатыры, і я павінен аб'яднаць кожнага з гэтых чатырох У, і кожны з іх чатыры ў, адзін за адным, так што у канчатковым рахунку, у мяне ёсць восем элементаў. Ён адчувае, як гэта Big O з п крокаў? Калі я атрымаў п пальцы і кожны з ім павінен быць аб'яднаны ў месцы, гэта як яшчэ п крокаў. 

Так сапраўды formulaically, мы можам выказаць гэта, хоць трохі палохала спачатку погляд, але гэта нешта што захоплівае менавіта гэтую логіку. Час працы, Т п, калі п больш або роўна 2. У гэтым выпадку, у выпадку ELSE, Т п дзеліцца на 2, плюс Т N дзеліцца на 2, плюс Big O п, некаторыя лінейны шэраг крокаў, магчыма роўна п, можа быць, у 2 разы п, але гэта прыкладна, парадак п. Так што, таксама, як мы можам выказаць гэта formulaically. Зараз вы не ведалі б, гэта, калі вы запісалі яго ў сваім розуме, або паглядзець яго ў таму падручніка, што можа мець трохі шпаргалку ў рэшце рэшт, але гэта, сапраўды, збіраецца даць нам Big O н часопіса п таму што рэцыдыў Вы бачыце тут, на экране, калі вы на самой справе гэта, з бясконцую колькасць прыкладаў, ці вы зрабілі гэта formulaically, вы б бачыць, што гэта, таму што гэтай формуле само па сабе з'яўляецца рэкурсіўнай, з т п над чым-то справа, і т п над злева, гэта можа фактычна быць выказана, у выніку, як вялікі ідуць н часопіса п. Калі не перакананы, што гэта добра цяпер, проста прыняць на веру, што гэта, на самай справе, што гэта рэцыдыў прыводзіць да, але гэта ўсяго толькі трохі больш Матэматычны падыход да пошуку на часе працы сартавання зліццём на падставе яго псевдокода ў спакоі. 

Зараз давайце трохі перадышку ад усяго гэтага, і прыняць зірнем на упэўнены былы сенатар, які можа выглядаць крыху знаёмыя, хто сеў з Эрыкам ад Google Шміт, некаторы час таму, для інтэрв'ю на сцэне, перад цэлым букетам людзей, у канчатковым рахунку, пра гаварыць тэма, гэта даволі ўжо знаёмыя. Давайце зірнем. 

Эрык Шміт: Цяпер сенатар, Вы тут Google, і я хацеў бы думаць аб Старшынства ў сумоўі. Зараз гэта цяжка атрымаць працу ў якасці прэзідэнта. Прэзідэнт Абама: Добра. Эрык Шміт: І ты збіраецца рабіць [неразборліва] ў цяперашні час. Гэта таксама цяжка атрымаць працу ў Google. Прэзідэнт Абама: Добра. 

Эрык Шміт: У нас ёсць пытанні, і мы просім нашых кандыдатаў пытанні, і гэта адна з Лары з'яўляецца Швімэр. 

Прэзідэнт Абама: Добра. 

Эрык Шміт: Што? Вы, хлопцы, думаеце, што я жартую? Гэта прама тут. Што з'яўляецца найбольш эфектыўным спосабам сартаваць мільён 32 бітныя цэлыя? 

Прэзідэнт Абама: Well-- Эрык Шміт: Часам, можа быць, мне шкада, maybe-- Прэзідэнт Абама: Не, няма, няма, няма, няма, я think-- Эрык Шміт: Гэта не it-- Прэзідэнт Абама: Я думаю, я думаю, што бурбалка Сартаваць б няправільны шлях. Эрык Шміт: Ну. Хто сказаў яму гэта? ДОБРА. Я не зрабіў інфарматыка on-- 

Прэзідэнт Абама: Мы ўжо атрымалі нашы шпіёны там. ПРАФЕСАР: Усё правільна. Давайце пакінем ззаду нас цяпер Тэарэтычная свет алгарытмаў у асімптатычнага аналізу іх, і вярнуцца да некаторых тэмах ад тыдня нулём і адзінкай, і пачала выдаліць некаторыя навучальныя колы, калі вы будзеце. Так што вы сапраўды разумееце, у канчатковым рахунку, ад пачатку да канца, што адбываецца пад капотам, калі вы пісаць, кампіляваць і выконваць праграмы. Нагадаем, у прыватнасці, што гэта было першая праграма З мы глядзелі на, кананічны, простая праграма роду, умоўна кажучы, дзе яна друкуе, Hello World. І ўспамінаю, што я сказаў, то працэс што зыходны код праходзіць праз з'яўляецца менавіта гэта. Вы бераце зыходны код, прайсці гэта праз кампілятар, як Clang, і прыбывае аб'ектны код, што можа выглядаць як гэта, нулёў і адзінак што працэсар кампутара, цэнтральнае Блок апрацоўкі або галаўнога мозгу, у канчатковым рахунку, разумее. 

Аказваецца, што гэта трохі спрашчэннем, што мы зараз у становішча, каб дражніць адзін ад аднаго каб зразумець, што сапраўды быў адбываецца пад капотам кожны раз, калі вы запусціце Ляск, ці ў больш агульным, кожны раз, калі вы робіце праграму, з дапамогай Марка і CF 50 IDE. У прыватнасці, такія рэчы, як Гэта першы генеруецца, калі вы ўпершыню скампіляваць праграму. Іншымі словамі, калі вы прыняць ваш зыходны код і скампіляваць яго, тое, што першы час выводны Clang што-то вядомы як асэмблеры. І на самай справе, гэта выглядае менавіта так. 

Я пабег каманды на каманднага радка раней. Ляск Dash вялікай літары hello.c, і гэта стварыла файл для мяне, званых hello.s, усярэдзіне якога былі дакладна гэта змест, і трохі больш вышэй, і трохі больш ніжэй, але я паставіў сакавітыя Інфармацыя тут на экране. І калі вы ўважліва паглядзіце, вы ўбачыце, па меншай меры, некалькі знаёмых ключавыя словы. У нас ёсць галоўны ў верхняй. Мы PRINTF пасярэдзіне. І мы таксама маем прывітанне свет Зваротная касая рыса н у двукоссі ўніз ніжэй. 

А ўсё астатняе тут з'яўляецца Інструкцыя па вельмі нізкага ўзроўню што працэсар кампутара разумее. Інструкцыі ЦП, якія рухаюцца памяць вакол, што струны груз з памяці, і ў канчатковым рахунку, друку рэчы на ​​экране. Цяпер тое, што адбываецца, хоць пасля гэтая зборка генеруецца код? У канчатковым рахунку, вы, на самой справе, яшчэ генераваць аб'ектны код. Але крокі, якія сапраўды ужо на пад капотам выглядаць трохі больш, як гэта. Зыходны код становіцца асэмблера, які затым становіцца аб'ектам код, і аператыўныя словы тут, што, пры кампіляцыі зыходнага кода, прыбывае зьмяняй код, а затым пры зборцы кода зборкі, прыбывае аб'ектны код. 

Цяпер Clang супер складаныя, як шмат кампілятараў, і ён робіць усе гэтыя крокі разам, і гэта не абавязкова Выхад любы прамежкавы файлы, якія вы можаце нават убачыць. Гэта проста кампілюе рэчы, які з'яўляецца агульным тэрмінам, які апісвае ўвесь гэты працэс. Але калі вы сапраўды хочаце каб быць прыватнасці, ёсць нашмат больш там адбываецца, а таксама. 

Але давайце таксама разгледзець цяпер, нават што супер простая праграма, hello.c, называецца функцыяй. Ён заклікаў Printf. Але я не напісаць Printf, сапраўды, які пастаўляецца з з, так бы мовіць. Гэта функцыя нагадаем, што гэта заявіў у стандартным io.h, які файл загалоўка, які гэта тэма, якую мы будзем на самай справе пагрузіцца ў глыбіні, перш чым больш доўгія. Але файл загалоўка як правіла, суправаджаецца файлам кода, файл зыходнага кода, так гэтак жа, як існуе стандартная io.h. 

Некаторы час таму, хто-то, ці каму-небудзь, таксама напісаў файл называецца стандартным io.c, у якія фактычныя вызначэння, або рэалізацыі Printf, і гронкі іншых функцый, на самай справе напісана. Таму, улічваючы, што, калі мы лічым, маючы тут, на левым, hello.c, што, калі складзены, дае нам hello.s, нават калі Clang не турбуе захаванне ў месцы мы можам убачыць яго, і што зборка код атрымлівае сабраны ў hello.o, які гэта, сапраўды, імя па змаўчанні улічваючы пры кампіляцыі крыніца код у аб'ектны код, але не цалкам гатовыя выканаць яго яшчэ, таму што яшчэ адзін крок павінна адбыцца, і мае што адбывалася на працягу апошніх некалькіх тыдня, магчыма, без ведама да вас. 

У прыватнасці дзесьці у CS50 IDE, а гэта, таксама будзе чымсьці накшталт спрашчэнне на імгненне, ёсць, ці быў на той час, файл называецца стандартным io.c, што хтосьці сабраны ў Стандартныя io.s або эквівалент, што хто-то затым сабраны у стандартнай io.o, або аказваецца ў крыху іншы файл Фармат, які можа мець розныя пашырэнне файла ў цэлым, але ў тэорыі і канцэптуальна, дакладна гэтыя крокі былі адбыцца ў нейкай форме. Што і казаць, што ў цяперашні час калі я пішу праграму, hello.c, што проста кажа, прывітанне свет, і я з дапамогай кода чужой як Printf, які быў давным- Час, у файле пад назвай стандарт io.c, потым як-то я павінен прыняць мае аб'ектнага кода, мае нулі і адзінкі, і аб'ект гэтага чалавека код, або нулі і адзінкі, і неяк звязаць іх разам у адзін апошні файл, называецца прывітанне, што мае ўсе нулі і тыя з маёй галоўнай функцыі, і ўсё нулі і тыя, для Printf. 

І на самай справе, што ў мінулым працэс называецца, звязваючы свой аб'ектны код. Выхад якога уяўляе сабой выкананы файл. Такім чынам, у справядлівасці, на Канец дня, нічога не змянілася з аднаго тыдня, калі мы ўпершыню пачаў кампіляцыі праграмы. Сапраўды, усё гэта ўжо было адбываецца пад капотам, але зараз мы ў стане дзе мы можам на самай справе дражніць адзін ад аднаго гэтыя розныя крокі. І на самай справе, у канцы у дзень, мы па-ранейшаму засталося нулёў і адзінак, якія на самай справе вялікая пераходзіць у цяперашні час іншаму магчымасцю C, што у нас не было, каб выкарыстоўваць, хутчэй за ўсё, на сённяшні дзень, вядомы як пабітавае аператары. Іншымі словамі, да гэтага часу, мы ў любы час справу з дадзенымі ў C або зменных ў C, у нас было нешта накшталт сімвалы і паплаўкі і модулі і прагне і двухмесных і да т.п., але усе тыя, па меншай меры восем біт. Мы ніколі яшчэ не быў у стане маніпуляваць асобных бітаў, нават калі асобны біт, мы Ведаеце, можа прадстаўляць 0 і 1. Цяпер высвятляецца, што ў C, вы можа атрымаць доступ да асобных бітам, калі вы ведаеце сінтаксіс, з якой, каб дабрацца да іх. 

Такім чынам, давайце зірнем у аператараў пабітавае. Так на фота, вось некалькі знакаў, якія мы, як тыя, накшталт, бачыў. Я бачу Ампэрсанд, вертыкальны бар, і некаторыя іншыя, а таксама, і ўспомніць, што Ампэрсанд Ампэрсанд гэта тое, што мы бачылі раней. Лагічны аператар І, дзе ў вас ёсць два з іх разам, або лагічнае АБО Аператар, дзе вы Дзве вертыкальныя палоскі. Бітаў аператары, якія мы будзем см працаваць на біт паасобку, проста выкарыстоўваць адзін Ампэрсанд, А адзін вертыкальны бар, карэтка сімвал прыходзіць наступны, маленькі Тыльда, а затым пакінуў Кранштэйны левай дужкі, або правая дужка правая дужка. Кожны з іх мае розныя значэнні. 

На самай справе, давайце зірнем. Давайце старой школы сёння, і выкарыстанне сэнсарны экран з мінулага, вядомы як белая дошка. І гэта белая дошка збіраецца, каб дазволіць нам каб выказаць некаторыя даволі простыя сімвалы, ці, хутчэй, некаторыя даволі простыя формулы, што мы можам у канчатковым рахунку, то рычагі, для таго, Для доступу да асобных Біты ў межах праграмы C. Іншымі словамі, давайце зробім гэта. Давайце спачатку пагаворым момант аб Ампэрсанд, які з'яўляецца пабітавае І аператара. Іншымі словамі, гэта аператар, які дазваляе мне ёсць пераменная левая як правіла, і пераменная правая, або індывідуальнае значэнне, што, калі мы і іх разам, дае мне канчатковы вынік. Так што я маю на ўвазе? Калі ў праграме, у вас ёсць пераменная што крамы адной з гэтых значэнняў, або давайце трымаць яго простая, і проста выпісаць нулі і адзінкі паасобку, Вось як працуе аператар Ампэрсанд. 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. 

У адрозненне ад AND Аператар, Ампэрсанд, толькі калі ў мяне ёсць два 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: Вы ведаеце, што, Дэн? Вы апусціце шлях, які вы хочаце акунуцца. Я апусціце так, што я хачу, каб акунуцца.