1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Музыка Воспроизведение] 3 00:00:10,800 --> 00:00:13,500 DAVID МАЛАН: Хорошо. 4 00:00:13,500 --> 00:00:14,670 Ладно, с возвращением. 5 00:00:14,670 --> 00:00:18,120 Так что это 4-я неделя, начало его, уже. 6 00:00:18,120 --> 00:00:21,320 И вы помните, что на прошлой неделе, мы ставим код отведенных для только немного 7 00:00:21,320 --> 00:00:24,240 и мы начали говорить немного больше высоком уровне, о таких вещах 8 00:00:24,240 --> 00:00:28,130 поиск и сортировка, которая хотя и несколько простых идей, являются 9 00:00:28,130 --> 00:00:31,840 представитель класса задач Вы начнете решать особенно 10 00:00:31,840 --> 00:00:34,820 как вы начинаете думать об окончательном проекты и интересные решения, которые вы 11 00:00:34,820 --> 00:00:36,760 возможно, придется реальных проблем. 12 00:00:36,760 --> 00:00:39,490 Теперь пузырьковой сортировки был одним из самых простых такие алгоритмы, и это 13 00:00:39,490 --> 00:00:42,900 работал при наличии этих небольших количествах в виде списка или в виде массива 14 00:00:42,900 --> 00:00:46,530 Пузырь их путь к вершине, и большие числа переместить свой путь к 15 00:00:46,530 --> 00:00:47,930 К концу этого списка. 16 00:00:47,930 --> 00:00:50,650 >> И напомнить, что мы могли представлять пузырьковая сортировка немного 17 00:00:50,650 --> 00:00:52,310 что-то вроде этого. 18 00:00:52,310 --> 00:00:53,640 Итак, позвольте мне идти вперед и нажмите кнопку Пуск. 19 00:00:53,640 --> 00:00:55,350 Я предварительно пузырьковой сортировки. 20 00:00:55,350 --> 00:00:58,920 А если вспомнить, что выше синий линии представляют большие номера, небольшие 21 00:00:58,920 --> 00:01:03,300 Синие линии представляют собой небольшие номера, а мы проходим через это снова и снова и 22 00:01:03,300 --> 00:01:07,680 снова, сравнивая два бара рядом друг другие в красном, мы собираемся, чтобы поменять 23 00:01:07,680 --> 00:01:11,010 большой и минимальным, если они вышли из строя. 24 00:01:11,010 --> 00:01:14,150 >> Так что это будет продолжаться и продолжаться и идти на, и вы увидите, что чем больше 25 00:01:14,150 --> 00:01:16,700 элементы вносят свой путь к вправо, а более мелкие элементы являются 26 00:01:16,700 --> 00:01:17,900 пробираются влево. 27 00:01:17,900 --> 00:01:21,380 Но мы начали количественно эффективностью, 28 00:01:21,380 --> 00:01:22,970 Качество этого алгоритма. 29 00:01:22,970 --> 00:01:25,200 И мы сказали, что в худшем случае, этот алгоритм взял 30 00:01:25,200 --> 00:01:27,940 примерно сколько шагов? 31 00:01:27,940 --> 00:01:28,980 >> Таким N квадрате. 32 00:01:28,980 --> 00:01:30,402 И то, что было N? 33 00:01:30,402 --> 00:01:31,650 >> АУДИТОРИЯ: число элементов. 34 00:01:31,650 --> 00:01:32,790 >> DAVID МАЛАН: Так было N число элементов. 35 00:01:32,790 --> 00:01:33,730 И поэтому мы будем делать это часто. 36 00:01:33,730 --> 00:01:36,650 Каждый раз, когда мы хотим говорить о размерах проблема или размер 37 00:01:36,650 --> 00:01:39,140 вход, или количество времени, необходимое для получения выходных, мы просто 38 00:01:39,140 --> 00:01:41,610 обобщенной все вход как н. 39 00:01:41,610 --> 00:01:45,970 Итак, вернемся к неделе 0, количество страниц В телефонной книге была N. 40 00:01:45,970 --> 00:01:47,550 Количество студентов в комнате с. 41 00:01:47,550 --> 00:01:49,630 Так и здесь, мы следуем этой модели. 42 00:01:49,630 --> 00:01:52,800 >> Теперь н квадрат не является особенно быстро, так что мы попытались сделать лучше. 43 00:01:52,800 --> 00:01:55,970 И так мы смотрели на пару другие алгоритмы, среди которых 44 00:01:55,970 --> 00:01:57,690 были сортировка выбором. 45 00:01:57,690 --> 00:01:59,180 Так что выбор был Сортировать немного по-другому. 46 00:01:59,180 --> 00:02:03,130 Это было почти простой, я осмелюсь сказать, которого я начал в начале 47 00:02:03,130 --> 00:02:06,740 Список наших волонтеров, и я просто снова и снова и снова прошел через 48 00:02:06,740 --> 00:02:10,060 списке, выщипывание наименьшим элемента за один раз и положить его или 49 00:02:10,060 --> 00:02:13,040 ее в начале списка. 50 00:02:13,040 --> 00:02:16,410 >> Но и это, как только мы начали думать через математику и больше 51 00:02:16,410 --> 00:02:19,860 картину, думал о том, сколько раз Я шел назад и вперед и назад 52 00:02:19,860 --> 00:02:24,090 и вперед, мы сказали, в худшем случае, Выбор рода тоже было что? 53 00:02:24,090 --> 00:02:24,960 N в квадрат. 54 00:02:24,960 --> 00:02:27,490 В настоящее время в реальном мире, она может на самом деле быть быстрее. 55 00:02:27,490 --> 00:02:30,620 Потому что опять же, у меня не было держать отступает, как только я сортировал 56 00:02:30,620 --> 00:02:31,880 мельчайших элементов. 57 00:02:31,880 --> 00:02:35,090 Но если мы думаем об очень больших N, и Если вы как бы сделать из математики как 58 00:02:35,090 --> 00:02:39,170 Я сделал на борту, с N квадрат минус что-то, все остальное 59 00:02:39,170 --> 00:02:41,850 Кроме того, N квадратов, как только N становится действительно большим, не 60 00:02:41,850 --> 00:02:42,850 имеет большого значения, как много. 61 00:02:42,850 --> 00:02:45,470 Так как компьютерные ученые, мы вроде как закрывать глаза на меньшие 62 00:02:45,470 --> 00:02:49,220 факторы и фокус только на фактор Выражение, которое собирается сделать 63 00:02:49,220 --> 00:02:50,330 Самая большая разница. 64 00:02:50,330 --> 00:02:52,840 >> Ну, наконец, мы смотрели на сортировку вставками. 65 00:02:52,840 --> 00:02:56,620 И это было близки по духу, но а не проходить через итеративно и 66 00:02:56,620 --> 00:03:01,250 выбрать наименьший элемент по одному время, я вместо этого взял руку, что я 67 00:03:01,250 --> 00:03:04,070 был нанесен, и я решила, все Хорошо, ты здесь останешься. 68 00:03:04,070 --> 00:03:06,160 Затем я перешел к следующему элементу и решил, что он или 69 00:03:06,160 --> 00:03:07,470 она принадлежала здесь. 70 00:03:07,470 --> 00:03:08,810 А потом я переехал дальше и дальше. 71 00:03:08,810 --> 00:03:11,780 И я мог бы, чтобы, по пути, перейти эти парни для того, чтобы 72 00:03:11,780 --> 00:03:13,030 освободить место для них. 73 00:03:13,030 --> 00:03:16,880 Так, чтобы был своего рода ментальный разворот отбора вроде тех, что мы 74 00:03:16,880 --> 00:03:18,630 называется сортировка вставками. 75 00:03:18,630 --> 00:03:20,810 >> Таким образом, эти темы возникают в реальном мире. 76 00:03:20,810 --> 00:03:23,640 Всего несколько лет назад, когда определенные Сенатор был баллотироваться на пост президента, 77 00:03:23,640 --> 00:03:27,160 Эрик Шмидт, в то время генеральный директор Google, на самом деле имели возможность 78 00:03:27,160 --> 00:03:28,040 взять у него интервью. 79 00:03:28,040 --> 00:03:32,010 И мы подумали, что мы разделим эту YouTube Зажим для вас здесь, если бы мы могли повернуть вверх 80 00:03:32,010 --> 00:03:32,950 громкости. 81 00:03:32,950 --> 00:03:39,360 >> [ВОСПРОИЗВЕДЕНИЕ ВИДЕО] 82 00:03:39,360 --> 00:03:44,620 >> -Теперь, сенатор, вы здесь, в Google, и мне нравится думать президентства 83 00:03:44,620 --> 00:03:46,042 как собеседование. 84 00:03:46,042 --> 00:03:47,770 >> [Смеется] 85 00:03:47,770 --> 00:03:50,800 >> -Теперь это трудно получить работа в качестве президента. 86 00:03:50,800 --> 00:03:52,480 И вы проходите суровости сейчас. 87 00:03:52,480 --> 00:03:54,330 Это также трудно устроиться на работу в Google. 88 00:03:54,330 --> 00:03:59,610 У нас есть вопросы, и мы просим нашим кандидатам вопросы. 89 00:03:59,610 --> 00:04:02,250 И на этот раз от Ларри Швиммер. 90 00:04:02,250 --> 00:04:05,325 >> [Смеется] 91 00:04:05,325 --> 00:04:06,400 -Вы, ребята, думаете, я шучу? 92 00:04:06,400 --> 00:04:08,750 Это прямо здесь. 93 00:04:08,750 --> 00:04:12,110 Что является наиболее эффективным способом сортировать миллион двести-разрядных целых чисел? 94 00:04:12,110 --> 00:04:15,810 >> [Смеется] 95 00:04:15,810 --> 00:04:18,260 >> -Ну, ну - 96 00:04:18,260 --> 00:04:19,029 >> -Прости. 97 00:04:19,029 --> 00:04:19,745 Может быть, мы должны - 98 00:04:19,745 --> 00:04:21,000 >> -Нет, нет, нет, нет, нет. 99 00:04:21,000 --> 00:04:21,470 >> -Это не - 100 00:04:21,470 --> 00:04:22,185 ОК. 101 00:04:22,185 --> 00:04:25,328 >> -Я думаю, что пузырьковая сортировка бы быть неправильный путь. 102 00:04:25,328 --> 00:04:26,792 >> [Смеется] 103 00:04:26,792 --> 00:04:28,510 >> [ПРИВЕТСТВИЕ И аплодисменты] 104 00:04:28,510 --> 00:04:31,211 >> -Давай, который сказал ему это? 105 00:04:31,211 --> 00:04:32,155 ОК. 106 00:04:32,155 --> 00:04:33,350 >> [КОНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] 107 00:04:33,350 --> 00:04:35,070 >> DAVID МАЛАН: Так что у вас есть. 108 00:04:35,070 --> 00:04:39,600 Таким образом, мы начали дать количественную оценку этим работает раз, так сказать, с чем-то 109 00:04:39,600 --> 00:04:43,480 называется асимптотическим обозначение, которое просто ссылаясь на наш вид поворота 110 00:04:43,480 --> 00:04:47,420 закрывать глаза на эти факторы и меньше Только глядя на время работы, 111 00:04:47,420 --> 00:04:51,250 производительность этих алгоритмов, как н становится действительно большим с течением времени. 112 00:04:51,250 --> 00:04:55,110 И поэтому мы ввели большое О. И Big O представлено то, что мы думали, 113 00:04:55,110 --> 00:04:57,000 как верхнюю границу. 114 00:04:57,000 --> 00:04:59,570 А на самом деле, Барри, мы можем снизить , чем микрофон немного? 115 00:04:59,570 --> 00:05:01,040 >> Мы думали об этом является верхней границей. 116 00:05:01,040 --> 00:05:04,710 Так Big O п квадрат означает, что в худшем случае, что-то вроде 117 00:05:04,710 --> 00:05:07,780 Выбор рода возьмет п квадрат шагов. 118 00:05:07,780 --> 00:05:10,310 Или что-то вроде сортировки вставками бы квадрат N шагов. 119 00:05:10,310 --> 00:05:15,150 Теперь за то, как вставки , смотрите, какое было в худшем случае? 120 00:05:15,150 --> 00:05:18,200 Дан массив, что самое худшее возможные сценарии, которые могут оказаться 121 00:05:18,200 --> 00:05:20,650 окажетесь перед? 122 00:05:20,650 --> 00:05:21,860 >> Это совершенно в обратном направлении, не так ли? 123 00:05:21,860 --> 00:05:24,530 Потому что, если это совершенно в обратном направлении, что вам нужно сделать много работы. 124 00:05:24,530 --> 00:05:26,420 Потому что, если вы совершенно в обратном направлении, Вы собираетесь найти 125 00:05:26,420 --> 00:05:28,840 крупнейшим элементом здесь, хотя он принадлежит там. 126 00:05:28,840 --> 00:05:31,140 Так что вы собираетесь сказать, все правильно, по данный момент времени, ты здесь останешься, 127 00:05:31,140 --> 00:05:32,310 так что вы оставить его в покое. 128 00:05:32,310 --> 00:05:35,425 >> Тогда вы понимаете, черт побери, я должен переместить этот немного меньший элемент 129 00:05:35,425 --> 00:05:36,470 Слева от вас. 130 00:05:36,470 --> 00:05:38,770 Тогда я должен сделать это снова и снова и снова. 131 00:05:38,770 --> 00:05:41,410 И если бы я ходил взад и вперед, вы уладит чувствую производительность 132 00:05:41,410 --> 00:05:45,540 , что алгоритм, потому что я постоянно перетасовка все остальные вниз в 133 00:05:45,540 --> 00:05:46,510 массив, чтобы освободить место для него. 134 00:05:46,510 --> 00:05:47,750 Так что это в худшем случае. 135 00:05:47,750 --> 00:05:48,570 >> В отличие от этого - 136 00:05:48,570 --> 00:05:50,320 и это было захватывающим последний раз - 137 00:05:50,320 --> 00:05:54,065 мы говорили, что сортировка вставками был омега чего? 138 00:05:54,065 --> 00:05:57,530 Какой самый лучший случай ход время сортировки вставками? 139 00:05:57,530 --> 00:05:58,520 Так это на самом деле п. 140 00:05:58,520 --> 00:06:00,980 Это был пустой, что мы оставили на доске последний раз. 141 00:06:00,980 --> 00:06:03,160 >> И это омега п, так почему? 142 00:06:03,160 --> 00:06:06,630 Ну, в самом лучшем случае, что сортировка вставками будет передан? 143 00:06:06,630 --> 00:06:09,830 Ну, список, который все полностью отсортированный уже, минимальная работа. 144 00:06:09,830 --> 00:06:12,460 Но то, что волшебное в том, сортировки вставкой является то, что, поскольку он начинается здесь и 145 00:06:12,460 --> 00:06:15,340 решает, О, ты числа Один из них, ты здесь останешься. 146 00:06:15,340 --> 00:06:16,970 Ах, какое счастье. 147 00:06:16,970 --> 00:06:17,740 >> Ты номер два. 148 00:06:17,740 --> 00:06:19,030 Вы также принадлежат здесь. 149 00:06:19,030 --> 00:06:21,010 Номер три, еще лучше, Вам стоит к нам. 150 00:06:21,010 --> 00:06:25,210 Как только он попадает в конце Список, на сортировку вставками в псевдокоде 151 00:06:25,210 --> 00:06:28,010 , что мы шли в вербально Последний раз, это делается. 152 00:06:28,010 --> 00:06:32,790 Однако выбор вида, напротив, продолжал делать то, что? 153 00:06:32,790 --> 00:06:35,260 >> Продолжал идти по списку снова и снова и снова. 154 00:06:35,260 --> 00:06:39,160 Поскольку ключевое понимание было только Как только вы смотрели все пути к 155 00:06:39,160 --> 00:06:42,500 конце списка вы можете быть уверены что элемент был выбран 156 00:06:42,500 --> 00:06:45,560 Действительно в настоящее время наименьший элемент. 157 00:06:45,560 --> 00:06:48,920 Таким образом, эти различные психические моделях до получения некоторых очень реальным 158 00:06:48,920 --> 00:06:53,130 различия для нас, а также эти теоретические асимптотической различия. 159 00:06:53,130 --> 00:06:56,910 >> Так просто, чтобы резюмировать, то, Big O п квадрат, мы видели несколько таких 160 00:06:56,910 --> 00:06:58,350 алгоритмов до сих пор. 161 00:06:58,350 --> 00:06:59,580 Big O п? 162 00:06:59,580 --> 00:07:02,870 Что алгоритм, способный назвать Big O п? 163 00:07:02,870 --> 00:07:06,930 В худшем случае, она занимает линейный число шагов. 164 00:07:06,930 --> 00:07:07,810 >> Хорошо, линейный поиск. 165 00:07:07,810 --> 00:07:10,470 А в худшем случае, когда это элемент, который вы ищете, когда 166 00:07:10,470 --> 00:07:12,950 применении линейного поиска? 167 00:07:12,950 --> 00:07:14,680 >> Хорошо, в худшем случае, это даже не там. 168 00:07:14,680 --> 00:07:17,000 Или во втором худшем случае, это все пути в конце концов, который 169 00:07:17,000 --> 00:07:18,880 плюс-минус один шаг разницы. 170 00:07:18,880 --> 00:07:21,180 Итак, в конце концов, мы можем сказать, что это линейная. 171 00:07:21,180 --> 00:07:23,910 Big O п будет линейный поиск, потому что в худшем случае, 172 00:07:23,910 --> 00:07:26,610 Элемент даже не там, или это все пути в конце. 173 00:07:26,610 --> 00:07:29,370 >> Ну, Big O журнала н. 174 00:07:29,370 --> 00:07:32,760 Мы не говорили очень подробно о это, но мы видели это раньше. 175 00:07:32,760 --> 00:07:36,840 Что работает в так называемый логарифмический времени, в худшем случае? 176 00:07:36,840 --> 00:07:38,500 >> Да, так что бинарный поиск. 177 00:07:38,500 --> 00:07:42,930 И бинарного поиска в худшем случае может иметь элемент где-то 178 00:07:42,930 --> 00:07:45,640 середине, или в другом в массиве. 179 00:07:45,640 --> 00:07:48,040 Но вы только найти его, как только вы разделить список в два раза, в 180 00:07:48,040 --> 00:07:48,940 половина, пополам, пополам. 181 00:07:48,940 --> 00:07:50,200 А потом вуаля, что она есть. 182 00:07:50,200 --> 00:07:52,500 Или, опять же, худшем случае, это даже не там. 183 00:07:52,500 --> 00:07:56,770 Но вы не знаете, что это не есть пока вроде не достигнете, что в прошлом 184 00:07:56,770 --> 00:08:00,470 самый нижний элементов вдвое и сокращение вдвое и вдвое. 185 00:08:00,470 --> 00:08:01,400 >> Big O 1. 186 00:08:01,400 --> 00:08:03,540 Возможно, мы можем Big O 2, Big O 3. 187 00:08:03,540 --> 00:08:06,260 В любое время вы хотите просто постоянное число, мы просто вроде просто упростить 188 00:08:06,260 --> 00:08:07,280 что Big O 1. 189 00:08:07,280 --> 00:08:10,440 Хотя, если реально, она занимает 2 или даже 100 шагов, если это 190 00:08:10,440 --> 00:08:13,680 постоянное число шагов мы просто скажем Big O 1. 191 00:08:13,680 --> 00:08:15,930 Что это алгоритм В Big O 1? 192 00:08:15,930 --> 00:08:18,350 >> АУДИТОРИЯ: Определение длины переменной. 193 00:08:18,350 --> 00:08:21,090 >> DAVID МАЛАН: Поиск Длина переменной? 194 00:08:21,090 --> 00:08:23,870 >> АУДИТОРИЯ: Нет, длина если он уже отсортирован. 195 00:08:23,870 --> 00:08:24,160 >> DAVID МАЛАН: Хорошо. 196 00:08:24,160 --> 00:08:27,850 ОК, так что найти что-то длину если длина что что-то вроде 197 00:08:27,850 --> 00:08:30,020 массив, хранится в некоторой переменной. 198 00:08:30,020 --> 00:08:33,380 Потому что вы можете просто прочитать переменную, или распечатать переменной или 199 00:08:33,380 --> 00:08:34,960 просто вообще доступ к этой переменной. 200 00:08:34,960 --> 00:08:37,299 И вуаля, что требует постоянного времени. 201 00:08:37,299 --> 00:08:38,909 >> В отличие от этого, думаю, обратно в хорошем состоянии. 202 00:08:38,909 --> 00:08:42,460 Вспомните первую неделю C, вызове просто Е и печати 203 00:08:42,460 --> 00:08:46,240 что-то на экране, возможно, постоянное время, так он просто принимает 204 00:08:46,240 --> 00:08:50,880 некоторое число циклов процессора, чтобы показать , что текст на экране. 205 00:08:50,880 --> 00:08:52,720 Или ждать - не так ли? 206 00:08:52,720 --> 00:08:56,430 Как еще мы можем моделировать производительность Е? 207 00:08:56,430 --> 00:09:00,420 Кто-нибудь хотел бы не согласиться, что Может быть, это не совсем постоянное время? 208 00:09:00,420 --> 00:09:03,600 В каком смысле может Е бежит Время, фактически выводя строку на 209 00:09:03,600 --> 00:09:05,580 экране, будь то кроме постоянной. 210 00:09:05,580 --> 00:09:07,860 >> АУДИТОРИЯ: [неразборчиво]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID МАЛАН: Да. 212 00:09:08,230 --> 00:09:09,300 Так что это зависит от нашей точки зрения. 213 00:09:09,300 --> 00:09:13,390 Если мы на самом деле думаем о входе Е как строки, а 214 00:09:13,390 --> 00:09:16,380 Поэтому мы измеряем размер этого Ввод его длина - поэтому назовем 215 00:09:16,380 --> 00:09:17,780 что длины N, а также - 216 00:09:17,780 --> 00:09:21,990 Можно утверждать, что Е является самой большой O п потому что он собирается предпринять шаги вы н 217 00:09:21,990 --> 00:09:24,750 распечатать каждую из этих N символов, скорее всего. 218 00:09:24,750 --> 00:09:27,730 По крайней мере, в той степени, что мы предполагаем что, возможно, он использует для петли 219 00:09:27,730 --> 00:09:28,560 под капотом. 220 00:09:28,560 --> 00:09:30,860 >> Но мы должны были бы смотреть на это код лучше понять его. 221 00:09:30,860 --> 00:09:33,650 И действительно, как только вы ребята начинают Анализируя собственные алгоритмы, вы будете 222 00:09:33,650 --> 00:09:34,900 буквально сделать именно это. 223 00:09:34,900 --> 00:09:37,765 Сортировать глазного яблока код и думать О нас - все в порядке, у меня есть эта петля 224 00:09:37,765 --> 00:09:41,870 Здесь или у меня есть вложенные циклы здесь, что будет делать вещи N N раз, 225 00:09:41,870 --> 00:09:46,050 и вы можете сортировать разума свой путь через код, даже если это 226 00:09:46,050 --> 00:09:47,980 псевдокод, а не реальный код. 227 00:09:47,980 --> 00:09:49,730 >> Так что о омега N квадратов? 228 00:09:49,730 --> 00:09:53,582 То, что было алгоритм, в лучшем случае, все еще взял квадрат N шагов? 229 00:09:53,582 --> 00:09:54,014 Да? 230 00:09:54,014 --> 00:09:54,880 >> АУДИТОРИЯ: [неразборчиво]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID МАЛАН: Так Сортировать выбора. 232 00:09:55,900 --> 00:09:59,150 Потому что в этом проблема действительно уменьшен к тому, что опять же, я не знаю, 233 00:09:59,150 --> 00:10:02,600 Я нашел текущего меньшему, пока Я проверил все проклятые элементов. 234 00:10:02,600 --> 00:10:08,050 Так омега, скажем, п только что пришел с одним. 235 00:10:08,050 --> 00:10:09,300 Сортировка вставками. 236 00:10:09,300 --> 00:10:12,370 Если список случается быть отсортированы уже, в лучшем случае мы просто должны 237 00:10:12,370 --> 00:10:15,090 чтобы сделать один проход через него, и в этот момент мы уверены. 238 00:10:15,090 --> 00:10:17,890 И затем, что можно сказать линейные, наверняка. 239 00:10:17,890 --> 00:10:20,570 >> Как насчет омега 1? 240 00:10:20,570 --> 00:10:23,790 Что, в лучшем случае, может занять постоянное число шагов? 241 00:10:23,790 --> 00:10:27,220 Так линейный поиск, если вы просто везет и элемент, который вы ищете 242 00:10:27,220 --> 00:10:31,000 находится в самом начале списка, если это то, где вы начинаете вашу 243 00:10:31,000 --> 00:10:33,070 линейного обхода этого списка. 244 00:10:33,070 --> 00:10:35,180 >> И это верно для несколько вещей. 245 00:10:35,180 --> 00:10:37,660 Например, даже двоичный поиск омега 1. 246 00:10:37,660 --> 00:10:40,310 Потому что, если вы получаете действительно проклятое повезло, и прикосновение вкуса в середине 247 00:10:40,310 --> 00:10:42,950 вашего массива является число Вы ищете? 248 00:10:42,950 --> 00:10:45,730 Таким образом, вы можете получить повезло там, а также. 249 00:10:45,730 --> 00:10:49,190 >> Этот, наконец, омега N § п. 250 00:10:49,190 --> 00:10:52,573 Таким N журнал N, нам действительно не говорить о пока нет, но - 251 00:10:52,573 --> 00:10:53,300 >> АУДИТОРИЯ: Сортировка слиянием? 252 00:10:53,300 --> 00:10:53,960 >> DAVID МАЛАН: сортировка слиянием. 253 00:10:53,960 --> 00:10:56,920 Это было захватывающим последнего времени, где мы предложили, и мы показали 254 00:10:56,920 --> 00:10:58,600 визуально, то есть алгоритмы. 255 00:10:58,600 --> 00:11:02,470 И сортировка слиянием только одного такого Алгоритм, который принципиально быстрее 256 00:11:02,470 --> 00:11:03,450 чем некоторые из этих других парней. 257 00:11:03,450 --> 00:11:07,800 В самом деле, слияние короткий не только в лучшем случае N журнал N, в худшем 258 00:11:07,800 --> 00:11:09,460 Случай п § п. 259 00:11:09,460 --> 00:11:14,540 И когда у вас есть это совпадение Омега и Big O является одно и то же? 260 00:11:14,540 --> 00:11:17,310 Мы можем реально описать это как то, что называются тета, хотя это 261 00:11:17,310 --> 00:11:18,220 немного реже. 262 00:11:18,220 --> 00:11:21,730 Но это просто означает, что два прыжка В этом случае те же самые. 263 00:11:21,730 --> 00:11:25,770 >> Так сортировки слиянием, что же это действительно сводятся к для нас? 264 00:11:25,770 --> 00:11:27,000 Ну, вспомните мотивации. 265 00:11:27,000 --> 00:11:30,340 Позвольте мне подтянуть анимацию, которое Мы не смотрели на последний раз. 266 00:11:30,340 --> 00:11:33,390 Это одно, та же идея, но это немного больше. 267 00:11:33,390 --> 00:11:36,160 И я собираюсь идти вперед и отметить, первое - у нас есть на сортировку вставками 268 00:11:36,160 --> 00:11:39,410 левом верхнем углу, а затем выбор рода, пузырьковая сортировка, несколько других видов - 269 00:11:39,410 --> 00:11:42,670 оболочки и быстро, - что мы еще не говорили о, и кучу и сортировка слиянием. 270 00:11:42,670 --> 00:11:47,090 >> Так по крайней мере попытаться сосредоточиться на ваших глазах тройку на левой, а затем 271 00:11:47,090 --> 00:11:49,120 сортировка слиянием, когда я нажимаю этой зеленой стрелкой. 272 00:11:49,120 --> 00:11:51,900 Но я позволю все они запускаются, просто чтобы дать вам ощущение разнообразия 273 00:11:51,900 --> 00:11:53,980 Алгоритмы, которые существуют в мире. 274 00:11:53,980 --> 00:11:56,180 Я собираюсь позволить этой перспективе всего за несколько секунд. 275 00:11:56,180 --> 00:11:59,640 И если вы сосредоточитесь глаза - выбрать Алгоритм, сосредоточиться на нем в течение всего 276 00:11:59,640 --> 00:12:02,970 секунд - вы начинаете видеть картина, что это осуществление. 277 00:12:02,970 --> 00:12:04,530 >> Сортировка слиянием, заметьте, делается. 278 00:12:04,530 --> 00:12:06,430 Кучи сортировки, быстрой сортировки, Shell - 279 00:12:06,430 --> 00:12:09,480 так что кажется, мы ввели три худших алгоритмов на прошлой неделе. 280 00:12:09,480 --> 00:12:12,960 Но это хорошо, что мы сегодня здесь, чтобы посмотреть на сортировки слиянием, которое является одним из 281 00:12:12,960 --> 00:12:16,500 более легкие, чтобы смотреть на, даже хотя она, вероятно, будет изгибаться ваш ум 282 00:12:16,500 --> 00:12:17,490 только немного. 283 00:12:17,490 --> 00:12:21,130 Здесь мы можем видеть, как много Выбор рода сосет. 284 00:12:21,130 --> 00:12:24,600 >> Но, с другой стороны, это действительно легко осуществить. 285 00:12:24,600 --> 00:12:28,160 И может быть, для P набор 3, это одна из Алгоритмы вы решили реализовать 286 00:12:28,160 --> 00:12:28,960 для стандартного издания. 287 00:12:28,960 --> 00:12:30,970 Прекрасно подходит, совершенно правильно. 288 00:12:30,970 --> 00:12:35,210 >> Но опять же, как н становится большим, если вы выбрать для реализации более быстрый алгоритм 289 00:12:35,210 --> 00:12:39,020 нравится сортировки слиянием, шансы в крупных и больше входов, код является просто 290 00:12:39,020 --> 00:12:39,800 собирается работать быстрее. 291 00:12:39,800 --> 00:12:41,090 Ваш сайт будет работать лучше. 292 00:12:41,090 --> 00:12:42,650 Ваши пользователи будут счастливее. 293 00:12:42,650 --> 00:12:45,280 И так есть эти эффекты фактически давая 294 00:12:45,280 --> 00:12:47,350 нам некоторые глубокие мысли. 295 00:12:47,350 --> 00:12:49,990 >> Итак, давайте посмотрим, что слияние Сортировать самом деле все о. 296 00:12:49,990 --> 00:12:52,992 Самое замечательное в том, что слияние рода является именно это. 297 00:12:52,992 --> 00:12:56,300 Это, опять же, то, что мы назвали псевдокод, псевдокод существо 298 00:12:56,300 --> 00:12:57,720 Английский-подобный синтаксис. 299 00:12:57,720 --> 00:12:59,890 И простота рода увлекательным. 300 00:12:59,890 --> 00:13:02,840 >> Так на входе из п элементов - так, чтобы просто означает, вот массив. 301 00:13:02,840 --> 00:13:04,000 У этого есть N вещи в нем. 302 00:13:04,000 --> 00:13:05,370 Это все, что мы говорим, что там. 303 00:13:05,370 --> 00:13:07,560 >> Если N меньше 2, вернуться. 304 00:13:07,560 --> 00:13:08,640 Так что это просто тривиальный случай. 305 00:13:08,640 --> 00:13:12,580 Если N меньше 2, то, очевидно, это 1 или 0, в этом случае вещь 306 00:13:12,580 --> 00:13:14,780 уже отсортирован или несуществующие, так что просто вернуться. 307 00:13:14,780 --> 00:13:15,900 Там нет ничего, чтобы сделать. 308 00:13:15,900 --> 00:13:18,360 Так что это простой случай, чтобы обрывать. 309 00:13:18,360 --> 00:13:20,110 >> В противном случае, у нас есть три этапа. 310 00:13:20,110 --> 00:13:23,650 Сортировать левую половину элементов, отсортируйте Правая половина элементов 311 00:13:23,650 --> 00:13:26,650 , а затем объединить отсортированный половины. 312 00:13:26,650 --> 00:13:29,400 Что интересно здесь то, что Я вроде понтировавшего, верно? 313 00:13:29,400 --> 00:13:32,300 Там вроде круговой определению для этого алгоритма. 314 00:13:32,300 --> 00:13:35,986 В каком смысле этого алгоритма Определение круговой? 315 00:13:35,986 --> 00:13:37,850 >> АУДИТОРИЯ: [неразборчиво]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID МАЛАН: Да, мой алгоритм сортировки, двух своих шагов "вид 317 00:13:41,670 --> 00:13:44,640 что-то. "И так, что возникает Вопрос, ну, что я собираюсь использовать 318 00:13:44,640 --> 00:13:46,460 для сортировки левой половины а правая половина? 319 00:13:46,460 --> 00:13:49,600 И красота в том, что даже при том, опять же, это галлюциногенный 320 00:13:49,600 --> 00:13:54,030 часть потенциально, вы можете использовать тот же Алгоритм для сортировки левой половине. 321 00:13:54,030 --> 00:13:54,700 >> Но подождите минуту. 322 00:13:54,700 --> 00:13:57,070 Когда вы сказали, чтобы отсортировать Левая половина, какие две 323 00:13:57,070 --> 00:13:58,240 шагов будет дальше? 324 00:13:58,240 --> 00:14:00,550 Мы разберемся с левой половины Левая половина и право 325 00:14:00,550 --> 00:14:01,420 половина левой половины. 326 00:14:01,420 --> 00:14:04,430 Блин, как мне отсортировать эти два половины и четверти, в настоящее время? 327 00:14:04,430 --> 00:14:05,260 >> Но это не страшно. 328 00:14:05,260 --> 00:14:07,830 У нас есть алгоритм сортировки здесь. 329 00:14:07,830 --> 00:14:10,660 И хотя вы можете беспокоиться первое это вроде бесконечного 330 00:14:10,660 --> 00:14:12,780 петли, это цикл, который никогда не кончится - он собирается 331 00:14:12,780 --> 00:14:15,770 прекратится, как только то, что происходит? 332 00:14:15,770 --> 00:14:16,970 После п меньше 2. 333 00:14:16,970 --> 00:14:19,180 Которые в конечном итоге произойдет, потому что если вы продолжайте делить на два и 334 00:14:19,180 --> 00:14:23,020 снижение в два раза сократить вдвое эти половины, безусловно, в конце концов вы будете в конечном 335 00:14:23,020 --> 00:14:25,350 только с 1 или 0 элементов. 336 00:14:25,350 --> 00:14:28,500 В этот момент, этот алгоритм говорит, что вы сделали. 337 00:14:28,500 --> 00:14:31,020 >> Таким образом, настоящая магия в этом Алгоритм, кажется, в 338 00:14:31,020 --> 00:14:33,470 этот последний шаг, сливаясь. 339 00:14:33,470 --> 00:14:37,190 Это простая идея просто слияния двух вещи, это то, что в конечном счете будет 340 00:14:37,190 --> 00:14:40,920 , чтобы позволить нам отсортировать массив, скажем, восемь элементов. 341 00:14:40,920 --> 00:14:44,410 Так что у меня еще восемь шаров до стресса Здесь, восемь бумажки, и один 342 00:14:44,410 --> 00:14:45,500 Google стекла - 343 00:14:45,500 --> 00:14:46,140 которые я получаю, чтобы сохранить. 344 00:14:46,140 --> 00:14:46,960 >> [Смеется] 345 00:14:46,960 --> 00:14:48,970 >> DAVID МАЛАН: Если бы мы могли принять восемь добровольцев, и давайте посмотрим, если мы можем 346 00:14:48,970 --> 00:14:51,430 играть в эту, таким образом. 347 00:14:51,430 --> 00:14:52,500 Ничего себе, ОК. 348 00:14:52,500 --> 00:14:53,565 Информатика становится весело. 349 00:14:53,565 --> 00:14:54,320 Хорошо. 350 00:14:54,320 --> 00:14:57,770 Так, как вы трое крупнейших руку там. 351 00:14:57,770 --> 00:14:58,580 Четыре в спину. 352 00:14:58,580 --> 00:15:02,220 А как насчет сделаем Вам три в этом ряду? 353 00:15:02,220 --> 00:15:03,390 И четыре в передней части. 354 00:15:03,390 --> 00:15:04,920 Таким образом, вы восемь, поднимайся. 355 00:15:04,920 --> 00:15:12,060 >> [Смеется] 356 00:15:12,060 --> 00:15:13,450 >> DAVID МАЛАН: Я на самом деле не уверен, что это такое. 357 00:15:13,450 --> 00:15:14,810 Это стресс шаров? 358 00:15:14,810 --> 00:15:16,510 Настольные лампы? 359 00:15:16,510 --> 00:15:18,650 Материал? 360 00:15:18,650 --> 00:15:19,680 В интернете? 361 00:15:19,680 --> 00:15:20,160 >> ОК. 362 00:15:20,160 --> 00:15:21,310 Так что приезжайте и выше. 363 00:15:21,310 --> 00:15:22,310 Кто хотел - 364 00:15:22,310 --> 00:15:23,570 продолжают поступать. 365 00:15:23,570 --> 00:15:24,240 Давайте посмотрим. 366 00:15:24,240 --> 00:15:26,460 И это ставит вас в месте - 367 00:15:26,460 --> 00:15:27,940 Вы находитесь в одном расположения. 368 00:15:27,940 --> 00:15:28,670 Ой, подожди минутку. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - о, хорошо. 370 00:15:30,760 --> 00:15:31,310 Хорошо, что мы хороши. 371 00:15:31,310 --> 00:15:35,130 Ладно, у всех есть место, но не на стекле Google. 372 00:15:35,130 --> 00:15:36,475 Позвольте мне в очередь эти вверх. 373 00:15:36,475 --> 00:15:37,115 Как тебя зовут? 374 00:15:37,115 --> 00:15:37,440 >> МИШЕЛЬ: Мишель. 375 00:15:37,440 --> 00:15:38,090 >> DAVID МАЛАН: Мишель? 376 00:15:38,090 --> 00:15:42,000 Ладно, вы получаете возможность выглядеть Играйте и выигрывайте, если это нормально. 377 00:15:42,000 --> 00:15:44,625 Ну, я тоже, я полагаю, на мгновение. 378 00:15:44,625 --> 00:15:45,875 Все права, в режиме ожидания. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Мы пытаемся, чтобы придумать случаи использования Google стекла, и мы 381 00:15:50,950 --> 00:15:53,750 думал, что это было бы интересно, чтобы просто делать это когда люди на сцене. 382 00:15:53,750 --> 00:15:57,120 Мы запишем мире с их точки зрения. 383 00:15:57,120 --> 00:15:58,410 Хорошо. 384 00:15:58,410 --> 00:15:59,830 Не вероятно, что Google предназначено. 385 00:15:59,830 --> 00:16:02,260 Ладно, если вы не против носить этом в течение следующего неудобный минут 386 00:16:02,260 --> 00:16:03,150 это было бы замечательно. 387 00:16:03,150 --> 00:16:08,620 >> Ладно, так что мы имеем здесь дело с массивом элементами и массива, согласно 388 00:16:08,620 --> 00:16:11,480 бумажки в этих людей " руки, в настоящее время отсортированы. 389 00:16:11,480 --> 00:16:12,050 >> МИШЕЛЬ: О, это так странно. 390 00:16:12,050 --> 00:16:12,810 >> DAVID МАЛАН: Это в значительной степени случайным. 391 00:16:12,810 --> 00:16:15,760 И через минуту, мы собираемся, чтобы попытаться для реализации сортировки слиянием вместе 392 00:16:15,760 --> 00:16:17,950 и посмотреть, где, что ключевое понимание есть. 393 00:16:17,950 --> 00:16:21,970 И трюк здесь с сортировки слиянием является то, что мы пока не предполагается. 394 00:16:21,970 --> 00:16:24,030 Мы на самом деле нужна дополнительное пространство. 395 00:16:24,030 --> 00:16:26,650 Так что же происходит, что особенно интересное в этом то, что эти 396 00:16:26,650 --> 00:16:29,270 ребята, собираетесь передвигаться немного немного, потому что я буду считать, что 397 00:16:29,270 --> 00:16:31,880 есть дополнительная массив пространстве, скажем, сразу за ними. 398 00:16:31,880 --> 00:16:34,570 >> Так что если они за свои кресла, это вторичное массива. 399 00:16:34,570 --> 00:16:36,960 Если они сидят здесь, это первичного массива. 400 00:16:36,960 --> 00:16:40,170 Но это ресурс, который мы имеем не использовала до сих пор с пузырем 401 00:16:40,170 --> 00:16:42,040 сортировка, с выбором вида, с сортировку вставками. 402 00:16:42,040 --> 00:16:44,600 Напомним, на прошлой неделе, все просто вид перемешиваются на месте. 403 00:16:44,600 --> 00:16:46,840 Они не использовали любой дополнительной памяти. 404 00:16:46,840 --> 00:16:49,310 Мы создали место для людей перемещение людей вокруг. 405 00:16:49,310 --> 00:16:50,580 >> Так что это ключевое понимание, тоже. 406 00:16:50,580 --> 00:16:53,410 Там есть компромисс, в целом в компьютерные науки, ресурсов. 407 00:16:53,410 --> 00:16:55,800 Если вы хотите ускорить что-то как время, вы собираетесь 408 00:16:55,800 --> 00:16:56,900 придется заплатить цену. 409 00:16:56,900 --> 00:17:00,750 И одна из этих цен очень часто пространстве, объем памяти или жесткого 410 00:17:00,750 --> 00:17:01,700 дискового пространства, который вы используете. 411 00:17:01,700 --> 00:17:03,640 Или, если честно, количество программист времени. 412 00:17:03,640 --> 00:17:06,700 Сколько времени это займет у вас, человека, в целях практического осуществления еще несколько 413 00:17:06,700 --> 00:17:07,829 сложный алгоритм. 414 00:17:07,829 --> 00:17:09,760 Но на сегодняшний день, компромисс время и пространство. 415 00:17:09,760 --> 00:17:11,930 >> Так что, если вы, ребята, могли бы просто поднимите номера, чтобы мы могли видеть, что Вы 416 00:17:11,930 --> 00:17:15,839 Действительно соответствующий 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Отлично. 418 00:17:16,599 --> 00:17:19,520 Так что я собираюсь попробовать, чтобы организовать вещи, если вы, ребята, можете просто 419 00:17:19,520 --> 00:17:21,800 следуй за мной здесь. 420 00:17:21,800 --> 00:17:26,650 >> Так что я собираюсь осуществить, во-первых, Первый этап псевдокода, который 421 00:17:26,650 --> 00:17:29,440 на входе элементов п, если п меньше 2, то возвращается. 422 00:17:29,440 --> 00:17:31,370 Очевидно, что не применяются, поэтому мы двигаться дальше. 423 00:17:31,370 --> 00:17:33,340 Так отсортировать левую половину элементов. 424 00:17:33,340 --> 00:17:36,220 Значит, я собираюсь сосредоточить свое внимание на мгновение на этих 425 00:17:36,220 --> 00:17:37,310 четверо парней здесь. 426 00:17:37,310 --> 00:17:39,774 Хорошо, что я следующий делать? 427 00:17:39,774 --> 00:17:40,570 >> АУДИТОРИЯ: Сортировать левую половину. 428 00:17:40,570 --> 00:17:42,780 >> DAVID МАЛАН: Так что теперь у меня есть, чтобы разобраться Левая половина этих парней. 429 00:17:42,780 --> 00:17:45,580 Потому что опять же, предположим, к себе Цель состоит в сортировке левую половину. 430 00:17:45,580 --> 00:17:46,440 Как вы это сделали? 431 00:17:46,440 --> 00:17:49,140 Просто следуйте инструкциям, даже хотя мы делаем это снова. 432 00:17:49,140 --> 00:17:50,160 Так отсортировать левую половину. 433 00:17:50,160 --> 00:17:52,030 Теперь я сортировку этих двух парней. 434 00:17:52,030 --> 00:17:53,563 Что будет дальше? 435 00:17:53,563 --> 00:17:54,510 >> АУДИТОРИЯ: Сортировать левую половину. 436 00:17:54,510 --> 00:17:55,460 >> DAVID МАЛАН: Сортировать левую половину. 437 00:17:55,460 --> 00:18:00,680 Так что теперь это, это место здесь, приведен список размер 1. 438 00:18:00,680 --> 00:18:01,365 И то, что тебя зовут? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESS DAISY: Принцесса Дейзи. 440 00:18:02,390 --> 00:18:03,690 >> DAVID МАЛАН: Принцесса Дэйзи здесь. 441 00:18:03,690 --> 00:18:07,470 И вот она уже отсортирован, так как Список имеет размер 1. 442 00:18:07,470 --> 00:18:09,490 Что мне делать следующий? 443 00:18:09,490 --> 00:18:13,680 OK, вернуться, потому что список из размер 1, который составляет менее 2. 444 00:18:13,680 --> 00:18:14,320 Тогда в чем же следующий шаг? 445 00:18:14,320 --> 00:18:17,490 И теперь вы должны вид возвратиться в вашем уме. 446 00:18:17,490 --> 00:18:19,340 >> Сортировать правая половина, которая - 447 00:18:19,340 --> 00:18:19,570 Как тебя зовут? 448 00:18:19,570 --> 00:18:20,220 >> ЛИНДА: Линда. 449 00:18:20,220 --> 00:18:20,980 >> DAVID МАЛАН: Линда. 450 00:18:20,980 --> 00:18:23,210 И так, что же нам теперь делать, что у нас есть список размером 1? 451 00:18:23,210 --> 00:18:24,440 >> АУДИТОРИЯ: Возвращение. 452 00:18:24,440 --> 00:18:24,760 >> DAVID МАЛАН: Осторожно. 453 00:18:24,760 --> 00:18:29,540 Вернемся первой, и теперь третий Шаг - и если я как бы изобразить его 454 00:18:29,540 --> 00:18:33,490 охватывает два места, теперь я необходимо объединить эти два элемента. 455 00:18:33,490 --> 00:18:35,530 Так что теперь, к сожалению, элементы вышли из строя. 456 00:18:35,530 --> 00:18:39,920 Но на этом процесс объединения начинает становиться убедительными. 457 00:18:39,920 --> 00:18:42,410 >> Так что, если вы, ребята, могли постоять за просто момент, я буду нуждаться в вас, в 458 00:18:42,410 --> 00:18:44,170 момент, чтобы шаг позади стула. 459 00:18:44,170 --> 00:18:46,480 И если Линда, поскольку 2 находится меньше, чем 4, почему не 460 00:18:46,480 --> 00:18:48,130 Вам приходят в первую очередь? 461 00:18:48,130 --> 00:18:48,690 Оставайтесь там. 462 00:18:48,690 --> 00:18:50,520 Так Линда, вы приходите вокруг первой. 463 00:18:50,520 --> 00:18:53,820 >> Сейчас на самом деле, если это просто массив мы могли бы просто переместить ее в режиме реального времени 464 00:18:53,820 --> 00:18:55,360 этой кафедры в это место. 465 00:18:55,360 --> 00:18:57,770 Итак, представьте, что потребовалось некоторое постоянное число шагов 1. 466 00:18:57,770 --> 00:18:58,480 А теперь - 467 00:18:58,480 --> 00:19:01,490 но мы должны поставить вас в первого места здесь. 468 00:19:01,490 --> 00:19:03,930 >> И теперь, если вы могли бы приходить, также, мы собираемся 469 00:19:03,930 --> 00:19:06,300 Расположение находится в два. 470 00:19:06,300 --> 00:19:09,120 И даже если это чувствует, что это занять некоторое время, то, что приятно сейчас 471 00:19:09,120 --> 00:19:14,710 что левая половина Левая половина теперь сортируется. 472 00:19:14,710 --> 00:19:18,010 Так что был следующий шаг, если мы сейчас перемотать дальше в историю? 473 00:19:18,010 --> 00:19:18,980 >> АУДИТОРИЯ: Правая половина. 474 00:19:18,980 --> 00:19:19,900 >> DAVID МАЛАН: Сортировать правую половину. 475 00:19:19,900 --> 00:19:21,320 Таким образом, вы, ребята, должны сделать это, а также. 476 00:19:21,320 --> 00:19:23,510 Так что если вы могли встать на мгновение? 477 00:19:23,510 --> 00:19:25,192 А как тебя зовут? 478 00:19:25,192 --> 00:19:25,540 >> Джесси: Джесс. 479 00:19:25,540 --> 00:19:25,870 >> DAVID МАЛАН: Джесс. 480 00:19:25,870 --> 00:19:29,720 Итак, Джесс Теперь левая половину правой половины. 481 00:19:29,720 --> 00:19:31,400 И так она список Размер 1. 482 00:19:31,400 --> 00:19:32,380 Она, очевидно, сортируют. 483 00:19:32,380 --> 00:19:33,070 И ваше имя? 484 00:19:33,070 --> 00:19:33,630 >> МИШЕЛЬ: Мишель. 485 00:19:33,630 --> 00:19:35,340 >> DAVID МАЛАН: Мишель, очевидно, Перечень размер 1. 486 00:19:35,340 --> 00:19:36,050 Она уже отсортирован. 487 00:19:36,050 --> 00:19:38,690 Так что теперь происходит волшебство, Процесс слияния. 488 00:19:38,690 --> 00:19:39,790 Так что, кто собирается придти прежде? 489 00:19:39,790 --> 00:19:41,560 Очевидно Мишель. 490 00:19:41,560 --> 00:19:43,280 Так что, если вы могли бы приходить обратно. 491 00:19:43,280 --> 00:19:47,090 Пространстве мы имеем в наличии для нее теперь Прямо за это кресло здесь. 492 00:19:47,090 --> 00:19:51,580 И теперь, если вы могли бы вернуться, а также, у нас теперь есть, чтобы быть ясным, два 493 00:19:51,580 --> 00:19:53,810 половин, каждая из размер 2 - 494 00:19:53,810 --> 00:19:57,090 и просто ради изображением автора, если Вы могли бы сделать немного пространства - 495 00:19:57,090 --> 00:19:59,780 одной левой половине, по одному Правая половина здесь. 496 00:19:59,780 --> 00:20:01,160 >> Перемотка дальше в историю. 497 00:20:01,160 --> 00:20:02,270 Какой шаг будет следующим? 498 00:20:02,270 --> 00:20:03,030 >> АУДИТОРИЯ: Merge. 499 00:20:03,030 --> 00:20:04,160 >> DAVID МАЛАН: Так что теперь у нас есть для слияния. 500 00:20:04,160 --> 00:20:07,490 Так хорошо, так что теперь, к счастью, мы просто освободил четырьмя стульями. 501 00:20:07,490 --> 00:20:11,480 Таким образом, мы использовали два раза больше памяти, но мы можем дать флип-флопе между 502 00:20:11,480 --> 00:20:12,330 два массива. 503 00:20:12,330 --> 00:20:14,190 Так, число которых на первом месте? 504 00:20:14,190 --> 00:20:14,850 Так Мишель, это очевидно. 505 00:20:14,850 --> 00:20:16,680 Так приходят и принимают ваше место здесь. 506 00:20:16,680 --> 00:20:19,120 А потом номер 2, очевидно, Далее, так что вы пришли сюда. 507 00:20:19,120 --> 00:20:21,520 Номер 4, номер 6. 508 00:20:21,520 --> 00:20:23,390 И снова, несмотря на то, что есть немного пешеходных прогулок вовлеченного, 509 00:20:23,390 --> 00:20:26,010 действительно, это может произойти мгновенно, путем перемещения одного - 510 00:20:26,010 --> 00:20:26,880 Хорошо, хорошо играл. 511 00:20:26,880 --> 00:20:28,350 >> [Смеется] 512 00:20:28,350 --> 00:20:29,680 >> DAVID МАЛАН: А теперь мы в довольно хорошей форме. 513 00:20:29,680 --> 00:20:34,910 Левая половина всего входного теперь сортируются. 514 00:20:34,910 --> 00:20:37,370 Ладно, эти парни были Преимущество моей - 515 00:20:37,370 --> 00:20:40,340 как она в конечном итоге все девушки на налево и все мальчики справа? 516 00:20:40,340 --> 00:20:42,450 >> Хорошо, таким образом парней очередь. 517 00:20:42,450 --> 00:20:44,680 Поэтому я не буду идти Вы через эти шаги. 518 00:20:44,680 --> 00:20:46,550 Мы увидим, если мы можем повторно же псевдокод. 519 00:20:46,550 --> 00:20:50,050 Если вы хотите идти вперед и встать, и вы, ребята, позвольте мне дать вам микрофон. 520 00:20:50,050 --> 00:20:52,990 Смотрите, если вы не можете повторить то, что мы только что сделали здесь, на 521 00:20:52,990 --> 00:20:53,880 Другой конец списка. 522 00:20:53,880 --> 00:20:59,530 Кто должен говорить первым, основанный на алгоритме? 523 00:20:59,530 --> 00:21:03,210 Так объясните, что вы делаете, прежде Вы делаете любой ноге движений. 524 00:21:03,210 --> 00:21:05,930 >> Выступающий 1: Ну, хорошо, так как Я левой половины 525 00:21:05,930 --> 00:21:07,790 Левая половина, я вернусь. 526 00:21:07,790 --> 00:21:08,730 Верно? 527 00:21:08,730 --> 00:21:09,250 >> DAVID МАЛАН: Хорошо. 528 00:21:09,250 --> 00:21:10,350 >> Выступающий 1: А потом - 529 00:21:10,350 --> 00:21:11,800 >> DAVID МАЛАН: кто MIC перейти к следующему? 530 00:21:11,800 --> 00:21:12,920 >> Выступающий 1: Следующий номер. 531 00:21:12,920 --> 00:21:14,720 >> Докладчик 2: Так что я правая половина левой половины 532 00:21:14,720 --> 00:21:17,830 левая половина, и я вернусь. 533 00:21:17,830 --> 00:21:18,050 >> DAVID МАЛАН: Хорошо. 534 00:21:18,050 --> 00:21:18,550 Вы вернетесь. 535 00:21:18,550 --> 00:21:21,855 Так что теперь каков следующий за вами двумя? 536 00:21:21,855 --> 00:21:23,740 >> Докладчик 2: Мы хотим видеть, кто меньше. 537 00:21:23,740 --> 00:21:24,200 >> DAVID МАЛАН: Совершенно верно. 538 00:21:24,200 --> 00:21:24,940 Мы хотим объединить. 539 00:21:24,940 --> 00:21:27,590 Пространство мы собираемся использовать для слияния Вас в, даже если они 540 00:21:27,590 --> 00:21:30,250 Очевидно, уже отсортированы, мы собираемся пойти по тому же алгоритму. 541 00:21:30,250 --> 00:21:31,560 Так кто идет в спине в первую очередь? 542 00:21:31,560 --> 00:21:35,720 Таким 3, а затем 7. 543 00:21:35,720 --> 00:21:38,570 А теперь идет микрофон с этими парнями, хорошо? 544 00:21:38,570 --> 00:21:43,590 >> Выступающий 3: Так что я правую половину левую половину, и мой N меньше 545 00:21:43,590 --> 00:21:45,048 1, так что я просто хочу, чтобы пройти - 546 00:21:45,048 --> 00:21:46,380 >> DAVID МАЛАН: Хорошо. 547 00:21:46,380 --> 00:21:49,450 >> Выступающий 4: Я правая половина Правая половина правая половина, и я 548 00:21:49,450 --> 00:21:51,740 Также один человек, так что я собирается вернуться. 549 00:21:51,740 --> 00:21:52,990 Так что теперь мы сливаемся. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> Выступающий 3: Итак, мы возвращаемся. 552 00:21:56,150 --> 00:21:57,160 >> DAVID МАЛАН: Так вы идете в заднюю часть. 553 00:21:57,160 --> 00:21:59,200 Так 5 идет в первую очередь, то 8. 554 00:21:59,200 --> 00:22:01,240 А теперь аудитории, который является шага нам нужно теперь перемотать 555 00:22:01,240 --> 00:22:02,200 вернуться к в нашем сознании? 556 00:22:02,200 --> 00:22:02,940 >> АУДИТОРИЯ: Merge. 557 00:22:02,940 --> 00:22:07,270 >> DAVID МАЛАН: объединение левой и правой половины половину первоначальной левую половину. 558 00:22:07,270 --> 00:22:08,840 Так что теперь - 559 00:22:08,840 --> 00:22:10,520 и просто, чтобы было понятнее, сделать немного пространства 560 00:22:10,520 --> 00:22:11,690 между вами двумя парнями. 561 00:22:11,690 --> 00:22:13,800 Так что теперь это два списка, слева и справа. 562 00:22:13,800 --> 00:22:18,320 Так как же нам теперь слияние, вы парни в первый ряд мест снова? 563 00:22:18,320 --> 00:22:19,600 >> 3 идет в первую очередь. 564 00:22:19,600 --> 00:22:20,850 5 Тогда, очевидно. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Затем 7, и теперь 8. 567 00:22:27,330 --> 00:22:28,710 ОК, а теперь мы? 568 00:22:28,710 --> 00:22:29,650 >> АУДИТОРИЯ: не делается. 569 00:22:29,650 --> 00:22:32,440 >> DAVID МАЛАН: Не за то, что Очевидно, что здесь один шаг осталось. 570 00:22:32,440 --> 00:22:35,720 Но, опять же, причина я использую это жаргона, как "перемотка в своем уме," 571 00:22:35,720 --> 00:22:37,160 это потому, что на самом деле что происходит. 572 00:22:37,160 --> 00:22:39,610 Мы проходим через все эти шаги, но мы же вроде останавливаясь на 573 00:22:39,610 --> 00:22:42,480 момент, дайвинг глубже в Алгоритм, задержавшись на мгновение, 574 00:22:42,480 --> 00:22:45,840 погружаться глубже и глубже в алгоритм, и Теперь мы должны разобраться перемотки в нашей 575 00:22:45,840 --> 00:22:49,430 умы и отменить все эти слои что мы вроде приостановлено. 576 00:22:49,430 --> 00:22:51,790 >> Так что теперь у нас есть два списка размера 4. 577 00:22:51,790 --> 00:22:54,790 Если вы, ребята, могли встать в последний раз и сделать немного места здесь, чтобы 578 00:22:54,790 --> 00:22:57,230 дать понять, что это левый половину первоначальной, 579 00:22:57,230 --> 00:22:58,620 Правая половина оригинала. 580 00:22:58,620 --> 00:23:01,060 Кто первым номером, что мы нужно тянуть в спину? 581 00:23:01,060 --> 00:23:01,870 Мишель, конечно. 582 00:23:01,870 --> 00:23:03,230 >> Так мы одели Мишель здесь. 583 00:23:03,230 --> 00:23:05,080 И кто имеет номер 2? 584 00:23:05,080 --> 00:23:06,440 Номер 2 приходит на спине, а также. 585 00:23:06,440 --> 00:23:07,800 Номер 3? 586 00:23:07,800 --> 00:23:08,510 Отлично. 587 00:23:08,510 --> 00:23:16,570 Номер 4, № 5, № 6, № 7, и № 8. 588 00:23:16,570 --> 00:23:18,850 >> Хорошо, таким образом, было похоже на много шагов, это точно. 589 00:23:18,850 --> 00:23:22,390 Но теперь давайте посмотрим, если мы не можем подтвердить рода интуитивно, что это 590 00:23:22,390 --> 00:23:26,190 Алгоритм принципиально, в частности, N становится действительно большим, как мы видели 591 00:23:26,190 --> 00:23:29,170 с анимацией, является принципиально быстрее. 592 00:23:29,170 --> 00:23:33,400 Поэтому я утверждаю, этот алгоритм, в худшем случай и даже в лучшем случае, 593 00:23:33,400 --> 00:23:36,160 большая O п § п раз. 594 00:23:36,160 --> 00:23:39,160 То есть, есть некоторые аспекты этого алгоритм, который пользуется N шагов, но 595 00:23:39,160 --> 00:23:43,110 есть еще один аспект где-то в что итерации цикла, что, что 596 00:23:43,110 --> 00:23:44,410 берет журнал N шагов. 597 00:23:44,410 --> 00:23:49,154 Можем ли мы указать на то, что эти два числа имеют в виду? 598 00:23:49,154 --> 00:23:51,320 Ну, и где - 599 00:23:51,320 --> 00:23:54,160 Где микрофон идти? 600 00:23:54,160 --> 00:23:58,660 >> Выступающий 1: Будет ли войти п нарушение нас на две части - 601 00:23:58,660 --> 00:23:59,630 деления на два, по существу. 602 00:23:59,630 --> 00:24:00,120 >> DAVID МАЛАН: Совершенно верно. 603 00:24:00,120 --> 00:24:03,000 Каждый раз, когда мы видим в любой алгоритм таким образом, далеко, там был этот образец 604 00:24:03,000 --> 00:24:04,200 деление, деления, деления. 605 00:24:04,200 --> 00:24:05,700 И это обычно восстанавливают на то, что это 606 00:24:05,700 --> 00:24:07,100 логарифмические, логарифм по основанию 2. 607 00:24:07,100 --> 00:24:10,180 Но это действительно может быть что угодно, но войти основанию 2. 608 00:24:10,180 --> 00:24:11,330 >> Теперь то, что о русских? 609 00:24:11,330 --> 00:24:14,550 Я вижу, что мы как бы разделило вас Ребята - разделило вас, разделило вас, 610 00:24:14,550 --> 00:24:15,910 разделило вас, разделенный вас. 611 00:24:15,910 --> 00:24:18,760 Где конце концов пришли? 612 00:24:18,760 --> 00:24:19,810 >> Так что это слияние. 613 00:24:19,810 --> 00:24:20,610 Потому что думать об этом. 614 00:24:20,610 --> 00:24:25,420 При объединении восемь человек вместе, посредством чего половина из них представляют собой набор из четырех 615 00:24:25,420 --> 00:24:27,770 и другая половина другой набор из четырех, как вы идете 616 00:24:27,770 --> 00:24:28,820 о выполнении слияния? 617 00:24:28,820 --> 00:24:30,830 Ну, вы, ребята, сделали это довольно интуитивно. 618 00:24:30,830 --> 00:24:34,140 >> Но если бы я сделал это, а немного больше методично, я бы указал на 619 00:24:34,140 --> 00:24:38,090 левый человек сначала с моей левой стороны, указал на крайнюю левую человека 620 00:24:38,090 --> 00:24:42,080 что половина из своей правой рукой, и только впоследствии шли через 621 00:24:42,080 --> 00:24:46,990 список, указывая на наименьший элемент каждый раз, двигая пальцем по и 622 00:24:46,990 --> 00:24:48,970 за которые необходимы для создания списка. 623 00:24:48,970 --> 00:24:51,890 Но то, что об этой ключевой слияния процесс я сравниваю эти пары 624 00:24:51,890 --> 00:24:53,460 элементов. 625 00:24:53,460 --> 00:24:57,270 С правой половине и с левой половину, я никогда не отступает один раз. 626 00:24:57,270 --> 00:25:00,570 >> Так слиться принимает не более N шагов. 627 00:25:00,570 --> 00:25:03,250 И сколько раз у меня есть сделать это слияние? 628 00:25:03,250 --> 00:25:07,150 Ну, не больше, чем N, и мы просто увидел, что с окончательным слиянием. 629 00:25:07,150 --> 00:25:13,120 И так, если вы делаете то, что занимает войти N п шагов раза, или наоборот, 630 00:25:13,120 --> 00:25:15,210 он собирается дать нам п раз журнал N. 631 00:25:15,210 --> 00:25:16,310 >> И почему это лучше? 632 00:25:16,310 --> 00:25:19,600 Ну, если мы уже знаем, что журнал N лучше, чем N - не так ли? 633 00:25:19,600 --> 00:25:22,590 Мы видели в бинарный поиск, телефонная книга Например, журнал N был определенно 634 00:25:22,590 --> 00:25:23,760 лучше, чем линейные. 635 00:25:23,760 --> 00:25:28,420 Значит, раз журнал N п определенно лучше, чем N раз другое 636 00:25:28,420 --> 00:25:30,390 N, N AKA квадрате. 637 00:25:30,390 --> 00:25:32,400 И это то, что мы в конечном итоге чувствуют. 638 00:25:32,400 --> 00:25:34,928 >> Настолько большие аплодисменты, если Мы могли бы, этих парней. 639 00:25:34,928 --> 00:25:38,920 >> [Аплодисменты] 640 00:25:38,920 --> 00:25:41,550 >> DAVID МАЛАН: И ваши подарки Расставание - Вы можете сохранить номера, 641 00:25:41,550 --> 00:25:44,010 Если вы хотели бы. 642 00:25:44,010 --> 00:25:45,620 И ваш прощальный подарок, как обычно. 643 00:25:45,620 --> 00:25:47,290 О, и мы вышлем Вам кадры, Мишель. 644 00:25:47,290 --> 00:25:48,343 Спасибо. 645 00:25:48,343 --> 00:25:49,250 Хорошо. 646 00:25:49,250 --> 00:25:50,400 Помочь себе стресс мяч. 647 00:25:50,400 --> 00:25:54,110 >> И позвольте мне подтянуть, в то же время, наш друг Роб Боуден предложить 648 00:25:54,110 --> 00:25:59,520 Несколько иной взгляд на это, так как вы можете думать об этих 649 00:25:59,520 --> 00:26:01,280 шагов происходит в несколько другому. 650 00:26:01,280 --> 00:26:04,750 На самом деле, установка за то, что Роб о чтобы показать нам, предполагает, что мы 651 00:26:04,750 --> 00:26:09,030 уже сделали дележ большой список на восемь небольших списков, 652 00:26:09,030 --> 00:26:10,570 каждая размером 1. 653 00:26:10,570 --> 00:26:13,350 >> Таким образом, мы меняем псевдокод немного только к виду получить в 654 00:26:13,350 --> 00:26:15,320 Основная идея, как слияние работ. 655 00:26:15,320 --> 00:26:17,600 Но время работы, что он собирается сделать, это по-прежнему 656 00:26:17,600 --> 00:26:19,110 будет тем же самым. 657 00:26:19,110 --> 00:26:23,540 И снова, настройки здесь является то, что он началось с восемью списки размера 1. 658 00:26:23,540 --> 00:26:27,730 Итак, вы пропустили часть, где он на самом деле сделали журнал N, N журнал, журнал N 659 00:26:27,730 --> 00:26:31,205 разделение входного сигнала. 660 00:26:31,205 --> 00:26:32,120 >> [ВОСПРОИЗВЕДЕНИЕ ВИДЕО] 661 00:26:32,120 --> 00:26:33,615 >> -Вот и все на первом шаге. 662 00:26:33,615 --> 00:26:38,270 Для второго шага, неоднократно объединяет пару списков. 663 00:26:38,270 --> 00:26:39,210 >> DAVID МАЛАН: Хм. 664 00:26:39,210 --> 00:26:41,270 Только звук идет из моего компьютера. 665 00:26:41,270 --> 00:26:42,520 Давайте попробуем еще раз. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Просто произвольно выбрать, какой - теперь у нас есть четыре списка. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Узнать раньше. 670 00:26:52,120 --> 00:26:53,040 >> DAVID МАЛАН: Там мы идем. 671 00:26:53,040 --> 00:27:00,510 >> Слияние-108 и 15, мы в конце с списке 15, 108. 672 00:27:00,510 --> 00:27:07,170 Слияние 50 и 4, мы в конечном итоге с 4, 50. 673 00:27:07,170 --> 00:27:12,990 Слияние 8 и 42, мы в конечном итоге с 8, 42. 674 00:27:12,990 --> 00:27:19,970 И слияние 23 и 16, мы в конечном итоге с 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Теперь все наши списки размера 2. 676 00:27:23,270 --> 00:27:26,690 Следует отметить, что каждый из четыре списка отсортированы. 677 00:27:26,690 --> 00:27:29,450 Так мы можем начать слияние пар списки. 678 00:27:29,450 --> 00:27:38,420 Слияние 15 и 108, 4 и 50, мы сначала взять 4, то 15, то 679 00:27:38,420 --> 00:27:41,500 50, то 108. 680 00:27:41,500 --> 00:27:50,610 Слияние 8, 42 и 16, 23, мы сначала 8, то 16, то 23, 681 00:27:50,610 --> 00:27:52,700 то 42. 682 00:27:52,700 --> 00:27:57,600 >> Так что теперь у нас есть только два списка размер 4, каждый из которых сортируют. 683 00:27:57,600 --> 00:28:01,170 Так что теперь мы объединить эти два списка. 684 00:28:01,170 --> 00:28:11,835 Во-первых, мы берем 4, то возьмем 8, то мы берем 15, то 16, то 685 00:28:11,835 --> 00:28:19,456 23, то 42, то 50, то 108. 686 00:28:19,456 --> 00:28:19,872 >> [КОНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] 687 00:28:19,872 --> 00:28:23,430 >> DAVID не МАЛАН: Опять же, заметьте, он никогда коснулся данной чашки более одного раза 688 00:28:23,430 --> 00:28:24,860 после роста за его пределами. 689 00:28:24,860 --> 00:28:26,200 Так он никогда не повторяется. 690 00:28:26,200 --> 00:28:29,850 Значит, он всегда движется в сторону, а вот где мы получили нашу н. 691 00:28:29,850 --> 00:28:33,290 >> Почему бы не позволить мне подтянуть одну анимацию , что мы видели ранее, но на этот раз 692 00:28:33,290 --> 00:28:35,110 ориентируясь только на сортировки слиянием. 693 00:28:35,110 --> 00:28:38,030 Позвольте мне идти вперед и увеличения на этом здесь. 694 00:28:38,030 --> 00:28:42,530 Прежде всего позвольте мне выбрать случайный ввод, увеличить это, и вы можете сортировать, см. 695 00:28:42,530 --> 00:28:46,600 то, что мы считали само собой разумеющимся, ранее, сортировка слиянием на самом деле делает. 696 00:28:46,600 --> 00:28:50,330 >> Так заметите, что вы получите эти половинки или этих кварталов или эти восьмых 697 00:28:50,330 --> 00:28:53,140 проблема, которая вдруг начать принимать хорошей форме. 698 00:28:53,140 --> 00:28:57,070 И, наконец, вы увидите в В самом конце, что БАМ, 699 00:28:57,070 --> 00:28:58,860 все объединены вместе. 700 00:28:58,860 --> 00:29:01,690 >> Так что это просто три разных берет на себя ту же идею. 701 00:29:01,690 --> 00:29:05,980 Но ключевое понимание, как и разрыва и победить в первом классе, 702 00:29:05,980 --> 00:29:10,640 было то, что мы решили как-то разделить Проблема в нечто большее, в 703 00:29:10,640 --> 00:29:14,760 что-то вроде идентичны по духу, но меньше и меньше 704 00:29:14,760 --> 00:29:15,660 и меньше. 705 00:29:15,660 --> 00:29:18,420 >> Теперь другой интересный способ сортировать думаю об этом, хотя это не 706 00:29:18,420 --> 00:29:20,520 собираюсь дать вам то же интуитивное понимании, 707 00:29:20,520 --> 00:29:21,640 Следующие анимации. 708 00:29:21,640 --> 00:29:25,400 Так что это видео кто-то положил вместе , что связано различных 709 00:29:25,400 --> 00:29:29,970 звуков с различных операций для сортировка вставками, для сортировки слиянием, и 710 00:29:29,970 --> 00:29:31,150 на пару других. 711 00:29:31,150 --> 00:29:32,330 Таким образом, в данный момент, я ударю Play. 712 00:29:32,330 --> 00:29:33,600 Это около минуты длиной. 713 00:29:33,600 --> 00:29:37,410 И даже если вы все еще можете увидеть модели происходит, это время вы можете 714 00:29:37,410 --> 00:29:41,420 также услышать, как эти алгоритмы выполнение по-разному и с 715 00:29:41,420 --> 00:29:43,950 несколько различных моделей. 716 00:29:43,950 --> 00:29:45,830 >> Это сортировку вставками. 717 00:29:45,830 --> 00:29:50,400 >> [TONES композиция] 718 00:29:50,400 --> 00:29:52,400 >> DAVID МАЛАН: Это снова пытается вставить каждый элемент 719 00:29:52,400 --> 00:29:52,900 в которой она принадлежит. 720 00:29:52,900 --> 00:29:54,628 Это пузырьковой сортировки. 721 00:29:54,628 --> 00:30:10,097 >> [TONES композиция] 722 00:30:10,097 --> 00:30:13,630 >> DAVID МАЛАН: И вы можете сортировать, чувство как относительно мало работать, что он делает 723 00:30:13,630 --> 00:30:15,834 на каждом шаге. 724 00:30:15,834 --> 00:30:20,470 Это то, что звучит как занудство. 725 00:30:20,470 --> 00:30:21,472 >> [TONES композиция] 726 00:30:21,472 --> 00:30:25,222 >> DAVID МАЛАН: Это выбор рода, где мы выбираем элемент, который мы формируем 727 00:30:25,222 --> 00:30:28,845 проходя снова и снова и снова и положить его в самом начале. 728 00:30:28,845 --> 00:30:37,674 >> [TONES композиция] 729 00:30:37,674 --> 00:30:43,970 >> DAVID МАЛАН: Это сортировки слиянием, которое Вы можете действительно начинаешь чувствовать. 730 00:30:43,970 --> 00:30:51,810 >> [TONES композиция] 731 00:30:51,810 --> 00:30:54,770 >> [Смеется] 732 00:30:54,770 --> 00:30:58,395 >> DAVID МАЛАН: То, что называется GNOME сортировка, которую мы не смотрели. 733 00:30:58,395 --> 00:31:13,630 >> [TONES композиция] 734 00:31:13,630 --> 00:31:17,910 >> DAVID МАЛАН: Так покажите, в настоящее время, отвлекаться, как вы, надеемся, по 735 00:31:17,910 --> 00:31:21,110 музыку, если я могу скользить немного немного математики здесь. 736 00:31:21,110 --> 00:31:24,850 Так что есть и четвертый путь, что мы можем думать о том, что это означает, что эти 737 00:31:24,850 --> 00:31:29,210 функций, которые будут быстрее, чем те, что мы видели раньше. 738 00:31:29,210 --> 00:31:32,470 И, если вы приезжаете на курс от математика фоном, вы 739 00:31:32,470 --> 00:31:36,030 на самом деле может быть, уже знаете, что вы может пощечину сроком на этой технике - 740 00:31:36,030 --> 00:31:40,400 а именно рекурсию, функции что так или иначе вызывает сам себя. 741 00:31:40,400 --> 00:31:44,780 >> И опять же, напомнить, что сортировка слиянием псевдокод рекурсивной в том смысле, 742 00:31:44,780 --> 00:31:48,460 что один из шагов сортировка слиянием в было призвать рода - 743 00:31:48,460 --> 00:31:49,740 то есть непосредственно. 744 00:31:49,740 --> 00:31:52,480 Но, к счастью, потому что мы продолжали вызова сортировку или сортировка слиянием, 745 00:31:52,480 --> 00:31:55,880 В частности, на меньшие и меньшие и меньше список, мы в конечном счете 746 00:31:55,880 --> 00:32:00,005 дна, благодаря чему мы будем называть базовый вариант, жестко случае, 747 00:32:00,005 --> 00:32:04,270 сказал, что если список небольшой, менее 2 В этом случае, просто немедленно вернуться. 748 00:32:04,270 --> 00:32:07,550 Если у нас не было, что особый случай, Алгоритм никогда не будет нижнего предела, 749 00:32:07,550 --> 00:32:11,010 и вы бы действительно попасть в бесконечный цикл действительно навсегда. 750 00:32:11,010 --> 00:32:14,330 >> Но предположим, что мы хотели сейчас поставлю некоторые номера на этом, опять же, с использованием н 751 00:32:14,330 --> 00:32:15,660 как размер входных данных. 752 00:32:15,660 --> 00:32:18,680 И я хотел бы спросить вас, что общее время, затрачиваемое на 753 00:32:18,680 --> 00:32:19,800 работает сортировка слиянием? 754 00:32:19,800 --> 00:32:22,960 Или более общем смысле, что стоимость его во времени? 755 00:32:22,960 --> 00:32:24,730 >> Ну, это довольно легко измерить это. 756 00:32:24,730 --> 00:32:29,010 Если N меньше 2, время, затрачиваемое В сортировку N элементов, 757 00:32:29,010 --> 00:32:30,480 где п равно 2, 0. 758 00:32:30,480 --> 00:32:31,410 Потому что мы просто возвращаем. 759 00:32:31,410 --> 00:32:32,510 Там нет работы, которую предстоит сделать. 760 00:32:32,510 --> 00:32:35,660 Теперь, возможно, может быть, это один шаг или два шаги, чтобы выяснить количество 761 00:32:35,660 --> 00:32:38,420 работать, но это достаточно близко к 0, что Я просто хочу сказать, нет работы 762 00:32:38,420 --> 00:32:40,940 требуется, если список настолько мала быть неинтересным. 763 00:32:40,940 --> 00:32:42,580 >> Но этот случай интересен. 764 00:32:42,580 --> 00:32:47,320 Рекурсивные случай был филиал псевдокод, сказал еще, отсортируйте 765 00:32:47,320 --> 00:32:52,000 левая половина, сортировать право половину, объединить две половины. 766 00:32:52,000 --> 00:32:55,530 Теперь почему это выражение заявляете, что счет? 767 00:32:55,530 --> 00:32:58,690 Ну, T п просто означает, что время, чтобы разобраться N элементов. 768 00:32:58,690 --> 00:33:03,070 А затем на правой стороне Знак равенства там, T п разделенный 769 00:33:03,070 --> 00:33:06,600 2 Имеется в виду стоимость того, что? 770 00:33:06,600 --> 00:33:07,570 Сортировка левую половину. 771 00:33:07,570 --> 00:33:10,990 Другой T п деленное на 2 предположительно со ссылкой на стоимость 772 00:33:10,990 --> 00:33:12,390 сортировать правую половину. 773 00:33:12,390 --> 00:33:14,590 >> И тогда N Plus? 774 00:33:14,590 --> 00:33:15,420 Это слияние. 775 00:33:15,420 --> 00:33:19,120 Потому что, если у вас есть два списка, один из Размер п над 2 и другим размером N 776 00:33:19,120 --> 00:33:22,580 более 2, вы должны коснуться по существу каждого из этих элементов, как и Роб 777 00:33:22,580 --> 00:33:24,990 коснулась каждой из чашек, и только как указывалось в каждом из 778 00:33:24,990 --> 00:33:26,310 добровольцев на сцене. 779 00:33:26,310 --> 00:33:28,790 Так п за счет слияния. 780 00:33:28,790 --> 00:33:31,780 >> Сейчас, к сожалению, эта формула Также сама рекурсивной. 781 00:33:31,780 --> 00:33:36,390 Таким образом, если задан вопрос, если п, скажем, 16, если есть 16 человек на сцене 782 00:33:36,390 --> 00:33:40,670 или 16 чашек в видео, сколько всего шаги нужно для того, чтобы отсортировать их 783 00:33:40,670 --> 00:33:41,550 с сортировки слиянием? 784 00:33:41,550 --> 00:33:45,790 Это на самом деле не очевидный ответ, потому что теперь у вас есть к виду 785 00:33:45,790 --> 00:33:48,500 рекурсивно ответить на этот формуле. 786 00:33:48,500 --> 00:33:51,190 >> Но это нормально, потому что то позвольте мне выдвинуть что мы делаем следующее. 787 00:33:51,190 --> 00:33:56,670 Времени, необходимого для сортировки или 16 человек 16 чашек, которые будут представлены 788 00:33:56,670 --> 00:33:58,020 вообще как Т 16. 789 00:33:58,020 --> 00:34:01,400 Но, равный, по нашим предыдущей формуле, 2 раза количество 790 00:34:01,400 --> 00:34:04,780 Время, необходимое для сортировки 8 чашек плюс 16. 791 00:34:04,780 --> 00:34:08,590 И опять же, плюс 16 самое время объединяться, и два раза Т 8 792 00:34:08,590 --> 00:34:10,790 время, чтобы разобраться левая половина и правая половина. 793 00:34:10,790 --> 00:34:11,989 >> Но опять же, этого недостаточно. 794 00:34:11,989 --> 00:34:13,210 Мы должны погрузиться в более глубоких. 795 00:34:13,210 --> 00:34:16,409 Это означает, что мы должны ответить вопрос, что такое Т 8? 796 00:34:16,409 --> 00:34:19,610 Ну Т 8 находится всего в 2 раз T 4 плюс 8. 797 00:34:19,610 --> 00:34:20,520 Ну, что Т 4? 798 00:34:20,520 --> 00:34:23,780 Т 4 находится всего в 2 раза Т 2 плюс 4. 799 00:34:23,780 --> 00:34:25,489 Ну, что Т 2? 800 00:34:25,489 --> 00:34:29,030 Т 2 находится всего в 2 раза Т 1 плюс 2. 801 00:34:29,030 --> 00:34:31,940 >> И опять же, мы вроде получения застрял в этом цикле. 802 00:34:31,940 --> 00:34:34,790 Но речь идет о ударить, что так называемый базовый вариант. 803 00:34:34,790 --> 00:34:37,310 Потому что то, Т 1, разве мы утверждаем? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Так что теперь, наконец, мы можем работать в обратном направлении. 806 00:34:39,730 --> 00:34:44,290 >> Если Т 1 0, теперь я могу вернуться до одного линии Вот этот парень, и я могу 807 00:34:44,290 --> 00:34:46,330 подключите 0 для T 1. 808 00:34:46,330 --> 00:34:51,770 Значит, она равна нулю 2 раза, иначе известный как 0, а также 2. 809 00:34:51,770 --> 00:34:53,739 И так, чтобы все выражение 2. 810 00:34:53,739 --> 00:34:58,740 >> Теперь, если я беру Т 2, ответ на 2, подключить его к средней линии, T 811 00:34:58,740 --> 00:35:02,740 4, то это дает мне 2 раза 2 плюс 4, поэтому 8. 812 00:35:02,740 --> 00:35:07,080 Если я после этого подключить 8 к предыдущему линии, что дает мне 2 раза 8, 16. 813 00:35:07,080 --> 00:35:12,470 И если мы будем продолжать то, что с 24, добавив в 16, мы, наконец, получить 814 00:35:12,470 --> 00:35:13,820 значение 64. 815 00:35:13,820 --> 00:35:18,480 >> Теперь, когда само по себе говорит рода Ничего обозначение N, 816 00:35:18,480 --> 00:35:20,700 Big O, омега, которые мы говорили. 817 00:35:20,700 --> 00:35:24,890 Но оказывается, что на самом деле 64 16, размер входного 818 00:35:24,890 --> 00:35:27,110 логарифм по основанию 2 из 16. 819 00:35:27,110 --> 00:35:30,200 И если это немного незнакомым, просто вспоминаю, и вернусь 820 00:35:30,200 --> 00:35:30,700 Вам в конце концов. 821 00:35:30,700 --> 00:35:33,775 Если это логарифм по основанию 2, это как 2 возведенное в то, что дает вам 16? 822 00:35:33,775 --> 00:35:36,380 О, это 4, так что это 16 раз 4. 823 00:35:36,380 --> 00:35:39,380 >> И опять же, это не имеет большого значения, если это является своего рода туманный памяти сейчас. 824 00:35:39,380 --> 00:35:43,720 Но сейчас, принимать на веру что 16 журнал 16 равно 64. 825 00:35:43,720 --> 00:35:46,590 И так действительно, с помощью этого простого здравомыслия проверить, мы подтвердили - 826 00:35:46,590 --> 00:35:48,250 но формально не доказана - 827 00:35:48,250 --> 00:35:52,800 что время слияния Сортировать действительно N N войти. 828 00:35:52,800 --> 00:35:53,790 >> Так не плохо. 829 00:35:53,790 --> 00:35:57,260 Это определенно лучше, чем алгоритмы, которые мы видели до сих пор, и 830 00:35:57,260 --> 00:36:00,710 это потому, что мы использовала, один, методику, которая называется рекурсией. 831 00:36:00,710 --> 00:36:03,880 Но что еще более интересно, чем та, что Понятие деления и завоевание. 832 00:36:03,880 --> 00:36:07,460 Опять же, по-настоящему неделя 0 вещи, которые даже сейчас повторяется в 833 00:36:07,460 --> 00:36:08,740 более убедительным способом. 834 00:36:08,740 --> 00:36:11,750 >> Теперь удовольствия мало упражнений, если у Вас есть никогда не делал этого, - и вы, вероятно, 835 00:36:11,750 --> 00:36:14,660 не будет, так как вид нормального люди не думают, чтобы сделать это. 836 00:36:14,660 --> 00:36:20,650 Но если я иду на google.com и если Я хочу узнать что-нибудь о 837 00:36:20,650 --> 00:36:22,356 рекурсию, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Смеется] 840 00:36:29,058 --> 00:36:32,030 [Смех] 841 00:36:32,030 --> 00:36:33,385 DAVID МАЛАН: плохая шутка постепенно распространяется. 842 00:36:33,385 --> 00:36:34,450 [Смеется] 843 00:36:34,450 --> 00:36:36,970 DAVID МАЛАН: На всякий случай, что она есть. 844 00:36:36,970 --> 00:36:38,710 Я не записать это неправильно, и есть шутка. 845 00:36:38,710 --> 00:36:40,810 Хорошо. 846 00:36:40,810 --> 00:36:42,950 Объясните это люди рядом с вами, если Это не совсем нажата только пока. 847 00:36:42,950 --> 00:36:47,650 Но рекурсии, в целом, относится в процессе вызова функции 848 00:36:47,650 --> 00:36:51,430 себе, или в более общем, разделив Проблема в то, что может быть 849 00:36:51,430 --> 00:36:56,220 решить по частям решения идентичных Представитель проблем. 850 00:36:56,220 --> 00:36:58,400 >> Ну, давайте передач изменения на мгновение. 851 00:36:58,400 --> 00:37:00,840 Мы бы закончить на определенных кульминаций, так что давайте начнем устанавливать 852 00:37:00,840 --> 00:37:05,870 этап, в течение нескольких минут на очень простой идее - 853 00:37:05,870 --> 00:37:07,620 перекачки, что два элемента, не так ли? 854 00:37:07,620 --> 00:37:10,040 Все эти алгоритмы мы были Говоря о последних нескольких 855 00:37:10,040 --> 00:37:12,420 Лекции включают некоторые рода замены. 856 00:37:12,420 --> 00:37:14,630 Сегодня было визуализировали их получения вверх из своего стула и 857 00:37:14,630 --> 00:37:18,570 ходят, но в коде, мы бы просто взять элемент из одного массива 858 00:37:18,570 --> 00:37:20,370 и вставить его в другой. 859 00:37:20,370 --> 00:37:21,880 >> Так как же нам идти об этом? 860 00:37:21,880 --> 00:37:24,850 Ну, позвольте мне идти вперед и написать быстрый программу здесь. 861 00:37:24,850 --> 00:37:31,600 Я собираюсь идти вперед и делать это как следующее. 862 00:37:31,600 --> 00:37:33,910 Давайте назовем это - 863 00:37:33,910 --> 00:37:38,070 Чего мы хотим назвать это одна? 864 00:37:38,070 --> 00:37:38,650 >> Вообще-то, нет. 865 00:37:38,650 --> 00:37:39,420 Позвольте мне перемотки назад. 866 00:37:39,420 --> 00:37:41,220 Я не хочу, чтобы сделать это еще захватывающим. 867 00:37:41,220 --> 00:37:42,270 Это испортит удовольствие. 868 00:37:42,270 --> 00:37:43,600 Давайте сделаем это вместо этого. 869 00:37:43,600 --> 00:37:47,430 >> Предположим, что я хочу написать немного программа и что в настоящее время использует эту 870 00:37:47,430 --> 00:37:48,700 Идея рекурсии. 871 00:37:48,700 --> 00:37:50,370 Я бы получил впереди себя там. 872 00:37:50,370 --> 00:37:51,420 Я собираюсь сделать следующее. 873 00:37:51,420 --> 00:38:00,220 >> Во-первых, быстро включать стандартные io.h, а также включать в себя, cs50.h. 874 00:38:00,220 --> 00:38:03,200 А потом я собираюсь идти вперед и объявить недействительным тап_п 875 00:38:03,200 --> 00:38:04,360 в обычном порядке. 876 00:38:04,360 --> 00:38:07,920 Я понял, я неверно названы файл, так что позвольте мне добавить. C расширением вот так 877 00:38:07,920 --> 00:38:09,510 что мы можем скомпилировать его должным образом. 878 00:38:09,510 --> 00:38:10,970 Начать эту функцию. 879 00:38:10,970 --> 00:38:13,290 >> А функция Я хочу написать, довольно Проще говоря, это тот, который спрашивает 880 00:38:13,290 --> 00:38:16,210 пользователя число, а затем складывает все числа между этим 881 00:38:16,210 --> 00:38:19,920 числа и, скажем, 0. 882 00:38:19,920 --> 00:38:22,510 Итак, сначала я собираюсь идти вперед и объявить Int N. 883 00:38:22,510 --> 00:38:24,760 Затем я копирую код, который мы использовали на некоторое время. 884 00:38:24,760 --> 00:38:26,660 Хотя кое-что верно. 885 00:38:26,660 --> 00:38:28,000 Я вернусь к этому чуть позже. 886 00:38:28,000 --> 00:38:29,010 >> Что я хочу сделать? 887 00:38:29,010 --> 00:38:33,460 Я хочу сказать, Е положительной целое пожалуйста. 888 00:38:33,460 --> 00:38:36,130 А потом я собираюсь говорят N получает получить Int. 889 00:38:36,130 --> 00:38:38,800 Итак, еще раз, некоторые шаблонный код что мы использовали раньше. 890 00:38:38,800 --> 00:38:40,810 И я собираюсь это сделать а п меньше 1. 891 00:38:40,810 --> 00:38:44,120 Так что это будет гарантировать, что пользователь дает мне положительное целое число. 892 00:38:44,120 --> 00:38:45,490 >> А теперь я собираюсь сделать следующее. 893 00:38:45,490 --> 00:38:51,020 Я хочу сложить все числа от 1 и N, или от 0 до N, 894 00:38:51,020 --> 00:38:52,570 то же самое, чтобы получить общую сумму. 895 00:38:52,570 --> 00:38:55,100 Так что самый большой символ Sigma что вы могли бы вспомнить. 896 00:38:55,100 --> 00:38:59,050 Так что я собираюсь сделать это, первого созыва функция под названием Sigma, 897 00:38:59,050 --> 00:39:06,030 передавая его по-русски, а затем я собираюсь Е сказать, ответ тут же. 898 00:39:06,030 --> 00:39:08,180 >> Короче говоря, я получаю и Int от пользователя. 899 00:39:08,180 --> 00:39:09,280 Я могу гарантировать, что это положительно. 900 00:39:09,280 --> 00:39:12,700 Я объявляю переменную ответ целого типа и хранить в его возвращение 901 00:39:12,700 --> 00:39:15,610 Значение сигма, передавая N качестве входных данных. 902 00:39:15,610 --> 00:39:17,060 И тогда я распечатать, что ответить. 903 00:39:17,060 --> 00:39:19,550 >> К сожалению, хотя сигма звучит как нечто, что может быть в 904 00:39:19,550 --> 00:39:24,040 math.h файла, его декларации, это на самом деле нет. 905 00:39:24,040 --> 00:39:24,690 Так что это нормально. 906 00:39:24,690 --> 00:39:26,170 Можно реализовать это сам. 907 00:39:26,170 --> 00:39:29,160 Я собираюсь реализовать функцию называют Sigma, и он собирается взять 908 00:39:29,160 --> 00:39:29,900 параметра - 909 00:39:29,900 --> 00:39:32,100 Давайте просто называть это м, всего так все по-другому. 910 00:39:32,100 --> 00:39:35,910 А потом здесь, я собираюсь сказать, Ну, если м меньше 1 - это 911 00:39:35,910 --> 00:39:38,180 очень неинтересные программы. 912 00:39:38,180 --> 00:39:41,700 Так что я собираюсь идти вперед и немедленно вернуть 0. 913 00:39:41,700 --> 00:39:45,920 Это просто не имеет смысла сложить все числа от 1 м, если м 914 00:39:45,920 --> 00:39:48,470 само 0 или отрицательным. 915 00:39:48,470 --> 00:39:50,900 >> А потом я собираюсь идти вперед и делать это очень итеративно. 916 00:39:50,900 --> 00:39:53,090 Я собираюсь делать такого рода старой школы, и я собираюсь идти вперед 917 00:39:53,090 --> 00:39:57,150 и сказать, что я собираюсь объявить сумму равным 0. 918 00:39:57,150 --> 00:39:59,630 Тогда я буду иметь для петли Int - 919 00:39:59,630 --> 00:40:02,820 и позвольте мне сделать это в соответствии с нашими Распределение кода, поэтому у вас есть копия 920 00:40:02,820 --> 00:40:07,500 дома. INT I получает 1 на до я меньше или равна м. 921 00:40:07,500 --> 00:40:09,430 Я плюс плюс. 922 00:40:09,430 --> 00:40:11,430 И тогда внутри этого цикла - 923 00:40:11,430 --> 00:40:12,440 мы почти на месте - 924 00:40:12,440 --> 00:40:15,810 сумма попадает сумма плюс 1. 925 00:40:15,810 --> 00:40:17,670 А потом я собираюсь вернуть сумму. 926 00:40:17,670 --> 00:40:19,420 >> Так что я сделал это быстро, совсем правда. 927 00:40:19,420 --> 00:40:22,775 Но, опять же, основная функция довольно просто на основе кода, который мы 928 00:40:22,775 --> 00:40:23,190 написано до сих пор. 929 00:40:23,190 --> 00:40:25,610 Использует двойную петлю, чтобы получить положительный Int от пользователя. 930 00:40:25,610 --> 00:40:29,870 Я затем передать десятичного к новой функции называется сигма, назвав его, опять же, с. 931 00:40:29,870 --> 00:40:33,100 И я хранения возвращаемого значения, ответ от черного ящика настоящее время 932 00:40:33,100 --> 00:40:35,460 известный как сигма, в переменную называют ответом. 933 00:40:35,460 --> 00:40:36,580 Тогда я распечатать его. 934 00:40:36,580 --> 00:40:39,090 >> Если мы теперь продолжим рассказ, каким сигма реализованы? 935 00:40:39,090 --> 00:40:40,840 Я предлагаю реализовать следующим образом. 936 00:40:40,840 --> 00:40:43,560 Во-первых, немного проверки ошибок чтобы убедиться, что пользователь не 937 00:40:43,560 --> 00:40:46,480 возиться со мной и передав некоторые отрицательные или значение 0. 938 00:40:46,480 --> 00:40:49,710 Тогда я объявляю переменную сумму и установить его в 0. 939 00:40:49,710 --> 00:40:55,910 >> И теперь я начинаю переходить от Я равно 1 все, вплоть до и включая м, 940 00:40:55,910 --> 00:41:00,130 потому что я хочу, чтобы включить все числа от одного до М включительно. 941 00:41:00,130 --> 00:41:04,350 А внутри этого цикла, я просто Сумма получает то, что он есть сейчас, плюс 942 00:41:04,350 --> 00:41:08,900 Значение я. 943 00:41:08,900 --> 00:41:10,370 Кроме того значение я. 944 00:41:10,370 --> 00:41:14,090 >> Как в стороне, если вы не видели этого и прежде, есть некоторые синтаксический сахар 945 00:41:14,090 --> 00:41:14,870 для этой линии. 946 00:41:14,870 --> 00:41:21,120 Я могу переписать это как плюс Я равно, просто чтобы спасти себя несколько нажатий клавиш 947 00:41:21,120 --> 00:41:22,570 и выглядеть немного прохладнее. 948 00:41:22,570 --> 00:41:23,140 Но вот и все. 949 00:41:23,140 --> 00:41:24,660 Это функционально то же самое. 950 00:41:24,660 --> 00:41:26,710 >> К сожалению, эта кода Не собираетесь компилировать еще. 951 00:41:26,710 --> 00:41:31,600 Если я запускаю сделать сигма 0, как же я Я собираюсь получить кричал на? 952 00:41:31,600 --> 00:41:33,473 Как это будет, не нравится? 953 00:41:33,473 --> 00:41:35,740 >> АУДИТОРИЯ: [неразборчиво]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID МАЛАН: Да, я не объявлял Функция наверху, не так ли? 955 00:41:37,800 --> 00:41:40,590 C отчасти глупо, тем, что он только делает то, что вы скажете ей сделать, и вы 956 00:41:40,590 --> 00:41:41,880 должны сделать это в таком порядке. 957 00:41:41,880 --> 00:41:45,910 И поэтому, если я ударил Введите здесь, я собираюсь получить предупреждение о Sigma неявной 958 00:41:45,910 --> 00:41:46,860 декларации. 959 00:41:46,860 --> 00:41:48,120 >> О, не проблема. 960 00:41:48,120 --> 00:41:50,370 Я могу подняться на самый верх, и я могу говорят, все в порядке, подожди минутку. 961 00:41:50,370 --> 00:41:54,240 Sigma является функцией, которая возвращает Целочисленное и он ожидает 962 00:41:54,240 --> 00:41:56,620 ИНТАС входа, точка с запятой. 963 00:41:56,620 --> 00:41:59,550 Или я мог бы поставить весь функции над главной, но в целом, я бы 964 00:41:59,550 --> 00:42:02,260 рекомендую против этого, потому что это хорошо, чтобы всегда иметь основные наверху, таким образом 965 00:42:02,260 --> 00:42:06,310 Вы сможете погрузиться в них и знаю, что Программа делает, читая основные первым. 966 00:42:06,310 --> 00:42:07,930 >> Так что теперь позвольте мне очистить экран. 967 00:42:07,930 --> 00:42:09,330 Римейк сигма 0. 968 00:42:09,330 --> 00:42:10,340 Все, кажется, чтобы проверить. 969 00:42:10,340 --> 00:42:11,970 Позвольте мне запустить сигма 0. 970 00:42:11,970 --> 00:42:12,770 Положительное в том. 971 00:42:12,770 --> 00:42:15,580 Я дам ему количество 3 сохранить его простым. 972 00:42:15,580 --> 00:42:18,710 Итак, что должен дать мне 3 плюс два плюс один, так 6. 973 00:42:18,710 --> 00:42:20,750 Введите, да и вообще я получаю 6. 974 00:42:20,750 --> 00:42:21,820 >> Я могу сделать что-то большее - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Так же, как касательной, я собираюсь сделать что-то смешное, как действительно большой 977 00:42:27,690 --> 00:42:30,375 число, О, это фактически удалось - 978 00:42:30,375 --> 00:42:31,600 Эх, я не думаю, что это правильно. 979 00:42:31,600 --> 00:42:32,810 Давайте посмотрим. 980 00:42:32,810 --> 00:42:34,060 Давайте уж возиться с ним. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Это проблема. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Что происходит? 985 00:42:44,970 --> 00:42:46,050 Кода не так уж плохо. 986 00:42:46,050 --> 00:42:48,470 Он по-прежнему линейно. 987 00:42:48,470 --> 00:42:50,810 Свист является хорошим эффектом, однако. 988 00:42:50,810 --> 00:42:52,060 Что происходит? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Не уверен, что я услышал его. 991 00:42:55,620 --> 00:42:57,620 Вот и получается, - и это как в сторону. 992 00:42:57,620 --> 00:42:59,400 Это не сердечника Идея рекурсии. 993 00:42:59,400 --> 00:43:02,480 Оказывается, потому, что я пытаюсь представляют такое большое количество, большинство 994 00:43:02,480 --> 00:43:06,980 вероятно, это неправильной интерпретации на С, не положительное число, 995 00:43:06,980 --> 00:43:09,980 но отрицательное число. 996 00:43:09,980 --> 00:43:12,690 >> Мы не говорили об этом, но это Оказывается, есть отрицательные числа 997 00:43:12,690 --> 00:43:14,210 в мире в дополнение на положительные числа. 998 00:43:14,210 --> 00:43:16,290 И средства, с помощью которых вы можете представляют собой отрицательное число 999 00:43:16,290 --> 00:43:19,530 по сути является, используется один специальный бит, чтобы указать, 1000 00:43:19,530 --> 00:43:20,400 положительные над негативными. 1001 00:43:20,400 --> 00:43:22,950 Это немного сложнее, чем, но это основная идея. 1002 00:43:22,950 --> 00:43:26,740 >> Поэтому, к сожалению, тогда, когда С запутанной один из тех битов, на самом деле это означает, 1003 00:43:26,740 --> 00:43:30,790 о, это отрицательное число, мой цикл Здесь, например, нет фактически никогда 1004 00:43:30,790 --> 00:43:31,740 собирается прекратить. 1005 00:43:31,740 --> 00:43:33,850 Так что если я на самом деле были напечатав что-нибудь снова и снова, мы, 1006 00:43:33,850 --> 00:43:34,650 см. много. 1007 00:43:34,650 --> 00:43:36,220 Но опять же, это, кроме точки. 1008 00:43:36,220 --> 00:43:38,590 Это действительно так, вроде интеллектуальное любопытство, что мы приедем 1009 00:43:38,590 --> 00:43:39,550 вернуться к в конце концов. 1010 00:43:39,550 --> 00:43:43,400 Но сейчас, это правильное реализацию, если мы предполагаем, что 1011 00:43:43,400 --> 00:43:45,970 Пользователь обеспечит целых , которые вписываются в целые. 1012 00:43:45,970 --> 00:43:49,370 >> Но я утверждаю, что этот код, честно говоря, можно было бы сделать гораздо больше, просто. 1013 00:43:49,370 --> 00:43:54,060 Если цель под рукой принять ряд м, как и сложите все 1014 00:43:54,060 --> 00:43:59,510 номера между ним и один или, наоборот между 1 и это, я утверждаю, 1015 00:43:59,510 --> 00:44:03,380 что я могу занять эту идею, которые сливаются Сортировать имел, который принимал проблемы 1016 00:44:03,380 --> 00:44:05,660 такого размера и разделив ее во что-то меньше. 1017 00:44:05,660 --> 00:44:09,875 Может быть, не половина, но меньше, но представительно то же самое. 1018 00:44:09,875 --> 00:44:12,130 Та же самая идея, но меньшие проблемы. 1019 00:44:12,130 --> 00:44:15,470 >> Так что я на самом деле - позвольте мне сохранить этот файл с другой номер версии. 1020 00:44:15,470 --> 00:44:17,670 Мы назовем эту версию 1 вместо 0. 1021 00:44:17,670 --> 00:44:20,790 И я утверждаю, что я могу реально переопределить эту в такого рода 1022 00:44:20,790 --> 00:44:22,160 галлюциногенный пути. 1023 00:44:22,160 --> 00:44:23,710 >> Я собираюсь оставить часть его в покое. 1024 00:44:23,710 --> 00:44:27,710 Я собирался сказать, если т меньше чем или равное 0 - 1025 00:44:27,710 --> 00:44:29,280 Я просто хочу быть немного Еще Анальный этот раз 1026 00:44:29,280 --> 00:44:30,520 с моей проверки ошибок - 1027 00:44:30,520 --> 00:44:33,190 Я собираюсь идти вперед и возвращает 0. 1028 00:44:33,190 --> 00:44:34,490 Это произвольное. 1029 00:44:34,490 --> 00:44:37,500 Я просто Просто решить, если пользователь дает мне отрицательным числом, я 1030 00:44:37,500 --> 00:44:41,490 возвращаем 0, и они должны были прочитать документации более внимательно. 1031 00:44:41,490 --> 00:44:42,170 >> Остальное - 1032 00:44:42,170 --> 00:44:44,070 заметить, что я собираюсь делать. 1033 00:44:44,070 --> 00:44:49,260 Остальное я собираюсь вернуться м плюс - 1034 00:44:49,260 --> 00:44:51,010 что сигма-м? 1035 00:44:51,010 --> 00:44:56,710 Ну, сигма-м плюс минус 1 м, м плюс минус 2, плюс минус 3 м. 1036 00:44:56,710 --> 00:44:58,030 Я не хочу писать все это. 1037 00:44:58,030 --> 00:44:59,120 Почему бы мне просто не плоскодонки? 1038 00:44:59,120 --> 00:45:05,080 Рекурсивный называю себя со слегка меньшая проблема, точку с запятой 1039 00:45:05,080 --> 00:45:06,840 и назовите его день? 1040 00:45:06,840 --> 00:45:07,040 >> Верно? 1041 00:45:07,040 --> 00:45:10,980 Теперь и здесь, вы можете почувствовать или беспокоиться что это бесконечный цикл, который я 1042 00:45:10,980 --> 00:45:15,450 вызывающие, в результате чего я реализую Sigma Sigma по телефону. 1043 00:45:15,450 --> 00:45:20,342 Но это совершенно нормально, потому что я думал, впереди которой добавлены линии? 1044 00:45:20,342 --> 00:45:22,600 >> АУДИТОРИЯ: [неразборчиво]. 1045 00:45:22,600 --> 00:45:25,430 >> Дэвид МАЛАН: от 23 до 26, которые Если мое состояние. 1046 00:45:25,430 --> 00:45:28,390 Потому что приятно об вычитание здесь, потому что я держу 1047 00:45:28,390 --> 00:45:31,180 вручать сигма меньше проблем меньше проблемы, меньше - это не 1048 00:45:31,180 --> 00:45:31,870 в два раза меньше. 1049 00:45:31,870 --> 00:45:34,380 Это всего лишь шаг ребенка меньше, но это нормально. 1050 00:45:34,380 --> 00:45:38,050 Потому что в конечном итоге, мы будем работать наш путь вниз к 1 или 0. 1051 00:45:38,050 --> 00:45:41,630 И как только мы поразили 0, Sigma не собираюсь называть себя больше. 1052 00:45:41,630 --> 00:45:43,590 Это собирается немедленно вернуть 0. 1053 00:45:43,590 --> 00:45:47,960 >> Таким образом, эффект, если вы рода Ветер этом в своем уме, является добавление м плюс 1054 00:45:47,960 --> 00:45:52,740 м минус 1, плюс минус 2 м, м плюс минус 3, а также точка, точка, точка, М минус 1055 00:45:52,740 --> 00:45:57,820 м, в конечном итоге дает вам 0, а эффект в конечном счете, чтобы добавить все 1056 00:45:57,820 --> 00:45:59,070 эти вещи вместе. 1057 00:45:59,070 --> 00:46:02,380 Так что мы не имеем с рекурсией, решена проблема, которую мы 1058 00:46:02,380 --> 00:46:03,470 не могли решить раньше. 1059 00:46:03,470 --> 00:46:06,840 Действительно, версия 0 об этом, и каждый Проблема на сегодняшний день, были разрешимы 1060 00:46:06,840 --> 00:46:09,980 только с использованием для петли или в то время как петли или аналогичных конструкций. 1061 00:46:09,980 --> 00:46:13,150 >> Но рекурсию, я полагаю, дает нам другой способ мышления о 1062 00:46:13,150 --> 00:46:17,010 проблемы, согласно которому, если мы можем взять Проблема, разделите его от чего-то 1063 00:46:17,010 --> 00:46:22,340 несколько большим в нечто несколько меньше, я утверждаю, что мы можем разрешить его 1064 00:46:22,340 --> 00:46:26,040 возможно, немного более элегантно, с точки конструкции, с меньшим количеством кода, 1065 00:46:26,040 --> 00:46:30,980 и может быть, даже решить проблемы, которые будет сложнее, так как мы в конечном счете 1066 00:46:30,980 --> 00:46:33,280 см., решая чисто итеративно. 1067 00:46:33,280 --> 00:46:35,980 >> Но захватывающим, что я сделал хотите, чтобы оставить нас было на это. 1068 00:46:35,980 --> 00:46:40,720 Позвольте мне идти вперед и открыть до файла из - 1069 00:46:40,720 --> 00:46:44,300 На самом деле, меня отпустили и сделать это очень быстро. 1070 00:46:44,300 --> 00:46:46,875 Позвольте мне пойти дальше и предложить следующем. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Среди код сегодняшняя этот файл здесь. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Вот эта вот, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Так что это глупая маленькая программа, которая Я на скорую руку, что утверждает, что делать 1076 00:47:06,260 --> 00:47:06,940 следующем. 1077 00:47:06,940 --> 00:47:10,140 В основном, это сначала заявляет десятичного называются X и присваивает его 1078 00:47:10,140 --> 00:47:11,100 значение 1. 1079 00:47:11,100 --> 00:47:13,520 Тогда он объявляет Целочисленное Y и присваивает ей значение 2. 1080 00:47:13,520 --> 00:47:15,310 Затем он выдает какие х и у. 1081 00:47:15,310 --> 00:47:17,781 Тогда он говорит, замена, точка точка точка. 1082 00:47:17,781 --> 00:47:21,670 >> Затем он утверждает, что вызов функции называется своп, переходя в X и 1083 00:47:21,670 --> 00:47:24,290 у, идея которого в том, что, мы надеемся, х и у вернется 1084 00:47:24,290 --> 00:47:25,620 другой, противоположный. 1085 00:47:25,620 --> 00:47:27,110 Тогда утверждают поменялись местами! 1086 00:47:27,110 --> 00:47:28,420 с восклицательным знаком. 1087 00:47:28,420 --> 00:47:30,190 Тогда она выводит х и у. 1088 00:47:30,190 --> 00:47:33,480 >> Но оказывается, что это очень Простая демонстрация вниз 1089 00:47:33,480 --> 00:47:35,570 Здесь на самом деле детская коляска. 1090 00:47:35,570 --> 00:47:38,870 Даже если я объявляю временный переменной и временно положить в 1091 00:47:38,870 --> 00:47:42,010 его, то я переназначении значение б - 1092 00:47:42,010 --> 00:47:45,080 которая чувствует себя разумно, потому, что я сохранены копии при темп. 1093 00:47:45,080 --> 00:47:48,410 Тогда я б обновления на равную все, что было при темп. 1094 00:47:48,410 --> 00:47:51,610 Такая оболочка игра перемещения в В и В в С помощью этой 1095 00:47:51,610 --> 00:47:54,360 среднего человека по имени Temp чувствует вполне разумно. 1096 00:47:54,360 --> 00:47:57,270 >> Но я утверждаю, что когда я запускаю эту кода, как я сделаю сейчас - 1097 00:47:57,270 --> 00:47:59,490 Позвольте мне идти вперед и вставьте его здесь. 1098 00:47:59,490 --> 00:48:01,995 Я буду называть эту noswap.c. 1099 00:48:01,995 --> 00:48:05,630 И как следует из названия, это не будет правильной программе. 1100 00:48:05,630 --> 00:48:09,460 Не делайте noswap. / нет подкачки. 1101 00:48:09,460 --> 00:48:12,110 X = 1, Y = 2, замена, поменяться местами. 1102 00:48:12,110 --> 00:48:14,220 х равен 1, у равен 2. 1103 00:48:14,220 --> 00:48:16,920 Это в корне неправильно, даже хотя это кажется совершенно 1104 00:48:16,920 --> 00:48:17,730 разумным мне. 1105 00:48:17,730 --> 00:48:21,330 И есть причины, но мы не собираемся выявить причину только пока. 1106 00:48:21,330 --> 00:48:24,610 >> Пока второй захватывающим я хотел оставит у вас есть то, 1107 00:48:24,610 --> 00:48:27,120 Объявление виды на скидочных купонов. 1108 00:48:27,120 --> 00:48:31,590 Наши инновации с конца дней в этом году спровоцировал нетривиальное количество 1109 00:48:31,590 --> 00:48:33,830 вопросов, который был В наши намерения не. 1110 00:48:33,830 --> 00:48:36,590 Целью этих скидочных купонов, согласно которому, если вы часть проблемы 1111 00:48:36,590 --> 00:48:39,850 установить рано, таким образом получая дополнительный день, было действительно, чтобы помочь вам, ребята, помогите 1112 00:48:39,850 --> 00:48:42,420 сами начинают рано, отсортируйте побочных стимулирования вас. 1113 00:48:42,420 --> 00:48:44,880 Помогает нам распределить нагрузку между Часы работы лучше, чтобы 1114 00:48:44,880 --> 00:48:45,740 это своего рода беспроигрышная. 1115 00:48:45,740 --> 00:48:48,860 >> К сожалению, я думаю, что мои инструкции не было, на сегодняшний день, очень ясно, так что 1116 00:48:48,860 --> 00:48:52,230 Я вернулся в эти выходные и обновляется В спецификации больше, смелее текст 1117 00:48:52,230 --> 00:48:53,600 объясните пули, как эти. 1118 00:48:53,600 --> 00:48:56,900 И просто сказать, что это более открыто, путем умолчанию, наборы проблемы обусловлены четверг 1119 00:48:56,900 --> 00:48:58,400 в полдень, в учебную программу. 1120 00:48:58,400 --> 00:49:02,030 Если вы начинаете рано, завершающая часть вопрос, поставленный среду в 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, часть, которая относится к купон код, идея в том, что вы можете расширить 1122 00:49:05,170 --> 00:49:07,710 Вашей срок P не установлена ​​до пятницы. 1123 00:49:07,710 --> 00:49:10,890 То есть, откусила крошечный часть р установлено относительно того, что обычно является 1124 00:49:10,890 --> 00:49:13,200 более серьезная проблема, и вы покупаете себе дополнительный день. 1125 00:49:13,200 --> 00:49:15,190 Опять же, он получает вас думать о Поставленная задача, получает вас к 1126 00:49:15,190 --> 00:49:16,380 Часы работы раньше. 1127 00:49:16,380 --> 00:49:20,670 Но проблема скидочный купон по-прежнему требуется, даже если вы ничего не пишите. 1128 00:49:20,670 --> 00:49:23,340 >> Но еще более убедительно это. 1129 00:49:23,340 --> 00:49:26,520 (Шепотом) А тех людей, оставляя рано собираются пожалеете. 1130 00:49:26,520 --> 00:49:28,620 Как те люди, на балконе. 1131 00:49:28,620 --> 00:49:32,510 Прошу прощения заранее, чтобы люди на балкон по причинам, которые будут 1132 00:49:32,510 --> 00:49:33,920 очистить через минуту. 1133 00:49:33,920 --> 00:49:37,050 >> Так что нам повезло иметь один из CS50 бывший глава обучения стипендиатов 1134 00:49:37,050 --> 00:49:39,302 Компания под названием dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Они очень щедро пожертвовал скидочный купон здесь для этого много места, 1136 00:49:45,500 --> 00:49:48,180 который по сравнению с обычная 2 гигабайта. 1137 00:49:48,180 --> 00:49:51,740 Так что то, что я думал, что мы могли бы сделать на этом Последнее замечание сделать немного поддавки, 1138 00:49:51,740 --> 00:49:55,380 при этом в какое-то мгновение мы раскроем победитель и кто имеет купон 1139 00:49:55,380 --> 00:49:57,980 кодов, которые можно затем перейти к их Веб-сайт, введите его в, и вуаля, получить 1140 00:49:57,980 --> 00:50:01,370 намного больше пространства Dropbox для вашего прибор и для ваших личных файлов. 1141 00:50:01,370 --> 00:50:05,690 >> И первый, кто хотел бы принять участие на этом рисунке? 1142 00:50:05,690 --> 00:50:09,630 Хорошо, теперь, что делает его еще более увлекательным. 1143 00:50:09,630 --> 00:50:14,010 Человек, который получает эту 25-гигабайтный код купона - который далеко 1144 00:50:14,010 --> 00:50:16,150 более убедительными, чем поздно дней в настоящее время, возможно - 1145 00:50:16,150 --> 00:50:20,620 это тот, кто сидит на вершине подушка сиденья под которой имеется 1146 00:50:20,620 --> 00:50:21,620 что код купона. 1147 00:50:21,620 --> 00:50:23,480 Теперь вы можете смотреть под ваша подушка сиденья. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [ВОСПРОИЗВЕДЕНИЕ ВИДЕО] 1150 00:50:29,680 --> 00:50:31,620 >> -Раз, два, три. 1151 00:50:31,620 --> 00:50:35,015 >> [Крики] 1152 00:50:35,015 --> 00:50:35,985 >> -Вы получаете автомобиль! 1153 00:50:35,985 --> 00:50:36,670 Вы получаете автомобиль! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID МАЛАН: Мы увидим Вы в среду. 1155 00:50:37,970 --> 00:50:38,904 >> -Вы получаете автомобиль! 1156 00:50:38,904 --> 00:50:39,371 Вы получаете автомобиль! 1157 00:50:39,371 --> 00:50:40,305 Вы получаете автомобиль! 1158 00:50:40,305 --> 00:50:41,706 Вы получаете автомобиль! 1159 00:50:41,706 --> 00:50:43,107 Вы получаете автомобиль! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID МАЛАН: Балкон люди, приходите здесь на передний план, 1161 00:50:45,530 --> 00:50:46,866 где у нас есть дополнительные услуги. 1162 00:50:46,866 --> 00:50:50,282 >> -Каждый получает автомобиль! 1163 00:50:50,282 --> 00:50:52,234 Каждый получает автомобиль! 1164 00:50:52,234 --> 00:50:52,722 >> [КОНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] 1165 00:50:52,722 --> 00:50:54,590 >> Рассказчик: На следующей CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> SPEAKER 5: О боже мой Гоша Гоша Гоша Гоша Гоша Гоша Гоша Гоша Гоша - 1167 00:51:00,374 --> 00:51:02,106 >> [Ukelele ИГРЫ]