[Музыка Прайграванне] 

Дэвід Дж. малая: Добра. Так што сардэчна запрашаем назад. Гэта CS50, і з'яўляецца Да канца тыдня тры. 

Так ўспомнім ў апошнія некалькі тыдняў, Мы праводзілі даволі шмат час на C, па праграмаванні, па сінтаксісу. І гэта цалкам нармальна, калі вы ўсё яшчэ змагаецца з праблемай ўсталяваць 2, каб быць біцца галавой аб сцяну. Гэта загадкавае выгляду паведамленні пра памылку а памылкі, якія вы Не цалкам можа пагнаць ўніз. Таму што, будзьце ўпэўненыя, што ўсяго за час некалькі тыдняў вы будзеце азірацца на рэчы, як Цэзар, і [? V-genair,?] можа быць, нават расколіна, і разумеюць, наколькі далёка вы прыехалі на працягу кароткага перыяду часу. Так што, калі гэта суцешыць, павесіць там на дадзены момант. 

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

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

Джэніфер: [неразборліва] 

Дэвід Дж. малая: Прабачце? 

Джэніфер: Джэніфер. 

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

15. 16. 50. Прыгожа зроблена. Добра. Апладысментаў для Джэніфер. 

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

Добра. Так якая была ваша стратэгія знаходжання колькасці, 50? 

Джэніфер: Хм, я думаў, можа быць, калі - [Неразборліва] 

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

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

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

Джэніфер: О, дарогай. 

Дэвід Дж. малая: Ах. 

Джэніфер: Так, мне проста пашанцавала. 

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

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

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

Джэніфер: Ці, калі гэта скончыцца тым, сапраўды вялікі, то ад большага да меншага. 

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

Джэніфер: Усё з іх. 

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

Джэніфер: Так. 

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

Джэніфер: OK. 

Дэвід Дж. малая: - раней? 

Джэніфер: Давайце пачнем з першай. 

Дэвід Дж. малая: Добра. Пачнем з першага. 4. А дзе вы збіраецеся пайсці, і чаму? 

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

Дэвід Дж. малая: OK. Давайце паглядзім, што вы думаеце? 

Джэніфер: Паспрабуйце апошні. Ніцу. 

Дэвід Дж. малая: Вельмі прыгожа зроблена. Добра. 

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

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

Джэніфер: OK. 

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

Джэніфер: Вярнуцца да пачатку. 

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

Джэніфер: Калі б я не ведаюць, што яны адсартаваныя. 

Дэвід Дж. малая: Правільна. Ну, калі вы ведалі у іх разабраліся - 

Джэніфер: О, ведаў, так. 

Дэвід Дж. малая: - Але вы не ведаю, дзе быў яшчэ 50? 

Джэніфер: Проста працягвайце ісці. 

Дэвід Дж. малая: Добра. ОК. Працягвайце. Добра, што я магу працаваць. 

Джэніфер: OK. 

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

Джэніфер: лінейная -. 

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

Джэніфер: Пачатак у сярэдзіне. 

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

Джэніфер: Перайсці ў гэтую палову. 

Дэвід Дж. малая: А чаму б не так? 

Джэніфер: Калі яны былі выглядам найменшая да буйных, то 50 павінна быць у гэтым кірунку. 

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

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

Дэвід Дж. малая: Добра. 42. Добра, так што цяпер твая інстынкт кажа вам? 

Джэніфер: Я магу выкінуць гэта, а затым проста - 

Дэвід Дж. малая: OK. Добра, вы можаце выкінуць Левая палова там. 

Джэніфер: - выбраць гэтага. 

Дэвід Дж. малая: І правільна. 

Джэніфер: Так. 

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

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

Джэніфер: Гэта трэба, як, можа быць, удвая скараціць час, ці нават больш, так. 

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

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

Выступоўца 1: [неразборліва] 

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

Джэніфер: Ура. 

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

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

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

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

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

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

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

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

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

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

Тое, што спіс быў адсартаваны. Таму, як толькі спіс быў адсартаваны, мы сцвярджаюць, што Джэніфер была ў стане зрабіць прынцыпова лепш. 7 дзвярэй, так, ужо не так цікава, Аднак уявім, што мы 7000000 дзвярэй. Часопіс N, безумоўна, будзе выконваць многае, многае хутчэй у доўгатэрміновай перспектыве. Але яна павінна была быць Дзверы адсартаваныя для яе. Зараз, я ўзяў на сябе смеласць зрабіць гэта Загадзя на экране кампутара тут, але выкажам здагадку, што Джэніфер павінен быў зрабіць гэта самой? Выкажам здагадку, што дзверы ў пытанне прадстаўлены дадзеныя ў базе дадзеных, або Сябры зарэгістраваныя для Facebook, або любы вэб-старонкі ў Інтэрнэце, якія розныя вэб-сайты, магчыма, спатрэбіцца у індэкс або пошук. 

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

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

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

[Прамежкавае VOICES] 

Дэвід Дж. малая: Oop, прабачце. Памылка. Добра. Ну, вось мы ідзем. Нумар пяць. Нумар шэсць. Адзін, два, тры, чатыры, пяць, шэсць, сем. О, гэта нязручна. 

Дакладчык 2: Я буду проста атрымаць -. 

Дэвід Дж. малая: Вельмі. Добра. Дзякуй за ўдзел. 

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

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

GRACE: Прывітанне, я Грэйс. Я на другім курсе ў Левереттом дом. 

BRANSON: Прывітанне. Я Брэнсон. Я на першым курсе ў зварцы. 

GABE: Прывітанне. Я Гейб. Я малодшы ў Кабот. 

Ніл: Я Ніл. Я на першым курсе ў Мэтьюз. 

Джэйсан: Я Джэйсанам. Я на першым курсе ў Greenough. 

Майк: Я Майкам. Я на першым курсе ў шэрых. 

Джэсі: Я Джэс. Я на другім курсе ў Левереттом. 

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

ОК. Добра. Гэта было сапраўды цыраваць хутка. Зараз хто-то тут, што быў алгарытм што гэтыя хлопцы ўжываць? 

Выступоўца 1: найменшага да найбольшага. 

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

Выступоўца 1: [неразборліва] 

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

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

Такім чынам, вы два хлопцы і чатыры два. Ці Вы правільным ці няправільным замовай? Відавочна няправільна. Такім чынам, мы памяняліся месцамі. Цяпер я збіраюся адысці ў бок тут і казаць, 05:56. Вы правільна ці няправільна? 

GABE: Правільна. 

Дэвід Дж. малая: Правільна. Шэсць і адзін? Не-е. Swap. Дык вось зменамі. Шэсць і тры? Не-е. Swap. Шасцю і сям'ю? Выглядае добра. Сем і пяць? 

Джэсі: [неразборліва] 

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

І цяпер, якія павінны мой алгарытм на другім праходзе быць? 

Выступоўца 1: Тое ж самае. 

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

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

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

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

Выступоўца 1: N: 

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

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

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

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

Зараз, колькі крокаў я ёсць прыняць, калі я пераматаная? Ну, мы маглі фактычна падвоіцца, што калі мы сапраўды хацелі, але цяпер, я раз збіраўся сказаць, усё ў парадку, іншая N мінус 1. Такім чынам, N мінус 1 збіраецца атрымаць раздражняе адсочваць, так што давайце проста за злёгку. Так 2n крокаў. Так 14 крокаў, плюс-мінус. 

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

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

Майк: Майк. 

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

Ніл: Ніл. 

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

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

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

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

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

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

Усе шляху ў самым пачатку. Так Ніл, пойдзем са мной. І што цябе клічуць? 

GRACE: мілата. 

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

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

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

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

Джэйсан: Джэйсан. 

Дэвід Дж. малая: Джэйсан. Так Джэйсан зараз найменшая Элемент я выбраў. Куды ён пойдзе? Дык дзе шэсць ёсць. І ваша імя зноў? 

GABE: Гейб. 

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

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

Выступоўца 3: Гэта п крокаў [неразборліва]. 

Дэвід Дж. малая: Гэта п крокаў па большай меры. Цікава. Так гэта хоць? Так як жа я магу знайсці найменшы элемент? Колькі крокаў я павінны прыняць знайсці найменшы элемент? Я глянуў на ўсім шляху У рэшце рэшт, ці не так? Таму што ў горшым выпадку, тое, што Калі Ніл былі тут? Так проста знайсці найменшы элемент бярэ мяне п крокаў, ці N мінус 1. Але, добра. Так выправіць Ніл. Памятаеце, што, хвіліну ці каля таго таму. 

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

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

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

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

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

BRANSON: Брэнсон. 

Дэвід Дж. малая: Брэнсон. Так Брэнсон нумар два. Так што я збіраюся ўзяць цябе за момантам. І цяпер, дзе вы належыце у гэтым масіве? Такім чынам, каб права ласкі. Такім чынам, яшчэ раз, мы як бы робіць Грэйс зрабіць шмат працы тут. Дзе мы ставім вас? Такім чынам, мы збіраемся, каб слізгаць вам злева, і ўстаўце Брэнсон там. Але зараз я сцвярджаю, што вы, хлопцы, зрабілі. Але звярніце ўвагу, што я не выкарыстоўваю дадатковае прастору. Ён па-ранейшаму 2 элемента Тут 5 тут. Агульная плошча масіва складае 7, так што я не падман, усё ў парадку? 

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

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

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

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

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

Добра. Там вы ідзяце. Дзякуй за - 

BRANSON: [неразборліва] трымаць нумары. 

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

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

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

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

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

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

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

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

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

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

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

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

[Прамежкавае VOICES] 

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

Зараз давайце пяройдзем у сартаванні Алгарытмы ня шукае - О, на самай справе пойдуць у гэта поле пустым. Двайковы пошук у лепшым выпадку? Гэта таксама 1, калі ён проста бывае у самым цэнтры масіва, або сярэдзіне тэлефоннай кнігі. Зараз давайце зробім пузырьковый сартавання. Такім чынам, яшчэ раз, цяпер мы ўваходзім у родаў, не пошук. 

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

Выступоўца 1: N. 

Дэвід Дж. малая: N, я чуў. 

Выступоўца 1: 2. 

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

[Прамежкавае VOICES] 

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

Што такое горшым выпадку працуе момант выбару выгляду? 

Выступоўца 4: N ў квадраце. 

Дэвід Дж. малая: N плошчы, я чую. Але чаму N ў квадраце, інтуітыўна? 

Выступоўца 4: Таму што мы проста зрабілі гэта. 

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

SPEAKER 5: [неразборліва] 

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

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

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

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

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

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

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

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