Дејвид MALAN: Во ред. Ние сме назад. Значи во овој сегмент на програмирање што Мислев дека би го сторила е мешавина на нештата. Еден од нив, се направи малку на нешто практично, иако со користење на повеќе игрива програмирање environment-- оној кој е покажана на токму видови на идеи ние сме биле зборува за, но малку повеќе формално. Две, да погледнеме некои од повеќе технички начини дека програмер, всушност, ќе се реши проблеми како во потрага проблем дека ние погледна пред и исто така, повеќе фундаментално интересен проблем на сортирање. 

Ние само се претпоставува од се оди дека телефонот книга е сортирана, но тоа само по себе е всушност еден вид на тежок проблем со многу различни начини да го реши. Па ние ќе ги користат овие како класа на проблеми претставник на работи кои може да се реши во целина. И потоа ќе зборуваме за во некои детали што се нарекуваат податоци structures-- познавач начини како поврзани листи и хаш маси и дрвја кои програмер всушност ќе користење и генерално се користат на таблата да се наслика слика на она што тој или таа предвидува одобрување за спроведување некои парче софтвер. 

Значи, да се направи со рацете на првиот дел. Па само да ја добиете вашата раце валкани со средина на scratch.mit.edu. Ова е алатка која ние ги користиме во нашата додипломски класа. Иако таа е дизајнирана за деца од 12 и нагоре, ние го користиме за до дел од тоа доста бидејќи тоа е убаво, забавно графички начин на учење нешто за програмирање. Па главата на таа адреса, каде што Треба да се види страница сосема вака, и да одат напред и да кликнете Приклучи се на гребнатини во горниот десен агол и да изберете корисничко име и лозинка и на крајот да си на account-- scratch.mit.edu. Мислев дека ќе го искористат ова како можност прво да се покаже тоа. А прашање дојде за време на паузата во врска со кодот кој всушност изгледа како. И ние се зборува За време на паузата за C, во particular-- особено на пониско ниво во постара јазик. И јас само направив брз Google пребарување за да најдете C код за бинарни пребарување, алгоритам што ние се користи за пребарување дека телефонот книга порано. Овој пример, се разбира, не се бара на телефон книга. Се бара само еден куп на броеви во меморијата на компјутерот. Но, ако сакате само да се визуелно смисла на она што вистински програмирање јазик како изгледа, тоа изгледа малку нешто како ова. Така, тоа е во врска со 20-плус, 30 или така линии на код, но на разговорот се имаат во текот на паузата беше за тоа како, всушност, добива претвори во нули и единици и ако не може само да се врати што обработува и да си одат од нули и единици се врати да се код. 

За жал, процесот е толку трансформативниот дека тоа е многу полесно да се каже отколку да се направи. Отидов напред и всушност се претвори таа програма, бинарни пребарување, во нулите и по пат на програма наречена компајлерот дека јас се случи да имаат право тука на мојот Mac. И ако се погледне на екранот тука, фокусирајќи се особено на овие средната шест колони само, ќе видите само нули и единици. И оние кои се на нули и оние кои компонира токму тоа бараат програма. 

И така секој парче на пет парчиња, секој бајт на нули и тука, претставуваат некои настава обично во внатрешноста на компјутерот. И во Всушност, ако сте слушнале маркетинг слоган "Интел внатре" - дека, се разбира, само значи дека има Интел процесор или мозокот во внатрешноста на компјутерот. И што значи тоа да се биде процесорот е дека имате инструкциско множество, така да се каже. 

Секој процесор во светот, многу од ги направи од Intel, овие денови, разбира конечен бројот на инструкции. И тие упатства се толку ниско ниво како да додадете овие два броја заедно, размножуваат овие два броја заедно, се движи овој дел од податоците од тука овде во меморијата, освен овој информации од тука до тука во меморијата, и така forth-- толку многу, многу ниско ниво, речиси електронски детали. Но, со овие математички операции во комбинација со она што беше порано, застапеноста на податоци како нули и единици, може да ќе се изгради до се што дека секој компјутер може да се направи денес, без разлика дали тоа е текстуални, графички, музички, или на друг начин. 

Значи ова е многу лесно да се добие изгубени во плевелот на брзо. И има многу синтаксички предизвици при што ако се направи од наједноставните, stupidest на грешки никој од програмата ќе работат она. И така, наместо користење на јазик како C ова утро, Мислев дека тоа ќе биде повеќе да се забавуваат да всушност направи нешто повеќе визуелни, кои а наменета за деца всушност е совршен манифестација на вистински програмирање Language-- само се случува да користење на слики наместо текст да ги претставуваат тие идеи. 

Значи откако ќе навистина имаат сметка на scratch.mit.edu, кликнете на копчето креирате во горниот лев агол на страницата. И треба да го видите на животната средина како оној што јас сум за да се види на мојот екран овде. И ние ќе се трошат само малку малку време да игра тука. Ајде да видиме ако не можеме да се решат некои проблеми заедно на следниот начин. 

Значи она што ќе видите во овој environment-- а всушност само ги споделите со ми се откажеш. Не е тука некој? Не тука? ДОБРО. Значи, дозволете ми да истакнам неколку карактеристики на оваа средина. 

Значи во горниот лев агол на екранот, ние има фаза на гребење, така да се каже. Нула не е само името на овој програмски јазик; тоа е, исто така, името на мачка која ќе видите стандардно таму во портокал. Тој е на сцената, па слично како што е опишано желката порано дека се наоѓа во правоаголни бела табла средина. светот оваа мачка е ограничена во целост на тоа правоаголник до врвот таму. 

Во меѓувреме, на десната страна странично тука, тоа е само една област скрипти, на празен ако сакате. Ова е местото каде што ние ќе треба да се напише нашите програми во само еден миг. И градежни блокови кои ние ќе се користи за да ја напишам оваа program-- сложувалката парчиња, ако се will-- оние, токму тука во средината, и тие се категоризираат од страна на функционалност. Така, на пример, јас ќе одам да се оди напред и покажат најмалку еден од нив. Одам да се оди напред и да кликнете категоријата Контролирајте до врвот. 

Значи овие се категориите до врвот. Одам да кликнете на категорија контрола. Наместо тоа, јас ќе одам да кликнете на Настани категорија, првиот еден до врвот. И ако сакате да го следат заедно, дури и како го правиме тоа, ти си сосема добредојдени да. Одам да кликнете и повлечете овој Првиот, "кога зелено знаме кликнато." И тогаш јас ќе одам да се намали само речиси на врвот на мојот празен лист. 

И, што е убаво за гребење е дека овој сложувалка, кога испреплетени со други загатка парчиња, се случува да се направи буквално она што тие мозаик парчиња се каже да се направи. Така, на пример, нула е во право сега во средината на неговиот свет. Одам да се оди напред и да се избере сега, да речеме, во категоријата движење, ако сакате да го направите same-- движење категорија. И сега се забележи имам целиот куп на мозаик парчиња тука дека, повторно, вид на направи она што велат тие. И јас одам да се оди напред и да го повлечете и пад на потег блок право овде. 

И ќе забележите дека веднаш штом ќе се во близина на долниот дел од "зелено знаме кликнато "копче, известување како се гледа бела линија, како да е речиси магнетни, таа сака да оди таму. Само нека оди, и тоа ќе пукне заедно и форми ќе одговара. И сега може да можеби речиси Претпоставувам каде одиме со ова. 

Ако се погледне во фазата на гребење овде и се погледне на врвот на тоа, ќе видите црвено светло, гости знак, и зелено знаме. И јас одам да се оди напред и да се види мојот screen-- за само еден миг, ако може. Одам да кликнете на зелено знаме во моментов, и тој се пресели она што се појавува да биде 10 чекори или 10 пиксели, 10 точки, на екранот. 

И така тоа не е возбудлив, но дозволете ми да предложат дури и без настава ова, само со користење на сопствени свој intuition-- ајде ми предложи да дознаам како да се направи гребење одиме право надвор од сцената. Го направи патот за десната страна на на екранот, на целиот пат кон десно. Дозволете ми да ви даде еден момент или така да се справат со тоа. Можеби ќе сакате да се погледне во други категории на блокови. Во ред. Па само да повториме, кога имаме зеленото знаме кликне тука и да се движат 10 чекори е само настава, секој пат кога кликнете на зелено знаме, што се случува? Па, тоа е водење мојата програма. За да можам да го направите ова можеби 10 пати рачно, но тоа се чувствува малку hackish малку, така да се каже, при што јас не сум решавање на проблемот. Јас сум само се обидува повторно и повторно и повторно и повторно додека јас вид на грешка постигнување на Директивата дека јас изнесени да се постигне и порано. 

Но, ние знаеме од нашето pseudocode претходно дека има овој поим во програмирањето на looping, прави нешто повторно и повторно. И така видов дека еден куп од вас посегна по што загатка парче? Повторете се додека. Значи ние не можеше да стори нешто како што се повторува додека не. И што ќе се повторува се додека точно? 

ДОБРО. И дозволете ми да одам со оној кој е нешто поедноставен за само еден миг. Дозволете ми да оди напред и да го направите тоа. Забележете дека, како што може да откриен под контрола, постои и ова се повторува блок, кој не изгледа како тоа е толку голема. Нема многу простор во помеѓу овие два жолти линии. Но, како што некои од вас може да има забележи, ако drag and drop, информации како што расте за пополнување на форма. 

Можете дури и да ставам повеќе. Тоа само ќе продолжи да расте, ако ќе повлечете и лебди над неа. И јас не знам што е најдобрите тука, па ајде мене барем повтори пет пати, за На пример, а потоа се врати на сцената и кликнете на зелено знаме. И сега се забележи тоа не е сосема таму. 

Сега некои од вас предложи, како Викторија само се повторува 10 пати. И тоа генерално не му се на тој пат, но не би да има повеќе стабилна начин од произволно да пронајдат колку потези да се направи? Што може да биде подобро блок од Повторете 10 пати да биде? 

Да, па зошто да не се направи нешто засекогаш? А сега дозволете ми да се движат на оваа загатка парче внатре има и ослободете се од оваа. Сега забележите без разлика каде гребење започнува, тој оди до работ. И за среќа МИТ, кој прави нула, само прави сигурни дека никогаш потполно исчезнува. секогаш може да го дофати опашката. 

И само интуитивно, зошто тој Чувајте се движат? Што се случува овде? Тој изгледа како да застанува, но тогаш да ги собереш и влечете тој постојано сакаат да одат таму. Зошто е тоа? Навистина, компјутерот е буквално ќе го направи она што го каже да го стори. Па ако го кажав и претходно го стори по нешто вечно, се движат од 10 чекори, тоа се случува да продолжувам да одам и ќе додека не хит на црвениот знак стоп и да престане целосно програмата. 

Па дури и ако не сте да го направите ова, како би можел да се движи побрзо од гребење низ екранот? Повеќе чекори, нели? Така, наместо да го прави 10 во исто време, зошто да не се оди напред и да ја промените to-- што би propose-- 50? Па сега јас ќе одам да кликнете на зелената знаме, и навистина, тој оди навистина брзо. 

И ова, се разбира, е само манифестација на анимација. Што е анимација? Тоа е само ви покажува на човекот на целиот куп на фотографии, навистина, навистина, навистина брзо. И така, ако ние сме само кажувам него да се движат повеќе чекори, ние сме само има ефект да биде да се промени, каде што е на екранот сите побрзо по единица време. 

Сега следниот предизвик што го предложив требаше да го преувеличува на раб. И без да знаат што загатка парчиња exist--, бидејќи тоа е во ред ако не се дојде до фаза на она што challenge-- Дали сакате да се направи интуитивно? Како ќе го натера да застане на нозе и натаму, меѓу левата и десната? 

Да. Значи ние треба некој вид на состојбата, а ние се чини дека имаат conditionals, така да зборува, во категоријата контрола. Која од овие блокови ние веројатно сакате? Да, можеби "ако, тогаш." Така да се забележи дека меѓу жолти блокови имаме тука, таму е ова "ако" или ова "ако, на друго место" блок кој ќе ни овозможи да се донесе одлука да се направи ова или да го стори тоа. па дури и може да ги гнездо да се направи повеќе нешта. Или, пак, ако се уште не сте поминале тука, оди напред во категоријата на детекција and-- Да видиме дали тоа е тука. 

Значи она што блок може да биде корисно тука да се открие дали тој е надвор од сцената? Да, забележите дека некои од овие блокови може да се parametrized, така да се каже. Тие може да се вид на индивидуално, не за разлика од HTML вчера со атрибути, каде што тие атрибути вид на го прилагодите однесувањето на таг. Слично на тоа тука, можам да го имате овој допирање блок и да се промени и да се постави прашањето, ви се допира на глувчето како покажувач на покажувачот или ви се допира работ? 

Па дозволете ми да оди и да го направите тоа. Одам да одзумирате за момент. Дозволете ми да го имате овој сложувалка тука, оваа сложувалка ова, и јас ќе одам да купот нив за само еден миг. Одам да се помести ова, промените ова на допир работ, а јас ќе одам на движење го направите тоа. Значи тука се и некои состојки. Мислам дека сум го доби она што го сакам. 

Некој би сакал да предложам како јас може да се поврзе овие можеби врвот до дното со цел да се реши проблемот на морале Нула движи од десно на лево кон десно за да лево кон десно на лево, секој време само бие надвор од ѕидот? Што сакате да направите? Кои блок треба да се поврзе со "Кога зелено знаме кликна првиот"? 

Добро, па ајде да почнеме со "засекогаш". Она што се случува внатре во вашето следно? Некој друг. Во ред, се движи чекори. Во ред. А што потоа? Па тогаш ако. И ќе забележите, дури и покрај тоа што изгледа споени заедно цврсто, тоа само ќе се зголеми за да се пополни. Тоа само ќе скокне во каде што го сакате. 

И она што можам да се стави меѓу на, ако и тогаш? Веројатно "ако допира работ". И известување, повторно, тоа е премногу голема за тоа, но тоа ќе се зголеми за да се пополни. А потоа се претвори 15 степени? Колку степени? Да, па ќе се вртат 180 мене сите обратно. Значи, да се види дали добив ова право. Дозволете ми да одзумирате. 

Дозволете ми да го повлечете на гребење нагоре. Па тој е малку искривена сега, но тоа е во ред. Како можам да го ресетирате лесно? Одам да лажеш малку. Затоа, јас сум додавајќи уште еден блок, само за да биде јасно. Сакам да истакнам 90 степени на правото по дифолт, па јас сум само ќе го кажам да го стори тоа програмски. И тука ќе одиме. Се чини да се го сториле тоа. Тоа е малку чудно, бидејќи тој е одење наопаку. Ајде да се јавите дека бубачка. Тоа е грешка. А бубачка е грешка во програмата, логичка грешка што јас, човекот, направени. Зошто е тој ќе наопаку? Дали МИТ зафркнам или јас? 

Да, мислам, тоа не е МИТ вина. Тие ми дадоа сложувалка кој се вели дека се претвори некои број на степени. И на предлог на Викторија, Јас сум врти за 180 степени, кој е вистинскиот интуиција. Но вртење од 180 степени буквално значи вртење од 180 степени, и тоа не е навистина она што сакам, очигледно. Бидејќи барем тој е во Оваа две-димензионални светот, така пресвртна навистина се случува да го флип наопаку. 

Јас веројатно ќе сакате да го користите она блок Наместо тоа, врз основа на она што го гледате овде? Како можеме да го надминете овој? Да, па ние може да се укаже во спротивна насока. И всушност, дури и дека е нема да биде доволно, затоа што ние може само тешко код да покажува лево или десно. 

Знаете што можеме да направиме? Изгледа дека имаме погодност блок тука. Ако можам да зумирате, видете нешто што допаѓа кај нас? Така што изгледа како МИТ има апстракција изградена тука. Овој блок се чини дека се еднакви на кое други блокови, множина? 

Оваа една блок се чини дека се еднакви за целиот трио на блокови дека имаме тука. Значи излегува јас може да се поедностави мојот програмата од страна да се ослободиме од сето тоа и само да се стави ова во тука. И сега тој е сепак малку кабриолет, и тоа е добро за сега. Ќе го оставиме тоа да биде. Но, мојата програма е дури и поедноставно, а тоа, исто така, да биде репрезентативен на гол во programming-- идеално е да се направи вашиот код како едноставен, како компактен како е можно, додека сеуште се како може да се чита како е можно. Вие не сакате да се направи тоа, така содржаен дека тоа е тешко да се разбере. 

Но забележите сум заменува три блокови со еден, и тоа е веројатно добра работа. Сум апстрахирани далеку поимот на проверка дали сте на работ со само еден блок. Сега можеме да се забавуваат со оваа, во факт. Ова не додадете толку многу интелектуална вредност, но разигран вредност. Одам да се оди напред и го имате овој звук тука. Па дозволете ми да оди напред, и нека ме запре програмата за момент. Одам да се снима следната година, овозможување на пристап до мојот микрофон. 

Еве ќе одиме. Уф. Ајде да се обидеме тоа повторно. Еве ќе одиме. Добро, јас снимен нешто погрешно. Еве ќе одиме. Уф. Уф. Во ред. Сега е потребно да се ослободи од тоа. Во ред. 

Па сега имам снимање на само "Уф". Па сега јас ќе одам да се оди напред и ова го нарекуваат "Уф". Одам да се врати на мојот скрипти, и сега известување има овој блок што се вика игра звук "meow" или репродуцира звук "Уф". Одам да го повлечете овој, и каде што треба да се стави ова за комична? Да, па сега тоа е вид на кабриолет, бидејќи сега тоа block-- информации како ова ", ако на работ, отскокнување "е вид на автономни. Значи ми треба да го надминете овој. Дозволете ми да оди напред и да го направите тоа. Дозволете ми да се ослободи од ова и се врати на нашите оригинални, повеќе намерно функционалност. Така, "ако се допира работ, тогаш" Сакам да се менува, бидејќи Викторија предлага, 180 степени. И не сакам да играм звукот "Уф" таму? 

Да, забележите дека тоа е надвор дека жолта блок. Значи ова, исто така, ќе биде грешки, но јас не сум го забележал. Па јас ќе одам да го влечете до тука, и информации сега е во внатрешноста на "ако". Значи, "ако" е овој вид на како рака-како размачкана што се случува само на го направи она што е во него. Па сега ако јас одзумирате на ризикот од annoying-- 

Компјутер: Уф, Уф, Уф. 

Дејвид MALAN: И тоа само ќе трае вечно. Сега само да се забрза работите тука, дозволете ми да оди напред и да се отвори, ајде say-- дозволете ми да одат на некои на моето работи од класа. И дозволете ми да се отвори, да речеме, ова направен од еден од нашите наставата соработници пред неколку години. Значи, некои од вас може да се потсетиме оваа игра од недалечното минато, а тоа е всушност извонреден. И покрај тоа што ние го направивме наједноставните програми во моментов, ајде да се разгледа она што овој всушност изгледа како. Нека ме удри игра. 

Значи во оваа игра, имаме жаба, и користење на стрелките keys-- тој зема поголеми чекори од мене remember-- Имам контрола над оваа жаба. А целта е да се добие низ зафатен патот без трчање во автомобили. И ајде да see-- ако одам до тука, мора да почека за најавите за да се движите од. Ова се чувствува како бубачка. Ова е вид на бубачка. Во ред. Јас сум на овој овде, таму, а потоа да се задржи случува се додека не добиете сите жаби на крин влошки. Сега ова може да изгледа сè повеќе и повеќе комплекс, но, ајде да се обиде да се пробие ова долу ментално и усно на нејзините составни блокови. Па таму е веројатно загатка парче што не сме виделе уште но тоа е одговор на тастатурата, на работите ќе се погоди на тастатурата. 

Па таму е веројатно еден вид блок кој вели дека, ако клучот е еднаква нагоре, потоа да се направи нешто со Scratch-- Можеби тоа се движи од 10 чекори на овој начин. Ако не се притисне копчето, се движат 10 чекори На овој начин, или левото изборно копче, се движат 10 чекори На овој начин, 10 чекори за тоа. Сум јасно покажа на мачка во жаба. Па тоа е само кога костим, како гребење повици it-- ние само увезени слика на жаба. 

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

Движење, па sure-- се движи блок, за сигурен. И, што е тој потег блок внатрешноста, најверојатно? Да, некој вид на јамка, можеби засекогаш да го блокира, а можеби и да се повтори block-- Повторете се додека блок. И тоа е она што се прави на регистрите и крин влошки и сè друго потег напред и назад. Тоа е само случува бескрајно. 

Зошто некои од автомобилите се движат побрзо од другите? Што е различно за овие програми? Да, веројатно некои од нив се одвиваат повеќе чекори одеднаш, а некои од нив помалку чекори одеднаш. И визуелен ефект е брз наспроти бавно. 

Што мислиш, што се случи? Кога влегов ми жаба на целиот пат другата страна на улицата и реката кон крин рампа, нешто спомене случило. Што се случи веднаш штом ќе го направи тоа? Тој престана. Жаба запре, и Добив вториот жаба. Значи она што конструкција мора да биде се користи, што функција? 

Да, па таму е некој вид на "Ако" состојба таму, исто така. И излегува out-- не видовме this-- но има и други блокови таму дека може да се каже, ако се допираат Друга работа, на екранот, ако сте допирање на крин рампа ", а потоа". И тогаш тоа е кога ние да се појават на втората жаба. Па дури и ако оваа игра е, секако, многу датум, иако на прв поглед има толку многу се случува on-- и Блејк не камшик ова во две минути, тоа веројатно го зеде неколку часа за да се создаде оваа игра врз основа на меморијата или неговите видеа на верзија на него недалечното минато е. Но, сите овие мали нешта се случува на екранот во изолација сведуваат на овие многу едноставна constructs-- движења или извештаи како ние разговаравме, јамки и услови, и тоа е за тоа. Има неколку други познавач карактеристики. Некои од нив се само естетски или акустична, како звуците јас само игра со. Но, во најголем дел, имаме во овој јазик, нула, сите основни градежни блокови кои имаат во C, Java, JavaScript, PHP, Ruby, Python и било кој број на други јазици. За било какви прашања во врска со нула? Во ред. Значи ние не ќе се нурне подлабоко да се нула, и покрај тоа што сте добредојдени овој викенд, особено ако имате деца или внуки и внуци и такви, да се запознаат со гребење. Тоа е всушност прекрасно разигран животната средина, со, како што велат неговите автори, многу високи тавани. И покрај тоа што започна со многу детали на ниско ниво, навистина може да направи доста со тоа, и ова е можеби демонстрација токму тоа. 

Но, ајде сега да транзиција кон некои повеќе софистицирани проблеми, ако сакате, познат како "пребарување" и "Сортирање", воопшто. Имавме овој телефон книга earlier-- еве уште еден само за discussion-- дека сме биле во можност да пребарување поефикасно, бидејќи на значителен претпоставка. И само за да биде јасно, што Претпоставката беше јас да прават при пребарување низ овој телефон книга? Дека Мајк Смит беше во книгата на телефонот, иако јас ќе биде во можност да се справи со сценарио без него таму, ако јас само престана предвреме. Книгата е по азбучен ред. И тоа е многу дарежлива претпоставка, бидејќи тоа значи someone-- Јас сум вид на сечење агол, како што сум јас побрзо, бидејќи некој друг не е многу напорна работа за мене. 

Но, што ако телефонот книгата се вон едиции? Можеби Веризон добив мрзливи, само фрли имињата и броевите на сите таму можеби во редоследот по кој тие се регистрираа за телефонски услуги. И колку време е потребно за мене да се најде некој како Мајкл Смит? 1.000 страница телефон book-- колку страници не морам да се погледне преку? 

Сите тие. Ти си вид на надвор од среќа. Вие буквално треба да се погледне во секој страница и ако телефонот книга е само случајно подредени. Можеби ќе имаат среќа и да се најде Мајк на првата страница, бидејќи тој беше првиот клиент да нареди телефонска услуга. Но, тој би можел да биде и последен, исто така. 

Значи случаен редослед не е добро. Па претпоставувам дека ние треба да ги сортирате телефон книга или воопшто податоци вид дека ние сме биле дадени. Како можеме да го направите тоа? 

Па, дозволете ми да се обиде едноставен пример тука. Дозволете ми да оди напред и да се фрли неколку броеви на табла. Да претпоставиме дека на броеви имаме се, да речеме, четири, два, еден, и три. И, Бен, се најде решение за овие броеви за нас. 

Во ред добро. Како го направи тоа? Во ред. Така на проектот со најмалите вредност и на највисоко, и тоа е навистина добра интуиција. И да сфатат дека ние луѓето се всушност прилично добар во решавање на проблемите вака, барем кога податоците е релативно мал. Веднаш штом ќе почнете да имаат стотици на броеви, илјадници броеви, милиони броеви, Бен веројатно не може да го направи тоа доста така брзо, под претпоставка дека имало празнини во бројките. Прилично лесно да се смета за еден милион Во спротивно, само одзема време. 

Значи алгоритам што звучи како Бен користи само сега беше пребарување за најмалиот број. Па дури и покрај тоа што луѓето може да се земе во голем број на информации визуелно, компјутер е, всушност, малку повеќе ограничени. Компјутерот може само погледнете на еден бајт во еден момент или можеби четири бајти на 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, само да одат и да се најде на најмалите. Но, сега, се разбира, на листата е, исто така, помал отколку што беше порано. Значи колку чекори не јас треба да го преземе следниот пат? 14 и од 13 и од 12, плус точка, точка, точка, се додека јас сум лево со само еден. Па сега компјутерски научник би побара, добро, што значи дека сите еднакви? Тоа, всушност, е еднаква на некои конкретни број што би можеле да сигурно направи аритметички, но ние сакаме да се зборува во однос на ефикасноста на алгоритми малку повеќе formulaically, независно од тоа колку долго на листата е. 

И така, знаеш што? Ова е 16, но како што реков претходно, ајде да се јавите на големината на проблемот n, каде што n е некој број. Можеби тоа е 16, а можеби и тоа е три, можеби тоа е еден милион. Јас не знам. Не ми е гајле. Она што јас навистина го сакам е формула што можам користат за споредба овој алгоритам против други алгоритми дека некој може да тврдат дека се подобро или полошо. 

Значи излегува, и само јас знам од основно училиште, дека тоа всушност се работи надвор на истиот нешто што е n повеќе од n плус еден во текот на две. И ова се случува да се изедначи, на Се разбира, n квадрат плус n текот на две. Значи, ако јас сакав формула за колку чекори беа вклучени во потрага на сите од тие броеви повторно и повторно и повторно и повторно, јас би рекол тоа е n квадрат плус n текот на две. Но знаеш што? Ова само изгледа неуредна. Јас само навистина сакате општа смисла на нештата. И може да се сети од средно училиште дека постојат е идејата за највисока цел мандат. Кои од овие услови, n квадрат, n, или на половина, има најмногу влијание текот на времето? Колку е поголема n добива, кој за овие работи најмногу? 

Со други зборови, ако јас приклучок во милион, n квадрат ќе биде, најверојатно, факторот доминантен, бидејќи еден милион пати само по себе е многу поголема од плус еден дополнителен милиони евра. Па да знаете што? Ова е толку ебам големи број ако се соочат со број. Ова навистина не е важно. Ние сме само ќе крстот што надвор и да заборави за тоа. И така компјутерски научник би рекол дека ефикасноста на овој алгоритам е од редот на n squared-- Мислам навистина приближување. Тоа е вид на приближно n квадрат. Со текот на времето, толку е поголема и поголеми n добива, овој е добра проценка за тоа што ефикасност или недостаток на ефикасност на овој алгоритам всушност е. И јас се изведе тоа, се разбира, од всушност прави математика. Но сега јас сум само мавта моите раце, бидејќи јас само сакате општа смисла на овој алгоритам. 

Па со користење на истата логика, пак, ајде да се разгледа уште еден алгоритам веќе погледна at-- линеарно пребарување. Кога бев пребарување за телефон book-- не сортирање, пребарување преку телефон book-- ние се чуваат велејќи дека тоа е 1.000 чекори, или 500 чекори. Но, ајде да се генерализира дека. Ако има n страници книгата на телефонот, што е трчање време или ефикасноста на линеарно пребарување? Тоа е од редот на колку чекори да се најде Мајк Смит користење на линеарна пребарување, Првиот алгоритам, или дури и на секунда? 

Во најлош случај, Мајк се наоѓа на крајот на книгата. Значи, ако телефонот книга има 1.000 страници, рековме последен пат, во најлош случај, тоа може да потрае приближно колку многу страници да се најде Мајк? Како 1000. Тоа е горната граница. Тоа е најлошата можна ситуација. Но, повторно, ние сме се движат подалеку од 1000 броеви како сега. Тоа е само n. 

Значи она што е логичниот заклучок? Наоѓање на Мајк во телефонски книга во која има n страници може да се земе, во најлош случај, колку чекори од редот на n? И навистина компјутер научник би рекол дека трчање време, или извршување или на ефикасноста или неефикасност, на алгоритам како линеарна пребарување е од редот на n. И ние може да се примени истата логиката на премин нешто како што го направија во втората алгоритам што го имавме со книгата на телефонот, каде што отидовме на две страници во исто време. 

Значи 1.000 страница телефон книга може да се со нас 500 страница се врти, плус еден ако ние двојно назад малку. Значи, ако именикот има n страници, но, ние сме прави две страници во еден момент, тоа е околу она што? N текот на две, па тоа е како n текот на две. Но, не сум направил барањето за пред моментот кога n над two-- тоа е вид на иста како само n. Тоа е само постојана фактор, компјутерски научници би рекол. Ајде да се фокусира само на променливи, really-- најголем променливи во равенката. 

Значи линеарно пребарување, без разлика дали тоа еден страница во време или две страници во еден момент, е еден вид на основа на истиот. Тоа е уште од редот на n. Но, јас тврдеше дека со мојата слика на почетокот дека третиот алгоритам не беше линеарна. Тоа не е права линија. Тоа беше тоа што крива линија, и алгебарската формула имаше што? Пријавете се на n-- така логаритам со основа две од n. И ние не треба да се оди во премногу многу детали за логаритми денес, Но, повеќето компјутерски научници не би дури и да ви кажам што е основата. Поради сето тоа е само константни фактори, така да се каже, само мало нумерички разлики. И така ова ќе биде многу честа начин за особено формални компјутер Научниците на одборот или програмери во бела табла всушност, тврдејќи кои алгоритам тие ќе го користат или што ефикасноста на нивните алгоритам е. 

И ова не е нужно нешто ќе разговараат во било која голема детали, но добар програмер е некој кој има солидна, формални позадина. Тој е во состојба да се зборува за вас во овој вид на начин а всушност се направи квалитативни аргументи зошто еден алгоритам или едно парче од софтвер е супериорен во однос на некој начин во друг. Затоа што секако може да се само ја стартувате програмата на една личност и смета на бројот на секунди што е потребно да се најде решение за некои броеви, и може да се кандидира на некои програма другата личност и смета на бројот на секунди што е потребно. Но, ова е поопшт начин што можете да го користите да се анализира алгоритми, ако сакате, само на хартија или само вербално. Без дури да ја извршува, без дури и се обидува примерок влезови, вие само може да се причина низ него. Така е и со ангажирање на инвеститорот или ако има на него или неа вид на се расправаат за вас зошто нивните алгоритам, нивните тајни сос за пребарување милијарди на веб страници за вашиот компанијата е подобро, овие се видови на аргументите кои ги идеално треба да бидат во можност да се направи. Или барем тие се видови на работи кој ќе излезе во дискусијата, во барем во многу формален дискусијата. Во ред. Значи Бен предложи нешто наречен селекција вид. Но јас ќе одам да предложи дека има другите начини на тоа, исто така. Она што јас не навистина ми се допаѓа за алгоритам на Ben е тоа што тој продолжи да чекори, или ја мене да оди, напред и назад и напред и назад и напред и назад. Што ако, наместо јас да се направи нешто како овие броеви тука и јас да се справи само со едни Бројот, пак, како што јас сум го дал? 

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

Тука е оригиналниот мојата листа. И јас одам да се одржи во суштина нов листа овде. Значи ова е стариот листата. Ова е нова листа. Гледам број четири во прв план. Мојот нов листа е првично празен, па тоа е тривијално случај дека четири сега се избрани листа. Јас сум само преземање на бројот сум дал, и јас сум тоа ставање во мојата нова листа. 

Се подредени оваа нова листа? Да. Тоа е глупаво, бидејќи таму е само еден елемент, но тоа е апсолутно подредени. Нема ништо надвор од местото. Тоа е повеќе интересно, овој алгоритам, кога ќе се движи кон следниот чекор. 

Сега имам еден. Па, се разбира, му припаѓа на почетокот или на крајот на оваа нова листа? Почетокот. Па јас треба да направи некои работи сега. Сум бил со преземање на некои слободи со мојот маркер само со цртање работи каде што ги сакате, но тоа не е навистина точни во компјутер. А компјутерот, како што знаеме, има RAM меморија, или Случаен Пристап меморија, и тоа е еден бајт и уште еден бајт и друг бајт. И ако имате GIGABYTE на RAM меморија, имаш една милијарда бајти, но тие се физички во едно место. Вие не може само да се движат работите околу со цртање на табла каде што сакате. Значи, ако мојата нова листа има четири локации во меморијата, За жал, четири е веќе во погрешно место. 

Така да внесете број еден Јас не само да го привлече тука. Оваа локација во меморијата не постои. Тоа би било мамење, и сум бил мамење сликовито за неколку минути овде. Значи, навистина, ако сакам да се стави тука, Имам привремено да го копирате четири а потоа се стави на еден таму. 

Тоа е во ред, тоа е точно, тоа е технички можно, но сфати дека е дополнителна работа. Јас не само што се стави на бројот на место. Јас прв пат мораше да се движи број, а потоа го стави во место, па јас вид на двојно мојот обемот на работа. Па задржи дека во умот. 

Но, јас сега сум се направи со овој елемент. Сега сакам да го имате на бројот три. Каде што, се разбира, не го припаѓаат? Помеѓу. Јас не може да измамник повеќе и само да го стави таму, затоа што, повторно, оваа меморија е во физички локации. Па јас треба да го копирате четири и го стави на три овде. Не е голема работа. Тоа е само еден дополнителен чекор again-- чувствува многу ефтин. 

Но, сега сум се движи кон двете. Двајцата, се разбира, му припаѓа тука. Сега ќе почнете да се види како работата може да се таложат. Сега, она што можам да сторам? Да, јас треба да се движат на четири, тогаш треба да го копирате три, и сега можам да вметнете ги двете. И се фати со овој алгоритам, интересно е доволно, е дека претпоставиме дека имаме поекстремни случај кога тоа е да речеме осум, седум, шест, пет, четири, три, два, еден. Ова е, во многу контексти, Најлошото сценарио, бидејќи ебам нешто е буквално наназад. 

Тоа навистина не е влијае на алгоритам на Бен, затоа што во изборот на Ben вид, тој се случува да се задржи ќе напред и назад низ листата. И затоа што тој е секогаш во потрага низ целиот преостанат листа, тоа не е важно каде што елементите се. Но, во овој случај со мојата вметнување approach-- ајде да се обидеме ова. 

Така, еден, два, три, четири, пет, шест, седум, осум. Еден два три четири, пет, шест, седум, осум. Одам да се земе на осум, и каде можам да го стави? Па, на почетокот на мојата листа, бидејќи оваа нова листа е сортирана. И јас го крстот надвор. 

Каде можам да се стави на седум? Ебам тоа. Тоа треба да се оди таму, па Јас треба да направите некои копирање. И сега на седум оди овде. Јас сега се движи кон шест. Сега тоа е дури и повеќе работа. 

Осум треба да оди тука. Седум мора да оди тука. Сега шест може да оди тука. Сега јас го дофати пет. Сега осум мора да оди тука, седум мора да оди тука, шест мора да оди тука, и сега пет и повторете. И јас сум прилично многу преместувајќи постојано. 

Па на крајот, ова algorithm-- ние ќе го нарекуваат вметнување sort--, всушност, има многу работа, исто така. Тоа е само различни вид на работа од Бен. работа на Бен имаше ми се случува напред и назад во секое време, изборот на следниот најмалите елемент повторно и повторно. Така беше тоа многу визуелни вид на работа. 

Овој други алгоритам, кој се уште е correct-- дека ќе одам на работа done-- го менува обемот на работа. Тоа изгледа како првично сте заштеда, затоа што ти си само кои се занимаваат со секој елемент до пред без одење сите начинот на кој се низ листата како Бен беше. Но, проблемот е, особено во овие луди случаи каде што тоа е за сите наназад, ти си само вид на одложување на напорна работа додека не треба да се поправат грешките. 

И така, ако може да се замисли ова осум и седум години и шест и пет а подоцна и четири и три и две движат својот пат низ листата, ние сме само смени видот на работа што го правиме. Наместо тоа го прават во почетокот на мојата повторување, Јас сум само тоа го прават во крајот на секоја итерација. Значи излегува дека овој алгоритам, исто така, обично се нарекува вметнување вид, Исто така, од редот на n квадрат. Тоа е всушност не се подобри, нема подобро на сите. 

Сепак, постои една третина пристап Јас би ни ги охрабри да се разгледа, што е ова. Значи Претпоставувам мојата листа, за едноставност повторно, е четири, еден, три, two-- само четири броеви. Бен имаше добра интуиција, добар човечки интуиција и досега, со кои сме ги решиле целиот листа eventually-- вметнување вид. Јас ни убедував заедно. Но, ајде да се разгледа Наједноставниот начин да го надминете овој список. 

Оваа листа не се подредени. Зошто? На англиски јазик, објасни зошто тоа не е всушност подредени. Што значи тоа да не да се решат? 

СТУДЕНТСКИ: Тоа не е секвенцијален. 

Дејвид MALAN: Не е секвенцијален. Дај ми еден пример. 

СТУДЕНТСКИ: Ставете ги во ред. 

Дејвид MALAN: Добро. Дај ми повеќе конкретен пример. 

СТУДЕНТСКИ: Растечки редослед. Дејвид MALAN: Не е растечки редослед. Попрецизно. Јас не знам што мислиш со нагорна линија. Што е проблемот? 

СТУДЕНТСКИ: Најмалото од броеви не е во првата простор. 

Дејвид MALAN: Најмалиот број е не во првиот простор. Бидете конкретни. Јас сум почнуваат да се фати за. Ние сме броење, но што е на ред овде? 

СТУДЕНТСКИ: нумерички редослед. Дејвид MALAN: нумерички редослед. вид на чување на сите тоа here-- многу високо ниво. Само буквално ми каже што е погрешно како и пет-годишниот сила. 

СТУДЕНТСКИ: плус еден. 

Дејвид MALAN: Што е тоа? 

СТУДЕНТСКИ: плус еден. 

Дејвид MALAN: Што сакаш да кажеш плус еден? Дај ми еден поинаков пет години. Што не е во ред, мамо? Што не е во ред, тато? Што сакаш да кажеш ова не е сортирана? 

СТУДЕНТСКИ: Тоа не е на вистинското место. 

Дејвид MALAN: Што е не е во право место? 

СТУДЕНТСКИ: Четири години. Дејвид MALAN: Добро, добро. Па четири не е местото каде што треба да биде. Поточно, дали е тоа така? Четири и, првиот два броја гледам. ова е во право? Не, тие се на ред, во ред? Всушност, мислам дека сега за компјутер, исто така. Тоа може само да се погледне во можеби една, можеби две работи once-- а всушност само една работа во исто време, но тоа може барем погледне во една работа, тогаш Следното нешто веднаш до него. 

Значи се овие, во ред? Се разбира не. Па да знаете што? Зошто не можеме да се земе бебето чекори за утврдување на овој проблем наместо да го прават овие фенси алгоритми како Бен, каде што тој вид на одредување на looping низ листата наместо да го прават она што го направив, каде што Јас само вид на фиксен како што ние одиме? Ајде само буквално се распаѓа на поимот order-- нумерички редослед, го наречеме она што want-- во овие парови споредби. 

Четири и еден. Дали е ова правилен ред? Значи, да го поправите тоа. Еден до четири, а потоа ние само ќе копија од тоа. Добро, добро. Јас фиксна еден до четири. Три и два? Бр Нека моите зборови одговараат на моите прсти. Четири и три? 

Тоа не е во ред, па јас ќе одам да се направи еден, три, четири, две. Во ред добро. Сега, четири и два? Ние треба да го надминете овој, исто така. Така, еден, три, два, четири. Така е тоа сортирани? Не, но тоа е поблиску до подредени? 

Тоа е, затоа што сме ги решиле ова грешка, дека сме ги решиле оваа грешка, и сме ги решиле оваа грешка. Значи ние фиксна три грешки веројатно. Се уште не навистина изгледа подредени, но тоа е објективно поблиску до сортирани затоа што ние фиксна некои од оние грешки. 

Сега, она што можам да направам следно? Јас вид на достигнала крајот на листата. Јас се чинеше дека имаат фиксни сите грешки, но нема. Затоа што во овој случај, некои броеви може да клобуркаше до поблиски на други броеви кои се уште се на ред. Значи, да го направат тоа повторно, а јас ќе само го прават тоа во место тоа време. Еден и три? Во ред е. Три и два? Се разбира дека не, па ајде да го промени тоа. Па два, три. Три и четири? И сега ајде да се биде особено педантни тука. Дали е тоа сортирани? Можете луѓето знаат дека тоа е сортирана. 

Јас треба да се обидете повторно. Значи Оливија се предлага се обидувам повторно. Зошто? Бидејќи компјутер нема луксузот на нашите човечки очи од само гледајќи back-- Добро, јас сум се направи. Како го прави компјутерот се утврди дека листата е сега се решат? Механички. 

Јас треба да се оди преку уште еднаш, и само ако јас не се направи / најде било какви грешки можам а потоа се заклучи како на компјутер, да, ние сме добро да отидевме. Значи еден и два, два и три, три и четири. Сега можам да дефинитивно да кажам дека ова е подредени, бидејќи не сум направил никакви промени. Сега тоа ќе биде грешка и само глупави ако Јас, на компјутерот, побара од истите прашања повторно очекуваат различни одговори. не треба да се случи. 

И така сега на листата се подредени. За жал, трчање време на Овој алгоритам е, исто така, N на квадрат. Зошто? Затоа што имаат n броеви, а во најлош случај треба да се движи n број n пати, бидејќи треба да се насочи назад за да се провери и потенцијално го надминете овие броеви. И ние може да направи повеќе формална анализа, исто така. 

Така што ова е за сите да се каже ние сме земени три различни пристапи, еден од нив веднаш интуитивен надвор од лилјак од Бен да предложи мојот вметнување вид на оваа каде што вид на изгубиме од вид шумата за дрва на почетокот. Но, тогаш, ако се чекор назад, Voila, решивме сортирање поим. Значи ова е, се осмелувам да кажам, пониско ниво можеби од некои од оние другите алгоритми, но ајде види ако не можеме да се визуелизира овие по пат на ова. 

Значи ова е некои убави софтвер кој некој напиша користење на шарени барови тоа е се случува да го направите следново за нас. Секој од овие барови претставува број. Повисоки бар, поголем бројот, толку е помал бар, толку е помал бројот. Значи идеално сакаме убав пирамида каде што почнува мали и добива голема, и тоа би значело дека овие барови се подредени. Па јас ќе одам да се оди напред и да изберат, на пример, алгоритам на Ben first-- селекција вид. 

И ќе забележите она што таа го прави. Начинот на кој тие го избрале да визуелизира овој алгоритам е дека, исто како што беше одење низ мојата листа, оваа програма е одење преку својата листа на броеви, осветлување во секоја розова број кој што е во потрага на. И, што е за да се случи сега? 

Најмалиот број кој I и Бен се најде одеднаш добива се пресели во почетокот на листата. И ќе забележите дека тие не иселат на број, кој е таму, и тоа е совршено добро. Јас не навлегувам во тоа ниво на детали. Но, ние треба да се стави тој број, некаде, па ние само што се пресели во отворено место што е создадена. Па јас ќе одам да се забрза овој , затоа што во спротивно станува многу досаден брзо. Анимација speed-- таму ќе одиме. Па сега истиот принцип Бев примена, но може да почне да се чувствувате алгоритам, ако волја, или да ја видите малку повеќе јасно. И овој алгоритам има ефект на изборот на следниот најмалиот елемент, така си оди за да почне да видите дека рампата на левата страна. И на секој повторување, како што предлага, тоа го прави малку помалку работа. Тоа не мора да одат сите на патот Вратете се на левиот крај на листата, затоа што веќе знае тие се подредени. Така што вид на се чувствува како да е забрзување, и покрај тоа што секој чекор е преземање на иста количина на време. Има само помалку чекори до крајот. И сега можете да вид на се чувствува алгоритам чистење на крајот од неа, и навистина сега тоа се подредени. 

Значи вметнување вид е направено. Јас треба да се ре-случајни низата. И ќе забележите дека јас само може да задржиш randomizing, а ние ќе се приближување на на истиот пристап, вметнување вид. Дозволете ми да ви го успори до тука. Да почнеме дека повеќе. Стоп. 

Ајде да го прескокнете четири. Таму ќе одиме. Случајни тие низа. И тука ние go-- вметнување вид. Игра. Забележете дека тоа е се занимаваат со секој елемент со кои доаѓа веднаш, но ако тоа припаѓа во огласот за доделување на погрешно место сите на работа што треба да се случи. Ние мора да се задржи менување на повеќе и повеќе елементи за да се направи простор за оној кој сакаме да се стави во место. 

Значи ние се фокусираме на левиот крај од само листата. Забележи, дури и не се гледаше at-- ние не се истакнати во розова ништо на десно. Ние сме само се занимаваат со проблемите како што ние одиме, но ние сме создавање на многу работи за нас самите уште. И така, ако ние го забрза тоа сега да одат на проектот, има различен чувствуваат кон него, навистина. Тоа е само се фокусира на левата крајот, но тоа малку повеќе работа како needed-- вид на мазнење работи повеќе, одредување на работите, но на крајот се занимаваат со секој елемент едно по едно време се додека не се дојде до the-- добро, Сите знаеме како тоа се случува да се стави крај, па тоа е малку underwhelming можеби. 

Но на листата во end-- spoiler-- се случува да се решат. Па ајде да погледнеме во еден последен. Не можеме само да ја активирате сега. Ние сме речиси таму. Две да одат, еден да одам. И Voila. Одлично. 

Па сега ајде да се направи еден последен, повторно randomizing со балон вид. И ќе забележите тука, особено ако го забават долу, ова води упад преку. Но забележите тоа само прави парови comparisons-- вид на локални решенија. Но, штом ќе се дојде до на крајот на листата во розова, она што се случува да мора да се повтори? Да, тоа се случува да треба да се во текот на проектот, бидејќи тоа само фиксна парови грешки. И дека може да се откри уште други. И така, ако го забрза тоа, ќе се види дека, колку што самото име имплицира, помалите elements-- или подобро, поголемите elements-- почнуваат на меурот до врвот, ако сакате. И помалите елементи се почнуваат да меур одредување на левата страна. И навистина, тоа е вид на визуелен ефект, како и. И така ова ќе заврши до завршувањето во многу сличен начин, исто така. 

Ние не треба да се задржиме на овој особено еден. Дозволете ми да се отвори ова сега, исто така. Има неколку други алгоритми за сортирање во светот, од кои неколку се заробени тука. А особено за учениците кои не се мора визуелен или математички, како и порано, може да се исто така го направите ова audially Ако ние се дружат звук со ова. И само за забава, тука е неколку различни алгоритми, а еден од нив особено сте ќе забележите се нарекува "спојат вид." 

Тоа, всушност, е фундаментално подобар алгоритам, како што се спојат вид, еден од оние што ти си за да се види, не е цел од n квадрат. Тоа е од редот на n пати се логирате на n, што е, всушност, помали и на тој начин побрзо од оние другите три. И има неколку други глупо оние што ќе видиме. 

Тука ќе одиме со некои звук. Ова е вметнување вид, па повторно тоа е само се занимаваат со елементи како што дојде. Ова е меур вид, па затоа е со оглед на нив парови во исто време. И повторно, најголемата елементи се жуборот на врвот. 

Потоа селекција вид. Ова е алгоритам на Бен, каде што повторно тој е изборот iteratively следниот најмалиот елемент. И повторно, сега навистина може да се слушне дека тоа е забрзување, но само доколку како што тоа го прави помалку и помалку работи на секој повторување. Ова е побрзо еден, се спојат вид, која сортирање групи на броеви заедно, а потоа комбинирање на нив. Значи look-- лево половина е веќе сортирана. 

Сега е сортирањето на десната половина, и сега тоа се случува да се комбинираат во една. Ова е нешто што се нарекува "Gnome вид." И можете да вид на се види дека тоа се случува и назад, одредување работат малку тука и таму пред продолжува до нова работа. И тоа е тоа. Има уште еден вид, кој е навистина само за академски цели, наречен "глупава вид", која ги зема вашите податоци, тоа сортира по случаен избор, а потоа проверува дали се подредени. И ако тоа не е, тоа повторно да го сортира по случаен избор, проверува дали тоа е сортирана, и ако не се повторува. И во теорија, probabilistically ова ќе заврши, но по доста време. Тоа не е повеќето ефикасни алгоритми. Така било прашања во врска со оние особено алгоритми или ништо поврзани таму, исто така? 

Па, ајде сега да одгатнат што сите овие линии се дека јас сум бил цртеж и она што јас сум под претпоставка дека компјутерот може да се направи под хауба. Јас би рекол дека сите овие броеви Продолжувам drawing-- тие треба да се чуваат некаде во меморијата. Ние ќе се ослободи од овој човек сега, исто така. 

Значи парче меморија во computer-- така RAM DIMM е она што го барав за вчера, двојна Вграден меморија module-- изгледа вака. И секоја од овие малку црна чипови некои број на бајти, обично. И тогаш злато иглички се допаѓа жици кои го поврзете на компјутер, и зелен силикон плоча е само она што чува се што сите заедно. Па што значи тоа навистина значи? Ако јас вид на се подготви оваа иста слика, да претпоставиме дека за едноставност дека ова DIMM, двојна РЕГИСТРАЦИЈА мемориски модул, е еден гигабајт RAM меморија, еден гигабајт меморија, која е колку вкупно бајти? Една GIGABYTE е колку бајти? Повеќе од тоа. 1.124 е килограм, 1000. Мега е милиони евра. Giga е една милијарда. 

Дали сум лежи? Можеме да дури и чита етикетата? Ова е всушност 128 гигабајти, па тоа е повеќе. Но, ние ќе се преправа дека ова е само еден гигабајт. Па тоа значи дека има милијарди бајти меморија на располагање за мене или 8 милијарди парчиња, но ние ќе да се зборува во однос на бајти сега, се движи напред. 

Па што значи тоа е тоа е еден бајт, ова е уште еден бајт, ова е уште еден бајт, И ако навистина сакаше да бидат конкретни ние ќе треба да подготви милијарда малку плоштади. Но, што значи тоа? Па, дозволете ми да зумирате во на оваа слика. Ако имам нешто што изгледа вака сега, тоа е четири бајти. 

И така, може да се стави четири броја тука. Еден два три четири. Или би можел да се стави четири букви или симболи. "Еееј!" би можеле да одат право, таму, бидејќи секоја од буквите, што беше порано, може да се претстави со осум бита или ASCII или бајт. Значи со други зборови, може да 8 милијарди стави работите во на овој еден стап на меморија. Сега, она што значи да се стави работите назад да се врати назад во меморијата, како тоа? Тоа е она што програмер би го нарекол "низа". Во компјутерска програма, што не мислам дека за основната хардвер, сама по себе. Вие само мислам на себе како што имаат пристап до вкупно една милијарда бајти, и може да се нешто што сакате со него. Но, за погодност генерално е покорисно да се задржи вашето право меморија еден до друг се допаѓа ова. Значи, ако јас зумирате на this-- затоа што, секако, не се случува да се подготви една милијарда малку squares-- Да претпоставиме дека овој форум претставува кои се лепат на меморија сега. И јас само ќе се повлече колку што ми маркер завршува давање мене. Така, сега имаме стап меморија на одборот што доби еден, два, три, четири, пет, шест, еден, два, три, четири, пет, шест, seven-- така 42 бајти на меморија на вкупно екранот. Ти благодарам. Да, не ми аритметички право. Значи 42 бајти меморија тука. Па што значи тоа всушност значи? Па, компјутерски програмер всушност, ќе се генерално мислам на тоа како адресибилен меморија. Со други зборови, секој еден од овие локации во меморија, хардвер, има единствена адреса. 

Тоа не е како комплекс како Еден Brattle Плоштад, Кембриџ, Масачусетс., 02138. Наместо тоа, тоа е само еден број. Ова е бајт бројот нула, ова е еден, ова е два, тоа е три, и ова е 41. Почекај минута. Мислев дека рече 42 пред еден миг. Почнав да бројам на нула, па тоа е всушност точни. Сега не треба да се, всушност, го подготви во облик на мрежа, и ако го нацрта тоа во облик на мрежа Мислам дека работите всушност, да се добие малку погрешно. Што програмер би, во неговиот или нејзиниот ум, генерално мислам на ова меморија е исто како на лента, како парче леплива лента тоа само продолжува и натаму засекогаш или додека не снема меморија. Значи, повеќе заеднички начин да се подготви и само се размислува за меморија ќе биде дека ова е бајт нула, еден, два, три, а потоа точка, точка, точка. И имаш вкупно 42 такви бајти, па дури и иако физички таа всушност може да да биде нешто повеќе вака. 

Значи, ако сега мислите дека на вашиот меморија што е оваа, како на лента, тоа е она што на програмерот повторно би го нарекол низа на меморија. И кога сакате да всушност складираат нешто во меморијата на компјутерот, обично се чува на работите назад-до-назад кон назад-до-назад. Значи ние сме биле зборува за бројки. И кога сакав да ги реши проблемите како четири, еден, три, два, иако бев само цртање само броевите четири, еден, три, две на табла, компјутерот ќе навистина треба ова подесување во меморијата. 

И она што ќе биде во близина на две во меморијата на компјутерот? Па, нема одговор на тоа. Ние навистина не знам. И така додека компјутер не е потребно, тоа не треба да се грижат што е следно на бројки, е заинтересиран за тоа. И кога реков претходно дека компјутер може да се погледне само на една адреса во еден момент, ова е вид на зошто. 

Не за разлика од евиденција плеер и главата за читање само да биде во можност да се погледне во одреден Мило ми е во физичка рекорд стар ков во исто време, на сличен начин може еден компјутер, благодарение на своите процесорот и неговите Интел настава во собата, меѓу чија настава се чита од меморија или да го зачувате до memory-- на компјутер може само да се погледне на едно место, на time-- понекогаш и комбинација од нив, но, навистина само едно место во исто време. Значи, кога ќе се прави овие различни алгоритми, Јас не сум само пишување во vacuum-- четири, еден, три, два. Овие бројки всушност припаѓаат некаде физичка меморија. Па така постојат малечки транзистори или некој вид од електроника под качулка складирање на овие вредности. 

И збирно, колку битови се вклучени во моментов, само за да биде јасно? Значи ова е четири бајти, или сега е 32 бита вкупно. Па таму се всушност 32 нули и единици оние компонирањето овие четири работи. Има дури и повеќе овде, но повторно не ми е гајле за тоа. 

Па сега ајде да прашам друго прашање со користење на меморијата, затоа што на крајот на денот е во варијанса. Без разлика на она што може да се направи со на компјутер, на крајот на денот хардверот е уште исто под хауба. Како можам да се складира збор тука? Па, еден збор на компјутер како "Еееј!" ќе се чуваат исто како и оваа. И ако си сакал подолг збор, можете едноставно да избрише тој и да каже нешто како "здраво" и продавница за тоа тука. 

И така тука, исто така, ова contiguousness всушност е предност, затоа што компјутерот може да се само читаат од десно кон лево. Но, тука е прашањето. Во контекст на овој збор, H-Е-Л-Л-О, фантастичен точка, како може на компјутер знае каде зборот почнува и каде зборот ќе заврши? Во контекст на броеви, како не на компјутер знам колку долго редоследот на броеви е или каде што почнува? Па, излегува out-- и нема да одат премногу во ова ниво на detail-- компјутери движат работите околу себе во меморијата буквално по пат на овие адреси. Значи во компјутер, ако сте пишување на код за да ги чувате работите како зборови, она што се навистина прави е пишување изрази, кои се сетам каде во меморијата на компјутерот овие зборови. Па дозволете ми да се направи многу, многу едноставен пример. 

Одам да се оди напред и да отвори едноставна програма текст, а јас ќе одам да се создаде датотека наречена hello.c. Поголемиот дел од оваа информација Нема да навлегувам во во голема детали, но јас ќе одам да се напише програма во тој ист јазик, C. Ова е далеку повеќе застрашувачки, Јас би рекол, од нула, но тоа е многу слични во духот. Всушност, овие кадрава braces-- може да се вид на мислам на она што јас само направив што е оваа. 

Ајде да го направите ова, всушност. Кога зелено знаме кликнато, го направите следново. Сакам да се печати "Здраво". Па сега тоа е pseudocode. Јас сум вид на замаглување на линии. Во C, овој јазик Зборувам за, оваа линија на печатење здраво всушност станува "printf" со некои загради и точка-запирка. 

Но, тоа е иста идеја. И тоа многу user-friendly "Кога зелено знаме кликнато" станува многу повеќе таинствени "int главната неважечки." И ова навистина нема мапирање, па јас сум само ќе го игнорираат тоа. Но, големите загради се како криви мозаик парчиња се допаѓа ова. 

Па можете да вид на се погоди. Дури и ако никогаш не сум програмиран пред тоа, она што оваа програма најверојатно да направам? Веројатно отпечатоци Здраво со фантастичен точка. 

Па ајде да се обидеме тоа. Одам да го спаси. И ова е, пак, многу стара училишна средина. Јас не може да кликнете, не можам да се повлечете. Морам да внесувате команди. Значи сакам да ја стартувате програмата, што значи Јас би можеле да го направите ова, како hello.c. Тоа е датотека истрчав. Но, чекај, јас сум недостасува чекор. Што ние велат дека е потребно чекор за јазик како C? Јас сум само пишан извор код, но она што ми е потребно? Да, јас треба компајлерот. Така, на мојот Mac тука, имам програма наречена GCC, GNU C компајлер, кој ми дозволува да се направи this-- пак мојот изворен код во, ние ќе го наречеме, машински код. 

И јас може да се види дека, повторно, како што следува, овие се нули и јас само создадена од мојот изворниот код, сите нули и единици. И ако сакам да се кандидира мојот program-- тоа се случува да се нарече a.out за историски reasons-- "здраво". Јас може да се кандидира повторно. Здраво, здраво, здраво. И се чини дека да се работи. 

Но, тоа значи некаде во мојата меморија на компјутерот се зборовите H-Е-Л-Л-О, извичник. И што излезе, исто како настрана, она што на компјутерот, вообичаено, би направите, така што тоа не знае каде работи на проектот и end-- тоа е ќе се стави посебен симбол тука. И Конвенцијата е да се стави број нула на крајот на некој збор така што ќе се знае каде всушност завршува, така што ќе не се задржи печатење на повеќе и повеќе ликови отколку што навистина имаат намера. 

Но, готова брза тука, дури и иако ова е прилично таинствени, е дека тоа е во крајна линија релативно едноставна. Сте биле дадени вид на лента, празна простор на кој може да се пишуваат писма. Вие едноставно треба да имаат посебен симбол, како произволно бројот нула, да се стави на крајот на Вашите зборови, така што компјутерот не знае, О, јас треба да престане печатење по Гледам точка на фантастичен. Бидејќи следниот нешто таму е ASCII вредност од нула, или нула карактер како некој ќе го наречеме. Но, има еден вид на проблем тука, и ајде да се врати назад на броеви за момент. Да претпоставиме дека јас не, всушност, имаат низа на броеви, и да претпоставиме дека програма што го пишувам како одделение книга на наставникот и наставниците во училница. И оваа програма им овозможува на него или неа да напишеш во оценките на нивните ученици на квизови. И да претпоставиме дека студентот добива 100 на првиот квиз, можеби како 80 на следниот, а потоа 75, а потоа 90 на четвртиот квиз. 

Значи во овој момент во приказната, низата е на големината на четири. Има апсолутно повеќе меморија во компјутер, но низа, така да се каже, е на големината на четири. Да претпоставиме сега дека наставникот сака да се додели една петтина квиз на класата. Па, една од работите што или таа се случува да треба да направите сега е да се сместат на дополнителна вредност тука. Но, ако низата наставникот има создадени во оваа програма е за големината за, еден од проблемот со низа е дека што не може само да ја задржите додавањето на меморија. Затоа што ако некој друг дел од Програмата има зборот "еј" таму? 

Со други зборови, мојата меморија може да биде се користи за ништо во програма. И ако однапред јас ја внеле во, еј, Сакам да го внесете четири квизот резултати, тие може да оди тука и тука. И ако одеднаш се промени вашиот ум подоцна и да се каже сакам една петтина квиз резултат, вие не само да го стави каде што сакате, затоа што ако тоа меморија се користи за нешто else-- некоја друга програма или некоја друга карактеристика на програмата дека сте водење? Значи мора да се размислува однапред како сакате да ги чувате вашите податоци, бидејќи сега сте насликани се во дигитален агол. 

Значи учител би можеле наместо каже кога пишување програма за чување на неговите или нејзините оценки, знаеш што? Одам да се бара, кога пишувате мојата програма, дека сакам нула, еден, два, три, четири, пет, шест, осум оценки вкупно. Така, еден, два, три, четири, пет, шест, седум, осум. Наставникот може само во текот на расподели меморија кога пишувате неговата или нејзината програма и да каже, знаеш што? Јас никогаш нема да се додели повеќе од осум квизови во еден семестар. Тоа е само луд. Никогаш нема да се доделат. Така што на овој начин тој или таа има флексибилност за да ја запази студент резултати, како 75, 90, а можеби и една дополнителна каде ученикот доби екстра кредит, 105. 

Но, ако никогаш не наставникот ги користи овие три места, има интуитивен готова брза тука. Тој или таа е само губење на простор. Значи со други зборови, не е ова заеднички Губитокот во програмирање каде што можете да ги распредели точно колку меморија како сакате, Добрата страна на тоа е дека сте супер efficient-- што не си се непотребното во all-- но во надолна линија, од кои е тоа што ако го промените вашиот ум кога користење на програмата што сакате да ги чувате повеќе податоци отколку што првично се наменети. 

Па можеби решението е, тогаш, напишете вашиот програми на таков начин кои тие ги користат повеќе меморија отколку што навистина треба. На овој начин не се случува да се кандидира во овој проблем, но сте се непотребното. И повеќе меморија вашата програма го користи, Како што разговаравме вчера, на помалку меморија, која е на располагање за други програми, толку побрзо вашиот компјутер може да се забави , бидејќи на виртуелна меморија. И така идеално решение би можело да биде тоа? 

Под-издвојување изгледа лошо. Над-издвојување изгледа лошо. Значи она што би можело да биде подобро решение? Пренасочување. Бидете повеќе динамичен. Не сила сами да се избере приори, на почетокот, она што сакам да. И, секако, не се над-одвои, да не би да биде губење на време. 

И така да се постигне таа цел, треба да се фрли оваа податочна структура, така да се каже, далеку. И така, програмер обично ќе ги користи е нешто што не е наречен низа, но листа на поврзани. Со други зборови, тој или таа ќе почнат да мислат на нивната меморија како вид на облик кој тие може да се подготви на следниов начин. Ако сакам да се сместат во еден број на program-- така што е септември, Јас сум со оглед на моите студенти квиз; сакам за чување на првиот квиз на учениците, и тие се здобија со 100 на it-- јас идам да прашам мојот компјутер, по пат на програмата сум напишано, за едно парче на меморија. И јас одам да ја запази број 100 во неа, и тоа е тоа. 

Потоа, неколку недели подоцна кога ќе се моето второ квиз, и тоа е време да напишеш со тоа што 90%, идам да побара од компјутер, еј, компјутер, Може ли уште едно парче на меморија? Тоа се случува да ми даде овој празни парче на меморија. Одам да се стави во број 90, но во мојата програма некако или other-- и ние не ќе се грижи за синтаксата на this-- ми треба некако синџирот овие работи заедно. И јас ќе ги синџирот заедно со она што изгледа како стрела тука. 

Третиот квиз што доаѓа, Јас ќе одам да се каже, еј, компјутер, Дај ми уште една парче на меморија. И јас одам да се спушти што и да е, како и 75, и јас треба да синџирот на овој заедно сега некако. Четврто квиз доаѓа заедно, а можеби и тоа е кон крајот на семестарот. И од тој момент мојата програма може да се користат меморија насекаде, во целиот физички. И така само за клоци, јас сум случува да се подготви овој натаму quiz-- го заборавам она што беше, јас дека можеби 80 или something-- начин овде. 

Но, тоа е во ред, бидејќи сликовито Одам да се подготви оваа линија. Со други зборови, во реалноста, во областа на хардверот на вашиот компјутер, на првиот резултат на сила завршуваат тука, бидејќи тоа е право на почетокот на семестарот. Следниот би можеле да завршат тука бидејќи малку време помина и програмата постојано работи. Следниот резултат, кој беше 75, може да биде овде. И последниот резултат може да биде 80, што е повеќе од тука. 

Така, во реалноста, физички, ова може да биде што меморијата на вашиот компјутер како изгледа. Но, тоа не е корисна ментална парадигма за компјутерски програмер. Зошто треба да се грижат каде што подлец вашите податоци се заврши? Вие само сакате да ја зачувате податоци. 

Ова е вид на како нашата дискусија порано за цртање на коцка. Зошто ви е гајле што аголот е на коцка и како треба да се претвори да го нацрта тоа? Вие само сакате коцка. Слично на тоа тука, само сакам да одделение книга. Вие само сакате да се размислува за ова како листа на броеви. Кој се грижи како тоа е спроведува во областа на хардверот? 

Значи апстракција сега е оваа слика овде. Ова е поврзана листа, како програмер би ја нарекол, доколку имате листа, очигледно на броеви. Но, тоа е поврзано сликовито по пат на овие стрели, и сите овие стрели are-- под капакот на моторот, ако сте љубопитни, потсетиме дека нашите физички хардвер има адреси нула, еден, два, три, четири. Сите овие стрели се е како мапа или насоки, каде што доколку 90 is-- сега Добив да се брои. 

Нула, еден, два, три, четири, пет, шест, седум. Тоа изгледа како на 90 години е во мемориска адреса бројот седум. Сите овие стрели се е како мало парче хартија дека е давање насоки на програма која вели следат оваа карта да стигнете до локацијата седум. И таму ќе ги најдете на вториот квиз резултат студентот. Во меѓувреме, 75-- ако продолжам ова, ова е седум, осум, девет, 10, 11, 12, 13, 14, 15. 

Овој други стрелка едноставно претставува карта на локација во меморијата 15. Но, повторно, програмер генерално не не се грижи за тоа ниво на детали. И во повеќето секој програмирање јазик и денес, на програмерот дури и не ќе знае каде во меморијата овие броеви всушност се. Сите тој или таа треба да се грижат за се дека тие се на некој начин поврзани заедно во податочна структура се допаѓа ова. 

Но, се покажа не да се добие премногу технички. Но, само затоа што можеби може да да си дозволи да ја имаат оваа дискусија овде, Да претпоставиме дека ние враќате овој проблем тука на низа. Ајде да видиме дали Жалиме случува тука. Ова е 100, 90, 75 и 80. 

Дозволете накратко да се направи ова тврдење. Ова е низа, и повторно, Истакнатите карактеристики на низа е дека сите на вашите податоци се назад до назад да се врати во memory-- буквално еден бајт или можеби четири бајти, некои фиксни број на бајти далеку. Во листа на поврзани, кои би можеле да се повлече вака, под хаубата кои знае каде тој звук е? Тоа дури и не треба да тече вака. Некои од податоците може да биде назад кон лево до таму. Вие дури и не знаат. 

И така со ред, имаш функција, познат како случаен пристап. И она што е случаен пристап е дека компјутерот може да скокне веднаш на било која локација во низа. Зошто? Затоа што компјутерот знае дека првата локација е нула, еден, два, три. 

И така, ако сакате да се оди од овој елемент на следниот елемент, вие буквално, во ум компјутерот, само додадете. Ако сакате да се оди на третиот елемент, само додадете one-- следниот елемент, само додадете. Сепак, во оваа верзија на приказната, да претпоставиме компјутер моментално е во потрага во или се занимаваат со бројот 100. Како да се дојде до следното одделение во одделение книга? 

Мора да се земе седум чекори, кој е произволен. За да се добие на следниот, ќе мора да се уште осум чекори за да добие до 15 години. Со други зборови, тоа не е постојан јаз меѓу броеви, и така тоа само зема компјутер повеќе време е поентата. Компјутерот мора да бараат преку меморија, со цел да се најде она што го барате. 

Па со оглед на низа има тенденција да биде structure-- брзо податоци, затоа што буквално може само да се направи едноставни аритметички и да добиете, каде сакате со додавање на една, за instance-- на поврзани листа, ќе го жртвува таа карактеристика. Вие не може да оди од првиот до втората од трето до четвртото место. Мора да се следат на сајтот. Вие мора да преземе повеќе чекори да се дојде до тие вредности, кои Се чини дека се додавајќи цена. Значи ние сме плаќаат цена, но она што беше функција која Дан беше бараат овде? Што прави поврзани листа очигледно ни овозможи да се направи, која е потеклото на ова особено приказна? 

Токму така. А динамичен големината на тоа. Ние можеме да додадете на оваа листа. Ние дури и може да се намали листата, па дека ние сме само да користи многу меморија како што ние, всушност, сакаат и така ние никогаш не сме над-издвојување. 

Сега само да биде навистина НИТ-picky, има скриени трошоци. Значи, вие не треба само да ме убеди вас дека ова е една огромна Губитокот. Има уште една скриени трошоци овде. Во корист, да биде јасно, е дека ние се динамика. Ако сакам друг елемент, јас само може да подготви него и го стави на број во таму. А потоа можам да ја водат со слика тука, со оглед на тоа овде, повторно, ако јас сум јас насликани во еден агол, ако нешто друго веќе е користење меморијата тука, јас сум надвор од среќа. Јас сум си насликани во аголот. 

Но она што е скриено чини во оваа слика? Тоа не е само на износот на времето што е потребно да одам од тука до тука, што е за седум чекори, а потоа осум чекори, што е повеќе од еден. Што е уште еден скриен цена? Не само време. Дополнителни информации се потребни за да се постигне оваа слика. 

Да, таа карта, тие мали парчиња хартија, како што се задржи опишувајќи ги како. Овие arrows-- оние кои не се бесплатни. А computer-- знаете што компјутер има. Таа има нули и единици. Ако сакате да ја претставува стрела или карта или број, треба некои меморија. Па на другата цената што плаќаат за список на поврзани, заеднички компјутерски науки ресурси, исто така е простор. 

И навистина е така, па најчесто, меѓу размени во процесот на дизајнирање на софтверското инженерство системи е време и space-- се две од вашиот состојки, две на својата повеќето скапи состојки. Ова ми се чини повеќе време бидејќи треба да го следи оваа карта, но тоа е, исто така, ме чини повеќе простор затоа што мора да се задржи оваа карта наоколу. Значи надеж, како што ние сме вид на дискутирано во текот на вчерашниот и денешниот ден, е дека придобивките ќе ги надминуваат трошоците. 

Но, нема очигледно решение овде. Можеби тоа е better-- a la брз и валкан, како Карим предложи earlier-- да се фрли меморија на проблемот. Само купи повеќе меморија, мислам помалку тешки за решавање на проблемот, и да ги реши на полесен начин. И навистина порано, кога ние разговаравме за размени, тоа не е простор во компјутер и време. Тоа беше време инвеститорот, кој е уште еден ресурс. 

Значи, повторно, тоа е оваа балансирање се обидува да се одлучи кои од тие работи подготвени да потрошат си? Кој е најмалку скап? Што дава подобри резултати? Да? 

Навистина. Во овој случај, ако сте претставуваат броеви во maps-- тие се нарекуваат во многу јазици "Совети" или "адреси" - што е двојно повеќе од простор. Тоа не треба да биде толку лоша како двојно повеќе Во моментов ние сме само чување на броеви. Да претпоставиме дека сме биле чување пациентот евиденција во hospital-- па имињата Пирсон е, телефонски броеви, броеви на социјално осигурување, лекар историја. Ова поле може да биде многу, многу поголем, во кој случај малечки покажувач, на адреса на следниот element-- тоа не е голема работа. Тоа е толку раб чини дека не е важно. Но, во овој случај, да, тоа е двојно зголемување. Добро прашање. 

Ајде да зборуваме за време на малку повеќе конкретно. Што е трчање време на од пребарувањето оваа листа? Да претпоставиме дека јас сакав да го бара преку сите оценки на учениците, и таму е n оценки во оваа податочна структура. Овде, исто така, може да се позајмуваат вокабуларот на претходно. Ова е линеарна структура на податоци. 

Биг О од n е она што е потребно за да до крајот на оваа структура на податоци, whereas-- и не сме виделе ова before-- низа ви дава она што се нарекува постојан време, што значи еден чекор или два чекори или 10 steps-- не е важно. Тоа е фиксен број. Таа не треба ништо да се направи со големината на низата. А причината за тоа, повторно, е случаен пристап. На компјутерот може само веднаш Скокни на друга локација, затоа што тие се сите исти Одалеченост од сè друго. Не постои размислување кои се вклучени. Во ред. Значи, ако можам да се обидам наслика две финалето слики. А многу чести и е позната како хаш табелата. Значи за да се мотивираат оваа дискусија, дозволете ми да мислам за тоа како да го направите тоа. 

Па, како за ова? Да претпоставиме дека проблемот сакаме да го решиме сега спроведува во dictionary-- па еден куп на англиски зборови или нешто друго. А целта е да се биде во можност да одговори прашања на формата е овој збор? Значи сакате да се спроведе на проверка на правопис, само како и физичко речникот кои може да се погледне на работите во. Да претпоставиме дека јас да го направите ова со низа. Јас би можеле да го направите тоа. 

И да претпоставиме зборовите се јаболко и банана и диња. И не можам да се сетам на овошје кои почнуваат со г, па ние сме само ќе има три плодови. Значи ова е низа, и ние сме складирање на сите од овие зборови во овој речник како низа. Прашањето, тогаш, е како на друго место би можеле да се сместат овие информации? 

Па, јас сум вид на мамење тука, затоа што секоја од овие букви во зборот е навистина индивидуална бајт. Значи, ако јас навистина сакаше да биде НИТ-picky, јас навистина треба да се дели на овој горе во многу помали делови од меморијата, а ние може да го направи токму тоа. Но, ние се случува да се кандидира во истиот проблем како порано. Што ако, како Merriam Webster или Оксфорд не секој year-- додаваат зборовите на dictionary-- ние не мора да сакаат да се наслика во еден агол со низа? 

Така, наместо, можеби попаметен приод е да се стави на Apple во своите јазол или кутија, како што би рекле, банана, и тогаш тука имаме диња. И ние низа овие работи заедно. Значи ова е низа, и ова е поврзана листа. Ако не сосема може да се види, тоа само вели: "низа", а тоа вели: "листа". 

Значи ние треба исто Точниот прашања како и досега, при што сега имаме динамика во нашата листа поврзани. Но ние имаме прилично бавен речникот. Да претпоставиме дека сакам да се погледне до зборот. Тоа би можело да ми се големи О од n чекори, бидејќи зборот би можел да бидат сите на начин на крајот на листата, како диња. И излегува дека во програмирање, вид на светиот грал на податоци структури, е нешто кој ви дава постојана време како низа но дека се уште ви дава динамика. 

Значи ние можеме да го имаат најдоброто од двата света? И навистина, има нешто наречен хаш табелата кој ви овозможува да го прават токму дека, иако околу. Хаш табелата е познавач структура на податоците кои ги може да го сметаме како комбинација на една array-- и јас одам да го нацрта како this-- и поврзани листи дека ќе се повлече како овој овде. 

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

Па со оглед на зборовите од јаболко и банана и диња, Јас намерно избра овие зборови. Зошто? Што е еден вид на основа различно за три? Што е очигледно? Тие почнуваат со различни букви. 

Па да знаете што? Наместо да се стави сите мои зборови во исто кофа, така да се каже, како во една голема листа, зошто да не Јас барем да се обидат оптимизација и направи мојот листи 1/26 толку долго. А краен оптимизација може да биде зошто не I-- при внесување на збор во оваа податочна структура, во меморијата на компјутерот, зошто не го ставам сите 'а' зборови тука, сите зборови "b" тука, и сите "c" зборови тука? Значи ова завршува ставање јаболко тука, тука банана, диња тука, и така натаму. 

И ако имам дополнителни зборот like-- што е друг? Јаболко, банана, круша. Секој мисли на овошје која започнува со a, b, c или? Blueberry-- совршена. Тоа се случува да се заокружи тука. И така ние се чини дека имаат малку подобро решение, затоа што сега ако сакам за да пребарувате за Apple, јас first-- јас не само нурне во мојот податоци структура. Јас не се нурне во меморијата на компјутерот ми е. Јас прв пат се погледне на првата буква. 

И тоа е она што на компјутер научник би рекол. Вие хаш во вашите податоци структура. Ќе се земе вашиот влез, кои во овој случај е збор како јаболко. Можете да го анализира, да гледа во на првата буква во овој случај, а со тоа hashing. Hashing е општ термин со кој ќе се земе нешто како влез и ќе се произведуваат некои излез. И излез во тој случај е локацијата сакате да пребарувате, првиот локација, втората локација, на третото место. Значи влезот е јаболко, излезот е во прв план. Влезот е банана, на излезот треба да биде втор. Влезот е диња, излезот треба да биде на третото место. Влезот е боровинки, на излез треба повторно да биде втор. И тоа е она што ви помага да се Кратенки преку вашата меморија со цел да се дојде до зборови или податоци поефикасно. 

Сега тоа намалување на одредување на нашето време потенцијално од колку што е еден од 26, затоа што ако се претпостави дека ќе има толку многу "а" зборови како "Z" зборови како зборови на "П", кој не е навистина realistic-- ви се случува да имаат искривувања низ одредени букви од alphabet-- но ова ќе биде постепена пристап кој не дозволува да се добие на зборовите на многу побрзо. И во реалноста, на еден софистициран програма, Googles на светот, на Фејсбук кои на world-- тие ќе го користат хаш табелата за многу различни цели. Но, тие не би биле толку наивни само да се погледне на првата буква во јаболко или банана или круша или диња, бидејќи, како што може да се види овие листи се уште може да се добие долго. 

И така ова се уште може да се вид на linear-- така вид на бавно, како и со голема О од n што зборувавме порано. Значи она што вистински добар хаш табелата ќе do-- тоа ќе има многу поголема низа. И тоа ќе се користи многу повеќе софистицирани функција hashing, така што тоа не само погледнете во "А". Можеби тоа изгледа на "А-P-P-л-е" и на некој начин се претвора овие пет букви во локацијата каде што Apple треба да се чуваат. Ние сме само наивно користење на буквата "а" сам, затоа што тоа е убав и едноставен. 

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

Но сфати колку брзо овој вид на дискусија ескалираше, или толку далеку што тоа е вид на над глава во овој момент, кој е во ред. Но, ние започна, да се потсетиме, со вистински нешто на ниско ниво и електронски. И така ова повторно е ова Темата на апстракција, кога еднаш ќе почнете да ги преземат за готово, во ред, јас сум it-- стигнавме таму е виртуелна меморија, во ред, разбрав, секој физичка локација има адреса, Добро, јас го зедов тоа, што може да претставува тие адреси како arrows-- можете многу брзо да почне да имаат пософистицирани разговори кои на крајот се чини дека се ни овозможи за решавање на проблеми како што се пребарување и сортирање поефикасно. И остатокот увери, too-- бидејќи сметам дека ова е најдлабокото ние сме поминале во некои на овие CS теми proper-- имаме направи во еден ден и половина на овој истакне она што вообичаено може да се направи во текот текот на осум недели во еден семестар. 

За било какви прашања во врска со овие? Не? Во ред. Па, зошто да не се откажеш таму, започне ручек неколку минути порано, продолжи и во само за еден час? И јас ќе траат малку со прашања. Тогаш јас ќе одам да мора да одат да потрае неколку повици ако тоа е во ред. Јас ќе се сврти на некоја музика во меѓувреме, но ручек треба да биде околу аголот.