>> [Играет музыка]
>> Дэвид Дж Малан: Это CS50.
И это начало недели три.
Таким образом, мы получили много интересной вещи, чтобы покрыть сегодня.
Много возможностей для добровольцев на сцене.
И в конечном счете, сегодня не о коде вообще.
Но это об идеях, и это об алгоритмах,
а на самом деле вернуть некоторые из Уроки, извлеченные из нулевой неделе,
где напомним, мы представил это чудовище.
И заимствования вдохновение того, чтобы начать
решить все изощреннее проблемы алгоритмически.
Но сначала пару объявлений.
Таким образом, одна, если вы хотели бы присоединиться к Сотрудники и одноклассники CS50 за ланчем
в эту пятницу, и здесь, и в Кембридж, и в Нью-Хейвене,
пожалуйста, посетите Курса сайт, где URL может быть найден.
Лекция в среду будет не быть здесь, в Сандерс.
Это будет только онлайн, так настроиться на сайте CS50 на, в
ли здесь в Кембридже или Нью-Хейвен, а также.
>> И тогда проблема установить два уже в ваших руках.
Если вы не ныряли в еще, позвольте мне предложить сформулированное предложение сильно
что особенно сейчас, в проблема устанавливает заранее,
Вы действительно хотите, чтобы начать сейчас, если не плескаться немного на выходные или до
когда они впервые выйти на Пятницам, потому что вы будете
найти, что они не обязательно получать больше или более сложным в
SE.
Я думаю, что вы найдете, что в Вообще, они, как правило, принимать примерно
вокруг столько же времени.
Но это, конечно, зависит на студента, и он
зависит от менталитета с которой вы приближаетесь к нему.
Но неизменно, вы собираетесь запустить против какой-то стене,
и вы собираетесь ударить какая-то ошибка, и вы просто
не будет в состоянии получить над ним в какой-то момент.
И это очень ценно, чтобы иметь возможность отойти, вернуться на следующий день,
перейти к офисным часов, пост на CS50 Обсудить и т.п., на самом деле получить разблокирован.
Так что имейте это в виду.
Начиная раннее, насколько это возможно это лучшее, что вы можете сделать.
Так вот, где мы начали класс, по нулевой неделе.
И мы можем получить добровольца здесь, чтобы помочь мне найти микрофоны?
ХОРОШО.
Стоя уже.
Давай до.
Угадайте, что это, как это будет работать.
Как тебя зовут?
АЛАН ESTRADA: Алан Эстрада.
Дэвид Дж Малан: Алан Эстрада.
Давай до.
Приятно познакомиться.
АЛАН ESTRADA: Приятно познакомиться.
Дэвид Дж Малан: И вы были здесь с нами в нулевом недели, конечно.
АЛАН ESTRADA: я был.
Я был.
>> Дэвид Дж Малан: Так может вы идете вперед и найти для нас Майк Смит,
так быстро, как вы можете?
Как быстро, как вы можете.
Буквально разрывая проблемы в половине, как вам нужно.
>> АЛАН ESTRADA: Хм.
Дэвид Дж Малан: Буквально разрывая проблему в два раза.
>> АЛАН ESTRADA: Ой.
Мм.
Отлично.
>> Дэвид Дж Малан: ОК.
Хорошо.
Спасибо.
АЛАН ESTRADA: Очень хорошо.
ХОРОШО.
>> Дэвид Дж Малан: И теперь, Вы свел его
до половины размера проблемы.
Теперь, мы до четверти.
Вы обращая внимания на с какой стороны мы держим?
>> [СМЕЮЩИЙСЯ]
>> АЛАН ESTRADA: Да, я think--
>> Дэвид Дж Малан: Какой раздел мы в?
АЛАН ESTRADA: Глушители, так.
>> Дэвид Дж Малан: ОК.
Но Майк Смит собирается чтобы быть после Глушители.
Так--
>> [СМЕЮЩИЙСЯ]
>> Все в порядке.
АЛАН ESTRADA: Где мы ищем?
Дэвид Дж Малан: Майк Смит.
АЛАН ESTRADA: Майк Смит.
Дэвид Дж Малан: Теперь мы в хирургическое.
Теперь врачи.
Теперь--
>> АЛАН ESTRADA: Let's- давайте идти с реальной.
Недвижимость.
>> Дэвид Дж Малан: Недвижимость.
ХОРОШО.
Если вам нужно реальное.
Теперь, какой путь Майк Смит?
>> АЛАН ESTRADA: Таким образом.
>> Дэвид Дж Малан: Каким образом?
АЛАН ESTRADA: Подождите.
M is-- правильно?
Мы начали with--
>> Дэвид Дж Малан: Да.
Они оставили.
Твое право.
>> АЛАН ESTRADA: Да.
>> Дэвид Дж Малан: Так Майк здесь.
АЛАН ESTRADA: Что?
>> [СМЕЮЩИЙСЯ]
>> Плохой пример, ребята.
Сожалею.
Дэвид Дж Малан: Это научит Вы выскочить из своего стула.
>> АЛАН ESTRADA: Ой.
Ой.
Понял тебя.
Ой.
Это is-- ОК, я вам.
Смит прямо здесь?
>> Дэвид Дж Малан: Смит, спасибо.
Так что я буду держать глядя Смит?
>> АЛАН ESTRADA: О, да.
Нет нет нет.
О нет.
Это мое.
>> Дэвид Дж Малан: О, вы получили Смит.
ХОРОШО.
>> АЛАН ESTRADA: Да, я получил Смит прямо здесь.
Извините ребята.
Я думал, мы Michael-- искали Михаила.
Сожалею.
>> Дэвид Дж Малан: Это нормально.
Ладно, теперь мы в Paccini и сыновья.
>> АЛАН ESTRADA: Paccini и сыновья.
Дэвид Дж Малан: Только вы и я на этом.
ХОРОШО.
Как нас найти Майк Смит.
Смит.
>> АЛАН ESTRADA: Смит.
>> Дэвид Дж Малан: Смит.
Мы в R для мусора.
АЛАН ESTRADA: Мусор.
Ой.
Это займет какое-то время.
>> [СМЕЮЩИЙСЯ]
Дэвид Дж Малан: Обувь.
Мы в обуви.
>> АЛАН ESTRADA: Теперь мы gonna--
>> Дэвид Дж Малан: Ницца.
АЛАН ESTRADA: Which--
[СМЕЮЩИЙСЯ]
О, это здорово.
[СМЕЮЩИЙСЯ]
>> Дэвид Дж Малан: Это нормально.
>> АЛАН ESTRADA: О, это хорошо.
Я не думаю, что я собираюсь есть PSAT приятелей после этого.
Дэвид Дж Малан: Хорошо.
Спортивные.
АЛАН ESTRADA: Спортивные.
Хм, L, M, N, O, П.
Дэвид Дж Малан: ОК.
Так что давайте разорвать этот пополам.
Это нормально.
На этом заканчивается плохо в любом случае, потому что Майк Смит не будет в желтых страницах.
>> АЛАН ESTRADA: Ой.
>> Дэвид Дж Малан: Нет, это нормально.
Но давайте представим, как он на этой странице.
Так что теперь, вы свели проблему вниз на одну страницу, и мы нашли Майка Смита.
>> [Ликующей]
Спасибо.
ХОРОШО.
Это было необычно.
Но это было еще быстрее чем линейный поиск,
где мы начинаем на начале книги,
и мы движемся наш путь слева направо, в конечном итоге, глядя на Майка Смита.
И так, если телефонная книга был, может быть, 1000 страниц,
может быть, это заняло бы нам 10 или около того страниц слезы.
>> Но вы, возможно, использовала коснулся предположение
во все это, что есть что в телефонной книге на заранее было то, что?
АУДИТОРИЯ: Сортировать.
Дэвид Дж Малан: Это отсортированы.
Правильно?
Это отсортированы по алфавиту, поэтому что все эти имена и номера
сортируются от А х до Z, и в алфавитном порядке между ними.
Но сегодня, мы теперь спросить вопрос, ну,
как сделал Verizon или телефон Компания получить его в таком состоянии?
>> Потому что одно дело использовать Предположение, что, и поэтому
решить проблему с Алгоритм более эффективно.
Но мы никогда действительно спросил нулевой неделе, ну,
сколько это стоило Verizon или кто-то еще
чтобы получить, что телефонную книгу в отсортированном порядке?
>> Правильно?
Это не имеет значения, если глядя Mike Smith
супер быстрый, если она принимает вас на год сортировать страницы первоначально.
Правильно?
Вы можете также просто просеять через рандомизированном телефонной книге,
если это будет супер дорого для сортировки.
Так что, если мы можем иметь другой доброволец.
Давайте смотреть здесь возьмем как мы might-- приходят на up-- как
мы могли бы идти о сортировке них.
>> И если на самом деле мог Иордания присоединиться к нам здесь, на сцене.
Давай на мгновение.
Как тебя зовут?
Каролина: Кэролайн.
Дэвид Дж Малан: Кэролайн, давай до.
И вы будете присоединился мной и Иордании здесь.
Кэролайн, спасибо.
Все в порядке.
Итак, что мы имеем здесь для Кэролайн 26 синие книги
что ФАС использует для управления некоторые выпускные экзамены.
Они становятся трудно найти, но то, что мы сделали заранее
является то, что мы вложили чье-то имя на передней каждый из них,
но мы держали его простым путем затем тушить полные имена.
Таким образом, мы бы поставить человека с именем L, D, J, B, полностью от А до Z,
но они в случайном порядке.
И так, если бы вы, говорю СВОЙ путь через проблемы, как вы
сделать это, вы можете идти вперед и сортировать их для нас, от А до Я.
>> АУДИТОРИЯ: ОК, так что я, как, средний.
С начинает.
Б. Дж, прежде чем Л. В, В.
>> Дэвид Дж Малан: Держите, что думал в течение одной секунды.
Потому что иначе, это только интересными для вас, меня и Иордании.
Там мы идем.
АУДИТОРИЯ: [неразборчиво].
Р.
Дэвид Дж Малан: ОК.
Что ты делаешь?
>> Каролина: М приходит после О.
>> Дэвид Дж Малан: ОК.
>> Каролина: О.
Дэвид Дж Малан: О, хорошо.
>> Каролина: Е.
>> Дэвид Дж Малан: E, F. Да.
>> Каролина: T, U, V.
>> Дэвид Дж Малан: V, T, U, V. Так-то оно Похоже, вы making-- продолжать.
Похоже, вы делаете большая куча здесь,
и вид большой кучи там.
Таким образом, первая половина алфавита, Вторая половина алфавита.
ХОРОШО.
Хорошо.
Вид разделения проблемы на две части.
M, N, Х. Да.
Каролина: К.
Дэвид Дж Малан: ОК.
К. Итак, вы вроде выбора их один за другим,
положить его влево или вправо, или Z собирается на полу.
ХОРОШО.
>> Каролина: Z собирается на полу.
>> Дэвид Дж Малан: ОК.
У собирается на полу.
Теперь мы можем поставить X.
>> Каролина: Г.
Дэвид Дж Малан: G происходит осталось.
S идет правильно.
Ладно, А пройдя весь путь влево.
>> Каролина: A, B, C, D.
>> Дэвид Дж Малан: Теперь, хорошо.
У нас есть A, B, C. Вт собирается там.
Ладно, Т.
>> Каролина: H, I, J.
Дэвид Дж Малан: H, I, J. Хорошо.
Каролина: В центре, я gonna--
Дэвид Дж Малан: ОК.
Так что теперь, мы собираемся вида слияния этих различных свай.
Таким образом, через С, тогда я вижу D, и Е, F и и G и Н, И. Ницца.
J, К. А потом, это груда с ног на голову, но это нормально.
Конечно.
Мы можем сократить некоторые углы.
ХОРОШО.
И тогда мы должны W, X, Y, Z.
>> Каролина: Да.
>> Дэвид Дж Малан: Отлично.
Таким образом, большое спасибо Кэролайн для сортировки них.
>> [Ликующей]
>> Спасибо.
Большое спасибо.
Так что теперь давайте на минуту как Кэролайн ходил, что
и что именно мы смогли, целью которых, как мы
смогли решить, что Проблема, когда мы были просто
учитывая целый букет случайных входов.
>> Ну, похоже, есть было немного системы там?
Правильно.
Так ранее писем в алфавите, она
был положить слева, а поздних буквы в алфавите,
она была положить в правый.
И как только она нашла некоторые проксимальных буквы, те,
которые идут рядом друг с другом, она вкладывать их в порядке.
И таким образом, мы были своего рода эти маленькие груды отсортированных входов, происходящих.
>> И так, что вполне как то, что большинство из нас люди будут делать.
Мы вроде просеять через него, и мы вроде есть механизм.
Но это может быть трудно, чтобы написать его вниз в формуле как таковой.
Он чувствовал себя немного более органичным, чем это.
Итак, давайте посмотрим, если мы можем в настоящее время границы Проблема с меньшим количеством входов.
>> Вместо 26, давайте сделать что-то гораздо меньше
с просто сказать, семь, за эти двери, так сказать.
Есть только семь чисел?
И если цель теперь в рука, чтобы найти значение,
давайте посмотрим, насколько эффективно мы можем идти об этом.
И давайте посмотрим, если мы можем в настоящее время начать применять некоторые цифры,
или некоторые формулы, с которой, чтобы описать эффективность нашей телефонной книге
Алгоритм, наш алгоритм экзамен книги, и в более общем, поиска информации.
>> Таким образом, для этого, позвольте мне идти вперед, и на сенсорном экране сюда,
поставить веб-браузер, который имеет именно эти семь дверей.
И если мы могли бы получить один добровольно прийти на здесь,
Я положил эти же двери здесь.
Быстрый общественных началах.
>> Это одно-- демо собираются к все быстрее и быстрее в настоящее время.
Идем вниз.
Как тебя зовут?
Тревор: Тревор.
>> Дэвид Дж Малан: Тревор?
Ладно, Тревор, давай вниз.
Так Тревор добровольно здесь, чтобы сделать подобную проблему, но это
более узким по объему, и что происходит чтобы позволить нам, чтобы попытаться оформить в настоящее время
процесс сортировки эти цифры.
>> Так Тревор, приятно встретиться с вами.
Так вот массив, так говорят, список из семи дверей.
Идите вперед и найти нам номер 50.
И затем, после того факта, расскажите, как вы его нашли.
Если be-- все права.
Да, это один здесь?
Ой-ой.
ХОРОШО.
Вы нажали, что один.
Хорошо.
>> И хорошо.
Теперь вы нажали эту.
И позвольте мне дать вам микрофон, так что у вас есть это в мгновение.
Идите вперед и нажмите рядом, что вы намерены.
Да, хорошо.
Тревор: Могу ли я повторно щелкните дверь?
Дэвид Дж Малан: Нет, вы не можете повторно щелкните.
Тревор: ОК.
Вот этот.
Дэвид Дж Малан: Где вы хотите пойти?
Который?
>> Тревор: Это одно.
>> Дэвид Дж Малан: Нет
>> Тревор: ОК.
Вот этот.
>> Дэвид Дж Малан: Да.
Это было хорошо.
Все в порядке.
Так что же ваш алгоритм или Процедура для этого, Тревор?
>> Тревор: Я только что прошел через двери, пока я не нашел 50.
Дэвид Дж Малан: ОК.
Отлично алгоритм.
Так что все в порядке.
Потому что в самом деле, если я открою что за этими двумя другими дверями, то, что
мы найдем здесь является то, что у нас есть только случайный вход.
Так что на самом деле, как было хорошо, как вы могли бы получить.
И в самом деле, вы получили лучше, чем исчерпывающе поиске весь массив,
потому что это было бы действительно повезло, если вы ударил количество
50 в самый последний двери.
Но что, если мы вместо дал вам предположение.
Предположим, что я вроде все эти двери вокруг,
так что у вас есть номера сортируются в этот раз,
но на этот раз он на самом деле different-- этот раз,
это на самом деле сортируются для вас.
А теперь ставите стороны заключается в хит номер 50.
>> Тревор: ОК.
>> Дэвид Дж Малан: Что ваш алгоритм будет?
>> Тревор: Ну, если это сортируется, это либо происходит
чтобы be-- если большой, чтобы по величине, убыванию, это будет первый,
или, если это наоборот, это будет последним.
Так что я просто нажмите эту дверь, и Затем просто нажмите на последнюю дверь.
Дэвид Дж Малан: Отлично.
Все в порядке.
Таким образом, мы нашли номер 50.
Поэтому, как только вы знали, они были отсортированы, мы
смогли использовать это предположение.
Так что они слишком много, как пример телефонной книги.
Как только у вас есть, даже с небольшая проблема, как это,
Ваши входы предварительно отсортированы, мы можем на самом деле найти значение возможно
более эффективно.
>> И я не говорю вам, если это было отсортировано мала до велика, или большого к малому,
и так было очень разумно чтобы начать на одном конце или другой
на самом деле найти, что целевое значение.
Так что спасибо Тревору, а также.
И я propose-- красиво сделано.
У нас есть небольшой клип, на самом деле, что является одним из наших любимых моментов в CS50,
в результате чего иногда эти демки не совсем по плану.
И в самом деле сейчас я подъехал неправильный интерфейс
с которой использовать сенсорный экран.
Так это была моя вина есть.
>> Так что это будет сделать для клип в следующем году, как
почему я был нажав на моем собственном экране.
Но давайте взглянем на то, что произошло в прошлом году
с Джеем, который придумал, много как Тревор здесь, добровольно,
и в этом короткий клип, вы увидите как эта же демонстрационный не совсем
выявить те же уроки, извлеченные.
[ПРОИГРЫВАНИЕ ВИДЕО]
-Все Я хочу, чтобы вы сейчас сделать, это найти для меня, и для нас,
действительно, число 50 шаг за шагом.
>> -Количество 50?
>> -Количество 50.
И вы можете выявить то, что За каждым из этих дверей
просто касаясь его пальцем.
Блин.
>> [СМЕЮЩИЙСЯ]
>> [КОНЕЦ ПРОСМОТРА]
Дэвид Дж Малан: Так что пошли очень хорошо.
Те были несортированные двери.
И Джей, конечно, найти все это слишком быстро.
Тревор сделал намного лучшую работу в терминах доступный момент,
так сказать, в этом году в занимает больше времени, чтобы найти его.
Конечно, тогда мы дали Джей второй шанс,
в результате чего мы отсортировали двери, как мы это делали для Тревора,
и Тревор сделал супер хорошо в этот раз.
Но Джей сделал это в два раза быстрее.
[ПРОИГРЫВАНИЕ ВИДЕО]
-The Целью теперь является также найти нам номер 50,
но сделать это алгоритмически, и расскажите нам, как вы собираетесь об этом.
>> -ХОРОШО.
>> -А Если вы найдете его, вы держите кино.
Если вы не найдете его, вы дать его обратно.
>> -Мужчина.
>> -Ой!
>> - [Неразборчиво] ОК.
Так что я собираюсь проверить концы сначала определить, если there's-- О.
>> [Аплодисменты]
>> [КОНЕЦ ПРОСМОТРА]
Дэвид Дж Малан: ОК.
Так сортировки двери ясно приводит к большей эффективности.
И так, в два раза быстрее это то, что я имел в виду там.
И так Джей повезло оба раза.
И он также повезло в прошлом, что год, я заказал несколько Blu-Ray дисков
на самом деле выдают.
Мне жаль, в этом году мы не имеют то же самое, Тревор.
Но все-таки лучше было несколько лет назад.
И некоторые из вас, возможно, знаете, это парень, Шон, который, когда он был в CS50,
был брошен вызов с точным Та же проблема, хотя и в SD,
как вы скоро увидите, назад в день.
И вы увидите, что не только сделал он займет немного больше времени, чем Джей,
немного больше, чем Тревор, это было на самом деле это прекрасная возможность
заниматься почти все в Толпа ла Цена справа, поощряя
ему найти номер, мы искали.
Давайте. взять быстрый взгляд.
>> [ПРОИГРЫВАНИЕ ВИДЕО]
>> -ХОРОШО.
Так ваша задача здесь, Шон, состоит в следующем.
Я спрятал за ними Двери число семь.
Но спрятан в некоторых из этих дверей а также другие отрицательные числа.
И ваша цель, чтобы думать этой верхней строке чисел
как только массив, или просто Последовательность бумажек
с номерами позади них.
И ваша цель, используя только верхнюю Массив здесь, найти мне номер семь.
И мы затем собирается критиковать как вы идете о делать это.
-Все в порядке.
-Найти Нам номер семь, пожалуйста.
Нет.
Пять, 19, 13.
>> [СМЕЮЩИЙСЯ]
>> Это не вопрос с подвохом.
Один.
>> [СМЕЮЩИЙСЯ]
На данный момент, ваш счет не очень хорошо, так что вы могли бы также продолжать.
Три.
>> [СМЕЮЩИЙСЯ]
>> Продолжай.
Честно говоря, я не могу помочь, но интересно, то, что вы даже думать о, so--
>> [СМЕЮЩИЙСЯ]
Только верхний ряд, так у вас есть три слева.
Так что найдите мне семь.
>> [СМЕЮЩИЙСЯ]
17.
Семь.
>> [Аплодисменты]
>> Все в порядке.
>> [КОНЕЦ ПРОСМОТРА]
>> Дэвид Дж Малан: Таким образом, мы могли смотреть это в течение всего дня.
И, конечно, некоторые из демо в этом году, возможно,
Теперь будет в конечном итоге в следующий видео года, а также.
Так что теперь давайте на самом деле сосредоточиться на алгоритмах
здесь, чтобы увидеть, если мы не можем Теперь начинают формализовать
как мы можем идти о получении наших данных в этом состоянии, что это сортируется,
так что в конечном счете, мы можем на самом деле искать его более эффективно.
И хотя мы собираемся использовать довольно небольшие наборы данных,
как мы восемь чисел есть здесь, на борту,
в конечном счете, эти же идеи можно применить 1000 входов, миллион входов,
4 млрд входы, потому что алгоритмы будут принципиально то же самое.
>> И таким образом, это наш последний возможность для добровольцев сегодня,
но, пожалуй, наиболее активное участие одного, для которых мы должны восемь добровольцев
прийти и ходить с нами через Процесс сортировки, что скоро
быть на этих музыке стоит здесь.
Позвольте мне начать снова здесь.
>> Таким образом, одна в turquoise-- зеленый это?
Вы совершении?
Два.
Идем вниз.
ХОРОШО.
Три.
4.
Пусть me-- ОК, пять.
Вы выдвигается вашим другом.
Шесть, семь, восемь.
Давай до.
Все в порядке.
Огромное спасибо.
Давай до.
>> Все в порядке.
Так что у нас есть here-- и это является одним из наиболее неудобных те,
так как это потребует, чтобы вы юмор мне в течение только немного времени.
Вы должны быть номер один.
Как тебя зовут?
>> АННАН: Аннан.
>> Дэвид Дж Малан: Аннан.
Дэвид.
Как тебя зовут?
>> ИОСИФ: Джозеф.
>> Дэвид Дж Малан: Иосиф, Вы номер два.
>> Серена: Серена, номер три.
Стефан, номер четыре.
СИНТИЯ: Синтия.
Дэвид Дж Малан: Синтия, номер пять.
[Неразборчиво]
Дэвид Дж Малан: [неразборчиво].
Дэвид, номер шесть.
Мэтт: Мэтт.
Дэвид Дж Малан: количество Мэтта семь.
А?
>> WAVERLY: Уэверли.
>> Дэвид Дж Малан: Уэверли, номер восемь.
Все в порядке.
Если вы could-- возгласы.
Если вы все, как ваш Первая задача, есть
восемь пюпитры здесь перед аудиторией.
Если бы вы могли поместить свои номера на Эти музыкальные выступает таким образом,
что они выстраиваются с те же номера на доске.
Так что сами выглядеть по положить ваши номера на этих музыке
стоит здесь.
Отлично сих пор.
>> Отлично.
ХОРОШО.
Так что теперь, мы собираемся спросить Вопрос в несколько различных способов.
Как мы можем идти о сортировке эти люди здесь?
Потому что у нас было несколько подходов ранее, в результате чего мы были
вид делает две разные ведра.
А потом мы, как правило, пирсингом вещи вместе.
Как только мы увидели две цифры который принадлежал вместе,
положить их вместе.
Два письма, которые принадлежат вместе.
>> Но давайте посмотрим, если мы не может оформить это,
так что в конечном итоге мы должны некоторые псевдо-код будет,
с помощью которого можно решить эти проблемы.
Так что теперь, я смотрел на эти цифры здесь.
И я вижу целую кучу ошибок.
В конечном счете, я хочу одна на влево и восемь на правой.
>> И поэтому я, глядя на эти два, четыре и два.
И в чем проблема, очевидно,?
Да.
Так.
Два явно идет перед четыре, так что вы знаете, что?
Позвольте мне сначала взять жадный подход, если вы будете, как и проблема
установить одно-- если вы помните из Стандартная редакция задачи один набор,
где я только локально решить проблему что прямо здесь передо мной
и увидеть, где она ведет меня.
>> ХОРОШО.
Так два и четыре, позвольте мне перейти вперед и просто поменять вам два.
Если вы можете физически переместить сами и ваша газета,
Я, кажется, получили перечислить в лучшем состоянии.
>> Теперь, они хороши.
Я собираюсь двигаться дальше, четырех и шести, выглядит хорошо.
Не проблема.
Шесть и восемь, ОК.
Восемь и один, еще одна проблема.
Потому что правда о восьми и одной?
Один приходит до восьми, и так, что мы должны делать?
Давайте поменять эти два.
Один и восемь.
А теперь, я собираюсь продолжать.
Я собираюсь продолжать смотреть вперед.
И давайте посмотрим, что произойдет.
Восемь и три, из Конечно, в порядке.
Давайте своп.
Восемь и семь, конечно.
Вышел из строя.
Давайте своп.
Восемь лет и пять, конечно, давайте подкачки.
Все в порядке.
Список сортируется.
Да?
>> ОК, очевидно, нет.
Но это немного лучше, верно?
Потому что уведомление, что произошло.
Каждый раз, когда мы провели обмен, меньше Количество и тип процеживают, что путь,
и большее число перколируют этот путь, или мы будем
начать говорить пропускают к влево или барботируют вправо.
>> Теперь, это не достаточно, потому что в лучшем случае число может
перешли одно место вперед, или в худшем случае,
ряд, возможно, переехал на одну позицию дальше.
Таким образом, вы знаете, что этот вид из работал очень хорошо до сих пор.
Позвольте мне попробовать еще раз.
Два и четыре, они ОК.
Четыре и шесть, они ОК.
Шесть и один, вышел из строя.
Итак, давайте поменять вам два.
А теперь обратите внимание, что проблема-х начинают получать немного лучше снова.
Шесть и три, вышел из строя.
Давайте менять вас два.
Шесть и семь, вы хорошо.
Семь и пять, конечно, в порядке.
Семь и восемь, в порядке.
А теперь, я, возможно, потребуется сделать это несколько раз.
И в самом деле, думаю, для себя возможно, сколько раз максимально
может я должен ходить взад и вперед?
>> Мы вернемся к этому.
Так два и четыре по-прежнему ОК.
Четыре и один, Нет.
Итак, давайте своп.
И снова, обратите внимание, визуально один из пузырьков вид
слева, где он должен быть.
Четыре и три замены.
Четыре и шесть.
Шесть и пять подкачки.
Шесть и семь.
Семь и восемь хороши.
>> Хорошо.
Мы получаем еще лучше.
Итак, давайте посмотрим.
Теперь у нас есть два и один.
Конечно, поменять.
Два и три, три и четыре, четыре и пять, шесть и семь, семь и восемь.
Хорошо.
И вы знаете, что?
Потому что я сделал одно изменение есть, позвольте мне сделать одну проверку вменяемости.
Позвольте мне пройти весь путь вернуться к началу.
ХОРОШО.
Один из них, two-- да, видите?
Что-то было не так.
Три, четыре, пять, шесть, семь, восемь.
И в этом последнем проходе, являются вы можете прямо сейчас с моим
утверждая, что это сортируется?
ХОРОШО.
Визуально, это абсолютно верно.
Но функционально, чем так и просто так
в этом последнем проходе, что позволяет чтобы подтвердить, что этот список действительно
отсортировано?
>> Что я делать или не делать этого последнего паса?
АУДИТОРИЯ: Там не было никаких изменений.
Дэвид Дж Малан: Извините?
АУДИТОРИЯ: Нет изменений.
Дэвид Дж Малан: Там не было никаких изменений.
Так что было бы глупо с моей стороны сделать это снова тот же алгоритм
если я не сделать любое изменения в первый раз.
И государство не изменилась.
Конечно, я не собираюсь делать любых изменений во второй раз.
И так, это теперь в безопасности сказать, список отсортирован.
>> И в самом деле, это сейчас то, что мы будем, как правило
Вызов пузырьковой сортировки, в результате чего попарно, вам исправить ошибки снова,
и снова, и снова, и вам держать вперед и назад,
не и назад и вперед, пока вы не делают такие свопы, на которых точка
Вы можете быть уверены, что, да, я закончил фиксации всех ошибок.
Давайте сброс и попробовать другой подход.
Если вы, ребята, могли бы вернуться в заказ вы были минуту назад,
который выглядел, как это.
Теперь, давайте рассмотрим подход, немного больше, как экзамен книги,
в результате чего мы были постоянно выбрав букву алфавита
что мы как-то хотел чтобы иметь дело с другой.
Может быть, это был высокий письмо, как А, или низкой буквы Z.
>> Таким образом, каждый вернулся в этом порядке.
А теперь позвольте мне сделать это.
Давайте посмотрим, я знаю, что есть восемь цифр здесь.
Я собираюсь идти вперед и просто сознательно выбрать
наименьшие элементы.
Правильно?
Это, кажется, интуитивно тоже.
Почему я не могу найти наименьший элемент, положить его, где она принадлежит,
а затем получить следующий наименьший элемент, поставить это, где это принадлежит, и только повторить.
>> Потому что интуитивно, который должен работать тоже.
Так четыре, это довольно малое число.
Я буду помнить, где это.
Подожди минуту.
Два меньше.
Позвольте мне теперь вспомните, когда два есть, и забыть о четырех.
Мы будем иметь дело с этим позже.
Шесть, мне это не интересно.
Восемь, я не заинтересован в.
Один мой новый малое число.
Так что я собираюсь вспомнить, где ты есть.
Три, не интересует.
Семь, не интересует.
Пять, не интересует.
>> Так, не падая этап в этом году,
Я собираюсь захватить количество одно-- и то, что снова ваше имя?
>> АННАН: Аннан.
>> Дэвид Дж Малан: Аннан.
И если бы вы могли присоединиться ко мне в начало списка,
давайте вам, где вы принадлежите.
Unfortunately-- что ваше имя?
>> СТЕПАН: Стефан.
>> Дэвид Дж Малан: Стефан находится в пути.
Поэтому, прежде чем Стефан решает эту Проблема, что мы должны делать?
Что мы делаем со Стефаном?
>> АУДИТОРИЯ: [неразборчиво].
Дэвид Дж Малан: ОК.
Таким образом, мы могли бы сделать это.
Мы могли бы принять своего рода Стефана и его четыре, и просто положить его в переменной
и провести на ней некоторое количество времени,
тем самым освобождая место для номер один.
И это не плохо.
Я мог бы предложить, почему не мы просто положить Стефана здесь?
Почему это может нарушить один идей мы начали
говорить о последнем времени, на прошлой неделе?
Да?
>> АУДИТОРИЯ: [неразборчиво].
>> Дэвид Дж Малан: Там нет Индекс для него.
Если вы думаете, это, действительно, как Массив, это как отрицательный,
так что нет на самом деле память здесь, если это действительно массив,
как мы объявили на прошлой неделе в лекции.
Таким образом, мы не должны делать этого.
Мы могли бы хранить его в переменной.
>> Или вы знаете, что?
Я слышал, кто-то еще предложить это.
Что еще мы можем сделать со Стефаном?
Почему бы нам просто не выселить его и положить его на себя, где номер один было.
Так что, если вы хотите пойти туда.
И в самом деле, это довольно хорошее решение.
Теперь, с одной стороны, я вроде из сделал проблему хуже.
Четыре теперь дальше от того, где это должно быть.
Она должна быть к этому половине.
>> Но вы знаете, что?
Это можно было бы невезение.
Может быть, номер восемь был здесь.
И так, может быть, мы бы получили повезло,
и толкнул восемь ближе к концу.
Таким образом, в конце концов, Это отчасти все средние из.
Нам не нужно заботиться о четырех.
Все, что я забочусь о прямо сейчас выбора наименьшего элемента.
>> А теперь, что я собираюсь сделать, это забыть о номер один
постоянно, потому что я знаю Список позади меня теперь сортируются.
Так что мой список был ранее размер восемь.
Теперь, это размер семь.
Так моя проблема становится меньше, хотя линейно.
Так что теперь, я собираюсь выбрать ток наименьший элемент, два.
Шесть, восемь, четыре, три, семь, пять.
Это был наименьший элемент.
Так что я собираюсь сделать with-- какой был ваше имя?
>> ИОСИФ: Джозеф.
>> Дэвид Дж Малан: Джозеф?
Мы собираемся, чтобы оставить Иосифа на месте.
Теперь, я собираюсь делать вид, что эти ребята хорошо are--,
Я знаю, что эти два уже отсортированы.
Давайте теперь сосредоточиться на Остальная часть списка.
Шесть является текущим наименьшим.
Восемь больше.
Четыре теперь ток маленький.
Три теперь тока мала.
И вот теперь, я собираюсь выбрать три, которые is-- что ваше имя снова?
Серена: Серена.
Дэвид Дж Малан: Серена, если бы вы могли захватить ваш номер и своп with--
Калсанг: Калсанг.
Дэвид Дж Малан: Калсанг.
Возвращайся, и мы собирается поменять эти два.
А теперь, давайте поставить это на автопилоте.
Я собираюсь пойти и оставить его с вами, ребята чтобы выбрать следующие наименьшие элементы.
Дун, серовато, серовато, серовато.
Номер четыре, что вы должны делать?
Отлично.
Теперь, я собираюсь сделать еще один проход.
Дун, серовато, серовато, серовато.
Я вижу пять является следующим наименьшим.
Теперь, я собираюсь взять еще один проход.
Дун, серовато, серовато, серовато.
Шесть является наименьшим.
Хорошо.
Семь самых маленьких.
Без изменений.
Восемь самых маленьких.
Готово.
>> Так что мы только что сделали итеративно выбрав один элемент за другим
это реализовать то, что мы собирается оформить в выборе рода.
И это, возможно, даже проще объяснить,
в том, что буквально все, что вы хочу сделать, это просто держать
вперед и назад по списку выбора, следующий наименьший элемент,
пока вы не закончите.
>> Так что это даже проще, возможно, интуитивно, чем в прошлом.
Давайте попробуем один последний.
Если вы, ребята, может сбросить себя в следующих положениях
один последний раз, давайте посмотрим, если мы не можем Теперь оформить еще один подход.
В самом деле, кто-то там бы предложить
как еще мы могли бы идти об этом?
Без выбросить словечки или рода ответов, которые уже известны,
просто интуитивно, что мы могли сделать?
>> АУДИТОРИЯ: [неразборчиво].
Дэвид Дж Малан: Да.
Так что некоторые большие интуиция есть.
Хорошие вещи, кажется, до сих пор случаются в компьютерной науке, когда мы делим
и завоевать проблему деления это в два раза и половина на половину.
И так на самом деле, мы может начать делать это.
И в самом деле, что будет, мы будем см, один из наших лучших решений пока.
Но давайте вернемся к тому, что в скором времени.
На самом деле, мы собираемся сделать что чуть позже на этой неделе.
Что еще мы могли бы сделать, чтобы решить эту проблему?
Таким образом, каждый здесь в казалось бы, случайном порядке.
Знаешь что?
Вместо идти вперед и назад, взад и вперед, взад и вперед
каждый раз, это чувствует себя подобно Я делаю много ходить.
Почему я не могу просто начать в начало списка,
и просто поставить четыре, где она принадлежит?
Итак, позвольте мне предположить, что в данный момент мой список только этот первый элемент.
Четырех сортируются в этот момент времени, если все, что я забочусь о том все здесь?
Это своего рода тривиально, не так ли?
Как список, содержащий один номер, и что номер четыре, очевидно, сортируются.
>> Итак, позвольте мне просто оговорить что этот список сортируется.
Но теперь у меня есть все остальное в этом списке.
Так что теперь, я сталкиваюсь с два.
Где два, очевидно, принадлежат в отношении четырех?
Перед четырех.
Так что я могу здесь делать?
Как твое имя, еще раз?
>> ИОСИФ: Джозеф.
>> Дэвид Дж Малан: Иосиф, если бы вы могли отступить
на мгновение с вашим номером.
А теперь то, что должно Стефан здесь делать?
Давайте переложить Стефана сюда.
А теперь, давайте Иосиф пришел сюда.
А теперь, позвольте мне заявить, что здесь все сортируется.
Так, аналогичный результат, но Принципиально иной подход.
Я даже не смотрел, что там внизу.
Я просто продолжать принимать элементы как они передали мне,
и борьбы с ними.
>> Так что теперь, я вижу, номер шесть.
Где номер шесть принадлежат?
У нас есть два, четыре, шесть.
Точно, где она сейчас находится.
Так что давайте оставим в покое, что, и в настоящее время утверждают, что этой части списка
теперь сортируются.
И так, это чувствует себя принципиально отличается тем, что я просто
перемещение по списку здесь линейно, и я никогда не удвоение назад.
Да.
Все в порядке.
Так восемь, где вы принадлежите?
Прямо здесь.
Отлично.
Так что теперь, один.
Ой-ой.
Это чувствует, как будто это будет дорого.
Теперь, в предыдущем алгоритме, Я просто поменялись людей.
Так что я положил ему может полностью на начало, но потом переехал Иосифа.
Но, если я перееду Иосифа, теперь что будет так?
>> Теперь, я вроде undone-- У меня принимать один шаг вперед, а затем
один шаг назад, потому что теперь Джозеф будет в порядке.
Так давайте сделаем это.
Если бы вы могли взять номер один и шаг назад на мгновение.
Как мы можем put--, что Ваше имя было снова?
>> АННАН: Аннан.
>> Дэвид Дж Малан: Аннан на месте?
Что должно произойти в отношении до двух, четырех, шести, восьми и?
Все они должны переместить.
Так что, если восемь хотел переложить , а затем шесть, потом четыре, потом два.
И тогда Аннан, если бы вы хотел приехать сюда, хорошо.
Но здесь, мы только вид заплатила
в другой точке в алгоритме.
В то время как последний раз с выбором сортировать и даже пузырьковой сортировки,
Я иду назад и вперед, назад и вперед,
который, безусловно, добавив, до Время-мудрый, и буквально поэтапно.
>> Сортировка вставками, на первый взгляд, выглядит, как будто это
супер умнее, в том, что я просто медленный, постепенный прогресс,
но я не собираюсь это назад и вперед.
Но если кто-то действительно из порядка, предупреждения
все работы я просто должен был сделать.
Мне пришлось переехать половина списка просто, чтобы освободить место для номер один.
Так что это то же самое количество работы до сих пор его
чувствует, просто другой тип работы.
>> Давай продолжим.
Так что теперь мы знаем, что каждый от одного до восьми сортируются.
Вот, у меня есть номер три.
Если вы хотите, чтобы забрать Номер три, шаг назад один.
И то, что вы, ребята, нужно сделать?
Ага.
Так что еще один, два, три шага.
Три единицы времени, которые просто стоят я, так что три могут теперь подходят.
Наконец, семь.
>> Давайте идти вперед и Вы шаг назад.
Это будет только стоить нам одна единица времени, но это нормально.
А теперь, пять собирается быть немного дороже.
Если вы хотите сделать шаг назад.
Мы должны двигаться восемь, и семь, а шесть.
И тогда все будет теперь сортируются.
Таким образом, большая рука, чтобы наши добровольцы здесь.
Огромное спасибо.
>> [Аплодисменты]
>> Спасибо вам всем.
Спасибо вам всем.
Итак, давайте посмотрим, как теперь просто дорого все, что было.
Давайте рассмотрим, пожалуй, Простейший из них, пузырьковая сортировка.
И я говорю простой, только потому, что Вы можете решить ее с жадностью, просто
исправить попарно проблема.
Закрепите попарно проблемы Здесь, снова и снова
и снова, повторяя как многие раз, как вы на самом деле нужно.
>> Так что получается, что с пузырьковой сортировки, хорошо,
сколько шагов я должен взять на себя первый проход этого алгоритма?
Я мог бы take-- давайте see-- один, два, три, четыре, пять, шесть, семь.
И есть восемь элементов здесь.
Так как п минус 1 до шаги получить от начала списка
в конце списка.
>> Но выбора-то, напомним, что я снова и снова, выбирая элементы
и снова, что это маленький, Я ставлю его на месте,
но тогда я не ищу позади меня снова.
Так что я думаю, что это немного более ясным то, что в первый раз, я мог бы
должны принять все п минус 1 шаги найти наименьший элемент.
Тогда я поставить их на место, и я выселить кто был здесь ранее.
>> Но тогда я не должен держать глядя на этот элемент,
потому что я знаю, что это Уже наименьшим.
Так что теперь, я могу смотреть на всего семь элементов, то шесть элементов,
затем пять элементов, то четыре элемента.
И так математически, если п число элементов или цифр
что мы начали с того, что вы можете себе что это то же самое, п минус 1,
плюс минус 2 п шагов, плюс минус 3 п шагов,
плюс минус 4 п шагов, все вплоть до всего один шаг.
И я на моем последнем человека.
>> И если вы помните, что много из книги или статистика математические книги
есть те формулы, на твердом переплете назад или перед ними,
выясняется, что этой серии может быть выражено более просто
минус, как в п раз п 1 над 2.
И это нормально, если это не на переднем крае своего ума.
Но это действительно так.
Это просто простой способ написания.
И потом, если вы думаете, вернуться к начальной школе,
когда вы только начинаете умножения вещи из, это, конечно,,
просто н квадрате минус п делится на 2.
Все, что я сделал, это расширить выражения там.
И так давайте перепишем это немного по-другому.
Вот н квадрате разделить на 2 минус п / 2.
>> Итак, еще раз, я просто вид применения некоторые арифметические правила есть.
Но обратите внимание, в настоящее время, что самая большая термин в этом выражении, так сказать,
является то, что п в квадрате.
Так что, да, это п квадрат делится на 2, минус п / 2.
>> Но в целом, если п будет большое значение,
Я собираюсь утверждать, что п в квадрате будет доминирующим фактором.
Это просто будет большая вклад
на число шагов, чем N / 2.
Так что я имею в виду под этим?
Давайте попробуем простой пример, даже хотя математика получает немного большим.
>> Итак, пусть у нас было 1 млн человек на сцене, или 1 млн вещей
что мы хотим, чтобы разобраться.
Давайте подключить миллион в этой формуле точно
чтобы увидеть, сколько шагов он принимает общей сортировать миллион элементы, используя скажем,
Выбор рода.
>> Таким образом, мы должны были бы ту же формулу, как и раньше.
Я подключить миллион, так что я получаю миллион квадрат делится на 2,
минус миллион разделить на 2.
Если я что математику в заранее здесь, у нас есть 500 млрд
минус 500000, который дает нам +499999500000,
что чертовски большой.
>> В самом деле, если сравнить с предприятием 499000000000 999 млн
500000 против нашей первоначальной стоимости, 500 миллиардов, это так чертовски близко.
Правильно? п квадрате разделить на 2 дает us-- или, скорее, н квадрате разделить на 2
дал нам 500 млрд.
Это чертовски близко чтобы 499,999,500,000,
который должен сказать, вычитания от 500000, или в более общем, вычитая от
п квадрате, на самом деле не большое дело.
В Русской квадрат делает эти число вырастет очень быстро.
>> Теперь, это только важное значение, поскольку как мы, как компьютерные ученых,
как правило, не будет заботиться так много о нюансах этих формул
и именно то, что точные ответы.
Мы заботимся лишь, что, вы знаете, что?
В конце концов, эта формула составляет порядка п квадрат.
>> Да, мы деления на 2 в там.
Да, мы вычитая от п минус 2.
Но в конце концов, термин что на самом деле вредит нам и стоит нам
много шагов, что квадрат термин.
И так, что ученый-компьютерщик собирается как правило, делают
это игнорировать все те меньшие сроки, порядок
и просто посмотреть на тот, который способствует наиболее к стоимости.
>> И это приятно, потому что мы можем Теперь поговорим гораздо большей общности
об алгоритмах, и может сравнить их.
И тот факт, что я с помощью этого вывода является преднамеренным.
Когда я говорю о порядке из, я специально
ссылаясь на то называется большой О. И Big O
это обозначение, что компьютер Ученый использует, чтобы описать
верхняя граница на что-то.
>> Так что, если вы говорите, что алгоритм в большом O н квадрат,
как я предложил просто Минуту назад, что средства
что с точки зрения его эксплуатации времени или его эффективность,
она занимает порядка н квадрате шаги.
Может быть, больше, может меньше.
Но это на порядок п в квадрате.
И это верхняя граница.
Это не будет более болезненным, чем это.
Это не будет п кубе, или 2 к п, или что-то гораздо большее.
Это верхняя граница на то, что, что стоимость.
Поэтому, учитывая, что, давайте Рассмотрим несколько примеров.
И это только конечный список очень общие времени прохождения
Для алгоритмов, которые предназначается, чтобы быть иллюстрируют некоторые вещи, которые мы
видел уже.
>> Так, например, в случае Выбор рода, что я утверждая, здесь
работает, что выбор Сорта время на порядок п в квадрате.
В худшем случае, я буду иметь целая куча случайных чисел здесь.
И, как мы видели математически, если я постоянно ходить
по списку, через Список, выбрав следующий маленький
элемент снова и снова, если я на самом деле записать все шаги
Я принимаю я предложил formulaically прежде, это порядка п квадратов
шаги, которые я принимаю.
>> И получается, что пузырь отсортируйте сортировка вставками
так же, как медленно в худшем случае.
Рассмотрим, например, сортировка вставками, самый последний алгоритм мы имели дело с,
который заставил нас посмотреть на элемент, а затем вставьте его там, где он принадлежит.
А потом мы смотрели на следующий элемент, и вставляется там, где он принадлежит.
>> Так считают лучший возможный сценарий.
Предположим, я мои добровольцы выстраиваются буквально, как это, от одного до восьми,
уже отсортированы.
Сколько шагов является сортировка вставками собирается предпринять, чтобы разобраться восемь человек,
если они прибывают на сцене глядя, как это?
>> Восемь человек уже отсортированы.
И я использую вставки рода.
Это последний из алгоритмов.
Ну, давайте воспроизвести очень быстро.
Так что, если я начинаю здесь, я вижу один.
Где же можно принадлежат?
Он принадлежит здесь.
Я вижу два.
Где двое принадлежат?
Прямо здесь.
Я вижу три.
Где три принадлежат?
Прямо здесь.
>> Я вижу четыре.
Прямо здесь.
Пять, шесть, семь, восемь.
Там нет причин, чтобы повторяться.
И так, сколько шагов является то, что через п?
Это на порядок п шаги, верно? п минус 1.
Но я взял линейный номер шагов, и теперь я сделал.
Так что это лучший случай, хотя.
Что можно сказать о худшем случае?
Что восемь были там, и семь были там,
и один и два были здесь, так что список действительно были вспять?
>> Ну, то, что происходит на самом деле если это число?
И мы будем делать только пару примеров.
Что делать, если, действительно, номер восемь здесь, и number-- возгласы.
Так что, если, действительно, количество Восемь полностью здесь,
и я использую вставки рода?
>> ХОРОШО.
Я утверждаю, на данный момент он находится в месте.
Но теперь, seven-- где же семь идти?
Конечно, это идет здесь.
Так что я должен двигаться восемь над одном месте.
Теперь шесть, где это идет?
Ну ладно.
Теперь, я должен двигаться восемь над место, и семь над местом,
и тогда я плюхнуться шесть.
>> Таким образом, первый раз, это стоимость мне один шаг, чтобы исправить положение,
то это стоило мне два шага, чтобы исправить положение.
Сколько шагов это собирается предпринять, чтобы исправить
вещи, чтобы поставить пять в нужном месте?
Три.
Потому что теперь я должен двигаться один, два, три.
Сколько шагов он собирается взять положить четыре в нужном месте?
4 плюс 5, плюс 6 плюс 7.
>> И так это математически идентичны то, что мы описали для выбора рода.
У нас есть эта серия вот только растет.
1 плюс 2 плюс 3 плюс 4, или, наоборот, плюс 6 7
плюс 5 плюс 4 добавляет на сегодня Цели в порядка п в квадрате.
>> Итак, позвольте мне предусматривают также, что пузырьковой сортировки также в п квадрате.
Потому что с пузырьковой сортировки, каждый раз я иду по списку,
Я принимаю примерно, сколько шагов?
Каждый раз, когда я буквально ходьбы от туда попасть?
Примерно п шагов.
Но сколько раз я мог бы нужно идти по списку?
>> Ну, примерно п раз.
Может п минус 1, но примерно в п раз.
Ну, почему же?
Ну, с пузырьковой сортировки, если мы начинаем с пузырьковой сортировки,
со списком в худшем ситуация, которая снова полностью
в обратном направлении, то, что произойдет?
Я иду по списку, и номер одним принадлежит весь путь туда.
>> Но с пузырьковой сортировки, насколько делает один двигаться на моем первом проходе по списку?
Сколько места он получает ближе к правильному месту?
Только один.
Так что, если вас вид причина через это, каждый раз, когда через этот алгоритм,
Давида, принимающие около п шагов.
Но сколько проходит через список его
собирается взять для одного пузыря слева, где она принадлежит?
>> Он должен двигаться, как, п пространства таким образом.
Так что, чтобы сделать сортировку списка, Я должен ходить взад и вперед п раз.
И каждый раз, я глядя на п элементов.
Так что русские вещи п раз на порядок п в квадрате.
>> Теперь мы увидим, в некоторых шорт, что
встроены в следующей проблеме CS50 в установить, другой подход в них,
но сейчас, давайте просто рассмотрим некоторые другие текущие времена,
особенно если принять те сортировки немного времени, чтобы погрузиться в.
Что такое алгоритм мы уже видели что берет на себя порядка п шагов?
>> Что следует принять линейный номер шагов, которые мы видели до сих пор?
Что это?
Поиск телефонный справочник.
Первый алгоритм.
Правильно?
Где мы линейно поиск Майк Смит?
Действительно.
От нулевой неделе, когда я начал превращая одну страницу в то время,
и я даже сказал, что это был вид алгоритма линейной чувство,
и у нас было что картинка на доска с прямой красной линии
и прямой желтый линия, это были действительно
алгоритмы, которые в большом O п.
>> Потому что, чтобы найти Майка Смита в телефоне Книга русских страниц, в худшем случае,
может взять меня н шаги.
Что о принятии посещаемость?
Один два три четыре пять шесть.
Что время работы этого Алгоритм для принятия посещаемости?
Большой О п, потому что в теории я должен указать всех в комнате.
>> Теперь, как в сторону, то, что о другой оптимизации с нуля неделю?
Два, четыре, шесть, восемь, 10, 12.
Компьютер ученый будет реализовать, подождите минуту,
это порядка п делится на два этапа.
Правильно?
Потому что я делаю два человека одновременно.
Но мы собираемся игнорировать эти младшие члены,
и мы только собираемся выбросить разделить на 2,
и просто сказать, большой вывода п для этого алгоритма, а также.
>> Как насчет этого?
Мы пропускаем некоторые из них, но то, что был алгоритм, который был журнал п?
Это заняло примерно войти п шагов?
Разделяй и властвуй.
В точку.
Как, например телефонной книги в нулевой неделе и сегодня утром,
где мы разделили проблемы Снова и снова и снова.
Мы обратили его на доске в неделю нулю при изогнутой зеленой линией,
и мы сказали, что это был день логарифмическая алгоритм.
>> И в самом деле, число шагов, она, требуется, чтобы выполнить разделяй и властвуй,
или бинарный поиск, как мы начнем называя его, как в телефонной книге,
на порядок журнале и шагов.
И это немного странно одно.
>> Что делает шаг, или, более конкретно
постоянное число шагов?
Может быть, это двое, может быть, это три, но ученый просто
упрощает его как Big O 1, некоторая константа число шагов.
Что-то вы могли бы сделать, что принимает постоянное количество шагов?
>> Что время работы хлопая?
Постоянное время.
Правильно?
Мол, то, что время работы делать что-либо, что берет только один
Операция, как печатать F Hello World.
Это может быть названо постоянная времени, если меньше угол случае с F печать,
Что может время работы печати F на самом деле быть?
И почему?
Что н измерения в этом случае?
>> АУДИТОРИЯ: [неразборчиво].
Дэвид Дж Малан: Точно.
Количество символов мы хотим, чтобы напечатать.
Так что это очень контекста.
Сегодня мы сосредоточились много на буквы и цифры здесь на доске.
Но это может быть также символы в реальную строку.
Вот и получается, есть другой мера, которая начнет заботиться о,
и это напротив большого О, так сказать.
>> Это омега обозначения.
В то время как большая вывода означает, что это, то Верхняя граница на беговой времени?
Максимально, сколько времени может что-то взять?
Omega-- жаль, что это продолжает прибывать up-- является противоположностью, что
в результате чего это нижняя граница на количество времени что-то может занять.
>> Так. Например, то, что алгоритм который принимает всегда н в квадрате шаги?
Ну, один из алгоритмов мы видели Сегодня, на самом деле, может быть, что, как хорошо.
Сортировать Выбор.
Выбор рода довольно глупо.
Даже если algorithm-- извините, даже если массив уже отсортированы,
Выбор рода собирается продолжать идти по списку
чтобы убедиться, что он имеет наименьшее элемент снова и снова, и снова.
И хотя вы, люди в Зрители знают, что, подожди минутку,
Вы уже принят наименьший элемент, компьютер
не знает, что, пока она выглядит весь путь через список.
Аналогичным образом, нижняя граница, что может быть также приняты во внимание
может быть линейное время.
>> Сколько времени нужно, чтобы Сортировать п элементов в лучшее
Дело используя что-то вроде пузыря рода?
Предположим, что ваш список уже отсортирован.
Мы сказали, пузырьковая сортировка берет на порядок п квадрате шаги.
Но что, если это уже отсортированы?
Что делать, если вы понимаете, после один проход по массиву
что вы не сделали ни одного свопы?
Вы должны продолжать делать больше проходит?
>> Нет.
Таким образом, нижняя граница пузырьковой сортировки можно сказать, быть линейной.
Омега п.
И мы можем смотреть на остальные них, а также.
Итак, давайте взглянем на только визуализации здесь
чтобы увидеть, как они отличаются.
Я собираюсь пойти сюда в это страница, которая доступна на веб-сайте С50, в
но это будет боль, чтобы получить работу, так как он использует технологию под названием
Java-апплеты, который является в значительной степени поддерживается в эти дни,
по крайней мере, Chrome и некоторых других.
>> И позвольте мне идти вперед и ускорить этот и объяснить, что происходит.
Это демонстрация пузыря сортировать, первый алгоритм, мы смотрели.
И это визуализация, что каждый из этих стержней представляет собой число.
Чем больше бар, тем больше число.
Чем меньше бар, чем меньше число.
И то, что вы можете увидеть визуально, даже хотя это будет очень быстро,
является то, что красная полоса, как меня, ходить взад и вперед фиксации проблемы.
Вы можете видеть, что чем больше элементов действительно бьется справа,
и меньше элементов которые бьется слева.
И здесь, если мы на самом деле выглядят более тесно,
мы можем на самом деле подсчитать количество сравнений и обменов
что были сделаны.
>> Но вместо этого, давайте посмотрим на втором алгоритме
мы смотрели на ранее с нашей волонтеры, выбор сортировки.
Визуально он имеет очень разные эффект.
Но это, опять же, очень интуитивным, в что мы держим выбора следующего маленький
элемент, и мы получили немного повезло.
Это чувствовал принципиально быстрее.
Но если мы побежали это снова и снова и снова с большим количеством входов,
мы увидим, что на самом деле это еще в большой O п квадрате.
>> Давайте сделаем один последний здесь, сортировка вставками,
который был третьим алгоритм мы смотрели на, и отзыве
что это одно дело с элементы, как это сталкивается их,
Но тогда, может быть, сдвиги вещи, чтобы освободить место,
вставки элементов, где они принадлежат.
>> И это тоже заканчивается давая конечный результат. Теперь все три из них
чувствовал себя довольно быстро.
И в самом деле, я побежал их на довольно хороший клип.
Но принципиально, все они довольно ужасно, честно говоря.
Все эти алгоритмы до сих пор которые работают в большом O п квадрате
принять совсем немного время для запуска в конце концов.
>> И действительно, мы видим, и чувствую, что это, наконец,
если тянуть эту третью и последнюю демо.
Это еще одна визуализации, что происходит,
показать пузырьковой сортировки слева, Выбор рода в середине,
и что-то, как один из наших Рука поднимает ранее предложил,
объединить то справа.
Разделяй и властвуй Стратегия справа.
И это, на самом деле, то, что мы будем смотреть на среду.
Но давайте время эти баллотироваться параллельно.
Это примерно то же самое количество Элементы, все работает в то же время.
Пузырь рода против выбора Сортировать против слияния рода.
>> Теперь они все работает В теории, в то же время.
Процессор работает на с той же скоростью, но вы
может чувствовать себя, как скучно это очень быстро станет,
и только, как быстро, когда мы вводим немного неделю
алгоритмы Зеро может мы ускорить.
>> А теперь давайте сравним это в последний форме.
Я собираюсь идти вперед на сайт CS50, где
у нас есть этот заключительный ссылку на сегодня, где кто-то в Интернете
любезно воедино видео, захватывает то, что различное сортировку
алгоритмы звучать.
Это своего рода вставки.
>> [ЗВУКОВОЙ СИГНАЛ]
>> Причем вы претендуете частоту основана на высоте бар бар.
Это своего рода пузырь.
>> [Искривленных ЗВУКОВОЙ СИГНАЛ]
>> Далее идет is-- на следующей is-- выбор рода,
где снова, мы выбора следующий наименьший элемент,
и мы можем видеть, как он растет слева направо.
>> Слияние сортировать, наш победитель до сих пор сегодня.
Обратите внимание, как это деления вещи в [неразборчиво] половину и четверти.
Гном рода, которые мы не имеем говорили, и создает визуально
и audally немного различная форма и звук.
Переход вперед и назад, очистки вещи.
Кроме того, проверить пирамидальной сортировки на веб-сайте этого парня.
>> Вот и все.
Мы увидим вас в следующий раз.
>> [Свист И МУЗЫКА]