СПІКЕР: Добра, гэта CS50. Гэта канец тры тыдні, і калі Вы не скарысталіся ўжо, ведаю, што там будзе абед у гэтую пятніцу, як звычайна, дзе Вы можаце атрымліваць асалоду ад добрай гутаркай і ежа ў Агонь і лёд з некаторымі з CS50 сайт персанал і аднакласнікі. Галава да гэтага URL тут. Зараз вы, напэўна, памятаеце, ці вы у бліжэйшы час можа быць знаёмы з, гэтыя рэчы тут, якія прыведзены ў канцы семестра для многіх класаў. Так званыя экзаменацыйныя сінія кнігі, у якіх Вы пішаце свае адказы на іспытах. Цяпер у мяне ёсць тут 26 такіх блакітныя кнігі, на кожны з іх напісана імя, да Z. І сапраўды, імёны, што проста, да Z. І адзін з мэты пад рукой сёння будзе працягваць тое, што мы пачалі ў панядзелак, які не з'яўляецца столькі гледзячы на ​​код, але на самой справе гледзячы на ​​ідэі і вырашэння праблем. Адна з мэтаў і Абяцанні гэтага курса з'яўляецца навучыць вас думаць больш старанна, больш метадычна, і больш эфектыўна вырашаць праблемы. І на самай справе, што мы можам зрабіць, што сапраўды , Нават не дакранаючыся ні аднаго радка кода. Таму ў мяне ёсць пару сланоў тут сёння, аранжавы і сіні, калі б мы маглі атрымаць адзін добраахвотнік, можа быць, ад далей таму, чым звычайна. Як наконт прама там, давай ўніз. Мэта, якая будзе ў дапамагчы плюс адміністраваць гэты экзамен тут. Як цябе завуць? АЎДЫТОРЫЯ: Мэры Бэт. СПІКЕР: Мэры Бэт, давай до. Дазвольце мне мікрафон тут для вас. Прыемна пазнаёміцца. АЎДЫТОРЫЯ: Прыемна пазнаёміцца. СПІКЕР: Добра, у мяне ёсць тут сіні кнігі праз Z, і я збіраюся рабіць выгляд, што У мяне ёсць адзін са студэнтаў, і яны ідуць у некалькі выпадковым У канцы трохгадзіннага іспыту блока, такім чынам, яны ў канчатковым выніку ў некаторых полуслучайная парадак, як гэта. Зараз ваша задача ў імгненне збіраецца каб be-- гэта на самай справе, як яны атрымліваюць Аказалася, у канцы клас, хутчэй за ўсё. Ваша задача цяпер будзе, цалкам проста, каб адсартаваць гэтыя сінія кнігі для нас ад А да Z. АЎДЫТОРЫЯ: О, гэта збіраецца ўзяць назаўжды. СПІКЕР: І мы будзем глядзець ня, як вы робіце гэта, ніякага ціску. АЎДЫТОРЫЯ: Не, ніякага ціску ці нічога. СПІКЕР: І для задавальнення, давайце мірыцца таймер. АЎДЫТОРЫЯ: Так весела, так весела. СПІКЕР: я магу трымаць мікрафон для вас. Добра, што мы толькі што падвоілі хуткасць. Такім чынам, у той жа час, Дазвольце мне задаць што будзе пытанне для Мэры Бэт з'яўляецца тое, што яна робіць, як гэта яна збіраецца аб рашэнні гэтага? І на самай справе, вы не маглі б Задумваліся аб чым так проста, як калі вы выбіраеце да 26 кнігах, як гэта, якія маюць натуральнае замовы да іх. Які працэс што вы на самай справе выкарыстаць? Гэта досыць выпадковым проста выбіраючы першы, які вы бачыце і пакласці яе на месца? Вы спачатку перамясціць свае рукі вакол шукаю затым шукаеце B? Вы зірніце на Пара з іх бок аб бок і проста сказаць, пастойце, гэта не мае рацыю, а затым памяняць парадак? Мы бачылі ўжо ў панядзелак што ёсць некалькі спосабаў , У якім мы можам зрабіць гэта, і сапраўды, як мы набліжаемся да канца тут, Я б прыняць да ведама, магчыма, чаго Мэры Бэт робіць. У нас ёсць некалькі паль падобна, большы, тры паменш. АЎДЫТОРЫЯ: я іх замове калі я знаходжу два лісты што я ведаю, разам у паслядоўнасці, Я паклаў іх разам так, што я не прыйдзецца турбавацца аб захаванні трэк з цэлага шэрагу кніг. Гэта проста, ну, па-першае, У мяне гэты стэк тут. СПІКЕР: Так, амаль як галаваломка частак, якія маюць правільную форму да супадаюць адзін з адным. АЎДЫТОРЫЯ: Даволі шмат, так. СПІКЕР: ОК, выдатна. І цяпер кожны з іх палі Меркавана сартуюцца? АЎДЫТОРЫЯ: Так. СПІКЕР: Добра, да Z. All Добра, віншую, вы зрабілі гэта. У вас ёсць выбар. Сіні? Добра, дзякуй вам за гэта. Так Мэры Бэт зрабіў прапанаваць што яе падыход быў, але тое, што гэта яшчэ адзін падыход, як вам можа ісці аб сартаванні гэтыя рэчы? Што б вы зрабілі? Запіс біць было б адна хвіліна і 50 або каля таго секунд, плюс тыя, якія я забыўся палічыць. Што б вы зрабілі? Так? АЎДЫТОРЫЯ: Вазьміце стос. Пачніце з самага пачатку. Праверце вашыя дакументы. І калі верхні вышэй чым, можа быць, яны, ніжні з'яўляецца вышэй, то памяняць іх. СПІКЕР: ОК, так што пачынаць у верхняй і ніжняй, а затым працаваць ваш шлях ўнутр так, памяняўшы іх месцамі? Такім чынам, трохі падобны па духу пузырьковый сартавання, але выбар крайнасці ня суседнія пары. Але за выключэннем гэтага з'яўляецца тое, што ёсць напэўна куча рознаму мы маглі б зрабіць гэта, і шчыра кажучы, я думаю, вам выгляд прыняў пару падыходаў, ці не так? Вы зрабілі тое чатырох адсартаваных паль, і затым эфектыўна аб'ядналі іх разам. І вось, мяркую, яшчэ адзін Тэхніка ў цэлым. Вы не разглядаць яго як адзін вялікі кучы, Вы падзялілі праблему на чатыры карэ, калі хочаце, і тады так ці інакш аб'ядналі іх у канцы. Такім чынам, давайце разгледзім, у канчатковым рахунку ,, як яшчэ мы маглі б зрабіць гэта. Мы аформлена паняцце пузырьковый сартавання апошні раз, і пузырьковый сартавання нагадаем было Алгарытм, які мы візуалізавалі з васьмі сваіх аднакласнікаў тут, здавалася б, выпадкова сартуюцца спачатку. І мы тады вырашылі парамі, калі два элемента з таго, проста памяняць іх месцамі. Так чатыры і два відавочна, з таго, так гэтыя два аднакласнікаў памяняліся месцамі. А потым мы паўтарылі з чатырох да шасці гадоў, затым шэсць і восем, на кожнай ітэрацыі, рухацца направа. Таму, улічваючы, восем чалавек, колькі парамі параўнання я зрабіў падчас прагулкі з злева направа ў адной такой ітэрацыі? Колькі параўнання? Сем, ці не так? Таму што, калі ёсць восем людзі, але ў вас ёсць пару ім і вы працягваць рухацца адзін хоп направа, вы не будзеце мець восем параўнання, таму што вы не можаце параўнаць элемент сам у сабе, ці гэта будзе проста бессэнсоўна, так што вы павінны сем. Ці ў больш агульным, калі у нас ёсць рускіх людзей, мы зрабіць п мінус 1 параўнанняў з пузырьковый сартавання. Такім чынам, давайце разгледзім цяпер, наколькі добра ці дрэнна бурбалка быў сам, і паспрабуйце даць сабе слоўнік з для крытыкі алгарытмаў, як гэта, і неўзабаве самастойна. Так пры першым праходжанні праз пузырьковый сартавання, першы раз Я ішоў злева направа па этап, узяў мяне н мінус 1 параўнанняў. І гэта будзе мой адзінка вымярэння, ці не так? Я быў збольшага гаварыць і шпацыруючы, некалькі хутка, некалькі павольна, так лічу сваіх секундах ня асабліва паказальна, але падліку колькасці аперацыі, якія я зрабіў у панядзелак, параўнання двух людзей, што адчувае сябе як добры адзінкі вымярэння. Так н мінус 1 крокі ў першы раз, але тое што адбылося пасля гэтага? Што адзін Верх адзін праход праз адваротным выпадку малокомплектных спіс? Што вы можаце сказаць мне пра элеменце які быў цалкам там? Так? Гэта быў самы вялікі элемент, ці не так? Нумар восем, хоць яна пачалося тут, кожны раз, калі я у параўнанні з ёй супраць сусед, яна працягвала б'ецца справа Правая частка спісу. І на самай справе, вось дзе Алгарытм атрымаў сваю назву. Зараз па гэтай логіцы, колькі параўнання ці трэба рабіць на другі раз Я раблю, што праход злева направа? н мінус 2, ці не так? Было б проста марнаваць свой час, калі I трымаць параўноўваючы восем супраць каго яшчэ, таму што мы ўжо ведаем яна была ў патрэбным месцы. Так што гэта крыху аптымізацыя, таму ў наступны праход будзе плюс н мінус два крокі, дзе п лік людзей. Цяпер вы можаце роду экстрапаляцыі, нават калі вы не спецыяліст па кампутарах, як гэта сканчаецца. У канцы гэтага алгарытму, па-відаць ў вас ёсць толькі адно параўнанне пакінулі. Вы павінны роду выправіць пачатку спісу ў выпадку двух і адзін выйшлі з ладу і павінен быць адзін і два, так што гэта ўпора на плюс 1 Канчатковае параўнанне. Цяпер кропка, кропка, кропка выгляд хваляў гэта рукі ў некаторых з сакавіцей дэталяў, але давайце проста ісці наперад і спрашчэння. Калі вы памятаеце з высокага школа, шчыра кажучы, многія з вас была матэматычныя кнігі, якія мелі трохі шпаргалка на вокладцы або задняя вечка, што паказаў вам, Сумаванне што серыя, як гэта ў канчатковым рахунку складаюцца ў. У агульным выпадку, калі ў вас ёсць зменная, як у я, і на самай справе гэта адно, калі вы паглядзіце на ваш старая школа матэматыка кніга, вы ўбачыце, што гэта на самай справе дадае да гэтай сумы тут, п раз п мінус 1 усе падзеленае на лік 2. Так што на дадзены дазвольце мне проста прадугледжваюць гэта дакладна, так на скачок веры, гэта тое, што гэта падводзіць да, і мы маглі даказаць, што ў больш агульным выпадку. Але цяпер давайце пашырым гэта. Так што давайце памножым гэта, так вось н квадрат, мінус п, усё падзяліць на 2. Гэта сапраўды п квадрат, падзеленае на 2, мінус п над 2, так што ўсё добра і цікава. Але што адбудзецца, калі мы Убудова значэнне? Выкажам здагадку, у мяне не было восем людзі, але сказаць, мільён. І млн толькі таму, што гэта даволі вялікая сума, давайце падключыць, што ў і паглядзець, што адбываецца. Так што, калі я падлучу млн у гэтай формуле Я іду, каб атрымаць мільён квадрат, падзеленае на 2, мінус млн, падзеленае на 2. Цяпер тое, што, што збіраецца раўняцца? Так 500000000000, мінус 500 000. А калі я на самой справе што матэматыка, гэта азначае, што сартаванне мільён людзі з пузырьковый сартавання можа заняць мне 499.999.500.000 крокі ці параўнання ў рэшце рэшт, мы проста экстрапаляцыі. Гэта адчувае сябе даволі павольна, але, шчыра кажучы вымярэння адзін пэўны ўваход як гэта, не ўсё, што кажа пра многае. Але на самой справе гэта азначае, што да як п атрымлівае больш і больш, гэты алгарытм выгляд адчувае сябе горш і горш, ці вы сапраўды пачынаюць адчуваць боль, што ўзвядзенне ў ступень, што п квадрат, які дадае даволі хутка. І гэтая дэталь не страціў на людзей, на самой справе Некалькі гадоў назад нейкі сенатар, які быў агітацыя, сеў на сумоўе з Эрыкам кампаніі Google Шміт, генеральны дырэктар у той час, і быў кінуты выклік з пытаннем гэтак жа, як мы даследуем сёння. Давайце зірнем. [ВИДЕОВОСПРОИЗВЕДЕНИЕ] -Senator, Што ты тут у Google, і мне падабаецца думаць пра прэзідэнцтва як сумоўе. Цяпер, гэта цяжка атрымаць праца ў якасці прэзідэнта, і вы збіраецеся праз суровыя цяпер. Гэта таксама цяжка атрымаць працу ў Google. У нас ёсць пытанні, і мы просім нашых кандыдатаў пытанні, і гэты ад Лары Швімэр. Што-вы, хлопцы, думаеце, што я жартую, гэта прама тут. Што з'яўляецца найбольш эфектыўным спосабам сартаваць мільён 32-разрадных цэлых лікаў? -Well-- -Прабачце, Maybe-- Не, не, не. Я думаю, што бурбалка то будзе няправільны шлях. -Давай, Які сказаў яму, гэты? Я не бачыў кампутар навука ў фоне. -Мы Атрымалі нашы шпіёны там. -OK, Давайце спытаем адрозніваецца пытанне інтэрв'ю. [END ВИДЕОВОСПРОИЗВЕДЕНИЕ] СПІКЕР: Так казаць пра канкрэтныя лічбы, хоць, не збіраецца быць усё, што карысна. Гэта не ўрок жыцця, што бурбалка сартаваць, улічваючы мільён уваходаў, можа заняць цэлых 500 мільярдаў крокаў. Вы не можаце сапраўды абагульніць занадта эфектыўна ад і прымаць правільныя рашэнні дызайну пры напісанні праграм. Так што давайце хоць засяродзіцца на тым, мы маглі б спрасціць гэты вынік. Так што я выдзелены жоўтым колерам тут Вынікам п падзеленае на квадрат 2, так млн квадрат падзеленае на 2, а затым Я вылучыў тое, што Канчатковы адказ быў як толькі мы адымаецца ад п падзеленае на лік 2. І прэтэнзіі я збіраюся зрабіць цяпер, хто, чорт вазьмі клапоціцца калі адняць ад трохі стары п над 2, калі першы частка гэтай формулы з'яўляецца нашмат больш? Гэта дамінуе над іншым Тэрмін, н квадрат падзелены на 2 так нашмат больш, ясна, як н становіцца вялікім, як мільён, што ёсць на самой справе вялікая розніца ў канец дня паміж 500000000000 і 499.999.500.000? Не зусім. І так, што мы збіраемся рабіць, як кампутарнікі з'яўляецца ігнараваць гэтыя малодшыя члены і прыняць тое, як гэта і сапраўды толькі спрасціць яго, каб тэрмін, які адбываецца з матэрыяй. Чым больш нашы наборы дадзеных атрымаць, тым больш нашы базы дадзеных атрымаць, тым больш вэб-старонак мы павінны шукаць, тым больш Сябры ў вас ёсць на Facebook. Як н становіцца больш, мы сапраўды будзе клапаціцца аб велічыні Тэрмiн у любым такім аналізе наш выступ алгарытмы. І я збіраюся сказаць, вы ведаеце, што, пузырьковый сартавання парадку вялікага O, парадку п квадрат. Гэта не зусім н квадрат, як мы бачылі, але хто сапраўды клапоціцца аб тых невялікіх кропкі, і, шчыра кажучы, хто на самай справе розніца, калі мы дзелім на 2? Вось толькі пастаянным фактарам. І гэта 500 мільярдаў супраць 250 млрд сапраўды, што вялікую справу? Я мог бы проста чакаць адзін год, хай мой ноўтбук літаральна атрымаць у два разы хутчэй у апаратных сродках, і такога роду адрозненні проста сыходзіць натуральным цягам часу. Тое, што мы клапоцімся пра тое, выраз, частка выразы, што будзе мяняцца ў залежнасці як наш ўклад становіцца больш і больш. І на самай справе, у рэальным свеце, гэта тое, што ўсё больш адбываецца з'яўляецца укладам у нашы праблемы і алгарытмы становяцца ўсё больш. Настолькі вялікі O будзе абазначэнне, асімптатычнага абазначэнне, што мы проста выкарыстоўваць як кампутарныя спецыялісты, каб апісаць прадукцыйнасць, або час працы, алгарытму. Так што мы можам параўнаць алгарытмы на розных кампутарах, напісаных рознымі людзьмі, з дапамогай некаторыя прынцыпова падобныя метрыка як лікі параўнанняў вы рашэнняў, або, можа быць, колькасць свопов вы робіце. Тое, што мы не збіраемся колькасць ўяўляе сабой колькасць часу , Які праходзіць па гадзінах на сцяне звычайна. Тое, што мы не збіраемся турбавацца пра тое, колькі памяці вы карыстаецеся сёння на меры, хоць гэта яшчэ адзін рэсурс, мы маглі б вымераць. Мы збіраемся, каб паспрабаваць засноўваць нашы аналізы на толькі асноўныя аперацыі, тыя, шчыра кажучы, што вы можаце бачыць найбольш візуальна. Так што нешта накшталт вялікай O п квадрат, я сцвярджаю, што O н квадрат з'яўляецца верхняй мяжой на так званы час працы ў пузырьковый сартавання. Іншымі словамі, калі вас хацеў сцвярджаць, што ёсць гэта верхні мяжа таго, колькі крокі алгарытму можа заняць, гэта будзе ў вялікі O п квадрат у гэтым выпадку верхняя мяжа. Што рабіць, калі я замест змяніць гісторыя была не пра пузырьковый сартавання, але пра гэта верхняя мяжа. Ці можаце вы назваць алгарытмам што мы глядзелі на ўжо чыя верхняя мяжа, максімум вымярэння часу або аперацый, будзе называецца абмежаваным, па п, лінейнай функцыяй, ня квадратычнай, вось выгнутыя? Што сабой алгарытм, які заўсёды займае не больш за чым як п крокаў, або 2n крокаў, або крокі 3n? Так? АЎДЫТОРЫЯ: Пошук Найбольшая колькасць у спісе? СПІКЕР: Цалкам, знаходзячы Найбольшая колькасць у спісе. Калі мне дадуць спіс людзі напрыклад, кожны з які трымае шэраг, што гэта максімальны лік крокаў ён павінен узяць мяне, разумна разумны чалавек, знайсці найбольшую чалавека ў гэтым спісе? п, ці не так? Таму што ў горшым выпадку, дзе можа самая вялікая каштоўнасць быць? Права, усю дарогу ў канцы. Такім чынам, у горшым выпадку Верхняя мяжа, я мог бы павінны прайсці ўвесь шлях тут і сказаць: ой, вось нумар восем, ці што гэта значэнне. Цяпер было б зусім недарэчна калі я працягваў ісці, ці не так? Гледзячы на ​​ўсё больш і больш элементаў калі апошні з іх знаходзіцца там? Так, вядома ,, п з'яўляецца верхняй мяжой. Мне не трэба, каб узяць больш крокаў, чым гэта. Так што, калі замест гэтага я прапанаваў, каб Ёсць алгарытмы ў гэтым свеце, што ёсць час, бегаючы Гэта абмежаваная вялікім O з часопіса п, увайдзіце н? Дзе мы бачылі гэтага раней? Так? АЎДЫТОРЫЯ: У задачы тэлефоннай кнігі? СПІКЕР: Як праблемы тэлефоннай кнігі. Тое, што было паказчыкам таго, наколькі колькі часу ці колькі слёз IT узяў мяне, каб знайсці такога чалавека, як Майк Сміт у тэлефоннай кнізе? Мы сцвярджалі, што гэта быў часопіс п, і нават калі не знаёмыя ці гэта трохі туманна, што лагарыфм ці паказчык быў, толькі памятайце, што § п як правіла, адносіцца да працэсу, У гэтым выпадку дзялення то ў палове зноў, і зноў, і зноў, і зноў, так што ён атрымлівае ўсё менш і менш, як і вы, што. Так увайсці н тычыцца, вядома, да прыкладу тэлефоннай кнігі, каб бінарнага пошуку ў тэорыі, калі мы былі віртуальныя дзверы на борце, ці калі Шон быў пошуках чагосьці. Калі ён выкарыстоўваецца бінарны пошук, увайдзіце н будзе верхняя мяжа, колькі час, якое патрабуецца. Але гэтыя алгарытмы, якія беглі ў § п мяркуецца, якія ключавыя дэталі? Гэта спіс быў адсартаваны, ці не так? Ваш алгарытм памыляецца, калі ваш ўклад не сартуецца, і яшчэ вы карыстаецеся нешта накшталт бінарнага пошуку таму што вы можаце скакаць прама над элементам , Не разумеючы, што гэта сапраўды ёсць. Цяпер, што гэта можа азначаць, Big O аднаго? Гэта не азначае, што ваш алгарытм займае адзін і толькі адзін крок, гэта проста азначае, што патрабуецца пастаяннае лік крокаў. Можа быць, гэта 1, можа быць, гэта 10, можа быць, гэта 1000, але гэта залежыць ад памер праблемы. Незалежна ад таго, наколькі вялікі п, пастаянная алгарытм час заўсёды мае тое ж самае лік крокаў. Так што можа быць алгарытм мы гаварылі пра ці проста інтуітыўна, што прыходзіць да вас, што заўсёды працуе ў так званай сталай часу? Так? АЎДЫТОРЫЯ: Дадаць два ліку. СПІКЕР: Дадаць два ліку, 2 плюс 2 раўняецца 4, зроблена. Так што можа працаваць, што яшчэ? Як наконт больш рэальным свеце, так? АЎДЫТОРЫЯ: Пошук Першае, што ў спісе. СПІКЕР: Пошук першым элемент у спісе, вядома. Мы на самой справе казаў аб масівах ўжо, як вы атрымаеце на Першы элемент у масіве, незалежна ад таго, як доўга масіў на З? Вы проста выкарыстоўваць як кранштэйны нулявы абазначэння, бац, ты там. І сапраўды масівы, як у бок, падтрымка-то вядома як выпадковага доступу, выпадковага доступу памяці, таму што вы можаце літаральна перайсці ў любы адным месцы. Мы можам зрабіць гэта яшчэ прасцей мы можам перамясціцца да нулявы тыдні калі мы зрабілі нуля. Колькі часу спатрэбіцца для кажуць блок у пустым выканаць? Проста сталая часу, ці не так? Скажы што-небудзь, скажам тое, гэта не мае значэння як вялікія драпіны свет, гэта заўсёды збіраецца ўзяць такое ж колькасць часу проста сказаць-то. Дык вось пастаянная часу, але тое, што адваротны бок? Калі б гэта было верхняя мяжы, што, калі мы хочам для апісання ніжнія мяжы нашых алгарытмаў час працы? Амаль лепшым выпадку патэнцыйна, калі хочаце, хоць гэтыя тэрміны можна прымяніць да лепшых Выпадкі, горшых выпадках сярэднія выпадкі больш наогул, але давайце проста засяродзіцца на ніжніх межаў у цэлым. Што сабой алгарытм, які мае ніжняя мяжа п крокаў, або 2n крокаў, або крокі 3n? Некаторыя фактар ​​п крокаў, вось яго ніжняй мяжы. Так? АЎДЫТОРЫЯ: Bubble роду? СПІКЕР: Bubble роду бярэ Вы мінімальна п крокаў, то чаму? Чаму гэта? Чаму, што пачатак прыходзіць да вас інтуітыўна, нават калі гэта не так проста яшчэ? Так? АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР: Дакладна. У лепшым сцэнары пузырьковый сартавання, і шмат алгарытмаў калі я ўручаю вам восем чалавек якія ўжо адсартаваныя, было б глупства для вас, алгарытм, каб ісці наперад і назад больш чым адзін раз, ці не так? Таму што як толькі вы хадзіць па спісе адзін раз, вы павінны разумець, пра, я зрабіў няма свопы, гэты спіс сартуецца, выхад. Але што адбываецца, каб у вас н крокі. І наадварот, тое, што яшчэ адзін спосаб думаць пра гэта? Bubble роду з'яўляецца амега, так бы мовіць, з п, таму што калі вы паглядзіце на менш, чым п элементаў, тое, што фундаментальны пытанне ёсць? Вы не ведаеце, калі гэта сартуюцца, права. Мы людзі маглі погляд на васьмі людзі і быць як, о, гэта сартуецца, што мяне не ўзялі н крокі, але гэта зрабіў. Твае вочы, хоць вас выгляд ад таго, маюць вялікае поле зроку, Вы глядзелі на васьмі элементаў, Вы глядзелі на восем чалавек, вось восем крокаў эфектыўна. І толькі тады, калі я іду праз увесь Спіс я разумею, так, Сартаваць. Калі я спыняцца на паўдарозе думаць, усё Права, гэта даволі сартуюцца да гэтага часу, якія шанцы, што гэта не Пачынаючы? Што алгарытмы не будзе правільным. Можа быць хутчэй, але няправільна. Так што цяпер у нас ёсць спосаб апісання ніжнія мяжы, і тое, што аб пастаянным часу? Што сабой алгарытм, які мае больш нізкі абмежаванне на час яго працы аднаго? 1 крок, 2 кроку, 10 крокаў, але сталым, залежыць ад п, памер ўваходу? Так, у спіну. АЎДЫТОРЫЯ: Printf? СПІКЕР: Што гэта? АЎДЫТОРЫЯ: Printf? СПІКЕР: Printf. ОК, упэўнены. Такім чынам, гэта займае фіксаваны лік крокаў. І я павінен now-- цяпер, мы кажам пра C кода а не да драпін, то як скажам, з Printf, мы павінны пачаць, каб атрымаць асцярожным. Паколькі Е сапраўды бярэ ўваход, гэта радок, і струны ў тэхнічна маюць даўжыню. Так што, калі мы зараз хочам, каб забраць на вас, калі вы не пярэчыце, тэхнічна мы маглі сцвярджаць, што Printf сапраўды бярэ зменную даўжыню уваходнай, і, вядома, гэта можа заняць больш Час надрукаваць радок так доўга, чым так доўга. Так што, калі мы разглядаем толькі сартаванне і пошук прыкладаў? Як наконт Майка Сміта ў тэлефоне Кніга, або бінарны пошук у больш агульным? У лепшым выпадку, што можа здарыцца? Я адкрываю тэлефонную кнігу і, бац, ёсць лік Майка Сміта. Я магу патэлефанаваць яму прама цяпер. Узяў адзін крок, можа быць, два крокі, але пастаяннае лік крокаў калі мне пашанцавала. І, шчыра кажучы, мы бачылі на Панядзелак ваш аднакласнік атрымаць вельмі пашанцавала два разы запар. І гэта было сапраўды пастаяннай час у ніжніх межаў ад алгарытму ў пытанні знаходжання лік 50 за тых, зачынены дзверы. Зараз, як у бок, калі вы выявіце, што і вялікая O, верхняя мяжа, і амега, ніжняя мяжа, адзін у тым жа, што з'яўляецца тая ж формула ў дужкі, вы таксама можаце сказаць, проста быць незвычайным, што-то не ў тэта н або тэта некаторага іншага значэння. Гэта проста азначае, калі большая Высновы і амега аднолькавыя. Цяпер наконт выбару роду? Давайце выкарыстоўваць гэты новы слоўнік. У селекцыі роду, тое, што мы былі рабіць зноў, і зноў, і зноў? Я збіраўся туды і назад праз спіс, шукае каго? Найменшая колькасць. Так як шмат крокаў, як шмат параўнанняў я таксама павінны зрабіць для таго, каб высветліць, хто найменшы элемент у спісе быў? н мінус 1, ці не так? Таму што, калі я проста пачаць з таго, што я знаходжуся улічваючы і я пачынаю параўноўваць яго ці яе, то яму ці ёй, як ён ці ёй, яму ці ёй, я можа толькі пару элементаў разам н мінус 1 раз. Так выбар роду ж бярэ н мінус 1 крокі ў першы раз. Колькі крокаў трэба, каб я знайсці другі найменшы элемент? н мінус 2, таму што я нямы калі я працягваю глядзець на тыя ж людзі, зноў, калі я ўжо выбралі яго або яе і пакласці іх на месца. І трэці крок, н мінус 3, то п мінус 4. Мы бачылі гэтую мадэль раней, і на самай справе Выбар роду аналагічна мае верхнюю мяжу н квадрат, калі мы робім да, што сумаванне. Якая яго ніжняй мяжы, выбар роду? Мінімальна, колькі часу адбору павінны Сартаваць прыняць, як мы вызначылі яго ў панядзелак? Прапаную два варыянты. Можа быць, гэта п, як і раней. Можа быць, гэта н квадрат, як гэта Цяпер як верхняя грань. АЎДЫТОРЫЯ: н квадрат. СПІКЕР: н квадрат. Чаму? АЎДЫТОРЫЯ: Таму што ў вас ёсць вызначыць [неразборліва]. СПІКЕР: Дакладна. Па крайняй меры, як я вызначыў выбар роду гэта было даволі наіўна, працягваць ісці, знайсці найменшы элемент. Ідзеце зноў, знайсці найменшы элемент. Ідзеце зноў, знайсці найменшы элемент. Там няма роду аптымізацыя ў там, што можа дазвольце мне перапыніць пасля усяго п або каля крокі. Так сапраўды, выбар сартаваць, амега п квадрат. Як наконт сартаванне ўстаўкамі, дзе я ўзяў якія мне далі, і тады я пляснуўся яго ці яе ў патрэбным месцы? Тады я працягнуў другога чалавека, пляснуўся яго ці яе ў патрэбным месцы. Тады наступны чалавек, пляснуўся яму ці ёй у патрэбным месцы. Звярніце ўвагу, што гэта вельмі лінейны, так бы мовіць. Я прамой, я не ходзіць туды-сюды, Я ніколі не аглядаючыся назад сапраўды, але што адбываецца, калі я ўстаўляю яго ці ёй у пачатку Спіс, як мы зрабілі ў панядзелак? Што адбываецца? Так? АЎДЫТОРЫЯ: [неразборліва]. СПІКЕР: Так, была загвоздка, ці не так? Вы можаце ўспомніць з Вашы аднакласнікі, калі яны рабілі любы рух з іх ногі, што была аперацыя. Так што, калі было тры чалавекі, тут і новы чалавек належаў спосаб там, на доўгі этап, як гэта, упэўнены, ён або яна можа проста пайсці да самага канца. Але калі мы думаем пра Кампутар і масіў памяці, гэтыя людзі збіраюцца прыйдзецца ператасаваць над каб вызваліць месца для гэтага чалавека. І так, што п мінус 1 shufflings, н мінус 2 shufflings, п мінус 3 shufflings з'яўляецца толькі збольшага адбываецца ззаду мяне, не перада мной як і раней, у пэўным сэнсе. Зараз, як у бок, і, як Вы, магчыма, бачылі онлайн калі вы пачынаеце калупацца аб віды, ёсць так шмат розных тыя, там, некаторыя з іх лепш, чым іншыя. Сапраўды, bogosort з'яўляецца адным што пацешна глядзець ўверх. Bogosort прымае набор лічбы ці сказаць калоду карт, Змяшайце выпадковым іх, і правярае, калі яны адсартаваныя. А калі не, робіць гэта зноў. А калі не, робіць гэта зноў. Калі не, робіць гэта зноў. Неверагодна дурное. І на самай справе, калі вы чытаеце як артыкулы Вікіпедыі, яго мянушка-дурному роду. Гэта ў канчатковым рахунку спрацуе, спадзяюся, дастаткова часу, але гэта колькасць часу можа заняць даволі шмат часу. Так што, калі я мог, давайце паскорыць рэчаў у параўнанні з, напрыклад Мэры Бэт раней, маючы яшчэ некалькі элементаў, але больш за двух працэсараў. Два чалавекі, калі вам быў бы не супраць далучыцца да мяне. Як наконт 1 тут, і давайце не go-- нікога, вунь там? Ніхто не там? Добра. Вы з чорнымі кашуля, так, давай ўніз. Добра, як цябе завуць? АЎДЫТОРЫЯ: Піцер. СПІКЕР: Што гэта? АЎДЫТОРЫЯ: Піцер. СПІКЕР: Піцер, Дэвід, прыемна пазнаёміцца. Добра, у нас ёсць Пётр тут, калі вам хачу прыехаць на стол тут. І як цябе завуць? АЎДЫТОРЫЯ: Алена. СПІКЕР: Алена. ОК, прыемна пазнаёміцца. Алена сустрэнеце Піцера. Піцер, Алена. І мы павінны Эндру тут таксама, калі ласка. І ваша задача будзе быць адсартаваць калоду карт. І калі не знаёмыя, палуба карт павінны ў канчатковым рахунку, быць адсартаваныя сёе як гэта дзе мы зробім клубы, то рыдлёўкі, то сэрца і брыльянты, ад туза як адзін, усё, аж да караля. Карты я збіраюся даць вам збіраюцца быць 52 у колькасці. Мы збіраемся аналагічным Час у вас, праз хвіліну. Мы збіраемся кінуць Эндру на экране тут, такім чынам, каб глядзець, як вы робіце гэта. І такім чынам, што ўсё гэта тым больш відаць, гэта карты, якія я атрымаў на Амазонцы. Так яны ўжо выпадкова сартуюцца, і мы збіраемся раз, калі вы. І мы збіраемся трымаць яго рэальнай на гэты раз, так што мы збіраемся паспрабаваць аказаць ціск на вас таму што інакш гэта будзе атрымаць стомна хутка. Калі б вы маглі прыступіць да адсартаваць 52 элементы разам праз некаторыя сродкі, цяпер. І зноў, як мы глядзім гэтыя хлопцы робяць тое, што, у рэшце рэшт, будзе вырабляць відавочна Вынік, думаю, пра сапраўды як яны кожны робіць гэта, як Вы маглі б апісаць яго. Таму што зноў жа, гэта усе працэсы, алгарытмы што мы лічым само сабой якія разумеюцца, як чалавек. Але вы, напэўна, даўно інтуіцыя, задоўга да вас, нават думаў аб узяцці інфарматыка клас вам магчыма, мелі інтуіцыю з якія вырашыць падобныя праблемы. Але як толькі вы прызнаеце патэрны і пачаць фармалізаваць дзеянні, з дапамогай якіх вы вырашаеце гэтыя праблемы, Вы знойдзеце, што вы можаце вырашыць шмат больш цікавым і значна складаней праблемы хутка. Дык хто з гледачоў, што з'яўляецца па меншай меры, адзін элемент алгарытму што яны выкарыстоўваюць тут? АЎДЫТОРЫЯ: [неразборліва] СПІКЕР: Што гэта? АЎДЫТОРЫЯ: Па касцюме. СПІКЕР: Па касцюме. Такім чынам, спачатку яны кластарызацыі усе алмазы разам па-відаць, усё сэрца разам падобна, і гэтак далей, без выканання для лікаў на картах. І цяпер яны з'яўляюцца, напрыклад, каб быць іх сартаванне па нумары. Вельмі добра. Добра, так што будзе быць апошнім крокам, то тут? Пасля таго, як у нас ёсць чатыры адсартаваныя касцюмы, што нам трэба зрабіць, каб чатырох паль для дасягнення адной сартуюцца палубу, дастаткова проста? Так што мы павінны аб'яднаць іх зноў. Такім чынам, ёсць цікавая ідэя, што зноў, мяркую, вельмі зразумелы нават калі вы ніколі б не ўдарыў што выгляд этыкеткі на ім. Гэта фундаментальнае паняцце дзялення праблема не ў палову гэтага часу, але па меншай меры на чатыры часткі. Рашэнне ў значнай ступені прынцыпова ідэнтычныя праблемы ізалявана адзін ад аднаго, , А затым аб'яднаць вынікі. І, выдатна, зроблена. Добра, вялікая круглая апладысментаў, калі мы маглі. [Апладысменты] СПІКЕР: Я паняцця не маю, што вы будзеце рабіць з імі, але тут вы ідзяце. Дзякуй вялікі. Такім чынам, давайце паглядзім, дзве хвіліны і восем секунд, калі вы хочаце, каб пазмагацца са сваімі сябрамі. Што ж тады будзе быць адняць ад гэтага што мы можам выкарыстоўваць больш агульным? Ну, думаю, назад у Гэты масіў лікаў, і ўспамінаю цяпер, каб некаторыя з псевдокод мы напісалі ў мінулым, і гэта было каманд для вырашэнні праблемы тэлефоннай кнігі. Прычым у псевдокода I пералічыў больш метадычную шлях апісання таго, як я зрабіў вельмі інтуітыўны чалавек алгарытм дзялення тэлефон Кніга ў палове, паўторыце, паўтараю, паўтараю, пакуль я не знайду такі чалавек, як Майк Сміт, калі ён сапраўды знаходзіцца ў тэлефоннай кнізе. Але я збольшага прывык, што я называю вельмі итеративный падыход тут, у прыватнасці апавяшчэння лінія 8 і радок 11. Тыя, з'яўляюцца сведчаннем итеративный падыход, перакручванне падыход, таму што гэта менавіта паводзіны яны выклікаюць. Гэтыя лініі як бы, ідуць у Лінія тры, і вы можаце роду думаць пра тое, што ў вашым разумовым поглядам як пятля. Гэта кажу вам, каб вярнуцца да кроку тры і паўтараю, зноў, і зноў, і зноў. Але што, калі мы выкарыстоўваць ключавую ідэю тут, што мы зрабілі не ў апошні раз, і спрасціць лініі 8 і радок 11 і іх суседзі як толькі гэта, у жоўты колер. Гэта не прынцыпова скарачэння псевдокод вельмі шмат, але гэта ў корані мяняе прырода майго алгарытму. Тое, што я зараз кажу у пункце 7, на этапе 10, з'яўляецца пошук Mike у тым жа чынам, але толькі ў левай палова ці правая палова. Такім чынам, іншымі словамі, калі Я пачынаю з крокам адзін, падабраць тэлефонную кнігу, адкрыты да сярэдзіны з тэлефоннай кнігі, паглядзець на імёны, калі Сміт з'яўляецца адным клічуць, тэлефануйце Майк, яшчэ калі Сміт раней у кнізе, крок сем шукаць Майка ў левай палове кнігі. Але што гэта за пачуццё, гэта пакінуўшы мяне вісіць, ці не так? У жоўты, з'яўляецца інструкцыя, але як я магу шукаць Майка у левай палова тэлефоннай кнізе? Дзе я павінен Алгарытм, з якой я можа шукаць такога чалавека, як Майк Сміт? Ну, гэта гледзячы нам у вочы. Я магу літаральна выкарыстоўваць сапраўды такі ж Праграма эфектыўна, падышоўшы да верхняй зноў і зноў працуе тыя ж радкі кода. Такім чынам, нават пры тым, што гэта павінна адчуваць сябе як трохі цыклічнага вызначэння дзе вы адказваючы хто- Пытанне па толькі выгляд з просьбай тое ж пытанне зноў, як, чаму, чаму, чаму? Рэальнасць такая, таму што мы жорстка пару спецыяльных ліній, крок 4, што, калі, і крок 12, якія эфектыўна іншая галіна, таму што ў нас гэтыя меры па ліквідацыі вузкіх, гэты алгарытм будзе спыненая, калі мы знайсці Майка, або калі мы не робім. Але ў кроку 7 і 10 зараз, у нас ёсць што мы будзем называць рэкурсіўны алгарытм. І Рэкурсія сапраўды магутная ідэя гэта крыху ашаламляльныя спачатку, што зараз мы можам прымяніць наступным чынам. Зліццё роду будзе апошнім выглядам, які мы глядзім на, па меншай меры, у класе фармальна. І гэта ў корані адрозніваецца ад тых трох апошніх, і, вядома, Апошнія чатыры, калі мы ўключым bogosort. Вось псевдокод для сартавання зліццём. Калі на ўваходзе п элементаў, таму, улічваючы, масіў памеру N, калі N менш 2, вярнуцца. Дык чаму ж я, што здаровае праверыць у першую чаргу? Што маецца на ўвазе калі аддам цябе масіў, даўжыня якога н менш 2? Гэта ўжо адсартаваныя, відавочна, ці не так? Паколькі спіс альбо мае адзін элемент, які з'яўляецца трывіяльным сартуюцца, таму што гэта Адзінае, што ёсць. Або, гэта з нулявога памеру, што азначае няма нічога, каб разабрацца, так па сваёй прыродзе сартуецца. Там проста нічога дрэннага там. Дык вось наша так званая базавы варыянт. Гэта значыць блізкі па духу да таго, што мы зрабілі з Майкам. Калі Майк ў тэлефоннай кнізе, патэлефануеце яму. Калі яго там няма, здавацца. Гэта так званы базавы варыянт, каб пераканацца Гэты алгарытм ў канцы дня спыніцца ў пэўных абставінах. Але вось скачок веры цяпер, інакш, сартаваць левую палову элементаў, затым адсартаваць права палова элементаў, а затым аб'яднаць адсартаваныя палоўкі. І вось, калі ён адчувае сябе як мы Copping з. Я папрасіў вас разабрацца п элементаў, і я кажучы, добра, зрабіце гэта з дапамогай сартавання налева і сартавання права. Але я кажу адно Іншая справа, і гэта з'яўляецца ключавой тэмай здаецца у інтуіцыі да гэтага часу, ёсць гэты трэці этап зліцця. Які хоць яго здаецца настолькі дурны ў духу, як толькі аб'яднаць рэчы разам, здаецца, з'яўляецца ключавым крокам на шляху зборка з двух праблем, якія у канчатковым рахунку, былі падзеленыя на дзве часткі. Так сартавання зліццём, давайце зробім гэта, калі вы будзеце гумар мяне, яшчэ адным дэманстрацыі, проста так, што ў нас ёсць некаторыя Нумары працаваць. Ці магу я абмяняць восем стрэс мячы для васьмі чалавек? Добра, а як наконт вас тры, вы чатыры у гэтым раздзеле, пяць, шэсць, і давайце у 7, 8, давай до. ОК, ды ОК. Мінус 8, там мы ідзем, плюс 1. Выдатна. Добра давай, давайце хутка даць вам лічбы. Нумар два, нумар тры, нумар чатыры, нумар пяць, шэсць, сем, восем. Я правільна зрабіў восем на гэты раз. ОК, так што ісці наперад, калі б мог, і давайце сартаваць ў першапачатковым парадку што мы павінны былі ўчора які выглядаў як гэта, калі вы не пярэчыце. І давайце зробім гэта перад сталом. Добра, так сартавання зліццём. Гэта дзе гэта адбываецца каб атрымаць від цікавага, таму што я, здаецца, даючы сябе столькі менш інфармацыі сёння. Так сартаванне зліццём у першую чаргу на ўваходзе п элементаў, і, відавочна, не менш за два, гэта восем, так што я яшчэ крыху папрацаваць. Так што цяпер у думках мы як клас цяпер у яшчэ галіны, што азначае тры крокі. Па-першае, у мяне ёсць для сартавання Левая палова элементаў. Так як жа я ісці пра гэта? Ну, я збіраюся выгляд думках падзяліць спіс тут, Вы не павінны фізічна рухацца, і я збіраюся засяродзіцца толькі на Левая палова элементаў тут. Так як я магу ісці аб сартаванні Спіс зараз памеру чатыры? Што мой алгарытм? Спачатку я праверыць гэта н менш двух, няма, так што я прыступіць да яшчэ блок зноў. Сартаваць пакінуў палову элементаў. Так што цяпер зноў, у думках, і гэта, калі Вы павінны налічвацца шмат псіхічнае гісторыя, калі вы будзеце. Цяпер я сартаванні левую палова левай палове. Добра, так што цяпер я называю жа зліццё алгарытм сартавання, з'яўляецца н менш за два? Не, гэта два, так што я павінен разабрацца левая палова, а правая палова. Таму тут мы ідзем, сартаваць левую палову. Чаму б вам проста не зрабіце адзін крок наперад. Як цябе завуць? АЎДЫТОРЫЯ: Дарэн. СПІКЕР: Дэн. Дэн выйшаў наперад. АЎДЫТОРЫЯ: Дарэн. , Зроблена Дарэн: СПІКЕР. Вы сказалі Дарэн або Дэн? АЎДЫТОРЫЯ: Дарэн. СПІКЕР: Дарэн. ОК, Дарэн актывізаваў наперад, і ён цяпер сартуецца. І гэта амаль бессэнсоўным патрабаванне, ці не так? Я сапраўды не здаецца, дасягненні нічога, але давайце пяройдзем. Цяпер дазвольце мне разабрацца права палова элементаў. Як цябе завуць? АЎДЫТОРЫЯ: Люк. СПІКЕР: Люк. Давай, крок наперад. Страты, я сартуюцца Лукі. Левая палова цяпер сартуецца і правая палова цяпер сартуецца, але зноў жа, ёсць ключавы крок тут. Што мне ў наступным трэба зрабіць? Зліццё адсартаваныя палоўкі. Цяпер мы збіраемся проста усё назад і наперад на гэтым шляху, таму што я накшталт трэба некаторыя працоўная прастора. Гэта амаль як яны хлопцы на стале, і мне патрэбна пакой перамяшчаць іх на. Так што я збіраюся аб'яднаць вы, хлопцы, паглядзеўшы на левай палове і ў правай палове. І які, відавочна, стаіць на першым месцы, левая палова ці правая палова? Так правая палова, так што давайце рухацца Лукі над тут у зыходнае становішча Дарэна. І зараз, каб аб'яднаць іх левую палову ў, Дарэн збіраецца рухацца прама там. Так адчувае сябе амаль пузырьковый сартавання эфект, але маё фундаментальнае алгарытм, вельмі розныя на гэты раз. Але цяпер, дзе рэчы становяцца крыху раздражняе, таму што вас павінны пераматаць разумова адкуль я спыніўся. Я толькі што зліў адсартаваныя палоўкі, які азначае, што я, дзе ў маім алгарытме? Я павінен разабрацца правую палову, ці не так? Калі вы пераматаць, літаральна на відэа, вы будзеце бачыць, што мы дабраліся да гэтага кропка Лукі і Дарэнам шляхам сартавання левы палова левай палове. Тады мы аб'ядналі тыя, адсартаваныя палоўкі, якія азначае наступны крок з'яўляецца свайго роду Правая палова левай палове. Добра, так што давайце зрабіць гэта хутчэй. Добра, шэсць, я збіраюся сцвярджаць, Вы зараз сартуюцца, давай наперад. Як цябе завуць? АЎДЫТОРЫЯ: Адрыяна. СПІКЕР: Адрыяна. Адрыяна цяпер сартуецца. І як цябе завуць? АЎДЫТОРЫЯ: Алекс. СПІКЕР: Алекс цяпер сартуецца. Левая палова, правая палова, што апошні крок? Зліццё. Даволі трывіяльна, так што я збіраецца аб'яднаць у шэсць, зрабіць крок назад, восем, зрабіць крок назад. А цяпер звярніце ўвагу, гэта карысна вынас, што Зараз праўда пра левай палове Спіс, незалежна ад таго, як мы пачалі? Гэта сартуецца. Зараз гэта не размеркаваны ў вялікі схеме рэчаў, але гэта сартуецца незалежна адзін ад аднаго з другой паловы. Цяпер тое, што крок я на, калі я працягну перамоткі, як гісторыя пачалася? Цяпер у мяне ёсць для сартавання правую палову. Так што цяпер мы шлях таму ў пачатак гісторыі, і давайце зробім гэта хутчэй. Так што я збіраюся разабрацца Правая палова ўсяго спісу. Які наступны крок? Сартаваць левую палову правай палове. Сартаваць левую палову Левая палова правай палове. І як цябе завуць? АЎДЫТОРЫЯ: Амар. СПІКЕР: Амар, крок наперад, зрабіць. Левая палова сартуецца. І як цябе завуць? АЎДЫТОРЫЯ: Крыс. СПІКЕР: Крыс, зрабіць крок наперад, вы зараз сартуюцца. Што ключавы крок цяпер? Зліццё. Так ніхто не збіраецца злівацца ў месцы тут, калі б вы маглі зрабіць крок назад, і тры збіраецца зрабіць крок назад, зліваюцца. Так левая палова Правая палова, цяпер сартуецца. Шчыра кажучы, гэты алгарытм адчувае, як мы марнуеце нашмат больш часу, чым раней, але калі б мы зрабілі гэта ў рэжыме рэальнага часу, мы будзем бачыць тое, што ежы на дом будзе. Такім чынам, я тут, прама палова правай палове, дазвольце мне ісці наперад і адсартаваць левую палову. Крок наперад, як цябе завуць? АЎДЫТОРЫЯ: Рэмсі. СПІКЕР: Рэмсі цяпер сартуецца. Як цябе завуць? АЎДЫТОРЫЯ: Марына. СПІКЕР: Марына цяпер сартуецца як добра, калі вы бераце адзін крок наперад. Ключ крок тут цяпер зліваюцца, я збіраецца зрываць з маіх двух спісаў, злева і справа. Пяць прыйдзе першым, і сем прыйдзе наступны. І зноў жа, гэта не выпадкова. Той факт, што яны бяруць крокі наперад і назад прызначана для прадстаўлення, што мы не можам зрабіць гэты алгарытм на месцы, як лёгка як пузырьковый сартавання і адбору роду, і сартаванне ўстаўкамі, дзе мы проста захоўваецца замены людзей. Я літаральна трэба свайго роду з паперы для нататак, у якіх паставіць гэтых людзей у той час як я раблю зліццё, і тады я магу пакласці іх на месца. І гэта ключавы момант, таму я выкарыстоўваю Новы рэсурс, прастора, не толькі час. ОК, гэта дзіўна. Левая палова сартуецца, правай палове адсартаваны, зараз, калі ключ зліцця крок. Як я буду аб'яднаць гэта? Так што калі вы будзеце прытрымлівацца маім левая рука і правая рука, Я збіраюся паказаць левую руку у левай палове, мая правая рука ў правай палове, і цяпер я павінен вырашыць, крок за крокам, якога да зьліцьця ст. Хто відавочна на першым месцы? Нумар адзін. Так ідзі сюды, вось наш сверхоперативной. Так што цяпер нумар адзін, і апавяшчэнне што я буду рабіць са сваёй правай рукой, Я збіраюся рухаць правай рукой адзін пераступіць пазначыць нумар тры, і цяпер я павінен зрабіць тое ж самае рашэнне. А на самай справе каштуюць правы ў Фронт Лукі тут, калі б вы маглі, таму што гэта наш сверхоперативной. Дык хто ж далей? У нас ёсць Лукі з нумар два або Крыс з нумарам тры. Відавочна Лукі, лік два, так што вы прыйшлі сюды. Але мая левая рука цяпер збіраецца быць павялічана, каб паказаць на Дарэна, і вось ключ забраць з зліцця, я збіраюся працягваць гэта рабіць, відавочна, калі вас выгляд з прытрымлівацца логіцы. Але мае рукі ніколі не збіраецца ісці ў адваротным кірунку, які азначае, што я толькі калі пераход да злева, з майго працэсу зліцця, і што будзе ключом да наш аналіз праз хвіліну. А цяпер давайце скончыць гэта хутка. Так тры будзе далей, затым чатыры будзе далей, і цяпер пяць будзе далей, то шэсць, і сем, і, нарэшце, восем. Па адчуваннях самага павольнага алгарытму пакуль няма, але не, калі мы на самай справе запусціць яго на такі ж тактавай частоты, такім чынам, каб кажуць, з тым жа цікаюць гадзіны, як і раней. Чаму? Ну, давайце паглядзець на канчатковы вынік. Давайце вернемся сюды, хай мяне падцягнуць дэманстрацыю візуальна аб тым, што мы толькі што зрабілі. Маштабаванне тут, на гэтым старонка тут, распавядаючы Firefox што мы хочам стаяць у чарзе ў гэтай рамкі, давайце сказаць пузырьковую сартаванне, з якой мы зараз добра знаёмыя, Выбар роду, што з'яўляецца яшчэ адным даволі проста адзін, і цяпер сённяшняя сартаванне зліццём, якая будзе нашым кліматычныя канчатак. Прычына гэта заняло так шмат больш тут з людзьмі і мне вусна гэта, Відавочна, я тлумачу кожны крок. Але калі вы проста выканаць гэта, значна як мы рабілі пузырьковый сартавання і выбару сартавання не толькі візуальна, гадзіны наколькі больш эфектыўна гэта ўцягванне ў працу падзел і заваёва можа быць пры ўжыванні да набору дадзеных, гэта нават не памер восем, але нават шмат, нашмат больш. Я даю вам сартаванне зліццём, бок аб баку з гэтымі іншымі алгарытмамі. Гэта будзе атрымаць балюча хутка, і канцоўка ня асабліва кліматычныя, яны проста ў канчатковым выніку сартуюцца. Але ключ адняць тое, што Паглядзіце, наколькі хутчэй сартаванне зліццём было, калі вы не думаеце, што я толькі збольшага важдацца з вамі. Калі мы робім гэта ў апошні раз, давайце Перазагрузіць, давайце вернемся і выбраць пузырьковую сартаванне, і толькі для удараў, давайце абярэм ўстаўку сартаваць, для роўнага рахунку. І на гэты раз зноў, давайце выбраць сартаванне зліццём і давайце рэальна працаваць гэтыя бок аб бок. І гэта не так, на самай справе, шчаслівая выпадковасць. Тое, што я эфектыўна зрабіць гэта ў мяне ёсць падзяліў свой уклад у палове, зноў, і зноў, і зноў. І ёсць толькі так шмат разоў, вы можаце падзяліць ўваход напалову, злева і права. Што формула, што мы ўвесь час бачу , Які апісвае падзел папалам зноў, і зноў, і зноў, і зноў? АЎДЫТОРЫЯ: Увайсці н. СПІКЕР: Увайсці н. Але тады ёсць яшчэ адзін ключавы крок, гэты алгарытм не ўвайсці п крокаў. Калі б гэта было толькі ўвайсці п крокаў, мы былі б у той жа праблемы як і раней, дзе мы не можам быць што ўсё ў сартуюцца. Вы павінны мінімальна паглядзець на п элементаў каб пераканацца, што п элементаў сартуюцца, у адваротным выпадку гэта скачок веры. Так што гэта мінімальна часопіс п крокаў, але што з гэтай нагоды ключавой стадыі зліцця дзе я зліліся мая левая палова і права палова і прайшоўся па сцэне? Колькі крокаў у тым, што для зліцця? Гэта п, але я не зрабіў усяго аб'яднаць у апошні раз. На кожнай з гэтых ўкладзеных выклікаў, на кожным з тых, ўкладзеных зліццё, я да гэтага часу сартуюцца. Я аб'яднаны гэтыя два хлопцы, то гэтыя два хлопцы, то гэтыя два хлопцы і так далей. Так што я зліцця зноў, і зноў. Колькі разоў? Так што кожны раз я падзяліў Спіс напалову, я зрабіў зліцця. Разбіце спіс напалову, зрабіць зліццё. Так што, калі што падзяляе спіс можна зрабіць часопіс п раз, і зліццё ў канчатковым рахунку, прымае п крокі, што можа быць цяпер верхняя абмежаванне на які працуе Час нашага алгарытму? н увайсці н. І на самай справе, вось што мы дасягнулі тут. Так пачуццё, што вы бачыце візуальна, калі гэтыя тры рэчы працаваць бок аб бок з'яўляецца н квадрат супраць п квадрат супраць н часопіса п. Якія прынцыпова мы ўбачым, не толькі сёння, але ў будучыні, значна, значна хутчэй. Апладысменты для гэтых хлопцаў, Я ўзнагародзіць іх са стрэсам шароў. Давайце перапыніць тут сёння, і мы будзем бачыць вас у панядзелак.