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