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