[Powered by Google Translate] [Неделя 3, продолжение]
>> [David J. Малан - Гарвардский университет]
>> [Это CS50. - CS50.TV]
>> Хорошо. Добро пожаловать обратно. Это CS50 и это в конце недели 3.
>> Так что для тех, кто незнаком, в прошлом году Гарвардский начал, что называется инновационной лаборатории,
или я-лаборатория, которая является прекрасным зданием через реку на территории кампуса в HBS
, которая открыта для студентов, GSAS, студенты со всего кампуса,
в том числе профессорско-преподавательский состав, и это место, чтобы собраться вместе, чтобы работать на инновационные вещи,
Особенно предпринимательской вещи
если вы и 0 или более друзей думаете делать что-то предпринимательских
либо во время этого класса, после этого класса, или за его пределами.
>> Таким образом, одна из вещей, которые они делают в течение срока J эти поездки,
одним из которых является Нью-Йорк, одна из которых заключается в Силиконовой долине.
Пространство очень ограничено, но это возможность пообщаться с МВА
и аспирантов по кампусу и фактически провести время в этих соответствующих областях
болтая стартапов, в чате предпринимателей и тому подобное.
Так что, если интересно, проверить этот адрес здесь.
Она также доступна на слайдах онлайн.
>> Можем ли мы смягчить дом аудио чуть-чуть?
Если вы хотите присоединиться к нам на обед в эту пятницу, в 1:15 вечера огонь и лед, пожалуйста, возглавить там.
Извинения, если форма уже заполнены раз, когда вы туда добраться.
Но мы будем продолжать эту традицию и далее.
>> Сегодня мы по-прежнему высокий уровень обсуждения различных проблем, которые мы можем решить,
фокусировки гораздо меньше, сегодня по крайней мере, на код и многое другое на идеи.
Так вспомните недели 0, когда мы разорвали телефонную книгу в два раза,
целью которой было что-то делать, правда, немного драматических
а послать такой степени, что поиск не должно быть, обязательно,
как очевидные на первый взгляд, как вы могли бы подумать.
И решение проблемы в целом не обязательно всегда быть лучшим -
Наиболее очевидное решение не обязательно может быть лучшим.
Поэтому мы вынуждены были это телефонную книгу и, честно говоря, мы все в этой комнате было инстинктов,
скорее всего, начнется в середине при поиске Майк Смит, а затем перейдите влево или вправо
основанный на любые буквы алфавита мы случайно попадают на.
>> Но это простая идея, что мы, люди, само собой разумеющимся, так долго
действительно должны начать выходят на передний план в своем уме
потому как проблем получить гораздо сложнее, чем телефонную книгу,
те же простые, блестящие идеи являются тем, что происходит, чтобы позволить нам
решать гораздо более сложные и более интересные проблемы,
Среди них некоторые вещи, которые мы считаем само собой разумеющимся, уже в эти дни.
Миллиарды веб-страниц там, и в то же Google и Bing и т.п.
в состоянии найти вещи для нас в этом роде.
Это не происходит с помощью линейного поиска, поиска по всем возможным веб-страниц.
Facebook в состоянии сказать вам, кто все ваши друзья или друзья друзей,
и, что тоже может быть сделано, казалось бы в одно мгновение в эти дни
даже если они имеют миллионы пользователей.
>> И так как мы на самом деле решать проблемы такого масштаба в конечном счете, снижению
на идеи, которые мы рассматривали в неделю 0 и немного больше сегодня.
Мы не будем повторно выполнить этот алгоритм, но помните, мы также сделали в неделю 0 это упражнение
где мы все встать, взять на себя № 1,
и тогда нам пришлось все самостоятельно, рассортированные по спариванию выключен, добавив числа вместе,
Затем половина банды сел на каждой итерации.
И мы пошли от 500 до 250 студентов в 125 и так далее.
Но, как мы сказали в понедельник, мощная идея существует
в том, что если мы удвоили размер этой проблеме
и все дети от правосудия или EC 10 вернулся в комнату и присоединился к нам,
Ну, мы могли бы рассчитывать, что вся совокупность группы
только с 1 еще большие итерации, потому что они бы, может быть, только в два раза больше
или в 10-Ec случае немного больше чем в два раза.
И поэтому мы должны были бы потратить немного больше времени,
но мы не должны были бы потратить 400 или 700 больше шагов.
>> Просто, чтобы нарисовать эту картину в способе, которым это немного менее абстрактным, давайте не будем иметь все встают.
Но если те, кто выбрал сидеть в оркестре сегодня не возражал бы стоя,
Давайте посмотрим, если мы можем выяснить, кто из вас самый высокий человек
делая такой же сравнительный алгоритм.
Так что, если вы сидите в оркестре, мои извинения, но шаг 1, встаньте;
шаг 2, на пары с кем рядом вы,
выяснить, кто выше, и сесть, если вы короче.
Затем повторите.
[Студентам ропот]
>> Хорошо.
Хорошо. Один из них остался стоять. Как тебя зовут? >> Андрей.
>> Андрей, ты самый высокий человек в разделе оркестр сегодня.
>> Поздравляю. [Аплодисменты и крики] Хорошо. Присаживайтесь. Таким образом, мы обнаружили, Андрей.
Но как долго бы он взял меня, например, найти Эндрю
В этом оркестре раздел 50 + или так люди?
Я мог бы принимать довольно простой подход и начать здесь.
А у меня 2 людей встать, и я просто сравнить их,
и тогда я говорю к тому, кто немного короче: "Хорошо, вы садитесь,"
и Я буду помнить, кто выше человек был.
Тогда я повторяю, повторяю, повторяю, и я повесить на самое высокое человек
пока я не найду кого-то немного выше, чем у них, и в этот момент
немного короче, человек должен потом сесть.
Но в этом алгоритме в этом разделе оркестр, если есть п о вас,
сколько шагов алгоритма является то, что собирается взять? >> [Студент] N.
>> Он собирается взять п, правильно, потому что в худшем случае, так сказать,
самый высокий человек самый последний человек, что я получаю только от случайных неудач.
Таким образом, в худшем случае, время работы, что алгоритм является линейным, это я,
где п-общее число людей в пространстве, размер проблемы.
Что об этом алгоритме?
Тот факт, что вы все встали и опять половина из вас сел,
половина из вас сел, половина из вас сел.
Сколько шагов следует, что взяли, если есть п вы здесь?
[Студент] N журнал п. >> Это было бы хуже. Вход с.
>> Так что войти я, даже если вы не помните точно, что логарифм,
сейчас, просто понять, что он относится к этому как-то наполовину, а наполовину, а наполовину.
Она не должна быть в 2 раза. Это может быть в 3 раза.
Но это повторение одного и того же вида, что фактор размера проблема начинается здесь
но затем сразу переходит здесь, то здесь, то тут, то здесь.
Вы не принимая маленькие кусочки из этой проблемы, вы действительно рубки далеко в этом
с большим махом каждый раз.
Поэтому мы вынуждены были 50 человек, потом 25, потом 12 ½ или 13 человек, стоя,
Затем 6 ½ и так далее, пока, наконец, просто Андрей остался стоять.
Так что мы собираемся называть это журнал п, и вы можете себе это следующим образом.
Напомним, эта картина здесь, где линейный алгоритм похож на красную линию там,
желтая линия была подсчете по алгоритму 2s, которые мы использовали для подсчета студентов
В прошлом, но сегодня Святой Грааль будет оставаться эта зеленая линия
где, если мы удвоили количество людей в оркестре раздел или только что сказал,
ад, давайте все в целую комнату встать, не такое уж большое дело
потому что мы примерно в два раза, сколько людей здесь,
Еще 1 итерации, не проблема.
>> Мы обнаружили, Андрей или тот, кто окажется выше, чем Андрей
В мезонине или на балконе.
Таким образом, эта простая идея, что мы взяли столько само собой разумеющимся в телефонной книге,
понимаю, что есть очень много различных мест, в которых мы можем применить его.
Просто, чтобы хлопнуть некоторые жаргоне - на самом деле, а не жаргон, во-первых,
отпусти меня к этой картине здесь.
Сейчас мы говорили о п и п / 2, а затем войти п,
но мы, безусловно, может придумать, как мы будем в течение семестра,
другого рода математические формулы, чтобы описать это общее понятие времени работы.
Это из контекста сейчас, потому что мы увидим в скором времени
Алгоритмы, что это на самом деле представляют.
>> Но заметьте, здесь линейной п, прямая, на самом деле очень низкой указывая прямо сейчас.
Это своего рода оптические иллюзии в том, что мы просто изменить то, что оси абсцисс
и оси у, и мы можем сделать прямо точки линию в любом направлении мы хотим.
Но причина того, что это так, казалось бы плоскую сейчас
потому, что нам нужно, чтобы освободить место на этом графике гораздо медленнее работает раза.
Сейчас, знаю, что есть некоторые довольно плохие алгоритмов в жизни,
некоторые из которых не принимают п шагов или, еще лучше, войдите п шагов, но больше.
Таким образом, выше линии п здесь внизу есть уведомление п раз журнал п,
и мы увидим, что это значит в скором времени.
Прежде, которая п квадратов, и мы ни разу не видели п квадратов алгоритмы, но мы собираемся.
И это выглядит действительно плохо.
Там в 2 к N, то экспоненциальный, который чувствует себя еще хуже.
И все же, как ни странно, то есть п кубе, который, если вы вроде Думая о будущем,
Если вы вид делают математику, от 2 до п на самом деле становится гораздо прямее,
гораздо выше, чем п кубе, если вы посмотрите на осях достаточно далеко.
Таким образом, заметил прямо сейчас эти оси произвольно от 2 до 10 на оси х.
>> А что это значит?
Это означает, что 2 человек до 10 человек в комнате.
Вот и все средства х: размер проблемы, независимо от контекста.
И вертикальной оси, сейчас это количество секунд или количество шагов -
некоторые единицу времени.
Но обратите внимание, что это от 0 до 60 и от 0 до 10.
Но если мы как-то уменьшить масштаб, как вы могли в Excel или несколько графических программ,
и идем до 200.000, обратите внимание, что нечто подобное от 2 до п
будет полностью подавить времени работы п в квадрате,
N в кубе, п § п - все, что мы говорили о до сих пор.
И все же загвоздка в том, когда вы начинаете говорить о вещах, как Facebook
где вы много, много, много людей все взаимосвязано,
Вы русские люди, каждый из которых может иметь столько, сколько друзей п
если все рода приятель в мире,
Ну, это п п раз уже, так что это п квадратов возможно дружба,
по крайней мере в 1-м направлении, п квадратов возможно дружеские отношения.
Так что уже предполагает, что поиски социальный граф Facebook, так сказать,
может начать быть выражено в этих видах формул.
>> Мы вернемся и сделать это гораздо более конкретное,
но сейчас цель на ближайшие несколько недель
будет, чтобы не идти о реализации алгоритмов или код
, что в конечном итоге принимать столько времени, сколько что-то вроде этого.
Но увлекательная вещь об информатике, если вы продолжать в этой области
принимая классы, как CS121, CS124, оба из которых теория курсов,
то, что есть на самом деле некоторые проблемы, которые существуют в этом мире
Принципиально, что, насколько мы знаем, не может быть решена быстрее
чем худшая из этих графов на самом деле предлагает.
Таким образом, есть много открытых проблем в этом мире, чтобы сделать намного лучше, чем у людей до сих пор.
>> Итак, давайте начнем тогда с этим примером.
Мы видели, Шон борьбы с этим на камеру, слишком неловко на видео.
Но на самом деле было, когда Шону было поручено найти на доске, как это число 7,
Напомню, что я сказал, что: "Существует где-то за эти бумажки или белые двери
"Номер 7. Шон, найти его для нас".
И это было удивительно неловко смотреть
потому что он действительно борется с этой проблемой.
Но реальность оказалась Шон сделал, как и любой в комнате мог бы сделать.
Он взял немного дольше, чем обычный человек может иметь,
Но он предположил, что была некоторая уловка, чтобы эту проблему,
Он предположил, что он чего-то не хватает.
И это не помогло, что сотни глаз надвигалась на него.
>> Но в действительности, если вход к этой проблеме куча случайных чисел
и вас просят, чтобы найти 1 такой номер,
Лучшее, что вы можете сделать, это линейный поиск.
Начните с левой, двигаться вправо или начать справа, двигайтесь влево.
Задним числом мы могли бы думать ", Шон, почему бы вам просто не начать с другого конца?"
Ну, 7 могли бы так же легко здесь случайно,
Но я сознательно положил его туда, потому что я полагал, что он не собирается начинать с конца.
Таким образом, я как бы манипулировал ситуацией, но по случайности 7 может быть где угодно.
Так, начиная с правого конца, возможно, были лучше, чем,
Но что, если в следующем году я перехожу 7 в другом месте?
Это не принципиально новое решение проблемы -
начиная с 1 конец или другой - когда вам дают никаких других предположений.
Так Шон начал искать по номерам, и он сказал: "5. Это не здесь".
Тогда он пошел сюда и увидел 19, то он сделал паузу в течение 20 секунд,
Затем он открыл это для 13, а затем стало очевидно,
, что, кажется, не быть образцом здесь.
Это было не 1, 2, 3, 4 или тому подобное. Были пробелы в цифры, которые не помогли.
А также тот факт, что я использовал эти дешевые бумажки, чтобы прикрыть номера
на самом деле преднамеренно, потому что если я удалил все эти бумажки,
Большинство из нас, Шон включены, вероятно, было бы посмотрела рода макроскопически
на доске и сказал: «О, 7, очевидно, прямо там." Мы сделали это мгновенно.
>> И это может быть путь человеческий мозг работает в некоторой степени,
но на самом деле, глаза или ум, вероятно, скользя числа справа налево,
Слева направо, на средней из - что-то происходит физиологически
так, что он чувствовал, что это происходит мгновенно,
но вполне вероятно, даже внутренне был своего рода методологию поиска 7.
И в самом деле, теперь, когда мы говорим о массивов и структур данных
и памяти внутри компьютера, единственное, что мы, люди, можем сделать
Достаточно посмотреть на отдельные ячейки памяти 1 за один раз.
>> Таким образом, каждый другом месте могли бы также быть покрыты с некоторыми бумаге
потому что мы не можем видеть это в любом случае. Мы можем сделать только 1 вещь за один раз.
Таким образом, в данном случае, в случае Шона, мы пошли сюда, а затем мы пошли сюда
и затем мы пошли здесь, здесь, здесь, здесь, есть умное к концу
и только отчасти пропустили эту произвольно и, найдены 7 там.
Этот не был особенным. Это тоже было не в порядке.
Но он, наконец, нашел 7.
Но сейчас еду на дом действительно является то, что лучшее, что вы можете сделать, когда не дали информации
кроме случайно отсортированный чисел начинать с левого или начать с правой стороны.
Или, черт возьми, вы можете случайно открыть двери, но даже тогда, что это значит быть случайной?
Ну, мы должны были бы как-то формализовать, что значит начать здесь,
Затем идите сюда, потом здесь. Шон сделал большой, и это было просто интересно смотреть.
Что, если вместо этого мы изменить проблема немного и воспитывать Шон этом году, если вы будете?
Кто-нибудь быть удобно придумывать на сцене и решения несколько иной задачи
и появляться на камеру?
>> Давайте выходить за рамки оркестра, потому что вы, ребята, были весьма участие уже сегодня.
Как насчет в розовом, в шляпе? Идем вниз. Как тебя зовут? >> Алекс. >> Алекс. Хорошо.
Так что Алекс будет Sean этого года и появится в ближайшие несколько лет
стоит из CS50 лекции.
Алекс, приятно встретиться с вами. >> Приятно познакомиться с вами.
Задача под рукой для вас, что у вас есть это немного легче
в том, что я говорю вам то же самое номера здесь, но теперь они сортируются.
Так что теперь ваша цель, чтобы найти номер 7.
А на самом деле, мы действительно должны сделать это - ты вид обмана, как компьютер не будет,
смотря на то, что цифры были минуту назад.
С мелом это на самом деле не собирается помогать всем, что многое,
но давайте представим, что вы не знаете, какой оригинальный массив.
Все теперь вы знаете, что у вас есть массив отсортированный номера
, которые могут иметь пробелов между ними, и вашей целью является найти номер 7.
Как бы вы, разумное человеческое существо, идти о поиске число 7?
>> Переход от низкой до высокой? >> Хорошо. Перейти низкой до высокой.
И не оторвать от них. Давайте просто поднять их, чтобы мы могли использовать их.
Итак, 1. Подождите. Прежде чем продолжать, это было 1, явно не так.
Так что же происходит в вашем уме следующий? Каким будет ваш следующий шаг?
Следующий. >> Хорошо. Следующий. Хорошо. 3, так неправильно. Каким будет ваш следующий шаг?
Продолжайте идти. >> Все правильно. Продолжайте идти. 5.
Так что продолжайте идти, и позвольте мне вручить вам это для потомков.
7. >> Отлично. Очень хорошо. Найдено номер 7. [Аплодисменты]
Так что было хорошо, но Шон тоже нашел номер 7.
И я утверждаю, что вы действительно не воспользовался этим дополнительным источником информации,
которых является то, что эти цифры сортируются.
Таким образом, мы можем сделать лучше? Любые предложения здесь? Да, в спину.
[Студент] двоичного поиска. >> Я не знаю, что бинарный поиск.
>> [Студент] Начало в середине. >> Начало в середине. Хорошо. Итак, давайте посмотрим, если мы можем туда добраться.
Так что, если вместо этого вы сказали начать с середины, идти вперед и открыть среднюю дверь.
Там в 8 из них, так что вы будете иметь, чтобы произвольно выбрать тот,
немного влево или вправо. Хорошо. 7! [Аплодисменты] Очень красиво.
Хорошо, но где же мы собираемся с этим?
Давайте предположим, что просто разорвать связь вы начали здесь
потому что в равной степени могло случиться, как хорошо.
Мы только что произошло, чтобы узнать, что 7 был там. Так что это 13.
Так что, если они сортируются и мы только начали в середине,
что было бы оптимальным следующий шаг был?
Перейти слева. И вот приходит пример телефонную книгу снова.
Если 13 является здесь и мы знаем, что список отсортирован,
Затем все эти кусочки бумаги неинтересными для нас сейчас
потому что мы уже знаем, что 7 должны быть слева
если эти цифры сортируются, и мы нашли 13.
>> Так что ваш следующий шаг здесь? >> Перейти в левой. >> Ладно, хорошо.
Так что идите к левой, и - ждать, эй, эй, эй. Это обман.
Таким образом, вы нашли 7, но то, что было алгоритму мы просто применять?
Начало в середине. >> Хорошо. Так в чем же логическое продолжение той же идеей?
О, это просто. >> Именно так. >> Так что я начинаю здесь. >> Хорошо.
Итак, теперь мы пошли немного левее снова. Это 3.
Но самое интересное вынос теперь какой из них вам не придется заботиться о?
Эти 2. Эти >> 2. Так что теперь это можно уйти, это можно уходить.
Теперь проблема, которая была 8, то был размером 4 теперь является размер 2.
Мы получаем довольно близко. Снова идем к середине этих 2-х элементов.
>> Хорошо. Так что это своего рода жаль, что теперь мы всегда будем ушел, потому что мы округления.
Но это нормально, потому что теперь мы бросаем эту сторону и все остальное, оставив нам только 7.
Давайте аплодисментами. Найдено 7 раз. [Аплодисменты] Хорошо. Конечно.
Держись всего за 1 больше секунды.
Хотя, что в следующем роде процесс занял чуть дольше, чем мы чувствовали, что это будет,
честно говоря, ваша первая инстинкты были лучше, не так ли? Найдено 7 мгновенно.
Но мы нашли бы 7 быстрее, несмотря ни на что, в этом примере по сравнению с этим
потому что если эти номера все сортируется, так же, как страницы в телефонной книге,
Вы действительно можете нарезать половина проблемы снова и снова и снова.
И это не так просто, чтобы видеть это всего 8 номеров
в отличие от 1000-страницы телефонной книги, где вы действительно видите его визуально,
но в данном случае здесь, когда Шон искал 7,
сколько шагов в худшем случае бы он взял его? >> [Студент] 7.
7 в худшем случае. Ну, в худшем случае не 7, если есть 8 дверей здесь.
Было бы взяли его 8 шагов.
>> Так что, если есть п двери, она могла бы пойти Шон пару лет назад п шагов.
Теперь, в вашем случае, Алекс, учитывая, что эти цифры сортируются -
и мы можем вида выводить это от того, где мы были до сих пор в этой истории -
что время работы более интеллектуальный алгоритм Алекса
из начиная с середины, а затем повторить?
[Студент] 3. >> Так это будет 3, грубо говоря, если вы идете с 8 до 4 до 2 к 1.
Таким образом, 3 шага или, более общо, это журнал N раз.
Каждый раз, когда вы наполовину, а наполовину, а наполовину, а наполовину,
это выражение эта идея журнала с.
И так, что бы вас взял всего 3 шага, и это действительно так сделали
После того как мы открыли двери вдвое и вдвое,
в то время как это заняло бы Шон около 7 или 8 шагов.
Так что спасибо вам за то, что с нами в этом году. >> Спасибо. Приятно было познакомиться.
Спасибо Алексу. >> Аналогично. [Аплодисменты]
>> Что то реальные последствия этого?
Теперь представьте, что это не 8 дверей, которые, откровенно говоря, все мы могли бы найти что-то
за 8 дверей довольно быстро, просто рвет листы бумаги и происходит с нашими инстинктами.
Но что, если это миллион дверей? Что, если это 4 миллиарда двери?
В случае 4 млрд. двери, вы действительно собираетесь хотите, чтобы пойти с алгоритмом Алекса,
бинарный поиск, как мы начнем, назвав его или разделяй и властвуй, более общо,
где вы храните вдвое и вдвое проблемы,
потому что, если у вас есть 4 миллиарда двери, сколько раз вы можете нарезать 4 млрд в половину?
[Студент] 32. >> Это на самом деле 32. Вы можете работать это на бумаге или в голове.
Вы идете 4 млрд до 2 млрд до 1 млрд до половины миллиарда до 250 миллионов, точка, точка, точка.
И если вы делаете из математики, вы собираетесь получить действительно 32,
и что на самом деле относится к информатике, потому что мы обычно рассчитывать по степеням 2.
От 2 до 32, случается, 4 миллиарда долларов.
Таким образом, есть много, имеющие отношение к такого рода полномочия 2 в компьютерные науки.
>> Но то, что около 8 миллиардов? Сколько шагов является то, что собирается предпринять, если есть 8 миллиардов двери?
[Студент] 33. >> Так 33. Что делать, если есть 16 миллиардов двери? Сколько шагов является то, что собираетесь предпринять?
[Студент] 34. >> 34. Мы могли бы видом продолжать это до бесконечности. Но это сильная вещь.
Вы можете ввести миллиардов больше входов к вашей проблеме, но ничего страшного,
Вы просто взять 1 дополнительный кусок из нее и таким образом дает нам что-то вроде бинарного поиска
или разделяй и властвуй, в целом.
Но я немного обманывает, да?
В случае алгоритм Алекса, она имела преимущество над Шоном.
Она знала, что эти цифры были отсортированы, но Алекс не должны сортировать их сама.
Я заранее подошел к доске и сделал вид, что
что я обратил их всех в определенном порядке, то я покрыл их бумаги.
Но сколько же работы, что меня принимаете?
Если бы мы начали с этих цифр в некоторых, казалось бы случайном порядке -
В этом случае эти простые цифры, от 1 до 8 здесь -
как же нам идти о сортировке этих ценностей?
Если бы вы были человеческие данного эту задачу, какую интуитивный подход вы бы взяли
для сортировки целую кучу цифр?
Эти вещи были разложены, как кусочки головоломки. Да.
>> [Студент] Я бы каждый номер и сравнить его с каждой
и продолжайте идти налево. >> Ладно, хорошо.
Так что берите каждый номер, сравнить его с тем, рядом с ним,
а потом просто продолжать двигаться по списку, вроде rejiggering вещи, как вы идете.
Итак, у нас есть шанс, может быть, еще несколько людей, чтобы вмешиваться.
Есть ли у нас еще 8 добровольцев, которые хотели бы прийти?
Чуть меньше давления, так как вы не единственный. 1, 2, 3, 4, 5, 6, 7, 8.
Идем вниз. Вы, ребята, собираетесь быть цифры от 1 до 8.
Давайте посмотрим, если мы не можем это сделать сортировку для Алекса во многом так же, как я сделал это заранее.
1, 2, 3, 4.
Идите вперед и, если бы Вы, выстраиваются на сцене между пюпитр и меня здесь
в том же порядке, что и слайдов на экране.
Ой-ой.
Мы будем работать вас в следующем примере. Ой, подождите, подождите. Здесь мы идем. Подождите.
В следующем примере в настоящее время. Здесь вы идете. Номер 8. Поднимайся.
Хорошо. Сортировать сами в соответствии с этим.
Слайд только немного в стороне от музыки стоять здесь.
Итак, мы имеем 4, 2, 6 - попасть туда, сюда, прямо там - 3.
Да. Хорошо. Вы идете сюда. Нет, вы остаетесь там.
Да, прямо здесь. Нет, я неправильно. Прямо там. Хорошо, очень хорошо. Хорошо.
А теперь давайте отсортировать их в порядке возрастания.
>> Как я могу идти об этом?
Алгоритм, который был предложен еще минуту назад было, почему бы нам просто не сравнить
люди, которые являются своего рода рядом друг с другом, а затем исправить любые ошибки,
двигаясь слева направо.
Таким образом, здесь мы имеем 4 и 2, очевидно, вышел из строя. Давайте обмениваться вас. Хорошо.
Так что теперь я собираюсь двигаться вниз линию. 4 и 6, нет. [Смех]
6 и 8, довольно хорошо. 8 и 1, позвольте мне поменять вас, ребята. Хорошо.
Таким образом, 8 и 3, обменять вас, ребята.
8 и 7, позвольте мне поменять вас, ребята. 5 и 8, отлично.
Я даю вам отсортированный список.
Хорошо. Таким образом, не совсем.
Но это лучше, потому что большие числа - случай в пункте 8 -
были вид пропускали по сравнению с левого на правый.
Так что я получил 1 из них прав, но он чувствует, как это не вполне решить эту проблему.
>> Так что же вы предлагаете нам делать дальше? >> [Студент] Продолжайте делать это. >> Мы продолжаем это делать.
И понимаю, мы снова установить вещи простым, имеющие все люди
рода разумно организовать себя на основе этой картины,
но теперь мы должны быть гораздо более методично.
Мы должны быть алгоритмическим об этом, как будто мы пишем код -
В этом случае словесного псевдокод.
Итак, позвольте мне просто попробовать еще раз. Это работало очень хорошо. Он не решить.
Но когда он сомневается, просто попробуйте и попробуйте снова. Таким образом, 2 и 4, не помогло больше.
4 и 6. Ах! 6 и 1, немного лучше.
6 и 3, хорошо. 6 и 7, 7 и 5, 7 и 8, хорошо.
И вы знаете, я, вероятно, может игнорировать 8 сейчас, потому что он в конце списка.
Может быть, нам не придется беспокоиться о ком-то, проходя мимо него.
Но давайте посмотрим, если это безопасное предположение.
Сейчас в списке - черт - не сортируются. Давайте попробуем это снова.
Таким образом, 2 и 4, 4 и 1, 4 и 3.
4 и 6, хорошо. 6 и 5, хорошо.
6, 7, и 8, хорошо. Но заметьте, я могу просто остановиться здесь, сейчас и остановимся здесь сейчас?
[Студент] Да. >> Да?
Что делать, если один из вас был номер 9 на всем пути там?
Это было бы отсортировать. >> Хорошо. Было бы были отсортированы в первый раз.
Хорошо. Так что давайте вернемся снова. Мы почти на месте.
1 и 2, 2 и 3, 3 и 4, 4 и 5, 5 и 6, 6 и 7, 7 и 8.
>> Я сделал сейчас, но, опять же, я компьютер, который может делать только то, что я сказал, чтобы сделать,
и мое единственное воспоминание сейчас, что я на самом деле просто сделал немного работы.
Что-то изменилось здесь.
Так что я технически не подтверждено визуально или алгоритмически, что этот список действительно отсортированы.
Так что для хорошей мерой, просто чтобы быть анальный об этом, давайте сделаем это еще 1 раз.
Таким образом, 1 и 2, 2 и 3, 3 и 4. И вы знаете что?
Просто для хорошей мерой, я буду следить на моей руке этот раз
сколько свопов я делаю просто так, что я знаю, как много работы я на самом деле сделал.
3 и 4, 4 и 5, 5 и 6, 6 и 7, 7 и 8. Нет свопов.
Так что теперь я бы законно быть идиотом, чтобы сделать это снова
потому что если я не работал через этот проход людей,
то, очевидно, что это произойдет снова, если ни один из них является своего рода случайным
adversarially движущихся вокруг себя. Так что теперь я могу остановиться.
Теперь давайте зададимся вопросом, сколько работы было это на самом деле взять меня?
Сколько шагов сделал, что взять? >> N в квадрате.
Да, так п в квадрате. Где вы получаете п квадрат от?
Вы должны проверить каждое число -
Существует п чисел, и вы должны проверить каждый номер с другими числами п.
Хорошо. >> Так что это п квадрат. >> Хорошо.
>> Таким образом, он чувствует, как она вполне может быть п квадрат, верно?
Там это п из этих парней, 8 конкретно в данном случае,
но каждый раз, когда я прошел через этот список я сравнивал первые лица, в отношении второго,
второго к третьему снова и снова, и снова,
и когда я добрался до конца, что же мне делать? Я переделал его.
Таким образом, если мы обобщим это объяснение, мы русские люди
и я делаю, очевидно, 8 шагов, п шагов, каждый раз, когда я иду по этому алгоритму.
Но сколько раз в худшем случае мне придется пройти через это список людей?
[Студент] N раз. >> Наверное, я, право, потому что в худшем случае,
, что, вероятно, в худшем случае расположения этих парней с самого начала идти?
Если они совершенно обратном порядке
потому что только предположить, мысленно, let's - Как тебя зовут? >> Боуэн.
Боуэн. Хорошо. Так Боуэн, иди сюда на минутку.
>> Предположим, что Боуэн был здесь в начале алгоритма,
и мы не знаем, что все остальные, но Боуэн здесь, в соответствии с этим алгоритмом -
и если вы хотите просто прогуляться со мной - будет пузыриться, как он это делал в первый раз,
весь путь до конца.
Но предположим, что человек рядом с Bowen был номер 7.
Я должен вернуться и получить номер 7, который означает, что я должен пройти весь путь сюда.
Теперь я должен иметь тот же прогулка с человеком, который является номером 7.
Но что, если затем номер 6 был рядом с ним, а?
Тогда я должен вернуться назад и получить 6.
Итак, еще раз, на каждой итерации этого цикла я обращаюсь к каждому из русского народа,
и я мог бы сделать п из этих прогулок, чтобы убедиться, что я потянув
Все из крупнейших элементов назад и назад и обратно в самом конце списка.
Таким образом, N Things п раз просто п раз п или п квадрат.
>> И вот уже у нас есть алгоритм, который уже не я, это не журнал п,
это на самом деле хуже, чем все, что мы делали раньше.
Так Алекс вида повезло в том, что я сделал всю работу по-видимому фронт для нее,
Все дорогие работы, так что она могла наслаждаться в этом алгоритм двоичного поиска,
который журнал с.
Но это согласуется с темой понедельник.
Мы дали немного больше пространства, мы использовали больше битов для того, чтобы ускорить наше время работы.
Так много, что есть это компромисс между временем и пространством,
там также может быть просто компромисс между времени впереди рода получении вещей готовы пойти
и фактического выполнения алгоритма как поиск. Давайте попробуем еще один.
Если вы, ребята, не возражал бы просто быстро переставляя себя, чтобы соответствовать это снова,
Давайте попробуем что-то немного отличается, где это не так просто,
как только исправить все ошибки попарно, что это очень интуитивно.
Давайте вместо этого быть немного более тщательно и сделать это.
Это один тоже я хотел бы предложить, вероятно, довольно интуитивно.
>> Давайте выберем наименьшее человека из списка снова и снова. Таким образом, здесь мы идем.
4, вы наименьшее человек, которого я так видел до сих пор,
так что я мысленно помнить, что, просто указывая на вас на данный момент.
2. Ох! Забудьте про номер 4. Я только что нашел новый наименьший элемент в этом списке.
Я собираюсь вид помнить об этом. 6, 8.
Ох! 1. До свидания. Так что теперь я буду помнить номер 1.
Мы знаем, что 1 является наименьшим, но я компьютер. Что делать, если есть 0?
Что делать, если есть -1? Я должен продолжать идти.
Таким образом, 3, 7, 5, нет. Хорошо. Так номером 1 был самым маленьким.
Позвольте мне вам выбрать из списка - МЫ идти по этому пути -
и поставить вас произвольно в начале списка.
Сейчас, подожди минутку. Я как бы обманутыми.
Если эти ребята представляют собой не список из 8 человек, но массиве,
8 кусков непрерывной памяти - вы не возражаете, отступив всего на данный момент?
Там на самом деле нет места для тебя прямо здесь.
Так как же нам освободить место для - как тебя зовут? >> Сэмми. >> Сэмми.
Как мы можем сделать пространство для Сэмми?
>> Мы движемся п, которые до меня. >> Хорошо.
Таким образом, мы могли двигаться русского народа, которые перед ним,
так что если вы, ребята, хотите принимать по 1 преднамеренным, драматический шаг влево.
Они все сделали это в унисон, но последний раз я написал код,
Вы не можете сортировать, перемещать много вещей сразу.
Мы можем сделать это в цикле, движущихся каждый раз в то время.
Так что, если вы, ребята, не возражал бы отступая вправо,
и Сэмми, если бы вы могли сделать шаг назад, потому что до сих пор нет места для тебя,
Теперь давайте сделаем это. Где был Сэмми минуту назад? Прямо там.
Так что разрыв есть. Таким образом, можно двигаться в месте Сэмми.
Теперь следующий человек, и теперь следующий человек, в настоящее время следующего человека. Теперь у нас есть место для Сэмми.
Теперь, кто-то из зала, - что было хорошо, что было правильно,
он чувствовал себя немного времени - что быстрее? Да.
[Студент] Новый массив? >> Что это такое? >> [Студент] Новый массив? >> Ладно, хорошо.
>> Таким образом, в соответствии с этой темой просто компромисс, то почему бы мне не сделать новый массив
, а затем Сэмми будут плавать в пространстве перед этими людьми, например,
и мы можем только начать заполнение нового массива в целом. Это тоже будет работать.
Но я не заинтересован в тратить больше пространства сегодня. Что другой подход?
[Студент] Swap. >> Хорошо. Мы могли бы просто поменять эти 2 парня. Как тебя зовут?
Марио. >> Марио. Таким образом, Марио, вы в настоящее время здесь.
Сэмми, вы можете создать резервную копию на мгновение? Марио был здесь.
У нас нет места для тебя больше, так что если вы не возражаете, где собираются Сэмми,
мы поставим Sammy здесь, и теперь я бы утверждать, что замена операции Сэмми был намного быстрее.
Мы сделали 1 операцию, чтобы поменять эти парни, или, может быть от 2 до обменять эти ребята,
но мы не делаем 1, 2, 3, 4, так что чувствует себя лучше. Сейчас, подожди минутку.
Я как бы сделал эту проблему еще хуже, потому что номер 4 был отчасти близко к началу.
Сейчас число 4 является чуть ближе к этой цели, но я действительно не знал, или заботятся об этом.
Так что это просто невезение, что число 4 является чуть дальше от своего предназначенного места.
Итак, давайте повторять этот алгоритм.
>> Напомним, что до тех пор, как эта история была, все, что мы делали, было пройтись по списку
ищет наименьший номером человек.
Итак, теперь давайте сделаем это снова. Мы не должны беспокоиться о Сэмми больше.
Мы можем просто пойти сюда. Ох! Номер 2. Это довольно малое число.
6, 8, 4, 3, 7, 5. Ладно, хорошо.
И к счастью, по стечению обстоятельств, у меня нет для перемещения - >> Вилли.
Вилли, потому что он в свое правильное место сейчас.
Давайте сделаем это снова и игнорировать эти 2 парня.
6. Это довольно малое число. Ох! 8, безусловно, больше.
4. Давайте сосредоточимся на 4. Ох! 3 еще лучше.
7 и 5. Итак, что же нам теперь делать с - >> Роджер. >> Роджер?
Давайте обменять его с номером 6.
Так что если 6 и 3 хотелось бы поменять,
Мы сейчас вид получил повезло в том, что 6 ближе туда, где она должна быть,
но это просто совпадение здесь. Итак, давайте теперь иди сюда.
8 представляет собой довольно малое число. Ох! 4 является меньшим.
6, 7, 5. Что мы сейчас делаем? >> Swap. >> Именно так.
Итак, давайте делать такого рода быстрее.
8, 6, 7, 5. Где 5 перейти? Хорошо. Хорошо.
6, 7, 8. 6 получает оставаться там, где она есть. Как тебя зовут? >> Розали.
Розали получает оставаться там, где она есть. 7 получает до - Давайте посмотрим. 7, 8. Хорошо.
Таким образом, 7 получает оставаться там, где она есть. Как тебя зовут? >> Amna. >> Amna.
>> Так Amna получает оставаться там, где она есть, и № 8 уже, где он сейчас и должно быть.
Ладно, хорошо. По ощущениям, мы просто создаем для себя работу здесь, однако.
Что в конечном счете, время работы этого алгоритма?
Если мы думаем об этих людях не как 8, но как п? >> Это с.
Это п шагов, но мы проверяем каждый раз.
Хорошо. N, но вы проверяете каждый раз?
Хорошо, но если он п шагов, не должен я был в состоянии разобраться вам просто будет 1, 2, 3, 4?
О! Хорошо, что есть большая разница.
Таким образом, п квадрат почему? Что на самом деле происходит?
Там в русском народе в этот список, но найти наименьшее лица в список
В худшем случае, сколько шагов я должен взять? Н. >>
>> N, правильно, потому что в худшем случае, номер 1 все пути туда,
так что я должен пойти получить его или ее.
А потом, когда я, наконец, понимаю, 1 был маленьким, то это довольно быстро, чтобы поменять их местами.
Но сейчас я должен начать с самого начала и искать кто?
Следующее наименьшее человек, что на 2. Где в худшем случае составляет 2?
О, мой Бог. Это все пути сюда в конце.
Так что теперь я только что сделал другой п шагов, другой п шагов.
И если у нас есть русские люди и в худшем случае наименьшее человек п шагов,
вот опять п п раз, и поэтому мы вновь п квадрат.
Это не чувствовал себя так хорошо.
И в самом деле, даже в лучшем случае - предполагать, что они начинают отсортированный -
сколько шагов требуется для меня с помощью этого алгоритма для сортировки этих русских людей?
N в квадрате. >> Я слышал п квадрат. Почему п квадрат?
Потому что вы все равно должны проверить каждый раз. >> Да.
И вы должны поменять их местами. >> Хотя мы, люди, вид всеведущего
в том смысле, визуально, что мы можем только отчасти видеть, что это сортируется,
Компьютер не то, что умный.
Это будет посмотреть здесь и здесь и здесь,
но если то, что он ищет это наименьший элемент,
Вы только знаете, что вы нашли наименьший элемент на какой момент? Как только вы в конце.
Но в этот момент вы только нашли в настоящее время наименьший элемент.
Вам не обязательно знать ничего о состоянии мира.
Таким образом, вы должны пойти снова и снова, и снова.
>> Поэтому на этот раз я действительно выглядят немыми, потому что я проверяю, ладно, 2, ты маленький,
Но я не знаю, что в общем пока нет.
3, 4, 5, 6, 7, 8. Ладно, хорошо. 2 был действительно самым маленьким.
Теперь давайте найдем следующий по величине. Хорошо.
3, вы в настоящее время самым маленьким. Давайте посмотрим. 4, 5, 6, 7, 8. Ладно, опять повезло.
3 был действительно в нужном месте. Но я собираюсь продолжать делать это снова и снова и снова.
Как мы можем сделать чуть-чуть лучше?
Вместо того, чтобы люди пузырь попарно от наименьшего к наибольшему
и вместо того, чтобы идти вперед и назад по списку выбора, то наименьшее человек,
Почему бы нам не вставить вместо этих людей в список новый шаг за шагом?
Давайте попробуем это. Теперь позвольте мне называть такого рода вещи вставки.
И вот мы здесь. Номер 1. Я не забочусь ни о ком другом в этом списке.
Моя цель сейчас это поставить номер 1 в начале отсортированного списка.
И я собираюсь предложить, так как я только 8 участков памяти,
произвольно сейчас я стену между моей якобы несортированный список,
и тех, кто находится позади меня, я буду утверждать, сортируется.
Так что теперь у нас есть номер 1.
Я хочу, чтобы вставить его в свой отсортированный список, так что я просто хочу, чтобы двигать стены здесь,
и теперь я утверждаю, этот список отсортирован, этот список несортированные - по крайней мере, насколько я знаю.
Я не могу видеть все номера сразу.
>> Теперь я, случается, сталкиваются с номером 2. Что мне делать с ним?
Я вставляю Вы сейчас в отсортированном списке. Но обратите внимание, как легко это было.
Мне просто нужно смотреть. Номер 1 есть. О, очевидно, 2 идет в сторону номер 1.
И что теперь мне делать с 3? Я вставляю Вас в упорядоченный список. Но это было просто супер.
Это супер просто, это просто супер, это просто супер, супер просто, супер просто.
А теперь все отсортировано позади меня, и сколько шагов было, что взять?
[Студентов] Н. >> Так это только п. Нам повезло.
Это было только п почему? >> [Студент] Поскольку список был отсортирован.
Список уже отсортирован. Так что нам повезло.
Но мы разработали алгоритм этого времени, которая использует такую ​​удачу,
что лучшем случае,, не теряя лишнее время.
Таким образом, мы теперь имеем то, что мы называем пузырь виды
где люди вроде пузырь попарно.
Теперь у нас есть выбор рода, где мы вырвать наименьшее человек снова и снова.
И теперь у нас есть сортировка вставкой, где мы вроде как активно ставить людей, где они принадлежат
В более упорядоченный список.
Если бы мы могли, аплодисменты для этих парней здесь. [Аплодисменты]
Давайте возьмем наш 5-минутный перерыв здесь.
А когда мы вернемся, мы будем взрывать все эти алгоритмы из воды
с чем-то лучше. Хорошо. Большое спасибо. Вы можете держать их в качестве сувениров.
Хорошо. Мы вернулись.
>> И чтобы резюмировать очень быстро, у нас были эти 3 различных подходов к сортировке,
Весь смысл которой было добраться до точки, где кто-то, как Алекс
может искать список номеров быстрее, чем кто-то, как Шон мог.
И хотя у нас есть такие простые примеры с 8 числа,
Вы можете легко экстраполировать до 8 веб-страниц, 8 миллиардов веб-страниц,
или 800 миллионов друзей на Facebook.
Таким образом, эти алгоритмы, безусловно, может масштабироваться до тех видах ценностей,
и идеи в конечном счете то же самое.
Так пузырьковой сортировки была первой, где мы вроде пропускают самую большую человек
все до упора вправо, меняя людей попарно.
Тогда мы имели то, что мы называем выбора рода, где я немного более сознательно
смотрел по списку, выбрав наименьшее число снова и снова и снова,
Логическим результатом которого является то, что список, в конечном счете отсортированы.
Тогда в третьем, я вставил людей в соответствующее место,
и мы сделали очень надуманный пример в том, что список уже отсортирован,
но это было отправить сообщение, что в случае сортировки вставкой, в
Вы можете получить повезло.
Если число уже отсортированы, он будет только у вас п шагов, чтобы подтвердить столько же,
в то время как выбор рода вы немного более туннельное зрение
и вы никогда не понимаете, что список уже отсортирован.
Итак, давайте посмотрим пузырьковой сортировки в действии здесь.
В следующем примере, мы собираемся, чтобы увидеть вертикальные полосы
, высота которых представляют числа, так что мы можем сортировать визуализировать сортировка происходит.
Чем меньше бара, чем меньше число, тем больше бара, тем больше число.
>> И мы будем играть на этой скорости по умолчанию.
Это будет двигаться слишком быстро сейчас, но красные это то, что показывает 2 бара
сравниваются бок о бок.
И если вы посмотрите внимательно, что происходит, что если бара вышли из строя,
меньшего перемещен влево, больший вправо,
а затем вы продолжаете двигаться вперед.
Так что, если мы будем делать это снова и снова, заметил, что наименьшее баров
собираетесь держать толчковой пути к левой
и крупнейшего бара собираются держать толчковой их до упора вправо.
И действительно, мы начинаем видеть картину полностью на правой стороне
так же, как мы видели, 8 и затем 7 в конечном итоге бьет ключом к дальнему концу нашей человеческой списка.
Так что это будет очень быстро получить немного утомительно, поэтому позвольте мне остановиться на мгновение.
Позвольте мне изменить скорость будет намного быстрее.
Я не изменяя алгоритм, я просто сделать анимацию произойдет быстрее.
Тем не менее пузырьковой сортировки, тот же алгоритм,
но теперь вы можете видеть гораздо быстрее, чем наша словесная демонстрация
что самая большая элементы действительно бьет ключом к вершине.
>> Как и в сторону, эти маленькие квадраты в нижней левой и нижней правой
просто маленькие напоминания о том, как много сравнений вы делаете.
Но сейчас, мы можем сосредоточиться на пирамиду которая складывается, и там она идет.
Наименьший элемент находится на левом, самый большой на правой, а все остальное между ними.
Теперь давайте вместо этого взглянем на выбор рода.
Я собираюсь идти вперед и ударил Stop. Мы собираемся, чтобы получить новый случайный набор баров.
Выбор рода, напомним, проходит через список снова и снова, и снова,
выщипывание наименьший элемент. Так вот выбор рода.
Похоже, там меньше работы происходит сейчас, потому что мы не сравниваем попарно
но мы только вид cherry выбора наименьшего элемента справа налево.
Это заняло очень мало времени, так что дихотомия уже.
Просто потому, что алгоритм сказали взять п квадратов время, как пузырьковой сортировки
и, как выбор рода, те действительно худшем случае работает раза.
Например, в случае, скажем, выбор сортировки,
Я на самом деле имею в выборе наименьшего человека и положить его или ее здесь,
Затем я делаю это снова, то я делаю это снова,
но там была небольшая оптимизация я мог бы сделать.
>> Как только я переехал номер 1 здесь - Сэмми в этом случае -
Что же я должен делать с ним после этого? >> [Студент] Оставь его.
Оставь его, не так ли? Ничего.
Мне не нужно, чтобы когда-либо поговорить с Сэмми снова, потому что, если бы я выбрал наименьший элемент
и положил его здесь, зачем тратить время собирается до конца моих весь список?
На следующей итерации позвольте мне на самом деле двигаться только на номер 2, только номер 3.
Таким образом, в действительности, я не делаю вещей п п раз.
Я делал вещи п, то п - 1 вещи, то п - 2 вещи, то п - 3 вещи,
то п - 4, точка, точка, точка.
У нас есть немного геометрической прогрессии, которая просто означает, что
Вы добавляете вверх постепенно меньших количествах.
Не N + N + N + N, а N + 7 + 6 + 5 + 4 + 3 + 2 + 1.
И что это вообще работает, чтобы быть -
Я собираюсь испортить мой совет здесь на мгновение -
, что будет работать, чтобы быть чем-то вроде п (п - 1) / 2
если мы просто вид взгляда на задней математике книгу, где у вас есть все шпаргалок
для формул.
Если вы только добавить что-то N + N - 1 + п - 2, то выходит, должно быть что-то вроде этого.
И если мы просто какая-то умножить на это, это п квадрате минус п / 2.
Я все время говорил п квадратов, хотя, и это потому, что я был отчасти с психическими контекстном
потому что в действительности, п квадрате минус п делится на 2, действительно, истинное число шагов
что алгоритм выбора рода, как бы, если мы действительно подсчитали
все эти сравнения и все немного занят работой мы делаем.
Но, честно говоря, как только п добирается, чтобы быть как миллион или миллиард, кто, черт возьми заботится
если вы делаете млрд. квадрате минус миллиард разделить на 2?
Млрд. квадратов огромное количество.
Вы можете взять еще один миллиард покинуть его с - п. Это не такое уж большое дело.
Таким образом, чем больше номер, тем меньше важны эти нижние упорядоченной термины.
Какая разница, если вы разделите на 2, если вы говорите о квадриллионы число шагов?
>> Так что в целом, компьютерные ученые, как правило, выбрасывают все, но самый большой срок,
и мы только отчасти упростить мир и сказать, что алгоритм
потребовалось около п квадрат шаги. Это время работы алгоритма.
Таким образом, мы вернемся к этому через минуту с некоторыми конкретными примерами,
но сейчас, это своего рода интуитивное мотивация просто упрощение нашего мира
и говорить о наиболее важных терминов, а не получать во все эти фантазии формул.
Так, чтобы был выбор рода, и мы получили немного повезло.
Давайте посмотрим на сортировку вставками. Позвольте мне пойти дальше и начать это одно, а.
Теперь обратите внимание, что картины происходит немного иначе,
и мы начали с случайных чисел,
Но если мы на самом деле подсчитать количество шагов в худшем случае,
Если в списке начал полностью в правильном порядке,
мы только взять п шагов по реализации так много.
>> Но если этот список были на самом деле в обратном направлении - например, в данном случае здесь -
то заметите, что мы на самом деле нужно сделать еще очень много работы в этом случае.
И это должно отчасти чувствую к тебе, как это один вид работать труднее
чтобы получить эти мелкие элементы слева, и это потому, что мы не повезло.
В списке были отсортированы случайно в обратном направлении.
С другой стороны, со вставкой рода, если мы имитировать то, что мы сделали с нашим людям здесь
, начиная с каждого сортируются, а затем начать, это довольно хороший алгоритм, правильно?
Это уже, по сути, сортируются.
Итак, давайте попробуем обобщить точно, сколько времени эти вещи с нами
путем введения только немного жаргона или обозначения, которые на самом деле гораздо проще,
по сравнению с крутостью рода предложения.
Эта вещь здесь, это большая вывода на экран, это то, что ученый обычно используют
Для описания худшем случае время выполнения алгоритма.
>> Опять же, по худшем случае, это полностью зависит от контекста.
Что мы подразумеваем под худшем случае полностью меняется в зависимости от проблемы, которую мы сейчас говорим.
Но в случае сортировки, что самое худшее из возможных сценариев?
Все назад, потому что он просто чувствует, что это означает, что много работы для нас.
Я набросал несколько алгоритмов, которые мы видели до сих пор:
линейный поиск, бинарный поиск, как с телефонной книгой или кусочки бумаги,
Затем пузырьковой сортировки, отбора сортировки и сортировки вставкой, как мы видели, с нашими людьми,
, а затем 1 друга, что в конечном счете будет называться сортировки слиянием.
Таким образом, в линейный поиск в худшем случае, сколько шагов нужно для того, чтобы найти номер 7
если есть п двери, как Шон лицом? >> [Студент] N.
N. Таким образом, мы собираемся написать большую O н.
Я просто хочу, чтобы заполнить некоторые пробелы. Это просто сетку пробелы.
Но в лучшем случае с линейным поиском, 7, возможно, был в самом начале списка,
Шон и, возможно, начали искать в начале списка.
Так что, если вы используете линейный поиск и просто проверка слева направо или, может быть, справа налево -
они эквивалентны - в лучшем случае, сколько шагов может линейного поиска,
Алгоритм, как Шон, возьми? Всего в 1 шаг.
>> Так что я собираюсь сказать, что это омега обозначений.
Это просто столица омега.
Omega просто сексуальный способ сказать лучшем случае время работы.
Таким образом, в лучшем случае время выполнения одного шага или постоянное число шагов -
1 в этом случае - но в худшем случае, большие О, это на самом деле п шагов.
И это здесь, тета, на самом деле мы не будем смотреть на прямо сейчас.
Это не относится к данному конкретном примере.
А теперь давайте попробуем бинарный поиск.
В худшем случае с бинарный поиск, сколько шагов он собирается предпринять, чтобы найти номер 7
или что мы ищем? >> [Студент] Вход с.
Тем не менее собираюсь взять журнал п, так как Алекс не повезло
Когда мы действительно работали по проблеме методично
и она не нашла номер 7 до самой последней двери, она посмотрела на,
хотя, справедливости ради, она получила выбрасывать определенные двери по пути,
бинарный поиск в худшем случае имеет время работы § п.
И снова, что говорит на этот деления и завоевания.
Но что в лучшем случае?
А Алекс на самом деле испытали, что лучшем случае правы, когда она вышла на сцену.
Сколько шагов сделал, что взять в бинарный поиск? >> [Студент] 1.
1, только потому, что повезло.
Но это нормально, потому что омега относится к лучшим сценариям,
лучшем случае входов, даже если это всего лишь случайное удача.
>> Теперь, это тоже мы собираемся просто какая-то отпуск пустой на данный момент.
Как насчет сейчас пузырьковой сортировки?
В худшем случае с пузырьковой сортировки, все в обратном порядке,
так что мы должны сделать много пузырьков.
Но сколько шагов является то, что собирается взять в худшем случае? >> [Студент] N в квадрате.
Это был указан в квадрате, потому что если вы думаете об этом,
если список полностью назад - 8, сюда, 1, здесь -
как вещи начинают пузыриться, номер 8 будет двигаться таким образом, таким образом,
Таким образом, этот способ, но где число 7 в худшем случае?
Здесь она все еще там. Таким образом, мы должны делать это снова и снова.
И вот, когда мы получаем п шагов, то п - 1 шагов, то п - 2 шага.
И если вы верьте мне на слово, - что если вы вид умножить его,
Это примерно п квадрат в конце концов с некоторыми другими условиями, которые мы будем просто игнорировать сейчас -
Затем в худшем пузырьковой сортировки случае п в квадрате, плюс-минус.
Но как насчет лучшем случае с пузырем рода?
Что является лучшим сценарием? Все номера сортируются уже.
И то, что было эвристический я использовал, уловка, которую я использовал,
чтобы понять, что я не сделал работу и поэтому может остановить рано?
[Студент] Проверьте это раз. >> Проверьте это раз. Но то, что я делаю на этом пути?
Я был отслеживать, сколько свопа я сделал.
И я понял, если бы я не считал любую свопы на пальцах, то я не сделал работу.
Я, конечно, не следует пытаться делать никакой работы снова, так что я могу просто остановиться.
>> Таким образом, в лучшем случае пузырьковой сортировки, когда список уже отсортирован,
что бы вы сказали обозначения омега есть, в лучшем случае время работы?
Это просто п. Мы должны сделать некоторую работу, но мы только должны сделать стоит 1 прогулка на работу.
И здесь я собираюсь оставить эту часть пустым.
И теперь выбор рода.
Выбор подобного не мне, выщипывание наименьшее человек снова и снова.
И что же мы говорим, что время работы, что было?
Это был п квадрат в худшем случае.
И, к сожалению, в лучшем случае он также п квадрат
потому что у меня нет такого рода всезнающий вид на весь мир;
Я знаю только после полной итерации, что я действительно нашел наименьшую человек.
Таким образом, выбор рода вид сосет в том смысле,
но Достоинством является то, что это отчасти интуитивно.
Это довольно легко закодировать, потому что все, что вам нужно сделать, это написать несколько вложенных циклов,
Обычно, которая проходит через ищем наименьший элемент
а затем помещает наименьший элемент, где он находится в конце списка.
Так что здесь тоже есть это будет компромисс.
Количество времени, которое требуется, чтобы вы думали, и на самом деле что-то разрабатывать путем написания кода
вполне может занять больше времени, если вы хотите лучше алгоритма и повышения производительности.
>> Но если вы действительно только отчасти код что-то быстро и грязно
и только отчасти взять на себя глупой идеей возможной Вы можете думать,
, которые могут у вас несколько минут, чтобы код, но с большими наборами данных
ваш алгоритм может занять несколько часов, чтобы бежать.
И даже я в аспирантуре иногда сделать эти компромиссы.
Было бы 3 часа ночи, я пытался проанализировать некоторые очень больших наборов данных
связанных с безопасностью исследований я делаю, и это было либо потратить 5 минут
настройки моей программы для анализа данных и пойти спать
или провести 8 часов получить его правой так, он работает сразу, а не спать.
И так там тоже своего рода сознательное решение.
Менее время разработки, больше спать.
Оглядываясь назад, я, вероятно, не следует поощрять, что
когда цель здесь заключается в оптимизации качества кода,
но это тоже в реальном мире это очень разумный компромисс.
Меньше времени, меньше производительность, или наоборот.
Так вот мы, наконец, получили возможность говорить о тета.
Theta обозначения чего-то компьютере ученые могут поднять в разговоре
При большом O и омега случится то же самое.
Вы говорите, что тета, чтобы действительно отправить сообщение, что это вид плотно связаны.
Независимо от того, является ли сценарий, хорошо это или плохо, это п квадрат.
Так что это просто не имеет значения в этих историях здесь.
Вставка рода является последним мы смотрели на,
где я был просто вставляете всех в нужное место.
В лучшем случае то, что было время работы сортировки вставками, как мы видели его здесь?
[Студент] лучшем случае? >> Лучшем случае.
>> Было п, потому что в лучшем случае все сортируется,
и Сэмми и никто действительно было двигаться.
Они уже были на своих местах.
Так сортировки вставкой в ​​лучшем случае, в данном случае, с.
Но в худшем случае это вроде п квадрат. Почему?
Если мой список людей в обратном порядке,
Я сначала начать с номером 8 и вставить его или ее в правильное положение, которое прямо здесь.
Я как бы движение в сторону. Эти ребята несортированные, он или она сортируется.
Но теперь я, случается, выяснить, кто следующий? >> [Студент] 7.
7, в худшем случае, потому что это в обратном порядке.
>> Так вот 7. Где 7 принадлежите? Определенно у меня за спиной.
Но сейчас 7 на самом деле принадлежит не сразу позади меня, но за № 8,
так что я должен сказать: "Извините, номер 8, пожалуйста, вы можете двигаться таким образом,
"Чтобы освободить место для 7?" Сейчас я сталкиваюсь 6.
"Ах, извините, № 8 и № 7, вы можете двигаться, чтобы освободить место для 6?"
Итак, другими словами, со вставкой рода, хотя я не делаю много движений,
люди за меня делают еще очень много работы, и это должен стоить раз, когда кто-то.
Это будет стоить машинного времени.
Таким образом, в случае введения подобного мы до сих пор страдаем.
Если вы начинаете сложения общее число шагов, мы в конечном итоге удара примерно п квадрат
потому что эти парни нужны, чтобы освободить место для человека должен быть вставлен обратно в этот список.
И поэтому в данном случае тета просто не применима к конкретной истории под рукой.
Это все хорошо и хорошо. У нас есть эти 3 различных способа говорить о времени работы.
Но что это на самом деле означает в реальном выражении, если мы на самом деле пытаются код до алгоритма?
>> Позвольте мне предложить, что есть еще лучше, алгоритм там
, который сам имеет некоторые компромиссы.
Мы будем называть его сортировки слиянием, и это своего рода этом волшебном алгоритм
, который просто работает быстрее так или иначе, и это так легко выразить, по крайней мере в псевдокоде.
Реализация данного алгоритма сортировки слиянием будет следующим образом.
Когда вам дают п элементов - N чисел, русские люди, независимо - первая есть здравомыслие проверка.
Если п меньше, чем 2, сортировка слиянием просто останавливается. Он возвращается, так сказать.
Почему бы вам остановиться, если N меньше, чем 2? >> [Неразборчиво ответ студента]
Право. И снова, п не номер в списке, п является размер списка.
Если п меньше, чем 2, это означает, что список является либо 1,
где вы, очевидно, отсортированный если это 1 номер,
или 0, в этом случае нет ничего, чтобы разобраться,
поэтому мы должны такого рода базовым сценарием.
Если в списке так мало, что там просто нечего делать, в буквальном смысле не делать ничего. Возвращение.
В противном случае отсортировать левую половину элементов, а затем отсортировать правую половину элементов,
затем объединить 2 Упорядочить половины.
>> Этот вид кажется немного обмануть которой я прошу вас, как отсортировать элементы
и ты говоришь мне, "Сортировка левой половине, сортировать правую половину".
Я, как: "Все в порядке. Как сортировать левую половину?"
"Сортировать левую половину левой половине, сортировать правой половине левой половине, а затем сделать".
Ты вид циклически определения того, что это означает для сортировки,
но оказывается, что на самом деле блестящая в этом случае.
Это не по-настоящему этот порочный круг, который никогда не заканчивается
потому что оно закончится, когда? >> [Студент] Когда Вы достигнете 1 вещь.
Когда вы достигнете 1 вещь.
Поэтому, даже если вы можете начать с 8 человек, и я говорю: "Сортировка левая половина из этих людей,
этих 4-х человек ", то я говорю:« Как сортировать левую половину? "
"Ну, вроде 2 человека здесь". И тогда вы, как: "Хорошо, хорошо".
"Как вы сортировать левой половины этих людей?"
"Просто разобраться в этом 1 человек здесь". Что такое блестящее откровение сейчас?
У меня есть для сортировки 1 человек. Готово. Я не должен делать любую работу.
Но теперь я должен разобраться в этом человеке, но они одним человеком, делать нечего.
>> Таким образом, магия по-видимому, в этом третий шаг: слияния отсортированных половинки.
Таким образом, сортировка слиянием принимает эту блестящую понимание того, что если вы нарушите большая проблема вниз
на 2 меньше, одинаково размера проблемы
, а затем просто вид клея меньше решений вместе в конце,
Я полагаю, что мы можем сделать гораздо, гораздо лучше [нажав звук]
чем любой из рода отбор или сортировку вставками.
Я на самом деле игнорировал, что в течение получаса, но я действительно не знаю, что происходит
за пределами сегодня. [Жужжащий звук] [смех]
Итак, давайте посмотрим, если мы можем увидеть это с небольшой помощью от нашего друга Роба Боуден.
Есть 2 большие шаги в процессе сортировки слиянием.
Во-первых, непрерывно разделить список чашки пополам
до тех пор пока у нас есть куча списков только с 1 чашкой в ​​них.
Не волнуйтесь, если список содержит нечетное число
и вы не можете сделать идеально чистый срез между ними.
Просто произвольно выбрать, какой список, включив дополнительную чашку дюйма
Так что давайте разделить эти списки.
Теперь у нас есть 2 списка.
Теперь у нас есть 4 списков.
Теперь у нас есть 8 списков с одной чашки в каждом списке.
Так вот оно что на шаге 1.
Для шаге 2 мы неоднократно слияния пары списков с использованием алгоритма слияния мы узнали раньше.
Слияние 108 и 15 мы в конечном итоге со списком 15, 108.
Слияние 50 и 4, мы в конечном итоге с 4, 50.
Слияние 8 и 42 мы в конечном итоге с 8, 42.
И слияние 23 и 16, мы в конечном итоге с 16, 23.
Теперь все наши списки размера 2.
Обратите внимание, что каждый из 4 списков сортируется,
так что мы можем начать слияние пары списки.
Слияние 15 и 108, а 4 и 50 мы сначала взять 4, то 15,
то 50, то 108.
Слияние 8, 42 и 16, 23 мы сначала взять 8, затем 16,
то 23, то 42.
Так что теперь у нас есть всего 2 списки размер 4, каждая из которых сортируется.
Итак, теперь мы объединить эти 2 списка.
Сначала мы берем 4, то мы берем 8, то мы берем 15
и 16 и 23 и 42 и 50 и 108.
И мы сделали. Теперь у нас есть отсортированный список.
>> Роб был отчасти воспользовавшись что-то, что мы еще не сделали.
Было высказано мнение, но мы на самом деле не делать.
Он делал что-то физически с чашками, который предполагает
он проводил некоторый ресурс, кроме времени. >> [Студент] пространства. >> Это было пространство.
Тот факт, что он был такого рода двухуровневая таблица, где он был пространство здесь
и пространство здесь было на самом деле это означает, что он использует два раза больше места
как любой из наших алгоритмов до сих пор - сортировка вставкой, пузырьковая сортировка, или выбор рода -
но он был использованию этого дополнительного пространства для вида ходу вещей и обратно
, сохраняя при этом порядок.
И хотя он чувствует, как мы добрались до отсортированный список, который чувствовал, что это потребовалось время.
В действительности, то, что Роб делал именно этот алгоритм.
Он первым принял проблема размера п, разделил его на левую половину и правую половины.
Вот когда он переехал чашки. Затем он повторил этот процесс.
Он разделил 4 в 2 подхода из 2 здесь и здесь.
Затем он повторил, что процесс и разделить 2 на 2 комплекта 1 для каждого из этих различных кубков.
И вот, когда блестящая возможность.
В этот момент в истории, Роб был 8 списков размер 1,
все из которых были отсортированы уже.
>> Итак, что же он продолжить делать?
Парные он взял это отсортированный список, и это отсортированный список и объединить их.
Затем он взял эту и объединить их, то это одно и объединить их,
то это одно и объединить их.
А то, что он сделал дальше?
Он затем снова объединить большие списки, а затем снова объединить большие списки.
И если вы думаете об этом просто интуитивно сейчас, то, что он действительно делает?
Он был делением проблема в два раза, в два раза, в два раза, в два раза
для того, чтобы получить эти сверхмалые списки.
Тогда он был добр объединения двухместные, двухместные, двухместные, двухместные.
Так он делал в два раза больше работы, чем мы видели до сих пор
с чем с участием разделяй и властвуй, но не большая проблема.
В два раза больше работы не такое уж большое дело. Это всего лишь постоянным множителем.
И так же, как наши арифметические выражения и раньше, я просто хочу, чтобы вычеркнуть постоянными коэффициентами
как раз 2. Кого это волнует? Если это 2 млрд. раза 2, что еще много шагов.
Так что это слияние шагом, кажется, ключевым пониманием.
Давайте пройдем через это только численно раньше - О, это не будет продолжаться еще нет.
Давайте пройдемся по этим численно просто на самом деле увидеть, как это теряет значение.
Это в основном только анимация немного бедного человека.
Давайте предлагать это.
Время работы сортировки слиянием - мы просто нужен способ говорить об этом.
Это не математика, это просто какая-то краткий способ выразить себя.
Таким образом, T представляет собой время и п представляет то, что? >> [Студент] размер -
>> [Малан] Размер проблемы, число людей.
Так что я утверждая, что время для сортировки русского народа будет 0 количество времени
если п меньше 2, потому что, если у вас есть 1 чашка или нет чашки, у вас нет ничего, чтобы отсортировать.
Но в целом, я собираюсь предложить, что время для сортировки п элементов
будет время, необходимое для сортировки левой половины плюс правой половины
плюс - то, что это дополнительное + п? >> [Студент] Слияние рода.
[Малан] Это на самом деле слияния, потому что, если у вас есть п / 2 элементов здесь
и у вас есть п / 2 элементов здесь, сколько времени нужно, чтобы их объединить?
Так же, как Роб, вы должны вырвать эту сюда, может быть, вырвать здесь,
срывать здесь, вырви здесь, вырви здесь.
Вы должны коснуться каждого из стакана один раз.
И если есть 4 чашки плюс 4 чашки, это 8 чашек
или, более общо, 8 п чашки.
Таким образом, слияние шаге мы можем выразить, как я,
и что буквально включает в себя несколько раз Роб физически коснулся
один из тех пенополистирола чашки.
Итак, давайте делать произвольные пример.
Если есть 16 чашек, что время работы сортировки, используя алгоритм Роба, 16 чашек?
Это в 2 раза количество времени, затрачиваемое на сортировку 8 чашек
потому что у нас здесь 8 чашек, 8 чашек здесь.
Я не знаю, как долго это берет, так что мы обобщающих его как T на данный момент.
Кто знает, что это такое?
Но теперь я могу сортировать рекурсивно или несколько раз задать тот же вопрос.
Сколько времени нужно для того, чтобы отсортировать 8 чашек?
8 чашек я собираюсь сказать, занимает количество времени, затрачиваемое на сортировку 4 чашки плюс 4 чашки,
затем объединять их вместе.
Хорошо. Мы входим в цикл уже. Сколько времени это займет, чтобы отсортировать 4 чашки?
Время, необходимое для сортировки 4 стакана составляет 2 чашки плюс 2 чашки плюс сортировка процесс слияния.
Хорошо. Сколько времени это займет, чтобы отсортировать 2 чашки?
2 чашки является количество времени, необходимое для сортировки 1 чашка плюс время, необходимое для сортировки еще одну чашку
плюс количество времени, необходимое для слияния, которое находится всего в 2.
>> Хорошо. Последний вопрос. Сколько времени это займет, чтобы отсортировать 1 стакан?
Вот базовый вариант, что мы и предсказывали мы бы ударить раньше.
Дело в том, что он принимает никаких работ вообще, чтобы разобраться наименьшей из проблем
означает, что теперь, вроде класс стиля школы,
мы можем просто пойти начать подключение этих цифр масштаб
Мы теперь знаем, что T 1 является, таким образом я могу подключить 0 при Т 1.
Это даст мне ответ на T 2, который я потом можно подключить выше.
Это даст мне Т 4, который я могу подключить выше.
Это даст мне T 8, который я могу подключить выше.
А если я на самом деле, что математика, подключив эти ответы,
Я тогда получим T от 16 64.
А что значит 64 представляют?
Если Т 16, да, это в 16 раз 4.
Таким образом, я утверждаю теперь, что время работы, что называется сортировка слиянием -
и это будет самый необычный из тех, что мы видели до сих пор -
будет называться п § п
потому что сколько раз может лишить разделить целую кучу чашки пополам? Вход с.
Это то же самое, например, телефонную книгу, это так же, как самостоятельного подсчета пример.
>> Сколько раз Вы можете что-то делить пополам?
Однако, есть это слияние шагом.
Возможно, вам придется делить чашки пополам снова и снова, и снова,
но каждый раз, когда вы будете иметь, чтобы слияние.
И мы сказали ранее, что слияние п чашки занимает п шагов
потому что вы должны вырвать из чашки, вырвать из чашки, и вы должны коснуться каждого стакана один раз,
так же, как Роб сделал.
Таким образом, если мы делаем что-то журнал N раз, и мы делаем п вещей на каждый из этих итераций,
каждый из этих полураспадов, у нас есть п раз журнал с.
Поэтому, если мы подключить 16 в этом примере, в 16 раз войти в 16 -
Не волнуйтесь о том, почему это так, на данный момент, потому что я не обращала базы -
но журнал базе 2 из 16 в 4, 16 раза 4, 64.
Но в отличие от, если бы мы использовали пузырьковой сортировки и сортировки выбором сортировки или вставке с 16 числа,
что бы время работы было, если п 16?
Это будет 16 квадратов, которая является 256, что, даже если вы не совсем следовал всем математике,
256 это больше, чем 64. Это действительно волшебный вынос здесь.
И понимаю, что работать через это в меньшей примеры, как вы будете на PSET
делает его еще более интуитивным.
Но что это означает в терминах чувства этого алгоритма заключается в следующем:
Если мы на самом деле смотрим на сортировка слиянием здесь - дайте мне потяните его вверх в этом окне здесь -
это немного другой пример, которому мы должны все 3 из этих алгоритмов -
Пузырь, отбора и слияния - просто бок о бок.
>> Они все началось со случайной баров, и это хорошо.
Никто не имеет фундаментальное преимущество над другими.
Я собираюсь в момент щелкните каждый из этих анимации - Пуск, Пуск, Пуск -
так быстро, как могу, так что, грубо говоря, все они начинаются в то же время,
и давайте считать, что худшем случае пузырьковой сортировки по времени работы это что? >> [Студент] N в квадрате.
N в квадрате. Худшем случае выбора рода бежит время? N в квадрате.
И сортировка слиянием видимо - даже если вы не совсем понимаю всю математику сейчас,
это станет значительно более интуитивным в течение долгого времени - это, мы утверждаем, п § п раз.
И потому, что § п строго меньше п раз у нас есть большие номера,
п § п раз меньше, чем раз п п или п квадрат.
Так что же это чувствует, чтобы быть на самом деле лучший алгоритм с точки зрения времени работы,
п § п раз, в отличие от п квадратов? Здесь мы идем. Клик, клик, клик.
>> Вот что значит использовать что-то вроде сортировки слиянием.
У нас есть время. Давайте посмотрим, что происходит здесь.
[Смеется] Чьи деньги на пузырьковой сортировки?
Это скорее зависит от входного иногда.
Давайте посмотрим.
Пойдем. Он чувствует, как он догоняет. >> [Студент]: пойди, пузырьковой сортировки!
[Студентам ропот]
[Малан] Да, да.
[Студентам ропот] Иди, иди, иди!
[Все аплодисменты] [аплодисменты]
Так что теперь с 1 последний, окончательный демо, если это немного хитро, чтобы обернуть ваш разум вокруг математике
или своего рода визуализация есть, вы можете услышать скорости
различных алгоритмов по-разному.
Это анимация кто-то сделал, что на самом деле звучит партнеров
с процессом замены и высота баров.
Как мы увидим здесь, есть несколько алгоритмов сортировки, что там люди не подумал.
Это первая будет сортировку вставками, и это будет пролететь через
и дать вам звуковой смысле, как эти различные алгоритмы работы.
Вот сортировки вставкой.
[Электронный звуковой сигнал]
[Малан] Bubble рода.
[Быстрый электронный звуковой сигнал]
[Малан] Выбор рода.
[Быстрый электронный звуковой сигнал]
[Малан] Слияние рода.
[Электронный звуковой сигнал]
[Звуковой сигнал замедляется] [смех]
[Малан] Gnome рода.
[Электронный звуковой сигнал]
>> Это CS50. Увидимся на следующей неделе. [Аплодисменты и крики]
>> [CS50.TV]