DAVID Маланом: Хорошо. Мы вернулись. Так что в этом сегменте по программированию, что Я думал, что мы делаем это сочетание вещей. Во-первых, сделать немного о чем-то руки-на, хотя и с использованием более игривый программирование environment-- тот, который является показательным из именно те виды идей мы говорим о том, но немного более формально. Во-вторых, посмотрите на некоторые из тем более технические способы что программист будет на самом деле решить Проблемы, как в поисках проблемы что мы рассмотрели до и также более фундаментально интересная проблема сортировки. 

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

Так что давайте делать практический части первой. Так что просто получить ваши руки грязные с окружающая среда называется scratch.mit.edu. Это инструмент, который мы используем в нашем университетском классе. Несмотря на то, что он предназначен для лиц до 12 лет и старше, мы используем его для вверх часть этого совсем немного так как это приятно, весело Графический способ обучения кое-что о программировании. Так голова к этому URL, где вы должны увидеть страницу совсем так, и идти вперед и нажмите Присоединяйтесь к царапинам в верхнем правом углу и выберите имя пользователя и пароль и в конечном итоге получить себе account-- scratch.mit.edu. Я думал, что использовать это как возможность впервые показать это. Вопрос подошел во время перерыва о том, что код на самом деле выглядит. И мы говорили во время перерыва о С, в частности particular-- более низкий уровень в более старом языке. И я просто сделал быстрый Google поиск, чтобы найти код C для двоичного поиска, алгоритм, который мы используется для поиска этой телефонной книги раньше. Этот конкретный пример, конечно же, не ищет телефонную книгу. Он просто ищет целую кучу Числа в памяти компьютера. Но если вы хотите, чтобы просто получить визуальное ощущение того, что фактическое программирование язык выглядит, это выглядит немного что-то вроде этого. Так что речь идет о 20-плюс, 30 или около того строк кода, но разговор мы имели более перерыва был о том, как это на самом деле получает трансформировалось в нулей и единиц и если вы не можете просто вернуться, что обрабатывать и идут от нулей и единиц обратно в код. 

К сожалению, процесс настолько преобразовательный что это намного легче сказать, чем сделать. Я пошел вперед и на самом деле оказалось что программа, бинарный поиск, в нули и единицы в форме присоединения Программа под названием компилятор, что я случается, есть здесь прямо на моем Mac. И если вы посмотрите на экран здесь, обратив особое внимание на этих средних шести колонн только, вы увидите только нули и единицы. И те нули и единицы, которые составить именно эту программу поиска. 

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

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

Так что это очень легко получить потеряли в сорняков быстро. И есть много синтаксические проблемы причем, если вы сделаете самый простой, глупое опечаток никто из программы будет работать вообще. И поэтому вместо того, чтобы использовать язык, как C этим утром, Я думал, что это было бы больше удовольствия на самом деле делать нечто большее, визуальное восприятие, в то время как предназначены для детей на самом деле является совершенным проявлением фактического программирования language-- как раз случается использовать изображения вместо текста чтобы представить эти идеи. 

Поэтому, как только вы на самом деле иметь счет на scratch.mit.edu, нажмите кнопку Создать в левом верхнем углу сайта. И вы должны увидеть окружающую среду как один я собираюсь видеть на моем экране Вот. И мы потратим немного немного времени, играя здесь. Давайте посмотрим, если мы не можем все решить некоторые проблемы вместе следующим образом. 

Так что вы увидите в этом environment-- и на самом деле просто дайте мне паузу. Кто-нибудь не здесь? Не здесь? ОК. Итак, позвольте мне отметить несколько Характеристики этой среды. 

Таким образом, в верхнем левом углу экрана, мы есть стадия чистого листа, так сказать. Царапины не только имя этого языка программирования; это также имя кота, вы видите, по умолчанию там в оранжевый цвет. Он находится на сцене, так так же, как я описал черепаха ранее как в прямоугольная белая доска окружающая среда. Мир этой кошки ограничивается исключительно на этот прямоугольник наверху там. 

В то же время, справа правая часть здесь, это только область скрипты, чистого листа, если вы будете. Именно здесь мы будем писать наши программы в мгновение. И строительные блоки, которые мы использовать, чтобы написать это program-- головоломки штук, если вы will-- являются те, прямо здесь, в центре, и они классифицируются по функциональности. Так, например, я собираюсь идти вперед и продемонстрировать, по крайней мере, один из них. Я собираюсь идти вперед и нажмите категория управления наверху. 

Так что эти категории до вершины. Я собираюсь нажать категорию управления. Скорее всего, я буду нажимать на события категория, самый первый наверху. И если вы хотите следовать даже как мы делаем это, вы очень добро пожаловать. Я собираюсь нажать и перетащить этот Первый из них, "когда зеленый флаг щелкнул". А потом я собираюсь бросить его просто примерно в верхней части моих пустых сланцы. 

И что приятно о пустом месте является то, что этот кусок головоломки, когда взаимосвязанный с другой головоломки штук, собирается сделать буквально что эти кусочки головоломки говорят делать. Так, например, Царапины прав сейчас в середине своего мира. Я собираюсь идти вперед и выбрать Теперь, скажем, категория движения, если вы хотите сделать same-- категории движения. А теперь обратите внимание у меня есть целый куча головоломки здесь что, опять же, делать вид, что они говорят. И я собираюсь идти вперед и перетащить уронить блок двигаться прямо здесь. 

И обратите внимание, что, как только вы получите близко к нижней части "зеленый флаг нажал "кнопку, уведомление как появляется белая линия, как будто это почти магнитные, он хочет поехать туда. Просто отпустить, и он будет хватать вместе и формы будут совпадать. И теперь вы можете, возможно, почти угадать, где мы собираемся с этим. 

Если вы посмотрите на сцену Скретч здесь и смотреть в верхней части его, вы увидите красный свет, знак остановки, и зеленый флаг. И я собираюсь идти вперед и смотреть мои screen-- на мгновение, если бы вы могли. Я собираюсь нажать зеленый флаг прямо сейчас, и он переехал, что, как представляется, 10 шагов или 10 пикселей, 10 точек, на экране. 

И так не так интересно, но позвольте мне предложить даже не учил этому, просто используя свой собственный intuition-- пусть я предлагаю вам выяснить, как сделать Царапины прогулку прямо со сцены. Были ли ему сделать путь для правой стороны экран, весь путь направо. Позвольте мне дать вам момент или так, чтобы бороться с этим. Вы можете захотеть взглянуть на другие категории блоков. Отлично. Так что просто резюмировать, когда мы имеем зеленый флаг нажав здесь и двигаться 10 шагов является только инструкция, каждый раз, когда я нажмите зеленый флаг, что происходит? Ну, это работает моя программа. Так что я мог бы сделать это может быть в 10 раз вручную, но это чувствует себя немного немного хаком, так сказать, в результате чего я на самом деле не решение проблемы. Я просто пытаюсь снова и Снова и снова и снова пока я вроде случайно достичь директивы что я намеревался достичь ранее. 

Но мы знаем из нашего псевдокод раньше, что есть это понятие в программировании зацикливание, делать что-то снова и снова. И вот я увидел, что связка из вас потянулся за то, что кусок головоломки? Повторяйте до тех пор. Таким образом, мы могли бы сделать что-то как повторять до. И не то, что вы повторить, пока точно? 

ОК. И позвольте мне пойти с тот, который несколько проще всего на мгновение. Позвольте мне идти вперед и делать это. Обратите внимание на то, что, как вы, возможно, обнаружил под контролем, есть этот повтор блок, который не выглядит, как будто это что большой. Там не так много места в между этими двумя желтыми линиями. Но так как некоторые из вас, возможно, заметили, если вы перетащить, обратите внимание, как он растет, чтобы заполнить форму. 

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

Сейчас некоторые из вас предложили в качестве Виктория просто, повторите 10 раз. И что вообще делает получить его весь путь, Но разве не было бы более надежным способ, чем произвольно выяснить, сколько ходов сделать? Что может быть лучше блок чем повторить 10 раз быть? 

Да, так почему бы не сделать что-то навсегда? А теперь позвольте мне перенести этот кусок головоломки внутри там, и избавиться от этого. Теперь обратите внимание независимо от того, где Царапина начинается, он идет к краю. И к счастью MIT, который делает нуля, просто не гарантирует, что он никогда полностью исчезает. Вы всегда можете схватить его за хвост. 

И точно так же интуитивно, Почему он продолжает двигаться? Что здесь происходит? Он, кажется, остановилось, но а затем, если я поднимаю и перетащить он продолжает хотеть идти туда. Почему это? Действительно, компьютер буквально собирается делать то, что вы скажете ей сделать. Так что, если вы сказали это раньше сделать следующая вещь навсегда, двигаться 10 шагов, это будет продолжать идти и идти пока я не ударил красный знак стоп и остановить программу в целом. 

Так что даже если вы этого не сделали сделать это, как я мог сделать Царапины двигаться быстрее по экрану? Другие шаги, не так ли? Таким образом, вместо того, чтобы делать 10 в то время, почему бы нам не идти вперед и изменить его, целью которых что бы вы propose-- 50? Так что теперь я собираюсь нажать зеленый флаг, и на самом деле, он идет очень быстро. 

И это, конечно же, это просто проявление анимации. Что такое анимация? Это просто показывает вам человека A целая куча неподвижных изображений на самом деле, на самом деле, очень быстро. И поэтому, если мы просто рассказываю ему двигаться больше шагов, мы просто имея эффект быть изменение, где он находится на экране все более быстро за единицу времени. 

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

Да. Так что нам нужно какое-то состояния, и мы как представляется, имеют условными, так говорят, под категорию управления. Какой из этих блоков мы, вероятно, хотите? Да, возможно, "если, то". Так заметить, что среди желтых блоков мы имеем здесь, есть это "если" или это ", если еще" блок, который будет позволяют нам принять решение, чтобы сделать это или сделать это. И вы даже можете их гнездо сделать несколько вещей. Или, если вы не прошли еще здесь, идти вперед к категории Sensing и-- давайте посмотрим, если он здесь. 

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

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

кто-то хотел бы предложить, как я может соединить их, может быть, сверху вниз для того, чтобы решить проблему наличия Царапина движение справа налево направо слева направо, налево, каждый Время как раз отражаясь от стены? Что я хочу сделать? Какой блок я должен подключиться к "Когда зеленый флаг щелкнул первый"? 

ОК, так что давайте начнем с «навсегда». То, что происходит внутри дальше? Кто-нибудь другой. OK, двигаться шаги. Отлично. И что? Так то если. И обратите внимание, даже если это выглядит зажатой вместе плотно, он просто будет расти, чтобы заполнить. Это будет просто прыгать в том, где я хочу. 

И что же я ставлю между ИФ и тогда? Возможно ", если вы прикасаетесь край». И заметьте, опять же, это слишком большой для нее, но она будет расти, чтобы заполнить. А затем повернуть на 15 градусов? Сколько градусов? Да, так что 180 будет вращаться меня все наоборот. Итак, давайте посмотрим, если я получил это право. Позвольте мне уменьшить изображение. 

Позвольте мне перетащить наскрести. Таким образом, он немного искажается сейчас, но это нормально. Как я могу сбросить его легко? Я собираюсь немного обмануть. Таким образом, я добавил еще один блок, просто чтобы быть ясным. Я хочу, чтобы он указывает на 90 градусов вправо по умолчанию, так что я просто хочу, чтобы сказать ему, сделать это программно. И здесь мы идем. Мы, кажется, сделали это. Это немного странно, потому что он идет с ног на голову. Давайте назовем, что ошибка. Это ошибка. Исправлена ​​ошибка, ошибка в программе, а логическая ошибка, что я, человек, сделал. Почему он собирается с ног на голову? Оказалась MIT завинтить или я? 

Да, я имею в виду, это не в MIT неисправность. Они дали мне кусок головоломки что говорит повернуть некоторое количество градусов. И по предложению Виктории, Я превращаюсь на 180 градусов, который является правильным интуиция. Но поворот на 180 градусов в буквальном смысле означает поворот на 180 градусов, и это на самом деле не что я хочу, по-видимому. Потому что, по крайней мере, он в это двумерная мир, так что поворот действительно происходит чтобы перевернуть его с ног на голову. 

Я, вероятно, хотите, чтобы использовать то, что блок вместо того, чтобы, основываясь на то, что вы видите здесь? Как мы можем это исправить? Да, таким образом, мы могли бы указать в противоположном направлении. И на самом деле даже это не будет достаточно, потому что мы можем только жесткий код чтобы указывать влево или вправо. 

Вы знаете, что мы можем сделать? Похоже, что у нас есть удобный блок здесь. Если я приближать см то, что мы, как здесь? Так это выглядит, как MIT имеет абстракция построена здесь. Этот блок представляется эквивалентным к которым другие блоки, множественное число? 

Этот блок представляется эквивалентным ко всей этой тройке блоков что мы имеем здесь. Так получается, что я могу упростить свою Программа, избавившись от всего этого и просто поставить это здесь. А теперь он еще немного глючит, и это нормально сейчас. Мы оставим это будет. Но моя программа даже проще, и это тоже, будет представитель гола в programming-- это в идеале сделать свой код, просто, как можно более компактным, в то же время, как читаемым, насколько это возможно. Вы не хотите, чтобы сделать это так лаконичен что это трудно понять. 

Но обратите внимание, я заменил три блока с одним, и это, возможно, хорошая вещь. Я абстрагируются понятие проверки, являетесь ли Вы на краю с помощью только одного блока. Теперь мы можем получать удовольствие с этим, на самом деле. Это не добавляет столько интеллектуальные ценности, но игривая значение. Я собираюсь идти вперед и захватить этот звук здесь. Итак, позвольте мне идти вперед, и пусть меня остановить программу на мгновение. Я собираюсь записать следующее, обеспечивая доступ к моему микрофону. 

Вот так. Уч. Давайте попробуем это снова. Вот так. ОК, я записал неправильные вещи. Вот так. Уч. Уч. Отлично. Теперь мне нужно, чтобы избавиться от этого. Отлично. 

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

Да, обратите внимание, что это за пределами что желтый блок. Так что это тоже было бы ошибка, но я заметил это. Так что я собираюсь тащить его сюда, и заметьте, теперь это внутри «если». Так что "если" это своего рода одноименных руки, как блоттинга что только собирается делать то, что внутри него. Так что теперь, если я отдалить в риск annoying-- 

КОМПЬЮТЕР: Ой, ой, ой. 

DAVID Маланом: И будет просто продолжаться вечно. Теперь просто ускорить вещи здесь, позвольте мне идти вперед и открыть, давайте say-- отпустить меня в какой-то моего собственного материала от класса. И позвольте мне открыть, скажем, это один сделанный одним из наших обучающих товарищей Несколько лет назад. Так что некоторые из вас могут вспомнить эта игра от прошлых лет, и это на самом деле замечательно. Несмотря на то, что мы сделали Простейшим программ прямо сейчас, давайте рассмотрим, что это на самом деле выглядит. Позвольте мне ударил играть. 

Так что в этой игре, у нас есть лягушки, и с помощью стрелки keys-- он принимает большие шаги, чем я remember-- У меня есть контроль над этой лягушки. И цель состоит в том, чтобы получить через занятый Дорога без запуска в автомобилях. И давайте see--, если я иду здесь, я придется ждать, пока журнал для прокрутки по. Это чувствует, как ошибка. Это своего рода ошибка. Отлично. Я на это здесь, там, а затем вы держите идти, пока не получите все лягушки в кувшинок. Теперь это может выглядеть все более сложными, но давайте попробуем разбить это вниз мысленно и устно на составные блоки. Так что, вероятно, головоломка часть, которую мы еще не видели но это реагирует на нажатие клавиш, к вещам, я ударил по клавиатуре. 

Так что там, наверное, какая-то блок, который говорит, если ключ равен вверх, затем сделать что-то с Scratch-- возможно переместить его 10 шагов таким образом. Если вниз клавиша нажата, двигаться 10 шагов таким образом, или левая клавиша, двигаться 10 шагов Таким образом, 10 шагов, которые. Я четко повернул кошку в лягушку. Так вот именно там, где костюм, как черновик звонки it-- мы только что импортировали картину лягушки. 

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

Motion, sure-- так переместить блок, наверняка. И то, что этот шаг блок внутри, скорее всего? Да, какой-то цикл, может быть, навсегда заблокировать, возможно повторение block-- повторять до блока. И вот что делает журналы и кувшинок и все остальное движение назад и вперед. Это просто происходит бесконечно. 

Почему некоторые из автомобилей двигаться быстрее, чем другие? Что отличает этих программ? Да, вероятно, некоторые из них принимают больше шагов сразу и некоторые из них меньше шагов сразу. И визуальный эффект очень быстро по сравнению с медленным. 

Как вы думаете, что случилось? Когда я получил мою лягушку весь путь через дорогу и реку на лилии площадку, что-то Примечательно, произошло. То, что произошло, как только я сделал это? Она остановилась. Эта лягушка остановилась, и Я получил вторую лягушку. Так что конструкция должна быть используется там, какая функция? 

Да, так что есть какая-то "Если" состояние там, тоже. И получается out-- мы не увидели this-- но есть и другие блоки там Можно сказать, если вы прикасаетесь Другое дело, на экране, если вы прикасаясь к кувшинки ", а затем". И тогда, когда мы сделать второй лягушки появляются. Так что, хотя эта игра, безусловно, очень устарели, хотя на первый взгляд есть так много происходит on-- и Блейк не хлестать это в две минуты, он, вероятно, взял его несколько часов, чтобы создать эту игру основанный на его памяти или видео версии вчерашнего дня о нем. Но все эти мелочи происходит на экране в изоляции сводятся к ним очень просто constructs-- движения или заявления как мы уже обсуждали, петли и условия, и именно об этом. Там в несколько других особенностей любитель. Некоторые из них являются чисто эстетические или акустические, как звуки я просто играл. Но по большей части, вы есть в этом языке, на пустом месте, все фундаментальные строительные блоки, которые вам есть в C, Java, JavaScript, PHP, Ruby, Python, и любое количество других языков. Любые вопросы на пустом месте? Отлично. Поэтому мы не будем погружаться глубже поцарапать, хотя вы всегда можете в эти выходные, особенно если у вас есть дети или племянницы и племянники и такие, познакомить их с нуля. Это на самом деле удивительно игривый среда с, как говорят его авторы, очень высокие потолки. Несмотря на то, что мы начали с очень низкоуровневых деталей, вы действительно можете сделать совсем немного с ним, и это, пожалуй, демонстрация именно это. 

Но давайте теперь перейти к некоторым более сложные проблемы, если вы будете, известный как "поиск" и "Сортировка" в более общем плане. У нас была эта телефонная книга earlier-- здесь еще один раз для discussion-- что мы смогли найти более эффективно, потому что значительного предположения. И просто быть понятно, что Предполагалось, что делает я при поиске через эту телефонную книгу? Это Майк Смит был в телефонная книга, хотя я будет иметь возможность обрабатывать сценарий без него там, если я просто остановился преждевременно. Книга в алфавитном порядке. И это очень щедрый предположение, потому что означает someone-- Я вроде резки угол, как я быстрее, потому что кто-то еще сделал много тяжелой работы для меня. 

Но что, если телефон Книга была НЕСОРТИРОВАННАЯ? Может быть, Verizon стал ленивым, просто бросил имена и номера каждого в там может быть, в том порядке, в котором они подписался на телефон службы. А сколько времени занимает меня чтобы найти кого-то вроде Майка Смита? 1000 страница телефон book-- сколько страницы я должен просмотреть? 

Все они. Ты вроде не повезло. Вы буквально должны смотреть на каждый страница, если телефонная книга просто случайным образом сортируются. Вы можете получить повезло и найти Mike на самой первой странице, потому что он был первым заказчиком заказать услугу по телефону. Но он, возможно, был последним, тоже. 

Так в случайном порядке не хорошо. Поэтому предположим, что мы должны сортировать Телефонная книга или в общих данных сортировки что мы дали. Как мы можем сделать это? 

Что ж, позвольте мне попробовать простой пример здесь. Позвольте мне идти вперед и бросить Несколько номеров на доске. Пусть числа у нас есть есть, скажем, четыре, два, один и три. И, Бен, сортировать эти цифры для нас. 

Хорошо. Как ты это сделал? Отлично. Так что начните с самым маленьким значение и высокий, и это действительно хорошая интуиция. И понимаем, что мы люди на самом деле довольно хорошо на решение проблем как это, по крайней мере, когда данные относительно мала. Как только вы начинаете иметь сотни чисел, тысячи чисел, миллионы чисел, Бен, вероятно, не мог сделать это достаточно быстро, что, если предположить, что существуют пробелы в цифрах. Довольно легко подсчитать до миллиона в противном случае просто отнимает много времени. 

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

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

Там два. Подожди минуту. Два меньше четырех. Я буду помнить. Два в настоящее время является наименьшим. Теперь одно-- это еще лучше. Это даже меньше. Я собираюсь забыть о двух и просто вспомнить его сейчас. 

И он мог перестать смотреть? Ну, он мог на основе на этой информации, но он лучше бы поиск остальная часть списка. Потому что, если ноль были в списке? Что делать, если отрицательный были в списке? Он знает только, что его ответ является правильным, если он исчерпывающе проверил весь список. Таким образом, мы смотрим на остальной части этого. Three--, что это пустая трата времени. Не повезло, но я был до сих пор правильно сделать это. И вот теперь он, вероятно, выбирается наименьшее число и просто положить его в начале из списка, как я буду здесь делать. Теперь то, что вы делали дальше, несмотря на то, Вы не думали об этом почти до такой степени? Повторите этот процесс, поэтому какой-то цикл. Там знакомая идея. Так вот четыре. Это в настоящее время самый маленький. Это кандидат. Уже нет. Теперь я видел два. Это следующий наименьший элемент. Three--, что не меньше, так Теперь Бен может вырывать два. 

И теперь мы повторяем процесс, а конечно три получает вытащил следующий. Повторите процесс. Четыре получает вытащил. А теперь мы из чисел, так что список должен быть отсортирован. 

И в самом деле, это формальный алгоритм. Компьютер ученый будет называем это "выбор рода" идея в том, сортировать по список iteratively-- снова и снова и снова выбор наименьшее число. И что приятно о нем это просто так чертовски интуитивным. Это так просто. И вы можете повторить то же самое операция снова и снова. Это просто. 

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

Предположим, что существуют числа там. Опять же, не имеет значения, что они есть, но они случайным образом. Я применяю алгоритм Бен. Мне нужно, чтобы выбрать наименьшее число. Что я делаю? И я собираюсь физически сделать это на этот раз, чтобы действовать его. Глядя, глядя, глядя, глядя, глядя. Только к тому времени я получаю конец списка может Я понимаю, что самый маленький число было два на этот раз. Один не в списке. Так что я положил два. 

Что делать дальше? Глядя, глядя, глядя, глядя. Теперь я нашел номер семь, потому что есть пробелы в этих numbers-- а просто произвольно. Отлично. Так что теперь я могу положить вниз семь. Глядя глядя, глядя. 

Теперь я предполагаю, из Конечно же, что Бен не имеют дополнительную оперативную память, дополнительные память, потому что, конечно же, Я смотрю на тот же номер. Конечно, я мог бы помнить, все эти цифры, и это абсолютно верно. Но если Бен помнит все из номера, которые он видел, он на самом деле не сделал фундаментальный прогресс потому что у него уже есть возможность поиска по номерам на доске. Вспоминая все из номера не помогает, потому что он все еще может как компьютер только смотреть, мы уже говорили, один номер вовремя. Так что нет никакого рода читов там, что вы можете использовать. 

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

Так что давайте думать о сколько шагов я на самом деле тащась через каждый раз. В первой ситуации у нас было 16 номеров, и так maximally-- давайте просто сделать это для discussion-- Я должен был смотреть через 16 лет номера, чтобы найти самый маленький. Но как только я исторгли наименьшее число, как долгое время был оставшийся список, конечно? Только 15. Так сколько чисел сделал Бен или у меня есть полистать во второй раз вокруг? 15, просто пойти и найти самый маленький. Но теперь, конечно, список, тоже меньше, чем это было раньше. Так сколько шагов сделал я должны взять на себя в следующий раз? 14, а затем 13, а затем 12, плюс точка, точка, точка, пока я не останется только один. Так что теперь компьютерный ученый будет спросите, ну, что же, что все равны? Это на самом деле равно некоторые конкретные число, которое мы могли бы, конечно, делать арифметически, но мы хотим поговорить об эффективности алгоритмов чуть более formulaically, не зависит от того, как долго этот список. 

И вы знаете, что? Это 16, но как я уже сказал раньше, давайте просто назвать размер проблемы п, где п некоторое число. Может быть, это 16, может быть, это три, может быть, это миллион. Я не знаю. Я не забочусь. То, что я действительно хочу, формула, я могу использовать для сравнения этот алгоритм против других алгоритмов что кто-то может претендовать лучше или хуже. 

Так что получается, и я только знаю, что это из начальной школы, что это на самом деле работает, к тому же вещь, как п по п плюс один больше двух. И это происходит в равных условиях, Конечно же, п квадрат плюс п над ними. Так что, если я хотел формулу На сколько шагов были вовлечены в глядя на все о снова и снова эти цифры и снова и снова, я бы сказал, это п квадрат плюс п над ними. Но вы знаете, что? Это просто выглядит неаккуратно. Я просто очень хочу Общий смысл вещей. И вы можете вспомнить из средней школы, что там является понятие термина высшего порядка. Какой из этих терминов, п квадрат, русский, или половину, имеет наибольшее влияние с течением времени? Чем больше п получает, что из этих вопросов больше всего? 

Другими словами, если я подключу на миллион, п квадрат будет, скорее всего, доминирующим фактором, потому что в миллион раз сама по себе намного больше чем плюс один дополнительный миллион. Таким образом, вы знаете, что? Это такая большая штопка номер, если вы квадратуры номер. Это не имеет никакого значения. Мы просто крест, , и забыть об этом. И поэтому ученый сказал бы что эффективность этого алгоритма составляет порядка п squared-- Я имею в виду действительно приближение. Это своего рода грубо п в квадрате. С течением времени, тем больше и больше п получает, это является хорошей оценкой для того, что эффективность или отсутствие эффективности этого алгоритма на самом деле. И я получить, что, конечно же, от фактически делает математику. Но теперь я просто махал мои руки, потому что я просто хотите общий смысл этого алгоритма. 

Таким образом, используя ту же логику, тем временем, давайте рассмотрим другой алгоритм мы уже рассмотрели at-- линейный поиск. Когда я искал для телефона book-- не сортировать ее, поиск через телефонную book-- мы продолжали говорить, что это было 1000 шагов или 500 шагов. Но давайте обобщим это. Если есть п страниц телефонная книга, что бегущая время или эффективность линейного поиска? Это на порядок сколько шагов, чтобы найти Майк Смит, используя линейный поиск, то Первый алгоритм, или даже второй? 

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

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

Так что 1000 страница Телефонная книга может взять нас 500 страниц поворотов, плюс один если мы загнуть немного. Так что, если телефонная книга имеет п страниц, но мы делаем две страницы в то время, это примерно то, что? N более чем два, так что как п над ними. Но я сделал требовать минуту назад, что п над two-- это своего рода такой же, как только п. Это просто постоянный множитель, компьютерные ученые сказали бы. Давайте акцентировать внимание только на переменные, really-- самые большие переменные в уравнении. 

Таким образом, линейный поиск, то ли сделал один страницы в то время, или две страницы в то время, является своего рода принципиально то же самое. Это по-прежнему порядка п. Но я утверждал с моим изображением ранее что третий алгоритм не был линейный. Это была не прямая линия. Это было то, что изогнутые линии, и алгебраическая формула была что? Журнал так войти N-, основание два п. И мы не должны вдаваться в много деталей на логарифмов сегодня, но большинство компьютерных ученых не будет даже сказать вам, что база. Потому что это все просто постоянными факторами, так сказать, только незначительные числовые различия. И вот это было бы очень распространенным явлением способ особенно формального компьютера научные работники на доске или программисты белой доски на самом деле утверждая, который Алгоритм они будут использовать или то, что коэффициент полезного действия из их алгоритм. 

И это не обязательно что-то вы будете обсуждать в любом деталях, но хороший программист кто-то который имеет солидный, формальный фон. Он в состоянии говорить Вы в этом виде пути и на самом деле сделать качественные аргументы, почему один алгоритм или одна часть программного обеспечения превосходит в какой-то мере к другому. Потому что вы могли бы, конечно, просто запустить программу одного человека и подсчитать количество секунд требуется, чтобы сортировать некоторые цифры, и вы можете запустить некоторые программа другого человека и подсчитать количество секунд требуется. Но это более общий способ, который вы можете использовать для анализа алгоритмов, если вы будете, как раз на бумага или просто в устной форме. Даже не запустить его без даже пробовать входы выборки, вы можете просто рассуждать через него. И так с наймом разработчик или если имея его или ее рода утверждают, вам почему их алгоритм, их секрет соус для поиска миллиарды веб-страниц для компания лучше, эти являются виды аргументов, которые они в идеале должны быть в состоянии сделать. Или, по крайней мере, это виды вещей что бы прийти в дискуссии на хотя бы в очень формальной дискуссии. Отлично. Так что Бен предложил что-то называется выбор рода. Но я собираюсь предложить, что есть другие способы сделать это, тоже. То, что я не очень нравится об алгоритме Бен в том, что он продолжал идти, или то, как я иду, взад и вперед и взад и вперед и назад и вперед. Что делать, если вместо того, чтобы я должен был сделать что-то вроде этих чисел здесь и я должен был просто иметь дело с каждым номер, в свою очередь, как я дал ему? 

Другими словами, здесь мой список номеров. Четыре, один, три, два. И я собираюсь сделать следующее. Я собираюсь вставить цифры где они принадлежат скорее чем выбирая их по одному за раз. Другими словами, вот номер четыре. 

Вот мой первоначальный список. И я буду поддерживать по существу, новый список здесь. Так что это старый список. Это новый список. Я вижу номер четыре в первую очередь. Мой новый список изначально пуст, поэтому тривиальным случай что четыре теперь сортировали список. Я просто принимая число я дал, и я ставлю его в своем новом списке. 

рассортированные этот новый список? Да. Это глупо, потому что есть только один элемент, но это абсолютно отсортирован. Там нет ничего, неуместны. Это более интересно, этот алгоритм, когда я перехожу к следующему шагу. 

Теперь у меня есть один. Так что, конечно же, принадлежит на начало или конец этого нового списка? Начало. Так что я должен сделать некоторые работы в настоящее время. Я принимаю некоторые вольности с моим маркером на просто рисунок вещей где я хочу их, но это не совсем точным в компьютере. Компьютер, как мы знаем, имеет Оперативная память, или Random Access Memory, и это один байт и другой байт и еще один байт. И если у вас есть гигабайта RAM, у вас есть миллиард байтов, но они физически в одном месте. Вы не можете просто перемещать вещи вокруг нарисовав ее на доске где угодно. Так что, если мой новый список имеет четыре места в памяти, к сожалению, четыре является уже в неправильном месте. 

Таким образом, чтобы вставить номер один Я не могу просто сделать это здесь. Это место памяти не существует. Это было бы обман, и я был Измены изобразительно в течение нескольких минут Вот. Так на самом деле, если я хочу поставить один здесь, Я должен временно скопировать четыре а затем положить один там. 

Это хорошо, это правильно, что это технически возможно, но понимаю, что это дополнительная работа. Я не просто поставить номер на месте. Сначала я должен был двигаться номер, а затем положить его на месте, так что я своего рода удвоил свою объем работы. Так что имейте это в виду. 

Но сейчас я сделал с этим элементом. Теперь я хочу, чтобы захватить номер три. Там, где, конечно же, оно принадлежит? Между. Я не могу обмануть больше и просто поставить его там, потому что, опять же, эта память в физических местах. Так что я должен скопировать четыре и поставить три здесь. Не ахти какое дело. Это всего лишь один дополнительный шаг again-- чувствует себя очень недорого. 

Но теперь я перехожу к двум. Два, конечно же, принадлежит здесь. Теперь вы начинаете видеть, как работа может накапливаться. Теперь то, что я должен делать? Да, я должен переместить четыре, Затем я должен скопировать три, и теперь я могу вставить два. И улов с этим Алгоритм, достаточно интересно, является то, что предположим, у нас есть более экстремальный случай, когда это, скажем, восемь, семь, шесть, пять, четыре, три, два, один. Это, во многих контекстах, в худшем случае, потому что штопать вещь буквально в обратном направлении. 

Это действительно не имеет влияет на алгоритм Бен, потому что в отборе Бен своего рода он собирается держать ходит взад и вперед по списку. И потому, что он всегда искал через весь оставшийся список, неважно где элементы. Но в этом случае с моей вставки approach-- давайте попробуем это. 

Так один, два, три, четыре, пять, шесть, семь, восемь. Один два три четыре, пять, шесть, семь, восемь. Я собираюсь взять восемь, и где я могу это сказать? Ну, в самом начале моего списка, потому что этот новый список отсортирован. И я пересекаю его. 

Где я поставил семь? Слей это. Он должен идти туда, так Я должен сделать некоторые копирования. А теперь семь идет здесь. Теперь я перехожу к шести. Теперь стало еще больше работы. 

Восемь должен идти здесь. Семь должен идти сюда. Теперь шесть может пойти сюда. Теперь я захватить пять. Теперь восемь должен идти здесь, семь приходится идти сюда, шесть должен идти здесь, и Теперь пять и повторите. И я довольно много перемещая его постоянно. 

Таким образом, в конце концов, это algorithm-- мы будем назвать его вставки sort-- на самом деле имеет много работы, тоже. Это просто разные вид работы, чем Бен. Работа Бен заставил меня идти назад и вперед все время, выбирая следующий наименьший элемент снова и снова. Так что это было очень визуальный вид работы. 

Этот другой алгоритм, который по-прежнему correct-- он получит работу done-- просто изменяет объем работы. Похоже, что изначально вы экономии, потому что вы просто имеем дело с каждым элементом фронт без ходить все путь через список, как Бен. Но проблема в том, особенно в эти сумасшедшие случаи, когда это все в обратном направлении, вы просто вид откладывая тяжелую работу пока вы не должны исправить свои ошибки. 

И так, если вы можете себе это восемь и семь и шесть и пять а затем четыре и три и два перемещая их путь через список, мы только что изменили тип работы, которую мы делаем. Вместо того, чтобы делать это на начало моей итерации, Я просто делаю это на конец каждой итерации. Так получается, что этот алгоритм, тоже, как правило, называется сортировка вставкой, Также на порядок п квадрата. Это не на самом деле не лучше, не лучше вообще. 

Тем не менее, есть и третий подход Я хотел бы призвать нас к рассмотрению, что это. Итак, пусть мой список, для простоты опять же, четыре, один, три, two-- всего четыре номера. Бен имел хорошую интуицию, хорошая человеческая интуиция до того, с помощью которого мы фиксировали весь список eventually-- вставки сортировки. Я уговорил нас вперед. Но давайте рассмотрим Простейший способ исправить этот список. 

Этот список не отсортирован. Зачем? В английском языке объяснить, почему это на самом деле не сортируется. Что это значит не быть отсортированы? 

СТУДЕНТ: Это не последовательный. 

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

СТУДЕНТ: Поместите их в порядке. 

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

СТУДЕНТ порядке возрастания. DAVID Маланом: Не в порядке возрастания. Быть более точным. Я не знаю, что вы имеете в виду по возрастанию. Что не так? 

СТУДЕНТ: Самый маленький из цифры не в первом пространстве. 

DAVID Маланом: Наименьший номера модели не в первом пространстве. Более конкретно. Я начинаю ловить на. Мы рассчитываем, но что из строя здесь? 

СТУДЕНТ: числовая последовательность. DAVID Маланом: числовая последовательность. вид каждого человека удерживания она here-- очень высокий уровень. Просто буквально сказать мне, что не так, как пять-летней мощи. 

СТУДЕНТ: Плюс один. 

DAVID Маланом: Что это? 

СТУДЕНТ: Плюс один. 

DAVID Маланом: Что вы имеете в виду плюс один? Дайте мне другой пять лет. Что случилось, мама? Что случилось, папа? Что вы имеете в виду это не отсортирован? 

СТУДЕНТ: Это не место. 

DAVID Маланом: Что не в нужном месте? 

СТУДЕНТ: Четыре. DAVID Маланом: Хорошо, хорошо. Так четыре не там, где она должна быть. В частности, это верно? Четыре и один, первый два числа, которые я вижу. Это правильно? Нет, они не в порядке, не так ли? На самом деле, думаю, что сейчас о компьютере, тоже. Он может смотреть только на одну, может быть, может быть, две вещи в once-- а на самом деле только одна вещь, в то время, но он может по крайней мере, посмотреть на одну вещь, то Следующее, что прямо рядом с ним. 

Так же эти в порядке? Конечно нет. Таким образом, вы знаете, что? Почему бы нам не взять ребенка шаги устранить эту проблему вместо того, чтобы делать эти фантазии алгоритмы, такие как Бен, где он вроде фиксируя его пробегаем по списку вместо того, чтобы делать то, что я сделал, где Я только отчасти установил его, как мы идем? Давайте просто буквально сломать Понятие order-- числового порядка, назвать это все, что вы want-- в этих парных сравнений. 

Четыре и один. Является ли это правильный порядок? Итак, давайте исправим это. Один и четыре, а затем мы просто скопировать это. Хорошо, хорошо. Я установил один и четыре. Три и два? Нет. Пусть мои слова совпадают мои пальцы. Четыре и три? 

Это не в порядке, так что я собираюсь чтобы сделать один, три, четыре, два. Хорошо. Теперь четыре и два? Нам нужно, чтобы исправить это, тоже. Так один, три, два, четыре. Так это сортируется? Нет, но это ближе к отсортирован? 

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

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

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

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

И вот теперь список отсортирован. К сожалению, бег времени этот алгоритм также N в квадрате. Зачем? Поскольку у вас есть п числа, а в худшем случае вы должны двигаться п чисел п раз, потому что вы должны продолжать идти назад, чтобы проверить и исправить потенциально эти цифры. И мы можем сделать более формальный анализ тоже. 

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

Так что это какой-то хороший программное обеспечение, которое кто-то написал, используя красочные бары, что это собирается сделать следующее для нас. Каждый из этих стержней представляет собой число. Taller столбик, тем больше число, меньше бар, тем меньше число. Так что в идеале мы хотим хорошую пирамиду где она начинается с малого и становится большой, и это будет означать, что эти бары сортируются. Так что я собираюсь идти вперед и выбирать, например, алгоритм Бен first-- выбор сортировки. 

И заметьте, что он делает. То, как они выбрали визуализировать этот алгоритм в том, что, так же, как я был ходить через мой список, эта программа идет через свой список номеров, выделяя в розовый цвет каждого число, которое он смотрит. А что должно произойти прямо сейчас? 

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

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

Давайте пропустить четыре. Там мы идем. Перемешайте их массив. И здесь мы go-- вставки рода. Играть. Обратите внимание на то, что он имеет дело с каждым элемент он встречает сразу же, но если она принадлежит неправильное место уведомление все работы, что должно произойти. Мы должны продолжать переход более и более элементов, чтобы освободить место для того, что мы хотим, чтобы поставить на место. 

Таким образом, мы сосредотачиваемся на левый конец только список. Заметьте, что мы даже не смотрели at-- мы не выделены розовым цветом что-нибудь направо. Мы просто имеем дело с проблемы, как мы идем, но мы создаем много работать для себя до сих пор. И поэтому, если мы ускорить этот процесс Теперь, чтобы перейти к завершению, она имеет другое чувство к нему на самом деле. Это просто сосредоточиться на левом конце, но делать немного больше работы, как needed-- вид сглаживающих вещей более, фиксируя вещи, но дело в конечном счете, с каждый элемент по одному за раз пока мы не получим хорошо the--, мы все знают, как это собирается закончиться, так что это немного сокрушающей возможно. 

Но список в end-- spoiler-- собирается быть отсортированы. Итак, давайте рассмотрим один последний. Мы не можем просто пропустить этот. Мы почти там. Два идти, один идти. И вуаля. Отлично. 

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

Мы не должны останавливаться по этому конкретному одному. Позвольте мне открыть это сейчас, тоже. Там в несколько других алгоритмов сортировки в мире, некоторые из которых захватываются здесь. И специально для учащихся, которые не являются обязательно визуальное или математическое, как мы делали раньше, мы можем также сделать это audially если ассоциировать звук с этим. И просто для удовольствия, вот несколько различных алгоритмов, и один из них, в частности, вы заметит, называется "сортировка слиянием." 

Это на самом деле принципиально лучше алгоритм, таким образом, что сортировка слиянием, один из те, с которыми вы хотите видеть, не порядок п в квадрате. Это о порядке п раз Логарифм N, которая на самом деле меньше, и, таким образом, быстрее, чем остальные три. И есть пара другой глупые те, что мы будем видеть. 

Так что здесь мы идем с некоторым звуком. Это сортировка вставкой, так что опять это просто дело с элементами как они приходят. Это своего рода пузырь, так что считая их пары одновременно. И опять же, самые большие элементы прорывается до самого верха. 

Далее выбор сортировки. Это алгоритм Бен, где снова он итеративно выбора следующий наименьший элемент. И опять же, теперь вы можете действительно услышать, что это ускорение, но только в той степени, как это делает все меньше и меньше работать на каждой итерации. Это более быстрое, сортировка слиянием, который сортирует кластеры чисел вместе, а затем объединяя их. Так look-- левый половина уже отсортированы. 

Теперь это сортировка правую половину, и Теперь он собирается объединить их в одно целое. Это то, что называется "Гном рода." И вы можете отчасти видеть, что он ходит взад и вперед, фиксируя работу немного здесь и там, прежде чем он приступает к новой работе. Вот и все. Там в другой вид, который действительно только для академических целей, называется "глупым рода", который принимает Ваши данные, сортирует его в случайном порядке, а затем проверяет, является ли она сортируется. И если это не так, то вновь сортирует его случайным образом, проверяет, является ли она сортируется, и если не повторяется. И в теории, вероятностно это будет завершено, но после того, как совсем немного времени. Это не самый эффективность алгоритмов. Так что любые вопросы о тех, конкретные алгоритмы или что-нибудь связанных там тоже? 

Что ж, давайте теперь дразнят друг от друга, что все эти линии, которые я рисую и то, что я предполагаю, что компьютер может сделать под капотом. Я считаю, что все эти цифры Я держу drawing-- они должны получить хранится где-то в памяти. Мы избавиться от этого парня сейчас тоже. 

Таким образом, часть памяти в computer-- так RAM памяти составляет то, что мы искали вчера, двойной встроенная память module-- выглядит следующим образом. И каждый из этих маленьких черных фишек некоторое количество байтов, как правило. А потом золотые булавки подобны провода, которые подключаются к компьютеру, и зеленая доска кремния просто что держит все вместе. Так что же это на самом деле означает? Если я как бы сделать такой же картину, давайте предположим для простоты что этот модуль DIMM, двойной встроенный модуль памяти, один гигабайт оперативной памяти, один гигабайт память, которая, сколько всего байт? Один гигабайт это сколько байт? Больше чем это. 1124 является килограмм, 1000. Мега млн. Гига это миллиард. 

Я лежу? Можем ли мы даже читать этикетку? Это на самом деле 128 гигабайты, так что это больше. Но мы будем делать вид, это это только один гигабайт. Так что означает, что есть миллиард байт памяти, доступной для меня или 8 миллиардов бит, но мы собираемся говорить в терминах байтов в настоящее время, Движение вперед. 

Так что это значит, это один байт, это еще один байт, это еще один байт, и если мы действительно хотели чтобы быть конкретным, мы бы привлечь миллиард маленьких квадратов. Но что это значит? Что ж, позвольте мне просто увеличить в этой фотографии. Если у меня есть что-то, что выглядит как это сейчас, это четыре байта. 

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

Это не так сложно, как один Brattle Площадь, Кембридж, штат Массачусетс., 02138. Вместо этого, это просто число. Это байт с номером ноль, это Во-первых, это два, это три, и это 41. Подожди минуту. Я думал, что я сказал, 42 минуту назад. Я начал отсчет с нуля, так что это на самом деле правильно. Теперь мы не должны фактически сделать его в виде сетки, и если вы рисуете его в виде сетки Я думаю, что вещи на самом деле получить немного вводит в заблуждение. Какой программист, в своем собственном уме, как правило, думают об этом памяти, как это так же, как ленты, как кусок липкой лентой что просто идет дальше и дальше навсегда или пока не кончатся памяти. Таким образом, более распространенным способом привлечь и думать только о памяти было бы, что это байта ноль, один, два, три, а затем точка, точка, точка. И у вас есть всего 42 таких байтов, даже хотя физически он может на самом деле быть чем-то больше, как это. 

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

А что было бы рядом с два в памяти компьютера? Ну, нет никакого ответа на это. Мы действительно не знаем. И до тех пор пока компьютер не нужен, он не должен заботиться, что будет дальше к числам это действительно заботится о. И когда я уже говорил ранее, что компьютер можно смотреть только по одному адресу в то время, это своего рода почему. 

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

А в общей сложности, сколько бит участие прямо сейчас, чтобы быть ясно? Так что это четыре байта, или теперь это всего 32 бита. Так что есть на самом деле 32 нулей и те составляющие эти четыре вещи. Там даже больше здесь, но снова мы не заботимся об этом. 

Так что теперь давайте зададим другой Вопрос использования памяти, потому что это в конце дня в дисперсии. Независимо от того, что мы могли бы сделать с компьютер, в конце дня аппаратные средства по-прежнему то же самое под капотом. Как бы я хранить слово здесь? Ну, слово в компьютере, как "Привет!" будет храниться так же, как это. И если вы хотели больше слово, вы можете просто перезаписать, что и сказать что-то как "привет" и магазин, который здесь. 

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

Я собираюсь идти вперед и открыть простую текстовую программу, и я собираюсь создать файл с именем hello.c. Большая часть этой информации мы Не буду вдаваться в очень подробно, но я собираюсь написать Программа в том же самом языке, C. Это гораздо более пугающим, Я бы сказал, чем нуля, но это очень похоже по духу. На самом деле, эти фигурная braces-- вы можете вид думаю о том, что я только что сделал, как это. 

Давайте сделаем это, на самом деле. Когда зеленый флаг щелкнул, выполните следующие действия. Я хочу, чтобы распечатать "привет". Так что теперь это псевдокод. Я отчасти размывая границы. В C, этот язык я говорю О, эта линия печати привет фактически становится "Printf" с некоторые круглые скобки и точка с запятой. 

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

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

Так давайте попробуем это. Я собираюсь сохранить его. И это, опять же, очень старая школьная среда. Я не могу нажать, я не могу перетащить. Я должен вводить команды. Поэтому я хочу, чтобы запустить свою программу, так что Я мог бы сделать это, как hello.c. Это файл я побежал. Но подождите, я пропускаю шаг. Что мы говорим, является необходимым шаг для языка как C? Я только что написал источник код, но что мне нужно сделать? Да, мне нужен компилятор. Так что на моем Mac здесь, у меня есть Программа под названием GCC, GNU C компилятор, которая позволяет мне делать this-- поворот мой исходный код в, мы будем называть его, Машинный код. 

И я вижу, что, еще раз, как показано ниже, эти являются нули и единицы я просто созданный из моего исходного кода, все нули и единицы. И если я хочу работать мой program-- это происходит называться a.out для исторические reasons-- "привет". Я могу запустить его снова. Привет привет привет. И это, кажется, работает. 

Но это означает, что где-то в моем память компьютера слова ч-е-л-л-о, восклицательным знаком. И оказывается, так же, как и в сторону, что такое компьютер, как правило, сделать так, что он знает, где вещи начинают и end-- это собирается поставить специальный символ здесь. И конвенция должна поставить номер ноль в конце слова так что вы знаете, где это на самом деле заканчивается, так что вы не продолжать печатать больше и больше символов, чем вы на самом деле намерены. 

Но здесь еда на дом, даже хотя это довольно аркан, является то, что это в конечном счете относительно просто. Вы получили вид ленты, заготовки пространство, на котором можно писать письма. Вы просто должны иметь специальный символ, как угодно число ноль, чтобы положить в конце ваши слова так, что компьютер знает, ой, я должен остановить печать после того, как Я вижу восклицательный знак. Потому что следующая вещь там это значение ASCII нуля, или нулевой символ, как кто-то назовет его. Но есть своего рода проблемы здесь, и давайте вернуться числам на минуту. Предположим, что я, на самом деле, есть массив чисел, и предположим, что Программа Я пишу это как класс книга для учителя и учителей классе. И эта программа позволяет ему или ей чтобы набрать баллы своих учеников на викторинах. И предположим, что студент получает 100 на их первой викторины, может быть, как 80 на следующий, то 75, а затем 90 на четвертой викторины. 

Таким образом, в этот момент в истории, массив имеет размер четыре. Там абсолютно больше памяти в компьютер, но массив, так сказать, имеет размер четыре. Предположим теперь, что учитель хочет назначить пятый тест на класс. Ну, одна из вещей, которые он или она будет иметь, чтобы сделать теперь хранить дополнительную ценность здесь. Но если массив учитель имеет Созданный в этой программе имеет размер для, одна из проблем с массивом является то, что Вы не можете просто продолжать добавлять к памяти. Потому что, если другая часть Программа имеет слово "эй" прямо там? 

Другими словами, память может быть используется для чего-нибудь в программе. А если заранее я напечатал, эй, Я хочу, чтобы ввод четырех баллов викторины, они могли бы пойти здесь и здесь. И если вы вдруг передумаете позже и сказать, что я хочу пятый викторины счет, вы не можете просто положить его туда, куда вы хотите, потому что, если это памяти используется для чего-то else-- другую программу или какой-либо другой особенностью программы что вы работаете? Таким образом, вы должны думать заранее как вы хотите хранить ваши данные, потому что теперь вы покрашены себя в цифровой угол. 

Таким образом, вместо того, чтобы учитель мог бы говорят, при написании программы хранить его или ее классов, вы знаете, что? Я буду просить, при написании моей программы, что я хочу, ноль, один, два, три, четыре, пять, шесть, восемь классов в общей сложности. Так один, два, три, четыре, пять, шесть, семь, восемь. Преподаватель может просто чрезмерно выделять памяти при написании свою программу и сказать, вы знаете, что? Я никогда не буду назначать более чем через восемь викторин в течение семестра. Это просто безумие. Я никогда не буду выделять это. Так что таким образом он или она имеет гибкость для хранения студенческих баллов, как 75, 90, и, возможно, один дополнительный, где студент получил дополнительный кредит, 105. 

Но если учитель никогда использует эти три пространства, есть интуитивное навынос здесь. Он или она просто тратить пространство. Итак, другими словами, есть этот общий компромисс в программировании где вы можете либо выделить ровно столько памяти, сколько вы хотите, потенциал роста которого является то, что ты супер efficient-- вы не быть расточительным на all-- но нижняя сторона которого является то, что если вы измените свое мнение, когда с помощью программы, которую вы хотите сохранить больше данных, чем первоначально предполагалось. 

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

Под-выделяющих кажется плохим. Чрезмерная кажется плохо Выделение. Так что может быть лучшим решением? Перераспределение. Будьте более динамичным. Не заставлять себя выбрать априори, в самом начале, что вы хотите. И, конечно, не чрезмерно выделять, чтобы не быть расточительным. 

И так, чтобы достичь этой цели, мы нужно бросить эту структуру данных, так сказать, прочь. И так, что программист как правило, используют что-то не называется массив, но связанный список. Другими словами, он или она будет начинают думать о своей памяти как являющийся своего рода форму, что они можно сделать следующим образом. Если я хочу, чтобы сохранить номер в program-- поэтому сентября Я дал моим студентам викторины; я хочу для хранения первой викторины студентов, и они получили 100 на it-- I задам мой компьютер, путем программы я написано, для одного куска памяти. И я буду хранить номер 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-- буквально один байт или, может быть четыре байта, некоторое фиксированное число байтов прочь. В связанном списке, который мы могли бы сделать как это, под капотом, который знает где, что материал? Он даже не нужно поступать так. Некоторые данные могут быть обратно влево там. Вы даже не знаете. 

И так с массивом, у вас есть особенность известна как случайного доступа. А какие средства произвольного доступа что компьютер может прыгать мгновенно в любое место в массиве. Зачем? Поскольку компьютер знает что первое местоположение ноль, один, два, и три. 

И поэтому, если вы хотите, чтобы перейти от этот элемент к следующему элементу, вы в буквальном смысле, в ум компьютера, просто добавьте один. Если вы хотите, чтобы перейти к третьему элементу, просто добавьте одно-- следующий элемент, просто добавить один. Тем не менее, в этой версии истории, предположим, компьютер в настоящее время ищет на или имеем дело с номером 100. Как вы получаете к следующему класс в классе книги? 

Вы должны принять семь шаги, которые произвольно. Для того, чтобы добраться до следующей, вы должны принять еще восемь шагов, чтобы добраться до 15. Другими словами, это не постоянный зазор между числами, и поэтому он просто берет Компьютер больше времени точка. Компьютер должен искать через память в порядке чтобы найти то, что вы ищете. 

Таким образом, в то время как массив имеет тенденцию быть быстро данные structure-- потому что вы может буквально сделать простую арифметику и попасть туда, куда вы хотите, добавив к нему один, для instance-- связанный список, вы жертвуете эту функцию. Вы не можете просто идти от первой на второй третий четвертый. Вы должны следовать карте. Вы должны предпринять дополнительные шаги, чтобы добраться до тех значений, которые Казалось бы, добавление стоимости. Таким образом, мы платим цену, но то, что было особенность, что Дэн искал здесь? Что делает связанный список по-видимому, позволяют нам делать, который был происхождение эта конкретная история? 

В точку. Динамический размер для него. Мы можем добавить к этому списку. Мы можем даже сократить список, так что мы только используя столько памяти как мы на самом деле хотим и так мы никогда не чрезмерно расПредеЛение. 

Теперь просто, чтобы быть действительно NIT-разборчивы, есть скрытые расходы. Таким образом, вы не должны просто дайте мне убедить вы, что это является убедительным компромиссом. Там другая скрытая стоимость здесь. Преимущество, чтобы быть ясно, является то, что мы получаем динамичность. Если я хочу еще один элемент, я могу просто нарисовать его и поставить ряд там. И тогда я могу связать его с изображением здесь, в то время как здесь, опять же, если я окрашены себя в угол, если что-то еще уже использует память здесь, я не повезло. Я нарисовал себя в угол. 

Но то, что скрытый стоит в этой картине? Это не просто сумма времени, которое требуется идти отсюда здесь, который семь шагов, а затем восемь шагов, что более чем один. Что еще одна скрытая стоимость? Не только время. Дополнительная информация необходимо для достижения этой фотографии. 

Да, эта карта, эти маленькие клочки бумаги, как я продолжаю описывать их как. Эти arrows-- те не являются свободными. Computer-- вы знаете, то, что компьютер имеет. Он имеет нули и единицы. Если вы хотите, чтобы представлять стрелу или А карту или номер, вам нужно некоторое количество памяти. Так что с другой ценой, которую вы платить за связанного списка, общая информатика ресурс, также пространство. 

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

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

Итак, еще раз, именно это уравновешивание пытаясь решить, какой из этих вещей вы готовы потратить? Который является наименее дорогим? Что дает лучшие результаты? Да? 

В самом деле. В этом случае, если вы представления чисел в maps-- их называют на многих языках "указатели" или "адреса" - это двойное пространство. Это не должно быть так плохо, как двойной, если Прямо сейчас мы просто хранения чисел. Предположим, что мы хранили записи пациента в hospital-- так называет Пирсона, номера телефонов, номера социального страхования, доктор история. Это поле может быть много, гораздо больше, и в этом случае крошечная указатель, адрес следующая element-- это не имеет большого значения. Это такая бахрома стоимость не имеет значения. Но в этом случае, да, это удвоение. Хороший вопрос. 

Давайте поговорим о том времени, а чуть более конкретно. Что время работы поиска этот список? Предположим, что я хотел искать через все классы студентов, и есть п классов в этой структуре данных. Здесь, также, мы можем заимствовать словарный запас ранее. Это линейная структура данных. 

Big O п является то, что требуется, чтобы получить к концу этой структуры данных, whereas-- и мы не видели это before-- массив дает вам что называется постоянной времени, что означает, один шаг или два шага или 10 steps-- не имеет значения. Это фиксированное число. Она не имеет ничего общего с размер массива. И причина этого, опять же, с произвольным доступом. Компьютер может просто немедленно перейти на другое место, потому что они все равно расстояние от всего остального. Там нет мышления участвует. Отлично. Так что, если я могу, я попытаюсь нарисовать два финальных изображений. Очень часто один известный как хэш-таблицу. Таким образом, чтобы мотивировать эту дискуссию, дайте мне подумать о том, как это сделать. 

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

И предположим, что слова яблоко и банан и дыня. И я не могу думать о фруктах которые начинаются с D, так что мы просто будет иметь три фруктов. Так что это массив, и мы хранить все эти слова в этом словаре как массив. Вопрос, тогда, как еще Вы могли бы хранить эту информацию? 

Ну, я своего рода обман здесь, потому что каждая из этих букв в слове действительно индивидуальный байт. Так что, если я действительно хотел быть нит-разборчивы, я должен действительно быть разделив это вверх в гораздо меньшие куски памяти, и мы могли бы сделать именно это. Но мы будем работать в та же проблема, как и раньше. Что если, как Merriam Webster или Оксфорд делает каждый год-- они добавляют слова к dictionary-- мы не делаем обязательно хотят рисовать себя в угол с массивом? 

Так что вместо того, чтобы, может быть, умнее подход это положить яблоко в своем собственном узле или коробке, как бы мы сказали, банан, и то здесь мы имеем дыню. И мы струна эти вещи вместе. Так что это массив, это связанный список. Если вы не можете достаточно видеть, это просто говорит "массив", и это говорит, что "список." 

Таким образом, мы имеем то же самое точные вопросы, как и прежде, в результате чего мы теперь имеем динамизм в нашем связанном списке. Но у нас есть довольно медленный словарь. Предположим, я хочу, чтобы искать слово. Это может занять мне большую O п шаги, потому что слово может быть весь путь в конце список, как дыня. И получается, что в программировании, сортировать Грааля данных структуры, что-то что дает вам постоянное время как массив но это по-прежнему дает вам динамизм. 

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

И то, как эта вещь работает следующим образом. Если этот now-- хэш table-- моя третья структура данных, и я хочу, чтобы сохранить Слова в этом, я не хочу просто хранить все слова спина к спине, чтобы спина к спине. Я хочу использовать некоторые часть информации о словах, которые позволят мне получить его там, где это быстрее. 

Так что, учитывая слова яблоко и бананы и дыня, Я намеренно выбрал эти слова. Зачем? Что-то принципиально отличается о трех? Что очевидно? Они начинаются с разных букв. 

Таким образом, вы знаете, что? Вместо того, чтобы поместить все мои слова в то же ведро, так сказать, как в одном большом списке, почему не Я по крайней мере попробовать оптимизацию и сделать мои списки 1/26 до тех пор. Убедительный оптимизация может быть, почему не Я-- при вставке слова в эту структуру данных, в память компьютера, почему я не отдал все 'а' слова здесь, все 'Ъ' слова здесь, и все 'C' слова здесь? Так что это в конечном итоге положить яблоко здесь, банан здесь, дыню здесь, и так далее. 

И если у меня есть дополнительный Слово like-- что другое? Яблоко, банан, груша. Любой думаю плода которая начинается с А, В или С? Blueberry-- совершенным. Это будет в конечном итоге здесь. И поэтому мы, кажется, есть незначительно лучшее решение, потому что теперь, если я хочу искать яблоко, я first-- Я не просто погружение в моей структуре данных. Я не погружайтесь в память моего компьютера. Я первый взгляд на первую букву. 

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

Теперь это сокращает наше время потенциально по столько, сколько один из 26, потому что если предположить, что вы иметь столько «а» слова, как "Z" слова, как "Q" слов, которые на самом деле не realistic-- вы будете иметь перекос по некоторые буквы alphabet-- но это было бы инкрементный Подход, который действительно позволяет вы, чтобы добраться до слов гораздо быстрее. И в самом деле, сложный программа, то Googles мира, Facebooks из world-- они будут использовать хэш-таблицу для многих различных целей. Но они не были бы настолько наивен, чтобы просто посмотреть на первую букву в яблоко или банан или груша или дыня, потому что, как вы можете видеть эти списки могут получить еще долго. 

И так что это еще может быть своего рода из linear-- так вроде медленно, как с большим O п что мы обсуждали ранее. Так что реальная хорошая хеш-таблица будет do-- он будет иметь гораздо больший массив. И это будет использовать гораздо больше сложные функции хеширования, так что это не просто смотреть на «а». Может быть, он смотрит на "а-р-р-л-е" и каким-то образом преобразует эти пять букв в том месте, где яблоко должно быть сохранено. Мы просто по наивности, используя букву 'A' в одиночку, потому что это просто и красиво. 

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

Но понять, насколько быстро такого рода дискуссии возрастали, либо до сих пор, что это своего рода из над головой в этот момент, который Это хорошо. Но мы начали, напомним, с истинно что-то низкого уровня и электронные. И так это опять-таки это тема абстракции, где, как только вы начнете принимать для как должное, в порядке, у меня есть it-- физической памяти, ОК, получил его, каждый физическое расположение имеет адрес, ОК, я получил его, я могу представить эти адреса как arrows-- Вы можете очень быстро начать иметь более сложные разговоры о том, в конце концов, кажется, что позволяет нам решать проблемы, такие как поиск и сортировки более эффективно. И будьте уверены, too-- потому что я думаю, что это является самым глубоким мы пошли в некоторые из этих тем CS proper-- мы сделано в полтора дня на это указать, что вы, возможно, как правило, делают более течение восьми недель в течение семестра. 

Любые вопросы по этим? Нет? Отлично. Ну, почему бы нам не сделать паузу там, начать обед на несколько минут раньше, резюме всего около часа? И я буду задерживаться немного с вопросами. Тогда я буду должен идти взять пару звонков, если это нормально. Я включу музыку в то же время, но обед должен быть за углом.