1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> СПИКЕР: Ладно, это CS50. 3 00:00:14,910 --> 00:00:19,020 Это конец три недели, и если Вы не воспользовались уже, 4 00:00:19,020 --> 00:00:21,790 знаю, что там будет обед в эту пятницу, как обычно, где 5 00:00:21,790 --> 00:00:25,430 Вы можете наслаждаться хорошей беседой и еда в Огонь и лед 6 00:00:25,430 --> 00:00:27,980 с некоторыми из CS50 сайт персонал и одноклассники. 7 00:00:27,980 --> 00:00:30,170 Голова к этому URL здесь. 8 00:00:30,170 --> 00:00:33,420 >> Теперь вы, наверное, помните, или вы в ближайшее время может быть знаком с, 9 00:00:33,420 --> 00:00:35,970 эти вещи здесь, которые приведены в конце 10 00:00:35,970 --> 00:00:37,850 семестра для многих классов. 11 00:00:37,850 --> 00:00:40,870 Так называемые экзаменационные синие книги, в которых Вы пишете свои ответы на экзаменах. 12 00:00:40,870 --> 00:00:44,240 Теперь у меня есть здесь 26 таких голубые книги, на каждый из них 13 00:00:44,240 --> 00:00:47,580 написано имя, до Z. И действительно, имена, что просто, 14 00:00:47,580 --> 00:00:50,490 до Z. И один из цели под рукой сегодня 15 00:00:50,490 --> 00:00:53,910 будет продолжать то, что мы начали в понедельник, который не является 16 00:00:53,910 --> 00:00:57,830 столько глядя на код, но на самом деле глядя на идеи и решения проблем. 17 00:00:57,830 --> 00:01:00,170 Одна из целей и Обещания этого курса 18 00:01:00,170 --> 00:01:02,985 является научить вас думать больше тщательно, более методично, 19 00:01:02,985 --> 00:01:05,400 и более эффективно решать проблемы. 20 00:01:05,400 --> 00:01:09,526 И в самом деле, что мы можем сделать, что действительно , даже не касаясь ни одной строки кода. 21 00:01:09,526 --> 00:01:12,150 Поэтому у меня есть пару слонов здесь сегодня, оранжевый и синий, 22 00:01:12,150 --> 00:01:15,780 если бы мы могли получить один доброволец, может быть, от дальше назад, чем обычно. 23 00:01:15,780 --> 00:01:18,070 Как насчет прямо там, давай вниз. 24 00:01:18,070 --> 00:01:24,180 Цель, которая будет в помочь плюс администрировать этот экзамен здесь. 25 00:01:24,180 --> 00:01:24,935 Как тебя зовут? 26 00:01:24,935 --> 00:01:25,768 >> АУДИТОРИЯ: Мэри Бет. 27 00:01:25,768 --> 00:01:27,560 СПИКЕР: Мэри Бет, давай до. 28 00:01:27,560 --> 00:01:29,560 Позвольте мне микрофон здесь для вас. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Приятно познакомиться. 31 00:01:32,880 --> 00:01:34,005 >> АУДИТОРИЯ: Приятно познакомиться. 32 00:01:34,005 --> 00:01:36,790 СПИКЕР: Ладно, у меня есть здесь синий книги через Z, 33 00:01:36,790 --> 00:01:41,680 и я собираюсь делать вид, что У меня есть один из студентов, 34 00:01:41,680 --> 00:01:45,770 и они идут в несколько случайным В конце трехчасового экзамена блока, 35 00:01:45,770 --> 00:01:49,400 таким образом, они в конечном итоге в некоторых полуслучайная порядок, как это. 36 00:01:49,400 --> 00:01:54,510 Теперь ваша задача в мгновение собирается чтобы be-- это на самом деле, как они получают 37 00:01:54,510 --> 00:01:56,820 Оказалось, в конце класс, скорее всего. 38 00:01:56,820 --> 00:02:01,120 Ваша задача теперь будет, вполне просто, чтобы отсортировать эти синие книги для нас 39 00:02:01,120 --> 00:02:05,220 от А до Z. 40 00:02:05,220 --> 00:02:08,400 >> АУДИТОРИЯ: О, это собирается взять навсегда. 41 00:02:08,400 --> 00:02:13,747 >> СПИКЕР: И мы будем смотреть не, как вы делаете это, никакого давления. 42 00:02:13,747 --> 00:02:15,330 АУДИТОРИЯ: Нет, никакого давления или ничего. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> СПИКЕР: И для удовольствия, давайте мириться таймер. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> АУДИТОРИЯ: Так весело, так весело. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> СПИКЕР: я могу держать микрофон для вас. 49 00:02:38,574 --> 00:02:40,240 Хорошо, что мы только что удвоили скорость. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Таким образом, в то же время, Позвольте мне задать что будет вопрос для Мэри Бет 52 00:02:49,060 --> 00:02:51,540 является то, что она делает, как это она собирается о решении этого? 53 00:02:51,540 --> 00:02:54,040 И в самом деле, вы не могли бы Задумывались о чем 54 00:02:54,040 --> 00:02:57,440 так просто, как когда вы выбираете до 26 книгах, как это, 55 00:02:57,440 --> 00:02:59,350 которые имеют естественное заказа до них. 56 00:02:59,350 --> 00:03:01,335 Каков процесс что вы на самом деле использовать? 57 00:03:01,335 --> 00:03:03,770 Это достаточно случайным просто выбирая первый, который вы видите 58 00:03:03,770 --> 00:03:05,250 и положить ее на место? 59 00:03:05,250 --> 00:03:09,680 Вы сначала переместить свои руки вокруг ищу затем ищете B? 60 00:03:09,680 --> 00:03:11,722 Вы взгляните на Пара из них бок о бок 61 00:03:11,722 --> 00:03:14,680 и просто сказать, постойте, это не прав, а затем поменять порядок? 62 00:03:14,680 --> 00:03:16,960 Мы видели уже в понедельник что есть несколько способов 63 00:03:16,960 --> 00:03:22,140 , в котором мы можем сделать это, и действительно, как мы приближаемся к концу здесь, 64 00:03:22,140 --> 00:03:26,360 Я бы принять к сведению, возможно, чего Мэри Бет делает. 65 00:03:26,360 --> 00:03:30,040 У нас есть несколько свай похоже, больший, три поменьше. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> АУДИТОРИЯ: я их заказе когда я нахожу два письма 68 00:03:36,415 --> 00:03:39,540 что я знаю, вместе в последовательности, Я положил их вместе так, что я не 69 00:03:39,540 --> 00:03:42,915 придется беспокоиться о сохранении трек из целого ряда книг. 70 00:03:42,915 --> 00:03:45,706 Это просто, ну, во-первых, У меня этот стек здесь. 71 00:03:45,706 --> 00:03:47,580 СПИКЕР: Так, почти как головоломка частей, которые 72 00:03:47,580 --> 00:03:49,860 имеют правильную форму к совпадают друг с другом. 73 00:03:49,860 --> 00:03:51,026 АУДИТОРИЯ: Довольно много, да. 74 00:03:51,026 --> 00:03:55,320 СПИКЕР: ОК, отлично. 75 00:03:55,320 --> 00:03:59,850 И теперь каждый из них сваи Предположительно сортируются? 76 00:03:59,850 --> 00:04:00,990 >> АУДИТОРИЯ: Да. 77 00:04:00,990 --> 00:04:09,900 >> СПИКЕР: Ладно, до Z. All Хорошо, поздравляю, вы сделали это. 78 00:04:09,900 --> 00:04:11,461 У вас есть выбор. 79 00:04:11,461 --> 00:04:11,960 Синий? 80 00:04:11,960 --> 00:04:13,530 Хорошо, спасибо вам за это. 81 00:04:13,530 --> 00:04:16,679 Так Мэри Бет сделал предложить что ее подход был, 82 00:04:16,679 --> 00:04:19,720 но то, что это еще один подход, как вам может идти о сортировке эти вещи? 83 00:04:19,720 --> 00:04:21,130 Что бы вы сделали? 84 00:04:21,130 --> 00:04:24,060 Запись бить было бы одна минута и 50 или около того секунд, 85 00:04:24,060 --> 00:04:26,039 плюс те, которые я забыл посчитать. 86 00:04:26,039 --> 00:04:27,080 Что бы вы сделали? 87 00:04:27,080 --> 00:04:27,579 Да? 88 00:04:27,579 --> 00:04:28,735 АУДИТОРИЯ: Возьмите стопку. 89 00:04:28,735 --> 00:04:29,776 Начните с самого начала. 90 00:04:29,776 --> 00:04:32,284 Проверьте ваши документы. 91 00:04:32,284 --> 00:04:36,586 И если верхний выше чем, может быть, они, 92 00:04:36,586 --> 00:04:38,980 нижний является выше, то поменять их. 93 00:04:38,980 --> 00:04:41,300 >> СПИКЕР: ОК, так что начинать в верхней и нижней, 94 00:04:41,300 --> 00:04:43,716 а затем работать ваш путь внутрь так, поменяв их местами? 95 00:04:43,716 --> 00:04:46,580 Итак, немного похож по духу пузырьковой сортировки, 96 00:04:46,580 --> 00:04:49,160 но выбор крайности не соседние пары. 97 00:04:49,160 --> 00:04:52,080 Но за исключением этого является то, что есть наверняка куча разному 98 00:04:52,080 --> 00:04:54,210 мы могли бы сделать это, и честно говоря, я думаю, вам вид 99 00:04:54,210 --> 00:04:55,700 принял пару подходов, не так ли? 100 00:04:55,700 --> 00:05:00,567 Вы сделали то четырех отсортированных свай, и затем эффективно объединили их вместе. 101 00:05:00,567 --> 00:05:02,650 И вот, полагаю, еще один Техника в целом. 102 00:05:02,650 --> 00:05:06,950 Вы не рассматривать его как один большой куче, Вы разделили проблему на четыре каре, 103 00:05:06,950 --> 00:05:09,820 если хотите, и тогда так или иначе объединили их в конце. 104 00:05:09,820 --> 00:05:13,410 >> Итак, давайте рассмотрим, в конечном счете,, как еще мы могли бы сделать это. 105 00:05:13,410 --> 00:05:15,860 Мы оформлено понятие пузырьковой сортировки последний раз, 106 00:05:15,860 --> 00:05:18,780 и пузырьковой сортировки напомним было Алгоритм, который мы визуализировали 107 00:05:18,780 --> 00:05:22,640 с восьми своих одноклассников здесь, казалось бы, случайно сортируются сначала. 108 00:05:22,640 --> 00:05:26,110 И мы тогда решили попарно, если два элемента из того, 109 00:05:26,110 --> 00:05:26,950 просто поменять их местами. 110 00:05:26,950 --> 00:05:28,930 Так четыре и два очевидно, из того, 111 00:05:28,930 --> 00:05:31,080 так эти два одноклассников поменялись местами. 112 00:05:31,080 --> 00:05:35,390 А потом мы повторили с четырех до шести лет, затем шесть и восемь, на каждой итерации, 113 00:05:35,390 --> 00:05:36,980 двигаться вправо. 114 00:05:36,980 --> 00:05:42,590 >> Поэтому, учитывая, восемь человек, сколько попарно сравнения я сделал во время прогулки с 115 00:05:42,590 --> 00:05:45,220 слева направо в одной такой итерации? 116 00:05:45,220 --> 00:05:48,410 Сколько сравнения? 117 00:05:48,410 --> 00:05:49,197 Семь, не так ли? 118 00:05:49,197 --> 00:05:51,405 Потому что, если есть восемь люди, но у вас есть пару 119 00:05:51,405 --> 00:05:53,880 им и вы продолжать двигаться один хоп вправо, 120 00:05:53,880 --> 00:05:56,060 вы не будете иметь восемь сравнения, потому что вы не можете сравнить 121 00:05:56,060 --> 00:05:59,226 элемент сам в себе, или это будет просто бессмысленно, так что вы должны семь. 122 00:05:59,226 --> 00:06:01,290 Или в более общем, если у нас есть русских людей, мы 123 00:06:01,290 --> 00:06:04,300 сделать п минус 1 сравнений с пузырьковой сортировки. 124 00:06:04,300 --> 00:06:08,150 >> Итак, давайте рассмотрим теперь, насколько хорошо или плохо пузырь был сам, и попробуйте 125 00:06:08,150 --> 00:06:13,570 дать себе словарь с для критики алгоритмов, как это, 126 00:06:13,570 --> 00:06:14,430 и вскоре самостоятельно. 127 00:06:14,430 --> 00:06:16,970 Так при первом прохождении через пузырьковой сортировки, первый раз 128 00:06:16,970 --> 00:06:20,909 Я шел слева направо по этап, взял меня н минус 1 сравнений. 129 00:06:20,909 --> 00:06:22,950 И это будет мой единица измерения, не так ли? 130 00:06:22,950 --> 00:06:26,170 Я был отчасти говорить и прогуливаясь, несколько быстро, несколько медленно, 131 00:06:26,170 --> 00:06:29,300 так считаю своих секундах не особенно показательно, 132 00:06:29,300 --> 00:06:32,260 но подсчета количества операции, которые я сделал в понедельник, 133 00:06:32,260 --> 00:06:35,900 сравнения двух людей, что чувствует себя как хороший единицы измерения. 134 00:06:35,900 --> 00:06:40,980 >> Так н минус 1 шаги в первый раз, но то что произошло после этого? 135 00:06:40,980 --> 00:06:46,610 Что один Верх один проход через противном случае несортированный список? 136 00:06:46,610 --> 00:06:49,840 Что вы можете сказать мне об элементе который был полностью там? 137 00:06:49,840 --> 00:06:51,300 Да? 138 00:06:51,300 --> 00:06:52,870 Это был самый большой элемент, не так ли? 139 00:06:52,870 --> 00:06:55,710 Номер восемь, хотя она началось здесь, каждый раз, когда я 140 00:06:55,710 --> 00:06:57,860 по сравнению с ней против сосед, она продолжала 141 00:06:57,860 --> 00:07:00,480 бьется справа Правая часть списка. 142 00:07:00,480 --> 00:07:02,710 И в самом деле, вот где Алгоритм получил свое название. 143 00:07:02,710 --> 00:07:07,630 >> Теперь по этой логике, сколько сравнения нужно ли делать на второй раз 144 00:07:07,630 --> 00:07:09,800 Я делаю, что проход слева направо? 145 00:07:09,800 --> 00:07:10,730 н минус 2, не так ли? 146 00:07:10,730 --> 00:07:14,297 Было бы просто тратить свое время, если I держать сравнивая восемь против кого 147 00:07:14,297 --> 00:07:16,630 еще, потому что мы уже знаем она была в нужном месте. 148 00:07:16,630 --> 00:07:19,760 Так что это немного оптимизация, поэтому в следующий проход 149 00:07:19,760 --> 00:07:23,899 будет плюс н минус два шага, где п число людей. 150 00:07:23,899 --> 00:07:26,940 Теперь вы можете рода экстраполяции, даже если вы не специалист по компьютерам, 151 00:07:26,940 --> 00:07:27,680 как это заканчивается. 152 00:07:27,680 --> 00:07:31,259 В конце этого алгоритма, по-видимому у вас есть только одно сравнение оставили. 153 00:07:31,259 --> 00:07:33,800 Вы должны рода исправить начале списка в случае двух 154 00:07:33,800 --> 00:07:36,540 и один вышли из строя и должен быть один и два, 155 00:07:36,540 --> 00:07:40,330 так что это упора на плюс 1 Окончательное сравнение. 156 00:07:40,330 --> 00:07:44,500 >> Теперь точка, точка, точка вид волн это руки у некоторых из сочнее деталей, 157 00:07:44,500 --> 00:07:46,452 но давайте просто идти вперед и упрощения. 158 00:07:46,452 --> 00:07:48,660 Если вы помните из высокого школа, честно говоря, многие из вас 159 00:07:48,660 --> 00:07:50,340 была математические книги, которые имели немного шпаргалка 160 00:07:50,340 --> 00:07:52,550 на обложке или задняя крышка, что показал вам, 161 00:07:52,550 --> 00:07:56,400 Суммирование что серия, как это в конечном счете складываются в. 162 00:07:56,400 --> 00:07:59,600 В общем случае, если у вас есть переменная, как п, и в самом деле это одно, 163 00:07:59,600 --> 00:08:01,634 если вы посмотрите на ваш старая школа математика книга, 164 00:08:01,634 --> 00:08:04,050 вы увидите, что это на самом деле добавляет до этой суммы здесь, 165 00:08:04,050 --> 00:08:07,970 п раз п минус 1 все деленное на число 2. 166 00:08:07,970 --> 00:08:11,172 Так что на данный позвольте мне просто предусматривают это верно, так на прыжок веры, 167 00:08:11,172 --> 00:08:12,880 это то, что это подводит до, и мы могли 168 00:08:12,880 --> 00:08:14,341 доказать, что в более общем случае. 169 00:08:14,341 --> 00:08:15,590 Но теперь давайте расширим это. 170 00:08:15,590 --> 00:08:19,920 Так что давайте умножим это, так вот н квадрат, минус п, все разделить на 2. 171 00:08:19,920 --> 00:08:23,200 Это действительно п квадрат, деленное на 2, минус п над 2, 172 00:08:23,200 --> 00:08:25,010 так что все хорошо и интересно. 173 00:08:25,010 --> 00:08:27,060 Но что произойдет, если мы Плагин значение? 174 00:08:27,060 --> 00:08:29,724 Предположим, у меня не было восемь люди, но сказать, миллион. 175 00:08:29,724 --> 00:08:31,890 И млн только потому, что это довольно большая сумма, 176 00:08:31,890 --> 00:08:34,039 давайте подключить, что в и посмотреть, что происходит. 177 00:08:34,039 --> 00:08:39,039 Так что, если я подключу млн в этой формуле Я иду, чтобы получить миллион квадрат, 178 00:08:39,039 --> 00:08:42,868 деленное на 2, минус млн, деленное на 2. 179 00:08:42,868 --> 00:08:44,159 Теперь то, что, что собирается равняться? 180 00:08:44,159 --> 00:08:47,354 Так 500000000000, минус 500 000. 181 00:08:47,354 --> 00:08:49,270 А если я на самом деле что математика, это означает, 182 00:08:49,270 --> 00:08:53,920 что сортировка миллион люди с пузырьковой сортировки 183 00:08:53,920 --> 00:09:01,800 может занять мне 499 999 500 000 шаги или сравнения в конце концов, 184 00:09:01,800 --> 00:09:02,900 мы просто экстраполяции. 185 00:09:02,900 --> 00:09:06,860 >> Это чувствует себя довольно медленно, но, честно говоря измерения один определенный вход 186 00:09:06,860 --> 00:09:09,160 как это, не все, что говорит о многом. 187 00:09:09,160 --> 00:09:14,050 Но на самом деле это означает, что к как п получает больше и больше, этот алгоритм 188 00:09:14,050 --> 00:09:16,280 вид чувствует себя хуже и хуже, или вы действительно 189 00:09:16,280 --> 00:09:20,450 начинают чувствовать боль, что возведение в степень, что п квадрат, 190 00:09:20,450 --> 00:09:21,770 который добавляет довольно быстро. 191 00:09:21,770 --> 00:09:25,340 И эта деталь не потерял на людей, на самом деле 192 00:09:25,340 --> 00:09:29,640 Несколько лет назад некий сенатор, который был агитация, сел на собеседование 193 00:09:29,640 --> 00:09:32,180 с Эриком компании Google Шмидт, генеральный директор в то время, 194 00:09:32,180 --> 00:09:36,380 и был брошен вызов с вопросом так же, как мы исследуем сегодня. 195 00:09:36,380 --> 00:09:38,468 Давайте взглянем. 196 00:09:38,468 --> 00:09:45,280 >> [ВИДЕОВОСПРОИЗВЕДЕНИЕ] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Что ты здесь в Google, и мне нравится 198 00:09:48,560 --> 00:09:53,382 думать о президентстве как собеседование. 199 00:09:53,382 --> 00:09:56,434 Теперь, это трудно получить работа в качестве президента, 200 00:09:56,434 --> 00:09:58,100 и вы собираетесь через суровые сейчас. 201 00:09:58,100 --> 00:10:01,860 Это также трудно получить работу в Google. 202 00:10:01,860 --> 00:10:05,490 У нас есть вопросы, и мы просим наших кандидатов вопросы, 203 00:10:05,490 --> 00:10:09,770 и этот от Ларри Швиммер. 204 00:10:09,770 --> 00:10:14,760 Что-- вы, ребята, думаете, что я шучу, это прямо здесь. 205 00:10:14,760 --> 00:10:17,930 Что является наиболее эффективным способом сортировать миллион 32-разрядных целых чисел? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -Прости, Maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Нет, нет, нет. 210 00:10:27,400 --> 00:10:30,700 Я думаю, что пузырь то будет неправильный путь. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Давай, Который сказал ему, этот? 213 00:10:38,180 --> 00:10:40,590 Я не видел компьютер наука в фоне. 214 00:10:40,590 --> 00:10:42,130 >> -Мы Получили наши шпионы там. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Давайте спросим отличается вопрос интервью. 217 00:10:48,444 --> 00:10:49,300 >> [END ВИДЕОВОСПРОИЗВЕДЕНИЕ] 218 00:10:49,300 --> 00:10:52,290 >> СПИКЕР: Так говорить о конкретные цифры, хотя, 219 00:10:52,290 --> 00:10:53,890 не собирается быть все, что полезно. 220 00:10:53,890 --> 00:10:56,810 Это не урок жизни, что пузырь сортировать, учитывая миллион входов, 221 00:10:56,810 --> 00:10:58,590 может занять целых 500 миллиардов шагов. 222 00:10:58,590 --> 00:11:01,120 Вы не можете действительно обобщить слишком эффективно от 223 00:11:01,120 --> 00:11:03,560 и принимать правильные решения дизайна при написании программ. 224 00:11:03,560 --> 00:11:07,070 Так что давайте хотя сосредоточиться на том, мы могли бы упростить этот результат. 225 00:11:07,070 --> 00:11:11,780 >> Так что я выделены желтым цветом здесь Результатом п деленное на квадрат 2, 226 00:11:11,780 --> 00:11:14,330 так млн квадрат деленное на 2, а затем 227 00:11:14,330 --> 00:11:16,710 Я выделил то, что Окончательный ответ был 228 00:11:16,710 --> 00:11:20,180 как только мы вычитается от п деленное на число 2. 229 00:11:20,180 --> 00:11:24,850 И претензии я собираюсь сделать сейчас, кто, черт возьми заботится если вычесть от 230 00:11:24,850 --> 00:11:30,060 немного старый п над 2, когда первый часть этой формулы является намного больше? 231 00:11:30,060 --> 00:11:33,910 Это доминирует над другим Термин, н квадрат разделен на 2 232 00:11:33,910 --> 00:11:37,510 так намного больше, ясно, как н становится большим, как миллион, 233 00:11:37,510 --> 00:11:41,450 что есть на самом деле большая разница в конец дня между 500000000000 234 00:11:41,450 --> 00:11:45,730 и 499 999 500 000? 235 00:11:45,730 --> 00:11:46,349 Не совсем. 236 00:11:46,349 --> 00:11:48,640 И так, что мы собираемся делать, как компьютерщики является 237 00:11:48,640 --> 00:11:53,270 игнорировать эти младшие члены и принять то, как это и действительно 238 00:11:53,270 --> 00:11:56,050 только упростить его, чтобы термин, который происходит с материей. 239 00:11:56,050 --> 00:12:00,315 Чем больше наши наборы данных получить, тем больше наши базы данных получить, тем больше веб-страниц 240 00:12:00,315 --> 00:12:02,690 мы должны искать, тем больше Друзья у вас есть на Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Как н становится больше, мы действительно будет заботиться о величине 242 00:12:07,340 --> 00:12:11,560 Термин в любом таком анализе наше выступление алгоритмы. 243 00:12:11,560 --> 00:12:16,230 И я собираюсь сказать, вы знаете, что, пузырьковой сортировки порядка большого O, 244 00:12:16,230 --> 00:12:18,060 порядка п квадрат. 245 00:12:18,060 --> 00:12:20,090 Это не совсем н квадрат, как мы видели, 246 00:12:20,090 --> 00:12:22,060 но кто действительно заботится о тех небольших точки, 247 00:12:22,060 --> 00:12:24,390 и, честно говоря, кто на самом деле разница, если мы делим на 2? 248 00:12:24,390 --> 00:12:25,870 Вот только постоянным фактором. 249 00:12:25,870 --> 00:12:29,480 И это 500 миллиардов против 250 млрд действительно, что большое дело? 250 00:12:29,480 --> 00:12:32,190 Я мог бы просто ждать один год, пусть мой ноутбук буквально 251 00:12:32,190 --> 00:12:34,810 получить в два раза быстрее в аппаратных средствах, и такого рода различия 252 00:12:34,810 --> 00:12:36,650 просто уходит естественным течением времени. 253 00:12:36,650 --> 00:12:39,300 >> То, что мы заботимся о том, выражение, часть 254 00:12:39,300 --> 00:12:42,489 выражения, что будет меняться в зависимости как наш вклад становится больше и больше. 255 00:12:42,489 --> 00:12:45,280 И в самом деле, в реальном мире, это то, что все больше происходит 256 00:12:45,280 --> 00:12:48,330 является вкладом в наши проблемы и алгоритмы становятся все больше. 257 00:12:48,330 --> 00:12:53,470 Настолько большой O будет обозначение, асимптотическое обозначение, что мы просто 258 00:12:53,470 --> 00:12:57,160 использовать как компьютерные специалисты, чтобы описать производительность, или время работы, 259 00:12:57,160 --> 00:12:58,130 алгоритма. 260 00:12:58,130 --> 00:13:00,800 Так что мы можем сравнить алгоритмы на разных компьютерах, написанных 261 00:13:00,800 --> 00:13:04,170 разными людьми, с помощью некоторые принципиально похожи метрика 262 00:13:04,170 --> 00:13:07,557 как числа сравнений вы решений, или, может быть, количество свопов 263 00:13:07,557 --> 00:13:08,140 вы делаете. 264 00:13:08,140 --> 00:13:11,910 >> То, что мы не собираемся количество представляет собой количество времени 265 00:13:11,910 --> 00:13:13,981 , который проходит по часам на стене обычно. 266 00:13:13,981 --> 00:13:16,230 То, что мы не собираемся беспокоиться о том, сколько памяти 267 00:13:16,230 --> 00:13:17,820 вы используете сегодня на мере, хотя это 268 00:13:17,820 --> 00:13:19,370 еще один ресурс, мы могли бы измерить. 269 00:13:19,370 --> 00:13:23,610 Мы собираемся, чтобы попытаться основывать наши анализы на только основные операции, те, 270 00:13:23,610 --> 00:13:25,930 честно говоря, что вы можете видеть наиболее визуально. 271 00:13:25,930 --> 00:13:30,700 Так что-то вроде большой O п квадрат, я утверждаю, что O н квадрат 272 00:13:30,700 --> 00:13:35,820 является верхней границей на так называемый время работы в пузырьковой сортировки. 273 00:13:35,820 --> 00:13:38,820 Другими словами, если вас хотел утверждать, что есть 274 00:13:38,820 --> 00:13:41,370 это верхний предел того, сколько шаги алгоритма может занять, 275 00:13:41,370 --> 00:13:46,240 это будет в большой O п квадрат в этом случае верхняя граница. 276 00:13:46,240 --> 00:13:49,710 >> Что делать, если я вместо изменить история была не о пузырьковой сортировки, 277 00:13:49,710 --> 00:13:50,910 но об этом верхняя граница. 278 00:13:50,910 --> 00:13:54,030 Можете ли вы назвать алгоритмом что мы смотрели на уже 279 00:13:54,030 --> 00:13:59,530 чья верхняя граница, максимум измерения времени или операций, 280 00:13:59,530 --> 00:14:04,300 будет называется ограниченным, по п, линейной функцией, 281 00:14:04,300 --> 00:14:07,260 не квадратичная, вот изогнутые? 282 00:14:07,260 --> 00:14:10,780 Что собой алгоритм, который всегда занимает не более 283 00:14:10,780 --> 00:14:12,860 чем как п шагов, или 2n шагов, или шаги 3n? 284 00:14:12,860 --> 00:14:13,360 Да? 285 00:14:13,360 --> 00:14:15,030 >> АУДИТОРИЯ: Поиск Наибольшее количество в списке? 286 00:14:15,030 --> 00:14:16,930 >> СПИКЕР: Совершенно, находя Наибольшее количество в списке. 287 00:14:16,930 --> 00:14:18,940 Если мне дадут список люди например, 288 00:14:18,940 --> 00:14:21,440 каждый из который держит ряд, что это максимальное число 289 00:14:21,440 --> 00:14:23,770 шагов он должен взять меня, разумно умный человек, 290 00:14:23,770 --> 00:14:27,530 найти наибольшее человека в этом списке? 291 00:14:27,530 --> 00:14:28,100 п, не так ли? 292 00:14:28,100 --> 00:14:31,320 Потому что в худшем случае, где может самая большая ценность быть? 293 00:14:31,320 --> 00:14:32,700 Право, всю дорогу в конце. 294 00:14:32,700 --> 00:14:34,575 Таким образом, в худшем случае Верхняя граница, я мог бы 295 00:14:34,575 --> 00:14:36,450 должны пройти весь путь здесь и сказать: 296 00:14:36,450 --> 00:14:39,170 ой, вот номер восемь, или что это значение. 297 00:14:39,170 --> 00:14:41,330 Теперь было бы просто глупо если я продолжал идти, не так ли? 298 00:14:41,330 --> 00:14:43,840 Глядя на все больше и больше элементов если последний из них находится там? 299 00:14:43,840 --> 00:14:45,340 Так, конечно,, п является верхней границей. 300 00:14:45,340 --> 00:14:47,420 Мне не нужно, чтобы взять больше шагов, чем это. 301 00:14:47,420 --> 00:14:51,580 >> Так что, если вместо этого я предложил, чтобы Есть алгоритмы в этом мире, что 302 00:14:51,580 --> 00:14:57,750 есть время, бегая Это ограничена большим O из журнала п, войдите н? 303 00:14:57,750 --> 00:15:00,390 Где мы видели этого раньше? 304 00:15:00,390 --> 00:15:00,890 Да? 305 00:15:00,890 --> 00:15:03,309 >> АУДИТОРИЯ: В задаче телефонной книги? 306 00:15:03,309 --> 00:15:04,850 СПИКЕР: Как проблемы телефонной книги. 307 00:15:04,850 --> 00:15:07,754 То, что было показателем того, насколько сколько времени или сколько слез IT 308 00:15:07,754 --> 00:15:10,170 взял меня, чтобы найти такого человека, как Майк Смит в телефонной книге? 309 00:15:10,170 --> 00:15:13,212 Мы утверждали, что это был журнал п, и даже если не знакомы или это 310 00:15:13,212 --> 00:15:15,170 немного туманно, что логарифм или показатель был, 311 00:15:15,170 --> 00:15:17,650 только помните, что § п как правило, относится к процессу, 312 00:15:17,650 --> 00:15:20,790 В этом случае деления то в половине снова, и снова, 313 00:15:20,790 --> 00:15:25,790 и снова, и снова, так что он получает все меньше и меньше, как и вы, что. 314 00:15:25,790 --> 00:15:28,470 >> Так войти н касается, конечно, к примеру телефонной книги, 315 00:15:28,470 --> 00:15:32,662 чтобы бинарного поиска в теории, когда мы были виртуальные двери на борту, 316 00:15:32,662 --> 00:15:34,370 или когда Шон был поисках чего-то. 317 00:15:34,370 --> 00:15:37,374 Если он используется бинарный поиск, войдите н будет верхняя граница, сколько 318 00:15:37,374 --> 00:15:38,040 время, которое требуется. 319 00:15:38,040 --> 00:15:44,027 Но эти алгоритмы, которые бежали в § п предполагается, какие ключевые детали? 320 00:15:44,027 --> 00:15:45,360 Это список был отсортирован, не так ли? 321 00:15:45,360 --> 00:15:47,789 Ваш алгоритм ошибается, если ваш вклад не сортируется, 322 00:15:47,789 --> 00:15:49,830 и еще вы используете что-то вроде бинарного поиска 323 00:15:49,830 --> 00:15:51,704 потому что вы можете прыгать прямо над элементом 324 00:15:51,704 --> 00:15:53,600 , не понимая, что это действительно есть. 325 00:15:53,600 --> 00:15:55,600 >> Теперь, что это может означать, Big O одного? 326 00:15:55,600 --> 00:15:59,117 Это не означает, что ваш алгоритм занимает один и только один шаг, 327 00:15:59,117 --> 00:16:01,200 это просто означает, что требуется постоянное число шагов. 328 00:16:01,200 --> 00:16:04,060 Может быть, это 1, может быть, это 10, может быть, это 1000, 329 00:16:04,060 --> 00:16:07,750 но это зависит от размер проблемы. 330 00:16:07,750 --> 00:16:10,850 Независимо от того, насколько большой п, постоянная алгоритм время 331 00:16:10,850 --> 00:16:12,747 всегда имеет то же самое число шагов. 332 00:16:12,747 --> 00:16:15,080 Так что может быть алгоритм мы говорили о или просто 333 00:16:15,080 --> 00:16:20,418 интуитивно, что приходит к вам, что всегда работает в так называемой постоянной времени? 334 00:16:20,418 --> 00:16:20,918 Да? 335 00:16:20,918 --> 00:16:22,001 >> АУДИТОРИЯ: Добавить два числа. 336 00:16:22,001 --> 00:16:25,320 СПИКЕР: Добавить два числа, 2 плюс 2 равняется 4, сделано. 337 00:16:25,320 --> 00:16:27,227 Так что может работать, что еще? 338 00:16:27,227 --> 00:16:28,560 Как насчет более реальном мире, да? 339 00:16:28,560 --> 00:16:30,686 >> АУДИТОРИЯ: Поиск Первое, что в списке. 340 00:16:30,686 --> 00:16:32,810 СПИКЕР: Поиск первым элемент в списке, конечно. 341 00:16:32,810 --> 00:16:34,540 Мы на самом деле говорил о массивах уже, 342 00:16:34,540 --> 00:16:36,540 как вы получите на Первый элемент в массиве, 343 00:16:36,540 --> 00:16:40,465 независимо от того, как долго массив на С? 344 00:16:40,465 --> 00:16:43,090 Вы просто использовать как кронштейн нулевой обозначения, бац, ты там. 345 00:16:43,090 --> 00:16:46,120 И действительно массивы, как в сторону, поддержка-то известно 346 00:16:46,120 --> 00:16:49,240 как случайного доступа, случайного доступа памяти, потому что вы можете буквально 347 00:16:49,240 --> 00:16:50,284 перейти в любое одном месте. 348 00:16:50,284 --> 00:16:52,700 Мы можем сделать это еще проще мы можем переместиться к нулевой неделе 349 00:16:52,700 --> 00:16:53,900 когда мы сделали нуля. 350 00:16:53,900 --> 00:16:59,707 Сколько времени потребуется для говорят блок в пустом выполнить? 351 00:16:59,707 --> 00:17:00,790 Просто постоянная времени, не так ли? 352 00:17:00,790 --> 00:17:03,960 Скажи что-нибудь, скажем то, это не имеет значения 353 00:17:03,960 --> 00:17:07,359 как большие царапины мир, это всегда собирается взять такое же количество времени 354 00:17:07,359 --> 00:17:08,490 просто сказать-то. 355 00:17:08,490 --> 00:17:11,089 >> Так вот постоянная времени, но то, что обратная сторона? 356 00:17:11,089 --> 00:17:13,030 Если бы это было верхняя границы, что, если мы хотим 357 00:17:13,030 --> 00:17:17,089 для описания нижние границы наших алгоритмов время работы? 358 00:17:17,089 --> 00:17:19,852 Почти лучшем случае потенциально, если хотите, 359 00:17:19,852 --> 00:17:23,060 хотя эти термины можно применить к лучшим Случаи, худших случаях средние случаи больше 360 00:17:23,060 --> 00:17:26,359 вообще, но давайте просто сосредоточиться на нижних границ в целом. 361 00:17:26,359 --> 00:17:31,920 Что собой алгоритм, который имеет нижняя граница п шагов, 362 00:17:31,920 --> 00:17:33,350 или 2n шагов, или шаги 3n? 363 00:17:33,350 --> 00:17:36,241 Некоторые фактор п шагов, вот его нижней границы. 364 00:17:36,241 --> 00:17:36,740 Да? 365 00:17:36,740 --> 00:17:37,910 >> АУДИТОРИЯ: Bubble рода? 366 00:17:37,910 --> 00:17:41,610 >> СПИКЕР: Bubble рода берет Вы минимально п шагов, то почему? 367 00:17:41,610 --> 00:17:42,279 Почему это? 368 00:17:42,279 --> 00:17:45,320 Почему, что начало приходить к вам интуитивно, даже если это не так просто 369 00:17:45,320 --> 00:17:46,530 еще? 370 00:17:46,530 --> 00:17:47,030 Да? 371 00:17:47,030 --> 00:17:47,990 >> АУДИТОРИЯ: [неразборчиво]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 СПИКЕР: Точно. 374 00:17:52,360 --> 00:17:55,810 В лучшем сценарии пузырьковой сортировки, и много алгоритмов 375 00:17:55,810 --> 00:17:58,769 если я вручаю вам восемь человек которые уже отсортированы, 376 00:17:58,769 --> 00:18:00,560 было бы глупо для вас, алгоритм, 377 00:18:00,560 --> 00:18:02,202 чтобы идти вперед и назад более чем один раз, не так ли? 378 00:18:02,202 --> 00:18:04,285 Потому что как только вы ходить по списку один раз, 379 00:18:04,285 --> 00:18:08,090 вы должны понимать, о, я сделал нет свопы, этот список сортируется, выход. 380 00:18:08,090 --> 00:18:09,700 Но что происходит, чтобы у вас н шаги. 381 00:18:09,700 --> 00:18:12,033 >> И наоборот, то, что еще один способ думать об этом? 382 00:18:12,033 --> 00:18:15,240 Bubble рода является омега, так сказать, из п, 383 00:18:15,240 --> 00:18:19,050 потому что если вы посмотрите на меньше, чем п элементов, то, что 384 00:18:19,050 --> 00:18:23,009 фундаментальный вопрос есть? 385 00:18:23,009 --> 00:18:24,550 Вы не знаете, если это сортируются, право. 386 00:18:24,550 --> 00:18:26,800 Мы люди могли взгляд на восьми люди и быть как, о, это сортируется, 387 00:18:26,800 --> 00:18:28,430 что меня не взяли н шаги, но это сделал. 388 00:18:28,430 --> 00:18:30,810 Твои глаза, хотя вас вид от того, имеют большое поле зрения, 389 00:18:30,810 --> 00:18:33,184 Вы смотрели на восьми элементов, Вы смотрели на восемь человек, 390 00:18:33,184 --> 00:18:34,610 вот восемь шагов эффективно. 391 00:18:34,610 --> 00:18:38,612 И только тогда, когда я иду через весь Список я понимаю, да, отсортировано. 392 00:18:38,612 --> 00:18:41,320 Если я останавливаться на полпути думать, все Право, это довольно сортируются до сих пор, 393 00:18:41,320 --> 00:18:42,520 каковы шансы, что это не Начиная? 394 00:18:42,520 --> 00:18:44,186 Что алгоритмы не будет правильным. 395 00:18:44,186 --> 00:18:46,250 Может быть быстрее, но неправильно. 396 00:18:46,250 --> 00:18:48,500 >> Так что теперь у нас есть способ описания нижние границы, 397 00:18:48,500 --> 00:18:49,710 и то, что о постоянном времени? 398 00:18:49,710 --> 00:18:54,565 Что собой алгоритм, который имеет более низкий ограничение на время его работы одного? 399 00:18:54,565 --> 00:18:58,350 1 шаг, 2 шага, 10 шагов, но постоянным, зависит от п, 400 00:18:58,350 --> 00:18:59,310 размер входа? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Да, в спину. 403 00:19:04,600 --> 00:19:05,309 >> АУДИТОРИЯ: Printf? 404 00:19:05,309 --> 00:19:06,183 СПИКЕР: Что это? 405 00:19:06,183 --> 00:19:07,184 АУДИТОРИЯ: Printf? 406 00:19:07,184 --> 00:19:07,850 СПИКЕР: Printf. 407 00:19:07,850 --> 00:19:08,400 ОК, уверен. 408 00:19:08,400 --> 00:19:10,720 Таким образом, это занимает фиксированное число шагов. 409 00:19:10,720 --> 00:19:13,170 И я должен now-- теперь, мы говорим о C кода 410 00:19:13,170 --> 00:19:16,040 а не к царапинам, то как скажем, с Printf, 411 00:19:16,040 --> 00:19:17,710 мы должны начать, чтобы получить осторожным. 412 00:19:17,710 --> 00:19:21,090 Поскольку Е действительно берет вход, это строка, 413 00:19:21,090 --> 00:19:23,220 и струны у технически имеют длину. 414 00:19:23,220 --> 00:19:25,530 Так что, если мы сейчас хотим, чтобы забрать на вас, если вы не возражаете, 415 00:19:25,530 --> 00:19:29,430 технически мы могли утверждать, что Printf действительно берет переменную длину входной, 416 00:19:29,430 --> 00:19:32,270 и, конечно, это может занять больше Время напечатать строку так долго, 417 00:19:32,270 --> 00:19:33,560 чем так долго. 418 00:19:33,560 --> 00:19:36,570 >> Так что, если мы рассматриваем только сортировка и поиск примеров? 419 00:19:36,570 --> 00:19:40,450 Как насчет Майка Смита в телефоне Книга, или бинарный поиск в более общем? 420 00:19:40,450 --> 00:19:42,220 В лучшем случае, что может случиться? 421 00:19:42,220 --> 00:19:45,577 Я открываю телефонную книгу и, бац, есть число Майка Смита. 422 00:19:45,577 --> 00:19:46,660 Я могу позвонить ему прямо сейчас. 423 00:19:46,660 --> 00:19:49,390 >> Взял один шаг, может быть, два шага, но постоянное число шагов 424 00:19:49,390 --> 00:19:50,230 если мне повезло. 425 00:19:50,230 --> 00:19:52,570 И, честно говоря, мы видели на Понедельник ваш одноклассник 426 00:19:52,570 --> 00:19:54,710 получить очень повезло два раза подряд. 427 00:19:54,710 --> 00:19:57,050 И это было действительно постоянной время в нижних границ 428 00:19:57,050 --> 00:20:01,280 от алгоритма в вопросе нахождения число 50 за тех, закрыт 429 00:20:01,280 --> 00:20:01,830 двери. 430 00:20:01,830 --> 00:20:06,400 >> Теперь, как в сторону, если вы обнаружите, что и большая O, верхняя граница, 431 00:20:06,400 --> 00:20:09,310 и омега, нижняя граница, один в том же, что 432 00:20:09,310 --> 00:20:11,830 является та же формула в скобки, вы также можете 433 00:20:11,830 --> 00:20:15,170 сказать, просто быть необычным, что-то не в тета 434 00:20:15,170 --> 00:20:18,270 н или тета некоторого другого значения. 435 00:20:18,270 --> 00:20:20,661 Это просто означает, когда большая Вывода и омега одинаковы. 436 00:20:20,661 --> 00:20:21,910 Теперь насчет выбора рода? 437 00:20:21,910 --> 00:20:23,400 Давайте использовать этот новый словарь. 438 00:20:23,400 --> 00:20:27,407 В селекции рода, то, что мы были делать снова, и снова, и снова? 439 00:20:27,407 --> 00:20:29,990 Я собирался туда и обратно через список, ищет кого? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Наименьшее число. 442 00:20:34,730 --> 00:20:37,560 >> Так как много шагов, как много сравнений я тоже 443 00:20:37,560 --> 00:20:43,250 должны сделать для того, чтобы выяснить, кто наименьший элемент в списке был? 444 00:20:43,250 --> 00:20:44,437 н минус 1, не так ли? 445 00:20:44,437 --> 00:20:47,770 Потому что, если я просто начать с того, что я нахожусь учитывая и я начинаю сравнивать его или ее, 446 00:20:47,770 --> 00:20:49,519 то ему или ей, как он или ей, ему или ей, я 447 00:20:49,519 --> 00:20:52,010 может только пару элементов вместе н минус 1 раз. 448 00:20:52,010 --> 00:20:55,630 Так выбор рода же берет н минус 1 шаги в первый раз. 449 00:20:55,630 --> 00:20:59,540 >> Сколько шагов нужно, чтобы я найти второй наименьший элемент? 450 00:20:59,540 --> 00:21:02,920 н минус 2, потому что я немой если я продолжаю смотреть на те же люди, 451 00:21:02,920 --> 00:21:06,280 снова, если я уже выбрали его или ее и положить их на место. 452 00:21:06,280 --> 00:21:09,270 И третий шаг, н минус 3, то п минус 4. 453 00:21:09,270 --> 00:21:11,020 Мы видели эту модель раньше, и на самом деле 454 00:21:11,020 --> 00:21:13,460 Выбор рода аналогично имеет верхнюю границу 455 00:21:13,460 --> 00:21:16,210 н квадрат, если мы делаем до, что суммирование. 456 00:21:16,210 --> 00:21:19,790 Какова его нижней границы, выбор рода? 457 00:21:19,790 --> 00:21:25,350 Минимально, сколько времени отбора должны Сортировать принять, как мы определили его в понедельник? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Предлагаю два варианта. 460 00:21:30,490 --> 00:21:32,360 Может быть, это п, как и раньше. 461 00:21:32,360 --> 00:21:35,040 Может быть, это н квадрат, как это Сейчас как верхняя грань. 462 00:21:35,040 --> 00:21:35,874 >> АУДИТОРИЯ: н квадрат. 463 00:21:35,874 --> 00:21:36,664 СПИКЕР: н квадрат. 464 00:21:36,664 --> 00:21:37,368 Почему? 465 00:21:37,368 --> 00:21:40,060 >> АУДИТОРИЯ: Потому что у вас есть определить [неразборчиво]. 466 00:21:40,060 --> 00:21:41,510 >> СПИКЕР: Точно. 467 00:21:41,510 --> 00:21:45,077 По крайней мере, как я определил выбор рода это было довольно наивно, продолжать идти, 468 00:21:45,077 --> 00:21:46,160 найти наименьший элемент. 469 00:21:46,160 --> 00:21:47,770 Пойдите опять, найти наименьший элемент. 470 00:21:47,770 --> 00:21:49,490 Пойдите опять, найти наименьший элемент. 471 00:21:49,490 --> 00:21:51,700 Там нет рода оптимизация в там, что 472 00:21:51,700 --> 00:21:54,350 может позвольте мне прервать после всего п или около шаги. 473 00:21:54,350 --> 00:21:57,080 Так действительно, выбор сортировать, омега п квадрат. 474 00:21:57,080 --> 00:22:00,667 >> Как насчет сортировку вставками, где я взял которые мне дали, и тогда я шлепнулся его 475 00:22:00,667 --> 00:22:01,750 или ее в нужном месте? 476 00:22:01,750 --> 00:22:04,958 Тогда я продолжил второго человека, шлепнулся его или ее в нужном месте. 477 00:22:04,958 --> 00:22:07,910 Тогда следующий человек, шлепнулся ему или ей в нужном месте. 478 00:22:07,910 --> 00:22:10,537 Обратите внимание, что это очень линейный, так сказать. 479 00:22:10,537 --> 00:22:12,620 Я прямой, я не ходит взад и вперед, 480 00:22:12,620 --> 00:22:16,080 Я никогда не оглядываясь назад действительно, но что происходит, когда я вставляю его 481 00:22:16,080 --> 00:22:20,302 или ей в начале Список, как мы сделали в понедельник? 482 00:22:20,302 --> 00:22:21,010 Что происходит? 483 00:22:21,010 --> 00:22:21,510 Да? 484 00:22:21,510 --> 00:22:23,122 АУДИТОРИЯ: [неразборчиво]. 485 00:22:23,122 --> 00:22:24,830 СПИКЕР: Да, была загвоздка, не так ли? 486 00:22:24,830 --> 00:22:26,746 Вы можете вспомнить из Ваши одноклассники, если они 487 00:22:26,746 --> 00:22:29,670 делали любое движение с их ноги, что была операция. 488 00:22:29,670 --> 00:22:33,610 Так что, если было три человека, здесь и новый человек принадлежал способ там, 489 00:22:33,610 --> 00:22:37,360 на долгий этап, как это, уверен, он или она может просто пойти до самого конца. 490 00:22:37,360 --> 00:22:40,074 Но если мы думаем о Компьютер и массив памяти, 491 00:22:40,074 --> 00:22:41,990 эти люди собираются придется перетасовать над 492 00:22:41,990 --> 00:22:43,260 чтобы освободить место для этого человека. 493 00:22:43,260 --> 00:22:46,930 И так, что п минус 1 shufflings, н минус 2 shufflings, п 494 00:22:46,930 --> 00:22:50,660 минус 3 shufflings является только отчасти происходит позади меня, не передо мной 495 00:22:50,660 --> 00:22:52,710 как и раньше, в некотором смысле. 499 00:22:52,557 --> 00:22:54,640 Теперь, как в сторону, и, как Вы, возможно, видели онлайн 500 00:22:54,640 --> 00:22:57,699 если вы начинаете ковыряться о виды, есть так много различных те, 501 00:22:57,699 --> 00:22:59,490 там, некоторые из них лучше, чем другие. 502 00:22:59,490 --> 00:23:02,200 Действительно, bogosort является одним что забавно смотреть вверх. 503 00:23:02,200 --> 00:23:06,650 Bogosort принимает набор цифры или сказать колоду карт, 504 00:23:06,650 --> 00:23:09,870 смешает случайным их, и проверяет, если они отсортированы. 505 00:23:09,870 --> 00:23:12,130 А если нет, делает это снова. 506 00:23:12,130 --> 00:23:14,140 А если нет, делает это снова. 507 00:23:14,140 --> 00:23:15,440 Если нет, делает это снова. 508 00:23:15,440 --> 00:23:17,060 Невероятно глупо. 509 00:23:17,060 --> 00:23:19,520 >> И в самом деле, если вы читаете как статьи Википедии, 510 00:23:19,520 --> 00:23:21,200 его прозвище глупо рода. 511 00:23:21,200 --> 00:23:25,180 Это в конечном счете сработает, надеюсь, достаточно времени, 512 00:23:25,180 --> 00:23:28,240 но это количество времени может занять довольно много времени. 513 00:23:28,240 --> 00:23:31,650 Так что, если я мог, давайте ускорить вещей по сравнению с, например Мэри Бет ранее, 514 00:23:31,650 --> 00:23:35,150 имея еще несколько элементов, но больше двух процессоров. 515 00:23:35,150 --> 00:23:37,100 Два человека, если вам был бы не против присоединиться ко мне. 516 00:23:37,100 --> 00:23:40,972 Как насчет 1 здесь, и давайте не go-- никого, вон там? 517 00:23:40,972 --> 00:23:41,722 Никто не там? 518 00:23:41,722 --> 00:23:42,221 Хорошо. 519 00:23:42,221 --> 00:23:44,190 Вы с черными рубашка, да, давай вниз. 520 00:23:44,190 --> 00:23:45,000 Ладно, как тебя зовут? 521 00:23:45,000 --> 00:23:45,720 >> АУДИТОРИЯ: Питер. 522 00:23:45,720 --> 00:23:46,100 >> СПИКЕР: Что это? 523 00:23:46,100 --> 00:23:46,766 >> АУДИТОРИЯ: Питер. 524 00:23:46,766 --> 00:23:49,450 СПИКЕР: Питер, Дэвид, приятно познакомиться. 525 00:23:49,450 --> 00:23:53,670 Хорошо, у нас есть Петр здесь, если вам хочу приехать на стол здесь. 526 00:23:53,670 --> 00:23:54,550 И как тебя зовут? 527 00:23:54,550 --> 00:23:55,216 >> АУДИТОРИЯ: Елена. 528 00:23:55,216 --> 00:23:55,970 СПИКЕР: Елена. 529 00:23:55,970 --> 00:23:57,030 ОК, приятно познакомиться. 530 00:23:57,030 --> 00:23:58,060 Елена встретите Питера. 531 00:23:58,060 --> 00:23:59,170 Питер, Елена. 532 00:23:59,170 --> 00:24:02,290 И мы должны Эндрю здесь также, пожалуйста. 533 00:24:02,290 --> 00:24:06,107 И ваша задача будет быть отсортировать колоду карт. 534 00:24:06,107 --> 00:24:08,190 И если не знакомы, палуба карт должны в конечном счете, 535 00:24:08,190 --> 00:24:11,064 быть отсортированы кое как это где мы сделаем клубы, то 536 00:24:11,064 --> 00:24:13,660 лопаты, то сердца и бриллианты, от туза как один, 537 00:24:13,660 --> 00:24:15,570 все, вплоть до короля. 538 00:24:15,570 --> 00:24:20,890 >> Карты я собираюсь дать вам собираются быть 52 в количестве. 539 00:24:20,890 --> 00:24:23,160 Мы собираемся аналогичным Время у вас, через минуту. 540 00:24:23,160 --> 00:24:26,410 Мы собираемся бросить Эндрю на экране здесь, 541 00:24:26,410 --> 00:24:28,170 таким образом, чтобы смотреть, как вы делаете это. 542 00:24:28,170 --> 00:24:31,070 И таким образом, что все это тем более видно, 543 00:24:31,070 --> 00:24:33,490 это карты, которые я получил на Амазонке. 544 00:24:33,490 --> 00:24:42,861 Так они уже случайно сортируются, и мы собираемся раз, когда вы. 545 00:24:42,861 --> 00:24:44,610 И мы собираемся держать его реальной на этот раз, 546 00:24:44,610 --> 00:24:47,820 так что мы собираемся попробовать оказать давление на вас потому что иначе это будет получить утомительно 547 00:24:47,820 --> 00:24:48,460 быстро. 548 00:24:48,460 --> 00:24:53,860 Если бы вы могли приступить к отсортировать 52 элементы вместе через некоторые средства, сейчас. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> И снова, как мы смотрим эти парни делают то, что, в конце концов, 551 00:25:07,180 --> 00:25:10,200 будет производить очевидно Результат, думаю, о действительно 552 00:25:10,200 --> 00:25:12,962 как они каждый делает это, как Вы могли бы описать его. 553 00:25:12,962 --> 00:25:15,045 Потому что опять же, это все процессы, алгоритмы 554 00:25:15,045 --> 00:25:17,090 что мы считаем само собой разумеющимся, как человек. 555 00:25:17,090 --> 00:25:22,349 Но вы, наверное, давно интуиция, задолго до вас, даже 556 00:25:22,349 --> 00:25:24,390 думал о взятии информатика класс вам 557 00:25:24,390 --> 00:25:27,223 возможно, имели интуицию с которые решить подобные проблемы. 558 00:25:27,223 --> 00:25:29,560 Но как только вы признаете паттерны и начать 559 00:25:29,560 --> 00:25:32,407 формализовать действия, с помощью которых вы решаете эти проблемы, 560 00:25:32,407 --> 00:25:35,490 Вы найдете, что вы можете решить много более интересным и гораздо сложнее 561 00:25:35,490 --> 00:25:39,190 проблемы быстро. 562 00:25:39,190 --> 00:25:42,351 Так кто из зрителей, что является по меньшей мере, один элемент алгоритма 563 00:25:42,351 --> 00:25:43,350 что они используют здесь? 564 00:25:43,350 --> 00:25:44,275 >> АУДИТОРИЯ: [неразборчиво] 565 00:25:44,275 --> 00:25:45,150 СПИКЕР: Что это? 566 00:25:45,150 --> 00:25:47,062 АУДИТОРИЯ: По костюме. 567 00:25:47,062 --> 00:25:47,770 СПИКЕР: По костюме. 568 00:25:47,770 --> 00:25:50,630 Итак, сначала они кластеризации все алмазы вместе 569 00:25:50,630 --> 00:25:52,560 по-видимому, все сердца вместе похоже, 570 00:25:52,560 --> 00:25:56,520 и так далее, без соблюдения для чисел на картах. 571 00:25:56,520 --> 00:26:00,900 И теперь они появляются, например, чтобы быть их сортировку по номеру. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Очень хорошо. 574 00:26:08,910 --> 00:26:12,370 >> Ладно, так что будет быть последним шагом, то здесь? 575 00:26:12,370 --> 00:26:16,950 После того, как у нас есть четыре отсортированные костюмы, что нам нужно сделать, чтобы четырех свай 576 00:26:16,950 --> 00:26:20,059 для достижения одной сортируются палубу, достаточно просто? 577 00:26:20,059 --> 00:26:21,350 Так что мы должны объединить их снова. 578 00:26:21,350 --> 00:26:25,160 >> Таким образом, есть интересная идея, что снова, полагаю, очень понятный даже 579 00:26:25,160 --> 00:26:28,140 если вы никогда бы не ударил что вид этикетки на нем. 580 00:26:28,140 --> 00:26:31,900 Это фундаментальное понятие деления проблема не в половину этого времени, 581 00:26:31,900 --> 00:26:33,410 но по крайней мере на четыре части. 582 00:26:33,410 --> 00:26:36,810 Решение в значительной степени принципиально идентичные проблемы 583 00:26:36,810 --> 00:26:40,480 изолированно друг от друга, , а затем объединить результаты. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 И, отлично, сделано. 586 00:26:50,140 --> 00:26:52,140 Хорошо, большая круглая аплодисментов, если мы могли. 587 00:26:52,140 --> 00:26:56,480 >> [Аплодисменты] 588 00:26:56,480 --> 00:26:59,740 >> СПИКЕР: Я понятия не имею, что вы будете делать с ними, но здесь вы идете. 589 00:26:59,740 --> 00:27:01,690 Спасибо большое. 590 00:27:01,690 --> 00:27:04,660 Итак, давайте посмотрим, две минуты и восемь секунд, 591 00:27:04,660 --> 00:27:07,490 если вы хотите, чтобы сразиться со своими друзьями. 592 00:27:07,490 --> 00:27:12,160 Что же тогда будет быть отнять от этого 593 00:27:12,160 --> 00:27:13,830 что мы можем использовать более общем? 594 00:27:13,830 --> 00:27:16,080 Ну, думаю, обратно в Этот массив чисел, 595 00:27:16,080 --> 00:27:19,060 и вспоминаю сейчас, чтобы некоторые из псевдокод мы написали в прошлом, 596 00:27:19,060 --> 00:27:22,080 и это было команд для решении проблемы телефонной книги. 597 00:27:22,080 --> 00:27:25,150 Причем в псевдокода I перечислил более методическую путь 598 00:27:25,150 --> 00:27:28,400 описания того, как я сделал очень интуитивный человек алгоритм деления телефон 599 00:27:28,400 --> 00:27:31,650 Книга в половине, повторите, повторяю, повторяю, пока я не найду такой человек, как Майк Смит, 600 00:27:31,650 --> 00:27:33,790 если он действительно находится в телефонной книге. 601 00:27:33,790 --> 00:27:37,610 >> Но я отчасти привык, что я называю очень итеративный подход здесь, 602 00:27:37,610 --> 00:27:42,160 в частности уведомления линия 8 и строка 11. 603 00:27:42,160 --> 00:27:46,750 Те, являются свидетельством итеративный подход, перекручивание подход, 604 00:27:46,750 --> 00:27:49,040 потому что это именно поведение они вызывают. 605 00:27:49,040 --> 00:27:52,910 Эти линии как бы, идут в Линия три, и вы можете рода 606 00:27:52,910 --> 00:27:55,140 думать о том, что в вашем мысленным взором как петля. 607 00:27:55,140 --> 00:27:59,080 Это говорю вам, чтобы вернуться до шага три и повторяю, снова, и снова, 608 00:27:59,080 --> 00:28:00,010 и снова. 609 00:28:00,010 --> 00:28:04,410 >> Но что, если мы использовать ключевую идею здесь, что мы сделали не в последний раз, 610 00:28:04,410 --> 00:28:10,280 и упростить линии 8 и строка 11 и их соседи 611 00:28:10,280 --> 00:28:12,840 как только это, в желтый цвет. 612 00:28:12,840 --> 00:28:16,480 Это не принципиально сокращения псевдокод очень много, 613 00:28:16,480 --> 00:28:20,530 но это в корне меняет природа моего алгоритма. 614 00:28:20,530 --> 00:28:24,220 То, что я сейчас говорю в пункте 7, на этапе 10, 615 00:28:24,220 --> 00:28:29,140 является поиск Mike в том же образом, 616 00:28:29,140 --> 00:28:31,580 но только в левой половина или правая половина. 617 00:28:31,580 --> 00:28:33,420 >> Таким образом, другими словами, если Я начинаю с шагом один, 618 00:28:33,420 --> 00:28:36,150 подобрать телефонную книгу, открыт до середины из телефонной книги, посмотреть на имена, 619 00:28:36,150 --> 00:28:39,010 если Смит является одним зовут, звоните Майк, еще 620 00:28:39,010 --> 00:28:44,340 если Смит ранее в книге, шаг семь искать Майка в левой половине книги. 621 00:28:44,340 --> 00:28:47,130 Но что это за чувство, это оставив меня висит, не так ли? 622 00:28:47,130 --> 00:28:49,240 В желтый, является инструкция, но как я могу 623 00:28:49,240 --> 00:28:51,870 искать Майка в левой половина телефонной книге? 624 00:28:51,870 --> 00:28:54,210 Где я должен Алгоритм, с которой я 625 00:28:54,210 --> 00:28:57,100 может искать такого человека, как Майк Смит? 626 00:28:57,100 --> 00:28:58,980 Ну, это смотря нам в глаза. 627 00:28:58,980 --> 00:29:03,090 Я могу буквально использовать точно такой же Программа эффективно, подойдя к верхней 628 00:29:03,090 --> 00:29:06,490 снова и снова работает те же строки кода. 629 00:29:06,490 --> 00:29:10,610 >> Таким образом, даже при том, что это должно чувствовать себя как немного циклического определения 630 00:29:10,610 --> 00:29:13,480 где вы отвечая кто- Вопрос по только вид с просьбой 631 00:29:13,480 --> 00:29:15,990 тот же вопрос снова, как, почему, почему, почему? 632 00:29:15,990 --> 00:29:21,580 Реальность такова, потому что мы жестко пару специальных линий, шаг 4, 633 00:29:21,580 --> 00:29:25,320 что, если, и шаг 12, которые эффективно другая ветвь, 634 00:29:25,320 --> 00:29:30,120 потому что у нас эти меры по устранению узких, этот алгоритм будет прекращена, если мы 635 00:29:30,120 --> 00:29:32,050 найти Майка, или если мы не делаем. 636 00:29:32,050 --> 00:29:36,810 Но в шаге 7 и 10 теперь, у нас есть что мы будем называть рекурсивный алгоритм. 637 00:29:36,810 --> 00:29:40,420 И рекурсия действительно мощная идея это немного умопомрачительным сначала, 638 00:29:40,420 --> 00:29:42,500 что теперь мы можем применить следующим образом. 639 00:29:42,500 --> 00:29:46,600 >> Слияние рода будет последним видом, который мы смотрим на, по крайней мере, в классе формально. 640 00:29:46,600 --> 00:29:50,040 И это в корне отличается от тех трех последних, и, конечно, 641 00:29:50,040 --> 00:29:52,140 Последние четыре, если мы включим bogosort. 642 00:29:52,140 --> 00:29:54,810 Вот псевдокод для сортировки слиянием. 643 00:29:54,810 --> 00:30:00,170 Когда на входе п элементов, поэтому, учитывая, массив размера N, если N меньше 2, 644 00:30:00,170 --> 00:30:01,040 вернуться. 645 00:30:01,040 --> 00:30:03,610 Так почему же я, что здравомыслие проверить в первую очередь? 646 00:30:03,610 --> 00:30:09,477 Что подразумевается если предам тебя массив, длина которого н меньше 2? 647 00:30:09,477 --> 00:30:11,060 Это уже отсортированы, очевидно, не так ли? 648 00:30:11,060 --> 00:30:13,640 Поскольку список либо имеет один элемент, который является тривиальным 649 00:30:13,640 --> 00:30:15,180 сортируются, потому что это Единственное, что есть. 650 00:30:15,180 --> 00:30:18,138 Или, это из нулевого размера, что означает нет ничего, чтобы разобраться, так по своей природе 651 00:30:18,138 --> 00:30:18,720 сортируется. 652 00:30:18,720 --> 00:30:20,410 Там просто ничего плохого там. 653 00:30:20,410 --> 00:30:22,310 Так вот наша так называемая базовый вариант. 654 00:30:22,310 --> 00:30:24,440 >> То есть близкий по духу к тому, что мы сделали с Майком. 655 00:30:24,440 --> 00:30:26,023 Если Майк в телефонной книге, позвоните ему. 656 00:30:26,023 --> 00:30:27,740 Если его там нет, сдаваться. 657 00:30:27,740 --> 00:30:31,240 Это так называемый базовый вариант, чтобы убедиться Этот алгоритм в конце дня 658 00:30:31,240 --> 00:30:33,540 остановится в определенных обстоятельствах. 659 00:30:33,540 --> 00:30:37,890 >> Но вот прыжок веры сейчас, иначе, сортировать левую половину элементов, 660 00:30:37,890 --> 00:30:39,740 затем отсортировать право половина элементов, 661 00:30:39,740 --> 00:30:41,189 а затем объединить отсортированные половинки. 662 00:30:41,189 --> 00:30:43,230 И вот, когда он чувствует себя как мы Copping из. 663 00:30:43,230 --> 00:30:46,900 Я попросил вас разобраться п элементов, и я 664 00:30:46,900 --> 00:30:50,712 говоря, хорошо, сделайте это с помощью сортировки влево и сортировки право. 665 00:30:50,712 --> 00:30:52,420 Но я говорю одно Другое дело, и это 666 00:30:52,420 --> 00:30:55,530 является ключевой темой кажется в интуиции до сих пор, 667 00:30:55,530 --> 00:30:57,380 есть этот третий этап слияния. 668 00:30:57,380 --> 00:31:00,430 Какой хотя его кажется настолько глуп в духе, 669 00:31:00,430 --> 00:31:02,320 как только объединить вещи вместе, кажется, 670 00:31:02,320 --> 00:31:05,380 является ключевым шагом на пути сборка из двух проблем, которые 671 00:31:05,380 --> 00:31:07,330 в конечном счете, были разделены на две части. 672 00:31:07,330 --> 00:31:12,090 >> Так сортировки слиянием, давайте сделаем это, если вы будете юмор меня, еще одним демонстрации, 673 00:31:12,090 --> 00:31:14,730 просто так, что у нас есть некоторые Номера работать. 674 00:31:14,730 --> 00:31:19,470 Могу ли я обменять восемь стресс мячи для восьми человек? 675 00:31:19,470 --> 00:31:29,320 Ладно, а как насчет вас три, вы четыре в этом разделе, пять, шесть, и давайте 676 00:31:29,320 --> 00:31:30,720 у 7, 8, давай до. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 ОК, да ОК. 679 00:31:36,520 --> 00:31:38,640 Минус 8, там мы идем, плюс 1. 680 00:31:38,640 --> 00:31:39,150 Отлично. 681 00:31:39,150 --> 00:31:42,000 Ладно давай, давайте быстро дать вам цифры. 682 00:31:42,000 --> 00:31:50,800 Номер два, номер три, номер четыре, номер пять, шесть, семь, восемь. 683 00:31:50,800 --> 00:31:52,140 Я правильно сделал восемь на этот раз. 684 00:31:52,140 --> 00:31:56,390 >> ОК, так что идти вперед, если бы мог, и давайте сортировать в первоначальном порядке 685 00:31:56,390 --> 00:31:59,810 что мы должны были вчера который выглядел как это, если вы не возражаете. 686 00:31:59,810 --> 00:32:03,620 И давайте сделаем это перед столом. 687 00:32:03,620 --> 00:32:06,510 Ладно, так сортировки слиянием. 688 00:32:06,510 --> 00:32:08,820 Это где это происходит чтобы получить вид интересного, 689 00:32:08,820 --> 00:32:12,800 потому что я, кажется, давая себя столько меньше информации сегодня. 690 00:32:12,800 --> 00:32:15,149 >> Так сортировка слиянием в первую очередь на входе п элементов, 691 00:32:15,149 --> 00:32:18,440 и, очевидно, не меньше двух, это восемь, так что я еще немного поработать. 692 00:32:18,440 --> 00:32:21,140 Так что теперь мысленно мы как класс теперь в еще отрасли, 693 00:32:21,140 --> 00:32:22,540 что означает три шага. 694 00:32:22,540 --> 00:32:25,017 Во-первых, у меня есть для сортировки Левая половина элементов. 695 00:32:25,017 --> 00:32:26,350 Так как же я идти об этом? 696 00:32:26,350 --> 00:32:28,950 Ну, я собираюсь вид мысленно разделить список здесь, 697 00:32:28,950 --> 00:32:30,700 Вы не должны физически двигаться, и я 698 00:32:30,700 --> 00:32:33,180 собираюсь сосредоточиться только на Левая половина элементов здесь. 699 00:32:33,180 --> 00:32:36,770 Так как я могу идти о сортировке Список теперь размера четыре? 700 00:32:36,770 --> 00:32:38,730 Что мой алгоритм? 701 00:32:38,730 --> 00:32:42,580 Сначала я проверить это н меньше двух, нет, так что я приступить к еще блок снова. 702 00:32:42,580 --> 00:32:43,900 Сортировать оставил половину элементов. 703 00:32:43,900 --> 00:32:45,608 >> Так что теперь снова, мысленно, и это, когда 704 00:32:45,608 --> 00:32:49,550 Вы должны начисляться много психическое история, если вы будете. 705 00:32:49,550 --> 00:32:51,940 Теперь я сортировке левую половина левой половине. 706 00:32:51,940 --> 00:32:57,000 Ладно, так что теперь я называю же слияние алгоритм сортировки, является н менее двух? 707 00:32:57,000 --> 00:33:00,590 Нет, это два, так что я должен разобраться левая половина, а правая половина. 708 00:33:00,590 --> 00:33:02,042 Поэтому здесь мы идем, сортировать левую половину. 709 00:33:02,042 --> 00:33:03,750 Почему бы вам просто не сделайте один шаг вперед. 710 00:33:03,750 --> 00:33:04,415 Как тебя зовут? 711 00:33:04,415 --> 00:33:04,860 >> АУДИТОРИЯ: Даррен. 712 00:33:04,860 --> 00:33:05,260 >> СПИКЕР: Дэн. 713 00:33:05,260 --> 00:33:06,040 Дэн вышел вперед. 714 00:33:06,040 --> 00:33:06,748 >> АУДИТОРИЯ: Даррен. 715 00:33:06,748 --> 00:33:09,000 , Сделано Даррен: СПИКЕР. 716 00:33:09,000 --> 00:33:10,090 Вы сказали Даррен или Дэн? 717 00:33:10,090 --> 00:33:10,550 >> АУДИТОРИЯ: Даррен. 718 00:33:10,550 --> 00:33:11,216 >> СПИКЕР: Даррен. 719 00:33:11,216 --> 00:33:14,422 ОК, Даррен активизировал вперед, и он теперь сортируется. 720 00:33:14,422 --> 00:33:16,130 И это почти бессмысленным требование, не так ли? 721 00:33:16,130 --> 00:33:18,862 Я действительно не кажется, достижения ничего, но давайте перейдем. 722 00:33:18,862 --> 00:33:20,820 Теперь позвольте мне разобраться право половина элементов. 723 00:33:20,820 --> 00:33:21,200 Как тебя зовут? 724 00:33:21,200 --> 00:33:21,690 >> АУДИТОРИЯ: Люк. 725 00:33:21,690 --> 00:33:22,273 >> СПИКЕР: Люк. 726 00:33:22,273 --> 00:33:23,400 Давай, шаг вперед. 727 00:33:23,400 --> 00:33:25,640 Урон, я сортируются Луки. 728 00:33:25,640 --> 00:33:28,570 Левая половина теперь сортируется и правая половина теперь сортируется, 729 00:33:28,570 --> 00:33:30,770 но опять же, есть ключевой шаг здесь. 730 00:33:30,770 --> 00:33:32,940 Что мне в следующем нужно сделать? 731 00:33:32,940 --> 00:33:33,941 Слияние отсортированные половинки. 732 00:33:33,941 --> 00:33:36,648 Теперь мы собираемся просто все назад и вперед на этом пути, 733 00:33:36,648 --> 00:33:38,620 потому что я вроде нужно некоторые рабочее пространство. 734 00:33:38,620 --> 00:33:40,411 Это почти как они ребята на столе, 735 00:33:40,411 --> 00:33:42,460 и мне нужна комната перемещать их на. 736 00:33:42,460 --> 00:33:44,170 Так что я собираюсь объединить вы, ребята, посмотрев 737 00:33:44,170 --> 00:33:45,960 на левой половине и в правой половине. 738 00:33:45,960 --> 00:33:48,740 И который, очевидно, стоит на первом месте, левая половина или правая половина? 739 00:33:48,740 --> 00:33:52,710 Так правая половина, так что давайте двигаться Луки над здесь в исходное положение Даррена. 740 00:33:52,710 --> 00:33:57,640 И теперь, чтобы объединить их левую половину в, Даррен собирается двигаться прямо там. 741 00:33:57,640 --> 00:33:59,750 >> Так чувствует себя почти пузырьковой сортировки эффект, 742 00:33:59,750 --> 00:34:02,482 но мое фундаментальное алгоритм, очень разные на этот раз. 743 00:34:02,482 --> 00:34:04,815 Но теперь, где вещи становятся немного раздражает, потому что вас 744 00:34:04,815 --> 00:34:06,810 должны перемотать умственно откуда я остановился. 745 00:34:06,810 --> 00:34:09,893 Я только что слил отсортированные половинки, который означает, что я, где в моем алгоритме? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Я должен разобраться правую половину, не так ли? 748 00:34:13,770 --> 00:34:15,910 >> Если вы перемотать, буквально на видео, вы будете 749 00:34:15,910 --> 00:34:18,339 видеть, что мы добрались до этого точка Луки и Дарреном 750 00:34:18,339 --> 00:34:21,370 путем сортировки левый половина левой половине. 751 00:34:21,370 --> 00:34:23,430 Тогда мы объединили те, отсортированные половинки, которые 752 00:34:23,430 --> 00:34:27,941 означает следующий шаг является своего рода Правая половина левой половине. 753 00:34:27,941 --> 00:34:29,649 Ладно, так что давайте сделать это быстрее. 754 00:34:29,649 --> 00:34:33,282 Ладно, шесть, я собираюсь утверждать, Вы теперь сортируются, давай вперед. 755 00:34:33,282 --> 00:34:33,990 Как тебя зовут? 756 00:34:33,990 --> 00:34:34,589 >> АУДИТОРИЯ: Адриано. 757 00:34:34,589 --> 00:34:35,200 >> СПИКЕР: Адриано. 758 00:34:35,200 --> 00:34:36,010 Адриано теперь сортируется. 759 00:34:36,010 --> 00:34:36,450 И как тебя зовут? 760 00:34:36,450 --> 00:34:37,080 >> АУДИТОРИЯ: Алекс. 761 00:34:37,080 --> 00:34:38,379 >> СПИКЕР: Алекс теперь сортируется. 762 00:34:38,379 --> 00:34:40,750 Левая половина, правая половина, что последний шаг? 763 00:34:40,750 --> 00:34:41,250 Слияние. 764 00:34:41,250 --> 00:34:44,310 Довольно тривиально, так что я собирается объединить в шесть, 765 00:34:44,310 --> 00:34:46,930 сделать шаг назад, восемь, сделать шаг назад. 766 00:34:46,930 --> 00:34:49,530 А теперь обратите внимание, это полезно вынос, что 767 00:34:49,530 --> 00:34:53,930 Сейчас правда о левой половине Список, независимо от того, как мы начали? 768 00:34:53,930 --> 00:34:55,090 Это сортируется. 769 00:34:55,090 --> 00:34:57,750 >> Теперь это не отсортированы в большой схеме вещей, 770 00:34:57,750 --> 00:35:00,250 но это сортируется независимо друг от друга из другой половины. 771 00:35:00,250 --> 00:35:04,100 Теперь то, что шаг я на, если я продолжу перемотки, как история началась? 772 00:35:04,100 --> 00:35:05,680 Теперь у меня есть для сортировки правую половину. 773 00:35:05,680 --> 00:35:07,630 Так что теперь мы путь назад в начало истории, 774 00:35:07,630 --> 00:35:08,921 и давайте сделаем это быстрее. 775 00:35:08,921 --> 00:35:11,320 Так что я собираюсь разобраться Правая половина всего списка. 776 00:35:11,320 --> 00:35:13,060 Какой следующий шаг? 777 00:35:13,060 --> 00:35:15,840 Сортировать левую половину правой половине. 778 00:35:15,840 --> 00:35:18,715 Сортировать левую половину Левая половина правой половине. 779 00:35:18,715 --> 00:35:19,590 И как тебя зовут? 780 00:35:19,590 --> 00:35:20,230 >> АУДИТОРИЯ: Омар. 781 00:35:20,230 --> 00:35:21,970 >> СПИКЕР: Омар, шаг вперед, сделать. 782 00:35:21,970 --> 00:35:22,860 Левая половина сортируется. 783 00:35:22,860 --> 00:35:23,330 И как тебя зовут? 784 00:35:23,330 --> 00:35:23,820 >> АУДИТОРИЯ: Крис. 785 00:35:23,820 --> 00:35:25,620 >> СПИКЕР: Крис, сделать шаг вперед, вы теперь сортируются. 786 00:35:25,620 --> 00:35:27,010 Что ключевой шаг сейчас? 787 00:35:27,010 --> 00:35:27,510 Слияние. 788 00:35:27,510 --> 00:35:30,509 Так никто не собирается сливаться в месте здесь, если бы вы могли сделать шаг назад, 789 00:35:30,509 --> 00:35:32,930 и три собирается сделать шаг назад, сливаются. 790 00:35:32,930 --> 00:35:38,080 Так левая половина Правая половина, теперь сортируется. 791 00:35:38,080 --> 00:35:41,747 Честно говоря, этот алгоритм чувствует, как мы тратите намного больше времени, чем раньше, 792 00:35:41,747 --> 00:35:44,830 но если бы мы сделали это в режиме реального времени, мы будем видеть то, что еды на дом будет. 793 00:35:44,830 --> 00:35:47,970 Итак, я здесь, прямо половина правой половине, 794 00:35:47,970 --> 00:35:50,170 позвольте мне идти вперед и отсортировать левую половину. 795 00:35:50,170 --> 00:35:51,482 Шаг вперед, как тебя зовут? 796 00:35:51,482 --> 00:35:52,190 АУДИТОРИЯ: Рэмси. 797 00:35:52,190 --> 00:35:53,210 СПИКЕР: Рэмси теперь сортируется. 798 00:35:53,210 --> 00:35:53,570 Как тебя зовут? 799 00:35:53,570 --> 00:35:54,200 >> АУДИТОРИЯ: Марина. 800 00:35:54,200 --> 00:35:57,033 >> СПИКЕР: Марина теперь сортируется как хорошо, если вы берете один шаг вперед. 801 00:35:57,033 --> 00:36:00,690 Ключ шаг здесь теперь сливаются, я собирается срывать с моих двух списков, 802 00:36:00,690 --> 00:36:01,720 слева и справа. 803 00:36:01,720 --> 00:36:05,150 Пять придет первым, и семь придет следующий. 804 00:36:05,150 --> 00:36:06,410 И опять же, это не случайно. 805 00:36:06,410 --> 00:36:08,535 Тот факт, что они берут шаги вперед и назад 806 00:36:08,535 --> 00:36:12,997 предназначена для представления, что мы не можем сделать этот алгоритм на месте, как легко 807 00:36:12,997 --> 00:36:15,830 как пузырьковой сортировки и отбора рода, и сортировка вставками, где мы просто 808 00:36:15,830 --> 00:36:16,960 хранится замены людей. 809 00:36:16,960 --> 00:36:19,940 Я буквально нужно своего рода из бумаги для заметок, в которых 810 00:36:19,940 --> 00:36:21,827 поставить этих людей в то время как я делаю слияние, 811 00:36:21,827 --> 00:36:23,410 и тогда я могу положить их на место. 812 00:36:23,410 --> 00:36:27,260 И это ключевой момент, потому я использую Новый ресурс, пространство, не только время. 813 00:36:27,260 --> 00:36:28,270 >> ОК, это удивительно. 814 00:36:28,270 --> 00:36:32,050 Левая половина сортируется, правой половине отсортированный, теперь, когда ключ слияния шаг. 815 00:36:32,050 --> 00:36:33,450 Как я буду объединить это? 816 00:36:33,450 --> 00:36:35,470 Так что если вы будете следовать моим левая рука и правая рука, 817 00:36:35,470 --> 00:36:38,930 Я собираюсь указать левую руку в левой половине, моя правая рука 818 00:36:38,930 --> 00:36:42,680 в правой половине, и теперь я должен решить, шаг за шагом, которого к слиянию в. 819 00:36:42,680 --> 00:36:44,650 Кто очевидно на первом месте? 820 00:36:44,650 --> 00:36:45,150 Номер один. 821 00:36:45,150 --> 00:36:47,327 Так иди сюда, вот наш сверхоперативной. 822 00:36:47,327 --> 00:36:49,910 Так что теперь номер один, и уведомление что я буду делать со своей правой рукой, 823 00:36:49,910 --> 00:36:54,152 Я собираюсь двигать правой рукой один перешагнуть указать номер три, 824 00:36:54,152 --> 00:36:55,860 и теперь я должен сделать то же самое решение. 825 00:36:55,860 --> 00:36:58,387 А на самом деле стоят права в Фронт Луки здесь, если бы вы могли, 826 00:36:58,387 --> 00:36:59,720 потому что это наш сверхоперативной. 827 00:36:59,720 --> 00:37:00,610 Так кто же дальше? 828 00:37:00,610 --> 00:37:05,000 У нас есть Луки с номер два или Крис с номером три. 829 00:37:05,000 --> 00:37:07,460 Очевидно Луки, число два, так что вы пришли сюда. 830 00:37:07,460 --> 00:37:11,270 >> Но моя левая рука теперь собирается быть увеличено, чтобы указать на Даррена, 831 00:37:11,270 --> 00:37:15,160 и вот ключ забрать с слияния, я собираюсь продолжать это делать, 832 00:37:15,160 --> 00:37:17,340 очевидно, если вас вид из следовать логике. 833 00:37:17,340 --> 00:37:19,670 Но мои руки никогда не собирается идти в обратном направлении, 834 00:37:19,670 --> 00:37:23,861 который означает, что я только когда переход к слева, с моей процесса слияния, 835 00:37:23,861 --> 00:37:26,360 и что будет ключом к наш анализ через минуту. 836 00:37:26,360 --> 00:37:27,859 >> А теперь давайте закончить это быстро. 837 00:37:27,859 --> 00:37:31,650 Так три будет дальше, затем четыре будет дальше, 838 00:37:31,650 --> 00:37:38,750 и теперь пять будет дальше, то шесть, и семь, и, наконец, восемь. 839 00:37:38,750 --> 00:37:42,960 По ощущениям самого медленного алгоритма пока нет, но не, если мы на самом деле 840 00:37:42,960 --> 00:37:45,510 запустить его на такой же тактовой частоты, таким образом, чтобы 841 00:37:45,510 --> 00:37:48,106 говорят, с тем же тикают часы, как и раньше. 842 00:37:48,106 --> 00:37:48,605 Почему? 843 00:37:48,605 --> 00:37:51,100 Ну, давайте посмотреть на конечный результат. 844 00:37:51,100 --> 00:37:56,990 >> Давайте вернемся сюда, пусть меня подтянуть демонстрацию визуально 845 00:37:56,990 --> 00:37:59,030 о том, что мы только что сделали. 846 00:37:59,030 --> 00:38:06,110 Масштабирование здесь, на этом страница здесь, рассказывая Firefox 847 00:38:06,110 --> 00:38:08,200 что мы хотим стоять в очереди в этой рамки, давайте 848 00:38:08,200 --> 00:38:11,260 сказать пузырьковую сортировку, с которой мы теперь хорошо знакомы, 849 00:38:11,260 --> 00:38:14,130 Выбор рода, что является еще одним довольно просто один, 850 00:38:14,130 --> 00:38:18,250 и теперь сегодняшняя сортировка слиянием, которая будет нашим климатические окончание. 851 00:38:18,250 --> 00:38:21,530 Причина это заняло так много больше здесь с людьми и мне устно это, 852 00:38:21,530 --> 00:38:23,480 Очевидно, я объясняю каждый шаг. 853 00:38:23,480 --> 00:38:26,920 Но если вы просто выполнить это, гораздо как мы делали пузырьковой сортировки и выбора 854 00:38:26,920 --> 00:38:30,890 сортировки не только визуально, часы насколько более эффективно 855 00:38:30,890 --> 00:38:33,330 это вовлечение в работу разделение и завоевание 856 00:38:33,330 --> 00:38:39,150 может быть при применении к набору данных, это даже не размер восемь, но даже много, 857 00:38:39,150 --> 00:38:39,970 намного больше. 858 00:38:39,970 --> 00:38:44,585 Я даю вам сортировка слиянием, бок о стороне с этими другими алгоритмами. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Это будет получить больно быстро, и концовка 861 00:38:58,530 --> 00:39:00,890 не особенно климатические, они просто в конечном итоге сортируются. 862 00:39:00,890 --> 00:39:05,280 Но ключ отнять то, что Посмотрите, насколько быстрее сортировка слиянием 863 00:39:05,280 --> 00:39:08,110 было, если вы не думаете, что я только отчасти возиться с вами. 864 00:39:08,110 --> 00:39:13,100 Если мы делаем это в последний раз, давайте Перезагрузить, давайте вернемся 865 00:39:13,100 --> 00:39:14,960 и выбрать пузырьковую сортировку, и только для ударов, 866 00:39:14,960 --> 00:39:17,330 давайте выберем вставку сортировать, для ровного счета. 867 00:39:17,330 --> 00:39:20,020 И на этот раз снова, давайте выбрать сортировка слиянием и давайте 868 00:39:20,020 --> 00:39:21,595 реально работать эти бок о бок. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> И это не так, на самом деле, счастливая случайность. 871 00:39:26,930 --> 00:39:31,140 То, что я эффективно сделать это у меня есть разделил свой вклад в половине, снова, 872 00:39:31,140 --> 00:39:32,240 и снова, и снова. 873 00:39:32,240 --> 00:39:35,590 И есть только так много раз, вы можете разделить вход пополам, слева 874 00:39:35,590 --> 00:39:36,240 и право. 875 00:39:36,240 --> 00:39:39,425 Что формула, что мы все время вижу , который описывает разделение пополам 876 00:39:39,425 --> 00:39:41,050 снова, и снова, и снова, и снова? 877 00:39:41,050 --> 00:39:41,890 >> АУДИТОРИЯ: Войти н. 878 00:39:41,890 --> 00:39:42,760 >> СПИКЕР: Войти н. 879 00:39:42,760 --> 00:39:46,300 Но тогда есть еще один ключевой шаг, этот алгоритм не войти п шагов. 880 00:39:46,300 --> 00:39:48,992 Если бы это было только войти п шагов, мы были бы в той же проблемы 881 00:39:48,992 --> 00:39:51,200 как и раньше, где мы не можем быть что все в сортируются. 882 00:39:51,200 --> 00:39:54,480 Вы должны минимально посмотреть на п элементов чтобы убедиться, что п элементов сортируются, 883 00:39:54,480 --> 00:39:55,950 в противном случае это прыжок веры. 884 00:39:55,950 --> 00:39:59,810 >> Так что это минимально журнал п шагов, но что по этому поводу ключевой стадии слияния 885 00:39:59,810 --> 00:40:04,370 где я слились моя левая половина и право половина и прошелся по сцене? 886 00:40:04,370 --> 00:40:06,980 Сколько шагов в том, что для слияния? 887 00:40:06,980 --> 00:40:10,150 Это п, но я не сделал всего объединить в последний раз. 888 00:40:10,150 --> 00:40:15,089 На каждой из этих вложенных вызовов, на каждом из тех, вложенных слияний, я до сих пор сортируются. 889 00:40:15,089 --> 00:40:18,380 Я объединены эти два парня, то эти два ребята, то эти два парня и так далее. 890 00:40:18,380 --> 00:40:19,955 >> Так что я слияния снова, и снова. 891 00:40:19,955 --> 00:40:20,580 Сколько раз? 892 00:40:20,580 --> 00:40:23,510 Так что каждый раз я разделил Список пополам, я сделал слияния. 893 00:40:23,510 --> 00:40:25,460 Разбейте список пополам, сделать слияние. 894 00:40:25,460 --> 00:40:28,570 Так что, если разделяющая список можно сделать журнал п раз, 895 00:40:28,570 --> 00:40:33,880 и слияние в конечном счете, принимает п шаги, что может быть сейчас верхняя 896 00:40:33,880 --> 00:40:37,000 ограничение на работающем Время нашего алгоритма? 897 00:40:37,000 --> 00:40:37,980 н войти н. 898 00:40:37,980 --> 00:40:40,560 >> И в самом деле, вот что мы достигли здесь. 899 00:40:40,560 --> 00:40:44,650 Так чувство, что вы видите визуально, когда эти три вещи работать бок о бок 900 00:40:44,650 --> 00:40:47,930 является н квадрат против п квадрат против н журнала п. 901 00:40:47,930 --> 00:40:51,010 Какие принципиально мы увидим, не только сегодня, но в будущем, 902 00:40:51,010 --> 00:40:52,760 гораздо, гораздо быстрее. 903 00:40:52,760 --> 00:40:56,010 Аплодисменты для этих ребят, Я вознаградит их со стрессом шаров. 904 00:40:56,010 --> 00:41:00,260 Давайте прервать здесь сегодня, и мы будем видеть вас в понедельник. 905 00:41:00,260 --> 00:41:02,255