[Музыка Воспроизведение] Дэвид Дж. МАЛАН: Хорошо. Так что добро пожаловать обратно. Это CS50, и является К концу недели три. Так вспомним в последние несколько недель, Мы проводили довольно много время на C, по программированию, по синтаксису. И это вполне нормально, если вы все еще борется с проблемой установить 2, чтобы быть биться головой о стену. Это загадочное вида сообщения об ошибке а ошибки, которые вы Не вполне может погнать вниз. Потому что, будьте уверены, что всего за время несколько недель вы будете оглядываться на вещи, как Цезарь, и [? V-genair,?] может быть, даже трещина, и понимают, насколько далеко вы приехали в течение короткого периода времени. Так что, если это утешит, повесить там на данный момент. Сегодня, однако, мы начинаем переход к вещам более высокого уровня. И мы начинаем считать само собой разумеющимся, что вы, ребята, знаете, как программировать, или, по крайней мере начала что уровень комфорта. И мы начнем, как мы можем идти о разработке программы более эффективно. Как мы можем идти об оптимизации Эффективность наших алгоритмов и вообще решения более интересные задачи. И начинают считать само собой разумеющимся, что, если бы мы хотели, мы могли бы код до любого из примеров мы имеем в виду. Таким образом, сегодня мы не трогайте клавиатуру любой формы кода. Это будет гораздо более высоком уровне, и В конечном счете, о решении проблем. Таким образом, чтобы добраться до этой точки, то позвольте мне выдвинуть что следующие семь прямоугольники представляют семью дверями, за которые целый букет номера, среди которых число 50. Позвольте мне проецировать на этом Экран здесь также. И предлагаю нужен доброволец, чтобы помочь найти мне номер перед Интернет здесь, чтобы посмотреть. Поднимайся, в розовом. Хорошо. Как тебя зовут? Дженнифер: [неразборчиво] Дэвид Дж. МАЛАН: Простите? Дженнифер: Дженнифер. Дэвид Дж. МАЛАН: Дженнифер. Ладно, Дженнифер. Очень приятно. Поднимайся. Таким образом, эти вот семь дверей, и то, что Я хочу, чтобы ты сделал для нас здесь, на глазах у всех своих одноклассников, это найти нам номер, 50. Чтобы найти номер, вы можете заглянуть за любой из этих дверей, просто нажав на одной из дверей, и это покажет его номер. И давайте посмотрим, как быстро вы можете найти нас числом, 50. 15. 16. 50. Красиво сделано. Хорошо. Аплодисментов для Дженнифер. [Аплодисменты] Хорошо. Так какова была ваша стратегия нахождения числа, 50? Дженнифер: Хм, я думал, может быть, если - [Неразборчиво] Дэвид Дж. МАЛАН: Ох. Дайте ему одну секунду. Так была ваша стратегия нахождения числа, 50? Дженнифер: Так что я просто начать в начинаем видеть то, что первый номер было, а потом я подумал: может быть, если они сортируются, я буду просто продолжать нажав выше? Дэвид Дж. МАЛАН: OK. И мы, кажется, нашли , что, чтобы иметь место. Хотя, давайте отогните слоев только немного, и вы хотите пойти вперед и раскрыть другие двери Вы могли бы выбрали? Дженнифер: О, дорогой. Дэвид Дж. МАЛАН: Ах. Дженнифер: Так, мне просто повезло. Дэвид Дж. МАЛАН: Таким образом, вы повезло. Хорошо. Так не плохо. Но это интересно понимания, не так ли? Если предполагается, и вы действительно получали, Действительно, немного повезло там. Но если предположить, что номера были сортируются, вы можете быть более точным , как, которые повлияли Ваше поведение? Дженнифер: Так что, если в них разобрались, я думал, может быть, от меньшего к большему. Дэвид Дж. МАЛАН: OK. Дженнифер: Или, если это закончило тем, действительно большой, то от большего к меньшему. Дэвид Дж. МАЛАН: OK. Так что от большего к меньшему, или меньшего к большему. Но позвольте мне предложить, предположим, что у вас было получили не повезло, и предположить, что они не были, по сути, сортируют, сколько эти двери может у вас было заглянуть за что в худшем случае? Дженнифер: Все из них. Дэвид Дж. МАЛАН: Все из них. Так что давайте обобщать, что при п. Там, оказывается, 7, но давайте больше обычно говорят, что есть N на двери Экран здесь. Таким образом, в худшем случае, вам придется заглянуть за 7 дверей, двери или н. И так это на самом деле, это немного удачи сегодня, но это действительно линейный Алгоритм в духе, даже если вы были отчасти пропуская вокруг. Разве это справедливо? Дженнифер: Да. Дэвид Дж. МАЛАН: Ну, позвольте мне увидеть, если ваш Стратегия изменения, если я перееду нам В качестве второго примера здесь с 7 различных дверей. Одинаковые номера, но это время они сортируются. Что ваша стратегия здесь будет, пытаются поставить в своем уме, что другие номера были - Дженнифер: OK. Дэвид Дж. МАЛАН: - раньше? Дженнифер: Давайте начнем с первой. Дэвид Дж. МАЛАН: Хорошо. Начнем с первого. 4. А где вы собираетесь пойти, и почему? Дженнифер: 4 действительно мал. Так что, если они рода, может быть, наименьшая к крупным, он должен , что в два раза, и -. Дэвид Дж. МАЛАН: OK. Давайте посмотрим, что вы думаете? Дженнифер: Попробуйте последний. Ниццу. Дэвид Дж. МАЛАН: Очень красиво сделано. Хорошо. [Аплодисменты] Дэвид Дж. МАЛАН: OK. Так что на самом деле вы делаете это ужасно, потому что ты делает это очень хорошо. Что оставляет нас неспособными сделать определенные точки. Так давайте попробуем здесь откат. Дженнифер: OK. Дэвид Дж. МАЛАН: Хорошо сделано, тем не менее. Итак, вы начали с самого начала, Вы видели, что это было 4, то вы перемещается в конец. Но предположим, что вы не повезти там, и предположим, 50 был где-то в другом месте. Что ваш третий шаг был? Дженнифер: Вернуться к началу. Дэвид Дж. МАЛАН: Вернитесь к началу. Итак, вы бы уже коснулся эта дверь, которая была 8. Хорошо. Так что это не 50. Где бы вы смотрели дальше? Дженнифер: Если бы я не знают, что они отсортированы. Дэвид Дж. МАЛАН: Правильно. Ну, если вы знали в них разобрались - Дженнифер: О, знал, да. Дэвид Дж. МАЛАН: - Но вы не знаю, где был еще 50? Дженнифер: Просто продолжайте идти. Дэвид Дж. МАЛАН: Хорошо. ОК. Продолжайте. Хорошо, что я могу работать. Дженнифер: OK. Дэвид Дж. МАЛАН: Теперь, если вы просто собираемся продолжать, как тебя Алгоритм возложенных загнан в. Дженнифер: линейная -. Дэвид Дж. МАЛАН: Это разновидность линейной. Но позвольте мне предложить, пусть мне положить на месте. Позвольте мне обновить страницу. же число, одинаковое расположение, же дверей. Но вспомните, что первый день в классе, когда мы разорвали в телефонной книге половину, вроде, и то, что было нашей стратегии есть? Дженнифер: Начало в середине. Дэвид Дж. МАЛАН: OK. Так начинаются в середине. Так что давайте идти вперед и имитировать это. Начало в среднем по Показательно, что дверь. Таким образом, число 16. Итак, что бы сильный парень сделал, кто сорвал телефонную книгу в два раза, чтобы добраться до следующего Guess? Дженнифер: Перейти в эту половину. Дэвид Дж. МАЛАН: А почему бы не так ли? Дженнифер: Если они были видом наименьшая к крупным, то 50 должно быть в этом направлении. Дэвид Дж. МАЛАН: Хорошо. Полностью разумным. Так как телефонная книга, вы идете в право в отличие от левой стороны, но здесь является ключевым еды на дом. Теперь вы можете или просто выбросить его оторвать, половина этой проблемы, оставляя вас не с 7 дверей, но на самом деле всего лишь 3. Что примерно половина Масштабы проблемы. Хорошо. Так что теперь вам придется сделано после вы идете прямо? Дженнифер: Так 16 все еще довольно мал, по сравнению с 50, так что, возможно, я постараюсь, как, на этот раз. Дэвид Дж. МАЛАН: Хорошо. 42. Ладно, так что теперь твоя инстинкт говорит вам? Дженнифер: Я могу выбросить это, а затем просто - Дэвид Дж. МАЛАН: OK. Хорошо, вы можете выбросить Левая половина там. Дженнифер: - выбрать этого. Дэвид Дж. МАЛАН: И правильно. Дженнифер: Да. Дэвид Дж. МАЛАН: Поэтому, даже если это трудно , чтобы увидеть, возможно, когда есть только 7 дверей, подумайте о том, в настоящее время, согласованность алгоритма, который просто применяется. В предыдущем случае, вы сделали повезти, которая была отличной. Но вы действительно использовал эвристический, Я бы сказал. Вы использовали рода своим инстинктам, и зная, что это рассортировать это довольно небольшой в начале, очевидно, мы в надо идти правее. Но в некотором смысле, Вам повезло, , потому что, может быть, это был номер 100, и, возможно, было более 50 в середине. Может быть, даже 50 было здесь. Но то, что вы сделали немного по-другому на этот раз было, вы сделали то же самое снова и снова. И я утверждаю, что то, что вы просто действительно, хотя и зависит от телефона Книга Например, нечто гораздо более алгоритмического и многое меньше специальных обсаженных. Гораздо меньше инстинктивным. Таким образом, в конце дня, как бы Вы описали эффективность Первый алгоритм, куда вы пошли слева направо, по сравнению Второй алгоритм здесь? Дженнифер: Это нужно, как, может быть, вдвое сократить время, или даже больше, да. Дэвид Дж. МАЛАН: Хорошо, может быть, даже больше. Давайте нажать чуть сильнее на этом. То, что действительно, если мы будем продолжать эту логике, мы, безусловно, вдвое время работы с этой второй алгоритм отбрасыванием половины цифры, но то, что мы сделали на следующий итерации, когда Дженнифер показала второе число? Мы вдвое количество дверей снова. И что тогда мы сделали после этого, если было больше дверей, чтобы играть с? Мы бы вдвое сократить их, и снова, и снова и снова. И это было так же, как вы, ребята, все стоя на первой неделе класса, половина из вас сидит, половина из вас сидит, половина из вас не садиться, пока в один одинокий Душа стояла. И мы говорили, что время работы , что количество шагов, что требовалось, о порядке и что? Выступающий 1: [неразборчиво] Дэвид Дж. МАЛАН: Так логарифм по основанию 2 п, или просто проще говоря, войти н. Так что-то логарифмическая. И графика была не прямая линия , что стало еще хуже и хуже, это было эту интересную кривую, которая не получить так плохо с течением времени. Так что давайте держаться за эту идею. Давайте благодарить Дженнифер. Спасибо большое, что пришли и выше. И, одной секунды. Нет настольных ламп сегодня, но мы действительно есть CS50 шары стресса. Дженнифер: Ура. Дэвид Дж. МАЛАН: Хорошо, здесь. Спасибо за неся стресс здесь. Хорошо. Итак, давайте посмотрим, если мы не можем сейчас формализовать это немного больше. Итак, еще раз, что мы только что сделали, практически то же самое, как мы сделали , что в первую неделю. Но вместо того, заканчивается просто линейная Алгоритм, который мы изображены Ранее, как эта прямая, которой, если положить еще одну дверь экрана, а затем Дженнифер бы должны были выглядеть, возможно, за еще одну дверь. Если мы поставим еще две двери, она может иметь заглянуть за две двери. Так вот, там была эта линейная отношения между размером Проблема, скажем, на оси х, а Количество времени, необходимое для решить на у. Но картина, которую я имел в виду ранее была Эта зеленая линия. Зеленый намеренно, потому что он просто почувствовал себя лучше. В теории, алгоритм, когда мы сделали это с телефонной книгой, когда мы сделали это с вами подсчет друг к другу, и Во втором случае, когда Дженнифер просто сделал это здесь, это был своего рода принципиально лучше. Потому что это было не только в два раза быстрее. Это была даже не в четыре раза быстрее. Это было полностью зависит от того, что Размер входного было относительно того, сколько шаги, которые он в конечном счете принял. И вот эта простая идея, что мы все взяли само собой разумеющимся с телефонной книгой, Аналогичным образом можно применять что-то вроде этого. И это могло бы быть более небрежно известный как, как можно было бы представить, разделяй и властвуй. Не в отличие от того, что мы сделали, конечно, с телефонной книгой. Но псевдокод, напомним, было это. Поэтому мы не будем делать это снова, но вспомнить В первую неделю, все мы встали а потом и половину вы сели, половина из вы сели, половина из вас сел. Этот алгоритм был реализован в Немного обмана Кстати, в том, что оно не только один из меня подсчета По сути, более эффективно. В таком случае, я используя вторичный ресурс. Вроде, несколько процессоров, несколько мозгов, несколько умных людей в Номер мне помогали получить от чего-то линейной к чему-то логарифмические, от чего-то красное на что-то зеленое. Но в данном случае, Дженнифер только и может принципиально улучшить выполнение своего первого алгоритма, снова, просто подумав немного сложнее. И теперь, когда приходит время для реализации эти вещи, выясняя какие строки кода вы можете написать такой что вы можете повторять их снова, и снова, и снова, как бы Алгоритм циклически повторяется. Потому что вы не будете иметь роскошь, как Дженнифер сделали сначала, чтобы просто целая куча IFS и сказать: хм, если это первое число 4, Позвольте мне прыгать всю дорогу до конца. Ох, если это число слишком большое, Перехожу произвольно назад второй элемент. Вы увидите, что это собирается быть много труднее формализовать то, что мы, люди, принять как должное, как очень разумный эвристики, но компьютер только собираюсь делать то, что вы скажете ей сделать. Теперь это очень интересно последствия. Этот график является своего рода означало для сортировки сокрушить визуально, но уведомление, где является прямой на этом графике? Где линейный график , которые мы называем п? Ну, это вроде к нижнему этой картины, не так ли? Так что все, что мы сделали, мы есть вид уменьшении до оси Х и Y-оси, чтобы попытаться получить ощущение того, что другими типами кривых выглядеть. И специфика математического Выражения сегодня не будет иметь значения так много, но заметил, что есть много алгоритмы, которые гораздо хуже, чем то, что это линейная. Действительно, N кубе выглядит довольно плохо. 2 к N выглядит довольно плохо. N квадрат выглядит довольно плохо. И мы увидим, что некоторые из этих может быть в сегодняшней реальности. И журнал N не чувствует, как плохо, но лучше, чем п логарифм по основанию 2 н. Но вы знаете, это было бы еще более удивительно, если Дженнифер, или если мы, В первую неделю, придумали то, что это журнал журнал N. Итак, другими словами, есть все это Диапазон возможных решений проблемы, но даже здесь, уведомления что произойдет. Когда я уменьшить масштаб, какой из этих кривых собирается оказаться абсолютным худший из тех, на экране теперь? Таким N куб выглядит довольно плохо на данный момент. Но если мы уменьшения и видеть больше X и Y-оси, кто собирается доминировать в конечном счете? Так что на самом деле оказывается, что от 2 до N, и вы можете понять это просто подключение в некоторых более крупных номера, и вы увидите, что от 2 до N, действительно, становится все больше намного быстрее. Если мы действительно уменьшить масштаб, 2 к N алгоритм абсолютно сосет. Я имею в виду, что это собирается взять совсем немного времени для того, Компьютер в большом количестве через. Но вы увидите, со временем, особенно с будущими домашние задания и даже дипломные проекты, это ваши данные набор получает большие, все в порядке? Даже в первой версии Facebook, как количество друзей и число зарегистрированных пользователей получили большие, Вы можете сортировать ее в телефон и осуществить то, с линейным поиском, или очень простой сортировки Алгоритм, как мы увидим сегодня. Вы должны начать думать труднее и труднее об этих проблемах. И типы проблем таких местах, как Facebook, и Google, и Microsoft, и другие работы является именно эти рода большие сортировки данных вопросов больше в эти дни. Хорошо. Так что успех Дженнифер в этом втором Алгоритм, честно говоря, она сделала удивительно а в первый раз, но давайте пишу это как удачу, так что мы может сделать эту точку. Во втором случае, она использовала Алгоритм, который повторяется снова и снова, но она приняла как должное определенные предположения, что мы позволили ей, но она использована некоторыми подробностями второй раз, что у нее не было первый раз. Что было что? То, что список был отсортирован. Поэтому, как только список был отсортирован, мы утверждают, что Дженнифер была в состоянии сделать принципиально лучше. 7 дверей, да, уже не так интересно, Однако допустим, что мы 7000000 дверей. Журнал N, безусловно, будет выполнять многое, многое быстрее в долгосрочной перспективе. Но она должна была быть Двери отсортированы для нее. Теперь, я взял на себя смелость сделать это Заранее на экране компьютера здесь, но предположим, что Дженнифер должен был сделать это самой? Предположим, что двери в вопрос представлены данные в базе данных, или Друзья зарегистрированы для Facebook, или любой веб-страницы в Интернете, которые различные веб-сайты, возможно, потребуется в индекс или поиск. Предположим, что вы только что исходные данные установлен, и это оставили для Вас, или Дженнифер это сделать сортировку? Это, скорее, требует, чтобы мы отвечаем вопрос, ну, сколько времени взял бы Дженнифер, или даже меня, для сортировки этих цифр заранее, чтобы что она может воспользоваться этим? Верно? Потому что подразумевается, конечно, если это займет некоторое время, чтобы разобраться номеров, кто, черт возьми, что вы заботится можно найти такое число, как 50 так быстро, как в случае с Дженнифер, если мы более перегружены количество общего времени потребовалось сортировкой вещей заранее? Итак, давайте посмотрим, если мы не можем нарисовать картину здесь. У меня есть целая куча больше стресса шаров, если это помогает сломать лед здесь. И если вы не против, мы нужно семь добровольцев - о, хорошо. Ничего себе. Так что мы не должны тратить на настольные лампы, кажется. Хорошо. Так, как вы два на передней панели. Как насчет вас двое парней в спине. Так вот четыре. Как насчет вас перед пять, шесть и семь. Вот здесь. Ваш друг, указывая вам, так что вы получите приз. Хорошо. Поднимайся. И почему бы нам не иметь вас Парни иди сюда. Я собираюсь дать вам каждый ряд. И пойти дальше и устроить себе одинаково к тому, что изображено на экране. [Промежуточное VOICES] Дэвид Дж. МАЛАН: Oop, извините. Ошибка. Хорошо. Ну, вот мы идем. Номер пять. Номер шесть. Один, два, три, четыре, пять, шесть, семь. О, это неудобно. Докладчик 2: Я буду просто получить -. Дэвид Дж. МАЛАН: Очень. Хорошо. Спасибо за участие. [Аплодисменты] ОК. Хорошо. Итак, мы имеем четыре, два, шесть, один, три, семь, пять. Прекрасно, таким образом мы имеем семь добровольцев здесь, которые равны по ширине массив, который мы играем с ранее. И я выбрал семь по причинам которые будут просто удобна в немного. И я собираюсь предложить сначала, что мы сортируем эти семь добровольцев. Если вы хотели бы, во-первых, , чтобы поздороваться, хотя. Так как это будет неловко несколько минут. Представьтесь. GRACE: Привет, я Грейс. Я на втором курсе в Левереттом дом. BRANSON: Привет. Я Брэнсон. Я на первом курсе в сварке. GABE: Привет. Я Гейб. Я младший в Кабот. Нил: Я Нил. Я на первом курсе в Мэтьюз. Джейсон: Я Джейсоном. Я на первом курсе в Greenough. Майк: Я Майком. Я на первом курсе в серых. Джесси: Я Джесс. Я на втором курсе в Левереттом. Дэвид Дж. МАЛАН: Отлично. Хорошо. Что ж, спасибо всем нашим добровольцы здесь до сих пор. И задача под рукой теперь собирается быть для сортировки из этих парней, но потом мы собираемся иметь немного подумать над тем, как эффективно мы на самом деле сортировал их. Так давайте сначала попробовать это. Вы, ребята, можете видеть друг друга номера просто путем размещения вокруг углов. Идти вперед и принимать несколько секунд, а Разбейтесь от самых маленьких на слева крупнейших справа. Go. ОК. Хорошо. Это было действительно штопать быстро. Теперь кто-то здесь, что был алгоритм что эти ребята применять? Выступающий 1: наименьшего к наибольшему. Дэвид Дж. МАЛАН: OK. Наименьшего к наибольшему действительно своего рода цели, но я не уверен, что это действительно алгоритма. Меньшего к большему не говорит меня шаг за шагом, что делать. Да? Выступающий 1: [неразборчиво] Дэвид Дж. МАЛАН: OK. Так что если вы видите человека, меньше, чем свой номер, а затем перейти к справа от них. Так что теперь становится все более выразительным, больше похоже на алгоритм, потому что вы можно говорить, если это, то, что. Поэтому у нас есть своего рода условные конструкции. И эти парни, казалось, сделал, что несколько раз, потому что некоторые из вас переехал немного от расстояния. Так появился предположительно какой-то цикл происходит в их умах. Но давайте попробуем формализовать это. Если вы, ребята могли сбросить обратно такой компоновкой. Давайте посмотрим, если мы не можем формализовать немного, а затем задать вопрос, просто насколько эффективно это? Конечно, когда мы делаем это более медленно, он будет чувствовать себя как благо алгоритм, но давайте посмотрим, если мы можем поставить наши пальцы на конкретные шаги. Таким образом, вы два парня и четыре два. Или Вы правильным или неправильным заказом? Очевидно неправильно. Таким образом, мы поменялись местами. Теперь я собираюсь отойти в сторону здесь и говорить, 5:56. Вы правильно или неправильно? GABE: Правильно. Дэвид Дж. МАЛАН: Правильно. Шесть и один? Не-а. Подкачки. Так вот сменами. Шесть и три? Не-а. Подкачки. Шестью и семью? Выглядит хорошо. Семь и пять? Джесси: [неразборчиво] Дэвид Дж. МАЛАН: Хорошо, обменять. И сортируются. Хорошо. Так, очевидно, нет, не так ли? Так было больше происходит. Но, в самом деле, эти ребята, даже просто инстинктивно. продолжал двигаться. Они не просто остановиться, как только они исправлена ​​одна проблема. Так. Более того, я буду иметь сделать то же самое. Я собираюсь должны разобраться задних перемотки до начала этой проблемы или в начале этого массива люди, давайте начнем называя их. И теперь, каковы должны мой алгоритм на втором проходе быть? Выступающий 1: То же самое. Дэвид Дж. МАЛАН: То же самое. И это, я начинаю любить, не так ли? Как только вы можете найти себе делать одно и то же снова и снова, это все больше походит на алгоритм, и менее человеческий инстинкт. Так что теперь, здесь мы идем снова. Два и четыре? Нет. Четыре и один? Ах, было действительно некоторые работы, которую еще предстоит сделать. Для и три? Хорошо. Четырех до шести? Шести и пяти? Шестью и семью? Хорошо, теперь, сделано. ОК, нет. Я должен вернуться. Так что теперь, опять же, мы делаем это немного более сознательно. А теперь, есть только один мозг выполнения этого алгоритма. Один процессор, если вы будете. И, честно говоря, это единственный ресурс, мы будем иметь доступ. И как только мы действительно возвращаемся к клавиатуре и есть что-то вроде C в нашем распоряжении, мы только пишем программу , которые могут сделать одну вещь за один раз. Принимая во внимание, эти парни минуту назад, мы заемных их коллективного ума как вы, ребята сделали в неделю нулю. Так что давайте продолжать делать это. Два с. Два и три. Три и четыре. Четыре и пять. Пять и шесть. Шесть и семь. Делать? Так что я, но позвольте мне играть Адвокат дьявола. Я тоже, вроде компьютера, который просто сделал пас через этот массив люди, знают, что я сделал? Выступающий 1: N: Дэвид Дж. МАЛАН: Так почему? Что я должен сделать для того, чтобы решительно заключить, что я сделал? Наверное, еще один проход. Верно? Потому что все, что я знаю из предыдущего проход, что я исправил ошибку. А значит, может быть, есть еще одна ошибка что мне нужно исправить. Поэтому я могу лишь быть уверены перематывать, и Затем проверка, 1:59, двух-и три, три и четыре, четыре и пять, пять и шесть, шесть и семь. Хорошо, теперь я не сделал никакой работы. Я не могу, конечно, помните, что я сделал не работать с чем-то как переменная, нравится Int. Назовите это свопы, свопы и если равно 0, как только я попасть сюда, и это началось в 0, то Я бы просто глупо продолжать идти взад и вперед, проверяя снова, и снова, и снова, не так ли? Потому что, если вы застряли в некоторых вид бесконечный цикл. Поэтому, как только есть 0 свопы, мы можем утверждать, что это Алгоритм действительно полным. Теперь, давайте поставим на этом имя. Алгоритм, который я предлагаю, мы просто реализовано то, что называется пузырем вида, известного как таковой в том смысле, что числа, большие виды Пузырь их путь к вершине, или до в конце массива чисел. Но насколько эффективным был этот алгоритм? Сколько шагов я физически должны взять, например, для сортировки этих семь людей? От четырех до пяти? ОК, слишком много, в конечном счете будет ответ. Но даже тогда, определенное количество это не так интересно. Давайте обобщим ее как н. Так что если я русского народа здесь, и они были, вроде, в случайном порядке на начинается, в этом исходном порядке. Ну, сколько шагов я есть взять на первом проходе? Это был один, два, три, четыре, пять, шесть, и они семь человек, поэтому это семь, шесть -, так что это н минус один шаг в первый раз. Теперь, сколько шагов я есть принять, когда я перемотана? Ну, мы могли фактически удвоится, что если мы действительно хотели, но сейчас, я раз собирался сказать, все в порядке, другая N минус 1. Таким образом, N минус 1 собирается получить раздражает отслеживать, так что давайте просто за слегка. Так 2n шагов. Так 14 шагов, плюс-минус. Сколько раз я беру шаг в следующий раз? Ну, это 3n. на самом деле. И теперь, в худшем случае, для Например, сколько раз у меня есть туда и обратно, туда и обратно, выполнения этого алгоритма, обменивая людей на каждом проходе, грубо? Это на самом деле п квадрат, верно? Потому что в худшем случае вы можете вида из думать об этом интуитивно, хотя это может занять немного немного времени, чтобы утонуть внутри В худшем случае, что бы эти семь человек, были похожи, в условия соглашения из их числа? Совершенно в обратном направлении, не так ли? И так же, чтобы имитировать, что, то, что было, тебя зовут? Майк: Майк. Дэвид Дж. МАЛАН: Майк? Хорошо, Майк, ты можешь просто присоединиться ко мне за здесь в течение всего одной секунды? Вообще-то, нет. К сожалению Майк, давай назад. Как тебя зовут? Нил: Нил. Дэвид Дж. МАЛАН: Нил. ОК, Нил, ты пойдешь со мне, если вы не против. Так что я собираюсь предложить, только для простоты, что Нил является теперь в его худший возможный случай. Но вспомните, как я реализовал мой алгоритм. Я сравниваю, сравнения, сравнения, сравнения, сравнения, о. Теперь эти ребята из порядка, так что я могу исправить. Так вы, ребята поменять. А сейчас рассмотрим, как далеко Нейл действительно должны пойти? Это примерно п. Вы знаете, это на самом деле не с. Это все равно, N минус 1, но я получаю раздраженный отслеживание мало числа, так что давайте просто называть его п. Так что если Нил перемещается на один шаг максимально каждого времени и переместить Нил один шаг, Я должен сделать это действительно утомительно проход туда и обратно, это примерно Делая это, п шагов, в общей сложности п раз, потому что он собирается взять меня что многие шаги, чтобы получить все Нейл туда, где он принадлежит. Не говоря уже о всех остальных, если вы, ребята, были неправильно заказаны, а также. Так что давайте называть пузырьковой сортировки N квадрате. Время работы этого алгоритма, выполнение этого алгоритма, Эффективность этого алгоритма мы будем просто описать более вообще как N в квадрат. Что приятно, потому что я мог сделать Тот же пример с восьми человек, девять люди, миллионы людей, и что Ответ не изменится. Так что, если вы, ребята, не возражали бы, давайте сбросить вас туда, где вы начали. И давайте обратимся к двум другим подходам и увидеть, если мы не можем сделать принципиально лучше, чем эта. Поэтому в этот раз, я собираюсь предложить своего рода другой алгоритм. Это был очень умный из нас в прошлый раз, и вы, ребята были правы, чтобы иметь Право инстинкты только отчасти перекачки попарно. Но если я действительно хотел подойти к этому просто, и моя цель состоит в перемещении все маленькие номера таким образом, и толкать все большие числа, которые Кстати, почему бы мне не сделать это в самые наивные возможными способами и посмотреть, если я может сделать лучше, чем то, что было довольно сложный алгоритм? Итак, давайте посмотрим. Четыре является довольно небольшим числом, так что я собираюсь оставить вас есть момент. Ох, номер два еще лучше. Так вы можете просто шаг вперед на минутку? В настоящее время это мой наименьшим номером кандидата, и я буду помнить , что с, как, переменной. Но я собираюсь продолжать проверять. Есть ли кто-то, чьи число меньше? Шесть, нет. О, есть Нил снова. Так что я собираюсь, чтобы подтолкнуть вас обратно рода концептуально. Нил будет выйти вперед. А теперь, переменная, который я использую, чтобы отслеживать, кто имеет наименьший количество обновляется, чтобы содержать Нейл месте. Ну, давайте посмотрим. Три, семь, пять. Хорошо, я знаю Нила был самым маленьким. Что самое простое, что Для меня же теперь делать? Я не собираюсь тратить свое время, просто пузырится Нил одно место влево. Почему я не могу просто поставить Нила, где он принадлежит, что является, конечно, где? Все пути в самом начале. Так Нил, пойдем со мной. И что тебя зовут? GRACE: благодать. Дэвид Дж. МАЛАН: благодать. ОК. Так и благодать, к сожалению, вы вид на пути. Так как же нам решить эту проблему? Верно? Если это массив, есть только семи местах. Напомним, что с Робом, мы говорили о объявив возрастов, и у нас только было конечное число возрастов? Та же самая идея здесь. У нас есть только конечное число целых чисел. Грейс находится отчасти в нашей Кстати, так как мы можем исправить? Самый простой способ, как, Грейс, извините. Вы будете иметь, чтобы перейти там, так мы можем сделать комнату. Теперь, если вы думаете об этом, может быть, мы просто сделали эту проблему еще хуже. А может быть, мы сделали, потому что, если Грейс была в нужном месте? Но мы знаем, что она не так, потому что В противном случае она была бы стоящих вперед, а не Нил в это время, не так ли? Мы уже проверили ее номер вне. Хорошо. Так что теперь, Нил в нужном месте, и Я могу сделать небольшую оптимизацию. Для следующей минуты, я буду игнорировать Нил все вместе, так, чтобы не тратить время, или случайно обменять его в неправильном месте. Так что теперь, как я могу найти следующую элемент, который самый маленький? Два. Это довольно хороший номер, если Вы хотите сделать шаг вперед и Я буду помнить тебя. Шесть, ничего хорошего. Четыре, три, семь, пять, ничего хорошего. Итак, позвольте мне перевести вас на ваше правильное место. И мы просто повезло на этот раз. Теперь, я собираюсь игнорировать эти два парня, и теперь сделать еще одну пройти через это. Шесть, что довольно малое число. Давай вперед. Ой, простите. Число Грейс лучше, так что шаг вперед на скорости. Четыре. К сожалению, Грейс. Вернуться снова. Номер три лучше. Семь. Пять. И что теперь тебя зовут? Джейсон: Джейсон. Дэвид Дж. МАЛАН: Джейсон. Так Джейсон сейчас наименьшая Элемент я выбрал. Куда он пойдет? Так где шесть есть. И ваше имя снова? GABE: Гейб. Дэвид Дж. МАЛАН: Гейб. Гейб находится в пути. Что проще всего сделать? Поменять эти два парня и продолжить. Итак, теперь давайте посмотрим. Кто самый маленький? Четыре. Позвольте мне только отчасти обман. Пять будет наименьшим. Я нахожу Далее, если, вы хотите к шагу вперед, что я должен делать с эти ребята, с Гейб? Поменяйте снова. Так что теперь, все еще немного не в порядке. Я нашел Гейб быть самым маленьким, так что Я сую его, переместить вас парни. И сделано. Так что ответ такой же. Конечным результатом является то же самое. Какой из этих двух алгоритмов что лучше? Второй, я слышал. Почему? Выступающий 3: Это п шагов [неразборчиво]. Дэвид Дж. МАЛАН: Это п шагов по большей мере. Интересно. Так это хоть? Так как же я могу найти наименьший элемент? Сколько шагов я должны принять найти наименьший элемент? Я взглянул на всем пути В конце концов, не так ли? Потому что в худшем случае, то, что Если Нил были здесь? Так просто найти наименьший элемент берет меня п шагов, или N минус 1. Но, хорошо. Так исправить Нил. Помните, что, минуту или около того назад. Но как же я найти следующую наименьший элемент? Это минус N 1 или N 2 действительно минус, от количества шагов. Так хорошо. Так что я п минус 2. Хорошо. Так, что чувствует себя немного лучше. Хорошо. Сколько шагов в следующий раз найти номер три? Таким N минус 4. Так что это снижение, на одну меньше наступать на каждой итерации. Так что это чувствовать себя лучше, не так ли? Если в прошлый раз это были примерно N раз N, на этот раз это N минус 1, плюс минус N 2, N плюс минус 3, плюс N минус 4, точка, точка, точка. Но если вы помните из вашей школе учебники, маленький обман лист на задней который имеет формулы, если Вы складываете этот числовой ряд, что общее количество шагов будет, что я беру здесь? Это одна из тех, вроде бы, N минус 1, N раз, деленной на 2. Итак, позвольте мне увидеть, если я могу вытащить до этого на мгновение. И опять же, я способ округления некоторых номера только, чтобы держать нашу жизнь просто, но насколько я помню, это то, что, если бы Я делаю N минус 1 вещи, то N минус 2, то N минус 3, это примерно что-то вроде этого более 2, и если я умножить это, вот и на самом деле N площади. Это чувствует себя не очень хорошо. N п над минус 2. Но вот в чем дело. В компьютерной науке, когда проблемы становится гораздо интереснее, когда п становится действительно большим. И когда N становится действительно большим, что из этих значений будет доминировать все от других? Это своего рода N в квадрате, не так ли? Да, деля на 2 довольно хорошо. Но если вы говорите о миллиардах частей данных, или триллионами частей данных, ОК, так Вы два раза быстрее. Но кто действительно заботится, если это большое число, Если этот фактор то, что получает больше и больше. И, конечно, он делает больше разницы, чем этот парень. Поэтому, даже если вы, ребята правы, Второй алгоритм, мы будем называть его выбор вида, т.е. в реальном мире потенциально немного быстрее, потому что я принимая все меньше и меньше шаги каждый раз. Это не так уж принципиально быстрее. Потому что, если мы играем это для больших значений п, в конце день, в течение достаточно большое N, она по-прежнему будет чувствовать себя довольно медленно. Ну, позвольте мне взять один последний проход на этом. Это то, что я бы назвал Выбор вида. Может вы, ребята сбросить себя в последний раз? И в этом последнем случае, я собираюсь предложить что-то называется сортировка вставками. Сортировка вставками бытия, концептуально, немного по-другому. Вместо того, чтобы идти вперед и назад и выбора наименьшего элемента, я только собираетесь иметь дело с каждым из этих парней, как я сталкиваюсь с ними, и вставьте их в нужные места. Так что я просто собираюсь начать с Грейс, и я вижу, что она номер четыре. Где номер четыре принадлежат? Я еще не начал сортировку ничего, так и благодать получает право остаться там. И теперь я собираюсь утверждать, если бы вы могли сделать шаг с правой, это мой отсортированный список, это моя несортированный список оставшихся. Так что теперь я собираюсь перейти к следующему, и то, что тебя зовут? BRANSON: Брэнсон. Дэвид Дж. МАЛАН: Брэнсон. Так Брэнсон номер два. Так что я собираюсь взять тебя за моментом. И теперь, где вы принадлежите в этом массиве? Таким образом, чтобы право благодати. Итак, еще раз, мы как бы делает Грейс сделать много работы здесь. Где мы ставим вас? Итак, мы собираемся, чтобы скользить вам слева, и вставьте Брэнсон там. Но сейчас я утверждаю, что вы, ребята, сделали. Но обратите внимание, что я не использую дополнительное пространство. Он по-прежнему 2 элемента Здесь 5 здесь. Общая площадь массива составляет 7, так что я не обман, все в порядке? Так что теперь у нас есть, с Гейб здесь, номер шесть, где вы принадлежите? Вы опять повезло. Таким образом, вы получите, чтобы остаться на месте. Просто возьмите небольшой шаг вправо просто дать понять, что вы сортируются. И теперь у нас есть Нил снова, число Один из них, куда вы идете? А теперь то, где мы начнем видеть, что Этот алгоритм, хотя на первый взгляд, чувствует себя довольно умным, смотреть то, что должно произойти. Если бы вы могли выйти вперед. Куда мы хотим поставить Нил? Так, очевидно, здесь, так как мы можем получить там Нил? Давайте сделаем это шаг за шагом. Гейб, куда вам нужно идти? Да, так возьмите один большой шаг, или две половины шаги, чтобы сделать на одну ступень выше там. Грейс, куда вы идете? Хорошо. Так что еще один шаг. И, наконец, Брэнсон? Еще один шаг. И теперь мы можем поставить на место Нил. Так что теперь, продолжать эту логику. Хотя мы и не перекладывая Нил снова, и снова, и снова, чтобы положить его , куда он идет, в худшем случае, Следующий номер мы могли бы столкнуться мог быть количество, например, было число нулю, то мы собираемся перенести все этих парней. Предположим, что есть числа, отрицательные единицу, то мы должны перейти Все эти парни. Так что мы действительно только отчасти листать Проблема вокруг, так, что мы за счет передачи из Процесс отбора так вставки Процесс, таким образом, что вы, ребята, только что двигаться примерно N минус что-то число шагов. И это число шагов будет только расти, как я выбираю несколько номеров, Если я должен продолжать толкать вас, ребята обратно, и обратно, и обратно. Так печально то сейчас все эти Алгоритмы п квадрат. Давайте пойдем дальше и благодаря этим парней, и визуализировать эти немного разному. Очень хорошо сделано. [Аплодисменты] Хорошо. Там вы идете. Спасибо за - BRANSON: [неразборчиво] держать номера. Дэвид Дж. МАЛАН: Нет, не можешь держать номера, а также. Хорошо. Красиво сделано. Хорошо. Итак, давайте посмотрим, если мы сейчас не можем суммировать более быстро и более визуально именно то, что только что произошло Здесь следующим образом. Я собираюсь идти вперед и подтянуть Firefox. Мы свяжем эту демонстрацию на сайте курса. Java немного раздражает, чтобы получить работу В некоторых браузерах эти дни. Так что если вы играете с этим в домашних условиях, понимаю, что вы, возможно, потребуется использовать Firefox чтобы заставить его работать. И то, что я собираюсь делать с этой демонстрации состоит в следующем. Внизу, у меня есть целая куча меню, включая время начала и Стоп. Кроме того, как в стороне, там, кажется, ошибка в этих программах, в котором вы не может реально увидеть запуска или остановки Кнопка если не удерживать Команда или Alt плюс и увеличить, которая с любопытством показывает вам больше кнопок. Так что просто FYI, если вы играете С этим у себя дома. Теперь я собираюсь, нажмите кнопку Пуск всего за момент, после указания задержки, как, 200 миллисекунд здесь, просто поэтому мы можем видеть, что происходит. Поэтому я утверждаю, что это визуализация первого алгоритма эти парни сделали, пузырьковая сортировка, в результате чего мы обменялись людей попарно. Ключевым моментом в этой визуализации является то, что высота баров представляет размер числом. Таким образом, выше бара, Чем больше число. Чем короче линия, чем меньше число. И если вы заметили, мы проходим первой итерации этого алгоритма, обмен большими и маленькими числами, так что Небольшое число стоит на первом месте и большого числа уходит вправо. И как только мы получаем в конец массива много больше номеров, чем семь, мы собираюсь вернуться к началу. И ожидаем, что это. На левой, что малыш собирается поменяться в сторону, и это процесс повторяется. Теперь этой визуализации быстро попадает скучно, так что позвольте мне идти вперед и остановиться его, изменить задержку нечто гораздо быстрее только, чтобы получить сейчас, почувствовать этого алгоритма. Так что, хотя я ускорил его, это модернизации как мой процессор, покупая новый компьютер. Я принципиально не изменилась моя алгоритм, но вы действительно можете увидеть больше ясно, чем с людьми, что большая Номера здесь бурлит до самого верха, и маленькими числами барботированием на дно. И теперь эта вещь здесь сортируются. И как в сторону, на площадях, есть просто некоторые бухгалтерские там поможет вам подсчитать, сколько сравнений, или сколько свопы на самом деле было сделано. Ну, давайте попробуем один из других мы видели. Позвольте мне нажмите на пузырьковой сортировки здесь, и позвольте мне выбирать, и вся эта веб-страница немного багги. Примем риска и запустить его снова. Там мы идем. Так давайте сделаем выбор рода. Я не знаю, почему меня появляется там. Давайте на увеличение, чтобы исправить это ошибка, измените это до 50. Ах, давайте на самом деле , что гораздо быстрее. Пять миллисекунд или около того, и начать. Так что это выбор рода. Итак, еще раз, подумайте о том, что мы сделали с людьми здесь. Мы прошли через массив и выбран наименьший элемент снова и снова и снова. Теперь я утверждаю, что был все еще довольно плохо. Это было все еще п квадрат, плюс-минус, но это было, в реальном мире, немного быстрее, потому что я действительно принимает немного меньше шагов каждый раз. Но мы говорим только то, что? Может быть, 40 или около бары здесь? Мы не говорим 40000000. Так что это не совсем ясно, что был действительно значительным усилением. Позвольте мне теперь вернуться назад и изменить нашему Третий алгоритм, который был выбрать сортировка вставками. И теперь это действительно детская коляска, потому что Меню действительно не должно быть там. Так что теперь мы будем прокручивать вернуться сюда и начать этот алгоритм. Возглас, запускать и останавливать. Так что это один вид имеет довольно узором к нему, в результате чего мы снова вставки людей или в этом случае в барах их соответствующее место. И это уже сделано до Я обернулся. Но этот, тоже, по идее, по-прежнему п квадрат. Итак, давайте посмотрим, если мы не можем подвести итог эти следующим образом. Я собираюсь идти вперед и только, чтобы дать нам вроде распространенный способ говорить об этих вещах, позвольте мне представиться просто немного обозначений здесь. Вы сейчас увидите то, что называется большим О, потому что это буквально большой О. И это таким образом, что компьютер ученый или математик даже использует , чтобы описать время работы некоторого алгоритма. Сколько шагов это на самом деле взять? Теперь я собираюсь опозориться с мой почерк здесь через минуту. Но позвольте мне пойти дальше и сказать, что это будет Big O здесь. И позвольте мне представить одного друга Символ, омега капитала. Omega будет противоположным, По сути, больших О. В то время как большая O средства, в худшем случае, сколько времени Могут ли некоторые алгоритма принимают в через п, омега собирается быть, сколько времени это может взять в лучшем случае. И мы увидим, что мы подразумеваем под лучшем случае через минуту. Итак, давайте начнем что-то простое. Позвольте мне начать с линейным поиском. Так что не сортировки. Мы называем это линейный поиск. И теперь, чтобы немного таблица из этого. И теперь, в случае линейного поиска, в худшем случае, сколько шагов он собирается предпринять, чтобы я нашел число произвольных выбор? И есть N Всего двери или н общего числа. Худшем случае. Сколько шагов я буду иметь, чтобы предпринять, чтобы найти число 50 в массив п дверями? И почему? Потому что это может быть все, перебросив на конце. Так много, как Дженнифер встречается, номер 50 был всю дорогу, так что в худшем случае линейного поиска большая O п, мы будем говорить. А в лучшем случае, Если вы получаете действительно повезло? Это просто будет сделать один шаг, или постоянное количество шагов. Таким образом, мы опишем, что 1. Так что это довольно хорошо. А что, если мы сделали что-то нравится бинарный поиск? Так бинарный поиск, в худшем случай, взял, сколько времени? [Промежуточное VOICES] Дэвид Дж. МАЛАН: Так на самом деле, я слышал его в паре мест. Так это на самом деле необходимо войти N, плюс-минус, потому что, как мы делим пополам список снова, и снова, и снова, мы можем найти, в конечном счете, значение Если она есть, но есть одна загвоздка. Что предположение, что мы должны само собой разумеющимся для бинарного поиска? Он должен быть отсортирован. Это не сортируются, вы можете разделить вещи в половине снова и снова, и вы может пойти налево, и вы можете пойти прямо, а Вы можете пойти с обеих сторон, но вы Не собираюсь найти элемент, если список не отсортирован, так как Вы могли бы пропустить его. Потому что ваш эвристические, для того, левая или вправо собирается быть недостатки, если это действительно не отсортированы. Таким образом, есть своего рода скрытые расходы чтобы использовать что-то вроде этого. Теперь давайте перейдем в сортировке Алгоритмы не ищет - О, на самом деле пойдут в это поле пустым. Двоичный поиск в лучшем случае? Это также 1, если он просто бывает в самом центре массива, или середине телефонной книги. Теперь давайте сделаем пузырьковой сортировки. Итак, еще раз, теперь мы входим в родов, не поиск. В худшем случае, сколько шагов мы сделали Сортировать претензии пузыря собирается взять? N в квадрат. Так что я собираюсь сделать это. Ох, мой почерк выглядит еще хуже когда он прогнозирует, что большие. Хорошо. Так что это п квадрат. И в лучшем случае пузырьковой сортировки, сколько шагов он собирается предпринять? 1, я слышал. Выступающий 1: N. Дэвид Дж. МАЛАН: N, я слышал. Выступающий 1: 2. Дэвид Дж. МАЛАН: 2, я слышал. Я слышу 3? Хорошо. Я слышал об этом 1, N, 2, но давайте выберем кроме по меньшей мере первой из этих предложения, 1. Это не плохо инстинкт, потому что она вид соответствует модели здесь. Но если это займет всего 1 шаг, как в мира я мог утверждать, что список сортируется, потому что, если я только позволил принимать по 1 шагу, сколько элементов я могу на самом деле проверить, чтобы убедиться? Ну, всего в 1, которая означает, что есть N минус 1 элементов, которые могут быть из порядке, а я только собираюсь на веру после глядя на 1 элемент, который вещи отсортированы. Таким образом, 1 не правильно здесь. Таким образом, минимально, сколько я должен смотреть? [Промежуточное VOICES] Дэвид Дж. МАЛАН: N минус 1, или на самом деле, N, потому что мне нужно смотреть на каждую Элемент чтобы убедиться, что это не вышел из строя. Но опять же, мы разберемся с нашими волновых руки в меньших количествах и Предположим, что при п становится большим, они неинтересных в любом случае. Так вот пузырьковой сортировки. А теперь, давайте сделаем эти два последних. Выбор вида, и тогда мы будем сделать сортировку вставками. И тогда мы будет ударом сознании с чем-то гораздо лучше, чем все из них. Хорошо. Что такое худшем случае работает момент выбора вида? Выступающий 4: N в квадрате. Дэвид Дж. МАЛАН: N площади, я слышу. Но почему N в квадрате, интуитивно? Выступающий 4: Потому что мы просто сделали это. Дэвид Дж. МАЛАН: Потому что мы просто сделали это. ОК. Хороший ответ. Но интуитивно, почему выбор Сортировать N квадратов? Что мы должны сделать, снова и снова? Мы должны были держать сканирования за счет, являются Вы самый маленький, вы наименьшая, ты наименьшим. И эксплуатацию, мы смогли взять п действия, а затем N минус 1, то п минус 2. Но если вы вроде добавить эти итоги, или взять его на веру, что я добавил их заранее, мы получаем примерно N квадрата за вычетом некоторых меньшем количестве. Так что я буду называть это N квадрате. Но с выбором рода в лучших случае, сколько шагов он собирается взять меня? SPEAKER 5: [неразборчиво] Дэвид Дж. МАЛАН: Это, к сожалению еще N в квадрате, не так ли? Потому что, если я выбираю наименьшее элементом, и у нас было семь человек здесь, Я знаю только, как только я доберусь до очень кончилось тем, что я нашел наименьшую числа, где бы он или она могла быть. Но как мне найти следующий Наименьшее число? Я должен сделать еще один проход. Таким образом, в лучшем случае, то, что вход выбора вида? Это уже список сортировки, номер один, номер два, номер три, номер четыре. Но я компьютер. Я могу только смотреть друг на вещь за один раз. Я не могу сортировать сделать шаг назад, как человеку и сказать: ох, это выглядит правильным. Я могу только выносить решения в правильности критериям Сортировать по выбору Наименьшее число. Но даже если я найду номер один первый, Если я не знаю, что еще насчет другие номера, которые я не делаю, все, что я знаю, что я был передан массив или набор двери, за которыми являются номера, только так я знаю, что один был самым маленьким? Если я получаю весь этот путь и понять, Блин, один был действительно наименьшим. Но как же я тогда определить, что два является следующим наименьшим? Делая то же неэффективности снова и снова. Итак, наконец, с сортировки вставкой, как, в худшем случае, мы сказали он выполняет? Это тоже п квадрат. А как насчет с лучшем случае? Мы оставим это в качестве захватывающим. Мы заполнить этот пустой следующий раз, Но сначала я предлагаю, чтобы мы принципиально лучше, чем Все они, все в порядке? Так что думайте сами, что вставка Сортировка будет. Ну, это было не очень драматические, потому что я только один что увидели изменения. Ничего себе. ОК. Так что здесь у нас есть несколько различные демонстрации. Если ли увеличить здесь, вы увидите, что за Слева мы должны пузырьковой сортировки, в среднего у нас есть выбор рода, а на крайне правых, у нас есть то, что мы не смотрел на еще называется сортировка слиянием. Но представьте, что мы были здесь делаю до сих пор сегодня. Когда Дженнифер впервые вышел на сцену, мы пошли через массив чисел снова, и снова, с линейным поиском, и мы получили линейное время работы, Big O п, так сказать. Когда мы рассмотрим первую неделю классе, когда мы разделяй и властвуй, и у нас была телефонная книга слезотечение, и Дженнифер, и мы все вместе использовала, что ключевое понимание, которое должно было повторяться снова и снова как-то выбрасывать, выбрасывать, выбрасывать, половина проблемы, или как правило, разделив проблемой в два раза, и затем обработкой небольшой кусок проблемы, как концептуально эквивалентные с другой стороны, мы как-то делали принципиально лучше. Но с пузырьковой сортировки, с выбором сортировка, сортировка вставками с, у нас может Нет такой идеи, которые Дженнифер сделала. Мы в значительной степени просто ходил взад и вперед целую кучу раз, и мы оптимальной вещи немного, обменивая в этом порядке, может быть вставки или выделения. Но в конце концов, я сделал много неловко ходить взад и вперед. Нам действительно не что-то рычаги умный, как Дженнифер сделал, как деление и завоевание. Таким образом, сортировка слиянием, наоборот, которую мы не увидим до следующей недели, это будет использовать, что ключевой идеей путем деления вход, а затем наполовину, а затем вдвое, а затем вдвое. И на каждой итерации этого цикла, сортировка левой половине, а также право пополам, то левая половина левой половине, и правую половину левой, а затем левая половина правая половина, и правой половине правой половине. И повторяет снова и снова. Таким образом, вы увидите, что это визуально, но это это то, что нас ждет на следующей неделе. И вообще, когда мы думаем, мало немного сложнее, на любой такой проблеме. Мы п квадрат слева, п квадрат в середине, и N н войти справа. Так что ваши реальные захватывающим. Увидимся в понедельник. [Аплодисменты]