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