[Играет музыка] ПРОФЕССОР: Все правильно. Это CS50, и это конец недели три. Так что мы здесь сегодня, а не в Сандерс Театр, вместо этого в Weidner библиотеки. Внутри которого является студия известный как Hauser Studio, или, скажем, студия H, или должны мы say-- если вам понравилось, что шутка, это на самом деле от одноклассник, Марк, онлайн, который предложил столько с помощью Twitter. Теперь то, что это круто о будучи здесь в студии является то, что я окружен эти зеленые стены, зеленый экран или цветности, так сказать, что означает, что CS50-х Производство команда, без моего ведома Прямо сейчас, может быть положить меня больше нигде в мире, лучше или хуже. Теперь то, что лежит впереди, установить проблема двух в ваших руках в течение этой недели, но с проблемой установить три на следующей неделе, Вы будете вызов с так называемый игра 15, старый вечере, что Вы могли бы вспомнить приема как ребенок, который имеет целый букет чисел, которые могут скользить вверх, вниз, слева и справа, и есть один пробел в головоломки, в которую вы может на самом деле эти слайд кусочки головоломки. В конечном итоге вы получите это письмо головоломка, в какой-то полу случайном порядке, и цель заключается в сортировать его, сверху донизу, слева направо, от одного весь путь через 15. К сожалению, реализация вы будете иметь под рукой будет обеспечение на основе, не физически. Вы на самом деле придется написать Код, с которой студент или пользователь может, играть в игру 15. И в самом деле, в хакера издание игры 15, Вы будете вызов для реализации, не только игра в этой старой школы игра, но, скорее, решение это, реализации режима бога, так сказать, что на самом деле решает головоломки для человека, путем предоставления им намек, после намека, после намека. Так больше на этом на следующей неделе. Но это то, что лежит впереди. Сейчас вспоминаю, что ранее на этой неделе у нас была эта Скалолаз, если хотите, в результате чего лучше мы делали сортировки мудрый был верхний предел Big O п в квадрате. Другими словами, пузырьковой сортировки, Выбор рода, сортировка вставками, все из них, в то время как другая в их реализации, переданы в п квадрате работает время в самом худшем случае. И мы, как правило предположить, что очень худшем случае для сортировки это то, что ваша входы полностью в обратном направлении. И в самом деле, он взял довольно много шагов для осуществления каждого из этих алгоритмов. Теперь в самом конце класса Напомним, мы сравнили пузырьковой сортировки против выбора рода в отношении одного другой что мы назвали сортировки слиянием в то время, и я предлагаю, чтобы он принимает Преимущество урока от недели нулю, разделяй и властвуй. И как-то достижения какой-то логарифмическая время работы, в конечном счете, вместо чего-то это чисто квадратичной. И это не совсем логарифмическая, это немного больше, чем это. Но если вы помните из класса, это было гораздо, гораздо быстрее. Давайте взглянем на то, где мы остановились. Пузырь рода против выбора Сортировать по сравнению с сортировки слиянием. Теперь они все работает, в Теория, в то же время. Процессор работает с такой же скоростью. Но вы можете чувствовать себя как скучно это очень быстро станет, и только, как быстро, когда мы вводим немного алгоритмов за неделю Зеро, мы можем ускорить. Так знак рода выглядит потрясающе. Как мы можем использовать его для того, сортировать число быстрее. Ну давайте вспомним к ингредиента, что был вернуться к нулевой неделе, что из ища кого-то в телефонной книге, и вспомнить, что псевдокод, что мы предложили, с помощью которых мы можем найти кто, как Майк Смит, выглядел немного что-то вроде этого. Теперь взгляните в частности в строке 7 и 8, и 10 и 11, которые индуцируют что цикл, в котором мы сохранили возвращаясь к строке 3 снова, и снова, и опять. Но оказывается, что мы можем смотреть этот алгоритм, здесь, в псевдокоде, немного более целостно. В самом деле, что я ищу на здесь на экране, алгоритм для поиска Майк Смит среди некоторого множества страниц. И в самом деле, мы могли бы упростить это Алгоритм в этих строках 7 и 8, и 10, и 11, чтобы просто сказать, что это, которые я представил здесь в желтый цвет. Другими словами, если Mike Смит ранее в книге, мы не должны указать шаг за шагом теперь, как пойти и найти его. Мы не должны указать вернуться к строке 3, почему бы нам просто не вместо, скажем, в более общем смысле, искать Майка в левая половина книги. И наоборот, если Майк на самом деле в книге позже, почему бы нам просто не процитировать Unquote поиска Майка в правой половине книги. Другими словами, почему бы нам просто не вроде плоскодонки на себя говорю, искать Майка в этом подмножество книги, и оставить его для наших существующих Алгоритм, чтобы сообщить нам как искать Майка в что левая половина книги. Другими словами, наш Алгоритм работы будь то телефонная книга этой толщины, это Толщина или любой толщины вообще. Таким образом, мы можем рекурсивно определить этот алгоритм. Другими словами, на Экран здесь, является алгоритм для поиска Майк Смит среди страниц телефонной книги. Таким образом, в линии 7 и 10, давайте просто сказать, что именно. И я использую этот термин мгновение назад, и, действительно, рекурсия это модное слово сейчас, и это этот процесс делать что-то, каким-то циклический с помощью кода, у вас уже есть, и призывая его снова, и снова, и снова. Теперь это будет важно что мы как-то снизу из, и не делать, что бесконечно долго. В противном случае мы будем есть действительно бесконечный цикл. Но давайте посмотрим, если мы можем заимствовать эту идею из рекурсии, делать что-то снова и снова, и снова, чтобы решить сортировка проблема с помощью слияния рода, тем более эффективно. Так я даю вам объединить рода. Давайте взглянем. Так вот псевдокод, с которые мы могли бы реализовать сортировку, с помощью этого алгоритма под названием сортировка слиянием. И это довольно просто это. На входе п элементов, Другими словами, если вы учитывая п элементов и числа и письма или что-то, то вход, если вы дали п элементов, если п меньше, чем 2, только возвращаться. Правильно? Потому что, если п меньше, чем 2, что означает, что мой список элементов либо размера 0 или 1, и В обоих этих более сложных случаях список уже отсортирован. Если нет никакого списка, это сортируется. А если есть список длины 1, то, очевидно, сортируются. Таким образом, алгоритм должен только действительно что-то интересное, если у нас есть два или более элементы дано нам. Итак, давайте посмотрим на то магии. Остальное отсортировать левую половину элементов, Затем сортировать правую половину элементов, Затем слить, отсортированные половинки. И то, что вроде умопомрачительным здесь является то, что я на самом деле не кажется, уже говорил вам ничего просто еще, верно? Все, что я сказал, это, учитывая список п элементов, сортировать левую половину, то правая половина, то объединить упорядоченные половинки, но где фактическое секрет соуса? Где алгоритм? Ну получается, что этих двух линий Сначала вроде левая половина элементов, и вроде правая половина элементов, рекурсивные вызовы, так сказать. В конце концов, в этом момент времени, у меня есть алгоритм с которым сортировать целую кучу элементов? Да. Это прямо здесь. Это прямо здесь, на экране, и так что я могу использовать тот же набор шагов сортировать левую половину, как я могу правая половина. И в самом деле, снова, и снова. Так или иначе, а мы скоро убедиться в этом, магию сортировки слиянием встроен в том, что очень финале линия, слияния отсортированных половинки. И это, кажется довольно интуитивно. Вы берете две половинки, и вам, так или иначе, объединить их вместе, и мы увидим, это конкретно в данный момент. Но это полная алгоритм. И давайте посмотрим, почему. Ну предположим, что нам дают эти же восемь элементов здесь на экране, один через восемь, но они в, казалось бы, случайном порядке. И цель под рукой сортировать эти элементы. Ну, как я могу идти о делать это с помощью, опять же, сортировка слиянием, в соответствии с настоящим псевдокоде? И опять, вселить это в Ваш ум, на мгновение. Первый случай является довольно тривиально, если это меньше, чем 2, просто вернуть, нет ни работы, чтобы сделать. Так на самом деле есть только три шаги, чтобы действительно держать в уме. Опять и опять, я захочет иметь сортировать левую половину, сортировать правую половину, а затем, как только их две половинки сортируются, Я хочу, чтобы объединить их вместе в один отсортированный список. Так что имейте это в виду. Так вот первоначальный список. Давайте относиться к этому как Массив, как мы начали в неделю два, который является непрерывный блок памяти. В этом случае, содержащий восемь номера, спина к спине к спине. И пусть теперь применим сортировки слиянием. Так что я сначала хочу, чтобы отсортировать левая половина этого списка, И давайте, следовательно, сосредоточиться на 4, 8, 6, и 2. Теперь, как я могу идти о сортировка списка размера 4? Ну у меня есть, чтобы рассмотреть в настоящее время сортировка слева от левой половины. Опять же, давайте назад на мгновение. Если псевдокод это, и я дал восемь элементов, 8, очевидно, больше чем или равно 2. Так что с первым случаем не применяется. Таким образом, чтобы разобраться восемь элементов, я впервые сортировать левую половину элементов, затем сортировать правую половину, то я объединить два отсортированных половинки, каждая из размеров 4. ХОРОШО. Но если вы только что сказали мне, сортировать левая половина, которая в настоящее время размер 4, Как отсортировать левую половину? Ну, если у меня есть вход из четырех элементов, Я впервые отсортировать левую два, то право два, а потом я их объединить вместе. Итак, еще раз, это становится немного из умопомрачительным игра здесь, потому что вы, вроде, должны помните, где вы находитесь в этой истории, но в конце концов, учитывая любое число элементов, Вы сначала хочу отсортировать левая половина, то правая половина, а затем объединить их вместе. Давайте начнем делать именно это. Вот вход из восьми элементов. Теперь мы смотрим на левой половине здесь. Как сортировать четырех элементов? Ну я сначала отсортировать левую половину. Теперь, как мне отсортировать левую половину? Ну мне дали два элемента. Итак, давайте разберемся этих двух элементов. 2 больше или равно 2, конечно. Так что первый случай не распространяется. Так что я теперь должен разобраться левую половина из этих двух элементов. Левая половина, конечно, находится всего в 4. Так как мне отсортировать список одного элемента? Ну, что специальная база случай наверху, так сказать, относится. 1 меньше, чем 2, и моя Список действительно размера 1. Так что я просто вернуться. Я ничего не делать. И в самом деле, посмотрите на то, что я сделано, 4 уже отсортированы. Как Я уже частично успешными здесь. Теперь, кажется, своего рода глупо требовать, но это правда. 4 приведен список размера 1. Это уже отсортированы. Это левая половина. Теперь я сортировать правую половину. Мой вход один элемент, 8 Точно так же, уже отсортированы. Глупо, слишком, но опять же, это основной принцип собирается, чтобы позволить нам в настоящее время строить на вершине этого успешно. 4 сортируются, 8 сортируется, теперь то, что было, что последний шаг? Таким образом, третий и последний шаг, любое раз вы сортировки списка, напомним, было объединить две половинки, левая и правая. Так что давайте делать именно это. Моя левая половина, конечно, 4. Моя правая половина 8. Так давайте сделаем это. Сначала я собираюсь выделить некоторые дополнительные памяти, что я буду представлять здесь, как просто вторичным массива, что это достаточно большой, чтобы соответствовать этим. Но вы можете себе представить, расширяя что прямоугольник вся длина, если нам нужно больше позже. Как я беру 4 и 8, и объединить эти два списка размере 1 вместе? Здесь тоже довольно просто. 4 приходит первым, а затем приходит 8. Потому что, если я хочу, чтобы отсортировать левая половина, то правая половина, а затем объединить эти две половинки вместе, в отсортированном порядке, 4 приходит первым, а затем приходит 8. Таким образом, мы, кажется, делает успехи, даже хотя я не сделал никакого фактическую работу. Но помните, где мы находимся в истории. Мы изначально приняли восемь элементов. Мы отсортировали левую половину, которая 4. Тогда мы отсортировали левую половину в левой половине, которая была 2. И здесь мы идем. Мы сделали с этим шагом. Так что, если мы сортируются левая половина 2, теперь мы есть для сортировки правую половину 2. Таким образом, правая половина 2 эти два значения здесь, 6 и 2. Так теперь давайте вход размера 2, и сортировать левую половину, а затем правая половина, а затем объединить их вместе. Ну, как мне отсортировать список размеров 1, содержащий только номер 6? Я уже сделал. Это список размере 1 сортируется. Как мне отсортировать список еще размер 1, так называемая правая половина. Ну, тоже уже отсортированы. 2 номер один. Так что теперь у меня есть две половинки, слева и Право, мне нужно, чтобы объединить их вместе. Позвольте мне дать себе некоторое дополнительное пространство. И положил 2 там, затем 6 в там, таким образом, сортировка этот список, слева и справа, и слияние их вместе, в конечном счете,. Так что я нахожусь в немного лучшей форме. Я не сделал, потому что ясно 4, 8, 2, 6 не является окончательным заказа, что я хочу. Но теперь у меня есть два списка размер 2, что оба, соответственно, были отсортированы. Так что теперь, если вы назад в вашем воображении глаз, откуда, что нам дает? Я начал с восьми элементов, то я свел его к левой половине 4, Затем левая половина 2 и Затем правая половина 2, Я закончил, поэтому, сортировка левую половина 2, а правая половина 2, так что третий и последний шаг здесь? Я должен объединить вместе два списка размера 2. Так что давайте идти вперед. И на экране тут, дать мне некоторые дополнительные памяти, хотя технически, заметили, что я имею получил целую кучу пробелом наверху Там. Если я хочу, чтобы быть особенно офисные помещения мудрый, Я мог бы просто начать двигаться элементы назад и вперед, сверху и снизу. Но только для наглядности, Я собираюсь поставить его вниз, чтобы держать вещи красивым и чистым. Так что я получил два списка размера 2. Первый список содержит 4 и 8. Второй список имеет 2 и 6. Давайте объединять тех, вместе в определенном порядке. 2, конечно, на первом месте, затем 4, затем 6, затем 8. И теперь мы, кажется, становятся где интересно. Теперь я сортируются половина список, и по совпадению, это все четные числа, а что это, действительно, просто совпадение. И я теперь сортируются влево половина, так что это 2, 4, 6 и 8. Ничего не в порядке. Это чувствует, как прогресс. Теперь он чувствует себя, как я говорили навеки, так, что еще предстоит увидеть, если это Алгоритм, по сути, более эффективным. Но мы собираемся через это супер методично. Компьютер, конечно, будет делать это так. Так где же мы? Мы начали с восьми элементов. Я сортируются левую половину 4. Я, кажется, с этим покончено. Так что теперь следующий шаг заключается в сортировать правую половину 4. И эта часть мы можем пойти через немного больше быстро, хотя вы Добро пожаловать, чтобы перемотать или приостановить, просто думаю, через него Ваш собственный темп, но то, что мы имеем сейчас возможность сделать то же алгоритм на четыре разные номера. Так что давайте идти вперед, а сосредоточиться на правая половина, которую мы здесь. Левая половина того, что Правая половина, и в настоящее время левая половина слева половина этого правой половине, и как мне отсортировать список размеров 1, содержащий только номер 1? Уже сделано. Как сделать то же самое для списка размер 1, содержащей всего 7? Уже сделано. Шаг три для половины, то является объединить эти два элемента в новый список размеров 2, 1 и 7. Есть, кажется, не сделали все что многое интересная работа. Давайте посмотрим, что произойдет дальше. Я просто сортируются левую половину из Правая половина моей первоначальной вход. Теперь давайте разберёмся право половина, которая содержит 5 и 3. Давайте раз взглянуть на левой половина, сортируется, правая половина, сортировать, и объединить эти два вместе, в какой-то дополнительное пространство, 3 приходит первым, а затем приходит 5. И вот теперь, мы отсортированы левая половина правой половине исходной задачи и правая половина правой половине исходной задачи. Что третий и последний шаг? Ну, чтобы объединить эти две половинки вместе. Итак, позвольте мне получить себе некоторые дополнительное пространство, но, опять же, я может быть с помощью этого свободное пространство наверху. Но мы собираемся, чтобы держать это просто визуально. Позвольте мне теперь сливаются в 1, и Затем 3, а затем 5, затем 7. Таким образом, оставив меня теперь с Правая половина исходной задачи Это совершенно отсортированы. Так что же остается? Я чувствую, что я держу заявив те же самые вещи снова и снова, но это отражать То, что мы используем рекурсию. Процесс используя Алгоритм снова, и снова, на небольших подмножеств исходная задача. Так что я теперь левая сортируются половина исходной задачи. У меня есть право отсортированный половину исходной задачи. Что третий и последний шаг? О, это слияние. Так давайте сделаем это. Выделим некоторые дополнительные памяти, но мой бог, мы может поставить его в любом месте в настоящее время. У нас есть так много свободного места для нас, но мы будем держать это простым. Вместо того, чтобы идти вперед и вперед с нашей первоначальной памяти, давайте просто делать это визуально сюда ниже, чтобы закончить слияние левая половина и правая половина. Так путем слияния, то, что мне нужно делать? Я хочу, чтобы взять элементы в порядке. Так, глядя на левой половине, Я вижу, что первое число 2. Я смотрю на правой половине, Я вижу первый номер 1, так что, очевидно, которая Количество я хочу вырвать, и поставить первым в моей окончательный список? Конечно, 1. Теперь я хочу спросить, что же вопрос. На левой половине, у меня еще есть номер 2. На правой половине, Я получил номер 3. Какой я хочу, чтобы выбрать? Конечно, число 2 и Теперь обратите внимание на кандидатов являются 4 слева, 3 справа. Давайте, конечно, выбрать 3. Теперь кандидаты на 4 левая, 5 справа. Мы, конечно, выбрать 4. 6 слева, 5 справа. Мы, конечно, выбрать 5. 6 слева, 7 справа. Мы выбираем 6, а затем мы выбрать 7, а затем мы выбираем 8. Вуаля. Таким образом, огромное количество слов позже, мы отсортировали это список из восьми элементов в список одного до восьми, который растет с каждым шагом, но сколько раз сделал это взять нас, чтобы сделать это. Ну, я намеренно возложили вещи из графически здесь, так что мы можем вид см или оценить разделение в завоевании, который был происходит. Действительно, если вы посмотрите на поминках, Я оставил все эти пунктирными линиями в место держателей, вы можете, вид, видите, в обратном порядке, если вы вроде оглянуться в История теперь, мой первоначальный список есть, конечно, от размера 8. А потом уже, я был имеем дело с двумя списками размером 4, а затем четыре списки размер 2, а затем восемь списков размера 1. Так что это делает, вид, вам напоминает? Ну, в самом деле, любой из алгоритмы мы посмотрел на до сих пор, где мы разделяй и деления и деления, держать имея вещи снова, и снова, приводит в этой общей идеи. И так есть что-то логарифмическая здесь происходит. И это не совсем журнал п, но есть логарифмическая компонент на то, что мы только что сделали. Теперь давайте рассмотрим, как это есть на самом деле. Так, авторизуйтесь п, снова прекрасное время работает, когда мы сделали что-то вроде бинарный поиск, как мы теперь называем, разделяй и властвуй стратегия через который мы нашли Майка Смита. Теперь технически. Это журнал Основание 2 п, даже хотя в большинстве математических классов, 10, как правило, база, что вы взять на себя. Но ученые-компьютерщики почти всегда думать и говорить в терминах базы 2, таким образом, мы вообще просто сказать, журнал п, а журнала базы 2 п, но они точно одно и то то же самое в мире компьютер наука, и, как в сторону, есть постоянный фактор Разница между ними, так что спорный во всяком случае, для более формальным причинам. Но сейчас, то, что мы заботимся о это пример. Так что давайте не доказать, например, но в мере использовать пример чисел под рукой для проверки отсутствия ошибок, если вы будете. Так, ранее формула была база журнала 2 п, но то, что п в этом случае. Я был п оригинальные номера, или 8 из исходного числа специально. Теперь это было немного в то время как, но я уверен, Убедитесь, что журнал основание 2 от стоимости 8 3, и, действительно, то, что приятно об этом является 3, что именно количество раз что вы можете разделить список длины 8 раз, и снова, и снова, пока вы оставили со списками только размер 1. Правильно? 8 идет на 4, идет до 2, идет в 1, и это отражает именно это картина у нас было всего лишь мгновение назад. Так немного здравомыслия проверить, куда на самом деле участвует логарифм. Так что теперь, что еще тут дело? п. Так заметить, что каждый раз я разделить список, хотя и в обратном порядке в истории здесь, я все еще делаю п вещи. Это слияние шаг требуется, Я прикасаюсь каждый из номеров, для того, чтобы скользить его в его подходящим местом. Поэтому, даже если высота этого диаграмма размера журнала п п или 3, В частности, другими словами, Я сделал три дивизии здесь. Сколько работы я сделал по горизонтали по этой схеме каждый раз? Ну, я сделал п шагов работать, потому что, если я получил четыре элемента и четыре элемента, и мне нужно, чтобы объединить их вместе. Мне нужно, чтобы пройти через эти четыре, и они четыре, в конечном счете, объединить их назад в восьми элементов. Если, наоборот, я получил восемь пальцев здесь, что я не делаю, и восемь fingers-- sorry-- если я получил четыре пальца сюда, что я и делаю, четыре пальца здесь, что я делаю, то, что то же самое, Пример, как и прежде, если я восемь пальцев, хотя в Всего которые я могу, вроде, сделать. Я могу точно сделать здесь, то я, конечно объединить все эти списки размер 1 вместе. Но я, конечно, придется искать каждый элемент ровно один раз. Таким образом, высота этого процесса журнала N, ширина этого процесса, так сказать, является н, так, что мы, кажется, чтобы, в конечном счете, это бегущий время размер п раз войти н. Другими словами, мы разделили список, журнал N раз, но каждый раз мы сделали это, мы были коснуться каждого из элементов для того, чтобы объединить их Все вместе, что шаг был п, так что мы должны п раз войти н, или как ученый скажет, асимптотически, что будет большое слово для описания верхний связаны на времени работы, мы бежим в Big O лог н время, так сказать. Теперь это важно, потому что вспомнить, что бегущие времена были с пузырьковой сортировки, отбора и сортировать и сортировка вставками, и даже некоторые другие, которые существуют, п квадрате было, где мы были в. И вы можете, вид, увидеть это здесь. Если п квадрате, очевидно, п раз п, но здесь мы имеем п раз войти н, и мы уже знаем, от недели нулю, что журнал п, логарифмическая, лучше, чем что-то линейной. В конце концов, вспомнить картину с красным и желтым и зеленые линии, которые мы нарисовали, тем зеленый логарифмическая линия была значительно ниже. И, следовательно, гораздо лучше и быстрее, чем прямой желтый и красных линий, п раз войти н, действительно, лучше чем п раз п, или н квадрате. Таким образом, мы, кажется, есть определили слияние алгоритм вроде тех, что работает в гораздо минимальное время, и, действительно, Вот почему, в начале этой недели, когда мы увидели, что конкурс между пузыря сортировать, выбор сортировки и слияния сортировать, сортировка слиянием действительно, действительно выиграл. И в самом деле, мы даже не ждать для пузырьковой сортировки и отбора рода заканчивать. Теперь давайте еще один проход При этом из несколько более формальный перспективе, только в случай, этот отклик лучше чем этого высшего уровня обсуждения. Так вот алгоритм снова. Давайте спросим себя, то, что время работы является это алгоритмы различные шаги? Давайте разделим его на первое Корпус и второй случай. ПЧ и еще в том случае, если, Если N меньше, чем 2, только возвращаться. По ощущениям постоянной времени. Это, своего рода, как два этапа, Если N меньше, чем 2, а затем вернуться. Но, как мы сказали, в понедельник, постоянная времени, или Big O 1, может быть два, три шага шаги, даже 1000 шагов. Важно то, что это постоянное число шагов. Таким образом, желтый выделенный псевдокод здесь работает в, мы будем называть его, постоянная времени. Так более формально, и мы собираемся, целью которых это будет степень, в которой мы оформить это право now-- Т п, время работы задачи который принимает п нечто в качестве входных, равна Big O из одного, Если N меньше, чем 2. Так что это обусловлено, что. Таким образом, чтобы быть ясным, если п меньше 2, у нас есть очень короткий список, то время работает, Т п, где п 1 или 0, в этом очень конкретном случае, это просто будет постоянная времени. Это займет один шаг, два шага, что угодно. Это фиксированное число шагов. Таким образом, сочная часть должна быть в безусловно другой случай в псевдокоде. Дело в другом месте. Сортировать левая половина элементов, отсортируйте право половина элементов, слияния отсортированных половинки. Как долго каждый из этих шагов взять? Ну, если работает Время сортировать п элементов , давайте называть его очень в общем, Т п, затем сортировки левой половина элементов это, вроде, как и говорили: Т п делится на 2, и аналогично сортировке правую половину из элементов, вроде, как и говорили: Т п делится 2, а затем слияния отсортированных половинки. Ну, если я получил некоторые Количество элементов здесь, как четыре, и некоторое количество элементов здесь, как четыре, и я должен объединить каждого из этих четырех В, и каждый из них четыре в, один за другим, так что в конечном счете, у меня есть восемь элементов. Он чувствует, как это Big O из п шагов? Если я получил п пальцы и каждый из им должен быть объединены в месте, это как еще п шагов. Так действительно formulaically, мы можем выразить это, хотя немного пугающе сначала взгляд, но это что-то что захватывает именно эту логику. Время работы, Т п, если п больше или равно 2. В этом случае, в случае ELSE, Т п делится на 2, плюс Т N делится на 2, плюс Big O п, некоторые линейный ряд шагов, возможно ровно п, может быть, в 2 раза п, но это примерно, порядок п. Так что, тоже, как мы можем выразить это formulaically. Теперь вы не знали бы, это, если вы записали его в своем уме, или посмотреть его в назад учебника, что может иметь немного шпаргалку в конце концов, но это, действительно, собирается дать нам Big O н журнала п потому что рецидив Вы видите здесь, на экране, если вы на самом деле это, с бесконечное число примеров, или вы сделали это formulaically, вы бы видеть, что это, потому что этой формуле само по себе является рекурсивным, с т п над чем-то справа, и т п над слева, это может фактически быть выражена, в итоге, как большой идут н журнала п. Если не убежден, что это хорошо сейчас, просто принять на веру, что это, в самом деле, что это рецидив приводит к, но это всего лишь немного больше Математический подход к поиску на времени работы сортировки слиянием на основании его псевдокода в покое. Теперь давайте немного передышку от всего этого, и принять взглянем на уверен бывший сенатор, который может выглядеть немного знакомы, кто сел с Эриком от Google Шмидт, некоторое время назад, для интервью на сцене, перед целым букетом людей, в конечном счете, о говорить тема, это довольно уже знакомы. Давайте взглянем. Эрик Шмидт: Теперь сенатор, Вы здесь Google, и я хотел бы думать о Председательство в собеседовании. Теперь это трудно получить работу в качестве президента. ПРЕЗИДЕНТ ОБАМА: Хорошо. Эрик Шмидт: И ты собирается делать [неразборчиво] в настоящее время. Это также трудно получить работу в Google. ПРЕЗИДЕНТ ОБАМА: Хорошо. Эрик Шмидт: У нас есть вопросы, и мы просим наших кандидатов вопросы, и это одна из Ларри является Швиммер. ПРЕЗИДЕНТ ОБАМА: Хорошо. Эрик Шмидт: Что? Вы, ребята, думаете, что я шучу? Это прямо здесь. Что является наиболее эффективным способом сортировать миллион 32 битные целые? ПРЕЗИДЕНТ ОБАМА: Well-- Эрик Шмидт: Иногда, может быть, мне жаль, maybe-- ПРЕЗИДЕНТ ОБАМА: Нет, нет, нет, нет, нет, я think-- Эрик Шмидт: Это не it-- ПРЕЗИДЕНТ ОБАМА: Я думаю, я думаю, что пузырь Сортировать бы неправильный путь. Эрик Шмидт: Ну. Кто сказал ему это? ХОРОШО. Я не сделал информатика on-- ПРЕЗИДЕНТ ОБАМА: Мы уже получили наши шпионы там. ПРОФЕССОР: Все правильно. Давайте оставим позади нас теперь Теоретическая мир алгоритмов в асимптотического анализа их, и вернуться к некоторым темам от недели нулем и единицей, и начала удалить некоторые учебные колеса, если вы будете. Так что вы действительно понимаете, в конечном счете, от начала до конца, что происходит под капотом, когда вы писать, компилировать и выполнять программы. Напомним, в частности, что это было первая программа С мы смотрели на, канонический, простая программа рода, условно говоря, где она печатает, Hello World. И вспоминаю, что я сказал, то процесс что исходный код проходит через является именно это. Вы берете исходный код, пройти это через компилятор, как Clang, и прибывает объектный код, что может выглядеть как это, нулей и единиц что процессор компьютера, центральное Блок обработки или головного мозга, в конечном счете, понимает. Оказывается, что это немного упрощением, что мы теперь в положение, чтобы дразнить друг от друга чтобы понять, что действительно был происходит под капотом каждый раз, когда вы запустите Лязг, или в более общем, каждый раз, когда вы делаете программу, с помощью Марка и CF 50 IDE. В частности, такие вещи, как Это первый генерируется, когда вы впервые скомпилировать программу. Другими словами, когда вы принять ваш исходный код и скомпилировать его, то, что первый время выводимый Clang что-то известный как ассемблере. И в самом деле, это выглядит именно так. Я побежал команды на командной строки раньше. Лязг Dash большой буквы hello.c, и это создало файл для меня, называемых hello.s, внутри которого были точно это содержание, и немного больше выше, и немного больше ниже, но я поставил сочные Информация здесь на экране. И если вы внимательно посмотрите, вы увидите, по крайней мере, несколько знакомых ключевые слова. У нас есть главный в верхней. Мы PRINTF посередине. И мы также имеем привет мир Обратная косая черта н в кавычки вниз ниже. А все остальное здесь является Инструкция по очень низкого уровня что процессор компьютера понимает. Инструкции ЦП, которые движутся память вокруг, что струны груз из памяти, и в конечном счете, печати вещи на экране. Теперь то, что происходит, хотя после эта сборка генерируется код? В конечном счете, вы, в самом деле, еще генерировать объектный код. Но шаги, которые действительно уже на под капотом выглядеть немного больше, как это. Исходный код становится ассемблера, который затем становится объектом код, и оперативные слова здесь, что, при компиляции исходного кода, прибывает ассемблерный код, а затем при сборке кода сборки, прибывает объектный код. Теперь Clang супер сложные, как много компиляторов, и он делает все эти шаги вместе, и это не обязательно Выход любой промежуточный файлы, которые вы можете даже увидеть. Это просто компилирует вещи, который является общим термином, который описывает весь этот процесс. Но если вы действительно хотите чтобы быть частности, есть намного больше там происходит, а также. Но давайте также рассмотреть теперь, даже что супер простая программа, hello.c, называется функцией. Он призвал Printf. Но я не написать Printf, действительно, который поставляется с с, так сказать. Это функция напомним, что это заявил в стандартном io.h, который файл заголовка, который это тема, которую мы будем на самом деле погрузиться в глубины, прежде чем более длинные. Но файл заголовка как правило, сопровождается файлом кода, файл исходного кода, так так же, как существует стандартная io.h. Некоторое время назад, кто-то, или кому-то, также написал файл называется стандартным io.c, в которые фактические определения, или реализации Printf, и гроздья других функций, на самом деле написано. Поэтому, учитывая, что, если мы считаем, имея здесь, на левом, hello.c, что, когда составлен, дает нам hello.s, даже если Clang не беспокоит сохранение в месте мы можем увидеть его, и что сборка код получает собраны в hello.o, который это, действительно, имя по умолчанию учитывая при компиляции источник код в объектный код, но не вполне готовы выполнить его еще, потому что еще один шаг должно произойти, и имеет что происходило на протяжении последних нескольких недели, возможно, без ведома к вам. В частности где-то в CS50 IDE, а это, тоже будет чем-то вроде упрощение на мгновение, есть, или был на то время, файл называется стандартным io.c, что кто-то собраны в Стандартные io.s или эквивалент, что кто-то затем собраны в стандартной io.o, или оказывается в немного другой файл Формат, который может иметь разные расширение файла в целом, но в теории и концептуально, точно эти шаги были произойти в какой-то форме. Что и говорить, что в настоящее время когда я пишу программу, hello.c, что просто говорит, привет мир, и я с помощью кода чужой как Printf, который был давным- Время, в файле под названием стандарт io.c, потом как-то я должен принять мои объектного кода, мои нули и единицы, и объект этого человека код, или нули и единицы, и как-то связать их вместе в один последний файл, называется привет, что имеет все нули и те из моей главной функции, и все нули и те, для Printf. И в самом деле, что в прошлом процесс называется, связывая свой объектный код. Выход которого представляет собой исполняемый файл. Таким образом, в справедливости, на Конец дня, ничего не изменилось с одной недели, когда мы впервые начал компиляции программы. Действительно, все это уже было происходит под капотом, но теперь мы в состоянии где мы можем на самом деле дразнить друг от друга эти различные шаги. И в самом деле, в конце в день, мы по-прежнему осталось нулей и единиц, которые на самом деле большая переходить в настоящее время другому возможностью C, что у нас не было, чтобы использовать, скорее всего, на сегодняшний день, известный как побитовые операторы. Другими словами, до сих пор, мы в любое время дело с данными в C или переменных в C, у нас было что-то вроде символы и поплавки и модули и жаждет и двухместных и т.п., но все те, по крайней мере восемь бит. Мы никогда еще не был в состоянии манипулировать отдельных битов, даже если отдельный бит, мы Знаете, может представлять 0 и 1. Теперь выясняется, что в C, вы может получить доступ к отдельным битам, если вы знаете синтаксис, с которой, чтобы добраться до них. Итак, давайте взглянем у операторов побитовых. Так на фото, вот несколько символов, которые мы, вроде, вроде, видел. Я вижу амперсанд, вертикальный бар, и некоторые другие, а также, и вспомнить, что амперсанд амперсанд это то, что мы видели раньше. Логический оператор И, где у вас есть два из них вместе, или логическое ИЛИ Оператор, где вы Две вертикальные полоски. Битовые операторы, которые мы будем см работать на бит по отдельности, просто использовать один амперсанд, А один вертикальный бар, каретка символ приходит следующий, маленький Тильда, а затем оставил Кронштейн левой скобки, или правая скобка правая скобка. Каждый из них имеет разные значения. В самом деле, давайте взглянем. Давайте старой школы сегодня, и использование сенсорный экран с прошлого, известный как белая доска. И это белая доска собирается, чтобы позволить нам чтобы выразить некоторые довольно простые символы, или, скорее, некоторые довольно простые формулы, что мы можем в конечном счете, то рычаги, для того, Для доступа к отдельным Биты в пределах программы C. Другими словами, давайте сделаем это. Давайте сначала поговорим момент о амперсанд, который является побитовое И оператора. Другими словами, это оператор, который позволяет мне есть переменная левая как правило, и переменная правая, или индивидуальное значение, что, если мы и их вместе, дает мне конечный результат. Так что я имею в виду? Если в программе, у вас есть переменная что магазины одной из этих значений, или давайте держать его проста, и просто выписать нули и единицы в отдельности, Вот как работает оператор амперсанд. 0 0 амперсанд будет равняться 0. Теперь, почему это? Это очень похоже на Логические выражения, что мы обсуждали до сих пор. Если вы думаете, после всего, 0 ложь, ложь 0, ложные и ложной это, как мы уже обсуждали логически, также ложно. Итак, мы получаем 0 здесь также. Если вы берете 0 амперсанд 1, хорошо, что тоже, будет 0, так как для этого Выражение левая, чтобы быть правдой или 1, то ему необходимо будет, чтобы быть правдой, и правда. Но здесь мы имеем ложное и правда, или 0 и 1. Теперь снова, если у нас есть 1 амперсанд 0, что тоже будет 0, и если у нас есть 1 амперсанд 1, наконец, у нас есть 1 бит. Итак, другими словами, мы не делаем что-нибудь интересное с этим оператором Пока еще нет, этот оператор амперсанд. Это побитовое И оператора. Но эти ингредиенты через который мы можем сделать интересные вещи, как мы вскоре увидим. Теперь давайте посмотрим на только один Вертикальная черта здесь справа. Если у меня есть 0 немного, и я Или это с того, что побитовое Оператор ИЛИ, другой бит 0, что собирается дать мне 0. Если я беру немного, и 0 или его с 1 бит, то я иду, чтобы получить 1. И в самом деле, как раз для ясность, позвольте мне вернуться, так что мои вертикальные полосы не принять за 1-х. Позвольте мне переписать все мой 1 немного больше ясно, так что мы в следующий раз увижу, если я имеют 1 или 0, что будет 1, и если у меня есть 1 или 1, что, тоже будет 1. Таким образом, вы можете видеть, что логически ИЛИ Оператор ведет себя очень по-разному. Это дает мне 0 или 0 дает мне 0, но каждый другая комбинация дает мне 1. Пока у меня есть один 1 в Формула, результат будет 1. В отличие от AND Оператор, амперсанд, только если у меня есть два 1-х годов в Уравнение, я на самом деле выйти на 1. Теперь есть несколько других операторы, а также. Одним из них является немного сложнее. Итак, позвольте мне идти вперед и стереть это, чтобы освободить пространство. И давайте взглянем на вставки символов, на мгновение. Как правило, это характер можно ввести На клавиатуре Удержание SHIFT и то одно из чисел на вершине вашего США клавиатура. Таким образом, это является эксклюзивным Оператор ИЛИ, исключающее ИЛИ. Таким образом, мы только что видели оператор или. Это исключительное ИЛИ оператор. Что на самом деле разница? Ну давайте посмотрим на формулу, и использовать это в качестве ингредиентов в конечном счете. 0 XOR 0. Я хочу сказать, всегда 0. Это определение XOR. 0 XOR 1 будет 1. 1 XOR 0 будет 1, и 1 XOR 1 будет? Неправильно? Или вправо? Я не знаю. 0. Теперь то, что здесь происходит? Ну думаю о наименование этого оператора. Исключающее ИЛИ, так как имя, вид, предлагает, ответ только будет 1, если входы эксклюзивные, исключительно отличается. Так вот входы являются то же самое, поэтому выход равен 0. Вот входы являются то же самое, поэтому выход равен 0. Вот выходы разные, они являются исключительными, и поэтому выход 1. Так что это очень похоже на И, это очень похоже, или, скорее, это очень похоже на ИЛИ, но только в эксклюзивном образом. Не Это один больше не 1, потому что у нас есть два 1-х, и не исключительно, только один из них. Все в порядке. Что можно сказать о других? Ну тильды, тем временем, на самом деле просто и красиво, к счастью. И это унарный Оператор, который означает он применяется только к одному входу, один операнд, так сказать. Не левой и правой. Другими словами, если вы берете тильды из 0, ответ будет наоборот. А если взять тильды из 1, Ответ будет наоборот. Таким образом, оператор тильда способ отрицания немного, или листать немного от От 0 до 1 или от 1 до 0. И, наконец, оставляет нас только с двумя операторами конечных, так называемый сдвиг влево, и так называемый оператор сдвига вправо. Давайте взглянем на то, как эти работы. Левый оператор сдвига, написанная с двумя угловыми скобками, как, что, работает следующим образом. Если мой вклад, или мой операнд, слева Оператор сдвига достаточно просто 1. И я тогда скажу компьютер в сдвиг влево, что 1, говорят семь мест, результат, как если бы я принять, что 1 и переместить его семь мест в более левый, и по умолчанию, мы будем считать, что пространство справа собирается быть нулями. Другими словами, 1 сдвиг влево 7 будет чтобы дать мне, что 1, затем 1, 2, 3, 4, 5, 6, 7 нулей. Таким образом, в некотором смысле, это позволяет взять небольшое количество, как 1, и четко сделать это гораздо намного больше, таким образом но на самом деле мы увидим более умные подходы к нему вместо этого, а также, Все в порядке. Вот это для трех недели. Мы увидим вас в следующий раз. Это было CS50. [Играет музыка] СПИКЕР 1: Он был на закуску бар ест горячую выдумки мороженое. Он был все это на его лице. Он одет, что шоколад, как бородой СПИКЕР 2: Что вы делаете? СПИКЕР 3: Хм? Что? СПИКЕР 2: Ты только двойное падение? Вы дважды опустил чип. СПИКЕР 3: Извините. СПИКЕР 2: Вы смоченной чип, вы откусил, и вы снова погружают. СПИКЕР 3: СПИКЕР 2: Так вот, как положить вся ваша рот прямо в провал. В следующий раз вы берете чип, просто окунуть его один раз, и конец. СПИКЕР 3: Вы знаете, что, Дэн? Вы опустите путь, который вы хотите окунуться. Я опустите так, что я хочу, чтобы окунуться.