[Музыка Воспроизведение] DAVID МАЛАН: Хорошо. Ладно, с возвращением. Так что это 4-я неделя, начало его, уже. И вы помните, что на прошлой неделе, мы ставим код отведенных для только немного и мы начали говорить немного больше высоком уровне, о таких вещах поиск и сортировка, которая хотя и несколько простых идей, являются представитель класса задач Вы начнете решать особенно как вы начинаете думать об окончательном проекты и интересные решения, которые вы возможно, придется реальных проблем. Теперь пузырьковой сортировки был одним из самых простых такие алгоритмы, и это работал при наличии этих небольших количествах в виде списка или в виде массива Пузырь их путь к вершине, и большие числа переместить свой путь к К концу этого списка. 

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

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

Таким N квадрате. И то, что было N? 

АУДИТОРИЯ: число элементов. 

DAVID МАЛАН: Так было N число элементов. И поэтому мы будем делать это часто. Каждый раз, когда мы хотим говорить о размерах проблема или размер вход, или количество времени, необходимое для получения выходных, мы просто обобщенной все вход как н. Итак, вернемся к неделе 0, количество страниц В телефонной книге была N. Количество студентов в комнате с. Так и здесь, мы следуем этой модели. 

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

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

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

Таким образом, эти темы возникают в реальном мире. Всего несколько лет назад, когда определенные Сенатор был баллотироваться на пост президента, Эрик Шмидт, в то время генеральный директор Google, на самом деле имели возможность взять у него интервью. И мы подумали, что мы разделим эту YouTube Зажим для вас здесь, если бы мы могли повернуть вверх громкости. 

[ВОСПРОИЗВЕДЕНИЕ ВИДЕО] 

-Теперь, сенатор, вы здесь, в Google, и мне нравится думать президентства как собеседование. 

[Смеется] 

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

[Смеется] -Вы, ребята, думаете, я шучу? Это прямо здесь. Что является наиболее эффективным способом сортировать миллион двести-разрядных целых чисел? 

[Смеется] 

-Ну, ну - 

-Прости. Может быть, мы должны - 

-Нет, нет, нет, нет, нет. 

-Это не - ОК. 

-Я думаю, что пузырьковая сортировка бы быть неправильный путь. 

[Смеется] 

[ПРИВЕТСТВИЕ И аплодисменты] 

-Давай, который сказал ему это? ОК. 

[КОНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] 

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

Мы думали об этом является верхней границей. Так Big O п квадрат означает, что в худшем случае, что-то вроде Выбор рода возьмет п квадрат шагов. Или что-то вроде сортировки вставками бы квадрат N шагов. Теперь за то, как вставки , смотрите, какое было в худшем случае? Дан массив, что самое худшее возможные сценарии, которые могут оказаться окажетесь перед? 

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

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

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

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

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

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

Так просто, чтобы резюмировать, то, Big O п квадрат, мы видели несколько таких алгоритмов до сих пор. Big O п? Что алгоритм, способный назвать Big O п? В худшем случае, она занимает линейный число шагов. 

Хорошо, линейный поиск. А в худшем случае, когда это элемент, который вы ищете, когда применении линейного поиска? 

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

Ну, Big O журнала н. Мы не говорили очень подробно о это, но мы видели это раньше. Что работает в так называемый логарифмический времени, в худшем случае? 

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

Big O 1. Возможно, мы можем Big O 2, Big O 3. В любое время вы хотите просто постоянное число, мы просто вроде просто упростить что Big O 1. Хотя, если реально, она занимает 2 или даже 100 шагов, если это постоянное число шагов мы просто скажем Big O 1. Что это алгоритм В Big O 1? 

АУДИТОРИЯ: Определение длины переменной. 

DAVID МАЛАН: Поиск Длина переменной? 

АУДИТОРИЯ: Нет, длина если он уже отсортирован. 

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

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

АУДИТОРИЯ: [неразборчиво]. 

DAVID МАЛАН: Да. Так что это зависит от нашей точки зрения. Если мы на самом деле думаем о входе Е как строки, а Поэтому мы измеряем размер этого Ввод его длина - поэтому назовем что длины N, а также - Можно утверждать, что Е является самой большой O п потому что он собирается предпринять шаги вы н распечатать каждую из этих N символов, скорее всего. По крайней мере, в той степени, что мы предполагаем что, возможно, он использует для петли под капотом. 

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

Так что о омега N квадратов? То, что было алгоритм, в лучшем случае, все еще взял квадрат N шагов? Да? 

АУДИТОРИЯ: [неразборчиво]. 

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

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

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

Этот, наконец, омега N § п. Таким N журнал N, нам действительно не говорить о пока нет, но - 

АУДИТОРИЯ: Сортировка слиянием? 

DAVID МАЛАН: сортировка слиянием. Это было захватывающим последнего времени, где мы предложили, и мы показали визуально, то есть алгоритмы. И сортировка слиянием только одного такого Алгоритм, который принципиально быстрее чем некоторые из этих других парней. В самом деле, слияние короткий не только в лучшем случае N журнал N, в худшем Случай п § п. И когда у вас есть это совпадение Омега и Big O является одно и то же? Мы можем реально описать это как то, что называются тета, хотя это немного реже. Но это просто означает, что два прыжка В этом случае те же самые. 

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

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

Сортировка слиянием, заметьте, делается. Кучи сортировки, быстрой сортировки, Shell - так что кажется, мы ввели три худших алгоритмов на прошлой неделе. Но это хорошо, что мы сегодня здесь, чтобы посмотреть на сортировки слиянием, которое является одним из более легкие, чтобы смотреть на, даже хотя она, вероятно, будет изгибаться ваш ум только немного. Здесь мы можем видеть, как много Выбор рода сосет. 

Но, с другой стороны, это действительно легко осуществить. И может быть, для P набор 3, это одна из Алгоритмы вы решили реализовать для стандартного издания. Прекрасно подходит, совершенно правильно. 

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

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

Так на входе из п элементов - так, чтобы просто означает, вот массив. У этого есть N вещи в нем. Это все, что мы говорим, что там. 

Если N меньше 2, вернуться. Так что это просто тривиальный случай. Если N меньше 2, то, очевидно, это 1 или 0, в этом случае вещь уже отсортирован или несуществующие, так что просто вернуться. Там нет ничего, чтобы сделать. Так что это простой случай, чтобы обрывать. 

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

АУДИТОРИЯ: [неразборчиво]. 

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

Но подождите минуту. Когда вы сказали, чтобы отсортировать Левая половина, какие две шагов будет дальше? Мы разберемся с левой половины Левая половина и право половина левой половины. Блин, как мне отсортировать эти два половины и четверти, в настоящее время? 

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

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

[Смеется] 

DAVID МАЛАН: Если бы мы могли принять восемь добровольцев, и давайте посмотрим, если мы можем играть в эту, таким образом. Ничего себе, ОК. Информатика становится весело. Хорошо. Так, как вы трое крупнейших руку там. Четыре в спину. А как насчет сделаем Вам три в этом ряду? И четыре в передней части. Таким образом, вы восемь, поднимайся. 

[Смеется] 

DAVID МАЛАН: Я на самом деле не уверен, что это такое. Это стресс шаров? Настольные лампы? Материал? В интернете? 

ОК. Так что приезжайте и выше. Кто хотел - продолжают поступать. Давайте посмотрим. И это ставит вас в месте - Вы находитесь в одном расположения. Ой, подожди минутку. 1, 2, 3, 4, 5, 6, 7 - о, хорошо. Хорошо, что мы хороши. Ладно, у всех есть место, но не на стекле Google. Позвольте мне в очередь эти вверх. Как тебя зовут? 

МИШЕЛЬ: Мишель. 

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

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

МИШЕЛЬ: О, это так странно. 

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

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

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

Так что, если вы, ребята, могли бы просто поднимите номера, чтобы мы могли видеть, что Вы Действительно соответствующий 4, 2, 6, 1, 3, 7, 8. Отлично. Так что я собираюсь попробовать, чтобы организовать вещи, если вы, ребята, можете просто следуй за мной здесь. 

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

АУДИТОРИЯ: Сортировать левую половину. 

DAVID МАЛАН: Так что теперь у меня есть, чтобы разобраться Левая половина этих парней. Потому что опять же, предположим, к себе Цель состоит в сортировке левую половину. Как вы это сделали? Просто следуйте инструкциям, даже хотя мы делаем это снова. Так отсортировать левую половину. Теперь я сортировку этих двух парней. Что будет дальше? 

АУДИТОРИЯ: Сортировать левую половину. 

DAVID МАЛАН: Сортировать левую половину. Так что теперь это, это место здесь, приведен список размер 1. И то, что тебя зовут? 

PRINCESS DAISY: Принцесса Дейзи. 

DAVID МАЛАН: Принцесса Дэйзи здесь. И вот она уже отсортирован, так как Список имеет размер 1. Что мне делать следующий? OK, вернуться, потому что список из размер 1, который составляет менее 2. Тогда в чем же следующий шаг? И теперь вы должны вид возвратиться в вашем уме. 

Сортировать правая половина, которая - Как тебя зовут? 

ЛИНДА: Линда. 

DAVID МАЛАН: Линда. И так, что же нам теперь делать, что у нас есть список размером 1? 

АУДИТОРИЯ: Возвращение. 

DAVID МАЛАН: Осторожно. Вернемся первой, и теперь третий Шаг - и если я как бы изобразить его охватывает два места, теперь я необходимо объединить эти два элемента. Так что теперь, к сожалению, элементы вышли из строя. Но на этом процесс объединения начинает становиться убедительными. 

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

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

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

АУДИТОРИЯ: Правая половина. 

DAVID МАЛАН: Сортировать правую половину. Таким образом, вы, ребята, должны сделать это, а также. Так что если вы могли встать на мгновение? А как тебя зовут? 

Джесси: Джесс. 

DAVID МАЛАН: Джесс. Итак, Джесс Теперь левая половину правой половины. И так она список Размер 1. Она, очевидно, сортируют. И ваше имя? 

МИШЕЛЬ: Мишель. 

DAVID МАЛАН: Мишель, очевидно, Перечень размер 1. Она уже отсортирован. Так что теперь происходит волшебство, Процесс слияния. Так что, кто собирается придти прежде? Очевидно Мишель. Так что, если вы могли бы приходить обратно. Пространстве мы имеем в наличии для нее теперь Прямо за это кресло здесь. И теперь, если вы могли бы вернуться, а также, у нас теперь есть, чтобы быть ясным, два половин, каждая из размер 2 - и просто ради изображением автора, если Вы могли бы сделать немного пространства - одной левой половине, по одному Правая половина здесь. 

Перемотка дальше в историю. Какой шаг будет следующим? 

АУДИТОРИЯ: Merge. 

DAVID МАЛАН: Так что теперь у нас есть для слияния. Так хорошо, так что теперь, к счастью, мы просто освободил четырьмя стульями. Таким образом, мы использовали два раза больше памяти, но мы можем дать флип-флопе между два массива. Так, число которых на первом месте? Так Мишель, это очевидно. Так приходят и принимают ваше место здесь. А потом номер 2, очевидно, Далее, так что вы пришли сюда. Номер 4, номер 6. И снова, несмотря на то, что есть немного пешеходных прогулок вовлеченного, действительно, это может произойти мгновенно, путем перемещения одного - Хорошо, хорошо играл. 

[Смеется] 

DAVID МАЛАН: А теперь мы в довольно хорошей форме. Левая половина всего входного теперь сортируются. Ладно, эти парни были Преимущество моей - как она в конечном итоге все девушки на налево и все мальчики справа? 

Хорошо, таким образом парней очередь. Поэтому я не буду идти Вы через эти шаги. Мы увидим, если мы можем повторно же псевдокод. Если вы хотите идти вперед и встать, и вы, ребята, позвольте мне дать вам микрофон. Смотрите, если вы не можете повторить то, что мы только что сделали здесь, на Другой конец списка. Кто должен говорить первым, основанный на алгоритме? Так объясните, что вы делаете, прежде Вы делаете любой ноге движений. 

Выступающий 1: Ну, хорошо, так как Я левой половины Левая половина, я вернусь. Верно? 

DAVID МАЛАН: Хорошо. 

Выступающий 1: А потом - 

DAVID МАЛАН: кто MIC перейти к следующему? 

Выступающий 1: Следующий номер. 

Докладчик 2: Так что я правая половина левой половины левая половина, и я вернусь. 

DAVID МАЛАН: Хорошо. Вы вернетесь. Так что теперь каков следующий за вами двумя? 

Докладчик 2: Мы хотим видеть, кто меньше. 

DAVID МАЛАН: Совершенно верно. Мы хотим объединить. Пространство мы собираемся использовать для слияния Вас в, даже если они Очевидно, уже отсортированы, мы собираемся пойти по тому же алгоритму. Так кто идет в спине в первую очередь? Таким 3, а затем 7. А теперь идет микрофон с этими парнями, хорошо? 

Выступающий 3: Так что я правую половину левую половину, и мой N меньше 1, так что я просто хочу, чтобы пройти - 

DAVID МАЛАН: Хорошо. 

Выступающий 4: Я правая половина Правая половина правая половина, и я Также один человек, так что я собирается вернуться. Так что теперь мы сливаемся. 

Выступающий 3: Итак, мы возвращаемся. 

DAVID МАЛАН: Так вы идете в заднюю часть. Так 5 идет в первую очередь, то 8. А теперь аудитории, который является шага нам нужно теперь перемотать вернуться к в нашем сознании? 

АУДИТОРИЯ: Merge. 

DAVID МАЛАН: объединение левой и правой половины половину первоначальной левую половину. Так что теперь - и просто, чтобы было понятнее, сделать немного пространства между вами двумя парнями. Так что теперь это два списка, слева и справа. Так как же нам теперь слияние, вы парни в первый ряд мест снова? 

3 идет в первую очередь. 5 Тогда, очевидно. Затем 7, и теперь 8. ОК, а теперь мы? 

АУДИТОРИЯ: не делается. 

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

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

Так мы одели Мишель здесь. И кто имеет номер 2? Номер 2 приходит на спине, а также. Номер 3? Отлично. Номер 4, № 5, № 6, № 7, и № 8. 

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

Выступающий 1: Будет ли войти п нарушение нас на две части - деления на два, по существу. 

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

Теперь то, что о русских? Я вижу, что мы как бы разделило вас Ребята - разделило вас, разделило вас, разделило вас, разделенный вас. Где конце концов пришли? 

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

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

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

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

Настолько большие аплодисменты, если Мы могли бы, этих парней. 

[Аплодисменты] 

DAVID МАЛАН: И ваши подарки Расставание - Вы можете сохранить номера, Если вы хотели бы. И ваш прощальный подарок, как обычно. О, и мы вышлем Вам кадры, Мишель. Спасибо. Хорошо. Помочь себе стресс мяч. 

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

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

[ВОСПРОИЗВЕДЕНИЕ ВИДЕО] 

-Вот и все на первом шаге. Для второго шага, неоднократно объединяет пару списков. 

DAVID МАЛАН: Хм. Только звук идет из моего компьютера. Давайте попробуем еще раз. 

-Просто произвольно выбрать, какой - теперь у нас есть четыре списка. Узнать раньше. 

DAVID МАЛАН: Там мы идем. 

Слияние-108 и 15, мы в конце с списке 15, 108. Слияние 50 и 4, мы в конечном итоге с 4, 50. Слияние 8 и 42, мы в конечном итоге с 8, 42. И слияние 23 и 16, мы в конечном итоге с 16, 23. 

Теперь все наши списки размера 2. Следует отметить, что каждый из четыре списка отсортированы. Так мы можем начать слияние пар списки. Слияние 15 и 108, 4 и 50, мы сначала взять 4, то 15, то 50, то 108. Слияние 8, 42 и 16, 23, мы сначала 8, то 16, то 23, то 42. 

Так что теперь у нас есть только два списка размер 4, каждый из которых сортируют. Так что теперь мы объединить эти два списка. Во-первых, мы берем 4, то возьмем 8, то мы берем 15, то 16, то 23, то 42, то 50, то 108. 

[КОНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] 

DAVID не МАЛАН: Опять же, заметьте, он никогда коснулся данной чашки более одного раза после роста за его пределами. Так он никогда не повторяется. Значит, он всегда движется в сторону, а вот где мы получили нашу н. 

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

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

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

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

Это сортировку вставками. 

[TONES композиция] 

DAVID МАЛАН: Это снова пытается вставить каждый элемент в которой она принадлежит. Это пузырьковой сортировки. 

[TONES композиция] 

DAVID МАЛАН: И вы можете сортировать, чувство как относительно мало работать, что он делает на каждом шаге. Это то, что звучит как занудство. 

[TONES композиция] 

DAVID МАЛАН: Это выбор рода, где мы выбираем элемент, который мы формируем проходя снова и снова и снова и положить его в самом начале. 

[TONES композиция] 

DAVID МАЛАН: Это сортировки слиянием, которое Вы можете действительно начинаешь чувствовать. 

[TONES композиция] 

[Смеется] 

DAVID МАЛАН: То, что называется GNOME сортировка, которую мы не смотрели. 

[TONES композиция] 

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

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

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

Ну, это довольно легко измерить это. Если N меньше 2, время, затрачиваемое В сортировку N элементов, где п равно 2, 0. Потому что мы просто возвращаем. Там нет работы, которую предстоит сделать. Теперь, возможно, может быть, это один шаг или два шаги, чтобы выяснить количество работать, но это достаточно близко к 0, что Я просто хочу сказать, нет работы требуется, если список настолько мала быть неинтересным. 

Но этот случай интересен. Рекурсивные случай был филиал псевдокод, сказал еще, отсортируйте левая половина, сортировать право половину, объединить две половины. Теперь почему это выражение заявляете, что счет? Ну, T п просто означает, что время, чтобы разобраться N элементов. А затем на правой стороне Знак равенства там, T п разделенный 2 Имеется в виду стоимость того, что? Сортировка левую половину. Другой T п деленное на 2 предположительно со ссылкой на стоимость сортировать правую половину. 

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

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

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

Но опять же, этого недостаточно. Мы должны погрузиться в более глубоких. Это означает, что мы должны ответить вопрос, что такое Т 8? Ну Т 8 находится всего в 2 раз T 4 плюс 8. Ну, что Т 4? Т 4 находится всего в 2 раза Т 2 плюс 4. Ну, что Т 2? Т 2 находится всего в 2 раза Т 1 плюс 2. 

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

Если Т 1 0, теперь я могу вернуться до одного линии Вот этот парень, и я могу подключите 0 для T 1. Значит, она равна нулю 2 раза, иначе известный как 0, а также 2. И так, чтобы все выражение 2. 

Теперь, если я беру Т 2, ответ на 2, подключить его к средней линии, T 4, то это дает мне 2 раза 2 плюс 4, поэтому 8. Если я после этого подключить 8 к предыдущему линии, что дает мне 2 раза 8, 16. И если мы будем продолжать то, что с 24, добавив в 16, мы, наконец, получить значение 64. 

Теперь, когда само по себе говорит рода Ничего обозначение N, Big O, омега, которые мы говорили. Но оказывается, что на самом деле 64 16, размер входного логарифм по основанию 2 из 16. И если это немного незнакомым, просто вспоминаю, и вернусь Вам в конце концов. Если это логарифм по основанию 2, это как 2 возведенное в то, что дает вам 16? О, это 4, так что это 16 раз 4. 

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

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

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

[Смеется] [Смех] DAVID МАЛАН: плохая шутка постепенно распространяется. [Смеется] DAVID МАЛАН: На всякий случай, что она есть. Я не записать это неправильно, и есть шутка. Хорошо. Объясните это люди рядом с вами, если Это не совсем нажата только пока. Но рекурсии, в целом, относится в процессе вызова функции себе, или в более общем, разделив Проблема в то, что может быть решить по частям решения идентичных Представитель проблем. 

Ну, давайте передач изменения на мгновение. Мы бы закончить на определенных кульминаций, так что давайте начнем устанавливать этап, в течение нескольких минут на очень простой идее - перекачки, что два элемента, не так ли? Все эти алгоритмы мы были Говоря о последних нескольких Лекции включают некоторые рода замены. Сегодня было визуализировали их получения вверх из своего стула и ходят, но в коде, мы бы просто взять элемент из одного массива и вставить его в другой. 

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

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

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

Во-первых, быстро включать стандартные io.h, а также включать в себя, cs50.h. А потом я собираюсь идти вперед и объявить недействительным тап_п в обычном порядке. Я понял, я неверно названы файл, так что позвольте мне добавить. C расширением вот так что мы можем скомпилировать его должным образом. Начать эту функцию. 

А функция Я хочу написать, довольно Проще говоря, это тот, который спрашивает пользователя число, а затем складывает все числа между этим числа и, скажем, 0. Итак, сначала я собираюсь идти вперед и объявить Int N. Затем я копирую код, который мы использовали на некоторое время. Хотя кое-что верно. Я вернусь к этому чуть позже. 

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

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

Короче говоря, я получаю и Int от пользователя. Я могу гарантировать, что это положительно. Я объявляю переменную ответ целого типа и хранить в его возвращение Значение сигма, передавая N качестве входных данных. И тогда я распечатать, что ответить. 

К сожалению, хотя сигма звучит как нечто, что может быть в math.h файла, его декларации, это на самом деле нет. Так что это нормально. Можно реализовать это сам. Я собираюсь реализовать функцию называют Sigma, и он собирается взять параметра - Давайте просто называть это м, всего так все по-другому. А потом здесь, я собираюсь сказать, Ну, если м меньше 1 - это очень неинтересные программы. Так что я собираюсь идти вперед и немедленно вернуть 0. Это просто не имеет смысла сложить все числа от 1 м, если м само 0 или отрицательным. 

А потом я собираюсь идти вперед и делать это очень итеративно. Я собираюсь делать такого рода старой школы, и я собираюсь идти вперед и сказать, что я собираюсь объявить сумму равным 0. Тогда я буду иметь для петли Int - и позвольте мне сделать это в соответствии с нашими Распределение кода, поэтому у вас есть копия дома. INT I получает 1 на до я меньше или равна м. Я плюс плюс. И тогда внутри этого цикла - мы почти на месте - сумма попадает сумма плюс 1. А потом я собираюсь вернуть сумму. 

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

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

И теперь я начинаю переходить от Я равно 1 все, вплоть до и включая м, потому что я хочу, чтобы включить все числа от одного до М включительно. А внутри этого цикла, я просто Сумма получает то, что он есть сейчас, плюс Значение я. Кроме того значение я. 

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

К сожалению, эта кода Не собираетесь компилировать еще. Если я запускаю сделать сигма 0, как же я Я собираюсь получить кричал на? Как это будет, не нравится? 

АУДИТОРИЯ: [неразборчиво]. 

DAVID МАЛАН: Да, я не объявлял Функция наверху, не так ли? C отчасти глупо, тем, что он только делает то, что вы скажете ей сделать, и вы должны сделать это в таком порядке. И поэтому, если я ударил Введите здесь, я собираюсь получить предупреждение о Sigma неявной декларации. 

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

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

Я могу сделать что-то большее - 50, 12, 75. Так же, как касательной, я собираюсь сделать что-то смешное, как действительно большой число, О, это фактически удалось - Эх, я не думаю, что это правильно. Давайте посмотрим. Давайте уж возиться с ним. 

Это проблема. Что происходит? Кода не так уж плохо. Он по-прежнему линейно. Свист является хорошим эффектом, однако. Что происходит? 

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

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

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

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

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

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

Остальное - заметить, что я собираюсь делать. Остальное я собираюсь вернуться м плюс - что сигма-м? Ну, сигма-м плюс минус 1 м, м плюс минус 2, плюс минус 3 м. Я не хочу писать все это. Почему бы мне просто не плоскодонки? Рекурсивный называю себя со слегка меньшая проблема, точку с запятой и назовите его день? 

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

АУДИТОРИЯ: [неразборчиво]. 

Дэвид МАЛАН: от 23 до 26, которые Если мое состояние. Потому что приятно об вычитание здесь, потому что я держу вручать сигма меньше проблем меньше проблемы, меньше - это не в два раза меньше. Это всего лишь шаг ребенка меньше, но это нормально. Потому что в конечном итоге, мы будем работать наш путь вниз к 1 или 0. И как только мы поразили 0, Sigma не собираюсь называть себя больше. Это собирается немедленно вернуть 0. 

Таким образом, эффект, если вы рода Ветер этом в своем уме, является добавление м плюс м минус 1, плюс минус 2 м, м плюс минус 3, а также точка, точка, точка, М минус м, в конечном итоге дает вам 0, а эффект в конечном счете, чтобы добавить все эти вещи вместе. Так что мы не имеем с рекурсией, решена проблема, которую мы не могли решить раньше. Действительно, версия 0 об этом, и каждый Проблема на сегодняшний день, были разрешимы только с использованием для петли или в то время как петли или аналогичных конструкций. 

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

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

Так что это глупая маленькая программа, которая Я на скорую руку, что утверждает, что делать следующем. В основном, это сначала заявляет десятичного называются X и присваивает его значение 1. Тогда он объявляет Целочисленное Y и присваивает ей значение 2. Затем он выдает какие х и у. Тогда он говорит, замена, точка точка точка. 

Затем он утверждает, что вызов функции называется своп, переходя в X и у, идея которого в том, что, мы надеемся, х и у вернется другой, противоположный. Тогда утверждают поменялись местами! с восклицательным знаком. Тогда она выводит х и у. 

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

Но я утверждаю, что когда я запускаю эту кода, как я сделаю сейчас - Позвольте мне идти вперед и вставьте его здесь. Я буду называть эту noswap.c. И как следует из названия, это не будет правильной программе. Не делайте noswap. / нет подкачки. X = 1, Y = 2, замена, поменяться местами. х равен 1, у равен 2. Это в корне неправильно, даже хотя это кажется совершенно разумным мне. И есть причины, но мы не собираемся выявить причину только пока. 

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

К сожалению, я думаю, что мои инструкции не было, на сегодняшний день, очень ясно, так что Я вернулся в эти выходные и обновляется В спецификации больше, смелее текст объясните пули, как эти. И просто сказать, что это более открыто, путем умолчанию, наборы проблемы обусловлены четверг в полдень, в учебную программу. Если вы начинаете рано, завершающая часть вопрос, поставленный среду в 12:00 PM, часть, которая относится к купон код, идея в том, что вы можете расширить Вашей срок P не установлена ​​до пятницы. То есть, откусила крошечный часть р установлено относительно того, что обычно является более серьезная проблема, и вы покупаете себе дополнительный день. Опять же, он получает вас думать о Поставленная задача, получает вас к Часы работы раньше. Но проблема скидочный купон по-прежнему требуется, даже если вы ничего не пишите. 

Но еще более убедительно это. (Шепотом) А тех людей, оставляя рано собираются пожалеете. Как те люди, на балконе. Прошу прощения заранее, чтобы люди на балкон по причинам, которые будут очистить через минуту. 

Так что нам повезло иметь один из CS50 бывший глава обучения стипендиатов Компания под названием dropbox.com. Они очень щедро пожертвовал скидочный купон здесь для этого много места, который по сравнению с обычная 2 гигабайта. Так что то, что я думал, что мы могли бы сделать на этом Последнее замечание сделать немного поддавки, при этом в какое-то мгновение мы раскроем победитель и кто имеет купон кодов, которые можно затем перейти к их Веб-сайт, введите его в, и вуаля, получить намного больше пространства Dropbox для вашего прибор и для ваших личных файлов. 

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

[ВОСПРОИЗВЕДЕНИЕ ВИДЕО] 

-Раз, два, три. 

[Крики] 

-Вы получаете автомобиль! Вы получаете автомобиль! 

DAVID МАЛАН: Мы увидим Вы в среду. 

-Вы получаете автомобиль! Вы получаете автомобиль! Вы получаете автомобиль! Вы получаете автомобиль! Вы получаете автомобиль! 

DAVID МАЛАН: Балкон люди, приходите здесь на передний план, где у нас есть дополнительные услуги. 

-Каждый получает автомобиль! Каждый получает автомобиль! 

[КОНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] 

Рассказчик: На следующей CS50 - 

SPEAKER 5: О боже мой Гоша Гоша Гоша Гоша Гоша Гоша Гоша Гоша Гоша - 

[Ukelele ИГРЫ]