DAVID Малан: Добре. Върнахме се. Така че в този сегмент на програмен какво Мислех да направя е смесица от неща. Един, направи малко на нещо практически, макар и с помощта на по-закачлив програмиране environment-- едно, че е демонстративен на точно вида на идеи ние сме били говорим за, но малко по-официално. Две, да разгледаме някои от по-техническите начини че един програмист действително би могла да разреши проблеми като търсите проблема че ние погледна преди и Също така по-фундаментално интересен проблем на сортиране. 

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

Така че нека да се направи на ръце на част първа. Така че просто си цапаме ръцете с околната среда, наречени scratch.mit.edu. Това е инструмент, който ние използваме в нашия студент клас. Въпреки, че той е проектиран за възрасти 12 и нагоре, ние го използваме за състава част от които доста малко тъй като това е приятно, забавно графичен начин на живот малко нещо за програмиране. Така се отправят към този адрес, където можете трябва да видите страница съвсем като този, и давай напред и кликнете Присъединете се към нулата в горния десен ъгъл и изберете потребителско име и парола и в крайна сметка се получи себе си на account-- scratch.mit.edu. Мислех, че ще използва това като възможност първо да покаже това. Актуален въпрос изскочи по време на почивката за това какво код действително прилича. И ние говорим По време на почивката за C, в particular-- особено на по-ниско ниво в по-стар език. И аз просто направих един бърз Google търсене, за да намерите C код за двоично търсене, алгоритъмът, че ние използва за търсене, които телефонен указател по-рано. Този конкретен пример, разбира се, не търси телефонен указател. Той просто търси цял куп номера в паметта на компютъра. Но ако искате просто да получите визуална смисъл на това, което действително програмиране език изглежда, че изглежда малко нещо като това. Така че това е около 20-плюс, 30-те реда код, но разговорът ни бяха с над почивка е за това, как това всъщност получава се превърна в нули и единици и ако не може просто да се върне, че обработват и отидете от нули и единици резервно за код. 

За съжаление, процесът е така трансформиращ че това е много лесно да се каже отколкото да се направи. Аз отидох напред и действително се обърна тази програма, Binary Search, в нули и единици посредством програма, наречена компилатор, че аз се случи да има тук точно на моя Mac. И ако погледнете на екрана тук, като се фокусира конкретно на следните средни шест колони само, ще видите само нули и единици. И тези, които са нули и тези, които композирате точно, че търсенето на програма. 

И така всеки парче от пет бита, всеки байт от нули и единици тук, представляват някаква инструкция Обикновено вътрешността на компютъра. И в действителност, ако сте чували за маркетинг лозунг "Intel вътре" - това, разбира се, просто означава, че имате Intel CPU или мозъка вътрешността на компютъра. И това, което означава, че за да бъде един CPU е че имате набор инструкции, така да се каже. 

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

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

Така че, след като наистина има сметка на scratch.mit.edu, Кликнете върху бутона Създаване в горния ляв ъгъл на сайта. И вие трябва да видите една среда, като този, аз съм за да се види на екрана си тук. И ние ще прекарат малко малко време да играе тук. Нека да видим дали не можем да решим всички някои проблеми заедно по следния начин. 

Така че това, което ще видите в този environment-- и всъщност просто нека ме пауза. Което не е тук някой? Не тук? ДОБРЕ. Така че нека да се отбележи няколко характеристики на тази среда. 

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

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

Така че това са категориите до върха. Отивам да кликнете категорията Control. По-скоро, аз отивам да кликнете на Събитията категория, най-първата една до върха. И ако искате да следват заедно дори като правим това, вие сте доста добре дошли да. Отивам да щракнете и плъзнете този Първият, "когато зелен флаг кликнали." И тогава аз ще го пуснете просто грубо в горната част на моите празни плочи. 

И това, което е хубаво за Scratch е, че този пъзел парче, когато сключено с друга пъзел парчета, ще направи буквално какви са тези пъзел парчета, казват, да се направи. Така, например, Scratch е прав сега в средата на неговия свят. Отивам да вървим напред и да изберете Сега, нека да кажем, категорията Motion, ако искате да направите same-- Предложение категория. И сега забележи имам цяло куп пъзел парчета тук че, отново, вид правя това, което казват. И аз ще отида напред и да влачите и изпускайте ход блок право върху тук. 

И забележете, че веднага щом се получи в близост до дъното на "зеленото знаме кликнали "бутон, известие как се появява бяла линия, като че ли това е почти магнитен, тя иска да отиде там. Само да отида, и той ще щракне заедно и формите ще съвпадат. А сега можете може би почти Предполагам, къде отиваме с това. 

Ако се вгледате в етапа на Scratch тук и гледам до върха на това, ще видите червена светлина, а знак стоп, и зелен флаг. И аз ще отида напред и гледам моите screen-- само за миг, ако можеше. Отивам да натиснете зелен флаг точно сега, и той се премества, което изглежда е 10 стъпки или 10 пиксела, 10 точки, на екрана. 

И така, не толкова вълнуващо, но нека да предложи без дори да преподава това, просто използвайки притежавате собствен intuition-- нека ми предложи, че можете да разбера как да направи Scratch пеша полето от сцената. Били го направи път на дясната страна на на екрана, по целия път от дясно. Нека ви дам един миг или така да се боря с това. Вие може да искате да погледнете в други категории блокове. Добре. Така че просто да обобщим, когато имаме зеленото знаме кликнали тук и да се премести на 10 стъпки е само инструкция, всеки път, когато кликнете зеленото знаме, което се случва? Е, това е движение моята програма. Така че мога да направя това може би 10 пъти ръчно, но това се чувства малко битов hackish, така да се каже, при което аз не съм наистина разрешаване на проблема. Аз просто се опитвам отново и отново и отново докато аз някак случайно постигане на директивата че съм тръгнал да се постигне по-рано. 

Но ние знаем от нашата Псевдокод по-рано, че има това понятие в програмирането на примка, правите нещо отново и отново. И така, аз видях, че един куп вас достига за какво пъзел парче? Повторете, докато. Така че можем да направим нещо като се повтаря, докато. А ти какво се повтаря, докато по-точно? 

ДОБРЕ. И нека да продължа с този, който е малко по-просто само за миг. Нека да вървим напред и да направим това. Забележете, че, тъй като може да се наложи открих под контрол, има това повторете блок, който не изглежда като това е толкова голям. Няма много място в между тези два жълти линии. Но тъй като някои от вас може да има Забелязах, ако плъзнете и капка, забележите как тя расте, за да запълни формата. 

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

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

Да, така че защо да не направим нещо вечно? А сега нека да се премести този пъзел парче вътре има и да се отървете от този. Сега забележите, без значение къде Scratch започва, той отива до ръба. И за щастие MIT, който прави Scratch, просто прави се, че той никога не изчезва напълно. Винаги можете да вземете опашката си. 

И просто интуитивно, защо той продължи да се движи? Какво става тук? Той, изглежда, е спряно, но След това, ако мога да взема и плъзгане той продължава да иска да отида там. Защо така? Наистина, един компютър е буквално Ще направя това, което го кажа, за да се направи. Така че, ако ви го каза по-рано направете следната нещо вечно, се движат от 10 стъпки, тя ще продължи да функционира и ще докато не се удари в червен знак стоп и спре програмата. 

Така че дори и да не го направи направите това, как бих могъл да направи Scratch движат по-бързо по екрана? Още стъпки, нали? Така че, вместо да правите 10 в момент, защо не отидете напред и да го промените to-- какво бихте propose-- 50? Така че сега аз отивам да кликнете на зелено флаг, и наистина, той отива много по-бързо. 

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

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

Да. Така че ние се нуждаем от някакъв вид на състояние, и изглежда да има условни, така че да говоря, в категорията Control. Коя от тези блокове имаме вероятно искате? Да, може би ", ако, след това." Така че забележите, че сред жълтите блокове имаме тук, там е това "ако" или това "ако, иначе" блок, който ще ни позволи да се вземе решение да се направи това или да направи това. дори и можете да ги гнездо да направим няколко неща. Или, ако все още не сте преминали тук, давай напред към категорията на засичане and-- нека да видим дали това е тук. 

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

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

Някой би ли искал да предложи как съм може да се свърже това може би горе до долу , за да се реши проблема с имащ Scratch ход дясно на ляво на дясно, за да от ляво на дясно на ляво, всеки време само подскачащи на разстояние от стената? Какво искам да направя? Кои блок трябва да се свърже с "Когато зелен флаг кликнали на първо място"? 

ОК, така че нека да започнем с "завинаги". Какво става вътре в следващата? Някой друг. ОК, се движат стъпки. Добре. Тогава какво? Така че тогава IF. И забележи, макар и да изглежда притисната плътно заедно, той просто ще нарасне до запълване. Тя просто ще скочи в мястото, където го искате. 

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

Нека да плъзнете Scratch нагоре. Така че той е малко изкривен сега, но това е добре. Как мога да го възстановите лесно? Отивам да мамят леко. Така че аз съм добавяне на друг блок, само за да бъде ясно. Искам да отбележа 90 градуса надясно по подразбиране, така че аз съм просто ще му кажа да направи това програмно. И тук отиваме. Ние като че ли са го направили. Това е малко странно, защото той ходи с главата надолу. Нека да наречем, че е грешка. Това е грешка. Бъг е грешка в програмата, а логическа грешка, че аз, човекът, направил. Защо се случва с главата надолу? Знаете MIT притеснявам или нали? 

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

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

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

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

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

Ето ни. Ох. Нека да опитаме отново. Ето ни. ОК, аз записва нещо погрешно. Ето ни. Ох. Ох. Добре. Сега трябва да се отървете от това. Добре. 

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

Да, забележи, че е извън че жълт блок. Така че това също би било бъг, но аз съм го забелязал. Така че аз ще го плъзнете до тук, и известие сега е вътре в ", ако". Така че, "ако" е този вид на подобно ръка-като петно че се случва само да направи това, което е вътре в него. Така че сега, ако аз отдалечаване на риска от annoying-- 

КОМПЮТЪР: Ох, ох, ох. 

DAVID Малан: И това просто ще продължи вечно. Сега, само за да се ускори нещата тук, нека да вървим напред и да се отворят, нека say-- ме пусна до известна на мои неща от класа. И нека да се отворят, да речем, това една, направена от един от нашите учебни събратя преди няколко години. Така че някои от вас може да се припомни, тази игра от недалечното минало, и това е всъщност забележителна. Въпреки, че ние сме направили на простият на програми в момента, нека да разгледаме какво е това всъщност прилича. Нека ме удари игра. 

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

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

Но какво друго се случва? Какви други реда код, какви други парчета от пъзел Направих Блейк, нашето учение колега, използва в тази програма, очевидно? Какво се прави всичко move-- какво програмиране изгради? 

Предложение, sure-- така че преместите блок, със сигурност. И това, което е, че ход блок вътре, най-вероятно? Да, някакъв вид цикъл, може би завинаги блокира, може би повторение block-- повтаря, докато блок. И това е това, което се прави на дървени трупи, и лилия подложки и всичко останало ход напред и назад. Това е просто става безкрайно. 

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

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

Да, така че има някакъв вид "Ако" състоянието там, също. И се оказва out-- не видяхме this-- но има други блокове в там, че Може да се каже, ако се допират Друго нещо, което на екрана, ако се докосва лилия тампон, "след това." И след това е, когато ние да се появи втората жаба. Така че, въпреки че тази игра е със сигурност много от, въпреки че на пръв поглед има толкова много ще on-- и Блейк не привличам това до две минути, то вероятно си взе няколко часа, за да се създаде тази игра въз основа на паметта или видеоклипове му на версия на това недалечното минало е. Но всички тези малки неща става на екрана в изолация се свеждат до това много проста constructs-- движения или изявления като говорихме, примки и условия, и това е за него. Има няколко други красиви черти. Някои от тях са чисто естетически или акустична, като звуците аз просто играе с. Но в по-голямата си част, вие има в този език, Scratch, всички от основните градивни елементи, които можете има в C, Java, JavaScript, PHP, Ruby, Python, и всякакъв брой други езици. Всякакви въпроси за Scratch? Добре. Така че ние няма да се потопите в дълбок до нулата, въпреки че сте добре дошли този уикенд, особено ако имате деца или племенници и такива, да ги запознае с Scratch. Това всъщност е чудесно игриво среда с, както казват неговите автори, много високи тавани. Въпреки, че ние започнахме с Самите детайли от ниско ниво, Вие наистина може да направи доста малко с него, и това е може би демонстрация на точно това. 

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

Но какво, ако телефонът книга бяха несортирани? Може би Verizon имам мързелив, просто хвърли имена и номера на всички там може би в реда, в който те регистрирали за телефонни услуги. И колко време отнема мен да се намери някой като Майк Смит? 1000 страница телефон book-- колко страници Трябва ли да погледнете през? 

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

Така произволен ред, не е добро. Така че предполагам, че трябва да се справи със телефонен указател или като цяло данните сортиране че ние сме били дадени. Как можем да направим това? 

Е, нека просто опитайте Един прост пример тук. Нека да вървим напред и да хвърля Няколко номера на дъската. Да предположим, че цифрите, които имаме, са, да речем, четири, две, едно, а три. И, Бен, сортирате тези номера за нас. 

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

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

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

Има две. Чакай малко. Две е по-малък от четири. Отивам да си спомня. Две сега е най-малката. Сега one--, че е дори по-добре. Това е още по-малък. Отивам да забрави за двама и просто не забравяйте едно сега. 

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

И сега ние повторете процеса, както и Разбира три получава извади следващия. Повторете този процес. Четири получава извади. И сега ние сме изложени на номера, така в списъка трябва да бъдат сортирани. 

И наистина, това е формален алгоритъм. Компютърен учен би наричаме това "избор на сортиране," като идеята е сортиране на изброят iteratively-- отново и отново избиране най-малък брой. И това, което е хубаво за него е това е просто толкова дяволски интуитивен. Това е толкова просто. И вие може да се повтаря един и същ работа отново и отново. Просто е. 

В този случай това е бързо, но колко време всъщност взема? Нека да изглежда и се чувствам малко по-досаден. Така че едно, две, три, четири, пет и шест, седем, осем, девет, 10, 11, 12, 13, 14, 15, 16-- произволен брой. Аз просто исках повече това време, отколкото само четиримата. Така че, ако аз имам едно цяло куп номера го now-- дори не значение това, което те are-- нека мисля за това, този алгоритъм наистина е като. 

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

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

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

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

И така, нека да мислим за колко стъпки аз съм всъщност traipsing през всяко време. В първата ситуация имахме 16 номера, и така maximally-- му нека просто направите това за discussion-- Аз трябваше да погледне през 16 номера, за да намерят най-малките. Но след като аз изтръгната най-малък брой, как отдавна е останалата част от списъка, разбира се? Само 15. Така че колко числа направиха Бен или имам да погледнете през втория път? 15, само за да отидат и да намерят най-малките. Но сега, разбира се, в списъка е, също по-малки, отколкото преди. Така че колко стъпки направиха I Трябва да се вземе следващия път? 14 и след 13 и след 12, плюс точка, точка, DOT, докато аз съм оставил само с един. Така че сега е компютърен специалист би попитам, добре, това, което прави, че всички сме равни? То всъщност се равнява на някои бетон брой, че ние със сигурност може да направя аритметично, но ние искаме да говорим за ефективността на алгоритми малко повече formulaically, независимо от това колко дълго списъка е. 

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

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

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

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

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

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

Така че 1000 страница телефон книга може предприеме ни 500 страници завои, плюс един ако ние се удвои малко назад. Така че, ако един телефонен указател има п страници, но правим две страници в даден момент, това е грубо какво? N над две, така че е като п над два. Но аз направих за да претендира за Преди миг, че п над two-- това е почти същото като просто п. Това е просто един постоянен фактор, компютърни специалисти ще кажат. Нека да се съсредоточи само върху променливите, really-- най-големите променливи в уравнението. 

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

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

С други думи, тук е моя списък от номера. Четири, едно, три, две. И аз ще направя следното. Отивам да въведете номера където им е мястото, а отколкото ги изберете един по един. С други думи, тук е номер четири. 

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

Се сортира този нов списък? Да. Това е глупаво, защото има само един елемент, но това е абсолютно подредени. Няма нищо не на място. Това е по-интересно, този алгоритъм, когато се премине към следващата стъпка. 

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

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

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

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

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

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

Така че едно, две, три, четири, пет, шест, седем, осем. Едно две три четири, пет, шест, седем, осем. Отивам да взема осем, и къде мога да го сложите? Е, в началото на моя списък, защото този нов списък е сортиран. И аз го зачеркнете. 

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

Осем трябва да отидете тук. Седем трябва да отидете тук. Сега шестимата да отидете тук. Сега вземете пет. Сега осемте трябва да си отиде тук, седем трябва да отидете тук, шест трябва да отидете тук, и Сега петимата и повторете. И аз съм доста много тя се движи постоянно. 

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

Това друг алгоритъм, който е все още correct-- това ще отида на работа done-- Просто се променя обема на работата. Тя изглежда като първоначално сте спестяване, защото ти си просто занимаващи се с всеки елемент отпред, без да ходят всички Между другото през списъка като Бен беше. Но проблемът е, особено в тези луди случаите, когато това е всичко назад, ти си просто вид отлагане на усилената работа докато не се наложи да поправите грешките си. 

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

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

Този списък не е сортиран. Защо? На английски език, обясни защо това не е всъщност сортирани. Какво означава това, не трябва да бъдат подредени? 

STUDENT: Това не е последователно. 

DAVID Малан: Не е последователен. Дайте ми пример. 

STUDENT: Сложете ги в ред. 

DAVID Малан: OK. Дай ми по-конкретен пример. 

STUDENT: възходящ ред. DAVID Малан: Не възходящ ред. Бъдем по-точни. Аз не знам какво искаш да кажеш с възходящ. Какво има? 

STUDENT: най-малката от номера не е на първо място. 

DAVID Малан: Най-малък брой на не на първо място. Бъдете по-специфичен. Аз съм се започне да се закачат. Ние разчитаме, но това, което е в ред тук? 

STUDENT: номериране. DAVID Малан: номериране. вид водене на всеки човек тя here-- много високо ниво. Просто буквално да ми каже какво е погрешно като пет-годишен мощ. 

STUDENT: Плюс един. 

DAVID Малан: Какво е това? 

STUDENT: Плюс един. 

DAVID Малан: Какво искаш да кажеш, плюс едно? Дай ми различен пет-годишен. Какво не е наред, мамо? Какво не е наред, татко? Какво искаш да кажеш това не е сортиран? 

STUDENT: Това не е на правилното място. 

DAVID Малан: Какво е не на мястото си? 

STUDENT: Four. DAVID Малан: Добре, добре. Така че четири не е мястото, където трябва да бъде. По-специално, е това право? Четири и един, първият две числа, които виждам. Това вярно ли е? Не, те не са на ред, нали? Всъщност, мисля, че сега за компютър, също. Тя може да гледа само може би един, може би две неща once-- и всъщност само едно нещо в даден момент, но може поне Посетете едно нещо тогавашния на Следващо нещо, в непосредствена близост до него. 

Така са тези, с цел? Разбира се, че не. Така ли какво? Защо не вземем бебе стъпки, определящи този проблем вместо да правиш тези фантазия алгоритми като Бен, където той е нещо като това определяне от примка през списъка вместо да правиш това, което направих, когато Аз просто един вид го фиксира като отидем? Нека просто буквално съборят понятие за order-- ред на номерата, го наричат ​​каквото и да want-- в тези двойки сравнения. 

Четири и един. Дали това е правилния ред? Така че нека да поправи това. Един и четири, и след това ние просто ще копира това. Добре, добре. Оправих едно и четири. Три и две? Не. Нека думите ми съвпадат пръстите ми. Четири и три? 

Това не е в ред, така че аз ще да се направи един, три, четири, две. Добре. Сега четири и две? Ние трябва да се определи това, също. Така един, три, две, четири. Така е то подредени? Не, но е по-близо до сортирани? 

Това е, защото тази фиксирана грешка, ние фиксирана тази грешка, и ние фиксирана тази грешка. Така че ние фиксирана три грешки безспорно. Все още не е наистина изглежда сортиран, но е обективно по-близо до сортиран защото фиксирана някои от тези грешки. 

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

Аз трябва да се опита отново. Така че Оливия предлага опитам отново. Защо? Защото един компютър няма лукса на нашите човешки очи на само поглеждайки back-- ОК, аз съм направил. Как компютърът определи че списъкът сега се сортира? Механично. 

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

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

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

Така че това е някой хубав софтуер, който някой пише с помощта на цветни ленти, които е Ще направя следното за нас. Всеки един от тези барове представлява номер. Taller бара, толкова по-голям броя, по-малък от гредата, толкова по-малък номер. Така че в идеалния случай ние искаме хубава пирамида където тя започва малък и получава голяма, и това би означавало, че тези барове са сортирани. Така че аз ще отида напред и да изберете, например, алгоритъм на Бен first-- избор на сортиране. 

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

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

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

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

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

Но списъка в end-- spoiler-- ще бъдат сортирани. Така че нека да разгледаме един последен един. Не можем просто да пропуснете сега. Ние сме почти там. Двама да отида, един да отиде. И готово. Отличен. 

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

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

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

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

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

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

Е, нека сега дразни, освен това, което всички тези линии са, че съм бил рисуване и това, което аз съм се предположи компютъра може да се направи под предния капак. Бих казал, че всички тези номера Държа drawing-- те се нуждаят, за да получите съхраняват някъде в паметта. Ние ще се отървете от този човек сега, твърде. 

Така че едно парче на памет в computer-- толкова RAM DIMM е това, което търсихме вчера, двойна инлайн памет module-- изглежда по този начин. И всеки един от тези малки черни чипове някои брой байтове, обикновено. И тогава златните игли са подобни на кабели, които го свързват с компютъра, и зелен силициев борда е просто това, което държи всичко заедно. Е, какво значи това наистина означава? Ако аз вид привлече същия тази картина, да предположим за простота че това DIMM, двойна инлайн модул с памет, е един гигабайт RAM, един гигабайт памет, която е колко общо байта? Един гигабайт е колко байта? Повече от това. 1124 е килограм, 1000. Mega е милион. Giga е един милиард. 

Am I лъже? Можем дори да чете етикета? Това е всъщност 128 гигабайта, така че е повече. Но ние ще се преструвам, този е само един гигабайт. Така че това означава, че има един милиард байта памет на разположение за мен или 8 милиарда бита, но ние отиваме да говоря от гледна точка на байта сега, движа се напред. 

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

И така, аз може да постави четири номера тук. Едно две три четири. Или мога да сложи четири букви или символи. "Хей!" може да отиде точно там, тъй като всяка от буквите, ние обсъдихме по-рано, могат да бъдат представени с осем бита или ASCII или един байт. Така че, с други думи, можете да сложи 8 милиарда неща вътре на този един стик на паметта. Сега какво означава да постави нещата назад за да се върна обратно в паметта като този? Това е, което един програмист ще се обади на "масив." В една компютърна програма, вие не мислите за основния хардуер, само по себе си. Просто мисля за себе си като имащи достъп до общия един милиард байта, и можете да всичко, което искате с него. Но за удобство това е обикновено полезно да си прав памет един до друг по този начин. Така че, ако аз се фокусирам върху this-- защото ние със сигурност няма да ходиш да се направи един милиард малки squares-- да предположим, че този съвет представлява че стик памет сега. И аз просто ще направи толкова, колкото ми маркер завършва давайки ми тук. Така че сега ние имаме една пръчка на паметта на дъската че има един, два, три, четири, пет, шест, едно, две, три, четири, пет, шест, seven-- така 42 байта памет общия брой на екран. Благодаря. Да, направих моя аритметика полето. Така 42 байта памет тук. И така, какво означава това всъщност означава? Е, компютърен програмист всъщност ще обикновено мисля, че на тази памет като адресат. С други думи, всеки един от тях местоположения в паметта, в хардуер, има уникален адрес. 

Това не е толкова сложна, колкото Един Братъл Square, Cambridge, Mass., 02138. Вместо това, той е просто един номер. Това е байт номер нула, това е един, това е два, е три, и това е 41. Чакай малко. Мислех, че каза 42 преди малко. Започнах да броим на нула, така че това е всъщност правилна. Сега ние не трябва да всъщност го направи като решетка, и ако го направи като решетка Мисля, че нещата в действителност получите малко подвеждащо. Какво програмист би, в собствената си ум, като цяло мисля, че на този памет, както е точно като на лента, като парче хартиено тиксо че просто продължава и върху завинаги или докато не изтече на паметта. Така че по-общ начин да се привлече и просто мисля за памет ще бъде, че това е байт нула, едно, две, три, а след това с точка, точка, точка. И вие имате общо 42 такива байта, дори въпреки че физически той може в действителност да е нещо по-така. 

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

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

Не е за разлика от рекордните плейър и четяща глава, само е в състояние да погледнем в определен бразда във физическа рекорд от старата школа по време, подобно може един компютър благодарение да му CPU и неговото Intel набор инструкции, сред чиито инструкция се чете от паметта или запишете на memory-- на компютър може да изглежда само на едно място в time-- понякога комбинация от тях, но наистина само едно място в даден момент. Така че, когато ние правехме тези различни алгоритми, Аз не съм просто писане в vacuum-- четири, едно, три, две. Тези числа всъщност принадлежат някъде физическа памет. Така че има мъничък транзистори или някакъв вид на електрониката под качулка съхраняване на тези стойности. 

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

Така че сега нека да поиска от друга въпрос с помощта на паметта, защото в края на деня е в противоречие. Без значение какво можем да направим с компютъра, в края на деня хардуерът е все още на същото под предния капак. Как бих се съхранява дума тук? Е, една дума на един компютър като "Хей!" ще се съхраняват само по този начин. И ако искате по-дълго дума, можете просто презаписване, че и да кажа нещо като "здравей" и магазин, който тук. 

И така, тук също, това contiguousness всъщност е предимство, защото един компютър може просто чете от дясно на ляво. Но тук е въпрос. В контекста на тази дума, з-д-л-л-о, удивителен знак, как може компютърът знае къде е Думата започва и където думата завършва? В контекста на номера, как компютъра знам колко дълго последователността на номера е или където тя започва? Е, оказва out-- и ние няма да отидат твърде много в това ниво на detail-- компютри се движат нещата около в памет буквално по пътя на тези адреси. Така че в един компютър, ако сте писането код за съхраняване на неща като думи, това, което сте наистина прави пише изрази, които си спомнят, където в памет на компютъра тези думи са. Така че нека да се направи много, много прост пример. 

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

Нека да направим това, всъщност. Когато зелен флаг кликнали, направете следното. Искам да отпечатате "здравей". Така че сега това е Псевдокод. Аз съм нещо като замъгляване на линиите. В C, този език говоря за тази линия печат здравей всъщност става "ФОРМАТ" с някои скоби и точка и запетая. 

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

Така че можете да вид предполагам. Дори ако никога не сте програмирани преди, какво прави тази програма вероятно правя? Вероятно отпечатва здравей с удивителен знак. 

Така че нека се опитаме това. Отивам да го спаси. И това е, отново, много стара училищна среда. Не мога да кликнете, аз не мога да плъзнете. Трябва да въведете команди. Така че аз искам да тече моята програма, така че Аз може да направи това, като hello.c. Това е файла, който изтича. Но чакайте, аз съм липсва една стъпка. Какво направихме ние казваме, е необходимо стъпка за език като C? Току-що написан източник код, но това, което ми е необходимо? Да, имам нужда от компилатор. Така че на моя Mac тук, имам програма, наречена GCC, GNU C компилатор, което ми позволява да правя this-- завой ми изходния код в, ние ще го наричаме, машинен код. 

И мога да видя, че, Отново, както следва, тези са нули и тези, които аз просто създаден от моя изходния код, всички нули и единици. И ако искам да тече ми program-- това се случва да се нарече a.out за исторически reasons-- "здравей". Мога да го стартирате отново. Здравей Здравей Здравей. И това изглежда да се работи. 

Но това означава, че някъде в моята памет на компютъра са думите з-д-л-л-о, удивителен знак. И се оказва, просто като настрана, какво компютър обикновено би направи така, че да не знае къде нещата започват и end-- това е ще постави специален символ тук. И Конвенцията е да се постави номер нула в края на думата така че вие ​​къде го знам фактически завършва, така че да Да не се съхранява отпечатване все повече и повече символи, отколкото всъщност имат намерение. 

Но Takeaway тук, дори въпреки че това е доста тайнствена, е, че това е в крайна сметка сравнително проста. Ти беше даден вид на лента, празен пространство, на която можете да пишете писма. Ти просто трябва да има специален символ, като произволно числото нула, за да сложи в края на Вашите думи така, че компютърът ми е свидетел, О, аз трябва да спре да печата, след Виждам удивителен знак. Защото следващото нещо, което има е ASCII стойност, равна на нула, или нулевата характер като някой ще го наречем. Но има и нещо като проблем тук, и нека да се върне обратно до номера за миг. Да предположим, че аз правя, всъщност, имаме масив от числа, и предполагам, че програма Пиша е като клас книга за учителя и учители класната стая. И тази програма него или нея позволява да въведете в десетки техните ученици на викторини. И предполагам, че студентът получава 100 за първия си тест, може би като 80 на следващия, а след това 75, след това 90 на четвърти теста. 

Така че в този момент в историята, масива е с размери четири. Няма абсолютно повече памет в компютър, но на масива, така да се каже, е с размери четири. Да предположим сега, че учителят иска да възложи една пета викторина към класа. Е, едно от нещата, които той или тя ще трябва да направите, сега се съхранява допълнителна стойност тук. Но ако масива учителят има създаден в тази програма е с размер за, един от проблема с множество е, че не може просто да поддържа добавянето на памет. Защото това, което, ако друга част от програма има думата "хей" точно там? 

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

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

Но ако никога учителя използва тези три помещения, има интуитивен храна за вкъщи тук. Той или тя е просто загуба на пространство. Така че, с други думи, там е това общ компромис в програмирането където можете да разпредели точно толкова памет, колкото искате, В посока нагоре, от които е, че вие ​​сте супер efficient-- ви не се разточително при all-- но недостатъкът на които е това, което, ако промените мнението си, когато с помощта на програмата, която искате да съхраните повече данни, отколкото първоначално сте предназначени. 

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

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

И така, за да се постигне тази цел, ние Трябва да хвърлят тази структура от данни, така да се каже, далеч. И така, какво програмист обикновено ще използва е нещо, което не е наречено масив, но свързан списък. С други думи, той или тя ще започне да се мисли за тяхната памет като вид форма, която те може да се направи по следния начин. Ако искам да се съхранява един номер в а program-- така че е септември Дадох моите студенти тест; аз искам за съхраняване на първия тест на студентите, и те имам 100 на it-- I отивам да попитам моя компютър, по пътя на програмата съм писмено, за една парче от паметта. И аз отивам, за да съхраните номер 100 в нея, и това е всичко. 

След няколко седмици по-късно когато получа моят втори тест, и че е време да въведете в която 90%, аз отивам да поиска от компютъра, хей, компютър, мога да имам друг парче от паметта? Това ще ми даде тази празно парче от паметта. Отивам да се постави в брой 90, но в моята програма по някакъв начин или other-- и ние няма да се тревожи за синтаксиса за this-- ми трябва по някакъв начин да прикове тези неща заедно. И аз ще ги прикове заедно с това, което изглежда като стрела тук. 

Третият тест, който идва, Отивам да се каже, хей, компютър, дай ми още една буца памет. И аз отивам да потушат каквото и да е, като 75, и аз трябва да верига тази заедно сега някак си. Четвърто викторина идва заедно, а може би и това е към края на семестъра. И от този момент моята програма може да бъде използване на паметта навсякъде, по целия физически. И така, само за ритници, аз съм Ще се направи това напред quiz-- да забравя какво е било; аз че може би на 80 противниците или нещо друго начин тук. 

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

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

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

Така черпене сега е тази снимка тук. Това е свързан списък, тъй като програмист ще го наричаме, доколкото имате списък, очевидно на номера. Но това е свързано картинно по пътя на тези стрелки, и всички тези стрели are-- отдолу качулката, ако сте любопитни, Припомняме, че нашата физическа хардуерна има адреси нула, едно, две, три, четири. Всички тези стрели са е като карта или направления, в които, ако 90 is-- сега Трябва да се брои. 

Нула, едно, две, три, четири, пет, шест, седем. Тя изглежда като 90 е най- памет адрес номер седем. Всички тези стрели са се като малко парче хартия че да даде указания на програма, която казва, следват тази карта да стигнем до място седем. И там ще намерите най- втори тест на полувремето студент. Междувременно, 75-- ако продължи това, това е седем, осем, девет, 10, 11, 12, 13, 14, 15. 

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

Но се оказва, не за да получите твърде технически. Но само защото ние може би ще позволят да имат тази дискусия тук, Предполагам, че ние отново този въпрос тук от масив. Да видим дали съжаляваме става тук. Това е 100, 90, 75 и 80. 

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

И така с масив, че имате функция, известна като произволен достъп. И какво означава произволен достъп е че компютърът може да скочи мигновено за всяко място в масив. Защо? Тъй компютъра знае че първото място е нула, едно, две, три. 

И така, ако искате да се премине от този елемент на следващия елемент, Вие буквално, в съзнанието на компютъра, просто добавете една. Ако искате да отидете на третия елемент, Просто добавете one-- следващия елемент, просто добавете една. Въпреки това, в тази версия на историята, да предположим, компютърът е в момента търси при или занимаващи се с номера 100. Как да стигнем до следващото клас в клас книгата? 

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

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

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

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

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

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

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

Но няма очевидно решение тук. Може би това е better-- а-ла-бърз и мръсен, като Карим предложен earlier-- да хвърлят памет на проблема. Просто купуват повече памет, мисля, че по-малко трудно за решаване на проблема, и го решим в по-лесен начин. И наистина по-рано, когато ние говорихме за компромиси, не е пространство компютъра и времето. Беше време разработчик, който е още един ресурс. 

Така че отново, това е този балансиращ акт опитвайки се да реши кои от тези неща, склонни да харчат сте? Коя е най-евтиният? Което води до получаване на по-добри резултати? Да? 

Наистина. В този случай, ако сте представляваща номера в maps-- те се наричат ​​в много езици "указатели" или "адреси" - това е двойно пространството. Това не трябва да бъде толкова лошо, колкото двойно, ако точно сега ние просто съхраняване на номера. Да предположим, че сме били съхраняване досиета на пациентите в hospital-- така имена Пиърсън е, телефонни номера, номера на социални осигуровки, лекар история. Тази клетка може да бъде много, много по-голям, като в този случай мъничък показалеца, на адреса на следващата element-- това не е голяма работа. Това е толкова ресни струва, че няма значение. Но в този случай, да, това е удвояване. Добър въпрос. 

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

Big O на п е какво се изисква, за да се получи в края на тази структура данни, whereas-- и не сме виждали това before-- масив дава това, което се нарича константно време, което означава, една стъпка или две стъпки или 10 steps-- Няма значение. Това е един фиксиран номер. Това няма нищо общо с размера на масива. И причината за това, отново, е произволен достъп. Компютърът може просто веднага скочи на друго място, защото те всички са еднакви разстояние от всичко останало. Не е мислене участват. Добре. Така че, ако мога, нека се опитаме да нарисува две финални снимки. А много често един известен като таблица хашиш. Така че, за да мотивира тази дискусия, позволете ми да мисля за това как да направите това. 

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

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

Е, аз съм един вид измама тук, защото всеки един от тези буквите в думата е наистина индивидуално байт. Така че, ако аз наистина исках да бъда гнида-придирчиви, че трябва наистина да се раздели този нагоре в много по-малки парчета от паметта, и можем да направим точно това. Но ние ще се сблъскате същия проблем, както преди. Ами ако, като Merriam Webster или Оксфорд прави всеки year-- те добавят думи до dictionary-- не го правим непременно искаме да се нарисува в един ъгъл с масив? 

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

Така че ние имаме едни и същи точните въпроси, както и преди, при което имаме сега динамика в нашия списък свързан. Но ние имаме доста бавен речника. Да предположим, че искате да погледнете нагоре и дума. Тя може да ми отнеме голяма O на п стъпки, защото думата мощ е чак в края на списъка, като пъпеш. И се оказва, че в програмирането, сортиране на Светия Граал на данни структури, е нещо, който ви дава постоянна време като масив но това все още дава динамика. 

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

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

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

Така ли какво? Вместо да постави всички мои думи в същата кофа, така да се каже, като в един голям списък, защо не го правят Аз поне се опита оптимизация и да ми списъци 1/26 толкова дълго. А непреодолими оптимизация може да е защо не го правят I-- при поставянето на думата в тази структура от данни, в паметта на компютъра, защо не сложих всички "А" думите тук, всичко думите "б" тук, и всички "С" думи тук? Така че това в крайна сметка сложи ябълка тук, банан тук, пъпеш тук, и т.н. 

И ако имам допълнителен Думата like-- това, което е още един? Ябълка, банан, круша. Всеки, който се мисли за плодове който започва с А, В, или С? Blueberry-- перфектно. Това се случва, за да се свърши тук. И така, ние като че ли да има незначително по-добро решение, защото сега, ако искам за търсене на ябълка, I first-- аз не просто гмуркане в моята структура на данните. Аз не се потопите в памет на моя компютър. Аз първо разгледаме първата буква. 

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

Сега това съкращава времето ни потенциално с толкова, колкото един на 26, защото, ако приемем, че сте имат най-много "А" думи като "Z" думи като думи "Q", които Не е наистина realistic-- започваш да имат кос през някои букви от alphabet-- но това ще бъде постепенен подход, който позволява можете да получите на думи много по-бързо. И в действителност, изискан програма, на Googles на света, на Facebooks на world-- те ще се използва хеш-таблица за много различни цели. Но те не биха били толкова наивен като да изглежда точно по първата буква в ябълка или банан или круша или пъпеш, защото, както можете да видите тези списъци все още може да получи дълго. 

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

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

Но осъзнават колко бързо този вид на дискусия ескалира, както досега, че това е вид на над главата в този момент, който е наред. Но ние започнахме, изземване, с наистина нещо на ниско ниво и на електронен носител. И така, това отново е това Темата на абстракция, където след като започнете да се вземат за отпусната, ОК, аз съм it-- попаднал там е физическата памет, Добре, разбрах, всеки физическо място има адрес, ОК, аз го имам, мога да представляват тези адреси като arrows-- можете да много бързо да започне да има по-сложни разговори, които в края на краищата изглежда да ни позволи за решаване на проблеми, като търсите и сортиране по-ефективно. И бъдете сигурни, too-- защото мисля, че това е най-дълбокото сме отишли ​​в някои на тези CS теми proper-- ние сме направи в един ден и половина в този посоча това, което може обикновено правя над В продължение на осем седмици в семестър. 

Всички въпроси, свързани с тях? Не? Добре. Е, защо не спрете там, започне обяд няколко минути по-рано, възобнови само около един час? И аз ще се задържи за малко с въпроса. Тогава аз ще трябва да отида отнеме няколко повиквания, ако това е ОК. Ще включа малко музика в същото време, но обяд трябва да е зад ъгъла.