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

Дэвід Дж малая: Гэта CS50. І гэта пачатак тыдні тры. Такім чынам, мы атрымалі шмат цікавай рэчы, каб пакрыць сёння. Шмат магчымасцяў для добраахвотнікаў на сцэне. І ў канчатковым рахунку, сёння не пра кодзе наогул. Але гэта пра ідэі, і гэта аб алгарытмах, а на самай справе вярнуць некаторыя з Урокі, вынятыя з нулявы тыдні, дзе нагадаем, мы прадставіў гэта пачвару. І запазычанні натхненне таго, каб пачаць вырашыць ўсё больш вытанчаных формах праблемы алгарытмічных. Але спачатку пару аб'яваў. Такім чынам, адна, калі вы хацелі б далучыцца да Супрацоўнікі і аднакласнікі CS50 за ланчам ў гэтую пятніцу, і тут, і ў Кембрыдж, і ў Нью-Хейвене, калі ласка, наведайце Курсу сайт, дзе URL можа быць знойдзены. Лекцыя ў сераду будзе ня быць тут, у Сандэрс. Гэта будзе толькі онлайн, так наладзіцца на сайце CS50 на, у Ці тут у Кембрыджы ці Нью-Хейвен, а таксама. 

І тады праблема ўсталяваць два ўжо ў вашых руках. Калі вы не ныралі ў яшчэ, дазвольце мне прапанаваць сфармуляванае прапанову моцна што асабліва цяпер, у праблема ўсталёўвае загадзя, Вы сапраўды хочаце, каб пачаць зараз, калі не плёскацца трохі на выходныя або да калі яны ўпершыню выйсці на Пятніцах, таму што вы будзеце знайсці, што яны не абавязкова атрымліваць больш ці больш складаным у SE. Я думаю, што вы знойдзеце, што ў Наогул, яны, як правіла, прымаць прыкладна вакол столькі ж часу. Але гэта, вядома, залежыць на студэнта, і ён залежыць ад менталітэту з якой вы набліжаецеся да яго. Але нязменна, вы збіраецеся запусціць супраць нейкай сцяны, і вы збіраецеся ударыць нейкая памылка, і вы проста не будзе ў стане атрымаць над ім у нейкі момант. І гэта вельмі каштоўна, каб мець магчымасць адысці, вярнуцца на наступны дзень, перайсці да офісных гадзін, пост на CS50 Абмеркаваць і да т.п., на самай справе атрымаць адмыкнутая. Так што майце гэта на ўвазе. Пачынаючы ранняе, наколькі гэта магчыма гэта лепшае, што вы можаце зрабіць. Дык вось, дзе мы пачалі клас, па нулявы тыдні. І мы можам атрымаць добраахвотніка тут, каб дапамагчы мне знайсці мікрафоны? ДОБРА. Стоячы ўжо. Давай до. Адгадайце, што гэта, як гэта будзе працаваць. Ваша імя? Алан ESTRADA: Алан Эстрада. Дэвід Дж малая: Алан Эстрада. Давай до. Вельмі прыемна. Алан ESTRADA: Прыемна пазнаёміцца. Дэвід Дж малая: І вы былі тут з намі ў нулявым тыдня, вядома. Алан ESTRADA: я быў. Я быў. 

Дэвід Дж малая: Дык можа вы ідзяце наперад і знайсці для нас Майк Сміт, так хутка, як вы можаце? Як хутка, як вы можаце. Літаральна раздзіраючы праблемы у палове, як вам трэба. 

Алан ESTRADA: Хм. Дэвід Дж малая: Літаральна раздзіраючы праблему ў два разы. 

Алан ESTRADA: Ой. Мм. Вельмі добра. 

Дэвід Дж малая: ОК. Добра. Дзякуй. Алан ESTRADA: Вельмі добра. ДОБРА. 

Дэвід Дж малая: І зараз, Вы звёў яго да паловы памеру праблемы. Зараз, мы да чвэрці. Вы звяртаючы ўвагі на з якога боку мы трымаем? 

[Смяецца] 

Алан ESTRADA: Так, я think-- 

Дэвід Дж малая: Які раздзел мы ў? Алан ESTRADA: Глушыцелі, так. 

Дэвід Дж малая: ОК. Але Майк Сміт збіраецца каб быць пасля Глушыцелі. So-- 

[Смяецца] 

Добра. Алан ESTRADA: Дзе мы шукаем? Дэвід Дж малая: Майк Сміт. Алан ESTRADA: Майк Сміт. Дэвід Дж малая: Цяпер мы ў хірургічнае. Цяпер лекары. Now-- 

Алан ESTRADA: Let's- давайце ісці з рэальнай. Нерухомасць. 

Дэвід Дж малая: Нерухомасць. ДОБРА. Калі вам трэба рэальнае. Цяпер, які шлях Майк Сміт? 

Алан ESTRADA: Такім чынам. 

Дэвід Дж малая: Якім чынам? Алан ESTRADA: Пачакайце. M is-- правільна? Мы пачалі with-- 

Дэвід Дж малая: Так. Яны пакінулі. Ваша права. 

Алан ESTRADA: Так. 

Дэвід Дж малая: Так Майк тут. Алан ESTRADA: Што? 

[Смяецца] 

Дрэнны прыклад, хлопцы. Выбачайце. Дэвід Дж малая: Гэта навучыць Вы выскачыць са свайго крэсла. 

Алан ESTRADA: Ой. Ох. Я вам. Я вам. Ох. Ох. Гэта is-- ОК, я вам. Сміт прама тут? 

Дэвід Дж малая: Сміт, дзякуй. Так што я буду трымаць гледзячы Сміт? 

Алан ESTRADA: О, так. Няма, няма, няма. О, няма. Гэта маё. 

Дэвід Дж малая: Аб, вы атрымалі Сміт. ДОБРА. 

Алан ESTRADA: Так, я атрымаў Сміт прама тут. Выбачайце, хлопцы. Я думаў, мы Michael-- шукалі Міхаіла. Выбачайце. 

Дэвід Дж малая: Гэта нармальна. Добра, зараз мы у Paccini і сыны. 

Алан ESTRADA: Paccini і сыны. Дэвід Дж малая: Толькі вы і я на гэтым. ДОБРА. Як нас знайсці Майк Сміт. Сміт. 

Алан ESTRADA: Сміт. 

Дэвід Дж малая: Сміт. Мы ў R для смецця. Алан ESTRADA: Смецце. Ох. Гэта зойме нейкі час. 

[Смяецца] Дэвід Дж малая: Абутак. Мы ў абутку. 

Алан ESTRADA: Цяпер мы gonna-- 

Дэвід Дж малая: Ніца. Алан ESTRADA: Which-- [Смяецца] О, гэта выдатна. [Смяецца] 

Дэвід Дж малая: Гэта нармальна. 

Алан ESTRADA: О, гэта добра. Я не думаю, што я збіраюся ёсць PSAT прыяцеляў пасля гэтага. Дэвід Дж малая: Добра. Спартыўныя. Алан ESTRADA: Спартыўныя. Хм, L, M, N, O, П. Дэвід Дж малая: ОК. Так што давайце разарваць гэты напалову. Добра. На гэтым сканчаецца дрэнна ў любым выпадку, таму што Майк Сміт не будзе ў жоўтых старонках. 

Алан ESTRADA: Ой. 

Дэвід Дж малая: Не, гэта нармальна. Але давайце прадставім, як ён на гэтай старонцы. Так што цяпер, вы звялі праблему ўніз на адну старонку, і мы знайшлі Майка Сміта. 

[Радаму] ОК, дзякуй. ДОБРА. Гэта было незвычайна. Але гэта было яшчэ хутчэй чым лінейны пошук, дзе мы пачынаем на пачатку кнігі, і мы рухаемся наш шлях злева направа, у канчатковым выніку, гледзячы на ​​Майка Сміта. І так, калі тэлефонная кніга быў, можа быць, 1000 старонак, можа быць, гэта заняло б нам 10 ці каля таго старонак слёзы. 

Але вы, магчыма, выкарыстоўвала закрануў здагадка ва ўсё гэта, што ёсць што ў тэлефоннай кнізе на загадзя было тое, што? АЎДЫТОРЫЯ: Сартаваць. Дэвід Дж малая: Гэта адсартаваныя. Дакладна? Гэта адсартаваныя па алфавіце, таму што ўсе гэтыя імёны і нумары сартуюцца ад А х да Z, і ў алфавітным парадку паміж імі. Але сёння, мы цяпер спытаць пытанне, ну, як зрабіў Verizon ці тэлефон Кампанія атрымаць яго ў такім стане? 

Таму што адна справа выкарыстоўваць Здагадка, што, і таму вырашыць праблему з Алгарытм больш эфектыўна. Але мы ніколі сапраўды спытаў нулявы тыдні, ну, Колькі каштуе Verizon або нехта яшчэ каб атрымаць, што тэлефонную кнігу ў адсартаваным парадку? 

Дакладна? Гэта не мае значэння, калі гледзячы Mike Smith супер хуткі, калі яна прымае вас на год сартаваць старонкі першапачаткова. Дакладна? Вы можаце таксама проста просеять праз рандомізірованное тэлефоннай кнізе, калі гэта будзе супер дорага для сартавання. Так што, калі мы можам мець іншы добраахвотнік. Давайце глядзець тут возьмем як мы might-- прыходзяць на up-- як мы маглі б ісці аб сартаванні іх. 

І калі на самай справе мог Іарданія далучыцца да нас тут, на сцэне. Давай на імгненне. Ваша імя? Караліна: Кэралайн. Дэвід Дж малая: Кэралайн, давай да. І вы будзеце далучыўся мной і Іарданіі тут. Кэралайн, дзякуй. Добра. Такім чынам, што мы маем тут для Кэралайн 26 сінія кнігі што ФАС выкарыстоўвае для кіравання некаторыя выпускныя іспыты. Яны становяцца цяжка знайсці, але тое, што мы зрабілі загадзя з'яўляецца тое, што мы ўклалі чыё-то імя на пярэдняй кожны з іх, але мы трымалі яго простым шляхам затым тушыць поўныя імёны. Такім чынам, мы б паставіць чалавека з імем L, D, J, B, цалкам ад А да Z, але яны ў выпадковым парадку. І так, калі б вы, кажу СВОЙ шлях праз праблемы, як вы зрабіць гэта, вы можаце ісці наперад і сартаваць іх для нас, ад А да Я. 

АЎДЫТОРЫЯ: ОК, так што я, як, сярэдні. З пачынае. Б. Дж, перш чым Л. У, В. 

Дэвід Дж малая: Трымайце, што думаў на працягу адной секунды. Таму што інакш, гэта толькі цікавымі для вас, мяне і Іарданіі. Там мы ідзем. АЎДЫТОРЫЯ: [неразборліва]. Р. Дэвід Дж малая: ОК. Што ты робіш? 

Караліна: М прыходзіць пасля О. 

Дэвід Дж малая: ОК. 

Караліна: О. Дэвід Дж малая: О, добра. 

Караліна: Е. 

Дэвід Дж малая: E, F. Так. 

Караліна: T, U, V. 

Дэвід Дж малая: V, T, U, V. Так-то яно Падобна на тое, вы making-- працягваць. Падобна на тое, вы робіце вялікая куча тут, і выгляд вялікі кучы там. Такім чынам, першая палова алфавіту, Другая палова алфавіту. ДОБРА. Добра. Выгляд падзелу праблемы на дзве часткі. M, N, Х. Так. Караліна: К. Дэвід Дж малая: ОК. К. Такім чынам, вы, здаецца, выбару іх адзін за адным, пакласці яго налева або направа, або Z збіраецца на падлозе. ДОБРА. 

Караліна: Z збіраецца на падлозе. 

Дэвід Дж малая: ОК. У збіраецца на падлозе. Цяпер мы можам паставіць X. 

Караліна: Г. Дэвід Дж малая: G адбываецца засталося. S ідзе правільна. Добра, А прайшоўшы ўвесь шлях налева. 

Караліна: A, B, C, D. 

Дэвід Дж малая: Цяпер, добра. У нас ёсць A, B, C. Вт збіраецца там. Добра, Т. 

Караліна: H, I, J. Дэвід Дж малая: H, I, J. Добра. Караліна: У цэнтры, я gonna-- Дэвід Дж малая: ОК. Так што цяпер, мы збіраемся выгляду зліцця гэтых розных паль. Такім чынам, праз С, тады я бачу D, і Е, F і і G і Н, І. Ніца. J, К. А потым, гэта куча з ног на галаву, але гэта нармальна. Вядома. Мы можам скараціць некаторыя куты. ДОБРА. І тады мы павінны W, X, Y, Z. 

Караліна: Так. 

Дэвід Дж малая: Выдатна. Такім чынам, вялікі дзякуй Кэралайн для сартавання іх. 

[Радаму] 

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

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

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

Замест 26, давайце зрабіць што-то значна менш з проста сказаць, сем, за гэтыя дзверы, так бы мовіць. Ёсць толькі сем лікаў? І калі мэта зараз у рука, каб знайсці значэнне, давайце паглядзім, наколькі эфектыўна мы можам ісці пра гэта. І давайце паглядзім, калі мы можам у цяперашні час пачаць ўжываць некаторыя лічбы, ці некаторыя формулы, з якой, каб апісаць эфектыўнасць нашай тэлефоннай кнізе Алгарытм, наш алгарытм экзамен кнігі, і ў больш агульным, пошуку інфармацыі. 

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

Гэта одно-- дэма збіраюцца да ўсё хутчэй і хутчэй у цяперашні час. Ідзем ўніз. Ваша імя? Тревор: Тревор. 

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

Так Тревор, прыемна сустрэцца з вамі. Дык вось масіў, так кажуць, спіс з сямі дзвярэй. Ідзіце наперад і знайсці нам нумар 50. І затым, пасля таго факту, раскажыце, як вы яго знайшлі. Калі be-- ўсе правы. Так, гэта адзін тут? Ой-ой. ДОБРА. Вы націснулі, што адзін. Добра. 

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

Тревор: Гэта адно. 

Дэвід Дж малая: Няма 

Тревор: ОК. Вось гэты. 

Дэвід Дж малая: Так. Гэта было добра. Добра. Дык што ж ваш алгарытм або Працэдура для гэтага, Тревор? 

Тревор: Я толькі што прайшоў праз дзверы, пакуль я не знайшоў 50. Дэвід Дж малая: ОК. Выдатна алгарытм. Так што ўсё ў парадку. Таму што на самай справе, калі я адкрыю што за гэтымі двума іншымі дзвярыма, тое, што мы знойдзем тут з'яўляецца тое, што у нас ёсць толькі выпадковы ўваход. Так што на самай справе, як было добра, як вы маглі б атрымаць. І на самай справе, вы атрымалі лепш, чым вычарпальна пошуку ўвесь масіў, таму што гэта было б сапраўды пашанцавала, калі вы ударыў колькасць 50 у самы апошні дзверы. Але што, калі мы замест даў вам здагадка. Выкажам здагадку, што я накшталт усё гэтыя дзверы вакол, так што ў вас ёсць нумары сартуюцца ў гэты раз, але на гэты раз ён на самай справе different-- гэты раз, гэта на самай справе сартуюцца для вас. А цяпер ставіце боку заключаецца ў хіт нумар 50. 

Тревор: ОК. 

Дэвід Дж малая: Што ваш алгарытм будзе? 

Тревор: Ну, калі гэта сартуецца, гэта альбо адбываецца каб be-- калі вялікі, каб па велічыні, змяншэнні, гэта будзе першы, або, калі гэта наадварот, гэта будзе апошнім. Так што я проста націсніце гэтую дзверы, і Затым проста націсніце на апошнюю дзверы. Дэвід Дж малая: Выдатна. Добра. Такім чынам, мы знайшлі нумар 50. Таму, як толькі вы ведалі, яны былі адсартаваныя, мы змаглі выкарыстаць гэтую здагадку. Так што яны занадта шмат, як прыклад тэлефоннай кнігі. Як толькі ў вас ёсць, нават з невялікая праблема, як гэта, Вашы ўваходы папярэдне адсартаваныя, мы можам на самай справе знайсці значэнне магчыма больш эфектыўна. 

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

Так што гэта будзе зрабіць для кліп у наступным годзе, як чаму я быў націснуўшы на маім ўласным экране. Але давайце зірнем на тое, што адбылося ў мінулым годзе з Джэем, які прыдумаў, шмат як Трэвар тут, добраахвотна, і ў гэтым кароткі кліп, вы ўбачыце як гэтая ж дэманстрацыйны не зусім выявіць тыя ж урокі, вынятыя. [Прайграванне відэа] -усе Я хачу, каб вы зараз зрабіць, гэта знайсці для мяне, і для нас, сапраўды, лік 50 адзін крок за адзін раз. 

-Количество 50? 

-Количество 50. І вы можаце выявіць тое, што За кожным з гэтых дзвярэй проста дакранаючыся яго пальцам. Чорт вазьмі. 

[Смяецца] 

[КАНЕЦ ПРАГЛЯДУ] Дэвід Дж малая: Так што пайшлі вельмі добра. Тыя былі малокомплектных дзверы. І Джэй, вядома, знайсці ўсё гэта занадта хутка. Тревор зрабіў нашмат лепшую працу у тэрмінах даступны момант, так бы мовіць, у гэтым годзе ў займае больш часу, каб знайсці яго. Вядома, тады мы далі Джэй другі шанец, у выніку чаго мы адсартаваныя дзверы, як мы гэта рабілі для Тревора, і Тревор зрабіў супер добра ў гэты раз. Але Джэй зрабіў гэта ў два разы хутчэй. [Прайграванне відэа] -The Мэтай цяпер з'яўляецца таксама знайсці нам нумар 50 але зрабіць гэта алгарытмічных, і раскажыце нам, як вы збіраецеся пра гэта. 

-ДОБРА. 

-А Калі вы знойдзеце яго, вы трымаеце кіно. Калі вы не знойдзеце яго, вы даць яго назад. 

-Man. 

-ай! 

- [Неразборліва] ОК. Так што я збіраюся праверыць канцы спачатку вызначыць, калі there's-- О. 

[Апладысменты] 

[КАНЕЦ ПРАГЛЯДУ] Дэвід Дж малая: ОК. Так сартавання дзверы ясна прыводзіць да большай эфектыўнасці. І так, у два разы хутчэй гэта тое, што я меў на ўвазе там. І так Джэй пашанцавала абодва разы. І ён таксама пашанцавала ў мінулым, што год, я замовіў некалькі Blu-Ray дыскаў на самай справе выдаюць. Мне шкада, у гэтым годзе мы не маюць тое ж самае, Тревор. Але ўсё-ткі лепш было некалькі гадоў таму. І некаторыя з вас, магчыма, ведаеце, гэта хлопец, Шон, які, калі ён быў у CS50, быў кінуты выклік з дакладным Тая ж праблема, хоць і ў SD, як вы хутка ўбачыце, таму ў дзень. І вы ўбачыце, што не толькі зрабіў ён зойме трохі больш часу, чым Джэй, крыху больш, чым Тревор, гэта было на самай справе гэта выдатная магчымасць займацца амаль усё ў Натоўп ла Кошт справа, заахвочваючы яму знайсці нумар, мы шукалі. Давайце. ўзяць хуткі погляд. 

[Прайграванне відэа] 

-ДОБРА. Так ваша задача тут, Шон, складаецца ў наступным. Я схаваў за імі Дзверы лік сем. Але схаваны ў некаторых з гэтых дзвярэй а таксама іншыя адмоўныя лікі. І ваша мэта, каб думаць гэтай верхняй радку лікаў як толькі масіў, ці проста Паслядоўнасць паперак з нумарамі ззаду іх. І ваша мэта, выкарыстоўваючы толькі верхнюю Масіў тут, знайсці мне нумар сем. І мы затым збіраецца крытыкаваць як вы ідзяце аб рабіць гэта. -Добра. -Найти Нам нумар сем, калі ласка. Няма. Пяць, 19, 13. 

[Смяецца] 

Гэта не пытанне з падвохам. Адзін. 

[Смяецца] На дадзены момант, ваш рахунак не вельмі добра, так што вы маглі б таксама працягваць. Тры. 

[Смяецца] 

Працягвай. Шчыра кажучы, я не магу дапамагчы, але цікава, тое, што вы нават думаць пра, so-- 

[Смяецца] Толькі верхні шэраг, так ў вас ёсць тры злева. Так што знайдзіце мне сем. 

[Смяецца] 17. Сем. 

[Апладысменты] 

Добра. 

[КАНЕЦ ПРАГЛЯДУ] 

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

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

Такім чынам, адна ў turquoise-- зялёны гэта? Вы здзяйсненні? Два. Ідзем ўніз. ДОБРА. Тры. Чатыры. Хай me-- ОК, пяць. Вы вылучаецца вашым сябрам. Шэсць, сем, восем. Давай до. Добра. Дзякую вас так шмат. Давай до. Давай до. 

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

Ганна: Анан. 

Дэвід Дж малая: Анан. Дэвід. Ваша імя? 

Іосіф: Джозэф. 

Дэвід Дж малая: Іосіф, Вы нумар два. 

Серэна: Серэна, нумар тры. Стэфан, нумар чатыры. Сінція: Сінція. Дэвід Дж малая: Сінція, нумар пяць. [Неразборліва] Дэвід Дж малая: [неразборліва]. Дэвід, нумар шэсць. Мэт: Мэт. Дэвід Дж малая: колькасць Мэтта сем. І што ж? 

WAVERLY: Уэверли. 

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

Выдатна. ДОБРА. Так што цяпер, мы збіраемся спытаць Пытанне ў некалькі розных спосабаў. Як мы можам ісці аб сартаванні гэтыя людзі тут? Таму што ў нас было некалькі падыходаў раней, у выніку чаго мы былі выгляд робіць дзве розныя вядра. А потым мы, як правіла, пірсінгам рэчы разам. Як толькі мы ўбачылі дзве лічбы які належаў разам, пакласці іх разам. Два лісты, якія належаць разам. 

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

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

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

Цяпер, яны добрыя. Я збіраюся рухацца далей, чатырох і шасці, выглядае добра. Не праблема. Шэсць і восем, ОК. Восем і адзін, яшчэ адна праблема. Таму што праўда пра восем і адной? Адзін прыходзіць да васьмі, і так, што мы павінны рабіць? Давайце памяняць гэтыя два. Адзін і восем. А цяпер, я збіраюся працягваць. Я збіраюся працягваць глядзець наперад. І давайце паглядзім, што адбудзецца. Восем і тры, з Вядома, у парадку. Давайце своп. Восем і сем, вядома. З парадку. Давайце своп. Восем гадоў і пяць, вядома, давайце падпампоўкі. Добра. Спіс сартуецца. да? 

ОК, відавочна, няма. Але гэта крыху лепш, праўда? Таму што апавяшчэнне, што адбылося. Кожны раз, калі мы правялі абмен, менш Колькасць і тып працаджваюць, што шлях, і большая колькасць перколируют гэты шлях, або мы будзем пачаць казаць прапускаюць да налева або барботируют направа. 

Цяпер, гэта не дастаткова, таму што у лепшым выпадку лік можа перайшлі адно месца наперад, або ў горшым выпадку, шэраг, магчыма, пераехаў на адну пазіцыю далей. Такім чынам, вы ведаеце, што гэты від з працаваў вельмі добра да гэтага часу. Дазвольце мне паспрабаваць яшчэ раз. Два і чатыры, яны ОК. Чатыры і шэсць, яны ОК. Шэсць і адзін, выйшаў з ладу. Такім чынам, давайце памяняць вам два. А цяпер звярніце ўвагу, што праблема-х пачынаюць атрымліваць трохі лепш зноў. Шэсць і тры, выйшаў з ладу. Давайце мяняць вас два. Шэсць і сем, вы добра. Сем і пяць, вядома, у парадку. Сем і восем, у парадку. А цяпер, я, магчыма, спатрэбіцца зрабіць гэта некалькі разоў. І на самай справе, думаю, для сябе магчыма, колькі разоў максімальна можа я павінен хадзіць туды-сюды? 

Мы вернемся да гэтага. Так два і чатыры па-ранейшаму ОК. Чатыры і адзін, Не. Такім чынам, давайце своп. І зноў, звярніце ўвагу, візуальна адзін з бурбалак выгляд злева, дзе ён павінен быць. Чатыры і тры замены. Чатыры і шэсць. Шэсць і пяць падпампоўкі. Шэсць і сем. Сем і восем добрыя. 

Добра. Мы атрымліваем яшчэ лепш. Такім чынам, давайце паглядзім. Цяпер у нас ёсць два і адзін. Вядома, памяняць. Два і тры, тры і чатыры, чатыры і пяць, шэсць і сем, сем і восем. Добра. І вы ведаеце, што? Таму што я зрабіў адно змяненне ёсць, дазвольце мне зрабіць адну праверку наяўнасці свядомасці. Дазвольце мне прайсці ўвесь шлях вярнуцца да пачатку. ДОБРА. Адзін з іх, two-- ды, бачыце? Нешта было не так. Тры, чатыры, пяць, шэсць, сем, восем. І ў гэтым апошнім праходзе, з'яўляюцца вы можаце прама цяпер з маім сцвярджаючы, што гэта сартуецца? ДОБРА. Візуальна, гэта абсалютна дакладна. Але функцыянальна, чым так і проста так у гэтым апошнім праходзе, што дазваляе каб пацвердзіць, што гэты спіс сапраўды Сартаваць? 

Што я рабіць ці не рабіць гэтага апошняга пасы? АЎДЫТОРЫЯ: Там не было ніякіх зменаў. Дэвід Дж малая: Выбачайце? АЎДЫТОРЫЯ: Няма зменаў. Дэвід Дж малая: Там не было ніякіх зменаў. Так што было б па-дурному з майго боку зрабіць гэта зноў той жа алгарытм калі я не зрабіць любы змены ў першы раз. І дзяржава не змянілася. Вядома, я не збіраюся рабіць любых змяненняў у другі раз. І так, гэта цяпер у бяспекі сказаць, спіс адсартаваны. 

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

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

Таму што інтуітыўна, які павінен працаваць таксама. Так чатыры, гэта даволі невялікі лік. Я буду памятаць, дзе гэта. Пачакайце хвіліну. Два менш. Дазвольце мне цяпер успомніце, калі два ёсць, і забыцца пра чатырох. Мы будзем мець справу з гэтым пазней. Шэсць, мне гэта не цікава. Восем, я не зацікаўлены ў. Адзін мой новы малы лік. Так што я збіраюся ўспомніць, дзе ты ёсць. Тры, не цікавіць. Сем, не цікавіць. Пяць, не цікавіць. 

Так, не падаючы этап у гэтым годзе, Я збіраюся захапіць колькасць одно-- і тое, што зноў ваша імя? 

Ганна: Анан. 

Дэвід Дж малая: Анан. І калі б вы маглі далучыцца да мяне ў пачатак спісу, давайце вам, дзе вы належыце. Unfortunately-- што ваша імя? 

Сцяпан: Стэфан. 

Дэвід Дж малая: Стэфан знаходзіцца ў дарозе. Таму, перш чым Стэфан вырашае гэтую Праблема, што мы павінны рабіць? Што мы робім са Стэфанам? 

АЎДЫТОРЫЯ: [неразборліва]. Дэвід Дж малая: ОК. Такім чынам, мы маглі б зрабіць гэта. Мы маглі б прыняць свайго роду Стэфана і яго чатыры, і проста пакласці яго ў зменнай і правесці на ёй некаторы колькасць часу, тым самым вызваляючы месца для нумар адзін. І гэта не дрэнна. Я мог бы прапанаваць, чаму не мы проста пакласці Стэфана тут? Чаму гэта можа парушыць адзін ідэй мы пачалі казаць пра апошні часу, на мінулым тыдні? Да? 

АЎДЫТОРЫЯ: [неразборліва]. 

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

Ці вы ведаеце, што? Я чуў, хто-то яшчэ прапанаваць гэта. Што яшчэ мы можам зрабіць са Стэфанам? Чаму б нам проста не выселіць яго і пакласці яго на сябе, дзе нумар адзін было. Так што, калі вы хочаце пайсці туды. І на самай справе, гэта даволі добрае рашэнне. Зараз, з аднаго боку, я накшталт з зрабіў праблему горш. Чатыры цяпер далей ад таго, дзе гэта павінна быць. Яна павінна быць да гэтага палове. 

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

А цяпер, што я збіраюся зрабіць, гэта забыцца пра нумар адзін пастаянна, таму што я ведаю Спіс ззаду мяне цяпер сартуюцца. Так што мой спіс быў раней памер восем. Цяпер, гэта памер сем. Так мая праблема становіцца менш, хоць лінейна. Так што цяпер, я збіраюся выбраць ток найменшы элемент, два. Шэсць, восем, чатыры, тры, сем, пяць. Гэта быў самы малы элемент. Так што я збіраюся зрабіць with-- які быў ваша імя? 

Іосіф: Джозэф. 

Дэвід Дж малая: Джозэф? Мы збіраемся, каб пакінуць Язэпа на месцы. Зараз, я збіраюся рабіць выгляд, што гэтыя хлопцы добра are--, Я ведаю, што гэтыя два ўжо адсартаваныя. Давайце зараз засяродзіцца на Астатняя частка спісу. Шэсць з'яўляецца бягучых найменшай. Восем больш. Чатыры цяпер ток маленькі. Тры цяпер току малая. І вось цяпер, я збіраюся выбраць тры, якія is-- што ваша імя зноў? Серэна: Серэна. Дэвід Дж малая: Серэна, калі б вы маглі захапіць ваш нумар і своп with-- Калсанг: Калсанг. Дэвід Дж малая: Калсанг. Вяртайся, і мы збіраецца памяняць гэтыя два. А цяпер, давайце паставіць гэта на аўтапілоце. Я збіраюся пайсці і пакінуць яго з вамі, хлопцы каб выбраць наступныя найменшыя элементы. Дун, шаравата, шаравата, шаравата. Нумар чатыры, што вы павінны рабіць? Выдатна. Зараз, я збіраюся зрабіць яшчэ адзін праход. Дун, шаравата, шаравата, шаравата. Я бачу пяць з'яўляецца наступным найменшай. Зараз, я збіраюся ўзяць яшчэ адзін праход. Дун, шаравата, шаравата, шаравата. Шэсць з'яўляецца найменшай. Добра. Сем самых маленькіх. Ніякіх зменаў. Восем самых маленькіх. Гатова. 

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

Так што гэта нават прасцей, магчыма, інтуітыўна, чым у мінулым. Давайце паспрабуем адзін апошні. Калі вы, хлопцы, можа скінуць сябе ў наступных палажэннях адзін апошні раз, давайце паглядзім, калі мы не можам Цяпер аформіць яшчэ адзін падыход. На самай справе, хто-то там бы прапанаваць як яшчэ мы маглі б ісці пра гэта? Без выкінуць слоўцы або роду адказаў, якія ўжо вядомыя, проста інтуітыўна, што мы маглі зрабіць? 

АЎДЫТОРЫЯ: [неразборліва]. Дэвід Дж малая: Так. Так што некаторыя вялікія інтуіцыя ёсць. Добрыя рэчы, здаецца, да гэтага часу здараюцца ў кампутарнай навуцы, калі мы дзелім і заваяваць праблему дзялення гэта ў два разы і палова на палову. І так на самой справе, мы можа пачаць рабіць гэта. І на самай справе, што будзе, мы будзем см, адзін з нашых лепшых рашэнняў пакуль. Але давайце вернемся да таго, што ў хуткім часе. На самай справе, мы збіраемся зрабіць што крыху пазней на гэтым тыдні. Што яшчэ мы маглі б зрабіць, каб вырашыць гэтую праблему? Такім чынам, кожны тут у здавалася б, выпадковым парадку. Вы ведаеце, што? Замест ісці наперад і назад, ўзад і наперад, туды-сюды кожны раз, гэта адчувае сябе падобна Я раблю шмат хадзіць. Чаму я не магу проста пачаць у пачатак спісу, і проста паставіць чатыры, дзе яна належыць? Такім чынам, дазвольце мне выказаць здагадку, што ў дадзены момант мой спіс толькі гэты першы элемент. Чатырох сартуюцца ў гэты момант часу, калі ўсё, што я клапачуся аб тым ўсе тут? Гэта свайго роду трывіяльна, ці не так? Як спіс, які змяшчае адзін нумар, і што нумар чатыры, відавочна, сартуюцца. 

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

Іосіф: Джозэф. 

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

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

Зараз, я накшталт undone-- У мяне прымаць адзін крок наперад, а затым адзін крок назад, таму што цяпер Джозэф будзе ў парадку. Так давайце зробім гэта. Калі б вы маглі ўзяць нумар адзін і крок назад на імгненне. Як мы можам put--, што Ваша імя было зноў? 

Ганна: Анан. 

Дэвід Дж малая: Анан на месцы? Што павінна адбыцца ў дачыненні да да двух, чатырох, шасці, васьмі і? Усе яны павінны перамясціць. Так што, калі восем хацеў перакласці , А затым шэсць, потым чатыры, потым два. І тады Анан, калі б вы хацеў прыехаць сюды, добра. Але тут, мы толькі выгляд заплаціла ў іншай кропцы ў алгарытме. У той час як апошні раз з выбарам сартаваць і нават пузырьковый сартавання, Я іду назад і наперад, назад і наперад, які, безумоўна, дадаўшы, да Час-мудры, і літаральна паэтапна. 

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

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

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

[Апладысменты] 

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

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

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

Але тады я не павінен трымаць гледзячы на ​​гэты элемент, таму што я ведаю, што гэта Ужо найменшай. Так што цяпер, я магу глядзець на ўсяго сем элементаў, то шэсць элементаў, затым пяць элементаў, то чатыры элемента. І так матэматычна, калі п лік элементаў або лічбаў што мы пачалі з таго, што вы можаце сабе што гэта тое ж самае, п мінус 1, плюс мінус 2 п крокаў, плюс мінус 3 п крокаў, плюс мінус 4 п крокаў, усё аж да ўсяго адзін крок. І я на маім апошнім чалавека. 

І калі вы памятаеце, што шмат з кнігі або статыстыка матэматычныя кнігі ёсць тыя формулы, на цвёрдым пераплёце назад або перад імі, высвятляецца, што гэтай серыі можа быць выказана больш проста мінус, як у п разоў п 1 над 2. І гэта нармальна, калі гэта не на пярэднім краі свайго розуму. Але гэта сапраўды так. Гэта проста просты спосаб напісання. І потым, калі вы думаеце, вярнуцца да пачатковай школе, калі вы толькі пачынаеце множання рэчы з, гэта, вядома ,, проста н квадраце мінус п дзеліцца на 2. Усё, што я зрабіў, гэта пашырыць выразы там. І так давайце перапішам гэта крыху па-іншаму. Вось н квадраце падзяліць на 2 мінус п / 2. 

Такім чынам, яшчэ раз, я проста выгляд прымянення некаторыя арыфметычныя правілы ёсць. Але звярніце ўвагу, у цяперашні час, што самая вялікая тэрмін у гэтым выразе, так бы мовіць, з'яўляецца тое, што п у квадраце. Так што, так, гэта п квадрат дзеліцца на 2, мінус п / 2. 

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

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

Такім чынам, мы павінны былі б тую ж формулу, як і раней. Я падключыць мільён, так што я атрымліваю мільён квадрат дзеліцца на 2, мінус мільён падзяліць на 2. Калі я што матэматыку ў загадзя тут, у нас ёсць за 500 млрд мінус 500000, які дае нам +499999500000, што па-чартоўску вялікі. 

На самай справе, калі параўнаць з прадпрыемствам 499000000000 999 млн 500000 супраць нашай першапачатковай кошту, 500 мільярдаў, гэта так па-чартоўску блізка. Дакладна? п квадраце падзяліць на 2 дае us-- ці, хутчэй, н квадраце падзяліць на 2 даў нам 500 млрд. Гэта па-чартоўску блізка каб 499,999,500,000, які павінен сказаць, аднімання ад 500000, ці ў больш агульным, адымаючы ад п квадраце, на самай справе не вялікая справа. У Рускай квадрат робіць гэтыя лік вырасце вельмі хутка. 

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

Так, мы падзелу на 2 у там. Так, мы адымаючы ад п мінус 2. Але ў рэшце рэшт, тэрмін што на самой справе шкодзіць нам і варта нам шмат крокаў, што квадрат тэрмін. І так, што вучоны-кампутарнік збіраецца як правіла, робяць гэта ігнараваць усе тыя меншыя тэрміны, парадак і проста паглядзець на той, які спрыяе найбольш да кошту. 

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

Так што, калі вы кажаце, што алгарытм у вялікім O н квадрат, як я прапанаваў проста Хвіліну таму, што сродкі што з пункту гледжання яго эксплуатацыі часу або яго эфектыўнасць, яна займае парадку н квадраце крокі. Можа быць, больш, можа менш. Але гэта на парадак п у квадраце. І гэта верхняя мяжа. Гэта не будзе больш хваравітым, чым гэта. Гэта не будзе п кубе, або 2 да п, ці нешта значна большае. Гэта верхняя мяжа на тое, што, што кошт. Таму, улічваючы, што, давайце Разгледзім некалькі прыкладаў. І гэта толькі канчатковы спіс вельмі агульныя часу праходжання Для алгарытмаў, якія прызначаецца, каб быць ілюструюць некаторыя рэчы, якія мы бачыў ужо. 

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

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

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

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

Я бачу чатыры. Прама тут. Пяць, шэсць, сем, восем. Там няма прычын, каб паўтарацца. І так, колькі крокаў з'яўляецца тое, што праз п? Гэта на парадак п крокі, праўда? п мінус 1. Але я ўзяў лінейны нумар крокаў, і цяпер я зрабіў. Так што гэта лепшы выпадак, хоць. Што можна сказаць пра горшым выпадку? Што восем былі там, і сем былі там, і адзін і два былі тут, так што спіс сапраўды былі назад? 

Ну, тое, што адбываецца на самай справе калі гэта лік? І мы будзем рабіць толькі пару прыкладаў. Што рабіць, калі, сапраўды, нумар восем тут, і number-- воклічы. Так што, калі, сапраўды, колькасць Восем цалкам тут, і я выкарыстоўваю ўстаўкі роду? 

ДОБРА. Я сцвярджаю, на дадзены момант ён знаходзіцца ў месцы. Але цяпер, seven-- дзе ж сем ісці? Вядома, гэта ідзе тут. Так што я павінен рухацца восем над адным месцы. Зараз шэсць, дзе гэта ідзе? Ну, усё ў парадку. Зараз, я павінен рухацца восем над месца, і сем над месцам, і тады я плюхнуться шэсць. 

Такім чынам, першы раз, гэта кошт мне адзін крок, каб выправіць становішча, то гэта каштавала мне два крокі, каб выправіць становішча. Колькі крокаў гэта збіраецца распачаць, каб выправіць рэчы, каб паставіць пяць у патрэбным месцы? Тры. Таму што цяпер я павінен рухацца адзін, два, тры. Колькі крокаў ён збіраецца ўзяць пакласці чатыры ў патрэбным месцы? 4 плюс 5, плюс 6 плюс 7. 

І так гэта матэматычна ідэнтычныя тое, што мы апісалі для выбару роду. У нас ёсць гэтая серыя вось толькі расце. 1 плюс 2 плюс 3 плюс 4, ці, наадварот, плюс 6 ліпеня плюс 5 плюс 4 дадае на сёння Мэты ў парадку п у квадраце. 

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

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

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

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

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

Што варта прыняць лінейны нумар крокаў, якія мы бачылі да гэтага часу? Што гэта? Пошук тэлефонны даведнік. Першы алгарытм. Дакладна? Дзе мы лінейна пошук Майк Сміт? Сапраўды. Ад нулявы тыдні, калі я пачаў ператвараючы адну старонку ў той час, і я нават сказаў, што гэта быў выгляд алгарытму лінейнай пачуццё, і ў нас было што малюначак на дошка з прамой чырвонай лініі і прамой жоўты лінія, гэта былі сапраўды алгарытмы, якія ў вялікай O п. 

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

Цяпер, як у бок, тое, што пра іншы аптымізацыі з нуля тыдзень? Два, чатыры, шэсць, восем, 10, 12. Кампутар вучоны будзе рэалізаваць, пачакайце хвіліну, гэта парадку п дзеліцца на два этапы. Дакладна? Таму што я раблю два чалавекі адначасова. Але мы збіраемся ігнараваць гэтыя малодшыя члены, і мы толькі збіраемся выкінуць падзяліць на 2, і проста сказаць, вялікі вываду п для гэтага алгарытму, а таксама. 

Як наконт гэтага? Мы прапускаем некаторыя з іх, але тое, што быў алгарытм, які быў часопіс п? Гэта заняло прыкладна ўвайсці п крокаў? Падзяляй і ўладар. Дакладна. Як, напрыклад тэлефоннай кнігі ў нулявы тыдні і сёння раніцай, дзе мы падзялілі праблемы зноў і зноў, і зноў. Мы звярнулі яго на дошцы у тыдзень нуля пры выгнутай зялёнай лініяй, і мы сказалі, што гэта быў дзень лагарыфмічная алгарытм. 

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

Што робіць крок, або, больш канкрэтна пастаяннае лік крокаў? Можа быць, гэта двое, можа быць, гэта тры, але вучоны проста спрашчае яго як Big O 1, некаторая канстанта лік крокаў. Што-то вы маглі б зрабіць, што прымае пастаяннае колькасць крокаў? 

Што час працы пляскаючы? Пастаяннае час. Дакладна? Маўляў, тое, што час працы рабіць што-небудзь, што бярэ толькі адзін Аперацыя, як друкаваць F Hello World. Гэта можа быць названа пастаянная часу, калі менш кут выпадку з F друк, Што можа час працы друку F на самай справе быць? І чаму? Што н вымярэння ў гэтым выпадку? 

АЎДЫТОРЫЯ: [неразборліва]. Дэвід Дж малая: Дакладна. Колькасць знакаў мы хочам, каб надрукаваць. Так што гэта вельмі кантэксту. Сёння мы засяродзіліся шмат на літары і лічбы тут на дошцы. Але гэта можа быць таксама сімвалы ў рэальную радок. Вось і атрымліваецца, ёсць іншы мера, якая пачне клапаціцца пра, і гэта насупраць вялікага О, так бы мовіць. 

Гэта амега абазначэння. У той час як вялікая вываду азначае, што гэта, то Верхняя мяжа на бегавой часу? Максімальна, колькі часу можа нешта ўзяць? Omega-- шкада, што гэта працягвае прыбываць up-- з'яўляецца супрацьлегласцю, што у выніку чаго гэта ніжняя мяжа на колькасць часу што-то можа заняць. 

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

Колькі часу трэба, каб Сартаваць п элементаў у лепшае Справа выкарыстоўваючы нешта накшталт бурбалкі роду? Выкажам здагадку, што ваш спіс ужо адсартаваны. Мы сказалі, пузырьковый сартаванне бярэ на парадак п квадраце крокі. Але што, калі гэта ўжо адсартаваныя? Што рабіць, калі вы разумееце, пасля адзін праход па масіву што вы не зрабілі ні аднаго свопы? Вы павінны працягваць рабіць больш праходзіць? 

Няма. Такім чынам, ніжняя мяжа пузырьковый сартавання можна сказаць, быць лінейнай. Амега п. І мы можам глядзець на астатнія іх, а таксама. Такім чынам, давайце зірнем на толькі візуалізацыі тут каб убачыць, як яны адрозніваюцца. Я збіраюся пайсці сюды ў гэта старонка, якая даступная на вэб-сайце С50, у але гэта будзе боль, каб атрымаць працу, так як ён выкарыстоўвае тэхналогію пад назвай Java-аплеты, які з'яўляецца у значнай ступені падтрымліваецца ў гэтыя дні, па меншай меры, Chrome і некаторых іншых. 

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

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

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

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

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

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

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

[Гукавога сігналу] 

Прычым вы прэтэндуеце частату заснавана на вышыні бар бар. Гэта свайго роду бурбалка. 

[Скрыўленых гукавога сігналу] 

Далей ідзе is-- на наступным is-- выбар роду, дзе зноў, мы выбару наступны найменшы элемент, і мы можам бачыць, як ён расце злева направа. 

Зліццё сартаваць, наш пераможца да гэтага часу сёння. Звярніце ўвагу, як гэта дзялення рэчы у [неразборліва] палову і чвэрці. Гном роду, якія мы не маем казалі, і стварае візуальна і audally трохі розная форма і гук. Пераход наперад і назад, ачысткі рэчы. Акрамя таго, праверыць пірамідальнай сартавання на вэб-сайце гэтага хлопца. 

І гэта ўсё. Мы ўбачым вас у наступны раз. 

[Свіст І МУЗЫКА]